(57)【要約】【課題】スレッド間の依存関係を固定的に実装する必要の無いマルチスレッド処理を実現する情報処理装置、プログラム処理方法及びコンピュータプログラムを提供する。【解決手段】プログラムモジュール同士の並列処理の関係を記述した並列実行制御記述から、個々の前記プログラムモジュールに関連する部分を抽出した先行情報と後続情報を含むグラフデータ構造生成情報に基づいて所定のプログラムモジュールを抽出し、これを依存関係に従ってグラフデータ構造に追加更新し、先行するノードすべてが処理済であるノードから実行する処理方法とする。【選択図】      図２
2010009495.tif 000002
【特許請求の範囲】
【請求項１】
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
を具備することを特徴とする情報処理装置。
【請求項２】
前記実行手段は制限幅を変更して幅優先探索を実施した時のプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記実行手段はあるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施することを特徴とする請求項１記載の情報処理装置。
【請求項４】
前記実行手段は深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施した時のプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施することを特徴とする請求項１記載の情報処理装置。
【請求項５】
前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新手段をさらに具備することを特徴とする請求項１記載の情報処理装置。
【請求項６】
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを用いるプログラム処理方法であって、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換ステップと、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加ステップと、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納ステップと、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行ステップと、
を具備することを特徴とするプログラム処理方法。
【請求項７】
前記実行ステップは制限幅を変更して幅優先探索を実施した時のプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施することを特徴とする請求項６載のプログラム処理方法。
【請求項８】
前記実行手段はあるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施することを特徴とする請求項６記載のプログラム処理方法。
【請求項９】
前記実行ステップは深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施した時のプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施することを特徴とする請求項６記載のプログラム処理方法。
【請求項１０】
前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新ステップをさらに具備することを特徴とする請求項６記載のプログラム処理方法。
【請求項１１】
複数のプロセッサに並列処理を行わせるためのコンピュータプログラムであって、
コンピュータを、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
して機能させるためのコンピュータプログラム。
【請求項１２】
コンピュータに前記実行手段として、制限幅を変更して幅優先探索を実施した時のプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施させることを特徴とする請求項１１記載のコンピュータプログラム。
【請求項１３】
コンピュータに前記実行手段として、あるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施させることを特徴とする請求項１１記載のコンピュータプログラム。
【請求項１４】
コンピュータに前記実行手段として、深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施した時のプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施させることを特徴とする請求項１１記載のコンピュータプログラム。
【請求項１５】
コンピュータを前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新手段をさらに機能させることを特徴とする請求項１１記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は並列処理のための情報処理装置、プログラム処理方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
計算機の処理の高速化を実現するために複数の処理を並列に行うマルチスレッド処理がある。従来のマルチスレッドによる並列処理プログラムでは複数のスレッドが生成され、それぞれのスレッドが同期処理を意識したプログラミングを強いられていた。例えば、実行順序を適切に保つためにはプログラムのさまざまな場所に同期を保証する処理を挿入する必要があり、プログラムのデバッグが困難になる等、メンテナンスコストが押し上げられていた。
【０００３】
このような並列処理プログラムの一例としては特許文献１に記載のマルチスレッド実行方法がある。ここでは依存関係のある複数のスレッド（スレッド１はスレッド２の終了後でなければ実行できない等）を生成したとき、そのスレッドの実行結果とスレッド間の依存関係に基づいて並列処理を実現する方法が開示されている。
【特許文献１】特開２００５−２５８９２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この手法ではスレッド間の依存関係を固定的に実装する必要があるため、プログラム変更の柔軟性に欠ける、スレッド間の同期処理の記述が困難である、あるいはプロセッサ数のスケーラビリティを得にくいという問題があった。
【０００５】
本発明の目的はスレッド間の依存関係を固定的に実装する必要の無いマルチスレッド処理を実現する情報処理装置、プログラム処理方法及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明の一態様による情報処理装置は、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
を具備するものである。
【０００７】
本発明の一態様によるプログラム処理方法は、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを用いるプログラム処理方法であって、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換ステップと、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加ステップと、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納ステップと、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行ステップと、
を具備するものである。
【０００８】
本発明の一態様によるコンピュータプログラムは、
複数のプロセッサに並列処理を行わせるためのコンピュータプログラムであって、
コンピュータを、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
して機能させるものである。
【発明の効果】
【０００９】
以上説明したように本発明によれば、スレッド間の依存関係を固定的に実装する必要が無いため、プログラム変更の柔軟性に優れ、スレッド間の同期処理の記述が容易である、あるいはプロセッサ数のスケーラビリティを得やすいという効果がある。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照して本発明による情報処理装置、プログラム処理方法及びコンピュータプログラムの実施の形態を説明する。
【００１１】
図１は本発明の第１の実施の形態に係る情報処理装置の構成の一例を示す図である。図１では並列処理を実現するための多数のプロセッサ１００ｉ（ｉ＝１，２，…）、メインメモリ１０１、ハードディスクドライブ（ＨＤＤ）１０２及び内部バス１０３が示されている。プロセッサ１００ｉはメインメモリ１０１やＨＤＤ１０２等の種々の記憶装置に記憶したプログラムコードを解釈し、プログラムとしてあらかじめ記述された処理を実行する機能を有する。図１では互いに同等の処理能力のプロセッサ１００ｉが３つ設けられていると想定するが、必ずしも同等のプロセッサである必要はなく、それぞれで処理能力が異なるものや、別種のコードを処理するプロセッサが含まれていてもかまわない。
【００１２】
メインメモリ１０１は例えばＤＲＡＭ等の半導体メモリで構成された記憶装置を指す。プロセッサ１００ｉが処理するプログラムは処理前に比較的高速にアクセス可能なメインメモリ１０１上に読み込まれ、プログラム処理に従ってプロセッサ１００ｉからアクセスされる。
【００１３】
ＨＤＤ１０２はメインメモリ１０１に比べて大容量のデータを記憶できるが、アクセス速度において不利である場合が多い。プロセッサ１００ｉが処理するプログラムコードはＨＤＤ１０２に記憶しておき、処理する部分のみをメインメモリ１０１上に読み出すように構成される。
【００１４】
内部バス１０３はプロセッサ１００ｉ、メインメモリ１０１及びＨＤＤ１０２を相互に接続し、互いにデータの授受ができるように構成した共通バスである。
【００１５】
また、図示していないが処理結果を出力するための画像表示装置あるいは処理データを入力するためのキーボードなどの入出力装置を備えていてもかまわない。
【００１６】
次に、本実施形態に係る並列処理プログラムの概略を説明する。
【００１７】
図２は従来の並列処理プログラムの処理フローの一例を示す図である。図２はプログラム３００（プログラムＡ）、プログラム３０１（プログラムＢ）、プログラム３０２（プログラムＡ）の複数のプログラムが並行して処理されている模式図を示している。
【００１８】
プログラム同士はそれぞれ無関係に処理されているわけではなく、他のプログラムの処理結果を自身の処理に使用する場合、あるいはデータの整合性を確保するという理由で他のプログラムの特定部分の処理が終わるのを待たねばならないことがある。このような特性を持つプログラムを並列に処理する場合、プログラムの各所に他のプログラムの実行状況を知得するための仕組みを埋め込まねばならない。この仕組み（同期処理とも呼ばれる）を埋め込むことによってプログラム間でデータ保証や、排他制御を実現し協調動作するように構成していた。
【００１９】
たとえばプログラム３００の処理中に所定のイベントが発生したとき、プログラム３０１に対してなんらかの処理をするように依頼する（イベント３０３）。プログラム３０１はイベント３０３を受けて所定の処理を実行し、所定の条件が成立したときさらにイベント３０４をプログラム３０２に発行する。プログラム３０１はイベント３０３によってプログラム３００から受けた処理の結果をイベント３０５としてプログラム３００に応答する。
【００２０】
しかしながら、プログラム自身に並列処理における同期処理を実現するための記述をした場合、本来のロジックとは別の配慮が必要となりプログラムが複雑になってしまう。また、他のプログラムの処理終了を待つ間、無駄にリソースを消費することにもなる。さらにはちょっとしたタイミングのずれによって処理効率が大きく変動するなど、後からのプログラム修正が困難になる場合が多い。
【００２１】
これに対して、本実施形態ではプログラムを、他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となり、直列かつ同期処理無しで実行する基本モジュール（直列実行モジュールとも呼ばれる）と、基本モジュールをノードとしてグラフデータ構造生成情報を用いて複数の基本モジュールの並列処理の関係を記述する並列実行制御記述とに分割する。同期やデータの授受の必要のある部分は並列実行制御記述で記述することによって、基本モジュールの部品化を促進し、かつ、並列実行制御記述をコンパクトに管理できるようにする。
【００２２】
図３は本実施形態に係るプログラムの分割方法の一例を説明する図である。図３は相互に同期処理をするプログラム４００(プログラムＤ)及びプログラム４０１(プログラムＥ)を示している。
【００２３】
プログラム４００がスレッド４０２を、プログラム４０１がスレッド４０７を実行している。プログラム４００はポイント４０６までスレッド４０２を実行すると、その処理結果をプログラム４０１に受け渡す必要がある。このためプログラム４００はスレッド４０２の実行を終了すると、処理結果をイベント４０４としてプログラム４０１に通知する。プログラム４０１はイベント４０４とスレッド４０７の処理結果との両方が揃ったとき、初めてスレッド４０５を実行可能である。一方、プログラム４００はスレッド４０２の実行の終了を受けて、ポイント４０６以降のプログラムをスレッド４０３として実行する。
【００２４】
このようにプログラム４００、４０１にはスレッド４０２、４０７のように無条件に処理を進めて良い部分と、ポイント４０６のようにプログラムを処理していく間に他のスレッドに通知すべきある処理結果が得られるポイント、あるいは他のスレッドからの処理結果を得ることが処理開始の条件となっているポイントなどが存在する。
【００２５】
そこで、図３に示すように、ポイント４０６のようなポイントでプログラムを分割し、分割後のプログラムの処理単位をそれぞれ基本モジュールｄ１、ｄ２、ｄ３、…、基本モジュールｅ１、ｅ２、ｅ３、…と定義する。図３では相互に関連する２つのプログラムＤ、Ｅが示されているが、それ以上の数の相互に関連するプログラムがあっても同様の考え方で分割可能である。基本モジュールｄ１、ｄ２、ｄ３、…、基本モジュールｅ１、ｅ２、ｅ３、…が同期処理無しで実行できる直列実行モジュールである。
【００２６】
図４は本実施形態に係る基本モジュールの依存関係の一例を説明するグラフデータ構造を示す図である。モジュールの依存関係とはモジュール＃１はモジュール＃２の終了後でなければ実行できない等の関係である。図４の丸印である基本モジュール５００は図３で説明した基本モジュールｄ１、ｄ２、…、ｅ１、ｅ２、…のいずれかを表す。一番最初に実行される基本モジュール５００は他のスレッドに関係なく無条件に進めて良いモジュール化されたプログラムが割当てられる。基本モジュール５００は他の基本モジュールとの依存関係を示すリンク５０１に基づいて他の基本モジュールと関連付けられている。
【００２７】
図４の依存関係は各基本モジュールはリンク５０１によって関連を定義された先行基本モジュールからの計算結果出力のようなイベントを受け、同時にリンクにより関連を定義された後続基本モジュールへのイベントを発生させることを示している。複数のリンクが入っている基本モジュールでは自身の処理のために複数の入力データ等が必要であることを示している。
【００２８】
図５は本実施形態に係るプログラムのトランスレーションの一例を示す図である。
【００２９】
多数の基本モジュール２００ｊ（ｊ＝１，２，…）は本実施形態に係るシステムで実行するプログラムである。基本モジュール２００ｊは１つ以上のパラメータ１９８を受け取り可能に構成され、このパラメータ１９８の値に基づき、例えば適用するアルゴリズムを変更したり、アルゴリズム上の閾値や係数を変更すること等により、実行負荷を調整できるようになっている。
【００３０】
並列実行制御記述２０１は実行する際に参照されるデータである。並列実行制御記述２０１は基本モジュール２００ｊ各々の並列処理時の依存関係（図４）を示しており、情報処理装置２０３で実行される前にトランスレータ２０２によってグラフデータ構造生成情報２０４に変換される。トランスレータ２０２は並列実行制御記述から複数の基本モジュールの各々に関連する部分を抽出し、並列実行制御記述を少なくとも基本モジュールに先行する基本モジュールの情報と後続する基本モジュールの情報とを含むグラフデータ構造生成情報を生成する。グラフデータ構造生成情報２０４はランタイムライブラリ２０６内に格納される。
【００３１】
トランスレータ２０２は基本モジュール２００を処理する前に事前に変換する場合以外にも、基本モジュール２００の実行中、ランタイムタスク等によって逐次トランスレートしながら処理する方法も考えられる。
【００３２】
情報処理装置２０３上の実行時点のソフトウェアは基本モジュール２００ｊ、ランタイムライブラリ２０６（グラフデータ構造生成情報２０４を格納する）、マルチスレッドライブラリ２０８、オペレーティングシステム２１０から構成される。
【００３３】
ランタイムライブラリ２０６は基本モジュール２００ｊを情報処理装置２０３上で実行する際のAPI（Application Interface）などを含み、また基本モジュール２００ｊを並列処理する際に必要となる排他制御を実現するための機能を有する。一方、ランタイムライブラリ２０６からトランスレータ２０２の機能を呼び出すように構成し、基本モジュール２００の処理の過程で呼び出されるとき、次に処理する部分の並列実行制御記述２０１をその都度変換するようにしても良い。このように構成すれば、トランスレートするための常駐タスクが不要になり、並列処理をよりコンパクトに構成できる。
【００３４】
オペレーティングシステム２１０は情報処理装置２０３のハードウェアやタスクのスケジューリングなど、システム全体を管理している。オペレーティングシステム２１０を導入することで、基本モジュール２００を実行する際、プログラマはシステムの雑多な管理から開放され、プログラミングに専念できるとともに、一般的に機機種でも稼動可能なソフトウェアを開発できるというメリットがある。
【００３５】
本実施形態に係る情報処理装置では同期処理やデータの授受の必要な部分でプログラムを分割し、その間の関連を並列実行制御記述として定義することで、基本モジュールの部品化を促進し、並列処理定義をコンパクトに管理することができる。部品化した各基本モジュールの実行負荷は動的に調整可能である。
【００３６】
図５に示すように、並列実行制御記述２０１をグラフデータ構造生成情報２０４に一旦変換し、これを解釈実行するランタイムを並列に実行させることによって、オーバーヘッドの低減を図り、かつプログラミングの柔軟性を確保することができる。このランタイム処理は少なくともプロセッサコアの数よりも多数のスレッドによって実行し、動的に生成されるグラフデータ構造を解釈して、実行するべき基本モジュール２００ｊを選択し、グラフデータ構造を更新しながら基本モジュール２００ｊの実行を繰り返すことによって、並列処理を実現する。
【００３７】
図６は図４に示すグラフデータ構造の基本構成要素であるノード６００のデータ構造の一例を説明する図である。ノードは基本モジュールに対応しており、図５の並列実行制御記述２０１をトランスレータ２０２でグラフデータ構造生成情報２０４に変換した後の情報に基づいて基本モジュール２００ｊをグラフデータ構造化したものである。ノード６００はリンクにより他のノードと依存関係を有している。ノード６００は基本モジュールの並列実行指定プログラムによって自動生成され、リンク数や結合子の数はモジュールの種別毎に決まった値となる。このグラフデータ構造は入力データ（あるいは出力リクエスト）のタイプごとに追加するべきノードと接続先の関係を表現したグラフデータ構造生成情報２０４を元にランタイムが動的に生成する。
【００３８】
図６（ａ）に示すように、ノード６００は基本モジュールが動作するときに参照するデータを生成する基本モジュールへの複数のリンク６０１を持ち、この基本モジュールが生成したデータを将来参照することになる基本モジュールが接続するための複数の結合子６０２を持つ。リンク６０１はノード６００が所定の処理を実行するのに必要なデータを得るために必要な他のノードの出力端に結合されるリンクである。リンク６０１のそれぞれはどのような出力端とのリンクが必要か等の定義情報を持っている。
【００３９】
結合子６０２はノード６００が処理後に出力するデータがいかなるものであるかを示す識別情報を備えている。後続のノードはこの結合子６０２の識別情報と並列実行制御記述２０１とに基づいて自身が実行可能な条件がそろったか否かを判断することができる。
【００４０】
ノード６００はランタイムライブラリ２０６により実行可能な条件がそろったとみなされると、図６（ｂ）に示すようにノードの単位でノードのＩＤ（あるいは基本モジュールＩＤ）が実行可能プール６０３に格納され、プール６０３内のノードの中から次に実行すべきノードＩＤが選択されて取り出され、処理される。実行可能プール６０３はノードＩＤが順次入力され、その中のいずれかのノードＩＤが任意に取り出される一種のレジスタである。
【００４１】
図７は本実施形態に係るノードのグラフデータ構造生成情報２０４の一例を示す図である。図７には並列実行制御記述２０１から基本モジュール毎にトランスレートされたグラフデータ構造生成情報２０４１、２０４２、…が示されている。情報としては基本モジュールＩＤ、先行ノードへの複数のリンク情報、当該ノードの出力バッファの種別、及び当該ノードの処理コストが含まれる。コスト情報は当該ノードに対応する基本モジュール２００の処理に係るコストを示している。この情報は実行可能プール６０３に格納されたノードのうち、次に取り出すノードを選択する際に考慮される。
【００４２】
先行ノードへのリンク情報には当該ノードの先行ノードとなるべきノードの条件が定義されている。たとえば所定のデータタイプを出力するノード、特定のＩＤを持つノードなどの定義が考えられる。
【００４３】
グラフデータ構造生成情報２０４は対応する基本モジュール２００をノードとして表現するとともに、リンク情報などに基づいて図４に示すような既存のグラフデータ構造にこの基本モジュールを追加するための情報として用いる。
【００４４】
図８は本実施形態に係るグラフデータ構造の追加処理フローの一例を示す図である。図８の処理はプロセッサ１００ｉの何れかで実行される。
【００４５】
このフローを実行すると、先行ノードが実行完了していればグラフデータ構造生成情報２０４に基づいてその時々に実行可能なノードを生成し、実行可能プール６０３に格納する。
【００４６】
マルチスレッド処理を管理するランタイムライブラリ２０６は処理対象となる入力データを受け付ける（ステップＳ０１）。
【００４７】
ランタイムライブラリ２０６は各コアから呼び出されてマルチスレッド処理を実行するように動作環境を設定する。これにより、ランタイムが主体となって動作するモデルから、各コアが主体となって動作するモデルとして並列プログラムを捉えることができ、ランタイムのオーバーヘッドを小さくすることで、並列処理における同期待ちを小さく抑えることが可能となる。もし、唯一のライタイムタスクが基本モジュールを呼び出すように動作環境を構成すると、基本モジュールを実行するタスクとランタイムタスクの切換えが煩雑に実行されるのでオーバーヘッドが増大する。
【００４８】
ランタイムライブラリ２０６は入力データの有無を判断し（ステップＳ０２）、入力データが無ければ（Ｎｏ）この一連の処理フローを終了する。
【００４９】
ステップＳ０２で入力データがある場合（Ｙｅｓ）、この入力データを入力とするグラフデータ構造生成情報２０４を抽出してこれらを取得する（ステップＳ０３）。
【００５０】
基本モジュール２００の出力データはあらかじめグラフデータ構造生成情報２０４の出力バッファ種別に記載すべき複数のタイプに分別されている。入力データを入力とするグラフデータ構造生成情報２０４の抽出にあたってはグラフデータ構造生成情報２０４に記載の先行ノードへのリンク情報に含まれる入力データとなるべきデータタイプに基づき、このデータタイプが先の入力データと一致するものを抽出すればよい。
【００５１】
次に、ステップＳ０３で取得したグラフデータ構造生成情報２０４に対応するノードを生成する（ステップＳ０４）。
【００５２】
ここで複数のグラフデータ構造生成情報２０４が抽出された場合には複数のそれぞれに対応するノードが生成される。
【００５３】
生成したノードは次に既存のグラフデータ構造に追加される（ステップＳ０５）。ここでいう既存のグラフデータ構造とはグラフデータ構造生成情報２０４から生成されたノードの先行ノードへのリンク情報と出力バッファタイプに基づいて、生成済みノードの前後の依存関係を、たとえば図４に示すように構造化したものである。
【００５４】
次に、既存のグラフデータ構造に含まれる、追加したノードの先行ノードにあたる全てのノードの処理が完了したかどうかを判断する（ステップＳ０６）。
【００５５】
あるノードについてすべての先行ノードが完了しているならば（Ｙｅｓ）、このノードが実行開始のための条件が整ったとみなし、このノードを実行可能プール６０３に格納する（ステップＳ０７）。
【００５６】
一方、依然として処理が完了していない先行ノードがある場合（Ｎｏ）、自身の処理を始めることが出来ず、フローは終了する。
【００５７】
このようにノードが生成されても、そのノードに対応する基本モジュールがすぐに実行されるわけではなく、追加されたグラフデータ構造の他のノードとの依存関係が満たされるまでその処理は保留される。
【００５８】
図９は本実施形態に係る基本モジュール処理の一例を示す図である。このフローでは実行可能プール６０３に格納されたノードを選択的に読み出して対応する基本モジュールを実行する例を示している。図９の処理もプロセッサ１００ｉの何れかで実行される。
【００５９】
実行可能プール６０３に格納されている実行可能となっているノードのうちから所定の条件に基づいて次に実行すべきノードを選択する（ステップＳ１１）。
【００６０】
所定の条件とはたとえば、格納された最も古いノード、後続ノードが多いノードあるいはコストの高いノードなどの基準に基づいて選択することができる。
【００６１】
各ノードのコストを次のように計算して求めても良い。
【００６２】
追加ノードのコスト  ＝  （  α  ×  過去の平均実行時間  ）
＋（  β  ×  出力バッファの使用量  ）
＋（  γ  ×  後続ノード数  ）
＋（  δ  ×  非スケジュール時の実行頻度  ）
一般的にはコストが高いノードから処理していく方が、並列処理のスループットが上がると考えられる。ここで非スケジュール時の実行頻度とはその基本モジュールが実行中に、実行可能プール６０３にいずれのノードも格納されていない状況が出現する頻度をいう。この状況は実行可能プール６０３のアンダーフローが発生したことを意味し、基本モジュール２００の並列処理度が低下するため好ましくない。このときに実行中の基本モジュール２００はコストがより高く算出されることから早めに処理されボトルネック回避に効果が期待できる。
【００６３】
コスト計算式の一次式の各係数α〜δはあらかじめ定めた値を使用しても良いし、処理の状況を見ながら動的に変化するように構成しても良い。
【００６４】
ノードの取得の一例は後述する。
【００６５】
次に実行すべきノードを取得したら、次にこのノードの処理結果を格納する出力用バッファを実行前に確保する（ステップＳ１２）。
【００６６】
出力用バッファはグラフデータ構造生成情報２０４で定義された出力バッファタイプの定義に基づいて確保される。
【００６７】
出力用バッファが確保できると、このノードに対応する基本モジュールの前回の実行時に取得されて保存された性能情報に基づき、当該基本モジュールが受け取り可能な１つ以上のパラメータの値を設定し（ステップＳ１３）、このノードに対応する基本モジュール２００の実行を開始する（ステップＳ１４）。
【００６８】
そして、当該基本モジュール２００が処理を終了すると、その性能情報を取得して保存し（ステップＳ１５）、グラフデータ構造内の当該ノードの実行済みフラグを処理済に設定する（ステップＳ１６）。
【００６９】
ステップＳ１５では処理を終了した基本モジュール２００のパラメータと実行時間との組を性能情報として記録する。
【００７０】
次に、当該ノードのグラフデータ構造に含まれる後続ノードがすべて処理済となっているか否かを判断する（ステップＳ１７）。後続ノードのすべてが処理済であれば（Ｙｅｓ）当該ノードをグラフデータ構造から削除することができる（ステップＳ１８）。このとき、当該ノードの出力データも使用することがないのでステップＳ１２で確保した出力用バッファも開放される。逆に後続ノードのうちまだ処理済でないものがあれば、当該ノードの出力データを後続ノードの基本モジュールで使用する可能性があるため、グラフデータ構造から削除してはいけない。
【００７１】
次に、グラフデータ構造に含まれるすべてのノードそれぞれについて、そのノードの先行ノードすべてが処理済となっているか否かを判断する（ステップＳ１９）。先行ノードのすべてが処理済となっているノードがあれば（Ｙｅｓ）、当該ノードは実行開始条件が整ったとみなし実行可能プール６０３に格納する（ステップＳ２０）。
【００７２】
先行ノードの一つでも処理済でないノードは（Ｎｏ）、その先行ノードの処理が終了時点で再度判断されることになる。
【００７３】
以上説明したように、ランタイムが入力を受け付けると、入力データのタイプに対応したグラフデータ構造生成情報２０４である「ノードと接続先の組」（図７）のリストを得て、このリストに従ってノードを既存のグラフデータ構造（図４）に追加していく。ノードのグラフデータ構造への追加が完了すると、そのノードの先行ノードがすべて実行完了済みであれば、追加したノードを実行可能プール６０３に追加する。ランタイムによる基本モジュールの実行は各プロセッサコアで実行しているスレッドがそれぞれ自立的に実行モジュールを選択してグラフデータ構造をアップデートして処理を行うことによって並列処理を実現する。
【００７４】
基本モジュール選択とグラフデータ構造のアップデート処理では排他制御が必要になるが、これはランタイムが行うので、並列プログラム設計者は排他制御を意識することはない。
【００７５】
基本モジュールは同期処理を含まないので、直列に最後まで実行され、実行が終わると、ランタイムに戻ってくる。
【００７６】
次に、ステップＳ１１における実行すべき基本モジュールの選択手法について説明する。
【００７７】
本実施形態では、並列処理は直列実行する基本モジュールと、基本モジュールを複数のプロセッサに順序良く割り当てるランタイム処理から構成される。ランタイム処理の処理時間の短縮が所望されており、この処理時間はキャッシュミスの発生に依存する。そのため、キャッシュミスの発生状況を観測し、観測結果に基づき次に実行すべきノードをどのプロセッサに割り当てるかを適切に決定することによって、ランタイム処理時間を短縮することができる。
【００７８】
本実施形態はシステムのメモリ階層を限定するものではないが、説明の便宜上、図１０に示すように３段階のキャッシュメモリ階層を持つものと仮定する。Ｌ１キャッシュ１１４はプロセッサ１００内にそれぞれ設けられ、ＣＰＵ１１２とそれぞれ接続される。プロセッサ１００とメインメモリ１０１との間にはＬ２キャッシュ１１６が設けられる。Ｌ１キャッシュ１１４とＬ２キャッシュ１１６はハードウェアによる同期機構を持ち、同一アドレスへのアクセスの際に必要な同期処理が行われる。Ｌ２キャッシュ１１６はＬ１キャッシュ１１４で参照されるアドレスのデータを保持し、キャッシュミスが生じた場合などにはハードウェアによる同期機構により、メインメモリ１０１との間で必要な同期処理が行われる。
【００７９】
図１１はある並列処理の実行時のノードの連なり状態を示す。ここでは、簡単のため木構造で記述しているが、図４に示すようなグラフデータ構造で記述してもよい。図の上下方向は依存関係を示し、ノードＡの下方向にノードＢ、Ｃが連結されている場合、ノードＡはノードＢまたはＣに依存することを示す。ノードＡの処理はノードＢ、Ｃの処理が終わらないと開始できない。関係の記述に関しては、ノードＡはノードＢ、Ｃの親と呼び、ノードＢ、ＣはノードＡの子と呼び、ノードＢとＣを互いに兄弟と呼ぶ。数字（＃）はノードに対応する基本モジュールを実行するＣＰＵの番号を示す。未実行のノードは白抜き、実行済みのノードは両方向の斜線、実行中のノードは一方向の斜線付の丸である。ここでは、３つのノードＢ、Ｃ、ＤがそれぞれＣＰＵ＃１、＃２、＃３により並列処理されることを示している。
【００８０】
あるＣＰＵがあるノードの処理を完了した場合、次に実行すべきノードを探索する手法には深さ優先探索と幅優先探索とがある。
【００８１】
幅さ優先探索とは、最上位のノードまで探索し、最上位のノードからなるべく近くのノードを探索しつつ最下位の未実行のノードまで辿る探索である。一方、深さ優先探索とは、木構造において上位方向へ探索していき、各ノードで子ノードが未実行であるか否か判断し、未実行の子ノードがあれば、そのノードで折り返し、未実行の子ノードまで辿る探索である。
【００８２】
図１１のような依存関係を示す構造では、依存関係が近いノード（例えば、ノードＢ、Ｃ）間では参照するデータ領域が重複していることが一般的である。並列処理する２つのノードで参照するデータ領域が重複していると、キャッシュメモリＬ１とＣＰＵ間の同期処理が頻繁となり、処理効率が低下する。一方、参照するデータ領域が重複しないように遠く離れたアドレスの２つのノードを並列処理する場合は、Ｌ２キャッシュ内に収まらないデータ領域へのアクセスが発生し、Ｌ２キャッシュとメインメモリ間の同期処理が頻繁となり、やはり処理効率が低下する。
【００８３】
キャッシュの同期処理を具体的に説明ため、図１２（ａ）に示すような依存関係を表すグラフデータ構造において深さ優先探索を行うことを想定する。ノードＢが実行済みで、ノードＣが実行中で、深さ優先探索を行なうと、ノードＢからノードＡ、Ｄまで辿ると、ノードＤの子ノードで未実行のノードＦがあるので、ノードＤで折り返す。以下、ノードＤからノードＥを辿り、最終的にノードＦが次に実行すべきノードとして決定される。
【００８４】
ノードＢ、Ｃがそれぞれ＃１、＃２のＣＰＵに割り当てられていたとすると、次のノードＣはノードＢの処理が完了した＃１のＣＰＵに割り当てられる。しかし、依存関係が近いノードＣ、Ｆ間では参照するデータ領域が重複していることが一般的であるため、図１２（ｂ）に示すように、＃１、＃２のＣＰＵが必要とするデータ領域が重複する。従って、Ｌ１キャッシュとＣＰＵ間の同期処理が頻繁となり、処理効率が低下する。
【００８５】
図１３（ａ）に示すような依存関係を表すグラフデータ構造において幅優先探索を行うことを想定する。ノードＢが実行済みで、ノードＣが実行中で、幅優先探索を行なうと、ノードＢからノードＡ、Ｄを介して最上位のノードＧまで辿り、ノードＧで折り返す。以下、ノードＧからノードＨ、Ｉを辿り、最終的にノードＪが次に実行すべきノードとして決定される。なお、ノードＤ、ＨとノードＧとの間には図示を省略しているが、複数の階層（ノード）が存在している。
【００８６】
ノードＢ、Ｃがそれぞれ＃１、＃２のＣＰＵに割り当てられていたとすると、次のノードＣはノードＢの処理が完了した＃１のＣＰＵに割り当てられる。ノードＣとＪは依存関係が殆ど無いので、図１３（ｂ）に示すように＃１、＃２のＣＰＵが必要とするデータ領域がＬ２キャッシュ内に収まらない可能性がある。この場合は、Ｌ２キャッシュとメインメモリ間の同期処理が頻繁となり、処理効率が低下する。
【００８７】
そこで、本実施形態では、図１４（ａ）に示すように幅優先探索において戻り位置に制限を付けることにより、並列処理において参照されるデータ領域がＬ２キャッシュ内に確実に収まり、かつアドレス領域が重複しない（Ｌ１キャッシュとＣＰＵとの同期処理が発生しない）ようにできるだけ離れるようにする。
【００８８】
Ｌ２キャッシュとメインメモリ間の同期処理の発生の頻度が検出できれば、上限の決定はその検出結果に基づいて行えばよいが、現在ではこの発生頻度は検出が困難である。そのため、幅優先探索における戻り位置の上限を適応的に変えつつ処理性能をプロファイルすることにより実質的に同期処理の発生頻度を検出できる。
【００８９】
最下層から数えて何層目を上限とするかを決定する処理の一例のフローチャートを図１５に示す。ステップＳ３２で変数ｉに１をセットする。変数ｉは最下層を０層目とした時の上限の層を示す変数である。図１５の処理もプロセッサ１００ｉの何れかで実行される。
【００９０】
ステップＳ３４で処理単位の処理を開始する。処理単位とは、例えば処理対象データが画像データである場合、１フレームの画像データである。ステップＳ３６でＣＰＵクロックのカウントを開始する。ステップＳ３８で図１４に示すような戻り位置に上限を設けた（ｉ層目を上限とする）幅優先探索により次に処理すべきノードを決定する。このようにして決定されたノードが空いているＣＰＵに割り当てられ並列処理が行われ、画像データの１フレームが処理される。
【００９１】
ステップＳ４０で１フレームの画像データの処理が終了すると、ステップＳ４２でＣＰＵクロックのカウントを終了する。ステップＳ４４でカウント値Ｔ（ｉ）を記録する。ステップＳ４６で変数ｉが最大値に達したか否か判定される。達していない場合は、ステップＳ４８で変数ｉがインクリメントされ、ステップＳ３４の処理に戻る。ｉが最大値に達した場合は、ステップＳ５０でカウント値Ｔ（ｉ）の最小値を検出し、そのｉを戻り位置の上限層とする。これは、上限を変えて実際の処理を行った時の処理時間が最短であるということは、Ｌ２キャッシュとメインメモリとの同期処理の頻度が最小であると判断できるからである。この時、Ｌ１キャッシュとＣＰＵとの同期処理の頻度も最小であると判断できる。
【００９２】
以上説明したように本実施形態によれば、並列処理においてある基本モジュールが実行完了した際に、次にどの基本モジュールを実行するべきかを決定するために次に実行するノードを探索する際に、処理とアクセスするデータ領域の相関関係に基づいて処理時間が最短になるように幅に制限を設けた幅優先探索を行うことにより、Ｌ２キャッシュのキャッシュミスを抑えつつ、Ｌ１キャッシュとＬ２キャッシュの同期処理による処理効率の低下を抑制することができる。これにより、並列処理の全体の性能を高めることができる。
【００９３】
上述の説明は幅優先探索を基本とするノードの探索について行ったが、深さ優先探索を行っても問題ない状況も存在する。あるノードについて、そのノードおよびそのノードが依存していたノードの処理が全て終了した場合には、深さ優先探索により次に実行するノードを選択することにより、Ｌ１キャッシュとＬ２キャッシュの同期処理による処理効率の低下を抑制させることができる。
【００９４】
兄弟のノードが参照しようとするデータ領域は元のノードが参照していたデータ領域に近い場合が多いが、例えば図１６に示すように、ノードＢとそのノードが依存していたノードＡ、Ｃの処理が全て終了した直後は、元のノードＢの処理が終了したことで、ノードＢを実行したＣＰＵ＃１がアクセスしていたデータ領域へのアクセスは終了したので、深さ優先探索により決定されたノードＰの処理をＣＰＵ＃１に割り当てても、Ｌ１キャッシュの同期処理を行必要は無い。しかも、ＣＰＵ＃１のＬ１キャッシュ上にはノードＢがアクセスしたデータがあるので、ノードＢに近いノードＰがアクセスするデータが存在する可能性が高い。このため、深さ優先探索を行うと、Ｌ１キャッシュとＬ２キャッシュで同一アドレスの参照による同期処理の発生確率は低減され、並列処理全体の性能を高めることができる。
【００９５】
上記の探索手法は幅優先探索、あるいは深さ優先探索の一方を基本としたが、両者を組み合わせて試行錯誤的に最適な手法を決定してもよい。具体的には、深さ優先探索と種々の制限幅の幅優先探索との組み合わせからなる複数の探索パターンを実施した時のプログラムモジュールの処理負荷（例えば、図１５に示したような処理時間）を計測し、処理負荷が最も軽い探索パターンを決定してもよい。これは、処理するデータが画像ストリームである場合は画像の特性に基づきグラフデータ構造の形状や処理の進み方が変化したり、あるいはある時点で使用できるシステム中のプロセッサコアが可変であるような場合には、特定の探索手法では最良の結果が得られない場合があるからである。しかし、全てのノードについて次ノードの探索を試行錯誤的に行うのではなく、通常のタイプのノードについては図１４、図１５に示した手法を用い、特定のタイプのノードについては探索パターンの中から選択する手法を用いるという組合せも可能である。
【００９６】
次に、ノードの探索手法ではないが、グラフデータ構造を更新することにより、全体の性能を向上する手法について説明する。図１７（ａ）に示すように、あるノードを親として子を再帰的に辿れるノードの集合全体について同一のＣＰＵへ割当てられることが判っている場合、図１７（ｂ）に示すように、この集合を形成するノード群を１つのノードとみなしグラフデータ構造を更新する。これにより、プロセッサの割当てが固定的であると見なせるノードはプロセッサの割当ての判断処理が不要となるので、並列処理の全体的な処理時間が短縮される。
【００９７】
以上説明したように、本実施形態によれば、並列処理を、同期処理や排他処理のない直列実行部分（基本モジュール）と、それらの並列動作を記述する並列指定部分に分割することができるため、並列プログラムの記述性を向上させ、性能チューニング時のプログラムの変更を容易に行うことができ、メンテナンスコストを削減することができる。また、このようにして作った並列プログラムを効率よく動作させるランタイムによって、プロセッサの個数に対して、スケーラブルな並列実行性能を得ることが可能である。ランタイムタスクは自立的に実行可能な基本モジュール２００を選択し、併せてグラフデータ構造を逐次更新することで並列処理がなされることから、これら一連の処理はアプリケーションとして考慮する必要がない。また、基本モジュール２００は他のタスクと分岐する部分を含まないことから、実行中の他のタスクとの調停を考慮する必要もない。さらに、その時々の状況に応じて、各プログラムの実行負荷を動的に調整可能な仕組みが併せて実現される。
【００９８】
従って並列処理を意識せずにプログラム作成が可能で、かつマルチスレッドによる並列処理においても柔軟に実行可能なプログラミング環境を提供することができる。
【００９９】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１００】
【図１】本実施形態に係るシステム構成図の一例を示す図。
【図２】従来の並列処理プログラムの処理フローの一例を示す図。
【図３】本実施形態に係るプログラムの分割方法の一例を説明する図。
【図４】本実施形態に係るノードの依存関係の一例を説明する図。
【図５】本実施形態に係るプログラムのトランスレーションの一例を示す図。
【図６】本実施形態に係るノードの一例を説明する図。
【図７】本実施形態に係るノードのグラフデータ構造生成情報の一例を示す図。
【図８】本実施形態に係るグラフデータ構造の追加処理フローの一例を示す図。
【図９】本実施形態に係る基本モジュール処理の一例を示す図。
【図１０】本実施形態に係るキャッシュメモリの階層構造の一例を示す図。
【図１１】並列処理の実行時のノードの連なり状態の一例の木構造を示す図。
【図１２】次に実行すべきノードを決定する深さ優先探索の処理の一例を示す図。
【図１３】次に実行すべきノードを決定する幅優先探索の処理の一例を示す図。
【図１４】戻り上限を制限した幅優先探索の処理の一例を示す図。
【図１５】戻り上限の適正値を決定する処理の一例を示すフローチャート。
【図１６】深さ優先探索が好ましい状況の一例を示す図。
【図１７】ノードを決定する深さ優先探索の処理の一例を示す図。
【符号の説明】
【０１０１】
１００…プロセッサ、１０１…メインメモリ、１０２…ＨＤＤ、１０３…内部バス、２００…基本モジュール、２０１…並列実行制御記述、２０２…トランスレータ、２０３…情報処理装置、２０４…グラフデータ構造生成情報、２０６…ランタイムライブラリ、２１０…ＯＳ、４００，４０１…プログラム、４０４…イベント、４０６…ポイント、４０２，４０３…スレッド、ｄ１，ｄ２，ｄ３，ｅ１，ｅ２，ｅ３…基本モジュール、５００…基本モジュール、５０１…リンク、６０１…リンク、６０２…結合子、６０３…実行可能プール。
【図１】
2010009495.tif 000003
【図２】
2010009495.tif 000004
【図３】
2010009495.tif 000005
【図４】
2010009495.tif 000006
【図５】
2010009495.tif 000007
【図６】
2010009495.tif 000008
【図７】
2010009495.tif 000009
【図８】
2010009495.tif 000010
【図９】
2010009495.tif 000011
【図１０】
2010009495.tif 000012
【図１１】
2010009495.tif 000013
【図１２】
2010009495.tif 000014
【図１３】
2010009495.tif 000015
【図１４】
2010009495.tif 000016
【図１５】
2010009495.tif 000017
【図１６】
2010009495.tif 000018
【図１７】
2010009495.tif 000019
【手続補正書】
【提出日】平成21年11月9日(2009.11.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
を具備し、
前記実行手段は制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施することを特徴とする情報処理装置。
【請求項２】
前記実行手段はあるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記実行手段は深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施したときのプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施することを特徴とする請求項１または請求項２記載の情報処理装置。
【請求項４】
前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新手段をさらに具備することを特徴とする請求項１、請求項２及び請求項３のいずれか一項記載の情報処理装置。
【請求項５】
複数のプロセッサを有する情報処理装置で処理され、他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを用いるプログラム処理方法であって、
前記情報処理装置によって実行され、前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換ステップと、
前記情報処理装置によって実行され、入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加ステップと、
前記情報処理装置によって実行され、前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納ステップと、
前記情報処理装置によって実行され、深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行ステップと、
を具備し、
前記実行ステップは制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施することを特徴とするプログラム処理方法。
【請求項６】
前記実行ステップはあるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施することを特徴とする請求項５記載のプログラム処理方法。
【請求項７】
前記実行ステップは深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施したときのプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施することを特徴とする請求項５または請求項６記載のプログラム処理方法。
【請求項８】
前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新ステップをさらに具備することを特徴とする請求項５、請求項６及び請求項７のいずれか一項記載のプログラム処理方法。
【請求項９】
複数のプロセッサに並列処理を行わせるためのコンピュータプログラムであって、
コンピュータを、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
して機能させるためのコンピュータプログラムであって、
前記実行手段は、制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施させるコンピュータプログラム。
【請求項１０】
コンピュータに前記実行手段として、あるノードが先行ノードを含めて全て実行済みである場合は深さ優先探索を実施させることを特徴とする請求項９記載のコンピュータプログラム。
【請求項１１】
コンピュータに前記実行手段として、深さ優先探索と幅が制限された幅優先探索との組み合わせからなる複数の探索パターンを実施したときのプログラムモジュールの処理負荷を計測し、処理負荷が最も軽い探索パターンを実施させることを特徴とする請求項９または請求項１０記載のコンピュータプログラム。
【請求項１２】
コンピュータを前記グラフデータ構造においてノードグループの実プロセッサへの割当て方を調べて同じプロセッサへ割り当てられるノードグループがある場合は、当該グループを１つのノードとしてグラフデータ構造を更新する更新手段としてさらに機能させることを特徴とする請求項９、請求項１０及び請求項１１のいずれか一項記載のコンピュータプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
本発明の一態様による情報処理装置は、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
を具備し、
前記実行手段は制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施するものである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
本発明の一態様によるプログラム処理方法は、
複数のプロセッサを有する情報処理装置で処理され、他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを用いるプログラム処理方法であって、
前記情報処理装置によって実行され、前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換ステップと、
前記情報処理装置によって実行され、入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加ステップと、
前記情報処理装置によって実行され、前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納ステップと、
前記情報処理装置によって実行され、深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行ステップと、
を具備し、
前記実行ステップは制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施するものである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
本発明の一態様によるコンピュータプログラムは、
複数のプロセッサに並列処理を行わせるためのコンピュータプログラムであって、
コンピュータを、
他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となる複数のプログラムモジュールと、前記複数のプログラムモジュールの並列処理の関係を記述した並列実行制御記述とを記憶する記憶手段と、
前記記憶手段に記憶されている前記並列実行制御記述から前記複数のプログラムモジュールの各々に関連する部分を抽出し、少なくとも該プログラムモジュールの先行情報と後続情報とを含むグラフデータ構造生成情報を該プログラムモジュールごとに生成する変換手段と、
入力データが得られた場合、該入力データを入力とするグラフデータ構造生成情報を抽出し、該抽出したグラフデータ構造生成情報に基づいてノードを生成し、該生成したノードを、前記先行情報および後続情報に基づいてそれ以前に生成されたグラフデータ構造に追加する追加手段と、
前記グラフデータ構造において前記生成したノードに先行する全てのノードが実行済である場合、前記生成したノードをノード記憶部へ格納する格納する格納手段と、
深さ優先探索と幅が制限された幅優先探索の少なくとも一方を前記グラフデータ構造に対して実施し、前記ノード記憶部に記憶されているノードから１つのノードを選択し、該選択したノードに対応するプログラムモジュールを実行する実行手段と、
して機能させるためのコンピュータプログラムであって、
前記実行手段は、制限幅を変更して幅優先探索を実施したときのプログラムモジュールの処理時間を計測し、処理時間が最も軽い幅を制限幅とした幅優先探索を実施させるものである。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
幅優先探索とは、最上位のノードまで探索し、最上位のノードからなるべく近くのノードを探索しつつ最下位の未実行のノードまで辿る探索である。一方、深さ優先探索とは、木構造において上位方向へ探索していき、各ノードで子ノードが未実行であるか否か判断し、未実行の子ノードがあれば、そのノードで折り返し、未実行の子ノードまで辿る探索である。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
兄弟のノードが参照しようとするデータ領域は元のノードが参照していたデータ領域に近い場合が多いが、例えば図１６に示すように、ノードＢとそのノードが依存していたノードＡ、Ｃの処理が全て終了した直後は、元のノードＢの処理が終了したことで、ノードＢを実行したＣＰＵ＃１がアクセスしていたデータ領域へのアクセスは終了したので、深さ優先探索により決定されたノードＰの処理をＣＰＵ＃１に割り当てても、Ｌ１キャッシュの同期処理を行う必要は無い。しかも、ＣＰＵ＃１のＬ１キャッシュ上にはノードＢがアクセスしたデータがあるので、ノードＢに近いノードＰがアクセスするデータが存在する可能性が高い。このため、深さ優先探索を行うと、Ｌ１キャッシュとＬ２キャッシュで同一アドレスの参照による同期処理の発生確率は低減され、並列処理全体の性能を高めることができる。