JP7366122B2 - プロセッサのフィルタリングされた分岐予測構造 - Google Patents

Description

処理効率を高めるために、プロセッサは、１つ以上の予測処理技術を使用することができる。予測処理技術の１つのタイプは、分岐予測と呼ばれ、プロセッサは、分岐命令の結果を予測することによって、プロセッシングユニットが分岐命令を評価する前に、予測された分岐に従って後続の命令を投機的に実行し始めることができる。分岐予測をサポートするために、プロセッサは、分岐ターゲットバッファ（ＢＴＢ）と呼ばれる分岐ターゲット構造及び分岐方向予測器を採用する。ＢＴＢは、予測された分岐のアドレス情報を記憶し、分岐方向予測器は、所定の分岐が取られると予期されるかどうかを予測する。しかしながら、従来の分岐予測構造は、望ましくない量の電力を消費することがある。

添付図面を参照することによって本開示をより良好に理解することができ、その多くの特徴及び利点が当業者に明らかになる。異なる図面で同じ符号を使用することは、類似又は同一のアイテムを示す。

いくつかの実施形態による、フィルタリングされた分岐予測構造を有する分岐予測器を含むプロセッサのブロック図である。 いくつかの実施形態による、分岐ターゲットバッファへのフィルタリングされたアクセスを示す、図１の分岐予測モジュールの一部のブロック図である。 いくつかの実施形態による、プロセッサにおいて分岐ターゲットバッファへのアクセスをフィルタリングする方法のフローチャートである。 いくつかの実施形態による、１つ以上の分岐方向テーブルへのフィルタリングされたアクセスを示す、図１の分岐予測モジュールの一部のブロック図である。 いくつかの実施形態による、指定された予測期間に亘るテーブル使用に基づいて、１つ以上の分岐方向テーブルへのアクセスをフィルタリングする方法のフローチャートである。 いくつかの実施形態による、テーブルユーティリティの予測に基づくテーブル使用に基づいて、１つ以上の分岐方向テーブルへのアクセスをフィルタリングする方法のフローチャートである。

図１～図６は、プロセッサの分岐予測器における電力消費を低減させる技術を示す。分岐予測器は、予測された分岐アドレス及び予測された分岐方向を含む、予測された分岐を識別するための１つ以上の予測構造を含む。電力消費を低減させるために、分岐予測器は、有用な分岐予測情報を提供することが予期されない１つ以上の予測構造を選択し、選択された構造をフィルタリングして、フィルタリングされた構造が分岐予測に使用されないようにする。これにより、分岐予測器は、予測された分岐の精度を実質的に低下させることなく、分岐予測に使用される電力量を低減させる。

説明するために、いくつかの実施形態では、分岐予測器は、一方の分岐ターゲットバッファ（ＢＴＢ）がレベル１（Ｌ１）ＢＴＢであり、他方がレベル２（Ｌ２）ＢＴＢであるレベルに編成された、２つのＢＴＢを含む。Ｌ２ ＢＴＢは、Ｌ１ ＢＴＢよりも大きいが、Ｌ１ ＢＴＢよりもアクセスが低速である。従来、分岐予測器は、予測された分岐アドレスを識別するために、プロセッサでフェッチされた命令アドレス毎にＬ１ ＢＴＢ及びＬ２ ＢＴＢの両方にアクセスする。しかしながら、Ｌ１ ＢＴＢにおいてヒットする可能性が高い（すなわち、記憶されているとして識別される）フェッチされた命令アドレスに対し、Ｌ２ ＢＴＢへの同時アクセスは、電力を不必要に消費する。更に、多くのケースでは、フェッチされた命令アドレスは、仮想アドレス空間において空間的に近接する、以前にフェッチされた命令アドレスもＬ１ ＢＴＢ内でヒットする場合に、Ｌ１ ＢＴＢ内でヒットする可能性がより高い。言い換えると、フェッチされた命令アドレスが比較的高い空間コードの局地性を有する場合、Ｌ１ ＢＴＢのヒットが増加する可能性が高い。したがって、本明細書で説明する技術を使用して、分岐予測器は、同じメモリ空間領域（本明細書では、ページと呼ばれる）へのアクセスのカウントを維持し、カウントが閾値を超えると、対応するメモリページ内のフェッチされたアドレスについてＬ２ ＢＴＢへのアクセスを抑制する。これにより、分岐予測器は、Ｌ２ ＢＴＢへの不必要なアクセスを低減させ、プロセッサにおける動的な電力消費を低減させる。

別の例として、いくつかの実施形態では、分岐予測器は、ベース予測器と、分岐方向を予測するための複数の方向テーブルと、を使用し、各方向テーブルは、方向テーブルに記憶されているフェッチされた命令アドレスの履歴に基づいて、予測分岐の方向を独立して予測する、タグ付けされたテーブルである。フェッチされた命令アドレスについて、分岐予測器は、フェッチされた命令アドレスに関連するタグに対してヒットするテーブルのセットを識別する。分岐予測器は、ベース予測器によって生成された予測を、識別されたテーブルの各セットからの予測と組み合わせて、組み合わされた予測を生成する。しかしながら、いくつかの予測テーブルは、フェッチされた命令アドレスの所定のストリームに対してヒットする可能性が低い。したがって、電力消費を低減させるために、分岐予測器は、所定の期間、所定の命令アドレス又はこれらの組み合わせに対し、各方向テーブルがヒットすると予測されるかどうかを予測する。分岐予測器は、ヒットが予測されず、したがって有用な分岐方向情報を提供する可能性が低い方向テーブルを無効にする。これにより、分岐予測器は、複数の方向テーブルへのアクセスの総数を低減させ、分岐予測精度を実質的に低下させることなく電力を低減させる。

図１は、いくつかの実施形態による、フィルタリングされた分岐予測構造を含むプロセッサ１００を示す。本明細書で使用されるように、分岐予測構造は、プロセッサ１００における分岐予測に対する分岐予測構造の影響を選択的に有効又は無効することができる場合に、フィルタリングされた構造である。本明細書で更に説明するように、プロセッサ１００は、構造へのアクセスを抑制すること、構造を無効にすること（例えば、構造を低電力状態に置くこと）、又は、これらの組み合わせを含むいくつかの方法のうち１つ以上において、構造が分岐予測に影響を与えないように、分岐予測構造をフィルタリングする。

プロセッサ１００は、電子デバイスの代わりに、特定のタスクを実行するように命令セット（例えば、コンピュータプログラム）を実行する。いくつかの実施形態では、プロセッサ１００は、デスクトップ又はラップトップコンピュータ、サーバ、ゲームコンソール、スマートフォン、タブレット等の様々な電子デバイスのうち何れかに組み込まれる。命令の実行をサポートするために、プロセッサ１００は、命令フェッチステージ１０２及び追加のパイプラインステージ（図示省略）を有する命令パイプラインを含む。追加のパイプラインステージは、フェッチされた命令をオペレーションのセットに復号するステージと、復号されたオペレーションを実行する実行ステージと、実行された命令をリタイアするリタイアステージと、を含む。いくつかの実施形態では、プロセッサ１００は、１つ以上のメモリコントローラ、入力／出力コントローラ、メモリ構造（例えば、１つ以上のキャッシュ）等を含む、命令の実行をサポートするための追加のモジュールを含むことが理解されよう。また、いくつかの実施形態では、プロセッサ１００は、追加の命令パイプラインを含むことが理解されよう。例えば、いくつかの実施形態では、プロセッサ１００は、複数のプロセッサコアを含み、各プロセッサコアは、命令セットを実行するための少なくとも１つの命令パイプラインを有する。さらに、いくつかの実施形態では、プロセッサ１００は、描画オペレーション、表示オペレーション、他のグラフィックスオペレーションに関連するオペレーションを実行する１つ以上のグラフィックスプロセッシングユニット（ＧＰＵ）等のように、特殊なタスクに関連するオペレーションを実行するように特に設計された追加のプロセッシングユニットを含む。

図１の例示された実施形態に戻ると、命令フェッチステージ１０２は、命令ポインタ１０１に基づいて、命令キャッシュ１０３から命令を取り出す（フェッチする）。当業者に理解されるように、命令ポインタ１０１は、フェッチされる現在の命令（複数可）を示すアドレス値であり、実行される命令のプログラムフローを修正するために、選択されたオペレーションを実行することによって修正される。例えば、いくつかの実施形態では、分岐命令は、例えば、分岐命令又は関連する命令によって指定されたデータの評価に基づいて、命令ポインタ１０１を修正する。

高い命令フェッチ帯域幅をサポートするために、プロセッサ１００は、所定のフェッチされた命令が分岐命令に対応するかどうかを予測し、所定の分岐命令の方向を予測し（すなわち、所定の分岐命令が実行されるか否かを予測し）、所定の分岐命令が実行されると予測される場合に、所定の分岐命令のターゲットアドレスを予測する分岐予測器１１０を含む。分岐予測器１１０は、Ｌ１ ＢＴＢ１１２と、Ｌ２ ＢＴＢ１１４と、分岐方向テーブル１１６と、分岐予測制御モジュール１２０と、を含む、分岐予測をサポートするためのいくつかのモジュール及び構造を含む。分岐予測制御モジュール１２０は、分岐予測構造を有効又は無効にすること、分岐予測構造へのアクセスを抑制すること、分岐予測構造に記憶されたデータを管理すること、本明細書で更に説明する他の管理オペレーションを含む、分岐予測器１１０のオペレーションを管理する。

Ｌ１ ＢＴＢ１１２及びＬ２ ＢＴＢ１１４の各々は、分岐命令であると予測される異なる命令ポインタ値に対応する複数のエントリを含む。少なくとも１つの実施形態では、分岐予測制御モジュール１２０は、Ｌ２ ＢＴＢ１１４がＬ１ ＢＴＢ１１２のビクティムバッファとなるように、Ｌ１ ＢＴＢ１１２及びＬ２ ＢＴＢ１１４のエントリを管理する。いくつかの実施形態では、Ｌ２ ＢＴＢ１１４は、Ｌ１ ＢＴＢ１１２よりも大きな構造であり、Ｌ１ ＢＴＢ１１２よりも多くのエントリを含む。分岐予測制御モジュール１２０は、指定された条件（例えば、新たなデータがＬ１ ＢＴＢ１１２に移動される等）に基づいてＬ１ ＢＴＢ１１２からデータをエビクトするので、分岐予測制御モジュール１２０は、エビクトされたデータをＬ２ ＢＴＢ１１４に移動する。

命令サイクル毎に、命令フェッチステージ１０２は、命令ポインタ１０１を分岐予測器１１０に提供する。これに応じて、分岐予測制御モジュール１２０は、Ｌ１ ＢＴＢ１１２が、命令ポインタ１０１によって示されるフェッチされた命令アドレスに対応するエントリを含むかどうかを判別する。エントリが、受信された命令ポインタ値に対応すると識別したことに応じて（ＢＴＢヒットと呼ばれる）、分岐予測制御モジュール１２０は、識別されたエントリから分岐ターゲットアドレス（ＢＴＡ）を取り出し、ＢＴＡを命令フェッチステージ１０２に提供する。

分岐予測制御モジュール１２０は、フェッチされた命令アドレス毎にＬ１ ＢＴＢ１１２にアクセスすることに加えて、Ｌ２ ＢＴＢ１１４へのアクセスが生産的であると予期されるかどうか、すなわち、Ｌ２ ＢＴＢ１１４へのアクセスがＢＴＢヒットと予期されるかどうかに基づいて、Ｌ２ ＢＴＢ１１４に選択的にアクセスする。図２及び図３に関して以下に更に説明するように、分岐予測制御モジュール１２０は、仮想メモリ空間の特定の領域に対応するフェッチされたアドレスについて、Ｌ１ ＢＴＢ１１２におけるヒットのカウントを維持し、ここでは、特定の領域をメモリページと呼ぶ。分岐予測制御モジュール１２０によって監視されるメモリページは、プロセッサ１００で実行されるオペレーティングシステムによって維持されるメモリページ等のように、プロセッサ１００における他のオペレーションのために使用されるメモリページとは異なってもよいことが理解されよう。

分岐予測制御モジュール１２０は、フェッチされた命令アドレスを受信したことに応じて、フェッチされた命令アドレスに対応するメモリページを識別し、識別されたメモリページに対応するカウントを識別する。分岐予測制御モジュール１２０は、カウントが閾値を下回っていることに応じて、フェッチされた命令アドレスをＬ２ ＢＴＢ１１４に提供するとともに、フェッチされた命令アドレスがＬ１ ＢＴＢ１１２においてヒットしたかどうかを識別する。Ｌ２ ＢＴＢ１１４におけるヒットに応じて、分岐予測制御モジュール１２０は、Ｌ２ ＢＴＢ１１４の識別されたエントリから分岐ターゲットアドレス（ＢＴＡ）を取り出し、ＢＴＡを命令フェッチステージ１０２に提供する。

分岐予測制御モジュール１２０は、識別されたメモリページのカウントが所定の閾値を上回ると判別したことに応じて、例えば、フェッチ命令アドレスをＬ２ ＢＴＢ１１４に提供しないことによって、フェッチされた命令アドレスのＬ２ ＢＴＢ１１４へのアクセスを抑制する。よって、分岐予測制御モジュール１２０は、Ｌ１ ＢＴＢ１１２にヒットすると予測されるフェッチされた命令アドレスのＬ２ ＢＴＢ１１４へのアクセスを回避し、プロセッサ１００における電力消費を低減させる。

分岐予測器１１０は、ＢＴＡをフェッチステージ１０２に提供することに加えて、予測される分岐命令毎に分岐方向予測を提供し、分岐方向予測は、分岐が実行されることが予測されるかどうかを示す。分岐方向の予測をサポートするために、分岐予測器１１０は、分岐方向テーブル１１６を含む。少なくとも１つの実施形態では、分岐方向テーブル１１６は、タグ付き幾何学長（ＴＡＧＥ）予測器の少なくとも一部を形成し、個々のテーブル（例えば、テーブル１１７，１１８）は、等比級数（geometric series）を形成するフェッチされた命令アドレスのグローバル履歴を記憶する、部分的にタグ付けされた予測器テーブル（partially tagged predictor table）である。また、各テーブルは、対応する等比級数に従って異なる履歴を記憶する。テーブルの各のエントリは、対応するエントリが分岐予測に有用であると予測されるかどうかを示す有用ビットと、分岐方向のバイアス値を追跡するためのカウンタと、エントリに関連する仮想アドレスを示すタグと、を記憶する。

分岐予測制御モジュールは、分岐方向テーブル１１６の各々に記憶されたデータを管理する。少なくとも１つの実施形態では、分岐予測制御モジュールは、何れの分岐命令が実行され、何れの分岐命令が実行されないかを含む、プロセッサ１００において実行される分岐命令のパターンを経時的に分析し、識別されたパターンに基づいて分岐方向テーブル１１６を更新する。少なくとも１つの実施形態では、分岐予測制御モジュール１２０は、本明細書で分岐予測ウィンドウと呼ばれるブロック又はセットで実行される命令を分析し、各分岐予測ウィンドウ上で分岐方向テーブル１１６にアクセスする。識別されたパターンに基づいて、分岐予測制御モジュールは、バイアス値、有用ビット、１つ以上のエントリに関連するタグ、又は、これらの組み合わせを更新する。

少なくとも１つの実施形態では、分岐方向テーブル１１６は、２つのレベル（レベル１（Ｌ１）テーブル及びレベル２（Ｌ２）テーブルと呼ばれる）に分割される。予測ウィンドウの間、分岐予測制御モジュール１２０は、ＢＴＢ１１２，１１４の何れかが予測ウィンドウ内の分岐を示すことに応じて、方向予測を識別するために、Ｌ１テーブル及びＬ２テーブルの両方にアクセスする。いくつかの実施形態では、分岐予測制御モジュール１２０は、予測ウィンドウに関連する経路履歴（例えば、予測ウィンドウに含まれる命令に関連する制御フロー履歴）に基づいて生成されたタグを使用して、各テーブルにアクセスする。一致したタグを有するエントリを有する分岐方向テーブル１１６の各々は、対応するエントリに記憶されたバイアス値を分岐予測制御モジュール１２０に提供し、分岐予測制御モジュール１２０は、受信したバイアス値を、特定の分岐予測アルゴリズムに従って選択又は組み合わせる。特定の分岐予測アルゴリズムは、プロセッサ１００の設計及びアプリケーションに応じて変わる。

いくつかのシナリオでは、所定の予測ウィンドウの経路履歴によって、１つ以上の分岐方向テーブル１１６は、生成されたタグに対応するエントリを記憶せず、又は、分岐予測制御モジュール１２０によって生成された分岐方向予測の精度を向上させない分岐予測情報を提供する。これらの１つ以上の分岐予測テーブルは、所定の予測ウィンドウ又は予測ウィンドウのセットについて有用な分岐予測情報を提供しないので、これらの分岐予測テーブルへのアクセスを、本明細書では「非生産的」読み出しと呼ぶ。非生産的読み出しは、分岐予測の精度を実質的に向上させることなく、プロセッサ１００内の電力を消費することが理解されよう。したがって、図４～図６に関して本明細書で更に説明するように、分岐予測器１１０は、選択された分岐予測テーブルが非生産的読み出しを生じさせる予測可能性（predicted likelihood）に基づいて、１つ以上の分岐方向テーブル１１６を非アクティブ状態に選択的に置く。非アクティブ状態の分岐予測テーブルは、分岐予測制御モジュール１２０によってアクセスされず、いくつかの実施形態では、低電力状態に置かれ、これにより、電力を節約する。本明細書で更に説明するように、分岐予測制御モジュール１２０は、予測ウィンドウのセット間の各テーブルへのヒットの数に基づいて、分岐方向テーブル１１６へのヒットのパターン履歴に基づいて、又は、これらの組み合わせに基づいて等のように、いくつかの方法のうち１つ以上で非アクティブ状態に置かれる分岐予測テーブルを選択する。

図２は、いくつかの実施形態による、ＢＴＢ１１４へのアクセスのフィルタリングを管理する図１の分岐予測器１１０の一部のブロック図である。図示した例では、分岐予測制御モジュールは、ＢＴＢアクセス制御モジュール２３０と、ページアクセステーブル２２５と、を含む。ＢＴＢアクセス制御モジュール２３０は、受信したフェッチされた命令アドレス（例えば、フェッチされたアドレス２１１）及びページアクセステーブル２２５に記憶されたデータに基づいて、Ｌ２ ＢＴＢ１１４へのアクセスを制御する。

ページアクセステーブル２２５は、複数のエントリ（例えば、エントリ２２６）を含み、各エントリは、メモリページ（例えば、メモリページ２３１）に対応する。上述したように、いくつかの実施形態では、メモリページ（例えば、メモリページ２３１，２３２）は、プロセッサ１００において実行されるオペレーティングシステムによって使用されるメモリページに対応する。他の実施形態では、メモリページ２３１，２３２は、オペレーティングシステムによって使用されるメモリページに対応しない。いくつかの実施形態では、メモリページ２３１，２３２の各々のサイズは、プロセッサ１００のユーザ又はプログラマによって構成可能である。

ページアクセステーブル２２５の各エントリは、メモリページ識別子フィールド（例えば、エントリ２２６の識別子フィールド２２７）と、アクセスカウントフィールド（例えば、エントリ２２６のアクセスカウントフィールド２２８）と、を含む。メモリページ識別子フィールド２２７は、エントリに対応するメモリページの識別子を記憶し、アクセスカウントフィールド２２８は、以下に更に説明するように、Ｌ２ ＢＴＢ１１４におけるヒットなしのメモリページへの連続アクセス数を記憶する。動作中、ＢＴＢアクセス制御モジュール２３０は、ページアクセステーブル２２５のエントリ及びフィールドを管理し、ページアクセステーブル２２５に基づくメモリページに対するアクセスカウントに基づいて、Ｌ２ ＢＴＢ１１４へのアクセスをフィルタリングする。

図３は、いくつかの実施形態による、Ｌ２ ＢＴＢ１１４へのアクセスをフィルタリングする方法３００のフローチャートを示す。ブロック３０２において、ＢＴＢアクセス制御モジュール２３０は、フェッチされた命令アドレス（例えば、フェッチされたアドレス２１１）を受信する。ブロック３０４において、ＢＴＢアクセス制御モジュール２３０は、フェッチされたアドレスに対応するメモリページを識別し、識別されたメモリページがページアクセステーブル２２５にエントリを有するかどうかを判別する。エントリを有する場合、方法のフローは、以下に説明するブロック３０８に移動する。識別されたメモリページがページアクセステーブル２２５にエントリを有しない場合、方法のフローは、ブロック３０６に移動し、ＢＴＢアクセス制御モジュール２３０は、識別されたメモリページのページアクセステーブル２２５にエントリを割り当て、割り当てられたエントリのアクセスカウントフィールドを初期値（例えば、ゼロ）に設定する。いくつかのケースでは、アクセス制御モジュールは、最近最も使用されていない（a least recently used）置換ポリシー等の特定の置換ポリシーを使用して別のエントリを置き換えることによって、エントリを割り当てる。方法のフローは、ブロック３０８に進む。

ブロック３０８において、ＢＴＢアクセス制御モジュール２３０は、識別されたメモリページのアクセスカウントフィールドが閾値よりも大きいかどうかを判別する。閾値よりも大きい場合、方法のフローは、ブロック３１０に移動し、ＢＴＢアクセス制御モジュール２３０は、例えば、フェッチされた命令アドレスをＬ２ ＢＴＢ１１４に提供しないことによって、Ｌ２ ＢＴＢ１１４へのアクセスをフィルタリングする。方法のフローは、ブロック３１１に移動し、ＢＴＢアクセス制御モジュール２３０は、Ｌ１ ＢＴＢ１１２が、フェッチされた命令アドレスに対するＢＴＡをＬ２ ＢＴＢ１１４に送信するかどうかを判別する。そうでない場合（すなわち、フェッチされた命令アドレスに対するＬ１ ＢＴＢミスが存在する場合）、方法のフローは、ブロック３０２に戻る。フェッチされた命令アドレスに対するＬ１ ＢＴＢヒットが存在し、Ｌ１ ＢＴＢ１１２が、フェッチされた命令アドレスに対するＢＴＡをＬ２ ＢＴＢ１１４に送信する場合、方法のフローは、ブロック３２１に移動し、ＢＴＢアクセス制御モジュール２３０は、識別されたメモリページに対するアクセスカウントフィールドを初期値にリセットする。方法のフローは、ブロック３０２に戻る。

ブロック３０８に戻り、ＢＴＢアクセス制御モジュール２３０が、識別されたメモリページに対するアクセスカウントが閾値以下であると判別した場合、方法のフローは、ブロック３１２に進み、ＢＴＢアクセス制御モジュール２３０は、フェッチされた命令アドレスをＬ２ ＢＴＢ１１４に提供して、Ｌ２ ＢＴＢ１１４が、フェッチされた命令アドレスに対するＢＴＡを記憶するかどうかを判別する。方法のフローは、ブロック３１４に進む。

ブロック３１４において、Ｌ１ ＢＴＢ１１２は、Ｌ１ ＢＴＢ１１２が、フェッチされた命令アドレスに対するＢＴＡを記憶するかどうかに基づいて、ＢＴＢヒット又はＢＴＢミスを示す。Ｌ１ ＢＴＢ１１２におけるＢＴＢヒットに応じて、方法のフローは、ブロック３１６に移動し、ＢＴＢアクセス制御モジュール２３０は、識別されたメモリページに対するアクセスカウントを修正しないままにする。方法のフローは、ブロック３０２に戻る。

ブロック３１４に戻り、Ｌ１ ＢＴＢ１１２がＢＴＢミスを示す場合、方法のフローは、ブロック３１８に移動し、ＢＴＢアクセス制御モジュール２３０は、Ｌ２ ＢＴＢ１１４が、フェッチされた命令アドレスに対するＢＴＢヒットを示したかどうかを判別する。フェッチされた命令アドレスに対するＬ２ ＢＴＢ１１４におけるヒットに応じて、方法のフローは、ブロック３１９に移動し、ＢＴＢアクセス制御モジュール２３０は、識別されたメモリページに対するアクセスカウントフィールドを初期値にリセットする。方法のフローは、ブロック３０２に戻る。ブロック３１８において、Ｌ２ ＢＴＢがＢＴＢミスを示す場合、方法のフローは、ブロック３２０に移動し、ＢＴＢアクセス制御モジュールは、識別されたメモリページに対するアクセスカウントフィールドをインクリメントする。

図４は、いくつかの実施形態による、分岐方向テーブル１１６の少なくともサブセットへのアクセスをフィルタリングすることを管理する図１の分岐予測器１１０の一部のブロック図である。図示した例では、方向予測テーブルは、２つのサブセット（Ｌ１方向テーブル４４２（例えば、Ｌ１方向テーブル４４８，４４９）のセット、及び、Ｌ２方向テーブル４４４（例えば、Ｌ２方向テーブル４４６，４４７）のセット）に分離される。分岐予測制御モジュール１２０は、方向テーブルアクセス制御モジュール４５２と、テーブル使用履歴４５５と、を含む。方向テーブルアクセス制御モジュール４５２は、何れのＬ２方向テーブル４４４が分岐方向に対する予測を提供するかを識別し、識別されたＬ２方向テーブルをテーブル使用履歴４５５に記録する。また、方向テーブルアクセス制御モジュール４５２は、テーブル使用履歴４５５に基づいて、Ｌ２方向テーブル４４４が有用な予測を提供するパターンを識別し、識別されたパターンに基づいて、Ｌ２方向テーブル４４４のうち選択された１つへのアクセスを有効又は無効にする。

例を用いて説明すると、所定の予測ウィンドウの分岐方向を判別するために、分岐予測制御モジュール１２０は、Ｌ１方向テーブル４４２の各々にアクセスし、特定の分岐方向アルゴリズムに従ってＬ１方向テーブル４４２によって生成された方向予測を組み合わせて、「Ｌ１方向予測」の説明のために指定された方向予測を生成する。従来、分岐予測制御モジュール１２０は、Ｌ１方向テーブル４４２と同様に、Ｌ２方向テーブル４４４の各々に同時にアクセスして、「Ｌ２方向予測」の説明のために指定された別個の独立した方向予測を生成する。Ｌ１方向予測とＬ２方向予測との間に競合が生じた場合、Ｌ２方向テーブルがより大きく、より多くの分岐履歴を利用し、より精度が高いので、Ｌ２方向予測が典型的には選択される。また、Ｌ１予測テーブルよりもアクセスが低速になる。しかしながら、上述したように、所定の予測ウィンドウについては、Ｌ２方向テーブル４４４のサブセットのみが方向予測を提供する可能性が高い。したがって、少なくとも１つの実施形態では、方向テーブルアクセス制御モジュール４５２は、Ｌ２方向テーブル４４４の選択されたサブセットへのアクセスを無効にし、これにより、方向予測の精度を実質的に低下させることなく、電力を節約する。

Ｌ２方向テーブル４４４のサブセットを識別する例示的な技術が図５及び図６に示されている。図５を参照すると、いくつかの実施形態による、複数の予測ウィンドウに亘るテーブル使用に基づいてＬ２方向テーブル４４４のサブセットを識別する方法５００のフローチャートが示されている。ブロック５０２において、方向テーブルアクセス制御モジュール４５２は、テーブル使用履歴４５５を使用して、Ｎ（Ｎは、整数）個の予測ウィンドウに亘ってＬ２方向テーブル４４４の各々の使用を識別する。Ｎ個の予測ウィンドウの各セットを、本明細書では「エポック」と呼ぶ。少なくとも１つの実施形態では、方向テーブルアクセス制御モジュール４５２は、予測ウィンドウの間にＬ２方向テーブルにおいてタグのヒットが存在する場合、所定のＬ２方向テーブルが予測ウィンドウに使用されると識別する。

ブロック５０４において、方向テーブルアクセス制御モジュール４５２は、エポックに対する分岐予測器１１０における方向予測誤り率を識別する。少なくとも１つの実施形態では、予測誤り率は、Ｎで除算されたエポックの間にプロセッサ１００によって識別された分岐方向予測誤りの数である。プロセッサ１００は、様々な従来の予測誤り識別技術のうち何れかを使用して、方向予測誤りを識別する。分岐予測誤り率に基づいて、方向テーブルアクセス制御モジュール４５２は、エポックに対する方向予測誤りのレベル、方向予測誤り率が変化している割合、及び、方向予測誤り率が増大又は減少しているかどうか、のうち１つ以上を示す制御値を生成する。

例えば、いくつかの実施形態では、方向テーブルアクセス制御モジュール４５２は、Ｍ（Ｍは、整数）個のエポックについて計算された参照予測誤り率を生成する。方向テーブルアクセス制御モジュール４５２は、エポックに対して、エポックに対する予測誤り率と参照予測誤り率との差に基づいて、誤り値を計算する。次に、方向テーブルアクセス制御モジュール４５２は、３つの成分、すなわち、１）前のエポックに対する予測誤り率を示す比例成分、２）前のエポックに対する誤り値の合計を示す積分成分、３）最後の２つの誤り値の差を示す微分成分、に基づいて、比例－積分－微分（ＰＩＤ）コントローラを使用して、制御値を計算する。

ブロック５０６において、方向テーブルアクセス制御モジュール４５２は、ブロック５０４において計算された制御値に基づいて、アクティブなＬ２方向テーブルの数を決定する。例えば、制御値が、予測誤り率が閾値を上回るか、閾値を上回る割合で増大していることを示す場合、方向テーブルアクセス制御モジュール４５２は、アクティブなＬ２方向テーブルの数を比較的多い量に設定する。一方、制御値が、予測誤り率が閾値を下回るか、閾値を下回る割合で増大していることを示す場合、方向テーブルアクセス制御モジュール４５２は、アクティブなＬ２方向テーブルの数を比較的少ない量に設定する。これにより、方向テーブルアクセス制御モジュール４５２は、予測誤り率を所定の許容範囲内に維持する。

ブロック５０８において、方向テーブルアクセス制御モジュール４５２は、前のエポックに亘るＬ２方向テーブル４４４の各々の使用に基づいて、及び、ブロック５０６において識別されたアクティブなＬ２方向テーブルの数に基づいて、非アクティブになるＬ２方向テーブル４４４のサブセットを選択する。例えば、いくつかの実施形態では、方向テーブルアクセス制御モジュール４５２は、前のエポック内での使用が閾値を下回るＬ２方向テーブルをサブセットに選択する。サブセットに選択されたＬ２方向テーブルの数によって、ブロック５０６において計算された必要数によって示されるアクティブなＬ２方向テーブルが少なすぎる結果になる場合、方向テーブルアクセス制御モジュールは、必要数が満たされるまで、サブセットからＬ２方向テーブルを除去する。非アクティブなＬ２方向テーブル４４４のサブセットを選択した後、方向テーブルアクセス制御モジュール４５２は、後続のエポックの間、選択されたサブセットへのアクセスを抑制する。

図６は、いくつかの実施形態による、エポック毎に予測されたテーブル使用に基づいて、Ｌ２方向テーブル４４４のサブセットを識別する方法６００のフローチャートを示す。方法６００に関して、方向テーブルアクセス制御モジュール４５２は、各予測ウィンドウの間に各Ｌ２方向テーブル４４４の使用を監視し、使用状況をテーブル使用履歴４５５に記録することが想定される。少なくとも１つの実施形態では、方向テーブルアクセス制御モジュールは、対応するＬ２方向テーブルがタグ一致を示している場合に、テーブルエントリの対応するビット位置に１を記憶し、Ｌ２方向テーブルがタグミスを示している場合に、対応するビット位置に０を記憶することによって、特定の期間の間（例えば、所定数の過去の予測ウィンドウ等）、各Ｌ２方向テーブル４４４の使用パターンを記録する。

ブロック６０２において、方向テーブルアクセス制御モジュール４５２は、テーブル使用履歴４５５にアクセスして、Ｌ２方向テーブル４４４の使用をプロファイルする。いくつかの実施形態では、方向テーブルアクセス制御モジュール４５２は、分岐方向を予測するために通常用いられる分岐予測技術を使用して、パターンを識別する。ブロック６０４において、方向テーブルアクセス制御モジュール４５２は、識別されたパターンに基づいて、Ｌ２方向テーブル４４４の各々に対して、対応するテーブルが次の予測ウィンドウの間に使用されると予期されるかどうかを予測する。ブロック６０６において、方向テーブルアクセス制御モジュールは、次の予測ウィンドウのために、ブロック６０４において使用されると予測されたＬ２方向テーブルをアクティブにする。したがって、次の予測ウィンドウの間、方向テーブルアクセス制御モジュール４５２は、アクティブにされたＬ２方向テーブルのみにアクセスする。これにより、方向テーブルアクセス制御モジュールは、分岐予測精度を維持しながら、電力を節約する。方法のフローは、次の予測ウィンドウのためにブロック６０２に戻る。

本明細書に開示されるように、方法は、プロセッサの命令パイプラインのフェッチステージでの実行のために第１の命令アドレスをフェッチしたことに応じて、第１の命令アドレスを含む第１のメモリ領域を識別することと、第１のメモリ領域について、第１の分岐ターゲットバッファ（ＢＴＢ）への第１のアクセスミス数を識別することと、第１のアクセスミス数が閾値を超えたことに応じて、第１の命令アドレスに対する第１のＢＴＢへのアクセスを抑制することと、を含む。一態様では、方法は、第１の命令アドレスをフェッチしたことに応じて、第２のＢＴＢにアクセスすることを含む。別の態様では、第１のＢＴＢは、第２のＢＴＢのビクティムバッファである。更に別の態様では、第１のメモリ領域について第１のアクセスミス数を識別することは、複数のアクセスミスカウントを記憶するテーブルに基づいて第１のアクセス数を識別することを含み、複数のアクセスミスカウントの各々は、異なるメモリ領域に関連付けられている。

別の態様では、方法は、第１のＢＴＢにおける第１のアクセスミスに応じて、複数のアクセスミスカウントのうち何れかをインクリメントすることを含む。更に別の態様では、複数のアクセスミスカウントのうち何れかをインクリメントすることは、第１のＢＴＢにおける第１のアクセスミス及び第２のＢＴＢにおける第２のアクセスミスに応じて、複数のアクセスミスカウントのうち何れかをインクリメントすることを含む。別の態様では、方法は、第１のＢＴＢにおけるアクセスヒットに応じて、複数のアクセスミスカウントのうち何れかをリセットすることを含む。更に別の態様では、方法は、第２のＢＴＢから第１のＢＴＢに分岐ターゲットアドレスを転送したことに応じて、複数のアクセスミスカウントのうち何れかをリセットすることを含む。

本明細書に開示されるように、いくつかの実施形態では、方法は、第１の期間に亘る第１の複数の分岐方向予測テーブルの各々の使用を示す第１の使用履歴を識別することと、第１の使用履歴に基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、プロセッサの分岐予測器の予測ウィンドウに対して、第１の複数の分岐方向予測テーブルの第１のサブセットへのアクセスを抑制することと、を含む。一態様では、第１の使用履歴を識別することは、分岐予測器の複数の予測ウィンドウについての第１の使用履歴を識別することを含む。一態様では、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することは、複数の予測ウィンドウについての分岐予測誤り率を決定することと、第１の使用履歴及び分岐予測誤り率に基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、を含む。更に別の態様では、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することは、第１の使用履歴に基づいて、分岐予測器の後続の予測ウィンドウの間に使用されると予期される第１の複数の分岐方向予測テーブルのサブセットを予測することと、予測されたサブセットに基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、を含む。

一実施形態では、プロセッサは、第１の命令アドレスをフェッチするように構成されたフェッチステージを含む命令パイプラインと、分岐予測器と、を備え、分岐予測器は、分岐ターゲットアドレスを命令パイプラインに提供するように構成された第１の分岐ターゲットバッファ（ＢＴＢ）と、分岐予測制御モジュールと、を備え、分岐予測制御モジュールは、第１の命令アドレスを含む第１のメモリ領域を識別することと、第１のメモリ領域について、第１のＢＴＢへの第１のアクセスミス数を識別することと、第１のアクセスミス数が閾値を超えたことに応じて、第１の命令アドレスに対する第１のＢＴＢへのアクセスを抑制することと、を行うように構成されている。一態様では、プロセッサは、第２のＢＴＢを備え、分岐予測制御モジュールは、第１の命令アドレスをフェッチしたことに応じて、第２のＢＴＢにアクセスするように構成されている。別の態様では、第１のＢＴＢは、第２のＢＴＢのビクティムバッファである。更に別の態様では、分岐予測制御モジュールは、複数のアクセスミスカウントを記憶するテーブルに基づいて第１のアクセスミス数を識別するように構成されており、複数のアクセスミスカウントの各々は、異なるメモリ領域に関連付けられている。

一態様では、分岐予測制御モジュールは、第１のＢＴＢにおける第１のアクセスミスに応じて、複数のアクセスミスカウントのうち何れかをインクリメントするように構成されている。別の態様では、分岐予測制御モジュールは、第１のＢＴＢにおける第１のアクセスミス及び第２のＢＴＢにおける第２のアクセスミスに応じて、複数のアクセスミスカウントのうち何れかをインクリメントするように構成されている。更に別の態様では、分岐予測制御モジュールは、第１のＢＴＢにおけるアクセスヒットに応じて、複数のアクセスミスカウントのうち何れかをリセットするように構成されている。更に別の態様では、分岐予測制御モジュールは、第２のＢＴＢから第１のＢＴＢに分岐ターゲットアドレスを転送したことに応じて、複数のアクセスミスカウントのうち何れかをリセットするように構成されている。

いくつかの実施形態では、プロセッサは、分岐予測器を備え、分岐予測器は、分岐命令方向の予測を提供するように構成された第１の複数の分岐方向予測テーブルと、分岐予測制御モジュールと、を備え、分岐予測制御モジュールは、第１の期間に亘る第１の複数の分岐方向予測テーブルの各々の使用を示す第１の使用履歴を識別することと、第１の使用履歴に基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、分岐予測器の予測ウィンドウに対して、第１の複数の分岐方向予測テーブルの第１のサブセットへのアクセスを抑制することと、を行うように構成されている。一態様では、分岐予測制御モジュールは、分岐予測器の複数の予測ウィンドウについて第１の使用履歴を識別することによって、第１の使用履歴を識別するように構成されている。

別の態様では、分岐予測制御モジュールは、複数の予測ウィンドウについての分岐予測誤り率を決定することと、第１の使用履歴及び分岐予測誤り率に基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、によって、第１の複数の分岐方向予測テーブルの第１のサブセットを選択するように構成されている。更に別の態様では、分岐予測制御モジュールは、第１の使用履歴に基づいて、分岐予測器の後続の予測ウィンドウの間に使用されると予期される第１の複数の分岐方向予測テーブルのサブセットを予測することと、予測されたサブセットに基づいて、第１の複数の分岐方向予測テーブルの第１のサブセットを選択することと、によって、第１の複数の分岐方向予測テーブルの第１のサブセットを選択するように構成されている。

いくつかの実施形態では、上記の技術のいくつかの態様は、ソフトウェアを実行する処理システムの１つ以上のプロセッサによって実装されてもよい。ソフトウェアは、非一時的なコンピュータ可読記憶媒体に記憶され、又は、非一時的なコンピュータ可読記憶媒体上で有形に具現化された実行可能命令の１つ以上のセットを含む。ソフトウェアは、１つ以上のプロセッサによって実行されると、上記の技術の１つ以上の態様を実行するように１つ以上のプロセッサを操作する命令及び特定のデータを含むことができる。非一時的なコンピュータ可読記憶媒体は、例えば、磁気若しくは光ディスク記憶デバイス、例えばフラッシュメモリ等のソリッドステート記憶デバイス、キャッシュ、ランダムアクセスメモリ（ＲＡＭ）、又は、他の不揮発性メモリデバイス等を含むことができる。非一時的なコンピュータ可読記憶媒体に記憶された実行可能命令は、ソースコード、アセンブリ言語コード、オブジェクトコード、又は、１つ以上のプロセッサによって解釈若しくは実行可能な他の命令フォーマットであってもよい。

上述したものに加えて、概要説明において説明した全てのアクティビティ又は要素が必要とされているわけではなく、特定のアクティビティ又はデバイスの一部が必要とされない場合があり、１つ以上のさらなるアクティビティが実行される場合があり、１つ以上のさらなる要素が含まれる場合があることに留意されたい。さらに、アクティビティが列挙された順序は、必ずしもそれらが実行される順序ではない。また、概念は、特定の実施形態を参照して説明された。しかしながら、当業者であれば、特許請求の範囲に記載されているような本発明の範囲から逸脱することなく、様々な変更及び変形を行うことができるのを理解するであろう。したがって、明細書及び図面は、限定的な意味ではなく例示的な意味で考慮されるべきであり、これらの変更形態の全ては、本発明の範囲内に含まれることが意図される。

利益、他の利点及び問題に対する解決手段を、特定の実施形態に関して上述した。しかし、利益、利点、問題に対する解決手段、及び、何かしらの利益、利点若しくは解決手段が発生又は顕在化する可能性のある特徴は、何れか若しくは全ての請求項に重要な、必須の、又は、不可欠な特徴と解釈されない。さらに、開示された発明は、本明細書の教示の利益を有する当業者には明らかな方法であって、異なっているが同様の方法で修正され実施され得ることから、上述した特定の実施形態は例示にすぎない。添付の特許請求の範囲に記載されている以外に本明細書に示されている構成又は設計の詳細については限定がない。したがって、上述した特定の実施形態は、変更又は修正されてもよく、かかる変更形態の全ては、開示された発明の範囲内にあると考えられることが明らかである。したがって、ここで要求される保護は、添付の特許請求の範囲に記載されている。

Claims (16)

1. プロセッサ［１００］の命令パイプラインのフェッチステージ［１０２］での実行のために第１の命令アドレス［２１１］をフェッチしたことに応じて、
   前記第１の命令アドレスを含む第１のメモリ領域［２３１］を識別することと、
   前記第１のメモリ領域について、第１の分岐ターゲットバッファ（ＢＴＢ）［１１４］への第１のアクセスミス数［２２８］を識別することと、
   前記第１のアクセスミス数が閾値を超えたことに応じて、前記第１の命令アドレスに対する前記第１のＢＴＢへのアクセスを抑制することと、を含む、
   方法。
2. 前記第１の命令アドレスをフェッチしたことに応じて、第２のＢＴＢ［１１２］にアクセスすることを更に含む、
   請求項１の方法。
3. 前記第１のＢＴＢは、前記第２のＢＴＢのビクティムバッファである、
   請求項２の方法。
4. 前記第１のメモリ領域について前記第１のアクセスミス数を識別することは、複数のアクセスミスカウントを記憶するテーブル［２２５］に基づいて前記第１のアクセスミス数を識別することを含み、前記複数のアクセスミスカウントの各々は、異なるメモリ領域に関連付けられている、
   請求項２の方法。
5. 前記第１のＢＴＢにおける第１のアクセスミスに応じて、前記複数のアクセスミスカウントのうち何れかをインクリメントすることを更に含む、
   請求項４の方法。
6. 前記複数のアクセスミスカウントのうち何れかをインクリメントすることは、前記第１のＢＴＢにおける前記第１のアクセスミス及び前記第２のＢＴＢにおける第２のアクセスミスに応じて、前記複数のアクセスミスカウントのうち何れかをインクリメントすることを含む、
   請求項５の方法。
7. 前記第１のＢＴＢにおけるアクセスヒットに応じて、前記複数のアクセスミスカウントのうち何れかをリセットすることを更に含む、
   請求項６の方法。
8. 前記第２のＢＴＢから前記第１のＢＴＢに分岐ターゲットアドレスを転送したことに応じて、前記複数のアクセスミスカウントのうち何れかをリセットすることを更に含む、
   請求項６の方法。
9. 第１の命令アドレス［２１１］をフェッチする［１０２］ように構成されたフェッチステージを含む命令パイプラインと、
   分岐予測器［１１０］と、を備えるプロセッサ［１００］であって、
   前記分岐予測器は、
   分岐ターゲットアドレスを前記命令パイプラインに提供するように構成された第１の分岐ターゲットバッファ（ＢＴＢ）［１１４］と、
   分岐予測制御モジュール［１２０］と、を備え、
   前記分岐予測制御モジュールは、
   前記第１の命令アドレスを含む第１のメモリ領域［２３１］を識別することと、
   前記第１のメモリ領域について、前記第１のＢＴＢへの第１のアクセスミス数［２２８］を識別することと、
   前記第１のアクセスミス数が閾値を超えたことに応じて、前記第１の命令アドレスに対する前記第１のＢＴＢへのアクセスを抑制することと、
   を行うように構成されている、
   プロセッサ［１００］。
10. 第２のＢＴＢ［１１２］を更に備え、
    前記分岐予測制御モジュールは、前記第１の命令アドレスをフェッチしたことに応じて、前記第２のＢＴＢにアクセスするように構成されている、
    請求項９のプロセッサ。
11. 前記第１のＢＴＢは、前記第２のＢＴＢのビクティムバッファである、
    請求項１０のプロセッサ。
12. 前記分岐予測制御モジュールは、
    複数のアクセスミスカウントを記憶するテーブル［２２５］に基づいて前記第１のアクセスミス数を識別するように構成されており、前記複数のアクセスミスカウントの各々は、異なるメモリ領域に関連付けられている、
    請求項１０のプロセッサ。
13. 前記分岐予測制御モジュールは、
    前記第１のＢＴＢにおける第１のアクセスミスに応じて、前記複数のアクセスミスカウントのうち何れかをインクリメントするように構成されている、
    請求項１２のプロセッサ。
14. 前記分岐予測制御モジュールは、
    前記第１のＢＴＢにおける前記第１のアクセスミス及び前記第２のＢＴＢにおける第２のアクセスミスに応じて、前記複数のアクセスミスカウントのうち何れかをインクリメントするように構成されている、
    請求項１３のプロセッサ。
15. 前記分岐予測制御モジュールは、
    前記第１のＢＴＢにおけるアクセスヒットに応じて、前記複数のアクセスミスカウントのうち何れかをリセットするように構成されている、
    請求項１３のプロセッサ。
16. 前記分岐予測制御モジュールは、
    前記第２のＢＴＢから前記第１のＢＴＢに分岐ターゲットアドレスを転送したことに応じて、前記複数のアクセスミスカウントのうち何れかをリセットするように構成されている、
    請求項１３のプロセッサ。

Images