JP5036523B2 - プログラム並列化装置 - Google Patents

Description

この発明は、並列化したプログラムを実行する並列処理装置に対して、プログラムを並列に実行可能な複数のタスクに自動的に分割するプログラム並列化装置に関するものである。

プログラム並列化装置では、一般に一つのプログラムを複数のタスクに分割し、複数のプロセスエレメント上で並列に実行するため、プログラムの演算対象である変数に関して読み出しと書き込みに関するフロー依存、逆依存、出力依存の各依存関係からデータ依存を解析し、タスク間の先行制約を抽出し、分割したプログラムに対して同期命令を組み込むことで、プロセスエレメントに割り付けたタスク間の先行制約を守り、演算結果の整合性を保証する。

このようなプログラム並列化装置において、従来の装置では、一つの仮想マシンコードを一つのタスクとして扱い、プログラムを並列に実行可能なタスクに分割し、複数のプロセッサにタスクスケジュールを行った後、タスクの結合が可能なときには、タスクを結合し再度タスクスケジュールをすることで、同期処理によるオーバーヘッドを小さくするようにしたものがあった（例えば、特許文献１参照）。

また、従来のプログラム並列化装置として次のような装置があった。即ち、実行プロセッサが指定されているタスクを含む各タスクの依存関係を示すタスクグラフに基づいて、各タスクのタスクスケジューリングを各タスクの実行前に行う静的なタスクスケジューリングシステムにおいて、各タスクから終端のタスクに至るまでのパス長が長いタスクに高い優先度が与えられ、優先度の高い順に登録される順方向リストと、終端のタスクから各タスクに至るまでのパス長が長いタスクに高い優先度が与えられ、優先度の低い順に登録される逆方向リストを持つようにしたものがあった（例えば、特許文献２参照）。そして、このようなプログラム並列化装置では、スケジューリングする際に、順方向リストか逆方向リストかのいずれかのリストを選択し、選択されたリストに基づいて各タスクの実行時刻を決定する。このようなプログラム並列化装置は、各プロセッサの最優先タスクの状況によって、順方向と逆方向のタスクスケジューリングを適宜行うため、タスクの待ち状態を少なくして、プロセッサの使用効率を向上させることができる。

特許第３０３９９５３号公報 特開２００３−２９９８８号公報

しかしながら、プログラムを複数のタスクに分割して複数のプロセスエレメントに割り付けるタスクスケジューリングを行う際に、従来のプログラム並列化装置では実行効率の高い割り付けを行っているとは言えなかった。

即ち、並列化した後のプログラムの全体の実行時間は、最も処理時間が長いプロセスエレメントの処理時間によって決まる。機器に組み込んで、その機器の制御を行うプログラムの場合、そのプログラムは実行を終えた時点で、外部との入出力によってデータの更新が必要であるため、分割後に割り付けたプログラムの処理が早く終了したプロセスエレメントだけを、他のプロセスエレメントに先行して、次の処理周期に進めることができない。処理が早く終了したプロセスエレメントは、最も処理時間を必要とするプロセスエレメントでの処理が終了するまで、待機する必要がある。その結果、先に処理を終えたプロセスエレメントは、次の周期の処理を開始するまでの間、空き時間が発生することになる。タスクスケジューリングの結果、全てのプロセスエレメントが同時に処理を終了するように各プロセスエレメントに対して処理が割り付けられていれば良いが、ある一つのプロセスエレメントのみがその他のプロセスエレメントより処理時間が長くなるようなスケジューリング結果となった場合、その他のプロセスエレメントは、その一つのプロセスエレメントが処理を終了するまでの間、待機することになり、複数のプロセスエレメントの実行効率が低くなるという問題があった。

上記の問題は、プロセスエレメントに割り当てた処理の最後の部分についての問題であるが、同様の問題はプロセスエレメントに割り当てた処理の途中の時点でも発生する場合がある。あるプロセスエレメントに割り当てたタスクが、他のプロセスエレメントに割り付けたタスク（先行タスクと呼ぶ）に含まれる変数に対してデータ依存の関係にある場合、他のプロセスエレメントに割り付けた先行タスクの完了を待機する必要がある。このため、先行タスクの完了を待機する間にも、空き時間が発生するという問題があった。後続のタスクの中で、データ依存がなく、かつコントロールフローの点からも制約がないタスクを、この空き時間に割り当てることによって、空き時間をなくすことも可能である。しかし、これは、後続のタスクにそのような条件が成り立つタスクが存在する場合であって、条件が成立するタスクが存在しない場合は、先に述べたようにプロセスエレメントの処理に空き時間が発生し、そのプロセスエレメントの実行効率が低下するという問題が同様に発生する。

例えば、特許文献１に記載された装置のように、一つの仮想マシンコードを一つのタスクとして扱い、プログラムを並列に実行可能なタスクに分割し、複数のプロセッサにタスクスケジュールを行った後に、結合が可能なタスク同士を結合した後、改めてスケジューリングを行う方法では、空き時間が少なくなるようにスケジューリングされるため、プロセスエレメントの実行効率は改善されるが、スケジューリングを行う回数が多く、演算量が増えるという問題があった。

また、組み込み機器の制御プログラムでは、実行条件とその条件下での処理の組み合わせの連続によってプログラムを構成できる。特許文献１に記載された装置でのタスクの扱いに基づいて、このようなプログラムの１マシンコードを１タスクとして扱おうとすると、個々のマシンコードに対して実行条件を考慮してタスクの結合の可否を判断する必要がある。実行条件が異なるタスクは一つのタスクとして結合できないためである。その結果、このような制御プログラムの場合、タスクを結合する際に実行条件を考慮に入れるため、演算量が増えるという問題があった。

また、特許文献２に記載された装置では、各タスクの依存関係を示すタスクグラフに基づいて、実行前にスケジューリングを行う静的なタスクスケジューリングシステムにおいて、優先度の高い順にタスクが登録された順方向リストと、優先度の低い順にタスクが登録された逆方向リストを用い、各プロセッサの最優先タスクの状況によって、順方向リストと逆方向リストを選択してタスクスケジューリングを行う。これにより、タスクの待ち状態である空き時間を削減できるとしている。しかし、データの依存性を持つタスク間では、依然としてこの方法では解決できない空き時間が発生するという問題があった。

この発明は上記のような課題を解決するためになされたもので、プロセスエレメントの空き時間を削減してプログラムの実行効率を改善し、最大実行時間を短縮することのできるプログラム並列化装置を得ることを目的とする。

この発明に係るプログラム並列化装置は、複数のプロセスエレメントで、実行条件とその条件下での処理内容の対で構成されるタスクの並列処理を行う並列処理装置において、複数のプロセスエレメントのそれぞれは、次の命令を実行するか否かを決定するための真偽値を格納するプレディケートレジスタと、他のプロセスエレメントから受信した次の命令を実行するか否かを決定するための真偽値が付いたプレディケート付き同期イベントを格納するプレディケート受信レジスタと、タスクの実行条件判定結果を他のプロセスエレメントで実行されるタスクに対して通知するタスクを実行する場合は、プレディケートレジスタの真偽値が付いたプレディケート付き同期イベントを他のプロセスエレメントに通知し、他のプロセスエレメントで実行されるタスクの実行条件判定結果に基づいて実行されるタスクを実行する場合は、プレディケート付き同期イベントの受信レジスタの真偽値に基づいて当該自身のタスクを実行する命令実行部とを備えた並列処理装置に対して、プログラムを複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、プログラムに含まれるデータの依存関係を解析する解析部と、解析部の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、分割したタスクを、複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、スケジューリング部でスケジューリングを行った結果、スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、タスク分割部がタスクの処理を複数のプロセスエレメントに対応して一つのタスクを複数のタスクへ再分割すると共に、コード生成部が、分割したタスクの処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するようにしたものである。

この発明のプログラム並列化装置は、プログラムに含まれるデータの依存関係を解析する解析部と、解析部の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、分割したタスクを、複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、スケジューリング部でスケジューリングを行った結果、スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、タスク分割部がタスクの処理を複数のプロセスエレメントに対応して一つのタスクを複数のタスクへ再分割すると共に、コード生成部が、分割したタスクの処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するようにしたので、プログラムの実行効率を改善し、最大実行時間を短縮することができる。

実施の形態１．
図１は、この発明の実施の形態１による並列処理装置を示す構成図である。
図において、並列処理装置は、プロセッサ１と外部メモリ５およびこれらを相互に接続するためのバス６から構成されている。プロセッサ１は、二つ以上のプロセスエレメント（実施の形態１ではプロセスエレメント（ＰＥ）＃０（２）、＃１（３）の２台）と内蔵メモリ４からなる。これらプロセスエレメント＃０（２）、＃１（３）は、それぞれ、プレディケートレジスタ７，１２、プレディケート受信レジスタ８，１１、命令実行部９，１３、同期機構１０，１４を備えている。

プレディケートレジスタ７，１２は、それぞれのプロセスエレメント＃０（２），＃１（３）において、次の命令を実行するか否かを決定するための真偽値を格納するレジスタである。これらのプレディケートレジスタ７，１２の値は、プロセスエレメント＃０（２），＃１（３）上での演算によって値が変化する。例えば、変数間の比較命令の結果が一致しない場合や、大小比較命令の結果が不成立の場合にこのレジスタの値が偽になる。一方で、変数間の比較命令の結果が一致したり、大小比較命令の結果が成立した場合には、このレジスタの値が真になる。
プレディケート受信レジスタ８，１１は、他のプロセスエレメントで実行された命令の結果（真偽値）を受信するためのレジスタである。即ち、プレディケート受信レジスタ８は、プロセスエレメント＃１（３）による命令実行結果を、また、プレディケート受信レジスタ１１は、プロセスエレメント＃０（２）による命令実行結果を受信する。

命令実行部９，１３は、自身に割り当てられたタスクの実行結果が、他のプロセスエレメントに割り当てられているタスクに同期している場合は、自身のタスクに対応した同期イベントを他のプロセスエレメントに通知すると共に、他のプロセスエレメントで実行されるタスクの同期イベントに基づいて実行されるタスクを実行する場合、その同期イベントの受信に基づいて自身のタスクを実行し、かつ、タスクの実行条件判定結果を他のプロセスエレメントで実行されるタスクに対して通知するタスクを実行する場合は、プレディケートレジスタ７，１２の真偽値を、他のプロセスエレメントに通知すると共に、他のプロセスエレメントで実行されるタスクの実行条件判定結果に基づいて実行されるタスクを実行する場合は、プレディケート受信レジスタ８，１１の真偽値に基づいて自身のタスクを実行するよう構成されている。

即ち、これらの命令実行部９，１３は、条件付き実行命令をサポートしている。条件付き実行命令の実行は、プレディケートレジスタ７，１２の値に依存する。プレディケートレジスタ７，１２には、真偽のいずれかの値が格納されるが、このプレディケートレジスタ７，１２の値が真の場合は、読み出した条件付き実行命令を実行して、その演算結果を内蔵メモリ４に書き込む。一方、プレディケートレジスタ７，１２の値が偽の場合は、読み出した条件付き実行命令を実行せず、次の命令を読み出す。

同期機構１０，１４は、プロセッサ１上の複数のプロセスエレメント＃０（２），＃１（３）間で、同期をとるための仕組みであり、自身のプロセスエレメントから通知されている同期イベントを待機する命令と、他のプロセスエレメントから通知された同期イベントの命令により、これらのプロセスエレメント間の同期を行う。
即ち、各プロセスエレメント＃０（２），＃１（３）は、他のプロセスエレメントに対して同期イベントを通知する命令を持つ。この同期イベントには、固有の番号が付けられる。この同期イベントの固有の番号は、後述するプログラム並列化装置２０がプログラム３０を分割する際に、静的に決定し、対応する命令をマシンコード３１に組み込むものである。尚、プログラム３０およびマシンコード３１についても後述する。

例えば、プロセスエレメント＃１（３）がプロセスエレメント＃０（２）からの同期イベントを待機する場合は、プロセスエレメント＃１（３）の同期機構１４は、例えば”ＷＡＩＴＥＶ ０”という命令で待機し、プロセスエレメント＃０（２）は、例えば”ＳＥＮＤＥＶ ０”という命令で同期イベントを同期機構１４に通知する。待機しているプロセスエレメント＃１（３）が、対応する同期イベントを受信すると、待機しているプロセスエレメント＃１（３）が持つ同期機構１４がそれを認識し、この場合は、プロセスエレメント＃１（３）の実行処理を再開する。プロセスエレメントの処理は、”ＷＡＩＴＥＶ ｎ”（ｎは整数）が呼び出された時点で、対応する同期イベントがシステム上の外のプロセスエレメントが発行するまで待機する。

また、プロセッサ１における内蔵メモリ４は、外部メモリ５に格納されているプログラムやデータを保持し、かつ、命令実行部９，１３によって実行結果が書き込まれるメモリである。即ち、プロセッサ１上の各プロセスエレメント＃０（２），＃１（３）は外部メモリ５上の対応するプログラム領域からマシンコード３１を読み出し、内蔵メモリ４から値を読み出して演算を行い、内蔵メモリ４上の変数に結果を書き込む。尚、内蔵メモリ４はアービトレーション機能を持ち、プロセスエレメント＃０（２），＃１（３）からの一つの変数へのアクセスは排他的に行われる。
この例では、マシンコード３１を外部メモリ５上に配置しているが、プロセッサ１内部に存在する内蔵メモリ４上に配置してもよい。また、内蔵メモリ４上に配置されている変数は、外部メモリ５上に配置することもできる。尚、外部メモリ５もアービトレーション機能を持ち、アクセスが排他的に行われる。また、バス６は、プロセッサ１と外部メモリ５とを相互に接続するためのバスである。

また、図１では、プロセッサ１に含まれるプロセスエレメントが２個の場合について示しているが、３個以上存在しても良い。この場合、各プロセスエレメントが持つ同期機構とプレディケートレジスタは、それぞれ自プロセスエレメント以外の全てのプロセスエレメントと接続される。

次に、プログラム並列化装置について説明する。
図２は、プログラム並列化装置の構成図である。
図示のプログラム並列化装置２０は、解析部２１、タスク分割部２２、スケジューリング部２３、コード生成部２４を備えている。

解析部２１は、入力されたプログラム３０について、字句解析、構文解析を行い、中間コードへ変換する。中間コードとしては、例えば四つ組が挙げられる。また、解析部２１は、プログラム３０内で表現されている演算内容とその順序に基づいて、変数間の依存性の解析を行うよう構成されている。タスク分割部２２は、中間コードで表現されたプログラムを複数のタスクへ分割する。タスクの単位としては、基本ブロックや、実行条件とその条件下での処理を一まとまりとしたものが挙げられる。尚、基本ブロックとは、途中に分岐がなくプログラムが記述された順に連続して実行されるプログラムの単位である。これらを単位としたタスクについて、タスク分割部２２では、変数間の依存性の解析結果を基に、タスク間の実行順序制約を求める。

スケジューリング部２３は、タスク分割部２２においてタスクに分割されたプログラムを、複数のプロセスエレメントに対して割り付ける機能部である。スケジューリング方式としては、クリティカルパス法が挙げられるが、いずれのスケジューリング・アルゴリズムでも採用することができる。ただし、実施の形態１では、各タスクの処理時間を評価関数とするクリティカルパス法に基づいたスケジューリングについて説明する。スケジューリングは、先のタスク間の実行順序制約に基づいて行われる。コード生成部２４は、スケジューリング部２３で複数のプロセスエレメントへ割り付けられた個々のタスクについて、実行するプロセスエレメントのマシンコード３１を生成する機能部である。このコード生成の際に、タスク間での変数についての依存性がプロセスエレメント間にわたる場合は、異なるプロセスエレメント間で実行順序を守る必要があるため、コード生成部２４ではその箇所に同期命令を追加するよう構成されている。

尚、プログラム並列化装置２０はコンピュータによって実現され、解析部２１〜コード生成部２４に対応したソフトウェアと、これらのソフトウェアを実行するためのＣＰＵやメモリ等のハードウェアから構成されている。あるいは、解析部２１〜コード生成部２４は専用のハードウェアから構成されている。
また、プログラム並列処理装置２０と図１に示した並列実行装置とは、例えば、ネットワークケーブルやＵＳＢケーブルによって接続され、プログラム並列化装置２０によって並列化されたプログラムを、並列実行装置のプログラムを格納する外部メモリ５へ転送するよう構成されている。

次に、実施の形態１のプログラム並列化装置と並列処理装置の動作について説明する。
例えば、あるプログラムを、実行条件とその条件下での処理のまとまりを一つのタスクとして扱った場合のタスク間の依存関係が、図３で表現されるようなプログラムを対象に説明する。図３は、プログラムの一部であり、その前後には他のタスクが存在していても良い。
図３の各ノードはタスクを表し、円の中の数字はタスクの番号である。また、円の右の数値はそのタスクの処理時間を数値で表現したものである。更にノード間の矢印は、タスク間の先行制約を表現している。例えば、タスク２はタスク１が終了するまで処理を開始することができず、タスク４はタスク２とタスク３が終了するまで処理を開始することができない。

以下では、各タスクは実行条件とその条件下での処理内容の対で表現されているとし、各タスクの先頭には必ず実行条件の判定が存在するとものとして扱う。尚、プログラムを記述する言語としては、実行条件とその条件下での処理が記述できる言語であれば何でも良く、対象となる言語が限定される訳ではない。

以下、図３で示されるタスク構成を持つプログラムを、プログラム３０としてプログラム並列化装置２０に入力した際の処理の流れについて図４を用いて説明する。
プログラム並列化装置２０は、プログラム３０を入力として受けると、解析部２１で字句解析・構文解析を行い中間コードを生成する（ステップＳＴ１）。このとき、タスク分割部２２によって図３に示すタスク間の依存関係を求める（ステップＳＴ２）。次に、スケジューリング部２３において、図３に示すタスクの依存性解析結果と各タスクの処理時間から、例えばクリティカルパス法を用いて、プロセスエレメントに対してタスクの割付を行う（ステップＳＴ３）。二つのプロセスエレメントに対して、図３のタスク構成を割り付けた例を図５に示す。

図５では、プロセスエレメント＃０（２）に対してタスク１、タスク２、およびタスク４を割り付け、プロセスエレメント＃１（３）に対してタスク３を割り付けている。尚、タスク３の実行はタスク１の終了を待つ必要があるため、これらのタスク間に同期イベントの受け渡しを行う命令を追加する。つまり、タスク３の先頭にタスク１からの同期イベントを待機する命令を追加し、タスク１の最後にタスク３への同期イベントを通知する命令を追加する。尚、ここでは、同期に要する時間を１としている。このため、タスク１、タスク２及びタスク４の処理時間の合計に、タスク１からタスク３への同期イベントの受け渡し時間１を加算した６５がこのスケジューリングによる処理時間である。全てのタスクを一つのプロセスエレメント上で順に処理した場合の処理時間は、全てのタスクの処理時間の合計である８４になるため、並列化によって処理時間が短縮されている。

同期イベントは、同期イベント通知命令”ＳＥＮＤＥＶ ｎ”および同期イベント待機命令”ＷＡＩＴＥＶ ｎ”で表現する。尚、ｎは整数で、イベントの番号を意味する。即ち、ＷＡＩＴＥＶ命令でイベントを待機する側は、指定したイベント番号の同期イベントが通知されるまで、処理を待機する。一方、同期イベントを通知する側は、同期イベントを通知すべき相手を、イベント番号で特定する。
同期イベントの通知では、一つの同期イベント通知命令が、複数の同期イベント待機命令に対して、ある一つの同期イベントをブロードキャストしてもよい。
また、プレディケート付き同期イベントは、例えば同期イベント通知命令“ＳＥＮＤＥＶ＿ＰＤ ｎ”およびプレディケート付き同期イベント待機命令“ＷＡＩＴＥＶ＿ＰＤ ｎ”で表現する。

スケジューリング部２３において、プロセスエレメントへのタスクの割り付けを終えると、スケジューリングした結果について、プロセスエレメント間の通信オーバーヘッドに要する時間よりも長い時間に渡って、タスクが割り付けられておらず、空いた時間が存在するかどうかを確認する（ステップＳＴ４）。空き時間の確認は、スケジューリング結果を、先頭から順に走査し、タスクが割り当てられていない時間を抽出することで行う。
図５の例では、タスク４をプロセスエレメント＃１（３）が実行している間、プロセスエレメント＃０（２）にはタスクが割り当てられておらず、空き時間が存在する。そこで、タスク分割部２２によるタスク再分割（ステップＳＴ５）に分岐し、タスクの再分割を行う。

図６は、図４におけるタスクの再分割（ステップＳＴ５）の処理の流れを示すフローチャートである。
先ず、空き時間を持つプロセスエレメントについて、空き時間の処理開始からの時刻とその時刻に空き時間を持つプロセスエレメントの数を求める（ステップＳＴ１１）。次に、その時刻で処理を分割することができるタスクが存在するかを確認する（ステップＳＴ１２）。このとき、タスクの処理時間が短く、分割して並列化するより、並列化による同期イベントの受け渡しのオーバーヘッドが大きくなる場合は、分割可能なタスクが存在しないと判断して処理を終了する。一方、図５のタスク４のように、同期イベントの受け渡しのオーバーヘッドに対して処理時間が長いタスクが存在する場合は、ステップＳＴ１３に移行して、分割可能なタスクの処理を空き時間を持つプロセスエレメントの数で分割する。図５の例では、プロセスエレメントが二つ存在するため、タスク４の処理を二つに分割する。このようにタスクの処理を複数に分割する際には、処理の内部でのデータの依存性を確認し、依存性を持つ処理の間で分割することを避ける必要がある。その理由は、依存性を持つ処理を複数のプロセスエレメントに対して割り付けると、この依存性を保証するために、新たに同期イベントの受け渡しの命令を追加する必要があるためである。従って、異なるプロセスエレメントに分割する際には、依存性を持たない処理を割り付ける。依存性を持つ場合は、依存関係がある処理をまとめて一つのプロセスエレメントに配置し、残りの処理を別のプロセスエレメントに配置する。

図６に示す処理の流れに沿って、図５のタスク４を二つに分割し、タスク４−１とタスク４−２を生成する。尚、タスク４−１はタスク４の前半の処理を、タスク４−２はタスク４の後半の処理である。タスク４の実行条件判定の処理はタスク４−１に含まれる。そこで、タスク４−１で求めた実行条件であるプレディケートの値を、タスク４−２に通知する。

このようにタスクを再分割した際には、分割後のタスクの起動元タスクの同期イベントを発行する位置にプレディケート付き同期命令を追加する（ステップＳＴ１４）。更に、起動先の同期イベントの待機位置にプレディケート付き同期イベントを待機する命令を追加する（ステップＳＴ１５）。
以上がタスクを再分割する際のタスク分割部２２の処理である。

タスクを再分割した後は、新たなタスク構成に対して、スケジューリング部２３でスケジューリングを行う（図４におけるステップＳＴ３）。そして、スケジューリング結果の中にプロセスエレメントの空き時間が存在するかどうかを確認する（ステップＳＴ４）。このステップＳＴ４において、空き時間が存在する場合は、改めてタスクの再分割処理（ステップＳＴ５）を行う。
空き時間がない場合は、コード生成部２４でマシンコード３１の生成を行う（ステップＳＴ６）。コード生成部２４では、タスク間の依存関係に基づいて、同期イベントの受け渡しを行うための、同期イベント通知命令と同期イベントの待機命令を追加する。尚、タスクを再分割した際に追加したプレディケート付き同期命令が追加されたタスクについては、マシンコード３１を生成する際に、その命令をマシンコード３１中に組み込む。

尚、あるプロセスエレメントから特定のプロセスエレメントに対して、同期イベントの通知処理を繰り返すなど、冗長な同期イベントの受け渡しについては、マシンコード３１を生成する時点で必要最小限まで同期イベントを削除しても良い。
図５に示したスケジューリング結果の空き時間を短縮する目的で、図４及び図６に示した処理を実行した結果、図７に示すスケジューリング結果が得られる。
図７は、図５のタスク４の処理を二つのプロセスエレメントに分割することで、空き時間を削減し、プログラム全体の処理時間を短縮している。尚、タスク４の条件判定処理の時間を２とすると、この時間は分割できないため、プロセスエレメント＃１（３）上で処理を行う。この条件判定処理によって求められたプレディケートの値を、プロセスエレメント＃０（２）に割り付けられたタスク４−２に通知する。このように、タスクを分割した結果、全体の処理時間は、タスク１及びタスク２の時間とタスク４−２の時間（＝１９）に対し、条件判定の時間２と二つの同期命令の時間の合計の４７となる。

次に、上記プログラム並列化装置２０で生成された並列化プログラム（図７に示す状態のプログラム）が外部メモリ５に格納された場合の並列処理装置の動作について説明する。
並列処理装置のプロセスエレメント＃０（２）は、図７の左側のタスクであるタスク１、タスク２、タスク４−２のプログラムを順に実行する。また、プロセスエレメント＃１（３）は、図７の右側のタスクであるタスク３、タスク４−１のプログラムを順に実行する。
先ず、プロセスエレメント＃０（２）は、タスク１のプログラムをメモリ（内蔵メモリ４または外部メモリ５）から読み込んで処理を開始する。このとき、プロセスエレメント＃１（３）でもタスク３のプログラムを読み込んで処理を開始するが、先頭の命令が、タスク３の先頭にタスク１が終了した時点でプロセスエレメント＃０（２）から発行される同期イベントを待機する命令であるため、プロセスエレメント＃１（３）が持つ同期機構１４に、プロセスエレメント＃０（２）からのイベントを待機する設定を行い、そのイベントの待機状態となる。尚、この同期イベントには固有の番号が割り振られており、その番号を持つイベントが発行されるまで待機する。同期イベントの固有番号は、プログラム並列化装置２０のコード生成部２４によって、同期イベントの受け渡しが必要となる箇所に、同期イベントの送受信命令を追加する際に、それぞれの箇所について固有の番号を割り付けられている。

プロセスエレメント＃０（２）の命令実行部９は、タスク１の処理を完了すると、プロセスエレメント＃１（３）のタスク３が待機している同期イベントを同期機構１４に通知する。次に、プロセスエレメント＃０（２）の命令実行部９は、タスク２のプログラムを読み出し、その実行を開始する。
プロセスエレメント＃０（２）からの同期イベントを受けたプロセスエレメント＃１（３）は、同期機構１４によって受信した同期イベントが、待機状態を抜ける条件となる同期イベントであるかを判断する。この場合は、待機状態を抜け出す条件の同期イベントであるため、待機状態を抜け、命令実行部１３での処理を再開し、プログラム３の処理を開始する。プロセスエレメント＃０（２）の命令実行部９は、タスク２の処理が完了すると、タスク４−２のプログラムを読み出す。このプログラム４−２の先頭は、プロセスエレメント＃１（３）からのプレディケート付き同期イベントを待機する命令である。このため、プロセスエレメント＃０（２）の命令実行部９は、同期機構１０に待機する同期イベントを登録し、待機状態に移る。

プロセスエレメント＃１（３）の命令実行部１３は、タスク３の処理を終えると、タスク４−１の処理に移る。命令実行部１３は、タスク４−１の先頭部分の実行条件判定処理の実行を終えると、プログラム並列化装置２０によってプログラム上のその次の位置に追加されたプレディケート付き同期命令を実行する。このプレディケート付き同期命令は、命令が実行された時点でのプレディケートレジスタ１２の真偽の値を、同期イベントと共に、対象プロセスエレメントに対して通知する命令である。この場合、タスク４−１の実行条件判定の処理を終えた時点で、プレディケート付き同期命令を発行しているため、タスク４−１の実行条件判定処理終了時点でのプレディケートレジスタ１２の値をプロセスエレメント＃０（２）に対して同期イベントと共に通知する。ここで、プレディケートレジスタ１２の値はプレディケート受信レジスタ８に通知される。これは、タスク４−２の実行開始を指示すると共に、タスク４−２に含まれる条件付き実行命令に対して、実行する／しないを通知する処理になる。プロセスエレメント＃１（３）からの同期イベントとプレディケート値を受けたプロセスエレメント＃０（２）は、命令実行部９により、受け取ったプレディケート値に基づいて、タスク４−２の処理を開始する。

このように、プロセスエレメントへのタスク割り付けを行った後に、プロセスエレメントに空き時間が存在し、その時間に実行条件判定を行った後の処理を分割可能なタスクが存在する場合は、そのタスクの処理の部分を、空き時間を持つプロセスエレメントに対して割り付け、割り付けたプログラムの実行開始タイミングを通知する同期イベントの受け渡しの命令を追加すると共に、実行条件判定の結果を合わせて通知する機構を設けることによって、プログラム全体の処理時間を短縮することができる。

以上のように、実施の形態１のプログラム並列化装置によれば、プログラムを、実施の形態１の並列処理装置における複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、プログラムに含まれるデータの依存関係を解析する解析部と、解析部の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、分割したタスクを、複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、スケジューリング部でスケジューリングを行った結果、スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、タスク分割部がタスクの処理を複数のプロセスエレメントに対応して一つのタスクを複数のタスクへ再分割すると共に、コード生成部が、分割したタスクの処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するようにしたので、並列処理装置におけるプログラムの実行効率を改善し、最大実行時間を短縮することができる。

実施の形態２．
実施の形態２における並列処理装置とプログラム並列化装置の構成は実施の形態１と同様であるため、実施の形態１の図面を用いて説明する。

実行条件とその条件下での処理内容の一まとまりを一つのタスクとして扱った場合のタスク間の依存関係が図８に示されるようなプログラムを例に実施の形態２によるプログラム並列化装置２０の処理の流れと並列処理装置の動作について説明する。
図８は、プログラムの一部であり、その前後には他のタスクが存在していても良い。
図８において、実施の形態１と同様に、各ノードがタスクを表し、円の中の数値はタスクの番号を表す。また、円の右側の数値はそのタスクの処理時間である。更に、ノード間の矢印は、タスク間の先行制約を表現している。この例では、処理時間４のタスク３を実行するためには、処理時間が４０であるタスク１と処理時間が２０であるタスク２の両方のタスクが処理を完了していなければならない。

図８で示されるタスク構成を持つプログラムをプログラム並列化装置２０に入力すると、プログラムを解析し中間コードを生成した後、図８のようなタスクの単位に分割し、プロセスエレメントへのタスクの割り付けを行うスケジューリングを終了した時点で、図９のようなスケジューリング結果が得られる。プロセスエレメント＃０（２）上では、タスク１とタスク３を、プロセスエレメント＃１（３）上では、タスク２を実行する。このとき、プログラム全体の処理時間は、プロセスエレメント＃０（２）での処理時間となり、タスク１の処理時間とタスク３の処理時間を合わせた４４となる。

スケジューリングを終えると、いずれかのプロセスエレメント上にプロセスエレメント間の通信のオーバーヘッドを越える空き時間が存在するかを確認する（図４におけるステップＳＴ４）。この例では、プロセスエレメント＃１（３）において、タスク２を実行した後の時間が空き時間になっている。このため、プログラム並列化装置２０は、タスクの再分割の処理に入る。

タスクの再分割（図６参照）では、空き時間の時刻とその時刻に空き時間を持つＰＥの数を求める（ステップＳＴ１１）。その後、同時刻で処理を分割可能なタスクが存在するかを確認する（ステップＳＴ１２）。この例では、プロセスエレメント＃１（３）でタスク２の実行を完了した後の時間では、プロセスエレメント＃０（２）上でタスク１の処理を行っている。この処理は、タスク２の処理完了後２０の時間に渡って行われるため、分割可能なタスクの処理となる。そこで、分割可能なタスクの処理を割当可能なＰＥの数で分割する（ステップＳＴ１３）。この例では、タスク１をタスク１−１とタスク１−２に分割する。

そして、起動元タスクの同期イベント発行位置となるタスク１−１に含まれる実行条件判定の処理を終えた位置にプレディケート付き同期命令を追加する（ステップＳＴ１４）。次に、その同期イベントの通知先となるタスク１−２の先頭位置に、プレディケート付き同期イベントを待機する命令を追加する（ステップＳＴ１５）。このように、タスク１を前後二つに分割した状態で、再度スケジューリングを実施する。
その結果、プログラムは、図１０に示すようにプロセスエレメントに対して割り付けられる。ここで、分割されたタスク１−２は、タスク２の後にスケジューリングされている。この例では、タスク１とタスク２の間に依存関係がないため、どちらのタスクを先に実行しても問題はない。ただし、タスク１−２は、タスク１−１で行われる実行条件判定の処理結果であるプレディケート値を必要とするため、このプレディケート値が確定してから処理を開始するようにした方がプロセスエレメントの空き時間の発生を抑えられる。そのため、プロセスエレメント＃０（２）上で実行条件判定の処理を行っている時間に並行して、プロセスエレメント＃１（３）上ではタスク２の処理を行うようにタスクを割り付ける。

図１０のスケジューリング結果では、図９のタスク１の処理を二つのプロセスエレメントに分割することで、空き時間を削減し、プログラム全体の処理時間を短縮している。タスク１の実行条件判定の処理時間を４とした場合、図９のスケジューリング結果でのプログラム全体の処理時間が４４であるの対し、図１０に示すように、タスク１の処理の部分を分割して処理を並列化することにより、プログラム全体の処理時間を３５に短縮することができる。

次に、この実施の形態での並列処理装置の動作について説明する。
並列処理装置のプロセスエレメント＃０（２）は、図１０のタスク１−１のプログラムを実行する。また、プロセスエレメント＃１（３）は、図１０のタスク２のプログラムから実行を開始する。
プロセスエレメント＃０（２）が、タスク１−１の実行条件判定の処理を完了した時点で、プロセスエレメント＃１（３）に対して、プレディケート付き同期イベントを通知する。その後、プロセスエレメント＃０（２）は、タスク１−１の後続の処理を続けて行う。
プロセスエレメント＃１（３）は、開始時にタスク２のプログラムから実行を開始するが、タスク２の実行中にプロセスエレメント＃０（２）からプレディケート付き同期イベントを受信する。このとき、この同期イベント通知に対応する受信命令はまだ実行されていない。この同期イベントを受信する命令は、タスク２の処理が完了した後に実行するタスク１−２の先頭に存在するためである。このような場合、プレディケート付き同期イベントを受信したプロセスエレメント＃１（３）は、この同期イベントの番号を同期機構１４に保持すると共に、受信したプレディケートの値を、プレディケート受信レジスタ１１に保持する。

プロセスエレメント＃１（３）でのタスク２の処理が完了すると、引き続きタスク１−２の処理を開始する。このときタスク１−２の先頭は、先にプロセスエレメント＃０（２）から送信されたプレディケート付き同期イベントを受信する命令である。そこで、プロセスエレメント＃１（３）の命令実行部１３は、同期機構１４に対してそのイベントを既に受信しているかを確認する。この例では、既に対象となるプレディケート付き同期命令を受信しているため、後続の処理をそのまま継続する。プロセスエレメント＃１（３）は、タスク１−２の処理を終了すると、引き続きタスク３のプログラムを読み出しながら、最後まで処理を進める。

このように、実施の形態２では、プロセスエレメントへのタスクの割り付けを行った後に、プロセスエレメントに空き時間が存在し、その時間に条件実行判定を行った後の処理を分割可能なタスクが存在する場合は、そのタスクの処理の部分を、空き時間を持つプロセスエレメントに対して割り付け、割り付けたプログラムの実行開始タイミングを通知する同期イベントの受け渡しの命令を追加すると共に、実行条件判定の結果を合わせて通知する機構を設けることによって、プログラム全体の処理時間を短縮することができる。

実施の形態３．
実施の形態３はタスクの先行制約において、後続のタスクを多数持つタスクを分割するようにしたものである。
実施の形態３におけるプログラム並列化装置および並列処理装置の図面上の構成は、実施の形態１と同様であるため、これらの図を援用して説明する。

実施の形態３のプログラム並列化装置２０において、タスク分割部２２は、解析部２１の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割すると共に、データ依存の関係において後続のタスクが所定の個数以上の対象タスクがあった場合は対象タスクを分割するよう構成されている。そしてスケジューリング部２３でスケジューリングを行った結果、処理時間が短縮される場合は、対象タスクの分割を行ってマシンコード３１を生成するよう構成されている。これ以外の構成は実施の形態１のプログラム並列化装置２０と同様である。また、並列処理装置の構成については実施の形態１と同様であるため、ここでの説明は省略する。

以下、実行条件とその条件下での処理内容を一まとまりとして一つのタスクとして扱った場合のタスク間の依存関係が図１１に示されるようなプログラムを例に実施の形態３によるプログラム並列化装置２０の処理の流れについて説明する。
図１１において、実施の形態１と同様に、各ノードがタスクを表し、円の中の数値はタスクの番号を表す。また、円の右側の数値はそのタスクの処理時間である。更に、ノード間の矢印は、タスク間の先行制約を表現している。この例では、処理時間が１８であるタスク１を実行した後、タスク３〜タスク６が実行可能になる。また、タスク２は常に実行可能である。

スケジューリング後に、実施の形態１、２に示すように、プログラム中のいずれかのタスクを分割しても、スケジューリング結果に改善が見られない状況であっても、プロセスエレメント上には、空き時間が存在する場合がある。同期によるオーバーヘッドのため、タスクを分割して同期命令を追加するより、そのまま空き時間とした方が、プログラム全体の処理時間が短いと判断される状況である。
しかし、このような細かな空き時間がスケジューリング結果の複数箇所に存在する場合、後続のタスクを多数持つタスクを分割することでスケジューリングの条件を改善し、プログラム全体の処理時間を短くできる可能性がある。

後続のタスクを多数持つタスクを分割し、処理の終了時間を早めると、タスクの先行制約により、先行タスクが完了するまでスケジューリングの対象にならなかったタスク群が、従来よりも早い時間にスケジューリング可能となることで、スケジュール対象のタスクの候補が多くなる。その結果、従来では、タスクの先行制約により、空き時間となっていた箇所が、新たにスケジュール可能となったタスクが割り当てられることで、空き時間が減少し、プログラム全体の処理時間を短くすることができる。

例えば、後続のタスクが四つ以上で、かつ、分割によって処理時間が短縮可能なタスクを検出し、それらのタスクについて、順にタスクの分割の前後で、プログラムの処理時間を比較し、効果があるタスクについてのみ、その分割を採用する方法がある。この場合、プログラムの先頭から順に、該当するタスクを検出し、プログラムの終端まで進んだ時点で処理を終了する。

図１１のようなタスク構成を持つプログラムを二つのプロセスエレメントに対して割り付けを行うと図１２のようになる。図１２のタスクを示す矢印の右側の数値は、そのタスクの処理時間を表す。このとき、タスク１の実行条件判定の時間を１とする。タスク１とタスク２の間の時間差は３であるため、同期処理のオーバーヘッドを考慮すると、タスク１を分割する効果はない。このためタスク１は分割しない。このときのプログラムの処理時間は、２６になる。

一方、実施の形態３では、後続のタスク数が多いタスクを強制的に分割する。この例では、タスク１に続くタスクが四つあるため、タスク１を二つに分割する。そして、タスク１の処理の後半の部分を起動するため、プレディケート付き同期イベントの送受信処理を追加する。
タスク１を分割した際のスケジューリング結果を図１３に示す。図１３のようなスケジューリングを行った際のプログラムの処理時間は２５になり、タスク１を一つのタスクとして扱う場合に比べ短縮できる。図１３のタスクを示す矢印の右側の数値は、そのタスクの処理時間を表す。

以上の処理の流れを図１４に示す。
先ず、タスク分割部２２は、全てのタスクのうち、後続のタスクが例えば三つ以上あるタスクについて、プログラム上の先頭のタスクから順にタスクを分割し（ステップＳＴ２１，ＳＴ２２）、スケジューリング部２３でスケジューリングを行う（ステップＳＴ２３）。その結果、ステップＳＴ２４において処理時間短縮の効果があれば、そのスケジューリング結果を採用し、そのタスクを分割する。一方、ステップＳＴ２４において、分割による効果がなければ、タスクを分割前に戻す（ステップＳＴ２５）。
次に、タスク分割部２２は、そのタスクがプログラムの最後のタスクかどうかを確認する（ステップＳＴ２６）。また、上記のステップＳＴ２１において、後続のタスクが三つ以上でなかった場合もステップＳＴ２６に移行する。ステップＳＴ２６において、そのタスクが最後のタスクであれば処理を終了する。一方、そのタスクが最後のタスクでない場合は、ステップＳＴ２１に戻って次のタスクに移る。このとき、後続のタスクが三つ以上あるタスクに移る。
尚、この例では、後続のタスクの数を３タスク以上としたが、このタスクの数は、３タスク以上に限定されるものではなく、２タスクや４タスク以上であってもよい。

尚、並列処理装置の動作については、実施の形態１，２と同様であるため、ここでの説明は省略する。
また、実施の形態１または２を実施した後、更に実施の形態３のタスク分割を適用することで、更なるプログラムの処理時間の短縮を行うことができる。

以上のように、実施の形態３のプログラム並列化装置によれば、プログラムを、実施の形態３の並列処理装置における複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、プログラムに含まれるデータの依存関係を解析する解析部と、解析部の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割すると共に、データ依存の関係において後続のタスクが所定の個数以上の対象タスクがあった場合は、所定の個数以上の後続タスクを持つある一つのタスクの処理内容を更に再分割して、実行条件と分割された処理内容を持つタスクと、分割された残りの一つ若しくは複数の処理内容へ分け、実行条件と分割された処理内容を持つタスクの実行条件が確定した後に、実行条件の値を受け渡すプレディケート付き同期イベントの送信処理を追加し、残りの分割された処理内容のそれぞれの先頭に、プレディケート付き同期イベントの受信処理を追加して、並列に実行可能な分割された処理内容を持つタスクと分割された一つ若しくは複数の処理内容へ分割するタスク分割部と、タスク分割部で分割したタスクを、複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、スケジューリング部でスケジューリングを行った結果、スケジューリング部が処理時間の短縮が可能と判断した場合は、タスク分割部が対象タスクの分割を行うようにしたので、データの先行制約が原因で空き時間となっている時間に対して、その時刻で割当可能となるタスクの数が増加することにより、その空き時間に割当可能なタスクが現れた場合、プログラム全体の処理時間を短縮できる。

実施の形態４．
実施の形態４は、タスクの実行条件の判定処理を複数のプロセスエレメントに対応して分割するようにしたものである。
プログラム並列化装置の図面上の構成は図２と同様であるため、図２を用いて説明する。
実施の形態４のプログラム並列化装置２０におけるタスク分割部２２は、解析部２１の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割すると共に、スケジューリング部２３でスケジューリングを行った結果、いずれかのプロセスエレメントで、タスク実行の空き時間が存在した場合は、タスクの実行条件の判定処理を複数のプロセスエレメントに対応して分割するよう構成されている。また、コード生成部２４は、タスク分割部２２で、タスクの実行条件の判定処理を分割した場合に、分割したタスクの実行条件の判定処理を同期させるための同期命令を付加するよう構成されている。それ以外の構成は実施の形態１と同様である。

図１５は、実施の形態４の並列処理装置におけるプロセスエレメントの構成図である。
実施の形態４のプロセッサはＮ（Ｎは任意の整数）個のプロセスエレメント（ＰＥ）を備えており、図１５はＮ番目（＃Ｎ）のプロセスエレメント５０を示している。
図示のプロセスエレメント５０は、プレディケートレジスタ５１、Ｎ−１個のプレディケート受信レジスタ５２、命令実行部５３、同期機構５４を備えている。プレディケートレジスタ５１は、そのプロセスエレメントで処理するプログラム用のプレディケート値を保持する（自プロセスエレメントの処理結果の真偽値を格納する）ためのレジスタであり、Ｎ−１個のプレディケート受信レジスタ５２は、それぞれ、他のプロセスエレメントからプレディケート付き同期イベントによって受信した、接続先のプレディケート値を格納するためのレジスタである。また、命令実行部５３は、プレディケートレジスタ５１の値とプレディケート受信レジスタ５２の値とに基づいて、タスクの実行を行うものである。更に、同期機構５４は、実施の形態１における同期機構１０，１４と同様に、他のプロセスエレメントとの同期を行うためのものである。

実施の形態４では、分割可能なタスクの実行条件の判定処理を空き時間を持つＰＥの数で分割する。そして、並列に演算する実行条件判定の結果を一つにまとめるために、複数のプロセスエレメント間でプレディケート付き同期イベントを受け渡す。
以下、実行条件とその条件下での処理内容の一まとまりを一つのタスクとして扱った場合のタスク間の依存関係が図１６に示されるようなプログラムを例に実施の形態４によるプログラム並列化装置２０の処理の流れと並列処理装置の動作について説明する。

図１６において、実施の形態１と同様に、各ノードがタスクを表し、円の中の数値はタスクの番号を表す。また、円の右側の数値はそのタスクの処理時間である。更にノード間の矢印は、タスク間の先行制約を表現している。この例では、処理時間が４０であるタスク１を実行した後、タスク２とタスク３が実行可能になる。

図１６で示されるタスク構成を持つプログラムをプログラム並列化装置２０に入力すると、プログラムを解析し中間コードを生成した後、図１６に示すタスクの単位に分割し、スケジューリングを終了した時点で、図１７のようなスケジューリング結果が得られる。図１７のタスクの動作を示す矢印の右側の数値は、そのタスクの処理時間を表す。プロセスエレメント＃０（２）上ではタスク１とタスク２を、プロセスエレメント＃１（３）上ではタスク３を実行する。このとき、プログラム全体の処理時間は、プロセスエレメント＃０（２）での処理時間となり、タスク１の処理時間とタスク２の処理時間を合わせた６１となる。

スケジューリングを終えると、スケジューリング部２３は、いずれかのプロセスエレメント上にプロセスエレメント間の通信のオーバーヘッドを越える空き時間が存在するかを確認する。この例では、プロセスエレメント＃０（２）においてタスク１を実行している間、プロセスエレメント＃１（３）に空き時間が生じている。このため、プログラム並列化装置２０は、タスクの再分割の処理に入る。

図１８は、タスクの再分割の処理を示すフローチャートである。
タスクの再分割では、空き時間の時刻とその時刻に空き時間を持つＰＥの数を求める（ステップＳＴ３１）。その後、同時刻において処理を分割可能なタスクが存在するかを確認する（ステップＳＴ３２）。ここで、タスク１は処理時間が４０のタスクであるが、その処理時間４０のうち実行条件判定の処理に３０の時間を要するタスクであるとする。
この例では、プロセスエレメント＃０（２）で処理時間が４０のタスク１の実行を行っている間、プロセスエレメント＃１（３）には処理が割り当てられておらず、空き時間がある。このため、３０の時間を要するタスク１の実行条件判定を分割することができる。また、分割したタスク１の割当可能なプロセスエレメントは、プロセスエレメント＃０（２）とプロセスエレメント＃１（３）の二つである。そこで、プロセスエレメント＃０（２）上で実行するタスク１の実行条件判定の処理を二つに分割し、それぞれをプロセスエレメント＃０（２）とプロセスエレメント＃１（３）の二つに割り付ける（ステップＳＴ３３）。

実行条件判定の処理は、値の比較、論理演算、実行条件を求めるための処理をまとめた関数や、様々な実行条件の論理和や論理積の組み合わせによって構成される。実行条件判定の処理に長い時間を要する場合、個々の実行条件の演算を行った後、これらの実行条件について論理積や論理和を求めている場合がある。このような場合、個々の実行条件を求める処理を複数のプロセスエレメントに割り当てることで並列に処理を行えば、処理時間を短縮できる。
そして、各プロセスエレメントで求めた実行条件の演算結果を、プレディケート値として同期イベントと共に、プレディケート付き同期命令を用いて、他のプロセスエレメントに対して送信する。他のプロセスエレメントからプレディケート付き同期イベントを受信するプロセスエレメントには、プレディケート付き同期イベントの受信命令を追加する。そして、元のプログラムでの論理演算をプレディケートレジスタ間の演算命令に置き換える。

即ち、タスク分割部２２は、起動元タスクの同期イベント発行位置にプレディケート付き同期命令を追加し（ステップＳＴ３４）、起動先の同期イベント待機位置に同期待ち命令を追加する（ステップＳＴ３５）。そして、同期イベント待ち後に受信したプレディケート値とプレディケートレジスタの値を用いた論理計算命令を追加する（ステップＳＴ３６）。このようにタスクを再分割したスケジューリング結果を図１９に示す。

プレディケートレジスタ間の演算命令とは、そのプロセスエレメントで処理するプログラム用のプレディケート値を保持するプレディケートレジスタと、他のプロセスエレメントからプレディケート付き同期イベントによって受信した、接続先のプレディケート値を格納するプレディケートレジスタ間で論理演算する命令である。この演算結果は、自プロセスエレメントのプレディケート値を格納するプレディケートレジスタに入れる。

以上の構成により、条件実行判定の処理を複数のプロセスエレメントに分割して割り付けて並列実行すると共に、割り当てた実行条件判定の演算結果をプレディケート付き同期命令によって集約し、プレディケートレジスタ間で論理演算を行うことで、実行条件判定処理での実行条件を求めるまでの処理時間を短縮することができる。

次に、実施の形態４の並列処理装置の動作を、図１９に示すスケジューリング結果のプログラムを例として説明する。
並列処理装置のプロセスエレメント＃０（２）は、分割されたタスク１−１を実行する。ここで、タスク１−１は、タスク１の実行条件判定処理の中の前半の処理である。また、プロセスエレメント＃１（３）は、分割されたタスク１−２を実行する。タスク１−２は、タスク１の実行条件判定処理の中の後半の処理である。タスク１−１のプログラムの最後の部分には、プレディケート付きイベントの受信命令と、通知されるプレディケート値と自プロセスエレメントのプレディケート値との間で論理演算を行う命令が追加されている。また、タスク１−２のプログラムの最後の部分には、プレディケート付き同期イベントの送信命令が追加されている。

プロセスエレメント＃０（２）上のタスク１−１が、プロセスエレメント＃１（３）上のタスク１−２より先に終了すると、タスク１−２からのプレディケート付き同期イベントの待機状態となる。即ち、プロセスエレメント＃０（２）の同期機構５４に待機命令を格納する。そして、プロセスエレメント＃１（３）上のタスク１−２の処理を終了した時点で、命令実行部５３は、プレディケート付き同期イベントをプロセスエレメント＃０（２）の同期機構５４に対して送信する。このタスク１−２からのプレディケート付き同期イベントを受信することで、プロセスエレメント＃０（２）の命令実行部５３は、プレディケート間の演算を行う。

一方、プロセスエレメント＃１（３）のタスク１−２が、プロセスエレメント＃０（２）のタスク１−１より先に終了した場合は、終了時点でのプロセスエレメント＃１（３）のプレディケート値を、プロセスエレメント＃０（２）のプレディケート受信レジスタ５２に対して、プレディケート付き同期イベントによって通知する。そして、プロセスエレメント＃１（３）の命令実行部５３は、タスク３のプログラムを読み出し、実行を開始する。ここで、タスク３の先頭には、プロセスエレメント＃０（２）からの同期イベントの受信命令であるため、プロセスエレメント＃０（２）からの同期イベントを待機する。

プロセスエレメント＃０（２）では、タスク１−１の処理の最後で、プレディケート付き同期イベントの受信命令を実行する。このとき、対象となる同期イベントは既にプロセスエレメント＃１（３）から受信している。そのため、プロセスエレメント＃０（２）の命令実行部５３では、自プロセスエレメント＃０（２）のプレディケートレジスタ５１と、同期イベントと共に受信しプレディケート受信レジスタ５２に格納されているプロセスエレメント＃１（３）のプレディケート値を用いて、タスク１の実行条件判定の全体のプレディケート値を演算によって求める。

プロセスエレメント＃０（２）の命令実行部５３では、複数のプロセスエレメント上で並列に演算した実行条件判定の結果を、プレディケート付き同期命令によって集約し、プレディケート受信レジスタ５２とプレディケートレジスタ５１間で演算を行い、実行条件判定部分のプレディケート値を求める。このプレディケートレジスタの真偽値に基づいて、タスク１−３の処理を行う。
プロセスエレメント＃０（２）の命令実行部５３は、タスク１−３の実行を終えると、プロセスエレメント＃１（３）上のタスク３に対して同期イベントを発行する。また、タスク２の処理を開始する。このとき、同期イベントを受信したプロセスエレメント＃１（３）では、タスク３の処理を開始し、タスク２とタスク３の処理を並行して行う。

以上の流れを図２０〜図２２を用いて説明する。
図２０は、実施の形態４におけるタスク１の分割前のプログラムの概要を示す説明図である。この図２０の処理Ｅの実行条件の判定処理において、論理和の部分で分割したものが、図２１と図２２である。この例では、図２１の処理をプロセスエレメント＃０（２）に、図２２の処理をプロセスエレメント＃１（３）に割り付けた例を示している。
図２１に示すプログラムは、条件Ａと条件Ｂの論理積をプレディケートレジスタ５１に格納し、プロセスエレメント＃１（３）からのプレディケート値の受信を待機することを示している。プロセスエレメント＃０（２）は、プレディケート付き同期イベントを受信すると、そのプレディケート受信レジスタ５２に格納された値と、自身のプレディケートレジスタ５１の論理和を取ってプレディケートレジスタ５１に格納する。そして、処理Ｅは、そのプレディケートレジスタ５１の真偽値に基づいて、処理を実行する。その後、図１６に示したタスクの先行関係に基づいて、タスク３を起動するために同期イベントをプロセスエレメント＃１（３）に対して送信する。その後、タスク２の処理に進む。

一方、図２２に示すプログラムは、条件Ｃと条件Ｄの論理積をプレディケートレジスタ５１に格納し、そのプレディケート値を同期イベントと共にプロセスエレメント＃０（２）に送信することを示している。その後、プロセスエレメント＃１（３）に割り当てられたタスク３の実行を開始するための同期イベントを待機する。
このような処理を行うことにより、タスク１の分割前の図１７に示すスケジューリングでは６１の時間がかかっていたプログラムの処理時間は、実行条件判定の処理の並列化によって、図１９に示すように４８に短縮される。

以上のように、実施の形態４のプログラム並列化装置によれば、プログラムを、実施の形態４の並列処理装置における複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、プログラムに含まれるデータの依存関係を解析する解析部と、解析部の解析結果に基づいて、プログラムを複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、分割したタスクを、複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、スケジューリング部でスケジューリングを行った結果、スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、タスク分割部がタスクの実行条件の判定処理を複数のプロセスエレメントに対応して複数のタスクへ再分割すると共に、コード生成部が、分割したタスクの実行条件の判定処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するようにしたので、並列処理装置におけるプログラムの実行効率を改善し、最大実行時間を短縮することができる。

この発明の実施の形態１による並列処理装置を示す構成図である。 この発明の実施の形態１によるプログラム並列化装置を示す構成図である。 この発明の実施の形態１におけるタスクの先行関係を示す説明図である。 この発明の実施の形態１によるプログラム並列化装置の動作を示すフローチャートである。 この発明の実施の形態１におけるタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態１によるプログラム並列化装置のタスクの再分割処理を示すフローチャートである。 この発明の実施の形態１におけるタスク再分割後のタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態２におけるタスクの先行関係を示す説明図である。 この発明の実施の形態２におけるタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態２におけるタスク再分割後のタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態３におけるタスクの先行関係を示す説明図である。 この発明の実施の形態３におけるタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態３におけるタスク再分割後のタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態３によるプログラム並列化装置のタスクの分割処理を示すフローチャートである。 この発明の実施の形態４による並列処理装置のプロセスエレメントを示す構成図である。 この発明の実施の形態４におけるタスクの先行関係を示す説明図である。 この発明の実施の形態４におけるタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態４によるプログラム並列化装置のタスクの再分割処理を示すフローチャートである。 この発明の実施の形態４におけるタスク再分割後のタスク構成をプロセスエレメントに割り付けた状態を示す説明図である。 この発明の実施の形態４における分割前のプログラムを示す説明図である。 この発明の実施の形態４における分割後のプログラムを一方のプロセスエレメントに割り付けた場合のプログラムを示す説明図である。 この発明の実施の形態４における分割後のプログラムを他方のプロセスエレメントに割り付けた場合のプログラムを示す説明図である。

符号の説明

１ プロセッサ、２，３，５０ プロセスエレメント、４ 内蔵メモリ、５ 外部メモリ、６ バス、７，１２，５１ プレディケートレジスタ、８，１１，５２ プレディケート受信レジスタ、９，１３，５３ 命令実行部、１０，１４，５４ 同期機構、２０ プログラム並列化装置、２１ 解析部、２２ タスク分割部、２３ スケジューリング部、２４ コード生成部、３０ プログラム、３１ マシンコード。

Claims (3)

1. 複数のプロセスエレメントを備え、これら複数のプロセスエレメントで、実行条件と当該実行条件下での処理内容の対で構成されるタスクの並列処理を行う並列処理装置において、
   前記各プロセスエレメントは、
   次の命令を実行するか否かを決定するための真偽値を格納するプレディケートレジスタと、
   他のプロセスエレメントから受信した次の命令を実行するか否かを決定するための真偽値が付いたプレディケート付き同期イベントを格納するプレディケート受信レジスタと、
   タスクの実行条件判定結果を他のプロセスエレメントで実行されるタスクに対して通知するタスクを実行する場合は、前記プレディケートレジスタの真偽値が付いたプレディケート付き同期イベントを前記他のプロセスエレメントに通知し、他のプロセスエレメントで実行されるタスクの実行条件判定結果に基づいて実行されるタスクを実行する場合は、前記プレディケート付き同期イベントの受信レジスタの真偽値に基づいて当該自身のタスクを実行する命令実行部とを備えた並列処理装置に対して、プログラムを前記複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、
   プログラムに含まれるデータの依存関係を解析する解析部と、
   前記解析部の解析結果に基づいて、前記プログラムを前記複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、
   前記分割したタスクを、前記複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、
   スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して前記各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、
   前記スケジューリング部でスケジューリングを行った結果、前記スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、前記タスク分割部がタスクの処理を前記複数のプロセスエレメントに対応して一つのタスクを複数のタスクへ再分割すると共に、前記コード生成部が、当該分割したタスクの処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するプログラム並列化装置。
2. 複数のプロセスエレメントを備え、これら複数のプロセスエレメントで、実行条件と当該実行条件下での処理内容の対で構成されるタスクの並列処理を行う並列処理装置において、
   前記各プロセスエレメントは、
   次の命令を実行するか否かを決定するための真偽値を格納するプレディケートレジスタと、
   他のプロセスエレメントから受信した次の命令を実行するか否かを決定するための真偽値が付いたプレディケート付き同期イベントを格納するプレディケート受信レジスタと、
   タスクの実行条件判定結果を他のプロセスエレメントで実行されるタスクに対して通知するタスクを実行する場合は、前記プレディケートレジスタの真偽値が付いたプレディケート付き同期イベントを前記他のプロセスエレメントに通知し、他のプロセスエレメントで実行されるタスクの実行条件判定結果に基づいて実行されるタスクを実行する場合は、前記プレディケート付き同期イベントの受信レジスタの真偽値に基づいて当該自身のタスクを実行する命令実行部とを備えた並列処理装置に対して、プログラムを前記複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、
   プログラムに含まれるデータの依存関係を解析する解析部と、
   前記解析部の解析結果に基づいて、前記プログラムを前記複数のプロセスエレメントに対応したタスクに分割すると共に、データ依存の関係において後続のタスクが所定の個数以上の対象タスクがあった場合は、前記所定の個数以上の後続タスクを持つある一つのタスクの処理内容を更に再分割して、実行条件と分割された処理内容を持つタスクと、分割された残りの一つ若しくは複数の処理内容へ分け、前記実行条件と分割された処理内容を持つタスクの実行条件が確定した後に、前記実行条件の値を受け渡すプレディケート付き同期イベントの送信処理を追加し、残りの前記分割された処理内容のそれぞれの先頭に、プレディケート付き同期イベントの受信処理を追加して、並列に実行可能な前記分割された処理内容を持つタスクと前記分割された一つ若しくは複数の処理内容へ分割するタスク分割部と、
   前記タスク分割部で分割したタスクを、前記複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、
   スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して前記各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、
   前記スケジューリング部でスケジューリングを行った結果、前記スケジューリング部が処理時間の短縮が可能と判断した場合は、前記タスク分割部が前記対象タスクの分割を行うプログラム並列化装置。
3. 複数のプロセスエレメントを備え、これら複数のプロセスエレメントで、実行条件と当該実行条件下での処理内容の対で構成されるタスクの並列処理を行う並列処理装置において、
   前記各プロセスエレメントは、
   次の命令を実行するか否かを決定するための真偽値を格納するプレディケートレジスタと、
   他のプロセスエレメントから受信した次の命令を実行するか否かを決定するための真偽値が付いたプレディケート付き同期イベントを格納するプレディケート受信レジスタと、
   タスクの実行条件判定結果を他のプロセスエレメントで実行されるタスクに対して通知するタスクを実行する場合は、前記プレディケートレジスタの真偽値が付いたプレディケート付き同期イベントを前記他のプロセスエレメントに通知し、他のプロセスエレメントで実行されるタスクの実行条件判定結果に基づいて実行されるタスクを実行する場合は、前記プレディケート付き同期イベントの受信レジスタの真偽値に基づいて当該自身のタスクを実行する命令実行部とを備えた並列処理装置に対して、プログラムを前記複数のプロセスエレメント上で並列に実行するタスクに分割するプログラム並列化装置であって、
   プログラムに含まれるデータの依存関係を解析する解析部と、
   前記解析部の解析結果に基づいて、前記プログラムを前記複数のプロセスエレメントに対応したタスクに分割するタスク分割部と、
   前記分割したタスクを、前記複数のプロセスエレメントで実行するためのスケジューリングを行うスケジューリング部と、
   スケジューリングされた各プロセスエレメント毎のタスクを、データの依存関係に応じた同期命令を付加して前記各プロセスエレメントの実行形式のコードとして生成するコード生成部とを備え、
   前記スケジューリング部でスケジューリングを行った結果、前記スケジューリング部がいずれかのプロセスエレメントで、タスク実行の空き時間が存在すると判断した場合は、前記タスク分割部がタスクの実行条件の判定処理を前記複数のプロセスエレメントに対応して複数のタスクへ再分割すると共に、前記コード生成部が、当該分割したタスクの実行条件の判定処理を同期させるためのプレディケート付き同期イベントの受け渡しを行う命令を付加するプログラム並列化装置。

Images