パラレルプリフィックスアダー(2)

Sklansky Adder (1960年)

1960年にJ.Sklansky氏により発表され、発明者にちなんでSklansky Adderと呼ばれるアダーのキャリー計算回路は次の図のようになっている。

この図の上端への入力は、各ビットのP、G信号のペアであり、各ボックスは左側の入力を右側の入力にプリフィックスする演算を行う。一般に各ボックスはP、G信号のペアを出力するが、出力が次のボックスに接続されていない場合は、P信号は不要であるので省略して、G信号だけを出力すれば良い。

Sklanskyアダーでは、第1段のボックス群で偶数と奇数のビットペアのP、G信号を計算し、第2段のボックス群の右端の2個のボックスでは、((P(1:0)、G(1:0))に(P2、G2)をプリフィックスして((P(2:0)、G(2:0))、((P(1:0)、G(1:0))に(P(3:2)、G(3:2))をプリフィックスして((P(3:0)、G(3:0))を作っている。そして、同様に、((P(5:0)、G(5:0))に(P6、G6)と((P(7:6)、G(7:6))をプリフィックスして6ビット目と7ビット目のP、G信号を作っている。

更に、3段目のボックスでは、2段目からの((P(3:0)、G(3:0))と((P(11:8)、G(11:8))にそれぞれの項をプリフィックスして4～7ビット目と12～15ビット目のP、G信号を作り、4段目では((P(7:0)、G(7:0))に対してそれぞれの項をプリフィックスして8～15ビット目へのキャリーを生成している。

このようにSklanskyアダーでは、2のn乗ビットのアダーの場合、最大n段のボックスを経由するだけで各ビットのキャリーインを計算することができ、信号が通過するボックス数としては最小の構成となっている。しかし、この図に見られるように(P(3:0)、G(3:0))信号は4箇所、(P(7:0)、G(7:0))信号は8箇所というように信号を分配する箇所(Fan-out,ファンナウトと呼ばれる)が増え、最大2のn-1乗箇所に信号を供給する必要がある。ファンナウトが大きくなると、次段のゲートの入力容量と、それらのゲートに接続するための配線が長くなり配線容量も増加する。このように負荷が大きくなるとプリフィックスボックスの動作速度が大幅に遅くなってしまう。バッファを挿入して信号を増幅する構成とすることにより速度の低下は抑えられるが、それでもバッファの遅延時間分は動作速度が低下してしまう。

Kogge-Stone Adder (1973年)

この大きなファンナウトの問題を解決するのが、当時IBMのワトソン研究所の研究者であったKogge(コーギー)氏とStone氏が1973年に発表したKogge-Stoneアダーである。

次の図に示すように、16ビットのKogge-Stoneアダーのプリフィックス計算部は、同サイズのSklanskyアダーが32個のボックスで済んでいるのに対して、49個と大量のプリフィックスボックスを必要とするが、各ボックスは2箇所に出力を供給するだけで良く、Sklanskyアダーの欠点であるファンナウトが大きいという点を解決している。

この図に示すようにKogge-Stoneアダーでは、1段目のボックスは隣接する右側のビットからの入力、2段目は2箇所右側、3段目は4箇所右側、4段目は8箇所右側のビットから入力を取ることによりバイナリツリーでキャリーを生成している。

Kogge-Stoneアダーでは各ボックスのファンナウトは2と小さいのであるが、後段になるに従って、距離の離れたビットから入力を取ってくる必要があり、配線が長くなる。従って、ファンナウトが小さいからと言ってバッファが不用になるというわけではないが、非常に高速なアダーである。しかし、回路量が多く、かつ、長い配線の本数も多いので、チップ面積や消費電力の点では不利である。

なお、上の図では(G0,P0)信号は全部の段のボックスに入力され、かつ、C0出力にもなっているので、ファンナウトは5である。しかし、この図では省略されているが、各段のボックスが抜けている位置にバッファを挿入することにより、クリティカルパスの遅延を増加させることなくファンナウトを2にすることが出来る。従って、最大遅延時間の観点からはファンナウトは2で考えれば良い。