(57)【要約】【課題】マルチコア・プロセッサ等の新たな並列処理用プロセッサにおいて、プログラムを効率的に動作させる。【解決手段】並列処理を最適化するコンパイラを提供する。コンパイラは、対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している。コンパイラは、まず、対象プログラムの中から単一のプロセッサ・コアで連続して実行すべき実行パスの候補である支配的パスを検出する。次に、実行コア数以下の数の支配的パスを選択することによりマルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成する。次に、生成されたクラスタ毎に、実行コア数以下の１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する。そして、算出された実行時間に基づいて各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を選択する。【選択図】図５
2007048052.tif 000002
【特許請求の範囲】
【請求項１】
コンパイル対象の対象プログラムの、マルチコア・プロセッサによる実行を最適化するコンパイラ装置であって、
前記マルチコア・プロセッサが有するプロセッサ・コアのうち、前記対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している、記録部と、
前記対象プログラムの中から単一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出する、パス検出部と、
前記実行コア数以下の数の支配的パスを選択することにより前記マルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成する、クラスタ生成部と、
生成されたクラスタ毎に、前記実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する、時間算出部と、
前記対象プログラムの実行時間を短縮するべく、算出された前記実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を、生成された前記クラスタの各々について選択する、コア数選択部と
を備えるコンパイラ装置。
【請求項２】
前記時間算出部は、生成されたクラスタ毎に、当該クラスタを１から前記実行コア数までの各々の自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出し、
前記コア数選択部は、算出された前記実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を、生成された前記クラスタの各々について選択する
請求項１に記載のコンパイラ装置。
【請求項３】
前記クラスタ生成部は、逐次に実行されまたは並列に実行できる、２以上の前記クラスタを前記クラスタの上位階層のクラスタ群とし、逐次に実行されまたは並列に実行できる、２以上の前記クラスタ群を更に上位階層のクラスタ群としていくことにより、前記複数のクラスタについての階層化された実行順序の依存関係を示すシリーズパラレル・グラフを生成し、
前記コア数選択部は、下位階層の前記クラスタ群から順に、前記プロセッサ・コアの個数以下の自然数の中から選択した１つまたは複数の自然数の各々について、前記下位階層のクラスタ群を当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出し、算出された当該実行時間に基づいて前記下位階層のクラスタ群の実行時間を短縮すべく、前記下位階層のクラスタ群の更に下位階層に位置する並列実行可能な２以上の前記クラスタに、または前記クラスタ群に、割り当てるべきプロセッサ・コアの個数を選択していくことにより、各々の前記クラスタに割り当てるプロセッサ・コアの個数を選択する
請求項１に記載のコンパイラ装置。
【請求項４】
前記クラスタ生成部は、複数の前記クラスタの各々をノードとし、実行順序に依存関係を有する複数のクラスタに対応する複数のノードの上位階層に、当該複数のクラスタが逐次に実行すべき逐次実行部分である旨を示すノードを生成し、並列に実行可能な複数のクラスタに対応する複数のノードの上位階層に、当該複数のクラスタが並列に実行可能な並列実行部分である旨を示すノードを生成し、更に、
実行順序に依存関係を有する複数の並列実行部分または逐次実行部分に対応する複数のノードの上位階層に、当該複数の並列実行部分または逐次実行部分が更に逐次実行部分である旨を示すノードを生成し、または、並列に実行可能な複数の並列実行部分または逐次実行部分に対応する複数のノードの上位階層に、当該複数の並列実行部分または逐次実行部分が更に並列実行部分である旨を示すノードを生成することによりシリーズパラレル・グラフを生成し、
前記コア数選択部は、逐次実行部分および並列実行部分の各々の実行時間を最適にするように当該部分を構成するクラスタ、逐次実行部分または並列実行部分の各々に割り当てるプロセッサ・コアの個数を選択する問題を部分問題とし、各々の部分問題を動的計画法によって解くことにより、前記対象プログラムの実行時間を最適にするために各々のクラスタに割り当てるプロセッサ・コアの個数を選択する
請求項１に記載のコンパイラ装置。
【請求項５】
検出された前記支配的パスの各々について、当該支配的パス中の何れかのタスクの処理に依存する他の実行パス中のタスクの処理に、当該支配的パス中の他のタスクが更に依存する循環性依存を検出する、循環性依存検出部を更に備え、
前記クラスタ生成部は、検出された前記循環性依存の数がより少ない支配的パスを、他の支配的パスよりも優先して選択し、選択した当該支配的パスおよび他のタスクを含めたクラスタを生成する
請求項１に記載のコンパイラ装置。
【請求項６】
前記支配的パスの各々について、当該支配的パス中の何れかのタスクと直接データ転送するタスクを含む他の支配的パスである隣接パスを選択する、隣接パス選択部を更に備え、
前記クラスタ生成部は、検出された前記循環性依存の数が各支配的パスについて同一であることを条件に、前記隣接パスの数がより少ない支配的パスを、他の支配的パスよりも優先して選択し、選択した当該支配的パスおよび他のタスクを含めたクラスタを生成する
請求項５に記載のコンパイラ装置。
【請求項７】
前記クラスタ生成部は、
少なくとも１つの前記支配的パスについて、当該支配的パスと共にクラスタに含めるべきタスクの候補である候補タスクを選択する、候補選択部と、
前記候補タスクを当該支配的パスと共にクラスタに含めた場合において、前記クラスタに含まれる支配的パスの総数を算出する、パス数算出部と、
算出された支配的パスの前記総数が前記実行コア数以下であることを条件に、前記候補タスクを含めて前記クラスタを生成するタスク追加部と
を有し、
前記候補選択部は、前記候補タスクが前記クラスタに追加されたことを条件に、更に他のタスクを前記クラスタに含めるべき他の候補タスクとして選択する
請求項１に記載のコンパイラ装置。
【請求項８】
選択された前記候補タスクが、前記クラスタ中の複数のタスクの各々と通信する通信量の和を算出する通信量算出部を更に備え、
前記タスク追加部は、予め定められた基準値よりも前記通信量の和が大きいことを更に条件として、選択された前記候補タスクを含めて前記クラスタを生成する
請求項７に記載のコンパイラ装置。
【請求項９】
選択された前記候補タスクを当該支配的パスと共に前記クラスタに含めた場合において前記クラスタ中のタスクを前記実行コア数のプロセッサ・コアで実行した場合に前記プロセッサがアイドル状態となる時間の割合を算出する、アイドル割合算出部を更に備え、
前記タスク追加部は、予め定められた基準値よりも前記アイドル状態となる時間の割合が小さいことを更に条件として、選択された前記候補タスクを含めて前記クラスタを生成する
請求項７に記載のコンパイラ装置。
【請求項１０】
前記時間算出部は、前記クラスタの各々の実行時間を、当該クラスタ内から当該クラスタ外へのタスク切替、または、当該クラスタ外から当該クラスタ内へのタスク切替に、予め見積もられた最大所要時間を要すると見積もることによって算出する
請求項１に記載のコンパイラ装置。
【請求項１１】
前記対象プログラム中の第１タスクについて、前記第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択する、タスク選択部と、
前記第１タスクおよび選択された前記第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、前記第２タスクを前記第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮される前記タスク切替時間の短縮量を算出する短縮量算出部と
を更に備え、
前記パス検出部は、算出される前記短縮量が最大となる第２タスクを前記第１タスクと共に前記支配的パスに含めて検出する
請求項１に記載のコンパイラ装置。
【請求項１２】
コンパイル対象の対象プログラムの中から、同一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出するコンパイラ装置であって、
前記対象プログラム中の第１タスクについて、前記第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択する、タスク選択部と、
前記第１タスクおよび選択された前記第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、前記第２タスクを前記第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮される前記タスク切替時間の短縮量を算出する、短縮量算出部と、
算出される前記短縮量が最大となる第２タスクを前記第１タスクと共に前記支配的パスに含めて検出する、パス検出部と
を備えるコンパイラ装置。
【請求項１３】
前記短縮量算出部は、更に、選択された前記第２タスクが処理結果に依存する先行タスクの各々について、当該先行タスクおよび前記第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、前記第２タスクを当該先行タスクの次に同一のプロセッサ・コアで実行させることにより短縮される短縮量を算出し、
前記パス検出部は、複数の前記先行タスクのうち前記第１タスクについての短縮量が最も大きいことを更に条件として、前記第２タスクを前記第１タスクと共に前記支配的パスに含めて検出する
請求項１２に記載のコンパイラ装置。
【請求項１４】
前記対象プログラムは、マルチコア・プロセッサにおいて実行され、
前記マルチコア・プロセッサは、
プロセッサ・コアと、
前記プロセッサ・コアに接続された局所メモリと、
当該マルチコア・プロセッサの外部に接続されるメイン・メモリと前記局所メモリとの間で命令コード又はデータを転送するＤＭＡコントローラと、
の組を複数有し、
先行タスクの処理結果を後続タスクに前記局所メモリを介して転送する処理の所要時間と、前記処理結果を前記メイン・メモリを介して転送する処理の処理時間と、を記録する記録部を更に備え、
前記短縮量算出部は、前記処理結果を前記局所メモリを介して転送する処理の所要時間と、前記処理結果を前記メイン・メモリを介して転送する処理の所要時間と、の差分値に基づいて前記短縮量を算出し、
前記パス検出部は、算出された前記短縮量が最大となる第２タスクを前記第１タスクと共に前記支配的パスに含めて検出する
請求項１２に記載のコンパイラ装置。
【請求項１５】
前記記録部は、前記先行タスクの実行コードに代えて前記後続タスクの実行コードを前記メイン・メモリから前記局所メモリに読み込む処理の所要時間を更に記録し、
前記短縮量算出部は、前記第１タスクおよび前記第２タスクが同一の実行コードを実行する場合の前記短縮量として、前記第１タスクおよび前記第２タスクが異なる実行コードを実行する場合の前記短縮量に、前記メイン・メモリから実行コードを前記局所メモリに読み込む処理の前記所要時間を加えた時間を算出する
請求項１４に記載のコンパイラ装置。
【請求項１６】
コンパイル対象の対象プログラムの、マルチコア・プロセッサによる実行を最適化する、コンパイラ装置によるコンパイル方法であって、
前記コンパイラ装置が、前記マルチコア・プロセッサの有するプロセッサ・コアのうちで前記対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している記録部を有し、
前記対象プログラムの中から単一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出するステップと、
前記実行コア数以下の数の支配的パスを選択することにより前記マルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成するステップと、
生成されたクラスタ毎に、前記実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出するステップと、
前記対象プログラムの実行時間を短縮するべく、算出された前記実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を、生成された前記クラスタの各々について選択するステップと
を備える方法。
【請求項１７】
コンパイル対象の対象プログラムの中から、同一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出するコンパイル方法であって、
前記対象プログラム中の第１タスクについて、前記第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択するステップと、
前記第１タスクおよび選択された前記第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、前記第２タスクを前記第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮される前記タスク切替時間の短縮量を算出するステップと、
算出される前記短縮量が最大となる第２タスクを前記第１タスクと共に前記支配的パスに含めて検出するステップと
を備える方法。
【請求項１８】
コンパイル対象の対象プログラムの、マルチコア・プロセッサによる実行を最適化するコンパイラ装置として、情報処理システムを機能させるコンパイラ・プログラムであって、
前記情報処理システムを、
前記マルチコア・プロセッサが有するプロセッサ・コアのうち、前記対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している、記録部と、
前記対象プログラムの中から単一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出する、パス検出部と、
前記実行コア数以下の数の支配的パスを選択することにより前記マルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成する、クラスタ生成部と、
生成されたクラスタ毎に、前記実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する、時間算出部と、
前記対象プログラムの実行時間を短縮するべく、算出された前記実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を、生成された前記クラスタの各々について選択する、コア数選択部
として機能させるコンパイラ・プログラム。
【請求項１９】
コンパイル対象の対象プログラムの中から、同一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出するコンパイラ装置として、情報処理システムを機能させるコンパイラ・プログラムであって、
前記情報処理システムを、
前記対象プログラム中の第１タスクについて、前記第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択する、タスク選択部と、
前記第１タスクおよび選択された前記第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、前記第２タスクを前記第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮される前記タスク切替時間の短縮量を算出する、短縮量算出部と、
算出される前記短縮量が最大となる第２タスクを前記第１タスクと共に前記支配的パスに含めて検出する、パス検出部
として機能させるコンパイラ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラ、制御方法およびコンパイラ・プログラムに関する。特に、本発明は、複数のタスクを並列処理させることによりプログラムを最適化するコンパイラ、制御方法およびコンパイラ・プログラムに関する。
【背景技術】
【０００２】
近年、複数のプロセッサ・コアを搭載したマイクロプロセッサが開発されている。各々のプロセッサ・コアは、他のプロセッサ・コアとは独立にかつ他のプロセッサ・コアと並列に演算を行うことができる。例えば、出願人によって開発されたＰＯＷＥＲ５プロセッサは、２つのプロセッサ・コアを有し、これらを並列に駆動させることができる。また、出願人らによって開発されたＣＥＬＬプロセッサは、８つのプロセッサ・コアを並列に駆動させることができる。
【０００３】
図１に、分散メモリ型のマルチコア・マイクロプロセッサ１０の構成を示す。マイクロプロセッサ１０は、プロセッサ・コア１００−１〜Ｎと、各々のプロセッサ・コアに対応する局所メモリ１１０およびＤＭＡエンジン１２０を有する。プロセッサ・コア１００−１〜Ｎの各々は、共通のオンチップバス１４０により相互に接続されている。また、プロセッサ・コア１００−１〜Ｎは、オフチップバス１５０によりメイン・メモリ１０２０に接続されている。
【０００４】
プロセッサ・コア１００−１は、局所メモリ１１０−１からプログラムを読み出して実行し、局所メモリ１１０−１中のデータにアクセスして処理を進行させる。処理結果は、所定のタイミングでメイン・メモリ１０２０に出力される。ここで、局所メモリ１１０−１は、従来のキャッシュメモリと同様に、メイン・メモリ１０２０と比較して極めて高速にアクセス可能である。また、オンチップバス１４０は、オフチップバス１５０による通信と比較して、局所メモリ１１０−１〜Ｎ間を極めて高速に通信させることができる。
【０００５】
以下、本発明の参考技術を挙げる。これらについては後述する。
【非特許文献１】Y. Kwok and I. Ashmad, "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors," ACM Computing Surveys, Vol. 31, No. 4, December 1999.
【非特許文献２】A. Gonzalez Escribano, A.J.C. van Gemund, and V. Cardenoso-Payo, "Mapping Unstructured Applications into Nested Parallelism," Proceedings of VECPAR 2002 - 5th International Conference on High Performance Computing for Computational Science, LNCS 2565, 2003, pp. 407-420.
【非特許文献３】P. Chretienne and C. Picouleau, "Scheduling with communication delays: a survey," In P. Chretienne, E.G. Coffman Jr., J.K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, chapter 4, pp. 65-90, John Wiley & Sons, 1995.
【非特許文献４】MPICH, http://www-unix.mcs.anl.gov/mpi/mpich/
【非特許文献５】LAM-MPI, http://www.lam-mpi.org
【非特許文献６】PVM, http://www.csm.ornl.gov/pvm/pvm_home.html
【非特許文献７】H. Ogawa and S. Matsuoka, "OMPI: optimizing MPI programs using partial evaluation," Proceedings of the 1996 ACM/IEEE conference on Supercomputing, November 1996.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このようなマルチコア・マイクロプロセッサにおいては、各々のプロセッサ・コアにおいて何れのタスクをどのような順序で実行させるかによって、処理全体の性能が大きく異なる。これは、局所メモリ１１０−１〜Ｎの各々の記憶容量が、メイン・メモリ１０２０と比べて極めて小さいからである。即ち、ある第１タスクの処理結果を次の第２タスクで用いない場合には、その処理結果を局所メモリに保持しておくことはできず、それを後で用いることができるようにメイン・メモリ１０２０に退避しなければならない。
【０００７】
このため、例えば、ある第１タスクの処理結果を用いる第２タスクは、第１タスクの次に連続して同一のプロセッサ・コアで実行させることが好ましい。また、第１タスクの処理中にその処理経過を用いる第３タスクは、第１タスクの処理中に他のプロセッサ・コアにおいて並列に実行させることが好ましい。従来、このような分散メモリ型マルチコア・マイクロプロセッサの特徴を活用して該当システムで効果的なタスクの実行順序を定める技術は提案されていなかった。
【０００８】
なお、参考技術として、分散メモリ・マルチプロセッサにおいて、複数のタスクを効率的に各々のプロセッサで実行させる技術が提案されている。例えば、非特許文献１においては、複数のタスクの相互依存関係を示すグラフを解析することによりプログラム全体を効率的に実行させるアルゴリズムを比較検討している。
【０００９】
既存の一般的なマルチプロセッサを搭載するシステムにおいて、プロセッサは大容量のメモリを高速にアクセスできる。これに対して、プロセッサ間の通信は低速である。このため、互いに頻繁に通信する複数のタスクについては、これらの間で発生する通信の通信量を低減するべく、同一のプロセッサで実行させるようにしていた。この結果、同一のプロセッサにおいてタスク切替が頻繁に発生する場合があった。
【００１０】
これに対して、マルチコア・プロセッサは、複数のプロセッサ・コアが互いに高速に通信できる。一方で、同一のプロセッサ・コアで異なるタスクを連続して実行する場合には、メイン・メモリへのアクセスが発生して処理効率が低下する。即ち、局所メモリが充分に大きくないので、前のタスクのコンテクストを局所メモリからメイン・メモリに退避し、かつ、次のタスクのコンテクストをメイン・メモリから局所メモリにロードする必要がある。
【００１１】
このように、マルチプロセッサを搭載したシステムとマルチコア・プロセッサとでは、その特徴が大きく異なり、マルチプロセッサに関連する技術をマルチコア・プロセッサにそのまま適用することはできない。
【００１２】
また、他の参考技術として、一群のタスクをクラスタにまとめ、クラスタ間の相互依存関係を示すシリーズパラレル・グラフを生成する技術が提案されている（非特許文献２を参照。）。しかしながら、これらの技術において、各々のクラスタの実行に要する時間、または、クラスタ間の通信に要する時間その他の情報は、グラフの生成に用いられない。また、そのグラフに基づいてクラスタをスケジューリングする技術が提案されている（非特許文献３を参照。）が、この方式は無限個のプロセッサを仮定している。即ち、これらの技術は分散メモリ型マルチコア・プロセッサで効果的なスケジューリングを行わない。
【００１３】
また、動的計画法を効果的に適用するには、全体問題の最適解が、部分問題の最適解の和で構成されることが必要である。即ち、各クラスタを独立して実行した場合の実行時間が、そのクラスタと他のクラスタとを並列または連続して実行したときのそのクラスタの実行時間に一致しなければならない。マルチコア・プロセッサにおいて、あるタスクを実行する実行効率は、そのタスクと並列にまたは連続して実行される他のタスクによって処理効率は大きく異なる。このため、この技術をそのまま適用することは難しい。
【００１４】
更に他の参考技術として、MPI(Message Passing Interface)やPVM(Parallel Virtual Machine)が用いられている（非特許文献４〜７を参照。）。これらの技術によれば、分散メモリ・マルチプロセッサを搭載するシステムにおいて、アプリケーションプログラムを効率的に並列動作させることができる。しかしながら、これらの技術においては、各々のタスクの相互依存関係を静的に解析する機能や、各々のタスクが相互に通信する通信量を解析する機能は提供されない。
【００１５】
そこで本発明は、上記の課題を解決することのできるコンパイラ、コンパイル方法およびコンパイラ・プログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、本発明の第１の形態においては、コンパイル対象の対象プログラムを、マルチコア・プロセッサで最適に実行させるようにする装置としてのコンパイラ（コンパイラ装置）であって、マルチコア・プロセッサが有するプロセッサ・コアのうち、対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している、記録部と、対象プログラムの中から単一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出する、パス検出部と、実行コア数以下の数の支配的パスを選択することによりマルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成する、クラスタ生成部と、生成されたクラスタ毎に、実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する、時間算出部と、対象プログラムの実行時間を短縮するべく、算出された実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を、生成されたクラスタの各々について選択する、コア数選択部とを備えるコンパイラ、当該コンパイラによるコンパイル方法および当該コンパイラとして情報処理システムを機能させるコンパイラ・プログラムを提供する。
【００１７】
また、本発明の第２の形態においては、コンパイル対象の対象プログラムの中から、同一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出する装置としてのコンパイラ（コンパイラ装置）であって、対象プログラム中の第１タスクについて、第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択する、タスク選択部と、第１タスクおよび選択された第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、第２タスクを第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮されるタスク切替時間の短縮量を算出する、短縮量算出部と、算出される短縮量が最大となる第２タスクを第１タスクと共に支配的パスに含めて検出する、パス検出部とを備えるコンパイラ、当該コンパイラによるコンパイル方法および当該コンパイラとして情報処理システムを機能させるコンパイラ・プログラムを提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１８】
本発明によれば、マルチコア・プロセッサ等の新たな並列処理用プロセッサにおいて、プログラムを効率的に動作させることができる。
【発明を実施するための最良の形態】
【００１９】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００２０】
図２は、コンパイラ２０および情報処理システム３０の全体構成を示す。コンパイラ２０は、対象プログラム１５を入力し、プロセッサ１０などのマルチコア・プロセッサで実行させるように最適化する。最適化された結果の結果プログラムは、情報処理システム３０において実行される。例えば、情報処理システム３０は、入力パラメータを結果プログラムに入力して実行し、その処理結果を出力する。
【００２１】
図３は、情報処理システム３０のハードウェア構成の一例を示す。情報処理システム３０は、ホストコントローラ１０８２により相互に接続されるプロセッサ１０、メイン・メモリ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００２２】
ホストコントローラ１０８２は、メイン・メモリ１０２０と、高い転送レートでメイン・メモリ１０２０をアクセスするプロセッサ１０及びグラフィックコントローラ１０７５とを接続する。プロセッサ１０は、ＢＩＯＳ１０１０及びメイン・メモリ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、プロセッサ１０等がメイン・メモリ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、プロセッサ１０等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００２３】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、情報処理システム３０が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、メイン・メモリ１０２０又はハードディスクドライブ１０４０に提供する。
【００２４】
また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、情報処理システム３０の起動時にプロセッサ１０が実行するブートプログラムや、情報処理システム３０のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してメイン・メモリ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００２５】
情報処理システム３０に提供される結果プログラムは、電気通信回線を経由して通信インターフェイス１０３０などから提供される。結果プログラムは情報処理システム３０に働きかけて、プログラム作成者が意図した演算その他の処理を行わせ、その処理結果を出力させる。以上に示したプログラムは、外部の記憶媒体に格納されて提供されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。
【００２６】
図４は、対象プログラム１５の一例を示す。対象プログラム１５は、情報処理システム３０に働きかけてガウスの消去法を実現する。以降、この対象プログラム１５を例に情報処理システム３０のコンパイル処理を説明する。また、本例に示す対象プログラム１５は、プログラムの処理内容をその処理手順に沿って説明する擬似コードであり、実際にコンパイルされるプログラムとは異なってもよい。また、対象プログラム１５は、２個のプロセッサ・コアと１個のサポートプロセッサとにより実行される。そして、対象プログラム１５における変数Ｎは、行列の大きさを示し、本実施例においてＮは４とする。即ち、対象プログラム１５は、４×４の正方行列についてガウスの消去法を実現することを目的とする。
【００２７】
３行目から５行目のプログラムは、サポートタスクによる処理を示す。即ち、変数ｍｙ＿ｔａｓｋ＿ｉｄには、実行中のタスクの識別番号が予め格納されている。タスクの識別番号が０の場合には、そのタスクはサポートタスクとなる。４行目および５行目のプログラムによって、サポートタスクは、連立方程式のパラメータを他の各々のタスクに分配し、その処理結果を各々のタスクから収集する。
【００２８】
６行目から２６行目のプログラムは、サポートタスクを除く他の各々のタスクの処理を示す。７行目および８行目のプログラムによって、各タスクは、連立方程式のパラメータをサポートタスクから取得する。９行目から１８行目のプログラムによって、各タスクは、そのタスクの識別番号と同一番号の行の解を求める。１９行目から２５行目のプログラムによって、各タスクは、そのタスク以外の各々のタスクから解を取得する。また、各タスクは、そのタスクによって担当する行の解を求めて他のタスクに送信する。
【００２９】
図５は、コンパイラ２０の機能構成を示す。コンパイラ２０は、パス関連処理部５００と、性能情報記録部５０５と、クラスタ関連処理部５１０と、実行時間算出部５２０と、コア数選択部５３０とを有する。性能情報記録部５０５は、情報処理システム３０の性能に関する各種の情報を記録する。例えば、性能情報記録部５０５は、プロセッサ１０が有するプロセッサ・コアの数のうち、対象プログラム１５を実行するプロセッサ・コアの個数である実行コア数を記録している。また、性能情報記録部５０５は、タスクの処理結果を局所メモリ１１０−１を介して他のタスクに転送する処理の所要時間の見積もりを記録している。なお、所要時間とは、マイクロ秒、ミリ秒等の実時間のみならず、プロセッサの実行サイクル数などの指標値であってもよい。
【００３０】
パス関連処理部５００は、性能情報記録部５０５から取得した性能に関する情報に基づいて、対象プログラム１５から所定の実行パスを検出する。ここで、実行パスとは、先行タスクを完了しなければ後続タスクを開始できない関係にある複数のタスクの処理の流れをいう。具体的には、パス関連処理部５００は、複数のタスクの各々をノードとし、それらの間の依存関係（例えば、制御依存またはデータ依存など）をエッジとした有向グラフを生成し、そのグラフ中の任意のパスの中から所定の方法によって実行パスを検出してもよい。
【００３１】
なお、本実施例においてタスクとは、対象プログラム１５中の処理の一部を指す。好ましくは、タスクは、その実行中にプリエンプション（例えば、コンテクストスイッチなど）を行わないことが保証された命令群である。即ち例えば、コンパイラ２０は、最適化処理に先立って、対象プログラム１５を、ブロッキング通信関数呼び出しを境界として分割することにより複数のタスクを生成する。
【００３２】
クラスタ関連処理部５１０は、対象プログラム１５に含まれる複数のタスクの中から所定の方法によって少なくとも１つのタスクを選択してクラスタとする。この処理を順次繰り返し、クラスタ関連処理部５１０は、対象プログラム１５に含まれる複数のタスクを複数のクラスタに分類する。クラスタの分類にも、性能情報記録部５０５に記録された情報が用いられる。
【００３３】
実行時間算出部５２０は、生成されたクラスタ毎に、実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する。例えば、実行コア数が７であれば、７以下の自然数の中から選択した１つまたは複数の自然数（即ち例えば３個および５個）に等しい個数のプロセッサ・コアで実行した実行時間を算出してもよい。好ましくは、実行時間算出部５２０は、クラスタを最も効率的に実行し得るプロセッサ・コアの個数を選択し、その個数のプロセッサ・コアで実行した場合の実行時間を算出してもよい。例えば、３以上のプロセッサ・コアで実行してもそれ以下の個数のプロセッサ・コアで実行した場合よりも実行時間が短縮しないことが予め分かっている場合には、実行時間算出部５２０は、３つのプロセッサ・コアで実行した場合の実行時間のみを算出してもよい。実行時間は、例えば、性能情報記録部５０５に記録された情報に基づいてその見積もり値が算出される。
【００３４】
コア数選択部５３０は、対象プログラム１５の実行時間を短縮するべく、算出された実行時間に基づいて、各クラスタの実行のために割り当てるプロセッサ・コアの個数を、生成されたクラスタの各々について選択する。各クラスタについて選択されたコアの個数は、例えば、命令スケジューラその他の最適化モジュールに通知されてもよい。このコアの個数に基づいて生成された結果プログラムは、情報処理システム３０に出力されて情報処理システム３０において実行される。
【００３５】
図６は、性能情報記録部５０５のデータ構造の一例を示す。図６（ａ）に示すように、性能情報記録部５０５は、データ転送条件およびコンテクスト転送条件の組に対応付けて、データ転送時間およびコンテクスト転送時間を記録している。データ転送条件とは、先行タスクおよびその処理結果に依存する後続タスクの間で処理結果のデータを転送する方法を定める条件である。例えば、データ転送条件は、先行タスクおよび後続タスクを同一のプロセッサで連続して実行するか、および、これらを異なるプロセッサで実行するか若しくは非連続に実行するかの何れかである。
【００３６】
先行タスクおよび後続タスクを同一のプロセッサで連続して実行することを条件に、先行タスクの処理結果は局所メモリを介して後続タスク転送される。このため、性能情報記録部５０５は、この条件に対応するデータ転送時間として、先行タスクの処理結果を後続タスクに局所メモリを介して転送する処理の所要時間を記録する。この所要時間は、実際の所要時間でなくともよく、プロセッサ１０の性能から予想される所要時間の見積もり値であってもよい。
【００３７】
先行タスクおよび後続タスクを異なるプロセッサで実行するか若しくは非連続に実行することを条件に、先行タスクの処理結果はメイン・メモリを介して後続タスクに転送される。このため、性能情報記録部５０５は、この条件に対応するデータ転送時間として、先行タスクの処理結果をメイン・メモリを介して転送する処理の所要時間を記録する。同様に、この所要時間は、情報処理システム３０の性能から予想される所要時間の見積もり値であってもよい。
【００３８】
また、コンテクスト転送条件とは、先行タスクおよび後続タスクの間でコンテクストを切り替える方法を定める条件である。例えば、コンテクスト転送条件は、先行タスクおよび後続タスクが同一タスクであるか、タスクは異なるが実行コードが同一であるか、および、タスクも実行コードも異なるかの何れかである。
【００３９】
先行タスクおよび後続タスクが同一であることを条件に、局所メモリに記録されている実行コードおよびコンテクストは、後続タスクにおいてそのまま用いられる。このため、性能情報記録部５０５は、この条件に対応するコンテクスト転送時間として０を記録する。一方で、先行タスクおよび後続タスクが異なり、かつ実行コードが同一であることを条件に、その実行コードは後続タスクにおいてそのまま用いられる。このため、性能情報記録部５０５は、この条件に対応するコンテクスト転送時間として、先行タスクのコンテクストを局所メモリからメイン・メモリに退避して後続タスクのコンテクストをメイン・メモリから局所メモリに復帰させる処理の所要時間を記録する。ここで、コンテクストとは、例えば、スタックポインタの値やその他のレジスタの値などを指す。
【００４０】
また、先行タスクおよび後続タスクの実行コードも異なることを条件に、先行タスクの実行コードに代えて後続タスクの実行コードがメイン・メモリから局所メモリに読み込まれる。このため、性能情報記録部５０５は、この条件に対応するコンテクスト転送時間として、先行タスクの実行コードに代えて後続タスクの実行コードをメイン・メモリから局所メモリに読み込む処理の所要時間を、上記コンテクストの退避・復帰に要する時間に加えた時間を記録する。
【００４１】
また、図６（ｂ）に示すように、性能情報記録部５０５は、実行コア数を更に記録する。実行コア数は、対象プログラム１５を実行するプロセッサ・コアのコア数であるから、プロセッサ１０が有するコア数と一致するとは限らない。例えば、実行コア数は、プロセッサ１０が有するコア数からサポートプロセッサに対応する１つを除いた数であってもよい。一例としてプロセッサ１０が８つのプロセッサ・コアを有する場合には、実行コア数は７である。実行コア数は、予め定められてもよいし、コンパイラ２０の利用者により設定されてもよい。
【００４２】
図７は、コンパイラ２０が対象プログラム１５をコンパイルする処理全体の流れを示す。パス関連処理部５００は、性能情報記録部５０５から取得した性能に関する情報に基づいて、単一のプロセッサ・コアで連続して実行すべきタスクの実行パスの候補である支配的パスを検出する（Ｓ７００）。好ましくは、パス関連処理部５００は、異なるプロセッサ・コアで実行し、または、非連続に実行した場合と比較して、性能向上の利得がより大きくなる実行パスを、支配的パスとして検出する。
【００４３】
クラスタ関連処理部５１０は、実行コア数以下の数の支配的パスを選択することによりプロセッサ１０において並列にまたは連続して実行すべきタスクのクラスタを生成する（Ｓ７１０）。生成されたクラスタにおいて支配的パスの数が実行コア数以下であるので、これらがたとえ並列に実行された場合であっても、支配的パス選択による性能向上の利得は失われない。
【００４４】
実行時間算出部５２０は、生成されたクラスタ毎に、実行コア数以下の自然数の中から選択した１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する（Ｓ７２０）。例えば、実行コア数が７であれば、７以下の少なくとも２つ、即ち例えば３個および５個の各々のコア数のプロセッサ・コアで実行した実行時間を算出してもよい。実行時間は、例えば、性能情報記録部５０５に記録された情報に基づいてその見積もり値が算出される。
【００４５】
これに加えて、実行時間算出部５２０は、実行コア数以下の３個以上のコア数の各々について実行時間を算出してもよい。好ましくは、実行時間算出部５２０は、生成されたクラスタ毎に、そのクラスタを１から実行コア数までの各々の自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する。即ち例えば、実行コア数が７であれば、各クラスタを１個、２個、３個、４個、５個、６個および７個の各々のコア数のプロセッサで実行した実行時間を算出することが望ましい。
【００４６】
更に好ましくは、実行時間の算出に際し、実行時間算出部５２０は、各々のクラスタの実行時間を、そのクラスタ内からクラスタ外へのタスク切替、または、そのクラスタ外からクラスタ内へのタスク切替に、予め見積もられた最大所要時間を要すると見積もる。予め見積もられた最大所要時間とは、例えば、それらのクラスタが非連続に実行されることによって生じるメモリアクセスの所要時間である。
【００４７】
実際には、あるクラスタの次に連続して他のクラスタが実行される場合には、当該クラスタから当該他のクラスタの間のタスク切替の時間は、この最大所要時間よりも短い。しかしながら、実行時間を算出する処理段階において、当該クラスタと当該他のクラスタとが連続して実行されるか否かを判断することはできない。このため、本実施例の実行時間算出部５２０は、タスク切替の所要時間を一律の最大所要時間とする。これにより、各クラスタの実行時間を統一した条件で評価することができる。
【００４８】
そして、コア数選択部５３０は、対象プログラム１５の実行時間を短縮するべく、算出された実行時間に基づいて、各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を選択する（Ｓ７３０）。
【００４９】
図８は、対象プログラム１５に含まれる複数のタスクがスケジューリングされる処理過程を示す（２図のうち１図目）。図８（ａ）は、対象プログラム１５に明示されたタスクの依存関係を示す。図中の円形の領域は、それぞれタスクを示し、図中の矢印はタスク間の依存関係を示す。図中の矩形領域の各々は、対象プログラム１５の文面上で一連の処理として明示されたタスク群を示す。例えば、命令群（Ｔ０）は、図４の３行目から５行目の処理に対応し、命令群（Ｔ１からＴ４）の各々は、図４の１０行目から１８行目に示す「ｆｏｒ」文の繰り返し処理の各々に対応する。
【００５０】
各々の繰り返し処理は、その途中にブロッキング通信命令を含むため、複数のタスクに分割されている。複数のタスクは、その処理内容に応じて相互に依存する。例えば、２番、３番、７番、１１番および１５番のタスクの各々は、１番のタスクの処理結果に依存する。
【００５１】
図８（ｂ）は、パス関連処理部５００によって検出された支配的パスの一例を示す。図中の矩形領域は、パス関連処理部５００によって検出された支配的パスを示す（Ｉ０からＩ４）。即ち、１５番、１６番、１７番および１８番のタスクは、同一のプロセッサで連続して実行すべきタスク群である。より詳細には、１５番のタスクの次に連続して１２番のタスクを実行するよりも、１５番のタスクの次に連続して１６番のタスクを実行した方が、性能向上の利得が大きいことを示している。本図の例において、対象プログラム１５中に明示された命令群Ｔ０からＴ４の各々は、支配的パスＩ０からＩ４の各々と一致するが、これらは必ずしも一致するとは限らない。
【００５２】
図８（ｃ）は、クラスタ関連処理部５１０によって生成されたクラスタの一例を示す。Ｃ１からＣ５を付して示した各々の矩形領域は、クラスタ関連処理部５１０によって生成された各々のクラスタを示す。即ち、クラスタ関連処理部５１０は、実行コア数である２を上限とする数の支配的パスを選択することによってクラスタを生成する。一例として、図８（ｂ）に示した支配的パスＩ３およびＩ４によって、クラスタＣ１が生成されている。
【００５３】
図９は、対象プログラム１５に含まれる複数のタスクがスケジューリングされる処理過程を示す（２図のうち２図目）。クラスタ関連処理部５１０は、各々のクラスタに割り当てるべきプロセッサ・コアの個数を選択するために、各々の当該クラスタの間で実行の依存関係を定めたシリーズパラレル・グラフを生成する。図９（ａ）は、クラスタ関連処理部５１０によって生成されたシリーズパラレル・グラフの一例を示す。
【００５４】
具体的な処理としては、まず、クラスタ関連処理部５１０は、クラスタ間の依存関係を定めるグラフから、推移的な依存関係を取り除く。例えば、図８（ｃ）において、クラスタＣ１はクラスタＣ５に直接依存しており、なおかつ、クラスタＣ１はクラスタＣ３に直接依存し、クラスタＣ３はクラスタＣ５に直接依存している。この場合、クラスタＣ１がクラスタＣ５に直接依存する依存関係は推移的な依存関係となる。クラスタ関連処理部５１０は、このような推移的な依存関係を取り除く。
【００５５】
この結果、クラスタ関連処理部５１０は、クラスタＣ４はクラスタＣ２に、クラスタＣ２はクラスタＣ１に、クラスタＣ１はクラスタＣ３に、クラスタＣ３はクラスタＣ５にそれぞれ直接依存するグラフを、シリーズパラレル・グラフとして生成する。これらのクラスタ群は、この順に逐次的に実行される必要のある逐次実行部分であり、シリーズスィートと呼ばれる。コア数選択部５３０は、このシリーズスィートの実行時間をより短縮するべく各々のクラスタの実行のために割り当てるプロセッサ・コアの個数を動的計画法により選択する。本例の場合、単純に、各々のクラスタに２つのプロセッサ・コアが割り当てられる。
【００５６】
図９（ｂ）は、コンパイルされた結果プログラムにおいて各々のタスクが実行される順序を示す。即ち、サポートプロセッサ１３０においてタスク１が最初に実行されてタスク２が最後に実行される。また、プロセッサ・コア１００−１およびプロセッサ・コア１００−２によりクラスタＣ３が並列に実行され、クラスタＣ１が並列に実行され、クラスタＣ２が並列に実行される。
【００５７】
次に、（１）支配的パスの検出、（２）クラスタの生成、および、（３）プロセッサ・コアの個数の選択の各処理について、その詳細を説明する。
（１）支配的パスの検出処理について
図１０は、パス関連処理部５００の機能構成を示す。パス関連処理部５００は、タスク選択部６００と、短縮量算出部６１０と、パス検出部６２０とを有する。タスク選択部６００は、対象プログラム１５中の第１タスクについて、その第１タスクの処理結果に依存する少なくとも１つの第２タスク（例えばその処理結果に依存する全てのタスク）を選択する。短縮量算出部６１０は、第１タスクおよび選択されたその第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、第２タスクを第１タスクの次に同一のプロセッサ・コアで実行した場合に短縮されるタスク切替時間の短縮量を算出する。
【００５８】
この短縮量は、第１タスクおよび第２タスクのコンテクストが同一である場合においては、コンテクストの退避および復帰に要する時間を含む。また、この短縮量は、第１タスクおよび第２タスクのコンテクストが異なる場合であっても実行コードが同一である場合においては、実行コードをメイン・メモリ１０２０から局所メモリに読み込む時間を含む。即ち、短縮量算出部６１０は、第１タスクおよび第２タスクが同一の実行コードを実行する場合の短縮量として、第１タスクおよび第２タスクが異なる実行コードを実行する場合の短縮量に、メイン・メモリ１０２０から実行コードを局所メモリに読み込む処理の所要時間を加えた時間を算出する。
【００５９】
パス検出部６２０は、算出された短縮量短縮幅が最も大きい第２タスクを当該支配的パスに含めて検出する。そして、タスク選択部６００は、当該支配的パスに含められた第２タスクを新たな第１タスクとして、その第１タスクに依存する新たな第２タスクについて上記同様の処理を繰り返す。パス検出部６２０は、全てのタスクを何れかの支配的パスに含めて検出したことを条件に、その検出結果をクラスタ関連処理部５１０に出力する。
【００６０】
図１１は、Ｓ７００における処理の詳細を示す。タスク選択部６００は、既に全てのタスクを何れかの支配的パスに含めるべく選択したか否かを判断する（Ｓ１１００）。既に全てのタスクを選択したことを条件に（Ｓ１１００：ＹＥＳ）、パス関連処理部５００は本図の処理を終了する。選択していなければ（Ｓ１１００：ＮＯ）、タスク選択部６００は、まだ選択されていない何れかのタスクを第１タスクとして選択する（Ｓ１１１０）。
【００６１】
次に、タスク選択部６００は、第１タスクが、サポートタスク以外と直接依存関係を有するか否かを判断する（Ｓ１１２０）。依存関係を有しないことを条件に（Ｓ１１２０：ＮＯ）、パス関連処理部５００は、当該第１タスクを含む支配的パスの検出を完了し（Ｓ１１７０）、次の支配的パスを検出するべくＳ１１００に処理を移す。
【００６２】
依存関係を有することを条件に（Ｓ１１２０：ＹＥＳ）、タスク選択部６００は、第１タスクの処理結果に依存する少なくとも１つの第２タスクを選択する（Ｓ１１３０）。選択した第２タスクが、既に他の支配的パスに含まれる場合には（Ｓ１１４０：ＹＥＳ）、タスク選択部６００は、その第２タスクがその支配的パスの始点であるか否かを判断する（Ｓ１１５０）。始点であれば（Ｓ１１５０：ＹＥＳ）、パス検出部６２０は、その支配的パスと検出中の支配的パスとを第２タスクを接点として連結して新たな支配的パスとし（Ｓ１１６０）、他の支配的パスを検出するべくＳ１１００に処理を戻す（Ｓ１１７０）。
【００６３】
もし始点でなければ（Ｓ１１５０：ＮＯ）、タスク選択部６００は、第２タスクを含めない状態で支配的パスの検出を完了し（Ｓ１１７０）、Ｓ１１００に処理を戻す。即ちこれにより、支配的パスから分岐や合流を排除することができる。第２タスクが他の支配的パスに含まれないことを条件に（Ｓ１１４０：ＮＯ）、パス検出部６２０は、その第２タスクが、第１タスクにとって直接依存関係を有する唯一のタスクであるか、または、第２タスクについて算出された上記短縮量が最も大きいかを判断する（Ｓ１１８０）。
【００６４】
このとき、好ましくは、短縮量算出部６１０は、当該第２タスクが処理結果に依存する先行タスクの各々について、当該先行タスクおよび当該第２タスクを異なるプロセッサ・コアで実行した場合のタスク切替時間と比較して、当該第２タスクを当該先行タスクの次に同一のプロセッサ・コアで実行させることにより短縮される短縮量を更に算出する。そして、パス検出部６２０は、複数の先行タスクのうち第１タスクについての短縮量が最も大きいことを更に条件として、当該第２タスクを第１タスクと共に支配的パスに含めて検出する（Ｓ１１９０）。
【００６５】
この判断処理を図１２を用いて説明する。
図１２は、支配的パスを検出する処理の具体例を示す。本図において関数Ｓａｖｅ（）は、タスク切替時間の短縮量を算出するための関数を示す。詳細には、Ｓａｖｅ（Ｔ，Ｓ）は、タスクＴの次にタスクＳを同一のプロセッサ・コアで連続して実行させることによって短縮されるタスク切替時間の短縮幅を示す。
【００６６】
Ｔは、第１タスクを示し、Ｓ１からＳｊの各々は、第１タスクの処理結果に依存する他のタスクを示す。このうちＳｄを第２タスクとする。また、Ｐ１からＰｌの各々はＳｄの先行タスクであり、Ｓｄは、Ｐ１からＰｌの各々の処理結果に依存する。
【００６７】
図１２（ａ）に示すように、パス検出部６２０は、タスクＴの次にタスクＳｄを同一のプロセッサ・コアで連続して実行させた場合の短縮幅Ｓａｖｅ（Ｔ，Ｓｄ）が、タスクＴの次に他の何れのタスクを実行させた場合の短縮幅よりも大きい場合には、タスクＳｄを支配的パスに含めて検出する。
【００６８】
図１２（ｂ）に示すように、短縮量算出部６１０は、第２タスク（Ｓｄ）が処理結果に依存する各々の先行タスク（Ｐ１からＰｌ）について、当該先行タスクおよび当該第２タスクを同一のプロセッサ・コアで実行させることにより短縮される短縮量Ｓａｖｅ（Ｐｉ，Ｓｄ）を更に算出する。そして、パス検出部６２０は、複数の先行タスク（Ｐ１からＰｌ）のうち第１タスク（Ｔ）についての短縮量が最も大きいことを更に条件として、当該第２タスク（Ｓｄ）を第１タスク（Ｔ）と共に支配的パスに含めて検出する。
【００６９】
図１２（ｃ）に、第１タスクについての短縮幅が最大とならない場合を示す。第２タスク（Ｓｄ）が処理結果に依存する各々の先行タスク（Ｐ１からＰｌ）のうち、タスク切替時間の短縮幅が最大となる先行タスクはＰｄであり、第１タスクであるＴとは異なっている。このような場合には、好ましくは、パス検出部６２０は、第２タスク（Ｓｄ）を第１タスク（Ｔ）と同一の支配的パスに含めない（Ｓ１１８０：ＮＯ）。第２タスクは、例えば先行タスク（Ｐｄ）などの他のタスクと同一の支配的パスに含めた方がよいからである。
【００７０】
図１１に戻る。パス検出部６２０は、第２タスクを第１タスクと共に支配的パスに含めて検出する（Ｓ１１９０）。タスク選択部６００は、この第２タスクを新たな第１タスクとして選択し（Ｓ１１９０）、Ｓ１１２０に処理を戻す。
【００７１】
（２）クラスタの生成処理
図１３は、クラスタ関連処理部５１０の機能構成を示す。クラスタ関連処理部５１０は、クラスタ生成部５１５と、循環性依存検出部１３００と、隣接パス選択部１３１０とを有する。循環性依存検出部１３００は、検出された支配的パスの各々について循環性依存を検出する。ある支配的パスにおける循環性依存とは、その支配的パス中の何れかのタスクの処理に依存する他の実行パス中のタスクの処理に、その支配的パス中の他のタスクが更に依存することをいう。
【００７２】
隣接パス選択部１３１０は、検出された支配的パスの各々について、当該支配的パス中の何れかのタスクと直接データ転送するタスクを含む他の支配的パスである隣接パスを選択する。クラスタ生成部５１５は、検出された循環性依存の数がより少ない支配的パスを他の支配的パスよりも優先して選択し、選択した当該支配的パスおよび他のタスクを含めたクラスタを生成する。クラスタ生成部５１５は、検出された循環性依存の数が各支配的パスについて同一であることを条件に、隣接パスの数がより少ない支配的パスを他の支配的パスよりも優先して選択し、選択した当該支配的パスおよび他のタスクを含めたクラスタを生成する。
【００７３】
クラスタ生成部５１５は、候補選択部１３２０と、パス数算出部１３３０と、タスク追加部１３４０と、通信量算出部１３５０と、アイドル割合算出部１３６０とを有する。候補選択部１３２０は、選択した支配的パスについて、その支配的パスと共にクラスタに含めるべきタスクの候補である候補タスクを選択する。パス数算出部１３３０は、その候補タスクを当該支配的パスと共にクラスタに含めた場合において当該クラスタに含まれる支配的パスの総数を算出する。タスク追加部１３４０は、算出された支配的パスの総数が実行コア数以下であることを条件に、当該候補タスクを含めて当該クラスタを生成する。
【００７４】
通信量算出部１３５０は、候補タスクが、当該クラスタ中の複数のタスクの各々と通信する通信量の和を算出する。アイドル割合算出部１３６０は、候補タスクを当該支配的パスと共にクラスタに含めた場合において当該クラスタ中のタスクを実行コア数のプロセッサ・コア数で実行した場合にプロセッサがアイドル状態となる時間の割合を算出する。タスク追加部１３４０は、予め定められた基準よりもその通信量の和が大きいことを更に条件として、その候補タスクを含めてクラスタを生成する。更に好ましくは、タスク追加部１３４０は、予め定められた基準値よりもアイドル状態となる時間の割合が小さいことを更に条件として、当該候補タスクを含めてクラスタを生成する。
【００７５】
図１４は、Ｓ７１０における処理の詳細を示す。循環性依存検出部１３００は、各々の支配的パスについて循環性依存を検出する（Ｓ１４００）。また、隣接パス選択部１３１０は、各々の支配的パスについて隣接パスを選択する（Ｓ１４１０）。クラスタ生成部５１５は、循環性依存の数がより少ない支配的パスから順に、循環性依存の数が同一の場合には隣接パスの数がより少ない支配的パスから順に、順次支配的パスを選択する（Ｓ１４２０）。
【００７６】
クラスタ生成部５１５は、選択した支配的パスに他のタスクを含めてクラスタを生成する（Ｓ１４３０）。まだ選択していない支配的パスが存在する場合には（Ｓ１４４０：ＹＥＳ）、クラスタ生成部５１５は、Ｓ１４２０に処理を戻す。一方で、全ての支配的パスをクラスタとして選択した場合には（Ｓ１４４０：ＮＯ）、クラスタ生成部５１５は、本図の処理を終了する。
【００７７】
図１５は、Ｓ１４００における処理の詳細を示す。Ｓ１４００において、循環性依存検出部１３００は、各々の支配的パスが他の支配的パスとの間に有している循環性依存を検出する。本図においては、この処理のうち、ある支配的パスが他の支配的パスとの間で循環性依存を有するか否かを判定する処理について説明する。具体的には、判定対象の支配的パスを支配的パスＣ１とし、この支配的パスＣ１が、支配的パスＣｘに対して循環性依存を有するか否かを判定する。
【００７８】
まず、循環性依存検出部１３００は、支配的パスＣ１の先頭タスクを選択する（Ｓ１５００）。この先頭タスクをＮｆとする。ｆは、先頭から末尾の順に各々のタスクに付した番号を格納する変数である。即ち、先頭タスクはＮ１となる。
【００７９】
図１６は、循環性依存を検出する処理の対象となるタスクの依存グラフを示す。図１６（ａ）に示すように、ｍ個のタスクから構成される支配的パスＣ１において、先頭タスクから順に末尾タスクに向けて、１からｍまでの番号が付される。
【００８０】
図１５に戻る。循環性依存検出部１３００は、タスクＮｆから支配的パスＣｘ中のタスクに到達する依存パスが存在するか否かを判断する（Ｓ１５１０）。存在しない場合には（Ｓ１５１０：ＮＯ）、循環性依存検出部１３００は、タスクＮｆが支配的パスＣ１の末尾タスクか否かを判断する（Ｓ１５２０）。末尾タスクならば（Ｓ１５２０：ＹＥＳ）、循環性依存検出部１３００は、支配的パスＣ１は支配的パスＣｘに循環性依存を有しないと判断し（Ｓ１５９０）、処理を終了する。
【００８１】
Ｓ１５１０において、タスクＮｆから支配的パスＣｘ中のタスクに到達する依存パスが判断されるが、この到達判断には、タスク間の依存グラフではなく支配的パス間の依存グラフが用いられる。図１６（ｂ）に、支配的パス間の依存グラフを例示し、図１６（ｃ）に、タスク間の依存グラフを例示する。図１６（ｃ）において、タスクＮ２からは、支配的パスＣ３中の何れのタスクにも到達不能である。一方で、図１６（ｂ）においては、支配的パスＣ１の何れのタスクからも、支配的パスＣ３に到達可能である。Ｓ１５１０において、循環性依存検出部１３００は、この支配的パス間の依存グラフに基づいて、依存パスの存在を判断する。
【００８２】
図１５に戻る。一方、タスクＮｆが支配的パスＣ１の末尾タスクで無いならば（Ｓ１５２０：ＮＯ）、循環性依存検出部１３００は、タスクＮｆの後続タスクを選択する。この後続タスクは、例えば、タスクＮｆの次に先頭側に近いタスクであるので、変数ｆに１を加えることで選択できる。後続タスクを新たなタスクＮｆとしてＳ１５１０に処理を戻す。
【００８３】
タスクＮｆから支配的パスＣｘ中のタスクに到達する依存パスが存在することを条件に（Ｓ１５１０：ＹＥＳ）、循環性依存検出部１３００は、最も先頭に近い分岐のタスクをＮｆとして選択する（Ｓ１５３５）。分岐のタスクとは、そのタスクから複数のタスクへの依存パスが存在するタスクである。即ち、分岐のタスクの処理結果には、複数のタスクが依存している。そして、循環性依存検出部１３００は、支配的パスＣ１の末尾タスクをタスクＮｊとして選択する（Ｓ１５４０）。
【００８４】
次に、循環性依存検出部１３００は、支配的パスＣｘ中の何れかのタスクからタスクＮｊに到達するパスが存在するか否かを判断する（Ｓ１５５０）。存在しない場合には（Ｓ１５５０：ＮＯ）、循環性依存検出部１３００は、タスクＮｊは支配的パスＣ１の先頭タスクか否かを判断する（Ｓ１５５５）。例えば変数ｊが１ならばＮｊは先頭タスクである。
【００８５】
先頭タスクであれば（Ｓ１５５５：ＹＥＳ）、循環性依存検出部１３００は、支配的パスＣ１は支配的パスＣｘに循環性依存を有しないと判断し（Ｓ１５９０）、処理を終了する。一方で、先頭タスクでなければ（Ｓ１５５５：ＮＯ）、循環性依存検出部１３００は、タスクＮｊから１つ先頭側のタスクを選択し、これを新たなタスクＮｊとし（Ｓ１５６０）、Ｓ１５５０に処理を移す。
【００８６】
支配的パスＣｘ中の何れかのタスクからタスクＮｊに到達するパスが存在することを条件に（Ｓ１５５０：ＹＥＳ）、循環性依存検出部１３００は、最も末尾に近い合流のタスクをタスクＮｊとして選択する（Ｓ１５７０）。合流のタスクとは、そのタスクに対して複数のタスクからの依存パスが存在するタスクである。即ち、合流のタスクは、複数のタスクの処理結果に依存する。
【００８７】
タスクＮｆがタスクＮｊの祖先であることを条件に（Ｓ１５８０：ＹＥＳ）、循環性依存検出部１３００は、支配的パスＣ１は支配的パスＣｘに循環性依存を有すると判断する（Ｓ１５８５）。ここで、タスクＮｆがタスクＮｊの祖先であるとは、タスクＮｊがタスクＮｆの処理結果に直接的または間接的に依存することをいう。タスクＮｆがタスクＮｊの祖先でないことを条件に（Ｓ１５８０：ＮＯ）、循環性依存検出部１３００は、支配的パスＣ１が支配的パスＣｘに循環性依存を有しないと判断する（Ｓ１５９０）。
【００８８】
図１７は、循環性依存が生じているタスク群の具体例を示す。（ａ）に示すように、支配的パスＣ１中のタスク１は、支配的パスＣ３中のタスク６に対して依存パスを有する。一方で、タスク６は、支配的パスＣ１中のタスク２に対して依存パスを有する。この場合、支配的パスＣ３の実行は支配的パスＣ１の実行に依存し、支配的パスＣ１の実行は支配的パスＣ３の実行に依存する。このような場合には、循環性依存検出部１３００は、支配的パスＣ１が支配的パスＣ３に対して循環性依存を有すると判断する。同様の理由から、循環性依存検出部１３００は、支配的パスＣ１が支配的パスＣ２に対して循環性依存を有すると判断する。
【００８９】
一方で、（ｂ）に示すように、支配的パスＣ１中のタスク１は、支配的パスＣ３中のタスク６に対して依存パスを有する。しかしながら、タスク６は支配的パスＣ１中の何れのタスクにも依存パスを有していない。このような場合には、循環性依存検出部１３００は、支配的パスＣ１が支配的パスＣ３に対して循環性依存を有していないと判断する。
【００９０】
以上、本図の処理によれば、ある支配的パスが他の支配的パスに対して循環性依存を有するか否かを判断することができる。ここで、循環性依存を有する支配的パスの特徴について検討すると、その支配的パスは、相互に依存する他の支配的パスと同一のプロセッサで並列に実行されるべきである。そうしなければ、当該支配的パスおよび当該他の支配的パスとの間で２回以上のコンテクストスイッチが生じ、プログラム全体の実行効率が低下するからである。
【００９１】
本実施例におけるクラスタ関連処理部５１０は、このように、明らかに並列に実行するべき支配的パスの組については、クラスタ生成の優先度を下げ、その他の支配的パスを並列に実行することによりプログラム全体の効率を高める。このため、Ｓ１４２０で説明したように、クラスタ関連処理部５１０は、循環性依存の数が少ない支配的パスから順に順次支配的パスをクラスタとして生成する。これにより、対象プログラム１５の処理の並列性を引き出して効率を高めることができる。
【００９２】
図１８は、Ｓ１４３０における処理の詳細を示す。候補選択部１３２０は、Ｓ１４２０において選択された支配的パスについて、当該支配的パスに含まれる何れかのタスクに直接依存するタスク、または、当該支配的パスに含まれる何れかのタスクが直接依存するタスクを候補タスクとして選択する（Ｓ１８００）。そして、通信量算出部１３５０は、各々の候補タスクについて、当該候補タスクが、当該支配的パスを含むクラスタ中の複数のタスクの各々と通信する通信量の和を算出する（Ｓ１８１０）。
【００９３】
候補選択部１３２０は、これらの候補タスクの中から、算出した通信量の和が大きい順に順次１つずつ候補タスクを選択する（Ｓ１８２０）。パス数算出部１３３０は、その候補タスクを当該支配的パスと共にクラスタに含めた場合において当該クラスタに含まれる支配的パスの総数を算出する（Ｓ１８３０）。タスク追加部１３４０は、算出された支配的パスの総数が実行コア数以下であるか否かを判断する（Ｓ１８４０）。
【００９４】
実行コア数以下であれば（Ｓ１８４０；ＹＥＳ）、アイドル割合算出部１３６０は、候補タスクを当該支配的パスと共にクラスタに含めた場合において当該クラスタ中のタスクを実行コア数のプロセッサ・コア数で実行した場合にプロセッサがアイドル状態となる時間の割合を算出する（Ｓ１８５０）。予め定められた基準値よりもアイドル状態となる時間の割合が小さいことを条件に（Ｓ１８６０：ＹＥＳ）、タスク追加部１３４０は、当該候補タスクを当該支配的パスに含めてクラスタを生成する（Ｓ１８７０）。
【００９５】
そして、候補選択部１３２０は、何れのクラスタにも含まれていないタスクがあれば（Ｓ１８８０：ＹＥＳ）、Ｓ１８２０に処理を戻して次のタスクを選択する。そのようなタスクがなければ（Ｓ１８８０：ＮＯ）、候補選択部１３２０は本図の処理を終了する。一方で、支配的パスの総数が実行コア数より大きいか（Ｓ１８４０：ＮＯ）、または、アイドル時間の割合が基準以上であれば（Ｓ１８６０：ＮＯ）、候補選択部１３２０は、候補タスクをクラスタに含めないと判断して本図の処理を終了する。
【００９６】
（３）プロセッサ・コアの個数の選択
続いて、各々のクラスタの実行のために割り当てるプロセッサ・コアの個数を選択する処理を、図４とは異なる対象プログラムを例として説明する。
図１９は、クラスタ間の依存関係を定めるシリーズパラレル・グラフを、それに含まれるタスクのスケジューリング結果と共に示す。図１９（ａ）は、クラスタ生成部５１５により生成されたクラスタを、それらの間の依存関係と共に示す。具体的には、クラスタ関連処理部５１０は、タスク１１、１２、１５および１６を選択して１つのクラスタを生成している。これをクラスタ１とする。
【００９７】
また、クラスタ関連処理部５１０は、タスク４、５、７および９を選択して１つのクラスタを生成している。これをクラスタ２とする。また、クラスタ関連処理部５１０は、タスク１３、１４、１７および１８を選択して１つのクラスタを生成している。これをクラスタ３とする。また、クラスタ関連処理部５１０は、タスク３、タスク７、タスク６およびタスク１０のそれぞれを、当該タスクのみから構成されるクラスタとして選択している。
【００９８】
クラスタ生成部５１５は、逐次に実行されまたは並列に実行できる、２以上のクラスタをクラスタの上位階層のクラスタ群とし、逐次に実行されまたは並列に実行できる２以上の前記クラスタ群を更に上位階層のクラスタ群としていく。例えば、また、クラスタ間の依存関係を解析したところ、タスク７のみから構成されるクラスタは、クラスタ１に対して依存パスを有する。従って、図１９（ｂ）に示すように、これらのクラスタは、これらのクラスタの上位階層のクラスタ群を形成する。このクラスタ群を、シリーズパラレル・グラフの逐次実行部分と呼ぶ。これを、タスク７およびクラスタ１から成るクラスタ群を逐次実行部分１とする。
【００９９】
また、クラスタ生成部５１５は、逐次実行され、または並列に実行できる２以上のクラスタをそのクラスタの上位階層のクラスタ群とし、逐次実行され、または並列に実行できる２以上のクラスタ群を更に上位階層のクラスタ群としていく。例えば、タスク３のみから構成されるクラスタは、この逐次実行部分１に対しては依存パスを有していない。このため、このクラスタと、この逐次実行部分１とから構成されるクラスタ群は、これらのクラスタおよび逐次実行部分１の上位階層のクラスタ群を形成する。このクラスタ群を、シリーズパラレル・グラフの並列実行部分と呼ぶ。この並列実行部分を、並列実行部分１とする。このようにクラスタ群を形成していくことによって、クラスタ生成部５１５は、複数のクラスタについての階層化された実行順序の依存関係を示すシリーズパラレル・グラフを生成する。
【０１００】
その他も同様に、クラスタ３は、タスク１０のみから構成されるクラスタと共に逐次実行部分２を構成する。また、この逐次実行部分２は、タスク６のみから構成されるクラスタと共に並列実行部分２を形成する。また、本図のクラスタ群が全体で逐次実行部分を形成する。
【０１０１】
図２０は、クラスタ群の階層構造を示す。この階層構造を形成するべく、クラスタ生成部５１５は、複数のクラスタの各々をノードとし、実行順序に依存関係を有する複数のクラスタに対応する複数のノードの上位階層に、当該複数のクラスタが逐次に実行すべき逐次実行部分である旨を示すノードを生成したグラフを生成してもよい。例えば、タスク７を示すノード、および、クラスタ１を示すノードの上位階層には、逐次実行部分１を示すノードが形成される。同様に、クラスタ生成部５１５は、並列に実行可能な複数のクラスタに対応する複数のノードの上位階層に、当該複数のクラスタが並列に実行可能な並列実行部分である旨を示すノードを生成してもよい。
【０１０２】
更に、クラスタ生成部５１５は、実行順序に依存関係を有する複数の並列実行部分または逐次実行部に対応する複数のノードの上位階層に、当該複数の並列実行部分または逐次実行部が更に逐次実行部分である旨を示すノードを生成する。例えば、逐次実行部分１を示すノードの上位階層には、その部分がタスク３と共に形成する並列実行部分を示すノードが生成される。同様に、クラスタ生成部５１５は、並列に実行可能な複数の並列実行部分または逐次実行部に対応する複数のノードの上位階層に、当該複数の並列実行部分または逐次実行部分が並列実行部分である旨を示すノードを生成してもよい。
なお、シリーズパラレル・グラフの詳細については、上述の非特許文献２および３に説明されている。
【０１０３】
図１９に戻る。コア数選択部５３０は、これらの逐次実行部分、および、並列実行部分の実行時間をより短縮するべく、各々のクラスタの実行のために割り当てるプロセッサ・コアの個数を動的計画法によって選択する。動的計画法の部分問題は、逐次実行部分および並列実行部分の各々の実行時間を最適にするために当該部分を構成するクラスタ、逐次実行部分または並列実行部分の各々に割り当てるプロセッサ・コアの個数を選択する問題となる。そして、コア数選択部５３０は、各々の部分問題を動的計画法によって解くことにより、対象プログラム１５の実行時間を最適にするために各々のクラスタに割り当てるプロセッサ・コアの個数を選択する。
【０１０４】
処理の手順としては、下位階層のクラスタ群から順に部分問題が解かれる。即ち、コア数選択部５３０は、下位階層の前記クラスタ群から順に、プロセッサ・コアの個数以下の自然数の中から選択した１つまたは複数の自然数の各々について、下位階層のクラスタ群の実行時間を短縮すべく、下位階層のクラスタ群の更に下位階層に位置する並列実行可能な２以上のクラスタまたはクラスタ群に割り当てるべきプロセッサ・コアの個数を選択していく。
【０１０５】
本図の例においては、コア数選択部５３０は、逐次実行部分１を１つのプロセッサ・コアで実行した実行時間を算出し、逐次実行部分１を２つのプロセッサ・コアで実行した実行時間を算出する。２つのプロセッサ・コアで実行した実行時間の方が、１つのプロセッサ・コアで実行した実行時間よりも短くなると考えられる。また、プログラムの性質上、逐次実行部分１の最大並列度が２であるので、プロセッサ・コア数が２以上の場合は同一の実行時間となる。
【０１０６】
次に、コア数選択部５３０は、並列実行部分１の実行時間を算出する。プロセッサ・コア数が１の場合には、コア数選択部５３０は、逐次実行部分１を１つのプロセッサ・コアで実行する場合について既に求めた実行時間に、タスク３を実行する実行時間を加えることにより、並列実行部分１の実行時間を算出する。プロセッサ・コア数が２や３以上の場合には、コア数選択部５３０は、逐次実行部分１について既に求めた実行時間を用いて、並列実行部分１の実行時間を算出する。
【０１０７】
例えば、プロセッサ・コア数が３の場合には、逐次実行部分１を１つのプロセッサ・コアで実行し、それと並行に、タスク３を２つのプロセッサ・コアで実行した実行時間を求める。また、逐次実行部分１を２つのプロセッサ・コアで実行し、それと並行に、タスク３を１つのプロセッサ・コアで実行した実行時間を求める。これらの実行時間のうち短い方の実行時間を、並列実行部分１の実行時間とする。
【０１０８】
コア数選択部５３０は、このように各々の部分の実行時間を算出して、最後に、クラスタ群全体から構成される逐次実行部分を実行コア数で実行した場合の実行時間を算出する。この実行時間を算出した場合において、各々のクラスタに割り当てられたプロセッサ・コア数が、各々のクラスタの実行に割り当てるべきプロセッサ・コア数となる。
【０１０９】
以上の実施例によれば、コンパイラ２０は、対象プログラム１５をマルチコアで効率的に実行させることができる。即ち、第１に、パス関連処理部５００は、同一のプロセッサ・コアで実行した場合に利得の大きい実行パスを支配的パスとして検出する。第２に、クラスタ関連処理部５１０は、複数の支配的パスを、並列に実行できる数を上限として選択し、連続にまたは並列に実行するべきクラスタを生成する。このとき、クラスタ内外で通信する通信量はできるだけ少なくし、循環性依存を有する支配的パスはクラスタ生成の優先度を低下させる。これによって、コア数選択部５３０による動的計画法の適用を可能とし、プログラム全体を効率的に実行できるようにタスクをスケジューリングできる。
【０１１０】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【０１１１】
【図１】図１は、分散メモリ型のマルチコア・マイクロプロセッサ１０の構成を示す。
【図２】図２は、コンパイラ２０および情報処理システム３０の全体構成を示す。
【図３】図３は、情報処理システム３０のハードウェア構成の一例を示す。
【図４】図４は、対象プログラム１５の一例を示す。
【図５】図５は、コンパイラ２０の機能構成を示す。
【図６】図６は、性能情報記録部５０５のデータ構造の一例を示す。
【図７】図７は、コンパイラ２０が対象プログラム１５をコンパイルする処理全体の流れを示す。
【図８】図８は、対象プログラム１５に含まれる複数のタスクがスケジューリングされる処理過程を示す（２図のうち１図目）。
【図９】図９は、対象プログラム１５に含まれる複数のタスクがスケジューリングされる処理過程を示す（２図のうち２図目）。
【図１０】図１０は、パス関連処理部５００の機能構成を示す。
【図１１】図１１は、Ｓ７００における処理の詳細を示す。
【図１２】図１２は、支配的パスを検出する処理の具体例を示す。
【図１３】図１３は、クラスタ関連処理部５１０の機能構成を示す。
【図１４】図１４は、Ｓ７１０における処理の詳細を示す。
【図１５】図１５は、Ｓ１４００における処理の詳細を示す。
【図１６】図１６は、循環性依存を検出する処理の対象となるタスクの依存グラフを示す。
【図１７】図１７は、循環性依存が生じているタスク群の具体例を示す。
【図１８】図１８は、Ｓ１４３０における処理の詳細を示す。
【図１９】図１９は、クラスタ間の依存関係を定めるシリーズパラレル・グラフを、それに含まれるタスクのスケジューリング結果と共に示す。
【図２０】図２０は、クラスタ群の階層構造を示す。
【符号の説明】
【０１１２】
１５  対象プログラム
２０  コンパイラ
３０  情報処理システム
１０  プロセッサ
１００  プロセッサ・コア
１１０  局所メモリ
１２０  ＤＭＡエンジン
１３０  サポートプロセッサ
１４０  オンチップバス
１５０  オフチップバス
５００  パス関連処理部
５０５  性能情報記録部
５１０  クラスタ関連処理部
５１５  クラスタ生成部
５２０  実行時間算出部
５３０  コア数選択部
６００  タスク選択部
６１０  短縮量算出部
６２０  パス検出部
１０２０  メイン・メモリ
１３００  循環性依存検出部
１３１０  隣接パス選択部
１３２０  候補選択部
１３３０  パス数算出部
１３４０  タスク追加部
１３５０  通信量算出部
１３６０  アイドル割合算出部
【図１】
2007048052.tif 000003
【図２】
2007048052.tif 000004
【図３】
2007048052.tif 000005
【図４】
2007048052.tif 000006
【図５】
2007048052.tif 000007
【図６】
2007048052.tif 000008
【図７】
2007048052.tif 000009
【図８】
2007048052.tif 000010
【図９】
2007048052.tif 000011
【図１０】
2007048052.tif 000012
【図１１】
2007048052.tif 000013
【図１２】
2007048052.tif 000014
【図１３】
2007048052.tif 000015
【図１４】
2007048052.tif 000016
【図１５】
2007048052.tif 000017
【図１６】
2007048052.tif 000018
【図１７】
2007048052.tif 000019
【図１８】
2007048052.tif 000020
【図１９】
2007048052.tif 000021
【図２０】
2007048052.tif 000022