Algorithmic Checkを用いたエラー検出

図2.3のAlgorithmic Checkの場合はユニットの出力にチェッカ(Checker)を付けて、一般には出力より少ない本数のチェックシンボルを作る。また、第2のユニットの替わりにプレディクタ(Predictor)という回路を設けて、入力から処理結果のチェックシンボルを予測する。そして、予測されたチェックシンボルとチェッカで計算されたチェックシンボルが一致しているかどうかをチェックしてエラーを検出する。

この構成が有効に機能するためには、チェッカの計算アルゴリズムは、どの出力が誤ってもそれがチェックシンボルに影響するようなものでなければならない。また、プレディクタの回路がユニット本体よりも複雑になってしまったのでは、二重化比較と比べてメリットが無い。

ということで、二重化比較と違ってAlgorithmic Checkは適用できる範囲が限られ、プロセサの中で良く用いられるのは乗算器のチェックである。入力A、Bの乗算の場合、

という関係が成り立つ。ここでModpはpのモデュロ演算(pで割った余りをとる)でpは素数である。一般にはpは3とか7が用いられ、Modpは2ビットとか3ビットというサイズになる。

一般的な2進数の割り算を行うのは大変であるが、pが3とか7の場合には簡便に余りを求める方法がある。

2の0乗は1であるので、余りは1である。2の1乗は2であり、余りは2となる。そして、2の2乗は4であり、p=3の場合は余りは1、p=7の場合は余りは4である。2の3乗は8であり、p=3の場合は余りは2、p=7の場合は余りは1となる。結果として図2.4に示すように、各桁のModpの値は、p=3の場合は1、2の繰り返し、p=7の場合は1、2、4の繰り返しとなる。

従って、元の2進数で"1"が立っている桁の位置に応じて、この1、2、4の値を足し、pを超えたらpを引いてp未満の数にするという操作を行えば、pで割った余りを求めることができる。

Modpを求めるための各桁の余りの合計は、並列乗算器のところで説明したCarry Save Adder(CSA)のツリーを用いて計算するが、乗算器と比較すると必要なCSAの個数が少なく、乗算器を2個用いて二重化比較を行うよりも少ないハードウェアでエラーチェックができる。

加算器にAlgorithmic checkを用いた例もあるが、プレディクタの回路がかなり大きくなる。そのため、プレディクタの設計に手間を掛けず、同じ加算器を並べて二重化比較でエラーを検出するという設計も多く見られる。