JPH1040104A

JPH1040104A - 分岐命令の結果予測装置及び方法

Info

Publication number: JPH1040104A
Application number: JP9109719A
Authority: JP
Inventors: Ekanadamu Katsutamuri; カッタムリ・エカナダム; N Rektoschafen Rudolf; ルドルフ・エヌ・レクトシャフェン
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1996-05-01
Filing date: 1997-04-25
Publication date: 1998-02-13
Also published as: TW312775B; KR970076253A; US5822577A

Abstract

(57)【要約】【課題】１又は複数の分岐命令に関連するコンテキス
ト指向予測子を記録するヒストリ・テーブルを用いて分
岐結果を予測する装置及び方法を提供する。【解決手段】コンテキスト指向予測子は、ヒストリ・
テーブルの各エントリ内の分岐予測子ベクトルを統合す
ることにより導出される。このベクトルは、ｎの各値に
ついて２個の予測子のセットからなる（ｎは任意に設定
され、好適には実施態様により固定される）。プロセッ
サのプリフェッチ動作によりヒストリ・テーブルがアク
セスされると、先祖分岐と称される所与の分岐について
の予測子のベクトルがヒストリ・テーブルから取り出さ
れ記憶される。ｎ回の取り出しの後、最後のｎ個の分岐
の動作ヒストリを用いて、次に現れる分岐のｎ番目の先
祖に関連する予測子ベクトルからの予測子へアクセスす
る。この予測子は、その先祖分岐のｎ番目の子孫分岐を
予測するために用いられる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ処理システ
ムに関し、特に、データ処理システムにより実行される
分岐命令の予測に関する。

【０００２】図１は、プロセッサのパイプラインを構成
する主要な構成要素を示す。これらの構成要素は、命令
フェッチ（段階Ｉ）、命令デコード及びアドレス発生
（段階II）、ディスパッチ（段階III）、命令実行（段
階IV）、並びに完了（段階Ｖ）である。各命令がパイプ
ラインに入ると、理想的には各パイプライン段階におい
て１サイクルを費やす。従って、理想的には、各命令が
このパイプラインを通るために５サイクルを要する。し
かしながら、仮にこのパイプラインを満杯状態とするこ
とが可能であって、プロセッサの各構成要素（パイプラ
イン段階）がそれぞれ異なるパイプライン段階にある別
の命令に関して作業するような活動状態とすることが可
能な場合、１サイクル毎に１つの命令を完了することが
できる。

【０００３】上記のように、パイプライン・プロセッサ
は、現在の命令の実行が終わる前に次の命令を実行パイ
プラインへとフェッチしなければならない。現在の命令
が条件分岐命令である場合、プロセッサは、その分岐が
選択されると仮定してその分岐の目標アドレスからフェ
ッチするか、又は、その分岐が選択されないと仮定して
次の順序通りのアドレスからフェッチするかを決定しな
ければならない。誤って推論されると、パイプラインが
再び有効な命令で満たされるまでパイプラインが停止す
ることとなる。この遅延は、「分岐ペナルティ」と称さ
れる。幾つかのシステムでは、ヒストリ(活動記録)・テ
ーブルを用いることにより条件分岐命令に関する分岐ペ
ナルティを低減することが試みられている。

【０００４】米国特許第３５５９１８３号では、分岐ヒ
ストリ・テーブル(ＢＨＴ)を用いる命令フェッチ機構が
記載されている。これは、個々に検討したところほとん
どの分岐が首尾一貫して選択されるか又は選択されない
かのいずれかであり、かつ選択される場合は首尾一貫し
た目標アドレスを有することとなる、という観察結果に
基づいている。この手法においては、選択された分岐の
テーブルが構築される。このテーブルの各エントリは、
選択された分岐のアドレス及びそれに続くその分岐の目
標アドレスから構成される。このテーブルは、ハードウ
ェア構成であるので所定のサイズを有し、通常１０２４
乃至４０９６個のエントリをもつ。エントリは、選択さ
れる分岐に遭遇したとき、それらの分岐についてのみ作
成される。テーブルが満杯となったとき、新たなエント
リを追加するために古いエントリを置換する必要があ
る。これは、キャッシュにおけると同様のＬＲＵ(Least
Recently Used)アルゴリズムにより実現することがで
きる。

【０００５】原則的には、プロセッサの実行パイプライ
ン内の各分岐命令はそのアドレスを用いてテーブルを参
照され、そして見出された場合には、その目標アドレス
がフェッチされてそのパイプラインへロードされる次の
命令となる。もしその分岐がテーブル内で見出されなか
った場合には、選択されないと推定する。その分岐命令
の実行が進行すると、それに従ってテーブルが更新され
る。仮に、選択されると予測された分岐が選択されなか
った場合は、その関連するテーブルのエントリは削除さ
れる。仮に、選択されないと予測された分岐が選択され
た場合は、その分岐について新たなエントリが作成され
る。予測された目標アドレスが誤っている場合は、修正
されたアドレスが入力される。

【０００６】米国特許第４４７７８７２号では、デコー
ド・ヒストリ・テーブル(ＤＨＴ)を用いたデコード時間
予測機構が記載されている。ＤＨＴは、エントリからな
るテーブルであり、予測される分岐命令のアドレスを構
成するビットに対するハッシュ変換や切捨て変換等の変
換に基づいてエントリがアクセスされる。エントリ自体
は、単一ビットからなる。このビットは、対応する分岐
命令が実行された最後のときにその分岐命令が選択され
た場合にセットされ、そうでない場合はセットされな
い。従って、通常ＤＨＴは、ＢＨＴのような各分岐命令
に対応する固有のエントリを含まない。これによりＤＨ
Ｔは、ＢＨＴよりも機能は劣ることになるがそのサイズ
を小さくすることができる。

【０００７】条件分岐命令の結果をより良好に予測する
ために、ＢＨＴ／ＤＨＴのエントリへ更なる情報（すな
わち関連する更なる情報）を追加する他のシステムも提
示されている。

【０００８】J. Smithによる「A Study of Branch Pred
iction Strategies（分岐予測方式の研究）」(24th Int
ernational Symposium on Computer Architecture, May
1981, pp. 135-148)では、所与の分岐命令の結果を予
測するために２個のヒストリ・ビットを用いることを提
示する。この方法においては、２個のビットを飽和カウ
ンタとみなすことができ、分岐命令が選択されたと解明
されたときに増分され、そして分岐命令が選択されなか
ったと解明されたときに減分される。

【０００９】Yeh及びPrattによる「A Comparison of Dy
namic Branch Predictors that useTwo Levels of Bran
ch History（２レベルの分岐ヒストリを用いる動的分岐
予測の対比）」(Conference Proceedings Annual Sympo
sium on Computer Archtecture, 1993, pp. 257-266、I
EEE Computer Society Presss刊行)では、所与の分岐命
令の結果を予測するために２つの記憶レベルを用いる３
つの方式が記載されている。第１の記憶レベルは、１又
は複数のエントリを保持し、各々が最後のＫ個の分岐の
状態（選択／非選択）を表す。第２の記憶レベルは、パ
ターン・テーブルと称され、複数の２ビット・エントリ
を含む。１つのエントリ（又はエントリ群）は、第１の
記憶レベル内の対応するエントリによりエンコードされ
た状態に対応する。パターン・テーブルの各エントリの
２ビットは、第１の記憶レベル内の対応するエントリに
より特定の状態がエンコードされるときに発生した先行
する繰返しの結果を追跡する。

【００１０】第１の方式（グローバル・ヒストリ方式）
では、第１の記憶レベルが、グローバル分岐ヒストリ・
レジスタと称され、遭遇した最後のＫ個の分岐の状態を
記憶する。第２の方式（パー・アドレス・ヒストリ方
式）では、第１の記憶レベルが、パー・アドレス分岐ヒ
ストリ・テーブルと称され、複数のエントリを記憶す
る。そして、各エントリが静的分岐命令アドレスにより
索引付けされ、その静的分岐命令アドレス索引により識
別された特定の分岐命令の最後のＫ個の発生状態をエン
コードする。第３の方式（パー・セット・ヒストリ方
式）では、分岐命令が複数のセットへと区分けされる。
所与の分岐のセット属性は、分岐命令コード、コンパイ
ラにより割当てられた分岐クラス、又は分岐アドレスに
より決定することができる。第３の方式では、第１の記
憶レベルが、パー・セット分岐ヒストリ・テーブルと称
され、複数のエントリを記憶する。各エントリは、セッ
ト属性により索引付けされ、そしてそのセット属性索引
により識別された特定のセット内の最後のＫ個の分岐命
令の状態をエンコードする。

【００１１】３つの方式の各々におけるパターン・テー
ブルのエントリの関係は、次の３種類が可能である。１）１つのエントリが、第１の記憶レベル内の対応する
エントリによりエンコードされた状態に関係する（グロ
ーバル・パターン・ヒストリ・テーブルと称される）。２）エントリの群が、第１の記憶レベル内の対応するエ
ントリによりエンコードされた状態に関係するが、さら
に、その群中の各エントリが、特定の分岐命令の静的分
岐アドレスにより索引付けされる（パー・アドレス・パ
ターン・ヒストリ・テーブルと称される）。３）エントリの群が、第１の記憶レベル内の対応するエ
ントリによりエンコードされた状態に関係するが、さら
に、その群中の各エントリが、所与の分岐命令セットの
セット属性に関係付けられる（パー・セット・パターン
・ヒストリ・テーブルと称される）。

【００１２】Yeh及びPratt による２レベル分岐予測機
構は、次のように機能する。分岐命令に遭遇したとき、
第１の記憶レベルがアクセスされ、その特定の分岐命令
に対応するエントリが第１の記憶レベルから読み取られ
る。第１の方式においては、第１の記憶レベルが１つの
エントリのみを保持し、そしてそのエントリはその特定
の分岐命令に対応する。第２の方式においては、特定の
分岐命令に対応する第１の記憶レベルのエントリが、そ
のエントリの索引がその特定の分岐命令のアドレスに一
致することにより識別される。第３の方式においては、
特定の分岐命令に対応する第１の記憶レベルのエントリ
が、そのエントリの索引がその特定の分岐命令に関連す
るセット属性に一致することにより識別される。

【００１３】第１の記憶レベル（及び可能であればその
特定の分岐命令の分岐アドレスやセット属性）によりエ
ンコードされた状態は、パターン・テーブルを索引付け
するために用いられる。その後、その索引に対応するエ
ントリが、パターン・テーブルから読み取られる。パタ
ーン・テーブルから読み取られた２ビット・エントリ
は、その予測を示す。特定の分岐命令が選択であるか若
しくは非選択であるかが解明された後、それに従って、
第１の記憶レベル内の対応するエントリにエンコードさ
れた状態が更新されると共に、パターン・テーブル内の
対応するエントリもまた更新される。

【００１４】IBM Technical Disclosere Bulletin, Vo
l. 36, No. 12, Dec. 1993に提示された別のシステムに
おいては、分岐命令の結果を予測するビットを記憶する
分岐コンテキスト・レジスタ・ヒストリ・テーブル(Ｂ
ＣＲＨＴ)が用いられる。ＢＣＲＨＴのビットは、所与
の分岐命令についての予測子(predictor)のベクトルを
導出するためにその所与の分岐命令のアドレスを用いて
アクセスされる。このベクトルは、グローバル分岐動作
ベクトルに保持される値により索引づけされる。グロー
バル分岐動作ベクトルは、その所与の分岐命令に先行す
る最後のｎ個の分岐の動作を表現するｎビットのバイナ
リ値を記憶する。この索引は、所与の分岐命令の動作を
予測するために用いられることになる予測子のベクトル
の成分を選択する。分岐命令の結果が解明されると、用
いられた予測子のベクトルの成分が必要に応じて更新さ
れる。更新された予測子のベクトルが元のベクトルと異
なる場合は、更新されたベクトルにより元のベクトルが
置換される。

【００１５】

【発明が解決しようとする課題】本発明の目的は、高い
確度で、条件分岐命令の結果を効率的に予測する機構を
提供することである。

【００１６】

【課題を解決するための手段】本発明によれば、ヒスト
リ・テーブルが、１又は複数の分岐命令に関連するコン
テキスト指向予測子を記録するために用いられる。好適
には、コンテキスト指向予測子は、ヒストリ・テーブル
の各エントリ内で分岐予測子のベクトルを統合すること
によりヒストリ・テーブルから導出される。このベクト
ルは、各ｎの値について２ⁿ個の予測子(predictor)のセ
ットを構成する（ここで、ｎは任意のセットとすること
ができるが、好適には所与の実施態様において一定とさ
れる）。プロセッサのプリフェッチ動作によりヒストリ
・テーブルがアクセスされるとき、先祖分岐と称される
所与の分岐についての予測子のベクトルがヒストリ・テ
ーブルから取り出されて記憶される。ｎ回の取り出しの
後、次に訪れる分岐のｎ番目の先祖分岐（すなわち先行
分岐）に関連した予測子のベクトルから予測子へアクセ
スするために最後のｎ個の分岐の動作ヒストリが用いら
れる。この予測子は、その先祖分岐のｎ番目の後続分岐
を予測するために用いられる。必要に応じて、先祖分岐
に関連するベクトルから導出された予測子を更新するた
めに、このようなｎ番目の後続分岐の次の動作が用いら
れ、そしてそのベクトルは、ヒストリ・テーブル内のそ
の先祖分岐命令に従って索引付けされる場所に再記憶さ
れる。

【００１７】コンテキスト指向予測子の長所は、次に現
れる分岐の動作予測がその分岐のアドレスに依存しない
ので、その動作予測をその分岐のデコード時間よりもは
るかに速く行うことができる点である。さらに、予測子
を先祖分岐及び一連の分岐解明結果に関連付けることに
より、その分岐の実行に先行するプログラム動作を表す
パスが、より忠実に個別化されると共に、予測機構に対
してさらに多くの情報が使用可能である。予測されよう
とする分岐の場所は、最終的には命令フェッチ機構によ
り明らかにされ、このアドレスはその分岐動作を予測す
るためには特に用いられないが、分岐予測子の集まりを
索引付けするために先祖分岐アドレスと目標分岐アドレ
スの組合せが用いられるときに利用することができる。

【００１８】本発明の他の目的及び利点は、以下の図面
と共に示される詳細な説明によりさらに明確に理解され
るであろう。

【００１９】

【発明の実施の形態】先ず、一般的な高性能プロセッサ
において命令がフェッチされ実行される方法を説明す
る。その後、本発明による分岐ヒストリ・テーブルを用
いたマシンの構造及び動作をさらに詳細に説明する。以
下の説明は、本発明をＲＩＳＣアーキテクチャのプロセ
ッサにおいて実施するものであるが、本発明はこのアー
キテクチャに限定されず、有効性及び汎用性を失うこと
なく非ＲＩＳＣアーキテクチャのプロセッサにおいても
実施可能である。

【００２０】図２は、一般的な高性能処理システムの本
質的特徴を示す構成図である。説明のために、図２で
は、分岐予測と共に含まれるＲＩＳＣ状のパイプライン
・プロセッサの部分を強調している。そして完全な設計
において必要な他の多くの特徴については簡略化又は省
略している。

【００２１】処理システムは、プロセッサ・ユニット１
００及び関連するメモリ・ユニット１０２を含む。メモ
リ・ユニット１０２は、プロセッサ・ユニット１００上
で実行されるプログラム・データ及び命令を保持する。
メモリ・ユニット１０２に記憶される命令は、分岐命令
を含むことができる。

【００２２】汎用的であるが、命令ユニット１０２は、
命令キャッシュ・ユニット１０４及びデータ・キャッシ
ュ・ユニット１０６とインタフェースされることによ
り、メモリ・ユニット１０２内の頻繁に用いられる命令
部分及びデータ部分が、それぞれ命令キャッシュ・ユニ
ット１０４及びデータ・キャッシュ・ユニット１０６内
に維持される。別の手段として、命令キャッシュ・ユニ
ット１０４とデータ・キャッシュ・ユニット１０６を、
１つに統合したキャッシュへと併合することもできる。
キャッシュ・ユニット１０４、１０６に関するアクセス
時間は、通常、メモリ・ユニット１０２のそれに比べて
はるかに短い。命令キャッシュ１０４及び／又はデータ
・キャッシュ１０６は、周知のように、多数のキャッシ
ュ若しくは多階層のキャッシュから構成することもでき
る。

【００２３】通常、命令キャッシュ１０４及びデータ・
キャッシュ１０６に記憶される命令及びデータは、それ
ぞれライン又はブロックへ分割される。命令フェッチ・
ユニット１０８は、命令キャッシュ１０４に記憶された
命令の１又は複数のブロックをデコード・ユニット１１
０へとフェッチする。デコード・ユニット１１０は、分
岐及び条件レジスタ更新命令を実行のために分岐ユニッ
ト１１２へ送り、そして順次の非分岐命令をディスパッ
チ・ユニット１１４へ送る。ディスパッチ・ユニット１
１４は、ペンディング中の命令同士の間の依存性を解析
し、１又は複数の機能ユニット１１６上での命令の実行
をスケジューリングする。

【００２４】Ｄフェッチ・ユニット１１８は、データの
ブロックをデータ・キャッシュ１０６から必要に応じて
機能ユニット１１６へフェッチすることを取り扱う。デ
ータ・キャッシュ・ユニット１０６は、命令によりソー
ス・オペランドとして用いられる所与のデータ及び実行
された命令により発生される所与のデータ値を保持す
る。多数のメモリ常駐データ値が機能ユニット１１６に
より同時に必要とされたり、多数のメモリ行きの結果が
同時に発生されたりするので、通常、データ・キャッシ
ュ・ユニット１０６はマルチポートとされている。

【００２５】処理ユニット１００はさらに、一組のレジ
スタを含むレジスタ・ファイル１２０を具備する。レジ
スタ・ファイル１２０は、命令を実行するために機能ユ
ニット１１６に対してオペランドを提供すると共に、実
行の結果を受信する。このレジスタ・ファイル１２０
は、アーキテクチャ的に可視のレジスタの組とアーキテ
クチャ的に不可視のレジスタの組へと分割される。アー
キテクチャ的に可視の、すなわち構造化レジスタは、レ
ジスタの固定セットと称され、マシンのアセンブリ・レ
ベルのプログラマ（又はコンパイラ）に対してアクセス
可能である。このようなレジスタ・ファイル１２０は、
従来の技術として知られている。

【００２６】各機能ユニット１１６は、幾つかの又は全
てのタイプの命令の実行を行うことができる。機能ユニ
ット１１６は、レジスタ・ファイル１２０及び／又はデ
ータ・キャッシュ・ユニット１０６から入力ソース・オ
ペランドを受信し、かつ、これらへ出力結果を書き込
む。実施例においては、全ての機能ユニット１１６が同
一であるので、任意の命令を実行することができる。別
の方法として機能ユニット１１６を非対称としてもよ
く、その場合、特定のユニットが、命令の所与のサブセ
ットのみを実行することができる。この場合、ディスパ
ッチ・ユニット１１４は、この非対称性を認知すると共
に命令を適宜スケジューリングしなければならない。

【００２７】プロセッサ・ユニット１００はさらに、ア
ーキテクチャにより有効な順序とみなされる順序で命令
実行を完了することを担う完了ユニット１２２を具備す
る。機能ユニット１１６が順序に従わずに命令を実行す
る場合であっても、アーキテクチャの制約によってはプ
ロセッサ・ユニット１００が、同じ順序で命令を完了で
きる場合とできない場合がある。

【００２８】分岐ユニット１１２は、分岐命令としてデ
コードされた命令を処理すると共に、命令フェッチ・ユ
ニット１０８による命令のフェッチを制御する。プログ
ラム実行の中で発生可能な３つのタイプの分岐命令があ
る。タイプ１：決して選択されない分岐命令タイプ２：常に選択される分岐命令タイプ３：選択されて、そして引き続き選択されない分
岐命令であって、通常、条件分岐命令と称される。

【００２９】タイプ１の分岐命令は、プロセッサ内のプ
リフェッチを実行することに関して分岐ユニット１１２
により無視される。本発明自体、タイプ２及びタイプ３
の分岐命令に関連する。タイプ３の分岐命令は分岐ユニ
ット１１２により識別され、そして識別されたならば、
分岐ユニット１１２は、その条件分岐命令の現在の動的
インスタンスを予測するために機能する。条件分岐命令
の結果を予測した後、命令フェッチ・ユニット１０８に
より記憶された命令フェッチ・アドレスがその予測に従
って更新される。もしその条件分岐命令が選択されると
予測されたならば、命令フェッチ・ユニット１０８は、
その分岐命令の非順次目標アドレスにより更新される。
この場合、命令フェッチ・ユニット１０８は、その条件
分岐命令の目標アドレスにおいて始まる予測されたパス
から推論的に命令をロードすることができる。もし条件
分岐命令が選択されないと予測されたならば、命令フェ
ッチ・ユニット１０８は、命令シーケンス中の次の順次
アドレスにより更新される。この場合、命令フェッチ・
ユニット１０８は、次の順次アドレスのアドレスにおい
て始まる予測されたパスから推論的に命令をロードする
ことができる。

【００３０】分岐ユニット１１２が、条件分岐命令が解
明されたと判断したとき、命令フェッチ・ユニット１０
８により記憶された命令フェッチ・アドレスが、その解
明された分岐命令に従って更新される。条件分岐命令
は、その命令が依存する条件レジスタ・ビットが更新さ
れた後にのみ解明されたとみなされる。さらに具体的に
云えば、解明された分岐命令が、選択されると予測され
ておりかつ選択されたと解明された場合、コンピュータ
処理システムの通常のオペレーションが続けられる。同
様に、解明された分岐命令が、選択されないと予測され
ておりかつ選択されなかったと解明された場合も、通常
のオペレーションが続けられる。一方、解明された命令
が、選択されると予測されておりかつ選択されなかった
と解明された場合、命令フェッチ・ユニット１０８が順
次（非選択）パスに従ってフェッチするべく更新される
と共に、目標（選択）パスから推論的に実行された命令
が破棄される。同様に、解明された命令が、選択されな
いと予測されておりかつ選択されたと解明された場合、
命令フェッチ・ユニット１０８が目標（選択）パスに従
ってフェッチするべく更新されると共に、順次（非選
択）パスから推論的に実行された命令が破棄される。

【００３１】本発明は、条件分岐命令の結果予測におけ
る分岐ユニット１１２の構造及びオペレーションを対象
とする。本発明における分岐ユニット１１２は、複数の
エントリを記録する分岐ヒストリ・テーブル（ＢＨＴ）
を含む。幾つかのエントリは、タイプ２の分岐命令に対
応する。他のエントリは、タイプ３の条件分岐命令に対
応する。条件分岐命令に対応する各エントリは、条件分
岐命令の目標アドレスを識別する目標アドレス・フィー
ルドと、条件分岐命令に続く複数のパスに関連する予測
子情報とを含む。予測子情報は、各パスについて、所与
のパスの終わりにおける終端条件分岐命令が、選択され
ると予測されるべきか又は選択されないと予測されるべ
きかを示す。所与の条件分岐命令についての予測子を発
生するプロセスは、その所与の分岐命令に対応する先祖
分岐命令に関連する予測子情報を識別し、その先祖分岐
命令からその所与の分岐命令までを導くパスに対応する
適宜の予測子情報を選択することを含む。このパスは、
その先祖分岐命令からその所与の条件分岐命令の直前の
条件分岐命令までの、各条件分岐命令の解明により決定
される。

【００３２】例えば、図３に示すプログラム・セグメン
トを想定する。条件分岐命令は、Ｂ０、Ｂ１、Ｂ
２、...と符号を付され、非条件命令は、Ｓ０、Ｓ１、
Ｓ２、...と符号を付されている。さらに、このような
条件分岐命令に対応するＢＨＴのエントリは、分岐命令
から２個の分岐を経るパス（すなわちｎ＝２）に対応す
る予測子情報を含む。この場合、ＢＨＴは、分岐Ｂ０に
対応するエントリを記録する。このエントリは、分岐Ｂ
０の目標アドレスを識別する目標アドレス・フィールド
と、分岐命令Ｂ０に続く４つのパス（選択／選択、選択
／非選択、非選択／選択、非選択／非選択）の各々に関
連する予測子情報とを含む。この予測子情報は、各パス
について、所与のパスの終わりにおける終端条件分岐命
令（Ｂ６、Ｂ５、Ｂ４、Ｂ３）が選択されると予測され
るべきか又は選択されないと予測されるべきかを示す。

【００３３】さらに、ＢＨＴは、Ｂ１分岐に対応するエ
ントリを記録する。このエントリは、分岐Ｂ１の目標ア
ドレスを識別する目標アドレス・フィールドと、分岐命
令Ｂ１に続く４つのパス（（選択／選択、選択／非選
択、非選択／選択、非選択／非選択））の各々に関連す
る予測子情報とを含む。この予測子情報は、各パスにつ
いて、所与のパスの終わりにおける終端条件分岐命令が
選択されると予測されるべきか又は選択されないと予測
されるべきかを示す。

【００３４】同様に、ＢＨＴは、分岐Ｂ２、Ｂ３、Ｂ
４、Ｂ５及びＢ６に対応するエントリを記録する。例え
ば、分岐ｂ６に対応するエントリは、分岐Ｂ６の目標ア
ドレスを識別する目標アドレス・フィールドと、分岐命
令Ｂ１に続く４つのパス（（選択／選択、選択／非選
択、非選択／選択、非選択／非選択））の各々に関連す
る予測子情報とを含む。この予測子情報は、各パスにつ
いて、所与のパスの終わりにおける終端条件分岐命令が
選択されると予測されるべきか又は選択されないと予測
されるべきかを示す。

【００３５】所与の条件分岐命令、例えば分岐命令Ｂ６
についての予測子を発生するために、その所与の分岐命
令Ｂ６に対応する先祖分岐命令Ｂ０に関連するエントリ
がＢＨＴから読み取られ、そして先祖分岐命令Ｂ０から
所与の分岐命令Ｂ６までを導くパスに対応する所与のエ
ントリ内の適宜の予測子情報が選択される。このパス
は、先祖分岐命令Ｂ０から所与の分岐命令の直前の条件
分岐命令（Ｂ６に対するＢ２）までの条件分岐の結果の
解明により決定される。仮に条件分岐命令Ｂ６について
発生された予測子が、分岐命令Ｂ６は選択と予測される
べきであることを示している場合、条件分岐命令Ｂ６の
目標アドレスが命令フェッチ・ユニット１０８へ送られ
る。好適には、条件分岐命令Ｂ６の目標アドレスは、条
件分岐命令Ｂ６に関連するＢＨＴから読み取られたエン
トリの一部である。

【００３６】さらに具体的には図４に示すように、本発
明の分岐ユニット１１２が、ＢＨＴ２０１、分岐解明記
録レジスタ２０３、分岐アドレス及び予測ベクトルのス
タック（以下、分岐予測スタック２０５と称する）、及
び予測論理２０７を含み、これらは、条件分岐命令の結
果を予測するために協同的に動作し、そして選択される
と予測された条件分岐命令については、その予測された
条件分岐の目標アドレスをＢＨＴから命令フェッチ・ユ
ニット１０８へと送らせる。

【００３７】図５乃至図７は、ＢＨＴ２０１をより詳細
に示す図である。図５に示すように、ＢＨＴ２０１は、
プリフェッチ・アドレスＸを記憶する入力ラッチ３００
を含む。アドレスＸは、２つの部分へ分割することがで
きる。すなわち、そのブロックのブロック・アドレスＢ
Ａ及びオフセットＯＦＦである。入力ラッチ３００に記
憶されたアドレスＸは、エントリのアレイ３０２と比較
される。図６に示すように、アレイ３０２の各エントリ
は条件ビットＢ（符号３０５）を含み、これがセットさ
れるときはそのエントリが条件分岐命令に関連すること
を示す。ＢＲタグ３０６は、そのブロック中の対応する
分岐命令の場所を示す。ベクトル３０８は対応する条件
分岐命令に関連し、目標アドレス・フィールド３０９は
対応する分岐命令の目標アドレスを識別する。図７に示
すように、ベクトル３０８は、複数のサブフィールドを
含む。例えば、図示のサブフィールド４０３−０、４０
３−１、...４０３−３である。この場合、各サブフィ
ールドは、関連するＢＲタグ３０６により識別された条
件分岐命令に続くパスに対応する。各サブフィールド
は、所与のサブフィールドに関連するパスの終わりにお
ける分岐命令が選択と予測されるべきか又は非選択と予
測されるべきかを示す予測子を含む。予測子サブフィー
ルド４０３−１、４０３−２、...４０３−３内で用い
られるビットの数は、実施態様による決定事項であり、
開示される本発明のオペレーションには影響を及ぼさな
い。最も単純な手法としては、単一ビットの予測子サブ
フィールドを用いる。この場合、「１」は、所与のパス
における分岐命令が選択と予測されるべきであることを
示し、そして「０」は、所与のパスにおける分岐命令が
非選択と予測されるべきであることを示す。通常、所与
のパスの終わりにおける分岐命令の最も新しく発生した
ものが選択と解明されたとき、ビットが「１」にセット
され、そして、所与のパスの終わりにおける分岐命令の
最も新しく発生したものが非選択と解明されたとき、ビ
ットが「０」にクリアされる。予測子サブフィールドと
して、１ビットより多いビットを用いることができる。
例えば、J. Smithによる「A Study of Branch Predicti
on Strategies」(24th InternationalSymposium on Com
puter Architecture, May 1981, pp.135-148)に記載さ
れるように、予測子サブフィールドを２ビット飽和カウ
ンタとしてもよい。さらに、アレイ３０２は、完全アソ
シアティブ構造、直接マッピング構造、又はセット・ア
ソシアティブ構造として配置してもよい。図示のよう
に、アレイ３０２は、４ウェイ・セット・アソシアティ
ブ構造として配置されている。

【００３８】さらに具体的には、入力ラッチ３００に記
憶される完全アドレスＸの第１の部分ＢＡは、デコーダ
３１０へ与えられる。デコーダ３１０の機能は、アレイ
３０２の対応する行を活動状態とすることである。活動
状態とされた行の各エントリ（図示ように、４個のエン
トリ）は、アレイ３０２から記憶素子３１２へと読み出
される。入力ラッチ３００に記憶された完全アドレスＸ
の第２の部分ＯＦＦと共に記憶素子３１２へロードされ
たエントリは、ヒット認知及び選択論理３１４へ与えら
れる。ヒット認知及び選択論理３１４は、記憶素子３１
２へロードされたエントリが２つの条件に適合するか否
かを判断する。すなわち、条件ビットＢがセットされて
いるか否か、及び、ＢＲタグ３０６がプリフェッチ・ア
ドレスのオフセットＯＦＦよりも大きいか否かである。
これら２つの条件に適合する場合、ヒット認知及び選択
論理３１４は、「ヒット」信号、ブロック・アドレスＢ
Ａ及び分岐アドレスＢＲ（条件に適合する分岐命令の完
全アドレスを識別する）、その分岐命令に関連する予測
ベクトル、並びにその分岐命令に関連する目標アドレス
ＴＡを出力する。もしこれら２つの条件に適合しない場
合は、ヒット認知及び選択論理３１４は、「ミス」信号
を出力する。

【００３９】ここで、１つのブロックについて複数の分
岐命令が２つの条件を満足する場合があることを注記す
る。この場合、ヒット認知及び選択論理３１４は、それ
らの分岐命令から１つの命令を抽出するために更なる論
理を含む。例えば、ＢＲタグがプリフェッチ・アドレス
のオフセットＯＦＦに最も近くかつそれよりも大きい分
岐命令を抽出する。

【００４０】ＢＨＴ２０１のヒット認知及び選択論理３
１４により発生されたヒット信号／ミス信号、ブロック
・アドレスＢＡ及び分岐アドレスＢＲ（分岐命令の完全
アドレスを識別する）、その分岐命令の予測ベクトル並
びに目標アドレスは、データ・パス２１１を介して分岐
予測スタック２０５へ与えられる。分岐予測スタック２
０５は、好適には、ｎ個のエントリを保持する先入れ先
出し（ＦＩＦＯ）バッファとして構成される。その各エ
ントリは、分岐命令の完全アドレスと、その分岐命令に
関連する予測ベクトルとを含む。好適には、ヒット信号
が分岐予測スタックへ与えられた場合、ブロックアドレ
スＢＡと分岐アドレスＢＲとが連結されて分岐命令の完
全アドレスを形成する。完全アドレスは、関連する予測
ベクトルと共に、分岐予測スタック２０５内の先頭エン
トリとして追加される。従って、分岐予測スタック２０
５内の最も古いエントリは、次に現れる条件分岐命令の
ｎ番目の先祖である条件分岐に対応する。

【００４１】加えて、分岐ユニット１１２は分岐解明論
理２０９を含む。分岐解明論理２０９は、条件分岐命令
が選択又は非選択のいずれかであると解明し、そしてそ
の分岐命令が選択又は非選択として解明されたことを示
すためにその条件分岐命令に関連する分岐解明記録レジ
スタ２０３のビットをデータ・パス２１３を介してセッ
トする。例えば、バイナリ値「１」をもつ分岐解明記録
レジスタ２０３のビットは、そのビットに関連する条件
分岐命令が選択されたと解明されたことを示す。そして
バイナリ値「０」をもつ分岐解明記録レジスタ２０３の
ビットは、そのビットに関連する条件分岐命令が選択さ
れなかったと解明されたことを示す。好適には、分岐解
明記録レジスタ２０３のビットは、シーケンシャル順序
における最も新しいｎ個の分岐命令の解明結果を表す。

【００４２】分岐解明論理２０９は、シーケンシャル順
序において条件分岐命令を解明することができる。この
場合、分岐解明記録レジスタ２０３をｎビットのシフト
・レジスタとすることができる。このｎビットのシフト
・レジスタは、分岐解明論理２０９によりロードされる
ことにより、最も新しく解明された分岐命令の選択／非
選択の解明状態を示すビットをシフトさせる。一方、分
岐解明論理２０９は、シーケンシャル順序に従わずに条
件分岐命令を解明することもできる。この場合も、分岐
解明記録レジスタ２０３のビットが、プログラム順序で
次に現れる任意の条件分岐に先行するｎ個の条件分岐の
解明結果を表すとすれば、分岐解明記録レジスタ２０３
を更新するためにさらに高度な機構が必要となることが
ある。

【００４３】本発明は、次の条件分岐を予測するため
に、分岐予測スタック２０５における最も古いエントリ
と共に分岐解明記録レジスタ２０３に記憶されたデータ
を利用する。説明のために図８に示したスタックを想定
する。次の条件分岐命令に対応するエントリは、このス
タックの一部ではなく、αとして示される。次の条件分
岐命令αのｎ番目の先祖条件分岐命令に対応するエント
リは、このスタックの最も古いエントリであり、βとし
て示される。ｎ番目の先祖条件分岐命令βと次に現れる
条件分岐命令αとの間の条件分岐命令に対応するｎ−１
個のエントリもまた、スタック２０５４の一部である。
スタック２０５の最も新しいエントリは、条件分岐命令
δに対応し、これは、次に現れる条件分岐命令αの直前
である。加えて、条件分岐命令βの直前の条件分岐命令
γに対応するエントリは、図示のようにスタックの一部
ではない。

【００４４】次に現れる分岐命令αについての予測子を
発生するプロセスは、先祖分岐β（分岐予測スタック２
０５内の最も古いエントリに記憶されている）に関連す
る予測ベクトルと、βとαとの間のｎ−１個の条件分岐
の解明結果（分岐解明記録レジスタ２０３内に記憶され
ている）とを含む。

【００４５】さらに具体的には、分岐解明記録レジスタ
２０３内のデータが、先祖分岐命令から次に現れる分岐
命令αまでのパスを特定し、そして、そのパスに対応す
る分岐予測スタック２０５中の最古エントリの予測子ベ
クトル内のサブフィールドを選択するために用いられ
る。次に、選択された予測子サブフィールドは、データ
・パス２１５を介して予測論理２０７へ送られる。予測
論理２０７は、予測子サブフィールドを解析することに
より、その分岐命令が選択されると予測すべきか選択さ
れないと予測すべきかを決定する。上記の通り、予測子
サブフィールドに用いられるビットの数は、実施態様に
よる決定事項である。予測子サブフィールドが、その分
岐命令は選択されないと予測すべきことを示す場合、予
測論理２０７は、ＢＨＴの再検査を起動させることによ
り、プリフェッチ・ブロック内に後に発生する条件分岐
命令に対応する別のエントリをＢＨＴが含むか否かを決
定する。適合するエントリが見出されない（すなわち、
再検査の結果が別の非選択予測となった）場合、予測論
理２０７は非選択信号を発生し、この信号は命令フェッ
チ・ユニット１０８へ送られる。一方、予測子サブフィ
ールドが、その分岐命令は選択されると予測すべきこと
を示す場合、予測論理２０７は、選択信号を発生して命
令フェッチ・ユニット１０８へと送り、さらにデータ・
パス２１７を介してＢＨＴ２０１を制御することにより
分岐命令αの目標アドレスを命令フェッチ・ユニット１
０８へと送る。分岐命令αの目標アドレスは、ＢＨＴ２
０１内の分岐命令αに関連するエントリから読み出され
る。

【００４６】上記の本発明のＢＨＴ２０１は、好適に
は、タイプ２の分岐命令に対応するエントリを含む。こ
のようなエントリは、図５乃至図７に示したタイプ３の
分岐命令に対応するＢＨＴエントリと同様に、条件ビッ
トＢ（符号３０５）、ＢＲタグ３０６、及び目標アドレ
ス・フィールド３０９を含む。このようなエントリの条
件ビットＢは、タイプ２の分岐命令に対応するエントリ
であることを示すためにクリアされる。さらに、タイプ
２の分岐命令は常に選択されるので、そのエントリの予
測子フィールド３０８は、タイプ２の分岐命令の結果を
予測する際に用いられない。このようなエントリの１つ
がＢＨＴ２０１から読み取られた場合、ＢＨＴ２０１
は、ヒット信号を発生し、そのエントリの目標アドレス
を命令フェッチ・ユニット１０８へと送る。命令フェッ
チ・ユニット１０８は、そのタイプ２の分岐命令の目標
アドレスにおいて始まる予測されたパスから推論的に命
令をロードする。タイプ２の分岐命令が選択されなかっ
たと解明された場合、ＢＨＴ更新論理は、ＢＨＴ内にタ
イプ３の分岐命令に対応する新たなエントリを作成し、
そして後述するようにその新たなエントリを初期化す
る。さらに、命令フェッチ・ユニット１０８は、そのタ
イプ２の分岐命令のシーケンシャル（非選択）・パスに
従ってフェッチするべく更新されると共に、そのタイプ
２の分岐命令の目標（選択）パスに従って推論的に実行
された命令が破棄される。

【００４７】ＢＨＴ２０１は、修正を必要とすることが
ある。例えば、分岐命令βに関連するＢＨＴエントリの
予測ベクトルに記憶された分岐命令αの選択／非選択予
測が誤っていることがある。すなわち、分岐命令αに関
連するＢＨＴエントリに記憶された分岐命令αの目標ア
ドレスが誤っている場合である。ＢＨＴ２０１の修正を
可能とするために、本発明のシステムは、ＢＨＴ更新論
理を含む。この論理は、タイプ２の分岐命令についての
動作の誤り、タイプ２及びタイプ３の分岐命令について
の目標の誤り、並びにタイプ３の分岐命令についての予
測の更新を処理する。もし、非選択と解明されたタイプ
２の分岐命令をＢＨＴが有しているならば、ＢＨＴ更新
論理は、そのエントリがタイプ３の分岐命令に対応する
ことを示すべく条件ビットＣ（符号３０５）をセットす
ることによりＢＨＴエントリを更新し、そしてそのエン
トリの予測ベクトルが以下に説明するように初期化され
る。そのエントリの目標アドレス・フィールドは修正さ
れない。タイプ２又はタイプ３の分岐命令のいずれかに
ついて目標の誤りが発生した場合、既存のＢＨＴエント
リを更新するために新たに解明された目標アドレスが用
いられる。ここで、タイプ３の分岐命令についての予測
の更新について説明する。

【００４８】前述の条件分岐命令βに続く命令シーケン
スを想定する。条件分岐命令γは、条件分岐命令βの直
前にある。この状況において、スタック２０５内の最古
のエントリが分岐命令βに対応しかつ分岐命令δ（この
スタック内の最新のエントリに対応する）が選択又は非
選択と解明されたとき、ＢＨＴ更新論理は、以下の１）
乃至４）を記憶する。１）条件分岐命令γに対応するＢＨＴエントリの場所を
識別するデータ、例えば、分岐命令γのアドレス。２）分岐命令γに関連する最も新しい予測ベクトル。３）分岐命令δの解明状態（選択／非選択）。４）分岐命令δの結果を予測するために用いられる分岐
解明記録レジスタ２０３のビット（これらのビットは、
分岐命令γから分岐命令δまでのパスを特定する）。

【００４９】分岐命令γのアドレス及び分岐命令γに関
連する最新予測ベクトルが、スタック２０５からＢＨＴ
更新論理へロードされると、分岐命令γに対応するエン
トリがシフトしてスタック２０５から出される。分岐命
令δの解明状態（選択／非選択）は、分岐解明論理２０
９によりＢＨＴ更新論理へ与えることができる。

【００５０】ＢＨＴ更新論理は、必要に応じて、先ず分
岐命令γに関連する最新予測ベクトル内の適宜の予測子
サブフィールドを選択することにより、分岐命令γに関
連するＢＨＴエントリの予測ベクトルを更新する。適宜
の予測子サブフィールドは、分岐命令δの結果を予測す
るために用いられる分岐解明記録レジスタ２０３のビッ
トにより特定される分岐命令γから分岐命令δまでのパ
スに対応する。次に、ＢＨＴ更新論理は、分岐命令δの
解明状態に従って選択された予測子サブフィールドを更
新する。例えば、「１」ビットの予測子サブフィールド
が実施されかつ選択された予測子サブフィールドが分岐
命令δの解明状態に一致しない場合、予測子サブフィー
ルドは、分岐命令δの解明状態に一致するように更新さ
れる。選択された予測子サブフィールドに変更がない場
合、ＢＨＴ更新論理のオペレーションは終了する。一
方、選択された予測子サブフィールドが更新される場
合、更新された予測子サブフィールドが、分岐命令γに
関連する予測子ベクトルへ組み込まれ、そして更新され
た予測子ベクトルは、分岐命令γのアドレスにより識別
される場所においてＢＨＴへ書き込まれる。

【００５１】ＢＨＴ２０１の初期化は、多くの異なる手
法を用いて実行することができる。例えば、先ずＢＨＴ
２０１がクリアされ、そして全ての分岐が存在しないす
なわち選択されないとみなされる。次に、選択された分
岐が解明されると、これらの分岐に関連するエントリが
ＢＨＴ２０１内に作成され、これらのエントリは、その
分岐をそれらの適宜の目標に対して非条件的であり選択
されるとして特定する。もしＢＨＴ２０１内のエントリ
が、その後に選択されたかったならば、条件分岐ビット
がセットされ、そしてこの分岐のｎ個の子孫分岐につい
ての予測子ベクトルが初期値に、例えば、全てが選択に
セットされる。予測子が用いられると、その予測子ベク
トル成分が用いられた子孫分岐の解明に基づいて適宜初
期値が修正されることになる。ｎ番目の条件分岐の検知
の前に、更新手順がバイパスされ、分岐予測スタック２
０５内の初期値が、所与のデフォールトの初期値を含む
ことにより所与のエントリが無効であることを示すこと
になる。この場合、条件分岐の予測もまたデフォールト
のオプションを用いることになる。

【００５２】上記のように、本発明のＢＨＴは、タイプ
２とタイプ３の双方の分岐命令に対応するエントリと、
最後のタイプ３の分岐命令の解明状態を記録する分岐解
明記録レジスタとを含む。次に現れる分岐命令について
の予測子は、ｎ番目の先祖条件分岐命令に関連する予測
ベクトルと、分岐解明記録レジスタに記憶されたｎ番目
の先祖条件分岐命令と次に現れる条件分岐命令との間の
ｎ−１個の条件分岐の解明結果とを読み取ることにより
発生される。従って、この手法を利用すると、タイプ２
の分岐命令は先祖となり得ない。しかしながら、本発明
はこの点に関して限定されない。別の手法として、分岐
解明記録レジスタが、最後のタイプ２及び／又はタイプ
３の分岐命令の解明状態を記録してもよい。この場合、
次に現れる分岐命令についての予測子は、ｎ番目の先祖
分岐命令に関連する予測ベクトルと、分岐解明レジスタ
に記憶されたｎ番目の先祖分岐命令と次に現れる分岐命
令との間のｎ−１個の分岐の解明結果とを読み取ること
により発生される。従って、この場合の予測方式は、タ
イプ２とタイプ３の分岐命令の間で差異はない。

【００５３】別の実施例として、タイプ２とタイプ３の
それぞれの分岐命令に対して２つの別個のテーブルを用
いることもできる。第１のＢＨＴは、好適には上記の本
発明のＢＨＴであるが、タイプ３の分岐命令を予測する
ために用いられる。そして第２のＢＨＴは、汎用的なＢ
ＨＴであってもよく、タイプ２の分岐命令を予測するた
めに用いられる。タイプ２の分岐命令が選択されると予
測され、そして選択されなかったと解明された（すなわ
ち、タイプ３の分岐命令となる）場合、この分岐命令に
対応するエントリが第２のＢＨＴから取り除かれ、第１
のＢＨＴ内に新たなエントリが作成される。

【００５４】さらに別の実施例として、本発明をＤＨＴ
として実施することができる。前述のように、ＤＨＴ
は、ＢＨＴのように選択される分岐の動作と目標アドレ
スを予測するのではなく、分岐の動作を予測する。ＤＨ
Ｔは、通常、その分岐の動作を予測する予測子のテーブ
ル内へ索引付けするためにその分岐のアドレスと最新の
分岐動作を利用する。本発明によれば、索引付けオペレ
ーションにおいてその分岐のアドレスを置換するものと
して先祖分岐のアドレスを用いることができる。以前に
遭遇した分岐についての情報は保持されないので、予測
子のテーブルを索引付けするために用いられるアドレス
を有する先祖分岐命令と、その予測子を用いようとする
子孫分岐命令との間の隔たりを規定する際に、全ての分
岐（タイプ１、タイプ２及びタイプ３）が考慮されるこ
とが好ましい。好適には、ＤＨＴのエントリは、先祖分
岐のアドレスに関連しかつその先祖分岐命令と予測され
ようとする分岐命令との間にある分岐の中間動作ヒスト
リに基づく複数のコンテキスト指向予測子を含む。

【００５５】この発明におけるｎ値は任意であるが、ハ
ードウェア・レジスタの幅を決定する実施態様の範囲内
で固定される。このことは、予測ベクトルの成分として
用いられる予測子のタイプにも同様に当てはめられる。

【００５６】本発明のコンテキスト指向予測子は、相関
分岐予測子とは区別される。相関分岐予測子は、分岐の
アドレス及び最後のｎ個の分岐命令の動作に基づくもの
である。コンテキスト指向予測子は、次の状況下におい
て相関分岐予測子よりも優れている。１）より早期の予測子が望ましい状況下において優れて
いる。コンテキスト予測子は、予測されようとする分岐
のアドレスではなく先祖分岐のアドレスに基づくからで
ある。２）予測子の数が制約要因でない状況下において優れて
いる。この場合、動作シーケンスの長さに対して、予測
子の数が、選択可能なパスの数とほぼ同じである。３）短い動作シーケンスに基づく予測が必要とされる状
況下において優れている。

【００５７】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００５８】（１）メモリに記憶された命令のシーケン
スが少なくとも１つのプロセッサ・ユニットにより実行
されかつ前記メモリに記憶された命令のシーケンスが１
又は複数の分岐命令を含むデータ処理システムにおいて
分岐命令の結果を予測する装置であって、各エントリが
それぞれ分岐命令に関連しかつその関連する分岐命令か
ら終端の分岐命令までを導く実行パスに対応する予測子
のセットを含み、かつ各予測子が前記対応する実行パス
の終わりにおける前記終端の分岐命令の結果を予測する
ためのデータを記憶している、複数のエントリを記憶す
るテーブルと、前記テーブルへ与えられるアクセス信号
に関連するエントリを前記テーブルから読み出す手段
と、前記テーブルから読み出された前記エントリに関連
する前記分岐命令から次に現れる分岐命令までを導く実
行パスを決定する手段と、前記実行パスに対応するテー
ブルから読み出された前記エントリに含まれる前記予測
子のセットの中から予測子を選択する手段と、前記選択
された予測子に記憶されたデータに従って前記次に現れ
る分岐命令の結果の予測を発生する手段とを有する分岐
命令の結果予測装置。（２）前記テーブルの特定のエントリの各々が、前記特
定のエントリに関連する分岐命令を識別する分岐識別フ
ィールドを含む上記（１）に記載の装置。（３）前記データ処理システムが、前記次に現れる分岐
命令の結果の予測に従う前記データ処理システムによる
推論的実行のためにメモリからデータをフェッチするデ
ータ・フェッチ手段を有する上記（１）に記載の装置。（４）前記アクセス信号が、前記データ処理システムに
よる推論的実行のためにフェッチされるメモリに記憶さ
れた命令のブロックを識別する命令フェッチ・アドレス
の一部である上記（３）に記載の装置。（５）前記テーブルの特定のエントリの各々が、前記特
定のエントリに関連する分岐命令の目標アドレスの一部
を識別する目標アドレス・フィールドを含み、前記次に
現れる分岐命令の結果の予測がその分岐命令が選択され
るとして示される場合、前記データ・フェッチ手段が、
前記次に現れる分岐命令に関連するエントリの前記目標
アドレス・フィールドにより識別される前記メモリ内の
場所からデータをフェッチする上記（３）に記載の装
置。（６）各エントリが複数の分岐命令に関連する上記
（１）に記載の装置。（７）前記アクセス信号が、前記データ処理システムに
より実行される分岐命令を識別する分岐命令アドレスの
一部である上記（６）に記載の装置。（８）前記テーブルのエントリと前記複数の分岐命令の
特定の分岐命令の各々との間の関係が、前記特定の分岐
命令の前記分岐命令アドレスの一部を変換することによ
り決定される上記（７）に記載の装置。（９）前記次に現れる分岐命令の解明状態に従って、前
記テーブルから読み出された前記エントリに含まれる前
記予測子のセット内の前記選択された１の予測子を更新
する手段を有する上記（１）に記載の装置。（１０）メモリに記憶された命令のシーケンスが少なく
とも１つのプロセッサ・ユニットにより実行され、前記
メモリに記憶された命令のシーケンスが１又は複数の分
岐命令であるデータ処理システムにおいて分岐命令の結
果を予測する方法であって、各エントリがそれぞれ分岐
命令に関連しかつその関連する分岐命令から終端の分岐
命令までを導く実行パスに対応する予測子のセットを含
み、かつ各予測子が前記対応する実行パスの終わりにお
ける前記終端の分岐命令の結果を予測するためのデータ
を含む複数のエントリをテーブルに記憶するステップ
と、前記テーブルへ与えられるアクセス信号に関連する
エントリを前記テーブルから読み出すステップと、前記
テーブルから読み出された前記エントリに関連する前記
分岐命令から次に現れる分岐命令までを導く実行パスを
決定するステップと、前記実行パスに対応するテーブル
から読み出された前記エントリに含まれる前記予測子の
セットの中から予測子を選択するステップと、前記選択
された予測子に記憶されたデータに従って前記次に現れ
る分岐命令の結果の予測を発生するステップとを有する
分岐命令の結果予測方法。（１１）前記テーブルの特定のエントリの各々が、前記
特定のエントリに関連する分岐命令を識別する分岐識別
フィールドを含む上記（１０）に記載の方法。（１２）前記次に現れる分岐命令の結果の予測に従う前
記データ処理システムによる推論的実行のためにメモリ
からデータをフェッチするステップを有する上記（１
０）に記載の方法。（１３）前記アクセス信号が、前記データ処理システム
による実行のためにフェッチされるメモリに記憶された
命令のブロックを識別する命令フェッチ・アドレスの一
部である上記（１２）に記載の方法。（１４）前記テーブルの特定のエントリの各々が、前記
特定のエントリに関連する分岐命令の目標アドレスの一
部を識別する目標アドレス・フィールドを含み、前記次
に現れる分岐命令の結果の予測がその分岐命令が選択さ
れるとして示される場合、前記データ・フェッチ手段
が、前記次に現れる分岐命令に関連するエントリの前記
目標アドレス・フィールドにより識別される前記メモリ
内の場所からデータがフェッチされる上記（１２）に記
載の方法。（１５）各エントリが複数の分岐命令に関連する上記
（１０）に記載の方法。（１６）前記アクセス信号が、前記データ処理システム
により実行される分岐命令を識別する分岐命令アドレス
の一部である上記（１５）に記載の方法。（１７）前記テーブルのエントリと前記複数の分岐命令
の特定の分岐命令の各々との間の関係が、前記特定の分
岐命令の前記分岐命令アドレスの一部を変換することに
より決定される上記（１６）に記載の方法。（１８）前記次に現れる分岐命令の解明状態に従って、
前記テーブルから読み出された前記エントリに含まれる
前記予測子のセット内の前記選択された１の予測子を更
新するステップを有する上記（１０）に記載の方法。（１９）メモリに記憶された命令のシーケンスが少なく
とも１つのプロセッサ・ユニットにより実行されかつ前
記メモリに記憶された命令のシーケンスが１又は複数の
分岐命令を含むデータ処理システムにおいて分岐命令の
結果を予測する装置であって、各エントリがそれぞれ分
岐命令に関連しかつその関連する分岐命令から終端の分
岐命令までを導く実行パスに対応する予測子のセットを
含み、各予測子が前記対応する実行パスの終わりにおけ
る前記終端の分岐命令の結果を予測するためのデータを
記憶している複数のエントリを記憶し、かつ、与えられ
るアクセス信号に関連するエントリを読み出すための論
理を含むテーブルと、前記テーブルから読み出されたエ
ントリに含まれる前記予測子のセットを記憶するスタッ
クと、前記テーブルから読み出された各エントリについ
て、前記各エントリに関連する前記分岐命令から次に現
れる分岐命令までを導く実行パスを識別するデータを記
憶するレジスタと、前記スタック及び前記レジスタに結
合され、前記レジスタに記憶された前記データに従って
先祖分岐命令に対応する前記スタックに記憶された前記
予測子のセットの中から予測子を選択し、前記レジスタ
に記憶された前記データが前記先祖分岐命令から次に現
れる分岐命令までの実行パスを表し、前記選択された予
測子に記憶されたデータに従って前記次に現れる分岐命
令の結果の予測を発生する予測論理とを有する分岐命令
の結果予測装置。（２０）前記テーブルの特定のエントリの各々が、前記
特定のエントリに関連する分岐命令を識別する分岐識別
フィールドを含む上記（１９）に記載の装置。（２１）前記データ処理システムが、前記次に現れる分
岐命令の結果の予測に従う前記データ処理システムによ
る推論的実行のためにメモリから命令をフェッチする命
令フェッチ論理を有する上記（１９）に記載の装置。（２２）前記アクセス信号が、前記データ処理システム
による推論的実行のためにフェッチされるメモリに記憶
された命令のブロックを識別する命令フェッチ・アドレ
スの一部である上記（２１）に記載の装置。（２３）前記テーブルの特定のエントリの各々が、前記
特定のエントリに関連する分岐命令の目標アドレスの一
部を識別する目標アドレス・フィールドを含み、前記次
に現れる分岐命令の結果の予測がその分岐命令が選択さ
れるとして示される場合、前記命令フェッチ論理が、前
記次に現れる分岐命令に関連するエントリの前記目標ア
ドレス・フィールドにより識別される前記メモリ内の場
所から命令のブロックをフェッチする上記（２２）に記
載の装置。（２４）各エントリが複数の分岐命令に関連する上記
（１９）に記載の装置。（２５）前記アクセス信号が、前記データ処理システム
により実行される分岐命令を識別する分岐命令アドレス
の一部である上記（２４）に記載の装置。（２６）前記テーブルのエントリと前記複数の分岐命令
の特定の分岐命令の各々との間の関係が、前記特定の分
岐命令の前記分岐命令アドレスの一部を変換することに
より決定される上記（２５）に記載の装置。（２７）前記次に現れる分岐命令の解明状態に従って、
前記テーブルから読み出された前記エントリに含まれる
前記予測子のセット内の前記選択された１の予測子を更
新する更新論理を有する上記（１９）に記載の装置。

【図面の簡単な説明】

【図１】パイプライン・プロセッサの各段階を表す図で
ある。

【図２】汎用的プロセッサの機能構成図である

【図３】プロセッサのメモリ・システム１０２に記憶さ
れる命令シーケンスを表す図である。

【図４】本発明による分岐ヒストリ・テーブル（ＢＨ
Ｔ）、ＢＨＴ予測スタック、ＢＨＴ予測更新論理及び分
岐解明記録レジスタを含む分岐ユニットの機能構成図で
ある。

【図５】本発明による図４のＢＨＴの構造を示す図であ
る。

【図６】本発明による図４のＢＨＴの構造を示す図であ
る。

【図７】本発明による図４のＢＨＴの構造を示す図であ
る。

【図８】図４のＢＨＴ予測スタックを表す図である。

【符号の説明】

１００プロセッサ１０２メモリ１０４命令キャッシュ１０６データ・キャッシュ１０８命令フェッチ・ユニット１１０デコード・ユニット１１２分岐ユニット１１４ディスパッチ・ユニット１１６機能ユニット１１８データ・フェッチ・ユニット１２０レジスタ・ファイル１２２完了ユニット２０１ＢＨＴ２０３分岐解明記録レジスタ２０５分岐予測スタック２０７予測論理２０９分岐解明論理３０８予測子３１０デコーダ３１４ヒット認知及び選択論理

───────────────────────────────────────────────────── フロントページの続き (72)発明者ルドルフ・エヌ・レクトシャフェンアメリカ合衆国10583、ニューヨーク州、スケアスデイル、インネス・ロード 24

Claims

【特許請求の範囲】

【請求項１】メモリに記憶された命令のシーケンスが少
なくとも１つのプロセッサ・ユニットにより実行されか
つ前記メモリに記憶された命令のシーケンスが１又は複
数の分岐命令を含むデータ処理システムにおいて分岐命
令の結果を予測する装置であって、各エントリがそれぞれ分岐命令に関連しかつその関連す
る分岐命令から終端の分岐命令までを導く実行パスに対
応する予測子のセットを含み、かつ各予測子が前記対応
する実行パスの終わりにおける前記終端の分岐命令の結
果を予測するためのデータを記憶している、複数のエン
トリを記憶するテーブルと、前記テーブルへ与えられるアクセス信号に関連するエン
トリを前記テーブルから読み出す手段と、前記テーブルから読み出された前記エントリに関連する
前記分岐命令から次に現れる分岐命令までを導く実行パ
スを決定する手段と、前記実行パスに対応するテーブルから読み出された前記
エントリに含まれる前記予測子のセットの中から予測子
を選択する手段と、前記選択された予測子に記憶されたデータに従って前記
次に現れる分岐命令の結果の予測を発生する手段とを有
する分岐命令の結果予測装置。
【請求項２】前記テーブルの特定のエントリの各々が、
前記特定のエントリに関連する分岐命令を識別する分岐
識別フィールドを含む請求項１に記載の装置。
【請求項３】前記データ処理システムが、前記次に現れ
る分岐命令の結果の予測に従う前記データ処理システム
による推論的実行のためにメモリからデータをフェッチ
するデータ・フェッチ手段を有する請求項１に記載の装
置。
【請求項４】前記アクセス信号が、前記データ処理シス
テムによる推論的実行のためにフェッチされるメモリに
記憶された命令のブロックを識別する命令フェッチ・ア
ドレスの一部である請求項３に記載の装置。
【請求項５】前記テーブルの特定のエントリの各々が、
前記特定のエントリに関連する分岐命令の目標アドレス
の一部を識別する目標アドレス・フィールドを含み、前
記次に現れる分岐命令の結果の予測がその分岐命令が選
択されるとして示される場合、前記データ・フェッチ手
段が、前記次に現れる分岐命令に関連するエントリの前
記目標アドレス・フィールドにより識別される前記メモ
リ内の場所からデータをフェッチする請求項３に記載の
装置。
【請求項６】各エントリが複数の分岐命令に関連する請
求項１に記載の装置。
【請求項７】前記アクセス信号が、前記データ処理シス
テムにより実行される分岐命令を識別する分岐命令アド
レスの一部である請求項６に記載の装置。
【請求項８】前記テーブルのエントリと前記複数の分岐
命令の特定の分岐命令の各々との間の関係が、前記特定
の分岐命令の前記分岐命令アドレスの一部を変換するこ
とにより決定される請求項７に記載の装置。
【請求項９】前記次に現れる分岐命令の解明状態に従っ
て、前記テーブルから読み出された前記エントリに含ま
れる前記予測子のセット内の前記選択された１の予測子
を更新する手段を有する請求項１に記載の装置。
【請求項１０】メモリに記憶された命令のシーケンスが
少なくとも１つのプロセッサ・ユニットにより実行さ
れ、前記メモリに記憶された命令のシーケンスが１又は
複数の分岐命令であるデータ処理システムにおいて分岐
命令の結果を予測する方法であって、各エントリがそれぞれ分岐命令に関連しかつその関連す
る分岐命令から終端の分岐命令までを導く実行パスに対
応する予測子のセットを含み、かつ各予測子が前記対応
する実行パスの終わりにおける前記終端の分岐命令の結
果を予測するためのデータを含む複数のエントリをテー
ブルに記憶するステップと、前記テーブルへ与えられるアクセス信号に関連するエン
トリを前記テーブルから読み出すステップと、前記テーブルから読み出された前記エントリに関連する
前記分岐命令から次に現れる分岐命令までを導く実行パ
スを決定するステップと、前記実行パスに対応するテーブルから読み出された前記
エントリに含まれる前記予測子のセットの中から予測子
を選択するステップと、前記選択された予測子に記憶されたデータに従って前記
次に現れる分岐命令の結果の予測を発生するステップと
を有する分岐命令の結果予測方法。
【請求項１１】前記テーブルの特定のエントリの各々
が、前記特定のエントリに関連する分岐命令を識別する
分岐識別フィールドを含む請求項１０に記載の方法。
【請求項１２】前記次に現れる分岐命令の結果の予測に
従う前記データ処理システムによる推論的実行のために
メモリからデータをフェッチするステップを有する請求
項１０に記載の方法。
【請求項１３】前記アクセス信号が、前記データ処理シ
ステムによる実行のためにフェッチされるメモリに記憶
された命令のブロックを識別する命令フェッチ・アドレ
スの一部である請求項１２に記載の方法。
【請求項１４】前記テーブルの特定のエントリの各々
が、前記特定のエントリに関連する分岐命令の目標アド
レスの一部を識別する目標アドレス・フィールドを含
み、前記次に現れる分岐命令の結果の予測がその分岐命
令が選択されるとして示される場合、前記データ・フェ
ッチ手段が、前記次に現れる分岐命令に関連するエント
リの前記目標アドレス・フィールドにより識別される前
記メモリ内の場所からデータがフェッチされる請求項１
２に記載の方法。
【請求項１５】各エントリが複数の分岐命令に関連する
請求項１０に記載の方法。
【請求項１６】前記アクセス信号が、前記データ処理シ
ステムにより実行される分岐命令を識別する分岐命令ア
ドレスの一部である請求項１５に記載の方法。
【請求項１７】前記テーブルのエントリと前記複数の分
岐命令の特定の分岐命令の各々との間の関係が、前記特
定の分岐命令の前記分岐命令アドレスの一部を変換する
ことにより決定される請求項１６に記載の方法。
【請求項１８】前記次に現れる分岐命令の解明状態に従
って、前記テーブルから読み出された前記エントリに含
まれる前記予測子のセット内の前記選択された１の予測
子を更新するステップを有する請求項１０に記載の方
法。
【請求項１９】メモリに記憶された命令のシーケンスが
少なくとも１つのプロセッサ・ユニットにより実行され
かつ前記メモリに記憶された命令のシーケンスが１又は
複数の分岐命令を含むデータ処理システムにおいて分岐
命令の結果を予測する装置であって、各エントリがそれぞれ分岐命令に関連しかつその関連す
る分岐命令から終端の分岐命令までを導く実行パスに対
応する予測子のセットを含み、各予測子が前記対応する
実行パスの終わりにおける前記終端の分岐命令の結果を
予測するためのデータを記憶している複数のエントリを
記憶し、かつ、与えられるアクセス信号に関連するエン
トリを読み出すための論理を含むテーブルと、前記テーブルから読み出されたエントリに含まれる前記
予測子のセットを記憶するスタックと、前記テーブルから読み出された各エントリについて、前
記各エントリに関連する前記分岐命令から次に現れる分
岐命令までを導く実行パスを識別するデータを記憶する
レジスタと、前記スタック及び前記レジスタに結合され、前記レジス
タに記憶された前記データに従って先祖分岐命令に対応
する前記スタックに記憶された前記予測子のセットの中
から予測子を選択し、前記レジスタに記憶された前記デ
ータが前記先祖分岐命令から次に現れる分岐命令までの
実行パスを表し、前記選択された予測子に記憶されたデ
ータに従って前記次に現れる分岐命令の結果の予測を発
生する予測論理とを有する分岐命令の結果予測装置。
【請求項２０】前記テーブルの特定のエントリの各々
が、前記特定のエントリに関連する分岐命令を識別する
分岐識別フィールドを含む請求項１９に記載の装置。
【請求項２１】前記データ処理システムが、前記次に現
れる分岐命令の結果の予測に従う前記データ処理システ
ムによる推論的実行のためにメモリから命令をフェッチ
する命令フェッチ論理を有する請求項１９に記載の装
置。
【請求項２２】前記アクセス信号が、前記データ処理シ
ステムによる推論的実行のためにフェッチされるメモリ
に記憶された命令のブロックを識別する命令フェッチ・
アドレスの一部である請求項２１に記載の装置。
【請求項２３】前記テーブルの特定のエントリの各々
が、前記特定のエントリに関連する分岐命令の目標アド
レスの一部を識別する目標アドレス・フィールドを含
み、前記次に現れる分岐命令の結果の予測がその分岐命
令が選択されるとして示される場合、前記命令フェッチ
論理が、前記次に現れる分岐命令に関連するエントリの
前記目標アドレス・フィールドにより識別される前記メ
モリ内の場所から命令のブロックをフェッチする請求項
２２に記載の装置。
【請求項２４】各エントリが複数の分岐命令に関連する
請求項１９に記載の装置。
【請求項２５】前記アクセス信号が、前記データ処理シ
ステムにより実行される分岐命令を識別する分岐命令ア
ドレスの一部である請求項２４に記載の装置。
【請求項２６】前記テーブルのエントリと前記複数の分
岐命令の特定の分岐命令の各々との間の関係が、前記特
定の分岐命令の前記分岐命令アドレスの一部を変換する
ことにより決定される請求項２５に記載の装置。
【請求項２７】前記次に現れる分岐命令の解明状態に従
って、前記テーブルから読み出された前記エントリに含
まれる前記予測子のセット内の前記選択された１の予測
子を更新する更新論理を有する請求項１９に記載の装
置。