演算器の設計 - 加算器(Adder)

本連載はHisa Ando氏による連載「コンピュータアーキテクチャ」の初掲載(2005年9月20日掲載)から第72回(2007年3月31日掲載)までの原稿を再掲載したものとなります。第73回以降、最新のものにつきましては、コチラにて、ご確認ください。

コンピュータは電子計算機と訳されており、計算する機械である。計算機が実行する演算は、四則の数値演算以外にも、ビット毎のAND、OR、NOTなどをとる論理演算やシフト演算などがある。また、数値演算に限ってみても計算を行う対象は整数と浮動小数点数がある。

更に、最近のプロセサでは、一般的な論理演算や数値演算だけではなく、グラフィックスの処理などを高速化するための演算が追加されたり、暗号処理を高速化するための多桁の整数乗算などを高速化する演算などがサポートされたりするようになって来ている。

しかし、何と言っても基本となるのは整数の加減算であり、数値演算に用いられるだけでなく、ロード/ストア命令のアドレス計算や分岐命令の分岐先アドレスの計算にも専用の加算器が使われており、高速に加算を実行することはコンピュータの高速化にとって極めて重要である。と、いうことで、加算器の高速化に関しては長い研究の歴史があり、多くの論文が発表されている。

この演算器の設計シリーズでは、まず、この高速加算器を取り上げ、引き続き、乗算器などのその他の演算器の設計を取り上げていくことにしたい。

加算器 (Adder)

次に示す論理回路図は、1ビットの2進数をキャリー込みで加算する1ビットの加算器で、フルアダーと呼ばれる。

• 1ビット フルアダー回路

論理図のXORゲート 1で、AとBの和を計算し、更にXORゲート 2で、C-inとの和を計算しており、これがその桁の和(Sum)となる。一方、この桁の計算から桁上がり(Carry)が出るのは、A、B、C-inの少なくとも二つが"1"の場合であり、NANDゲート 3はAとC-inが双方とも"1"の場合を検査し、NANDゲート 4はBとC-in、NANDゲート 5はAとBが"1"になっていると"0"を出力する。NANDゲート 6は入力の一つ以上が"0"であると"1"を出力するので、A、B、C-inのいずれか2つが"1"となっている場合にC-outが"1"となり、桁上がり信号を生成している。

1ビットだけの加算ではほとんど役には立たないが、この1ビット加算回路を桁数分だけ並べて、小学校で習った2桁以上の足し算のように、最下位の桁を足し、桁上がりを含めて次の上位の桁を足すという操作を繰り返せば多ビットの加算を行うことが出来る。この方式で多ビットの加算を行う回路を次の図に示す。

• n+1ビット リップルキャリーアダー

最下位ビットのA0、B0とC-inをフルアダーで加算し、その桁上がりを次の桁のA1、B1との加算のC-inとし、更に、その桁上がりをA2、B2に加算のC-inとし、というように最上位ビットまで繰り返してキャリーを伝播させて行く。このキャリーの伝わり方が、水面に石などを放り込んだときにさざ波(Ripple:リップル)が伝わるのに似ているので、この形式のアダーはリップルキャリーアダーと呼ばれる。

この方式は、昔、小学校の算数で習った足し算の2進数版をハードウェアに置き換えただけであり、原理的に、非常に分かり易いのであるが、最下位のC-inから結果のC-outに至るまで、桁数分のフルアダーを信号が通過する必要がある。桁数が4ビットとか8ビットであれば問題無いが、32ビットとか64ビットの加算となると、この信号の伝搬遅延時間が問題となる。

あまり頻繁に使われない演算であれば、計算に多少時間が掛かっても性能に大きな影響は無いが、加算は使用頻度が高く、加算結果を次の命令で使用するという使い方が多いので、加算は1クロックサイクルで演算が完了するように作るのが普通である。

最近のマイクロプロセサではキャッシュメモリ用のSRAMのアクセスや、アウトオブオーダ実行のための制御回路などの複雑な回路があり、これらの部分の遅延もクロックサイクルを決める要素となっているが、昔は加算器が一番複雑な論理回路であり、加算器の遅延時間がプロセサのサイクルタイムを決めていた。このため、プロセサのクロック周波数向上のためには加算器の高速化が重要なテーマであり、多くの研究がなされている。