Kogge–Stone adder とは

Kogge-Stone加算器(KSAまたはKS)は、並列プレフィックス形式のキャリールックアヘッド加算器です。他の並列プリフィックス加算器(PPA)には、Brent-Kung加算器(BKA)、Han-Carlson加算器(HCA)、最も知られている最も速い種類のLynch-Swartzlanderスパニングツリー加算器(STA)があります。
Kogge-Stone加算器は、Brent-Kung加算器より実装面積が広いが、各段階でファンアウトが低く、一般的なCMOSプロセスノードの性能が向上する。しかし、配線混雑は、Kogge-Stone加算器ではしばしば問題になります。 Lynch-Swartzlanderのデザインは小さく、ファンアウトが低く、配線の輻輳に悩まされません。しかし、使用されるプロセスノードは、マンチェスターのキャリーチェーン実装をサポートする必要があります。パラレルプレフィックス加算器を最適化する一般的な問題は、可変ブロックサイズ、マルチレベル、キャリースキップ加算器最適化問題と同一であり、その解決策は1996年のトーマスリンチの論文に見られる。
図には、4ビットKogge-Stone加算器の例が示されています。各垂直ステージは、示されるように、「伝播」ビットおよび「生成」ビットを生成する。最終的な生成ビット(桁上げ)は最後の段(垂直)に生成され、これらのビットは入力の後に最初の伝播(赤のボックス)と排他的論理和をとり、合計ビットを生成します。例えば、第1(最下位)の合計ビットは、一番右の赤いボックス(「1」)の伝播をキャリーイン(「0」)と排他的論理和し、「1」を生成することによって計算される。第2のビットは、第2のボックス内の伝搬を右から(「0」)C0(「0」)でXORし、「0」を生成することによって計算される。
Kogge-Stone加算器の概念はPeter M. KoggeとHarold S. Stoneによって開発されました。このStoneは1973年の論文の中で一般的なクラスの反復式の効率的な解法のための並列アルゴリズムを発表しました。