(57)【要約】【解決手段】マイクロプロセッサは、２つの分岐履歴テーブルを含んでおり、分岐ターゲットキャッシュにおいてヒットである分岐命令を予測するために分岐履歴テーブルのうちの第１の１つを使用し、分岐ターゲットキャッシュにおいてミスである分岐命令を予測するために分岐履歴テーブルのうちの第２の１つを使用するように構成される。また、第１の分岐履歴テーブルは、分岐ターゲットキャッシュのものと一致するアクセス速度を持つように構成される。これによって、マイクロプロセッサの命令パイプラインにおいて早期に起こる予測情報が、分岐ターゲットキャッシュヒット検知に対してタイムリーに利用可能になる。第２の分岐履歴テーブルは、例えば命令パイプラインの命令復号ステージにおいて、分岐ターゲットキャッシュミスを分岐命令として認識することに関連する予測情報をタイムリーに提供するために必要なだけ高速である必要がある。【選択図】      図２
2008542917.tif 000002
【特許請求の範囲】
【請求項１】
採用又は不採用として命令パイプラインへ取得された予測分岐命令に基づいて、マイクロプロセッサの命令パイプラインのため、命令取得を指示するように構成された分岐予測回路を備えるマイクロプロセッサであって、
前記分岐予測回路は、
既知の分岐命令のための分岐ターゲット情報を格納するように構成された分岐ターゲットキャッシュと、
第１の分岐予測情報を格納するように構成された第１の分岐履歴テーブルと、
第２の分岐予測情報を格納するように構成された第２の分岐履歴テーブルと、
分岐ターゲットキャッシュヒットである分岐命令のための前記第１の分岐予測情報に従って、及び、分岐ターゲットキャッシュミスである分岐命令のための前記第２の分岐予測情報に従って、分岐命令を、採用されたもの又は採用されないものとして予測するように構成された分岐制御ロジックと
を備えるマイクロプロセッサ。
【請求項２】
命令パイプラインを備えたマイクロプロセッサであって、前記命令パイプラインは、
取得する命令を、前記命令パイプラインへキャッシュするように構成された命令キャッシュと、
既知の分岐情報のための分岐ターゲット情報を格納するように構成された分岐ターゲットキャッシュと、
第１の分岐予測情報を格納するように構成された第１の分岐履歴テーブルと、
第２の分岐予測情報を格納するように構成された第２の分岐履歴テーブルと、
分岐ターゲットキャッシュヒットである分岐命令のための前記第１の分岐予測情報に従って、及び、分岐ターゲットキャッシュミスである分岐命令のための前記第２の分岐予測情報に従って、分岐命令を、採用されたもの又は採用されないものとして予測するように構成された分岐制御ロジックと
を含むか、又は、関連しているマイクロプロセッサ。
【請求項３】
前記第１の分岐履歴テーブルは、前記分岐ターゲットキャッシュのものと一致するアクセス速度を持つように構成され、前記第２の分岐履歴テーブルは、前記命令キャッシュのものと一致するアクセス速度を持つように構成された請求項２に記載のマイクロプロセッサ。
【請求項４】
前記第１の分岐履歴テーブルと前記分岐ターゲットキャッシュとは、前記命令パイプラインのＭ個のサイクルにおいてアクセス可能であるように構成され、前記第２の分岐履歴テーブルは、前記命令パイプラインのＮ個のサイクルにおいてアクセス可能であるように構成され、Ｍ及びＮは第１及び第２の数であり、ＭはＮよりも小さい請求項２に記載のマイクロプロセッサ。
【請求項５】
前記第１の分岐履歴テーブルは、前記第２の分岐履歴テーブルよりも少ない数の分岐予測変量を備え、もって、前記第１の分岐履歴テーブル内の分岐予測変量にアクセスすることが、前記第２の分岐履歴テーブル内の分岐予測変量にアクセスすることもよりも時間がかからないようにする請求項２に記載のマイクロプロセッサ。
【請求項６】
前記マイクロプロセッサは、前記第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットに対する初期予測を行い、前記第２の分岐予測情報に従って、前記分岐ターゲットキャッシュヒットに対する対応する次の予測を行うように構成された請求項２に記載のマイクロプロセッサ。
【請求項７】
前記マイクロプロセッサは、前記初期予測に従って命令取得を指示するように、かつ、前記対応する次の予測に従って命令取得を条件付で再指示するように構成された請求項６に記載のマイクロプロセッサ。
【請求項８】
前記対応する次の予測が、与えられた初期予測と一致しないのであれば、前記マイクロプロセッサは、前記与えられた初期予測に対して、命令取得を再指示することによって、条件付で命令取得を再指示するように構成された請求項７に記載のマイクロプロセッサ。
【請求項９】
前記マイクロプロセッサは、分岐ターゲットキャッシュヒット及びミスのためになされた分岐予測の解決に応じて、前記第２の分岐予測情報を更新するように構成され、これによって、前記第２の分岐予測情報が、分岐ターゲットキャッシュヒットとミスとの両方について、分岐履歴を反映することができる請求項２に記載のマイクロプロセッサ。
【請求項１０】
前記マイクロプロセッサは、前記第１の分岐予測情報を、前記第２の分岐予測情報に応じて更新するように構成された請求項９に記載のマイクロプロセッサ。
【請求項１１】
前記マイクロプロセッサは、分岐ターゲットキャッシュミスのためになされた分岐予測の解決に応じて、前記第２の分岐予測情報を更新するように構成され、分岐ターゲットキャッシュヒットのためになされた分岐予測の解決に応じて、前記第１の分岐予測情報を更新するように構成された請求項２に記載のマイクロプロセッサ。
【請求項１２】
前記マイクロプロセッサは、命令アドレスを前記命令パイプラインに取得することに応じて、前記第１及び第２の分岐履歴テーブルへのアクセスを開始するように構成され、更に、前記分岐ターゲットキャッシュにおいて、前記命令アドレスがヒットであることを検知することに応じて、前記第２の分岐履歴テーブルへのアクセスを終了し、もって、分岐ターゲットキャッシュヒットである分岐命令に対して、前記第２の分岐履歴テーブルへのフルアクセスが回避されるように構成された請求項２に記載のマイクロプロセッサ。
【請求項１３】
前記分岐ターゲットキャッシュは、分岐ターゲットアドレスキャッシュ又は分岐ターゲット命令キャッシュのうちの１つを含む請求項２に記載のマイクロプロセッサ。
【請求項１４】
マイクロプロセッサにおける分岐予測の方法であって、
既知の分岐命令を識別する分岐ターゲットキャッシュを保持することと、
前記マイクロプロセッサの命令パイプラインへ取得された分岐命令が、分岐ターゲットキャッシュヒットであるか、又は、分岐ターゲットキャッシュミスであるかを判定することと、
第１の分岐履歴テーブルに格納された第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットである分岐命令が、採用されるか、又は、採用されないかを予測し、第２の分岐履歴テーブルに格納された第２の分岐予測情報に従って、分岐ターゲットキャッシュミスである分岐命令が、採用されるか、又は、採用されないかを予測することと
を含む方法。
【請求項１５】
前記第１の分岐履歴テーブルを、前記分岐ターゲットキャッシュのものと一致するアクセス速度を持つように構成することと、
前記第２の分岐履歴テーブルを、命令が前記命令パイプラインへと取得される前記命令キャッシュのものと一致するアクセス速度を持つように構成することと
を更に含む請求項１４に記載の方法。
【請求項１６】
前記第１の分岐履歴テーブルと前記分岐ターゲットキャッシュとが、前記命令パイプラインのＭ個のサイクルにおいてアクセスできるように構成することと、
前記第２の分岐履歴テーブルが、前記命令パイプラインのＮ個のサイクルにおいてアクセスできるように構成することとを更に含み、
Ｍ及びＮは第１及び第２の数であり、ＭはＮよりも小さい請求項１４に記載の方法。
【請求項１７】
前記第１の分岐履歴テーブルが、前記第２の分岐履歴テーブルよりも少ない数の分岐予測変量を格納するように構成することを更に含み、もって、前記第１の分岐履歴テーブル内の分岐予測変量にアクセスすることが、前記第２の分岐履歴テーブル内の分岐予測変量にアクセスすることもよりも時間がかからないようにする請求項１４に記載の方法。
【請求項１８】
第１の分岐履歴テーブルに格納された第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットである分岐命令が、採用されるか、又は、採用されないかを予測することは、
前記第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットに対する初期予測を行うことと、
前記第２の分岐予測情報に従って、前記分岐ターゲットキャッシュヒットに対する対応する次の予測を行うことと
を含む請求項１４に記載の方法。
【請求項１９】
前記初期予測に従って命令取得を指示することと、
前記対応する次の予測に従って命令取得を条件付で再指示することと
を更に含む請求項１８に記載の方法。
【請求項２０】
前記対応する次の予測に従って命令取得を条件付で再指示することは、前記対応する次の予測が、与えられた初期予測と一致しないのであれば、前記与えられた初期予測に対して、命令取得を再指示することを含む請求項１９に記載の方法。
【請求項２１】
分岐ターゲットキャッシュヒット及びミスのためになされた分岐予測の解決に応じて、前記第２の分岐予測情報を更新し、これによって、前記第２の分岐予測情報が、分岐ターゲットキャッシュヒットとミスとの両方について、分岐履歴を反映できるようにしたことを含む請求項１４に記載の方法。
【請求項２２】
前記第１の分岐予測情報を、前記第２の分岐予測情報に応じて更新することを更に含む請求項２１に記載の方法。
【請求項２３】
分岐ターゲットキャッシュミスのためになされた分岐予測の解決に応じて、前記第２の分岐予測情報を更新することと、
分岐ターゲットキャッシュヒットのためになされた分岐予測の解決に応じて、前記第１の分岐予測情報を更新することと
を更に含む請求項１４に記載の方法。
【請求項２４】
命令アドレスを前記命令パイプラインに取得することに応じて、前記第１及び第２の分岐履歴テーブルへのアクセスを開始することと、
前記分岐ターゲットキャッシュにおいて、前記命令アドレスがヒットであることを検知することに応じて、前記第２の分岐履歴テーブルへのアクセスを終了し、もって、分岐ターゲットキャッシュヒットである分岐命令に対して、前記第２の分岐履歴テーブルへのフルアクセスが回避されるようにしたことと
を更に含む請求項１４に記載の方法。
【請求項２５】
前記分岐ターゲットキャッシュを、分岐ターゲットアドレスキャッシュ及び分岐ターゲット命令キャッシュのうちの１つとして構成することを更に含む請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、マイクロプロセッサに関し、特に、分岐予測マイクロプロセッサに関する。
【背景技術】
【０００２】
パイプラインマイクロプロセッサは、条件付分岐命令が採用されるべきかを判定するために待機している間、命令パイプラインがストールすることを回避するために、一般に分岐予測を用いる。分岐予測メカニズムによって、そのようなマイクロプロセッサは、分岐条件を実際に評価する前に、条件付分岐命令を採用すべきかを「推測する」ことができる。
【０００３】
一般的な分岐予測方法は、分岐予測情報を与える多くの飽和カウンタやその他のトラッキングインジケータを含む分岐履歴テーブルを保持することに依存する。一例として、２ビット飽和カウンタは、最大値１１までカウントアップし、最小値００までカウントダウンする。ここで値１１は、強く採用されることを表し、１０は、弱く採用されることを表し、０１は、弱く採用されないことを表し、００は、強く採用されないことを表す。そのようなカウンタは、過去の分岐挙動を追跡するマイクロプロセッサのようなランタイムヒューリスティックスに、動的に基づいて保持されうる。
【０００４】
分岐予測によって得られた実際のパフォーマンスゲインは、分岐予測精度に依存するので、異なる命令アドレス範囲のために異なるカウンタが使用されうる。これによって、各カウンタのインジケータ状態が、より狭い命令アドレス範囲内の分岐命令の採用／不採用挙動にも良好に反映できるようになる。この方法による予測精度の改善は、比較的大きな数からなるカウンタを用いることに至る。なぜなら、各カウンタは、比較的小さな命令アドレス範囲に対する分岐予測変量しか与えないからである。従って、分岐履歴テーブルは比較的大きくなりうる。また、それらへインデクスすることは、含まれている比較的狭い命令アドレス範囲を識別するために、かなりの数の命令アドレスビットを復号する必要がある。
【０００５】
これに伴う遅延は、分岐ターゲットアドレスキャッシュ（又は、同様に、分岐ターゲット命令キャッシュ）を使用することによって更なる分岐予測パフォーマンスゲインを実現する能力を制限する。そのような分岐ターゲットキャッシュは、例えば、マイクロプロセッサによって以前に取得され、復号され、分岐命令として識別されたような分岐命令のように、以前に認識された分岐命令の命令アドレスを保持する。そして、分岐命令は、新たに取得された各命令の命令アドレスを分岐ターゲットキャッシュ内容と比較することによって、復号前に検知される。分岐ターゲットキャッシュ「ヒット」は、命令アドレスが、以前に認識された分岐に相当することを示す。一方、分岐ターゲットキャッシュ「ミス」は、この命令が、以前に認識された分岐ではないことを示す。これは、命令が分岐命令であるかを判定する命令復号ステージまで、マイクロプロセッサが待機しなければならないことを意味する。
【０００６】
従って、分岐ターゲットキャッシュヒットである分岐命令は、命令復号を待つことなく採用又は不採用として予測されうる。しかしながら、分岐履歴テーブルを用いてそのような予測をする能力は、分岐ターゲットキャッシュヒットを検知するために要するのと同じ長さの時間において利用可能なテーブル情報に依存する。大きな分岐履歴テーブルは、一般に、分岐ターゲットキャッシュヒットの予測に使用できるほど十分速くアクセスできない。
【０００７】
タイムリーな予測情報を利用できないことによって、マイクロプロセッサは、別のアプローチを適用しなければならなくなる。１つの代替アプローチでは、分岐ターゲットキャッシュヒットである分岐命令が、常に採用されるものと仮定される。すなわち、「予測」が採用されるとして固定される。そのようなアプローチは、かなりの回数、誤った予測に導きうる。別の代替例は、分岐履歴テーブルをスピードアップすることである。これは、一般に、分岐履歴テーブルを、命令パイプラインの取得ステージにおいて早期にアクセス可能となるほど十分小さくすることによって行われ、これによって、命令を復号する前に予測情報を利用できるようになる。しかしながら、このように分岐履歴テーブルを小さくすることは、一般に、予測精度を落とす。なぜなら、分岐を予測するために、広範囲の命令アドレスにわたって同じ予測変量が使用されるからである。
【発明の開示】
【０００８】
１又は複数の実施形態では、マイクロプロセッサが、分岐ターゲットキャッシュヒットである分岐命令を予測するために第１の分岐履歴テーブルを用い、分岐ターゲットキャッシュミスである分岐命令を予測するために第２の分岐履歴テーブルを用いる。第１の分岐履歴テーブルは、分岐ターゲットキャッシュのものと一致するアクセス速度を持つように構成されている。これによって、予測情報が、分岐ターゲットキャッシュヒット及びミスが検出されるマイクロプロセッサの命令パイプラインにおいて、早期に利用可能となる。その予測情報は、パイプラインにおける後半まで必要ではないので、第２の分岐履歴テーブルは、第１の分岐履歴テーブルほど高速である必要はない。この事実によって、第２の分岐履歴テーブルのサイズ及び精度を設定する際において、かなりの柔軟性を許容する。
【０００９】
マイクロプロセッサは、採用又は不採用として命令パイプラインへ取得された予測分岐命令に基づいて、マイクロプロセッサの命令パイプラインのため、命令キャッシュからの命令取得を指示するように構成された分岐予測回路を含む。この分岐予測回路の１つの実施形態は、既知の分岐命令のための分岐ターゲット情報を格納するように構成された分岐ターゲットキャッシュと、第１の分岐予測情報を格納するように構成された第１の分岐履歴テーブルと、第２の分岐予測情報を格納するように構成された第２の分岐履歴テーブルと、分岐制御ロジックとを備える。この分岐制御ロジックは、分岐ターゲットキャッシュヒットである分岐命令のための第１の分岐予測情報に従って、及び、分岐ターゲットキャッシュミスである分岐命令のための第２の分岐予測情報に従って、分岐命令を、採用又は採用として予測するように構成される。
【００１０】
１つの実施形態では、第１の分岐履歴テーブルは、分岐ターゲットキャッシュのものと一致するアクセス速度を持つように構成されている。そして、第２の分岐履歴テーブルは、命令キャッシュのものと一致するアクセス速度を持つように構成されている。より一般的には、第１の分岐履歴テーブルは、その分岐予測情報が、例えば、命令パイプラインの取得ステージにおいて早期に、分岐ターゲットキャッシュヒットの検出と連携して利用可能となるように構成される。一方、第２の分岐履歴テーブルは、その分岐予測情報が、例えば、命令パイプラインの復号ステージの後半において、分岐命令を認識することと連携して利用可能となるように構成される。
【００１１】
上記マイクロプロセッサは、第１の分岐履歴テーブルを用いて分岐ターゲットキャッシュヒットを予測し、かつ、第２の分岐履歴テーブルを用いて分岐ターゲットキャッシュミスを予測する方法の１又は複数のバリエーションを具体化する。例えば、マイクロプロセッサは、第１の分岐予測情報に従って分岐ターゲットキャッシュヒットの初期予測を行うように構成され、かつ、第２の分岐予測情報に従って分岐ターゲットキャッシュヒットの対応する次の予測を行うように構成される。従って、マイクロプロセッサは、初期予測に従って命令取得を指示し、かつ、対応する次の予測に従って、命令取得を条件付で再指示するように構成される。すなわち、第２の分岐履歴テーブルは、第１の分岐履歴テーブルよりも大きく（かつより正確に）なりうるので、マイクロプロセッサは、対応する次の予測が、与えられた初期予測と一致しないのであれば、命令取得を再指示する。
【００１２】
更に、マイクロプロセッサは、分岐ターゲットキャッシュヒット及びミスのためになされた分岐予測の解決に応じて、第２の分岐予測情報を更新するように構成されうる。これによって、第２の分岐予測情報が、分岐ターゲットキャッシュヒットとミスとの両方について、分岐履歴を反映することができる。このアプローチによって、マイクロプロセッサは、第１の分岐予測情報を、第２の分岐予測情報に応じて更新するように構成されうる。すなわち、第２の分岐履歴テーブルは、実行された全ての分岐命令の分岐履歴を、それらが分岐ターゲットキャッシュ内で表わされていようといまいと反映するように作成される。
【００１３】
あるいは、マイクロプロセッサは、分岐ターゲットキャッシュミスのためになされた分岐予測の解決に応じて、第２の分岐予測情報を更新するように構成され、かつ、分岐ターゲットキャッシュヒットのためになされた分岐予測の解決に応じて、第１の分岐予測情報を更新するように構成される。このアプローチを用いて、第１の分岐履歴テーブルは、キャッシュ内に表わされた分岐命令の分岐履歴を反映し、第２の分岐履歴テーブルは、キャッシュ内に表わされていない分岐命令の分岐履歴を反映する。
【発明を実施するための最良の形態】
【００１４】
限定しない例によって、図１は、マイクパイプラインＲＩＳＣマイクロプロセッサを備えるマイクロプロセッサ１０を例示する。例示した実施形態では、マイクロプロセッサ１０は、入出力（Ｉ／Ｏ）回路１２、命令キャッシュ１４、データキャッシュ１６、及び命令パイプライン１８を含む。命令パイプライン１８は、フロントエンド回路２０、実行ユニット２２、及び完了ユニット２４を含む。
【００１５】
動作中、フロントエンド回路２０は、内蔵したレベル１（Ｌ１）キャッシュでありうる命令キャッシュ１４から命令を取得する。これら命令は、プログラム分岐やジャンプを含む定められたコンピュータプログラムフローに従って取得される。マイクロプロセッサ１０は、条件付分岐が採用されるか否かを予測するために分岐予測を用いる。これによって、条件付分岐命令に遭遇した場合、一般に、その命令取得動作を中断しなくてよい。
【００１６】
取得された命令は、復号され、実行ユニット２２へ発行される。実行ユニット２２は、スーパースカラアーキテクチャに従って実施することができる。実行ユニット２２は、この発行された命令を実行する。また、完了ユニット２４が、この実行された命令を退かせる。完了ユニット２４は、実行結果を１又は複数のターゲットファイルレジスタに格納するライトバックメカニズムを備える。限定しない例によって、実行ユニット２２は、整数ユニット２６、ロード／ストアユニット２８、及び、浮動小数点ユニット３０を含む。従って、フロントエンド回路２０は、整数命令を整数ユニット２６へ、メモリアクセス情報をロード／ストアユニット２８へディスパッチする等を行うように構成される。
【００１７】
当業者であれば、実行ユニット２２内の各サブニット自身が、多くの連続的なパイプラインステージを備えていることと、実行ユニット２２内に実装された特定のサブニットが変わりうることを認識するだろう。確かに、当業者であれば、マイクロプロセッサ１０のアーキテクチャは、本明細書に記載の分岐予測方法及び装置から逸脱することなく大幅に変わりうることを認識するだろう。
【００１８】
マイクロプロセッサ１０の１つの実施形態に従った分岐予測のより詳細な処理に移ると、フロントエンド回路２０は、連続取得ステージ３２，３２（この図ではＦＥ１，ＦＥ２とも示される）と、連続復号ステージ３６，３８（この図ではＤＣ１，ＤＣ２とも示される）と、発行／ディスパッチステージ４０（この図ではＩＳとも示される）とを含む多くのパイプラインステージを備える。これらフロントエンドパイプラインステージのうちの１又は複数は、分岐制御ロジック４４、分岐ターゲットキャッシュ４６、第１の分岐履歴テーブル４８（この図ではＢＨＴ１とも示される）、及び、第２の分岐履歴テーブル５０（この図ではＢＨＴ２とも示される）を備える分岐予測回路４２に関連付けられる。
【００１９】
取得ステージ３２は、命令パイプライン１８へ取得される次の命令の命令アドレスを表わすアドレスカウンタを保持するように構成される。取得ステージ３２に保持された値は、命令キャッシュ１４に提供される。これによって、命令キャッシュ１４は、復号ステージ３６による復号のために、指定されたアドレスに保持される実際のプログラム命令を出力する。取得ステージ３２に保持された値は、一般に、各クロックサイクルにおいて更新される。連続取得の場合、この値を更新することは、現在の命令シーケンス内の次のプログラム命令へのポイントへ値をインクリメントすることを含む。しかしながら、もしも取得された最後の命令が、採用される条件付分岐命令である場合、連続取得は適切ではない。むしろ、命令取得は、分岐命令のターゲットアドレスへと転送示されるべきである。
【００２０】
その目的のため、分岐予測回路４２は、与えられた条件付分岐命令が採用されるか否かを予測するために分岐履歴情報を用いる。そのような分岐履歴情報は、１又は複数のヒューリスティックスに従って生成されうる。限定しない例によれば、この分岐予測情報は、最後のＲ個の分岐のうちのいくつが採用され、又は、採用されないかをモニタすることに基づく。そのような情報は、例えば、順方向分岐及び逆方向分岐のために個別の履歴情報を保持することによって、及び／又は、プログラム命令アドレス空間全体の部分領域のための分岐履歴予測変量を保持することによってリファインされる。これによって、各分岐予測変量は、比較的小さな命令アドレス範囲の採用／不採用挙動を反映することができる。各予測変量を、小さな範囲の命令アドレスに限定することによって、より正確な予測変量を提供することができる。なぜなら、各予測変量によって表される分岐の数が低減され、恐らくは、より小さな数の分岐の具体的な挙動がより反映されるからである。
【００２１】
しかしながら、より多くの予測変量を保持することは、一般に、より大きな分岐履歴テーブルを必要とする。これは、テーブルがアクセスされるレートを低減する。アクセス速度がより遅くなることは、命令パイプライン１８内の復号ステップまで認識されない（すなわち、予測されない）分岐命令に関しては問題ではない。しかしながら、分岐ターゲットキャッシュ４６によって、命令パイプライン１８において分岐命令として早期に認識される分岐命令には問題となる。分岐ターゲットキャッシュ４６は、マイクロプロセッサ１０に、復号されている命令に先立って、新たに取得された命令が分岐命令であるか否かを認識する能力を与える。
【００２２】
限定しない理由によれば、分岐ターゲットキャッシュ４６は、分岐ターゲットアドレスキャッシュ（ＢＴＡＣ（Branch Target Address Cache）として知られている）、又は、分岐ターゲット命令キャッシュ（ＢＴＩＣ（Branch Target Instruction Cache）として知られている）として実施されうる。第１のケースでは、分岐ターゲットキャッシュ４６は、以前に識別された分岐命令の命令アドレスを格納し、また、対応する分岐ターゲットアドレスを格納する。第２のケースでは、分岐ターゲットキャッシュ４６は、以前に識別された分岐命令の命令アドレスと、これら分岐命令の実際のターゲット命令と、ターゲット命令のアドレスの後の次の命令アドレスとを格納する。
【００２３】
それにも関わらず、与えられた命令が以前に取得され、復号され、条件付分岐命令として識別されれば、その対応する命令アドレスが、分岐ターゲットキャッシュ４６内に格納される。従って、分岐ターゲットキャッシュ４６は、既知の分岐命令の命令アドレスを格納し、新たに取得された各命令の命令アドレスが、分岐ターゲットキャッシュ４６内に保持されたアドレス値と比較される。比較が一致すること（分岐ターゲットキャッシュヒット）は、新たに取得された命令が、既知の分岐命令であることを意味する。一方、一致しないこと（分岐ターゲットキャッシュミス）は、新たに取得された命令が、分岐命令であるかを判定するために、命令復号が必要とされることを意味する。
【００２４】
分岐命令が分岐ターゲットキャッシュヒットであるとの検知に基づいて識別されるステージは、分岐命令が命令復号に基づいて識別されるステージより早いので、分岐ターゲットキャッシュヒットである分岐命令を予測するために使用される分岐予測情報は、分岐ターゲットキャッシュミスである分岐命令の予測に使用される分岐予測情報よりもより迅速に使用可能になるに違いない。従って、マイクロプロセッサ１０の少なくとも１つの実施形態では、その分岐予測方法は、既知の分岐命令の識別のために分岐ターゲットキャッシュ４６を保持することと、マイクロプロセッサ１０の命令パイプライン１８に取得された分岐命令が、分岐ターゲットキャッシュヒット又は分岐ターゲットキャッシュミスであるかを判定することと、第１の分岐履歴テーブル４８に格納された第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットである分岐命令を、採用される又はされないとして予測することと、第２の分岐履歴テーブル５０に格納された第２の分岐予測情報に従って、分岐ターゲットキャッシュミスである分岐命令を、採用される又はされないとして予測することとを含む。
【００２５】
この方法は更に、第１の分岐履歴テーブル４８が、分岐ターゲットキャッシュ４６のものと一致するアクセス速度を持つように構成することと、第２の分岐履歴テーブル５０が、命令キャッシュ１４のものと一致するアクセス速度を持つように構成することとを含む。命令キャッシュからは、命令が命令パイプライン１８へと取得される。一般に、命令キャッシュ１４のアクセス速度は、実際の（取得された）プログラム命令が、適切な命令クロックサイクルで第１の復号ステージ３６へ提供されるようにされる。例として、第１の分岐履歴テーブル４８及び分岐ターゲットキャッシュ４６は、命令パイプライン１８のＭ個のサイクルにおいてアクセス可能に構成することができる。また、第２の分岐履歴テーブル５０は、命令パイプライン１８のＮ個のサイクルにおいてアクセス可能に構成することができる。Ｍは第１の数、Ｎは第２の数であり、ＭはＮよりも小さい。
【００２６】
第１の分岐履歴テーブル４８を、第２の分岐履歴テーブル５０よりも高速に構成する１つの方法は、第１の分岐履歴テーブル４８を、第２の分岐履歴テーブル５０よりも少ない数の分岐予測を格納するように構成し、もって、第１の分岐履歴テーブル４８内の分岐予測変量にアクセスすることが、第２の分岐履歴テーブル５０内の分岐予測変量にアクセスするよりも少ない時間しかかからないようにすることを含む。上述したように、分岐履歴テーブル４８，５０に格納された個々の予測変量は、例えば２ビットカウンタのような飽和カウンタを備える。この飽和カウンタは、強く採用された状態、弱く採用された状態、弱く採用されていない状態、及び、強く採用されていない状態を有するインジケータの形態で分岐予測情報を与える。しかしながら、分岐履歴テーブル４８，５０が、異なるタイプのカウンタを適応するかもしれないこと、あるいは、分岐予測変量とは全く異なる形態を適応するかもしれないことが理解されるべきである。
【００２７】
上述した２テーブル分岐予測方法の更なる局面では、マイクロプロセッサ１０は、第１の分岐予測情報に従って、分岐ターゲットキャッシュヒットのための初期予測を行い、第２の分岐予測情報に従って、分岐ターゲットキャッシュヒットのための対応する次の予測を行うように構成されうる。すなわち、マイクロプロセッサ１０は、第１の分岐履歴テーブル４８に格納された情報を用いてなされた初期（早期）分岐予測に基づいて、分岐ターゲットキャッシュヒットを取得する命令を制御し、そして、第２の分岐履歴テーブル５０に格納された情報を用いてなされた対応する次の分岐予測が、初期予測と一致しない場合には、そのような制御を無効にするように構成される。
【００２８】
この状況では、早期の予測を無視することは、命令取得を再指示することを含む。例えば、初期予測が採用される場合、分岐予測回路４２が、示された分岐ターゲットアドレスに対して命令取得を指示し、次の予測が採用されない場合、分岐予測回路は、採用されない分岐命令後、次の連続するアドレスへ命令取得を再指示する。例えば、第２の分岐履歴テーブル５０が、小さくかつ高速である第１の分岐履歴テーブル４８よりも大きく、恐らくはより正確である場合、次の分岐予測を用いて、早期の分岐予測を条件付で再指示（無視）することに利点がある。
【００２９】
上記方法を用いて、第２の分岐履歴テーブル５０は、分岐ターゲットキャッシュヒット及び分岐ターゲットキャッシュミスの両方に用いられる予測情報を格納する。そのため、第２の分岐履歴テーブル５０を更新する方法は、分岐ターゲットキャッシュヒット及び分岐ターゲットキャッシュミスのためになされた分岐予測の解決に応じて、第２の分岐予測情報を更新し、これによって、第２の分岐予測情報が、分岐ターゲットキャッシュヒット及び分岐ターゲットキャッシュミスの両方のための分岐履歴を反映できるようになることを含む。すなわち、実行ユニット２２は、分岐ターゲットキャッシュヒットと分岐ターゲットキャッシュミスとの両方について、個々の分岐命令が実際に採用されているか又はされていないかに関し、分岐予測回路４２にフィードバックを提供するように構成されうる。そして、そのフィードバックは、第２の分岐履歴テーブル５０に格納された予測情報を更新するために使用される。一方、第１の分岐履歴テーブル４８内に格納された予測情報は、（更新された）第２の分岐予測情報に応じて更新される。同様に、少なくとも、分岐ターゲットキャッシュヒットのためのフィードバックは、第１の分岐履歴テーブル４８の更新の際に直接使用するために、分岐予測回路４２へ提供される。
【００３０】
本明細書で教示された２テーブル分岐予測方法の別の実施形態は、命令アドレスを命令パイプライン１８に取得することに応じて、第１及び第２の分岐履歴テーブル４８，５０へのアクセスを開始することと、分岐ターゲットキャッシュ４６において、この命令アドレスがヒットであることを検知することに応じて、第２の分岐履歴テーブル５０へのアクセスを終了することとを含む。従って、マイクロプロセッサ１０は、新たな命令を命令パイプライン１８に取得することと連携して、第１及び第２の分岐履歴テーブル４８，５０へのアクセスを開始する。新たに取得された命令が、分岐ターゲットキャッシュヒットとして検知された場合、マイクロプロセッサ１０は、第２の分岐履歴テーブル５０へのアクセスを、必要ないものとして終了させる。
【００３１】
そのような状況下でアクセスを終了させることによって、電力を節約することができる。例えば、第２の分岐履歴テーブル５０からの分岐予測結果を出力するために使用されるセンスアンプ及び／又はその他の出力回路は、電源を投入する必要がない。更に、上記方法に従って第２の分岐履歴テーブル５０へのアクセスを開始することは、これらアクセスのうちの幾つかが終了したとしても、必要とされる結果がタイムリーに利用可能になることを保証する。つまり、第２の分岐履歴テーブル５０へのアクセスが、命令パイプライン１８において早期に開始される。これによって、分岐ターゲットキャッシュミスに対する第２の分岐履歴テーブル５０からの予測結果が命令パイプライン１８内で準備され、後に利用可能となる。
【００３２】
このアプローチによって、第１の分岐履歴テーブル４８は、分岐ターゲットキャッシュヒットである分岐命令に限定された予測情報を格納することができ、第２の分岐履歴テーブル５０は、分岐ターゲットキャッシュミスである分岐命令に限定された予測情報を格納することができる。そのため、マイクロプロセッサ１０によって採用される分岐予測情報更新方法は、分岐ターゲットキャッシュミスに対してなされる分岐予測を解決することに応じて第２の分岐予測情報を更新することと、分岐ターゲットキャッシュヒットに対してなされる分岐予測を解決することに応じて第１の分岐予測情報を更新することとを含む。
【００３３】
言い換えれば、マイクロプロセッサ１０は、分岐命令が実際に採用されるか否かを判定するために、実行ユニット２２からのフィードバックを使用する。分岐ターゲットキャッシュヒットであった分岐命令のフィードバックは、第１の分岐履歴テーブル４８内に格納された予測情報を更新するために使用され、分岐ターゲットキャッシュミスであった分岐命令のフィードバックは、第２の分岐履歴テーブル５０内に格納された予測情報を更新するために使用される。このようにして予測情報を分離することによって、マイクロプロセッサ１０の予測精度を、少なくとも、分岐ターゲットキャッシュヒット及びミスが、異なる採用／不採用挙動を示す程度まで改善する。
【００３４】
図２は、マイクロプロセッサ１０の部分機能ブロック図を提供する。ここでは、図示する機能要素は、本明細書で教示された２テーブル分岐予測方法を実行するように構成することができる。この図から、命令パイプライン１８の取得ステージ３２が、命令キャッシュ１４及び分岐制御ロジック４４へ命令アドレスを与えることがわかるだろう。命令キャッシュ１４は、これらアドレスを用いて、命令パイプラインの復号ステージ３６への出力のために、対応する命令を取得する。一方、分岐制御ロジック４４は、各取得アドレスを、分岐ターゲットキャッシュ４６と比較して、既知の分岐命令を検知する。つまり、分岐ターゲットキャッシュ４６内に格納された命令アドレスと一致する命令アドレスを識別する。
【００３５】
分岐ターゲットキャッシュ４６が、分岐制御ロジック４４にヒット指示を返す場合、分岐制御ロジック４４は、第１の分岐履歴テーブル４８から予測情報を取得し、分岐ターゲットキャッシュヒットが採用と予測されるか、あるいは不採用と予測されるかを判定する。予測インジケータが、採用との予測を示す場合、分岐制御ロジック４４は、取得ステージ３２の次の取得アドレスが、この図では“ＢＴＡ（ＢＴＣ  ＨＩＴ）”と示される分岐キャッシュヒットの分岐ターゲットアドレスを用いて更新されるようにする。ＢＴＡ（ＢＴＣ  ＨＩＴ）は、分岐ターゲットキャッシュ（ＢＴＳ）ヒットである分岐ターゲットアドレス（ＢＴＡ）を示す。
【００３６】
分岐ターゲットキャッシュミスである命令アドレスは、取得ステージ３２，３４を介して連続的に伝えられ、これらアドレスに対応する命令は、復号ステージ３６を復号するために命令キャッシュ１４によって提供される。その点では、分岐ターゲットキャッシュ４６においてミスであった復号された分岐命令が認識され、分岐制御ロジック４４が、分岐命令が採用されるか否かを、第２の分岐履歴テーブル５０からの予測情報を用いて予測する。採用されると予測される場合には、分岐制御ロジック４４は、この図において“ＢＴＡ（ＢＴＣ  ＭＩＳＳ）と示されている対応する分岐ターゲットアドレスを取得ステージ３２に与え、ＢＴＣミスであるＢＴＡを示す。
【００３７】
図３は、上記機能の１又は複数の実施形態のためのアクセスサイクルタイミングを図示する。ここでは、第１の分岐履歴テーブル４８が、分岐ターゲットキャッシュ４６のものと一致するアクセス速度を持つように構成される。このマッチングによって、マイクロプロセッサ１０は、マイクロプロセッサ１０が分岐ターゲットキャッシュヒットを検知することに基づいて分岐命令を識別する同じパイプラインステージ内の分岐予測情報を取得できるようになる。例として、分岐ターゲットキャッシュ４６及び第１の分岐履歴テーブル４８はともに、命令パイプライン１８のＭ個のサイクル（例えば、Ｍ個の命令クロックサイクル）にアクセス可能である。この構成によって、マイクロプロセッサ１０は、Ｍ＋１サイクルの後、分岐ターゲットキャッシュヒットである分岐命令のために、取得ステージ３２へ分岐ターゲットアドレスを提供することができる。
【００３８】
更に、第２の分岐履歴テーブル５０は、命令キャッシュ１４のものと一致するアクセス速度を持つように構成される。あるいは、どんな速度に一致されていても、命令アドレス取得と、復号ステージ３６による対応する命令の引き続く復号との間の遅れのために適切である。例として、命令キャッシュ１４及び第２の分岐履歴テーブル５０は、命令パイプライン１８のＮ個のサイクルにアクセス可能に構成される。この構成によって、マイクロプロセッサ１０は、Ｎ＋１サイクルの後、分岐ターゲットキャッシュミスである分岐命令のために、取得ステージ３２へ分岐ターゲットアドレスを提供することができる。
【００３９】
限定しない例では、Ｍは、１クロックサイクルであり、Ｎは、２クロックサイクルである。従って、マイクロプロセッサ１０は、第２の分岐履歴テーブル５０と比較して、含んでいる個々の分岐予測変量数の観点から比較的小さな第１の分岐履歴テーブル４８を用いて、２つの命令クロックサイクルにおける分岐ターゲットキャッシュヒットの分岐予測を得る。更に、マイクロプロセッサ１０は、第２の分岐履歴テーブル５０を使用して、３つの命令クロックサイクルにおける分岐ターゲットキャッシュヒットの分岐予測を得る。
【００４０】
上記の例から、「ミニ」分岐履歴テーブル（すなわち、第１の分岐履歴テーブル４８）を用いることによって、マイクロプロセッサ１０は、分岐ターゲットキャッシュヒットとして検知される分岐命令のための優れた予測及び取得性能を得ることがわかる。更に、このような性能を得ることは、任意に大きくかつ（恐らくは）より正確なメイン分岐履歴テーブル（すなわち、第２の分岐履歴テーブル５０）を保持することなくして得られない。このテーブルは、分岐ターゲットキャッシュヒットではない分岐命令を予測したり、ミニテーブルからなされた初期予測を無効にするために使用される。
【００４１】
このように、当業者であれば、本明細書で開示された２テーブル分岐予測は、マイクロプロセッサアーキテクチャ、ミニ分岐履歴テーブルとメイン分岐履歴テーブルとの間の相対的な命令サイクルアクセスタイミング差、ミニテーブルを用いて、分岐ターゲットキャッシュヒットが限定的に又は最初に予測されているか、ミニ分岐履歴テーブルとメイン分岐履歴テーブルとの更新のために選択されるヒューリスティックス及び方法、ミニテーブル及びメインテーブルに格納された分岐予測情報の特定のフォーマット、ミニテーブルとメインテーブルとの相対的なサイズ等に関するような多くのバリエーションに従うことができることを理解すべきである。更に詳しくは、当業者であれば、本発明は、前述の説明や、添付図面によって限定されるものではないことを理解すべきである。実際、本発明は、特許請求の範囲及びそれらの等価物によってのみ制限される。
【図面の簡単な説明】
【００４２】
【図１】図１は、マイクロプロセッサのブロック図である。
【図２】図２は、図１のマイクロプロセッサで実施されうる命令パイプライン用のフロントエンド回路のブロック図である。
【図３】図３は、図２で例示されたフロントエンド回路の実施形態の命令処理のフローチャートである。
【図１】
2008542917.tif 000003
【図２】
2008542917.tif 000004
【図３】
2008542917.tif 000005
【国際調査報告】
2008542917.tif 000006