JP3689183B2 - 正確な浮動小数点除算／平方根演算を実現する正確、かつ効果的なスティッキー・ビット計算 - Google Patents
正確な浮動小数点除算／平方根演算を実現する正確、かつ効果的なスティッキー・ビット計算 Download PDFInfo
- Publication number
- JP3689183B2 JP3689183B2 JP16750896A JP16750896A JP3689183B2 JP 3689183 B2 JP3689183 B2 JP 3689183B2 JP 16750896 A JP16750896 A JP 16750896A JP 16750896 A JP16750896 A JP 16750896A JP 3689183 B2 JP3689183 B2 JP 3689183B2
- Authority
- JP
- Japan
- Prior art keywords
- bit
- carry
- sum
- zero
- partial remainder
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/535—Dividing only
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
- G06F7/552—Powers or roots, e.g. Pythagorean sums
- G06F7/5525—Roots or inverse roots of single operands
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/483—Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers
- G06F7/487—Multiplying; Dividing
- G06F7/4873—Dividing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/499—Denomination or exception handling, e.g. rounding or overflow
- G06F7/49942—Significance control
- G06F7/49947—Rounding
- G06F7/49952—Sticky bit
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Optimization (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
- Executing Machine-Instructions (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明はマイクロプロセッサ内の浮動小数点除算器（Floating point dividers）の分野、より詳細には、ＳＲＴ除算／平方根演算のインプリメンテーション（SRT division/square root implementation）における商デジット選択規則（Quotient digit selection rules）に関し、同規則は結果が正確な場合、負の最終部分剰余（Negative final partial remainders）の形成を防止する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
ＳＲＴアルゴリズムは引き放し法除算（Non-restoring division）を実行する１つの方法を提供する。この詳細については、１９５８年９月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）第Ｃ−７巻２１８〜２２２頁に記載されているジェイ．イー．ロバートソンによる“デジタル除算法の新たなクラス”と、１９５８年に発行されたメカニカル応用数学誌（Quart. J. Mech. Appl. Math.）第１１刊第３部３６４〜３８４頁に記載されているケー．ディー．トーチャーによる“自動２進コンピュータのための乗算及び除算技術”を参照のこと。デジタル除算では、オペランドとして除数及び被除数が使用され、かつ出力として商が形成される。複数の商デジットは反復計算され、同商デジットのうちの最上位商デジットが最初に形成される。ＳＲＴ除算は他の除算アルゴリズムとは異なる。ＳＲＴ除算では、連続する各商デジットは上位の僅かな部分剰余デジットのみに基づいて公式化され、非常に多くのデジットを含み得る部分剰余全体に基づいて公式化されることはない。全ての反復において、正確な商デジットの選択は部分剰余全体を考慮せずには保証できない。このため、ＳＲＴアルゴリズムは不正確な商デジットを時々形成する。しかし、ＳＲＴアルゴリズムは正、ゼロ及び負の各商デジットの可能性を提供する。商デジットを１つの反復において過大予測した場合、誤りは負の商デジットを選択することにより、次の反復において補正される。ＳＲＴ除算では、商デジットを過小予測してはならない。即ち、商デジットは常に過大予測するか、または正確に予測する必要がある。全ての商デジットを過小予測しなかった場合、部分剰余は所定の上下限内に維持され、正確な最終商の計算が可能になる。ＳＲＴアルゴリズムは負の商デジットの形成を可能にする。このため、一般的に最終商出力は通常の除算のように全商デジットを単に連結するのではなく、寧ろ商デジットの重み付け加算及び減算を介して行われる。
【０００３】
基数が更に大きい場合、１つの反復において形成される商デジットの数が更に多くなる。これは複雑さを増大させる。基数２のインプリメンテーションは１つのデジットを１つの反復において形成する。基数４のインプリメンテーションは２つのデジットを１つの反復において形成する。図１はＳＲＴに基づく基数２を使用する簡単な浮動小数点インプリメンテーション（Simple SRT radix-2 floating point implementation）を示す。同インプリメンテーションは、除数及び被除数の両方が正であって、かつ正規化されていることを要する。従って、１／２≦Ｄ、被除数＜１となる。シフトされた最初の部分剰余（Initial shifted partial remainder）、即ち２ＰＲ［０］は被除数である。第１商デジットの計算の反復（First quotient digit calculation iteration）開始前に、被除数は部分剰余レジスタ１００に対してロードされる。この結果、最初の部分剰余は被除数となる。その後、反復によって形成される部分剰余は以下の数式１に基づいて形成される。
【０００４】
【数１】
数式１において、ｑi+1は商デジットであって、−１，０または＋１の値を有し得る。商デジットｑi+1は直前の部分剰余の値に基づいて単独で決定され、かつ除数から独立している。商選択ロジック１０２は部分剰余のうちの上位４ビットのみを入力され、そして商デジットを形成する。除算では、全ての反復において除数は一定に維持される。しかし、平方根演算は各反復後に除数レジスタ１０１内に格納された除数に対する調整を一般的に含む。従って、商デジットが除数から独立していることは平方根演算における魅力的な特徴である。
【０００５】
部分剰余は一般的に冗長桁上げ保留の形態に維持される。この結果、次の部分剰余の計算では、更に処理速度が遅く、かつ大きい桁上げ伝搬加算器に代えて桁上げ保留加算器の使用が可能である。部分剰余は全ての反復が実施され、かつ所望の精度に達した後で、非冗長形態（Non-redundant form）へ変換される。ＳＲＴアルゴリズムは商デジットの過大予測を可能にする。商デジットの過大予測により、負の部分剰余が続いて形成される。このため、最終部分剰余を負にすべく最後の商デジットを過大予測し得る。この場合、過大予測に対する補正が不可能なため、Ｑ及びＱ−１の維持が必要である。この結果、最終部分剰余が負である場合、Ｑ−１がＱに代えて選択される。商デジットは常には冗長形態に維持され、さらには最後の反復において非冗長形態へ変換される。これに代えて、商（即ちＱ）と、商−１（即ちＱ−１）とを１９９２年１２月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）第４１巻第１２号の１４９７〜１５０３頁に記載されているエム．ディ．エルセゴバック及びティ．ラングによる“オン・ザ・フライ・ラウンディング（On-the-fly rounding）”に開示されている規則に基づいてフライ（Fly）上に形成し得る。
【０００６】
ＳＲＴアルゴリズムは平方根演算にも適用される。これにより、従来の除算ハードウェアの使用が可能である。簡略化された平方根の式は除算の式に類似している。これについては、１９９０年８月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）の第３９巻第８号の１０１６〜１０２４頁に記載されているエム．ディ．エルセゴバック及びティ．ラングによる“初期ＰＬＡを伴わない基数４を使用した平方根演算（Radix-4 square root without initial PLA）”を参照のこと。平方根演算の反復方程式を以下の数式２に示す。
【０００７】
【数２】
数式２において、括弧内の項は有効除数である。平方根演算において、除数はＱiの関数であり、同Ｑiは直前の全ルート・デジット（Previous root digits）ｑ1〜ｑiの関数である。用語の一貫性を維持すべく、ルート・デジットを商デジットと称する。従って、除算で使用するハードウェアと同一のハードウェアを使用する平方根演算を実現すべく、オン・ザ・フライ商形成（On-the-fly quotient generation）は各反復後の除数の更新に必要である。
【０００８】
２進法の除算アルゴリズムはグラマー・スクールで教授されている標準的な十進法の除算に類似している。Ｒ／Ｄ＝Ｑにおいて、Ｑに対する各商デジットが予測される。第１商デジットを決定すべく、商デジットの適切な予測値に対して除数が掛けられる。次いで、その積は剰余を形成すべく被除数から引かれる。剰余が除数より更に大きい場合、商デジットの予測値は過小である。更に、剰余が負である場合、商デジットの予測値は過大である。いづれにしても、商デジットの予測値が誤っている場合、予測値の変更が必要である。この結果、正確な商デジットは次のデジットへ進む前に導き出される。次の関係、即ち０≦ＰＲ＜Ｄが正しい場合、商デジットは正しい。ここで、ＰＲは除数を掛けた商デジットを引いた後の部分剰余を示す。
【０００９】
ＳＲＴ除算アルゴリズムの鍵としては、負の商デジットを使用し得る点が挙げられる。例えば、基数１０において、商デジットは標準デジット０〜９に加えて、−１〜−９の値を有し得る。６００÷４０の除算演算を以下に例示する。各反復において、正しい商デジットを選択した場合、正しい結果は１５になる。しかし、正しいデジットである１に代えて、商デジットとして２が第１の反復中に選択されたと仮定する。第１の商デジットとして２を選択した後の部分剰余は６００−（２＊４０＊１０1）＝−２００である。ＳＲＴ除算では、このエラーを補正すべくバックアップを行い、かつ第１の反復を繰り返すことはない。寧ろ、エラーは次の反復において補正可能である。ＳＲＴ除算に基づき、第２の商デジットとして−５を正しく予測したと仮定する。反復後、部分剰余は−２００−（−５＊４０＊１０0）＝０となる。反復後の部分剰余がゼロの場合、残りの全てのデジットの正しい値はゼロになる。従って、計算結果は（２＊１０1）＋（−５＊１０0）＝１５となり、同計算結果は正しい。従って、ＳＲＴアルゴリズムは、後から１つ以上の負の商デジットを選択することにより、任意の商デジットの過大予測の補正を可能にする。その後の部分剰余を実質的にゼロまで削減すべく、予測された商デジットから正しい商デジットを引いた値が１を上回ってはならない。商デジットの予測における誤りが＋１を上回ることを許容した場合、−９を下回る商デジット（例：−１０、−１１等）が底１０において必要とされる。同様に、商デジットの範囲はＳＲＴアルゴリズムに基づいて正の方向へ拡大されることはない。このため、正しい商デジットの過小予測は致命的である。これは部分剰余が基数を掛けた除数より更に大きく、かつその後、底１０において９を上回る商デジット（例：１０、１１等）を必要とすることに起因する。従って、部分剰余を所定の上下限内に維持するために、商デジット選択において、正しい商デジットを過小予測してはならない。更に、商デジット選択において商デジットが過大予測された場合、予測された商デジットから正しい商デジットを引いた値は１を上回ってはならない。
【００１０】
部分剰余を所定の上下限内に維持するための前記の基準を全ての部分剰余デジットを使用することなく満足させ得る点が保証される。正しい演算結果の算出を可能にする商デジットを選択するためには、部分剰余のうちの上位の僅かなデジットのみを使用すればよい。
【００１１】
ＳＲＴ除算は冗長商表示を負以外のデジットのみを有する標準的な非冗長形態まで削減するために、全ての商デジットの選択後に最終加算を要する。
最近の電子計算回路に用いられる２進法（底２）では、ＳＲＴ除算は＋１、０または−１の商デジットを提供する。商選択デジットを形成するロジック１０２はＳＲＴ除算インプリメンテーションの中心エレメントである。初期のリサーチは冗長部分剰余のうちの上位３ビットのみが基数２を使用する商デジット選択関数（Radix-2 quotient digit selection function）に必要な入力であることを示している（１９８３年に発行された米国電気電子学会第６回コンピュータ計算シンポジウムの予稿集（Proc. Sixth IEEE Symp. Comput. Arithmetic.）の９９〜１０２頁に記載されているエス．マジェルスキーによる“高速デジタル回路のための平方根アルゴリズム”と、１９８６年１０月に発行された米国電気電子学会の固体回路ジャーナル（IEEE J. Solid-State Circuits.）第ＳＣ−２１巻第５番の８１４〜８１９頁に記載されているディー．ズラス及びダブリュ．マックアリスターによるＶＬＳＩにおける平衡遅延ツリー及び組合せ除算を参照）。しかし、更に最近の研究結果は、商デジット選択デジットを正しく形成し、かつ部分剰余を所定の上下限内に維持するために４ビットを要する点を指摘している（１９９４年にクルワー・アカデミック出版社（Kluwer Academic Publishers）から発行されたエム．ディー．エルセゴバック及びティー．ラングによる除算及び平方根演算：デジット漸化アルゴリズム及びインプリメンテーション（Division and Square Root: Digit-recurrence Algorithms and Implementations）ｃｈ．３と、１９８５年８月に発行された米国電気電子学会コンピュータ部会会報第Ｃ−３４巻第８号の７２４〜７３３頁に記載のエス．マジェルスキーによる“高速デジタル回路のための平方根アルゴリズム”と、１９９１年に発行された米国電気電子学会第１０回コンピュータ計算シンポジウムの予稿集の２０２〜２０９頁に記載のピー．モンツシ及びエル．シミニエラによる“幾つかの加算工程の省略をともなう基数２を使用する簡単な除算及び平方根演算”と、１９８７年に発行された米国電気電子学会第８回コンピュータ計算シンポジウムの予稿集の９５〜１０１頁に記載のブイ．ペング、エス．サムドララ及びエム．ガブリエロフによる“浮動小数点ユニットにおけるシフター、乗算器及び除算器のインプリメンテーション”とを参照）。従来の商デジット選択規則は以下の数式３によって表すことができる。ここで、ＰＲは実際の部分剰余のうちの上位４ビットを示し、１０進小数点は上位の第３デジット及び第４デジットの間に位置する。部分剰余は２の補数であり、第１ビットは符合ビットとなる。
【００１２】
【数３】
部分剰余はレジスタ１００内に桁上げ保留の形態で格納されている。このため、実際の上位４ビットは部分剰余の桁上げ部分及び和部分の桁上げ伝搬全加算（Full carry propagate addition of the carry and sum portions of the partial remainder）を行わずには得られない。部分剰余のうちの上位４ビットを計算すべく各反復中に桁上げ伝搬全加算の実施を回避することが望ましい。このため、商デジット選択規則は予測部分剰余を使用して形成できる。
【００１３】
予測部分剰余（ＰＲest）は４ビット桁上げ伝搬加算器のみを用いて計算できる。４ビット桁上げ伝搬加算器は実際の部分剰余のうちの桁上げ部分及び和部分の上位４ビットを加算する。実際の部分剰余のうちの上位４ビットの計算には、５９ビット桁上げ伝搬全加算を要する。従って、この簡略化は待ち時間の大きな節約を意味する。予測部分剰余ＰＲestは５９ビット桁上げ伝搬全加算を実施した場合に、予測部分剰余のうちの最下位ビット位置に一致するビット位置へ桁上げが伝搬される可能性を示していない。表１は基数２を使用する従来の商選択の真理値表である。予測部分剰余の上位４ビットは正しい商デジットを選択すべく使用される。従って、以下の真理値表は真の部分剰余の上位４ビットが予測部分剰余の上位４ビットとは異なり得るという事実を考慮している。
【００１４】
【表１】
表１の真理値表において、２ＰＲestを示す４ビットは部分剰余の上位４つの桁上げビット及び和ビット（Carry and sum bits）の非冗長表示である。第４ビットは少数部である。従って、部分剰余の上位４ビットの導出演繹は１／２である。
【００１５】
商選択ロジックは０に代えて１、または−１に代えて０を予測する等、真の商結果を正しく予測するか、または過大予測すべく設計されている。ＳＲＴアルゴリズムは誤った商デジットを選択した場合、後から自身を補正する。
【００１６】
部分剰余は−５／２≦２ＰＲ［ｉ］≦３／２に制限される。このため、ＳＲＴに基づく基数２を使用する商選択ロジック（SRT radix-2 quotient selection logic）に関する従来の真理値表は幾つかのドントケア・インプット（Don't care inputs）を有する。下位ビットが無視されるため、予測部分剰余は常に真の部分剰余の最も重要な上位ビットより少ないか、または同上位ビットに等しい。従って、予測部分剰余が上下限外に位置する１つのケース（上記の真理値表において、星印で示す）が存在する。インプリメントされたＳＲＴアルゴリズムは上下限外の部分剰余を形成しない。このため、実際の部分剰余は負の限界内に位置する。従って、−１は選択すべき適切な商デジットである。予測部分剰余に基づいて選択された商デジットが実際の部分剰余に基づいて選択された商デジットと異なる他の２つのケース（表１の１１１．０及び１１１．１に対するエントリに対応するケース）が存在する。しかし、ここに示す商デジットの誤った選択例では、商デジットは過小予測されないうえ、部分剰余は所定の上下限内に維持される。従って、最終結果は依然正確に形成される。
【００１７】
以下の表２は表１に示す従来の商選択ロジックを簡単に表した真理値表である。以下の表において、“Ｘ”はドントケア論理変数（"Don't care" logic variable）を表す。１ｘｘ．ｘが−１の商デジットを形成する第３のケースは、予測部分剰余が１１１．１である場合には適用されない。この場合、第２のエントリが使用され、正しい商デジットは０になる。
【００１８】
【表２】
浮動小数点演算は結果が正確であるか否かを表示するために、同結果とともにスティッキー・ビット（Sticky bit）を形成する。結果が不正確である場合、スティッキー・ビットがアサート（Assert）される。また、結果が正確である場合、スティッキー・ビットがデアサート（Deassert）される。実質的に、スティッキー・ビットは任意の下位ビットがゼロでないか否かを示す。スティッキー・ビットは米国電気電子学会７５４規格（IEEE Standard 754）に基づく丸めのためのガード・ビット及び丸めビットとともに使用される。これについては、１９８５年にニューヨークに所在する米国電気電子学会から発行された米国規格協会／米国電気電子学会標準規格（ANSI/IEEE Standard）７５４規格に記載されている２進浮動小数点演算のための米国電気電子学会規格を参照のこと。
【００１９】
除算及び平方根演算において、スティッキー・ビットは最終部分剰余がゼロであるか否かを確認することによって決定される。所望の数の商ビットを計算した後、最終部分剰余は部分剰余として定義される。部分剰余は冗長形態であるため、桁上げ伝搬加算はゼロ検出前に実施される。図２はスティッキー・ビットを計算するための回路を示す。図２において、最終部分剰余の桁上げ部分２０１及び和部分２０２は桁上げ伝搬加算器２００によって合計される。加算器２００から出力される最上位ビット（Most significant bit;略してmsb）は最終部分剰余の符号ビット２０３である。図１に示すように、除算ハードウェアは商（即ちＱ）及び商−１（即ちＱ−１）を累算する。最終部分剰余が負の場合、Ｑ−１は適切な商である。また、最終部分剰余がゼロまたは正の場合、Ｑは正しい商である。従って、符合ビット２０３は正しい商を選択すべく使用される。図２において、ゼロ検出器２０４は非冗長最終部分剰余２０５の全てのビットがゼロであるか否かを決定し、かつスティッキー・ビット２０６を出力する。ゼロ検出器２０４は５９入力論理和ゲート（59-input OR gate）と論理的に等しい。
【００２０】
一見して、前記の解決策は正または負の最終部分剰余の全ての可能性について適切に見える。しかし、結果が正確である希なケースでは、最終部分剰余は負の除数に等しい。表３は自身によって除される数のための除算反復を示す。ここで、ＰＲ［ｉ］はｉ番目の商デジットが選択された後における部分剰余を示す。
【００２１】
【表３】
被除数は常に正であり、かつ正規化されている。このため、第１の反復から得られる商デジットは１になる。これは正の正規化数がゼロの符合ビットと、１の最上位デジットとを有するという事実に基づく。１ビットだけ位置を右へシフトすることにより、正の正規化数を２で割った際に、最上位ビットは必ずゼロになる。（最上位ビットは正しい２の補数を形成する符合ビットに対して整合すべく拡大されている。このため、負の数を２で割った場合、最上位ビットは１になる。）最上位ビットがゼロである場合、表２は１の商デジットを選択すべきことを命ずる。
【００２２】
表３に示す第２の反復において、部分剰余ＰＲ［１］はゼロである。このため、第２の商デジットは１になる。その後の全ての反復において、部分剰余は負の除数に等しく、−１の商デジットが選択される。最後の反復後、最終部分剰余ＰＲ［ｎ］における符合検出は、最終部分剰余が負であることを決定し、かつＱ−１を選択すべきことを表示する。事実、これは正しい結果である。しかし、この最終部分剰余はゼロではない。これは不正確な結果を誤って示すとともに、スティッキー・ビットをアサートすべきことを誤って示す。
【００２３】
この問題は正確な結果を要する全ての除算演算に波及する。表２に示すように、商選択ロジックは実際にはゼロである部分剰余に対して正の値を予測し、そして同予測を後から補正すべく定義されている。基本的に、前記の問題はこの商選択ロジックの定義に起因して生じる。従来の除算器はスティッキー・ビットの計算前に負の最終部分剰余を復元するために１つのプロセッサ・サイクルを要する。正確なスティッキー・ビット計算の実現が望まれる。負の最終部分剰余を復元することなく正確なスティッキー・ビットの計算を保証する除算器の開発は効果的である。
【００２４】
本発明は前述した事情に鑑みてなされたものであって、その目的は、浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算する能力を提供することにある。本発明の別の目的は商選択規則を実行する際の待ち時間を短縮するとともに、最小限のサイズを有する最適な商選択回路及び同商選択回路を含む除算回路を提供することにある。
【００２５】
【課題を解決するための手段】
本発明の課題を解決すべく、２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路であって、冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、選択された商デジットは−１商デジットに該当するマイナス出力（Minus output）と、ゼロ商デジットに該当するゼロ出力（Zero output）と、＋１商デジットに該当するプラス出力（Plus output）とのうちのいづれか１つをアサートすることによって出力される商デジット選択回路において、第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器（Four-bit one detector）と、第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートと、オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路（Zero circuit）とを含む商デジット選択回路が提供される。
【００２６】
更に、前記の商デジット選択回路は第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、前記プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路（Plus circuit）を含み得る。同商デジット選択回路は第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、前記マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路（Minus circuit）を含み得る。４ビット・ゼロ検出器として４入力論理和ゲート（Four input OR gate）を使用可能である。また、４ビット１検出器は４入力論理積ゲート（Four input AND gate）であり得る。
【００２７】
更に本発明では、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路であって、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路（Quotient zero circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路（Quotient positive circuit）とを含む商デジット選択回路を提供する。
【００２８】
前記の商デジット選択回路は第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路（Quotient negative circuit）を含み得る。更に商デジット選択回路は、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路（Inverted quotient zero circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路（Inverted quotient positive circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路（Inverted quotient negative circuit）とを含み得る。
【００２９】
更に本発明では、被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタと、オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタと、本発明の商デジット選択回路と、部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器とを含む浮動小数点正規形仮数除算回路（Floating point normalized mantissa division circuit）を提供する。同除算回路は商デジットを累算する商レジスタを含み得る。前記の部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示し得る。また、前記の加算器は桁上げ保留加算器であり得る。
【００３０】
更に、２進除算及び平方根演算において商デジットを冗長部分剰余から選択する方法であって、冗長部分剰余は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含む方法において、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを形成すべく第１和ビット、第２和ビット、第３和ビット及び第４和ビットを第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットに対して加算する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１である場合、または前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロであって、かつ第５和ビット及び第５桁上げビットの両方がゼロに等しい場合にのみ商デジットとしてゼロを選択する工程とを含む方法を提供する。
【００３１】
更に、前記の商デジットを選択する方法は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない状態と、第５和ビット及び第５桁上げビットが全てゼロにならない状態とのうちのいづれかにおいて、第１予測部分剰余ビットがゼロである場合にのみ商デジットとして＋１を選択する工程を含み得る。また、同商デジットを選択する方法は第１予測部分剰余ビットがアサートされ、さらには第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない場合にのみ商デジットとして−１を選択する工程を含み得る。
【００３２】
更に本発明では、２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路を形成する方法であって、冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、選択された商デジットは−１商デジットに該当するマイナス出力と、ゼロ商デジットに該当するゼロ出力と、＋１商デジットに該当するプラス出力とのうちのいづれか１つをアサートすることによって出力される方法において、第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器を形成する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器を形成する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器を形成する工程と、第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートを形成する工程と、オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、前記ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路を形成する工程とを含む方法を提供する。
【００３３】
前記の商デジット選択回路を形成する方法は第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路を形成する工程を含み得る。商デジット選択回路は第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路を形成する工程を含み得る。４ビット・ゼロ検出器として４入力論理和ゲートを使用可能である。また、４ビット１検出器は４入力論理積ゲートであり得る。
【００３４】
更に本発明では、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路を形成する方法であって、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路を形成する工程とを含む方法を提供する。
【００３５】
前記の商ポジティブ回路を形成する工程は第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路を形成する工程を含み得る。
【００３６】
更に、前記の商ネガティブ回路を形成する工程は第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路を形成する工程とを含み得る。
【００３７】
また本発明では、被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタを形成する工程と、オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタを形成する工程と、本発明の商デジット選択回路を形成する工程と、部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器を形成する工程とを含む浮動小数点正規形仮数除算回路を形成する方法を提供する。同方法は商デジットを累算する商レジスタを形成する工程を含み得る。また、部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示し得る。更に、加算器は桁上げ保留加算器であり得る。
【００３８】
本発明は浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算する能力を提供する。本発明は本発明に基づく商選択規則を最小限の待ち時間で実行するとともに、最小限のサイズを有する最適な商選択回路を提供する。
【００３９】
本発明は正確な結果が得られた際に、作業中の部分剰余が負になることを防止する更に効果的な商デジット選択関数を提供する。負の部分剰余はスティッキー・ビットの計算前に復元する必要がないため、１サイクルが削減される。
【００４０】
本発明に基づき、商デジット選択ロジックは負の除数に等しい部分剰余の形成を防止すべく変更される。正確な除算結果を実現する正確、かつ効果的なスティッキー・ビットの計算を行うために、負の除数に等しい負の部分剰余の形成を防止する必要がある。これを実現すべく商デジット選択関数を強化して、ハードウェアのコストの削減及び待ち時間の短縮を行い得る。このため、商デジット選択関数の強化は理想的な解決策である。予備最終部分剰余（Preliminary final partial remainder）を復元するための余分なメカニズムを提供する必要がないため、余分なハードウェアが排除される。負の予備部分剰余を復元する別のサイクル時間を必要としないため、待ち時間が短縮される。
【００４１】
本発明に基づき、実際の部分剰余がゼロの際に、１の商デジットに変えてゼロの商デジットを選択すべく商デジット選択ロジックが変更される。上位４ビットがゼロである５ビットからなる予測部分剰余を使用することにより、第４の上位ビットへの可能な桁上げ伝搬が検出される。これは冗長部分剰余のうちの第５の最上位和ビット及び桁上げビットの確認により実現可能である。これら両方がゼロである場合、同ビット位置から予測部分剰余の最下位ビット位置への桁上げ伝搬は不可能であり、ゼロの商デジットが選択される。冗長部分剰余の第５の最上位桁上げビット及び和ビットのうちの少なくともいづれか一方が１である別のケースでは、１の商デジットが選択される。
【００４２】
【発明の実施の形態】
浮動小数点演算において、負の最終部分剰余が生じた際にスティッキー・ビットを正確に計算すべく幾つかのオプションを検討する必要がある。最も簡単な解決策はゼロ検出を行う前に除数を加算することにより、負の最終部分剰余を復元することが挙げられる。別の桁上げ伝搬加算器を設置するために要する空間を考慮した場合、解決策は従来のハードウェアを利用する必要がある。これを実現する２つの方法を図３及び図４に示す。
【００４３】
図３に示す解決策は基本的な反復工程をインプリメントする従来の桁上げ保留加算器３００を利用している。通常の演算中、最終サイクル信号３０１はロー（Low）である。この結果、マルチプレクサ３０２，３０３は図１に関連して詳述した標準的反復工程をインプリメントすべく形成されている。しかし、最終サイクル中、最終サイクル信号３０１はハイ（High）であり、マルチプレクサ３０３はレジスタ３０５内に格納された部分剰余の桁上げ部分及び和部分に対して除数Ｄ３０４を加算すべく同除数Ｄ３０４を加算器３００へ出力する。予備部分剰余の符号が負の場合、マルチプレクサ３０６は加算器３００の結果を最終部分剰余フリップ・フロップ３０７に対して出力する。
【００４４】
図４に示す解決策では、図２に示すスティッキー・ビット計算を行う従来の桁上げ伝搬加算器４００を再び使用している。図１に示す反復データパス等のデータパスが所望の精度の商デジットを形成した後、冗長部分剰余の桁上げ部分ＰＲC及び和部分ＰＲSは最終サイクル信号がローの間にマルチプレクサ４０３，４０２へそれぞれ入力される。次いで、桁上げ伝搬加算器４００は冗長部分剰余を予備非冗長最終部分剰余（Preliminary non-redundant final partial remainder）へと削減する。桁上げ伝搬加算器４００の最上位出力ビット４０４は予備最終部分剰余の符号を示す。非冗長予備最終部分剰余はフリップ・フロップ４０６内へラッチされる。次いで、最終サイクル信号４０１がアサートされる。予備最終部分剰余が負であることを符号ビット４０４が示した場合、マルチプレクサ４０５は加算器４００に対して除数を出力するマルチプレクサ４０２に対して同除数を出力する。その一方、マルチプレクサ４０３は加算器４００に対する別の入力として予備非冗長部分剰余を出力する。次いで、ゼロ検出器４０７は復元された部分剰余を使用してスティッキー・ビットを形成する。符号ビットが負以外の部分剰余を示す場合、マルチプレクサ４０５は除数Ｄに代えてゼロを部分剰余に対して加算させる。
【００４５】
図３及び図４に示す前記の２つの解決策は、予備最終部分剰余が負の際にスティッキー・ビットを計算すべく別のマルチプレクサ・ハードウェアと、別のサイクルとを要する。マルチプレクサ３０２は部分剰余形成クリティカル・パス（Partial remainder formation critical path）上に配置されている。このため、図３に示す解決策は基本的反復のためのサイクル時間に影響を及ぼす。更に、パイプライン・スーパースカラ・プロセッサ内の待ち時間可変命令（Variable latency instructions）は命令スケジューリング及びバイパス制御ロジックを更に複雑にするため望ましくない。従って、スティッキー・ビットを正確に計算するために除算演算の全分布のうちの僅かな部分のみが余分なサイクルを必要とする場合にも、負の予備最終部分剰余を形成しない除算命令のための余分なサイクルを削除すべくプロセッサのデザインは更に複雑になる。従って、負の部分剰余を復元する正味の効果は、全ての除算及び平方根演算を行う別の待ち時間サイクルを必要とする。
【００４６】
本発明に基づき、商デジット選択ロジックは負の除数に等しい部分剰余の形成を防止するために変更される。正確な除算結果を実現するスティッキー・ビットを正確、かつ効果的に計算すべく、負の除数に等しい負の部分剰余の形成を防止する必要がある。これを実現すべく商デジット選択関数を強化することにより、ハードウェアが削減され、かつ待ち時間が短縮される。このため、同選択関数の強化は理想的な解決策である。予備最終部分剰余を復元するための余分なメカニズムを提供する必要がないため、余分なハードウェアを排除し得る。また、負の予備部分剰余を復元する別のサイクル時間を必要としないため待ち時間が短縮される。
【００４７】
本発明に基づく、商デジット選択ロジックは、実際の部分剰余がゼロの際に１の商デジットに代えてゼロの商デジットを選択すべく変更される。これは２ＰＲ［ｉ］est＝０００．０に対してｑ［ｉ＋１］＝０を選択することを示唆している。しかし、商デジット選択関数は実際の部分剰余より寧ろ予測部分剰余に対して作用するため、商選択ロジックの注意深いデザインが必要である。実際には予測部分剰余は１／２未満であり得るため、更に下位の冗長部分剰余ビットの加算は実際の部分剰余の上位４ビットのうちの最下位ビット位置へ１を伝搬させる。従って、実際の部分剰余は１／２以上になる。
【００４８】
実際の部分剰余が１／２（または１／２以上）である場合、除数は１／２≦Ｄ＜１に限定されるため、ｑ＝１を常に選択する必要がある。実際の部分剰余が１／２より更に大きく、かつｑ＝０が選択された場合、次の部分剰余は除数を最初に加算または減算することなく、実際の部分剰余を左側へ１ビットだけシフトすることによって得られる。この左シフトは正確な商への収束に必要な３／２の上限を越える次の実際の部分剰余を形成する。
【００４９】
正確な商デジットがゼロの際に、除数が実際の部分剰余より更に大きく、さらに商デジットとして＋１の値が選択された場合、このエラーは後の反復において補正可能である。しかし、予測部分剰余が０００．０であって、かつ正確な商デジットが１である際に商デジットとしてゼロが選択された場合、このエラーを補正する方法はない。ｑ＝１が正しい商デジットである際にｑ＝０が選択された場合、過小予測を補正する方法はない。結果は回復不能な誤りであり、次の部分剰余は正確な結果への収束に必要な所定の上下限の外に位置する。
【００５０】
全ての部分剰余に対する２進加算の実施は予測の問題を排除する。しかし、これはＳＲＴ除算のタイミング及び空間に関する効果を無効にする。ゼロの商デジットは全ての部分剰余がゼロである際にのみ選択可能である。しかし、全ての部分剰余に対するゼロの検出は同一の理由により逆効果となる。
【００５１】
前記の解決策に対する簡単な代替策としては、実際の部分剰余の上位４ビットのうちの最下位ビットへの可能な桁上げ伝搬を検出することが挙げられる。これは冗長部分剰余のうちの第５の最上位和ビット及び桁上げビット、即ちＰＲS,msb-4及びＰＲC,msb-4を確認することによって実現し得る。ＰＲS,msb-4及びＰＲC,msb-4がそれぞれゼロである場合、そのビット位置から予測部分剰余の最下位ビット位置への桁上げ伝搬は不可能であり、さらにはゼロの商デジットを選択する必要がある。冗長部分剰余の第５の最上位桁上げビット及び和ビットのうちの少なくともいづれか一方が１である別のケースでは、１の商デジットを選択する必要がある。部分剰余のうちの複数の下位ビットがゼロでない場合にも、同部分剰余は所定の上下限（−５／２≦２ＰＲ≦３／２）内に存在し、かつ正しい結果が依然算出されることになる。
【００５２】
予測部分剰余の計算に必要な桁上げ伝搬加算は実際の冗長部分剰余の上位４つの伝搬ビット及び和ビットに対してのみ行われる。このため、本発明に基づく計算の待ち時間に対する影響は最低限に抑制される。表４は本発明に基づく正確な商選択ロジックのための真理値表を示す。
【００５３】
【表４】
図５は強化された商デジット選択関数の論理図を示す。図５において、４ビット桁上げ伝搬加算器５００は実際の冗長部分剰余の桁上げ部分（２ＰＲＣ［ｍｓｂ：ｍｓｂ−３］）及び和部分（２ＰＲＳ［ｍｓｂ：ｍｓｂ−３］）の上位４ビットを入力され、そして予測非冗長部分剰余ｘ［３：０］を形成する。オール・ゼロ検出器（All-zero detector）５０１は予測部分剰余ｘ［３：０］の４ビット全てがゼロであるか否かを決定する。ｘ［３：０］の全ビットがゼロである場合、中間信号ｎ０がアサートされる。オール・ゼロ検出器５０１は４入力否定論理和ゲート（Four input NOR gate）と機能的に同じである。ｘ［３：０］の全ビットが１である場合、中間信号ｎ１がアサートされる。オール・ワン検出器（All-one detector）５０２は４入力論理積ゲートと機能的に同じである。否定論理和ゲート５０３は冗長部分剰余のうちの最上位の第５桁上げビット（２ＰＲＣ［ｍｓｂ−４］）及び第５和ビット（２ＰＲＳ［ｍｓｂ−４］）を入力され、そして中間信号ｉ０を形成する。中間信号ｉ０は２ＰＲＣ［ｍｓｂ−４］及び２ＰＲＳ［ｍｓｂ−４］がゼロである際にのみアサートされる。
【００５４】
ランダム・ロジック５０４のブロックはＳＲＴ除算に基づく可能な商デジット値のうちの１つにそれぞれ該当する３つの信号（Ｍ、Ｚ及びＰ）を形成する。Ｍは−１の商デジットに該当する。Ｚはゼロの商デジットに該当する。Ｐは＋１の商デジットに該当する。Ｍはｘ［３］がデアサートされ、かつｎ１がデアサートされた場合にのみアサートされる。Ｚはｎ１がアサートされるか、またはｉ０及びｎ０がアサートされた場合にのみアサートされる。ＰはＸ［３］がアサートされ、ｎ０またはｉ０がデアサートされた場合にのみアサートされる。各論理関係を仮定した場合、商デジット信号Ｍ、Ｚ及びＰのうちの任意の２つを同時にアサートすることは不可能である。
【００５５】
図５に示すインプリメンテーションは論理的に正しい。しかし実際には、４ビット２進加算器及びその後のロジックは統合され、さらには最適化されたロジック・インプリメンテーションへの併合が可能である。図６に示すように、５段階ロジック・インプリメンテーション（Five-stage logic implementation）は空間を更に効果的に使用するとともに、出力を更に短い遅延時間を伴って形成する。
【００５６】
図６に示すインプリメンテーションでは、Ｍ、Ｚ及びＰが計算されるとともに、論理反転／Ｍ、／Ｚ及び／Ｐも計算される。これはデコードされた選択入力を有するＣＭＯＳマルチプレクサ内等において伝達ゲートをイネーブルするために商信号を使用する際に効果的である。Ｍ及び／Ｍは冗長部分剰余ビットの上位４ビット（２ＰＲＣ［ｍｓｂ：ｍｓｂ−３］及び２ＰＲＳ［ｍｓｂ：ｍｓｂ−３］）にのみ依存する。その一方、Ｚ、Ｐ、／Ｚ及び／Ｐは全て冗長部分剰余の上位５ビット（２ＰＲＣ［ｍｓｂ：ｍｓｂ−４］及び２ＰＲＳ［ｍｓｂ：ｍｓｂ−４］）に依存する。図６のセルは回路が占める空間の削減を第２の課題とする一方で、主に遅延を最小限に抑制すべく最適化されている。図６に示す殆どの論理は空間を削減すべく幾つかの出力計算の間において共有されている。
【００５７】
本発明に基づく基数２を使用する新たな商デジット選択論理（Radix-2 quotient digit selection logic）をインプリメントするために必要な別のゲートの総数は比較的少ない。好ましい実施の形態のインプリメンテーションに関するスパイス・シミュレーション分析（Spice simulation analysis）において、商選択論理クリティカル・タイミング・パス（Quotient selection logic critical timing path）が５％未満であることが示されている。
【００５８】
更に遅い商選択ロジックと、最後に行われる部分剰余復元サイクルの排除との間には、インプリメンテーションに依存するタイミング・トレードオフが存在する。僅かにより複雑な商選択論理に起因する遅延の増加がプロセッサ・サイクル時間（Processor cycle time）を制限しない場合、性能の増加は負の最終部分剰余の復元に必要とされる待ち時間サイクルの削減により常には実現される。本発明のハードウェア除算器等を含む最近のマイクロプロセッサでは、プロセッサ・サイクル時間は他のクリティカル・パスによって決定されるか、またはプロセッサを設計する前に任意で適合させ得る。商選択ロジックのうちの増大した遅延が最長パスでないケースにおいて、各除算演算あたり１サイクルの正味節約は新たな出費を伴うことなく実現し得る。
【００５９】
図６に示す実施の形態において、変更された商選択ロジック・アルゴリズムは内部浮動小数点除算器クリティカル・パス（Internal floating point divider critical path）の速度を従来の商選択規則を使用して最適化された同等のクリティカル・パスより約１００ｐｓ遅くする。これは２パーセント未満の速度低下に相当する。プロセッサの限界タイミング・パス（Limiting timing path）は更に長い。従って、改善された商選択ロジックはプロセッサ・サイクル時間に悪影響を及ぼさない。スティッキー検出（Sticky detection）前に部分剰余を復元するサイクルを排除する効果が実現される。
【００６０】
本発明の商選択ロジックを使用しても負の最終部分剰余は依然形成され得る。しかし、負の最終部分剰余が形成された際、本発明に基づく商選択ロジックは負の部分剰余が負の除数より更に大きいことを保証する。従って、本発明に基づく負の最終部分剰余が形成された場合、Ｑ−１が選択され、結果は必ず不正確になる。この結果、負の最終部分剰余が負の除数に等しくなる恐れを伴うことなくスティッキー・ビットを安全にアサートし得る。
【００６１】
符号検出及びスティッキー・ビット計算を平行して実施する一方で、ハードウェアの節約が可能である。５９ビット全加算器を使用する代わりに、５９ビット符号検出加算器（59-bit sign detect adder）を使用し得る。これはタイミングを僅かに改善する一方で、主に空間の節約を実現する。ゼロ検出は冗長部分剰余を２進数へ変換する明確な加算を伴うことなく行える。
【００６２】
【数４】
数式４の式において、Ｓｉ及びＣｉはそれぞれ最終部分剰余の和の値及び桁上げ値である。次いで、スティッキー・ビットは以下の数式５に基づいて計算される。
【００６３】
【数５】
この方法は５９ビット桁上げ伝搬加算器の遅延に代えて３入力排他的論理和遅延（3-input XOR delay ）を伴うゼロ検出器に対する入力を形成し、大きな正味節約を可能にする。
【００６４】
以上、本発明を好ましい実施の形態に基づいて詳述したが、同実施の形態は例示を目的とするものであって、本発明を限定するものではない。当業者は必要に応じて本発明の実施の形態を変更することが可能であり、同変更は請求項に開示する本発明の範囲及び精神を逸脱しないものとする。例えば、図６に示す商選択ロジックの最適化された論理インプリメンテーションは各種の同等の方法を用いて設計し得る。また、図６に示す回路は標準的なＣＭＯＳ伝達ゲート・マルチプレクサ（CMOS transmission gate multiplexor）に代えて、ｎ−チャネル・パス・トランジスタ・マルチプレクサ（n-channel pass transistor multiplexor）を制御すべく商デジットの正の極性のみを計算し、論理反転の計算を削除できる。最適化された異なるインプリメンテーションは異なる技術（例：ＮＭＯＳ、ＥＣＬ等）におけるインプリメンテーション、または同一技術に属する異なる設計規則及び設計ツールを用いたインプリメンテーションの結果である。請求項は表４に示す真理値表の全ての回路インプリメンテーションを網羅することを目的とする。従って、本発明の技術分野の当業者にとって自明な各種の変更及び修正は、本発明の精神及び範囲に属する。
【００６５】
【発明の効果】
以上詳述したように、本発明によれば、浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算し得る。更に、本発明は商選択規則を実行する際の待ち時間を短縮するとともに、最小限のサイズを有する最適な商選択回路及び同商選択回路を含む除算回路を実現するという優れた効果を発揮する。
【図面の簡単な説明】
【図１】反復ＳＲＴ除算アルゴリズムをインプリメントする従来のハードウェア除算モジュールの簡単な論理図。
【図２】従来のスティッキー・ビット演算回路の簡単な論理図。
【図３】反復ＳＲＴ除算アルゴリズムをインプリメントするか、または負の最終部分剰余を復元する１つのハードウェア除算モジュールの簡単な論理図。
【図４】反復ＳＲＴ除算アルゴリズムをインプリメントするか、または負の最終部分剰余を復元する別のハードウェア除算モジュールの簡単な論理図。
【図５】本発明の商選択規則をインプリメントする回路の簡単な論理図。
【図６】商デジット信号及びその論理反転を形成する商選択規則をインプリメントする回路の詳細な論理図。
【符号の説明】
３００…桁上げ保留加算器、３０１，４０１…最終サイクル信号、３０２，３０３，３０６，４０３，４０２，４０５…マルチプレクサ、３０４…除数、３０５…レジスタ、３０７，４０６…フリップ・フロップ、４００…桁上げ伝搬加算器、４０４…最上位出力ビット、４０４…符号ビット、４０７…ゼロ検出器、５００…４ビット桁上げ伝搬加算器、５０１…オール・ゼロ検出器、５０２…オール・ワン検出器、５０３…否定論理和ゲート、５０４…ランダム・ロジック。
【発明の属する技術分野】
本発明はマイクロプロセッサ内の浮動小数点除算器（Floating point dividers）の分野、より詳細には、ＳＲＴ除算／平方根演算のインプリメンテーション（SRT division/square root implementation）における商デジット選択規則（Quotient digit selection rules）に関し、同規則は結果が正確な場合、負の最終部分剰余（Negative final partial remainders）の形成を防止する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
ＳＲＴアルゴリズムは引き放し法除算（Non-restoring division）を実行する１つの方法を提供する。この詳細については、１９５８年９月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）第Ｃ−７巻２１８〜２２２頁に記載されているジェイ．イー．ロバートソンによる“デジタル除算法の新たなクラス”と、１９５８年に発行されたメカニカル応用数学誌（Quart. J. Mech. Appl. Math.）第１１刊第３部３６４〜３８４頁に記載されているケー．ディー．トーチャーによる“自動２進コンピュータのための乗算及び除算技術”を参照のこと。デジタル除算では、オペランドとして除数及び被除数が使用され、かつ出力として商が形成される。複数の商デジットは反復計算され、同商デジットのうちの最上位商デジットが最初に形成される。ＳＲＴ除算は他の除算アルゴリズムとは異なる。ＳＲＴ除算では、連続する各商デジットは上位の僅かな部分剰余デジットのみに基づいて公式化され、非常に多くのデジットを含み得る部分剰余全体に基づいて公式化されることはない。全ての反復において、正確な商デジットの選択は部分剰余全体を考慮せずには保証できない。このため、ＳＲＴアルゴリズムは不正確な商デジットを時々形成する。しかし、ＳＲＴアルゴリズムは正、ゼロ及び負の各商デジットの可能性を提供する。商デジットを１つの反復において過大予測した場合、誤りは負の商デジットを選択することにより、次の反復において補正される。ＳＲＴ除算では、商デジットを過小予測してはならない。即ち、商デジットは常に過大予測するか、または正確に予測する必要がある。全ての商デジットを過小予測しなかった場合、部分剰余は所定の上下限内に維持され、正確な最終商の計算が可能になる。ＳＲＴアルゴリズムは負の商デジットの形成を可能にする。このため、一般的に最終商出力は通常の除算のように全商デジットを単に連結するのではなく、寧ろ商デジットの重み付け加算及び減算を介して行われる。
【０００３】
基数が更に大きい場合、１つの反復において形成される商デジットの数が更に多くなる。これは複雑さを増大させる。基数２のインプリメンテーションは１つのデジットを１つの反復において形成する。基数４のインプリメンテーションは２つのデジットを１つの反復において形成する。図１はＳＲＴに基づく基数２を使用する簡単な浮動小数点インプリメンテーション（Simple SRT radix-2 floating point implementation）を示す。同インプリメンテーションは、除数及び被除数の両方が正であって、かつ正規化されていることを要する。従って、１／２≦Ｄ、被除数＜１となる。シフトされた最初の部分剰余（Initial shifted partial remainder）、即ち２ＰＲ［０］は被除数である。第１商デジットの計算の反復（First quotient digit calculation iteration）開始前に、被除数は部分剰余レジスタ１００に対してロードされる。この結果、最初の部分剰余は被除数となる。その後、反復によって形成される部分剰余は以下の数式１に基づいて形成される。
【０００４】
【数１】
【０００５】
部分剰余は一般的に冗長桁上げ保留の形態に維持される。この結果、次の部分剰余の計算では、更に処理速度が遅く、かつ大きい桁上げ伝搬加算器に代えて桁上げ保留加算器の使用が可能である。部分剰余は全ての反復が実施され、かつ所望の精度に達した後で、非冗長形態（Non-redundant form）へ変換される。ＳＲＴアルゴリズムは商デジットの過大予測を可能にする。商デジットの過大予測により、負の部分剰余が続いて形成される。このため、最終部分剰余を負にすべく最後の商デジットを過大予測し得る。この場合、過大予測に対する補正が不可能なため、Ｑ及びＱ−１の維持が必要である。この結果、最終部分剰余が負である場合、Ｑ−１がＱに代えて選択される。商デジットは常には冗長形態に維持され、さらには最後の反復において非冗長形態へ変換される。これに代えて、商（即ちＱ）と、商−１（即ちＱ−１）とを１９９２年１２月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）第４１巻第１２号の１４９７〜１５０３頁に記載されているエム．ディ．エルセゴバック及びティ．ラングによる“オン・ザ・フライ・ラウンディング（On-the-fly rounding）”に開示されている規則に基づいてフライ（Fly）上に形成し得る。
【０００６】
ＳＲＴアルゴリズムは平方根演算にも適用される。これにより、従来の除算ハードウェアの使用が可能である。簡略化された平方根の式は除算の式に類似している。これについては、１９９０年８月に発行された米国電気電子学会コンピュータ部会会報（IEEE Trans. Comput.）の第３９巻第８号の１０１６〜１０２４頁に記載されているエム．ディ．エルセゴバック及びティ．ラングによる“初期ＰＬＡを伴わない基数４を使用した平方根演算（Radix-4 square root without initial PLA）”を参照のこと。平方根演算の反復方程式を以下の数式２に示す。
【０００７】
【数２】
【０００８】
２進法の除算アルゴリズムはグラマー・スクールで教授されている標準的な十進法の除算に類似している。Ｒ／Ｄ＝Ｑにおいて、Ｑに対する各商デジットが予測される。第１商デジットを決定すべく、商デジットの適切な予測値に対して除数が掛けられる。次いで、その積は剰余を形成すべく被除数から引かれる。剰余が除数より更に大きい場合、商デジットの予測値は過小である。更に、剰余が負である場合、商デジットの予測値は過大である。いづれにしても、商デジットの予測値が誤っている場合、予測値の変更が必要である。この結果、正確な商デジットは次のデジットへ進む前に導き出される。次の関係、即ち０≦ＰＲ＜Ｄが正しい場合、商デジットは正しい。ここで、ＰＲは除数を掛けた商デジットを引いた後の部分剰余を示す。
【０００９】
ＳＲＴ除算アルゴリズムの鍵としては、負の商デジットを使用し得る点が挙げられる。例えば、基数１０において、商デジットは標準デジット０〜９に加えて、−１〜−９の値を有し得る。６００÷４０の除算演算を以下に例示する。各反復において、正しい商デジットを選択した場合、正しい結果は１５になる。しかし、正しいデジットである１に代えて、商デジットとして２が第１の反復中に選択されたと仮定する。第１の商デジットとして２を選択した後の部分剰余は６００−（２＊４０＊１０1）＝−２００である。ＳＲＴ除算では、このエラーを補正すべくバックアップを行い、かつ第１の反復を繰り返すことはない。寧ろ、エラーは次の反復において補正可能である。ＳＲＴ除算に基づき、第２の商デジットとして−５を正しく予測したと仮定する。反復後、部分剰余は−２００−（−５＊４０＊１０0）＝０となる。反復後の部分剰余がゼロの場合、残りの全てのデジットの正しい値はゼロになる。従って、計算結果は（２＊１０1）＋（−５＊１０0）＝１５となり、同計算結果は正しい。従って、ＳＲＴアルゴリズムは、後から１つ以上の負の商デジットを選択することにより、任意の商デジットの過大予測の補正を可能にする。その後の部分剰余を実質的にゼロまで削減すべく、予測された商デジットから正しい商デジットを引いた値が１を上回ってはならない。商デジットの予測における誤りが＋１を上回ることを許容した場合、−９を下回る商デジット（例：−１０、−１１等）が底１０において必要とされる。同様に、商デジットの範囲はＳＲＴアルゴリズムに基づいて正の方向へ拡大されることはない。このため、正しい商デジットの過小予測は致命的である。これは部分剰余が基数を掛けた除数より更に大きく、かつその後、底１０において９を上回る商デジット（例：１０、１１等）を必要とすることに起因する。従って、部分剰余を所定の上下限内に維持するために、商デジット選択において、正しい商デジットを過小予測してはならない。更に、商デジット選択において商デジットが過大予測された場合、予測された商デジットから正しい商デジットを引いた値は１を上回ってはならない。
【００１０】
部分剰余を所定の上下限内に維持するための前記の基準を全ての部分剰余デジットを使用することなく満足させ得る点が保証される。正しい演算結果の算出を可能にする商デジットを選択するためには、部分剰余のうちの上位の僅かなデジットのみを使用すればよい。
【００１１】
ＳＲＴ除算は冗長商表示を負以外のデジットのみを有する標準的な非冗長形態まで削減するために、全ての商デジットの選択後に最終加算を要する。
最近の電子計算回路に用いられる２進法（底２）では、ＳＲＴ除算は＋１、０または−１の商デジットを提供する。商選択デジットを形成するロジック１０２はＳＲＴ除算インプリメンテーションの中心エレメントである。初期のリサーチは冗長部分剰余のうちの上位３ビットのみが基数２を使用する商デジット選択関数（Radix-2 quotient digit selection function）に必要な入力であることを示している（１９８３年に発行された米国電気電子学会第６回コンピュータ計算シンポジウムの予稿集（Proc. Sixth IEEE Symp. Comput. Arithmetic.）の９９〜１０２頁に記載されているエス．マジェルスキーによる“高速デジタル回路のための平方根アルゴリズム”と、１９８６年１０月に発行された米国電気電子学会の固体回路ジャーナル（IEEE J. Solid-State Circuits.）第ＳＣ−２１巻第５番の８１４〜８１９頁に記載されているディー．ズラス及びダブリュ．マックアリスターによるＶＬＳＩにおける平衡遅延ツリー及び組合せ除算を参照）。しかし、更に最近の研究結果は、商デジット選択デジットを正しく形成し、かつ部分剰余を所定の上下限内に維持するために４ビットを要する点を指摘している（１９９４年にクルワー・アカデミック出版社（Kluwer Academic Publishers）から発行されたエム．ディー．エルセゴバック及びティー．ラングによる除算及び平方根演算：デジット漸化アルゴリズム及びインプリメンテーション（Division and Square Root: Digit-recurrence Algorithms and Implementations）ｃｈ．３と、１９８５年８月に発行された米国電気電子学会コンピュータ部会会報第Ｃ−３４巻第８号の７２４〜７３３頁に記載のエス．マジェルスキーによる“高速デジタル回路のための平方根アルゴリズム”と、１９９１年に発行された米国電気電子学会第１０回コンピュータ計算シンポジウムの予稿集の２０２〜２０９頁に記載のピー．モンツシ及びエル．シミニエラによる“幾つかの加算工程の省略をともなう基数２を使用する簡単な除算及び平方根演算”と、１９８７年に発行された米国電気電子学会第８回コンピュータ計算シンポジウムの予稿集の９５〜１０１頁に記載のブイ．ペング、エス．サムドララ及びエム．ガブリエロフによる“浮動小数点ユニットにおけるシフター、乗算器及び除算器のインプリメンテーション”とを参照）。従来の商デジット選択規則は以下の数式３によって表すことができる。ここで、ＰＲは実際の部分剰余のうちの上位４ビットを示し、１０進小数点は上位の第３デジット及び第４デジットの間に位置する。部分剰余は２の補数であり、第１ビットは符合ビットとなる。
【００１２】
【数３】
【００１３】
予測部分剰余（ＰＲest）は４ビット桁上げ伝搬加算器のみを用いて計算できる。４ビット桁上げ伝搬加算器は実際の部分剰余のうちの桁上げ部分及び和部分の上位４ビットを加算する。実際の部分剰余のうちの上位４ビットの計算には、５９ビット桁上げ伝搬全加算を要する。従って、この簡略化は待ち時間の大きな節約を意味する。予測部分剰余ＰＲestは５９ビット桁上げ伝搬全加算を実施した場合に、予測部分剰余のうちの最下位ビット位置に一致するビット位置へ桁上げが伝搬される可能性を示していない。表１は基数２を使用する従来の商選択の真理値表である。予測部分剰余の上位４ビットは正しい商デジットを選択すべく使用される。従って、以下の真理値表は真の部分剰余の上位４ビットが予測部分剰余の上位４ビットとは異なり得るという事実を考慮している。
【００１４】
【表１】
【００１５】
商選択ロジックは０に代えて１、または−１に代えて０を予測する等、真の商結果を正しく予測するか、または過大予測すべく設計されている。ＳＲＴアルゴリズムは誤った商デジットを選択した場合、後から自身を補正する。
【００１６】
部分剰余は−５／２≦２ＰＲ［ｉ］≦３／２に制限される。このため、ＳＲＴに基づく基数２を使用する商選択ロジック（SRT radix-2 quotient selection logic）に関する従来の真理値表は幾つかのドントケア・インプット（Don't care inputs）を有する。下位ビットが無視されるため、予測部分剰余は常に真の部分剰余の最も重要な上位ビットより少ないか、または同上位ビットに等しい。従って、予測部分剰余が上下限外に位置する１つのケース（上記の真理値表において、星印で示す）が存在する。インプリメントされたＳＲＴアルゴリズムは上下限外の部分剰余を形成しない。このため、実際の部分剰余は負の限界内に位置する。従って、−１は選択すべき適切な商デジットである。予測部分剰余に基づいて選択された商デジットが実際の部分剰余に基づいて選択された商デジットと異なる他の２つのケース（表１の１１１．０及び１１１．１に対するエントリに対応するケース）が存在する。しかし、ここに示す商デジットの誤った選択例では、商デジットは過小予測されないうえ、部分剰余は所定の上下限内に維持される。従って、最終結果は依然正確に形成される。
【００１７】
以下の表２は表１に示す従来の商選択ロジックを簡単に表した真理値表である。以下の表において、“Ｘ”はドントケア論理変数（"Don't care" logic variable）を表す。１ｘｘ．ｘが−１の商デジットを形成する第３のケースは、予測部分剰余が１１１．１である場合には適用されない。この場合、第２のエントリが使用され、正しい商デジットは０になる。
【００１８】
【表２】
【００１９】
除算及び平方根演算において、スティッキー・ビットは最終部分剰余がゼロであるか否かを確認することによって決定される。所望の数の商ビットを計算した後、最終部分剰余は部分剰余として定義される。部分剰余は冗長形態であるため、桁上げ伝搬加算はゼロ検出前に実施される。図２はスティッキー・ビットを計算するための回路を示す。図２において、最終部分剰余の桁上げ部分２０１及び和部分２０２は桁上げ伝搬加算器２００によって合計される。加算器２００から出力される最上位ビット（Most significant bit;略してmsb）は最終部分剰余の符号ビット２０３である。図１に示すように、除算ハードウェアは商（即ちＱ）及び商−１（即ちＱ−１）を累算する。最終部分剰余が負の場合、Ｑ−１は適切な商である。また、最終部分剰余がゼロまたは正の場合、Ｑは正しい商である。従って、符合ビット２０３は正しい商を選択すべく使用される。図２において、ゼロ検出器２０４は非冗長最終部分剰余２０５の全てのビットがゼロであるか否かを決定し、かつスティッキー・ビット２０６を出力する。ゼロ検出器２０４は５９入力論理和ゲート（59-input OR gate）と論理的に等しい。
【００２０】
一見して、前記の解決策は正または負の最終部分剰余の全ての可能性について適切に見える。しかし、結果が正確である希なケースでは、最終部分剰余は負の除数に等しい。表３は自身によって除される数のための除算反復を示す。ここで、ＰＲ［ｉ］はｉ番目の商デジットが選択された後における部分剰余を示す。
【００２１】
【表３】
【００２２】
表３に示す第２の反復において、部分剰余ＰＲ［１］はゼロである。このため、第２の商デジットは１になる。その後の全ての反復において、部分剰余は負の除数に等しく、−１の商デジットが選択される。最後の反復後、最終部分剰余ＰＲ［ｎ］における符合検出は、最終部分剰余が負であることを決定し、かつＱ−１を選択すべきことを表示する。事実、これは正しい結果である。しかし、この最終部分剰余はゼロではない。これは不正確な結果を誤って示すとともに、スティッキー・ビットをアサートすべきことを誤って示す。
【００２３】
この問題は正確な結果を要する全ての除算演算に波及する。表２に示すように、商選択ロジックは実際にはゼロである部分剰余に対して正の値を予測し、そして同予測を後から補正すべく定義されている。基本的に、前記の問題はこの商選択ロジックの定義に起因して生じる。従来の除算器はスティッキー・ビットの計算前に負の最終部分剰余を復元するために１つのプロセッサ・サイクルを要する。正確なスティッキー・ビット計算の実現が望まれる。負の最終部分剰余を復元することなく正確なスティッキー・ビットの計算を保証する除算器の開発は効果的である。
【００２４】
本発明は前述した事情に鑑みてなされたものであって、その目的は、浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算する能力を提供することにある。本発明の別の目的は商選択規則を実行する際の待ち時間を短縮するとともに、最小限のサイズを有する最適な商選択回路及び同商選択回路を含む除算回路を提供することにある。
【００２５】
【課題を解決するための手段】
本発明の課題を解決すべく、２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路であって、冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、選択された商デジットは−１商デジットに該当するマイナス出力（Minus output）と、ゼロ商デジットに該当するゼロ出力（Zero output）と、＋１商デジットに該当するプラス出力（Plus output）とのうちのいづれか１つをアサートすることによって出力される商デジット選択回路において、第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器（Four-bit one detector）と、第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートと、オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路（Zero circuit）とを含む商デジット選択回路が提供される。
【００２６】
更に、前記の商デジット選択回路は第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、前記プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路（Plus circuit）を含み得る。同商デジット選択回路は第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、前記マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路（Minus circuit）を含み得る。４ビット・ゼロ検出器として４入力論理和ゲート（Four input OR gate）を使用可能である。また、４ビット１検出器は４入力論理積ゲート（Four input AND gate）であり得る。
【００２７】
更に本発明では、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路であって、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路（Quotient zero circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路（Quotient positive circuit）とを含む商デジット選択回路を提供する。
【００２８】
前記の商デジット選択回路は第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路（Quotient negative circuit）を含み得る。更に商デジット選択回路は、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路（Inverted quotient zero circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路（Inverted quotient positive circuit）と、第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路（Inverted quotient negative circuit）とを含み得る。
【００２９】
更に本発明では、被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタと、オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタと、本発明の商デジット選択回路と、部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器とを含む浮動小数点正規形仮数除算回路（Floating point normalized mantissa division circuit）を提供する。同除算回路は商デジットを累算する商レジスタを含み得る。前記の部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示し得る。また、前記の加算器は桁上げ保留加算器であり得る。
【００３０】
更に、２進除算及び平方根演算において商デジットを冗長部分剰余から選択する方法であって、冗長部分剰余は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含む方法において、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを形成すべく第１和ビット、第２和ビット、第３和ビット及び第４和ビットを第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットに対して加算する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１である場合、または前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロであって、かつ第５和ビット及び第５桁上げビットの両方がゼロに等しい場合にのみ商デジットとしてゼロを選択する工程とを含む方法を提供する。
【００３１】
更に、前記の商デジットを選択する方法は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない状態と、第５和ビット及び第５桁上げビットが全てゼロにならない状態とのうちのいづれかにおいて、第１予測部分剰余ビットがゼロである場合にのみ商デジットとして＋１を選択する工程を含み得る。また、同商デジットを選択する方法は第１予測部分剰余ビットがアサートされ、さらには第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない場合にのみ商デジットとして−１を選択する工程を含み得る。
【００３２】
更に本発明では、２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路を形成する方法であって、冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、選択された商デジットは−１商デジットに該当するマイナス出力と、ゼロ商デジットに該当するゼロ出力と、＋１商デジットに該当するプラス出力とのうちのいづれか１つをアサートすることによって出力される方法において、第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器を形成する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器を形成する工程と、第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器を形成する工程と、第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートを形成する工程と、オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、前記ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路を形成する工程とを含む方法を提供する。
【００３３】
前記の商デジット選択回路を形成する方法は第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路を形成する工程を含み得る。商デジット選択回路は第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路を形成する工程を含み得る。４ビット・ゼロ検出器として４入力論理和ゲートを使用可能である。また、４ビット１検出器は４入力論理積ゲートであり得る。
【００３４】
更に本発明では、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路を形成する方法であって、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路を形成する工程とを含む方法を提供する。
【００３５】
前記の商ポジティブ回路を形成する工程は第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路を形成する工程を含み得る。
【００３６】
更に、前記の商ネガティブ回路を形成する工程は第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路を形成する工程と、第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路を形成する工程とを含み得る。
【００３７】
また本発明では、被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタを形成する工程と、オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタを形成する工程と、本発明の商デジット選択回路を形成する工程と、部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器を形成する工程とを含む浮動小数点正規形仮数除算回路を形成する方法を提供する。同方法は商デジットを累算する商レジスタを形成する工程を含み得る。また、部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示し得る。更に、加算器は桁上げ保留加算器であり得る。
【００３８】
本発明は浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算する能力を提供する。本発明は本発明に基づく商選択規則を最小限の待ち時間で実行するとともに、最小限のサイズを有する最適な商選択回路を提供する。
【００３９】
本発明は正確な結果が得られた際に、作業中の部分剰余が負になることを防止する更に効果的な商デジット選択関数を提供する。負の部分剰余はスティッキー・ビットの計算前に復元する必要がないため、１サイクルが削減される。
【００４０】
本発明に基づき、商デジット選択ロジックは負の除数に等しい部分剰余の形成を防止すべく変更される。正確な除算結果を実現する正確、かつ効果的なスティッキー・ビットの計算を行うために、負の除数に等しい負の部分剰余の形成を防止する必要がある。これを実現すべく商デジット選択関数を強化して、ハードウェアのコストの削減及び待ち時間の短縮を行い得る。このため、商デジット選択関数の強化は理想的な解決策である。予備最終部分剰余（Preliminary final partial remainder）を復元するための余分なメカニズムを提供する必要がないため、余分なハードウェアが排除される。負の予備部分剰余を復元する別のサイクル時間を必要としないため、待ち時間が短縮される。
【００４１】
本発明に基づき、実際の部分剰余がゼロの際に、１の商デジットに変えてゼロの商デジットを選択すべく商デジット選択ロジックが変更される。上位４ビットがゼロである５ビットからなる予測部分剰余を使用することにより、第４の上位ビットへの可能な桁上げ伝搬が検出される。これは冗長部分剰余のうちの第５の最上位和ビット及び桁上げビットの確認により実現可能である。これら両方がゼロである場合、同ビット位置から予測部分剰余の最下位ビット位置への桁上げ伝搬は不可能であり、ゼロの商デジットが選択される。冗長部分剰余の第５の最上位桁上げビット及び和ビットのうちの少なくともいづれか一方が１である別のケースでは、１の商デジットが選択される。
【００４２】
【発明の実施の形態】
浮動小数点演算において、負の最終部分剰余が生じた際にスティッキー・ビットを正確に計算すべく幾つかのオプションを検討する必要がある。最も簡単な解決策はゼロ検出を行う前に除数を加算することにより、負の最終部分剰余を復元することが挙げられる。別の桁上げ伝搬加算器を設置するために要する空間を考慮した場合、解決策は従来のハードウェアを利用する必要がある。これを実現する２つの方法を図３及び図４に示す。
【００４３】
図３に示す解決策は基本的な反復工程をインプリメントする従来の桁上げ保留加算器３００を利用している。通常の演算中、最終サイクル信号３０１はロー（Low）である。この結果、マルチプレクサ３０２，３０３は図１に関連して詳述した標準的反復工程をインプリメントすべく形成されている。しかし、最終サイクル中、最終サイクル信号３０１はハイ（High）であり、マルチプレクサ３０３はレジスタ３０５内に格納された部分剰余の桁上げ部分及び和部分に対して除数Ｄ３０４を加算すべく同除数Ｄ３０４を加算器３００へ出力する。予備部分剰余の符号が負の場合、マルチプレクサ３０６は加算器３００の結果を最終部分剰余フリップ・フロップ３０７に対して出力する。
【００４４】
図４に示す解決策では、図２に示すスティッキー・ビット計算を行う従来の桁上げ伝搬加算器４００を再び使用している。図１に示す反復データパス等のデータパスが所望の精度の商デジットを形成した後、冗長部分剰余の桁上げ部分ＰＲC及び和部分ＰＲSは最終サイクル信号がローの間にマルチプレクサ４０３，４０２へそれぞれ入力される。次いで、桁上げ伝搬加算器４００は冗長部分剰余を予備非冗長最終部分剰余（Preliminary non-redundant final partial remainder）へと削減する。桁上げ伝搬加算器４００の最上位出力ビット４０４は予備最終部分剰余の符号を示す。非冗長予備最終部分剰余はフリップ・フロップ４０６内へラッチされる。次いで、最終サイクル信号４０１がアサートされる。予備最終部分剰余が負であることを符号ビット４０４が示した場合、マルチプレクサ４０５は加算器４００に対して除数を出力するマルチプレクサ４０２に対して同除数を出力する。その一方、マルチプレクサ４０３は加算器４００に対する別の入力として予備非冗長部分剰余を出力する。次いで、ゼロ検出器４０７は復元された部分剰余を使用してスティッキー・ビットを形成する。符号ビットが負以外の部分剰余を示す場合、マルチプレクサ４０５は除数Ｄに代えてゼロを部分剰余に対して加算させる。
【００４５】
図３及び図４に示す前記の２つの解決策は、予備最終部分剰余が負の際にスティッキー・ビットを計算すべく別のマルチプレクサ・ハードウェアと、別のサイクルとを要する。マルチプレクサ３０２は部分剰余形成クリティカル・パス（Partial remainder formation critical path）上に配置されている。このため、図３に示す解決策は基本的反復のためのサイクル時間に影響を及ぼす。更に、パイプライン・スーパースカラ・プロセッサ内の待ち時間可変命令（Variable latency instructions）は命令スケジューリング及びバイパス制御ロジックを更に複雑にするため望ましくない。従って、スティッキー・ビットを正確に計算するために除算演算の全分布のうちの僅かな部分のみが余分なサイクルを必要とする場合にも、負の予備最終部分剰余を形成しない除算命令のための余分なサイクルを削除すべくプロセッサのデザインは更に複雑になる。従って、負の部分剰余を復元する正味の効果は、全ての除算及び平方根演算を行う別の待ち時間サイクルを必要とする。
【００４６】
本発明に基づき、商デジット選択ロジックは負の除数に等しい部分剰余の形成を防止するために変更される。正確な除算結果を実現するスティッキー・ビットを正確、かつ効果的に計算すべく、負の除数に等しい負の部分剰余の形成を防止する必要がある。これを実現すべく商デジット選択関数を強化することにより、ハードウェアが削減され、かつ待ち時間が短縮される。このため、同選択関数の強化は理想的な解決策である。予備最終部分剰余を復元するための余分なメカニズムを提供する必要がないため、余分なハードウェアを排除し得る。また、負の予備部分剰余を復元する別のサイクル時間を必要としないため待ち時間が短縮される。
【００４７】
本発明に基づく、商デジット選択ロジックは、実際の部分剰余がゼロの際に１の商デジットに代えてゼロの商デジットを選択すべく変更される。これは２ＰＲ［ｉ］est＝０００．０に対してｑ［ｉ＋１］＝０を選択することを示唆している。しかし、商デジット選択関数は実際の部分剰余より寧ろ予測部分剰余に対して作用するため、商選択ロジックの注意深いデザインが必要である。実際には予測部分剰余は１／２未満であり得るため、更に下位の冗長部分剰余ビットの加算は実際の部分剰余の上位４ビットのうちの最下位ビット位置へ１を伝搬させる。従って、実際の部分剰余は１／２以上になる。
【００４８】
実際の部分剰余が１／２（または１／２以上）である場合、除数は１／２≦Ｄ＜１に限定されるため、ｑ＝１を常に選択する必要がある。実際の部分剰余が１／２より更に大きく、かつｑ＝０が選択された場合、次の部分剰余は除数を最初に加算または減算することなく、実際の部分剰余を左側へ１ビットだけシフトすることによって得られる。この左シフトは正確な商への収束に必要な３／２の上限を越える次の実際の部分剰余を形成する。
【００４９】
正確な商デジットがゼロの際に、除数が実際の部分剰余より更に大きく、さらに商デジットとして＋１の値が選択された場合、このエラーは後の反復において補正可能である。しかし、予測部分剰余が０００．０であって、かつ正確な商デジットが１である際に商デジットとしてゼロが選択された場合、このエラーを補正する方法はない。ｑ＝１が正しい商デジットである際にｑ＝０が選択された場合、過小予測を補正する方法はない。結果は回復不能な誤りであり、次の部分剰余は正確な結果への収束に必要な所定の上下限の外に位置する。
【００５０】
全ての部分剰余に対する２進加算の実施は予測の問題を排除する。しかし、これはＳＲＴ除算のタイミング及び空間に関する効果を無効にする。ゼロの商デジットは全ての部分剰余がゼロである際にのみ選択可能である。しかし、全ての部分剰余に対するゼロの検出は同一の理由により逆効果となる。
【００５１】
前記の解決策に対する簡単な代替策としては、実際の部分剰余の上位４ビットのうちの最下位ビットへの可能な桁上げ伝搬を検出することが挙げられる。これは冗長部分剰余のうちの第５の最上位和ビット及び桁上げビット、即ちＰＲS,msb-4及びＰＲC,msb-4を確認することによって実現し得る。ＰＲS,msb-4及びＰＲC,msb-4がそれぞれゼロである場合、そのビット位置から予測部分剰余の最下位ビット位置への桁上げ伝搬は不可能であり、さらにはゼロの商デジットを選択する必要がある。冗長部分剰余の第５の最上位桁上げビット及び和ビットのうちの少なくともいづれか一方が１である別のケースでは、１の商デジットを選択する必要がある。部分剰余のうちの複数の下位ビットがゼロでない場合にも、同部分剰余は所定の上下限（−５／２≦２ＰＲ≦３／２）内に存在し、かつ正しい結果が依然算出されることになる。
【００５２】
予測部分剰余の計算に必要な桁上げ伝搬加算は実際の冗長部分剰余の上位４つの伝搬ビット及び和ビットに対してのみ行われる。このため、本発明に基づく計算の待ち時間に対する影響は最低限に抑制される。表４は本発明に基づく正確な商選択ロジックのための真理値表を示す。
【００５３】
【表４】
【００５４】
ランダム・ロジック５０４のブロックはＳＲＴ除算に基づく可能な商デジット値のうちの１つにそれぞれ該当する３つの信号（Ｍ、Ｚ及びＰ）を形成する。Ｍは−１の商デジットに該当する。Ｚはゼロの商デジットに該当する。Ｐは＋１の商デジットに該当する。Ｍはｘ［３］がデアサートされ、かつｎ１がデアサートされた場合にのみアサートされる。Ｚはｎ１がアサートされるか、またはｉ０及びｎ０がアサートされた場合にのみアサートされる。ＰはＸ［３］がアサートされ、ｎ０またはｉ０がデアサートされた場合にのみアサートされる。各論理関係を仮定した場合、商デジット信号Ｍ、Ｚ及びＰのうちの任意の２つを同時にアサートすることは不可能である。
【００５５】
図５に示すインプリメンテーションは論理的に正しい。しかし実際には、４ビット２進加算器及びその後のロジックは統合され、さらには最適化されたロジック・インプリメンテーションへの併合が可能である。図６に示すように、５段階ロジック・インプリメンテーション（Five-stage logic implementation）は空間を更に効果的に使用するとともに、出力を更に短い遅延時間を伴って形成する。
【００５６】
図６に示すインプリメンテーションでは、Ｍ、Ｚ及びＰが計算されるとともに、論理反転／Ｍ、／Ｚ及び／Ｐも計算される。これはデコードされた選択入力を有するＣＭＯＳマルチプレクサ内等において伝達ゲートをイネーブルするために商信号を使用する際に効果的である。Ｍ及び／Ｍは冗長部分剰余ビットの上位４ビット（２ＰＲＣ［ｍｓｂ：ｍｓｂ−３］及び２ＰＲＳ［ｍｓｂ：ｍｓｂ−３］）にのみ依存する。その一方、Ｚ、Ｐ、／Ｚ及び／Ｐは全て冗長部分剰余の上位５ビット（２ＰＲＣ［ｍｓｂ：ｍｓｂ−４］及び２ＰＲＳ［ｍｓｂ：ｍｓｂ−４］）に依存する。図６のセルは回路が占める空間の削減を第２の課題とする一方で、主に遅延を最小限に抑制すべく最適化されている。図６に示す殆どの論理は空間を削減すべく幾つかの出力計算の間において共有されている。
【００５７】
本発明に基づく基数２を使用する新たな商デジット選択論理（Radix-2 quotient digit selection logic）をインプリメントするために必要な別のゲートの総数は比較的少ない。好ましい実施の形態のインプリメンテーションに関するスパイス・シミュレーション分析（Spice simulation analysis）において、商選択論理クリティカル・タイミング・パス（Quotient selection logic critical timing path）が５％未満であることが示されている。
【００５８】
更に遅い商選択ロジックと、最後に行われる部分剰余復元サイクルの排除との間には、インプリメンテーションに依存するタイミング・トレードオフが存在する。僅かにより複雑な商選択論理に起因する遅延の増加がプロセッサ・サイクル時間（Processor cycle time）を制限しない場合、性能の増加は負の最終部分剰余の復元に必要とされる待ち時間サイクルの削減により常には実現される。本発明のハードウェア除算器等を含む最近のマイクロプロセッサでは、プロセッサ・サイクル時間は他のクリティカル・パスによって決定されるか、またはプロセッサを設計する前に任意で適合させ得る。商選択ロジックのうちの増大した遅延が最長パスでないケースにおいて、各除算演算あたり１サイクルの正味節約は新たな出費を伴うことなく実現し得る。
【００５９】
図６に示す実施の形態において、変更された商選択ロジック・アルゴリズムは内部浮動小数点除算器クリティカル・パス（Internal floating point divider critical path）の速度を従来の商選択規則を使用して最適化された同等のクリティカル・パスより約１００ｐｓ遅くする。これは２パーセント未満の速度低下に相当する。プロセッサの限界タイミング・パス（Limiting timing path）は更に長い。従って、改善された商選択ロジックはプロセッサ・サイクル時間に悪影響を及ぼさない。スティッキー検出（Sticky detection）前に部分剰余を復元するサイクルを排除する効果が実現される。
【００６０】
本発明の商選択ロジックを使用しても負の最終部分剰余は依然形成され得る。しかし、負の最終部分剰余が形成された際、本発明に基づく商選択ロジックは負の部分剰余が負の除数より更に大きいことを保証する。従って、本発明に基づく負の最終部分剰余が形成された場合、Ｑ−１が選択され、結果は必ず不正確になる。この結果、負の最終部分剰余が負の除数に等しくなる恐れを伴うことなくスティッキー・ビットを安全にアサートし得る。
【００６１】
符号検出及びスティッキー・ビット計算を平行して実施する一方で、ハードウェアの節約が可能である。５９ビット全加算器を使用する代わりに、５９ビット符号検出加算器（59-bit sign detect adder）を使用し得る。これはタイミングを僅かに改善する一方で、主に空間の節約を実現する。ゼロ検出は冗長部分剰余を２進数へ変換する明確な加算を伴うことなく行える。
【００６２】
【数４】
【００６３】
【数５】
【００６４】
以上、本発明を好ましい実施の形態に基づいて詳述したが、同実施の形態は例示を目的とするものであって、本発明を限定するものではない。当業者は必要に応じて本発明の実施の形態を変更することが可能であり、同変更は請求項に開示する本発明の範囲及び精神を逸脱しないものとする。例えば、図６に示す商選択ロジックの最適化された論理インプリメンテーションは各種の同等の方法を用いて設計し得る。また、図６に示す回路は標準的なＣＭＯＳ伝達ゲート・マルチプレクサ（CMOS transmission gate multiplexor）に代えて、ｎ−チャネル・パス・トランジスタ・マルチプレクサ（n-channel pass transistor multiplexor）を制御すべく商デジットの正の極性のみを計算し、論理反転の計算を削除できる。最適化された異なるインプリメンテーションは異なる技術（例：ＮＭＯＳ、ＥＣＬ等）におけるインプリメンテーション、または同一技術に属する異なる設計規則及び設計ツールを用いたインプリメンテーションの結果である。請求項は表４に示す真理値表の全ての回路インプリメンテーションを網羅することを目的とする。従って、本発明の技術分野の当業者にとって自明な各種の変更及び修正は、本発明の精神及び範囲に属する。
【００６５】
【発明の効果】
以上詳述したように、本発明によれば、浮動小数点除算及び平方根演算中、最終部分剰余が負の場合にスティッキー・ビットを正確、かつ効果的に計算し得る。更に、本発明は商選択規則を実行する際の待ち時間を短縮するとともに、最小限のサイズを有する最適な商選択回路及び同商選択回路を含む除算回路を実現するという優れた効果を発揮する。
【図面の簡単な説明】
【図１】反復ＳＲＴ除算アルゴリズムをインプリメントする従来のハードウェア除算モジュールの簡単な論理図。
【図２】従来のスティッキー・ビット演算回路の簡単な論理図。
【図３】反復ＳＲＴ除算アルゴリズムをインプリメントするか、または負の最終部分剰余を復元する１つのハードウェア除算モジュールの簡単な論理図。
【図４】反復ＳＲＴ除算アルゴリズムをインプリメントするか、または負の最終部分剰余を復元する別のハードウェア除算モジュールの簡単な論理図。
【図５】本発明の商選択規則をインプリメントする回路の簡単な論理図。
【図６】商デジット信号及びその論理反転を形成する商選択規則をインプリメントする回路の詳細な論理図。
【符号の説明】
３００…桁上げ保留加算器、３０１，４０１…最終サイクル信号、３０２，３０３，３０６，４０３，４０２，４０５…マルチプレクサ、３０４…除数、３０５…レジスタ、３０７，４０６…フリップ・フロップ、４００…桁上げ伝搬加算器、４０４…最上位出力ビット、４０４…符号ビット、４０７…ゼロ検出器、５００…４ビット桁上げ伝搬加算器、５０１…オール・ゼロ検出器、５０２…オール・ワン検出器、５０３…否定論理和ゲート、５０４…ランダム・ロジック。
Claims (27)
- ２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路であって、前記冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、前記選択された商デジットは−１商デジットに該当するマイナス出力と、ゼロ商デジットに該当するゼロ出力と、＋１商デジットに該当するプラス出力とのうちのいづれか１つをアサートすることによって出力される商デジット選択回路において、
前記第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器と、
前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、前記オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器と、
前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、前記オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器と、
前記第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートと、
前記オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、前記ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路と
を含む商デジット選択回路。 - 前記第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、前記プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路を含む請求項１に記載の商デジット選択回路。
- 前記第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、前記マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路を含む請求項２に記載の商デジット選択回路。
- 前記４ビット・ゼロ検出器は４入力論理和ゲートである請求項１に記載の商デジット選択回路。
- 前記４ビット１検出器は４入力論理積ゲートである請求項１に記載の商デジット選択回路。
- 第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路であって、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路と
を含む商デジット選択回路。 - 前記第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路を含む請求項６に記載の商デジット選択回路。
- 前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路と
を含む請求項７に記載の商デジット選択回路。 - 被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタと、
オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタと、
請求項７に記載の商デジット選択回路と、
前記部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器と
を含む浮動小数点正規形仮数除算回路。 - 商デジットを累算する商レジスタを含む請求項９に記載の浮動小数点正規形仮数除算回路。
- 前記部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示される請求項１０に記載の浮動小数点正規形仮数除算回路。
- 前記加算器は桁上げ保留加算器である請求項１１に記載の浮動小数点正規形仮数除算回路。
- ２進除算及び平方根演算において商デジットを冗長部分剰余から選択する方法であって、前記冗長部分剰余は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含む方法において、
第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを形成すべく第１和ビット、第２和ビット、第３和ビット及び第４和ビットを第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットに対して加算する工程と、
前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１である場合、または前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロであって、かつ第５和ビット及び第５桁上げビットの両方がゼロに等しい場合にのみ商デジットとしてゼロを選択する工程と
を含む方法。 - 前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない状態と、第５和ビット及び第５桁上げビットが全てゼロにならない状態とのうちのいづれかにおいて、前記第１予測部分剰余ビットがゼロである場合にのみ商デジットとして＋１を選択する工程を含む請求項１３に記載の商デジットを選択する方法。
- 前記第１予測部分剰余ビットがアサートされ、さらには第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロにならない場合にのみ商デジットとして−１を選択する工程を含む請求項１３に記載の商デジットを選択する方法。
- ２進除算及び平方根演算における商デジットを冗長部分剰余入力に基づいて決定する商デジット選択回路を形成する方法であって、前記冗長部分剰余入力は第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビットを含み、前記選択された商デジットは−１商デジットに該当するマイナス出力と、ゼロ商デジットに該当するゼロ出力と、＋１商デジットに該当するプラス出力とのうちのいづれか１つをアサートすることによって出力される方法において、
前記第１和ビット、第２和ビット、第３和ビット及び第４和ビット並びに第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビットを入力され、そして第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを出力として形成する４ビット桁上げ伝搬加算器を形成する工程と、
前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ゼロ信号を形成し、前記オール・ゼロ信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全てゼロの場合にのみアサートされる４ビット・ゼロ検出器を形成する工程と、
前記第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットを入力され、そしてオール・ワン信号を形成し、前記オール・ワン信号は第１予測部分剰余ビット、第２予測部分剰余ビット、第３予測部分剰余ビット及び第４予測部分剰余ビットが全て１の場合にのみアサートされる４ビット１検出器を形成する工程と、
前記第５和ビット及び第５桁上げビットを入力され、そして第５ビット・ゼロ信号を形成する否定論理和ゲートを形成する工程と、
前記オール・ワン信号、第５ビット・ゼロ信号及びオール・ゼロ信号を入力され、そしてゼロ出力を形成し、前記ゼロ出力はオール・ワン信号がアサートされるか、または第５ビット・ゼロ信号及びオール・ゼロ信号の両方がアサートされた場合にのみアサートされるゼロ回路を形成する工程と
を含む方法。 - 前記第１予測部分剰余ビット、オール・ゼロ信号及び第５ビット・ゼロ信号を入力され、そしてプラス出力を形成し、前記プラス出力は第１予測部分剰余ビットがデアサートされ、かつオール・ゼロ信号または第５ビット・ゼロ信号がデアサートされた場合にのみアサートされるプラス回路を形成する工程を含む請求項１６に記載の方法。
- 前記第１予測部分剰余ビット及びオール・ワン信号を入力され、そしてマイナス出力を形成し、前記マイナス出力は第１予測部分剰余ビットがアサートされ、かつオール・ワン信号がデアサートされた場合にのみアサートされるマイナス回路を形成する工程を含む請求項１７に記載の方法。
- 前記４ビット・ゼロ検出器は４入力論理和ゲートである請求項１６に記載の方法。
- 前記４ビット１検出器は４入力論理積ゲートである請求項１６に記載の方法。
- 第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして商デジットを計算する商デジット選択回路を形成する方法であって、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてゼロ出力を形成する商ゼロ回路を形成する工程と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そしてプラス出力を形成する商ポジティブ回路を形成する工程と
を含む方法。 - 前記第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そしてマイナス出力を形成する商ネガティブ回路を形成する工程を含む請求項２１に記載の方法。
- 前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたゼロ出力を形成する反転商ゼロ回路を形成する工程と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット、第４桁上げビット及び第５桁上げビット並びに第１和ビット、第２和ビット、第３和ビット、第４和ビット及び第５和ビットを入力され、そして反転されたプラス出力を形成する反転商ポジティブ回路を形成する工程と、
前記第１桁上げビット、第２桁上げビット、第３桁上げビット及び第４桁上げビット並びに第１和ビット、第２和ビット、第３和ビット及び第４和ビットを入力され、そして反転されたマイナス出力を形成する反転商ネガティブ回路を形成する工程と
を含む請求項２２に記載の方法。 - 被除数を第１の反復中に入力され、次いで左シフトされた部分剰余をその後の複数の反復中に入力され、そして出力として部分剰余を形成する部分剰余レジスタを形成する工程と、
オペランド除数を第１の反復中に入力され、そして出力として除数を形成する除数レジスタを形成する工程と、
請求項２２に記載の商デジット選択回路を形成する工程と、
前記部分剰余と、商デジット及び除数の否定論理積とを入力され、そして左シフトされた部分剰余を形成する加算器を形成する工程と
を含む浮動小数点正規形仮数除算回路を形成する方法。 - 商デジットを累算する商レジスタを形成する工程を含む請求項２４に記載の方法。
- 前記部分剰余は桁上げ部分及び和部分を有する桁上げ保留の形態で表示される請求項２５に記載の方法。
- 前記加算器は桁上げ保留加算器である請求項２６に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/498,397 US5787030A (en) | 1995-07-05 | 1995-07-05 | Correct and efficient sticky bit calculation for exact floating point divide/square root results |
| US08/498397 | 1995-07-05 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0934691A JPH0934691A (ja) | 1997-02-07 |
| JP3689183B2 true JP3689183B2 (ja) | 2005-08-31 |
Family
ID=23980922
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16750896A Expired - Fee Related JP3689183B2 (ja) | 1995-07-05 | 1996-06-27 | 正確な浮動小数点除算／平方根演算を実現する正確、かつ効果的なスティッキー・ビット計算 |
Country Status (3)
| Country | Link |
|---|---|
| US (2) | US5787030A (ja) |
| JP (1) | JP3689183B2 (ja) |
| KR (1) | KR100323338B1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI754680B (zh) * | 2016-11-03 | 2022-02-11 | 南韓商三星電子股份有限公司 | 產生起始估算值的裝置及方法、製造方法及測試方法 |
Families Citing this family (56)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5995992A (en) * | 1997-11-17 | 1999-11-30 | Bull Hn Information Systems Inc. | Conditional truncation indicator control for a decimal numeric processor employing result truncation |
| US6594681B1 (en) * | 1998-11-04 | 2003-07-15 | Sun Microsystems, Inc. | Quotient digit selection logic for floating point division/square root |
| US6732135B1 (en) * | 1999-02-01 | 2004-05-04 | Hewlett-Packard Development Company, L.P. | Method and apparatus for accumulating partial quotients in a digital processor |
| US6360241B1 (en) * | 1999-02-01 | 2002-03-19 | Compaq Information Technologies Goup, L.P. | Computer method and apparatus for division and square root operations using signed digit |
| JP2002063025A (ja) * | 2000-08-18 | 2002-02-28 | Fujitsu Ltd | 可変長データ処理用プロセッサ |
| JP3793505B2 (ja) * | 2000-09-26 | 2006-07-05 | 株式会社ルネサステクノロジ | 演算器及びそれを用いた電子回路装置 |
| US7031996B2 (en) * | 2000-11-02 | 2006-04-18 | Seagate Technology Llc | Calculating square root of binary numbers with fixed-point microprocessor |
| US6792443B2 (en) * | 2001-06-29 | 2004-09-14 | Intel Corporation | Economical on-the-fly rounding for digit-recurrence algorithms |
| EP1315080A1 (en) * | 2001-11-22 | 2003-05-28 | STMicroelectronics Limited | Circuitry for carrying out square root and division operations |
| EP1315081B1 (en) * | 2001-11-22 | 2008-05-07 | STMicroelectronics Limited | Circuitry for carrying out at least one of a square root operation and a division operation |
| EP1315079A1 (en) * | 2001-11-22 | 2003-05-28 | STMicroelectronics Limited | Circuit for calculation of division and square root with floating point numbers |
| EP1315082A1 (en) | 2001-11-22 | 2003-05-28 | STMicroelectronics Limited | Iteration circuitry for carrying out square root operation on floating point numbers |
| EP1315077A1 (en) * | 2001-11-23 | 2003-05-28 | STMicroelectronics Limited | Circuitry and method for performing floating point compare operations |
| US7127483B2 (en) * | 2001-12-26 | 2006-10-24 | Hewlett-Packard Development Company, L.P. | Method and system of a microprocessor subtraction-division floating point divider |
| EP1485904B1 (en) * | 2002-03-13 | 2012-08-29 | Dolby Laboratories Licensing Corporation | High dynamic range display devices |
| US7016930B2 (en) * | 2002-10-25 | 2006-03-21 | Arm Limited | Apparatus and method for performing operations implemented by iterative execution of a recurrence equation |
| US7139786B2 (en) | 2003-05-12 | 2006-11-21 | Sun Microsystems, Inc. | Method and apparatus for efficiently performing a square root operation |
| US7660842B2 (en) * | 2003-05-12 | 2010-02-09 | Sun Microsystems, Inc. | Method and apparatus for performing a carry-save division operation |
| US7185178B1 (en) | 2004-06-30 | 2007-02-27 | Sun Microsystems, Inc. | Fetch speculation in a multithreaded processor |
| US7478225B1 (en) | 2004-06-30 | 2009-01-13 | Sun Microsystems, Inc. | Apparatus and method to support pipelining of differing-latency instructions in a multithreaded processor |
| US7330988B2 (en) * | 2004-06-30 | 2008-02-12 | Sun Microsystems, Inc. | Method and apparatus for power throttling in a multi-thread processor |
| US7437538B1 (en) | 2004-06-30 | 2008-10-14 | Sun Microsystems, Inc. | Apparatus and method for reducing execution latency of floating point operations having special case operands |
| US7890734B2 (en) * | 2004-06-30 | 2011-02-15 | Open Computing Trust I & II | Mechanism for selecting instructions for execution in a multithreaded processor |
| US8095778B1 (en) | 2004-06-30 | 2012-01-10 | Open Computing Trust I & II | Method and system for sharing functional units of a multithreaded processor |
| US7523330B2 (en) * | 2004-06-30 | 2009-04-21 | Sun Microsystems, Inc. | Thread-based clock enabling in a multi-threaded processor |
| US7426630B1 (en) | 2004-06-30 | 2008-09-16 | Sun Microsystems, Inc. | Arbitration of window swap operations |
| US7343474B1 (en) | 2004-06-30 | 2008-03-11 | Sun Microsystems, Inc. | Minimal address state in a fine grain multithreaded processor |
| US7401206B2 (en) * | 2004-06-30 | 2008-07-15 | Sun Microsystems, Inc. | Apparatus and method for fine-grained multithreading in a multipipelined processor core |
| US7747771B1 (en) | 2004-06-30 | 2010-06-29 | Oracle America, Inc. | Register access protocol in a multihreaded multi-core processor |
| US7178005B1 (en) | 2004-06-30 | 2007-02-13 | Sun Microsystems, Inc. | Efficient implementation of timers in a multithreaded processor |
| US7774393B1 (en) | 2004-06-30 | 2010-08-10 | Oracle America, Inc. | Apparatus and method for integer to floating-point format conversion |
| US7373489B1 (en) | 2004-06-30 | 2008-05-13 | Sun Microsystems, Inc. | Apparatus and method for floating-point exception prediction and recovery |
| US7216216B1 (en) | 2004-06-30 | 2007-05-08 | Sun Microsystems, Inc. | Register window management using first pipeline to change current window and second pipeline to read operand from old window and write operand to new window |
| US7370243B1 (en) | 2004-06-30 | 2008-05-06 | Sun Microsystems, Inc. | Precise error handling in a fine grain multithreaded multicore processor |
| US7941642B1 (en) | 2004-06-30 | 2011-05-10 | Oracle America, Inc. | Method for selecting between divide instructions associated with respective threads in a multi-threaded processor |
| US7533248B1 (en) | 2004-06-30 | 2009-05-12 | Sun Microsystems, Inc. | Multithreaded processor including a functional unit shared between multiple requestors and arbitration therefor |
| US7861063B1 (en) | 2004-06-30 | 2010-12-28 | Oracle America, Inc. | Delay slot handling in a processor |
| US8225034B1 (en) | 2004-06-30 | 2012-07-17 | Oracle America, Inc. | Hybrid instruction buffer |
| US7383403B1 (en) | 2004-06-30 | 2008-06-03 | Sun Microsystems, Inc. | Concurrent bypass to instruction buffers in a fine grain multithreaded processor |
| US7702887B1 (en) | 2004-06-30 | 2010-04-20 | Sun Microsystems, Inc. | Performance instrumentation in a fine grain multithreaded multicore processor |
| US7434000B1 (en) | 2004-06-30 | 2008-10-07 | Sun Microsystems, Inc. | Handling duplicate cache misses in a multithreaded/multi-core processor |
| US7676655B2 (en) * | 2004-06-30 | 2010-03-09 | Sun Microsystems, Inc. | Single bit control of threads in a multithreaded multicore processor |
| US7353364B1 (en) | 2004-06-30 | 2008-04-01 | Sun Microsystems, Inc. | Apparatus and method for sharing a functional unit execution resource among a plurality of functional units |
| US8037250B1 (en) | 2004-12-09 | 2011-10-11 | Oracle America, Inc. | Arbitrating cache misses in a multithreaded/multi-core processor |
| JP4273071B2 (ja) * | 2004-12-15 | 2009-06-03 | エヌイーシーコンピュータテクノ株式会社 | 除算・開平演算器 |
| US7539720B2 (en) * | 2004-12-15 | 2009-05-26 | Sun Microsystems, Inc. | Low latency integer divider and integration with floating point divider and method |
| US7752250B2 (en) * | 2006-01-12 | 2010-07-06 | International Business Machines Corporation | Rounding floating point division results |
| ES2893327T3 (es) * | 2007-02-01 | 2022-02-08 | Dolby Laboratories Licensing Corp | Calibración de visualizadores que tienen luz de fondo espacialmente variable |
| US20100115494A1 (en) * | 2008-11-03 | 2010-05-06 | Gorton Jr Richard C | System for dynamic program profiling |
| US8024719B2 (en) | 2008-11-03 | 2011-09-20 | Advanced Micro Devices, Inc. | Bounded hash table sorting in a dynamic program profiling system |
| US8478948B2 (en) * | 2008-12-04 | 2013-07-02 | Oracle America, Inc. | Method and system for efficient tracing and profiling of memory accesses during program execution |
| US20100214282A1 (en) | 2009-02-24 | 2010-08-26 | Dolby Laboratories Licensing Corporation | Apparatus for providing light source modulation in dual modulator displays |
| US8452831B2 (en) * | 2009-03-31 | 2013-05-28 | Oracle America, Inc. | Apparatus and method for implementing hardware support for denormalized operands for floating-point divide operations |
| US8817875B2 (en) * | 2009-08-13 | 2014-08-26 | The Johns Hopkins University | Methods and systems to encode and decode sequences of images |
| US9086890B2 (en) | 2012-01-06 | 2015-07-21 | Oracle International Corporation | Division unit with normalization circuit and plural divide engines for receiving instructions when divide engine availability is indicated |
| US10706101B2 (en) | 2016-04-14 | 2020-07-07 | Advanced Micro Devices, Inc. | Bucketized hash tables with remap entries |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5023827A (en) * | 1988-08-18 | 1991-06-11 | Digital Equipment Corporation | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction |
| US5272660A (en) * | 1992-06-01 | 1993-12-21 | Motorola, Inc. | Method and apparatus for performing integer and floating point division using a single SRT divider in a data processor |
| US5386376A (en) * | 1992-08-31 | 1995-01-31 | Intel Corporation | Method and apparatus for overriding quotient prediction in floating point divider information processing systems |
| US5258944A (en) * | 1992-09-01 | 1993-11-02 | Cray Research, Inc. | High performance mantissa divider |
| US5357455A (en) * | 1992-10-09 | 1994-10-18 | Intel Corporation | Floating point remainder generator for a math processor |
-
1995
- 1995-07-05 US US08/498,397 patent/US5787030A/en not_active Expired - Fee Related
-
1996
- 1996-05-15 US US08/648,410 patent/US5954789A/en not_active Expired - Lifetime
- 1996-06-27 JP JP16750896A patent/JP3689183B2/ja not_active Expired - Fee Related
- 1996-07-03 KR KR1019960026783A patent/KR100323338B1/ko not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI754680B (zh) * | 2016-11-03 | 2022-02-11 | 南韓商三星電子股份有限公司 | 產生起始估算值的裝置及方法、製造方法及測試方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5954789A (en) | 1999-09-21 |
| JPH0934691A (ja) | 1997-02-07 |
| KR970008882A (ko) | 1997-02-24 |
| US5787030A (en) | 1998-07-28 |
| KR100323338B1 (ko) | 2002-06-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3689183B2 (ja) | 正確な浮動小数点除算／平方根演算を実現する正確、かつ効果的なスティッキー・ビット計算 | |
| Zhang et al. | Efficient multiple-precision floating-point fused multiply-add with mixed-precision support | |
| Obermann et al. | Division algorithms and implementations | |
| US6594681B1 (en) | Quotient digit selection logic for floating point division/square root | |
| EP0450754B1 (en) | High speed dividers | |
| US6847985B1 (en) | Floating point divide and square root processor | |
| US5696712A (en) | Three overlapped stages of radix-2 square root/division with speculative execution | |
| JP3609512B2 (ja) | 演算器 | |
| Lang et al. | A radix-10 digit-recurrence division unit: algorithm and architecture | |
| US5132925A (en) | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| US5023827A (en) | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| Bruguera | Low latency floating-point division and square root unit | |
| US8019805B1 (en) | Apparatus and method for multiple pass extended precision floating point multiplication | |
| US6941334B2 (en) | Higher precision divide and square root approximations | |
| JPH05250146A (ja) | 整数累乗処理を行なうための回路及び方法 | |
| EP0436905B1 (en) | High performance adder using carry predictions | |
| US7016930B2 (en) | Apparatus and method for performing operations implemented by iterative execution of a recurrence equation | |
| Dixit et al. | FPGA accomplishment of a 16-bit divider | |
| US6598065B1 (en) | Method for achieving correctly rounded quotients in algorithms based on fused multiply-accumulate without requiring the intermediate calculation of a correctly rounded reciprocal | |
| US7127483B2 (en) | Method and system of a microprocessor subtraction-division floating point divider | |
| US7660842B2 (en) | Method and apparatus for performing a carry-save division operation | |
| US6615228B1 (en) | Selection based rounding system and method for floating point operations | |
| Baesler et al. | FPGA implementation of a decimal floating-point accurate scalar product unit with a parallel fixed-point multiplier | |
| JPH04172526A (ja) | 浮動小数点除算器 | |
| US5208769A (en) | Unsigned integer multiply/divide circuit |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050428 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050517 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050610 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |