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

　

　これを解決するのがSRT法で、

部分剰余Piと除数Dの一部の上位ビットから部分商Qiの値を予測Pi – Qi×Dを計算し、部分剰余Pi+1を計算

　という手順で計算を行う。ここで、「部分剰余Piと除数Dの一部の上位ビットから部分商Qiの値を予測」というところがミソである。なお、Pi、Qiはi回目のステップの部分剰余、部分商という意味である。

　引き放し法では部分剰余がマイナスになることを許容し、部分商Qiは1と－1をとることにしたが、Radix-4の場合でもこのような計算方法が可能である。Radix-4の場合は、一桁は4つの値をとる必要があるので、これを0、1、2、3とするのが自然であるが、それ以外にも表現法がある。0～3は全く余裕のないデータの表現法であるが、これを-2、-1、0、1、2の5つの値をとるデータ表現を使うと、部分商がとり得る値に1つ余裕が生まれる。

　あるビットから、それ以降の繰り返しで全部の部分商が2になると、-(2/4 + 2/16 + 2/64 +…)となり、(無限に続く場合は、)部分剰余から2D/3が引かれることになる。また、全部の部分商が‐2となると、部分剰余に2D/3が足されることになる。つまり、各ビットで、部分剰余を更新する場合、結果が+2D/3以下で-2D/3以上の範囲に納まっていれば、それ以降の部分商で調整ができる範囲である。

　この関係を逆に考えると、除数をDとすると、部分商が2の時は、部分剰余Pは(2+2/3)Dから(2-2/3)Dの範囲であれば良い。また、部分商が1の時は、部分剰余Pは(1+2/3)Dから(1-2/3)Dの範囲であれば良い。部分商2の下限は4D/3 であり、一方、部分商1の上限は5D/3である。つまり、部分剰余Pが4D/3から5D/3の間にある場合は、そのステップの部分商として、2を選んでも、1を選んでも良いことになる。これを図にすると次のようになり、灰色にハッチした、PDプロットにQiが0でも1でも良いというような領域が生まれる。

　図11:部分商の各桁を-2～2の5状態とした場合のPDプロット

　次の図12は、この図の上半分を拡大して、選択すべきQiの値ごとに色分けした図である。

　図12:選択すべき部分商Qiの値を色分けしたPDプロット

　この図では、除数側を8領域、部分剰余側を11領域に分けており、前の図においてグレーで示したどちらの値でも良いという領域を、適当にどちらかの値の領域とくっつけることにより、PDプロットのマスごとにQiの値を決めている。

　このPDプロットのマス分割では、除数Dの上位3ビットと、部分剰余Pの上位4ビットを使えば、マスを指定することができる。しかし、このマス分割は不完全で、2個の白抜きのマスが残っている。左側のマスでは、ひとつのマスの中にQiが”1″の領域と”2″の領域が含まれており、一つの値に統一することが出来ない。また、右側のマスも同様である。

　つまり、この分割では各マスのQiの値を一通りにするには分割の細かさが不十分で、部分剰余P側の刻みを半分にしてやれば、現在、白色のマスの上側は”2″、下側は”1″とすることができる。つまり、部分剰余Pの上位5ビットと除数Dの上位3ビットの合計8ビットをインデックスとするROMを使えば、正しく部分商を予測できるテーブルを作ることができるというわけである。この表をQuotient Selection Tableと言う。また、ROMを使わず、PLAのような回路でテーブルと等価な値を与える回路を作ることも可能であり、一般的には、この回路をQuotient Selection Logicと呼ぶ。

　このように、冗長度のある状態割り当てによりPDプロットにどちらの値でも良いという領域を作り、これを利用してP、Dの少数の上位ビットで索引する粗いマスのテーブルを使ってQiを求めるというのがSRT法の基本アイデアである。

　SRT割り算器の回路を次の図-13に示す。

　図13:Radix-4 SRT割り算器の構成

　この図で、Quotient Selection Tableと書かれた箱が、PDプロットのマスによってQiを選択するテーブルである。上の説明では省略したが、部分剰余が負になった場合には加算を行うようにアダーを切り替える信号も、このブロックで生成する。

　この図13の回路は、図6に示した改良された引き戻し法によるRadix-2の回路と比較すると、部分商選択テーブルと、除数Dの-2～2倍を選択する切り替え回路が追加になっているだけであり、比較的少ない回路の追加で割り算に必要なステップ数を半減している。

　なお、SRT法では、引き放し法と同様に、最後の剰余がマイナスになる場合があり、その場合は、補正に1サイクルを必要とする。従って、Radix-4のSRT法による割り算に必要なステップ数はN/2+1となる。