(57)【要約】コードの領域内でメモリ動作についてプリフェッチを行う実行可能コードにソースコードをコンパイルするシステムを提供する。システムは、ソースコードモジュールを、実行可能コードモジュールにコンパイルすることによって動作する。システムは、実行可能コードモジュール内の関数内のキャッシュミスレートに関する統計を取り、ホット関数のセットを識別する。プリフェッチ動作は、関数の開始でプリフェッチ生成をアクティブにし、関数からのリターンでプリフェッチ生成をイナクティブにすることによって、実行可能コードにスケジューリングされる。システムは、メモリ動作のサブセットを識別し、サブセットに属するメモリ動作の明示的なプリフェッチ動作をスケジューリングすることによってメモリ動作についてのプリフェッチ動作をさらにスケジューリングする。【選択図】図５
2004501410.tif 000002
【特許請求の範囲】
【請求項１】
ソースコードを、キャシュミスを生成する傾向のあるコードの領域内でメモリ動作についてプリフェッチを行う実行可能コードにコンパイルする方法であって、
プログラミング言語命令を含むソースコードモジュールを、プロセッサによって実行されることに適した命令を含む実行可能コードモジュールにコンパイルする工程と、
多くのキャッシュミスを生成する傾向のあるメモリ動作を含む関数を識別する工程であって、
代表的なワークロードのトレーニングモードで該プロセッサの実行可能コードモジュールを実行する工程と、
該実行可能コードモジュール内の関数内のメモリ動作についてキャッシュミスレートに関する統計を取る工程と、
多くのキャッシュミスを生成する関数のセットを識別する工程と
によって、多くのキャッシュミスを生成する傾向のあるメモリ動作を含む関数を識別する工程と、
明示的なプリフェッチ命令を、該識別された関数のセット内でのメモリ動作に先立って、該実行可能コードモジュールにスケジューリングすることによって、プリフェッチ動作が多くのキャッシュミスを生成する該関数のセット内でのメモリ動作について行われるようにする工程と、
を包含する、方法。
【請求項２】
前記明示的なプリフェッチ動作を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数の開始でプリフェッチ生成をアクティブにする工程と、
該識別された関数からのリターンでプリフェッチ生成をイナクティブにする工程と
を含む、請求項１に記載の方法。
【請求項３】
前記プリフェッチ生成をアクティブにする工程は、コマンド線において特定されたプリフェッチ生成に応じて該プリフェッチ生成をアクティブにする工程を含む、請求項２に記載の方法。
【請求項４】
相互排除ロック動作と相互排除ロック解除動作との間のコードの領域を識別することによって、実行可能コードモジュール内のクリティカル部分を識別する工程と、
該クリティカル部分内に配置されるメモリ動作に先だって、明示的なプリフェッチ命令を前記実行可能コードモジュールにスケジューリングすることによって、前記プリフェッチ動作を該クリティカル部分内でメモリ動作について実行する工程と
をさらに包含する、請求項１に記載の方法。
【請求項５】
前記明示的なプリフェッチ命令を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内で特定のタイプのメモリ動作のサブセットを識別する工程と、
該サブセットに属するメモリ動作の明示的なプリフェッチ動作をスケジューリングする工程と
をさらに含む、請求項１に記載の方法。
【請求項６】
前記メモリ動作の特定のタイプは、
ポインタを介するメモリ動作と、
スタティックデータに関わるメモリ動作と、
以前にアクセスされていない位置からのメモリ動作と、
システムスタックの外部のメモリ動作と、
実行される可能性が高いメモリ動作と
のうちの１つを含む、請求項５に記載の方法。
【請求項７】
前記明示的なプリフェッチ命令を、実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内でメモリ動作に関連する特定の特性でプリフェッチ動作のサブセットを識別する工程と、
該サブセットの特性に基づいた該サブセットに属するプリフェッチ動作について、明示的なプリフェッチ動作をスケジューリングする工程と
をさらに包む、請求項１に記載の方法。
【請求項８】
前記プリフェッチ動作のサブセットの特定の特性は、
該プリフェッチ動作についての利用可能な供給スロットの存在と、
関連するメモリ動作から関数呼び出しサイトと同じ側に位置することと、
関連するメモリ動作から関数呼び出しサイトと反対側に位置することと、
スケジューリングされたプリフェッチ動作の対象にまだなっていないキャッシュブロックに関連付けられることと
のうちの１つを含むが、これらに限定されない、請求項７に記載の方法。
【請求項９】
コンピュータによって実行される場合に、ソースコードを、キャシュミスを生成する傾向のあるコードの領域内でメモリ動作についてプリフェッチを行う実行可能コードにコンパイルする方法を該コンピュータに行わせる命令を格納するコンピュータ読み出し可能格納媒体であって、該方法は、
プログラミング言語命令を含むソースコードモジュールを、プロセッサによって実行されることに適した命令を含む実行可能コードモジュールにコンパイルする工程と、
多くのキャッシュミスを生成する傾向のあるメモリ動作を含む関数を識別する工程であって、
代表的なワークロードのトレーニングモードで該プロセッサの該実行可能コードモジュールを実行する工程と、
該実行可能コードモジュール内の関数内でメモリ動作についてキャッシュミスレートに関する統計を取る工程と、
多くのキャッシュミスを生成する関数のセットを識別する工程と
によって、多くのキャッシュミスを生成する傾向のあるメモリ動作を含む関数を識別する工程と、
明示的なプリフェッチ命令を、該識別された関数のセット内でのメモリ動作に先立って、該実行可能コードモジュールにスケジューリングすることによって、プリフェッチ動作を、多くのキャッシュミスを生成する該関数のセット内でメモリ動作について行う工程と、
を包含する、コンピュータ読み出し可能格納媒体。
【請求項１０】
前記明示的なプリフェッチ動作を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数の開始でプリフェッチ生成をアクティブにする工程と、
該識別された関数からのリターンでプリフェッチ生成をイナクティブにする工程と
を含む、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１１】
前記プリフェッチ生成をアクティブにする工程は、コマンド線において特定されたプリフェッチ生成に応じて該プリフェッチ生成をアクティブにする工程を含む、請求項１０に記載のコンピュータ読み出し可能格納媒体。
【請求項１２】
前記コンピュータ読み出し可能格納媒体内に格納された命令内に実装された方法は、
相互排除ロック動作と相互排除ロック解除動作との間のコードの領域を識別することによって、実行可能コードモジュール内のクリティカル部分を識別する工程と、
該クリティカル部分内に配置されるメモリ動作に先だって、明示的なプリフェッチ命令を前記実行可能コードモジュールにスケジューリングすることによって、前記プリフェッチ動作を該クリティカル部分内でメモリ動作について実行する工程と
をさらに含む、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１３】
前記明示的なプリフェッチ命令を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内で特定のタイプのメモリ動作のサブセットを識別する工程と、
該サブセットに属するメモリ動作の明示的なプリフェッチ動作をスケジューリングする工程と
をさらに含む、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１４】
前記メモリ動作の特定のタイプは、
ポインタを介するメモリ動作と、
スタティックデータに関わるメモリ動作と、
以前にアクセスされていない位置からのメモリ動作と、
システムスタックの外部のメモリ動作と、
実行される可能性が高いメモリ動作と
のうちの１つを含むが、これらに限定されない、請求項１３に記載のコンピュータ読み出し可能格納媒体。
【請求項１５】
前記明示的なプリフェッチ命令を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内でメモリ動作に関連する特定の特性でプリフェッチ動作のサブセットを識別する工程と、
該サブセットの特性に基づいた該サブセットに属するプリフェッチ動作について、明示的なプリフェッチ動作をスケジューリングする工程と
をさらに含む、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１６】
前記プリフェッチ動作のサブセットの特定の特性は、
該プリフェッチ動作についての利用可能な供給スロットの存在と、
関連するメモリ動作から関数呼び出しサイトと同じ側に位置することと、
関連するメモリ動作から関数呼び出しサイトと反対側に位置することと、
スケジューリングされたプリフェッチ動作の対象にまだなっていないキャッシュブロックに関連付けられることと
のうちの１つを含むが、これらに限定されない、請求項１５に記載のコンピュータ読み出し可能格納媒体。
【請求項１７】
ソースコードを、キャシュミスを生成する傾向のあるコードの領域内でメモリ動作についてプリフェッチを行う実行可能コードにコンパイルする装置であって、
プログラミング言語命令を含むソースコードモジュールをプロセッサによって実行されることに適した命令を含む実行可能コードモジュールにコンパイルするコンパイル機構と、
多くのキャッシュミスを生成する傾向のあるメモリ動作を含む関数を識別する識別機構であって、該識別機構は、
代表的なワークロードのトレーニングモードで該プロセッサ上の実行可能コードモジュールを実行し、
該実行可能コードモジュール内の関数内でメモリ動作についてキャッシュミスレートに関する統計を取り、
多くのキャッシュミスを生成する関数のセットを識別する
ように構成される識別機構と、
明示的なプリフェッチ命令を、該識別された関数のセット内のメモリ動作に先立って、該実行可能コードモジュールにスケジューリングすることによって、プリフェッチ動作を多くのキャッシュミスを生成する該関数のセット内でのメモリ動作について行うスケジュール機構と、
を備える、装置。
【請求項１８】
前記スケジューリング機構は、
前記識別された関数の開始でプリフェッチ生成をアクティブにし、
該識別された関数からのリターンでプリフェッチ生成をイナクティブにするように構成される、請求項１７に記載の装置。
【請求項１９】
前記スケジューリング機構は、
コマンド線において特定されたプリフェッチ生成に応じて該プリフェッチ生成をアクティブにするように構成される、請求項１８に記載の装置。
【請求項２０】
前記識別機構は、相互排除ロック動作と相互排除ロック解除動作との間のコードの領域を識別することによって、前記実行可能コードモジュール内のクリティカル部分を識別するように構成され、
前記スケジューリング機構は、該クリティカル部分内に配置されるメモリ動作に先だって、明示的なプリフェッチ命令を該実行可能コードモジュールにスケジューリングすることによって、前記プリフェッチ動作を該クリティカル部分内のメモリ動作について実行するようにさらに構成される、請求項１７に記載の装置。
【請求項２１】
前記スケジューリング機構は、
前記識別された関数のセット内の特定のタイプのメモリ動作のサブセットを識別し、
該サブセットに属するメモリ動作の明示的なプリフェッチ動作をスケジューリングする
ようにさらに構成される、請求項１７に記載の装置。
【請求項２２】
前記メモリ動作の特定のタイプは、
ポインタを介するメモリ動作と、
スタティックデータに関わるメモリ動作と、
以前にアクセスされていない位置からのメモリ動作と、
システムスタックの外部のメモリ動作と、
実行される可能性が高いメモリ動作と
のうちの１つを含むが、これらに限定されない、請求項２１に記載の装置。
【請求項２３】
前記スケジューリング機構は、
前記識別された関数のセット内でメモリ動作に関連する特定の特性でプリフェッチ動作のサブセットを識別し、
該サブセットの特性に基づいた該サブセットに属するプリフェッチ動作について、明示的なプリフェッチ動作をスケジューリングする
ようにさらに構成された、請求項１７に記載の装置。
【請求項２４】
前記プリフェッチ動作のサブセットの特定の特性は、
該プリフェッチ動作についての利用可能な供給スロットの存在と、
関連するメモリ動作から関数呼び出しサイトと同じ側に位置することと、
関連するメモリ動作から関数呼び出しサイトと反対側に位置することと、
スケジューリングされたプリフェッチ動作の対象にまだなっていないキャッシュブロックに関連付けられることと
のうちの１つを含むが、これらに限定されない、請求項２３に記載の装置。
【請求項２５】
ソースコードを、キャシュミスを生成する傾向のあるコードの領域内でメモリ動作についてプリフェッチを行う実行可能コードにコンパイルする方法であって、
プログラミング言語命令を含むソースコードモジュールを、プロセッサによって実行されることに適した命令を含む実行可能モジュールにコンパイルする工程と、
多くのキャッシュミスを生成する傾向のあるメモリ動作を含むコードの領域を識別する工程と、
明示的なプリフェッチ命令を、該コードの識別された領域内のメモリ動作に先立って、該実行可能コードモジュールにスケジューリングすることによって、プリフェッチ動作を多くのキャッシュミスを生成する傾向のある該コードの領域でのメモリ動作について行う工程と、
を包含する、方法。
【請求項２６】
前記明示的なプリフェッチ命令を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内の特定のタイプのメモリ動作のサブセットを識別する工程と、
該サブセットに属するメモリ動作の明示的なプリフェッチ動作をスケジューリングする工程と
をさらに含む、請求項２５に記載の方法。
【請求項２７】
前記メモリ動作の特定のタイプは、
ポインタを介するメモリ動作と、
スタティックデータに関わるメモリ動作と、
以前にアクセスされていない位置からのメモリ動作と、
システムスタックの外部のメモリ動作と、
実行される可能性が高いメモリ動作と
のうちの１つを含むが、これらに限定されない、請求項２６に記載の方法。
【請求項２８】
前記メモリ動作の特定のタイプは、前記コードの領域について領域マーカによって特定される、請求項２６に記載の方法。
【請求項２９】
前記明示的なプリフェッチ命令を実行可能コードモジュールにスケジューリングする工程は、
前記識別された関数のセット内でメモリ動作に関連する特定の特性でプリフェッチ動作のサブセットを識別する工程と、
該サブセットの特性に基づいて、該サブセットに属するプリフェッチ動作の明示的なプリフェッチ動作をスケジューリングする工程と
をさらに含む、請求項２５に記載の方法。
【請求項３０】
前記プリフェッチ動作のサブセットの特定の特性は、
該プリフェッチ動作についての利用可能な供給スロットの存在と、
関連するメモリ動作から関数呼び出しサイトと同じ側に位置することと、
関連するメモリ動作から関数呼び出しサイトと反対側に位置することと、
スケジューリングされたプリフェッチ動作の対象にまだなっていないキャッシュブロックに関連付けられることと
のうちの１つを含むが、これらに限定されない、請求項２９に記載の方法。
【請求項３１】
前記プリフェッチ動作のサブセットの特定の特性は、前記コードの領域について領域マーカによって特定される、請求項２９に記載の方法。
【発明の詳細な説明】
【０００１】
（関連出願）
本願の主題は、同時係属出願中の、本願と同じ発明者による、本出願と同じ日に出願された、「Ｍｅｔｈｏｄ　ａｎｄ　Ａｐｐａｒａｔｕｓ　ｆｏｒ　Ｐｅｒｆｏｒｍｉｎｇ　Ｐｒｅｆｅｔｃｈｉｎｇ　ａｔ　ｔｈｅ　Ｃｒｉｔｉｃａｌ　Ｓｅｃｔｉｏｎ　Ｌｅｖｅｌ」という名称の仮出願でない出願の主題と関連する。この出願の出願番号および出願日は割り当てられる予定である（代理人ドケット番号ＳＵＮ−Ｐ４３４２−ＪＴＦ）。
【０００２】
（背景）
（発明の分野）
本発明は、コンピュータシステム用のコンパイラに関する。より具体的には、本発明は、ソースコードを、キャッシュ（ｃａｃｈｅ）ミスを多数発生する傾向のあるコードの領域内でメモリ動作のプリフェッチを行う実行可能なコードにコンパイルする方法および装置を提供する。
【０００３】
（関連技術）
プロセッサクロックスピードが、指数関数的な速度で増大し続けるにつれて、メモリ待ち時間が、コンピュータシステム性能における大きなネックとなってきている。いくつかの適用例において、プロセッサは、未処理のメモリ動作がデータをキャッシュまたはメインメモリからプロセッサ内のレジスタに移動させるために待機することに時間のうちの半分までを費やし得る。１つのメモリ動作が、高速Ｌ１キャッシュからのキャッシュミス、およびより遅いＬ２キャッシュからの対応するアクセスの原因となる場合、あるいは、さらに悪いことに、メモリ動作が、Ｌ２キャッシュからのキャッシュミスおよびメインメモリからの対応するアクセスの原因となる場合、プロセッサを、多数のクロックサイクルの間待機させ得る。
【０００４】
メモリ動作から返ってきたデータを利用する命令に先立って、メモリ動作を開始し得るようにシステムを設計することによって、メモリ動作の影響を制限して、性能の一部を緩和することが可能である。しかし、このような能力を有するようにプロセッサを設計することは、プロセッサを格段に複雑にし得る。このように複雑になることによって、プロセッサのコストが増加し得、さらに複雑になることによってプロセッサを通じるクリティカル経路が延ばされる場合、プロセッサのクロックスピードが潜在的に低減し得る。さらに、このような技術を用いることによって得られる潜在的な性能は、限定され得る。
【０００５】
コンパイルプロセスの間、メモリ動作が行われる前に、メモリ動作に関連するデータを明示的にプリフェッチするように、実行可能コードを変更することも可能である。これによって、メモリ動作が発生するときに、データがＬ１キャッシュに存在する可能性が高くなる。このタイプのプリフェッチは、コードにおいてメモリ動作が起きる前に、データをＬ１キャッシュにプリフェッチするために、関連するメモリ動作に先立って、明示的なプリフェッチ動作をコードにスケジューリングすることによって、達成され得る。
【０００６】
不運なことに、どのデータアイテムが、プリフェッチされるべきであり、どのデータアイテムがプリフェッチされるべきでないのかを判定することは非常に困難である。全てのデータアイテムをプリフェッチすることは、むだである。なぜなら、メモリシステムは、参照されないプリフェッチデータアイテムのネックとなり得るからである。一方、個々のメモリ動作を解析して、それらがプリフェッチの良好な候補であるか否かを判定することは、計算時間を大量に費やし得る。
【０００７】
必要とされているのは、個々のメモリ動作を解析する時間を大量に費やすことなく、一組のプリフェッチするメモリ動作を選択する方法および装置である。
【０００８】
（要旨）
本発明の一実施形態は、ソースコードを、キャッシュミスを生成する傾向があるコードの領域内でメモリ動作について、プリフェッチを行う実行可能コードにコンパイルするシステムを提供する。そのシステムは、プログラミング言語命令を含むソースコードモジュールを、プロセッサによって実行されることに適した命令を含む実行可能コードモジュールにコンパイルすることによって動作する。次に、システムは、それぞれのワークロードについて、トレーニングモードで実行可能コードモジュールを実行し、実行可能コードモジュール内の関数について、キャッシュミスレートの統計を取る。これらの統計を用いて、多数のキャッシュミスを生成する、１セットの「ホット」関数が識別される。次に、明示的なプリフェッチ命令が、このセットのホット関数内のメモリ動作に先立って、スケジューリングされる。
【０００９】
一実施形態において、明示的なプリフェッチ動作は、識別された関数の開始で、プリフェッチ生成をアクティブにすることによって、かつ、識別された関数からのリターンでプリフェッチ生成をイナクティブにすることによって、実行可能コードモジュールにスケジューリングされる。
【００１０】
実施形態において、システムは、メモリ動作について、プリフェッチ動作を、１セットのホット関数のうちの特定のタイプのメモリ動作のサブセットを識別すし、サブセットに属するメモリ動作について明示的なプリフェッチ動作をスケジューリングすることによって、さらにスケジューリングする。特定のタイプのメモリ動作には、ポインタを介するメモリ動作、スタティックデータに関わるメモリ動作、以前にアクセスされていない位置からのメモリ動作、システムスタックの外部のメモリ動作、および実行される可能性の高いメモリ動作が含まれ得る。
【００１１】
一実施形態において、システムは、特定の性質を有するプリフェッチ動作のサブセットを識別することによって、かつ、その性質に基づいてプリフェッチ動作をスケジューリングすることによって、プリフェッチ動作をスケジューリングする。例えば、特定の性質には、利用可能な供給スロットを有すること、関連するメモリ動作から関数呼び出しサイトの反対側に位置すること、関連するメモリ動作から関数呼び出しサイトの同じ側に位置すること、まだスケジューリングされたプリフェッチ動作に対する対象でないキャッシュブロックに関連付けられていることが含まれ得る。
【００１２】
本発明の一実施形態は、ソースコードを、相互排除の対象となるコードのクリティカル部分内でのメモリ動作について、プリフェッチを行う実行可能コードにコンパイルするシステムを提供する。システムは、プログラミング言語命令を含むソースコードモジュールを、プロセッサによって実行されることに適した命令を含む実行可能コードモジュールにコンパイルすることによって動作する。次に、システムは、実行可能コードモジュール内のクリティカル部分を、相互排除ロック動作と相互排除ロック解除動作との間のコードの領域を識別することによって識別する。システムは、明示的なプリフェッチ命令を、関連するメモリ動作に先立って、クリティカル部分にスケジューリングする。
【００１３】
一実施形態において、システムは、第１のマクロを用いて、相互排除ロック動作を行うことによって、コードのクリティカル部分を識別する。第１のマクロは、さらにプリフェッチをアクティブにする。また、システムは、第２のマクロを用いて、相互排除ロック解除動作を行う。第２のマクロは、さらに、プリフェッチをイナクティブにする。相互排除ロック解除動作が他のクリティカル部分内にネストされている場合、第２のマクロは、プリフェッチをイナクティブにしないことに留意されたい。
【００１４】
（詳細な説明）
以下の説明は、当該技術の当業者が本発明を作成し、用いることを可能にするために提示され、特定の適用例およびその要件のコンテキストにおいて提供される。開示された実施形態への様々な改変例が当業者に容易に理解され、本明細書に規定された概略的な原理が、本発明の意図および範囲から逸脱することなく、他の実施形態および適用例に適用され得る。従って、本発明は、示した実施形態に限定されることを意図したものではなく、本明細書中に開示した原理および特徴と首尾一貫する最も広い範囲に一致するものである。
【００１５】
この詳細な説明において説明されたデータ構造およびコードは、典型的には、コンピュータシステムによって用いられる、コードおよび／またはデータを格納し得る任意のデバイスまたは媒体であり得る、コンピュータ読み出し可能格納媒体に格納される。これには、磁気および光学格納デバイス、例えば、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（デジタルビデオディスク）、および転送媒体（信号が変調される搬送波を含むか、または含まない）として実装されたコンピュータ命令信号が含まれるが、これらに限定されるものではない。例えば、転送媒体は、通信ネットワーク、例えば、インターネットを含み得る。
【００１６】
（コンピュータシステム）
図１に、本発明の一実施形態による、コンピュータシステム１００の内部構造を示す。特に、図１に、中央処理装置（ＣＰＵ）１０２内のレジスタ１０４と、Ｌ１キャッシュ１０６と、プリフェッチキャッシュ１０８と、Ｌ２キャッシュ１１０と、メモリ１１２と、格納デバイス１１６とを含むコンピュータシステム１００のメモリ階層を示す。
【００１７】
ＣＰＵ１０２は、コンピュータシステムにおいて用いられ得る任意のタイプの処理エンジンを含み得る。コンピュータシステムは、マイクロプロセッサ、メインフレームプロセッサ、デバイスコントローラ、個人用オーガナイザ内のプロセッサ、および器具内の処理回路を含むが、これらに限定されるものではない。レジスタ１０４は、Ｌ１キャッシュ１０６、プリフェッチキャッシュ１０８、Ｌ２キャッシュ１１０またはメモリ１１２からデータがロードされる、ＣＰＵ１０２内の内部レジスタである。データがレジスタ１０４にロードされた後、ＣＰＵ１０２は、データについての計算動作を行い得る。（この開示において、「ロード」動作をプリフェッチすることについてしばしば記載するが、このような記載が、プリフェッチから利益を得ることができる任意のメモリ動作、例えば、格納および他のメモリの参照にも適用されることに留意されたい。）
データは、Ｌ１キャッシュ１０６からレジスタ１０４にロードされる。Ｌ１キャッシュ１０６は、ＣＰＵ１０２の近傍に位置する、限定されたサイズの高速キャッシュメモリである。いくつかの実施形態において、Ｌ１キャッシュ１０６は、ＣＰＵ１０２と同じ半導体チップ内に位置し得る。
【００１８】
同様に、データは、プリフェッチキャッシュ１０８からレジスタ１０４にロードされる。プリフェッチキャッシュ１０８も、ＣＰＵ１０２の近傍に位置する、限定されたサイズの高速キャッシュメモリである。プリフェッチキャッシュ１０８とＬ１キャッシュ１０６との違いは、プリフェッチキャッシュ１０８は明示的にプリフェッチされるデータを保持するが、Ｌ１キャッシュ１０６は、最近参照されたが、プリフェッチされないデータを保持することである。プリフェッチキャッシュ１０８を用いると、Ｌ１キャッシュ１０６を汚染することなく起こる推論的（ｓｐｅｃｕｌａｔｉｖｅ）プリフェッチを可能にする。
【００１９】
データは、Ｌ２キャッシュ１１０からＬ１キャッシュ１０６およびプリフェッチキャッシュ１０８にロードされる。Ｌ２キャッシュ１１０は、Ｌ１キャッシュ１０６またはプリフェッチキャッシュ１０８よりも相当大きい。しかし、Ｌ２キャッシュは、ＣＰＵ１０２からより遠くに位置し、従って、Ｌ２キャッシュ１１０へのアクセスは、Ｌ１キャッシュ１０６またはプリフェッチキャッシュ１０８へのアクセスよりも、時間がかかる。しかし、Ｌ２キャッシュへのアクセスは、メモリ１１２へのアクセスより時間がかからないことに留意されたい。
【００２０】
Ｌ１キャッシュ１０６、プリフェッチキャッシュ１０８、およびＬ２キャッシュ１１０は、多数の方法で設計され得る。例えば、直接マッピングされたキャッシュ、完全結合キャッシュ、またはセット結合キャッシュが含まれ得る。また、ライトスルーキャッシュまたはライトバックキャッシュが含まれ得る。
【００２１】
データは、メモリ１１２からＬ２キャッシュにロードされる。メモリ１１２は、ＣＰＵ１０２によって用いられるコードおよび／またはデータを格納するために用いられ得る、任意のタイプのランダムアクセスメモリを含み得る。図１に示す本発明の一実施形態において、メモリ１１２は、図２〜６を参照しながら以下に説明するように、関数レベルまたはクリティカル部分レベルで挿入される、明示的なプリフェッチ命令を有するコードを含む。
【００２２】
データは、格納デバイス１１６内のファイルから、メモリ１１２にロードされる。格納デバイス１１６は、ＣＰＵ１０２によって、操作されるコードおよび／またはデータを格納する、任意のタイプの不揮発性格納デバイスを含み得る。一実施形態において、格納デバイス１１６は、磁気ディスクドライブを含む。
【００２３】
また、図１は、ＣＰＵ１０２が、ネットワーク１２０を介して、サーバ１２２にどのように結合され得るかを示す。ネットワーク１２０は、計算ノードを互いに結合することができる、任意のタイプのワイヤ通信チャネルまたはワイヤレス通信チャネルを含み得る。このような通信チャネルには、ローカルエリアネットワーク、ワイドエリアネットワーク、またはネットワークの組合せが含まれるが、これらに限定されない。本発明の一実施形態において、ネットワーク１２０は、インターネットを含む。サーバ１２２は、計算またはデータ格納リソースについてクライアントからのリクエストに応じるメカニズムを含む任意の計算ノードを含み得る。本発明の実施形態において、サーバ１２２は、ＣＰＵ１０２によって実行される実行可能なコードを含むファイルサーバである。また、ネットワーク１２０がＣＰＵ１０２に直接結合されるとして説明されるが、概して、ネットワーク１０２は、図１に示すコンピュータシステム内の他の位置に結合され得ることに留意されたい。
【００２４】
図１が、メモリ階層の構成要素を、様々なデータ経路およびバスを介して互いに結合し得る多くの可能な様態を図示していないことに留意されたい。また、本発明が、図１に示す特定のコンピュータシステムだけではなく、概して、プリフェッチ能力を有する任意のタイプのコンピュータシステムに適用され得ることに留意されたい。
【００２５】
（コードの領域内でのロード）
図２に、本発明の実施形態による、実行可能コードの領域内で発生するロード動作を示す。図２は、領域（領域Ａ２０２と、領域Ｂ２０４と、領域Ｃ２０６とを含む）に分割したコード部分を示している。これらの領域は、メモリ階層からのデータを、ＣＰＵ１０２内のレジスタ１０４にロードするロード動作を含む。これらのロード動作は、図１の中央の列に示される。コード部分が、干渉するロード以外の動作（不図示）をも多く含むことに留意されたい。これらのロード以外の動作は、ロード動作によって、レジスタ１０４に引き込まれるデータを演算する。
【００２６】
図２の右側の列に、ロード動作の結果を示す。より具体的には、図２の上から最初の２つのロード動作（領域Ａ２０２内）は、Ｌ１キャッシュ１０６から取り出される。次の４つのロード動作（領域Ｂ２０４内）は、Ｌ２キャッシュ１１０、メモリ１１２、Ｌ２キャッシュ１１０、およびＬ２キャッシュ１１０から、それぞれ取り出される。最後の２つのロード（領域Ｃ２０６内）は、Ｌ１キャッシュ１０６から取り出される。
【００２７】
この実施例において、領域Ｂ２０４内の全てのロードは、Ｌ１キャッシュ１０６からＬ２キャッシュ１１０にキャッシュミスを生成する。これらのロードのうちの１つは、Ｌ２キャッシュ１１０におけるさらなるキャッシュミス、およびメモリ１１２への対応するアクセスを生成する。領域Ｂ２０４は、領域Ｂ２０４内の高い割合のロードがキャッシュミスを生じるので、「ホット」領域と呼ばれる。従って、領域Ｂ２０４内のロードは、プリフェッチの良好な候補である。
【００２８】
領域境界が、複数の様態で判定され得ることに留意されたい。本発明の一実施形態において、領域境界は、関数的境界である。他の実施形態において、領域境界は、クリティカル部分境界である。クリティカル部分が、典型的には、キャッシュミスが起こりやすい、共有データにアクセスするので、クリティカル部分内のロードは多数のキャッシュミスを生成する傾向にあることに留意されたい。領域境界は、ユーザによって特定されるコードの任意の「ホット」領域をも含み得る。領域境界は、コマンドラインによって特定され得る完全なソースファイルをも含み得る。
【００２９】
（クリティカル部分のプリフェッチ）
図３Ａに、本発明の一実施形態による、プリフェッチをイネーブルおよびディセーブルする相互排除マクロを示す。図３Ａの上に示す第１のマクロは、相互排除変数をロックする前に、特定のプリフェッチ性質で、コンパイラのプリフェッチ機能をオンにする、相互排除ロックマクロである。このプリフェッチ機能は、プリフェッチ動作が、図５および図６を参照しながら以下に説明するようにフィルタアウトされない限り、全てのロード動作について、プリフェッチを行うように試みる。概して、相互排除変数が、任意のタイプの相互排除変数、例えば、スピンロックと関連する相互排除変数、セマフォー、読み書きロック、ターンスタイル、ミュテックス（ｍｕｔｅｘ）ロック、適応ミュテックスロック、または任意の他の相互排除メカニズムを含み得ることに留意されたい。
【００３０】
また、プリフェッチ機能が、関連するロードおよびプリフェッチ命令の特定のプリフェッチ性質を有し得ることに留意されたい。これらの性質については、以下でより詳細に説明する。従って、異なる相互排除マクロは、異なるプリフェッチ性質をアクティブにし得る。本発明の他の実施形態において、異なるプリフェッチ性質は、関数レベル、ファイルレベル、またはコードの任意の領域内でアクティブにされ得る。これらの異なるプリフェッチ特性は、特定の性質の特有の異なる領域マーカ（例えば、相互排除マクロ）によって、アクティブにされ、イナクティブにされ得る。これらの異なる領域マーカがネストされ得ることに留意されたい。
【００３１】
図３Ａに示す第２のマクロは、相互排除変数をロック解除し、プリフェッチ機能をオフにする、対応する相互排除ロック解除マクロの例である。本発明の一実施形態において、システムは、プリフェッチをイナクティブにし、プリフェッチをアクティブにする、適合する第１のマクロによって先行されない、適合しない第２のマクロをチェックする。このような適合しない第２のマクロが発生する場合、システムは、エラー状態を知らせ得る。
【００３２】
図３Ｂに、本発明の一実施形態による、クリティカル部分のネストを示す。多くの適用例において、クリティカル部分は、ネストされる。例えば、図３Ｂにおいて、ｍｕｔｅｘ＿ｌｏｃｋ（Ｂ）およびｍｕｔｅｘ＿ｕｎｌｏｃｋ（Ｂ）によって境界が定められるクリティカル部分Ｂ３０４は、ｍｕｔｅｘ＿ｌｏｃｋ（Ａ）およびｍｕｔｅｘ＿ｕｎｌｏｃｋ（Ａ）によって境界が定められるクリティカル部分Ａ３０２内にネストされる。この場合、ｔｕｒｎｏｆｆ＿ｐｒｅｆｅｔｃｈ（）関数は、ネストされたクリティカル部分の数を追跡し、ネストされたクリティカル部分の端部でプリフェッチをオフにしない。例えば、図３Ｂにおけるｍｕｔｅｘ＿ｕｎｌｏｃｋ（Ｂ）呼び出しは、ネストされたクリティカル部分Ｂ３０４と関連するので、プリフェッチをオフにしない。しかし、ｍｕｔｅｘ＿ｕｎｌｏｃｋ（Ａ）呼び出しは、後に続くコードが任意のクリティカル部分の外側にあり、プリフェッチの目的とはならないので、プリフェッチをオフにする。
【００３３】
図６は、本発明の一実施形態による、クリティカル部分内におけるロードをプリフェッチするコードを作成するプロセスを示すフローチャートである。システムは、ソースコードモジュールを実行可能コード命令にコンパイルして、対応する実行可能コードモジュールを生成することによって開始する（工程６０２）。そうすることにおいて、システムは、クリティカル部分を識別する（工程６０４）。これは、図３Ａに示すｍｕｔｅｘ＿ｌｏｃｋ（）マクロおよびｍｕｔｅｘ＿ｕｎｌｏｃｋ（）マクロを用いることによって、行われ得る。あるいは、コンパイラは、プリフェッチをイネーブルおよびディセーブルするために、相互排除ロックおよびロック解除動作を探すように変更され得る。
【００３４】
次に、システムは、クリティカル部分内のロード動作を調べ、ある特定のタイプのロード動作について、プリフェッチ動作をスケジューリングする（工程６０６）。これは、プリフェッチ動作の数を大幅に低減し得る。例えば、システムは、ポインタを介するロード、スタティックデータのロード、ポインタを介するロードおよびスタティックデータのロード、システムスタックの外部からのロード、ならびに実行される可能性の高いロードをプリフェッチすることを選択し得る。実行される可能性の高いロードは、トレーニングモードにおいて、実行可能なコードを実行することによって、識別され得ることに留意されたい。また、システムスタック内のロード、または、以前にロードされた位置からのロードは、キャッシュミスを生成する可能性が低く、従って、プリフェッチに関して、不適確な候補であることに留意されたい。
【００３５】
また、システムは、プリフェッチ動作の性質に基づいて、クリティカル部分内に現れるプリフェッチ動作をスケジューリングし得る（工程６０８）。例えば、システムは、プリフェッチ動作について、利用可能なロード供給スロットおよび利用可能な未処理ロードがある場合にのみ、プリフェッチ動作をスケジューリングすることを選択し得る。プロセッサ内の典型的なロード格納単位が、少ない数の利用可能なロード供給スロット、ならびに、限定された数の未処理ロードを有することに留意されたい。これらのロード供給スロットが充填される場合、プリフェッチをスケジューリングすることは、プリフェッチについて、利用可能なロード供給スロットがないので、意味をなさない。また、システムは、関連するロード動作からの関数呼び出しサイトの反対側で（あるいは、関数呼び出しサイトと同じ側で）プリフェッチ動作をスケジューリングし得る。これは、関数についての呼び出しサイトが、ミュテックスロック関数のようなキャッシュに影響する可能性が低い場合、有用であり得る。他のタイプの関数について、関数呼び出しの前にプリフェッチを供給することは、関数呼び出しが、長期間、実行の流れをコードの他の領域に移動させる可能性が高いので、意味をなさない。また、システムは、スケジュールされたプリフェッチ動作の既に目的ではないキャッシュブロックについてのプリフェッチをスケジューリングし得る。
【００３６】
この時点で、ソースコードは、通常プログラム実行の用意ができている。
【００３７】
（実行される可能性の高いロードのプリフェッチ）
図４に、本発明の一実施形態による、実行される可能性の高いロードのプリフェッチの実施例を示す。関数４００は、４つの基本ブロック４０２〜４０５に分割される。基本ブロックは、制御フローにおける変化なしに、実行されるコード部分である。従って、基本ブロックは、ブロックの端部に、せいぜい、１つのブランチまたは関数呼び出しを含む。図４において、基本ブロック４０２の端部に、基本ブロック４０４または基本ブロック４０３のいずれかに進む、条件ブランチがある。後に、これらの別個のブランチ経路は、基本ブロック４０５において再結合する。
【００３８】
例示的な基本ブロック４０２〜４０５のそれぞれは、ロード動作を含む。より具体的には、基本ブロック４０２は、ロードＡおよびＢを含む。基本ブロック４０３は、ロードＤおよびＥを含む。基本ブロック４０４は、ロードＦおよびＧを含む。最終的に、基本ブロック４０５は、ロードＨ、Ｉ、Ｊ、およびＫを含む。
【００３９】
図４に示す例において、関数４００が、代表的なワークロードで実行される多数のキャッシュミスを示した「ホット」関数であると仮定する。この例において、システムは、システムスタックに向けられたロードを、これらのロードはキャッシュミスを生成する可能性が低いので、フィルタアウトすることによって開始する。これはロードＣ、Ｇ、およびＨを消去する。
【００４０】
次に、システムは、実行される可能性が低いロードを消去する。基本ブロック４０２、４０４、および４０５が同様に実行されるロード動作を含むと仮定する。これによって、ロードＤおよびＥが消去される。システムが、代表的なワークロードにおいて、「トレーニングモード」の関数４００を含むプログラムを実行することによって、かつ、どの命令が関数４００を介して実行されるかについての統計を取ることによって実行される可能性が高いロード命令を識別し得ることに留意されたい。
【００４１】
次に、システムは、同様の実行経路上にプリフェッチをスケジューリングする。そうすることによって、システムは、未処理のプリフェッチの数が、システムのロード格納装置における利用可能なロード供給スロットの数および未処理のロードの最大数を超えないことを確実にする。図４に示す例においては、利用可能な４つの未処理ロードがあると仮定している。従って、基本ブロック４０２のはじめにおいて、システムは、ロードＡの前に、ロードＢ、Ｆ、およびＩをプリフェッチする。（Ｂ、Ｆ、およびＩの３つのプリフェッチ、ならびにＡのロードには、４つのロード供給スロットが用いられることに留意されたい。）次に、Ｂのプリフェッチが、Ａのロードの完了した直後に完了すると仮定すると、他の未処理ロードが利用可能になり、システムがロードＪをプリフェッチする。その後、ロードＦの発生の前に、Ｆのプリフェッチが完了すると仮定すると、システムは、ロードＫをプリフェッチする。
【００４２】
実行される可能性の高いロードをプリフェッチする技術が、コードの任意の領域において行われ得、関数に限定されないことに留意されたい。例えば、システムは、クリティカル部分内、または、コードの任意の他の部分内で実行される可能性の高いロードもプリフェッチし得る。
【００４３】
（選択された関数のプリフェッチ）
図５は、本発明の一実施形態における、ホット関数内のロードをプリフェッチするコードを作成するプロセスを示すフローチャートである。システムは、ソースコードモジュールを、実行可能コード命令にコンパイルして、対応する実行可能コードモジュールを生成することによって開始する（工程５０２）。
【００４４】
次に、システムは、実行可能モジュール内のどの関数が、キャッシュミスを多数作成する傾向にあるかを判定する。これらの関数を「ホット関数」と呼ぶ。システムは、代表的なワークロードにおいて、トレーニングモードの実行可能モジュールを実行すること（工程５０４）によって、かつ、関数レベルでキャッシュミスレートについて統計を取ること（工程５０６）によって、判定を行う。次に、システムは、これらの統計を用いて、キャッシュミスを多数生成する傾向のある関数を識別する（工程５０８）。
【００４５】
次に、システムは、ホット関数内の全てのロード動作を検査して、ある特定のタイプのロード動作について（上記で、クリティカル部分について行われたように）プリフェッチ動作をスケジューリングする（工程５１０）。また、システムは、ホット関数内に現れるプリフェッチ動作を、プリフェッチ動作の性質に基づいて、スケジューリングし得る（工程５１２）。この時点で、ソースコードが、通常のプログラム実行について用意ができる。
【００４６】
本発明の実施形態についての上記の説明は、例示および説明の目的のみで提示されてきた。この説明は、本発明を、開示された形態により網羅し、開示された形態に限定することを意図していない。従って、多くの改良例および改変例が、当業者にとって明らかである。さらに上記の開示内容は、本発明を限定することを意図したものではない。本発明の範囲は、添付の特許請求の範囲によって規定される。
【図面の簡単な説明】
【図１】
図１は、本発明の一実施形態による、コンピュータシステムを示す図である。
【図２】
図２は、本発明の一実施形態による、実行可能コードの領域内で発生するロード動作を示す図である。
【図３Ａ】
図３Ａは、本発明の一実施形態による、プリフェッチをイネーブルおよびディセーブルするマクロを示す図である。
【図３Ｂ】
図３Ｂは、本発明の一実施形態による、クリティカル部分のネストを示す図である。
【図４】
図４は、本発明の一実施形態による、実行される可能性が高いロードをプリフェッチする例を示す図である。
【図５】
図５は、本発明の一実施形態による、ホット関数においてロードをプリフェッチするコードを作成するプロセスを示すフローチャートである。
【図６】
図６は、本発明の一実施形態による、クリティカル部分においてロードをプリフェッチするコードを作成するプロセスを示すフローチャートである。
【図１】
2004501410.tif 000003
【図２】
2004501410.tif 000004
【図３Ｂ】
2004501410.tif 000005
【図４】
2004501410.tif 000006
【図５】
2004501410.tif 000007
【図６】
2004501410.tif 000008
【国際公開パンフレット】
2004501410.tif 000009
2004501410.tif 000010
2004501410.tif 000011
2004501410.tif 000012
2004501410.tif 000013
2004501410.tif 000014
2004501410.tif 000015
2004501410.tif 000016
2004501410.tif 000017
2004501410.tif 000018
2004501410.tif 000019
2004501410.tif 000020
2004501410.tif 000021
2004501410.tif 000022
2004501410.tif 000023
2004501410.tif 000024
2004501410.tif 000025
2004501410.tif 000026
2004501410.tif 000027
2004501410.tif 000028
2004501410.tif 000029
2004501410.tif 000030
2004501410.tif 000031
2004501410.tif 000032
2004501410.tif 000033
2004501410.tif 000034
2004501410.tif 000035
2004501410.tif 000036
【国際公開パンフレット（コレクトバージョン）】
2004501410.tif 000037
2004501410.tif 000038
【国際調査報告】
2004501410.tif 000039
2004501410.tif 000040
2004501410.tif 000041