(57)【特許請求の範囲】
【請求項１】
分岐予測の方法であって、
プロセッサが、ループに関連する分岐命令を識別することと、前記識別することは、分岐命令アドレスと実行された最終の分岐命令のアドレスとを比較することを含み、
前記ループに関連する後方分岐命令が識別されたとき、前記プロセッサが、前記後方分岐命令に関連するループの反復の回数を更新し、前記ループの反復が終了するとき、前記プロセッサが、前記ループの反復の回数を示す多ビット値を分岐ヒストリレジスタ（ＢＨＲ）に記憶することと、
を備える方法。
【請求項２】
前記ループに関連する分岐命令の分岐の方向は後方分岐である、請求項１に記載の方法。
【請求項３】
前記識別することは、前記分岐命令のＰＣが、最終分岐命令のＰＣを記憶する最終分岐ＰＣ（ＬＢＰＣ）レジスタの内容とマッチングする場合、前記分岐命令は前記ループに関連する後方分岐命令であると識別する、請求項１に記載の方法。
【請求項４】
前記識別することは、前記分岐命令のＰＣが、複数の最終分岐命令のＰＣを記憶する複数のＬＢＰＣレジスタのうちのどれかの内容とマッチングする場合、前記分岐命令は前記ループに関連する後方分岐命令であると識別する、請求項１に記載の方法。
【請求項５】
前記分岐命令は、終了ループについてコンパイラによって生成されるユニークな分岐命令である、請求項１に記載の方法。
【請求項６】
前記分岐命令のｏｐコードは、それが前記ループに関連する後方分岐命令であることを指し示す１つまたは複数のビット、を含む、請求項１に記載の方法。
【請求項７】
多ビット値を前記ＢＨＲに記憶することは、あらかじめ決定された数のビットを前記ＢＨＲに記憶することを備える、請求項１に記載の方法。
【請求項８】
前記プロセッサが、ループ反復の回数の、前記多ビット値に対する固定されたマッピングに応じて、前記あらかじめ決定された数のビットの前記値を決定すること、をさらに備える請求項７に記載の方法。
【請求項９】
前記プロセッサが、ループ反復の回数の、前記多ビット値に対するスケーラブルなマッピングに応じて、前記あらかじめ決定された数のビットの前記値を決定すること、をさらに備える請求項７に記載の方法。
【請求項１０】
前記プロセッサが、ループ反復の回数の、前記多ビット値に対する前記スケーラブルなマッピングを決定するために、複数のしきい値を読み取ること、をさらに備える請求項９に記載の方法。
【請求項１１】
多ビット値を前記ＢＨＲに記憶することは、前記ループの反復の回数に応じて変化するビットの可変な数を前記ＢＨＲに記憶することを備える、請求項１に記載の方法。
【請求項１２】
前記プロセッサが、前記ＢＨＲの下位の複数のビットでループ反復をカウントすること、をさらに備える請求項１１に記載の方法。
【請求項１３】
前記プロセッサが、ループカウンタにおいてループ反復をカウントすることと、
前記プロセッサが、前記ループが終了するときに前記ループカウンタの前記値を前記ＢＨＲに転送することと、をさらに備える請求項１１に記載の方法。
【請求項１４】
ループに関連する分岐命令を識別することは、第１のループに関連する第１の後方分岐命令と、第２のループに関連する第２の後方分岐命令を検出することを備え、前記第１のループは、前記第２のループ内でネストされる、請求項１に記載の方法。
【請求項１５】
多ビット値を前記ＢＨＲに記憶することは、前記第１のループの反復の回数を示す多ビット値を前記ＢＨＲに記憶することを備え、前記第２のループの反復の回数を示す多ビット値を前記ＢＨＲに記憶することをさらに備える、請求項１４に記載の方法。
【請求項１６】
多ビット値を前記ＢＨＲに記憶することは、前記第１のループの反復の回数を示す多ビット値だけを前記ＢＨＲに記憶することを備える、請求項１４に記載の方法。
【請求項１７】
多ビット値を前記ＢＨＲに記憶することは、前記第２のループの反復の回数を示す多ビット値だけを前記ＢＨＲに記憶することを備える、請求項１４に記載の方法。
【請求項１８】
条件付き分岐命令の評価を予測するように動作する分岐予測器と、
前記分岐予測器からの予測に基づいて命令を推論的にフェッチし実行するように動作する命令実行パイプラインと、
条件付き分岐命令の評価を記憶するように動作する分岐ヒストリレジスタ（ＢＨＲ）と、
コードループの反復の回数をカウントするように動作するループカウンタ（ＬＣ）と、
条件付き分岐命令に関連するループの反復の回数を示す多ビット値を前記ＢＨＲに記憶するように動作する制御回路と、
を備え、
前記制御回路は、ループに関連する条件付き分岐命令を識別し、前記ループに関連する条件付き分岐命令が識別されたとき前記ＬＣを更新し、前記条件付き分岐命令に関連するループの反復の終了のときに、前記多ビット値を前記ＢＨＲに記憶し、前記識別することは、前記条件付き分岐命令のアドレスと実行された最終の条件付き分岐命令のアドレスとを比較することを含む、
プロセッサ。
【請求項１９】
条件付き分岐命令のＰＣを記憶するように動作する最終分岐ＰＣ（ＬＢＰＣ）レジスタをさらに備え、前記制御回路は、前記分岐命令のＰＣが前記ＬＢＰＣの内容とマッチングする場合に、条件付き分岐命令がループに関連づけられることを決定する、請求項１８に記載のプロセッサ。
【請求項２０】
２つ以上のＬＢＰＣレジスタと、対応する２つ以上のＬＣと、をさらに備え、第１のＬＢＰＣは、第１のループに関連する条件付き分岐命令のＰＣを記憶するように動作し、第１のＬＣは、前記第１のループの反復のカウントを保持するように動作し、第２のＬＢＰＣは、第２のループに関連する条件付き分岐命令のＰＣを記憶するように動作し、第２のＬＣは、前記第２のループの反復のカウントを保持するように動作し、前記第１のループは、前記第２のループ内でネストされる、請求項１９に記載のプロセッサ。
【請求項２１】
前記制御回路は、前記第１のループの１つの実行の反復の回数を示す多ビット値と、前記第２のループの反復の回数を示す多ビット値とを、前記ＢＨＲに記憶するように動作する、請求項２０に記載のプロセッサ。
【請求項２２】
前記制御回路は、前記第１のループの１つの実行の反復の回数を示す多ビット値を前記ＢＨＲに記憶するように、そして前記第２のループの反復の回数の表示を前記ＢＨＲに記憶しないように動作する、請求項２０に記載のプロセッサ。
【請求項２３】
前記制御回路は、前記第２のループの反復の回数を示す多ビット値を前記ＢＨＲに記憶するように、そして前記第１のループの任意の実行の反復の回数の表示を前記ＢＨＲに記憶しないように動作する、請求項２０に記載のプロセッサ。
【請求項２４】
前記ＢＨＲは、前記ＢＨＲに直接にループ反復カウントを保持するために、前記ループに関連する前記条件付き分岐命令のおのおのの分岐成立評価に応じて、複数のビットを増分するように動作する、請求項１８に記載のプロセッサ。
【請求項２５】
複数のしきい値に応じて、ループ反復カウントを固定された多ビット値に対してマッピングするように動作するしきい値化ロジック、をさらに備える請求項１８に記載のプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般にプロセッサの分野に関し、特に、複数のビット(multiple bits)を有する分岐ヒストリレジスタ(branch history register)においてループ分岐(loop branches)を表す方法に関する。
【背景技術】
【０００２】
マイクロプロセッサは、多種多様なアプリケーションにおいて計算タスクを実行する。改善されたプロセッサ性能は、ソフトウェア変更を介してより高速なオペレーションおよび／または増大された機能を可能にするためにほとんどの場合に望ましい。ポータブル電子デバイスなどの一般的な埋込みアプリケーションにおいては、パワーを節約することも望ましい。
【０００３】
一般的な現代のプロセッサは、パイプライン化アーキテクチャを使用しており、ここでおのおのが複数の実行ステップを有するシーケンシャル命令が、実行においてオーバーラップされる。最大の性能のために、命令は、絶えずパイプラインを介して流れるべきである。命令がパイプラインにおいて機能停止する(stall)ようにさせるどのような状況も、性能に悪影響を及ぼす。命令がパイプラインからフラッシュされ、後で再フェッチされる必要がある場合、性能もパワー消費も影響を受けてしまう可能性がある。
【０００４】
一般にすべての現実の世界のプログラムは、条件付き分岐命令を含み、この条件付き分岐命令の実際の分岐動作(branching behavior)は、命令がパイプラインにおいて深く評価されるまで、一般には知られていない。分岐命令の実際の評価を待つことからもたらされる可能性がある機能停止を回避するために、一般的な現代のプロセッサは、何らかの形態の分岐予測を使用し、それにより条件付き分岐命令の分岐動作は、パイプラインにおいて早期に予測される。予測分岐評価(predicted branch evaluation)に基づいて、プロセッサは、推論的に(speculatively)フェッチし（プリフェッチし(prefetch)）、予測されたアドレス(predicted address)  −  分岐ターゲットアドレス（分岐が成立と予測される場合(if the branch is predicted taken)）かまたは分岐命令の後の次の順次アドレス（分岐が不成立と予測される場合(if the branch is predicted not taken)）  −  からの命令を実行する。実際の分岐動作が決定されるとき、分岐が誤って予測された場合には、推論的にフェッチされた命令は、パイプラインからフラッシュされる必要があり、新しい命令は正しい次のアドレスからフェッチされる。誤った分岐予測に応じて命令をフェッチすることは、プロセッサ性能およびパワー消費に悪影響を及ぼす。その結果、分岐予測の精度(accuracy)を改善することが望ましい。
【０００５】
知られている分岐予測技法は、静的予測と動的予測の両方を含んでいる。一部の分岐命令の可能性のある動作は、プログラマおよび／またはコンパイラによって静的に予測されることができる。一例は、エラー検査ルーチン(error checking routine)である。一般的なコードは適切に実行し、エラーは、まれである。したがって、「エラー上分岐(branch on error)」ファンクションをインプリメントする分岐命令は、非常に高いパーセンテージの時間に「不成立(not taken)」と評価することになる。そのような命令は、分岐条件の一般的に可能性のある結果の知識を用いて、プログラマまたはコンパイラによって設定される、ｏｐコード(op code)の中の静的分岐予測ビットを含むことができる。
【０００６】
動的予測は、一般に予測されている分岐命令および／または同じコードにおける他の分岐命令の分岐評価ヒストリ（そして一部の場合には分岐予測精度ヒストリ）に基づいている。実際のコードの広範囲にわたる解析は、最近の過去の分岐評価パターンが、将来の分岐命令の評価のよいインジケータとすることができることを指し示す。
【０００７】
図１に示される、知られている一形態の動的分岐予測は、過去のｎ個の分岐評価を記憶する分岐ヒストリレジスタ(Branch History Register)（ＢＨＲ）１００を利用する。簡単なインプリメンテーションにおいては、ＢＨＲ３０は、シフトレジスタを備える。一般的な最近の分岐評価結果は、レジスタの中の最も以前の過去の評価(the oldest past evaluation)が移動させられて、（例えば、１が利用されることを指し示し、０が利用されないことを指し示して）シフトされる。プロセッサは、各分岐命令についてローカルＢＨＲ１００を保持することができる。代わりに（または追加して）、ＢＨＲ１００は、時に当技術分野においてグローバルＢＨＲ、またはＧＨＲとして知られているすべての条件付き分岐命令についての最近の過去の評価を含むことができる。ここにおいて使用されるように、ＢＨＲは、ローカル分岐ヒストリレジスタと、グローバル分岐ヒストリレジスタの両方を意味する。
【０００８】
図１に示されるように、ＢＨＲ１００は、分岐予測器テーブル(Branch Predictor Table)（ＢＰＴ）１０２をインデックス付けすることができ、この分岐予測器テーブルは、この場合にもローカルまたはグローバルとすることができる。ＢＨＲ１００は、ＢＰＴ１０２に直接にインデックス付けすることができ、あるいはＢＰＴインデックスロジック１０４における分岐命令のプログラムカウンタ(Program Counter)（ＰＣ）など、他の情報と組み合わせられることができる。ＢＰＴインデックスロジック１０４に対する他の入力が、さらに利用されることもできる。ＢＰＴインデックスロジック１０４は、それらの入力を連結し（当技術分野においてｇｓｅｌｅｃｔとして知られている）、それらの入力のＸＯＲ（ｇｓｈａｒｅ）を行い、ハッシュ関数(hash function)を実行し、あるいは様々なやり方でそれらの入力を組み合わせ、または変換することができる。
【０００９】
一例として、ＢＰＴ１０２は、複数の飽和カウンタ(saturation counters)を備えることができ、これらの飽和カウンタのＭＳＢは、二項の分岐予測器としての役割を果たす。例えば、各テーブルエントリは、おのおのに以下の重み付けされた予測値(weighted prediction value)が割り当てられた４つの状態のうちの１つを仮定する(assumes)２ビットカウンタ、を備えることができる。
【００１０】
１１−強い予測の成立(Strongly predicted taken)
１０−弱い予測の成立(Weakly predicted taken)
０１−弱い予測の不成立(Weakly predicted not taken)
００−強い予測の不成立(Strongly predicted not taken)
カウンタは、対応する分岐命令が「成立(taken)」を評価するたびに、増分し(increments)、命令が「不成立(not taken)」を評価するたびに、減分する(decrements)。カウンタのＭＳＢは、二項分岐予測器であり、それは、基礎となる予測の強度または重みにかかわらず、成立の予定である、または不成立の予定である分岐を予測することになる。飽和カウンタは、頻度の低い分岐評価方向の予測エラーを低減させる。一方法を一貫して評価する分岐は、カウンタを飽和させることになる。頻度の低い評価は、他方、カウンタ値（および予測の強度）を変更することになるが、二項予測値を変更することにはならない。それ故に、頻度の低い評価は、１回だけ誤った予測を行うにすぎないことになり、２回は行わない。飽和カウンタのテーブルは、例示の例であるにすぎず、一般に、ＢＨＴは、様々な分岐予測メカニズムを含むテーブルにインデックス付けすることができる。
【００１１】
ＢＰＴ１０２において使用される分岐予測メカニズムにかかわらず、ＢＨＲ１００は、単独で、または分岐命令ＰＣなど、他の情報と組み合わせて、分岐予測を取得するためにＢＰＴ１０２にインデックス付けする。ＢＨＲ１００に先行した分岐評価を記憶することと、分岐予測における評価を使用することとにより、予測されている分岐命令は、過去の分岐動作（ローカルＢＨＲ１００の場合におけるそれ自体の過去の動作と、グローバルＢＨＲ１００の場合における他の分岐命令の動作）に相関させられる。この相関は、少なくとも高い反復コードの場合には、正確な分岐予測に対する鍵である。
【００１２】
図１は、ＢＨＲ１００に記憶されている分岐評価（−すなわち、実行パイプステージなどにおけるパイプラインの中の深くにおいて知られているだけの可能性がある条件付き分岐命令の実際の評価）を示すことに注意すべきである。これは、最終的な結果であるが、実際には、一般的な高性能プロセッサは、ＢＰＴ１０２からの予測された分岐評価をＢＨＲ１００に記憶し、予測が誤っていることが分かる場合には、誤った予測の回復オペレーションの一部分としてＢＨＲ１００を後で訂正する。この図面は、明確にするために、このインプリメンテーションの特徴を反映していない。
【００１３】
ＢＨＲ１００を使用した分岐予測器の効力を低減させる可能性のある一般的なコード構造は、ループである。ループは、ループを介するたびに増分されるインデックス変数が、ループ終了値に到達しているかどうかなどのループ終了条件をテストする条件付き分岐命令と共に終了する。そうでない場合には、実行は、別の反復についてのループの始め、および別のループ終了条件付き分岐評価へと分岐して戻る。
【００１４】
ループが、多数の反復を介して実行する場合、ループ終了分岐命令の「成立」後方分岐は、部分的に、または完全にＢＨＲ１００を飽和させる。ループの反復の回数が、ＢＨＲ１００の幅に等しいか、あるいは超過する場合には、ループの端で、ｎ−ビットＢＨＲは、ループ反復からもたらされる長い一連の分岐が成立する評価に対応し、そしてループが終了するときに単一の不成立分岐評価と共に終了する、単一のゼロ（不成立）によって追随される正確にｎ−１個の１（成立）を含むことになる。これは、（ローカルまたはグローバルのＢＨＲ１００のいずれかについての）先行する分岐評価とのすべての相関が失われるので、ＢＨＲ１００の効力を効果的に破壊する。この場合には、ＢＨＲ１００は、先行する分岐評価に対する分岐命令の相関を反映する分岐予測を含むエントリに対してではなく、（ＢＰＴインデックスロジック１０４に対する他の入力に応じて）与えられた分岐命令についての同じＢＰＴ１０２に対してマッピングする可能性が高いことになる。
【００１５】
さらに、飽和させられたＢＨＲ１００は、ＢＰＴ１０２において、エイリアシングを増大させる可能性がある。すなわち、ＢＨＲ１００が、ＢＰＴ１０２に直接にインデックス付けする場合、一般的な反復を用いてループに追随するすべての分岐命令は、同じＢＰＴ１０２エントリに対してマッピングすることになる。ＢＨＲ１００が、他の情報と組み合わせられる場合でさえ、エイリアシングの機会は、増大させられる。これは、ループに追随する分岐命令についてだけでなく、ＢＰＴ１０２においてそのエントリに対してエイリアスする分岐命令のすべてについて予測精度に悪影響を及ぼす。
【００１６】
ループが、ＢＨＲ１００の幅よりもより少ない反復を介して実行する場合、ＢＨＲ１００は、飽和させられず、何らかの先行する分岐評価ヒストリが、保持される。しかしながら、先行する分岐評価ヒストリを表すビットは、ループ終了分岐命令の非常に多くの「成立」結果により、ＢＨＲ１００の中で移動させられる。とりわけ、ループ反復の回数が、変化する場合には、これは、分岐予測に対して２つの悪影響を有する。第１に、分岐命令は、先行する分岐評価との同じ相関を取り込むためにＢＰＴ１０２においてずっと大きな数のエントリに対してマッピングすることになり、ＢＨＲ３０に影響を及ぼすループ終了分岐なしに必要とされることになるよりも大きなＢＰＴ１０２が、同じ数の分岐命令について同じ精度をサポートすることを必要とする。第２に、ＢＰＴ１０２における分岐予測器は、「トレーニングする」ためにより長くかかることになり、ＢＰＴ１０２が正確な分岐予測を提供し始める前に実行する必要のあるコードの量を増大させる。
【００１７】
本願の譲受人に譲渡され、参照によりここにおいて組み込まれている特許出願シリアル番号１１／０６６，５０８号は、ループ終了分岐命令についてＢＨＲ１００をアップデートすることを抑制することを提案している。これは、ＢＨＲ１００の飽和、または分岐予測精度に対する部分的な飽和の悪影響の一般的なものを解決する。しかしながら、それは、ループ動作と、後に続く分岐評価との間に存在する可能性のある相関を取り込み、活用することができない。
【００１８】
一般的なアプリケーションにおいて、分岐命令の評価は、先行するループの反復の回数に相関させられることができる。例えば、科学的プログラムは、ループの中のデータポイントを取り込み、ループに追随して、取り込まれたデータが解析される統計解析サブルーチンへと分岐することができる。しかしながら、ループが、少ないデータポイントを取り込むことと、小さなサンプルを与えることとを比較的少ない回数しか反復しない場合、統計解析は、信頼できない可能性があり、スキップされることができる。この場合には、統計解析サブルーチンへと分岐する条件付き命令の評価は、データ獲得ループの反復の回数に強く相関させられる。
【００１９】
別の例においては、アプリケーションは、リスト、トランザクションログ、ヒストリファイル、あるいは同様なデータ構造を介して検索するためにループ構造を使用することができる。検索パラメータにマッチングするアイテムがリストの中で頻繁に現れる場合、比較的少ないループ反復が、アイテムの所在を見出すために必要とされることになる。その結果、まれにしか現れないアイテムは、検索ループを介して多数の反復を必要とする可能性がある。後続の分岐命令の評価は、特定のアイテムがリストの中で現れる頻度に相関させられることができ、それ故にそのアイテムの所在を見出すために必要とされるループ反復の回数に相関させられる。
【００２０】
ループ終了分岐命令評価に応じてＢＨＲ１００のアップデートを抑制することは、ループ反復の回数と、後続の分岐命令の分岐動作との間のどのような相関も取り込むことができない。他方、ループ終了分岐命令の評価の完全なヒストリを保持することは、完全にまたは部分的にＢＨＲ１００を飽和させ、ループに先立つ分岐命令評価に対する相関をなくする。
【発明の開示】
【概要】
【００２１】
分岐がループ終了分岐(loop-ending branch)であることを指し示すプロパティなど、ループに関連する条件付き分岐命令のプロパティに応じて、ループの反復の回数のカウント(a count of the number of iterations of the loop)は、保持され、ループ反復カウントを示す多ビット値(multi-bit value)が、ＢＨＲに記憶される。一実施形態においては、多ビット値は、実際のループカウントを備えることができ、この場合には、ビットの数は可変である。別の実施形態においては、ビットの数は固定され（例えば、２）、ループ反復カウントは、しきい値(thresholds)と比較することにより多ビット値にマッピングされる(mapped)。別個の反復カウントは、ネストされたループ(nested loops)のために保持されることができ、ＢＨＲに記憶される多ビット値は、内側ループだけ、外側ループだけ、あるいは両方の、ループ反復カウントを指し示すことができる。
【００２２】
一実施形態は、分岐予測(branch prediction)の方法に関する。ループに関連する分岐命令のプロパティが、識別される(identified)。そのプロパティに応じて、その分岐命令に関連するループの反復の数を示す多ビット値が、ＢＨＲに記憶される。
【００２３】
別の実施形態は、プロセッサに関する。本プロセッサは、条件付き分岐命令の評価を予測するように動作する分岐予測器(branch predictor)と、分岐予測器からの予測に基づいて命令を推論的にフェッチし、そして実行するように動作する命令実行パイプライン(instruction execution pipeline)とを含む。本プロセッサはまた、条件付き分岐命令の評価を記憶するように動作するＢＨＲと、コードループの反復の回数をカウントするように動作するループカウンタと、を含む。本プロセッサは、条件付き分岐命令に関連するループの反復の回数を示す多ビット値をＢＨＲに記憶するように動作する制御回路を、さらに含んでいる。
【詳細な説明】
【００２４】
図２は、プロセッサ１０の機能ブロック図を示している。プロセッサ１０は、制御ロジック１４に応じて、命令実行パイプライン(instruction execution pipeline)１２の中で命令を実行する。一部の実施形態においては、パイプライン１２は、複数のパイプラインを有するスーパースカラ(superscalar)設計とすることができる。パイプライン１２は、パイプステージの形に構成された様々なレジスタまたはラッチ１６と、１つまたは複数の演算論理ユニット(Arithmetic Logic Unit)（ＡＬＵ）１８とを含む。汎用レジスタ(General Purpose Register)（ＧＰＲ）ファイル２０は、メモリ階層の最上部を備えるレジスタを提供する。
【００２５】
パイプライン１２は、メモリアドレスの変換および許可が、命令側変換索引バッファ(Instruction-side Translation Lookaside Buffer)（ＩＴＬＢ）２４によって管理されて、命令キャッシュ(Instruction cache)（Ｉ−キャッシュ）２２から命令をフェッチする。条件付き分岐命令がパイプライン１２において早期に復号化されるときに、分岐予測器２６は、分岐動作を予測し、命令プリフェッチユニット(instruction prefetch unit)２８に対してその予測を提供する。命令プリフェッチユニット２８は、「成立」分岐予測についてのパイプライン１２の中で計算される分岐ターゲットアドレスにおいて、あるいは「不成立」と予測される分岐についての次の順次アドレスにおいてＩ−キャッシュ２２から命令を推論的にフェッチする。いずれの場合にも、プリフェッチされた命令は、推論的実行のためにパイプライン１２にロードされる。
【００２６】
分岐予測器２６は、分岐ヒストリレジスタ(Branch History Register)（ＢＨＲ）３０と、分岐予測器テーブル(Branch Predictor Table)（ＢＰＴ）３２と、ＢＰＴインデックスロジック３４と、ＢＨＲアップデートロジック３６とを含む。分岐予測器２６は、１つまたは複数の最終分岐ＰＣレジスタ(Last Branch PC register)３８と、ＢＨＲアップデートロジック３６に対して入力を供給する１つまたは複数のループカウンタ３７とをさらに含むことができる。
【００２７】
データは、メモリアドレスの変換および許可が主要な変換索引バッファ（ＴＬＢ）４２によって管理されて、データキャッシュ（Ｄ−キャッシュ）４０からアクセスされる。ＴＬＢ４２は、専用データＴＬＢとすることができ、あるいは命令とデータの両方についてアドレスの変換および許可を管理する一体化されたＴＬＢを備えることができる。さらに、プロセッサ１０の様々な実施形態においては、Ｉ−キャッシュ２２とＤ−キャッシュ４０は、一体化され、あるいは統合されることができる。Ｉ−キャッシュ２２および／またはＤ−キャッシュ４０における失敗は、メモリインターフェース４６の制御の下でメイン（オフチップ）メモリ４４に対するアクセスを引き起こす。
【００２８】
プロセッサ１０は、様々な周辺デバイス５０、５２に対するアクセスを制御する入出力(Input/Output)（Ｉ／Ｏ）インターフェース４８を含むことができる。当業者は、プロセッサ１０の非常に多くの変形が可能であることを認識するであろう。例えば、プロセッサ１０は、Ｉキャッシュ２２とＤキャッシュ４０のいずれかまたは両方についての第２のレベルの（Ｌ２）キャッシュを含むことができる。さらに、プロセッサ１０に示される１つまたは複数の機能ブロックは、特定の実施形態から省略されることができる。
【００２９】
ループ反復の多ビット表示(Multi-Bit Indications of Loop Iterations)
１つまたは複数の実施形態によれば、分岐予測精度は、以前の分岐評価(previous branch evaluations)と以前のループの反復カウント(iteration count of previous loops)の両方に対して分岐評価を相関させることにより改善される。これは、ループ反復カウント（単数または複数）を示す多ビット値をＢＨＲ３０に記憶することにより達成される。比較的少ないビットに対して潜在的に大きなループ反復カウントをマッピングすることにより、ループについての特性情報は、ループ終了分岐が、分岐予測器２６における１つまたは複数のＢＨＲ３０を完全にまたは部分的に飽和させないようにしながら保存される。
【００３０】
このプロセスは、図３に流れ図として示される。命令が、フェッチされ、復号化される（ブロック５２）。命令が、条件付き分岐命令でない場合（ブロック５３）、それは、パイプラインの中で進み、プロセスは、次の命令をフェッチするために戻る（ブロック５２）。命令が、条件付き分岐命令である場合には（ブロック５３）、分岐がループ終了分岐であるかどうか（ブロック５４）についての決定が行われる。そうでない場合、分岐が（パイプラインの実行ステージなどにおいて）評価するときに、ＢＨＲ３０は、単一ビットを使用して分岐評価を、すなわち分岐命令が「成立」として評価されるか、あるいは「不成立」として評価されるかを記録するように、アップデートされる（ブロック５６）。次いで、実行は、それぞれ分岐ターゲットアドレスまたは次の順次アドレスにおいて続行される（ブロック６４）。分岐がループ終了分岐である場合には（ブロック５４）、ループ反復カウントが、増分される（ブロック５８）。ループが完了するときに（ブロック６０）、ループ反復の回数を示す多ビット値が、ＢＨＲ３０へと書き込まれる（ブロック６２）。次いでループ反復カウンタはクリアされ（ブロック６３）、実行は、次の順次アドレスにおいて続行される（ブロック６４）。
【００３１】
両方のクエリ（ブロック５４）（すなわちループ終了分岐命令として分岐命令を識別することと）ループ反復カウントを保持することと（ブロック５８）は、様々なやり方で達成されることができる。一実施形態においては、１つまたは複数のループカウンタ（ＬＣ）３７は、ループ終了分岐であるように決定される条件付き分岐命令が、「成立」を評価するときに、増分される。ＬＣ３７の値、または（ここにおいて、より十分に論じられるように）そこから導き出される値は、ループ終了分岐がループの出口を指し示す「不成立」を評価するときに、ＢＨＲ３０に書き込まれる。ＬＣ３７もまた、その時にクリアされる。
【００３２】
ループ終了分岐命令を識別すること(Identifying Loop-Ending Branch Instructions)
ループは、ループの終わりからループの始めへと後方に分岐することにより反復する。一実施形態によれば、分岐命令アドレスまたはＰＣよりも小さな分岐ターゲットアドレスを有するあらゆる条件付き分岐命令（すなわち、後方分岐）は、ループ終了分岐命令であるものと仮定される。ループ終了分岐を識別するこの方法は、簡潔性を提供する。図４に示されるように、分岐命令ＰＣは、分岐命令が実際にパイプラインの中で評価されるときにループ終了分岐検出ロジック(Loop-Ending Branch Detection logic)３５において分岐ターゲットアドレス（ＢＴＡ）と比較される。ＢＴＡ＜ＰＣである場合、ループカウンタ（ＬＣ）３７は、増分される。この実施形態は、分岐ターゲットアドレスが決定されるときにアドレス比較を必要とし、必ずしもすべての後方分岐がループ終了分岐であるとは限らないので、何らかの不正確さの影響を受ける可能性がある。
【００３３】
ループ終了分岐を検出する別の方法は、同じ分岐命令の反復される実行を認識することである。一実施形態においては、図４に示されるように、最終分岐ＰＣ(Last Branch PC)（ＬＢＰＣ）レジスタ３８は、実行される最終分岐命令のＰＣを記憶する。簡単なループの場合には、分岐命令のＰＣが、ループ終了分岐検出ロジック３５におけるＬＢＰＣ３８とマッチングする（すなわち、分岐命令が評価される最終分岐命令であった）場合、分岐命令は、ループ終了分岐命令であるものと仮定され、ＬＣ３７が、増分される。
【００３４】
ループ内の条件付き分岐命令を含むコードは、ループ終了分岐検出を複雑にしてしまう可能性がある。例えば、アレイまたはリンクされたリストを検索するための一般的なアルゴリズムは、ループを作る。ループ内の分岐は、マッチングについて検査し、マッチングが見出される場合にループを早期に抜けるが、ループ終了分岐は、そのアレイまたはリンクされたリストの終わりについて検査する。この場合に、単一ＬＢＰＣ３８は、それが２つの分岐ＰＣによって交互に上書きされることになるので、ループ終了分岐を検出することができない。それに応じて、一実施形態においては、２つ以上のＬＢＰＣレジスタ３８が、（図４に示されるように）提供されることができ、正常に評価された分岐命令のＰＣが、対応するＬＢＰＣレジスタ（ＬＢＰＣ０、ＬＢＰＣ１、...ＬＢＰＣＭ）３８に記憶される。これにより、ループ内に他の条件付き分岐が存在する場合でさえ、ループ終了分岐の検出が可能になる。
【００３５】
ループ終了分岐命令は、コンパイラまたはアセンブラによって静的にマーク付けされることもできる。一実施形態においては、コンパイラは、ループ終了分岐、例えば、「ＢＲＬＰ」のために使用されるだけの特定のタイプの分岐命令を生成する。ＢＲＬＰ命令は、認識され、ＬＣ３７は、ＢＲＬＰ命令が実行パイプステージにおいて成立と評価するたびに、増分される。別の実施形態においては、コンパイラまたはアセンブラは、命令ｏｐコード内に１つまたは複数のあらかじめ定義されたビットを設定することなどにより、分岐命令にループ終了分岐表示(loop-ending branch indication)を埋め込むことができる。ループ終了分岐ビットは、検出され、ＬＣ３７は、分岐命令が、実行パイプステージにおいて成立と評価するときに、増分される。一般に、ループ終了インジケータ(Loop-Ending Indicator)は、ループ終了分岐検出ロジック３５に対して提供されることができる。ループ終了分岐の静的識別は、ループ終了識別ファンクションをコンパイラまたはアセンブラへと移動させることにより、ハードウェアと計算の複雑さを低減させる。
【００３６】
ループ反復の回数のインジケータを生成することおよび記憶すること(Generating and Storing an Indicator of the Number of Loop Iterations)
（内側ループまたは外側ループについて）ループ終了分岐命令を識別するために使用される技法に関係なく、１つまたは複数の実施形態によれば、ループが反復する回数の表示は、ループ反復の回数と、後続の条件付き分岐命令評価との間の任意の相関を活用するために、ＢＨＲ３０に記憶される。
【００３７】
一実施形態においては、ループ反復の実際のカウントは、ＢＨＲ３０に記憶される。すなわち、例えば、ＬＣ３７からの多ビットカウントは、ＢＨＲ３０へとシフトされ、ＢＨＲ３０のＭＳＢへと先行する分岐評価を移動させる。非常に大きなループでは、このカウントは、ｎ個のループ反復についてｌｏｇ２（ｎ）ビットを必要とすることになり、先行する分岐評価の対応する数を移動させる。しかしながら、大きなループ反復カウントの場合でさえも、２進表現は、先行技術の分岐ヒストリレジスタ（すなわち、単一のゼロによって追随されるｎ−１個のもの）に記憶されるループ終了分岐動作についてのかなりの圧縮である。一実施形態においては、反復カウントは、ＬＣ３７に蓄積され、ＢＨＲ３０へとシフトされる。別の実施形態（図示されず）においては、ＢＨＲ３０の少なくとも下位のｋビットが、デュアルモードシフトレジスタ／カウンタとしてインプリメントされることができ、ループ反復カウントは、（先行するＢＨＲ３０の内容が、カウントが大きくなるにつれて左にシフトして）ＢＨＲ３０において直接に増分されることができる。
【００３８】
別の実施形態においては、ループ反復の回数の固定された多ビット表示が、ＢＨＲ３０に記憶される。例えば、２ビットが、以下の意味をもつように、ループ反復の回数の表示を記録するために割り付けられることができる。
【００３９】
１１−ループ反復の非常に大きな回数(Very large number of loop iterations)
１０−ループ反復の大きな回数(Large number of loop iterations)
０１−ループ反復の適度な回数(Moderate number of loop iterations)
００−ループ反復の小さな回数(Small number of loop iterations)
この例においては、（小さいものと適度なものとの間（００−＞０１）と、適度なものと大きなものとの間（０１−＞１０）と、大きなものと非常に大きなものとの間（１０−＞１１）の）３つのしきい値は、しきい値化ロジック(Thresholding logic)３９によって指し示されるように、実際のループ反復カウントを２ビット表現に対してマッピングするために使用される。一実施形態においては、しきい値は、一般的なループサイズが一般に知られている場合の、ある種の埋込みアプリケーションについてなど、与えられたプロセッサインプリメンテーションについて固定されることができる。別の実施形態においては、マッピングは、しきい値が、ＧＰＲ２０、メモリ４４におけるテーブルなどから読み取られて、スケーラブルとすることができる。一般的なアプリケーションにおいては、ループ反復の回数の固定された多ビット表示は、同時にループ終了分岐によってＢＨＲ３０から移動させられた先行する分岐評価の回数を制限しながら、分岐評価動作との意味のある相関を可能とする、ループ反復カウントの十分な表示を提供することができる。
【００４０】
もちろん、実際のループ反復カウントは、ＢＨＲ３０におけるループ反復カウント精度と分岐評価変位(branch evaluation displacement)との間の望ましい、あるいは必要とされるバランスを達成するために、しきい値の対応する数を伴う任意の固定数のビット、例えば３ビットと７個のしきい値、４ビットと１５個のしきい値などに対してマッピングされることができる。
【００４１】
ネストされるループ(Nested Loops)
ループは、１つまたは複数のネストされた、あるいは内側のループを含むことができる。したがって、一実施形態においては、複数のＬＣカウンタ（ＬＣ０、ＬＣ１、...ＬＣM）３７が提供され、これらは、ＬＢＰＣ３８レジスタの数に対応する可能性がある。ＬＣ３７は、ネストされたループの反復カウントを保持するために、成立評価と、関連するＬＢＰＣＭ３８とのマッチングのすぐ後に増分される。
【００４２】
内側ループが終了するたびに、内側ループの反復の回数の多ビット表示を記憶することにより、ＢＨＲ３０は、外側ループが、比較的少ない回数、反復する時までに、部分的に、あるいは完全に飽和するようになる可能性がある。したがって、一実施形態においては、ひとたびループが内側ループであると決定された後には、内側ループの初期実行の後の後続の反復カウントは、ＢＨＲ３０をアップデートしないように抑制される可能性がある。この実施形態においては、外側ループが終了する時までに、ＢＨＲ３０は、外側ループの第１の反復だけについての内側ループの反復カウントの表示と、外側ループの反復カウントの表示とを含むことになる。
【００４３】
別の実施形態においては、内側ループ反復カウントは、外側ループ反復カウントの表示を用いて、ＢＨＲ３０におけるその値を上書きすることにより、捨てられることができる。これは、後続の分岐評価の、外側ループの反復カウントとの相関を可能としながら、最大数の先行する分岐評価をＢＨＲ３０に保存する。
【００４４】
別の実施形態においては、外側ループ反復カウントは、外側ループが終了するときにＢＨＲ３０のアップデートを抑制することにより、捨てられることができる。これは、この場合にも、後続の分岐評価の内側ループの反復カウントとの相関を可能にしながら、最大数の先行する分岐評価をＢＨＲ３０に保存し、これは、一部のアプリケーションにおいては後続の分岐評価について、より予測的なものとすることができる。
【００４５】
条件付き分岐命令は、例えば分岐命令アドレスまたはＰＣと、命令タイプと、ｏｐコードにおけるインジケータビットの存在または不在(presence, vel non)とを含めて一般的なプロパティを有する。ここにおいて使用されるように、分岐オペレーションのプロパティ、および／または分岐に関するプログラムのプロパティは、分岐命令のプロパティと考えられる。例えば、分岐命令ＰＣが、１つまたは複数のＬＢＰＣレジスタ３８の内容にマッチングするかどうかと、分岐ターゲットアドレスが、分岐命令ＰＣに対して前方にあるか、または後方にあるかは、分岐命令のプロパティである。
【００４６】
本開示は、その特定の特徴、態様、および実施形態に関して、ここに説明されてきたが、多くの変形、修正、および他の実施形態が、本開示の広い範囲内において可能であるということは明らかであり、したがって、すべての変形、修正、および実施形態は、本開示の範囲内にあるものと見なされるべきである。それ故に、本実施形態は、すべての点において例示的であって限定的ではないとして解釈されるべきであり、添付の特許請求の範囲の意味する範囲および均等の範囲の中に入るすべての変更は、そこに包含されるべきであるように意図される。
【図面の簡単な説明】
【００４７】
【図１】先行技術の分岐予測器回路の機能ブロック図である。
【図２】プロセッサの機能ブロック図である。
【図３】分岐命令を実行する方法の流れ図である。
【図４】１つまたは複数の最終分岐ＰＣレジスタおよびループカウンタを含む分岐予測器回路の機能ブロック図である。
【図１】
0005384323.tif 000002
【図２】
0005384323.tif 000003
【図３】
0005384323.tif 000004
【図４】
0005384323.tif 000005