(57)【特許請求の範囲】
【請求項１】
所与の分岐インストラクションがヒステリシスを表わすかどうかの指示を与え、且つ所与の分岐インストラクションのための第１の分岐予測データを発生するように構成された第１の分岐プレディクタと、
第１の分岐プレディクタよりも後の時間で、所与の分岐インストラクションのための第２の分岐予測データを発生するように構成された第２の分岐プレディクタと、
前記第１の分岐予測データと第２の分岐予測データとの間に不一致があるとの決定及び前記所与の分岐インストラクションがヒステリシスを表わさないことの指示の検出に応答して前記第１の分岐プレディクタをトレーニングし、前記第１の分岐予測データと第２の分岐予測データとの間に不一致があるとの決定及び前記所与の分岐インストラクションがヒステリシスを表わすことの指示の検出に応答して、前記所与の分岐インストラクションのための第１の分岐プレディクタのトレーニングを阻止するように構成されたコントロールロジックと、
を備え、
前記ヒステリシスは、前記所与の分岐インストラクションがその分岐方向について交替するパターンを表わすことを指示するプロセッサ。
【請求項２】
第１の分岐プレディクタをトレーニングするかどうかを決定することが、ヒステリシス、第１の分岐予測データ及び第２の分岐予測データに基づいて、合成出力を決定することを含む、請求項１に記載のプロセッサ。
【請求項３】
所与の分岐インストラクションがヒステリシスを表わすこと、そして前記第１の分岐予測データ及び第２の分岐予測データの少なくとも１つは、所与の分岐インストラクションがテークンであることを指示することを、前記出力は指示しうる、請求項２に記載のプロセッサ。
【請求項４】
所与の分岐インストラクションがヒステリシスを表わすこと、そして前記第１の分岐予測データ及び第２の分岐予測データの一方は、所与の分岐インストラクションがノット・テークンであることを指示することを、前記出力は指示しうる、請求項２に記載のプロセッサ。
【請求項５】
前記第１の分岐プレディクタは、複数のエントリを伴うテーブルを含み、各エントリは、次フェッチプログラムカウンタ（ＰＣ）アドレス及びヒステリシス指示を記憶するように構成される、請求項３に記載のプロセッサ。
【請求項６】
前記第２の分岐プレディクタは、前記第１の分岐プレディクタより分岐予測精度が高い、請求項３に記載のプロセッサ。
【請求項７】
前記第２の分岐プレディクタは、前記第１の分岐プレディクタが前記第１の分岐予測データを発生するパイプ段より後方のパイプ段で、第２の分岐予測データを発生する、請求項３に記載のプロセッサ。
【請求項８】
所与の分岐インストラクションに対して第１の分岐プレディクタで第１の分岐予測データ及び前記分岐インストラクションがヒステリシスを表わすかどうかの指示を発生する段階と、
前記第１の分岐プレディクタより後の時間に、所与の分岐インストラクションに対して第２の分岐プレディクタで第２の分岐予測データを発生する段階と、
前記第１の分岐予測データと第２の分岐予測データとの間に不一致があること及び前記分岐インストラクションがヒステリシスを表わす指示がないとの決定に応答して前記第１の分岐プレディクタをトレーニングする段階と、
前記第１の分岐予測データと第２の分岐予測データとの間に不一致があるとの決定及び前記所与の分岐インストラクションがヒステリシスを有することの指示の検出に応答して、前記所与の分岐インストラクションに対する前記第１の分岐プレディクタのトレーニングを阻止する段階と、
を備え、
前記ヒステリシスは、前記所与の分岐インストラクションがその分岐方向について交替するパターンを表わすことを指示する、方法。
【請求項９】
第１の分岐プレディクタをトレーニングするかを決定することは、前記ヒステリシス、第１の分岐予測データ及び第２の分岐予測データに基づく合成出力を決定することを含む、請求項８に記載の方法。
【請求項１０】
前記所与の分岐インストラクションがヒステリシスを表わすこと、そして前記第１の分岐予測データ及び第２の分岐予測データの少なくとも１つは、所与の分岐インストラクションがテークンであることを指示することを、前記出力が指示しうる、請求項９に記載の方法。
【請求項１１】
前記所与の分岐インストラクションがヒステリシスを表わすこと、そして前記第１の分岐予測データ及び第２の分岐予測データの一方は、前記所与の分岐インストラクションがノット・テークンであることを指示することを、前記出力が指示しうる、請求項９に記載の方法。
【請求項１２】
前記所与の分岐インストラクションがヒステリシスを示さないこと、そして前記所与の分岐インストラクションがテークンであることを前記第２の分岐予測データが指示することを前記出力が指示するとの決定に応答して、前記第１の分岐プレディクタをトレーニングし、そして前記所与の分岐インストラクションがヒステリシスを表わすことを指示するように前記指示をセットする段階を更に備えた、請求項９に記載の方法。
【請求項１３】
分岐予測を行うように動作できるプログラムインストラクションを含むコンピュータ読み取り可能な記憶媒体において、前記プログラムインストラクションは、
所与の分岐インストラクションに対して第１の分岐プレディクタで第１の分岐予測データ及び前記分岐インストラクションがヒステリシスを表わすかどうかの指示を発生し、
前記第１の分岐プレディクタより後の時間で、所与の分岐インストラクションに対して第２の分岐プレディクタで第２の分岐予測データを発生し、
前記第１の分岐予測データと第２の分岐予測データとの間に不一致があること及び前記分岐インストラクションがヒステリシスを有することの指示がないことの決定に応答して前記第１の分岐プレディクタをトレーニングし、
前記第１の分岐予測データと第２の分岐予測データとの間に不一致があると決定すること及び前記所与の分岐インストラクションがヒステリシスを有していることの指示を検出することに応答して、前記所与の分岐インストラクションに対する前記第１の分岐予測データのトレーニングを阻止する、
ように実行することができ、
前記ヒステリシスは、前記所与の分岐インストラクションがその分岐方向について交替するパターンを表わすことを指示する、コンピュータ読み取り可能な記憶媒体。
【請求項１４】
第１の分岐プレディクタをトレーニングするかどうかを決定することは、前記ヒステリシス、前記第１の分岐予測データ及び前記第２の分岐予測データに基づいて、合成出力を決定することを含む、請求項１３に記載の記憶媒体。
【請求項１５】
（１）所与の分岐インストラクションがヒステリシスを表わすこと、かつ、前記第１の分岐予測データ及び第２の分岐予測データの少なくとも１つが、所与の分岐インストラクションがテークンであることを、前記出力が指示しうるか、又は、（２）所与の分岐インストラクションがヒステリシスを表わすこと、かつ、前記第１及び第２の分岐予測データの一方が、所与の分岐インストラクションがノット・テークンであることを指示しうるものであるかのいずれかを、前記出力が指示する、請求項１４に記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マイクロプロセッサに関するもので、より特定すれば、分岐予測メカニズムに関する。
【背景技術】
【０００２】
各クロックサイクル中に、マイクロプロセッサは、理想的には、パイプラインの段ごとにインストラクションの有用な実行を生じさせる。しかしながら、パイプラインにストールが生じると、１つ以上の特定パイプライン段の間に有用な仕事が行われるのを妨げる。あるストールは、数クロックサイクル持続して、プロセッサの性能を著しく低下させる。ストールの一例は、予測ミス分岐インストラクションである。
【０００３】
ストールの否定的な影響を減少するための技術は、パイプライン段をオーバーラップさせ、インストラクションの順序ずれした実行を許し、そして同時マルチスレッディングをサポートすることを含む。しかしながら、数クロックサイクルのストールは、全てのストールサイクルを隠すことを妨げる順序正しい撤退のためにプロセッサの性能を依然として低下させる。この性能ロスを防止するために、マルチサイクルストールの発生を減少する技術が使用される。そのような技術の一例は、分岐予測である。
【０００４】
分岐予測技術は、分岐インストラクションの条件の評価を予測する。更に、分岐予測技術は、分岐ターゲットアドレスを予測する。高い精度にするために分岐予測ロジックが複雑なものとなる。それ故、分岐予測ロジックは、複数のクロックサイクルを使用して評価及び計算を遂行し、条件に対する結果及び分岐ターゲットアドレスを生じさせる。しかしながら、これらの複数のクロックサイクル中に、インストラクションがインストラクションキャッシュからフェッチされる。これらのフェッチされたインストラクションは、分岐予測ロジックが他のインストラクションをフェッチすべきであると決定した場合にフラッシュされる。
【０００５】
分岐予測ロジックは、精度を犠牲にして早く結果を出すロジックを使用する。しかしながら、精度が低いことは、変化する分岐パターンを伴う小さな繰り返しループ分岐が適切に評価されないという事態を招く。この場合、大半の時間予測ミスを招き、それに対応するパイプラインにおけるインストラクションを常時フラッシュさせる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以上に鑑み、効率的な分岐予想のための効率的な方法及びメカニズムが要望される。
【課題を解決するための手段】
【０００７】
効率的な分岐予測を行うためのシステム及び方法が提供される。一実施形態において、プロセッサは、２つの分岐プレディクタを備えている。第１の分岐プレディクタは、分岐方向及び分岐ターゲットアドレスのような分岐予測データを素早く発生する。ある実施形態において、第１の分岐プレディクタは、単一サイクル内に分岐予測データを発生する。第２の分岐プレディクタは、その後の時間に、より高い予測精度で分岐予測データを発生する。コントロールロジックは、第１及び第２の分岐プレディクタの各々からの分岐予測データが一致するかどうか決定する。
【０００８】
コントロールロジックが不一致の発生を決定した場合には、コントロールロジックは、第１のプレディクタをトレーニングする。このトレーニングは、第１のプレディクタにおける記憶された値を、第２の分岐プレディクタによって発生される分岐予測データで更新することを含む。しかしながら、不一致の検出にも関わらず、コントロールロジックは、トレーニングを遂行しないと決定する。第１のプレディクタ又は別の位置は、特定の分岐インストラクションに対するヒステリシスの指示を記憶する。ヒステリシスの指示は、所与の分岐インストラクションがその分岐方向に関して頻繁に交替するパターンを表わすことを指示する。そのような振舞いは、トレーニングが、変化する分岐方向に追従できないために分岐予測ミスを招くことがある。そのような状態が生じると決定されたときには、コントロールロジックが、第１のプレディクタのトレーニングを阻止する。
【０００９】
これら及び他の実施形態は、以下の説明及び添付図面から更に明らかとなろう。
【図面の簡単な説明】
【００１０】
【図１】プロセッサの前端の一実施形態を示す一般化されたブロック図である。
【図２】次フェッチプレディクタの一実施形態を示す一般化されたブロック図である。
【図３】効率的な次フェッチ予測のための方法の一実施形態を示す一般化されたフローチャートである。
【図４】次フェッチプレディクタのためのトレーニング更新ロジック４００の一実施形態を示す一般化されたブロック図である。
【図５】効率的な分岐予測トレーニングのための方法の一実施形態を示す一般化されたフローチャートである。
【発明を実施するための形態】
【００１１】
本発明は、種々の変更を受けそして別の形態でも実施できるが、その特定の実施形態を一例として添付図面に示して以下に詳細に説明する。しかしながら、添付図面及び詳細な説明は、本発明を、ここに開示する特定の形態に限定するものではなく、本発明は、特許請求の範囲に規定される本発明の精神及び範囲内に入る全ての変更、等効物及び代替え物を網羅することを理解されたい。本出願全体にわたって使用される「〜してもよい(may)」という語は、許すという意味（即ち、〜の潜在性があるという意味）で使用されるもので、強制の意味（即ち、〜しなければならないという意味）ではない。同様に、「含む(include)」、「含んでいる(including)」及び「含む(includes)」という語は、含むことを意味するが、それに限定されない。
【００１２】
種々のユニット、回路又は他のコンポーネントは、１つ又は複数のタスクを遂行するように「構成される」ものとして述べる。この点について、「構成される」とは、動作中に１つ又は複数のタスクを遂行する「回路を有する」ことを一般的に意味する構造を広く表現するものである。従って、ユニット／回路／コンポーネントは、そのユニット／回路／コンポーネントが現在オンでなくても、タスクを遂行するように構成することができる。一般的に、「構成される」に対応する構造を形成する回路は、ハードウェア回路を含む。同様に、種々のユニット／回路／コンポーネントは、説明の便宜上、１つ又は複数のタスクを遂行するものとして説明されてもよい。そのような説明は、「構成される」という句を含むものと解釈されねばならない。１つ以上のタスクを遂行するように構成されたユニット／回路／コンポーネントを表現する場合に、そのユニット／回路／コンポーネントに関して３５Ｕ.Ｓ.Ｃ.§１１２、第６節の解釈を引用しないことが明確に意図される。
【００１３】
以下の説明において、本発明の完全な理解を与えるために多数の特定の細部が述べられる。しかしながら、当業者であれば、本発明は、これらの特定の細部を伴わずに実施できることが認識されよう。他の点では、本発明を不明瞭にしないため、良く知られた回路、構造及び技術は、詳細に説明しない。
【００１４】
図１は、プロセッサ１００の前端の一実施形態を示す一般化されたブロック図である。パイプライン１００は、インストラクションを処理するために少なくとも１つの多段パイプラインを使用する。インストラクションキャッシュ（ｉ−キャッシュ）１２０は、ソフトウェアアプリケーションのためのインストラクションを記憶する。アドレスセレクタ１１０により搬送されるプログラムカウンタ（ＰＣ）アドレスにより指示される１つ以上のインストラクションは、ｉ−キャッシュ１２０からフェッチされる。ｉ−キャッシュミスがない場合にはクロックサイクル当たり複数のインストラクションがｉ−キャッシュ１２０からフェッチされる。
【００１５】
プロセッサ１００は、１つ以上のバーチャルアドレススペースが実行中のソフトウェアに見えるようにするアドレス変換スキームを実施する。バーチャルアドレススペース内のメモリアクセスは、プロセッサ１００に使用できる実際の物理的メモリに対応する物理的アドレススペースへ変換される。アドレス変換を使用するプロセッサ１００の実施形態では、ｉ−キャッシュ１２０は、バーチャルアドレスビットではなく物理的アドレスビットを使用して部分的に又は完全にアドレスされる。例えば、ｉ−キャッシュ１２０は、キャッシュインデックスに対してバーチャルアドレスビットを、そしてキャッシュタグに対して物理的アドレスビットを使用する。
【００１６】
キャッシュアクセスを遂行するときに全メモリ変換を遂行するコストを回避するため、プロセッサ１００は、最近及び／又は頻繁に使用されるバーチャル／物理的アドレス変換のセットを、変換ルックアサイドバッファ（ＴＬＢ）に記憶し、このバッファは、例示を容易にするために図示されていない。
【００１７】
インクリメンタ１１２は、次の順次ＰＣアドレスを発生する。一実施形態において、次フェッチプレディクタ１３０及び分岐プレディクタ１５０の各々は、アドレスセレクタ１１０においてインストラクションのフェッチを変更する。例えば、無条件分岐ｏｐｃｏｄｅに関連した絶対アドレス値がアドレスセレクタ１１０へ送られる。このアドレス値は、分岐ターゲットアドレス又は次フェッチプログラムカウンタ（ＰＣ）アドレスとも称される。次フェッチプレディクタ１３０及び分岐プレディクタ１５０の各々は、予測される分岐ターゲットアドレスをアドレスセレクタ１１０へ送る。
【００１８】
次フェッチプレディクタ１３０は、所与の分岐インストラクションに対する高速予測に基づいて非順次ＰＣアドレスを発生する。ある実施形態では、次フェッチプレディクタ１３０は、次フェッチテーブル１３２及び次フェッチコントロールロジック１３４を含む。一実施形態において、次フェッチコントロールロジック１３４は、ハッシュ関数において、ｉ−キャッシュ１２０からインストラクションをフェッチするのに使用されるＰＣアドレスの少なくとも一部分を、それ自体の別の部分、又は他の値と合成する。この特定のハッシュ関数は、比較的高速の排他的オア（ＸＯＲ）合成（又は合成）関数である。このハッシュ関数の出力は、次フェッチテーブル１３２をインデックスするのに使用される。次フェッチテーブル１３２においてヒットが生じると、ｉ−キャッシュ１２０からインストラクションをフェッチするのに使用するための次のＰＣアドレスを与える。一実施形態では、次フェッチプレディクタは、単一サイクルプレディクタである。
【００１９】
又、分岐プレディクタ１５０は、ｉ−キャッシュ１２０からインストラクションをフェッチするのに使用されるＰＣアドレスの少なくとも一部分を受け取る。又、分岐プレディクタ１５０は、個別のハッシュ関数において、その受け取ったＰＣアドレスの少なくとも一部分を、それ自体の別の部分、又は履歴情報のような他の値と合成する。種々のハッシュ関数は、１つ以上のパターン履歴テーブル（ＰＨＴ）、分岐ターゲットバッファ（ＢＴＢ）、及び／又は分岐予測データを与えるのに使用される他のテーブルへのインデックスを決定するために遂行される。分岐予測データは、分岐方向及び分岐ターゲットアドレスを含む。分岐プレディクタ１５０は、複数のクロックサイクルを使用して、分岐インストラクションの条件の成果を決定すると共に、分岐ターゲットアドレスを決定する。
【００２０】
分岐プレディクタ１５０は、次フェッチプレディクタ１３０より予測精度の高い分岐予測データを与える。しかしながら、分岐プレディクタ１５０は、精度の高い分岐予測データを発生するために複数のサイクルを使用する。それ故、次フェッチプレディクタ１３０は、迅速な初期分岐予測を与えるのに使用される。それに続いて、分岐プレディクタ１５０は、初期分岐予測を後で検証する。
【００２１】
次フェッチプレディクタ１３０により発生される予測データは、プロセッサ１００のパイプラインに沿って記憶され段階化される。その段階化された予測データは、分岐プレディクタ１５０によりその後のパイプ段で発生される予測データと比較される。次フェッチプレディクタ１３０が、その後に分岐プレディクタ１５０により発生される予測データに一致しない分岐予測データを発生するときには、次フェッチプレディクタ１３０は、分岐プレディクタ１５０により発生される予測データで更新され又はトレーニングされる。ここで使用する、次フェッチプレディクタ１３０のトレーニングとは、次フェッチプレディクタ１３０に記憶されたパラメータに、分岐プレディクタに１５０より発生される分岐予測データを書き込むか又はそれで更新することを含む。頻繁に交替するパターンを伴う分岐インストラクションは、多数の分岐予測ミスを引き起こすことがある。多数の分岐予測ミスは、分岐プレディクタ１５０による次フェッチプレディクタ１３０のトレーニングが頻繁に交替するパターンを保持できないことから生じる。
【００２２】
一実施形態において、次フェッチテーブル１３２は、対応する分岐インストラクションがヒステリシスを示すかどうかの指示を記憶する。ヒステリシスは、対応する分岐インストラクションがその分岐方向について頻繁に交替するパターンを有することを指示する。例えば、対応する分岐インストラクションは、テークン(taken)とノット・テークン(not-taken)との間で頻繁に交替する。ある実施形態では、次フェッチテーブル１３２の各エントリがヒステリシスビットを記憶する。一例において、セットされたヒステリシスビットは、対応する分岐インストラクションが頻繁に交替するパターンを示すことを指示する。リセットされたヒステリシスビットは、対応する分岐インストラクションが頻繁に交替するパターンを示さないことを指示する。
【００２３】
次フェッチプレディクタ１３０により発生された分岐予測データと、同じ分岐インストラクションに対して分岐プレディクタ１５０によって発生された分岐予測データとの間に不一致が見つかったときには、コントロールロジックが、次フェッチプレディクタ１３０をトレーニングすべきかどうか決定する。このコントロールロジックは、分岐インストラクションに対するヒステリシスの対応指示を使用する。ヒステリシスの指示は、次フェッチプレディクタ１３０のその後のトレーニングを阻止する。ヒステリシスの指示を使用して分岐予測を改善するための方法及びメカニズムを以下に詳細に説明する。先ず、パイプライン１００を更に詳細に説明する。
【００２４】
デコードユニット１４０は、複数のフェッチされたインストラクションのｏｐｃｏｄｅをデコードする。或いは又、インストラクションは、マイクロインストラクション又はマイクロｏｐに分割されてもよい。ここに使用する「インストラクション」及び「マイクロｏｐ」という語は、交換可能である。というのは、本発明は、各々の具現化を使用するアーキテクチャーに使用されるからである。デコードユニット１４０は、付加的なデコードされた情報を伴うインストラクションを、その後のパイプ段でのインストラクション処理のためにプロセッサ１００の他のコンポーネントへ送信する。例えば、デコードユニット１４０は、ディスパッチキューにおいてエントリを割り当てる。その後のインストラクション処理ステップは、例えば、レジスタの再ネーミング、インストラクションスケジューリング、演算動作の実行及び／又はメモリアクセスの遂行、及び順序正しい撤退である。インストラクション処理ユニット１６０は、一般的に、これらのステップの１つを遂行する。
【００２５】
図２は、次フェッチプレディクタ２００の一実施形態を示す一般化されたブロック図である。図示されたように、次フェッチプレディクタ２００は、現在フェッチＰＣ２０２を受け取る。その受け取られた現在フェッチＰＣ２０２は、現在分岐インストラクションを識別するｉ−キャッシュ１２０からのインストラクションをフェッチするのに使用されるアドレスの充分な数のビットを含む。現在フェッチＰＣ２０２は、アドレスセレクタ１１０からのものである。現在フェッチＰＣ２０２でフェッチされた複数のインストラクション内の２つ以上の分岐インストラクション間の曖昧さをなくし及びエイリアシングを回避するために１つ以上の方法を使用することができる。
【００２６】
一実施形態において、その受け取られた現在フェッチＰＣ２０２のビットのハッシュは、ハッシュ関数２２０によりそれ自身で遂行される。一例において、現在フェッチＰＣ２０２のオフセット部分は、ハッシュ関数２２０内の排他的オア（ＸＯＲ）合成関数により現在フェッチＰＣ２０２の上位ビットと合成される。他の例では、オフセット部分は、現在フェッチＰＣ２０２の各上位ビット以外のビットと合成される。更に、非連続ビット及び他の合成ロジックが使用されてもよい。履歴情報、カウント値、等の他の値（図示せず）が使用されてもよい。多数のそのような変形例が考えられ、意図される。しかしながら、種々の実施形態では、次フェッチプレディクタ２００による分岐予測データの発生は、単一クロックサイクル後に予想される。それ故、ハッシュ関数２２０の機能は、迅速且つ効率的なハッシュ計算に向けられる。
【００２７】
次フェッチプレディクタ２００は、次フェッチテーブル２４０を含む。次フェッチテーブル２４０は、少なくともハッシュ関数２２０の出力によりインデックスされる。次フェッチテーブル２４０は、分岐インストラクションに対応する情報であって、分岐予測データを発生するのに使用される情報を記憶する。分岐予測データは、分岐方向及び分岐ターゲットアドレス、例えば、予測される次フェッチＰＣアドレスを含む。次フェッチテーブル２４０は、条件付き及び無条件分岐インストラクションのための情報を記憶する。更に、次フェッチテーブル２４０は、直接的及び間接的分岐インストラクションのための情報を記憶する。
【００２８】
条件付き分岐インストラクションは、インストラクションストリームにおいてどの経路をとるべきかの決定を行う。分岐インストラクションが、条件が満足されないと決定する場合には、分岐インストラクションは、ノット・テークンと考えられ、プログラム順序における次の順次インストラクションが実行される。しかしながら、分岐インストラクションが、条件が満足されると決定する場合には、分岐インストラクションは、テークンと考えられる。テークンの分岐インストラクションの場合には、プログラム順序において次の順次インストラクションでないが、計算された分岐ターゲットアドレスに位置するインストラクションが実行される。無条件分岐インストラクションは、常にテークンの条件付き分岐インストラクションと考えられる。テストするための条件はなく、順次の順序以外のシーケンスでインストラクションの実行が行われる。
【００２９】
直接的分岐インストラクションの場合には、分岐ターゲットアドレスが、プログラムカウンタ（ＰＣ）値に対するオフセットにより指定され、オフセットは、分岐インストラクションそれ自体に記憶される。間接的分岐インストラクションの場合には、分岐ターゲットアドレスがレジスタ又はメモリの値により指定され、レジスタ又はメモリ位置は、分岐インストラクションにおいて識別される。更に、分岐ターゲットアドレスを指定するレジスタ又はメモリ位置には、異なる値がロードされてもよい。
【００３０】
一実施形態において、次フェッチテーブル２４０は、複数のエントリ２４２ａ−２４２ｇを有する。これらエントリ２４２ａ−２４２ｇの各々は、少なくともフィールド２５０−２５６のような幾つかのフィールドを含む。一実施形態において、フィールド２５０は、少なくとも有効ビットのような状態情報を記憶する。フィールド２５２は、ハッシュ出力識別子（ＩＤ）を記憶する。この識別子の値は、早い時期にハッシュ関数２２０により発生された値である。一実施形態において、フィールド２５２は、ハッシュされたフェッチＰＣアドレスの付加的なビットを記憶する。他の実施形態では、ハッシュ出力ＩＤは、迅速な個別のルックアップを次フェッチテーブル２４０に与えるのに充分なものである。
【００３１】
テーブル２４０のフィールド２５４は、対応する分岐インストラクションのための予測される次フェッチＰＣアドレス値を記憶する。フィールド２５６は、対応する分岐インストラクションがヒステリシスを伴う分岐振舞いを示すかどうかの指示を記憶する。例えば、対応する分岐インストラクションは、その分岐方向について頻繁に交替するパターンを有する。極端な場合に、対応する分岐インストラクションは、分岐インストラクションの各実行中に、テークン（Ｔ）方向と、ノット・テークン（ＮＴ）方向との間で交替する。パターンは、Ｔ、ＮＴ、Ｔ、ＮＴ、等のように見える。そのようなパターンは、次フェッチプレディクタ２００をトレーニングしながら検出することが困難である。次フェッチプレディクタ２００は、対応する分岐インストラクションの各発生後に再トレーニングされるが、再トレーニングは、次フェッチプレディクタ２００が再び分岐インストラクションを予測ミスすることを招き得る。それ故、フィールド２５６に記憶されたヒステリシスの指示は、対応する分岐インストラクションの少なくとも１つの発生の間、再トレーニングを停止するのに使用される。一実施形態において、フィールド２５６は、ヒステリシスを指示するための単一ビットを記憶する。
【００３２】
少なくともハッシュ関数２２０の出力は、次フェッチテーブル２４０をインデックスするのに使用される。ハッシュ関数２２０の出力と、エントリ２４２ａ−２４２ｇのフィールド２５２に記憶されたハッシュ出力ＩＤとの比較が遂行される。一致が見つかると、対応する次フェッチＰＣと、フィールド２５４及び２５６に記憶されたヒステリシスの指示が、次フェッチテーブル２４０から読み取られる。ヒット状態と、対応する分岐インストラクションを識別するのに使用されるハッシュ出力ＩＤは、フィールド２５４及び２５６に記憶されたデータとグループ化される。このデータは、全て、段階化され、そしてその後のパイプ段へ送られて、分岐プレディクタ１５０のコントロールロジックにより使用される。分岐プレディクタ１５０は、受け取られたデータが、後で発生される分岐予測データと一致するかどうか検証する。分岐プレディクタ１５０にデータを送信するのに加えて、次フェッチテーブル２４０から読み取られた次フェッチＰＣがアドレスセレクタ１１０へ送信される。
【００３３】
又、次フェッチプレディクタ２００は、分岐プレディクタ１５０からも情報を受信する。この情報は、次フェッチプレディクタ２００からの分岐予測データが分岐プレディクタ１５０によって発生された分岐予測データに一致するかどうか分岐プレディクタ１５０が検証した後に受信される。次フェッチプレディクタ２００は、トレーニングコントロール信号２０４、ハッシュ出力ＩＤ２０６、次フェッチＰＣアドレス２０８、及び所与の分岐インストラクションに対するヒステリシス２１０の指示を受信する。分岐プレディクタから受信されるこのデータは、更新ロジック２３０へ送信される。更新ロジックは、次フェッチテーブル２４０にデータをいつ書き込むべきか及びエントリ２４２ａ−２４２ｇのうちのどのエントリを変更すべきか決定する。
【００３４】
トレーニングコントロール信号２０４は、次フェッチテーブル２４０の特定エントリを変更するための分岐プレディクタ１５０からの指示である。ハッシュ出力ＩＤ２０６は、次フェッチテーブルへインデックスしそしてエントリ２４２ａ−２４２ｇのうちの所与のエントリを識別するのに使用される。次フェッチＰＣ２０８は、識別されたエントリのフィールド２５４に記憶されたＰＣ値をオーバーライトするのに使用される。同様に、ヒステリシス２１０の受け取られた指示は、識別されたエントリのフィールド２５６に記憶された指示をオーバーライトするのに使用される。
【００３５】
次フェッチプレディクタ２００へ送られるトレーニングコントロール信号２０４又は他の指示子は、識別されたエントリにおいてどのフィールドにオーバーライトすべきか識別する。あるケースでは、次フェッチＰＣ及びヒステリシスの指示の両方が更新される。他のケースでは、これら２つの値の一方が更新されるが、他方は変更されない。あるケースでは、次フェッチプレディクタ２００及び分岐プレディクタ１５０により発生される分岐予測データ間の不一致が決定されるが、次フェッチプレディクタ２００のトレーニングは行われない。これらのケースでは、トレーニング信号２０４は、対応する分岐インストラクションに対し次フェッチテーブル２４０において変更が遂行されないことを指示する。
【００３６】
図３は、効率的な次フェッチ予測のための方法３００の一実施形態を示す一般化されたフローチャートである。説明上、この実施形態及び以下に述べる方法のその後の実施形態におけるステップは、連続的な順序で示されている。しかしながら、他の実施形態では、あるステップは、図示された以外の順序で行われてもよく、あるステップは、同時に遂行されてもよく、あるステップは、他のステップと組み合わされてもよく、そしてあるステップは、存在しなくてもよい。
【００３７】
ブロック３０２において、インストラクションをフェッチするために所与のプログラムカウンタ（ＰＣ）が送られる。ブロック３０４において、ハッシュ関数を使用して所与のＰＣの１つ以上のビットが他のコントロール値と合成される。他のコントロール値は、先に述べたように、所与のＰＣ内の他のビットである。ブロック３０６において、少なくともハッシュ関数の出力を使用して次フェッチテーブルをインデックスする。次フェッチテーブルにおいてミスが生じた場合には（条件付きブロック３０８）、ブロック３１０において、次の順次ＰＣを使用してインストラクションをフェッチする指示が送られる。この指示は、次フェッチプレディクタからアドレスセレクタへ送られる。
【００３８】
次フェッチテーブルにおいてヒットが生じた場合には（条件ブロック３０８）、ブロック３１２において、ヒットに対応してエントリに記憶された次フェッチＰＣが、インストラクションフェッチに使用するために送られる。次フェッチＰＣがアドレスセレクタに送られる。ブロック３１４において、分岐予測データを検証するために、分岐予測データが分岐プレディクタ１５０のような第２の分岐プレディクタへ送られる。分岐予測データは、少なくとも、次フェッチＰＣ、ヒステリシスの指示、ヒット／ミス状態を含む。ヒット／ミス状態は、予測されるテークン／ノット・テークン分岐方向を含む。
【００３９】
図４は、次フェッチプレディクタのためのトレーニング更新ロジック４００の一実施形態を示す一般化されたブロック図である。一実施形態において、トレーニング更新ロジック４００は、次フェッチプレディクタ、及び次フェッチプレディクタを検証するのに使用される分岐プレディクタの各々からの分岐予測データ間の不一致を決定するのに応答して出力を発生するように使用される。例えば、これら２つのプレディクタの各々により発生される次フェッチＰＣアドレスは、同じでなくてもよい。典型的に、次フェッチプレディクタのトレーニングは、次の通りである。しかしながら、方向のような、対応する分岐インストラクションの頻繁に交替するパターンによる持続する予測ミスを防止するために、トレーニング更新ロジック４００は、トレーニングをスキップできるかどうか決定する。ある実施形態では、不一致の適格化は、不一致が生じないときにエネルギー消費を節約するためにトレーニング更新ロジック４００内のロジックアップフロントを可能にする。他の実施形態では、不一致の適格化は、トレーニング更新ロジック４００の結果に対して使用されて、結果を使用すべきかどうか決定する。
【００４０】
一実施形態において、更新ロジック４２０は、より精度の高い分岐プレディクタから、テークン状態信号４１０のような予測分岐方向を受け取る。更に、更新ロジック４２０は、高速分岐プレディクタから、予測分岐方向及びヒステリシスの指示を受け取る。一実施形態において、高速分岐プレディクタは、次フェッチテーブルを伴う単一サイクルの次フェッチプレディクタである。予測分岐方向は、テーブルヒット状態によって指示される。ヒステリシスの指示は、（例えば）次フェッチテーブルの各エントリに記憶された単一ビットである。それ故、更新ロジック４２０は、次フェッチプレディクタからヒット状態４１２及び単一ヒステリシスビット４１４を受け取る。高速分岐プレディクタ及びそれにより生じる分岐予測データのための他の実施形態も考えられ、意図される。
【００４１】
トレーニングが行われるかどうか決定するために、更新ロジック４２０内のコントロールロジック及びアルゴリズムは、多数の異なる仕方で具現化される。ある具現化の例は、組み合わせロジックゲート、状態ダイアグラム、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、並びにハードウェア記述言語又は高レベルＣプログラミング言語のようなプログラミング言語のプログラムコードを含む。プログラムコードは、ハードディスク、マザーボード上のコンピュータシステムメモリ、フロッピー（登録商標）ディスク又は他のポータブルメモリ記憶装置、等の非一時的記憶媒体に記憶される。プログラムコードのインストラクションは、プロセッサへロードされそしてプロセッサ内のハードウェアで実行されて、プログラムコードで記述されたアルゴリズムを遂行する。一実施形態において、更新ロジック４２０は、２つの分岐プレディクタから受け取った値を使用して、次フェッチプレディクタのような高速分岐プレディクタにより使用される次フェッチＰＣアドレスを、より高精度の分岐プレディクタにより発生される次フェッチＰＣアドレスによりオーバーライトすべきかどうか決定する。
【００４２】
更新ロジック４２０の行４４２は、行４４０及び列４２４−４３０に示す条件が真と評価されるかどうかに基づき次フェッチＰＣアドレスに対する特定の更新シナリオを示す。一例において、行４４０及び列４２８に示すように、次フェッチプレディクタがリセットヒステリシスビット（ＮＯＴヒステリシス）を与え、リセットビットがそれに対応する分岐インストラクションに対して検出されたヒステリシスを指示せず、且つ分岐プレディクタの検証でテークン分岐方向が発生される場合には、トレーニングが行われる。トレーニングは、次フェッチプレディクタに記憶された対応する分岐インストラクションのための次フェッチＰＣアドレスを、検証分岐プレディクタにより発生される次フェッチＰＣアドレスでオーバーライトすることを含む。図２を再び参照すれば、信号２０４−２１０は、検証分岐プレディクタから次フェッチプレディクタ２００へ送られる。信号２０４−２１０の情報は、エントリ２４２ａ−２４２ｇのうちの特定エントリを識別し、そして次フェッチＰＣアドレスを記憶する少なくともフィールド２５４をオーバーライトするのに使用される。
【００４３】
図４の更新ロジック４２０の行４４０及び列４２８に示す評価条件で続けると、次フェッチプレディクタに記憶された対応する分岐インストラクションのためのヒステリシスビットがセットされる。ヒステリシスビットをセットすることは、次フェッチプレディクタに記憶された次フェッチＰＣアドレスをオーバーライトすることに加えて行われる。図２を再び参照すれば、信号２０４−２１０の情報は、先に述べたように、エントリ２４２ａ−２４２ｇのうちの特定のエントリを識別し、そして対応する分岐インストラクションのためのヒステリシスの指示を記憶する少なくともフィールド２５６をオーバーライトするのに使用される。図４に戻ると、更新ロジック４２０の行４４４は、列４２４−４３０に示す条件が真と評価されるかどうかに基づき対応分岐インストラクションのためのヒステリシスの指示に対する特定の更新シナリオを例示する。
【００４４】
この場合も、行４４０及び列４２４−４３０の各々に示す条件は、次フェッチプレディクタと、より高精度の検証分岐プレディクタとの間の分岐予測データの不一致で適格化される。この適格化は、更新ロジック４２０のアルゴリズムを使用する前に行われる。或いは又、この適格化は、更新ロジック４２０のアルゴリズムで結果が見つかった後に行ってもよい。別の例では、行４４０及び列４３０に示すように、次フェッチプレディクタがリセットヒステリシスビットを与え、そのリセットビットがそれに対応する分岐インストラクションに対するヒステリシス検出を指示せず、且つ次フェッチテーブル内にヒット状態がある場合には、トレーニングが行われる。この場合のトレーニングは、次フェッチプレディクタに記憶された対応分岐インストラクションに対して次フェッチＰＣアドレスを無効化することを含む。この特定の次フェッチＰＣアドレスを無効化することは、次フェッチテーブル２４０のエントリ２４２ａ−２４２ｇのうちの対応エントリを無効化することにより達成される。更に、この識別されたエントリにおいて対応ヒステリシスビットがセットされる。
【００４５】
更新ロジック４２０において行４４０及び列４２４、４２６により識別される各ケースについては、トレーニングがスキップされる。トレーニングは、これらのケースでは、次フェッチプレディクタと、より高精度の検証分岐プレディクタとの間で分岐予測データに不一致が検出されても、スキップされる。トレーニングのスキップは、分岐方向について頻繁に交替するパターンを示す特定の分岐インストラクションに対して分岐予測精度を高める。一例において、ｉ−キャッシュ１２０は、クロックサイクル当たり４つのフェッチされたインストラクションを与え、そしてより高精度の検証分岐プレディクタは、５つのクロックサイクルを使用して、分岐予測データを発生する。次フェッチプレディクタと、より高精度の分岐プレディクタとの間に不一致が検出されるときまでに、２０個のインストラクションがフラッシュされることが適格である。これら２０個のインストラクションを処理するのにエネルギーが消費され、その仕事の結果は未使用である。それ故、ある条件に対してトレーニングをスキップするとの決定は、エネルギー消費を減少し、パイプラインを有用な仕事でいっぱいに保つ。
【００４６】
行４４０及び列４２４は、次フェッチプレディクタがセットヒステリシスビットを与えるときのケースを示し、セットビットは、対応する分岐インストラクションに対するヒステリシスの検出を指示する。列４２４に示すケースでは、次フェッチプレディクタが次フェッチテーブル内のヒット状態を与えるか、又はより高精度の検証分岐プレディクタが、予測されるテークン分岐方向を与える。行４４２は、このケースでは、次フェッチプレディクタに記憶された次フェッチＰＣアドレスが維持されることを示す。次フェッチプレディクタの対応する分岐インストラクションに対して変更もトレーニングも生じない。行４４４は、このケースでは、対応するヒステリシスビットがリセットされることを示し、リセット値は、対応分岐インストラクションに対してヒステリシスが検出されないことを指示する。
【００４７】
行４４０及び列４２６は、次フェッチプレディクタがセットヒステリシスビットを与えるときのケースを示し、セットビットは、対応する分岐インストラクションに対するヒステリシスの検出を指示する。列４２６に示すケースでは、次フェッチプレディクタは、次フェッチテーブル内のミス状態を与える。更に、より高精度の検証分岐プレディクタは、予測されたノット・テークン分岐方向を与える。行４４２は、このケースでは、次フェッチプレディクタに記憶された次フェッチＰＣアドレスが維持されることを示す。次フェッチプレディクタの対応分岐インストラクションに対して変更もトレーニングも生じない。行４４４は、このケースでは、対応ヒステリシスビットも維持されることを示す。
【００４８】
図５は、効率的な分岐予測トレーニングのための方法５００の一実施形態を示す一般化されたフローチャートである。説明上、この実施形態及び以下に述べる方法のその後の実施形態におけるステップは、連続的な順序で示されている。しかしながら、他の実施形態では、あるステップは、図示された以外の順序で行われてもよく、あるステップは、同時に遂行されてもよく、あるステップは、他のステップと組み合わされてもよく、そしてあるステップは、存在しなくてもよい。
【００４９】
ブロック５０２において、所与の分岐インストラクションに対して、第１の予測データが第１の分岐プレディクタにより発生される。ブロック５０４において、同じ所与の分岐インストラクションに対して、第１のプレディクタより精度の高い第２のプレディクタにより第２の予測データがその後に発生される。ブロック５０６において、第１及び第２の予測データが比較される。第１と第２の分岐予測データの間に不一致が生じないと決定された場合には（条件ブロック５０８）、ブロック５１０において、第１のプレディクタに対してトレーニングを遂行しないことを示す指示が発生される。２つの分岐プレディクタは、所与の分岐インストラクションに対して同じ結果を発生する。
【００５０】
第１と第２の分岐予測データの間に不一致が生じると決定された場合には（条件ブロック５０８）、ブロック５１２において、第１のプレディクタをトレーニングする条件が存在するかどうかの決定が、第１及び第２の予測データと、所与の分岐インストラクションに対応するヒステリシスの指示とに基づいて、行われる。再び、図４を簡単に参照すれば、これらの条件は、更新ロジック４２０の行４４０及び列４２４−４３０により指定される。第１のプレディクタをトレーニングする少なくとも１つの条件が存在すると決定された場合には（条件ブロック５１４）、ブロック１６５において、第１のプレディクタにおける予測される方向、分岐ターゲットアドレス、及びヒステリシスの指示の１つ以上が、所与の分岐インストラクションに対して、決定された条件に基づき更新される。より高精度の第２の分岐プレディクタにより発生される分岐予測データは、第１のプレディクタに記憶された値を更新するのに使用される。
【００５１】
第１のプレディクタをトレーニングする条件が存在しないと決定される場合には（条件ブロック５１４）、方法５００のコントロールフローは、ブロック５１０へ進み、第１のプレディクタに対してトレーニングが遂行されないことを示す指示が発生される。種々の実施形態において、少なくとも所与の分岐インストラクションを検出することは、分岐方向について頻繁に交替するパターンが第１のプレディクタのトレーニングを阻止することを示す。再び、図４を参照すれば、更新ロジック４２０は、ヒステリシスを使用して第１のプレディクタのトレーニングを阻止する条件を決定する一実施形態を例示する。
【００５２】
以上、本発明の実施形態を詳細に説明したが、当業者であれば、前記開示が完全に理解されると、多数の修正や変更が明らかとなろう。そのような修正や変更は、全て、特許請求の範囲に包含されることが意図される。
【符号の説明】
【００５３】
１００：プロセッサパイプライン
１１０：アドレスセレクタ
１１２：インクリメンタ
１２０：ｉ−キャッシュ
１３０：次フェッチプレディクタ
１３２：次フェッチテーブル
１３４：次フェッチコントロールロジック
１４０：デコードユニット
１５０：分岐プレディクタ
１６０：インストラクション処理ユニット
２００：次フェッチプレディクタ
２０２：プログラムカウンタ
２０４：トレーニング
２０６：ハッシュ出力ＩＤ
２０８：次フェッチプログラムカウンタ
２１０：ヒステリシス
２２０：ハッシュ関数
２３０：更新ロジック
【図１】
0005927616.tif 000002
【図２】
0005927616.tif 000003
【図３】
0005927616.tif 000004
【図４】
0005927616.tif 000005
【図５】
0005927616.tif 000006