(57)【要約】【課題】より実際的でかつ、さらに機能拡張したプログラム変換装置を提供する。【解決手段】本発明のプログラム変換装置１は、プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成部１３０と、前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換部１４０と、変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化部１０２とを具備する。【選択図】図３
2010039536.tif 000002
【特許請求の範囲】
【請求項１】
プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成部と、
前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換部と、
変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化部と
を具備するプログラム変換装置。
【請求項２】
前記スレッド作成部は、
前記プログラム部分の複数の実行経路のうち１つの実行経路を構成する命令を複写することにより、スレッドの本体となるスレッド本体ブロックを生成するスレッド本体ブロック生成部と、
他のスレッドの実行を停止させる命令で構成される他スレッド停止ブロックを生成し、前記スレッド本体ブロックの後に配置する他スレッド停止ブロック生成部と
を具備し、
前記置換部は、
前記スレッド本体ブロックの入口および出口で生きている変数である出入口生存変数を検出する出入口生存変数検出部と、
前記出入口生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記出入口生存変数を新たに生成した変数に置換する出入口変数置換部と、
前記出入口生存変数のうち入口で生きている変数が保持する値を、前記出入口変数置換部で置換した変数に代入する命令で構成される入口ブロックを生成し、前記スレッド本体ブロックの前に配置する入口ブロック生成部と、
前記出入口変数置換部で置換した変数が保持する値を、前記出入口生存変数のうち出口で生きている変数へ代入する命令で構成される出口ブロックを生成し、前記他スレッド停止ブロックの後に配置する出口ブロック生成部と、
前記出入口生存変数検出部で検出されない変数でかつ前記スレッド本体ブロック中に出現する変数であるスレッド内生存変数を検出するスレッド内生存変数検出部と、
検出された前記スレッド内生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記スレッド内生存変数を新たに生成した変数に置換するスレッド内生存変数置換部と
を具備する請求項１記載のプログラム変換装置。
【請求項３】
前記スレッド作成部は、さらに、
前記スレッド本体ブロック中の条件分岐命令の分岐先の命令が、当該スレッド本体ブロックの実行経路に存在しない場合は、当該分岐先の命令として当該スレッドを停止させる自スレッド停止命令を生成し、当該スレッド本体ブロック内に配置する自スレッド停止命令生成部
を具備する請求項２記載のプログラム変換装置。
【請求項４】
前記自スレッド停止命令生成部は、さらに、
前記スレッド本体ブロック中の条件分岐命令の判定条件が不成立である場合の分岐先の命令が、当該スレッド本体ブロックの実行経路に存在しない場合は、当該条件分岐命令の判定条件を反転させ、反転した判定条件が成立した時の分岐先の命令として、自身のスレッドを停止させる自スレッド停止命令を生成し、当該スレッド本体ブロック内に配置する
請求項３記載のプログラム変換装置。
【請求項５】
前記プログラム変換装置は、さらに、前記置換部によって変数を置換されたスレッド中の命令をより効率のよいものに最適化するスレッド内最適化部を具備し、
前記スレッド並列化部は、前記スレッド内最適化部によって最適化されたスレッドを投機的に並列実行させるプログラムを生成する
請求項２記載のプログラム変換装置。
【請求項６】
前記スレッド内最適化部は、前記置換部によって変数を置換されたスレッド中の前記入口ブロックの命令に対して、前記スレッド本体ブロック及び前記出口ブロック中へのコピー伝播及び不要コード最適化を実施する入口ブロック内命令コピー伝播最適化部を具備する
請求項５記載のプログラム変換装置。
【請求項７】
前記スレッド内最適化部は、さらに、
前記置換部によって変数を置換されたスレッド中の命令のデータの更新及び参照の実行順に基づいて、前記変数を置換されたスレッド中の命令の依存関係を算出する一般依存関係算出部と、
前記出口ブロック中の命令に先立って前記他スレッド停止ブロック中の命令が実行されるような依存関係と、前記他スレッド停止ブロック中にある命令に先立って、前記自スレッド停止命令が実行されるような依存関係とを発生する特殊依存発生部と、
前記一般依存関係算出部で算出された依存関係と、前記特殊依存発生部で算出された依存関係とに基づいて、スレッド内の命令を並列化する命令スケジューリング部と
を具備する請求項５記載のプログラム変換装置。
【請求項８】
前記経路情報は、経路上に存在する変数と、前記変数毎に予め定められた定数値とを含み、
前記プログラム変換装置は、さらに、
前記変数の値が、前記定数値と等しいか否かを判定する命令と、等しくない場合、当該スレッドを停止する命令とで構成される定数値判定ブロックを生成し、前記入口ブロックの前に配置する定数値判定ブロック生成部と、
前記スレッド本体ブロック中の前記変数を、前記定数値に変換する定数値変換部とを具備し、
前記スレッド並列化部は、変換後の複数のスレッドを投機的に並列実行させるプログラムを生成する
請求項２又は３記載のプログラム変換装置。
【請求項９】
前記経路情報は、経路上に存在する変数と、前記変数毎に予め定められた定数値とを含み、
前記プログラム変換装置は、さらに、
前記変数の値が、前記定数値と等しいか否かを判定する命令と、等しくない場合、当該スレッドを停止する命令とで構成される定数値判定ブロックを生成し、前記入口ブロックの前に配置する定数値判定ブロック生成部と、
前記定数値判定ブロック生成部で等しいと判定された場合、当該スレッド中の前記スレッド本体ブロック中の前記変数を、前記定数値に変換する定数値変換部とを具備し、
前記スレッド並列化部は、変換後の複数のスレッドを投機的に並列実行させるプログラムを生成する
請求項７記載のプログラム変換装置。
【請求項１０】
前記特殊依存発生部は、さらに、前記他スレッド停止ブロック中の命令に先立って、前記定数値判定ブロック中の命令が実行されるような特別な依存関係を発生する
請求項９記載のプログラム変換装置。
【請求項１１】
前記複数のスレッドは、第１のスレッドと第２のスレッドとを含み、
前記スレッド本体ブロック生成部は、
前記第１及び第２のスレッドの包含関係を算出する経路包含関係算出部と、
前記スレッドの包含関係から、前記第１のスレッドが前記第２のスレッドを包含する場合に、前記第１のスレッドから前記第２のスレッドと重複する経路を削除するスレッド本体ブロック経路簡略化部と
を具備する請求項２又は１０記載のプログラム変換装置。
【請求項１２】
前記スレッド並列化部は、
前記複数のスレッドに含まれる第１のスレッドと第２のスレッドとに対して、前記第１のスレッドと等価な経路が、前記第２のスレッドと等価な経路に含まれるか否かを判定し、含まれていると判定した場合、前記第１のスレッドが前記第２のスレッドに包含されているとみなして、スレッド間の包含関係を算出するスレッド間包含関係算出部と、
前記経路情報から、経路の実行確率と、変数が保持する値の保持確率により、生成したスレッドの平均実行時間を算出するスレッド平均実行時間算出部と、
前記第１のスレッドが前記第２のスレッドに包含されており、かつ、前記第２のスレッドの平均実行時間が、前記第１のスレッドの平均実行時間より短い時に、前記第１のスレッドを削除する確率情報スレッド削除部と
を具備する請求項２記載のプログラム変換装置。
【請求項１３】
前記プログラムは、経路を識別する情報である経路識別情報を含み、
前記プログラム変換装置は、さらに、前記経路識別情報を解析して前記経路情報を抽出する経路解析部
を具備する請求項１記載のプログラム変換装置。
【請求項１４】
前記プログラムは、経路上に存在する変数が保持する値を示す変数保持値情報を含み、
前記経路解析部は、前記経路識別情報と、前記変数保持値情報とを解析して、変数が保持する値を特定する変数保持値解析手段を具備する請求項１３記載のプログラム変換装置。
【請求項１５】
前記プログラムは、経路を識別する情報である経路識別情報と、経路の実行確率情報と、経路上に存在する変数が保持する値を示す変数保持値情報と、変数が保持する値の保持確率情報とを含み、
前記プログラム変換装置は、さらに、前記経路識別情報と、前記実行確率情報と、前記変数保持値情報と、前記保持確率情報とに従って、前記実行確率及び前記保持確率を特定する確率特定手段を具備する請求項１２記載のプログラム変換装置。
【請求項１６】
プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成ステップと、
前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換ステップと、
変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化ステップと
を含むプログラム変換方法。
【請求項１７】
前記スレッド作成ステップは、
前記プログラム部分の複数の実行経路のうち１つの実行経路を構成する命令を複写することにより、スレッドの本体となるスレッド本体ブロックを生成するスレッド本体ブロック生成ステップと、
他のスレッドの実行を停止させる命令で構成される他スレッド停止ブロックを生成し、前記スレッド本体ブロックの後に配置する他スレッド停止ブロック生成ステップと
を含み、
前記置換ステップは、
前記スレッド本体ブロックの入口および出口で生きている変数である出入口生存変数を検出する出入口生存変数検出ステップと、
前記出入口生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記出入口生存変数を新たに生成した変数に置換する出入口変数置換ステップと、
前記出入口生存変数のうち入口で生きている変数が保持する値を、前記出入口変数置換ステップで置換した変数に代入する命令で構成される入口ブロックを生成し、前記スレッド本体ブロックの前に配置する入口ブロック生成ステップと、
前記出入口変数置換ステップで置換した変数が保持する値を、前記出入口生存変数のうち出口で生きている変数へ代入する命令で構成される出口ブロックを生成し、前記他スレッド停止ブロックの後に配置する出口ブロック生成ステップと、
前記出入口生存変数検出ステップで検出されない変数でかつ前記スレッド本体ブロック中に出現する変数であるスレッド内生存変数を検出するスレッド内生存変数検出ステップと、
検出された前記スレッド内生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記スレッド内生存変数を新たに生成した変数に置換するスレッド内生存変数置換ステップとを含み、
前記プログラム変換方法は、さらに、前記置換部によって変数を置換されたスレッド中の命令をより効率のよいものに最適化するスレッド内最適化ステップを含み、
前記スレッド内最適化ステップは、
前記置換ステップによって変数を置換されたスレッド中の前記入口ブロックの命令に対して、前記スレッド本体ブロック及び前記出口ブロック中へのコピー伝播及び不要コード最適化を実施する入口ブロック内命令コピー伝播最適化ステップと、
前記置換ステップによって変数を置換されたスレッド中の命令のデータの更新及び参照の実行順に基づいて、前記変数を置換されたスレッド中の命令の依存関係を算出する一般依存関係算出ステップと、
前記出口ブロック中の命令に先立って前記他スレッド停止ブロック中の命令が実行されるような依存関係と、前記他スレッド停止ブロック中にある命令に先立って、前記自スレッド停止命令が実行されるような依存関係とを発生する特殊依存発生ステップと、
前記一般依存関係算出ステップで算出された依存関係と、前記特殊依存発生ステップで算出された依存関係とに基づいて、スレッド内の命令を並列化する命令スケジューリングステップとを含み、
前記スレッド並列化ステップにおいて、前記スレッド内最適化ステップによって最適化されたスレッドを投機的に並列実行させるプログラムを生成する
請求項１６記載のプログラム変換方法。
【請求項１８】
前記経路情報は、経路上に存在する変数と、前記変数毎に予め定められた定数値とを含み、
前記プログラム変換方法は、さらに、
前記変数の値が、前記定数値と等しいか否かを判定する命令と、等しくない場合、当該スレッドを停止する命令とで構成される定数値判定ブロックを生成し、前記入口ブロックの前に配置する定数値判定ブロック生成ステップと、
前記スレッド本体ブロック中の前記変数を、前記定数値に変換する定数値変換ステップとを含み、
前記スレッド並列化ステップにおいて、変換後の複数のスレッドを投機的に並列実行させるプログラムを生成する
請求項１７記載のプログラム変換方法。
【請求項１９】
前記特殊依存発生ステップにおいて、さらに、前記他スレッド停止ブロック中の命令に先立って、前記定数値判定ブロック中の命令が実行されるような特別な依存関係を発生する
請求項１８記載のプログラム変換方法。
【請求項２０】
プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成ステップと、
前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換ステップと、
変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化ステップと
をコンピュータに実行させるプログラム。
【請求項２１】
前記スレッド作成ステップは、
前記プログラム部分の複数の実行経路のうち１つの実行経路を構成する命令を複写することにより、スレッドの本体となるスレッド本体ブロックを生成するスレッド本体ブロック生成ステップと、
他のスレッドの実行を停止させる命令で構成される他スレッド停止ブロックを生成し、前記スレッド本体ブロックの後に配置する他スレッド停止ブロック生成ステップと
を含み、
前記置換ステップは、
前記スレッド本体ブロックの入口および出口で生きている変数である出入口生存変数を検出する出入口生存変数検出ステップと、
前記出入口生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記出入口生存変数を新たに生成した変数に置換する出入口変数置換ステップと、
前記出入口生存変数のうち入口で生きている変数が保持する値を、前記出入口変数置換ステップで置換した変数に代入する命令で構成される入口ブロックを生成し、前記スレッド本体ブロックの前に配置する入口ブロック生成ステップと、
前記出入口変数置換ステップで置換した変数が保持する値を、前記出入口生存変数のうち出口で生きている変数へ代入する命令で構成される出口ブロックを生成し、前記他スレッド停止ブロックの後に配置する出口ブロック生成ステップと、
前記出入口生存変数検出ステップで検出されない変数でかつ前記スレッド本体ブロック中に出現する変数であるスレッド内生存変数を検出するスレッド内生存変数検出ステップと、
検出された前記スレッド内生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記スレッド内生存変数を新たに生成した変数に置換するスレッド内生存変数置換ステップとを含み、
前記プログラム変換方法は、さらに、前記置換部によって変数を置換されたスレッド中の命令をより効率のよいものに最適化するスレッド内最適化ステップを含み、
前記スレッド内最適化ステップは、
前記置換ステップによって変数を置換されたスレッド中の前記入口ブロックの命令に対して、前記スレッド本体ブロック及び前記出口ブロック中へのコピー伝播及び不要コード最適化を実施する入口ブロック内命令コピー伝播最適化ステップと、
前記置換ステップによって変数を置換されたスレッド中の命令のデータの更新及び参照の実行順に基づいて、前記変数を置換されたスレッド中の命令の依存関係を算出する一般依存関係算出ステップと、
前記出口ブロック中の命令に先立って前記他スレッド停止ブロック中の命令が実行されるような依存関係と、前記他スレッド停止ブロック中にある命令に先立って、前記自スレッド停止命令が実行されるような依存関係とを発生する特殊依存発生ステップと、
前記一般依存関係算出ステップで算出された依存関係と、前記特殊依存発生ステップで算出された依存関係とに基づいて、スレッド内の命令を並列化する命令スケジューリングステップとをコンピュータに実行させ、
前記スレッド並列化ステップにおいて、前記スレッド内最適化ステップによって最適化されたスレッドを投機的に並列実行させる
請求項２０記載のプログラム。
【請求項２２】
前記経路情報は、経路上に存在する変数と、前記変数毎に予め定められた定数値とを含み、
前記プログラム変換方法は、さらに、
前記変数の値が、前記定数値と等しいか否かを判定する命令と、等しくない場合、当該スレッドを停止する命令とで構成される定数値判定ブロックを生成し、前記入口ブロックの前に配置する定数値判定ブロック生成ステップと、
前記スレッド本体ブロック中の前記変数を、前記定数値に変換する定数値変換ステップとをコンピュータに実行させ、
前記スレッド並列化ステップにおいて、変換後の複数のスレッドを投機的に並列実行させるプログラムを生成する
請求項２１記載のプログラム。
【請求項２３】
前記特殊依存発生ステップにおいて、さらに、前記他スレッド停止ブロック中の命令に先立って、前記定数値判定ブロック中の命令が実行されるような特別な依存関係を発生する
請求項２２記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム変換装置、プログラム変換方法およびプログラム変換プログラムに関わり、特に、プログラム実行時間を短縮するために、プログラムの特定部分の実行経路を投機的に実行可能な複数スレッドに変換するプログラム変換の技術に関する。
【背景技術】
【０００２】
昨今のディジタルテレビ、ブルーレイレコーダ、携帯電話など、マルチメディア処理の量と質の拡大や、通信速度の拡大、ゲーム機器に代表されるインタフェース処理量の拡大等により、民生用組込機器に搭載されるプロセッサへの性能向上要望は留まることはない。
【０００３】
また、昨今の半導体技術の進歩により、民生用組込機器に搭載されるプロセッサにおいても、マルチプロセッサ構成によりプログラム部分（スレッド）を並列実行できるプロセッサや、単一プロセッサで複数スレッドを並列実行できるスレッド並列実行機能を持たせたプロセッサを安価で使用できる環境が整いつつある。
【０００４】
一方、これらプロセッサを有効活用するコンパイラ等のプログラム変換装置において、は、プロセッサの計算資源を効率よく利用し、よりプログラムを高速に実行させることが、重要となる。
【０００５】
このようなスレッド並列化機能をもつプロセッサのプログラム変換方法としては、（特許文献１）がある。
【０００６】
この文献の方法は、プログラムの特定部分を、実行経路毎にスレッド化し、かつ、スレッド毎に最適化を施し、複数のスレッドを並列に実行することにより、プログラムの特定部分を短時間で実行させるものである。短時間に実行できる主要因は、特定の実行経路に特化した最適化を施すことができること、および、生成したスレッドを並列に実行することにある。
【０００７】
通常、プログラムの特定部分の実行経路は、実行時には唯一の実行経路が選択されて実行されるものである。一方、（特許文献１）が提供するプログラム変換装置は、実行経路毎に生成されたスレッドを並列に実行し、本来ならば選択されない実行経路も並列に実行するという、「投機的」なスレッド実行を行っている。即ち、（特許文献１）は、プログラムの特定部分の実行経路を投機的に実行するスレッドに変換する「ソフトウェア・スレッド投機変換」を行うプログラム変換装置を提供している。
【０００８】
例えば、図３８（（特許文献１）の図３）に示すように、まず、変換前のプログラム部分であるスレッド３００から、スレッド３０１、スレッド３０２、スレッド３０３を生成する。ここで、スレッド３０１中の、Ｉ、Ｊ、Ｋ、Ｑ、Ｓ、Ｌ、Ｕ、ＴおよびＸは基本ブロックを示す。ここで、基本ブロックとは、スレッド中に分岐および合流を含まず、連続的に処理される部分のことであり、基本ブロック中の命令は基本ブロックの入口から出口に向かって順に実行される。基本ブロックからでている矢印は実行の遷移を表現しており、例えば、基本ブロックＩの出口から基本ブロックＪ、基本ブロックＸに分岐することを意味している。なお、基本ブロックの最初に合流を含んでも、最後に分岐を含んでもよい。
【０００９】
また、スレッド３０１中の基本ブロックＩ、ＪおよびＱは、実行遷移がスレッド３００において、基本ブロックＩ、基本ブロックＪ、基本ブロックＱの順に移動した場合の実行経路とと等価な動作を行う基本ブロックを示している。スレッド３０２の基本ブロックＩ、Ｊ、Ｋ、ＳおよびＴ、スレッド３０３の基本ブロックＩ、Ｊ、ＫおよびＬも同様である。
【００１０】
次に取り出したスレッド毎に、最適化を行い１スレッド当たりの実行時間を短縮し、かつ、スレッド３００、スレッド３０１、スレッド３０２及びスレッド３０３を並列に実行することにより、変換前のプログラム部分であるスレッド３００を単独で実行する場合と比較して、実行時間の短縮を図れるという効果がある。
【特許文献１】特開２００６−１５４９７１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明においては、基本の考え方は（特許文献１）に基づくが、共有メモリ型のマルチプロセッサ構成のコンピュータシステムをターゲットに、より実際的でかつ、さらに機能拡張したプログラム変換装置を提供することを目的とする。具体的には、命令を並列に実行可能なプロセッサの共有メモリ型のマルチプロセッサ構成のコンピュータシステムをターゲットにし、共有メモリへの書き込み競合を引き起こさないスレッド生成、実行経路上の変数が保持する値を利用したスレッド生成、スレッドの実行制御命令生成およびスレッド内部の命令スケジューリングを備えたプログラム変換装置を提供することを目的とする。
【００１２】
尚、メモリはプログラム上では、変数として表現されるので、共有メモリも共有変数として表現される。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本発明のプログラム変換装置は、プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成部と、前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換部と、変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化部とを具備する。
【００１４】
かかる構成により、特定のプログラム部分を複数のスレッドで並列に実行することにより、特定のプログラム部分を短時間で実行することができる。
【００１５】
また、前記スレッド作成部は、前記プログラム部分の複数の実行経路のうち１つの実行経路を構成する命令を複写することにより、スレッドの本体となるスレッド本体ブロックを生成するスレッド本体ブロック生成部と、他のスレッドの実行を停止させる命令で構成される他スレッド停止ブロックを生成し、前記スレッド本体ブロックの後に配置する他スレッド停止ブロック生成部とを具備し、前記置換部は、前記スレッド本体ブロックの入口および出口で生きている変数である出入口生存変数を検出する出入口生存変数検出部と、前記出入口生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記出入口生存変数を新たに生成した変数に置換する出入口変数置換部と、前記出入口生存変数のうち入口で生きている変数が保持する値を、前記出入口変数置換部で置換した変数に代入する命令で構成される入口ブロックを生成し、前記スレッド本体ブロックの前に配置する入口ブロック生成部と、前記出入口変数置換部で置換した変数が保持する値を、前記出入口生存変数のうち出口で生きている変数へ代入する命令で構成される出口ブロックを生成し、前記他スレッド停止ブロックの後に配置する出口ブロック生成部と、前記出入口生存変数検出部で検出されない変数でかつ前記スレッド本体ブロック中に出現する変数であるスレッド内生存変数を検出するスレッド内生存変数検出部と、検出された前記スレッド内生存変数毎に新たな変数を生成し、前記スレッド本体ブロック中の前記スレッド内生存変数を新たに生成した変数に置換するスレッド内生存変数置換部とを具備してもよい。
【００１６】
かかる構成により、スレッド間で共有される変数の書き込みは、単一のスレッドとすることができる。即ち、スレッド本体ブロック内で書き込みが実施される変数は、新たに生成した変数に置換され、かつ、他のスレッドが停止された後に、スレッド間で共有される変数への書き込みが実施される。また、共有される変数への書き込みは、スレッドの出口で生きている変数のみに対して実施されるので、無駄な変数の書き込みは起こさないようにすることができる。
【００１７】
また、前記スレッド作成部は、さらに、前記スレッド本体ブロック中の条件分岐命令の分岐先の命令が、当該スレッド本体ブロックの実行経路に存在しない場合は、当該分岐先の命令として当該スレッドを停止させる自スレッド停止命令を生成し、当該スレッド本体ブロック内に配置する自スレッド停止命令生成部を具備してもよい。
【００１８】
かかる構成により、スレッドの実行自体が本来実行すべきでないスレッドであることが判明した時点で、スレッドを停止させることができ、プロセッサの使用権を他のスレッドに明け渡すことができる。
【００１９】
また、前記自スレッド停止命令生成部は、さらに、前記スレッド本体ブロック中の条件分岐命令の判定条件が不成立である場合の分岐先の命令が、当該スレッド本体ブロックの実行経路に存在しない場合は、当該条件分岐命令の判定条件を反転させ、反転した判定条件が成立した時の分岐先の命令として、自身のスレッドを停止させる自スレッド停止命令を生成し、当該スレッド本体ブロック内に配置してもよい。
【００２０】
かかる構成により、スレッドの条件分岐命令の判定条件が不成立である場合の分岐先の命令が、当該スレッドに存在しない場合に、当該スレッドを停止させることができ、プロセッサの使用権を他のスレッドに明け渡すことができる。
【００２１】
また、前記プログラム変換装置は、さらに、前記置換部によって変数を置換されたスレッド中の命令をより効率のよいものに最適化するスレッド内最適化部を具備し、前記スレッド並列化部は、前記スレッド内最適化部によって最適化されたスレッドを投機的に並列実行させるプログラムを生成してもよい。
【００２２】
かかる構成により、スレッドを最適化することで、スレッドを短時間で実行できる。
また、前記スレッド内最適化部は、前記置換部によって変数を置換されたスレッド中の前記入口ブロックの命令に対して、前記スレッド本体ブロック及び前記出口ブロック中へのコピー伝播及び不要コード最適化を実施する入口ブロック内命令コピー伝播最適化部を具備してもよい。
【００２３】
かかる構成により、スレッド間で共有される変数への書き込みを単一のスレッドが行うように変換した際に発生した、無駄な命令を削除できる。
【００２４】
また、前記スレッド内最適化部は、さらに、前記置換部によって変数を置換されたスレッド中の命令のデータの更新及び参照の実行順に基づいて、前記変数を置換されたスレッド中の命令の依存関係を算出する一般依存関係算出部と、前記出口ブロック中の命令に先立って前記他スレッド停止ブロック中の命令が実行されるような依存関係と、前記他スレッド停止ブロック中にある命令に先立って、前記自スレッド停止命令が実行されるような依存関係とを発生する特殊依存発生部と、前記一般依存関係算出部で算出された依存関係と、前記特殊依存発生部で算出された依存関係とに基づいて、スレッド内の命令を並列化する命令スケジューリング部とを具備してもよい。
【００２５】
かかる構成により、スレッド内部の命令をスレッドの入口から出口に向かって単純に実行するのではなく、実行の順番に依存が無い命令間では並列に実行することができるので、スレッドを短時間で実行できる。
【００２６】
また、前記経路情報は、経路上に存在する変数と、前記変数毎に予め定められた定数値とを含み、前記プログラム変換装置は、さらに、前記変数の値が、前記定数値と等しいか否かを判定する命令と、等しくない場合、当該スレッドを停止する命令とで構成される定数値判定ブロックを生成し、前記入口ブロックの前に配置する定数値判定ブロック生成部と、前記スレッド本体ブロック中の前記変数を、前記定数値に変換する定数値変換部とを具備し、前記スレッド並列化部は、変換後の複数のスレッドを投機的に並列実行させるプログラムを生成してもよい。
【００２７】
かかる構成により、特定のスレッドにおいて、スレッド内の変数が保持する値が一定である場合に、その値を活用した最適化をスレッドに適用できるので、スレッドを短時間で実行できる。
【００２８】
また、前記特殊依存発生部は、さらに、前記他スレッド停止ブロック中の命令に先立って、前記定数値判定ブロック中の命令が実行されるような特別な依存関係を発生してもよい。
【００２９】
かかる構成により、特定のスレッドにおいて、スレッド内の変数が保持する値が一定である場合に、その値を活用した最適化を施したスレッドに対しても、スレッド内部で実行の順番に依存が無い命令間では並列に実行することができるので、スレッドを短時間で実行できる。
【００３０】
また、前記複数のスレッドは、第１のスレッドと第２のスレッドとを含み、前記スレッド本体ブロック生成部は、前記第１及び第２のスレッドの包含関係を算出する経路包含関係算出部と、前記スレッドの包含関係から、前記第１のスレッドが前記第２のスレッドを包含する場合に、前記第１のスレッドから前記第２のスレッドと重複する経路を削除するスレッド本体ブロック経路簡略化部とを具備してもよい。
【００３１】
かかる構成により、スレッド内で、実行されることのない経路が削除されるので、スレッド自体の命令数が削減しスレッドのコードサイズが削減される。また、実行されることのない経路が削除により、新たな最適化の適用も可能となる機会が増えるので、スレッドを短時間でできる機会を増やすこともできる。
【００３２】
また、前記スレッド並列化部は、前記複数のスレッドに含まれる第１のスレッドと第２のスレッドとに対して、前記第１のスレッドと等価な経路が、前記第２のスレッドと等価な経路に含まれるか否かを判定し、含まれていると判定した場合、前記第１のスレッドが前記第２のスレッドに包含されているとみなして、スレッド間の包含関係を算出するスレッド間包含関係算出部と、前記経路情報から、経路の実行確率と、変数が保持する値の保持確率により、生成したスレッドの平均実行時間を算出するスレッド平均実行時間算出部と、前記第１のスレッドが前記第２のスレッドに包含されており、かつ、前記第２のスレッドの平均実行時間が、前記第１のスレッドの平均実行時間より短い時に、前記第１のスレッドを削除する確率情報スレッド削除部とを具備してもよい。
【００３３】
かかる構成により、スレッドの平均実行時間を用いて、実行しても無駄なスレッドを削除することができ、コードサイズの増加を抑えるとともに、無駄なスレッドをプロセッサに実行させないので、他のスレッドがプロセッサを使用できる機会を増加させることができる。
【００３４】
また、前記プログラムは、経路を識別する情報である経路識別情報を含み、前記プログラム変換装置は、さらに、前記経路識別情報を解析して前記経路情報を抽出する経路解析部を具備してもよい。
【００３５】
かかる構成により、プログラム変換装置の利用者が経路識別情報を直接ソースプログラムに記載し、スレッド化したいプログラム部分を特定できるので、利用者によるプログラムの効率化が短期に実施できる。
【００３６】
また、前記プログラムは、経路上に存在する変数が保持する値を示す変数保持値情報を含み、前記経路解析部は、前記経路識別情報と、前記変数保持値情報とを解析して、変数が保持する値を特定する変数保持値解析手段を具備してもよい。
【００３７】
かかる構成により、プログラム変換装置の利用者が、経路上の存在する変数が保持する値を直接ソースプログラムに記載し、スレッドをさらに短時間実行化できるので、利用者によるプログラムの効率化が短期に実施できる。
【００３８】
また、前記プログラムは、経路を識別する情報である経路識別情報と、経路の実行確率情報と、経路上に存在する変数が保持する値を示す変数保持値情報と、変数が保持する値の保持確率情報とを含み、前記プログラム変換装置は、さらに、前記経路識別情報と、前記実行確率情報と、前記変数保持値情報と、前記保持確率情報とに従って、前記実行確率及び前記保持確率を特定する確率特定手段を具備してもよい。
【００３９】
かかる構成により、プログラム変換装置の利用者が、経路の実行確率情報、経路上に存在する変数が保持する値の保持確率情報を直接ソースプログラムに記載し、スレッドの平均実行時間に基づいて、無駄なスレッド生成を抑制し、効率よくスレッドを生成することができるので利用者によるプログラムの効率化が短期に実施できる。
【００４０】
なお、本発明はこのようなプログラム変換装置として実現することができるだけでなく、プログラム変換装置に含まれる処理部をステップとするプログラム変換方法として実現したり、そのような特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ等の記録媒体及びインターネット等の伝送媒体を介して流通させることができるのは言うまでもない。
【発明の効果】
【００４１】
本発明によるプログラム変換装置によれば、特定のプログラム部分を、投機的に複数のスレッドで並列に実行するプログラムに変換するので、特定のプログラム部分を短時間実行することができる。
【発明を実施するための最良の形態】
【００４２】
以下、プログラム変換装置等の実施の形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
【００４３】
＜用語の説明＞
具体的な、本実施の形態を述べる前に、用語について定義する。
【００４４】
・文
一般的なプログラム言語上の文のことである。文には代入文、分岐文、繰り返し文などが存在する。また、本実施の形態では、断りがないかぎり、文と命令を区別せず同義に扱う。
【００４５】
・経路
複数の文の集合であり、かつ、文の間には実行順序が規定されているものである。但し、経路を構成する文のいくつかには実行順序が規定されていなくてもよい。例えば、図４において、矢印「→」で実行順序を表す場合、
Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１２→Ｓ１３→Ｓ１４→Ｓ１５は、一つの経路でもあるし、
Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１２→Ｓ１３→Ｓ１４→Ｓ１５と、
Ｓ１→Ｓ２→Ｓ３→Ｓ６→Ｓ７→Ｓ８→Ｓ９→Ｓ１２→Ｓ１３→Ｓ１４→Ｓ１５とを合わせたものも一つの経路である。但し、この場合、Ｓ４とＳ６，Ｓ７および、Ｓ５とＳ６，Ｓ７の間には実行順序は規定されない。
【００４６】
・スレッド
スレッドとは、コンピュータによる処理に適した、順番付けられた命令の集まりである。
【００４７】
＜実施の形態＞
本発明の実施の形態におけるプログラム変換装置は、コンピュータシステム２００上で実行される。図１はコンピュータシステムの例である。記憶部２０１は、ハードディスク等の大容量記憶装置であり、プロセッサ２０４は制御装置と演算装置からなり、メモリ２０５はＭＯＳ−ＩＣなどの記憶素子により構成される。
【００４８】
本発明の実施の形態におけるプログラム変換装置は、記憶部２０１中にプログラム変換プログラム２０２として実現されており、プログラム変換プログラム２０２は、プロセッサ２０４によりメモリ２０５に格納され、プロセッサ２０４よって実行される。プロセッサ２０４は、プログラム変換プログラム２０２の指令に従って、後述するコンパイラシステムにより、記憶部２０１に格納されているソースプログラム２０３を目的プログラム２０７に変換し、記憶部２０１に格納する。
【００４９】
図２は、プロセッサ２０４が備えるコンパイラシステムの構成を示すブロック図である。このコンパイラシステム２１０は、Ｃ言語やＣ＋＋言語等の高級言語で記述されたソースプログラム２０３を機械語プログラムである目的プログラム２０７に変換するコンパイラシステムであり、大きく分けてコンパイラ２１１と、アセンブラ２１２と、リンカ２１３とから構成される。
【００５０】
コンパイラ２１１は、ソースプログラム２０３をプログラム変換プログラム２０２によってコンパイルし、機械語命令に置き換えることで、アセンブラプログラム２１５を生成する。
【００５１】
アセンブラ２１２は、コンパイラ２１１から出力されたアセンブラプログラム２１５に対して、内部に保持する変換テーブル等を参照することで、全てのコードをバイナリの機械語コードに置き換えることで、再配置可能バイナリプログラム２１６を生成する。
【００５２】
リンカ２１３は、アセンブラ２１２から出力された複数の再配置可能バイナリプログラム２１６に対して、未解決なデータのアドレス配置等を決定して連結することにより、目的プログラム２０７を生成する。
【００５３】
次に、上述したプログラム変換プログラム２０２として実現されているプログラム変換装置について詳しく説明する。本実施の形態におけるプログラム変換装置は、プログラム中のプログラム部分の実行経路に関する経路情報から、前記プログラム部分と等価な複数のスレッドであって、かつ、それぞれのスレッドが前記プログラム部分の複数の実行経路のうち少なくとも１つの実行経路と等価なスレッドを作成するスレッド作成部と、前記複数のスレッド間で変数の書き込み競合を引き起こさないように、前記複数のスレッド間で共有される変数の値の書き込みを単一のスレッドのみが実行するように、前記複数のスレッドの変数を置換する置換部と、変数の置換後に複数のスレッドを投機的に並列実行させるプログラムを生成するスレッド並列化部とを具備する。
【００５４】
図３は、本実施の形態におけるプログラム変換装置の構成を階層的に示した図である。
プログラム変換装置１は、経路解析部１２４、スレッド生成部１０１、スレッド並列化部１０２を具備する。具体的には、スレッド生成部１０１は、スレッド本体ブロック生成部１０３、自スレッド停止命令生成部１１１、他スレッド停止ブロック生成部１０４、出入口生存変数検出部１０５、出入口変数置換部１０６、入口ブロック生成部１０７、出口ブロック生成部１０８、スレッド内生存変数検出部１０９、スレッド内生存変数置換部１１０、入口ブロック内命令コピー伝播最適化部１１２、一般依存関係算出部１１３、特殊依存発生部１１４および命令スケジューリング部１１５を具備する。
【００５５】
ここで、スレッド本体ブロック生成部１０３と、自スレッド停止命令生成部１１１と、他スレッド停止ブロック生成部１０４とから、スレッド作成部１３０が構成される。また、出入口生存変数検出部１０５と、出入口変数置換部１０６と、入口ブロック生成部１０７と、出口ブロック生成部１０８と、スレッド内生存変数検出部１０９と、スレッド内生存変数置換部１１０とから、置換部１４０が構成される。また、入口ブロック内命令コピー伝播最適化部１１２と、一般依存関係算出部１１３と、特殊依存発生部１１４と、命令スケジューリング部１１５とから、スレッド内最適化部１５０が構成される。
【００５６】
また、図３は、プログラム変換装置１の動作順も示しており、上から順番に各部を起動する。つまり、プログラム変換装置１は、経路解析部１２４、スレッド生成部１０１、スレッド並列化部１０２の順番に起動し、かつ、スレッド生成部１０１は、スレッド本体ブロック生成部１０３、自スレッド停止命令生成部１１１、他スレッド停止ブロック生成部１０４、出入口生存変数検出部１０５、出入口変数置換部１０６、入口ブロック生成部１０７、出口ブロック生成部１０８、スレッド内生存変数検出部１０９、スレッド内生存変数置換部１１０、入口ブロック内命令コピー伝播最適化部１１２、一般依存関係算出部１１３、特殊依存発生部１１４、命令スケジューリング部１１５の順番に各部を起動する。
【００５７】
以下、起動順に、各部の説明をするとともに、図４から図１９の例を使用して具体的な動作を説明する。
【００５８】
経路解析部１２４は、プログラマによってソースプログラム上に記載された、経路を識別する情報である経路識別情報を解析して経路情報を抽出する。
【００５９】
図４は、Ｃ言語プログラムの記法に従って記述したソースプログラムの例であり、図５は、プログラマにより経路識別情報を記述追加されたソースプログラムの例である。図５中「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ」は、各種の経路情報を表すものである。図５において「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｘ）」は経路の最初を示し、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＥＮＤ（Ｘ）」は経路の最後を示す。また、Ｘは経路を識別する経路名である。「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＰＩＤ（Ｘ）」は、経路の途中を示すものであり、Ｘは経路を識別する経路名である。これらの３種類の経路情報をプログラムに示された実行順に辿ることによって、経路は特定される。つまり、図５において経路Ｘは、
Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１０→Ｓ１１→Ｓ１５と特定される。
【００６０】
また、図５においてＳ９の直後の「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＰＩＤ（Ｘ）」が存在しない場合、経路Ｘは、
Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１０→Ｓ１１→Ｓ１５と、
Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１２→Ｓ１３→Ｓ１４→Ｓ１５とを合わせたものと特定される。
【００６１】
スレッド生成部１０１は、特定のプログラム部分に関する経路情報から、スレッド間でメモリやレジスタなどの記憶領域への書き込み競合を引き起こさないように、複数のスレッドを生成する。具体的には図３に示す通り、スレッド生成部１０１は、スレッド本体ブロック生成部１０３、自スレッド停止命令生成部１１１、他スレッド停止ブロック生成部１０４、出入口生存変数検出部１０５、出入口変数置換部１０６、入口ブロック生成部１０７、出口ブロック生成部１０８、スレッド内生存変数検出部１０９、スレッド内生存変数置換部１１０、入口ブロック内命令コピー伝播最適化部１１２、一般依存関係算出部１１３、特殊依存発生部１１４および命令スケジューリング部１１５を具備する。
【００６２】
スレッド本体ブロック生成部１０３は、経路情報から、経路を複写することにより生成されるスレッド本体ブロックを生成する。
【００６３】
図６は、図５の経路Ｘを複写して生成したスレッド本体ブロックを含むプログラムを示す。本実施の形態では、図６に示すように「＃ｐｒａｇｍａ  Ｔｈｒｅａｄ  ｔｈｒ＿Ｘ」および、これに続く中括弧「｛｝」によりスレッドを定義する。「ｔｈｒ＿Ｘ」はスレッドを識別するスレッド名であり、以下の説明では、「スレッドｔｈｒ＿Ｘ」のように、スレッドをスレッド名で識別する。また、スレッド本体ブロックは図６に示すように、さらに中括弧「｛／／  スレッド本体ブロック．．．．｝」で囲んでその範囲を明示する。以上をまとめると、スレッド本体ブロック生成部１０３は、図５の経路ＸであるＳ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ８→Ｓ９→Ｓ１０→Ｓ１１→Ｓ１５を複写し、スレッドｔｈｒ＿Ｘのスレッド本体ブロックを生成している。特に、図５の条件分岐命令Ｓ３および条件分岐命令Ｓ９の条件が不成立である場合の実行経路の「ｅｌｓｅ側」は複写されない。
【００６４】
自スレッド停止命令生成部１１１は、スレッド本体ブロック中の条件分岐命令の判定条件が成立した場合の分岐先が、スレッド本体ブロック中に複写されていない場合は、判定条件が成立した時に自身のスレッドを停止させる自スレッド停止命令を生成し、スレッド本体ブロック中の条件分岐命令の判定条件が不成立である場合の分岐先が、スレッド本体ブロック中に複写されていない場合は、判定条件を反転させ、反転した判定条件が成立した時に自身のスレッドを停止させる自スレッド停止命令を生成する。
【００６５】
図７は、図６のスレッドｔｈｒ＿Ｘに対して自スレッド停止命令生成部１１１を適用した結果である。図５のソースプログラムから判断されるように、条件分岐命令Ｓ３が不成立である場合の分岐先である文Ｓ６を複写した文がスレッドｔｈｒ＿Ｘのスレッド本体ブロック中に存在しない。よって、自スレッド停止命令生成部１１１は、Ｓ３＿１１のように判定条件を反転させ、反転した判定条件が成立した場合に、自身のスレッドを停止させる「Ｓｔｏｐ  ｔｈｒ＿Ｘ」命令を生成する。Ｓ９＿１１も同様である。
【００６６】
他スレッド停止ブロック生成部１０４は、他のスレッドの実行を停止させる命令で構成される他スレッド停止ブロックを生成し、スレッド本体ブロックの後に配置する。
【００６７】
図８は、図７のスレッドｔｈｒ＿Ｘに対して他スレッド停止ブロック生成部１０４を適用した結果である。スレッド本体ブロックの後に、他スレッド停止ブロックが生成されている。図中の、「Ｓｔｏｐ  ＯＴＨＥＲ＿ＴＨＲＥＡＤ」は、スレッドｔｈｒ＿Ｘと並列実行される他のスレッドを停止させることを示している。ＯＴＨＥＲ＿ＴＨＲＥＡＤは並列実行される他のスレッドの識別名が明確になり次第、具体的なスレッドの識別名が記述される。これについては後述する。
【００６８】
出入口生存変数検出部１０５は、スレッド本体ブロックの入口および出口で生きている変数である出入口生存変数を検出する。
【００６９】
生きている変数の定義と、その算出方法に関しては、文献１で示されているものと同様であり、本発明の主眼でないので省略する。なお、スレッド本体ブロックの入口で生きているとは、スレッド本体ブロック中において、参照の前に値の更新がない変数のことである。また、スレッド本体ブロックの出口で生きているとは、スレッド本体ブロックが実行された後に値が参照される変数のことである。つまり、経路識別情報が記載されたソースプログラムにおいて経路の最後を示す「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＥＮＤ（．．）」が指定された場所以降において値が参照される変数のことである。要するに、図５の文Ｓ１５より後において値が参照される変数のことである。図８のスレッド本体ブロックに対して出入口生存変数検出部１０５を適用すると、入口生存変数は、変数ｂ、変数ｃ、変数ｅ、変数ｇおよび変数ｙであり、出口生存変数は、変数ａ、変数ｃ、変数ｈおよび変数ｘとなる。
【００７０】
（文献１）  Ａ．Ｖ．Ａｈｏ、  Ｒ．Ｓｅｔｈｉ、  Ｊ．Ｄ．Ｕｌｌｍａｎ著「Ｃｏｍｐｉｌｅｒｓ、  Ｐｒｉｎｃｉｐｌｅ、  Ｔｅｃｈｎｉｑｕｅｓ、  ａｎｄ  Ｔｏｏｌ」、Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ  Ｉｎｃ．、１９８６、ｐ．６３１−ｐ．６３２
【００７１】
次に、出入口変数置換部１０６は、出入口生存変数毎に新たな変数を生成し、スレッド本体ブロック中の出入口生存変数の出現箇所を、新たに生成した変数に置換し、入口ブロック生成部１０７及び出口ブロック生成部１０８は、出入口生存変数と新たに生成された変数との間で変数が保持する値の交換を行う命令を生成する。
【００７２】
図９は、図８のスレッド本体ブロックに対して出入口変数置換部１０６、入口ブロック生成部１０７、および出口ブロック生成部１０８を適用した結果である。
【００７３】
例えば、図８のスレッド本体ブロック中の入口生存変数である変数ｂの出現箇所は、図９のスレッド本体ブロックでは、新たに生成した変数ｂ２に置換されている。その他の入口生存変数である変数ｃ、変数ｅ、変数ｇ、変数ｙについても同様である。また、図８のスレッド本体ブロック中の出口生存変数である変数ａの出現箇所は、図９のスレッド本体ブロックでは、新たに生成した変数ａ２に置換されている。その他の出口生存変数である変数ｃ、変数ｈ、変数ｘについても同様である。尚、変数ｃは入口生存変数でもあるので、既に新しい変数ｃ２に置換されており、出口生存変数の置換の際には省略される。
【００７４】
入口ブロック生成部１０７は、出入口生存変数のうち入口で生きている変数が保持する値を、出入口変数置換部１０６で置換された変数に代入する命令の集まりである入口ブロックを生成し、スレッド本体ブロックの前に配置する。
【００７５】
出口ブロック生成部１０８は、出入口変数置換部１０６で置換された変数が保持する値を、出入口生存変数のうち出口で生きている変数へ代入する命令の集まりである出口ブロックを生成し、他スレッド停止ブロックの後に配置する。
【００７６】
図９の入口ブロックおよび出口ブロックは、図９のスレッド本体ブロックおよび他スレッド停止ブロックに対して、入口ブロック生成部１０７および出口ブロック生成部１０８を適用した結果である。
【００７７】
例えば、図９の入口ブロックでは、図８のスレッド本体ブロックの入口で生きている変数ｂから、出入口変数置換部１０６で置換した変数ｂ２に変数ｂが保持する値を代入する命令である文Ｓ２０１が生成されている。他の入口生存変数、変数ｃ、変数ｅ、変数ｇ、変数ｙについても同様である。
【００７８】
また、図９の出口ブロックでは、図８のスレッド本体ブロックの出口で生きている変数ａへ、出入口変数置換部１０６で置換された変数ａ２が保持する値を代入する命令である文Ｓ２０６が生成されている。他の出口生存変数である変数ｃ、変数ｈ、変数ｘについても同様である。
【００７９】
次に、出入口生存変数検出部１０５で検出されない変数でかつスレッド本体ブロックに出現する変数を検出し、置換する。
【００８０】
図１０は、図９のスレッド本体ブロックにスレッド内生存変数検出部１０９およびスレッド内生存変数置換部１１０を適用した結果である。
【００８１】
スレッド内生存変数検出部１０９は、出入口生存変数検出部１０５で検出されない変数でかつスレッド本体ブロックに出現する変数であるスレッド内生存変数を検出する。図９の例では、出入口生存変数検出部１０５で検出されていない変数ｄおよび変数ｆが検出される。
【００８２】
スレッド内生存変数置換部１１０は、検出されたスレッド内生存変数毎に新たな変数を生成し、スレッド本体ブロック中のスレッド内生存変数の出現箇所を、新たに生成した変数に置換する。図９のスレッド本体ブロックにおいて、変数ｄは図１０のように新たに生成した変数ｄ２に置換される。変数ｆについても同様に変数ｆ２に置換される。
【００８３】
ここで、他スレッド停止ブロック生成部１０４までの変換を実施した後のスレッドｔｈｒ＿Ｘである図８と、スレッド内生存変数置換部１１０までを実施した後のスレッドｔｈｒ＿Ｘを示す図１０を比較する。まず、図８と図１０の入口生存変数、出口生存変数は同じであり、かつ、スレッド本体ブロック内では格納する変数に違いはあるものの計算過程は全く同一である。よって、図８と図１０のスレッドｔｈｒ＿Ｘは等価である。
【００８４】
引き続き、各処理部について説明する。
入口ブロック内命令コピー伝播最適化部１１２は、入口ブロック中にある命令文に対して、スレッド本体ブロックおよび出口ブロック中へのコピー伝播および不要コード最適化を実施する。
【００８５】
図１１は、図１０のスレッドに対してコピー伝播および不要コード最適化を実施した結果である。
【００８６】
コピー伝播最適化と不要コード最適化自体の方法に関しては、文献２で示されているものと同様であり、本発明の主眼でないので省略する。ここでは、図１０と図１１を用いて具体的に説明する。
【００８７】
（文献２）  Ａ．Ｖ．Ａｈｏ、  Ｒ．Ｓｅｔｈｉ、  Ｊ．Ｄ．Ｕｌｌｍａｎ著「Ｃｏｍｐｉｌｅｒｓ、  Ｐｒｉｎｃｉｐｌｅ、  Ｔｅｃｈｎｉｑｕｅｓ、  ａｎｄ  Ｔｏｏｌ」、Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ  Ｉｎｃ．、１９８６、ｐ．５９４−ｐ．５９５およびｐ．６３６−ｐ．６３８
【００８８】
図１０の文Ｓ２０１で設定された変数ｂ２の値の参照先文Ｓ１＿１、文Ｓ１０＿１中において、変数ｂ２が保持する値と等しい値を保持する変数ｂに置換することでコピー伝播を実施し、それぞれ、ａ２＝ｂ＋ｃ１、ａ２＝ｂ／ｆ２となる。更に、文Ｓ２０１で設定されたｂ２の値を参照する文は、スレッド本体ブロック、および出口ブロックには存在しないので、不要コードとして削除される。
【００８９】
その他の、入口ブロック中に存在する文Ｓ２０２、文Ｓ２０３、文Ｓ２０４および文Ｓ２０５についても文Ｓ２０１と同様に変数が置換され削除される。
【００９０】
ここまで説明した、出入口生存変数検出部１０５から入口ブロック内命令コピー伝播最適化部１１２までの変換の意図は、自身のスレッドと並列実行する他のスレッドとの間で、メモリやレジスタなどの記憶領域の書き込み競合を起こさないようにするためである。例えば、出入口生存変数検出部１０５を適用する前の図８のままで実行し、かつ他のスレッドが変数ａの値を参照している場合、文Ｓ１＿１の変数ａが保持する値の更新が、他のスレッドに予期せぬ動作をさせてしまうことになる。よって、ソースプログラムである図５の実行結果と異なる結果を算出してしまい、等価なプログラムにならないという問題が生じる。
【００９１】
図８と図１１とを比較すると、図８で保持する値が更新される変数が、図１１では新たに生成した変数に置換されていることが解る。これにより、図１１のスレッド本体ブロックまでの実行が他のスレッドの実行に影響を与えることはない。さらに、他スレッド停止ブロックを実行して、他のスレッドを停止した後に出口ブロックが実行されるので、出口ブロック中の各文における、他のスレッドと共有される変数が保持する値の更新は安全に実行される。ここで、共有される変数とは、複数のスレッド中で同一の変数として扱われる変数のことである。
【００９２】
次に、スレッド毎の処理速度を向上させるために、スレッド中の命令レベルの並列化を行う。
【００９３】
一般依存関係算出部１１３は、スレッド中の命令間にデータの更新と参照とに基づいた一般的な実行順の依存関係を算出する。一般依存関係算出部１１３は、文献３で示されているものと同様であり、本発明の主眼でないので省略する。
【００９４】
（文献３）中田育男著「コンパイラの構成と最適化」朝倉書店、１９９９年９月２０日、ｐ．４１２−ｐ．４１４
【００９５】
図１２は、図１１に対して一般依存関係算出部１１３を適用した結果である。図１２は文間の依存関係を示す依存グラフである。図中、矢印の先から矢印の元へ依存が発生している。つまり、図中例えば、文Ｓ２＿１→文Ｓ４＿１は、文Ｓ４＿１が文Ｓ２＿１に依存しており、文Ｓ２＿１を実行した後でないと文Ｓ４＿１は実行できないことを示す。
【００９６】
特殊依存発生部１１４は、出口ブロック中の命令に先立って他スレッド停止ブロック中にある命令が実行されるような特別な依存関係を発生し、さらに、他スレッド停止ブロック中にある命令に先立って、自スレッド停止命令が実行されるような特別な依存関係を発生する。
【００９７】
図１３は、図１１に対して特殊依存発生部１１４を適用した結果であり、図１２の依存グラフに、特殊依存発生部１１４の結果、発生した依存を太い矢印で追加している。ここで発生した依存により、他のスレッドを停止するタイミングおよび出口ブロック中の命令の実行順番を正しく指定することが可能となる。
【００９８】
命令スケジューリング部１１５は、一般依存関係算出部１１３で算出された依存関係と、特殊依存発生部１１４で発生された依存関係とに基づいて、スレッド内の命令を並列化する。命令スケジューリング部１１５は、文献４で示されているものと同様であり、本発明の主眼でないので省略する。
【００９９】
（文献４）中田育男著「コンパイラの構成と最適化」朝倉書店、１９９９年９月２０日、ｐ．３５８−ｐ．３８２
【０１００】
図１４は、図１３の依存関係に基づき、図１１のスレッド中の命令をスケジューリングし並列化した結果である。ここで、２命令が並列に実行可能であると仮定している。図中、「＃」は、並列に実行できる命令の区切りであり、例えば、文Ｓ１＿１と、文Ｓ５＿１は並列に実行できることを示している。
【０１０１】
これまで、図５に示したプログラムのうち、経路Ｘに関するスレッド生成について説明した。ところで図１４のスレッドｔｈｒ＿Ｘのみを実行しただけでは、ソースプログラムである図５と等価な実行とはならないことは自明である。なぜなら、図５において経路Ｘは文Ｓ１から文１５に至る経路の一つと等価な実行を行うだけであるからである。よって、ソースプログラムである図５の文Ｓ１から文Ｓ１５のプログラム部分をそのままスレッド化したスレッドｔｈｒ＿Ｏｒを生成し、図１４のスレッドｔｈｒ＿Ｘと並列実行するようにすれば、スレッドｔｈｒ＿Ｘが停止しても、スレッドｔｈｒ＿Ｏｒは停止させないことにより、必ず、図５の文Ｓ１から文Ｓ１５の部分と等価な実行となることが保証される。以下、まずスレッドｔｈｒ＿Ｏｒの生成について説明した後、スレッドｔｈｒ＿Ｏｒとスレッドｔｈｒ＿Ｘとの並列実行について説明する。
【０１０２】
図１５は、図５のソースプログラムをスレッド化したスレッド本体ブロックおよび他スレッド停止ブロックの例である。
【０１０３】
スレッドｔｈｒ＿Ｏｒは、スレッドｔｈｒ＿Ｘと同様に生成される。スレッド本体ブロック生成部１０３は、図１５に示すように、図５の文Ｓ１から文１５に至る全経路を複写することにより、スレッドｔｈｒ＿Ｏｒのスレッド本体ブロックを生成する。
【０１０４】
次に、自スレッド停止命令生成部１１１は、図１５のスレッド本体ブロック中の条件分岐命令毎に分岐先に着目して処理をすすめるが、文Ｓ３の条件分岐命令において、判定条件が成立した場合も不成立な場合もともに分岐先は、スレッド本体ブロック中に存在するので、自身を停止させる自スレッド停止命令は生成されない。文Ｓ９の条件分岐命令も同様の理由により、自身を停止させる自スレッド停止命令は生成されない。
【０１０５】
次に、他スレッド停止ブロック生成部１０４は、図１５に示すとおり他スレッド停止ブロックを生成し、スレッド本体ブロックの後に配置する。
【０１０６】
次に、スレッドｔｈｒ＿Ｘの場合と同じように、出入口生存変数の検出および置換が行われる。図１６は、図１５のスレッドに対して、出入口生存変数検出部１０５、出入口変数置換部１０６、入口ブロック生成部１０７、および出口ブロック生成部１０８を適用した結果である。
【０１０７】
出入口生存変数検出部１０５が起動し、入口生存変数として、変数ｂ、変数ｃ、変数ｄ、変数ｅ、変数ｇおよび変数ｙが検出され、出口生存変数として、変数ａ、変数ｃ、変数ｈおよび変数ｘが検出される。
【０１０８】
次に、出入口変数置換部１０６、入口ブロック生成部１０７および出口ブロック生成部１０８が起動し、図１５は、図１６のように変換される。
【０１０９】
次に、スレッドｔｈｒ＿Ｘの場合と同じように、スレッド内生存変数検出部１０９が起動し、出入口生存変数検出されていない変数ｆが検出される。
【０１１０】
次に、スレッド内生存変数置換部１１０が起動し、図１６は、図１７のように変換される。
【０１１１】
次に、スレッドｔｈｒ＿Ｘの場合と同じように、入口ブロック内命令コピー伝播最適化部１１２が起動し、図１７の入口ブロックの各文がコピー伝播および不要コード最適化が実施され、図１７は、図１８のように変換される。
【０１１２】
以上により、スレッドｔｈｒ＿Ｏｒの生成は終了する。なお、スレッドｔｈｒ＿Ｏｒの入口ブロック、スレッド本体ブロック、出口ブロック内の文に対して、一般的な命令の依存関係を算出して、命令スケジューリングを実施しても構わない。
【０１１３】
次に、これまで生成されたスレッドｔｈｒ＿Ｏｒとスレッドｔｈｒ＿Ｘとを並列動作させるための処理を説明する。
【０１１４】
スレッド並列化部１０２は、スレッド生成部１０１で生成された複数のスレッドを並列動作させるようにスレッドを配置し、特定のプログラム部分と等価でかつ、高速化されたプログラムを生成する。また、ここで、他スレッド停止ブロック中において具体的に停止されるスレッドが決定される。
【０１１５】
図１９は、図１４のスレッドｔｈｒ＿Ｘと、図１８のスレッドｔｈｒ＿Ｏｒに対して、スレッド並列化部１０２を適用した結果である。
【０１１６】
図１９において、「＃ｐｒａｇｍａ  ＰａｒａＴｈｒｅａｄＥｘｅ  ｛．．｝」は、中括弧中に存在するスレッドを並列に実行することを示す。図１９では、「＃ｐｒａｇｍａ  ＰａｒａＴｈｒｅａｄＥｘｅ  ｛．．｝」の中括弧の中に、二つのスレッド、すなわちスレッドｔｈｒ＿Ｏｒとスレッドｔｈｒ＿Ｘとが配置されており、スレッドｔｈｒ＿Ｏｒとスレッドｔｈｒ＿Ｘが並列実行されること示す。さらに、図１８中の文Ｓ１００の「Ｓｔｏｐ  ＯＴＨＥＲ＿ＴＨＲＥＡＤ」のＯＴＨＥＲ＿ＴＨＥＡＤは、スレッドｔｈｒ＿Ｘに決定され、図１９中の文Ｓ１００のように設定される。図１４のスレッドｔｈｒ＿Ｘ中の文Ｓ２００の場合も同様であり、文Ｓ２００の「Ｓｔｏｐ  ＯＴＨＥＲ＿ＴＨＲＥＡＤ」のＯＴＨＥＲ＿ＴＨＥＡＤはスレッドｔｈｒ＿Ｏｒに決定され、図１９中の文Ｓ２００のように設定される。
【０１１７】
以上のように、本実施の形態のプログラム変換装置１は、共有メモリへの書き込み競合を引き起こさないスレッド生成、スレッドの実行制御命令生成およびスレッド内部の命令スケジューリングを行うことができる。
【０１１８】
よって、本実施の形態のプログラム変換装置１は、経路Ｘが実行される場合、変換前の経路Ｘの実行が１０ステップ要するのに対して、スレッドｔｈｒ＿Ｘの実行は８ステップで実行可能となる。さらに、経路Ｘが実行されない場合は、スレッドｔｈｒ＿Ｏｒが実行されるので、変換前と等価な実行となる。しかし、スレッドｔｈｒ＿Ｏｒは変換前と比較して、入口ブロック、他スレッド停止ブロック、出口ブロックが増加しておりステップ数は増加している。しかし、経路Ｘの実行頻度が相当に高いとき、図１９のようにスレッド化した方が平均実行時間が短くなるので有利である。
【０１１９】
尚、図１４の文Ｓ１０＿１は、文Ｓ９１＿１１より先行されて実行されている。ここで、変数ｆ２が保持する値がゼロである場合、文ＳＳ１０＿１において、ゼロ割算による実行時例外が発生する。このように実行時に例外発生する場合は、プロセッサおよびオペレーションシステムが実行時に例外を感知した際にスレッドを自動的に停止させてもよい。
【０１２０】
または、文献５で公開されている方法と同様に、特殊依存発生部１１４において、実行時に例外発生する文（図１４では文Ｓ１０＿１）が、例外発生を避けるための判定文（図１４では文Ｓ９１＿１１）より先行して実行されないように依存を生成してもよい。
【０１２１】
つまり、特殊依存発生部１１４において、例外発生を避けるための判定文から、実行時に例外発生する文へ依存を生成する。図１２の依存グラフにおいては、文Ｓ９１＿１１→文Ｓ１０＿１の依存を生成する。
【０１２２】
（文献５）特開２００８−４０８２号公報
【０１２３】
＜変形例１＞
上述した実施の形態では、経路情報として経路のみを使用していたが、経路上に存在する変数と、当該変数毎に予め定められた定数値とを含む変数保持値情報を使用するよう拡張してもよい。
【０１２４】
図２０は、本変形例のプログラム変換装置の構成を階層的に示した図である。本変形例のプログラム変換装置１は、実施の形態のプログラム変換装置１と比較して、さらに、定数値判定ブロック生成部１１６、定数値変換部１１７および冗長性削除最適化部１１８を備える点が異なる。
【０１２５】
図２１は、プログラマにより経路情報に変数が保持する値の情報を記述追加されたソースプログラムの例である。図中、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｘ）、  ＶＡＬ（ｂ：５）、  ＶＡＬ（ｅ：８）」は、経路Ｘの中で、変数ｂおよび変数ｅがそれぞれ値５、値８を保持することを示す。
【０１２６】
経路解析部１２４は、実施の形態と比較して、新たに、変数保持値解析手段を備える。変数保持値解析手段は、変数保持値情報から変数が保持する値を特定する。具体的には、図２１の例において、経路解析部１２４は、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｘ）、  ＶＡＬ（ｂ：５）、  ＶＡＬ（ｅ：８）」を解析し、経路Ｘ中で、変数ｂおよび変数ｅがそれぞれ値５、値８を保持することを特定する。
【０１２７】
スレッド本体ブロック生成部１０３から入口ブロック内命令コピー伝播最適化部１１２までの動作は、実施の形態と同じである。結果として、経路Ｘに対しては、図１１と同じ結果が得られる。ここでは、図１１の変換結果と、混同を避けるために、図２２に示すように、図１１を複写し、スレッド名をｔｈｒ＿Ｘ＿ＶＰ、スレッド内で使用する変数名も変更している。次に、図２２を用いて変換過程について述べる。
【０１２８】
定数値判定ブロック生成部１１６は、変数保持値情報に含まれる変数毎に、予め定められた定数値と、経路上に存在する変数とが等しいか否かを判定する命令と、等しくないと判定した場合、自スレッドを停止する命令とで構成される定数値判定ブロックを生成し、入口ブロックの前に配置する。
【０１２９】
定数値変換部１１７は、変数保持値情報に含まれる変数毎に、スレッド本体ブロック中の当該変数の参照箇所を、予め定められた定数値に置換する。
【０１３０】
図２３は、図２２に対して、定数値判定ブロック生成部１１６および定数値変換部１１７を適用した結果である。図中の定数値判定ブロックに示されているように、変数ｂが保持する値が５でない時、または、変数ｅが保持する値が８でない時に、スレッドｔｈｒ＿Ｘ＿ＶＰを停止する命令が生成される。また、スレッド本体ブロック中の変数ｂおよび変数ｅの参照箇所が、それぞれ定数値５および定数値８で置き換えられている。
【０１３１】
冗長性削除最適化部１１８は、入口ブロック、スレッド本体ブロックおよび出口ブロックに対して一般的な定数伝播・畳み込み最適化を行う。さらに、定数伝播・畳み込み最適化後に、不要命令の削除や、条件分岐命令の判定条件が恒真または恒偽である場合に不要な分岐を削除する。特に、条件分岐命令の判定が成立したときに自スレッド停止命令を実行する場合で、かつ、判定条件は恒真である場合は、常に自スレッド停止命令が実行されることになるので、変数が保持する値の情報を使用したスレッド生成自体を取りやめる。
【０１３２】
尚、一般的な定数伝播最適化は、文献２で示されているものと同様であり、本発明の主眼でないので省略する。
【０１３３】
図２４は、図２３に対して、冗長性削除最適化部１１８のうち、定数伝播・畳み込みを適用した結果である。図中、文Ｓ５＿２は定数畳み込みが行われて「ｄ３＝９」となり、文Ｓ８＿２は文Ｓ５＿２の定数伝播と定数畳み込みとが行われて、「ｆ３＝１２」となっている。また、文Ｓ９１＿２１は、文Ｓ８＿２の定数伝播が行われて判定条件が、「１２＜＝０」となっている。その他の変化に関しても同様である。
【０１３４】
図２５は、図２４に対して、冗長性削除最適化部１１８のうち残りの最適化を実施した結果である。図２４中の文Ｓ５＿２は変数ｄ３の参照箇所が存在しないので、不要命令の削除の処理で削除される。図２４中の文Ｓ８＿２、文Ｓ１０＿２も同様な理由で削除される。図２４中の文Ｓ９１＿２１の判定条件は恒偽となるので削除される。
【０１３５】
次に、一般依存関係算出部１１３、特殊依存発生部１１４および命令スケジューリング部１１５が順に起動される。特に、特殊依存発生部１１４では、定数値判定ブロック生成部１１６で生成された定数値判定ブロック中の命令が、他スレッド停止ブロック生成部１０４中の命令に先立って実行されるような特別な依存関係を生成する。図２６は、図２５のプログラムの依存グラフを示す。図中、太い矢印で示している文Ｓ３１０、文Ｓ３１１から文Ｓ３００への依存が、ここで新たに生成した依存である。
【０１３６】
図２７は、図２５のプログラムに対するスケジューリング結果である。経路情報として変数が保持する値の情報を使用しない場合である図１４と比較すると、ステップ数が７ステップとなり、１ステップ減少する。
【０１３７】
図２８は、図２７のスレッドｔｈｒ＿Ｘ＿ＶＰと図１７のスレッドｔｈｒ＿Ｏｒに対して、スレッド並列化部１０２を適用した結果である。
【０１３８】
以上により、本変形例のプログラム変換装置１は、経路上に存在する変数と、当該変数毎に予め定められた定数値とを含む変数保持値情報を利用してスレッド内の最適化を行うことで、当該スレッドを短時間で実行できる。
【０１３９】
＜変形例２＞
上述した実施の形態では、ソースプログラムである図５の文Ｓ１から文Ｓ１５のプログラム部分をそのままスレッド化したスレッドｔｈｒ＿Ｏｒを生成し、スレッドｔｈｒ＿Ｘやスレッドｔｈｒ＿Ｘ＿ＶＰと並列実行するようにスレッドを形成することにより、スレッドｔｈｒ＿Ｘやスレッドｔｈｒ＿Ｘ＿ＶＰが停止しても、スレッドｔｈｒ＿Ｏｒは停止しないので、必ず、図５の文Ｓ１から文Ｓ１５の部分と等価な実行となることを保証していた。
【０１４０】
しかし、一般には図２９のように経路は複数指定されることもあり得る。この場合、ソースプログラム中の経路を全てスレッド化する必要がない。つまり、前述の例ではスレッドｔｈｒ＿Ｏｒを簡略化できる。以下、図を用いて詳細に説明する。
【０１４１】
図３０は、本変形例のプログラム変換装置のスレッド本体ブロック生成部の構成を階層的に示した図である。スレッド本体ブロック生成部１０３は、新たに、経路包含関係算出部１１９およびスレッド本体ブロック経路簡略化部１２０を備える。
【０１４２】
経路包含関係算出部１１９は、スレッドの包含関係を算出する。まず、経路情報が指定されている経路に関して、実行時に通る部分経路を全て抽出する。
【０１４３】
図２９の経路Ｘに関する部分経路は、
文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ４→文Ｓ５→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５のみであり、経路Ｙに関する部分経路は、
文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ６→文Ｓ７→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５となる。
【０１４４】
また、経路Ｘ、経路Ｙの開始点（ＢＥＧＩＮ（Ｘ）、ＢＥＧＩＮ（Ｙ））の直後の文Ｓ１から、終了点（ＥＮＤ（Ｘ）、ＥＮＤ（Ｙ））の直前の文Ｓ１５までの経路（説明上、経路Ｏｒと呼ぶことにする）に関する、部分経路は、
部分経路１：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ４→文Ｓ５→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５（経路Ｘに同じ）
部分経路２：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ６→文Ｓ７→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５（経路Ｙに同じ）
部分経路３：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ４→文Ｓ５→文Ｓ８→文Ｓ９→文Ｓ１２→文Ｓ１３→文Ｓ１４→文Ｓ１５
部分経路４：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ６→文Ｓ７→文Ｓ８→文Ｓ９→文Ｓ１２→文Ｓ１３→文Ｓ１４→文Ｓ１５
の４経路となる。当然のことではあるが、経路Ｘ、経路Ｙはともに、経路Ｏｒに含まれることが算出される。
【０１４５】
ここで、仮に、文Ｓ３の直後の「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＰＩＤ（Ｘ）」の記載がない場合、経路Ｘは、
部分経路１：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ４→文Ｓ５→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５
部分経路２：文Ｓ１→文Ｓ２→文Ｓ３→文Ｓ６→文Ｓ７→文Ｓ８→文Ｓ９→文Ｓ１０→文Ｓ１１→文Ｓ１５（経路Ｙに同じ）
の２経路となる。よって、この場合、経路Ｙは、経路Ｘにも含まれることになる。
【０１４６】
スレッド本体ブロック経路簡略化部１２０は、スレッドの包含関係から、第１のスレッドが第２のスレッドを包含する場合に、第１のスレッドから、第２のスレッドと重複する
経路を削除しかつ、不要な命令を削除した、スレッド本体ブロックを生成する。
【０１４７】
図２９の経路Ｘおよび経路Ｙはスレッド化されるので、経路Ｏｒの部分経路のうち経路Ｘおよび経路Ｙと等価な、部分経路１および部分経路２が削除され、部分経路３および部分経路４により、経路Ｏｒは再構築される。
【０１４８】
図３１（ａ）は、経路Ｏｒに対するスレッドｔｈｒ＿Ｏｒのスレッド本体ブロックを示す図である。部分経路３および部分経路４上に存在しない文Ｓ１０および文Ｓ１１は複写されない。図３１（ｂ）は、生成されたスレッドｔｈｒ＿Ｏｒに対して、自スレッド停止命令生成部１１１、他スレッド停止ブロック生成部１０４、出入口生存変数検出部１０５、出入口変数置換部１０６、入口ブロック生成部１０７、出口ブロック生成部１０８、スレッド内生存変数検出部１０９、スレッド内生存変数置換部１１０および入口ブロック内命令コピー伝播最適化部１１２を実施した結果である。
【０１４９】
図３２および図３３は、図２９に対してスレッド並列化部１０２まで実施した変換結果である。スレッドｔｈｒ＿Ｏｒ、スレッドｔｈｒ＿Ｘ、スレッドｔｈｒ＿Ｙが、並列実行されるように変換されている。図３２のスレッドｔｈｒ＿Ｏｒは、図１９と比較して簡略化される。
【０１５０】
以上のように、本変形例のプログラム変換装置は、特定のスレッドが停止した場合にも、残りのスレッドは必要最小限の実行を行うので、残りのスレッドの実行時間を短縮できる。
【０１５１】
＜変形例３＞
上述した変形例１では、経路情報として経路上に存在する変数と、当該変数毎に予め定められた定数値とを含む変数保持値情報を使用していたが、経路情報として、経路の実行確率および変数が特定の値を保持する確率を示す保持確率情報を用いてもよい。
【０１５２】
図３４は、プログラマにより経路の実行確率と、経路上で変数が特定の値を保持する確率を記述追加したソースプログラムの例である。図中、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｘ：７０）、  ＶＡＬ（ｂ：５：８０）、  ＶＡＬ（ｅ：８：５０）」は、経路Ｘの実行確率が７０％、変数ｂが経路Ｘ中で値５を保持する確率が８０％、変数ｅが経路Ｘ中で値８を保持する確率が５０％であることを示す。また、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｙ：２５）」は、経路Ｙの実行確率が２５％であることを示す。
【０１５３】
経路解析部１２４は、変形例１と比較して、新たに、確率特定手段を備える。確率特定手段は、経路の実行確率と、経路上で変数が特定の値を保持する確率とを特定する。具体的には、図３４の例において、確率特定手段は、「＃ｐｒａｇｍａ  ＰａｔｈＩｎｆ：  ＢＥＧＩＮ（Ｘ：７０）、  ＶＡＬ（ｂ：５：８０）、  ＶＡＬ（ｅ：８：５０）」を解析し、経路Ｘの実行確率が７０％、変数ｂが経路Ｘ中で値５を保持する確率が８０％、変数ｅが経路Ｘ中で値８を保持する確率が５０％であることを特定する。同様に、経路Ｙの実行確率が２５％であることを特定する。
【０１５４】
スレッド生成部１０１の動作は、上述の実施の形態および各変形例と同じであり、その結果、図２７、図３２および図３３に示すスレッドｔｈｒ＿Ｘ＿ＶＰ、スレッドｔｈｒ＿Ｏｒ、スレッドｔｈｒ＿Ｘおよびスレッドｔｈｒ＿Ｙが生成される。図３５および図３６は生成したスレッドの結果である。
【０１５５】
図３７は、本変形例のプログラム変換装置のスレッド並列化部の構成を階層的に示した図である。スレッド並列化部１０２は、新たに、スレッド間包含関係算出部１２１、スレッド平均実行時間算出部１２２および確率情報スレッド削除部１２３を備える。
【０１５６】
スレッド間包含関係算出部１２１は、スレッド生成部１０１により生成された第１のスレッドと第２のスレッドに対して、第１のスレッドと等価な経路が、第２のスレッドと等価な経路に含まれるか否かを判定し、含まれていると判定したとき、第１のスレッドが第２のスレッドに包含されているとみなして、スレッド間の包含関係を算出する。
【０１５７】
スレッドの包含関係を具体的に算出するには、前述の変形例２の経路包含関係算出部１１９で算出した経路間の包含関係を利用する。即ち、経路１と等価なスレッド１と、経路２と等価なスレッド２において、経路１が経路２を包含する場合は、スレッド１もスレッド２を包含すると特定する。
【０１５８】
また、変形例１において、予め定められた定数値で置換する前のスレッド３と、置換後のスレッド４において、スレッド３はスレッド４を包含すると特定することにより、スレッドの包含関係を算出する。例えば、図３６に示すスレッドｔｈｒ＿Ｘ＿ＶＰは、経路Ｘにおいて、変数ｂの値を５、変数ｅの値を８、と特化した場合のスレッドであるので、スレッドｔｈｒ＿Ｘ＿ＶＰは、スレッドｔｈｒ＿Ｘに包含されるものである。
【０１５９】
スレッド平均実行時間算出部１２２は、経路情報に含まれる経路の実行確率と、変数が保持する値の保持確率とから、生成されたスレッドの平均実行時間を算出する。
【０１６０】
図３５および図３６のスレッドｔｈｒ＿Ｏｒ、スレッドｔｈｒ＿Ｘ、スレッドｔｈｒ＿Ｘ＿ＶＰおよびスレッドｔｈｒ＿Ｙの平均実行時間は次の通りである。
【０１６１】
スレッドｔｈｒ＿Ｘの平均実行時間              ．．．    Ｔｘ＊Ｐｘ
スレッドｔｈｒ＿Ｘ＿ＶＰの平均実行時間        ．．．    Ｔｘ＊Ｐｘｖ
スレッドｔｈｒ＿Ｙの平均実行時間              ．．．    Ｔｙ＊Ｐｙ
スレッドｔｈｒ＿Ｏｒの平均実行時間            ．．．    Ｔｏｒ＊Ｐｏｒ
【０１６２】
ここで、Ｔｘ、ＴｙおよびＴｏｒは、それぞれ、スレッドｔｈｒ＿Ｘ、スレッドｔｈｒ＿Ｙ、スレッドｔｈｒ＿Ｏｒの実行時間である。Ｐｘは経路Ｘの確率７０％、Ｐｙは経路Ｙの実行確率２５％である。Ｐｏｒは、経路Ｘおよび経路Ｙ以外の経路を実行した場合の確率であるので５％である。また、Ｐｘｖは、経路Ｘ上の変数ｂが５、変数ｅが８を保持する確率であるので、２８％（７０％＊８０％＊５０％）である。
【０１６３】
確率情報スレッド削除部１２３は、スレッド間包含関係から、生成された２つのスレッドに対して、第１のスレッドが第２のスレッドに包含されており、かつ、第２のスレッドの平均実行時間が、第１のスレッドの平均実行時間より短い時に、第１のスレッドを削除する。
【０１６４】
図３６では、スレッドｔｈｒ＿Ｘ＿ＶＰは、スレッド＿ｔｈｒ＿Ｘに包含されるものであり、もし、スレッドｔｈｒ＿Ｘ＿ＶＰの平均実行時間が、スレッドｔｈｒ＿Ｘの平均実行時間と同じか、大きいときは、スレッドｔｈｒ＿Ｘ＿ＶＰを削除する。
【０１６５】
以上、実施の形態、変形例１、変形例２および変形例３を示したが、これだけに限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を本実施の形態に施したものや、異なる実施の形態における構成要素を組み合わせて構築される形態も、本発明の範囲内に含まれる。
【０１６６】
なお、上記において、経路情報はプログラマにより与えられえるとしたが、デバッガやシミュレータ等実行ツールからプログラム変換装置に与えられても良い。また、経路情報の与え方もソースプログラムから与えら得れるのではなく、ソースプログラムとは別の情報として、例えば経路情報ファイルとしてプログラム変換装置に与えられても良い。
【０１６７】
また、命令コードをアセンブラプログラムに対して追加してもよい。また、共有メモリは、集中共有メモリ型であっても、分散共有メモリ型であってもよい。
【産業上の利用可能性】
【０１６８】
以上のように、本発明にかかるプログラム変換装置は、ソースプログラムの特定部分を、等価でかつスレッド間で共有する記憶領域への値の書き込み競合を引き起こさないような複数スレッドで再構成し、スレッド毎に最適化変換と命令レベルの並列化変換を行い、複数スレッドを並列に実行するので、ソースプログラムの特定部分が高速化されたプログラムを生成できるという効果を有し、プログラム変換装置等として有用である。
【図面の簡単な説明】
【０１６９】
【図１】コンピュータシステムの概観図
【図２】コンパイラシステムの構成を示すブロック図
【図３】プログラム変換装置の構成を階層的に示した図
【図４】ソースプログラムの例
【図５】経路情報が記載されたソースプログラムの例
【図６】スレッド本体ブロックの生成例
【図７】自スレッド停止命令の生成例
【図８】他スレッド停止ブロックの生成の例
【図９】入口ブロックと出口ブロックの例
【図１０】スレッド内生存変数の置換の例
【図１１】入口ブロック内命令コピー伝播最適化の実施の例
【図１２】一般的な依存の依存グラフの例
【図１３】特殊な依存を追加した依存グラフの例
【図１４】命令スケジューリングの実施の例
【図１５】スレッド本体ブロックと他スレッド停止ブロックの例
【図１６】入口ブロックと出口ブロックの例
【図１７】スレッド内生存変数の置換の例
【図１８】入口ブロック内命令コピー伝播最適化の実施の例
【図１９】スレッド並列化の例
【図２０】変形例１のプログラム変換装置の構成を階層的に示した図
【図２１】変形例１の変数の値情報が記載されたソースプログラムの例
【図２２】変形例１の入口ブロック内命令コピー伝播最適化の実施の例
【図２３】変形例１の定数値判定ブロックの生成の例
【図２４】変形例１の定数伝播・畳み込みの実施の例
【図２５】変形例１の不要命令および不要な分岐の削除の実施の例
【図２６】変形例１の特殊な依存を追加した依存グラフの例
【図２７】変形例１の命令スケジューリングの実施の例
【図２８】変形例１のスレッド並列化の例
【図２９】変形例２の複数の経路情報が記載されたソースプログラムの例
【図３０】変形例２のスレッド本体ブロック生成部の構成を階層的に示した図
【図３１】変形例２のスレッド本体ブロックの経路簡略化の実施の例
【図３２】変形例２のスレッド並列化の一部を示した例
【図３３】変形例２のスレッド並列化の残る部分を示した例
【図３４】変形例３の確率情報が記載されたソースプログラムの例
【図３５】変形例３のスレッド並列化の一部を示した例
【図３６】変形例３のスレッド並列化の残る部分を示した例
【図３７】変形例３のスレッド並列化部の構成を階層的に示した図
【図３８】従来技術の説明図
【符号の説明】
【０１７０】
１  プログラム変換装置
１０１  スレッド生成部
１０２  スレッド並列化部
１０３  スレッド本体ブロック生成部
１０４  他スレッド停止ブロック生成部
１０５  出入口生存変数検出部
１０６  出入口変数置換部
１０７  入口ブロック生成部
１０８  出口ブロック生成部
１０９  スレッド内生存変数検出部
１１０  スレッド内生存変数置換部
１１１  自スレッド停止命令生成部
１１２  入口ブロック内命令コピー伝播最適化部
１１３  一般依存関係算出部
１１４  特殊依存発生部
１１５  命令スケジューリング部
１１６  定数値判定ブロック生成部
１１７  定数値変換部
１１８  冗長性削除最適化部
１１９  経路包含関係算出部
１２０  スレッド本体ブロック経路簡略化部
１２１  スレッド間包含関係算出部
１２２  スレッド平均実行時間算出部
１２３  確率情報スレッド削除部
１２４  経路解析部
１３０  スレッド作成部
１４０  置換部
１５０  スレッド内最適化部
２００  コンピュータシステム
２０１  記憶部
２０２  プログラム変換プログラム
２０３  ソースプログラム
２０４  プロセッサ
２０５  メモリ
２０７  目的プログラム
２１０  コンパイラシステム
２１１  コンパイラ
２１２  アセンブラ
２１３  リンカ
２１５  アセンブラプログラム
２１６  再配置可能バイナリプログラム
３００  従来技術のスレッドの例
３０１  従来技術のスレッドの例
３０２  従来技術のスレッドの例
３０３  従来技術のスレッドの例
【図１】
2010039536.tif 000003
【図２】
2010039536.tif 000004
【図３】
2010039536.tif 000005
【図４】
2010039536.tif 000006
【図５】
2010039536.tif 000007
【図６】
2010039536.tif 000008
【図７】
2010039536.tif 000009
【図８】
2010039536.tif 000010
【図９】
2010039536.tif 000011
【図１０】
2010039536.tif 000012
【図１１】
2010039536.tif 000013
【図１２】
2010039536.tif 000014
【図１３】
2010039536.tif 000015
【図１４】
2010039536.tif 000016
【図１５】
2010039536.tif 000017
【図１６】
2010039536.tif 000018
【図１７】
2010039536.tif 000019
【図１８】
2010039536.tif 000020
【図１９】
2010039536.tif 000021
【図２０】
2010039536.tif 000022
【図２１】
2010039536.tif 000023
【図２２】
2010039536.tif 000024
【図２３】
2010039536.tif 000025
【図２４】
2010039536.tif 000026
【図２５】
2010039536.tif 000027
【図２６】
2010039536.tif 000028
【図２７】
2010039536.tif 000029
【図２８】
2010039536.tif 000030
【図２９】
2010039536.tif 000031
【図３０】
2010039536.tif 000032
【図３１】
2010039536.tif 000033
【図３２】
2010039536.tif 000034
【図３３】
2010039536.tif 000035
【図３４】
2010039536.tif 000036
【図３５】
2010039536.tif 000037
【図３６】
2010039536.tif 000038
【図３７】
2010039536.tif 000039
【図３８】
2010039536.tif 000040