(57)【要約】【課題】本発明は、大規模なソフトウェアを対象として、マルチプロセッサ上で効果的に動作する並列化プログラムを生成する方法を提供することを目的とする。【解決手段】並列化プログラム生成方法は、プログラム依存グラフの頂点同士を融合して縮退プログラム依存グラフを生成し、縮退プログラム依存グラフの頂点の実行順序を計算し、分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、手続きの実行を制御する手続き制御プログラムを生成する各段階を含むことを特徴とする。【選択図】図６
2008090541.tif 000002
【特許請求の範囲】
【請求項１】
逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
該縮退プログラム依存グラフの頂点の実行順序を計算し、
該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、
該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
各段階を含むことを特徴とする並列化プログラム生成方法。
【請求項２】
該手続き制御プログラムを生成する段階は、プロセッサに共通の共有メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きの終了を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項１記載の並列化プログラム生成方法。
【請求項３】
該手続き制御プログラムを生成する段階は、プロセッサ毎に設けた分散メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きからのデータ転送を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項１記載の並列化プログラム生成方法。
【請求項４】
該手続き制御プログラムを生成する段階は、入力データのデータ転送に対する手続きの依存関係を登録する命令及び手続きに対する出力データのデータ転送の依存関係を登録する命令を生成することを特徴とする請求項３記載の並列化プログラム生成方法。
【請求項５】
該実行順序を計算する段階において、該縮退プログラム依存グラフを静的単一代入形式に変換する段階を含むことを特徴とする請求項２記載の並列化プログラム生成方法。
【請求項６】
逐次プログラムと並列化プログラム生成プログラムとを格納するメモリと、
該メモリに格納された該並列化プログラム生成プログラムを実行することで該メモリに格納された該逐次プログラムから並列化プログラムを生成する演算処理ユニットを含み、該演算処理ユニットは、該並列化プログラム生成プログラムを実行することにより、
該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
該縮退プログラム依存グラフの頂点の実行順序を計算し、
該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、
該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
ことを特徴とする並列化プログラム生成装置。
【請求項７】
該演算処理ユニットは、プロセッサに共通の共有メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きの終了を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項６記載の並列化プログラム生成装置。
【請求項８】
該演算処理ユニットは、プロセッサ毎に設けた分散メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きからのデータ転送を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項６記載の並列化プログラム生成装置。
【請求項９】
該演算処理ユニットは、入力データのデータ転送に対する手続きの依存関係を登録する命令及び手続きに対する出力データのデータ転送の依存関係を登録する命令を生成することを特徴とする請求項８記載の並列化プログラム生成装置。
【請求項１０】
逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
該縮退プログラム依存グラフの頂点の実行順序を計算し、
該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まない頂点列を基本ブロックとして纏め、
該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
各段階を計算機に実行させるコードを含むことを特徴とする並列化プログラム生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にプログラム生成方法、装置、及びプログラムに関し、詳しくは並列化プログラム生成方法、装置、及びプログラムに関する。
【背景技術】
【０００２】
近年、シングル・プロセッサでのプログラム性能には限界があることが知られてきた。従来、性能を上げるためには、プロセッサの動作周波数を高くすることで単位時間あたりの処理量を増やす方法と、命令を並列に実行することで同時に実行できる処理を増やす方法とがとられてきた。
【０００３】
しかし動作周波数を高くすると消費電力が大きくなるという問題があるとともに、動作周波数の向上には物理的な限界があるという問題がある。また、命令レベルの並列性は高々２〜４程度であり（非特許文献１）、投機的な実行などを導入することにより多少並列性を上げることはできるが、それにも限界があることが知られている。
【０００４】
そこで、命令レベルよりも大きな粒度でプログラムを並列化し、複数のプロセッサにて実行することにより、処理性能を向上させる方法が注目されている。しかしながら、制御による分岐が多い逐次プログラムを効果的な並列プログラムへ変換する画一的な方法は、これまでのところ知られていない。
【０００５】
逐次プログラムを分割して複数のプロセッサ上で並列に実行するプログラムを生成する手法として、ループに着目したデータ・レベル並列化という方法と、制御に着目した投機的なスレッド実行という方法が知られている。
【０００６】
特許文献１では、ループの中におけるデータの依存関係を解析し、配列を分割して、ループの処理を複数のプロセッサで実行させる。この手法は、数値計算等の規則的なループの処理が多い場合に有効である。
【０００７】
また特許文献２は、逐次プログラムにおける分岐に着目して、投機的なスレッド実行に置換する手法を示す。この手法では、制御の流れに基づいてプログラムを並列化するので、プログラムの潜在的な並列性を充分に抽出できているとはいえない。また、投機的スレッド実行機構を持たないマルチプロセッサにおいては予測失敗時のロールバックのコストが大きいので、分岐予測ヒット率が低いアプリケーションにはこの手法は適さない。
【０００８】
従って、大規模なソフトウェアを対象として、逐次プログラムを並列化することにより、マルチプロセッサ上で効果的に動作する非投機的なマルチ・スレッド・プログラム（並列化プログラム）を生成する方法を提供することが必要になる。但し、このようにして生成する並列化プログラムにおいては、以下に説明するように、スレッド間の依存関係に基づく待ち時間の発生という問題について考慮する必要がある。
【０００９】
並列化プログラムの各スレッドの実行を制御する方式としては、例えば、手続を非同期の遠隔呼び出しとして呼び出すことにより並列にスレッドを実行する方式、手続に実行開始するメッセージを送信することにより並列にスレッドを実行する方式、スレッド間で共有メモリを利用して入出力変数の受け渡しを行なうことにより並列にスレッドを実行する方式等が考えられる。しかしこれらの方式では、第１の手続（スレッド）の実行結果を利用する第２の手続がある場合、第１の手続の終了を待つ命令とそれに続く第２の手続を実行する命令とを、他の手続の実行に要する時間などを見積もって、プログラム中の適当な場所に配置しておくことになる。この場合、第１の手続が予想以上に早く終了した場合などに、第２の手続を実行するまでに、不必要な待ち時間が発生してしまう。
【００１０】
図１は、無駄な待ち時間の発生について説明するための図である。図１において、プロセッサ０乃至プロセッサ３の４つのプロセッサが用いられる。プロセッサ０でスレッド制御プログラム１（各スレッドに対応する手続の実行及び終了待ちを制御するプログラム）を実行する。図１の例では、まずプロセッサ０から、プロセッサ１乃至プロセッサ３に対して手続Ａ乃至Ｃの実行を順番に要求する（start A()〜start C()）。その後プロセッサ０は、手続Ａの終了を待って（wait A()）、手続Ａの実行結果を利用する手続Ｄの実行を要求する（start D()）。その後、手続Ｂの終了を待って（wait B()）、手続Ｂの実行結果を利用する手続Ｅの実行を要求する（start Ｅ()）。更にその後、手続Ｃの終了を待って（wait C()）、手続Ｃの実行結果を利用する手続Ｆの実行を要求する（start F()）。
【００１１】
この例では、手続Ｃが終了してから手続Ｆの実行を要求するまでに待ち時間が発生している。これは、スレッド制御プログラム中において、手続Ｂの終了待ち合わせ（wait B()）と手続Ｅの実行要求（start Ｅ()）が、手続Ｃの終了待ち合わせ（wait C()）と手続Ｆの実行要求（start F()）よりも前に配置されているからである。このような命令配置順のために、手続Ｂが終了しないと、手続Ｃの終了待ち合わせ及び手続Ｆの実行要求が実行されないことになる。
【００１２】
このような命令配置は、手続Ｂが手続Ｃよりも早く実行が終了するであろうという見積もりに基づくものである。手続Ｃの方が手続Ｂよりも早く終了することが分かっていたならば、手続Ｃの終了待ち合わせ及び手続Ｆの実行要求を、手続Ｂの終了待ち合わせ及び手続Ｅの実行要求よりも前に配置することが考えられる。しかし実際には、手続の実行にかかる時間は処理データの内容等にも依存するので、終了時間を正確に見積もることは不可能である。従って、単純な遠隔手続呼び出し、共有メモリによるスレッド、メッセージ送信等の上記方式では、図１に示すような待ち時間を無くすことはできない。
【００１３】
そこで、並列化プログラムの各スレッドの実行を制御する際に、各手続毎に他の手続に対する依存関係を実行条件として指定し、各手続をプロセッサ毎の実行キューに投入し、実行条件が満たされた手続を実行していくという方式が考えられる。このような方式を、依存関係待ち合わせ付き非同期遠隔手続呼び出し方式と呼ぶ。
【００１４】
図２は、依存関係待ち合わせ付き非同期遠隔手続呼び出し方式による手続実行の制御について説明するための図である。図２において、プロセッサ０乃至プロセッサ３の４つのプロセッサが用いられる。プロセッサ０でスレッド制御プログラム２（各スレッドに対応する手続きの実行及び依存関係を制御するプログラム）を実行する。この際プロセッサ０は、手続き呼出しプログラム３を実行することにより、スレッド制御プログラム２に規定される各手続きを各プロセッサ毎のキューを用いて管理する。
【００１５】
図２の例では、まず制御プログラム２の命令start A()に従って、プロセッサ１の実行キュー４に手続Ａが投入される。また制御プログラム２の命令start B()に従って、プロセッサ２の実行キュー５に手続Ｂが投入される。更に制御プログラム２の命令start C()に従って、プロセッサ３の実行キュー６に手続Ｃが投入される。
【００１６】
同様に、制御プログラム２の命令start D()、start E()、及びstart F()に従って、実行キュー４乃至６にそれぞれ手続Ｄ、Ｅ、及びＦが投入される。またスレッド制御プログラム２中のdep(x, y, …)は依存関係を指定する命令であり、手続Ｘの依存先が手続Ｙ、・・・であることを示す。即ち、手続Ｘを実行するためには、手続Ｙ、・・・の実行が終了している必要があることを示す。制御プログラム２の命令dep(D, A)に従って、プロセッサ１の実行キュー４中の手続Ｄに対して、依存先の手続がＡであることが登録される。また制御プログラム２の命令dep(E, A, B)に従って、プロセッサ２の実行キュー５中の手続Ｅに対して、依存先の手続がＡ及びＢであることが登録される。更に、制御プログラム２の命令dep(F, A, C)に従って、プロセッサ３の実行キュー６中の手続Ｆに対して、依存先の手続がＡ及びＣであることが登録される。
【００１７】
このようにして各プロセッサ毎に設けた実行キューに投入されている手続を、キューの順番に従って対応するプロセッサで実行する。この際、依存先が登録されていない手続（図２においてＮＵＬＬで示されている手続）については無条件に実行し、依存先が登録されている手続については、依存先の手続の終了を検出してから実行する。このようにプロセッサ毎にキューを設け、実行条件が満たされたキュー内の手続き（実行可能手続き）から順番に実行していくことで、図１に示したような待ち時間を無くすことができる。
【００１８】
以上説明したように、上記の依存関係待ち合わせ付き非同期遠隔手続呼び出し方式を用いれば、並列化プログラムの実行時における不要な待ち合わせ時間の発生を防ぐことができる。従って、大規模なソフトウェアを対象として、逐次プログラムを並列化することにより、マルチプロセッサ上で効果的に動作する非投機的な並列化プログラムを生成する際には、上記の依存関係待ち合わせ付き非同期遠隔手続呼び出し方式に適用可能な並列化プログラムを生成することが望ましい。
【特許文献１】特許第３０２８８２１号公報
【特許文献２】特許第３６４１９９７号公報
【非特許文献１】David W. Wall. Limits of Instruction-Level Parallelism. Proceedings of the fourth international conference on Architectural support for programming languages pp. 176-188 May. 1991.
【非特許文献２】S. Horwitz, J. Prins, and T. Reps, "Integrating non-interfering versions of programs," ACM Transactions on Programming Languages and Systems, vol. 11, no. 3, pp. 345-387, 1989.
【非特許文献３】Jeanne Ferrante, Karl J. Ottenstein, Joe D. Warren, "The Program Dependence Graph and Its Use in Optimization," ACM Transactions on Programming Languages and Systems, pp. 319-419, vol. 9 no. 3, July 1987.
【非特許文献４】Susan Horwitz, Jan Prins, Thomas Reps, "On the adequacy of program dependence graphs for representing programs," Proceedings of the 15th Annual ACM Symposium on the Principles of Programming Languages, pp. 146-157, Jan., 1988.
【非特許文献５】中田育男著:"コンパイラの構成と最適化"，朝倉書店，１９９９
【発明の開示】
【発明が解決しようとする課題】
【００１９】
以上を鑑みて、本発明は、大規模なソフトウェアを対象として、マルチプロセッサ上で効果的に動作する非投機的かつ依存関係待ち合わせに基づく並列化プログラムを生成する方法、装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
並列化プログラム生成方法は、逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、該縮退プログラム依存グラフの頂点の実行順序を計算し、該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する各段階を含むことを特徴とする。
【００２１】
並列化プログラム生成装置は、逐次プログラムと並列化プログラム生成プログラムとを格納するメモリと、該メモリに格納された該並列化プログラム生成プログラムを実行することで該メモリに格納された該逐次プログラムから並列化プログラムを生成する演算処理ユニットを含み、該演算処理ユニットは、該並列化プログラム生成プログラムを実行することにより、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、該縮退プログラム依存グラフの頂点の実行順序を計算し、該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成することを特徴とする。
【００２２】
並列化プログラム生成プログラムは、逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、該縮退プログラム依存グラフの頂点の実行順序を計算し、該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まない頂点列を基本ブロックとして纏め、該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する各段階を計算機に実行させるコードを含むことを特徴とする。
【発明の効果】
【００２３】
本発明の少なくとも１つの実施例によれば、制御の流れグラフではなく、制御の依存関係を示すグラフであるプログラム依存グラフに基づいて並列化プログラムを生成するので、制御の流れ（分岐）を超えたプログラムの並列性を抽出することができる。また、プログラム依存グラフを縮退してグラフの規模を削減することで、その後の並列化プログラム生成処理の効率化及び最適化が可能になるとともに、大きな粒度での並列化を実現することができる。
【００２４】
また更に、異なる基本ブロックをまたいでの手続き間の依存関係については、先行手続きの終了待ち合わせを行ってから、後続手続きを実行するようにする。また同一の基本ブロック内部で依存関係がある手続きの実行については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより手続きを実行する。即ち、基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置して、この命令の配置順により依存関係を非明示的に規定して、依存関係を満たすように手続き制御する。また同一の基本ブロック内部で依存関係がある手続きについては後続手続きの先行手続きへの依存関係を明示的に登録する命令を生成するようにして、依存関係を満たすように手続き制御する。このような構成とすることで、複雑な制御の依存関係が存在する基本ブロック間については、手続きの実行を待ち合わせにより実現することで制御プログラムの生成を容易なものとし、実行順が固定である同一基本ブロック内については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより無駄な待ち合わせ時間をなくすことができる。
【発明を実施するための最良の形態】
【００２５】
以下に、本発明の並列化プログラム生成方法の概略及び実施例を添付の図面を用いて詳細に説明する。
【００２６】
図３は、本発明による並列化プログラム生成方法の概略を示す図である。
【００２７】
ステップＳ１で逐次プログラムからプログラム依存グラフ（ＰＤＧ：Program Dependence Graph）を生成する。次に、ステップＳ２で、手続きとして他のプロセッサエレメントで実行するに適した処理量となるまで依存関係を縮退することにより、手続きを頂点とする縮退プログラム依存グラフを作成する。ステップＳ３で、作成した縮退プログラム依存グラフから、非投機的に手続きの起動と同期を制御する手続き制御プログラムを生成する。またステップＳ４で、縮退プログラム依存グラフから、その各頂点に相当する手続きプログラムを生成する。
【００２８】
まず逐次プログラムからプログラム依存グラフを生成する処理（図３のステップＳ１）について説明する。
【００２９】
プログラム依存グラフとは、例えば非特許文献２乃至４等に説明されるように、プログラムの文を頂点とし、文と文の間の関係を辺で表現したグラフである。非特許文献２乃至４に記載されるプログラム依存グラフは、次のような頂点集合Vと辺集合Eの組で表現されるものであり、逐次プログラムを解析することにより生成できる。
【００３０】
［V:頂点集合］
エントリ:プログラムの開始ポイントを表す。
【００３１】
初期定義:プログラム開始時の初期値の定義を表す。
【００３２】
プリディケート: If-then-elseまたはwhile-loopの条件判定を表す。
【００３３】
代入文:プログラムの代入文を表す。
【００３４】
最終使用:プログラム終了時の変数の参照を表す。
【００３５】
［E:辺集合］
［制御依存辺: v→cL w］プリディケート頂点vに対して、その条件判定結果により、頂点wに到達するか否かが決まることを表す。Lは条件判定のフラグを表し、L=Tのときは条件判定結果が真の場合に頂点wを実行し、L=Fのときは結果が偽の場合に頂点wを実行する。
【００３６】
［データ依存辺］
［ループ独立フロー依存辺: v→lix w］頂点vで代入された変数xの値を、頂点wで参照するような場合のデータ依存関係を表す。ここでは、ループを繰り越さない場合のみを表す。
【００３７】
［ループ繰り越しフロー依存辺: v→lc(L)x w］頂点vで代入された変数xの値を、頂点wで参照するような場合のデータ依存関係を表す。ループLを繰り越す場合を表す。
【００３８】
［定義順序関係: v→do(u)x w］頂点v及び頂点wが変数xの値を代入し、頂点uで参照するような場合の、頂点vと頂点wの順序関係を表す。制御の流れによっては、v, w, u, あるいは、v, uの順に実行される可能性がある場合に、v, wの実行順序を表すものである。
【００３９】
以下において、縮退プログラム依存グラフを作成する処理（図３のステップＳ２）について説明する。
【００４０】
上記のような一般的なプログラム依存グラフでは、文または代入式を頂点としたグラフとなっている。文または代入式を頂点とした場合、大規模なソフトウェアではグラフの頂点数が数千〜数万となってしまう。一般的に、コンパイラのグラフを用いた最適化の問題の計算量は、グラフの規模に対して指数関数的に増大することが知られている。したがって、例えば数個の手続きなどを対象とした頂点数が数十程度のグラフの場合には、解析が可能であるが、現実的な規模のソフトウェア全体に対する最適化は困難といえる。
【００４１】
そこで、プログラム依存グラフの頂点数及び辺数を低減すべく、プログラム依存グラフの依存関係を縮退して頂点を融合し、粗粒度のプログラム依存グラフを作成する。依存関係を縮退することによりグラフの規模を1/10〜1/100とすることで、現実的な時間にて、プログラムの最適化を可能にする。
【００４２】
依存関係の縮退は、次のような方法で、縮退可能な依存関係及び頂点の集合を求め、依存関係を削除して頂点を1つの頂点に融合することにより実行される。
【００４３】
１．構文規則に基づく縮退
一般にプログラム依存グラフから等価な逐次プログラムの制御の流れを再構成することは、困難と言われている。これは、制御の依存関係のみの表現となっているため、依存関係を満足する制御の流れは一意に決定できない上に、グラフを変形するような最適化を行なった場合、依存関係を満足するような制御の流れが存在しないような場合も出てくるためである。
【００４４】
しかし、表現するプログラムの制御構造を、if文、while文、及び、代入文に限定し、プログラム依存グラフの制御依存部分グラフ(頂点と制御依存辺のみで構成される部分グラフ)の形が木構造となる場合は、プログラムの制御の流れを再構成できることが知られている（非特許文献２）。そこで、プログラムにおけるif文、while文でない制御文に対して、入り口と出口がそれぞれ1つとなるようなプログラムのブロックを求める。ブロック全体とブロック内部の依存関係を1つの頂点に縮退することで、安全に制御の流れを再構成可能な範囲の縮退プログラム依存グラフを作成する。
【００４５】
２．結合度に基づく縮退
プログラム依存グラフを探索して、頂点間の結合の強さを求める。結合度は、データ依存辺とその大きさ、及び、制御依存辺、処理の大きさから計算されるものとする。ある結合度以上の頂点に対して、縮約可能な条件を満足する場合は、頂点を結合し依存関係を縮約する。ここで、次の２つ条件を満たすときに、頂点を結合しての縮約が可能となる。
【００４６】
１）プログラム依存グラフに対応するＣＦＧ(Control Flow Graph：制御フローグラフ)上で頂点集合外から頂点集合内への分岐は頂点集合の先頭頂点へのみであり、頂点集合内から頂点集合外への分岐は頂点集合の最後の頂点のみである。
【００４７】
２）頂点間のデータ依存パスに外部の頂点が含まれない。
【００４８】
以上のようにして、「構文規則に基づく縮退」又は「結合度に基づく縮退」により、頂点数が大幅に削減された縮退プログラム依存グラフを生成することができる。縮退プログラム依存グラフは、次の要素から構成される。
【００４９】
［V:頂点集合］
エントリ:プログラムの開始ポイントを表す。
【００５０】
初期定義:プログラム開始時の初期値の定義を表す。
【００５１】
プリディケート: If-then-elseまたはwhile-loopの条件判定を表す。
【００５２】
文の集合: プログラムを構成する文の集合を表す。
【００５３】
最終使用:プログラム終了時の変数の参照を表す。
【００５４】
［E:辺集合］
［制御依存辺: v→cL w］プリディケート頂点vに対して、その条件判定結果により、頂点wに到達するか否かが決まることを表す。Lは条件判定のフラグを表し、L=Tのときは条件判定結果が真の場合に頂点wを実行し、L=Fのときは結果が偽の場合に頂点wを実行する。
【００５５】
［データ依存辺］
［ループ独立フロー依存辺: v→lix w］頂点vで代入された変数xの値を、頂点wで参照するような場合のデータ依存関係を表す。ここでは、ループを繰り越さない場合のみを表す。
【００５６】
［ループ繰り越しフロー依存辺: v→lc(L)x w］頂点vで代入された変数xの値を、頂点wで参照するような場合のデータ依存関係を表す。ループLを繰り越す場合を表す。
【００５７】
［定義順序関係: v→do(u)x w］頂点v及び頂点wが変数xの値を代入し、頂点uで参照するような場合の、頂点vと頂点wの順序関係を表す。制御の流れによっては、v, w, u, あるいは、v, uの順に実行される可能性がある場合に、v, wの実行順序を表すものである。
【００５８】
以下において、手続き制御プログラムを生成する処理（図３のステップＳ３）及び手続きプログラムを生成する処理（図３のステップＳ４）について説明する。
【００５９】
まず手続きプログラムの生成について説明する。上記のようにして生成された縮退プログラム依存グラフの頂点は、入力逐次プログラムの文の部分集合であって、文の間の制御の流れの情報を有している。従って、着目する１つの頂点へのデータフロー入力辺が表す変数を入力とし、データフロー出力辺が表す変数を出力とする、１つの手続きプログラムを１つの頂点に対して生成する。また、制御の流れより手続きプログラムの本文を、また、本文の実行に必要な局所変数をそれぞれ生成する。
【００６０】
図４は、手続きプログラム生成方法の概要を示す図である。図５は、図４の手続きプログラム生成方法により生成される手続きプログラムを示す図である。
【００６１】
図４のステップＳ１において、着目頂点についてデータフロー入力辺が表す変数を入力として、入力変数を引数として受信するためのプログラム部分を生成する。これにより、図５に示す入力変数の引数受信部分１０が生成される。ステップＳ２において必要な変数を探索する。更にステップＳ３において、探索により見つかった変数について変数宣言を生成する。これにより、図５に示す変数宣言部分１１が生成される。
【００６２】
ステップＳ４において、着目頂点の文の間の制御の流れの情報に基づいて、プログラムの本文を生成する。これにより、図５に示すプログラム本体部分１２が生成される。ステップＳ５において、着目頂点のデータフロー出力辺が表す変数を出力として返すためのプログラム部分を生成する。これにより、図５に示す出力変数のセット部分１３が生成される。
【００６３】
このように、手続きプログラムとしては、頂点が表す文／文の集合を実行する手続きとする。また、入力変数を手続きの引数とし、出力変数を復帰値あるいは、出力変数を格納するアドレスを引数として受け取るような手続きを作成する。
【００６４】
次に手続き制御プログラムの生成について説明する。非特許文献２に記載される技術に基づいて、縮退したプログラム依存グラフから制御の流れを安全に再構成することができる。具体的には、縮退したプログラム依存グラフの制御依存部分木について、プログラムの実行順序関係を計算し、基本ブロックを求める。基本ブロックとは、分岐（ＩＦ、ＧＯＴＯ、ＬＯＯＰ等）や合流を含まない順番に実行される頂点の列のことを言う。各中間節点が表す制御構造と子頂点が表す「手続き」の呼び出しを行なうプログラムを生成することで、並列プログラムを生成することができる。「手続き」を実行する上で必要となる入力および出力データの送受信と待ち合わせを行なうコードも生成する。基本ブロック内の手続き呼び出しおよびデータ転送の依存関係に関しては、依存関係待ち合わせのメカニズムを用いて制御する。
【００６５】
以下に、本発明の実施例について詳細に説明する。第１の実施例は、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を共有メモリで実現する例であり、第２の実施例は、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を分散メモリで実現する例である。まず第１の実施例と第２の実施例に共通な部分について説明する。
【００６６】
図６は、手続き制御プログラムの生成方法を示すフローチャートである。まずステップＳ１で、頂点間の実行順序関係を計算する。縮退したプログラム依存グラフは、データ及び制御の依存関係のみを表現したグラフであって頂点間の実行順序は明示されていないので、これから適切な制御の流れを再構成する必要がある。そこで、縮退したプログラム依存グラフの制御依存部分木について、各中間節点の子頂点の実行順序を計算する。この結果、頂点間の半順序関係を求めることができる。この実行順序関係を用いて、制御プログラムを生成することとなる。またその課程において、逆依存関係、出力依存関係が抽出される。
【００６７】
次にステップＳ２で、求めた実行順序(制御の流れ)から、基本ブロックを抽出する。
【００６８】
次にステップＳ３で、制御プログラムの変数と初期値代入文を生成する。この際、静的単一代入形式（非特許文献５、３２０頁）に変換することで、並列性を向上されることも考えられる。ここで変数としては、データの受け渡しを行うための変数を生成する。
【００６９】
次にステップＳ４で、Ｓ１で求めた実行順序順に制御依存部分グラフを探索し、制御プログラムを生成する。プリディケート頂点については、その頂点が表す制御構造を生成する。そして、制御構造の本文として、当該頂点の下位の部分木の制御プログラムを生成する。基本ブロックについては依存関係に基づく非同期遠隔手続きを行う文を生成する。これについては以下に詳細に説明する。
【００７０】
更にステップＳ５で、手続きの終了の待ち合わせを行う文を生成する。
【００７１】
図７は、頂点間の実行順序関係を決定する方法を示すフローチャートである。図７の処理は、図６のステップＳ１に相当する。図７に示す処理の入力は縮退したプログラム依存グラフＰＤＧであり、出力は縮退したプログラム依存グラフＰＤＧ及びその制御の流れである。
【００７２】
ステップＳ１で、縮退したプログラム依存グラフＰＤＧのエントリ頂点（プログラムの開始ポイント）をｖとする。ステップＳ２で、頂点ｖ以下の制御の流れを再構成する。以上で処理を終了する。
【００７３】
図８は、頂点ｖ以下の制御の流れを再構成する処理（図７のステップＳ２）を示すフローチャートである。図８の処理の入力は、縮退したプログラム依存グラフＰＤＧ及び頂点ｖである。
【００７４】
ステップＳ１で、Region(v, T) = {u | u ∈ V, v→cTu ∈ E}が空集合であるか否かを判断する。空集合であれば処理を終了し、空集合でなければステップＳ２に進む。ここでRegion(v, T)とは、頂点uの集合であって、頂点vから頂点uへのL=Fの制御依存関係が存在するものである。ここでＶは頂点集合、Ｅは辺集合、v→cTuはL=Fの制御依存辺を示すものである。
【００７５】
ステップＳ２で、Region(v, T)の実行順序関係を計算する。ステップＳ３で、Region(v, F) = {u | u ∈ V, v→cFu ∈ E}が空集合であるか否かを判断する。空集合であれば処理を終了し、空集合でなければステップＳ４に進む。ここでRegion(v, F)とは、頂点uの集合であって、頂点vから頂点uへのL=Fの制御依存関係が存在するものである。以上で処理を終了する。
【００７６】
図９は、Regionの実行順序関係を計算する処理を示すフローチャートである。この処理は、図８のステップＳ２及びステップＳ４の各々に対応する。図９の処理の入力は、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）である。
【００７７】
ステップＳ１で、着目領域Ｖ'の各頂点ｖについて、ステップＳ２乃至Ｓ３の処理を繰り返すループを開始する。ステップＳ２で、ｖがプレディケート頂点（If-then-else又はwhile-loopの条件判定を表す頂点）であるか否かを判断する。ｖがプレディケート頂点である場合のみ、ステップＳ３を実行する。ステップＳ３で、頂点ｖ以下の実行順序関係を計算する。
【００７８】
次に、ステップＳ４で、逆依存及び出力依存を求める。ここでは制御の流れに起因するデータ依存関係(逆依存、出力依存)を抽出する。具体的には、着目領域（Region）を越えるデータ依存関係から、着目領域内の逆依存及び出力依存を表出する。
【００７９】
次に、ステップＳ５で、逆依存及び出力依存を求める。ここでは着目領域（Region）内の実行順序を決定する。即ち、実行順序が一意に定まらないRegion内頂点の集合について適切な実行順序制約を決定する。具体的には、求められた逆依存関係や出力依存関係などによる実行順序制約をもとに、Region内の逆依存関係や出力依存関係を明らかにして、実行順序を決定する。実行順序が任意となる場合は、実行順序を仮定して逆依存関係、出力依存関係を求め、矛盾が起きない実行順序が得られるまで試行を繰返す。
【００８０】
最後にステップＳ６でスケジューリングを行う。即ち、上で求めた実行順次関係に基づいて頂点の実行順を決定する。これは、半順序関係の成立するグラフのスケジューリングという一般的な問題に帰着できる。従って、トポロジカル・ソートや、頂点の実行時間の概算を重みとしたリスト・スケジューリングなどのよく知られたスケジューリング手法を適用することができる。
【００８１】
図１０は、逆依存及び出力依存を求める処理（図９のステップＳ４）を示すフローチャートである。図１０の処理の入力は、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）である。
【００８２】
ステップＳ１で、着目領域Ｖ'を越える変数参照を抽出してＶｄｅｆとする。ステップＳ２で、着目領域Ｖ'を越える変数代入を抽出してＶｕｓｅとする。ステップＳ３で、Ｖｕｓｅ及びＶ'に基づいて逆依存辺を追加する。ステップＳ４で、Ｖｄｅｆ及びＶ'に基づいて出力依存辺を追加する。以上で処理を終了する。
【００８３】
図１１は、着目領域を越える変数参照を抽出する処理を示すフローチャートである。図１１の処理は図１０のステップＳ１に相当し、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）を入力とする。
【００８４】
ステップＳ１で、頂点の集合Ｖｕｓｅを空にする。ステップＳ２で、着目領域Ｖ'内の各フロー依存辺について以降の処理を繰り返すループを開始する。ここでフロー依存辺としては、ループ独立フロー依存辺とループ繰り越しフロー依存辺とを含む。ステップＳ３で、フロー依存辺ｅの依存元頂点をｕとするとともに、辺ｅの依存先頂点をｖとする。
【００８５】
ループ繰り越しフロー依存辺である場合には、ステップＳ４で、依存先頂点ｖが着目領域Ｖ'に含まれるという条件が満たされるか否かを判定する。またループ独立フロー依存辺である場合には、ステップＳ５で、依存元頂点ｕが着目領域Ｖ'に含まれず且つ依存先頂点ｖが着目領域Ｖ'に含まれるという条件が満たされるか否かを判定する。この判定結果がｙｅｓの場合のみ、ステップＳ６を実行する。ステップＳ６で、頂点の集合Ｖｕｓｅに依存先頂点ｖを追加する。
【００８６】
最後に、ステップＳ７で、頂点の集合Ｖｕｓｅを値として返す。以上で処理を終了する。
【００８７】
図１２は、着目領域を越える変数代入を抽出する処理を示すフローチャートである。図１２の処理は図１０のステップＳ２に相当し、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）を入力とする。
【００８８】
ステップＳ１で、頂点の集合Ｖｄｅｆを空にする。ステップＳ２で、着目領域Ｖ'内の各フロー依存辺について以降の処理を繰り返すループを開始する。ここでフロー依存辺としては、ループ独立フロー依存辺とループ繰り越しフロー依存辺とを含む。ステップＳ３で、フロー依存辺ｅの依存元頂点をｕとするとともに、辺ｅの依存先頂点をｖとする。
【００８９】
ループ繰り越しフロー依存辺である場合には、ステップＳ４で、依存先頂点ｖが着目領域Ｖ'に含まれるという条件が満たされるか否かを判定する。またループ独立フロー依存辺である場合には、ステップＳ５で、依存元頂点ｕが着目領域Ｖ'に含まれ且つ依存先頂点ｖが着目領域Ｖ'に含まれないという条件が満たされるか否かを判定する。何れかの判定結果がｙｅｓの場合のみ、ステップＳ６を実行する。ステップＳ６で、頂点の集合Ｖｄｅｆに依存先頂点ｖを追加する。
【００９０】
最後に、ステップＳ７で、頂点の集合Ｖｄｅｆを値として返す。以上で処理を終了する。
【００９１】
図１３は、逆依存の追加処理を示すフローチャートである。図１３の処理は図１０のステップＳ３に相当し、縮退したプログラム依存グラフＰＤＧ、V'（着目Region）、及び頂点集合Ｖｕｓｅを入力とする。
【００９２】
ステップＳ１で、頂点集合Ｖｕｓｅの各頂点ｖに対して以降の処理を繰り返すループを開始する。ステップＳ２で、頂点ｖで使用する各変数ｘに対して以降の処理を繰り返すループを開始する。ステップＳ３で、着目領域Ｖ'の各頂点ｕに対して以降の処理を繰り返すループを開始する。
【００９３】
ステップＳ４で、頂点ｕが変数ｘを定義するか否かを判定する。判定結果がｙｅｓの場合のみ、ステップＳ５を実行する。ステップＳ５において、ｖからｕへの逆依存辺を追加する。以上で処理を終了する。
【００９４】
図１４は、出力依存の追加処理を示すフローチャートである。図１４の処理は図１０のステップＳ４に相当し、縮退したプログラム依存グラフＰＤＧ、V'（着目Region）、及び頂点集合Ｖｄｅｆを入力とする。
【００９５】
ステップＳ１で、頂点集合Ｖｄｅｆの各頂点ｕに対して以降の処理を繰り返すループを開始する。ステップＳ２で、頂点ｕで使用する各変数ｘに対して以降の処理を繰り返すループを開始する。ステップＳ３で、着目領域Ｖ'の各頂点ｖに対して以降の処理を繰り返すループを開始する。
【００９６】
ステップＳ４で、頂点ｖが変数ｘを定義するか否かを判定する。判定結果がｙｅｓの場合のみ、ステップＳ５を実行する。ステップＳ５において、ｖからｕへの出力依存辺を追加する。以上で処理を終了する。
【００９７】
図１５は、逆依存及び出力依存を求める処理（図９のステップＳ５）を示すフローチャートである。図１５の処理の入力は、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）である。
【００９８】
ステップＳ１で、着目領域内の全域木を求めＳとする。変数xを定義する頂点vとその変数ｘを使用するRegionＲ内の頂点との集合として、頂点ｖの変数xに関する全域木が、
Span(v, x) = {v}∪{u| v→lixu ∈ ER}
と定義される。図１６は、全域木を説明するための図である。図１６に示されるプログラム依存グラフにおいて、頂点ｖｉにおいて変数ｘが定義され、２つの頂点ｖ１及びｖ２が変数ｘを使用する。この場合、頂点ｖｉ、ｖ１、及びｖ２で全域木２１を形成する。また頂点ｖｊにおいて変数ｘが定義され、２つの頂点ｖ３及びｖ４が変数ｘを使用する。この場合、頂点ｖｊ、ｖ３、及びｖ４で全域木２２を形成する。図１７は、全域木を模式的に示す図である。全域木Span(vｉ, x)及び全域木Span(vｊ, x)が、データ依存グラフとして図１７に示されるように構成される。
【００９９】
図１５に戻り、ステップＳ２で、実行順が未決定である２つの任意の全域木を順次選択して以降の処理を繰り返すループが開始される。ステップＳ３で、着目領域に閉路がなく、同一変数xに対する独立した全域木Span(h0,x)及びSpan(h1,x)が存在するか否かを判定する。ここで、「独立した」とは、２つの全域木 Span(h0,x)及びSpan(h1,x)について、Span(h0,x)に含まれる頂点とSpan(h1,x)に含まれる頂点との間に辺（依存関係）がないことを言う。
【０１００】
ステップＳ４でR（Region）のオリジナルをスタックに退避させる。ステップＳ５で、h0→h1の出力依存辺を追加し、推移閉包を求める。ステップＳ６で、全域木間の順序関係を計算する。
【０１０１】
ステップＳ７で、Ｒ（Region）に閉路が存在するか否かを判定する。存在しない場合には、以降の処理ステップＳ８〜ステップＳ１１をスキップする。存在する場合には、ステップＳ８に進む。ステップＳ８で、スタックが空か否かを判断する。空の場合にはエラー終了する。空でない場合には、ステップＳ９で、Ｒのオリジナルをスタックから取り出す。
【０１０２】
以上の処理は、頂点h0からh1への出力依存関係をグラフに追加したときに、巡回グラフとならない場合には追加した依存関係を確定させ、巡回グラフになった場合には元のグラフに戻すことに相当する。元のグラフに戻した後は、以降に示すように、頂点h1からh0への出力依存関係をグラフに追加する。即ち、ステップＳ１０で、h1→h0の出力依存辺を追加し、推移閉包を求める。ステップＳ１１で、全域木間の順序関係を計算する。
【０１０３】
以上の処理により、２つの全域木 Span(h0,x)及びSpan(h1,x)に対する実行順序が決定する。更に、実行順が未決定である２つの任意の全域木を順次選択して同様の処理を繰り返し、全ての全域木間の順序関係が決定されたところで終了する。
【０１０４】
図１８は、全域木間の順序関係を計算する処理を示すフローチャートである。図１８の処理は、図１５のステップＳ６及びステップＳ１１に相当する。図１８の処理の入力は、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）である。
【０１０５】
ステップＳ１で、着目領域内の各辺ｅ（頂点ｖ→頂点ｗ）について以降の処理を繰り返すループを開始する。ステップＳ２で、頂点ｗで定義され、頂点ｖで参照される各変数ｘについて以降の処理を繰り返すループを開始する。
【０１０６】
ステップＳ３で、Va ← { u | v ∈ Span(u, x) }とするとともに、Vb ← { u | w ∈ Span(u, x) }とする。これは、頂点ｖを要素として含む変数ｘに関する全域木における変数ｘを定義する頂点の集合を求めるとともに、頂点ｗを要素として含む変数ｘに関する全域木における変数ｘを定義する頂点の集合を求めることである。
【０１０７】
ステップＳ４で、Ｖａの各頂点ｖａについて以降の処理を繰り返すループを開始する。ステップＳ５で、Ｖｂの各頂点ｖｂについて以降の処理を繰り返すループを開始する。更にステップＳ６で、Span(va, x)の頂点であってSpan(vb, x)の頂点でない各頂点ｖｃについて以降の処理を繰り返すループを開始する。
【０１０８】
ステップＳ７で、ｖｃ→ｖｂがＥ（辺集合）に含まれるか否かを判定する。判定結果がｙｅｓの場合のみステップＳ８を実行する。ステップＳ８で、ｖｃ→ｖｂの逆依存辺を追加し、推移閉包を求める。以降、各ループの処理を繰り返す。
【０１０９】
図１９は、図１８の処理による逆依存辺の追加について説明する図である。図１９には、頂点ｖの変数ｘに関する全域木Span(v,x)と頂点ｗの変数ｘに関する全域木Span(w,x)とが示される。頂点ｖを要素として含む変数ｘに対する全域木Span(va, x)（即ちSpan(v,x)）の各頂点ｖｃ（即ちｖ、２５、２６）に対して、全域木Span(vb, x)（即ちSpan(ｗ,x)）のヘッドｖｂ（変数を定義している頂点ｗ）への逆依存辺３２、３３を追加する。
【０１１０】
図２０は、頂点間の実行順序関係を決定する方法の変形例を示すフローチャートである。図２０のフローチャートに示す処理を、図７のフローチャートに示す処理の代わりに用いてもよい。即ち、頂点間の実行順序関係を決定する処理において、前段階のステップＳ０として、ＳＳＡ（静的単一代入形式）を適用する処理を実行してもよい。即ち、縮退プログラム依存グラフを静的単一代入形式に変換してもよい。この場合、図９に示すステップＳ７の処理（逆依存、出力依存を求め着目領域内の実行順序を決定する処理：図１５のフローチャート）を省略することができる。
【０１１１】
以上により、頂点間の実行順序関係を決定し、逆／出力依存関係を抽出することができる。即ち、図６のステップＳ１の処理が実行される。
【０１１２】
図２１は、基本ブロックを抽出する処理のフローチャートを示す図である。図２１に示す処理は、図６のステップＳ２の処理に相当する。図２１の処理の入力は、実行順序関係が決定された縮退したプログラム依存グラフである。
【０１１３】
求めた制御の流れの順に頂点を探索し、頂点の種類に応じた処理を行なう。以下の説明においてＢは基本ブロックの集合であり、Ｂｉはｉ番目の基本ブロックである。またｖは現在の頂点（着目頂点）であり、ｕは現在の頂点の１つ前の頂点である。
【０１１４】
まずステップＳ２で、最初の基本ブロックＢ０を空集合として生成する。次にステップＳ２で、ｕをエントリ頂点（プログラムの開始ポイント）として、ｖをエントリ頂点の次の頂点とする。ステップＳ４で、現在の頂点ｖが最終頂点であるか否かを判断する。最終頂点である場合には、処理を終了して基本ブロックの集合Ｂが生成される。
【０１１５】
現在の頂点ｖが最終頂点でない場合には、ステップＳ５に進み、現在の頂点ｖがプレディケート頂点（If-then-else又はwhile-loopの条件判定を表す頂点）であるか否かを判断する。プリディケート頂点である場合には、ステップＳ６に進み、ｉをインクリメントしてからＢｉの要素をｖとすることで、新たなプリディケートのみの基本ブロックＢｉを形成する。その後ステップＳ７で、更にｉをインクリメントして、新たな空集合の基本ブロックＢｉを形成する。
【０１１６】
現在の頂点ｖがプレディケート頂点でない場合（Ｓ５でＮｏの場合）には、ステップＳ８で、現在の頂点ｖと１つ前の頂点ｕとが、同一のプレディケート頂点からの制御依存関係を有し、且つその制御依存関係が同一の条件判定フラグに基づくものであるか否かを判定する。この判定結果がＮＯとなるのは、例えばｕとｖとが、ＩＦ文の内部と外部とに対応する場合や、ＩＦ文のＴＨＥＮ節とＥＬＳＥ節とに対応する場合等である。即ち、ステップＳ８においては、同一の条件判定に応じて双方共に実行される２つの頂点であるか否かが判定されている。
【０１１７】
ステップＳ８の判定がＹＥＳの場合には、ステップＳ９で、現在の基本ブロックに現在の頂点ｖを追加する。ステップＳ８の判定がＮＯの場合には、ステップＳ１０で、ｉをインクリメントして新たな空集合の基本ブロックＢｉを形成する。その後ステップＳ１１で、この新たに生成された基本ブロックＢｉに現在の頂点ｖを追加する。その後ステップＳ１２でｕとｖとをそれぞれ次の頂点に更新し、ステップＳ４に戻り以降の処理を繰り返す。
【０１１８】
以上の処理により、分岐（ＩＦ、ＧＯＴＯ、ＬＯＯＰ等）や合流を含まない順番に実行される頂点の列である各基本ブロックＢｉを生成し、これらの基本ブロックを要素とする基本ブロックの集合Ｂを生成することができる。分岐や合流を含まない頂点の列とは、固定の１つの実行順に従い順番に実行される頂点の列のことである。図２１のフローチャートから分かるように、各プレディケート頂点は単独で１つの基本ブロックＢｉを構成し、プレディケート頂点でない１つの基本ブロックＢｉには、途中で分岐も合流もなく固定の１つの実行順に従い順番に実行される頂点の列が含まれることになる。
【０１１９】
本発明では、異なる基本ブロックをまたいでの手続き間の依存関係については、先行手続きの終了待ち合わせを行ってから、後続手続きを実行するようにする。また同一の基本ブロック内部で依存関係がある手続きの実行については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより手続きを実行する。即ち、基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置することにより、依存関係を満たすように手続き制御する。また同一の基本ブロック内部で依存関係がある手続きについては後続手続きの先行手続きへの依存関係を明示的に登録する命令を生成するようにして、依存関係を満たすように手続き制御する。このような構成とすることで、複雑な制御の依存関係が存在する基本ブロック間については、手続きの実行を待ち合わせにより実現することで制御プログラムの生成を容易なものとし、実行順が固定である同一基本ブロック内については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより無駄な待ち合わせ時間をなくすことができる。
【０１２０】
以上により、基本ブロックを抽出することができる。即ち、図６のステップＳ２の処理が実行される。
【０１２１】
以下において、制御プログラムを生成する処理や生成した制御プログラムの具体例等について説明する。以下の説明は、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を共有メモリで実現する第１の実施例と、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を分散メモリで実現する第２の実施例とで異なる。
【０１２２】
まず依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を共有メモリで実現する第１の実施例について説明する。
【０１２３】
図２２は、制御プログラムを生成する処理のフローチャートを示す図である。図２２に示す処理は、図６のステップＳ４（及びＳ５）の処理に相当する。図２２の処理の入力は、実行順序関係が決定された縮退したプログラム依存グラフ及び基本ブロックの集合Ｂである。
【０１２４】
ステップＳ１において、プログラムの先頭を表すエントリ頂点ｖEntryの直下の子頂点ｖを要素とする基本ブロックの集合をＢ'とする。ステップＳ２において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ３で、Ｂｉについての手続き制御プログラムを生成する。ステップＳ４で、手続きの終了待ち合わせを生成する。
【０１２５】
図２３は、基本ブロックの集合Ｂ'の要素Ｂｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。図２３の処理は、図２２のステップＳ３に相当する。図２３に示す処理の入力は縮退したプログラム依存グラフＰＤＧ及び基本ブロック要素Ｂｉである。
【０１２６】
なおここでは、全ての手続き呼び出しを待ち合わせる方法と、制御の流れによって、待ち合わせが行なわれない可能性がある全ての手続き呼び出しを待ち合わせる方法の2つが考えられる。制御の流れによらず必ず待ち合わせが行なわれる頂点V'の集合は次のように表現できる。
【数１】
2008090541.tif 000003
従って、待ち合わせが行なわれない頂点の集合V''は、プログラム・ブロック頂点の集合VPBと頂点集合V'の差分V''=VPB-V'として表現できる。
【０１２７】
図２３のステップＳ１で、基本ブロックＢｉの要素（頂点）の種類を判定する。基本ブロックＢｉの要素である頂点の種類を判定することによって、基本ブロックＢｉがプログラム・ブロックの集合であるか、プレディケート頂点であるかが分かる。
【０１２８】
ステップＳ１の判定の結果、基本ブロックＢｉがプログラム・ブロックの集合の場合は、基本ブロックＢｉに属する頂点の手続きを呼び出す文とその間の依存関係を登録する文とを生成することとなる。具体的には、まずステップＳ２において、基本ブロックＢｉの先行手続きに対する待ち合わせを生成する。この際、ブロック外からブロック内へのフロー依存関係に関して、手続きの終了待ち合わせを生成する。また同時に、定義順序関係及び逆依存関係、出力依存関係に関しても、手続きの終了待ち合わせを生成する。これは、共有メモリ上の同一変数に対して、データが読み書きされる順を保証するための待ち合わせである。ここでは、次の５種類の依存関係について、出力元頂点の手続き終了待ち合わせを生成する。
【０１２９】
１．Ｂｉへのループ繰越フロー依存辺
２．ＢｘからＢｉ（i≠x）へのループ独立フロー依存辺
３．Ｂｉへの定義順序関係、
４．Ｂｉへの逆依存関係、
５．Ｂｉへの出力依存関係
なお同一頂点への待ち合わせが複数ある場合は、1つの待ち合わせに集約する。
【０１３０】
次にステップＳ３で、基本ブロックＢｉの各頂点ｖについて、実行順序の順番で以降の処理を繰り返すループを開始する。ステップＳ４で、頂点ｖの非同期遠隔手続き呼び出しを生成する。ステップＳ５で、基本ブロックＢｉに属する頂点から頂点ｖへのループ独立フロー依存関係に関して依存関係を登録する文を生成する。基本ブロックＢｉの全ての頂点ｖについてこれらの処理を繰り返した後に、ステップＳ６で、実行開始を指示する文を生成する。
【０１３１】
ステップＳ１の判定の結果、基本ブロックＢｉがプリディケート頂点ｖの場合は、頂点ｖの表す制御構造を生成する。まずステップＳ７で、基本ブロックＢｉの要素ｖの先行手続きに対する待ち合わせを生成する。即ち、条件式で参照する変数の値を確定するために、入力フロー依存辺について、先行する手続き呼び出しを待ち合わせる文を生成する。ここでは、当該頂点の外のループを繰り越すフロー依存辺と、当該頂点へのループ独立フロー依存辺との２種類のデータ依存入力辺について、出力元頂点の手続き終了待ち合わせを生成する。
【０１３２】
次にステップＳ８で、頂点ｖのプレディケートの種類を判定する。プレディケートがループである場合には、ステップＳ９に進む。プレディケートがｉｆ文である場合には、ステップＳ１４に進む。
【０１３３】
ステップＳ８の判定結果がループを示す場合には、ステップＳ９において、入力逐次プログラムにおいて相当するｆｏｒ文或いはｗｈｉｌｅ文を生成する。次にステップＳ１０において、頂点ｖへのL=Tの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ１１において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ１２で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ１２は入れ子構造となっており、ＢｉについてステップＳ１２を実行することは、このＢｉについて図２３全体のフローチャートを実行することに相当する。
【０１３４】
ループの終了後、ステップＳ１３で、頂点ｖへのループを繰り越す先行手続きの終了待ち合わせを生成する。これは、ループを繰り越して条件を判定するので、本文の末尾に、条件式への入力データ待ち合わせ（自ループを繰り越す入力フロー依存辺）を行なう文を追加するものである。
【０１３５】
ステップＳ８の判定結果がｉｆ文を示す場合には、ステップＳ１４において、ｉｆ文を生成する。次にステップＳ１５で、ｔｈｅｎ節を生成する。ステップＳ１６で、頂点ｖへのL=Tの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ１７において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ１８で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ１８は入れ子構造となっており、ＢｉについてステップＳ１８を実行することは、このＢｉについて図２３全体のフローチャートを実行することに相当する。なおステップＳ１７及びＳ１８で生成された文が、ｔｈｅｎ節の本文を構成することになる。
【０１３６】
次にステップＳ１９で、頂点ｖへのL=Fの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ２０で、基本ブロックの集合Ｂ'が空集合であるか否かを判定し、空集合の場合には処理を終了する。基本ブロックの集合Ｂ'が空集合でない場合、ステップＳ２１で、ｅｌｓｅ節を生成する。ステップＳ２２で、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ２３で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ２３は入れ子構造となっており、ＢｉについてステップＳ２３を実行することは、このＢｉについて図２３全体のフローチャートを実行することに相当する。なおステップＳ２２及びＳ２３で生成された文が、ｅｌｓｅ節の本文を構成することになる。
【０１３７】
以上の処理を実行することで、基本ブロックＢｉ以下の手続き制御プログラムが生成される。図２４は、第１の実施例の場合の手続き制御プログラムの構造を示す図である。
【０１３８】
図２４に示されるように、本発明の第１の実施例の場合の制御プログラムは、変数の宣言初期化部分４１、プレディケートへの入力データ待合わせ部分４２、プレディケートの制御構造の生成部分４３、基本ブロックへの入力データ・依存関係の待ち合わせ部分４４、基本ブロック内のスレッド起動と依存関係登録部分４５、及び手続きの終了の待ち合わせ終了処理部分４６を含む。基本ブロックへの入力データ・依存関係の待ち合わせ部分４４では、非同期遠隔手続き呼び出しの起動、依存関係の登録、手続きのディスパッチ（実行開始）を行う。
【０１３９】
なお第１の実施例においては、複数のプロセッサに共通の共有メモリを用いる。共有メモリを用いる場合、非同期遠隔手続き呼び出しを指示した段階では、先行する手続きの結果が得られていない可能性があり、引数として値を渡すことができない場合がある。そこで、手続きの入出力データは、共有メモリ上の適切な場所に格納されるものとし、そのアドレスを渡すこととする。
【０１４０】
即ち、手続きの生成においては、入力変数の値が格納されるアドレスと出力結果を格納するアドレスとを手続きの引数とするように、手続きを構成する。更に、頂点の部分プログラムが使用したり定義したりする変数であって、入力の変数以外の変数を求め、それらの変数に対する宣言部を生成する。更に、部分プログラムを出力し、最後に、引数として受け取ったアドレスに対して、出力する変数の値を代入する文を生成する。
【０１４１】
このように共有メモリの場合は、特定のメモリ領域への値の書き込み／参照という形で、入出力データを受け渡す。そのため、データの依存関係から、値を書き込む手続きの完了を待ち合わせて、後続の値を参照する手続きを実行することとなる。
【０１４２】
以下に、第１の実施例により生成された手続きプログラム及び手続き制御プログラムについて、その構成及び動作を具体的な例を用いて説明する。
【０１４３】
図２５は、（ａ）入力逐次プログラムの部分及び（ｂ）対応する縮退プログラム依存グラフを示す図である。図２５（ａ）に示す入力逐次プログラムからプログラム依存グラフを生成し、頂点を結合して縮退することにより、（ｂ）に示す縮退プログラム依存グラフが生成される。頂点ｖ０からｖ６が存在し、頂点ｖ４は縮退により文の集合となっている。
【０１４４】
図２６は、図２５の縮退プログラム依存グラフから第１の実施例に従い生成される手続き制御プログラムである。最初に変数の宣言があり、使用する変数ｘ，ｙ，ｚ，ａ，ｂ，ｐを宣言する。その後、まず頂点ｖ０に対応する手続きｖ０の開始を登録する（文５１）。その後のディスパッチ命令（ｄｉｓｐａｔｃｈ）により、実行可能手続きである手続きｖ０が実行される。
【０１４５】
図２５（ａ）に示す逐次プログラムのｗｈｉｌｅ文の中は、（ｂ）に示す縮退プログラム依存グラフの頂点ｖ２乃至ｖ５に対応し、１つの基本ブロックに相当する。この基本ブロック中の頂点ｖ２乃至ｖ５のうちで、ｖ３は定義順序関係に従いｖ０を待ち合わせる必要があり、ｖ２はループ繰越フロー依存に従いｖ５を待ち合わせる必要がある。従って、文５２でこれらの待ち合わせを実現する。
【０１４６】
基本ブロック中のグラフの頂点ｖ２乃至ｖ５については、手続きと依存関係の登録文５３により、手続きと依存関係とを登録する。即ち、頂点ｖ２乃至ｖ５に対応する手続きｖ２乃至ｖ５を登録すると共に、ｖ３がｖ２に依存し、ｖ５がｖ４に依存することが登録される。即ち、ａ＝Ｃ（ｘ）はｘ＝Ｂ（ｚ）が終了しないと実行できないし、ｚ＝Ｆ（ｙ）はｙ＝Ｅ（ｐ）が終了しないと実行できない。なお手続き及び依存関係の登録と手続きの実行とについては、図２に示した仕組みと同様であり、手続き呼出しプログラム３が管理する各プロセッサ毎のキューに手続きと依存関係を登録し、実行可能状態となった手続きを順次実行していく。具体的に、これらの手続きと依存関係の登録文５３の後に、ディスパッチ文５４により実行を指示する。このディスパッチ命令により、上記頂点ｖ２乃至ｖ５に対応する手続きｖ２乃至ｖ５は、各々実行可能状態となると直ちに実行される。
【０１４７】
ｗｈｉｌｅループの最後で、ｖ４の終了待ち合わせを設定する。これはｖ４によりｗｈｉｌｅ文の条件の変数ｐが計算されるためである。
【０１４８】
ｗｈｉｌｅループの後、ｖ６に対応する手続きｖ６を実行する前には、ｖ３に対する手続き終了待ち合わせが設定される（文５６）。これはｖ６がｖ３に依存し、且つｖ６とｖ３とが異なる基本ブロックに属するからである。
【０１４９】
図２７は、以上の手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。図２７では、プロセッサ０と手続きｖ０、ｖ２乃至ｖ６にそれぞれ対応するプロセッサとが用いられる。プロセッサ０により手続き制御プログラムを実行する。
【０１５０】
まず手続きｖ０の手続きプログラム６１が、対応するプロセッサにより実行される。ｗｈｉｌｅ文の条件が成立すると、手続きｖ０が実行中であるので、ｖ０の終了を待ち合わせする。
【０１５１】
手続きｖ０が終了し、手続きと依存関係が登録され、ディスパッチ命令が実行されると、手続きｖ２とｖ４とにそれぞれ対応する手続きプログラム６２及び６４が、対応するプロセッサにより実行される。また登録された依存関係に基づいて、ｖ２が終了すると直ちに、手続きｖ３の手続きプログラム６３が対応するプロセッサにより実行される。同様に、登録された依存関係に基づいて、ｖ４が終了すると直ちに、手続きｖ５の手続きプログラム６５が対応するプロセッサにより実行される。
【０１５２】
なおｖ２はループ繰越フロー依存に従いｖ５を待ち合わせる必要がある。従って、ｗｈｉｌｅ文の次のループに入った際に、手続きｖ５の手続きプログラム６５が実行中の間はｖ２やｖ４の手続きは実行されずに、手続きｖ５の終了を待ち合わせることになる。
【０１５３】
ｗｈｉｌｅ文のループが終了すると、手続きｖ３の終了を待ち合わせてから、手続きｖ６の手続きプログラム６６が対応するプロセッサにより実行される。
【０１５４】
この例において、手続きｖ１が第１の基本ブロックに属し、手続きｖ２乃至ｖ５が第２の基本ブロックに属し、手続きｖ３が第３の基本ブロックに属する。このように、異なる基本ブロックをまたいでの手続き間の依存関係（例えばｖ３からｖ０への依存関係）については、先行手続きの終了待ち合わせを行ってから、後続手続きを実行するようにする。また同一の基本ブロック内部で依存関係がある手続きｖ２乃至ｖ５の実行については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより手続きを実行する。このような構成とすることで、複雑な制御の依存関係が存在する基本ブロック間については、手続きの実行を待ち合わせにより実現することで制御プログラムの生成を容易なものとし、実行順が固定である同一基本ブロック内については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより無駄な待ち合わせ時間をなくすことができる。
【０１５５】
以下に、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を分散メモリで実現する第２の実施例について説明する。図２８は、第２の実施例の場合の制御プログラムを生成する処理のフローチャートを示す図である。図２８に示す処理は、図６のステップＳ４（及びＳ５）の処理に相当する。図２８の処理の入力は、実行順序関係が決定された縮退したプログラム依存グラフ及び基本ブロックの集合Ｂである。
【０１５６】
ステップＳ１において、プログラムの先頭を表すエントリ頂点ｖEntryの直下の子頂点ｖを要素とする基本ブロックの集合をＢ'とする。ステップＳ２において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ３で、Ｂｉについての手続き制御プログラムを生成する。ステップＳ４で、手続きの出力データ転送待ち合わせを生成する。
【０１５７】
図２９は、基本ブロックの集合Ｂ'の要素Ｂｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。図２９の処理は、図２８のステップＳ３に相当する。図２９に示す処理の入力は縮退したプログラム依存グラフＰＤＧ及び基本ブロック要素Ｂｉである。
【０１５８】
図２９のステップＳ１で、基本ブロックＢｉの要素（頂点）の種類を判定する。基本ブロックＢｉの要素である頂点の種類を判定することによって、基本ブロックＢｉがプログラム・ブロックの集合であるか、プレディケート頂点であるかが分かる。
【０１５９】
ステップＳ１の判定の結果、基本ブロックＢｉがプログラム・ブロックの集合の場合は、基本ブロックＢｉに属する頂点の手続きを呼び出す文とその間の依存関係を登録する文とを生成することとなる。具体的には、まずステップＳ２において、基本ブロックＢｉへの入力の待ち合わせを生成する。この際、ブロック外からブロック内へのフロー依存関係に関して、データ転送の待ち合わせを生成する。また定義順序関係及び逆依存関係、出力依存関係に関しても、データ転送の待ち合わせを生成する。即ち、次の５種類の辺について待ち合わせを生成する。
【０１６０】
１．Ｂｉの要素へのループ繰越フロー依存辺
２．Ｂｘの要素からＢｉの要素（i≠x）へのループ独立フロー依存辺
３．Ｂｉの要素への定義順序関係
４．Ｂｉの要素への逆依存関係
５．Ｂｉの要素への出力依存関係
なお逆依存関係がある場合は、先行頂点の手続きの終了待ち合わせを生成する。これは、制御プログラム上の同一変数に対して、データが転送される順を保証するための待ち合わせである。
【０１６１】
次にステップＳ３で、基本ブロックＢｉの各頂点ｖについて、実行順序の順番で以降の処理を繰り返すループを開始する。ステップＳ４−１で、基本ブロックを越える頂点ｖへの入力データ転送指示及び実行結果の出力データ転送指示を生成する。具体的には、ブロックを越えるデータ依存関係がある場合は、制御プロセッサ上の変数にデータがあるため、手続きを実行するプロセッサに対してこのデータを転送する。具体的には、次の２種類の辺について制御プロセッサから遠隔プロセッサへのデータ転送を生成する。
【０１６２】
１．頂点vへのループ繰越フロー依存辺
２．Ｂｉの要素でないｕから頂点vへのループ独立フロー依存辺
次にステップＳ４−２で、頂点ｖの遠隔手続き呼び出しを行う文を生成する。
【０１６３】
更にステップＳ５−１で、入力データ転送への依存関係を登録する文を生成する。ブロック内のデータ依存の場合は、先行する手続きから直接データが転送されるため、これに対する依存関係を登録する。
【０１６４】
更にステップＳ５−２で、頂点ｖからの実行結果のデータ転送を指示する文を生成する。この際、基本ブロック越えない手続きへのデータ依存の場合は、後続手続きを実行するプロセッサに直接データ転送する。また基本ブロックを越えるデータ転送の場合は、制御プロセッサへとデータを転送する。またステップＳ５−２では、これらのデータ転送指示から手続き呼び出しへの依存関係を登録する文も併せて生成する。
【０１６５】
基本ブロックＢｉの全ての頂点ｖについて上記の処理を繰り返した後に、ステップＳ６で、実行開始を指示する文を生成する。
【０１６６】
ステップＳ１の判定の結果、基本ブロックＢｉがプリディケート頂点ｖの場合は、頂点ｖの表す制御構造を生成する。まずステップＳ７で、基本ブロックＢｉの要素ｖへのデータ転送待ち合わせを生成する。即ち、条件式で参照する変数の値を確定するために、入力フロー依存辺の待ち合わせを行なう文を生成する。ここでは、当該頂点の外のループを繰り越すフロー依存辺と、当該頂点へのループ独立フロー依存辺との２種類の辺について待ち合わせを生成する。
【０１６７】
次にステップＳ８で、頂点ｖのプレディケートの種類を判定する。プレディケートがループである場合には、ステップＳ９に進む。プレディケートがｉｆ文である場合には、ステップＳ１４に進む。
【０１６８】
ステップＳ８の判定結果がループを示す場合には、ステップＳ９において、入力逐次プログラムにおいて相当するｆｏｒ文或いはｗｈｉｌｅ文を生成する。次にステップＳ１０において、頂点ｖへのL=Tの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ１１において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ１２で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ１２は入れ子構造となっており、ＢｉについてステップＳ１２を実行することは、このＢｉについて図２９全体のフローチャートを実行することに相当する。
【０１６９】
ループの終了後、ステップＳ１３で、プレディケート頂点ｖへのデータ転送待ち合わせを生成する。これは、ループを繰り越して条件を判定するので、本文の末尾に、条件式への入力データ待ち合わせ（自ループを繰り越す入力フロー依存辺）を行なう文を追加するものである。
【０１７０】
ステップＳ８の判定結果がｉｆ文を示す場合には、ステップＳ１４において、ｉｆ文を生成する。次にステップＳ１５で、ｔｈｅｎ節を生成する。ステップＳ１６で、頂点ｖへのL=Tの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ１７において、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ１８で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ１８は入れ子構造となっており、ＢｉについてステップＳ１８を実行することは、このＢｉについて図２９全体のフローチャートを実行することに相当する。なおステップＳ１７及びＳ１８で生成された文が、ｔｈｅｎ節の本文を構成することになる。
【０１７１】
次にステップＳ１９で、頂点ｖへのL=Fの制御依存関係がある頂点ｕを要素とする基本ブロックの集合をＢ'とする。ステップＳ２０で、基本ブロックの集合Ｂ'が空集合であるか否かを判定し、空集合の場合には処理を終了する。基本ブロックの集合Ｂ'が空集合でない場合、ステップＳ２１で、ｅｌｓｅ節を生成する。ステップＳ２２で、Ｂ'の各要素Ｂｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ２３で、Ｂｉについての手続き制御プログラムを生成する。このステップＳ２３は入れ子構造となっており、ＢｉについてステップＳ２３を実行することは、このＢｉについて図２９全体のフローチャートを実行することに相当する。なおステップＳ２２及びＳ２３で生成された文が、ｅｌｓｅ節の本文を構成することになる。
【０１７２】
以上の処理を実行することで、基本ブロックＢｉ以下の手続き制御プログラムが生成される。図３０は、第２の実施例の場合の手続き制御プログラムの構造を示す図である。
【０１７３】
図３０に示されるように、本発明の第２の実施例の場合の制御プログラムは、変数の宣言初期化部分７１、プレディケートへの入力データ待合わせ部分７２、プレディケートの制御構造の生成部分７３、基本ブロックへの入力データ待ち合わせ部分７４、基本ブロック内のスレッド起動と依存関係登録部分７５、及び手続き及びデータ転送の待ち合わせ終了処理部分７６を含む。基本ブロックへの入力データ待ち合わせ部分７４では、手続きの入力データの転送指示、遠隔手続き呼び出しの起動指示、手続きの出力データの転送指示、及び依存関係の登録を行う。第２の実施例では、手続き間の待ち合わせは、データ転送の待ち合わせとなる。
【０１７４】
第２の実施例では、各プロセッサに設けた個別のメモリである分散メモリを使用する。この場合、手続きの入力データは、制御プロセッサから実行するプロセッサに転送するものとし、出力データは遠隔プロセッサから制御プロセッサに転送されるものとする。ただし、基本ブロック内については、手続きを実行するプロセッサ間で、直接データの転送を行うものとする。
【０１７５】
即ち、手続きの生成においては、入出力変数のためのデータ領域は予め用意し、入力データは予め実行するプロセッサ上に転送されているものとする。また、実行結果は、実行するプロセッサ上に格納し、制御プログラムによって必要とされるプロセッサへ適宜その値を転送されるものとする。
【０１７６】
更に、頂点の部分プログラムが使用したり定義したりする変数であって、入力の変数以外の変数を求め、それらの変数に対する宣言部を生成する。更に、部分プログラムを出力し、最後に、引数として受け取ったアドレスに対して、出力する変数の値を代入する文を生成する。
【０１７７】
以下に、第２の実施例により生成された手続きプログラム及び手続き制御プログラムについて、その構成及び動作を具体的な例を用いて説明する。
【０１７８】
この例で用いる入力逐次プログラムの部分及び縮退プログラム依存グラフは、第１の実施例の場合と同じであり、図２５（ａ）及び（ｂ）にそれぞれ示すものである。図２５（ａ）に示す入力逐次プログラムからプログラム依存グラフを生成し、頂点を結合して縮退することにより、（ｂ）に示す縮退プログラム依存グラフが生成される。頂点ｖ０からｖ６が存在し、頂点ｖ４は縮退により文の集合となっている。
【０１７９】
図３１は、図２５の縮退プログラム依存グラフから第２の実施例に従い生成される手続き制御プログラムを示す図である。最初に変数の宣言があり、使用する変数ｘ，ｙ，ｚ，ａ，ｂ，ｐを宣言する。第２の実施例では分散メモリを想定しているので、各頂点ｖ０及びｖ２乃至ｖ６に対応する手続きｖ０及びｖ２乃至ｖ６のそれぞれについて、入力のデータ転送指示及び入力のデータ転送に対する手続きの依存関係、並びに、実行結果のデータ転送指示及び手続きに対する実行結果のデータ転送指示の依存関係が規定される。例えば、頂点ｖ０に対応する手続きｖ０の場合、入力のデータ転送指示８１、手続きｖ０の呼び出し指示８２、入力のデータ転送に手続きｖ０が依存するという依存関係の指定８３、実行結果のデータ転送指示８４、及び手続きｖ０に実行結果のデータ転送が依存するという依存関係の指定８５が規定されており、これらが登録されることになる。その後のディスパッチ命令により手続きｖ０が実行される。
【０１８０】
データ転送指示及びその依存関係の指示が含まれていることを除いて、プログラムの制御構造は図２６の場合と同様である。従って、詳細な説明については省略する。
【０１８１】
図３２は、以上の手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。図３２では、プロセッサ０と手続きｖ０、ｖ２乃至ｖ６にそれぞれ対応するプロセッサとが用いられる。また更に、データ転送ユニットＤＴＵ＃０乃至ＤＴＵ＃３が用いられる。プロセッサ０により手続き制御プログラムを実行する。
【０１８２】
まずデータ転送ユニットＤＴＵ＃０により、データａを手続きｖ０のプロセッサに転送する。それに応じて、手続きｖ０の手続きプログラム９１が、対応するプロセッサにより実行される。ｗｈｉｌｅ文の条件が成立すると、手続きｖ０の実行結果の転送が未完了であるので、ｖ０からのデータ転送を待ち合わせする。
【０１８３】
手続きｖ０からデータａがプロセッサ０に転送されると、それに応答して、手続きｖ２とｖ４とにそれぞれ対応する手続きプログラム９２及び９４が、対応するプロセッサにより実行される。この際、データ転送ユニットＤＴＵ＃１によりデータｚ及びｘを転送する。またデータ転送ユニットＤＴＵ＃２によりデータｐを転送する。
【０１８４】
また登録された依存関係に基づいて、データ転送ユニットＤＴＵ＃１を介した手続きｖ２の出力データｘの転送に応答して、手続きｖ３の手続きプログラム９３が対応するプロセッサにより実行される。同様に、登録された依存関係に基づいて、データ転送ユニットＤＴＵ＃３を介した手続きｖ４の出力データｙの転送に応答して、手続きｖ５の手続きプログラム９５が対応するプロセッサにより実行される。
【０１８５】
なおｖ２はループ繰越フロー依存に従いｖ５のデータｚを待ち合わせる必要がある。従って、ｗｈｉｌｅ文の次のループに入った際に、手続きｖ５の手続きプログラム９５が実行中の間はｖ２やｖ４の手続きは実行されずに、手続きｖ５の終了によるデータｚの転送を待ち合わせることになる。
【０１８６】
ｗｈｉｌｅ文のループが終了すると、手続きｖ３の出力データａの転送を待ち合わせてから、手続きｖ６の手続きプログラム９６が対応するプロセッサにより実行される。
【０１８７】
この例において、手続きｖ１が第１の基本ブロックに属し、手続きｖ２乃至ｖ５が第２の基本ブロックに属し、手続きｖ３が第３の基本ブロックに属する。このように、異なる基本ブロックをまたいでの手続き間の依存関係（例えばｖ３からｖ０への依存関係）については、先行手続きからのデータ転送待ち合わせを行ってから、後続手続きを実行するようにする。また同一の基本ブロック内部で依存関係がある手続きｖ２乃至ｖ５の実行については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより手続きを実行する。このような構成とすることで、複雑な制御の依存関係が存在する基本ブロック間については、手続きの実行を待ち合わせにより実現することで制御プログラムの生成を容易なものとし、実行順が固定である同一基本ブロック内については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより無駄な待ち合わせ時間をなくすことができる。
【０１８８】
図３３は、本発明による並列化プログラム生成方法を実行する装置の構成を示す図である。
【０１８９】
図３３に示されるように、本発明による並列化プログラム生成方法を実行する装置は、例えばパーソナルコンピュータやエンジニアリングワークステーション等のコンピュータにより実現される。図３３の装置は、コンピュータ５１０と、コンピュータ５１０に接続されるディスプレイ装置５２０、通信装置５２３、及び入力装置よりなる。入力装置は、例えばキーボード５２１及びマウス５２２を含む。コンピュータ５１０は、ＣＰＵ５１１、ＲＡＭ５１２、ＲＯＭ５１３、ハードディスク等の二次記憶装置５１４、可換媒体記憶装置５１５、及びインターフェース５１６を含む。
【０１９０】
キーボード５２１及びマウス５２２は、ユーザとのインターフェースを提供するものであり、コンピュータ５１０を操作するための各種コマンドや要求されたデータに対するユーザ応答等が入力される。ディスプレイ装置５２０は、コンピュータ５１０で処理された結果等を表示すると共に、コンピュータ５１０を操作する際にユーザとの対話を可能にするために様々なデータ表示を行う。通信装置５２３は、遠隔地との通信を行なうためのものであり、例えばモデムやネットワークインターフェース等よりなる。
【０１９１】
本発明による並列化プログラム生成方法は、コンピュータ５１０が実行可能なコンピュータプログラムとして提供される。このコンピュータプログラムは、可換媒体記憶装置５１５に装着可能な記憶媒体Ｍに記憶されており、記憶媒体Ｍから可換媒体記憶装置５１５を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。或いは、このコンピュータプログラムは、遠隔地にある記憶媒体（図示せず）に記憶されており、この記憶媒体から通信装置５２３及びインターフェース５１６を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。
【０１９２】
キーボード５２１及び／又はマウス５２２を介してユーザからプログラム実行指示があると、ＣＰＵ５１１は、記憶媒体Ｍ、遠隔地記憶媒体、或いは二次記憶装置５１４からプログラムをＲＡＭ５１２にロードする。ＣＰＵ５１１は、ＲＡＭ５１２の空き記憶空間をワークエリアとして使用して、ＲＡＭ５１２にロードされたプログラムを実行し、適宜ユーザと対話しながら処理を進める。なおＲＯＭ５１３は、コンピュータ５１０の基本動作を制御するための制御プログラムが格納されている。
【０１９３】
上記コンピュータプログラム（並列化プログラム生成プログラム即ち並列化プログラム生成コンパイラ）を実行することにより、コンピュータ５１０が、上記各実施例で説明されたように並列化プログラム生成方法を実行する。
【０１９４】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【０１９５】
【図１】無駄な待ち時間の発生について説明するための図である。
【図２】依存関係待ち合わせ付き非同期遠隔手続呼び出し方式による手続実行の制御について説明するための図である。
【図３】本発明による並列化プログラム生成方法の概略を示す図である。
【図４】手続きプログラム生成方法の概要を示す図である。
【図５】図４の手続きプログラム生成方法により生成される手続きプログラムを示す図である。
【図６】手続き制御プログラムの生成方法を示すフローチャートである。
【図７】頂点間の実行順序関係を決定する方法を示すフローチャートである。
【図８】頂点ｖ以下の制御の流れを再構成する処理（図７のステップＳ２）を示すフローチャートである。
【図９】Regionの実行順序関係を計算する処理を示すフローチャートである。
【図１０】逆依存及び出力依存を求める処理（図９のステップＳ４）を示すフローチャートである。
【図１１】着目領域を越える変数参照を抽出する処理を示すフローチャートである。
【図１２】着目領域を越える変数代入を抽出する処理を示すフローチャートである。
【図１３】逆依存の追加処理を示すフローチャートである。
【図１４】出力依存の追加処理を示すフローチャートである。
【図１５】逆依存及び出力依存を求める処理（図９のステップＳ５）を示すフローチャートである。
【図１６】全域木を説明するための図である。
【図１７】全域木を模式的に示す図である。
【図１８】全域木間の順序関係を計算する処理を示すフローチャートである。
【図１９】図１８の処理による逆依存辺の追加について説明する図である。
【図２０】頂点間の実行順序関係を決定する方法の変形例を示すフローチャートである。
【図２１】基本ブロックを抽出する処理のフローチャートを示す図である。
【図２２】制御プログラムを生成する処理のフローチャートを示す図である。
【図２３】基本ブロックの集合Ｂ'の要素Ｂｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。
【図２４】第１の実施例の場合の手続き制御プログラムの構造を示す図である。
【図２５】（ａ）は入力逐次プログラムの部分を示す図、（ｂ）は対応する縮退プログラム依存グラフを示す図である。
【図２６】図２５の縮退プログラム依存グラフから第１の実施例に従い生成される手続き制御プログラムを示す図である。
【図２７】手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。
【図２８】第２の実施例の場合の制御プログラムを生成する処理のフローチャートを示す図である。
【図２９】基本ブロックの集合Ｂ'の要素Ｂｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。
【図３０】第２の実施例の場合の手続き制御プログラムの構造を示す図である。
【図３１】図２５の縮退プログラム依存グラフから第２の実施例に従い生成される手続き制御プログラムを示す図である。
【図３２】手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。
【図３３】本発明による並列化プログラム生成方法を実行する装置の構成を示す図である。
【符号の説明】
【０１９６】
１０  入力変数の引数受信部分
１１  変数宣言部分
１２  プログラム本体部分
１３  出力変数の送信部分
２１，２２  全域木
３１  出力依存辺
３２，３３  逆依存辺
５１０  コンピュータ
５１１  ＣＰＵ
５１２  ＲＡＭ
５１３  ＲＯＭ
５１４  二次記憶装置
５１５  可換媒体記憶装置
５１６  インターフェース
５２０  ディスプレイ装置
５２１  キーボード
５２２  マウス
５２３  通信装置
【図１】
2008090541.tif 000004
【図２】
2008090541.tif 000005
【図３】
2008090541.tif 000006
【図４】
2008090541.tif 000007
【図５】
2008090541.tif 000008
【図６】
2008090541.tif 000009
【図７】
2008090541.tif 000010
【図８】
2008090541.tif 000011
【図９】
2008090541.tif 000012
【図１０】
2008090541.tif 000013
【図１１】
2008090541.tif 000014
【図１２】
2008090541.tif 000015
【図１３】
2008090541.tif 000016
【図１４】
2008090541.tif 000017
【図１５】
2008090541.tif 000018
【図１６】
2008090541.tif 000019
【図１７】
2008090541.tif 000020
【図１８】
2008090541.tif 000021
【図１９】
2008090541.tif 000022
【図２０】
2008090541.tif 000023
【図２１】
2008090541.tif 000024
【図２２】
2008090541.tif 000025
【図２３】
2008090541.tif 000026
【図２４】
2008090541.tif 000027
【図２５】
2008090541.tif 000028
【図２６】
2008090541.tif 000029
【図２７】
2008090541.tif 000030
【図２８】
2008090541.tif 000031
【図２９】
2008090541.tif 000032
【図３０】
2008090541.tif 000033
【図３１】
2008090541.tif 000034
【図３２】
2008090541.tif 000035
【図３３】
2008090541.tif 000036