(57)【要約】  並列実行時間のより短い並列化プログラムを効率的に生成できるプログラム並列化方法および装置を提供する。  命令間の依存関係を参照して命令をスケジューリングする。ある関数ｆｐ／ｆ０内の命令とその子孫の関数ｆｑの命令との間の依存関係について解析し、その解析結果を用いて並列化を行う。先ずより深い方の関数ｆｑの命令を相対的にスケジューリングし、各命令が他の関数ｆｐの命令との間で依存関係を有するか否かを解析する。命令間の依存関係が存在すれば、その依存関係を維持し、且つ最も実行時間が短くなるように関数ｆｐの命令のスケジューリングを実行する。
2008090665.tif 000002
【特許請求の範囲】
【請求項１】
複数の命令を並列処理用にスケジューリングするプログラム並列化方法において、
少なくとも１つの命令を含む第１命令組と、少なくとも１つの命令を含む第２命令組との間の命令間依存関係を解析し、
前記命令間依存関係を参照して前記第１命令組および前記第２命令組の命令スケジューリングを実行する、
ことを特徴とするプログラム並列化方法。
【請求項２】
前記第２命令組の下位に前記第１命令組が関連付けられた場合、前記第１命令組の命令スケジューリングを実行した後、前記命令間依存関係を参照して前記第２命令組の命令スケジューリングを実行する、
ことを特徴とする請求項１に記載のプログラム並列化方法。
【請求項３】
前記第２命令組は、前記第１命令組を呼び出す呼出命令を含む、
ことを特徴とする請求項１または２に記載のプログラム並列化方法。
【請求項４】
前記命令間依存関係の情報を前記呼出命令に付加した後、前記第２命令組の命令スケジューリングを実行する、
ことを特徴とする請求項３に記載のプログラム並列化方法。
【請求項５】
前記第１命令組および前記第２命令組の各々は、少なくとも１つの命令を含む関数を少なくとも１つ含む強連結成分を構成する、
ことを特徴とする請求項１−４のいずれか１項に記載のプログラム並列化方法。
【請求項６】
ａ）１つの強連結成分に含まれる関数ごとに命令スケジューリングを実行し、
ｂ）前記関数ごとに他の関数との間の命令依存関係を解析し、
ｃ）各強連結成分に関して、当該強連結成分の形態に応じて設定された所定回数だけ、前記ａ）およびｂ）を繰り返す、
ことを特徴とする請求項５に記載のプログラム並列化方法。
【請求項７】
前記強連結成分の形態は、当該強連結成分を構成する関数同士の間で相互に呼び出しを行っている場合、当該強連結成分を構成する関数が１つで当該関数が自己再帰呼び出しを行っている場合、および、当該強連結成分がループを表している場合を含む、
ことを特徴とする請求項６に記載のプログラム並列化方法。
【請求項８】
前記ｂ）は、前記強連結成分の形態に応じて設定された所定回数だけ繰り返す、
ことを特徴とする請求項６に記載のプログラム並列化方法。
【請求項９】
前記強連結成分の形態は、当該強連結成分を構成する関数同士の間で相互に呼び出しを行っている場合、当該強連結成分を構成する関数が１つで当該関数が自己再帰呼び出しを行っている場合、および、当該強連結成分がループを表している場合を含む、
ことを特徴とする請求項８に記載のプログラム並列化方法。
【請求項１０】
前記強連結成分の形態がループを表している場合であって、そのループの繰り返し回数が決定されている場合は、当該ループの繰り返し回数だけ前記ｂ）を繰り返す、
ことを特徴とする請求項９に記載のプログラム並列化方法。
【請求項１１】
前記命令間依存関係を維持し、かつ、実行時間が最も短くなるように、前記第１命令組および前記第２命令組の命令スケジューリングを実行する、
ことを特徴とする請求項１−８のいずれか１項に記載のプログラム並列化方法。
【請求項１２】
複数の命令を並列処理用にスケジューリングするプログラム並列化装置において、
少なくとも１つの命令を含む第１命令組と、少なくとも１つの命令を含む第２命令組との間の命令間依存関係を解析する命令間依存解析手段と、
前記命令間依存関係を参照して前記第１命令組および前記第２命令組の命令スケジューリングを実行するスケジュール手段と、を有する、
ことを特徴とするプログラム並列化装置。
【請求項１３】
入力した逐次処理プログラムの制御フローを解析する制御フロー解析手段と、
前記制御フローの解析結果を参照して、スケジュール対象となる領域を決定するスケジュール領域形成手段と、
前記スケジュール領域を参照して、レジスタのデータフローを解析するレジスタデータフロー解析手段と、
あるアドレスに読み書きを行う命令と前記アドレスから読み書きを行う命令との間の依存を解析する命令間メモリデータフロー解析手段と、
を更に有し、
前記命令間依存解析手段は、前記レジスタデータフローと前記命令間メモリデータフローとを参照して、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存関係を解析し、
前記スケジュール手段は、命令間依存関係を参照して、命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻および実行プロセッサを実現する位置にフォーク命令を挿入する、
ことを特徴とする請求項１２に記載のプログラム並列化装置。
【請求項１４】
前記スケジュール手段の結果を参照して、レジスタ割り当てを行うレジスタ割り当て手段と
前記レジスタ割り当ての結果を参照して、実行可能な並列化プログラムを生成するプログラム出力手段と、を更に有する、
ことを特徴とする請求項１３に記載のプログラム並列化装置。
【請求項１５】
前記命令間依存解析手段は、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数の開始時刻および実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値およびプロセッサの相対値を解析する、
ことを特徴とする請求項１２または１３に記載のプログラム並列化装置。
【請求項１６】
前記命令間依存解析手段は、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数を呼び出す命令の実行時刻および実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値およびプロセッサの相対値を解析する、
ことを特徴とする請求項１２または１３に記載のプログラム並列化装置。
【請求項１７】
逐次処理中間プログラムを入力し、マルチスレッド型並列プロセッサ向けの並列化中間プログラムを出力するプログラム並列化方法において、
ａ）レジスタのデータフローの解析結果の情報と、あるメモリアドレスに関する命令の間の依存の解析結果の情報とを参照して、関数呼び出しの命令と、関数呼び出しグラフにおける呼び出された関数とその子孫の関数群の命令との間の依存関係の解析を行い、
ｂ）前記命令間依存関係を参照しながら各命令の実行時刻および実行プロセッサを決定し、
ｃ）決定された命令の実行時刻および実行プロセッサを実現する位置にフォーク命令を挿入して並列化中間プログラムを出力する、
ことを特徴とするプログラム並列化方法。
【請求項１８】
前記レジスタのデータフローの解析結果の情報は、前記入力した逐次処理プログラムの制御フローの解析を行い、制御フローの解析結果を参照してスケジュール対象の領域を決定し、制御フローの解析結果および前記スケジュール対象の領域を参照してレジスタのデータフローの解析を行う、ことにより生成され、
前記メモリアドレスに関する命令の間の依存の解析結果の情報は、前記制御フローの解析結果を参照して、あるメモリアドレスに読み書きを行う命令と前記アドレスから読み書きを行う命令との間の依存の解析を行う、ことにより生成される、
ことを特徴とする請求項１７に記載のプログラム並列化方法。
【請求項１９】
さらに、
ｄ）決定された命令の実行順序および実行プロセッサを参照して、レジスタ割り当てを行い、
ｅ）レジスタ割り当ての結果を参照して、並列化プログラムを出力する、
ことを特徴とする請求項１８に記載のプログラム並列化方法。
【請求項２０】
前記ステップａ）は、
ａ−１）順序に従って、関数呼び出しグラフの強連結成分のうち未選択のものを強連結成分 s とするステップと、
ａ−２）順序に従って、強連結成分 s を構成する関数のうち未選択の関数を関数fとするステップと、
ａ−３）関数ｆの命令スケジュールを行うステップと、
ａ−４）全ての関数をスケジュールしたか判断し、スケジュールされていない関数があれば繰り返し実行するステップと、
ａ−５）強連結成分ｓのソースに関する関数内外依存解析を行うステップと、
ａ−６）強連結成分ｓのデスティネーションに関する関数内外依存解析を行うステップと、
ａ−７）指定回数繰り返したか判断し、指定回数に満たない場合は繰り返し実行するステップと、
ａ−８）強連結成分ｓを構成する全関数を未選択にするステップと、
ａ−９）全ての強連結成分を調べたか判断し、調べていない強連結成分があれば繰り返し実行するステップと、を含む、
ことを特徴とする請求項１７記載のプログラム並列化方法。
【請求項２１】
前記ステップａ−５）は、
ａ−５−１）順序に従って、強連結成分を構成する関数のうち未選択の関数を関数fとするステップと、
ａ−５−２）関数ｆのソースに関する関数内外依存解析を行うステップと、
ａ−５−３）全ての関数を調べたか判断し、調べていない関数があれば繰り返し実行するステップと、
ａ−５−４）指定回数繰り返したか判断し、指定回数に満たない場合は繰り返し実行するステップと、
ａ−５−５）強連結成分を構成する全関数を未選択にするステップと、を含む、
ことを特徴とする請求項２０に記載のプログラム並列化方法。
【請求項２２】
前記ステップａ−５−２）は、
ａ−５−２−１）処理対象の関数の命令のうち未選択の命令はあるか判断し、未選択の命令があれば繰り返し実行するステップと、
ａ−５−２−２）順序に従って、該当命令のうち未選択のものを命令iとするステップと、
ａ−５−２−３）命令 i がソースとなっている依存の有向辺のうち未選択のものがあれば繰り返し実行するステップと、
ａ−５−２−４）順序に従って、該当有向辺のうち未選択のものを有向辺 e とするステップと、
ａ−５−２−５）有向辺 e を複製、ソースを関数を表すノードにするステップと、
ａ−５−２−６）有向辺に付加されていたソースに関する相対値に、関数の開始時点を基準とした、命令 i の実行時刻および実行プロセッサ番号の相対値を加算するステップと、
ａ−５−２−７）関数を呼び出す関数呼び出しの命令のうち未選択のものがあれば繰り返し実行するステップと、
ａ−５−２−８）順序に従って、該当命令のうち未選択のものを関数呼び出しの命令c するステップと、
ａ−５−２−９）複製してできた有向辺のうち未選択のものはあれば繰り返し実行するステップと、
ａ−５−２−１０）順序に従って、該当有向辺のうち未選択のものを有向辺 e とするステップと、
ａ−５−２−１１）有向辺 e を複製、複製してできた有向辺のソースを命令 c にした有向辺を作成するステップと、
ａ−５−２−１２）有向辺に付加されていたソースに関する相対値に、関数呼び出しの命令の実行時点を基準とした、関数の開始時刻および実行プロセッサ番号の相対値を加算するステップと、を含む、
ことを特徴とする請求項２１に記載のプログラム並列化方法。
【請求項２３】
前記ステップａ−６）は、
ａ−６−１）順序に従って、強連結成分を構成する関数のうち未選択の関数を関数fとするステップと、
ａ−６−２）関数ごとのデスティネーションに関する関数内外依存解析を行うステップと、
ａ−６−３）全ての関数を調べたか判断し、調べていない関数があれば繰り返し実行するステップと、
ａ−６−４）指定回数繰り返したか判断し、指定回数に満たない場合は繰り返し実行するステップと、
ａ−６−５）強連結成分を構成する全関数を未選択にするステップと、を含む、
ことを特徴とする請求項２０に記載のプログラム並列化方法。
【請求項２４】
前記ステップａ−６−２）は、
ａ−６−２−１）処理対象の関数の命令のうち未選択の命令はあるか判断し、未選択の命令があれば繰り返し実行するステップと、
ａ−６−２−２）順序に従って、該当命令のうち未選択のものを命令iとするステップと、
ａ−６−２−３）命令 i がデスティネーションとなっている依存の有向辺のうち未選択のものがあれば繰り返し実行するステップと、
ａ−６−２−４）順序に従って、該当有向辺のうち未選択のものを有向辺 e とするステップと、
ａ−６−２−５）有向辺 e を複製し、デスティネーションを関数を表すノードにするステップと、
ａ−６−２−６）有向辺に付加されていたデスティネーションに関する相対値に、関数の開始時点を基準とした、命令 i の実行時刻および実行プロセッサ番号の相対値を加算するステップと、
ａ−６−２−７）関数を呼び出す関数呼び出しの命令のうち未選択のものがあれば繰り返し実行するステップと、
ａ−６−２−８）順序に従って、該当命令のうち未選択のものを関数呼び出しの命令c とするステップと、
ａ−６−２−９）複製してできた有向辺のうち未選択のものがあれば繰り返し実行するステップと、
ａ−６−２−１０）順序に従って、該当有向辺のうち未選択のものを有向辺 e とするステップと、
ａ−６−２−１１）有向辺e を複製し、複製してできた有向辺のデスティネーションを命令 c にするステップと、
ａ−６−２−１２）有向辺に付加されていたデスティネーションに関する相対値に、関数呼び出しの命令の実行時点を基準とした、関数の開始時刻および実行プロセッサ番号の相対値を加算するステップと、を含む、
ことを特徴とする請求項２３に記載のプログラム並列化方法。
【請求項２５】
前記ステップａ）において、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数の開始時刻および実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値およびプロセッサの相対値を解析する、
ことを特徴とする請求項１７−２４のいずれか１項に記載のプログラム並列化方法。
【請求項２６】
前記ステップａ）において、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数を呼び出す命令の実行時刻と実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値とプロセッサの相対値を解析する、
ことを特徴とする請求項１７−２４のいずれか１項に記載のプログラム並列化方法。
【請求項２７】
複数の命令を並列処理用にスケジューリングするプログラム並列化装置を構成するコンピュータを、
少なくとも１つの命令を含む第１命令組と、少なくとも１つの命令を含む第２命令組との間の命令間依存関係を解析する命令間依存解析手段、および
前記命令間依存関係を参照して前記第１命令組および前記第２命令組の命令スケジューリングを実行するスケジュール手段、
として機能させる、
ことを特徴とするプログラム。
【請求項２８】
前記コンピュータを、
入力した逐次処理プログラムの制御フローを解析する制御フロー解析手段、
前記制御フローの解析結果を参照して、スケジュール対象となる領域を決定するスケジュール領域形成手段、
前記スケジュール領域を参照して、レジスタのデータフローを解析するレジスタデータフロー解析手段、および
あるアドレスに読み書きを行う命令と前記アドレスから読み書きを行う命令との間の依存を解析する命令間メモリデータフロー解析手段、
として更に機能させ、
前記命令間依存解析手段は、前記レジスタデータフローと前記命令間メモリデータフローとを参照して、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存関係を解析し、
前記スケジュール手段は、命令間依存関係を参照して、命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻および実行プロセッサを実現する位置にフォーク命令を挿入する、
ことを特徴とする請求項２７に記載のプログラム。
【請求項２９】
前記コンピュータを、
前記スケジュール手段の結果を参照して、レジスタ割り当てを行うレジスタ割り当て手段、および    
前記レジスタ割り当ての結果を参照して、実行可能な並列化プログラムを生成するプログラム出力手段、
として更に機能させる、
ことを特徴とする請求項２８に記載のプログラム。
【請求項３０】
前記命令間依存解析手段は、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数の開始時刻および実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値およびプロセッサの相対値を解析する、
ことを特徴とする請求項２７または２８に記載のプログラム。
【請求項３１】
前記命令間依存解析手段は、ある命令について、該命令が属する関数または関数呼び出しグラフ上での祖先の関数を呼び出す命令の実行時刻および実行プロセッサを基準とした、該命令がデータを定義または参照する時刻の相対値およびプロセッサの相対値を解析する、
ことを特徴とする請求項２７または２８に記載のプログラム。
【請求項３２】
逐次処理中間プログラムを入力し、マルチスレッド型並列プロセッサ向けの並列化中間プログラムを出力するプログラム並列化装置を構成するコンピュータを、
命令間の依存の解析結果と、命令間の依存の解析結果を参照して、ある関数内の命令と、関数呼び出しグラフにおける前記関数の子孫の関数群の命令との間の依存を解析する関数内外依存解析手段、および
前記関数内外依存解析手段の解析結果を参照して、命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻および実行プロセッサを実現する位置にフォーク命令を挿入し並列化中間プログラムを出力する命令スケジュール手段、
として機能させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は逐次処理プログラムを並列プロセッサシステムで並列に処理する技術に係り、特に逐次処理プログラムから並列化プログラムを生成する方法および装置に関する。
【背景技術】
【０００２】
単一の逐次処理プログラムを並列プロセッサシステムで並列に処理する手法としてマルチスレッド実行方法が知られている（例えば、特許文献１〜５、非特許文献１〜２参照）。マルチスレッド実行方法は、逐次処理プログラムをスレッドと呼ぶ命令流に分割して複数のプロセッサで並列に実行する手法であり、マルチスレッド実行を行う並列プロセッサをマルチスレッド型並列プロセッサと呼ぶ。以下、マルチスレッド実行方法についての一般的な説明に続いて、関連するプログラム並列化手法について説明する。【０００３】
１．マルチスレッド実行方法
一般に、マルチスレッド型並列プロセッサでのマルチスレッド実行方法において、他のプロセッサ上に新たなスレッドを生成することをスレッドを「フォーク（ｆｏｒｋ）する」と言い、フォーク動作を行った側のスレッドを「親スレッド」、生成された新しいスレッドを「子スレッド」、スレッドをフォークするプログラム位置を「フォーク元アドレス」または「フォーク元ポイント」、子スレッドの先頭のプログラム位置を「フォーク先アドレス」または「フォーク先ポイント」あるいは「子スレッドの開始点」と呼ぶ。【０００４】
特許文献１〜４および非特許文献１〜２では、スレッドのフォークを指示するためにフォーク元ポイントにフォーク命令が挿入される。フォーク命令にはフォーク先アドレスが指定され、フォーク命令の実行によりそのフォーク先アドレスから始まる子スレッドが他プロセッサ上に生成され、子スレッドの実行が開始される。また、スレッドの処理を終了させるプログラム位置をターム（ｔｅｒｍ）点と呼び、ターム点で各プロセッサはスレッドの処理を終了する。【０００５】
図１Ａ〜Ｄはマルチスレッド型並列プロセッサにおけるマルチスレッド実行方法の処理の概要を説明するための模式図である。図１Ａは３つのスレッドＡ、Ｂ、Ｃに分割された単一の逐次処理プログラムを示す。このプログラムを単一のプロセッサで処理する場合には、図１Ｂに示すように１つのプロセッサＰＥがスレッドＡ、Ｂ、Ｃを順番に処理していく。【０００６】
１．１）フォーク１回モデル
これに対して、マルチスレッド型並列プロセッサにおけるマルチスレッド実行方法では、図１Ｃに示すように、１つのプロセッサＰＥ１にスレッドＡを実行させ、プロセッサＰＥ１でスレッドＡを実行している最中に、スレッドＡに埋め込まれたフォーク命令によってスレッドＢを他のプロセッサＰＥ２に生成し、プロセッサＰＥ２においてスレッドＢを実行させる。また、プロセッサＰＥ２は、スレッドＢに埋め込まれたフォーク命令によってスレッドＣをプロセッサＰＥ３に生成する。プロセッサＰＥ１は、実行可能ファイル上で、スレッドＡとスレッドＢの境目に相当する場所に位置するターム点に到達するとスレッドの処理を終了する。同様にプロセッサＰＥ２は、スレッドＢとスレッドＣの境目に相当するプログラム位置にあるターム点に到達するとスレッドの処理を終了する。プロセッサＰＥ３は、スレッドＣの最後の命令を実行すると、その次の命令（一般にはシステムコール命令）を実行する。このように、複数のプロセッサでスレッドを同時に並行して実行することにより、逐次処理に比べて性能の向上が図られる。【０００７】
図１Ｃのように、スレッドはその生存中に高々１回に限って有効な子スレッドを生成することができるという制約を課したマルチスレッド実行方法をフォーク１回モデルと呼ぶ。フォーク１回モデルでは、スレッド管理の大幅な簡略化が可能となり、現実的なハードウェア規模でスレッド管理部のハードウェア化が実現できる。また、個々のプロセッサは子スレッドを生成する他プロセッサが１プロセッサに限定されるため、隣接するプロセッサを単方向にリング状に接続した並列プロセッサシステムでマルチスレッド実行が可能となる。【０００８】
他のマルチスレッド実行方法として、図１Ｄに示すように、スレッドＡを実行しているプロセッサＰＥ１からフォークを複数回行うことにより、プロセッサＰＥ２にスレッドＢを、またプロセッサＰＥ３にスレッドＣをそれぞれ生成するマルチスレッド実行方法も存在する。【０００９】
なお、フォーク命令時、子スレッドを生成できる空きのプロセッサが存在しない場合には、親スレッドを実行しているプロセッサにおいて、子スレッドを生成できる空きのプロセッサが生じるまでフォーク命令の実行を待機する方法が典型的である。その他の方法としては、特許文献４に示されるように、フォーク命令を無効化してフォーク命令以降の後続命令を引き続き実行した後、子スレッドの命令群を自ら実行する方法もある。【００１０】
スレッドはその生存中に高々１回に限って有効な子スレッドを生成するというフォーク１回モデルのマルチスレッド実行を実現するために、例えば非特許文献１等では、逐次処理プログラムから並列化プログラムを生成するコンパイルの段階で、全てのスレッドが有効なフォークを１回しか実行しない命令コードになるように制限している。即ち、フォーク１回制限を並列化プログラム上において静的に保証している。一方、特許文献３では、親スレッド中に存在する複数のフォーク命令のうちから有効な子スレッドを生成する１つのフォーク命令を親スレッドの実行中に選択することにより、フォーク１回制限をプログラム実行時に保証している。【００１１】
１．２）レジスタ値継承
親スレッドが子スレッドを生成し、子スレッドに所定の処理を行わせるためには、レジスタ値の継承が必要である。すなわち、親スレッドのフォーク点におけるレジスタファイル中のレジスタのうち少なくとも子スレッドで必要なレジスタの値を親スレッドから子スレッドに引き渡す必要がある。このスレッド間のデータ引き渡しコストを削減するために、特許文献２や非特許文献１では、スレッド生成時のレジスタ値継承機構をハードウェア的に備えている。これは、スレッド生成時に親スレッドのレジスタファイルの内容を子スレッドに全てコピーするものである。子スレッド生成後は、親スレッドと子スレッドのレジスタ値の変更は独立となり、レジスタを用いたスレッド間のデータの引き渡しは行われない。【００１２】
スレッド間のデータ引き渡しに関する他の技術としては、非特許文献２に記載されているように、レジスタ値継承機構をハードウェア的に備え、子スレッド生成時と子スレッド生成後、必要なレジスタ値をスレッド間で転送する方法もある。あるいは、レジスタの値を命令によりレジスタ単位で個別に転送する機構を備えた並列プロセッサシステムも提案されている。【００１３】
１．３）スレッド投機実行
マルチスレッド実行方法では、実行の確定した先行スレッドを並列に実行することを基本とするが、実際のプログラムでは実行の確定するスレッドが充分に得られない場合も多い。また、動的に決定される依存やコンパイラ解析能力の限界等により並列化率が低く抑えられ、所望の性能が得られない可能性が生じる。このため、特許文献１では、制御投機を導入し、ハードウェア的にスレッドの投機実行をサポートしている。制御投機では、実行する可能性の高いスレッドを実行確定前に投機的に実行する。投機状態のスレッドは、実行の取り消しがハードウェア上可能である範囲内で仮実行を行う。子スレッドが仮実行を行っている状態を仮実行状態と言い、子スレッドが仮実行状態にあるとき親スレッドはスレッド仮生成状態にあると言う。仮実行状態の子スレッドでは共有メモリおよびキャッシュメモリへの書き込みは抑制され、別途設けた仮実行用バッファ（ｔｅｍｐｏｒａｒｙ ｂｕｆｆｅｒ）に対して書き込みが行われる。【００１４】
投機が正しいことが確定すると、親スレッドから子スレッドに対して投機成功通知が出され、子スレッドは仮実行用バッファの内容を共有メモリおよびキャッシュメモリに反映し、仮実行用バッファを用いない通常の状態となり、親スレッドはスレッド仮生成状態からスレッド生成状態となる。【００１５】
他方、投機が失敗したことが確定すると、親スレッドでスレッド破棄命令（ａｂｏｒｔ）が実行され、子スレッド以下の実行がキャンセルされる。また、親スレッドは、スレッド仮生成状態からスレッド未生成状態となり、再び子スレッドの生成が可能になる。つまり、フォーク１回モデルでは、スレッド生成は高々１回に限定されるが、投機的にフォークを行い、投機が失敗した場合には再びフォークが可能となる。この場合においても、有効な子スレッドは高々１つである。【００１６】
２．プログラム並列化
次に、上記マルチスレッド実行を行う並列プロセッサ向けの並列プログラムを生成する技術について説明する。【００１７】
図２Ａは関連するプログラム並列化装置の一例を示すブロック図である。このプログラム並列化装置１０は、たとえば特許文献７および８に記載された機能的構成によれば、制御・データフロー解析部１１および並列化部分決定部１２を有する。まず、制御・データフロー解析部１１によって、高級言語で記述された逐次処理プログラム１３の制御フローおよびデータフローが解析される。このデータフローの解析では、ある関数内の命令（Ｉ１とする）と当該関数が呼び出す別の関数内の命令（Ｉ２とする）との間に依存関係があると判断されると、命令Ｉ１を実行した後で関数呼出命令Ｃを実行するようにスケジューリングされる（たとえば特許文献８の段落００４７参照）。言い換えれば、命令Ｉ１と命令Ｉ２との間の依存関係は、命令Ｉ１と関数呼出命令Ｃとの間の依存関係に置き換えるという近似が用いられる（具体例は図３で説明する。）。そして、制御フローおよびデータフローの解析結果を参照しながら、並列化部分決定部１２は、基本ブロックあるいは複数の基本ブロックを並列化の単位とし、各並列化単位をどのプロセッサで実行させるかを決定し、複数のスレッドに分割された並列化プログラム１４を生成する。【００１８】
図２Ｂは関連するプログラム並列化装置の他の例を示すブロック図である。このプログラム並列化装置２０は、たとえば特許文献６に記載された機能的構成によれば、命令入れ替え処理・命令入れ替え選択部２１、フォーク箇所決定部２２およびフォーク挿入部２３を有する。まず、命令列の入れ替えのステップでは、逐次処理プログラム２４の一部の命令列を他の命令列に変換した複数の逐次処理プログラムを作成し、それらと逐次処理プログラム２４とを比較することで、並列実行性能が改善された逐次処理プログラムを選択する（たとえば特許文献６の段落０１００参照）。【００１９】
続いて、フォーク箇所決定ステップでは、選択された逐次処理プログラムに対して、反復改善法を用いて並列実行性能が最も良くなるフォーク箇所の組み合わせを決定する（たとえば特許文献６の段落０１５４参照）。この際に、上述した命令間の依存関係は、命令列の入れ替えは行わずフォーク箇所の組み合わせのみを変更して維持される。これは見方を変えると、依存関係を複数の命令をまとめた単位で維持しようとするものである。この複数の命令をまとめた単位は、逐次処理プログラムを入力データで逐次実行したときの逐次実行トレースをすべてのターム点候補を分割点として分割した要素に相当する。最後に、フォーク挿入ステップでは、並列化のためのフォーク命令を挿入し複数のスレッドに分割された並列化プログラム２５を生成する。
【特許文献１】特開平１０−２７１０８号公報
【特許文献２】特開平１０−７８８８０号公報
【特許文献３】特開２００３−０２９９８５号公報
【特許文献４】特開２００３−０２９９８４号公報
【特許文献５】特開２００１−２８２５４９号公報
【特許文献６】特開２００６−０１８４４５号公報
【特許文献７】特許第２７４９０３９号公報
【特許文献８】特開平５−１４３３５７号公報
【非特許文献１】「Ｏｎ  Ｃｈｉｐ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ指向  制御並列アーキテクチャＭＵＳＣＡＴの提案」（並列処理シンポジュウムＪＳＰＰ９７論文集、情報処理学会、ｐｐ．２２９−２３６、Ｍａｙ  １９９７）
【非特許文献２】Ｔａｋｕ Ｏｈｓａｗａ， Ｍａｓａｍｉｃｈｉ Ｔａｋａｇｉ， Ｓｈｏｊｉ Ｋａｗａｈａｒａ， Ｓａｔｏｓｈｉ Ｍａｔｓｕｓｈｉｔａ： Ｐｉｎｏｔ： Ｓｐｅｃｕｌａｔｉｖｅ Ｍｕｌｔｉ−ｔｈｒｅａｄｉｎｇ Ｐｒｏｃｅｓｓｏｒ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｅｘｐｌｏｉｔｉｎｇ Ｐａｒａｌｌｅｌｉｓｍ Ｏｖｅｒ ａ Ｗｉｄｅ Ｒａｎｇｅ ｏｆ Ｇｒａｎｕｌａｒｉｔｉｅｓ． Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ３８ｔｈ ＭＩＣＲＯ， ｐａｇｅｓ ８１―９２， ２００５．
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、上記関連するプログラム並列化装置では、並列実行時間を期待通りに短縮できない場合がある上に、並列化プログラムを決定するために要する時間も長くなるという問題があった。以下詳述する。【００２１】
（１）図２Ａに示すプログラム並列化装置によれば、上述した命令Ｉ１とＩ２との間の依存関係を用いることなく、この命令間依存関係を命令Ｉ１と関数呼出命令Ｃとの依存関係で近似する。このように命令間依存関係を考慮しないので、関数呼出命令Ｃがあると、依存関係を安全に維持するように命令Ｉ１の後に関数呼出命令Ｃを配置するようにスケジューリングされる。このために並列実行時間が不必要に長くなるスケジュールが決定されうる。この点を図３および図４を用いて具体的に説明する。【００２２】
図３は逐次処理プログラムを解析することで得られた中間プログラムの内部表現を示す図である。ここでは、説明を簡略化するために、入力プログラムは関数ｆ１および関数ｆ２から構成され、関数ｆ１は命令Ｌ１〜Ｌ３、関数ｆ２は命令Ｌ４〜Ｌ６からそれぞれ構成されるものとし、さらに関数ｆ１は関数呼出命令Ｌ３によって関数ｆ２を呼び出すものとする(L3: call f2)。実行は、関数ｆ１から開始されるものとする。【００２３】
図３において、関数ｆ１、ｆ２は関数を表すノードで表現され、関数ｆ１は基本ブロックＢ１およびＢ２から構成され、基本ブロックＢ１は命令Ｌ１およびＬ２から、基本ブロックＢ２は呼出命令Ｌ３からそれぞれ構成されるとする。また、関数ｆ２は基本ブロックＢ３から構成され、基本ブロックＢ３は命令Ｌ３、Ｌ４およびＬ５から構成されるものとする。【００２４】
基本ブロックＢ１を実行した後、制御は基本ブロックＢ２に移り、基本ブロックＢ２で関数呼出し命令Ｌ３を実行した後、制御は基本ブロックＢ３に移る。この制御フローを実線の矢印で表す。また、このプログラムでは、命令Ｌ１が定義したデータ（ｒ３）を命令Ｌ２が参照するというデータフローによる依存があり、命令Ｌ２が定義したデータ（アドレスｒ２に格納されたメモリデータ）を命令Ｌ５が参照するというデータフローによる依存がある。ある命令Ｘからある命令Ｙへデータフローによる依存がある場合は、命令Ｘの実行時刻に実行遅延時間を加えた時刻か、それより後に命令Ｙを実行せねばならないとし、全ての命令の実行遅延時間は１サイクルとする。【００２５】
図４Ａおよび図４Ｂは関連するプログラム並列化装置により得られた命令スケジュール結果の一例を示す命令割り当て図である。命令間依存を解析せずに命令の実行サイクルおよび実行プロセッサを決定しようとする場合、データフローの条件が満たされるように安全策をとって、命令Ｌ２から命令Ｌ３に依存があるとしてスケジュールを行う。この安全な近似を用いて命令スケジュールを行った結果、図４Ａに示すように、たとえプロセッサが複数あっても、命令Ｌ１から命令Ｌ２への依存、命令Ｌ２から命令Ｌ３への依存を厳守するために、結局、命令Ｌ１〜Ｌ３は一つのプロセッサ上に配置されることとなる。したがって、実行時には図４Ｂに示すように６サイクルの時間が必要となる。しかしながら、この例では、命令Ｌ２から命令Ｌ５への依存は維持される必要があるが、命令Ｌ２から命令Ｌ３への依存を維持する必要はない。従来技術では、安全な近似により依存関係を維持しているために、結果的に不必要に長い並列実行時間が生じる可能性が高くなっている。【００２６】
同様のことが図２Ｂに示すプログラム並列化装置でも言える。このプログラム並列化によれば、並列実行性能が改善されるように命令列を入れ替え、並列実行時間が最も短くなるように逐次処理プログラムを選択し、選択された逐次処理プログラムに対して反復改善法により最適なフォーク箇所の組み合わせを決定する。この場合、命令列の入れ替えのステップではフォーク箇所の候補数が増大するように命令列を入れ替えるが、フォーク箇所組み合わせ探索ステップでは命令列の入れ替えを行わずに、フォーク箇所のみを変更して最適なフォーク箇所集合を決定する。したがって、命令間の依存関係は、複数の命令をまとめた単位で維持することとなる。すなわち、フォーク箇所組み合わせ探索ステップでは、複数命令を単位として命令間依存関係が解析され、上述した近似による依存関係の維持と同様に、結果的に不必要に長い並列実行時間が生じる可能性が高くなっている。【００２７】
要するに、関連するプログラム並列化装置では、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令について部分的な解析しか行わないために、並列実行時間が不必要に長くなるスケジュールが決定される場合がある。【００２８】
（２）関連するプログラム並列化装置の第２の問題点は、並列実行時間のより短い並列化プログラムを得ようとするにつれて、その決定処理にますます時間がかかることである。たとえば図２Ｂに示すプログラム並列化装置においては、その理由は２つある。第１に、フォーク箇所の可能な組み合わせの数は非常に多いために、その中からより短い並列実行時間のフォーク箇所の組み合わせを決定するには多くの時間を要するからである。第２に、より短い並列実行時間のフォーク箇所の組み合わせを決定する際の反復改善法は、フォーク箇所の組み合わせを変更し、並列実行時間を計測するという２ステップを繰り返す必要があるからである。【００２９】
本発明は、このような事情に鑑みて提案されたものであり、その目的は、並列実行時間のより短い並列化プログラムを効率的に生成できるプログラム並列化方法および装置を提供することにある。
【課題を解決するための手段】
【００３０】
本発明によれば、命令間の依存関係を参照して命令をスケジューリングすることでプログラムの並列化を行う。すなわち、少なくとも１つの命令を含む第１命令組と少なくとも１つの命令を含む第２命令組との間の命令間依存関係を解析し、その命令間依存関係を参照することで第１命令組および第２命令組の命令スケジューリングを実行する。命令間依存関係を参照することで、実行時間がより短かいスケジュールを得ることができる。【００３１】
本発明の一実施形態によれば、前記第２命令組の下位に前記第１命令組が関連付けられた場合、第１命令組の命令スケジューリングを実行した後、命令間依存関係を参照して第２命令組の命令スケジューリングを実行する。たとえば、第２命令組が第１命令組を呼び出す呼出命令を含む場合である。【００３２】
第１命令組の命令スケジューリングを実行した後に第２命令組の命令スケジューリングを実行する場合、命令間依存関係の情報を第２命令組に含まれる呼出命令に付加した後、第２命令組の命令スケジューリングを実行することが望ましい。第２命令組をスケジューリングする際に、呼出命令に付加された命令間依存関係を参照することができるからである。【００３３】
本発明の他の側面によれば、第１命令組および第２命令組の各々は、少なくとも１つの命令を含む関数を少なくとも１つ含む強連結成分を構成する。特に関数同士が相互に依存する形態の強連結成分に対しては、複数回のスケジューリングおよび命令依存関係の解析を繰り返すことが望ましい。すなわち、ａ）１つの強連結成分に含まれる関数ごとに命令スケジューリングを実行し、ｂ）関数ごとに他の関数との間の命令依存関係を解析し、ｃ）各強連結成分に関して、当該強連結成分の形態に応じて設定された所定回数だけ、ａ）およびｂ）を繰り返す。【００３４】
本発明の一実施形態によれば、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存関係について命令の実行サイクルおよび実行プロセッサを解析し、その解析結果を用いて並列化を行う。これにより、ある関数内の命令と当該関数の子孫の関数群の命令とが依存関係を守りながら並列実行することが可能となり、並列実行時間のより短い並列化プログラムを生成することができる。
【発明の効果】
【００３５】
本発明によれば、命令間の依存関係を参照して命令をスケジューリングすることで実行時間がより短いスケジュールを得ることができる。たとえば、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存関係について解析し、その解析結果を用いて並列化を行うことにより、ある関数内の命令と、当該関数の子孫の関数群の命令とを並列に実行するよう指示することが可能になるからである。【００３６】
さらに、本発明によれば、並列化においてフォーク箇所の組み合わせを対象にした探索を行わない。上述したようにフォーク箇所の組み合わせは可能な候補数が非常に多いので、プログラム並列化の高速性を困難にしていたが、本発明ではこのようなフォーク箇所の組み合わせの探索を行わないので、並列実行時間のより短い並列化プログラムを高速に生成することができる。
【図面の簡単な説明】
【００３７】
【図１Ａ】マルチスレッド型並列プロセッサにおけるマルチスレッド実行方法の処理の概要を説明するための模式図である。
【図１Ｂ】マルチスレッド型並列プロセッサにおけるマルチスレッド実行方法の処理の概要を説明するための模式図である。
【図１Ｃ】マルチスレッド型並列プロセッサにおけるマルチスレッド実行方法の処理の概要を説明するための模式図である。
【図１Ｄ】マルチスレッド型並列プロセッサにおけるマルチスレッド実行方法の処理の概要を説明するための模式図である。
【図２Ａ】関連するプログラム並列化装置の一例を示すブロック図である。
【図２Ｂ】関連するプログラム並列化装置の他の例を示すブロック図である。
【図３】逐次処理プログラムを解析することで得られた中間プログラムの内部表現を示す図である。
【図４Ａ】関連するプログラム並列化装置により得られた命令スケジュール結果の一例を示す命令割り当て図である。
【図４Ｂ】関連するプログラム並列化装置により得られた命令スケジュール結果の一例を示す命令割り当て図である。
【図５Ａ】本発明の第１実施形態によるプログラム並列化方法を説明するための関数の一例を示した模式図である。
【図５Ｂ】図５Ａに示す例に適用した本実施形態によるプログラム並列化方法の手順を示すフローチャートである。
【図６】関数ｆ１およびｆ２をプログラム並列化装置で処理する際の内部表現で表した中間プログラムの構成図である。
【図７Ａ】本実施形態による並列化手順を説明するためのスケジュール空間の割り当て例を示す模式図である。
【図７Ｂ】本実施形態による並列化手順を説明するためのスケジュール空間の割り当て例を示す模式図である。
【図８】強連結成分について説明するための関数呼出グラフである。
【図９】強連結成分について説明するための入力プログラムの一例を示す図である。
【図１０】図９の入力プログラムに対応する逐次処理中間プログラムを示した図である。
【図１１】本発明の第１実施例によるプログラム並列化装置の構成を示す概略的ブロック図である。
【図１２】本実施例における処理装置の一例を示すブロック図である。
【図１３】命令間依存情報を生成する回路の一例を示すブロック図である。
【図１４】依存解析・命令スケジュール部１０２で処理される依存解析およびスケジュール処理の全体的動作を示すフローチャートである。
【図１５】ソースに関する関数内外依存解析処理の全体を示すフローチャートである。
【図１６】ソースに関する関数内外依存解析処理の詳細を示すフローチャートである。
【図１７】デスティネーションに関する関数内外依存解析処理の全体を示すフローチャートである。
【図１８】デスティネーションに関する関数内外依存解析処理の詳細を示すフローチャートである。
【図１９】逐次処理中間プログラムに変換される前の入力プログラムを示す図である。
【図２０Ａ】逐次処理中間プログラムを示した図である。
【図２０Ｂ】図２０Ａに示す逐次処理中間プログラムの関数呼出グラフを示す図である。
【図２１】関数ｆ１２の相対的スケジュールを示す図である。
【図２２】依存解析過程における有向辺に付加された相対値の操作を説明するための逐次処理中間プログラムを示した図である。
【図２３】命令Ｌ１３のスケジュール決定過程を示す図である。
【図２４】命令Ｌ１３のスケジュール結果を示す図である。
【図２５】従来技術によるスケジュールを比較例として示す図である。
【図２６】本発明の第２実施例によるプログラム並列化装置の構成を示す概略的ブロック図である。
【符号の説明】
【００３８】
１００，１００Ａ プログラム並列化装置
１０１，１０１Ａ 処理装置
１０２ 依存解析・スケジュール部
１０３ 関数内外依存解析部
１０４ 命令スケジュール部
３０１ 記憶装置
３０２ 逐次処理中間プログラム
３０３ 記憶装置
３０４ 命令間の依存情報
３０５ 記憶装置
３０６ 並列化中間プログラム
４０１ 記憶装置
４０２ 逐次処理プログラム
４０３ 記憶装置
４０４ プロファイルデータ
４０５ 記憶装置
４０６ 並列化プログラム
１０１．１ 制御フロー解析部
１０１．２ スケジュール領域形成部
１０１．３ レジスタデータフロー解析部
１０１．４ 命令間メモリデータフロー解析部
１０１．５ レジスタ割り当て部
１０１．６ プログラム出力部
【発明を実施するための最良の形態】
【００３９】
１．第１実施形態
以下、本発明の第１実施形態によるプログラム並列化方法について図５Ａ〜図７Ｂを参照しながら説明する。【００４０】
１．１）概略説明
本発明によれば、命令間の依存関係を参照しながらプログラムの並列化を行う。特に、本発明の第１実施形態によれば、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存関係に基づいて命令の実行サイクルおよび実行プロセッサを決定し並列化プログラムを生成する。【００４１】
図５Ａは、本発明の第１実施形態によるプログラム並列化方法を説明するための関数の一例を示した模式図であり、図５Ｂは図５Ａに示す例に適用した本実施形態によるプログラム並列化方法の概略的手順を示すフローチャートである。【００４２】
ただし、ここでは説明を簡略化するために次のように仮定する。関数ｆ０は他の関数から呼び出されていない関数であり、その子孫の関数群の末端の２つを関数ｆｐおよびｆｑとする。ここでは関数ｆｐの命令Lp_kが関数ｆｑの呼出命令である。また、一例として、関数ｆ０の命令L0_rの結果が関数ｆｑの命令Lq_iで参照され、関数ｆｑの命令Lq_jの結果が関数ｆｐの命令Lp_lで参照されるデータフローの依存関係があるものとする。すなわち、関数ｆｑの命令Lq_jがソース（始点の命令）となり関数ｆｐの命令Lp_lがデスティネーション（終点の命令）となる破線の矢印が命令Lq_jと命令Lp_lとの間の命令間依存関係を示し、関数ｆ０の命令L0_rがソースとなり関数ｆｑの命令Lq_iがデスティネーションとなる破線の矢印が命令L0_rと命令Lq_iとの間の命令間依存関係を示す。ただし、この命令間依存関係は説明のための一例であり、命令間依存関係は任意の関数間で存在しうる。またデータの参照による依存関係だけでなく、分岐命令等による依存関係も含まれる。【００４３】
図５Ｂに示すように、先ず図５Ａに示すような命令間依存関係が情報として与えられる（ステップＳ１）。続いて、関数ｆｐの命令Lp_kが関数ｆｑを呼び出し、関数ｆｑは他の関数を呼び出さないので、関数ｆｑの命令の相対的なスケジューリングから開始する（ステップＳ２）。ある関数の依存の解析を行う際には、その関数が呼び出す子孫の関数の情報を必要とするため、関数の呼び出しが深いものから順に解析を行う必要があるからである。【００４４】
ここで、命令のスケジューリングとは、当該命令をどのサイクル（実行時刻）でどのプロセッサにより実行させるか、言い換えれば、当該命令をサイクル番号およびプロセッサ番号からなるスケジュール空間のどの位置に割り当てるかを決定することをいう。また「スケジュール空間」とは実行時刻を示すサイクル番号と複数のプロセッサ番号とを座標軸とする空間をいう。ただし、プロセッサ数には上限があるので、スケジュール空間のプロセッサ番号に上限を設けるか、スケジュール空間のプロセッサ番号に上限を設けずに、スケジュール空間のプロセッサ番号を実際のプロセッサ数で割った際の剰余を実行時のプロセッサ番号として用いる必要がある。【００４５】
また、「相対的スケジュール」とは、当該関数（ここでは関数ｆｑ）が実行を開始する実行サイクルおよびプロセッサ番号を基準として、その基準からの増分を示すスケジュールをいう。ステップＳ２における関数ｆｑの命令のスケジュールは現存する命令間の依存関係を参照して決定されるが、これらの命令Ｌｑはスケジュール空間における互いの相対的な位置関係が決定されるだけである。なぜならば、関数ｆｑは関数ｆｐの関数呼出命令Lp_kにより呼び出されるのであるから、命令Lp_kのスケジュールが決定されない限り、関数ｆｑの命令のスケジュールは絶対的に決定されないからである。なお、この例では、最終的な関数ｆ０のスケジュールが決定されない限り、その子孫の関数群の命令のスケジュールも決定されないことになる。【００４６】
続いて、命令Lq_jと命令Lp_lとの間の命令間依存関係が参照され、これらの命令間依存関係を遵守し、かつ、全体として最も短い命令実行時間となる、というスケジューリング条件を満たすように、関数ｆｐの命令の相対的なスケジュールが決定される（ステップＳ３）。その際、命令L0_rと命令Lq_iとの間の命令間依存関係は、関数ｆｐの関数呼出命令Lp_kに引き継がれ、関数ｆｐより祖先の関数のスケジューリングの際に、ステップＳ３の場合と同様に参照される。このように関数ｆ０へ向けてステップＳ２およびＳ３が再帰的に実行され、最終的に関数ｆ０の命令のスケジュールが決定され、全ての関数の命令のスケジュールが確定する。【００４７】
このように決定されたスケジュールは、命令間依存関係を遵守し、かつ、全体として最も短い命令実行時間となる、というスケジューリング条件を満たしている。このスケジューリング条件を一般化すれば、次のようになる：（ａ）関数ｆ内の命令と、関数呼び出しグラフにおける当該関数ｆの子孫の関数群の命令との間の依存関係を満たすこと；および（ｂ）関数ｆおよびその子孫の関数群内の命令の全体的な実行時間が最短になること。【００４８】
なお、本実施形態によるプログラム並列化方法は、プログラム制御プロセッサ上でプログラム並列化プログラムを実行することにより実現してもよいし、ハードウエア的に実現することもできる。【００４９】
また、図５Ａ、Ｂでは説明を簡単にするために、関数ｆ０の子孫の関数群として関数ｆｐおよびｆｑを図示したが、この関数呼出関係の上記スケジューリング過程は、任意の深さの関数呼出モデルに対して再帰的に適用されうる。【００５０】
１．２）具体例
次に、従来技術として説明した図３の入力プログラムに対して本実施形態を適用した場合を説明する。【００５１】
図６は関数ｆ１およびｆ２をプログラム並列化装置で処理する際の内部表現で表した中間プログラムの構成図である。関数ｆ１およびｆ２、基本ブロックＢ１〜Ｂ３は入力プログラムを解析することにより求められる。関数ｆ１および関数ｆ２は関数を表すノードで表現され、関数ｆ１は基本ブロックＢ１およびＢ２から構成され、関数と基本ブロックとの関係を点線の矢印で表す。基本ブロックＢ１は命令Ｌ１およびＬ２から構成され、基本ブロックと命令との関係を四角形で囲うことで表す。基本ブロックＢ２は命令Ｌ３から構成されるとする。関数ｆ２は基本ブロックＢ３から構成され、基本ブロックＢ３は命令Ｌ４、Ｌ５およびＬ６から構成されるとする。【００５２】
この場合の制御は、基本ブロックＢ１を実行した後に基本ブロックＢ２に移り、基本ブロックＢ２で関数呼出し命令Ｌ３を実行した後に基本ブロックＢ３に移るものとする。この制御フローを実線の矢印で表す。また、命令Ｌ１が定義したデータを命令Ｌ２が参照するというデータフローによる命令間依存、命令Ｌ２が定義したデータを命令Ｌ５が参照するというデータフローによる命令間依存があるので、これら命令間依存をそれぞれ破線の矢印で表す。ある命令Ｘからある命令Ｙへデータフローによる依存がある場合は、命令Ｘの実行時刻に実行遅延時間を加えた時刻か、それより後に命令Ｙを実行せねばならないとし、全ての命令の実行遅延時間は１サイクルとする。【００５３】
上述したように、関数ｆ２は既に相対的なスケジュールが完了し、その結果、命令Ｌ４、命令Ｌ５、命令Ｌ６の順で一つのプロセッサに配置されるものとする（サイクル番号およびプロセッサ番号は未決定である。）。【００５４】
本実施形態によれば、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存について、命令の実行サイクルおよび実行プロセッサに関する情報を解析できる。この解析により、１）命令Ｌ２から命令Ｌ５へ依存があること；２）命令Ｌ５は関数呼出し命令Ｌ３を経て実行されるため、命令Ｌ２と命令Ｌ３との実行時刻の関係が命令Ｌ２から命令Ｌ５への依存関係を満たすものであればよいこと；３）命令Ｌ３の実行の１サイクル後に関数ｆ２が実行を開始し、開始から１サイクル後、開始時と同じプロセッサ上で命令Ｌ５が実行されることが分かる。【００５５】
図７Ａおよび図７Ｂは、本実施形態による並列化手順を説明するためのスケジュール空間の割り当て例を示す模式図である。上記解析結果を用いて命令スケジュールを行うと、図７Ａに示すように、関数呼出命令Ｌ３をスケジュール空間の位置（２，０）あるいは位置（０，１）に配置することが可能である。なぜならば、関数ｆ２のスケジュールされた命令Ｌ４〜Ｌ６は関数呼出命令Ｌ３の１サイクル後に配置されるので、命令Ｌ５が命令Ｌ２の実行時刻に命令Ｌ２の遅延時間１サイクルを加えた時刻か、それより後の時刻に配置されるように、関数呼出命令Ｌ３を配置すればよいからである。【００５６】
さらに、上述したスケジューリング制約条件（ｂ）の最短実行時間の条件から、関数呼出命令Ｌ３は位置（０，１）に配置することが決定される。このように、本実施形態によれば、命令Ｌ３を命令Ｌ２より前のサイクルに配置することが可能になる。実行時には図７Ｂに示すように処理され、全体で４サイクルの実行時間で関数ｆ１およびｆ２の処理が完了する。従来では、図４Ｂに示すように６サイクルの時間が必要であったから、本発明によって有効な並列処理が可能になることが分かる。【００５７】
このように、本発明によれば、ある関数ｆ内の命令と、関数呼び出しグラフにおける当該関数ｆの子孫の関数群の命令との間の依存を考慮してスケジュールを行うので、命令をより適切な時刻（サイクル）とプロセッサに配置することが可能となり並列実行時間のより短い並列化プログラムを得ることができる。【００５８】
２．第２実施形態
上述したように、ある関数の依存の解析を行う際には、その関数から呼び出される関数の情報が必要とされるため、関数の呼び出しが深いものから解析を行うが、相互再帰呼び出しによって相互依存のある関数群は解析の順番が決定できない。そこで、このような相互依存のある関数群は、関数呼び出しグラフの「強連結成分」としてひとまとめにして解析する。【００５９】
本発明の第２実施形態によれば、相互依存のある関数群からなる強連結成分では、各関数における命令間依存関係の解析を指定回数実行することで命令スケジュールを決定するという方法を採用する。先ず、本実施形態における「強連結成分」について説明する。【００６０】
（強連結成分）
図８は強連結成分について説明するための関数呼出グラフである。それぞれの頂点ｆ２１、ｆ２２およびｆ２３が関数に対応し、有向辺が呼出関係に対応する。ここで関数ｆ２２と関数ｆ２３とが相互再帰呼び出しを行っているとする。この場合、関数ｆ２２からｆ２３への経路と関数ｆ２３からｆ２２への経路とが共に存在する。強連結成分は、このような関数ｆ２２およびｆ２３をひとまとめにする。このように相互依存のある関数群は強連結成分としてひとまとめにできる。【００６１】
強連結成分を求めるアルゴリズムは周知である。たとえば、まずグラフの頂点（ここでは関数に対応する。）に帰りがけ順の番号をつけ、次に、グラフの全ての有向辺を逆向きにしたグラフを作成し、逆向きにしたグラフ上で、先の番号が最大の頂点を出発点として、深さ優先探索を行い、辿られたもので木を作る。続いて、この探索で到達できない頂点について、先の番号が最大の頂点を出発点として、深さ優先探索を行い、辿られたもので木を作る、という作業を繰り返す。できた木一つ一つが強連結成分となる。その他のアルゴリムとしては、「データ構造とアルゴリズム」（Ａ．Ｖ．エイホ他著、大野義夫訳、培風館、１９８７）の第１９５項〜第１９８項に記載の方法を挙げることができる。次に、関数呼び出しグラフと強連結成分の具体例を示す。【００６２】
図９は強連結成分について説明するための入力プログラムの一例を示す図である。入力プログラムは関数ｆ２１、関数ｆ２２、関数ｆ２３から構成されており、実行は関数ｆ２１から開始するものとする。ここでは、関数ｆ２１が関数呼出命令Ｌ２３によって関数ｆ２２を呼び出し、関数ｆ２２が関数呼出命令Ｌ２５によって関数ｆ２３を呼び出し、また関数ｆ２３が関数呼出命令Ｌ２８によって関数ｆ２２を呼び出す。【００６３】
図１０は図９の入力プログラムに対応する逐次処理中間プログラムを示した図である。関数ｆ２１、関数ｆ２２、関数ｆ２３は関数を表すノードで表現される。関数ｆ２１は基本ブロックＢ２１およびＢ２２から構成され、その関係を点線の矢印で表す。基本ブロックＢ２１は命令Ｌ２１およびＬ２２から、基本ブロックＢ２２は命令Ｌ２３からそれぞれ構成され、基本ブロックと命令との関係を四角形で囲うことで表す。関数ｆ２２、関数ｆ２３も同様である。【００６４】
制御は、基本ブロックＢ２１を実行した後に基本ブロックＢ２２に移り、基本ブロックＢ２２で関数呼出命令を実行した後に基本ブロックＢ２３に移る。また、基本ブロックＢ２３の命令Ｌ２４は条件分岐命令で、条件に従って基本ブロックＢ２５あるいは基本ブロックＢ２６に制御が移る。さらに、基本ブロックＢ２４で関数呼出命令を実行した後に基本ブロックＢ２６に制御が移り、基本ブロックＢ２６を実行した後に基本ブロックＢ２７に制御が移る。さらに、基本ブロックＢ２７で関数呼出命令を実行した後は基本ブロックＢ２３に制御が移り、基本ブロックＢ２４を実行した後に基本ブロックＢ２５に制御が移る。これらの制御フローを実線の矢印で表す。【００６５】
このような関数呼出関係が図８に示されている。ただし、以下、強連結成分は複数の関数の相互依存だけでなく、単一の関数も強連結成分の１つとして取り扱うものとする。すなわち、図８に示すように、関数ｆ２１はそれ自身で関数呼出グラフの１つの強連結成分を構成し、関数ｆ２２と関数ｆ２３はもう１つの強連結成分を構成する。このように本発明の第２実施形態では強連結成分を単位としてプログラム並列化を実行する。以下、本発明の実施例を具体的に説明する。
【実施例１】
【００６６】
３．第１実施例
３．１）装置構成
図１１は本発明の第１実施例によるプログラム並列化装置の構成を示す概略的ブロック図である。本実施例によるプログラム並列化装置１００は、処理装置１０１にソフトウエアあるいはハードウエアにより依存解析・スケジュール部１０２を実現する。依存解析・スケジュール部１０２は、後述するように関数内外依存解析部１０３および命令スケジュール部１０４を有し、記憶装置３０１に格納された逐次処理中間プログラム３０２と記憶装置３０３に格納された命令間依存情報３０４とを入力し、並列化中間プログラム３０６を生成して記憶装置３０５に格納する。【００６７】
逐次処理中間プログラム３０２は、図示しないプログラム解析装置によって生成され、グラフの形で表現される。たとえば図３で示すような関数、基本ブロックおよびそれらの依存関係を記述したプログラムであり、逐次処理中間プログラム３０２を構成する関数および命令がそれぞれを表すノードとして表現される。また、ループは再帰関数に変換して、再帰関数として表現してもよい。また、逐次処理中間プログラム３０２においては、図３に示すように、命令スケジューリングの対象となるスケジュール領域が決定されている。スケジュール領域は、例えば、１つの基本ブロックとしてもよいし、複数の基本ブロックとしてもよい。【００６８】
命令間依存情報３０４は、命令間の依存関係およびそれに関連する情報であり、たとえば図６における破線の矢印で示すような命令間依存関係に関する情報である。命令間依存情報３０４は、レジスタ、メモリの読み書きに伴うデータフローの解析、制御フローの解析により得られる命令間の依存であり、命令を表すノードを結ぶ有向辺で表す（図５Ａ）。具体的には図２２を参照して後述するが、有向辺には、ソース（始点の命令）に関する実行時刻の相対値、実行プロセッサ番号の相対値およびソース命令の遅延時間を付加する。実行時刻の相対値および実行プロセッサ番号の相対値の初期値はいずれも０に設定されている。また、有向辺には、デスティネーション（終点の命令）に関する実行時刻の相対値、実行プロセッサ番号の相対値を付加する。初期値はいずれも０に設定されている。【００６９】
依存解析・スケジュール部１０２は、関数内外依存解析部１０３および命令スケジュール部１０４を有する。関数内外依存解析部１０３は命令間の依存情報３０４を参照して命令間の依存を解析する。すなわち、ある関数ｆ内の命令と、関数呼び出しグラフにおける当該関数ｆの子孫の関数群の命令との間の依存を解析する。この解析された依存関係に従って、命令スケジュール部１０４は命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻と実行プロセッサとを実現するように命令の実行順序を決定してフォーク命令を挿入する。こうして並列化中間プログラム３０６を記憶装置３０５に記録する。【００７０】
なお、処理装置１０１は中央処理装置ＣＰＵなどの情報処理装置であり、記憶装置３０１、３０３および３０５は磁気ディスク装置などの記憶装置である。このようなプログラム並列化装置１００は、パーソナルコンピュータやワークステーションなどのコンピュータとプログラムとで実現することができる。プログラムは、磁気ディスク等のコンピュータ可読記録媒体に記録され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に依存解析・スケジュール部１０２といった機能手段を実現する。たとえば、図１２に示すように構成されうる。【００７１】
図１２は本実施例における処理装置の一例を示すブロック図である。ここでは、プログラム制御プロセッサからなる制御部２０１がメモリから依存解析・スケジュール制御プログラム２０２を読み出して実行する。制御部２０１は、強連結成分抽出部２０３、スケジューリング・依存解析回数管理部２０４、ソース／デスティネーション関数内外依存解析部２０５および命令スケジュール部２０６を制御し、次に述べるプログラム並列化動作を実行する。【００７２】
強連結成分抽出部２０３は、入力した逐次処理中間プログラム３０２から強連結成分を抽出し、呼出の深い関数から順に若い番号を振る。たとえば、図８に示す関数呼び出しグラフにおいて、次のようにして帰りがけ順の番号をふる。有向辺に沿って、関数ｆ２１、ｆ２２、ｆ２３の順に辿り、これ以上まだ辿っていない関数がないので関数ｆ２３の帰りがけ順を「１」とする。次に関数ｆ２２に戻り、これ以上まだ辿っていない関数がないので、関数ｆ２２の帰りがけ順を「２」とする。最後に関数ｆ１１に戻り、これ以上まだ辿っていない関数がないので、関数ｆ１１の帰りがけ順を「３」とする。このようにして、呼び出しが深いものに若い番号を振ることができる。帰りがけ順を求める方法には、「データ構造とアルゴリズム」（Ａ．Ｖ．エイホ他著、大野義夫訳、培風館、１９８７）の第１９５項〜第１９８項に記載のものが挙げられる。【００７３】
スケジューリング・依存解析回数管理部２０４は、詳しくは後述するが、強連結成分を構成する関数の依存形態に応じて強連結成分のスケジューリングおよび依存解析の実行回数を管理する。【００７４】
ソース／デスティネーション関数内外依存解析部２０５は、上述したように、命令間の依存情報３０４を参照し、ある関数ｆ内の命令と、関数呼び出しグラフにおける当該関数ｆの子孫の関数群の命令との間の依存を解析する。この解析された依存関係に従って、命令スケジュール部２０６は命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻と実行プロセッサとを実現するように命令の実行順序を決定してフォーク命令を挿入する。【００７５】
なお、命令間依存情報３０４を生成する装置を設けることもできる。以下、命令間依存情報生成回路について簡単に説明する。【００７６】
図１３は命令間依存情報を生成する回路の一例を示すブロック図である。制御フロー解析部１０１．１は逐次処理プログラムの制御フローを解析し、その解析結果をスケジュール領域形成部１０１．２、レジスタデータフロー解析部１０１．３および命令間メモリデータフロー解析部１０１．４へ出力する。【００７７】
スケジュール領域形成部１０１．２は、制御フロー解析結果と逐次処理プログラムのプロファイルデータとを参照して、命令スケジュールの単位となるスケジュール領域を決定する。【００７８】
レジスタデータフロー解析部１０１．３は、制御フロー解析結果とスケジュール領域形成部１０１．２により決定されたスケジュール領域とを参照して、レジスタの読み書きに伴うデータフローを解析する。【００７９】
命令間メモリデータフロー解析部１０１．４は、制御フロー解析結果と逐次処理プログラムのプロファイルデータとを参照して、あるメモリアドレスに対する読み書きに伴うデータフローを解析する。【００８０】
レジスタデータフロー解析部１０１．３および命令間メモリデータフロー解析部１０１．４により得られたレジスタおよびメモリの読み書きに伴うデータフローの解析結果は、命令間依存情報３０４として依存解析・スケジュール部１０２へ出力され、制御フロー解析結果およびスケジュール領域は、逐次処理中間プログラム３０２として依存解析・スケジュール部１０２へ出力される。【００８１】
３．２）プログラム並列化動作
図１４は依存解析・命令スケジュール部１０８で処理される依存解析およびスケジュール処理の全体的動作を示すフローチャートである。【００８２】
まず、強連結成分抽出部２０３は、逐次処理中間プログラム３０２を参照して、関数呼出グラフの強連結成分を求める。次に、関数呼出グラフの強連結成分を順序に従って処理する。たとえば、すでに処理したものを再び処理しないために、最初に全ての強連結成分を未選択とマークし、処理したものを選択済とマークしていく。こうして、順序に従って、関数呼出グラフの強連結成分のうち未選択のものを強連結成分ｓとする（ステップＳ１０１）。強連結成分の選択の順序については、その強連結成分を構成する関数を一つ選び、その関数の帰りがけ順のインデックス値が小さいものを優先する。【００８３】
次に、順序に従って強連結成分sを構成する関数のうち未選択の関数を関数ｆとする（ステップＳ１０２）。強連結成分ｓを構成する関数の順序については、例えば関数呼出グラフの行きがけ順で付与したインデックス値が小さいものを優先してもよい。【００８４】
続いて、命令スケジュール部２０６は関数ごとの命令スケジュールを行う。すなわち、関数内のスケジュール領域ごとに、命令の実行時刻と実行プロセッサを決定し、決定された命令の実行時刻と実行プロセッサを実現するように命令の実行順序を決定し、フォーク命令を挿入して図示しないメモリに格納する（ステップＳ１０３）。【００８５】
次に、制御部２０１は強連結成分ｓの全ての関数をスケジュールしたかを判定し（ステップＳ１０４）、スケジュールしていない関数があれば（ステップＳ１０４のＮｏ）、ステップ１０２に制御を戻す。【００８６】
選択された強連結成分ｓに含まれる全ての関数のスケジュールが完了していれば（ステップＳ１０４のＹｅｓ）、制御部２０１はソース／デスティネーション関数内外依存解析部２０５に指示し、強連結成分ｓの依存を示す有向辺のソースに関する関数内外依存解析（ステップＳ１０５）とデスティネーションに関する関数内外依存解析とを実行する（ステップＳ１０６）。ソースに関する関数内外依存解析については図１５および図１６で、デスティネーションに関する関数内外依存解析については図１７および図１８で詳細に説明する。【００８７】
次に、スケジューリング・依存解析回数管理部２０４は、ステップＳ１０２からステップＳ１０６で構成されるループの繰り返し回数が当該強連結成分ｓの指定値に達したか否かを判定する（ステップＳ１０７）。繰り返し回数が指定値に達していなければ（ステップＳ１０７のＮｏ）、強連結成分ｓを構成する全関数を未選択にし（ステップＳ１０８）、ステップＳ１０２に制御を戻す。このようにステップＳ１０２からステップＳ１０６の解析を繰り返し行っているのは、強連結成分ｓを構成する関数同士に再帰呼び出しあるいは相互再帰呼び出しによる相互依存がある場合、ある関数におけるスケジュールおよび依存解析の結果を他の関数におけるスケジュールおよび依存解析に利用する必要があるためである。繰り返し回数は、関数呼出グラフにおける強連結成分ｓの形態に応じて、１回あるいは複数回に設定することができる。例えば、関数呼出グラフにおいて、強連結成分ｓを構成する関数同士の間に有向辺がある場合には繰り返し回数を複数回（例えば４回）、あるいは、強連結成分ｓを構成する関数が１つで、その関数が自己再帰呼び出しを行っている場合にも繰り返し回数を複数回（たとえば４回）に、それ以外は１回に設定してもよい。あるいは繰り返し回数は、例えば強連結成分ｓがループを表している場合は４回に、それ以外は１回というように設定してもよい。このように解析とスケジュールを繰り返すことで、スケジュールによる依存先命令の位置が変化することに対応することができ、ループを表す強連結成分に対してより良好なスケジュールを得ることができる。【００８８】
繰り返し回数が指定値に到達すると（ステップＳ１０７のＹｅｓ）、全ての強連結成分を調べたか否かを判定し（ステップＳ１０９）、調べていない強連結成分があれば（ステップｓ１０９のＮｏ）、ステップＳ１０１に制御を戻す。全ての強連結成分を調べた場合は（ステップｓ１０９のＹｅｓ）、依存解析およびスケジュール処理を終了する。【００８９】
３．３）ソースに関する関数内外依存解析
次に、ソース／デスティネーション関数内外依存解析部２０５により実行されるソースに関する関数内外依存解析処理（ステップＳ１０５）について詳細に説明する。【００９０】
図１５はソースに関する関数内外依存解析処理の全体を示すフローチャートであり、図１６はソースに関する関数内外依存解析処理の詳細を示すフローチャートである。【００９１】
図１５において、まず、順序に従って、強連結成分ｓを構成する関数のうち未選択の関数を関数ｆとする（ステップＳ２０１）。強連結成分ｓを構成する関数の順序においては、上述したように、例えば関数呼出グラフの行きがけ順で付与したインデックス値が大きいものを優先してもよい。【００９２】
続いて、ソース／デスティネーション関数内外依存解析部２０５は、関数ごとのソースに関する関数内外依存解析を行う（ステップＳ２０２）。詳しくは図１６で詳述する。【００９３】
制御部２０１は、処理対象の強連結成分を構成する全ての関数を調べたか否かを判定し（ステップＳ２０３）、まだ調べていない関数がある場合は（ステップＳ２０３のＮｏ）、制御をＳ２０１に戻す。全ての関数を調べたならば（ステップＳ２０３のＹｅｓ）、ステップＳ２０１からステップＳ２０３までの処理ループの繰り返し回数が指定値に達したか否かを判定する（ステップＳ２０４）。繰り返し回数が指定値に達していなければ（ステップＳ２０４のＮｏ）、強連結成分ｓを構成する全関数を未選択にし（ステップＳ２０５）、ステップＳ２０１に制御を戻す。【００９４】
ステップＳ２０１からステップＳ２０３までの解析処理を繰り返し行っているのは、上述したように、強連結成分ｓを構成する関数同士に再帰呼び出しあるいは相互再帰呼び出しによる相互依存があるためである。繰り返し回数は、関数呼出グラフにおける強連結成分ｓの形態に応じて、１回あるいは複数回に設定することができる。例えば、関数呼出グラフにおいて、強連結成分ｓを構成する関数同士の間に有向辺がある場合には繰り返し回数を複数回（例えば４回）、あるいは、強連結成分ｓを構成する関数が１つで、その関数が自己再帰呼び出しを行っている場合にも繰り返し回数を複数回（たとえば４回）に、それ以外は１回に設定してもよい。あるいは繰り返し回数は、強連結成分がループを表している場合で、かつそのループの繰り返し回数が分かっている場合は、そのループの繰り返し回数に設定してもよい。【００９５】
繰り返し回数が指定値に達していた場合は（ステップｓ２０４のＹｅｓ）、強連結成分ごとのソースに関する関数内外依存解析処理を終了する。【００９６】
次に、図１６を参照して、上記ステップＳ２０２における関数ごとのソースに関する関数内外依存解析処理を詳細に説明する。【００９７】
まず、処理対象となる関数の命令のうち未選択のものがあるか否かを判定し（ステップＳ３０１）、未選択のものがなければ（ステップＳ３０１のＮｏ）、後述するステップＳ３０７に制御を移す。未選択のものがあれば（ステップＳ３０１のＹｅｓ）、順序に従って、処理対象となる関数の命令のうち未選択のものを命令ｉとする（ステップＳ３０２）。命令の選択の順序については、例えば、命令のアドレスの順序を用いてもよい。【００９８】
続いて、命令ｉがソースになっている依存の有向辺のうち未選択のものがあるか否かを判定し（ステップＳ３０３）、未選択のものがなければ（ステップＳ３０３のＮｏ）、ステップＳ３０１に制御を移す。たとえば、図５Ａにおいて、関数ｆｑが強連結成分ｓである場合、その中の命令Lｑ_ｊは関数ｆｐの命令Lp_ｌへの依存のソースとなっている。【００９９】
未選択のものがあれば（ステップＳ３０３のＹｅｓ）、順序に従って、命令ｉがソースになっている依存の有向辺のうち未選択のものを有向辺ｅとする（ステップＳ３０４）。有向辺の選択の順序については任意の順序を用いてよい。【０１００】
次に、有向辺ｅを複製し、複製してできた有向辺のソースを処理対象の関数を表すノードに置き換える（ステップＳ３０５）。続いて、有向辺に付加されているソースに関する実行時刻および実行プロセッサ番号の相対値に、処理対象の関数の開始時点を基準とした命令ｉの実行時刻および実行プロセッサ番号の相対値を加算する（ステップＳ３０６）。ステップＳ３０６の処理の具体的な操作は、デスティネーションに関する関数内外依存解析に関する図１８および図２２を用いた説明のなかで明らかにする。【０１０１】
なお、ソースが関数を表すノードであるようなデータフローに関する依存の有向辺は、レジスタの個数が予め分かっているので、関数ごとの表として表現しても良い。この表は、レジスタ番号をインデックスとし、有向辺に付加されているソースに関する実行時刻および実行プロセッサ番号の相対値とソースの命令の遅延時間とを内容とする。表として表現することで、リスト表現を用いた場合に比較して、使用するメモリ容量を少なくすることができる。【０１０２】
次に、処理対象の関数を呼び出す関数呼出し命令のうち、未選択のものがあるか否かを判定し（ステップＳ３０７）、未選択のものがなければ（ステップＳ３０７のＮｏ）、関数ごとのソースに関する関数内外依存解析処理を終了する。未選択のものがあれば（ステップＳ３０７のＹｅｓ）、順序に従って、処理対象の関数を呼び出す関数呼出し命令のうち、未選択のものを関数呼出命令ｃとする（ステップＳ３０８）。【０１０３】
続いて、複製してできた有向辺のうち未選択のものがあるか否かを判定し（ステップＳ３０９）、未選択のものがなければ（ステップＳ３０９のＮｏ）、ステップＳ３０７に制御を移す。未選択のものがあれば（ステップＳ３０９のＹｅｓ）、順序に従って、有向辺のうち未選択のものを有向辺ｅとする（ステップＳ３１０）。【０１０４】
次に、有向辺ｅを複製して、複製してできた有向辺のソースを命令ｃにした有向辺を作成し（ステップＳ３１１）、有向辺に付加されているソースに関する実行時刻および実行プロセッサ番号の相対値に、命令ｃの実行時点を基準とした処理対象の関数の開始時刻および実行プロセッサ番号の相対値を加算する（ステップＳ３１２）。ステップＳ３１２の処理の具体的な操作も、デスティネーションに関する関数内外依存解析に関する図１８および図２２を用いた説明のなかで明らかにする。【０１０５】
そして、制御をステップＳ３０９へ戻し、複製してできた有向辺のうち未選択のものがなくなるまで、ステップＳ３１０〜Ｓ３１２を繰り返す。【０１０６】
３．４）デスティネーションに関する関数内外依存解析
次に、ソース／デスティネーション関数内外依存解析部２０５により実行されるデスティネーションに関する関数内外依存解析処理（ステップＳ１０６）について詳細に説明する。【０１０７】
図１７はデスティネーションに関する関数内外依存解析処理の全体を示すフローチャートであり、図１８はデスティネーションに関する関数内外依存解析処理の詳細を示すフローチャートである。【０１０８】
図１７において、まず、順序に従って、強連結成分sを構成する関数のうち未選択の関数を関数ｆとする（ステップＳ４０１）。なお、強連結成分ｓを構成する関数の順序については、例えば、関数呼び出しグラフの行きがけ順で付与したインデックスを調べ、その値が大きいものを優先してもよい。【０１０９】
続いて、関数ごとのデスティネーションに関する関数内外依存解析を行う（ステップ４０２）。詳しくは図１８で詳述する。【０１１０】
制御部２０１は、処理対象の強連結成分を構成する全ての関数を調べたか否かを判定し（ステップＳ４０３）、まだ調べていない関数がある場合は（ステップＳ４０３のＮｏ）、制御をステップＳ４０１に戻す。処理対象の強連結成分を構成する全ての関数を調べていれば（ステップＳ４０３のＹｅｓ）、ステップＳ４０１からステップＳ４０４までのループ処理の繰り返し回数が指定値に達したか否かを判定する（ステップＳ４０４）。繰り返し回数が指定値に達していなければ（ステップＳ４０４のＮｏ）、強連結成分ｓを構成する全関数を未選択にし（ステップＳ４０５）、ステップＳ４０１に制御を戻す。繰り返し回数は、関数呼出グラフにおける強連結成分ｓの形態に応じて、１回あるいは複数回に設定することができる。例えば、関数呼出グラフにおいて、強連結成分ｓを構成する関数同士の間に有向辺がある場合には繰り返し回数を複数回（例えば４回）、あるいは、強連結成分ｓを構成する関数が１つで、その関数が自己再帰呼び出しを行っている場合にも繰り返し回数を複数回（たとえば４回）に、それ以外は１回に設定してもよい。あるいは繰り返し回数は、強連結成分がループを表している場合で、かつそのループの繰り返し回数が分かっている場合は、そのループの繰り返し回数に設定してもよい。【０１１１】
ループの繰り返し回数が指定値に達していた場合は（ステップＳ４０４のＹｅｓ）、強連結成分ごとのデスティネーションに関する関数内外依存解析処理を終了する。【０１１２】
次に、図１８を参照して、上記ステップＳ４０２における関数ごとのデスティネーションに関する関数内外依存解析処理を詳細に説明する。【０１１３】
まず、処理対象の関数の命令のうち未選択のものがあるか否かを判定し（ステップＳ５０１）、未選択のものがなければ（ステップＳ５０１のＮｏ）、ステップＳ５０７に制御を移す。未選択のものがあれば（ステップＳ５０１のＹｅｓ）、順序に従って、処理対象の関数の命令のうち未選択のものを命令ｉとする（ステップＳ５０２）。命令の選択の順序については、例えば、命令のアドレスの順序を用いてもよい。【０１１４】
続いて、命令ｉがデスティネーションになっている依存の有向辺のうち未選択のものがあるか判定し（ステップＳ５０３）、未選択のものがなければ（ステップＳ５０３のＮｏ）、ステップＳ５０１に制御を移す。未選択のものがあれば（ステップＳ５０３のＹｅｓ）、順序に従って、命令ｉがデスティネーションになっている依存の有向辺のうち未選択のものを有向辺ｅとする（ステップＳ５０４）。有向辺の選択の順序については、任意の順序を用いてよい。【０１１５】
次に、有向辺ｅを複製し、複製してできた有向辺のデスティネーションを処理対象の関数を表すノードに置き換える（ステップＳ５０５）。有向辺に付加されている、デスティネーションに関する実行時刻および実行プロセッサ番号の相対値に、処理対象の関数の開始時点を基準とした命令ｉの実行時刻および実行プロセッサ番号の相対値を加算する（ステップＳ５０６）。このステップＳ５０６は、後述するように図２２における操作ｏｐ１に相当する。前述した図１６のステップＳ３０６もソースに関する同様の操作である。【０１１６】
なお、デスティネーションが関数を表すノードであるようなデータフローに関する依存の有向辺は、レジスタの個数が予め分かっているので、関数ごとの表として表現しても良い。この表は、レジスタ番号をインデックスとし、有向辺に付加されているデスティネーションに関する実行時刻および実行プロセッサ番号の相対値を内容とする。表として表現することで、リスト表現を用いた場合に比較して、使用するメモリ容量を少なくすることができる。【０１１７】
次に、処理対象の関数を呼び出す関数呼出命令のうち、未選択のものがあるか否かを判定し（ステップＳ５０７）、未選択のものがなければ（ステップＳ５０７のＮｏ）、関数ごとのソースに関する関数内外依存解析処理を終了する。未選択のものがあれば（ステップＳ５０７のＹｅｓ）、順序に従って、処理対象の関数を呼び出す関数呼出し命令のうち、未選択のものを関数呼び出しの命令ｃとする（ステップＳ５０８）。【０１１８】
次に、複製してできた有向辺のうち未選択のものがあるか否かを判定し（ステップＳ５０９）、未選択のものがなければ（ステップＳ５０９のＮｏ）、ステップＳ５０７に制御を移す。未選択のものがあれば（ステップＳ５０９のＹｅｓ）、順序に従って、有向辺のうち未選択のものを有向辺ｅとする（ステップＳ５１０）。【０１１９】
続いて、有向辺ｅを複製して、複製してできた有向辺のデスティネーションを命令ｃにした有向辺を作成し（ステップＳ５１１）、有向辺に付加されている、デスティネーションに関する実行時刻および実行プロセッサ番号の相対値に、命令ｃの実行時点を基準とした処理対象の関数の開始時刻および実行プロセッサ番号の相対値を加算する（ステップＳ５１２）。このステップＳ５１２は、後述するように図２２における操作ｏｐ２に相当する。前述した図１６のステップＳ３１２もソースに関する同様の操作である。【０１２０】
そして、制御をステップＳ５０９へ戻し、複製してできた有向辺のうち未選択のものがなくなるまで、ステップＳ５１０〜Ｓ５１２を繰り返す。【０１２１】
３．５）具体例
上述した図１４〜図１８の依存解析およびスケジュール処理の具体例を図１９〜図２４を参照しながら説明する。【０１２２】
図１９は逐次処理中間プログラムに変換される前の入力プログラムを示す図である。入力プログラムは関数ｆ１１および関数ｆ１２から構成され、実行は関数ｆ１１から開始するものとする。関数ｆ１１は関数呼出命令Ｌ１３によって関数ｆ１２を呼び出す。【０１２３】
図２０Ａは逐次処理中間プログラムを示した図であり、図２０Ｂはその関数呼出グラフを示す図である。関数ｆ１１および関数ｆ１２は関数を表すノードで表現される。関数ｆ１１は基本ブロックＢ１１およびＢ１２から構成されるものとし、その関係を点線の矢印で示す。基本ブロックＢ１１は命令Ｌ１１およびＬ１２から構成されるものとし、その関係を四角形で囲うことにより示す。基本ブロックＢ１２は命令Ｌ１３から構成されるものとする。関数ｆ１２は基本ブロックＢ１３から構成され、基本ブロックＢ１３は命令Ｌ１４、Ｌ１５、Ｌ１６およびＬ１７から構成されるものとする。【０１２４】
制御は、基本ブロックＢ１１を実行した後に基本ブロックＢ１２に移り、基本ブロックＢ１２で関数呼出命令Ｌ１３を実行した後に基本ブロックＢ１３に移るとものとする。この制御フローを実線の矢印で示す。また、ここでは、命令Ｌ１２を実行した後に命令Ｌ１６を実行する必要があるので、このデータフローによる依存を破線の矢印で示す。【０１２５】
レジスタデータフローおよびメモリデータフローの解析により、命令Ｌ１２から命令Ｌ１６へのデータフローの依存を示す有向辺が作成される。依存の有向辺に付加されているソースに関する実行時刻の相対値は０、実行プロセッサの相対値は０、遅延時間は命令Ｌ１２の遅延時間である１であるとする。デスティネーションに関する実行時刻の相対値は０、実行プロセッサの相対値は０とする。【０１２６】
図２０Ｂに示すように、関数呼び出しグラフは、関数ｆ１１および関数ｆ１２から構成されており、関数ｆ１１から関数ｆ１２に有向辺が存在する。また、関数ｆ１１はそれ自身で関数呼び出しグラフの１つの強連結成分を構成し、関数ｆ１２もそれ自身で１つの強連結成分を構成する。【０１２７】
次に、図２０Ａ、Ｂに示す具体例に対する依存解析およびスケジュール処理を図１４〜図１８のフローチャートも参照しつつ説明する。【０１２８】
まず、図１４のステップＳ１０１において、関数呼び出しグラフの帰りがけ順は、関数ｆ１２、関数ｆ１１であり、いずれもそれ自身で強連結成分を構成し、また、いずれの強連結成分も選択されていない。したがって、関数ｆ１２から構成される強連結成分を選択する。ステップＳ１０２において、選択された強連結成分ｓは関数ｆ１２のみから構成されるため、関数ｆ１２を選択する。【０１２９】
ステップＳ１０３において、関数ｆ１２の相対的な命令スケジュールを行う。「相対的スケジュール」とは、当該関数（ここでは関数ｆ１２）が実行を開始した実行サイクルおよびプロセッサ番号を基準として、その基準からの増分を示すスケジュールをいう。【０１３０】
図２１は関数ｆ１２の相対的スケジュールを示す図である。ステップＳ１０３における相対的スケジューリングの結果、図２１に示すように、命令Ｌ１４は（０，０）すなわちサイクル０、プロセッサ０に、命令Ｌ１５は（１，０）すなわちサイクル１、プロセッサ０に、命令Ｌ１６は（１，１）すなわちサイクル１、プロセッサ１に、命令Ｌ１７は（２，１）すなわちサイクル２、プロセッサ１にそれぞれ配置されたものとする。ここで、命令をプロセッサ１に配置する、とは、当該関数が実行を開始したプロセッサを基準としてプロセッサ番号が１増加したプロセッサで実行する、という意味である。ここでいうプロセッサ番号はスケジュール空間のプロセッサ番号である。プロセッサ数は有限であるため、スケジュール空間のプロセッサ番号を実際のプロセッサ数で割った際の剰余を、実行時のプロセッサ番号として用いる。同様に、命令をサイクル１に配置する、とは、当該関数が実行を開始した時点（サイクル）を基準として１サイクル後に実行する、という意味である。【０１３１】
この例では強連結成分を構成する全ての関数をスケジュールしたので（ステップＳ１０４のＹｅｓ）、ステップＳ１０５へ進み、強連結成分ごとのソースに関する関数内外依存解析を行う。この例では、ステップＳ１０５で依存の有向辺は追加されないので説明を省略する。【０１３２】
次に、ステップＳ１０６において、強連結成分ごとのデスティネーションに関する関数内外依存解析を行う。以下、図１７、図１８および図２２を参照しながら説明する。【０１３３】
図２２は、依存解析過程における有向辺に付加された相対値の操作を説明するための逐次処理中間プログラムを示した図である。【０１３４】
まず、図１７のステップＳ４０１において、選択された強連結成分は関数ｆ１２のみから構成されるため、関数ｆ１２を選択する。ステップＳ４０２において、関数ごとのデスティネーションに関する関数内外依存解析を行う。【０１３５】
図１８のステップＳ５０１において、関数ｆ１２の全ての命令が未選択であるため、制御をステップＳ５０２へ移す。ステップＳ５０２において命令Ｌ１４を選択する。ステップＳ５０３において、命令Ｌ１４がデスティネーションになっている依存の有向辺は存在しないため、制御をステップＳ５０１に移す。ステップＳ５０１、Ｓ５０２において、命令Ｌ１５を選択するが、命令Ｌ１５もデスティネーションになっている依存の有向辺は存在しないため、制御をステップＳ５０１に移す。同様に、ステップＳ５０１、Ｓ５０２において命令Ｌ１６を選択する。【０１３６】
命令Ｌ１６はデスティネーションになっている依存の有向辺が存在するので、ステップＳ５０３およびＳ５０４において、命令Ｌ１２から命令Ｌ１６への依存の有向辺ｅを選択する。そして、ステップＳ５０５において、有向辺ｅを複製し、命令Ｌ１２から関数ｆ１２への依存の有向辺を作成する。【０１３７】
次に、ステップＳ５０６において、有向辺に付加されていたデスティネーションに関する相対値に、関数ｆ１２の開始時刻を基準とした、命令Ｌ１６の実行時刻の相対値および実行プロセッサ番号の相対値を加算する。有向辺に付加されていたデスティネーションに関する相対値は、図２０Ａに示すように実行時刻およびプロセッサ番号ともに０であり、図２１に示すように、命令Ｌ１６の実行時刻の相対値は１、実行プロセッサ番号の相対値は１であるため、これらを加算する。結果として、図２２の操作ｏｐ１が実行され、破線の矢印（Ｂ）に示すような、命令Ｌ１２から関数ｆ１２への依存の有向辺が作成される。そのデスティネーションに関する相対値は（１，１）、すなわち実行時刻が１、実行プロセッサが１となる。【０１３８】
次に、ステップＳ５０３において、命令Ｌ１６がデスティネーションになっている依存の有向辺のうち未選択のものがあるか判定する。未選択のものはないので制御をステップＳ５０１に移す。続いて、ステップＳ５０１、Ｓ５０２において、命令Ｌ１７を選択する。ステップＳ５０３において、命令Ｌ１７がデスティネーションになっている依存の有向辺は存在しないため、制御をステップＳ５０１に移す。ステップＳ５０１において、未選択の命令があるか判定し、未選択の命令はないので制御をステップＳ５０７へ移す。ステップＳ５０７、ステップＳ５０８において、関数ｆ１２を呼び出す関数呼出命令Ｌ１３を選択する。【０１３９】
続いて、ステップＳ５０９、ステップＳ５１０において、命令Ｌ１２から関数ｆ１２への依存の有向辺を選択し、ステップＳ５１１において、有向辺を複製し命令Ｌ１２から命令Ｌ１３への依存の有向辺を作成する。【０１４０】
次に、ステップＳ５１２において、有向辺に付加されていたデスティネーションに関する相対値に、命令Ｌ１３の実行時刻を基準とした関数ｆ１２の開始時刻の相対値および実行プロセッサ番号の相対値をそれぞれ加算する。この例では、命令Ｌ１３の実行の１サイクル後に関数ｆ１２が同じプロセッサ上で実行を開始すると仮定されているので、有向辺に付加されていたデスティネーションに関する相対値（実行時刻１，プロセッサ１）に実行時刻１と実行プロセッサ０を加算する。結果として、図２２の操作ｏｐ２が実行され、破線の矢印（Ｃ）に示すような、命令Ｌ１２から命令Ｌ１３への依存の有向辺が作成される。そのデスティネーションに関する相対値は（実行時刻２、実行プロセッサ１）である。【０１４１】
次に、ステップＳ５０９において、複製してできた有向辺のうち未選択のものはないので、制御をステップＳ５０７に移す。ステップＳ５０７において、関数ｆ１２を呼び出す関数呼出命令のうち未選択のものはないので、関数ごとのデスティネーションに関する関数内外依存解析処理を終了する。【０１４２】
次に、図１７のステップＳ４０３において、関数ｆ１２から構成される強連結成分の全ての関数を調べたので、ステップＳ４０４へ進む。ステップＳ４０４において、指定回数繰り返したか判定する。この例では、強連結成分を構成する関数ｆ１２から同じ強連結成分を構成する関数への関数呼び出しはないので、指定回数は１に設定されている。そのため、強連結成分ごとのデスティネーションに関する関数内外依存解析処理を終了する。【０１４３】
次に、図１４のステップＳ１０７において、指定回数繰り返したか判定する。強連結成分はループを表していないので、指定回数は１であるから、ステップＳ１０９に進む。関数ｆ１２から構成される強連結成分を調べ終わり、関数ｆ１１から構成される強連結成分をまだ調べていないので（ステップＳ１０９のＮｏ）、ステップＳ１０１に制御を戻す。【０１４４】
こうして、図２２に示す操作ｏｐ１およびｏｐ２を実行することで、命令Ｌ１２からＬ１６への依存関係の情報が、破線の矢印（Ｃ）に示すように、命令Ｌ１２から命令Ｌ１３への依存として組み込まれる。したがって、命令Ｌ１３（関数１２の呼出命令）のスケジューリングは、依存のデスティネーションである命令Ｌ１６に関する相対値（実行時刻２、実行プロセッサ１）を考慮して実行される。【０１４５】
ステップＳ１０１において、関数ｆ１２から構成される強連結成分は選択したので、残りの関数ｆ１１から構成される強連結成分を選択する。ステップＳ１０２において、選択された強連結成分は関数ｆ１１のみから構成されるため関数ｆ１１を選択する。【０１４６】
ステップＳ１０３において、関数ｆ１１の命令スケジュールを行う。命令スケジュールにおいて、図２３に示すように、命令Ｌ１１、命令Ｌ１２が配置され、これからＬ１３を配置するところであるとする。また、命令Ｌ１２の定義するデータは、１サイクル後に、命令Ｌ１２の実行されたプロセッサか、番号がより大きな他のプロセッサ上の命令から参照できるとする。【０１４７】
命令Ｌ１３を配置する時刻およびプロセッサを決定する際に、命令Ｌ１２から命令Ｌ１３への依存の有向辺と有向辺に付加された相対値（実行時刻２、実行プロセッサ１）とを参照する。有向辺に付加したソースに関する相対値は次のことを意味する。すなわち、命令Ｌ１２が定義するデータが入手可能になるのは、命令Ｌ１２の実行時刻に、ソースに関する相対時刻および遅延時間を加えた時刻、命令Ｌ１２の実行プロセッサにソースに関する相対プロセッサ番号を加えたプロセッサである、ということである。【０１４８】
また、有向辺に付加したデスティネーションに関する相対値は次のことを意味する。すなわち、データを参照する命令Ｌ１６は、命令Ｌ１３の実行時刻にデスティネーションに関する相対時刻を加えた時刻、命令Ｌ１３の実行プロセッサにデスティネーションに関する相対プロセッサ番号を加えたプロセッサにおいて実行される、ということである。【０１４９】
したがって、命令Ｌ１２が定義するデータが入手可能になるのは、命令Ｌ１２が実行されるサイクル１にソースに関する相対時刻０と遅延時間１を加えたサイクル２、命令Ｌ１２が実行されるプロセッサ０にソースに関する相対プロセッサ番号０を加えたプロセッサ０となる。【０１５０】
また、命令Ｌ１６は、命令Ｌ１３の実行時刻に、デスティネーションに関する相対時刻２を加えた時刻、命令Ｌ１３の実行プロセッサにデスティネーションに関する相対プロセッサ番号１を加えたプロセッサ、において実行される。この命令Ｌ１６の実行時刻、実行プロセッサが、命令Ｌ１２が定義するデータが入手可能な時刻およびプロセッサであればよいことになる。これは、見方を変えると、命令Ｌ１３の実行時刻に２を加えた時刻、命令Ｌ１３の実行プロセッサに０を加えたプロセッサが、サイクル２以上で、プロセッサ番号が０以上であればよいということになる。この条件の下で、最も実行時刻が小さい時刻に命令Ｌ１３を配置する。【０１５１】
図２３は命令Ｌ１３のスケジュール決定過程を示す図であり、図２４は命令Ｌ１３のスケジュール結果を示す図である。図２３に示すように、命令Ｌ１３の配置を決定することは、それが呼び出す関数ｆ１２を構成する命令Ｌ１３〜Ｌ１７の相対的スケジュールの配置も決定することを意味する。したがって、命令Ｌ１２と依存関係のある命令Ｌ１６が、命令Ｌ１２より後の実行サイクルとなるように（制約条件ａ）、かつ、全体の実行時間が最も短くなるように（制約条件ｂ）、命令Ｌ１３のスケジュールの配置を決定すればよい。この例では、これらの条件ａおよびｂを満たす命令Ｌ１３の配置は、図２４に示すように、サイクル０、プロセッサ１となるであろう。【０１５２】
このように命令Ｌ１３をサイクル０、プロセッサ１に配置することで、全ての命令の実行は４サイクルで完了することになる。【０１５３】
３．６）効果
図２５は、従来技術によるスケジュールを比較例として示す図である。このように、ある関数ｆ内の命令と、関数呼出グラフにおける当該関数ｆの子孫の関数群の命令との間の依存について考慮しない場合は、命令Ｌ１２から命令Ｌ１６への依存の安全な近似を行う。具体的には、命令Ｌ１６を含む関数ｆ１２を呼び出す命令Ｌ１３は、命令Ｌ１２の実行時刻１より遅い時刻に配置される。このような配置を行った場合、全ての命令の実行には６サイクルが必要となる。【０１５４】
これに対して、本実施例によれば、関数ｆ１１内の命令Ｌ１２と、関数ｆ１１が呼び出す関数ｆ１２内の命令Ｌ１６との間の依存について解析しているために、本発明による並列化スケジュールの方が実行時間を短くできる。具体的には、命令Ｌ１２が定義するデータが入手可能な時刻およびプロセッサと、命令Ｌ１６が関数ｆ１２を呼び出す命令Ｌ１３の実行時刻および実行プロセッサに対してどれだけずれて実行されるかを示す相対値とを解析し、これらの解析結果を用いて、関数ｆ１２を呼び出す命令Ｌ１３の実行時刻および実行プロセッサの配置を行う。これにより命令Ｌ１３の実行時刻を早めることができ、また関数ｆ１２の開始時刻を早めることができる。【０１５５】
さらに、本実施例によれば、並列化においてフォーク箇所の組み合わせを対象にした探索を行わない。フォーク箇所の組み合わせは可能な候補数が非常に多いので、プログラム並列化の高速性を困難にしていたが、本実施例ではこのようなフォーク箇所の組み合わせの探索を行わないので、並列実行時間のより短い並列化プログラムを高速に生成することができる。
【実施例２】
【０１５６】
４．第２実施例
図２６は本発明の第２実施例によるプログラム並列化装置の構成を示す概略的ブロック図である。本実施例によるプログラム並列化装置１００Ａは、処理装置１０１Ａに第１実施例と同じ依存解析・スケジュール部１０２をソフトウエアあるいはハードウェアにより実現している。【０１５７】
さらに、本実施例では、図１３で説明した制御フロー解析部１０１．１、スケジュール領域形成部１０１．２、レジスタデータフロー解析部１０１．３および命令間メモリデータフロー解析部１０１．４が設けられ、命令間依存情報３０４および逐次処理中間プログラム３０２を依存解析・スケジュール部１０２へ出力する。また、依存解析・スケジュール部１０２から出力された並列化中間プログラムは、レジスタ割り当て部１０１．５およびプログラム出力部１０１．６によって並列化プログラム４０６に変換される。【０１５８】
記憶装置４０１には、図示しない逐次コンパイラによって生成された機械語命令形式の逐次処理プログラム４０２が格納されている。記憶装置４０３には、逐次処理プログラム４０２を並列化プログラムに変換する過程で使用するプロファイルデータ４０４が格納されている。また、処理装置１０１Ａにより生成された並列化プログラム４０６は記憶装置４０５に格納される。記憶装置４０１、４０３および４０５は、磁気ディスク等の記録媒体である。【０１５９】
本実施例によるプログラム並列化装置１００Ａは、逐次処理プログラム４０２およびプロファイルデータ４０４を入力し、マルチスレッド型並列プロセッサ向けの並列化プログラム４０６を生成する。このようなプログラム並列化装置１００Ａは、パーソナルコンピュータやワークステーションなどのコンピュータとプログラムとで実現することができる。プログラムは、磁気ディスク等のコンピュータ可読記録媒体に記録され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に制御フロー解析部１０１．１、スケジュール領域形成部１０１．２、レジスタデータフロー解析部１０１．３および命令間メモリデータフロー解析部１０１．４、依存解析・スケジュール部１０２、レジスタ割り当て部１０１．５およびプログラム出力部１０１．６といった機能手段を実現する。【０１６０】
制御フロー解析部１０１．１は、逐次処理プログラム４０２を入力し、制御フローを解析する。この解析結果を参照して、ループを再帰関数に変換してもよい。この変換によって、ループの各イタレーションを並列化することができる。【０１６１】
スケジュール領域形成部１０１．２は、制御フロー解析部１０１．１による制御フローの解析結果とプロファイルデータ４０４とを参照して、命令の実行時刻および実行プロセッサとを決定する命令スケジュールの対象となるスケジュール領域を決定する。【０１６２】
レジスタデータフロー解析部１０１．３は、制御フローの解析結果とスケジュール領域形成部１０１．２によるスケジュール領域の決定を参照してレジスタの読み書きに伴うデータフローを解析する。【０１６３】
命令間メモリデータフロー解析部１０１．４は、制御フローの解析結果とプロファイルデータ４０４とを参照して、あるメモリアドレスに対する読み書きに伴うデータフローを解析する。【０１６４】
依存解析・スケジュール部１０２は、第１実施例で説明したとおりであり、レジスタデータフロー解析部１０１．３によるレジスタのデータフローの解析結果と、命令間メモリデータフロー解析部１０１．４による命令間のデータフローの解析結果とを参照して、命令間の依存を解析する。特に、ある関数内の命令と、関数呼び出しグラフにおける当該関数の子孫の関数群の命令との間の依存を解析する。そして、既に説明したように、依存に従って命令の実行時刻および実行プロセッサを決定し、決定された命令の実行時刻および実行プロセッサを実現するように命令の実行順序を決定し、フォーク命令を挿入する。【０１６５】
レジスタ割り当て部１０１．５は、命令スケジュール部１０４によって決定された命令の実行順序およびフォーク命令を参照してレジスタ割り当てを行う。プログラム出力部１０１．６は、レジスタ割り当て部１０１．５の結果を参照して、実行可能な並列化プログラム４０６を生成する。【０１６６】
次に本実施例によるプログラム並列化装置１００Ａの動作について説明するが、依存解析・スケジュール部１０２の動作は図１４〜図１８で説明したのでここでは省略する。【０１６７】
まず、制御フロー解析部１０１．１は、逐次処理プログラム４０２を入力し、制御フローを解析する。プログラム並列化装置１０１Ａの内部では、第１実施例と同様に逐次処理プログラム４０２はグラフの形で表現される。【０１６８】
スケジュール領域形成部１０１．２は、制御フロー解析部１０１．１による制御フローの解析結果とプロファイルデータ４０４とを参照して、命令の実行時刻および実行プロセッサとを決定する命令スケジュールの対象となるスケジュール領域を決定する。スケジュール領域は、例えば、基本ブロックとしてもよいし、複数の基本ブロックとしてもよい。【０１６９】
レジスタデータフロー解析部１０１．３は、制御フローの解析結果とスケジュール領域形成部１０１．２によるスケジュール領域の決定を参照してレジスタの読み書きに伴うデータフローを解析する。データフローの解析は、例えば、関数内に限定して行ってもよいし、関数間にまたがって行ってもよい。データフローは命令間の依存として、命令を表すノードを結ぶ有向辺で表す。有向辺には、既に述べたように、ソースに関する実行時刻の相対値、実行プロセッサ番号の相対値およびソースの命令の遅延時間を付加する。この時点では、実行時刻の相対値は０、プロセッサ番号の相対値は０、遅延時間はソースの命令の遅延時間に設定する。有向辺にはデスティネーションに関する実行時刻の相対値、実行プロセッサ番号の相対値を付加する。この時点では、実行時刻の相対値は０、プロセッサ番号の相対値は０に設定する。【０１７０】
命令間メモリデータフロー解析部１０１．４は、制御フローの解析結果とプロファイルデータ４０４とを参照して、あるメモリアドレスに対する読み書きに伴うデータフローを解析する。データフローは命令間の依存として、上述したように、命令を表すノードを結ぶ有向辺で表す。【０１７１】
レジスタ割り当て部１０１．５は、命令スケジュール部１０４によって決定された命令の実行順序およびフォーク命令を参照してレジスタ割り当てを行う。プログラム出力部１０１．６は、レジスタ割り当て部１０１．５の結果を参照して、実行可能な並列化プログラム４０６を生成する。【０１７２】
このように、プログラム制御プロセッサ等の処理装置１０１Ａ上で命令間依存情報を生成し、並列化中間プログラムに対してレジスタ割り当てを行うことで実行可能な並列化プログラム４０６を出力することができる。第１実施例と同様に依存解析・スケジュール部１０２を有するので、並列実行時間のより短い並列化プログラムを高速に生成することができる。【０１７３】
なお、本発明は上記実施例に限定されるものではなく、本発明の特徴を変更しない限り、各種の付加変更が可能である。例えば、上記第２実施例において、プロファイルデータ４４を省略した構成にすることも可能である。
【産業上の利用可能性】
【０１７４】
本発明のプログラム並列化方法及び装置は、例えば実行効率の高い並列プログラムを生成する方法及び装置に利用される。
【図１Ａ】
2008090665.tif 000003
【図１Ｂ】
2008090665.tif 000004
【図１Ｃ】
2008090665.tif 000005
【図１Ｄ】
2008090665.tif 000006
【図２Ａ】
2008090665.tif 000007
【図２Ｂ】
2008090665.tif 000008
【図３】
2008090665.tif 000009
【図４Ａ】
2008090665.tif 000010
【図４Ｂ】
2008090665.tif 000011
【図５Ａ】
2008090665.tif 000012
【図５Ｂ】
2008090665.tif 000013
【図６】
2008090665.tif 000014
【図７Ａ】
2008090665.tif 000015
【図７Ｂ】
2008090665.tif 000016
【図８】
2008090665.tif 000017
【図９】
2008090665.tif 000018
【図１０】
2008090665.tif 000019
【図１１】
2008090665.tif 000020
【図１２】
2008090665.tif 000021
【図１３】
2008090665.tif 000022
【図１４】
2008090665.tif 000023
【図１５】
2008090665.tif 000024
【図１６】
2008090665.tif 000025
【図１７】
2008090665.tif 000026
【図１８】
2008090665.tif 000027
【図１９】
2008090665.tif 000028
【図２０Ａ】
2008090665.tif 000029
【図２０Ｂ】
2008090665.tif 000030
【図２１】
2008090665.tif 000031
【図２２】
2008090665.tif 000032
【図２３】
2008090665.tif 000033
【図２４】
2008090665.tif 000034
【図２５】
2008090665.tif 000035
【図２６】
2008090665.tif 000036
【国際調査報告】
2008090665.tif 000037
2008090665.tif 000038
2008090665.tif 000039
2008090665.tif 000040
2008090665.tif 000041