JPH09500989A - 分岐ターゲット・バッファにおける推論履歴 - Google Patents

Abstract

(57)【要約】 各分岐命令に対する推論履歴（２５）と実履歴（２２）を分岐ターゲット・バッファに維持する分岐予測機構。実分岐履歴（２２）は分岐命令の完全に解決されたオカレンスの分岐履歴を含んでいる。推論分岐履歴（２５）は実履歴（２２）ならびに分岐に対する最近の分岐予測の「履歴」を含んでいる。推論分岐履歴（２５）が何らかの最近の予測を含んでいる場合には、推論ビット（２４）がセットされる。推論ビット（２４）がセットされた場合、これは分岐に対する推論履歴（２５）が存在していることを示す。したがって、推論ビット（２４）がセットされた場合、推論履歴（２５）を使用して、分岐予測を行う。この分岐に対して誤予測が行われた場合、推論履歴（２５）が不正確な分岐履歴を含んでいるので、推論ビット（２４）がクリアされる。

Description

【発明の詳細な説明】 分岐ターゲット・バッファにおける推論履歴 発明の背景 １．発明の分野 本発明はマイクロプロセッサ用の分岐予測機構に関する。詳細にいえば、分岐 予測を行った場合に「推論履歴」を格納して、分岐履歴を小さいループ内の分岐 命令に直ちに利用できるようにする分岐予測機構に関する。 ２．背景の技術 初期のマイクロプロセッサは命令を一度に１つずつ処理していた。各命令は４ つの順次ステージ、すなわち命令取出し、命令復号、実行、および結果書戻しを 使用して処理されていた。このようなマイクロプロセッサ内では、異なる専用論 理ブロックがそれぞれ異なる処理ステージを行う。各論理ブロックは以前の論理 ブロックがすべて動作を完了するまで待機してから、その動作を開始する。 効率を改善するために、マイクロプロセッサの設計者は取出し、復号、実行、 および書戻しの各ステージの動作を重ね合わせ、マイクロプロセッサが数種類の 命令で同時に動作するようにした。動作時に、取出し、復号、実行、および書戻 しの各ステージは異なる命令を並行に処理する。各クロック時に、各処理ステー ジの結果が後続の処理ステージに渡される。取出し、復号、実行、および書戻し の各ステージを重ね合わせる技法を使用するマイクロプロセッサは、「パイプラ イン式」マイクロプロセッサと呼ばれている。 パイプライン・マイクロプロセッサが効率よく作動するために、パイプライン の先頭の命令取出しユニットがパイプラインに命令のストリームを与える。ただ し、命令ストリーム内の条件付き分岐命令は、条件が解決されるまで、パイプラ インの先頭にある命令取り出しユニットが適正な命令を取出すのを阻止する。パ イプラインを先に進むまで、条件が解決されないため、命令取り出しユニットは 適正な命令を取り出すことができないためである。 この問題を多少とも解消するため、多くのパイプライン・マイクロプロセッサ は分岐命令の結果を予測してから、分岐予測にしたがって以降の命令を取り出す 分岐予測機構を使用している。たとえば、ＹｅｈおよびＰａｔｔはきわめて正確 な２レベル分岐予測機構を導入している。（Ｔｓｅ Ｙｕ ＹｅｈおよびＹａｌ ｅ Ｎ． ＰａｔｔのＴｗｏ−Ｌｅｖｅｌ Ａｄａｐｔｉｖｅ Ｂｒａｎｃｈ Ｐｒｅｄｉｃｔｉｏｎ ， Ｔｈｅ ２４ｔｈ ＡＣＭ／ＩＥＥＥ Ｉｎｔｅｒｎ ａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ａｎｄ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｉ ｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ， Ｎｏｖｅｍｂｅｒ １９９１， ｐｐ． ５１ ― ６１参照。）分岐予測機構が分岐を誤って予測した場合、取り出され るべきではなかった命令は命令パイプラインから排除される。 ＹｅｈおよびＰａｔｔが開示した２レベル分岐予測機構などのほとんどの分岐 予測機構は分岐の結果履歴を動的に維持することによって動作する。分岐予測は この場合、記憶された分岐履歴に基づいている。 小さいループが深くパイプライン化されたプロセッサで実行された場合、同一 の分岐命令が命令パイプラインにいくつか同時に発生することがある。そのよう な場合には、以前の分岐は解決されない。したがって、以前の分岐に対する履歴 は分岐予測機構には利用されない。パイプラインの深いところにある分岐命令に 対する分岐履歴を、分岐命令の以降のオカレンス（実現地）に利用できないため 、後の分岐命令に対する分岐予測は古くなった履歴を使用して行われることとな る。したがって、パイプラインの深いプロセッサにおいて、分岐履歴に基づいて 予測を行う分岐予測機構は小さいループ内の分岐の予測を誤ることがしばしばあ る。 発明の概要 したがって、本発明の目的は、これも命令パイプラインにある分岐の「推論履 歴」に基づいて予測を行う分岐予測機構を提供することである。推論分岐履歴は 以前の分岐履歴、ならびに分岐に対する最近の分岐予測からなっている。 この目的およびその他の目的は、分岐ターゲット・バッファにおける各分岐命 令に対する推論履歴および実履歴を維持する本発明の分岐予測機構によって達成 される。実分岐履歴は発生した分岐命令の完全に解決されたオカレンスに対する 分岐履歴を含んでいる。推論分岐履歴は実履歴、ならびに分岐に対する最近の分 岐予測の「履歴」を含んでいる。推論分岐履歴が何らかの最近の分岐を含んでい る場合、推論ビットがセットされる。推論ビットがセットされると、これは分岐 に対する推論履歴があることを示す。したがって、推論ビットがセットされた場 合、推論履歴が分岐予測を行うために使用される。分岐に対して誤予測が行われ た場合、推論履歴が不正確な分岐履歴を含んでいるので、推論ビットはクリアさ れる。 図面の簡単な説明 本発明の目的、特徴および利点は、以下の詳細な説明に鑑み、当分野の技術者 には明らかとなろう。 第１図は、命令を処理するための深いパイプラインのブロック図である。 第２ａ図は、緊密なループを有する簡単な疑似アセンブリ言語プログラムの図 である。 第２ｂ図は、一度に１つの命令を取り出すが、推論履歴を使用しないシステム に対する第１図に示した深い命令パイプラインを通過する第２ａ図のプログラム における命令のトレースの図である。 第３図は、推論履歴を使用する分岐予測機構に対する分岐ターゲット・バッフ ァ項目のブロック図である。 第４図は、分岐予測を行ったときに分岐ターゲット・バッファの推論履歴フィ ールドを更新するのに必要なステップをリストした流れ図である。 第５図は、分岐がプロセッサによって完全に解決されたときに分岐ターゲット ・バッファの該当するフィールドを更新するのに必要なステップをリストした流 れ図である。 第６図は、分岐ターゲット・バッファの推論履歴フィールドに基づいて分岐予 測を行うのに必要なステップをリストした流れ図である。 第７図は、推論履歴に基づいて予測を行うシステムに対する第１図に示した深 い命令パイプラインを通過する第２ａ図のプログラムにおける命令のトレースの 図である。 第８図は本発明の技法を使用するコンピュータ・システムのブロック図である 。 表記法および術語 以下の詳細な説明は主として、コンピュータ・メモリ内のデータ・ビットの操 作の表示画像、アルゴリズム、および記号表示によって行われる。これらのアル ゴリズムによる記述および表示は当分野の技術者が自分たちの作業の内容を他の 技術者にもっとも効果的に伝えるために使用される手段である。 本明細書におけるアルゴリズムは一般に、希望する結果につながる自己矛盾の ない一連のステップであると理解される。これらのステップは物理量の物理的な 操作に必要なものである。通常、必ずしもそうとは限らないが、これらの量は記 憶、転送、組合せ、比較、選択、選別、修正、あるいは操作することのできる電 気的または磁気的な信号の形態をとる。場合により、主として一般的な用法の理 由から、これらの信号をビット、値、要素、記号、文字、画像、項、数値その他 と呼ぶのが便利なことが証明されている。しかしながら、これらおよび類似の用 語が該当する物理量に関連づけられるものであって、これらの量に適用される便 宜的なラベルにすぎないことを念頭に置いておくべきである。 本件において、動作とは操作員に関連して行われる機械の動作である。本発明 の動作を行うために有用な機械としては、汎用ディジタル・コンピュータその他 類似の装置がある。すべての場合に、コンピュータを作動させる方法の操作と、 コンピュテーションの方法そのものとの違いに留意すべきである。本発明はコン ピュータを操作する方法のステップと、電気的信号またはその他の物理的信号を 処理して、他の希望する物理信号を生成する方法のステップに関する。 本発明はこれらの操作を行う装置にも関する。この装置は必要な目的のために 特別に構成されたものであっても、コンピュータに格納されているコンピュータ ・プログラムによって選択的に活動化、または再構成される汎用コンピュータで あってもよい。本明細書で提示するアルゴリズムは本来、特定のコンピュータま たはその他の装置に関するものではない。詳細にいえば、各種の汎用コンピュー タを本発明で教示する技法にしたがったプログラムとともに使用することができ るが、必要な方法のステップを行うために専用の装置を構成することが便利なこ ともある。各種のこれらの装置に必要な構造は、以下の説明から明らかとなろう 。本発明の機能を遂行できる機械には、譲受人であるインテル・コーポレーショ ンならびにコンピュータ・システムのその他の製造業者が製造したものがある。 発明の詳細な説明 推論履歴に基づいて分岐予測を行う分岐予測機構を開示する。以下の説明にお いて、説明のために、本発明を完全に理解してもらうために特定の術語を使用す る。しかしながら、これらの個々の細部が本発明を実施するのに必要ないことが 、当分野の技術者には明らかであろう。その他の場合に、本発明を不必要に不明 確としないために、周知の回路および装置をブロック図の形で示す。 パイプラインの深いプロセッサにおける分岐予測 パイプラインの深いプロセッサにおいては、パイプライン・プロセッサの取出 し、復号および実行などの主要なステージをいくつかのサブステージに分割し、 各主要ステージがパイプライン化されるようにしている。たとえば、第１図はパ イプラインの深いプロセッサの一連のパイプライン・ステージを示す。第１図の 命令パイプラインには、１１のパイプライン・ステージがある。 第１図に示した命令パイプラインの先頭には、２つの命令取出しサブステージ が配置されている。（取出し１および取出し２。）これらの２つの命令取出しサ ブステージは命令パイプラインに対する新しい命令の連続的な取出しを担う。命 令ストリーム内の無条件分岐命令は、取出しサブステージによる順次命令の単純 な取出しを阻止する。さらに、命令ストリームの条件付き分岐命令は、取出しサ ブステージによる予測したパスに沿った命令の単純な取出しを阻止する。命令取 出しサブステージは、したがって、プログラムの進路を正確に知らずに、将来の 命令を取り出せるものでなければならない。 将来の命令を取り出すために、命令パイプラインの先頭の取出しサブステージ を、分岐予測機構によって実現する。分岐予測機構は命令ストリームのどこに分 岐命令があるかを予測し、かつこれらの分岐命令の結果を予測する。命令取出し ユニットは次いで、分岐予測機構によって予測されたとおりに命令のストリーム を取り出す。 ほとんどの分岐予測機構は分岐命令の以前のオカレンスの結果に基づいて、分 岐命令の結果を予測する。分岐命令が解決されるたびに、分岐予測機構は分岐の 結果を分岐履歴バッファに記憶する。分岐命令の次のオカレンスで、分岐予測機 構は収集した分岐履歴に基づいて分岐予測を行う。このような分岐予測機構によ って、極めて高い分岐予測速度が達成される。たとえば、ＹｅｈおよびＰａｔｔ の２レベル適応分岐予測機構は９７％超の精度の予測速度を達成する。（Ｔｓｅ Ｙｕ ＹｅｈおよびＹａｌｅ Ｎ． ＰａｔｔのＴｗｏ−Ｌｅｖｅｌ Ａｄａ ｐｔｉｖｅ Ｂｒａｎｃｈ Ｐｒｅｄｉｃｔｉｏｎ ， Ｔｈｅ ２４ｔｈ ＡＣ Ｍ／ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ａｎｄ Ｗ ｏｒｋｓｈｏｐ ｏｎ Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ， Ｎｏｖｅｍｂ ｅｒ １９９１， ｐ． ６０参照。） パイプラインの深いプロセッサは分岐予測プロセスを複雑とすることがある。 具体的にいえば、パイプラインの深いプロセッサにおいて、短いプログラム・ル ープの分岐命令の予測を、予測を行うのに分岐履歴を使用する分岐予測機構が誤 ることがしばしばある。この問題を第１図、第２ａ図および第２ｂ図を参照して 説明する。 第２ａ図を参照すると、疑似アセンブリ言語で書かれた短いプログラムのリス トが示されている。第２ａ図のプログラムはきわめて短いループからなっている 。プログラムの１行目は絶対値３を有する第１レジスタ（Ｒ１）をロードするロ ード命令からなっている。プログラムの２行目は第１レジスタ（Ｒ１）の値を第 ２レジスタ（Ｒ２）に加算するＡｄｄ命令を含んでいる。第１レジスタ（Ｒ１） は次いで、プログラムの３行目で減分される。プログラムの４行目で、ゼロ・フ ラ グがセットされていなければ、プログラムは２行目に戻って分岐する。それ故、 第１レジスタ（Ｒ１）が値０をまだ含んでいない場合には、プログラムは２行目 にループ・バックする。最後に、プログラムの５行目で、第２レジスタ（Ｒ２） の値がメモリに記憶される。 ３という絶対値が第１レジスタ（Ｒ１）にロードされるので、減分Ｒ１命令後 にロードされる「ｂｒａｎｃｈ ｉｆ ｎｏｔ ｚｅｒｏ」命令が２行目へ２回 ループ・バックする。ただし、３回目のループで、第１レジスタ（Ｒ１）はゼロ に減らされることになる。したがって、プログラムが３度目に「ｂｒａｎｃｈ ｉｆ ｎｏｔ ｚｅｒｏ」命令に到達すると、プログラムはプログラムの５行目 に進み、第２レジスタをメモリに格納する。それ故、４行目の分岐命令は分岐実 行（ｔａｋｅｎ）、分岐実行、分岐非実行（ｎｏｔ−ｔａｋｅｎ）（ＴＴＮ）と いう分岐履歴を作成する。このプログラムを再実行すると、第１レジスタ（Ｒ１ ）に常に絶対値３がロードされているので、この分岐はこのパターンを常に反復 し、これによってプログラムの４行目におかれた分岐命令に対して「ＴＴＮＴＴ ＮＴＴＮＴＴＮ ．．．」という分岐履歴を生成する。 正確な分岐予測機構はこの反復分岐パターンを識別し、反復分岐パターンを使 用して、将来の分岐予測を行うことができる。たとえば、ＹｅｈおよびＰａｔｔ が開示した２レベル適応分岐予測機構の理想的な実施形態は、このパターンを識 別し、分岐命令の将来のオカレンスの結果を常に正しく予測することになる。し かしながら、分岐予測機構が深いパイプラインを有する実際のプロセッサで実施 した場合、問題が発生することがある。 第２ｂ図は第２ａ図のプログラムの命令がプロセッサを通過する場合の、第１ 図の命令パイプラインに対する命令パイプライン・ステージの内容を示す。第２ ｂ図の命令の流れは命令が１つずつ取り出され、パイプラインの停止がないもの と想定している。さらに、命令の流れは分岐予測機構がプログラムの４行目の分 岐命令に対して「ＴＴＮＴＴＮＴＴＮ ．．．」（ただし、Ｔは分岐実行（ｔａ ｋｅｎ）を表し、Ｎは分岐非実行（ｎｏｔ−ｔａｋｅｎ）を表し、右端の文字は 分岐命令のもっとも最近のオカレンスの結果を表す）という分岐履歴を構築した ものと想定している。 第２ｂ図に示す最初のクロック・サイクル、クロック・サイクルＮにおいて、 ロード命令がまず取り出される。クロック・サイクルＮ＋１において、ロード命 令は取出しサブステージ２へ移動し、第１取出しサブステージはプログラムの２ 行目からＡｄｄ命令を取り出す。プロセッサはクロック・サイクルＮ＋３の終わ りまで、命令をメモリから命令パイプラインへ順次ロードする。 クロック・サイクルＮ＋３の終了時に、第１取出しサブステージは分岐予測を 行って、次の命令をロードしなければならない。この分岐に対する分岐履歴パタ ーンが「ＴＴＮＴＴＮＴＴＮ ．．．」を含んでいるので、取出しサブステージ は分岐が取り出されたことを予測する（正しく）。したがって、クロック・サイ クルＮ＋４において、命令取出しユニットはプログラムの２行目に戻り、Ａｄｄ 命令を取り出す。プロセッサは再度、クロック・サイクルＮ＋６が終わるまで、 命令をメモリから命令パイプラインへ順次取り出す。 クロック・サイクルＮ＋６の終了時に、第１取出しサブステージは分岐命令の 結果を順に予測して、以降の命令を取り出さなければならない。クロック・サイ クルＮ＋６の終了時に、分岐命令の最初のオカレンスが第４パイプステージ、復 号１に到達している。それ故、分岐命令の最初のオカレンスはまだ完全には解決 されていない。これは分岐命令が完全に解決されるまで、分岐履歴が更新されな いので、分岐履歴が依然「ＴＴＮＴＴＮＴＴＮ ．．．」を含んでいることを意 味する。古くなった履歴「ＴＴＮＴＴＮＴＴＮ ．．．」を使用すると、取出し サブステージは再度、分岐が行われると予測する（正しく）。分岐予測機構が実 際には、反復パターンの行われなかった分岐後に最初に行われた分岐を予測して いるので、これはまぐれ当たりといえる。したがって、クロック・サイクルＮ＋ ７において、命令取出しユニットは再度２行目に戻って、Ａｄｄ命令を取り出す 。今度も、クロック・サイクルＮ＋９が終わるまで、プロセッサは命令をメモリ から命令パイプラインへ取り出す。 クロック・サイクルＮ＋９の終了時に、第１取出しサブステージは再度、分岐 命令の結果を予測して、以降の命令を取り出さなければならない。クロック・サ イクルＮ＋９の終了時に、分岐命令の最初のオカレンスは第７のパイプステージ （スケジューリング）に到達しており、分岐命令の２番目のオカレンスは第４の パイプステージ（復号１）に到達している。それ故、クロック・サイクルＮ＋９ の終了時に、分岐命令の最初のオカレンスも、２番目のオカレンスも完全には解 決されていない。このことは分岐履歴が依然「ＴＴＮＴＴＮＴＴＮ ．．．」を 含んでいることを意味する。したがって、分岐予測機構は再度、分岐が実行され ると予測する。しかしながら、この予測が結局正しくないことになるので、ここ では運がなくなっていることとなる。クロック・サイクルＮ＋１０において、命 令取出しユニットは再度２行目に戻って、Ａｄｄ命令を取り出す。プロセッサが 誤予測を結局検出すると、Ａｄｄ命令および以降のすべての命令をパイプライン から除去することが必要となる。 上記の例で生じる問題は分岐履歴が十分な早さで更新されないほど、プログラ ムのループが小さいことである。したがって、分岐予測機構は反復分岐パターン と「同期する」ことができなくなる。具体的にいえば、分岐命令が完全に解決さ れていない段階で、以前の分岐が命令パイプラインにまだ存在しているので、以 前の分岐の結果を使用することができない。それ故、分岐命令の結果をより正確 に予測するためには、まだパイプラインにある分岐命令の以前のオカレンスの履 歴が直ちに利用できなければならない。しかしながら、分岐命令の結果が完全に は解決されていないのであるから、まだパイプラインの深いプロセッサの途中に ある分岐命令に対して、「実」分岐履歴をもたらすことは不可能である。 この問題を解決するために、本発明は行われる各分岐予測が正しいことを想定 することによって各分岐に対する「推論履歴」を格納する。分岐予測の精度が十 分高い場合には、この技法はパイプラインの深いプロセッサ内の小さいループに おける分岐に対する分岐予測精度を改選する。 推論履歴フィールドを備えた分岐ターゲット・バッファ 第３図は推論履歴を格納する分岐予測機構の分岐ターゲット・バッファの項目 を示す。第３図の分岐ターゲット・バッファ項目の最初の３つのフィールドは、 分岐予測機構によって使用される分岐命令についての情報を格納する。分岐ター ゲット・バッファ項目の最初のフィールドはタグ・アドレス・フィールド２１で ある。タグ・アドレス・フィールド２１は分岐命令のメモリ内の場所を識別する アドレスを格納する。実履歴フィールド２２はこの特定の分岐のすべての完全に 解決された オカレンスに対する分岐履歴を格納する。事前計算予測フィールド２ ３は実履歴フィールド２２に格納されている分岐履歴情報に基づいて、分岐の次 のオカレンスに対する分岐予測を格納する。第３図の事前計算予測フィールド２ ３は実分岐履歴フィールド２２に基づく実際の実行または非実行分岐予測である 。事前計算予測フィールド２３は実履歴フィールドが更新されるたびに計算され 、分岐予測を行うのに必要な時間を２サイクルから１サイクルに減らす。 第３図の分岐ターゲット・バッファ項目の次の３つのフィールドは、分岐ター ゲット・バッファの各分岐に対して予測履歴を維持し、使用するために必要な情 報を含んでいる。本発明の分岐予測機構がこの特定の分岐ターゲット・バッファ 項目を使用して分岐予測を行ったときに、推論ビット２４がセットされる。分岐 予測が行われると、分岐予測機構は推論履歴フィールド２５および事前計算予測 フィールド２３も更新する。推論履歴フィールド２５を更新して、分岐予測の結 果を含むようにする。事前計算推論予測２６は推論履歴フィールド２５に格納さ れている推論分岐履歴に基づいて分岐の次のオカレンスに対する分岐予測を格納 する。 第３図の分岐ターゲット・バッファ項目の他のフィールドは分岐ターゲット・ バッファで共通して使用される情報を格納する。分岐命令が「ｒｅｔｕｒｎ ｆ ｒｏｍ ｓｕｂｒｏｕｔｉｎｅ」命令である場合に、戻りビット・フィールド２ ７がセットされる。戻りビット・フィールド２７がセットされると、分岐予測機 構は戻りアドレスの予測に特化した戻りスタック・バッファ（ＲＳＢ）から値を 削除しなければならない。ターゲット・アドレス・フィールド２８は、分岐が行 われると分岐予測機構が予測した場合に、命令取出しユニットが命令を取り出す べきアドレスを格納する。 分岐ターゲット・バッファの推論履歴フィールドの更新 第４図は本発明の分岐ターゲット・バッファにおける推論履歴フィールドを更 新する方法を示す。推論履歴フィールドを更新するプロセスは、第４図のステッ プ１０１によって示されるような分岐の履歴に基づく分岐予測を分岐予測機構が 行ったときに開始される。分岐履歴に基づく任意のタイプの分岐予測機構を、本 発明で使用することができる。したがって、分岐予測機構の正確な細部を本明細 書では示さない。好ましい実施例において、Ｙｅｈおよびｐａｔｔの２レベル適 応分岐予測法の変形を使用する。ステップ１０２において、推論ビット２４の状 態を調べて、分岐命令に対する推論履歴があるかどうかを判定する。 推論ビット２４がセットされていない場合、これは推論履歴フィールド２５の 情報が古くなっているか、あるいはこれまでセットされたことがなかったことを 示す。推論ビット２４がセットされていない場合、方法はステップ１０３に移動 し、推論ビット２４をセットして、分岐ターゲット・バッファ項目が推論履歴を 含むようになることを示すようにする。次に、ステップ１０４において、実履歴 フィールド２２を推論履歴フィールド２５にコピーして、推論履歴に開始点を与 えるようにする。最後に、ステップ１０４において、事前計算予測２３を推論履 歴フィールド２５にシフトし、これによって「推論履歴」の最初のビットを与え るが、これは事前計算予測が結局間違っていたと判明する可能性のある予測にす ぎないからである。 ステップ１０２をもう一度参照すると、推論ビット２４がセットされている場 合、これは以前の分岐予測がこの分岐ターゲット・バッファ項目に対して行われ ており、推論履歴フィールド２５がこれらの以前の予測の履歴を含んでいること を示している。したがって、推論ビット２４がセットされている場合、更新プロ セスはステップ１０５へ移動し、事前計算推論予測ビット２６を推論履歴フィー ルド２５へシフトし、これによって「推論履歴」の他のビットを推論履歴フィー ルド２５に追加する。 推論履歴フィールド２５の更新後、推論履歴フィールド２５の新しい推論履歴 を使用して、事前計算推論予測ビット２６を再計算しなければならない。ステッ プ１０６において、システムは分岐が条件付き分岐であるか、無条件分岐である かを調べる。分岐が無条件である場合、ステップ１０８において事前計算推論予 測ビット２６がセットされる。これは、分岐が常に行われるからである。分岐が 無条件である場合、分岐予測機構は新たに更新された推論履歴フィールド２５に 基づいて、この分岐に対する予測を計算する。新しい分岐予測はステップ１０７ に示されているように、推論事前計算予測ビット・フィールド２６におかれる。 分岐ターゲット・バッファにおける実履歴フィールドの更新 分岐予測を行った後、分岐命令は命令パイプラインに沿って継続する。命令パ イプラインの端部の近くで、予測が行われた分岐命令が結局完全に解決される。 分岐命令が完全に解決されたら、分岐命令を実際の解決された分岐命令の結果に 照らして検証する。 分岐予測が正しかった場合、プロセッサは正常に継続する。しかしながら、分 岐予測が間違っていた場合、プロセッサは誤予測された分岐後にロードされた命 令パイプライン内のあらゆる命令をクリアしなければならない。これは命令取出 しユニットがこれらの命令をロードすべきではないからである。 さらに、分岐が誤予測された場合、推論履歴は分岐ターゲット・バッファが間 違っているものとする。したがって、この分岐に対する推論履歴を何らかの他の 分岐予測を行うのに使用してはならない。誤予測の検出後のそれ以上の予測を阻 止するために、分岐ターゲット・バッファ内の推論ビット２４を、第３図に示す ようにクリアする。 第５図は分岐命令が結局完全に解決されたときに実行されるステップを示す。 第５図のステップ３０１で、分岐命令が完全に解決され、これによって最終的な 分岐実行または非実行分岐の結果がもたらされる。次いで、ステップ３０２にお いて、解決された分岐の結果が実履歴フィールド２２にシフトされる。ステップ ３０３において、分岐のタイプを調べる。分岐が無条件分岐である場合、事前取 出し予測ビット２３がステップ３０５に示すようにセットされる。分岐が無条件 分岐である場合、分岐予測機構は実履歴フィールド２２にない実履歴を使用して 分岐予測を計算し、予測をステップ３０４に記載するように事前取出し予測ビッ ト２３におく。最後に、ステップ３０６で、この分岐に対して行われた分岐予測 が解決された分岐の実際の結果と比較される。分岐予測が正しい場合には、更新 は完了し、プロセッサは正常に継続する。しかしながら、予測が正しくない場合 には、推論ビット２４がクリアされ、推論履歴フィールド２５の不正推論履歴を 使用して、それ以上の予測を阻止する。 推論履歴フィールドに基づく予測の実行 第６図は推論履歴フィールドを備えた分岐ターゲット・バッファに基づく分岐 予測機構が、推論履歴情報を使用して予測を行う方法を示す。最初のステップ、 ステップ２０１は分岐ターゲット・バッファを探索して、分岐ターゲット・バッ ファ項目が存在しているかどうかを調べるものである。分岐ターゲット・バッフ ァ項目が存在しない場合には、分岐予測を行うために分岐ターゲット・バッファ を使用することができない。したがって、分岐予測機構はステップ２０３に述べ るように、静的な分岐予測を行わなければならない。 分岐ターゲット・バッファがヒットした場合には、分岐予測機構はステップ２ ０４で、該当する分岐ターゲット・バッファ項目内の戻りビット２７の状態を調 べる。戻りビット２７がセットされており、分岐が「ｒｅｔｕｒｎ ｆｒｏｍ ｓｕｂｒｏｕｔｉｎｅ ｉｎｓｔｒｕｃｔｉｏｎ」であることを示している場合 には、分岐予測機構はステップ２０５に述べるように戻りアドレスの予測に特化 している戻りスタック・バッファから予測を取得する。 戻りビット２７がセットされていない場合には、分岐予測機構はステップ２０ ６で分岐ターゲット・バッファ項目内の推論ビット２４の状態を調べる。この調 査は分岐予測機構が事前計算推論予測２６を使用すべきか、正規の事前計算予測 ２３を使用すべきかを判定する。 推論ビット２４がセットされている場合には、事前計算推論予測ビット２６を 使用して、ステップ２１０に示すように分岐予測を選択する。事前計算推論予測 ビット２６がセットされている場合には、分岐予測機構はステップ２１２に示す ようにターゲット・アドレスへのジャンプを予測し、セットされていない場合に は、分岐予測機構はステップ２１１で失敗を予測する。 推論ビット２４がセットされていない場合には、正規の推論予測ビット２３を 使用して、ステップ２０７に示すように分岐予測を選択する。推論予測ビット２ ３がセットされている場合には、分岐予測機構はステップ２０８に示すようにタ ーゲット・アドレスへのジャンプを予測し、セットされていない場合には、分岐 予測機構はステップ２０９で失敗を予測する。 分岐予測を行った後、命令取出しユニットは予測命令ストリームに沿って命令 を取り出す。分岐予測機構は新しい分岐予測を使用して、ステップ２１３で述べ るように推論履歴フィールドの更新も行う。 第７図は第２ａ図のプログラムを推論履歴を使用するプロセッサで作動させた ときの第１図の命令パイプラインに対する命令パイプライン・ステージの内容を 示す。第７図に示す命令の流れは命令が１つずつ取り出され、パイプラインの停 止がなく、分岐予測機構がプログラムの５行目の分岐命令に対して「ＴＴＮＴＴ ＮＴＴＮ ．．．」という分岐履歴を構築していると想定している。 最初の４つのクロック・サイクル（ＮないしＮ＋３）に対して、プロセッサは 第７図に示すように命令をパイプラインへ順次ロードする。ただし、クロック・ サイクルＮ＋３の終了時に、第１取出しサブステージは分岐予測を行って、次の 命令をロードしなければならない。分岐に対する分岐履歴パターンが「ＴＴＮＴ ＴＮＴＴＮ ．．．」を含んでいるので、取出しサブステージは分岐が実行され ると予測する（正しく）。このとき、分岐項目に対する推論ビットがセットされ 、「分岐実行」予測が推論履歴にシフトされる。それ故、推論履歴は「ＴＴＮＴ ＴＮＴＴＮ ．．．」を含むことになる。分岐予測機構が分岐が実行されると予 測したので、命令取出しユニットはクロック・サイクルＮ＋４でプログラムの２ 行目に戻り、Ａｄｄ命令を取り出す。プロセスは次いで、クロック・サイクルＮ ＋６の終わりまで、命令をメモリから命令パイプラインへ取り出す。 クロック・サイクルＮ＋６の終了時に、第１取出しサブステージは分岐命令の 結果を再度予測して、以降の命令を取り出さなければならない。クロック・サイ クルＮ＋６の終了時に、分岐命令の最初のオカレンスは第４のパイプステージ、 復号１、に到達している。それ故、分岐命令の最初のオカレンスはまだ完全に解 決されておらず、したがって、分岐履歴は更新されていない。しかしながら、推 論履歴が予測された分岐を使用して更新され、推論分岐履歴が「ＴＴＮＴＴＮＴ ＴＮＴ ．．．」を含むようになる。推論ビットがセットされているので、取出 しサブステージの分岐予測機構は「ＴＴＮＴＴＮＴＴＮＴ ．．．」という推論 履歴を使用して、分岐が実行されると予測する（正しく）。したがって、クロッ ク・サイクルＮ＋９において、命令取出しユニットは２行目に再度戻って、Ａｄ ｄ命令を取り出す。この場合、プロセッサはクロック・サイクルＮ＋９の終わり まで、命令をメモリから命令パイプラインへ順次取り出す。 クロック・サイクルＮ＋９の終了時に、第１取出しサブステージは分岐命令の 結果を再度予測して、以降の命令を取り出さなければならない。クロック・サイ クルＮ＋９の終了時に、分岐命令の最初のオカレンスは第７のパイプステージ（ スケジューリング）に到達しており、分岐命令の第２のオカレンスは第４のパイ プステージ（復号１）に到達している。それ故、クロック・サイクルＮ＋９の終 了時に、分岐命令の最初のオカレンスも、第２のオカレンスも完全には解決され ていない。このことは分岐履歴が依然「ＴＴＮＴＴＮＴＴＮ ．．．」を含んで いることを意味する。しかしながら、推論分岐履歴は「ＴＴＮＴＴＮＴＴＮＴＴ ．．．」を含んでいる。推論ビットがセットされているので、分岐予測機構は 分岐を実行するべきではないと予測する（正しく）。したがって、クロック・サ イクルＮ＋１０において、命令取出しユニットは分岐命令後に、Ｓｔｏｒｅ命令 を取り出す。第７図の命令トレースでわかるように、推論履歴を使用する本発明 の分岐予測機構は緊密なループの分岐の結果を正しく予測する。 第８図は典型的なコンピュータ・システムで使用した場合の本発明を示す。本 発明はプロセッサ内に配置された分岐予測装置を含んでいる。分岐予測装置を使 用して、キャッシュ・メモリまたはメイン・メモリからプロセッサに対して適正 な命令を取り出す。 推論履歴を格納している分岐ターゲット・バッファを備えた分岐予測機構を、 以上で説明した。推論履歴はパイプラインが深いプロセッサで実行される小さい ループに対する分岐予測の精度を改善する。本発明の範囲から逸脱することなく 本発明の材料および構成に対して、当分野の通常の技量を有する技術者が変更お よび改変を行えることを意図している。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ， ＣＡ，ＣＨ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，Ｇ Ｂ，ＧＥ，ＨＵ，ＪＰ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＮ，ＭＷ，ＮＬ，ＮＯ， ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＩ，Ｓ Ｋ，ＴＪ，ＴＴ，ＵＡ，ＵＺ，ＶＮ (72)発明者 グルー，アンドリュー・エフ アメリカ合衆国 97124 オレゴン州・ヒ ルズボロ・ノースイースト キャサリン・ 825 (72)発明者 ナタラジャン，スブラマニアン アメリカ合衆国 97229 オレゴン州・ポ ートランド・ノースウエスト 143アール ディ アヴェニュ・ナンバー ジイー36・ 1865

Claims (1)

1. 【特許請求の範囲】 １．メモリに結合されたコンピュータ・プロセッサにおける、プロセッサ命令の ストリームを予測して取り出すための分岐予測装置において、 各々がプロセッサ命令の前記ストリーム内の分岐命令と関連づけられているＮ 個の分岐予測項目からなる分岐ターゲット・バッファを備えており、前記Ｎ個の 分岐予測項目の各々が 前記の関連分岐命令の最後のＫ個のオカレンスの解決された分岐の最後の結果 を格納する実分岐履歴フィールドと、 前記の関連分岐命令に対して予測が行われたときにセットされる推論ビットと 、 前記の関連分岐命令の解決された分岐の最後の結果と、前記の関連分岐命令の 最近のオカレンスの分岐予測を含んでいる推論分岐履歴のＫ個のビットを格納す る推論分岐履歴フィールドと、 前記の関連分岐命令が実行されたときに前記の関連分岐命令がどこへジャンプ するのかを識別するターゲット・アドレス・タグを含んでいるターゲット・アド レス・フィールドと、 前記推論ビットがクリアされた場合に前記実分岐履歴を使用して、分岐予測を 行い、それ以外の場合には、前記推論ビットがセットされた場合に前記推論分岐 履歴を使用して分岐予測を行う分岐予測機構と を有する分岐予測装置。 ２．前記の関連分岐命令に対して誤予測がなされたときに、分岐予測項目の前記 推論ビットがクリアされることを特徴とする、請求の範囲第１項に記載の分岐予 測装置。 ３．前記の関連分岐命令に対して予測がなされたときに、分岐予測項目の前記推 論分岐履歴フィールドが更新されることを特徴とする、請求の範囲第２項に記載 の分岐予測装置。 ４．前記分岐ターゲット・バッファの各分岐予測項目が 実分岐履歴フィールドに基づく分岐予測からなる事前計算分岐予測と、 前記推論分岐履歴フィールドに基づく分岐予測からなる事前計算推論分岐予測 と をさらに含んでいることを特徴とする。請求の範囲第３項に記載の分岐予測装 置。 ５．前記推論ビットがクリアされた場合に、前記事前計算分岐予測を使用して、 前記推論分岐履歴フィールドが更新され、それ以外の場合には、前記推論ビット がセットされた場合に、前記事前計算推論分岐予測を使用して、前記推論分岐履 歴フィールドが更新されることを特徴とする、請求の範囲第４項に記載の分岐予 測装置。 ６．前記の関連分岐命令が完全に解決されたときに、前記分岐予測項目の前記実 分岐履歴フィールドが実際の分岐結果によって更新されることを特徴とする、請 求の範囲第５項に記載の分岐予測装置。 ７．前記分岐予測機構が２レベル適応分岐予測機構の変形からなることを特徴と する、請求の範囲第６項に記載の分岐予測装置。 ８．前記分岐ターゲット・バッファの各分岐予測項目がさらに戻りビットを含ん でおり、該戻りビットがセットされた場合に、前記分岐予測装置が戻りスタック ・バッファからの予測を使用することを特徴とする、請求の範囲第７項に記載の 分岐予測装置。 ９．前記分岐予測装置が静的分岐予測機構をさらに含んでおり、前記分岐予測装 置に適当なターゲット・バッファ項目が見つからない場合に、前記静的分岐予測 機構を使用して、分岐予測を行うようになっていることを特徴とする、請求の範 囲第８項に記載の分岐予測装置。 １０．前記分岐予測装置が深い命令パイプラインを備えたプロセッサで実現され ることを特徴とする、請求の範囲第９項に記載の分岐予測装置。 １１．メモリに結合されたコンピュータ・プロセッサにおける、プロセッサ命令 のストリームを予測して取り出すための分岐予測装置において、 各々がプロセッサ命令の前記ストリーム内の分岐命令と関連づけられているＮ 個の分岐予測項目からなる分岐ターゲット・バッファ手段であって、前記Ｎ個の 分岐予測項目の各々が 前記の関連分岐命令の最後のＫ個のオカレンスの解決された分岐の最後 の結果を格納する実分岐履歴手段と、 前記の関連分岐命令に対して予測が行われたときにセットされる推論ビ ット手段と、 前記の関連分岐命令の解決された分岐の最後の結果と、前記の関連分岐 命令の最近のオカレンスの分岐予測を含んでいる推論分岐履歴のＫ個のビットを 格納する推論分岐履歴手段と、 前記の関連分岐命令が実行されたときに前記の関連分岐命令がどこへジ ャンプするのかを識別するターゲット・アドレス手段と、 を有する分岐ターゲット・バッファ手段、及び 前記推論ビットがクリアされた場合に前記実分岐履歴手段を使用して、分岐予 測を行い、それ以外の場合には、前記推論ビットがセットされた場合に前記推論 分岐履歴手段を使用して分岐予測を行う分岐予測手段 を有する分岐予測装置。 １２．前記の関連分岐命令に対して誤予測がなされたときに、分岐予測項目の前 記推論ビット手段がクリアされることを特徴とする、請求の範囲第１１項に記載 の分岐予測装置。 １３．前記の関連分岐命令に対して予測がなされたときに、分岐予測項目の前記 推論分岐履歴手段が更新されることを特徴とする、請求の範囲第１２項に記載の 分岐予測装置。 １４．前記分岐ターゲット・バッファ手段の各分岐予測項目が 実分岐履歴手段に基づく分岐予測からなる事前計算分岐予測手段と、 前記推論分岐履歴手段に基づく分岐予測からなる事前計算推論分岐予測手段と をさらに含んでいることを特徴とする。請求の範囲第１３項に記載の分岐予測 装置。 １５．前記推論ビット手段がクリアされた場合に、前記事前計算分岐予測手段を 使用して、前記推論分岐履歴手段が更新され、それ以外の場合には、前記推論ビ ット手段がセットされた場合に、前記事前計算推論分岐予測手段を使用して、前 記推論分岐履歴手段が更新されることを特徴とする、請求の範囲第１４項に記載 の分岐予測装置。 １６．前記の関連分岐命令が完全に解決されたときに、前記分岐予測項目の前記 実分岐履歴手段が実際の分岐結果によって更新されることを特徴とする、請求の 範囲第１５項に記載の分岐予測装置。 １７．前記分岐予測手段が２レベル適応分岐予測機構の変形からなることを特徴 とする、請求の範囲第１６項に記載の分岐予測装置。 １８．前記分岐ターゲット・バッファの各分岐予測項目がさらに戻りビット手段 を含んでおり、該戻りビット手段がセットされた場合に、前記分岐予測装置が戻 りスタック・バッファからの予測を使用することを特徴とする、請求の範囲第１ ７項に記載の分岐予測装置。 １９．前記分岐予測装置が静的分岐予測手段をさらに含んでおり、前記分岐予測 装置に適当なターゲット・バッファ項目が見つからない場合に、前記静的分岐予 測手段を使用して、分岐予測を行うようになっていることを特徴とする、請求の 範囲第１８項に記載の分岐予測装置。 ２０．前記分岐予測装置が深い命令パイプラインを備えたプロセッサで実現され ることを特徴とする、請求の範囲第１９項に記載の分岐予測装置。 ２１．システム・バス、 該システム・バスに結合されたメイン・メモリ、 プロセッサ命令のストリームを予測して取り出すための分岐ターゲット・バッ ファを有するコンピュータ・プロセッサであって、該分岐ターゲット・バッファ が各々がプロセッサ命令の前記ストリーム内の分岐命令と関連づけられているＮ 個の分岐予測項目からなっており、前記Ｎ個の分岐予測項目の各々が 前記の関連分岐命令の最後のＫ個のオカレンスの解決された分岐の最 後の結果を格納する実分岐履歴フィールドと、 前記の関連分岐命令に対して予測が行われたときにセットされる推論 ビットと、 前記の関連分岐命令の解決された分岐の最後の結果と、前記の関連分 岐命令の最近のオカレンスの分岐予測を含んでいる推論分岐履歴のＫ個のビット を格納する推論分岐履歴フィールドと、 前記の関連分岐命令が実行されたときに前記の関連分岐命令がどこへ ジャンプするのかを識別するターゲット・アドレス・タグを含んでいるターゲッ ト・アドレスと、 を有するコンピュータ・プロセッサ、及び 前記推論ビットがクリアされた場合に前記実分岐履歴フィールドを使用して、 分岐予測を行い、それ以外の場合には、前記推論ビットがセットされた場合に前 記推論分岐履歴フィールドを使用して分岐予測を行う分岐予測機構 を有するコンピュータ・システム。 ２２．前記の関連分岐命令に対して誤予測がなされたときに、分岐予測項目の前 記推論ビットが更新されることを特徴とする、請求の範囲第２１項に記載のコン ピュータ・システム。 ２３．前記の関連分岐命令に対して予測がなされたときに、分岐予測項目の前記 推論分岐履歴フィールドがクリアされることを特徴とする、請求の範囲第２２項 に記載のコンピュータ・システム。 ２４．前記分岐ターゲット・バッファの各分岐予測項目が 実分岐履歴フィールドに基づく分岐予測からなる事前計算分岐予測と、 前記推論分岐履歴フィールドに基づく分岐予測からなる事前計算推論分岐予測 と をさらに含んでいることを特徴とする。請求の範囲第２３項に記載のコンピュ ータ・システム。 ２５．前記推論ビットがクリアされた場合に、前記事前計算分岐予測を使用して 、前記推論分岐履歴フィールドが更新され、それ以外の場合には、前記推論ビッ トがセットされた場合に、前記事前計算推論分岐予測を使用して、前記推論分岐 履歴フィールドが更新されることを特徴とする、請求の範囲第２４項に記載のコ ンピュータ・システム。 ２６．前記の関連分岐命令が完全に解決されたときに、前記分岐予測項目の前記 実分岐履歴フィールドが実際の分岐結果によって更新されることを特徴とする、 請求の範囲第２５項に記載のコンピュータ・システム。 ２７．前記分岐予測機構が２レベル適応分岐予測機構の変形からなることを特徴 とする、請求の範囲第２６項に記載のコンピュータ・システム。 ２８．前記分岐ターゲット・バッファの各分岐予測項目がさらに戻りビットを含 んでおり、該戻りビットがセットされた場合に、前記プロセッサが戻りスタック ・バッファからの予測を使用することを特徴とする、請求の範囲第２７項に記載 のコンピュータ・システム。 ２９．前記分岐予測装置が静的分岐予測機構をさらに含んでおり、前記プロセッ サに適当なターゲット・バッファ項目が見つからない場合に、前記静的分岐予測 機構を使用して、分岐予測を行うようになっていることを特徴とする、請求の範 囲第２８項に記載のコンピュータ・システム。 ３０．前記プロセッサが深い命令パイプラインを備えたプロセッサで実現される ことを特徴とする、請求の範囲第２９項に記載のコンピュータ・システム。 ３１．システム・バス、 該システム・バスに結合されたメイン・メモリ、 プロセッサ命令のストリームを予測して取り出すための分岐ターゲット・バッ ファ手段を有するコンピュータ・プロセッサであって、該分岐ターゲット・バッ ファ手段が各々がプロセッサ命令の前記ストリーム内の分岐命令と関連づけられ ているＮ個の分岐予測項目からなっており、前記Ｎ個の分岐予測項目の各々が 前記の関連分岐命令の最後のＫ個のオカレンスの解決された分岐の最後 の結果を格納する実分岐履歴手段と、 前記の関連分岐命令に対して予測が行われたときにセットされる推論ビ ット手段と、 前記の関連分岐命令の解決された分岐の最後の結果と、前記の関連分岐 命令の最近のオカレンスの分岐予測を含んでいる推論分岐履歴のＫ個のビットを 格納する推論分岐履歴手段と、 前記の関連分岐命令が実行されたときに前記の関連分岐命令がどこへジ ャンプするのかを識別するターゲット・アドレス手段と、 を有するコンピュータ・プロセッサ、及び 前記推論ビットがクリアされた場合に前記実分岐履歴手段を使用して、分岐予 測を行い、それ以外の場合には、前記推論ビットがセットされた場合に前記推論 分岐履歴手段を使用して分岐予測を行う前記プロセッサ内の分岐予測手段 を有するコンピュータ・システム。 ３２．前記の関連分岐命令に対して誤予測がなされたときに、分岐予測項目の前 記推論ビット手段がクリアされることを特徴とする、請求の範囲第３１項に記載 のコンピュータ・システム。 ３３．前記の関連分岐命令に対して予測がなされたときに、分岐予測項目の前記 推論分岐履歴手段が更新されることを特徴とする、請求の範囲第３２項に記載の コンピュータ・システム。 ３４．前記分岐ターゲット・バッファ手段の各分岐予測項目が 実分岐履歴手段に基づく分岐予測からなる事前計算分岐予測手段と、 前記推論分岐履歴手段に基づく分岐予測からなる事前計算推論分岐予測手段と をさらに含んでいることを特徴とする、請求の範囲第３３項に記載のコンピュ ータ・システム。 ３５．前記推論ビット手段がクリアされた場合に、前記事前計算分岐予測手段を 使用して、前記推論分岐履歴手段が更新され、それ以外の場合には、前記推論ビ ット手段がセットされた場合に、前記事前計算推論分岐予測手段を使用して、前 記推論分岐履歴手段が更新されることを特徴とする、請求の範囲第３４項に記載 のコンピュータ・システム。 ３６．前記の関連分岐命令が完全に解決されたときに、前記分岐予測項目の前記 実分岐履歴手段が実際の分岐結果によって更新されることを特徴とする、請求の 範囲第３５項に記載のコンピュータ・システム。 ３７．前記分岐予測手段が２レベル適応分岐予測機構の変形からなることを特徴 とする、請求の範囲第３６項に記載のコンピュータ・システム。 ３８．前記分岐ターゲット・バッファの各分岐予測項目がさらに戻りビット手段 を含んでおり、該戻りビット手段がセットされた場合に、前記分岐予測装置が戻 りスタック・バッファからの予測を使用することを特徴とする、請求の範囲第３ ７項に記載のコンピュータ・システム。 ３９．前記分岐予測装置が静的分岐予測手段をさらに含んでおり、前記分岐予測 装置に適当なターゲット・バッファ項目が見つからない場合に、前記静的分岐予 測手段を使用して、分岐予測を行うようになっていることを特徴とする、請求の 範囲第３８項に記載のコンピュータ・システム。 ４０．前記分岐予測装置が深い命令パイプラインを備えたプロセッサで実現され ることを特徴とする、請求の範囲第３９項に記載のコンピュータ・システム。 ４１．メモリに結合されたコンピュータ・プロセッサでのプロセッサ命令のスト リームを予測して取り出すための方法において、 各々がプロセッサ命令の前記ストリーム内の分岐命令と関連づけられているＮ 個の分岐予測項目からなる分岐ターゲット・バッファを設けるステップと、 前記の関連分岐命令のＫ個の最近のオカレンスの完全に解決された分岐の結果 を含んでいる、各分岐予測項目内の実分岐履歴を分岐ターゲット・バッファに格 納するステップと、 前記の関連分岐命令のＫビットの解決された分岐の結果と前記の関連分岐命令 の最近のオカレンスの分岐予測を含んでいる、各分岐予測項目内の推論分岐履歴 を分岐ターゲット・バッファに格納するステップと、 各分岐予測項目内の推論ビットを分岐ターゲット・バッファに格納するステッ プと、 前記の関連分岐命令に対して分岐予測が行われているときに、前記推論ビット を格納するステップと、 前記の関連分岐命令に対して分岐予測が行われたときに、前記推論ビットを設 定するステップと、 前記推論ビットがクリアされたときに前記実分岐履歴を使用して分岐命令の結 果を予測し、それ以外の場合には、前記推論ビットがセットされたときに前記推 論分岐履歴を使用して分岐命令の結果を予測するステップと を有するプロセッサ命令のストリームを予測する方法。 ４２．前記方法が前記の関連分岐命令に対する分岐予測が不正であるときに前記 推論ビットをクリアするステップをさらに含んでいることを特徴とする、請求の 範囲第４１項に記載のプロセッサ命令のストリームを予測する方法。