演算回路および演算処理装置ならびに演算処理方法
【課題】誤動作を確実に検出する。
【解決手段】前処理回路2は、演算対象となる数値をレジスタ1に格納する。解予測回路3は、レジスタに数値が格納されるごとに、レジスタ1に格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。中間値計算回路4は、解予測回路3で予測された部分解を用いた所定の演算により、中間値を示す数値を生成し、中間値に対して符号拡張により拡張符号ビットを付加した数値をレジスタに格納する。解生成回路5は、解予測回路3で予測された部分解を順次取得し、解を生成する。エラー検出回路6は、レジスタに格納された中間値の符号ビットと、拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。
【解決手段】前処理回路2は、演算対象となる数値をレジスタ1に格納する。解予測回路3は、レジスタに数値が格納されるごとに、レジスタ1に格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。中間値計算回路4は、解予測回路3で予測された部分解を用いた所定の演算により、中間値を示す数値を生成し、中間値に対して符号拡張により拡張符号ビットを付加した数値をレジスタに格納する。解生成回路5は、解予測回路3で予測された部分解を順次取得し、解を生成する。エラー検出回路6は、レジスタに格納された中間値の符号ビットと、拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、演算回路および演算処理装置ならびに演算処理方法に関する。
【背景技術】
【0002】
論理演算回路には、加減算器、除算器、平方根演算器などがある。電子回路による除算や平方根演算手法としては、引戻し法(復元法・回復型)・引離し法(非回復型)・SRT法などがある。これらの演算アルゴリズムは、商または平方根をn桁(nは自然数)ずつ求める演算を繰り返し行う計算手法である。商または平方根の桁数は、演算の繰り返し回数に比例することが特徴である。以下、このような演算手法は、筆算と同様に減算と桁のシフトとを繰り返すことから、減算シフト型演算と呼ぶことにする。
【0003】
減算シフト型演算回路は、誤作動検出装置で誤作動を検出することで、信頼性を向上させることができる。例えば、被除数および除数が零でないのに、除算装置で求めた商を正規化する前の中間的な商の最上位の桁、および最上位の桁よりも1桁上位の商のあふれの桁の2桁が零の場合、誤作動信号を発生させる誤動作検出回路が考えられている。これにより、商が誤って零になるような誤動作が検出できる。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開昭62−212728号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
ところで、減算シフト型演算論理に発見される論理障害の中には、演算過程で生じる演算データのデータパターンのうち、極めて稀なデータパターンでのみ異常動作をしてしまうものがある。減算シフト型演算回路でこのようなエラーが発生し易い論理的な場所は分かっているが、その部分の論理に間違いがないことを証明する方法が見つかっていない。そのため現状では、極めて稀なデータパターンで発生する論理障害を発見するためには、論理図面などの目視確認と論理シミュレーションによる動作検証実績の積み重ねに頼るしかない。ここで、論理図面などの目視確認による論理障害検出は、論理障害を適切に検出できるか否かが作業者の能力に依存することとなり、確実な信頼性確保手段とはいえない。他方、論理シミュレーションによる論理障害検出は、演算器レベルでの小規模な回路であれば、時間を十分にかけて検証実績を積めば高い信頼性を確保できる。
【0006】
しかし、論理シミュレーションによる動作検証を行ったとしても、回路規模が大きくなると、減算シフト型演算器の十分な信頼性を得ることは困難である。すなわち、大規模システムレベルでの論理シミュレーションや、実機検証では一演算器のチェックにかけられる時間には限界がある。このような時間的制約のため、論理シミュレーションで減算シフト型演算器バグを確実に発見するのは困難である。そのため、演算器の論理品質の向上に限界があった。
【0007】
完全な動作検証による障害の事前回避が困難であったとしても、誤った計算結果を後処理に渡さないようにできれば、信頼性を担保できる。そのため、演算動作中に希に発生する誤動作であっても、その誤動作を確実に検出する技術が求められる。
【0008】
本発明はこのような点に鑑みてなされたものであり、演算動作中に発生する誤動作を確実に検出することができる演算回路および演算処理装置ならびに演算処理方法を提供することを目的とする。
【課題を解決するための手段】
【0009】
上記課題を解決するために、以下の演算回路が提供される。演算回路は、レジスタ、前処理回路、解予測回路、中間値計算回路、解生成回路、およびエラー検出回路を有する。前処理回路は、演算対象となる数値をレジスタに格納する。解予測回路は、レジスタに数値が格納されるごとに、レジスタに格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。中間値計算回路は、解予測回路で予測された部分解を用いた所定の演算により、中間値を示す数値を生成し、中間値に対して符号拡張により拡張符号ビットを付加した数値をレジスタに格納する。解生成回路は、解予測回路で予測された部分解を順次取得し、解を生成する。エラー検出回路は、レジスタに格納された中間値の符号ビットと、拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。
【発明の効果】
【0010】
上記演算回路では、演算動作中に発生する誤作動を確実に検出することができる。
【図面の簡単な説明】
【0011】
【図1】第1の実施の形態に係る演算回路を示す図である。
【図2】第2の実施の形態に係る除算器の例を示す図である。
【図3】中間剰余レジスタと排他的論理和回路との接続例を示す図である。
【図4】部分商の判定が正常に行われた除算の例を示す図である。
【図5】部分商の判定を誤った除算の例を示す図である。
【図6】第3の実施の形態に係る除算器の例を示す図である。
【図7】第4の実施の形態に係る平方根演算器の例を示す図である。
【図8】部分平方根の判定が正常に行われた平方根演算の例を示す図である。
【図9】部分平方根の判定を誤った平方根演算の例を示す図である。
【図10】第5の実施の形態に係る平方根演算器の例を示す図である。
【図11】演算処理装置の例を示す図である。
【発明を実施するための形態】
【0012】
以下、本実施の形態について図面を参照して説明する。
[第1の実施の形態]
図1は、第1の実施の形態に係る演算回路を示す図である。演算回路は、レジスタ1、前処理回路2、解予測回路3、中間値計算回路4、解生成回路5、およびエラー検出回路6を有する。
【0013】
レジスタ1は、少なくとも1つ設けられる。レジスタ1には、中間値計算回路4で生成された中間値1aと、その中間値1aの符号拡張により中間値1aに付与された拡張符号1bが格納される。
【0014】
前処理回路2は、演算対象となる数値をレジスタ1に格納する。例えば除算器を行う場合、前処理回路2は、被除数をレジスタ1に格納する。また演算対象の数値の平方根を演算する場合、前処理回路2は、演算対象の数値をレジスタ1に格納する。なお、除算を行う場合、除数を格納するレジスタを別途設け、前処理回路2は、別途設けたレジスタに除数を格納する。
【0015】
解予測回路3は、レジスタ1に数値が格納されるごとに、レジスタ1に格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。例えば、除算を行う場合、解予測回路3は、商の一部の桁の値である部分商を、上位の桁から順に予測する。また平方根演算を行う場合、解予測回路3は、平方根の一部の桁の値である部分平方根を、上位の桁から順に予測する。
【0016】
中間値計算回路4は、解予測回路3で予測された部分解を用いた所定の演算により、中間値を示す数値を生成する。そして中間値計算回路4は、中間値に対して符号拡張により拡張符号ビットを付加した数値を、レジスタ1に格納する。
【0017】
解生成回路5は、解予測回路3で予測された部分解を順次取得し、解を生成する。例えば、除算が行われた場合、解生成回路5は、解予測回路3から部分商を取得し、商を生成する。また、平方根演算が行われた場合、解生成回路5は、解予測回路3から部分平方根を取得し、平方根を生成する。
【0018】
エラー検出回路6は、レジスタ1に格納された中間値1aの符号ビットと、拡張符号1bのいずれかの拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。例えばエラー検出回路6は、レジスタ1における中間値1aの符号ビットの位置と、拡張符号ビットの位置とに接続された排他的論理和回路6aである。排他的論理和回路6aは、レジスタ1から符号ビットと拡張符号ビットとの値を取得し、それらのビットの排他的論理和を出力する。排他的論理和回路6aの出力が1となった場合、その出力信号がエラー信号となる。
【0019】
このような構成の演算回路によれば、前処理回路2によって演算対象となる数値がレジスタ1に格納される。すると、解予測回路3により部分解が予測される。次に解予測回路3で予測された部分解に基づいて、中間値計算回路4で中間値が生成される。生成された中間値は符号拡張され、中間値計算回路4によってレジスタ1に格納される。
【0020】
中間値がレジスタ1に格納されると、その中間値に基づいて、解予測回路3によって既に予測されている桁の下位の桁の部分解が予測される。すると、新たに予測された部分解に基づいて中間値計算回路4で中間値が生成される。生成された中間値は、符号拡張され、レジスタ1に格納される。このような部分解の予測と中間値の更新とが、所定の桁数までの部分解の予測が完了するまで繰り返し実行される。
【0021】
解生成回路5では、解予測回路3で予測された部分解を組み合わせて解が生成される。
また、レジスタ1に中間値が格納されるごとに、エラー検出回路6でエラー検出が行われる。すなわち、解予測が正しく行われている場合、中間値の符号ビットと、符号拡張された拡張符号ビットとは同じ値である。そのため、エラー検出回路6からエラー信号は出力されない。解予測回路3が部分解の予測を誤ると、中間値計算回路4により生成される中間値も誤った値となる。誤った部分解が予測されると、それ以後、解の予測と中間値生成が繰り返されることで、中間値がオーバーフローとなる。中間値がオーバーフローすると、中間値の符号ビットに、中間値の最上位の桁の値が格納される。すると、拡張符号1bと、中間値の符号ビットとの値が不一致となり、エラー検出回路6からエラー信号が出力される。
【0022】
このようにして、解予測回路3の解予測の誤りによるエラーを確実に検出することが可能となる。演算回路に組み込まれたエラー検出回路6でエラーを検出するため、演算回路が稼動していれば常時エラーの有無をチェックできる。すなわち、解予測回路3での解予測の誤りが極めて希にしか発生しない場合でも、実際に発生したときにエラー信号を出力できる。エラー信号が出されれば、解生成回路5で生成された解を使用する後処理回路において、誤った解を使用せずに済む。その結果、演算結果の信頼性が向上する。
【0023】
また、エラー検出回路6で検出されるエラーは、中間値のオーバーフローである。従って、エラー原因の特定が容易になる。
しかも、エラー検出回路6は、例えば排他的論理和回路6aで実現できる。すなわち、極めて少ない論理の追加で障害検出が可能となる。
【0024】
なお、上記の説明では、解予測回路3による部分解の予測の誤りによるエラー発生の事例を説明したが、中間値のオーバーフローは、他の原因でも発生する。例えば、LSI(Large Scale Integration)の初期不良(トランジスタセルの固定故障)や、放射線等の要因によるソフトエラーのために演算が期待通りの動作をしないこともある。このような故障も、中間値のオーバーフローが発生した時点で障害を発見できる。そこで、図1に示した構成の演算回路を製品のLSIに組み込んでおけば、製品の信頼性を向上する。すなわち、RAS(Reliability、Availability、Serviceability)と呼ばれる、信頼性、可用性、保守性が向上する。
【0025】
ここで、図1に示した演算回路は、すべての除算シフト型演算に適用できる。除算シフト型演算としては、除算や平方根演算がある。除算や平方根演算では、解予測回路3の設計にミスが生じやすい。図1に示した演算回路を用いれば、減算シフト型の除算・平方根演算における、回路設計が難しい解予測回路の動作検証が可能となる。その結果、回路設計ミスによるバグの発生を防止できる。
【0026】
なお、図1に示した演算回路と等価の回路を用いて論理シミュレーションを行うことで、論理シミュレーション上でも解予測の誤りを検出可能となる。
また、ソフトウェアにより減算シフト型演算を実行する場合も、エラー検出回路6と同様の処理を行うモジュールをプログラムに追加することで、中間値のオーバーフローを検出できる。
【0027】
このような減算シフト型演算には、例えば除算や平方根演算がある。そこで、以下、除算の例を第2・第3の実施の形態で説明し、平方根演算の例を第4・第5の実施の形態で説明する。
【0028】
[第2の実施の形態]
第2の実施の形態は、誤動作検出が可能な除算器である。
以下の説明では、まず減算シフト型演算の漸化式と一般的な演算方法を説明する。その後、中間剰余の符号ビットの比較が論理チェッカーとして機能する理由を説明する。
【0029】
以下のように記号と言葉を定義する。
・被除数=op1
・除数=op2
・基数=k(=2m:mは自然数)
通常、演算前にop2の最上位桁とOP1の最上位桁の位置合わせ(桁合わせ)が行われる。桁合わせでは、OP1とOP2の最上位桁の位置は一致しているか、またはOP1がOP2より一桁小さい値とされる。このように桁合わせされたop1をOP1、op2をOP2とそれぞれ大文字で書くことにする。桁合わせされた前後における被除数と除数とは、以下の関係式で表されるものとする。
OP1=op1×ka:(aは整数)
OP2=op2×kb:(bは整数)
ここで、上記OP1,OP2を使って、減算シフト型除算は以下の漸化式で定義される。
r(n)=k×r(n−1)−q(n−1)×OP2
r(0)=OP1
・・・(1)
この式(1)より、商および中間剰余が算出される。ただし、|r(n)|<OP2となるように整数q(n−1)を選ぶ。q(n−1)の候補は|q(n−1)|<kを満たす範囲に複数存在することがあるが、そのうち1つを任意に選択すればよい。このときのr(n)をn番目の中間剰余と呼び、q(n−1)を上からn桁目の部分商と呼ぶ。
【0030】
引戻し法(復元法)とはr(n)が常に0または正の数となるように整数q(n−1)を選ぶ計算法である。引離し法とはr(n)が負の数になることも許す計算法である。
SRT法とはr(n)に負の数を許し、かつ|r(n)|<OP2の判定をr(n)の上位数ビットのみから判断する計算法である。なお、SRT法では、実際には|r(n)|<OP2の判定を、その元となる右辺のr(n−1)の上位数ビットから判断される。
【0031】
このように引戻し法であれば、r(n)が常に0または正の数に制限される。この場合、q(n−1)の候補として自動的に0または正の数が唯一に決まる。他方、引離し法やSRT法であれば、r(n)に負の数も許される。この場合、q(n−1)も負の値を取ることがあり、またその候補は複数存在することがある。
【0032】
また、上から1〜n桁目までの商をQ(n)と書くことにし、q(n)を用いてQ(n)を表現すると
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
・・・(2)
と表せる。ただし、この商は桁合わせされた被除数OP1、除数OP2のときの商である。
【0033】
式(1)より
r(n)=k×r(n−1)?q(n−1)×OP2
=k×{k×r(n−2)?q(n−2)×OP2}?q(n−1)×OP2
=k2×r(n−2)?{k×q(n−2)+q(n−1)}×OP2
=k3×r(n−3)?{k2×q(n−3)+k×q(n−2)+q(n−1)}×OP2
:
=kn×r(0)?{kn-1×q(0)+kn-2×q(1)+…+k2×q(n−3)+k×q(n−2)+q(n−1)}×OP2
=kn×r(0)?Q(n)×OP2
・・・(3)
⇔r(0)={Q(n)×OP2+r(n)}/kn
={Q(n)×kb/kn}×op2+r(n)/kn
(OP2=op2×kbより)
・・・(4)
⇔op1={Q(n)×kb/kn+a}×op2+r(n)/kn+a
(r(0)=OP1=op1×kaより)
・・・(5)
式(4)は、式(3)をr(0)について解き、OP2をop2に置き換えたものである。そのため、式(3)と式(4)とは同値(記号⇔で表される)となる。式(5)は、式(4)のr(0)をOP1に置き換え、さらにOP1をop1に置き換えたものである。そのため、式(4)と式(5)とは同値である。
【0034】
被除数op1、除数op2の場合、商と剰余の関係式がop1=商×op2+剰余である。このことと、式(3)、(4)、(5)により、
商=Q(n)×kb/kn+a ・・・(6)
剰余=r(n)/kn+a ・・・(7)
となる。
【0035】
通常、固定小数除算の場合は、上記の商を示す式(6)および剰余を示す式(7)が整数であり続ける最大のnまで式(1)の演算が繰り返される。
浮動小数除算の場合は、Q(n)が必要な桁数(=有効数字+α)に達するまで式(1)の演算を繰り返す。例えばIEEE754で定義されている単精度浮動小数点数なら仮数部23ビットの有効数字、倍精度なら仮数部52ビットの有効数字が使用される。有効数字に必要なビット数に、暗黙の1と呼ばれる整数部1ビットと、丸めに必要な下位数ビットとを加えた合計が、必要な桁数となる。ここで「丸め」とは、数値を一定の規則に従って近似値で表現することであり、例えば有効数字以下の値の四捨五入が行われる。
【0036】
以上が減算シフト型除算についての説明である。この演算を実行する演算回路の論理設計で注意を要するのは、式(1)の演算と、|r(n)|<OP2となるように整数q(n−1)を選ぶ選び方である。
【0037】
特に、論理ミスを起こしやすくその発見が難しいのが|r(n)|<OP2の判定論理である。1990年代には、パーソナルコンピュータで使用されるCPU(Central Processing Unit)の浮動小数点除算にSRT法を用いたが、ある特定の入力値に対して演算結果を誤ることが製品の出荷後に判明し、リコールに至ってしまったという事例もある。この事例においても、|r(n)|<OP2判定を誤ったことが原因である。なお、演算結果を誤る頻度が極めて少ないとしても、演算結果の正しさが保証されていないと科学技術計算に使用できない。そこで、誤った演算結果を後処理に渡さない回路を組み込むことが重要となる。
【0038】
本実施の形態は、|r(n)|<OP2の判定を間違えた場合、判定誤りを検出してエラーを出力するものである。以下、|r(n)|<OP2の判定誤りを検出する論理について説明する。
【0039】
まずは|r(n)|<OP2の判定を間違えた場合、その後の演算の動きがどうなるのかを考察する。
|r(n)|<OP2の判定を間違えると、間違った部分商q(n−1)が選ばれる。すると、それ以降ずっと|r(n)|≧OP2となり、中間剰余が二度と収束しなくなってしまう。その理由は以下の通りである。
|r(n)|≧OP2とすると
|r(n+1)|=|k×r(n)−q(n)×OP2|
≧|k×(±OP2)−q(n)×OP2|
=|±k−q(n)|×OP2
≧OP2(|整数q(n)|<kより)
・・・(8)
式(8)は|r(n)|≧OP2が満たされると、常に|r(n+1)|≧OP2が満たされることを示している。すなわち、一度判定誤りを起こすと、その後も誤り続けることが示されている。
【0040】
一度判定誤りを起こすと、演算は上記のような中間剰余が発散した状態を続ける。多くの場合、または発散した状態による演算を繰り返すうちに、中間剰余の上位ビットがオーバーフロー(桁あふれ)を起こす。中間剰余の上位ビットがオーバーフローを起こすと、演算器の桁数範囲を越えてしまうため、誤った中間剰余(上位ビットが欠損した中間剰余)が発生する。誤った中間剰余が発生すると、それ以降誤った中間剰余と中間商を算出し続ける。このように|r(n)|<OP2の判定誤りが発生すると、中間剰余が発散した状態を続けるか、誤った中間剰余と中間商を算出し続けるかのどちらかである。いずれにせよ商は正しい期待値とは一致しなくなる。
【0041】
本実施の形態では、上記エラー状態のうち特に、中間剰余がオーバーフローしたことを検出することで、判定誤りの発生を検出する。
以下、論理演算が、符号拡張機能を有するディジタル回路によって構成されているものとする。符号拡張とは、符号付の数値を表現するビット列が格納領域のビット幅より短い場合に、空いたビットに適切な値を設定することによって数値としての同一性を維持する手法である。本実施の形態では、符号ビットと同じ値を上位のビットに書き込むことで符号拡張が行われるものとする。
【0042】
演算前の桁合わせにより、式(1)の初期値としての被除数OP1=r(0)とOP2の最上位桁の位置は一致しているか、またはOP1=r(0)がOP2より一桁小さい値となる。それ以降も論理的に間違いがなければ|r(n)|<OP2を満たしながら演算が続く。そのため、r(n)の最上位桁の位置はOP2の最上位桁の位置を超えることはない。よって論理的に間違いがなければOP2の符号ビットの位置は、r(n)にとっても符号ビットの位置となる。符号付きディジタル回路では、符号拡張により、符号ビットの値はその上位に全て同じ値がコピーされる。つまり符号ビットと、符号ビットの上位のビットとを比較すれば必ず同じ値になる。もしも符号ビットと、符号ビットの上位の拡張符号ビットとの値が異なってしまったときは、オーバーフローが発生したことで符合ビットの位置までデータが溢れてきたと判断できる。
【0043】
ここでOP2の最上位桁のすぐ隣の符号ビットの位置(符号ビット列中の最も右側にある符号ビット)をs0、そのひとつ上位の符号ビット(拡張符号ビット)の位置をs1とする。このとき、r(n)の排他的論理和(s0 xor s1)の演算結果を見るだけで論理障害の検出が可能になる。すなわち、問題がない時は排他的論理和(s0 xor s1)=0であり、エラーが発生すれば排他的論理和(s0 xor s1)=1となる。
【0044】
このような判定誤り検出実現に用いられる追加論理回路は、排他的論理和回路(xorゲート)1つだけで実現することができる。
図2は、第2の実施の形態に係る除算器の例を示す図である。除算器には、前処理回路11が設けられている。前処理回路11は、被除数と除数との桁合わせ処理などの前処理を行う。前処理回路11の出力信号線は、中間剰余レジスタ12と除数レジスタ13とに接続されている。前処理回路11は、桁合わせ後の被除数であるOP1を中間剰余レジスタ12に格納する。また、前処理回路11は、桁合わせ後の除数であるOP2を除数レジスタ13に格納する。
【0045】
中間剰余レジスタ12は、中間剰余を格納するレジスタである。例えばIEEE754で定義されている倍精度浮動小数点なら、64ビット幅のレジスタを中間剰余レジスタ12として使用できる。中間剰余レジスタ12の出力信号線は、商予測回路14と加算器16とに接続されている。また、中間剰余レジスタ12の出力信号線は、除算器の除算結果として得られる最終剰余の後処理を行う回路(図示せず)に接続されている。
【0046】
商予測回路14は、中間剰余レジスタ12に設定された中間剰余に基づいて部分商q(n−1)を予測する。ここで商予測回路14は、除数OP2と中間剰余との組み合わせパターンにおいて、式(1)の演算の結果、|r(n)|<OP2となる部分商q(n−1)を決定する。しかし、商予測回路14に論理障害があり、その障害を活性化させるような除数OP2と中間剰余との特別な組み合わせパターンが発生する場合、またはトランジスタセルの固定故障や放射線等の要因によるソフトエラーが発生する場合がある。これらの場合、商予測回路14が、|r(n)|<OP2を満たさない部分商q(n−1)を予測する可能性がある。商予測回路14の出力信号線は、加算値生成回路15と商生成回路17とに接続されている。
【0047】
なお、図2では商予測回路14と除数レジスタ13との接続関係を省略しているが、商予測回路14は除数レジスタ13に格納された除数を参照できる。そして、商予測回路14は、除数を用いて部分商を予測できる。
【0048】
加算値生成回路15は、中間剰余に加算する値を算出する。具体的には、加算値生成回路15は、商予測回路14が予測した部分商q(n−1)に除数レジスタ13から取得した除数OP2を乗算する。加算値生成回路15は乗算結果に−1を乗算する。−1を乗算することで符号が反転される。加算値生成回路15の演算結果を出力する出力信号線は、加算器16に接続されている。
【0049】
加算器16は、入力された値を加算する。具体的には、加算器16は、中間剰余レジスタ12に格納されている中間剰余と、加算値生成回路15で算出された値とを加算する。加算器16の加算結果を出力する出力信号線は、中間剰余レジスタ12に接続されている。すなわち、加算器16による加算結果が、中間剰余として中間剰余レジスタ12に格納される。
【0050】
なお、除数と部分商とが共に正であれば、加算値生成回路15の演算結果は負の値となる。この場合、加算器16における演算は、中間剰余から加算値生成回路15の演算結果の絶対値を減算する演算に等しい。本実施の形態では、負の数を2の補数で表す。2の補数表現は、符号以外の値のバイナリ表現の各ビットを否定(値を反転)させ、1を加えたものである。すなわち加算値生成回路15は、演算結果が負の数であれば、2の補数表現の演算結果を出力する。この場合、加算器16では中間剰余に加算値生成回路15の演算結果を加算し、最上位ビットからのキャリー(1つ上の桁へ繰り上げる数)を無視する。これにより、負の数の加算結果を得ることができる。
【0051】
商生成回路17は、商予測回路14で決定された部分商に基づいて商を生成し、出力する。商生成回路17の出力信号線は、商レジスタ18に接続されている。すなわち、商生成回路17で生成された商が商レジスタ18に書き込まれる。具体的には、商生成回路17は、商予測回路14で部分商が予測されるごとに商レジスタ18に格納されている商の値を読み込む。次に商生成回路17は、商レジスタ18から読み込んだ値を所定の桁だけ上位にシフトさせ、空いた下位の桁に商予測回路14で決定された部分商を加算する。そして商生成回路17は、部分商を追加した値を商レジスタ18に書き込む。
【0052】
商レジスタ18は、商を記憶するレジスタである。商レジスタ18の出力信号線は、商生成回路17に接続されている。また商レジスタ18の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0053】
中間剰余レジスタ12には、排他的論理和回路19が接続されている。具体的には、中間剰余レジスタ12内の符号ビットと、符号ビットの上位の1ビットとの出力信号線に、排他的論理和回路19が接続されている。
【0054】
図3は、中間剰余レジスタと排他的論理和回路との接続例を示す図である。図3の例では、中間剰余レジスタ12は64ビット幅のレジスタである。中間剰余レジスタ12には、下位から順に、丸め用ビット列12a、中間剰余ビット列12b、および拡張符号ビット列12cが設けられている。
【0055】
丸め用ビット列12aは、中間剰余レジスタ12の下位の数ビットである。丸め用ビット列12aには、中間剰余を丸めるために使用する値が設定される。例えば、丸め用ビット列12aとして、中間剰余レジスタ12の下位2ビットが使用される。
【0056】
中間剰余ビット列12bは、丸め用ビット列12aの上位に設けられている。中間剰余ビット列12bには、初期値として被除数OP1が格納される。その後、加算器16による演算が行われるごとに、演算結果が中間剰余として中間剰余ビット列12bに格納される。例えば、中間剰余ビット列12bとして、中間剰余レジスタ12内の53ビット用いられる。
【0057】
中間剰余ビット列12bの最上位ビットは、符号ビット12dである。符号ビットには、中間剰余の符号を示す値が設定される。中間剰余が正の値であれば符号ビットに0が設定され、中間剰余が負の値であれば符号ビットに1が設定される。
【0058】
拡張符号ビット列12cは、中間剰余ビット列12bの上位に設けられている。拡張符号ビット列12cには、拡張符号ビットが格納される。例えば加算器16による演算結果が正の値であれば、拡張符号ビット列12cのすべてのビットに0が設定される。また加算器16による演算結果が負の値であれば、拡張符号ビット列12cのすべてのビットに1が設定される。
【0059】
排他的論理和回路19への入力信号線は、中間剰余ビット列12bの符号ビット12dと、拡張符号ビット列12cの最下位のビット12eとに接続されている。これにより、排他的論理和回路19に符号ビット12dと、符号ビット12dの上位のビット12eとの値が入力される。そして排他的論理和回路19において、入力された2つのビットの値の排他的論理和演算が行われる。すなわち排他的論理和回路19は、入力された2つのビットの値が同じときに0を出力する。また排他的論理和回路19は、入力された2つのビットの値が異なるときに1を出力する。
【0060】
図2、図3に示すような回路構成により、除算処理が行われる。除算処理が行われる場合、被除数op1と除数op2とが前処理回路11に入力される。すると前処理回路11により桁合わせが行われ、桁合わせ後の被除数OP1と除数OP2とが生成される。除数OP1は、前処理回路11により中間剰余レジスタ12に格納される。除数OP2は、前処理回路11により除数レジスタ13に格納される。
【0061】
次に中間剰余レジスタ12に格納された被除数OP1の最上位の桁の部分商が、商予測回路14により予測される。予測された部分商は、加算値生成回路15と商生成回路17とに入力される。すると商生成回路17により、商予測回路14で予測された部分商を商レジスタ18に格納される。
【0062】
また加算値生成回路15では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路15による演算結果は、加算器16に入力される。加算器16では、中間剰余レジスタ12に格納されている被除数OP1に、加算器16の演算結果が加算される。加算結果は中間剰余レジスタ12に書き込まれる。これにより、中間剰余レジスタ12の内容が、被除数OP1から中間剰余に更新される。
【0063】
中間剰余レジスタ12の値が更新されると、商予測回路14により次の桁の部分商が予測される。予測された部分商は、加算値生成回路15と商生成回路17とに入力される。すると商生成回路17により、商レジスタ18に格納されている値の下位に、商予測回路14で予測された部分商が追加される。そして商生成回路17により、新たに予測された部分商を追加した値が商レジスタ18に格納される。
【0064】
また加算値生成回路15では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路15による演算結果は、加算器16に入力される。加算器16では、中間剰余レジスタ12に格納されている中間剰余に、加算値生成回路15の演算結果が加算される。加算結果は中間剰余レジスタ12に書き込まれる。これにより、中間剰余レジスタ12内の中間剰余の値が更新される。
【0065】
以後同様に、部分商の予測と、予測された部分商による演算が、必要な桁数の商が得られるまで繰り返し実行される。その結果、商レジスタ18には、被除数OP1を除数OP2で除算したときの商が格納される。また中間剰余レジスタ12には、被除数OP1を除数OP2で除算したときの剰余が格納される。
【0066】
このような除算の過程において、商予測回路14が部分商の予測を誤らなければ、拡張符号ビット列12cの最下位のビット12eと符号ビット12dとの値は常に一致する。
図4は、部分商の判定が正常に行われた除算の例を示す図である。図4の例では、簡単のため、数字は8ビットの2進数であるものとする。また、桁合わせは済んでいるものとする。桁合わせ後の被除数OP1を「+11000000」、除数OP2を「+10000001」とする。この場合、OP1÷OP2=(+11000000)÷(+10000001)という除算が除算器で行われる。
【0067】
図4には、左側に除算過程が示されている。また右側に中間剰余レジスタの内容が示されている。中間剰余レジスタの内容のうち、左端の値が拡張符号ビット列の最後尾のビットの値である。そのビットの右側の値が、符号ビットの値である。中間剰余レジスタの内容のうち、右側の8つの通知が中間剰余ビット列の値である。
【0068】
商予測回路14では、商の上位の桁から順に1桁ずつ部分商が予測される。中間剰余が正の値の間は、符号ビットとその上位のビットとの値が共に0である。中間剰余が負の値になると、符号ビットとその上位のビットとの値が共に1となる。いずれにしても、商予測が正しく行われていれば、符号ビットとその上位のビットとの値は一致する。
【0069】
他方、商予測回路14に論理障害があったとき、またはトランジスタセルの固定故障や、放射線等の要因によるソフトエラーが発生したとき、除算過程において、商予測回路14が部分商の予測を誤る場合がある。すなわち、式(1)の演算の結果|r(n)|<OP2を満たさなくなる部分商q(n−1)を、商予測回路14が予測する場合がある。その場合、中間剰余のオーバーフローが発生し、符号を設定すべき符号ビット12dに中間剰余の符号以外の数値が設定されてしまう。すると、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となる。
【0070】
図5は、部分商の判定を誤った除算の例を示す図である。図5の例では、上から4桁目の部分商の判定を誤った場合を示している。すなわち|r(n)|<OP2という条件を満たすには部分商q(n−1)を1とすべきであるが、商予測回路14が部分商を0と判定したものとする。
【0071】
すると4桁目の部分商を用いて計算した中間剰余が、除数OP2よりも大きくなる。図5の例では、4桁目の部分商を用いて計算した中間剰余は9桁の数値となっており、中間剰余レジスタにおける中間剰余ビット列のビット数を超えている。その結果、中間剰余が発散し、オーバーフローが発生する。オーバーフローが発生した結果、算出された中間剰余の最上位の桁の値が、符号ビットに設定されている。その結果、中間剰余が正の値であるにも拘わらず、符号ビットの値が1になっている。他方、拡張符号ビット列の最下位のビットの値は、以前として0である。その結果、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となっている。
【0072】
拡張符号ビット列の最下位のビットと符号ビットとの一致・不一致は、排他的論理和回路19によって検出される。排他的論理和回路19の1の出力信号は、エラー通報を示す情報である。
【0073】
なお、中間剰余が一度発散すると、それ以降どの様な計算が行われるかは不明である。すなわち、図5の右側に示した筆算による計算通りに除算器で計算が続けられるかどうかも不明である。
【0074】
このように、本実施の形態によれば、中間剰余レジスタ12に排他的論理和回路19を接続するだけで、中間剰余のオーバーフローを検出することができる。その結果、商予測回路14が商予測を誤った場合、エラーを発生させることができる。
【0075】
しかも排他的論理和回路19を追加するだけでよいため、商予測の誤り検出機能の追加による回路の大規模化を、最低限におさえることができる。
[第3の実施の形態]
次に第3の実施の形態について説明する。第3の実施の形態は、CSA(Carry Save Adder)を用いた除算器である。
【0076】
図6は、第3の実施の形態に係る除算器の例を示す図である。除算器には、前処理回路21が設けられている。前処理回路21は、被除数と除数との桁合わせ処理などの前処理を行う。前処理回路21の出力信号線は、2つの中間剰余レジスタ22a,22bと除数レジスタ23とに接続されている。前処理回路21は、桁合わせ後の被除数であるOP1を、一方の中間剰余レジスタ22aに格納する。また、前処理回路21は、桁合わせ後の除数であるOP2を除数レジスタ23に格納する。
【0077】
中間剰余レジスタ22a,22bは、中間剰余をサムとキャリーに分けて格納するレジスタである。例えば中間剰余レジスタ22aにサムの値が格納され、中間剰余レジスタ22bにキャリーの値が格納される。中間剰余レジスタ22a,22bの出力信号線は、商予測回路24とCSA26とに接続されている。また、中間剰余レジスタ22a,22bの出力信号線は、加算・オーバーフロー検出回路29に接続されている。
【0078】
商予測回路24は、中間剰余レジスタ22a,22bにサムとキャリーとに分けて設定された中間剰余に基づいて部分商q(n−1)を予測する。商予測回路24の出力信号線は、加算値生成回路25と商生成回路27とに接続されている。
【0079】
なお、図6では商予測回路24と除数レジスタ23との接続関係を省略しているが、商予測回路24は除数レジスタ23に格納された除数を参照できる。そして、商予測回路24は、除数を用いて部分商を予測できる。
【0080】
加算値生成回路25は、中間剰余に加算する値を算出する。具体的には、加算値生成回路25は、商予測回路24が予測した部分商q(n−1)に除数レジスタ23から取得した除数OP2を乗算する。加算値生成回路25の演算結果を出力する出力信号線は、CSA26に接続されている。
【0081】
CSA26は、入力された値を加算する。CSA26は、入力値の加算処理を行い、部分剰余をサムとキャリーとに欠けて出力する機能を有している。CSAで得られるサムは、加算される値の桁ごとの和であり、繰り上げされる値が無視されている。繰り上げられる値は、キャリーとして出力される。具体的には、CSA26は、中間剰余レジスタ22a,22bに格納されている中間剰余を示すサムとキャリー、および加算値生成回路25で算出された値を加算する。CSA26の加算結果を出力する出力信号線は、中間剰余レジスタ22a,22bに接続されている。CSA26の加算によって得られるサムは、中間剰余レジスタ22aに格納される。またCSA26の加算によって得られるキャリーは、中間剰余レジスタ22bに格納される。
【0082】
商生成回路27は、商予測回路24で決定された部分商に基づいて商を生成し、出力する。商生成回路27の出力信号線は、商レジスタ28に接続されている。
商レジスタ28は、商を記憶するレジスタである。商レジスタ28の出力信号線は、商生成回路27に接続されている。また商レジスタ28の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0083】
加算・オーバーフロー検出回路29は、中間剰余レジスタ22a,22bからサムとキャリーとを取得する。そして加算・オーバーフロー検出回路29は、サムとキャリーとを加算し、正しい剰余を生成する。除算処理の途中であれば、加算・オーバーフロー検出回路29で算出される剰余は中間剰余となる。除算処理が終了していれば、加算・オーバーフロー検出回路29で算出される剰余は最終剰余となる。加算・オーバーフロー検出回路29は、算出した最終剰余を、後処理を行う回路(図示せず)に出力する。
【0084】
また加算・オーバーフロー検出回路29は、オーバーフロー検出処理を行う。具体的には、加算・オーバーフロー検出回路29は、算出した剰余の桁数が符号ビットを含めた桁数を超えているか否かを判定し、超えていた場合、エラー検出信号を出力する。
【0085】
図6に示すような回路構成により、除算処理が行われる。除算処理が行われる場合、被除数op1と除数op2とが前処理回路21に入力される。すると前処理回路21により桁合わせが行われ、桁合わせ後の被除数OP1と除数OP2とが生成される。除数OP1は、前処理回路21により中間剰余レジスタ22aに格納される。除数OP2は、前処理回路21により除数レジスタ13に格納される。
【0086】
次に中間剰余レジスタ22aに格納された被除数OP1の最上位の桁の部分商が、商予測回路24により予測される。予測された部分商は、加算値生成回路25と商生成回路27とに入力される。すると商生成回路27により、商予測回路24で予測された部分商を商レジスタ28に格納される。
【0087】
また加算値生成回路25では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路25による演算結果は、CSA26に入力される。CSA26では、中間剰余レジスタ22aに格納されている被除数OP1に、加算値生成回路25の演算結果が加算され、サムとキャリーとが出力される。加算結果のうちのサムは中間剰余レジスタ22aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ22bに書き込まれる。
【0088】
中間剰余レジスタ22a,22bの値が更新されると、中間剰余レジスタ22a,22bの値に基づいて、商予測回路24により次の桁の部分商が予測される。予測された部分商は、加算値生成回路25と商生成回路27とに入力される。すると商生成回路27により、商レジスタ28に格納されている値の下位に、商予測回路24で予測された部分商が追加される。そして商生成回路27により、新たに予測された部分商を追加した値により、商レジスタ28の値が更新される。
【0089】
また加算値生成回路25では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路25による演算結果は、CSA26に入力される。CSA26では、中間剰余レジスタ22aに格納されているサム、中間剰余レジスタ22aに格納されているキャリー、および加算値生成回路25の演算結果が加算される。加算結果のうちのサムは中間剰余レジスタ22aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ22bに書き込まれる。
【0090】
以後同様に、部分商の予測と、予測された部分商による演算が、必要な桁数の商が得られるまで繰り返し実行される。その結果、商レジスタ28には、被除数OP1を除数OP2で除算したときの商が格納される。また中間剰余レジスタ22a,22bには、被除数OP1を除数OP2で除算したときの剰余が格納される。
【0091】
また、中間剰余レジスタ22a,22bの値が更新された場合、加算・オーバーフロー検出回路29により中間剰余が算出され、オーバーフローの発生の有無が判定される。加算・オーバーフロー検出回路20からエラー検出信号が出力される。除算処理が終了すると、加算・オーバーフロー検出回路29により、中間剰余レジスタ22a,22bの値に基づいて最終剰余が算出される。
【0092】
このように、CSAを用いた除算器においても、中間剰余のオーバーフローを検出できる。その結果、商予測回路24による商予測に誤りがあった際に、エラー検出信号を出力することができる。
【0093】
[第4の実施の形態]
次に第4の実施の形態について説明する。第4の実施の形態は、平方根演算器(開平回路)における解予測の誤りを検出するものである。以下、除算の場合と同様に、まず減算シフト型演算の漸化式と一般的な演算方法を説明する。その後、中間剰余の符号ビットの比較が論理チェッカーとして機能する理由を説明する。
【0094】
なお以下の説明では、平方根演算の対象として入力された数値と、計算途中の平方根の解の自乗との差分を、中間剰余と呼ぶこととする。また、平方根演算の対象として入力された数値と、平方根演算終了時の平方根の解の自乗との差分を最終剰余と呼ぶこととする。さらに平方根演算においても、中間剰余の符号拡張が行われる。また負の数は、2の補数で表現される。
【0095】
平方根演算では入力される数値は1つのみである。入力された数値をop3とし、op3の平方根を求めるものとする。この場合、桁合わせされたOP3をOP3と書くことにし、以下の関係式で表されるものとする。
OP3=op3×kb:bは整数
除算の商の場合と同様に、1〜n桁目までの平方根Q(n)を、n桁目の部分平方根q(n)を用いて表すと、
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
・・・(9)
である。ここで、Q(0)=0と定義する。
【0096】
この式(9)を変形すると以下の関係が得られる。
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
=k{q(0)×kn-2+q(1)×kn-3+…+q(n−2)}+q(n−1)
=k×Q(n−1)+q(n−1)
・・・(10)
上記OP3、Q(n)を使って、減算シフト型の平方根演算は以下の漸化式で定義される。
r(n)=k2×r(n−1)−2k×Q(n−1)×q(n−1)−q2(n−1)
r(0)=OP3
・・・(11)
r(n)は、n番目の中間剰余である。式(11)の証明については後述する(証明1)。
【0097】
ただし、|r(n)−1|<2Q(n)となるように整数q(n−1)を選ぶ。q(n−1)の候補は|q(n−1)|<kを満たす範囲に複数存在することがあるが、そのうち1つを任意に選択すればよい。すなわち、q(n−1)の算出に用いられる判定不等式が|r(n)−1|<2Q(n)である。判定不等式が|r(n)−1|<2Q(n)であることの証明については、後述する(証明2)。
【0098】
よって除算と同様に考えれば、中間剰余r(n)の最上位桁のすぐ隣の符号ビットの位置(符号ビットの最も右側)をs0、そのひとつ上位の符号ビットの位置をs1としたとき、r(n)の(s0 xor s1)を見るだけで論理障害の検出が可能になる。問題がない時は(s0 xor s1)=0であり、エラーが発生すれば(s0 xor s1)=1となる。エラーが発生すれば(s0 xor s1)=1となることの証明については、後述する(証明3)。
【0099】
次に、平方根演算が式(11)で表されることを証明する(証明1)。
Q2(n)≒(OP3に桁合わせを行った値)=(r(0)に桁合わせを行った値)である。すると、r(n)は、r(0)とQ2(n)とを用いて、以下のような差分の式で書くことができる。
r(n)=k2n×r(0)−Q2(n) ・・・(12)
さらに式(10)より、
r(n)=k2n×r(0)−{k×Q(n−1)+q(n−1)}2
=k2n×r(0)−{k2×Q2(n−1)+2k×Q(n−1)×q(n−1)+q2(n−1)}
=k2×{k2(n−1)×r(0)−Q2(n−1)}−2k×Q(n−1)×q(n−1)−q2(n−1)
=k2×r(n−1)−2k×Q(n−1)×q(n−1)−q2(n−1)
・・・(13)
となる。このようにして式(11)が導かれる(証明1終了)。
【0100】
次にq(n−1)算出に用いられる判定不等式が|r(n)−1|<2Q(n)であることを証明する(証明2)。
|r(n)−1|<2Q(n) ⇔ −2Q(n)+1<r(n)<2Q(n)+1
・・・(14)
ここでn≧1でr(n−1)が式(14)の不等式を満たしたとき、r(n)においても式(14)が成立することを示す。具体的には、「n=1」のときに式(14)が成立すること、および「n>1」のときにr(n−1)が成立すれば必ずr(n)が成立することを証明する。
【0101】
まず「n=1」のときを考える。
Q(1)=q(0)>0であり、|k×√(OP3)−q(0)|<1となるようにq(0)が選ばれているはずである。これは、k×√(OP3)とq(0)の最上位の桁が合うように桁合わせがされており、その整数部分が一致するようにq(0)を選んでいるからである。
【0102】
よって
−1<k×√(OP3)−q(0)<1
⇔−1<k×√(r(0))−q(0)<1
・・・(15)
式(15)の連立不等式の左側より
0<k×√(r(0))−q(0)+1
⇔0<(k×√(r(0))+q(0)−1)(k×√(r(0))−q(0)+1)
⇔0<k2×r(0)−(q(0)−1)2
⇔0<k2×r(0)−q2(0)+2q(0)−1
⇔−2q(0)<k2×r(0)−q2(0)−1
・・・(16)
同じく式(15)の連立不等式の右側より
k×√(r(0))−q(0)−1<0
⇔(k×√(r(0))+q(0)+1)(k×√(r(0))−q(0)−1)<0
⇔k2×r(0)−(q(0)+1)2<0
⇔k2×r(0)−q2(0)−2q(0)−1<0
⇔k2×r(0)−q2(0)−1<2q(0)
・・・(17)
q(0)>0であることと、式(16)、式(17)の結果を合わせると、
|k2×r(0)?q2(0)?1|<2q(0)
⇔|r(1)?1|<2Q(1) ・・・(18)
となり、n=1のときで式(14)が成立する。
【0103】
次に「−2Q(n−1)+1<r(n−1)」が満たされれば、「−2Q(n)+1<r(n)」が満たされることを証明する。
r(n)=k2×r(n−1)?2k×Q(n−1)×q(n−1)?q2(n−1)
>k2×{−2Q(n−1)+1}?2k×Q(n−1)×q(n−1)?q2(n−1)
=−2kQ(n−1)×{k+q(n−1)}+{k+q(n−1)}×{k−q(n−1)}
={k+q(n−1)}×{−2k×Q(n−1)+k−q(n−1)}
={k+q(n−1)}×[−2{k×Q(n−1)+2q(n−1)}+k+q(n−1)]
={k+q(n−1)}×{−2Q(n)+k+q(n−1)}
・・・(19)
式(19)の右辺はr(n)の下限であるから、ここがどのような値を取ってもr(n)はその値より大きい。よって右辺が最も大きくなるようにq(n−1)を選ぶと、q(n−1)=−(k−1)となる。その理由は以下の通りである。
【0104】
−2Q(n)+k+q(n−1)<0であり、1≦k+q(n−1)≦2k−1である。そのため、q(n−1)=−(k−1)で右辺{k+q(n−1)}×{−2Q(n)+k+q(n−1)}は最大となる。
【0105】
よってq(n−1)=−(k−1)を式(19)の右辺に代入して以下の式となる。
r(n)>−2Q(n)+1 ・・・(20)
さらに「r(n−1)<2Q(n−1)+1」が満たされれば、「r(n)<2Q(n)+1」が満たされることを証明する。
r(n)=k2×r(n−1)?2k×Q(n−1)×q(n−1)?q2(n−1)
<k2×{2Q(n−1)+1}?2k×Q(n−1)×q(n−1)?q2(n−1)
=2kQ(n−1)×{k−q(n−1)}+{k+q(n−1)}×{k−q(n−1)}
={k−q(n−1)}×{2k×Q(n−1)+k+q(n−1)}
={k−q(n−1)}×[2{k×Q(n−1)+2q(n−1)}+k−q(n−1)]
={k−q(n−1)}×{2Q(n)+k−q(n−1)}
・・・(21)
ここで式(21)の右辺が最も小さくなるようにq(n−1)を選ぶと、q(n−1)=k−1となる。よって
r(n)<2Q(n)+1 ・・・(22)
が得られる。式(20)と式(22)との連立不等式は、|r(n)−1|<2Q(n)と同値である。従って、「n>1」の場合に、r(n−1)が式(14)の不等式を満たしたとき、r(n)においても式(14)が満たされる。
【0106】
以上より、「n≧1」のすべてのnの場合に、式(14)の不等式が満たされる(証明2終了)。
次に、エラーが発生すれば(s0 xor s1)=1となることについて証明する(証明3)。
【0107】
式(11)で定義される平方根演算の方法は、Q(n)、r(n)が整数で表せるように各数式を定義している。ただし、その副作用として最上位桁の位置が演算回数に比例して上に移動してしまう。実際のハードで実現する場合には、最上位の位置が固定されるように以下の漸化式に置き換えて行うのが普通である。
r’(n)=r(n)/kn
Q’(n)=Q(n)/kn
・・・(23)
とし、式(11)の両辺をknで割る。
r’(n)=k×r’(n−1)−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)
r(0)=OP3
・・・(24)
すると、整数q(n−1)選択に用いられる判定式は|r’(n)−1/kn|<2Q’(n)となる。この判定式を満たさないq(n−1)が選択されると、繰り返し部分平方根の予測を行ううちに、式(24)におけるr’(n)の演算結果がオーバーフローする。すなわち、r’(n)の演算結果の桁数が、r’(n)の格納領域の桁数を超える。すると、r’(n)の最上位桁のすぐ隣の符号ビットs0と、ひとつ上位の符号ビットs1との値が不一致となる。その結果、r(n)の(s0 xor s1)を見るだけで論理障害の検出が可能になる(証明3終了)。
【0108】
このような判定誤り検出実現に用いられる追加論理回路は、排他的論理和回路(xorゲート)1つだけで実現することができる。
図7は、第4の実施の形態に係る平方根演算器の例を示す図である。平方根演算器には、前処理回路31が設けられている。前処理回路31は、平方根演算対象となる数値の桁合わせ処理などの前処理を行う。前処理回路31の出力信号線は、中間剰余レジスタ32に接続されている。前処理回路31は、桁合わせ後の数値であるOP3を中間剰余レジスタ32に格納する。
【0109】
中間剰余レジスタ32は、中間剰余を格納するレジスタである。例えばIEEE754で定義されている倍精度浮動小数点なら、64ビット幅のレジスタを中間剰余レジスタ32として使用できる。中間剰余レジスタ32の出力信号線は、平方根予測回路33と加算器35とに接続されている。また、中間剰余レジスタ32の出力信号線は、除算器の除算結果として得られる最終剰余の後処理を行う回路(図示せず)に接続されている。
【0110】
平方根予測回路33は、中間剰余レジスタ32に設定された中間剰余に基づいて部分平方根q(n−1)を予測する。ここで平方根予測回路33は、式(24)の演算の結果、|r’(n)−1/kn|<2Q’(n)となる部分平方根q(n−1)を決定する。しかし、平方根予測回路33に論理障害があり、その障害を活性化させるような平方根Q’(n−1)と中間剰余との特別な組み合わせパターンが発生する場合、またはトランジスタセルの固定故障や放射線等の要因によるソフトエラーが発生する場合がある。これらの場合、平方根予測回路33が、|r’(n)−1/kn|<2Q’(n)を満たさない部分平方根q(n−1)を予測する可能性がある。平方根予測回路33の出力信号線は、加算値生成回路34と平方根生成回路36とに接続されている。
【0111】
加算値生成回路34は、中間剰余に加算する値を算出する。具体的には、加算値生成回路34は、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」という演算を行う。この演算により、現在の中間剰余の値から、新たに予測された部分平方根を解の平方根に追加したときの中間剰余を得るのに用いられる、現在の中間剰余への加算値が算出される。現在の中間剰余の値が、新たに予測された部分平方根を解の平方根に追加したときの中間剰余の値より大きければ、加算値生成回路34の演算結果は負の数となる。負の数は2の補数で表現される。加算値生成回路34の演算結果を出力する出力信号線は、加算器35に接続されている。
【0112】
加算器35は、入力された値を加算する。具体的には、加算器35は、中間剰余レジスタ32に格納されている中間剰余と、加算値生成回路34で算出された値とを加算する。加算器35の加算結果を出力する出力信号線は、中間剰余レジスタ32に接続されている。すなわち、加算器35による加算結果が、中間剰余として中間剰余レジスタ32に格納される。なお加算器35は、第1の実施の形態に示した加算器16と同様に、2の補数表現の負の数を加算することで、数値の減算を行うことができる。
【0113】
平方根生成回路36は、平方根予測回路33で決定された部分平方根に基づいて平方根を生成し、出力する。平方根生成回路36の出力信号線は、平方根レジスタ37に接続されている。すなわち、平方根生成回路36で生成された平方根が平方根レジスタ37に書き込まれる。具体的には、平方根生成回路36は、平方根予測回路33で部分平方根が予測されるごとに平方根レジスタ37に格納されている平方根の値を読み込む。次に平方根生成回路36は、平方根レジスタ37から読み込んだ値を所定の桁だけ上位にシフトさせ、空いた下位の桁に平方根予測回路33で決定された部分平方根を加算する。そして平方根生成回路36は、部分平方根を追加した値を平方根レジスタ37に書き込む。
【0114】
平方根レジスタ37は、平方根を記憶するレジスタである。平方根レジスタ37の出力信号線は、平方根生成回路36と加算値生成回路34とに接続されている。また平方根レジスタ37の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0115】
中間剰余レジスタ32には、排他的論理和回路38が接続されている。具体的には、中間剰余レジスタ32内の符号ビットと、符号ビットの上位の1ビットとの出力信号線に、排他的論理和回路38が接続されている。中間剰余レジスタ32と排他的論理和回路38との接続関係は、図3に示した中間剰余レジスタ12と排他的論理和回路19との接続関係と同様である。排他的論理和回路38において、入力された2つのビットの値の排他的論理和演算が行われる。すなわち排他的論理和回路38は、入力された2つのビットの値が同じときに0を出力する。また排他的論理和回路38は、入力された2つのビットの値が異なるときに1を出力する。
【0116】
図7に示すような回路構成により、平方根演算処理が行われる。平方根演算処理が行われる場合、演算対象の数値OP3が前処理回路31に入力される。すると前処理回路31により桁合わせが行われ、桁合わせ後の数値OP3が生成される。数値OP3は、前処理回路31により中間剰余レジスタ32に格納される。
【0117】
次に中間剰余レジスタ32に格納された数値OP3の最上位の桁の部分平方根が、平方根予測回路33により予測される。予測された部分平方根は、加算値生成回路34と平方根生成回路36とに入力される。すると平方根生成回路36により、平方根予測回路33で予測された部分平方根を平方根レジスタ37に格納される。
【0118】
また加算値生成回路34では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路34による演算結果は、加算器35に入力される。加算器35では、中間剰余レジスタ32に格納されている数値OP3に、加算器35の演算結果が加算される。加算結果は中間剰余レジスタ32に書き込まれる。これにより、中間剰余レジスタ32の内容が、数値OP3から中間剰余に更新される。
【0119】
中間剰余レジスタ32の値が更新されると、平方根予測回路33により次の桁の部分平方根が予測される。予測された部分平方根は、加算値生成回路34と平方根生成回路36とに入力される。すると平方根生成回路36により、平方根レジスタ37に格納されている値の下位に、平方根予測回路33で予測された部分平方根が追加される。そして平方根生成回路36により、新たに予測された部分平方根を追加した値が、平方根レジスタ37に格納される。
【0120】
また加算値生成回路34では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路34による演算結果は、加算器35に入力される。加算器35では、中間剰余レジスタ32に格納されている中間剰余に、加算値生成回路34の演算結果が加算される。加算結果は中間剰余レジスタ32に書き込まれる。これにより、中間剰余レジスタ32内の中間剰余の値が更新される。
【0121】
以後同様に、部分平方根の予測と、予測された部分平方根による演算が、必要な桁数の平方根が得られるまで繰り返し実行される。その結果、平方根レジスタ37には、入力された数値OP3の平方根が格納される。また中間剰余レジスタ32には、平方根演算後の剰余が格納される。
【0122】
このような平方根演算の過程において、平方根予測回路33が部分平方根の予測を誤らなければ、中間剰余の符号ビットと拡張符号ビット列の最下位のビットとの値は常に一致する。
【0123】
図8は、部分平方根の判定が正常に行われた平方根演算の例を示す図である。図8の例では、簡単のため、演算対象の数字は8ビットの2進数であるものとする。また、桁合わせは済んでいるものとする。桁合わせ後の数値OP3を「+11111111」とする。この場合、OP3の平方根が、平方根演算器で行われる。
【0124】
図8には、左側に平方根演算過程が示されている。また右側に中間剰余レジスタの内容が示されている。中間剰余レジスタの内容のうち、左端の値が拡張符号ビット列の最後尾のビットの値である。そのビットの右側の値が、符号ビットの値である。中間剰余レジスタの内容のうち、右側の9つの通知が中間剰余ビット列の値である。
【0125】
平方根予測回路33では、平方根の上位の桁から順に1桁ずつ部分平方根が予測される。中間剰余が正の値の間は、符号ビットとその上位のビットとの値が共に0である。中間剰余が負の値になると、符号ビットとその上位のビットとの値が共に1となる。いずれにしても、平方根予測が正しく行われていれば、符号ビットとその上位のビットとの値は一致する。
【0126】
他方、平方根予測回路33に論理障害があったとき、またはトランジスタセルの固定故障や、放射線等の要因によるソフトエラーが発生したとき、平方根演算過程において、平方根予測回路33が部分平方根の予測を誤る場合がある。すなわち、式(24)の演算の結果|r’(n)−1/kn|<2Q’(n)を満たさなくなる部分平方根q(n−1)を、平方根予測回路33が予測する場合がある。その場合、中間剰余のオーバーフローが発生し、符号を設定すべき符号ビットに中間剰余の符号以外の数値が設定されてしまう。すると、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となる。
【0127】
図9は、部分平方根の判定を誤った平方根演算の例を示す図である。図9の例では、上から4桁目の部分平方根の判定を誤った場合を示している。すなわち|r’(n)−1/kn|<2Q’(n)という条件を満たすには部分平方根q(n−1)を1とすべきであるが、平方根予測回路33が部分平方根を0と判定したものとする。
【0128】
すると4桁目の部分平方根を用いて計算した中間剰余が、10桁の数値となり、中間剰余レジスタにおける中間剰余ビット列のビット数を超えている。その結果、オーバーフローが発生する。オーバーフローが発生した結果、算出された中間剰余の最上位の桁の値が、符号ビットに設定されている。その結果、中間剰余が正の値であるにも拘わらず、符号ビットの値が1になっている。他方、拡張符号ビット列の最下位のビットの値は、以前として0である。その結果、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となっている。
【0129】
拡張符号ビット列の最下位のビットと符号ビットとの一致・不一致は、排他的論理和回路38によって検出される。排他的論理和回路38の1の出力信号は、エラー通報を示す情報である。
【0130】
なお、中間剰余が一度発散すると、それ以降どの様な計算が行われるかは不明である。すなわち、図9の右側に示した筆算による計算通りに平方根演算器で計算が続けられるかどうかも不明である。
【0131】
このように、本実施の形態によれば、中間剰余レジスタ32に排他的論理和回路38を接続するだけで、中間剰余のオーバーフローを検出することができる。その結果、平方根予測回路33が平方根予測を誤った場合、エラーを発生させることができる。
【0132】
しかも排他的論理和回路38を追加するだけでよいため、平方根予測の誤り検出機能の追加による回路の大規模化を、最低限におさえることができる。
[第5の実施の形態]
次に第5の実施の形態について説明する。第5の実施の形態は、CSAを用いた平方根演算器である。
【0133】
図10は、第5の実施の形態に係る平方根演算器の例を示す図である。平方根演算器には、前処理回路41が設けられている。前処理回路41は、入力された数値の桁合わせ処理などの前処理を行う。前処理回路41の出力信号線は、2つの中間剰余レジスタ42a,42bに接続されている。前処理回路41は、桁合わせ後の数値OP3を、一方の中間剰余レジスタ42aに格納する。
【0134】
中間剰余レジスタ42a,42bは、中間剰余をサムとキャリーに分けて格納するレジスタである。例えば中間剰余レジスタ42aにサムの値が格納され、中間剰余レジスタ42bにキャリーの値が格納される。中間剰余レジスタ42a,42bの出力信号線は、平方根予測回路43とCSA45とに接続されている。また、中間剰余レジスタ42a,42bの出力信号線は、加算・オーバーフロー検出回路48に接続されている。
【0135】
平方根予測回路43は、中間剰余レジスタ42a,42bにサムとキャリーとに分けて設定された中間剰余に基づいて部分平方根q(n−1)を予測する。平方根予測回路43の出力信号線は、加算値生成回路44と平方根生成回路46とに接続されている。
【0136】
加算値生成回路44は、中間剰余に加算する値を算出する。具体的には、加算値生成回路44は、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算を行う。加算値生成回路44の演算結果を出力する出力信号線は、CSA45に接続されている。
【0137】
CSA45は、入力された値を加算する。CSA45は、入力値の加算処理を行い、部分剰余をサムとキャリーとに欠けて出力する機能を有している。CSAで得られるサムは、加算される値の桁ごとの和であり、繰り上げされる値が無視されている。繰り上げられる値は、キャリーとして出力される。具体的には、CSA45は、中間剰余レジスタ42a,42bに格納されている中間剰余を示すサムとキャリー、および加算値生成回路44で算出された値を加算する。CSA45の加算結果を出力する出力信号線は、中間剰余レジスタ42a,42bに接続されている。CSA45の加算によって得られるサムは、中間剰余レジスタ42aに格納される。またCSA45の加算によって得られるキャリーは、中間剰余レジスタ42bに格納される。
【0138】
平方根生成回路46は、平方根予測回路43で決定された部分平方根に基づいて平方根を生成し、出力する。平方根生成回路46の出力信号線は、平方根レジスタ47に接続されている。
【0139】
平方根レジスタ47は、平方根を記憶するレジスタである。平方根レジスタ47の出力信号線は、平方根生成回路46と加算値生成回路44とに接続されている。また平方根レジスタ47の出力信号線は、最終平方根として後処理を行う回路(図示せず)に接続されている。
【0140】
加算・オーバーフロー検出回路48は、中間剰余レジスタ42a,42bからサムとキャリーとを取得する。そして加算・オーバーフロー検出回路48は、サムとキャリーとを加算し、正しい剰余を生成する。平方根演算処理の途中であれば、加算・オーバーフロー検出回路48で算出される剰余は中間剰余となる。平方根演算処理が終了していれば、加算・オーバーフロー検出回路48で算出される剰余は最終剰余となる。加算・オーバーフロー検出回路48は、算出した最終剰余を、後処理を行う回路(図示せず)に出力する。
【0141】
また加算・オーバーフロー検出回路48は、オーバーフロー検出処理を行う。具体的には、加算・オーバーフロー検出回路48は、算出した剰余の桁数が符号ビットを含めた桁数を超えているか否かを判定し、超えていた場合、エラー検出信号を出力する。
【0142】
図10に示すような回路構成により、平方根演算処理が行われる。平方根演算処理が行われる場合、数値op3が前処理回路41に入力される。すると前処理回路41により桁合わせが行われ、桁合わせ後の数値OP3が生成される。数値OP3は、前処理回路41により中間剰余レジスタ42aに格納される。
【0143】
次に中間剰余レジスタ42aに格納された数値OP3の最上位の桁の部分平方根が、平方根予測回路43により予測される。予測された部分平方根は、加算値生成回路44と平方根生成回路46とに入力される。すると平方根生成回路46により、平方根予測回路43で予測された部分平方根を平方根レジスタ47に格納される。
【0144】
また加算値生成回路44では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路44による演算結果は、CSA45に入力される。CSA45では、中間剰余レジスタ42aに格納されている数値OP3に、加算値生成回路44の演算結果が加算され、サムとキャリーとが出力される。加算結果のうちのサムは中間剰余レジスタ42aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ42bに書き込まれる。
【0145】
中間剰余レジスタ42a,42bの値が更新されると、中間剰余レジスタ42a,42bの値に基づいて、平方根予測回路43により次の桁の部分平方根が予測される。予測された部分平方根は、加算値生成回路44と平方根生成回路46とに入力される。すると平方根生成回路46により、平方根レジスタ47に格納されている値の下位に、平方根予測回路43で予測された部分平方根が追加される。そして平方根生成回路46により、新たに予測された部分平方根を追加した値により、平方根レジスタ47の値が更新される。
【0146】
また加算値生成回路44では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路44による演算結果は、CSA45に入力される。CSA45では、中間剰余レジスタ42aに格納されているサム、中間剰余レジスタ42aに格納されているキャリー、および加算値生成回路44の演算結果が加算される。加算結果のうちのサムは中間剰余レジスタ42aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ42bに書き込まれる。
【0147】
以後同様に、部分平方根の予測と、予測された部分平方根による演算が、必要な桁数の平方根が得られるまで繰り返し実行される。その結果、平方根レジスタ47には、数値OP3で平方根演算したときの平方根が格納される。また中間剰余レジスタ42a,42bには、OP3の平方根を演算したときの剰余が格納される。
【0148】
また、中間剰余レジスタ42a,42bの値が更新された場合、加算・オーバーフロー検出回路48により中間剰余が算出され、オーバーフローの発生の有無が判定される。加算・オーバーフロー検出回路20からエラー検出信号が出力される。平方根演算処理が終了すると、加算・オーバーフロー検出回路48により、中間剰余レジスタ42a,42bの値に基づいて最終剰余が算出される。
【0149】
このように、CSAを用いた平方根演算器においても、中間剰余のオーバーフローを検出できる。その結果、平方根予測回路43による平方根予測に誤りがあった際に、エラー検出信号を出力することができる。
【0150】
[第6の実施の形態]
次に第6の実施の形態について説明する。第6の実施の形態は、第2の実施の形態で示した除算器、および第4の実施の形態で示した平方根演算器を搭載した演算処理装置である。演算処理装置としては、例えばCPUやFPU(Floating point number Processing Unit)がある。
【0151】
図11は、演算処理装置の例を示す図である。図11に示すように演算処理装置50には、除算器51、平方根演算器52、レジスタファイル53およびキャッシュメモリ54が含まれている。除算器51の内部構成は、図2に示した除算器と同様である。平方根演算器52の内部構成は、図7に示した平方根演算器と同様である。また、演算処理装置50は、除算器51または平方根演算器52からエラー信号が出力された場合、エラー処理を行うように構成されている。
【0152】
ここで、レジスタファイル53およびキャッシュメモリ54は、除算器51や平方根演算器52に対して、演算対象となる数値を供給するとともに、除算器51や平方根演算器52の演算結果を格納する記憶装置である。すなわち除算器51および平方根演算器52内の前処理回路は、レジスタファイル53またはキャッシュメモリ54から演算対象となる数値を読み出す。
【0153】
このように、演算処理装置50に、エラー検出機能を有する除算器51や平方根演算器52を搭載することで、演算処理装置50の動作中に部分商や部分平方根の予測誤りが発生しても、確実にエラーを検出することができる。その結果、演算処理装置50の信頼性が向上する。
【0154】
除算器51や平方根演算器52におけるエラー検出回路は、主として排他的論理和回路である。そのため演算処理装置50が、例えばLSIと呼ばれる、高密度配線を有する集積回路であれば、エラー検出回路を追加してもLSIのチップのサイズが肥大化することはない。LSIのサイズが肥大化すると、一枚のシリコンウエハから取れるチップの数が減り、LSIの1つ当たりの製造単価が高くなってしまう。本実施の形態ではチップサイズを肥大化させずにエラー検出回路を組み込めるため、製造コストを増加させずにエラー回路の組み込みが可能である。
【0155】
なお、図11に示した除算器51として、図6に示した除算器を実装することもできる。また、図11に示した平方根演算器52として、図10に示した平方根演算器を実装することもできる。
【0156】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の2以上の構成(特徴)を組み合わせたものであってもよい。
【0157】
以上説明した実施の形態の主な技術的特徴は、以下の付記の通りである。
(付記1) レジスタと、
演算対象となる数値を前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算回路。
【0158】
(付記2) 前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする付記1記載の演算回路。
【0159】
(付記3) 除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする付記1または2記載の演算回路。
【0160】
(付記4) 前記中間値計算回路は、
前記解予測回路で予測された前記部分解と前記除数とを乗算し、乗算結果の符号を反転して加算値を生成する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする付記3記載の演算回路。
【0161】
(付記5) 前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする付記1または2記載の演算回路。
【0162】
(付記6) 前記中間値計算回路は、
前記解予測回路で予測された前記部分解を平方根演算の解に含めた場合の解の自乗と前記演算対象の数値との差分を得るのに用いられる、前記レジスタに格納されている数値への加算値を算出する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする付記5記載の演算回路。
【0163】
(付記7) 前記レジスタは、第1のレジスタと第2のレジスタとの2つであり、
前記解予測回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値に基づいて前記部分解を予測し、
前記中間値計算回路は、前記所定の演算の最終段階で行われる加算における繰り上げを除外した各桁の和を前記第1のレジスタに格納し、最終段階で行われる加算の各桁の繰り上げを示す値を前記第2のレジスタに格納し、
前記エラー検出回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値を加算し、加算結果の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力することを特徴とする付記1記載の演算回路。
【0164】
(付記8) 前記排他的論理和回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記符号ビットの1ビット上位の位置とに接続されていることを特徴とする付記2記載の演算回路。
【0165】
(付記9) 演算対象となる数値を格納する記憶装置と、
レジスタと、
前記演算対象となる数値を、前記記憶装置から読み出し、前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算処理装置。
【0166】
(付記10) 前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする付記9記載の演算処理装置。
【0167】
(付記11) 除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする付記9または10記載の演算処理装置。
【0168】
(付記12) 前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする付記9または10記載の演算処理装置。
【0169】
(付記13) 演算回路の演算処理方法において、
前記演算回路が有する前処理回路が、演算対象となる数値をレジスタに格納するステップと、
前記演算回路が有する解予測回路が、前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測するステップと、
前記演算回路が有する中間値計算回路が、前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納するステップと、
前記演算回路が有する解生成回路が、前記解予測回路で予測された前記部分解を順次取得し、前記解を生成するステップと、
前記演算回路が有するエラー検出回路が、前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するステップと、
を有することを特徴とする演算処理方法。
【符号の説明】
【0170】
1 レジスタ
1a 中間値
1b 拡張符号
2 前処理回路
3 解予測回路
4 中間値計算回路
5 解生成回路
6 エラー検出回路
6a 排他的論理和回路
【技術分野】
【0001】
本発明は、演算回路および演算処理装置ならびに演算処理方法に関する。
【背景技術】
【0002】
論理演算回路には、加減算器、除算器、平方根演算器などがある。電子回路による除算や平方根演算手法としては、引戻し法(復元法・回復型)・引離し法(非回復型)・SRT法などがある。これらの演算アルゴリズムは、商または平方根をn桁(nは自然数)ずつ求める演算を繰り返し行う計算手法である。商または平方根の桁数は、演算の繰り返し回数に比例することが特徴である。以下、このような演算手法は、筆算と同様に減算と桁のシフトとを繰り返すことから、減算シフト型演算と呼ぶことにする。
【0003】
減算シフト型演算回路は、誤作動検出装置で誤作動を検出することで、信頼性を向上させることができる。例えば、被除数および除数が零でないのに、除算装置で求めた商を正規化する前の中間的な商の最上位の桁、および最上位の桁よりも1桁上位の商のあふれの桁の2桁が零の場合、誤作動信号を発生させる誤動作検出回路が考えられている。これにより、商が誤って零になるような誤動作が検出できる。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開昭62−212728号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
ところで、減算シフト型演算論理に発見される論理障害の中には、演算過程で生じる演算データのデータパターンのうち、極めて稀なデータパターンでのみ異常動作をしてしまうものがある。減算シフト型演算回路でこのようなエラーが発生し易い論理的な場所は分かっているが、その部分の論理に間違いがないことを証明する方法が見つかっていない。そのため現状では、極めて稀なデータパターンで発生する論理障害を発見するためには、論理図面などの目視確認と論理シミュレーションによる動作検証実績の積み重ねに頼るしかない。ここで、論理図面などの目視確認による論理障害検出は、論理障害を適切に検出できるか否かが作業者の能力に依存することとなり、確実な信頼性確保手段とはいえない。他方、論理シミュレーションによる論理障害検出は、演算器レベルでの小規模な回路であれば、時間を十分にかけて検証実績を積めば高い信頼性を確保できる。
【0006】
しかし、論理シミュレーションによる動作検証を行ったとしても、回路規模が大きくなると、減算シフト型演算器の十分な信頼性を得ることは困難である。すなわち、大規模システムレベルでの論理シミュレーションや、実機検証では一演算器のチェックにかけられる時間には限界がある。このような時間的制約のため、論理シミュレーションで減算シフト型演算器バグを確実に発見するのは困難である。そのため、演算器の論理品質の向上に限界があった。
【0007】
完全な動作検証による障害の事前回避が困難であったとしても、誤った計算結果を後処理に渡さないようにできれば、信頼性を担保できる。そのため、演算動作中に希に発生する誤動作であっても、その誤動作を確実に検出する技術が求められる。
【0008】
本発明はこのような点に鑑みてなされたものであり、演算動作中に発生する誤動作を確実に検出することができる演算回路および演算処理装置ならびに演算処理方法を提供することを目的とする。
【課題を解決するための手段】
【0009】
上記課題を解決するために、以下の演算回路が提供される。演算回路は、レジスタ、前処理回路、解予測回路、中間値計算回路、解生成回路、およびエラー検出回路を有する。前処理回路は、演算対象となる数値をレジスタに格納する。解予測回路は、レジスタに数値が格納されるごとに、レジスタに格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。中間値計算回路は、解予測回路で予測された部分解を用いた所定の演算により、中間値を示す数値を生成し、中間値に対して符号拡張により拡張符号ビットを付加した数値をレジスタに格納する。解生成回路は、解予測回路で予測された部分解を順次取得し、解を生成する。エラー検出回路は、レジスタに格納された中間値の符号ビットと、拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。
【発明の効果】
【0010】
上記演算回路では、演算動作中に発生する誤作動を確実に検出することができる。
【図面の簡単な説明】
【0011】
【図1】第1の実施の形態に係る演算回路を示す図である。
【図2】第2の実施の形態に係る除算器の例を示す図である。
【図3】中間剰余レジスタと排他的論理和回路との接続例を示す図である。
【図4】部分商の判定が正常に行われた除算の例を示す図である。
【図5】部分商の判定を誤った除算の例を示す図である。
【図6】第3の実施の形態に係る除算器の例を示す図である。
【図7】第4の実施の形態に係る平方根演算器の例を示す図である。
【図8】部分平方根の判定が正常に行われた平方根演算の例を示す図である。
【図9】部分平方根の判定を誤った平方根演算の例を示す図である。
【図10】第5の実施の形態に係る平方根演算器の例を示す図である。
【図11】演算処理装置の例を示す図である。
【発明を実施するための形態】
【0012】
以下、本実施の形態について図面を参照して説明する。
[第1の実施の形態]
図1は、第1の実施の形態に係る演算回路を示す図である。演算回路は、レジスタ1、前処理回路2、解予測回路3、中間値計算回路4、解生成回路5、およびエラー検出回路6を有する。
【0013】
レジスタ1は、少なくとも1つ設けられる。レジスタ1には、中間値計算回路4で生成された中間値1aと、その中間値1aの符号拡張により中間値1aに付与された拡張符号1bが格納される。
【0014】
前処理回路2は、演算対象となる数値をレジスタ1に格納する。例えば除算器を行う場合、前処理回路2は、被除数をレジスタ1に格納する。また演算対象の数値の平方根を演算する場合、前処理回路2は、演算対象の数値をレジスタ1に格納する。なお、除算を行う場合、除数を格納するレジスタを別途設け、前処理回路2は、別途設けたレジスタに除数を格納する。
【0015】
解予測回路3は、レジスタ1に数値が格納されるごとに、レジスタ1に格納された数値に基づいて、演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する。例えば、除算を行う場合、解予測回路3は、商の一部の桁の値である部分商を、上位の桁から順に予測する。また平方根演算を行う場合、解予測回路3は、平方根の一部の桁の値である部分平方根を、上位の桁から順に予測する。
【0016】
中間値計算回路4は、解予測回路3で予測された部分解を用いた所定の演算により、中間値を示す数値を生成する。そして中間値計算回路4は、中間値に対して符号拡張により拡張符号ビットを付加した数値を、レジスタ1に格納する。
【0017】
解生成回路5は、解予測回路3で予測された部分解を順次取得し、解を生成する。例えば、除算が行われた場合、解生成回路5は、解予測回路3から部分商を取得し、商を生成する。また、平方根演算が行われた場合、解生成回路5は、解予測回路3から部分平方根を取得し、平方根を生成する。
【0018】
エラー検出回路6は、レジスタ1に格納された中間値1aの符号ビットと、拡張符号1bのいずれかの拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力する。例えばエラー検出回路6は、レジスタ1における中間値1aの符号ビットの位置と、拡張符号ビットの位置とに接続された排他的論理和回路6aである。排他的論理和回路6aは、レジスタ1から符号ビットと拡張符号ビットとの値を取得し、それらのビットの排他的論理和を出力する。排他的論理和回路6aの出力が1となった場合、その出力信号がエラー信号となる。
【0019】
このような構成の演算回路によれば、前処理回路2によって演算対象となる数値がレジスタ1に格納される。すると、解予測回路3により部分解が予測される。次に解予測回路3で予測された部分解に基づいて、中間値計算回路4で中間値が生成される。生成された中間値は符号拡張され、中間値計算回路4によってレジスタ1に格納される。
【0020】
中間値がレジスタ1に格納されると、その中間値に基づいて、解予測回路3によって既に予測されている桁の下位の桁の部分解が予測される。すると、新たに予測された部分解に基づいて中間値計算回路4で中間値が生成される。生成された中間値は、符号拡張され、レジスタ1に格納される。このような部分解の予測と中間値の更新とが、所定の桁数までの部分解の予測が完了するまで繰り返し実行される。
【0021】
解生成回路5では、解予測回路3で予測された部分解を組み合わせて解が生成される。
また、レジスタ1に中間値が格納されるごとに、エラー検出回路6でエラー検出が行われる。すなわち、解予測が正しく行われている場合、中間値の符号ビットと、符号拡張された拡張符号ビットとは同じ値である。そのため、エラー検出回路6からエラー信号は出力されない。解予測回路3が部分解の予測を誤ると、中間値計算回路4により生成される中間値も誤った値となる。誤った部分解が予測されると、それ以後、解の予測と中間値生成が繰り返されることで、中間値がオーバーフローとなる。中間値がオーバーフローすると、中間値の符号ビットに、中間値の最上位の桁の値が格納される。すると、拡張符号1bと、中間値の符号ビットとの値が不一致となり、エラー検出回路6からエラー信号が出力される。
【0022】
このようにして、解予測回路3の解予測の誤りによるエラーを確実に検出することが可能となる。演算回路に組み込まれたエラー検出回路6でエラーを検出するため、演算回路が稼動していれば常時エラーの有無をチェックできる。すなわち、解予測回路3での解予測の誤りが極めて希にしか発生しない場合でも、実際に発生したときにエラー信号を出力できる。エラー信号が出されれば、解生成回路5で生成された解を使用する後処理回路において、誤った解を使用せずに済む。その結果、演算結果の信頼性が向上する。
【0023】
また、エラー検出回路6で検出されるエラーは、中間値のオーバーフローである。従って、エラー原因の特定が容易になる。
しかも、エラー検出回路6は、例えば排他的論理和回路6aで実現できる。すなわち、極めて少ない論理の追加で障害検出が可能となる。
【0024】
なお、上記の説明では、解予測回路3による部分解の予測の誤りによるエラー発生の事例を説明したが、中間値のオーバーフローは、他の原因でも発生する。例えば、LSI(Large Scale Integration)の初期不良(トランジスタセルの固定故障)や、放射線等の要因によるソフトエラーのために演算が期待通りの動作をしないこともある。このような故障も、中間値のオーバーフローが発生した時点で障害を発見できる。そこで、図1に示した構成の演算回路を製品のLSIに組み込んでおけば、製品の信頼性を向上する。すなわち、RAS(Reliability、Availability、Serviceability)と呼ばれる、信頼性、可用性、保守性が向上する。
【0025】
ここで、図1に示した演算回路は、すべての除算シフト型演算に適用できる。除算シフト型演算としては、除算や平方根演算がある。除算や平方根演算では、解予測回路3の設計にミスが生じやすい。図1に示した演算回路を用いれば、減算シフト型の除算・平方根演算における、回路設計が難しい解予測回路の動作検証が可能となる。その結果、回路設計ミスによるバグの発生を防止できる。
【0026】
なお、図1に示した演算回路と等価の回路を用いて論理シミュレーションを行うことで、論理シミュレーション上でも解予測の誤りを検出可能となる。
また、ソフトウェアにより減算シフト型演算を実行する場合も、エラー検出回路6と同様の処理を行うモジュールをプログラムに追加することで、中間値のオーバーフローを検出できる。
【0027】
このような減算シフト型演算には、例えば除算や平方根演算がある。そこで、以下、除算の例を第2・第3の実施の形態で説明し、平方根演算の例を第4・第5の実施の形態で説明する。
【0028】
[第2の実施の形態]
第2の実施の形態は、誤動作検出が可能な除算器である。
以下の説明では、まず減算シフト型演算の漸化式と一般的な演算方法を説明する。その後、中間剰余の符号ビットの比較が論理チェッカーとして機能する理由を説明する。
【0029】
以下のように記号と言葉を定義する。
・被除数=op1
・除数=op2
・基数=k(=2m:mは自然数)
通常、演算前にop2の最上位桁とOP1の最上位桁の位置合わせ(桁合わせ)が行われる。桁合わせでは、OP1とOP2の最上位桁の位置は一致しているか、またはOP1がOP2より一桁小さい値とされる。このように桁合わせされたop1をOP1、op2をOP2とそれぞれ大文字で書くことにする。桁合わせされた前後における被除数と除数とは、以下の関係式で表されるものとする。
OP1=op1×ka:(aは整数)
OP2=op2×kb:(bは整数)
ここで、上記OP1,OP2を使って、減算シフト型除算は以下の漸化式で定義される。
r(n)=k×r(n−1)−q(n−1)×OP2
r(0)=OP1
・・・(1)
この式(1)より、商および中間剰余が算出される。ただし、|r(n)|<OP2となるように整数q(n−1)を選ぶ。q(n−1)の候補は|q(n−1)|<kを満たす範囲に複数存在することがあるが、そのうち1つを任意に選択すればよい。このときのr(n)をn番目の中間剰余と呼び、q(n−1)を上からn桁目の部分商と呼ぶ。
【0030】
引戻し法(復元法)とはr(n)が常に0または正の数となるように整数q(n−1)を選ぶ計算法である。引離し法とはr(n)が負の数になることも許す計算法である。
SRT法とはr(n)に負の数を許し、かつ|r(n)|<OP2の判定をr(n)の上位数ビットのみから判断する計算法である。なお、SRT法では、実際には|r(n)|<OP2の判定を、その元となる右辺のr(n−1)の上位数ビットから判断される。
【0031】
このように引戻し法であれば、r(n)が常に0または正の数に制限される。この場合、q(n−1)の候補として自動的に0または正の数が唯一に決まる。他方、引離し法やSRT法であれば、r(n)に負の数も許される。この場合、q(n−1)も負の値を取ることがあり、またその候補は複数存在することがある。
【0032】
また、上から1〜n桁目までの商をQ(n)と書くことにし、q(n)を用いてQ(n)を表現すると
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
・・・(2)
と表せる。ただし、この商は桁合わせされた被除数OP1、除数OP2のときの商である。
【0033】
式(1)より
r(n)=k×r(n−1)?q(n−1)×OP2
=k×{k×r(n−2)?q(n−2)×OP2}?q(n−1)×OP2
=k2×r(n−2)?{k×q(n−2)+q(n−1)}×OP2
=k3×r(n−3)?{k2×q(n−3)+k×q(n−2)+q(n−1)}×OP2
:
=kn×r(0)?{kn-1×q(0)+kn-2×q(1)+…+k2×q(n−3)+k×q(n−2)+q(n−1)}×OP2
=kn×r(0)?Q(n)×OP2
・・・(3)
⇔r(0)={Q(n)×OP2+r(n)}/kn
={Q(n)×kb/kn}×op2+r(n)/kn
(OP2=op2×kbより)
・・・(4)
⇔op1={Q(n)×kb/kn+a}×op2+r(n)/kn+a
(r(0)=OP1=op1×kaより)
・・・(5)
式(4)は、式(3)をr(0)について解き、OP2をop2に置き換えたものである。そのため、式(3)と式(4)とは同値(記号⇔で表される)となる。式(5)は、式(4)のr(0)をOP1に置き換え、さらにOP1をop1に置き換えたものである。そのため、式(4)と式(5)とは同値である。
【0034】
被除数op1、除数op2の場合、商と剰余の関係式がop1=商×op2+剰余である。このことと、式(3)、(4)、(5)により、
商=Q(n)×kb/kn+a ・・・(6)
剰余=r(n)/kn+a ・・・(7)
となる。
【0035】
通常、固定小数除算の場合は、上記の商を示す式(6)および剰余を示す式(7)が整数であり続ける最大のnまで式(1)の演算が繰り返される。
浮動小数除算の場合は、Q(n)が必要な桁数(=有効数字+α)に達するまで式(1)の演算を繰り返す。例えばIEEE754で定義されている単精度浮動小数点数なら仮数部23ビットの有効数字、倍精度なら仮数部52ビットの有効数字が使用される。有効数字に必要なビット数に、暗黙の1と呼ばれる整数部1ビットと、丸めに必要な下位数ビットとを加えた合計が、必要な桁数となる。ここで「丸め」とは、数値を一定の規則に従って近似値で表現することであり、例えば有効数字以下の値の四捨五入が行われる。
【0036】
以上が減算シフト型除算についての説明である。この演算を実行する演算回路の論理設計で注意を要するのは、式(1)の演算と、|r(n)|<OP2となるように整数q(n−1)を選ぶ選び方である。
【0037】
特に、論理ミスを起こしやすくその発見が難しいのが|r(n)|<OP2の判定論理である。1990年代には、パーソナルコンピュータで使用されるCPU(Central Processing Unit)の浮動小数点除算にSRT法を用いたが、ある特定の入力値に対して演算結果を誤ることが製品の出荷後に判明し、リコールに至ってしまったという事例もある。この事例においても、|r(n)|<OP2判定を誤ったことが原因である。なお、演算結果を誤る頻度が極めて少ないとしても、演算結果の正しさが保証されていないと科学技術計算に使用できない。そこで、誤った演算結果を後処理に渡さない回路を組み込むことが重要となる。
【0038】
本実施の形態は、|r(n)|<OP2の判定を間違えた場合、判定誤りを検出してエラーを出力するものである。以下、|r(n)|<OP2の判定誤りを検出する論理について説明する。
【0039】
まずは|r(n)|<OP2の判定を間違えた場合、その後の演算の動きがどうなるのかを考察する。
|r(n)|<OP2の判定を間違えると、間違った部分商q(n−1)が選ばれる。すると、それ以降ずっと|r(n)|≧OP2となり、中間剰余が二度と収束しなくなってしまう。その理由は以下の通りである。
|r(n)|≧OP2とすると
|r(n+1)|=|k×r(n)−q(n)×OP2|
≧|k×(±OP2)−q(n)×OP2|
=|±k−q(n)|×OP2
≧OP2(|整数q(n)|<kより)
・・・(8)
式(8)は|r(n)|≧OP2が満たされると、常に|r(n+1)|≧OP2が満たされることを示している。すなわち、一度判定誤りを起こすと、その後も誤り続けることが示されている。
【0040】
一度判定誤りを起こすと、演算は上記のような中間剰余が発散した状態を続ける。多くの場合、または発散した状態による演算を繰り返すうちに、中間剰余の上位ビットがオーバーフロー(桁あふれ)を起こす。中間剰余の上位ビットがオーバーフローを起こすと、演算器の桁数範囲を越えてしまうため、誤った中間剰余(上位ビットが欠損した中間剰余)が発生する。誤った中間剰余が発生すると、それ以降誤った中間剰余と中間商を算出し続ける。このように|r(n)|<OP2の判定誤りが発生すると、中間剰余が発散した状態を続けるか、誤った中間剰余と中間商を算出し続けるかのどちらかである。いずれにせよ商は正しい期待値とは一致しなくなる。
【0041】
本実施の形態では、上記エラー状態のうち特に、中間剰余がオーバーフローしたことを検出することで、判定誤りの発生を検出する。
以下、論理演算が、符号拡張機能を有するディジタル回路によって構成されているものとする。符号拡張とは、符号付の数値を表現するビット列が格納領域のビット幅より短い場合に、空いたビットに適切な値を設定することによって数値としての同一性を維持する手法である。本実施の形態では、符号ビットと同じ値を上位のビットに書き込むことで符号拡張が行われるものとする。
【0042】
演算前の桁合わせにより、式(1)の初期値としての被除数OP1=r(0)とOP2の最上位桁の位置は一致しているか、またはOP1=r(0)がOP2より一桁小さい値となる。それ以降も論理的に間違いがなければ|r(n)|<OP2を満たしながら演算が続く。そのため、r(n)の最上位桁の位置はOP2の最上位桁の位置を超えることはない。よって論理的に間違いがなければOP2の符号ビットの位置は、r(n)にとっても符号ビットの位置となる。符号付きディジタル回路では、符号拡張により、符号ビットの値はその上位に全て同じ値がコピーされる。つまり符号ビットと、符号ビットの上位のビットとを比較すれば必ず同じ値になる。もしも符号ビットと、符号ビットの上位の拡張符号ビットとの値が異なってしまったときは、オーバーフローが発生したことで符合ビットの位置までデータが溢れてきたと判断できる。
【0043】
ここでOP2の最上位桁のすぐ隣の符号ビットの位置(符号ビット列中の最も右側にある符号ビット)をs0、そのひとつ上位の符号ビット(拡張符号ビット)の位置をs1とする。このとき、r(n)の排他的論理和(s0 xor s1)の演算結果を見るだけで論理障害の検出が可能になる。すなわち、問題がない時は排他的論理和(s0 xor s1)=0であり、エラーが発生すれば排他的論理和(s0 xor s1)=1となる。
【0044】
このような判定誤り検出実現に用いられる追加論理回路は、排他的論理和回路(xorゲート)1つだけで実現することができる。
図2は、第2の実施の形態に係る除算器の例を示す図である。除算器には、前処理回路11が設けられている。前処理回路11は、被除数と除数との桁合わせ処理などの前処理を行う。前処理回路11の出力信号線は、中間剰余レジスタ12と除数レジスタ13とに接続されている。前処理回路11は、桁合わせ後の被除数であるOP1を中間剰余レジスタ12に格納する。また、前処理回路11は、桁合わせ後の除数であるOP2を除数レジスタ13に格納する。
【0045】
中間剰余レジスタ12は、中間剰余を格納するレジスタである。例えばIEEE754で定義されている倍精度浮動小数点なら、64ビット幅のレジスタを中間剰余レジスタ12として使用できる。中間剰余レジスタ12の出力信号線は、商予測回路14と加算器16とに接続されている。また、中間剰余レジスタ12の出力信号線は、除算器の除算結果として得られる最終剰余の後処理を行う回路(図示せず)に接続されている。
【0046】
商予測回路14は、中間剰余レジスタ12に設定された中間剰余に基づいて部分商q(n−1)を予測する。ここで商予測回路14は、除数OP2と中間剰余との組み合わせパターンにおいて、式(1)の演算の結果、|r(n)|<OP2となる部分商q(n−1)を決定する。しかし、商予測回路14に論理障害があり、その障害を活性化させるような除数OP2と中間剰余との特別な組み合わせパターンが発生する場合、またはトランジスタセルの固定故障や放射線等の要因によるソフトエラーが発生する場合がある。これらの場合、商予測回路14が、|r(n)|<OP2を満たさない部分商q(n−1)を予測する可能性がある。商予測回路14の出力信号線は、加算値生成回路15と商生成回路17とに接続されている。
【0047】
なお、図2では商予測回路14と除数レジスタ13との接続関係を省略しているが、商予測回路14は除数レジスタ13に格納された除数を参照できる。そして、商予測回路14は、除数を用いて部分商を予測できる。
【0048】
加算値生成回路15は、中間剰余に加算する値を算出する。具体的には、加算値生成回路15は、商予測回路14が予測した部分商q(n−1)に除数レジスタ13から取得した除数OP2を乗算する。加算値生成回路15は乗算結果に−1を乗算する。−1を乗算することで符号が反転される。加算値生成回路15の演算結果を出力する出力信号線は、加算器16に接続されている。
【0049】
加算器16は、入力された値を加算する。具体的には、加算器16は、中間剰余レジスタ12に格納されている中間剰余と、加算値生成回路15で算出された値とを加算する。加算器16の加算結果を出力する出力信号線は、中間剰余レジスタ12に接続されている。すなわち、加算器16による加算結果が、中間剰余として中間剰余レジスタ12に格納される。
【0050】
なお、除数と部分商とが共に正であれば、加算値生成回路15の演算結果は負の値となる。この場合、加算器16における演算は、中間剰余から加算値生成回路15の演算結果の絶対値を減算する演算に等しい。本実施の形態では、負の数を2の補数で表す。2の補数表現は、符号以外の値のバイナリ表現の各ビットを否定(値を反転)させ、1を加えたものである。すなわち加算値生成回路15は、演算結果が負の数であれば、2の補数表現の演算結果を出力する。この場合、加算器16では中間剰余に加算値生成回路15の演算結果を加算し、最上位ビットからのキャリー(1つ上の桁へ繰り上げる数)を無視する。これにより、負の数の加算結果を得ることができる。
【0051】
商生成回路17は、商予測回路14で決定された部分商に基づいて商を生成し、出力する。商生成回路17の出力信号線は、商レジスタ18に接続されている。すなわち、商生成回路17で生成された商が商レジスタ18に書き込まれる。具体的には、商生成回路17は、商予測回路14で部分商が予測されるごとに商レジスタ18に格納されている商の値を読み込む。次に商生成回路17は、商レジスタ18から読み込んだ値を所定の桁だけ上位にシフトさせ、空いた下位の桁に商予測回路14で決定された部分商を加算する。そして商生成回路17は、部分商を追加した値を商レジスタ18に書き込む。
【0052】
商レジスタ18は、商を記憶するレジスタである。商レジスタ18の出力信号線は、商生成回路17に接続されている。また商レジスタ18の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0053】
中間剰余レジスタ12には、排他的論理和回路19が接続されている。具体的には、中間剰余レジスタ12内の符号ビットと、符号ビットの上位の1ビットとの出力信号線に、排他的論理和回路19が接続されている。
【0054】
図3は、中間剰余レジスタと排他的論理和回路との接続例を示す図である。図3の例では、中間剰余レジスタ12は64ビット幅のレジスタである。中間剰余レジスタ12には、下位から順に、丸め用ビット列12a、中間剰余ビット列12b、および拡張符号ビット列12cが設けられている。
【0055】
丸め用ビット列12aは、中間剰余レジスタ12の下位の数ビットである。丸め用ビット列12aには、中間剰余を丸めるために使用する値が設定される。例えば、丸め用ビット列12aとして、中間剰余レジスタ12の下位2ビットが使用される。
【0056】
中間剰余ビット列12bは、丸め用ビット列12aの上位に設けられている。中間剰余ビット列12bには、初期値として被除数OP1が格納される。その後、加算器16による演算が行われるごとに、演算結果が中間剰余として中間剰余ビット列12bに格納される。例えば、中間剰余ビット列12bとして、中間剰余レジスタ12内の53ビット用いられる。
【0057】
中間剰余ビット列12bの最上位ビットは、符号ビット12dである。符号ビットには、中間剰余の符号を示す値が設定される。中間剰余が正の値であれば符号ビットに0が設定され、中間剰余が負の値であれば符号ビットに1が設定される。
【0058】
拡張符号ビット列12cは、中間剰余ビット列12bの上位に設けられている。拡張符号ビット列12cには、拡張符号ビットが格納される。例えば加算器16による演算結果が正の値であれば、拡張符号ビット列12cのすべてのビットに0が設定される。また加算器16による演算結果が負の値であれば、拡張符号ビット列12cのすべてのビットに1が設定される。
【0059】
排他的論理和回路19への入力信号線は、中間剰余ビット列12bの符号ビット12dと、拡張符号ビット列12cの最下位のビット12eとに接続されている。これにより、排他的論理和回路19に符号ビット12dと、符号ビット12dの上位のビット12eとの値が入力される。そして排他的論理和回路19において、入力された2つのビットの値の排他的論理和演算が行われる。すなわち排他的論理和回路19は、入力された2つのビットの値が同じときに0を出力する。また排他的論理和回路19は、入力された2つのビットの値が異なるときに1を出力する。
【0060】
図2、図3に示すような回路構成により、除算処理が行われる。除算処理が行われる場合、被除数op1と除数op2とが前処理回路11に入力される。すると前処理回路11により桁合わせが行われ、桁合わせ後の被除数OP1と除数OP2とが生成される。除数OP1は、前処理回路11により中間剰余レジスタ12に格納される。除数OP2は、前処理回路11により除数レジスタ13に格納される。
【0061】
次に中間剰余レジスタ12に格納された被除数OP1の最上位の桁の部分商が、商予測回路14により予測される。予測された部分商は、加算値生成回路15と商生成回路17とに入力される。すると商生成回路17により、商予測回路14で予測された部分商を商レジスタ18に格納される。
【0062】
また加算値生成回路15では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路15による演算結果は、加算器16に入力される。加算器16では、中間剰余レジスタ12に格納されている被除数OP1に、加算器16の演算結果が加算される。加算結果は中間剰余レジスタ12に書き込まれる。これにより、中間剰余レジスタ12の内容が、被除数OP1から中間剰余に更新される。
【0063】
中間剰余レジスタ12の値が更新されると、商予測回路14により次の桁の部分商が予測される。予測された部分商は、加算値生成回路15と商生成回路17とに入力される。すると商生成回路17により、商レジスタ18に格納されている値の下位に、商予測回路14で予測された部分商が追加される。そして商生成回路17により、新たに予測された部分商を追加した値が商レジスタ18に格納される。
【0064】
また加算値生成回路15では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路15による演算結果は、加算器16に入力される。加算器16では、中間剰余レジスタ12に格納されている中間剰余に、加算値生成回路15の演算結果が加算される。加算結果は中間剰余レジスタ12に書き込まれる。これにより、中間剰余レジスタ12内の中間剰余の値が更新される。
【0065】
以後同様に、部分商の予測と、予測された部分商による演算が、必要な桁数の商が得られるまで繰り返し実行される。その結果、商レジスタ18には、被除数OP1を除数OP2で除算したときの商が格納される。また中間剰余レジスタ12には、被除数OP1を除数OP2で除算したときの剰余が格納される。
【0066】
このような除算の過程において、商予測回路14が部分商の予測を誤らなければ、拡張符号ビット列12cの最下位のビット12eと符号ビット12dとの値は常に一致する。
図4は、部分商の判定が正常に行われた除算の例を示す図である。図4の例では、簡単のため、数字は8ビットの2進数であるものとする。また、桁合わせは済んでいるものとする。桁合わせ後の被除数OP1を「+11000000」、除数OP2を「+10000001」とする。この場合、OP1÷OP2=(+11000000)÷(+10000001)という除算が除算器で行われる。
【0067】
図4には、左側に除算過程が示されている。また右側に中間剰余レジスタの内容が示されている。中間剰余レジスタの内容のうち、左端の値が拡張符号ビット列の最後尾のビットの値である。そのビットの右側の値が、符号ビットの値である。中間剰余レジスタの内容のうち、右側の8つの通知が中間剰余ビット列の値である。
【0068】
商予測回路14では、商の上位の桁から順に1桁ずつ部分商が予測される。中間剰余が正の値の間は、符号ビットとその上位のビットとの値が共に0である。中間剰余が負の値になると、符号ビットとその上位のビットとの値が共に1となる。いずれにしても、商予測が正しく行われていれば、符号ビットとその上位のビットとの値は一致する。
【0069】
他方、商予測回路14に論理障害があったとき、またはトランジスタセルの固定故障や、放射線等の要因によるソフトエラーが発生したとき、除算過程において、商予測回路14が部分商の予測を誤る場合がある。すなわち、式(1)の演算の結果|r(n)|<OP2を満たさなくなる部分商q(n−1)を、商予測回路14が予測する場合がある。その場合、中間剰余のオーバーフローが発生し、符号を設定すべき符号ビット12dに中間剰余の符号以外の数値が設定されてしまう。すると、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となる。
【0070】
図5は、部分商の判定を誤った除算の例を示す図である。図5の例では、上から4桁目の部分商の判定を誤った場合を示している。すなわち|r(n)|<OP2という条件を満たすには部分商q(n−1)を1とすべきであるが、商予測回路14が部分商を0と判定したものとする。
【0071】
すると4桁目の部分商を用いて計算した中間剰余が、除数OP2よりも大きくなる。図5の例では、4桁目の部分商を用いて計算した中間剰余は9桁の数値となっており、中間剰余レジスタにおける中間剰余ビット列のビット数を超えている。その結果、中間剰余が発散し、オーバーフローが発生する。オーバーフローが発生した結果、算出された中間剰余の最上位の桁の値が、符号ビットに設定されている。その結果、中間剰余が正の値であるにも拘わらず、符号ビットの値が1になっている。他方、拡張符号ビット列の最下位のビットの値は、以前として0である。その結果、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となっている。
【0072】
拡張符号ビット列の最下位のビットと符号ビットとの一致・不一致は、排他的論理和回路19によって検出される。排他的論理和回路19の1の出力信号は、エラー通報を示す情報である。
【0073】
なお、中間剰余が一度発散すると、それ以降どの様な計算が行われるかは不明である。すなわち、図5の右側に示した筆算による計算通りに除算器で計算が続けられるかどうかも不明である。
【0074】
このように、本実施の形態によれば、中間剰余レジスタ12に排他的論理和回路19を接続するだけで、中間剰余のオーバーフローを検出することができる。その結果、商予測回路14が商予測を誤った場合、エラーを発生させることができる。
【0075】
しかも排他的論理和回路19を追加するだけでよいため、商予測の誤り検出機能の追加による回路の大規模化を、最低限におさえることができる。
[第3の実施の形態]
次に第3の実施の形態について説明する。第3の実施の形態は、CSA(Carry Save Adder)を用いた除算器である。
【0076】
図6は、第3の実施の形態に係る除算器の例を示す図である。除算器には、前処理回路21が設けられている。前処理回路21は、被除数と除数との桁合わせ処理などの前処理を行う。前処理回路21の出力信号線は、2つの中間剰余レジスタ22a,22bと除数レジスタ23とに接続されている。前処理回路21は、桁合わせ後の被除数であるOP1を、一方の中間剰余レジスタ22aに格納する。また、前処理回路21は、桁合わせ後の除数であるOP2を除数レジスタ23に格納する。
【0077】
中間剰余レジスタ22a,22bは、中間剰余をサムとキャリーに分けて格納するレジスタである。例えば中間剰余レジスタ22aにサムの値が格納され、中間剰余レジスタ22bにキャリーの値が格納される。中間剰余レジスタ22a,22bの出力信号線は、商予測回路24とCSA26とに接続されている。また、中間剰余レジスタ22a,22bの出力信号線は、加算・オーバーフロー検出回路29に接続されている。
【0078】
商予測回路24は、中間剰余レジスタ22a,22bにサムとキャリーとに分けて設定された中間剰余に基づいて部分商q(n−1)を予測する。商予測回路24の出力信号線は、加算値生成回路25と商生成回路27とに接続されている。
【0079】
なお、図6では商予測回路24と除数レジスタ23との接続関係を省略しているが、商予測回路24は除数レジスタ23に格納された除数を参照できる。そして、商予測回路24は、除数を用いて部分商を予測できる。
【0080】
加算値生成回路25は、中間剰余に加算する値を算出する。具体的には、加算値生成回路25は、商予測回路24が予測した部分商q(n−1)に除数レジスタ23から取得した除数OP2を乗算する。加算値生成回路25の演算結果を出力する出力信号線は、CSA26に接続されている。
【0081】
CSA26は、入力された値を加算する。CSA26は、入力値の加算処理を行い、部分剰余をサムとキャリーとに欠けて出力する機能を有している。CSAで得られるサムは、加算される値の桁ごとの和であり、繰り上げされる値が無視されている。繰り上げられる値は、キャリーとして出力される。具体的には、CSA26は、中間剰余レジスタ22a,22bに格納されている中間剰余を示すサムとキャリー、および加算値生成回路25で算出された値を加算する。CSA26の加算結果を出力する出力信号線は、中間剰余レジスタ22a,22bに接続されている。CSA26の加算によって得られるサムは、中間剰余レジスタ22aに格納される。またCSA26の加算によって得られるキャリーは、中間剰余レジスタ22bに格納される。
【0082】
商生成回路27は、商予測回路24で決定された部分商に基づいて商を生成し、出力する。商生成回路27の出力信号線は、商レジスタ28に接続されている。
商レジスタ28は、商を記憶するレジスタである。商レジスタ28の出力信号線は、商生成回路27に接続されている。また商レジスタ28の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0083】
加算・オーバーフロー検出回路29は、中間剰余レジスタ22a,22bからサムとキャリーとを取得する。そして加算・オーバーフロー検出回路29は、サムとキャリーとを加算し、正しい剰余を生成する。除算処理の途中であれば、加算・オーバーフロー検出回路29で算出される剰余は中間剰余となる。除算処理が終了していれば、加算・オーバーフロー検出回路29で算出される剰余は最終剰余となる。加算・オーバーフロー検出回路29は、算出した最終剰余を、後処理を行う回路(図示せず)に出力する。
【0084】
また加算・オーバーフロー検出回路29は、オーバーフロー検出処理を行う。具体的には、加算・オーバーフロー検出回路29は、算出した剰余の桁数が符号ビットを含めた桁数を超えているか否かを判定し、超えていた場合、エラー検出信号を出力する。
【0085】
図6に示すような回路構成により、除算処理が行われる。除算処理が行われる場合、被除数op1と除数op2とが前処理回路21に入力される。すると前処理回路21により桁合わせが行われ、桁合わせ後の被除数OP1と除数OP2とが生成される。除数OP1は、前処理回路21により中間剰余レジスタ22aに格納される。除数OP2は、前処理回路21により除数レジスタ13に格納される。
【0086】
次に中間剰余レジスタ22aに格納された被除数OP1の最上位の桁の部分商が、商予測回路24により予測される。予測された部分商は、加算値生成回路25と商生成回路27とに入力される。すると商生成回路27により、商予測回路24で予測された部分商を商レジスタ28に格納される。
【0087】
また加算値生成回路25では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路25による演算結果は、CSA26に入力される。CSA26では、中間剰余レジスタ22aに格納されている被除数OP1に、加算値生成回路25の演算結果が加算され、サムとキャリーとが出力される。加算結果のうちのサムは中間剰余レジスタ22aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ22bに書き込まれる。
【0088】
中間剰余レジスタ22a,22bの値が更新されると、中間剰余レジスタ22a,22bの値に基づいて、商予測回路24により次の桁の部分商が予測される。予測された部分商は、加算値生成回路25と商生成回路27とに入力される。すると商生成回路27により、商レジスタ28に格納されている値の下位に、商予測回路24で予測された部分商が追加される。そして商生成回路27により、新たに予測された部分商を追加した値により、商レジスタ28の値が更新される。
【0089】
また加算値生成回路25では、入力された部分商と除数OP2とが乗算され、さらに乗算結果の符号が反転される。加算値生成回路25による演算結果は、CSA26に入力される。CSA26では、中間剰余レジスタ22aに格納されているサム、中間剰余レジスタ22aに格納されているキャリー、および加算値生成回路25の演算結果が加算される。加算結果のうちのサムは中間剰余レジスタ22aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ22bに書き込まれる。
【0090】
以後同様に、部分商の予測と、予測された部分商による演算が、必要な桁数の商が得られるまで繰り返し実行される。その結果、商レジスタ28には、被除数OP1を除数OP2で除算したときの商が格納される。また中間剰余レジスタ22a,22bには、被除数OP1を除数OP2で除算したときの剰余が格納される。
【0091】
また、中間剰余レジスタ22a,22bの値が更新された場合、加算・オーバーフロー検出回路29により中間剰余が算出され、オーバーフローの発生の有無が判定される。加算・オーバーフロー検出回路20からエラー検出信号が出力される。除算処理が終了すると、加算・オーバーフロー検出回路29により、中間剰余レジスタ22a,22bの値に基づいて最終剰余が算出される。
【0092】
このように、CSAを用いた除算器においても、中間剰余のオーバーフローを検出できる。その結果、商予測回路24による商予測に誤りがあった際に、エラー検出信号を出力することができる。
【0093】
[第4の実施の形態]
次に第4の実施の形態について説明する。第4の実施の形態は、平方根演算器(開平回路)における解予測の誤りを検出するものである。以下、除算の場合と同様に、まず減算シフト型演算の漸化式と一般的な演算方法を説明する。その後、中間剰余の符号ビットの比較が論理チェッカーとして機能する理由を説明する。
【0094】
なお以下の説明では、平方根演算の対象として入力された数値と、計算途中の平方根の解の自乗との差分を、中間剰余と呼ぶこととする。また、平方根演算の対象として入力された数値と、平方根演算終了時の平方根の解の自乗との差分を最終剰余と呼ぶこととする。さらに平方根演算においても、中間剰余の符号拡張が行われる。また負の数は、2の補数で表現される。
【0095】
平方根演算では入力される数値は1つのみである。入力された数値をop3とし、op3の平方根を求めるものとする。この場合、桁合わせされたOP3をOP3と書くことにし、以下の関係式で表されるものとする。
OP3=op3×kb:bは整数
除算の商の場合と同様に、1〜n桁目までの平方根Q(n)を、n桁目の部分平方根q(n)を用いて表すと、
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
・・・(9)
である。ここで、Q(0)=0と定義する。
【0096】
この式(9)を変形すると以下の関係が得られる。
Q(n)=q(0)×kn-1+q(1)×kn-2+…+q(n−2)×k+q(n−1)
=k{q(0)×kn-2+q(1)×kn-3+…+q(n−2)}+q(n−1)
=k×Q(n−1)+q(n−1)
・・・(10)
上記OP3、Q(n)を使って、減算シフト型の平方根演算は以下の漸化式で定義される。
r(n)=k2×r(n−1)−2k×Q(n−1)×q(n−1)−q2(n−1)
r(0)=OP3
・・・(11)
r(n)は、n番目の中間剰余である。式(11)の証明については後述する(証明1)。
【0097】
ただし、|r(n)−1|<2Q(n)となるように整数q(n−1)を選ぶ。q(n−1)の候補は|q(n−1)|<kを満たす範囲に複数存在することがあるが、そのうち1つを任意に選択すればよい。すなわち、q(n−1)の算出に用いられる判定不等式が|r(n)−1|<2Q(n)である。判定不等式が|r(n)−1|<2Q(n)であることの証明については、後述する(証明2)。
【0098】
よって除算と同様に考えれば、中間剰余r(n)の最上位桁のすぐ隣の符号ビットの位置(符号ビットの最も右側)をs0、そのひとつ上位の符号ビットの位置をs1としたとき、r(n)の(s0 xor s1)を見るだけで論理障害の検出が可能になる。問題がない時は(s0 xor s1)=0であり、エラーが発生すれば(s0 xor s1)=1となる。エラーが発生すれば(s0 xor s1)=1となることの証明については、後述する(証明3)。
【0099】
次に、平方根演算が式(11)で表されることを証明する(証明1)。
Q2(n)≒(OP3に桁合わせを行った値)=(r(0)に桁合わせを行った値)である。すると、r(n)は、r(0)とQ2(n)とを用いて、以下のような差分の式で書くことができる。
r(n)=k2n×r(0)−Q2(n) ・・・(12)
さらに式(10)より、
r(n)=k2n×r(0)−{k×Q(n−1)+q(n−1)}2
=k2n×r(0)−{k2×Q2(n−1)+2k×Q(n−1)×q(n−1)+q2(n−1)}
=k2×{k2(n−1)×r(0)−Q2(n−1)}−2k×Q(n−1)×q(n−1)−q2(n−1)
=k2×r(n−1)−2k×Q(n−1)×q(n−1)−q2(n−1)
・・・(13)
となる。このようにして式(11)が導かれる(証明1終了)。
【0100】
次にq(n−1)算出に用いられる判定不等式が|r(n)−1|<2Q(n)であることを証明する(証明2)。
|r(n)−1|<2Q(n) ⇔ −2Q(n)+1<r(n)<2Q(n)+1
・・・(14)
ここでn≧1でr(n−1)が式(14)の不等式を満たしたとき、r(n)においても式(14)が成立することを示す。具体的には、「n=1」のときに式(14)が成立すること、および「n>1」のときにr(n−1)が成立すれば必ずr(n)が成立することを証明する。
【0101】
まず「n=1」のときを考える。
Q(1)=q(0)>0であり、|k×√(OP3)−q(0)|<1となるようにq(0)が選ばれているはずである。これは、k×√(OP3)とq(0)の最上位の桁が合うように桁合わせがされており、その整数部分が一致するようにq(0)を選んでいるからである。
【0102】
よって
−1<k×√(OP3)−q(0)<1
⇔−1<k×√(r(0))−q(0)<1
・・・(15)
式(15)の連立不等式の左側より
0<k×√(r(0))−q(0)+1
⇔0<(k×√(r(0))+q(0)−1)(k×√(r(0))−q(0)+1)
⇔0<k2×r(0)−(q(0)−1)2
⇔0<k2×r(0)−q2(0)+2q(0)−1
⇔−2q(0)<k2×r(0)−q2(0)−1
・・・(16)
同じく式(15)の連立不等式の右側より
k×√(r(0))−q(0)−1<0
⇔(k×√(r(0))+q(0)+1)(k×√(r(0))−q(0)−1)<0
⇔k2×r(0)−(q(0)+1)2<0
⇔k2×r(0)−q2(0)−2q(0)−1<0
⇔k2×r(0)−q2(0)−1<2q(0)
・・・(17)
q(0)>0であることと、式(16)、式(17)の結果を合わせると、
|k2×r(0)?q2(0)?1|<2q(0)
⇔|r(1)?1|<2Q(1) ・・・(18)
となり、n=1のときで式(14)が成立する。
【0103】
次に「−2Q(n−1)+1<r(n−1)」が満たされれば、「−2Q(n)+1<r(n)」が満たされることを証明する。
r(n)=k2×r(n−1)?2k×Q(n−1)×q(n−1)?q2(n−1)
>k2×{−2Q(n−1)+1}?2k×Q(n−1)×q(n−1)?q2(n−1)
=−2kQ(n−1)×{k+q(n−1)}+{k+q(n−1)}×{k−q(n−1)}
={k+q(n−1)}×{−2k×Q(n−1)+k−q(n−1)}
={k+q(n−1)}×[−2{k×Q(n−1)+2q(n−1)}+k+q(n−1)]
={k+q(n−1)}×{−2Q(n)+k+q(n−1)}
・・・(19)
式(19)の右辺はr(n)の下限であるから、ここがどのような値を取ってもr(n)はその値より大きい。よって右辺が最も大きくなるようにq(n−1)を選ぶと、q(n−1)=−(k−1)となる。その理由は以下の通りである。
【0104】
−2Q(n)+k+q(n−1)<0であり、1≦k+q(n−1)≦2k−1である。そのため、q(n−1)=−(k−1)で右辺{k+q(n−1)}×{−2Q(n)+k+q(n−1)}は最大となる。
【0105】
よってq(n−1)=−(k−1)を式(19)の右辺に代入して以下の式となる。
r(n)>−2Q(n)+1 ・・・(20)
さらに「r(n−1)<2Q(n−1)+1」が満たされれば、「r(n)<2Q(n)+1」が満たされることを証明する。
r(n)=k2×r(n−1)?2k×Q(n−1)×q(n−1)?q2(n−1)
<k2×{2Q(n−1)+1}?2k×Q(n−1)×q(n−1)?q2(n−1)
=2kQ(n−1)×{k−q(n−1)}+{k+q(n−1)}×{k−q(n−1)}
={k−q(n−1)}×{2k×Q(n−1)+k+q(n−1)}
={k−q(n−1)}×[2{k×Q(n−1)+2q(n−1)}+k−q(n−1)]
={k−q(n−1)}×{2Q(n)+k−q(n−1)}
・・・(21)
ここで式(21)の右辺が最も小さくなるようにq(n−1)を選ぶと、q(n−1)=k−1となる。よって
r(n)<2Q(n)+1 ・・・(22)
が得られる。式(20)と式(22)との連立不等式は、|r(n)−1|<2Q(n)と同値である。従って、「n>1」の場合に、r(n−1)が式(14)の不等式を満たしたとき、r(n)においても式(14)が満たされる。
【0106】
以上より、「n≧1」のすべてのnの場合に、式(14)の不等式が満たされる(証明2終了)。
次に、エラーが発生すれば(s0 xor s1)=1となることについて証明する(証明3)。
【0107】
式(11)で定義される平方根演算の方法は、Q(n)、r(n)が整数で表せるように各数式を定義している。ただし、その副作用として最上位桁の位置が演算回数に比例して上に移動してしまう。実際のハードで実現する場合には、最上位の位置が固定されるように以下の漸化式に置き換えて行うのが普通である。
r’(n)=r(n)/kn
Q’(n)=Q(n)/kn
・・・(23)
とし、式(11)の両辺をknで割る。
r’(n)=k×r’(n−1)−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)
r(0)=OP3
・・・(24)
すると、整数q(n−1)選択に用いられる判定式は|r’(n)−1/kn|<2Q’(n)となる。この判定式を満たさないq(n−1)が選択されると、繰り返し部分平方根の予測を行ううちに、式(24)におけるr’(n)の演算結果がオーバーフローする。すなわち、r’(n)の演算結果の桁数が、r’(n)の格納領域の桁数を超える。すると、r’(n)の最上位桁のすぐ隣の符号ビットs0と、ひとつ上位の符号ビットs1との値が不一致となる。その結果、r(n)の(s0 xor s1)を見るだけで論理障害の検出が可能になる(証明3終了)。
【0108】
このような判定誤り検出実現に用いられる追加論理回路は、排他的論理和回路(xorゲート)1つだけで実現することができる。
図7は、第4の実施の形態に係る平方根演算器の例を示す図である。平方根演算器には、前処理回路31が設けられている。前処理回路31は、平方根演算対象となる数値の桁合わせ処理などの前処理を行う。前処理回路31の出力信号線は、中間剰余レジスタ32に接続されている。前処理回路31は、桁合わせ後の数値であるOP3を中間剰余レジスタ32に格納する。
【0109】
中間剰余レジスタ32は、中間剰余を格納するレジスタである。例えばIEEE754で定義されている倍精度浮動小数点なら、64ビット幅のレジスタを中間剰余レジスタ32として使用できる。中間剰余レジスタ32の出力信号線は、平方根予測回路33と加算器35とに接続されている。また、中間剰余レジスタ32の出力信号線は、除算器の除算結果として得られる最終剰余の後処理を行う回路(図示せず)に接続されている。
【0110】
平方根予測回路33は、中間剰余レジスタ32に設定された中間剰余に基づいて部分平方根q(n−1)を予測する。ここで平方根予測回路33は、式(24)の演算の結果、|r’(n)−1/kn|<2Q’(n)となる部分平方根q(n−1)を決定する。しかし、平方根予測回路33に論理障害があり、その障害を活性化させるような平方根Q’(n−1)と中間剰余との特別な組み合わせパターンが発生する場合、またはトランジスタセルの固定故障や放射線等の要因によるソフトエラーが発生する場合がある。これらの場合、平方根予測回路33が、|r’(n)−1/kn|<2Q’(n)を満たさない部分平方根q(n−1)を予測する可能性がある。平方根予測回路33の出力信号線は、加算値生成回路34と平方根生成回路36とに接続されている。
【0111】
加算値生成回路34は、中間剰余に加算する値を算出する。具体的には、加算値生成回路34は、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」という演算を行う。この演算により、現在の中間剰余の値から、新たに予測された部分平方根を解の平方根に追加したときの中間剰余を得るのに用いられる、現在の中間剰余への加算値が算出される。現在の中間剰余の値が、新たに予測された部分平方根を解の平方根に追加したときの中間剰余の値より大きければ、加算値生成回路34の演算結果は負の数となる。負の数は2の補数で表現される。加算値生成回路34の演算結果を出力する出力信号線は、加算器35に接続されている。
【0112】
加算器35は、入力された値を加算する。具体的には、加算器35は、中間剰余レジスタ32に格納されている中間剰余と、加算値生成回路34で算出された値とを加算する。加算器35の加算結果を出力する出力信号線は、中間剰余レジスタ32に接続されている。すなわち、加算器35による加算結果が、中間剰余として中間剰余レジスタ32に格納される。なお加算器35は、第1の実施の形態に示した加算器16と同様に、2の補数表現の負の数を加算することで、数値の減算を行うことができる。
【0113】
平方根生成回路36は、平方根予測回路33で決定された部分平方根に基づいて平方根を生成し、出力する。平方根生成回路36の出力信号線は、平方根レジスタ37に接続されている。すなわち、平方根生成回路36で生成された平方根が平方根レジスタ37に書き込まれる。具体的には、平方根生成回路36は、平方根予測回路33で部分平方根が予測されるごとに平方根レジスタ37に格納されている平方根の値を読み込む。次に平方根生成回路36は、平方根レジスタ37から読み込んだ値を所定の桁だけ上位にシフトさせ、空いた下位の桁に平方根予測回路33で決定された部分平方根を加算する。そして平方根生成回路36は、部分平方根を追加した値を平方根レジスタ37に書き込む。
【0114】
平方根レジスタ37は、平方根を記憶するレジスタである。平方根レジスタ37の出力信号線は、平方根生成回路36と加算値生成回路34とに接続されている。また平方根レジスタ37の出力信号線は、最終商として後処理を行う回路(図示せず)に接続されている。
【0115】
中間剰余レジスタ32には、排他的論理和回路38が接続されている。具体的には、中間剰余レジスタ32内の符号ビットと、符号ビットの上位の1ビットとの出力信号線に、排他的論理和回路38が接続されている。中間剰余レジスタ32と排他的論理和回路38との接続関係は、図3に示した中間剰余レジスタ12と排他的論理和回路19との接続関係と同様である。排他的論理和回路38において、入力された2つのビットの値の排他的論理和演算が行われる。すなわち排他的論理和回路38は、入力された2つのビットの値が同じときに0を出力する。また排他的論理和回路38は、入力された2つのビットの値が異なるときに1を出力する。
【0116】
図7に示すような回路構成により、平方根演算処理が行われる。平方根演算処理が行われる場合、演算対象の数値OP3が前処理回路31に入力される。すると前処理回路31により桁合わせが行われ、桁合わせ後の数値OP3が生成される。数値OP3は、前処理回路31により中間剰余レジスタ32に格納される。
【0117】
次に中間剰余レジスタ32に格納された数値OP3の最上位の桁の部分平方根が、平方根予測回路33により予測される。予測された部分平方根は、加算値生成回路34と平方根生成回路36とに入力される。すると平方根生成回路36により、平方根予測回路33で予測された部分平方根を平方根レジスタ37に格納される。
【0118】
また加算値生成回路34では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路34による演算結果は、加算器35に入力される。加算器35では、中間剰余レジスタ32に格納されている数値OP3に、加算器35の演算結果が加算される。加算結果は中間剰余レジスタ32に書き込まれる。これにより、中間剰余レジスタ32の内容が、数値OP3から中間剰余に更新される。
【0119】
中間剰余レジスタ32の値が更新されると、平方根予測回路33により次の桁の部分平方根が予測される。予測された部分平方根は、加算値生成回路34と平方根生成回路36とに入力される。すると平方根生成回路36により、平方根レジスタ37に格納されている値の下位に、平方根予測回路33で予測された部分平方根が追加される。そして平方根生成回路36により、新たに予測された部分平方根を追加した値が、平方根レジスタ37に格納される。
【0120】
また加算値生成回路34では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路34による演算結果は、加算器35に入力される。加算器35では、中間剰余レジスタ32に格納されている中間剰余に、加算値生成回路34の演算結果が加算される。加算結果は中間剰余レジスタ32に書き込まれる。これにより、中間剰余レジスタ32内の中間剰余の値が更新される。
【0121】
以後同様に、部分平方根の予測と、予測された部分平方根による演算が、必要な桁数の平方根が得られるまで繰り返し実行される。その結果、平方根レジスタ37には、入力された数値OP3の平方根が格納される。また中間剰余レジスタ32には、平方根演算後の剰余が格納される。
【0122】
このような平方根演算の過程において、平方根予測回路33が部分平方根の予測を誤らなければ、中間剰余の符号ビットと拡張符号ビット列の最下位のビットとの値は常に一致する。
【0123】
図8は、部分平方根の判定が正常に行われた平方根演算の例を示す図である。図8の例では、簡単のため、演算対象の数字は8ビットの2進数であるものとする。また、桁合わせは済んでいるものとする。桁合わせ後の数値OP3を「+11111111」とする。この場合、OP3の平方根が、平方根演算器で行われる。
【0124】
図8には、左側に平方根演算過程が示されている。また右側に中間剰余レジスタの内容が示されている。中間剰余レジスタの内容のうち、左端の値が拡張符号ビット列の最後尾のビットの値である。そのビットの右側の値が、符号ビットの値である。中間剰余レジスタの内容のうち、右側の9つの通知が中間剰余ビット列の値である。
【0125】
平方根予測回路33では、平方根の上位の桁から順に1桁ずつ部分平方根が予測される。中間剰余が正の値の間は、符号ビットとその上位のビットとの値が共に0である。中間剰余が負の値になると、符号ビットとその上位のビットとの値が共に1となる。いずれにしても、平方根予測が正しく行われていれば、符号ビットとその上位のビットとの値は一致する。
【0126】
他方、平方根予測回路33に論理障害があったとき、またはトランジスタセルの固定故障や、放射線等の要因によるソフトエラーが発生したとき、平方根演算過程において、平方根予測回路33が部分平方根の予測を誤る場合がある。すなわち、式(24)の演算の結果|r’(n)−1/kn|<2Q’(n)を満たさなくなる部分平方根q(n−1)を、平方根予測回路33が予測する場合がある。その場合、中間剰余のオーバーフローが発生し、符号を設定すべき符号ビットに中間剰余の符号以外の数値が設定されてしまう。すると、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となる。
【0127】
図9は、部分平方根の判定を誤った平方根演算の例を示す図である。図9の例では、上から4桁目の部分平方根の判定を誤った場合を示している。すなわち|r’(n)−1/kn|<2Q’(n)という条件を満たすには部分平方根q(n−1)を1とすべきであるが、平方根予測回路33が部分平方根を0と判定したものとする。
【0128】
すると4桁目の部分平方根を用いて計算した中間剰余が、10桁の数値となり、中間剰余レジスタにおける中間剰余ビット列のビット数を超えている。その結果、オーバーフローが発生する。オーバーフローが発生した結果、算出された中間剰余の最上位の桁の値が、符号ビットに設定されている。その結果、中間剰余が正の値であるにも拘わらず、符号ビットの値が1になっている。他方、拡張符号ビット列の最下位のビットの値は、以前として0である。その結果、拡張符号ビット列の最下位のビットと符号ビットとの値が不一致となっている。
【0129】
拡張符号ビット列の最下位のビットと符号ビットとの一致・不一致は、排他的論理和回路38によって検出される。排他的論理和回路38の1の出力信号は、エラー通報を示す情報である。
【0130】
なお、中間剰余が一度発散すると、それ以降どの様な計算が行われるかは不明である。すなわち、図9の右側に示した筆算による計算通りに平方根演算器で計算が続けられるかどうかも不明である。
【0131】
このように、本実施の形態によれば、中間剰余レジスタ32に排他的論理和回路38を接続するだけで、中間剰余のオーバーフローを検出することができる。その結果、平方根予測回路33が平方根予測を誤った場合、エラーを発生させることができる。
【0132】
しかも排他的論理和回路38を追加するだけでよいため、平方根予測の誤り検出機能の追加による回路の大規模化を、最低限におさえることができる。
[第5の実施の形態]
次に第5の実施の形態について説明する。第5の実施の形態は、CSAを用いた平方根演算器である。
【0133】
図10は、第5の実施の形態に係る平方根演算器の例を示す図である。平方根演算器には、前処理回路41が設けられている。前処理回路41は、入力された数値の桁合わせ処理などの前処理を行う。前処理回路41の出力信号線は、2つの中間剰余レジスタ42a,42bに接続されている。前処理回路41は、桁合わせ後の数値OP3を、一方の中間剰余レジスタ42aに格納する。
【0134】
中間剰余レジスタ42a,42bは、中間剰余をサムとキャリーに分けて格納するレジスタである。例えば中間剰余レジスタ42aにサムの値が格納され、中間剰余レジスタ42bにキャリーの値が格納される。中間剰余レジスタ42a,42bの出力信号線は、平方根予測回路43とCSA45とに接続されている。また、中間剰余レジスタ42a,42bの出力信号線は、加算・オーバーフロー検出回路48に接続されている。
【0135】
平方根予測回路43は、中間剰余レジスタ42a,42bにサムとキャリーとに分けて設定された中間剰余に基づいて部分平方根q(n−1)を予測する。平方根予測回路43の出力信号線は、加算値生成回路44と平方根生成回路46とに接続されている。
【0136】
加算値生成回路44は、中間剰余に加算する値を算出する。具体的には、加算値生成回路44は、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算を行う。加算値生成回路44の演算結果を出力する出力信号線は、CSA45に接続されている。
【0137】
CSA45は、入力された値を加算する。CSA45は、入力値の加算処理を行い、部分剰余をサムとキャリーとに欠けて出力する機能を有している。CSAで得られるサムは、加算される値の桁ごとの和であり、繰り上げされる値が無視されている。繰り上げられる値は、キャリーとして出力される。具体的には、CSA45は、中間剰余レジスタ42a,42bに格納されている中間剰余を示すサムとキャリー、および加算値生成回路44で算出された値を加算する。CSA45の加算結果を出力する出力信号線は、中間剰余レジスタ42a,42bに接続されている。CSA45の加算によって得られるサムは、中間剰余レジスタ42aに格納される。またCSA45の加算によって得られるキャリーは、中間剰余レジスタ42bに格納される。
【0138】
平方根生成回路46は、平方根予測回路43で決定された部分平方根に基づいて平方根を生成し、出力する。平方根生成回路46の出力信号線は、平方根レジスタ47に接続されている。
【0139】
平方根レジスタ47は、平方根を記憶するレジスタである。平方根レジスタ47の出力信号線は、平方根生成回路46と加算値生成回路44とに接続されている。また平方根レジスタ47の出力信号線は、最終平方根として後処理を行う回路(図示せず)に接続されている。
【0140】
加算・オーバーフロー検出回路48は、中間剰余レジスタ42a,42bからサムとキャリーとを取得する。そして加算・オーバーフロー検出回路48は、サムとキャリーとを加算し、正しい剰余を生成する。平方根演算処理の途中であれば、加算・オーバーフロー検出回路48で算出される剰余は中間剰余となる。平方根演算処理が終了していれば、加算・オーバーフロー検出回路48で算出される剰余は最終剰余となる。加算・オーバーフロー検出回路48は、算出した最終剰余を、後処理を行う回路(図示せず)に出力する。
【0141】
また加算・オーバーフロー検出回路48は、オーバーフロー検出処理を行う。具体的には、加算・オーバーフロー検出回路48は、算出した剰余の桁数が符号ビットを含めた桁数を超えているか否かを判定し、超えていた場合、エラー検出信号を出力する。
【0142】
図10に示すような回路構成により、平方根演算処理が行われる。平方根演算処理が行われる場合、数値op3が前処理回路41に入力される。すると前処理回路41により桁合わせが行われ、桁合わせ後の数値OP3が生成される。数値OP3は、前処理回路41により中間剰余レジスタ42aに格納される。
【0143】
次に中間剰余レジスタ42aに格納された数値OP3の最上位の桁の部分平方根が、平方根予測回路43により予測される。予測された部分平方根は、加算値生成回路44と平方根生成回路46とに入力される。すると平方根生成回路46により、平方根予測回路43で予測された部分平方根を平方根レジスタ47に格納される。
【0144】
また加算値生成回路44では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路44による演算結果は、CSA45に入力される。CSA45では、中間剰余レジスタ42aに格納されている数値OP3に、加算値生成回路44の演算結果が加算され、サムとキャリーとが出力される。加算結果のうちのサムは中間剰余レジスタ42aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ42bに書き込まれる。
【0145】
中間剰余レジスタ42a,42bの値が更新されると、中間剰余レジスタ42a,42bの値に基づいて、平方根予測回路43により次の桁の部分平方根が予測される。予測された部分平方根は、加算値生成回路44と平方根生成回路46とに入力される。すると平方根生成回路46により、平方根レジスタ47に格納されている値の下位に、平方根予測回路43で予測された部分平方根が追加される。そして平方根生成回路46により、新たに予測された部分平方根を追加した値により、平方根レジスタ47の値が更新される。
【0146】
また加算値生成回路44では、「−2×Q’(n−1)×q(n−1)−(1/kn)×q2(n−1)」の演算が行われる。加算値生成回路44による演算結果は、CSA45に入力される。CSA45では、中間剰余レジスタ42aに格納されているサム、中間剰余レジスタ42aに格納されているキャリー、および加算値生成回路44の演算結果が加算される。加算結果のうちのサムは中間剰余レジスタ42aに書き込まれる。また加算結果のうちのキャリーは中間剰余レジスタ42bに書き込まれる。
【0147】
以後同様に、部分平方根の予測と、予測された部分平方根による演算が、必要な桁数の平方根が得られるまで繰り返し実行される。その結果、平方根レジスタ47には、数値OP3で平方根演算したときの平方根が格納される。また中間剰余レジスタ42a,42bには、OP3の平方根を演算したときの剰余が格納される。
【0148】
また、中間剰余レジスタ42a,42bの値が更新された場合、加算・オーバーフロー検出回路48により中間剰余が算出され、オーバーフローの発生の有無が判定される。加算・オーバーフロー検出回路20からエラー検出信号が出力される。平方根演算処理が終了すると、加算・オーバーフロー検出回路48により、中間剰余レジスタ42a,42bの値に基づいて最終剰余が算出される。
【0149】
このように、CSAを用いた平方根演算器においても、中間剰余のオーバーフローを検出できる。その結果、平方根予測回路43による平方根予測に誤りがあった際に、エラー検出信号を出力することができる。
【0150】
[第6の実施の形態]
次に第6の実施の形態について説明する。第6の実施の形態は、第2の実施の形態で示した除算器、および第4の実施の形態で示した平方根演算器を搭載した演算処理装置である。演算処理装置としては、例えばCPUやFPU(Floating point number Processing Unit)がある。
【0151】
図11は、演算処理装置の例を示す図である。図11に示すように演算処理装置50には、除算器51、平方根演算器52、レジスタファイル53およびキャッシュメモリ54が含まれている。除算器51の内部構成は、図2に示した除算器と同様である。平方根演算器52の内部構成は、図7に示した平方根演算器と同様である。また、演算処理装置50は、除算器51または平方根演算器52からエラー信号が出力された場合、エラー処理を行うように構成されている。
【0152】
ここで、レジスタファイル53およびキャッシュメモリ54は、除算器51や平方根演算器52に対して、演算対象となる数値を供給するとともに、除算器51や平方根演算器52の演算結果を格納する記憶装置である。すなわち除算器51および平方根演算器52内の前処理回路は、レジスタファイル53またはキャッシュメモリ54から演算対象となる数値を読み出す。
【0153】
このように、演算処理装置50に、エラー検出機能を有する除算器51や平方根演算器52を搭載することで、演算処理装置50の動作中に部分商や部分平方根の予測誤りが発生しても、確実にエラーを検出することができる。その結果、演算処理装置50の信頼性が向上する。
【0154】
除算器51や平方根演算器52におけるエラー検出回路は、主として排他的論理和回路である。そのため演算処理装置50が、例えばLSIと呼ばれる、高密度配線を有する集積回路であれば、エラー検出回路を追加してもLSIのチップのサイズが肥大化することはない。LSIのサイズが肥大化すると、一枚のシリコンウエハから取れるチップの数が減り、LSIの1つ当たりの製造単価が高くなってしまう。本実施の形態ではチップサイズを肥大化させずにエラー検出回路を組み込めるため、製造コストを増加させずにエラー回路の組み込みが可能である。
【0155】
なお、図11に示した除算器51として、図6に示した除算器を実装することもできる。また、図11に示した平方根演算器52として、図10に示した平方根演算器を実装することもできる。
【0156】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の2以上の構成(特徴)を組み合わせたものであってもよい。
【0157】
以上説明した実施の形態の主な技術的特徴は、以下の付記の通りである。
(付記1) レジスタと、
演算対象となる数値を前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算回路。
【0158】
(付記2) 前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする付記1記載の演算回路。
【0159】
(付記3) 除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする付記1または2記載の演算回路。
【0160】
(付記4) 前記中間値計算回路は、
前記解予測回路で予測された前記部分解と前記除数とを乗算し、乗算結果の符号を反転して加算値を生成する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする付記3記載の演算回路。
【0161】
(付記5) 前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする付記1または2記載の演算回路。
【0162】
(付記6) 前記中間値計算回路は、
前記解予測回路で予測された前記部分解を平方根演算の解に含めた場合の解の自乗と前記演算対象の数値との差分を得るのに用いられる、前記レジスタに格納されている数値への加算値を算出する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする付記5記載の演算回路。
【0163】
(付記7) 前記レジスタは、第1のレジスタと第2のレジスタとの2つであり、
前記解予測回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値に基づいて前記部分解を予測し、
前記中間値計算回路は、前記所定の演算の最終段階で行われる加算における繰り上げを除外した各桁の和を前記第1のレジスタに格納し、最終段階で行われる加算の各桁の繰り上げを示す値を前記第2のレジスタに格納し、
前記エラー検出回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値を加算し、加算結果の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力することを特徴とする付記1記載の演算回路。
【0164】
(付記8) 前記排他的論理和回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記符号ビットの1ビット上位の位置とに接続されていることを特徴とする付記2記載の演算回路。
【0165】
(付記9) 演算対象となる数値を格納する記憶装置と、
レジスタと、
前記演算対象となる数値を、前記記憶装置から読み出し、前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算処理装置。
【0166】
(付記10) 前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする付記9記載の演算処理装置。
【0167】
(付記11) 除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする付記9または10記載の演算処理装置。
【0168】
(付記12) 前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする付記9または10記載の演算処理装置。
【0169】
(付記13) 演算回路の演算処理方法において、
前記演算回路が有する前処理回路が、演算対象となる数値をレジスタに格納するステップと、
前記演算回路が有する解予測回路が、前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測するステップと、
前記演算回路が有する中間値計算回路が、前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納するステップと、
前記演算回路が有する解生成回路が、前記解予測回路で予測された前記部分解を順次取得し、前記解を生成するステップと、
前記演算回路が有するエラー検出回路が、前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するステップと、
を有することを特徴とする演算処理方法。
【符号の説明】
【0170】
1 レジスタ
1a 中間値
1b 拡張符号
2 前処理回路
3 解予測回路
4 中間値計算回路
5 解生成回路
6 エラー検出回路
6a 排他的論理和回路
【特許請求の範囲】
【請求項1】
レジスタと、
演算対象となる数値を前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算回路。
【請求項2】
前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする請求項1記載の演算回路。
【請求項3】
除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする請求項1または2記載の演算回路。
【請求項4】
前記中間値計算回路は、
前記解予測回路で予測された前記部分解と前記除数とを乗算し、乗算結果の符号を反転して加算値を生成する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする請求項3記載の演算回路。
【請求項5】
前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする請求項1または2記載の演算回路。
【請求項6】
前記中間値計算回路は、
前記解予測回路で予測された前記部分解を平方根演算の解に含めた場合の解の自乗と前記演算対象の数値との差分を得るのに用いられる、前記レジスタに格納されている数値への加算値を算出する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする請求項5記載の演算回路。
【請求項7】
前記レジスタは、第1のレジスタと第2のレジスタとの2つであり、
前記解予測回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値に基づいて前記部分解を予測し、
前記中間値計算回路は、前記所定の演算の最終段階で行われる加算における繰り上げを除外した各桁の和を前記第1のレジスタに格納し、最終段階で行われる加算の各桁の繰り上げを示す値を前記第2のレジスタに格納し、
前記エラー検出回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値を加算し、加算結果の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力することを特徴とする請求項1記載の演算回路。
【請求項8】
前記排他的論理和回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記符号ビットの1ビット上位の位置とに接続されていることを特徴とする請求項2記載の演算回路。
【請求項9】
演算対象となる数値を格納する記憶装置と、
レジスタと、
前記演算対象となる数値を、前記記憶装置から読み出し、前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算処理装置。
【請求項10】
前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする請求項9記載の演算処理装置。
【請求項11】
演算回路の演算処理方法において、
前記演算回路が有する前処理回路が、演算対象となる数値をレジスタに格納するステップと、
前記演算回路が有する解予測回路が、前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測するステップと、
前記演算回路が有する中間値計算回路が、前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納するステップと、
前記演算回路が有する解生成回路が、前記解予測回路で予測された前記部分解を順次取得し、前記解を生成するステップと、
前記演算回路が有するエラー検出回路が、前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するステップと、
を有することを特徴とする演算処理方法。
【請求項1】
レジスタと、
演算対象となる数値を前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算回路。
【請求項2】
前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする請求項1記載の演算回路。
【請求項3】
除算における除数を格納する除数レジスタを更に有し、
前記前処理回路は、除算における被除数を前記レジスタに格納し、除算における前記除数を前記除数レジスタに格納し、
前記解予測回路は、前記被除数を前記除数で除算した商の前記部分解を予測し、
前記中間値計算回路は、前記レジスタに格納された数値から、前記解予測回路で予測された前記部分解と前記除数との乗算結果を減算して中間剰余を生成し、前記中間剰余を前記中間値とすることを特徴とする請求項1または2記載の演算回路。
【請求項4】
前記中間値計算回路は、
前記解予測回路で予測された前記部分解と前記除数とを乗算し、乗算結果の符号を反転して加算値を生成する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする請求項3記載の演算回路。
【請求項5】
前記前処理回路は、平方根演算における演算対象の数値を前記レジスタに格納し、
前記解予測回路は、前記演算対象の数値の平方根の前記部分解を予測することを特徴とする請求項1または2記載の演算回路。
【請求項6】
前記中間値計算回路は、
前記解予測回路で予測された前記部分解を平方根演算の解に含めた場合の解の自乗と前記演算対象の数値との差分を得るのに用いられる、前記レジスタに格納されている数値への加算値を算出する加算値生成回路と、
前記加算値生成回路で生成された前記加算値を、前記レジスタ内の数値に加算する加算器と、
を有することを特徴とする請求項5記載の演算回路。
【請求項7】
前記レジスタは、第1のレジスタと第2のレジスタとの2つであり、
前記解予測回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値に基づいて前記部分解を予測し、
前記中間値計算回路は、前記所定の演算の最終段階で行われる加算における繰り上げを除外した各桁の和を前記第1のレジスタに格納し、最終段階で行われる加算の各桁の繰り上げを示す値を前記第2のレジスタに格納し、
前記エラー検出回路は、前記第1のレジスタと前記第2のレジスタとに格納された数値を加算し、加算結果の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力することを特徴とする請求項1記載の演算回路。
【請求項8】
前記排他的論理和回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記符号ビットの1ビット上位の位置とに接続されていることを特徴とする請求項2記載の演算回路。
【請求項9】
演算対象となる数値を格納する記憶装置と、
レジスタと、
前記演算対象となる数値を、前記記憶装置から読み出し、前記レジスタに格納する前処理回路と、
前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測する解予測回路と、
前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納する中間値計算回路と、
前記解予測回路で予測された前記部分解を順次取得し、前記解を生成する解生成回路と、
前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するエラー検出回路と、
を有することを特徴とする演算処理装置。
【請求項10】
前記エラー検出回路は、前記レジスタにおける前記中間値の前記符号ビットの位置と、前記拡張符号ビットの位置とに接続された排他的論理和回路であることを特徴とする請求項9記載の演算処理装置。
【請求項11】
演算回路の演算処理方法において、
前記演算回路が有する前処理回路が、演算対象となる数値をレジスタに格納するステップと、
前記演算回路が有する解予測回路が、前記レジスタに数値が格納されるごとに、前記レジスタに格納された数値に基づいて、前記演算対象となる数値の解の一部の桁の値である部分解を、上位の桁から順に予測するステップと、
前記演算回路が有する中間値計算回路が、前記解予測回路で予測された前記部分解を用いた所定の演算により、中間値を示す数値を生成し、前記中間値に対して符号拡張により拡張符号ビットを付加した数値を前記レジスタに格納するステップと、
前記演算回路が有する解生成回路が、前記解予測回路で予測された前記部分解を順次取得し、前記解を生成するステップと、
前記演算回路が有するエラー検出回路が、前記レジスタに格納された前記中間値の符号ビットと、前記拡張符号ビットとの値を比較し、不一致の場合にエラー信号を出力するステップと、
を有することを特徴とする演算処理方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2011−8649(P2011−8649A)
【公開日】平成23年1月13日(2011.1.13)
【国際特許分類】
【出願番号】特願2009−153130(P2009−153130)
【出願日】平成21年6月29日(2009.6.29)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成23年1月13日(2011.1.13)
【国際特許分類】
【出願日】平成21年6月29日(2009.6.29)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]