乗算器 その2

この記事はkivantium Advent Calendarの8日目です。

昨日は符号なし整数掛け算の実現方法として単純な2つの回路を考えてそれらが実用的でないことを確認し、また、符号付き整数の掛け算を行う方法としてBaugh-Wooleyアルゴリズムを紹介しました。
今日は乗算器を高速化する方法を考えていきます。

Wallaceツリーを用いた高速化

Wallace（ワラス/ウォレス）ツリーは昨日の「単純な符号なし乗算器 その1」に対応する回路を高速にする方法です。加算器をたくさん使う方法はハードウェアを大量に消費する上に遅いという問題がありました。Wallaceツリーは加算器に入れる前に処理を行うことでハードウェアの使用量を減らした上で速度を改善する手法で、多くの乗算器に採用されています。

まずは4bit符号なし整数の掛け算を考えます。この筆算は

と書けます。
これを式通り計算すると4つの数字を足すことになりますが、Wallaceツリーを使って2つの数の足し算まで圧縮していきます。

文字を書くと大変なのでアダー配列図と呼ばれる図を書いて表すことにします。

一つの□がなどの値に対応します。

これをまず、各bitにいくつ四角があるか分かりやすくするために全ての項を上に寄せます。

これを以下のルールに従って潰していき、段数を減らします。

• 同じbitに3つ以上四角があるなら、フルアダーを使って加算する。→加算した3つの四角を消してFAのSに対応する四角をそのbitに、Cに対応する四角を一つ上のbitに追加する。
• 四角が2つ以上あるbitのうち最下位のbitに四角が2つあればハーフアダーを使って加算する。→加算した2つの四角を消してHAのSに対応する四角をそのbitに、Cに対応する四角を一つ上のbitに追加する。
• ただし、全てのbitの四角が3つ以下になったら最下位でなくても四角が2つあるbitにハーフアダーを適用する
• 全てのbitの四角が2つ以下になったら終了する

実際にこのルールを適用して潰していきます。

フルアダーを用いる項を赤、ハーフアダーを用いる項を青でかこみました。これを実行すると次のようになります。

演算によって新しくできた項には別の番号を振っています。
次のステップは

のようになり、左側の4項を加算器（キャリールックアヘッドやKogge-stoneなど高速なもの）で足した結果を出力すれば積になります。

このようにWallaceツリーを使うことで数段のフルアダーの遅延+全体のアダーの遅延で計算することができハードウェアも時間も節約することができます。

いま説明した4bitの符号なし整数の乗算器をVerilogで書いてみます。

module testbench;
  logic [3:0] a, b;
  logic [7:0] result, answer;
  int i, j;

  unsigned_mult_4bit mul(.a(a), .b(b), .p(result));
  assign answer = a*b;

  initial begin
    $monitor("%b x %b -> %b (%d x %d = %d)", a, b, result, a, b, result);
    for (i = 0; i<=15; i++) begin
      for (j = 0; j<=15; j++) begin
        a = i; b = j; #1;
        if(result != answer) $display("wrong answer!");
      end
    end
    $finish;      
  end
endmodule

module HA(
  input A, B,
  output S, C
);
  assign S = A ^ B;
  assign C = A & B;
endmodule

module FA(
  input A, B, Cin,
  output S, Cout
);
  assign S = (A ^ B) ^ Cin;
  assign Cout = ((A ^ B) & Cin) | (A & B);
endmodule

module cla_adder_4bit (
  input [3:0] A, B,
  output [4:0] S,
  output C
);
  logic [4:0] c;
  logic [3:0] p, g;
  
  genvar i;
  generate
    for(i=0; i<4; i=i+1) begin
      assign p[i] = A[i] | B[i];
      assign g[i] = A[i] & B[i];
      assign c[i+1] = g[i] | (p[i] & c[i]);
      assign S[i] = A[i] ^ B[i] ^ c[i];
    end
  endgenerate
  assign c[0] = 1'b0;
  assign S[4] = c[4];
endmodule

module unsigned_mult_4bit(
  input [3:0] a, b,
  output [7:0] p
);
  logic [31:0] t;
  logic [3:0] x, y;

  genvar i, j;
  generate
    for(i=0; i<4; i=i+1) begin
      for(j=0; j<4; j=j+1) begin
        assign t[i*4+j] = a[j] & b[i];
      end
    end
  endgenerate

  HA ha0(.A(t[1]), .B(t[4]), .S(t[16]), .C(t[17]));
  FA fa1(.A(t[2]), .B(t[5]), .Cin(t[8]), .S(t[18]), .Cout(t[19]));
  FA fa2(.A(t[3]), .B(t[6]), .Cin(t[9]), .S(t[20]), .Cout(t[21]));
  FA fa3(.A(t[7]), .B(t[10]), .Cin(t[13]), .S(t[22]), .Cout(t[23]));
  HA ha1(.A(t[18]), .B(t[17]), .S(t[24]), .C(t[25]));
  FA fa4(.A(t[20]), .B(t[12]), .Cin(t[19]), .S(t[26]), .Cout(t[27]));
  HA ha2(.A(t[22]), .B(t[21]), .S(t[28]), .C(t[29]));
  FA fa5(.A(t[11]), .B(t[14]), .Cin(t[23]), .S(t[30]), .Cout(t[31]));
  
  assign p[0] = t[0];
  assign p[1] = t[16];
  assign p[2] = t[24];

  assign x = {t[15], t[30], t[28], t[26]};
  assign y = {t[31], t[29], t[27], t[25]};
  cla_adder_4bit cla(.A(x), .B(y), .S(p[7:3]));
endmodule

結果は、

(略)
1111 x 1100 -> 10110100 (15 x 12 = 180)
1111 x 1101 -> 11000011 (15 x 13 = 195)
1111 x 1110 -> 11010010 (15 x 14 = 210)
1111 x 1111 -> 11100001 (15 x 15 = 225)

のようになって確かにこの回路が掛け算になることが分かります。

符号付きの場合やよりbit数が多い場合も同様に書けますが、今日中に書くのはつらいので今日はやりません。

明日は足し算を繰り返して掛け算を行う方法の高速化について書きます。

参考文献

ディジタル数値演算回路の実用設計―四則演算、初等超越関数、浮動小数点演算の作りかた (Design Wave Advanceシリーズ)