(57)【要約】【課題】  キャッシュされたメモリを用いるプロセッサにおいて命令及びデータを取り出すことについて改善された方法を提供する。【解決手段】  本発明の実施形態は、命令ラインをプリフェッチするための方法及び装置を提供する。方法は、レベル２キャッシュから第１の命令ラインをフェッチするステップと、第１の命令ラインにおいて、第１の命令ラインの外部にある命令をターゲットとする分岐命令を識別するステップと、識別された分岐命令からアドレスを抽出するステップと、抽出されたアドレスを用いて、レベル２キャッシュから、ターゲットとされた命令を含む第２命令ラインをプリフェッチするステップを含む。【選択図】      図２
2007207246.tif 000002
【特許請求の範囲】
【請求項１】
命令ラインをプリフェッチする方法であって、
（ａ）レベル２キャッシュから第１の命令ラインをフェッチするステップと、
（ｂ）前記第１の命令ラインにおいて、前記第１の命令ラインの外部にある命令をターゲットとする分岐命令を識別するステップと、
（ｃ）前記識別された分岐命令からアドレスを抽出するステップと、
（ｄ）前記抽出されたアドレスを用いて、前記レベル２キャッシュから前記ターゲットとされた命令を含む第２の命令ラインをプリフェッチするステップと、
を含む、方法。
【請求項２】
前記第２の命令ラインにおいて（ａ）から（ｄ）の前記ステップを繰り返して、分岐命令によってターゲットとされた命令を含む第３の命令ラインをプリフェッチするステップをさらに含む、請求項１に記載の方法。
【請求項３】
所定の数の命令ラインがプリフェッチされるまで（ａ）から（ｄ）の前記ステップを繰り返すステップをさらに含む、請求項１の記載の方法。
【請求項４】
所定の数の予測不可能な出口分岐命令を含む、複数のプリフェッチされた命令ラインが前記レベル２キャッシュからプリフェッチされるまで、（ａ）から（ｄ）の前記ステップを繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記第１の命令ラインにおいて、前記第１の命令ラインの外部にある第２の命令をターゲットとする第２の分岐命令を識別するステップと、
前記識別された第２の分岐命令から第２のアドレスを抽出するステップと、
前記抽出された第２のアドレスを用いて、前記レベル２キャッシュから、前記ターゲットとされた第２の命令を含む第３の命令ラインをプリフェッチするステップと、
をさらに含む、請求項１の記載の方法。
【請求項６】
前記抽出されたアドレスが、前記第１の命令ラインに付加された有効アドレスとして格納される、請求項１に記載の方法。
【請求項７】
前記有効アドレスが、前の識別された分岐命令の実行の間に算出される、請求項６に記載の方法。
【請求項８】
前記第１の命令ラインが、前記第１の命令ラインの外部にある２以上の命令をターゲットとする２以上の分岐命令を含み、前記第１の命令ラインに格納されている分岐履歴値が、前記識別された分岐命令が前記第１の命令ラインについての予測された分岐であることを示す、請求項１に記載の方法。
【請求項９】
レベル２キャッシュと、
１以上の命令を含む命令ラインを前記レベル２キャッシュから受信するように構成されたレベル１キャッシュと、
前記レベル１キャッシュから取り出された命令を実行するように構成されたプロセッサ・コアと、
（ａ）レベル２キャッシュから第１の命令ラインをフェッチし、
（ｂ）前記第１の命令ラインにおいて、前記第１の命令ラインの外部にある命令をターゲットとする分岐命令を識別し、
（ｃ）前記識別された分岐命令からアドレスを抽出し、
（ｄ）前記抽出されたアドレスを用いて、前記レベル２キャッシュから前記ターゲットとされた命令を含む第２の命令ラインをプリフェッチするように構成された回路と、
を備える、プロセッサ。
【請求項１０】
１以上の命令を含む命令ラインに出口分岐アドレスを格納する方法であって、
命令ラインに含まれる１以上の命令を実行するステップと、
前記１以上の命令のうちの１つが別の命令ラインにある命令に分岐するかどうかを判定するステップと、
分岐すると判定されたことを条件に、前記他の命令ラインに対応する命令ラインに出口アドレスを格納するステップと、
を含む方法。
【請求項１１】
前記格納された出口アドレスを有する前記命令ラインを、レベル２キャッシュに書戻すステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記１以上の命令のうちの１つに対応する分岐履歴情報を前記命令ラインに格納するステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記命令ラインにある１以上の命令のその後の実行の間に、前記命令ラインにある１以上の命令のうちの第２の命令を実行するステップと、
前記１以上の命令のうちの第２の命令が第２の命令ラインにある第２の命令に分岐する場合に、前記１以上の命令のうちの１つに対応する前記分岐履歴情報が、前記分岐が予測可能であることを示すかどうかを判定するステップと、
前記分岐が予測可能ではなかった場合に、前記第２の命令ラインに対応する命令ラインに第２の出口アドレスを格納するステップと、
をさらに含む、請求項１２に記載の方法。
【請求項１４】
前記出口アドレスを格納するステップは、複数の命令ラインが繰り返し実行される最初の実行フェーズの間に行われる、請求項１０に記載の方法。
【請求項１５】
前記格納された出口アドレスを有する前記命令ラインをレベル２キャッシュに格納するステップと、
前記レベル２キャッシュから前記付加された出口アドレスを有する前記命令ラインをフェッチし、前記命令ラインをレベル１キャッシュに配置するステップと、
前記命令ラインに付加された前記出口アドレスを用いて、他の命令ラインをプリフェッチするステップと、
をさらに含む、請求項１０に記載の方法。
【請求項１６】
前記出口アドレスは、前記出口分岐命令の実行がキャッシュ・ミスを引き起こす場合にのみ前記命令ラインに付加される、請求項１７に記載の方法。
【請求項１７】
前記出口アドレスは、前記１以上の命令のうちの１つの実行の間に算出された有効アドレスである、請求項１０に記載の方法。
【請求項１８】
命令ラインに含まれる１以上の命令を実行するように構成されたプロセッサ・コアと、
前記１以上の命令のうちの１つが別の命令ラインにある命令に分岐するかどうかを判定し、分岐すると判定されたことを条件に、前記他の命令ラインに対応する命令ラインに出口アドレスを格納するように構成された回路と、
を備える、プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータ・プロセッサの分野に関する。より具体的には、本発明は、コンピュータ・プロセッサによって用いられるキャッシュ機構に関する。
【背景技術】
【０００２】
現代のコンピュータ・システムは、一般的に、コンピュータ・システム内の情報を処理するために使用することができるプロセッサを含む、数個の集積回路（ＩＣ）を備える。プロセッサによって処理されたデータは、プロセッサによって実行されるコンピュータ命令を含み、さらに、そのコンピュータ命令を用いるプロセッサによって取り扱われるデータを含むことができる。一般的に、コンピュータ命令およびデータは、コンピュータ・システムのメイン・メモリに格納される。
【０００３】
プロセッサは、一般的に、一連の小ステップに分けて命令を実行することによって命令を処理する。プロセッサによって処理される命令の数を増やす（そしてプロセッサの速度を上げる）ために、プロセッサをパイプラインすることができる場合がある。ここで、「パイプラインする」とは、各々が１つの命令を実行するために必要な小ステップの１以上を行う独立した段を、プロセッサに提供することをいう。パイプラインは（他の回路に加えて）、プロセッサ・コアと呼ばれるプロセッサの一部に配置することができる。プロセッサは、複数のプロセッサ・コアを有することができる場合がある。
【０００４】
パイプラインにおける命令実行の１つの例として、第１の命令が受信されたときに、第１のパイプライン段はその命令の小部分を処理することができる。第１のパイプライン段がその命令の小部分の処理を終了したときに第２のパイプライン段が第１の命令の別の小部分の処理を開始することができ、その間に第１のパイプライン段は第２の命令を受信し、その小部分の処理を開始する。このようにして、プロセッサは、２以上の命令を同時に（並行して）処理することができる。
【０００５】
データおよび命令へのより高速のアクセス、および、プロセッサのより良好な活用を提供するために、プロセッサは、数個のキャッシュを有することができる。キャッシュとは、一般的に、メイン・メモリより小さく、プロセッサと同じダイ（すなわちチップ）上に製造されるメモリである。現代のプロセッサは、一般的に、複数のレベルのキャッシュを有する。プロセッサ・コアの最も近辺に設置される最も高速のキャッシュは、レベル１キャッシュ（Ｌ１キャッシュ）と呼ばれる。プロセッサは、一般的に、Ｌ１キャッシュに加えて、レベル２キャッシュ（Ｌ２キャッシュ）と呼ばれる、第２のより大型のキャッシュを有する。プロセッサは、他の付加的なレベルのキャッシュを有することもある（例えば、Ｌ３キャッシュおよびＬ４キャッシュ）。
【０００６】
プロセッサにプロセッサのパイプラインの各段を満たすのに十分な命令を与えるために、プロセッサは、Ｌ２キャッシュから命令ラインと呼ばれる複数の命令を含んだグループの形で命令を取り出すことができる。取り出された命令ラインはＬ１命令キャッシュ（Ｉ−キャッシュ）に配置することができ、プロセッサ・コアは命令ラインにある命令にアクセスすることができる。同様に、プロセッサによって処理されるべきデータ・ブロックは、Ｌ２キャッシュから取り出し、Ｌ１キャッシュ・データ・キャッシュ（Ｄ−キャッシュ）に配置することができる。
【０００７】
より上位レベルのキャッシュから情報を取り出し、その情報をより下位レベルのキャッシュに配置するプロセスは「フェッチする」と称され、一般的に、ある程度の時間（待ち時間）を要する。例えば、プロセッサ・コアが情報を要求し、その情報がＬ１キャッシュに存在しなかった場合（これはキャッシュ・ミスと呼ばれる）、その情報をＬ２キャッシュからフェッチすることができる。要求された情報のために次のレベルのキャッシュ／メモリが検索されることから、キャッシュ・ミスは付加的な待ち時間をもたらす。例えば、要求された情報がＬ２キャッシュに存在しなかった場合には、プロセッサは、Ｌ３キャッシュやメイン・メモリの中にその情報を探すであろう。
【０００８】
プロセッサは、ある命令およびデータを、キャッシュおよび／またはメモリから取り出される命令およびデータよりも速く処理することができる場合がある。例えば、命令ラインが処理された後で、処理されるべき次の命令ラインにアクセスするために時間がかかる場合がある（例えば、次の命令を含む命令ラインを求めてＬ１キャッシュが検索された時に、キャッシュ・ミスがあった場合など）。プロセッサがより上位レベルのキャッシュまたはメモリから次の命令ラインを取り出している間に、パイプライン段は前の命令の処理を終了し、それ以上処理する命令が残っていない場合がある（これは、パイプライン停止と呼ばれる）。パイプラインが停止したときには、プロセッサは活用されておらず、パイプラインされたプロセッサ・コアによって得られる利益を失うことになる。
【０００９】
命令（そして命令ライン）は、一般的に、逐次的に処理されることから、プロセッサは、逐次的にアドレスされた命令ラインのブロックをフェッチすることによって、パイプライン停止を防ぐことを試みる場合がある。逐次的にアドレスされた命令ラインのブロックをフェッチすることにより、次の命令ラインは必要とされた時に既にＬ１キャッシュにおいて利用可能となることができ、したがって、プロセッサ・コアは、現行の命令ラインにある命令の処理を終了したときに、次の命令ラインにある命令に容易にアクセスすることができることとなる。
【００１０】
逐次的にアドレスされた命令ラインのブロックをフェッチしても、パイプライン停止を防ぐことができない場合がある。例えば、出口分岐（ｅｘｉｔ  ｂｒａｎｃｈ）命令と呼ばれる命令は、プロセッサを、逐次的にアドレスされた命令ラインのブロックの外部にある命令（ターゲット命令と呼ばれる）へ分岐させる場合がある。ここで、出口分岐命令は、現行の命令ラインに存在しないかまたは次の逐次的にアドレスされ既にフェッチされた命令ラインに存在するターゲット命令へ分岐する場合がある。したがって、分岐が行われるとプロセッサが判定したときに、出口分岐のターゲット命令を含む次の命令ラインは、Ｌ１キャッシュにおいて利用可能とならない場合がある。その結果として、パイプラインが停止し、プロセッサが非効率的に動作する場合がある。
【００１１】
データをフェッチすることに関して、命令がデータにアクセスする場合に、プロセッサが、Ｌ１キャッシュにあるデータを含むデータ・ラインを見つけることを試みる場合がある。データ・ラインがＬ１キャッシュにおいて見つけられなかった場合には、所望のデータ・ラインを求めてＬ２キャッシュ、および、上位のメモリが検索されている間、プロセッサが停止する場合がある。所望のデータのアドレスは命令が実行されるまで知られないことから、プロセッサは、その命令が実行されるまで所望のデータ・ラインを検索することができない場合がある。プロセッサが実際にデータ・ラインを検索したときに、キャッシュ・ミスが起こってパイプラインが停止することがある。
【００１２】
プロセッサは、現行のアクセスされているデータ・アドレスに近いデータ・アドレスを含むデータ・ラインのブロックをフェッチすることによって、こうしたキャッシュ・ミスを防ぐようにされる場合がある。近傍のデータ・ラインをフェッチすることは、あるデータ・ラインに存在するデータ・アドレスがアクセスされたときに、その近傍のデータ・アドレスもまた通常アクセスされるという仮定に依拠している（この仮定は「参照の局所性」と呼ばれる）。しかし、この仮定が正しくない場合もあり、そのような場合、命令により現行のデータ・ラインの近傍に位置していないデータ・ラインにあるデータがアクセスされることによって、キャッシュ・ミスおよびプロセッサの非効率性がもたらされる。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、キャッシュされたメモリを用いるプロセッサにおいて命令およびデータを取り出すことについて改善された方法に対する必要性が存在する。
【課題を解決するための手段】
【００１４】
本発明の実施形態は、命令ラインをプリフェッチするための方法および装置を提供する。本発明の実施形態において、方法は、（ａ）レベル２キャッシュから第１の命令ラインをフェッチするステップと、（ｂ）第１の命令ラインにおいて、第１の命令ラインの外部にある命令をターゲットとする分岐命令を識別するステップと、（ｃ）識別された分岐命令からアドレスを抽出するステップと、（ｄ）抽出されたアドレスを用いて、レベル２キャッシュから、ターゲットとされた命令を含む第２の命令ラインをプリフェッチするステップを含む。
【００１５】
本発明の実施形態においては、プロセッサが提供される。プロセッサは、レベル１キャッシュと、レベル２キャッシュと、プロセッサ・コアと、回路とを備える。レベル１キャッシュは、レベル２キャッシュから、１以上の命令を含む命令ラインを受信するように構成される。プロセッサ・コアは、レベル１キャッシュから取り出された命令を実行するように構成される。回路は、（ａ）レベル２キャッシュから第１の命令ラインをフェッチし、（ｂ）第１の命令ラインにおいて、第１の命令ラインの外部にある命令をターゲットとする分岐命令を識別し、（ｃ）識別された分岐命令からアドレスを抽出し、（ｄ）抽出されたアドレスを用いて、レベル２キャッシュから、ターゲットとされた命令を含む第２の命令ラインをプリフェッチするように構成される。
【００１６】
本発明の実施形態においては、命令ラインに出口分岐アドレスを格納する方法が提供される。命令ラインは１以上の命令を含む。方法は、命令ラインにある１以上の命令のうちの１つを実行するステップと、１以上の命令のうちの１つが別の命令ラインにある命令に分岐するかどうかを判定するステップと、分岐すると判定されたことを条件に、他の命令ラインに対応する命令ラインに出口アドレスを格納するステップを含む。
【発明を実施するための最良の形態】
【００１７】
本発明の上記の特徴、利点、および目的が得られる手法が詳細に理解できるように、上記で要約された本発明のより具体的な説明が、添付の図面に示されている本発明の実施形態を参照することによってなされる。
【００１８】
しかし、添付の図面は本発明の典型的な実施形態のみを図示するものであって、本発明の範囲を限定するものと見なされるべきではないことに留意すべきである。
【００１９】
本発明の実施形態は、命令ラインをプリフェッチするための方法および装置を提供する。本発明の実施形態においては、命令ラインの外部にあるターゲット命令に分岐する「出口分岐命令」について、フェッチされている命令ラインを検査することができる。このような出口分岐命令のターゲット・アドレスを抽出して、ターゲットにされた命令を含む命令ラインをＬ２キャッシュからプリフェッチするために用いることができる。その結果として、出口分岐がとられた場合に、ターゲットにされた命令ラインは、既にＬ１命令キャッシュ（「Ｉ−キャッシュ」）に存在するようにすることができ、そうすることによって、コストのかかる命令キャッシュ・ミスをなくして全体の性能を向上させることができる。
【００２０】
本発明の実施形態においては、プリフェッチ・データは、プリフェッチ・データが属する対応する情報ブロック（例えば命令ラインまたはデータ・ライン）の形で従来のキャッシュ・メモリに格納することができる。対応する情報ブロックがキャッシュ・メモリからフェッチされる際に、情報ブロックを検査して、他の関連する情報ブロックをプリフェッチするために用いることができる。次いで、各々の他のプリフェッチされた情報ブロックに格納されたプリフェッチ・データを用いて、プリフェッチを行うことができる。フェッチされた情報ブロック内の情報を用いて、フェッチされた情報ブロックに関連する他の情報ブロックをプリフェッチすることにより、フェッチされた情報ブロックに関係するキャッシュ・ミスを防ぐことができる。
【００２１】
本発明の実施形態によれば、プリフェッチ・データおよび予測データを情報ブロックの一部として従来のキャッシュに格納することにより、プリフェッチ・データおよび予測データ（例えば、データ・ラインおよび／または命令ラインのためのプリフェッチ・データおよび予測データ）を排他的に格納する特別なキャッシュまたはメモリの不要とすることができる。しかし、かかる情報を命令ラインに格納することに関して以下に説明するが、かかる情報は、履歴情報の格納を専門とする特別なキャッシュまたはメモリを含むいかなる位置に格納してもよい。異なるキャッシュ（およびキャッシュ・ライン）、バッファ、専用キャッシュ、および他の位置の組み合わせを用いて、ここに説明された履歴情報を格納することができる場合がある。
【００２２】
以下は、添付の図面に図示された本発明の実施形態の詳細な説明である。本発明の実施形態はあくまで例示であり、本発明を明確に教示するため、詳細なものとなっている。しかし、開示された詳細な説明は、実施形態の予期される変形物を排除することを意図しておらず、逆に、添付の特許請求の範囲によって定められる本発明の精神および範囲内にある全ての修正物、均等物、および代替物を包含することを意図している。
【００２３】
本発明の実施形態は、例えばコンピュータ・システムなどのシステムとともに用いることができ、そのようなシステムに関して説明される。本明細書において用いられるシステムという用語は、パーソナル・コンピュータ、インターネット機器、ディジタル・メディア機器、携帯情報端末（ＰＤＡ）、携帯型音楽／映像再生機、およびビデオゲーム機を含めた、プロセッサおよびキャッシュ・メモリを用いるいかなるシステムも含む。キャッシュ・メモリは、そのキャッシュ・メモリを使用するプロセッサと同じダイに設置することができるが、プロセッサとキャッシュ・メモリは、異なるダイ（例えば、独立したモジュール内の独立したチップ、または単一のモジュール内の独立したチップ）に設置することもできる。
【００２４】
本発明の実施形態は、各々がパイプラインを用いて命令を実行する複数のプロセッサ・コアと複数のＬ１キャッシュとを有するプロセッサに関して以下で説明されるが、単一の処理コアを有するプロセッサおよび／または命令の実行にパイプラインを用いないプロセッサを含む、キャッシュを用いるいずれかのプロセッサとともに用いることもできる。一般的に、本発明の実施形態は、いかなるプロセッサとも用いることができ、特定の構成に限定されない。
【００２５】
本発明の実施形態は、以下で、Ｌ１命令キャッシュ（Ｌ１  Ｉ−キャッシュ）とＬ１データ・キャッシュ（Ｌ１  Ｄ−キャッシュ）に分割されたＬ１キャッシュを有するプロセッサに関して説明されるが、統合されたＬ１キャッシュが用いられるような構成において用いることができる。さらに、本発明の実施形態は、命令ラインおよびデータ・ラインをＬ２キャッシュからプリフェッチすること、および、プリフェッチされたラインをＬ１キャッシュに配置することに関して説明されるが、いずれかのキャッシュまたはメモリ・レベルから別のいずれかのキャッシュまたはメモリ・レベルへ命令ラインおよびデータ・ラインをプリフェッチするために用いることもできる。
【００２６】
（例示的なシステムの概要）
図１は、本発明の実施形態によるシステム１００を図示するブロック図である。システム１００は、命令およびデータを格納するためのシステム・メモリ１０２、グラフィックス処理のためのグラフィックス処理装置１０４、外部デバイスと通信するためのＩ／Ｏインターフェース、命令およびデータを長期格納するためのストレージ・デバイス１０８、命令およびデータを処理するためのプロセッサ１１０を含むことができる。
【００２７】
本発明の実施形態により、プロセッサ１１０は、Ｌ２キャッシュ１１２、複数のＬ１キャッシュ１１６を有することができ、Ｌ１キャッシュ１１６の各々は、複数のプロセッサ・コア１１４の１つによって用いられる。ある実施形態によれば、プロセッサ・コア１１４の各々はパイプラインすることができ、命令の各々は一連の小ステップの形で実施され、ステップの各々は異なるパイプライン段によって実施される。
【００２８】
図２は、本発明の実施形態によるプロセッサ１１０を図示するブロック図である。簡略化のために、図２は、プロセッサ１１０の単一のコア１１４を図示し、これに関して説明される。ある実施形態においては、コア１１４の各々は、同一のものとすることができる（例えば、同一のパイプライン段を伴う同一のパイプラインを含む）。別の実施形態においては、コア１１４の各々は異なるものとすることができる（例えば、異なる段を伴う異なるパイプラインを含む）。
【００２９】
本発明の実施形態においては、Ｌ２キャッシュは、プロセッサ１１０によって使用される命令およびデータの一部を格納することができる。プロセッサ１１０は、Ｌ２キャッシュ１１２に格納されていない命令およびデータを要求する場合がある。要求された命令およびデータがＬ２キャッシュ１１２に格納されていない場合には、要求された命令およびデータを（上位のレベルのキャッシュまたはシステム・メモリ１０２から）取り出して、Ｌ２キャッシュに配置することができる。プロセッサ・コア１１４がＬ２キャッシュ１１２から命令を要求したときに、その命令を、まずプリデコーダおよびスケジューラ２２０で処理することができる（以下でより詳細に説明する）。
【００３０】
本発明の実施形態においては、図１に図示されたＬ１キャッシュ１１６は、２つの部分、すなわち、命令ラインを格納するためのＬ１命令キャッシュ２２２、および、データ・ラインを格納するためのＬ１データ・キャッシュ２２４に分割することができる。Ｌ２キャッシュ１１２から取り出された命令ラインがプリデコーダおよびスケジューラ２２０によって処理された後で、命令ラインを命令キャッシュ２２２に配置することができる。
【００３１】
本発明の実施形態においては、命令は、命令ラインと呼ばれるグループとしてＬ２キャッシュ１１２および命令キャッシュ２２２からフェッチして、プロセッサ・コア１１４が命令ラインにある命令にアクセスすることができる命令ライン・バッファ２２６に配置することができる。ある実施形態においては、命令キャッシュ２２２および命令ライン・バッファ２２６の一部は、有効アドレスおよび制御ビット（ＥＡ／ＣＴＬ）を格納するために用いることができ、それらは、命令ラインの各々を処理して、例えば以下で説明される命令プリフェッチ機構を実行するために、コア１１４および／またはプリデコーダおよびスケジューラ２２０によって用いられることができる。
【００３２】
（Ｌ２キャッシュからの命令ラインのプリフェッチ）
図３は、本発明の実施形態による、例示的な複数の命令ラインを示す図である。ある実施形態においては、各々の命令ラインは、複数の命令（例えば、Ｉ１、Ｉ２、Ｉ３・・・、など）、並びに、有効アドレスおよび制御ビットなどの制御情報を格納することができる。ある規模においては、命令ラインの各々にある命令は順番に実行され、それにより、命令Ｉ１が第一に実行され、Ｉ２が第二に実行され、以下続くことになる。命令が順番に実行され、命令ラインもまた順番に実行される。したがって、いくつかの場合においては、命令ラインがＬ２キャッシュ１１２から命令キャッシュ２２２に移動される度ごとに、プリデコーダおよびスケジューラ２２０は、命令ライン（例えば命令ライン１）を検査して、次の逐次的な命令ライン（例えば命令ライン２）をプリフェッチし、そのことにより、次の命令ラインが命令キャッシュ２２２に配置され、プロセッサ・コア１１４によりアクセスできるようにすることができる。
【００３３】
プロセッサ・コア１１４によって実行される命令ラインは、分岐命令（例えば、条件付き分岐命令）を含むことができる場合がある。分岐命令は、別の命令（ここではターゲット命令と呼ばれる）に分岐する命令である場合がある。ターゲット命令は、分岐命令と同じ命令ライン内にある。例えば、図３に示される命令Ｉ２１は、特定の条件が満たされる場合に（例えば、メモリに格納された値がゼロである場合に）ターゲット命令Ｉ４１が実行されるべきであることを指定する。ターゲット命令を含む命令ライン（命令ライン１）は既に命令キャッシュ２２２に存在するので、命令Ｉ４１への分岐がとられる場合に、命令キャッシュ・ミスはおこらず、プロセッサ・コア１１４が効率的に命令を処理し続けることができる。
【００３４】
分岐命令は、分岐命令を含む現在の命令ラインの外部にある命令に分岐することができる場合がある。現在の命令ライン以外の命令ラインに分岐する分岐命令は、ここでは出口分岐命令または出口分岐と呼ばれる。出口分岐命令は、無条件分岐命令（例えば、常に分岐する）かまたは条件付き分岐命令（例えばゼロに等しい場合に分岐する）とすることができる。例えば、命令ライン１にある命令Ｉ５１は、対応する条件が満たされる場合に命令ライン２にある命令Ｉ４２に分岐する条件付き分岐命令とすることができる。いくつかのケースでは、命令ライン２のフェッチが成功し、既に命令キャッシュ２２２に配置されているとみなす条件付き分岐がとられる場合、プロセッサ・コア１１４は、命令キャッシュ・ミスなしに命令キャッシュ２２２からの命令Ｉ４２の要求に成功することができる。
【００３５】
しかし、条件付き分岐命令（例えば命令Ｉ６１）が、命令キャッシュ２２２に配置されていない命令ラインにある命令（例えば命令ラインＸにある命令Ｉ４ｘ）に分岐して、キャッシュ・ミスを引き起こし、プロセッサ１１０の動作が非効率になる場合がある。
【００３６】
本発明の実施形態によれば、現在フェッチされている命令ラインから抽出された出口分岐アドレスによってターゲット命令ラインをプリフェッチすることにより、命令キャッシュ・ミスの数を減少させることができる。
【００３７】
図４は、本発明の実施形態による、命令キャッシュ・ミスをなくすためのプロセス４００を図示する流れ図である。プロセス４００は、Ｌ２キャッシュ１１２から命令ラインがフェッチされるステップ４０４で開始することができる。ステップ４０６において、命令ラインから抜け出す分岐命令を識別することができ、ステップ４０８において、出口分岐命令のターゲットとされた命令のアドレス（分岐出口アドレスと呼ばれる）を抽出することができる。次いで、ステップ４１０において、分岐出口アドレスを用いて、Ｌ２キャッシュ１１２からターゲットとされた命令を含む命令ラインをプリフェッチすることができる。ターゲットとされた命令を含む命令ラインをプリフェッチし、プリフェッチされた命令を命令キャッシュ２２２に配置することにより、出口分岐がとられた場合のキャッシュ・ミスを防ぐことができる。
【００３８】
ある実施形態においては、分岐出口アドレスは、直接、命令ラインに格納する（付加する）ことができる。図５は、本発明の一実施形態に係る命令ライン分岐出口アドレス（ＥＡＩ）を含む命令ライン（命令ライン１）を示すブロック図である。格納される分岐出口アドレスＥＡ１は、有効アドレスまたは有効アドレスの一部とすることができる。図示されたように、分岐出口アドレスＥＡ１は、分岐命令Ｉ６１のターゲットとされた命令Ｉ４Ｘを含む命令ラインを識別することができる。
【００３９】
ある実施形態により、命令ラインはまた、他の有効アドレス（例えばＥＡ２）および制御ビット（例えばＣＴＬ）を格納することもできる。以下で説明されるように、他の有効アドレスは、命令ラインにあるデータ・アクセス命令に対応するデータ・ラインまたは付加的な分岐命令アドレスをプリフェッチするために用いることができる。制御ビットＣＴＬは、分岐命令の履歴（ＣＢＨ）を示す１以上のビット、および、命令ライン内の分岐命令の位置（ＣＢ−ＬＯＣ）を示す１以上のビットを含むことができる。命令ラインに格納される情報の用途もまた以下で説明される。
【００４０】
（例示的なプリフェッチ回路）
図６は、本発明の実施形態による、命令およびデータ・ラインをプリフェッチするための回路を図示するブロック図である。本発明の実施形態においては、回路は、データ・ラインのみまたは命令ラインのみをプリフェッチすることができる。本発明の別の実施形態においては、回路は、命令ラインとデータ・ラインの両方をプリフェッチすることができる。
【００４１】
命令ラインまたはデータ・ラインがＬ２キャッシュ１１２からフェッチされて命令キャッシュ２２２またはデータ・キャッシュ２２４に配置されるたびに、命令／データ（Ｉ／Ｄ）によって制御される選択回路６２０は、フェッチされた命令ラインまたはデータ・ラインを、適切なキャッシュに送ることができる。
【００４２】
プリデコーダおよびスケジューラ２２０は、Ｌ２キャッシュ１１２によって出力された情報を検査することができる。複数のプロセッサ・コア１１４が用いられるある実施形態においては、複数のプロセッサ・コアの間で単一のプリデコーダおよびスケジューラ２２０を共有することができる。別の実施形態においては、プリデコーダおよびスケジューラ２２０は、プロセッサ・コア１１４の各々に個別に提供される。
【００４３】
ある実施形態においては、プリデコーダおよびスケジューラ２２０は、Ｌ２キャッシュ１１２によって出力された情報が命令ラインであるかデータ・ラインであるかを判定するプリデコーダ制御回路６１０を有することができる。例えば、Ｌ２キャッシュ１１２は、Ｌ２キャッシュ１１２に格納された情報ブロックの各々に特定のビットを設定することができ、プリデコーダ制御回路６１０はその特定のビットを検査して、Ｌ２キャッシュ１１２によって出力された情報ブロックが命令ラインであるかデータ・ラインであるかを判定することができる。
【００４４】
プリデコーダ制御回路６１０が、Ｌ２キャッシュ１１２によって出力された情報が命令ラインであると判定した場合、プリデコーダ制御回路６１０は、命令ライン・アドレス選択回路６０４およびデータ・ライン・アドレス選択回路６０６を使って、命令ラインに格納されるいずれかの適切な有効アドレス（例えばＥＡ１、またはＥＡ２）を選択することができる。次いで、選択（ＳＥＬ）信号を用い、選択回路６０８によって、有効アドレスを選択することができる。次いで、選択された有効アドレスを、例えば対応する命令ラインまたはデータ・ラインをＬ２キャッシュ１１２からプリフェッチするために使われる３２ビットのプリフェッチ・アドレスとして、プリフェッチ回路６０２に出力することができる。
【００４５】
フェッチされた命令ラインは、メイン・メモリ（例えば出口分岐命令によってターゲットとされた命令を含む）からプリフェッチされるべき第２の命令ラインに対応する単一有効アドレスを格納することができる場合がある。他の場合には、命令ラインは、メイン・メモリからプリフェッチされるべきターゲット命令ラインの有効アドレス、および、メイン・メモリからプリフェッチされるべきターゲットデータ・ラインの有効アドレスを格納することができる。他の実施形態においては、各命令ラインは、メイン・メモリからプリフェッチされるべき複数の命令ラインおよび／または複数のデータ・ラインについての有効アドレスを格納することができる。ある実施形態によれば、命令ラインがプリフェッチされるべき複数の有効アドレスを格納している場合、アドレスは、プリフェッチ回路６０２に有効アドレスの各々が送信されている間、（例えば、プリデコーダ制御回路６１０、または命令ライン・アドレス選択回路６０４、または何らかの他のバッファに）アドレスを一時的に格納することができる。別の実施形態においては、プリフェッチ・アドレスは、プリフェッチ回路６０２および／またはＬ２キャッシュ１１２に並列に送信することができる。
【００４６】
プリフェッチ回路６０２は、要求された有効アドレスがＬ２キャッシュ１１２にあるか否かを判定することができる。例えば、プリフェッチ回路６０２は、要求された有効アドレスがＬ２キャッシュ１１２にあるか否かを判定することができる変換索引バッファ（ＴＬＢ）のような内容アドレス可能メモリ（ｃｏｎｔｅｎｔ  ａｄｄｒｅｓｓａｂｌｅ  ｍｅｍｏｒｙ）（ＣＡＭ）を格納することができる。要求された有効アドレスがＬ２キャッシュ１１２にあった場合には、プリフェッチ回路６０２は、要求された有効アドレスに対応する実アドレスをフェッチする要求を、Ｌ２キャッシュに発行することができる。次いで、実アドレスに対応する情報ブロックを選択回路６２０に出力し、適切なＬ１キャッシュ（例えば命令キャッシュ２２２、またはデータ・キャッシュ２２４）に向けることができる。プリフェッチ回路６０２が、要求された有効アドレスはＬ２キャッシュ１１２に存在しないと判定した場合には、プリフェッチ回路は、より上位レベルのキャッシュおよび／またはメモリに信号を送信することができる。例えば、プリフェッチ回路６０２はＬ３キャッシュにアドレスのプリフェッチ要求を送信することができ、次いでＬ３キャッシュは要求されたアドレスを検索される。
【００４７】
プリデコーダおよびスケジューラ２２０が命令ラインまたはデータ・ラインをＬ２キャッシュ１１２からプリフェッチすることを試みる前に、プリデコーダおよびスケジューラ２２０（または随意的にプリフェッチ回路６０２）は、要求されプリフェッチされる命令ラインまたはデータ・ラインが既に命令キャッシュ２２２またはデータ・キャッシュ２２４に格納されているか否かを判定することができる場合がある。要求された命令ラインまたはデータ・ラインが既に命令キャッシュ２２２またはデータ・キャッシュ２２４に設置されていた場合には、Ｌ２キャッシュ・プリフェッチは必ずしも必要ではなく、したがって、行われない場合もある。プリフェッチが不必要となる場合においては、現行の有効アドレスを命令ラインに格納することは、やはり必ずしも必要ではなく、命令ラインに他の有効アドレスが格納されることが可能となる（以下で説明する）。
【００４８】
ある実施形態においては、プリフェッチされた情報ラインの各々がＬ２キャッシュ１１２からフェッチされる際に、プリフェッチされた情報はまた、プリフェッチされた情報ラインが命令ラインであるかどうかを判定するためにプリデコーダおよびスケジューラ回路２２０によって試験することができる。プリフェッチされた情報が命令ラインである場合には、プリフェッチされた命令ラインが、例えば、プリフェッチされた命令ラインにある分岐命令によってターゲットとされた命令を格納している別の命令ラインに対応するいずれかの有効アドレスを格納するかどうかを判定するために、プリデコーダ制御回路６１０によって命令ラインを試験することができる。プリフェッチされた命令ラインが別の命令ラインを指す有効アドレスを含む場合には、他の命令ラインをプリフェッチしても良い。第２のプリフェッチされた命令ラインに対して同じプロセスを繰り返して、各命令ラインに格納された分岐出口アドレスに基づいて複数の命令ラインのチェーンをプリフェッチすることができる。
【００４９】
本発明の実施形態においては、プリデコーダおよびスケジューラ２２０は、所定の数（閾値数）の命令ラインおよび／またはデータ・ラインがフェッチされるまで、命令ライン（およびデータ・ライン）のプリフェッチを続行することができる。閾値は、いずれかの適切な方法で選択することができる。例えば、閾値は、命令キャッシュに配置することができる命令ラインの数および／またはデータ・キャッシュに配置することができるデータ・ラインの数に基づいて選択することができる。命令キャッシュおよび／またはデータ・キャッシュがより大きな容量を有する場合には大きなプリフェッチ所定の数を選択することができるが、命令キャッシュおよび／またはデータ・キャッシュがより小さな容量を有する場合には小さなプリフェッチ所定の数を選択することができる。
【００５０】
別の例として、プリフェッチの所定の数は、フェッチされた命令ライン内の条件付き分岐命令の予測可能性に基づいて選択することができる。いくつかの場合においては、条件付き分岐命令の結果（その分岐が取られるか否か）が予測可能となることがあり、したがって、プリフェッチするべき適正な命令ラインが予測可能となることがある。しかし、命令ラインの間の分岐予測の数が増大するに従い、全体の予測精度は小さくなることがあり、そのことにより、与えられた命令ラインがアクセスされることになる可能性は小さくなる場合がある。予測不可能性のレベルは、予測不可能な分岐命令を用いるプリフェッチの数が増大するにしたがって、増大する場合がある。
【００５１】
したがって、ある実施形態においては、プリフェッチの所定の数は、予測された、プリフェッチされた命令ラインにアクセスする可能性が、所定の率を下回らないように選び出される。選び出された閾値は、サンプル命令のテスト・ランにより選択された固定の数とすることができる場合がある。テスト・ランおよび閾値の選択は設計時に行うことができ、閾値は、プロセッサ１１０に予めプログラムすることができる場合がある。随意的に、テスト・ランは、プログラム実行の最初の「トレーニング」フェーズの間に起こることがある（以下で詳細に説明される）。別の実施形態においては、プロセッサ１１０は、予測不可能な分岐命令を格納しているプリフェッチされた命令ラインの数を追跡して、予測不可能な分岐命令を格納している所定の数の命令ラインがフェッチされた後にのみ命令ラインのプリフェッチを止め、そのことにより、プリフェッチされた命令ラインの所定の数が命令ラインの内容に基づいて動的に変化するようにすることができる。また、いくつかのケースでは、予測不可能な分岐（例えば分岐についての予測可能性の値が予測可能性の閾値を下回る場合の分岐）に達する場合、分岐命令の両方のパスについて（例えば予測された分岐パスと予測されていない分岐パスとの両方について）命令ラインをフェッチすることができる。
【００５２】
（命令ラインのための分岐出口アドレスの格納）
本発明の実施形態により、命令ライン内の分岐命令と、かかる分岐命令のターゲットに対応する分岐出口アドレスを、命令ラインにある命令を実行することによって判定することができる。命令ラインにある命令の実行はまた、分岐命令の分岐履歴を記録し、それにより分岐が別の命令ラインにあるターゲット命令へ続いて命令キャッシュ・ミスを引き起こす可能性を判定するために用いることができる。
【００５３】
図７は、本発明の実施形態による、出口分岐命令に対応する分岐出口アドレスを格納するためのプロセス７００を図示する流れ図である。プロセス７００は、例えば命令キャッシュ２２２から命令ラインがフェッチされるステップ７０４で開始することができる。ステップ７０６において、フェッチされた命令ラインの中の出口分岐を実行することができる。ステップ７０８において、出口分岐がとられた場合に、出口分岐によってターゲットとされた命令がフェッチされた命令ラインに位置するか否かの判定を行うことができる。出口分岐によってターゲットとされた命令が命令ラインに存在しない場合には、ステップ７１０において、ターゲットとされた命令の有効アドレスが出口アドレスとして格納される。ターゲットとされた命令に対応する分岐出口アドレスを記録することにより、次にＬ２キャッシュ１１２から命令ラインがフェッチされたときに、Ｌ２キャッシュ１１２から、ターゲットとされた命令を格納している命令ラインをプリフェッチすることができる。
【００５４】
本発明の実施形態においては、分岐出口アドレスは、その分岐出口アドレスに分岐する分岐命令が実行されるまで、算出されない場合がある。例えば、分岐命令は、その分岐が行われるはずの現在の命令のアドレスからのオフセット値を指定することができる。分岐命令が実行され、分岐がとられたときに、分岐ターゲットの有効アドレスを算出し、分岐出口アドレスとして格納することができる。全ての有効アドレスを格納することができる場合がある。しかし、他の場合においては、有効アドレスの一部のみを格納することができる。例えば、有効アドレスの高位の３２ビットのみを用いて、分岐のターゲット命令を格納しているキャッシュされた命令ラインを見つけることができる場合に、命令ラインをプリフェッチする目的のために、これら３２ビットのみを分岐出口アドレスとして保管することができる。
【００５５】
（分岐履歴の追跡および記録）
本発明の実施形態においては、種々の量の分岐履歴情報を格納することができる。いくつかの場合においては、分岐履歴は、命令ラインに存在するどの分岐がとられることになるかまたはとられたかを示すことができる。どの分岐出口アドレスが命令ラインに格納されるのかは、リアルタイム実行の間に、または実行前の「トレーニング」期間の間に生成され格納された分岐履歴情報に基づいて判定することができる。
【００５６】
上記で説明されたように、ある実施形態により、命令ラインにおいて最後にとられた出口分岐命令に対応する分岐出口アドレスのみを格納することができる。命令ラインにおいて最後にとられた分岐に対応する分岐出口アドレスのみを格納することは、後でその命令ラインがフェッチされたときに同じ出口分岐がとられることを効果的に予測する。よって、前にとられた出口分岐命令のためのターゲット命令を格納している命令ラインをプリフェッチすることができる。
【００５７】
１以上のビットを用いて、命令ラインから抜け出す出口分岐の履歴を記録し、フェッチされた命令ラインにある命令が実行されたときにどの出口分岐がとられるかを予測することができる場合がある。例えば、図５に図示されたように、命令ライン（命令ライン１）に格納されている制御ビットＣＴＬは、その命令ラインに存在するどの出口分岐が前にとられたかを示す情報（ＣＢ−ＬＯＣ）、および、いつ分岐がとられたかの履歴を示す情報（ＣＢＨ）（例えば、前の数回の実行において分岐が何回取られたか）を格納することができる。
【００５８】
ここで、分岐位置ＣＢ−ＬＯＣおよび分岐履歴ＣＢＨをどのようにして用いることができるかの例として、Ｌ２キャッシュ１１２にあって、まだＬ１キャッシュ２２２にフェッチされていない命令ラインを考える。命令ラインがＬ１キャッシュ２２２にフェッチされたときに、プリデコーダおよびスケジューラ２２０は、命令ラインが分岐出口アドレスを持たないと判定して、別の命令ラインをプリフェッチしないことがある。随意的に、プリデコーダおよびスケジューラ２２０は、現在の命令ラインから次の順番のアドレスに位置する命令ラインをプリフェッチすることがある。
【００５９】
フェッチされた命令ラインにある命令が実行される際に、プロセッサ・コア１１４は、その命令ライン内の分岐が別の命令ラインにあるターゲット命令に分岐するか否かを判定することができる。そうした出口分岐が検出された場合には、分岐出口アドレスをＥＡ１に格納することに加えて、ＣＢ−ＬＯＣにその分岐の命令ライン内の位置を格納することができる。命令ラインの各々が３２の命令を格納する場合、出口分岐命令を示す（可能性ある命令位置の各々に対応する）０−３１の番号をＣＢ−ＬＯＣに格納することができるように、ＣＢ−ＬＯＣを５ビットのバイナリ数とすることができる。
【００６０】
ある実施形態においては、ＣＢ−ＬＯＣに設置された出口分岐命令がとられたことを示す値を、ＣＢＨに書込むことができる。例えば、ＣＢＨが単一ビットであった場合には、命令ラインにある命令の最初の実行の間に、出口分岐命令が実行されたときにＣＢＨに０を書込むことができる。ＣＢＨに格納された０は、ＣＢ−ＬＯＣに設置された出口分岐命令が、その後その命令ラインに格納されている命令を実行する間にとられることの、弱い予測を示すことができる。
【００６１】
命令ラインにある命令のその後の実行の間に、ＣＢ−ＬＯＣに設置された出口分岐が再びとられた場合には、ＣＢＨを１に設定することができる。ＣＢＨに格納された１は、ＣＢ−ＬＯＣに設置されたその出口分岐命令が再びとられることの強い予測を示すことができる。
【００６２】
しかし、同一の命令ラインが再びフェッチされ（ＣＢＨ＝１）、かつ、異なる分岐出口命令が取られる場合には、ＣＢ−ＬＯＣおよびＥＡ１の値は同じままとすることができるが、ＣＢＨは、命令ラインに格納されている命令のその後の実行の間に、前に取られた分岐が取られることの弱い予測を示す０にクリアされる。
【００６３】
ＣＢＨが０であり（弱い分岐予測を示す）、かつ、ＣＢ−ＬＯＣによって示されている出口分岐以外の出口分岐がとられる場合には、分岐出口アドレスＥＡ１を、そのとられた出口分岐のターゲット・アドレスで上書きすることができ、ＣＢ−ＬＯＣを、その命令ラインにある、とられた出口分岐に対応する値に変更することができる。
【００６４】
このようにして、分岐履歴ビットが用いられる場合においては、命令ラインは、予測された出口分岐に対応する格納された分岐出口アドレスを格納することができる。このような定期的にとられる出口分岐は、それほど頻繁にとられない出口分岐よりも優先される場合がある。しかし、出口分岐が弱く予測され、かつ別の出口分岐がとられた場合には、分岐出口アドレスを、とられた出口分岐に対応するアドレスに変更して、他の出口分岐が定期的にとられる時に、弱く予測された出口分岐が優先されないようにすることができる。
【００６５】
ある実施形態においては、ＣＢＨは、ＣＢ−ＬＯＣによって示される分岐命令のより長い履歴を格納することができるように、複数の履歴ビットを格納することができる。例えば、ＣＢＨが２つのバイナリ・ビットである場合には、００は非常に弱い予測に対応することができ（その場合には他の分岐をとることは、分岐出口アドレスおよびＣＢ−ＬＯＣを上書きすることになる）、一方、０１は弱い予測、１０は強い予測、１１は非常に強い予測に対応することができる（その場合には他の分岐命令をとることは、分岐出口アドレスまたはＣＢ−ＬＯＣを上書きしない）。例として、出口分岐の強い予測に対応する分岐出口アドレスを置換するためには、命令ラインにある命令の３回の連続実行において３つの他の出口分岐がとられることを必要とする場合がある。
【００６６】
本発明の実施形態においては、複数の分岐履歴（例えばＣＢＨ１、ＣＢＨ２など）、複数の分岐位置（例えばＣＢ−ＬＯＣ１、ＣＢ−ＬＯＣ２など）、および／または複数の有効アドレスを用いることができる。例えば、ある実施形態においては、ＣＢＨ１、ＣＢＨ２などを用いて複数の分岐履歴を追跡することができるが、ＣＢＨ１、ＣＢＨ２などのうち最も予測可能性が高い分岐に対応する１つの分岐出口アドレスのみを、ＥＡ１に格納することができる。随意的に、複数の分岐履歴および複数の分岐出口アドレスを単一の命令ラインに格納することができる。ある実施形態においては、ＣＢ−ＬＯＣによって示される所定の分岐が予測可能であることを分岐履歴が示した場合においてのみ、分岐出口アドレスを用いて命令ラインをプリフェッチすることができる。随意的に、いくつかの格納されたアドレスの中から最も予測可能性が高い分岐出口アドレスに対応する命令ラインのみを、プリデコーダおよびスケジューラ２２０によってプリフェッチすることができる。
【００６７】
本発明の実施形態においては、出口分岐命令が命令キャッシュ・ミスを引き起こすかどうかを用いて、分岐出口アドレスを格納するか否かを判定することができる。例えば、与えられた出口分岐が稀にしか命令キャッシュ・ミスを引き起こさない場合には、その出口分岐が命令ラインにある他の出口分岐よりも頻繁にとられるような場合であっても、その出口分岐に対応する分岐出口アドレスを格納しなくてもよい。命令ラインにある別の出口分岐が、とられる頻度は低いが、全体的により多くの命令キャッシュ・ミスを引き起こす場合には、他の出口分岐に対応する分岐出口アドレスを、その命令ラインに格納することができる。上述されたように、命令キャッシュ「ミス」フラグのような履歴ビットを用いて、どの出口分岐が命令キャッシュ・ミスを引き起こす可能性が最も高いかを判定することができる。
【００６８】
命令ラインに格納されたビットを用い、命令キャッシュ・ミスまたはプリフェッチに起因して命令キャッシュ２２２に命令ラインが配置されるか否かを示すことができる場合がある。ビットは、プロセッサ１１０により、キャッシュ・ミスを防ぐに当たって、プリフェッチの有効性を判定するために用いることができる。また、プリデコーダおよびスケジューラ２２０（または随意的に、プリフェッチ回路６０２）も、プリフェッチが不必要であると判定し、したがって命令ラインのビットを変更することができる場合がある。例えば、プリフェッチされた情報が既に命令キャッシュ２２２またはデータ・キャッシュ２２４に存在するなどの理由で、プリフェッチが不必要である場合においては、より多くの命令キャッシュ・ミスおよびデータ・キャッシュ・ミスを引き起こす命令に対応する他の分岐出口アドレスを命令ラインに格納することができる。
【００６９】
ある実施形態においては、出口分岐が命令キャッシュ・ミスを引き起こすかどうかを、出口分岐のための分岐出口アドレスを格納するか否かを判定するために用いられる唯一の要因とすることができる。別の実施形態においては、出口分岐の予測可能性と、その出口分岐が命令キャッシュ・ミスを引き起こすかどうかの予測可能性の両方をともに用いて、分岐出口アドレスを格納するか否かを判定することができる。例えば、分岐履歴および命令キャッシュ・ミス履歴に対応する値を加算するか、乗算するか、または他の計算式の中で（例えば加重として）用いて、分岐出口アドレスを格納するか否か、および／または、その分岐出口アドレスに対応する命令ラインをプリフェッチするか否かを判定することができる。
【００７０】
本発明の実施形態においては、分岐出口アドレス、出口分岐履歴、および出口分岐位置を実行時に継続的に追跡し、更新して、命令ラインに格納された分岐出口アドレスおよび他の値が、与えられた命令の組が実行されるに従い時間が経つにつれて変化するようにすることができる。このようにして、例えばプログラムが実行されるに従い、分岐出口アドレスおよびプリフェッチされた命令ラインを動的に修正することができる。
【００７１】
本発明の別の実施形態においては、命令の組の最初の実行フェーズの間に（例えばプログラムが実行される最初の期間の間に）、分岐出口アドレスを選択し、格納することができる。最初の実行フェーズは、初期化フェーズ、またはトレーニング・フェーズと呼ばれることもある。初期化フェーズの間に、分岐履歴および分岐出口アドレスを追跡することができ、１以上の分岐出口アドレスを（例えば、上述された基準によって）命令ラインに格納することができる。最初の実行フェーズが完了したときに、格納された分岐出口アドレスは、引き続き、Ｌ２キャッシュ１１２から命令ラインをプリフェッチするために用いることができるが、しかし、フェッチされた命令ラインにある分岐出口アドレス（単数または複数）は、それ以上追跡されたり更新されたりしないであろう。
【００７２】
ある実施形態においては、分岐出口アドレス（単数または複数）を格納している命令ラインの１以上のビットを用いて、その分岐出口アドレスが最初の実行フェーズの間に更新されたか否かを示すことができる。例えば、トレーニング・フェーズの間に、１つのビットをクリアすることができる。ビットがクリアされている間に、命令ラインにある命令が実行されるに従い、分岐履歴を追跡することができ、分岐出口アドレス（単数または複数）を更新することができる。トレーニング・フェーズが完了したときに、ビットを設定することができる。ビットが設定されたときに、分岐出口アドレス（単数または複数）はそれ以上更新されない場合があり、最初の実行フェーズが完了となるであろう。
【００７３】
ある実施形態においては、最初の実行フェーズは、特定の期間にわたって（例えばある数のクロック周期が経過するまで）続行することができる。ある実施形態においては、格納された最新の分岐出口アドレスは、指定の期間が経過し、最初の実行フェーズが終了するまで、命令ラインに格納されたままでいることができる。別の実施形態においては、最も頻繁にとられた出口分岐に対応する分岐出口アドレスか、または最も頻繁に命令キャッシュ・ミスを引き起こした出口分岐に対応する分岐出口アドレスを命令ラインに格納して、その後のプリフェッチに用いることができる。
【００７４】
本発明の別の実施形態においては、最初の実行フェーズは、１以上の出口基準が満たされるまで続行することができる。例えば、分岐履歴が格納されるような場合においては、最初の実行フェーズは、命令ラインにある分岐の１つが予測可能になる（または強く予測可能になる）までか、または命令キャッシュ・ミスが予測可能になる（または強く予測可能になる）まで、続行することができる。与えられた出口分岐が予測可能になったときに、最初のトレーニング・フェーズが完了したことと、その命令ラインがＬ２キャッシュ１１２からフェッチされる時に行われるその後のプリフェッチの各々において、強く予測可能な出口分岐の分岐出口アドレスを用いることができることを示すロック・ビットを、命令ラインに設定することができる。
【００７５】
本発明の別の実施形態においては、断続的なトレーニング・フェーズにおいて、命令ラインにある分岐出口アドレスを修正することができる。例えば、トレーニング・フェーズの各々について、頻度および期間の値を格納することができる。頻度に対応しているある数のクロック周期が経過するたびに、トレーニング・フェーズは初期化され、指定の期間値にわたって続行することができる。別の実施形態においては、頻度に対応しているある数のクロック周期が経過する度ごとに、トレーニング・フェーズは初期化され、指定の条件が満たされるまで（例えば、上述されたように、分岐についての指定のレベルの分岐予測可能性に到達するまで）、続行することができる。
【００７６】
本発明の実施形態においては、システム１００において用いられる各々のレベルのキャッシュおよび／またはメモリは、命令ラインに格納されている情報のコピーを格納することができる。本発明の別の実施形態においては、指定のレベルのキャッシュおよび／またはメモリのみが、命令ラインに格納されている情報（例えば、分岐履歴および出口分岐）を格納することができる。ある実施形態においては、当業者には公知のキャッシュの一貫性原則を用いて、各々のレベルのキャッシュおよび／またはメモリにある命令ラインのコピーを更新することができる。
【００７７】
命令キャッシュを用いる従来型のシステムにおいては、一般的には、命令はプロセッサ１１０によって修正されないことに注意されたい。よって、一般的には、従来型のシステムにおいては、命令ラインは、処理された後に命令キャッシュに書き戻されるのではなく廃棄されることになる。しかし、ここで説明されるように、本発明の実施形態においては、修正された命令ラインを命令キャッシュ２２２に書戻すことができる。
【００７８】
例として、命令ラインにある命令がプロセッサ・コアにより既に処理された（分岐出口アドレスおよび他の履歴情報が更新されることを引き起こす可能性がある）ときに、その命令ラインを、おそらくは命令キャッシュ２２２に格納されたより古いバージョンの命令ラインを上書きする形で、命令キャッシュ２２２に書込むことができる（書戻しと呼ばれる）。ある実施形態においては、命令ラインは、その命令ラインに格納された情報に対して変更が為された場合においてのみ、命令キャッシュ２２２に配置される。
【００７９】
本発明の実施形態により、修正された命令ラインが命令キャッシュ２２２に書戻されたときに、命令ラインを変更されたものとしてマークすることができる。命令ラインが命令キャッシュ２２２に書戻され、変更されたものとしてマークされる場合においては、命令ラインは異なった時間にわたって命令キャッシュに留まることができる。例えば、命令ラインがプロセッサ・コア１１４によって頻繁に使用される場合には、命令ラインは命令キャッシュ２２２へフェッチされ、戻されることが何度かあり、おそらくはそのたびに更新されるであろう。しかし、命令ラインが頻繁に使用されない場合には（エージングと呼ばれる）、その命令ラインを命令キャッシュ２２２から除去（パージ）することができる。命令ラインが命令キャッシュ２２２からパージされたときに、その命令ラインをＬ２キャッシュ１１２に書戻すことができる。ある実施形態においては、命令ラインが修正されたものとしてマークされた場合にのみ、Ｌ２キャッシュ１１２に書戻すことができる。別の実施形態においては、命令ラインは常にＬ２キャッシュ１１２に書戻すことができる。ある実施形態においては、命令ラインは、随意的に、いくつかのキャッシュ・レベルに（例えばＬ２キャッシュ１１２および命令キャッシュ２２２に）一度に書戻すか、または命令キャッシュ２２２以外のレベルに（例えばＬ２キャッシュ１１２に直接）書戻すことができる。
【００８０】
上述されたように、第１の命令ラインに格納されている出口分岐命令のターゲットとされた命令のアドレスを格納し、ターゲットとされた命令を格納している第２の命令ラインを、Ｌ２キャッシュからプリフェッチするために用いることができる。その結果として、命令キャッシュ・ミス、および対応する、命令にアクセスする待ち時間の数を減少させることができ、プロセッサ性能を向上させることができる。
【００８１】
以上、本発明の実施形態を一例として説明したが、本発明の他のさらなる実施形態をその基本的な範囲を逸脱することなく考案することができる。本発明の範囲は、添付の特許請求の範囲によって定められる。
【図面の簡単な説明】
【００８２】
【図１】本発明の実施形態によるシステムを図示するブロック図である。
【図２】本発明の実施形態によるコンピュータ・プロセッサを図示するブロック図である。
【図３】本発明の実施形態による、複数の例示的な命令ラインを図示する図である。
【図４】本発明の実施形態による、Ｌ１命令キャッシュ・ミスを防ぐためのプロセスを図示する流れ図である。
【図５】本発明の実施形態による、分岐出口アドレスを含んだ命令ラインを図示するブロック図である。
【図６】本発明の実施形態による命令ラインおよびデータ・ラインをプリフェッチするための回路を図示するブロック図である。
【図７】本発明の実施形態による、出口分岐命令に対応する分岐出口アドレスを格納するためのプロセスを図示するブロック図である。
【図１】
2007207246.tif 000003
【図２】
2007207246.tif 000004
【図３】
2007207246.tif 000005
【図４】
2007207246.tif 000006
【図５】
2007207246.tif 000007
【図６】
2007207246.tif 000008
【図７】
2007207246.tif 000009