コンピュータアーキテクチャの話 (87) 1サイクルに複数ビットの商を求める割り算器

　

　商を1ビットづつ求めるのは繰り返し回数が多く時間が掛かるので、乗算のブースアルゴリズムのように、複数ビットの商を1サイクルで求められないかということになる。しかし、毎サイクル2ビットの商を求めようとすると、商の値は0～3の可能性があり、その時点での被除数レジスタの値(以下では部分剰余と呼ぶ)が除数Dの1倍以下、2倍以下、3倍以下、それ以上のいずれであるかを正確に知る必要がある。

　そのためには、次の図-8に示すように、除数Dの1倍と1ビット左シフトした2倍、それらをアダーで加算した3倍の値を作り、それぞれ、引き算器(サブトラクター、図中ではサブと略記する)で部分剰余から引き算を行い、大小関係を判別する。例えば、部分剰余Pが除数Dの1.5倍であったとすると、3D、2Dに対応する引き算器のキャリーは”1″で、1Dの引き算器のキャリーは”0″となる。これをデコーダで2ビットのバイナリ数の”01″に変換する。これが部分商となる。

　

　図8:2ビットづつ部分商を求める回路の概念図

　同時に、マルチプレクサで1Dの引き算器の出力を選択して部分剰余Hレジスタに2ビットシフトして書き戻す。毎サイクル2ビットに限らず、この方法を拡張すれば、3ビットでも4ビットでも部分商を求めることが出来るが、bビットの部分商を求めるには、引き算器とマルチプレクサの入力が2のb乗-1個必要になる。2ビットの場合は3個であるが、3ビットでは7個、4ビットでは15個となり、必要となるハードウェアの物量の負担が急激に増加する。

　なお、一つのステップで1ビットの部分商を得るやり方は、計算の単位は2の1乗であるのでRadix-2の計算法と呼び、2ビットの部分商を得るやり方はRadix-4、3ビットはRadix-8、4ビットはRadix-16の割り算法と呼んでいる。

SRT割り算器

　図8の回路でもRadix-4の割り算を行うことが出来るが、より少ない物量で、複数ビットの部分商を求める割り算法の研究が行われた。その結果、IBMのSweeney氏、イリノイ大学のRobertson氏と、ロンドンのインペリアルカレッジのTocher氏が独立にほぼ同じ方式を考案し、1958年にほぼ同時に論文発表されたので、この割り算のやり方は、考案者3人の頭文字をとってSRT法と呼ばれている。

　以下に述べるSRT法は、それほど多くの物量を必要とせず、複数ビットの部分商を得ることができる方式であり、現在のマイクロプロセサの割り算器には、殆ど例外なく、このSRT法が用いられている。

　商用のマイクロプロセサでの実装例を見ると、2ビット単位で計算するRadix-4のアルゴリズムを採用したものが多いが、最近、Intelは、45nm半導体プロセスで製造する最初のプロセサであるPenrynでは4ビット単位の計算を行うRadix-16の割り算器を搭載すると発表して、話題をよんでいるのはご存知の通りである。

　

　図9:Radix-16割り算器のPenrynへの搭載。(出典:Intel)

　1ステップで2ビットの部分商を求める場合、各ステップで除数Dの0～3倍を引き、結果が1D未満のプラスの数になる必要があるので、除数Dと部分剰余Pの関係を図示すると、次の図10のようになる。但し、この図では、必要なシフトを行って、除数Dは0.5以上1.0未満に正規化し、部分剰余Pは4.0未満になるように正規化されているとしている。

　

　図10:部分剰余Pと除数Dから部分商の値を求めるP-Dプロット

　このように考えると、上記のP-Dプロットで、3と書かれた緑の領域では除数Dの3倍を引き、水色の領域では2倍を引き、クリーム色の領域では1倍を引く必要があることが分かる。しかし、0倍と1倍の領域の区切りはP >_ Dかどうかであり、部分剰余と除数の1倍、2倍と全ビットを見て大小比較を行う必要があり、図8のように3個の引き算器が必要なってしまう。