JP4621786B2 - 情報処理装置、並列処理最適化方法およびプログラム - Google Patents

Description

本発明は、例えばＣＰＵコアを複数内蔵するＣＰＵを搭載するコンピュータや、複数のＣＰＵを搭載するコンピュータ等に適用して好適なプログラムの並列処理制御技術に関する。

近年、ノートブックタイプやデスクトップタイプ等、様々な種類の個人向けコンピュータ（パーソナルコンピュータ）が広く普及している。この種のコンピュータでは、例えば高精細動画像データをソフトウェアによって再生する等、その情報処理能力に対する要求はＣＰＵの性能向上の限界に迫るほどに高まる一方である。

このような事から、例えば複数のＣＰＵを搭載したり、また、最近では、ＣＰＵコアを複数内蔵するＣＰＵを搭載するコンピュータが登場してきている。即ち、プログラムを並列処理することで、所要時間の短縮化を図り、以て、コンピュータの性能を向上させるわけである。プログラムの並列処理を効率的に行うための仕組みについては、これまでも種々提案されている。

例えば、特許文献１は、(ヘテロジニアス)マルチプロセッサの制御方法において、タスクを第１のプロセッサにおける処理コストと転送コストを加算した値と、第２のプロセッサにおける処理コストと転送コストを加算した値とを比較して、タスクをプロセッサに割り当てることを開示している。

特開２００７−３２８４１５号公報

上述した文献は、コンパイラの技術を開示している。現在発売されているマルチプロセッサ中のＣＰＵコアの数は一定ではない。ＣＰＵコアの数に応じてコンパイルを行ったプログラムを提供する必要がある。

この発明は、プログラムの実行中に動的にプログラムの並列処理を効率化することを可能とする情報処理装置、並列処理最適化方法およびプログラムを提供することを目的とする。

一例に係わる情報処理装置は、それぞれ識別子が与えられた複数のスレッドを実行する複数の実行ユニットと、他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、前記複数の実行ユニットによって並列実行するために、前記実行規則に基づき、前記複数の実行ユニットが実行するスレッドに対する前記複数の基本モジュールの動的な割り当てを制御するスケジューラと、を具備し、
前記スケジューラは、前記実行ユニットによって実行済みの基本モジュールを実行したスレッドの識別子を管理する手段と、前記実行ユニットによって実行可能な基本モジュールを実行可能集合として管理する手段と、前記実行可能集合中の各基本モジュールについて、前記基本モジュールがデータを参照する前記実行済みの基本モジュールの計算結果のデータサイズおよび当該実行済みの基本モジュールを実行したスレッドの識別子に基づいて、実行済みの基本モジュールを実行したスレッドから複数のスレッドから選ばれる一つのスレッドtidにデータを転送した場合の転送コストをそれぞれ計算するコスト計算手段と、前記転送コストが最小の基本モジュールを前記スレッドtidに割り当てる基本モジュールとして選択する選択手段とを具備し、
前記転送コストは、

によって演算される、
ここで、Ｐｒｅｄ（ｃ）は前記実行可能集合中の基本モジュールから選ばれる一つの基本モジュールｃがデータを参照する基本モジュールｎの集合を示し、ｓｉｚｅ（ｎ）は前記基本モジュールｎによる計算結果のデータサイズ、ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は前記基本モジュールｎを実行したスレッドｎ→tidからスレッドtidへのデータ転送コストである、
ことを特徴とする。

本発明によれば、プログラムの実行中に動的にプログラムの並列処理を効率化することを可能とする。

本発明の一実施形態に係る情報処理装置のシステム構成の一例を示す図。 本実施形態の情報処理装置によって実行される並行処理仕様のプログラムの概略構成を説明するための図。 一般的なマルチスレッド処理を示す図。 本実施形態の情報処理装置によって実行されるプログラムを構成する直列基本モジュールと並列実行制御記述との関係を示す図。 本実施形態の情報処理装置によって実行されるプログラムの並列実行制御記述を説明するための図。 本実施形態の情報処理装置上で動作するランタイムライブラリが行うプログラムの並列処理制御を説明するための図。 本実施形態の情報処理装置上におけるランタイムライブラリの動作状態を示す図。 本実施形態の情報処理装置上におけるランタイムライブラリおよび基本モジュールの動作状態を示す図。 オペレーティングシステム（ＯＳ）によるスレッドのスケジューリング粒度と、並列ランタイム環境がスケジュールするタスクの粒度の違いを示す図。 並列実行環境が管理するグラフデータ構造を示す図。 ラインタイムライブラリの構成を示すブロック図。 Ｒｅａｄy集合からノードを選択する処理の手順を示すフローチャート。 スレッド毎にＲｅａｄｙ集合を持つ場合の登録処理の手順を示す図。 スレッド毎にＲｅａｄｙ集合を持つ場合の選択処理の手順を示す図。 データ転送サイズを視覚化したグラフデータ構造を示す図。 プロセッサ間のデータ転送コストを視覚化した図。

本発明の実施の形態を以下に図面を参照して説明する。

図１は、本実施形態に係る情報処理装置のシステム構成の一例を示す図である。この情報処理装置は、ノートブックタイプやデスクトップタイプ等のいわゆるパーソナルコンピュータとして実現されている。そして、図１に示すように、本コンピュータは、プロセッサ１、主メモリ２およびハードディスク駆動装置（ＨＤＤ）３を有しており、これらは内部バスを介して相互に接続されている。

プロセッサ１は、コンピュータ等の情報処理装置から読み取り可能な記憶媒体であるＨＤＤ３から主メモリにロードされたプログラムを実行制御する中央演算処理装置（ＣＰＵ）であり、主要部の演算回路（ＣＰＵコア）であるコア１１を複数内蔵している。

主メモリ２は、プロセッサ１がアクセス可能な、例えば半導体で構成される記憶装置である。一方、ＨＤＤ３は、本コンピュータにおける補助記憶としての役割を担う、（主メモリ２と比較して）低速大容量の記憶媒体である。

また、図示していないが、プロセッサ１によるプログラムの処理結果等を表示するためのディスプレイや処理データ等を入力するためのキーボードなどの入出力装置が、例えばノートブックタイプの場合はさらに備えられ、また、例えばデスクトップタイプの場合はケーブル等により外部接続される。

コア１１を複数内蔵するプロセッサ１を搭載する本コンピュータは、複数のプログラムを並列実行することが可能であり、また、１つのプログラム中の複数の処理を並列実行することも可能である。ここで、図２を参照して、本コンピュータによって実行される並行処理仕様のプログラムの概略構成について説明する。

図２に示すように、本コンピュータによって実行される並行処理仕様の実行プログラム１００は、複数の直列基本モジュール１０１と、この複数の直列基本モジュール１０１をどのような順序で実行すべきかを定義する並列実行制御記述１０２とから構成される。

いわゆるマルチスレッド処理では、一般的に、図３に示すように、他のスレッドとの間で（通信を含む）同期を取りながら、即ち、プログラム全体の整合性を保ちながら、各スレッドが処理を進行させていく。よって、同期の待ち合わせが多発すると、期待した並列性能が得られないことも考えられる。

そこで、本実施形態では、図４に示すように、他のモジュールとの同期を取る必要がない、非同期に実行可能な処理単位にプログラムを分割することで、複数の直列基本モジュール１０１を作成すると共に、この複数の直列基本モジュール１０１の時系列的な実行規則を定義する並列実行制御記述１０２を作成する。並列実行制御上、各直列基本モジュール１０１は、ノードとして表現される。このように、直列基本モジュールとは、他のモジュールと非同期に実行可能な処理単位のモジュールをいう。次に、図５を参照して、並列実行制御記述１０２について説明する。

図５（Ａ）は、ある直列基本モジュール１０１を表現したノードの概念図である。図示のように、各直列基本モジュール１０１は、先行ノードへのリンクと、後続ノードへの結合子とを有するノードとして捉えることができる。並列実行制御記述１０２は、各直列基本モジュール１０１それぞれについて、先行ノードへのリンク情報を記すことにより、複数の直列基本モジュール１０１の実行順序を定義する。図５（Ｂ）は、ある直列基本モジュール１０１に関する並列実行制御記述を例示する図であり、図示のように、それぞれの識別子である直列基本モジュールＩＤと、その直列基本モジュール１０１の先行ノードへのリンク情報とが記される。また、その他に、出力バッファタイプや生成するデータサイズの情報が併せて記される。

続いて、この複数の直列基本モジュール１０１と並列実行制御記述１０２とから構成されるという構成をもつ実行プログラム１００を本コンピュータがどのように実行するのかについて説明する。

このような構成をもつ実行プログラム１００を並列処理するために、本コンピュータでは、図６に示すランタイムライブラリ２００が用意される。ランタイムライブラリ２００はコンピュータ情報処理装置から読み取り可能な記憶媒体であるＨＤＤ３に格納される。ハードディスクドライブ３から主メモリにロードされたランタイムライブラリ２００は、プロセッサ１によって実行される。このランタイムライブラリ２００は、スケジューラとしての機能を備えており、並列実行制御記述１０２がグラフデータ構造生成情報２０１として与えられる。並列実行制御記述１０２は、例えば関数型言語を用いて作成され、トランスレータによってグラフデータ構造生成情報２０１に変換される。

何らかのデータ入力が行われると、このデータを処理するための直列基本モジュール１０１をいくつか実行する必要が生じるが、その都度、ランタイムライブラリ２００は、グラフデータ構造生成情報２０１に基づき、複数のノードとノード間を接続するエッジによって示すグラフデータ構造２０２を動的に生成・更新していく。グラフデータ構造２０２は、その時々で適宜に実行されていくノード群の前後関係を示すグラフデータであり、ランタイムライブラリ２００は、追加対象のノード間での前後関係は勿論、実行待ちの状態にあるノードとの間の前後関係も考慮して、それらノード群のグラフデータ構造２０２への追加を行っていく。

また、ランタイムライブラリ２００は、あるノードの実行が完了すると、このノードをグラフデータ構造２０２から削除すると共に、このノードを先行ノードとし、かつ、その他に先行ノードがないか、または、その他の先行ノードがすべて完了している後続ノードの有無を調べて、この条件を満たす後続ノードが存在したら、そのノードをいずれかのコア１１に割り当てる。

このランタイムライブラリ２００の働きにより、並列実行制御記述１０２に基づく複数の直列基本モジュール１０１の並列実行が矛盾無く進められていく。また、このランタイムライブラリ２００は、プロセッサ１が内蔵するコア１１の数よりも多くの数のスレッドによって実行する（マルチスレッド）。その結果、図７および図８に示すように、各コア１１（各コア１１のＯＳ３００配下の１スレッドであるランタイムライブラリ２００）があたかも自律的に次に実行すべき直列基本モジュール１０１を見つけ出してくるかのごとく本コンピュータを動作させることができる。スレッド間の排他制御は、ランタイムライブラリ２００による、グラフデータ構造２０２からのノードの選択と、当該グラフデータ構造の更新とのみに止まるので、図３に示した一般的なマルチスレッド処理と比較して、高い並列性能を得ることを実現する。

図７には、コア１１が４つの場合を示している。４つのコア中のコア（２）１１がランタイムライブラリ２００を実行し、ランタイムライブラリ２００が複数の基本モジュール１０１の中から基本モジュールを呼び出すさまを模式的に示している。

また、図８において、五角形の図形はランタイムライブラリ２００を示し、太い矢印線は基本モジュールを示している。太い矢印線の長さは基本モジュールの実行時間を示している。

次に、図９に、オペレーティングシステム（ＯＳ）によるスレッドのスケジューリング粒度と、ランタイムライブラリ２００がスケジュールするタスクの粒度の違いを示す。粒度とは、処理単位の大きさのことである。粒度を細かくする方が、並列化の機会を増やすことが可能となるので、並列性能を向上することができる。

ランタイムライブラリ２００は、基本モジュール（タスク）をそれぞれのスレッドを識別するためのスレッドｉｄが割り当てられているスレッドに割り当てることによって、プログラムを実行する。

ＯＳは、プロセスの切替えを行なうための、ＣＰＵ、実行時間の最小単位であるタイムクォンタムごとにスレッドを再スケジュールする。これはスレッド切換えのオーバーヘッドを考慮して十分大きなタイムクォンタムで処理する。一方で、ランタイムライブラリ２００が提供するタスクの並列スケジューリングは、割り込みを必要とせず、細かい粒度でのスケジューリングが可能である。ランタイムライブラリ２００がタスクを細かく分けることによって、より並列化のチャンスが多くなる。このとき、ランタイムライブラリ２００のタスクスケジューラは、タスク間のデータの移動が、できるだけコアをまたがらないように制御することが出来れば、タスク内で参照するデータアクセス時にキャッシュミスを抑えることが可能である。

しかし、通常はアプリからコア番号を得るには特殊な処理を必要とするし、動いている間にスレッドが別のコアに移動することもあるので、アプリから実行コアを特定するのは困難が伴う。そこで、出来るだけコア間でデータ転送が起こらないようにすることを、出来るだけスレッド間でデータ転送が起きないようにすることで代用する。

この方針でも性能に大差がないことは、スレッドとタスクのスケジュール頻度の違いによって保障される。仮にタスクの粒度が大きい場合においては、各スレッドを出来るだけ１つのコア上で動き続けさせるアフィニティの指定を行えば、“スレッド間でのデータの転送を出来るだけ減らす”ということで、コア間のデータ転送を減らすという目的を達成することができる。

図１０（Ａ）に、ランタイムライブラリ２００が管理するグラフデータ構造を示す。ランタイムライブラリ２００は、このグラフデータ構造（データフロータスクグラフ）を生成して、タスクに相当するノードをプロセッサに割り当てることによって、並列処理を実行する。実際には、プログラム起動時に必要な数だけスレッドを起動し、各スレッドが、このグラフデータ構造の中から実行可能なノードをＲｅａｄy集合（実行可能集合）のなかから選択してノードに対応するタスクを実行し、タスク終了時にノードの依存関係に従って、実行可能となるノードをＲｅａｄy集合に挿入すると同時に、データフローに繋ぐべき新たなノードを生成することを繰り返す。

本実施形態は、このＲｅａｄy集合の中からノードを選択する際に、各プロセッサのキャッシュやローカルメモリが保持するデータを、できるだけコア間で移動することがないように、ノードを選択する方法を提供する。

次に、ノード選択時の転送コストを計算するための式を式（１）に示す。

式（１）の意味を図１０（Ｂ）を参照して説明する。図１０（Ｂ）は、図１０（Ａ）のグラフデータ構造の一部を切り出したグラフデータ構造である。図１０（Ｂ）に示すように、ノードａ、ノードｂ、ノードｃ、およびノードｄがある。ノードｃがＲｅａｄy集合の中から選択されるカレントノードである。

ノードｎは、カレントノードｃがデータを参照するノードの集合Ｐｒｅｄ（ｃ）である。図１０（Ｂ）に示すグラフデータ構造の場合、ノードｎはノードａおよびノードｂであり、Ｐｒｅｄ（ｃ）はＰｒｅｄ（ｃ）＝｛ａ，ｂ｝と記述される。ｓｉｚｅ（ｎ）は、ノードｃが参照するノードｎの計算結果のデータサイズであり、グラフデータ構造２０２中のノードにそれぞれ定義されている。

Cost(tid, c)は、被割り当て対象であるスレッドtidに、ノードｃを割り当てたときの、ノードｃの入力データの転送コストである。trCost(n→tid, tid)は、ノードｎを実行したスレッドｎ→tidからスレッドtidへのデータ転送コストであり、スレッドn→tidとスレッドtidが等しい場合に、trCostは０となる。また、スレッドn→tidとスレッドtidとが異なる場合に、trCostを１とする。

ＯＳのスレッドスケジューラがコアへの割り当てにおいてアフィニティを指定できれば、コアの階層構造に応じて、trCostの値を、各スレッドが動作するコアとコアの間の転送コストとして定義することもできる。

図１１は、ランタイムライブラリ２００の機能ブロック図である。

ランタイムライブラリ２００は、図１１に示すように、実行スレッド管理部２１０、Ｒｅａｄｙ集合管理部２２２、転送コスト計算部２２３、ノード選択部２２５、およびノード割り当て部２２４を有している。

ノード割り当て部２２４は、後述するノード選択部２２５から指示されたノードをスレッドに対して割り当てる処理を実行する。実行ノード管理部２２１は、ノード割り当て部２２４がスレッドに割り当てたノードおよび割り当てられたスレッドを示すスレッドｉｄを管理する。より具体的には、グラフデータ構造２０２中の実行済みのノードに対して、ノードを実行したスレッドを示すスレッドｉｄを割り当てる。

Ｒｅａｄｙ集合管理部２２２は、グラフデータ構造２０２を参照することによって、処理が可能なノードを検出し、検出したノードをＲｅａｄｙ集合に加える。また、Ｒｅａｄｙ集合管理部２２２は、Ｒｅａｄｙ集合中の処理済みのノードをＲｅａｄｙ集合から削除する。

転送コスト計算部２２３は、前述した式（１）の計算を行い、計算結果をノード選択部２２５に通知する。ノード選択部は、通知された転送コストが最小なノードを選択し、選択したノードをスレッドに割り当てるべきノードとしてノード割り当て部２２４に通知する。

図１２のフローチャートを参照して、Ｒｅａｄy集合からスレッドに割り当てるノード（基本モジュール）を選択する処理の手順を示す。
まず、ノード（基本モジュール）の処理が終了したらノードを実行していた転送コスト計算部２２３は、ノードを実行していたスレッドのスレッドid（＝スレッドtid）を取得する（ステップＳ１１）。そして、転送コスト計算部２２３は、グラフデータ構造２０２からＲｅａｄｙ集合に含まれるノードを検出し、検出された各ノードに対してCost(tid, c)を計算する。転送コスト計算部２２３は、計算結果をノード割り当て部２２４に通知する。ノード選択部２２５は、計算結果に基づいてCost(tid, c)が最小になるノードcをスレッドｔｉｄに割り当てるべきノードとして選択する（ステップＳ１２）。ノード割り当て部２２４は、選択されたノードｃをスレッドｔｉｄに割り当てる。

なお、このときランタイムライブラリ２００が管理するグラフデータ構造のノード情報に、スレッドtidのサイズ分の配列を用意しておき、Cost(tid, c)の計算結果をキャッシュしておく。キャッシュに計算結果があれば、Cost(tid, c)の計算を何度も行う必要がない。それでも別のスレッドがＲｅａｄy集合を探すたびに、式（１）の計算を行う必要がある。

先にＲｅａｄｙ集合は全てのスレッドに対して管理を行っていた。しかし、スレッド毎にＲｅａｄｙ集合の管理を行っても良い。図１３、図１４のフローチャートを参照して、
スレッド毎にＲｅａｄy集合を管理する場合のＲｅａｄy集合からスレッドに割り当てるノード（基本モジュール）を選択する処理の手順を説明する。
先ず、図１３のフローチャートを参照して、新たにＲｅａｄｙとなったノードをＲｅａｄｙ集合に登録する処理を説明する。先ず、転送コスト計算部２２３は、グラフデータ構造２０２から新たにＲｅａｄｙ集合に登録されたノードｃの情報を取得する（ステップＳ２１）。次ぎに、転送コスト計算部２２３は、実行中の全てのスレッドｉｄに対して、Cost(tid, c)を計算する。転送コスト演算／選択部２２３は、Cost(tid, c)が最小となるスレッドtidを選択する（ステップＳ２２）。なお、Cost(tid, c)を計算する場合、すべてのスレッドｉｄについて最小値を計算する代わりに、ノードｃが参照しているノードを計算したスレッドｉｄのみについて計算することで代用することができる。次に、Ｒｅａｄｙ集合管理部２２２は、ステップＳ２２において選択されたスレッドtidのＲｅａｄｙ集合にノードｃを登録する(ステップＳ２３)。

次に、図１４を参照してスレッドｔｉｄが登録されたＲｅａｄｙ集合から次に処理するノードを選択する処理の手順を説明する。先ず、ノード選択部２２５は、基本モジュールが終了したら基本モジュールを実行していたスレッドｉｄ（＝スレッドtid）を取得する(ステップＳ３１)。次に、ノード選択部２２５は、スレッドtidのＲｅａｄｙ集合中にノードが登録されているか否かを判別する（ステップＳ３２）。ノードが登録されている場合（ステップＳ３２のＮｏ）、ノード選択部２２５は、スレッドｔｉｄのＲｅａｄｙ集合からノードを選択する（ステップＳ３３）。ノードが登録されていない場合（ステップＳ３２のＹｅｓ）、ノード選択部２２５は、trCost(m→tid, tid)が最も小さいスレッドm→tidのＲｅａｄｙ集合からノードを集合する（ステップＳ３４）。

なお、ランタイムライブラリ２００は、ノードの処理にかかった実行時間を記録し、ノード単位でノードを呼び出したスレッドに対する実行時間を管理すると良い。そして、ランタイムライブラリ２００は、同一のノードにおいて、自身のスレッドが管理するノードの実行時間と、異なるスレッドが管理するＲｅａｄｙ集合から呼び出されたノードの実行時間との時間差を求め、求められた時間差に比例する値でデータサイズｓｉｚｅ（ｎ）を補正することが好ましい。この処理は、反復して実行されるノードに対して有用である。実質的な処理にかかる時間が同一であるとすると、求められた時間差は、スレッド間のデータの転送にかかった時間に等しいと考えられる。よって、データの転送時間とデータサイズが比例すると考えることによって、データサイズがより正確なサイズになる。その結果、式（１）で求められる転送コストがより実処理を反映するようになる。

これらの処理を実行するために、ランタイムライブラリ２００は、コア毎に基本モジュールの実行時間を記録する実行時間記録モジュールと、基本モジュール毎にコアに応じた実行時間を管理する実行時間管理モジュールと、実行時間管理手段が管理する実行時間からコア間の実行時間の差を演算する実行時間差演算モジュールと、実行時間差演算モジュールが演算した時間差からデータサイズ補正モジュールとを有することが好ましい。また、ランタイムライブラリ２００は、基本モジュールを呼び出した時間（ランタイムライブラリ２００が呼び戻された時間）と、基本モジュールの処理が終了し、再度ランタイムライブラリ２００が呼び出された時間の差によって実行時間を求める。なお、ランタイムライブラリ２００は、時間差を得るために、故意に異なるスレッドが管理するＲｅａｄｙ集合からノードを呼び出しても良い。

以上説明した処理によってスレッド毎に最適なノードを選択することができ、プログラムの実行中に動的にプログラムの並列処理を効率化することができる。

図１５および図１６に、ランタイムライブラリ２００によって、意図的にアフィニティを保つ場合、保たない場合の処理を行い、その差分を各ノード間のデータ転送コストとしてビジュアルに表示する例を示す。

図１５は、データ転送サイズを視覚化したグラフデータ構造を示している。図１５に示すように、ノード間を接続するエッジの太さを転送データサイズに応じて変えている。また、６５は、プロセッサ間のデータ転送コストを視覚化している。

このような表示により、プログラマはどのタスクとタスクの間でデータのやり取りが多いかを直感的に理解することが可能となり、並列処理のプログラムの分割方法のチューニング、見直しの作業を効率よく進めることが可能となる。逆に、ノード間の転送データサイズが事前にわかる場合は、この差分データを転送データサイズで割った値を使って、プロセッサ間の転送コストの違いを視覚化することが可能である。

また、意図的に、同一スレッドに割り当てた場合と、別スレッドに割り当てた場合の性能差を測定することによって、タスク間のデータの転送サイズを見積もることが出来る。このデータをフィードバックして割り当てスケジュールに反映させるという手順も考えられる。

また、ここでは、本コンピュータが、コア１１を複数内蔵するプロセッサ１を搭載する場合を例に本手法を説明したが、本手法は、複数のプロセッサ１を搭載するいわゆるマルチプロセッサコンピュータにおいても当然に適用できる。

本実施形態では、タスクを、データフローで繋ぐグラフデータ構造を管理するランタイムライブラリにおいて、プログラマの指定なしで、プログラム実行時に並列処理環境に適応して、タスク割り当てのアフィニティ向上を実現することが可能になる。また、プログラマが意図していないようなデータの定義参照関係が存在する場合や、実行時にしか判明しないデータ移動のコストに対しても、適応的に最適なタスクのスケジューリングを行うことが可能であり、データアクセスのキャッシュミスやローカルメモリ間のデータ移動を抑制して、並列プログラムの実行速度向上を実現することが可能になる。

なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。

１…プロセッサ，２…主メモリ，３…ハードディスク駆動装置，３…ＨＤＤ，１１…コア，１００…実行プログラム，１０１…直列基本モジュール，１０２…並列実行制御記述，２００…ランタイムライブラリ，２０１…グラフデータ構造生成情報，２０２…グラフデータ構造，２２１…実行ノード管理部，２２２…Ｒｅａｄｙ集合管理部，２２３…転送コスト計算部，２２４…ノード割り当て部２２４，２２５…ノード選択部。

Claims (7)

1. それぞれ識別子が与えられた複数のスレッドを実行する複数の実行ユニットと、
   他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムを、前記複数の実行ユニットによって並列実行するために、前記実行規則に基づき、前記複数の実行ユニットが実行するスレッドに対する前記複数の基本モジュールの動的な割り当てを制御するスケジューラと、
   を具備し、
   前記スケジューラは、
   前記実行ユニットによって実行済みの基本モジュールを実行したスレッドの識別子を管理する手段と、
   前記実行ユニットによって実行可能な基本モジュールを実行可能集合として管理する手段と、
   前記実行可能集合中の各基本モジュールについて、前記基本モジュールがデータを参照する前記実行済みの基本モジュールの計算結果のデータサイズおよび当該実行済みの基本モジュールを実行したスレッドの識別子に基づいて、実行済みの基本モジュールを実行したスレッドから複数のスレッドから選ばれる一つのスレッドtidにデータを転送した場合の転送コストをそれぞれ計算するコスト計算手段と、
   前記転送コストが最小の基本モジュールを前記スレッドtidに割り当てる基本モジュールとして選択する選択手段と
   を具備し、
   前記転送コストは、
   

   

   によって演算される、
   ここで、Ｐｒｅｄ（ｃ）は前記実行可能集合中の基本モジュールから選ばれる一つの基本モジュールｃがデータを参照する基本モジュールｎの集合を示し、ｓｉｚｅ（ｎ）は前記基本モジュールｎによる計算結果のデータサイズ、ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は前記基本モジュールｎを実行したスレッドｎ→tidからスレッドtidへのデータ転送コストである、
   ことを特徴とする情報処理装置。
2. 前記スレッドｎ→tidと前記スレッドtidとが同じスレッドである場合、前記ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は０であることを特徴とする請求項１に記載の情報処理装置。
3. 前記スレッドｎ→tidと前記スレッドtidとが異なるスレッドである場合、前記ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は０より大きい値であることを特徴とする請求項１に記載の情報処理装置。
4. 前記複数の実行ユニットは、１つのＣＰＵに内蔵されるＣＰＵコアであることを特徴とする請求項１記載の情報処理装置。
5. 前記複数の実行ユニットは、それぞれが個別に構成された複数のＣＰＵであることを特徴とする請求項１記載の情報処理装置。
6. 他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムから複数の基本モジュールをそれぞれ識別子が与えられた複数のスレッドに動的に割り当て、当該複数のスレッドを複数の実行ユニットによって並列実行する情報処理装置によって実行される並列処理最適化方法であって、
   前記情報処理装置が、前記実行ユニットによって実行済みの基本モジュールを実行したスレッドの識別子を管理し、
   前記情報処理装置が、前記実行ユニットによって実行可能な基本モジュールを実行可能集合として管理し、
   前記情報処理装置が、前記実行可能集合中の各基本モジュールについて、前記基本モジュールがデータを参照する前記実行済みの基本モジュールの計算結果のデータサイズおよび当該実行済みの基本モジュールを実行したスレッドの識別子に基づいて、実行済みの基本モジュールを実行したスレッドから複数のスレッドから選ばれる一つのスレッドtidにデータを転送した場合の転送コストをそれぞれ計算し、
   前記情報処理装置が、前記転送コストが最小の基本モジュールを前記スレッドtidに割り当て、
   前記転送コストは、
   

   

   によって演算される、
   ここで、ｎPred(c)は前記実行可能集合中の基本モジュールから選ばれる一つの基本モジュールｃがデータを参照する基本モジュールｎの集合を示し、ｓｉｚｅ（ｎ）は前記基本モジュールｎによる計算結果のデータサイズ、ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は前記基本モジュールｎを実行したスレッドｎ→tidからスレッドtidへのデータ転送コストである、
   ことを特徴とする並列処理最適化方法。
7. 他のモジュールと非同期に実行可能な複数の基本モジュールに分割され、当該複数の基本モジュールの時系列的な実行規則が定義されるプログラムから複数の基本モジュールをそれぞれ識別子が与えられた複数のスレッドに動的に割り当て、当該複数のスレッドを複数の実行ユニットによって並列実行する情報処理装置情報処理装置を、
   前記実行ユニットによって実行済みの基本モジュールを実行したスレッドの識別子を管理する手段と、
   前記実行ユニットによって実行可能な基本モジュールを実行可能集合として管理する手段と、
   前記実行可能集合中の各基本モジュールについて、前記基本モジュールがデータを参照する前記実行済みの基本モジュールの計算結果のデータサイズおよび当該実行済みの基本モジュールを実行したスレッドの識別子に基づいて、実行済みの基本モジュールを実行したスレッドから複数のスレッドから選ばれる一つのスレッドtidにデータを転送した場合の転送コストをそれぞれ計算するコスト計算手段と、
   前記転送コストが最小の基本モジュールを前記スレッドtidに割り当てる基本モジュールとして選択する選択手段と
   として機能させ、
   前記転送コストは、
   

   

   によって演算される、
   ここで、ｎPred(c)は前記実行可能集合中の基本モジュールから選ばれる一つの基本モジュールｃがデータを参照する基本モジュールｎの集合を示し、ｓｉｚｅ（ｎ）は前記基本モジュールｎによる計算結果のデータサイズ、ｔｒＣｏｓｔ（ｎ→ｔｉｄ，ｔｉｄ）は前記基本モジュールｎを実行したスレッドｎ→tidからスレッドtidへのデータ転送コストである、
   プログラム。

Images