Lingアダー

1981年にIBMのワトソン研究所のH.Ling氏は、P、G信号とは異なるキャリーの計算方法を提案し、この方式の方が計算が容易で、高速に加算が実現できるという論文を発表した。この方式は、発明者のLing氏にちなんでリングアダーと呼ばれている。

Ling氏の方式では、Lingキャリーと後に呼ばれることになるHiを、

  • Hi = Ci＋Ci-1

と定義する。ここで、Ci、Ci-1は通常のiビット目とi-1ビット目のキャリーである。このように定義すると、

  • Hi = Gi＋Gi-1 ＋ Pi・Gi-1 ＋ Pi-1・Gi-2 ＋ … ＋ Pi-1・Pi-2・…・G0 ＋ Pi・Pi-1・…・G0

となる。しかし、Gi-1＋Pi・Gi-1はGi-1、…、Pi-1・Pi-2・…・G0＋Pi・Pi-1・…・G0はPi-1・Pi-2・…・G0と同じであるので、この式は次のように簡単化できる。

  • Hi = Gi＋Gi-1 ＋ Pi-1・Gi-2 ＋ … ＋ Pi-1・Pi-2・…・G0

例えば、通常のキャリーC5は、

  • C5 = G5 ＋ P5・G4 ＋ P5・P4・G3 ＋ P5・P4・P3・G2 ＋ P5・P4・P3・P2・G1 ＋ P5・P4・P3・P2・P1・G0

で計算されるのに対して、リングキャリーH5は、

  • H5 = G5 ＋ G4＋P4・G3 ＋ P4・P3・G2 ＋ P4・P3・P2・G1 ＋ P4・P3・P2・P1・G0

で計算することが出来る。ORの項数はどちらも同じであるが、2項目以降はANDされる項数が一つづつ減っており、リングキャリーの方が通常のキャリーより高速に計算することが出来る。

しかし、当然、これにはデメリットもあり、和SiはAi(+)Bi(+)Ci-1では計算できず、

  • Ci-1 = Pi-1・Hi-1 = Pi-1・Gi-1 ＋ Pi-1・Gi-1 ＋ Pi-1・Pi-2・Gi-2 ＋ Pi-1・Pi-2・Pi-3・Gi-3 ＋ …

であるので、

  • Si = *Hi-1・(Ai(+)Bi) ＋ Hi-1・(Ai(+)Bi(+)Pi-1)

で計算する必要がある。

Ling氏のアイデアは、2ビットづつ纏めて計算すると計算が容易になるというのが原点であり、上記のH5と対になるH4は、

  • H4 = G4 ＋ G3＋P3・G2 ＋ P3・P2・G1 ＋ P3・P2・P1・G0

である。ここで、Gi・PiとGiは等しいので、これを用いてH5、H4の式を変形すると、

  • H5 = (G5+G4)＋P4・P3・(G3+G2) ＋ P4・P3・P2・P1・(G1+G0) ・H4 = (G4+G3)＋P3・P2・(G2+G1) ＋ P3・P2・P1・P0・G0

となる。更に、Fi=Gi+Gi-1、Qi=Pi・Pi-1と定義すると、G-1は"0"であるので、

  • H5 = F5＋Q4・F3＋Q4・Q2・F1 = (F5,Q4)×(F3,Q2)×(F1,Q0) ・H4 = F4＋Q3・F2＋Q3・Q1・F0 = (F4,Q3)×(F2,Q1)×(F0,Q-1)

となる。この形はP、Gを使った計算と同じ形であり、P、Gの代わりにQとFを使ったプレフィックス演算でHを求めることが出来る。但し、Pi-1は"0"であるので、Q0、Q-1は"0"である。

このQとFを用いるプリフィックス演算回路を次の図に示す。

FとQのプリフィックス演算を行うH-Boxの論理回路

LingキャリーHの計算もプリフィックス計算であるので、キャリーCの計算と同様に、分割の仕方により各種の構成が可能である。次の図に、Sklansky型のLingキャリー計算回路を示す。

Sklansky型のLingキャリー計算回路

また、Kogge-Stone型にLingキャリー計算回路を構成すると次の図のようになる。

Kogge-Stone型のLingキャリー計算回路

Lingキャリー計算は、偶数ビットと奇数ビットの2グループで行われるため、演算ビット数の半分のビット群のLingキャリーを纏める回路が二組ある形となる。このため、ここに掲げた二つのLingキャリーの計算回路を、前に掲げた通常のキャリーを計算する回路と比べると、キャリー計算に必要なボックス段数が1段少なくて済む。しかし、次に述べるように最終結果である和を求めるには、セレクタが1段必要となる。

次の図にKogge-Stone型のキャリー計算回路を用いるLingアダーの回路図を示す。

Kogge-Stone型キャリー計算回路を用いるLing Adder

入力は、通常のアダーと同じP、G信号とA(+)B信号であるが、その次のグレーのボックスはP,G信号からQ,F信号を作り出す部分である。この部分は、

  • Fi = Gi＋Gi-1 ・Qi = Pi・Pi-1

を作れば良いので、それぞれORとANDで簡単に生成できる。そして中間の白い箱はプリフィックス演算を行うH-Boxであり、最後のひし形の箱は、和Sを計算する部分である。前に述べたように、Sは次の式で表わされるので、

  • Si = *Hi-1・(Ai(+)Bi) ＋ Hi-1・(Ai(+)Bi(+)Pi-1)

Hi-1が"0"の場合には(Ai(+)Bi)を出力し、Hi-1が"1" の場合には(Ai(+)Bi(+)Pi-1)を選択する次の図に示すようなセレクタで実現できる。

和Sのセレクタ回路

上に掲げたLing Adder全体の図で分かるように、Hi-1と(Ai(+)Bi(+)Pi-1)は並列に計算することができ、(Ai(+)Bi(+)Pi-1)の計算は論理段数が少なく早く計算できるので、和Siの計算はHi-1の計算が速度を決めるクリティカルパスになる。

前述のように、通常のキャリーCi-1よりLingキャリーHi-1の方がボックス1段分短い時間で計算できる。しかし、図の中でグレーの箱で示したF、Qの生成にOR(あるいはAND)ゲート1段が必要であり、また、和Sの生成に上記の図のようにインバータ1段とAND-OR 1段からなるセレクタが必要となるので、これらの論理回路の遅延時間とボックス1段分の遅延時間のどちらが短いかということになる。単純にゲート段数だけを見ると、ボックス1段はAND-OR 1段であり、Lingアダーの方がORとインバータ1段分だけ通過する論理回路が多いが、どのような回路形式を用いるか、配線長がどうなるかなどにより得失が変わってくる。

Lingアダーを用いたマイクロプロセサとしては、HP、Intelを経て現在はAMDに勤めているSamuel Naffziger氏が1996年のISSCCで発表したHPのPA8000が知られている程度であまり採用例は多くないと思われるが、 Parallel Prefix Adderとして通常キャリーを用いる方式と同程度の遅延の高速アダーを実現できる方式である。