Mul. Design

浮動小数点乗算演算

マッチョ書きかけ

目標

整数型の32bit乗算回路を設計してみたところ、3サイクルあれば、まぁ動きそうな感じがした。浮動小数点は、正規化の部分があるものの、加減算より複雑にならずに結構簡単にいきそうな予感がする。目標は 8 ～ 9 サイクル (19970930)。 5 サイクルに変更 ( 19971017 )
更に 4 サイクルへ。多分いける。目途がついたので、一旦サスペンド ( 19971027 )
単精度と例外処理を実装すべく再開。なぜか除算の方が先に終わってしまっている ( 19971226 )

進行状況

終わっていること
1. 通常パスの入出力全般 ( 19971027 )
2. 組み合わせ回路として見たときの、入力から出力までの遅延の見積もり ( 大雑把 ) ( 19971027 )
終わってないこと
1. トラップの引数等も含めた完全な入出力インターフェースの仕様 ( 19971027 )
2. 例外パス全部 ( 19971027 )
3. 合成 ( 爆 )
  そして、パイプライン化に際してどこまでを 1 ステージとして分割するか ( 19971027 )

上図は気持ちの問題で、必ずしも設計と 1 対 1 になっているわけではない。インターフェースも少し違う。

やりなおし : 最後の詰め

単精度、倍精度も照準に合わせ、かつ例外の処理もちゃんとできるものを作ろう。

特殊数の演算 (EXCEPTION path)

ここで特殊数とは、SNaN と QNaN と Inf と 0 を指し、入力に対してこれらを排他的にアサートされる 4 ビットで入力の状態を決定する。全てのビットが立っていなければ、それは通常の有限数を意味する。以下の仕様に基づいて作る。

結果 / 例外一覧

演算種類	結果	例外
SNaN × SNaN SNaN × QNaN と QNaN × SNaN SNaN × 0 と 0 × SNaN SNaN × Inf と Inf × SNaN SNaN × W と W × SNaN Inf × 0 と 0 × Inf	QNaN	V
QNaN × QNaN QNaN × 0 と 0 × QNaN QNaN × Inf と Inf × QNaN QNaN × W と W × QNaN	QNaN	-
0 × 0 W × 0 と 0 × W	符号付き 0	-
Inf × Inf Inf × W と W × Inf	符号付き Inf	-
W × W	?(W,Inf,0)	?(O,U,I)

V : Invalid Operation , O : Overflow , Z : Zero Divide , U : Underflow , I : Inexcact

モジュール毎の動作

精度に応じて符号、指数、仮数に分割する ( fmul_split )

module fmul_split(in,isdouble,s,e,upf);
	input [63:0] in;
	input isdouble;
	output s; // sign 
	output [10:0] e; // biased exp ( zero adjusted )
	output [52:0] upf; // unpacked mantissa

被乗数と乗数を規格化するためのエンコードを行う ( fmul_encode )

module fmul_encode(upf,enc);
	input [52:0] upf;
	output [5:0] enc;

エンコードに基づき、被乗数と乗数の規格化シフトを行う ( fmul_presft )

module fmul_presft(upf,enc,presft);
        input [52:0] upf;
        input [5:0] enc;
        output [52:0] presft;

指数の前調整をする ( fmul_preadje )

module fmul_preadje(ea,eb,enca,encb,isdouble,c4_0,c4_1,sftbit_0,sftbit_1);
	input [10:0] ea,eb;
	input [5:0] enca,encb;
	input isdouble;
	output [12:0] c4_0,c4_1; // c4_0 : C3 , c4_1 : C3 + 1
	output [12:0] sftbit_0,sftbit_1; // post sfift bit

オーバーフロー時の結果をINFにするかどうか判断する ( fmul_resultinf )

module fmul_resultinf(rmode,sa,sb,sc,ovi);
        input [1:0] rmode; // roundmode
        input sa,sb;
        output sc;  // sign of result
        output ovi;

例外パスの処理を行う ( fmul_exception )

module fmul_exception(a,b,isdouble,out,flags,istrue);
        input [63:0] a,b;
        input isdouble;
        output [63:0] out;
        output [4:0] flags; // V,O,Z,U,I
        output istrue; // output is TRUE or Don't care

部分積を生成する ( fmul_boothencode )

module fmul_boothencode(upfa,partb,partp);
        input [52:0] upfa;
        input [2:0] partb;
        output [54:0] partp;
        // partial product , 2's complement expression

27 個の部分積を 2 つになるまで圧縮する ( fmul_comp1_0 ～ fmul_comp7_0 )

指数の前調整の際の予測解を選択する ( fmul_premux )

module fmul_premux(c4_0,c4_1,sftbit_0,sftbit_1,msbz,c4,sftbit);
        input [12:0] c4_0,c4_1;
        input [12:0] sftbit_0,sftbit_1;
        input msbz; // MSB of Z ( Z = X mul Y )
        output [12:0] c4;
        output [12:0] sftbit;

デノーマル時に仮数のシフトを行う ( fmul_postsft )

module fmul_postsft(o,sftbit,postsft);
        input [105:0] o;
        input [5:0] sftbit; // 0 ~ 64
        output [54:0] postsft; // including round bit & sticky bit

丸めを行う ( fmul_round with fmul_roundlogic )

module fmul_round(in,sib,rob,stb,rmode,round,cbr,iex);
        input [52:0] in;
        input sib,rob,stb; // sign bit , round bit , sticky bit
        input [1:0] rmode;
        output [52:0] round;
        output cbr; // carry of rounded result
        output iex; // inexact result

指数 ( 等 ) の後調整を投機的に行う ( fmul_postadje )

module fmul_postadje(c4,ovi,isdouble,
c5_0,c5_1,of_0,of_1,uf_0,uf_1,zo_0,zo_1);

        input [12:0] c4;
        input ovi; 
	// output infinity as a result  if overflow
        input isdouble;

        output [12:0] c5_0,c5_1;
        output of_0,of_1; 
        // overflow
        output uf_0,uf_1; 
        // underflow ( both exact and inexact ) 
        output [52:0] zo_0,zo_1;
        // result of Z ( X mul Y ) if overflow and nontrap

丸めの結果に基づいて後調整の選択を行う ( fmul_postmux )

これで最後にしたい乗算器の合成結果

モジュール名	cost prim.	時間 (ns)	必要数	小計 prim.
fmul_split	198	1.866	2	396
fmul_encode	310	5.152	2	620
fmul_presft	875	4.414	2	1750
fmul_preadje	883	8.546	1	883
fmul_resultinf	9	1.154	1	9
fmul_exception	655	5.486	1	655
fmul_boothencode	786	6.691	27	21222
fmul_comp1_0	452	1.204	9	4068
fmul_comp2_0	478	1.244	3	1434
fmul_comp2_1	475	1.181	3	475
fmul_comp3_0	522	1.274	1	522
fmul_comp3_1	520	1.280	1	520
fmul_comp3_2	529	1.450	1	529
fmul_comp3_3	476	1.015	1	476
fmul_comp4_0	590	1.495	1	590
fmul_comp4_1	589	1.407	1	589
fmul_comp5_0	703	1.765	1	703
fmul_comp5_1	510	1.008	1	510
fmul_comp6_0	729	1.204	1	729
fmul_comp7_0	685	0.835	1	685
fmul_cla	1142	13.724	1	1142
fmul_premux	87	1.334	1	87
fmul_postsft	2311	6.151	1	2311
fmul_round	862	6.778	1	862
fmul_postadje	148	6.787	1	148

no clock, opt area -high, opt timing -high にて合成
[ primitive cost × 必要数 ] で、
必要な primitive cost が計算できる。

ステージの分割

インターフェースは以下の通り。

module fmul_1(CLK,a,b,isdouble,rmode,
disdouble,drmode,dea,deb,denca,dencb,dpresfta,dpresftb,dovi,dsc,
dexceout,dexceflags,disexcetrue);
        input CLK;
        input [63:0] a,b;
        input isdouble;
        input [1:0] rmode;

        output disdouble;
        output [1:0] drmode;
        output [10:0] dea,deb;
        output [5:0] denca,dencb;
        output [52:0] dpresfta,dpresftb;
        output dovi;
        output dsc;
        output [63:0] dexceout;
        output [4:0] dexceflags;
        output disexcetrue;

module fmul_2(CLK,
isdouble,rmode,ea,eb,enca,encb,presfta,presftb,ovi,sc,
exceout,exceflags,isexcetrue,
disdouble,drmode,dc4_0,dc4_1,dsftbit_0,dsftbit_1,dos,doc,dovi,dsc,
dexceout,dexceflags,disexcetrue);
        input CLK;

        input isdouble;
        input [1:0] rmode;
        input [10:0] ea,eb;
        input [5:0] enca,encb;
        input [52:0] presfta,presftb;
        input ovi;
        input sc;
        input [63:0] exceout;
        input [4:0] exceflags;
        input isexcetrue;

        output disdouble;
        output [1:0] drmode;
        output [12:0] dc4_0,dc4_1;
        output [12:0] dsftbit_0,dsftbit_1;
        output [105:0] dos;
        output [96:0]  doc;
        output dovi;
        output dsc;
        output [63:0] dexceout;
        output [4:0] dexceflags;
        output disexcetrue;

module fmul_3(CLK,
isdouble,rmode,c4_0,c4_1,sftbit_0,sftbit_1,os,oc,ovi,sc,
exceout,exceflags,isexcetrue,
disdouble,drmode,dc4,dsftbit,dz,dovi,dsc,
dexceout,dexceflags,disexcetrue);
        input CLK;

        input isdouble;
        input [1:0] rmode;
        input [12:0] c4_0,c4_1;
        input [12:0] sftbit_0,sftbit_1;
        input [105:0] os;
        input [96:0]  oc;
        input ovi;
        input sc;
        input [63:0] exceout;
        input [4:0] exceflags;
        input isexcetrue;

        output disdouble;
        output [1:0] drmode;
        output [12:0] dc4;
        output [12:0] dsftbit;
        output [105:0] dz;
        output dovi;
        output dsc;
        output [63:0] dexceout;
        output [4:0] dexceflags;
        output disexcetrue;

module fmul_4(CLK,
isdouble,rmode,c4,sftbit,z,ovi,sc,
exceout,exceflags,isexcetrue,
disdouble,dc5_0,dc5_1,dzo_0,dzo_1,dof_0,dof_1,duf_0,duf_1,dcbr,dround,diex,dsc,
dexceout,dexceflags,disexcetrue);

        input CLK;
        input isdouble;
        input [1:0] rmode;
        input [12:0] c4;
        input [12:0] sftbit;
        input [105:0] z;
        input ovi;
        input sc;
        input [63:0] exceout;
        input [4:0] exceflags;
        input isexcetrue;

        output disdouble;
        output [12:0] dc5_0,dc5_1;
        output [52:0] dzo_0,dzo_1;
        output dof_0,dof_1;
        output duf_0,duf_1;
        output dcbr;
        output dround;
        output diex;
        output dsc;
        output [63:0] dexceout;
        output [4:0] dexceflags;
        output disexcetrue;

module fmul_5(
isdouble,c5_0,c5_1,zo_0,zo_1,of_0,of_1,uf_0,uf_1,
cbr,round,iex,sc,
exceout,exceflags,isexcetrue,
out,outflags
);

        input isdouble;
        input [12:0] c5_0,c5_1;
        input [52:0] zo_0,zo_1;
        input of_0,of_1;
        input uf_0,uf_1;
        input cbr;
        input round;
        input iex;
        input sc;
        input [63:0] exceout;
        input [4:0] exceflags;
        input isexcetrue;

	output [63:0] out;
	output [4:0] outflags;

基本部分のアルゴリズム ( その 2 )

最初に考えついた方法は、あまりにももったいないので、やはり 3 - 2 圧縮器 ( CSA ) を使ってみることにする。

この方法は、大きなキャリーの伝播は 1 回のみとして、それ以外は、各桁をできるだけ独立に計算しようというものである。全加算器の 3 入力に対して、同一桁のビットと、桁上がりのビットの 2 出力を吐くようにやっていく。但し、これは非対称の汚い回路ができるので、一般性に乏しい。

1.

まず、2 Booth によってできた 27 個の 55 ビット部分積を、上から順に ( このルールは色々考えられるが、今回は全ての段でこの条件を適用する ) 3 つずつ区切り、57 ビット全加算器にかける。下位 2 ビットはスルーする。すると、同一桁からは、59 ビットの和が 9 個、繰り上がりの桁からは、57 ビットの和が 9 個できる。


55b ( total 27 )  -> 57+2b(through2) , 57b ( total 18 )
    
                                                     0000000000000000000000000000000000000000000000000000000
                                                   1111111111111111111111111111111111111111111111111111111
                                                +2222222222222222222222222222222222222222222222222222222
                                                ----------------------------------------------------------
                                                 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                                yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                                012345678901234567890123456789012345678901234567890123456 
                                                0         1         2         3         4         5      
 
 
                                               3333333333333333333333333333333333333333333333333333333
                                             4444444444444444444444444444444444444444444444444444444
                                          +5555555555555555555555555555555555555555555555555555555
                                          ----------------------------------------------------------
                                           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                          yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
 
                                 
                                         6666666666666666666666666666666666666666666666666666666
                                       7777777777777777777777777777777777777777777777777777777
                                    +8888888888888888888888888888888888888888888888888888888
                                    ----------------------------------------------------------
                                     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                    yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
 
 
                                   9999999999999999999999999999999999999999999999999999999
                                 0000000000000000000000000000000000000000000000000000000
                              +1111111111111111111111111111111111111111111111111111111
                              ----------------------------------------------------------
                               xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                              yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
 
                                 
                             2222222222222222222222222222222222222222222222222222222
                           3333333333333333333333333333333333333333333333333333333
                        +4444444444444444444444444444444444444444444444444444444
                        ----------------------------------------------------------
                         xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
 

                       5555555555555555555555555555555555555555555555555555555
                     6666666666666666666666666666666666666666666666666666666
                  +7777777777777777777777777777777777777777777777777777777
                  ----------------------------------------------------------
                   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                  yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

               
                 8888888888888888888888888888888888888888888888888888888
               9999999999999999999999999999999999999999999999999999999
            +0000000000000000000000000000000000000000000000000000000
            ----------------------------------------------------------
             xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
            yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy


           1111111111111111111111111111111111111111111111111111111
         2222222222222222222222222222222222222222222222222222222
      +3333333333333333333333333333333333333333333333333333333
      ----------------------------------------------------------
       xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
      yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

    
     4444444444444444444444444444444444444444444444444444444
   5555555555555555555555555555555555555555555555555555555
+O666666666666666666666666666666666666666666666666666666
----------------------------------------------------------
 dxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
ddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

2.

それを上から 3 個ずつ区切ると、今度は偶数と奇数で振舞いが異なる。

0 オリジンで偶数番目の 3 セットは、( 59 , 57 , 59 / 62 , 3 ) 加算器にかける
( 59 , 57 , 59 ビットを入力とする、62 ビット全加算器 + 3 ビットスルー )
奇数番目の 3 セットは、( 57 , 59 , 57 / 60 , 3 ) 加算器にかける。

すると、

偶数の同一桁からは、 65 ビットが 3 本
偶数のキャリーからは、 62 ビットが 3 本
奇数の同一桁からは、63 ビットが 3 本
( 但し、最後の 1 本の MSB そば 2 ビットはダミー。実質 61 ビット )
奇数のキャリーからは、 60 ビットが 3 本
( 但し、最後の 1 本の MSB そば 3 ビットはダミー。実質 57 ビット )

でる。


57+2b , 57b , 57+2b -> 62+3b , 63b ( total 3 )
57b , 57+2b , 57b  -> 60+3b , 60b , including head partial ( total 3 )

                                                  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                                 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                           +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                           ---------------------------------------------------------------
                                            xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                                           yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                           01234567890123456789012345678901234567890123456789012345678901 
                                           0         1         2         3         4         5         6


                                           yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                      xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                                    +yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                    -------------------------------------------------------------
                                     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                                    yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                    012345678901234567890123456789012345678901234567890123456789
                                    0         1         2         3         4         5         


                                xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                               yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                         +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                         ---------------------------------------------------------------
                          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                         yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy


                         yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                    xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
                  +yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                  -------------------------------------------------------------
                   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                  yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy


              xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
             yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
       +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
       ---------------------------------------------------------------
        xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
       yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy


       yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
  dxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzz
+ddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
-------------------------------------------------------------
 ddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
dddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

3.

これから先は、もう一般則は無く、各々特注のモジュールを使用する必要がある。

( 65 , 62 , 63 / 68 , 4 ) 加算器を用いて、72b , 68b を出力
( 60 , 65 , 62 / 66 , 5 ) 加算器を用いて、71b , 66b を出力
( 63 , 60 , 65 / 70 , 4 ) 加算器を用いて、74b , 70b を出力
( 62 , 61 , 57 / 61 , 5 ) 加算器を用いて、66b , 61b を出力
但し、このモジュールのキャリー出力の MSB はダミー出力とする ( 実質的に 66b , 60b 出力となる )


62+3b , 62b , 60+3b  -> 68+4b , 68b
60b , 62+3b , 62b  -> 66+5b , 66b
60+3b , 60b , 62+3b  -> 70+4b , 70b
62b , 60+3b , 60b  -> 61+5b , 61b ( 1 bit dummy ) ( head partial )

    
                                             xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                                            yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                     +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                                     ---------------------------------------------------------------------
                                      xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzz
                                     yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                                     01234567890123456789012345678901234567890123456789012345678901234567 
                                     0         1         2         3         4         5         6


                                     yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                         +yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                         -------------------------------------------------------------------
                          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
                         yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                         012345678901234567890123456789012345678901234567890123456789012345
                         0         1         2         3         4         5         6


                    xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
                   yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
        -----------------------------------------------------------------------
         xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzz
        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        0123456789012345678901234567890123456789012345678901234567890123456789
        0         1         2         3         4         5         6


        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
  ddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
+dddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
   --------------------------------------------------------------
 dddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
dddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
   0123456789012345678901234567890123456789012345678901234567890
   0         1         2         3         4         5

( 72 , 68 , 71 / 79 , 5 ) 加算器を用いて、84b , 79b を出力
( 66 , 74 , 70 / 75 , 8 ) 加算器を用いて、83b , 75b を出力
66b , 60b はスルー


68+4b , 68b , 66+5b  -> 79+5b , 79b
66b , 70+4b , 70b -> 75+8b , 75b
61+5b , 60b ( head partial ) -> through
    
                                       xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzz
                                      yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                          +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
                          --------------------------------------------------------------------------------
                           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
                          yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
                          0123456789012345678901234567890123456789012345678901234567890123456789012345678
                          0         1         2         3         4         5         6         7


                          yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzz
        +yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        ----------------------------------------------------------------------------
         xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzz
        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        012345678901234567890123456789012345678901234567890123456789012345678901234
        0         1         2         3         4         5         6         7


  dddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
 dddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
     012345678901234567890123456789012345678901234567890123456789
     0         1         2         3         4         5

( 84 , 79 , 83 / 96 , 6 ) 加算器を用いて、102b , 96b を出力
( 75 , 66 , 60 / 66 , 12 ) 加算器を用いて、78b , 66b を出力。但し、66b の MSB はダミー


 79+5b , 79b , 75+8b  -> 96+6b , 96b
 75b , 61+5b , 60b ( head partial ) -> 66+12b , 66b ( 1 bit dummy )
    
                           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
                          yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        +xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzz
        -------------------------------------------------------------------------------------------------
         xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzz
        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
        0         1         2         3         4         5         6         7         8         9



        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
  dddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzz
+ddddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
-----------------------------------------------------------------------
 ddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzzzzzz
ddddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
    012345678901234567890123456789012345678901234567890123456789012345
    0         1         2         3         4         5         6

( 102 , 96 , 78 / 99 , 7 ) 加算器を用いて 106b , 99b を出力。但し、99b の MSB はダミー
65b はスルー



96+6b , 96b , 66+12b ( headpartial ) -> 99+7b , 98b
65b ( headpartial ) -> through 
    
         xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzz
        yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
+ddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzzzzzz
    ----------------------------------------------------------------------------------------------------
 ddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzz
ddddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
    012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678
    0         1         2         3         4         5         6         7         8         9


ddddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
     01234567890123456789012345678901234567890123456789012345678901234
     0         1         2         3         4         5         6

( 106 , 98 , 65 / 98 , 8 ) 加算器を用いて、106b , 98b を出力する。 98b の MSB はダミーとする


99+7b , 98b , 65b ( headpartial ) -> 98+8b , 98b ( 1 bit dummy )

    
  ddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzz
 dddddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
+dddddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
     ---------------------------------------------------------------------------------------------------
 dddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzz
dddddYyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
      0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
      0         1         2         3         4         5         6         7         8         9         0


and CLA
 dddddxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzzzzzzz
ddddddyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
	 -----------------------------------------------------------------------------------------------------------
      0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
      0         1         2         3         4         5         6         7         8         9         0

以上の方式に従うと、

モジュール名	cost prim.	時間 (ns)	必要数	小計 prim.
boothencode ( 改 )	787	6.691	27	21249
comp1_0	452	1.204	9	4068
comp2_0	478	1.244	3	1434
comp2_1	475	1.181	3	475
comp3_0	522	1.274	1	522
comp3_1	520	1.280	1	520
comp3_2	529	1.450	1	529
comp3_3	476	1.015	1	476
comp4_0	590	1.495	1	590
comp4_1	589	1.407	1	589
comp5_0	703	1.765	1	703
comp5_1	510	1.008	1	510
comp6_0	729	1.204	1	729
comp7_0	685	0.835	1	685
cla	1142	13.724	1	1142

no clock, opt area -high, opt timing -high にて合成
[ primitive cost × 必要数 ] で、
必要な primitive cost が計算できる。
トータルコストは 33701 で、27 の部分積をエンコードして、最後の 2 つまで圧縮するのに、最悪 15.888 ns かかる。ここまでは、2 サイクルでいける。

これらのモジュールを管理するために、 53b 入力から CLA にかける直前までの部分、即ち boothencode から comp7_0 までの部分を pproduct という一つのモジュール ( 組み合わせ回路 ) にして合成する。その結果、上記の表を下のように変更する。

モジュール名	cost prim.	時間 (ns)	必要数	小計 prim.
pproduct ( 遅いバージョン )	34317	18.453	1	34317
cla	1142	13.724	1	1142

no clock, opt area -high, opt timing -high にて合成したいがしていない

基本以外の部分のアルゴリズム
乗算の基本部分以外にも、浮動小数点で起こり得る、丸め、正規化シフト、デノーマルといった、厄介な問題がまだ残っている。

デノーマルについて
デノーマルが、一般性を大きく失わせる要因となっている。デノーマルに対処する方法は 2 種類考えられる。

53b × 53b の乗算器に投入する前に、あらかじめデノーマルを正規化しておく方法で、乗算前に 53b エンコーダ + 53b バレルシフタが 2 個ずつ、乗算後に 53b バレルシフタが必要
そのまま乗算器に投入して、後からエンコードする方法で、乗算後に 53b ( 106b ? ) エンコーダ + 53b バレルシフタが必要となる

前者は、正規化したオペランドの乗算は、結果の桁が読みやすい ( 桁上がりがあるかないか ) という利点がある。スピードの点ではどちらがよいか、よくわからないが、前者の方が設計が簡単そうな感じがするので、前者でやってみる。 ( 前者は桁が読みやすいから、丸めの処理が簡単になるかと思ったが、そうもいかないらしい。しかし仮数の乗算の結果の桁が予想しやすいので、先行して制御回路を組めるという利点があることは確か。 )

やるべきことを以下に示していく。

入力オペランドを正規化する ( preencode & presft )

主に 2 つの段階に分けられる。
- 2 つのアンパック済の入力オペランドをエンコードして、何ビット左シフトを行えば正規化されるかを計算する ( preencode )
```
module preencode(in,encode);
        input [52:0] in;
        output [5:0] encode;
```
  モジュール preencode は、0 から 53 までを表現する 6 ビット出力である。
  53 が出力されたということは、仮数は 0 であるこということになる。
- その 6 ビットの値を用いてバレルシフタで実際に正規化する ( presft )
```
module presft(in,sft,out);
        input [52:0] in;
        input [5:0] sft;
        output [52:0] out;
```
この preencode , presft の 2 段階を 1 ステップにすると、多入力多出力となってしまうため、合成にやたらと時間がかかってしまう。それと後で何ビットシフトしたかという情報も必要なので、結局 2 つのステップに分割した。

この操作は 2 つの入力に対して行われ、各々、エンコードA とエンコードB を出力する。

2 つの指数の和と調整を積の計算と並列に行う ( preadjexp )

乗算において、返すべき指数の値は、基本的に、入力オペランドの指数の和をとるだけでよいが、ゲタばき表現や、桁上がり等が実際には起こるため、調整を行う必要がある。これを、仮数が 53b × 53b 乗算器に投入されている間に、並列に実行する。
指数の調節において、知るべき情報は 5 つに分けられる

返すべき指数の値の基礎となる、2 つの入力オペランドの指数はいくつか
乗算器にかける前に行う、仮数の正規化シフトが何ビットあったか
乗算器にかけた結果、仮数に桁上がりが起きたかどうか
丸めによって、仮数に桁上がりが起きたかどうか
修正した結果が、浮動小数点数のフォーマットに収まっているかどうか
( デノーマルにする必要はないのか = 仮数を何ビットシフトすればよいのか )

4 と 5 の条件は、互いに関係している。何故ならば、何ビットシフトしたか ( どの 53 ビットを選択して丸めを行うか ) で、丸めの結果は変化し、丸めの結果次第では、指数の修正結果が変わってくるからである。

まず、2 つの入力オペランドである指数の和について考える。ここで、気をつけるべきことは、指数フィールドは、ゲタばき表現 ( biased exponent expression ) であるということに注意する。

倍精度の場合、入力の指数を A , B 、出力の指数を C とすると

ゲタばきA = ゲタなしA + 1023 ,
ゲタばきB = ゲタなしB + 1023 ,
ゲタばきC = ゲタなしC + 1023 ,

ゲタなしC = ゲタなしA + ゲタなしB =
( ゲタばきA - 1023 ) + ( ゲタばきB - 1023 ) =
ゲタばきA + ゲタばきB - 2046 = ゲタばきC - 1023

つまり

ゲタばきA + ゲタばきB = ゲタばきC + 1023
だから、単純に足しただけでは、C は、ゲタばき表現でも 1023 だけ大きな値になってしまっていることに注意する。この段階で、結果の指数は以下のようになる。以下、C の修正のポリシーは、仮数の結果が正規化された状態で、指数を正しく求めることを基本としている。

C1 ( ゲタばき表現 ) = ゲタばきA + ゲタばきB - 1023

しかしこのままでは、オペランドがデノーマルのとき、ゲタばきの指数は、表現している指数よりも 1 小さな値になってしまっているため、正しい指数の和が得られない。( 実際の指数は Emin なのに、デノーマルは Emin - 1 で表現されていることに、その原因がある )
それを調節するために、( アンパック済の ) 仮数の MSB を用いて、更に修正を行う。

C2 = C1 + ( ! MSBofFA ) + ( ! MSBofFB ) =
( ゲタばきA + ( ! MSBofFA ) ) + ( ゲタばきB + ( ! MSBofFB ) ) - 1023

上式で、 ! は否定を、MSBofFA は A のアンパックした仮数の MSB を表す。この式は、オペランドが正規化数ならば、仮数の MSB は 1 なので、その否定は 0 で、何も足されない。デノーマルならば、 MSB は 0 なので、1 が余分に加算され、修正が行われる。

次に、正規化シフト数の影響による指数の修正を考える。正規化シフトは左シフトだから、シフトした分を前の C から引いてやればよい。何ビットシフトしたかという情報をエンコードFA、エンコードFB とすると修正は以下のようになる。

C3 = C2 - エンコードFA - エンコードFB =
( ゲタばきA + ( ! MSBofFA ) ) + ( ゲタばきB + ( ! MSBofFB ) ) - エンコードFA - エンコードFB - 1023

以降、53b × 53b の乗算結果をふまえた修正を行っていく。

今回は、あらかじめ 1.f という形に修正して乗算器に投入しているため、乗算器の出力は、あたかも固定小数点のような扱いが可能である。 ( 但し、f は 52 ビットの 2 進列 )
即ち、正規化したもの同士、53 bit × 53 bit の計算を行い、 106 bit の結果を得たとき、{ 2 . 104 } の形で固定の小数点が存在するのである。しかも

1 ≦ X ＜ 2
1 ≦ Y ＜ 2
ならば
1 ≦ X × Y ＜ 4

だから、106 ビットのうちの整数部にあたる上位 2 ビットのうちどちらかは、必ず 1 であるということになる。
Z = X × Y とおき、以上のことを考慮すると、Z の MSB が 0 なら、Z は正規化されており、指数の修正は行う必要がない。反対に MSB が 1 なら、桁上がりが 1 ビットだけあったと判断でき、これは後で 1 ビット右シフトを行うので、その修正のため指数を +1 だけ修正する。

C4 = C3 + ( MSBofZ ) =
( ゲタばきA + ( ! MSBofFA ) ) + ( ゲタばきB + ( ! MSBofFB ) ) - エンコードFA - エンコードFB + ( MSBofZ ) - 1023

この部分の修正は、乗算器の出力を待ってから行うと時間がかかるため、実際には、乗算器の出力が出る前に MSBofZ が 0 のときと 1 のときの両方について場合分けをして、どんどん先に修正を進めていき、後で正しい方の答えを選択するようにする。しかし上式の考え方に基づいていることは間違いない。

ここで一旦整理する。
もし、結果のフォーマットについて、指数や仮数の範囲に制限がなく、正規化数で表現できるならば、答えは

指数は C4 ( ゲタばき表現 )
仮数は MSBofZ が 0 なら Z で、MSBofZ が 1 なら、Z を 1 ビット右シフトした値 ( この 1 ビット分の修正は C3 -> C4 のときに既に折りこまれている )

であるが、指数の範囲が無限でないことから、デノーマル、オーバーフローという問題が起き、仮数の範囲が無限でないことから、丸めの問題が起こる。以下、その修正について考える。この余計な部分が面倒なのだが。この C4 という値は、トラップの際渡す引数として利用するはずなので、C4 は保存しておく必要がある。

乗算の例外処理

例外の種類	非トラップの結果	トラップの引数
無効演算	Quiet ( ? ) NaN	入力オペランド
0 除算	起こらない	起こらない
オーバーフロー	( 略 )	正規化した Z 、C4 と符号
アンダーフロー	丸めた結果	正規化した Z 、C4 と符号
不正確	丸めた結果	正規化した Z 、C4 と符号

但し、C4 はビットを 1 ビット増やした 2 の補数表現である

まず丸めをどの 53 ビットについて行うか ( 何ビットポストシフトすればよいか ) を判断するために C4 の値で最初の場合分けを行う。

C4 が浮動小数点数フォーマットの指数の範囲内であるならば、Z を ( MSBofZ ) ビット右シフトして、MSB を含まない上位 53 ビット ( MSB より一つ下の位のビットから下 53 ビット ) を丸める。指数 ( C4' ) は C4 を返す。
C4 が浮動小数点数フォーマットの指数の最小値 Emin よりも小さいならば、Z をデノーマルにするために、余分に右シフトしなければならない。シフトする値は ( ( Emin - C4 ) + ( MSBofZ ) ) ビットである。指数 ( C4' ) は Emin - 1 ( つまり 0 ) を返す。また、アンダーフロー例外の準備も行うが、丸めによって、デノーマルから正規化数に敗者復活する可能性があるので、盲目的にやってはいけない。例外の詳細は未定。
C4 が浮動小数点数フォーマットの指数の最大値 Emax よりも大きいならば、オーバーフローの準備を行う。トラップの事を考えて、C4 は保存しておかなければならない。オーバーフローのときは、丸めモードによって、仮数、指数ともに変化するので、オーバーフローの旨を伝えるビットを用意して、この部分ではやらないのが無難ではなかろうか。返す値、例外について、まだ詳細は決まっていない。返り値は、指数 ( C4' ) は Emax か Emax + 1 で、仮数は、100...000 か 111...111 のどちらかであろう。

C4' と書いたのは、実際には使われないで、実際には、丸めによる桁の繰り上がりの存在を考慮した C5 を用いる。 ( 後述 )

それはさておき、C4 とポストシフトのビット数の関係をまとめると、以下のようになる。

C4 とポストシフトの関係

C4	ポストシフト ( bit )
0 以下	( Emin - C4 ) + MSBofZ = Emin - C3
Emin ( 1 ) ～ Emax	MSBofZ
Emax + 1 以上	( don't care : overflow )

結局、上表から、ポストシフトに関する値は、( MSBofZ ) , ( Emin - C3 ) の 2 通りを用意すればよい。しかも、dont'care をうまく使えば、C4 が 0 以下かそうでないかを調べるだけでよく、それは、C4 - 1 の MSB が 0 かどうかで判定できる。

( その根拠は、C4 は 2 の補数表現であるということと、C4 が取る最小値は - 1023 - 53 - 53 = - 1129 となり、12 ビットで表現できる数の最小値 - 2047 よりも大きな数なので、 C4 - 1 をしたときにその MSB が C4 の MSB と比べて変化するのは、 C4 - 1 = 0 、即ち C4 = 1 のときだけに限られるということにある )

実際には、MSBofC4m ( C4 - 1 の MSB ) を制御ビットとして、MSBofZ と Emin - C3 をセレクトするモジュールを構成すればよい。

以上をまとめると

最終的なポストシフトの判定

MSBofC4m	ポストシフト
0	MSBofZ
1	Emin - C3

となる。但しこの段階では、MSBofZ はまだわかっていない状態なので、 MSBofZ を 0 と仮定した場合と、MSBofZ を 1 と仮定した場合の 2 通りを出力する。
このとき、丸め前であるこの段階でオーバーフローが確定しているものに関しては、仮数のシフトビット数は保証しないので、後のロジックで気をつける必要がある。例えば、後の結果 0 の検出は、仮数が 0 であるとともに、オーバーフローをしていないという条件も加えたほうがよい。
( オーバーフロー時は、仮数は不定として考えておくとよいかもしれない )

ここまでをモジュールにしたものが、 preadjexp である。前述した通り

MSBofZ が 0 と仮定したときの C4 である c4_0 ( = C3 ) と、そのときのポストシフト数 sft_0
MSBofZ が 1 と仮定したときの C4 である c4_1 ( = C3 +1 ) と、そのときのポストシフト数 sft_1

の 2 通りの場合をここでは計算、出力しており、後でわかる MSBofZ の値でセレクトする。

module preadjexp(expa,expb,enca,encb,msba,msbb,
				c4_0,c4_1,sft_0,sft_1);
        input [10:0] expa,expb;
        input [5:0] enca,encb;
        input msba,msbb; 
	// FA[52] : MSB of unpacked FA  ( F : mantissa )
        output [12:0] c4_0,c4_1;
	output [12:0] sft_0,sft_1; // post sfift bit

実際にセレクトするモジュールは、 premux である。

module premux(c4_0,c4_1,sft_0,sft_1,msbz,c4,sft);
        input [12:0] c4_0,c4_1;
        input [12:0] sft_0,sft_1;
        input msbz; // MSB of Z ( Z = X mul Y )
        output [12:0] c4;
        output [12:0] sft;

更なる仮数の調整を、ポストシフト、丸めと並列に行う ( postadjexp )

上記までの時点で ( MSBofZ が 0 か 1 に確定すれば ) 仮数の方に関しては、何処の 53 ビットを丸めればよいのかが完全に決まるが、指数の方は、丸めた結果、桁上がりがあった場合の修正というものを考えなければならない。前述した通り、C4 から ( C4' を経て ) C5 へ調整する事を考えてみる。

なお、この部分は、53b × 53b の乗算は終了しており、MSBofZ が既知のものとなり、正しい C4 が選択されているものとする。
また、この部分は、C5 を計算するのに、丸めの結果桁上がりが起きたかどうかが重要な判断材料となるが、 preadjexp 同様に、桁上がりが起きた場合と桁上がりが起きなかったときの 2 通りの修正を行う。

C4 が浮動小数点数フォーマットの指数の範囲内のときに、丸めが起きて桁上がりが発生した場合、C4 + 1 がオーバーフローかどうかを調べて、もしそうならばオーバーフロー例外の準備を行う。そうでなければ、このステップはスルー。即ち、このステップの影響を受けるのは C4 = Emax の場合だけである。
C4 が浮動小数点数フォーマットの指数の最小値 Emin よりも小さいならば、桁上りが発生してもしも C4 + 1 が Emin になったとき、そのときは C4 をインクリメントして、例外も起こさないでスルー。これは即ち、C4 が 0 のときに限る。そして C4 がそれ以外の場合においてのみ、デノーマルとアンダーフロー例外の準備をする。
C4 が浮動小数点数フォーマットの指数の最大値 Emax よりも大きいならば、この部分はスルー。

指数の調整と丸めの関係 ( トラップは無いと仮定 )

C4	丸めの繰り上がり	C5	例外
-1 以下	( don't care )	0	アンダーフローか
0	無	0	アンダーフローか
0	有	1	無し
1 ～ Emax - 1	無	C4	無し
1 ～ Emax - 1	有	C4 + 1	無し
Emax	無	Emax ( C4 )	無し
Emax	有	※	オーバーフロー
Emax + 1 以上	( don't care )	※	オーバーフロー

0 とは Emin - 1 を指し、1 とは Emin を指している
不正確例外は、どの場合にも存在することに注意

アンダーフローか、と書いたのは、トラップの無いときアンダーフローのフラグが立つのは、同時に精度が損なわれたときのみなので、100 % 例外の状態になるとは言えないからである。

※ は、丸めモードと符号によって Emax か Emax + 1 かを取る。丸めモードと符号の組み合わせ次第で、オーバーフロー時の返す値が

∞
表現可能な有限数の内、絶対値が最大のもの

の、どちらかになる。
( 符号は、入力オペランド 2 つの数の符号の排他的論理和 ( xor ) になる )
ここで、OverFlow-Infinity ( OVI ) という信号を導入し、その値を参照することで、オーバーフロー時に結果として返す値がどちらなのかを決定する。

この ovi を計算するのは、postadjexp とは別のモジュールである resultinfty で行う。出力 ovi が 1 ならば、オーバーフロー時に∞を返す。 0 ならば表現できる最大値を返す。また、ついでに結果の符号 sc も出力する。

オーバーフロー時における、丸めモード、符号と返り値
( 非トラップ )

丸めモード	SA xor SB	OVI
RN ( 00 )	( don't care )	1
RZ ( 01 )	( don't care )	0
RP ( 10 )	0 1	1 0
RM( 11 )	0 1	0 1

SA , SB は、入力オペランドの符号

module resultinfty(rmode,sa,sb,sc,ovi);
        input [1:0] rmode; // roundmode
        input sa,sb;
        output sc;  // sign of result
        output ovi;

結局、モジュール postadjexp では、以下のような function を個々に作った。 OVI については、前述したモジュール resultinfty の出力を利用する。また、 CarryByRounding ( CBR ) とは、丸めによって桁上がりが発生した際に丸め回路が出力 ( アサート ) する信号である。そして preadjexp 同様に、CBR が 0 の場合と 1 の場合の両方を

調整した指数 C4
オーバーフローの処理を後でする必要があることを知らせる of
アンダーフローの処理を後でする必要があることを知らせる uf
オーバーフロー時の仮数の結果 zo
( オーバーフロー以外のときはこの値は使用しないため、don't care とする )

の 4 つについて各々計算するようにしている。
( 計 8 出力になる )

C4 、丸めと C5 、仮数の関係 ( 実装版 )

C4	CBR	OVI	C5	ZO
-1 以下	( don't care )	( don't care )	0	( don't care )
0 ～ Emax - 1	( don't care )	( don't care )	C4 + CBR	( don't care )
Emax	0	( don't care )	Emax ( C4 )	( don't care )
Emax	1	0 1	Emax Emax + 1	111...111 100...000
Emax + 1 以上	( don't care )	0 1	Emax Emax + 1	111...111 100...000

C4 、丸めとオーバーフローの関係 ( 実装版 )

C4	CBR	Overflow ( of )
Emax - 1 以下	( don't care )	0
Emax	0	0
Emax	1	1
Emax + 1 以上	(don't care)	1

C4 、丸めとアンダーフローの関係 ( 実装版 )

C4	CBR	Underflow ( uf )
-1 以下	( don't care )	1
0	0	1
0	1	0
1 以上	( don't care )	0

仮数をポストシフトする ( postsft )

ただのバレルシフタで、指数が小さすぎてデノーマルになってしまうことを想定して用意されている。それさえなければ、1 ビットシフタだけで事は足りるはずなのだが。
丸めを行う ( round + roundlogic )
```
module round(in,sib,rob,stb,rmode,out,cbr,iex);
        input [52:0] in;
        input sib,rob,stb; // sign bit , round bit , sticky bit
        input [1:0] rmode;
        output [52:0] out;
        output cbr; // CarryByRounding : carry of rounded result
```
丸め回路。入力は、MSB のみを整数部とする、固定小数点のフォーマットで渡される。
加減算ではいろいろ小細工を仕掛けているので利用できないが、おそらく除算なら適用できるし、もっとも、丸めを行うかどうかを判定するモジュール roundlogic は、加減算のものと同じものを利用している。
アルゴリズムに関しては、加減算の時と同様で、まず並列に結果 Z と結果 Z + 1 を計算しておき、丸めの結果に従いそれを選択するという戦法をとる。
ただ、一つだけ小細工をしている点は、繰り上がりで桁が 1 つあがるような丸めの入力は、 111...111 というように、全てのビットが 1 のときであるが、このとき、丸めで繰り上がったときは、そのまま結果を返せば、 000...00 となってしまうが、これは望ましい形ではないので、あふれがあった旨を知らせるビット cbr を立てるとともに、 100...000 という出力を返すことにしている。あふれたときに、MSB の or をとるだけなので、それほど複雑な回路にはなっていない。
ここまで考えた時点で一つ問題が起きた。デノーマルのときの桁上がりが検出できなかった。つまり、 011...111 を丸めたとき、100...000 になっても、あふれビット cbr が立たなかった。このときも cbr が立つように改造することは、さほど難しくはない。
モジュール round は、下位に roundlogic を持っている。 roundlogic に関しては、単純に丸めの判断となる真理値表に基づいて、 +1 を行うかどうかというビットを返すもので、合成の結果、12 primitives という小さな回路に落ちついている。
```
module roundlogic(sib,lsb,rob,stb,rmode,out,iex);
        input sib,lsb,rob,stb;
        input [1:0] rmode; // 00:RN , 01:RZ , 10:RP , 11:RM
        output out;
	output iex; // inexact result by rounding
```
結局、 roundlogic の出力 out を、RLO と書くと、以下のような真理値表ができる。

モジュール round 内部の真理値表

in RLO out CBR

( don't care ) 0 in 0

011...111
111...111
上記以外 1 100...000
100...000
in + 1 1
1
0

CBR : CarryByRounding
上表では、デノーマルから正規化数に上がるのも、正規化数の桁が一つあがるのも、どちらも全く同じ結果を返しているが、指数を調整する回路でどちらなのかはちゃんと把握しているはずなので、これでよいはず。そして出力 CBR を制御信号として、モジュール postadjexp で出力された
- c5_0 , of_0 , uf_0 , zo_0
- c5_1 , of_1 , uf_1 , zo_1
の 2 セットのうち、どちらかを選択する。
また、モジュール round は不正確の例外を発生するか否かという判断をする基準となるビットInexact ( iex ) も出力する。
Sun のマニュアルを真似して、オーバーフロー時には、必ず不正確の例外がでるようにしてある。確かに定義通りであるならば、正確な値と表現している値に差があるので、当然といえば当然だが。
別回路も含めて、全ての解の候補の中から、正しいものを選択する
以上の過程で、オーバーフロー、アンダーフローを考慮した正しい結果の候補が出力されている。
更に、NaN や ∞等の特殊数に関する出力を別回路で行い、ここでそれも一緒に出力することにする。
出力すべきものをまとめると
- トラップが発生したと仮定したとき、渡されるべき引数
- 立てるべき ( 又はおろすべき ) 非トラップ例外処理のステータスフラグ
- トラップ / 非トラップを判断するビット
  これは、入力をそのまま出力する。つまり、この命令で例外が起きたときに、トラップかどうかを判断するのは、命令投入時のステータスフラグであり、命令完了時のステータスフラグを見て、トラップを起こすかどうかは判断しない。

in	RLO	out	CBR
( don't care )	0	in	0
011...111 111...111 上記以外	1	100...000 100...000 in + 1	1 1 0

基本部分以外の各モジュールの組み合わせ回路としての合成結果は以下の通り。

モジュール名	cost prim.	時間 (ns)	必要数	小計 prim.
resultinfty	9	1.154	1	9
preencode	286	5.129	2	572
presft	960	4.020	2	1920
preadjexp	652	8.136	1	652
premux	87	1.334	1	87
postsft	1162	6.548	1	1162
postadjexp	215	2.993	1	215
postmux	417	2.331	1	417
round + roundlogic	643	6.369	1	643

no clock, opt area -high, opt timing -high にて合成
[ primitive cost × 必要数 ] で、
必要な primitive cost が計算できる。

設計にあたって冗長なところ

即ち、改善の余地があるかもしなれいところ

モジュール round にて丸めを実際に行った結果、53 ビットで返しているが、けち表現の際 MSB を落とすため、実際に MSB を返すことは不要と思われるが、デバッグが困難になると思われるので、あえて余分に計算をしている。 ( どこかで役に立つかもしれないし )
ポストシフトの際、106 ビットの入力の MSB が 1 なら、最低 1 ビットはシフトしなければならない。つまり、ポストシフトをしないならば、MSB が 0 ということと対応している( = かけ算による桁上がりがおきない )
但し、MSB が 0 ならば、必ずポストシフトをしないかというと、そうでもない。何故ならば、MSB に関わらず、デノーマルのために右シフトは何ビットでもとり得るからである。

基本部分のアルゴリズム ( その 1 : 大失敗 )
純粋に 53 bit × 53 bit 乗算器のアルゴリズムについて考える。
2 bit Booth 法を基礎にして、力技でいく。

2 bit Booth 法とは、A × B を計算するのに、B を 2 bit + 重複 1 bit = 3 bit 毎に分割して、部分積を形成する方法である。区切った 3 bit と、対応する部分積の値は以下の通りである。

code B	部分積
000	0
001	+A
010	+A
011	+2A
100	-2A
101	-A
110	-A
111	0

2 Booth は、実質は 2 bit 毎にエンコードしているため、筆算のやり方に比べて、部分積の数が半分になる上、部分積が単純な ±A,±2A のみになるという利点がある。
ここの部分はモジュール boothencode で実現する。あらかじめアンパックも忘れずに。(加減算器と違って、ごく普通にアンパックを行う。

module boothencode(in,code,out);
        input [52:0] in;
        input [2:0] code;
        output [54:0] out; // 2's complement expression

53 bit × 53 bit を 2 Booth でエンコードすると、エンコードの結果は、入力に対して 2 倍の値まで持つことになり、更に、2 の補数表現というのも考慮して、55 bit の部分積を生成する。そしてその生成される 55 bit の部分積の数は、図のように 27 個である。

       5         4         3         2         1         0
    -21098765432109876543210987654321098765432109876543210-
------------------------------------------------------------
00 |-|-|---------|---------|---------|---------|--------00o
01 | | |         |         |         |         |      111
02 | | |         |         |         |         |    222
03 | | |         |         |         |         |  333
04 | | |         |         |         |         |444
05 | | |         |         |         |        555
06 | | |         |         |         |      666
07 | | |         |         |         |    777
08 | | |         |         |         |  888
09 | | |         |         |         |999
10 |-|-|---------|---------|--------000
11 | | |         |         |      111
12 | | |         |         |    222
13 | | |         |         |  333
14 | | |         |         |444
15 | | |         |        555
16 | | |         |      666
17 | | |         |    777
18 | | |         |  888
19 | | |         |999
20 |-|-|--------000
21 | | |      111
22 | | |    222
23 | | |  333
24 | | |444
25 | |555
26 |o66

27 個に分割された 3 bit のうち、最初と最後の末端は、必ず 0 になっている。

この 27 個の部分積のうち、隣り合ったもの同士を加算器に投入する。和は、各々 55 + 2 = 57 bit である。それが 13 組と半端が 1 つ出る。下図は、投入するイメージで、あえて符号拡張の部分を書いていないが、絶対必要である。また、27 番目の MSB は、上図のエンコード表から、絶対マイナスにならない為、常に 0 となる。

                                                    0000000000000000000000000000000000000000000000000000000
                                                 +1111111111111111111111111111111111111111111111111111111
                                         
                                                2222222222222222222222222222222222222222222222222222222
                                             +3333333333333333333333333333333333333333333333333333333
                                         
                                            4444444444444444444444444444444444444444444444444444444
                                         +5555555555555555555555555555555555555555555555555555555
                               
                                        6666666666666666666666666666666666666666666666666666666
                                     +7777777777777777777777777777777777777777777777777777777
                               
                                    8888888888888888888888888888888888888888888888888888888
                                 +9999999999999999999999999999999999999999999999999999999
                         
                                0000000000000000000000000000000000000000000000000000000
                             +1111111111111111111111111111111111111111111111111111111
                               
                            2222222222222222222222222222222222222222222222222222222
                         +3333333333333333333333333333333333333333333333333333333
                         
                        4444444444444444444444444444444444444444444444444444444
                     +5555555555555555555555555555555555555555555555555555555

                    6666666666666666666666666666666666666666666666666666666
                 +7777777777777777777777777777777777777777777777777777777

                8888888888888888888888888888888888888888888888888888888
             +9999999999999999999999999999999999999999999999999999999

            0000000000000000000000000000000000000000000000000000000
         +1111111111111111111111111111111111111111111111111111111

        2222222222222222222222222222222222222222222222222222222
     +3333333333333333333333333333333333333333333333333333333

    4444444444444444444444444444444444444444444444444444444
 +5555555555555555555555555555555555555555555555555555555
 
O666666666666666666666666666666666666666666666666666666

上記のモジュールを、partial55 とする。

module partial55(ina,inb,out);
    input [54:0] ina,inb;
    output [56:0] out;
    assign out = { {ina[54],ina[54],ina[54:2]}+inb , ina[1:0] };

そして、また隣接する 57 bit を加算器に投入する。今度は、61 bit の和が 7 組できる。
一つ前のプロセスで出た半端な 1 個の対処としては、2 bit 符号拡張をして他の加算器と同じモジュールを使用するか、「54 bit の加算器 & 4 bit スルー」という特殊なモジュールを組み直すかのどちらかが考えられる。しかしここだけ速くしても、あまり意味がない。強いて言えば、ハードウェアの量が多少減るくらいなものである。まずは支障がなければ、0 を詰めて、特殊なモジュールは使用しないことにする。

   
                                                     000000000000000000000000000000000000000000000000000000000
                                                +111111111111111111111111111111111111111111111111111111111
                                            
                                             222222222222222222222222222222222222222222222222222222222
                                        +333333333333333333333333333333333333333333333333333333333
                                  
                                     444444444444444444444444444444444444444444444444444444444
                                +555555555555555555555555555555555555555555555555555555555
                                  
                             666666666666666666666666666666666666666666666666666666666
                        +777777777777777777777777777777777777777777777777777777777
                        
                     888888888888888888888888888888888888888888888888888888888
                +999999999999999999999999999999999999999999999999999999999
          
             000000000000000000000000000000000000000000000000000000000
        +111111111111111111111111111111111111111111111111111111111
      
     222222222222222222222222222222222222222222222222222222222
+ooO333333333333333333333333333333333333333333333333333333

これを実現するのは、モジュール partial57 である。

module partial57(ina,inb,out);
    input [56:0] ina,inb;
    output [60:0] out;

    assign out = { {ina[56],ina[56],ina[56],ina[56],ina[56:4]}+inb , ina[3:0] };

同様に、隣接する 61 bit の対を加算器に投入。69 bit の和が 3 組と、余りが 1 つできる。

                                                 0000000000000000000000000000000000000000000000000000000000000
                                        +1111111111111111111111111111111111111111111111111111111111111

                                 2222222222222222222222222222222222222222222222222222222222222
                        +3333333333333333333333333333333333333333333333333333333333333

                 4444444444444444444444444444444444444444444444444444444444444
        +5555555555555555555555555555555555555555555555555555555555555

 ooO6666666666666666666666666666666666666666666666666666666666

モジュール partial61 で実現する。

module partial61(ina,inb,out);
    input [60:0] ina,inb;
    output [68:0] out;

    assign out = { {ina[60],ina[60],ina[60],ina[60],ina[60],ina[60],ina[60],ina[60],
                    ina[60:8]}+inb , ina[7:0] };

69 bit の対を加算器に投入。85 bit の和が 2 つできる。特殊モジュールでは、「 58 bit の加算器 + 16 bit スルー」となる。

                                                 000000000000000000000000000000000000000000000000000000000000000000000
                                 111111111111111111111111111111111111111111111111111111111111111111111

                 222222222222222222222222222222222222222222222222222222222222222222222
+OOOOOOOOooO3333333333333333333333333333333333333333333333333333333333

モジュール partial69 にて。

module partial69(ina,inb,out);
    input [68:0] ina,inb;
    output [84:0] out;

    assign out = { {ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],
                    ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],ina[68],
                    ina[68:16]}+inb ,ina[15:0] };

最後に足して終了。モジュールは唯一なので特殊も何もなく、「 74 bit の加算器 + 32 bit スルー」となる。これで、 53 bit × 53 bit = 106 bit の積を得ることができる。

                                 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+OOOOOOOOooO11111111111111111111111111111111111111111111111111111111111111111111111111
----------------------------------------------------------------------------------------------------------------------
            1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

            0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
            0         1         2         3         4         5         6         7         8         9         0

入出力が変則的なモジュールは partial74 とする。

module partial74(ina,inb,out);
    input [84:0] ina;
    input [73:0] inb

    output [105:0] out;

    assign out = { {ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],
                    ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],ina[84],
                    ina[84:32]}+inb , ina[31:0] };

以上のモジュールの組み合わせ回路としての速さは、東芝のライブラリを使用した Mentor にかけると

モジュール名	prim. cost	時間 (ns)	必要数
boothencode	1176	6.805	27
partial55	658	8.530	13
partial57	683	8.754	7
partial61	730	9.251	3
partial69	822	10.245	2
partial74	879	10.968	1

no clock, opt area -high, opt timing -high にて合成
[ primitive cost × 必要数 ] で、
必要な primitive cost が計算できる。
となり、50 MHz なら、4 ～ 5 サイクルでこの部分は対処できることがわかる。
ハードウェアの量としてはどうなのだろう。使いすぎなのだろうか。

特殊数に関する具体的な動作

X op Y	Y = 0	Y = W	Y = ∞	Y = NaN
X = 0			(ii)	(i)
X = W			(ii)	(i)
X = ∞	(ii)	(ii)	(ii)	(i)
X = NaN	(i)	(i)	(i)	(i)

(i) -> (ii) の順で評価を行うとうまくいきそう。

(i) NaN を 1 つでも含む場合

X = NaN ?	Y = NaN ?	結果
0	0	d (担当外)
0	1	Y
1	0	X
1	1	X

IsTruePath : (X==NaN) | (Y==NaN)
出力の NaN は入力をそのままスルーさせていいのか？それをやると、 Signaling はいつまでたっても Quiet に変化しないのだが

(ii) ∞を含む場合

X	Y	Z
∞	∞	∞
∞	W	∞
W	∞	∞
∞	0	Signaling ( ? ) NaN
0	∞	Signaling ( ? ) NaN

IsTruePath : ( X==∞ ) | ( Y==∞ )

一歩前へ
僕のホームへ[Home]
研究室のページへ[Amano Lab.]

Takahiro Kawaguchi kawaguti@aa.cs.keio.ac.jp
Last modified: Dec. 26 , 1997