(57)【特許請求の範囲】
【請求項１】
分岐を有する命令を含むコンピュータシステムにおいて分岐予測テーブル汚染を低減するための方法であって、
分岐予測構造を利用して分岐についての分岐ターゲットアドレスを予測するステップと、
分岐を処理するステップと、
実際の分岐ターゲットアドレスを計算するステップと、
前記分岐予測構造に格納されない前記実際の分岐ターゲットアドレスのビットと、前記予測された分岐ターゲットアドレスの対応するビットとを比較するステップと、
特定の命令と共に流れる比較ビットを該命令と共に設定するステップと、
前記比較ビットが前記比較の結果の一致を示す場合に、前記実際の分岐アドレスの一部を前記分岐予測構造に格納し、前記比較ビットが前記比較の結果の一致を示さない場合に、前記実際の分岐アドレスの如何なる部分も前記分岐予測構造に格納しないステップと、
からなる方法。
【請求項２】
分岐を有する命令を含むコンピュータシステムにおいて分岐予測テーブル汚染を低減するための装置であって、
分岐ターゲットを予測する分岐ターゲットバッファ（ＢＴＢ）と、
前記ＢＴＢに接続された分岐アドレスコンパレータ（ＢＡＣ）とを備え、
該ＢＡＣが、前記分岐ターゲットを計算し、及び比較ビットを設定し、前記計算が、分岐ターゲットアドレスの実装されていないビットと実際の分岐ターゲットアドレス内の対応するビットとが一致するか否か比較し、前記比較ビットが命令と共に設定されて該命令と共に流れ、前記一致が生じた場合に、前記ＢＡＣが、前記分岐ターゲットアドレスの一部を前記ＢＴＢに書き込まれるよう割り当てることを特徴とする装置。
【請求項３】
前記ＢＡＣが分岐導出テーブルを備え、この分岐導出テーブルが、
分岐ターゲットアドレス情報と、
比較結果を示す比較ビットとを含む、請求項２に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にコンピュータアーキテクチャの分野に関する。より詳細には、
本発明は、処理動作を改善するための手段として分岐予測を使用するコンピュータアーキテクチャの分野に関する。
【０００２】
【従来の技術】
近年のマイクロプロセッサは、命令を処理するために、長いパイプラインを用いる場合が多い。これらの長いパイプラインを用いることによる副次的な作用は、分岐によるペナルティ、不利な条件が増加することである。分岐によるペナルティは、命令シーケンスをリダイレクトしなければならない。通常、この分岐動作は、少なくともパイプラインの一部をフラッシュする必要があり、それによりパイプライン動作の効率が低下する。分岐予測構造は、このようなペナルティー、不利な条件を低減するために、一般にハードウエアで実施される。
【０００３】
分岐予測構造は、分岐ターゲットを予測し、分岐予測テーブルに分岐ターゲット情報を記憶することができる。しかしながら、分岐ターゲット構造に記憶された分岐ターゲット情報の中には正しくないもの又は誤りもある。これらの誤りは、ターゲットアドレスの一部のみが、分岐予測テーブルに記憶されるために生じる場合もある。これらの場合には、ターゲットアドレスの残りの部分は、典型的には現在の命令アドレスからのビットを用いて推定される。この仮定が誤っている場合には、分岐予測構造内のエントリが無駄に消費され、及び／又は非効率な分岐予測を行うようになる。この不正確な情報は、次の分岐予測のために用いることができず、そのため無駄である。この無駄な情報の存在は、分岐汚染と呼ばれる。
【０００４】
【発明が解決しようとする課題】
本発明の課題は、分岐予測テーブル汚染を低減するための方法を提供することである。
【０００５】
【課題を解決するための手段】
コンパレータ、すなわち比較器が、予測された分岐ターゲットのエイリアシングビットを現在の命令アドレスの対応するビットと比較する。エイリアシングビットのアドレスの比較は、分岐ターゲットアドレスが分岐予測構造のための分岐ターゲット範囲の外にあるか否かを判定するために行われる。エイリアシングビットが一致する場合には、分岐ターゲットアドレスが現在の命令と同じメモリブロック内に存在しているという仮定は正しく、分岐予測が使用可能である。エイリアシングビットが一致しない場合には、分岐予測は不正確である。
【０００６】
比較の結果は、分岐導出テーブルに記憶される。分岐導出テーブルは、パイプライン内にあるが、まだリタイア、すなわち退避していない分岐を記憶する。分岐命令が退避すると、対応する分岐エントリがアクセスされ、比較結果ビットが検査される。比較結果ビットが、分岐ターゲットがエイリアシングしないことを示す場合には、分岐エントリを更新して、さらに分岐の発生を予測できるような分岐予測構造とすることができる。そうでない場合には、分岐エントリは挿入されない。エントリが誤った分岐ターゲットをもたらしている場合、分岐エントリの挿入を避けることによって、より有用な予測のために利用することができる分岐予測構造内のエントリ空間を節約し、誤った分岐ターゲットを利用することにより結果生じる、付加的な誤った予測を潜在的に防ぐことができる。
【０００７】
代替的な実施形態では、同じ比較結果ビットは、命令が退避するまで、その命令の残りの部分とともにパイプライン内を流れる。比較結果ビットが、エイリアシングビットが一致することを示すのであれば、退避時に、そのエントリは、分岐予測構造内に挿入されるようになる。
【０００８】
【発明の実施の形態】
以下の詳細な説明は図面を参照しており、その図面では、同様の参照番号は同様の部分を示す。
【０００９】
最近のコンピュータシステムでは、命令を処理中に、予め予測できない不可避の１つ以上の分岐がその処理に続く場合がある。誤った分岐予測の結果によって、処理上の著しいペナルティが生じることがある。具体的には、深くパイプライン化された装置を用いる場合、おおよそ数サイクルの、分岐のペナルティ、問題が生じる場合がある。分岐後に、分岐ターゲットが命令を取り出し、フェッチ（fetch）し始めることが決定されるまで、コンピュータシステムが待機する場合には、クロックサイクルが無駄にされる。この遅延を避けるために、分岐予測構造は、命令フェッチユニットが命令をフェッチするのに応じて、分岐のターゲットを予測する。予測機能は投機的であり、誤っている場合もある。しかしながら、誤った予測が行われると、プロセッサはそれを検出し、再生することができる。直接分岐のターゲットの分岐予測構造によって行われる予測は、分岐アドレス計算装置によって下流で検査される場合がある。分岐予測構造が予測をもたらさない場合には、分岐アドレス計算装置がターゲットを計算し、フェッチユニット（fetch unit）を再誘導（re-steer）することもできる。最終的に、一旦分岐が識別されれば、分岐予測構造は、その分岐命令のターゲットを予測することができる。
【００１０】
このような分岐予測構造の一実施形態では、多数の分岐に対する分岐ターゲットは、パイプラインにおいて以前より知られているが、分岐ターゲットは、分岐命令が退避するまで、分岐予測構造に入れられない。このような分岐予測構造に含まれることがあるデータフィールドの１つは、分岐ターゲットアドレスである。空間あるいはタイミングの制約のために、コンピュータシステム、特に分岐予測構造は、分岐ターゲットアドレスの一部のみを格納する場合がある。残りのデータビット（エイリアシングビットと呼ばれる）は、分岐のアドレス、それ自体から暗示される。分岐命令は、現在の命令と同じメモリ範囲内の別の命令をターゲットにすることが、暗黙のうちに仮定されている。例えば３２ビットからなる下位の２０ビットが分岐ターゲットのために格納される場合、予測される分岐ターゲットは、その分岐ターゲットが分岐命令それ自体と同じ１Ｍバイト範囲（２の20乗）内にある場合にのみ有効である。上位の１２ビットのうちの任意のビットが一致しない場合には、この仮定は不正確である、又は誤っている。誤った分岐ターゲット予測が分岐予測構造に入ることにより、エントリは、いつまでも分岐ターゲットを正確に予測する可能性がないため、エントリを無駄にする。この条件は、分岐予測構造の汚染と呼ばれる。
【００１１】
分岐予測構造を強化することによって、後続するはずの分岐を正確に予測できるようになり、それによって処理の効率が高められる。具体的には、分岐ターゲットバッファ（ＢＴＢ）を利用して、動的な分岐予測をもたらすことができる。すなわち、一旦分岐ターゲットアドレスが決定されれば、ＢＴＢはフェッチパイプラインの早い段階に分岐を予測して、分岐のターゲットをフラッシュし、かつ再誘導することから結果生じるペナルティを最小限とする。一般に、ＢＴＢに命令アドレスが記録されない場合には、命令の実行は、分岐することなく、継続するものと予測される。予測されて実際に成立した（taken）分岐は、１サイクルあるいは、多くの場合に２サイクル以上のクロック遅延を有する場合がある。最終的にＢＴＢは、分岐予測の履歴を格納することができる。その後、命令フェッチの処理中に、ＢＴＢ内のエントリを用いて、命令アドレスが検査される。そのアドレスがＢＴＢ内にない場合には、命令実行は、分岐動作を行うことなく、次の命令に継続するものと予測される。
【００１２】
図１は、分岐予測を組み込んだコンピュータシステム５を示す。システム５は、１つ以上のプロセッサ１２iと、メモリサブシステム１６とを備える。また各プロセッサ１２iは、当業界においてよく知られているように、オンチップメモリコントローラ及び／又はキャッシュメモリ１７も備える。プロセッサ１２内の命令フェッチユニット（ＩＦＵ）１８は、当業界においてよく知られているパイプラインに応じてメモリサブシステム１６にアクセスすることができる、メモリコントローラ１７への１つ以上の命令に対する命令フェッチ要求を開始し、所定のパイプライン設計に応じて処理を制御する。分岐ターゲットバッファ（ＢＴＢ）１０は、命令フェッチアドレスを利用して、フェッチされた命令が分岐を含むか否かを予測する。分岐が成立するものと予測される場合には、ＩＦＵ １８は、プログラムの流れを分岐のターゲットにリダイレクトする。予測された分岐の意味（すなわち成立（taken）か、不成立（not taken）か）及び予測された分岐のターゲットを含む、成立した分岐についての情報は、分岐アドレス計算装置（ＢＡＣ）１４に対してパイプラインを下流に送出される。ＢＡＣ １４は、メモリコントローラ１７から戻される命令を復号化して、分岐の意味及び／又はターゲットアドレス情報を計算する。ＢＡＣ １４で計算された情報は、ＢＴＢ １０の情報よりも一層正確である。なぜなら、実際の命令データが、計算を実行するために利用されているためである。例えば、命令（例えば直接分岐）において符号化された分岐ターゲットは、ＢＡＣ １４によって正確に判定される。ＢＡＣ １４は、ＢＴＢ １０によって行われた予測に対して、計算された分岐情報を比較する。ＢＴＢ １０が分岐を予測することに失敗した場合、あるいはＢＴＢ １０が予測した意味及び／又はターゲットアドレスが不正確であると予測した場合には、ＢＡＣ １４は、ＩＦＵ １８に、計算されたＢＡＣ １４の情報にしたがってプログラムの流れの向きを直させる、すなわちリダイレクトさせる。
【００１３】
一実施形態では、ＢＡＣ １４は分岐導出テーブル（ＢＲＴ）１５を備える。
ＢＲＴ １５を利用して、分岐についての情報を格納する。この情報は、退避ステージを介して、パイプライン１９での処理中に利用され、その時点で、実際の分岐の成立／不成立の意味及び分岐ターゲットアドレスが確実にわかっている。
いくつかの分岐のための意味及び／又は分岐ターゲットアドレスが、退避前に確実にわかっていることに留意されたい。例えば、直接分岐のための分岐ターゲットアドレスは、ＢＡＣ １４によって確実に知られている。
【００１４】
別の実施形態では、分岐情報は、実行及び退避パイプライン１９に対する命令とともにパイプライン処理される。
【００１５】
多くの場合に、ＢＲＴ １５及び／又はパイプライン１９に格納された分岐情報を用いて、分岐の意味及びターゲット情報についてＢＴＢ １０を更新する。
一実施形態では、この情報は、実際の意味及び／又はターゲットアドレスがわかるまで、すなわち退避時まで格納されない場合もある。例として、実行及び退避パイプライン１９内の退避論理、リタイアロジックは、ＢＡＣ １４に送出され得る。この情報は、ＢＲＴ １５に格納された情報と組み合わせて、ＢＴＢ １０を更新するために利用される。
【００１６】
ＢＴＢ予測とＢＡＣ予測との間の重要な相違点は、ＢＴＢ予測が命令アドレスに基づいてのみ行われるのに対して、ＢＡＣ １４は、実際に命令データを検査し、ターゲットが命令自体において符号化されている直接分岐のための分岐ターゲットを判定するという点にある。
【００１７】
図１は、コンピュータシステム５の１つの実現可能な構成を示す。当業者には明らかであろうが、分岐予測テーブル汚染を低減できるようにする他の構成要素の構成も実現可能である。
【００１８】
図２は、動的な分岐予測のために利用される、ＢＴＢ １０のようなＢＴＢの一例を示す。多数のプロセッサを有するコンピュータシステムでは、プロセッサ１２のような各プロセッサが、ＢＴＢ １０を備えることができる。ＩＦＵ １８による命令のフェッチ中に、命令アドレス３０が生成される。ＢＴＢインデクスビット３２のような、複数のビットの一部が、デコーダ、復号化器４４を利用して、ＢＴＢ １０への索引付けに使用される。図示される例の場合、ＢＴＢは１２８エントリを有するので、ＢＴＢ １０内の各エントリを固有に索引付けするために、７個のインデクスビット３２が必要とされる。一旦エントリが選択されると、タグビット３１がエントリタグ２１と比較され、ＢＴＢ １０内のインデクスビット３２によって選択されたエントリが、現在の命令アドレス３０に関連するか否かが判定される。当業界では一般的であるように、タグビット３１の一部のみが、エントリ２０のエントリタグ２１に格納される場合がある。
【００１９】
当業界においてよく知られている、付加フィールド２４が、各ＢＴＢエントリに設けられる。例えば付加フィールドは、分岐予測の成立／不成立の履歴あるいは分岐タイプを含む場合がある。
【００２０】
ＢＴＢ １０内の分岐ターゲットフィールド２３は、分岐ターゲット４０の一部のみがＢＴＢに格納されていることを示す。１つ以上のエイリアスビット４１はＢＴＢ １０には格納されない。残りのビットは、ＢＴＢエントリ２０iを利用して分岐を予測する際に、現在の命令アドレス３０から暗示されるであろう。多くの場合に空間あるいはタイミングの制約のために選択される、部分的な分岐ターゲットのみを格納する結果、エイリアスビットが実際に分岐命令３１それ自体のアドレスと一致しない場合には、不正確に分岐を予測する可能性がある。
【００２１】
図３は、ＢＴＢ １０とともに利用される、簡略化された処理用パイプライン１０１を示す。パイプライン１０１は、主処理用パイプライン１１０と、分岐ターゲットパイプライン１２０と、分岐アドレスパイプライン１３０とを備える。パイプライン１１０、１２０、１３０内の処理は並行して、パラレルに行われる場合もある。主パイプライン１１０は、１つ以上の命令フェッチステージ１１２と、命令実行ステージ１１４と、退避ステージ１１６とを備える。図３に示されるように、主ステージ１１０には、多数の他のステージが含まれ得る。分岐ターゲットパイプライン１２０は、１つ以上の分岐ターゲットステージ１２２を備えることができ、そのステージでは、ＢＴＢ １０が、実際に成立した分岐、あるいは不成立した分岐を予測する。最後に、分岐アドレスパイプライン１３０は、１つ以上の分岐アドレスステージを備え、そのステージでは、分岐アドレスコンパレータ、分岐アドレス比較器１４によって、分岐アドレスが検査される。
【００２２】
上記のように、メモリ１６に記憶される命令アドレスは、３２ビットを含むことができる。しかしながら、ターゲット分岐のための命令アドレスの全３２ビットを記憶する代わりに、ＢＴＢ １０は、ターゲット分岐アドレスが現在の命令アドレスに近いという可能性があるという仮定のもとに、アドレスビットのサブセットのみを実装する場合もある。一実施形態では、分岐ターゲットアドレスのうちの２０ビットのみがＢＴＢ １０の分岐ターゲットフィールド２３に格納される。分岐ターゲットアドレス４１のうちの残りの１２ビットは、現在の命令のアドレスに基づいて暗示される。したがって予測される分岐が成立すると、分岐ターゲットアドレスの下位の２０ビットが、ＢＴＢ １０の分岐ターゲットフィールド２６に格納され、現在の命令アドレスの上位の１２ビットが分岐ターゲットアドレスの下位の２０ビットに予めペンド（prepend）される。一実施形態では、分岐ターゲットアドレスは、１Ｍバイトメモリブロック内にある、すなわち分岐ターゲット範囲内にあるものと仮定される。
【００２３】
ＢＴＢ １０のエントリが空きになると、正常なシーケンスを開始することができる。ＩＦＵ １８は、ＢＴＢ １０を介して読み出しを行うが、ＢＴＢ １０にエントリがないため、その処理はパイプラインの分岐アドレス計算装置（ＢＡＣ）ステージに継続する。ＢＡＣ １４は、分岐ターゲットのアドレスが現在の命令アドレスから１Ｍバイトより離れているか否かを判定する。この判定は、ＢＡＣ １４によって計算されたアドレスの上位のビットと、対応する、現在の命令、すなわち分岐命令の上位のビットとを比較することにより行われる。ＢＴＢ１０が分岐ためのエントリを有さず、それゆえ分岐を全く予測できなかったため、ＢＡＣ １４は、分岐のターゲット対する命令フェッチを再誘導する必要がある。退避ステージ１１６の後、分岐ターゲットアドレスは、ＢＴＢ １０に書き込まれる。しかしながら、ＢＴＢ １０に書き込まれたアドレスは２０ビットで打ち切られる。この誤差を検出するための機構が設けられなければ、これによって不要なフラッシング及び再誘導が生じる。具体的には、ＢＴＢ １０及びＢＡＣ １４は、分岐ターゲット命令に再び直面、遭遇する。しかしながら、この時点で、命令アドレスはＢＴＢ １０内にエントリを有する。ＢＴＢ １０は、ＢＴＢ １０に格納された部分的なターゲットアドレスビットと、現在のフェッチアドレスから暗示された（あるいはエイリアシング）ビットとを連結することにより、予測される分岐ターゲットを構成する。すなわち、現在の命令アドレスの残りの１２ビットは、分岐ターゲットアドレスの下位の２０ビットに予めペンドされる。その後プロセッサは、現在の命令アドレスの１Ｍバイト以内にあるが、不正確であるターゲットアドレスに再誘導する。ＢＡＣ １４は、不正確なアドレスを表示してパイプラインをフラッシュし、ＢＴＢエントリを無効にし、再び再誘導する。その後、その命令の処理は、パイプライン１１０を介して継続する。命令処理が退避ステージ１１６に到達すると、分岐ターゲット命令アドレスが割り当てられ、ＢＴＢ １０内に戻される。したがって、この命令の次の段階でも、フラッシュ及び再誘導が結果生じるであろう。
【００２４】
この問題を避けるために、ＢＡＣ １４は、ターゲットアドレスの上位の実装されていないビット（例えば上位の１２ビット又はエイリアシングビット）と、現在の命令アドレスの対応するビットとを比較する。エイリアシングビットが分岐命令のアドレスの対応するビットに一致する場合には、分岐ターゲットアドレスが現在の命令のアドレスと同じメモリブロック内にあるという仮定は正確であり、その予測は使用可能である。比較の結果が一致しない場合には、分岐ターゲット予測は不正確、又は誤っている。
【００２５】
エイリアシングビットを比較した結果は、ＢＲＴ １５（図１参照）に格納される。各結果又はエントリは、予測されたターゲット内のエイリアシングビットと分岐命令のアドレスが一致するか否かを示す比較ビットを含む。ＢＲＴ １５は、パイプライン１９内にあるが、退避されていない分岐を格納する。分岐が退避するとき、対応する分岐エントリがアクセスされ、比較ビットが検査される。分岐ターゲットアドレスがエイリアシングしていなかったことを、比較ビットが示す場合には、ＢＴＢ １０はその分岐情報を用いて更新される。比較ビットが一致を示さない場合には、ＢＴＢ １０は、その分岐情報を用いて更新されない。これは、余剰フラッシュ及び再誘導を生じることになる分岐ターゲットアドレスの記録処理を妨げる。また分岐ターゲットアドレスの次の比較も、あるビットのビット表明（bit assertion）を表明し、特定の命令アドレスに対するＢＴＢ １０内のエントリの更新を抑制する結果となる。したがって、誤って予測された分岐ターゲットアドレスに対して、多くても一回の再誘導しか必要とされない。
【００２６】
一実施形態では、比較が一致しないことを示す場合に、比較ビットが１に設定される場合がある。他の符号化機構を利用して、ＢＴＢ １０の更新を抑制する場合もある。
【００２７】
ＢＡＣ １４による比較の終了時に、比較ビットを設定するための代替的な実施形態として、比較ビットはその命令と共に設定される場合もある。この代替的な実施形態では、命令が退避するまで、比較ビットは、命令の残りの部分とともにパイプラインを下流に流れる。退避時に、エイリアシングビットが一致することを、比較ビットが示す場合には、そのエントリはＢＴＢ １０内に挿入され得る。
【００２８】
別の実施形態では、ＢＴＢ １０が退避前に更新される場合もある。上記の代替的な実施形態と同様に、エイリアシングビットの比較結果を利用して、そのエントリがＢＴＢ １０に割り当てられるべきか否かを判定する。
【００２９】
図４は、分岐予測テーブル汚染を低減するために用いられるプロセスを示す。プロセスは１００で開始する。ＢＴＢ １０は、分岐ターゲットアドレスを予測する（ブロック１１０）。命令がフェッチされ、さらに処理され、ＢＡＣ １４に送出される（ブロック１２０）。ＢＡＣ １４が、分岐ターゲットアドレスを計算し（ブロック１３０）、その計算された分岐ターゲットアドレスと予測された分岐ターゲットアドレスのエイリアシングビットを比較する（ブロック１４０）。エイリアシングビット比較の結果は、符号化され、例えばパイプライン１９又はＢＲＴ １５に格納される（ブロック１５０、１６０）。実行及び退避後（ブロック１７０）、格納された比較ビットが検査される（ブロック１８０）。比較ビットの符号化が、エイリアシングビットが一致したことを示す場合には、ＢＴＢ １０はその分岐情報を用いて更新される（ブロック１９０）。比較ビットの符号化が、エイリアシングビットが一致しないことを示す場合には、ＢＴＢの更新は抑制される（ブロック１９５）。ブロック２００で、プロセスは終了する。
【００３０】
ここで使用した用語及び説明は、例示するためにのみ述べられており、制限することを意図しない。全ての用語は、他に指示がなければ、添付の特許請求の範囲においてできるだけ幅広い意味で理解されるべきであり、特許請求の範囲によって画定されるような本発明の精神及び範囲内、及びその等価な内容において、多数の変形形態が実現可能であることは、当業者には理解されよう。
【００３１】
以下においては、本発明の種々の構成要件の組み合わせからなる例示的な実施態様を示す。
１．  分岐予測テーブル汚染を低減するための方法であって、
分岐予測構造（１２）を利用して分岐ターゲットアドレスを予測するステップ（１１０）と、
分岐を処理するステップ（１２０）と、
実際の分岐ターゲットアドレスを計算するステップ（１３０）と、
現在の命令アドレスのビットと、前記分岐予測構造に格納されていない前記実際の分岐ターゲットアドレスのビットとを比較するステップ（１４０）と、
前記比較の結果が一致する場合に、前記実際の分岐アドレスの一部を前記分岐予測構造に格納するステップ（１９０）と、
からなる方法。
【００３２】
２．  前記比較の結果が、比較ビットを設定することにより示される、１項に記載の方法。
【００３３】
３．  前記比較ビットが、分岐導出テーブル（１５）に設定されている、２項に記載の方法。
【００３４】
４．  前記比較が、前記分岐の退避後に終了する、１項に記載の方法。
【００３５】
５．  前記予測された分岐ターゲットアドレスが、アドレスの第１の部分と、該アドレスの第２の部分とに基づいており、さらに前記方法が、現在の命令のアドレスに基づいて前記第２の部分を暗示するステップを含む、１項に記載の方法。
【００３６】
６．  前記現在のアドレス及び前記予測された分岐ターゲットアドレスが、同じメモリ領域を占めるものと仮定される、５項に記載の方法。
【００３７】
７．  分岐予測テーブル汚染を低減するための装置であって、
分岐ターゲットを予測する分岐ターゲットバッファ（ＢＴＢ）（１０）と、
前記分岐ターゲットを計算する前記ＢＴＢに接続されている分岐アドレスコンパレータ（ＢＡＣ）（１４）とを備え、前記計算が、分岐ターゲットアドレスの実装されていないビットと、現在の命令アドレス内の対応するビットとが一致するか否か比較するステップを含み、一致する場合に、前記ＢＡＣが、前記ＢＴＢに書き込まれるべき前記分岐ターゲットアドレスの一部を割り当てることを特徴とする装置。
【００３８】
８．  前記ＢＡＣが分岐導出テーブル（１５）を備え、この分岐導出テーブルが、
分岐ターゲットアドレス情報と、
比較結果を示す比較ビットとを含む、７項に記載の装置。
【００３９】
９．  比較結果の一致が、前記分岐ターゲットアドレスの前記実装されたビットと、前記現在の命令の前記対応するビットとが同じメモリブロック内にあることを示す、７項に記載の装置。
【００４０】
１０．  前記比較が、分岐命令の退避後に終了する、７項に記載の装置。
【００４１】
【発明の効果】
本発明は、命令をフローさせるための分岐ターゲットアドレスを予測する分岐ターゲット構造（１２）に関する。スペースを保存するために、分岐ターゲットアドレスの一部のみが格納される。分岐ターゲットアドレスは、現在の命令アドレスの特定されない部分が分岐ターゲットアドレスの対応するビットに一致することを仮定して、再構成される。比較器（１４）は、現在のアドレスの特定されない部分が分岐ターゲットアドレスの対応するビットに一致するか否かを判定する。アドレスの特定されない部分が分岐命令アドレスの対応するビットに一致しない場合には、分岐ターゲット構造の更新が抑制される。一致する場合には、更新が許可される。
【図面の簡単な説明】
【図１】分岐ターゲットバッファを用いるコンピュータシステムのブロック図である。
【図２】分岐ターゲットバッファを示す図である。
【図３】図２の分岐ターゲットバッファとともに利用される処理用パイプラインを示す図である。
【図４】図１の分岐ターゲットバッファとともに実行される処理を示すフローチャートである。
【符号の説明】
１０  分岐ターゲットバッファ（ＢＴＢ）
１２  分岐予測構造
１４  分岐アドレスコンパレータ（ＢＡＣ）
１５  分岐導出テーブル
【図１】
0003840382.tif 000002
【図２】
0003840382.tif 000003
【図３】
0003840382.tif 000004
【図４】
0003840382.tif 000005