リニアアレイとパラレルアダー

リニアアレイ

前述のように、乗数のビットにゼロが多い場合は、ゼロをスキップすれば乗算に必要な繰り返しを減らすことができるが、乗数のビットの"0"、"1"にかかわり無く複数ビットを同時に処理できれば、より望ましい。最初に述べた1ビットづつ処理する単純な乗算器の複数回の繰り返しを1回で実行する方式として考えられたのが、次に述べるリニアアレイである。

上の図に示すように、一番上のアダーが最下位の乗数ビット、次のアダーが2番目の乗数ビット、そして一番下のアダーが3番目の乗数ビットに対応する部分積を加算するようになっている。つまり、1ビットづつ処理する乗算器の3回のループを物理的に展開したものである。

そして、乗数と積のレジスタは1回の処理ごとに3ビットづつ右にシフトを繰り返せば、乗数を3ビット単位で処理することができる。この方式では乗数を3ビットづつ処理するので、乗数全体を処理するためのループの回数はN/3となるが、1回の部分積の計算には3段のアダーを通過するので元の回路よりループ1回の計算に必要な時間は長くなってしまう。仮に、計算時間がアダーの通過時間だけで決まるとすると、この方式では1回の部分積の計算に3倍の時間がかかることになり、ループ回数が1/3になっても全体の計算時間は短くならない。

実際には、積レジスタの書き込みや読み出しの時間が3回から1回に減るので、1ビットづつ処理する方式よりは多少は速くなるが、リニアアレイ方式は、アダーを複数個にして物量をつぎ込んだ割には高速化の効果が少ない。

パラレルアダー

リニアアレイは、複数の演算器を使って複数の部分積の加算を行っているが、この考えを押し進めると、乗数の各ビットに対応する全部の部分積を加算する回路を作ってしまえば、ループを回る必要は無く、1回で積が計算できるという方式になる。もちろん、リニアアレイ方式でも乗数のビット数だけのアダーを直列に繋げば、ループ無しに全部の部分積を加算することが出来るが、速度的には効率の良い方法とは言えない。

乗数のビット数分の多数の部分積を、バイナリーツリー(2分木)構造に接続したアダーでトーナメント方式のように加算を行えば、log2(N)段のアダーの通過時間で計算できる。これが、パラレルアダー方式の乗算器である。

この図に示すように、乗数レジスタの各ビットをそれぞれのマルチプレクサに配り、並列に全ての部分積を作り、アダーをツリー状に配置して全ての部分積を加算してしまう。1個のアダーは2つの入力を1つにまとめる働きであり、部分積を1個減らすだけであるので、乗数がNビットの場合、全体ではN-1個のアダーが必要となる。また、アダーの通過回数はlog2(N)であり、16ビットの場合はアダー4回分、32ビットの場合はアダー5回分の遅延が必要となる。

これでは遅延時間が長すぎてクロックサイクルが伸びてしまうという場合は、次の図のように、アダーの段ごとにフリップフロップで作られたレジスタを置いてやれば良い。このようにパイプライン化すると、1サイクルには1段のアダーを通過するだけで良いので、クロック周波数は高くできるが、16ビットの場合は結果が得られるまで4サイクルを必要とすることになり、結果が得られるまでの遅延時間の点では、1ビットづつ処理する乗算器と比べて4倍の性能向上しか得られない。しかし、16回のループで計算する乗算器の場合は、次の演算を開始できるのは16サイクル後であるが、パイプライン化したパラレルアダー方式の乗算器では、次のサイクルには別の乗数、被乗数ペアの乗算を開始することが出来るので、単位時間に実行できる乗算の数としては16倍になっている。