JPH06324865A

JPH06324865A - マルチ予測型分岐予測機構

Info

Publication number: JPH06324865A
Application number: JP3252872A
Authority: JP
Inventors: Philip G Emma; フィリップ・ジョージ・エマ; Joshua W Knight; ジョシュア・ウィルソン・ナイト; James H Pomerene; ジェームス・ハーバート・ポメレーヌ; Thomas R Puzak; トーマス・ロバーツ・プザック; Rudolph N Rechtschaffen; ルドルフ・ネイサン・リヒトシャーフェン; James R Robinson; ジェームス・ロバート・ロビンソン; Van Albert J Norstrand; アルバート・ジェームス・バン・ノーストランド，ジュニア
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-10-09
Filing date: 1991-09-05
Publication date: 1994-11-25
Anticipated expiration: 2011-03-04
Also published as: EP0480193A2; US5353421A; EP0480193A3; JPH0820950B2

Abstract

(57)【要約】【目的】条件付き分岐の結果を予測するマルチ予測型
分岐予測機構であり、分岐履歴テーブルの利点と、デコ
ード履歴テーブルの利点とを組合せてコンピュータ性能
の向上を図る。【構成】マルチ予測型分岐予測機構によって、条件付
き分岐の各々を、少なくとも２回予測するに当たり、最
初、パイプラインの命令フェッチ段階中に予測し、次
に、パイプラインのデコード段階中に予測する。この機
構によって、少なくとも２つの異なった分岐予測機構を
利用し、これらは互いに独立した機構である。一組のル
ールを利用して、これら予測における差を解決する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データ処理の分野に関
するもので、特に、コンピュータのプロセッサで採用さ
れまたは採用されない条件付き分岐の結果を予測する機
構に関するものである。

【０００２】

【従来の技術】高性能なプロセッサの大部分は、パイプ
ラインを、性能の向上のための手段として利用してい
る。このようなパイプラインによってプロセッサを別個
の構成要素に分割することができ、この各構成要素は、
命令実行の異なった段階の遂行を引き受けている。例え
ば、図１は、プロセッサのパイプラインを構成する主要
構成要素を示すものである。これら構成要素は、命令フ
ェッチ（ステージＩ）、命令デコードおよびアドレス生
成（ステージII）、オペランド・フェッチ（ステージII
I ）、命令実行（ステージIV）および結果の格納（ステ
ージＶ）である。各命令はこのパイプラインに入り、理
想的には、パイプラインの各ステージにおいて、１サイ
クルをついやす。各命令はパイプラインを通るのに５サ
イクルを必要とする。しかしながら、パイプラインを満
杯な状態で維持できるならば、プロセッサの各構成要素
（パイプライン・ステージ）を異なった命令に関してそ
れぞれ異なったパイプライン・ステージにおいて能動的
に作動させることができ、更に、１つの命令をサイクル
毎に完了させることができる。しかし、パイプラインを
満杯な状態で維持することは困難な作業である。パイプ
ラインではブレーク、即ち破壊が頻繁に起こってしま
い、この結果としてアイドル・サイクルが生じ、これに
よって、命令の実行が遅延してしまう。

【０００３】分岐命令は、パイプラインの破壊の主要原
因の１つである。この分岐命令によって、一時的な不確
実性がパイプライン中にもたらされる。その理由は、こ
のパイプラインを満杯の状態で維持するために、プロセ
ッサは、２つの可能な命令の内どちらが次のパイプライ
ンに導入されるかを推測する必要がある。即ち、フォー
ルスルー命令または分岐の目標のどちらかである。高性
能プロセッサの大部分によれば、実行する前に分岐の結
果を推定し、次に、推定されたパスへの命令をフェッチ
しデコードする（命令は採用されるかまたは採用されな
い）。

【０００４】分岐の結果を予測することによって、プロ
セッサは、このパイプラインを命令で満杯に維持するこ
とができると共に、この分岐の結果を正しく推測する場
合には、パイプラインの破壊を回避できる。しかし、こ
の分岐を誤って推測した場合に、例えば、実際には分岐
が採用されるのに不採用であると推測すると、この分岐
に続くパイプラインに導入されるあらゆる命令はキャン
セルされ、パイプラインが正しい命令で再び開始され
る。

【０００５】いくつかの特許は分岐の予測機構に関する
もので、それらには、それぞれ或る利点と欠点とが存在
する。これら特許の多くは、大部分の分岐が確実に採用
または不採用であり、個々に取扱われた場合に、確実
に、同一目標アドレスへ分岐するという観測に基いたも
のである。例えば、米国特許第４，４７７，８７２号明
細書によれば、各条件付き分岐を動作の以前の性能に基
いて予測する機構が記載されている。採用または不採用
の条件付き分岐の各々の動作を記録するテーブルが設け
られている。このテーブルの各エントリは、１または０
の１ビット値から構成され、この分岐が採用または不採
用であるかを表している。分岐を構成するアドレスビッ
トの部分集合を利用して、このテーブルを、条件付き分
岐をデコードする毎に調べる。このテーブルは“デコー
ド履歴テーブル（ＤＨＴ）”と呼ばれており、組合せロ
ジックによってこのテーブルで見つけた値から推測を決
定する。分岐目標を予測することはしない。その理由と
しては、これはデコード時に既知なものであるから、分
岐の結果が丁度、予測されるからである。このＤＨＴを
用いることによって、条件付き分岐のみの結果が予測さ
れる。その理由は、無条件分岐が一旦デコードされる
と、その結果は明らかになるからである。

【０００６】米国特許第３，３２５，７８５号明細書に
よれば、分岐の種類と、分岐を採用するかどうかの統計
学的経験とに基いて、分岐の結果を予測する機構が記載
されている。他の分岐ストラテジによれば、分岐が完全
に実行されるまでパイプラインを保持することが記載さ
れている。したがって、採用または不採用の分岐の結果
が既知となり、更に、正しい命令をパイプラインを介し
てフェッチし処理できる。しかしながら、このようなス
トラテジでは、分岐当り数サイクルのパイプライン遅延
（アイドル・サイクル）が生じてしまう。

【０００７】また、米国特許第４，１８１，９４２号明
細書によれば、特別な分岐命令をプロセッサで利用し
て、分岐の種類、即ち、内部レジスタの状態によって決
定される条件付きまたは無条件を指示する機構が開示さ
れている。この特殊な分岐命令は、プログラム・ループ
の最後におけるプログラム制御に、およびループ外への
無条件分岐に利用される。

【０００８】更に、米国特許第４，２００，９２７号明
細書によれば、命令ストリーム中に存在する各分岐の予
測に基いて、複数命令バッファをアドレスし、充満させ
る機構が記載されている。各命令バッファへの命令のプ
リフェッチ、および命令をデコーダにゲートするための
命令バッファの１つの選択は、ロジックによって制御す
る。このロジックは、各命令バッファに格納されている
命令ストリームおよび分岐の状態を追跡する。分岐を、
これらの種類に基いて推測し、条件付き分岐命令の実行
に応答して、命令実行ユニットからの結果信号によって
種々のポインタの設定を制御して、新しい命令ストリー
ムを命令バッファに割り当て、分岐実行の結果に基いて
命令ストリームを割り当て解除しまたはリセットする。

【０００９】更に、有効なストラテジが米国特許第３，
５５９，１８３号明細書に記載されている。この特許に
よれば、テーブルに、最近実行した一組の分岐のアドレ
ス（分岐の目標アドレスが続く）を記録する機構が開示
されている。このテーブルを分岐履歴テーブル（ＢＨ
Ｔ）と称している。エントリは、採用された各分岐に対
して形成されており、この分岐は、プロセッサが出会う
条件付きおよび無条件である。このテーブル（ＢＨＴ）
は、パイプラインの命令フェッチ（Ｉ−フェッチ）段階
中にアクセスされる（図１のステージＩ）。このことに
よって、ＢＨＴは、分岐命令がデコードされてしまう前
にも、分岐の結果を予測できるようになる。プロセッサ
によって実行された各命令フェッチをＢＨＴに保管され
た各分岐アドレスに対して比較し、一致した場合に分岐
は採用されたものと仮定し、またテーブル中の目標アド
レスは次の命令フェッチ・アドレスとなる。原則的に、
このテーブルで見つけられた命令フェッチ・アドレス
は、分岐命令がそのアドレスで見つけられ、この分岐が
ＢＨＴに保管された目標アドレスによって特定化された
同一のアドレスに採用されることを予測する。このＢＨ
Ｔ内でエントリが見つからない場合には、命令フェッチ
・アドレス（フェッチされる命令ダブルワードのアドレ
ス）内に分岐が存在しないものと仮定されるか、また
は、分岐が存在すれば、採用されないものと仮定され
る。パイプラインの命令フェッチ段階中に、このＢＨＴ
をアクセスすることによって、できるだけ早期に、採用
された分岐を見つけるようにすると共に、分岐命令アド
レスをデコードする前にもこの目標アドレスをフェッチ
するようにする。理想的には、このことによって、パイ
プライン化プロセッサで採用された分岐によって発生す
るあらゆるパイプライン遅延を回避するようになる。代
表的には、プロセッサは、その目標をフェッチする前に
分岐がデコードされるまで待機する場合に、パイプライ
ンの破壊が起こるようになる（採用された各分岐に対し
て）。その理由は、キャッシュまたはメモリから分岐の
目標をフェッチするには、数サイクル必要とするからで
ある。分岐をデコードする以前にも、この分岐の目標を
フェッチすることによって、ＢＨＴにより、前述した分
岐予測機構に対して極めて大きな性能の改善が達成され
るようになる。

【００１０】米国特許第４，６７９，１４１号明細書に
よれば、米国特許第３，５５９，１８３号明細書に記載
のように、ＢＨＴを改善する分岐予測機構が記載されて
いる。このＢＨＴを２つの部分、即ち、アクティブ領域
およびバックアップ領域に分割することによって改良し
ている。このアクティブ領域には、プロセッサが出会っ
た小さな部分集合の分岐に対するエントリが含まれてお
り、更に、バックアップ領域には、他の分岐エントリの
すべてが含まれている。このバックアップ領域からエン
トリをアクティブ領域へ、プロセッサがこれらエントリ
を使用するに先立って移動させる機構が記載されてい
る。このアクティブ領域の小さなサイズによって、これ
をプロセッサの物理的なレイアウト中に、迅速に、且
つ、最適に配置することができる。

【００１１】前述した従来の特許を２つのカテゴリに分
割することが可能である。即ち、一方のカテゴリは、命
令フェッチ時に、分岐に対する予測を行う。他方のカテ
ゴリは、デコード時に、この予測を行うものである。前
述の米国特許第４，２００，９２７号明細書、第４，１
８１，９４２号明細書、第３，３２５，７８５号明細書
および第４，４７７，８７２号明細書においては、各分
岐をパイプラインのデコード段階（図１のステージＩ
Ｉ）中に発見し、推測している。このような理由のため
に、条件付き分岐のみがＤＨＴによって推測即ち予測さ
れる必要がある。その理由は、デコード時の後に、無条
件分岐のすべての分岐確実性が既知となるからである。
これら特許を、“デコード時分岐予測機構”と称するも
のとする。これら予測機構のいずれにおいても、分岐の
目標を予測するものではない。即ち、分岐がデコードさ
れた時に、この目標が正確にわかるからである。これに
対して、残りの特許においては、パイプラインの命令フ
ェッチ段階（図１のステージＩ）中に、分岐予測が行わ
れ、この予測中に、条件付きおよび無条件の採用分岐の
すべてに対する結果を予測する必要があり、採用した分
岐の目標を予測する必要がある。これら残余の特許を、
“命令フェッチ時分岐予測機構”と称する。これら命令
フェッチ時分岐予測機構の各々は、デコード時分岐予測
機構のものに比べて極めて大きなハードウェアを与える
が、性能が改善されて、それらの実行を保証するように
なる。

【００１２】説明のために、ＢＨＴとＤＨＴを実行する
のに必要なハードウェアの量の簡単な比較を行う。先ず
初めに、ＢＨＴとＤＨＴとによって使用される各テーブ
ルのハードウェアの量について比較する。ＢＨＴの各エ
ントリは２つのアドレス、即ち、予測した目標アドレス
に続く分岐アドレスから構成されるのに対して、ＤＨＴ
の各エントリは単一ビットにより表され、これによっ
て、分岐が採用または不採用であるかを表している。従
って、ＢＨＴ中の各アドレスが３２ビットとして表現さ
れるならば、１ｋエントリを有するＢＨＴは１０２４個
の２つのアドレス対（即ち、１０２４×６４ビット）よ
り構成され、ここでは各エントリが６４ビットで表され
る。次に、各機構の相対サイズについて比較すると、１
ｋエントリで構成されるＢＨＴは、１ｋエントリで構成
されるＤＨＴに比べて実際に、６４倍も大きくなる。

【００１３】

【発明が解決しようとする課題】従って、本発明の目的
は、各分岐の結果を複数回だけ予測し、一致しない場合
に、予測を決定する機構を提供することにある。

【００１４】また、本発明の他の目的は、コンピュータ
における条件付き分岐の結果を予測するマルチ予測型分
岐予測機構であって、分岐履歴テーブルの利点と、デコ
ード履歴テーブルの利点とを組合せてコンピュータの性
能を向上させる一方、同時に、向上した性能に通常は関
連するハードウェア・オーバーヘッドを最小化する機構
を提供することにある。

【００１５】

【課題を解決するための手段】本発明のマルチ予測型分
岐予測と称する分岐予測機構によって、各分岐を少なく
とも２回だけ予測し、最初の予測は、パイプラインの命
令フェッチ段階中であり、次の予測は、パイプラインの
デコード段階中である。この機構は、２つの異なった分
岐予測機構を利用し、各々は、互いに独立した機構であ
る。この機構では、一組のルールを利用して、これら２
つの独立の分岐予測機構が不一致である時は、何時でも
この分岐を予測する。この命令フェッチタイム予測機構
に対してＢＨＴが好適に選択され、デコードタイム予測
機構に対してはＤＨＴが好適に選択される。各機構は、
好適なものである。その理由は、各機構の予測精度はそ
れぞれ極めて高いものであると共に、組合せた場合に、
更に、高い推測精度比率が得られる。例えば、４ｋエン
トリから成るＢＨＴまたはＤＨＴに対して、プロセッサ
により遭遇した分岐の８０％以上の結果を予測に成功す
ることはまれなことではない。しかし、他のデコードタ
イムまたは命令フェッチ機構を所望に応じて置換するこ
とができる。

【００１６】２個またはそれ以上の分岐予測機構をパイ
プライン化したプロセッサ中に共存できることは、直観
できるものではない。概念的な作業を実行することは、
予測が互いに相異した場合に、これを解決するための一
組のルールを利用することである。本発明の利点は、単
一の予測機構だけを利用した時に比べて、高度な正しい
予測率が達成されると共に、これら比較的少ないハード
ウェア・オーバーヘッドによって実現できることであ
る。

【００１７】

【実施例】標準のＢＨＴまたはＤＨＴを有するプロセッ
サの動作を、マルチ予測型分岐予測による本発明の動作
に対する前置きとして以下に説明する。

【００１８】前述したように、このＢＨＴは、その分岐
を高いパーセンテージで正しく予測する必要があり、そ
の理由は、予測が誤った時に、厳しいペナルティが課せ
られているからである。通常、このＢＨＴによって生じ
た予測誤りの多くは、分岐の実行後に発見される。も
し、各誤りがもっと初期の段階で予測できたならば、数
サイクル分の遅延を回避できる。パイプラインの命令フ
ェッチ段階中に、このＢＨＴによってその予測を行い、
分岐が最終的に実行されるまで数サイクル必要となるこ
とが知られている。ＤＨＴを利用してプロセッサによっ
て処理される条件付き分岐の各々の結果を、再予測する
に当り、ＢＨＴによって生じる潜在予測誤りを、パイプ
ラインのデコード段階中に検出することができる。そし
て、このプロセッサを正しい命令ストリームに再度、向
かわせることによって、数サイクルの遅延が回避でき
る。

【００１９】この予測プロセスについて以下説明する。
ＢＨＴは上述したように多く使用され、一方、ＤＨＴを
利用して、ＢＨＴによって行われた分岐予測を確認す
る。これら予測が異なるような或る場合において、ＢＨ
Ｔによって行われた予測を無効する。両方の予測が一致
した場合においては、例え、両方が採用または不採用で
あっても、いずれの分岐予測を無効にする必要はないこ
とは明らかである。しかしながら、分岐に対する予測が
異なった場合に、採用または不採用となる分岐の結果に
関する決定を行う必要がある。例えば、ＢＨＴによる初
期の予測が、分岐を不採用とする場合と、ＤＨＴによっ
て分岐を採用するであろうと予測する場合のケースにつ
いて考える。

【００２０】即ち、プロセッサの処理による命令フェッ
チが、ＢＨＴに含まれているすべての“分岐アドレス”
エントリをミスしたものと考える。このことは、命令に
アクセスしたデータ中に含まれた採用分岐が存在しない
ことを示している。このことは、すべての将来の命令フ
ェッチを“フォールスルー”パスに向かわせる。デコー
ダによってこのデータ内で条件付き分岐を発見させ、Ｄ
ＨＴのエントリによって分岐が採用されたことを表す。
この事象は、ＤＨＴによって予測されたように“分岐採
用パス”をフェッチする必要があることを表す。このよ
うな事象のシーケンスに対して、ＢＨＴによって分岐の
結果を誤って予測したものと仮定し、更に、ＤＨＴによ
って行われた予測は正しいものであるものと仮定する。
従って、このことによってデコーダは、“予測された目
標アドレス”パスからの命令をデコードするように指示
される。

【００２１】上述した一例において、ＤＨＴによって行
われた予測が、ＢＨＴによって行われた予測を無効にで
きる以下のいくつかの理由が存在する。（ａ）エントリの数量において、より大きなＤＨＴを小
さいＢＨＴと一緒に利用でき、このＤＨＴのサイズは、
ＢＨＴの全体のサイズよりかなり小さいままとする。こ
のことによって、ＤＨＴが、ＢＨＴの分岐より相当多く
の分岐からの結果を覚えることができ、ＤＨＴをＢＨＴ
に比べて大幅に小さなままとすることができる。例え
ば、４ｋエントリを有するＤＨＴは、１ｋエントリのＢ
ＨＴのサイズの僅か１／１６のままである（４０９６ビ
ット／（１０２４×６４）ビット）。（ｂ）ＢＨＴは、すべての“採用分岐”情報の保管場所
として機能し、その一定サイズ制限のために、キャッシ
ュの場合と同じヒットおよびミス統計に悩まされる。命
令フェッチ・アドレスは、ヒットとなるべきＢＨＴに含
まれる分岐アドレスの１つに一致しなければならず、一
方、ＤＨＴを、分岐のアドレスビットの部分集合を利用
してアクセスし、常時、予測できるようにする。（ｃ）ＢＨＴは、条件付きおよび無条件のすべての採用
分岐を記録する必要があるのに対して、ＤＨＴは、条件
付き分岐の結果のみを記録する。すべての無条件分岐を
デコーダによって正確に予測でき、これら分岐はこれら
分岐の結果をＤＨＴ情報の一部分として記憶しておく必
要がない。従って、ＢＨＴは、予測するための別個の分
岐を、ＤＨＴに比べて更に多く有するようになる。この
ことによって、有限のＢＨＴディレクトリに関連した
“キャッシュ状”ミス現象を悪化させる。（ｄ）すべての“新しい”（最初の）採用分岐は、ＢＨ
Ｔに対してミスするものとなるが、その大きいサイズの
ために、ＤＨＴ中に、依然含まれるようになる。これら
“新しい”分岐によって、分岐の初期実行を、またはそ
の有限のサイズのためにＢＨＴから古い分岐の再実行を
表すことができる。これら条件によって、ＤＨＴが、デ
コーダを条件付き分岐に正確に再指定できるようにな
り、これら分岐は実際には採用され、ＢＨＴによって
“不採用”なように予測されている。

【００２２】命令フェッチ時にＢＨＴを用い、更にデコ
ード時にＤＨＴを用いることによって、各分岐を２回予
測することにより、プロセッサの性能を実際に増大する
ことができ、マシーンのハードウェア全体を減少させら
れる。例えば、１ｋエントリを有するＢＨＴと協動して
作動する１６ｋエントリを有するＤＨＴは、２ｋエント
リを有するＢＨＴよりかなり少ないハードウェアを与え
る。また、１ｋＢＨＴと１６ｋＤＨＴとによって分岐の
大部分のパーセンテージを正確に予測でき、この結果、
大きなＢＨＴに亘って性能を増大できる。

【００２３】図面を参照しながら説明した上述の説明は
基本的なものであり、従って、当業者であれば、このプ
ロセッサの設計を確立する実際の特徴の大部分を簡略化
または省略できることは容易に理解できるであろう。例
えば、十分に連合されたディレクトリを、実際の実行に
おいて必要な従来のセット連合ルックアップより、むし
ろ、ＢＨＴに対して選択する。ＢＨＴに関する更に詳細
な説明は、米国特許第３，５５９，１８３号明細書およ
び第４，６７９，１４１号明細書に開示されており、Ｄ
ＨＴに関するものは、米国特許第４，４７７，８７２号
明細書に開示されている。

【００２４】また、図面において、類似の参照番号は、
同一または類似の部分を表すものとする。図２は、ＢＨ
Ｔを有するプロセッサの主要構成を示す。各構成要素の
動作は、図１に示した各パイプライン段階に従って詳述
されている。各段階は別個に記載されているが、いかな
るパイプライン・プロセッサにおけると同様に、パイプ
ラインのすべての段階は並列に起こるものである。

【００２５】命令はメモリ１０に記憶されており、この
メモリ１０からフェッチされ、キャッシュ１３に記憶さ
れる。これらは、周知の機構に従って行われる。パイプ
ラインの命令フェッチ段階中に、命令バッファ１１はＢ
ＨＴ１２に対して、“命令バッファは満杯でない”信号
を介して他の命令フェッチに対してスペースが利用でき
ることを知らせる。ＢＨＴ１２は次の命令フェッチを発
生し、アドレスをキャッシュ１３に送る。次に、Ｉ−フ
ェッチ・セグメントをキャッシュからパス１４を介して
戻す。

【００２６】デコード段階中に、ＢＨＴ１２によって、
命令バッファ１１へパス１５を介して、信号が与えら
れ、これにより“次命令レジスタ”１６に適当な次の命
令がロードされる。このロードされた命令は、前にロー
ドされた命令の直後の命令、即ち、“次の順序命令”、
または、“分岐目標命令”とすることができ、これは、
ＢＨＴから送られた情報の内容に応じて決定される。

【００２７】命令デコード・レジスタ１７を次命令レジ
スタ１６からロードする。この命令をデコードし、オペ
レーション・コード（オペコード）および実行情報を組
立てる。命令をデコードした後に、実行情報をこれが実
行されるまで保持される実行ユニット１８に送る。オペ
ランドが命令によって要求されると、必要情報（ベース
・レジスタ値、インデックス・レジスタおよび変位）が
アドレス生成部１９へ送られる。アドレス生成部１９の
出力はオペランドのアドレスである。次に、このアドレ
スがキャッシュ１３へ送られる。続いて、このキャッシ
ュ１３によってオペランド情報がパス２１を介して実行
ユニット１８へ戻される。

【００２８】命令は、必要なデータがキャッシュから得
られるまで、実行ユニット１８で待機する。ここで、命
令は実行され、その実行結果が要求通りに保管される。
分岐が実行された場合に、ＢＨＴ更新情報が実行ユニッ
ト１８からパス２２を介してＢＨＴ１２に戻される。Ｂ
ＨＴ更新情報は、ＢＨＴが各分岐の出力を正確に予測す
ることを確実ならしめるために送られる。最後に、エン
ドオペ（終了オペレーション）２３を発行して、命令が
完全に完了した場合に、この時点を正しい時間でマーク
する。

【００２９】この動作と並行して、デコード・レジスタ
１７によって生成された命令長情報をアドレス加算器２
５に送る。ここで、この情報と、命令カウンタ（ＩＣ）
レジスタ２６からの値と組合せることにより、次命令ア
ドレスを形成する。アドレス加算器２５からの出力を、
更新命令カウンタ・レジスタ２７に送ると共に、ライン
２８を介してＢＨＴ１２に送る。更新命令カウンタ・レ
ジスタ２７によって、次のサイクルでデコードされる命
令の値を保持する。次に、この事象シーケンスを次のサ
イクルでプロセッサによって繰返す。

【００３０】ＢＨＴについて更に詳しい説明が図３に開
示されている。基本的には、このＢＨＴを利用して、プ
ロセッサの命令フェッチ・ポリシィを効果的に指示し、
正しい命令、次の順序または分岐目標をデコーダに指示
することによって分岐予測を精度改善することを行って
いる。これを実行するために、プロセッサによって形成
した各命令フェッチのアドレスを検査し、命令フェッチ
・セグメント内に含まれている採用分岐が何時存在する
かを検出する必要がある。各命令フェッチを、命令フェ
ッチ・アドレス・レジスタ３１に保持する。このアドレ
スを比較部３３によってＢＨＴディレクトリ３２で保持
した各分岐アドレスに対して比較する。通常、命令フェ
ッチ・セグメントの各々は、１個以上の命令を含んでい
る。現状のマシーンでは、命令フェッチ・セグメントは
数ワード長（即ち、８バイトのダブル（２倍）ワードま
たは１６バイトのクワド（４倍）ワードである。従っ
て、数個の命令が各命令フェッチ・セグメント内に存在
する可能性がある。ＢＨＴに含まれている分岐アドレス
に一致する命令フェッチ・アドレスを、以下“ＢＨＴヒ
ット”と称する。同様に、“ＢＨＴミス”と称する用語
を以下のように用いる。即ち、ＢＨＴ内に含まれたすべ
ての分岐アドレスと一致しない命令フェッチ・セグメン
トを意味する。即ち、命令フェッチのアドレスが、ＢＨ
Ｔディレクトリ中に保持された命令セグメントのいずれ
とも比較に失敗することである。

【００３１】命令フェッチがすべてのＢＨＴエントリを
ミスした場合に、プロセッサによって形成された次命令
フェッチアドレスは、次順序ロジック３４によって決定
されるように、“次順序”命令フェッチ・セグメントと
なる。命令フェッチ・アドレスが“ＢＨＴ中でヒット”
した場合に、プロセッサは命令ストリームを切換え、プ
ロセッサによって生成させた次命令アドレス・セグメン
トは、“ヒット”の原因となったＢＨＴエントリの目標
アドレスとなる。この新しい目標アドレスがゲート３５
に移り、更に、ＢＨＴヒットが検出された場合に、新し
い命令フェッチ・アドレスとなる。次順序命令フェッチ
は、ＢＨＴミスがゲート３６を介して検出された時に、
呼び出される。

【００３２】アドレス一致、即ち、ヒットが起こると、
分岐アドレス（ＢＡ）および目標アドレス（ＴＡ）が分
岐アドレス，目標アドレス（ＢＡ／ＴＡ）スタック３７
に保管され、この目標アドレスは、後続のサイクルにお
ける次の命令フェッチ・アドレスとなる。このＢＡ／Ｔ
Ａスタックを用いて、命令バッファからの命令を、次命
令レジスタに前以ってロードするように案内する。この
命令バッファをロードするための情報をパス１５を介し
て送る。命令バッファをロードするために用いた情報、
即ち、アドレスは、ＢＡ／ＴＡスタック３７中の最も古
いエントリの分岐アドレスと、パス２８を介して送った
次命令アドレスとを比較することによって得られる。こ
れら比較対象のアドレスが機能ブロック４１内で決めら
れたように、等しいものであれば、この次命令アドレス
は、スタック３７中のＢＡ／ＴＡ対に対する目標アドレ
スとなる。ここで、ＢＨＴが分岐の動作の予測において
正しい場合に、このことが起こるものである。このよう
に一致したＢＡ／ＴＡ対に対する目標アドレスを機能ブ
ロック４２および信号ユニット４３で保持することによ
って、パス１５上の次命令アドレスにこのアドレスを選
択する。機能ブロック４１における比較結果が等しくな
い場合に、選択が行われず、パス２８からの次命令アド
レスは、パス１５から送られる次命令アドレスとなる。
次に、このＢＡ／ＴＡ対をスタック３７から移動し、ス
タックで見出した次の最も古いＢＡ／ＴＡ対によって処
理を継続する。

【００３３】次順序論理回路３４を制御する次順序フェ
ッチの内側の最終セグメントフェッチレジスタを、目標
アドレス値でロードする。“次順序”命令フェッチが呼
び出される時は何時でも、この最終命令フェッチ・レジ
スタに保管された値を上げる（１ユニット分だけ上昇さ
せる）ことによって、次命令フェッチ・セグメントのア
ドレスとし、これは、新たな命令フェッチ・アドレスと
なる。

【００３４】前述したＢＨＴに関する説明は、ＢＨＴに
よって行われた各予測は正しいものであると仮定してい
た。しかしながら、場合によっては、ＢＨＴは誤った決
定を行うこともある。従って、更新または補正機構をこ
のＢＨＴに設ける必要がある。

【００３５】ＢＨＴによる予測誤りは、命令のアドレス
生成段階または実行段階の後に検出できる。分岐が実行
された後で発見されるＢＨＴ予測誤りによって、かなり
のパイプライン遅延が発生する。“パイプライン再始
動”信号を、実行ユニットによってＢＨＴへ送る。これ
は、採用または不採用の分岐の結果が予測した動作と異
なるものであることがわかった場合には何時でも送られ
る。ＢＨＴ補正情報と一緒に再始動情報をパス２２を介
して送る。このパイプラインを、更に早く再始動するこ
とができる。これは、パイプラインの命令デコードおよ
びＡＧＥＮ段階の後にＢＨＴ誤りを検出することによっ
て実行できる。このことによって、数サイクルのパイプ
ライン遅延を回避でき、これは分岐が実行された後、実
行ユニット中の分岐予測誤りを検出することによって達
成される。

【００３６】ＢＨＴが、分岐が無く、ＢＨＴがミスする
と予測し、デコーダが無条件分岐をデコードする時はい
つでも、ＢＨＴ予測誤りをデコード時に検出できる。こ
の情報をパス２２を介してＢＨＴに送ることもできる。

【００３７】分岐の目標アドレスを予測する場合の誤り
を、アドレス生成部１９の後に検出することができ、図
２に示したようにパス２８を介してＢＨＴ１２に得るこ
とができる。分岐がデコード部１７によってデコードさ
れた場合には、何時でも、分岐の目標アドレス（アドレ
ス生成部１９の出力）をＢＨＴ１２に送り、図３に出し
たＢＡ／ＴＡスタック３７中に保持された予測済み目標
アドレスと比較する。このロジックは図３の機能４０内
に包含されている。アドレス生成部１９からのＴＡが、
予測したＴＡと一致しない場合に補正が必要となる。Ｂ
ＨＴエントリ中に保管された目標アドレスを変化させ
て、新しい、即ち現在の分岐命令の目標アドレスを反映
させる必要がある。これら補正をパス４６を介してＢＨ
Ｔディレクトリ３２に送る。パイプライン再始動情報を
パス４５を介して送り、これを利用してＩ−フェッチ・
アドレス・レジスタ３１を再ロードし、ＢＡ／ＴＡスタ
ック３７を消去する。パイプライン再始動の効果を以下
に説明する。

【００３８】ＢＨＴ補正はまた、命令実行段階の後に検
出される。補正情報をパス２２を介して送る。ここで、
採用または不採用の各分岐の出力をＢＨＴに送り、ＢＡ
／ＴＡスタック３７に現在保有されている各分岐の予測
状態と比較する。これはユニット４７で行われる。も
し、採用した分岐を予測するのに失敗した時の誤りであ
った場合、新しいエントリがＢＨＴディレクトリ中に形
成される。この新しいＢＡ／ＴＡ情報がパス４６を介し
てＢＨＴに送られる。また、誤りは分岐が採用されると
いう予測であり、実際に、この分岐を採用しない場合
に、ＢＨＴに現在保持されているＢＡ／ＴＡエントリを
削除する必要がある。この補正情報をまたパス４６を介
してＢＨＴに送る。

【００３９】予測誤りがプロセッサで一旦、検出される
と、パイプラインは再び始動させる必要がある。例え
ば、分岐が採用されないものと予測され、分岐が実際に
採用された場合を考える。ＢＨＴの命令フェッチ方式
は、分岐の目標が決してフェッチされず、パイプライン
は、正しい命令情報がフェッチされ命令バッファに格納
されるまで、アイドル状態であるようなものである。正
しい命令がキャッシュから一旦フェッチされると、通常
のパイプラインの流れが継続されるようになる。この
“パイプライン再始動”を完了させるためには、情報を
パス４５を介して送る。再始動ロジックによって、命令
フェッチ・アドレス３１が新しい命令アドレス（この場
合、分岐の目標に相当する）でロードされる。このこと
によって命令フェッチ・シーケンスが改めて開始し得る
ようになる。この“パイプライン再始動”手順によっ
て、図２の命令バッファ１１が消去され、図３のＢＡ／
ＴＡスタック３７が空となる。次に、このプロセッサ
は、正しい命令（再始動アドレス中に含まれている）を
キャッシュからフェッチし、通常のパイプラインの流れ
が継続できる。パイプラインを再始動することのできる
方法は数種類存在する。大部分の方法は、上述した一方
法に比べて更に複雑なものである。例えば、命令バッフ
ァ１１には、すでに、正しい命令が含まれており、これ
によってパイプラインを再び始動でき、更に、これら命
令を命令バッファから僅かの遅延または全く遅延無しで
フェッチすることにより実行を継続できる。このことを
実行するために、追加ハードウェアが必要となる。しか
しながら、本実施例において、簡単な再始動手順が用い
られ、各ＢＨＴ誤りの後で、パイプラインが再び始動す
るものとする。

【００４０】ＤＨＴを有するプロセッサの動作につい
て、以下説明する。図４は、ＤＨＴを有するプロセッサ
の主要特徴部を示す。この図は、ＤＨＴ付きプロセッサ
によってＢＨＴを有するプロセッサ中に見出される特徴
の大部分が保有されていることを示している。しかしな
がら、主要な差異としては、このＤＨＴは採用または不
採用の各条件付き分岐の出力を予測するだけであり、更
に、ＢＨＴの命令フェッチ・ロジックを、“次の順序”
フェッチのみを発生することが可能な更に簡単な機構に
よって置き換えることである。

【００４１】ＤＨＴを有するプロセッサ内の構成要素の
大部分は、ＢＨＴを有するプロセッサ中で見つけられた
ものと類似の機能を有する。しかしながら、いくつかの
主要な差異が存在する。キャッシュ１３によって、命令
フェッチ情報を再び、命令バッファ１１へ送るようにす
る。命令バッファ（ＩＢ）１１は、キャッシュ１３より
戻された命令フェッチ・セグメントを保持する。これら
命令バッファを多重化することができる。マルチ命令ス
トリーム・プロセッサのように、独立のＩＢを用いて、
再始動情報（ＤＨＴによる予測が誤っている場合に、パ
イプラインを再び始動するためのもの）、命令フェッチ
情報（パイプライン中の現在の命令ストリーム用の命令
フェッチ・セグメント）および交互命令パス情報を保持
する。マルチ命令ストリーム・マルチ命令バッファ・プ
ロセッサについては、例えば、米国特許第４，２００，
９２７号明細書に詳述されている。次命令レジスタ１６
を命令バッファからロードする。この命令バッファは次
命令アドレスを利用する。このアドレスを、更新命令カ
ウンタ（更新ＩＣ）２７に入力して、どの命令を次命令
レジスタ１６にロードするかを決定する。

【００４２】命令デコード・ロジック１７は以下の出力
を発生する。

【００４３】即ち、・命令に関する実行情報と一緒に、時刻ユニットを与え
ること、・オペランド情報（ベース・レジスタ，インデックス・
レジスタ，および変位値）と一緒に、アドレス生成機能
を与えること、・アドレス加算器２５に命令長情報を与えることであ
る。

【００４４】次に、このアドレス加算器２５によって、
命令長値を命令カウンタ値２６と組合わせて、次命令ア
ドレスを生成する。次に、この値を更新命令カウンタ２
７に保管する。オペランド・アドレスをアドレス生成ユ
ニット１９で演算し、フェッチ・リクエストおよびアド
レスをキャッシュ１３へ送る。これらオペランドをパス
２１を介して実行ユニット１８へ戻す。ここでは、命令
が実行されて、その結果が格納される。次にエンドオペ
・ユニット２３は命令の完了を知らせる。

【００４５】デコーダ１７によって、無条件分岐を検出
するものとする。この分岐の目標アドレス（これは命令
である）をキャッシュ１３からフェッチし、この目標命
令をパス２１およびゲート５１を介して次命令レジスタ
１６にロードする。分岐の目標アドレスがアドレス生成
ユニット１９から得られる。目標アドレスを、更新ＩＣ
２７にも送ると共に、パス５３と５４をそれぞれ介し
て、順次プリフェッチ制御部（ＳＰＣ）５２へ送る。こ
のＳＰＣ５２は、分岐の新たな目標アドレスと共に開始
する命令セグメントをフェッチし始める。

【００４６】デコーダ１７が条件付き分岐を検出した場
合に、ＤＨＴ５５がパス９１を介してアクセスされ、こ
れによって採用または不採用の分岐の結果を予測する。
このＤＨＴ５５は、命令カウンタ２６に含まれたアドレ
ス・ビットの部分集合を利用して、ＤＨＴ５５に含まれ
たＤＨＴアレイを検査する。この分岐の予測が“採用さ
れた”場合に、目標アドレスが、無条件分岐に対する目
標アドレスがフェッチされたのと同様にフェッチされ
る。即ち、目標アドレスがキャッシュ１３からフェッチ
され、目標命令をゲート５１を介して次命令レジスタ１
６にロードされる。また、目標アドレスをパス５３を介
して更新ＩＣ２７にも送ると共に、ＤＨＴ５５は、パス
５６を経て順次プリフェッチ制御部（ＳＰＣ）５２に信
号を与えて、その命令フェッチアドレスを、分岐の予測
された目標アドレスに対してリセットして、新たな次順
序フェッチを開始する。この分岐の目標アドレスをパス
５４を介してＳＰＣ５２に送る。

【００４７】命令フェッチ・ロジックを順次プリフェッ
チ制御（ＳＰＣ）５２に包含させる。図５は、この機構
を更に詳細に示すものである。ここで、最終命令フェッ
チのアドレスを最終セグメント・フェッチド・レジスタ
６１に保管し、命令バッファが、ＳＰＣ５２に対して、
ゲート６２を経て、他の命令フェッチ用にスペースを利
用できる旨を知らせた場合は何時でも、次の順次命令フ
ェッチ・アドレスが発生し、キャッシュ１３へ送られ
る。無条件分岐または、予測された採用条件付き分岐を
デコードし、ＳＰＣ５２に、パス５６を経て信号伝送し
て、その命令フェッチ・アドレスを分岐命令の目標アド
レスに対してリセットする時は、何時でも、最終ブロッ
ク・フェッチド・レジスタ６１を分岐の目標アドレスで
ロードする。このアドレスは、アドレス生成部１９によ
り与えられる。その後に、次順序フェッチのすべてをＳ
ＰＣ５２内で生成することができる。目標アドレスをこ
のＳＰＣ５２にパス５４を介して送り、ＤＨＴ５５から
パス５６を介して送られてきた信号にゲート６３を経て
ロードする。無条件分岐または予測された採用条件付き
分岐がデコードされる。

【００４８】分岐予測はＤＨＴ５５によって実行され
る。図６はＤＨＴの更に詳細な説明である。前述したよ
うに、条件付き分岐のみがＤＨＴによって予測される。
これは、すべての無条件分岐は、一旦デコードされれ
ば、これら分岐を正確に予測できるからである。条件付
き分岐をデコードした時は、何時でも、ＤＨＴは、パス
９１を経てデコード機能ブロック１７より信号伝送され
る。ＤＨＴアレイ７１は、命令アドレスを表示し命令カ
ウンタレジスタ２６内で保持されたビットの部分集合を
利用してアクセスされる。各アレイ・エントリは、単一
ビットのみから構成され、このビットの値は、このメモ
リ・ロケーションで分岐の結果を、このテーブルのサイ
ズまで表す。例えば、ＤＨＴアレイ７１で検査されたエ
ントリが１個（ＤＨＴヒット）の場合に、この分岐は採
用されたものと推定される。または、見出された値がゼ
ロ（ＤＨＴミス）の場合に、この分岐は採用されなかっ
たものと推定される。ここで、用語“ＤＨＴヒット”お
よび“ＤＨＴミス”とは、ＢＨＴに対する用語、即ち、
“ＢＨＴヒット”および“ＢＨＴミス”に対応するもの
である。これら用語は、分岐が採用としてまたは不採用
として予測されるかどうかを表している。

【００４９】ＤＨＴ補正情報がパス２２を経て、実行ユ
ニット１８からＤＨＴへ送られる。この補正情報には、
採用または不採用の分岐の実行結果が含まれており、更
に、分岐のアドレスも含まれている。この情報を利用し
て、ＤＨＴを更新する。ＤＨＴは、条件付き分岐の各々
の動作を予測するだけであるので、各分岐の実行結果の
みをＤＨＴへ戻す必要がある。

【００５０】ＢＨＴおよびＤＨＴを有するプロセッサの
動作についての概要について説明する。図７（Ａ）およ
び図７（Ｂ）は、これらプロセッサにおいて起こる事象
および動作を要約した表形態のルールのセットを表して
いる。これら事象はデコード時および命令フェッチ時動
作に従ってリストされており、ＢＨＴおよびＤＨＴヒッ
トまたはミス結果が表されている。例えば、図７（Ａ）
は、“ＢＨＴヒット”（採用の予測）によって命令フェ
ッチ機構に、分岐の目標アドレス（命令フェッチ時の）
に切り換えさせることを表している。しかしながら、Ｂ
ＨＴミスにおいては、命令フェッチ機構は命令を次の順
次パスへフェッチし続ける。パイプラインのデコード段
階中に、デコーダは、ＢＨＴヒットによって識別された
ように目標アドレスストリームに切換えられるか、また
は、ＢＨＴエントリが見つからなかった場合（ＢＨＴミ
ス）、次の順序パスをデコードし続ける。

【００５１】図７（Ｂ）に示したように、ＤＨＴを有す
るプロセッサに対し採用された動作は、互いに相違す
る。命令フェッチ段階中に、命令フェッチ機構によっ
て、予測結果に拘らず、次の順序命令のみをフェッチす
ることができる。しかしながら、分岐がデコード時に発
見され、採用されたものと（ＤＨＴヒット）予測された
場合に、命令フェッチ機構は、命令セグメントを目標ア
ドレス・パスへフェッチし始める。同様に、デコーダ
は、ＤＨＴヒットが起こると、命令を目標アドレス・パ
スへデコードするように切換える。予測がＤＨＴミスの
場合に、プロセッサは命令を次の順序パスへフェッチし
続け、次のサイクルのフォールスルー命令をデコードす
る。

【００５２】次に、本発明の特別な実施例、即ち、マル
チ予測型分岐予測機構を説明する。この機構は、ＢＨＴ
とＤＨＴとを両方利用して分岐を予測するもので、この
ような予測を行う場合に、どちらの予測機構（ＤＨＴ／
ＢＨＴ）も別個に設けることができない特徴を提供する
ことによって、予測プロセスを改良することができる。
従って、これらの特別な特徴によって、分岐予測の全体
の精度を改善し、この結果として性能を改善する。図８
は、本発明を説明する事象および動作の概要を示すテー
ブルである。ＢＨＴヒットの各々を２つのカテゴリ、即
ち、“アクティブ採用ヒット”および“ゴースト・ヒッ
ト”に分割する。

【００５３】アクティブ採用ヒットを用いて前に呼び出
されたＢＨＴヒットが何であるかを説明する。即ち、命
令フェッチ・アドレスは、ＢＨＴに保管された分岐アド
レスに一致し、この分岐が現在採用される。しかしなが
ら、“ゴースト・ヒット”とは、命令フェッチアドレス
がＢＨＴにセーブされた分岐アドレスに一致するが、こ
の分岐は最早、採用しない場合のことを意味する。図９
を用いてこれらの差異を詳述する。この図は、ＢＨＴデ
ィレクトリ，アレイおよびブロック・エントリ用のフォ
ーマットを表す。各ディレクトリ・エントリ８１は、命
令フェッチ・セグメントのアドレスを表し、このセグメ
ントには少なくとも１個のすでに実行して採用された分
岐が含まれる。ディレクトリのエントリの各々に関連し
たアレイ情報８２によって、（ａ）命令フェッチ・セグ
メント内に含まれた採用分岐の各々のアドレスと、
（ｂ）各分岐の目標アドレスと、（ｃ）採用された、採
用されなかったビットと、（ｄ）有効ビットと、（ｅ）
ＬＲＵ使用ビットとを識別する。

【００５４】命令フェッチ・セグメント中に包まれた採
用分岐のアドレスをＸとする。ＢＨＴディレクトリ８３
および対応するセグメント情報８４にＸの値を有するよ
うになる。ディレクトリ・エントリは命令フェッチ・セ
グメントのアドレスを表し、採用された多数の分岐が各
セグメント内に存在し得る。各命令フェッチ・セグメン
トは、通常、数ワード長であり、いくつかの命令を含む
ことを思い出されたい。従って、アレイ・セグメント・
エントリ情報には、各命令フェッチ・セグメント内で見
つかった採用分岐を識別する情報が含まれている。図９
は、セグメント・エントリの各々によって、命令フェッ
チ・セグメント内の採用分岐を４個まで識別できること
を示している。このことは、クワドワード（１６バイ
ト）の命令フェッチ・セグメントに対して更に適切なも
のである。各サブ・セグメント・エントリは、命令フェ
ッチ・セグメント内の分岐アドレスを識別する情報を含
んでいる。このフィールドは、ＩＢＭＳ／３７０アー
キテクチャにおけるクワドワード・セグメント内の命令
を識別するには、僅か３ビット長であれば良い。その理
由は、命令を各ハーフワード境界でのみ開始できるから
である。分岐はあらゆる命令フェッチ・セグメントに分
岐できるから、目標アドレスは完全な命令アドレスであ
る必要がある。しかしながら、目標アドレスをＢＨＴに
記憶させた場合に、略記または短縮することができる。
下位ビットの部分集合のみを保管することができ、これ
らビットによって完全な目標アドレスが形成される。従
って、この完全な目標アドレスは、命令カウンタ・レジ
スタからの現在の高位ビットをＢＨＴに保管された低位
ビットに連結することによって再構成することができ
る。この技術は、一般に分岐が短い距離ジャンプし、完
全な目標アドレスをアドレス・ビットの短縮されたセッ
トのみから発生する場合に、非常に僅かの精度しか失わ
れないという観察を利用しようとするものである。

【００５５】有効ビットを用いることによって、各ブロ
ックにおけるＢＡ／ＴＡ対のいずれが（４個まで）が有
効であるかを表す。前述したように、各命令フェッチセ
グメント内の４個までの分岐アドレスを記憶しておくよ
うにする。

【００５６】分岐はその動作を変更できるから、採用さ
れたビットが必要となる。即ち最初に、分岐を採用し
て、ＢＨＴに入る必要がある。しかしながら、続く実行
において、分岐の採用に失敗する。この動作は、ＢＨＴ
補正を生じる。このＢＨＴ補正は、採用されるものと予
測され、次に、実行時に採用に失敗するすべての分岐と
に対して行われることを思い出されたい。この補正機構
によって、このＢＨＴエントリに対して採用されたビッ
トを“ターンオフ”する必要がある。命令フェッチ・セ
グメントが、ターンオフされた“採用ビット”を有する
分岐アドレスに一致する場合に、ゴースト・ヒットが識
別される。これらゴースト・ヒットを利用して、最早採
用されないＢＨＴエントリ（分岐）に対するヒットを記
述する。

【００５７】命令フェッチ・セグメントには４個より多
くの採用分岐を含むことができるので、使用ビットを必
要とする。このことが起こった場合に、置き換え機構を
利用して、最近参照した分岐アドレスを保持し、過去に
おいて最も早く参照した分岐アドレスを廃棄する。代表
的に、最低使用頻度（ＬＲＵ）アルゴリズムまたはＬＲ
Ｕアルゴリズムの形態を、置き換えアルゴリズムとして
利用する。

【００５８】図８から理解できるように、ＢＨＴ予測の
各々（ヒット，ゴースト・ヒット，ミス）は、現在、Ｄ
ＨＴ予測（ヒットまたはミス）と対となっている。これ
ら事象が、プロセッサの命令フェッチおよびデコード時
段階に従ってリストされている。

【００５９】例えば、有効ＢＨＴヒットによって、命令
機構がＢＨＴ内で見出された分岐の目標をフェッチす
る。このことはＤＨＴの予測、ヒットまたはミスに関係
なく起こるものである。デコード時において、このプロ
セッサは、目標アドレス・パスからの命令をデコードす
るように切り換える。目標アドレスパスからの命令を、
ＤＨＴヒットまたはミスに対しプロセッサによってデコ
ードする。

【００６０】しかしながら、各“ゴースト・ヒット”予
測（命令フェッチ時での）によって、命令フェッチ機構
が、次順序パスからの命令をフェッチし続けるようにす
る。パイプラインのデコード段階中は、プロセッサは、
ＤＨＴ予測がヒットまたはミスに関係なく、次順序パス
をデコードし続ける。

【００６１】ＢＨＴミスに対して、プロセッサは、次順
序セグメントをフェッチし続ける。デコード時におい
て、ＤＨＴが分岐は採用されないと予測した場合に、プ
ロセッサは次順序パスからの命令をデコードし続ける。
しかしながら、ＢＨＴによって実行される初期予測がミ
ス（即ち、採用されなかった）であり、ＤＨＴが分岐は
採用される、即ち、デコード時にＤＨＴヒットであると
予測する場合には、プロセッサは、次順序パスのフェッ
チを停止し、目標アドレス・パスからの命令をフェッチ
するように切り換わる。分岐の目標アドレスはアドレス
生成機能より得られる。目標アドレス命令が命令バッフ
ァ内で得られると、デコーダはまた、分岐によって識別
された目標アドレス・パスからの命令をデコードするよ
うに切り換わる。

【００６２】図１０は、分岐予測にＢＨＴとＤＨＴの両
者を利用する本発明の好適な実施例によるプロセッサの
特徴を示している。この図における特徴の大部分は、Ｂ
ＨＴだけを有するプロセッサ（図２）またはＤＨＴのみ
を有するプロセッサ（図４）で説明したのと同様な機能
を有するものである。例えば、キャッシュ１３によって
命令を命令バッファ１１に供給すると共に、オペランド
を実行ユニット１８に供給する。次命令レジスタ１６に
は、命令デコード部１７によって処理すべき次命令が含
まれている。ＢＨＴ１２は分岐予測を実行し、命令のフ
ェッチ動作を制御し、更に、パイプラインを経る命令の
流れを指定する。ＢＨＴ１２によって、命令バッファ１
１に信号が伝送され、これによって、次命令レジスタ１
６には適当な次命令、即ち、次順序命令または分岐目標
命令がロードされる。次命令フェッチは、スペースが利
用可能であるとの信号（命令バッファ１１からの）に対
してＢＨＴ１２によって発生される。次命令フェッチ
は、前の命令フェッチの結果（ＢＨＴヒットまたはＢＨ
Ｔミス）に応じて、次順序アドレスまたは分岐命令の目
標アドレスのいずれかとすることができる。

【００６３】ＤＨＴ５５の動作は、図４に記載したＤＨ
Ｔの動作に類似したものである。即ち、このＤＨＴ５５
はパイプラインのデコード段階中に条件付き分岐を予測
し、ＢＨＴに対して、分岐予測の結果（ヒットまたはミ
ス）のパス５６を介して信号伝送する。分岐予測結果と
一緒に、分岐のアドレスならびに分岐の目標アドレスも
また、パス５６を介して供給する。この情報は、ＢＨＴ
１２における命令フェッチ・ロジックによって利用さ
れ、ＢＨＴによって行われた分岐予測（これはパイプラ
インの命令フェッチ段階中に行われる）が正しいことを
確認する。しかしながら、分岐の目標アドレスをパス２
８を介してＢＨＴ１２にすでに供給しているので、重ね
てパス５６を介して送る必要がない。この情報をパス５
６上の信号に包含させることによって、パイプラインの
再始動および命令フェッチ・ロジックが簡略化される。

【００６４】ＤＨＴ５５はパス９１を介して命令デコー
ド機能ブロック１７から信号伝送され、これは条件付き
分岐がデコードされた場合には、何時でも行われる。分
岐のアドレスは、命令カウンタ・レジスタ２６からＤＨ
Ｔ５５へ供給される。ＢＨＴとＤＨＴとの補正が、実行
ユニット１８からパス２２を介して信号伝送される。ア
ドレス加算器２５は、デコードされ且つＩＣレジスタで
見出された命令のアドレスと、デコードされる命令の長
さとをその入力とし、次命令アドレスを演算する。新し
いアドレスを更新ＩＣレジスタ２７に保管する。分岐が
採用または不採用であるかを決定するためのＤＨＴ予測
ロジックは、図６で説明したものと同一である。この情
報をＢＨＴ内で見出される分岐予測ロジックと組合せる
ことにより、ＢＨＴまたはＤＨＴが単独で与えられない
分岐スキームが改善される。

【００６５】図３に関連して説明したように、ＢＨＴに
対していくつかの変更がなされる。図１１は、図９で説
明したように正しいＢＡ／ＴＡ対がどのようにしてＢＨ
Ｔエントリから選択されるかを、詳細に示したものであ
る。“ＢＨＴヒット”とは、図３において、命令フェッ
チアドレス３１の結果であり、図９のＢＨＴ８２に保管
された命令フェッチセグメントに一致している。比較ロ
ジックが機能部１０２に包まれる。比較に使用された命
令フェッチアドレスを２つの部分１０３と１０４とに分
割できる。部分１０３を使用して、ＢＨＴに保管された
各命令フェッチ・セグメントに対して比較を行う。アド
レスのこの部分によって、ダブルワードまたはクワドワ
ードまで命令フェッチのアドレスを特定化する必要があ
り、これは、キャッシュまたはメモリからの命令をフェ
ッチするために使用したアドレス・フェッチ・バスの幅
に依存する。部分１０４は命令フェッチ・アドレスのサ
ブアドレス（ＳＡ）部分を表し、更に、命令フェッチ・
セグメント内のどの命令がＢＨＴエントリを生じさせた
かを識別する。この命令は採用分岐となる。このアドレ
スの部分は、直ちに、“ＢＨＴヒット”を検出する時に
必要となるものではない。これは、命令フェッチ・アド
レスとＢＨＴに保管された命令フェッチ・セグメントと
の初期一致後にのみ使用される。“ＢＨＴヒット”が検
出された後に、命令フェッチ・セグメント内の正しい分
岐を選択する必要がある。各命令フェッチ・セグメント
内に数個の採用分岐が存在し得るものである。

【００６６】所望の分岐は、命令フェッチ・アドレス以
降に出会う、最も近接した分岐として識別される。適切
な分岐アドレスは、以下のルールに従って、選択ロジッ
ク１０５によって選択される。・識別されたＢＨＴセグメント中の各ＢＡフィールドか
らＳＡフィールドを減算する。・負および無効の差を無視する。・最小の差または差が零のＢＡを選択する。

【００６７】次に、完全なＢＡを選択ゲートロジック１
０６において生成する。選択ロジック１０６から選択さ
れたＢＡ１０４の値を命令フェッチ・アドレス１０３に
付加して、完全な分岐アドレスを生成する。次に、この
アドレスを適当なＴＡと対を成し、ＢＡ／ＴＡ対を形成
する。このＢＡ／ＴＡ対は、採用したビットがゼロ、Ｔ
＝０の場合に、ゴースト・ヒットを表し、Ｔ＝１の場合
に、有効な採用ヒットを表す。選択されたＢＡ／ＴＡ対
を図３のＢＡ／ＴＡスタック３７に保管して、命令バッ
ファ１１からの“次命令”の後の選択を、図２の次命令
レジスタ１６に導く。選択された目標アドレスをまた他
の２つのロケーションにゲートする。第１として、ＴＡ
を用いて、図３の次命令フェッチ・アドレス３１を更新
する。第２として、目標アドレスを用いて、図３の次順
序命令フェッチ制御部３４をリセットする。

【００６８】図１２は、ＤＨＴおよびＢＨＴを利用した
予測ロジックを詳細に説明するものである。このロジッ
クの要素は、図３に説明した予測ロジックに類似してい
る。次命令フェッチ・アドレス３１に含まれている命令
フェッチ・アドレスの各々を、ＢＨＴに含まれている命
令フェッチ・セグメントに対して比較を行う。比較ロジ
ックが機能ブロック３３中に含まれている。一致検出
（ＢＨＴヒット）されると、適切なＢＡ／ＴＡアドレス
がＢＡ／ＴＡスタック３７に保管される。有効な採用ヒ
ット（採用ビットＴ＝１）とゴースト・ヒット（Ｔ＝
０）とが、ＢＡ／ＴＡスタック中に保管される。これら
ＢＡ／ＴＡアドレス対を利用して、命令バッファ１１か
らの次命令レジスタ１６を適切な次命令でロードする。

【００６９】“ＢＨＴヒット”が有効な採用ヒット（Ｔ
＝１）の場合に、ＴＡを命令フェッチ・レジスタ３１に
も送ると共に、次順序フェッチ機構３４にも送る。選択
されたＴＡはすべての有効な採用ヒット上の次命令フェ
ッチとなり、またこれを利用して次順序フェッチ制御部
３４をリセットする。

【００７０】パス５６を介して得られたＤＨＴの予測結
果と、ＢＡ／ＴＡスタック３７により与えられたＢＨＴ
による予測とを機能ブロック１１１で検証する。ＢＡ／
ＴＡスタック３７中の最古のエントリのＢＡを、丁度デ
コードした分岐のアドレスと比較する。これらアドレス
が互いに等しくない場合は、プロセッサは、ＢＨＴが不
採用、即ちＢＨＴミスである分岐をデコードする。次
に、この処理ロジックは機能ブロック１１２に進んで、
ここでは、ＤＨＴによる予測を検証する。分岐が採用さ
れるとＤＨＴが予測した場合に、ＢＨＴによって行われ
る予測が正しいものでなく、正しい予測はＤＨＴによる
ものであるとする。このことによってパイプラインが再
び始動されるようになり（機能ブロック１１３）、図８
で説明したＢＨＴミスおよびＤＨＴヒットに対する命令
フェッチおよびデコード時のポリシィが実施される。丁
度デコードされた分岐の目標アドレスは、次命令フェッ
チ・アドレスとなり、パイプラインは目標アドレス・パ
スへ進行する。このＤＨＴによって、ＢＨＴより多数の
分岐の結果を記憶することができるが、サイズにおいて
は依然小さいものである。この結果、採用されない分
岐、即ちＢＨＴミスの予測を、採用された分岐の結果と
することができ、この採用された分岐は小さなＢＨＴか
ら古くなったもので、依然として大きなＤＨＴに保持さ
れている。

【００７１】ＤＨＴによって成された予測が採用されな
い場合に、機能ブロック４３が信号伝送されて、命令バ
ッファからロードされた次命令として分岐に継続する命
令を、次命令レジスタ１６にロードする。

【００７２】機能ブロック１１１のロジックに戻り、Ｂ
Ａ／ＴＡスタック３７からのＢＡが、デコードされる分
岐のアドレスに等しい場合に、図８のＢＨＴヒットポリ
シィを実行する。この分岐が有効な採用ヒット（Ｔ＝
１）として識別される場合に、機能ブロック４２が信号
伝送されて、目標アドレス情報を命令バッファ１１から
ロードされた次命令として利用する。ＢＨＴエントリが
ゴースト・ヒット（Ｔ＝０）を識別する場合に、機能ブ
ロック４３は、命令バッファからロードされた次命令が
次順序またはフォールスルー命令であることを伝える。

【００７３】機能４１を再び利用して、パス２８を介し
て戻された次命令アドレスを、ＢＡ／ＴＡスタック３７
中の最古のエントリのＢＡと比較する。このことによっ
て、命令バッファからの命令を、次命令レジスタ１６に
ロードすることを導く。機能４０によって、図２のアド
レス生成部１９によって演算された分岐の目標アドレス
を、ＢＡ／ＴＡスタック３７に保管された分岐の目標ア
ドレスと比較する。保管された目標アドレスがデコード
時の生成目標アドレスと異なる場合に、パイプラインを
再び始動する必要がある。この再始動情報をパス４５を
介して送る。ＢＨＴ補正が補正処理スタック４７へ送ら
れる。ここで、採用または不採用の各分岐の実行結果
を、予測結果に基いてチェックし、新しいエントリを更
新する。即ち、必要に応じて、分岐削除を更新パス４６
を経てＢＨＴへスケジュールされる。

【００７４】最後に、図１３は、比較ロジックの詳細を
示し、このロジックを利用してＢＨＴとＤＨＴとによっ
て行われた予測を検証する。機能１１１によって、丁度
デコードされた分岐のアドレス（パス５６を介して送ら
れた）を、ＢＡ／ＴＡスタック３７中の最も古いエント
リのＢＡと比較する。これらアドレスが等しい場合に
（ＢＨＴヒットを識別する場合）、採用または不採用の
ビットを機能１２２で検証する。機能１２２の出力によ
って、選択された分岐が有効な採用ヒットまたはゴース
ト・ヒットであるかを決定する。比較ロジック１２２に
よって、ＢＡ／ＴＡスタック３７からの分岐アドレスが
デコードされた分岐のアドレスと等しくないことが決定
されると、ＢＨＴミスが識別される。

【００７５】選択ゲート１２３〜１２８によって、どの
命令フェッチ／デコード時ポリシィを、図８で説明した
ように採用するかを決定する。各ゲートは、ＡＮＤゲー
トを表し、その出力を以下のユニット（図１２に示し
た）に送る。：・次の命令として次順序命令をデコードするユニット４
３。・次の命令として分岐の目標アドレスをデコードするユ
ニット４２。・パイプラインを再始動させるユニット１１３。このユ
ニットによって、分岐の目標アドレスをフェッチさせ、
次の命令としてデコードする。

【００７６】前述した実施例においては、パイプライン
の命令フェッチ段階中およびデコード時に、２度各分岐
を予測する。従って実施例では、２つの独立した分岐予
測ポリシィが互いに一致しないときは何時でも、予測を
決定する一組のルールを利用する。特に、実施例で記載
されている２つの分岐予測スキームはＢＨＴとＤＨＴと
である。すべての分岐予測差を調停するルールの組が図
８に記載されている。ＢＨＴとＤＨＴとは、分岐予測ポ
リシィにおける好適な選択である。その理由は、これら
は各々別個に、分岐の予測において極めて高い成功率を
有しており、更に、これらを一緒に利用した場合に、高
いパーセンテージの分岐をうまく予測できるからであ
る。

【００７７】しかしながら、従来技術で説明したような
他の分岐予測スキームの１つを、ＢＨＴまたはＤＨＴ予
測スキームで置換することは容易なことであり、更に、
本発明の技術思想上の範囲内である。例えば、分岐予測
は米国特許第４，１８１，９４２号明細書および第４，
２００，９２７号明細書に記載されたようなオペコード
・タイプに従って実行できる。これらオペコード・タイ
プの両方を、ＢＨＴおよびＤＨＴで置換できる。従っ
て、図８に関連して記載したルールに類似したルール
が、分岐予測スキームが一致しない時に、これら差異を
解決するために必要となる。事実、第３の分岐予測ポリ
シィを利用して、最初の２つの分岐予測スキームが一致
しないケースを調停するようにする。

【００７８】例えば、ＢＨＴとＤＨＴとによって行われ
た予測が一致しない場合に、他の分岐予測スキーム（オ
ペコード・タイプによって各分岐を予測できるもの）を
利用してこれら差異を調停できる。あるいはまた、マル
チ予測型分岐予測機構を、２つの予測の一致によって決
められる各分岐の実際の予測を有する３つの別個の分岐
予測ポリシィで構成できる。当業者であれば、異なる分
岐予測スキームを、本発明の実施例で説明したスキーム
と置き換えるか、または、現存の分岐予測スキームを変
更でき、および本発明の技術思想の範囲内で変形し得る
ものである。

【図面の簡単な説明】

【図１】高性能コンピュータにおけるパイプライン・ス
テージの概念を示すブロック図である。

【図２】分岐履歴テーブル付き従来のプロセッサを示す
ブロック・ダイヤグラムである。

【図３】図２のプロセッサのテーブルと組合された動作
を示すフローチャートである。

【図４】デコード履歴テーブル付き従来のプロセッサを
示すブロック・ダイヤグラムである。

【図５】図４に示したプロセッサにおける順序フェッチ
・ロジック制御を示すブロック・ダイヤグラムである。

【図６】図４のプロセッサのデコード履歴テーブルを示
すブロック・ダイヤグラムである。

【図７】図２と図４に示したプロセッサの分岐履歴テー
ブルとデコード履歴テーブル命令フェッチ・デコード・
アルゴリズムを示すテーブルである。

【図８】本発明の一実施例による、集積された分岐履歴
／デコード履歴テーブル命令フェッチおよびデコード時
アルゴリズムを示すテーブルである。

【図９】本発明による分岐履歴テーブル・ダイヤグラム
と、セグメント・エントリ情報を示すテーブルである。

【図１０】本発明の一実施例による、分岐履歴テーブル
と、デコード履歴テーブルとを有するプロセッサのブロ
ック・ダイヤグラムである。

【図１１】本発明の一実施例で使用されている分岐アド
レス／目標アドレス選択機構を示すブロック・ダイヤグ
ラムである。

【図１２】分岐履歴テーブルおよびデコード履歴テーブ
ル・ロジックを示すフローチャートである。

【図１３】分岐履歴テーブルとデコード履歴テーブル予
測機構の詳細を示すブロック・ダイヤグラムである。

【符号の説明】

１０メモリ１３キャッシュ１７デコード機構２７更新命令カウンタ・レジスタ３１アドレス・レジスタ３７目標アドレス・スタック４３信号ユニット５２順序プリフェッチ制御７１ＤＨＴアレイ８２アレイ情報１０３命令フェッチ・アドレス

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジョシュア・ウィルソン・ナイトアメリカ合衆国ニューヨーク州モヒガンレイクサガモアアベニュー 3490 (72)発明者ジェームス・ハーバート・ポメレーヌアメリカ合衆国ニューヨーク州チャッパカノースベッドフォードロード 403 (72)発明者トーマス・ロバーツ・プザックアメリカ合衆国コネチカット州リッジフィールドスクールハウスプレイス９ (72)発明者ルドルフ・ネイサン・リヒトシャーフェンアメリカ合衆国ニューヨーク州スカースデールインズロード 24 (72)発明者ジェームス・ロバート・ロビンソンアメリカ合衆国ニューヨーク州クリントンコーナーズアールアール２ボックス 319 (72)発明者アルバート・ジェームス・バン・ノーストランド，ジュニアアメリカ合衆国ニューヨーク州レッドフックグランドムールドライブ３

Claims

【特許請求の範囲】

【請求項１】フェッチした命令を一時記憶するメモリに
接続された命令バッファと、この命令バッファに接続さ
れ、命令バッファ内に一時記憶された命令をデコードす
る命令デコード機構と、この命令デコード機構からのデ
コードされた命令に応答して、前記メモリをアドレスす
ることにより前記命令バッファへの命令をフェッチする
アドレス生成機構と、前記命令デコード機構からのデコ
ードされた命令に応答して、デコードされた命令に従っ
て動作を実行する実行ユニットとを含むパイプラインプ
ロセッサを有するコンピュータにおける分岐命令の結果
を予測するマルチ予測型分岐予測機構において、前記パイプラインプロセッサに接続され、前記パイプラ
インのそれぞれ異なるステージにおいて分岐命令を独立
して予測する少なくとも２個の独立した分岐予測機構
と、前記分岐予測機構に応答して、前記分岐予測機構の各々
から得られた予測が互いに異なる場合にこれを解決する
手段と、前記実行ユニットに応答し、分岐命令の実行に基づい
て、前記分岐予測機構を更新する手段とを備えたことを
特徴とするマルチ予測型分岐予測機構。
【請求項２】前記少なくとも２つの独立した分岐予測機
構の１つまたはそれ以上の機構が、前記命令バッファおよび前記アドレス生成機構に接続さ
れた命令フェッチ分岐機構を有し、この命令フェッチ分
岐機構によって、採用された分岐の限定された履歴に基
づいて初期分岐予測を生成し、目標アドレスを前記アド
レス生成機構に供給することを特徴とする請求項１記載
のマルチ予測型分岐予測機構。
【請求項３】前記少なくとも２つの独立した分岐予測機
構の１つまたはそれ以上の機構が、前記命令デコード機
構および前記命令分岐予測機構に接続されたデコード時
分岐予測機構を有し、このデコード時分岐予測機構によ
って、実行した分岐の履歴に基づいて分岐予測を生成す
ることを特徴とする請求項１記載のマルチ予測型分岐予
測機構。
【請求項４】前記少なくとも２つの独立した分岐予測機
構が、前記命令バッファと前記アドレス生成機構とに接続さ
れ、採用された分岐の限定された履歴に基づいて初期分
岐予測を生成し、目標アドレスを前記アドレス生成機構
に供給する命令フェッチ分岐予測機構と、前記命令デコード機構と前記命令フェッチ分岐予測機構
とに接続され、実行した分岐の履歴に基いて分岐予測を
生成するデコード時予測機構とを有することを特徴とす
る請求項１記載のマルチ予測型分岐予測機構。
【請求項５】前記分岐予測機構に応答して、前記分岐予
測機構の各々から得られた予測が互いに相違した場合
に、これを解決する前記手段が、前記命令フェッチ分岐予測機構からの前記初期分岐予測
と、前記デコード時分岐予測機構からの前記分岐予測と
を比較する比較手段と、この比較手段に応答して、前記初期分岐予測と、デコー
ド時分岐予測機構からの分岐予測との間で一致が発生し
た時に、前記命令フェッチ分岐予測機構からの初期分岐
予測を受入れるが、前記デコード時分岐予測機構からの
分岐予測を選択し、前記初期分岐予測と前記分岐予測と
が一致しない場合に、前記パイプラインを再始動するこ
とによって、前記初期分岐予測を無効とする選択手段と
を有することを特徴とする請求項４記載のマルチ予測型
分岐予測機構。
【請求項６】前記命令フェッチ分岐予測機構が、分岐の
目標アドレスが続く最近実行された一組の分岐が記憶さ
れる分岐履歴テーブルを有し、前記デコード時分岐予測
機構が、各分岐の動作の記録が記憶されるデコード履歴
テーブルを有することを特徴とする請求項５記載のマル
チ予測型分岐予測機構。
【請求項７】前記実行ユニットに応答して、分岐命令の
実行に基いて前記分岐予測機構を更新する前記手段が、
前記実行ユニット，分岐履歴テーブルおよびデコード履
歴テーブルに接続され、これらテーブルに記憶された情
報を分岐命令の実行に基づいて補正する補正処理機構を
有することを特徴とする請求項６記載のマルチ予測型分
岐予測機構。