(57)【要約】  実行中にキャッシュミスとなった命令の位置に基づいて情報をプリフェッチするための装置（３００）および方法が示される。アクセスされるプリフェッチ情報は、以前のキャッシュミスと現在のキャッシュミスの情報に基づいて決定される。例えば、以前のキャッシュミスに基づく情報が、プリフェッチ情報としてデータレコードに記憶される。このプリフェッチ情報は、以前のキャッシュミスを発生させた命令に基づく位置情報を含んでおり、現在のキャッシュミスのプリフェッチ要求を生成するためにアクセスされる。現在のキャッシュミス情報に基づいて、プリフェッチ情報が更新される。
2009540429.tif 000002
【特許請求の範囲】
【請求項１】
第１の命令の実行の一環として情報がアクセスされる第１のメモリ位置がキャッシュにおいて利用可能でない場合に、第１のキャッシュミス標識を受信するステップ（７１１）と、
前記第１のキャッシュミス標識を受信すると、第１のテーブルの第１のレコードに情報を記憶するステップ（７１２）とを含み、前記情報は、
前記第１の命令の位置を特定する命令情報（４１２，４２１）と、
前記第１のメモリ位置に基づくメモリ位置情報（４２２，４１１，４１３）とを有する、方法。
【請求項２】
第２の命令の実行の一環として情報がアクセスされる第２のメモリ位置がキャッシュにおいて利用可能でない場合、第２のキャッシュミス標識を受信するステップと、
前記第２のメモリ位置が前記第１のエントリに記憶されている前記第１のメモリ位置から定義された距離内にあると判定されると、前記第１のレコードに第１のプリフェッチ情報（４２１，４１４）を記憶するステップとを更に含み、前記第１のプリフェッチ情報は前記第２のメモリ位置に基づく、請求項１記載の方法。
【請求項３】
前記第１のプリフェッチ情報は前記第２のメモリアドレスを含むメモリ位置範囲を特定している、請求項２記載の方法。
【請求項４】
前記第１のプリフェッチ情報は参照メモリ位置に対するオフセットを含む、請求項３記載の方法。
【請求項５】
前記第１のプリフェッチ情報は前記第２のメモリアドレスを含む、請求項２記載の方法。
【請求項６】
前記第２のキャッシュミス標識を受信すると、前記第１のテーブルの第２のレコードに情報を記憶するステップを更に含み、前記情報は、
前記第２の命令の位置を特定する命令情報（４１２，４２２）と、
前記第２のメモリ位置を特定するメモリ位置情報（４２２，４１１，４１３）とを有する請求項２記載の方法。
【請求項７】
前記第２のメモリ位置が、前記第１のエントリに記憶されている前記第１のメモリ位置の定義された距離内にあることが判定されると、前記第１のレコードに記憶されている値（４２１，４１５）をインクリメントするステップを更に含む、請求項２記載の方法。
【請求項８】
前記第１のテーブル（３３１）は連想メモリであり、前記ＣＡＭの命令位置情報をアドレス指定するために内容が使用される、請求項１記載の方法。
【請求項９】
前記第１の命令の前記位置で命令を実行すると、第２のキャッシュミス標識を受信するステップ（７１３）と、
前記第１のレコードが、前記第１の命令の前記位置を特定する命令情報を含むことが判定されると、プリフェッチするメモリを決定するステップ（７３３）とを更に含む、請求項１記載の方法。
【請求項１０】
プリフェッチする前記メモリは複数の不連続なメモリ領域を含む、請求項９記載の方法。
【請求項１１】
前記第２のキャッシュミス標識を受信し、前記第１のレコードが、前記第１の命令の前記位置を特定する命令情報を含むことを決定すると、前記第１のレコードに記憶されている値（９２３）をインクリメントするステップを更に含む、請求項９記載の方法。
【請求項１２】
アドレス情報を提供するための第１の出力を有するデータプロセッサ（３００）と、
プリフェッチ情報を記憶するための第１の記憶位置（３３０）と、
前記第１の記憶位置に結合された第１の入力、第２の入力、および前記データプロセッサで実行中のキャッシュミスを発生させる命令のロケーションが第１の記憶位置に記憶されるとプリフェッチ要求を提供する第１の出力を有するプリフェッチモジュール（３４０）と、
前記データプロセッサの前記第１の出力に結合された第１の入力、前記プリフェッチモジュールの前記第１の出力に結合された第２の入力、およびキャッシュミス標識を提供するために前記プリフェッチモジュールの前記第２の入力に結合された第１の出力を有するメモリコントローラ（３５０）とを備えるデバイス。
【発明の詳細な説明】
【背景技術】
【０００１】
本出願は、データプロセッサの使用のために取得されるデータの決定に関し、より詳細には、データプロセッサのためにプリフェッチされる情報の決定に関する。
【０００２】
プリフェッチとは、データプロセッサを備えたコンピューティングデバイスに広く実装されている手法であり、この手法では、プロセッサが要求するデータおよび命令が、プロセッサが実際に必要としていると予想してプリフェッチされる。プリフェッチの結果、外部記憶装置に関連する低データレートではなく、プロセッサの内部バスアーキテクチャの比較的高いデータレートによって制限されるデータレートで、プロセッサが情報を利用できるようになる。このため、プリフェッチされた情報（データ、命令など）は、要求時にプロセッサがオンチップで利用可能であるため、通常は、プリフェッチによりプロセッサ全体の性能が改善される。
【発明の開示】
【０００３】
しかし、プリフェッチの実行が適切ではない場合には、結局はプロセッサが必要としない情報をプリフェッチすることによって、プリフェッチによりプロセッサまたはシステムの性能が低下しかねない。このため、特定のプリフェッチ手法は、あるタイプの用途では有利であるが、別のタイプの用途には適さないこともあるということが認められよう。このため、特定のタイプの用途のプリフェッチ効率を改善する、情報をプリフェッチするための方法および装置が有用であろう。
【０００４】
本発明は、添付の図面を参照することによって、より明確に理解することができ、その数多くの特徴および利点が当業者にとって明白となろう。
【発明を実施するための最良の形態】
【０００５】
本開示によれば、実行中にキャッシュミスとなった命令の位置（ロケーション）に基づいて、プリフェッチ情報がアクセスされる。アクセスされるプリフェッチ情報は、以前のキャッシュミスと現在のキャッシュミスの情報に基づいて決定される。例えば、以前のキャッシュミスに基づく情報が、プリフェッチ情報としてデータレコードに記憶される。このプリフェッチ情報は、以前のキャッシュミスを発生させた命令の位置（ロケーション）情報を含んでおり、現在のキャッシュミスのプリフェッチ要求を生成するためにアクセスされる。更に、現在のキャッシュミス情報に基づいて、プリフェッチ情報が更新される。本開示の特定の実施形態は、ここで図１〜１９の図面を参照すれば、より明確に理解できるであろう。
【０００６】
本開示の特定の実施形態を、一連の命令を実行した結果記憶されるプリフェッチ情報に関して記載する。図１は、複数の行を有するテーブル１１０が図示されており、その各行は、データプロセッサによる命令の実行に関連する情報を表している。テーブル１１０の列１１１は、対応する命令の実行時間を示す情報を含む。テーブル１１０の列１１２は、対応する命令への命令ポインタを特定する情報を含む。テーブル１１０の列１１３は、実行された命令を特定する情報を含む。
【０００７】
列１１１に記憶されている情報は、対応する命令が、テーブル１１０の他の命令に対して実行される相対順序を示す時間標識である。時間標識の末尾の数字により、ＩＮＳＴ２は、対応する時間標識Ｔ１を有するＩＮＳＴ１の後に実行されることが示される点に留意されたい。ＩＮＳＴ１とＩＮＳＴ２の間に別の命令が入らず、ＩＮＳＴ１とＩＮＳＴ２が連続的に実行されるとは限らない点に留意されたい。
【０００８】
列１１２の命令ポインタは、その対応する命令の位置（ロケーション）を示す。例えば、時間Ｔ１に実行される命令ＩＮＳＴ１は、図１では、ｈＦＦＦＦ１２３４という１６進値を有する。命令ポインタは、物理メモリ空間、論理メモリ空間を含む、どのようなタイプのメモリ空間の位置（ロケーション）を表してもよい。
【０００９】
ＩＮＳＴ１〜ＩＮＳＴ４は、実行時にキャッシュミスとなる命令である。ここでの説明のため、すべてのキャッシュミスが、ニーモニックＬＯＡＤｘのロード命令の結果発生するものとする。ロード命令のニーモニックの末尾の「ｘ」は、Ａ〜Ｚの値を有するアルファベット文字であり、特定のレジスタを識別する。このため、ニーモニックＬＯＡＤＡとＬＯＡＤＢは、メモリの情報にアクセスし、それぞれ、レジスタＡ１２１とレジスタＢ１２２にストアする命令を表す。
【００１０】
命令ＩＮＳＴ１〜ＩＮＳＴ４を実行する際には、各種のアドレス指定モードを使用してメモリ位置がアクセスされうる。ここに特に示すアドレス指定モードには、直接アドレス指定モードとレジスタ間接アドレス指定モードが含まれる。命令「ＬＯＡＤＢ  ｈＡＤＤＲ１」は、直接アドレス指定モードを使用するロード命令の例であり、ｈＡＤＤＲ１は、レジスタＢ１２１においてリードおよびストアされるメモリ位置を特定している１６進数である。先頭の文字「ｈ」は、値Ａｄｄｒ１が１６進数であることを示す点に留意されたい。命令「ＬＯＡＤＢ  ＜ＲＥＧＡ＞」は、記号「＜＞」が示すように、レジスタ間接アドレス指定モードの例であり、記号「＜＞」で囲んだレジスタにストアされている値は、この位置から情報がレジスタＢ１２１にリードおよびストアされるメモリ位置を特定している。
【００１１】
例えば、図１には、ＩＮＳＴ１が、レジスタ間接アドレス指定モードを使用するＬＯＡＤＢ命令であることが示されている。ニーモニック＜ＲＥＧ  Ａ＞は、レジスタＡ１２１に、その位置から情報を読み出すアドレス値が含まれることを特定している。レジスタＡ１２１の値は、ＡＤＤＲ（Ｔ１）であり、レジスタＡ１２１にストアされている情報が、命令ＩＮＳＴ１の実行中の時間Ｔ１に存在していたアドレス位置を表すことを示している。
【００１２】
説明のため、メモリ空間の各バイトが３２ビット値によってアドレス指定可能であるとする。先頭の文字「ｈ」は、ここでは１６進数を表すのに用いられる。このため、図１のレジスタＡ１２１にストアされている値は、３２ビット値であり、ビット順序を示す参照符号１２３に示すように、最上位ビット（ｂ３１）と最下位ビット（ｂ０）を有する。
【００１３】
特定のニーモニックを、各メモリ位置を表すビットｂ３１〜ｂ０の一部分と関連付ければ、ここでの説明がわかりやすくなるであろう。データプロセッサシステムは、各メモリアクセスによってアクセスされる最小バイト数を有しうることが理解されよう。ここでの説明のため、一度に４バイトずつアクセスされるとする。このため、最小アクセスブロックは、整列された４バイトの領域に関連するバイトを含む。この４バイト領域の各バイトはバイトインデックスによって特定され、本例では、これには、アドレスロケーションの下位２ビット（ＬＳＢ）が含まれる。図１に更に示すように、「ベースアドレス」との文言は、メモリ内で整列領域を特定するインデックス値を与える、各３２ビットメモリロケーションの所定の数の上位ビット（ＭＳＢ）を指す。図に示すように、図１の２２ビットのベースアドレスには、各アドレスロケーション（ｂ２１〜ｂ１０）の上位２２のＭＳＢ（ｂ２１〜ｂ１０）が含まれる。このため、それぞれが一意である２２ビットのベースアドレス値は、アドレス整列されたメモリ領域の先頭バイトを特定する。「アドレス整列されたメモリ領域」との文言は、オフセットを繰り返して整列された（例えば始点など）メモリの整列領域を指し、例えばアドレス値に基づいた、１キロバイト（２１０）おきのメモリ領域（例えばｈ０、ｈ４００、ｈ８００、ｈＣ００等）などである。ここに記載する別の整列されたメモリ領域として、中央ブロック整列されたメモリ領域があり、これは、中央にくる特定のメモリブロックに対する参照メモリブロックへの正負のインデックス値を使用する方式である。
【００１４】
オフセットは、整列領域内で特定の１以上のバイトをインデックスするかまたはアドレス指定するために使用される。例えば、１キロバイト領域内で任意の１バイトを特定するために、１０ビットのオフセットインデックス（オフセットインデックス１）が使用されうる。別の実施形態では、これより大きな整列領域内のバイトブロックの先頭バイトを特定するために、オフセットインデックスが使用されてもよい。例えば、オフセットインデックス２は、１キロバイト領域内で、特定の最小アクセスブロックを特定するために使用することができる８ビットのオフセットインデックスである。同様に、オフセットインデックス３は、キャッシュラインサイズに対応する１キロバイト領域内で、６４バイトメモリブロックの先頭バイトを特定するために使用することができる４ビットのオフセットである。例えば、メモリに対する各データ要求の結果、６４バイトのキャッシュラインが埋まるとすると、このキャッシュライン内の特定のバイトを特定するために、ビットｂ５〜ｂ０（ブロックインデックス）が使用され、オフセットインデックス３の特定の値は、２２ビットのベースアドレスによって定義される１キロバイトの整列領域内の１６個の６４バイトの領域の１つをインデックスしている。
【００１５】
別の実施形態では、同じ命令セットに基づくインデックストレーニングプリフェッチ情報図３〜７に記載され、この方式では、ブロックオフセットは、キャッシュミスとなったブロックを表す中央位置に対するオフセットである。この位置は、正負のオフセットを使用することができるため、中央位置と呼ばれる。
【００１６】
図２は、本開示によるシステム３００を示す。システム３００は、表２２１に示す命令を実行するデータプロセッサ３１０；データプロセッサ３１０から情報を受信し、プリフェッチ情報を提供するように結合されたプリフェッチトレーニングモジュール；プリフェッチトレーニングモジュール３２０からプリフェッチ情報を受信して、これを記憶する記憶場所３３０；記憶場所３３０にある情報に基づいてプリフェッチ要求を提供するプリフェッチコントローラ３４０；データプロセッサ３１０からメモリアクセス要求情報を、プリフェッチコントローラ３４０からメモリプリフェッチ要求を受け取り、メモリ３７０にメモリ要求を、プリフェッチトレーニングモジュール３２０およびプリフェッチ制御モジュールにキャッシュミス標識を提供するメモリコントローラ３５０；および、メモリコントローラ３５０から要求された情報を受け取り、これを提供するキャッシュ３６０を備える。図２の特定の実施形態では、集積回路装置３０１と外部コンポーネント３０２との間に境界が示されている。
【００１７】
データプロセッサ３１０内にテーブル２３１が示されており、テーブル３１１の各行はデータプロセッサ３１０によって実行される命令を表している。表３１１の各行において、列３１２は、命令の位置を示す命令ポインタを特定し、命令ポインタによってポイントされている命令が列３１３に一覧され、列３１１には、テーブル２３１の他の命令に対する各命令の実行の順序を示す時間シーケンス標識が一覧され、列３１４のアドレスは、一覧された命令によってアクセスされるメモリ位置を示す。
【００１８】
動作時に、データプロセッサ３１０は、特定の命令の実行を完了するのに必要な情報を含むメモリ位置を特定するアドレス情報を、メモリコントローラ３５０に提供する。メモリコントローラ３５０は、要求されたアドレスの情報がキャッシュ３６０に存在する場合はキャッシュ３６０から、存在しない場合はメモリ３７０から情報を提供する。要求された情報がキャッシュ３６０で利用できない場合、メモリコントローラ３５０はキャッシュミスを発生させる。データプロセッサ３１０によって要求された情報は、取得されると、プロセッサ３１０とキャッシュ３６０に提供される。メモリコントローラ３５０は、一般に、データプロセッサ３１０が必要とする情報を格納しているアドレスの近くのアドレス位置にある情報によって、キャッシュ３６０のキャッシュライン全体を埋めることが理解されよう。説明のため、キャッシュ３６０の各キャッシュラインが長さ６４バイトであるとする。
【００１９】
プリフェッチコントローラは、メモリコントローラ３５０からキャッシュミスを受け取ると、記憶場所３３０にあるプリフェッチ情報に基づいて、キャッシュミスの結果、プリフェッチすべき追加の情報があるかどうかを判定する。ここに記載の特定の実施形態によれば、キャッシュミスを発生させた命令の命令ポインタが使用され、関連するプリフェッチ情報が記憶場所３３０に存在するどうかが判定される。プリフェッチ要求の生成時のレーテンシを短縮するために、記憶場所３３０は、通常、プリフェッチコントローラと同じ集積回路装置に存在する点に留意されたい。一実施形態では、テーブル２３１にあるレコードを格納している記憶場所３３０の部分は、現在のキャッシュミスを発生させている命令の命令ポインタを使用してアクセスされる連想メモリ（content addressable memory）であってもよい。キャッシュミスを発生させた命令に関連するエントリが、記憶場所３３０に格納されている場合、プリフェッチコントローラ３４０は、記憶場所３３０に記憶されている情報に基づいて、メモリコントローラ３５０にプリフェッチアドレス情報を提供する。この結果、メモリコントローラ３５０は、プリフェッチコントローラから要求されている情報が、既にキャッシュ３６０にあるかどうかを判定する。ない場合、メモリコントローラ３５０は、メモリ３７０から情報を取得し、キャッシュ３６０の追加のキャッシュラインを埋める。プリフェッチトレーニングモジュールの動作と、テーブル３１１の情報の決定方法について、記憶場所３３０でのプリフェッチ情報のトレーニングの特定の例を示す図３〜７を参照して説明する。
【００２０】
図３〜７は、それぞれ、データプロセッサ３１０で実行されている、テーブル２２１中の命令によりキャッシュミスが発生した際の、記憶場所３３０でのプリフェッチ情報のトレーニングを示す。図３〜７のそれぞれは、テーブル２２１の一番下の行には現在のキャッシュミスを発生させている現在の命令が含まれ、列３１２の命令は現在実行中であり、以前に実行された命令（存在する場合）も含む。更に、図３〜７のそれぞれは、プリフェッチトレーニングモジュール３２０によって、記憶場所３３０にあるテーブル３３１に提供されるプリフェッチ情報を示す。記憶場所３３０に記憶されるプリフェッチ情報は、テーブル３３１の表形式で表され、各行は、キャッシュミスに関連する情報を格納している情報のレコードを表している。キャッシュミスを発生させたメモリアドレスは、列４１１のミスベースアドレスと、列４１３のミスオフセットによって特定される。説明のため、ミスベースアドレスは、メモリ空間内の１キロバイトの整列領域を特定する２２ビットのインデックスであるとする。このため、３２ビットアドレスの場合、各ミスベースアドレス値は、ミスを発生させたアドレスの上位２２ビットを表す２２ビットの１６進数（ミスアドレス）によって表される。列４１３に記憶されるミスオフセット値は、ミスベースアドレスによって特定される１キロビット領域に対するオフセットを表す１０ビット数である。命令ポインタ（ＩＰ）値は、列４１２に記憶され、キャッシュミスを発生させた命令の位置を特定する。プリフェッチするメモリロケーションの特定に使用されるプリフェッチ情報は、列４１４の一致ビット配列に記憶される。列４１５には一致カウンタが保持される。
【００２１】
プリフェッチ情報を記憶するためのテーブル３３１のレコード数は、固定数でも可変でもよい。一実施形態では、記憶位置は、図２の３０１によって表される集積回路装置上のモジュールを含む半導体デバイスの固定記憶位置である。
【００２２】
図３は、時間Ｔ１で命令ＬＯＡＤＢ  ＜ＲＥＧ  Ａ＞の実行によって発生したキャッシュミスの影響を示している。具体的には、時間Ｔ１でのキャッシュミスの結果、新規レコードがテーブル３３１の行４２１に作成される。時間Ｔ１のキャッシュミスの原因となった命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞への命令ポインタを表す情報は、テーブル３３１の列４１２／行４２１に記憶される。キャッシュ３６０に存在せず、時間Ｔ１でミスを発生させたミスアドレスを表す情報は、ミスベースアドレスとして列４１１に、ミスオフセットとして列４１３に記憶される。例えば、ミスアドレス（ｈＦＥＤＣＢ１２３）の上位２２ビットを含む２２ビットのミスベースアドレス（ｈ３ＦＢ７２Ｃ）が、テーブル３３１の列４１１／行４２１に記憶される。ミスベースアドレス値は、メモリの１キロバイトの整列領域を特定する。メモリ内での１キロバイト領域の開始点は、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）にｈ４００を掛け、これにより、ベースアドレスに、１０個のゼロをＬＳＢとして追加することで求めることができる。例えば、ｈ３ＦＢ７２Ｃ×ｈ４００＝ｈＦＥＤＣＢ０００となる。
【００２３】
キャッシュミスを発生させたアドレスの残りの１０ビットは、ミスオフセットとして列４１３／行４２１に記憶される。上で説明したように、ミスオフセットを表すのに必要なビット数が変更されてもよい点に留意されたい。例えば、メモリが一度に４バイトずつアクセスされる場合には、キャッシュミスを発生させたメモリ位置を格納しているメモリの位置を特定するのに、１０ビットのうちの８ビットしか必要ではなく、１０ビットのオフセットを保持する必要はない。同様に、１キロビットの整列メモリ領域内の１６個の可能なキャッシュライン位置の１つを特定するには、４ビットのオフセット値で足りる。例えばミスオフセットの値が０の場合には、１キロバイトの整列領域の先頭バイトでメモリのアクセスが開始され、ミスオフセットの値が１の場合、１キロバイト領域の６５番目のバイトでメモリのアクセスが開始される。
【００２４】
時間Ｔ１においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを特定する（ミスベースアドレスの値によって特定される）ために、列４１４／行４２１の一致ビット配列に値が記憶される。一実施形態では一致ビット配列は、１６ビットの値を記憶し、１６ビット値の各ビット（ｂ１５〜ｂ０）は、上で説明したように、１キロバイト領域を構成している１６個の６４ビットデータブロックの１つに対応している。例えば、列４１３／行４２１のミスオフセットｈ１２３に対応するビットは、ミスオフセット値を６ビット右シフトすることで求められる。例えば、値ｈ１２３を６ビットシフトさせると、ｈ００１０の１６進値が得られ、これは００００  ００００  ０００１  ００００の２進値に対応している。この結果、時間Ｔ１においてミスを発生させたメモリアドレスが、１キロバイトの整列領域の５番目の６４ビットブロックに存在することを示すように、一致ビット配列の第５ビット（ｂ４）がセットされる。
【００２５】
行４２１の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００２６】
図４は、時間Ｔ２での命令ＬＯＡＤＣ  ｈＦＥＤＣＢ１Ｅ７の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図４の矢印４９２は、現在のキャッシュミスによって影響されるレコードを表す行をポイントしており、これらのレコードには、行４２１によって表されるレコードと、行４２２によって表される新規レコードが含まれる。
【００２７】
時間Ｔ２でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２２に記憶される。時間Ｔ２においてミスを発生させた命令によってアクセスされているアドレス位置（ｈＦＥＤＣＢ１Ｅ７）を表す情報が、ミスベースアドレス（Ｈ３ＦＢ７２Ｃ）として列４１１／行４２２に、１０ビットのミスオフセット（ｈ１Ｅ７）として列４１３／行４２２に記憶される。
【００２８】
時間Ｔ２においてキャッシュミスを発生させたメモリロケーションを格納している１キロバイトの整列領域の６４バイトブロックを示す（ミスベースアドレスの値によって特定される）ために、列４１４／行４２２の一致ビット配列に値が記憶される。行４２１のミスオフセットｈ１Ｅ７に対応する６４バイトブロックは、第７ビット（ｂ６）であり、時間Ｔ２でのキャッシュミスの結果、列４１４／行４２２にｈ００８０の一致ビット配列値が記憶される。
【００２９】
列４１５／行４２２のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００３０】
新たにキャッシュミスが発生するたびに、テーブル３３１の既存のレコードのそれぞれが評価され、前に記憶されたレコードのうち、同じ１キロバイトの整列領域に対応するミスベースアドレスを有するものが存在するかどうかがチェックされる。例えば、行４２１と行４２２は、同じベースミスアドレス値（ｈ２ＦＢ７２Ｃ）を有するため、これらのキャッシュミスの両方を発生させたアクセスのメモリが、同じ１キロバイトの整列領域に記憶されていると判定される。このため、現在の（Ｔ２）ミスベースアドレスが以前のミスベースアドレスに一致していると、以前の一致ビット配列が更新される。例えば、現在の一致ビット配列と以前のミスビット配列の論理和を求めることによって、列４１４／行４２１の以前のミスベースアドレスに情報が記憶される。例えば、時間Ｔ２でのキャッシュミスの結果、プリフェッチトレーニングモジュールから情報が提供され、行４２１の一致ビット配列の値が、値ｈ００９０（ｈ００１０  ＯＲ  ｈ００８０）に更新される。
【００３１】
行４２１の列４１５のカウンタ値が、現在のミスの結果一致ビット配列情報が更新されたことを示すように１インクリメントされる。
【００３２】
図５は、時間Ｔ３での命令ＬＯＡＤＢ  ｈＦＥＤＣＣ２３４の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図５の矢印４９３は、現在のキャッシュミスによって影響されるレコードを表す行をポイントしており、このレコードには、行４２３によって表される新規レコードのみが含まれる。
【００３３】
時間Ｔ３でキャッシュミスの原因となった命令への命令ポインタを表す情報が、テーブル３３１の列４１２／行４２３に記憶される。時間Ｔ３においてミスを発生させた命令によってアクセスされているアドレスロケーション（ｈＦＥＤＣＣ２３４）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７３０）として列４１１／行４２３に、１０ビットのミスオフセット（ｈ２３４）として列４１３／行４２３に記憶される。
【００３４】
時間Ｔ３においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを示す（ミスベースアドレスの値によって特定される）ために、列４１４／行４２３の一致ビット配列に値が記憶される。行４２１のミスオフセットｈ２３４に対応する６４バイトブロックは、第９ビット（ｂ８）であり、時間Ｔ３でのキャッシュミスの結果、行４２３の列４１４にｈ０１００の一致ビット配列値が記憶される。
【００３５】
行４２３の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００３６】
時間Ｔ３でキャッシュミスを発生させたアドレスは、テーブル３３１の他のレコードと同じミスベースアドレスを持たないため、時間Ｔ３のキャッシュミスが、テーブル３３１の他のレコードに影響することはない。
【００３７】
図６は、時間Ｔ４での命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図６の矢印４９４は、現在のキャッシュミスによって影響されるレコードをポイントしており、これらのレコードには、行４２１と行４２２によって表されるレコードと、行４２４によって表される新規レコードが含まれる。
【００３８】
時間Ｔ４でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２４に記憶される。時間Ｔ４においてミスを発生させた命令によってアクセスされているアドレス位置（ｈＦＥＤＣＣ２３４）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）として列４１１／行４２４に、１０ビットのミスオフセット（ｈ２３）として列４１３／行４２４に記憶される。
【００３９】
時間Ｔ４においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域内の６４バイトブロックの位置を示すために、列４１４／行４２４の一致ビット配列に値が記憶される。ミスオフセットｈ２３を格納している６４バイトブロックに対応するビットは、第１ビット（ｂ０）であり、時間Ｔ４でのキャッシュミスの結果、列４１４／行４２４にｈ０００１の一致ビット配列値が記憶される。
【００４０】
行４２４の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００４１】
また、時間Ｔ４でのキャッシュミスの結果、テーブル３３０の２つの既存のレコードも、これらのレコードが同じ１キロバイトの整列領域のインデックスを有するため、追加のプリフェッチ情報によって更新される。例えば、列４１４／行４２１と列４１４／行４２２のプリフェッチ情報は、いずれも、現在のキャッシュミスを表す行４２４の同じミスアドレス値（ｈ３ＦＢ７２Ｃ）値を有するため、更新する必要がある。このため、列４１４／行４２１の一致ビット配列がｈ００９１に更新され、列４１４／行４２２の一致ビット配列が００８１に更新される。行４２１および行４２２のプリフェッチ情報の更新が発生するのは、時間Ｔ４で必要とされた情報が、仮に、Ｔ１または時間Ｔ２のいずれかでプリフェッチされていたならば、時間Ｔ４でのキャッシュミスを回避できたためであることが理解されよう。この点については、更に別の実施形態に関してここに後述する。
【００４２】
行４２１と行４２２の列４１５のカウンタ値が、現在のミスの結果、それぞれの行の一致ビット配列情報が更新された回数を示すように、１インクリメントされる。
【００４３】
図７は、時間Ｔ５での命令ＬＯＡＤＣ  ＜ＲＥＧＢ＞の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図７の矢印４９５は、現在のキャッシュミスによって影響されるレコードをポイントしており、これらのレコードには、行４２１、行４２２、行４２４によって表されるレコードと、行４２５によって表される新規レコードが含まれる。
【００４４】
時間Ｔ５でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２５に記憶される。時間Ｔ５においてミスを発生させた命令によってアクセスされているアドレス位置（ＨＦＥＤＣＢ３Ｃ５）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）として列４１１／行４２５に、１０ビットのミスオフセット（ｈ３Ｃ５）として列４１３／行４２５に記憶される。
【００４５】
時間Ｔ５においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを示すために、列４１４／行４２４の一致ビット配列に値が記憶される。行４２１のミスオフセットｈ３ＣＦに対応する６４バイトブロックは、第１６ビット（ｂ１５）であり、時間Ｔ５でのキャッシュミスの結果、列４１４／行４２５にｈ８０００の一致ビット配列値が記憶される。
【００４６】
列４１５／行４２５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００４７】
また、新たにキャッシュミスが発生するたびに、テーブル３３０の既存のレコードのそれぞれが評価され、前に記憶されたレコードのうち、同じ１キロバイトの整列領域に対応するミスベースアドレスを有するものが存在するかどうかがチェックされる。本例では、行４２１、行４２２および行４２４のプリフェッチ情報は、いずれも、現在のキャッシュミスを表す行４２５のミスアドレス値（ｈ３ＦＢ７２Ｃ）と同じ値を有するため、更新する必要がある。このため、行４２１の一致ビット配列がｈ８０９１に更新され、行４２２の一致ビット配列が８０８１に更新され、行４２４の一致ビット配列がｈ８０００に更新される。
【００４８】
行４２１、行４２２および行４２４の列４１５のカウンタ値が、現在のミスの結果、それぞれの行の一致ビット配列情報が更新された回数を示すように、１インクリメントされる。
【００４９】
プリフェッチコントローラ３４０の動作について、図８を参照して説明する。説明のため、図７に図示したプリフェッチ情報が、新たなキャッシュミスが発生した時点におけるプリフェッチ情報の現在の組であるとする。図８は、キャッシュミス標識５１１を受け取るプリフェッチコントローラ３４０、キャッシュミス標識５１１を発生させた命令に対する命令ポインタ５１２、およびキャッシュミスを発生させたメモリ位置のミスベースアドレスを示す。
【００５０】
プリフェッチコントローラ３４０は、キャッシュミス標識を受け取ると、記憶場所３３０のプリフェッチ情報に、現在のキャッシュミスを発生させた命令ポインタに関連するレコードが含まれているかどうかを判定する。例えば、命令ポインタｈ８１１１を有する命令を実行した結果、発生したキャッシュミス標識を受け取った場合、この命令ポインタは、テーブル３３１に存在しないため、テーブル３３１でプリフェッチ情報が発見されない。しかし、命令ポインタｈ８１００にある命令を実行した結果、キャッシュミスが発生した場合、プリフェッチコントローラはテーブル３３１のプリフェッチ情報に２つのエントリ（行４２１および行４２４を参照）を発見する。プリフェッチコントローラ３４０は、最も古いエントリ（すなわち列４１４／行４２１によって表されるエントリ）を使用して、メモリコントローラ３５０にプリフェッチ要求を発行する。
【００５１】
プリフェッチコントローラ３４０からのプリフェッチ要求には、以前にメモリがアクセスされた特定のメモリブロックに関連するメモリアドレスが提示される。列４１４／行４２１の一致ビット配列のセットされたビットのそれぞれは、６４ビットメモリブロックに対応しているため、プリフェッチコントローラは、メモリコントローラ３５０に４つのメモリプリフェッチ要求を提示する。例えば、行４９１の一致ビット配列値ｈ８０９１には、以前にデータがアクセスされた４つのメモリブロックに対応する４つのビット（ｂ１５、ｂ８、ｂ４およびｂ０）がセットされている。このため、プリフェッチコントローラは、メモリコントローラ３５０に４つのメモリアドレス（４つのブロックに対して１つずつ）を提供する。プリフェッチコントローラ３４０は、対応するブロックの全６４バイトをプリフェッチするために、６４バイトブロック内の任意のアドレスをメモリコントローラ３６０に提供することができる。一致ビット配列内のセットされたビットに対応するメモリブロックの先頭バイトは、対応するミスベース配列値を１０ビット左シフトし、この結果に、セットされたビットに対応する図８のテーブル５３０のオフセットを加算して求めることができる。このため、ｈ８０９１の一致ビット配列値の場合、プリフェッチコントローラは、１キロバイトの境界の先頭バイトから、ｈ０００（ｂ０）、ｈ１００（ｂ４）、ｈ２００（ｂ８）およびｈ３Ｃ０（ｂ１５）だけオフセットされたアドレスロケーションを要求しうる。
【００５２】
本発明の一実施形態では、プリフェッチ要求を生成するために使用される１キロバイトの境界は、プリフェッチコントローラ３４０が受け取る現在のミスベースアドレスである。このため、図８を参照すると、ミスベースアドレス５１３が、ｈＣＦＦＦＦＦの２２ビット値を有する場合、プリフェッチコントローラ３４０は、ＦＦＦＦＦＣ００（ｂ０）、ＦＦＦＦＦＤ００（ｂ４）、ＦＦＦＦＦＤＣ０（Ｂ８）、およびＦＦＦＦＦＦＣ０（ｂ１５）の各アドレス値をメモリコントローラ３５０に提供する。これらのアドレス値により、メモリコントローラ３５０によって４つのキャッシュラインがプリフェッチされる（これらが現在キャッシュ３６０に存在しない場合）。連続するメモリブロックを含む大きなメモリ領域をプリフェッチするのではなく、プリフェッチされるメモリブロックが、メモリの不連続な領域であってもよい点に留意されたい。
【００５３】
なお、その後発生したキャッシュミスのうち、共通する１キロバイトのメモリ領域に存在するものを決定するために、プリフェッチトレーニング中にテーブル３３１の列４１１にあるミスベースアドレス情報が必要とされるが、プリフェッチコントローラはミスベースアドレス情報を必要とせず、現在のキャッシュミスのミスベースアドレスを使用して、プリフェッチアドレスを生成する。このため、プリフェッチコントローラ３４０がプリフェッチ要求を生成するために使用する別のテーブルを保持することができる。図９は、記憶場所３３０に記憶することができるテーブル３３２を示し、このテーブルはプリフェッチコントローラ３４０が使用するプリフェッチ情報を格納している。具体的には、テーブル３３２の列５１１に命令ポインタ情報が記憶され、列５１２に一致ビット配列情報が記憶される。テーブル３３２は、各命令ポインタ値に対して複数のレコードを保持するのではなく、所定の命令ポインタに対して１つのレコードのみを含む。これにより、テーブル３３２は、キャッシュミスの発生時に、現在のキャッシュミスの原因となった命令ポインタ値を使用して、プリフェッチコントローラによってアクセスされる連想メモリが可能となる。連想メモリに対する要求により、列５１１に一致する命令ポインタが特定された場合その対応する一致ビット配列がプリフェッチコントローラ３４０によって使用され、メモリコントローラ３５０にプリフェッチアドレスが提示される。
【００５４】
図１０は、プリフェッチコントローラ３４０によって使用されるプリフェッチ情報を記憶するために、テーブル３３２の代わりに使用することができるテーブル３３３の別の実施形態を示す。列５２１および列５２２は、上で説明した列５１１および列５１２に対応している。ただし、テーブル３３３には、キャッシュミスカウンタを保持するための列５２３が含まれる。キャッシュミスカウンタ値は、プリフェッチコントローラが、キャッシュミスの際に、特定のレコードを使用してプリフェッチ要求を発生させた回数を示す。このため、レコードのキャッシュミスカウンタは、プリフェッチ要求を生成するために、その一致ビット配列情報が使用されるたびにインクリメントされる。
【００５５】
上で説明した以外の別のオフセット方式を使用することができ、上の方式では、ブロックオフセットは、３２ビットアドレスの上位２２ビットによって定義される１キロバイトのメモリ境界に基づいた整列領域の先頭に対するオフセットであることが理解されよう。例えば、図１１〜１５は、図３〜７に図示したのと同じ命令セットに基づくトレーニングプリフェッチ情報の別の実施形態を示しており、この方式では、ブロックオフセットは、キャッシュミスとなったブロックを表す中央位置に対するオフセットである。この位置は、正負のオフセットを使用することができるため、中央位置と呼ばれる。
【００５６】
図１１〜１５を参照すると、記憶場所３３０に記憶されるプリフェッチ情報は、テーブル３４１の表形式で表され、各行は、キャッシュミスに関連する情報を格納している情報のレコードを表している。列４４１〜４４３および列４４５は、列３４１〜３４３および列３４５に関して上で説明した情報を記憶する。列４４４は、キャッシュミスの原因となったアドレスを含むメモリブロックを中心とする整列領域内に、プリフェッチ情報を記憶する。このため、テーブル３４１の行４４４の各エントリの８つのＭＳＢは、中央ブロックの前の８つの６４バイトデータブロックの１つを表し、行４４４の各エントリの８つのＬＳＢは、中央の６５バイトブロックの後の８つの６４バイトデータブロックの１つを表す。
【００５７】
図１１を参照すると、時間Ｔ１において命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞が実行されると、列４４４／行４５１の一致ビット配列がクリアされる（例えば、全ビットがゼロにセットされる）。エントリが作成されると、一致ビット配列がクリアされる点に留意されたい。この理由は、ミスを発生させたアドレスを格納している６４バイトデータブロック（例えば図１１のｈＦＥＤＣＢ１２３）が参照点となり、この点から、プリフェッチ情報を表す他のブロックオフセットが求められるためである。
【００５８】
図１２を参照すると、時間Ｔ２においてキャッシュミスを発生させた命令が実行されると、行４５２の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１の情報が評価されて、このプリフェッチ情報を更新すべきかどうかが判定される。本実施形態に関しては、現在のキャッシュミスを発生させたメモリ位置が８つの６４バイトメモリブロック内（すなわち、±５１２バイト）に存在する場合、特定の行のプリフェッチ情報が更新される。この値は、（６ビット右シフトさせた現在のミスアドレス）−（６ビットシフトさせた評価される行のミスアドレス）の式によって求めることができる。このため、図１２に関して、現在のキャッシュミスを発生させたメモリ位置（ｈＦＥＤＣＢ１Ｅ７）は、行４５１のキャッシュミスを発生させたメモリ位置（ｈＦＥＤＣＢ１２３）に対し、＋ｈ３（（６ビット右シフトさせたｈＦＥＤＣＢ１Ｅ７）−（６ビット右シフトさせたｈＦＥＤＣＢ１２３））のブロックオフセットを有する。このため、行４５２のキャッシュミスを発生させたアドレスは、行４５１のキャッシュミスを発生させたアドレスの５１２バイト以内に存在していたため、行４５１の一致ビット配列の中央位置の左から３番目のビット（すなわち１１番目のＭＳＢ（ｂ１０））がセットされ、この結果、４５１にｈ４００の一致ビット配列値がセットされる。
【００５９】
図１３を参照すると、時間Ｔ３においてキャッシュミスを発生させる命令が実行されると、図１２を参照して説明したように、行４５３の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１および行４５２の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５３（ｈＦＥＤＣＣ２３４）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５３のミス位置は行４５１のミス位置から、−４４ブロックオフセットされていることがわかる。このため、行４５３の一致ビット配列は行４５１の中央ブロックの８ブロック以内になく、行４５１の一致ビット配列値が追加のプリフェッチ情報によって更新されることはない。行４５３のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果（ｈＦＥＤＣＣ２３４）、行４５３のミス位置は行４５２のミス位置から、＋４１ブロックオフセットされていることがわかる。このため、行４５３の一致ビット配列は行４５２の一致ビット配列の８ブロック以内になく、行４５２の一致ビット配列値が追加のプリフェッチ情報によって更新されることはない。
【００６０】
図１４を参照すると、時間Ｔ４においてキャッシュミスを発生させる命令が実行されると、図１２を参照して説明したように、行４５４の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５４〜４５３の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５４のミス位置は行４５１のミス位置から、−ｈ４ブロックオフセットされていることがわかる。ミス位置同士が４ブロック以内にあるため、一致ビット配列の中央位置の右から４番目のビット（ｂ４）をセットすることにより、行４５１の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５１の一致ビット配列にｈ４１０の値が記憶される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果、行４５４のミス位置は行４５２のミス位置から、−ｈ７ブロックオフセットされていることがわかる。ミス位置同士が８ブロック以内にあるため、一致ビット配列の中央位置の右から７番目のビット（ｂ１）をセットすることにより、行４５２の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５２の一致ビット配列にｈ０００２の値が記憶される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５４のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。
【００６１】
図１５を参照すると、時間Ｔ５において命令が実行されると、図１２を参照して説明したように、行４５５の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１〜４５４の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５５のミス位置は行４５１のミス位置から、＋ｈＡブロックオフセットされていることがわかり、このため、８ブロック以内にないため、行４５１の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果、行４５４のミス位置は行４５２のミス位置から、＋ｈ７ブロックオフセットされていることがわかる。ミス位置同士が８ブロック以内にあるため、行４５２の一致ビット配列の中央位置の左から７番目のビット（ｂ１４）をセットすることにより、行４５２の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５２の一致ビット配列にｈ４００２（図１５の軽微な変更）の値が記憶される。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５５のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５４のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５４（ｈＦＥＤＣＢ０２３）のミス位置を評価した結果、行４５５のミス位置は行４５１のミス位置から、＋ｈＥブロックオフセットされていることがわかり、このため、行４５４の一致ビット配列値への変更はない。
【００６２】
プリフェッチコントローラ３４０の動作について、図１６を参照して説明する。説明のため、図１５のテーブルに図示したプリフェッチ情報が、新たなキャッシュミスが発生した時点におけるプリフェッチ情報の現在の組であるとする。図１５は、キャッシュミス標識６１１を受け取るプリフェッチコントローラ３４０、キャッシュミス標識５１１を発生させた命令に対する命令ポインタ６１２、およびキャッシュミスを発生させたメモリ位置のミスアドレスを示す。
【００６３】
プリフェッチコントローラ３４０は、キャッシュミス標識を受け取ると、記憶場所３３０のプリフェッチ情報に、現在のキャッシュミスを発生させた命令ポインタに関連するレコードが含まれているかどうかを判定する。例えば、ｈ８１１１の命令ポインタ（ＩＰ）値を有する命令を実行した結果、発生したキャッシュミス標識を受け取った場合、この命令ポインタは、テーブル３４１に存在しないため、テーブル３４１でプリフェッチ情報が発見されない。しかし、命令ポインタｈ８１００にある命令を実行した結果、キャッシュミスが発生した場合、プリフェッチコントローラはテーブル３３１のプリフェッチ情報に２つのエントリ（行４５１および行４５４を参照）を発見する。プリフェッチコントローラ３４０は、最も古いエントリ（すなわち列４１４／行４２１によって表されるエントリ）を使用して、メモリコントローラ３５０にプリフェッチ要求を発行する。なお、別の実施形態では、図１０を参照して上で説明し、下記に更に説明するように、各命令ポインタに対して１つのエントリのみが保持される。
【００６４】
このため、図１６を参照すると、ｈ８１００の命令ポインタ値を有する命令によって、ミスアドレス６１３でキャッシュミスが発生すると、プリフェッチコントローラ３４０は、１つのアドレス値（ミスアドレス６１３−テーブル６３０においてビットｂ４に対応するオフセット（−ｈ１００））をメモリコントローラ３５０に提供し、別のアドレス値（ミスアドレス６１３−テーブル６３０においてビットｂ１０に対応するオフセット（ｈＣ０））をメモリコントローラ３５０に提供する。これらのアドレス値により、メモリコントローラ３５０によって２つのキャッシュラインがプリフェッチされる（これらが現在キャッシュ３６０に存在しない場合）。
【００６５】
本開示の特定の実施形態によれば、２つのテーブルが記憶場所３３０に保持される。１つ目のテーブル（例えばテーブル３４１）は、図１１〜１５を参照して説明したように、命令履歴バッファとして機能し、実行された一連の命令に対して、キャッシュミスとなったアドレスを相関させる。２つ目のテーブル（例えば図１７のテーブル３３４）は、プリフェッチコントローラ３４０が必要とする情報を格納しているレコードを有する。図１１の列５３１〜５３３は、上（図１０）で説明した列５２１〜５２３に対応している。列５３４は、テーブル３３４の所定の行に、プリフェッチ情報を定義している一致回数のカウントを記憶する。
【００６６】
一実施形態では（図１７参照）、各命令ポインタ（ＩＰ）に対して１つのレコードのみが保持され、同じＩＰ値を有するレコードがテーブル３４１から除去されると、テーブル３３４のレコードが更新される。テーブル３３４のレコードの一致カウンタ情報は、テーブル３３４の一致カウンタにテーブル３４１の一致カウンタを加算することで更新され、テーブル３３４の一致ビット配列は、テーブル３４１の一致ビット配列とテーブル３３４の一致ビット配列の論理和を求めることで更新される。
【００６７】
レコードの一致カウンタとキャッシュミスカウンタは、キャッシュミスの結果、テーブル３３４でＩＰがヒットした場合に、メモリコントローラにプリフェッチ情報を提示するべきかどうかを判定するために、プリフェッチ制御３４０によって使用されうる。例えば、プリフェッチ情報を生成するためにテーブル３３４のレコードが使用された回数（すなわち列５３３のキャッシュミスカウンタ値）が、一致ビット配列を定義している一致の回数（すなわち列５３４の一致カウンタ）と比べて十分大きな場合、レコードに記憶されているプリフェッチ情報がおそらく有用であることが一般に示される。一実施形態では、レコードに基づく情報について、（一致カウンタ）×（比率しきい値）＞（キャッシュミスカウンタ）が真となる場合にのみ、プリフェッチコントローラ３４０は、このレコードに基づいてプリフェッチ要求を生成する。ここで、比率しきい値とは、例えば２〜４の範囲の尺度値（scaling value）である。比率しきい値を大きな値に設定すると、帯域幅の消費が大きくなる点に留意されたい。
【００６８】
一実施形態では、テーブル３４１に保持されるレコード数は、テーブル３３４よりも少なくてもよい。例えば、テーブル３４１には、最近の３２回のキャッシュミスのそれぞれのレコードが含まれ、テーブル３３４には、数百〜数千もの命令ポインタのレコードが含まれてもよい。テーブル３３４は、テーブル３４１に上書きされている情報によって更新されうる。例えば、テーブル３４１の各レコードが一杯になると、新規レコードがテーブル３４１に記憶されるときに、最も古いキャッシュミス情報を含むレコードが削除される。しかし、削除の前に、上で説明したように、テーブル３４１の最も古いキャッシュミスレコードの情報が、テーブル３３３に情報を記憶するために使用されうる。テーブル３３４のエントリが定期的にクリアされうる点に留意されたい。例えば、テーブル３３４の行に対応するレコードを定期的に（例えば２０００サイクル毎など）クリアするために、図２の装置によって１つのポインタが使用されうる。
【００６９】
図１８は、本開示による方法を示す。ブロック７１１において、命令の実行の一環として情報がアクセスされる第１のメモリロケーションがキャッシュにおいて利用可能でない場合、第１のキャッシュミス標識が受信される。ブロック７１２において、第１のキャッシュミスにより、第１のキャッシュミスに基づく情報が、記憶位置の第１のレコードに記憶される。上で説明したように、この情報には、第１の命令のロケーションを特定する命令情報（命令ポインタなど）、およびブロック７１１において第１のキャッシュミスとなった命令によってアクセスされているメモリアドレスを特定するメモリ情報が含まれうる。ブロック７１２において、第１のキャッシュミスに基づく情報を格納しているレコードの例には、テーブル３３１〜３３４、および３４１の各行が含まれる。例えば、アクセスされているメモリロケーションを特定するメモリ情報は、メモリロケーションのアドレス、あるいは、整列領域（アドレス整列領域または中央ブロック整列領域など）からのオフセットなどである。メモリ情報が整列領域からのオフセットである場合、オフセット情報により、プリフェッチする情報の個々のバイトまたは全データブロックを特定することができる。上で説明した実施形態では、整列領域に関連する複数のデータブロックの１つに対応する１つのビット位置がアサートされる。別の実施形態では、メモリ情報に、特定の命令のロケーションに関連するアドレス範囲を特定する複数の値が含まれてもよい。
【００７０】
ブロック７１３において命令の実行の一環として情報がアクセスされる第２のメモリロケーションがキャッシュにおいて利用可能でない場合、第２のキャッシュミス標識が受信される。第２のメモリにアクセスしている命令は、ブロック７１１の第１の命令のこともあれば、別の命令のこともある。
【００７１】
ブロック７１４において、第２のキャッシュミスに基づいて情報が記憶される。一実施形態では、第２のキャッシュミスが、以前のキャッシュミスの整列領域内の関連するアドレスの結果発生した場合、その以前のキャッシュミスに関連するレコードが、追加のプリフェッチ情報を記憶することによって更新される。例えば、アドレス領域または中央ブロック整列領域内でキャッシュミスが発生すると、テーブル３３１〜３３４、および３４１のエントリが、このように更新される。キャッシュミスが発生すると、テーブル３３２〜３３４が、テーブル３３１および３４１にある情報によって更新されることに注意されたい。別の実施形態では、例えば、テーブル３３１〜３３４のエントリに関して上で説明したように、第２のキャッシュミスが発生すると、情報が記憶されて新規レコードが作成されてもよい。
【００７２】
図１９は、本開示による方法のフロー図を示す。ブロック７３１において、キャッシュミスが受信される。ブロック７３２において、第１の命令のために第１のメモリ位置へのアクセスが行われると、キャッシュミスが発生するかどうかが判定される。キャッシュミスが発生する場合は、フローはブロック７３３に進み、第１の命令のメモリ位置に基づいてプリフェッチ情報がアクセスされる。ブロック７３４において、プリフェッチされた情報に基づいて情報のブロックが記憶される。例えば、キャッシュラインと同じサイズを有する情報のブロックが、キャッシュラインに記憶されうる。
【００７３】
上記の明細書では、本発明の原理を、特定の実施形態に関連して上に記載した。しかし、下記の特許請求の範囲に記載の本発明の範囲内から逸脱することなく、実施形態のいずれか１つ以上に対して、１つ以上の修正または１つ以上の他の変更を加えることができることを、当業者は認めるであろう。例えば、プリフェッチ情報が、プリフェッチする各情報ブロックに対する重み値を含んでもよいことが理解されよう。例えば、頻繁にキャッシュミスとなるデータを含むブロックには、他のデータブロックよりも大きな重みが与えられうる。更に、本開示を一般にキャッシュミスに関して記載したが、本開示は、複数のレベルのキャッシュミスに対応することができることが理解されよう。例えば、Ｌ２キャッシュミスに関してトレーニングが行われ、Ｌ１キャッシュミスに関してプリフェッチ情報の生成が行われてもよい。また、システム３００が、集積回路装置３０１に変換索引バッファ（translation look-aside buffer：ＴＬＢ）を備え、仮想メモリのアクセス時に、Ｌ２のＴＬＢの電力を低減させ、負荷を軽減してもよい点も理解されよう。記憶場所３３０のさまざまな構成も考えられる。例えば、１つまたは複数のリードライトポートを有する記憶位置を使用してもよい。例えば、一致ビット配列は、飽和カウンタであってもよい。
【００７４】
本開示の特定の実施形態によれば、第１の命令の実行中に、第１のメモリロケーションへのアクセスが行われると、キャッシュミス標識が受信される。キャッシュミス標識を受けて、第１の命令のロケーションに基づいてプリフェッチ情報がアクセスされる。特定の実施形態は、プリフェッチ情報に基づいて、プリフェッチされた第１のメモリのブロックを第１のキャッシュラインに、プリフェッチされた第２のメモリのブロックを第２のキャッシュラインに記憶するステップを更に有してもよい。プリフェッチ情報は、第１のブロックを表す第１のビット位置、および第２のブロックへのオフセットを表す第２のビット位置を有するエントリを含みうる。また、エントリは、第３のメモリブロックに対するオフセットを表す第３のビット位置を更に含んでもよく、第３のビット位置は、第１のビット位置と第２のビット位置の間にあり、プリフェッチ情報は、複数の連続するアドレス位置を表し、プリフェッチフィールドの各ビットは、連続するアドレスロケーションの一部分に対応するブロックを表し、第１のブロック、第２のブロックおよび第３のブロックは、複数の連続するアドレス位置の異なる部分に対応している。したがって、本明細書および図面は、限定としてではなく例示としてみなすべきであり、あらゆるこのような修正や他の変更の全てが、発明の範囲内に含まれることが意図される。
【００７５】
１つ以上の利点、１つ以上の他の有利な点、１つ以上の問題に対する１つ以上の解決策、またはこれらの任意の組み合わせについて、１つ以上の特定の実施形態に関して記載した。しかし、利点、有利な点、問題に対する解決策、または想到されるかより明らかとなる何らかの利点、有利な点または解決策を生み出す任意の要素は、特許請求の範囲の重要、必要または本質的な特徴または要素であると解釈されるべきではない。
【図面の簡単な説明】
【００７６】
【図１】本開示の特定の実施形態による、命令によってアクセスされているアドレス位置に関連する各種のニーモニックを示す図。
【図２】本開示の特定の実施形態による装置を示す図。
【図３】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図４】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図５】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図６】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図７】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図８】図２のプリフェッチコントローラの一実施形態をより詳細に示す図。
【図９】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１０】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１１】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１２】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１３】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１４】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１５】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１６】図２のプリフェッチコントローラの別の実施形態をより詳細に示す図。
【図１７】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１８】本開示による方法を表すフロー図。
【図１９】本開示による方法を表すフロー図。
【図１】
2009540429.tif 000003
【図２】
2009540429.tif 000004
2009540429.tif 000005
【図３】
2009540429.tif 000006
【図４】
2009540429.tif 000007
【図５】
2009540429.tif 000008
【図６】
2009540429.tif 000009
【図７】
2009540429.tif 000010
【図８】
2009540429.tif 000011
【図９】
2009540429.tif 000012
【図１０】
2009540429.tif 000013
【図１１】
2009540429.tif 000014
【図１２】
2009540429.tif 000015
【図１３】
2009540429.tif 000016
【図１４】
2009540429.tif 000017
【図１５】
2009540429.tif 000018
【図１６】
2009540429.tif 000019
【図１７】
2009540429.tif 000020
【図１８】
2009540429.tif 000021
【図１９】
2009540429.tif 000022
【手続補正書】
【提出日】平成20年4月4日(2008.4.4)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【背景技術】
【０００１】
本出願は、データプロセッサの使用のために取得されるデータの決定に関し、より詳細には、データプロセッサのためにプリフェッチされる情報の決定に関する。
【０００２】
プリフェッチとは、データプロセッサを備えたコンピューティングデバイスに広く実装されている手法であり、この手法では、プロセッサが要求するデータおよび命令が、プロセッサが実際に必要としていると予想してプリフェッチされる。プリフェッチの結果、外部記憶装置に関連する低データレートではなく、プロセッサの内部バスアーキテクチャの比較的高いデータレートによって制限されるデータレートで、プロセッサが情報を利用できるようになる。このため、プリフェッチされた情報（データ、命令など）は、要求時にプロセッサがオンチップで利用可能であるため、通常は、プリフェッチによりプロセッサ全体の性能が改善される。
【発明の開示】
【０００３】
しかし、プリフェッチの実行が適切ではない場合には、結局はプロセッサが必要としない情報をプリフェッチすることによって、プリフェッチによりプロセッサまたはシステムの性能が低下しかねない。このため、特定のプリフェッチ手法は、あるタイプの用途では有利であるが、別のタイプの用途には適さないこともあるということが認められよう。このため、特定のタイプの用途のプリフェッチ効率を改善する、情報をプリフェッチするための方法および装置が有用であろう。
【０００４】
本発明は、添付の図面を参照することによって、より明確に理解することができ、その数多くの特徴および利点が当業者にとって明白となろう。
【発明を実施するための最良の形態】
【０００５】
本開示によれば、実行中にキャッシュミスとなった命令の位置（ロケーション）に基づいて、プリフェッチ情報がアクセスされる。アクセスされるプリフェッチ情報は、以前のキャッシュミスと現在のキャッシュミスの情報に基づいて決定される。例えば、以前のキャッシュミスに基づく情報が、プリフェッチ情報としてデータレコードに記憶される。このプリフェッチ情報は、以前のキャッシュミスを発生させた命令の位置（ロケーション）情報を含んでおり、現在のキャッシュミスのプリフェッチ要求を生成するためにアクセスされる。更に、現在のキャッシュミス情報に基づいて、プリフェッチ情報が更新される。本開示の特定の実施形態は、ここで図１〜１９の図面を参照すれば、より明確に理解できるであろう。
【０００６】
本開示の特定の実施形態を、一連の命令を実行した結果記憶されるプリフェッチ情報に関して記載する。図１は、複数の行を有するテーブル１１０が図示されており、その各行は、データプロセッサによる命令の実行に関連する情報を表している。テーブル１１０の列１１１は、対応する命令の実行時間を示す情報を含む。テーブル１１０の列１１２は、対応する命令への命令ポインタを特定する情報を含む。テーブル１１０の列１１３は、実行された命令を特定する情報を含む。
【０００７】
列１１１に記憶されている情報は、対応する命令が、テーブル１１０の他の命令に対して実行される相対順序を示す時間標識である。時間標識の末尾の数字により、ＩＮＳＴ２は、対応する時間標識Ｔ１を有するＩＮＳＴ１の後に実行されることが示される点に留意されたい。ＩＮＳＴ１とＩＮＳＴ２の間に別の命令が入らず、ＩＮＳＴ１とＩＮＳＴ２が連続的に実行されるとは限らない点に留意されたい。
【０００８】
列１１２の命令ポインタは、その対応する命令の位置（ロケーション）を示す。例えば、時間Ｔ１に実行される命令ＩＮＳＴ１は、図１では、ｈＦＦＦＦ１２３４という１６進値を有する。命令ポインタは、物理メモリ空間、論理メモリ空間を含む、どのようなタイプのメモリ空間の位置（ロケーション）を表してもよい。
【０００９】
ＩＮＳＴ１〜ＩＮＳＴ４は、実行時にキャッシュミスとなる命令である。ここでの説明のため、すべてのキャッシュミスが、ニーモニックＬＯＡＤｘのロード命令の結果発生するものとする。ロード命令のニーモニックの末尾の「ｘ」は、Ａ〜Ｚの値を有するアルファベット文字であり、特定のレジスタを識別する。このため、ニーモニックＬＯＡＤＡとＬＯＡＤＢは、メモリの情報にアクセスし、それぞれ、レジスタＡ１２１とレジスタＢ１２２にストアする命令を表す。
【００１０】
命令ＩＮＳＴ１〜ＩＮＳＴ４を実行する際には、各種のアドレス指定モードを使用してメモリ位置がアクセスされうる。ここに特に示すアドレス指定モードには、直接アドレス指定モードとレジスタ間接アドレス指定モードが含まれる。命令「ＬＯＡＤＢ  ｈＡＤＤＲ１」は、直接アドレス指定モードを使用するロード命令の例であり、ｈＡＤＤＲ１は、レジスタＢ１２１においてリードおよびストアされるメモリ位置を特定している１６進数である。先頭の文字「ｈ」は、値Ａｄｄｒ１が１６進数であることを示す点に留意されたい。命令「ＬＯＡＤＢ  ＜ＲＥＧＡ＞」は、記号「＜＞」が示すように、レジスタ間接アドレス指定モードの例であり、記号「＜＞」で囲んだレジスタにストアされている値は、この位置から情報がレジスタＢ１２１にリードおよびストアされるメモリ位置を特定している。
【００１１】
例えば、図１には、ＩＮＳＴ１が、レジスタ間接アドレス指定モードを使用するＬＯＡＤＢ命令であることが示されている。ニーモニック＜ＲＥＧ  Ａ＞は、レジスタＡ１２１に、その位置から情報を読み出すアドレス値が含まれることを特定している。レジスタＡ１２１の値は、ＡＤＤＲ（Ｔ１）であり、レジスタＡ１２１にストアされている情報が、命令ＩＮＳＴ１の実行中の時間Ｔ１に存在していたアドレス位置を表すことを示している。
【００１２】
説明のため、メモリ空間の各バイトが３２ビット値によってアドレス指定可能であるとする。先頭の文字「ｈ」は、ここでは１６進数を表すのに用いられる。このため、図１のレジスタＡ１２１にストアされている値は、３２ビット値であり、ビット順序を示す参照符号１２３に示すように、最上位ビット（ｂ３１）と最下位ビット（ｂ０）を有する。
【００１３】
特定のニーモニックを、各メモリ位置を表すビットｂ３１〜ｂ０の一部分と関連付ければ、ここでの説明がわかりやすくなるであろう。データプロセッサシステムは、各メモリアクセスによってアクセスされる最小バイト数を有しうることが理解されよう。ここでの説明のため、一度に４バイトずつアクセスされるとする。このため、最小アクセスブロックは、整列された４バイトの領域に関連するバイトを含む。この４バイト領域の各バイトはバイトインデックスによって特定され、本例では、これには、アドレスロケーションの下位２ビット（ＬＳＢ）が含まれる。図１に更に示すように、「ベースアドレス」との文言は、メモリ内で整列領域を特定するインデックス値を与える、各３２ビットメモリロケーションの所定の数の上位ビット（ＭＳＢ）を指す。図に示すように、図１の２２ビットのベースアドレスには、各アドレスロケーションの上位２２のＭＳＢ（ｂ３１〜ｂ１０）が含まれる。このため、それぞれが一意である２２ビットのベースアドレス値は、アドレス整列されたメモリ領域の先頭バイトを特定する。「アドレス整列されたメモリ領域」との文言は、オフセットを繰り返して整列された（例えば始点など）メモリの整列領域を指し、例えばアドレス値に基づいた、１キロバイト（２１０）おきのメモリ領域（例えばｈ０、ｈ４００、ｈ８００、ｈＣ００等）などである。ここに記載する別の整列されたメモリ領域として、中央ブロック整列されたメモリ領域があり、これは、中央にくる特定のメモリブロックに対する参照メモリブロックへの正負のインデックス値を使用する方式である。
【００１４】
オフセットは、整列領域内で特定の１以上のバイトをインデックスするかまたはアドレス指定するために使用される。例えば、１キロバイト領域内で任意の１バイトを特定するために、１０ビットのオフセットインデックス（オフセットインデックス１）が使用されうる。別の実施形態では、これより大きな整列領域内のバイトブロックの先頭バイトを特定するために、オフセットインデックスが使用されてもよい。例えば、オフセットインデックス２は、１キロバイト領域内で、特定の最小アクセスブロックを特定するために使用することができる８ビットのオフセットインデックスである。同様に、オフセットインデックス３は、キャッシュラインサイズに対応する１キロバイト領域内で、６４バイトメモリブロックの先頭バイトを特定するために使用することができる４ビットのオフセットである。例えば、メモリに対する各データ要求の結果、６４バイトのキャッシュラインが埋まるとすると、このキャッシュライン内の特定のバイトを特定するために、ビットｂ５〜ｂ０（ブロックインデックス）が使用され、オフセットインデックス３の特定の値は、２２ビットのベースアドレスによって定義される１キロバイトの整列領域内の１６個の６４バイトの領域の１つをインデックスしている。
【００１５】
別の実施形態では、同じ命令セットに基づくインデックストレーニングプリフェッチ情報が図３〜７に記載され、この方式では、ブロックオフセットは、キャッシュミスとなったブロックを表す中央位置に対するオフセットである。この位置は、正負のオフセットを使用することができるため、中央位置と呼ばれる。
【００１６】
図２は、本開示によるシステム３００を示す。システム３００は、表２２１に示す命令を実行するデータプロセッサ３１０；データプロセッサ３１０から情報を受信し、プリフェッチ情報を提供するように結合されたプリフェッチトレーニングモジュール３２０；プリフェッチトレーニングモジュール３２０からプリフェッチ情報を受信して、これを記憶する記憶場所３３０；記憶場所３３０にある情報に基づいてプリフェッチ要求を提供するプリフェッチコントローラ３４０；データプロセッサ３１０からメモリアクセス要求情報を、プリフェッチコントローラ３４０からメモリプリフェッチ要求を受け取り、メモリ３７０にメモリ要求を、プリフェッチトレーニングモジュール３２０およびプリフェッチ制御モジュールにキャッシュミス標識を提供するメモリコントローラ３５０；および、メモリコントローラ３５０から要求された情報を受け取り、これを提供するキャッシュ３６０を備える。図２の特定の実施形態では、集積回路装置３０１と外部コンポーネント３０２との間に境界が示されている。
【００１７】
データプロセッサ３１０内にテーブル２３１が示されており、テーブル３１１の各行はデータプロセッサ３１０によって実行される命令を表している。表３１１の各行において、列３１２は、命令の位置を示す命令ポインタを特定し、命令ポインタによってポイントされている命令が列３１３に一覧され、列３１１には、テーブル２３１の他の命令に対する各命令の実行の順序を示す時間シーケンス標識が一覧され、列３１４のアドレスは、一覧された命令によってアクセスされるメモリ位置を示す。
【００１８】
動作時に、データプロセッサ３１０は、特定の命令の実行を完了するのに必要な情報を含むメモリ位置を特定するアドレス情報を、メモリコントローラ３５０に提供する。メモリコントローラ３５０は、要求されたアドレスの情報がキャッシュ３６０に存在する場合はキャッシュ３６０から、存在しない場合はメモリ３７０から情報を提供する。要求された情報がキャッシュ３６０で利用できない場合、メモリコントローラ３５０はキャッシュミスを発生させる。データプロセッサ３１０によって要求された情報は、取得されると、プロセッサ３１０とキャッシュ３６０に提供される。メモリコントローラ３５０は、一般に、データプロセッサ３１０が必要とする情報を格納しているアドレスの近くのアドレス位置にある情報によって、キャッシュ３６０のキャッシュライン全体を埋めることが理解されよう。説明のため、キャッシュ３６０の各キャッシュラインが長さ６４バイトであるとする。
【００１９】
プリフェッチコントローラは、メモリコントローラ３５０からキャッシュミスを受け取ると、記憶場所３３０にあるプリフェッチ情報に基づいて、キャッシュミスの結果、プリフェッチすべき追加の情報があるかどうかを判定する。ここに記載の特定の実施形態によれば、キャッシュミスを発生させた命令の命令ポインタが使用され、関連するプリフェッチ情報が記憶場所３３０に存在するどうかが判定される。プリフェッチ要求の生成時のレーテンシを短縮するために、記憶場所３３０は、通常、プリフェッチコントローラと同じ集積回路装置に存在する点に留意されたい。一実施形態では、テーブル２２１にあるレコードを格納している記憶場所３３０の部分は、現在のキャッシュミスを発生させている命令の命令ポインタを使用してアクセスされる連想メモリ（content addressable memory）であってもよい。キャッシュミスを発生させた命令に関連するエントリが、記憶場所３３０に格納されている場合、プリフェッチコントローラ３４０は、記憶場所３３０に記憶されている情報に基づいて、メモリコントローラ３５０にプリフェッチアドレス情報を提供する。この結果、メモリコントローラ３５０は、プリフェッチコントローラから要求されている情報が、既にキャッシュ３６０にあるかどうかを判定する。ない場合、メモリコントローラ３５０は、メモリ３７０から情報を取得し、キャッシュ３６０の追加のキャッシュラインを埋める。プリフェッチトレーニングモジュールの動作と、テーブル３１１の情報の決定方法について、記憶場所３３０でのプリフェッチ情報のトレーニングの特定の例を示す図３〜７を参照して説明する。
【００２０】
図３〜７は、それぞれ、データプロセッサ３１０で実行されている、テーブル２２１中の命令によりキャッシュミスが発生した際の、記憶場所３３０でのプリフェッチ情報のトレーニングを示す。図３〜７のそれぞれは、テーブル２２１の一番下の行には現在のキャッシュミスを発生させている現在の命令が含まれ、列３１２の命令は現在実行中であり、以前に実行された命令（存在する場合）も含む。更に、図３〜７のそれぞれは、プリフェッチトレーニングモジュール３２０によって、記憶場所３３０にあるテーブル３３１に提供されるプリフェッチ情報を示す。記憶場所３３０に記憶されるプリフェッチ情報は、テーブル３３１の表形式で表され、各行は、キャッシュミスに関連する情報を格納している情報のレコードを表している。キャッシュミスを発生させたメモリアドレスは、列４１１のミスベースアドレスと、列４１３のミスオフセットによって特定される。説明のため、ミスベースアドレスは、メモリ空間内の１キロバイトの整列領域を特定する２２ビットのインデックスであるとする。このため、３２ビットアドレスの場合、各ミスベースアドレス値は、ミスを発生させたアドレスの上位２２ビットを表す２２ビットの１６進数（ミスアドレス）によって表される。列４１３に記憶されるミスオフセット値は、ミスベースアドレスによって特定される１キロビット領域に対するオフセットを表す１０ビット数である。命令ポインタ（ＩＰ）値は、列４１２に記憶され、キャッシュミスを発生させた命令の位置を特定する。プリフェッチするメモリロケーションの特定に使用されるプリフェッチ情報は、列４１４の一致ビット配列に記憶される。列４１５には一致カウンタが保持される。
【００２１】
プリフェッチ情報を記憶するためのテーブル３３１のレコード数は、固定数でも可変でもよい。一実施形態では、記憶位置は、図２の３０１によって表される集積回路装置上のモジュールを含む半導体デバイスの固定記憶位置である。
【００２２】
図３は、時間Ｔ１で命令ＬＯＡＤＢ  ＜ＲＥＧ  Ａ＞の実行によって発生したキャッシュミスの影響を示している。具体的には、時間Ｔ１でのキャッシュミスの結果、新規レコードがテーブル３３１の行４２１に作成される。時間Ｔ１のキャッシュミスの原因となった命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞への命令ポインタを表す情報は、テーブル３３１の列４１２／行４２１に記憶される。キャッシュ３６０に存在せず、時間Ｔ１でミスを発生させたミスアドレスを表す情報は、ミスベースアドレスとして列４１１に、ミスオフセットとして列４１３に記憶される。例えば、ミスアドレス（ｈＦＥＤＣＢ１２３）の上位２２ビットを含む２２ビットのミスベースアドレス（ｈ３ＦＢ７２Ｃ）が、テーブル３３１の列４１１／行４２１に記憶される。ミスベースアドレス値は、メモリの１キロバイトの整列領域を特定する。メモリ内での１キロバイト領域の開始点は、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）にｈ４００を掛け、これにより、ベースアドレスに、１０個のゼロをＬＳＢとして追加することで求めることができる。例えば、ｈ３ＦＢ７２Ｃ×ｈ４００＝ｈＦＥＤＣＢ０００となる。
【００２３】
キャッシュミスを発生させたアドレスの残りの１０ビットは、ミスオフセットとして列４１３／行４２１に記憶される。上で説明したように、ミスオフセットを表すのに必要なビット数が変更されてもよい点に留意されたい。例えば、メモリが一度に４バイトずつアクセスされる場合には、キャッシュミスを発生させたメモリ位置を格納しているメモリの位置を特定するのに、１０ビットのうちの８ビットしか必要ではなく、１０ビットのオフセットを保持する必要はない。同様に、１キロビットの整列メモリ領域内の１６個の可能なキャッシュライン位置の１つを特定するには、４ビットのオフセット値で足りる。例えばミスオフセットの値が０の場合には、１キロバイトの整列領域の先頭バイトでメモリのアクセスが開始され、ミスオフセットの値が１の場合、１キロバイト領域の６５番目のバイトでメモリのアクセスが開始される。
【００２４】
時間Ｔ１においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを特定する（ミスベースアドレスの値によって特定される）ために、列４１４／行４２１の一致ビット配列に値が記憶される。一実施形態では一致ビット配列は、１６ビットの値を記憶し、１６ビット値の各ビット（ｂ１５〜ｂ０）は、上で説明したように、１キロバイト領域を構成している１６個の６４ビットデータブロックの１つに対応している。例えば、列４１３／行４２１のミスオフセットｈ１２３に対応するビットは、ミスオフセット値を６ビット右シフトすることで求められる。例えば、値ｈ１２３を６ビットシフトさせると、ｈ００１０の１６進値が得られ、これは００００  ００００  ０００１  ００００の２進値に対応している。この結果、時間Ｔ１においてミスを発生させたメモリアドレスが、１キロバイトの整列領域の５番目の６４ビットブロックに存在することを示すように、一致ビット配列の第５ビット（ｂ４）がセットされる。
【００２５】
行４２１の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００２６】
図４は、時間Ｔ２での命令ＬＯＡＤＣ  ｈＦＥＤＣＢ１Ｅ７の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図４の矢印４９２は、現在のキャッシュミスによって影響されるレコードを表す行をポイントしており、これらのレコードには、行４２１によって表されるレコードと、行４２２によって表される新規レコードが含まれる。
【００２７】
時間Ｔ２でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２２に記憶される。時間Ｔ２においてミスを発生させた命令によってアクセスされているアドレス位置（ｈＦＥＤＣＢ１Ｅ７）を表す情報が、ミスベースアドレス（Ｈ３ＦＢ７２Ｃ）として列４１１／行４２２に、１０ビットのミスオフセット（ｈ１Ｅ７）として列４１３／行４２２に記憶される。
【００２８】
時間Ｔ２においてキャッシュミスを発生させたメモリロケーションを格納している１キロバイトの整列領域の６４バイトブロックを示す（ミスベースアドレスの値によって特定される）ために、列４１４／行４２２の一致ビット配列に値が記憶される。行４２２のミスオフセットｈ１Ｅ７に対応する６４バイトブロックは、第７ビット（ｂ６）であり、時間Ｔ２でのキャッシュミスの結果、列４１４／行４２２にｈ００８０の一致ビット配列値が記憶される。
【００２９】
列４１５／行４２２のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００３０】
新たにキャッシュミスが発生するたびに、テーブル３３１の既存のレコードのそれぞれが評価され、前に記憶されたレコードのうち、同じ１キロバイトの整列領域に対応するミスベースアドレスを有するものが存在するかどうかがチェックされる。例えば、行４２１と行４２２は、同じベースミスアドレス値（ｈ３ＦＢ７２Ｃ）を有するため、これらのキャッシュミスの両方を発生させたアクセスのメモリが、同じ１キロバイトの整列領域に記憶されていると判定される。このため、現在の（Ｔ２）ミスベースアドレスが以前のミスベースアドレスに一致していると、以前の一致ビット配列が更新される。例えば、現在の一致ビット配列と以前のミスビット配列の論理和を求めることによって、列４１４／行４２１の以前のミスベースアドレスに情報が記憶される。例えば、時間Ｔ２でのキャッシュミスの結果、プリフェッチトレーニングモジュールから情報が提供され、行４２１の一致ビット配列の値が、値ｈ００９０（ｈ００１０  ＯＲ  ｈ００８０）に更新される。
【００３１】
行４２１の列４１５のカウンタ値が、現在のミスの結果一致ビット配列情報が更新されたことを示すように１インクリメントされる。
【００３２】
図５は、時間Ｔ３での命令ＬＯＡＤＢ  ｈＦＥＤＣＣ２３４の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図５の矢印４９３は、現在のキャッシュミスによって影響されるレコードを表す行をポイントしており、このレコードには、行４２３によって表される新規レコードのみが含まれる。
【００３３】
時間Ｔ３でキャッシュミスの原因となった命令への命令ポインタを表す情報が、テーブル３３１の列４１２／行４２３に記憶される。時間Ｔ３においてミスを発生させた命令によってアクセスされているアドレスロケーション（ｈＦＥＤＣＣ２３４）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７３０）として列４１１／行４２３に、１０ビットのミスオフセット（ｈ２３４）として列４１３／行４２３に記憶される。
【００３４】
時間Ｔ３においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを示す（ミスベースアドレスの値によって特定される）ために、列４１４／行４２３の一致ビット配列に値が記憶される。行４２１のミスオフセットｈ２３４に対応する６４バイトブロックは、第９ビット（ｂ８）であり、時間Ｔ３でのキャッシュミスの結果、行４２３の列４１４にｈ０１００の一致ビット配列値が記憶される。
【００３５】
行４２３の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００３６】
時間Ｔ３でキャッシュミスを発生させたアドレスは、テーブル３３１の他のレコードと同じミスベースアドレスを持たないため、時間Ｔ３のキャッシュミスが、テーブル３３１の他のレコードに影響することはない。
【００３７】
図６は、時間Ｔ４での命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図６の矢印４９４は、現在のキャッシュミスによって影響されるレコードをポイントしており、これらのレコードには、行４２１と行４２２によって表されるレコードと、行４２４によって表される新規レコードが含まれる。
【００３８】
時間Ｔ４でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２４に記憶される。時間Ｔ４においてミスを発生させた命令によってアクセスされているアドレス位置（ｈＦＥＤＣＣ２３４）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）として列４１１／行４２４に、１０ビットのミスオフセット（ｈ２３）として列４１３／行４２４に記憶される。
【００３９】
時間Ｔ４においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域内の６４バイトブロックの位置を示すために、列４１４／行４２４の一致ビット配列に値が記憶される。ミスオフセットｈ２３を格納している６４バイトブロックに対応するビットは、第１ビット（ｂ０）であり、時間Ｔ４でのキャッシュミスの結果、列４１４／行４２４にｈ０００１の一致ビット配列値が記憶される。
【００４０】
行４２４の列４１５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００４１】
また、時間Ｔ４でのキャッシュミスの結果、テーブル３３１の２つの既存のレコードも、これらのレコードが同じ１キロバイトの整列領域のインデックスを有するため、追加のプリフェッチ情報によって更新される。例えば、列４１４／行４２１と列４１４／行４２２のプリフェッチ情報は、いずれも、現在のキャッシュミスを表す４２４と同じミスアドレス値（ｈ３ＦＢ７２Ｃ）値を有するため、更新する必要がある。このため、列４１４／行４２１の一致ビット配列がｈ００９１に更新され、列４１４／行４２２の一致ビット配列が００８１に更新される。行４２１および行４２２のプリフェッチ情報の更新が発生するのは、時間Ｔ４で必要とされた情報が、仮に、時間Ｔ１または時間Ｔ２のいずれかでプリフェッチされていたならば、時間Ｔ４でのキャッシュミスを回避できたためであることが理解されよう。この点については、更に別の実施形態に関してここに後述する。
【００４２】
行４２１と行４２２の列４１５のカウンタ値が、現在のミスの結果、それぞれの行の一致ビット配列情報が更新された回数を示すように、１インクリメントされる。
【００４３】
図７は、時間Ｔ５での命令ＬＯＡＤＣ  ＜ＲＥＧＢ＞の実行に関連するキャッシュミスの発生により、プリフェッチトレーニングモジュール３２０によってテーブル３３１に提供される情報を示す。図７の矢印４９５は、現在のキャッシュミスによって影響されるレコードをポイントしており、これらのレコードには、行４２１、行４２２、行４２４によって表されるレコードと、行４２５によって表される新規レコードが含まれる。
【００４４】
時間Ｔ５でキャッシュミスの原因となった命令への命令ポインタを表す情報が、列４１２／行４２５に記憶される。時間Ｔ５においてミスを発生させた命令によってアクセスされているアドレス位置（ＨＦＥＤＣＢ３Ｃ５）を表す情報が、ミスベースアドレス（ｈ３ＦＢ７２Ｃ）として列４１１／行４２５に、１０ビットのミスオフセット（ｈ３Ｃ５）として列４１３／行４２５に記憶される。
【００４５】
時間Ｔ５においてキャッシュミスを発生させたメモリ位置を格納している１キロバイトの整列領域の６４バイトブロックを示すために、列４１４／行４２４の一致ビット配列に値が記憶される。行４２１のミスオフセットｈ３ＣＦに対応する６４バイトブロックは、第１６ビット（ｂ１５）であり、時間Ｔ５でのキャッシュミスの結果、列４１４／行４２５にｈ８０００の一致ビット配列値が記憶される。
【００４６】
列４１５／行４２５のカウンタは、ゼロにセットされている場合、一致ビット配列情報がその後発生したキャッシュミスによって更新されていないことを示す。
【００４７】
また、新たにキャッシュミスが発生するたびに、テーブル３３１の既存のレコードのそれぞれが評価され、前に記憶されたレコードのうち、同じ１キロバイトの整列領域に対応するミスベースアドレスを有するものが存在するかどうかがチェックされる。本例では、行４２１、行４２２および行４２４のプリフェッチ情報は、いずれも、現在のキャッシュミスを表す行４２５のミスアドレス値（ｈ３ＦＢ７２Ｃ）と同じ値を有するため、更新する必要がある。このため、行４２１の一致ビット配列がｈ８０９１に更新され、行４２２の一致ビット配列がｈ８０８１に更新され、行４２４の一致ビット配列がｈ８００１に更新される。
【００４８】
行４２１、行４２２および行４２４の列４１５のカウンタ値が、現在のミスの結果、それぞれの行の一致ビット配列情報が更新された回数を示すように、１インクリメントされる。
【００４９】
プリフェッチコントローラ３４０の動作について、図８を参照して説明する。説明のため、図７に図示したプリフェッチ情報が、新たなキャッシュミスが発生した時点におけるプリフェッチ情報の現在の組であるとする。図８は、キャッシュミス標識５１１を受け取るプリフェッチコントローラ３４０、キャッシュミス標識５１１を発生させた命令に対する命令ポインタ５１２、およびキャッシュミスを発生させたメモリ位置のミスベースアドレスを示す。
【００５０】
プリフェッチコントローラ３４０は、キャッシュミス標識を受け取ると、記憶場所３３０のプリフェッチ情報に、現在のキャッシュミスを発生させた命令ポインタに関連するレコードが含まれているかどうかを判定する。例えば、命令ポインタｈ８１１１を有する命令を実行した結果、発生したキャッシュミス標識を受け取った場合、この命令ポインタは、テーブル３３１に存在しないため、テーブル３３１でプリフェッチ情報が発見されない。しかし、命令ポインタｈ８１００にある命令を実行した結果、キャッシュミスが発生した場合、プリフェッチコントローラはテーブル３３１のプリフェッチ情報に２つのエントリ（行４２１および行４２４を参照）を発見する。プリフェッチコントローラ３４０は、最も古いエントリ（すなわち列４１４／行４２１によって表されるエントリ）を使用して、メモリコントローラ３５０にプリフェッチ要求を発行する。
【００５１】
プリフェッチコントローラ３４０からのプリフェッチ要求には、以前にメモリがアクセスされた特定のメモリブロックに関連するメモリアドレスが提示される。列４１４／行４２１の一致ビット配列のセットされたビットのそれぞれは、６４ビットメモリブロックに対応しているため、プリフェッチコントローラは、メモリコントローラ３５０に４つのメモリプリフェッチ要求を提示する。例えば、行４２１の一致ビット配列値ｈ８０９１には、以前にデータがアクセスされた４つのメモリブロックに対応する４つのビット（ｂ１５、ｂ８、ｂ４およびｂ０）がセットされている。このため、プリフェッチコントローラは、メモリコントローラ３５０に４つのメモリアドレス（４つのブロックに対して１つずつ）を提供する。プリフェッチコントローラ３４０は、対応するブロックの全６４バイトをプリフェッチするために、６４バイトブロック内の任意のアドレスをメモリコントローラ３６０に提供することができる。一致ビット配列内のセットされたビットに対応するメモリブロックの先頭バイトは、対応するミスベース配列値を１０ビット左シフトし、この結果に、セットされたビットに対応する図８のテーブル５３０のオフセットを加算して求めることができる。このため、ｈ８０９１の一致ビット配列値の場合、プリフェッチコントローラは、１キロバイトの境界の先頭バイトから、ｈ０００（ｂ０）、ｈ１００（ｂ４）、ｈ２００（ｂ８）およびｈ３Ｃ０（ｂ１５）だけオフセットされたアドレスロケーションを要求しうる。
【００５２】
本発明の一実施形態では、プリフェッチ要求を生成するために使用される１キロバイトの境界は、プリフェッチコントローラ３４０が受け取る現在のミスベースアドレスである。このため、図８を参照すると、ミスベースアドレス５１３が、ｈＣＦＦＦＦＦの２２ビット値を有する場合、プリフェッチコントローラ３４０は、ＦＦＦＦＦＣ００（ｂ０）、ＦＦＦＦＦＤ００（ｂ４）、ＦＦＦＦＦＤＣ０（ｂ８）、およびＦＦＦＦＦＦＣ０（ｂ１５）の各アドレス値をメモリコントローラ３５０に提供する。これらのアドレス値により、メモリコントローラ３５０によって４つのキャッシュラインがプリフェッチされる（これらが現在キャッシュ３６０に存在しない場合）。連続するメモリブロックを含む大きなメモリ領域をプリフェッチするのではなく、プリフェッチされるメモリブロックが、メモリの不連続な領域であってもよい点に留意されたい。
【００５３】
なお、その後発生したキャッシュミスのうち、共通する１キロバイトのメモリ領域に存在するものを決定するために、プリフェッチトレーニング中にテーブル３３１の列４１１にあるミスベースアドレス情報が必要とされるが、プリフェッチコントローラはミスベースアドレス情報を必要とせず、現在のキャッシュミスのミスベースアドレスを使用して、プリフェッチアドレスを生成する。このため、プリフェッチコントローラ３４０がプリフェッチ要求を生成するために使用する別のテーブルを保持することができる。図９は、記憶場所３３０に記憶することができるテーブル３３２を示し、このテーブルはプリフェッチコントローラ３４０が使用するプリフェッチ情報を格納している。具体的には、テーブル３３２の列９１１に命令ポインタ情報が記憶され、列５１２に一致ビット配列情報が記憶される。テーブル３３２は、各命令ポインタ値に対して複数のレコードを保持するのではなく、所定の命令ポインタに対して１つのレコードのみを含む。これにより、テーブル３３２は、キャッシュミスの発生時に、現在のキャッシュミスの原因となった命令ポインタ値を使用して、プリフェッチコントローラによってアクセスされる連想メモリが可能となる。連想メモリに対する要求により、列５１１に一致する命令ポインタが特定された場合、その対応する一致ビット配列がプリフェッチコントローラ３４０によって使用され、メモリコントローラ３５０にプリフェッチアドレスが提示される。
【００５４】
図１０は、プリフェッチコントローラ３４０によって使用されるプリフェッチ情報を記憶するために、テーブル３３２の代わりに使用することができるテーブル３３３の別の実施形態を示す。列９２１および列９２２は、上で説明した列９１１および列９１２に対応している。ただし、テーブル３３３には、キャッシュミスカウンタを保持するための列９２３が含まれる。キャッシュミスカウンタ値は、プリフェッチコントローラが、キャッシュミスの際に、特定のレコードを使用してプリフェッチ要求を発生させた回数を示す。このため、レコードのキャッシュミスカウンタは、プリフェッチ要求を生成するために、その一致ビット配列情報が使用されるたびにインクリメントされる。
【００５５】
上で説明した以外の別のオフセット方式を使用することができ、上の方式では、ブロックオフセットは、３２ビットアドレスの上位２２ビットによって定義される１キロバイトのメモリ境界に基づいた整列領域の先頭に対するオフセットであることが理解されよう。例えば、図１１〜１５は、図３〜７に図示したのと同じ命令セットに基づくトレーニングプリフェッチ情報の別の実施形態を示しており、この方式では、ブロックオフセットは、キャッシュミスとなったブロックを表す中央位置に対するオフセットである。この位置は、正負のオフセットを使用することができるため、中央位置と呼ばれる。
【００５６】
図１１〜１５を参照すると、記憶場所３３０に記憶されるプリフェッチ情報は、テーブル３４１の表形式で表され、各行は、キャッシュミスに関連する情報を格納している情報のレコードを表している。列４１１〜４１３および列４１５は、列３４１〜３４３および列３４５に関して上で説明した情報を記憶する。列４４４は、キャッシュミスの原因となったアドレスを含むメモリブロックを中心とする整列領域内に、プリフェッチ情報を記憶する。このため、テーブル３４１の行４５１の各エントリの８つのＭＳＢは、中央ブロックの前の８つの６４バイトデータブロックの１つを表し、行４５１の各エントリの８つのＬＳＢは、中央の６５バイトブロックの後の８つの６４バイトデータブロックの１つを表す。
【００５７】
図１１を参照すると、時間Ｔ１において命令ＬＯＡＤＢ  ＜ＲＥＧＡ＞が実行されると、列４４４／行４５１の一致ビット配列がクリアされる（例えば、全ビットがゼロにセットされる）。エントリが作成されると、一致ビット配列がクリアされる点に留意されたい。この理由は、ミスを発生させたアドレスを格納している６４バイトデータブロック（例えば図１１のｈＦＥＤＣＢ１２３）が参照点となり、この点から、プリフェッチ情報を表す他のブロックオフセットが求められるためである。
【００５８】
図１２を参照すると、時間Ｔ２においてキャッシュミスを発生させた命令が実行されると、行４５２の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１の情報が評価されて、このプリフェッチ情報を更新すべきかどうかが判定される。本実施形態に関しては、現在のキャッシュミスを発生させたメモリ位置が８つの６４バイトメモリブロック内（すなわち、±５１２バイト）に存在する場合、特定の行のプリフェッチ情報が更新される。この値は、（６ビット右シフトさせた現在のミスアドレス）−（６ビットシフトさせた評価される行のミスアドレス）の式によって求めることができる。このため、図１２に関して、現在のキャッシュミスを発生させたメモリ位置（ｈＦＥＤＣＢ１Ｅ７）は、行４５１のキャッシュミスを発生させたメモリ位置（ｈＦＥＤＣＢ１２３）に対し、＋ｈ３（（６ビット右シフトさせたｈＦＥＤＣＢ１Ｅ７）−（６ビット右シフトさせたｈＦＥＤＣＢ１２３））のブロックオフセットを有する。このため、行４５２のキャッシュミスを発生させたアドレスは、行４５１のキャッシュミスを発生させたアドレスの５１２バイト以内に存在していたため、行４５１の一致ビット配列の中央位置の左から３番目のビット（すなわち１１番目のＭＳＢ（ｂ１０））がセットされ、この結果、４５１にｈ４００の一致ビット配列値がセットされる。
【００５９】
図１３を参照すると、時間Ｔ３においてキャッシュミスを発生させる命令が実行されると、図１２を参照して説明したように、行４５３の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１および行４５２の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５３（ｈＦＥＤＣＣ２３４）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５３のミス位置は行４５１のミス位置から、−４４ブロックオフセットされていることがわかる。このため、行４５３の一致ビット配列は行４５１の中央ブロックの８ブロック以内になく、行４５１の一致ビット配列値が追加のプリフェッチ情報によって更新されることはない。行４５３（ｈＦＥＤＣＣ２３４）のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果、行４５３のミス位置は行４５２のミス位置から、＋４１ブロックオフセットされていることがわかる。このため、行４５３の一致ビット配列は行４５２の一致ビット配列の８ブロック以内になく、行４５２の一致ビット配列値が追加のプリフェッチ情報によって更新されることはない。
【００６０】
図１４を参照すると、時間Ｔ４においてキャッシュミスを発生させる命令が実行されると、図１２を参照して説明したように、行４５４の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５４〜４５３の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５４のミス位置は行４５１のミス位置から、−ｈ４ブロックオフセットされていることがわかる。ミス位置同士が４ブロック以内にあるため、一致ビット配列の中央位置の右から４番目のビット（ｂ４）をセットすることにより、行４５１の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５１の一致ビット配列にｈ４１０の値が記憶される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果、行４５４のミス位置は行４５２のミス位置から、−ｈ７ブロックオフセットされていることがわかる。ミス位置同士が８ブロック以内にあるため、一致ビット配列の中央位置の右から７番目のビット（ｂ１）をセットすることにより、行４５２の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５２の一致ビット配列にｈ０００２の値が記憶される。行４５４（ｈＦＥＤＣＢ０２３）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５４のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。
【００６１】
図１５を参照すると、時間Ｔ５において命令が実行されると、図１２を参照して説明したように、行４５５の一致ビット配列がクリアされ（例えば、全ビットがゼロにセットされ）、テーブル３４１の行４５１〜４５４の情報が評価されて、更新すべきプリフェッチ情報が存在するかどうかが判定される。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５１（ｈＦＥＤＣＢ１２３）のミス位置を評価した結果、行４５５のミス位置は行４５１のミス位置から、＋ｈＡブロックオフセットされていることがわかり、このため、８ブロック以内にないため、行４５１の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５２（ｈＦＥＤＣＢ１Ｅ７）のミス位置を評価した結果、行４５４のミス位置は行４５２のミス位置から、＋ｈ７ブロックオフセットされていることがわかる。ミス位置同士が８ブロック以内にあるため、行４５２の一致ビット配列の中央位置の左から７番目のビット（ｂ１４）をセットすることにより、行４５２の一致ビット配列が、追加のプリフェッチ情報によって更新される。この結果、行４５２の一致ビット配列にｈ４００２（図１５の軽微な変更）の値が記憶される。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５５のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５３（ｈＦＥＤＣＣ２３４）のミス位置を評価した結果、行４５４のミス位置は行４５３のミス位置から、８ブロックを越えるブロック数オフセットされていることがわかり、このため、行４５３の一致ビット配列値への変更はない。行４５５（ｈＦＥＤＣＢ３Ｃ５）のミス位置に対して、行４５４（ｈＦＥＤＣＢ０２３）のミス位置を評価した結果、行４５５のミス位置は行４５１のミス位置から、＋ｈＥブロックオフセットされていることがわかり、このため、行４５４の一致ビット配列値への変更はない。
【００６２】
プリフェッチコントローラ３４０の動作について、図１６を参照して説明する。説明のため、図１５のテーブルに図示したプリフェッチ情報が、新たなキャッシュミスが発生した時点におけるプリフェッチ情報の現在の組であるとする。図１５は、キャッシュミス標識６１１を受け取るプリフェッチコントローラ３４０、キャッシュミス標識５１１を発生させた命令に対する命令ポインタ６１２、およびキャッシュミスを発生させたメモリ位置のミスアドレスを示す。
【００６３】
プリフェッチコントローラ３４０は、キャッシュミス標識を受け取ると、記憶場所３３０のプリフェッチ情報に、現在のキャッシュミスを発生させた命令ポインタに関連するレコードが含まれているかどうかを判定する。例えば、ｈ８１１１の命令ポインタ（ＩＰ）値を有する命令を実行した結果、発生したキャッシュミス標識を受け取った場合、この命令ポインタは、テーブル３４１に存在しないため、テーブル３４１でプリフェッチ情報が発見されない。しかし、命令ポインタｈ８１００にある命令を実行した結果、キャッシュミスが発生した場合、プリフェッチコントローラはテーブル３４１のプリフェッチ情報に２つのエントリ（行４５１および行４５４を参照）を発見する。プリフェッチコントローラ６４０は、最も古いエントリ（すなわち列４４４／行４２１によって表されるエントリ）を使用して、メモリコントローラ３５０にプリフェッチ要求を発行する。なお、別の実施形態では、図１０を参照して上で説明し、下記に更に説明するように、各命令ポインタに対して１つのエントリのみが保持される。
【００６４】
このため、図１６を参照すると、ｈ８１００の命令ポインタ値を有する命令によって、ミスアドレス６１３でキャッシュミスが発生すると、プリフェッチコントローラ３４０は、１つのアドレス値（ミスアドレス６１３−テーブル６３０においてビットｂ４に対応するオフセット（−ｈ１００））をメモリコントローラ３５０に提供し、別のアドレス値（ミスアドレス６１３−テーブル６３０においてビットｂ１０に対応するオフセット（ｈＣ０））をメモリコントローラ３５０に提供する。これらのアドレス値により、メモリコントローラ３５０によって２つのキャッシュラインがプリフェッチされる（これらが現在キャッシュ３６０に存在しない場合）。
【００６５】
本開示の特定の実施形態によれば、２つのテーブルが記憶場所３３０に保持される。１つ目のテーブル（例えばテーブル３４１）は、図１１〜１５を参照して説明したように、命令履歴バッファとして機能し、実行された一連の命令に対して、キャッシュミスとなったアドレスを相関させる。２つ目のテーブル（例えば図１７のテーブル３３４）は、プリフェッチコントローラ３４０が必要とする情報を格納しているレコードを有する。図１１の列９３１〜９３３は、上（図１０）で説明した列９２１〜９２３に対応している。列９３４は、テーブル３３４の所定の行に、プリフェッチ情報を定義している一致回数のカウントを記憶する。
【００６６】
一実施形態では（図１７参照）、各命令ポインタ（ＩＰ）に対して１つのレコードのみが保持され、同じＩＰ値を有するレコードがテーブル３４１から除去されると、テーブル３３４のレコードが更新される。テーブル３３４のレコードの一致カウンタ情報は、テーブル３３４の一致カウンタにテーブル３４１の一致カウンタを加算することで更新され、テーブル３３４の一致ビット配列は、テーブル３４１の一致ビット配列とテーブル３３４の一致ビット配列の論理和を求めることで更新される。
【００６７】
レコードの一致カウンタとキャッシュミスカウンタは、キャッシュミスの結果、テーブル３３４でＩＰがヒットした場合に、メモリコントローラにプリフェッチ情報を提示するべきかどうかを判定するために、プリフェッチ制御３４０によって使用されうる。例えば、プリフェッチ情報を生成するためにテーブル３３４のレコードが使用された回数（すなわち列９３３のキャッシュミスカウンタ値）が、一致ビット配列を定義している一致の回数（すなわち列９３４の一致カウンタ）と比べて十分大きな場合、レコードに記憶されているプリフェッチ情報がおそらく有用であることが一般に示される。一実施形態では、レコードに基づく情報について、（一致カウンタ）×（比率しきい値）＞（キャッシュミスカウンタ）が真となる場合にのみ、プリフェッチコントローラ３４０は、このレコードに基づいてプリフェッチ要求を生成する。ここで、比率しきい値とは、例えば２〜４の範囲の尺度値（scaling value）である。比率しきい値を大きな値に設定すると、帯域幅の消費が大きくなる点に留意されたい。
【００６８】
一実施形態では、テーブル３４１に保持されるレコード数は、テーブル３３４よりも少なくてもよい。例えば、テーブル３４１には、最近の３２回のキャッシュミスのそれぞれのレコードが含まれ、テーブル３３４には、数百〜数千もの命令ポインタのレコードが含まれてもよい。テーブル３３４は、テーブル３４１に上書きされている情報によって更新されうる。例えば、テーブル３４１の各レコードが一杯になると、新規レコードがテーブル３４１に記憶されるときに、最も古いキャッシュミス情報を含むレコードが削除される。しかし、削除の前に、上で説明したように、テーブル３４１の最も古いキャッシュミスレコードの情報が、テーブル３３３に情報を記憶するために使用されうる。テーブル３３４のエントリが定期的にクリアされうる点に留意されたい。例えば、テーブル３３４の行に対応するレコードを定期的に（例えば２０００サイクル毎など）クリアするために、図２の装置によって１つのポインタが使用されうる。
【００６９】
図１８は、本開示による方法を示す。ブロック７１１において、命令の実行の一環として情報がアクセスされる第１のメモリロケーションがキャッシュにおいて利用可能でない場合、第１のキャッシュミス標識が受信される。ブロック７１２において、第１のキャッシュミスにより、第１のキャッシュミスに基づく情報が、記憶位置の第１のレコードに記憶される。上で説明したように、この情報には、第１の命令のロケーションを特定する命令情報（命令ポインタなど）、およびブロック７１１において第１のキャッシュミスとなった命令によってアクセスされているメモリアドレスを特定するメモリ情報が含まれうる。ブロック７１２において、第１のキャッシュミスに基づく情報を格納しているレコードの例には、テーブル３３１〜３３４および３４１の各行が含まれる。例えば、アクセスされているメモリロケーションを特定するメモリ情報は、メモリロケーションのアドレス、あるいは、整列領域（アドレス整列領域または中央ブロック整列領域など）からのオフセットなどである。メモリ情報が整列領域からのオフセットである場合、オフセット情報により、プリフェッチする情報の個々のバイトまたは全データブロックを特定することができる。上で説明した実施形態では、整列領域に関連する複数のデータブロックの１つに対応する１つのビット位置がアサートされる。別の実施形態では、メモリ情報に、特定の命令のロケーションに関連するアドレス範囲を特定する複数の値が含まれてもよい。
【００７０】
ブロック７１３において、命令の実行の一環として情報がアクセスされる第２のメモリロケーションがキャッシュにおいて利用可能でない場合、第２のキャッシュミス標識が受信される。第２のメモリにアクセスしている命令は、ブロック７１１の第１の命令のこともあれば、別の命令のこともある。
【００７１】
ブロック７１４において、第２のキャッシュミスに基づいて情報が記憶される。一実施形態では、第２のキャッシュミスが、以前のキャッシュミスの整列領域内の関連するアドレスの結果発生した場合、その以前のキャッシュミスに関連するレコードが、追加のプリフェッチ情報を記憶することによって更新される。例えば、アドレス領域または中央ブロック整列領域内でキャッシュミスが発生すると、テーブル３３１〜３３４および３４１のエントリが、このように更新される。キャッシュミスが発生すると、テーブル３３２〜３３４が、テーブル３３１および３４１にある情報によって更新されることに注意されたい。別の実施形態では、例えば、テーブル３３１〜３３４のエントリに関して上で説明したように、第２のキャッシュミスが発生すると、情報が記憶されて新規レコードが作成されてもよい。
【００７２】
図１９は、本開示による方法のフロー図を示す。ブロック７３１において、キャッシュミスが受信される。ブロック７３２において、第１の命令のために第１のメモリ位置へのアクセスが行われると、キャッシュミスが発生するかどうかが判定される。キャッシュミスが発生する場合は、フローはブロック７３３に進み、第１の命令のメモリ位置に基づいてプリフェッチ情報がアクセスされる。ブロック７３４において、プリフェッチされた情報に基づいて情報のブロックが記憶される。例えば、キャッシュラインと同じサイズを有する情報のブロックが、キャッシュラインに記憶されうる。
【００７３】
上記の明細書では、本発明の原理を、特定の実施形態に関連して上に記載した。しかし、下記の特許請求の範囲に記載の本発明の範囲内から逸脱することなく、実施形態のいずれか１つ以上に対して、１つ以上の修正または１つ以上の他の変更を加えることができることを、当業者は認めるであろう。例えば、プリフェッチ情報が、プリフェッチする各情報ブロックに対する重み値を含んでもよいことが理解されよう。例えば、頻繁にキャッシュミスとなるデータを含むブロックには、他のデータブロックよりも大きな重みが与えられうる。更に、本開示を一般にキャッシュミスに関して記載したが、本開示は、複数のレベルのキャッシュミスに対応することができることが理解されよう。例えば、Ｌ２キャッシュミスに関してトレーニングが行われ、Ｌ１キャッシュミスに関してプリフェッチ情報の生成が行われてもよい。また、システム３００が、集積回路装置３０１に変換索引バッファ（translation look-aside buffer：ＴＬＢ）を備え、仮想メモリのアクセス時に、Ｌ２のＴＬＢの電力を低減させ、負荷を軽減してもよい点も理解されよう。記憶場所３３０のさまざまな構成も考えられる。例えば、１つまたは複数のリードライトポートを有する記憶位置を使用してもよい。例えば、一致ビット配列は、飽和カウンタであってもよい。
【００７４】
本開示の特定の実施形態によれば、第１の命令の実行中に、第１のメモリロケーションへのアクセスが行われると、キャッシュミス標識が受信される。キャッシュミス標識を受けて、第１の命令のロケーションに基づいてプリフェッチ情報がアクセスされる。特定の実施形態は、プリフェッチ情報に基づいて、プリフェッチされた第１のメモリのブロックを第１のキャッシュラインに、プリフェッチされた第２のメモリのブロックを第２のキャッシュラインに記憶するステップを更に有してもよい。プリフェッチ情報は、第１のブロックを表す第１のビット位置、および第２のブロックへのオフセットを表す第２のビット位置を有するエントリを含みうる。また、エントリは、第３のメモリブロックに対するオフセットを表す第３のビット位置を更に含んでもよく、第３のビット位置は、第１のビット位置と第２のビット位置の間にあり、プリフェッチ情報は、複数の連続するアドレス位置を表し、プリフェッチフィールドの各ビットは、連続するアドレスロケーションの一部分に対応するブロックを表し、第１のブロック、第２のブロックおよび第３のブロックは、複数の連続するアドレス位置の異なる部分に対応している。したがって、本明細書および図面は、限定としてではなく例示としてみなすべきであり、あらゆるこのような修正や他の変更のすべてが、発明の範囲内に含まれることが意図される。
【００７５】
１つ以上の利点、１つ以上の他の有利な点、１つ以上の問題に対する１つ以上の解決策、またはこれらの任意の組み合わせについて、１つ以上の特定の実施形態に関して記載した。しかし、利点、有利な点、問題に対する解決策、または想到されるかより明らかとなる何らかの利点、有利な点または解決策を生み出す任意の要素は、特許請求の範囲の重要、必要または本質的な特徴または要素であると解釈されるべきではない。
【図面の簡単な説明】
【００７６】
【図１】本開示の特定の実施形態による、命令によってアクセスされているアドレス位置に関連する各種のニーモニックを示す図。
【図２】本開示の特定の実施形態による装置を示す図。
【図３】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図４】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図５】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図６】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図７】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図８】図２のプリフェッチコントローラの一実施形態をより詳細に示す図。
【図９】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１０】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１１】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１２】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１３】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１４】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１５】本開示による、命令の実行によるプリフェッチ情報への影響を示す図。
【図１６】図２のプリフェッチコントローラの別の実施形態をより詳細に示す図。
【図１７】データを記憶するための特定の実施形態としてのテーブルを示す図。
【図１８】本開示による方法を表すフロー図。
【図１９】本開示による方法を表すフロー図。
【手続補正書】
【提出日】平成20年9月16日(2008.9.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１の命令の実行の一環として情報がアクセスされる第１のメモリロケーションがキャッシュにおいて利用可能でない場合、第１のキャッシュミス標識を受信するステップ（７１１）と、
前記第１のキャッシュミス標識を受信すると、第１のテーブルの第１のレコードに情報を記憶するステップ（７１２）であって、前記情報は、
前記第１の命令の位置を特定する命令情報（４１２，４２１）と、
前記第２のメモリロケーションを特定するメモリロケーション情報（４２２，４１１，４１３）とを有するステップと、
第２の命令の実行の一環として情報がアクセスされる第２のメモリロケーションがキャッシュにおいて利用可能でない場合、第２のキャッシュミス標識を受信するステップと、
前記第２のメモリロケーションが前記第１のエントリに記憶されている前記第１のメモリロケーションから定義された距離内にあると判定されると、前記第１のレコードに第１のプリフェッチ情報（４２１，４１４）を記憶するステップとを含み、
前記第１のプリフェッチ情報は、前記第２のメモリロケーションに基づくメモリ位置情報を含み、前記第１のプリフェッチ情報の記憶後は、前記第１のレコードは、前記第１のメモリロケーションを特定する前記メモリロケーション情報および前記第２のメモリロケーションを特定する前記メモリ情報を有する、方法。
【請求項２】
前記第１のプリフェッチ情報は前記第２のメモリアドレスを含むメモリ位置範囲を特定している請求項１記載の方法。
【請求項３】
前記第１のプリフェッチ情報は参照メモリ位置に対するオフセットを含む、請求項２記載の方法。
【請求項４】
前記第１のプリフェッチ情報は前記第２のメモリアドレスを含む、請求項１記載の方法。
【請求項５】
前記第２のキャッシュミス標識を受信すると、前記第１のテーブルの第２のレコードに情報を記憶するステップを更に有し、前記情報は、
前記第２の命令の位置を特定する命令情報（４１２，４２２）と、
前記第２のメモリ位置を特定するメモリ位置情報（４２２，４１１，４１３）とを有する請求項１に記載の方法。
【請求項６】
前記第２のメモリ位置が、前記第１のエントリに記憶されている前記第１のメモリ位置の定義された距離内にあることが判定されると、前記第１のレコードに記憶されている値（４２１，４１５）をインクリメントするステップを更に有する請求項１記載の方法。
【請求項７】
前記第１のテーブル（３３１）は、連想メモリであり、前記ＣＡＭの命令位置情報をアドレス指定するために内容が使用される請求項１記載の方法。
【請求項８】
前記第１の命令の前記位置で命令を実行すると、第２のキャッシュミス標識を受信するステップ（７１３）と、
前記第１のレコードが前記第１の命令の前記位置を特定する命令情報を含むことが判定されると、プリフェッチするメモリを決定するステップ（７３３）を更に含む、請求項１記載の方法。
【請求項９】
プリフェッチする前記メモリは複数の不連続なメモリ領域を含む請求項８に記載の方法。
【請求項１０】
前記第２のキャッシュミス標識を受信し、前記第１のレコードが前記第１の命令の前記位置を特定する命令情報を含むことを決定すると、前記第１のレコードに記憶されている値（９２３）をインクリメントするステップを更に含む、請求項８に記載の方法。
【国際調査報告】
2009540429.tif 000023
2009540429.tif 000024
2009540429.tif 000025