Nビット加算器の基本
Nビット整数二つを加算した結果を出力する回路を、Nビット加算器と呼びます。 Nビット加算器は、もっとも単純には、全加算器（full adder, FA）をN個直列につなげば作ることができます。 この構成法のことを、リプルキャリー加算器（ripple-carry adder, RCA）と呼びます。 リプルキャリー加算器は、Θ(N)の遅延を持ち遅いため、使われることは稀です。 ただし、最も小さな加算器構成法であるため、遅延が気にならない場合には優れた構成法です。
キャリー先読み加算器
リプルキャリー加算器が遅いのは、下の桁で生じたキャリーがわからないことには上の桁で生じるキャリーがわからない、という依存関係が直列に並んでいるためです。 キャリー先読み加算器（carry-lookahead adder, CLA）は、上の方の桁で生じるキャリーを何らかの方法で算出する回路を備えた、高速な加算器です。 上の方の桁で生じるキャリーを一足飛びに算出することで、高速な加算を実現します。 上の方の桁で生じるキャリーは、下の方の桁で生じるキャリーを使わずに*1、加算器の入力だけを用いて計算します。 上の方の桁で生じるキャリーを直接計算することは、原理的には可能ですが、指数的に多くの回路素子が必要となるため現実的ではありません。 実際には、以下のようなΘ(log N)段で計算できる方法を使うことが多いようです。
よく紹介されるキャリー先読み加算器では「4ビットをひとまとめのブロックとして、そのブロックから外にキャリーが出るか」を算出しています。 これだけだとキャリーの伝搬が4倍速くなっただけですが、この手順を再帰的に繰り返すことで、指数的な高速化を図ります。 このブロックが16進の全加算器のようなものになっていることに着目します。 このブロックを4つまとめてスーパーブロックとして、「スーパーブロックから外にキャリーが出るか」を算出することで、16ビット先のキャリーを算出することができます。 以下、64ビット先、256ビット先、……と指数的に上のビットでのキャリーを算出することができます。
キャリー先読みにより、より小さなビット幅の高速な加算器を作る問題に帰着されることになります。 したがって、これを再帰的に行えばΘ(log N)段の遅延で結果が出る加算器が完成します。
並列プリフィクス加算器
並列プリフィクス加算器（parallel prefix adder, PPA）は、高速加算器の構成体系です。 並列プリフィクス加算器に分類される加算器は無数にありますが、いずれも各桁のキャリーをΟ(log N)段で算出します。
したがって、広い意味でのキャリー先読み加算器の一種になります。
並列プリフィクス加算器は、キャリーの生成g（二つの入力のこの桁がどちらも1で、下の桁のキャリーにかかわらずこの桁でキャリーが出る）とキャリーの伝搬p（二つの入力のこの桁が片方だけ1*2で、下の桁のキャリーがそのままこの桁のキャリーとなる）のペアに関する特定の二項演算がモノイド（単位元があり、結合則が成り立つ）になることを利用した加算器です。 具体的には、(g0,p0)⊕(g1,p1)=(g0&p1|g1,p0&p1)という二項演算です。 結合則が成り立つということはどこから計算し始めてもよいということで、特に二分木状にマージすることを並列に行うことでΘ(log N)段の遅延で“総和”が求まります。 実際には、“総和”だけでなく、各部分和を求めることもΟ(log N)段でできます（prefix scan）。 並列プリフィクス加算器という名前は、これに由来します。
並列プリフィクス加算器として有名なものに、Sklansky加算器（Sklansky adder, 1960*3）、Kogge-Stone加算器（Kogge-Stone adder, 1973）、Brent-Kung加算器（Brent-Kung adder, 1982）があります。 また、Sklansky加算器とBrent-Kung加算器の中間的特性を持つLandner-Fischer加算器（1980）、Kogge-Stone加算器とBrent-Kung加算器の中間的特性を持つHan-Carlson加算器（1987）、Sklansky加算器とKogge-Stone加算器の中間的特性を持つKnowles加算器（1999）もあります。 これらの関係をまとめた論文が"A Taxonomy of Parallel Prefix Networks"であり、その際に三者すべての中間的特性を持つ謎の加算器も発見されました（Harris, 2003）。
以下では、最も極端な特性を持つ三種類の並列プリフィクス加算器（Sklansky加算器、Kogge-Stone加算器、Brent-Kung加算器）の特性をまとめてみます。
Sklansky加算器
- ☹️回路素子量がΘ(N log N)
- 😊回路面積がΘ(N log N)
- ☹️最大ファンアウトがΘ(N)
- ファンアウト16などは非現実的
- 😊回路の段数が最短（モノイドの二項演算がlog N回）
Kogge-Stone加算器
- ☹️回路素子量がΘ(N log N)
- ☹️回路面積がΘ(N2)
- 長さΘ(N)の長い配線がΘ(N)本必要なため
- 😊最大ファンアウトが2
- Sklansky加算器よりも高速に動作する
- 😊回路の段数が最短（モノイドの二項演算がlog N回）
Brent-Kung加算器
- 😊回路素子量がΘ(N)
- 高速加算器の中では最も消費電力が少ないとされる
- 😊回路面積がΘ(N log N)
- 回路素子量がΘ(N)なのにΘ(N log N)の面積が必要なのは、配線の長さの合計がΘ(N log N)になるため
- 😊最大ファンアウトが2
- ☹️回路の段数が他のものと比べて約二倍（モノイドの二項演算が2 log N - 1回）
よく紹介されるキャリー先読み加算器はどれ？
4つごとにグループ化するタイプのキャリー先読み加算器は、これらのうちどの方式なのでしょうか。 そもそも、並列パラレルプリフィクス加算器と呼んでよいのでしょうか？
Fast Adder Architectures: Modeling and Experimental Evaluation（http://web.tecnico.ulisboa.pt/~ist14359/wordpress/nfvr_pubs/dcis03.pdf）という論文*4のFig. 1には、2つごとにグループ化するタイプのキャリー先読み加算器の構成法が載っています。 上から下に情報が流れていくのではなく、上から入力された情報がいったん下に集められてから上に戻され、上から加算結果が出力される、という方式になっており、ぱっと見ではどの入力とどの出力がつながっているのかや段数などが良くわかりません。
上から下に流れるタイプで書き直してみたのが以下の図1になります。
これはほぼBrent-Kung加算器です（後半部分についてボックスを置く位置がずれていますが、受信側に置くか送信側に置くかの違いであり、回路としては同じはずです）。 これが明示されている文献が見つからなかったので、回路の構成を展開して考えて初めて分かりました。 冷静に考えてみると、情報が下に集められた後に上に行くので、2 log N段くらいになりそうで、つまりSklansky型やKogge-Stone型ではないはずと予想できたかもしれません。
4つごとにグループ化するタイプのキャリー先読み加算器も、おそらく、4入力のプリフィクスボックスを使い、Brent-Kung型のネットワークを組んで動かしているのでしょう。
*1:実際には、回路規模削減のため、遅延が増えない範囲で下の方の桁で生じるキャリーの情報を再利用することが多いです。
*2:片方だけ1、ではなく少なくとも片方1、としたものをpの定義とすることが結構あります（実際、図1で使っているpの定義もそれです）。その場合、真の意味での「伝搬」を意味する情報ではなくなり、解釈がやや直観的ではなくなります。一方、特定の二項演算がモノイドであるという議論には影響がなく、またpをXORゲートより簡単なORゲートで作れるようになります。このため、「少なくとも片方1」をpの定義とすることがよく行われるようです。
*3:1960年に提案されたのは桁上げ選択加算器であって、並列プリフィクス加算器としてのSklansky加算器ではなさそうです。conditional sum adder (COSA)の選択信号を作るネットワークがSklansky型になっている、というのが命名の由来のようです。
*4:N. Roma, T. Dias and L. Sousa, "Fast Adder Architectures: Modeling and Experimental Evaluation", Proceedings of the XVIII Conference on Design of Circuits and Integrated Systems, 367–372 (2003).
