素朴な全加算器
皆さん，加算器は好きですか？私は好きでも嫌いでもないです．
加算器と言えば，IPA試験のFEやAPの対策本でおなじみ(そして試験では出ない)ですし，大学の論理回路設計の授業なんかでVerilogで書いてFPGAに実装したことある方も多いでしょう．
ところで，そのとき実装したVerilogコードはどのようになっていましたか？
恐らく以下のようなものだったのではないでしょうか．
module fa(input wire a, input wire b, input wire cin, output wire s, output wire cout);
assign s=a^b^cin;
assign cout=(a&b)|(b&cin)|(a&cin);
endmodule
module adder #(parameter bits=64)
(
input wire [bits-1:0] a,
input wire [bits-1:0] b,
input wire cin,
output wire [bits-1:0] sum,
output wire cout
);
wire [bits:0] carry;
assign carry[0]=cin;
assign cout=carry[bits];
genvar i;
generate
for(i=0;i<bits;i=i+1) begin: linear_length_critical_path
fa u_fa(
.a(a[i]),
.b(b[i]),
.cin(carry[i]),
.s(sum[i]),
.cout(carry[i+1])
);
end
endgenerate
endmodule
これは加算器の定義より明らかな加算器の構成です．
恐らく大学の授業ではgenerateを使わず，固定長の例えば 8 bitとか 16 bitの加算器を大量のコピペで作らされたとは思いますが，やってることは基本的に同じです．
1 bit全加算器は以下の真理値表に基づいて入出力し，それが上記のコードのfaに当たります．
| 入力a | 入力b | 入力c | 出力s | 出力c |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
入力と出力のcが繰り上がりのための配線になり，これで 1 bitの足し算ができるわけですが，この 8 パターンをすべてcaseで場合分けするのは非常に大変なので，もっと簡単に書けるようにちょうどいいまとまりの部分を探します．
それを以下のカルノー図で行います．
| 表2. sのカルノー図 | 表3. c(出力)のカルノー図 |
|
|
表は01->11->10になっていますが，これで正しいです．グレイコードと言って，ハミング距離が1なので隣り合うマスが1つ以外すべて同じ入力のままになります．
真理値表では 1 bitずつ違う隣り合う項のまとまりを考えることで積和標準形1の形で取り出すことのできる補助ツールみたいなものです．
sは真理値表で頑張ってもいい感じにならないので，実はこれに意味はないです．
$s=a\oplus b\oplus c$は半加算器のときにXOR使ってたのを思い出す感じで，2進加算の性質みたいなもんだと思っておけばいいんじゃないですか．知らんけど
表3では，1になっている部分を2冪長さの箱で囲みましょう．
そうすると，{a,b,c}をこの順で解釈したとき*11, 11*, 1*1の3つの部分が囲えます．*は01どっちでもいい場所のことです．つまりこれはどれか2つ以上が1のとき，繰り上がりがあるということです．
あたりまえですね．
なので，この当たり前を実装すると，faになります．
そしてfaをビット長$N$と同じだけ繋げれば$N\ \mathrm{bit}$全加算器の完成です．
回路計算量
ところで，上記の方法で加算器を実装するとクリティカルパスが長くなってしまいます．
クリティカルパスとは，その回路を実行するときに，繋がっている入力と出力の一番遠い場所だと考えればいいです．
ある入力からある出力にデータが伝わるまでの距離が長くなると実行時間が長くなるので，これはちょっと問題です．光の速度は有限で，回路が入力信号に対応する出力で安定するための時間もあって，光の速度より遅い速度でデータは伝わるので，クリティカルパスが長くなると正しい出力を保証するためにクロックを下げざるを得なくなります．
アルゴリズムの良し悪しを判断するのに，だいたいの計算量をオーダーで測る方法があります．必ずしもオーダーが小さいからと言って速いわけではないですが，大規模な計算に対しては有効な考え方です．
この考え方は回路にもあって，回路計算量というものがあります．
ACやTC，NCなどがありますがそれらには深く立ち入らず，これらに基づくと加算回路は$\mathrm{NC}^1$に属します．これは，有限ファンイン($\mathrm{NC}^1$では4以下)で対数深さの回路ということです．有限ファンインというのは，ANDやORのゲートが定数個の入力しかとらないということで，対数深さというのはその名の通り回路の規模に対して深さ(クリティカルパス)が対数的にしか増加しないもののことです．回路の完全性は{AND,OR,NOT}か{AND,XOR}, {NAND}, {NOR}のいずれかのプリミティブなゲートを用いれば実現できるので，どのゲートを想定しても大丈夫です．加算回路は教科書的に普通の2入力1出力のゲートだけで実現できます．出力側に複数繋ぎますが，これはゲートの出力が複数必要なわけではなく配線を繋ぐだけでいいので1出力と考えても複数出力と考えても大きな差はないです．実際に回路を実装するときには配線の複雑度に直結するので無視できる要素ではないですが．
多くの入門的な本では加算回路の対数的な構築には触れません．少なくとも私が見たことある本では．
FE/APを取ったり，学部の論理回路設計の授業ならそれでいいのでしょうが，それでは面白くないので以下ではVerilogの実装も交えながら，加算器の対数深さ回路について解説してみます．
あらかじめご了承いただくこととして，私は情報系学部3年のまだまだ半人前の学生なので，勉強不足で間違ったことを書いている可能性があります．間違いを見つけた場合はできれば優しく教えてください．マサカリ投げないで
対数深さの加算回路 Kogge-Stone adder
対数的な深さにするための工夫として，ある2つの状態を導入しましょう．
あらかじめ競プロer向けにネタバレしておくと，これはいい感じのモノイドを導入してsparse tableを作ることをやっています．
以下では $a,b$を入力とし，$a_i, b_i$は$a,b$の $i\ \mathrm{bit}$目とします．
$$
g_i=a_i\cdot b_i
$$$$
p_i=a_i\oplus b_i
$$ここで$\oplus$はXORとします．またこの記事では$+$をOR，$\cdot$をANDとして扱います．
$g$はそのビットが繰り上がりを発生(generate)させるかどうかのフラグで，$p$はそのビットに繰り上がりが来たらそれを通過(pass through)させるかどうかのフラグです．
このとき，ある連続する部分について，その部分の$g,p$がわかっているとき，それを繋げた部分の$g,p$がわかります．
つまり，繰り上がりが発生することと，繰り上がりが伝播することが部分的にわかれば，それを繋げたときの繰り上がりの発生と伝播がわかります．
それは以下のように計算します．このとき$i>k>j$とします．
$$
g_{i:j}=g_{i,k}+(p_{i:k}\cdot g_{k:j})
$$$$
p_{i:j}=p_{i:k}\cdot p_{k:j}
$$
まずわかりやすいのは繰り上がりを伝播させる$p$で，これは前も後ろも伝播させるならその部分全体も伝播させるという形になっています．
そして，繋げた部分が繰り上がりを発生させるかという$g$は，上側が繰り上がりを発生させるか，下側が発生させて上側が通過させるかのどちらかなら発生するとみなしてよいということになっています．
言うまでもなく，あたりまえの話です．
これの実装は以下のようになります．
module pg_logic (
input wire g_in_upper, p_in_upper,
input wire g_in_lower, p_in_lower,
output wire g_out, p_out
);
assign g_out = g_in_upper | (p_in_upper & g_in_lower);
assign p_out = p_in_upper & p_in_lower;
endmodule
ここで，最初の$g,p$の定義で発生するであろう疑問の回収をします．
$p_i=a_i+b_i$ではないのかという疑問です．もちろん，繰り上がりを伝播させるという条件であればこちらの方が正しそうな気がします．実際にはどちらでもよいですが，これは$g_{i:j}$の定義が上側で発生する繰り上がりの情報を持っているからです．
ここで，わざわざ少し定義と違いそうな$p$を使うのには訳が無いわけではないです．
後で入力の加算をするわけですが，そのとき用いる情報は$a\oplus b$と各ビットの繰り上がり情報で，pを再利用できるようになります．
(余談)本当にモノイドか
一応，$((g,p),\mathrm{pg}\textrm{_}\mathrm{logic})$がモノイドになっていることを確認しましょう．
$g,p\in \lbrace 0,1\rbrace$で演算の結果ももちろん$\lbrace 0,1\rbrace$なので，演算は閉じています．
次に単位元の確認をしましょう．
この演算は自明に非可換なので，左右を入れ替えたときの確認も必要です．
プログラムを書いて全探索すると単位元$(g_e,p_e)=(0,1)$が見つかります．
$$
(g,p)\odot(0,1)=(g+p\cdot 0,\ p\cdot 1)=(g,p)
$$$$
(0,1)\odot(g,p)=(0+1\cdot g,\ 1\cdot p)=(g,p)
$$存在してよかったですね．
$\mathrm{pg}\textrm{_}\mathrm{logic}$を一旦$\odot$で表します．
このとき，結合律が成り立つとは，$A,B,C\in (g,p)$について$(A\odot B)\odot C=A\odot(B\odot C)$が成り立つことです．
\begin{align}
(A\odot B)\odot C&=(A_g+A_p\cdot B_g,\ \ A_p\cdot B_p)\odot C\\
&=(A_g+A_p\cdot B_g+ A_p\cdot B_p\cdot C_g,\ \ A_p\cdot B_p \cdot C_p)
\end{align}
\begin{align}
A\odot(B\odot C)&=A\odot (B_g+B_p\cdot C_g,\ \ B_p\cdot C_p)\\
&=(A_g+A_p\cdot(B_g+(B_p\cdot C_g)),\ \ A_p\cdot B_p \cdot C_p)\\
&=(A_g+A_p\cdot B_g+ A_p\cdot B_p\cdot C_g,\ \ A_p\cdot B_p \cdot C_p)\\
&=(A\odot B)\odot C
\end{align}
どうやら結合律も成り立つようです．
本当に都合がいいですね．
このように区間について簡単に扱うことができるということは，もちろんsparse tableのようなことが簡単にできるということです．
非競プロerに向けに簡単に説明するとsparse tableは静的なデータ構造で，長さに対して定数時間で区間に対するモノイド積を計算できます．
ただし，演算は冪等性があるもの(最大値や最小値など)しか使えず，加算やXORなどの冪等で無い演算は使えません．
簡単な例では，配列の任意の区間のbitwise-ORや最大値などを複数回求めるときに使えます．
構築方法は，配列の任意の地点から2冪長の区間でモノイド積を前計算します．
区間積を求めるときに，それを被覆する最小数の区間を選んでその部分区間のモノイド積を計算することで$O(1)$の区間積が得られます．
このとき区間の重なりを許容するため定数時間になる反面，冪等な演算しか行えません．
区間の重複を排除し，対数時間に区間積を求められるデータ構造でセグ木がありますが，こちらは後から更新もできるので便利度は上です．
今回，加算器ではpg_logicをモノイドを利用しますが，これの冪等性は問題になりません．
なぜなら，構築時に互いに背反な区間を用い，結果は区間の一部ではなく全体を使うためです．
また仮に部分積を求めたとしてもこの演算は多分冪等なので多分大丈夫です．知らんけど
言葉で説明するより，プログラムを見たほうがわかりやすいと思います．
これはsparse tableの構築みたいだなと私が早合点したので，説明をサボりたいというのもある．
こういうのAIにポン出しさせたり，ggったりしても特定のビット数の段数ごとにベタ打ちの実装ばかりで死ぬほど見づらいので全部書きました．
module kogge_stone_adder
#(
parameter bits = 64 // bit数．2冪じゃないと壊れる
)
(
input wire [bits-1:0] A, // 入力A
input wire [bits-1:0] B, // 入力B
input wire Cin, // 繰り上がりin
output wire [bits-1:0] Sum, // 出力
output wire Cout //繰り上がりout
);
localparam integer bitidx = $clog2(bits);
wire [bits-1:0] g [0:bitidx]; // g(対数+1深さ)
wire [bits-1:0] p [0:bitidx]; // p(対数+1深さ)
genvar i;
generate // 最初のg,pを計算
for (i = 0; i < bits; i = i + 1) begin : pre_process
assign g[0][i] = A[i] & B[i];
assign p[0][i] = A[i] ^ B[i];
end
endgenerate
genvar s;
generate // 各深さで長さ2^sの区間のpg_logicを計算
for(s=1;s<=bitidx;s=s+1) begin : log_stage
localparam integer stride = 1<<(s-1);
for(i=0;i<bits;i=i+1) begin : each_stage
if(i>=stride) begin // 自分より手前から2^sの長さの区間についての積
pg_logic u_pg_logic(
.g_in_upper(g[s-1][i]),
.p_in_upper(p[s-1][i]),
.g_in_lower(g[s-1][i-stride]),
.p_in_lower(p[s-1][i-stride]),
.g_out(g[s][i]),
.p_out(p[s][i])
);
end else begin // 2^s未満なら前の結果(先頭まで)を引き継ぎ
assign g[s][i]=g[s-1][i];
assign p[s][i]=p[s-1][i];
end
end
end
endgenerate
wire [bits:0] carry_in; // 各ビットの繰り上がり
assign carry_in[0] = Cin;
assign Cout = carry_in[bits]; // 最後の繰上りも以下と同じ方法で計算できる
generate // 各bitに繰上りがあるかは先頭から一つ前までに繰上りがあるか通過させるか
for (i = 1; i <= bits; i = i + 1) begin : final_carry
assign carry_in[i] = g[bitidx][i-1] | (p[bitidx][i-1] & Cin);
end
endgenerate
assign Sum = p[0] ^ carry_in[bits-1:0]; // p[0]はA^Bでcarry_inは各ビットの繰上り
endmodule
コメントがすべてという感じがしますが，一応混乱しそうなポイントとしては，$g,p$は2次元配列で1個目の引数が大きいほど長い2冪の長さをカバーしています．またg[i][j]は自分を含めて自分以前の$2^i$長さのモノイド積を持っています．
さて，この回路が本当にKogge-Stone adderになっているか確認しましょう．
Kogge-Stone adderの特徴はゲート数が$O(N\log_2 N)$，配線などを考慮した物理的な面積が$O(N^2)$です．
そしてverilogプログラムの実装では，ゲート数は，g，pのそれぞれの深さのモノイドの計算に使われg，pはそれぞれ$O(N\log_2N)$，面積は，最終段が$N/2$要素で長さ$N/2$の配線があり$O(N^2)$となります．
深さも対数オーダーですし，ちゃんとKogge-Stone adderになっていると言ってよさそうです．
対数深さの加算回路2 Brent-Kung adder
対数深さの加算回路は別に1つしかないというわけではありません．
Kogge-Stone adderはクリティカルパスが短く高速であるという反面，実装面積が大きいという欠点がありました．
これに対し，クリティカルパスを多少伸ばしながら実装面積を小さくする実装がBrent-Kung adderです．
競プロer向けにネタバレすると，これはほぼセグ木です．構築がボトムアップで，各ビットの繰上りを求めるのにトップダウンで見るだけです．
勘のいい読者の皆さんなら先ほどのプログラムを見て気付いたはずです．
「これは全地点で$p,g$を求めなくても，2冪でまとめればいいのでは？」と．
その通りです．2冪でまとめてしまえば各地点の$p,g$を求めるために対数的な数のノードを見る必要がある反面，ノード数は減らすことができます．
ここに一種の時間計算量と空間計算量のトレードオフが発生していますが，このときノード数は$O(N\log_2 N)$から$O(N)$に減少するのに対して，クリティカルパスの長さは$\log_2 N$から$2\log_2 N$程度にしかならず，$O(\log_2 N)$のままです．
私は「C++で間に合えばいいんだよ」派なので，セグ木上の二分探索を普通に二分探索して$O(\log^2 N)$にしますが，そんな感じで大して時間計算量が増えることを気にしないなら，この設計変更はコスパがよく有効です．
以下のコードは実はBrent-Kung adderではなく，それよりも緩い普通のParallel Prefix Sum Treeで実装しています．本物のBrent-Kung adderはもっとシビアに小さくしているらしいです．
module brent_kung_adder
#(
parameter bits = 64 // 2冪じゃないと壊れる
)
(
input wire [bits-1:0] A,
input wire [bits-1:0] B,
input wire Cin,
output wire [bits-1:0] Sum,
output wire Cout
);
localparam integer bitidx = $clog2(bits);
// 1-indexed セグ木
wire [2*bits-1:1] g;
wire [2*bits-1:1] p;
genvar i;
generate // セグ木の葉には1-indexedのとき要素数加算した場所を使う
for(i=0; i<bits; i=i+1) begin : leaves
assign g[bits+i] = A[i] & B[i];
assign p[bits+i] = A[i] ^ B[i];
end
endgenerate
generate
for(i=bits-1;i>=1;i=i-1) begin : build_tree
pg_logic u_pg_logic(
.g_in_upper(g[2*i+1]),
.p_in_upper(p[2*i+1]),
.g_in_lower(g[2*i]),
.p_in_lower(p[2*i]),
.g_out(g[i]),
.p_out(p[i])
);
end
endgenerate
// 根から葉に累積されたキャリーを流す
// c_tree[k+bits]は[0,k)のキャリーを持つ
wire [2*bits-1:1] c_tree;
assign c_tree[1] = Cin;
generate
for(i=1; i<bits; i=i+1) begin : push_down
assign c_tree[2*i] = c_tree[i]; // 左はそのまま
assign c_tree[2*i+1] = g[2*i] | (p[2*i] & c_tree[i]);
//右は今まで伝わっている部分と下位の積
end
endgenerate
generate
for(i=0; i<bits; i=i+1) begin : final_sum
assign Sum[i] = p[bits+i] ^ c_tree[bits+i];
end
endgenerate
assign Cout = g[1] | (p[1] & Cin); // Coutは全区間=根とCinの合成
endmodule
これも本当にBrent-Kung adderになっているか確かめてみましょう．
Brent-Kung adderの特徴はノード数が$O(N)$，面積が$O(N\log_2 N)$です．
セグ木をご存知の方には言うまでもないですし，プログラムを見ればg，pの長さは$2N$なので，ノード数が$O(N)$なのは明らかですね．もちろんこれはあくまでもverilogの都合で書いているものなので，実際はこれらのg，pの間のモノイドの数が$O(N)$なのでゲート数が$O(N)$だということです．
では面積はというと，セグ木なんだから当然$O(N\log_2N)$だろと言いたいんですが，多分これはプログラムだけではわからないですよね．
ggって出てきた実装とはかなり違う実装をしているので，本当にこれでいいのかはちょっと不安ですが，聞いた話と同じ雰囲気なので同じだと思うことにしました．
わかっていたことですが，これはクリティカルパスがちょっと長くなりますよね．
例えば，MPI_Allreduceみたいなやつを自作するときも，木構造にすると行きと帰りで2倍の長さを通信しなければならなかったりするので，もうちょっといいトポロジーはないかと考えてハイパーキューブなんかを実装するわけですが，そういうのが加算回路にもあると嬉しいですよね．
まぁMPIの集約演算と違って加算回路は非可換の演算を扱う(加算自体は可換演算だけど)のでハイパーキューブは使えないんですけど．
対数深さの加算回路3 Han-Carlson adder
手っ取り早くKogge-Stone adderとBrent-Kung adderのいいとこどりをする方法として，両方を混ぜるということが考えられます．それがHan-Carlson adderです．なんとWikipediaのページがありませんでした．
困ったなぁ．
実装自体はgeminiとかに前記のプログラム2つと合わせて，verilogのparameterで任意の2冪ビットで動作するように頼むといい感じのものが出てきます．
ざっくり理解するなら，ビット数が多い部分をBrent-Kung的アプローチで小さくして，十分小さくなったらKogge-Stone的なアプローチで解いて，最後にBrent-Kungの配るほうをやるという感じです．
最後がこんなに短いのはもちろん力尽きたからです．
最後に
私はあまりHDLは書かないのですが，調べてみると結構面白かったですね．
次は整数乗算器か，整数除算器か，あるいは浮動小数点か，いずれにせよ面白そうなもので簡単そうなものはまだまだ転がってますから，気が向いたら次を書くかもしれません．
あ，一応この記事に書いているverilogプログラムはすべてiverilogでテストしているので，使えると思います．
ただ，実際のFPGAで使っても+演算子は専用の最適化がされているので早くなりませんけどね．
-
積和標準形は$A\cdot B+C\cdot D$のような形で積の和の形になったもので，選言標準形，加法標準形，DNFとも呼ばれる．逆に和の積の形となる和積標準形は連言標準形，乗法標準形，CNFとも呼ばれ，SATとかではこちらを解くことになる．回路ではどちらでも都合の良い方を使えばいいが，CNFを使うなら，0の側をまとめて取って，入力を反転する．詳しくは，中野浩嗣・伊藤靖朗著 デジタル回路設計入門-FPGA時代の論理回路設計- 25~33ページを参照．うちの大学の先生が書いた本でデジタル回路設計の授業の教科書でした．宣伝じゃないよ ↩