コンピュータアーキテクチャの話 (75) パラレルプリフィックスアダー(3)

　Ladner-Fisher Adder (1980年)

　Sklanskyアダーの大きなファンアウト、Kogge-Stoneアダーの必要なボックス数が多いという問題を解決する方法として、Ladner-Fisherアダー、Han-Carlsonアダーなどが提案されている。これらはKogge-Stoneと同様に、何れも考案者の名前が付けられたアダーである。

　次の図にLadner-Fisherアダーのキャリー計算回路を示す。Ladner-Fisherのキャリー計算回路は1段目はSklanskyアダーと同じで偶数、奇数ペアのP,Gを生成するが、2段目はKogge-Stoneアダーのように2箇所右側のビット位置から取っている。そして、3段目と4段目はSklanskyアダーのように複数のファンナウトを持つステージとなっているが、次の段のボックスは一つ置きに間引かれているのでSklanskyアダーと比べるとファンナウトは半減している。

　しかし、4段目までのボックスでは奇数ビットのキャリーだけの計算であり、偶数ビット位置のキャリーを作るために5段目のボックスを必要とする。前述のSklanskyアダーでは、16ビットのキャリー生成は最小限の4段のボックスで実現されていたのであるが、Ladner-Fishderアダーでは、ボックス通過段数を1段追加することによりファンナウトを半減している。

　16ビットLadner-Fisherアダーのキャリー計算回路

　ファンナウトの半減による遅延時間の短縮と5段目のボックスを通過するための遅延を比較すると、この例で取り上げた16ビット程度の長さのアダーでは5段目のボックスの通過時間の方が大きいのではないと思われるが、ビット数がより大きいアダーではファンナウトが半減する段数が増えるので、Sklanskyアダーより高速になると思われる。

Han-Carlson Adder (1987年)

　Han-Carlsonアダーは、回路量が大きいというKogge-Stoneアダーの欠点を解消しようというものである。次の図にHan-Carlsonアダーのキャリー計算回路を示すが、必要ボックス数は33個とKogge-Stoneアダーの49個よりかなり少なく、Sklanskyアダーの32個に比べて1個多いだけである。

　16ビットHan-Carsonアダーのキャリー計算回路

　この図に見られるように、Han-Carlsonアダーの場合は、1段目が右隣、2段目は2箇所右側、3段目は4箇所右側、4段目は8箇所右側から入力する点はKogge-Stoneアダーと同じであるが、ボックスが半分に間引かれているので、配線本数は半分になっている。

　しかし、間引いたままではC2、C4、…というキャリーが計算できない。これを補うのが5段目のプリフィックスボックスである。これで4段目までで計算されたP、G信号を右側の奇数ビットのP、G信号にプリフィックスしてキャリー信号C2、C4、…を生成する。

　つまり、Han-CarlsonアダーはKogge-Stoneアダーと比較すると、ファンナウト=2をキープして、配線とボックス数を減少させている。しかし、その代償は5段目のプリフィックスボックスで、最長のキャリーの遅延時間がボックス一段分増加している。

　以上述べてきた各種のParallel Prefixアダーのどれが高速かは、アダーのビット数、使用する基本回路の形式、ゲートの入力容量と配線容量の比率や、回路の配置に依存してそれぞれの配線長がどうなるかによって変わり、一概にどれが速いとは言えないが、64ビットアダーのようにビット数が長くなると、Kogge-StoneやHan-Carlsonアダーの方が、ファンナウトが増えるLadner-FisherやSklanskyアダーより高速に出来るようである。

　ここでは代表的な考え方の4種のParallel Prefixアダーについて説明したが、これ以外にも多くのParallel Prefixアダーが提案されている。また、ここで説明したParallel Prefixアダーは1ビット単位のプリフィックスボックスを使うものである。論文としては、複数ビット単位のプリフィックスボックスを使うアダーも発表されているが、ここでは割愛する。