(57)【要約】【課題】並列実行されるプログラムの粒度調整を実行時において効率的に実施することを可能とする情報処理装置を提供する。【解決手段】ランタイムライブラリ２００の並列粒度調整部２３０は、各直列基本モジュールの実行時、基本モジュール負荷測定部２３３およびランタイム負荷測定部２３４により各種実行時間を測定してプロファイル情報収集部２３１にて管理し、このプロファイル情報収集部２３１にて管理された測定情報に基づいた粒度調整を実行する。そして、投機実行制御部２３２は、空き状態の実行ユニットが存在する時、先行ノードが完了していない待機状態の直列基本モジュールを、本来の実行プログラム１００用とは無関係に、空き状態のコア１１に対して別途割り当てて試験的に実行させ、基本モジュール負荷測定部２３３およびランタイム負荷測定部２３４による各種実行時間の測定を行わせる。【選択図】      図９
2010009395.tif 000002
【特許請求の範囲】
【請求項１】
複数の実行ユニットと、
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、前記複数の実行ユニットによって並列実行するために、前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御するスケジューラと、
を具備し、
前記スケジューラは、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させる投機実行制御手段と、
前記基本モジュール自体の処理の実行時間を測定する基本モジュール負荷測定手段と、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定するランタイム負荷測定手段と、
前記基本モジュール負荷測定手段が測定した実行時間および前記ランタイム負荷測定手段が測定した実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する粒度調整手段と、
を有することを特徴とする情報処理装置。
【請求項２】
前記投機実行制御手段は、前記基本モジュールの試験的な実行中、いずれかの基本モジュールが待機状態から実行可能状態に移行した場合、前記基本モジュールの試験的な実行を中止して実行ユニットを解放することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記投機実行制御手段は、各基本モジュールが指定された回数実行され、前記基本モジュール負荷測定手段による実行時間の測定が各基本モジュール毎に前記指定された回数実行されるまで、前記基本モジュールの試験的な実行を継続することを特徴とする請求項１記載の情報処理装置。
【請求項４】
前記投機実行制御手段は、入力パラメータが変更された基本モジュールを、前記基本モジュールの試験的な実行の対象とすることを特徴とする請求項１記載の情報処理装置。
【請求項５】
前記複数の実行ユニットは、１つのＣＰＵに内蔵されるＣＰＵコアであることを特徴とする請求項１記載の情報処理装置。
【請求項６】
前記複数の実行ユニットは、それぞれが個別に構成された複数のＣＰＵであることを特徴とする請求項１記載の情報処理装置。
【請求項７】
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、複数の実行ユニットによって並列実行する情報処理装置における粒度調整方法であって、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させ、
前記基本モジュール自体の処理の実行時間を測定し、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定し、
前記測定した２つの実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する、
ことを特徴とする粒度調整方法。
【請求項８】
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、複数の実行ユニットによって並列実行する情報処理装置を、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させる投機実行制御手段、
前記基本モジュール自体の処理の実行時間を測定する基本モジュール負荷測定手段、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定するランタイム負荷測定手段、
前記基本モジュール負荷測定手段が測定した実行時間および前記ランタイム負荷測定手段が測定した実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する粒度調整手段、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＣＰＵコアを複数内蔵するＣＰＵを搭載するコンピュータや、複数のＣＰＵを搭載するコンピュータ等に適用して好適なプログラムの粒度調整技術に関する。
【背景技術】
【０００２】
近年、ノートブックタイプやデスクトップタイプ等、様々な種類の個人向けコンピュータ（パーソナルコンピュータ）が広く普及している。この種のコンピュータでは、例えば高精細動画像データをソフトウェアによって再生する等、その情報処理能力に対する要求はＣＰＵの性能向上の限界に迫るほどに高まる一方である。
【０００３】
このような事から、例えば複数のＣＰＵを搭載したり、また、最近では、ＣＰＵコアを複数内蔵するＣＰＵを搭載するコンピュータが登場してきている。即ち、プログラムを並列処理することで、所要時間の短縮化を図り、以て、コンピュータの性能を向上させるわけである。プログラムの並列処理を効率的に行うための仕組みについては、これまでも種々提案されている（例えば特許文献１等参照）。
【特許文献１】特開２００５−２５８９２０公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
プログラムの並列処理の１つの形態は、プログラム中の各処理単位を実行ユニットに割り当てる（複数のＣＰＵを搭載するコンピュータにおいては、各ＣＰＵへの割り当てを行い、ＣＰＵコアを複数内蔵するＣＰＵを搭載するコンピュータにおいては、各ＣＰＵコアへの割り当てを行う）スケジューラを含むランタイム処理と、各実行ユニット上で動作する処理単位との２つの構成要素から構成される。この時、処理単位の大きさを並列処理の粒度といい、粒度を細かくする方が、並列化の機会を増やすことが可能となるので、並列性能を向上できる。
【０００５】
一方で、この並列処理の粒度が細かすぎると、スケジューラが動作する回数が多くなるため、このオーバーヘッドによって、十分な性能を得られないという問題があった。
【０００６】
この発明は、このような事情を考慮してなされたものであり、並列実行されるプログラムの粒度調整を実行時において効率的に実施することを可能とする情報処理装置、粒度調整方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
前述の目的を達成するために、この発明の情報処理装置は、複数の実行ユニットと、他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、前記複数の実行ユニットによって並列実行するために、前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御するスケジューラと、を具備し、前記スケジューラは、前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させる投機実行制御手段と、前記基本モジュール自体の処理の実行時間を測定する基本モジュール負荷測定手段と、前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定するランタイム負荷測定手段と、前記基本モジュール負荷測定手段が測定した実行時間および前記ランタイム負荷測定手段が測定した実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する粒度調整手段と、を有することを特徴とする。
【発明の効果】
【０００８】
この発明によれば、並列実行されるプログラムの粒度調整を実行時において効率的に実施することが可能となる。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照して、この発明の一実施形態を説明する。
【００１０】
図１は、本実施形態に係る情報処理装置のシステム構成の一例を示す図である。この情報処理装置は、ノートブックタイプやデスクトップタイプ等のいわゆるパーソナルコンピュータとして実現されている。そして、図１に示すように、本コンピュータは、プロセッサ１、主メモリ２およびハードディスク駆動装置（ＨＤＤ）３を有しており、これらは内部バスを介して相互に接続されている。
【００１１】
プロセッサ１は、ＨＤＤ３から主メモリにロードされたプログラムを実行制御する中央演算処理装置（ＣＰＵ）であり、主要部の演算回路（ＣＰＵコア）であるコア１１を複数内蔵している。
【００１２】
主メモリ２は、プロセッサ１がアクセス可能な、例えば半導体で構成される記憶装置である。一方、ＨＤＤ３は、本コンピュータにおける補助記憶としての役割を担う、（主メモリ２と比較して）低速大容量の記憶媒体である。
【００１３】
また、図示していないが、プロセッサ１によるプログラムの処理結果等を表示するためのディスプレイや処理データ等を入力するためのキーボードなどの入出力装置が、例えばノートブックタイプの場合はさらに備えられ、また、例えばデスクトップタイプの場合はケーブル等により外部接続される。
【００１４】
コア１１を複数内蔵するプロセッサ１を搭載する本コンピュータは、複数のプログラムを並列実行することが可能であり、また、１つのプログラム中の複数の処理を並列実行することも可能である。ここで、図２を参照して、本コンピュータによって実行される並行処理仕様のプログラムの概略構成について説明する。
【００１５】
図２に示すように、本コンピュータによって実行される並行処理仕様の実行プログラム１００は、複数の直列基本モジュール１０１と、この複数の直列基本モジュール１０１をどのような順序で実行すべきかを定義する並列実行制御記述１０２とから構成される。
【００１６】
いわゆるマルチスレッド処理では、一般的に、図３に示すように、他のスレッドとの間で（通信を含む）同期を取りながら、即ち、プログラム全体の整合性を保ちながら、各スレッドが処理を進行させていく。よって、同期の待ち合わせが多発すると、期待した並列性能が得られないことも考えられる。
【００１７】
そこで、本実施形態では、図４に示すように、他のモジュールとの同期を取る必要がない、非同期に実行可能な処理単位にプログラムを分割することで、複数の直列基本モジュール１０１を作成すると共に、この複数の直列基本モジュール１０１の時系列的な実行規則を定義する並列実行制御記述１０２を作成する。並列実行制御上、各直列基本モジュール１０１は、ノードとして表現される。このように、直列基本モジュールとは、他のモジュールと非同期に実行可能な処理単位のモジュールをいう。次に、図５を参照して、並列実行制御記述１０２について説明する。
【００１８】
図５（Ａ）は、ある直列基本モジュール１０１を表現したノードの概念図である。図示のように、各直列基本モジュール１０１は、先行ノードへのリンクと、後続ノードへの結合子とを有するノードとして捉えることができる。並列実行制御記述１０２は、各直列基本モジュール１０１それぞれについて、先行ノードへのリンク情報を記すことにより、複数の直列基本モジュール１０１の実行順序を定義する。図５（Ｂ）は、ある直列基本モジュール１０１に関する並列実行制御記述を例示する図であり、図示のように、それぞれの識別子である直列基本モジュールＩＤと、その直列基本モジュール１０１の先行ノードへのリンク情報とが記される。また、その他に、出力バッファタイプやコスト等の情報が併せて記される。
【００１９】
続いて、この複数の直列基本モジュール１０１と並列実行制御記述１０２とから構成されるという独自の構成をもつ実行プログラム１００を本コンピュータがどのように実行するのかについて説明する。
【００２０】
このような独自の構成をもつ実行プログラム１００を並列処理するために、本コンピュータでは、図６に示すランタイムライブラリ２００が用意される。このランタイムライブラリ２００は、スケジューラとしての機能を備えており、並列実行制御記述１０２がグラフデータ構造生成情報２０１として与えられる。並列実行制御記述１０２は、例えば関数型言語を用いて作成され、トランスレータによってグラフデータ構造生成情報２０１に変換される。
【００２１】
何らかのデータ入力が行われると、このデータを処理するための直列基本モジュール１０１をいくつか実行する必要が生じるが、その都度、ランタイムライブラリ２００は、グラフデータ構造生成情報２０１に基づき、グラフデータ構造２０２を動的に生成・更新していく。グラフデータ構造２０２は、その時々で適宜に実行されていくノード群の前後関係を示すグラフデータであり、ランタイムライブラリ２００は、追加対象のノード間での前後関係は勿論、実行待ちの状態にあるノードとの間の前後関係も考慮して、それらノード群のグラフデータ構造２０２への追加を行っていく。
【００２２】
また、ランタイムライブラリ２００は、あるノードの実行が完了すると、このノードをグラフデータ構造２０２から削除すると共に、このノードを先行ノードとし、かつ、その他に先行ノードがないか、または、その他の先行ノードがすべて完了している後続ノードの有無を調べて、この条件を満たす後続ノードが存在したら、そのノードをいずれかのコア１１に割り当てる。
【００２３】
このランタイムライブラリ２００の働きにより、並列実行制御記述１０２に基づく複数の直列基本モジュール１０１の並列実行が矛盾無く進められていく。また、このランタイムライブラリ２００は、プロセッサ１が内蔵するコア１１の数よりも多くの数のスレッドによって実行する（マルチスレッド）。その結果、図７に示すように、各コア１１（各コア１１のＯＳ３００配下の１スレッドであるランタイムライブラリ２００）があたかも自律的に次に実行すべき直列基本モジュール１０１を見つけ出してくるかのごとく本コンピュータを動作させることができる。スレッド間の排他制御は、ランタイムライブラリ２００による、グラフデータ構造２０２からのノードの選択と、当該グラフデータ構造の更新とのみに止まるので、図３に示した一般的なマルチスレッド処理と比較して、高い並列性能を得ることを実現する。
【００２４】
ところで、本コンピュータのプロセッサ１が内蔵するコア１１の数に対して、直列基本モジュール１０１の処理単位、つまり並列処理の粒度が細かすぎると、ランタイムライブラリ２００の稼働機会、いわゆるオーバヘッドが増えてしまい、実行効率を低下させることになりかねない。この点を考慮して、本実施形態のランタイムライブラリ２００は、この並列処理の粒度を実行時に効率的に調整する機能を備える。
【００２５】
より具体的に説明すると、いま、図８（Ａ）に示すような関係にあるノードＡ〜ノードＥの５つのノードが存在するものと想定すると、ランタイムライブラリ２００は、例えば図８（Ｂ）に示すように、ノードＡとノードＢとを連結し、ノードＣ〜ノードＥの先行ノードをノードＡからノードＢに変更する機能を備える。
【００２６】
また、逆に、連結によって並列性が落ちてしまうこともありうる。例えば、処理するべき入力データの性質が変化して、モジュール毎の負荷バランスが変化する場合である。これを考慮して、ランタイムライブラリ２００は、図８（Ｂ）に示すように連結したノードＡとノードＢとを、図８（Ａ）に示すように再分割する機能も備える。
【００２７】
図９は、ランタイムライブラリ２００の機能ブロック図である。
【００２８】
ランタイムライブラリ２００は、図９に示すように、ノード生成部２１０、グラフ構造解釈実行エンジン２２０および並列粒度調整部２３０を有している。
【００２９】
前述した、本ランタイムライブラリ２００による、グラフデータ構造生成情報２０１に基づくグラフデータ構造２０２の動的な生成・更新と、このグラフデータ構造２０２を用いたノードのコア１１への割り当て制御とは、ノード生成部２１０およびグラフ構造解釈実行エンジン２２０とによって実現されている。そして、以下にその詳細を説明する、並列処理されるプログラムの実行時における効率的な粒度調整は、並列粒度調整部２３０によって実現され、並列粒度調整部２３０は、プロファイル情報収集部２３１、投機実行制御部２３２、基本モジュール負荷測定部２３３およびランタイム負荷測定部２３４を有している。
【００３０】
基本モジュール負荷測定部２３３は、各直列基本モジュール１０１自体の処理の実行時間（基本モジュール実行時間）を測定する。一方、ランタイム負荷測定部２３４は、各直列基本モジュール１０１をコア１１に割り当てるためのランタイムライブラリ２００による処理の実行時間（ランタイム実行時間）を測定する。そして、プロファイル情報収集部２３１は、この基本モジュール負荷測定部２３３およびランタイム負荷測定部２３４によって得られる測定情報を一元的に管理する。
【００３１】
並列粒度調整部２３０は、プロファイル情報収集部２３１によって管理される測定情報に基づき、実行プログラム１００の粒度調整を実行する。より具体的には、
（１）基本モジュールの実行時間平均  ＜  ランタイム実行時間、であるとき、粒度を大きくする。
【００３２】
（２）基本モジュールの実行時間平均  ＞＞  ランタイム実行時間、であるとき、粒度を小さくする。
【００３３】
という粒度調整を実行する。
【００３４】
ところで、本コンピュータのように、複数のコア１１を内蔵するプロセッサ１を搭載する場合、複数の直列基本モジュール１０１を並列実行することが可能であるので、高速化が図られるわけであるが、すべてのコア１１が、常時、いずれかの直列基本モジュール１０１を実行しているとは限らない。並列実行制御記述１０２に基づき、直列基本モジュール１０１の並列実行を矛盾無く進めていくために、ある直列基本モジュール１０１が、他の直列基本モジュール１０１の実行終了を待機することがあるからである。
【００３５】
そこで、本コンピュータで動作するランタイムライブラリ２００の並列粒度調整部２３０は、このような事情で発生する空き状態のコア１１を、実行プログラム１００の粒度調整に活用するようにしたものである。そのために、並列粒度調整部２３０は、投機実行制御部２３２を備える。
【００３６】
ここでは、先行ノードがすべて完了している実行可能状態の直列基本モジュール１０１を先行制約のない直列基本モジュール１０１と称し、また、先行ノードが完了していない待機状態の直列基本モジュール１０１を先行制約がある直列基本モジュール１０１と称することとする。
【００３７】
投機実行制御部２３２は、空き状態のコア１１が存在する場合、先行制約がある直列基本モジュール１０１を、本来の実行プログラム１００用とは無関係に、空き状態のコア１１に対して別途割り当てる。入力パラメータは、たとえばテスト用に作成されたデータを予め用意しておいて暫定的に与える。このような結果を考慮しない直列基本モジュール１０１の実行を、ここでは投機実行と称する。
【００３８】
先行制約のない直列基本モジュール１０１は、即時にコア１１に割り当てられて実行されるので、基本モジュール負荷測定部２３３による基本モジュール実行時間の測定と、ランタイム負荷測定部２３４によるランタイム実行時間の測定が行われ、並列粒度調整部２３０による粒度調整が必要に応じて行われることになる。これに加えて、本コンピュータでは、空き状態のコア１１が存在するならば、この空き状態のコア１１に対して、先行制約がある直列基本モジュール１０１が割り当てられて投機実行されるので、基本モジュール負荷測定部２３３による基本モジュール実行時間の測定と、ランタイム負荷測定部２３４によるランタイム実行時間の測定が行われ、並列粒度調整部２３０による粒度調整が必要に応じて行われることになる。
【００３９】
即ち、実行プログラム１００の並列実行時において、空き状態のコア１１を、当該実行プログラム１００の粒度調整に活用することが実現されるわけである。
【００４０】
なお、当然ながら、本来の実行プログラム１００の実行は、粒度調整のための投機実行に優先する。そのため、投機実行制御部２３２は、先行制約がある直列基本モジュール１０１の投機実行中、いずれかの直列基本モジュール１０１が先行制約のない直列基本モジュール１０１となった場合、その実行を優先するために、先行制約がある直列基本モジュール１０１の投機実行を中止して、そのコア１１を解放する。
【００４１】
また、投機実行制御部２３２は、実行プログラム１００の実行が開始された後、すべての直列基本モジュール１０１が実行されるのを１セットとして、（十分な粒度調整が図られると予測される）指定されたセット数分、各直列基本モジュール１０１が実行されるまで、この先行制約がある直列基本モジュール１０１の投機実行を継続する。ランタイムライブラリ２００は、並列粒度調整部２３０の投機実行制御部２３２についての有効／無効の設定を受け付け可能であり、例えば（コア１１数の異なるプロセッサ１への）プロセッサ１の交換時等に、投機実行制御部２３２を有効に設定するといった運用を行うことができる。
【００４２】
次に、図１０乃至図１２を参照して、本コンピュータによる実行プログラム１００の実行時における粒度調整に関わる動作手順について説明する。
【００４３】
ランタイムライブラリ２００は、まず、グラフ構造解釈実行エンジン２２０が、グラフデータ構造２０２中において先行制約のない直列基本モジュール１０１をコア１１に対して割り当てる（図１０ステップＡ１）。また、ランタイムライブラリ２００は、空き状態のコア１１が発生していないかを監視し（図１０ステップＡ２）、空き状態のコア１１が存在しなければ（図１０ステップＡ２のＮＯ）、空き状態のコア１１が発生するまで待機する（図１０ステップＡ３）。
【００４４】
一方、空き状態のコア１１が存在した場合（図１０ステップＡ２のＹＥＳ）、並列粒度調整部２３０の投機実行制御部２３２は、指定されたセット数分、各直列基本モジュール１０１が実行される前であれば（図１０ステップＡ４のＮＯ）、図１２に詳細な流れが示される投機実行による粒度調整を実行する（図１０ステップＡ５）。
【００４５】
例えば図１１に示すようなグラフデータ構造２０２が存在する場合、直列基本モジュール１０１（２）は、直列基本モジュール１０１（１）の実行終了という先行制約があり、直列基本モジュール１０１（３）は、直列基本モジュール１０１（１）および直列基本モジュール１０１（２）双方の実行終了という先行制約がある。従って、直列基本モジュール１０１（１）の実行中においては、空き状態のコア１１が存在しても、直列基本モジュール１０１（２）および直列基本モジュール１０１（３）のいずれも実行を開始することはできない。
【００４６】
このような時、投機実行制御部２３２は、直列基本モジュール１０１（２）および直列基本モジュール１０１（３）のうち、本セット中にまだ実行されていない直列基本モジュール１０１があれば、その直列基本モジュール１０１を投機実行させるべく、空き状態のコア１１に割り当てる（図１２のステップＢ１）。この投機実行により、基本モジュール負荷測定部２３３による基本モジュール実行時間の測定と、ランタイム負荷測定部２３４によるランタイム実行時間の測定が行われるので、並列粒度調整部２３０は、基本モジュール実行時間がランタイム実行時間に対して想定時間外であったならば（図１２のステップＢ２のＹＥＳ）、この投機実行した直列基本モジュール１０１について並列粒度調整を実行する（図１２ステップＢ３）。
【００４７】
また、ランタイムライブラリ２００は、先行制約のない直列基本モジュール１０１へと移行した直列基本モジュール１０１がないかを監視し（図１０ステップＡ６）、存在した場合（図１０ステップＡ６のＹＥＳ）、投機実行を中止して、この先行制約のない直列基本モジュール１０１の実行を開始する（図１０ステップＡ１）。一方、存在しない場合には（図１０ステップＡ６のＮＯ）、並列粒度調整部２３０は、本セットにおいてすべての直列基本モジュール１０１が実行されたかを調べ（図１０ステップＡ７）、すべて実行されていれば（図１０ステップＡ７のＹＥＳ）、残セット数を１デクリメントする（図１０ステップＡ８）。そして、並列粒度調整部２３０は、指定されたセット数分、各直列基本モジュール１０１が実行されたかを再度調べ（図１０ステップＡ４）、実行される前であれば（図１０ステップＡ４のＹＥＳ）、この先行制約がある直列基本モジュール１０１の投機実行を継続する。
【００４８】
なお、並列粒度調整部２３０は、ノードの結合を行う場合、結合するノードを属性情報として持つような新たなグラフデータ構造生成情報２０１を生成する。新たに生成する情報は、２つの直列基本モジュール１０１を同一のコア１１上で連続して実行させるためのノードに関する情報であり、そのリンク情報は、２つのノードのリンク情報をマージしたものとする。即ち、ここで新たに作成されるノードは、２つの直列基本モジュール１０１を１つのモジュールと見なす論理的な直列基本モジュール１０１に対応するものである。
【００４９】
この時、並列粒度調整部２３０は、これら２つのノードを参照していた別のノードのリンク情報を、新たに生成したノードに書き換える。これにより、次回以降、ノード生成部２１０は、この新たに生成されたグラフデータ構造生成情報２０１を使って、グラフデータ構造２０２へのノードの追加を行うことになる。
【００５０】
また、連結したノードに対応する直列基本モジュール１０１が同一のコア１１上で連続実行されることになることから、並列粒度調整部２３０は、この範囲で、命令のスケジューリングや変数のレジスタへの再割り当て、その他のコンパイラの最適化を行い、これらが効率よく処理されるための変換を併せて実行する。
【００５１】
この並列粒度調整部２３０の働きにより、ランタイムライブラリ２００は、実行プログラム１００の実行時において、効率的に、その粒度を自己調整することを実現する。そして、（並列処理の粒度が実行時に自己調整される）本手法によれば、実行プログラム１００の作成時には、粒度を意識することなく、各直列基本モジュール１０１を、ただ十分小さな処理単位に分割すれば良い。よって、コア１１の数毎に実行プログラム１００を作り直したり、チューニングする手間を一切無くすことができる。
【００５２】
なお、以上では、本コンピュータが、コア１１を複数内蔵するプロセッサ１を搭載する場合を例に本手法を説明したが、本手法は、複数のプロセッサ１を搭載するいわゆるマルチプロセッサコンピュータにおいても当然に適用できる。
【００５３】
また、投機実行制御部２３２が、例えば入力パラメータが変更された直列基本モジュール１０１のみを投機実行の対象とするように変更することも容易に可能である。
【００５４】
つまり、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００５５】
【図１】この発明の実施形態に係る情報処理装置のシステム構成の一例を示す図
【図２】本実施形態の情報処理装置によって実行される並行処理仕様のプログラムの概略構成を説明するための図
【図３】一般的なマルチスレッド処理を示す図
【図４】本実施形態の情報処理装置によって実行されるプログラムを構成する直列基本モジュールと並列実行制御記述との関係を示す図
【図５】本実施形態の情報処理装置によって実行されるプログラムの並列実行制御記述を説明するための図
【図６】本実施形態の情報処理装置上で動作するランタイムライブラリが行うプログラムの並列処理制御を説明するための図
【図７】本実施形態の情報処理装置上におけるランタイムライブラリの動作状態を示す図
【図８】本実施形態の情報処理装置上で動作するランタイムライブラリが実施するノードの結合を説明するための図
【図９】本実施形態の情報処理装置上で動作するランタイムライブラリの機能ブロックを示す図
【図１０】本実施形態の情報処理装置上で動作するランタイムライブラリが実行する並列処理最適化の動作の流れを示す第１のフローチャート
【図１１】本実施形態の情報処理装置上で動作するランタイムライブラリによる直列基本モジュールの投機実行の具体例を示す図
【図１２】本実施形態の情報処理装置上で動作するランタイムライブラリが実行する並列処理最適化の動作の流れを示す第２のフローチャート
【符号の説明】
【００５６】
１…プロセッサ、２…主メモリ、３…ハードディスク駆動装置（ＨＤＤ）、１１…コア、１００…実行プログラム、１０１…直列基本モジュール、１０２…並列実行制御記述、２００…ランタイムライブラリ、２０１…グラフデータ構造生成情報、２０２…グラフデータ構造、２１０…ノード生成部、２２０…グラフ構造解釈実行エンジン、２３０…並列粒度調整部、２３１…プロファイル情報収集部、２３２…投機実行制御部、２３３…基本モジュール負荷測定部、２３４…ランタイム負荷測定部。
【図１】
2010009395.tif 000003
【図２】
2010009395.tif 000004
【図３】
2010009395.tif 000005
【図４】
2010009395.tif 000006
【図５】
2010009395.tif 000007
【図６】
2010009395.tif 000008
【図７】
2010009395.tif 000009
【図８】
2010009395.tif 000010
【図９】
2010009395.tif 000011
【図１０】
2010009395.tif 000012
【図１１】
2010009395.tif 000013
【図１２】
2010009395.tif 000014
【手続補正書】
【提出日】平成21年7月17日(2009.7.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の実行ユニットと、
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、前記複数の実行ユニットによって並列実行するために、前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御するスケジューラと、
を具備し、
前記スケジューラは、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させる投機実行制御手段と、
前記基本モジュール自体の処理の実行時間を測定する基本モジュール負荷測定手段と、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定するランタイム負荷測定手段と、
前記基本モジュール負荷測定手段が測定した実行時間および前記ランタイム負荷測定手段が測定した実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する粒度調整手段と、
を有することを特徴とする情報処理装置。
【請求項２】
前記投機実行制御手段は、前記基本モジュールの試験的な実行中、いずれかの基本モジュールが待機状態から実行可能状態に移行した場合、前記基本モジュールの試験的な実行を中止して実行ユニットを解放することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記投機実行制御手段は、各基本モジュールが指定された回数実行され、前記基本モジュール負荷測定手段による実行時間の測定が各基本モジュール毎に前記指定された回数実行されるまで、前記基本モジュールの試験的な実行を継続することを特徴とする請求項１記載の情報処理装置。
【請求項４】
前記投機実行制御手段は、入力パラメータが変更された基本モジュールを、前記基本モジュールの試験的な実行の対象とすることを特徴とする請求項１記載の情報処理装置。
【請求項５】
前記複数の実行ユニットは、１つのＣＰＵに内蔵されるＣＰＵコアであることを特徴とする請求項１記載の情報処理装置。
【請求項６】
前記複数の実行ユニットは、それぞれが個別に構成された複数のＣＰＵであることを特徴とする請求項１記載の情報処理装置。
【請求項７】
前記プログラムを記憶する記憶媒体を備え、
前記複数の実行ユニットは、前記記憶媒体から読み出した前記プログラムの前記基本モジュールを実行する、
ことを特徴とする請求項１記載の情報処理装置。
【請求項８】
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、複数の実行ユニットによって並列実行する、前記実行規則に基づき前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御するスケジューラを有する情報処理装置における粒度調整方法であって、
前記スケジューラが、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させ、
前記基本モジュール自体の処理の実行時間を測定し、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定し、
前記測定した２つの実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する、
ことを特徴とする粒度調整方法。
【請求項９】
他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、複数の実行ユニットによって並列実行する情報処理装置を、
前記複数の実行ユニットの中にいずれの基本モジュールも割り当てられていない空き状態の実行ユニットが存在した場合、前記実行規則によって他の基本モジュールの実行終了待ちの状態となっている基本モジュールを、前記プログラムの並列実行とは別に、前記空き状態の実行ユニットに対して割り当てて試験的に実行させる投機実行制御手段、
前記基本モジュール自体の処理の実行時間を測定する基本モジュール負荷測定手段、
前記基本モジュールを前記実行ユニットに割り当てる処理の実行時間を測定するランタイム負荷測定手段、
前記基本モジュール負荷測定手段が測定した実行時間および前記ランタイム負荷測定手段が測定した実行時間に基づき、前記実行規則によって前後して実行される２以上の基本モジュールを、前記実行ユニットに対して１組みとして割り当てられるように結合し、または、結合した２以上の基本モジュールを再分割することによる粒度調整を実行する粒度調整手段、
として機能させるプログラム。