整数除算演算

1 ビットずつ商を計算する符号無/有の 32 ビット除算。 現段階ではひとまず完了(19971213)

簡単な仕様を以下に示す。

• 32 ビット入力 a , b と 32 ビット出力 c から成る。
• それ以外に入力として、符号付きの除算かどうかを示す signed を持つ。
• 更に出力には、0 除算フラグを持つ。 このフラグが立った際は、商のビットは 32 ビット全て 1 を立たせている。( 混乱を避けるため )

整数と浮動小数点の除算は、丸めの問題等で少し芸風が違うので、やはり整数 に絞って考えることにする。

まずは符号なしから。

• 除数 b をエンコードする ( div_encodea , div_encodeb )

module div_encodea(b,enca);
        input [31:0] b;
        output [4:0] enca; // 0 ~ 31

module div_encode(b,encb);
        input [31:0] b;
        output [4:0] encb; // 0 ~ 31

当初は一つのモジュールだったが、一つにすると何故か倍くらい遅い回路が生 成されてしまうので、別々にすることにした。 除数 b を見て、何ビット左シフトすれば MSB が 1 になるかというビット encb を返す。この 32 ビットに対して、更に MSB に 1 ビット 0 を付加す ることで、0.5 以上 1 未満の固定小数点を作り、除算のお膳立てが揃うこと になる。

また、被除数 a も 31 - encb ビット右シフトさせる (予定)もしかしたら 32 - encb とかになるかも。 この値を enca として出力する。

• 除数 b を左シフトする ( div_lsft )

除数 b を 0.5 以上 1 未満になるようにシフトする。

module div_lsft(b,encb,sfb);
        input [31:0] b;
        input [4:0] encb; // 0 ~ 63 ( 32 )
        output [31:0] sfb;

• 被除数 a を右シフトする ( div_rsft )

被除数 a を encodea ビット右にシフトする。出力は 63 ビットになる。

module div_rsft(a,enca,sfa);
        input [31:0] a;
        input [4:0] enca; // 0 ~ 31
        output [62:0] sfa;

• 除数、被除数を正数に変換する ( div_complement )

module div_complement(in,signed,out);
        input [31:0] in;
        input signed;
        output [31:0] out;

今回実装している除算アルゴリズムは、正数同士しか受けつけないため、 被除数を正の数に変換しておく必要がある。 除数 / 被除数について、2 の補数を取る条件は

1. 演算が符号付き除算であること、即ち signed が 1 であること
2. 除数 / 被除数が負数であること、即ち MSB が 1 であること

の 2 つが同時に成立していることである。

• 被除数と除数を正規化するためのエンコードを行う ( div_encode )

module div_encode(in,enc);
        input [31:0] in;
        output [5:0] enc;

被除数 a と除数 b の両方を正規化する。整数の場合は除数のみ正規化すれば いいと思うが、浮動小数点除算のお流れで設計しているのでこのままいく。

• 被除数と除数をシフトする ( div_presft )

module div_presft(in,sft,out);
        input [31:0] in;
        input [5:0] sft; // 0 ~ 64
        output [31:0] out; // including round bit & sticky bit

• 商の選択、部分剰余の計算を行う ( div_qselect_top , div_qselect )

module div_qselect_top(b,a,po,mo,zpo,zno);
        input [32:0] b; // divisor
        input [32:0] a; // plusone , minusone 
        output [32:0] po,mo; // sum/carry of partial remainder , output
        output [31:0] zpo,zno;

module div_qselect(b,pi,mi,zpi,zni,po,mo,zpo,zno);
        input [32:0] b; // divisor
        input [32:0] pi,mi; // plusone , minusone 
        input [30:0] zpi,zni; // on-the-fly conversion
        output [32:0] po,mo; // sum/carry of partial remainder , output
        output [31:0] zpo,zno;

モジュール div_qselect_top では、最初の商ビットを 1 として計算している。 それ以降の商の判定は div_qselect で行う。

キャリーセーブ表現の部分剰余 pi , mi から商を判定して

1. 次の部分剰余 po , mo
2. on-the-fly 変換を施した商ビット列 zpo , zno

を返す。

冗長表現されている部分剰余の上位 3 ビットから商を選択する。

部分剰余の CSA のアルゴリズムは、商が 1 、即ち減算演算を行うとき、各ビッ トの出力は以下の通り。

商が -1 のとき、即ち加算演算のときは以下の通り

また、on - the - fly 変換以下の表に基づく。

• 入力の選択を行う ( div_premux )

• 商の微調整を行う ( div_mux )

本来なら名前を div_postmux にすべきだが、div_premux の登場を考慮してい なかったためこのようなややこしい名前になってしまった。 整数除算に固有か？

• 2 つの入力の桁の差に基づいてシフトを行う ( div_postsft )

この操作は、この除算アルゴリズムを浮動小数点にも適用させようともくろん でいるために必要となっているステップ。

• 2 つの入力の桁の差に基づいてシフトを行う ( div_signconv )

異符号同士の除算についても、まず正に変換してから実際に除算を行っているため この最後の段階で 2 の補数を取らなくてはならない。 この 2 回補数を取る操作は、オーバーヘッドが大きいように見えるが、これ をしないで、全て商選択ルーチンに押し込めてしまうと、1 回に商を選択する 時間が大きくなってしまい、かえって遅くなりそうな感じがする。なんといっ ても商を選択する回数が 32 回もあるのだから。でも頑張れば、この補数操作 は不要になって、高速な動作を行うことができるようになるはずである。

除算は、加減算・乗算と違って、毎サイクルオペランドを投入できないので、 ステージの割り方を考える必要がある。

こんな感じでステージを割ると、10 サイクル毎に投入が可能となる。

第 1 ステージはこんな感じ

module div_1(CLK,a,b,signed,start,
fstart,fp,fm,fzp,fzn,fconv,fdf,fnb);

        input CLK;
        input [31:0] a,b;
        input signed; 
	// signed operation or unsigned operation
        input start;

        output fstart;
        output [32:0] fp,fm;
        output [31:0] fzp,fzn;
        output fconv;
        output [5:0] fdf;
        output [32:0] fnb;

第 2 ・第 3 ステージはこんな感じ

module div_2(CLK,
fstart,fnb,fp,fm,fzp,fzn,fconv,fdf,
snb,sp,sm,szp,szn,sconv,sdf,
dnb,dp,dm,dzp,dzn,dconv,ddf);

        input CLK;
        input fstart;
        input [32:0] fnb;
        input [32:0] fp,fm;
        input [31:0] fzp,fzn;
        input fconv;
        input [5:0] fdf;

        input [32:0] snb;
        input [32:0] sp,sm;
        input [31:0] szp,szn;
        input sconv;
        input [5:0] sdf;

        output [32:0] dnb;
        output [32:0] dp,dm;
        output [31:0] dzp,dzn;
        output dconv;
        output [5:0] ddf;

module div_3(CLK,nb,p31,m31,zp31,zn31,conv,df,fq,fzerod);
        input CLK;
        input [32:0] nb;
        input [32:0] p31,m31;
        input [31:0] zp31,zn31;
        input conv;
        input [5:0] df;

        output [31:0] fq;
        output fzerod; // zero divide

描いていないが、第 2 ステージの出力は、そのまま第 2 ステージの入力 ( マルチプレクサの入力 ) へフィードバックもさせている。この配線は、一つ 上の階層のモジュールで行うことにする。