(57)【要約】第２のブロックのセット［３１０、３１５］の分岐予測構造［５００］のエントリのセットは、第１のブロック［３０５］の第１のアドレスに基づいてアクセスされる。第２のブロックのセットは、第１のブロックの１つ以上の第１の分岐命令の結果に対応する。第２のブロックにおける第２の分岐命令の結果の投機的予測は、分岐予測構造のエントリに基づいて開始される。投機的予測に関連付けられる状態は、分岐命令のタイプに基づいて選択的にフラッシュされる。【選択図】図８
2021527892.tif 000002
【特許請求の範囲】
【請求項１】
第１のブロック［３０５］の第１のアドレスに基づいて、前記第１のブロックにおける少なくとも１つの第１の分岐命令［３２０］の結果に対応する第２のブロックのセット［３１０，３１５］の分岐予測構造［５００］のエントリのセットにアクセスすることと、
前記分岐予測構造の前記エントリのセットに基づいて、前記第２のブロックのセットにおける第２の分岐命令［３２５，３３５］の結果の投機的予測を開始することと、
前記少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、前記投機的予測に関連付けられる状態を選択的にフラッシュすることと、
を含む、方法。
【請求項２】
前記分岐予測構造の前記エントリのセットにアクセスすることは、前記少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは前記少なくとも１つの第１の分岐命令を受け入れない場合は前記第１のブロックに続くブロックのための前記分岐予測構造のエントリのセットにアクセスすることを含む、請求項１に記載の方法。
【請求項３】
前記第２のブロックのセットにおける前記第２の分岐命令の前記結果の前記投機的予測と同時に、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプ［７１０］を決定することをさらに含む、請求項１に記載の方法。
【請求項４】
前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定することは、前記少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定することを含む、請求項３に記載の方法。
【請求項５】
前記状態を選択的にフラッシュすることは、前記分岐命令のタイプのセットの第１のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答して、前記第２の分岐命令の前記結果の前記投機的予測に関連付けられる前記状態をフラッシュすることを含む、請求項１に記載の方法。
【請求項６】
前記第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む、請求項５に記載の方法。
【請求項７】
前記予測された第２のブロックの第２のアドレスによってインデックス化される前記分岐予測構造のエントリに基づいて、前記第２のブロックの予測された第２のブロックにおける前記第２の分岐命令の少なくとも１つの投機的予測を再開することをさらに含む、請求項５に記載の方法。
【請求項８】
前記予測された第２のブロックは、前記第１のブロックにおける前記少なくとも１つの第１の分岐命令の予測された結果に対応する、請求項７に記載の方法。
【請求項９】
前記状態を選択的にフラッシュすることは、前記状態をフラッシュすることをバイパスし、前記分岐命令の前記タイプのセットの第２のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答して、前記投機的予測を継続することを含む、請求項５に記載の方法。
【請求項１０】
前記第１のブロックの前記第１のアドレスから所定数の最下位ビットをドロップすることによって、インデックスを前記分岐予測構造に生成することをさらに含む、請求項１に記載の方法。
【請求項１１】
第１のブロック［３０５］における少なくとも１つの第１の分岐命令［３２０］の結果を予測し、前記第１のブロックの第１のアドレスに基づいて、前記第１のブロックにおける前記少なくとも１つの第１の分岐命令の前記結果に対応する第２のブロックのセット［３１０、３１５］のための分岐予測構造［５００］のエントリのセットにアクセスするように構成される分岐予測器［２２０］と、
前記分岐予測構造の前記エントリのセットに基づいて、前記第２のブロックのセットにおける第２の分岐命令の結果の投機的予測のための命令をフェッチするフェッチロジック［２２５］と、を含み、
前記投機的予測に関連付けられる状態は、前記少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、前記分岐予測器から選択的にフラッシュされる、装置。
【請求項１２】
前記分岐予測器は、前記少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは前記少なくとも１つの第１の分岐命令を受け入れない場合は前記第１のブロックに続くブロックのための前記分岐予測構造の前記エントリのセットにアクセスするように構成される、請求項１１に記載の装置。
【請求項１３】
前記分岐予測器は、前記第２のブロックのセットにおける前記第２の分岐命令の前記結果の前記投機的予測と同時に、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定するように構成される、請求項１１に記載の装置。
【請求項１４】
前記分岐予測器は、前記少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定するように構成される、請求項１３に記載の装置。
【請求項１５】
前記第２の分岐命令の前記結果の前記投機的予測に関連付けられる前記状態は、前記分岐命令のタイプのセットの第１のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答してフラッシュされる、請求項１１に記載の装置。
【請求項１６】
前記第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む、請求項１５に記載の装置。
【請求項１７】
前記分岐予測器は、前記予測された第２のブロックの第２のアドレスによってインデックス化される前記分岐予測構造のエントリに基づいて、前記第２のブロックの予測された第２のブロックにおける前記第２の分岐命令の少なくとも１つの投機的予測を再開するように構成される、請求項１５に記載の装置。
【請求項１８】
前記予測された第２のブロックは、前記第１のブロックにおける前記少なくとも１つの第１の分岐命令の予測された結果に対応する、請求項１７に記載の装置。
【請求項１９】
前記分岐予測器は、前記状態をフラッシュすることをバイパスし、前記分岐命令の前記タイプのセットの第２のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答して、前記投機的予測を継続するように構成される、請求項１５に記載の装置。
【請求項２０】
前記分岐予測器は、前記第１のブロックの前記第１のアドレスから所定数の最下位ビットをドロップすることによって、インデックスを前記分岐予測構造に生成するように構成される、請求項１１に記載の装置。
【請求項２１】
対応するブロックの分岐命令に関する分岐予測情報を含むエントリ［６０５］を記憶するように構成される分岐ターゲットバッファ（ＢＴＢ）［６００］と、
第１のブロックの第１のアドレスを使用してアクセスされる前記ＢＴＢのエントリに基づいて、前記第１のブロックにおける分岐命令の結果を所定数になるまで予測するように構成される第１の分岐予測器［５００］と、
前記第１のブロックの前記第１のアドレスを使用してアクセスされる前記ＢＴＢのエントリに基づいて、複数の第２のブロックの分岐命令の結果を前記所定数になるまで投機的に予測するように構成される第２の分岐予測器であって、前記第２のブロックは前記第１のブロックにおける前記分岐命令の結果に対応する、前記第２の分岐予測器と、を備え、
前記投機的予測に関連付けられる状態は前記第２の分岐予測器から選択的にフラッシュされ、前記第２のブロックの１つの分岐命令の結果の予測は、前記第１のブロックにおける前記分岐命令の少なくとも１つのうちの少なくとも１つのタイプに基づいて、前記第１の分岐予測器で選択的に開始される、装置。
【請求項２２】
前記投機的予測に関連付けられる前記状態は、前記分岐命令のタイプのセットの第１のサブセットに属する前記少なくとも１つのタイプに応答してフラッシュされ、前記投機的予測に関連付けられる前記状態は、前記分岐命令の前記タイプのセットの第２のサブセットに属する前記少なくとも１つのタイプに応答してフラッシュされない、請求項２１に記載の装置。
【請求項２３】
前記第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む、請求項２２に記載の装置。
【請求項２４】
前記戻り命令または前記間接分岐命令は、前記ＢＴＢのエントリに基づいて予測される前記戻り命令または前記間接分岐命令の結果に応答して、前記第１のサブセットから削除される、請求項２３に記載の装置。
【請求項２５】
前記第１の分岐予測器は、前記予測された第２のブロックの第２のアドレスによってインデックス化される前記ＢＴＢのエントリに基づいて、前記第２のブロックの予測された第２のブロックにおける前記分岐命令の少なくとも１つの投機的予測を再開するように構成される、請求項２１に記載の装置。
【請求項２６】
前記予測された第２のブロックは、前記第１のブロックにおける前記分岐命令のうちの少なくとも１つの予測された結果に対応する、請求項２５に記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
処理ユニットは様々なタイプの分岐命令を行い、分岐命令によって示されるアドレスにおける命令にプログラムフローをリダイレクト（または「分岐」）する。分岐命令のタイプは、プログラムフローを所定のターゲットアドレスにリダイレクトする無条件分岐命令と、条件が満たされた場合はプログラムフローをターゲットアドレスにリダイレクトするために「受け入れ」られ、条件が満たされない場合は命令の順次実行を継続するために「受け入れられない」条件付き分岐命令と、プログラムフローをサブルーチンのアドレスにリダイレクトする呼び出し命令と、サブルーチンから、サブルーチンを開始した呼び出し命令の後のアドレスにプログラムフローをリダイレクトする戻り命令と、処理ユニットの状態に応じて、プログラムフローを異なるアドレスにリダイレクトする間接分岐命令と、を含む。
【０００２】
分岐予測技術を使用して分岐命令の結果を推測し、これにより、処理ユニットが分岐命令を評価する前に、処理ユニットが予測された分岐に沿って後続の命令を投機的に実行することを始めることができる。処理ユニットは、分岐命令を含む命令のブロックに関連付けられる分岐予測構造のエントリの情報を使用して結果を予測する。分岐命令を評価するときに予測された分岐が誤りであることが判明した場合、予測が正しくない分岐に沿った投機的実行が中断され、処理ユニットの状態が分岐命令の状態にロールバックされ、正しい分岐に沿って実行が始まる。より具体的には、分岐予測ユニット及びフェッチユニットの両方がロールバックされ、分岐の正しいターゲットから、または分岐が受け入れなかった場合は分岐後のアドレスから処理される。
【０００３】
本開示は、添付の図面を参照することによって、良好に理解され得、その多くの特徴及び利点が当業者に明らかになる。異なる図面における同じ参照記号の使用は、類似項目または同一項目を示す。
【図面の簡単な説明】
【０００４】
【図１】いくつかの実施形態による、処理システムのブロック図である。
【図２】いくつかの実施形態による、プロセッサコアを含む処理システムの部分のブロック図である。
【図３】いくつかの実施形態による、予測ブロックと、予測ブロックにおける分岐命令の異なる起こり得る結果に対応するブロックのセットとのブロック図である。
【図４】いくつかの実施形態による、プログラムフロー及びサブルーチンを含む命令のセットである。
【図５】いくつかの実施形態による、分岐予測構造のブロック図である。
【図６】いくつかの実施形態による、分岐ターゲットバッファのブロック図である。
【図７】いくつかの実施形態による、分岐命令のタイプに基づいて、非先行分岐予測または先行分岐予測を選択的に行う方法のフロー図である。
【図８】いくつかの実施形態による、分岐ターゲットバッファ及び条件付き分岐予測器を含む分岐予測ユニットの一部のブロック図である。
【図９】いくつかの実施形態による、戻り命令及び間接分岐命令のサブセットが「予測先行」分岐予測を使用することを選択的に可能にする処理システムの部分のブロック図である。
【発明を実施するための形態】
【０００５】
分岐予測の「予測先行」手法では、第１のブロックのアドレスは、分岐予測構造及び分岐予測ストレージの情報にアクセスするためのインデックスとして使用される。その情報は、第１のブロックにおける分岐命令のターゲットのいずれかである潜在的な後続ブロックのセット、または第１のブロックの全ての分岐が受け入れないと予測される場合は第１のブロックに続くブロックに対応するエントリのセットを含む。エントリの１つのサブセットは、第１のブロックにおける分岐命令の結果を予測する分岐予測器に応答して、セットから選択される。予測された結果は、第２のブロックにおける分岐命令に関する分岐予測情報を含むエントリのサブセットに対応する分岐命令を含む第２のブロックを示す。分岐予測器は、エントリのサブセットの情報を使用して、第１のブロックの結果が正しく予測されたかどうかを決定する前に、第２のブロックにおける分岐命令の結果を予測する。第２のブロックのアドレスは、第２のブロックにおける分岐命令の１つの結果として予測されたアドレスにおいて、第３のブロックにおける分岐命令の結果を予測するために使用される情報へのインデックスとして使用される。第１のブロックの分岐結果またはターゲットの予測ミスが生じる場合、処理ユニットは第１のブロックにおける予測ミスした分岐命令の終わりの状態にロールバックされ、正しいパスに沿って実行が始まる。分岐命令が「受け入れなかった」、実際の分岐結果が「受け入れられた」という誤った予測であった場合、正しいパスは、第１のブロックにおける分岐命令のターゲットである潜在的な後続ブロックのセットの別の１つから始まる。分岐命令が「受け入れられ」、実際の分岐結果が「受け入れなかった」という誤った予測であった場合、第１のブロックの残りの部分が予測され、第２のブロックに移動する前にフェッチされる。したがって、第１の分岐予測が誤りである場合、処理ユニットは正しいパスに基づいて分岐予測器を再起動する必要があり、これによって、分岐予測の待ち時間が長くなる。
【０００６】
予測先行技術の有効性は、分岐命令のタイプによって異なる。予測先行技術は、通常、条件付き分岐命令及び無条件分岐命令の精度を犠牲にすることなく、全体的な待ち時間を短くする。しかしながら、他のタイプの分岐命令に予測先行技術を使用すると、ブロック内の分岐命令の結果を予測するために使用される情報に対するインデックスとしてブロックのアドレスを使用する従来の分岐予測と比較して、潜在的に精度が犠牲になる可能性がある。例えば、サブルーチンは、通常、プログラム内の複数の場所からアクセスされる。予測先行が使用中である場合、分岐予測構造の複数のエントリがサブルーチン内のブロックに対して生成される。この理由として、各エントリがプログラム内の異なる発信元アドレスによってインデックス化されるためである。同じブロックに複数のエントリを記憶すると、分岐ターゲットバッファのスペースが消費され、容量性ミスにつながる。係る分岐ターゲットバッファミスにより分岐予測器が分岐を識別できないとき、識別されない分岐を受け入れる場合、予測ミスが生じる。別の例について、サブルーチンからの戻り命令は、プログラムの複数のターゲットアドレスに戻る。したがって、分岐ターゲットバッファは、複数のターゲットアドレスから始まるブロックのエントリを含む。予測先行が使用中である場合、エントリは同じ発信元アドレス（つまり、戻り命令を含むブロックのアドレス）によってインデックス化される。したがって、セットアソシアティブ分岐ターゲットバッファはエントリを同じセットに記憶し、これによって、分岐ターゲットバッファにホットスポットを作成し、ウェイの数が同じ発信元アドレスによってインデックス化されるエントリの数よりも少ない場合、競合性ミスが生じる。また別の例として、間接分岐命令は、処理ユニットの状態に応じて異なるターゲットアドレスにジャンプする可能性があるため競合性ミスが発生し、これによって、戻り命令に対して発生するものと同様な方式で、複数のエントリが同じ発信元アドレスによってインデックス化されることがもたらされる。
【０００７】
図１〜図９は、第１のブロックにおける分岐命令のタイプに基づいて予測先行分岐予測を選択的に行うことによって、従来の非先行予測器の精度を維持しながら、先行予測器の待ち時間の利点のほとんどを達成する分岐予測技術を開示する。分岐予測器は、分岐予測構造の情報にアクセスするためのインデックスとして第１のブロックのアドレスを使用する。その情報は、第１のブロックにおける分岐命令の潜在的にターゲットになる第２のブロックのセットまたは第１のブロックにおける全ての分岐が受け入れないと予測される場合は第１のブロックに続くブロックに対応するエントリのセットを含む。分岐予測構造の組み合わせロジックの複数のインスタンスは、第２のブロックのセットに対応するエントリのセットからの分岐予測情報を使用して、第１のブロックにおける分岐命令の結果を決定する前に、（予測された及び代替の）第２のブロックにおける分岐命令の結果を予測する。分岐予測器は、組み合わせロジックが第２のブロックにおける分岐命令の結果を予測すると同時に、第１のブロックにおける分岐命令のタイプを決定する。タイプが分岐命令のタイプのセットの所定のサブセットにあると分岐予測器が決定したことに応答して、分岐予測器は、第２のブロックにおける分岐命令の結果の投機的予測に関連付けられる状態をフラッシュし、第２のブロックのアドレスを使用して第２のブロックの分岐予測構造のエントリにアクセスする。例えば、第１のブロックが呼び出し命令、戻り命令、または間接分岐命令で終了すると予測される場合、分岐予測器は第２のブロックの投機的予測に関連付けられる状態をフラッシュする。次に、分岐予測器は、第２のブロックのアドレスによってインデックス化されるエントリに基づいて、第２のブロックにおける分岐命令の結果の予測を再開する。
【０００８】
予測先行技術を実装する分岐予測器のいくつかの実施形態の性能は、少ない数のインデックスビットを使用して改善される。例えば、分岐ターゲットバッファにおけるエントリのインデックスを生成するために使用されるアドレスから、所定数の最下位ビットがドロップされる。いくつかのソフトウェア構成は、アドレス空間で相互に近接し、同じターゲットアドレスを有する複数の分岐命令を含む。予測先行分岐予測では、これらの分岐命令のそれぞれは同じターゲットアドレスを有し、ひいては、同じブロックを参照するが、分岐ターゲットバッファに異なるエントリを生成するであろう。このタイプの重複はインデックスから所定数の最下位ビットをドロップすることによって減り、これにより、近接する分岐命令は分岐ターゲットバッファにおける単一のエントリと同じインデックスを有する。
【０００９】
図１は、いくつかの実施形態による、処理システム１００のブロック図である。処理システム１００は、メモリ１０５もしくはダイナミックランダムアクセスメモリ（ＤＲＡＭ）等の非一時的コンピュータ可読媒体を使用して実装される他のストレージコンポーネントを含む、またはメモリ１０５もしくは他のストレージコンポーネントにアクセスことが可能である。しかしながら、場合によって、メモリ１０５は、スタティックランダムアクセスメモリ（ＳＲＡＭ）、及び不揮発性ＲＡＭ等を含む他のタイプのメモリを使用して実装される。メモリ１０５は、それが処理システム１００に実装される処理ユニットの外部に実装されることから、外部メモリと称される。処理システム１００は、また、メモリ１０５等の処理システム１００に実装されるエンティティ間の通信をサポートするバス１１０を含む。処理システム１００のいくつかの実施形態は、分かり易くするために図１に示さない他のバス、ブリッジ、スイッチ、ルータ等を含む。
【００１０】
処理システム１００は、ディスプレイ１２０に提示するために画像をレンダリングするように構成されるグラフィックスプロセッシングユニット（ＧＰＵ）１１５を含む。例えば、ＧＰＵ１１５は、オブジェクトをレンダリングし、ディスプレイ１２０に提供される画素値を作り、ディスプレイ１２０は、その画素値を使用して、レンダリングされたオブジェクトを表す画像を表示する。ＧＰＵ１１５は、同時にまたは並行して、命令を実行するように構成される複数のプロセッサコア１２１、１２２、１２３（本明細書では、まとめて「プロセッサコア１２１〜１２３」と称される）を実装する。ＧＰＵ１１５に実装されているプロセッサコア１２１〜１２３の数は、設計上の選択に関する重要な点である。ＧＰＵ１１５のいくつかの実施形態は、汎用コンピューティングのために使用される。ＧＰＵ１１５はメモリ１０５に記憶されるプログラムコード１２５等の命令を実行し、ＧＰＵ１１５は実行された命令の結果等の情報をメモリ１０５に記憶する。
【００１１】
また、処理システム１００は中央処理装置（ＣＰＵ）１３０を含み、中央処理装置（ＣＰＵ）１３０は、バス１１０に接続され、ひいては、バス１１０を介してＧＰＵ１１５及びメモリ１０５と通信する。ＣＰＵ１３０は、同時にまたは並行して、命令を実行するように構成される複数のプロセッサコア１３１、１３２、１３３（本明細書では、まとめて「プロセッサコア１３１〜１３３」と称される）を実装する。プロセッサコア１３１〜１３３はメモリ１０５に記憶されるプログラムコード１３５等の命令を実行し、ＣＰＵ１３０は実行された命令の結果等の情報をメモリ１０５に記憶する。ＣＰＵ１３０は、また、ＧＰＵ１１５にドローコールを発行することによって、グラフィック処理を開始することが可能である。ＣＰＵ１３０のいくつかの実施形態は、同時にまたは並行して命令を実行するように構成されるマルチプロセッサコア（分かり易くするために、図１に示さない）を実装する。
【００１２】
入力／出力（Ｉ／Ｏ）エンジン１４５は、ディスプレイ１２０、ならびにキーボード、マウス、プリンタ、及び外部ディスク等の処理システム１００の他の要素に関連付けられる入力動作または出力動作に対処する。Ｉ／Ｏエンジン１４５はＩ／Ｏエンジン１４５がバス１１０に結合され、これにより、メモリ１０５、ＧＰＵ１１５、またはＣＰＵ１３０と通信することが可能である。示される実施形態では、Ｉ／Ｏエンジン１４５は、コンパクトディスク（ＣＤ）、及びデジタルビデオディスク（ＤＶＤ）等の非一時的コンピュータ可読媒体を使用して実装される外部ストレージコンポーネント１５０に記憶される情報を読み取る。Ｉ／Ｏエンジン１４５は、また、ＧＰＵ１１５またはＣＰＵ１３０による処理の結果等の情報を、外部ストレージコンポーネント１５０に書き込むことが可能である。
【００１３】
図２は、いくつかの実施形態による、プロセッサコア２０５を含む処理システムの部分２００のブロック図である。プロセッサコア２０５は、図１に示されるプロセッサコア１２１〜１２３、１３１〜１３３のいくつかの実施形態を実装するために使用される。また、処理システムの部分２００は図１に示されるメモリ１０５のいくつかの実施形態を実装するために使用されるメモリ２１０を含む。メモリ２１０に記憶される情報の一部のコピーは、また、キャッシュ２１５に記憶される。例えば、頻繁にアクセスされる命令は、キャッシュ２１５のキャッシュラインまたはキャッシュブロックに記憶される。
【００１４】
プロセッサコア２０５は、条件付き分岐予測ストレージ及び条件付き分岐予測ロジックを含む分岐予測ユニット２２０を含む。条件付き分岐予測ストレージは、メモリ２１０の場所のアドレスを記憶し、条件付き分岐予測ロジックは、下記に詳細に説明するように、分岐命令の結果を予測するように構成される。分岐命令は、条件が真または偽であるかに応じてプログラムフローをアドレスにリダイレクトする条件付き分岐命令を含む。例えば、条件付き分岐命令は、ｉｆ−ｔｈｅｎ−ｅｌｓｅステートメント及びケースステートメント等のソフトウェア構成を実施するために使用される。分岐命令は、また、プログラムフローを命令によって示されるアドレスに常にリダイレクトする無条件分岐命令を含む。例えば、ＪＭＰ命令は、常に、命令によって示されるアドレスにジャンプする。分岐命令は、さらに、プログラムフローをサブルーチンの場所にリダイレクトする呼び出し命令と、プログラムフローをサブルーチンからプログラムフローの呼び出し命令に続く命令にリダイレクトする戻り命令とを含む。場合によって、ターゲットアドレスがレジスタまたはメモリの場所に提供されるため、分岐が実行されるたびにターゲットが異なる可能性がある。係る分岐は間接分岐と呼ばれる。
【００１５】
分岐予測ユニット２２０のいくつかの実施形態は、現在のプロセスまたはプロセッサコア２０５で以前に実行されたプロセスによって以前に実行された分岐命令に関連付けられるエントリを含む。分岐予測ユニット２２０の各エントリに記憶される分岐予測情報は、分岐命令がプログラムフローを命令のアドレスに向ける可能性を示す。分岐予測ユニット２２０のエントリは、対応する分岐命令に関連付けられるアドレスに基づいてアクセスされる。例えば、分岐命令の物理アドレス、仮想アドレス、またはキャッシュラインアドレスを表すビット（またはそのサブセット）の値は、分岐予測ユニット２２０へのインデックスとして使用される。別の例について、ビット（またはそのサブセット）のハッシュ値が、分岐予測ユニット２２０へのインデックスとして使用される。分岐予測構造の例は、間接分岐予測器、リターンアドレススタック、分岐ターゲットバッファ、条件付き分岐予測器、分岐履歴、または分岐予測情報を記憶するために使用されるいずれかのその他の予測構造を含む。
【００１６】
分岐予測ユニット２２０のいくつかの実施形態は、非先行分岐予測ロジック及び先行分岐予測ロジックを含む。本明細書で使用される語句「非先行分岐予測」は、ブロックを識別するアドレスに基づいてアクセスされる分岐予測構造（分岐ターゲットバッファ等）のエントリに基づいて、ブロックにおける１つ以上の分岐命令に対して分岐予測ユニット２２０によって行われる分岐予測を指す。本明細書で使用される語句「先行分岐予測」は、分岐予測ユニット２２０で以前にされたまたは同時に処理されているブロックを識別するアドレスに基づいてアクセスされる分岐予測構造のエントリに基づいて、ブロックにおける１つ以上の分岐命令に対して分岐予測ユニット２２０によって行われる分岐予測を指す。例えば、分岐予測ユニット２２０は、第１のブロックにおける分岐命令の結果を予測できる。結果は第２のブロックを示し、先行分岐予測ロジックは、本明細書で詳細に説明するように、第１のブロックのアドレスに基づいて、第２のブロックにおける分岐命令のエントリにアクセスできる。
【００１７】
分岐予測ユニット２２０は、分岐命令のタイプに基づいて、先行分岐予測または非先行分岐予測を選択的に利用する。例えば、分岐予測ユニット２２０の先行分岐予測ロジックは、条件付き分岐命令及び無条件分岐命令の分岐予測を行うために使用される。分岐予測ユニット２２０の非先行分岐予測ロジックは、サブルーチンのアドレスに分岐する呼び出し命令の分岐予測、サブルーチンから呼び出し命令に続く後続のアドレスに戻る戻り命令、及び間接分岐命令を行うために使用される。分岐予測ユニット２２０は、現在のブロックにおける分岐命令の起こり得る結果に対応する１つ以上の後続のブロックにおける分岐命令の結果を投機的に予測すると同時に、現在のブロックにおける分岐命令のタイプを決定する。分岐予測ユニット２２０が、現在のブロックにおける分岐命令のタイプが所定のタイプのサブセットにあると決定した場合（例えば、分岐命令は、呼び出し命令、戻り命令、または間接分岐命令である場合）、分岐予測ユニット２２０の状態がフラッシュされ、後続のブロックのアドレスに基づく非先行分岐予測ロジックを使用して、後続のブロックの１つの分岐予測が再開される。
【００１８】
いくつかの実施形態では、特定のタイプの分岐命令が所定のタイプのサブセットから削除され、これにより、ＢＴＢエントリ、間接分岐予測器、またはリターンアドレススタックに基づいて分岐命令の結果を予測するかどうかに基づいて、分岐命令に先行予測を使用できる。例えば、下記に説明するように、間接分岐命令を所定のタイプのサブセットから削除して、これにより、結果を予測する間接分岐予測器の代わりに、間接分岐命令の結果を予測するＢＴＢエントリに応答して、間接分岐命令に先行予測を使用できる。別の例について、下記に説明するように、結果を予測するリターンアドレススタックの代わりに、戻り命令の結果を予測するＢＴＢエントリに応答して、所定のタイプのサブセットから戻り命令を削除できる。
【００１９】
フェッチユニット２２５は、分岐予測ユニット２２０から受信したアドレスに基づいて、メモリ２１０またはキャッシュ２１５から命令等の情報をフェッチする。フェッチユニット２２５は、キャッシュ２１５またはメモリ２１０から命令を表すバイトを読み取り、その命令をデコードユニット２３０に送信する。デコードユニット２３０は命令バイトを調べて、命令の機能を決定する。デコードユニット２３０は、プロセッサコア２０５によって行われる予定の一連の動作を発生させる命令を変換（すなわち、デコード）する。これらの動作はスケジューラ２３５に書き込まれる。スケジューラ２３５は、動作のソース値がいつ準備ができているかを決定し、ソース値を１つ以上の実行ユニット２３１、２３２、２３３（本明細書では、まとめて「実行ユニット２３１〜２３３」と称される）に送信して動作を行う。結果は、レジスタファイル２４０にライトバックされる。
【００２０】
スケジューラ２３５は、プロセッサコア２０５による命令の実行をスケジュールする。スケジューラ２３５のいくつかの実施形態は、分岐命令によって示されるメモリ２１０（または関連のキャッシュ２１５）のアドレスにおいて、プログラムフローを命令にリダイレクトする分岐命令に続く命令の投機的実行を行う。次に、プロセッサコア２０５は、送信先アドレスにおいて命令と、プログラムフローの予測された分岐に沿って後続の命令とを投機的に実行することが可能である。分岐命令を評価するときに予測分岐が不正確であることが判明した場合、予測が不正確であった分岐に沿った投機的実行が中断され、プロセッサコア２０５の状態が分岐命令の状態にロールバックされ、正しい分岐に沿って実行が始まる。
【００２１】
図３は、いくつかの実施形態による、予測ブロック３００と、予測ブロック３００にける分岐命令の異なる起こり得る結果に対応するブロック３０５、３１０、３１５のセットとのブロック図である。予測ブロック３００は、分岐命令３２０、３２５と、命令３３０、３３５とを含む。予測ブロック３００のいくつかの実施形態は、より少ない分岐命令または追加の分岐命令（分かり易くするために、図３に示さない）を含む。ブロック３０５、３１０、３１５は、各々、命令３４０、３４５、３５０、３５５、３６０、３６５を含む。ブロック３０５は分岐命令３２０のターゲットである第１のアドレスによって識別され、ブロック３１０は分岐命令３２５のターゲットである第２のアドレスによって識別され、ブロック３１５は分岐命令３２５に続く第３のアドレスによって識別される。示される実施形態では、第３のアドレスは、命令３６０等のブロック３００とブロック３１５との間のキャッシュライン境界等の境界における後続の命令のためのものである。他の実施形態では、第３のアドレスは、命令３３５等のブロック３００における後続の命令のためのものである。
【００２２】
図２に示される分岐予測ユニット２２０等の分岐予測器は、予測ブロック内の複数の分岐命令の結果を同時に予測する。示される実施形態では、分岐予測器は、分岐命令３２０及び分岐命令３２５の結果を同時に予測する。分岐命令３２０の起こり得る結果が「受け入れられた」場合、プログラムフローはブロック３０５における命令３４０のターゲットアドレスに分岐する、または「受け入れられない」場合、プログラムフローは予測ブロック３００の命令３３０を連続的に継続する。分岐命令３２５の起こり得る結果が「受け入れられた」場合、プログラムフローはブロック３１０における命令３５０のターゲットアドレスに分岐する、または「受け入れられない」場合、プログラムフローは予測ブロック３００の命令３３５を連続的に継続する。
【００２３】
ブロック３０５、３１０、３１５の命令３４０、３４５、３５０、３５５、３６０、３６５は、１つ以上の分岐命令を含み得る。先行分岐予測を実施するいくつかの実施形態では、条件付き予測ロジックの複数のインスタンスを使用して、ブロック３０５、３１０、３１５における分岐命令の結果を同時に予測する。例えば、ブロック３００のアドレスを使用して、ブロック３０５、３１０、３１５の予測情報等の条件付き分岐予測ストレージの情報にアクセスできる。条件付き予測ロジックの複数のインスタンスは、アクセスされた情報を使用して、ブロック３０５、３１０、３１５における分岐命令の結果を予測する。下記に詳細に説明するように、投機的実行は、ブロック３０５、３１０、３１５のうちの予測された１つを含むパスに沿って進行する。
【００２４】
分岐予測器は、ブロック３０５、３１０、３１５における分岐命令の結果を予測すると同時に、分岐命令３２０、３２５のタイプを決定する。いくつかの実施形態では、先行分岐予測器は、ブロック３０５、３１０、３１５のアドレスに基づいてアクセスされる分岐予測構造の対応するエントリを使用して、ブロック３０５、３１０、３１５における分岐命令の結果を同時に予測するために分岐予測器に実装される。先行分岐予測は第１のタイプのサブセット（条件付き分岐命令及び無条件分岐命令等）に優先され、非先行分岐予測は第２のタイプのサブセット（呼び出し命令、戻り命令、間接分岐命令等）に優先される。したがって、分岐予測器は、分岐命令３２０、３２５のタイプに基づいて、先行分岐予測または非先行分岐予測を選択的に行う。１つ以上の分岐命令３２０、３２５のタイプが第１のサブセットにあるとの決定に応答して、分岐予測器は先行分岐予測を継続する。１つ以上の分岐命令３２０、３２５のタイプが第２のサブセットにあるとの決定に応答して、分岐予測器の状態はフラッシュされ、分岐予測は、例えば、分岐予測器の非先行インデックスを使用して、非先行分岐予測のために再開される。
【００２５】
図４は、いくつかの実施形態による、プログラムフロー４０５及びサブルーチン４１０を含む命令のセット４００である。プログラムフロー４０５は、プログラムフロー４０５の異なる場所からサブルーチン４１０を呼び出す、呼び出し命令４１５、４２０、４２５を含む。呼び出し命令４１５、４２０、４２５のいくつかの実施形態は、命令４３０のアドレスに基づいて、プログラムフロー４０５を命令４３０にリダイレクトすることによって、サブルーチン４１０を呼び出す。先行命令を利用している分岐予測器は、前のブロックのアドレスに基づいて、ブロックにおける分岐命令のための分岐予測構造にエントリを生成する。したがって、分岐予測器は、呼び出し命令４１５、４２０、４２５のそれぞれについて、サブルーチン４１０の分岐予測構造にエントリを生成する。例えば、分岐予測器は、呼び出し命令４１５のアドレスを使用してアクセスされる分岐予測構造の第１のエントリ、呼び出し命令４２０のアドレスを使用してアクセスされる分岐予測構造の第２のエントリ、及び呼び出し命令４２５のアドレスを使用してアクセスされる分岐予測構造の第３のエントリを生成する。第１のエントリ、第２のエントリ、及び第３のエントリの分岐予測情報は、同じサブルーチン４１０を参照しているため同じである。
【００２６】
サブルーチン４１０は、１つ以上の追加の命令４３５（場合によって、分岐命令を含む）と、プログラムフロー４０５をサブルーチン４１０にリダイレクトした呼び出し命令に続く命令に戻すようにフローをリダイレクトする戻り命令４４０とを含む。例えば、サブルーチン４１０が呼び出し命令４１５によって呼び出される場合、戻り命令４４０はフローを命令４４５にリダイレクトし、サブルーチン４１０が呼び出し命令４２０によって呼び出される場合、戻り命令４４０はフローを命令４５０にリダイレクトし、サブルーチン４１０が呼び出し命令４２５によって呼び出される場合、戻り命令４４０はフローを命令４５５にリダイレクトする。分岐予測器は、命令４４５、４５０、４５５のターゲットアドレスによって識別されるブロックの分岐予測構造にエントリを生成する。予測先行が使用中である場合、エントリは、同じ発信元アドレス（すなわち、戻り命令４４０を含むブロックのアドレス）によってインデックス化される。したがって、セットアソシアティブ分岐予測構造は、命令４４５、４５０、４５５のエントリを同じセットに記憶し、これによって、分岐予測構造にホットスポットを作成し、ウェイの数が同じ発信元アドレスによってインデックス化されるエントリの数よりも少ない場合、競合性ミスが生じる。
【００２７】
図５は、いくつかの実施形態による、分岐予測構造５００のブロック図である。分岐予測構造５００は、図２に示される分岐予測ユニット２２０のいくつかの実施形態で実装される。分岐予測構造５００は、図４に示される呼び出し命令４１５、４２０、４２５等の呼び出し命令の先行分岐予測中に生成されるエントリ５０５、５１０、５１５を含む。呼び出し命令は、プログラムフローを同じサブルーチン（例えば、図４に示されるサブルーチン４１０）にリダイレクトする。
【００２８】
エントリ５０５は、２つの分岐命令に関する分岐予測情報を含む。例えば、エントリ５０５は、アドレス５２０に対する第１の分岐命令の場所を示すオフセット５３５と、アドレス５２０に対する第２の分岐命令の場所を示すオフセット５４０とを含む。エントリ５０５は、また、第１の分岐命令のタイプ５４５及び第２の分岐命令のタイプ５５０と、第１の分岐命令のターゲットアドレス５５５及び第２の分岐命令のターゲットアドレス５６０とを識別する情報を含む。第１の分岐命令が受け入れられた場合、プログラムフローは第１の分岐命令からターゲットアドレス５５５に分岐する。そうでなければ、プログラムフローが第２の分岐命令に到達するまで、プログラムフローはブロックの命令を連続的に継続する。第２の分岐命令が受け入れられた場合、プログラムフローは第２の分岐命令からターゲットアドレス５６０に分岐し、そうでなければ、プログラムフローはブロックの命令を連続的に継続する。オーバーフローインジケータ５６５は、次の順次境界の前に追加の分岐命令があるかどうかを示す。いくつかの実施形態では、順次境界は、命令キャッシュライン境界と一致する。他の実施形態では、順次境界は、他の整列されたアドレスに設定される。図５に示されるエントリ５０５は、分岐ターゲットバッファ等の分岐予測構造のエントリの一例である。エントリ５０５のいくつかの実施形態は、異なる方式で編成または構造化される異なる分岐予測情報を含む。
【００２９】
エントリ５１０、５１５は前のアドレス（例えば、図４に示される呼び出し命令４１５、４２０、４２５を含むブロックのアドレス）によってインデックス化されるため、エントリ５１０、５１５はＢＴＢアレイの異なるインデックスに配置される。しかしながら、オフセット、分岐命令タイプ、ターゲットアドレス、オーバーフロー値等のエントリ５１０、５１５のコンテンツはエントリ５０５のコンテンツと同じであり、この理由として、エントリ５０５、５１０、５１５の全てが同じ命令ブロック（例えば、図４に示される呼び出し命令４１５、４２０、４２５によって呼び出されるサブルーチンに対応する命令ブロック４１０）に生成されるためである。したがって、エントリ５０５、５１０、５１５は相互に重複し、分岐予測構造のスペースを不必要に消費する。
【００３０】
図６は、いくつかの実施形態による分岐ターゲットバッファ６００のブロック図である。分岐ターゲットバッファ６００は、図２に示される分岐予測ユニット２２０のいくつかの実施形態を実装するために使用される。分岐ターゲットバッファ６００のエントリは、分岐命令を含むブロックのアドレスに基づいて形成されるインデックスを使用してインデックス化される。例えば、非先行予測が使用中であるとき、分岐命令を含むブロックのアドレスは、分岐ターゲットバッファ６００のエントリへのインデックスを生成するために使用される。別の例について、先行予測が使用中であるとき、前のブロックのアドレスを使用して、現在のブロックに対応する分岐ターゲットバッファのエントリへのインデックスを生成する。
【００３１】
示される実施形態では、分岐ターゲットバッファ６００は、対応するプロセッサコアで実行するプログラムフローにおける分岐命令に関する分岐予測情報を含むエントリを記憶する４ウェイセットアソシアティブバッファである。したがって、各インデックスは、複数のエントリを含む４つの異なる方法の１つにおけるエントリにマッピングされる。例えば、分岐ターゲットバッファ６００は、実線のボックスによって示される第１のウェイに対応するエントリ６０５、６１０、６１５を含む。他のエントリ６２０（分かり易くするために、符号によって１つだけ示されるもの）は、破線のボックスによって示される４ウェイセットアソシアティブバッファの他のウェイに対応する。
【００３２】
分岐予測器は、対応する分岐命令に関連付けられるアドレスに基づいて生成されるインデックス６２５、６３０、６３５によって識別されるブロックについて、分岐ターゲットバッファ６００にエントリを生成する。示される実施形態では、分岐予測器は先行予測を実施し、インデックス６２５、６３０、６３５に関連付けられる分岐命令はサブルーチンの戻り命令である。したがって、インデックス６２５、６３０、６３５は同じ値を有する。この理由として、同じ発信元アドレス（すなわち、サブルーチンの戻り命令を含むブロックのアドレス）に基づいて生成されるためである。したがって、インデックス６２５、６３０、６３５によって識別されるエントリは、分岐ターゲットバッファ６００において同じ（第１の）ウェイでエントリ６０５、６１０、６１５に作成される。これは、特に、他のインデックスを使用してアクセスされる分岐ターゲットバッファ６００の他のウェイ６２０でエントリが作成されない（または、より少ないエントリが作成される）場合、第１のウェイにおいてホットスポットを作成する。第１のウェイにおけるエントリの数が同じ発信元アドレスによってインデックス化されるエントリの数よりも少ない場合（例えば、同じ戻り命令によってアクセスされるブロックに関するブロック予測情報によって消費されるエントリの数が第１のウェイにおけるエントリの数を超える場合）、ホットスポットでは競合性ミスが生じる。
【００３３】
図７は、いくつかの実施形態による、分岐命令のタイプに基づいて、非先行分岐予測または先行分岐予測を選択的に行う方法のフロー図７００である。方法７００の第１の部分は、図１に示される処理システム１００及び図２に示される処理システムの部分２００のいくつかの実施形態で実施される。示される実施形態では、分岐予測器は、２つの分岐命令等の分岐命令の結果を所定数になるまで同時に予測する。しかしながら、ブロックは、所定数の分岐命令を正確に含む必要はなく、いくつかのブロックは所定数の分岐命令よりも多い数のまたは少ない数の分岐命令を含む。
【００３４】
ブロック７０５において、分岐予測器は、第１のブロックにおける第１の分岐及び第２の分岐の結果を同時に予測する。本明細書で説明するように、第１のブロックにおける第１の分岐及び第２の分岐の結果の異なる組み合わせは、異なる送信先の第２のブロックに対応する。分岐予測器は、第１の分岐及び第２の分岐の予測された結果に基づいて、第２のブロックの１つを「予測された」第２のブロックとして識別する。他の結果に対応する第２のブロックは、「代替」の第２のブロックとして識別される。次に、方法７００の一部は、ブロック７１０、７１５に移る。
【００３５】
ブロック７１０において、分岐予測器は、第１のブロックにおける１つ以上の分岐命令のタイプを決定する。本明細書で説明するように、タイプは、条件付き分岐命令及び無条件直接分岐命令を含む第１のサブセットと、呼び出し命令、戻り命令、及び間接分岐命令を含む第２のサブセットとを含む。いくつかの実施形態では、他のタイプの命令は第１のサブセットまたは第２のサブセットに含まれる。例えば、間接分岐命令は、下記に説明するように、予測された第２のブロックのアドレスを生成する間接分岐予測器に応答して第１のサブセットに含まれる。別の例について、下記に説明するように、予測された第２のブロックのアドレスを生成するリターンアドレススタックに応答して、戻り命令は第１のサブセットに含まれる。分岐予測器は、図５に示される分岐予測構造５００等の分岐予測構造及び図６に示される分岐ターゲットバッファ６００から取り込まれた分岐予測情報に基づいて、分岐命令のタイプを決定する。
【００３６】
ブロック７１５において、分岐予測器は、予測された及び代替の第２のブロックにおける分岐命令の結果の先行予測を開始する。本明細書で説明するように、分岐予測器による先行予測は、第１のブロックのアドレスから派生したインデックスに基づいてアクセスされる分岐予測構造のエントリにおける分岐予測情報に基づいて行われる。いくつかの実施形態では、条件付き予測ロジックの複数のインスタンスを使用して、予測された及び代替の第２のブロックのそれぞれにおける第１の分岐命令及び第２の分岐命令の結果を予測する。いくつかの実施形態では、条件付き予測ロジックの第１のインスタンスは予測された第２のブロックにおける第１の分岐命令及び第２の分岐命令の結果を予測し、第２のインスタンスは代替の第２のブロックの１つにおける第１の分岐命令及び第２の分岐命令の結果を予測し、第３のインスタンスは代替の第２のブロックの別のものにおける第１の分岐命令及び第２の分岐命令の結果を予測する。しかしながら、他の実施形態では、第２のブロックの一部または全ては、多い数のまたは少ない数の分岐命令を含む。
【００３７】
ブロック７１０、７１５は、示される実施形態で同時に行われる。しかしながら、分岐予測器のいくつかの実施形態は、連続的にまたは交互方式を含む他の順序で、ブロック７１０、７１５における動作の一部または全てを行う。方法７００は、第１のブロックにおける１つ以上の分岐命令のタイプを決定する分岐記述に応答して、決定ブロック７２０に移る。
【００３８】
決定ブロック７２０において、分岐予測器は、第１のブロックにおいて最初に予測された受入済の分岐命令のタイプがタイプのセットの第１のサブセットまたは第２のサブセットにあるかどうかを決定する。分岐予測器が、分岐命令が第１のタイプのサブセットにあると決定した場合（例えば、分岐命令が条件付き分岐命令または無条件分岐命令である場合）、方法７００はブロック７２５に移り、分岐予測器は先行分岐予測技術の使用を継続する。分岐予測器が、分岐命令が第２のタイプのサブセットにあると決定した場合（例えば、分岐命令が呼び出し命令、戻り命令、または間接分岐命令である場合）、方法７００はブロック７３０に移る。
【００３９】
本明細書で説明するように、第２のサブセットのタイプの分岐命令の結果を予測するために先行分岐予測を使用すると、ブロック内の分岐命令の結果の予測するために使用される情報に対するインデックスとしてブロックのアドレスを使用する従来の分岐予測と比較して、潜在的に精度が犠牲になる可能性がある。第２のサブセットにタイプを有する分岐命令の精度を保つために、ブロック７３０において、分岐予測パイプラインはフラッシュされ、予測された及び代替の第２のブロックにおける分岐命令の結果の先行予測に関連付けられる状態を削除する。次に、予測された第２のブロックのアドレスに基づいて分岐予測構造のエントリからアクセスされた分岐予測情報を使用して、予測された第２のブロックに対して非先行分岐予測が再開される。
【００４０】
図８は、いくつかの実施形態による、分岐ターゲットバッファ及び条件付き分岐予測器を含む分岐予測ユニット８００の一部のブロック図である。分岐予測ユニット８００は、図２に示される分岐予測ユニット２２０のいくつかの実施形態を実装するために使用される。アドレス８０５は、命令のブロックの開始アドレスを示す。分岐ターゲットバッファのエントリは、エントリに関連付けられるブロックの開始アドレスによってインデックス化される。示される実施形態では、ブロックにおける分岐命令に関する分岐予測情報を含む分岐ターゲットバッファのエントリ８１５へのインデックス８１０は、アドレス８０５に等しい値を含む。したがって、インデックス８１０は、分岐ターゲットバッファのエントリ８１５にアクセスするために使用される。例えば、図３に示されるブロック３００のアドレスは、ブロック３００の分岐３２０、３２５に対応する分岐ターゲットバッファのエントリへのインデックスとして使用される。
【００４１】
エントリ８１５は、２つの分岐命令に関する分岐予測情報を含む。例えば、エントリ８１５は、アドレス８０５に対する第１の分岐命令の場所を示すオフセット８２０と、アドレス８０５に対する第２の分岐命令の場所を示すオフセット８２５とを含む。エントリは、また、第１の分岐命令のタイプ８３０及び第２の分岐命令のタイプ８３５と、第１の分岐命令のターゲットアドレス８４０及び第２の分岐命令のターゲットアドレス８４５とを識別する情報を含む。プログラムフローは、第１の分岐命令が受け入れられた場合、第１の分岐命令からターゲットアドレス８４０に分岐する。そうでなければ、プログラムフローが第２の分岐命令に到達するまで、プログラムフローはブロックの命令を連続的に継続する。第２の分岐命令が受け入れられた場合、プログラムフローは第２の分岐命令からターゲットアドレス８４５に分岐し、そうでなければ、プログラムフローはブロックの命令を連続的に継続する。オーバーフローインジケータ８５０は、次の順次境界の前に追加の分岐命令があるかどうかを示す。いくつかの実施形態では、順次境界は、命令キャッシュライン境界と一致する。他の実施形態では、順次境界は、他の整列されたアドレスに設定される。図８に示されるエントリ８１５は、分岐ターゲットバッファにおけるエントリの一例である。エントリ８１５のいくつかの実施形態は、異なる方式で編成または構造化される異なる分岐予測情報を含む。
【００４２】
分岐予測構造は、条件付き分岐予測ストレージ８６０及び条件付き予測ロジック８６５を含む。条件付き分岐予測ストレージ８６０は、分岐命令の結果を予測するために使用される情報を記憶する。インデックス８１０は、アドレス８０５によって示されるブロックに関連付けられる記憶された情報にアクセスするために、条件付き分岐予測ストレージ８６０に提供される。いくつかの実施形態では、分岐履歴情報８５５等の追加情報は条件付き分岐予測ストレージ８６０に提供される。アドレス８０５から始まるブロックに関連付けられるアクセスされた情報は条件付き予測ロジック８６５に提供され、条件付き予測ロジック８６５は、また、エントリ８１５からブロックにおける分岐命令に関する分岐予測情報を受信する。条件付き予測ロジック８６５は、エントリ８１５及び条件付き分岐予測ストレージ８６０からアクセスされる情報を使用して、ブロックにおける分岐命令の結果を予測する。示される実施形態では、条件付き予測ロジック８６５は、第１の分岐命令が受け入れられず、第２の分岐命令が受け入れられたことを予測する。したがって、条件付き予測ロジック８６５は、第１のブロックの終わりが第２の分岐命令（ＯＦＦＳＥＴ＿２）の場所にあり、第２の分岐命令のターゲットアドレスがＴ＿ＡＤＤＲ＿２であると予測する。
【００４３】
図９は、いくつかの実施形態による、戻り命令及び間接分岐命令のサブセットが「予測先行」分岐予測を使用することを選択的に可能にする処理システムの部分９００のブロック図である。処理システムの部分９００は、図１に示される処理システム１００及び図２に示される処理システムの部分２００のいくつかの実施形態を実装するために使用される。部分９００の示される実施形態は、間接分岐命令または戻り命令のターゲットを記憶するＢＴＢエントリ９０５を含む。間接予測器９１０は間接分岐命令のターゲットを予測し、リターンアドレススタック９１５は戻り命令のリターンアドレスを予測する。間接予測器９１０及びリターンアドレススタック９１５は、対応する分岐の結果が予測されるたびに異なるアドレスを返す。分岐が例えばＢＴＢエントリ９０５に最初にインストールされるときに、間接分岐命令またはリターンの第１のターゲットはＢＴＢに書き込まれる。間接分岐命令または戻り命令のＢＴＢエントリ９０５に記憶されるターゲット情報はその後変更されない。
【００４４】
間接分岐予測器９１０またはリターンアドレススタック９１５からの予測は、ＢＴＢエントリ９０５の予測よりも優先される。例えば、間接予測器９１０が間接分岐命令のターゲットアドレスを予測する場合、このターゲットアドレスは、ＢＴＢエントリ９０５によって予測されたターゲットアドレスの代わりに、後続の分岐予測のためにセレクタ９２０によって選択される。別の例について、リターンアドレススタック９１５が戻り命令のリターンアドレスを予測する場合、このリターンアドレスは、ＢＴＢエントリ９０５によって予測されたリターンアドレスの代わりに、後続の分岐予測のためにセレクタ９２０によって選択される。間接分岐予測器９１０及びリターンアドレススタック９１５は常に予測を返すわけではない。したがって、ＢＴＢエントリ９０５によって予測されたアドレスは、間接分岐予測器９１０またはリターンアドレススタック９１５による予測がない場合に、セレクタ９２０によって選ばれる。
【００４５】
いくつかの実施形態では、先行予測または非先行予測は、セレクタ９２０によって選ばれるアドレスを生成するエンティティに応じて、間接分岐命令及び戻り命令に対して選択的に使用される。先行予測は、ＢＴＢエントリ９０５によって予測されたアドレスを選ぶセレクタ９２０に応答して使用される。この理由として、ＢＴＢエントリ９０５が分岐予測に使用されるたびに、分岐予測が同じアドレスに対して行われるためである。したがって、これらの場合、先行予測を使用することによって、ホットスポットはＢＴＢアレイに生成されない。非先行予測は、間接分岐予測器９１０またはリターンアドレススタック９１５によって予測されたアドレスを選ぶセレクタ９２０に応答して使用される。この理由として、本明細書で説明するように、これらのエンティティは毎回異なるターゲットアドレスを生成し、ひいては、ＢＴＢアレイにホットスポットを生成し得るためである。
【００４６】
本明細書に開示されるように、本方法は、第１のブロックの第１のアドレスに基づいて、第１のブロックにおける少なくとも１つの第１の分岐命令の結果に対応する第２のブロックのセットのための分岐予測構造のエントリのセットにアクセスすることと、分岐予測構造のエントリのセットに基づいて、第２のブロックのセットにおける第２の分岐命令の結果の投機的予測を開始することと、少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、投機的予測に関連付けられる状態を選択的にフラッシュすることとを含む。一態様では、分岐予測構造のエントリのセットにアクセスすることは、少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは少なくとも１つの第１の分岐命令が受け入れられない場合は第１のブロックに続くブロックのための分岐予測構造のエントリのセットにアクセスすることを含む。別の態様では、第２のブロックのセットにおける第２の分岐命令の結果の投機的予測と同時に、少なくとも１つの第１の分岐命令の少なくとも１つのタイプを決定する。
【００４７】
別の態様では、少なくとも１つの第１の分岐命令の少なくとも１つのタイプを決定することは、少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、少なくとも１つの第１の分岐命令の少なくとも１つのタイプを決定することを含む。また別の態様では、状態を選択的にフラッシュすることは、分岐命令のタイプのセットの第１のサブセットに属する少なくとも１つの第１の分岐命令の少なくとも１つのタイプに応答して、第２の分岐命令の結果の投機的予測に関連付けられる状態をフラッシュすることを含む。さらに別の態様では、第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む。また別の態様では、本方法は、予測された第２のブロックの第２のアドレスによってインデックス化される分岐予測構造のエントリに基づいて、第２のブロックの予測された第２のブロックにおける第２の分岐命令の少なくとも１つの投機的予測を再開することを含む。一態様では、予測された第２のブロックは、第１のブロックにおける少なくとも１つの第１の分岐命令の予測された結果に対応する。別の態様では、状態を選択的にフラッシュすることは、状態のフラッシュをバイパスし、分岐命令のタイプのセットの第２のサブセットに属する少なくとも１つの第１の分岐命令の少なくとも１つのタイプに応答して投機的予測を継続することを含む。また別の態様では、本方法は、第１のブロックの第１のアドレスから所定数の最下位ビットをドロップすることによって、インデックスを分岐予測構造に生成することを含む。
【００４８】
本明細書に開示されるように、本装置は、第１のブロックにおける少なくとも１つの第１の分岐命令の結果を予測し、第１のブロックの第１のアドレスに基づいて、第１のブロックにおける少なくとも１つの第１の分岐命令の結果に対応する第２のブロックのセットのための分岐予測構造のエントリのセットにアクセスするように構成される分岐予測器と、分岐予測構造のエントリのセットに基づいて、第２のブロックのセットにおける第２の分岐命令の結果の投機的予測のための命令をフェッチするフェッチロジックと、を含み、投機的予測に関連付けられる状態は、少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、分岐予測器から選択的にフラッシュされる。一態様では、分岐予測器は、少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは少なくとも１つの第１の分岐命令を受け入れない場合は第１のブロックに続くブロックのための分岐予測構造のエントリのセットにアクセスするように構成される。別の態様では、分岐予測器は、第２のブロックのセットにおける第２の分岐命令の結果の投機的予測と同時に、少なくとも１つの第１の分岐命令の少なくとも１つのタイプを決定するように構成される。さらに別の態様では、分岐予測器は、少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、少なくとも１つの第１の分岐命令の少なくとも１つのタイプを決定するように構成される。
【００４９】
別の態様では、第２の分岐命令の結果の投機的予測に関連付けられる状態は、分岐命令のタイプのセットの第１のサブセットに属する少なくとも１つの第１の分岐命令の少なくとも１つのタイプに応答してフラッシュされる。別の態様では、第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む。さらに別の態様では、分岐予測器は、予測された第２のブロックの第２のアドレスによってインデックス化される分岐予測構造のエントリに基づいて、第２のブロックの予測された第２のブロックにおける第２の分岐命令の少なくとも１つの投機的予測を再開するように構成される。また別の態様では、予測された第２のブロックは、第１のブロックにおける少なくとも１つの第１の分岐命令の予測された結果に対応する。別の態様では、分岐予測器は、状態のフラッシュをバイパスし、分岐命令のタイプのセットの第２のサブセットに属する少なくとも１つの第１の分岐命令の少なくとも１つのタイプに応答して投機的予測を継続するように構成される。さらに別の態様では、分岐予測器は、第１のブロックの第１のアドレスから所定数の最下位ビットをドロップすることによって、インデックスを分岐予測構造に生成するように構成される。
【００５０】
本明細書に開示されるように、本装置は、対応するブロックの分岐命令に関する分岐予測情報を含むエントリ［６０５］を記憶するように構成される分岐ターゲットバッファ（ＢＴＢ）［６００］と、第１のブロックの第１のアドレスを使用してアクセスされるＢＴＢのエントリに基づいて、第１のブロックにおける分岐命令の結果を所定数になるまで予測するように構成される第１の分岐予測器［５００］と、第１のブロックの第１のアドレスを使用してアクセスされるＢＴＢのエントリに基づいて、複数の第２のブロックの分岐命令の結果を所定数になるまで投機的に予測するように構成される第２の分岐予測器であって、第２のブロックは第１のブロックにおける分岐命令の結果に対応する、第２の分岐予測器と、を含み、投機的予測に関連付けられる状態は第２の分岐予測器から選択的にフラッシュされ、第２のブロックの１つの分岐命令の結果の予測は、第１のブロックにおける分岐命令の少なくとも１つのうちの少なくとも１つのタイプに基づいて、第１の分岐予測器で選択的に開始する。別の態様では、投機的予測に関連付けられる状態は、分岐命令のタイプのセットの第１のサブセットに属する少なくとも１つのタイプに応答してフラッシュされ、投機的予測に関連付けられる状態は、分岐命令のタイプのセットの第２のサブセットに属する少なくとも１つのタイプに応答してフラッシュされない。さらに別の態様では、第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む。また別の態様では、戻り命令または間接分岐命令は、ＢＴＢのエントリに基づいて予測される戻り命令または間接分岐命令の結果に応答して、第１のサブセットから削除される。また別の態様では、第１の分岐予測器は、予測された第２のブロックの第２のアドレスによってインデックス化されるＢＴＢのエントリに基づいて、第２のブロックの予測された第２のブロックにおける分岐命令の少なくとも１つの投機的予測を再開するように構成される。さらに別の態様では、予測された第２のブロックは、第１のブロックにおける分岐命令のうちの少なくとも１つの予測された結果に対応する。
【００５１】
いくつかの実施形態では、上記に説明した装置及び技術は、図１〜図９を参照して上記に説明した分岐予測等の、１つ以上の集積回路（ＩＣ）デバイス（また、集積回路パッケージまたはマイクロチップと称される）を含むシステムに実装される。電子設計自動化（ＥＤＡ）及びコンピュータ支援設計（ＣＡＤ）ソフトウェアツールは、これらのＩＣデバイスの設計及び製作で使用され得る。これらの設計ツールは、通常、１つ以上のソフトウェアプログラムとして表される。１つ以上のソフトウェアプログラムは、回路を製造するための製造システムを設計または適合させるプロセスの少なくとも一部を行うように、コンピュータシステムを操作し１つ以上のＩＣデバイスの回路を表すコードで動作する、コンピュータシステムによって実行可能なコードを含む。このコードは、命令、データ、または命令及びデータの組み合わせを含み得る。設計ツールまたは製作ツールを表すソフトウェア命令は、通常、コンピューティングシステムにアクセス可能なコンピュータ可読記憶媒体に記憶される。同様に、ＩＣデバイスの設計または製造の１つ以上のフェーズを表すコードは、同じコンピュータ可読記憶媒体または異なるコンピュータ可読記憶媒体に記憶され、同じコンピュータ可読記憶媒体または異なるコンピュータ可読記憶媒体からアクセスされ得る。
【００５２】
コンピュータ可読記憶媒体は、命令及び／またはデータをコンピュータシステムに提供するために、使用中にコンピュータシステムによってアクセス可能な任意の非一時的記憶媒体、または非一時的記憶媒体の組み合わせを含み得る。係る記憶媒体は、限定ではないが、光媒体（例えば、コンパクトディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）、ブルーレイディスク）、磁気媒体（例えば、フロッピーディスク、磁気テープ、または磁気ハードドライブ）、揮発性メモリ（例えば、ランダムアクセスメモリ（ＲＡＭ）またはキャッシュ）、不揮発性メモリ（例えば、読み取り専用メモリ（ＲＯＭ）またはフラッシュメモリ）、または微小電気機械システム（ＭＥＭＳ）ベースの記憶媒体を含み得る。コンピュータ可読記憶媒体は、コンピューティングシステムに埋め込まれ得（例えば、システムＲＡＭまたはＲＯＭ）、コンピューティングシステムに固定式に取り付けられ得（例えば、磁気ハードドライブ）、コンピューティングシステムに取り外し可能に取り付けられ得（例えば、光ディスクまたはユニバーサルシリアルバス（ＵＳＢ）ベースフラッシュメモリ）、または有線もしくは無線ネットワークを介してコンピュータシステムに結合され得る（例えば、ネットワークアクセス可能ストレージ（ＮＡＳ））。
【００５３】
いくつかの実施形態では、上記に説明した技術の特定の態様は、ソフトウェアを実行する処理システムの１つ以上のプロセッサによって実施され得る。ソフトウェアは、非一時的コンピュータ可読記憶媒体に記憶されるまたはそうでなければ有形に具現化される、実行可能な命令の１つ以上のセットを含む。ソフトウェアは、１つ以上のプロセッサにより実行されるとき、上記に説明した技術の１つ以上の態様を行うために１つ以上のプロセッサを操作する命令及び特定のデータを含み得る。非一時的コンピュータ可読記憶媒体は、例えば、磁気もしくは光ディスク記憶デバイス、フラッシュメモリ、キャッシュ、ランダムアクセスメモリ（ＲＡＭ）等のソリッドステートストレージデバイス、または他の単一の不揮発性メモリデバイスもしくは複数の不揮発性メモリデバイス等を含み得る。非一時的コンピュータ可読記憶媒体上に記憶される実行可能命令は、１つ以上のプロセッサにより、解釈される、またはそうでなければ実行可能である、ソースコード、アセンブリ言語コード、オブジェクトコード、または他の命令形式であり得る。
【００５４】
説明したものに加えて、全体的な説明において上記に説明した全てのアクティビティまたは要素が要求されないこと、特定のアクティビティまたはデバイスの一部が要求され得ないこと、１つ以上のさらなるアクティビティが行われ得ること、または要素が含まれることを留意されたい。さらには、アクティビティをリストアップする順序は、必ずしもそれらが行われる順序ではない。また、特定の実施形態を参照して概念が説明されている。しかしながら、当業者は、下記の「特許請求の範囲」に記載される本開示の範囲から逸脱することなく、様々な修正及び変更がなされ得ることを認識する。したがって、本明細書及び図は、限定的な意味ではなく、例示的な意味で見なされるべきであり、全ての係る修正は、本開示の範囲内に含まれることが意図される。
【００５５】
特定の実施形態に関して、利益、他の利点、及び問題に対する解決策を上記に説明している。しかしながら、利益、利点、及び問題に対する解決策、ならびにいずれかの利益、利点、または解決策を生じさせ得る、もしくはより顕著になり得るいずれかの特徴（複数可）が、いずれかまたは全ての請求項の重要な、必要な、または不可欠な特徴として解釈されるべきではない。さらに、開示された主題は、本明細書の教示の利益がもたらされる当業者に明らかである、異なるが同等になるように修正及び実践され得るため、上記に開示した特定の実施形態は例示にすぎない。下記の「特許請求の範囲」に記載される場合を除き、本明細書に示される構造または設計の詳細に対する制限は意図されていない。したがって、上記に開示した特定の実施形態が改正または修正され得、全ての係る変形が開示した主題の範囲内で考慮されることは明らかである。したがって、本明細書に求められる保護は、下記の「特許請求の範囲」に記載されるようなものである。
【図１】
2021527892.tif 000003
【図２】
2021527892.tif 000004
【図３】
2021527892.tif 000005
【図４】
2021527892.tif 000006
【図５】
2021527892.tif 000007
【図６】
2021527892.tif 000008
【図７】
2021527892.tif 000009
【図８】
2021527892.tif 000010
【図９】
2021527892.tif 000011
【手続補正書】
【提出日】令和3年3月22日(2021.3.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１のブロック［３０５］の第１のアドレスに基づいて、前記第１のブロックにおける少なくとも１つの第１の分岐命令［３２０］の結果に対応する第２のブロックのセット［３１０，３１５］の分岐予測構造［５００］のエントリのセットにアクセスすることと、
前記分岐予測構造の前記エントリのセットに基づいて、前記第２のブロックのセットにおける第２の分岐命令［３２５，３３５］の結果の投機的予測を開始することと、
前記少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、前記投機的予測に関連付けられる状態を選択的にフラッシュすることと、
を含む、方法。
【請求項２】
前記分岐予測構造の前記エントリのセットにアクセスすることは、前記少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは前記少なくとも１つの第１の分岐命令を受け入れない場合は前記第１のブロックに続くブロックのための前記分岐予測構造のエントリのセットにアクセスすることを含む、請求項１に記載の方法。
【請求項３】
前記第２のブロックのセットにおける前記第２の分岐命令の前記結果の前記投機的予測と同時に、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプ［７１０］を決定することをさらに含む、請求項１または２に記載の方法。
【請求項４】
前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定することは、前記少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定することを含む、請求項３に記載の方法。
【請求項５】
前記状態を選択的にフラッシュすることは、前記分岐命令のタイプのセットの第１のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答して、前記第２の分岐命令の前記結果の前記投機的予測に関連付けられる前記状態をフラッシュすることを含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記第１のサブセットは、呼び出し命令、戻り命令、及び間接分岐命令を含む、請求項５に記載の方法。
【請求項７】
前記予測された第２のブロックの第２のアドレスによってインデックス化される前記分岐予測構造のエントリに基づいて、前記第２のブロックの予測された第２のブロックにおける前記第２の分岐命令の少なくとも１つの投機的予測を再開することをさらに含む、請求項５または６に記載の方法。
【請求項８】
前記予測された第２のブロックは、前記第１のブロックにおける前記少なくとも１つの第１の分岐命令の予測された結果に対応する、請求項７に記載の方法。
【請求項９】
前記状態を選択的にフラッシュすることは、前記状態をフラッシュすることをバイパスし、前記分岐命令の前記タイプのセットの第２のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答して、前記投機的予測を継続することを含む、請求項５〜７のいずれか１項に記載の方法。
【請求項１０】
前記第１のブロックの前記第１のアドレスから所定数の最下位ビットをドロップすることによって、インデックスを前記分岐予測構造に生成することをさらに含む、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
第１のブロック［３０５］における少なくとも１つの第１の分岐命令［３２０］の結果を予測し、前記第１のブロックの第１のアドレスに基づいて、前記第１のブロックにおける前記少なくとも１つの第１の分岐命令の前記結果に対応する第２のブロックのセット［３１０、３１５］のための分岐予測構造［５００］のエントリのセットにアクセスするように構成される分岐予測器［２２０］と、
前記分岐予測構造の前記エントリのセットに基づいて、前記第２のブロックのセットにおける第２の分岐命令の結果の投機的予測のための命令をフェッチするフェッチロジック［２２５］と、を含み、
前記投機的予測に関連付けられる状態は、前記少なくとも１つの第１の分岐命令の少なくとも１つのタイプに基づいて、前記分岐予測器から選択的にフラッシュされる、装置。
【請求項１２】
前記分岐予測器は、前記少なくとも１つの第１の分岐命令の潜在的ターゲットである第２のブロックのセットまたは前記少なくとも１つの第１の分岐命令を受け入れない場合は前記第１のブロックに続くブロックのための前記分岐予測構造の前記エントリのセットにアクセスするように構成される、請求項１１に記載の装置。
【請求項１３】
前記分岐予測器は、前記第２のブロックのセットにおける前記第２の分岐命令の前記結果の前記投機的予測と同時に、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定するように構成される、請求項１１または１２に記載の装置。
【請求項１４】
前記分岐予測器は、前記少なくとも１つの第１の分岐命令の結果が、分岐ターゲットバッファ、間接分岐予測器、またはリターンアドレススタックによって決定されるかどうかに基づいて、前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプを決定するように構成される、請求項１３に記載の装置。
【請求項１５】
前記第２の分岐命令の前記結果の前記投機的予測に関連付けられる前記状態は、前記分岐命令のタイプのセットの第１のサブセットに属する前記少なくとも１つの第１の分岐命令の前記少なくとも１つのタイプに応答してフラッシュされる、請求項１１〜１４のいずれか１項に記載の装置。
【国際調査報告】
2021527892.tif 000012
2021527892.tif 000013