(57)【要約】【課題】並列処理の粒度の調整を簡単に指定できるグラフィックユーザインターフェースを実現すること。【解決手段】基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムにおける、基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピング方法において、並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示するステップと、データフローグラフ上で処理単位の結合候補を指示するステップとを具備し、データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示する。【選択図】      図６
2010086319.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロセッサシステム用のプログラムであって、基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムにおける、基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピング方法において、
前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示するステップと、
前記データフローグラフ上で処理単位の結合候補を指示するステップとを具備し、
前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示することを特徴とするグルーピング方法。
【請求項２】
前記並列記述をテキスト表示するステップと、
前記データフローグラフ上で指示された結合候補の処理単位の結合に応じて前記並列記述を修正するステップをさらに具備することを特徴とする請求項１記載のグルーピング方法。
【請求項３】
前記データフローグラフ上で処理単位の結合候補の結合の優先度を指示するステップをさらに具備することを特徴とする請求項１または請求項２記載のグルーピング方法。
【請求項４】
前記データフローグラフ上で処理単位の結合候補を指示するステップは、同一データの異なるエントリに関する処理単位、あるいは異なるデータに関する処理単位を結合候補に指示可能であることを特徴とする請求項１または請求項２記載のグルーピング方法。
【請求項５】
前記データフローグラフ上で処理単位の結合候補を指示するステップは、処理単位が階層的な構造を有している場合は、結合候補を階層的に指示可能であることを特徴とする請求項１または請求項２記載のグルーピング方法。
【請求項６】
結合候補を階層的に指示した場合は、下位階層の処理単位の結合候補の結合の優先度は自動的に高く設定されることを特徴とする請求項５記載のグルーピング方法。
【請求項７】
前記並列記述の修正によりサイクルが出来る場合は、警告を発生し、結合を無効化するステップをさらに具備することを特徴とする請求項２記載のグルーピング方法。
【請求項８】
前記並列記述の修正によりクリティカルパスが出来る場合は、警告を発生するとともに、前記データフローグラフ上でクリティカルパスを明示的に表示するステップをさらに具備することを特徴とする請求項２記載のグルーピング方法。
【請求項９】
前記データフローグラフを表示するステップは、ノード間で転送されるデータの量に応じてエッジの太さを変えることを特徴とする請求項１または請求項２記載のグルーピング方法。
【請求項１０】
複数のプロセッサに並列処理を行わせるコンピュータプログラムであって、
基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムは基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピングをするものであり、
前記コンピュータプログラムは、コンピュータを、
前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示させる手段と、
前記データフローグラフ上で処理単位の結合候補を指示する手段として機能させるためのコンピュータプログラムであり、
前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示することを特徴とするコンピュータプログラム。
【請求項１１】
コンピュータを、さらに、
前記並列記述をテキスト表示する手段と、
前記データフローグラフ上で指示された結合候補の処理単位の結合に応じて前記並列記述を修正する手段として機能させることを特徴とする請求項１０記載のコンピュータプログラム。
【請求項１２】
基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムを実行して並列処理を行なうマルチプロセッサシステムであって、
前記プログラムは基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピングがなされ、該グルーピングは、前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示するステップと、前記データフローグラフ上で処理単位の結合候補を指示するステップとを具備し、前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示するグルーピング方法によりなされることを特徴とするマルチプロセッサシステム。
【請求項１３】
前記グルーピング方法は、前記並列記述をテキスト表示するステップと、前記データフローグラフ上で指示された結合候補の処理単位の結合に応じて前記並列記述を修正するステップをさらに具備することを特徴とする請求項１２記載のマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数のプロセッサに並列処理を行わせるコンピュータプログラム及びマルチプロセッサシステムと、プログラミングのためのグルーピング方法に関する。
【背景技術】
【０００２】
計算機の処理の高速化を実現するために複数の処理を並列に行うマルチスレッド処理がある。マルチスレッドによる並列処理プログラムでは複数のスレッドが生成され、それぞれのスレッドが同期処理を意識したプログラミングを強いられていた。例えば、実行順序を適切に保つためにはプログラムのさまざまな場所に同期を保証する処理を挿入する必要があり、プログラムのデバッグが困難になる等、メンテナンスコストが押し上げられていた。
【０００３】
このような並列処理プログラムの一例としては、特許文献１に記載のマルチスレッド実行方法がある。ここでは依存関係のある複数のスレッド（スレッド１はスレッド２の終了後でなければ実行できない等）を生成したとき、そのスレッドの実行結果とスレッド間の依存関係に基づいて並列処理を実現する方法が開示されている。
【０００４】
並列処理されるプログラム同士が実行順序を適切に保ちながら処理するには、プログラム間あるいはスレッド間であらかじめ依存関係を固定的に決定しておく必要がある。その一方で、その時々の状況に応じて、各プログラムの実行負荷を動的に調整可能な仕組みを備えることが好ましい。
【０００５】
並列処理の一つの形態は、複数ある処理単位を実行ユニット（ＣＰＵ）に割り当てるスケジューラを含むランタイム処理と、各実行ユニット上で動作する処理単位の２つの構成要素から構成される。処理単位の大きさを並列処理の粒度といい、粒度を細かくする方が並列化の機会を増やすことが可能となり、並列性能を向上できる。並列処理の粒度が細かすぎると、スケジューラが動作する回数が多くなるため、このオーバーヘッドによって、十分な性能を得られないと言う問題があった。
【０００６】
実行ユニット（ＣＰＵ）の数が十分多い場合には、ランタイムのオーバーヘッドが増えても、処理の並列度を向上させて、実行ユニットを使い切ることで性能向上が期待できる。実行ユニットの数に対して、並列度が十分であるときには、並列度を抑えて、ランタイムのオーバーヘッドを小さくすることで、実行効率を向上させることができる。
【０００７】
さらに、メニイコア等のプロセッサ数が２桁以上となるような環境において、メモリ階層が多層になりプロセッサ間のデータ通信のオーバーヘッドが均質でない場合において、処理単位のプロセッサへの割り当ては、データ転送のある処理単位を出来るだけ近くのプロセッサに割り当てられるようにすることで、共有メモリアクセスのメモリバンド幅を削減することが可能となる。しかし、プログラマがプロセッサへの割り当て方法を明示に指示するには、プログラムの構造を書き換えるなどの煩雑な作業が必要であった。
【０００８】
このような複数の処理を並列に実行するプログラムを、視覚的に、図形を用いて階層的に作成可能とするプログラムの表示方法が開発されている（例えば、特許文献２参照）。ここでは、並列計算機１３上で実行されるプロセスとして実現されている機能としてプログラム開発環境７４があり、プログラム開発環境７４は、プログラムとして、自プロセスに固有のプログラムとして、前述したようにエディタ３０、デバッカ３１、並列度評価プログラム３２を有している。また、プログラム開発環境７４は、ソースプログラム３５の内容をグラフィカルにディスプレイ１７に表示し、マウス６１やキーボード６５からの指示をエディタ３０、デバッカ３１、並列度評価プログラム３２に伝えるプログラムＧＵＩ５６を有している。プログラムＧＵＩ５６は、マウス６４やキーボード６５による指示をエディタ３０、デバッガ３１、並列度評価プログラム３２に伝える等、プログラム開発環境７４全体を制御する役割を担う。
【０００９】
特許文献２記載のプログラム表示方法は、プログラムを構成する複数の処理単位の階層的な構造の編集を受け付けるが、並列処理の粒度の変更に関する編集は受け付けていない。
【特許文献１】特開２００５−２５８９２０号公報（段落［００１４］、図７）
【特許文献２】特開平６−３３２６８９号公報（段落［００５６］、図１６）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
このように従来のプログラム表示方法には、並列処理の処理単位の大きさである並列処理の粒度を調整するためのプログラムの編集ができなかった。
【００１１】
本発明の目的は並列処理の粒度の調整を簡単に指定できるグラフィックユーザインターフェースを実現することである。
【課題を解決するための手段】
【００１２】
本発明の一態様によるグルーピング方法は、マルチプロセッサシステム用のプログラムであって、基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムにおける、基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピング方法において、前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示するステップと、前記データフローグラフ上で処理単位の結合候補を指示するステップとを具備し、前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示するものである。
【００１３】
本発明の他の態様によるコンピュータプログラムは、複数のプロセッサに並列処理を行わせるコンピュータプログラムであって、基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムは基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピングをするものであり、前記コンピュータプログラムは、コンピュータを、前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示させる手段と、前記データフローグラフ上で処理単位の結合候補を指示する手段として機能させるためのコンピュータプログラムであり、前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示するものである。
【００１４】
本発明の他の態様によるマルチプロセッサシステムは、基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムを実行して並列処理を行なうマルチプロセッサシステムであって、前記プログラムは基本モジュールとデータとからなる処理単位をプロセッサに割当てる処理単位のグルーピングがなされ、該グルーピングは、前記並列記述に基づき処理単位の処理状況を視覚的に示すデータフローグラフを表示するステップと、前記データフローグラフ上で処理単位の結合候補を指示するステップとを具備し、前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示するグルーピング方法によりなされることを特徴とするものである。
【発明の効果】
【００１５】
以上説明したように本発明によれば、基本モジュールの並列処理の関係を記述した並列記述に基づいて、データの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとからなるデータフローグラフを表示することにより、データフローグラフ上のノードの結合候補をマウス等で指示することにより、並列処理の粒度を直感的な操作で簡単に変更することができる。
【発明を実施するための最良の形態】
【００１６】
以下、図面を参照して本発明によるコンピュータプログラム、マルチプロセッサシステム及びグルーピング方法の実施の形態を説明する。
【００１７】
図１は本発明の第１の実施形態に係る並列処理を行うマルチプロセッサシステムの一例を示す図である。並列処理を実現するための多数のプロセッサ１００ｉ（ｉ＝１，２，３，…）、メインメモリ１０１、ハードディスクドライブ（ＨＤＤ）１０２が内部バス１０３に接続される。プロセッサ１００ｉはメインメモリ１０１やＨＤＤ１０２等の種々の記憶装置に記憶したプログラムコードを解釈し、プログラムとしてあらかじめ記述された処理を実行する機能を有する。図１では互いに同等の処理能力のプロセッサ１００ｉが３つ設けられていると想定するが、必ずしも同等のプロセッサである必要はなく、それぞれで処理能力が異なるものや、別種のコードを処理するプロセッサが含まれていてもかまわない。
【００１８】
メインメモリ１０１は例えばＤＲＡＭ等の半導体メモリで構成された記憶装置を指す。プロセッサ１００ｉが処理するプログラムは処理前に比較的高速にアクセス可能なメインメモリ１０１上に読み込まれ、プログラム処理に従ってプロセッサ１００ｉからアクセスされる。
【００１９】
ＨＤＤ１０２はメインメモリ１０１に比べて大容量のデータを記憶できるが、アクセス速度において不利である場合が多い。プロセッサ１００ｉが処理するプログラムコードはＨＤＤ１０２に記憶しておき、処理する部分のみをメインメモリ１０１上に読み出すように構成される。
【００２０】
内部バス１０３はプロセッサ１００ｉ、メインメモリ１０１及びＨＤＤ１０２を相互に接続し、互いにデータの授受ができるように構成した共通バスである。
【００２１】
プログラム表示のためのグラフィックユーザインタフェース（ＧＵＩ）１０４も内部バス１０３に接続され、処理結果を出力するための画像表示部１０５、後述するデータフローグラフの編集指示を入力するためのマウス１０６がＧＵＩ１０４に接続される。さらに、データ入力のためのキーボードがＧＵＩ１０４に接続されていてもよい。
【００２２】
次に、並列処理プログラムの概略を説明する。並列処理では複数のプログラムが並行して処理されているが、プログラム同士はそれぞれ無関係に処理されているわけではなく、他のプログラムの処理結果を自身の処理に使用する場合、あるいはデータの整合性を確保するという理由で他のプログラムの特定部分の処理が終わるのを待たねばならないことがある。このような特性を持つプログラムを並列に処理する場合、プログラムの各所に他のプログラムの実行状況を知得するための仕組みを埋め込まねばならない。この仕組み（同期処理とも呼ばれる）を埋め込むことによってプログラム間でデータ保証や、排他制御を実現し協調動作するように構成していた。しかしながら、プログラム自身に並列処理における同期処理を実現するための記述をした場合、本来のロジックとは別の配慮が必要となりプログラムが複雑になってしまう。また、他のプログラムの処理終了を待つ間、無駄にリソースを消費することにもなる。さらにはちょっとしたタイミングのずれによって処理効率が大きく変動するなど、後からのプログラム修正が困難になる場合が多い。
【００２３】
これを回避するために、本実施形態ではプログラムを、他のプログラムの実行状況に関係なく入力データが与えられたことを条件に実行可能となり、直列かつ同期処理無しで実行する直列基本モジュール（直列実行モジュールとも呼ばれる）と、直列基本モジュールをノードとしてグラフデータ構造生成情報を用いて複数の直列基本モジュールの並列処理の関係を記述する並列実行制御記述とに分割する。同期やデータの授受の必要のある部分は並列実行制御記述で記述することによって、直列基本モジュールの部品化を促進し、かつ、並列実行制御記述をコンパクトに管理できるようにする。図４にプログラムが直列基本モジュールと並列実行制御記述とに分割される様子を示す。
【００２４】
図２は本実施形態に係るプログラムの分割方法の一例を説明する図である。図２は相互に同期処理をするプログラム４００(プログラムＤ)及びプログラム４０１(プログラムＥ)を示している。
【００２５】
プログラム４００がスレッド４０２を、プログラム４０１がスレッド４０７を実行している。プログラム４００はポイント４０６までスレッド４０２を実行すると、その処理結果をプログラム４０１に受け渡す必要がある。このためプログラム４００はスレッド４０２の実行を終了すると、処理結果をイベント４０４としてプログラム４０１に通知する。プログラム４０１はイベント４０４とスレッド４０７の処理結果との両方が揃ったとき、初めてスレッド４０５を実行可能である。一方、プログラム４００はスレッド４０２の実行の終了を受けて、ポイント４０６以降のプログラムをスレッド４０３として実行する。
【００２６】
このようにプログラム４００、４０１にはスレッド４０２、４０７のように無条件に処理を進めて良い部分と、ポイント４０６のようにプログラムを処理していく間に他のスレッドに通知すべきある処理結果が得られるポイント、あるいは他のスレッドからの処理結果を得ることが処理開始の条件となっているポイントなどが存在する。
【００２７】
そこで、図２に示すように、ポイント４０６のようなポイントでプログラムを分割し、分割後のプログラムの処理単位をそれぞれ直列基本モジュールｄ１、ｄ２、ｄ３、…、直列基本モジュールｅ１、ｅ２、ｅ３、…と定義する。図２では相互に関連する２つのプログラムＤ、Ｅが示されているが、それ以上の数の相互に関連するプログラムがあっても同様の考え方で分割可能である。直列基本モジュールｄ１、ｄ２、ｄ３、…、直列基本モジュールｅ１、ｅ２、ｅ３、…が同期処理無しで実行できる直列実行モジュールである。
【００２８】
図３は本実施形態に係る直列基本モジュールの依存関係の一例を説明するグラフデータ構造を示す図である。モジュールの依存関係とはモジュール＃１はモジュール＃２の終了後でなければ実行できない等の関係である。図３の丸印である直列基本モジュール５００は図２で説明した直列基本モジュールｄ１、ｄ２、…、ｅ１、ｅ２、…のいずれかを表す。一番最初に実行される直列基本モジュール５００は他のスレッドに関係なく無条件に進めて良いモジュール化されたプログラムが割当てられる。直列基本モジュール５００は他の直列基本モジュールとの依存関係を示すリンク５０１に基づいて他の直列基本モジュールと関連付けられている。なお、グラフデータ構造においては、直列基本モジュールはノードとも呼ばれる。
【００２９】
図３の依存関係は、各直列基本モジュールはリンク５０１によって関連を定義された先行する直列基本モジュールからの計算結果出力のようなイベントを受け、同時にリンクにより関連を定義された後続の直列基本モジュールへのイベントを発生させることを示している。複数のリンクが入っている直列基本モジュールでは自身の処理のために複数の入力データ等が必要であることを示している。
【００３０】
図５は本実施形態に係るプログラムの実行環境を示す図である。多数の直列基本モジュール２００ｊ（ｊ＝１，２，…）は本実施形態に係るシステムで実行するプログラムである。直列基本モジュール２００ｊは１つ以上のパラメータ１９８を受け取り可能に構成され、このパラメータ１９８の値に基づき、例えば適用するアルゴリズムを変更したり、アルゴリズム上の閾値や係数を変更すること等により、実行負荷を調整できるようになっている。直列基本モジュール２００はそのまま実行環境の情報処理装置２０３内に取り込まれる。
【００３１】
並列実行制御記述２０１は実行する際に参照されるデータである。並列実行制御記述２０１は直列基本モジュール２００ｊ各々の並列処理時の依存関係（図３）を示す。並列実行制御記述は、実行環境における情報処理装置２０３にて実行される前にトランスレータ２０２によってグラフデータ構造生成情報２０４に変換される。トランスレータ２０２は並列実行制御記述から複数の直列基本モジュールの各々に関連する部分を抽出し、並列実行制御記述を少なくとも直列基本モジュールに先行する直列基本モジュールの情報と後続の直列基本モジュールの情報とを含むグラフデータ構造生成情報を生成する。グラフデータ構造生成情報２０４はランタイムライブラリ２０６内に格納される。
【００３２】
トランスレータ２０２は直列基本モジュール２００を処理する前に事前に変換する場合以外にも、直列基本モジュール２００の実行中、ランタイムタスク等によって逐次トランスレートしながら処理する方法も考えられる。
【００３３】
情報処理装置２０３上の実行時点のソフトウェアは直列基本モジュール２００ｊ、ランタイムライブラリ２０６（グラフデータ構造生成情報２０４を格納する）、マルチスレッドライブラリ２０８、オペレーティングシステム２１０、対称マルチプロセッサ２１２から構成される。
【００３４】
ランタイムライブラリ２０６は直列基本モジュール２００ｊを情報処理装置２０３上で実行する際のAPI（Application Interface）などを含み、直列基本モジュール２００ｊを並列処理する際に必要となる排他制御を実現するための機能を有する。一方、ランタイムライブラリ２０６からトランスレータ２０２の機能を呼び出すように構成し、直列基本モジュール２００の処理の過程で呼び出されるとき、次に処理する部分の並列実行制御記述２０１をその都度変換するようにしても良い。このように構成すれば、トランスレートするための常駐タスクが不要になり、並列処理をよりコンパクトに構成できる。
【００３５】
オペレーティングシステム２１０は情報処理装置２０３のハードウェアやタスクのスケジューリングなど、システム全体を管理している。オペレーティングシステム２１０を導入することで、基本モジュール２００を実行する際、プログラマはシステムの雑多な管理から開放され、プログラミングに専念できるとともに、一般的に機機種でも稼動可能なソフトウェアを開発できるというメリットがある。
【００３６】
本実施形態に係る情報処理装置では同期処理やデータの授受の必要な部分でプログラムを分割し、その間の関連を並列実行制御記述として定義することで、基本モジュールの部品化を促進し、並列処理定義をコンパクトに管理することができる。部品化した各基本モジュールの実行負荷は動的に調整可能である。
【００３７】
図５に示すように、並列実行制御記述２０１をグラフデータ構造生成情報２０４に一旦変換し、これを解釈実行するランタイムを並列に実行させることによって、オーバーヘッドの低減を図り、かつプログラミングの柔軟性を確保することができる。このランタイム処理は少なくともプロセッサの数よりも多数のスレッドによって実行し、動的に生成されるグラフデータ構造を解釈して、実行するべき直列基本モジュール２００ｊを選択し、グラフデータ構造を更新しながら直列基本モジュール２００ｊの実行を繰り返すことによって、並列処理を実現する。
【００３８】
グラフデータ構造生成情報は、Ｃ言語の構造体によるデータ構造で実現する場合もあるし、仮想マシンとしてのバイトコード列によって表現することもある。バイトコードで表現する場合は、プログラム実行環境である仮想マシンが、バイトコードを解釈実行することによって、グラフ構造を生成する。バイトコードによるグラフ生成は、バイトコードの入力オペランドのデータが、まだ有効でない場合でかつ、その入力データを求めるためにスレッドの実行を必要とする場合に、その処理をノードとして作成し、データの依存関係をエッジとしてデータフローグラフに追加することによって行う。
【００３９】
そのため、ＧＵＩ１０４は図５に示す実行環境の情報処理装置２０３内のグラフデータ構造生成情報２０４に基づいて図６の右側に示すようなデータフローグラフを表示部１０５で表示する。データフローグラフはデータと関数（タスク）の並列関係を示すものであり、この例では、データ（配列）ｉｎ０、ｉｎ１に関数ｈ、ｇが作用し、その結果のデータ（配列）ａ、ｂに対してさらに関数ｆが作用し、その結果のデータ（配列）ｃに対してさらに関数ｋが作用し、結果のデータ（配列）ｏｕｔが得られることを示す。関数ｆ、ｈ、ｇは直列基本モジュールに相当する。データ配列のそれぞれのデータに対する関数は関数のノードと称される。
【００４０】
図６の左側は右側のデータフローグラフの元である並列実行制御記述である。並列処理の粒度の変更に関する編集はデータフローグラフ上の関数のノードの結合という視覚的な編集処理により実行できるが、並列実行制御記述のテキストを直接編集することによっても実行できるので、並列実行制御記述は必ずしも表示しなくても良いが、データフローグラフに加えて表示してもよい。並列実行制御記述はデータフローグラフとともに同じ表示部１０５で表示してもよいが、表示部１０５とは別の表示部（テキストエディタ）で表示させても良い。
【００４１】
図６に示した並列実行制御記述は、トランスレータ２０２により以下のように解釈され、グラフデータ構造生成情報２０４に変換され、情報処理装置２０３で実行される。
【００４２】
ステップ＃１：以下の３行を解釈する。
【００４３】
ｌｏｃａｌ  ａ［１００］；
ｌｏｃａｌ  ｂ［１００］；
ｌｏｃａｌ  ｃ［１００］；
ｌｏｃａｌ宣言されたメモ化用のデータ配列ａ，ｂ，ｃ（それぞれエントリ個数は１００とする）を生成する（領域を確保し初期化する）。
【００４４】
ステップ＃２：次の３行は関数定義である。
【００４５】
ａ［ｉ］：＝ｈ（ｉｎ０［ｉ］）；
ｂ［ｉ］：＝ｇ（ｉｎ１［ｉ］）；
ｃ［ｉ］：＝ｆ（ａ［ｉ］，ｂ［ｉ］）；
ステップ＃３：ｆｏｒ文を実行し、変数ｊを０に初期化する。ｊが１００以下の場合は、ループ本体を実行する。
【００４６】
ｆｏｒ（ｊ＝０；  ｊ＜１００；ｊ＋＋）｛ｏｕｔ［ｉ］＝ｋ（ｃ［ｉ］）；｝
ステップ＃４：ループ本体で、ｏｕｔ［０］を計算するために関数ｋを呼び出そうとするが、引数ｃ［０］が未定義なので、関数ｋのノードを作成し、データ依存として関数ｋのノードとｃ［０］のエントリをつなぐエッジを生成する。
【００４７】
ステップ＃５：ｃ［０］を求めるための関数定義であるｃ［ｉ］：＝ｆ（ａ［ｉ］，ｂ［ｉ］）に従い関数ｆを呼び出そうとするが、引数ａ［０］，ｂ［０］が未定義であるため、関数ｆのノードを作成し、データ依存として関数ｆのノードとａ［０］およびｂ［０］のエントリをつなぐエッジをそれぞれ生成する。
【００４８】
ステップ＃６：ａ［０］を求めるために関数定義であるａ［ｉ］：＝ｈ（ｉｎ０［ｉ］）に従い、関数ｈを呼び出そうとするが、引数ｉｎ０［０］が未定義であるため、上記と同様にノードを作成しエッジを生成する。ｂ［０］についても同様に、ノードを作成しエッジを生成する。
【００４９】
ステップ＃７：ｉｎ０［０］やｉｎ１［０］が定義済みの場合は、関数ｈ，ｇの実行に移り、バイトコード解釈を次のプロセッサに引き継ぐ。
【００５０】
ステップ＃８：一連のノード生成と連結が完了するとステップ＃４に戻り、ｉ＝１の場合のバイトコード実行を継続する。
【００５１】
ステップ＃９：並列実行制御記述実行の各フェーズにおいて、上記で作成して成長したデータフローグラフの各ノードの入力値が確定し、実行可能になった時点で、それらのノードがあらわす関数（スレッド）の実行に遷移するものとする。
【００５２】
図６の右側に示したデータフローグラフは、上記の動作を模擬して生成可能なものであり、図１のＧＵＩ１０４を介して表示部１０５の画面上に表示される。
【００５３】
上記の並列実行制御記述の実行過程は、各関数（スレッド）を呼び出すたびにランタイムを引き継いでいくので、スレッドへの分割が細かすぎると、ランタイムの実行頻度が高くなり、全体処理に対するオーバーヘッドが大きくなってしまう。
【００５４】
一方で、プロセッサ数が大きくない場合は、細かく分けて並列性を抽出しても、結局は、同じプロセッサ上で一連の処理を動作させることになる。
【００５５】
また、メモリ階層がある場合は、特定のノードの集合を同一のクラスタ上で動作させると効率が良くなる場合がある。２次キャッシュを共有する８個のプロセッサ群（クラスタ）４個が３次キャッシュを共有して、８×４＝３２個のマルチプロセッサを構成する。
【００５６】
そこで、図７に示すように、ノードの粒度を粗くするための情報をデータフローグラフ画面から指定する仕組みを提案する。
【００５７】
プログラマは、データフローグラフ画面において、ランタイムの介在なくまとめて処理を行いたい複数のノードを指定する。図７では、関数ｆ、ｇ、ｈの複数のノードをデータ並列方向にグルーピングする例を示している。図６では説明の便宜上、関数は１つのデータ配列に対して代表的に１つだけ示したが、実際には、データ配列内のそれぞれのエントリ（例えば、ｉｎ０［０］、ｉｎ０［１］、…）に対してそれぞれ関数のノードｈ１、ｈ２、…が存在する。グルーピングはデータフローグラフ画面においてグルーピングする関数のノードをマウス１０６で指定する、あるいは囲むことで実施する。関数ｆ、ｇについてはグループ化を完了し、そのグループ化の結合強度（優先順位）のタブの数値入力まで完了している状態を示している。結合強度とはプログラマにより操作指示されたグループ化を実際に実行する時の優先順位である。関数ｈについては、複数のノードｈ０、ｈ１、…をマウス操作（図７の矢印はマウスカーソルを示す）によって囲む途中の様子を示し、囲む作業が終了すると、囲んだ楕円上にタブが現れ、優先順位の数値データの入力を促す。
【００５８】
データフローグラフ上のこのグルーピングに呼応して、グラフデータ構造生成情報が変更され、トランスレータ２０２の逆トランスレーションを利用して並列実行制御記述にもグルーピングが反映される。すなわち、図７の左側に示すように、該当する関数ｈ、ｇ、ｆの定義の終わりにアノテーションｃｏｎｎ（関数、ｘ）が自動生成される。ｘは、結合強度である。
【００５９】
ａ［ｉ］：＝ｈ（ｉｎ０［ｉ］）；ｃｏｎｎ（ｈ，０）；
ｂ［ｉ］：＝ｇ（ｉｎ１［ｉ］）；ｃｏｎｎ（ｇ，０）；
ｃ［ｉ］：＝ｆ（ａ［ｉ］，ｂ［ｉ］）；ｃｏｎｎ（ｆ，１）；
図８はタスク並列方向にグルーピングする例を示している。タスクとは関数と対応し、図８は関数ｈと関数ｇをランタイムの介在なく纏めて処理を行いたい指示を示す。タスク並列のグルーピングの場合は、並列実行制御記述上では、グルーピングしたタスクがｃｏｎｎ（ｘ）｛…｝というスコープで括られる。関数定義の順序も自動的に入れ替えられる場合がある。
【００６０】
ｃｏｎｎ（０）｛  
ａ［ｉ］：＝ｈ（ｉｎ０［ｉ］）；
ｂ［ｉ］：＝ｇ（ｉｎ１［ｉ］）；
｝
図９はタスク並列方向のグルーピングに階層構造をもたせる例を示している。関数ｆとｇとのグルーピング全体と関数ｆとをさらにグルーピングする２階層のグルーピングの例を示す。関数ｆとｇとのグルーピングが下位の階層であり、下位の階層の優先順位は自動的に高く設定される。階層構造を持たせ、下位ほど優先順位を高くすることにより、試行錯誤により最適なグルーピングを決定する際に、容易に最適解を求めることが出来る。
【００６１】
ｃｏｎｎ（０）｛  
ｃｏｎｎ（１）｛  
ａ［ｉ］：＝ｈ（ｉｎ０［ｉ］）；
ｂ［ｉ］：＝ｇ（ｉｎ１［ｉ］）
｝
ｃ［ｉ］：＝ｆ（ａ［ｉ］，ｂ［ｉ］）；
｝
なお、グルーピングには、図７に示すデータ並列方向のグルーピングと、図８、図９に示すタスク並列方向のグルーピング以外に、その両者を組み合わせた第３のグルーピングもある。
【００６２】
図１０にデータフローグラフ上でグルーピング（ノードを連結）した場合のアルゴリズムを示す。ノードの連結指示が検出されると、ブロックＢ１２において、グルーピングによってデータフローグラフにサイクルが出来てしまうか否か判定する。この判定はグルーピング後のグラフデータ構造生成情報からトランスレータの逆トランスレーションにより求めた並列実行制御記述を解析することにより実施できる。サイクルが出来てしまった場合は、ブロックＢ１４に示すように、警告「グルーピングによりサイクル生成」を画面に表示して、そのグルーピング操作を無効にする。
【００６３】
サイクルが出来ていない場合は、ブロックＢ１６において、グルーピングによって処理のクリティカルパスが大きく悪化するか否かさらに判定する。この判定も逆トランスレーションにより求めた並列実行制御記述を解析することにより実施できる。クリティカルパスが大きく悪化する場合は、ブロックＢ１８でワーニングメッセージ「グルーピングにより並列度悪化」を表示し、そのグルーピングが本当に必要かどうかの再考を促す。
【００６４】
クリティカルパスが大きく悪化しない場合、あるいはブロックＢ１８でワーニングメッセージを表示した後、ブロックＢ２０で結合候補のノードは同じ関数であるか否か判定する。同じ関数である場合は図７に示すデータ並列方向のグルーピングであるので、ブロックＢ２２で並列実行制御記述上の該当する関数の適用位置の引数リストの後ろにｃｏｎｎ（ｘ）を記載する。別の関数である場合は図８、図９に示すタスク並列方向のグルーピングであるので、ブロックＢ２４で並列実行制御記述上のグルーピングする関数の配置を並び替えスコープｃｏｎｎ（ｘ）｛…｝でくくる。
【００６５】
上述のデータフローグラフは関数のノードとデータのエントリとを繋ぐエッジは単なる線で示したが、ノード間を転送するデータの量に応じてエッジの太さを変えて表示してもよい。図６のノードｇとｆとを繋ぐエッジは他よりも太い線で表示し、データ量が多いことを示す。データ量を知ることにより、グルーピング候補を決定する際の参考になる。
【００６６】
また、グルーピングすることによりノード間のデータ転送がローカル化できるエッジの線を異なる色、態様で表示してもよい。これによっても、グルーピング候補を決定する際の参考になる。図６のデータ配列ａとデータ配列ｃまでのデータ転送はメインメモリ１０１へのアクセスが不要で、Ｌ１キャッシュあるいはＬ２キャッシュまでのアクセスで済みローカル化できることを示す。
【００６７】
上述のデータフローグラフは２次元的に表示した例を示したが、図３に示すようにタスクの関係が複雑で網の目のようになっている場合は、タスクの表示だけで２次元が使われてしまう。その場合は、図１１に示すように、タスクを２次元に表示し、データ配列はタスク面とは異なる次元に、すなわち３次元的に表示してもよい。
【００６８】
以上の仕組みによって、基本モジュールの並列処理の様子を示すデータフローグラフ上で、結合するノードとその結合強度を指定できるようになり、これらのデータを使って、並列実行環境は、プロセッサ数やメモリ階層に適合して、充分な並列性がありランタイム処理のオーバーヘッドが大きい場合は、結合強度の優先度にしたがって、ノードを結合することによって、ランタイムの実行切り替え回数を削減すると同時に、メモリ階層の局所性が必要な場合は、グループごとに、ノードをクラスタに割り当てるなどの最適化を行うことが出来るようになる。
【００６９】
グルーピングにおいて、もしそのグループ化によって配列データを必要としなくなる場合は、データの転送コストを大きく削減できる可能性がある。そのような配列データを、あらかじめハイライト表示することによって、プログラマにグループ化の効果が高い部分を認識させることが可能となる。
【００７０】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００７１】
【図１】本発明の一実施形態に係る並列処理を行うマルチプロセッサシステムの一例を示す図。
【図２】並列処理プログラムの処理フローの一例を示す図。
【図３】本実施形態に係るノードの依存関係の一例を説明する図。
【図４】本実施形態に係るプログラム構成を説明する図。
【図５】本実施形態に係るプログラムのトランスレーションの一例を示す図。
【図６】本実施形態に係るグラフデータ構造生成情報から得られたデータフローグラフの一例と、それに対応する並列実行制御記述を示す図。
【図７】本実施形態に係るデータフローグラフと並列実行制御記述におけるデータ並列方向のグルーピングの例を示す図。
【図８】本実施形態に係るデータフローグラフと並列実行制御記述におけるタスク並列方向のグルーピングの例を示す図。
【図９】本実施形態に係るデータフローグラフと並列実行制御記述におけるタスク並列方向の階層構造を持つグルーピングの例を示す図。
【図１０】本実施形態に係るグルーピングのアルゴリズムの一例を示すフローチャート。
【図１１】本実施形態に係るデータフローグラフの３次元表示の一例を示す図。
【符号の説明】
【００７２】
１００…プロセッサ、１０１…メインメモリ、１０２…ＨＤＤ、１０３…内部バス、１０４…ＧＵＩ、１０５…表示部、１０６…マウス、２００…基本モジュール、２０１…並列実行制御記述、２０２…トランスレータ、２０３…情報処理装置、２０４…グラフデータ構造生成情報、２０６…ランタイムライブラリ、２１０…ＯＳ、２１２…対称マルチプロセッサ。
【図１】
2010086319.tif 000003
【図２】
2010086319.tif 000004
【図３】
2010086319.tif 000005
【図４】
2010086319.tif 000006
【図５】
2010086319.tif 000007
【図６】
2010086319.tif 000008
【図７】
2010086319.tif 000009
【図８】
2010086319.tif 000010
【図９】
2010086319.tif 000011
【図１０】
2010086319.tif 000012
【図１１】
2010086319.tif 000013
【手続補正書】
【提出日】平成21年11月5日(2009.11.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチプロセッサシステム用のプログラムであって、基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなるプログラムにおける、基本モジュールとデータとからなるスレッドをプロセッサに割当てるスレッドのグルーピング方法において、
前記並列記述に基づきスレッドの状況を視覚的に示すデータフローグラフを表示することと、
前記データフローグラフ上でスレッドの結合候補を指示することとを具備し、
前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとをそれぞれを繋ぐエッジとを表示し、
前記表示することと、前記指示することはコンピュータハードウェアにより実施されるグルーピング方法。
【請求項２】
前記並列記述をテキスト表示することと、
前記データフローグラフ上で指示された結合候補に応じて前記並列記述を修正することとをさらに具備する請求項１記載のグルーピング方法。
【請求項３】
前記データフローグラフ上で結合候補の優先度を指示することをさらに具備する請求項１記載のグルーピング方法。
【請求項４】
前記結合候補を指示することは、同一データの異なるエントリに関するスレッド、あるいは異なるデータに関するスレッドを結合候補として指示することを具備する請求項１記載のグルーピング方法。
【請求項５】
前記結合候補を指示することは、スレッドが階層的な構造を有している場合は、階層内の結合候補の位置を指示することを特徴とする請求項１記載のグルーピング方法。
【請求項６】
階層内の下位のスレッドの結合候補に実質的に高い優先度を割り当てることを具備する請求項５記載のグルーピング方法。
【請求項７】
前記並列記述の修正によりサイクルが出来る場合は、警告を発生し、結合を無効化することをさらに具備する請求項２記載のグルーピング方法。
【請求項８】
前記並列記述の修正によりクリティカルパスが出来る場合は、警告を発生するとともに、前記データフローグラフ上でクリティカルパスを明示的に表示することをさらに具備する請求項２記載のグルーピング方法。
【請求項９】
前記データフローグラフを表示することは、ノード間で転送されるデータの量に応じてエッジの太さを変えることを具備する請求項１記載のグルーピング方法。
【請求項１０】
処理単位のグルーピングをするプログラムを格納するコンピュータ読取可能な媒体であって、前記処理単位は基本モジュールとデータとからなり、前記処理単位はマルチプロセッサシステム用のプログラムにおける複数のプロセッサに割り当てられ、プログラムは基本モジュールと、基本モジュールの並列処理の関係を記述した並列記述とからなり、
前記プログラムは、コンピュータに、
前記並列記述に基づき処理単位の状況を視覚的に示すデータフローグラフを表示させることと、
複数のエントリと、基本モジュールの複数のノードと、複数のエントリと複数のノードとを繋ぐエッジとを表示することと、
前記データフローグラフ上で処理単位の結合候補を指示することと、
を実行させるものであるコンピュータ読取可能な媒体。
【請求項１１】
コンピュータに、さらに、
前記並列記述をテキスト表示することと、
前記データフローグラフ上の結合候補に応じて前記並列記述を修正することとを実行させる請求項１０記載のコンピュータ読取可能な媒体。
【請求項１２】
基本モジュールと、基本モジュールの並列スレッドの関係を記述した並列記述とからなるプログラムを実行して並列計算を行なうマルチプロセッサシステムであって、
前記プログラムを格納する格納システムと、
前記プログラムを実行する多数のプロセッサと、を具備し、
前記プログラムは基本モジュールとデータとからなり、前記多数のプロセッサに割り当てられるスレッドグルーピングすることを具備し、該グルーピングすることは、前記並列記述に少なくとも部分的に基づきスレッドの状況を視覚的に示すデータフローグラフを表示することと、前記データフローグラフ上でスレッドの結合候補を指示することとを具備し、前記データフローグラフはデータの複数のエントリと、基本モジュールの複数のノードと、データの複数のエントリと基本モジュールの複数のノードとを繋ぐエッジとを表示するマルチプロセッサシステム。
【請求項１３】
前記プログラムは、前記並列記述をテキスト表示することと、前記データフローグラフ上の結合候補に応じて前記並列記述を修正することと、をさらに具備する請求項１２記載のマルチプロセッサシステム。