(57)【要約】【課題】ソースプログラム中の始点と終点を同じくする異なる実行経路それぞれの処理を並列に投機実行する場合よりも、効率を高めた投機実行方法を実現するための、ソースプログラムを実行形式プログラムに変換するプログラム変換装置を提供する。【解決手段】  ソースプログラムにおいて複数の実行経路があり、当該実行経路部分は繰り返し実行されるものとする。プログラム変換装置は、複数の実行経路のそれぞれの実行頻度を取得する。そして、実行頻度の高い実行経路から順にそれぞれの経路を最適化した命令を、ターゲットハードウェア上の各スレッドに割りふるコードを生成する。また、各スレッドが、処理した内容についてコミット処理を行ったかどうかを示す情報を出力するコードを生成する。より実行頻度の低い実行経路を割り当てる際には、コミット処理がなされなかった処理についてのみ、各スレッドに割り当てるコードを生成する。【選択図】図４
2012043128.tif 000002
【特許請求の範囲】
【請求項１】
始点と終点とを同じくする複数の実行経路を含む区間を複数回繰り返す繰り返し処理をプロセッサに実行させる処理を含むソースプログラムを、複数のプロセッサに並列に投機実行させるための実行プログラムに変換するプログラム変換装置であって、
前記複数の実行経路夫々について、当該実行経路を最適化し、コミット処理、及び、コミット処理がされたか否かを示すコミット処理情報を出力する処理を付加した第１コードを生成する第１コード生成手段と、
生成された複数の第１コードのうち、最も実行頻度の高い実行経路に対応する第１コードを前記繰り返し処理における回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第１割当コードを生成する第１割当コード生成手段と、
実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理を、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第２割当コードを生成する第２割当コード生成手段とを備える
ことを特徴とするプログラム変換装置。
【請求項２】
前記プログラム変換装置は、更に、
前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、
前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、コミット処理がされていない回数目の処理の分だけ、前記複数のプロセッサのうちの１つのプロセッサにのみ割り当てて実行させる第２割当コードを生成する
ことを特徴とする請求項１記載のプログラム変換装置。
【請求項３】
前記プログラム変換装置は、更に、
前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、
前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、実行されていない実行経路に対応する第１コードをそれぞれ別のプロセッサに割り当て、コミット処理がされていない回数目の処理の分だけ実行させる第２割当コードを生成する
ことを特徴とする請求項１記載のプログラム変換装置。
【請求項４】
前記プログラム変換装置は、更に、
前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、
前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、前記区間をそのまま実行形式に変換したオリジナルパスコードを、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第２割当コードを生成する
ことを特徴とする請求項１記載のプログラム変換装置。
【請求項５】
前記プログラム変換装置は、更に、
前記投機実行される実行経路の実行頻度及び実行時間に基づいて、前記第１割当コード及び前記第２割当コードを実行するか否かを判定させる第２判定コードを生成する第２判定コード生成手段と、
前記第１割当コード及び前記第２割当コードを実行しないと判定された場合に、前記区間をそのまま実行形式に変換したオリジナルパスコードを、前記繰り返し処理における回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第３割当コードを生成する第３割当コード生成手段とを備える
ことを特徴とする請求項１記載のプログラム変換装置。
【請求項６】
前記第２判定コード生成手段は、前記実行時間として、前記投機実行の対象である実行経路が選択されたときの実行時間と、選択されなかったときの実行時間とに基づいて判定させる前記第２判定コードを生成する
ことを特徴とする請求項５記載のプログラム変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はソースプログラムを投機実行する実行プログラムに変換する技術に関する。
【背景技術】
【０００２】
プログラムの実行にあたり、プログラムの実行速度を短縮する技術として投機実行がある。
投機実行は、プログラム内において、複数の実行経路がある場合に、実際に選択される経路は１つであるものの、マルチプロセッサを用いて各実行経路を最適化した複数の実行経路を並列に実行して、プログラムの実行速度を速める技術である。ある実行経路をマルチプロセッサに実行させるに当たり、その実行経路を最適化することにより、複数の分岐がある経路を実行するよりも、最適化した経路の方が、分岐条件命令の実行等をしなくてもよいため、より早く実行を終了させることができる。
【０００３】
しかし、複数の実行経路分のプロセッサを用意できない場合がある。
そこで、特許文献１には、複数の実行経路分のプロセッサがなくとも効率的な投機実行可能な実行プログラムをソースプログラムから生成できるプログラム変換装置が開示されている。当該実行プログラムをマルチプロセッサ等が実行することにより、複数の実行経路がある場合に、各実行経路の実行される確率の高いものから最適化してあるプロセッサに実行させるとともに、実行確率の低い経路については、最適化されていないプログラムをあるプロセッサに実行させている。これにより、複数の実行経路分のマルチプロセッサがなくとも、投機実行を実現できるとともに、実行頻度の高い経路が実行された場合には、プログラムの実行に要する時間を短縮することができる。
【０００４】
具体的に説明すると、仮に、図１６に示すようなフローグラフで示される処理がプログラム１０内に組み込まれているものとする。図１６に示すフローグラフの各ブロックＩ、Ｊ、Ｋ、Ｌ、Ｑ、Ｓ、Ｔ、Ｕ、Ｘは１以上の命令を含むブロックであり、ブロックＩ、Ｊ、Ｋ、Ｓは、それぞれその最後に分岐命令を含むものとする。また、このプログラムは、４つのプロセッサにより並列実行されるものとする。当該フローは、プログラム１０内において、何度も出現するパターンであり、何度も繰り返し実行されるものであるとする。
【０００５】
このフローグラフにおいては、５つの実行経路があるが、実際にプログラムが実行されて通過する経路はこのうちの一つである。そして、ここでは、実行経路Ｉ→Ｊ→Ｑが最も実行頻度が高い実行経路であり、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔが次に実行頻度が高く、実行経路Ｉ→Ｊ→Ｋ→Ｌが次に実行頻度が高いものとする。
【０００６】
そこで、マルチプロセッサは、最も実行頻度の高い実行経路Ｉ→Ｊ→Ｑの命令列を最適化した実行プログラムを一つのプロセッサ（図１７のスレッド２参照）に実行させる。また、２番目に実行頻度の高い実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔの命令列を最適化した実行プログラムを一つのプロセッサ（図１７のスレッド３参照）また、３番目に実行頻度の高い実行経路Ｉ→Ｊ→Ｋ→Ｌの命令列を最適化した実行プログラムを一つのプロセッサ（図１７のスレッド４参照）に実行させ、その他の経路を保証するために、オリジナルの実行経路を示すプログラムを変換して得られる実行プログラムを一つのプロセッサ（図１７のスレッド１参照）に実行させる。
【０００７】
このような投機実行をすることで、実行経路Ｉ→Ｊ→Ｑ、Ｉ→Ｊ→Ｋ→Ｓ→Ｔ、Ｉ→Ｊ→Ｋ→Ｌのいずれかを通る場合には、オリジナルのプログラムを実行するよりもプログラムの実行時間を短縮することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００６−１５４９７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、上述したように、上記特許文献１の場合には、複数の実行頻度の高い実行経路をそれぞれ異なるプロセッサに実行させるとともに、最適化されていないオリジナルパスを示すプログラムを１つのプロセッサに実行させることによって、プログラムの動作を保障するとともに、実行速度の短縮を図っていた。
【００１０】
しかし、当該構成の場合、１つのスレッドにより実行されて得られる結果のみが選択されるため、他のスレッドで実行されていたプログラムの処理は破棄されることになるので、ある種の無駄が発生していたと言える。
【００１１】
具体例を挙げて説明するとすれば、例えば図１７に示すように各処理を各スレッドに割り振ったとして、その実行結果が、例えば、図１８のようになったとする。この図１８で言えば、ＯＫとなっているスレッド以外のスレッドは、その処理が無駄になっているとも言える。投機実行はこの無駄が発生することを踏まえたうえでのプログラムの処理を高速化するものであるものの、この無駄をなるべく抑えたいという要望がある。なお、本図１８において、オリジナルパスは実際には全てＯＫとなるのであるが、その他のパスの実行が早く終了しコミット処理がされた場合に中断することになるため、そのような場合はＮＧとしている。
【００１２】
本発明は、当該無駄を除去することができる投機実行方法を提供することを目的とし、ソースプログラムを、当該投機実行方法がなされるようにコンピュータが実行可能な実行形式の命令列に変換するプログラム変換装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決するため、本発明は、始点と終点とを同じくする複数の実行経路を含む区間を複数回繰り返す繰り返し処理をプロセッサに実行させる処理を含むソースプログラムを、複数のプロセッサに並列に投機実行させるための実行プログラムに変換するプログラム変換装置であって、前記複数の実行経路夫々について、当該実行経路を最適化し、コミット処理、及び、コミット処理がされたか否かを示すコミット処理情報を出力する処理を付加した第１コードを生成する第１コード生成手段と、生成された複数の第１コードのうち、最も実行頻度の高い実行経路に対応する第１コードを前記繰り返し処理における回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第１割当コードを生成する第１割当コード生成手段と、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理を、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第２割当コードを生成する第２割当コード生成手段とを備えることを特徴としている。
【００１４】
ここで、コミット処理とは、実行経路の選択処理のことであり、複数ある実行経路のうちの１つの実行結果を確定させる処理のことである。
【発明の効果】
【００１５】
上述のような構成によって、従来技術における投機実行上の無駄を省き、プログラムの総実行時間を従来よりも短縮することができる。
【図面の簡単な説明】
【００１６】
【図１】プログラム変換装置の機能構成を示す機能ブロック図である。
【図２】プログラム変換装置のプログラム変換における基本動作を示すフローチャートである。
【図３】ソースプログラムを投機実行可能な実行形式に変換するプログラム変換装置の動作を示すフローチャートである。
【図４】プログラム変換装置により生成された実行形式の命令列をターゲットウェアの投機実行の手法を示す図である。
【図５】変形例１−１に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図６】図５の動作を行った場合のターゲットハードウェアの投機実行の手法を示す図である。
【図７】変形例１−２に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図８】変形例２−１に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図９】図８の動作を行った場合のターゲットハードウェアの投機実行の手法を示す図である。
【図１０】変形例２−２に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図１１】変形例３−１に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図１２】図１１の動作を行った場合のターゲットハードウェアの投機実行の手法を示す図である。
【図１３】変形例３−２に係る投機実行におけるプログラム変換装置の動作の変形例を示すフローチャートである。
【図１４】フローグラフの各分岐の確率を示す図である。
【図１５】実行頻度をプログラムで指定する手法を示すプログラム例である。
【図１６】プログラムのフローグラフの一例を示す図である。
【図１７】図１６に示すフローグラフの実行経路のうち、実行頻度の高いものを最適化してスレッドに割り当てる投機実行例を示す図である。
【図１８】図１７に示すようにスレッドに命令列を割り振ったその実行結果を示す図である。
【発明を実施するための形態】
【００１７】
＜実施の形態＞
以下、本発明の一実施形態である投機実行方法について図面を用いて説明する。
＜構成＞
図１は、本発明に係る投機実行方法を実行するプロセッサに命令列を供給するプログラム変換装置１００の機能構成を示す機能ブロック図である。プログラム変換装置１００はソースプログラム１０を、ターゲットハードウェア２００用の実行プログラム３０に変換するものであり、所謂コンパイラとしての機能を有する。プログラム変換装置１００により変換生成された実行プログラム３０は、ターゲットハードウェア２００上で実行される。ターゲットハードウェア２００は、所謂プロセッサである。
【００１８】
図１に示すようにプログラム変換装置１００は、解析部１０１と、最適化部１０２と、コード変換部１０３とを含んで構成される。
解析部１０１は、高級言語により記述されたソースプログラム１０を入力とし、当該ソースプログラム１０の内容を解析して、図１６に示すようなフローグラフを含む解析情報を生成し、最適化部１０２に伝達する機能を有する。当該解析は、従来からも行われていることであり、ここでは、その詳細は割愛する。
【００１９】
最適化部１０２は、解析部１０１から伝達された解析内容に基づいて、ソースプログラム１０で示される処理を最適化する機能を有する。
最適化部１０２は、実行経路（実行経路は、パスともいう）の実行頻度情報４０を受け付けていない場合においては、解析部１０１から受け付けた解析情報に繰り返し処理が含まれているか否かに応じて、繰り返し処理が含まれて板場合に、当該繰り返し処理における各実行経路の実際に実行された頻度を示す実行頻度情報を出力させる処理を加えた情報をコード変換部１０３に出力する機能を有する。
【００２０】
最適化部１０２は、実行頻度情報４０を受け付けている場合には、ソースプログラム１０をターゲットハードウェア２００が投機実行を実行するために最適化し、生成した情報をコード変換部１０３に出力する機能を有する。なお、投機実行用の最適化の詳細については、図３のフローチャートを用いて後述する。
【００２１】
コード変換部１０３は、最適化部１０２から伝達された情報に基づきソースプログラム１０をターゲットハードウェア２００が実行できる実行形式の実行プログラム３０に変換する機能を有する。
【００２２】
ターゲットハードウェア２００は、プログラム変換装置１００から伝送されてきた実行プログラム３０を実行する機能を有するマルチプロセッサであり、少なくとも４つのプロセッサを備え、４つのスレッドを並列実行できる機能を有する。ターゲットハードウェア２００は、プログラム変換装置１００から実行頻度情報を出力する処理を含む実行プログラム３０を受け付けた場合には、通常通りソースプログラム１０がそのまま実行形式に変換された実行プログラム３０を実行して、各実行経路の実行頻度を算出して得た実行頻度情報４０をプログラム変換装置１００に出力し、投機実行用の実行プログラム３０を受け付けた場合には、当該実行プログラム３０を実行することにより、実行頻度情報４０をプログラム変換装置１００に出力する機能を有する。
＜動作＞
次に、本実施の形態におけるコンパイル動作を図２及び図３に示すフローチャートを用いて説明する。
【００２３】
図２はプログラム変換装置１００の基本動作を示すフローチャートである。
プログラム変換装置１００の解析部１０１は、プログラマにより高級言語で記載されたソースプログラム１０の構文を解析し、解析して得た情報を最適化部１０２に伝達する（ステップＳ２０１）。
【００２４】
解析情報を受け付けた最適化部１０２は、実行頻度情報４０を受け付けているかを判定する（ステップＳ２０２）。
実行頻度情報４０を受け付けていない場合には（ステップＳ２０２のＮＯ）、解析して得られた情報に基づき、ソースプログラム１０の投機実行を行う繰り返し部分において、それぞれの実行経路についてその実行経路のコミット処理を行ったかどうかについてのコミット処理情報を出力する処理を付加する（ステップＳ２０３）。
【００２５】
そして、最適化部１０２は、その投機実行を行う繰り返し部分の実行経路ごとの実行頻度をその実行経路についてコミット処理が行われた回数を繰り返し部分の繰り返し数で割って得られる実行頻度情報４０を出力する処理を付加する。そして、コード変換部１０３は、最適化部１０２が付加した処理を含む処理を実行形式に変換した実行プログラム３０を出力して終了する（ステップＳ２０４）。
【００２６】
ステップＳ２０１、Ｓ２０２、Ｓ２０３、Ｓ２０４の処理を経てプログラム変換装置１００により生成された実行プログラム３０を伝送されてきたターゲットハードウェア２００は、当該実行プログラム３０を実行し、ソースプログラム１０に記載されている処理を実行しつつ、実行頻度情報４０を生成してプログラム変換装置１００に出力することとなる。
【００２７】
一方、プログラム変換装置１００の最適化部１０２は、実行頻度情報４０を受け付けている場合は（ステップＳ２０２のＹＥＳ）、投機実行用の実行プログラムのための処理を生成する。当該処理の詳細については、図３を用いて後述する。コード変換部１０３は、最適化部１０２が生成した処理を実行形式に変換した実行プログラム３０を出力する（ステップＳ２０５）。
【００２８】
本実施例に係るプログラムの投機実行用のプログラムを生成する動作を図３に示すフローチャートを用いて説明する。当該図３に示すフローチャートは、図２のステップＳ２０５の処理を詳細に示したものである。なお、当該投機実行の最適化については、投機実行が実行される部分に対してなされる処理のみを説明するものとし、その他の部分についての最適化については従来技術に順ずるものとして説明を割愛する。
【００２９】
最適化部１０２は、解析情報の中に分岐を含む繰り返し処理があるかどうかを検出する（ステップＳ３０１）。繰り返し処理がない場合には（ステップＳ３０１のＮＯ）、そのまま最適化処理を行わずに処理を終了する。
【００３０】
繰り返し処理がある場合には（ステップＳ３０１のＹＥＳ）、最適化部１０２は、当該繰り返し処理に含まれる複数の実行経路のうち、実行頻度情報４０で示される実行頻度が最も高い実行経路のブロックを最適化する（ステップＳ３０２）。当該最適化においては、最適化する実行経路のブロックから分岐命令を除いて一連の命令列にした後に、当該実行経路の各分岐命令に基づき当該実行経路が選択されるかどうかの判定処理と、選択された場合のコミット処理とを付加するものである。
【００３１】
最適化部１０２は、その後にコミット処理がなされたかどうかを示すコミット処理情報を出力する処理を付加する（ステップＳ３０３）。当該コミット処理情報は、プログラム中におけるどの繰り返し処理の、繰り返し処理の中の何回目の処理であるかを示す情報を含み、出力された当該情報は、特定のレジスタ等に格納されるものとする。
【００３２】
そして、最も実行頻度の高い実行経路について、繰り返し処理の、繰り返しの回数目を異ならせて、ターゲットハードウェア２００の全スレッドに割り当てる処理を付加する（ステップＳ３０４）。これは、例えば、全スレッド数が３であった場合には、繰り返し処理の中の１回目の処理をスレッド１に、２回目の処理をスレッド２に、３回目の処理をスレッド３に、４回目の処理をスレッド１に、・・・という風に割り当てて並列実行させる処理である。また、繰り返し処理の中の１回分の処理とは、図１６を例に説明すると、図１６に示すフローグラフの先頭（ブロックＩの先頭）から各実行経路の終点（ブロックＬ、Ｑ、Ｔ、Ｕ、Ｘの最後の命令）までの処理が１回分の処理に該当する。
【００３３】
最適化部１０２は、その後にコミット処理されていない処理、即ち、繰り返し処理の中でその実行経路が実際に選択されなかった回数目であって繰り返し処理の何回目の繰り返しであるのかを示す情報を前記ターゲットハードウェア２００に取得させる処理を付加する（ステップＳ３０５）。
【００３４】
最適化部１０２は、その後に、最適化されていない実行経路のうち、実行頻度の最も高い実行経路のブロックを最適化する（ステップＳ３０６）。
最適化部１０２は、その後にコミット処理がなされたかどうかの情報を出力する処理を付加する（ステップＳ３０７）。
【００３５】
最適化部１０２は、その後に、ステップＳ３０５で取得したコミット処理がされていない処理の情報に基づいて、実行されていない回数目の処理をその回数目（ここでいう回数目とは、上述の通り繰り返し処理中の何回目の繰り返しであるかを示すものである。）を異ならせて、それぞれ異なるスレッドに並列実行させる処理を付加する（ステップＳ３０８）。これは、例えば、全スレッド数が３であって、コミット処理がされていない処理が繰り返し処理の３回目、６回目、７回目、９回目、１０回目の処理であったとする。この場合に、実行されていない実行経路を最適化した処理を全スレッドに割り当てるとともに、３回目の処理をスレッド１に、６回目の処理をスレッド２に、７回目の処理をスレッド３に、９回目の処理をスレッド１に、１０回目の処理をスレッド２に割り当てて並列実行させる処理である。
【００３６】
最適化部１０２は、最後に当該繰り返し部分の全実行経路についての最適化を実行したかどうかを判定する（ステップＳ３０９）。
全実行経路の最適化を行っていない場合には（ステップＳ３０９のＮＯ）、ステップＳ３０５に戻る。全実行経路の最適化を行っていた場合には（ステップＳ３０９のＹＥＳ）、そのまま処理を終了する。
【００３７】
以上の最適化処理を行って、実行形式に変換された投機実行用の実行プログラム３０をターゲットハードウェア２００が実行した場合の動作について一具体例を用いて説明する。
【００３８】
ここでは、図１６に示すフローグラフが１０回繰り返し実行されるものとし、実行経路Ｉ→Ｊ→Ｑが最も実行頻度が高い実行経路であり、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔが次に実行頻度が高く、実行経路Ｉ→Ｊ→Ｋ→Ｌが次に実行頻度が高いものとする。残り２つの実行経路は、実行経路Ｉ→Ｘの方が実行頻度が高く、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｕが最も実行頻度が低い実行経路であるとする。
【００３９】
当該実行頻度４０は、実際に図１６に示すフローグラフの繰り返し処理を含むプログラムをターゲットハードウェア２００が実行したことにより、既に得られているものとする。
【００４０】
ターゲットハードウェア２００は、実行経路Ｉ→Ｊ→Ｑを最適化した命令列を、全スレッド（スレッド１〜スレッド４）に割り当て、繰り返し実行される回数（１０回）分だけ、並列にその繰り返し処理の回数目を異ならせて割り当てる。
【００４１】
即ち、ターゲットハードウェア２００は、まず、図４（ａ）に示すように、実行経路Ｉ→Ｊ→Ｑを最適化し、コミット処理とコミット処理がなされたか否かを示す情報を出力する処理とを付加された処理を割り当て、スレッド１には、１回目、５回目、９回目の分の処理を、スレッド２には、２回目、６回目、１０回目の分の処理を、スレッド３には、３回目、７回目の分の処理を、スレッド４には、４回目、８回目の分の処理を実行させる。
【００４２】
そして、このとき、各スレッドは、実行した繰り返し処理におけるどの回数目の処理であるかを示し、コミット処理がされたかどうかを示すコミット処理情報を出力して、所定のメモリに格納する。
【００４３】
当該命令列が実行されて、例えば、図４（ａ）に示すように、１回目、２回目、４回目、５回目、１０回目についてコミット処理がなされ、その他の処理においては、コミット処理がなされなかったとする。すると、この場合コミット処理がなされなかった処理の情報とは、３回目、６回目、７回目、８回目、９回目の処理ということになり、この情報がターゲットハードウェア２００上に保持される。
【００４４】
次に、ターゲットハードウェア２００は、２番目に実行頻度の高い経路、即ち、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔを最適化し、コミット処理とコミット処理がなされたか否かを示す処理を付加した処理を全スレッドに割り当てる。このとき、前回の実行結果において、コミット処理がなされなかった処理の情報で示される繰り返し処理の回数目の分だけ、その回数目を異ならせて各スレッドに並列に割り当てる。
【００４５】
この命令列を実行するとターゲットハードウェア２００上では、図４の例で言えば、３回目、６回目、７回目、８回目、９回目の分の処理が各スレッドに割り当てられて実行される。即ち、図４（ｂ）に示すように、ターゲットハードウェア２００は、スレッド１に３回目と９回目の処理を、スレッド２に６回目の処理を、スレッド３に７回目の処理を、スレッド４に８回目の処理を割り当てて実行することとなる。
【００４６】
ターゲットハードウェア２００上における実行の結果、６回目、７回目、９回目の処理に対してコミット処理がなされ、コミット処理されていない処理として、３回目と８回目の処理が残り、その情報がターゲットハードウェア上に保持される。
【００４７】
そして、ターゲットハードウェア２００は、図４（ｃ）に示すように、その次に実行頻度が高い実行経路Ｉ→Ｊ→Ｋ→Ｌを最適化し、コミット処理と、コミット処理がされたか否かを示す情報を出力する処理とが付加された処理を、各スレッドに割り振って、並列実行させる。即ち、３回目の処理をスレッド１に、８回目の処理をスレッド２に割り当てる。
【００４８】
ターゲットハードウェア２００上における実行の結果、８回目の処理に対してコミット処理がなされ、コミット処理されていない処理として、３回目の処理が残り、その情報がターゲットハードウェア上に保持される。
【００４９】
そして、次に実行頻度が高い実行経路Ｉ→Ｘが最適化された処理がスレッド１に割り当てられて実行される。なお、図４（ｄ）では、実行経路Ｉ→Ｘが実行されコミット処理がなされたこととなっているが、ここで、コミット処理がなされなかった場合には、最後に、残っている実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｕをスレッド１に実行させることとなる。
【００５０】
以上の内容からわかるように、本実施の形態に示す投機実行を実行した場合には、回数で言えば、全ての処理を実行し終わるのに、図４（ａ）〜図４（ｄ）に示されるように７回の並列投機実行で済んでおり、従来の実行例を示す図１８にあるように、従来であれば１０回の並列投機実行をする必要があったのに対して、３回分の時間の短縮を図ることができており、総実行時間の短縮を実現できている。即ち、従来の投機実行における無駄を削減できている。
【００５１】
なお、本実施例に開示した内容は、前回の値を次の繰り返しの処理に適用する必要がある、即ち、繰り返し間にデータの依存関係があるイタレーションには対応できない。
＜変形例＞
上記実施の形態における変形例について説明する。当該変形例１では、実行すべき実行経路のスレッドへの割り当て手法に関するものであり、プログラム変換装置は以下に示すように実行経路をスレッドに割り当てる命令列を生成することとしてもよい。
＜変形例１−１＞
変形例１−１においては、投機実行を行う部分の繰り返し数が所定数以下になった場合に、全スレッドに処理を並列に割り当てずに、１つのスレッドにのみ割り当てる例を示す。なお、当該所定数は、プログラム変換装置１００が予め記憶しておいて指定することとしてよく、この所定数は、プログラム変換装置１００のオペレータ等により任意に設定できることとしてよい。
＜動作＞
変形例１−１における投機実行用の実行プログラムを生成する動作を図５のフローチャートに示す。なお、図５に示すフローチャートにおいて、図３に示すフローチャートと同様の動作を実行するステップにおいては同じステップ番号をふっている。
【００５２】
図５に示すように、ステップＳ３０１、Ｓ３０６、Ｓ３０７、Ｓ３０９に示す処理により、最適化部１０２は、ステップＳ３０１に示される分岐を含む繰り返しにおける各実行経路について、ターゲットハードウェア２００から取得している実行頻度情報４０に基づき、その実行頻度の高いものから、実行経路上のブロックを最適化し、コミット処理と、コミット処理がされたか否かを示す情報を出力する処理とを付加したコードが生成される。
【００５３】
次に、最適化部１０２は、最も高い実行頻度を有する経路について、繰り返し数の分だけ、それぞれの繰り返しの回数目を異ならせて、各スレッドに割り当てる処理を付加する（ステップＳ５０１）。
【００５４】
最適化部１０２は、ターゲットハードウェア２００がコミット処理されていない処理の情報を取得する処理を付加する（ステップＳ５０２）。
そして、最適化部１０２は、ターゲットハードウェア２００が取得したコミット処理されていない処理の情報に基づき、残りの処理数が所定数以下になっているかどうかを判定する判定処理を付加する（ステップＳ５０３）。
【００５５】
最適化部１０２は、ターゲットハードウェア２００がステップＳ５０３において付加された処理を実行した判定の結果、残りの処理数が所定数以下になっていなかった場合には、ターゲットハードウェア２００に実行していない実行経路のうち最も実行頻度の高い実行経路を最適化した処理を、コミット処理がされなかった分の処理だけ、その回数を異ならせて各スレッドに割り当てさせ、残りの処理数が所定数以下になっていた場合には、ターゲットハードウェア２００に実行していない残りの実行経路のうち最も実行頻度の高い実行経路を最適化した処理を１つのスレッドにのみ割り当てさせる処理を付加する（ステップＳ５０３）。なお、実行していない残りの実行経路を最適化した処理とは、残りの実行経路上のブロックをまとめて最適化したものであり、複数の実行経路が残っている場合には、最適化後のコードには分岐命令に対応する処理を含んでいてもよいものとする。
【００５６】
そして、最適化部１０２は、ステップＳ５０４の判定の結果、全ての実行経路についての処理を行っている場合には、全ての処理を終了し、全ての実行経路についての処理を行っていない場合には、ステップＳ５０１の処理に戻る処理を付加して、プログラムの変換処理を終了する。
【００５７】
当該フローチャートに従った場合のスレッドへの割り当ての例を図６に示す。ここでは、所定数を３とする。当該スレッドへの割り当ては、図１６に示すフローグラフを投機実行した場合のものであり、ターゲットハードウェア２００においては、図４の（ａ）、（ｂ）までは、上記実施の形態１と同様の割り当て方がされる。
【００５８】
すると、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔの実行後には、未実行の処理は、３回目と８回目の２回となり所定数３以下となる。
そのため、この場合には、図６に示すように、次に実行頻度が高い実行経路Ｉ→Ｊ→Ｋ→Ｌを最適化した処理がスレッド１にのみ割り当てられて実行される。
【００５９】
この後には、図４（ｄ）に示される割り当てと同様の割り当てが行われる。
このようにすることで、処理数が残り少なくなった場合（処理数が所定数を下回った場合）には、残っている実行経路の処理が一つのスレッドにのみ割り当てられることになるので、ターゲットハードウェア２００は、処理が割り当てられなかったスレッドにその他の処理を割り振ることができ、各種の処理の高効率化を実現できる。
【００６０】
＜変形例１−２＞
本変形例１−２においては、上記変形例１−１と同様の実行処理が行われるプログラムを生成するプログラム変換装置の当該プログラムを生成する別の手法を開示する。
＜動作＞
変形例１−２における最適化部１０２が投機実行用の実行プログラムを生成する動作を図７のフローチャートに示す。なお、図７において、図３に示した動作と共通する部分については、同じステップ番号を付して、その説明を割愛するものとする。
【００６１】
最適化部１０２は、最も実行頻度の高い実行経路の最適化処理を終了すると、ターゲットハードウェア２００にコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる処理を付加する（ステップＳ７０１）。
【００６２】
そして、残りの処理数が所定回数以下でない場合には（ステップＳ７０１のＮＯ）、最適化部１０２は、ステップＳ３０５以降の処理を実行する。
残りの処理数が所定数以下の場合には（ステップＳ７０１のＹＥＳ）、ステップＳ３０５〜Ｓ３０７と同様の処理ステップＳ７０２〜Ｓ７０５を実行する。
【００６３】
そして、最適化部１０２は、最適化した処理を全スレッドではなく、１つのスレッドにのみコミット処理されていない処理の回数分だけ実行させる処理を付加して（ステップＳ７０５）、ステップＳ３０９に移る。
【００６４】
このような手法で変換されたプログラムをターゲットハードウェア２００が実行したとしても、図６に示すようなスレッドの割り当てがなされる。
＜変形例２−１＞
変形例２−１においては、投機実行を行う部分の繰り返し数が所定数以下になった場合に、未実行の実行経路それぞれを最適化した処理をそれぞれ別々のスレッドに割り当てる例を示す。つまり、同時に別の実行経路を並列実行させるという本来の投機実行と同様の処理をさせる例を示す。なお、当該所定数は、プログラム変換装置１００が予め記憶しておいて指定することとしてよく、この所定数は、プログラム変換装置１００のオペレータ等により任意に設定できることとしてよい。
＜動作＞
変形例２−１における投機実行用の実行プログラムを生成する動作を図８のフローチャートに示す。なお、図８に示すフローチャートにおいて、図５に示すフローチャートと同様の動作を実行するステップにおいては同じステップ番号をふっている。
【００６５】
本変形例２−１は、残りの処理数が所定数以下になったときにターゲットハードウェア２００に実行させる処理が、変形例１−１とは異なってくる。
即ち、プログラム変換装置１００は、図５に示したステップＳ５０４の処理に換えて、図８に示すステップＳ８０４の処理を実行する。ステップＳ８０４の処理以外の処理は、変形例１−１に示した通りである。
【００６６】
ステップＳ８０４においては、最適化部１０２は、残りの処理数が所定数より大きい場合に、ステップＳ５０１で付加した処理を実行する処理を、残りの処理数が所定数以下であった場合に、コミット処理されていない処理の分だけ別々のスレッドに異なる実行経路を最適化し、コミット処理を追加し、コミット処理されたか否かを出力する処理を追加した処理を割り当てる処理を付加する。
【００６７】
こうすることで、ターゲットハードウェア２００は、残りの処理数が所定数以下になった場合には、実行されていない実行経路の処理をそれぞれ別々のスレッドに実行させるという従来通りの投機実行に切り替えることができる。これにより、実行頻度の低い実行経路については、当該実行経路が選択される可能性が低いため、投機実行の高い実行経路を繰り返しの回数を異ならせて全スレッドに割り当てて実行させるという手法の効率が低下するので、従来の投機実行方法に切り替えても問題はなく場合によっては、処理の高効率化を図ることができる。
【００６８】
図８のフローチャートに従った場合のスレッドへの割り当ての例を図９に示す。
ここでは、所定数を３とする。当該スレッドへの割り当ては、図１６に示すフローグラフを投機実行した場合のものであり、図４の（ａ）、（ｂ）までは、上記実施の形態１と同様の割り当て方がされる。
【００６９】
すると、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔの実行後には、未実行の処理は、３回目と８回目の２回となり所定数以下となる。
そのため、この場合には、図９に示すように、残りの実行経路Ｉ→Ｊ→Ｋ→Ｌ、Ｉ→Ｘ、Ｉ→Ｊ→Ｋ→Ｓ→Ｕの実行経路それぞれを最適化した処理が、それぞれ、スレッド１、スレッド２、スレッド３に割り当てられて実行される。
【００７０】
＜変形例２−２＞
本変形例２−２においては、上記変形例２−１と同様の実行処理が行われるプログラムを生成するプログラム変換装置の当該プログラムを生成する別の手法を開示する。
＜動作＞
変形例２−２における投機実行用の実行プログラムを生成する動作を図１０のフローチャートに示す。なお、図１０において図７に示した動作と共通する部分については同じステップ番号を付して、その説明を割愛するものとする。
【００７１】
図１０において、未実行の処理が所定数以下となった場合（ステップＳ７０１のＹＥＳ）、未実行の実行経路それぞれを最適化する（ステップＳ１００２）。
そして、最適化部１０２は、コミット処理されていない処理の分だけ別々のスレッドに、異なる実行経路の処理を割り当てる処理を付加する（ステップＳ１００３）。言い換えれば、未実行の実行経路について、１つの実行経路を１つのスレッドに割り当てる処理を付加して、処理を終了する。
【００７２】
当該手法によって生成された実行プログラムをターゲットハードウェア２００が実行しても、図９に示すような割り当てが実現できる。
＜変形例３−１＞
変形例３−１においては、投機実行を行う部分の繰り返し数が所定数以下になった場合に、オリジナルパスを割り当てる例を示す。なお、当該所定数は、プログラム変換装置１００が予め記憶しておいて指定することとしてよく、この所定数は、プログラム変換装置１００のオペレータ等により任意に設定できることとしてよい。
＜動作＞
変形例３−１における投機実行用の実行プログラムを生成する動作を図１１のフローチャートに示す。なお、図８に示すフローチャートにおいて、図５に示すフローチャートと同様の動作を実行するステップにおいては同じステップ番号をふっている。
【００７３】
本変形例３−１は、残りの処理数が所定数以下になったときにターゲットハードウェア２００に実行させる処理が、変形例１−１とは異なってくる。
即ち、プログラム変換装置１００は、図５に示したステップＳ５０４の処理に換えて、図１１に示すステップＳ１１０４の処理を実行する。ステップＳ１１０４の処理以外の処理は、変形例１−１に示した通りである。
【００７４】
ステップＳ１１０４においては、最適化部１０２は、残りの処理数が所定数より大きい場合の処理として、ステップＳ５０１において付加した処理に戻る処理を、残りの処理数が所定数以下になっていた場合の処理として、コミット処理されていない処理の分だけ回数を異ならせてオリジナルパスを全スレッドに割り当てる処理を付加する。
【００７５】
こうすることで、残りの処理数が所定数以下になった場合には、投機実行の効率が低下してしまう、つまり、投機実行する有用性が低下するので、コミット処理されていない処理の分だけ回数を異ならせてオリジナルパスを全スレッドに割り当てる。このようにすると、予め、残りの処理数が所定数以下になるタイミングが分かっている場合には実行頻度の低い実行経路についての最適化処理を実行しなくともよくなるため、プログラム変換装置１００における、その分の処理負荷を軽減することができる。
【００７６】
図１１のフローチャートに従った場合のスレッドへの割り当ての例を図１２に示す。
ここでは、所定数を３とする。当該スレッドへの割り当ては、図１６に示すフローグラフを投機実行した場合のものであり、図４の（ａ）、（ｂ）までは、上記実施の形態１と同様の割り当て方がされる。
【００７７】
すると、実行経路Ｉ→Ｊ→Ｋ→Ｓ→Ｔの実行後には、未実行の処理は、３回目と８回目の２回となり所定数以下となる。
そのため、この場合には、図１２に示すように、オリジナルパスを最適化した処理が、それぞれ、スレッド１、スレッド２、に回数を異ならせて、即ち、３回目の処理がスレッド１に、８回目の処理がスレッド２に割り当てられて実行される。
【００７８】
このようにすることで、ターゲットハードウェア２００は、処理が割り当てられなかったスレッドをその他の処理のために割り振ることができるとともに、並列実行回数を抑制することができる。この場合の所定数は、並列実行可能なスレッド数以下とすると効果が高い。
【００７９】
＜変形例３−２＞
本変形例３−２においては、上記変形例３−１と同様の実行処理が行われるプログラムを生成するプログラム変換装置の当該プログラムを生成する別の手法を開示する。
＜動作＞
変形例３−２における投機実行用の実行プログラムを生成する動作を図１３のフローチャートに示す。なお、図１３において図７に示した動作と共通する部分については同じステップ番号を付して、その説明を割愛するものとする。
【００８０】
図１３において、未実行の処理が所定数以下となった場合（ステップＳ５０１のＹＥＳ）、コミット処理されていない処理の情報を取得する処理を付加する（ステップＳ１３０２）。
【００８１】
そして、最適化部１０２は、オリジナルパス、即ち、ソースプログラムそのままを最適化し（ステップＳ１３０３）、そのオリジナルパスをコミット処理されていない処理の回数分だけ、その回数を異ならせて、全スレッドに並列に割り当てる処理を付加して（ステップＳ１３０４）、処理を終了する。
【００８２】
このような手法で変換されたプログラムをターゲットハードウェア２００が実行したとしても、図１２に示すようなスレッドの割り当てがなされる。
＜補足１＞
上記実施の形態において、本発明の実施の手法について説明してきたが、本発明の実施の形態がこれに限られないことは勿論である。以下、上記実施形態以外に本発明として含まれるその他の各種の変形例について説明する。
（１）上記実施の形態においては、とくに記載しなかったが、上記投機実行を実行するに当たって、以下の処理を加えた上で、上記投機実行を実行するか否かの判定を行い、肯定的な判定を行った場合にのみ、上記投機実行を実行するという構成にしてもよい。
【００８３】
当該判定は、従来の場合と上記実施の形態に示す投機実行を実行する場合とで、実行時間が短縮できるか否かを判定することによって行われる。即ち、各実行経路についてＮＧケースとＯＫケースのそれぞれの実行時間を測定し、その実行経路を繰り返し数実行する分だけ従来の場合と本発明の投機実行を行った場合とでカウントして、比較することで行う。ＮＧケースが極端に短時間で済む場合には、投機実行の効果が得られない場合があるので、その場合に対応してこの処理を含む構成としてもよい。
【００８４】
即ち、プログラム変換装置１００の最適化部１０２は、ソースプログラムを実行プログラムに変換する過程において、（ａ）ターゲットハードウェア２００にコミット処理がされた場合の実行時間と、されなかった場合の実行時間とを取得させる処理と、（ｂ）コミット処理がされた場合の実行時間とされなかった場合の実行時間との差分を求める処理と、（ｃ）当該差分が所定の閾値以上であるか否かを判定させる処理と、（ｄ）差分が所定の閾値以上である場合に、オリジナルパスを繰り返し処理の回数目を異ならせて各スレッドに割り当てて実行させ、差分が所定の閾値以下である場合に、上記実施の形態１や各変形例で示した投機実行をさせる処理とを付加し、コード変換部１０３が変換して実行プログラム３０を生成、出力する構成をとることとしてもよい。
【００８５】
当該実行プログラム３０をターゲットハードウェアが実行すると、上記実施の形態１や各種変形例に示した投機実行の効果が見込める場合にのみ、その投機実行を行うため、処理の効率を高めることができる。
（２）上記実施の形態においては、ソースプログラムをそのまま最適化等を行わずに生成した命令列を、実際にターゲットハードウェアに実行させることにより、実行頻度情報を取得することとした。
【００８６】
しかし、ソースプログラムによっては、プログラマ自身が、各実行経路の事項頻度を想定することができる場合もある。このような場合には、プログラマがソースプログラム中に予め実行頻度に関する情報を記載しておくことで、ターゲットハードウェアにソースプログラムを最適化せずに生成した命令列を実行させて実行頻度情報を取得せずとも、ソースプログラム１０を、そのまま実行形式に変換して実行経路の実行頻度情報を出力する処理を含む実行プログラム３０をターゲットハードウェア２００に実行させて実行頻度情報を得ることなく、入力された最初から図３のフローチャートに示す手順に従って最適化処理と、投機実行処理を行う命令列を生成する構成としてもよい。
【００８７】
ソースプログラム中に実行頻度情報を埋め込む一例としては、例えば、pragma指令を用いるという構成で行えばよい。例えば、図１６に示すフローグラフの各分岐が、例えば図１４に示すような分岐確率を有するとする。図１４のフローグラフ中の分岐においてブロック間を実線の矢印で結んだ経路が真、破線の矢印で結んだ経路が偽となっている。この分岐確率が予めわかる、予想できる場合には、図１５に示すソースプログラム例のように、pragma指令を用いて、その分岐が真となる確率を指定してもよい。なお、図１５中、ＩやＪなどで示されるブロックは、それぞれ図１４のフローグラフのブロックＩ、Ｊに対応する。
（３）上記実施の形態の変形例１−１〜３−２においては、ステップＳ５０３において追加した判定処理や、ステップＳ５０４、Ｓ７０１、Ｓ８０４、Ｓ１１０４における判定処理において、繰り返し数が所定数以下になったかどうかを判断基準として設定、あるいは、判定しているが、これは、実行していない実行経路の実行頻度の合計を判断基準とする構成にしてもよい。つまり、ステップＳ５０３で言えば、実行された各実行経路の実行頻度情報で示される実行頻度の割合の合計が、所定の割合を超えているかを判定させる処理を付加することとし、ステップＳ５０４、Ｓ７０１、Ｓ８０４、Ｓ１１０４においては、実行済みの実行経路の実行頻度情報で示される実行頻度の合計が所定の割合を超えているかを判定することとしてもよい。
（４）上記実施の形態においてはフローグラフの繰り返し回数を１０回としたが、これは当然この回数に限定されるものではなく、ソースプログラム１０にプログラマが記載した回数により任意であり、５回であっても１００回であってもよい。
（５）上記実施の形態においては、ターゲットハードウェア２００は、４つのプロセッサを備え、４つのスレッドを同時に並列実行できるハードウェアであるとして説明したが、当該並列実行可能なスレッドの個数は４に限定されるものではなく、２以上のスレッドを並列実行できるものであればよく、例えば、ターゲットハードウェア２００は、３つのプロセッサを備えて３つのスレッド同時に並列実行できるものであってもよい。
（６）上記実施の形態においては、例えば、図１６に示すようなフローグラフで示される処理が繰り返し実行されるものとして説明したが、本発明は、図１６に示すフローグラフが繰り返し実行されるのではなく、ソースプログラム１０中において、図１６に示すフローグラフと同じ構成の処理が各所に点在する場合において、これを投機実行する場合においても有効である。
（７）上記実施の形態においては特に記載しなかったが、繰り返し処理の中の処理を各スレッドに割り振る処理や、残りの処理数が所定数以下になっているかの処理などは、スレッド１〜４を担当するいずれかのプロセッサが実行することとしてもよいし、これらのプロセッサとは異なるターゲットハードウェア２００に備えられている別のプロセッサが実行することとしてもよい。
（８）上述の実施形態で示したコンパイリングに係る動作等（図２、図３、図５、図７、図８、図１０、図１１、図１３等参照）をコンパイラ、プログラム変換装置等のプロセッサ、及びそのプロセッサに接続された各種回路に実行させるためのプログラムコードからなる制御プログラムを、記録媒体に記録すること、又は各種通信路等を介して流通させ頒布させることもできる。このような記録媒体には、ＩＣカード、ハードディスク、光ディスク、フレキシブルディスク、ＲＯＭ等がある。流通、頒布された制御プログラムはプロセッサに読み出され得るメモリ等に格納されることにより利用に供され、そのプロセッサがその制御プログラムを実行することにより、実施形態で示したような各種機能が実現されるようになる。
＜補足２＞
以下に本発明に係るプログラム変換装置の一実施態様とその効果について説明する。
【００８８】
本発明は、始点と終点とを同じくする複数の実行経路を含む区間を複数回繰り返す繰り返し処理をプロセッサに実行させる処理を含むソースプログラムを、複数のプロセッサに並列に投機実行させるための実行プログラムに変換するプログラム変換装置であって、前記複数の実行経路夫々について、当該実行経路を最適化し、コミット処理、及び、コミット処理がされたか否かを示すコミット処理情報を出力する処理を付加した第１コードを生成する第１コード生成手段と、生成された複数の第１コードのうち、最も実行頻度の高い実行経路に対応する第１コードを前記繰り返し処理における回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第１割当コードを生成する第１割当コード生成手段と、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理を、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第２割当コードを生成する第２割当コード生成手段とを備えることを特徴とする。
【００８９】
ここでいう第１コードは、上記実施の形態１で示した図３のステップＳ３０２及びステップＳ３０３において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第１割当コードは、上記実施の形態１の図３のステップＳ３０４において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第２割当コードは、上記実施の形態１の図３のステップＳ３０８において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。
【００９０】
上記構成により、プログラム変換装置が生成する各コードを複数のプロセッサに実行させることにより、最も実行頻度の高い実行経路から繰り返し処理の繰り返し数分だけ並列に、その繰り返し数の回数目を異ならせて投機実行され、以降、コミット処理がなされなかった処理の分だけ、実行頻度を下げていきながら、各実行経路を並列に投機実行させることができる。
【００９１】
これにより、実行頻度が２番目に高い実行経路以降の実行経路については、既に、コミット処理がされている分についての処理を、並列投機実行することがなくなるため、その分の処理時間を短縮することができ、従来よりもプログラムの総実行時間を短縮することができる。
【００９２】
また、前記プログラム変換装置は、更に、前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、コミット処理がされていない回数目の処理の分だけ、前記複数のプロセッサのうちの１つのプロセッサにのみ割り当てて実行させる第２割当コードを生成することとしてもよい。
【００９３】
ここで第１判定コードは、上記実施の形態１変形例１−１の図５のステップＳ５０２において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第２割当コードは、上記実施の形態１変形例１−１のステップＳ５０４において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。
【００９４】
これにより、コミット処理がされていない処理の回数が所定数以下になった場合、即ち、少なくなってきた場合には、以降の未実行の実行経路についての処理を全スレッドに割り振るのではなく１つのスレッドに割り振らせることにより、プログラム変換装置が生成する実行形式のプログラムを実行するハードウェア上において投機実行する際に用いていたスレッドを解放することができ、当該ハードウェアは解放されたスレッドにその他の処理を割り振ることができる。コミット処理がされていない処理の回数が少なくなってきた場合には、投機実行により得られる処理時間の短縮化の効果が低減するため、１つのスレッドに処理を割り当てる構成にすることにより、ハードウェア上で実行される様々な処理の高効率化を図ることができる。
【００９５】
また、前記プログラム変換装置は、更に、前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、実行されていない実行経路に対応する第１コードをそれぞれ別のプロセッサに割り当て、コミット処理がされていない回数目の処理の分だけ実行させる第２割当コードを生成することとしてもよい。
【００９６】
ここでいう、第１判定コードは、上記実施の形態１変形例２−１の図８のステップＳ５０２において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第２割当コードは、上記実施の形態１変形例２−１の図８のステップＳ８０４において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。
【００９７】
これにより、コミット処理がされていない処理の回数が所定数以下になった場合、即ち、少なくなってきた場合には、以降の未実行の実行経路それぞれを最適化して、各実行経路を並列的に実行するのではなく、１つのプロセッサに実行させることで、処理効率を向上させることができることがある。
【００９８】
また、前記プログラム変換装置は、更に、前記繰り返し処理においてコミット処理がされていない処理の回数が所定数以下であるか否かを判定させる第１判定コードを生成する第１判定コード生成手段を備え、前記第２割当コード生成手段は、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数よりも大きかった場合にのみ、実行されていない実行経路のうち、最も実行頻度の高い実行経路に対応する第１コードを、前記コミット処理情報に基づき、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させ、前記第１判定コードに基づく判定の結果、コミット処理がされていない処理の回数が所定数以下であった場合には、前記区間をそのまま実行形式に変換したオリジナルパスコードを、コミット処理がされていない回数目の処理について、その回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第２割当コードを生成することとしてもよい。
【００９９】
ここでいう、第１判定コードは、上記実施の形態１変形例３−１の図１１のステップＳ５０２において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第２割当コードは、上記実施の形態１変形例３−１の図１１のステップＳ１１０４において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。
【０１００】
これにより、コミット処理がされていない処理の回数が所定数以下になった場合、即ち、少なくなってきた場合には、以降の未実行の実行経路ではなく、複数回実行される区間をそのまま実行形式に変換したプログラムを並列に実行させることで、処理効率を向上させることができることがある。
【０１０１】
また、前記プログラム変換装置は、更に、前記投機実行される実行経路の実行頻度及び実行時間に基づいて、前記第１割当コード及び前記第２割当コードを実行するか否かを判定させる第２判定コードを生成する第２判定コード生成手段と、前記第１割当コード及び前記第２割当コードを実行しないと判定された場合に、前記区間をそのまま実行形式に変換したオリジナルパスコードを、前記繰り返し処理における回数目を異ならせて前記複数のプロセッサに割り当てて実行させる第３割当コードを生成する第３割当コード生成手段とを備える
こととしてもよい。
【０１０２】
そして、前記第２判定コード生成手段は、前記実行時間として、前記投機実行の対象である実行経路が選択されたときの実行時間と、選択されなかったときの実行時間とに基づいて判定させる前記第２判定コードを生成することとしてもよい。
【０１０３】
ここで、第２判定コードは、上記＜補足１＞の（１）の（ｂ）、（ｃ）において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。また、第３割当コードは、上記＜補足１＞の（１）の（ｄ）において最適化部１０２が付加した処理をコード変換部１０３が実行コードに変換することにより生成される。
【０１０４】
投機実行する処理の内容によっては、コミット処理がされる場合とされない場合とで、実行時間が異なり、コミット処理がされない処理の実行時間が短い場合などには、本発明に係る投機実行を行っても実行時間を短縮できない場合があり、当該構成を備えることにより、そのような場合において、本発明の投機実行を行うことを回避することができる。
【産業上の利用可能性】
【０１０５】
本発明に係るコンパイラの最適化技術は、投機実行可能なプロセッサにおいて、プロセッサの処理の高速化並びにスレッドの有効活用において有用である。
【符号の説明】
【０１０６】
１００  プログラム変換装置
１０１  解析部
１０２  最適化部
１０３  コード変換部
２００  ターゲットハードウェア
【図１】
2012043128.tif 000003
【図２】
2012043128.tif 000004
【図３】
2012043128.tif 000005
【図４】
2012043128.tif 000006
【図５】
2012043128.tif 000007
【図６】
2012043128.tif 000008
【図７】
2012043128.tif 000009
【図８】
2012043128.tif 000010
【図９】
2012043128.tif 000011
【図１０】
2012043128.tif 000012
【図１１】
2012043128.tif 000013
【図１２】
2012043128.tif 000014
【図１３】
2012043128.tif 000015
【図１４】
2012043128.tif 000016
【図１５】
2012043128.tif 000017
【図１６】
2012043128.tif 000018
【図１７】
2012043128.tif 000019
【図１８】
2012043128.tif 000020