(57)【要約】【課題】高速に実行することのできる並列処理装置を得る。【解決手段】並列化プログラム生成装置４は、単一の入力プログラム５を複数のプロセスエレメント１０−１，１０−２で実行するプログラムに分割する。プロセスエレメント１０−１，１０−２では、正の依存関係にあるデータについて投機的実行を行った場合、投機的実行結果判定手段１３０は、その投機的実行における読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定する。【選択図】図１
2009048269.tif 000002
【特許請求の範囲】
【請求項１】
単一のプログラムを複数のプロセスエレメントで実行するプログラムに分割して、これら分割したプログラムをそれぞれ前記複数のプロセスエレメントで並列に処理する並列処理装置において、
前記複数のプロセスエレメントで、正の依存関係にあるデータについて投機的実行を行った場合、当該投機的実行における読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定する投機的実行結果判定手段とを備えた並列処理装置。
【請求項２】
投機的実行結果判定手段は、並列して複数の投機的実行が行われる場合、それぞれの投機的実行を行うプロセスエレメントを識別し、各プロセスエレメントの投機的実行毎に、読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定することを特徴とする請求項１記載の並列処理装置。
【請求項３】
投機的実行の成否の履歴を格納する成否履歴テーブルと、
前記成否履歴テーブルにおける成否履歴のパターンに基づいて、同じ成否結果になる投機的実行箇所を検出し、失敗が予想される箇所については、投機的実行の不実施と判定する投機的実行可否判定手段とを備えた請求項１または請求項２記載の並列処理装置。
【請求項４】
投機的実行の成否の履歴を格納する成否履歴テーブルと、
現在実行中のプログラムについて、前記成否履歴テーブルにおける成否履歴に基づき、投機的実行の失敗回数が規定値を超えるか、または、予め定めたプログラムの最悪処理時間を超えてしまうと判断される場合に以降の投機的実行を不実施と判定する投機的実行可否判定手段とを備えたこと特徴とする請求項１または請求項２記載の並列処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プログラムの自動並列化によって実行性能を向上させる並列処理装置に関するものである。
【背景技術】
【０００２】
従来の並列処理装置では、親スレッドが子スレッドをフォーク後、親の汎用レジスタ書込み毎に更新後のレジスタ値を親から子のプロセッサへ送信する。子スレッドは投機的に実行し正依存違反検出時に再実行する。正依存の違反は、各プロセッサの汎用レジスタに１対1に対応し、最初のアクセスがリードかライトかを保持する状態レジスタを設け、親から値が送信されたレジスタの状態がリードの場合に検出するよう構成されていた（例えば、特許文献１参照）。
【０００３】
また、データ依存投機的実行時では、失敗時の回復処理の際に、プログラム順序で実行するより性能が低下するため、従来の並列処理装置では、過去の投機的実行の成否の履歴を参照し、成功予測時は非プログラム順序で投機的に実行、失敗予測時はプログラム順序で確定的に実行するようにしたものがあった（例えば、特許文献２参照）。このような並列処理装置では、ロード命令の対象アドレスをハッシュ関数回路で投機的実行成否履歴テーブルのエントリに重複して割り当るため、少ないハードウェア量でデータ依存投機的実行の性能を向上させることができる。
【０００４】
【特許文献１】特許第３７０２８１５号公報
【特許文献２】特許第３７２９０８７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記特許文献１に記載されているような従来の並列処理装置では、子スレッドの汎用プロセッサ毎に、フォークされてからの最初のアクセスがリードかライトかを保持する状態レジスタを設け、最初のアクセスがリードであった場合、正依存違反があったとして、子スレッドを再実行する。しかしながら、再実行が必要となるのは、子スレッドが投機的に読み出した値と、親スレッドが後から書き込んだ値が異なる場合であって、同じ値の場合は、アクセスの順序に正依存違反があったとしても、プログラムの実行結果に問題があるわけではない。従来では、このような場合でも無条件で再実行を行うために、性能向上の妨げとなっていた。
【０００６】
また、特許文献２に示されるような並列処理装置では、ロード命令の対象アドレスを投機的実行成否履歴テーブルのエントリに重複して割り当てるため、ロード命令の対象アドレスのエイリアスが発生し、エントリの数により予測の精度向上には限度があった。更に、特許文献２に示されるような並列処理装置では、投機的実行成否履歴に基づいて、投機的実行の実行／非実行を判断しているが、実行の判断の対象は個々の投機的実行部分に閉じており、他の投機的実行部分に対しては関連を持たない。このため、投機的実行部分間に関連があり、前方の投機的実行部分で投機的実行に失敗すると、後方の投機的実行でも必ず失敗するような状況であっても、個々の部分についての投機的実行成否履歴に依存するため、履歴に基づいて成功すると判断する。しかし結果的には投機的実行に失敗するため、プログラム順序で実行するよりかえって性能が低下するといった問題があった。
【０００７】
この発明は上記のような課題を解決するためになされたもので、与えられた入力プログラムを並列化し、高速に実行する並列処理装置を得ることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る並列処理装置は、単一のプログラムを複数のプロセスエレメントで実行するプログラムに分割して、これら分割したプログラムをそれぞれ複数のプロセスエレメントで並列に処理する並列処理装置において、複数のプロセスエレメントで、正の依存関係にあるデータについて投機的実行を行った場合、その投機的実行における読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定する投機的実行結果判定手段とを備えたものである。
【発明の効果】
【０００９】
この発明の並列処理装置は、正の依存関係にあるデータについて投機的実行を行った場合に読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定するようにしたので、高速に実行する並列処理装置を得ることができる。
【発明を実施するための最良の形態】
【００１０】
実施の形態１．
図１は、この発明の実施の形態１による並列処理装置を示す構成図である。
図において、並列処理装置は、プロセッサ１、バス２、メモリ３、並列化プログラム生成装置４からなる。プロセッサ１は、プロセスエレメント（ＰＥ０）１０−１、プロセスエレメント（ＰＥ１）１０−２、プロセッサ内部バス１１、共有メモリ部１２を備えている。
【００１１】
プロセスエレメント１０−１、プロセスエレメント１０−２は共通の構成であり、命令実行部１０１と実行制御部１０２を備えている。
図２は、プロセスエレメント１０−１（１０−２）を示すブロック図である。
命令実行部１０１は、与えられた命令を実行する機能部である。実行制御部１０２は、命令実行部１０１が実行時に参照するプログラムカウンタ（ＰＣ）１０３と、プログラムカウンタ１０３の値を一時的に保持するシャドウプログラムカウンタ（シャドウＰＣ）１０４と、プロセスエレメントの状態を表すステータスレジスタ１０５とを備え、プログラムカウンタ１０３やシャドウプログラムカウンタ１０４の値を管理すると共に、命令実行部１０１の実行を管理するよう構成されている。
【００１２】
次に、共有メモリ部１２について説明する。
共有メモリ部１２は、図１に示すように、共有変数の値を保持する共有変数領域１３と、共有変数への書き込みデータを一時的に格納するテンポラリ領域１４から構成される。共有変数領域１３には、複数のプロセスエレメント１０−１，１０−２で、正の依存関係にあるデータについて投機的実行を行った場合、投機的実行における読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定する投機的実行結果判定手段１３０を備えている。
【００１３】
図３に示すように、共有メモリ部１２の共有変数領域１３は、メモリ上の各要素のデータ１３１に対して、１ビットの投機フラグ１３２を持つ。ここで、各要素のサイズとしては、１６ビット、３２ビット、６４ビットが挙げられるが、制御システムを構成する並列処理装置の場合、１ビットの要素も含めることができる。また、一般的には、先に挙げたサイズが用いられることが多いが、用途に特化したシステムにおいては、上記サイズに限定されるものではない。
【００１４】
図４は、共有変数領域１３の投機的実行結果判定手段１３０の構成を示す説明図である。
図示のように、投機的実行結果判定手段１３０では、各要素に対する投機フラグ１３２の他に、各要素に既に格納されているメモリ上のデータ１３１と、その要素に対して書き込もうとする書込データ１３３についての比較器１３４を持つ。この比較器１３４は、共有メモリ部１２へ値を格納する際に働き、共有メモリ部１２上のある要素に対して、その要素に格納されている値と異なる値を書き込んだ場合に、論理積回路１３５によって、投機フラグ１３２との論理積をとった結果の信号を出力する。即ち、投機的実行が失敗したことを示す信号を出力する。一方、共有メモリ部１２上のある要素に対して、その要素に格納されている値と同じ値を書き込んだ場合には信号を出力しない。
【００１５】
図１に示す共有メモリ部１２のテンポラリ領域１４は、共有メモリ部１２の共有変数領域１３へ書き込むデータを一時的に保持する領域である。プロセスエレメント１０−１（１０−２）から共有変数に対して書き込みが発生する場合に、図５に示す構造によって書き込みアドレスとその値を一時的に保持する。プロセスエレメントで実行する命令が、このテンポラリ領域１４から共有変数領域１３へ書き込む命令の場合に、テンポラリ領域１４に格納されているアドレスとそのアドレスへ書き込む値を基に、共有変数領域１３に対して値を書き込む。
【００１６】
元のプログラムを並列化し、プログラム実行時の処理の並列度の向上によって、処理時間を短縮する並列処理装置において、処理の役割によって、親スレッドと子スレッドの２種類のスレッドによって処理を実行する。
ここで親スレッドとは、処理全体の流れを司り、子スレッドに対して割り当てた処理の実行タイミングを通知して起動し、かつ自身も処理を行うスレッドである。また、子スレッドとは、親スレッドから実行開始の指示を受けて親スレッドと並行して処理を行い、一連の処理を終えると再び親スレッドからの実行開始指示待ちに入るスレッドである。
親スレッドは、常に一つのみ存在するが、子スレッドは複数存在することができる。ま親スレッドは複数の子スレッド起動することもできるし、親スレッドに起動された子スレッド自身が親スレッドとしてさらに子スレッドを起動することもできる。
これらのスレッドについて、例えば親スレッドを図１で示すプロセスエレメント１０−１で、子スレッドをプロセスエレメント１０−２で実行することで、並列処理を行うことができる。
【００１７】
図１における並列化プログラム生成装置４は、入力プログラム５に対して、コントロールフロー及びデータの依存関係について解析を行い、入力プログラム５の中で、並列化が可能と判断された部分について、上記のような複数のスレッドで並列処理を行う実行コード５１，５２を生成する装置である。特に、本発明の並列化プログラム生成装置４では、並列度を更に向上してプログラム実行時の性能改善を図るため、データ依存関係について、投機的に実行する実行コードを生成するよう構成されている。
【００１８】
図６は、並列化プログラム生成装置４の構成図である。
図示のように、並列化プログラム生成装置４は、解釈部４１、依存性解析部４２、並列化部４３、コード生成部４４を備えている。解釈部４１は入力プログラム５を解釈する機能部で、依存性解析部４２は、解釈部４１で解釈された入力プログラム５に対してコントロールフローおよびデータ依存関係を解析する機能部である。並列化部４３は、依存性解析部４２の解析結果に基づいて複数のプロセスエレメント１０−１，１０−２に対してプログラムを分割して割り当て、かつ、投機的実行処理を組み込む機能部である。コード生成部４４は、並列化部４３で生成されたプログラムの実行コードを生成し、実行コード５１，５２として出力する機能部である。尚、ここでは、二つのプロセスエレメント１０−１，１０−２に対応して二つの実行コード５１，５２を生成しているが、プロセスエレメントの数に応じて三つ以上の分割も可能である。
【００１９】
並列化プログラム生成装置４で生成された実行コード５１，５２は、メモリ３にロードされた後、プログラムで扱う変数のうち、データ依存についての投機的実行の対象となる変数が、投機フラグ１３２を持つ共有メモリ部１２上に配置される。それ以外の変数についても共有メモリ部１２上に配置するが、使用する変数の数に対して、共有メモリ部１２の領域が少ない場合は、外部のメモリ３上にも配置される。
一般に、プロセッサ１外部のメモリ３より、プロセッサ１内部のメモリを利用した方が、高速なデータ転送が行えるため、共有メモリ部１２のサイズが足りない場合は、まずデータ依存の投機的項対象の変数を配置し、次にアクセス頻度の高い変数を優先的に配置する。
【００２０】
データ依存について投機的に実行するコードとは、次のようなコードである。一般に、並列化ではデータの依存関係が重要で、ある変数に対して値を書き込んだ後に、同じ変数から値を読み出す処理が存在する場合、これらの処理を同時に実行することはできない。また、先に値を読み出し、後から値を書き込むような順序に並列化することもできない。書き込みによって、その変数の値が確定するまでは、その変数の値を読み出しても、正しい値とは言えず、その後の演算の結果が正しい結果となる保証がないためである。
一方、データ依存についての投機実行では、ある変数に対する書き込み処理に対して、読み出し処理を先に投機的に実行する。そして、その変数へ値を書き込む際に、その値が読み出した値と異なっていれば、投機的な実行に失敗したとして、新たな変数の値を用いて改めて読み出し処理から再実行する。その値が読み出した値と一致していれば、投機的な実行に成功したとして、そのまま処理を継続できる。
投機的実行では、データ依存による並列度の限界を超えた並列化が可能になるため、並列処理の高速化において、有効な手段である。
【００２１】
データ依存の投機的実行の様子を図７に示す。図中、丸囲い数字が実行順序を示している。
図７（ａ）は、並列化前の元のプログラムをスレッド０によって実行する様子である。ある変数について書き込みと読み出しが行われており、この間に正依存が存在している。
次に、並列化したプログラムをスレッド０とスレッド１の二つのスレッドで実行する様子を図７（ｂ）に示す。ある変数についての正依存を守る範囲でプログラムを二つに分割し、並列化することで処理時間を短縮している。
次に、スレッド１で投機的実行を行う場合の様子を図７（ｃ）に示す。ある変数の値について投機的実行をすることにより、図７（ｂ）の場合に比べ、更に処理時間を短縮している。
次に、スレッド１で投機的実行をしたが、失敗した場合の様子を図７（ｄ）に示す。投機的実行の対象となる変数の値が、スレッド０によって途中で更新された場合、その投機的実行は失敗となり、改めて再実行することになる。このとき、再実行に向けた復帰処理が入るため、その分だけ投機的実行を行わない図７（ｂ）の場合に比べて、処理時間は長くなる。
【００２２】
このようなデータ依存の投機的実行を実現するため、この並列処理装置で実行する命令には、一般的なシングルプロセッサが持つ命令体系に対して、次のような拡張を行う。
親スレッドが子スレッドを起動するフォーク命令、子スレッドの処理の終了を示すターム命令、親スレッドが子スレッドの終了を待機するウエイト命令、子スレッドが投機的実行する際にデータをロードする投機ロード命令、及び、データをストアする投機ストア命令である。
【００２３】
次に、個々の命令について、フローチャートを用いて、ハードウェア上での動作を示しながら説明する。
ここで、プロセスエレメント１０−１が親スレッド、プロセスエレメント１０−２が子スレッドに割り当てられているとする。並列化プログラム生成装置４は、データ依存箇所を投機的に実行するように、親スレッド用の実行コード５１と、子スレッド用の実行コード５２を生成する。
この並列処理装置は、実行を開始すると、親スレッド用の実行コード５１を実行するプロセスエレメント１０−１が、実行コード５１を先頭から順に処理する。この間、子スレッドを実行するプロセスエレメント１０−２は、親スレッドからの起動待ちの状態にあり、処理を停止している。より具体的には、プロセスエレメント１０−２のプログラムカウンタ１０３の値を、親スレッドからの実行開始信号が届き次第開始する命令のアドレスにセットして、親スレッドからの起動待ちの状態に入る。
【００２４】
図８は、親スレッドを実行するプロセスエレメント１０−１が行う処理のフローチャートである。
親スレッドを実行するプロセスエレメント１０−１は、実行する命令が子スレッドのフォーク命令かを判断し（ステップＳＴ１００）、フォーク命令の場合、実行制御部１０２は、子スレッドを実行するプロセスエレメント１０−２の実行制御部１０２に対して、実行開始信号を通知する（ステップＳＴ１０１）。フォーク命令に関して、親スレッドが実行する処理は以上である。
一方、親スレッドを実行するプロセスエレメント１０−１から実行開始信号を受けたプロセスエレメント１０−２の実行制御部１０２は、プログラムカウンタ１０３の値をシャドウプログラムカウンタ１０４にコピーし、更に、プロセスエレメント１０−２の命令実行部１０１に対して、実行を指示する。この指示を受けて、プロセスエレメント１０−２の命令実行部１０１は、プログラムカウンタ１０３が示すアドレスから命令コードを読み出し、その命令コードを実行する。また、プロセスエレメント１０−２の実行制御部１０２は、ステータスレジスタ１０５の値を実行中を示す値に切り換える。プロセスエレメント１０−２の命令実行部１０１は、プロセスエレメント１０−２用の命令コードの中にターム命令が現れるまで、連続して処理を行う。この間、親スレッドも並行して処理を行っている。以上が、フォーク命令の動作である。
【００２５】
次に、ウエイト命令について説明する。ウエイト命令は、親スレッドが実行する命令であり、子スレッドと同期をとるための命令である。
プロセスエレメント１０−１は、親スレッドで実行する命令がウエイト命令かを判断し（ステップＳＴ１０２）、ウエイト命令の場合は、子スレッドがターム命令を実行済みであるかを、子スレッドを実行するプロセスエレメント１０−２のステータスレジスタ１０５を読み出して確認する。子スレッドが既にターム命令を実行していれば、プロセスエレメント１０−２が待機状態であることを示す値がステータスレジスタ１０５に格納されている。一方、まだ子スレッドがターム命令を実行しておらす、プログラムを処理中の場合は、実行中であることを示す値が、ステータスレジスタ１０５に格納されている。
そこで、子スレッドが既にターム命令を実行済みであれば、親スレッドが実行する処理は以上であり、次の命令の実行に移る。
子スレッドがターム命令を実行していなければ、子スレッドが終了するまで待機する（ステップＳＴ１０４）。子スレッドの終了を待機する方法としては、親スレッドが子スレッドを実行するプロセスエレメント１０−２のステータスレジスタ１０５をポーリングによって監視する方法もあるし、子スレッドがターム命令を実行する際に、親スレッドを実行しているプロセスエレメント１０−１に対して、割り込みを通知する方法もある。
【００２６】
次にストア命令について説明する。ストア命令は、親スレッドが実行する命令であり、共有変数領域１３に対して値を書き込む命令である。
プロセスエレメント１０−１は、親スレッドで実行する命令がストア命令かを判断し（ステップＳＴ１０５）、ストア命令の場合は、共有メモリ部１２の共有変数領域１３に対して値を書き込む（ステップＳＴ１０６）。このとき、共有変数領域１３の投機的実行結果判定手段１３０は、共有メモリ部１２の内容と書き込む値が異なるかを判定する（ステップＳＴ１０７）。同じ場合は、論理積回路１３５から、投機的実行が失敗したことを示す信号が出力されないため、プロセスエレメント１０−１は、親スレッドが実行する処理が終了したと判断し、次の命令へ移る。値が異なる場合は、投機フラグ１３２がＯＮになっているかを確認する（ステップＳＴ１０８）。投機フラグ１３２がＯＦＦの場合は、次の命令へ移る。投機フラグ１３２がＯＮになっている場合は、子スレッドによる投機的実行が失敗したことを意味するため、論理積回路１３５から、投機的実行が失敗したことを示す信号が出力される。この信号を受けてプロセスエレメント１０−１は、子スレッドを実行しているプロセスエレメント１０−２の実行制御部１０２に対して、再実行を通知する（ステップＳＴ１０９）。再実行の通知は、割り込みによって通知する。以上の処理を終了した時点で、次の命令へ移る。
【００２７】
次に、ロード命令について説明する。親スレッドは、実行する命令がロード命令であるかを判断し（ステップＳＴ１１０）、ロード命令の場合は、メモリ上の指定されたアドレスから値を読み出す（ステップＳＴ１１１）。以上の処理を終了した時点で、次の命令へ移る。また、その他の命令については、それぞれの命令に応じた処理を行って（ステップＳＴ１１２）、次の命令に移る。
【００２８】
次に、子スレッドを実行するプロセスエレメント１０−２が行う処理を図９のフローチャートに従って説明する。
先ず、子スレッドで実行する投機ロード命令について説明する。
子スレッドが共有メモリ部１２から変数をロードする場合、並列化プログラム生成装置４は、メモリ３から値を読み出す通常のロード命令ではなく、投機ロード命令を生成する。
子スレッドを実行するプロセスエレメント１０−２は、実行する命令が投機ロード命令かを判断し（ステップＳＴ２００）、投機ロード命令の場合は、共有メモリ部１２の共有変数領域１３から値を読み出し（ステップＳＴ２０１）、その領域の該当箇所の投機フラグ１３２をＯＮにする（ステップＳＴ２０２）。以上の処理を終了した時点で、次の命令へ移る。一方、ステップＳＴ２００において、投機ロード命令ではなく、通常のロード命令の場合は、ステップＳＴ２０１に相当するメモリ３から値を読み出す処理を行い、次の命令に移る。
【００２９】
次に、子スレッドで実行する投機ストア命令について説明する。
子スレッドが共有メモリ部１２に対して、変数の値をストアする場合、並列化プログラム生成装置４は、メモリ３から値を読み出す通常のストア命令ではなく、投機ストア命令を生成する。
プロセスエレメント１０−２は、子スレッドで実行する命令が、投機ストア命令かを判断し（ステップＳＴ２０３）、投機ストア命令の場合は、テンポラリ領域１４に対して値を書き込む（ステップＳＴ２０４）。以上の処理を終了した時点で、次の処理へ移る。ステップＳＴ２０３において、投機ストア命令ではなく、通常のストア命令の場合は、メモリ３に対して値の書き込みを行い、次の命令に移る。
【００３０】
次に、子スレッドで実行するターム命令について説明する。
ターム命令は、子スレッドの処理をその位置で一旦終了することを意味する命令である。
子スレッドで実行する命令が、ターム命令であるかを判断し（ステップＳＴ２０５）、ターム命令の場合は、テンポラリ領域１４に書き込まれた値を、共有変数領域１３へ書き込む（ステップ２０６）。次に、投機フラグ１３２をＯＦＦにし（ステップＳＴ２０７）、ステータスレジスタ１０５を待機中を示す値に変更して、次の実行開始信号を待機する（ステップＳＴ２０８）。また、その他の命令については、それぞれの命令に応じた処理を行って（ステップＳＴ２０９）、次の命令に移る。
【００３１】
このように、共有メモリ部１２に値を比較する機構を付加することにより、データ依存の投機的実行において、値が異なる場合のみ、再実行が行われ、無用な再実行を抑制することができる。その結果、データ依存の投機的実行を効率良く実行することができ、プログラムの処理を高速化することができる。
【００３２】
以上のように、実施の形態１の並列処理装置によれば、単一のプログラムを複数のプロセスエレメントで実行するプログラムに分割して、これら分割したプログラムをそれぞれ複数のプロセスエレメントで並列に処理する並列処理装置において、複数のプロセスエレメントで、正の依存関係にあるデータについて投機的実行を行った場合、投機的実行における読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定する投機的実行結果判定手段とを備えたので、再実行の回数を必要最小限に抑えられると共に、投機的実行の失敗の検出を効率化でき、並列処理装置の性能向上を図ることができる。
【００３３】
実施の形態２．
図１０は、本発明の実施の形態２による並列処理装置を示す図である。
実施の形態２の並列処理装置は、図１に示す実施の形態１の構成に対して子スレッドを実行するプロセスエレメントが一つ増え、三つのプロセスエレメント（ＰＥ０，ＰＥ１，ＰＥ２）１０−１，１０−２，１０−３によって構成される。尚、各プロセスエレメント１０−１〜３の内部構成は実施の形態１と同様であるため、その図示は省略している。また、並列化プログラム生成装置４は、各プロセスエレメント１０−１〜３に対応した実行コード５１，５２，５３を生成するが、ここでの図示は省略している。メモリ３中の実行コード５１，５２，５３は、ロードされた実行コード５１〜５３を示している。
更に、プロセスエレメント１０−１〜３の拡張に伴って、実施の形態１における投機フラグ１３２を拡張し、図１１に示すように、子スレッドを実行する複数のプロセスエレメント用の複数の投機フラグ１３２ａ，１３２ｂを設けている。
また、実施の形態２の投機的実行結果判定手段１３０ａは、並列して複数の投機的実行が行われる場合、それぞれの投機的実行を行うプロセスエレメントを識別し、各プロセスエレメントの投機的実行毎に、読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定するよう構成されている。
これ以外の構成は、実施の形態１と同様である。
【００３４】
次に、この実施の形態によるフォーク命令について説明する。尚、以下の説明では実施の形態１で説明した図８および図９のフローチャートを援用する。
子スレッドのフォーク命令では、親スレッドを実行するプロセスエレメントから、子スレッドを実行するプロセスエレメントに対して、実行開始信号を通知する。
子スレッドを実行するプロセスエレメントが複数存在する場合は、親スレッドを実行するプロセスエレメントから、どの子スレッドを実行するプロセスエレメントに対して実行開始信号を通知するかを特定する必要がある。そこで、実施の形態２によるフォーク命令では、命令の引数でフォークするプロセスエレメントの番号を指定し、命令実行部１０１は、その番号で指定されたプロセスエレメントに対して、実行開始信号を通知する。つまり、実施の形態１で説明した図８のステップＳＴ１０１の処理において、フォーク命令の引数で指定されたプロセスエレメントに対して実行開始信号を通知する。
この動作を実現するため、並列化プログラム生成装置４は、複数の子スレッドを扱う状況においては、起動するスレッドを引数で特定したフォーク命令を生成する。
この実行開始信号を受けたプロセスエレメントは、そのプロセスエレメントに対応したスレッドの命令コード中に、ターム命令が現れるまで、連続して処理を行う。
【００３５】
次に、この実施の形態によるウエイト命令について説明する。ウエイト命令は、親スレッドが実行する命令であり、子スレッドと同期をとるための命令である。
複数の子スレッド用プロセスエレメントを持つ場合のウエイト命令は、図８のステップＳＴ１０３の処理において、どのプロセスエレメントで実行する子スレッドのターム命令の実行を待つかを指定する引数を持つ。この引数の値が、例えばゼロの場合、全てのプロセスエレメントで実行中の子スレッドを待機する。また、子スレッドをビットで表現し、複数の子スレッドを同時に待機する設定が可能である。例えば、子スレッドを実行するプロセスエレメントが三つ（ＰＥ１，ＰＥ２，ＰＥ３）存在し、各プロセスエレメントに対応するビットが１の時に、ウエイトの対象にする場合、ＰＥ１とＰＥ２を待つ場合は２を、ＰＥ１とＰＥ３を待つ場合は５といったように設定する。これらの子スレッドの終了の待機は、図８のステップＳＴ１０４の処理であり、個々の子スレッドを実行するプロセスエレメントのステータスレジスタ１０５をポーリングして確認する方法もあるし、子スレッドを実行するプロセスエレメントから、親スレッドを実行するプロセスエレメントに対して、終了を通知する割り込みを上げても良い。
既に子スレッドがターム命令を実行している場合は、子スレッドを待つ必要がないため、この命令は無効となり、親スレッドは後続の命令を処理する。
【００３６】
次に、この実施の形態によるストア命令について説明する。ストア命令は、親スレッドが共有メモリ部１２あるいはメモリ３に対して値を書き込む命令である。
先ず、図８のステップＳＴ１０６のように値を書き込む。次に、ステップＳＴ１０７に示すように、投機的実行結果判定手段１３０ａは値が異なるかを確認する。ここで、値が同じであれば、次の命令に移行する。値が異なっていれば、ステップＳＴ１０８に示すように投機フラグ１３２ａ（１３２ｂ）が立っているかを確認する。ここで、投機フラグ１３２ａ（１３２ｂ）が立っていれば、ステップＳＴ１０９に移り、複数存在するプロセスエレメント１０−２，１０−３のうち、該当するプロセスエレメントの実行制御部１０２に対して、再実行を通知する。投機フラグ１３２ａ（１３２ｂ）が立っていなければ、次の命令に移る。
親スレッドで実行するロード命令や上記以外の命令については、実施の形態１と全く同じ処理であるため、ここでの説明は省略する。
【００３７】
次に、この実施の形態による子スレッドで実行する投機ロード命令について説明する。
子スレッドが共有メモリ部１２から変数をロードする場合、並列化プログラム生成装置４は、メモリ３から値を読み出す通常のロード命令ではなく、投機ロード命令を生成する。
子スレッドが実行する投機ロード命令は、共有メモリ部１２から値を読み出す際に、値を読み出す対象エリアの投機フラグ１３２ａ（１３２ｂ）を立てる。
この実施の形態では、複数の子スレッド用に複数のプロセスエレメント１０−２，１０−３が存在するため、図１１に示すように、共有変数領域１３に各プロセスエレメント１０−２，１０−３に１対１に対応した投機フラグを設ける。即ち、各要素のデータ１３１毎に、子スレッド用に複数のプロセスエレメント１０−２，１０−３に対応した投機フラグ１３２ａ，１３２ｂを設ける。子スレッドが投機ロード命令を実行すると、図９のステップＳＴ２０２の処理において、そのプロセスエレメントに対応した投機フラグ１３２ａ（１３２ｂ）を立てる。これにより、どのプロセスエレメント上で実行している子スレッドが、投機的に値を読み出したのかを表現する。
【００３８】
次に、子スレッドで実行する投機ストア命令について説明する。
子スレッドが共有メモリ部１２に対して、変数の値をストアする場合、並列化プログラム生成装置４は、メモリ３から値を読み出す通常のストア命令ではなく、投機ストア命令を生成する。
子スレッドでの投機ストア命令は、図９のステップＳＴ２０４の処理において、その子スレッドに対応したテンポラリ領域１４に対して、書き込み対象アドレスと値の両方を書き込む。
この書き込みの際に、複数の子スレッドが存在するこの実施の形態では、図１２に示すように、ＰＥ番号１４１を設け、プロセスエレメント（ＰＥ１，ＰＥ２）１０−２，１０−３のＰＥ番号を付加することによって、どの子スレッドが値を書き込んだかを管理する。
【００３９】
次に、子スレッドで実行するターム命令について説明する。
ターム命令は、子スレッドの処理をその位置で一旦終了することを意味する命令である。
複数の子スレッド用プロセスエレメント１０−２，１０−３を持つ場合、ターム命令は、それぞれの子スレッドに対応して、それまでその子スレッドが書き込んだアドレスとデータを一斉に共有変数領域１３に書き込む処理を行う。これは、図９のステップＳＴ２０６に該当する処理である。図１２に示すＰＥ番号１４１に基づいて、ターム命令を実行するプロセスエレメント１０−２，１０−３に該当する箇所について、テンポラリ領域１４から共有変数領域１３に対して書き込みを行う。また、図９のステップＳＴ２０７の処理として、図１１に示す投機フラグ１３２ａ，１３２ｂのうち、そのプロセスエレメント１０−２，１０−３に関するものをＯＦＦにする。その後、そのプロセスエレメント１０−２，１０−３に関しては、次に親スレッドからフォーク命令によって起動されまるまで処理を中断する。
【００４０】
このように、複数の子スレッドを並列に実行するために三つ以上のプロセスエレメント１０−１〜３が存在する場合、共有メモリ部１２に値を比較する機構を付加すると共に、各プロセスエレメント１０−１〜３に対応して投機フラグ１３２ａ，１３２ｂやテンポラリ領域１４への値書き込みの管理を行うことによって、データ依存の投機的実行において、値が異なるプロセスエレメントによる処理のみが再実行され、無用な再実行を抑制し、効率よくプログラムを実行することができる。
【００４１】
以上のように実施の形態２の並列処理装置によれば、投機的実行結果判定手段は、並列して複数の投機的実行が行われる場合、それぞれの投機的実行を行うプロセスエレメントを識別し、各プロセスエレメントの投機的実行毎に、読み出した値と書き込む値とを比較し、これらの値が異なった場合にのみ投機的実行が失敗したと判定するようにしたので、複数のプロセスエレメントで並列して投機的実行が行われる場合でも、再実行の回数を必要最小限に抑えられると共に、投機的実行の失敗の検出を効率化でき、並列処理装置の性能向上を図ることができる。
【００４２】
実施の形態３．
図１３は、本発明の実施の形態３による並列処理装置を示す構成図である。
図１３の並列処理装置は、図２に示した実施の形態１のプロセスエレメントの構成に対して、実行制御部１０２ａに、成否履歴テーブル１０６と投機的実行可否判定手段１０７とを加えることによって構成される。
成否履歴テーブル１０６とは、過去の投機的実行が成功したか否かを記録するデータテーブルである。また、投機的実行可否判定手段１０７とは、過去の投機的実行の成否を基に、投機的実行の実施の可否を判断する手段である。図７に示したように、投機的実行に失敗した場合は、プログラム順序で確定的に実行する場合に比べ、再実行に向けた復帰処理にオーバーヘッドが発生することによって、処理時間が長くなる。このため、投機的実行可否判定手段１０７によって、失敗が予想される状況下では投機的実行をせず、失敗による処理時間の延長を防ぐ。
【００４３】
特に、プログラム中の投機的実行箇所の間に、投機的実行の成否について関連がある場合は、そのパターンに基づいて投機的実行の成否を予想することによって、投機的実行の精度を向上する。
例えば、プログラム中に投機的実行の対象箇所が４箇所あったとする。この中で、１番目と３番目の過去何回かの投機的実行の履歴が同じ成否パターンの場合、これらの間に関連があると認識する。それ以降の実行時には、１番目の投機的実行が成功すれば、３番目の投機的実行も成功すると予想して、投機的に実行する。一方、１番目の投機的実行が失敗すれば、３番目の投機的実行も失敗すると予想して、投機的な実行を実施せず、プログラム順序で確定的に実行する。
【００４４】
このような動作を実現する処理の流れを図１４に示し、以下で説明する。
例えば、図１５に示すような、プログラム中の各投機的実行箇所について、過去１６回までの成否を、投機的実行が成功した場合に１、失敗した場合に０で表現する投機的実行の成否履歴テーブル１０６を設ける。この成否履歴テーブル１０６には、各投機的実行箇所に応じて１６ビット変数を設け、プログラムを１回実行する毎に、投機的実行の成否結果を１ビットで表現し、これまでの結果を１ビット左シフトして、今回の結果をＬＳＢに格納する。このようにして、直近の１６回の実行について、投機的実行が成功したか、失敗したかを格納する。
【００４５】
投機的実行が行われた際に、ステップＳＴ３００で投機的実行に成功したかを判断する。投機的実行の成否の判断は、子スレッドがターム命令を実行するまで親スレッドを実行するプロセスエレメントから再実行の指示が来なかったことで判断する。再実行の指示が無ければ、投機的実行の成功であり、再実行の指示があれば、投機的実行に失敗したことになる。
投機的実行に成功した場合は、ステップＳＴ３０１のように成否履歴テーブル１０６の該当セルに１を書き込む。また、失敗した場合はステップＳＴ３０２のように成否履歴テーブル１０６の該当セルに０を書き込む。ここで、該当セルとは、ある投機的実行に対応した行を１ビット左シフトして空いた、その行の０の列を指す。
例えば、図１５に示す成否履歴テーブル１０６において、No.１に対応する投機的実行結果が判明した時点で、No.１の行を１ビット左シフトし、その行の０の列にNo.１に対応する投機的実行箇所の新たな結果を格納する。次に、No.２に対応する投機的実行結果が判明した時点で、No.２の行を１ビット左シフトし、その行のゼロの列にNo.２に対応する投機的実行箇所の新たな結果を格納する。以下、各投機的実行箇所の実行結果が判明する度に、対応する行をビットシフトして、その行のゼロの列に新たな結果を格納する。
【００４６】
このような処理によって、成否履歴テーブル１０６には、常に列数分の最新の履歴が格納される。尚、この成否履歴テーブル１０６は、投機的実行の予想が当たったか外れたかの結果を格納するのではなく、結果的に投機的実行が成功したか否かを格納する。
【００４７】
このメモリ要素の値の変化の検出は、図１３に示す投機的実行結果判定手段１３０ｂにおける比較器１３４によって行うことができる。実施の形態１では、更に投機フラグ１３２との論理積によって、投機的実行の実行成否として扱っていた。しかし、実施の形態３では、投機的実行が行われたかどうかは問題ではないため、比較器１３４の出力をそのまま投機的実行の成否履歴テーブル１０６に格納する。
【００４８】
投機的実行可否判定手段１０７は、プログラムを１回終了する度に、成否履歴テーブル１０６の各投機的実行箇所を示す１６ビット変数間で比較を行い、一致するものを探す。一致の検出は、例えば図１６に示す構成で行うことによって、効率的に行うことができる。
これは、成否履歴テーブル１０６上の全ての値を総当り方式で比較するものであり、履歴比較器１０７ａと履歴一致箇所検出装置１０７ｂによって、一致する値の存在を直ちに判定することができるが、成否履歴テーブル１０６のサイズに応じて必要となる履歴比較器１０７ａの数が増加し、多くのハードウェアリソースを必要とする。
また、別の方法として、プログラムの実行が終了した際に、成否履歴テーブル１０６上の二つの値をランダムに選択し、比較する方法が挙げられる。プログラム実行後に多数の比較処理を行うと、処理のオーバーヘッドが大きくなるため、二つあるいは、数点について比較を行う。この比較の対象は、ランダムに選択することもできるし、比較する一方を固定しておき、もう一方を毎回変化させることもできる。この方法では、値の一致は確率的に検出されることになるため、全ての一致を検出することはできないが、この処理に向けてハードウェアを追加する必要はない。
【００４９】
成否履歴テーブル１０６で一致する箇所が存在する場合、プログラム前方での投機的実行の成否が、プログラム後方の投機的実行の成否と関係することを意味する。例えば、成否履歴テーブル１０６が、図１５に示すような状態であった場合、No.１の成否パターンとNo.３の成否パターンは同一であるため、No.１の投機的実行の成否がNo.３の投機的実行の成否と関係があることを意味している。そこで、あるプログラムを実行した場合No.１の投機的実行の結果が失敗であった場合、No.３の箇所でも失敗が予想されるとしてNo.３の箇所では投機的実行を不実施とする。
【００５０】
このように、投機的実行可否判定手段１０７がこの情報を基に投機的実行の可否を予想することによって、個々の投機的実行箇所の履歴に基づいて予想するのではなく、投機的実行箇所間の関係を基に予想を行うため、投機的実行の成功確率を向上し、性能を改善することができる。
この例では、１６ビット変数を例に、処理の流れを説明したが、ビット数がこの値に制限される訳ではない。
【００５１】
このように、投機的実行の成否履歴テーブル１０６と、そのテーブルが示す過去の成否パターンを基に、投機的実行を行うか否かの判断を行う投機的実行可否判定手段１０７を設け、プログラム中で投機的実行を行う箇所について、個々の投機的実行箇所の履歴のみに基づかず、これらの投機的実行箇所の間のつながりを考慮して投機的実行の可否判断を行うことにより、投機的実行が失敗し、再実行によるオーバーヘッドが発生する状況を削減できるため、全体の処理性能を向上することができる。
【００５２】
尚、上記実施の形態３は、実施の形態１の構成に適用した例を説明したが、実施の形態２の構成に対して適用してもよい。
【００５３】
以上のように、実施の形態３の並列処理装置によれば、投機的実行の成否の履歴を格納する成否履歴テーブルと、成否履歴テーブルにおける成否履歴のパターンに基づいて、同じ成否結果になる投機的実行箇所を検出し、失敗が予想される箇所については、投機的実行の不実施と判定する投機的実行可否判定手段とを備えたので、投機的実行の履歴から、実行に失敗する箇所についてプログラム順に確定的に実行するため、失敗時のオーバーヘッドが無く、性能向上に寄与することができる。
【００５４】
実施の形態４．
図１７は、本発明の実施の形態４による並列処理装置を示す図である。
実施の形態３では、成否履歴テーブル１０６を基に、投機的実行箇所の間での関係に注目して、投機的実行の可否判断を行うよう構成したが、この実施の形態４では、実行制御部１０２ｂが、成否履歴テーブル１０６ａのうち、実行中のプログラムに関し、前方の投機的実行箇所の実行成否結果に基づいて、後方の投機的実行の可否判断を行う。即ち、実施の形態４の投機的実行可否判定手段１０８は、現在実行中のプログラムについて、成否履歴テーブル１０６ａにおける成否履歴に基づき、投機的実行の失敗回数が規定値を超えるか、または、予め定めたプログラムの最悪処理時間を超えてしまうと判断される場合に以降の投機的実行を不実施と判定するよう構成されている。これ以外の構成は実施の形態１と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００５５】
プログラムで制御する対象のシステムによっては、プログラムの最悪実行時間がある時間内に納まることが必須である場合がある。このようなシステムは、ハードリアルタイム性が要求されるシステムと呼ばれる。ハードリアルタイムなシステムにおいては、デッドラインとなる時間を越えることは許されないため、必ずその時間内にプログラムの処理を完了することが要求される。
こうしたシステムにおいて、投機的実行を行う複数の箇所で、連続して投機的実行に失敗すると、プログラムの再実行による処理時間のオーバーヘッドが発生するため、システム設計時に設定したデッドラインを守ることが保証できなくなる場合がある。
投機的実行は、プログラムを並列に処理することで、プログラムの処理時間を短縮し、システムの性能を向上することを目的としているが、失敗した場合には、プログラムの再実行というオーバーヘッドが避けられない。
そこで、実施の形態４では、プログラム実行中に、これ以上プログラムの再実行によるオーバーヘッドが発生するとデッドラインを守れなくなる状況下では、それ以降のプログラム中に存在する投機的実行を一切やめ、プログラム順で確定的に実行する方を選択する。
その結果、投機的実行の失敗によるオーバーヘッドが発生しないため、ハードリアルタイムを完全に守ることができる。
【００５６】
投機的実行可否判定手段１０８が、そのプログラム実行周期において何点の投機的実行の失敗を検出すると、その後の投機的実行を無効化するかは、入力したプログラムの処理内容と、設定される最悪実行時間に依存する。
このため、投機的実行可否判定手段１０８で管理する投機的実行失敗時の制限回数は、シミュレーションによって全ての投機的実行箇所において失敗した際の処理時間を求め、要求される最悪実行時間を越えない回数とする方法がある。また、実際の処理時間をトレースしておき、その結果を基に投機的実行失敗時の制限回数を求める方法もある。
【００５７】
尚、実施の形態４では、実際に実行された投機的実行の成否が重要であり、投機的実行を実施したかどうかを判断するため、図１７に示す構成とし、投機フラグ１３２の情報を含んだ情報を成否履歴テーブル１０６ａで扱う。
【００５８】
このように、投機的実行の成否履歴テーブル１０６ａを用いて、プログラム前半での投機的実行の成否を基に後半の投機的実行の可否判断を行う。前半での投機的実行に連続して失敗する状況においては、投機的実行の失敗によるプログラムの再実行で発生する処理時間の延長を、それ以上起こさないようにするため、プログラム順で確定的に実行するようにする。このような条件下において、投機的実行をしないことにより、プログラムの最悪実行時間を抑えることができる。
【００５９】
尚、上記実施の形態４は、実施の形態１の構成に適用した例を説明したが、実施の形態２の構成に対して適用してもよい。
【００６０】
以上のように、実施の形態４の並列処理装置によれば、投機的実行の成否の履歴を格納する成否履歴テーブルと、現在実行中のプログラムについて、成否履歴テーブルにおける成否履歴に基づき、投機的実行の失敗回数が規定値を超えるか、または、予め定めたプログラムの最悪処理時間を超えてしまうと判断される場合に以降の投機的実行を不実施と判定する投機的実行可否判定手段とを備えたので、プログラムの最悪実行時間がある時間内に納まることが必須であるようなシステムであっても、この最悪実行時間を守ることができる。
【図面の簡単な説明】
【００６１】
【図１】この発明の実施の形態１による並列処理装置を示す構成図である。
【図２】この発明の実施の形態１による並列処理装置のプロセスエレメントを示すブロック図である。
【図３】この発明の実施の形態１による並列処理装置の共有変数領域の説明図である。
【図４】この発明の実施の形態１による並列処理装置の投機的実行結果判定手段の構成を示す説明図である。
【図５】この発明の実施の形態１による並列処理装置のテンポラリ領域の説明図である。
【図６】この発明の実施の形態１による並列処理装置の並列化プログラム生成装置の構成図である。
【図７】この発明の実施の形態１による並列処理装置のデータ依存の投機的実行の様子を示す説明図である。
【図８】この発明の実施の形態１による並列処理装置の親スレッドを実行するプロセスエレメントが行う処理のフローチャートである。
【図９】この発明の実施の形態１による並列処理装置の子スレッドを実行するプロセスエレメントが行う処理のフローチャートである。
【図１０】この発明の実施の形態２による並列処理装置を示す構成図である。
【図１１】この発明の実施の形態２による並列処理装置における投機フラグを示す説明図である。
【図１２】この発明の実施の形態２による並列処理装置のテンポラリ領域の説明図である。
【図１３】この発明の実施の形態３による並列処理装置を示す構成図である。
【図１４】この発明の実施の形態３による並列処理装置における成否履歴テーブルの処理を示すフローチャートである。
【図１５】この発明の実施の形態３による並列処理装置の成否履歴テーブルを示す説明図である。
【図１６】この発明の実施の形態３による並列処理装置の投機的実行可否判定手段の具体的手段を示す構成図である。
【図１７】この発明の実施の形態４による並列処理装置を示す構成図である。
【符号の説明】
【００６２】
１  プロセッサ、２  バス、３  メモリ、４  並列化プログラム生成装置、５  入力プログラム、１０−１，１０−２，１０−３  プロセスエレメント、１２  共有メモリ部、１３  共有変数領域、１４  テンポラリ領域、５１，５２，５３  実行コード、１０１  命令実行部、１０２  実行制御部、１０６，１０６ａ  成否履歴テーブル、１０７，１０８  投機的実行可否判定手段、１３０，１３０ａ，１３０ｂ  投機的実行結果判定手段、１３１  データ、１３２，１３２ａ，１３２ｂ  投機フラグ、１３３  書込データ、１３４  比較器、１３５  論理積回路、１４１  ＰＥ番号。
【図１】
2009048269.tif 000003
【図２】
2009048269.tif 000004
【図３】
2009048269.tif 000005
【図４】
2009048269.tif 000006
【図５】
2009048269.tif 000007
【図６】
2009048269.tif 000008
【図７】
2009048269.tif 000009
【図８】
2009048269.tif 000010
【図９】
2009048269.tif 000011
【図１０】
2009048269.tif 000012
【図１１】
2009048269.tif 000013
【図１２】
2009048269.tif 000014
【図１３】
2009048269.tif 000015
【図１４】
2009048269.tif 000016
【図１５】
2009048269.tif 000017
【図１６】
2009048269.tif 000018
【図１７】
2009048269.tif 000019