kivantium活動日記

プログラムを使っていろいろやります

除算器 その2

この記事はkivantium Advent Calendarの11日目です。

昨日は回復法を用いた除算器の設計を説明しました。回復法は符号付き整数を扱えないという欠点がありました。今日はこれを克服する非回復法を説明します。

非回復法(引き放し法)

回復法では引き算の結果にキャリーが発生するかどうかを見て、レジスタに元の値を入れるか減算器の出力を入れるかを決定していました。非回復法ではキャリーが発生した場合もそのまま減算器の出力を入れ、次の桁では加算を行います。回復法における「D桁目は引かずにD-1桁目で引く」という動作は、非回復法で「D桁目で引きD-1桁目で足す」という操作に相当します。どちらも結果として同じ数を引いていることが分かると思います。
符号なし整数で10÷3を行う例を示します

    (+1)(-1)(+1)
011)-------
    01010
   -011   <- 同符号なので引く
    ----
    11110 <- -2 (=10-3x2^2)
    +011  <- 異符号なので足す
    -----
    00100 <- 4 (=10-3x2^2+3x2^1)
     -011 <- 同符号なので引く
   ----
    00001 <- 1 (=10-3x2^2+3x2^1-1)

(+1)(-1)(+1)は3に相当するので3余り1という正しい演算結果が出ることが分かりました。

このように各商がbitが±1の値を持つ形で与えられるのを元に戻すコストなどが必要ですが、符号付きでも扱えるというメリットが大きいです。

実装は厳しいので今日のところは省略します‥‥

SRT法

今まで説明した方法による割り算の実行には被除数bit数と同じサイクルが必要になります。これを減らすには数bitずつ一気に割ることでサイクル数を減らすことが考えられます。2bitずつ割る方法をRadix-4、4bitずつ割る方法をRadix-16と呼びます。

引き戻し法が商を{0, 1}から選び、引き放し法が{-1, 1}から選んでいたのは2進数で1bitずつ見ていたからでした。複数bitずつ見た時にも候補を瞬時に確定することができれば1サイクルで複数bit分の商を確定することができます。
このアイデアに基づいて数bitずつ割り算を実行するのがSRT法です。
Radix-4の場合には商の候補として{-2, -1, 0, 1, 2}が存在しますが、詳細に分析すると部分剰余の上位5bitと除数の上位3bitのみから決定することができ、引き放し法と同じ要領で正しい2進数として復元すれば商を被除数のbit数の1/2のサイクルで求めることができます。

PentiumまではRadix-4が、Core2シリーズからはRadix-16が利用されているようです。

(図は http://www.intel.com/content/dam/www/public/us/en/documents/research/2008-vol12-iss-3-intel-technology-journal.pdf p.188より)

SRT法は商を決定するテーブルの決定が難しく、Pentium浮動小数点演算のバグはこのテーブルの埋め方に問題があったのが原因とされています。

Intelがバグらせるものを締め切りまでのあと10分で書けるとは思えないので実装は省略します……。

次回は引き算の繰り返しではない別の割り算アプローチを見ていきます。