(57)【要約】  分岐予測サポートを有する各分岐命令は、分岐命令の中のアーキテクチャ指定ビット位置の中で分岐予測ビットを有する。命令キャッシュは、分岐命令が実行される場合に動的に判断される更新された分岐予測ビットで分岐命令を変更することをサポートする。
2013545194.tif 000002
【特許請求の範囲】
【請求項１】
命令キャッシュの中の分岐命令の中にバイモーダル分岐予測ビットを記憶する方法であって、
命令キャッシュからフェッチされた分岐命令の中に記憶されたバイモーダル分岐予測ビットに基づいて、分岐ターゲットアドレスを予測するステップと、
前記分岐命令の実行に応じて、分岐予測精度の評価に基づいて、前記バイモーダル分岐予測ビットを変更するかどうかを判断するステップと、
前記フェッチされた分岐命令の中の前記バイモーダル分岐予測ビットから変更されたバイモーダル分岐予測ビットを前記命令キャッシュの中に記憶するステップとを備える、方法。
【請求項２】
前記バイモーダル分岐予測ビットは、分岐する可能性大、分岐する可能性小、分岐しない可能性小、分岐しない可能性大の分岐予測表示を示すバイモーダル予測子回路からのビットである、請求項1に記載の方法。
【請求項３】
前記バイモーダル予測子回路の最下位ビットは、32ビット分岐命令形式のビットフィールドで使用されないビットに割り当てられ、前記ビットは対応する16ビット分岐命令形式で使用される、請求項2に記載の方法。
【請求項４】
前記バイモーダル予測ビットは、プログラムの分析によって静的に判断され、前記プログラムを実行する前にメモリにロードされた前記分岐命令の中に指定される、請求項1に記載の方法。
【請求項５】
前記分岐命令がフェッチされた後、前記命令フェッチアドレスをパイプラインステージに保存するステップであって、前記命令フェッチアドレスがキャッシュラインアドレス、および前記キャッシュラインアドレスによってアドレス指定されるキャッシュラインにおける前記分岐命令位置のためのオフセットであるステップと、
前記保存されたキャッシュラインアドレスおよび前記キャッシュラインの中のオフセットを、前記変更されたバイモーダル分岐予測ビットを保存するための前記命令フェッチアドレスとして選択するステップとをさらに備える、請求項1に記載の方法。
【請求項６】
前記命令キャッシュはレベル1命令キャッシュである、請求項1に記載の方法。
【請求項７】
前記変更されたバイモーダル分岐予測ビットを有する前記分岐命令でレベル2命令キャッシュを更新するステップをさらに備える、請求項1に記載の方法。
【請求項８】
前記保存された分岐命令の中の前記変更されたバイモーダル分岐予測ビットは、次に前記分岐命令が前記分岐命令の関数に影響を及ぼさずにフェッチされるときに、次の分岐ターゲットアドレスの予測に影響を及ぼす、請求項1に記載の方法。
【請求項９】
前記変更されたバイモーダル分岐予測ビットは、前記変更されたバイモーダル分岐予測ビットを有する前記分岐命令を保存することによって前記命令キャッシュの中に保存される、請求項1に記載の方法。
【請求項１０】
バイモーダル分岐予測ビットを有する分岐命令を命令フェッチアドレスで記憶し、提供するように構成された命令キャッシュと、
前記分岐命令の前記命令フェッチアドレスを保存するように構成されたパイプライン記憶装置と、
前記提供された分岐命令に関連する条件の評価に基づいて、前記バイモーダル分岐予測ビットを変更するかどうかを判断するように構成された予測回路と、
前記命令キャッシュの中の前記保存された命令フェッチアドレスで、前記分岐命令の中に、前記提供された分岐命令の中の前記バイモーダル分岐予測ビットから変更された前記バイモーダル分岐予測ビットを記憶するように構成された書込み制御論理回路とを備える、分岐予測装置。
【請求項１１】
前記書込み制御論理回路は、前記命令キャッシュの中に前記保存された命令フェッチアドレスで、前記フェッチされた分岐命令の中の前記バイモーダル分岐予測ビットから変更された前記バイモーダル分岐予測ビットを有する前記分岐命令をさらに記憶する、請求項10に記載の分岐予測装置。
【請求項１２】
前記分岐命令は比較および分岐命令である、請求項10に記載の分岐予測装置。
【請求項１３】
前記分岐命令はロードおよび分岐命令である、請求項10に記載の分岐予測装置。
【請求項１４】
前記分岐予測回路は、
分岐する可能性大、分岐する可能性小、分岐しない可能性小、分岐しない可能性大の状態を有し、分岐する可能性大を表す3のバイナリカウントで飽和する各々の分岐する分岐のために増加し、分岐しない可能性大を表す0のバイナリカウントで飽和する各々の分岐しない分岐のために減少するように構成された2ビットカウンタをさらに備える、請求項10に記載の分岐予測装置。
【請求項１５】
バイモーダル分岐予測のための方法であって、
実行の間に、条件分岐命令に関連する分岐予測ビットを動的に生成するステップと、
前記動的に生成された分岐予測ビットを、命令キャッシュの中の前記条件分岐命令の中に記憶するステップとを備える、方法。
【請求項１６】
前記条件分岐命令が分岐すると評価する場合に、飽和状態の分岐する可能性大の状態に向かって動く重み付け予測値の現在の状態と次の状態との間で前方移行を行うステップと、
前記条件分岐命令が分岐しないと評価する場合に、飽和状態の分岐しない可能性大の状態に向かって動く前記重み付け予測値の前記現在の状態と次の状態との間で逆方向移行を行うステップとをさらに備える、請求項15に記載の方法。
【請求項１７】
前記重み付け予測値の前記現在の状態と前記次の状態とは、前記条件分岐命令を実行することの分岐する可能性大、分岐する可能性小、分岐しない可能性小、分岐しない可能性大の履歴を表す有限状態機械予測子の状態である、請求項16に記載の方法。
【請求項１８】
前記条件分岐命令によって特定される条件の分岐するまたは分岐しないという解決に基づいてバイモーダル予測回路を調整するステップと、
前記バイモーダル予測回路によって表される前記分岐予測ビットが前記条件分岐命令から復号された前記バイモーダル予測ビットと同じである場合、前記条件分岐命令とともに記憶された前記分岐予測ビットを更新しないことを動的に判断するステップとをさらに備える、請求項15に記載の方法。
【請求項１９】
前記分岐予測ビットは、バイモーダル予測回路の分岐する可能性小の状態を示して、1の最上位ビットおよび0の最下位ビットに最初に設定される、請求項15に記載の方法。
【請求項２０】
前記条件分岐命令のアドレスおよび前記分岐予測ビットを一時的バッファの中に保存するステップと、
前記保存された分岐予測ビットを、前記条件分岐命令によって特定される条件の分岐するまたは分岐しないという解決に基づいて調整されたバイモーダル予測回路値と比較するステップと、
前記動的に判断された分岐予測ビットをどこに記憶するのかを識別するために、前記保存された前記条件分岐命令のアドレスを取り出すステップとをさらに備える、請求項15に記載の方法。
【請求項２１】
前記条件分岐命令は、前記バイモーダル予測ビットを含む固定された命令セットアーキテクチャ形式を有する、請求項15に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、電力および実装複雑性を軽減し、分岐予測をサポートする処理システムにおけるパフォーマンスを向上させるための技法に関し、より詳細には、多重レベルのメモリ階層に記憶された分岐命令の中に分岐予測情報を動的に符号化するための有利な技法に関する。
【背景技術】
【０００２】
携帯電話、ラップトップコンピュータ、携帯情報端末(PDA)などの多くのポータブル製品は、通信およびマルチメディアのアプリケーションをサポートするプログラムを実行する1つまたは複数のプロセッサを組み込む。そのような製品のためのプロセッサは通常、命令キャッシュとデータキャッシュとシステムメモリとを含む多重レベルのキャッシュを備えた階層メモリ構成を有する。このプロセッサはまた、そのような製品のための複数の計算集約的機能をサポートするために、高いパフォーマンスおよび効率で動作しなければならない。このプロセッサは典型的にパイプライン化され、条件分岐命令の実行をサポートする。
【０００３】
パイプライン化されたプロセッサ上で条件分岐命令を実行することは、条件の判断を保留中のパイプラインをストールさせる場合がある。プロセッサをストールさせることを回避するために、典型的には、プロセッサが予測された分岐の挙動に基づいて投機的に命令をフェッチし、実行できるようにする何らかの形式の分岐予測がパイプラインの初期で用いられる。条件分岐が誤って予測された場合、関連する投機的にフェッチされた命令はパイプラインからフラッシュされ、新しい命令が判断された分岐アドレスからフェッチされる。そのような予測ミスはプロセッサのパフォーマンスを減少させ、電力使用量を増加させる。
【０００４】
従来の分岐予測の手法は、実装コスト、およびすべてが電力を消費する分岐予測回路の複雑性のために制限されている。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明は、そのいくつかの態様の中で、実装コストが少なく、電力使用量を減少させる向上した分岐予測機能に対する要求を認識する。上記の目的で、本発明の一実施形態は、分岐命令の中のバイモーダル分岐予測ビットを命令キャッシュの中に記憶する方法を適用する。分岐ターゲットアドレスは、命令キャッシュからフェッチされた分岐命令の中に記憶されたバイモーダル分岐予測ビットに基づいて予測される。分岐命令の実行に応じて、分岐予測精度の評価に基づいてバイモーダル分岐予測ビットを変更するかどうかについて判断がなされる。フェッチされた分岐命令の中のバイモーダル分岐予測ビットから変更されたバイモーダル分岐予測ビットは、命令キャッシュの中に記憶される。
【０００６】
本発明の別の実施形態は、分岐予測装置に対処する。命令キャッシュは、命令フェッチアドレスで、バイモーダル分岐予測ビットを有する分岐命令を記憶し、提供するように構成される。パイプライン記憶装置は、分岐命令の命令フェッチアドレスを保存するように構成される。予測回路は、提供された分岐命令に関連する条件の評価に基づいて、バイモーダル分岐予測ビットを変更するかどうかを判断するように構成される。書込み制御論理回路は、命令キャッシュの中の保存された命令フェッチアドレスで、分岐命令の中に、提供された分岐命令の中のバイモーダル分岐予測ビットから変更されたバイモーダル分岐予測ビットを記憶するように構成される。
【０００７】
本発明の別の実施形態は、バイモーダル分岐予測のための方法に対処する。条件分岐命令に関連する分岐予測ビットは、実行の間に動的に生成される。動的に生成された分岐予測ビットは、命令キャッシュの中の条件分岐命令の中に記憶される。
【０００８】
本発明におけるさらに完全な理解と、本発明におけるさらなる特徴および利点とは、以下の詳細な説明と添付図面より明らかとなろう。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施形態を有利に用いることができる例示的なワイヤレス通信システムのブロック図である。
【図２】本発明によるメモリ階層に記憶された分岐命令の中に符号化されたバイモーダル分岐予測子を記憶するための処理複合体の機能ブロック図である。
【図３】本発明によるバイモーダル分岐予測ビットの動的符号化をサポートする例示的な32ビットおよび16ビットの条件分岐命令形式を示す図である。
【図４】本発明によるプロセッサパイプラインのステージに結合された例示的なレベル1命令キャッシュサブシステムを示す図である。
【図５】本発明によるIキャッシュの分岐命令の中のバイモーダル分岐予測ビットを読み取り、書き込むためのプロセスを示す図である。
【発明を実施するための形態】
【００１０】
次に、本発明におけるいくつかの実施例が示されている添付図面を参照して、本発明についてさらに十分に説明する。しかし、本発明は、様々な形態で実施されてもよく、本明細書に明記された実施形態に限定されるように解釈されるべきではない。むしろ、これらの実施態様は、本開示が徹底的で完全なものとなり、本発明の範囲を当業者に十分に伝えることになるように提供されている。
【００１１】
本発明の教示に基づいて動作するか、もしくは本発明の教示に従う動作を実行するコンピュータプログラムコードまたは「プログラムコード」は、C、C++、JAVA(登録商標)、SmallTalk、JavaScript(登録商標)、Visual Basic(登録商標)、TSQL、Perlなどの高レベルのプログラミング言語、または、様々な他のプログラミング言語で最初は書かれてもよい。これらの言語の1つで書かれたプログラムは、高レベルプログラムのコードをネイティブアセンブラプログラムに変換することによって、ターゲットプロセッサのアーキテクチャにコンパイルされる。また、ターゲットプロセッサのアーキテクチャのためのプログラムは、ネイティブアセンブラ言語で直接書かれてもよい。ネイティブアセンブラプログラムでは、マシンレベルのバイナリ命令における、命令のニーモニック表現が用いられる。本明細書で用いられる場合、プログラムコードまたはコンピュータ可読媒体は、プロセッサがフォーマットを理解できる、オブジェクトコードなどのマシン言語コードを指す。
【００１２】
図1は、本発明の実施形態を有利に用いることができる例示的なワイヤレス通信システム100を示す。図1は、説明のために、3つの遠隔ユニット120、130、および150、ならびに、2つの基地局140を示す。一般的なワイヤレス通信システムは、より多くの遠隔ユニットおよび基地局を有し得ることが理解されよう。コンポーネント125A、125C、125B、および125Dでそれぞれ表されるハードウェアコンポーネント、ソフトウェアコンポーネント、またはその両方を含む遠隔ユニット120、130、150、および基地局140は、さらに後で論じるように、本発明を実施するように適合している。図1は、基地局140から遠隔ユニット120、130、および150への順方向リンク信号180、ならびに、遠隔ユニット120、130、および150から基地局140への逆方向リンク信号190を示している。
【００１３】
図1では、遠隔ユニット120はモバイル電話として示され、遠隔ユニット130はポータブルコンピュータとして示され、遠隔ユニット150は、ワイヤレスローカルループシステムにおける固定位置遠隔ユニットとして示されている。例として、遠隔ユニットは、代替的には、セルフォン、ページャ、ウォーキートーキー、ハンドヘルド個人通信システム(PCS)ユニット、携帯情報端末などのポータブルデータユニット、またはメータ読取り機器などの固定位置データユニットでもよい。図1は、本開示における教示による遠隔ユニットを示しているが、本開示は、これらの例示的に示されたユニットに限定されない。本発明の実施形態は、分岐予測をサポートし、キャッシュを有するメモリ階層をサポートする任意のプロセッサシステムにおいて適切に採用されてもよい。
【００１４】
分岐予測技法は、静的および動的予測のための技法を含んでもよい。いくつかの分岐命令の起こり得る挙動は、プログラマーおよび/またはコンパイラによって静的に予測され得る。たとえば、分岐命令は、ループの初めに前のアドレスに分岐するループ出口評価等の実行時属性に基づいて静的に予測されてもよい。そのような「後方」分岐は通常、ループの中に残されていると予測される。「後方」分岐は、ループが終了する場合、および分岐の後の次の命令に行ってしまうことによって分岐が起こらず、それによってループが終了する場合、誤って予測されることになる。また、特定のプログラムについて、「前方」分岐はめったに起こらないと判断される場合もある。したがって、「後方」分岐は「分岐する(taken)」と静的に予測され、「前方」分岐は「分岐しない(not taken)」と静的に予測される場合がある。
【００１５】
動的予測は一般に、特殊な分岐履歴メモリ回路の中に記憶された特定の分岐の挙動の履歴の評価に基づく。プログラムの分析は一般に、最近の過去の分岐評価パターンが将来の分岐命令の挙動のよい指標になり得ることを示す。単純な分岐履歴の分岐予測子の一例として、複数の1ビットフラグは、各1ビットフラグが条件分岐命令のアドレスに関連して維持されてもよい。各フラグは、関連する条件分岐が「分岐する」と評価する場合に設定され、「分岐しない」と評価する場合には再設定される。次いで、次に生じる条件分岐の予測は単に関連するフラグの値であってもよい。いくつかの分岐命令については、この予測子は正確な予測をもたらし得る。
【００１６】
分岐予測の精度を最大化することに密接に関連した設計目標は、誤った分岐予測の悪影響を最小限に抑えることである。上述の「後方」分岐条件、および1ビットフラグを動的分岐予測子として使用することを考える。プロセッサがループの中にある間、分岐が起こり、関連するフラグはループを通る各サイクルで「1」のままであり、将来の「後方」分岐命令の実行について「分岐する」を予測する。ループが終了する場合、「後方」分岐は「分岐する」として誤って予測され、間違った命令がパイプラインの中にプリフェッチされる。プロセッサは知られている分岐予測ミス回復方法によって誤った分岐予測から回復するが、一方でパフォーマンスの減損を生じさせ、電力を無駄にする。この事象によって、関連する1ビットフラグは「分岐しない」分岐履歴を反映するために再設定される。しかしながら、次の「後方」分岐命令の実行は第1のループのサイクルにある可能性が最も高くなり、「分岐しない」フラグに基づく予測は誤りとなる。このシナリオでは、シングルビットの分岐評価履歴によって、第1のループのサイクルの中で、1つはループ出口の終端において、もう１つは「後方」分岐命令の次に続く実行で、各ループ出口の分岐評価について2つの予測ミスが生じる。
【００１７】
誤って予測された分岐評価の影響を最小限に抑えるための1つの技法は、強いまたは弱い予測を示すための信頼係数によって分岐予測を重み付けすることである。信頼係数は、たとえば、2ビット飽和カウンタの状態によって表される分岐履歴に基づいたバイモーダル分岐予測子によって生成されてもよい。この技法を使用して予測される各分岐のために、個別のカウンタまたは個別の2ビット履歴記憶装置が必要である。各カウンタは、各々が重み付けされた予測値を表す以下のような4つの状態のうちの1つを仮定する:
11-分岐する可能性大と予測される(Strongly predicted taken)
10-分岐する可能性小と予測される(Weakly predicted taken)
01-分岐しない可能性小と予測される(Weakly predicted not taken)
00-分岐しない可能性大と予測される(Strongly predicted not taken)
【００１８】
カウンタは、たとえば、対応する条件分岐命令が「分岐する」と評価するたびに増加し、その命令が「分岐しない」と評価するたびに減少する。増加は、「分岐する可能性大と予測される」状態へ向かう方向の中で移動する2つの状態の間での前方移行であり、減少は、「分岐しない可能性大と予測される」状態へ向かう方向の中で移動する2つの状態の間での逆方向移行である。たとえば、「01」の分岐しない可能性小と予測される状態からの増加は、「10」の分岐する可能性小と予測される状態への前方移行である。この増加/減少は、増加は0b11で止まり、減少は0b00で止まるので「飽和状態」である。したがって、分岐予測は、2ビットの飽和カウンタの出力の最上位ビット(MSB)を検査することによって判断され得るので、分岐するまたは分岐しないという予測だけでなく、カウンタ値の両方のビットを利用する予測の強度また信頼度を示す重み係数も含む。
【００１９】
バイモーダル分岐予測子を実装するための代替技法は、有限状態機械に基づく。個別の有限状態機械予測子は、予測された各分岐のために使用される。有限状態機械予測子は、各々が重み付け予測値を表す以下のような4つの状態のうちの1つを有する:
11-分岐する可能性大と予測される
10-分岐する可能性小と予測される
00-分岐しない可能性小と予測される
01-分岐しない可能性大と予測される
【００２０】
有限状態機械予測子は現在の状態、および関連する条件分岐命令が「分岐する」と評価するかどうかに応じて、重み付け予測値「01」→「00」→「10」→「11」のうちの2つの状態の間で前方移行を行い、「11」で飽和する。有限状態機械予測子は現在の状態、および関連する条件分岐命令が「分岐しない」と評価するかどうかに応じて、重み付け予測値「11」→「10」→「00」→「01」のうちの2つの状態の間で逆方向移行を行い、「00」で飽和する。有限状態機械予測子を用いて、重み付け予測値の最上位ビットはPビットとラベリングされ、重み付け予測値の最下位ビットはQビットとラベリングされ、予測の強度を表す。
【００２１】
上で考察した「後方」分岐命令などの分岐命令は、単一ビットフラグ予測子によって2度予測を誤るのではなく、バイモーダル分岐予測子によって1度だけ予測を誤る。ループ出口での分岐予測は、予測子を「分岐する可能性大」から「分岐する可能性小」に移動する。実際の予測はバイモーダルであり、関連する2ビットカウンタ、または上述の有限状態機械予測子として実装することができるバイモーダル予測子回路のMSBによって表される。したがって、次に生じる「後方」分岐命令は「分岐する」と予測され、これはおそらく正しく、予測子は「分岐する可能性大」の状態に戻る。重み付け予測値のバイナリ値は、範囲の両端ではより高い信頼度で、範囲の中央に向かってはより低い信頼度で、分岐予測信頼度の強度を決定する。
【００２２】
そのようなバイモーダル予測システムを実装するコストは高く、分岐履歴テーブル等、および分岐カウンタまたは有限状態機械予測子を分岐命令のアドレスと関連付けるための手段を必要とする。分岐命令が5から7つの命令ごとに1回発生し得る大規模なプログラムのサポートのために、分岐履歴テーブルは非常に大きくなり得る。
【００２３】
図2は、本発明によるメモリ階層202に記憶された分岐命令の中に符号化されたバイモーダル分岐予測子を記憶するための処理複合体200の機能ブロック図である。処理複合体200は、メモリ階層202および、プロセッサパイプライン206と、制御回路208と、レジスタファイル(RF)210とを有するプロセッサ204を含む。メモリ階層202は、レベル1命令キャッシュ(L1 Iキャッシュ)230と、レベル1データキャッシュ(L1 Dキャッシュ)232と、メモリシステム234とを含む。制御回路208は、プログラムカウンタ(PC)209を含む。処理複合体につながることができる周辺デバイスは、説明を簡潔にするために図示されていない。処理複合体200は、L1 Dデータキャッシュ232に記憶され、より高いレベルのキャッシュおよびメインメモリを含むことができるメモリシステム234と関連付けられたデータを利用して、L1 Iキャッシュ230に記憶されたプログラムコードを実行するために、図1のハードウェアコンポーネント125A〜125Dにおいて好適に用いることができる。プロセッサ204は、汎用プロセッサ、マルチスレッドプロセッサ、デジタル信号プロセッサ(DSP)、特定用途向けプロセッサ(ASP)等であってもよい。処理複合体200における様々なコンポーネントは、特定用途向け集積回路(ASIC)の技術、フィールドプログラマブルゲートアレイ(FPGA)の技術、または他のプログラマブルロジック、ディスクリートゲートもしくはトランジスタロジック、または意図されるアプリケーションに適した任意の他の利用可能な技術を用いて実現することができる。
【００２４】
プロセッサパイプライン206は、たとえば、命令フェッチステージ214と、予測論理回路217とバイモーダル予測子回路218とを有する復号および予測ステージ216と、ディスパッチステージ219と、リードレジスタステージ220と、実行ステージ222と、ライトバックステージ224とである、6つの主要ステージを含む。単一のプロセッサパイプライン206が図示されているが、本発明のメモリ階層202と復号および予測ステージ216とを使用する命令の処理は、スーパースカラの設計、および並列パイプラインを実装している他のアーキテクチャに適用可能である。たとえば、高いクロックレート用に設計されたスーパースカラプロセッサは、複数のスレッドをサポートする2つ以上の並列パイプラインを有することができ、各パイプラインは、命令フェッチステージ214と、復号ステージ216と、ディスパッチステージ219と、リードレジスタステージ220と、実行ステージ222と、ライトバックステージ224とを、2つ以上のパイプライン化されたステージに分割して、高いクロックレートをサポートするために全体的なプロセッサパイプラインの深さを増すことができる。また、設計、実装または他の理由のために、予測論理回路217とバイモーダル予測子回路218とは、たとえば制御回路208の中など、プロセッサ204の中の他の場所に配置することができる。
【００２５】
プロセッサパイプライン206の第1のステージで始めると、プログラムカウンタ(PC)209と関連する命令フェッチステージ214は、後段のステージによる処理のためにL1 Iキャッシュ230から命令をフェッチする。L1 Iキャッシュ230において命令フェッチがミスする場合、これは、フェッチされる命令がL1 Iキャッシュ230に存在しないことを意味し、命令は、レベル2(L2)のキャッシュなどのマルチレベルのキャッシュとメインメモリとを含み得るメモリシステム234からフェッチされる。命令は、ブートリードオンリーメモリ(ROM)、ハードドライブ、光ディスクなどの他のソース、または、ネットワークなどの外部インターフェースからメモリシステム234にロードされてもよい。次いで、フェッチされた命令は復号ステージ216で復号される。
【００２６】
ディスパッチステージ219は1つまたは複数の復号された命令を取り出し、それらを1つまたは複数の命令パイプラインにディスパッチする。リードレジスタステージ220は、RF210からデータオペランドをフェッチする。実行ステージ222はディスパッチされた命令を実行し、ライトバックステージ224は結果をRF210に書き込む。実行ステージ222からの結果オペランドは、条件分岐命令によって使用される条件を判断するために、複数の実行サイクルを行ってもよい。これらのサイクルの間、プロセッサパイプライン206は結果オペランドが利用可能になるまで待機しなければならない。結果は、プログラムの順序と比較して順不同でライトバックステージ224において受信され得るため、ライトバックステージ224は、結果をRF210に書き込む場合には、プロセッサの機能を使ってプログラムの順序を保つ。
【００２７】
処理複合体200は、コンピュータ可読記憶媒体に記憶されたプログラムにおける制御のもとで命令を実行するように構成することができる。たとえば、コンピュータ可読記憶媒体は、L1 Dキャッシュ232およびメモリシステム234から得られるデータに基づく動作に向けて、処理複合体200とローカルに直接関連付けられていてもよく、たとえば、L1 Iキャッシュ230から利用可能なものでもよく、または、たとえば、入力/出力インターフェース(図示せず)を介するものでもよい。L1 Iキャッシュ230からフェッチされた条件分岐命令(C分岐)は、命令フェッチステージ214で受信される。L1 Iキャッシュ230のC分岐とともに動的に記憶されたバイモーダル予測ビットは、フェッチされた条件分岐命令が行われるべきか、または行われないべきかどうかを予測するために、復号および予測ステージ216で取り出され、使用される。さらに、命令は予測に基づいて投機的にフェッチされてもよい。C分岐が実行ステージ222にある場合、条件が判断され、バイモーダル予測子回路218は予測信号223を介して、C分岐に分岐する場合にはバイモーダル予測子の状態の前方移行を行うように通知され、C分岐に分岐しない場合にはバイモーダル予測子の状態の逆方向移行を行うように通知される。次いで、更新されたバイモーダル予測子回路218の状態は、L1 Iキャッシュ230の中の次に利用可能な書込みサイクルの関連するC分岐の中にバイモーダル予測ビットを記憶するために、バイモーダルビット信号240を介して渡される。記憶されたC分岐命令の中の変更されたバイモーダル分岐予測ビットは、次にC分岐命令がC分岐命令の関数に影響を及ぼさずにフェッチされるときに、次の分岐ターゲットアドレスの予測に影響を及ぼす。L1 Iキャッシュ230を使用するプロセッサパイプライン206と、復号および予測ステージ216のより詳細な説明は、詳細なコード例とともに以下に示される。
【００２８】
図3は、本発明によるバイモーダル分岐予測ビットの動的符号化をサポートする例示的な32ビットおよび16ビットの条件分岐命令形式302および304をそれぞれ示す図である。32ビット条件分岐命令形式302は、第1の条件コード選択フィールド306と、第1の命令コード308と、予測ビット310と、24ビット署名付きオフセット312と、Qビット314とを含む。16ビットの条件分岐命令形式304は、第2の命令コード320と、第2の条件コード選択フィールド322と、ハーフワードアドレス境界上の16ビット命令のアドレスを識別するための8ビット署名付きオフセット324とを含む。
【００２９】
予測ビット310などの条件分岐命令の中の予測ビットは、プログラムをロードする前に静的に判断される。たとえば、後方分岐命令の24ビット署名付きオフセットフィールド312から判断された後方分岐は、Pビット310を1の値にアサートすることによって、コンパイラによって「分岐する」と予測されてもよい。バイモーダル予測子回路218の有限状態機械実装を用いて、Qビット314は可能性大の予測を示すために1の値に設定されてもよい。代替的に、Qビット314は可能性小の予測を示すためにゼロ値に設定されてもよい。たとえば、Qビット314のための初期またはデフォルト設定はゼロであってもよい。代替実施形態では、バイモーダル予測ビットの両方は、プログラムの分析によって静的に判断され、プログラムを実行する前に分岐命令の中に指定されてもよい。たとえば、ループバック機能として使用される条件分岐(C分岐)命令を備えたプログラムコンテキストの中で、Pビット310は「1」に設定されてもよく、Qビット314は分岐する可能性小の状態を示して「0」に設定されてもよい。ループを回る第1のサイクルで、C分岐命令は分岐すると予測される可能性が最も高く、また分岐すると評価される可能性が最も高い。分岐するという評価によって、バイモーダル予測子回路は「11」の分岐する可能性大の状態に進む。
【００３０】
バイモーダル予測子回路218の2ビット飽和カウンタ実装を用いて、分岐するまたは分岐しないという予測は、2ビット飽和カウンタ出力の最上位ビット(MSB)を検査することによって判断されてもよい。予測の強度または信頼度は、カウンタ値の両方のビットを検査することによって作られてもよい。たとえば、2ビット飽和カウンタの出力排他的論理和否定(¬XOR)は予測の強度のバイナリ表示を提供し、そこで「1」は可能性大の予測を示し、「0」は可能性小の予測を示す。上述のような2ビット飽和カウンタの重み付け予測値を使用することによって、「10」の分岐する可能性小と予測される状態、または「01」の分岐しない可能性小と予測される状態などの所望の状態を選び、プログラムをロードする前に条件分岐命令の中に最初に設定することができる。バイモーダル予測子回路218の両方のビットは、重み付け予測値の状態の変化を判断するために検査される。
【００３１】
予測ビット310およびQビット314は、条件分岐命令に関連するバイモーダル予測子回路の最上位ビット(MSB)および最下位ビット(LSB)によってそれぞれ動的に判断される。条件分岐命令は、第1の命令コード308の符号化によって復号の間に識別されてもよい。Qビット314は、32ビット条件分岐命令形式302のビット0位置に配置される。アドレスのビット0位置は一般に、ハーフワードアドレス境界上の16ビット命令を識別するために16ビットおよび32ビット命令を有するプロセッサの中で使用される。しかしながら、定義上、すべての32ビット命令はワード単位で整列され、ビット0は16ビットのアドレスビットを表すので、ビット0位置は32ビット条件分岐命令形式302の中でアドレッシング目的のために使用されることはない。代替的に、Qビットは、各条件分岐命令のために個別のアレイの中に記憶されてもよく、一方で予測ビットは条件分岐命令の中に記憶されたままである。
【００３２】
図4は、本発明によるプロセッサパイプライン206のステージに結合された例示的なレベル1命令キャッシュ(L1 Iキャッシュ)サブシステム400を示す図である。L1 Iキャッシュサブシステム400は、L1 Iキャッシュ230と、プロセッサパイプライン206の複数のステージとを含む。L1 Iキャッシュ230は、命令連想メモリ(ICAM)402と、命令ランダムアクセスメモリ(IRAM)403と、書込み制御論理404とを含む。
【００３３】
命令がフェッチされる場合、プロセッサパイプライン206の命令フェッチステージ214は、L1 Iキャッシュ230のICAM402で受信されるフェッチアドレス408を発行する。フェッチアドレス408は、たとえば、キャッシュラインアドレス、およびキャッシュラインアドレスによってアドレス指定されるキャッシュラインの中の分岐命令位置のためのオフセットを含む。フェッチアドレス408は、フェッチアドレス408の命令がキャッシュのIRAM403の中で発見されるかどうかを判断するために、ICAM402の中のエントリと比較される。ICAM402の中で一致することが判断されると、ICAM402の中の一致するエントリに関連するIRAM403の中のラインを選択するために、ヒット表示410が生成される。たとえば、第1の命令(命令1)414と、Pビット417とQビット418とを有する条件分岐命令(C分岐)416と、追加命令420とを含む命令ライン412が選択されてもよい。
【００３４】
選択された命令ライン412は、L1 Iキャッシュ230の出力424に向けられ、命令フェッチステージ214で受信される。C分岐416のためのプロセッサパイプライン206の次のステージで、復号および予測ステージ216は、C分岐416が分岐するのか、または分岐しないのかどうかを予測するためにPビット417とQビット418とを使用する。予測に基づいて、PC209は相応に調整され、命令フェッチステージ214は分岐するまたは分岐しないアドレスで次のフェッチアドレスを生成する。C分岐416のアドレス、ならびに予測Pビット417およびQビット418は、条件判断の後のその後の検査のためにパイプラインバッファ421の中に記憶される。
【００３５】
C分岐416は、たとえばディスパッチステージ219、リードレジスタステージ220を通ってプロセッサパイプライン206を下り続け、条件が判断される実行ステージ222に達する。予測信号223は、条件が「分岐する」を示す場合にはバイモーダル予測子回路(BP)218の中で前方移行を行うように、条件が「分岐しない」を示す場合にはBP218の中で逆方向移行を行うように復号および予測ステージ216に通知する。次いで、復号および予測ステージ216は、BP218から選択されたバイモーダル分岐ビットをバイモーダルビット信号240を介して書込み制御論理404へ渡す。最新のバイモーダル分岐ビット値が以前のPビット417およびQビット418の値と異なる場合、書込み制御論理404によって最新のPビットおよびQビット値は、関連するPビットおよびQビット値を更新することによってL1 Iキャッシュ230の中のC分岐命令416に記憶される。したがって、以前のPビット417および以前のQビット418の値は置き換えられてもよい。たとえば、PビットおよびQビットの最新版は内部信号430を介して渡され、命令ライン412の中のC分岐位置にロードされてもよい。代替手法では、PビットおよびQビットの最新版によって更新された、フェッチされたC分岐命令は、内部信号430を介して渡され、命令ライン412の中のC分岐位置にロードされてもよい。内部信号428および432は、命令キャッシュラインの中の他の命令位置に関連付けられ、それらの位置に記憶され得る条件分岐命令のアクセスをサポートする。条件分岐命令がIキャッシュから読み取られるときから分岐予測情報がIキャッシュにライトバックされるまでの間の時間に、IキャッシュラインがIキャッシュから置き換えられている場合、分岐予測情報はフラッシュされ、キャッシュは更新されない。
【００３６】
C分岐命令がL1 Iキャッシュ230の中で発見されない場合、ミスが示され、フェッチアドレスはメモリ階層の中の次のレベルのメモリに転送される。たとえば、統合レベル2キャッシュ(L2キャッシュ)を使用してもよい。L2キャッシュの中にヒットがある場合、L2キャッシュからアクセスされたC分岐命令は、ローディングのためにL1 Iキャッシュ230に転送され、並行してプロセッサパイプライン206の命令フェッチステージ214に転送される。C分岐のためのバイモーダル予測ビットに対する更新を判断すると、L1 Iキャッシュ230の中のC分岐は、PビットおよびQビットの最新値で動的に更新される。たとえば、L1 Iキャッシュが単一ポートデバイスである場合、C分岐命令の更新は、L1 Iキャッシュが一般にその更新に勝るプライオリティを有するフェッチング命令であればストールされてもよい。L1 Iキャッシュが2ポートデバイスである場合、C分岐命令の更新は、命令が第2のポートを使用してIキャッシュからフェッチされる間に1つのポートを使用して実行されてもよい。分岐予測情報はまた、C分岐命令を有するキャッシュラインがL1 Iキャッシュの中に存在する場合でもL2キャッシュに転送される。L1ラインが、たとえば最長時間未使用法(LRU)などの置換ポリシーに基づいて置換される場合、その後次にL2キャッシュからラインがフェッチされるとき、L2キャッシュラインはすでに更新されているために、L2キャッシュの中の記憶されたC分岐命令から最新予測情報が利用可能になる。別の手法では、L1 Iキャッシュが分岐情報によって更新される場合、C分岐命令を有する命令ラインに関連するタグの中ダーティビットが設定される。L1 Iキャッシュの中のダーティラインが置換されると、その後古いダーティラインはL2キャッシュの中で更新される。
【００３７】
図示する例示的なパイプライン206のために、4つのバイモーダル予測子回路は、パイプラインの中の4つの連続する条件分岐の可能性を配慮するために復号および予測ステージ216に配置されてもよい。バイモーダル予測子回路の数は、パイプラインの深さによって変化する。より深いパイプラインについては、4つよりも多くのバイモーダル予測子回路が必要であり、必要に応じて、「n」をパイプラインの深さによってサポートされるよりも少ない数として「n」個のバイモーダル予測子回路を実装してもよい。そのような場合、「n+1」の条件分岐命令を受信すると、そのような分岐には利用可能な予測サポートがなく、ストールする。たとえば、予測された分岐ターゲットアドレスでの投機的アクセスは、「n+1」分岐のための条件が判断されるときに分岐ターゲットアドレスを生成できるようになるまでストールされる。
【００３８】
たとえば、各条件分岐命令に関連するバイモーダルカウンタを使用する分岐予測は、典型的に、バイモーダルカウンタビット、および関連する条件分岐命令のための対応値を保存するために、個別の分岐予測アレイを有する予測論理回路を使用する。回路要件によって容量が制約されるような分岐予測アレイは、本発明では必要ではない。したがって、分岐予測の有効性を維持しながら、本発明によるハードウェア回路実装は減らされる。また、本明細書で説明する分岐予測は各分岐命令とともにバイモーダル予測情報を記憶することができ、分岐予測アレイによって容量を制限されることはない。したがって、電力使用量は、分岐予測アレイを使用する手法と比較して最小化される。
【００３９】
図5は、本発明によるIキャッシュの中の分岐命令の中のバイモーダル分岐予測ビットを読み取り、書き込むためのプロセスを示す。実装の詳細を強調し、明確にするために、前の図面を参照する。第1のステップ502で、プログラムは処理複合体200上で開始する。また、プロセス500はプロセッサパイプライン206を通るときに、1つの条件分岐命令の経路をたどる。
【００４０】
ステップ504で、命令はL1 Iキャッシュ230からフェッチされる。決定ステップ506で、フェッチされた命令が条件分岐(C分岐)命令であるかどうかが判断される。フェッチされた命令がC分岐命令ではない場合、プロセス500はステップ504に戻る。フェッチされた命令がC分岐命令である場合、プロセス500はステップ508に進む。
【００４１】
ステップ508で、フェッチされたC分岐命令は復号および予測ステージ216で復号され、バイモーダル予測ビットは条件分岐命令から選択される。ステップ510で、C分岐命令のフェッチアドレスおよび選択されたバイモーダル予測ビットは、図5のパイプラインバッファ421に保存される。ステップ512で、バイモーダル予測ビットに基づいて分岐ターゲットアドレスが予測される。決定ステップ514で、フェッチアドレスが更新されるべきかどうかが判断される。フェッチアドレスが予測された分岐ターゲットアドレスに変更されなければならない場合、プロセス500はステップ516へ進む。ステップ516で、命令フェッチステージ214で使用されたフェッチアドレスは、ステップ504で予測された分岐ターゲットアドレスに基づいて命令をフェッチするために投機的に更新され、プロセス500はステップ518へ進む。決定ステップ514に戻ると、フェッチアドレスが変更される必要がない場合、プロセス500はステップ518へ進む。
【００４２】
ステップ518で、C分岐命令のための条件は、たとえば実行ステージ222で判断され、プロセス500は並行して決定ステップ520および521へ進む。ステップ518で判断された条件は、バイモーダル分岐予測の精度を判断するために使用される。決定ステップ520で、C分岐命令が誤って予測されたかどうかが判断される。C分岐命令が誤って予測されていた場合、プロセス500はステップ522へ進む。ステップ522で、プロセッサパイプライン206はフラッシュされ、フェッチアドレスは修正されたフェッチアドレスに設定される。C分岐命令が誤って予測されていなかった場合、プロセス500はステップ524へ進む。ステップ524で、プロセスパイプライン206は通常のパイプ動作を続ける。
【００４３】
決定ステップ521で、条件が、C分岐命令が分岐すると評価したことを示すかどうかが判断される。C分岐命令が分岐すると評価しない、言い換えれば分岐しないと評価した場合、プロセス500はステップ526へ進む。ステップ526で、バイモーダル予測子回路は、「00」のバイモーダル予測値で飽和する予測値で逆方向で調整され、プロセス500は決定ステップ530へ進む。決定ステップ520に戻ると、C分岐命令が分岐すると評価される場合、プロセス500はステップ528へ進む。ステップ528で、バイモーダル予測子回路は、「11」のバイモーダル予測値で飽和する予測値で前方向で調整され、プロセス500は決定ステップ530へ進む。
【００４４】
決定ステップ530で、バイモーダル予測子回路ビットが、フェッチされたC分岐命令から選択されたバイモーダル予測ビットと異なるかどうかが判断される。バイモーダル予測子回路ビットがフェッチされたC分岐命令から選択されたバイモーダル予測ビットと同じである場合、プロセス500はステップ504へ進む。バイモーダル予測子回路ビットがC分岐命令のバイモーダル予測ビットと異なる場合、プロセス500はステップ532へ進む。ステップ532で、C分岐命令とともにL1 Iキャッシュに記憶されたバイモーダル予測ビットは、利用可能なIキャッシュ書込みサイクルで更新される。次いで、プロセス500はステップ504へ進む。
【００４５】
本明細書で開示する実施形態に関して説明する方法は、ハードウェアの組合せにおいて、およびプロセッサによって実行される非一時的信号を記憶するソフトウェアモジュールにおいて具現化することができる。ソフトウェアモジュールは、ランダムアクセスメモリ(RAM)、フラッシュメモリ、読取り専用メモリ(ROM)、電気的プログラマブル読取り専用メモリ(EPROM)、ハードディスク、リムーバブルディスク、テープ、コンパクトディスク読取り専用メモリ(CD-ROM)、または、当技術分野で既知の任意の他の形態の記憶媒体中に常駐し得る。記憶媒体は、プロセッサがその記憶媒体から情報を読み取り、場合によってはその記憶媒体に情報を書き込むことができるようにプロセッサに結合され得る。プロセッサに結合している記憶媒体は回路実装と一体の直接結合であってもよく、直接アクセス、またはダウンローディング技法を使用したデータストリーミングをサポートする1つまたは複数のインターフェースを利用してもよい。
【００４６】
本発明が、プロセッサシステムにおいて使用するための例示的な実施形態の場合において開示されたが、上記の説明および添付の特許請求の範囲と矛盾することのない非常に様々な実装形態が当業者によって利用され得ることが理解されよう。本技法は、レベル3キャッシュおよびメインメモリを含むすべてのレベルのメモリ階層に対してスケーラブルである。また、条件分岐命令は、単一の比較分岐命令の中の比較命令と組み合わせられてもよい。単一の比較分岐命令は、比較分岐命令の命令形式の中のバイモーダル分岐予測ビットを含む。たとえば、命令形式の中の未使用ビットはバイモーダル分岐予測ビットのために使用されてもよい。さらに、条件分岐命令は単一のロードの中のロード命令、および同じくバイモーダル分岐予測ビットを含む分岐命令と組み合わせられてもよい。
【符号の説明】
【００４７】
100  ワイヤレス通信システム
120、130、150  遠隔ユニット
140  基地局
125A、125C、125B、125D  コンポーネント
180  順方向リンク信号
190  逆方向リンク信号
200  処理複合体
202  メモリ階層
204  プロセッサ
206  プロセッサパイプライン
208  制御回路
209  プログラムカウンタ(PC)
210  レジスタファイル(RF)
214  フェッチステージ
216  復号および予測ステージ
217  予測論理回路
218  バイモーダル予測子回路
219  ディスパッチステージ
220  リードレジスタステージ
222  実行ステージ
224  ライトバックステージ
230  レベル1命令キャッシュ(L1 Iキャッシュ)
232  レベル1データキャッシュ(L1 Dキャッシュ)
234  メモリシステム
125A〜125D  ハードウェアコンポーネント
302  32ビット条件分岐命令形式
304  16ビット条件分岐命令形式
306  第1の条件コード選択フィールド
308  第1の命令コード
310  予測ビット、Pビット
312  24ビット署名付きオフセット
314  Qビット
320  第2の命令コード
322  第2の条件コード選択フィールド
324  8ビット署名付きオフセット
400  レベル1命令キャッシュ(L1 Iキャッシュ)サブシステム
402  命令連想メモリ(ICAM)
403  命令ランダムアクセスメモリ(IRAM)
404  書込み制御論理
408  フェッチアドレス
410  ヒット表示
412  命令ライン
414  第1の命令(命令1)
416  条件分岐命令(C分岐)
417  Pビット
418  Qビット
420  追加命令
421  パイプラインバッファ
424  出力
428、430、432  内部信号
500  プロセス
【図１】
2013545194.tif 000003
【図２】
2013545194.tif 000004
【図３】
2013545194.tif 000005
【図４】
2013545194.tif 000006
【図５】
2013545194.tif 000007
【手続補正書】
【提出日】平成25年5月28日(2013.5.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
命令キャッシュの中の分岐命令の中に重み付けバイモーダル分岐予測ビットを記憶する方法であって、
命令キャッシュ(230、504)からフェッチされた分岐命令(416、506)の中に記憶された重み付けバイモーダル分岐予測ビット(Pビット310、417およびQビット314、418)に基づいて、予測される分岐ターゲットアドレスを判断するために分岐ターゲットアドレスを予測する(218)ステップ(512)であって、前記重み付けバイモーダル分岐予測ビットの最上位ビット(310、417)が分岐するまたは分岐しないという予測を示し、前記重み付けバイモーダル分岐予測ビットの最下位ビット(314、418)が可能性大または可能性小の予測を示し、命令フェッチアドレスが前記予測される分岐ターゲットアドレスに対して投機的に更新されるステップと、
前記分岐命令の実行に応じて、分岐予測精度の評価に基づいて、前記重み付けバイモーダル分岐予測ビットを変更するかどうかを判断するステップ(530)と、
前記フェッチされた分岐命令の中の前記重み付けバイモーダル分岐予測ビットから変更された重み付けバイモーダル分岐予測ビットを前記命令キャッシュの中に記憶するステップ(532)とを特徴とする、方法。
【請求項２】
前記重み付けバイモーダル分岐予測ビットは、11分岐する可能性大、10分岐する可能小、00分岐しない可能性小、01分岐しない可能性大の分岐予測表示を示す有限状態機械予測子回路からのビットである、請求項1に記載の方法。
【請求項３】
前記重み付けバイモーダル分岐予測ビットの前記最下位ビットは、32ビット分岐命令形式のビットフィールドで使用されないビットに割り当てられ、前記ビットは対応する16ビット分岐命令形式のビットフィールドで代替目的のために使用される、請求項1に記載の方法。
【請求項４】
前記重み付けバイモーダル予測ビットは、プログラムの分析によって静的に判断され、前記プログラムを実行する前にメモリにロードされた前記分岐命令の中で特定される、請求項1に記載の方法。
【請求項５】
前記分岐命令がフェッチされた後、前記命令フェッチアドレスをパイプラインステージに保存するステップであって、前記命令フェッチアドレスがキャッシュラインアドレス、および前記キャッシュラインアドレスによってアドレス指定されるキャッシュラインにおける前記分岐命令位置の中のオフセットであるステップと、
前記保存されたキャッシュラインアドレスおよび前記キャッシュラインの中のオフセットを、前記変更された重み付けバイモーダル分岐予測ビットを保存するための前記命令フェッチアドレスとして選択するステップとをさらに備える、請求項1に記載の方法。
【請求項６】
前記命令キャッシュはレベル1命令キャッシュである、請求項1に記載の方法。
【請求項７】
前記変更された重み付けバイモーダル分岐予測ビットを有する前記分岐命令でレベル2命令キャッシュを更新するステップをさらに備える、請求項1に記載の方法。
【請求項８】
前記保存された分岐命令の中の前記変更された重み付けバイモーダル分岐予測ビットは、次に前記分岐命令が前記分岐命令の関数に影響を及ぼさずにフェッチされるときに、次の分岐ターゲットアドレスの予測に影響を及ぼす、請求項1に記載の方法。
【請求項９】
前記変更された重み付けバイモーダル分岐予測ビットは、前記変更された重み付けバイモーダル分岐予測ビットを有する前記分岐命令を記憶することによって前記命令キャッシュの中に記憶される、請求項1に記載の方法。
【請求項１０】
重み付けバイモーダル分岐予測ビットを有する分岐命令(416)を命令フェッチアドレス(408)で記憶し、提供するように構成された命令キャッシュ(230)であって、前記分岐命令が重み付けバイモーダル分岐予測ビット(Pビット417、Qビット418)を有し、前記重み付けバイモーダル分岐予測ビットの最上位ビット(417)が分岐するまたは分岐しないという予測を示し、前記重み付けバイモーダル分岐予測ビットの最下位ビット(418)が可能性大または可能性小の予測を示す命令キャッシュ(230)と、
前記分岐命令の前記命令フェッチアドレスを保存するように構成されたパイプライン記憶装置(421)と、
前記提供された分岐命令に関連する条件の評価に基づいて、前記重み付けバイモーダル分岐予測ビットを変更するかどうかを判断するように構成されたパイプライン回路(218)と、
前記命令キャッシュの中の前記保存された命令フェッチアドレスで、前記分岐命令の中に、前記提供された分岐命令の中の前記重み付けバイモーダル分岐予測ビットから変更された前記重み付けバイモーダル分岐予測ビットを記憶するように構成された書込み制御論理回路(404)とを特徴とする、分岐予測装置。
【請求項１１】
前記書込み制御論理回路は、前記命令キャッシュの中に前記保存された命令フェッチアドレスで、前記フェッチされた分岐命令の中の前記重み付けバイモーダル分岐予測ビットから変更された前記重み付けバイモーダル分岐予測ビットを有する前記分岐命令をさらに記憶する、請求項10に記載の分岐予測装置。
【請求項１２】
前記分岐命令は比較および分岐命令である、請求項10に記載の分岐予測装置。
【請求項１３】
前記分岐命令はロードおよび分岐命令である、請求項10に記載の分岐予測装置。
【請求項１４】
前記分岐予測回路は、
最上位カウンティングビットと最下位カウンティングビットと前記2つのカウンティングビットのNOT XOR関数とを有する2ビットカウンタ回路をさらに備え、前記最上位カウンティングビットが前記重み付けバイモーダル分岐予測ビットの前記最上位ビットであり、前記NOT XOR関数の出力が前記重み付けバイモーダル分岐予測ビットの前記最下位ビットであり、前記重み付けバイモーダル分岐予測ビットが11分岐する可能性大、10分岐する可能性小、00分岐しない可能性小および01分岐しない可能性大の状態を有し、前記2ビットカウンタ回路が各々の分岐する分岐のために増加し、各々の分岐しない分岐のために減少するように構成される、請求項10に記載の分岐予測装置。
【請求項１５】
バイモーダル分岐予測のための方法であって、
実行の間に、条件分岐命令(416、521)に関連する重み付け分岐予測ビット(218、526、528)を動的に生成するステップであって、第1の重み付け分岐予測ビット(Pビット417)が分岐するまたは分岐しないという予測を示し、第2の重み付け分岐予測ビット(Qビット418)が可能性大または可能性小の予測を示すステップと、
前記動的に生成された重み付け分岐予測ビットを、命令キャッシュ(230)の中の前記条件分岐命令の中に記憶するステップ(532)とを特徴とする、方法。
【請求項１６】
前記条件分岐命令が分岐すると評価する場合に、飽和状態の分岐する可能性大の状態に向かって動く前記重み付け分岐予測ビットの現在の状態と次の状態との間で前方移行を行うステップと、
前記条件分岐命令が分岐しないと評価する場合に、飽和状態の分岐しない可能性大の状態に向かって動く前記重み付け分岐予測ビットの前記現在の状態と次の状態との間で逆方向移行を行うステップとをさらに備える、請求項15に記載の方法。
【請求項１７】
前記重み付け分岐予測ビットの前記現在の状態と前記次の状態とは、前記条件分岐命令を実行することの11分岐する可能性大、10分岐する可能性小、00分岐しない可能性小、01分岐しない可能性大の履歴を表す有限状態機械予測子の状態である、請求項16に記載の方法。
【請求項１８】
前記条件分岐命令によって特定される条件の分岐するまたは分岐しないという解決に基づいてバイモーダル予測回路を調整するステップと、
前記バイモーダル予測回路によって表される前記重み付け分岐予測ビットが前記条件分岐命令から復号された前記重み付け分岐予測ビットと同じである場合、前記条件分岐命令とともに記憶された前記重み付け分岐予測ビットを更新しないことを動的に判断するステップとをさらに備える、請求項15に記載の方法。
【請求項１９】
前記重み付け分岐予測ビットは、バイモーダル予測回路の分岐する可能性小の状態を示して、1の最上位ビットおよび0の最下位ビットに最初に設定される、請求項15に記載の方法。
【請求項２０】
前記条件分岐命令のアドレスおよび前記重み付け分岐予測ビットを一時的バッファの中に保存するステップと、
前記保存された重み付け分岐予測ビットを、前記条件分岐命令によって特定される条件の分岐するまたは分岐しないという解決に基づいて調整されるバイモーダル予測回路値と比較するステップと、
前記動的に判断された重み付け分岐予測ビットをどこに記憶するのかを識別するために、前記保存された前記条件分岐命令のアドレスを取り出すステップとをさらに備える、請求項15に記載の方法。
【請求項２１】
前記条件分岐命令は、前記重み付け分岐予測ビットを含む固定された命令セットアーキテクチャ形式を有する、請求項15に記載の方法。
【国際調査報告】
2013545194.tif 000008
2013545194.tif 000009