JPH10187420A - 除算・開平演算器 - Google Patents

Abstract

(57)【要約】 【課題】 SRT除算・開平演算において演算の高速化を
達成し、かつ、回路規模を削減することにある。 【解決手段】 QSL1009とREL1010は商選択/部分剰余上
位桁予測表に基づいて論理合成することによって実現さ
れる。REM1011はREL1010からの部分剰余上位２桁と、CS
A1008からの和１ビットとキャリー１ビットに基づき部
分剰余上位３桁を生成する。QSL1009はREM1011からの部
分剰余上位３桁と、CSA1008からの和１ビットとキャリ
ー１ビットに基づき部分剰余上位４桁を生成し、これに
より商デジットを求める。REL1010は、REM1011からの部
分剰余上位３桁とCSA1008からの和１ビットとキャリー
１ビットに基づき部分剰余上位４桁を生成し、これと除
数/部分開平値１桁とQSL1009からの商デジットにより部
分剰余上位２桁の予測値を求める。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、SRT法を用いた除
算/開平器に係り、特に、演算の高速化と回路の小規模
化を図った除算器、並びに、演算の高速化と除算器との
回路の共通化が可能な開平器に関する。

【０００２】

【従来の技術】SRT法により除算、開平は以下の手順で
計算される。図１(a)にSRT法による除算、図１(b)にSRT
法による開平演算の処理フローを示す。除算について
は、まず部分剰余に被除数Xが代入される。部分剰余を
参照し、商デジット選択回路101によって商デジットが
選択される。商デジットは-1,0,1のいずれかで、部分剰
余は選択された商デジットの値に応じて除数Dとの部分
剰余計算103が行われる。商デジットが-1，1のとき、そ
れぞれ部分剰余Rと除数Dとの加算、減算を行い、その結
果を1ビット右シフトして次ステップの部分剰余R'とす
る。商デジットが0のとき、部分剰余と0との加算を行
い、その結果を1ビット右シフトして次ステップの部分
剰余R'とする。並行して商デジット値-1を含まない商へ
の変換、すなわち商計算102が行われる。部分剰余計算
に用いられる加算器は桁上げ保存加算器(Carry Save Ad
der:CSA)である。求められた部分剰余上位数ビットに対
して桁上げ伝搬加算(Carry PropagationAdder:CPA)104
を行い、次ステップの商デジット選択回路の入力とす
る。桁上げ伝搬のビット数は商デジット選択規則により
異なるが、通常3〜4ビットである。上記動作を繰り返す
ことで商が求められる。

【０００３】開平演算については、除数Dの代りに部分
開平値を用いて部分剰余計算107が行われる。開平演算
では部分開平値計算回路106で部分開平値が求まってか
ら部分剰余計算を行う。除算では商計算と部分剰余計算
を同時に行うのに対し、開平演算では部分開平値が求ま
ってから部分剰余計算を行う。図１(b)では省略してい
るが、除算の商計算と同様に、開平値を求める開平計算
と部分剰余計算は同時に行うものとする。尚、以後、開
平演算における除算の商、除数をそれぞれ開平値、部分
開平値と呼び、区別する。SRT開平回路は部分開平値を
求める回路を付加すればSRT除算回路と共通化できる。
開平演算の商デジット選択回路105で求められる開平値
デジットは、以後、除算と同じ商デジットと呼ぶことに
する。

【０００４】次に、文献(William M. McAllister, Dan
Zurus, "An NMOS 64b Floating-Point Chip Set", Proc
eeding of the ISSCC 86, February 1986，G.Matsubara
et.al.,“30-ns 55-b Shared Radix 2 Division and S
quare Root Using a Self-Timed Circuit”,Proceeding
of the 12th IEEE Computer Arithmetic Symp.,July19
95)を参考にして従来例を説明する。図２に従来例にお
けるSRT除算処理フローを示す。図１(a)の処理フローで
は商デジットが選択された後、その商デジットq(1,0,-
1)に従ってCSAによる部分剰余と除数Dの加減算(-D,0,+
D)が行われる。そしてCPAによる部分剰余の桁上げ伝搬
が行われる。図２の処理フローでは商デジットの選択結
果を得る前に、部分剰余と除数(-D,0,+D)の加減算202と
部分剰余の桁上げ伝搬203をすべて同時に計算させてお
く。得られた商デジットq(1,0,-1)の結果から一つの部
分剰余を選択する。商デジット選択と部分剰余計算を並
列化することで大幅に性能が向上する。

【０００５】

【発明が解決しようとする課題】図２のSRT除算処理フ
ローに従った回路を構成すると、図１(a)の処理フロー
に従った回路に対し高速に演算することが可能である
が、商デジットパターン(-1,0,1)に相当する数のCSAとC
PAを持つことになるので回路規模が大きいことが問題で
ある。本発明の目的はSRT除算において図１のSRT除算処
理フローに対し高速化を達成しつつ、図２に対して回路
規模を削減することにある。さらに本発明の他の目的
は、SRT開平演算においてもSRT除算と共通の回路を用い
て回路規模を削減し、かつ除算と同等の処理時間で演算
することである。

【０００６】

【課題を解決するための手段】上記目的を達成するた
め、本発明は、計算機システムのＳＲＴ方式による基数
２の除算・開平演算器において、部分剰余計算を行う桁
上げ保存加算手段と、部分剰余上位桁決定手段と、商デ
ジット選択手段と、部分剰余上位桁予測手段を備え、前
記部分剰余上位桁決定手段は、前記部分剰余上位桁予測
手段から出力される部分剰余上位２桁と、前記桁上げ保
存加算手段から出力される和１ビットとキャリー１ビッ
トに基づき部分剰余上位３桁を生成し、前記商デジット
選択手段は、前記部分剰余上位桁決定手段から出力され
る部分剰余上位３桁と、前記桁上げ保存加算手段から出
力される和１ビットとキャリー１ビットに基づき部分剰
余上位４桁を生成し、該生成した部分剰余上位４桁に基
づき商デジットを求め、出力し、前記部分剰余上位桁予
測手段は、前記部分剰余上位桁決定手段から出力される
部分剰余上位３桁と前記桁上げ保存加算手段から出力さ
れる和１ビットとキャリー１ビットに基づき部分剰余上
位４桁を生成し、該生成した部分剰余上位４桁と、除数
または部分開平値１桁と、商デジット選択手段からの商
デジットに基づき部分剰余上位２桁の予測値を求め、出
力するようにしている。

【０００７】また、計算機システムのＳＲＴ方式による
基数２の除算・開平演算器において、部分剰余計算を行
う桁上げ保存加算手段と、部分剰余上位桁決定手段と、
商デジット選択手段と、部分剰余上位桁予測手段を備
え、前記部分剰余上位桁決定手段は、前記部分剰余上位
桁予測手段から出力される部分剰余上位２桁と、前記桁
上げ保存加算手段から出力される和１ビットとキャリー
１ビットに基づき部分剰余上位３桁を生成し、前記商デ
ジット選択手段は、前記部分剰余上位桁決定手段から出
力される部分剰余上位３桁と、前記桁上げ保存加算手段
から出力される和１ビットとキャリー１ビットに基づき
部分剰余上位４桁を生成し、該生成した部分剰余上位４
桁に基づき商デジットを求め、出力し、前記部分剰余上
位桁予測手段は、前記部分剰余上位桁決定手段から出力
される部分剰余上位３桁と前記桁上げ保存加算手段から
出力される和１ビットとキャリー１ビットに基づき部分
剰余上位４桁を生成し、該生成した部分剰余上位４桁
と、除数または部分開平値１桁に基づき部分剰余上位２
桁の予測値を求め、出力し、前記商デジット選択手段と
前記部分剰余上位桁予測手段は、それぞれの処理を並行
して実行するようにしている。

【０００８】また、開平演算における商デジット１桁ま
でを定めて初期値設定する手段を設けるようにしてい
る。また、開平演算における商デジット２桁までを定め
て初期値設定する手段を設けるようにしている。また、
前記部分剰余計算を行う桁上げ保存加算手段と、前記部
分剰余上位桁決定手段と、前記商デジット選択手段と、
前記部分剰余上位桁予測手段からなるステージを複数ス
テージ設け、１サイクルに複数桁の商デジットを決定す
るようにしている。

【０００９】

【発明の実施の形態】まず、本発明におけるSRT除算処
理フローおよびSRT開平演算処理フローについて、その
概略を説明する。図３のSRT除算処理フローは、図１のS
RT除算処理フローの場合より高速になり、図２のSRT除
算処理フローの場合より回路規模を削減する。商デジッ
ト選択回路302で商デジットが選択され、その商デジッ
トに従って、CSAによる除数Dとの部分剰余計算304と商
計算305を行う。部分剰余上位桁予測回路303は次ステッ
プの部分剰余上位数ビットを予測するもので、部分剰余
と除数を入力とし、商デジット選択回路と並行して計算
される。CSA 304 による部分剰余計算の結果と部分剰余
上位桁予測回路303による予測の部分剰余から部分剰余
上位桁決定回路301において次ステップの上位桁の部分
剰余が決定され、商デジット選択回路と部分剰余上位桁
予測回路の入力となる。以後上記動作を繰り返す。

【００１０】図１のSRT除算処理フローに対する高速化
は以下の点である。すなわち、商デジット選択回路で商
デジットを選択すると同時に、部分剰余予測回路では部
分剰余を一部予測する。部分剰余決定回路は部分剰余予
測回路で予測した部分剰余に対し、CSAの出力により該
部分剰余を補正する回路であり、同ビット数のCPAより
高速である。つまり、図３のSRT除算処理フローは、図
１のSRT除算処理フローに対して商デジット選択102と部
分剰余計算103を同時に計算していることになる。

【００１１】図２のSRT除算処理フローに対する回路規
模の削減は以下の点である。すなわち、図２では、部分
剰余計算を行うCSA 202と桁上げ伝搬を行うCPA 203が３
組必要であったが、図３では、部分剰余上位桁決定回路
301、部分剰余上位桁予測回路303、部分剰余計算回路30
4は１組あればよい。つまり、図２では基数での商デジ
ットパターン数に相当するCSA，CPAが必要である。例え
ば、基数2{-1,0,1}では3組のCSA，CPAが必要であり、基
数4{-2,-1,0,1,2}では5組のCSA，CPAを用いる。ところ
が、図３では必要となるCSA,CPAの数は商デジットパタ
ーン数には依存しないため、図２に対し回路規模の削減
が可能である。

【００１２】SRT開平演算処理フローは、図４の構成と
なる。SRT開平演算では除数の代わりに部分開平値を用
いる。除数は商デジットに対して不変であるが部分開平
値は商デジットにより変化する。このため部分開平値計
算回路404は商デジット選択403により選択された商デジ
ット値に従って部分開平値計算を行う。部分剰余上位桁
予測回路405は部分開平値の特定ビットを参照するた
め、部分開平値計算結果が出るまで待たなければならな
い。そこで開平初期値設定回路401で開平演算の部分剰
余初期値を適当な値に設定することにより、部分剰余上
位桁予測回路405において上記部分開平値の特定ビット
は商デジットに非依存の一定値となる。従って、除算と
同様に商デジット選択と並行して部分剰余上位桁予測演
算を行うことができる。上記以外は除算と同様のフロー
で計算される。

【００１３】次に、本発明で用いるSRT除算、SRT開平演
算のアルゴリズムを説明する。SRT法では、部分剰余を
桁上げ保存加算器(Carry Save Adder : CSA)で演算し、
キャリーセーブフォーマット (Carry Save Format)で結
果を保持する。図５に桁上げ保存加算器の構成図を示
す。部分剰余Rは和si(Sum)とキャリーci(Carry)で記述
され、二つの和{0,1,2}として表わされる。除数/部分開
平値diとの和si'とキャリーci'を各桁で独立に計算す
る。桁上げ保存回路は1ビットの全加算器と等しい。

【００１４】図６に部分剰余R、 除数/部分開平値D、
商/開平値Qの各ビット名称を示す（“/”は“または”
を表わす）。本発明では浮動小数点除算・開平演算の仮
数部について述べる。左端のビットは符号ビットであ
る。si，ciは、それぞれキャリーセーブフォーマットの
和、キャリーである。部分剰余Rにおいて、r-1, r0, r1
以外はキャリーセーブフォーマットである。例えば、r2
は(s2, c2)、 r3は(s3, c3)により表わされる。除数/部
分開平値D, 商/開平値Qは符号が正であることからd-1=
0, q-1=0に固定である。更に除数/部分開平値Dは［1/2,
1) (“［1/2, 1)”は“1/2 <= D <1”と等しい)である
ためd0=0である。以後、部分剰余R, 除数/部分開平値D,
商/開平値Qは図６の表記を用いる。

【００１５】除算と開平演算の部分剰余は数１のように
表わされる。

【００１６】

【数１】

【００１７】開平演算は除算における除数Dを部分開平
値Qi+(qi+1×2^-(i+2)) (「^」はべき乗を表わす)で置
き換えることにより除算と同様の演算となり、回路の共
通化が行える。開平演算の部分開平値Di+2は除算の除数
Dに相当するもので、開平値Qiと区別して扱う。数１で
の×2乗算は左1ビットシフトにより行う。SRT法では、
部分剰余は上位数ビットのみ桁上げ伝搬が行われ、その
部分剰余の値から商デジットが選択される。商デジット
選択論理は様々なものがあるが、本発明では上位3ビッ
トの部分剰余とキャリーセーブフォーマットの４ビット
目の和とキャリーにより商デジットを選択するものとす
る。数１より各ステップで部分剰余と商デジットが求ま
っていく。全ステップが終了すると、商/開平値が得ら
れる。商デジットには-1を含むので、商/開平値，部分
開平値は-1を含まない0,1のみの数に変換する必要があ
るが、演算終了後に変換するのではなく、商デジットが
求まる度にOn-the-flyで変換する。On-the-fly変換とは
Qi(positive)とQi-2^-i (negative)の二進表現を保持し
ておき商デジット-1を桁伝搬せずに変換させる方式であ
る。開平演算はOn-the-flyで変換された部分開平値を用
いて部分剰余を求める点が、除数を用いる除算と異な
る。初期値はi=0のときR0=X(被除数/被開平値)，q0=1
(除算)，q0=0，q1=1(開平)である。除算では被除数Xは
［1/2, 1)、除数Dは［1/2,1)と正規化されている。開平
演算では被開平値Xは［1/4,1)とする。開平値は指数部
が偶数となるよう仮数部を1ビットシフトして調整す
る。

【００１８】本発明では次ステップの部分剰余の上位2
ビットを予測するのが特徴である。部分剰余上位桁予測
表に従って上位桁の予測を行うが、以下に部分剰余上位
桁予測表の作成方法を示す。4ビットの部分剰余Rと除数
/部分開平値Dから商デジットqと次ステップの部分剰余
上位2ビットを求める対応表を図７に示す。図７は部分
剰余Rの上位4ビット(r-1, r0, r1, r2)、除数/部分開平
値Dを入力とし、次ステップの部分剰余上位3ビット(r-
1', r0', r1')を出力する。＃は１または2のいづれか、
％は0または1のいづれかを示す。部分剰余Rの桁上げ伝
搬は商デジットを決めるのに最低限必要な上位3ビット
(r-1, r0, r1)のみ行っている。4ビット目r2はキャリー
セーブフォーマットである。除数/部分開平値Dの範囲は
条件より［1/2,1)で、上から4ビット目のd2(小数点第二
位)のみ参照している。

【００１９】図７の作成法の例を図８に示す。図８は部
分剰余Rが1102の場合である。商デジットq=-1なので数
１より、図示のように除数/部分開平値Dと部分剰余Rと
の和をとり、更に３ビット桁上げ伝搬と1ビット左シフ
トを行うと、図８より除数/部分開平値Dが0011*、0010*
のときそれぞれ00#、00%となる。*はドントケアであ
る。例として、(1.1)は次のようにして次ステップの部
分剰余を定める。部分剰余Rは1102*、除数/部分開平値D
は0011*なので、(1.1)ではそれぞれR=11020，D=00110と
した。部分剰余Rと除数/部分開平値Dの桁上げ保存加算
を行うと、キャリーセーブフォーマットではS=11110，C
=00100となる（Cの空欄は0とした)。キャリーセーブフ
ォーマットのS，Cに対し、上位3ビット桁上げ伝搬と1ビ
ット左シフトを行うと、次ステップの部分剰余は001と
なる。同様に(1.2)の結果は002なので、(1.1)，(1.2)よ
り、除数/部分開平値Dが0011*のとき次ステップの部分
剰余は00#となる。(2.1)、(2.2)より除数/部分開平値D
が0010*のとき次ステップの部分剰余は00%となる。同様
にして部分剰余Rの4ビット全ての組み合わせについて行
えば、図７が得られる。

【００２０】図７から図９の商選択/部分剰余上位桁予
測表が得られる。図９では部分剰余上位4ビット(r-1,r
0,r1,r2)、除数/部分開平値上位4ビット目d2を入力と
し、商デジットq(qabs, qsign)、次ステップの部分剰余
上位2ビット(r-1', r0')を出力する。ここでの次ステッ
プの部分剰余は図７の3ビットのうち確定している上位2
ビットとし、既に桁上げ伝搬が行われているものであ
る。計算機シミュレーションの結果から、部分剰余の上
位3ビットがr-1=1，r0=0，r1=0となる確率が0%であった
ため、商デジットq、次ステップの部分剰余r-1，r0をド
ントケアとした。図９の商選択/部分剰余上位桁予測表
を用いると、部分剰余と除数/部分開平値から商デジッ
トと次ステップの部分剰余上位2ビットを予測すること
ができる。図９の商選択/部分剰余上位桁予測表は、該
表に基づいて論理合成することもしくは、該表をメモリ
にマッピングすることにより実現される。

【００２１】次に、本発明の第一の実施例の全体構成図
を図１０に示す。本実施例の除算開平演算器は、部分剰
余和レジスタ1001、部分剰余キャリーレジスタ1002、部
分剰余上位桁レジスタ1003、positionレジスタ1004、po
sitiveレジスタ1005、negativeレジスタ1006、除数レジ
スタ1007、部分剰余計算回路CSA 1008、商デジット選択
回路QSL 1009、部分剰余上位桁予測回路REL 1010、部分
剰余上位桁決定回路REM 1011、開平初期値設定回路SRI
1012、商/開平値生成回路OQD 1013、除数/部分開平値生
成回路DSF 1014から構成されている。本発明では開平初
期値設定回路SRIについては二つの実施例を挙げる。開
平初期値設定回路SRI第一の実施例を用いた全体構成図
が図１０である。部分剰余和レジスタ1001、部分剰余キ
ャリーレジスタ1002は、部分剰余におけるキャリーセー
ブフォーマットの和成分、キャリー成分を保持する。部
分剰余上位桁レジスタ1003は、部分剰余上位桁予測回路
の出力である2ビットの部分剰余を保持する。position
レジスタ1004、positiveレジスタ1005、negativeレジス
タ1006は、それぞれ計算しているビット位置、そのposi
tion値での商/開平値のpositive値、negative値を保持
する。除数レジスタ1007は、除数を保持する。部分剰余
計算回路CSAでは、部分剰余の和成分、キャリー成分の
加算を行う。商デジット選択回路QSL(Quotient Selecti
on Logic)では、図９の商選択/部分剰余上位桁予測表に
従って商デジット選択を行う。部分剰余上位桁予測回路
REL(Remainder Expectation Logic)では、図９の商選択
/部分剰余上位桁予測表に従って部分剰余上位2ビットを
予測する。部分剰余上位桁決定回路REM(REMainder uppe
r)では、予測した部分剰余上位２ビットとCSAの出力か
ら部分剰余上位3ビットを決定する。商/開平値生成回路
OQD(On-the-fly Quotient Decoder)は、商デジット選択
回路QSL出力の商デジットからOn-the-fly変換により商/
開平値を生成する。除数/部分開平値生成回路DSF(Divid
er Square root Formation)では、部分剰余計算回路CSA
の入力となる除数/部分開平値を生成する。商/開平値、
部分開平値は、position値、 positive値、negative値
から計算される。開平初期値設定回路SRI(Square Root
Initialization)では、開平演算で商デジット選択回路Q
SLを用いるための開平演算の初期値を設定する。

【００２２】次に本発明の実施例の個別ブロックの説明
に移る。部分剰余計算回路CSAは図５の各ビットの桁上
げ保存回路により実現される。部分剰余上位桁決定回路
REM(REMainder Upper)では、予測した2ビットの部分剰
余(r-1, r0)とCSAの和(sum)1ビット、キャリー(carry)1
ビットを入力とし3ビットの部分剰余(r-1',r0',r1')を
生成する。部分剰余上位桁決定回路REMの構成図を図１
１に示す。図１１から明らかなように3ビットのCPA(Car
ry Propagation Adder)に比べ、回路規模は小さくかつ
高速に演算できる。なお、図に示されたMUX(multiplexe
r)の動作を図の左側のMUXを例にとり説明すると、sum,c
arryを入力とするANDゲートの出力が“１”のときは、M
UXは、r-1,r0を入力とするEXORの出力を選択し、“０”
のときは、MUXは、r-1を選択する。以降の図においても
同様である。

【００２３】商/開平値生成回路OQDは商デジットのOn-t
he-fly変換を行い、商/開平値を定める。商/開平値生成
回路OQDの構成図を図１２に示す。(a)はpositive値Mi、
negative値Niを用いた計算方法である。商デジットが求
まる度に逐次Mi、Niを求めていく。position値Piを用い
るとMi，Niは(b)のように表される。(b)をもとにした構
成図が(c)である。Pi［n］，Mi［n］，Ni［n］はそれぞ
れiステップのnビット目のposition値、positive値、ne
gative値を表す。商デジット選択回路QSLにより定まる
商デジットqのqsign, qabsをマルチプレクサの選択信号
とする。

【００２４】部分剰余を計算するために除数/部分開平
値を計算する回路が除数/部分開平値生成回路DSF(Divid
er Square root Formation)である。除数/部分開平値生
成回路DSFの構成図を図１３に示す。まず、除算に関し
ては、商デジットq=-1のときは部分剰余 Rと除数Dを加
算するため、Dを出力する。q=0のときは0を加算するた
め、商デジットqのqabsとのアンドをとり0を出力する。
q=1のときは-Dを加算するために除数Dの反転 ~Dを出力
する。-Dの加算は2の補数による演算なのでCSAの末尾に
キャリー信号を与える。開平演算では、q=0のときは除
算と同様に0を出力するが、q=-1，１では除数D，反転 ~
Dの代わりにそれぞれMi+2^-(i+2) ，Ni+2^-(i+1)+2^-(i
+2) を選択する。これらは商/開平値生成回路OQDのposi
tion、positive、negative信号により生成される。ここ
で、sqrt:1，div:0は、開平のときは１が入力され、除
算のときは０が入力されることを示す。

【００２５】商デジット選択回路QSLは商デジットqを選
択する回路である。桁上げ伝搬された部分剰余3ビット
と4ビット目のキャリーセーブフォーマットのsum，carr
yを入力とし、図９の商選択/部分剰余上位桁予測表に従
って商デジットを選択する。商デジット選択回路QSLは
図９の商選択/部分剰余上位桁予測表に基づいて論理合
成することにより実現される。商デジットは三種(-1，
０，１)で2ビットで表現する。qabs=1，qsign=0のとき
商デジット-1、 qabs=0，qsign=0のとき商デジット0、q
abs=1，qsign=1のとき商デジット1である。除数/部分開
平値Dが［1/2,1)の範囲でなければならない。

【００２６】部分剰余上位桁予測回路RELは次ステップ
の部分剰余上位桁を予測する回路である。桁上げ伝搬さ
れた部分剰余3ビットと4ビット目のキャリーセーブフォ
ーマットのsum，carry、除数/部分開平値d2ビットを入
力とし、図９の商選択/部分剰余上位桁予測表に従っ
て、次ステップの部分剰余上位2ビット(r-1,r0)を予測
する。部分剰余上位桁予測回路RELは、図９の商選択/部
分剰余上位桁予測表に基づいて論理合成することにより
実現される。商デジット選択回路と同様に、除数/部分
開平値Dが［1/2,1)の範囲でなければならない。また、
部分剰余上位桁予測回路RELは同期回路だけではなく、
非同期回路にも使用することができる。

【００２７】開平初期値設定回路SRIは開平演算の初期
部分剰余を定めるブロックである。先に述べたように、
開平演算では、除算の除数Dを部分開平値で置き換える
必要がある。商デジット選択回路QSL、部分剰余上位桁
予測回路RELではDの範囲が［1/2,1)であることが前提条
件なので、部分開平値が［1/2,1)を満たすよう開平初期
値設定回路SRIで初期値を定める。開平初期値設定回路S
RIには二つの実施例がある。第一の実施例では部分開平
値Dの範囲が［1/2,1)となるよう開平の部分剰余初期値
を定める。第二の実施例では部分開平値Dの範囲が［1/
2,1)であるだけでなく、部分剰余上位桁予測回路RELに
おいて参照する部分開平値d2ビットを定数にするよう開
平の部分剰余初期値を定める。

【００２８】図１０の本発明の第一の実施例は開平初期
値設定回路SRIの第一の実施例を用いたものである。図
１０の部分剰余上位桁予測回路RELにおいて参照する部
分開平値d2ビットは商デジットによって変わるので、商
デジットの結果に従って除数/部分開平値生成回路DSF出
力の部分開平値から得られる。従って、図１０では、商
デジット選択(QSL)→部分開平値生成(DSF)→部分剰余上
位桁予測(REL)の順に演算が行われる。第一の実施例で
は以下に示す数2のように開平値Q1を定める。

【００２９】

【数２】

【００３０】商デジットq0=0, q1=1、開平値Q0=0とする
と、開平値Q1=0.1である。開平値Qの範囲は［1/2,1)な
のでq2は1または0である。このときD3=Q1+q2×2^-3より
［1/2,1)を満たすので、商デジット選択回路QSL、部分
剰余上位桁予測回路RELで演算を行うことができる。そ
こで開平初期値設定回路SRIでは商デジットq0=0, q1=
1、開平値Q0=0となるよう初期部分剰余R1を定める。部
分剰余初期値R1を数３に示す。

【００３１】

【数３】

【００３２】第一の実施例ではR1 を部分剰余初期値と
して計算する。図１４(a)に開平初期値設定回路SRIでの
計算方法、(b)SRI回路の構成図を示す。被開平値Xの範
囲は［1/4,1)よりXは00.11*，00.10*，00.01*(*はドン
トケア)のいずれかである。このXに対し数３により求ま
るR1はそれぞれ01.0*, 00.1*, 00.0*となる。

【００３３】ドントケア部は不変である。図１４(a)は
上記アルゴリズムを真理値表にしたものである。(b)は
(a)の真理値表をもとにした構成図である。図１４では
データ幅を54ビットとした。ここで、［54:0］は0ビッ
ト目〜54ビット目を意味し、［54］は54ビット目を意味
する。(b)の構成図において、MUXの右側の入力は、0〜5
3ビット目の54ビット入力であり、左側の入力は、0〜51
ビット目の最下位桁の０ビット目のさらに下位に0を入
れ（1'b0は１ビットの0を表わす）、最上位桁の51ビッ
ト目のさらに上位にout［0］を入れ54ビットとしたもの
である。このことは、後述の図１５についても同様であ
る。

【００３４】次に第二の実施例を示す。部分剰余上位桁
予測回路RELでは除数/部分開平値Dのd2ビットを参照す
るが、第二の実施例での開平初期値設定回路SRIではd2
ビットを商デジットに依存せず定数にすることができる
ので、部分剰余上位桁予測回路と商デジット選択回路を
並行して実行できる。第二の実施例での開平初期値設定
回路SRIの部分剰余Rを数４に示す。

【００３５】

【数４】

【００３６】第二の実施例では、部分開平値のd2を一定
値にするためにR2を部分剰余初期値として計算する。開
平値Qの範囲は［1/2,1)なので商デジットq0=0， q1=1，
q2=0または1である。D4=Q2+q3×2^-4より、商デジットq
2と部分開平値のd2ビットは等しい。開平の部分剰余R2<
0では商デジットq3が-1となるので、q2すなわちd2信号
が変化する。開平の部分剰余R2>=0とすると、商デジッ
トq3は1または0であり、q2すなわちd2信号は変化しな
い。R3以降はd2信号に影響を与えないので、R2>=0を満
たすよう部分剰余の初期化を行う。第二の実施例ではR2
を部分剰余初期値として計算する。図１５(a)に開平初
期値設定回路SRIでの計算方法、(b)SRI回路の構成図を
示す。［1/4,1)を満たす被開平値Xに対し、R2>=0となる
ようにq2，d2を定める。図１５(a)は上記アルゴリズム
を真理値表にしたものである。(b)は(a)の真理値表をも
とにした構成図である。

【００３７】部分剰余上位桁予測回路RELは開平初期値
設定回路SRIの第一、第二の実施例では以下のように構
成が異なる。第一の実施例では図１０のように除数/部
分開平値生成回路DSFからの出力である除数/部分開平値
d2ビットを参照する。除算では除数D、開平演算ではq=+
1のときMi+2^-(i+2) 、 q=-1のときNi+2^-(i+1)+2^-(i+
2) の小数点第2位をd2とする。QSLの真理値表よりq=0の
ときはd2はドントケアとなるのでq=-1と同様の値をd2と
する。ここで、q=+1には2^-(i+2) 項、q=-1には2^-(i+
1)+2^-(i+2) 項があるがd2に影響を与えないため、商/
開平値生成回路OQD出力のpositive(Mi)，negative(Ni)
の小数点第2位をd2としてもよい。

【００３８】第二の実施例では、d2が商デジット非依存
の定数となるため、除数/部分開平値生成回路DSFの出力
は不要となる。更に、商デジットを参照しないことから
商デジット選択回路QSLと平行して実行することができ
高速化がはかれる。演算終了後は、部分剰余は和とキャ
リーの形で保持されているので、丸めの計算のためには
和とキャリーを加算しなければならない。ビット長のCP
Aが必要となるが、除算/開平器の中に持たせるか、ある
いは他のモジュール(例えばMACモジュール)と共通化し
て持たさなければならない。また、指数部演算回路、正
規化回路、丸め回路に関しても別に回路を持つ必要があ
る。なお、開平初期値設定回路SRIは同期回路だけでは
なく、非同期回路にも使用することができる。

【００３９】本発明の第二の実施例の全体構成図を図１
６に示す。本実施例の除算開平演算器は、部分剰余和レ
ジスタ1601、部分剰余キャリーレジスタ1602、部分剰余
上位桁レジスタ1603、positionレジスタ1604、positive
レジスタ1605、negativeレジスタ1606、除数レジスタ16
07、部分剰余計算回路CSA 1608、商デジット選択回路QS
L 1609、部分剰余上位桁予測回路REL 1610、部分剰余上
位桁決定回路REM 1611、開平初期値設定回路SRI 1612、
商/開平値生成回路OQD 1613、除数/部分開平値生成回路
DSF 1614から構成されている。本実施例では開平初期値
設定回路SRIの第二の実施例を用いている。部分剰余上
位桁予測回路RELは、商デジット選択回路QSLの商デジッ
トを参照せずに部分剰余上位桁を予測するので、商デジ
ット選択回路QSLと同時に独立して演算を行うことがで
きる。他のブロックは第一の実施例と同じブロックで同
じ機能を有する。第一、第二の実施例では1ステージ構
成であったが、複数ステージ構成とし、1サイクルに複
数桁の商デジットを決定することが可能である。

【００４０】第三の実施例は第二の実施例を複数ステー
ジ構成にしたものである。第三の実施例の全体構成図を
図１７に示す。第一、第二の実施例では1ステージ構成
であったが、本実施例では、3ステージ構成とし、1サイ
クルに３bitの商デジットを決定する。全てのレジスタ
と開平初期値設定回路SRIはステージ数に無関係に一
つ、他のブロックはステージ数だけ必要となる。

【００４１】

【発明の効果】本発明の部分剰余上位桁予測回路RELに
より、商パターン三種 (-1,0,1)についてそれぞれ演算
器を持つオーバーラップ方式に対して演算時間を増やす
こと無く回路規模を削減できる。本発明の開平初期値設
定回路SRIを用いることで開平演算にも部分剰余上位桁
予測回路RELが使用でき、除算器と回路の共通化ができ
る。開平初期値設定回路SRIの第一の実施例では部分剰
余上位桁予測回路RELは商デジット選択回路QSLと並行し
て実行できないが、開平初期値設定回路SRIの第二の実
施例を用いると部分剰余上位桁予測回路RELは商デジッ
ト選択回路QSLと並行して実行できるため、除算器と共
通の回路を用いながら同程度の時間で開平演算が可能で
あり、正確には、開平演算は開平初期値設定回路SRIで
予め商デジットを求めているため、除算より短いステッ
プ数で結果を求めることができる。本発明は単精度、倍
精度双方で演算が可能である。部分剰余上位桁レジスタ
を除く全てのレジスタ、部分剰余計算回路CSA、開平初
期値設定回路SRI、商/開平値生成回路OQD、除数/部分開
平値生成回路DSFは倍精度のビット幅を持ち、単精度演
算ではそれぞれの回路で上位桁から必要な桁数のみ（下
位側はドントケアとする）で演算する。本発明の部分剰
余上位桁予測回路REL、開平初期値設定回路SRIは同期回
路だけでなく、非同期回路にも適用可能である。

【図面の簡単な説明】

【図１】SRT除算/SRT開平演算処理フローを示す図であ
る。

【図２】SRT除算の第一の従来例を示す図である。

【図３】部分剰余桁上げ予測を行うSRT除算の例を示す
図である。

【図４】部分剰余桁上げ予測を行うSRT開平演算の例を
示す図である。

【図５】桁上げ保存加算器CSAの構成図である。

【図６】部分剰余、除数/部分開平値、商/開平値のビッ
ト名称を示す図である。

【図７】部分剰余、除数/部分開平値対応表を示す図で
ある。

【図８】部分剰余、除数/部分開平値対応表(図７)作成
の例を示す図である。

【図９】商選択/部分剰余上位桁予測表を示す図であ
る。

【図１０】本発明第一の実施例の全体構成図である。

【図１１】部分剰余上位桁決定回路REM回路を示す図で
ある。

【図１２】商/開平値生成回路OQD回路を示す図である。

【図１３】除数/部分開平値生成回路DSF回路を示す図で
ある。

【図１４】開平初期値設定回路SRI回路の第一の実施例
を示す図である。

【図１５】開平初期値設定回路SRI回路の第二の実施例
を示す図である。

【図１６】本発明第二の実施例の全体構成図である。

【図１７】本発明第三の実施例の全体構成図である。

【符号の説明】

１００１、１６０１ 部分剰余和レジスタ １００２、１６０２ 部分剰余キャリーレジスタ １００３、１６０３ 部分剰余上位桁レジスタ １００４、１６０４ positionレジスタ １００５、１６０５ positiveレジスタ １００６、１６０６ negativeレジスタ １００７、１６０７ 除数レジスタ １００８、１６０８ 部分剰余計算回路 １００９、１６０９ 商デジット選択回路 １０１０、１６１０ 部分剰余上位桁予測回路 １０１１、１６１１ 部分剰余上位桁決定回路 １０１２、１６１２ 開平初期値設定回路 １０１３、１６１３ 商/開平値生成回路 １０１４、１６１４ 除数/部分開平値生成回路

───────────────────────────────────────────────────── フロントページの続き (72)発明者 戸塚 米太郎 東京都国分寺市東恋ケ窪一丁目280番地 株式会社日立製作所中央研究所内

Claims (5)

【特許請求の範囲】
1. 【請求項１】 計算機システムのＳＲＴ方式による基数
   ２の除算・開平演算器において、 部分剰余計算を行う桁上げ保存加算手段と、 部分剰余上位桁決定手段と、 商デジット選択手段と、 部分剰余上位桁予測手段を備え、 前記部分剰余上位桁決定手段は、前記部分剰余上位桁予
   測手段から出力される部分剰余上位２桁と、前記桁上げ
   保存加算手段から出力される和１ビットとキャリー１ビ
   ットに基づき部分剰余上位３桁を生成し、 前記商デジット選択手段は、前記部分剰余上位桁決定手
   段から出力される部分剰余上位３桁と、前記桁上げ保存
   加算手段から出力される和１ビットとキャリー１ビット
   に基づき部分剰余上位４桁を生成し、該生成した部分剰
   余上位４桁に基づき商デジットを求め、出力し、 前記部分剰余上位桁予測手段は、前記部分剰余上位桁決
   定手段から出力される部分剰余上位３桁と前記桁上げ保
   存加算手段から出力される和１ビットとキャリー１ビッ
   トに基づき部分剰余上位４桁を生成し、該生成した部分
   剰余上位４桁と、除数または部分開平値１桁と、商デジ
   ット選択手段からの商デジットに基づき部分剰余上位２
   桁の予測値を求め、出力することを特徴とする除算・開
   平演算器。
2. 【請求項２】 計算機システムのＳＲＴ方式による基数
   ２の除算・開平演算器において、 部分剰余計算を行う桁上げ保存加算手段と、 部分剰余上位桁決定手段と、 商デジット選択手段と、 部分剰余上位桁予測手段を備え、 前記部分剰余上位桁決定手段は、前記部分剰余上位桁予
   測手段から出力される部分剰余上位２桁と、前記桁上げ
   保存加算手段から出力される和１ビットとキャリー１ビ
   ットに基づき部分剰余上位３桁を生成し、 前記商デジット選択手段は、前記部分剰余上位桁決定手
   段から出力される部分剰余上位３桁と、前記桁上げ保存
   加算手段から出力される和１ビットとキャリー１ビット
   に基づき部分剰余上位４桁を生成し、該生成した部分剰
   余上位４桁に基づき商デジットを求め、出力し、 前記部分剰余上位桁予測手段は、前記部分剰余上位桁決
   定手段から出力される部分剰余上位３桁と前記桁上げ保
   存加算手段から出力される和１ビットとキャリー１ビッ
   トに基づき部分剰余上位４桁を生成し、該生成した部分
   剰余上位４桁と、除数または部分開平値１桁に基づき部
   分剰余上位２桁の予測値を求め、出力し、 前記商デジット選択手段と前記部分剰余上位桁予測手段
   は、それぞれの処理を並行して実行することを特徴とす
   る除算・開平演算器。
3. 【請求項３】 請求項１記載の除算・開平演算器におい
   て、 開平演算における商デジット１桁までを定めて初期値設
   定する手段を設けることを特徴とする除算・開平演算
   器。
4. 【請求項４】 請求項２記載の除算・開平演算器におい
   て、 開平演算における商デジット２桁までを定めて初期値設
   定する手段を設けることを特徴とする除算・開平演算
   器。
5. 【請求項５】 請求項３または請求項４記載の除算・開
   平演算器において、 前記部分剰余計算を行う桁上げ保存加算手段と、前記部
   分剰余上位桁決定手段と、前記商デジット選択手段と、
   前記部分剰余上位桁予測手段からなるステージを複数ス
   テージ設け、 １サイクルに複数桁の商デジットを決定することを特徴
   とする除算・開平演算器。