JP3798404B2

JP3798404B2 - ２レベルの分岐予測キャッシュによる分岐予測

Info

Publication number: JP3798404B2
Application number: JP2003521935A
Authority: JP
Inventors: ディー．ズラスキージェラルド; エス．ロバーツジェイムズ
Original assignee: Advanced Micro Devices Inc
Current assignee: Advanced Micro Devices Inc
Priority date: 2001-07-24
Filing date: 2002-06-27
Publication date: 2006-07-19
Anticipated expiration: 2022-06-27
Also published as: CN1310134C; TW591530B; US7024545B1; WO2003017091A1; CN1535415A; EP1410177A1; JP2005500616A; KR20040014673A; US6854050B1; KR100880686B1

Description

本発明は、スーパースカラーマイクロプロセッサの分野に関するものであり、より詳細には、分岐予測のための方法およびメカニズム（機構）に関するものである。

IEEE Transactions on Computers, IEEE Inc, New York, US, vol. 42, no. 4, 1 April 1993, ３９６から４１２ページ，Perleberg CH et al, 題名"Branch Target Buffer Design and Optimization"（分岐ターゲットバッファの設計および最適化）には、マルチレベル分岐ターゲットバッファ（ＢＴＢ）が説明されている。マルチレベルＢＴＢの各レベルには、エントリ毎に異なった量／タイプの情報が含まれており、エントリの数的およびエントリ毎の情報の量のよりよいバランスを達成することによって、性能の最大化を達成する。
スーパースカラーマイクロプロセッサでは、１クロックサイクルに複数の命令を実行し、その設計に合わせた最も短いクロックサイクルを選択することによって高性能が実現されている。本明細書で使用されるように、「クロックサイクル」との用語は、マイクロプロセッサ内の命令処理パイプラインの各種ステージに与えられる時間間隔を指す。記憶装置（例えばレジスタやアレイ）は、クロックサイクルに従って値を取得する。例えば、記憶装置が、クロックサイクルを定義しているクロック信号の立ち上がりまたは立ち下がりに従って値を取得し得る。次に、記憶装置は、クロック信号の立ち上がりに値を取得した場合は次の立ち上がりまで、足り下がりで取得した場合は立ち下がりまでこの値をストアし得る。本明細書に使用する「命令処理パイプライン」との用語は、パイプライン方式での命令の処理に使用される論理回路を指す。パイプラインを、任意の数のステージに分割して、これらステージで命令処理の一部を実行することが可能であるが、一般に命令処理では、命令のフェッチ、命令のデコード、命令の実行、およびデスティネーションへの実行結果のストアが行われる。

発明の概要

スーパースカラーマイクロプロセッサ（およびスーパーパイプライン方式のマイクロプロセッサ）の重要な機能に、分岐予測メカニズムがある。分岐予測メカニズムは、分岐命令の予測された行き先（分岐の成立［taken］または不成立［not-taken］）を示し、これにより、分岐予測によって示される予測された命令の流れに含まれる後続の命令のフェッチを続行できるようになる。分岐命令とは、分岐命令の直後の命令から始まる命令の流れを示す連続するアドレスか、メモリ内の任意の場所から始まる命令の流れを示すターゲットアドレスか、の２つ以上のアドレスの１つから後続の命令をフェッチさせる命令のことである。無条件分岐命令では、常にターゲットアドレスに分岐するのに対し、条件付き分岐命令では、先行する命令の結果によって、連続アドレスかターゲットアドレスかのいずれかが選択され得る。予測された命令の流れに含まれる命令は、分岐命令の実行前に投機的に実行され得、いずれの場合であっても分岐命令の実行前に命令処理パイプラインに投入される。予測された命令の流れが正しければ、１クロックサイクルに実行される命令数が増え有利となる。しかし、予測された命令の流れが外れた（つまり、１つ以上の分岐命令が誤って予測された）場合には、その予測された命令の流れに含まれる命令が命令処理パイプラインから破棄され、１クロックサイクルに実行される命令数が低下する。

分岐予測メカニズムが効果を発揮するには、予測された命令の流れができるだけ的中するように、分岐予測メカニズムの精度が極めて高くなければならない。過去の分岐の実行履歴を使用して、特定の分岐の挙動の精度を向上させることがよく行われる。通常、このような分岐予測履歴では、分岐命令に対応するデータを記憶域に保持しなければならない。分岐予測のデータが記憶域から排除されているかデータが失われている場合は、その分岐命令の実行履歴を後から再生成する必要がある。上記の問題に対する解決策の１つとして、分岐予測用の記憶域のサイズを増やすことが考えられる。しかし、分岐予測用の記憶域のサイズを増やすには、ゲート面積の大幅な拡張と、分岐予測メカニズムのサイズの拡張とが必要となることがある。このため、分岐の挙動に関する貴重なデータが失われるおそれがあり、再生成が必要となる。したがって、ゲート数および分岐予測メカニズムのサイズの大幅な拡張を必要としない、分岐予測の性能を向上させるためのメカニズムが求められている。

上記の問題は、ここに記載するマイクロプロセッサおよび方法によって大部分が解決される。一実施形態においては、命令の組に対応する分岐予測情報をストアするように構成された１次レベル分岐予測キャッシュが、プロセッサに設けられる。さらに、１次レベルキャッシュから排除された分岐予測情報をストアするために２次レベル分岐予測キャッシュが使用される。２次レベル分岐予測キャッシュは、１次レベルキャッシュから排除された情報の一部（subset）のみをストアするように構成されている。１次レベルキャッシュから排除され、２次レベルキャッシュにストアされない分岐予測情報は破棄される。１次レベルキャッシュでミスが発生すると、２次レベルキャッシュが、ミスに対応する分岐予測情報を格納しているかどうかが判定される。対応する分岐予測情報が２次レベルキャッシュで検出された場合、２次レベルキャッシュから検出された分岐予測情報がフェッチされて、完全な分岐予測情報の生成に使用される。この予測情報は、のちに分岐予測の作成に使用され得る。一実施形態においては、２次レベルキャッシュからフェッチした命令のデコードを実行するデコード回路系が設けられ得る。２次レベルキャッシュからフェッチした命令のデコードが、完全な分岐予測情報の再生成の際に使用され得る。サイズの小さいキャッシュを使用して、１次レベル分岐予測キャッシュから排除された分岐予測情報をストアすることができ有利である。さらに、１次レベルキャッシュでミスが発生した場合に、２次レベルキャッシュにストアされているデータから、完全な分岐予測を迅速に再生成することができる。

本発明の他の目的ならびに利点は、添付の図面を参照しつつ下記に記載する本発明の詳細な説明を参照すれば明白となる。

本発明は、様々に変形されたり代替形態を取り得るが、その特定の実施形態が、例として図中に図示され、かつ本明細書に詳細に記載される。しかし、図面および詳細な説明は、開示の実施形態に本発明を限定することを意図するものではなく、本発明が添付の特許請求の範囲によって規定される本発明の趣旨ならびに範囲に含まれる全ての変形例、均等物および代替例を含むことが意図にあることが理解されるべきである。

プロセッサの概略
図１を参照すると、プロセッサ１０の一実施形態のブロック図が示される。別の実施形態も可能であり、考慮される。プロセッサ１０は、プリフェッチユニット１２、分岐予測ユニット１４、命令キャッシュ１６、命令整列ユニット１８、複数個のデコードユニット２０Ａ〜２０Ｃ、複数個のリザベーションステーション２２Ａ〜２２Ｃ、複数個の機能ユニット２４Ａ〜２４Ｃ、ロード／ストアユニット２６、データキャッシュ２８、レジスタファイル３０、リオーダーバッファ３２、ＭＲＯＭユニット３４およびバスインターフェイスユニット３７を備える。本明細書において、後に文字が付された参照符号によって参照される複数の要素は、参照符号のみによって集合的に参照される。例えば、デコードユニット２０Ａ〜２０Ｃは、デコードユニット２０として集合的に参照される。

プリフェッチユニット１２は、バスインターフェイスユニット３７から命令を受け取るために同ユニットに結合され、さらに命令キャッシュ１６および分岐予測ユニット１４にも結合されている。同様に、分岐予測ユニット１４は命令キャッシュ１６に結合されている。さらに、分岐予測ユニット１４は、デコードユニット２０および機能ユニット２４に結合されている。命令キャッシュ１６は、さらにＭＲＯＭユニット３４および命令整列ユニット１８に結合されている。さらに、命令整列ユニット１８は、デコードユニット２０に結合されている。各デコードユニット２０Ａ〜２０Ｃは、ロード／ストアユニット２６と、それぞれ対応するリザベーションステーション２２Ａ〜２２Ｃとに結合されている。リザベーションステーション２２Ａ〜２２Ｃは、それぞれ対応する機能ユニット２４Ａ〜２４Ｃにさらに結合されている。さらに、デコードユニット２０とリザベーションステーション２２とは、レジスタファイル３０およびリオーダーバッファ３２に結合されている。機能ユニット２４は、ロード／ストアユニット２６、レジスタファイル３０およびリオーダーバッファ３２とも結合されている。データキャッシュ２８は、ロード／ストアユニット２６とバスインターフェイスユニット３７とに結合されている。バスインターフェイスユニット３７は、Ｌ２キャッシュへのＬ２インターフェイスとバスとにさらに結合されている。最後に、ＭＲＯＭユニット３４はデコードユニット２０に結合されている。

命令キャッシュ１６は、命令をストアするために設けられた高速キャッシュメモリである。命令キャッシュ１６から命令がフェッチされて、デコードユニット２０にディスパッチされる。一実施形態においては、命令キャッシュ１６は、６４バイト（１バイトは８つのバイナリビットを含む）のラインを有する２ウェイアソシエーティブ構造に、最大６４キロバイトの命令をストアできるように構成されている。別法として、他の任意の構成およびサイズを使用してもよい。例えば、命令キャッシュ１６は、フルアソシエーティブ構成、セットアソシエーティブ構成、ダイレクトマップド構成のいずれでも実装可能であるという点が注目される。

プリフェッチユニット１２によって、命令が命令キャッシュ１６にストアされる。プリフェッチ方式では、命令は、その命令が要求される前に命令キャッシュ１６からプリフェッチされ得る。種々のプリフェッチ方式が、プリフェッチユニット１２によって採用され得る。命令キャッシュからフェッチされた命令は、スキャナ／整列器（scanner/aligner）に渡される。命令は、初めてフェッチされるときには、プリデコードタグが付けられていない。この場合、スキャナ／整列器は、１クロックにつき４バイトをデコードユニット２０に渡す。デコードユニット２０がプリデコードされていない命令をコアにディスパッチすると、デコードユニットは、この命令に対応するプリデコードデータを生成し得る。このデータは命令の境界を示すものである。

次に、可変バイト長の命令セットを使用するプロセッサ１０の一実施形態のプリデコードタグのエンコード方式（encoding）を以下に記載する。可変バイト長の命令セットとは、命令が占めるバイト数が命令によって変わり得る命令セットのことである。プロセッサ１０の一実施形態が使用する可変バイト長の命令セットの例に、ｘ８６命令セットがある。

本例に示すエンコード方式においては、あるバイトが命令の最終バイトである場合、このバイトのエンドビットがセットされる。デコードユニット２０が直接デコード可能な命令は「ファストパス」命令と呼ばれる。一実施形態によると、それ以外のｘ８６命令はＭＲＯＭ命令と呼ばれる。例えば、ＭｏｄＲ／Ｍバイトおよび即値バイトの２つのプリフィックスバイトを含むファストパス命令は、下記のようなエンドビットを有し得る。
エンドビット００００１

ＭＲＯＭ命令とは、複雑過ぎるためにデコードユニット２０がデコードすることができないと判断された命令のことである。ＭＲＯＭ命令は、ＭＲＯＭユニット３４を呼び出すことにより実行される。より詳細には、ＭＲＯＭユニット３４は、ＭＲＯＭ命令が出現すると、この命令をパース（parse）し、定義済みのファストパス命令のサブセットを発行して、所望の操作が実行されるようにする。ＭＲＯＭユニット３４は、ファストパス命令のサブセットをデコードユニット２０にディスパッチする。

プロセッサ１０は、条件付き分岐命令に後続する命令を投機的にフェッチするために分岐予測を使用する。分岐予測処理を実行するために分岐予測ユニット１４が設けられる。一実施形態においては、分岐予測ユニット１４は、命令キャッシュ１６のキャッシュラインの１６バイト部分につき、最大３個の分岐ターゲットアドレスと、分岐の成立／不成立の予測とをキャッシュ可能な分岐ターゲットバッファを使用する。例えば、分岐ターゲットバッファには、２０４８個のエントリが含まれていても、これ以外の適切な数のエントリが含まれていてもよい。プリフェッチユニット１２は、特定のラインがプリデコードされたときに、最初の分岐ターゲットを決定する。その後、キャッシュライン内の命令の実行によって、このキャッシュラインに対応する分岐ターゲットが更新され得る。命令キャッシュ１６は、フェッチされようとしている命令アドレスを示す情報（indication）を提供し、これによって分岐予測ユニット１４は、選択すべき分岐ターゲットアドレスを決定して、分岐予測を作成し得る。デコードユニット２０と機能ユニット２４とは、分岐予測ユニット１４に更新情報を提供する。デコードユニット２０は、分岐予測ユニット１４によって予測されなかった分岐命令を検出する。機能ユニット２４は、分岐命令を実行して、予測した分岐方向が誤っているかどうかを判定する。この分岐方向を「辿る」可能性があり、この場合、後続の命令が、分岐命令のターゲットアドレスからフェッチされる。逆に、この分岐方向を「辿らない」可能性もあり、この場合、後続の命令が、分岐命令の後のメモリ場所からフェッチされる。予測誤りの分岐命令が検出されると、この誤って予測された分岐に後続する命令が、プロセッサ１０の種々のユニットから破棄される。別法による構成においては、分岐予測ユニット１４が、デコードユニット２０および機能ユニット２４の代わりにリオーダーバッファ３２と結合されており、分岐予測ミスの情報をリオーダーバッファ３２から受け取ってもよい。分岐予測ユニット１４によって、種々の適切な分岐予測アルゴリズムが使用され得る。

命令キャッシュ１６からフェッチされた命令は、命令整列ユニット１８に送られる。命令キャッシュ１６から命令がフェッチされる際に、これに対応するプリデコードデータがスキャンされ、フェッチされようとしている命令に関する情報が命令整列ユニット１８に（およびＭＲＯＭユニット３４に）提供される。命令整列ユニット１８はプリデコードデータをスキャンして、各デコードユニット２０に送る命令を並び替える。一実施形態においては、命令整列ユニット１８は、１６個の命令バイトの組２つに含まれる命令を並び替えてデコードユニット２０に送る。デコードユニット２０Ａは、（プログラムの順序において）デコードユニット２０Ｂ，２０Ｃが同時に受け取る命令に先行する命令を受け取る。同様に、デコードユニット２０Ｂは、プログラムの順序においてデコードユニット２０Ｃが同時に受け取る命令に先行する命令を受け取る。

デコードユニット２０は、命令整列ユニット１８から受け取った命令をデコードするように構成されている。レジスタオペランド情報が検出されて、レジスタファイル３０およびリオーダーバッファ３２に転送される。さらに、命令が１つ以上のメモリ操作の実行を要求する場合、デコードユニット２０は、このメモリ操作をロード／ストアユニット２６にディスパッチする。各命令がデコードされて、機能ユニット２４用の制御値の組が生成される。この制御値は、オペランドアドレス情報、ならびに変位データまたは即値データ（命令に含まれていることがある）と共に、リザベーションステーション２２にディスパッチされる。特定の実施形態においては、各命令がデコードされて最大２つの操作が生成され、これらの操作は機能ユニット２４Ａ〜２４Ｃによって別個に実行され得る。

プロセッサ１０はアウトオブオーダー実行に対応しており、このため、レジスタの読み出し操作および書き込み操作のために、プログラムの元のシーケンスを追跡するためにリオーダーバッファ３２を使用して、レジスタリネーミングを実行し、投機的命令実行と分岐予測ミスから回復できるようにすると共に、正確な例外を可能にする。レジスタの更新を伴う命令がデコードされると、リオーダーバッファ３２内に一時的な記憶場所が確保され、これにより投機的なレジスタの状態がストアされる。分岐予測が正しくない場合、誤って予測された経路に沿って投機的に実行された命令による結果が、レジスタファイル３０に書き込まれる前に、これをバッファ内で無効化することができる。同様に、特定の命令が例外を発生させる場合、この特定の命令に後続する命令を破棄することができる。このように、例外は「厳密」である（すなわち、例外を発生させるこの特定の命令に後続する命令が、例外が発生する前に完了することはない）。特定の命令が、プログラムの順序においてこの命令に先行する命令より先に投機的に実行されるという点が注目される。先行する命令は、分岐命令のこともあれば、例外を発生させる命令のこともあり、この場合、投機的な実行の結果がリオーダーバッファ３２によって破棄され得る。

デコードユニット２０の出力において提供される命令制御値と、即値データまたは変位データとは、対応するリザベーションステーション２２に直接転送される。一実施形態においては、各リザベーションステーション２２は、対応する機能ユニットへの発行を待機している保留中の命令の命令情報（すなわち、命令制御値のほか、オペランド値、オペランドタグおよび／または即値データ）を、最大５つの命令分だけ保持することができる。図１に示す実施形態については、各リザベーションステーション２２は、専用の機能ユニット２４に対応しているという点が注目される。したがって、リザベーションステーション２２および機能ユニット２４によって、３つの専用の「発行位置（issue position）」が形成される。つまり、発行位置０がリザベーション２２Ａおよび機能ユニット２４Ａによって形成される。整列されてリザベーションステーション２２Ａにディスパッチされた命令は、機能ユニット２４Ａによって実行される。同様に、発行位置１がリザベーションステーション２２Ｂおよび機能ユニット２４Ｂによって形成され、発行位置２がリザベーションステーション２２Ｃおよび機能ユニット２４Ｃによって形成される。

特定の命令がデコードされたときに、要求されたオペランドがレジスタ位置である場合は、レジスタのアドレス情報が、リオーダーバッファ３２とレジスタファイル３０とに同時に転送される。一実施形態においては、リオーダーバッファ３２は、デコードユニットからのオペランド要求を受け取るフューチャファイル（future file）も備える。ｘ８６レジスタファイルは、３２ビットの実レジスタを８つ（すなわち、通常はＥＡＸ、ＥＢＸ、ＥＣＸ、ＥＤＸ、ＥＢＰ、ＥＳＩ、ＥＤＩおよびＥＳＰ）有するということを当業者は理解するであろう。ｘ８６プロセッサアーキテクチャを採用しているプロセッサ１０の実施形態においては、レジスタファイル３０は、３２ビットの実レジスタの各々に対する記憶場所を有する。レジスタファイル３０に、ＭＲＯＭユニット３４が使用する付加的な記憶場所が設けられてもよい。リオーダーバッファ３２は、これらのレジスタの内容を変更し、これによってアウトオブオーダー実行を可能にする結果用に、一時的な記憶場所を有する。リオーダーバッファ３２内の一時的な記憶場所が、デコード時に、実レジスタのうちの１つの内容を変更するように判定される各命令のために確保される。このため、特定のプログラムの実行中のさまざまな点において、リオーダーバッファ３２は、所定のレジスタの投機的に実行された内容を格納している場所を１つ以上有し得る。所定の命令のデコードの後に、リオーダーバッファ３２が、所定の命令において、オペランドとして使用されているレジスタに割り当てられた以前の場所を１つ以上有することが判定された場合、リオーダーバッファ３２は、１）最後に割り当てられた場所にある値か、または２）そのうち前の命令を実行する機能ユニットによって値が未だ生成されていない場合は最後に割り当てられた場所に対するタグ、のいずれかを対応するリザベーションステーションに転送する。リオーダーバッファ３２が、所定のレジスタ用に確保されている場所を有する場合、オペランド値（またはリオーダーバッファタグ）は、レジスタファイル３０ではなくリオーダーバッファ３２から提供される。要求されるレジスタのために確保された場所がリオーダーバッファ３２に存在しない場合、レジスタファイル３０から値が直接取得される。このオペランドがメモリ場所に対応している場合、ロード／ストアユニット２６を介して、このオペランドの値がリザベーションステーションに提供される。

特定の実施形態においては、リオーダーバッファ３２は、並列的にデコードされた複数の命令を１つの単位としてストアおよび操作するように構成される。ここでは、この構成を「ライン指向型（line-oriented）」と呼ぶ。複数の命令をまとめて操作することによって、リオーダーバッファ３２内に採用されているハードウェアを簡略化することができる。例えば、本実施形態に使用されているライン指向型のリオーダーバッファは、１つ以上の命令が命令整列ユニット２０によって発行（issue）されたときは必ず、３つの命令（各デコードユニット２０から１つずつ）に関する命令情報に十分足る記憶領域を割り当てる。これに対して、従来のリオーダーバッファでは、実際にディスパッチされる命令の数に応じて、割り当てられる記憶領域の大きさが変わる。可変の記憶領域を割り当てるために、比較的多くの論理ゲートが必要となることがある。並列的にデコードされた複数の命令のうちの各々が実行されると、これらの命令の結果が、レジスタファイル３０に同時にストアされる。この記憶領域は解放されて、並列的にデコードされる複数の命令の別の組に割り当て可能になる。さらに、制御論理が、同時にデコードされたいくつかの命令に分散されるため、命令１つにつき使用される制御論理回路系の数が減る。特定の命令を識別するリオーダーバッファタグを、ラインタグとオフセットタグとの２つのフィールドに分けてもよい。ラインタグは、この特定の命令を含む、並列的にデコードされた複数の命令のセットを識別し、オフセットタグは、このセットの中のどの命令が特定の命令に対応しているかを識別する。命令の結果をレジスタファイル３０にストアして、対応する記憶領域を解放する操作は、この命令の「リタイヤ」と呼ばれているという点が注目される。フューチャファイルを使用して、レジスタファイル３０の投機的状態を保存するなど、プロセッサ１０の様々な実施形態に、任意のリオーダーバッファ構成を使用し得るという点がさらに注目される。

上記したように、リザベーションステーション２２は、対応する機能ユニット２４によって命令が実行されるまで、その命令をストアする。（ｉ）命令のオペランドが提供され、かつ（ｉｉ）同じリザベーションステーション２２Ａ〜２２Ｃ内にあり、プログラムの順序においてこの命令に先行する命令にオペランドが提供されていない場合、命令が実行のために選択される。命令が機能ユニット２４のうちの１つによって実行された場合、この命令の結果が、この結果を待機しているリザベーションステーション２２のいずれかに直接転送されると同時に、この結果がリオーダーバッファ３２を更新するために送られる（この方法は一般に「結果転送」と呼ばれる）という点が注目される。関連する結果が転送されるクロックサイクルの間に、命令が実行のために選択されて、機能ユニット２４Ａ〜２４Ｃに送られ得る。この場合、リザベーションステーション２２は、転送された結果を機能ユニット２４に送信する。命令が、複数の操作にデコードされて、機能ユニット２４によって実行される実施形態においては、これらの操作が互いに独立してスケジューリングされ得る。

一実施形態においては、各機能ユニット２４は、加算および減算の整数演算操作のほか、シフト、ローテート、論理演算および分岐処理も実行するように構成されている。特定の命令について、デコードユニット２０によってデコードされた制御値を受けて、操作が実行される。浮動小数点演算を処理するために、浮動小数点演算ユニット（図示せず）が使用され得るという点が注目される。この浮動小数点演算ユニットは、ＭＲＯＭユニット３４またはリオーダーバッファ３２から命令を受け取って、次にリオーダーバッファ３２と通信を行って命令を遂行するコプロセッサとしても動作し得る。さらに、機能ユニット２４は、ロード／ストアユニット２６によって実行されるロードメモリ操作およびストアメモリ操作のために、アドレス生成を行うように構成され得る。特定の実施形態においては、各機能ユニット２４は、アドレスを生成するアドレス生成ユニットと、それ以外の機能を実行する実行ユニットとを備え得る。この２つのユニットは、あるクロックサイクルの間に別の命令または操作を独立して処理することができる。

また、各機能ユニット２４は、条件付き分岐命令の実行に関する情報を、分岐予測ユニット１４に提供する。分岐予測が正しくない場合、分岐予測ユニット１４は、命令処理パイプラインに既に入っている、予測ミスとなった分岐に後続する命令を破棄して、必要な命令を命令キャッシュ１６またはメインメモリからフェッチさせる。このような場合、投機的に実行され、ロード／ストアユニット２６とリオーダーバッファ３２とに一時的にストアされた命令を含め、元のプログラムシーケンスにおいて、予測ミスとなった分岐命令に後続する命令の結果が破棄されるという点が注目される。機能ユニット２４からリオーダーバッファ３２に分岐の実行結果が提供されてもよく、この結果が、分岐予測ミスを機能ユニット２４に通知し得るという点がさらに注目される。

レジスタ値が更新されようとしている場合、機能ユニット２４によって生成された結果は、リオーダーバッファ３２に送られ、メモリ場所の内容が変更される場合はロード／ストアユニット２６に送られる。結果がレジスタにストアされる必要がある場合、リオーダーバッファ３２は、命令がデコードされたときにレジスタの値のために確保された場所に、結果をストアする。機能ユニット２４およびロード／ストアユニット２６から結果を転送するために、複数の結果バス３８が設けられる。結果バス３８は、生成された結果のほかに、実行されようとしている命令を識別するリオーダーバッファタグを伝達する。

ロード／ストアユニット２６は、機能ユニット２４とデータキャッシュ２８との間のインターフェイスを提供する。一実施形態においては、ロード／ストアユニット２６は、２つのロード／ストアバッファを備えて構成される。第１のロード／ストアバッファは、データキャッシュ２８に未だアクセスしていない実行待ちのロードおよびストアに対応するデータおよびアドレス情報用の記憶場所を備える。第２のロード／ストアバッファは、データキャッシュ２８に既にアクセスしている実行待ちのロードおよびストアに対応するデータおよびアドレス情報用の記憶場所を備える。例えば、第１のバッファは１２個の場所を備え得、第２のバッファは３２個の場所を備え得る。デコードユニット２０は、ロード／ストアユニット２６へのアクセスを調停（arbitrate）する。第１のバッファが満杯の場合は、デコードユニットは、待機中のロード要求またはストア要求に関する情報を格納するための空きが、ロード／ストアユニット２６に生じるまで待機する。また、ロード／ストアユニット２６は、データの一貫性が確実に維持されるように、待機中のストアメモリ操作に対するロードメモリ操作の依存関係を検査する。メモリ操作とは、プロセッサ１０とメインメモリサブシステムとの間で行われるデータ転送である。メモリ操作は、メモリにストアされているオペランドを利用する命令の結果生じることもあれば、データ転送のみを生じさせるが他の操作を生じさせないロード／ストア命令の結果生じることもある。さらに、ロード／ストアユニット２６は、セグメントレジスタやｘ８６プロセッサアーキテクチャによって規定されるアドレス変換機構に関わるその他のレジスタなどの特殊レジスタのための、特別なレジスタ記憶領域を備えていてもよい。

データキャッシュ２８は、ロード／ストアユニット２６とメインメモリサブシステムとの間で転送されるデータを一時的にストアするために設けられる高速キャッシュメモリである。一実施形態においては、データキャッシュ２８は、２ウェイセットアソシエーティブ構造において、最大６４キロバイトのデータをストアできるだけの容量を有する。データキャッシュ２８は、セットアソシエーティブ構成、フルアソシエーティブ構成、ダイレクトマップド構成、または任意の構成かつ任意のサイズのその他の構成など、様々なメモリ構成に実装可能であるということが理解される。

ｘ８６プロセッサアーキテクチャを使用するプロセッサ１０の特定の実施形態においては、命令キャッシュ１６およびデータキャッシュ２８は、リニアアドレス指定されて物理タグが付される。リニアアドレスは、命令によって指定されるオフセットと、ｘ８６のアドレス変換メカニズムのセグメント部分によって指定されるベースアドレスとから生成される。リニアアドレスは、メインメモリにアクセスするために、随意的に物理アドレスに変換されることがある。リニアアドレスから物理アドレスへの変換は、ｘ８６のアドレス変換メカニズムのページング部分によって指定される。物理アドレスと物理タグとが比較されて、ヒット／ミス状態が判定される。

バスインターフェイスユニット３７は、バスを介して、プロセッサ１０とコンピュータシステム内の他の部品とを通信させるように構成されている。例えば、バスは、デジタルイクイップメントコーポレーション（Digital Equipment Corporation）によって開発されたＥＶ−６バスと互換性を有するバスであり得る。あるいは、パケットベースのリンク、一方向リンクまたは双方向リンクなど、任意の適した相互接続構造を使用することができる。また、オプションのＬ２キャッシュインターフェイスを使用して、レベル２キャッシュとインターフェイスを取ってもよい。

以下の説明では、ｘ８６マイクロプロセッサアーキテクチャを例に採り上げる。しかし、ここに記載する分岐予測技法（technique）は、どのようなマイクロプロセッサアーキテクチャ内でも使用することができ、そのような実施形態も考察される。ｘ８６マイクロプロセッサアーキテクチャでは、シングルバイトのオペコードからなるサブルーチンリターン命令（ＲＥＴ命令など）が定義されているという点が注目される。サブルーチンリターン命令は、その分岐ターゲットアドレスを、ＥＳＰレジスタによって示されるスタックの最上部から取得するように指示する。場合によっては、このシングルバイトのＲＥＴ命令の処理が特別な問題を引き起こし得る。このような場合に対処するメカニズムを、下記に詳細に示す。

分岐予測の概略
図２に、分岐予測ユニット１４の一実施形態の一部を示す。図２に示した部分のほか、分岐予測ユニット１４の他の実施形態も可能であり、考慮される。図２に示すように、分岐予測ユニット１４は、グローバル予測記憶域２０５、ローカル予測記憶域２０６、分岐ターゲット記憶域２０８、更新論理２００，２０２、グローバル履歴シフトレジスタ（GHSR）２０４、ラインバッファ２１０、戻りアドレススタック（RAS）２３０、連続アドレス生成器（SEQ）２３２、予測論理２２０、犠牲キャッシュ２６０、分岐アドレス計算器２７０、命令キャッシュ１６、Ｌ２キャッシュ１８２８、およびデコーダ回路４００を備える。犠牲キャッシュ２６０は、ローカル予測記憶域２０６から排除された分岐予測情報をストアするように構成されたレベル２（Ｌ２）キャッシュである。一実施形態においては、犠牲キャッシュ２６０は、以前はローカル予測記憶域２０６に保持されていたが、別のデータを記憶する領域を確保するために排除されたデータのみをキャッシュするように構成されている。ローカル予測記憶域２０６と犠牲キャッシュ２６０とがデータを重複して記憶することがないため、より多くの分岐予測情報を保持することができ有利である。

グローバル予測記憶域２０５、ローカル予測記憶域２０６、分岐ターゲット記憶域２０８、命令キャッシュ１６、予測論理２２０、分岐アドレス計算器２７０、およびラインバッファ２１０は、フェッチアドレスマルチプレクサ２２２から出力されるフェッチアドレスバス２３６に結合されている。グローバル履歴シフトレジスタ２０４は、バス２３４を介してグローバル予測記憶域２０５およびラインバッファ２１０に結合されている。更新論理２００は、グローバル予測記憶域２０５、ローカル予測記憶域２０６および分岐ターゲット記憶域２０８に結合されている。ラインバッファ２１０は、バス２４８を介して更新論理２００，２０２に結合されている。さらに、更新論理２０２は、バス２４６を介してグローバル履歴シフトレジスタ２０４に結合されている。リオーダーバッファ３２は、選択制御を行い、マルチプレクサ２２２にアドレスを転送する。また、リオーダーバッファ３２は、更新論理２００および更新論理２０２に、分岐の予測された挙動と実際の挙動とに関する情報を提供する。グローバル予測記憶域２０５とローカル予測記憶域２０６とは、それぞれバス２３８，２４２を介して予測論理２２０に結合されている。予測論理２２０は、バス２５０を介して分岐アドレス計算器２７０に、選択信号２４０を介してマルチプレクサ２１２に結合されている。命令キャッシュ１６は、バス２４１を介して分岐アドレス計算器２７０に結合されている。マルチプレクサ２１２の出力は、バス２４３を介して分岐アドレス計算器２７０およびマルチプレクサ２２１に結合されている。また、分岐アドレス計算器２７０は、バス２４５および選択信号２２３を介してマルチプレクサ２２１に結合されている。最後に、マルチプレクサ２２１からの出力はマルチプレクサ２２２に結合されている。

一般に、分岐予測ユニット１４の図２に示す部分の基本的な操作は下記のとおりである。フェッチアドレス２３６が、ラインバッファ２１０、ローカル予測記憶域２０６、ターゲットアレイ記憶域２０８および分岐アドレス計算器２７０に送られる。さらに、フェッチアドレス２３６の一部がグローバル履歴２３４と結合されて、インデックスが生成され、グローバル予測記憶域２０５に送られる。さらに、フェッチアドレス２３６の部分２２５が予測論理２２０に送られる。グローバル予測記憶域２０５はグローバル予測２３８を送り、ローカル予測記憶域２０６はローカル予測２４２を送り、ターゲットアレイ２０８は受け取ったフェッチアドレスに対応するターゲットアドレスを送る。ローカル予測記憶域２０６から送られるローカル予測２４２は、予測論理２２０が分岐予測を作成するために使用する情報を提供する。同様に、グローバル予測記憶域２０５は、分岐予測の作成に使用されるグローバル予測２３８を予測論理２２０に送る。一実施形態においては、動的な挙動を示す分岐について、グローバル予測２３８によって、ローカル予測記憶域２０６から提供されるローカル予測２４２が無効にされ得る。動的な挙動を示す分岐の分類については後述する。最後に、予測論理２２０は、新しい命令のフェッチに使用される次のフェッチアドレス２４３を選択する信号をマルチプレクサ２１２に送る。場合によっては、マルチプレクサ２１２によって送信されるフェッチアドレス２４３が、現在の分岐予測の唯一のフェッチアドレスのこともある。しかし、分岐アドレス計算器２７０が、マルチプレクサ２１２によって送信されるフェッチアドレス２４３が誤っていたことを検出すると、現在の分岐予測に対応する第２のフェッチアドレス２４５を送信することもある。そのような場合、分岐アドレス計算器２７０は、フェッチアドレス２４５を選択して、マルチプレクサ２２１から出力させるための信号２２３を送信し得る。このように、予測ミスが初期の段階で検出されて訂正される。

動的な挙動およびグローバル分類
上記したように、一実施形態においては、分岐予測ユニット１４にグローバル予測メカニズムが含まれ得る。グローバル予測メカニズムの詳細は、同時係属中であって譲受人が共通する特許出願「グローバル履歴分岐予測における条件付き分岐の動的分類（Dynamic Classification of Conditional Branches in Global History Branch Prediction）」、米国特許出願第０９／４４１，６３０号、１９９９年１１月１６日出願、ズラスキージュニアら（Zuraski, Jr. et al.）に記載されている。同開示は、参照として本願に包含される。上記したように、プリフェッチユニット１２は、分岐命令を検出して、分岐命令に対応する分岐情報を分岐予測ユニット１４に送るように構成され得る。条件付き分岐が検出されると、更新論理２００は、この分岐予測に対応するエントリをローカル予測記憶域２０６内に作成し、新たに作成したこの分岐予測エントリを「分岐不成立」に初期化し得る。一実施形態においては、ローカル予測記憶域２０６は、分岐マーカーを含む分岐予測情報をストアし得る。この情報は、分岐予測を作成して、分岐ターゲット記憶域２０８、連続アドレス２３２、または戻りスタックアドレス２３０にストアされている複数の分岐ターゲットアドレスのうちから行き先を選択するために使用される。ローカル予測記憶域２０６内に分岐のエントリを作成する際に、予測分岐方向が「分岐不成立」に初期化され、これと対応する分岐マーカーが、連続アドレス２３２を示すように初期化される。このほかに、条件付き分岐に対応するエントリがラインバッファ２１０内に作成される。ラインバッファのエントリには、グローバル履歴、フェッチアドレス、グローバル予測およびグローバルビットが含まれ得る。

ローカル予測記憶域２０６にある分岐予測が「分岐不成立」の場合、マルチプレクサ２１２から連続アドレス２３２が送られる。最終的な予測２５０が、更新論理２０２に送られ、更新論理２０２は、動的であると分類された予測分岐方向を、グローバル履歴シフトレジスタ２０４に移す。ローカル分岐予測のエントリが「分岐不成立」の場合、最終的な予測２５０は「分岐不成立」を示し、信号２４０は、マルチプレクサ２１２からの連続アドレス２３２を次のフェッチアドレスとして選択する。この分岐予測のエントリが分岐予測ユニット１４から削除される前に、この分岐が次に実行されるとき、予測分岐方向は「分岐不成立」であり、次のフェッチアドレスとして連続アドレス２３２が送られる。リタイヤ時に、ラインバッファ２１０内の対応するエントリが、更新論理２００および更新論理２０２に送られ、ラインバッファ２１０から削除される。ラインバッファのエントリが、分岐が非動的であると分類されていることを示し、リオーダーバッファ３２が、分岐予測が的中したことを示す場合、更新論理２００または２０２によって更新が実行されることはない。しかし、分岐が非動的であると分類されており、分岐予測が外れた場合、予測ミスとなった分岐に対応する分岐予測が更新されて、以下に記載するようにグローバル履歴シフトレジスタ２０４が更新される。

成立した非動的な分岐
リオーダーバッファ３２は、リタイヤ時または予測ミスの発生時に、分岐の挙動に関する情報を更新論理２００に送る。また、ラインバッファ２１０も、更新論理２００，２０２にラインバッファのエントリを送る。ラインバッファの分岐のエントリが、分類が非動的であると分類されており、「分岐不成立」と予測されていることを示し、かつリオーダーバッファ３２が、対応する分岐の予測が外れたことを示す場合、更新論理２００は、予測ミスとなった分岐に対応する分岐予測のエントリを更新する。更新論理２００は、ローカル予測記憶域２０６内の分岐予測を「分岐不成立」から「分岐成立」に更新し、分岐ターゲットアドレスを分岐ターゲット記憶域２０８にストアする。ストアした分岐ターゲットアドレスに対応する「動的」（すなわち「グローバル」）ビットが、分岐が静的すなわち非動的であることを示すように初期化される。この値は、２進数の０によって表され得る。この分岐予測のエントリが分岐予測ユニット１４から削除される前に、この分岐が次に実行されたとき、分岐予測のエントリは「分岐成立」を示し、分岐は非動的として分類されている。分岐が「分岐成立」と予測され、非動的であると分類されている場合、予測論理２２０は、マルチプレクサ２１２からターゲットアドレスを選択する。上記と同様に、分岐予測が正しい場合は、更新論理２００または２０２によって分岐予測を更新する必要はない。これに対して、「分岐成立」と予測された非動的な分岐が成立しなかった場合、分岐予測のエントリとグローバル履歴シフトレジスタ２０４とが更新される。

動的分岐
非動的であると分類され、かつ「分岐成立」と予測された分岐の予測が外れた場合、更新論理２００は、ローカル予測記憶域２０６内の、予測ミスとなった分岐に対応する動的ビットを更新して、分岐を動的すなわちグローバルであると分類する。さらに、更新論理２００は、グローバル予測記憶域２０４内の、予測ミスとなった分岐に対応するグローバル予測エントリを、「分岐不成立」に更新する。また、更新論理２０２は、分岐が不成立だったことを示すようにグローバル履歴シフトレジスタ２０４を更新する。一実施形態においては、グローバル履歴シフトレジスタ２０４は、最新の８個の動的分岐の挙動を記録する。

動的分岐がフェッチされると、ローカル予測記憶域２０６、ターゲットアレイ２０８およびラインバッファ２１０にフェッチアドレス２３６が送られる。さらに、このフェッチアドレスは、グローバル履歴シフトレジスタ２０４の内容と結合されて、インデックス２０３が生成され、これがグローバル予測記憶域２０５に送られる。また、グローバル履歴シフトレジスタ２０４の内容は、バス２３４を介してラインバッファ２１０にも送られる。一実施形態においては、フェッチアドレス２３６のビット９〜４と、グローバル履歴シフトレジスタ２０４の内容とを連結することによってインデックス２０３が生成される。論理和または排他的論理和を求めるなど、インデックスを生成する別の方法も同様に考察される。このインデックスを基にグローバル予測記憶域２０５のエントリが選択されて、このエントリがラインバッファ２１０、更新論理２０２およびマルチプレクサ２２０に送られる。グローバル予測記憶域２０４から送られた予測分岐方向が、更新論理２０２によってグローバル履歴シフトレジスタ２０４に移される。例えば、２進数の１は「分岐成立」を、２進数の０は「分岐不成立」を表し得る。対応する動的ビットが、分岐がグローバルであると分類されていることを示し、かつグローバル予測が「分岐成立」を示す場合、マルチプレクサ２１２から送られるターゲットアドレスが次のフェッチアドレスとして選択される。グローバル予測が「分岐不成立」を示す場合、マルチプレクサ２１２から、連続アドレス２３２が次のフェッチアドレスとして選択される。

リタイヤ時に、リオーダーバッファ３２は更新論理２００および更新論理２０２に分岐情報を送る。さらに、ラインバッファ２１０は、対応する分岐情報を更新論理２０２に送る。リオーダーバッファ３２が、動的分岐の予測が正しいことを示す場合、更新論理２００は、分岐のこの挙動を示すためにグローバル予測のエントリ２０５を変更する。一実施形態においては、グローバル分岐予測のエントリには飽和カウンタが含まれる。このカウンタは２ビット長で、分岐が成立するとインクリメントされ、分岐が成立しないとデクリメントされ得る。この指標（indicator）を使用して、「分岐成立の可能性大（strongly taken）」、「分岐成立の可能性小（weakly taken）」、「分岐不成立の可能性大（strongly not taken）」、「分岐不成立の可能性小（weakly not taken）」を表すことができる。動的分岐の予測が外れた場合、更新論理２００は、分岐のこの挙動を示すためにグローバル予測のエントリ２０５を更新する。さらに、更新論理２０２は、予測ミスの発生時に、動的分岐の予測による挙動ではなく実際の挙動を反映するようにグローバル履歴シフトレジスタ２０４を修正する。

犠牲分岐予測用のキャッシュ
上記の分岐予測ユニット１４の動作の概略は、対応するフェッチアドレスがローカル予測記憶域２０６に存在する場合の分岐予測を想定している。しかし、受け取ったフェッチアドレスに対応する分岐予測がローカル予測記憶域２０６にない場合もある。次に、このような状況に対処する方法を概説する。

図３は、１次レベル（Ｌ１）分岐予測用の記憶域２０６内に分岐予測のエントリを作成する方法の一実施形態を示すフローチャートであり、存在する分岐予測のエントリを排除することと、排除された分岐予測情報の一部（サブセット）を２次レベル（Ｌ２）記憶域にストアすることとが行われる。２次レベルの分岐予測記憶域２６０を利用することによって、Ｌ１予測記憶域２０６から排除された分岐予測情報を保持できるようになり有利である。特定の分岐に対して正確な予測を作成するには、数多くの分岐の実行を記録した分岐の実行履歴の作成が必要となり得ることを当業者は認めるであろう。このため、排除された分岐予測に対応する分岐予測情報をキャッシュに保持することにより、分岐予測の精度を向上させることができる。Ｌ１記憶域２０６へのデータの再ロードが要求されていることが検出される（判断ブロック３０１）と、分岐予測用の対応するエントリを作成するための空きがＬ１分岐予測記憶域２０６に存在するかどうかが判定される（判断ブロック３０３）。再ロードするデータに対応する、Ｌ１分岐予測記憶域２０６のエントリが既に占有されている場合、現在のエントリが排除され得（ブロック３０５）、排除された分岐予測情報の一部のみがＬ２記憶域２６０にストアされる（ブロック３０７）。再ロードするデータをＬ２記憶域２６０からフェッチする場合（判断ブロック３０９）、Ｌ２記憶域２６０からフェッチされるデータは分岐予測のエントリの一部を有しており、これが対応する分岐予測の完全なエントリ（ブロック３１１）の再生成に使用され得る。次に、再生成されたエントリがＬ１記憶域２０６にストアされ得る（ブロック３１５）。一方、再ロードするデータをＬ２記憶域２６０からフェッチしない場合（判断ブロック３０９）、新しい分岐予測のエントリが初期化され（ブロック３１３）、Ｌ１記憶域にストアされる（ブロック３１５）。

図４は、対応する分岐予測がＬ１分岐予測記憶域に存在しない場合の方法の別の実施形態である。初めに、フェッチアドレスがＬ１分岐予測記憶域２０６に提示される（ブロック４００）。フェッチアドレスが提示されると、提示されたフェッチアドレスに対応する分岐予測がＬ１予測記憶域に存在するかどうかが判定される（判断ブロック４０２）。対応する分岐予測がＬ１記憶域に存在する場合、予測が送られる（ブロック４１８）。しかし、対応する分岐予測がＬ１記憶域２０６にない場合、フェッチアドレスに対応するＬ１予測記憶域２０６のエントリが、別のフェッチアドレスに対応する分岐予測のエントリによって占有されているかどうかが判定される（判断ブロック４０４）。Ｌ１予測記憶域２０６に別のエントリが存在する場合、現在のエントリがＬ１予測記憶域２０６から排除される（ブロック４０６）。Ｌ１予測記憶域の対応するエントリが有効なエントリによって占有されていない場合、Ｌ２予測記憶域２６０に対して、このフェッチアドレスに対応する分岐予測のエントリを要求する（ブロック４０８）。一実施形態においては、Ｌ１予測記憶域２０６とＬ２予測記憶域２６０とに対して同時に要求を行うことができる。対応するエントリがＬ２予測記憶域２６０に存在しない場合（ブロック４１０）、提示されたフェッチアドレス用の、新しい分岐予測のエントリがＬ１予測記憶域２０６に作成され得る（ブロック４１２）。一方、Ｌ２分岐予測記憶域２６０内にこのフェッチアドレスに対応するエントリが存在する場合、Ｌ２のエントリのデータが使用されて、フェッチアドレスに対応する完全な分岐予測が作成される（ブロック４１４）。次に、再作成された分岐予測がＬ１分岐予測記憶域にストアされ（ブロック４１６）、送られて分岐予測の作成に使用される（ブロック４１８）。分岐命令に対応する分岐予測情報を、Ｌ２分岐予測記憶域から復旧することができ、分岐実行の履歴から再生成する必要はなく有利である。さらに、分岐予測に対応する情報の一部のみをＬ２分岐予測用の記憶域２６０にストアするだけで済む。このようにして、Ｌ２分岐予測用の記憶域２６０のサイズを小さくすることができる。

ローカル分岐予測記憶域
一実施形態においては、ローカル予測記憶域２０６は、命令キャッシュ１６と同様な方法によって編成され得る。ローカル予測記憶域２０６にストアされているデータは、ウェイに編成された記憶域のラインから構成され得る。一実施形態においては、ローカル予測記憶域２０６は、命令キャッシュ１６内の全エントリを格納できるだけの十分なサイズを有する。別の実施形態においては、ローカル予測記憶域２０６のサイズは、命令キャッシュ１６のサイズよりも小さくてもよい。例えば、ローカル予測記憶域２０６は、命令キャッシュ１６のサイズの４分の１であり得る。このような実施形態においては、ローカル予測記憶域２０６内の、同じ記憶場所を指している複数のフェッチアドレスのエントリ同士を区別するために、ローカル予測記憶域２０６にローカル予測と共に追加ビットがストアされ得る。一実施形態においては、グローバル予測記憶域２０５が、複数のフェッチアドレスの予測を１つの記憶場所に格納できるように構成され得る。当業者は、ローカル予測記憶域２０６およびグローバル予測記憶域２０５を様々に構成可能であることを容易に理解するであろう。

図５を参照すると、連続する命令バイト５０と、これに対応するローカル予測記憶域２０６のエントリとの組の例を表す図が示される。図５では、命令内の各バイトが、短い垂直線（参照符号５４など）によって表される。さらに、組５０にある命令同士を区切っている線（参照符号５６など）もバイトの境界を示す。図５に示す命令は可変長であり、このため、図５に示す命令を含む命令セットは可変バイト長の命令セットである。換言すれば、この可変バイト長の命令セットの先頭の命令のバイト数は、この命令セットの２番目の命令のバイト数とは異なる。命令セット内の各命令のバイト数が全て等しくなるような固定長の命令セットもあり得る。

図５に示すように、組５０には、非分岐命令ＩＮ０〜ＩＮ４が含まれる。命令ＩＮ０，ＩＮ３，ＩＮ４は２バイト命令である。命令ＩＮ１は１バイト命令であり、命令ＩＮ２は３バイト命令である。このほか、「分岐成立」と予測された３つの分岐命令ＰＢ０，ＰＢ１，ＰＢ２も示されており、これらは全て２バイトを占める。非分岐命令および分岐命令は様々なバイト数をとりうるという点が注目される。

本明細書で使用されるように、アドレスのオフセットは、アドレスの所定数の最下位ビット（least significant bit）を含む。この数は、オフセットが関連しているバイトの組に含まれる各バイトに対して、異なったビットのエンコーディング（コード化）を付与するのに十分な数である。例えば、組５０は、バイト０〜１５の１６バイトを含む。このため、このグループにあるアドレスの最下位の４ビットが、そのアドレスのオフセットを形成している。このアドレスの残りのビットは、メインメモリ内の隣接する他の命令バイトの組から、組５０を識別する。さらに、残りのビットのうちの所定数の最下位ビットが、命令キャッシュ１６によって使用され、組５０をストア可能な記憶場所の行を選択するためのインデックスを形成している。

セット５２は９個の分岐マーカービット０〜８からなるセットの例で、組５０に対応している。セット５２内の９個の分岐マーカービットの各々は、組５０の特定のバイト群に対応しており、「分岐成立」と予測された分岐命令が、対応するバイト群で終端しているかどうかを示す。本図の実施形態においては、分岐マーカービット０は命令バイト０に、分岐マーカービット１は命令バイト１〜２に、分岐マーカービット２は命令バイト３〜４に、分岐マーカービット３は命令バイト５〜６に、分岐マーカービット４は命令バイト７〜８に、分岐マーカービット５は命令バイト９〜１０に、分岐マーカービット６は命令バイト１１〜１２に、分岐マーカービット７は命令バイト１３〜１４に、分岐マーカービット８は命令バイト１５に対応している。分岐マーカービット５２のほかに、分岐マーカービット５２に対応する分岐予測情報４５０も含まれる。分岐予測情報４５０は、「分岐成立」と予測された分岐に対応する情報を含んでおり、以下に詳細に記載するように、分岐予測の作成に使用される。

図５の実施形態においては、成立予測分岐命令（predicted taken branch preduction）が、対応するバイト範囲で終端している場合は、分岐マーカービットが「１」にセットされる。成立予測分岐命令が、分岐マーカービットに対応するバイト範囲で終端していない場合は、この分岐マーカービットが「０」にセットされる。したがって、分岐マーカービット２は、成立予測分岐ＰＢ０が命令バイト範囲３〜４内で終端していることを示す。分岐マーカービット６は、成立予測分岐ＰＢ１が命令バイト範囲１１〜１２内で終端していることを示す。最後に、分岐マーカービット７は、成立予測分岐ＰＢ２が命令バイト範囲１３〜１４内で終端していることを示す。一実施形態においては、分岐マーカービット５２によって、最大３つの成立予測分岐が示され得る。このような実施形態においては、分岐予測情報４５０は、３つの別個の分岐命令に関する情報を格納することができる。この情報４５０は、分岐命令の種類を含むほか、対応する分岐の過去の挙動に関する情報を示し得る。分岐予測情報４５０については、図１５を説明する際に詳述する。

フェッチアドレスがローカル予測記憶域２０６に提示されると、分岐マーカービット５２と分岐情報４５０とからなる組が予測論理２２０に送られ、分岐予測の作成に使用される。一実施形態においては、分岐予測の作成の際に考慮すべき分岐マーカービット５２の識別に、フェッチアドレスのオフセットが使用される。図６を参照すると、分岐マーカービット５２とフェッチアドレスのオフセットとの関係の一実施形態が示される。図６において、列６０２〜６１８を有するテーブルは、オフセットアドレスと、これと対応する分岐マーカービットとを有する。一般に、対応するオフセットが、テーブル内にある条件を満足するかどうかによって、分岐予測の作成の際に分岐マーカービットが考慮されるかどうかが決まる。例えば、列６０２は、アドレスのオフセットが０以下の場合、分岐予測の作成の際に全ての分岐マーカービットが考慮されることを示す。このように、このテーブルは、所定のオフセットについて、考慮される分岐マーカービットの番号の最小値を示している。したがって、オフセットが７の場合、分岐マーカービット４〜８が考慮される。オフセットが１５の場合、分岐マーカービット８のみが考慮される。

図７を参照すると、上記した命令バイトと分岐マーカービットとの関係を表す図が示される。図７には、命令バイト５０と、これと対応する分岐マーカービットとが記載されている。また、命令バイト＃７０２、分岐マーカービット＃７０４、各分岐マーカービットに対応する命令バイト７０６、および各分岐マーカービットに対応するフェッチアドレスのオフセット７０８も記載されている。分岐情報４５０は記載されていない。図５に関して上記したように、「分岐成立」と予測された３つの分岐命令ＰＢ０〜ＰＢ２に対応する分岐マーカービット２，６および７がセットされている。例として、オフセットが３のフェッチアドレスがローカル予測記憶域２０６に提示された場合を考える。この例では、分岐マーカービット２〜８は、全て各ビットの条件（つまり、分岐マーカービット２ではオフセット≦３、分岐マーカービット３ではオフセット≦５など）を満足している。したがって、分岐予測の作成時に、分岐マーカービット２〜８が使用される一方、分岐マーカービット０〜１は、命令シーケンスにおいて現在フェッチされようとしている命令に先行する命令に対応しているため、効率的に無視され得る。このようにして、分岐予測の作成時に考慮すべき分岐マーカービットを、容易に判定できるようになる。

図８は、予測の作成に分岐マーカービット５２を使用する方法の一実施形態を示すものである。図８には、受け取ったフェッチアドレスのオフセット（本図で「ａ」として示される）と、図７に示すオフセット値７０８に相当する値０，１，３，５，７，９，１１，１３および１５とを比較する回路系８０２が記載されている。受け取ったオフセットが、比較対象の値以下である度に、このことを示す信号８０８がＡＮＤゲート８０４に送られる。さらに、各分岐マーカービット５２もＡＮＤゲート８０４に送られる。論理ＡＮＤゲート８０８は、論理ＯＲゲート８０６に結合されており、その出力は、分岐予測が作成されようとしているかどうかを示す。図８の例でも上記と同様に、オフセットが値３に指定されたフェッチアドレスを受け取った場合を考える。図７に示すように、オフセットが３の命令は、成立予測分岐ＰＢ０に対応している。次に、対応する分岐マーカービット５２が、ローカル予測記憶域２０６から図８に示す論理に送られる。回路系８０２は、値が３に指定されたオフセットを受け取って、信号８０８Ｃ〜８０８Ｉをアサートし、ゲート８０４Ｃ〜８０４Ｉが各々これらを受け取る。さらに、分岐マーカービット２，６および７は、２進数値の「１」をゲート８０４Ｃ，８０４Ｇおよび８０４Ｈのそれぞれに送る。残りの分岐マーカービットは、２進数値の「０」を送る。したがって、ゲート８０４Ｃ，８０４Ｇおよび８０４Ｈの各々は、ゲート８０６に２進数値の「１」を送り、この結果、ゲート８０６は、分岐予測が作成されようとしていることを示す２進数値の「１」を送る。

図９は、図８に示す回路系の、動的論理を使用した一実施形態９００を示すものである。当業者は動的論理の動作を容易に理解するであろう。図９には、結合トランジスタ９０２Ａ〜９０２Ｉが含まれており、これらは論理ＡＮＤゲート８０４Ａ〜８０４Ｉにそれぞれ対応する。また、プリチャージされた値を動的論理に供給し得るトランジスタ９０４およびインバータ９０６も記載されている。まず、回路の評価段階の間に、インバータ９０６の出力９０８は、分岐予測が作成されようとしていないことを示す２進数の状態「０」を送る。しかし、少なくとも１つのゲート９０２の入力の両方がアサートされると、インバータ９０６の出力９０８が、分岐予測が作成されようとしていることを示す２進数値の「１」に遷移する。当業者は、同じ動作を達成するために、図９，１０の論理を実装し得る多くの方法を容易に認めるであろう。

分岐マーカービットの更新
一般に分岐命令は、少なくとも１つのオペコード（マイクロプロセッサ１０が使用する命令セット内で分岐命令を識別する）と、分岐ターゲットアドレスを生成するために分岐命令のアドレスに加算される変位（あるいは分岐命令の直後の命令のアドレス）とを有する。このため、分岐命令は、通常は少なくとも２バイトを占める。このことを利用すれば、全命令バイトに対する分岐マーカービットをストアする必要がなく、連続する命令バイトの組に対してストアされる分岐マーカービットのビット数を低減させることができる。しかし、分岐が「分岐成立」と予測されていることを示すように分岐マーカーがセットされていても、分岐予測が見落とされ得る、シングルバイトのＲＥＴ命令が関与する留意すべき特定の場合が存在する。この特定の場合に対処するための実施形態を以下に記載する。

図１１〜１５には、分岐マーカービットを更新する例が示される。図１０には、連続する命令バイト５０、分岐マーカービット５２および分岐情報４５０からなる組が示されている。図１０の例においては、「分岐成立」と予測された分岐はなく、分岐マーカービット５２もセットされていない。図１１を参照すると、成立予測分岐が検出された後の、命令バイト５０、マーカービット５２および分岐情報４５０と、これに対応する分岐マーカービット５２の更新の様子とが示される。図１１では、命令バイト５０内の命令バイト＃８および＃９で、成立予測分岐ＰＢ０１２０１が検出されている。この成立予測分岐は、命令バイト＃９で終端しているため、分岐マーカービット＃５１２０３を２進数値の「１」に設定して、分岐マーカービット５２が更新される。さらに、一実施形態においては、分岐情報のエントリ５００Ａ〜５００Ｃは、命令バイト５０に存在する成立予測分岐の１番目、２番目および３番目にそれぞれ対応し得る。このような実施形態においては、成立予測分岐ＰＢ０１２０１は、命令バイトの組５０の、１番目の成立予測分岐であると検出され得る。したがって、分岐命令ＰＢ０１２０１に対応する情報が分岐情報のエントリ５００Ａにストアされ得る。

図１２に、２番目の成立予測分岐が検出されたときの、分岐マーカービット５２の更新の様子が示される。成立予測分岐ＰＢ１１３０１が組５０で検出される。分岐ＰＢ１１３０１が検出され、かつ分岐ＰＢ１１３０１が命令バイト＃３で終端しているため、分岐マーカービット＃２１３０３が２進数値の「１」にセットされる。さらに、本図の実施形態においては、新たに検出された分岐ＰＢ１１３０１が、組５０の、１番目の成立予測分岐であることが判定される。このため、分岐ＰＢ１１３０１に対応する分岐情報は、分岐情報のエントリ５００Ａとなる。しかし、図１１の説明で上記したように、分岐情報のエントリ５００Ａは、今は分岐ＰＢ０１２０に対応する分岐情報を格納している。したがって、エントリ５００Ａ内のデータがエントリ５００Ｂに移され、分岐ＰＢ１１３０１に対応する新しい分岐情報がエントリ５００Ａにストアされる。

図１３には、成立予測分岐のエントリの更新の様子が示される。図１３の例では、分岐ＰＢ１１３０１に対して、予測が「分岐不成立」であることがのちに判定される。「分岐成立」となっているＰＢ１１３０１の予測を更新するために、対応する動的ビット５００Ａが２進数値の「１」にセットされる。このため、分岐ＰＢ０およびＰＢ１に対応する分岐予測が存在することになる。しかし、分岐ＰＢ１は動的５００Ａであると分類される一方で、分岐ＰＢ０はローカル５００Ｂであると分類されたままである。

上記の議論においては、分岐情報のエントリ５００Ａ〜５００Ｃのそれぞれが、組５０の特定の成立予測分岐に対応しているものとして記載した。例えば、エントリ５００Ａは組５０の１番目の成立予測分岐に対応し、エントリ５００Ｂは２番目の分岐に対応し、エントリ５００Ｃは３番目の分岐に対応している。したがって、更新後もこの対応関係を維持するには、エントリ５００Ａ〜５００Ｃ内のデータをシフトさせる必要がある。一般に、新しいエントリが作成される場合、このエントリに対応するデータエントリと、このエントリの右にある全エントリとが右にシフトされて、新しいエントリが入る空きが作られる。例えば、エントリ５００Ａに対応する新たに成立予測分岐が検出され、エントリ５００Ａに既に有効なエントリがストアされている場合、エントリ５００Ａの内容がエントリ５００Ｂにシフトされ、エントリ５００Ｂの内容がエントリ５００Ｃにシフトされ、エントリ５００Ｃの内容が分岐情報４５０から排除されて失われる。一実施形態においては、ターゲットアレイ２０８にあるターゲットアドレスも同様にシフトされて、組５０の成立予測分岐、エントリ５００の分岐情報、およびターゲットアレイ２０８のターゲットの間の対応関係が保たれ得る。上記の実施形態では、エントリ間でデータをシフトすることによって対応関係を保っているが、別の実施形態も可能であり、考察される。例えば、エントリ間でデータを移動させるのではなく、エントリ５００にストアされているビットとターゲットアレイ２０８のエントリとが特定の分岐のエントリに対応していてもよい。

上記したように、シングルバイトの分岐命令では特殊な場合が存在する。図１４は、シングルバイトの分岐命令の予測が見落とされる例を示す。図１４に、バイト位置８にシングルバイトのＲＥＴ命令１５０１を含む連続する命令バイトの組が示される。分岐マーカービット＃４１５０３がセットされており、成立予測分岐であるＲＥＴ命令１５０１が、命令バイト範囲７〜８で終端していることを示す。これ以外に、成立予測分岐はない。ここで、オフセット値に８が指定されたＲＥＴ命令１５０１のフェッチアドレスが受信された場合を考える。分岐マーカービット＃４は、この命令の分岐予測を作成する必要があることを示している。しかし、予測を作成するためにこの分岐マーカービットが送られる場合に、対応する分岐マーカービット＃４は、考慮対象となるマーカービット位置の条件を満たさず（つまり、値が８のオフセットは≦７とならない）、分岐マーカービット＃４が効果的に無視される。図８の論理に示されるように、分岐マーカービット＃４のｂ_４が設定されて、ゲート８０４Ｅに送られる。しかし、「オフセット≦７」の条件が真とならないため、ゲート８０８Ｅに結合されている信号８０８Ｅがセットされない。したがって、図８の論理は、分岐予測を示さない。一般に、この予測の見落としの例は、シングルバイトのＲＥＴ命令が命令バイト位置２，４，６，８，１０，１２，１４のいずれにある場合にも発生する可能性がある。この特別な場合に対処するための様々な実施形態およびメカニズムを以下に記載する。

分岐命令の情報
図１５を参照すると、分岐予測情報４５０の一実施形態が示される。上記のように、連続する命令バイト５０の各組は、ローカル予測記憶域２０６にストアされている、対応する分岐マーカービット５２と分岐予測情報４５０とのセットを有する。本図の実施形態においては、分岐予測情報４５０は、５００Ａ〜５００Ｃの３つの分岐命令情報を有する。５００Ａ〜５００Ｃの各々は６ビットであり、成立予測分岐に対応する情報を提供している。図１５に示すように、分岐予測情報には、動的ビット５０２、エンド調整ビット５０４、および分岐命令の種類およびサイズの分類に使用する４つのビット５０６が含まれる。動的ビット５０２は、ローカル予測記憶域２０６にあるローカル分岐予測ではなく、グローバル予測記憶域２０５にあるグローバル分岐予測を使用すべきことを示し得る。エンド調整ビット５０４は、対応する分岐命令が偶数バイトで終端しているか奇数バイトで終端しているかを示し得る。最後に、分岐情報５０６は、分岐命令の種類およびサイズの分類に使用され得る。

図１５には、分岐情報５０６のエンコーディング（encodings、コード化）の例が４つ記載されている。本図に示すように、各分岐命令には、エンドビット５０４（本例ではビット位置４）が含まれる。第１のコード５０８では、第２ビットおよび第３ビットがそれぞれ「０」、「０」に設定されることで、条件命令または無条件分岐命令を表し得る。第２のコード５１０では、第３ビットおよび第２ビットがそれぞれ「０」、「１」に設定されることで、ｃａｌｌ命令を表し得る。第３のコード５１２では、ビット３〜０が「１０００」に設定されることで、ｒｅｔｕｒｎ型の命令を表し得る。最後に、第４のコード（５１４）では、ビット３を「１」に、ビット２〜０を「０００」以外の値に設定することで、偶数バイトで終端する１バイトのｒｅｔｕｒｎオペコードを表し得る。最初の２つのコード５０８〜５１０には、命令の任意の即値データまたは変位データのサイズを示すフィールド（ビット１および０）もそれぞれ含まれる。一実施形態においては、１，２，４バイトのデータは、コード化ビット１，０を、それぞれ「００」、「０１」、「１０」に設定することによって表され得る。最後に、図１５に示す第４のコード５１４には、シングルバイトのｒｅｔｕｒｎ命令が現れる、組５０内の０以外の偶数命令バイトを示すフィールド（ビット２〜０）が含まれている。上記の実施形態においては、第４のコード５１４の位置フィールドは、「００１」〜「１１１」の７つの値を取り得、これらは、バイト位置２，４，６，８，１０，１２，１４にそれぞれ対応している。上記した分岐情報の使用方法を以下に記載する。

予測論理
図１６を参照すると、予測論理の一実施形態２２０が示される。図１６には、比較回路系８０２、ローカル予測回路９００、ターゲット選択回路１１００、および制御回路１１０２が記載されている。比較回路８０２はフェッチアドレスのオフセットを受信するように結合され、かつ予測回路９００およびターゲット選択回路１１００に信号１７０４を送るようにさらに結合されている。ターゲット選択回路１１００および予測回路９００は、ローカル予測記憶域２０６から分岐予測のエントリに関する情報を受信するように結合されている。制御回路１１０２は、予測回路９００、ターゲット選択回路１１００、ローカル予測記憶域２０６、およびグローバル予測記憶域２０５に結合されている。一般に、比較回路８０２は、上記のようにフェッチアドレスを受け取って回路９００，１１００に信号１７０４を送る。予測回路９００は、ローカル予測記憶域２０６から受け取った分岐マーカービットおよび回路８０２から受け取った信号に基づいて分岐予測が作成されるかどうかを判定するように構成されており、得られた予測１７１０を制御回路１１０２に送る。また、ターゲット選択回路１１００は、ローカル予測記憶域２０６から受け取った分岐マーカービットを使用して、分岐成立の際にどの分岐ターゲットを使用すべきかを示す情報（indication）１７０６を制御回路１１０２に送る。また、制御回路は、分岐ターゲット情報１７１４を受け取って、フェッチアドレスを選択する信号２４０をマルチプレクサ２０２に送る。さらに、一実施形態においては、回路１１０２は、分岐アドレス計算器２７０に分岐予測２５０を送る。また、本実施形態には特定の分岐について別の予測を提供し得るグローバル予測メカニズムが記載されているが、本メカニズムは、グローバル予測メカニズムがなくても使用することができる。

図１６に示すターゲット選択回路１１００は一般に、複数のターゲットのうちから、分岐予測に使用するターゲットを１つ選択するように構成され得る。一実施形態においては、ターゲット選択回路１１００は、受け取ったフェッチアドレスのオフセットに先行するオフセットに対応する命令バイトに対して設定された分岐マーカービットの個数を決定し得る。この情報に基づいて、１番目〜３番目の分岐ターゲットが選択され得る（３つの分岐ターゲットが保持される一実施形態の場合）。例えば、可能性のある３つの分岐ターゲットを保持でき、値が６のオフセットを受け取る場合を考える。回路１１００は、分岐マーカービット６に先行する分岐マーカービットの範囲（つまり、分岐マーカービット０〜５）内で、設定されている分岐マーカービットの個数を決定し得る。この範囲に、設定された分岐マーカービットがない場合は、この分岐が、１番目の成立予測分岐であると識別され、１番目のターゲットが選択される。分岐マーカービットがこの範囲で１つだけ設定されている場合、この分岐は２番目の成立予測分岐命令であると識別され、ターゲット２が選択される。２つの分岐マーカービットが設定されている場合、ターゲット３が選択される。

ターゲット選択回路１１００の実装方法として、数多くの方法が考えられるが、図１７に動的論理を使用した実施形態の一例１８００を示する。図１７の実施形態においては、トランジスタの行１２０２〜１２１６および列１２２０〜１２３４が、受け取った分岐マーカービットとオフセットアドレスとに基づいてターゲットが選択され得るように構成されている。回路１８００では、Ｔ１１２１２、Ｔ２１２１４およびＴ３１２１８の３通りのターゲット選択が可能である。一般に、回路系１８００は、受け取った分岐マーカービットと、比較回路８０２から受け取った信号とを使用して、特定のターゲットが検出されると、これを考慮対象から除外する。例えば、フェッチアドレスのオフセットに先行して１つの分岐マーカーが出現することが検出されると、ターゲット１が考慮対象から除外されてターゲット２が選択される。フェッチアドレスのオフセットに先行して２つの分岐マーカービットの組が出現することが検出されると、ターゲット３が選択される。当業者は回路１８００の動作を容易に理解するであろうが、以下に概略を記載する。

図１７の第１の行１２０２は、トランジスタ対１２２０〜１２３４からなり、これらは受信したオフセットに先行して、セットされている分岐マーカービットがあるかどうかを判定する。標準では、ターゲットＴ１１２１２の値は、真すなわち２進数の「１」である。Ｔ１１２１２の値は、論理ＡＮＤゲートの反転された入力にもなり、Ｔ２１２１４の値が提供される。したがって、Ｔ１１２１２の値が２進数の「１」の場合、Ｔ２は２進数の「０」となる。行１２０２の各トランジスタ対は、このフェッチアドレスオフセットに対応する分岐マーカービットと比較回路８０２からの信号とを受け取る。例えば、列１２２０、行１２０２のトランジスタ対は、分岐マーカービット０（ｂ_０）に対応する第１の入力と、受け取ったオフセットアドレスが０より大きいかどうか（つまり、受け取ったオフセットアドレスを「ａ」で表すとａ＞０）を示す第２の入力とを受け取る。２つの入力が共に２進数の「１」である場合、ターゲットＴ１１２１２の値は２進数の「０」となり、受け取ったフェッチアドレスに先行して成立予測分岐が存在することを示し、ターゲットＴ１１２１２が予測されたターゲットとして考慮対象から除外される。残りの行１２０４〜１２１６は、現在のオフセットに先行して２つの分岐マーカービットがセットされているかどうかを判定するように構成されており、２つの分岐マーカービットがセットされている場合、ターゲットＴ２１２１４が考慮対象から除外される。行１２０４は、分岐マーカービットｂ_０と、分岐マーカービットｂ_１〜ｂ_７とを比較する。行１２０６は、分岐マーカービットｂ_１と分岐マーカービットｂ_２〜ｂ_７とを比較し、以下、同様の比較を行う。現在のオフセットに先行して２つの分岐マーカービットがセットされていることが検出された場合、ターゲットＴ３１２１８の値は「１」となり、ターゲットＴ２１２１４の値は「０」となる。しかし、先行する２つの分岐マーカービットがセットされていることが行１２０４〜１２１６によって検出されなければ、ターゲットＴ２１２１４の値は２進数の「１」となる。既に説明したように、回路系１８００は例示的なものに過ぎない。対応するターゲットの選択方法として数多くの方法が可能であり、考察される。

図１８を参照すると、制御回路１１０２の一実施形態が示される。図１８には、エンコーダ回路系１８２０およびマルチプレクサ１８３２，１８３０が記載されている。マルチプレクサ１８３２は、予測回路９００からローカル予測１７１０を、グローバル予測記憶域２０５からグローバル予測１７１２を受信するように結合されている。マルチプレクサ１８３０は、３つの分岐命令に対応する分岐情報１７１４をローカル予測記憶域２０６から受け取るように結合されている。さらに、マルチプレクサ１８３０は、ターゲット選択回路１１００からターゲット選択信号１７０６を受け取るように結合されている。選択信号１７０６は、マルチプレクサ１８３０からエンコーダ回路系１８２０に送る分岐情報１８４０を選択する。さらに、本図の実施形態においては、ローカル予測１７１０かグローバル予測１７１２かのいずれを予測１８０６としてマルチプレクサ１８３２からエンコーダ回路系１８２０に送るかを選択するために、分岐情報１８４０に含まれる動的ビット１８０８が使用される。エンコード回路系１８２０は、分岐情報１８４０および予測１８０６を使用して、分岐が「分岐成立」と予測されているか「分岐不成立」と予測されているかを決定し得る。「分岐成立」と予測されている分岐がない場合、エンコーダ回路系１８２０は、マルチプレクサ２１２から連続アドレス２３２を送る選択信号２４０をエンコードするように構成され得る。別法として、エンコーダ回路系１８２０が、戻りアドレス２３０かターゲットアレイ２０８から受信した分岐ターゲットアドレスかを選択するために信号２４０をエンコードしてもよい。本図の実施形態においては、ローカル予測１７１０かグローバル予測１７１２かを選択するために、動的ビット１８０８が使用され得る。一実施形態においては、分岐が、比較的予測不可能な挙動を示す場合、グローバル分岐予測履歴を使用して、その分岐の予測精度を向上させることができる。この場合、ローカル分岐予測ではなくグローバル分岐予測を使用すべきことを示すように動的ビットが設定され得る。

分岐アドレスの計算
上記したように、一実施形態においては、信号２４０によって選択されてマルチプレクサ２１２によって送信されるフェッチアドレス２４３は、所定のフェッチアドレスに関し、分岐予測ユニット１６によって送信される最終的な分岐予測を提供し得る。しかし、別の実施形態においては、分岐予測ユニット１４は、初期の段階で予測ミスを検出するために、分岐アドレスの計算を実行するように構成される。図１９は、分岐アドレス計算器２７０のブロック図である。本図の実施形態においては、分岐アドレス計算器２７０は、マルチプレクサ２２２からアドレス２３６を、ローカル予測記憶域２０６から予測情報２４２を、命令キャッシュ１６から命令バイトの組２４１を、マルチプレクサ２１２からターゲットアドレス２４３を受け取るように構成されている。分岐アドレス計算器２７０はフェッチアドレス２４５を送るようにも構成されている。

一般に、分岐アドレス計算器２７０は、受け取ったフェッチアドレス２３６と分岐命令の即値データ２４１とに基づいて、相対分岐ターゲットアドレスを計算するように構成されている。次に、新たに求めたターゲットアドレスと予測されたターゲットアドレス２４３とが比較される。新たに求めたターゲットアドレスと予測されたターゲットアドレス２４３とが一致しない場合、予測ミスが検出されて、新たに求めたターゲットが次のフェッチアドレス２４５として送られる。分岐予測ミスが早期に検出されて、新しいフェッチアドレスを早いうちに計算できるため有利である。

図１９の実施形態においては、予測された分岐命令に対応する情報が、バス１８５０を介してローカル予測記憶域２０６から送られる。一実施形態においては、分岐情報１８５０には、命令バイトの組にある、対応する分岐命令のオフセットアドレスが含まれる。さらに、命令バイトの組２４１が、命令キャッシュ１６からマルチプレクサ１４０６に送られる。受け取ったオフセットと、分岐情報１８５０に含まれるエンドビット５０４情報とが使用されて、選択信号１４２０がマルチプレクサ１４０６に送られ、対応する分岐命令がマルチプレクサ１４０６からマルチプレクサ１４０８に送られ得る。さらに、受け取った情報１８５０に含まれる受け取った分岐情報５０６が使用されて、マルチプレクサ１４０８に信号１４２２が送られ、マルチプレクサ１４０８は、予測された分岐命令に対応する即値データ１４２４を選択して送る。フェッチアドレス２３６が、マルチプレクサ１４１４と、フェッチアドレス２３６からベースアドレスを減算するように構成された回路１４０２とに送られる。一実施形態においては、ベースアドレスのベースは、８６アドレス変換メカニズムの対応する部分によって指定されるアドレスに対応している。回路１４０２は、ベースを減算して、求めたアドレスを回路１４０４に送る。回路１４０４は、このアドレスに、マルチプレクサ１４０８から受け取った即値データ１４２４を加算し、この結果１４１３を回路１４１０に送るように構成されている。

上記に加え、予測されたターゲット２４３がマルチプレクサ１４１４および回路１４１２に送られる。回路１４１２は、予測されたフェッチアドレスからベースアドレスを減算してフェッチアドレスを調整し、得られたアドレス１４１５を回路１４１０に送るように構成されている。回路１４１０は、計算によって求めたアドレス１４１３と調整されたフェッチアドレス１４１５とを受け取ると、両者を比較するように構成されている。回路１４１０は、２つのアドレスが等しくない場合、フェッチアドレス２３６を選択して、マルチプレクサ１４１４から送信させる。回路１４３０は、両者が一致しない場合に、フェッチアドレス２３６を送るように構成され得る。回路１４３０は、計算によって求めたフェッチアドレスと調整済みのフェッチアドレスとが等しい場合に、新しいフェッチアドレスを送信しないように構成され得る。さらに、回路１４３０は、「分岐不成立」の予測を示す予測信号２５０を検出すると、新しいフェッチアドレスを送信しないように構成され得る。

一実施形態においては、フェッチアドレス２３６が受信されると、分岐予測ユニット１４によって２つのフェッチアドレスが決定されて送信され得る。マルチプレクサ２１２から送られる第１のフェッチアドレスは、命令キャッシュ１６から命令をフェッチするための新しいフェッチアドレスとして直ちに使用され得る。同時に、マルチプレクサ２１２から送られるフェッチアドレスは、分岐アドレス計算器２７０にも送られ、上記の比較が実行される。分岐アドレス計算器２７０は、マルチプレクサ２１２経由のフェッチアドレスと、分岐アドレス計算器２７０が上記のように算出したフェッチアドレスとが一致しない場合、命令キャッシュ１６から命令をフェッチするために使用する第２のフェッチアドレスを送る。

分岐予測犠牲キャッシュ
上記したように、犠牲キャッシュ２６０を使用して、ローカル予測記憶域２０６から排除された分岐予測情報がストアされ得る。図２０は、ローカル予測記憶域２０６と犠牲キャッシュ２６０との相互作用（interaction）の一実施形態を示すブロック図である。図２０には、ローカル予測記憶域２０６および犠牲キャッシュ２６０のほかに、Ｉ（命令）キャッシュ１６、Ｌ２キャッシュ１８２８およびデコーダ４００が記載されている。本図の実施形態においては、犠牲キャッシュ２６０は、ローカル予測記憶域２０６から排除された分岐予測情報をストアするように構成され、Ｌ２キャッシュ１８２８は、プログラム命令を含め、データをストアするように構成されている。

ローカル予測記憶域２０６からエントリが排除される際には、排除されるエントリに対応する分岐マーカービットと動的ビットとが、バス２１０８を介して犠牲キャッシュ２６０に送られ、犠牲キャッシュ２６０にストアされる。エンド調整ビット５０４、分岐情報５０６など、排除されるエントリに対応する他の分岐予測情報は破棄される。同様に、本図の実施形態においては、Ｉキャッシュ１６から排除されるデータが、バス２１０６を介して送られ、Ｌ２キャッシュ１８２８にストアされる。続いて、ローカル予測記憶域２０６およびＩキャッシュ１６にフェッチアドレス２３６が提示されると、提示されたフェッチアドレスに対応する分岐予測のエントリが、ローカル予測記憶域２０６に存在するかどうかが判定される。対応するエントリがローカル予測記憶域２６０にない場合、犠牲キャッシュ２６０に、対応するエントリが要求され得る。対応する有効なエントリが犠牲キャッシュ２６０で検出されると、分岐マーカービットおよび動的ビットが、バス２１０２を介してデコーダ４００とローカル予測記憶域２０６とに送られる。ローカル予測記憶域は、受け取った分岐マーカービットおよび動的ビットを、これらに対応するエントリにストアするように構成されている。さらに、フェッチアドレス２３６に対応する命令の組が、バス２１０４を介してデコーダ４００とＩキャッシュ１６とに送られる。

次にデコーダ４００は、受け取った命令と分岐マーカービットとを使用して、ローカル予測記憶域２０６に分岐予測のエントリの残りの部分を再生成し得る。デコーダは、バス２１０２を介して受け取った分岐マーカービットを使用して、バス２１０４から受け取った命令の組内での成立予測分岐の位置を特定し得る。さらに、デコーダ４００は、特定した成立予測分岐をデコードして、分岐の種類（無条件分岐、条件付き分岐など）、分岐の終端バイトが偶数バイトか奇数バイトかのほか、分岐命令に対応する即値データがあればそのサイズを決定し得る。デコーダ４００は、この決定の結果を基に、ローカル予測記憶域２０６に、対応する分岐予測のエントリの残りの部分を再生成し得る。本図の実施形態においては、分岐予測のエントリの残りの部分は、分岐情報５０６およびエンド調整ビット５０４に該当する。対応する命令の組を実行することなく、ローカル予測記憶域２０６に分岐予測の完全なエントリを再生成することができ有利である。さらに、分岐予測のエントリの一部のみを犠牲キャッシュ２６０にストアするだけで済む。このため、犠牲キャッシュ２６０のサイズを小さくすることができる。

図２１に、ローカル予測記憶域２０６への分岐予測のエントリの再生成をさらに詳細に示す。図２１には、犠牲キャッシュ２６０、デコーダ４００、およびローカル予測記憶域２０６のエントリ２１００が記載されている。本図に示すように、分岐マーカービット２１２０および動的ビット２１２２はデータを構成しており、このデータは、バス２１０８を介して犠牲キャッシュへと排除されるほか、バス２１０２を介して犠牲キャッシュ２６０からリトリーブされる。分岐情報２１３０は、分岐情報５０６およびエンド調整ビット５０４に対応するデータを含む。分岐情報２１３０は、ローカル予測記憶域２０６からエントリ２１００が排除される際に破棄される。上記したように、デコーダ４００は、分岐情報２１３０を再生成し、２１１０を介して再生成されたデータを送るように構成されている。

上記したように、フェッチアドレス２３６が、ローカル予測記憶域２０６およびＩキャッシュ１６の双方に提示される。しかし、別の実施形態においては、フェッチアドレス２３６が、ローカル予測記憶域２０６およびＩキャッシュ１６に加えて、犠牲キャッシュ２６０およびＬ２キャッシュ１８２８の少なくともいずれかに提示されてもよい。さらに、Ｌ２キャッシュ１８２８が、上記したようにローカル予測記憶域２０６から排除されたデータをストアするように構成される実施形態もあり得る。図２２に、Ｌ２キャッシュ１８２８が、プログラム命令と、対応する分岐予測情報とをストアするように構成されている実施形態を示す。本図の実施形態においては、ローカル予測記憶域２０６は、バス２２０６を介して排除された分岐予測情報をＬ２キャッシュ１８２８に送るように構成されている。Ｉキャッシュ１６は、排除されたプログラム命令を、バス２２０を介してＬ２キャッシュ１８２８に送信するように構成され得る。プリフェッチユニット１２は、Ｌ２キャッシュ１８２８からプログラム命令と分岐予測情報の両方をフェッチするように構成されている。プリフェッチユニットは、Ｌ２キャッシュ１８２８からフェッチした分岐情報およびプログラム命令に基づいて、分岐予測のエントリを完全に再生成するようにさらに構成されている。次に、分岐予測の完全なエントリが、バス２２０２を介してローカル予測記憶域２０６に送られると共に、対応するフェッチ済みのプログラム命令が、バス２２０４を介してＩキャッシュ１６に送られ得る。

見落とされた予測の検出
上記したように、シングルバイトのＲＥＴ命令が関与する特別な場合がある。図１４に示すように、特定の位置に現れる、「分岐成立」と予測されたシングルバイトのＲＥＴ命令が、予測論理２２０によって見落とされ、その後「分岐不成立」と予測される可能性がある。下記に、このような見落とされた予測を検出するように構成された分岐予測ユニット１４の一実施形態を記載する。図２３は、分岐予測ユニット１４の一実施形態を示すブロック図である。図２３の実施形態は図２の実施形態と類似している。しかし、図２３の実施形態においては、戻りアドレススタック２３０が、マルチプレクサ２２１Ａに結合されているほか、分岐アドレス計算器２７０と比べて分岐アドレス計算器２７０Ａが変更されており、信号２２３Ａは、マルチプレクサ２２１Ａへの３つの入力のうちの１つを選択するように構成されている。図２３の実施形態は、全般に前の例と同じように動作する。しかし、分岐アドレス計算器２７０Ａは、シングルバイトのＲＥＴ命令に対応する見落とされた予測を検出すると、戻りスタック２３０から送られるフェッチアドレスを選択するように構成されている。

図２４に、分岐アドレス計算器２７０Ａの一実施形態を示す。分岐アドレス計算器２７０Ａは、分岐アドレス計算器２７０と同様に構成されており、上記したように第２のフェッチアドレスを計算し、バス２４５を介してこれを送信し得る。しかし、分岐アドレス計算器２７０のように回路１４３０からアドレス２４５および制御信号２２３を送るのではなく、回路１４３０は、可能性のある第２のフェッチアドレス２４１０を制御回路２４００に、選択信号２４１２をマルチプレクサ２４０２に送信するように構成されている。さらに、分岐アドレス計算器２７０Ａは、シングルバイトのＲＥＴ命令に対応する、見落とされた予測を検出するように構成された見落予測回路２４５０を備える。見落予測回路２４５０は、ローカル予測記憶域２０６から分岐ターゲット情報４５０を、予測論理２２０から予測２５０を受け取るほか、フェッチアドレス２３６を受信するように結合されている。さらに、回路２４５０は、選択信号２４２０，２４２２をマルチプレクサ２４０２に送るように結合されている。信号２４２２は、制御回路２４００にさらに結合されている。

見落予測回路２４５０は、見落とされた予測を検出すると、マルチプレクサ２２１Ａから送られる戻りアドレスを選択するように構成された選択信号２４２０と、見落とされた予測の検出を示し、信号２４２０を選択してマルチプレクサ２４０２から出力させるように構成された選択信号２４２２とを送信する。一実施形態においては、見落予測回路２４５０は、予測２５０が「分岐成立」の予測を示す場合には必ず、信号２４１２を選択してマルチプレクサ２４０２から送信させるように構成され得る。このように、予測論理２２０が「分岐不成立」の予測を示す場合には、見落予測回路２４５０が、見落とされた予測の検出のみを実行してもよい。マルチプレクサ２４０２は、信号２４６０を送るように構成されており、信号２４６０は、第２のフェッチアドレス２４５を選択してマルチプレクサ２２１Ａから送信させるようにも、戻りアドレスを選択してマルチプレクサ２２１Ａから送信させるようにも構成され得る。

制御回路２４００は、予測ミスまたはＲＥＴ命令の見落とされた予測のために、第２のフェッチアドレスが必要であるかどうかを判定し、対応する情報をバス２４５および信号２２３Ａを介して送るように構成されている。一実施形態においては、信号２４１０には、フェッチアドレスと、回路１４１０による比較の結果が不一致となったことを示す情報とが含まれる。本図の実施形態においては、制御回路２４００は、２つの条件のうちの１つを検出すると、第２のフェッチアドレスが必要であることを判定し得る。第２のフェッチアドレスが必要となる第１の条件は、「分岐成立」の予測２５０を検出し、かつ信号２４１０から、回路１４１０による比較の結果が不一致となったことを検出することである。制御回路は、第１の条件を検出すると、受け取ったアドレス２４１０をバス２４５を介して送るほか、対応する選択信号２２３Ａを送るように構成されている。この場合、選択信号２２３Ａは、回路１４３０から送られる信号２４１２に対応しており、信号２４５を選択してマルチプレクサ２２１Ａから送信させるように構成されている。第２のフェッチアドレスを要求する第２の条件は、「分岐不成立」の予測２５０を検出し、かつ信号２４２２から、見落とされた予測が検出されたことを検出することである。制御回路２４００は、第２の条件を検出すると、選択信号２２３Ａを送り、これは見落予測回路２４５０によって送られる信号２４２０に対応している。第２の条件の場合、送信された選択信号２２３Ａは、戻りアドレス２３０を選択してマルチプレクサ２２１Ａから送信させるように構成されている。制御回路２４００によって第１の条件も第２の条件も検出されない場合、第２のフェッチアドレスが送られることはない。

図２５は、見落予測回路２４５０の一実施形態を示すブロック図である。見落予測回路２４５０は、候補回路２５０２、偶数バイト回路２５０４、照合回路２５０６、および制御回路２５０８を備える。候補回路２５０２は、分岐情報４５０を受信するように結合され、偶数バイト回路２５０４は、フェッチアドレス２３６を受信するように結合され、制御回路２５０８は、予測２５０を受信するように結合されている。さらに、照合回路２５０６は、候補回路２５０２から信号２５２０を、偶数バイト回路２５０４から信号２５２２をそれぞれ受信するように結合されている。制御回路２５０８は、照合回路２５０６から信号２５３０を受信するように結合されている。

図２５の実施形態においては、候補回路２５０２は、分岐情報４５０の偶数バイト位置に、ＲＥＴ命令に対応する有効なエントリが含まれるかどうかを判定するように構成されている。上記したように、分岐情報４５０は、５００Ａ〜５００Ｃの３つの分岐命令に対応する分岐情報を含み得る。図１５に示すコードを使用して、ＲＥＴ命令が、分岐情報ビット＃３が２進数の「１」である命令として特定され得る。さらに、エンド調整ビットによって、偶数バイトで終端する命令が検出され得る。次に、偶数バイトのＲＥＴ命令に対応していると判定された分岐情報５００Ａ〜５００Ｃが、見落とされた予測の候補とみなされ、候補を検出したことを示す肯定的な指示（positive indication）と共に照合回路２５０６に送られ得る。偶数バイト回路２５０４は、偶数アドレスに該当するフェッチアドレスを決定するように構成されている。一実施形態においては、偶数バイト回路２５０４は、この判断を行うために、受け取ったフェッチアドレス２３６の最下位ビットを比較し得る。フェッチアドレス２３６の最下位ビットが２進数の「０」である場合、偶数フェッチアドレスとして判定され、対応する肯定的な指示２５２２が照合回路２５０６に送信され得る。

照合回路２５０６は、回路２５０２，２５０４から肯定的な指示を受け取ると、フェッチアドレス２３６に対応する、見落とされた予測の候補を検出するように構成されている。一実施形態においては、フェッチアドレス２３６のオフセットのビット３〜１と、候補の分岐情報のビット２〜０とが比較される。上記したように、ＲＥＴ命令の分岐情報５０６のビット２〜０は、ＲＥＴ命令の偶数バイト位置を示している。下記の表に、偶数フェッチアドレスのオフセットと分岐情報のバイト位置との関係を示す。

表１に示すように、偶数フェッチアドレスのオフセットのビット３〜１と、分岐情報５０６のビット２〜０とを直接対応付けることができる。このため、照合回路２５０６は、ＲＥＴ命令に対応する候補分岐情報とフェッチアドレスのオフセットとを照合することができる。照合回路２５０６は、この一致を検出すると、一致を検出したことを示す信号２５３０を制御回路２５０８に送るように構成されている。ここに示す例示的な実施形態では、制御回路２５０８は、「分岐不成立」の予測２５０と一致を示す情報２５３０とを検出すると、戻りアドレスを選択してマルチプレクサ２２１Ａから送信させるように構成された信号を送信するように構成されている。制御回路２５０８は、戻りアドレス２３０を選択してマルチプレクサ２２１Ａから送信させるために、信号２４２２および信号２４２０を送る。信号２４２０には、戻りアドレス２３０を選択してマルチプレクサ２２１Ａから送信させるためのコードが含まれる。選択信号２４２２は、信号２４１２か信号２４２０かを選択してマルチプレクサ２４２２から出力させるように構成されている。信号２４２２は、「分岐不成立」の予測２５０と一致を示す情報２５３０とを検出すると、信号２４２０を選択してマルチプレクサ２４０２から出力させる。これらが検出されない場合、信号２４２２は、信号２４１２を選択してマルチプレクサ２４０２から出力させる。

図２６に、バスブリッジ２６０２を介して種々のシステム部品に結合されたプロセッサ１０を備えたコンピュータシステム２６００の一実施形態のブロック図が示される。別の実施形態も可能であり、考慮される。図中のシステムにおいて、メインメモリ２６０４は、メモリバス２６０６を介してバスブリッジ２６０２に結合され、グラフィックコントローラ２６０８は、ＡＧＰバス２６１０を介してバスブリッジ２６０２に結合されている。最後に、複数のＰＣＩ機器２６１２Ａ〜２６１２Ｂが、ＰＣＩバス２６１４を介してバスブリッジ２６０２に結合されている。さらに、ＥＩＳＡ／ＩＳＡバス２６２０を介して１つ以上のＥＩＳＡ機器またはＩＳＡ機器２６１８を電気的に接続できるように、セカンダリバスブリッジ２６１６を設けてもよい。プロセッサ１０は、ＣＰＵバス２６２４を介してバスブリッジ２６０２に結合されているほか、自由選択で設けられるＬ２キャッシュ１８２８にも結合されている。

バスブリッジ２６０２は、プロセッサ１０、メインメモリ２６０４、グラフィックコントローラ２６０８およびＰＣＩバス２６１４に接続された機器の間のインターフェイスを提供している。バスブリッジ２６０２に接続された機器のうちの１つから操作（operation）が受信されると、バスブリッジ２６０２は、この操作のターゲット（例えば、特定の機器か、ターゲットがＰＣＩバス２６１４に接続している場合はＰＣＩバス２６１４）を識別する。バスブリッジ２６０２は、この操作をターゲット機器に転送する。バスブリッジ２６０２は一般に、この操作を、ソースの機器またはバスが使用しているプロトコルから、ターゲットの機器またはバスが使用しているプロトコルに変換する。

セカンダリバスブリッジ２６１６は、ＰＣＩバス２６１４に対するインターフェイスをＩＳＡ／ＥＩＳＡバスに提供すると共に、必要に応じて追加の機能も有している。また、必要に応じて、セカンダリバスブリッジ２６１６の外側に設けたか、ブリッジ２６１６に搭載した入出力コントローラ（図示せず）をコンピュータシステム２６００に設けて、キーボードおよびマウス２６２２、ならびに様々なシリアルポートおよびパラレルポートの操作をサポートしてもよい。さらに、別の実施形態においては、プロセッサ１０とバスブリッジ２６０２との間にあるＣＰＵバス２６２４に、外部キャッシュユニット（図示せず）を結合してもよい。別法として、外部キャッシュをバスブリッジ２６０２に結合してもよく、この外部キャッシュのためのキャッシュ制御論理をバスブリッジ２６０２に搭載してもよい。さらに、Ｌ２キャッシュ１８２８が、プロセッサ１０のバックサイド構成（backside configuration）で記載されている。Ｌ２キャッシュ１８２８は、プロセッサ１０から独立していても、プロセッサ１０にカートリッジ（例えば、スロット１またはスロットＡ）として搭載されていても、プロセッサ１０と共に半導体基板に搭載されていてもよいという点が注目される。

メインメモリ２６０４は、アプリケーションプログラムのストア先であると共に、プロセッサ１０の主な実行元のメモリである。適切なメインメモリ２６０４は、ＤＲＡＭ（ダイナミックランダムアクセスメモリ）を有する。例えば、複数バンク構成のＳＤＲＡＭ（シンクロナスＤＲＡＭ）のまたはラムバスＤＲＡＭ（ＲＤＲＡＭ）が適切であり得る。

ＰＣＩ機器２６１２Ａ〜２６１２Ｂの例には、ネットワークインターフェイスカード、ビデオアクセラレータ、オーディオカード、ハードディスクドライブ、フロッピーディスクドライブもしくはドライブコントローラ、ＳＣＳＩ（小型コンピュータシステムインターフェイス）アダプタおよびテレフォニカードなどの様々な周辺機器がある。同様に、ＩＳＡ機器２６１８の例には、モデム、サウンドカード等の様々なタイプの周辺機器のほか、種々のデータ取得カード（ＧＰＩＢインターフェイスカードまたはフィールドバスインターフェイスカード等）などがある。

グラフィックコントローラ２６０８は、ディスプレイ２６２６の文字および画像の表示を制御するために設けられる。グラフィックコントローラ２６０８は、メインメモリ２６０４との間で効率的に移動可能な３次元データ構造を表示するために、当業界において一般に公知となっているグラフィックアクセラレータを具体化し得る。このため、グラフィックコントローラ２６０８は、バスブリッジ２６０２内でターゲットインターフェイスに対するアクセスを要求および受け取って、これによってメインメモリ２６０４へのアクセスを取得できるという点で、ＡＧＰバス２６１０のマスタであり得る。専用のグラフィックバスによって、メインメモリ２６０４から高速にデータを取得することが可能となる。グラフィックコントローラ２６０８は、特定の操作のために、ＡＧＰバス２６１０でＰＣＩプロトコルトランザクションを生成するようにさらに構成され得る。このため、バスブリッジ２６０２のＡＧＰインターフェイスは、ＡＧＰプロトコルのトランザクションと、ＰＣＩプロトコルのターゲットトランザクションおよびイニシエータトランザクションとの両方をサポートする機能を有し得る。ディスプレイ２６２６は、画像または文字を表現可能な任意の電子ディスプレイである。適切なディスプレイ２６２６には、陰極線管（「ＣＲＴ」）ディスプレイや液晶ディスプレイ（「ＬＣＤ」）などがある。

上記の説明においてＡＧＰバス、ＰＣＩバス、およびＩＳＡバスまたはＥＩＳＡバスを例として採り上げたが、必要に応じて任意のバスアーキテクチャを代用してもよいという点が注目される。さらに、コンピュータシステム２６００は、追加のプロセッサ（コンピュータシステム２６００の追加部品として示されるプロセッサ１０ａなど）を備えたマルチプロセッシングコンピュータシステムであってもよいという点が注目される。プロセッサ１０ａはプロセッサ１０と類似のものであってもよい。より詳細には、プロセッサ１０ａは、プロセッサ１０と全く同一であってもよい。プロセッサ１０は、独立したバスを介してバスブリッジ２６０２に結合されていても（図４に示される）、プロセッサ１０との間でＣＰＵバス２６２４を共用してもよい。さらに、プロセッサ１０ａは、Ｌ２キャッシュ１８２８と類似した追加のＬ２キャッシュ１８２８ａと結合されてもよい。

本議論は、種々の信号のアサートに言及し得るという点が注目される。本明細書で使用されるように、ある信号が特定の条件を示す値を伝達する場合、その信号は「アサートされている」という。これに対して、ある信号が特定の条件がないことを示す値を伝達する場合、その信号は「ディアサートされている」という。信号が論理０値を伝達する場合、または逆に論理１値を伝達する場合、この信号はアサートされていると定義することができる。さらに、上記の説明において種々の値が破棄されていると記載した。値は、さまざまな方法によって破棄され得るが、一般には、この値を受け取る論理回路によって無視されるように値を変更することが行われる。例えば、値が１つのビットを有する場合、この値の論理状態を反転して値を破棄してもよい。値がｎビット値である場合、ｎビットコードのうちの１つのビットが、値が無効であることを示す値を示し得る。このビットを、コードを無効にする値に設定すると、値が破棄される。さらに、ｎビット値が、設定されるとそのビット値が有効であることを示す有効ビットを有していてもよい。この有効ビットをリセットすることによって、値を破棄することがある。値を破棄する別の方法が使用されてもよい。

上記の開示が完全に理解されれば、数多くの変形例および変更例が当業者にとって自明となるであろう。添付の特許請求の範囲はこのような変更例および変更例を全て包含するものと解釈されることが意図される。

本発明は一般に、マイクロプロセッサの分岐予測メカニズムに利用可能である。

マイクロプロセッサの一実施形態を示すブロック図である。分岐予測ユニットの一実施形態を示すブロック図である。分岐を予測する方法を示すフローチャートである。レベル２分岐予測キャッシュの使用法を示すフローチャートである。プログラム命令と、対応する分岐予測のエントリとから構成される連続する組を示す図である。分岐マーカービットとアドレスオフセットとの関係を示す図である。プログラム命令、分岐マーカービットおよびアドレスオフセットの関係を示す図である。予測論理の一実施形態を示す図である。図８の予測論理から導出した動的論理を示す図である。分岐マーカービットの使用を示す図である。分岐マーカービットの使用を示す図である。分岐マーカービットの使用を示す図である。分岐マーカービットの使用を示す図である。見落とされた予測を示す図である。分岐ターゲット情報を示す図である。予測論理ユニットの一実施形態を示すブロック図である。ターゲット選択回路の一実施形態を示す図である。選択信号回路の一実施形態を示すブロック図である。分岐アドレス計算ユニットの一実施形態を示す図である。レベル１分岐予測用の記憶域とレベル２分岐予測用の記憶域との関係を示すブロック図である。レベル１分岐予測用の記憶域とレベル２分岐予測用の記憶域との関係を示すブロック図である。レベル１分岐予測用の記憶域とレベル２分岐予測用の記憶域との関係を示すブロック図である。分岐予測ユニットの一実施形態を示すブロック図である。分岐アドレス計算ユニットの一実施形態を示す図である。見落予測回路の一実施形態を示すブロック図である。コンピュータシステムを示すブロック図である。

Claims

１次レベルキャッシュ（２０６）が第１のアドレスに対応する第１分岐予測情報（２１００）を有さないことを検出するステップと、
２次レベルキャッシュ（２６０，１８２８）が、前記第１のアドレスに対応し、前記第１分岐予測情報の一部を含む第２分岐予測情報（２１２０，２１２２）を有するかどうかを判定するステップと、
前記２次レベルキャッシュが前記第２分岐予測情報を有することが検出されると、前記第１の分岐予測情報を再生成するステップと、
分岐命令のタイプを示す第３分岐予測情報を生成するステップと、
前記第２分岐予測情報と、前記第３分岐予測情報とを組み合わせるステップと、
前記第１のアドレスに対応する、前記１次レベルキャッシュの第１のエントリに前記第１の分岐予測情報として、前記組み合わせられた第２および第３分岐予測情報をストアするステップとを含む方法。
前記１次レベルキャッシュ（２０６）の前記第１のエントリ（２１００）が使用可能であるかどうかを判定するステップと、
前記第１のエントリが使用不可能であることが検出されると、前記第１のエントリ（２１００）の内容を排除するステップと、
前記排除を受けて、前記内容の一部（２１２０，２１２２）を前記２次レベルキャッシュ（２６０，１８２８）にストアするステップと、をさらに含む請求項１記載の方法。
前記生成するステップは、前記第１アドレスに対応するプログラム命令を受信し、デコードするステップを含む請求項１または２記載の方法。
分岐予測情報（２１００）をストアするように構成された１次レベルキャッシュ（２０６）と、
前記分岐予測情報の一部（２１２０，２１２２）をストアするように構成された２次レベルキャッシュ（２６０）と、
前記１次レベルキャッシュ（２０６）および前記２次レベルキャッシュ（２６０，１８２８）に結合された回路系（４００）とを備え、前記回路系は、
前記１次レベルキャッシュが第１のアドレスに対応する第１分岐予測情報を有さないことを検出し、
前記２次レベルキャッシュが前記第１のアドレスに対応し、前記第１分岐予測情報の一部を含む第２分岐予測情報を有するかどうかを判定し、
前記２次レベルキャッシュが前記第２分岐予測情報を有することが検出されると、前記第１分岐予測情報を再生成するように構成され、前記回路系は、前記第１分岐予測情報を再生成するために、さらに、
分岐命令のタイプを示す第３分岐予測情報を生成し、
前記第２分岐予測情報と、前記第３分岐予測情報とを組み合わせ、
前記第１のアドレスに対応する、前記１次レベルキャッシュの第１のエントリに前記第１の分岐予測情報として、前記組み合わせられた第２および第３分岐予測情報をストアするように構成されている、分岐予測機構。
前記回路系（４００）は、
前記１次レベルキャッシュの前記第１のエントリが使用可能であるかどうかを判定し、
前記第１のエントリが使用不可能であることが検出されると、前記第１のエントリの内容を排除し、
前記排除を受けて、前記内容の一部を前記２次レベルキャッシュにストアするようにさらに構成されている請求項４記載の分岐予測機構。
前記第３分岐予測情報を生成するために、前記回路系は、前記第１アドレスに対応するプログラム命令を受信し、デコードするように構成されている、請求項４または５記載の分岐予測機構。
前記プログラム命令は、前記第２次レベルキャッシュ（２６０，１８２８）からフェッチされる、請求項６記載の分岐予測機構。
相互接続（２６２４）と、
前記相互接続に結合されたメモリ（２６０４）と、
分岐予測情報をストアするように構成された２次レベルキャッシュ（２６０，１８２８）と、
１次レベルキャッシュ（２０６）を備えたプロセッサ（１０）とを備え、前記プロセッサは、
前記１次レベルキャッシュ（２０６）が第１のアドレスに対応する第１分岐予測情報を有さないことを検出し、
前記２次レベルキャッシュ（２６０，１８２８）が前記第１のアドレスに対応し、前記第１分岐予測情報の一部を含む第２分岐予測情報を有するかどうかを判定し、
前記２次レベルキャッシュが前記第２分岐予測情報を有することが検出されると、前記第１の分岐予測を再生成するように構成され、前記プロセッサは、前記第１分岐予測情報を再生成するために、さらに、
分岐命令のタイプを示す第３分岐予測情報を生成し、
前記第２分岐予測情報と、前記第３分岐予測情報とを組み合わせ、
前記第１のアドレスに対応する、前記１次レベルキャッシュの第１のエントリ（２１００）に前記第１の分岐予測として、前記組み合わせられた第２および第３分岐予測情報をストアするように構成されている、コンピュータシステム。
前記プロセッサ（１０）は、前記１次レベルキャッシュ（２０６）の前記第１のエントリ（２１００）が使用可能であるかどうかを判定し、前記第１のエントリが使用不可能であることが検出されると、前記第１のエントリ（２１００）の内容を排除し、前記排除を受けて、前記内容の一部を前記２次レベルキャッシュ（２６０，１８２８）にストアするようにさらに構成されている請求項８記載のコンピュータシステム。
前記２次レベルキャッシュ（２６０，１８２８）および前記１次レベルキャッシュ（２０６）は重複する情報をストアしない、請求項１、２または３記載の方法。
前記２次レベルキャッシュ（２６０，１８２８）は、前記１次レベルキャッシュ（２０６）から排除された情報のみをストアするように構成されている、請求項１０記載の方法。
前記第３分岐予測情報は、前記プログラム命令のなかの成立予測分岐の位置をさらに示す、請求項３記載の方法。
前記２次レベルキャッシュ（２６０，１８２８）および前記１次レベルキャッシュ（２０６）は重複する情報をストアしない、請求項４、５、６または７記載の分岐予測機構。
前記２次レベルキャッシュ（２６０，１８２８）は、前記１次レベルキャッシュ（２０６）から排除された情報のみをストアするように構成されている、請求項１３記載の分岐予測機構。
前記第３分岐予測情報は、前記プログラム命令のなかの成立予測分岐の位置をさらに示す、請求項６または７記載の分岐予測機構。
前記２次レベルキャッシュ（２６０，１８２８）および前記１次レベルキャッシュ（２０６）は重複する情報をストアしない、請求項８または９記載のコンピュータシステム。
前記２次レベルキャッシュ（２６０，１８２８）は、前記１次レベルキャッシュ（２０６）から排除された情報のみをストアするように構成されている、請求項１６記載のコンピュータシステム。