(57)【要約】【課題】動的分岐予測方式を実現するためには複雑なハードウェア分岐予測機構が必要となるが、プロセッサコアの複雑化を招く。一方、ハードウェア分岐予測機構を用いない静的分岐予測方式では予測精度が低くなりがちである。【解決手段】分岐処理を含むソフトウェアのうち分岐命令を特定する手順、分岐ヒント命令を前記分岐命令の前に実行されるべき位置に挿入し、前記分岐命令の分岐のうち第1の分岐判断をした場合に実行されるべき位置に第1の分岐後処理コードを挿入し、前記分岐命令の分岐のうち第２の分岐判断をした場合に実行されるべき位置に第２の分岐後処理コードを挿入し、オブジェクトコードを生成する手順、を実行させる。【選択図】図８
2008107913.tif 000002
【特許請求の範囲】
【請求項１】
分岐処理を含むソフトウェアを、コンピュータが実行可能なオブジェクトコードに変換する装置としてコンピュータを機能させるためのプログラムであって、
前記ソフトウェアのうち分岐命令を特定する手順、
分岐ヒント命令を前記分岐命令の前に実行されるべき位置に挿入し、前記分岐命令の分岐のうち第1の分岐判断をした場合に実行されるべき位置に第1の分岐後処理コードを挿入し、前記分岐命令の分岐のうち第２の分岐判断をした場合に実行されるべき位置に第２の分岐後処理コードを挿入し、前記オブジェクトコードを生成する手順、
を実行させるためのプログラム。    
【請求項２】
分岐処理を含むソースプログラムを、コンピュータが実行可能なオブジェクトコードに変換する装置としてコンピュータを機能させるためのプログラムであって、
前記ソースプログラムを機械語に翻訳する手順、
機械語に翻訳された前記ソースプログラムのうち分岐命令を特定する手順、
分岐ヒント命令を前記分岐命令の前に実行されるべき位置に挿入し、前記分岐命令の後に実行されるべき位置に分岐予測処理用コードを挿入し、前記オブジェクトコードを生成する手順、
を実行させるためのプログラム。
【請求項３】
分岐処理を含むソフトウェアを、変換する装置としてコンピュータを機能させるためのプログラムであって、
前記ソフトウェアのうち分岐命令を特定する手順、
前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に、
前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を挿入する手順、
前記分岐命令の後に実行されるべき位置に、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令である分岐予測処理用コードを挿入し、オブジェクトコードを生成する手順、
を実行させるためのプログラム。
【請求項４】
前記分岐先格納レジスタに格納されている前記分岐先アドレスは、
分岐成立・分岐不成立に応じて書き換えられる予測状態値と、
所定の閾値に対する前記予測状態値の大小関係が大小のうちの一方である場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスと、
前記所定の閾値に対する前記予測状態値の大小関係が大小のうちの他方である場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスと、
に関連付けて格納され、
前記分岐予測処理用コードは、
分岐成立・分岐不成立に応じて前記予測状態値を書き換える手順と、
前記所定の閾値に対する前記予測状態値の大小関係が大小のうちの前記一方である場合に前記分岐成立時分岐先アドレスを前記分岐先格納レジスタに書き込み、前記所定の閾値に対する前記予測状態値の大小関係が大小のうちの前記他方である場合に前記分岐不成立時分岐先アドレスを前記分岐先格納レジスタに書き込む手順と、
を示すコードであることを特徴とする請求項３記載のプログラム。
【請求項５】
前記分岐先格納レジスタに格納されている前記分岐先アドレスは、
２ビットの予測状態値と、
前記予測状態値の上位ビットが、１と０とのうちの一方である場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスと、
前記予測状態値の上位ビットが、１と０とのうちの他方である場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスと、
に関連付けて格納され、
前記分岐予測処理用コードは、
分岐成立である場合に前記予測状態値に、インクリメントおよびディクリメントのうちの一方をし、分岐不成立である場合に前記予測状態値にインクリメントおよびディクリメントのうちの他方をする手順と、
前記予測状態値の上位ビットが１と０のうちの前記一方である場合に前記分岐成立時分岐先アドレスを前記分岐先格納レジスタに書き込み、予測状態値の上位ビットが１と０のうちの前記他方である場合に前記分岐不成立時分岐先アドレスを前記分岐先格納レジスタに書き込む手順と、
を示すコードであることを特徴とする請求項３記載のプログラム。
【請求項６】
分岐処理を含むソフトウェアを、ＳＩＭＤ命令をサポートしＳＩＭＤレジスタを有するプロセッサを備えるコンピュータが実行可能なオブジェクトコードに変換する装置として、コンピュータを機能させるためのプログラムであって、
前記ソフトウェアのうち分岐命令を特定する手順、
前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を挿入する手順、
分岐成立・分岐不成立に応じて書き換えられる予測状態値と、前記予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスと、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスと、前記分岐先格納レジスタと、を格納するＳＩＭＤレジスタに対するＳＩＭＤ命令であって前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令であるＳＩＭＤ命令を、前記分岐命令の後に実行されるべき位置に挿入する手順、
を経て前記オブジェクトコードの生成を実行させるためのプログラム。
【請求項７】
前記分岐先格納レジスタで示される第1のｂｉｔ列と、前記予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスを表す第２のｂｉｔ列と、分岐成立・分岐不成立に応じて書き換えられる前記予測状態値を表す第３のｂｉｔ列と、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスを表す第４のｂｉｔ列と、を前記ＳＩＭＤレジスタの上位ビットに該当する要素から順に並べて格納させる手順を更に含むことを特徴とする請求項６記載のプログラム。
【請求項８】
前記分岐先格納レジスタで示される第1のｂｉｔ列を、前記ＳＩＭＤレジスタの要素に格納させ、
前記ＳＩＭＤレジスタの前記第１のｂｉｔ列を格納させた要素よりも下位のビットに該当する要素に、前記予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスを表す第２のｂｉｔ列と、分岐成立・分岐不成立に応じて書き換えられる前記予測状態値を表す第３のｂｉｔ列と、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスを表す第４のｂｉｔ列と、を並べて格納させる手順を更に含むことを特徴とする請求項６記載のプログラム。
【請求項９】
ＳＩＭＤレジスタに所定の値を書き込ませる装置として、ＳＩＭＤ命令をサポートし前記ＳＩＭＤレジスタを有するプロセッサを備えるコンピュータを機能させるためのプログラムであって、
分岐命令の前に実行されるべき位置に挿入され、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を実行する手順、
分岐成立・分岐不成立に応じて書き換えられる予測状態値と、前記予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスと、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスと、前記分岐先格納レジスタと、を格納するＳＩＭＤレジスタに対するＳＩＭＤ命令であって、前記分岐命令の後に実行されるべき位置に挿入され、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令であるＳＩＭＤ命令を実行する手順、
を実行させるためのプログラム。
【請求項１０】
分岐処理を含むソフトウェアを、コンピュータが実行可能なオブジェクトコードに変換するソフトウェア変換装置であって、
前記ソフトウェアのうち分岐命令を特定し、前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を挿入し、前記分岐命令の後に実行されるべき位置に、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令である分岐予測処理用コードを挿入し、オブジェクトコードを生成するプロセッサと、
前記ソフトウェアと前記オブジェクトコードとを記憶する記憶部と、
を備えるソフトウェア変換装置。
【請求項１１】
ＳＩＭＤ命令をサポートするプロセッサを備え、分岐処理を含むソフトウェアから生成されたオブジェクトコードを実行するコンピュータであって、
分岐先格納レジスタで示される第1のｂｉｔ列を格納し、更に該第１のｂｉｔ列よりも下位のビットに該当する要素に、分岐成立・分岐不成立に応じて書き換えられる予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスを格納する第２のｂｉｔ列と、前記予測状態値を格納する第３のｂｉｔ列と、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスを格納する第４のｂｉｔ列と、を並べて格納するＳＩＭＤレジスタと、
前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に挿入され、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている前記分岐先格納レジスタとを含む分岐ヒント命令と、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令であるＳＩＭＤ命令と、を実行するプロセッサと、
を備えることを特徴とするコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プロセッサにおける分岐予測方式、及びそれに係るにプログラム、コンパイル装置、オブジェクトコード変換装置、及びコンピュータに関する。
【背景技術】
【０００２】
分岐命令では、厳密には、分岐結果が確定するまで次の命令を実行することが出来ない。分岐命令に後続する処理は停めてしまうのでは、前段の処理結果を用いるいわゆるパイプライン処理を行うプロセッサは、その特徴が生かせない。
【０００３】
これを避けるために、分岐命令の分岐結果を事前に予測する分岐予測処理が従来から行なわれている。具体的には、分岐予測処理で決定した仮の分岐判断を基に、分岐命令に後続する命令を実行して仮の演算結果を求めておく。その後に行われる実際の分岐判断が仮の分岐判断と一致（すなわち分岐ヒット）すれば、仮の演算結果を用いる。また、実際の分岐判断が仮の分岐判断と異なる（すなわち分岐ミス）となれば改めて実際の分岐判断に基づいて、後続する命令の結果を求めるのである。これにより、命令の実行を止める必要がなくなり、性能低下を抑制出来る。
【０００４】
分岐予測処理のひとつが、静的分岐予測方式である。プログラムの実行前に分岐命令の分岐結果を予測する静的分岐予測方式では、プロファイリングを用いる場合がある。プロファイリングを用いた方式では、テストデータを用いてプログラムを事前に試行し、プロファイル情報（各分岐命令の分岐結果）を取得する。プロファイル情報を基にコンパイラが各分岐命令の予測値を決定したプログラムを再び生成することで分岐予測処理を実現する。
【０００５】
分岐予測処理として他に、動的分岐予測方式がある。プログラムの実行中に分岐結果を予測する動的分岐予測方式では、プロセッサが持つハードウェアによる分岐予測機構によって予測が行われる。分岐予測機構は、プログラムの実行中に分岐結果を分岐履歴情報として分岐予測テーブルに記録する。予測テーブルに記録された分岐履歴情報に基づいて、次回の分岐結果の予測を行うことで分岐予測処理を実現する。
【０００６】
一般的な動的分岐予測方式では、各分岐命令に２ビットの分岐履歴情報を用いる。２ビット分岐履歴情報は、予測される分岐先アドレスと合わせて分岐予測テーブルの１つのエントリに格納される。２ビット分岐履歴情報は、例えば以下のように予測状態を２ビットに対応させる。予測値’００’，’０１’，’１０’，’１１’，にそれぞれ、高い確率で分岐不成立，低い確率で分岐不成立，低い確率で分岐成立，高い確率で分岐成立、の予測結果を割り当てる。
【０００７】
分岐予測は、分岐命令を実行する毎に、その分岐結果に応じて予測状態を遷移させ、予測状態に基づき分岐結果を予測する。状態遷移は、分岐結果が分岐成立なら予測値をインクリメントし、不成立ならディクリメントすることで行われる状態遷移の結果、予測状態が’００’、’０１’となった場合には分岐不成立、予測状態が‘１０’、‘１１’となった場合には、分岐成立となるはずだと予測する。
【非特許文献１】John L. Hennessy, David A. Patterson, “Computer Architecture. A Quantitative Approach, Third Edition, Morgan Kaufmann, 2003, pp. 196-200.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記動的分岐予測方式を実現するためには複雑なハードウェア分岐予測機構が必要となる。
【０００９】
しかし、プロセッサの低消費電力化およびマルチコア化を行う際には、ハードウェア分岐予測機構を省き、プロセッサコアのシンプル化を図ることが必要となる。
【００１０】
一方、ハードウェア分岐予測機構を用いない静的分岐予測方式ではコンパイル時に予測が固定されてしまうため、実行時にならないと分岐結果が確定しない場合などに対応出来ず予測精度が低くなりがちである。
【課題を解決するための手段】
【００１１】
本発明は、分岐処理を含むソフトウェアを、コンピュータが実行可能なオブジェクトコードに変換する装置としてコンピュータを機能させるためのプログラムであって、前記ソフトウェアのうち分岐命令を特定する手順、分岐ヒント命令を前記分岐命令の前に実行されるべき位置に挿入し、前記分岐命令の分岐のうち第1の分岐判断をした場合に実行されるべき位置に第1の分岐後処理コードを挿入し、前記分岐命令の分岐のうち第２の分岐判断をした場合に実行されるべき位置に第２の分岐後処理コードを挿入し、前記オブジェクトコードを生成する手順、を実行させるためのプログラムを提供する。
【００１２】
また本発明は、ＳＩＭＤレジスタに所定の値を書き込ませる装置として、ＳＩＭＤ命令をサポートし前記ＳＩＭＤレジスタを有するプロセッサを備えるコンピュータを機能させるためのプログラムであって、分岐命令の前に実行されるべき位置に挿入され、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を実行する手順、分岐成立・分岐不成立に応じて書き換えられる予測状態値と、前記予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレス、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスと、前記分岐先格納レジスタと、を格納するＳＩＭＤレジスタに対するＳＩＭＤ命令であって、前記分岐命令の後に実行されるべき位置に挿入され、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令であるＳＩＭＤ命令を実行する手順、を実行させるためのプログラムを提供する。
【００１３】
また本発明は、分岐処理を含むソフトウェアを、コンピュータが実行可能なオブジェクトコードに変換するソフトウェア変換装置であって、前記ソフトウェアのうち分岐命令を特定し、前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと、前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている分岐先格納レジスタと、を含む分岐ヒント命令を挿入し、前記分岐命令の後に実行されるべき位置に、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令である分岐予測処理用コードを挿入し、オブジェクトコードを生成するプロセッサと、前記ソフトウェアと前記オブジェクトコードとを記憶する記憶部と、を備えるソフトウェア変換装置を提供する。
【００１４】
また本発明は、ＳＩＭＤ命令をサポートするプロセッサを備え、分岐処理を含むソフトウェアから生成されたオブジェクトコードを実行するコンピュータであって、分岐先格納レジスタで示される第1のｂｉｔ列を格納し、更に該第１のｂｉｔ列よりも下位のビットに該当する要素に、分岐成立・分岐不成立に応じて書き換えられる予測状態値が所定の閾値より大きい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐成立時分岐先アドレスを格納する第２のｂｉｔ列と、前記予測状態値を格納する第３のｂｉｔ列と、前記予測状態値が前記所定の閾値より小さい場合に前記分岐先格納レジスタに書き込まれるべき値である分岐不成立時分岐先アドレスを格納する第４のｂｉｔ列と、を並べて格納するＳＩＭＤレジスタと、前記ソフトウェアのなかの前記分岐命令の前に実行されるべき位置に挿入され、前記分岐命令が記憶されるアドレスである対象分岐命令アドレスと前記分岐命令の結果として仮に選択されるべき分岐先アドレスが格納されている前記分岐先格納レジスタとを含む分岐ヒント命令と、前記分岐先格納レジスタに格納されている分岐先アドレスを変更する命令であるＳＩＭＤ命令と、を実行するプロセッサと、を備えることを特徴とするコンピュータを提供する。
【発明の効果】
【００１５】
本発明によって、オブジェクトコードに動的分岐予測処理を組み込んで、プロセッサが実行する際に動的に分岐処理をさせることが可能となる。
【発明を実施するための最良の形態】
【００１６】
本実施の形態のコンパイラやオブジェクトコードを実行する計算機の一例を、図１を参照して説明する。
【００１７】
計算機は、例えば、プロセッサ１０１、一時記憶装置１０２、データ転送装置１０３、主記憶装置１０４、バス１０５、入出力装置１０６を備えている。
【００１８】
プロセッサ１０１は、入出力装置１０６から主記憶装置１０４に入力したデータを、一時記憶装置１０２、データ転送装置１０３、バス１０５を介して受け取り、データに含まれる命令に従って演算操作を実行する。
【００１９】
一時記憶装置１０２は、一時的な、過渡的なデータを記憶するための装置である。一時記憶装置１０２は、プロセッサ１０１と主記憶装置１０４との間に配置される。一時記憶装置１０２は、主記憶装置１０４からプロセッサ１０１へのデータの読み込みを高速化する。一時記憶装置１０２は、具体的には、例えば、キャッシュやローカルメモリである。後述するコンパイラはこの一時記憶装置１０２にロードされる。また、オブジェクトコードを実行する場合はオブジェクトコード自体やそれに係るデータの類（分岐予測テーブルなど）を記憶する。
【００２０】
データ転送装置１０３は、一時記憶装置１０２と主記憶装置１０４との間でデータ転送を行う。
【００２１】
主記憶装置１０４は、計算機に搭載されている記憶装置の中で、プロセッサ１０１が処理するデータが配置される装置である。主記憶装置１０４は、例えば、ＯＳ（オペレーティングシステム）、アプリケーション、データ、周辺機器を制御するドライバなどを読み込む。
【００２２】
バス１０５は、計算機の各構成装置間で命令やデータを転送するための伝送路である。バス１０５は、データ転送装置１０３、主記憶装置１０４、入出力装置１０６の間で命令やデータの転送を行う。
【００２３】
入出力装置１０６は、例えばメディアドライブや、ネットワークインタフェースといった、計算機の外部とのデータやソフトウェアの入出力を行うための装置である。
【００２４】
次に、図１の計算機で実行されるソフトウェアとプログラムの関係を図２に示す。
【００２５】
本発明は、最終的にオブジェクトコードとして得たいソフトウェアのソースプログラム２０１が、計算機上で実行されるソフトウェアであるコンパイラ２０２に処理されて生成される、オブジェクトコード２０３によって実現される。
【００２６】
コンパイラ２０２は分岐最適化部２０４を含む。分岐最適化部２０４は、ソースプログラム２０１に分岐ヒント命令２０５と分岐予測処理用コード２０６を挿入する。
【００２７】
オブジェクトコード２０３は、分岐ヒント命令２０５、分岐予測処理用コード２０６を含む。
【００２８】
分岐予測処理用コード２０６は、オブジェクトコード２０３の実行時に同時に処理され、分岐予測処理を行う。さらに、その予測結果を分岐予測ヒント命令２０５が利用できるように設定する。
【００２９】
分岐ヒント命令２０５は、その後の分岐命令の振舞い（分岐判断）を制御するための命令である。図３にその一例を示す。
【００３０】
分岐ヒント命令２０５は、分岐ヒント命令自身を表すオペコード３０１と分岐ヒント命令に設定する分岐ヒント情報３０５から構成される。分岐ヒント情報３０５は、対象分岐命令アドレス３０２と分岐先格納レジスタ３０３から構成される。
【００３１】
対象分岐命令アドレス３０２は、分岐ヒント命令２０５の後の、ヒント対象（分岐予測対象）である分岐命令を特定するためのものである。対象分岐命令アドレス３０２は、対象の分岐命令を特定出来る値であればよく、例えば分岐ヒント命令２０５から分岐命令への相対アドレスの形式で指定する。
【００３２】
分岐先格納レジスタ３０３は、ヒント対象の分岐命令の仮の分岐先が格納されているレジスタを指すものである。分岐先格納レジスタ３０３は、分岐先アドレスを特定出来る値であればよく、例えば分岐命令の分岐先アドレスを指定する。
【００３３】
図４に、分岐予測処理用コード２０６の構成例を示す。分岐予測処理用コード２０６は、分岐成立時処理コード４０１と分岐不成立時処理コード４０２を含む。分岐成立時処理コード４０１と分岐不成立時処理４０２は、共通の分岐予測テーブル４０３を操作するコードである。
【００３４】
図５に、分岐予測テーブル４０３の構成例を示す。分岐予測テーブル４０３は、分岐予測情報５０１を複数記録する。分岐予測テーブル４０３の各エントリは、分岐命令に一対一対応している。つまりエントリ５０２はある分岐命令に対応し、エントリ５０３が別の分岐命令に対応する。分岐成立時処理コード４０１および分岐不成立時処理コード４０２は、分岐命令ごとに対応するテーブルエントリを選択し、分岐予測情報を操作する。
【００３５】
各テーブルエントリ（分岐予測情報５０１）は、複数の分岐命令に対応してもよい。この場合は、複数の分岐命令（例えばプログラム全体）に跨る分岐結果の傾向から分岐予測が出来るようになる。
【００３６】
図６に、分岐予測情報５０１の一例として、２ビット分岐履歴情報を用いた動的分岐予測方式を利用する場合を示す。
【００３７】
分岐予測情報５０１は、分岐予測結果６０２、２ビット予測状態６０３、分岐成立時分岐先アドレス６０４、分岐不成立時分岐先アドレス６０５から構成される。
【００３８】
分岐予測結果６０２は、予測結果の分岐先アドレスを格納するための要素である。
【００３９】
２ビット予測状態６０３は、２ビット分岐履歴情報を格納するための要素である。よって、２ビット予測状態６０３は、’００’，’０１’，’１０’，’１１’のいずれかの２進数の値を格納する。
【００４０】
分岐成立時アドレス６０４は、分岐が成立する場合の分岐先アドレスを格納する。
【００４１】
分岐不成立時アドレス６０５は、分岐が不成立の場合の分岐先アドレスを格納する。
【００４２】
２ビット予測状態６０３は、分岐成立時処理コード４０１および分岐不成立時処理コード４０２によるテーブルエントリ操作時に更新する。更新結果に基づいて次の分岐結果を予測する。予測結果が成立の場合は、分岐成立時アドレス６０４の値で分岐予測結果６０２を更新する。不成立の場合、分岐不成立時アドレス６０５の値で更新する。
【００４３】
図７に例示する分岐予測情報５０１は、２ビット予測状態７０３が’０１’の場合を表わしている。次に、分岐成立時処理コードによる操作を行う場合には、２ビット予測状態７０３は’１０’に更新される。’１０’は分岐成立に対応するので、分岐成立時アドレス７０４の値０ｘ１００で分岐予測結果７０２を更新する。また、分岐不成立時処理コードによる操作を行う場合には、２ビット予測状態７０３は’００’に更新される。’００’は分岐不成立に対応するので、分岐不成立時アドレス７０５の値０ｘ３０４で分岐予測結果７０２を更新する。
【００４４】
図８に、分岐最適化部２０４による分岐ヒント命令２０５と分岐予測処理用コード２０６の挿入例を示す。
【００４５】
図８（ａ）は、挿入がされない場合のオブジェクトコード２０３が実行される際の処理フローである。
【００４６】
分岐命令８０１の分岐結果に依って、分岐結果が成立の場合はコードブロックＡ８０２が実行される。逆に、不成立だった場合はコードブロックＢ８０３が実行される。この処理が繰り返し実行される。
【００４７】
図８（ｂ）は、分岐ヒント命令２０５、分岐成立時処理コード４０１、分岐不成立時処理コード４０２を挿入した場合のオブジェクトコード２０３が実行される際の処理フローである。分岐ヒント命令２０５は分岐命令８０１の前に挿入される。分岐予測処理用コード２０６は分岐命令８０１の後に挿入される。分岐結果が成立するフロー中に分岐成立時処理コード４０１を、不成立のフロー中に分岐不成立時処理コード４０２を挿入する。
【００４８】
このように分岐ヒント命令２０５と分岐予測処理用コード２０６が挿入されたオブジェクトコード２０３による処理全体の処理フローを図９に示す。
【００４９】
図９（ａ）は、オブジェクトコード２０３が実行される際に、分岐命令８０１の結果が分岐成立となり、分岐成立時処理コード４０１が実行される場合の処理フローである。なおこのフローは図８（ｂ）の分岐の左側に対応する。
【００５０】
はじめに、分岐命令に対応する分岐予測テーブルエントリの分岐予測情報５０１の２ビット予測状態６０３をインクリメントする（ステップ９０１）。
【００５１】
次に、分岐予測結果を得るために、インクリメントした２ビット予測状態の値と２進数１０との論理積をとる（ステップ９０２）。論理積の結果が００の場合は、次回は分岐不成立と予測し、１０の場合は分岐成立と予測する。  
・‘００’の場合、’１０’との論理積が’００’で、分岐不成立
・‘０１’の場合、’１０’との論理積が’００’で、分岐不成立
・‘１０’の場合、’１０’との論理積が’１０’で、分岐成立
・‘１１’の場合、’１０’との論理積が’１０’で、分岐成立
【００５２】
次に、分岐予測結果を分岐予測テーブルエントリの分岐予測情報５０１の分岐予測結果６０２を、適切な分岐先アドレスで更新する（ステップ９０３）。予測結果が分岐成立の場合には、同エントリの分岐成立時分岐先アドレス６０４の値で更新する。不成立の場合、同エントリの分岐不成立時分岐先アドレス６０５の値で更新する。
【００５３】
図９（ｂ）は、オブジェクトコード２０３が実行される際に、分岐命令８０１の結果が分岐不成立となり、分岐不成立時処理コード４０２が実行される場合の処理フローである。なおこのフローは図８（ｂ）の分岐の右側に対応する。
【００５４】
はじめに、分岐命令に対応する分岐予測テーブルエントリの分岐予測情報５０１の２ビット予測状態６０３をディクリメントする（ステップ９０４）。
【００５５】
次に、予測結果を得るために、ディクリメントした２ビット予測状態と２進数１０との論理積をとる（ステップ９０５）。論理積の結果が００の場合は分岐不成立と予測し、１０の場合は分岐成立と予測する。
【００５６】
次に、分岐予測結果を分岐予測テーブルエントリの分岐予測情報５０１の分岐予測結果６０２を、適切な分岐先アドレスで更新する（ステップ９０６）。予測結果が分岐成立の場合には、同エントリの分岐成立時分岐先アドレス６０４の値で更新する。不成立の場合、同エントリの分岐不成立時分岐先アドレス６０５の値で更新する。
【００５７】
更新される分岐予測テーブルエントリの分岐予測結果６０２の値を分岐ヒント命令２０５が利用することで、分岐予測処理を実現出来る。
【００５８】
（ＳＩＭＤ命令およびＳＩＭＤレジスタを用いる例）
分岐予測処理の効率化および高速化を実現するための方法として、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令およびＳＩＭＤレジスタを用いる例について説明する。
【００５９】
ＳＩＭＤ命令とは、主にマルチメディア処理を高速化するための命令であり、プロセッサ１０１がそれに対応したハードウェア（ＳＩＭＤレジスタと呼ばれる）を備える場合に用いることができる。マルチメディア処理では、複数データに対して同一の演算を繰り返し行うことが多い。ＳＩＭＤ命令は、これら複数データに対する演算処理を一括処理する命令である。ＳＩＭＤ命令の種類には、算術演算命令、論理演算命令、飽和演算命令、シャッフル命令、シフトおよびローテート命令などがある。
【００６０】
ＳＩＭＤ命令は、ＳＩＭＤレジスタに格納された複数要素に対して処理を行う。ＳＩＭＤ命令をサポートするプロセッサは、一般に１２８ビットのレジスタを複数本持つ。各１２８ビットレジスタは、４つの３２ｂｉｔ値を要素としてそれぞれ保持することが出来る。
【００６１】
ＳＩＭＤ命令は、多くのプロセッサでサポートされている。ＳＩＭＤ命令セットの例としては、インテルのＩＡ３２アーキテクチャのＳＳＥ、ＣｅｌｌプロセッサのＳＰＥの命令セット、ＰｏｗｅｒＰＣアーキテクチャのＡｌｔｉＶｅｃ、ＳＰＡＲＣアーキテクチャのＶＩＳなどがある。
【００６２】
しかし、ＳＩＭＤ命令の種類やＳＩＭＤレジスタは、アーキテクチャによって大きく異なるため、一般論を示すのは難しい。このため、以下一例として、４つの要素データを格納するＳＩＭＤレジスタおよびＳＩＭＤ命令セットを示して説明する。
【００６３】
図１０に、ＳＩＭＤレジスタの一例を示す。
【００６４】
ＳＩＭＤレジスタ１００１は、４つの要素であるＡ１００２、Ｂ１００３、Ｃ１００４、Ｄ１００５から構成される。これら４つの要素は上位ビットから順に（図１０では左から右へ昇順に）Ａ１００２、Ｂ１００３、Ｃ１００４、Ｄ１００５として定義されるものである。ＳＩＭＤ命令以外の、単一要素に対して操作を行うスカラ命令（例えば分岐ヒント命令）では、オペランドにＳＩＭＤレジスタ１００１が指定された場合は、要素Ａ１００２を利用する。
【００６５】
図１１は、ＳＩＭＤ命令の一例を示すための図である。
【００６６】
図１１（ａ）では、ＳＩＭＤレジスタに格納された４つの要素に対して、論理積演算を行うＳＩＭＤ命令を示す。
【００６７】
ＳＩＭＤレジスタ１１０１には、００，０１，１０，１１という２進数の値が格納されている。ＳＩＭＤレジスタ１１０１の各要素に対し、２進数１０と論理積演算を行っている。その結果、ＳＩＭＤレジスタ１１０１の値は００，００，１０，１０となっている。
【００６８】
図１１（ｂ）では、ＳＩＭＤレジスタに格納された４つの要素に対して、飽和加算を行うＳＩＭＤ命令を示す。
【００６９】
ＳＩＭＤレジスタ１１０５には、００，０１，１０，１１という２進数の要素が格納されている。ＳＩＭＤレジスタ１１０５の各要素に対し、別のＳＩＭＤレジスタ１１０６の対応する要素と、飽和加算がなされている。その結果、ＳＩＭＤレジスタ１１０５の値は００，０１，１１，１１となっている。
【００７０】
図１１（ｃ）では、ＳＩＭＤレジスタに格納された４つの要素に対して、飽和減算を行うＳＩＭＤ命令を示す。
【００７１】
ＳＩＭＤレジスタには、ＳＩＭＤレジスタ１１０７に００，０１，１０，１１という２進数の値が格納されている。ＳＩＭＤレジスタ１１０７の各要素に対し、別のＳＩＭＤレジスタ１１０８の対応する要素と飽和減算がなされている。その結果、ＳＩＭＤレジスタ１１０７の値は００，００，１０，１１となっている。
【００７２】
図１１（ｄ）では、ＳＩＭＤレジスタに格納された４つの要素に対して、シャッフルＡを行うＳＩＭＤ命令を示す。
【００７３】
ＳＩＭＤレジスタ１１１０には、０ｘ０，０ｘ１００，０ｘ２００，０ｘ３００という１６進数の値が格納されている。シャッフルＡでは、ＳＩＭＤレジスタ１１１０の各要素をＳＩＭＤレジスタ１１１０の任意の要素から複製出来る。その結果、ＳＩＭＤレジスタ１１１０の値は０ｘ１００，０ｘ０，０ｘ３００，０ｘ２００となっている。
【００７４】
図１１（ｅ）では、ＳＩＭＤレジスタに格納された４つの要素データに対して、別のシャッフルＢを行うＳＩＭＤ命令を示す。
【００７５】
ＳＩＭＤレジスタ１１１１には、０ｘ３０４、０ｘ３０４、０ｘ０２、０ｘ１００という１６進数の値が格納されている。別のＳＩＭＤレジスタ１１１２には、０ｘ１００、０ｘ３０４、０ｘ３０４、０ｘ０２が格納されている。シャッフルＢでは、ＳＩＭＤレジスタ１１１１の各要素にＳＩＭＤレジスタ１１１１とＳＩＭＤレジスタ１１１２の対応する要素のいずれかを入れることが出来る。その結果、ＳＩＭＤレジスタ１１１１の値は０ｘ１００，０ｘ３０４，０ｘ０２，０ｘ１００となっている。
【００７６】
図１１（ｆ）では、ＳＩＭＤレジスタに格納された４つの要素に対して、ローテートを行うＳＩＭＤ命令を示す。
【００７７】
ＳＩＭＤレジスタ１１１４には、０ｘ０，０ｘ１００，０ｘ２００，０ｘ３００という１６進数の値が格納されている。ＳＩＭＤレジスタ１１１４の各要素に対し、ローテートを行う。左端からローテートアウトされた要素は右端にローテートインする。その結果、ＳＩＭＤレジス１１１４の値は０ｘ１００，０ｘ２００，０ｘ３００，０ｘ０となっている。
【００７８】
しかし、ＳＩＭＤ命令およびＳＩＭＤレジスタを利用すれば高速化出来るという反面、プロセッサがサポートするＳＩＭＤ命令の種類が限定されている。さらに、ＳＩＭＤレジスタの本数も有限であるため、効率よく利用する必要がある。この問題を解決しつつ予測処理をＳＩＭＤ命令およびＳＩＭＤレジスタを用いて効率化・高速化する手法を以下説明する。
【００７９】
具体的には、ＳＩＭＤ命令およびＳＩＭＤレジスタを用いて分岐予測テーブル４０３の操作を高速化する。そのために、分岐予測テーブル４０３の各エントリ５０１をＳＩＭＤレジスタ１００１に割り当てる。また、分岐予測テーブル４０３の操作にＳＩＭＤ命令を利用する。
【００８０】
その際に、ＳＩＭＤレジスタ本数を節約するために、ＳＩＭＤレジスタの４要素に分岐予測情報の４要素を適切に配置し、分岐予測テーブル４０３の各エントリ５０１を１本のＳＩＭＤレジスタで保持させる。
【００８１】
図１２に、ＳＩＭＤレジスタ１００１の４要素に対する分岐予測情報の４要素の配置を示す。
【００８２】
要素Ａ１００２に分岐予測結果６０２、要素Ｂ１００３に分岐成立時分岐先アドレス６０４、要素Ｃ１００４に２ビット予測状態６０３、要素Ｄ１００５に分岐不成立時アドレス６０５を配置する。この配置は、プロセッサがサポートとするＳＩＭＤ命令の種類を考慮したものである。以下にその詳細を説明する。
【００８３】
分岐予測結果６０２は、分岐ヒント命令２０５で利用する。分岐ヒント命令２０５はスカラ命令であるため、ＳＩＭＤレジスタの要素Ａ１００２を利用する。このため、要素Ａ１００２に分岐予測結果６０２を配置する必要がある。
【００８４】
２ビット予測状態６０３は要素Ｃ１００２に配置する。
【００８５】
２ビット予測状態６０３の値は、予測結果を得るために２進数１０と論理演算するため、最終的には１０（１０進数で３）か００（１０進数で０）をとる。この値は、シャッフルＡ命令を利用して分岐予測結果６０２を格納する要素Ａ１００２に分岐結果を代入する場合、代入元のレジスタの要素番号を指定するのに利用できる。
【００８６】
このため、２ビット予測状態６０３を要素Ｃ１００２に配置して、残りの分岐成立時分岐先アドレス６０４を要素Ｂ１００３に、分岐不成立時分岐先アドレス６０５を要素Ｄ１００５に配置する。
【００８７】
図１３は、ＳＩＭＤ命令およびＳＩＭＤレジスタを使用した場合のオブジェクトコード２０３による処理全体の処理フローを示すための図である。
【００８８】
図１３（ａ）は、オブジェクトコード２０３が実行される際に、分岐命令８０１の結果が分岐成立となり、分岐成立時処理コード４０１が実行される場合の処理フローである。なおこのフローは図８（ｂ）の分岐の左側に対応する。
【００８９】
はじめに、分岐命令８０１に対応する分岐予測テーブルエントリの分岐予測情報の２ビット予測状態６０３をインクリメントする（ステップ１３０１）。インクリメントには、飽和加算命令を用いて行う。
【００９０】
次に、予測結果を得るために、インクリメントした２ビット予測状態６０３と２進数１０とで論理積をとる。論理積を求める際には、論理積演算命令を用いて行う。結果が００の場合は分岐不成立と予測し、１０の場合は分岐成立と予測する（ステップ１３０２）。
【００９１】
次に、分岐予測結果６０２を、同エントリの適切な分岐先アドレスで更新する（ステップ１３０３）。予測結果が分岐成立の場合、同エントリの分岐成立時分岐先アドレス６０４の値で更新する。不成立の場合、同エントリの分岐不成立時分岐先アドレス６０５の値で更新する。この際、シャッフルＳＩＭＤ命令Ａを用いる。
【００９２】
図１３（ｂ）は、オブジェクトコード２０３が実行される際に、分岐命令８０１の結果が分岐不成立となり、分岐成立時処理コード４０２が実行される場合の処理フローである。なおこのフローは図８（ｂ）の分岐の右側に対応する。
【００９３】
はじめに、分岐命令８０１に対応する分岐予測テーブルエントリの分岐予測情報の２ビット予測状態６０３をディクリメントする（ステップ１３０４）。ディクリメントには、飽和減算命令を用いて行う。
【００９４】
次に、予測結果を得るために、ディクリメントした２ビット予測状態６０３と２進数１０とで論理積をとる。論理積を求める際には、論理積演算命令を用いて行う。結果が００の場合は分岐不成立と予測し、１０の場合は分岐成立と予測する（ステップ１３０５）。
【００９５】
次に、分岐予測結果６０２を、同エントリの適切な分岐先アドレスで更新する（ステップ１３０３）。予測結果が分岐成立の場合、同エントリの分岐成立時分岐先アドレス６０４の値で更新する。不成立の場合、同エントリの分岐不成立時分岐先アドレス６０５の値で更新する。この際、シャッフルＳＩＭＤ命令Ａを用いる。
【００９６】
以上説明したＳＩＭＤ命令すべてをサポートするプロセッサが必要なわけではない。ＳＩＭＤ命令を、より細かいＳＩＭＤ命令やスカラ命令を組み合わせて実現することが可能であることはいうまでもない。
【００９７】
その一例として、シャッフルＳＩＭＤ命令Ａをサポートしていないアーキテクチャを想定し、以下に説明する。このようなアーキテクチャを持つプロセッサを利用する場合では、シャッフルＳＩＭＤ命令Ａを、別のＳＩＭＤ命令であるローテート命令とシャッフルＳＩＭＤ命令Ｂで置き換える。
【００９８】
図１４に例を示す。
【００９９】
図１４では、ＳＩＭＤレジスタ１４０１の各要素に１６進数の値０ｘ３０４、０ｘ３０４、０ｘ０２、０ｘ１００が格納されている。ＳＩＭＤレジスタ１４０１を、ローテート命令を利用して３要素分左にローテートし、その結果をＳＩＭＤレジスタ１４０２に代入する。その後に、ＳＩＭＤレジスタ１４０１とＳＩＭＤレジスタ１０４２とでシャッフルＳＩＭＤ命令Ｂを利用する。その結果、ＳＩＭＤレジスタ１４０１には、シャッフルＳＩＭＤ命令Ａを用いた場合と同じ結果が得られる。
【０１００】
以上が、ＳＩＭＤ命令およびＳＩＭＤレジスタを利用した例である。
【０１０１】
（最適化処理を行う例）
以下に、図８の分岐ヒント命令２０５の前に前処理を挿入し、最適化処理を行う例を示す。
【０１０２】
図１５に処理フローを示す。
【０１０３】
分岐最適化部２０４が分岐ヒント命令２０５を挿入する際に、分岐ヒント命令２０５の前に前処理１５０１を挿入する。
【０１０４】
前処理１５０１では、本発明の分岐予測処理の予測精度の最適化処理を行うことが出来る。
【０１０５】
以下に前処理１５０１の例を２つ示す。
【０１０６】
（２ビット予測状態６０３の初期値などを設定する前処理の例）
仮に図１５の処理フローが、分岐命令８０１が分岐成立をＮ回繰り返した後に１回分岐不成立となるループ処理であり、このループ処理が複数回実行されるとする。さらに、各ループ処理が異なる分岐特性を持つデータセットに対して処理を行う場合には、各ループ処理に入る前の前処理において、データセットに適した初期値を設定することで予測精度を向上されることを実現する。
【０１０７】
（データセットの分岐特性に応じて分岐予測を動的に切り替える前処理の例）
例えば、初期値などを設定する上記例で示したループ処理において、各ループ処理に入る前の前処理で、前回のループ処理の分岐予測結果と実際の分岐結果を比較し予測精度チェックを行なう。得られた予測精度に応じて、適切な動的分岐予測方式を動的に選択する。選択肢としては、ハードウェア分岐機構を持つプロセッサで実施する場合にはハードウェアの分岐予測機構を優先するなどがあげられる。また、既存の別の動的分岐予測方法をソフトウェアで実装しておき、これに切り替えることも可能である。
【０１０８】
（その他）
なお、図２に示した分岐最適化部はコンパイラ２０２から独立していてもよい。図１６に構成例を示す。計算機上で実行されるソフトウェアであるコンパイラ２０２は、ソースプログラム２０１を処理して第１オブジェクトコード１６０１を生成する。
【０１０９】
計算機上で実行されるソフトウェアである分岐最適化ソフトウェア１６０２は、第１オブジェクトコード１６０１に分岐ヒント命令２０５と分岐予測処理用コード２０６を挿入し、第２オブジェクトコード２０３を生成する。
【０１１０】
分岐予測処理用コード２０６は、第２オブジェクトコード２０３の実行時に同時に処理され、分岐予測処理を行う。さらに、その予測結果を分岐予測ヒント命令２０５が利用できるように設定する。
【０１１１】
以上のように本発明は、ソースコードからコンパイルする時点に限らず、先にコンパイルされたオブジェクトコードに対して動的分岐予測処理を組み込むことによっても実施可能である。
【０１１２】
また、ＳＩＭＤ命令をサポートするプロセッサで実行するオブジェクトコードに適用する場合に、分岐予測処理に必要な操作をＳＩＭＤレジスタ内の操作で完結させることができるので、分岐予測処理のための計算コストを予測ミスペナルティより充分に小さく抑えられる。
【０１１３】
本発明は以上説明した実施の形態に限らず、様々な態様で実施することが可能であることはいうまでもない。例えば、ソフトウェアを実行する主体は単一の計算機に限らず、例えばコンパイラを実行する計算機とオブジェクトコードを実行する計算機とが別々であってもよいし、コンパイラを実行する計算機と分岐最適化ソフトウェアを実行する計算機とが別々であってもよいのは自明である。
【図面の簡単な説明】
【０１１４】
【図１】計算機のブロック図。
【図２】計算機で実行されるソフトウェアとプログラムの関係を示す図。
【図３】分岐ヒント命令のフォーマットを示す図。
【図４】分岐予測処理用コードの構造概念図。
【図５】分岐予測テーブルの構造概念図。
【図６】分岐予測情報の構造概念図。
【図７】分岐予測情報の具体例を示す図。
【図８】分岐ヒント命令と分岐予測処理用コードとの挿入例を示す図。
【図９】オブジェクトコードに係る処理のフローチャート。
【図１０】ＳＩＭＤレジスタの構造概念図。
【図１１】ＳＩＭＤ命令によるＳＩＭＤレジスタ格納値の変化を示す図。
【図１２】ＳＩＭＤレジスタの要素と分岐予測情報の要素と配置関係を示す図。
【図１３】ＳＩＭＤ命令を含むオブジェクトコードに係る処理のフローチャート。
【図１４】図１３に係るＳＩＭＤレジスタ格納値の変化を示す図。
【図１５】前処理と分岐ヒント命令と分岐予測処理用コードとの挿入例を示す図。
【図１６】計算機で実行されるソフトウェアとプログラムの関係を示す図。
【符号の説明】
【０１１５】
１０１・・・プロセッサ、１０２・・・一時記憶装置、１０３・・・データ転送装置、１０４・・・主記憶装置、１０５・・・バス、１０６・・・入出力装置。
【図１】
2008107913.tif 000003
【図２】
2008107913.tif 000004
【図３】
2008107913.tif 000005
【図４】
2008107913.tif 000006
【図５】
2008107913.tif 000007
【図６】
2008107913.tif 000008
【図７】
2008107913.tif 000009
【図８】
2008107913.tif 000010
【図９】
2008107913.tif 000011
【図１０】
2008107913.tif 000012
【図１１】
2008107913.tif 000013
【図１２】
2008107913.tif 000014
【図１３】
2008107913.tif 000015
【図１４】
2008107913.tif 000016
【図１５】
2008107913.tif 000017
【図１６】
2008107913.tif 000018