並列コンピュータ・システムの性能を改良するための装置、方法及びコンピュータ・プログラム
【課題】並列コンピュータ・システムの性能を改良するための装置、方法及びコンピュータ・プログラムを提供する。
【解決手段】第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラは、プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有（false sharing）の発生を検出し且つ第２プロセッサによる第１キャッシュ・ラインの偽共有を許可する。第１キャッシュ・ラインの偽共有が発生するのは、第１ローカル・キャッシュ・コントローラによって第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新する場合である。
【解決手段】第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラは、プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有（false sharing）の発生を検出し且つ第２プロセッサによる第１キャッシュ・ラインの偽共有を許可する。第１キャッシュ・ラインの偽共有が発生するのは、第１ローカル・キャッシュ・コントローラによって第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新する場合である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列コンピュータ・システムに係り、さらに詳細に説明すれば、並列コンピュータ・システム内で動作するキャッシュ・コヒーレンス・プロトコルに係る。
【背景技術】
【０００２】
従来の並列コンピュータ・システムは、一度に２つ以上のスレッド又はプロセッサによって同じキャッシュ・ライン・アドレスを更新することを許可しない。もし、プロセッサが関連するローカル・キャッシュ・メモリ装置(以下「ローカル・キャッシュ」と略記）内のキャッシュ・ラインを更新することを望んでいれば、従来の並列コンピュータ・システムは、先ず、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化しなければならない。従って、キャッシュ・コヒーレント機構は、ローカル・キャッシュを更新するように（例えば、ローカル・キャッシュ内のキャッシュ・ラインを無効化するように）、コンピュータ・システム内で実装される。従って、従来の並列コンピュータ・システム内の２つ以上の別個のスレッド又はプロセッサは、ローカル・キャッシュ間でキャッシュ・コヒーレンス動作を実行する場合、同じキャッシュ・ライン・アドレスを同時に更新することができない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
２つ以上の別個のスレッド又はプロセッサによってアクセスされるときに同じキャッシュ・ライン・アドレスの同時的な更新を阻止するために、従来の並列コンピュータ・システムは、ローカル・キャッシュ間のより頻繁な通信（例えば、他のローカル・キャッシュへの無効化通知のブロードキャスト）を必要とし、ローカル・キャッシュ内のキャッシュ・ラインを頻繁に無効化する。
【課題を解決するための手段】
【０００４】
本明細書は、複数のプロセッサ及び少なくとも１つの共有キャッシュ・メモリ装置(以下「共有キャッシュ」と略記）を備える、並列コンピュータ・システムの性能を改良するための装置、方法及びコンピュータ・プログラムを開示する。各プロセッサは、少なくとも１つのローカル・キャッシュ（例えば、Ｌ１キャッシュ）を含む。
【０００５】
一側面では、並列コンピュータ・システムの性能を改良するための装置を提供する。本装置は、複数のプロセッサを備え、各プロセッサは、ローカル・キャッシュを有する。各プロセッサは、データ従属性（data dependency）を含まないソフトウェア・プログラム領域のプログラム・コードを実行する。各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するハードウェア・ローカル・キャッシュ・コントローラ(以下「ローカル・キャッシュ・コントローラ」と略記）に関連する。第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラは、プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有（false sharing）の発生を検出し且つ第２プロセッサによる第１キャッシュ・ラインの偽共有を許可する。第１キャッシュ・ラインの偽共有は、第１ローカル・キャッシュ・コントローラによって第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新するときに発生する。
【０００６】
他の側面では、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットする。
【０００７】
他の側面では、第２ローカル・キャッシュ・コントローラが第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新するとき、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットし、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、第２ローカル・キャッシュ・コントローラは、第２ローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットする。
【０００８】
他の側面では、複数のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラ及び第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている第１ローカル・キャッシュ及び第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【０００９】
他の側面では、ローカル・キャッシュへの任意の書き込みが、複数のプロセッサによって共有される共有キャッシュにライトスルーされる。
【００１０】
他の側面では、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される。
【００１１】
他の側面では、第１キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に、当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない。
【００１２】
他の側面では、複数のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。
【００１３】
他の側面では、２つ以上のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する。
【００１４】
他の側面では、２つ以上のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する。
【００１５】
他の側面では、偽共有の発生を検出するために、第１ローカル・キャッシュ・コントローラ及び第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する。
【発明の効果】
【００１６】
本発明は、並列コンピュータ・システムにおいて偽共有を許可することにより、ローカル・キャッシュへの書き込み動作が発生する都度の、キャッシュ・ラインを無効化するためのローカル・キャッシュ間の通信オーバーヘッドを減少させることができる。
【図面の簡単な説明】
【００１７】
【図１】一実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【図２】一実施形態に従った、データ従属性を含まないソフトウェア・プログラム領域を例示する図である。
【図３】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図４】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図５】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図６】一実施形態に従った、偽共有を許可する状態図である。
【図７】一実施形態に従った、状態遷移を例示する図である。
【図８】一実施形態に従った、状態遷移を例示する図である。
【図９】一実施形態に従った、状態遷移を要約するテーブルである。
【図１０】一実施形態に従った、図１及び図１２〜図１３に示すフローチャートを実装するための並列コンピュータ・システムを例示する図である。
【図１１】一実施形態に従った、フラグ・ビットを示す図である。
【図１２】一実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【図１３】他の実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【発明を実施するための形態】
【００１８】
図１０は、複数のプロセッサ７０５〜７１５（例えば、IBM(R)PowerPC(R)プロセッサ）及び共有キャッシュ７２０を備える、一実施形態に従った並列コンピュータ・システム７００を示す。各プロセッサは、ローカル・キャッシュ、例えば、プロセッサ７０５内のローカル・キャッシュ７３０、プロセッサ７１０内のローカル・キャッシュ７３５及びプロセッサ７１５内のローカル・キャッシュ７４０を含む。また、各プロセッサは、ローカル・キャッシュに関連するローカル・キャッシュ・コントローラを備える。ローカル・キャッシュ・コントローラは、ローカル・キャッシュ・メモリの読み取り及び書き込み動作を制御する。例えば、プロセッサ７０５に関連するローカル・キャッシュ・コントローラ７４５は、例えば、ローカル・キャッシュ７３０内のキャッシュ・ラインを無効化するためのフラグ・ビットをセットすることにより、ローカル・キャッシュ７３０を制御する。同様に、ローカル・キャッシュ・コントローラ７５０は、ローカル・キャッシュ７３５を制御し、ローカル・キャッシュ・コントローラ７５５は、ローカル・キャッシュ７４０を制御する。任意のローカル・キャッシュ・メモリ内の任意の更新は、例えば、バス又はネットワーク７２５を介して、共有キャッシュ７２０にライトスルーされる。また、共有キャッシュ７２０は、共有キャッシュ７２０を制御するキャッシュ・コントローラ７２２を含む。コンパイラ７６０は、高水準のプログラミング・コードを機械コードに変換するために設けられる。
【００１９】
並列コンピュータ・システム７００は、その性能を改良するために図１の方法ステップを実施する。図１のステップ１００では、ソフトウェア・プログラム領域（例えば、図２に示すソフトウェア・ループ２００）に入るときに、コンパイラ７６０は、当該ソフトウェア・プログラム領域がデータ従属性を含むか否かを決定する。コンパイラ７６０は、当該ソフトウェア・プログラムのどの部分を並列に実行可能であるかを知っている。なぜなら、ユーザが当該ソフトウェア・プログラムの特定のサブセットを並列に実行するように明示的に要求するか、又はコンパイラ７６０が対応するプログラム・コードを分析し且つ当該ソフトウェア・プログラムの特定のサブセットを並列に実行可能であると決定したからである。一旦、コンパイラ７６０が、当該プログラム・コードの一部を並列に実行可能であることを知ると、コンパイラ７６０は、並列タスク(即ち、複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域）の作成を扱うランタイム・ライブラリへの機能呼び出しを挿入する。コンパイラ７６０は、これらの並列タスクが開始する位置及び終了する位置に特殊命令を挿入する。一実施形態では、コンパイラ７６０は、並列に実行すべきソフトウェア・プログラム領域を作成する、ランタイム・ライブラリを呼び出す。従って、ランタイム・ライブラリは、ソフトウェア・プログラム領域を実行する直前に特殊命令を呼び出すとともに、ソフトウェア・プログラム領域を並列に実行した直後に特殊命令を呼び出す。他の実施形態では、コンパイラ７６０は、並列に実行されるソフトウェア・プログラム領域の最初の命令が１つの特殊命令であり、並列に実行されるソフトウェア・プログラム領域の最後の命令が他の特殊命令であるように、並列に実行すべきプログラム・コードを装備化（instrument）する。例えば、ソフトウェア・ループ２００がデータ従属性を含むか否かを決定するために、コンパイラ７６０は、ソフトウェア・ループ２００内の先行するソフトウェア・プログラム・ラインの出力がソフトウェア・ループ２００内の後続するソフトウェア・プログラム・ラインの入力として使用されるか否かを評価する。図２のソフトウェア・ループ２００において、アレイ「ｂ」内の２つの別個の要素が同じデータ値を含んでいなければ、データ従属性は存在しない。なぜなら、先行するループ反復の出力は、後続するループ反復の入力として使用されないからである。さらに、コンパイラ７６０は、例えば、図２のソフトウェア・ループ２００のループ出口条件に基づいて、データ従属性を含まないソフトウェア・プログラム領域の開始及び終了境界を決定する。図１のステップ１１０では、コンパイルの後、ソフトウェア・プログラム領域がデータ従属性を含まないことをコンパイラ７６０が決定することに応答して、全て又は一部のプロセッサは、データ従属性を含まないソフトウェア・プログラム領域を並列に実行する。例えば、少なくとも２つの異なるプロセッサが、図２のソフトウェア・ループ２００を実行する。もし、ソフトウェア・プログラム領域内にデータ従属性があれば、単一のプロセッサが、データ従属性を含むソフトウェア・プログラム領域を実行することができる。データ従属性を含まないソフトウェア・プログラム領域を並列に実行する間、各プロセッサは、そのローカル・キャッシュを変更することができる。しかし、本実施形態によれば、各プロセッサがバリア(即ち、全ての参加プロセッサが到達しなければならないポイントであって、そのポイントの後にだけ、各プロセッサがその後続の実行を継続することができる）に到達するまで、ローカル・キャッシュ内の変更を他のローカル・キャッシュが観察する必要はない。
【００２０】
図１のステップ１２０に示すように、全て又は一部のプロセッサが、データ従属性を含まないソフトウェア・プログラム領域を並列に実行することを開始するとき、各プロセッサのローカル・キャッシュに関連するローカル・キャッシュ・コントローラは、ソフトウェア・プログラム領域内の偽共有を許可する。偽共有とは、少なくとも２つの異なるローカル・キャッシュ・メモリ内の同じキャッシュ・ライン・アドレスの異なる部分を更新することを意味する。
【００２１】
以下、図３〜図５を参照して、偽共有を許可する一実施形態を詳述する。ローカル・キャッシュ内のキャッシュ・ラインへの書き込み動作が発生するときには、対応するローカル・キャッシュ・コントローラは、当該ローカル・キャッシュ内の対応するキャッシュ・ライン３３０の偽共有ビット（図３の偽共有ビット３００）をセットする。一実施形態では、全てのローカル・キャッシュ・コントローラは、全てのローカル・キャッシュをスヌープ(即ち、モニタ）する。従って、単一のローカル・キャッシュへの書き込み動作が発生するとき、他のローカル・キャッシュ・コントローラは、例えば、スヌーピングを通して、当該書き込み動作の発生を検出し且つ他のローカル・キャッシュ内の対応するキャッシュ・ラインの対応する偽共有ビットをセットする。従って、一実施形態では、ローカル・キャッシュ内の更新は、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化しない。並列コンピュータ・システム７００が偽共有を許可するので、他のプロセッサは、その後に同じキャッシュ・ラインの異なる部分に書き込みを行うことができる。また、同じキャッシュ・ラインへのこの後続の書き込みは、他のローカル・キャッシュ内の同じキャッシュ・ラインを無効化しない。偽共有を許可することにより、並列コンピュータ・システム７００は、ローカル・キャッシュへの書き込み動作が発生する都度の、キャッシュ・ラインを無効化するためのローカル・キャッシュ間の通信オーバーヘッドを減少させることができる。
【００２２】
図１に戻って説明を続ける。ステップ１３０では、コンパイラ７６０は、各プロセッサがデータ従属性を含まないソフトウェア・プログラム領域の実行を完了する、プログラム・コード内の位置を決定する。例えば、図２では、コンパイラ７６０は、例えば、各プロセッサに関連するループ出口条件を評価することにより、各プロセッサがソフトウェア・プログラム領域の実行を完了することを決定する。具体的には、コンパイラ７６０は、各プロセッサが並列実行領域（parallel region）を完了するプログラム・コード内の位置（例えば、図２の位置２１０）が、各プロセッサに割り当てられた元のループ反復「Ｎ−１」のサブセクションの計算を各プロセッサが完了する直後のコードに対応することを決定する。図１のステップ１４０では、プロセッサがデータ従属性を含まないソフトウェア・プログラム領域の実行を完了することを検出するとき、コンパイラ７６０は、当該プロセッサに関連するローカル・キャッシュ・コントローラに対し、偽共有ビットがセットされているその関連するローカル・キャッシュ内のキャッシュ・ラインを無効化することを指示するための特殊命令（又は一連の特殊命令）を挿入する。従って、一実施形態では、並列コンピュータ・システム７００は、バリアに到達するとき又はデータ従属性を含まないソフトウェア・プログラム領域を出るときに、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【００２３】
図３〜図５は、一実施形態における偽共有を例示する。最初に、ローカル・キャッシュ３０５及び他のローカル・キャッシュ３１０は、同じキャッシュ・ライン３３０を有する。図３に示すように、プロセッサ０上のスレッド０は、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０にある第１部分３３５を変更する。また、ローカル・キャッシュ３０５内のこの変更は、共有キャッシュ３１５にライトスルーされる。ローカル・キャッシュ３０５のこの変更を（例えば、スヌーピングを通して）検出するとき、ローカル・キャッシュ３１０のローカル・キャッシュ・コントローラは、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０の偽共有ビット３５０をセットする。偽共有ビット３５０は、プロセッサ又はスレッドがデータ従属性を含まないソフトウェア・プログラム領域を実行する間に、その対応するローカル・キャッシュ内のその対応するキャッシュ・ラインが変更されたことを示す。プロセッサ又はスレッドがデータ従属性を含まないソフトウェア・プログラム領域を実行する間、ローカル・キャッシュ間のコヒーレンス・トラフィック（例えば、キャッシュ・コヒーレンス動作等）は阻止される。任意のローカル・キャッシュは、最新のデータを有さないことがあるが、各ローカル・キャッシュは、それ自体の値を有することができる。図４に示すように、その後暫くして、プロセッサ・コア１上のスレッド１は、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０にある第２部分３４０を変更する。この変更は、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０の偽共有ビット３００をセットすることを含む。また、ローカル・キャッシュ３１０内の変更は、共有キャッシュ３１５にライトスルーされる。ローカル・キャッシュ３０５及び３１０内で行われるこれらのローカル変更は、キャッシュ・コヒーレンス動作（例えば、キャッシュ・ライン３３０を無効化する動作）を呼び出さない。
【００２４】
プロセッサがデータ従属性を含まないソフトウェア・プログラム領域を実行する間、どのローカル・キャッシュも最新のデータを有さない。各ローカル・キャッシュは、それ自体のデータ値を有する。ローカル・キャッシュ・コントローラを備える並列コンピュータ・システム７００は、偽共有を許可する(即ち、同じキャッシュ・ライン内の異なる部分における書き込みを許可する）が、並列コンピュータ・システム７００は、データ従属性を含まないソフトウェア・プログラム領域にある同じキャッシュ・ライン内の同じ部分を対象とする任意の後続書き込みを阻止する。そのようにするため、例えば、コンパイラ７６０に当該同じ部分を対象とする任意の後続書き込みを検出させる。一実施形態では、ローカル・キャッシュ内のキャッシュ・ラインにつき１つの偽共有ビットがある。偽共有ビットは、最初に０にセットされるが、偽共有及び／又はローカル書き込みが発生するときは常に、１にセットされる。他の実施形態では、キャッシュ・ラインにつき２以上の偽共有ビットを設けることができる。例えば、キャッシュ・ラインを幾つかのサブセクタに分割し、各サブセクタをそれ自体の偽共有ビットに関連付けることができる。
【００２５】
図５に示すように、一実施形態では、バリアに到達するとき、各ローカル・キャッシュ・コントローラは、その関連するローカル・キャッシュにおいて、偽共有ビットがセットされているキャッシュ・ラインを無効化する。例えば、ローカル・キャッシュ３０５に関連するローカル・キャッシュ・コントローラは、例えば、対応する無効ビット３２０をセットすることにより、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０を無効化する。同様に、ローカル・キャッシュ３１０に関連するローカル・キャッシュ・コントローラは、例えば、対応する無効ビット３２０をセットすることにより、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０を無効化する。一実施形態では、ローカル・キャッシュ・コントローラは、例えば、共有キャッシュ３１５からデータを取り出すことにより、その関連するローカル・キャッシュ内の無効キャッシュ・ラインを有効化する。というのは、共有キャッシュ３１５は、キャッシュ「ライトスルー」方式に起因して、常に有効データを有するからである。
【００２６】
図６は、一実施形態におけるローカル・キャッシュ内のキャッシュ・ラインの状態を示す状態遷移図４００である。「Ｒ」は、ローカル・キャッシュ内のローカル読み取りイベントを表す。「Ｗ」は、ローカル・キャッシュ内のローカル書き込みイベントを表す。「ｏＲ」は、リモート読み取りイベント（他のスレッドが他のローカル・キャッシュ内の当該キャッシュ・ラインの読み取りを要求していること）を表す。「ｏＷ」は、リモート書き込みイベント（他のスレッドが他のローカル・キャッシュ内の当該キャッシュ・ラインへの書き込みを要求していること）を表す。「ＥＯＰ」は、並列実行領域の終端(即ち、データ従属性を含まないソフトウェア・プログラム領域の終端）を表す。最初に、ローカル・キャッシュ・メモリ内のキャッシュ・ラインは、有効状態４１０(即ち、当該キャッシュ・ライン内の全てのデータが有効であることを表す状態）にあることがある。キャッシュ・ラインが有効であるか否かは、例えば、共有キャッシュ３１５から有効データを取り出すときに対応するローカル・キャッシュ・コントローラによりセットされる、有効ビット（例えば、図３の有効ビット３４５）によって表すことができる。ローカル・キャッシュ内のキャッシュ・ラインが有効状態にある間は、ローカル読み取りイベント、リモート読み取りイベント（ｏＲ）、ローカル書き込みイベント又はＥＯＰが発生しようとも、ローカル・キャッシュ内のキャッシュ・ラインは、如何なる状態遷移も行わない。ローカル書き込みイベントは、常に他のローカル・キャッシュ内の同じキャッシュ・ラインを対象とするリモート書き込みイベント（ｏＷ）を生成する。もし、ローカル・キャッシュ・コントローラが、例えば、スヌーピングを通して、「ｏＷ」イベントの発生を検出すれば、その対応するローカル・キャッシュ・メモリ内の対応する有効キャッシュ・ラインは、偽共有状態４１５(即ち、偽共有ビットがセットされる状態）に遷移する。従来の並列コンピュータ・システムと異なり、リモート書き込みイベント（ｏＷ）は、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化させない。ローカル・キャッシュ内のキャッシュ・ラインの更新は、例えば、偽共有ビット（図３を参照）をセットすることにより、他のローカル・キャッシュ内の対応するキャッシュ・ラインを偽共有状態４１５に遷移させる。
【００２７】
ローカル・キャッシュ内のキャッシュ・ラインが偽共有状態４１５にある間は、ローカル読み取りイベント、他のローカル・キャッシュへの「ｏＷ」イベントを生成するローカル書き込みイベント、リモート読み取りイベント（ｏＲ）又はリモート書き込みイベント（ｏＷ）が発生しようとも、そのローカル・キャッシュ内の当該キャッシュ・ラインは、依然として偽共有状態４１５に留まる。ローカル・キャッシュ内のキャッシュ・ラインが偽共有状態４１５にある間に、「ＥＯＰ」イベントが発生すると（例えば、バリアに到達すると）、そのローカル・キャッシュ内の当該キャッシュ・ラインは、無効状態４０５(即ち、当該キャッシュ・ライン内のデータが無効であることを表す状態）に遷移する。ローカル・キャッシュ内のキャッシュ・ラインが無効状態４０５にある間は、リモート読み取りイベント、リモート書き込みイベント又は「ＥＯＰ」イベントが発生しようとも、依然として無効状態４０５に留まる。ローカル・キャッシュ内のキャッシュ・ラインが無効状態４０５にある間に、他のローカル・キャッシュへのリモート読み取りイベントを引き起こすローカル読み取りイベントが発生するか、又は他のローカル・キャッシュへのリモート書き込みイベントを引き起こすローカル書き込みイベントが発生すると、そのローカル・キャッシュ内の当該キャッシュ・ラインは、例えば、共有キャッシュ３１５から有効データを取り出すことにより、有効状態４１０に遷移する。
【００２８】
図７及び図８は、一実施形態において、偽共有を許可する２つのローカル・キャッシュ内の状態遷移を例示する。この実施形態では、ステージ５００に示すように、所与のキャッシュ・ラインについて、第１ローカル・キャッシュ５２０及び第２ローカル・キャッシュ５２５は、最初に有効状態にある。その後、第１ローカル・キャッシュ５２０に関連する第１プロセッサは、第１ローカル・キャッシュ５２０内のキャッシュ・ラインに書き込み５０５を行う。また、この書き込み５０５は、他のローカル・キャッシュへのリモート書き込みイベントを生成する。従って、ステージ５１０に示すように、書き込み５０５が発生するとき、第１ローカル・キャッシュ５２０は、依然として有効状態に留まるが、第２ローカル・キャッシュ５２５は、偽共有状態に遷移する。書き込み５０５が発生するときに、第２ローカル・キャッシュ５２５が無効状態に遷移しないことに留意されたい。図８のステージ５１５に示すように、「ＥＯＰ」イベント５３０が発生するとき、第１ローカル・キャッシュ５２０は、依然として有効状態に留まるが、第２ローカル・キャッシュ５２５は、無効状態に遷移する。
【００２９】
図９は、ローカル・キャッシュ内の状態遷移を要約するテーブル６００を示す。そのローカル・キャッシュに関連するプロセッサが、非並列実行領域（即ち、複数のプロセッサがプログラムを並列に実行しないソフトウェア・プログラム領域）を実行する間に、ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、有効状態４１０から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、非並列実行領域内でリモート書き込みイベントが発生するときに、有効状態４１０から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、無効状態４０５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、リモート書き込みイベントが発生するときに、無効状態４０５から無効状態４０５に遷移する。
【００３０】
ローカル・キャッシュに関連するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域を実行しており且つ当該ソフトウェア・プログラム領域が他のプロセッサと並列に実行されている間に、当該ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、有効状態４１０から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、非並列実行領域内でリモート書き込みイベントが発生するときに、有効状態４１０から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内でリモート書き込みイベントが発生するときに、有効状態４１０から偽共有事態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、無効状態４０５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、リモート書き込みイベントが発生するときに、無効状態４０５から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生し且つその後にリモート書き込みイベントが発生するときに、無効状態４０５から偽共有状態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、共有キャッシュ３１５から有効データを取り出すことにより、偽共有状態４１５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内でローカル読み取りイベントが発生するときに、偽共有状態４１５から偽共有状態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内で「ＥＯＰ」イベントが発生するときに、偽共有状態４１５から無効状態４０５に遷移する。
【００３１】
一実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行可能であるソフトウェア・プログラム領域では、ローカル読み取りミスが発生すると、対応するプロセッサに共有キャッシュ３１５から有効データを取り出させ、そして他のローカル・キャッシュ内の対応するキャッシュ・ラインを降格させない（例えば、無効化又は偽共有状態に低下させない）。そのソフトウェア・プログラム領域内では、ローカル書き込みミスが発生すると、対応するプロセッサに共有キャッシュ３１５から有効データを取り出させ、そして他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化させない。そのソフトウェア・プログラム領域内では、ローカル読み取りイベントが発生すると、プロセッサに対応するローカル・キャッシュからデータを読み取らせる。そのソフトウェア・プログラム領域内では、ローカル書き込みイベントが発生すると、プロセッサに対応するローカル・キャッシュにデータを書き込ませ、そして共有キャッシュ３１５に同じデータを書き込ませる。そのソフトウェア・プログラム領域では、ローカル・キャッシュ・コントローラは、例えば、既知のＬＲＵ（最長未使用時間）アルゴリズム又は他のキャッシュ・ライン追い出しアルゴリズムに基づいて、そのローカル・キャッシュ内のキャッシュ・ラインを追い出す。
【００３２】
データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域を出る直前に、各ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているそのキャッシュ内のキャッシュ・ラインを無効化する。代替的に、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインに対応する有効データを、共有キャッシュ３１５から取り出すことができる。
【００３３】
一実施形態では、並列コンピュータ・システム７００は、３つの異なるイベントを表す、３つの異なるフラグ・ビット（図示せず）を利用する。第１フラグ・ビットは、データ従属性を含まず且つ複数のプロセッサによって並列に実行可能であるソフトウェア・プログラム領域の始端を表す。コンパイラ７６０は、ソフトウェア・プログラム領域がデータ従属性を含まず且つ複数のプロセッサによって並列に実行可能であることを決定するときに、この第１フラグ・ビットをセットすることができる。第２フラグ・ビットは、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域の終端を表す。コンパイラ７６０は、プロセッサ又はスレッドがそのソフトウェア・プログラム領域を出ることを決定するときに、この第２フラグ・ビットをセットすることができる。第３のフラグ・ビット(即ち、偽共有ビット）は、偽共有状態への遷移を表す。ローカル・キャッシュ内の１キャッシュ・ラインにつき１ビットの偽共有ビットを設けることができる。偽共有が発生するとき、ローカル・キャッシュ・コントローラは、そのローカル・キャッシュの対応するキャッシュ・ラインのこの偽共有ビットをセットすることができる。
【００３４】
一実施形態では、ローカル・キャッシュ・コントローラは、その対応するローカル・キャッシュの状態を表すための専用ビットを使用する代わりに、２ビット以上を使用して幾つかの状態を表すことができる。例えば、図６の３つの状態を表すためには、第１ビットを使用してキャッシュ・ラインの状態が無効であるか否かを示し、第２ビットを使用してキャッシュ・ラインの状態が有効であるか否かを示し、第３のビットを使用してキャッシュ・ラインの状態が偽共有であるか否かを示すことができる。代替的に、ローカル・キャッシュ・コントローラは、例えば、２ビットを使用することにより、これらの３つの状態を実装することができる。即ち、「００」はキャッシュ・ラインの状態が無効であることを示し、「０１」はキャッシュ・ラインの状態が有効であることを示し、「１０」はキャッシュ・ラインの状態が偽共有であることを示す。従って、一実施形態では、有効/無効/偽共有状態について別個のビットを設けることができる。他の実施形態では、これらの３つの状態は、ローカル・キャッシュ内で追跡中の他のデータと共有される複数ビットの組み合わせによって実装することができる。
【００３５】
一実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域では、ローカル書き込みイベントが発生するときに、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、有効状態に留まる。もし、このキャッシュ・ライン内で偽共有が発生すれば、ソフトウェア・プログラム領域の終端に対応するローカル・キャッシュ内の対応するキャッシュ・ラインを無効化する必要はない。しかし、当該対応するキャッシュ・ライン内で偽共有が発生すれば、例えば、２つの異なるプロセッサがそれらのローカル・キャッシュ内の同じキャッシュ・ラインの異なる部分に対して書き込みを行うならば、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、偽共有状態に遷移する。
【００３６】
他の実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域では、他のローカル・キャッシュへの偽共有イベントを構成するローカル書き込みイベントが発生するときに、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、偽共有状態に遷移する。この実施形態では、当該キャッシュ・ラインにおける後続の偽共有が発生するときに、ローカル書き込みイベントが最初に発生する場合を除き、ローカル・キャッシュ間で当該後続の偽共有の発生を通信する必要はない。この実施形態では、ソフトウェア・プログラム領域の終端において、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているそれらのローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【００３７】
一実施形態では、図１２は、偽共有ビットをセットし且つ偽共有ビットがセットされているキャッシュ・ラインを無効化するための方法ステップを示す。ステップ９００では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する。ステップ９１０では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。しかし、ステップ９２０に示すように、キャッシュ・ラインを更新した後は、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットすることを阻止される。ステップ９３０では、ローカル・キャッシュ・コントローラは、対応するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することをコンパイラ７６０が検出するときに、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインを無効化する。しかし、ステップ９４０に示すように、対応するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達するときに、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化しない。
【００３８】
他の実施形態では、図１３は、偽共有ビットをセットし且つ偽共有ビットがセットされているキャッシュ・ラインを無効化するための方法ステップを示す。ステップ１０００では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する。ステップ１０１０では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。ステップ１０２０では、キャッシュ・ラインを更新した後に、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットする。そのため、ステップ１０３０に示すように、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、対応するキャッシュ・ライン上の後続の偽共有が発生するときに、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は必要とされない。
【００３９】
一実施形態では、データ従属性を含まないソフトウェア・プログラム領域の終端に複数のプロセッサが到達するときに、ローカル・キャッシュ・コントローラは、共有キャッシュ・メモリ３１５から有効データを取り出すことにより、偽共有ビットがセットされているキャッシュ・ラインのうちの幾つか（例えば、１つ、２つ又は３つ）の部分を選択的に更新する。データ従属性を含まないソフトウェア・プログラム領域の終端に対応するプロセッサが到達することをコンパイラ７６０が検出するときに、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているキャッシュ・ラインのうちの幾つか（例えば、残り）の部分を選択的に無効化する。例えば、既知のＬＲＵアルゴリズムを使用することにより、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている最近に使用されたキャッシュ・ラインのための有効データを共有キャッシュ３１５からローカル・キャッシュに取り出す。ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている残りのキャッシュ・ラインを無効化する。これらの残りのキャッシュ・ラインについては、ローカル・キャッシュ・コントローラは、どのような処置を講じる必要もなく、これらの残りのキャッシュ・ラインに関するローカル読み取りイベント又はローカル書き込みイベントが発生するときに、共有キャッシュ３１５から有効データを取り出すことができる。
【００４０】
データ従属性を含むか又は並列に実行できないソフトウェア・プログラム領域では、ローカル・キャッシュ内の有効キャッシュ・ラインへのローカル書き込みは、共有キャッシュ３１５にライトスルーされる。このソフトウェア・プログラム領域内では、共有キャッシュ３１５にライトスルーされている間、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の同じキャッシュ・ラインを無効化する。この無効化を完了し且つライトスルー動作を発行するとき、このローカル書き込みは完了する。
【００４１】
データ従属性を含まず且つ並列に実行可能であるソフトウェア・プログラム領域では、ローカル・キャッシュ内の有効キャッシュ・ラインへのローカル書き込みは、共有キャッシュ３１５にライトスルーされる。このソフトウェア・プログラム領域では、共有キャッシュ３１５にライトスルーされている間、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の同じキャッシュ・ラインを偽共有状態に遷移させる。偽共有状態への遷移を完了し且つライトスルー動作を発行するとき、このローカル書き込みは完了する。
【００４２】
代替的に、偽共有状態への遷移が完了する前又はライトスルー動作が完了する前に、ローカル書き込みを完了することができる。換言すれば、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内のキャッシュ・ラインを更新する場合、第１ローカル・キャッシュ・コントローラが、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する動作を完了する後に、他のローカル・キャッシュ・コントローラのうちの幾つか（例えば、１つ又は２つ等）は、他のローカル・キャッシュ・メモリ内の対応するキャッシュ・ラインの偽共有ビットをセットする。他のローカル・キャッシュ・コントローラは、データ従属性を含まないソフトウェア・プログラム領域を出る前に、他のローカル・キャッシュ・メモリ内の対応するキャッシュ・ラインの偽共有ビットのセッティングを完了する。この方式を実装するために、特定の一連のステップが実行される。即ち、各スレッドは、（１）データ従属性を含まないソフトウェア・プログラム領域を開始し、（２）そのローカル・キャッシュ・コントローラがそのキャッシュ・ラインを更新する後に他の幾つかのローカル・キャッシュ・コントローラが対応するキャッシュ・ラインの偽共有ビットをセットすることができるように計算を実行し、（３）当該並列実行領域の計算を完了し、（４）そのローカル・キャッシュ・コントローラから生じる全ての偽共有通知が完了した(即ち、他の全てのキャッシュ・コントローラが、このスレッドの計算に起因して偽共有が生じた全ての対応するキャッシュ・ラインを通知された）ことを保証し、（５）このソフトウェア・プログラム領域に参加する全てのスレッドが当該ソフトウェア・プログラム領域の終端に到達したとき、同期バリアを実行し、（６）並列実行領域の終了動作を実行する。この一連の動作（１）〜（６）を使用すると、並列実行領域の終了動作を実行するとき、データ従属性を含まない当該並列実行領域に参加する任意のスレッドによる偽共有の保留中通知が存在しないことが保証される。動作（４）を実装するために、ローカル・キャッシュ・コントローラは、当該ローカル・キャッシュ・コントローラによる他の任意のキャッシュ・コントローラへの任意の保留中通知を追跡し、対応するキャッシュ・ラインに関連する偽共有ビットをセットしようと試みる。
【００４３】
一実施形態では、並列コンピュータ・システム７００は、全てのローカル・キャッシュ及び共有キャッシュ３１５を制御するために、中央ディレクトリ又はスヌーピング技術を使用する。スヌーピング技術は、各ローカル・キャッシュ・コントローラが全てのプロセッサに関連する全てのローカル・キャッシュをモニタするように実装されたシステムを表す。従って、ローカル書き込みイベントが発生するとき、スヌーピング技術を使用することにより、ローカル・キャッシュ・コントローラは、全てのローカル書き込みイベントの発生を検出することができる。中央ディレクトリは、そのデータが有効である１つのキャッシュＩＤに対応する、１つのタグ・フィールドを有することができる。このタグ・フィールドに記述されているローカル・キャッシュが有効データを有するのに対し、他のローカル・キャッシュ内の対応するキャッシュ・ラインは偽共有状態にあることがある。対応するキャッシュ・ライン上の偽共有がその後に発生するときに、並列コンピュータ・システム７００は、このタグ・フィールドを使用し、例えば、有効キャッシュ・ラインの偽共有ビットをセットすることにより、当該有効キャッシュ・ラインを偽共有状態に移行させることができる。換言すれば、並列コンピュータ・システム７００は、このタグ・フィールドに基づいて、有効キャッシュ・ラインのみの状態を変更させる。代替的に、各ローカル・キャッシュ内の各キャッシュ・ラインは、そのデータが有効であるか否かを示す、有効ビットを有する。偽共有イベントが発生するとき、並列コンピュータ・システム７００は、有効ビットがセットされているキャッシュ・ラインのみの状態を変更させる。例えば、並列コンピュータ・システム７００は、これらのキャッシュ・ラインの有効ビットをオフに転じ且つこれらのキャッシュ・ラインの偽共有ビットをセットする。
【００４４】
本発明の諸側面は、システム、方法又はコンピュータ・プログラムとして具体化することができる。従って、本発明の諸側面は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）又はソフトウェア及びハードウェア要素の両方を含む実施形態の形式を取ることができ、これらの全てを一般に「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本発明の諸側面は、コンピュータ可読プログラム・コードを１つ以上のコンピュータ可読媒体内に具体化した、コンピュータ・プログラムの形式を取ることができる。
【００４５】
１つ以上のコンピュータ可読媒体の任意の組み合わせを利用することができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。例えば、コンピュータ可読ストレージ媒体は、電子、磁気、光学、電磁気、赤外線、半導体システム、装置若しくはデバイス、又はこれらの任意の適切な組み合わせとすることができる。コンピュータ可読ストレージ媒体の特定の例は、１つ以上の線を有する電気接続、フレキシブル・ディスク、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、読み取り専用ＣＤ−ＲＯＭ、光ストレージ装置、磁気ストレージ装置、又はこれらの任意の適切な組み合わせとすることができる。本明細書の文脈では、コンピュータ可読ストレージ媒体は、命令を実行するシステム、装置又はデバイスに関連して又はこれらによって使用するためのプログラムを保持又は格納する、任意の有形的媒体とすることができる。
【００４６】
コンピュータ可読信号媒体は、伝搬されるデータ信号の形式を有することもあるが、その場合には、ベースバンド内に又は搬送波の一部として、コンピュータ可読プログラム・コードを具体化することができる。かかる伝搬される信号は、電磁気、光学、又はこれらの任意の適切な組み合わせ等を含む、種々の形式のうち任意の形式を取る。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、命令を実行するシステム、装置又はデバイスに関連して又はこれらによって使用するためのプログラムを通信し、伝搬し、移送する、任意のコンピュータ可読媒体とすることができる。
【００４７】
コンピュータ可読媒体上に具体化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦ、又はこれらの任意の適切な組み合わせ等を含む、適切な任意の媒体を使用して伝送することができる。
【００４８】
本発明の諸側面に従った動作を実施するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のようなオブジェクト指向プログラミング言語及び「Ｃ」プログラミング言語又は同様のプログラミング言語のような通常の手続き的プログラミング言語を含む、１つ以上のプログラミング言語の任意の組み合わせで書くことができる。プログラム・コードは、独立のソフトウェア・パッケージとしてユーザ・コンピュータ上で完全に実行することができ、その一部をユーザ・コンピュータ上で且つ他の一部をリモート・コンピュータ上で実行することができ、又はリモート・コンピュータ若しくはサーバ上で完全に実行することができる。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通してユーザ・コンピュータに接続することができ、或いはその接続を（例えば、インターネット・サービス・プロバイダを使用するインターネットを通して）外部コンピュータに行うことができる。
【００４９】
以上では、本発明の実施形態に従った、方法、装置（システム）及びコンピュータ・プログラムのフローチャート又はブロック図を参照して、本発明の諸側面を説明した。フローチャート又はブロック図の各ブロック、複数ブロックの組み合わせは、コンピュータ・プログラム命令によって実装することができる。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサに提供すると、当該コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサを介して実行される諸命令は、フローチャート又はブロック図のブロックで指定された機能／行為を実装するための手段を作成する。また、これらのコンピュータ・プログラム命令をコンピュータ可読媒体内に格納すると、当該コンピュータ可読媒体内に格納された諸命令が、フローチャート又はブロック図のブロックで指定された機能／行為を実装するための諸命令を含む製品を生産することを目的として、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスに対し特定の態様で機能するように指示することができる。
【００５０】
また、これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスにロードすると、当該コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイス上で実行される諸命令が、フローチャート又はブロック図のブロックで指定された機能／行為を実装するためのプロセスを提供することを目的として、一のコンピュータ実装プロセスを生成するように当該コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイス上で一連の動作ステップを実行させることができる。
【００５１】
諸図面のうちフローチャート及びブロック図は、本発明の種々の実施形態に従った、システム、方法及びコンピュータ・プログラムの可能な実装のアーキテクチャ、機能性及び動作を示す。この点に関連して、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための１つ以上の動作可能命令から成る、モジュール、セグメント又はコード部分を表すことがある点に留意されたい。また、幾つかの代替的実装では、ブロック内に表記された機能を図面に示した順序とは異なる順序で実施することができる点にも留意されたい。例えば、特定の機能性に依存して、連続的に示した２つのブロックを実質的に並列に実施したり、これらのブロックを反対の順序で実施することができる。さらに、ブロック図又はフローチャートの各ブロック及び複数ブロックの組み合わせは、指定された機能又は行為を実行する専用のハードウェア・ベースのシステム又は専用ハードウェア及びコンピュータ命令の組み合わせによって実装することができる点にも留意されたい。
【符号の説明】
【００５２】
３００、３５０・・・偽共有ビット」
３０５、３１０・・・ローカル・キャッシュ
３１５・・・共有キャッシュ
３３０・・・キャッシュ・ライン
３３５・・・キャッシュ・ライン３３０にある第１部分
３４５・・・有効ビット
４０５・・・無効状態
４１０・・・有効状態
４１５・・・偽共有状態
７０５、７１０、７１５・・・プロセッサ
７２０・・・共有キャッシュ
７２２・・・キャッシュ・コントローラ
７３０、７３５、７４０・・・ローカル・キャッシュ
７４５、７５０、７５５・・・ローカル・キャッシュ・コントローラ
７６０・・・コンパイラ
【技術分野】
【０００１】
本発明は、並列コンピュータ・システムに係り、さらに詳細に説明すれば、並列コンピュータ・システム内で動作するキャッシュ・コヒーレンス・プロトコルに係る。
【背景技術】
【０００２】
従来の並列コンピュータ・システムは、一度に２つ以上のスレッド又はプロセッサによって同じキャッシュ・ライン・アドレスを更新することを許可しない。もし、プロセッサが関連するローカル・キャッシュ・メモリ装置(以下「ローカル・キャッシュ」と略記）内のキャッシュ・ラインを更新することを望んでいれば、従来の並列コンピュータ・システムは、先ず、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化しなければならない。従って、キャッシュ・コヒーレント機構は、ローカル・キャッシュを更新するように（例えば、ローカル・キャッシュ内のキャッシュ・ラインを無効化するように）、コンピュータ・システム内で実装される。従って、従来の並列コンピュータ・システム内の２つ以上の別個のスレッド又はプロセッサは、ローカル・キャッシュ間でキャッシュ・コヒーレンス動作を実行する場合、同じキャッシュ・ライン・アドレスを同時に更新することができない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
２つ以上の別個のスレッド又はプロセッサによってアクセスされるときに同じキャッシュ・ライン・アドレスの同時的な更新を阻止するために、従来の並列コンピュータ・システムは、ローカル・キャッシュ間のより頻繁な通信（例えば、他のローカル・キャッシュへの無効化通知のブロードキャスト）を必要とし、ローカル・キャッシュ内のキャッシュ・ラインを頻繁に無効化する。
【課題を解決するための手段】
【０００４】
本明細書は、複数のプロセッサ及び少なくとも１つの共有キャッシュ・メモリ装置(以下「共有キャッシュ」と略記）を備える、並列コンピュータ・システムの性能を改良するための装置、方法及びコンピュータ・プログラムを開示する。各プロセッサは、少なくとも１つのローカル・キャッシュ（例えば、Ｌ１キャッシュ）を含む。
【０００５】
一側面では、並列コンピュータ・システムの性能を改良するための装置を提供する。本装置は、複数のプロセッサを備え、各プロセッサは、ローカル・キャッシュを有する。各プロセッサは、データ従属性（data dependency）を含まないソフトウェア・プログラム領域のプログラム・コードを実行する。各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するハードウェア・ローカル・キャッシュ・コントローラ(以下「ローカル・キャッシュ・コントローラ」と略記）に関連する。第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラは、プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有（false sharing）の発生を検出し且つ第２プロセッサによる第１キャッシュ・ラインの偽共有を許可する。第１キャッシュ・ラインの偽共有は、第１ローカル・キャッシュ・コントローラによって第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新するときに発生する。
【０００６】
他の側面では、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットする。
【０００７】
他の側面では、第２ローカル・キャッシュ・コントローラが第２ローカル・キャッシュ内の第１キャッシュ・ラインの第２部分を更新するとき、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットし、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、第２ローカル・キャッシュ・コントローラは、第２ローカル・キャッシュ内の第１キャッシュ・ラインに対応する偽共有ビットをセットする。
【０００８】
他の側面では、複数のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラ及び第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている第１ローカル・キャッシュ及び第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【０００９】
他の側面では、ローカル・キャッシュへの任意の書き込みが、複数のプロセッサによって共有される共有キャッシュにライトスルーされる。
【００１０】
他の側面では、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される。
【００１１】
他の側面では、第１キャッシュ・コントローラが第１ローカル・キャッシュ内の第１キャッシュ・ラインの第１部分を更新するとき、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に、当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない。
【００１２】
他の側面では、複数のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内の第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。
【００１３】
他の側面では、２つ以上のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する。
【００１４】
他の側面では、２つ以上のプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することに応答して、第１ローカル・キャッシュ・コントローラは、共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する。
【００１５】
他の側面では、偽共有の発生を検出するために、第１ローカル・キャッシュ・コントローラ及び第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する。
【発明の効果】
【００１６】
本発明は、並列コンピュータ・システムにおいて偽共有を許可することにより、ローカル・キャッシュへの書き込み動作が発生する都度の、キャッシュ・ラインを無効化するためのローカル・キャッシュ間の通信オーバーヘッドを減少させることができる。
【図面の簡単な説明】
【００１７】
【図１】一実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【図２】一実施形態に従った、データ従属性を含まないソフトウェア・プログラム領域を例示する図である。
【図３】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図４】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図５】一実施形態に従った、偽共有を許可するインスタンスを示す図である。
【図６】一実施形態に従った、偽共有を許可する状態図である。
【図７】一実施形態に従った、状態遷移を例示する図である。
【図８】一実施形態に従った、状態遷移を例示する図である。
【図９】一実施形態に従った、状態遷移を要約するテーブルである。
【図１０】一実施形態に従った、図１及び図１２〜図１３に示すフローチャートを実装するための並列コンピュータ・システムを例示する図である。
【図１１】一実施形態に従った、フラグ・ビットを示す図である。
【図１２】一実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【図１３】他の実施形態に従った、並列コンピュータ・システムの性能を改良するための方法ステップを示すフローチャートである。
【発明を実施するための形態】
【００１８】
図１０は、複数のプロセッサ７０５〜７１５（例えば、IBM(R)PowerPC(R)プロセッサ）及び共有キャッシュ７２０を備える、一実施形態に従った並列コンピュータ・システム７００を示す。各プロセッサは、ローカル・キャッシュ、例えば、プロセッサ７０５内のローカル・キャッシュ７３０、プロセッサ７１０内のローカル・キャッシュ７３５及びプロセッサ７１５内のローカル・キャッシュ７４０を含む。また、各プロセッサは、ローカル・キャッシュに関連するローカル・キャッシュ・コントローラを備える。ローカル・キャッシュ・コントローラは、ローカル・キャッシュ・メモリの読み取り及び書き込み動作を制御する。例えば、プロセッサ７０５に関連するローカル・キャッシュ・コントローラ７４５は、例えば、ローカル・キャッシュ７３０内のキャッシュ・ラインを無効化するためのフラグ・ビットをセットすることにより、ローカル・キャッシュ７３０を制御する。同様に、ローカル・キャッシュ・コントローラ７５０は、ローカル・キャッシュ７３５を制御し、ローカル・キャッシュ・コントローラ７５５は、ローカル・キャッシュ７４０を制御する。任意のローカル・キャッシュ・メモリ内の任意の更新は、例えば、バス又はネットワーク７２５を介して、共有キャッシュ７２０にライトスルーされる。また、共有キャッシュ７２０は、共有キャッシュ７２０を制御するキャッシュ・コントローラ７２２を含む。コンパイラ７６０は、高水準のプログラミング・コードを機械コードに変換するために設けられる。
【００１９】
並列コンピュータ・システム７００は、その性能を改良するために図１の方法ステップを実施する。図１のステップ１００では、ソフトウェア・プログラム領域（例えば、図２に示すソフトウェア・ループ２００）に入るときに、コンパイラ７６０は、当該ソフトウェア・プログラム領域がデータ従属性を含むか否かを決定する。コンパイラ７６０は、当該ソフトウェア・プログラムのどの部分を並列に実行可能であるかを知っている。なぜなら、ユーザが当該ソフトウェア・プログラムの特定のサブセットを並列に実行するように明示的に要求するか、又はコンパイラ７６０が対応するプログラム・コードを分析し且つ当該ソフトウェア・プログラムの特定のサブセットを並列に実行可能であると決定したからである。一旦、コンパイラ７６０が、当該プログラム・コードの一部を並列に実行可能であることを知ると、コンパイラ７６０は、並列タスク(即ち、複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域）の作成を扱うランタイム・ライブラリへの機能呼び出しを挿入する。コンパイラ７６０は、これらの並列タスクが開始する位置及び終了する位置に特殊命令を挿入する。一実施形態では、コンパイラ７６０は、並列に実行すべきソフトウェア・プログラム領域を作成する、ランタイム・ライブラリを呼び出す。従って、ランタイム・ライブラリは、ソフトウェア・プログラム領域を実行する直前に特殊命令を呼び出すとともに、ソフトウェア・プログラム領域を並列に実行した直後に特殊命令を呼び出す。他の実施形態では、コンパイラ７６０は、並列に実行されるソフトウェア・プログラム領域の最初の命令が１つの特殊命令であり、並列に実行されるソフトウェア・プログラム領域の最後の命令が他の特殊命令であるように、並列に実行すべきプログラム・コードを装備化（instrument）する。例えば、ソフトウェア・ループ２００がデータ従属性を含むか否かを決定するために、コンパイラ７６０は、ソフトウェア・ループ２００内の先行するソフトウェア・プログラム・ラインの出力がソフトウェア・ループ２００内の後続するソフトウェア・プログラム・ラインの入力として使用されるか否かを評価する。図２のソフトウェア・ループ２００において、アレイ「ｂ」内の２つの別個の要素が同じデータ値を含んでいなければ、データ従属性は存在しない。なぜなら、先行するループ反復の出力は、後続するループ反復の入力として使用されないからである。さらに、コンパイラ７６０は、例えば、図２のソフトウェア・ループ２００のループ出口条件に基づいて、データ従属性を含まないソフトウェア・プログラム領域の開始及び終了境界を決定する。図１のステップ１１０では、コンパイルの後、ソフトウェア・プログラム領域がデータ従属性を含まないことをコンパイラ７６０が決定することに応答して、全て又は一部のプロセッサは、データ従属性を含まないソフトウェア・プログラム領域を並列に実行する。例えば、少なくとも２つの異なるプロセッサが、図２のソフトウェア・ループ２００を実行する。もし、ソフトウェア・プログラム領域内にデータ従属性があれば、単一のプロセッサが、データ従属性を含むソフトウェア・プログラム領域を実行することができる。データ従属性を含まないソフトウェア・プログラム領域を並列に実行する間、各プロセッサは、そのローカル・キャッシュを変更することができる。しかし、本実施形態によれば、各プロセッサがバリア(即ち、全ての参加プロセッサが到達しなければならないポイントであって、そのポイントの後にだけ、各プロセッサがその後続の実行を継続することができる）に到達するまで、ローカル・キャッシュ内の変更を他のローカル・キャッシュが観察する必要はない。
【００２０】
図１のステップ１２０に示すように、全て又は一部のプロセッサが、データ従属性を含まないソフトウェア・プログラム領域を並列に実行することを開始するとき、各プロセッサのローカル・キャッシュに関連するローカル・キャッシュ・コントローラは、ソフトウェア・プログラム領域内の偽共有を許可する。偽共有とは、少なくとも２つの異なるローカル・キャッシュ・メモリ内の同じキャッシュ・ライン・アドレスの異なる部分を更新することを意味する。
【００２１】
以下、図３〜図５を参照して、偽共有を許可する一実施形態を詳述する。ローカル・キャッシュ内のキャッシュ・ラインへの書き込み動作が発生するときには、対応するローカル・キャッシュ・コントローラは、当該ローカル・キャッシュ内の対応するキャッシュ・ライン３３０の偽共有ビット（図３の偽共有ビット３００）をセットする。一実施形態では、全てのローカル・キャッシュ・コントローラは、全てのローカル・キャッシュをスヌープ(即ち、モニタ）する。従って、単一のローカル・キャッシュへの書き込み動作が発生するとき、他のローカル・キャッシュ・コントローラは、例えば、スヌーピングを通して、当該書き込み動作の発生を検出し且つ他のローカル・キャッシュ内の対応するキャッシュ・ラインの対応する偽共有ビットをセットする。従って、一実施形態では、ローカル・キャッシュ内の更新は、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化しない。並列コンピュータ・システム７００が偽共有を許可するので、他のプロセッサは、その後に同じキャッシュ・ラインの異なる部分に書き込みを行うことができる。また、同じキャッシュ・ラインへのこの後続の書き込みは、他のローカル・キャッシュ内の同じキャッシュ・ラインを無効化しない。偽共有を許可することにより、並列コンピュータ・システム７００は、ローカル・キャッシュへの書き込み動作が発生する都度の、キャッシュ・ラインを無効化するためのローカル・キャッシュ間の通信オーバーヘッドを減少させることができる。
【００２２】
図１に戻って説明を続ける。ステップ１３０では、コンパイラ７６０は、各プロセッサがデータ従属性を含まないソフトウェア・プログラム領域の実行を完了する、プログラム・コード内の位置を決定する。例えば、図２では、コンパイラ７６０は、例えば、各プロセッサに関連するループ出口条件を評価することにより、各プロセッサがソフトウェア・プログラム領域の実行を完了することを決定する。具体的には、コンパイラ７６０は、各プロセッサが並列実行領域（parallel region）を完了するプログラム・コード内の位置（例えば、図２の位置２１０）が、各プロセッサに割り当てられた元のループ反復「Ｎ−１」のサブセクションの計算を各プロセッサが完了する直後のコードに対応することを決定する。図１のステップ１４０では、プロセッサがデータ従属性を含まないソフトウェア・プログラム領域の実行を完了することを検出するとき、コンパイラ７６０は、当該プロセッサに関連するローカル・キャッシュ・コントローラに対し、偽共有ビットがセットされているその関連するローカル・キャッシュ内のキャッシュ・ラインを無効化することを指示するための特殊命令（又は一連の特殊命令）を挿入する。従って、一実施形態では、並列コンピュータ・システム７００は、バリアに到達するとき又はデータ従属性を含まないソフトウェア・プログラム領域を出るときに、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【００２３】
図３〜図５は、一実施形態における偽共有を例示する。最初に、ローカル・キャッシュ３０５及び他のローカル・キャッシュ３１０は、同じキャッシュ・ライン３３０を有する。図３に示すように、プロセッサ０上のスレッド０は、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０にある第１部分３３５を変更する。また、ローカル・キャッシュ３０５内のこの変更は、共有キャッシュ３１５にライトスルーされる。ローカル・キャッシュ３０５のこの変更を（例えば、スヌーピングを通して）検出するとき、ローカル・キャッシュ３１０のローカル・キャッシュ・コントローラは、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０の偽共有ビット３５０をセットする。偽共有ビット３５０は、プロセッサ又はスレッドがデータ従属性を含まないソフトウェア・プログラム領域を実行する間に、その対応するローカル・キャッシュ内のその対応するキャッシュ・ラインが変更されたことを示す。プロセッサ又はスレッドがデータ従属性を含まないソフトウェア・プログラム領域を実行する間、ローカル・キャッシュ間のコヒーレンス・トラフィック（例えば、キャッシュ・コヒーレンス動作等）は阻止される。任意のローカル・キャッシュは、最新のデータを有さないことがあるが、各ローカル・キャッシュは、それ自体の値を有することができる。図４に示すように、その後暫くして、プロセッサ・コア１上のスレッド１は、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０にある第２部分３４０を変更する。この変更は、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０の偽共有ビット３００をセットすることを含む。また、ローカル・キャッシュ３１０内の変更は、共有キャッシュ３１５にライトスルーされる。ローカル・キャッシュ３０５及び３１０内で行われるこれらのローカル変更は、キャッシュ・コヒーレンス動作（例えば、キャッシュ・ライン３３０を無効化する動作）を呼び出さない。
【００２４】
プロセッサがデータ従属性を含まないソフトウェア・プログラム領域を実行する間、どのローカル・キャッシュも最新のデータを有さない。各ローカル・キャッシュは、それ自体のデータ値を有する。ローカル・キャッシュ・コントローラを備える並列コンピュータ・システム７００は、偽共有を許可する(即ち、同じキャッシュ・ライン内の異なる部分における書き込みを許可する）が、並列コンピュータ・システム７００は、データ従属性を含まないソフトウェア・プログラム領域にある同じキャッシュ・ライン内の同じ部分を対象とする任意の後続書き込みを阻止する。そのようにするため、例えば、コンパイラ７６０に当該同じ部分を対象とする任意の後続書き込みを検出させる。一実施形態では、ローカル・キャッシュ内のキャッシュ・ラインにつき１つの偽共有ビットがある。偽共有ビットは、最初に０にセットされるが、偽共有及び／又はローカル書き込みが発生するときは常に、１にセットされる。他の実施形態では、キャッシュ・ラインにつき２以上の偽共有ビットを設けることができる。例えば、キャッシュ・ラインを幾つかのサブセクタに分割し、各サブセクタをそれ自体の偽共有ビットに関連付けることができる。
【００２５】
図５に示すように、一実施形態では、バリアに到達するとき、各ローカル・キャッシュ・コントローラは、その関連するローカル・キャッシュにおいて、偽共有ビットがセットされているキャッシュ・ラインを無効化する。例えば、ローカル・キャッシュ３０５に関連するローカル・キャッシュ・コントローラは、例えば、対応する無効ビット３２０をセットすることにより、ローカル・キャッシュ３０５内のキャッシュ・ライン３３０を無効化する。同様に、ローカル・キャッシュ３１０に関連するローカル・キャッシュ・コントローラは、例えば、対応する無効ビット３２０をセットすることにより、ローカル・キャッシュ３１０内のキャッシュ・ライン３３０を無効化する。一実施形態では、ローカル・キャッシュ・コントローラは、例えば、共有キャッシュ３１５からデータを取り出すことにより、その関連するローカル・キャッシュ内の無効キャッシュ・ラインを有効化する。というのは、共有キャッシュ３１５は、キャッシュ「ライトスルー」方式に起因して、常に有効データを有するからである。
【００２６】
図６は、一実施形態におけるローカル・キャッシュ内のキャッシュ・ラインの状態を示す状態遷移図４００である。「Ｒ」は、ローカル・キャッシュ内のローカル読み取りイベントを表す。「Ｗ」は、ローカル・キャッシュ内のローカル書き込みイベントを表す。「ｏＲ」は、リモート読み取りイベント（他のスレッドが他のローカル・キャッシュ内の当該キャッシュ・ラインの読み取りを要求していること）を表す。「ｏＷ」は、リモート書き込みイベント（他のスレッドが他のローカル・キャッシュ内の当該キャッシュ・ラインへの書き込みを要求していること）を表す。「ＥＯＰ」は、並列実行領域の終端(即ち、データ従属性を含まないソフトウェア・プログラム領域の終端）を表す。最初に、ローカル・キャッシュ・メモリ内のキャッシュ・ラインは、有効状態４１０(即ち、当該キャッシュ・ライン内の全てのデータが有効であることを表す状態）にあることがある。キャッシュ・ラインが有効であるか否かは、例えば、共有キャッシュ３１５から有効データを取り出すときに対応するローカル・キャッシュ・コントローラによりセットされる、有効ビット（例えば、図３の有効ビット３４５）によって表すことができる。ローカル・キャッシュ内のキャッシュ・ラインが有効状態にある間は、ローカル読み取りイベント、リモート読み取りイベント（ｏＲ）、ローカル書き込みイベント又はＥＯＰが発生しようとも、ローカル・キャッシュ内のキャッシュ・ラインは、如何なる状態遷移も行わない。ローカル書き込みイベントは、常に他のローカル・キャッシュ内の同じキャッシュ・ラインを対象とするリモート書き込みイベント（ｏＷ）を生成する。もし、ローカル・キャッシュ・コントローラが、例えば、スヌーピングを通して、「ｏＷ」イベントの発生を検出すれば、その対応するローカル・キャッシュ・メモリ内の対応する有効キャッシュ・ラインは、偽共有状態４１５(即ち、偽共有ビットがセットされる状態）に遷移する。従来の並列コンピュータ・システムと異なり、リモート書き込みイベント（ｏＷ）は、他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化させない。ローカル・キャッシュ内のキャッシュ・ラインの更新は、例えば、偽共有ビット（図３を参照）をセットすることにより、他のローカル・キャッシュ内の対応するキャッシュ・ラインを偽共有状態４１５に遷移させる。
【００２７】
ローカル・キャッシュ内のキャッシュ・ラインが偽共有状態４１５にある間は、ローカル読み取りイベント、他のローカル・キャッシュへの「ｏＷ」イベントを生成するローカル書き込みイベント、リモート読み取りイベント（ｏＲ）又はリモート書き込みイベント（ｏＷ）が発生しようとも、そのローカル・キャッシュ内の当該キャッシュ・ラインは、依然として偽共有状態４１５に留まる。ローカル・キャッシュ内のキャッシュ・ラインが偽共有状態４１５にある間に、「ＥＯＰ」イベントが発生すると（例えば、バリアに到達すると）、そのローカル・キャッシュ内の当該キャッシュ・ラインは、無効状態４０５(即ち、当該キャッシュ・ライン内のデータが無効であることを表す状態）に遷移する。ローカル・キャッシュ内のキャッシュ・ラインが無効状態４０５にある間は、リモート読み取りイベント、リモート書き込みイベント又は「ＥＯＰ」イベントが発生しようとも、依然として無効状態４０５に留まる。ローカル・キャッシュ内のキャッシュ・ラインが無効状態４０５にある間に、他のローカル・キャッシュへのリモート読み取りイベントを引き起こすローカル読み取りイベントが発生するか、又は他のローカル・キャッシュへのリモート書き込みイベントを引き起こすローカル書き込みイベントが発生すると、そのローカル・キャッシュ内の当該キャッシュ・ラインは、例えば、共有キャッシュ３１５から有効データを取り出すことにより、有効状態４１０に遷移する。
【００２８】
図７及び図８は、一実施形態において、偽共有を許可する２つのローカル・キャッシュ内の状態遷移を例示する。この実施形態では、ステージ５００に示すように、所与のキャッシュ・ラインについて、第１ローカル・キャッシュ５２０及び第２ローカル・キャッシュ５２５は、最初に有効状態にある。その後、第１ローカル・キャッシュ５２０に関連する第１プロセッサは、第１ローカル・キャッシュ５２０内のキャッシュ・ラインに書き込み５０５を行う。また、この書き込み５０５は、他のローカル・キャッシュへのリモート書き込みイベントを生成する。従って、ステージ５１０に示すように、書き込み５０５が発生するとき、第１ローカル・キャッシュ５２０は、依然として有効状態に留まるが、第２ローカル・キャッシュ５２５は、偽共有状態に遷移する。書き込み５０５が発生するときに、第２ローカル・キャッシュ５２５が無効状態に遷移しないことに留意されたい。図８のステージ５１５に示すように、「ＥＯＰ」イベント５３０が発生するとき、第１ローカル・キャッシュ５２０は、依然として有効状態に留まるが、第２ローカル・キャッシュ５２５は、無効状態に遷移する。
【００２９】
図９は、ローカル・キャッシュ内の状態遷移を要約するテーブル６００を示す。そのローカル・キャッシュに関連するプロセッサが、非並列実行領域（即ち、複数のプロセッサがプログラムを並列に実行しないソフトウェア・プログラム領域）を実行する間に、ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、有効状態４１０から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、非並列実行領域内でリモート書き込みイベントが発生するときに、有効状態４１０から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、無効状態４０５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、リモート書き込みイベントが発生するときに、無効状態４０５から無効状態４０５に遷移する。
【００３０】
ローカル・キャッシュに関連するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域を実行しており且つ当該ソフトウェア・プログラム領域が他のプロセッサと並列に実行されている間に、当該ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、有効状態４１０から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、非並列実行領域内でリモート書き込みイベントが発生するときに、有効状態４１０から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内でリモート書き込みイベントが発生するときに、有効状態４１０から偽共有事態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生するときに、無効状態４０５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、リモート書き込みイベントが発生するときに、無効状態４０５から無効状態４０５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、ローカル読み取りイベントが発生し且つその後にリモート書き込みイベントが発生するときに、無効状態４０５から偽共有状態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、共有キャッシュ３１５から有効データを取り出すことにより、偽共有状態４１５から有効状態４１０に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内でローカル読み取りイベントが発生するときに、偽共有状態４１５から偽共有状態４１５に遷移する。ローカル・キャッシュ内のキャッシュ・ラインは、例えば、並列に実行されるソフトウェア・プログラム領域内で「ＥＯＰ」イベントが発生するときに、偽共有状態４１５から無効状態４０５に遷移する。
【００３１】
一実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行可能であるソフトウェア・プログラム領域では、ローカル読み取りミスが発生すると、対応するプロセッサに共有キャッシュ３１５から有効データを取り出させ、そして他のローカル・キャッシュ内の対応するキャッシュ・ラインを降格させない（例えば、無効化又は偽共有状態に低下させない）。そのソフトウェア・プログラム領域内では、ローカル書き込みミスが発生すると、対応するプロセッサに共有キャッシュ３１５から有効データを取り出させ、そして他のローカル・キャッシュ内の対応するキャッシュ・ラインを無効化させない。そのソフトウェア・プログラム領域内では、ローカル読み取りイベントが発生すると、プロセッサに対応するローカル・キャッシュからデータを読み取らせる。そのソフトウェア・プログラム領域内では、ローカル書き込みイベントが発生すると、プロセッサに対応するローカル・キャッシュにデータを書き込ませ、そして共有キャッシュ３１５に同じデータを書き込ませる。そのソフトウェア・プログラム領域では、ローカル・キャッシュ・コントローラは、例えば、既知のＬＲＵ（最長未使用時間）アルゴリズム又は他のキャッシュ・ライン追い出しアルゴリズムに基づいて、そのローカル・キャッシュ内のキャッシュ・ラインを追い出す。
【００３２】
データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域を出る直前に、各ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているそのキャッシュ内のキャッシュ・ラインを無効化する。代替的に、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインに対応する有効データを、共有キャッシュ３１５から取り出すことができる。
【００３３】
一実施形態では、並列コンピュータ・システム７００は、３つの異なるイベントを表す、３つの異なるフラグ・ビット（図示せず）を利用する。第１フラグ・ビットは、データ従属性を含まず且つ複数のプロセッサによって並列に実行可能であるソフトウェア・プログラム領域の始端を表す。コンパイラ７６０は、ソフトウェア・プログラム領域がデータ従属性を含まず且つ複数のプロセッサによって並列に実行可能であることを決定するときに、この第１フラグ・ビットをセットすることができる。第２フラグ・ビットは、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域の終端を表す。コンパイラ７６０は、プロセッサ又はスレッドがそのソフトウェア・プログラム領域を出ることを決定するときに、この第２フラグ・ビットをセットすることができる。第３のフラグ・ビット(即ち、偽共有ビット）は、偽共有状態への遷移を表す。ローカル・キャッシュ内の１キャッシュ・ラインにつき１ビットの偽共有ビットを設けることができる。偽共有が発生するとき、ローカル・キャッシュ・コントローラは、そのローカル・キャッシュの対応するキャッシュ・ラインのこの偽共有ビットをセットすることができる。
【００３４】
一実施形態では、ローカル・キャッシュ・コントローラは、その対応するローカル・キャッシュの状態を表すための専用ビットを使用する代わりに、２ビット以上を使用して幾つかの状態を表すことができる。例えば、図６の３つの状態を表すためには、第１ビットを使用してキャッシュ・ラインの状態が無効であるか否かを示し、第２ビットを使用してキャッシュ・ラインの状態が有効であるか否かを示し、第３のビットを使用してキャッシュ・ラインの状態が偽共有であるか否かを示すことができる。代替的に、ローカル・キャッシュ・コントローラは、例えば、２ビットを使用することにより、これらの３つの状態を実装することができる。即ち、「００」はキャッシュ・ラインの状態が無効であることを示し、「０１」はキャッシュ・ラインの状態が有効であることを示し、「１０」はキャッシュ・ラインの状態が偽共有であることを示す。従って、一実施形態では、有効/無効/偽共有状態について別個のビットを設けることができる。他の実施形態では、これらの３つの状態は、ローカル・キャッシュ内で追跡中の他のデータと共有される複数ビットの組み合わせによって実装することができる。
【００３５】
一実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域では、ローカル書き込みイベントが発生するときに、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、有効状態に留まる。もし、このキャッシュ・ライン内で偽共有が発生すれば、ソフトウェア・プログラム領域の終端に対応するローカル・キャッシュ内の対応するキャッシュ・ラインを無効化する必要はない。しかし、当該対応するキャッシュ・ライン内で偽共有が発生すれば、例えば、２つの異なるプロセッサがそれらのローカル・キャッシュ内の同じキャッシュ・ラインの異なる部分に対して書き込みを行うならば、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、偽共有状態に遷移する。
【００３６】
他の実施形態では、データ従属性を含まず且つ複数のプロセッサによって並列に実行されるソフトウェア・プログラム領域では、他のローカル・キャッシュへの偽共有イベントを構成するローカル書き込みイベントが発生するときに、対応するローカル・キャッシュ内の対応するキャッシュ・ラインは、偽共有状態に遷移する。この実施形態では、当該キャッシュ・ラインにおける後続の偽共有が発生するときに、ローカル書き込みイベントが最初に発生する場合を除き、ローカル・キャッシュ間で当該後続の偽共有の発生を通信する必要はない。この実施形態では、ソフトウェア・プログラム領域の終端において、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているそれらのローカル・キャッシュ内のキャッシュ・ラインを無効化する。
【００３７】
一実施形態では、図１２は、偽共有ビットをセットし且つ偽共有ビットがセットされているキャッシュ・ラインを無効化するための方法ステップを示す。ステップ９００では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する。ステップ９１０では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。しかし、ステップ９２０に示すように、キャッシュ・ラインを更新した後は、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットすることを阻止される。ステップ９３０では、ローカル・キャッシュ・コントローラは、対応するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達することをコンパイラ７６０が検出するときに、偽共有ビットがセットされているローカル・キャッシュ内のキャッシュ・ラインを無効化する。しかし、ステップ９４０に示すように、対応するプロセッサがデータ従属性を含まないソフトウェア・プログラム領域の終端に到達するときに、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化しない。
【００３８】
他の実施形態では、図１３は、偽共有ビットをセットし且つ偽共有ビットがセットされているキャッシュ・ラインを無効化するための方法ステップを示す。ステップ１０００では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する。ステップ１０１０では、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする。ステップ１０２０では、キャッシュ・ラインを更新した後に、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、第１ローカル・キャッシュ・コントローラは、第１ローカル・キャッシュの偽共有ビットをセットする。そのため、ステップ１０３０に示すように、データ従属性を含まないソフトウェア・プログラム領域を複数のプロセッサが並列に実行する間に、対応するキャッシュ・ライン上の後続の偽共有が発生するときに、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は必要とされない。
【００３９】
一実施形態では、データ従属性を含まないソフトウェア・プログラム領域の終端に複数のプロセッサが到達するときに、ローカル・キャッシュ・コントローラは、共有キャッシュ・メモリ３１５から有効データを取り出すことにより、偽共有ビットがセットされているキャッシュ・ラインのうちの幾つか（例えば、１つ、２つ又は３つ）の部分を選択的に更新する。データ従属性を含まないソフトウェア・プログラム領域の終端に対応するプロセッサが到達することをコンパイラ７６０が検出するときに、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされているキャッシュ・ラインのうちの幾つか（例えば、残り）の部分を選択的に無効化する。例えば、既知のＬＲＵアルゴリズムを使用することにより、ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている最近に使用されたキャッシュ・ラインのための有効データを共有キャッシュ３１５からローカル・キャッシュに取り出す。ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている残りのキャッシュ・ラインを無効化する。これらの残りのキャッシュ・ラインについては、ローカル・キャッシュ・コントローラは、どのような処置を講じる必要もなく、これらの残りのキャッシュ・ラインに関するローカル読み取りイベント又はローカル書き込みイベントが発生するときに、共有キャッシュ３１５から有効データを取り出すことができる。
【００４０】
データ従属性を含むか又は並列に実行できないソフトウェア・プログラム領域では、ローカル・キャッシュ内の有効キャッシュ・ラインへのローカル書き込みは、共有キャッシュ３１５にライトスルーされる。このソフトウェア・プログラム領域内では、共有キャッシュ３１５にライトスルーされている間、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の同じキャッシュ・ラインを無効化する。この無効化を完了し且つライトスルー動作を発行するとき、このローカル書き込みは完了する。
【００４１】
データ従属性を含まず且つ並列に実行可能であるソフトウェア・プログラム領域では、ローカル・キャッシュ内の有効キャッシュ・ラインへのローカル書き込みは、共有キャッシュ３１５にライトスルーされる。このソフトウェア・プログラム領域では、共有キャッシュ３１５にライトスルーされている間、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の同じキャッシュ・ラインを偽共有状態に遷移させる。偽共有状態への遷移を完了し且つライトスルー動作を発行するとき、このローカル書き込みは完了する。
【００４２】
代替的に、偽共有状態への遷移が完了する前又はライトスルー動作が完了する前に、ローカル書き込みを完了することができる。換言すれば、第１ローカル・キャッシュ・コントローラが第１ローカル・キャッシュ内のキャッシュ・ラインを更新する場合、第１ローカル・キャッシュ・コントローラが、第１ローカル・キャッシュ内のキャッシュ・ラインを更新する動作を完了する後に、他のローカル・キャッシュ・コントローラのうちの幾つか（例えば、１つ又は２つ等）は、他のローカル・キャッシュ・メモリ内の対応するキャッシュ・ラインの偽共有ビットをセットする。他のローカル・キャッシュ・コントローラは、データ従属性を含まないソフトウェア・プログラム領域を出る前に、他のローカル・キャッシュ・メモリ内の対応するキャッシュ・ラインの偽共有ビットのセッティングを完了する。この方式を実装するために、特定の一連のステップが実行される。即ち、各スレッドは、（１）データ従属性を含まないソフトウェア・プログラム領域を開始し、（２）そのローカル・キャッシュ・コントローラがそのキャッシュ・ラインを更新する後に他の幾つかのローカル・キャッシュ・コントローラが対応するキャッシュ・ラインの偽共有ビットをセットすることができるように計算を実行し、（３）当該並列実行領域の計算を完了し、（４）そのローカル・キャッシュ・コントローラから生じる全ての偽共有通知が完了した(即ち、他の全てのキャッシュ・コントローラが、このスレッドの計算に起因して偽共有が生じた全ての対応するキャッシュ・ラインを通知された）ことを保証し、（５）このソフトウェア・プログラム領域に参加する全てのスレッドが当該ソフトウェア・プログラム領域の終端に到達したとき、同期バリアを実行し、（６）並列実行領域の終了動作を実行する。この一連の動作（１）〜（６）を使用すると、並列実行領域の終了動作を実行するとき、データ従属性を含まない当該並列実行領域に参加する任意のスレッドによる偽共有の保留中通知が存在しないことが保証される。動作（４）を実装するために、ローカル・キャッシュ・コントローラは、当該ローカル・キャッシュ・コントローラによる他の任意のキャッシュ・コントローラへの任意の保留中通知を追跡し、対応するキャッシュ・ラインに関連する偽共有ビットをセットしようと試みる。
【００４３】
一実施形態では、並列コンピュータ・システム７００は、全てのローカル・キャッシュ及び共有キャッシュ３１５を制御するために、中央ディレクトリ又はスヌーピング技術を使用する。スヌーピング技術は、各ローカル・キャッシュ・コントローラが全てのプロセッサに関連する全てのローカル・キャッシュをモニタするように実装されたシステムを表す。従って、ローカル書き込みイベントが発生するとき、スヌーピング技術を使用することにより、ローカル・キャッシュ・コントローラは、全てのローカル書き込みイベントの発生を検出することができる。中央ディレクトリは、そのデータが有効である１つのキャッシュＩＤに対応する、１つのタグ・フィールドを有することができる。このタグ・フィールドに記述されているローカル・キャッシュが有効データを有するのに対し、他のローカル・キャッシュ内の対応するキャッシュ・ラインは偽共有状態にあることがある。対応するキャッシュ・ライン上の偽共有がその後に発生するときに、並列コンピュータ・システム７００は、このタグ・フィールドを使用し、例えば、有効キャッシュ・ラインの偽共有ビットをセットすることにより、当該有効キャッシュ・ラインを偽共有状態に移行させることができる。換言すれば、並列コンピュータ・システム７００は、このタグ・フィールドに基づいて、有効キャッシュ・ラインのみの状態を変更させる。代替的に、各ローカル・キャッシュ内の各キャッシュ・ラインは、そのデータが有効であるか否かを示す、有効ビットを有する。偽共有イベントが発生するとき、並列コンピュータ・システム７００は、有効ビットがセットされているキャッシュ・ラインのみの状態を変更させる。例えば、並列コンピュータ・システム７００は、これらのキャッシュ・ラインの有効ビットをオフに転じ且つこれらのキャッシュ・ラインの偽共有ビットをセットする。
【００４４】
本発明の諸側面は、システム、方法又はコンピュータ・プログラムとして具体化することができる。従って、本発明の諸側面は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）又はソフトウェア及びハードウェア要素の両方を含む実施形態の形式を取ることができ、これらの全てを一般に「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本発明の諸側面は、コンピュータ可読プログラム・コードを１つ以上のコンピュータ可読媒体内に具体化した、コンピュータ・プログラムの形式を取ることができる。
【００４５】
１つ以上のコンピュータ可読媒体の任意の組み合わせを利用することができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。例えば、コンピュータ可読ストレージ媒体は、電子、磁気、光学、電磁気、赤外線、半導体システム、装置若しくはデバイス、又はこれらの任意の適切な組み合わせとすることができる。コンピュータ可読ストレージ媒体の特定の例は、１つ以上の線を有する電気接続、フレキシブル・ディスク、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、読み取り専用ＣＤ−ＲＯＭ、光ストレージ装置、磁気ストレージ装置、又はこれらの任意の適切な組み合わせとすることができる。本明細書の文脈では、コンピュータ可読ストレージ媒体は、命令を実行するシステム、装置又はデバイスに関連して又はこれらによって使用するためのプログラムを保持又は格納する、任意の有形的媒体とすることができる。
【００４６】
コンピュータ可読信号媒体は、伝搬されるデータ信号の形式を有することもあるが、その場合には、ベースバンド内に又は搬送波の一部として、コンピュータ可読プログラム・コードを具体化することができる。かかる伝搬される信号は、電磁気、光学、又はこれらの任意の適切な組み合わせ等を含む、種々の形式のうち任意の形式を取る。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、命令を実行するシステム、装置又はデバイスに関連して又はこれらによって使用するためのプログラムを通信し、伝搬し、移送する、任意のコンピュータ可読媒体とすることができる。
【００４７】
コンピュータ可読媒体上に具体化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦ、又はこれらの任意の適切な組み合わせ等を含む、適切な任意の媒体を使用して伝送することができる。
【００４８】
本発明の諸側面に従った動作を実施するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のようなオブジェクト指向プログラミング言語及び「Ｃ」プログラミング言語又は同様のプログラミング言語のような通常の手続き的プログラミング言語を含む、１つ以上のプログラミング言語の任意の組み合わせで書くことができる。プログラム・コードは、独立のソフトウェア・パッケージとしてユーザ・コンピュータ上で完全に実行することができ、その一部をユーザ・コンピュータ上で且つ他の一部をリモート・コンピュータ上で実行することができ、又はリモート・コンピュータ若しくはサーバ上で完全に実行することができる。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通してユーザ・コンピュータに接続することができ、或いはその接続を（例えば、インターネット・サービス・プロバイダを使用するインターネットを通して）外部コンピュータに行うことができる。
【００４９】
以上では、本発明の実施形態に従った、方法、装置（システム）及びコンピュータ・プログラムのフローチャート又はブロック図を参照して、本発明の諸側面を説明した。フローチャート又はブロック図の各ブロック、複数ブロックの組み合わせは、コンピュータ・プログラム命令によって実装することができる。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサに提供すると、当該コンピュータ又は他のプログラム可能なデータ処理装置のプロセッサを介して実行される諸命令は、フローチャート又はブロック図のブロックで指定された機能／行為を実装するための手段を作成する。また、これらのコンピュータ・プログラム命令をコンピュータ可読媒体内に格納すると、当該コンピュータ可読媒体内に格納された諸命令が、フローチャート又はブロック図のブロックで指定された機能／行為を実装するための諸命令を含む製品を生産することを目的として、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスに対し特定の態様で機能するように指示することができる。
【００５０】
また、これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイスにロードすると、当該コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイス上で実行される諸命令が、フローチャート又はブロック図のブロックで指定された機能／行為を実装するためのプロセスを提供することを目的として、一のコンピュータ実装プロセスを生成するように当該コンピュータ、他のプログラム可能なデータ処理装置又は他のデバイス上で一連の動作ステップを実行させることができる。
【００５１】
諸図面のうちフローチャート及びブロック図は、本発明の種々の実施形態に従った、システム、方法及びコンピュータ・プログラムの可能な実装のアーキテクチャ、機能性及び動作を示す。この点に関連して、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための１つ以上の動作可能命令から成る、モジュール、セグメント又はコード部分を表すことがある点に留意されたい。また、幾つかの代替的実装では、ブロック内に表記された機能を図面に示した順序とは異なる順序で実施することができる点にも留意されたい。例えば、特定の機能性に依存して、連続的に示した２つのブロックを実質的に並列に実施したり、これらのブロックを反対の順序で実施することができる。さらに、ブロック図又はフローチャートの各ブロック及び複数ブロックの組み合わせは、指定された機能又は行為を実行する専用のハードウェア・ベースのシステム又は専用ハードウェア及びコンピュータ命令の組み合わせによって実装することができる点にも留意されたい。
【符号の説明】
【００５２】
３００、３５０・・・偽共有ビット」
３０５、３１０・・・ローカル・キャッシュ
３１５・・・共有キャッシュ
３３０・・・キャッシュ・ライン
３３５・・・キャッシュ・ライン３３０にある第１部分
３４５・・・有効ビット
４０５・・・無効状態
４１０・・・有効状態
４１５・・・偽共有状態
７０５、７１０、７１５・・・プロセッサ
７２０・・・共有キャッシュ
７２２・・・キャッシュ・コントローラ
７３０、７３５、７４０・・・ローカル・キャッシュ
７４５、７５０、７５５・・・ローカル・キャッシュ・コントローラ
７６０・・・コンパイラ
【特許請求の範囲】
【請求項１】
並列コンピュータ・システムの性能を改良するための装置であって、
複数のプロセッサを備え、
各プロセッサは、ローカル・キャッシュを有し、各プロセッサは、データ従属性を含まないソフトウェア・プログラム領域のプログラム・コードを実行し、各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するローカル・キャッシュ・コントローラに関連しており、
前記プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有の発生を検出し且つ前記第２プロセッサによる前記第１キャッシュ・ラインの前記偽共有を許可するための、第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラを備え、
前記第１キャッシュ・ラインの前記偽共有は、前記第１ローカル・キャッシュ・コントローラによって前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの第２部分を更新するときに発生する、装置。
【請求項２】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１記載の装置。
【請求項３】
前記第２ローカル・キャッシュ・コントローラが前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第２部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットし、前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第２ローカル・キャッシュ・コントローラは、前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１記載の装置。
【請求項４】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている前記第１ローカル・キャッシュ及び前記第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する、請求項３記載の装置。
【請求項５】
データ従属性を含まない前記ソフトウェア・プログラム領域は、データ従属性を含まない少なくとも１つのループを含む、請求項１記載の装置。
【請求項６】
前記ループがデータ従属性を含まないか否かを決定するために、コンパイラは、先行する反復の出力が後続する反復の入力として使用されるか否かを評価する、請求項５記載の装置。
【請求項７】
ローカル・キャッシュへの任意の書き込みが、前記複数のプロセッサによって共有される共有キャッシュにライトスルーされる、請求項１記載の装置。
【請求項８】
前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される、請求項１記載の装置。
【請求項９】
前記第１キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない、請求項１記載の装置。
【請求項１０】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする、請求項４記載の装置。
【請求項１１】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の前記終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する、請求項４記載の装置。
【請求項１２】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する、請求項７記載の装置。
【請求項１３】
前記偽共有の発生を検出するために、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する、請求項１記載の装置。
【請求項１４】
並列コンピュータ・システムの性能を改良するための方法であって、
複数のプロセッサを提供するステップを有し、
各プロセッサは、ローカル・キャッシュを有し、各プロセッサは、データ従属性を含まないソフトウェア・プログラム領域のプログラム・コードを実行し、各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するローカル・キャッシュ・コントローラに関連しており、
第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラによって、前記プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有の発生を検出し且つ前記第２プロセッサによる前記第１キャッシュ・ラインの前記偽共有を許可するステップを有し、
前記第１キャッシュ・ラインの前記偽共有は、前記第１ローカル・キャッシュ・コントローラによって前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの第２部分を更新するときに発生する、方法。
【請求項１５】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１４記載の方法。
【請求項１６】
前記第２ローカル・キャッシュ・コントローラが前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第２部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットし、前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第２ローカル・キャッシュ・コントローラは、前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１４記載の方法。
【請求項１７】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている前記第１ローカル・キャッシュ及び前記第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する、請求項１６記載の方法。
【請求項１８】
ローカル・キャッシュへの任意の書き込みが、前記複数のプロセッサによって共有される共有キャッシュにライトスルーされる、請求項１４記載の方法。
【請求項１９】
前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される、請求項１４記載の方法。
【請求項２０】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない、請求項１４記載の方法。
【請求項２１】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする、請求項１７記載の方法。
【請求項２２】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の前記終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する、請求項１７記載の方法。
【請求項２３】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する、請求項１８記載の方法。
【請求項２４】
偽共有の発生を検出するために、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する、請求項１４記載の方法。
【請求項２５】
請求項１４ないし請求項２４の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【請求項１】
並列コンピュータ・システムの性能を改良するための装置であって、
複数のプロセッサを備え、
各プロセッサは、ローカル・キャッシュを有し、各プロセッサは、データ従属性を含まないソフトウェア・プログラム領域のプログラム・コードを実行し、各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するローカル・キャッシュ・コントローラに関連しており、
前記プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有の発生を検出し且つ前記第２プロセッサによる前記第１キャッシュ・ラインの前記偽共有を許可するための、第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラを備え、
前記第１キャッシュ・ラインの前記偽共有は、前記第１ローカル・キャッシュ・コントローラによって前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの第２部分を更新するときに発生する、装置。
【請求項２】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１記載の装置。
【請求項３】
前記第２ローカル・キャッシュ・コントローラが前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第２部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットし、前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第２ローカル・キャッシュ・コントローラは、前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１記載の装置。
【請求項４】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている前記第１ローカル・キャッシュ及び前記第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する、請求項３記載の装置。
【請求項５】
データ従属性を含まない前記ソフトウェア・プログラム領域は、データ従属性を含まない少なくとも１つのループを含む、請求項１記載の装置。
【請求項６】
前記ループがデータ従属性を含まないか否かを決定するために、コンパイラは、先行する反復の出力が後続する反復の入力として使用されるか否かを評価する、請求項５記載の装置。
【請求項７】
ローカル・キャッシュへの任意の書き込みが、前記複数のプロセッサによって共有される共有キャッシュにライトスルーされる、請求項１記載の装置。
【請求項８】
前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される、請求項１記載の装置。
【請求項９】
前記第１キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない、請求項１記載の装置。
【請求項１０】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする、請求項４記載の装置。
【請求項１１】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の前記終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する、請求項４記載の装置。
【請求項１２】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する、請求項７記載の装置。
【請求項１３】
前記偽共有の発生を検出するために、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する、請求項１記載の装置。
【請求項１４】
並列コンピュータ・システムの性能を改良するための方法であって、
複数のプロセッサを提供するステップを有し、
各プロセッサは、ローカル・キャッシュを有し、各プロセッサは、データ従属性を含まないソフトウェア・プログラム領域のプログラム・コードを実行し、各プロセッサのローカル・キャッシュは、当該ローカル・キャッシュ内のキャッシュ・ラインを更新するローカル・キャッシュ・コントローラに関連しており、
第１プロセッサの第１ローカル・キャッシュに関連する第１ローカル・キャッシュ・コントローラによって、前記プログラム・コードを実行中の第２プロセッサによる第１キャッシュ・ラインの偽共有の発生を検出し且つ前記第２プロセッサによる前記第１キャッシュ・ラインの前記偽共有を許可するステップを有し、
前記第１キャッシュ・ラインの前記偽共有は、前記第１ローカル・キャッシュ・コントローラによって前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの第１部分を更新し、その後に、第２ローカル・キャッシュ・コントローラによって第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの第２部分を更新するときに発生する、方法。
【請求項１５】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１４記載の方法。
【請求項１６】
前記第２ローカル・キャッシュ・コントローラが前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第２部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットし、前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第２ローカル・キャッシュ・コントローラは、前記第２ローカル・キャッシュ内の前記第１キャッシュ・ラインに対応する偽共有ビットをセットする、請求項１４記載の方法。
【請求項１７】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている前記第１ローカル・キャッシュ及び前記第２ローカル・キャッシュ内のキャッシュ・ラインを無効化する、請求項１６記載の方法。
【請求項１８】
ローカル・キャッシュへの任意の書き込みが、前記複数のプロセッサによって共有される共有キャッシュにライトスルーされる、請求項１４記載の方法。
【請求項１９】
前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュの偽共有ビットをセットすることを阻止され、他のローカル・キャッシュ・コントローラは、偽共有ビットがセットされていないローカル・キャッシュ内のキャッシュ・ラインを無効化することを阻止される、請求項１４記載の方法。
【請求項２０】
前記第１ローカル・キャッシュ・コントローラが前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの前記第１部分を更新するとき、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインの偽共有ビットをセットし、他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットし、その後に当該対応するキャッシュ・ラインについて偽共有が発生するときは、ローカル・キャッシュ・メモリ・コントローラ間で更なる通信は行われない、請求項１４記載の方法。
【請求項２１】
前記複数のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記第１ローカル・キャッシュ内の前記第１キャッシュ・ラインを更新する動作を完了し、その後に、１つ以上の他のローカル・キャッシュ・コントローラは、他のローカル・キャッシュ内の対応するキャッシュ・ラインの偽共有ビットをセットする、請求項１７記載の方法。
【請求項２２】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の前記終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に無効化する、請求項１７記載の方法。
【請求項２３】
２つ以上のプロセッサがデータ従属性を含まない前記ソフトウェア・プログラム領域の終端に到達することに応答して、前記第１ローカル・キャッシュ・コントローラは、前記共有キャッシュから有効データを取り出すことにより、偽共有ビットがセットされている１つ以上のキャッシュ・ラインを選択的に更新する、請求項１８記載の方法。
【請求項２４】
偽共有の発生を検出するために、前記第１ローカル・キャッシュ・コントローラ及び前記第２ローカル・キャッシュ・コントローラは、中央ディレクトリ又はスヌーピング技術を使用する、請求項１４記載の方法。
【請求項２５】
請求項１４ないし請求項２４の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１６８９３０（Ｐ２０１２−１６８９３０Ａ）
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願番号】特願２０１２−６１１６（Ｐ２０１２−６１１６）
【出願日】平成２４年１月１６日（２０１２．１．１６）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願日】平成２４年１月１６日（２０１２．１．１６）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]