プロセッサによって実行可能なコードの生成方法、記憶領域の管理方法及びコード生成プログラム
【課題】ソフトウェアによる簡単なコヒーレンシ制御を提供する。
【解決手段】マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを、コンパイラによって生成する方法であって、プロセッサによって実行されるプログラムを解析し、前記プログラムに含まれる各タスクの実行に必要なデータを解析し、前記解析の結果に基づいて、前記プログラムを前記各タスクに分割した場合に、前記分割されたタスクによって使用されるデータの境界がメモリの管理単位と整合するか否かを判定し、前記タスクによって使用されるデータの境界がメモリの管理単位と整合しないと判定された場合、データが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を用いて、当該境界を含む管理単位に格納されたデータを演算するコードを生成することを特徴とするコードの生成方法。
【解決手段】マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを、コンパイラによって生成する方法であって、プロセッサによって実行されるプログラムを解析し、前記プログラムに含まれる各タスクの実行に必要なデータを解析し、前記解析の結果に基づいて、前記プログラムを前記各タスクに分割した場合に、前記分割されたタスクによって使用されるデータの境界がメモリの管理単位と整合するか否かを判定し、前記タスクによって使用されるデータの境界がメモリの管理単位と整合しないと判定された場合、データが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を用いて、当該境界を含む管理単位に格納されたデータを演算するコードを生成することを特徴とするコードの生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセシングエレメントによって構成されるマルチプロセッサにおけるメモリの管理方法に関し、特に、コンパイラが取得した情報に基づいて、共有メモリに格納されたデータの一貫性（コヒーレンシ）を保つように制御する方法に関する。
【背景技術】
【０００２】
複数のプロセシングエレメントを集積したマルチプロセッサが、各マイクロプロセッサメーカによって次々に発表されている。スーパーコンピュータ、サーバ、デスクトップコンピュータ及びＰＣサーバ分野の他、情報家電及び装置組み込みの分野（例えば、携帯電話機、ゲーム機、カーナビゲーションシステム、デジタルテレビ受像機、ＨＤＤ／ＤＶＤレコーダ・プレーヤ等）においても、マイクロプロセッサのマルチコア化の動きが見られる。
【０００３】
マルチプロセッサは、複数のプロセシングエレメント、内部結合網及び集中共有メモリを備え、各プロセシングエレメントは、プロセッサ及びキャッシュメモリを備え、独立に演算処理を行うものである。このような構成のマルチプロセッサは、集中共有メモリを主記憶として使用し、複数のプロセッシングエレメントが、集中共有メモリに格納された同一のデータをアクセスする主記憶共有型プロセッサとして使用される。
【０００４】
このとき、共有データ間のコヒーレンシを保つために、あるプロセッサがキャッシュメモリ上の共有データをアクセスしている場合、他のプロセッサが当該共有データを集中共有メモリからキャッシュメモリへのアクセスを禁止するコヒーレンシ制御が必要となっていた。
【０００５】
ここで、コヒーレンシとは、ある時刻において、メモリのあるアドレスに格納された値を、全てのプロセッサが同一の値としてアクセスできることであり、主記憶共有型マルチプロセッサにおいて、各プロセッサからアクセスされるメモリの内容が同一であることを保証するための制御である。コヒーレンシを保つための機能には、ハードウェアによってメモリアクセスを制御するコヒーレントキャッシュがある。
【０００６】
コヒーレンシ制御において解決しなければならない第１の問題はデータの陳腐化（Ｓｔａｌｅ Ｄａｔａ）であり、第２の問題はフォルスシェアリング（Ｆａｌｓｅ Ｓｈａｒｉｎｇ）である。
【０００７】
図２２は、コヒーレンシ制御における第１の問題点（ステイルデータ）を説明する図である。
【０００８】
まず、グローバル変数ａ、ｂ、ｃが宣言され（２２００）、共有メモリに変数ａ＝０，ｂ＝０，ｃ＝１が格納された（２２０１）。
【０００９】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュメモリに共有データ（ａ＝０、ｂ＝０、ｃ＝１）が格納されており（２２０２）、他のプロセシングエレメント（ＰＥ１）のキャッシュメモリにも同じ共有データが格納されている（２２０３）場合、ＰＥ０で当該共有データが更新（ａ＝０→１）されても、ＰＥ１のキャッシュ上の共有データは更新されていない古いデータ（ａ＝０）である（２２０５）。この状態で、ＰＥ１で当該共有データが更新（ｃ＝ａ）されると、変数ｃは正しいａの値を反映することなく０に更新されてしまう（２２０６）。
【００１０】
このため、コヒーレンシ制御がされていれば、ａ＝１、ｂ＝０、ｃ＝１であるはずの変数が、ａ＝０、ｂ＝０、ｃ＝０となる。このため、ＰＥ０のキャッシュメモリに格納されているデータと、ＰＥ１のキャッシュメモリに格納されているデータとが不一致となる。このため、ＰＥ１が誤った動作をしてしまう。
【００１１】
図２３は、コヒーレンシ制御における第２の問題点（フォルスシェアリング）を説明する図である。
【００１２】
まず、グローバル変数ａ、ｂが宣言され（２３００）、変数ａ＝０、ｂ＝０が共有メモリに格納された（２３０１）。この変数ａ及びｂは、共有メモリの同じキャッシュライン上に格納されている。また、共有メモリは、ライン単位でアクセスされる。
【００１３】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュメモリに格納された共有データが更新（ａ＝０→１）され（２３０２）、他のプロセシングエレメント（ＰＥ１）のキャッシュメモリに格納された共有データが更新（ｂ＝０→２）された（２３０３）。すなわち各プロセッシングエレメントが、同一のライン上に格納された異なる変数を更新した。この場合、ＰＥ０が先に共有メモリにデータを書き戻せば、後にデータを書き戻したＰＥ１のデータが共有メモリに格納される（２３０４）。一方、ＰＥ１が先に共有メモリにデータを書き戻せば、後にデータを書き戻したＰＥ０のデータが共有メモリに格納される（２３０５）。
【００１４】
コヒーレンシ制御がされている場合、共有メモリにはａ＝１、ｂ＝２が格納されるが、コヒーレンシ制御がされない場合、最終的にどのデータが共有メモリに格納されるかは定まらない。すなわち、ライン吐き出しタイミングによりメモリの内容が異なり、いずれにせよプロセッシングエレメントは誤った動作をしてしまう。
【００１５】
このような共有メモリとキャッシュメモリとの間での不一致が生じる問題点を解決するために、各プロセッシングエレメント及び共有資源（内部結合網、共有メモリ等）にコヒーレンシ制御部を設けることによって、メモリに格納されたデータのコヒーレンシを保つ。
【００１６】
具体的には、あるプロセシングエレメント（ＰＥ０）がデータｘを共有メモリから読み出した後に、ＰＥ０がデータｘを共有メモリから読み出して、それを更新し、データｘの所有権を破棄するまで、他のプロセシングエレメント（ＰＥ１）による共有メモリのデータｘへの書き込みは許可されない。
【００１７】
このような所有権制御によって、データの陳腐化（Ｓｔａｌｅ Ｄａｔａ）及びフォルスシェアリング（Ｆａｌｓｅ Ｓｈａｒｉｎｇ）のコヒーレンシ制御の問題を解決することができる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００４−３０３６２号公報
【特許文献２】特開平９−４４４０３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかし、ハードウェアによってメモリアクセスを所有権制御するコヒーレントキャッシュでは、ハードウェアのコストのために、プロセッサ数の増加によって、マルチプロセッサのコストが上昇する。また、ハードウェアによってメモリアクセスを制御することによって、メモリアクセスが遅くなる。
【００２０】
さらに、ハードウェアによるコヒーレンシ制御では、イベント毎に全てのプロセッサ、メモリ及びバス制御機構に信号を送るので、実行時のオーバーヘッドが生じる。このオーバーヘッドは、マルチプロセッサに含まれるプロセッサ数に応じて増加する。このため、プロセッサ数が増加した場合、コヒーレンシ制御のための通信でバスが埋まってしまい、プロセッサの動作を妨げる。
【００２１】
このため、より簡単なハードウェア構成によるコヒーレンシ制御、特にソフトウェアによるコヒーレンシ制御が求められている。
【課題を解決するための手段】
【００２２】
本発明のコンパイラは、プログラムを解析して得られるコントロールフロー及びデータ依存関係の情報を用いて、ソフトウェアによる明示的なキャッシュ操作コードを生成する。また、異なるプロセシングエレメントによって使用される変数が、同じキャッシュラインに載らないように配置する。
【発明の効果】
【００２３】
本発明によれば、ソフトウェアによる制御によって、コヒーレンシ制御のためのハードウェアが不要となり、ハードウェアを簡素化できる。このため、低コストかつ低消費電力のマルチプロセッサを実現できる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態のマルチプロセッサの構成図である。
【図２】本発明の実施の形態のマルチプロセッサのキャッシュメモリの各ラインがとりうる状態を説明する図である。
【図３Ａ】本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【図３Ｂ】本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【図４】本発明の実施の形態のフォルスシェアリングの発生を避ける方法の概要を説明する図である。
【図５Ａ】一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図５Ｂ】一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図６Ａ】本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図６Ｂ】本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図７Ａ】本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図７Ｂ】本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ｂ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ｃ】本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が集中共有メモリに設けられた場合の例を示す。
【図８Ｄ】本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリに設けられた場合の例を示す。
【図９Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図９Ｂ】図９Ａに示す変形例におけるノンキャッシャブル領域が集中共有メモリに設けられた場合の例を示す。
【図９Ｃ】図９Ａに示す変形例におけるノンキャッシャブル領域が分散共有メモリに設けられた場合の例を示す。
【図１０Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１０Ｂ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１１】本発明の第４の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１２Ａ】多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図１２Ｂ】多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図１３Ａ】第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１３Ｂ】第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１４Ａ】第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１４Ｂ】第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１５Ａ】第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１５Ｂ】第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１６】第４の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１７Ａ】本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【図１７Ｂ】本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【図１７Ｃ】本発明の実施の形態のフォルスシェアリングを検出するためのコードの例を説明する図ある。
【図１８】本発明の実施の形態の並列化コンパイラによるソフトウェアコヒーレンシ制御コードを生成する処理の概要を説明する図である。
【図１９】本発明の実施の形態のコンパイラによって実行される処理のフローチャートである。
【図２０Ａ】本発明の実施の形態のフォルスシェアリング回避処理のフローチャートである。
【図２０Ｂ】本発明の実施の形態のフォルスシェアリング回避処理のフローチャートである。
【図２１】本発明の実施の形態のキャッシュ操作指示の挿入処理のフローチャートである。
【図２２】コヒーレンシ制御における第１の問題点（ステイルデータ）を説明する図である。
【図２３】コヒーレンシ制御における第２の問題点（フォルスシェアリング）を説明する図である。
【発明を実施するための形態】
【００２５】
図１は、本発明の実施の形態のマルチプロセッサの構成図である。
【００２６】
本発明の実施形態のマルチプロセッサは、複数のプロセシングエレメント（ＰＥ０、ＰＥ１、…、ＰＥｎ）１００、１１０、１２０、内部結合網１５０、及び集中共有メモリ１６０を備える。
【００２７】
プロセシングエレメント１００は、演算処理をするプロセッサ１０１、データを一時的に格納するキャッシュメモリ１０２、分散共有メモリ（ＤＳＭ）１０３及びデータ転送コントローラを備え、独立に動作する。
【００２８】
プロセッサ１０１は、整数演算及び浮動小数点演算が可能なものであればよく、その機能は特に限定されない。例えば、データのロード及びストアのアーキテクチャが単純なシングルイッシューＲＩＳＣアーキテクチャのＣＰＵを用いてもよい。また、スーパースカラプロセッサ、ＶＬＩＷプロセッサ等も用いてもよい。
【００２９】
キャッシュメモリ１０２は、集中共有メモリ１６０からプロセッサ１０１によって読み込まれたデータを一時的に格納するメモリである。プロセッサ１０１は、キャッシュメモリ１０２に格納されたデータを用いて演算処理をする。プロセッサ１０１による演算処理が終了すると、キャッシュメモリ１０２に格納されたデータは集中共有メモリ１６０に書き戻される。このキャッシュメモリ１０２と集中共有メモリ１６０との間では、ライン毎にデータが読み書きされる。このラインは、キャッシュメモリ１０２に格納されたデータの管理単位である。
【００３０】
なお、プロセッシングエレメント１００は、キャッシュメモリ１０２を二次キャッシュとして使用し、キャッシュメモリ１０２の他に一次キャッシュを備えてもよい。この場合、一次キャッシュと二次キャッシュ（キャッシュメモリ１０２）とは、コヒーレンシ制御がされてもよい。すなわち、本発明の実施の形態のマルチプロセッサでは、主記憶として機能する集中共有メモリ１６０と最外側のキャッシュメモリ１０２との間でデータの一致を保つコヒーレンシ機能を有さない。
【００３１】
分散共有メモリ１０３は、格納されたデータを他のプロセシングエレメントから直接読み書きすることができるメモリである。なお、分散共有メモリ１０３がデュアルポートメモリで構成されていると、プロセッサ１０１とデータ転送コントローラとが競合することなく分散共有メモリにアクセスすることができる。なお、分散共有メモリ１０３は、本実施の形態のマルチプロセッサに必須の構成ではない。
【００３２】
データ転送コントローラは、プロセッシングエレメントに備わるメモリに格納されたデータをプロセッシングエレメント間で転送する。
【００３３】
さらに、プロセシングエレメント１００は、図示した構成の他、ローカルプログラムメモリ、ローカルデータメモリ、ネットワークインターフェイス及び電力制御レジスタを備えてもよい。
【００３４】
なお、プロセシングエレメント１１０、１２０も、プロセシングエレメント１００と同じ構成を有する。
【００３５】
内部結合網１５０は、既存の接続技術（クロスバースイッチ、バス、マルチステージネットワーク等）によって実現され、複数のプロセシングエレメント１００等及び集中共有メモリ１６０を接続する。
【００３６】
集中共有メモリ１６０（ＣＳＭ）は、システム中の全プロセシングエレメント１００等によって共有されるデータが格納される主記憶として機能し、各プロセシングエレメント１００等からアクセス可能なメモリである。
【００３７】
なお、本実施の形態のマルチプロセッサは、キャッシュメモリ１０２等と集中共有メモリ１６０との間でデータの一致を保つための、ハードウェアによるコヒーレンシ機能を有さない。
【００３８】
＜ステイルデータの解決＞
まず、第１の課題であるステイルデータの発生を避ける方法について説明する。
【００３９】
本発明の実施の形態のマルチプロセッサは、前述したように、キャッシュメモリ１０２等と集中共有メモリ１６０との間でデータの一致を保つための、ハードウェアによるコヒーレンシ機能を有さない。このため、あるプロセッシングエレメントがキャッシュメモリ上でデータを更新した場合、このデータ更新は他のプロセッシングエレメントに通知されない。また、更新されたデータが書き戻されるまで、更新されたデータは集中共有メモリ１６０にも反映されない。
【００４０】
このため、本発明の実施の形態のコンパイラは、プログラムを解析した結果（データコントロールフロー、データ依存関係）に基づいて、ソフトウェアによる明示的なキャッシュ操作コードを生成する。
【００４１】
生成されるキャッシュ操作コードは、その命令が実行されるプロセッシングエレメントのキャッシュメモリに格納されたデータを操作する命令だけであり、ハードウェアによるコヒーレンシプロトコルにおけるキャッシュ操作要求のような、他プロセッシングエレメントのキャッシュメモリに格納されたデータの状態を操作する命令ではない。生成されるキャッシュ操作コードは、ライトバック、セルフインバリデート、パージの３種類がある。
【００４２】
ライトバック（ｗｒｉｔｅｂａｃｋ）は、キャッシュメモリ１０２に格納されたデータを集中共有メモリ１６０に書き戻すための命令である。キャッシュメモリ１０２上でデータが更新され、集中共有メモリ１６０上の対応するアドレスに格納されるデータと異なる場合、ラインの状態はダーティとなり、キャッシュメモリ１０２に格納されたデータを、集中共有メモリ１６０に書き戻す必要がある。
【００４３】
なお、キャッシュメモリ１０２のラインリプレースに伴うデータの書き戻し（ａｕｔｏ−ｗｒｉｔｅｂａｃｋ）によっても、集中共有メモリ１６０へデータが書き戻される。
【００４４】
セルフインバリデート（ｓｅｌｆ−ｉｎｖａｌｉｄａｔｅ）は、キャッシュメモリ１０２のラインを無効化するための命令である。セルフインバリデートされ、インバリデート状態になったデータは、キャッシュメモリに格納されていても、再度集中共有メモリ１６０から読み込むまで使用することができない。
【００４５】
パージ（ｐｕｒｇｅ）は、キャッシュメモリ１０２のラインに格納されたデータを書き戻した（ライトバック）後、セルフインバリデート実行するための命令である。
【００４６】
また、各プロセッシングエレメントで実行されるタスク間で通信が発生する箇所にキャッシュ操作コードが挿入される。
【００４７】
さらに、コンパイラは、異なるプロセッシングエレメントが同一ラインのデータを保持している場合、異なるプロセッシングエレメントに格納された同一ラインのデータを同時に更新しないように制御する。
【００４８】
図２は、本発明の実施の形態のマルチプロセッサのキャッシュメモリ１０２の各ラインがとりうる状態を説明する図である。
【００４９】
キャッシュメモリ１０２は、ライン毎に、Ｍｏｄｉｆｉｅｄ、Ｖａｌｉｄ、Ｓｔａｌｅ、Ｉｎｖａｌｉｄの４状態をとる。
【００５０】
Ｍｏｄｉｆｉｅｄは、キャッシュメモリ１０２に格納されたデータが更新されたダーティデータで、集中共有メモリ１６０上の対応するアドレスに格納されるデータと異なっている状態である。この場合、ライトバックによって、キャッシュメモリ１０２に格納されたデータを集中共有メモリ１６０に書き戻す必要がある。
【００５１】
Ｖａｌｉｄは、キャッシュメモリ１０２に格納されたデータが集中共有メモリ１６０上の対応するアドレスに格納されるデータと一致しているクリーン状態である。
【００５２】
Ｓｔａｌｅは、キャッシュメモリ１０２に格納されたデータと同期すべきデータが他のプロセッシングエレメントによって書き換えられたが、まだ当該更新データは集中共有メモリ１６０に書き戻されていないため、当該キャッシュデータは集中共有メモリ１６０上の対応するアドレスに格納されるデータとが一致しているクリーン状態である。
【００５３】
Ｉｎｖａｌｉｄは、キャッシュメモリ１０２に格納されたデータと一致していないデータである可能性がある状態である。
【００５４】
前述した４状態は、キャッシュメモリ１０２へのアクセス、及び、キャッシュ操作によって遷移する。
【００５５】
キャッシュメモリ１０２へのアクセスには、プロセッサ１０１による集中共有メモリ１６０からのデータの読み込み（ｒｅａｄ）、プロセッサ１０１によるキャッシュメモリ１０２へのデータの書き込み（ｗｒｉｔｅ）がある。
【００５６】
本発明の実施の形態のコンパイラは、複数のプロセッシングエレメントのキャッシュメモリに格納された同一ラインのデータが、同時にＭｏｄｉｆｉｅｄとならないように制御する。また、本実施の形態のコンパイラは、Ｓｔａｌｅのデータを読み書きしないように制御する。
【００５７】
図３Ａ及び図３Ｂは、本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【００５８】
本発明の実施の形態のコンパイラは、プロセッシングエレメントをまたがるデータ依存が存在する場合、データ依存のエッジでデータを同期する。例えば、コンパイラがプログラムの解析によって検出すべきデータ依存のエッジは、フロー依存によって生じるｄｅｆ−ｕｓｅの関係である。
【００５９】
例えば、図３Ａに示すように、ＰＥ０がタスクブロック１（ＳＢ１）で変数Ａを定義した（３００）後、ＰＥ１がタスクブロック３（ＳＢ３）で変数Ａを使用する場合、図３Ｂに示すように、ＰＥ０による変数Ａの更新によって、ＰＥ１は変数Ａが格納されているラインの状態をｉｎｖａｌｉｄａｔｅへ変更する（３０２）。また、ＰＥ０が変数Ａを集中共有メモリに書き戻した（３０１）後に、ＰＥ１が変数Ａを使用する。
【００６０】
より具体的には、コンパイラは、ＰＥ０が更新した変数Ａを、他のプロセッシングエレメント（ＰＥ１）で使用する前に、ライトバック命令（３０１）を挿入する。この場合、次に自プロセシングエレメント（ＰＥ０）が変数Ａが使用する場合は、ライトバック命令を挿入せず、他のプロセッシングエレメント（ＰＥ１）が変数Ａを使用する前にライトバック命令を挿入すればよい。
【００６１】
さらに、コンパイラは、フラグ変数を用いたプロセッシングエレメント間のデータ同期のために、同期の送信側（ＰＥ０）は、同期フラグ変数（ｓｙｎｃ＿ｆｌｇ）に同期を示す値を書き込む命令（３０２）、及び、その同期フラグ変数が格納されているキャッシュメモリのラインを集中共有メモリに書き戻す命令（３０３）を挿入する。
【００６２】
一方、ＰＥ１について、コンパイラは、他のプロセシングエレメント（ＰＥ０）によって更新された変数Ａを使用する前にセルフインバリデート命令（３０４）を挿入する。なお、セルフインバリデート命令（３０４）が挿入される箇所（セルフインバリデートのタイミング）は、変数Ａを使用する直前が望ましい。
【００６３】
さらに、コンパイラは、同期フラグ変数（ｓｙｎｃ＿ｆｌｇ）のインバリデート及び読み込みを繰り返し、同期フラグ変数の値が同期を示す値に更新されるまでビジーウェイト状態で待機する命令（３０５）を挿入する。
【００６４】
ＰＥ１は、変数Ａがインバリデートされており、キャッシュメモリ上の変数Ａを使用できないため、変数Ａを集中共有メモリ１６０からキャッシュメモリにロードし、ＰＥ０で更新された変数Ａを取得する。
【００６５】
以上、ｄｅｆ−ｕｓｅの関係について説明したが、出力依存によって生じるｄｅｆ−ｄｅｆの関係、ｕｓｅ−ｄｅｆによる逆依存の関係、ｕｓｅ−ｕｓｅによる入力依存の関係でも同様のことが生じうる。
【００６６】
このように、本実施の形態のコンパイラは、タスク間のフロー依存及び出力依存を解析した結果に応じてキャッシュ操作命令を挿入するので、コヒーレンシ制御をすることなく、ステイルデータを消費することがない。
【００６７】
＜フォルスシェアリングの解決＞
次に、第２の課題であるフォルスシェアリングの発生を避けるための方法について説明する。
【００６８】
図４は、本発明の実施の形態のフォルスシェアリングの発生を避ける方法の概要を説明する図である。
【００６９】
本実施の形態では、各プロセシングエレメントによって使用される変数が、同じキャッシュラインに載らないように、各変数がキャッシュラインの先頭に配置される（アラインメント）を行う。なお、変数のアライメントは、配列変数の宣言において指定しても、別に設定ファイル等に記述してもよい。
【００７０】
まず、図２３で前述したと同様に、グローバル変数ａ、ｂが宣言され（４００）、変数ａ＝０、ｂ＝０が集中共有メモリ１６０に格納された。しかし、本発明の実施の形態では、図２３で前述したと異なり、宣言されたグローバル変数ａ、ｂは集中共有メモリ１６０のキャッシュラインの先頭に配置されるので、異なるライン上に格納される。
【００７１】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュ上の共有データが更新（ａ＝０→１）され（４０１）、他のプロセシングエレメント（ＰＥ１）のキャッシュ上の共有データが更新（ｂ＝０→２）された（４０２）。しかし、各プロセッシングエレメントは、異なるライン上に格納された異なる変数を更新したので、各プロセシングエレメントがいかなるタイミングでキャッシュメモリに格納されたデータを集中共有メモリ１６０に書き戻しても（４０４、４０５）、正しいデータ（ａ＝１、ｂ＝２）が集中共有メモリ１６０格納される。
【００７２】
次に、一次元配列を扱う場合について説明する。
【００７３】
図５Ａ及び図５Ｂは、一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【００７４】
まず、図５Ｂに示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（５００）。本実施の形態ではキャッシュメモリの１ラインが１６バイトであり、１ラインに４個の変数が格納できる場合を考える。このため、図５Ａに示すように、キャッシュメモリの第１ライン５１１にはａ［０］からａ［３］が格納されており、第２ライン５１２にはａ［４］からａ［７］が格納されており、第５ライン５１５にはａ［１６］からａ［１９］が格納されている。
【００７５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ１０２上で処理し（５０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８≦ｉ＜３６）をキャッシュメモリ１１２上で処理し（５０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻す。
【００７６】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。ＰＥ０によって処理されるａ［１６］及びａ［１７］と、ＰＥ１によって処理されるａ［１８］及びａ［１９］とが第５ライン５１５上に存在することから、このライン上でＰＥ０によるアクセスとＰＥ１によるアクセスとが競合しフォルスシェアリングが発生する。
【００７７】
図６Ａ及び図６Ｂは、本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００７８】
第１の実施の形態の方法では、図６Ａに示すように、グローバル変数ａの各要素を集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置することによって、各要素を異なるラインに配置する。このため、キャッシュラインの境界で処理が分割される。
【００７９】
まず、図６Ｂに示すように、グローバル変数ａが宣言され、変数ａに含まれる３６個の配列変数の各要素が集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（６００）。
【００８０】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）を処理し（６０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８≦ｉ＜３６）を処理し（６０２）、ＰＥ０及びＰＥ１が処理の結果を集中共有メモリ１６０に書き戻す。しかし、図５Ａを用いて前述した場合と異なり、図６Ｂに示すように、ＰＥ０とＰＥ１とは集中共有メモリ１６０の同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００８１】
なお、本実施の形態では、１ラインは４個の変数が格納できる容量を有するが、１ラインに１個の変数しか格納されていないので、キャッシュメモリの利用効率が低下する。このため、本実施の形態は、配列変数の要素の数が少ない場合に有効である。また、同一のプロセッシングエレメントが、配列変数の異なる添字の要素（ａ（ｉ）、ａ（ｉ＋１））にアクセスするような間接メモリアクセスをする場合にも有効である。
【００８２】
図７Ａ及び図７Ｂは、本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００８３】
フォルスシェアリングは、図５Ａを用いて前述したように、異なるプロセッシングエレメントによって処理されたデータがキャッシュメモリの１ライン上に格納されることによって発生する。このため、本実施の形態では、図７Ａに示すように、キャッシュメモリのラインの境界によって、各プロセッシングエレメントが処理するデータを分け、複数のプロセッシングエレメントによって処理されるデータがキャッシュメモリの１ライン上に格納されないようにする。
【００８４】
まず、図７Ｂに示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（７００）。
【００８５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１６）を処理し（７０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１６≦ｉ＜３６）を処理する（７０２）。その後、ＰＥ０が処理の結果をキャッシュメモリ１０２から集中共有メモリ１６０に書き戻し、ＰＥ１が処理の結果をキャッシュメモリ１１２から集中共有メモリ１６０に書き戻す。
【００８６】
本実施の形態では、１ラインは４個の変数が格納できる容量を有するので、各プロセッシングエレメントが、キャッシュラインサイズである４の倍数の配列変数の要素を処理するようにしている。このため、図７Ａに示すように、ＰＥ０のアクセス範囲とＰＥ１のアクセス範囲とはキャッシュメモリのラインの境界で分けられ、ＰＥ０とＰＥ１とはキャッシュメモリの同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００８７】
なお、本実施の形態ではＰＥ０に１６個、ＰＥ１に２０個の配列変数の処理を割り当てたが、キャッシュラインサイズ（１ラインに格納できる配列変数の要素数）の倍数になるように分ければ、ＰＥ０に２０個、ＰＥ１に１６個の配列変数の処理を割り当てても、よい。また、各プロセッシングエレメントの処理能力の比に従って数の配列変数の処理を割り当ててもよい。
【００８８】
なお、本実施の形態では、キャッシュラインサイズ、配列変数の要素の数及びプロセッシングエレメントの数によっては、各プロセッシングエレメントに割り当てられる配列変数の要素の数が等しくならず、プロセッシングエレメントの処理負荷の不均衡が生じる場合がある。このため、本実施の形態は、配列サイズが十分に大きく、不均衡が配列サイズに比べて無視できるほど小さい場合に有効である。
【００８９】
図８Ａ及び図８Ｂは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００９０】
第３の実施の形態では、処理の境界においてノンキャッシャブル領域を用いることによって、フォルスシェアリングの発生を避ける。
【００９１】
まず、図８Ｂに示すように、グローバル変数ａ及び変数ｎｃｂｕｆが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置され、配列変数４個のサイズの変数ｎｃｂｕｆがノンキャッシャブル領域に設けられる（８００）。
【００９２】
ノンキャッシャブル領域とは、プロセッシングエレメントが当該領域に格納されたデータをメモリから読み込んだ場合に、当該読み込まれたデータを各プロセッシングエレメントのキャッシュメモリにロードしないで使用される領域である。ノンキャッシャブル領域は、メモリの領域（アドレス）又は特定の変数をノンキャッシャブルに指定することによって、通常のキャッシャブル領域と区別される。このノンキャッシャブルの指定は、所定の設定ファイルによって予め定めておいてもよいし、変数を宣言する命令によって定めてもよい。
【００９３】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８、１９）をｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いてノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【００９４】
ＰＥ０は、その後又は処理８０３と並行して、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。このデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【００９５】
その後、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻す。
【００９６】
このように、第３の実施の形態では、図８Ａに示すように、ＰＥ１がノンキャッシャブルバッファを用いて演算した結果をＰＥ０のキャッシュメモリの変数に反映する。すなわち、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、一方のプロセシングエレメント（ＰＥ１）はキャッシュメモリ内に設けられたノンキャッシャブル領域に当該ライン上のデータを格納し、他方のプロセシングエレメント（ＰＥ０）はノンキャッシャブル領域のデータを集中共有メモリに格納するので、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００９７】
なお、ライン８１１〜８１４に格納されたデータはＰＥ０のみによって使用され、ライン８１１〜８１４に格納されたデータはＰＥ０のみによって使用されるので、ライン８１１〜８１４及びライン８１６〜８１９をキャッシュメモリ上でローカライズしてもよい。ローカライズされたデータは、主記憶に書き戻されず、次にＰＥ０が使用するまでキャッシュメモリ上に保持される。同様に、ライン８１１〜８１４に格納されるべきデータ及びライン８１６〜８１９に格納されるべきデータをローカルメモリに格納してもよい。
【００９８】
すなわち、第５ライン８１５のみがキャッシュメモリ上（キャッシャブル領域上）にあればよく、そのほかの領域（ライン８１１〜８１４、ライン８１６〜８１９）はキャッシャブル領域上に存在していなくてもよい。
【００９９】
なお、本実施の形態ではメモリ上にノンキャッシャブル領域を設ける必要があるが、ノンキャッシャブル領域は、集中共有メモリ、分散共有メモリ等の何れのメモリに設けてもよい。また、本実施の形態では、ノンキャッシャブル領域からキャッシュメモリにデータをコピーする処理のオーバーヘッドが生じる。しかし、ノンキャッシャブルのバッファとして分散共有メモリを利用することによって、低オーバーヘッドでデータの転送を実現することができる。
【０１００】
この第３の実施の形態の方法は、前述した第２の実施の形態の方法によっては分割が不可能な場合や、配列が拡張できない場合に有効である。
【０１０１】
図８Ｃは、本発明の第３の実施の形態においてノンキャッシャブル領域が集中共有メモリ１６０に設けられた場合の例を示す。図８Ｃに示す例では、集中共有メモリ１６０の一部の領域がノンキャッシャブル領域に指定されている。
【０１０２】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を、ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いて集中共有メモリ１６０に設けられたノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【０１０３】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を集中共有メモリ１６０のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１０４】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１０５】
図８Ｄは、本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリ１０３に設けられた場合の例を示す。図８Ｄに示す例では、分散共有メモリ１０３の一部の領域がノンキャッシャブル領域に指定されている。
【０１０６】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を、ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いてＰＥ０の分散共有メモリ１０３に設けられたノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【０１０７】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を分散共有メモリ１０３のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１０８】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１０９】
図９Ａは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１１０】
図９Ａで説明する変形例は、前述した例と異なり、各プロセシングエレメントが自己のメモリ上で演算し、その演算結果をノンキャッシャブル領域に転送することによって、フォルスシェアリングの発生を避ける。このため、他のメモリ、プロセシングエレメント等へのアクセスを減らし、処理を高速化することができる。
【０１１１】
まず、図９Ａに示すように、グローバル変数ａ及び変数ｎｃｂｕｆ及びｌｏｃａｌｂｕｆ＿ｐｅ１が宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される。また、配列変数４個のサイズの変数ｎｃｂｕｆがノンキャッシャブル領域に設けられ、配列変数４個のサイズの変数ｌｏｃａｌｂｕｆ＿ｐｅ１がノンキャッシャブル領域に設けられる（９００）。なお、変数Ｌｏｃａｌｂｕｆ＿ｐｅ１はプロセッシングエレメント（ＰＥ１）１１０のみで使用されるので、ローカル変数でよい。
【０１１２】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）をｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）をｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１１３】
ＰＥ０は、その後又は処理９０４と並行して、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。このデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１１４】
その後、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻す。
【０１１５】
図９Ｂは、本発明の第３の実施の形態においてノンキャッシャブル領域が集中共有メモリ１６０に設けられ、演算領域（ｌｏｃａｌｂｕｆ＿ｐｅ１）がＰＥ１のメモリに設けられた場合の例を示す。この演算領域が設けられるＰＥ１のメモリは、ローカルメモリでも、分散共有メモリでも、キャッシュメモリでもよい。
【０１１６】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）を、ＰＥ１のメモリ上に設けられたｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３））を集中共有メモリ１６０に設けられたノンキャッシャブル領域上のｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１１７】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を集中共有メモリ１６０のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１１８】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１１９】
図９Ｃは、本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリ１０３に設けられ、演算領域（ｌｏｃａｌｂｕｆ＿ｐｅ１）がＰＥ１のメモリに設けられた場合の例を示す。図９Ｃに示す例では、分散共有メモリ１０３の一部の領域がノンキャッシャブル領域に指定されている。また、演算領域が設けられるＰＥ１のメモリは、ローカルメモリでも、分散共有メモリでも、キャッシュメモリでもよい。
【０１２０】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）を、ＰＥ１のメモリ上に設けられたｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３））をＰＥ０の分散共有メモリ１０３に設けられたノンキャッシャブル領域上のｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１２１】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を分散共有メモリ１０３のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１２２】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１２３】
図９Ａ〜図９Ｃに記載した変形例によると、自プロセシングエレメント上のメモリで境界部分の変数を演算するので、バスを介した他のプロセシングエレメントやメモリへのデータの転送が減り、処理を高速化することができる。
【０１２４】
図１０Ａ及び図１０Ｂは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１２５】
まず、図１０Ｂに示すように、グローバル変数ａ、ｎｃｂｕｆ＿ｐｅ０、ｎｃｂｕｆ＿ｐｅ１が宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置され、配列変数４個分のサイズの変数ｎｃｂｕｆ＿ｐｅ０及び変数ｎｃｂｕｆ＿ｐｅ１がノンキャッシャブル領域に設けられる（１０００）。この変数ｎｃｂｕｆ＿ｐｅ０は、ＰＥ０の分散共有メモリに配置され、変数ｎｃｂｕｆ＿ｐｅ１は、ＰＥ１の分散共有メモリに配置される。
【０１２６】
本実施の形態では、プロセッシングエレメント（ＰＥ０）１００がｉ＝０からｉ＝１７の変数ａを処理し、プロセッシングエレメント（ＰＥ１）１１０がｉ＝１８からｉ＝３５の変数ａを処理する。
【０１２７】
具体的には、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１６）をキャッシュメモリ上で処理した（１００１）。また、ＰＥ０が変数ａ［ｉ］（ｉ＝１６、１７）を分散共有メモリ上のｎｃｂｕｆ＿ｐｅ０において処理し、処理の結果をＰＥ１の分散共有メモリのｎｃｂｕｆ＿ｐｅ１に書き込む（１００２）。
【０１２８】
これと並行して又は前後して、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を分散共有メモリ上のｎｃｂｕｆ＿ｐｅ１において処理し、処理の結果をＰＥ０の分散共有メモリのｎｃｂｕｆ＿ｐｅ０に書き込む（１００４）。また、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（１００５）。
【０１２９】
また、ＰＥ０は、変数ｎｃｂｕｆ＿ｐｅ０［ｉ］（０≦ｉ＜４）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（１６≦ｉ＜２０）に書き込む（１００３）。なお、処理の結果のｎｃｂｕｆ＿ｐｅ０への書き込み（１００４）からｎｃｂｕｆ＿ｐｅ０のａ［ｉ］への書き込み（１００３）へのデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がｎｃｂｕｆ＿ｐｅ０［ｉ］に格納されている。このため、ステップ１００３では、ＰＥ０によって処理された変数ａ［ｉ］（ｉ＝１６、１７）及びＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０のキャッシュメモリ上に書き込まれる。
【０１３０】
その後、ＰＥ０及びＰＥ１が処理の結果を集中共有メモリ１６０に書き戻す。しかし、図５Ａを用いて前述した場合と異なり、ＰＥ０とＰＥ１との境界領域の変数ａ［ｉ］（１６≦ｉ＜２０）には同じデータが格納されているので、何れのプロセッシングエレメントがデータを書き戻しても、集中共有メモリ１６０に格納されるデータは変わらない。
【０１３１】
すなわち、第３の実施の形態では、各プロセシングエレメントは、ＰＥ０がアクセスする集中共有メモリの領域とＰＥ１がアクセスする集中共有メモリの領域との境界部分は、分散共有メモリ上のデータを使用して計算をする。
【０１３２】
なお、ＰＥ０のｎｃｂｕｆ＿ｐｅ０と、ＰＥ１のｎｃｂｕｆ＿ｐｅ１とは、互いに書き込まれることによって、同じ値が格納されている。このため、ＰＥ０が、変数ｎｃｂｕｆ＿ｐｅ０を集中共有メモリに書き込んだ場合、変数ｎｃｂｕｆ＿ｐｅ１のｉ＝２、３も集中共有メモリに書き込まれており、ｎｃｂｕｆ＿ｐｅ０又はｎｃｂｕｆ＿ｐｅ１のいずれかが集中共有メモリに書き込まれることによって、他方のデータも集中共有メモリに書き込まれる。
【０１３３】
このように、第３の実施の形態では、図１０Ａに示すように、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、両方のプロセシングエレメントの分散共有メモリ内に設けられたノンキャッシャブル領域に当該ライン上のデータを格納し、両方のノンキャッシャブル領域のデータをコピーすることによって、両ノンキャッシャブル領域のデータが一致し、何れのデータを書き戻しても、フォルスシェアリングは発生しない。
【０１３４】
なお、本実施の形態では分散共有メモリ上にノンキャッシャブル領域を設ける必要があり、分散共有メモリ間でデータをコピーする処理のオーバーヘッドが生じる。
【０１３５】
図１１は、本発明の第４の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１３６】
第４の実施の形態では、ローカル変数を用いることによって、フォルスシェアリングの発生を避ける。
【０１３７】
まず、図１１に示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１１００）。
【０１３８】
その後、プロセシングエレメント０（ＰＥ０）１００が、ローカル変数ｌｏｃａｌ＿ａを宣言し（１１０１）、変数ａ［ｉ］（０≦ｉ＜１８）をローカル変数において処理し（１１０２）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］（０≦ｉ＜１８）をグルーバル変数ａ［ｉ］（０≦ｉ＜１８）へ書き込む（１１０３）。
【０１３９】
これと並行して又は前後して、プロセシングエレメント１（ＰＥ１）１１０が、ローカル変数ｌｏｃａｌ＿ａを宣言し（１１０４）、変数ａ［ｉ］（１８≦ｉ＜３６）をローカル変数において処理し（１１０５）、ｉ＝１８からｉ＝３５のローカル変数ｌｏｃａｌ＿ａ［ｉ］（１８≦ｉ＜３６）をグルーバル変数ａ［ｉ］（１８≦ｉ＜３６）に書き込む（１１０６）。
【０１４０】
ステップ１１０６には、ステップ１１０３からのデータ依存が設定されているので、ステップ１１０６のｌｏｃａｌ＿ａ［ｉ］をａ［ｉ］に書き込む前に、ａ［ｉ］（ｉ＝１６、１７）を集中共有メモリ１６０からロードする。このため、ステップ１００６では、ＰＥ０で更新されたａ［１６］及びａ［１７］を、ａ［１８］及びａ［１９］と共に集中共有メモリに書き戻す。
【０１４１】
このように、第４の実施の形態では、図１１に示すように、複数のプロセシングエレメントがローカル変数を用いてデータを更新し、各プロセシングエレメントがローカル変数をグローバル変数に書き戻す。このため、第４の実施の形態では、フォルスシェアリングは発生しない。
【０１４２】
なお、本実施の形態ではプロセシングエレメント間でデータをコピーする処理のオーバーヘッドが生じる。
【０１４３】
次に、多次元配列を扱う場合について説明する。
【０１４４】
図１２Ａ及び図１２Ｂは、多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【０１４５】
まず、図１２Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１２００）。キャッシュメモリの１ラインには４個の変数が格納できる。このため、図１２Ａに示すように、キャッシュメモリの第１ライン１２１１にはａ［０］［０］からａ［０］［３］が存在し、第２ライン１２１２にはａ［０］［４］からａ［１］［１］が存在し、第５ライン１２１５にはａ［２］［４］、ａ［２］［５］、ａ［３］［０］、ａ［３］［１］が存在する。
【０１４６】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１２０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］］（３≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理し（１２０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻す。
【０１４７】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。また、前述したように、キャッシュラインの境界でループを分割できれば、フォルスシェアリングは発生しない。しかし、ＰＥ０によって処理されるａ［２］［４］及びａ［２］［５］と、ＰＥ１によって処理されるａ［３］［０］及びａ［３］［１］とが第５ライン１２１５上に存在することから、このライン上でＰＥ０によるアクセスとＰＥ１によるアクセスとが競合しフォルスシェアリングが発生する。
【０１４８】
図１３Ａ及び図１３Ｂは、第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１４９】
第１の実施の形態では、キャッシュラインの境界でループを分割するために、配列変数の各要素を外側ループのパラメータ毎に異なるラインに配置する。
【０１５０】
まず、図１３Ｂに示すように、６×１０の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１３００）。この配列の各変数ａ［ｉ］［ｊ］は、外側ループのパラメータ毎に異なるラインに配置される。
【０１５１】
本実施の形態では、キャッシュメモリの１ラインには４個の変数が格納でき、必要な変数は６×６の配列であるので、ラインサイズ（４個）の余分な変数を設けて、６×１０の配列変数を定義した。
【０１５２】
なお、ラインサイズ−１個の余分な変数を設ければよい。
【０１５３】
さらに、一般化すると、余分な配列変数の数の最低値は、下式が０以上となるＳの最低値によって与えられる。
【０１５４】
余分な配列変数の数の最低値＝Ｓ（４）の倍数−ｊmax
Ｓ：ラインサイズ
ｊmax：配列変数の外側ループより一つ内側のループの数（６）
【０１５５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１３０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理し（１３０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻した。
【０１５６】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。しかし、図１２を用いて前述した場合と異なり、図１３Ｂに示すように、ＰＥ０とＰＥ１とはキャッシュメモリの同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１５７】
なお、本実施の形態では、余分な変数が確保されるので、キャッシュメモリの利用効率が低下する。このため、本実施の形態は、配列変数の要素の数が少ないい場合、具体的には、下式を満たす場合に有効である。
【０１５８】
図１４Ａ及び図１４Ｂは、第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１５９】
第２の実施の形態では、キャッシュメモリのラインの区切りによって、各プロセッシングエレメントが処理するデータを分け、複数のプロセッシングエレメントによって処理されたデータがキャッシュメモリの１ライン上に格納されないようにする。
【０１６０】
まず、図１４Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１４００）。
【０１６１】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜４、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１４０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理する（１４０２）。その後、ＰＥ０が処理の結果をキャッシュメモリ１０２から集中共有メモリ１６０に書き戻し、ＰＥ１が処理の結果をキャッシュメモリ１１２から集中共有メモリ１６０に書き戻す。
【０１６２】
本実施の形態では、図１４Ａに示すように、１ラインは４個の変数が格納できる容量を有するが、ａ［３］［６］と、ａ［４］［０］とは異なるライン上に存在する。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１６３】
なお、本実施の形態ではＰＥ０に２４個、ＰＥ１に１２個の配列変数の処理を割り当てたが、キャッシュラインサイズの倍数になるように分ければ、ＰＥ０に１２個、ＰＥ１に２４個の配列変数の処理を割り当てても、よい。また、各プロセッシングエレメントの処理能力の比に従って数の配列変数の処理を割り当ててもよい。
【０１６４】
なお、本実施の形態では、対象の次元以下の配列変数の要素のサイズがラインサイズの倍数となればループ分割が可能である。この場合、配列変数の要素の数及びプロセッシングエレメントの数によって割り当てられる配列変数の数が等しくならず、プロセッシングエレメントの処理負荷の不均衡が生じる場合がある。このため、本実施の形態は、配列サイズが十分に大きく、不均衡が配列サイズに比べて無視できるほど小さい場合に有効である。
【０１６５】
図１５Ａ及び図１５Ｂは、第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１６６】
第３の実施の形態では、ノンキャッシャブル領域を用いて、フォルスシェアリングの発生を避ける。
【０１６７】
まず、図１５Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される。また、１×６の１次元の配列変数ｎｃ＿ｂｕｆ２が宣言され、変数ｎｃ＿ｂｕｆ２が変数６個（内側ループの数）のサイズのノンキャッシャブル領域が設けられる（１５００）。
【０１６８】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ上で処理し（１５０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［３］［ｊ］（０≦ｊ＜６）をｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）を用いてノンキャッシャブル領域上で処理し（１５０２）、ＰＥ１が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ上で処理する（１５０３）。
【０１６９】
ＰＥ０は、その後又は処理１５０３と並行して、ＰＥ１で処理された変数ｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［３］［ｊ］（０≦ｊ＜６）に書き込む（１５０４）。これによって、ＰＥ１によってｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）を用いて処理された変数ａ［３］［ｊ］（０≦ｊ＜６）がＰＥ０に転送される。
【０１７０】
その後、ＰＥ０が変数ａ［ｉ］［ｊ］（０≦ｉ＜４、０≦ｊ＜６）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）を集中共有メモリ１６０に書き戻す。
【０１７１】
このように、第３の実施の形態では、図１５Ａに示すように、ＰＥ１がノンキャッシャブルバッファを用いて演算した結果をＰＥ０のキャッシュメモリの変数に反映する。すなわち、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、一方のプロセシングエレメント（ＰＥ１）はノンキャッシャブル領域に当該ライン上のデータを格納し、他方のプロセシングエレメント（ＰＥ０）はノンキャッシャブル領域のデータを集中共有メモリのキャッシャブル領域に格納するので、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１７２】
なお、本実施の形態ではメモリ上にノンキャッシャブル領域を設ける必要があるが、ノンキャッシャブル領域は、集中共有メモリ、分散共有メモリ等の何れのメモリに設けてもよい。また、本実施の形態では、ノンキャッシャブル領域からキャッシュメモリにデータをコピーする処理のオーバーヘッドが生じる。しかし、ノンキャッシャブルのバッファとして分散共有メモリを利用することによって、低オーバーヘッドでデータの転送を実現することができる。
【０１７３】
図１６は、第４の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１７４】
まず、図１６に示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１６００）。
【０１７５】
その後、プロセシングエレメント０（ＰＥ０）１００が、６×６の２次元配列のローカル変数ｌｏｃａｌ＿ａを宣言し（１６０１）、変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］を用いて処理し（１６０２）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をグルーバル変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）へ書き込む（１６０３）。
【０１７６】
これと並行して又は前後して、プロセシングエレメント１（ＰＥ１）１１０が、６×６の２次元配列のローカル変数ｌｏｃａｌ＿ａを宣言し（１６０４）、変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］を用いて処理し（１６０５）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をグルーバル変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）へ書き込む（１６０６）。
【０１７７】
ステップ１６０６には、ステップ１１０３からのデータ依存が設定されているので、ステップ１６０６のｌｏｃａｌ＿ａ［ｉ］［ｊ］をａ［ｉ］［ｊ］に書き込む前に、ａ［２］［４］、ａ［２］［５］を集中共有メモリ１６０からロードする。このため、ステップ１００６では、ＰＥ０で更新されたａ［２］［４］及びａ［２］［５］を、ａ［３］［０］及びａ［３］［１］と共に集中共有メモリに書き戻す。
【０１７８】
このように、第４の実施の形態では、図１６に示すように、複数のプロセシングエレメントがローカル変数を用いてデータを更新し、各プロセシングエレメントがローカル変数をグローバル変数に書き戻す。このため、第４の実施の形態では、フォルスシェアリングは発生しない。
【０１７９】
なお、本実施の形態ではプロセシングエレメント間でデータをコピーする処理のオーバーヘッドが生じる。
【０１８０】
以上説明した実施の形態及び変形例は、プログラムのコンパイル時に一つ又は複数を組み合わせて用いることができる。
【０１８１】
次に、コンパイラが、フォルスシェアリングを回避するために最適な方法を選択する手順について説明する。
【０１８２】
図１７Ａは、本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【０１８３】
ステップ１７１０のタスクは、変数ｉを制御変数とするループであり、ループ分割により生成する部分タスクをそれぞれ別々のプロセッシングエレメントにスケジューリングすることにより並列処理を行う。このタスクを最大分割数でループ分割を行う場合、つまりｉループの１イタレーション分の処理を一つの部分タスクとなるようにループ分割した場合に生成される各部分タスクでは、２次元の配列変数Ａについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があるということがデータアクセス範囲解析により解析される。同様にステップ１７２０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を使用する可能性があり、ステップ１７３０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を使用する可能性があり、ステップ１７４０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があり、ステップ１７５０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があることが解析される。ここで、各タスクを最大分割数で分割した場合のアクセス範囲を考慮しているのは、任意の分割パターンでタスク分割を行った場合に、フォルスシェアリングが発生する可能性があるかどうかを解析するためである。
【０１８４】
各タスクの各部分タスクにおけるデータのアクセス範囲から、フォルスシェアリングが発生する可能性のある箇所とその要因となる配列変数およびその配列次元を解析する。具体的には、前述の部分タスクにおけるデータアクセス範囲において、分割元のタスクにおけるループ制御変数が含まれている次元のうち最も下位の次元において、その下位次元の部分配列サイズをキャッシュメモリのラインサイズで除したときに余りが発生する場合、フォルスシェアリングが発生する可能性があると判断できる。その場合、当該配列の更新を行うタスクの分割後の各部分タスクの間、あるいは当該配列の更新を行うタスクの分割後の各部分タスクとその配列を使用するタスクの分割後の各部分タスクの間でフォルスシェアリングが発生する可能性がある。
【０１８５】
なお、変数をメモリへ格納する方法がプログラム言語によって異なるので、どの添字を１次元目とするかは、変数のメモリへの格納方法によって異なる。すなわち、メモリの連続した領域に格納される配列変数の要素で変化する添字と最内周ループを構成する添字とが異なる場合、コンパイラは、必要に応じて、計算順序を変えるインターチェンジを行ってもよい。
【０１８６】
また、配列変数が集中共有メモリ１６０のラインの先頭にアラインされていない場合、上記の条件にかかわらずフォルスシェアリングが発生する可能性があると解析される。
【０１８７】
図１７Ｂは、本発明の実施の形態のループ分割後の処理を示すマクロタスクグラフである。本例では各タスクの分割数を３としているが、この分割数は任意に設定することが可能である。
【０１８８】
図１７Ｂ中、実線（１本線）は、プログラム上のデータ依存を示し、２重線は、フォルスシェアリングが発生する可能性がある箇所を示す。
【０１８９】
なお、フォルスシェアリングを検出するコードの例を図１７Ｃに示す。
【０１９０】
図１８は、本発明の実施の形態の並列化コンパイラによるソフトウェアコヒーレンシ制御コードを生成する処理の概要を説明する図である。
【０１９１】
まず、コンパイルすべきプログラム２００１が並列化コンパイラ２００２に入力される。入力されるプログラム２００１は、Ｃ、Ｆｏｒｔｒａｎ等の言語で記述された逐次プログラムである。
【０１９２】
並列化コンパイラ２００２は、入力された逐次プログラムを並列化し、ノンコヒーレントキャッシュで実行するための制御コードが挿入された並列ＡＰＩプログラム２００３を生成する。生成される並列ＡＰＩプログラム２００３は、コヒーレンシ機能を持たないキャッシュメモリを用いてプログラムを実行するための指示（ＡＰＩ）を含む並列プログラム形式である。
【０１９３】
生成された並列ＡＰＩプログラム２００３は、コード生成コンパイラ２００４に入力される。コード生成コンパイラ２００４は、コヒーレンシ機能を持たないキャッシュメモリを用いてプログラムを実行するための指示（ＡＰＩ）を解釈しながら、プログラムを機械語命令（実行形式プログラム）２００５に変換する。この実行形式プログラム２００５にも、ノンコヒーレントキャッシュでプログラムを実行するための命令が含まれる。
【０１９４】
図１９は、本発明の実施の形態のコンパイラによって実行される処理のフローチャートである。
【０１９５】
まず、コンパイラは、コンパイルすべきプログラムの字句を解析し、プログラムの構文を解析する（２１０１）。
【０１９６】
構文の解析結果に基づいて、階層的なタスク、すなわち、プログラムの階層的マクロタスクによる表現を生成する（２１０２）。
【０１９７】
その後、生成されたタスク間の依存関係（制御フロー）を解析し（２１０３）、タスク間のデータ依存を解析し（２１０４）、各タスクによってアクセスされるデータの範囲を解析する（２１０５）。
【０１９８】
その後、プログラムの解析結果を使用して、プログラムが最も早く実行できる条件を解析し（２１０６）、最早実行条件の解析結果を使用して、並列処理区間やタスクが割り当てられるプロセッサ数を決定し、マクロタスクグラフを生成する。
【０１９９】
その後、マクロタスクグラフにおけるデータ依存関係から、図１７Ａ、図１７Ｂ、図１７Ｃを用いて説明した方法によってフォルスシェアリングを検出し、フォルスシェアリングが検出された箇所及びフォルスシェアリングが検出された変数を含むフォルスシェアリング情報を生成する（２１０７）。
【０２００】
その後、生成されたフォルスシェアリング情報に基づいて、フォルスシェアリングが検出された箇所毎に、フォルスシェアリングを回避する方法が決定され、決定された方法に従って命令が挿入され、フォルスシェアリングが回避された並列プログラムが生成される（２１０８）。このフォルスシェアリング回避処理については、図２０Ａ及び図２０Ｂを用いて詳述する。
【０２０１】
その後、各タスクの実行順序を決定するタスクスケジューリングを実行し（２１０９）、ステイルデータに対処するためのキャッシュ操作指示を挿入する（２１１０）。これによって、コヒーレンシ制御機能つき並列プログラムが生成される。このキャッシュ操作指示の挿入処理については、図２１を用いて詳述する。
【０２０２】
図２０Ａ及び図２０Ｂは、本発明の実施の形態のフォルスシェアリング回避処理のフローチャートであり、コンパイル処理（図１９）のステップ２１０８から呼び出される。
【０２０３】
図２０Ａ及び図２０Ｂに示すフォルスシェアリング回避処理は、ステップ２１０７で検出されたフォルスシェアリング情報を入力とし、同じ配列に対して発生する各フォルスシェアリングについて以下の処理を行う。
【０２０４】
このフォルスシェアリング回避処理は、データレイアウト変換及びリストラクチャリングに大別され、図２０Ａにデータレイアウト変換処理を示し、図２０Ｂにリストラクチャリング処理を示す。
【０２０５】
まず、処理の対象となる配列変数が変換可能であるか否かを判定する（２１２１）。例えば、この配列変数がコンパイルされるプログラム中で閉じている場合、具体的には、コンパイルされるプログラム中で宣言されており、かつ、このプログラム外で定義される関数の引数とならない場合、データレイアウトの変換によりプログラムが予期せぬ動作をする可能性がないので、配列変数が変換可能であると判定する。
【０２０６】
その結果、配列が変換不可能であると判定された場合、配列の拡張又はパディング等のデータレイアウトの変換が困難であるため、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２０７】
一方、配列が変換可能であると判定された場合、配列の最速変化次元の要素間でフォルスシェアリングが発生するか否かを判定する（２１２２）。具体的には、Ｎ次元配列において、最速変化次元を１次元目、最遅変化次元をＮ次元目と定義する。最速変化次元とは、添字が連続的に変化する配列の次元である。例えば、Ｎ次元配列がループによって処理される場合、ループの最内周が最速変化次元となり、ループの最外周が最遅変化次元となる。すなわち、最速変化次元のデータはメモリ上の連続した領域に配置される。
【０２０８】
その結果、最速変化次元の要素間でフォルスシェアリングが発生すると判定された場合、配列の拡張が可能か否かを判定する（２１２３）。ステップ２１２３では、配列を拡張してもキャッシュ利用効率の低下に起因する性能の低下が小さいか否かを判定する。例えば、配列サイズが十分に小さい場合、図６Ａに示すように配列を拡張しても、キャッシュ利用効率の低下に起因する性能低下が小さいことから、配列の拡張が可能であると判定する。具体的には、下式（１）を満たす場合、配列サイズが十分に小さいので、配列の拡張が可能であると判定することができる。
【０２０９】
Ｓａ１≦Ｓ×Ｎ ・・・（１）
Ｓａ１：対象の配列の１次元目の宣言サイズ
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２１０】
その結果、配列の拡張が可能であると判定された場合、プログラム中に図６Ｂに示すコードを挿入することによって、図６Ａに示すように、配列を拡張する。一方、配列の拡張が困難であると判定された場合、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２１１】
一方、ステップ２１２２で、最速変化次元以外の次元の要素間でフォルスシェアリングが発生すると判定された場合、配列のパディングが可能か否かを判定する（２１２５）。ステップ２１２５では、配列をパディングしてもキャッシュ利用効率の低下に起因する性能の低下が小さいか否かを判定する。例えば、配列サイズが十分い大きい場合、図１３Ａに示すように配列をパディングしてもキャッシュ利用効率の低下に起因する性能低下が小さいことから、配列のパディングが可能であると判定する。具体的には、下式（２）を満たす場合、配列サイズが十分に小さいので、配列のパディングが可能であると判定することができる。
【０２１２】
Ｓａ２≧Ｓ×Ｎ ・・・（２）
Ｓａ２：対象の配列変数でフォルスシェアリングが発生する次元以下の部分配列サイズ
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２１３】
その結果、配列の拡張が可能であると判定された場合、図１３Ｂに示すコードをプログラム中に挿入することによって、図１３Ａに示すように、配列を拡張する。一方、配列の拡張が困難であると判定された場合、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２１４】
図２０Ｂに示すリストラクチャリング処理では、検出されたフォルスシェアリング情報のうち、データレイアウト変換で対処できなかったフォルスシェアリングに対して、以下の処理を行う。
【０２１５】
まず、各プロセッサによる処理の境界領域のみでフォルスシェアリングが発生するか否かを判定する（２１３１）。具体的には、処理の対象となる配列へのアクセスが連続アクセスになっているか否かを判定する。例えば、並列化後に各プロセッサがアクセスする領域が重複している場合（ＰＥ０がｉ、ｉ＋２、ｉ＋４…とアクセスし、ＰＥ１がｉ＋１、ｉ＋３、ｉ＋５…とアクセスする場合）、処理の対象となる配列へのアクセスは連続アクセスとならないことから、境界領域以外でもフォルスシェアリングが発生する。
【０２１６】
その結果、境界領域以外でもフォルスシェアリングが発生すると判定された場合、ステップ２１３９へ進む。
【０２１７】
一方、境界領域のみでフォルスシェアリングが発生すると判定された場合、フォルスシェアリングが発生すると判定された場所がループによる並列処理であるか否かを判定する（２１３２）。
【０２１８】
その結果、ループによる並列処理以外でフォルスシェアリングが発生すると判定された場合、ステップ２１３９へ進む。
【０２１９】
一方、ループによる並列処理においてフォルスシェアリングが発生すると判定された場合、キャッシュラインの境界でループを分割できるか否かを判定する（２１３３）。
【０２２０】
その結果、キャッシュラインの境界でループを分割できないと判定された場合、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３８）。
【０２２１】
一方、キャッシュラインの境界でループを分割できると判定された場合、ループの分割に起因する負荷の不均衡による性能低下が小さいか否かを判定する（２１３４）。例えば、ループ回転数が十分に大きい場合、ループの分割に起因する負荷の不均衡による影響は小さいと判定できる。具体的には、下式（３）を満たす場合、ループ回転数が十分に大きいので、負荷の不均衡による影響は小さいと判定することができる。
【０２２２】
Ｒ≧Ｓ×Ｎ ・・・（３）
Ｒ：ループ回転数
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２２３】
また、各プロセッサにタスクを均等に分割した場合、分割されたタスクによって使用されるデータ量（アクセス範囲）の最大値と最小値との差をラインサイズと比較し、この差がラインサイズより小さい場合に負荷不均衡による影響が小さいと判定してもよい。
【０２２４】
その結果、ループの分割による負荷の不均衡による影響が大きいと判定された場合、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３８）。なお、図１０Ａ、図１０Ｂに示す方法を用いてもよく、多次元配列の場合は図１５Ａ、図１５Ｂに示す方法を用いる。
【０２２５】
一方、ループの分割による負荷の不均衡による影響は小さいと判定された場合、キャッシュラインの境界のみでループを分割できるか否かを判定する（２１３５）。例えば、配列変数の要素ａ［ｉ］及びａ［ｉ＋１］に同じループ内でアクセスされる場合、キャッシュラインの境界のみでループを分割することはできない。
【０２２６】
その結果、キャッシュラインの境界のみでループを分割できると判定された場合、図７Ｂに示すコードをプログラム中に挿入することによって、図７Ａに示すように、キャッシュラインの境界でループを分割する（２１３６）。なお、多次元配列の場合は図１５Ａ、図１５Ｂに示す方法を用いる。
【０２２７】
一方、配列変数ａ［ｉ］及びａ［ｉ＋１］に同じループ内でアクセスされる場合、キャッシュラインの境界のみではループを分割できない場合、キャッシュラインの境界でループを分割できる箇所（例えば、ａ［ｉ］が分割される箇所）には、図７Ｂに示すコードをプログラム中に挿入する。さらに、キャッシュラインの境界でループを分割できない箇所（例えば、ａ［ｉ＋１］が分割される箇所）には、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３７）。
【０２２８】
例えば、ａ［ｉ］は、キャッシュラインの境界でループを分割し、ａ［ｉ＋１］については、バッファを用いてプロセッシングエレメント間で通信するとよい。この場合、ａ［ｉ］のアクセス回数とａ［ｉ＋１］のアクセス回数とを比較し、アクセス回数が多い配列変数の要素の添字について、キャッシュラインの境界でループを分割して、バッファに格納されたデータの通信のオーバーヘッドを少なくするとよい。
【０２２９】
一方、ステップ２１３９では、各プロセッシングエレメントにおける演算に用いられるプライベート変数からグローバル変数へのコピー処理のオーバーヘッドが小さいか否かを判定する。具体的には、ループ中で実行される計算の処理量が十分に大きい場合、コピー処理のオーバーヘッドは無視できる程度の小さい。例えば、単に他の変数のデータをａへ代入（コピー）する場合、ループ中で実行される計算の処理量は小さいが、ループ中で四則演算や関数による計算結果をａへ代入している場合、ループ中で実行される計算の処理量は大きくなる。
【０２３０】
その結果、変数のコピー処理のオーバーヘッドが小さいと判定された場合、図１１に示すコード（多次元配列の場合は図１６に示すコード）をプログラム中に挿入することによって、各プロセッシングエレメントにおいて定義されたプライベート変数を用いて演算をし、演算の結果をプライベート変数からグローバル変数へコピーする（２１４０）。
【０２３１】
一方、変数のコピー処理のオーバーヘッドが大きいと判定された場合、各プロセッシングエレメントによる演算の結果を、逐次、集中共有メモリ１６０に書き込む（２１４１）。
【０２３２】
図２１は、本発明の実施の形態のキャッシュ操作指示の挿入処理のフローチャートである。
【０２３３】
まず、並列化フェイズにおけるタスクグラフのスケジューリング結果において、異なるプロセッサに割り当てられたタスク間のデータ依存を解析する（２１５１）。
【０２３４】
解析されたデータの依存関係が、フロー依存又は出力依存であるか否かを判定する（２１５２）。その結果、解析されたデータの依存関係がフロー依存又は出力依存である場合、キャッシュ操作指示を挿入する。
【０２３５】
具体的には、図３Ｂを用いて前述したように、データを生産する側のプロセシングエレメントが、データを更新後にライトバック命令によって主記憶（集中共有メモリ１６０）に更新されたデータを書き戻すキャッシュ操作指示と、データを消費する側のプロセシングエレメントが、データを消費する前にセルフインバリデート命令によって主記憶からデータを読み込むキャッシュ操作指示と生成し、生成されたキャッシュ操作指示をプログラム中に挿入する。このとき、生産側のプロセシングエレメントによるデータの更新の終了はフラグによって消費側のプロセシングエレメントに通知され、消費側のプロセシングエレメントはフラグの更新によってデータの更新を知り、更新されたデータを主記憶から読み込むように制御される。コンパイラは、このフラグによる制御命令を生成し、生成された制御命令をプログラム中に挿入する。
【０２３６】
一方、解析されたデータの依存関係がフロー依存でも出力依存でもない場合、キャッシュ操作指示の挿入処理を終了する。
【０２３７】
以上説明したように、本発明の実施の形態によると、ソフトウェアによる制御によって、コヒーレンシ制御のためのハードウェアが不要となり、ハードウェアを簡素化できる。このため、低コストかつ低消費電力のマルチプロセッサを実現できる。また、コンパイラの最適化によって、スケーラブルな性能向上が可能となる。
【０２３８】
特許請求の範囲に記載した以外の本発明の観点の代表的なものとして、次のものがあげられる。
【０２３９】
（１）複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備えるマルチプロセッサシステムであって、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントは、
前記主記憶装置から読み込んだデータを前記キャッシュメモリに一時的に格納し、
使用が終了したデータを前記キャッシュメモリから、前記キャッシュメモリの管理単位に従って、前記主記憶装置に書き戻し、
前記プログラムを分割して生成される各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納することを特徴とするマルチプロセッサシステム。
【０２４０】
（２）前記プロセッシングエレメントは、少なくとも第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記第１のプロセッシングエレメントは、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算し、
前記第２のプロセッシングエレメントは、
前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記ノンキャッシャブル領域で演算し、
前記ノンキャッシャブル領域で演算した結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送することを特徴とする（１）に記載のマルチプロセッサシステム。
【０２４１】
（３）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記各プロセッシングエレメントは、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算し、
前記第１のプロセッシングエレメントは、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込むことを特徴とする（１）に記載のマルチプロセッサシステム。
【０２４２】
（４）異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻し、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化することを特徴とする（１）から（３）のいずれか一つに記載のマルチプロセッサシステム。
【０２４３】
（５）マルチプロセッサシステムに備わるプロセッサにおいて演算処理を実行させるプログラムであって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリの管理単位に従ってデータが転送され、
前記プログラムは、各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順を含むことを特徴とするプログラム。
【０２４４】
（６）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算する手順と、
前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順と、
前記第２のプロセッシングエレメントが、前記ノンキャッシャブル領域に格納された演算結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送する手順とを含むことを特徴とする（５）に記載のプログラム。
【０２４５】
（７）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算する手順と、
前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込む手順とを含むことを特徴とする（５）に記載のプログラム。
【０２４６】
（８）異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻す手順と、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化する手順とを含むことを特徴とする（５）から（７）のいずれか一つに記載のプログラム。
【符号の説明】
【０２４７】
１００、１１０、１２０ プロセシングエレメント
１０１、１１１、１２１ プロセッサ
１０２、１１２、１２２ キャッシュメモリ
１５０ 内部結合網
１６０ 集中共有メモリ（主記憶）
【技術分野】
【０００１】
本発明は、複数のプロセシングエレメントによって構成されるマルチプロセッサにおけるメモリの管理方法に関し、特に、コンパイラが取得した情報に基づいて、共有メモリに格納されたデータの一貫性（コヒーレンシ）を保つように制御する方法に関する。
【背景技術】
【０００２】
複数のプロセシングエレメントを集積したマルチプロセッサが、各マイクロプロセッサメーカによって次々に発表されている。スーパーコンピュータ、サーバ、デスクトップコンピュータ及びＰＣサーバ分野の他、情報家電及び装置組み込みの分野（例えば、携帯電話機、ゲーム機、カーナビゲーションシステム、デジタルテレビ受像機、ＨＤＤ／ＤＶＤレコーダ・プレーヤ等）においても、マイクロプロセッサのマルチコア化の動きが見られる。
【０００３】
マルチプロセッサは、複数のプロセシングエレメント、内部結合網及び集中共有メモリを備え、各プロセシングエレメントは、プロセッサ及びキャッシュメモリを備え、独立に演算処理を行うものである。このような構成のマルチプロセッサは、集中共有メモリを主記憶として使用し、複数のプロセッシングエレメントが、集中共有メモリに格納された同一のデータをアクセスする主記憶共有型プロセッサとして使用される。
【０００４】
このとき、共有データ間のコヒーレンシを保つために、あるプロセッサがキャッシュメモリ上の共有データをアクセスしている場合、他のプロセッサが当該共有データを集中共有メモリからキャッシュメモリへのアクセスを禁止するコヒーレンシ制御が必要となっていた。
【０００５】
ここで、コヒーレンシとは、ある時刻において、メモリのあるアドレスに格納された値を、全てのプロセッサが同一の値としてアクセスできることであり、主記憶共有型マルチプロセッサにおいて、各プロセッサからアクセスされるメモリの内容が同一であることを保証するための制御である。コヒーレンシを保つための機能には、ハードウェアによってメモリアクセスを制御するコヒーレントキャッシュがある。
【０００６】
コヒーレンシ制御において解決しなければならない第１の問題はデータの陳腐化（Ｓｔａｌｅ Ｄａｔａ）であり、第２の問題はフォルスシェアリング（Ｆａｌｓｅ Ｓｈａｒｉｎｇ）である。
【０００７】
図２２は、コヒーレンシ制御における第１の問題点（ステイルデータ）を説明する図である。
【０００８】
まず、グローバル変数ａ、ｂ、ｃが宣言され（２２００）、共有メモリに変数ａ＝０，ｂ＝０，ｃ＝１が格納された（２２０１）。
【０００９】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュメモリに共有データ（ａ＝０、ｂ＝０、ｃ＝１）が格納されており（２２０２）、他のプロセシングエレメント（ＰＥ１）のキャッシュメモリにも同じ共有データが格納されている（２２０３）場合、ＰＥ０で当該共有データが更新（ａ＝０→１）されても、ＰＥ１のキャッシュ上の共有データは更新されていない古いデータ（ａ＝０）である（２２０５）。この状態で、ＰＥ１で当該共有データが更新（ｃ＝ａ）されると、変数ｃは正しいａの値を反映することなく０に更新されてしまう（２２０６）。
【００１０】
このため、コヒーレンシ制御がされていれば、ａ＝１、ｂ＝０、ｃ＝１であるはずの変数が、ａ＝０、ｂ＝０、ｃ＝０となる。このため、ＰＥ０のキャッシュメモリに格納されているデータと、ＰＥ１のキャッシュメモリに格納されているデータとが不一致となる。このため、ＰＥ１が誤った動作をしてしまう。
【００１１】
図２３は、コヒーレンシ制御における第２の問題点（フォルスシェアリング）を説明する図である。
【００１２】
まず、グローバル変数ａ、ｂが宣言され（２３００）、変数ａ＝０、ｂ＝０が共有メモリに格納された（２３０１）。この変数ａ及びｂは、共有メモリの同じキャッシュライン上に格納されている。また、共有メモリは、ライン単位でアクセスされる。
【００１３】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュメモリに格納された共有データが更新（ａ＝０→１）され（２３０２）、他のプロセシングエレメント（ＰＥ１）のキャッシュメモリに格納された共有データが更新（ｂ＝０→２）された（２３０３）。すなわち各プロセッシングエレメントが、同一のライン上に格納された異なる変数を更新した。この場合、ＰＥ０が先に共有メモリにデータを書き戻せば、後にデータを書き戻したＰＥ１のデータが共有メモリに格納される（２３０４）。一方、ＰＥ１が先に共有メモリにデータを書き戻せば、後にデータを書き戻したＰＥ０のデータが共有メモリに格納される（２３０５）。
【００１４】
コヒーレンシ制御がされている場合、共有メモリにはａ＝１、ｂ＝２が格納されるが、コヒーレンシ制御がされない場合、最終的にどのデータが共有メモリに格納されるかは定まらない。すなわち、ライン吐き出しタイミングによりメモリの内容が異なり、いずれにせよプロセッシングエレメントは誤った動作をしてしまう。
【００１５】
このような共有メモリとキャッシュメモリとの間での不一致が生じる問題点を解決するために、各プロセッシングエレメント及び共有資源（内部結合網、共有メモリ等）にコヒーレンシ制御部を設けることによって、メモリに格納されたデータのコヒーレンシを保つ。
【００１６】
具体的には、あるプロセシングエレメント（ＰＥ０）がデータｘを共有メモリから読み出した後に、ＰＥ０がデータｘを共有メモリから読み出して、それを更新し、データｘの所有権を破棄するまで、他のプロセシングエレメント（ＰＥ１）による共有メモリのデータｘへの書き込みは許可されない。
【００１７】
このような所有権制御によって、データの陳腐化（Ｓｔａｌｅ Ｄａｔａ）及びフォルスシェアリング（Ｆａｌｓｅ Ｓｈａｒｉｎｇ）のコヒーレンシ制御の問題を解決することができる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００４−３０３６２号公報
【特許文献２】特開平９−４４４０３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかし、ハードウェアによってメモリアクセスを所有権制御するコヒーレントキャッシュでは、ハードウェアのコストのために、プロセッサ数の増加によって、マルチプロセッサのコストが上昇する。また、ハードウェアによってメモリアクセスを制御することによって、メモリアクセスが遅くなる。
【００２０】
さらに、ハードウェアによるコヒーレンシ制御では、イベント毎に全てのプロセッサ、メモリ及びバス制御機構に信号を送るので、実行時のオーバーヘッドが生じる。このオーバーヘッドは、マルチプロセッサに含まれるプロセッサ数に応じて増加する。このため、プロセッサ数が増加した場合、コヒーレンシ制御のための通信でバスが埋まってしまい、プロセッサの動作を妨げる。
【００２１】
このため、より簡単なハードウェア構成によるコヒーレンシ制御、特にソフトウェアによるコヒーレンシ制御が求められている。
【課題を解決するための手段】
【００２２】
本発明のコンパイラは、プログラムを解析して得られるコントロールフロー及びデータ依存関係の情報を用いて、ソフトウェアによる明示的なキャッシュ操作コードを生成する。また、異なるプロセシングエレメントによって使用される変数が、同じキャッシュラインに載らないように配置する。
【発明の効果】
【００２３】
本発明によれば、ソフトウェアによる制御によって、コヒーレンシ制御のためのハードウェアが不要となり、ハードウェアを簡素化できる。このため、低コストかつ低消費電力のマルチプロセッサを実現できる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態のマルチプロセッサの構成図である。
【図２】本発明の実施の形態のマルチプロセッサのキャッシュメモリの各ラインがとりうる状態を説明する図である。
【図３Ａ】本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【図３Ｂ】本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【図４】本発明の実施の形態のフォルスシェアリングの発生を避ける方法の概要を説明する図である。
【図５Ａ】一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図５Ｂ】一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図６Ａ】本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図６Ｂ】本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図７Ａ】本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図７Ｂ】本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ｂ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【図８Ｃ】本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が集中共有メモリに設けられた場合の例を示す。
【図８Ｄ】本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリに設けられた場合の例を示す。
【図９Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図９Ｂ】図９Ａに示す変形例におけるノンキャッシャブル領域が集中共有メモリに設けられた場合の例を示す。
【図９Ｃ】図９Ａに示す変形例におけるノンキャッシャブル領域が分散共有メモリに設けられた場合の例を示す。
【図１０Ａ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１０Ｂ】本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１１】本発明の第４の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【図１２Ａ】多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図１２Ｂ】多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【図１３Ａ】第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１３Ｂ】第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１４Ａ】第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１４Ｂ】第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１５Ａ】第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１５Ｂ】第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１６】第４の実施の形態を２次元配列変数に適用した例を説明する図である。
【図１７Ａ】本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【図１７Ｂ】本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【図１７Ｃ】本発明の実施の形態のフォルスシェアリングを検出するためのコードの例を説明する図ある。
【図１８】本発明の実施の形態の並列化コンパイラによるソフトウェアコヒーレンシ制御コードを生成する処理の概要を説明する図である。
【図１９】本発明の実施の形態のコンパイラによって実行される処理のフローチャートである。
【図２０Ａ】本発明の実施の形態のフォルスシェアリング回避処理のフローチャートである。
【図２０Ｂ】本発明の実施の形態のフォルスシェアリング回避処理のフローチャートである。
【図２１】本発明の実施の形態のキャッシュ操作指示の挿入処理のフローチャートである。
【図２２】コヒーレンシ制御における第１の問題点（ステイルデータ）を説明する図である。
【図２３】コヒーレンシ制御における第２の問題点（フォルスシェアリング）を説明する図である。
【発明を実施するための形態】
【００２５】
図１は、本発明の実施の形態のマルチプロセッサの構成図である。
【００２６】
本発明の実施形態のマルチプロセッサは、複数のプロセシングエレメント（ＰＥ０、ＰＥ１、…、ＰＥｎ）１００、１１０、１２０、内部結合網１５０、及び集中共有メモリ１６０を備える。
【００２７】
プロセシングエレメント１００は、演算処理をするプロセッサ１０１、データを一時的に格納するキャッシュメモリ１０２、分散共有メモリ（ＤＳＭ）１０３及びデータ転送コントローラを備え、独立に動作する。
【００２８】
プロセッサ１０１は、整数演算及び浮動小数点演算が可能なものであればよく、その機能は特に限定されない。例えば、データのロード及びストアのアーキテクチャが単純なシングルイッシューＲＩＳＣアーキテクチャのＣＰＵを用いてもよい。また、スーパースカラプロセッサ、ＶＬＩＷプロセッサ等も用いてもよい。
【００２９】
キャッシュメモリ１０２は、集中共有メモリ１６０からプロセッサ１０１によって読み込まれたデータを一時的に格納するメモリである。プロセッサ１０１は、キャッシュメモリ１０２に格納されたデータを用いて演算処理をする。プロセッサ１０１による演算処理が終了すると、キャッシュメモリ１０２に格納されたデータは集中共有メモリ１６０に書き戻される。このキャッシュメモリ１０２と集中共有メモリ１６０との間では、ライン毎にデータが読み書きされる。このラインは、キャッシュメモリ１０２に格納されたデータの管理単位である。
【００３０】
なお、プロセッシングエレメント１００は、キャッシュメモリ１０２を二次キャッシュとして使用し、キャッシュメモリ１０２の他に一次キャッシュを備えてもよい。この場合、一次キャッシュと二次キャッシュ（キャッシュメモリ１０２）とは、コヒーレンシ制御がされてもよい。すなわち、本発明の実施の形態のマルチプロセッサでは、主記憶として機能する集中共有メモリ１６０と最外側のキャッシュメモリ１０２との間でデータの一致を保つコヒーレンシ機能を有さない。
【００３１】
分散共有メモリ１０３は、格納されたデータを他のプロセシングエレメントから直接読み書きすることができるメモリである。なお、分散共有メモリ１０３がデュアルポートメモリで構成されていると、プロセッサ１０１とデータ転送コントローラとが競合することなく分散共有メモリにアクセスすることができる。なお、分散共有メモリ１０３は、本実施の形態のマルチプロセッサに必須の構成ではない。
【００３２】
データ転送コントローラは、プロセッシングエレメントに備わるメモリに格納されたデータをプロセッシングエレメント間で転送する。
【００３３】
さらに、プロセシングエレメント１００は、図示した構成の他、ローカルプログラムメモリ、ローカルデータメモリ、ネットワークインターフェイス及び電力制御レジスタを備えてもよい。
【００３４】
なお、プロセシングエレメント１１０、１２０も、プロセシングエレメント１００と同じ構成を有する。
【００３５】
内部結合網１５０は、既存の接続技術（クロスバースイッチ、バス、マルチステージネットワーク等）によって実現され、複数のプロセシングエレメント１００等及び集中共有メモリ１６０を接続する。
【００３６】
集中共有メモリ１６０（ＣＳＭ）は、システム中の全プロセシングエレメント１００等によって共有されるデータが格納される主記憶として機能し、各プロセシングエレメント１００等からアクセス可能なメモリである。
【００３７】
なお、本実施の形態のマルチプロセッサは、キャッシュメモリ１０２等と集中共有メモリ１６０との間でデータの一致を保つための、ハードウェアによるコヒーレンシ機能を有さない。
【００３８】
＜ステイルデータの解決＞
まず、第１の課題であるステイルデータの発生を避ける方法について説明する。
【００３９】
本発明の実施の形態のマルチプロセッサは、前述したように、キャッシュメモリ１０２等と集中共有メモリ１６０との間でデータの一致を保つための、ハードウェアによるコヒーレンシ機能を有さない。このため、あるプロセッシングエレメントがキャッシュメモリ上でデータを更新した場合、このデータ更新は他のプロセッシングエレメントに通知されない。また、更新されたデータが書き戻されるまで、更新されたデータは集中共有メモリ１６０にも反映されない。
【００４０】
このため、本発明の実施の形態のコンパイラは、プログラムを解析した結果（データコントロールフロー、データ依存関係）に基づいて、ソフトウェアによる明示的なキャッシュ操作コードを生成する。
【００４１】
生成されるキャッシュ操作コードは、その命令が実行されるプロセッシングエレメントのキャッシュメモリに格納されたデータを操作する命令だけであり、ハードウェアによるコヒーレンシプロトコルにおけるキャッシュ操作要求のような、他プロセッシングエレメントのキャッシュメモリに格納されたデータの状態を操作する命令ではない。生成されるキャッシュ操作コードは、ライトバック、セルフインバリデート、パージの３種類がある。
【００４２】
ライトバック（ｗｒｉｔｅｂａｃｋ）は、キャッシュメモリ１０２に格納されたデータを集中共有メモリ１６０に書き戻すための命令である。キャッシュメモリ１０２上でデータが更新され、集中共有メモリ１６０上の対応するアドレスに格納されるデータと異なる場合、ラインの状態はダーティとなり、キャッシュメモリ１０２に格納されたデータを、集中共有メモリ１６０に書き戻す必要がある。
【００４３】
なお、キャッシュメモリ１０２のラインリプレースに伴うデータの書き戻し（ａｕｔｏ−ｗｒｉｔｅｂａｃｋ）によっても、集中共有メモリ１６０へデータが書き戻される。
【００４４】
セルフインバリデート（ｓｅｌｆ−ｉｎｖａｌｉｄａｔｅ）は、キャッシュメモリ１０２のラインを無効化するための命令である。セルフインバリデートされ、インバリデート状態になったデータは、キャッシュメモリに格納されていても、再度集中共有メモリ１６０から読み込むまで使用することができない。
【００４５】
パージ（ｐｕｒｇｅ）は、キャッシュメモリ１０２のラインに格納されたデータを書き戻した（ライトバック）後、セルフインバリデート実行するための命令である。
【００４６】
また、各プロセッシングエレメントで実行されるタスク間で通信が発生する箇所にキャッシュ操作コードが挿入される。
【００４７】
さらに、コンパイラは、異なるプロセッシングエレメントが同一ラインのデータを保持している場合、異なるプロセッシングエレメントに格納された同一ラインのデータを同時に更新しないように制御する。
【００４８】
図２は、本発明の実施の形態のマルチプロセッサのキャッシュメモリ１０２の各ラインがとりうる状態を説明する図である。
【００４９】
キャッシュメモリ１０２は、ライン毎に、Ｍｏｄｉｆｉｅｄ、Ｖａｌｉｄ、Ｓｔａｌｅ、Ｉｎｖａｌｉｄの４状態をとる。
【００５０】
Ｍｏｄｉｆｉｅｄは、キャッシュメモリ１０２に格納されたデータが更新されたダーティデータで、集中共有メモリ１６０上の対応するアドレスに格納されるデータと異なっている状態である。この場合、ライトバックによって、キャッシュメモリ１０２に格納されたデータを集中共有メモリ１６０に書き戻す必要がある。
【００５１】
Ｖａｌｉｄは、キャッシュメモリ１０２に格納されたデータが集中共有メモリ１６０上の対応するアドレスに格納されるデータと一致しているクリーン状態である。
【００５２】
Ｓｔａｌｅは、キャッシュメモリ１０２に格納されたデータと同期すべきデータが他のプロセッシングエレメントによって書き換えられたが、まだ当該更新データは集中共有メモリ１６０に書き戻されていないため、当該キャッシュデータは集中共有メモリ１６０上の対応するアドレスに格納されるデータとが一致しているクリーン状態である。
【００５３】
Ｉｎｖａｌｉｄは、キャッシュメモリ１０２に格納されたデータと一致していないデータである可能性がある状態である。
【００５４】
前述した４状態は、キャッシュメモリ１０２へのアクセス、及び、キャッシュ操作によって遷移する。
【００５５】
キャッシュメモリ１０２へのアクセスには、プロセッサ１０１による集中共有メモリ１６０からのデータの読み込み（ｒｅａｄ）、プロセッサ１０１によるキャッシュメモリ１０２へのデータの書き込み（ｗｒｉｔｅ）がある。
【００５６】
本発明の実施の形態のコンパイラは、複数のプロセッシングエレメントのキャッシュメモリに格納された同一ラインのデータが、同時にＭｏｄｉｆｉｅｄとならないように制御する。また、本実施の形態のコンパイラは、Ｓｔａｌｅのデータを読み書きしないように制御する。
【００５７】
図３Ａ及び図３Ｂは、本発明の実施の形態のステイルデータの消費を避ける方法を説明する図である。
【００５８】
本発明の実施の形態のコンパイラは、プロセッシングエレメントをまたがるデータ依存が存在する場合、データ依存のエッジでデータを同期する。例えば、コンパイラがプログラムの解析によって検出すべきデータ依存のエッジは、フロー依存によって生じるｄｅｆ−ｕｓｅの関係である。
【００５９】
例えば、図３Ａに示すように、ＰＥ０がタスクブロック１（ＳＢ１）で変数Ａを定義した（３００）後、ＰＥ１がタスクブロック３（ＳＢ３）で変数Ａを使用する場合、図３Ｂに示すように、ＰＥ０による変数Ａの更新によって、ＰＥ１は変数Ａが格納されているラインの状態をｉｎｖａｌｉｄａｔｅへ変更する（３０２）。また、ＰＥ０が変数Ａを集中共有メモリに書き戻した（３０１）後に、ＰＥ１が変数Ａを使用する。
【００６０】
より具体的には、コンパイラは、ＰＥ０が更新した変数Ａを、他のプロセッシングエレメント（ＰＥ１）で使用する前に、ライトバック命令（３０１）を挿入する。この場合、次に自プロセシングエレメント（ＰＥ０）が変数Ａが使用する場合は、ライトバック命令を挿入せず、他のプロセッシングエレメント（ＰＥ１）が変数Ａを使用する前にライトバック命令を挿入すればよい。
【００６１】
さらに、コンパイラは、フラグ変数を用いたプロセッシングエレメント間のデータ同期のために、同期の送信側（ＰＥ０）は、同期フラグ変数（ｓｙｎｃ＿ｆｌｇ）に同期を示す値を書き込む命令（３０２）、及び、その同期フラグ変数が格納されているキャッシュメモリのラインを集中共有メモリに書き戻す命令（３０３）を挿入する。
【００６２】
一方、ＰＥ１について、コンパイラは、他のプロセシングエレメント（ＰＥ０）によって更新された変数Ａを使用する前にセルフインバリデート命令（３０４）を挿入する。なお、セルフインバリデート命令（３０４）が挿入される箇所（セルフインバリデートのタイミング）は、変数Ａを使用する直前が望ましい。
【００６３】
さらに、コンパイラは、同期フラグ変数（ｓｙｎｃ＿ｆｌｇ）のインバリデート及び読み込みを繰り返し、同期フラグ変数の値が同期を示す値に更新されるまでビジーウェイト状態で待機する命令（３０５）を挿入する。
【００６４】
ＰＥ１は、変数Ａがインバリデートされており、キャッシュメモリ上の変数Ａを使用できないため、変数Ａを集中共有メモリ１６０からキャッシュメモリにロードし、ＰＥ０で更新された変数Ａを取得する。
【００６５】
以上、ｄｅｆ−ｕｓｅの関係について説明したが、出力依存によって生じるｄｅｆ−ｄｅｆの関係、ｕｓｅ−ｄｅｆによる逆依存の関係、ｕｓｅ−ｕｓｅによる入力依存の関係でも同様のことが生じうる。
【００６６】
このように、本実施の形態のコンパイラは、タスク間のフロー依存及び出力依存を解析した結果に応じてキャッシュ操作命令を挿入するので、コヒーレンシ制御をすることなく、ステイルデータを消費することがない。
【００６７】
＜フォルスシェアリングの解決＞
次に、第２の課題であるフォルスシェアリングの発生を避けるための方法について説明する。
【００６８】
図４は、本発明の実施の形態のフォルスシェアリングの発生を避ける方法の概要を説明する図である。
【００６９】
本実施の形態では、各プロセシングエレメントによって使用される変数が、同じキャッシュラインに載らないように、各変数がキャッシュラインの先頭に配置される（アラインメント）を行う。なお、変数のアライメントは、配列変数の宣言において指定しても、別に設定ファイル等に記述してもよい。
【００７０】
まず、図２３で前述したと同様に、グローバル変数ａ、ｂが宣言され（４００）、変数ａ＝０、ｂ＝０が集中共有メモリ１６０に格納された。しかし、本発明の実施の形態では、図２３で前述したと異なり、宣言されたグローバル変数ａ、ｂは集中共有メモリ１６０のキャッシュラインの先頭に配置されるので、異なるライン上に格納される。
【００７１】
その後、あるプロセシングエレメント（ＰＥ０）のキャッシュ上の共有データが更新（ａ＝０→１）され（４０１）、他のプロセシングエレメント（ＰＥ１）のキャッシュ上の共有データが更新（ｂ＝０→２）された（４０２）。しかし、各プロセッシングエレメントは、異なるライン上に格納された異なる変数を更新したので、各プロセシングエレメントがいかなるタイミングでキャッシュメモリに格納されたデータを集中共有メモリ１６０に書き戻しても（４０４、４０５）、正しいデータ（ａ＝１、ｂ＝２）が集中共有メモリ１６０格納される。
【００７２】
次に、一次元配列を扱う場合について説明する。
【００７３】
図５Ａ及び図５Ｂは、一次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【００７４】
まず、図５Ｂに示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（５００）。本実施の形態ではキャッシュメモリの１ラインが１６バイトであり、１ラインに４個の変数が格納できる場合を考える。このため、図５Ａに示すように、キャッシュメモリの第１ライン５１１にはａ［０］からａ［３］が格納されており、第２ライン５１２にはａ［４］からａ［７］が格納されており、第５ライン５１５にはａ［１６］からａ［１９］が格納されている。
【００７５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ１０２上で処理し（５０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８≦ｉ＜３６）をキャッシュメモリ１１２上で処理し（５０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻す。
【００７６】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。ＰＥ０によって処理されるａ［１６］及びａ［１７］と、ＰＥ１によって処理されるａ［１８］及びａ［１９］とが第５ライン５１５上に存在することから、このライン上でＰＥ０によるアクセスとＰＥ１によるアクセスとが競合しフォルスシェアリングが発生する。
【００７７】
図６Ａ及び図６Ｂは、本発明の第１の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００７８】
第１の実施の形態の方法では、図６Ａに示すように、グローバル変数ａの各要素を集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置することによって、各要素を異なるラインに配置する。このため、キャッシュラインの境界で処理が分割される。
【００７９】
まず、図６Ｂに示すように、グローバル変数ａが宣言され、変数ａに含まれる３６個の配列変数の各要素が集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（６００）。
【００８０】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）を処理し（６０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８≦ｉ＜３６）を処理し（６０２）、ＰＥ０及びＰＥ１が処理の結果を集中共有メモリ１６０に書き戻す。しかし、図５Ａを用いて前述した場合と異なり、図６Ｂに示すように、ＰＥ０とＰＥ１とは集中共有メモリ１６０の同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００８１】
なお、本実施の形態では、１ラインは４個の変数が格納できる容量を有するが、１ラインに１個の変数しか格納されていないので、キャッシュメモリの利用効率が低下する。このため、本実施の形態は、配列変数の要素の数が少ない場合に有効である。また、同一のプロセッシングエレメントが、配列変数の異なる添字の要素（ａ（ｉ）、ａ（ｉ＋１））にアクセスするような間接メモリアクセスをする場合にも有効である。
【００８２】
図７Ａ及び図７Ｂは、本発明の第２の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００８３】
フォルスシェアリングは、図５Ａを用いて前述したように、異なるプロセッシングエレメントによって処理されたデータがキャッシュメモリの１ライン上に格納されることによって発生する。このため、本実施の形態では、図７Ａに示すように、キャッシュメモリのラインの境界によって、各プロセッシングエレメントが処理するデータを分け、複数のプロセッシングエレメントによって処理されるデータがキャッシュメモリの１ライン上に格納されないようにする。
【００８４】
まず、図７Ｂに示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（７００）。
【００８５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１６）を処理し（７０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１６≦ｉ＜３６）を処理する（７０２）。その後、ＰＥ０が処理の結果をキャッシュメモリ１０２から集中共有メモリ１６０に書き戻し、ＰＥ１が処理の結果をキャッシュメモリ１１２から集中共有メモリ１６０に書き戻す。
【００８６】
本実施の形態では、１ラインは４個の変数が格納できる容量を有するので、各プロセッシングエレメントが、キャッシュラインサイズである４の倍数の配列変数の要素を処理するようにしている。このため、図７Ａに示すように、ＰＥ０のアクセス範囲とＰＥ１のアクセス範囲とはキャッシュメモリのラインの境界で分けられ、ＰＥ０とＰＥ１とはキャッシュメモリの同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００８７】
なお、本実施の形態ではＰＥ０に１６個、ＰＥ１に２０個の配列変数の処理を割り当てたが、キャッシュラインサイズ（１ラインに格納できる配列変数の要素数）の倍数になるように分ければ、ＰＥ０に２０個、ＰＥ１に１６個の配列変数の処理を割り当てても、よい。また、各プロセッシングエレメントの処理能力の比に従って数の配列変数の処理を割り当ててもよい。
【００８８】
なお、本実施の形態では、キャッシュラインサイズ、配列変数の要素の数及びプロセッシングエレメントの数によっては、各プロセッシングエレメントに割り当てられる配列変数の要素の数が等しくならず、プロセッシングエレメントの処理負荷の不均衡が生じる場合がある。このため、本実施の形態は、配列サイズが十分に大きく、不均衡が配列サイズに比べて無視できるほど小さい場合に有効である。
【００８９】
図８Ａ及び図８Ｂは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法を説明する図である。
【００９０】
第３の実施の形態では、処理の境界においてノンキャッシャブル領域を用いることによって、フォルスシェアリングの発生を避ける。
【００９１】
まず、図８Ｂに示すように、グローバル変数ａ及び変数ｎｃｂｕｆが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置され、配列変数４個のサイズの変数ｎｃｂｕｆがノンキャッシャブル領域に設けられる（８００）。
【００９２】
ノンキャッシャブル領域とは、プロセッシングエレメントが当該領域に格納されたデータをメモリから読み込んだ場合に、当該読み込まれたデータを各プロセッシングエレメントのキャッシュメモリにロードしないで使用される領域である。ノンキャッシャブル領域は、メモリの領域（アドレス）又は特定の変数をノンキャッシャブルに指定することによって、通常のキャッシャブル領域と区別される。このノンキャッシャブルの指定は、所定の設定ファイルによって予め定めておいてもよいし、変数を宣言する命令によって定めてもよい。
【００９３】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（１８、１９）をｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いてノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【００９４】
ＰＥ０は、その後又は処理８０３と並行して、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。このデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【００９５】
その後、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻す。
【００９６】
このように、第３の実施の形態では、図８Ａに示すように、ＰＥ１がノンキャッシャブルバッファを用いて演算した結果をＰＥ０のキャッシュメモリの変数に反映する。すなわち、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、一方のプロセシングエレメント（ＰＥ１）はキャッシュメモリ内に設けられたノンキャッシャブル領域に当該ライン上のデータを格納し、他方のプロセシングエレメント（ＰＥ０）はノンキャッシャブル領域のデータを集中共有メモリに格納するので、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【００９７】
なお、ライン８１１〜８１４に格納されたデータはＰＥ０のみによって使用され、ライン８１１〜８１４に格納されたデータはＰＥ０のみによって使用されるので、ライン８１１〜８１４及びライン８１６〜８１９をキャッシュメモリ上でローカライズしてもよい。ローカライズされたデータは、主記憶に書き戻されず、次にＰＥ０が使用するまでキャッシュメモリ上に保持される。同様に、ライン８１１〜８１４に格納されるべきデータ及びライン８１６〜８１９に格納されるべきデータをローカルメモリに格納してもよい。
【００９８】
すなわち、第５ライン８１５のみがキャッシュメモリ上（キャッシャブル領域上）にあればよく、そのほかの領域（ライン８１１〜８１４、ライン８１６〜８１９）はキャッシャブル領域上に存在していなくてもよい。
【００９９】
なお、本実施の形態ではメモリ上にノンキャッシャブル領域を設ける必要があるが、ノンキャッシャブル領域は、集中共有メモリ、分散共有メモリ等の何れのメモリに設けてもよい。また、本実施の形態では、ノンキャッシャブル領域からキャッシュメモリにデータをコピーする処理のオーバーヘッドが生じる。しかし、ノンキャッシャブルのバッファとして分散共有メモリを利用することによって、低オーバーヘッドでデータの転送を実現することができる。
【０１００】
この第３の実施の形態の方法は、前述した第２の実施の形態の方法によっては分割が不可能な場合や、配列が拡張できない場合に有効である。
【０１０１】
図８Ｃは、本発明の第３の実施の形態においてノンキャッシャブル領域が集中共有メモリ１６０に設けられた場合の例を示す。図８Ｃに示す例では、集中共有メモリ１６０の一部の領域がノンキャッシャブル領域に指定されている。
【０１０２】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を、ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いて集中共有メモリ１６０に設けられたノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【０１０３】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を集中共有メモリ１６０のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１０４】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１０５】
図８Ｄは、本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリ１０３に設けられた場合の例を示す。図８Ｄに示す例では、分散共有メモリ１０３の一部の領域がノンキャッシャブル領域に指定されている。
【０１０６】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（８０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を、ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を用いてＰＥ０の分散共有メモリ１０３に設けられたノンキャッシャブル領域上で処理し（８０２）、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（８０３）。
【０１０７】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を分散共有メモリ１０３のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（８０４）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１０８】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１０９】
図９Ａは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１１０】
図９Ａで説明する変形例は、前述した例と異なり、各プロセシングエレメントが自己のメモリ上で演算し、その演算結果をノンキャッシャブル領域に転送することによって、フォルスシェアリングの発生を避ける。このため、他のメモリ、プロセシングエレメント等へのアクセスを減らし、処理を高速化することができる。
【０１１１】
まず、図９Ａに示すように、グローバル変数ａ及び変数ｎｃｂｕｆ及びｌｏｃａｌｂｕｆ＿ｐｅ１が宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される。また、配列変数４個のサイズの変数ｎｃｂｕｆがノンキャッシャブル領域に設けられ、配列変数４個のサイズの変数ｌｏｃａｌｂｕｆ＿ｐｅ１がノンキャッシャブル領域に設けられる（９００）。なお、変数Ｌｏｃａｌｂｕｆ＿ｐｅ１はプロセッシングエレメント（ＰＥ１）１１０のみで使用されるので、ローカル変数でよい。
【０１１２】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）をｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）をｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１１３】
ＰＥ０は、その後又は処理９０４と並行して、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。このデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１１４】
その後、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻す。
【０１１５】
図９Ｂは、本発明の第３の実施の形態においてノンキャッシャブル領域が集中共有メモリ１６０に設けられ、演算領域（ｌｏｃａｌｂｕｆ＿ｐｅ１）がＰＥ１のメモリに設けられた場合の例を示す。この演算領域が設けられるＰＥ１のメモリは、ローカルメモリでも、分散共有メモリでも、キャッシュメモリでもよい。
【０１１６】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）を、ＰＥ１のメモリ上に設けられたｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３））を集中共有メモリ１６０に設けられたノンキャッシャブル領域上のｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１１７】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を集中共有メモリ１６０のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１１８】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１１９】
図９Ｃは、本発明の第３の実施の形態の方法におけるノンキャッシャブル領域が分散共有メモリ１０３に設けられ、演算領域（ｌｏｃａｌｂｕｆ＿ｐｅ１）がＰＥ１のメモリに設けられた場合の例を示す。図９Ｃに示す例では、分散共有メモリ１０３の一部の領域がノンキャッシャブル領域に指定されている。また、演算領域が設けられるＰＥ１のメモリは、ローカルメモリでも、分散共有メモリでも、キャッシュメモリでもよい。
【０１２０】
ＰＥ０が変数ａ［ｉ］（０≦ｉ＜１８）をキャッシュメモリ上で処理し（９０１）、ＰＥ１が変数ａ［ｉ］（１８、１９）を、ＰＥ１のメモリ上に設けられたｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３）を用いて処理し（９０２）、処理の結果（ｌｏｃａｌｂｕｆ＿ｐｅ１［ｉ］（ｉ＝２、３））をＰＥ０の分散共有メモリ１０３に設けられたノンキャッシャブル領域上のｎｃｂｕｆ［ｉ］（ｉ＝２、３）に書き込む（９０３）。その後、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（９０４）。
【０１２１】
その後、ＰＥ１で処理された変数ｎｃｂｕｆ［ｉ］（ｉ＝２、３）を分散共有メモリ１０３のノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（ｉ＝１８、１９）に書き込む（９０５）。これによって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０に転送される。
【０１２２】
このため、ＰＥ０が変数ａ［ｉ］（０≦ｉ＜２０）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）を集中共有メモリ１６０に書き戻しても、フォルスシェアリングは発生しない。
【０１２３】
図９Ａ〜図９Ｃに記載した変形例によると、自プロセシングエレメント上のメモリで境界部分の変数を演算するので、バスを介した他のプロセシングエレメントやメモリへのデータの転送が減り、処理を高速化することができる。
【０１２４】
図１０Ａ及び図１０Ｂは、本発明の第３の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１２５】
まず、図１０Ｂに示すように、グローバル変数ａ、ｎｃｂｕｆ＿ｐｅ０、ｎｃｂｕｆ＿ｐｅ１が宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置され、配列変数４個分のサイズの変数ｎｃｂｕｆ＿ｐｅ０及び変数ｎｃｂｕｆ＿ｐｅ１がノンキャッシャブル領域に設けられる（１０００）。この変数ｎｃｂｕｆ＿ｐｅ０は、ＰＥ０の分散共有メモリに配置され、変数ｎｃｂｕｆ＿ｐｅ１は、ＰＥ１の分散共有メモリに配置される。
【０１２６】
本実施の形態では、プロセッシングエレメント（ＰＥ０）１００がｉ＝０からｉ＝１７の変数ａを処理し、プロセッシングエレメント（ＰＥ１）１１０がｉ＝１８からｉ＝３５の変数ａを処理する。
【０１２７】
具体的には、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］（０≦ｉ＜１６）をキャッシュメモリ上で処理した（１００１）。また、ＰＥ０が変数ａ［ｉ］（ｉ＝１６、１７）を分散共有メモリ上のｎｃｂｕｆ＿ｐｅ０において処理し、処理の結果をＰＥ１の分散共有メモリのｎｃｂｕｆ＿ｐｅ１に書き込む（１００２）。
【０１２８】
これと並行して又は前後して、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］（ｉ＝１８、１９）を分散共有メモリ上のｎｃｂｕｆ＿ｐｅ１において処理し、処理の結果をＰＥ０の分散共有メモリのｎｃｂｕｆ＿ｐｅ０に書き込む（１００４）。また、ＰＥ１が変数ａ［ｉ］（２０≦ｉ＜３６）をキャッシュメモリ上で処理する（１００５）。
【０１２９】
また、ＰＥ０は、変数ｎｃｂｕｆ＿ｐｅ０［ｉ］（０≦ｉ＜４）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［ｉ］（１６≦ｉ＜２０）に書き込む（１００３）。なお、処理の結果のｎｃｂｕｆ＿ｐｅ０への書き込み（１００４）からｎｃｂｕｆ＿ｐｅ０のａ［ｉ］への書き込み（１００３）へのデータ依存によって、ＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がｎｃｂｕｆ＿ｐｅ０［ｉ］に格納されている。このため、ステップ１００３では、ＰＥ０によって処理された変数ａ［ｉ］（ｉ＝１６、１７）及びＰＥ１によって処理された変数ａ［ｉ］（ｉ＝１８、１９）がＰＥ０のキャッシュメモリ上に書き込まれる。
【０１３０】
その後、ＰＥ０及びＰＥ１が処理の結果を集中共有メモリ１６０に書き戻す。しかし、図５Ａを用いて前述した場合と異なり、ＰＥ０とＰＥ１との境界領域の変数ａ［ｉ］（１６≦ｉ＜２０）には同じデータが格納されているので、何れのプロセッシングエレメントがデータを書き戻しても、集中共有メモリ１６０に格納されるデータは変わらない。
【０１３１】
すなわち、第３の実施の形態では、各プロセシングエレメントは、ＰＥ０がアクセスする集中共有メモリの領域とＰＥ１がアクセスする集中共有メモリの領域との境界部分は、分散共有メモリ上のデータを使用して計算をする。
【０１３２】
なお、ＰＥ０のｎｃｂｕｆ＿ｐｅ０と、ＰＥ１のｎｃｂｕｆ＿ｐｅ１とは、互いに書き込まれることによって、同じ値が格納されている。このため、ＰＥ０が、変数ｎｃｂｕｆ＿ｐｅ０を集中共有メモリに書き込んだ場合、変数ｎｃｂｕｆ＿ｐｅ１のｉ＝２、３も集中共有メモリに書き込まれており、ｎｃｂｕｆ＿ｐｅ０又はｎｃｂｕｆ＿ｐｅ１のいずれかが集中共有メモリに書き込まれることによって、他方のデータも集中共有メモリに書き込まれる。
【０１３３】
このように、第３の実施の形態では、図１０Ａに示すように、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、両方のプロセシングエレメントの分散共有メモリ内に設けられたノンキャッシャブル領域に当該ライン上のデータを格納し、両方のノンキャッシャブル領域のデータをコピーすることによって、両ノンキャッシャブル領域のデータが一致し、何れのデータを書き戻しても、フォルスシェアリングは発生しない。
【０１３４】
なお、本実施の形態では分散共有メモリ上にノンキャッシャブル領域を設ける必要があり、分散共有メモリ間でデータをコピーする処理のオーバーヘッドが生じる。
【０１３５】
図１１は、本発明の第４の実施の形態のフォルスシェアリングの発生を避ける方法の変形例を説明する図である。
【０１３６】
第４の実施の形態では、ローカル変数を用いることによって、フォルスシェアリングの発生を避ける。
【０１３７】
まず、図１１に示すように、グローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１１００）。
【０１３８】
その後、プロセシングエレメント０（ＰＥ０）１００が、ローカル変数ｌｏｃａｌ＿ａを宣言し（１１０１）、変数ａ［ｉ］（０≦ｉ＜１８）をローカル変数において処理し（１１０２）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］（０≦ｉ＜１８）をグルーバル変数ａ［ｉ］（０≦ｉ＜１８）へ書き込む（１１０３）。
【０１３９】
これと並行して又は前後して、プロセシングエレメント１（ＰＥ１）１１０が、ローカル変数ｌｏｃａｌ＿ａを宣言し（１１０４）、変数ａ［ｉ］（１８≦ｉ＜３６）をローカル変数において処理し（１１０５）、ｉ＝１８からｉ＝３５のローカル変数ｌｏｃａｌ＿ａ［ｉ］（１８≦ｉ＜３６）をグルーバル変数ａ［ｉ］（１８≦ｉ＜３６）に書き込む（１１０６）。
【０１４０】
ステップ１１０６には、ステップ１１０３からのデータ依存が設定されているので、ステップ１１０６のｌｏｃａｌ＿ａ［ｉ］をａ［ｉ］に書き込む前に、ａ［ｉ］（ｉ＝１６、１７）を集中共有メモリ１６０からロードする。このため、ステップ１００６では、ＰＥ０で更新されたａ［１６］及びａ［１７］を、ａ［１８］及びａ［１９］と共に集中共有メモリに書き戻す。
【０１４１】
このように、第４の実施の形態では、図１１に示すように、複数のプロセシングエレメントがローカル変数を用いてデータを更新し、各プロセシングエレメントがローカル変数をグローバル変数に書き戻す。このため、第４の実施の形態では、フォルスシェアリングは発生しない。
【０１４２】
なお、本実施の形態ではプロセシングエレメント間でデータをコピーする処理のオーバーヘッドが生じる。
【０１４３】
次に、多次元配列を扱う場合について説明する。
【０１４４】
図１２Ａ及び図１２Ｂは、多次元配列を扱う場合、配列変数の要素間でフォルスシェアリングが発生する例を説明する図である。
【０１４５】
まず、図１２Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１２００）。キャッシュメモリの１ラインには４個の変数が格納できる。このため、図１２Ａに示すように、キャッシュメモリの第１ライン１２１１にはａ［０］［０］からａ［０］［３］が存在し、第２ライン１２１２にはａ［０］［４］からａ［１］［１］が存在し、第５ライン１２１５にはａ［２］［４］、ａ［２］［５］、ａ［３］［０］、ａ［３］［１］が存在する。
【０１４６】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１２０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］］（３≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理し（１２０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻す。
【０１４７】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。また、前述したように、キャッシュラインの境界でループを分割できれば、フォルスシェアリングは発生しない。しかし、ＰＥ０によって処理されるａ［２］［４］及びａ［２］［５］と、ＰＥ１によって処理されるａ［３］［０］及びａ［３］［１］とが第５ライン１２１５上に存在することから、このライン上でＰＥ０によるアクセスとＰＥ１によるアクセスとが競合しフォルスシェアリングが発生する。
【０１４８】
図１３Ａ及び図１３Ｂは、第１の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１４９】
第１の実施の形態では、キャッシュラインの境界でループを分割するために、配列変数の各要素を外側ループのパラメータ毎に異なるラインに配置する。
【０１５０】
まず、図１３Ｂに示すように、６×１０の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１３００）。この配列の各変数ａ［ｉ］［ｊ］は、外側ループのパラメータ毎に異なるラインに配置される。
【０１５１】
本実施の形態では、キャッシュメモリの１ラインには４個の変数が格納でき、必要な変数は６×６の配列であるので、ラインサイズ（４個）の余分な変数を設けて、６×１０の配列変数を定義した。
【０１５２】
なお、ラインサイズ−１個の余分な変数を設ければよい。
【０１５３】
さらに、一般化すると、余分な配列変数の数の最低値は、下式が０以上となるＳの最低値によって与えられる。
【０１５４】
余分な配列変数の数の最低値＝Ｓ（４）の倍数−ｊmax
Ｓ：ラインサイズ
ｊmax：配列変数の外側ループより一つ内側のループの数（６）
【０１５５】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１３０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理し（１３０２）、ＰＥ０及びＰＥ１が処理の結果をキャッシュメモリ１０２及び１１２から集中共有メモリ１６０に書き戻した。
【０１５６】
キャッシュメモリ１０２及び１１２から集中共有メモリ１６０へのデータの書き戻しは、ライン単位で行われる。しかし、図１２を用いて前述した場合と異なり、図１３Ｂに示すように、ＰＥ０とＰＥ１とはキャッシュメモリの同じラインにアクセスしない。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１５７】
なお、本実施の形態では、余分な変数が確保されるので、キャッシュメモリの利用効率が低下する。このため、本実施の形態は、配列変数の要素の数が少ないい場合、具体的には、下式を満たす場合に有効である。
【０１５８】
図１４Ａ及び図１４Ｂは、第２の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１５９】
第２の実施の形態では、キャッシュメモリのラインの区切りによって、各プロセッシングエレメントが処理するデータを分け、複数のプロセッシングエレメントによって処理されたデータがキャッシュメモリの１ライン上に格納されないようにする。
【０１６０】
まず、図１４Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１４００）。
【０１６１】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜４、０≦ｊ＜６）をキャッシュメモリ１０２上で処理し（１４０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ１１２上で処理する（１４０２）。その後、ＰＥ０が処理の結果をキャッシュメモリ１０２から集中共有メモリ１６０に書き戻し、ＰＥ１が処理の結果をキャッシュメモリ１１２から集中共有メモリ１６０に書き戻す。
【０１６２】
本実施の形態では、図１４Ａに示すように、１ラインは４個の変数が格納できる容量を有するが、ａ［３］［６］と、ａ［４］［０］とは異なるライン上に存在する。このため、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１６３】
なお、本実施の形態ではＰＥ０に２４個、ＰＥ１に１２個の配列変数の処理を割り当てたが、キャッシュラインサイズの倍数になるように分ければ、ＰＥ０に１２個、ＰＥ１に２４個の配列変数の処理を割り当てても、よい。また、各プロセッシングエレメントの処理能力の比に従って数の配列変数の処理を割り当ててもよい。
【０１６４】
なお、本実施の形態では、対象の次元以下の配列変数の要素のサイズがラインサイズの倍数となればループ分割が可能である。この場合、配列変数の要素の数及びプロセッシングエレメントの数によって割り当てられる配列変数の数が等しくならず、プロセッシングエレメントの処理負荷の不均衡が生じる場合がある。このため、本実施の形態は、配列サイズが十分に大きく、不均衡が配列サイズに比べて無視できるほど小さい場合に有効である。
【０１６５】
図１５Ａ及び図１５Ｂは、第３の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１６６】
第３の実施の形態では、ノンキャッシャブル領域を用いて、フォルスシェアリングの発生を避ける。
【０１６７】
まず、図１５Ｂに示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される。また、１×６の１次元の配列変数ｎｃ＿ｂｕｆ２が宣言され、変数ｎｃ＿ｂｕｆ２が変数６個（内側ループの数）のサイズのノンキャッシャブル領域が設けられる（１５００）。
【０１６８】
その後、プロセッシングエレメント（ＰＥ０）１００が変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をキャッシュメモリ上で処理し（１５０１）、プロセッシングエレメント（ＰＥ１）１１０が変数ａ［３］［ｊ］（０≦ｊ＜６）をｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）を用いてノンキャッシャブル領域上で処理し（１５０２）、ＰＥ１が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）をキャッシュメモリ上で処理する（１５０３）。
【０１６９】
ＰＥ０は、その後又は処理１５０３と並行して、ＰＥ１で処理された変数ｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）をノンキャッシャブル領域から読み出し、ＰＥ０のキャッシュメモリの変数ａ［３］［ｊ］（０≦ｊ＜６）に書き込む（１５０４）。これによって、ＰＥ１によってｎｃ＿ｂｕｆ２［０］［ｊ］（０≦ｊ＜６）を用いて処理された変数ａ［３］［ｊ］（０≦ｊ＜６）がＰＥ０に転送される。
【０１７０】
その後、ＰＥ０が変数ａ［ｉ］［ｊ］（０≦ｉ＜４、０≦ｊ＜６）を集中共有メモリ１６０に書き戻し、ＰＥ１が変数ａ［ｉ］［ｊ］（４≦ｉ＜６、０≦ｊ＜６）を集中共有メモリ１６０に書き戻す。
【０１７１】
このように、第３の実施の形態では、図１５Ａに示すように、ＰＥ１がノンキャッシャブルバッファを用いて演算した結果をＰＥ０のキャッシュメモリの変数に反映する。すなわち、複数のプロセシングエレメントが同じライン上のデータにアクセスする場合、一方のプロセシングエレメント（ＰＥ１）はノンキャッシャブル領域に当該ライン上のデータを格納し、他方のプロセシングエレメント（ＰＥ０）はノンキャッシャブル領域のデータを集中共有メモリのキャッシャブル領域に格納するので、複数のプロセシングエレメントが同じラインにデータを書き戻すことがなく、フォルスシェアリングは発生しない。
【０１７２】
なお、本実施の形態ではメモリ上にノンキャッシャブル領域を設ける必要があるが、ノンキャッシャブル領域は、集中共有メモリ、分散共有メモリ等の何れのメモリに設けてもよい。また、本実施の形態では、ノンキャッシャブル領域からキャッシュメモリにデータをコピーする処理のオーバーヘッドが生じる。しかし、ノンキャッシャブルのバッファとして分散共有メモリを利用することによって、低オーバーヘッドでデータの転送を実現することができる。
【０１７３】
図１６は、第４の実施の形態を２次元配列変数に適用した例を説明する図である。
【０１７４】
まず、図１６に示すように、６×６の２次元配列のグローバル変数ａが宣言され、変数ａが集中共有メモリのラインの先頭（キャッシュメモリのラインの先頭）に配置される（１６００）。
【０１７５】
その後、プロセシングエレメント０（ＰＥ０）１００が、６×６の２次元配列のローカル変数ｌｏｃａｌ＿ａを宣言し（１６０１）、変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］を用いて処理し（１６０２）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）をグルーバル変数ａ［ｉ］［ｊ］（０≦ｉ＜３、０≦ｊ＜６）へ書き込む（１６０３）。
【０１７６】
これと並行して又は前後して、プロセシングエレメント１（ＰＥ１）１１０が、６×６の２次元配列のローカル変数ｌｏｃａｌ＿ａを宣言し（１６０４）、変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］を用いて処理し（１６０５）、ローカル変数ｌｏｃａｌ＿ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）をグルーバル変数ａ［ｉ］［ｊ］（３≦ｉ＜６、０≦ｊ＜６）へ書き込む（１６０６）。
【０１７７】
ステップ１６０６には、ステップ１１０３からのデータ依存が設定されているので、ステップ１６０６のｌｏｃａｌ＿ａ［ｉ］［ｊ］をａ［ｉ］［ｊ］に書き込む前に、ａ［２］［４］、ａ［２］［５］を集中共有メモリ１６０からロードする。このため、ステップ１００６では、ＰＥ０で更新されたａ［２］［４］及びａ［２］［５］を、ａ［３］［０］及びａ［３］［１］と共に集中共有メモリに書き戻す。
【０１７８】
このように、第４の実施の形態では、図１６に示すように、複数のプロセシングエレメントがローカル変数を用いてデータを更新し、各プロセシングエレメントがローカル変数をグローバル変数に書き戻す。このため、第４の実施の形態では、フォルスシェアリングは発生しない。
【０１７９】
なお、本実施の形態ではプロセシングエレメント間でデータをコピーする処理のオーバーヘッドが生じる。
【０１８０】
以上説明した実施の形態及び変形例は、プログラムのコンパイル時に一つ又は複数を組み合わせて用いることができる。
【０１８１】
次に、コンパイラが、フォルスシェアリングを回避するために最適な方法を選択する手順について説明する。
【０１８２】
図１７Ａは、本発明の実施の形態のループ分割前の処理を示すマクロタスクグラフである。
【０１８３】
ステップ１７１０のタスクは、変数ｉを制御変数とするループであり、ループ分割により生成する部分タスクをそれぞれ別々のプロセッシングエレメントにスケジューリングすることにより並列処理を行う。このタスクを最大分割数でループ分割を行う場合、つまりｉループの１イタレーション分の処理を一つの部分タスクとなるようにループ分割した場合に生成される各部分タスクでは、２次元の配列変数Ａについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があるということがデータアクセス範囲解析により解析される。同様にステップ１７２０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を使用する可能性があり、ステップ１７３０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を使用する可能性があり、ステップ１７４０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があり、ステップ１７５０のタスクでは、２次元の配列変数Ｂについて１次元目の０から９９までの要素、２次元目はｉからｉまでの要素を変更する可能性があることが解析される。ここで、各タスクを最大分割数で分割した場合のアクセス範囲を考慮しているのは、任意の分割パターンでタスク分割を行った場合に、フォルスシェアリングが発生する可能性があるかどうかを解析するためである。
【０１８４】
各タスクの各部分タスクにおけるデータのアクセス範囲から、フォルスシェアリングが発生する可能性のある箇所とその要因となる配列変数およびその配列次元を解析する。具体的には、前述の部分タスクにおけるデータアクセス範囲において、分割元のタスクにおけるループ制御変数が含まれている次元のうち最も下位の次元において、その下位次元の部分配列サイズをキャッシュメモリのラインサイズで除したときに余りが発生する場合、フォルスシェアリングが発生する可能性があると判断できる。その場合、当該配列の更新を行うタスクの分割後の各部分タスクの間、あるいは当該配列の更新を行うタスクの分割後の各部分タスクとその配列を使用するタスクの分割後の各部分タスクの間でフォルスシェアリングが発生する可能性がある。
【０１８５】
なお、変数をメモリへ格納する方法がプログラム言語によって異なるので、どの添字を１次元目とするかは、変数のメモリへの格納方法によって異なる。すなわち、メモリの連続した領域に格納される配列変数の要素で変化する添字と最内周ループを構成する添字とが異なる場合、コンパイラは、必要に応じて、計算順序を変えるインターチェンジを行ってもよい。
【０１８６】
また、配列変数が集中共有メモリ１６０のラインの先頭にアラインされていない場合、上記の条件にかかわらずフォルスシェアリングが発生する可能性があると解析される。
【０１８７】
図１７Ｂは、本発明の実施の形態のループ分割後の処理を示すマクロタスクグラフである。本例では各タスクの分割数を３としているが、この分割数は任意に設定することが可能である。
【０１８８】
図１７Ｂ中、実線（１本線）は、プログラム上のデータ依存を示し、２重線は、フォルスシェアリングが発生する可能性がある箇所を示す。
【０１８９】
なお、フォルスシェアリングを検出するコードの例を図１７Ｃに示す。
【０１９０】
図１８は、本発明の実施の形態の並列化コンパイラによるソフトウェアコヒーレンシ制御コードを生成する処理の概要を説明する図である。
【０１９１】
まず、コンパイルすべきプログラム２００１が並列化コンパイラ２００２に入力される。入力されるプログラム２００１は、Ｃ、Ｆｏｒｔｒａｎ等の言語で記述された逐次プログラムである。
【０１９２】
並列化コンパイラ２００２は、入力された逐次プログラムを並列化し、ノンコヒーレントキャッシュで実行するための制御コードが挿入された並列ＡＰＩプログラム２００３を生成する。生成される並列ＡＰＩプログラム２００３は、コヒーレンシ機能を持たないキャッシュメモリを用いてプログラムを実行するための指示（ＡＰＩ）を含む並列プログラム形式である。
【０１９３】
生成された並列ＡＰＩプログラム２００３は、コード生成コンパイラ２００４に入力される。コード生成コンパイラ２００４は、コヒーレンシ機能を持たないキャッシュメモリを用いてプログラムを実行するための指示（ＡＰＩ）を解釈しながら、プログラムを機械語命令（実行形式プログラム）２００５に変換する。この実行形式プログラム２００５にも、ノンコヒーレントキャッシュでプログラムを実行するための命令が含まれる。
【０１９４】
図１９は、本発明の実施の形態のコンパイラによって実行される処理のフローチャートである。
【０１９５】
まず、コンパイラは、コンパイルすべきプログラムの字句を解析し、プログラムの構文を解析する（２１０１）。
【０１９６】
構文の解析結果に基づいて、階層的なタスク、すなわち、プログラムの階層的マクロタスクによる表現を生成する（２１０２）。
【０１９７】
その後、生成されたタスク間の依存関係（制御フロー）を解析し（２１０３）、タスク間のデータ依存を解析し（２１０４）、各タスクによってアクセスされるデータの範囲を解析する（２１０５）。
【０１９８】
その後、プログラムの解析結果を使用して、プログラムが最も早く実行できる条件を解析し（２１０６）、最早実行条件の解析結果を使用して、並列処理区間やタスクが割り当てられるプロセッサ数を決定し、マクロタスクグラフを生成する。
【０１９９】
その後、マクロタスクグラフにおけるデータ依存関係から、図１７Ａ、図１７Ｂ、図１７Ｃを用いて説明した方法によってフォルスシェアリングを検出し、フォルスシェアリングが検出された箇所及びフォルスシェアリングが検出された変数を含むフォルスシェアリング情報を生成する（２１０７）。
【０２００】
その後、生成されたフォルスシェアリング情報に基づいて、フォルスシェアリングが検出された箇所毎に、フォルスシェアリングを回避する方法が決定され、決定された方法に従って命令が挿入され、フォルスシェアリングが回避された並列プログラムが生成される（２１０８）。このフォルスシェアリング回避処理については、図２０Ａ及び図２０Ｂを用いて詳述する。
【０２０１】
その後、各タスクの実行順序を決定するタスクスケジューリングを実行し（２１０９）、ステイルデータに対処するためのキャッシュ操作指示を挿入する（２１１０）。これによって、コヒーレンシ制御機能つき並列プログラムが生成される。このキャッシュ操作指示の挿入処理については、図２１を用いて詳述する。
【０２０２】
図２０Ａ及び図２０Ｂは、本発明の実施の形態のフォルスシェアリング回避処理のフローチャートであり、コンパイル処理（図１９）のステップ２１０８から呼び出される。
【０２０３】
図２０Ａ及び図２０Ｂに示すフォルスシェアリング回避処理は、ステップ２１０７で検出されたフォルスシェアリング情報を入力とし、同じ配列に対して発生する各フォルスシェアリングについて以下の処理を行う。
【０２０４】
このフォルスシェアリング回避処理は、データレイアウト変換及びリストラクチャリングに大別され、図２０Ａにデータレイアウト変換処理を示し、図２０Ｂにリストラクチャリング処理を示す。
【０２０５】
まず、処理の対象となる配列変数が変換可能であるか否かを判定する（２１２１）。例えば、この配列変数がコンパイルされるプログラム中で閉じている場合、具体的には、コンパイルされるプログラム中で宣言されており、かつ、このプログラム外で定義される関数の引数とならない場合、データレイアウトの変換によりプログラムが予期せぬ動作をする可能性がないので、配列変数が変換可能であると判定する。
【０２０６】
その結果、配列が変換不可能であると判定された場合、配列の拡張又はパディング等のデータレイアウトの変換が困難であるため、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２０７】
一方、配列が変換可能であると判定された場合、配列の最速変化次元の要素間でフォルスシェアリングが発生するか否かを判定する（２１２２）。具体的には、Ｎ次元配列において、最速変化次元を１次元目、最遅変化次元をＮ次元目と定義する。最速変化次元とは、添字が連続的に変化する配列の次元である。例えば、Ｎ次元配列がループによって処理される場合、ループの最内周が最速変化次元となり、ループの最外周が最遅変化次元となる。すなわち、最速変化次元のデータはメモリ上の連続した領域に配置される。
【０２０８】
その結果、最速変化次元の要素間でフォルスシェアリングが発生すると判定された場合、配列の拡張が可能か否かを判定する（２１２３）。ステップ２１２３では、配列を拡張してもキャッシュ利用効率の低下に起因する性能の低下が小さいか否かを判定する。例えば、配列サイズが十分に小さい場合、図６Ａに示すように配列を拡張しても、キャッシュ利用効率の低下に起因する性能低下が小さいことから、配列の拡張が可能であると判定する。具体的には、下式（１）を満たす場合、配列サイズが十分に小さいので、配列の拡張が可能であると判定することができる。
【０２０９】
Ｓａ１≦Ｓ×Ｎ ・・・（１）
Ｓａ１：対象の配列の１次元目の宣言サイズ
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２１０】
その結果、配列の拡張が可能であると判定された場合、プログラム中に図６Ｂに示すコードを挿入することによって、図６Ａに示すように、配列を拡張する。一方、配列の拡張が困難であると判定された場合、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２１１】
一方、ステップ２１２２で、最速変化次元以外の次元の要素間でフォルスシェアリングが発生すると判定された場合、配列のパディングが可能か否かを判定する（２１２５）。ステップ２１２５では、配列をパディングしてもキャッシュ利用効率の低下に起因する性能の低下が小さいか否かを判定する。例えば、配列サイズが十分い大きい場合、図１３Ａに示すように配列をパディングしてもキャッシュ利用効率の低下に起因する性能低下が小さいことから、配列のパディングが可能であると判定する。具体的には、下式（２）を満たす場合、配列サイズが十分に小さいので、配列のパディングが可能であると判定することができる。
【０２１２】
Ｓａ２≧Ｓ×Ｎ ・・・（２）
Ｓａ２：対象の配列変数でフォルスシェアリングが発生する次元以下の部分配列サイズ
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２１３】
その結果、配列の拡張が可能であると判定された場合、図１３Ｂに示すコードをプログラム中に挿入することによって、図１３Ａに示すように、配列を拡張する。一方、配列の拡張が困難であると判定された場合、ステップ２１３１（図２０Ｂ）に進み、リストラクチャリングを行う。
【０２１４】
図２０Ｂに示すリストラクチャリング処理では、検出されたフォルスシェアリング情報のうち、データレイアウト変換で対処できなかったフォルスシェアリングに対して、以下の処理を行う。
【０２１５】
まず、各プロセッサによる処理の境界領域のみでフォルスシェアリングが発生するか否かを判定する（２１３１）。具体的には、処理の対象となる配列へのアクセスが連続アクセスになっているか否かを判定する。例えば、並列化後に各プロセッサがアクセスする領域が重複している場合（ＰＥ０がｉ、ｉ＋２、ｉ＋４…とアクセスし、ＰＥ１がｉ＋１、ｉ＋３、ｉ＋５…とアクセスする場合）、処理の対象となる配列へのアクセスは連続アクセスとならないことから、境界領域以外でもフォルスシェアリングが発生する。
【０２１６】
その結果、境界領域以外でもフォルスシェアリングが発生すると判定された場合、ステップ２１３９へ進む。
【０２１７】
一方、境界領域のみでフォルスシェアリングが発生すると判定された場合、フォルスシェアリングが発生すると判定された場所がループによる並列処理であるか否かを判定する（２１３２）。
【０２１８】
その結果、ループによる並列処理以外でフォルスシェアリングが発生すると判定された場合、ステップ２１３９へ進む。
【０２１９】
一方、ループによる並列処理においてフォルスシェアリングが発生すると判定された場合、キャッシュラインの境界でループを分割できるか否かを判定する（２１３３）。
【０２２０】
その結果、キャッシュラインの境界でループを分割できないと判定された場合、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３８）。
【０２２１】
一方、キャッシュラインの境界でループを分割できると判定された場合、ループの分割に起因する負荷の不均衡による性能低下が小さいか否かを判定する（２１３４）。例えば、ループ回転数が十分に大きい場合、ループの分割に起因する負荷の不均衡による影響は小さいと判定できる。具体的には、下式（３）を満たす場合、ループ回転数が十分に大きいので、負荷の不均衡による影響は小さいと判定することができる。
【０２２２】
Ｒ≧Ｓ×Ｎ ・・・（３）
Ｒ：ループ回転数
Ｓ：キャッシュラインサイズ
Ｎ：使用するプロセッサ数
【０２２３】
また、各プロセッサにタスクを均等に分割した場合、分割されたタスクによって使用されるデータ量（アクセス範囲）の最大値と最小値との差をラインサイズと比較し、この差がラインサイズより小さい場合に負荷不均衡による影響が小さいと判定してもよい。
【０２２４】
その結果、ループの分割による負荷の不均衡による影響が大きいと判定された場合、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３８）。なお、図１０Ａ、図１０Ｂに示す方法を用いてもよく、多次元配列の場合は図１５Ａ、図１５Ｂに示す方法を用いる。
【０２２５】
一方、ループの分割による負荷の不均衡による影響は小さいと判定された場合、キャッシュラインの境界のみでループを分割できるか否かを判定する（２１３５）。例えば、配列変数の要素ａ［ｉ］及びａ［ｉ＋１］に同じループ内でアクセスされる場合、キャッシュラインの境界のみでループを分割することはできない。
【０２２６】
その結果、キャッシュラインの境界のみでループを分割できると判定された場合、図７Ｂに示すコードをプログラム中に挿入することによって、図７Ａに示すように、キャッシュラインの境界でループを分割する（２１３６）。なお、多次元配列の場合は図１５Ａ、図１５Ｂに示す方法を用いる。
【０２２７】
一方、配列変数ａ［ｉ］及びａ［ｉ＋１］に同じループ内でアクセスされる場合、キャッシュラインの境界のみではループを分割できない場合、キャッシュラインの境界でループを分割できる箇所（例えば、ａ［ｉ］が分割される箇所）には、図７Ｂに示すコードをプログラム中に挿入する。さらに、キャッシュラインの境界でループを分割できない箇所（例えば、ａ［ｉ＋１］が分割される箇所）には、図８Ｂに示すコードをプログラム中に挿入することによって、図８Ａに示すように、バッファを用いてプロセッシングエレメント間で通信する（２１３７）。
【０２２８】
例えば、ａ［ｉ］は、キャッシュラインの境界でループを分割し、ａ［ｉ＋１］については、バッファを用いてプロセッシングエレメント間で通信するとよい。この場合、ａ［ｉ］のアクセス回数とａ［ｉ＋１］のアクセス回数とを比較し、アクセス回数が多い配列変数の要素の添字について、キャッシュラインの境界でループを分割して、バッファに格納されたデータの通信のオーバーヘッドを少なくするとよい。
【０２２９】
一方、ステップ２１３９では、各プロセッシングエレメントにおける演算に用いられるプライベート変数からグローバル変数へのコピー処理のオーバーヘッドが小さいか否かを判定する。具体的には、ループ中で実行される計算の処理量が十分に大きい場合、コピー処理のオーバーヘッドは無視できる程度の小さい。例えば、単に他の変数のデータをａへ代入（コピー）する場合、ループ中で実行される計算の処理量は小さいが、ループ中で四則演算や関数による計算結果をａへ代入している場合、ループ中で実行される計算の処理量は大きくなる。
【０２３０】
その結果、変数のコピー処理のオーバーヘッドが小さいと判定された場合、図１１に示すコード（多次元配列の場合は図１６に示すコード）をプログラム中に挿入することによって、各プロセッシングエレメントにおいて定義されたプライベート変数を用いて演算をし、演算の結果をプライベート変数からグローバル変数へコピーする（２１４０）。
【０２３１】
一方、変数のコピー処理のオーバーヘッドが大きいと判定された場合、各プロセッシングエレメントによる演算の結果を、逐次、集中共有メモリ１６０に書き込む（２１４１）。
【０２３２】
図２１は、本発明の実施の形態のキャッシュ操作指示の挿入処理のフローチャートである。
【０２３３】
まず、並列化フェイズにおけるタスクグラフのスケジューリング結果において、異なるプロセッサに割り当てられたタスク間のデータ依存を解析する（２１５１）。
【０２３４】
解析されたデータの依存関係が、フロー依存又は出力依存であるか否かを判定する（２１５２）。その結果、解析されたデータの依存関係がフロー依存又は出力依存である場合、キャッシュ操作指示を挿入する。
【０２３５】
具体的には、図３Ｂを用いて前述したように、データを生産する側のプロセシングエレメントが、データを更新後にライトバック命令によって主記憶（集中共有メモリ１６０）に更新されたデータを書き戻すキャッシュ操作指示と、データを消費する側のプロセシングエレメントが、データを消費する前にセルフインバリデート命令によって主記憶からデータを読み込むキャッシュ操作指示と生成し、生成されたキャッシュ操作指示をプログラム中に挿入する。このとき、生産側のプロセシングエレメントによるデータの更新の終了はフラグによって消費側のプロセシングエレメントに通知され、消費側のプロセシングエレメントはフラグの更新によってデータの更新を知り、更新されたデータを主記憶から読み込むように制御される。コンパイラは、このフラグによる制御命令を生成し、生成された制御命令をプログラム中に挿入する。
【０２３６】
一方、解析されたデータの依存関係がフロー依存でも出力依存でもない場合、キャッシュ操作指示の挿入処理を終了する。
【０２３７】
以上説明したように、本発明の実施の形態によると、ソフトウェアによる制御によって、コヒーレンシ制御のためのハードウェアが不要となり、ハードウェアを簡素化できる。このため、低コストかつ低消費電力のマルチプロセッサを実現できる。また、コンパイラの最適化によって、スケーラブルな性能向上が可能となる。
【０２３８】
特許請求の範囲に記載した以外の本発明の観点の代表的なものとして、次のものがあげられる。
【０２３９】
（１）複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備えるマルチプロセッサシステムであって、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントは、
前記主記憶装置から読み込んだデータを前記キャッシュメモリに一時的に格納し、
使用が終了したデータを前記キャッシュメモリから、前記キャッシュメモリの管理単位に従って、前記主記憶装置に書き戻し、
前記プログラムを分割して生成される各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納することを特徴とするマルチプロセッサシステム。
【０２４０】
（２）前記プロセッシングエレメントは、少なくとも第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記第１のプロセッシングエレメントは、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算し、
前記第２のプロセッシングエレメントは、
前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記ノンキャッシャブル領域で演算し、
前記ノンキャッシャブル領域で演算した結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送することを特徴とする（１）に記載のマルチプロセッサシステム。
【０２４１】
（３）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記各プロセッシングエレメントは、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算し、
前記第１のプロセッシングエレメントは、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込むことを特徴とする（１）に記載のマルチプロセッサシステム。
【０２４２】
（４）異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻し、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化することを特徴とする（１）から（３）のいずれか一つに記載のマルチプロセッサシステム。
【０２４３】
（５）マルチプロセッサシステムに備わるプロセッサにおいて演算処理を実行させるプログラムであって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリの管理単位に従ってデータが転送され、
前記プログラムは、各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順を含むことを特徴とするプログラム。
【０２４４】
（６）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算する手順と、
前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順と、
前記第２のプロセッシングエレメントが、前記ノンキャッシャブル領域に格納された演算結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送する手順とを含むことを特徴とする（５）に記載のプログラム。
【０２４５】
（７）前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算する手順と、
前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込む手順とを含むことを特徴とする（５）に記載のプログラム。
【０２４６】
（８）異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻す手順と、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化する手順とを含むことを特徴とする（５）から（７）のいずれか一つに記載のプログラム。
【符号の説明】
【０２４７】
１００、１１０、１２０ プロセシングエレメント
１０１、１１１、１２１ プロセッサ
１０２、１１２、１２２ キャッシュメモリ
１５０ 内部結合網
１６０ 集中共有メモリ（主記憶）
【特許請求の範囲】
【請求項１】
マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを、コンパイラによって生成する方法であって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリの管理単位に従ってデータが転送され、
前記方法は、
前記プロセッサによって実行されるプログラムを解析し、
前記プログラムに含まれる各タスクの実行に必要なデータを解析し、
前記解析の結果に基づいて、前記各タスクを分割した場合、前記分割されたタスクによって使用されるデータの境界がメモリの管理単位と整合するか否かを判定し、
前記タスクによって使用されるデータの境界がメモリの管理単位と整合しないと判定された場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設けるコードと、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納するコードとを生成することを特徴とするコードの生成方法。
【請求項２】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記プログラムの解析結果に基づいて、前記第１のプロセッシングエレメントによって実行されるタスクと前記第２のプロセッシングエレメントによって実行されるタスクとの境界がメモリの管理単位と整合しないと判定された場合、前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算するコードと、前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納するコードと、前記ノンキャッシャブル領域に格納された演算結果を前記第１のプロセッシングエレメントのキャッシュメモリに転送するコードとを生成することを特徴とする請求項１に記載のコードの生成方法。
【請求項３】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメントに設けられ、
前記プログラムの解析結果に基づいて、前記第１のプロセッシングエレメントによって実行されるタスクと前記第２のプロセッシングエレメントによって実行されるタスクとの境界がメモリの管理単位と整合しないと判定された場合、前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算するコードと、前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込むコードとを生成することを特徴とする請求項１に記載のコードの生成方法。
【請求項４】
前記ノンキャッシャブル領域を前記主記憶装置に設ける命令又は設定文を生成することを特徴とする請求項１又は２に記載のコードの生成方法。
【請求項５】
前記各プロセッシングエレメントは、前記各プロセッシングエレメントからアクセス可能な分散共有メモリ備え、
前記ノンキャッシャブル領域を前記分散共有メモリに設ける命令又は設定文を生成することを特徴とする請求項１から３のいずれか一つに記載のコードの生成方法。
【請求項６】
前記プログラムの解析結果に基づいて、前記分割されたタスクが前記主記憶の複数の領域にアクセスすると判定された場合、タスクによって使用されるデータの境界と整合する前記メモリの管理単位については、当該管理単位に整合するように前記タスクを分割し、前記タスクによって使用されるデータの境界と整合しない管理単位については、データが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を用いて、当該境界を含む前記管理単位に格納されたデータを演算するコードを生成することを特徴とする請求項１から５のいずれか一つに記載のコードの生成方法。
【請求項７】
前記プログラムの解析結果に基づいて、前記タスクによって使用されるデータが、当該プログラムにおいて宣言され、当該プログラムのみで使用されると判定された場合、当該データの複数の要素が前記各管理単位に配置されないように配列を拡張するコードを生成することを特徴とする請求項１から６のいずれか一つに記載のコードの生成方法。
【請求項８】
前記タスクによって使用されるデータは配列変数であって、
前記プログラムの解析結果に基づいて、前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が発生している箇所を判定し、
前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が、前記配列変数の要素が前記主記憶装置の連続する領域に格納される次元の要素間で発生している場合、前記配列変数の複数の要素が前記各管理単位に配置されないように前記配列変数を拡張するコードを生成し、
前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が、前記配列変数の要素が前記主記憶装置の連続する領域に格納される次元の要素間で発生していない場合、前記不整合が発生している次元より下位の複数の次元の前記配列変数の要素が前記各管理単位に配置されないように前記配列変数を拡張するコードを生成することを特徴とする請求項７に記載のコードの生成方法。
【請求項９】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記各プロセシングエレメント毎に、当該プロセシングエレメント内で使用されるローカル変数を定義するコードと、
前記各プロセッシングエレメントが前記定義されたローカル変数を用いて演算をするコードと、
前記第１のプロセシングエレメントが前記ローカル変数で演算した結果を主記憶装置に書き戻すコードと、
前記第２のプロセシングエレメントが前記第１のプロセシングエレメントによる演算結果を前記主記憶装置から読み込むコードと、
前記第２のプロセシングエレメントが前記主記憶装置から読み込んだデータを前記キャッシュメモリに書き込むコードとを含むことを特徴とする請求項１から８のいずれか一つに記載のコードの生成方法。
【請求項１０】
異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、前記データを生産するプロセシングエレメントが前記依存関係があるデータを前記主記憶装置に書き戻すコードと、前記データを消費するプロセシングエレメントが前記依存関係があるデータを無効化するコードとを生成することを特徴とする請求項１から９のいずれか一つに記載のコードの生成方法。
【請求項１１】
マルチプロセッサシステムに備わるプロセッサがプログラムを実行する際にメモリの記憶領域を管理する方法であって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記方法は、
前記プロセッシングエレメントが、前記主記憶装置から読み込んだデータを、前記キャッシュメモリの管理単位に従って、前記キャッシュメモリに一時的に格納する手順と、
前記プロセッシングエレメントによる使用が終了したデータを、前記キャッシュメモリの管理単位に従って、前記キャッシュメモリから前記主記憶装置に書き戻す手順と、
前記プログラムを分割して生成される各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順とを含むことを特徴とする記憶領域の管理方法。
【請求項１２】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算する手順と、
前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順と、
前記第２のプロセッシングエレメントが、前記ノンキャッシャブル領域に格納された演算結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送する手順とを含むことを特徴とする請求項１１に記載の記憶領域の管理方法。
【請求項１３】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算する手順と、
前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込む手順とを含むことを特徴とする請求項１１に記載の記憶領域の管理方法。
【請求項１４】
異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻し、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化することを特徴とする請求項１１から１３のいずれか一つに記載の記憶領域の管理方法。
【請求項１５】
マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを生成するプログラムであって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリのアクセス管理単位に従ってデータが転送され、
前記コード生成プログラムは、当該プログラムを実行する計算機に
前記プロセッサによって実行されるプログラムを解析する手順と、
前記プログラムに含まれる各タスクの実行に必要なデータを解析する手順と、
前記解析の結果に基づいて、前記プログラムを前記各タスクをに分割した場合に、前記分割されたタスクによって使用されるデータの境界がメモリのアクセス管理単位と整合するか否かを判定する手順と、
前記タスクによって使用されるデータの境界がメモリのアクセス管理単位と整合しないと判定された場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設けるコードと用いて、当該タスクによって使用されるデータの境界を含むアクセス管理単位に格納されたデータを演算結果を前記ノンキャッシャブル領域に格納するコードとを生成する手順とを実行させることを特徴とするコード生成プログラム。
【請求項１】
マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを、コンパイラによって生成する方法であって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリの管理単位に従ってデータが転送され、
前記方法は、
前記プロセッサによって実行されるプログラムを解析し、
前記プログラムに含まれる各タスクの実行に必要なデータを解析し、
前記解析の結果に基づいて、前記各タスクを分割した場合、前記分割されたタスクによって使用されるデータの境界がメモリの管理単位と整合するか否かを判定し、
前記タスクによって使用されるデータの境界がメモリの管理単位と整合しないと判定された場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設けるコードと、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納するコードとを生成することを特徴とするコードの生成方法。
【請求項２】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記プログラムの解析結果に基づいて、前記第１のプロセッシングエレメントによって実行されるタスクと前記第２のプロセッシングエレメントによって実行されるタスクとの境界がメモリの管理単位と整合しないと判定された場合、前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算するコードと、前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納するコードと、前記ノンキャッシャブル領域に格納された演算結果を前記第１のプロセッシングエレメントのキャッシュメモリに転送するコードとを生成することを特徴とする請求項１に記載のコードの生成方法。
【請求項３】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメントに設けられ、
前記プログラムの解析結果に基づいて、前記第１のプロセッシングエレメントによって実行されるタスクと前記第２のプロセッシングエレメントによって実行されるタスクとの境界がメモリの管理単位と整合しないと判定された場合、前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算するコードと、前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込むコードとを生成することを特徴とする請求項１に記載のコードの生成方法。
【請求項４】
前記ノンキャッシャブル領域を前記主記憶装置に設ける命令又は設定文を生成することを特徴とする請求項１又は２に記載のコードの生成方法。
【請求項５】
前記各プロセッシングエレメントは、前記各プロセッシングエレメントからアクセス可能な分散共有メモリ備え、
前記ノンキャッシャブル領域を前記分散共有メモリに設ける命令又は設定文を生成することを特徴とする請求項１から３のいずれか一つに記載のコードの生成方法。
【請求項６】
前記プログラムの解析結果に基づいて、前記分割されたタスクが前記主記憶の複数の領域にアクセスすると判定された場合、タスクによって使用されるデータの境界と整合する前記メモリの管理単位については、当該管理単位に整合するように前記タスクを分割し、前記タスクによって使用されるデータの境界と整合しない管理単位については、データが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を用いて、当該境界を含む前記管理単位に格納されたデータを演算するコードを生成することを特徴とする請求項１から５のいずれか一つに記載のコードの生成方法。
【請求項７】
前記プログラムの解析結果に基づいて、前記タスクによって使用されるデータが、当該プログラムにおいて宣言され、当該プログラムのみで使用されると判定された場合、当該データの複数の要素が前記各管理単位に配置されないように配列を拡張するコードを生成することを特徴とする請求項１から６のいずれか一つに記載のコードの生成方法。
【請求項８】
前記タスクによって使用されるデータは配列変数であって、
前記プログラムの解析結果に基づいて、前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が発生している箇所を判定し、
前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が、前記配列変数の要素が前記主記憶装置の連続する領域に格納される次元の要素間で発生している場合、前記配列変数の複数の要素が前記各管理単位に配置されないように前記配列変数を拡張するコードを生成し、
前記分割されたタスクによって使用されるデータの境界と前記管理単位との不整合が、前記配列変数の要素が前記主記憶装置の連続する領域に格納される次元の要素間で発生していない場合、前記不整合が発生している次元より下位の複数の次元の前記配列変数の要素が前記各管理単位に配置されないように前記配列変数を拡張するコードを生成することを特徴とする請求項７に記載のコードの生成方法。
【請求項９】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記各プロセシングエレメント毎に、当該プロセシングエレメント内で使用されるローカル変数を定義するコードと、
前記各プロセッシングエレメントが前記定義されたローカル変数を用いて演算をするコードと、
前記第１のプロセシングエレメントが前記ローカル変数で演算した結果を主記憶装置に書き戻すコードと、
前記第２のプロセシングエレメントが前記第１のプロセシングエレメントによる演算結果を前記主記憶装置から読み込むコードと、
前記第２のプロセシングエレメントが前記主記憶装置から読み込んだデータを前記キャッシュメモリに書き込むコードとを含むことを特徴とする請求項１から８のいずれか一つに記載のコードの生成方法。
【請求項１０】
異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、前記データを生産するプロセシングエレメントが前記依存関係があるデータを前記主記憶装置に書き戻すコードと、前記データを消費するプロセシングエレメントが前記依存関係があるデータを無効化するコードとを生成することを特徴とする請求項１から９のいずれか一つに記載のコードの生成方法。
【請求項１１】
マルチプロセッサシステムに備わるプロセッサがプログラムを実行する際にメモリの記憶領域を管理する方法であって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記方法は、
前記プロセッシングエレメントが、前記主記憶装置から読み込んだデータを、前記キャッシュメモリの管理単位に従って、前記キャッシュメモリに一時的に格納する手順と、
前記プロセッシングエレメントによる使用が終了したデータを、前記キャッシュメモリの管理単位に従って、前記キャッシュメモリから前記主記憶装置に書き戻す手順と、
前記プログラムを分割して生成される各タスクによって使用されるデータの境界がメモリの管理単位と整合しない場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設け、当該境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順とを含むことを特徴とする記憶領域の管理方法。
【請求項１２】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記第１のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを前記キャッシュメモリにおいて演算する手順と、
前記第２のプロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納された演算結果を前記ノンキャッシャブル領域に格納する手順と、
前記第２のプロセッシングエレメントが、前記ノンキャッシャブル領域に格納された演算結果を、前記第１のプロセッシングエレメントのキャッシュメモリに転送する手順とを含むことを特徴とする請求項１１に記載の記憶領域の管理方法。
【請求項１３】
前記プロセッシングエレメントは、第１のプロセッシングエレメント及び第２のプロセッシングエレメントを含み、
前記ノンキャッシャブル領域は、前記各プロセッシングエレメント毎に設けられ、
前記ノンキャッシャブル領域を用いて演算する手順は、
前記各プロセッシングエレメントが、前記タスクによって使用されるデータの境界を含む管理単位に格納されたデータを自プロセッシングエレメントのノンキャッシャブル領域において演算する手順と、
前記第１のプロセッシングエレメントが、前記ノンキャッシャブル領域で演算した結果を、前記第２のプロセッシングエレメントの共有メモリに書き込む手順とを含むことを特徴とする請求項１１に記載の記憶領域の管理方法。
【請求項１４】
異なる前記プロセッシングエレメントによって実行されるタスク間でデータ依存がある場合、
前記データを生産するプロセシングエレメントが、前記依存関係があるデータを前記主記憶装置に書き戻し、
前記データを消費するプロセシングエレメントが、前記依存関係があるデータを無効化することを特徴とする請求項１１から１３のいずれか一つに記載の記憶領域の管理方法。
【請求項１５】
マルチプロセッサシステムに備わるプロセッサによって実行可能なコードを生成するプログラムであって、
前記マルチプロセッサシステムは、複数のプロセッシングエレメントと、前記各プロセッシングエレメントからアクセス可能な主記憶装置とを備え、
前記各プロセッシングエレメントは、演算処理をするプロセッサと、前記プロセッサによって使用されるデータが一時的に格納されるキャッシュメモリとを備え、
前記プロセッシングエレメントが前記主記憶装置から読み込んだデータは、前記キャッシュメモリに一時的に格納され、
前記プロセッシングエレメントによる使用が終了したデータは、前記キャッシュメモリから前記主記憶装置に書き戻され、
前記主記憶装置と前記キャッシュメモリとの間では、前記キャッシュメモリのアクセス管理単位に従ってデータが転送され、
前記コード生成プログラムは、当該プログラムを実行する計算機に
前記プロセッサによって実行されるプログラムを解析する手順と、
前記プログラムに含まれる各タスクの実行に必要なデータを解析する手順と、
前記解析の結果に基づいて、前記プログラムを前記各タスクをに分割した場合に、前記分割されたタスクによって使用されるデータの境界がメモリのアクセス管理単位と整合するか否かを判定する手順と、
前記タスクによって使用されるデータの境界がメモリのアクセス管理単位と整合しないと判定された場合、当該境界を含む管理単位に格納されるべきデータが前記キャッシュメモリに一時的に格納されないノンキャッシャブル領域を設けるコードと用いて、当該タスクによって使用されるデータの境界を含むアクセス管理単位に格納されたデータを演算結果を前記ノンキャッシャブル領域に格納するコードとを生成する手順とを実行させることを特徴とするコード生成プログラム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図６Ｂ】
【図９Ａ】
【図１０Ｂ】
【図１１】
【図１３Ｂ】
【図１５Ｂ】
【図１６】
【図１７Ａ】
【図１７Ｂ】
【図１７Ｃ】
【図１８】
【図１９】
【図２０Ａ】
【図２０Ｂ】
【図２１】
【図２２】
【図２３】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９Ｂ】
【図９Ｃ】
【図１０Ａ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図６Ｂ】
【図９Ａ】
【図１０Ｂ】
【図１１】
【図１３Ｂ】
【図１５Ｂ】
【図１６】
【図１７Ａ】
【図１７Ｂ】
【図１７Ｃ】
【図１８】
【図１９】
【図２０Ａ】
【図２０Ｂ】
【図２１】
【図２２】
【図２３】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９Ｂ】
【図９Ｃ】
【図１０Ａ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【公開番号】特開２０１１−１２８８０３（Ｐ２０１１−１２８８０３Ａ）
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【出願番号】特願２００９−２８５５８６（Ｐ２００９−２８５５８６）
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]