乗算器の原理 ─ Boothエンコーディングとワレスツリー

乗算が重いのに速い理由

筆算の掛け算を思い出すと、乗数の各桁ごとに被乗数をずらしながら並べ、最後に全部を足し合わせます。nビット同士の乗算なら、この「部分積」がn本でき、それらをすべて加算すれば積が出ます。素直に実装すると部分積n本を順番に足すため、遅くて面積も食います。

ハードウェア乗算器は、この素朴な手順を2つの軸で削ります。第一に部分積の本数そのものを減らすこと（Boothエンコーディング）。第二に、残った部分積を段数の少ない木構造で一気に足すこと（ワレス／Daddaツリーによる桁上げ保存加算）です。この2段構えのおかげで、乗算は加算より本質的に重い演算でありながら、数段ぶんの論理遅延で結果を出せます。SIMDのベクトル演算やテンソルコアの行列積が積和を大量に流せるのも、各レーンにこの構成の乗算器が並んでいるからです。

基数4 Boothで部分積を半減する

Boothエンコーディングは、乗数を1ビットずつではなく複数ビットまとめて符号付きに読み替えることで部分積の本数を減らす技法です。実装で標準的なのは基数4（radix-4、Booth-2とも呼ぶ）です。

基数4 Boothは乗数を下位から2ビットずつ区切りますが、隣の区画と1ビット重ねた3ビットの窓で読みます。窓の値（最下位には初期値0を補う）に応じて、その区画が被乗数Mに対して何倍の部分積を出すかを次の表で決めます。

倍率が 0, ±1, ±2 の5通りしかないのが要点です。±1 は被乗数そのもの、±2 は1ビット左シフトで作れ、負側は2の補数（ビット反転＋1）で得ます。つまり乗数の値に依らず、シフトと反転だけで部分積を生成でき、面倒な3倍などは現れません。

窓を2ビットずつずらして走査するので、nビットの乗数からできる部分積はおよそ n/2 + 1 本です。8ビットなら8本が5本に、64ビットなら64本が33本になります。部分積が半分になると、次に説明する加算ツリーの段数も入力本数の対数で効くため、遅延と面積の双方に効きます。

桁上げ保存加算（CSA）── 桁上げを伝搬させない

部分積を半減しても、まだ複数本を足す必要があります。ここで普通の加算器（桁上げを下位から上位へ伝えるキャリー伝搬加算器、CPA）を使うと、1回の加算ごとに桁上げがビット幅ぶん伝搬し、本数×幅ぶんの遅延が積み上がります。

そこで乗算器は**桁上げ保存加算（Carry-Save Adder、CSA）**を使います。CSAの肝は、桁上げをその場で上位桁に足し込まず、別のベクトルとして保持して次段へ送ることです。各桁を独立した全加算器で処理するので、桁上げ伝搬が起きず、入力本数に依らず1段の遅延は全加算器1個ぶんで一定です。

3:2コンプレッサ（全加算器を桁ごとに並べたもの）
  入力: 同じ重みの3ビット a, b, c
  出力: 和ビット s = a XOR b XOR c          （同じ桁に残る）
        桁上げ c_out = majority(a,b,c)       （1つ上の桁へ送る）
  → 3本の入力ベクトルを「和ベクトル＋桁上げベクトル」の2本に圧縮

3本を2本に圧縮するので 3:2コンプレッサ と呼びます。重要なのは、桁上げ c_out を即座に隣へ伝搬させず、次段の入力として水平に渡す点です。これにより、何本の部分積があっても各CSA段の遅延は一定になり、段を重ねるほど本数が 3→2、2本ずつ減っていきます。

ワレスツリーとDaddaツリー ── 圧縮の組み方

CSAをどう積み上げるかで、ワレス（Wallace）とDadda（ダダ）の2流派があります。どちらも部分積を「最終的に2本（和ベクトルと桁上げベクトル）になるまで」段階的に圧縮する木ですが、方針が違います。

ワレスツリーは「各桁にある部分積ビットを、その都度3本ずつまとめて3:2圧縮する」のを段ごとに繰り返します。早めに貪欲に圧縮するため全加算器の数はやや増えますが、考え方が単純です。Daddaツリーは逆に、「最終的に許される段数（高さ）」を先に決め、その高さに収まる範囲で必要なぶんだけ圧縮します。無駄な圧縮を省くので全加算器が減り、面積で有利になることが多い一方、最後のキャリー伝搬加算器がやや広くなります。

肝心の遅延は両者とも、部分積の本数Nを2本へ落とすのに必要な段数が log オーダになる点で共通です。3:2圧縮は1段で本数を約 2/3 倍にするので、N本から2本までは概ね 1.5 を底とする対数段で到達します。Boothで本数を半減してあると、この段数がさらに1段ぶん前後縮みます。素朴な直列加算の N 段に対し、ツリーは log N 段なので、本数が増えるほど差が開きます。

最後はキャリー伝搬加算で確定する

ツリーが本数を2本まで圧縮すると、残るのは和ベクトルと桁上げベクトルの2本です。この2本はまだ「桁上げを伝搬させていない」中間表現なので、最後に一度だけ本物の加算をして桁上げを上位まで伝搬させ、真の積を確定します。

ここで初めて**キャリー伝搬加算器（CPA）**を使います。乗算器全体の臨界経路は次のように分解できます。

乗算遅延 ≒ Boothエンコード/部分積生成
        + CSAツリーの圧縮段（log オーダの段数）
        + 最終CPA1台の桁上げ伝搬

最終CPAは全体遅延の一角を占めるため、ここには**桁上げ先見加算器（CLA）やプレフィックス加算器（Kogge-Stone等）**といった、桁上げ伝搬を log 段で済ませる高速加算器を使います。リップルキャリー（順送り）では幅ぶんの遅延が乗ってしまい、せっかくツリーで稼いだ速さが台無しになるからです。整数のパイプライン処理に乗せる乗算ユニットでは、この3区間をステージ分割し、スループットを1サイクルあたり1乗算に保ちます。アウトオブオーダ実行のコアでは、乗算は複数サイクルのレイテンシを持つ実行ユニットとしてスケジューラに扱われます。

まとめ

• ハードウェア乗算は「部分積を減らす」と「少ない段数で足す」の2軸で速くする。
• 基数4 Boothエンコーディングは乗数を3ビット重なり窓で読み、倍率 0, ±1, ±2 をシフトと反転だけで生成して、部分積を約 n/2 + 1 本へ半減する。
• **桁上げ保存加算（CSA）**は桁上げを伝搬させず別ベクトルで次段へ送るため、3:2・4:2コンプレッサで本数を段ごとに圧縮でき、加算段数を本数の対数オーダに抑える。ワレスは貪欲圧縮、Daddaは段数逆算の最小圧縮。
• 圧縮しきった和ベクトルと桁上げベクトルの2本を、最後に高速なキャリー伝搬加算器1台で足して積を確定する。乗算遅延はBooth＋log段のCSA＋最終加算で決まる。