JP4946323B2 - 並列化プログラム生成方法、並列化プログラム生成装置、及び並列化プログラム生成プログラム - Google Patents

Description

本発明は、一般にプログラム生成方法、装置、及びプログラムに関し、詳しくは並列化プログラム生成方法、装置、及びプログラムに関する。

近年、シングル・プロセッサでのプログラム性能には限界があることが知られてきた。従来、性能を上げるためには、プロセッサの動作周波数を高くすることで単位時間あたりの処理量を増やす方法と、命令を並列に実行することで同時に実行できる処理を増やす方法とがとられてきた。

しかし動作周波数を高くすると消費電力が大きくなるという問題があるとともに、動作周波数の向上には物理的な限界があるという問題がある。また、命令レベルの並列性は高々２〜４程度であり（非特許文献１）、投機的な実行などを導入することにより多少並列性を上げることはできるが、それにも限界があることが知られている。

そこで、命令レベルよりも大きな粒度でプログラムを並列化し、複数のプロセッサにて実行することにより、処理性能を向上させる方法が注目されている。しかしながら、制御による分岐が多い逐次プログラムを効果的な並列プログラムへ変換する画一的な方法は、これまでのところ知られていない。

逐次プログラムを分割して複数のプロセッサ上で並列に実行するプログラムを生成する手法として、ループに着目したデータ・レベル並列化という方法と、制御に着目した投機的なスレッド実行という方法が知られている。

特許文献１では、ループの中におけるデータの依存関係を解析し、配列を分割して、ループの処理を複数のプロセッサで実行させる。この手法は、数値計算等の規則的なループの処理が多い場合に有効である。

また特許文献２は、逐次プログラムにおける分岐に着目して、投機的なスレッド実行に置換する手法を示す。この手法では、制御の流れに基づいてプログラムを並列化するので、プログラムの潜在的な並列性を充分に抽出できているとはいえない。また、投機的スレッド実行機構を持たないマルチプロセッサにおいては予測失敗時のロールバックのコストが大きいので、分岐予測ヒット率が低いアプリケーションにはこの手法は適さない。

従って、大規模なソフトウェアを対象として、逐次プログラムを並列化することにより、マルチプロセッサ上で効果的に動作する非投機的なマルチ・スレッド・プログラム（並列化プログラム）を生成する方法を提供することが必要になる。但し、このようにして生成する並列化プログラムにおいては、以下に説明するように、スレッド間の依存関係に基づく待ち時間の発生という問題について考慮する必要がある。

並列化プログラムの各スレッドの実行を制御する方式としては、例えば、手続を非同期の遠隔呼び出しとして呼び出すことにより並列にスレッドを実行する方式、手続に実行開始するメッセージを送信することにより並列にスレッドを実行する方式、スレッド間で共有メモリを利用して入出力変数の受け渡しを行なうことにより並列にスレッドを実行する方式等が考えられる。しかしこれらの方式では、第１の手続（スレッド）の実行結果を利用する第２の手続がある場合、第１の手続の終了を待つ命令とそれに続く第２の手続を実行する命令とを、他の手続の実行に要する時間などを見積もって、プログラム中の適当な場所に配置しておくことになる。この場合、第１の手続が予想以上に早く終了した場合などに、第２の手続を実行するまでに、不必要な待ち時間が発生してしまう。

図１は、無駄な待ち時間の発生について説明するための図である。図１において、プロセッサ０乃至プロセッサ３の４つのプロセッサが用いられる。プロセッサ０でスレッド制御プログラム１（各スレッドに対応する手続の実行及び終了待ちを制御するプログラム）を実行する。図１の例では、まずプロセッサ０から、プロセッサ１乃至プロセッサ３に対して手続Ａ乃至Ｃの実行を順番に要求する（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→_c ^L w］プリディケート頂点vに対して、その条件判定結果により、頂点wに到達するか否かが決まることを表す。Lは条件判定のフラグを表し、L=Tのときは条件判定結果が真の場合に頂点wを実行し、L=Fのときは結果が偽の場合に頂点wを実行する。

［データ依存辺］
［ループ独立フロー依存辺: v→_li ^x 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→_c ^L w］プリディケート頂点vに対して、その条件判定結果により、頂点wに到達するか否かが決まることを表す。Lは条件判定のフラグを表し、L=Tのときは条件判定結果が真の場合に頂点wを実行し、L=Fのときは結果が偽の場合に頂点wを実行する。

［データ依存辺］
［ループ独立フロー依存辺: v→_li ^x 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→_c ^Tu ∈ E}が空集合であるか否かを判断する。空集合であれば処理を終了し、空集合でなければステップＳ２に進む。ここでRegion(v, T)とは、頂点uの集合であって、頂点vから頂点uへのL=Fの制御依存関係が存在するものである。ここでＶは頂点集合、Ｅは辺集合、v→_c ^TuはL=Fの制御依存辺を示すものである。

ステップＳ２で、Region(v, T)の実行順序関係を計算する。ステップＳ３で、Region(v, F) = {u | u ∈ V, v→_c ^Fu ∈ 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→_li ^xu ∈ E_R}
と定義される。図１６は、全域木を説明するための図である。図１６に示されるプログラム依存グラフにおいて、頂点ｖ_ｉにおいて変数ｘが定義され、２つの頂点ｖ１及びｖ２が変数ｘを使用する。この場合、頂点ｖ_ｉ、ｖ１、及びｖ２で全域木２１を形成する。また頂点ｖ_ｊにおいて変数ｘが定義され、２つの頂点ｖ３及びｖ４が変数ｘを使用する。この場合、頂点ｖ_ｊ、ｖ３、及びｖ４で全域木２２を形成する。図１７は、全域木を模式的に示す図である。全域木Span(v_ｉ, x)及び全域木Span(v_ｊ, x)が、データ依存グラフとして図１７に示されるように構成される。

図１５に戻り、ステップＳ２で、実行順が未決定である２つの任意の全域木を順次選択して以降の処理を繰り返すループが開始される。ステップＳ３で、着目領域に閉路がなく、同一変数xに対する独立した全域木Span(h₀,x)及びSpan(h₁,x)が存在するか否かを判定する。ここで、「独立した」とは、２つの全域木 Span(h₀,x)及びSpan(h₁,x)について、Span(h₀,x)に含まれる頂点とSpan(h₁,x)に含まれる頂点との間に辺（依存関係）がないことを言う。

ステップＳ４でR（Region）のオリジナルをスタックに退避させる。ステップＳ５で、h₀→h₁の出力依存辺を追加し、推移閉包を求める。ステップＳ６で、全域木間の順序関係を計算する。

ステップＳ７で、Ｒ（Region）に閉路が存在するか否かを判定する。存在しない場合には、以降の処理ステップＳ８〜ステップＳ１１をスキップする。存在する場合には、ステップＳ８に進む。ステップＳ８で、スタックが空か否かを判断する。空の場合にはエラー終了する。空でない場合には、ステップＳ９で、Ｒのオリジナルをスタックから取り出す。

以上の処理は、頂点h₀からh₁への出力依存関係をグラフに追加したときに、巡回グラフとならない場合には追加した依存関係を確定させ、巡回グラフになった場合には元のグラフに戻すことに相当する。元のグラフに戻した後は、以降に示すように、頂点h₁からh₀への出力依存関係をグラフに追加する。即ち、ステップＳ１０で、h₁→h₀の出力依存辺を追加し、推移閉包を求める。ステップＳ１１で、全域木間の順序関係を計算する。

以上の処理により、２つの全域木 Span(h₀,x)及びSpan(h₁,x)に対する実行順序が決定する。更に、実行順が未決定である２つの任意の全域木を順次選択して同様の処理を繰り返し、全ての全域木間の順序関係が決定されたところで終了する。

図１８は、全域木間の順序関係を計算する処理を示すフローチャートである。図１８の処理は、図１５のステップＳ６及びステップＳ１１に相当する。図１８の処理の入力は、縮退したプログラム依存グラフＰＤＧ及びV'（着目Region）である。

ステップＳ１で、着目領域内の各辺ｅ（頂点ｖ→頂点ｗ）について以降の処理を繰り返すループを開始する。ステップＳ２で、頂点ｗで定義され、頂点ｖで参照される各変数ｘについて以降の処理を繰り返すループを開始する。

ステップＳ３で、V_a ← { u | v ∈ Span(u, x) }とするとともに、V_b ← { u | w ∈ Span(u, x) }とする。これは、頂点ｖを要素として含む変数ｘに関する全域木における変数ｘを定義する頂点の集合を求めるとともに、頂点ｗを要素として含む変数ｘに関する全域木における変数ｘを定義する頂点の集合を求めることである。

ステップＳ４で、Ｖ_ａの各頂点ｖ_ａについて以降の処理を繰り返すループを開始する。ステップＳ５で、Ｖ_ｂの各頂点ｖ_ｂについて以降の処理を繰り返すループを開始する。更にステップＳ６で、Span(v_a, x)の頂点であってSpan(v_b, x)の頂点でない各頂点ｖ_ｃについて以降の処理を繰り返すループを開始する。

ステップＳ７で、ｖｃ→ｖｂがＥ（辺集合）に含まれるか否かを判定する。判定結果がｙｅｓの場合のみステップＳ８を実行する。ステップＳ８で、ｖ_ｃ→ｖ_ｂの逆依存辺を追加し、推移閉包を求める。以降、各ループの処理を繰り返す。

図１９は、図１８の処理による逆依存辺の追加について説明する図である。図１９には、頂点ｖの変数ｘに関する全域木Span(v,x)と頂点ｗの変数ｘに関する全域木Span(w,x)とが示される。頂点ｖを要素として含む変数ｘに対する全域木Span(v_a, x)（即ちSpan(v,x)）の各頂点ｖ_ｃ（即ちｖ、２５、２６）に対して、全域木Span(v_b, x)（即ちSpan(ｗ,x)）のヘッドｖ_ｂ（変数を定義している頂点ｗ）への逆依存辺３２、３３を追加する。

図２０は、頂点間の実行順序関係を決定する方法の変形例を示すフローチャートである。図２０のフローチャートに示す処理を、図７のフローチャートに示す処理の代わりに用いてもよい。即ち、頂点間の実行順序関係を決定する処理において、前段階のステップＳ０として、ＳＳＡ（静的単一代入形式）を適用する処理を実行してもよい。即ち、縮退プログラム依存グラフを静的単一代入形式に変換してもよい。この場合、図９に示すステップＳ７の処理（逆依存、出力依存を求め着目領域内の実行順序を決定する処理：図１５のフローチャート）を省略することができる。

以上により、頂点間の実行順序関係を決定し、逆／出力依存関係を抽出することができる。即ち、図６のステップＳ１の処理が実行される。

図２１は、基本ブロックを抽出する処理のフローチャートを示す図である。図２１に示す処理は、図６のステップＳ２の処理に相当する。図２１の処理の入力は、実行順序関係が決定された縮退したプログラム依存グラフである。

求めた制御の流れの順に頂点を探索し、頂点の種類に応じた処理を行なう。以下の説明においてＢは基本ブロックの集合であり、Ｂ_ｉはｉ番目の基本ブロックである。またｖは現在の頂点（着目頂点）であり、ｕは現在の頂点の１つ前の頂点である。

まずステップＳ２で、最初の基本ブロックＢ０を空集合として生成する。次にステップＳ２で、ｕをエントリ頂点（プログラムの開始ポイント）として、ｖをエントリ頂点の次の頂点とする。ステップＳ４で、現在の頂点ｖが最終頂点であるか否かを判断する。最終頂点である場合には、処理を終了して基本ブロックの集合Ｂが生成される。

現在の頂点ｖが最終頂点でない場合には、ステップＳ５に進み、現在の頂点ｖがプレディケート頂点（If-then-else又はwhile-loopの条件判定を表す頂点）であるか否かを判断する。プリディケート頂点である場合には、ステップＳ６に進み、ｉをインクリメントしてからＢ_ｉの要素をｖとすることで、新たなプリディケートのみの基本ブロックＢ_ｉを形成する。その後ステップＳ７で、更にｉをインクリメントして、新たな空集合の基本ブロックＢ_ｉを形成する。

現在の頂点ｖがプレディケート頂点でない場合（Ｓ５でＮｏの場合）には、ステップＳ８で、現在の頂点ｖと１つ前の頂点ｕとが、同一のプレディケート頂点からの制御依存関係を有し、且つその制御依存関係が同一の条件判定フラグに基づくものであるか否かを判定する。この判定結果がＮＯとなるのは、例えばｕとｖとが、ＩＦ文の内部と外部とに対応する場合や、ＩＦ文のＴＨＥＮ節とＥＬＳＥ節とに対応する場合等である。即ち、ステップＳ８においては、同一の条件判定に応じて双方共に実行される２つの頂点であるか否かが判定されている。

ステップＳ８の判定がＹＥＳの場合には、ステップＳ９で、現在の基本ブロックに現在の頂点ｖを追加する。ステップＳ８の判定がＮＯの場合には、ステップＳ１０で、ｉをインクリメントして新たな空集合の基本ブロックＢ_ｉを形成する。その後ステップＳ１１で、この新たに生成された基本ブロックＢ_ｉに現在の頂点ｖを追加する。その後ステップＳ１２でｕとｖとをそれぞれ次の頂点に更新し、ステップＳ４に戻り以降の処理を繰り返す。

以上の処理により、分岐（ＩＦ、ＧＯＴＯ、ＬＯＯＰ等）や合流を含まない順番に実行される頂点の列である各基本ブロックＢ_ｉを生成し、これらの基本ブロックを要素とする基本ブロックの集合Ｂを生成することができる。分岐や合流を含まない頂点の列とは、固定の１つの実行順に従い順番に実行される頂点の列のことである。図２１のフローチャートから分かるように、各プレディケート頂点は単独で１つの基本ブロックＢ_ｉを構成し、プレディケート頂点でない１つの基本ブロックＢ_ｉには、途中で分岐も合流もなく固定の１つの実行順に従い順番に実行される頂点の列が含まれることになる。

本発明では、異なる基本ブロックをまたいでの手続き間の依存関係については、先行手続きの終了待ち合わせを行ってから、後続手続きを実行するようにする。また同一の基本ブロック内部で依存関係がある手続きの実行については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより手続きを実行する。即ち、基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置することにより、依存関係を満たすように手続き制御する。また同一の基本ブロック内部で依存関係がある手続きについては後続手続きの先行手続きへの依存関係を明示的に登録する命令を生成するようにして、依存関係を満たすように手続き制御する。このような構成とすることで、複雑な制御の依存関係が存在する基本ブロック間については、手続きの実行を待ち合わせにより実現することで制御プログラムの生成を容易なものとし、実行順が固定である同一基本ブロック内については、依存関係待ち合わせ付き非同期遠隔手続呼び出しにより無駄な待ち合わせ時間をなくすことができる。

以上により、基本ブロックを抽出することができる。即ち、図６のステップＳ２の処理が実行される。

以下において、制御プログラムを生成する処理や生成した制御プログラムの具体例等について説明する。以下の説明は、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を共有メモリで実現する第１の実施例と、依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を分散メモリで実現する第２の実施例とで異なる。

まず依存関係待ち合わせ付き非同期遠隔手続き呼び出し方式を共有メモリで実現する第１の実施例について説明する。

図２２は、制御プログラムを生成する処理のフローチャートを示す図である。図２２に示す処理は、図６のステップＳ４（及びＳ５）の処理に相当する。図２２の処理の入力は、実行順序関係が決定された縮退したプログラム依存グラフ及び基本ブロックの集合Ｂである。

ステップＳ１において、プログラムの先頭を表すエントリ頂点ｖ_Entryの直下の子頂点ｖを要素とする基本ブロックの集合をＢ'とする。ステップＳ２において、Ｂ'の各要素Ｂ_ｉについて、ｉの昇順に以降の処理を繰り返すループを開始する。ステップＳ３で、Ｂ_ｉについての手続き制御プログラムを生成する。ステップＳ４で、手続きの終了待ち合わせを生成する。

図２３は、基本ブロックの集合Ｂ'の要素Ｂ_ｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。図２３の処理は、図２２のステップＳ３に相当する。図２３に示す処理の入力は縮退したプログラム依存グラフＰＤＧ及び基本ブロック要素Ｂ_ｉである。

なおここでは、全ての手続き呼び出しを待ち合わせる方法と、制御の流れによって、待ち合わせが行なわれない可能性がある全ての手続き呼び出しを待ち合わせる方法の2つが考えられる。制御の流れによらず必ず待ち合わせが行なわれる頂点V'の集合は次のように表現できる。

従って、待ち合わせが行なわれない頂点の集合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の実行順序関係を計算する処理を示すフローチャートである。 逆依存及び出力依存を求める処理（図９のステップＳ４）を示すフローチャートである。 着目領域を越える変数参照を抽出する処理を示すフローチャートである。 着目領域を越える変数代入を抽出する処理を示すフローチャートである。 逆依存の追加処理を示すフローチャートである。 出力依存の追加処理を示すフローチャートである。 逆依存及び出力依存を求める処理（図９のステップＳ５）を示すフローチャートである。 全域木を説明するための図である。 全域木を模式的に示す図である。 全域木間の順序関係を計算する処理を示すフローチャートである。 図１８の処理による逆依存辺の追加について説明する図である。 頂点間の実行順序関係を決定する方法の変形例を示すフローチャートである。 基本ブロックを抽出する処理のフローチャートを示す図である。 制御プログラムを生成する処理のフローチャートを示す図である。 基本ブロックの集合Ｂ'の要素Ｂ_ｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。 第１の実施例の場合の手続き制御プログラムの構造を示す図である。 （ａ）は入力逐次プログラムの部分を示す図、（ｂ）は対応する縮退プログラム依存グラフを示す図である。 図２５の縮退プログラム依存グラフから第１の実施例に従い生成される手続き制御プログラムを示す図である。 手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。 第２の実施例の場合の制御プログラムを生成する処理のフローチャートを示す図である。 基本ブロックの集合Ｂ'の要素Ｂ_ｉ以下の手続き制御プログラムを生成する処理を示すフローチャートである。 第２の実施例の場合の手続き制御プログラムの構造を示す図である。 図２５の縮退プログラム依存グラフから第２の実施例に従い生成される手続き制御プログラムを示す図である。 手続き制御プログラムの動作を手続きプログラムの実行とともに示す模式図である。 本発明による並列化プログラム生成方法を実行する装置の構成を示す図である。

符号の説明

１０ 入力変数の引数受信部分
１１ 変数宣言部分
１２ プログラム本体部分
１３ 出力変数の送信部分
２１，２２ 全域木
３１ 出力依存辺
３２，３３ 逆依存辺
５１０ コンピュータ
５１１ ＣＰＵ
５１２ ＲＡＭ
５１３ ＲＯＭ
５１４ 二次記憶装置
５１５ 可換媒体記憶装置
５１６ インターフェース
５２０ ディスプレイ装置
５２１ キーボード
５２２ マウス
５２３ 通信装置

Claims (10)

1. 逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
   該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
   該縮退プログラム依存グラフの頂点の実行順序を計算し、
   該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、
   該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
   該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
   各段階を含み、該各段階をコンピュータが実行することを特徴とする並列化プログラム生成方法。
2. コンピュータが実行する段階であって該手続き制御プログラムを生成する段階は、プロセッサに共通の共有メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きの終了を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成する段階をコンピュータが実行することを特徴とする請求項１記載の並列化プログラム生成方法。
3. コンピュータが実行する段階であって該手続き制御プログラムを生成する段階は、プロセッサ毎に設けた分散メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きからのデータ転送を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成する段階をコンピュータが実行することを特徴とする請求項１記載の並列化プログラム生成方法。
4. コンピュータが実行する段階であって該手続き制御プログラムを生成する段階は、入力データのデータ転送に対する手続きの依存関係を登録する命令及び手続きに対する出力データのデータ転送の依存関係を登録する命令を生成する段階をコンピュータが実行することを特徴とする請求項３記載の並列化プログラム生成方法。
5. コンピュータが実行する段階であって該実行順序を計算する段階において、該縮退プログラム依存グラフを静的単一代入形式に変換する段階であってコンピュータが実行する段階を含むことを特徴とする請求項２記載の並列化プログラム生成方法。
6. 逐次プログラムと並列化プログラム生成プログラムとを格納するメモリと、
   該メモリに格納された該並列化プログラム生成プログラムを実行することで該メモリに格納された該逐次プログラムから並列化プログラムを生成する演算処理ユニットを含み、該演算処理ユニットは、該並列化プログラム生成プログラムを実行することにより、
   該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
   該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
   該縮退プログラム依存グラフの頂点の実行順序を計算し、
   該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まずに順番に実行される頂点列を基本ブロックとして纏め、
   該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
   該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
   ことを特徴とする並列化プログラム生成装置。
7. 該演算処理ユニットは、プロセッサに共通の共有メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きの終了を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項６記載の並列化プログラム生成装置。
8. 該演算処理ユニットは、プロセッサ毎に設けた分散メモリへの値の書き込み及び参照により該手続き間のデータの転送を実現し、該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きからのデータ転送を待ち合わせてから後続手続きを実行するように該手続き制御プログラムを生成することを特徴とする請求項６記載の並列化プログラム生成装置。
9. 該演算処理ユニットは、入力データのデータ転送に対する手続きの依存関係を登録する命令及び手続きに対する出力データのデータ転送の依存関係を登録する命令を生成することを特徴とする請求項８記載の並列化プログラム生成装置。
10. 逐次プログラムを入力として、該逐次プログラムを構成する各文を頂点として有するとともに、文と文の間の関係を該頂点間の辺として有するプログラム依存グラフを生成し、
    該プログラム依存グラフの該頂点同士を融合することにより該頂点の数を減少させた縮退プログラム依存グラフを生成し、
    該縮退プログラム依存グラフの頂点の実行順序を計算し、
    該実行順序を与えられた該複数の頂点のうちで分岐及び合流の何れも含まない頂点列を基本ブロックとして纏め、
    該縮退プログラム依存グラフの頂点の各々に相当する手続きを生成し、
    該基本ブロック間をまたいでの依存関係がある手続きについては先行手続きを待ち合わせる命令の後に後続手続きを実行する命令を配置し、同一の基本ブロック内部で依存関係がある手続きについては先行手続きに対する後続手続きの依存関係を登録する命令を生成するようにして、該手続きの実行を制御する手続き制御プログラムを生成する
    各段階を計算機に実行させるコードを含むことを特徴とする並列化プログラム生成プログラム。

Images