(57)【要約】プリフェッチングシステム（４００）は、シーケンシャルなプロセスにおいてデータをプリフェッチする（１３０）ために用いられるストライド値（４１２）の決定及び変更のヒステリシスを含む。いったんストライド値が決定されると、断続的なストライド非一貫性は無視され（３２２〜３３０）、ストライド値はその前の値を保持する。ストライド非一貫性が頻繁になる場合（３２２〜３３０）、ストライド値は変更される（２３０）。変更されたストライド値が繰り返すようになると、上記システムはこの値をストライドとして採用し、後続のストライド非一貫性は再び無視され、その後に保持されるストライド値は、非一貫性が頻繁になるまで、現在の値である。
2006510082.tif 000002
【特許請求の範囲】
【請求項１】
メモリからキャッシュへデータをプリフェッチする方法であって、
複数の等しいストライドのメモリアクセス及び前のストライド値に基づいて、前記等しいストライドのメモリアクセスの第１の程度を決定するステップと、
複数の等しくないストライドのメモリアクセス及び前記前のストライド値に基づいて、前記等しくないストライドのメモリアクセスの第２の程度を決定するステップと、
前記第１の程度に基づいて、前記メモリから前記データのプリフェッチをもたらすステップと、
前記第２の程度に基づいて、前記前のストライド値の変更をもたらすステップと、
を含む方法。
【請求項２】
前記第１の程度及び前記第２の程度を決定するステップが、各々の等しいストライドのメモリアクセスについてインクリメントされると共に、各々の等しくないストライドのメモリアクセスについてデクリメントされるカウントを維持することによって行われ、
前記プリフェッチをもたらすステップ及び前記変更をもたらすステップが、前記カウントに各々基づく、請求項１に記載の方法。
【請求項３】
前記プリフェッチをもたらすステップは、前記カウントが上限に等しいか又は該上限を上回る場合に行われ、前記変更をもたらすステップは、前記カウントが下限に等しいか又は該下限を下回る場合に行われる、請求項２に記載の方法。
【請求項４】
前記カウントは、最大で３に制限され、前記上限が２であり、前記下限が１である、請求項３に記載の方法。
【請求項５】
リクエストされたメモリアクセス間のストライド値の一貫性に対応する少なくとも一つの程度を含むように構成される制御レジスタと、
前記一貫性の程度に依存して、メモリからキャッシュへデータをプリフェッチするように構成されるプリフェッチコントローラと、
を有するプリフェッチシステムであって、
前記ストライド値の一貫性が、現在のストライド値と前のストライド値との比較に依存し、前記プリフェッチコントローラが、更に、非一貫性の程度に基づいて前記前のストライド値を変更するように構成され、前記非一貫性の程度が、リクエストされたメモリアクセス間の複数の等しくないストライドに基づく、プリフェッチシステム。
【請求項６】
前記一貫性の程度及び前記非一貫性の程度は、メモリアクセスをリクエストされた各々の等しいストライドに応じて最大カウントまでインクリメントされると共に、メモリアクセスをリクエストされた各々の等しくないストライドに応じて最小カウントまでデクリメントされるカウントに対応する、請求項５に記載のプリフェッチシステム。
【請求項７】
前記プリフェッチコントローラは、
前記カウントが上位スレッショルドレベルに等しいか又は該上位スレッショルドレベルを上回る場合、前記データをプリフェッチし、
前記カウントが下位スレッショルドレベルに等しいか又は該下位スレッショルドレベルを下回る場合、前記前のストライド値を変更するように構成される、請求項６に記載のプリフェッチシステム。
【請求項８】
前記最大カウントが３であり、前記上位スレッショルドレベルが２であり、前記下位スレッショルドレベルが１であり、前記最小カウントが０である、請求項７に記載のプリフェッチシステム。
【請求項９】
アクセスアドレスに基づいたデータにアクセスを供給するように構成されるメモリと、
前記メモリに動作可能に結合され、前記データへの高速アクセスを容易にするために、前記メモリからアクセスされるデータを記憶するように構成されるキャッシュと、
前記メモリ及び前記キャッシュに動作可能に結合され、前記データが前記キャッシュに記憶されている場合は前記キャッシュから前記データを受け取り、前記キャッシュに記憶されていない場合は前記メモリから前記データを受け取ると共に、前記アクセスアドレスを供給するように構成されるプロセッサと、
前記プロセッサ、前記メモリ及び前記キャッシュに動作可能に結合され、前記アクセスアドレス及び予測されたストライド値に基づいて、前記メモリから前記キャッシュへデータの転送をもたらすように構成されるフェッチコントローラと、
を有する処理システムであり、
前記フェッチコントローラが、更に、等しいストライド値の繰り返し発生に基づくストライド一貫性の程度と、等しくないストライド値の繰り返し発生に基づくストライド非一貫性の程度と、を維持するように構成され、
前記フェッチコントローラが、前記ストライド一貫性の程度に基づいて前記データの転送をもたらし、前記ストライド非一貫性の程度に基づいて前記予測されたストライド値の変更をもたらす処理システム。
【請求項１０】
前記ストライド一貫性の程度及び前記ストライド非一貫性の程度が、それぞれ、メモリアクセスをリクエストされた各々の等しいストライドに応じて最大カウントまでインクリメントされると共に、メモリアクセスをリクエストされた各々の等しくないストライドに応じて最小カウントまでデクリメントされるカウントに基づく、請求項９に記載の処理システム。
【請求項１１】
前記フェッチコントローラは、
前記カウントが、上位スレッショルドレベルに等しいか又は該上位スレッショルドレベルを上回る場合、前記データの転送をもたらし、
前記カウントが、下位スレッショルドレベルに等しいか又は該下位スレッショルドレベルを下回る場合、前記予測された前記ストライド値の変更をもたらすように構成される、請求項１０に記載の処理システム。
【請求項１２】
前記最大カウントが３であり、前記上位スレッショルドレベルが２であり、前記下位スレッショルドレベルが１であり、前記最小カウントが０である、請求項１１に記載の処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレクトロニクスの分野に関し、特に、あるプロセスにおける次のデータロケーションからのデータのプリフェッチを容易にするために、当該データロケーションを予測するための方法及びシステムに関する。
【背景技術】
【０００２】
プリフェッチング（prefetching、先取り）は、シーケンシャルプロセスにおける待ち時間（latency，レーテンシ）を最短化するための一般的な技法である。プロセスにおいて将来必要になると予期されるデータは、将来の後続アクセスのために、メモリから取り出され、キャッシュに記憶される。キャッシュは、メモリよりも実質的に一層高速なアクセスタイムを供給するように設計される。それゆえ、プロセスがデータを必要とする場合及びデータがキャッシュにある場合、このデータは、より高速なキャッシュアクセス速度でプロセスに供給される。逆に、データがキャッシュにない場合、このデータは、実質的に一層低速なメモリアクセスタイムまでプロセスに供給されず、それによってメモリアクセス遅延をプロセスにもたらす。
【０００３】
将来必要になるであろうデータの予測を容易にするために、種々の技法が一般に利用できる。このような技法の一つは「ストライド予測」である。この技法において、必要とされる次のデータ項目のロケーションは、前にアクセスされたデータ項目のロケーションのシーケンスに基づく。例えば、データは、従業員の名前、住所、社会保障番号（ＳＳＮ）等のレコードのようなデータレコードのリスト又は配列（array，アレイ）として記憶されることが多い。通常、これらのレコードは固定長のレコードであり、それにより、各レコードの開始（beginning，先頭）が、メモリの隣接するレコードからメモリロケーションの定数で区切られる。全従業員名の表示又はプリントアウトを供給するアプリケーションは、例えば、この定数で区切られるメモリロケーションにシーケンシャルにアクセスする。アプリケーションが、ロケーションＬにおいてメモリから第１の従業員名にアクセスし、ロケーションＬ＋Ｓにおいて第２の従業員名にアクセスすると仮定すると、アプリケーションは、次の従業員名を得るためにメモリのロケーションＬ＋Ｓ＋Ｓに位置するデータにアクセスするであろうと思われる。このアクセスがリクエストされる前に、ロケーションＬ＋Ｓ＋Ｓにおけるデータが、メモリから取り出され、より高速のキャッシュメモリに記憶される場合、第３の従業員名は、第１の従業員名又は第２の従業員名より一層迅速にアプリケーションに供給され得る。
【０００４】
図１は、従来技術のストライド予測プリフェッチプロセスの一実施例のフロー図を示す。１１０において、通常、アプリケーションが新たなデータ項目に対するアクセスのリクエストを呼び出す（invoke，起動する）のと同時に、プリフェッチプロセスが呼び出される。図示されていないが、このプリフェッチプロセスは、複数のプリフェッチングアルゴリズムを含むグロ―バルスキームの一部として呼ばれることができ、シーケンシャルデータアクセスのプロキシミティ等のようなファクタに依存して選択的に呼び出されることもできる。通常、プロセッサは、ここでアクセスのストライドと称される、シーケンシャルなアクセス間の間隔（interval，インターバル）を含むメモリに対して実行されたアクセスに関する情報を記録する、ストライド予測テーブル（ＳＰＴ）を維持する。このストライド予測テーブルは、通常、複数の起こり得るストライドの状況を常に把握するために実行されたアクセスに関する情報の複数のセットを記録するように構成される。便宜上及び理解を簡単にするために、本発明は、関連のメモリアクセス間の単一のストライドの状況を常に把握するために使用される単一のセットの情報のパラダイムを用いて本願明細書に示される。当業者であれば、ここに示される原則が、複数のストライドに関する複数のセットの情報を含むストライド予測テーブルの通常の使用に直接適用できることを認識するであろう。
【０００５】
１１０において、現在の（current，その時点の）ストライドは、前の／旧(prior/old)アクセスのアドレスと、１２０において新たにリクエストされたアクセスのアドレスとの間の差分によって決定される。次にリクエストされたアクセスが、前のアクセスと同様に均等にスペースを置かれるであろうという想定の下に、１３０において、現在の／新（current/new）アドレスから同じ間隔のアドレスにてフェッチする（fetch，取り出す）ように、プリフェッチが実行される。１４０において、次のデータアクセスに備えて、新アドレスが旧アドレスに取って代わり、１５０において、このプリフェッチルーチンは終了する。新たなデータに対してリクエストされたアクセスの時点で、次に起こり得るデータのためのプリフェッチを開始する（initiate，起動する）ことによって、このプリフェッチされたデータは、アプリケーションがこのデータのためのアクセスリクエストを開始する場合及び開始するとき、より高速のキャッシュに存在するであろう。次に起こり得るデータが、その後リクエストされるデータでない場合、キャッシュは次のリクエストされたデータを含まず、メモリアクセスが要求されるであろう。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、図１のプリフェッチプロセスは、次に起こり得るリクエストされたデータが、前にリクエストされたデータから均等にスペースを置かれているであろうという想定の何らかの根拠があるか否かに関係なく、新たなデータに対するアクセスごとにプリフェッチを開始する。これにより、かなりのメモリアクセストラフィックを生じ、これは、有効メモリアクセスを大幅に低減するように作用し得る。図２は、改善された従来技術のストライド予測プリフェッチプロセスの一実施例のフロー図であり、ここでは、２つの連続したアクセスが同じストライドを示す場合に限り、プリフェッチが開始される。この実施形態では、２２０において、新たなアクセスリクエストについて決定されたストライドが、前に決定されたストライドと比較される。新ストライドが旧ストライドに等しい場合、次のストライドがこれらの２つのストライドにも等しいであろうという見込み（likelihood）は、１３０でのプリフェッチを正当化するのに十分に高い。新ストライドが旧ストライドと異なる場合、次のサイクルに備えて、２３０において、新ストライドは旧ストライドに取って代わる。当業者であれば、プリフェッチを開始するためのこの２つ連続（two-in-a-row） の基準は、過剰のメモリアクセストラフィックと、キャッシュにおける次にリクエストされるデータをもつ見込みとの兼ね合い（tradeoff，トレードオフ）のために、３つ連続、４つ連続などの基準に拡張され得ることが分かるであろう。
【０００７】
本発明の目的は、アプリケーションによってその後アクセスされるであろうデータをプリフェッチする見込みを改善することにある。本発明の他の目的は、ハードウェアインプリメンテーションに十分に適している効率的なプリフェッチスキームを提供することにある。
【課題を解決するための手段】
【０００８】
これらの目的及びその他の目的は、シーケンシャルプロセスにおいてデータをプリフェッチするために用いられるストライド値の決定及び変更におけるヒステリシス（hysteresis，履歴）を含むプリフェッチングシステムによって達成される。いったんストライド値が決定されると、断続的なストライド非一貫性（inconsistencies，不一致）は無視され、ストライド値は該ストライドの前の値を保持する。このストライド非一貫性が頻繁になると、ストライド値は変更される。変更されたストライド値が繰り返すように（repetitive，反復的に）なると、システムはこの値をストライドとして採用し、後続のストライド非一貫性は再び無視され、その後に保持されるストライド値は、非一貫性が頻繁になるまで、現在の値である。
【０００９】
全図面を通して、同一の参照符号は同様の又は対応する特徴又は機能を示す。
【発明を実施するための最良の形態】
【００１０】
本発明は、メモリアクセスにおける規則的なストライドパターンが、ストライドパターンに従わない断続的なデータアクセスを含むことが多いという観察を前提とする。例えば、ネストループ構造は、データのリストを循環する内側ループと、この内側ループの各サイクルに用いられる一つ又は複数の変数を予め設定（preset，プリセット）する外側ループ又は内側ループの各サイクルから得られる結果を記憶する外側ループと、を含み得る。この実施例では、データのリストを循環している内側ループは、一定のストライドを示す可能性がある。但し、内側ループを再開するたびに、 メモリアクセスがリストの先頭（start）であるのに対して、前のアクセスはリストの終わり(end)であった。但し、リストの終わりとリストの先頭との間のスパン（span，間隔）は、内側ループのストライドに対応しないであろう。更に、ループの始まり又は終わりでの外側ループによるデータアクセスは、内側ループのストライドに対応しないアクセス間のスパンを生み出すであろう。ストライドにおける断続的な中断（break，ブレーク）の他の実施例は、多次元配列に編成される（organize，系統立てられる）データの処理を含む。通常、データは、ある次元に沿って所与の範囲について処理され、その後、他の次元へのインデックスがインクリメント（increment，増加）され、この次にインデックス付けされた他の次元のデータが、最初の次元に沿って所与の範囲について処理される。最初の次元の範囲に沿ったストライドは、一般に一定であるが、次の次元に対するインデックスのインクリメントは、最初の次元に沿ったストライドに合致しない前のアクセスからのスパンをもつアクセスを結果として生じる可能性がある。
通常のストライド予測プロセスでは、ストライドが「中断される」、即ち、割り込みをかけられる（interrupt，インタラプトされる）たびに、ストライドを決定するプロセスが、新たなストライドを決定するために繰り返される。新たなストライドが決定されている間、プリフェッチは行われない。アプリケーションは、内側ループの各々の再始動（re-start，リスタート）時のメモリアクセスによって遅延されるか、又は多次元配列の処理時のより高いレベルのインデックスをそれぞれインクリメントすることによって遅延される。
【００１１】
本発明によれば、ストライド値は、ストライドにおいて断続的な中断が生じる時に保存される。現在のストライドでデータのプリフェッチを実施することは、メモリアクセスの所与の回数の範囲内における等しい値のストライドの回数に依存する。プリフェッチ値を調整することは、複数の等しくない値のストライドの発生（occurrence，オカレンス）に依存する。簡単な実施例において、データのプリフェッチは、３回のアクセスのうち２回が連続した等しいストライドをもつたびに実施されることができ、ストライド値の変更は、２回のアクセスが連続した等しくないストライドをもつたびに実施されることができる。
【００１２】
図３は、本発明によるストライド予測プリフェッチプロセスの一実施例のフロー図を示す。この実施例では、「カウント」パラメータが、選択された最大限まで、同じ値の連続したストライドの数をカウントするために用いられる。本発明の好ましい実施形態では、このカウントパラメータは、ストライドにおける断続的な中断と、ストライドの実際の持続的な変化とを区別するためにも用いられる。当業者であれば、この開示を考慮して、独立パラメータが、連続した等しくないストライドの数をカウントするために利用され得ることは明らかであろう。
【００１３】
１２０において、新たなアクセスアドレスと前のアクセスアドレスとの間で現在のストライドを決定した後に、本発明のプロセスは、２２０において、現在のストライドと前のストライドとを比較する。現在のストライドが前のストライドに等しい場合、３２６において、カウントはインクリメントされる;等しくない場合、３２２において、現在のカウントはデクリメント（decrement，減少）される。好ましい実施形態では、このカウントが、ゼロから最大カウントまでの値に制限される。ブロック３２４及び３２８は、上記の制限の範囲内にとどまるように、ブロック３２２及びブロック３２６からインクリメントされたカウント又はデクリメントされたカウントをそれぞれクリップする。
【００１４】
３３０において、カウントは、上限（ＵＬ）と比較されると共に、下限（ＬＬ）とも比較され、ここで、下限ＬＬは、好ましくは、上限ＵＬより小さい。この実施例では、上限ＵＬは、次のストライド予測されるアクセスロケーションからのプリフェッチを正当化するのに必要とされる等しいストライド発生の数に対応する。カウントが、この上限ＵＬに等しい場合又はこの上限ＵＬを上回る場合、１３０において、現在のアドレスに現在のストライドをプラスしたものに対応するアドレスからデータのプリフェッチが実行される。例えば、上限ＵＬが２の値である場合、同じストライド値の２つ連続が起こらない限り、当初、プリフェッチは実行されない。上限が３の値である場合、同じストライド値の３つ連続が起こるまで、プリフェッチは実行されず、その他の場合も同様である。その後、３２６、３２８経由で、後続の等しい値をもつストライドが、最大限までカウントをインクリメントし続ける。好ましい実施形態において、最大値は、現在のストライド値が「信頼できる」との結論を下すのに必要とされる連続した等しい値のストライドの数として選択される。
【００１５】
等しくないストライドが起こるたびに、３２２において、カウントはデクリメントされる。このように、最大のカウントと現在のカウントとの間の差分は、現在のストライド値の「非信頼性」の程度（a measure）に対応する。下限は、２３０において、現在のストライド値に対する変更を正当化するのに十分な程度の非信頼性を構成する現在のカウントの値として選択される。一般に、図３に示されるように、２３０において、現在のストライド値が信頼できないと考えられる場合、１３０において、プリフェッチは実施されない。同様に、１３０において、現在のストライド値が、プリフェッチの正当な根拠となるのに十分信頼できる場合、２３０にて現在のストライド値の変更は実施されない。このように、下限ＬＬは、上限ＵＬより小さくなるように設定され、一般にＵＬ−１であるように設定される。オプションとして、テストブロック３３０とブロック１４０との間の破線接続によって示されるとおり、下限ＬＬは、１３０(count＜UL)にて、現在のストライドの判断（assess，査定）された信頼性がプリフェッチを正当化するのに十分でなく、２３０(count＞LL)にて、判断された非信頼性が現在のストライドの変更を正当化するのに十分でないように、上限ＵＬに関して選択され得る。
【００１６】
図４は、本発明によるストライド予測プリフェッチシステム４００の一実施例のブロック図を示す。フェッチコントローラ４３０は、制御レジスタ４１０のコンテンツ及びプロセッサ４２０からのデータアクセスリクエストに基づいて、メモリ４５０からキャッシュ４６０へのデータのプリフェッチをもたらす。リクエストされたデータのアドレスは、上記に説明されたとおり、アプリケーションが、メモリアクセス間に一貫したストライド又はロケーションのスパンを示す、繰り返し方式（repetitive manner）において、データをリクエストしているか否かを決定するために用いられる。制御レジスタ４１０は、前のデータアクセスのアドレス４１６、前のストライド４１２及びカウンタ４１４を含む。上記されたように、２つのカウンタが、等しいストライドアクセス及び等しくないストライドアクセスの独立カウントを維持するために、単一のカウンタ４１４の代わりに使われることもできる。プロセッサ４２０から現在リクエストされるデータのアドレスは、現在のストライドを決定するために前のアドレス４１６と比較される。現在のストライドが前のストライド４１２に対応する場合、カウンタ４１４はインクリメントされる；対応しない場合、カウンタ４１４はデクリメントされる。カウンタ４１４のインクリメントされた値又はデクリメントされた値に依存して、フェッチコントローラは、メモリ４５０における次に予測されるロケーションからキャッシュ４６０へのデータのプリフェッチを開始するか否かを決定する。後続のデータリクエストが、キャッシュ４６０にプリフェッチされているデータのために行われる場合、キャッシュ４６０は、データを直接プロセッサに供給し、その結果、メモリ４５０からデータを取り出すことによりもたらされる遅延を回避する。
【００１７】
更に、カウンタ４１４のインクリメントされた値又はデクリメントされた値に依存して、上記に詳述されたように、フェッチコントローラ４３０は、ストライド値４１２を変更するか否かを決定する。通常のシステムにおけるように一つの等しくないストライド発生に基づいてストライド値を変更するのではなく、等しくないストライドの数に依存するカウントに基づいてストライド値４１２を変更するか否かを決定することによって、ストライド予測プリフェッチシステム４００は、ストライドにおける断続的な中断に対して感度を下げられる（de-sensitize）。
【００１８】
前述の説明は、単に本発明の原理を示すのに過ぎない。従って、当業者であれば、ここに明確に説明されない又は図示されないけれども、本発明の原理を具現化し、それゆえ、添付の請求項の範囲及び精神の範囲内にある種々の装置を考案することが可能であることが理解されるであろう。
【図面の簡単な説明】
【００１９】
【図１】従来技術のストライド予測プリフェッチプロセスの一実施例のフロー図である。
【図２】代替の従来技術のストライド予測プリフェッチプロセスの一実施例のフロー図である。
【図３】本発明によるストライド予測プリフェッチプロセスの一実施例のフロー図である。
【図４】本発明によるストライド予測プリフェッチシステムの一実施例のブロック図である。
【図１】
2006510082.tif 000003
【図２】
2006510082.tif 000004
【図３】
2006510082.tif 000005
【図４】
2006510082.tif 000006
【国際調査報告】
2006510082.tif 000007
2006510082.tif 000008
2006510082.tif 000009