(57)【要約】ある実施形態では、本発明は、メモリ中のデータ・アクセス・ストライドがあるレンジにはいるときを検出し、予測される次のストライドを計算し、前記予測される次のストライドを使ってキャッシュ・ラインを選択的にプリフェッチするとともに、プリフェッチを動的に制御するプリフェッチ・エンジンを含む。他の実施形態も記載され、特許請求される。
2013539117.tif 000002
【特許請求の範囲】
【請求項１】
アクセスする機械によって実行されたときに該アクセスする機械に：
メモリ中のデータ・アクセス・ストライドがあるレンジにはいるときを検出し；
予測される次のストライドを計算し；
前記予測される次のストライドを使ってキャッシュ・ラインを選択的にプリフェッチすることを実行させるコンテンツを含む、
記憶媒体。
【請求項２】
アクセスする機械によって実行されたときに該アクセスする機械に、前記レンジ内にはいるデータ・アクセス・ストライドを追跡するようクレジット・ベースのシステムを維持させるコンテンツをさらに含む、請求項１記載の記憶媒体。
【請求項３】
前記クレジット・ベースのシステムが、データ・アクセスが前記レンジ内にはいる場合にカウントを増加させ、データ・アクセス・ストライドが前記レンジ外である場合に前記カウントを減少させることを含む、請求項２記載の記憶媒体。
【請求項４】
キャッシュ・ラインを選択的にプリフェッチするためのコンテンツが、前記カウントが閾値に達するときにキャッシュ・ラインをプリフェッチするためのコンテンツを含む、請求項３記載の記憶媒体。
【請求項５】
アクセスする機械によって実行されたときに該アクセスする機械に、第二の隣接するキャッシュ・ラインをプリフェッチさせるコンテンツをさらに含む、請求項４記載の記憶媒体。
【請求項６】
予測される次のストライドを計算するためのコンテンツが、最近の前のアクセスのストライドを平均するためのコンテンツを含む、請求項４記載の記憶媒体。
【請求項７】
アクセスする機械によって実行されたときに該アクセスする機械に：前記レンジ、前記閾値、キャッシュ・ラインをプリフェッチするかどうかおよび第二のキャッシュ・ラインをプリフェッチするかどうかからなる群から選択される一つまたは複数の変数を変更させるコンテンツをさらに含む、請求項４記載の記憶媒体。
【請求項８】
アクセスする機械によって実行されたときに該アクセスする機械に、適応的な外部制御を提供させるコンテンツをさらに含む、請求項７記載の記憶媒体。
【請求項９】
命令を実行するための第一のコアおよび複数のエントリーを記憶するキャッシュを含むプロセッサと；
前記プロセッサに結合された動的ランダム・アクセス・メモリ（DRAM）と；
メモリ中のデータ・アクセス・ストライドがあるレンジにはいるときを検出し、予測される次のストライドを計算し、前記予測される次のストライドを使ってキャッシュ・ラインを選択的にプリフェッチするファジー・ストライド・プリフェッチ・ハンドラとを有する、
システム。
【請求項１０】
前記ファジー・ストライド・プリフェッチ・ハンドラが、前記レンジ内にはいるデータ・アクセス・ストライドを追跡するようクレジット・ベースのシステムを維持することをさらに含む、請求項９記載のシステム。
【請求項１１】
前記クレジット・ベースのシステムが、データ・アクセスが前記レンジ内にはいる場合にカウントを増加させ、データ・アクセス・ストライドが前記レンジ外である場合に前記カウントを減少させることを含む、請求項１０記載のシステム。
【請求項１２】
前記ファジー・ストライド・プリフェッチ・ハンドラがキャッシュ・ラインを選択的にプリフェッチすることが、前記ファジー・ストライド・プリフェッチ・ハンドラが前記カウントが閾値に達するときにキャッシュ・ラインをプリフェッチすることを含む、請求項１１記載のシステム。
【請求項１３】
前記ファジー・ストライド・プリフェッチ・ハンドラが第二の隣接するキャッシュ・ラインをプリフェッチすることをさらに含む、請求項１２記載のシステム。
【請求項１４】
前記ファジー・ストライド・プリフェッチ・ハンドラが予測される次のストライドを計算することが、前記ファジー・ストライド・プリフェッチ・ハンドラが最近の前のアクセスのストライドを平均することを含む、請求項１２記載のシステム。
【請求項１５】
メモリ中のデータ・アクセス・ストライドがあるレンジにはいるときを検出し；
予測される次のストライドを計算し；
前記予測される次のストライドを使ってキャッシュ・ラインを選択的にプリフェッチすることを含む、
方法。
【請求項１６】
前記レンジ内にはいるデータ・アクセス・ストライドを追跡するようクレジット・ベースのシステムを維持することをさらに含む、請求項１５記載の方法。
【請求項１７】
前記クレジット・ベースのシステムが、データ・アクセスが前記レンジ内にはいる場合にカウントを増加させ、データ・アクセス・ストライドが前記レンジ外である場合に前記カウントを減少させることを含む、請求項１６記載の方法。
【請求項１８】
キャッシュ・ラインを選択的にプリフェッチすることが、前記カウントが閾値に達するときにキャッシュ・ラインをプリフェッチすることを含む、請求項１７記載の方法。
【請求項１９】
第二の隣接するキャッシュ・ラインをプリフェッチすることをさらに含む、請求項１８記載の方法。
【請求項２０】
前記レンジ、前記閾値、キャッシュ・ラインをプリフェッチするかどうかおよび第二のキャッシュ・ラインをプリフェッチするかどうか、からなる群から選択される一つまたは複数の変数を変更することをさらに含む、請求項１８記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願はプリフェッチのための方法および装置に関する。
【背景技術】
【０００２】
現代のプロセッサでは、メモリからのプリフェッチにより将来必要とされることがありうるデータおよび命令がキャッシュにロードされることができる。このようにして、そのようなプリフェッチがなかったとした場合にキャッシュ・ミスになったはずの場合、のちの転送に付随する追加的なオーバーヘッドを回避することが可能となることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、必要とされないキャッシュ・ラインのプリフェッチはメモリ帯域幅を浪費し、キャッシュを汚染するきらいがある。
【課題を解決するための手段】
【０００４】
本願の課題は請求項記載の手段によって解決される。
【図面の簡単な説明】
【０００５】
【図１】本発明のある実施形態に基づくファジー・ストライド・プリフェッチのための例示的な装置のブロック図である。
【図２】本発明のある実施形態に基づく例示的なファジー・ストライド・プリフェッチ・エンジンのブロック図である。
【図３】本発明のある実施形態に基づくファジー・ストライドの検出およびそれに対する応答のフローチャートである。
【図４】本発明のある実施形態に基づくストライドを予測するためのフローチャートである。
【図５】本発明のある実施形態に基づくシステムのブロック図である。
【発明を実施するための形態】
【０００６】
以下では、説明の目的上、本発明の十全な理解を提供するために数多くの個別的な詳細が記載される。しかしながら、当業者には、本発明の実施形態がこうした個別的詳細なしでも実施できることは明白であろう。一方、本発明を埋没させるのを避けるため、構造および装置はブロック図の形で示される。
【０００７】
本明細書を通じて「一つの実施形態」または「ある実施形態」への言及は、その実施形態に関連して記述される特定の特徴、構造または特性が本発明の少なくとも一つの実施形態に含まれることを意味している。よって、本明細書を通じて随所に「一つの実施形態では」または「ある実施形態では」という句が現れるのは、必ずしもみなが同じ実施形態に言及しているわけではない。さらに、それら特定の特徴、構造または特性は一つまたは複数の実施形態においていかなる好適な仕方で組み合わされてもよい。
【０００８】
ここで図１を参照するに、本発明のある実施形態に基づくファジー・ストライド・プリフェッチのための例示的な装置のブロック図が示されている。図１に示されるように、装置１００は、プロセッサ１０２と、動的ランダム・アクセス・メモリ（DRAM）のようなメモリ１０４とを含んでいてもよい。プロセッサ１０２はコア１０６〜１１０、キャッシュ１１２およびファジー・ストライド・プリフェッチ・エンジン１１６を含んでいてもよい。コア１０６〜１１０は、互いから独立に命令を実行することができてもよく、いかなる型のアーキテクチャを含んでいてもよい。三つのコアを含むものとして図示されているが、プロセッサ１０２は任意の数のコアを有していてよく、図示しない他のコンポーネントまたはコントローラを含んでいてもよい。ある実施形態では、プロセッサ１０２はシステム・オン・チップ（SOC:  system  on  a  chip）である。
【０００９】
キャッシュ１１２は、任意の数の別個のキャッシュを含んでいてよく、任意の数のエントリーを含んでいてよい。低レイテンシーのレベル１キャッシュとして意図されているものの、キャッシュ１１２は任意の階層レベルにおける任意のメモリ技術において実装されてもよい。ある実施形態では、キャッシュ１１２は、メモリ１０４の諸領域、たとえば領域１１８からフェッチまたはプリフェッチされたいくつかのキャッシュ・ライン、たとえばライン１１４を記憶する。しかしながら、本発明は、キャッシュまたはメモリの他のさまざまなレベル間のプリフェッチによって実施されてもよい。
【００１０】
ファジー・ストライド・プリフェッチ・エンジン１１６は、たとえば図３および図４を参照して述べるようなファジー・ストライド・プリフェッチのための方法を実装してもよく、図２を参照して述べるようなアーキテクチャを有していてもよい。ファジー・ストライド・プリフェッチ・エンジン１１６はプロセッサ１０２とは別個であってもよく、ハードウェア、ソフトウェアまたはハードウェアおよびソフトウェアの組み合わせにおいて実装されてもよい。
【００１１】
本稿での用法では、ストライド１２４はメモリ・アドレス間の距離を指す。いくつかの実施形態では、ストライド１２４は、プロセッサ１０２によって要求される相続くメモリ読み出しのアドレス間の現在のストライドまたは距離を指す。他の実施形態では、ストライド１２４は、どのメモリ・アドレスが次に要求されるか、どのメモリ・アドレスをプリフェッチするのが有利でありうるかについての予測されるストライドまたは推測を指す。これについてはのちにより詳細に述べる。
【００１２】
ここで図２を参照すると、本発明のある実施形態に基づく例示的なファジー・ストライド・プリフェッチ・エンジンのブロック図が示されている。図２に示されるように、ファジー・ストライド・プリフェッチ・エンジン１１６は、プリフェッチ・サービス２０２、レンジ２０４、カウント２０６、閾値２０８および予測されたストライド２１０を含んでいてもよい。プリフェッチ・サービス２０２は、検出サービス２１２、予測サービス２１４、プリフェッチ・サービス２１６および制御サービス２１８を含んでいてもよく、これらはそれぞれ、メモリ内のデータ・アクセス・ストライドがあるレンジ内にはいるときを検出し、予測される次のストライドを計算し、予測された次のストライドを使って一つまたは複数のキャッシュ・ラインを選択的にプリフェッチし、外部モジュールによって適応制御を提供してもよい。
【００１３】
検出サービス２１２は、メモリ内のデータ・アクセス・ストライド（たとえばメモリ１０４内のストライド１２４）がレンジ２０４内にはいるときを検出してもよい。本稿での用法では、ファジー・ストライドは、大半が狭いレンジ２０４内にはいる、一定でないアドレス・ストライド１２４のストリーム（たとえば、プロセッサ１０２によるメモリ読み出しのストリーム）を指す。（たとえば、レンジ２０４は前のデータ・アクセスから128バイトないし192バイト、すなわち二または三キャッシュ・ライン離れている。）いくつかのアプリケーションは、ファジー・ストライド・プリフェッチから裨益するデータ・アクセス・パターンをもつことがあるが、他のアプリケーションはそうではないこともある。本発明は、他のプリフェッチ技法との関連で実施されてもよい。ある実施形態では、検出サービス２１２は、一連のアドレス・ストライド１２４がレンジ２０４にはいるかどうかを追跡するためにクレジット・ベースのシステムを使う。ある実施形態では、検出サービス２１２は、データ・アクセス・ストライド１２４がレンジ２０４にはいるときにカウント２０６を増加させ、データ・アクセス・ストライド１２４がレンジ２０４外になるときにカウント２０６を減少させる。
【００１４】
予測サービス２１４は、予測されるストライド２１０を計算してもよい。ある実施形態では、予測サービス２１４は最近の前のアクセスのファジー・ストライドを平均する（たとえば、予測されるストライド＝前の５個のストライドの和／５）。もう一つの実施形態では、予測サービス２１４は、予測されるストライド２１０の計算において、現在のファジー・ストライドに他よりも大きな重みをかけてもよい（たとえば、予測されるストライド＝(予測されるストライド＋現在のストライド)／２）。予測されるストライド２１０を計算するための他の方法を当業者が思いつくことがあり、本発明の範囲内であると考えられる。
【００１５】
プリフェッチ・サービス２１６は、予測されたストライド２１０を使って一つまたは複数のキャッシュ・ラインを選択的にプリフェッチしてもよい。ある実施形態では、プリフェッチ・サービス２１６は、カウント２０６が閾値２０８を満たすまたは閾値２０８を超え、それによりファジー・ストライド・プリフェッチが有益である可能性がより高いことが示される場合にのみ、予測されたストライド２１０によって（たとえば予測されたストライド２１０をアクセスされた以前のメモリ・アドレスに加えることによって）同定されるキャッシュ・ラインをプリフェッチすることになる。ある実施形態では、プリフェッチ・サービス２１４は、予測されたストライド２１０によって示されるメモリ・アドレスがメモリ領域１２０の境界に十分近い場合にも第二のキャッシュ・ライン内に隣接したメモリ領域１２２をプリフェッチしてもよい。
【００１６】
制御サービス２１８は、他のソフトウェアまたはハードウェアまたはハードウェアおよびソフトウェアの組み合わせのような外部モジュールによって適応制御を提供してもよい。ある実施形態では、制御サービス２１８は、作動時に、レンジ２０４、カウント２０６および閾値２０８を、メモリに記憶されている値をもって初期化する。ある実施形態では、レンジ、閾値、キャッシュ・ラインをプリフェッチするかどうかおよび第二のキャッシュ・ラインをプリフェッチするかどうかは、ファジー・ストライド・プリフェッチの有効性をモニタリングする外部の最適化モジュール（図示せず）によって制御されてもよい。もう一つの実施形態では、制御サービス２１８は、レンジ２０４および閾値２０８のような変数を初期化、更新および／または修正する自らのデータ・アクセス・パターンについて自ら認識する（self-aware）ソフトウェア・アプリケーションが、たとえばファジー・ストライド・プリフェッチを適宜するまたはしないことを推奨することを許容してもよい。
【００１７】
ここで図３を参照すると、本発明のある実施形態に基づく、ファジー・ストライドを検出し、これに応答するためのフローチャートが示されている。図３に示されるように、本方法は、検出サービス２１２がデータ・アクセス・アドレスを受け取る（３０２）ことをもって始まる。ある実施形態では、検出サービス２１２はメモリ読み出しのたびに呼び出される。別の実施形態では、検出サービス２１２はキャッシュ・ミスのたびに呼び出される。次に、検出サービス２１２は前のデータ・アクセスからの差を取ることによってデータ・アクセスのストライド１２４を決定する（３０４）。
【００１８】
検出サービス２１２は次いで、ストライド１２４をレンジ２０４と比較して、ストライド１２４がファジー・ストライドと考えられるかどうかを判定する（３０６）。もしそうであれば、カウント２０６が増加させられる（３０８）。もしそうでなければ、カウント２０６は減少させられる（３１０）。
【００１９】
プリフェッチ・サービス２１６は次いでカウント２０６を閾値２１０と比較して、プリフェッチをトリガーするかどうかを決定する（３１２）。カウント２０６が閾値２１０を満たしていたら、プリフェッチ・サービス２１６は予測されたストライド２１０に基づいて一つまたは複数のキャッシュ・ラインをプリフェッチする（３１４）。
【００２０】
ここで図４を参照すると、本発明のある実施形態に基づくストライドを予測するためのフローチャートが示されている。図４に示されるように、本発明は、予測サービス２１４が現在のファジー・ストライド値を検出サービス２１２から受け取る（４０２）ことをもって始まる。次に、予測サービス２１４は更新された予測されたストライド２１０を計算する（４０４）。プリフェッチがトリガーされたとき、プリフェッチ・サービス２１６は予測されたストライド２１０を使ってどのキャッシュ・ライン（単数または複数）をプリフェッチすべきかを決定する（４０６）。
【００２１】
実施形態は、多くの異なるシステム型で実装されうる。ここで図５を参照するに、本発明のある実施形態に基づくシステムのブロック図が示されている。図５に示されるように、マルチプロセッサ・システム５００はポイント・ツー・ポイント相互接続システムであり、ポイント・ツー・ポイント相互接続５５０を介して結合された第一のプロセッサ５７０および第二のプロセッサ５８０を含む。図５に示されるように、プロセッサ５７０および５８０のそれぞれは、第一および第二のプロセッサ・コア（すなわちプロセッサ・コア５７４ａおよび５７４ｂならびにプロセッサ・コア５８４ａおよび５８４ｂ）を含むマルチコア・プロセッサであってもよい。各プロセッサは、本発明に基づくファジー・ストライド・プリフェッチ・ハードウェア、ソフトウェアおよびファームウェアを含んでいてもよい。
【００２２】
引き続き図５を参照するに、第一のプロセッサ５７０はさらに、メモリ・コントローラ・ハブ（MCH:  memory  controller  hub）５７２およびポイント・ツー・ポイントの（P-P）インターフェース５７６および５７８を含む。同様に、第二のプロセッサ５８０はMCH  ５８２およびP-Pインターフェース５８６および５８８を含む。図５に示されるように、MCH  ５７２および５８２はプロセッサをそれぞれのメモリ、すなわちメモリ５３２およびメモリ５３４に結合させる。これらのメモリはそれぞれのプロセッサにローカルに取り付けられたメイン・メモリ（たとえば動的ランダム・アクセス・メモリ（DRAM））の部分であってもよく、そのそれぞれは、本発明の実施形態に基づく拡張されたページ・テーブルを含んでいてもよい。第一のプロセッサ５７０および第二のプロセッサ５８０は、それぞれP-P相互接続５５２および５５４を介してチップセット５９０に結合されうる。図５に示されるように、チップセット５９０はP-Pインターフェース５９４および５９８を含む。
【００２３】
さらに、チップセット５９０は、チップセット５９０を高性能グラフィック・エンジン５３８と結合するインターフェース５９２を含む。チップセット５９０は、インターフェース５９６を介して第一のバス５１６に結合されうる。図５に示されるように、さまざまなI/O装置５１４が、第一のバス５１６を第二のバス５２０に結合するバス・ブリッジ５１８とともに、第一のバス５１６に結合されうる。第二のバス５２０にはさまざまな装置が結合されうる。ある実施形態では、それにはたとえば、キーボード／マウス５２２、通信装置５２６およびコード５３０を含みうるディスク・ドライブまたは他の大容量記憶装置といったデータ記憶ユニット５２８が含まれる。さらに、オーディオI/O  ５２４が第二のバス５２０に結合されていてもよい。
【００２４】
実施形態は、コードにおいて実装されてもよく、記憶媒体上に記憶されてもよい。記憶媒体がその上に記憶された命令を有し、該命令が、該命令を実行するようシステムをプログラムするために使用される。記憶媒体は、これに限られないが、フロッピー（登録商標）ディスク、光ディスク、コンパクト・ディスク読み出し専用メモリ（CD-ROM）、書き換え可能型コンパクト・ディスク（CD-RW）および光磁気ディスクを含む任意の型のディスク、読み出し専用メモリ（ROM）、動的ランダム・アクセス・メモリ（DRAM）、静的ランダム・アクセス・メモリ（SRAM）といったランダム・アクセス・メモリ（RAM）、消去可能なプログラム可能型読み出し専用メモリ（EPROM）、フラッシュメモリ、半導体ドライブ（SSD:  solid  state  drive）、電気的に消去可能なプログラム可能型読み出し専用メモリ（EEPROM）といった半導体デバイス、磁気カードもしくは光カードまたは電子的な命令を記憶するために好適な他の任意の型の媒体を含みうる。
【００２５】
本発明について、限られた数の実施形態に関して記載してきたが、当業者はそうした実施形態からの数多くの修正および変形を認識するであろう。付属の請求項は本発明の真の精神および範囲にはいるそのようなすべての修正および変形をカバーすることが意図されている。
【図１】
2013539117.tif 000003
【図２】
2013539117.tif 000004
【図３】
2013539117.tif 000005
【図４】
2013539117.tif 000006
【図５】
2013539117.tif 000007
【国際調査報告】
2013539117.tif 000008
2013539117.tif 000009