(57)【要約】【課題】  少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置等を提供する。【解決手段】  実行頻度が高い命令列の実行パスを検出するための実行パス検出装置は、分岐命令を含む命令列を１ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブル３１０と、分岐命令の分岐履歴が格納される分岐履歴テーブル３２０と、分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部２２０とを含み、実行回数が所与の閾値を超えたことを条件に、分岐履歴管理部２２０が、分岐履歴の収集を開始すると共に、実行パスを特定するためのパス情報を分岐履歴に基づいて出力する。【選択図】      図６
2008250867.tif 000002
【特許請求の範囲】
【請求項１】
実行頻度が高い命令列の実行パスを検出するための実行パス検出装置であって、
分岐命令を含む命令列を１ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブルと、
前記分岐命令の分岐履歴が格納される分岐履歴テーブルと、
前記分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部とを含み、
前記実行回数が所与の閾値を超えたことを条件に、前記分岐履歴管理部が、前記分岐履歴の収集を開始すると共に、前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力することを特徴とする実行パス検出装置。
【請求項２】
請求項１において、
前記命令列ブロックの先頭アドレスの命令の実行回数をカウントするカウンタを含み、
前記実行履歴テーブルは、
前記先頭アドレスの命令毎に、実行回数を記憶することを特徴とする実行パス検出装置。
【請求項３】
請求項１又は２において、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していることを特徴とする実行パス検出装置。
【請求項４】
請求項１又は２において、
前記分岐履歴テーブルに登録すべき情報の少なくとも一部が、前記実行履歴テーブルの記憶領域に書き込まれることを特徴とする実行パス検出装置。
【請求項５】
請求項１乃至４のいずれかにおいて、
前記実行履歴テーブルに、
分岐命令の戻り方向の分岐先アドレスの命令の実行回数が格納されることを特徴とする実行パス検出装置。
【請求項６】
請求項１乃至５のいずれかにおいて、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記分岐履歴管理部が、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することを特徴とする実行パス検出装置。
【請求項７】
請求項１乃至６のいずれかにおいて、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することを特徴とする実行パス検出装置。
【請求項８】
請求項１乃至７のいずれかにおいて、
前記分岐履歴管理部が、
前記分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することを特徴とする実行パス検出装置。
【請求項９】
請求項１乃至８のいずれかにおいて、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴管理部が、
前記分岐履歴テーブルの記憶情報を無効化することを特徴とする実行パス検出装置。
【請求項１０】
請求項１乃至９のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置とを含み、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理が最適化されることを特徴とする情報処理装置。
【請求項１１】
請求項１乃至９のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置と、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理を最適化するパス処理部とを含むことを特徴とする情報処理装置。
【請求項１２】
実行頻度が高い命令列の実行パスを検出するための実行パス検出方法であって、
分岐命令を含む命令列を１ブロックとする命令列ブロックの先頭アドレスの命令の実行回数を実行履歴テーブルに記憶するステップと、
前記実行回数が所与の閾値を超えたことを条件に前記分岐命令の分岐履歴の収集を開始し、該分岐履歴を分岐履歴テーブルに記憶するステップと、
前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力するステップとを含むことを特徴とする実行パス検出方法。
【請求項１３】
請求項１２において、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していることを特徴とする実行パス検出方法。
【請求項１４】
請求項１２又は１３において、
前記先頭アドレスが、
分岐命令の戻り方向の分岐先アドレスであり、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することを特徴とする実行パス検出方法。
【請求項１５】
請求項１２乃至１４のいずれかにおいて、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することを特徴とする実行パス検出方法。
【請求項１６】
請求項１２乃至１５のいずれかにおいて、
該分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することを特徴とする実行パス検出方法。
【請求項１７】
請求項１２乃至１６のいずれかにおいて、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴テーブルの記憶情報を無効化することを特徴とする実行パス検出方法。
【請求項１８】
コンピュータに、請求項１２乃至１７のいずれか記載の実行パス検出方法を実行させるためのプログラム。
【請求項１９】
請求項１８記載のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
アプリケーションプログラムを実行するプロセッサの処理の高速化や低消費電力化を実現するために、プログラムの局所性に着目した手法が提案されている。この手法は、プログラムを実行する上でクリティカルな命令列を発見し、該命令列の処理の最適化を図ることで処理の高速化や低消費電力化を実現するものである。このようなクリティカルな命令列を発見する手法として、命令列に含まれる分岐命令の実行履歴を利用する手法がある。
【０００３】
例えば特許文献１には、命令列の命令が実行される方向とは逆方向である戻り方向に分岐する分岐命令の実行回数に着目してループ構造の命令部分を検出し、ループ構造の命令の実行回数が多いと判断されるパス経路を記録する分岐履歴記録装置が開示されている。即ち、特許文献１では、プログラムのループ構造の部分に局所性が存在するという仮定の下で、該パス経路を実行頻度の高い命令列の実行パスとして検出する。
【０００４】
また、例えば特許文献２には、分岐命令の分岐履歴が格納されるプロファイラテーブルと、戻り方向の分岐先アドレス及び分岐回数が格納される戻り分岐先テーブルとを設け、戻り分岐先テーブルの分岐先アドレスとプロファイラテーブルに格納された分岐履歴とに基づいて、実行頻度の高い命令列の実行パスを検出する推定装置が開示されている。
【特許文献１】特開２０００−１４８４８２号公報
【特許文献２】特開２００５−９２５３２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に開示された分岐履歴記録装置では、ソフトウェアで処理する必要がある。そのため、実行頻度の高い命令列の実行パスを検出するための処理時間が長くなり、プロセッサの処理中に、所望の命令列の実行パスを特定することが困難であるという問題がある。
【０００６】
また、特許文献２に開示された推定装置では、膨大な分岐履歴や分岐先アドレスを記録しておく必要があり、分岐履歴や分岐先アドレス等を記憶する記憶領域が膨大になってしまうという問題がある。このような推定装置において、記憶領域を少なくしようとすると、退避等の必要性から処理が中断されてしまい、所望の命令列の実行パスを検出するための処理時間が長くなる。更に、特許文献２におけるＳＷプロファイラ部による処理が複雑であるため、ハードウェア化が困難であり、ソフトウェアで実現せざるを得なくなる。従って、特許文献１と同様に、プロセッサの処理中に、所望の命令列の実行パスを特定することは困難となる。
【０００７】
本発明は、以上のような技術的課題に鑑みてなされたものであり、その目的とするところは、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置、情報処理装置、実行パス検出方法、その実行パス検出方法をコンピュータに実現させるプログラム、及び該プログラムを記録する記録媒体を提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために本発明は、
実行頻度が高い命令列の実行パスを検出するための実行パス検出装置であって、
分岐命令を含む命令列を１ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブルと、
前記分岐命令の分岐履歴が格納される分岐履歴テーブルと、
前記分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部とを含み、
前記実行回数が所与の閾値を超えたことを条件に、前記分岐履歴管理部が、前記分岐履歴の収集を開始すると共に、前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力する実行パス検出装置に関係する。
【０００９】
また本発明に係る実行パス検出装置では、
前記命令列ブロックの先頭アドレスの命令の実行回数をカウントするカウンタを含み、
前記実行履歴テーブルは、
前記先頭アドレスの命令毎に、実行回数を記憶することができる。
【００１０】
上記のいずれかの発明によれば、アプリケーションプログラムの局所性に着目して、高頻度で実行される命令列の繰り返し部分を検出してから、該繰り返し部分の分岐履歴を収集するようにしたので、アプリケーションプログラムにおいて実行頻度が高い命令列の実行パスを検出する際に膨大な分岐履歴を収集する必要がなくなる。そのため、本発明によれば、実行パスの検出精度の低下を抑えつつ、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できるようになる。
【００１１】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していてもよい。
【００１２】
また本発明に係る実行パス検出装置では、
前記分岐履歴テーブルに登録すべき情報の少なくとも一部が、前記実行履歴テーブルの記憶領域に書き込まれてもよい。
【００１３】
上記のいずれかの発明においては、まず実行履歴テーブルを用いて高頻度で実行される命令列の繰り返し部分を検出してから、分岐履歴テーブルに該繰り返し部分の分岐履歴を収集する。そのため、分岐履歴を収集する段階では実行履歴テーブルを不要にできるため、本発明によれば、実行履歴テーブルと分岐履歴テーブルの記憶領域を共用するようにしたので、両テーブルのために必要な記憶容量の削減を図ることができる。
【００１４】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルに、
分岐命令の戻り方向の分岐先アドレスの命令の実行回数が格納されてもよい。
【００１５】
本発明によれば、戻り方向の分岐命令の実行履歴のみを収集するようにしたので、少ないメモリ容量で、高頻度で繰り返される実行部分を検出できるようになる。
【００１６】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記分岐履歴管理部が、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することができる。
【００１７】
本発明によれば、実行履歴テーブルを用いて検出した高頻度の繰り返し部分の分岐履歴の収集を行うことができるので、少ないメモリ容量で分岐履歴テーブルを構成できるようになる。
【００１８】
また本発明に係る実行パス検出装置では、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することができる。
【００１９】
また本発明に係る実行パス検出装置では、
前記分岐履歴管理部が、
前記分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することができる。
【００２０】
上記のいずれかの発明によれば、分岐履歴テーブルに基づいてターゲットアドレス出力できるので、無駄なソフトウェア処理を省略して、高速に、実行パスを特定できるようになる。
【００２１】
また本発明に係る実行パス検出装置では、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴管理部が、
前記分岐履歴テーブルの記憶情報を無効化することができる。
【００２２】
本発明によれば、分岐履歴の収集を開始した後に、高頻度で繰り返される実行が行われなかったことを検出して分岐履歴テーブルを無効化するようにしたので、無駄にパス情報を収集する必要がなくなる。
【００２３】
また本発明は、
上記のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置とを含み、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理が最適化される情報処理装置に関係する。
【００２４】
また本発明は、
上記のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置と、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理を最適化するパス処理部とを含む情報処理装置に関係する。
【００２５】
上記のいずれかの発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置が適用され、処理が最適化された情報処理装置を提供できる。
【００２６】
また本発明は、
実行頻度が高い命令列の実行パスを検出するための実行パス検出方法であって、
分岐命令を含む命令列を１ブロックとする命令列ブロックの先頭アドレスの命令の実行回数を実行履歴テーブルに記憶するステップと、
前記実行回数が所与の閾値を超えたことを条件に前記分岐命令の分岐履歴の収集を開始し、該分岐履歴を分岐履歴テーブルに記憶するステップと、
前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力するステップとを含む実行パス検出方法に関係する。
【００２７】
また本発明に係る実行パス検出方法では、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していてもよい。
【００２８】
また本発明に係る実行パス検出方法では、
前記先頭アドレスが、
分岐命令の戻り方向の分岐先アドレスであり、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することができる。
【００２９】
また本発明に係る実行パス検出方法では、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することができる。
【００３０】
また本発明に係る実行パス検出方法では、
該分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することができる。
【００３１】
また本発明に係る実行パス検出方法では、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴テーブルの記憶情報を無効化することができる。
【００３２】
上記のいずれかの発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法を提供できる。
【００３３】
また本発明は、
コンピュータに、上記のいずれか記載の実行パス検出方法を実行させるためのプログラムに関係する。
【００３４】
本発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法をコンピュータに実現させるプログラムを提供できる。
【００３５】
また本発明は、
上記記載のプログラムを記録したコンピュータ読み取り可能な記録媒体に関係する。
【００３６】
本発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法をコンピュータに実現させるプログラムを記録した記録媒体を提供できる。
【発明を実施するための最良の形態】
【００３７】
以下、本発明の実施の形態について図面を用いて詳細に説明する。なお、以下に説明する実施の形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また以下で説明される構成のすべてが本発明の必須構成要件であるとは限らない。
【００３８】
１．  情報処理装置
図１に、本実施形態における情報処理装置の構成例のブロック図を示す。
【００３９】
情報処理装置１００は、中央演算処理装置（Central Processing Unit：ＣＰＵ）１０と、アクセラレータ２０と、プロファイラ（実行パス推定装置、実行パス検出装置）３０とを含む。情報処理装置１００は、バス５０を含み、バス５０を介して、ＣＰＵ１０、アクセラレータ２０及びプロファイラ３０との間でデータやアドレスのやり取りが行われる。また、情報処理装置１００の外部には、メモリバス５２を介してバス５０と接続されるメモリ１１０が設けられており、ＣＰＵ１０、アクセラレータ２０及びプロファイラ３０はバス５０及びメモリバス５２を介してメモリ１１０にアクセスできるようになっている。
【００４０】
ＣＰＵ１０は、ＣＰＵ１０の内蔵メモリ又はメモリ１１０に格納されたアプリケーションプログラムを読み込んで、該プログラムに対応した命令を実行する。
【００４１】
アクセラレータ２０は、ＣＰＵ１０に代わってＣＰＵ１０が実行すべき処理を行う。アクセラレータ２０の処理時間は、ＣＰＵ１０の処理時間より短い。アクセラレータ２０の機能は、ハードウェア又はソフトウェアにより実現される。アクセラレータ２０の機能がソフトウェアにより実現される場合には、アクセラレータ２０がＣＰＵ及びメモリを有し、該メモリ又は図１のメモリ１１０に格納されたアクセラレータ用プログラムを読み込んで該プログラムに対応した処理を実行するＣＰＵによりアクセラレータ２０の機能が実現される。
【００４２】
このようなアクセラレータ２０は、例えば、より処理時間が短くなるように、又はより低消費電力となるように、ＣＰＵ１０が処理すべきプログラムの命令列を最適化させた状態で該プログラムの処理結果を生成する。アクセラレータ２０は、例えばＣＰＵ１０が処理すべきプログラムのうち不要な命令列が削除された命令列を実行することで、該プログラムを実行した場合のＣＰＵ１０の処理結果と同じ結果をより短時間で得られるようになっている。また、例えばアクセラレータ２０は、ＣＰＵ１０が処理すべきプログラムの命令列を並列に処理することで、該プログラムを実行した場合のＣＰＵ１０の処理結果と同じ結果をより短時間で得られるようになっている。
【００４３】
プロファイラ（広義には実行パス検出装置）３０は、プログラムの実行中に実行頻度の高いループ構造のパス（実行パス、命令パス、ホットパス）を高精度で検出（推定）し、検出したパスを特定するための情報であるホットパス情報（広義にはパス情報）を出力する。プロファイラ３０は、ＣＰＵ１０が実行するプログラムを構成する命令列のうち繰り返し実行される命令列を検出し、繰り返し実行される命令列の分岐履歴に基づいて実行頻度の高いパスを特定する処理を行う。
【００４４】
更に情報処理装置１００の外部には、ホットパス処理部１２０が設けられている。ホットパス処理部１２０は、プロファイラ３０からのホットパス情報に基づいて実行頻度の高いループ構造のパスを特定し、このパスの処理を最適化することで情報処理装置１００の処理時間を短縮させたり情報処理装置１００の処理中の消費電力を低減させたりする。
【００４５】
例えば、ホットパス処理部１２０は、プロファイラ３０からのホットパス情報に基づいて特定した命令列のパスを並列処理させるように命令列を最適化したり、実行不要な命令を削除して命令列を最適化したりする。このとき、ホットパス処理部１２０は、最適化処理後の命令列をアクセラレータ２０や該アクセラレータ２０がアクセスするメモリに格納する。
【００４６】
或いは、例えばホットパス処理部１２０は、プロファイラ３０からのホットパス情報に基づいて特定した命令列のパスの処理時間が短くなるようにアクセラレータ２０のハードウェア構成を変更したり、或いは該パスを処理する上で情報処理装置１００の消費電力が低減するようにアクセラレータ２０のハードウェア構成を変更したりする処理を行う。この場合、アクセラレータ２０は動的再構成可能な回路であり、ホットパス処理部１２０が、動的再構成に必要なハードウェア構成情報をアクセラレータ２０に供給する。
【００４７】
次に、図１の情報処理装置１００の処理の概要について説明する。
【００４８】
本実施形態では、基本ブロックと呼ばれる命令列ブロックを単位に、命令列の実行パスを考える。
【００４９】
図２に、本実施形態における基本ブロックの説明図を示す。
【００５０】
アプリケーションプログラムを構成する命令列の実行パスを考えると、アプリケーションプログラムを構成する命令は、プログラムの実行の流れを変える分岐命令と、分岐命令以外の他の命令とに区別できる。そして、プログラムを構成する命令が、アドレス値の小さい命令からアドレス値の大きい命令の方向に順番に実行されるため、実行の流れを変える分岐命令毎に、命令列のブロックを区分できる。このブロックが、基本ブロックである。基本ブロックは、例えば直前の基本ブロックの最後の分岐命令の次の命令から始まり、アドレス値の大きい方向に命令が実行されたときの最初の分岐命令で終わる命令列のブロックである。
【００５１】
図２では、基本ブロックＢＢ１、ＢＢ２、・・・、ＢＢＫ（Ｋは３以上の正の整数）が示されている。基本ブロックＢＢ１は、このブロックの先頭アドレスＢＳＡ１の命令“ｉｎｓｔ１”に始まり、命令の実行方向に順次命令が実行され、アドレスＢＩＡ１の分岐命令“ｂｎｅ”で終わる。ここで分岐命令“ｂｎｅ”が条件分岐命令であるとすると、条件が「真」のときの分岐先アドレスがＢＳＡ３、条件が「偽」のときの分岐先アドレスがアドレスＢＩＡ１の次のアドレスであるＢＳＡ２である。
【００５２】
基本ブロックＢＢ２は、このブロックの先頭アドレスＢＳＡ２の命令“ｉｎｓｔ２”に始まり、命令の実行方向に順次命令が実行され、アドレスＢＩＡ２の分岐命令“ｂｒ”で終わる。アドレスＢＳＡ２は、アドレスＢＩＡ１の分岐命令の分岐先アドレスであるため、アドレスＢＳＡ２は分岐ターゲットアドレスＢＴＡ１である。
【００５３】
基本ブロックＢＢ３は、このブロックの先頭アドレスＢＳＡ３の命令“ｉｎｓｔ３”に始まり、命令の実行方向に順次命令が実行され、同様にアドレスＢＩＡ３の分岐命令（図示せず）で終わる。アドレスＢＳＡ３は、アドレスＢＩＡ１の分岐命令の分岐先アドレスであるため、アドレスＢＳＡ３の分岐ターゲットアドレスＢＴＡ２である。
【００５４】
従って、命令の実行パスを、基本ブロックＢＢ１、ＢＢ２のパスとして表したり、基本ブロックＢＢ１、ＢＢ３のパスとして表したりすることができる。
【００５５】
図３に、図１の情報処理装置１００の処理の一例の概要のフローを示す。
【００５６】
まず、情報処理装置１００のプロファイラ３０は、アプリケーションプログラムを実行するＣＰＵ１０の実行履歴を収集し、アプリケーションプログラムを構成する命令列のうち高頻度で繰り返し実行される実行命令部分を検出する（ステップＳ１０）。このとき、アプリケーションプログラムを構成する命令列が、それぞれ１つの分岐命令を含む基本ブロックに区分でき、基本ブロック間の流れでプログラムの実行パスを特定できる。その結果、図４に示すように、例えば基本ブロックＦから基本ブロックＡに戻るパスが高頻度で繰り返し実行される実行命令部分として検出される。なお、図４では、基本ブロックＡ〜Ｆが示されており、基本ブロックＡから基本ブロックＢ〜Ｇのいずれかの方向にプログラムの実行が流れるものとする。
【００５７】
図３に示すように、次に、情報処理装置１００は、ステップＳ１０で検出した実行頻度の高い実行命令部分の分岐履歴の収集を開始する。そして、情報処理装置１００は、収集した分岐履歴情報に基づいてパスを特定するホットパス情報を出力する（ステップＳ１１）。
【００５８】
ホットパス処理部１２０は、プロファイラ３０からのホットパス情報を受けて、上述のようにホットパスの処理の最適化を行い（ステップＳ１２）、一連の処理を終了する（エンド）。
【００５９】
図５に、図３のホットパスの説明図を示す。
【００６０】
図５において、図４と同じ基本ブロックＡ〜Ｆが示されている。各基本ブロックは、当該基本ブロックの先頭アドレス（Basic block Start Address：ＢＳＡ）の命令ＦＩと、当該基本ブロックの最終アドレスである分岐命令アドレス（Branch Instruction Address：ＢＩＡ)の分岐命令ＢＩとを含む。各基本ブロック間を接続する矢印は、分岐命令により処理の流れが変えられたことを示し、この矢印に付される数値は該分岐命令による分岐回数を示す。
【００６１】
例えば基本ブロックＡの分岐命令ＢＩの分岐先が２つあり、該分岐命令ＢＩが条件分岐命令であることを示す。基本ブロックＡから基本ブロックＢへの矢印は、例えば基本ブロックＡの分岐命令ＢＩの条件が「真」のときの分岐先アドレスが基本ブロックＢの先頭アドレスＢＳＡであることを示す。そして、基本ブロックＡから基本ブロックＢへの処理の流れの変更が、履歴として８００回であったことを意味している。また、基本ブロックＡから基本ブロックＣへの矢印は、例えば基本ブロックＡの分岐命令ＢＩの条件が「偽」のときの分岐先アドレスが基本ブロックＣの先頭アドレスＢＳＡであることを示す。そして、基本ブロックＡから基本ブロックＣへの処理の流れの変更が、履歴として２００回であったことを意味している。
【００６２】
これに対して、例えば基本ブロックＤの分岐命令ＢＩの分岐先は１つであり、該分岐命令ＢＩが無条件分岐命令であることを示す。この無条件分岐は、履歴として７００回であることを意味する。
【００６３】
以上のような履歴を履歴情報として収集するため、基本ブロックの開始アドレスＢＳＡ、分岐先アドレスＢＴＡ（Branch Target Address）（広義にはターゲットアドレス）、分岐命令のアドレスＢＩＡ、分岐回数がテーブルを用いて管理される。そして、各基本ブロック間の分岐回数が多いルートがホットパスとして特定される。図５では、基本ブロックＡ、Ｂ、Ｄ、Ｆのルートがホットパスとなり、ホットパス情報として、基本ブロックＡ、Ｂ、Ｄ、Ｆの各基本ブロックの先頭アドレス列を出力することでホットパスが特定される。
【００６４】
その結果、基本ブロックＡ、Ｂ、Ｄ、Ｆのパスの命令列の最適化により一層高い負荷をかける等して情報処理装置１００の処理を重点的に最適化することができる。
【００６５】
このように、本実施形態においては、プログラムの局所性に着目して、高頻度で実行される命令列の繰り返し部分を検出してから、該繰り返し部分の分岐履歴を収集するようにしたので、アプリケーションプログラムのホットパスを検出する際に膨大な分岐履歴を収集する必要がなくなる。そのため、本実施形態によれば、パスの検出精度の低下を抑えつつ、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できるようになる。
【００６６】
２．  プロファイラの説明
次に、このようなホットパスの検出を行う図１のプロファイラ３０について説明する。
【００６７】
図６に、図１のプロファイラ３０の構成の概要を示す。
【００６８】
プロファイラ３０は、制御部２００と、管理テーブル部３００とを含む。制御部２００は、実行履歴管理部２１０、分岐履歴管理部２２０を含む。管理テーブル部３００は、実行履歴テーブル３１０、分岐履歴テーブル３２０を含む。
【００６９】
なお、制御部２００の機能は、ソフトウェアで実現されてもよいし、専用のハードウェアにより実現されてもよい。制御部２００がソフトウェアで実現される場合、後述する実行パスの検出方法を実現するプログラムを読み込んだプロファイラ３０のＣＰＵが処理を行う。また、管理テーブル部３００は、後述するように実行履歴テーブル３１０と分岐履歴テーブル３２０の記憶領域を共用することが望ましい。
【００７０】
実行履歴管理部２１０は、実行履歴テーブル３１０を管理する制御を行う。
【００７１】
図７に、図６の実行履歴テーブル３１０の構成の概要を示す。
【００７２】
実行履歴テーブル３１０は、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスＢＳＡに関連付けて（対応して）、該先頭アドレスＢＳＡの命令の実行回数ＣＯＵＮＴが記憶される。即ち、基本ブロックの先頭アドレスＢＳＡの命令の実行回数がカウントされ、実行履歴テーブル３１０には、基本ブロックの先頭アドレスの命令毎に、実行回数が記憶される。
【００７３】
ここで、先頭アドレスＢＳＡは、分岐命令の戻り方向の分岐先アドレスである。そのため、実行履歴テーブル３１０には、基本ブロックの先頭アドレスＢＳＡではなく、該先頭アドレスＢＳＡを戻り方向の分岐先アドレスとして登録してもよい。このように戻り方向の分岐命令の実行履歴のみを収集することで、少ないメモリ容量で、高頻度で繰り返される実行部分を検出できるようになる。
【００７４】
そこで、実行履歴管理部２１０は、分岐命令を含む命令列を１ブロックとする基本ブロック（命令列ブロック）の先頭アドレスＢＳＡ、該先頭アドレスＢＳＡの命令の実行回数を実行履歴テーブル３１０に登録、追加、検索等をする管理制御を行う。
【００７５】
図６において、分岐履歴管理部２２０は、実行履歴テーブル３１０で管理される基本ブロックの先頭アドレスのうちいずれかの先頭アドレスの命令の実行回数が所与の閾値ＴＨ１を超えたことを条件に、分岐命令の分岐履歴の収集を開始し、その後、分岐履歴を収集する処理を行う。
【００７６】
図８に、図６の分岐履歴テーブル３２０の構成の概要を示す。
【００７７】
分岐履歴テーブル３２０は、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスＢＳＡに関連付けて、分岐命令のアドレスＢＩＡ、該分岐命令の分岐先アドレスＢＴＡ、該分岐命令の分岐回数ＣＯＵＮＴが記憶される。ここで、先頭アドレスＢＳＡは、分岐命令の戻り方向の分岐先アドレスであったり、分岐命令の順方向の分岐先アドレスであったりする。
【００７８】
そこで、分岐履歴管理部２２０は、基本ブロックの先頭アドレスＢＳＡ、分岐命令のアドレス、該分岐命令の分岐先アドレス、分岐回数を分岐履歴テーブル３２０に登録、追加、検索等をする管理制御を行う。また分岐履歴管理部２２０は、分岐履歴テーブル３２０に登録された分岐履歴に基づいてホットパス情報（実行頻度の高い実行パスを特定するためのパス情報）を出力する。
【００７９】
なお、図８において、分岐履歴テーブル３２０に分岐命令のアドレスＢＩＡを記憶させなくてもよい。しかしながら、分岐履歴テーブル３２０に分岐命令のアドレスＢＩＡを記憶させることで、分岐先アドレスＢＴＡの情報として分岐命令のアドレスＢＩＡを基準としたオフセット情報を用いることができるので、分岐先アドレスＢＴＡの記憶領域を削減できるようになる。
【００８０】
ところで、本実施形態では、まず実行履歴テーブル３１０を用いて高頻度で実行される命令列の繰り返し部分を検出してから、分岐履歴テーブル３２０に該繰り返し部分の分岐履歴を収集するようにしている。そのため、分岐履歴を収集する段階では、実行履歴テーブル３１０を不要にできる。そこで、本実施形態では、実行履歴テーブル３１０と分岐履歴テーブル３２０の記憶領域を共用し、管理テーブル部３００に設けられる記憶容量の削減を図ることができる。
【００８１】
図９（Ａ）、図９（Ｂ）に、本実施形態における管理テーブル部３００の説明図を示す。
【００８２】
図９（Ａ）は、管理テーブル部３００が有する共用テーブルの構成の概要を示す。共用テーブルは、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスＢＳＡに関連付けて、分岐命令のアドレスＢＩＡ、該分岐命令の分岐先アドレスＢＴＡ、該分岐命令の分岐回数ＣＯＵＮＴが記憶される。即ち、共用テーブルは、図８に示す分岐履歴テーブル３２０と同様の構成を有する。
【００８３】
本実施形態では、図９（Ａ）に示す共用テーブルを用いて、図７に示す実行履歴テーブル３１０の機能を実現する。
【００８４】
即ち、図９（Ｂ）に示すように、図９（Ａ）の管理テーブルのうち分岐命令のアドレスＢＩＡと分岐先アドレスＢＴＡの欄がディセーブルにされる（図９（Ｂ）の斜線部分）。その結果、共用履歴テーブルが実行履歴テーブル３１０として機能する場合には、基本ブロックＢＳＡと回数ＣＯＵＮＴの欄のみがイネーブルとなる。これにより、図９（Ａ）に示す共用テーブルで、実行履歴テーブル３１０及び分岐履歴テーブル３２０の両方の機能を実現できる。
【００８５】
このため、本実施形態では、実行履歴テーブル３１０の記憶領域の少なくとも一部が、分岐履歴テーブル３２０の記憶領域と重複しているということができる。また、分岐履歴テーブル３２０に登録すべき情報の少なくとも一部を、実行履歴テーブル３１０の記憶領域に書き込むことができる。
【００８６】
以下では、管理テーブル部３００が、図９（Ａ）に示す共用テーブルの構成を有しているものとする。
【００８７】
２．１  プロファイラの処理例
図１０に、本実施形態におけるプロファイラ３０の処理の概要のフローを示す。
【００８８】
まず、プロファイラ３０の分岐履歴管理部２２０は、共用テーブルを図９（Ｂ）に示すように実行履歴テーブルとして用いるための初期化処理を行う（ステップＳ２０）。
【００８９】
次に実行履歴管理部２１０は、実行履歴テーブルとして機能する共用テーブルを用いて実行履歴を収集する（ステップＳ２１）。そして、実行履歴テーブルとして機能する共用テーブルに格納される基本ブロックの先頭アドレスの命令の実行回数が所与の閾値ＴＨ１を超えたか否かを判断することで、高頻度の繰り返しがあるか否かを判別する（ステップＳ２２）。
【００９０】
ステップＳ２２において、高頻度の繰り返しがないと判別したとき（ステップＳ２２：Ｎ）、実行履歴管理部２１０は、ステップＳ２１に戻って実行履歴の収集を継続する。
【００９１】
ステップＳ２２において、高頻度の繰り返しがあると判別したとき（ステップＳ２２：Ｙ）、実行履歴管理部２１０は、その旨を分岐履歴管理部２２０に通知する。実行履歴管理部２１０又は分岐履歴管理部２２０は、共用テーブルを図９（Ａ）に示すように分岐履歴テーブルとして用いるための初期化処理を行う（ステップＳ２３）。
【００９２】
その後、分岐履歴管理部２２０は、閾値ＴＨ１を超えた実行回数に関連付けて記憶される先頭アドレスを用いて、分岐履歴の収集を開始する。そして分岐履歴管理部２２０は、分岐履歴テーブルとして機能する共用テーブルを用いて分岐履歴の収集を行うと共に、分岐命令が入力される毎に分岐履歴情報に基づいて分岐回数の多い分岐先アドレスをパス情報として出力する（ステップＳ２４）。分岐履歴管理部２２０は、公知の分岐履歴収集手法を用いて分岐命令、分岐先アドレスを登録、追加、リプレース等を行うが、更に分岐回数についても登録する。
【００９３】
次に、分岐履歴管理部２２０は、分岐命令が入力される毎に、分岐履歴テーブルがミスヒットし、且つ該分岐命令の分岐先アドレスが、実行履歴テーブルに一度記録された基本ブロックの先頭アドレスと一致するか否かを検出することで、繰り返し処理の有無を判別する（ステップＳ２５）。繰り返し処理がないと判別されたとき（分岐命令の分岐先が実行履歴テーブルに記録された先頭アドレスとならないとき）（ステップＳ２５：Ｙ）、分岐履歴管理部２２０は、分岐履歴テーブルの分岐履歴を廃棄（無効化、初期化）し（ステップＳ２６）、ステップＳ２０に戻る（リターン）。
【００９４】
分岐履歴管理部２２０は、分岐命令の実行回数を保持している。そしてステップＳ２５において、繰り返し処理があると判別されたとき（ステップＳ２５：Ｎ）、分岐履歴管理部２２０は、所与のサンプリング期間内に分岐命令の実行回数が所与の閾値ＴＨＸ以上であるか否かを判別する（ステップＳ２７）。サンプリング期間内に分岐命令の実行回数が閾値ＴＨＸ以上であると判別されたとき（ステップＳ２７：Ｙ）、分岐履歴管理部２２０は、ステップＳ２４に戻り、分岐履歴の収集とホットパス情報の出力を継続する。一方、サンプリング期間内に分岐命令の実行回数が閾値ＴＨＸ以上ではないと判別されたとき（ステップＳ２７：Ｎ）、分岐履歴管理部２２０は、分岐履歴テーブルの分岐履歴を廃棄（無効化）し（ステップＳ２６）、ステップＳ２０に戻る（リターン）。このように、ステップＳ２７において閾値ＴＨＸ以上繰り返していないか否かを検出することで、ステップＳ２２で検出された高頻度の繰り返し部分について必ずしもホットパスを検出する必要がなくなり、プロファイラ３０が検出するホットパス情報の精度を高めることができる。
【００９５】
以上のように、分岐命令の分岐先が実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、分岐履歴管理部２２０が分岐履歴を廃棄できる。
【００９６】
以上のような処理を、コンピュータを機能させるためのプログラムで実現してもよい。この場合、図１のメモリ１１０又はプロファイラ３０の図示しないメモリに上記の処理を実現するためのプログラムを格納しておき、プロファイラ３０の図示しないＣＰＵがメモリ１１０又はプロファイラ３０の図示しないメモリのプログラムを読み出すことで、上記の処理を実現できる。また、図１において、例えばメモリ１１０又はプロファイラ３０の図示しないメモリに代えてコンピュータ読み取り可能な記録媒体で上記のプログラムを提供してもよい。この記録媒体は、コンピュータにより使用可能な記憶媒体であって、プログラムやデータなどの情報を格納するものであり、その機能は、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク（ＭＯ）、磁気ディスク、ハードディスク、磁気テープ、或いはメモリ（ＲＯＭ）などのハードウェアにより実現できる。プロファイラ３０の図示しないＣＰＵは、この記憶媒体に格納される情報に基づいて本発明（本実施形態）の種々の処理を行う。即ちこの記憶媒体には、本発明（本実施形態）の手段を実行（実現）するための情報（プログラム或いはデータ）が格納される。
【００９７】
図１１に、実行履歴管理部２１０の処理例のフロー図を示す。
【００９８】
まず、実行履歴管理部２１０は、例えばＣＰＵ１０による分岐命令の実行を監視し、基本ブロックの先頭アドレスＢＳＡとして該分岐命令の分岐先アドレスの入力を待つ（ステップＳ４０：Ｎ）。基本ブロックの先頭アドレスＢＳＡが入力されたとき（ステップＳ４０：Ｙ）、実行履歴管理部２１０は、該先頭アドレスＢＳＡをインデックスとして、実行履歴テーブルとして機能する共用テーブルを検索する（ステップＳ４１）。
【００９９】
そして、ステップＳ４１において共用テーブルを検索した結果、既に登録された先頭アドレスＢＳＡがあるとき（ステップＳ４２：Ｙ）、実行履歴管理部２１０は、ステップＳ４１で検索した先頭アドレスＢＳＡに関連付けて記録された実行回数をインクリメントして更新する（ステップＳ４３）。このとき、実行履歴管理部２１０は、ステップＳ４３で更新した実行回数が所与の閾値ＴＨ１を超えたか否かを検出する（ステップＳ４４）。実行回数が閾値ＴＨ１を超えたことが検出されたとき（ステップＳ４４：Ｙ）、実行履歴管理部２１０は、高頻度の繰り返し実行部分が存在したと判断し、当該先頭アドレスＢＳＡを用いた分岐履歴の収集を開始するように分岐履歴収集イネーブルを設定し（ステップＳ４５）、一連の処理を終了する（エンド）。
【０１００】
一方、ステップＳ４１において共用テーブルを検索した結果、既に登録された先頭アドレスＢＳＡがないとき（ステップＳ４２：Ｎ）、実行履歴管理部２１０は、入力された先頭アドレスＢＳＡを実行履歴テーブルとして機能する共用テーブルに登録する処理を行い（ステップＳ４６）、ステップＳ４０に戻る。なお、実際には、先頭アドレスＢＳＡと分岐先アドレスＢＴＡとを比較し、分岐先アドレスが戻り方向であるときに、分岐先アドレスＢＴＡを新たに追加する先頭アドレスＢＳＡとして登録する。このとき、実行履歴テーブルとして機能する共用テーブルでは、必要に応じて記憶情報のリプレースが行われる。
【０１０１】
ステップＳ４４において、実行回数が閾値ＴＨ１を超えていないことが検出されたとき（ステップＳ４４：Ｎ）、実行履歴管理部２１０は、ステップＳ４０に戻って次の基本ブロックの先頭アドレスＢＳＡを待つ。
【０１０２】
以上のように、実行履歴管理部２１０は、実行履歴の収集を行うと共に、収集した実行履歴に基づいて、高頻度で繰り返される実行部分を検出し、分岐履歴の収集開始を指示できるようになっている。
【０１０３】
図１２に、分岐履歴管理部２２０の処理例のフロー図を示す。
【０１０４】
まず、分岐履歴管理部２２０は、分岐履歴収集イネーブルが設定されているか否かを監視する（ステップＳ６０：Ｎ）。分岐履歴収集イネーブルが設定されていることが検出されたとき（ステップＳ６０：Ｙ）、分岐履歴管理部２２０は、図１１のステップＳ４４で閾値ＴＨ１を超えたエントリの先頭アドレスＢＳＡの入力を待つ（ステップＳ６１：Ｎ）。この先頭アドレスＢＳＡは、分岐命令の分岐先アドレスである。基本ブロックの先頭アドレスＢＳＡが入力されたとき（ステップＳ６１：Ｙ）、分岐履歴管理部２２０は、該先頭アドレスＢＳＡをインデックスとして、分岐履歴テーブルとして機能する共用テーブルを検索する（ステップＳ６２）。
【０１０５】
そして、ステップＳ６２において共用テーブルを検索した結果、既に登録された先頭アドレスＢＳＡがあるとき（ステップＳ６３：Ｙ）、分岐履歴管理部２２０は、複数の先頭アドレスＢＳＡが登録されているとき（ステップＳ６４：Ｙ）、分岐回数が最も多い分岐先アドレスをホットパス情報として出力する（ステップＳ６５）と共に、当該分岐先アドレスに関連付けて記憶された分岐回数をインクリメントして更新し（ステップＳ６５）、ステップＳ６０に戻る（リターン）。
【０１０６】
ステップＳ６４において、１つの先頭アドレスＢＳＡのみが登録されているとき（ステップＳ６４：Ｎ）、分岐履歴管理部２２０は、ヒットした分岐先アドレスをホットパス情報として出力すると共に、当該分岐先アドレスに関連付けて記憶された分岐回数をインクリメントして更新し（ステップＳ６６）、ステップＳ６０に戻る（リターン）。
【０１０７】
一方、ステップＳ６２において共用テーブルを検索した結果、既に登録された先頭アドレスＢＳＡがないとき（ステップＳ６３：Ｎ）、分岐履歴管理部２２０は、入力された先頭アドレスＢＳＡを分岐履歴テーブルとして機能する共用テーブルに登録する処理を行い（ステップＳ６７）、ステップＳ６０に戻る。このとき、分岐履歴テーブルとして機能する共用テーブルでは、必要に応じて記憶情報のリプレースが行われる。
【０１０８】
以上のように、分岐履歴管理部２２０は、分岐履歴の収集を行うと共に、収集した分岐履歴に基づいてホットパスを出力できるようになっている。このホットパスは、分岐履歴テーブルを検索して得られた分岐先アドレスを蓄積したホットパス情報として出力される。
【０１０９】
２．２  プロファイラの構成例
次に、本実施形態における実行履歴テーブル３１０、分岐履歴テーブル３２０、実行履歴管理部２１０、分岐履歴管理部２２０の要部の構成例について説明する。
【０１１０】
本実施形態では、実行履歴テーブル３１０及び分岐履歴テーブル３２０が、それぞれ２ウェイ−セットアソシアティブ方式で記憶情報を記憶するものとして説明するが、本発明が、ウェイ数や実行履歴テーブル３１０及び分岐履歴テーブル３２０の構成に限定されるものではない。例えば、実行履歴テーブル３１０及び分岐履歴テーブル３２０は、フルアソシアティブ方式で記憶情報を記憶してもよい。しかしながら、条件分岐命令の分岐先は２箇所であるため、２ウェイ構成とすることで、条件分岐命令の条件が「真」のときの分岐先アドレスと該条件が「偽」の分岐先アドレスとを記憶でき、分岐先アドレスの記憶管理を効率化できる上に無駄な記憶領域を設ける必要がなくなる。
【０１１１】
図１３、図１４（Ａ）、図１４（Ｂ）、図１５（Ａ）、図１５（Ｂ）に、本実施形態における実行履歴テーブル３１０と実行履歴管理部２１０の要部の構成例を示す。
【０１１２】
実行履歴テーブル３１０は、２ウェイ−セットアソシアティブ方式で、基本ブロックの先頭アドレスＢＳＡ及び該先頭アドレスＢＳＡの命令の実行回数ＣＯＵＮＴを記憶する。両方のウェイは同様の構成を有し、各ウェイの記憶情報は公知のＬＲＵ（Least Recently Used）方式でリプレース制御されるようになっている。
【０１１３】
先頭アドレスＢＳＡの例えば下位ビットがデコーダＤＥＣ１、ＤＥＣ２に入力される。各デコーダは、各ウェイのテーブルの１エントリを先頭アドレスＢＳＡの下位ビットに基づいて選択する。各ウェイにおいて選択されたエントリの先頭アドレス及び実行回数ＣＯＵＮＴは読み出される。こうして読み出された先頭アドレスは、先頭アドレスレジスタＢＳＡ１、ＢＳＡ２、実行回数は、実行回数レジスタＣＮＴ１、ＣＮＴ２で保持される。
【０１１４】
コンパレータＣＭＰ１は、先頭アドレスＢＳＡと先頭アドレスレジスタＢＳＡ１の値と比較し、一致したときにヒット信号ｈｉｔａ１をアクティブ（例えば「１」）にする。コンパレータＣＭＰ２は、先頭アドレスＢＳＡと先頭アドレスレジスタＢＳＡ２の値と比較し、一致したときにヒット信号ｈｉｔａ２をアクティブ（例えば「１」）にする。
【０１１５】
実行回数レジスタＣＮＴ１の値は、インクリメンタＩＮＣ１（広義にはカウンタ）でインクリメントされる。実行回数レジスタＣＮＴ２の値は、インクリメンタＩＮＣ２（広義にはカウンタ）でインクリメントされる。
【０１１６】
セレクタＳＥＬ１は、選択制御信号ｓｅｌ１に基づいて、実行回数レジスタＣＮＴ１の値又はインクリメンタＩＮＣ１の出力を選択して、選択出力ＣＮＴｓ１を出力する。そして、選択出力ＣＮＴｓ１により、デコーダＤＥＣ１で選択されたエントリの実行回数ＣＯＵＮＴを更新する。セレクタＳＥＬ２は、選択制御信号ｓｅｌ２に基づいて、実行回数レジスタＣＮＴ２の値又はインクリメンタＩＮＣ２の出力を選択して、選択出力ＣＮＴｓ２を出力する。そして、選択出力ＣＮＴｓ２により、デコーダＤＥＣ２で選択されたエントリの実行回数ＣＯＵＮＴを更新する。
【０１１７】
図１４（Ａ）に示すように、実行履歴管理部２１０又は実行履歴テーブル３１０は、ヒット判定部２１２を含む。ヒット判定部２１２は、ヒット信号ｈｉｔａ１、ｈｉｔａ２が入力され、選択制御信号ｓｅｌ１、ｓｅｌ２、ライトイネーブルｗｅ１、ｗｅ２を出力する。
【０１１８】
図１４（Ｂ）に、図１４（Ａ）のヒット判定部２１２の動作説明図を示す。
【０１１９】
ヒット判定部２１２は、ヒット信号ｈｉｔａ１がアクティブのとき、選択制御信号ｓｅｌ１をアクティブにしてインクリメンタＩＮＣ１の出力で実行履歴テーブル３１０を更新するように制御する。またヒット判定部２１２は、ヒット信号ｈｉｔａ２がアクティブのとき、選択制御信号ｓｅｌ２をアクティブにしてインクリメンタＩＮＣ２の出力で実行履歴テーブル３１０を更新するように制御する。
【０１２０】
更に、ヒット判定部２１２は、ヒット信号ｈｉｔａ１、ｈｉｔａ２が非アクティブのとき、セレクタＳＥＬ１、ＳＥＬ２でいずれも出力されないように制御すると共に、ＬＲＵ制御ビットＬＲＵ１、ＬＲＵ２を用いてＬＲＵ制御を行い、先頭アドレスＢＳＡを基準に分岐先アドレスＢＴＡが戻り方向であるときにライトイネーブルｗｅ１、ｗｅ２の一方をアクティブにする。ライトイネーブルｗｅ１がアクティブのとき、先頭アドレスＢＳＡがデコーダＤＥＣ１で選択されたエントリに書き込まれると共に、実行回数ＣＯＵＮＴとして「１」が書き込まれる。ライトイネーブルｗｅ２がアクティブのとき、先頭アドレスＢＳＡがデコーダＤＥＣ２で選択されたエントリに書き込まれると共に、実行回数ＣＯＵＮＴとして「１」が書き込まれる。
【０１２１】
図１５（Ａ）に示すように、実行履歴管理部２１０又は実行履歴テーブル３１０は、分岐履歴収集開始制御部２１４、閾値ＴＨ１が設定される閾値設定レジスタ２１６を含む。分岐履歴収集開始制御部２１４には、ヒット信号ｈｉｔａ１、ｈｉｔａ２、選択出力ＣＮＴｓ１、ＣＮＴｓ２、閾値ＴＨ１が入力され、分岐履歴収集イネーブルを出力する。
【０１２２】
図１５（Ｂ）に、図１５（Ａ）の分岐履歴収集開始制御部２１４の動作説明図を示す。
【０１２３】
分岐履歴収集開始制御部２１４は、ヒット信号ｈｉｔａ１がアクティブのとき、選択出力ＣＮＴｓ１と閾値ＴＨ１とを比較し、選択出力ＣＮＴｓ１が閾値ＴＨ以上のとき分岐履歴イネーブルをアクティブ（例えば「１」）に設定する。また分岐履歴収集開始制御部２１４は、ヒット信号ｈｉｔａ２がアクティブのとき、選択出力ＣＮＴｓ２と閾値ＴＨ１とを比較し、選択出力ＣＮＴｓ２が閾値ＴＨ以上のとき分岐履歴イネーブルをアクティブ（例えば「１」）に設定する。更に分岐履歴収集開始制御部２１４は、ヒット信号ｈｉｔａ１、ｈｉｔａ２が共に非アクティブのとき、分岐履歴収集イネーブルを非アクティブに設定する。
【０１２４】
図１６、図１７（Ａ）、図１７（Ｂ）に、本実施形態における分岐履歴テーブル３２０と分岐履歴管理部２２０の要部の構成例を示す。
【０１２５】
分岐履歴テーブル３２０は、２ウェイ−セットアソシアティブ方式で、基本ブロックの先頭アドレスＢＳＡ、当該基本ブロックの分岐命令の分岐先アドレスＢＴＡ、該分岐先アドレスへの分岐回数ＣＯＵＮＴを記憶する。なお、図１６では、分岐履歴テーブル３２０に分岐命令のアドレスＢＩＡが記録されないものとする。両方のウェイは同様の構成を有し、各ウェイの記憶情報は公知のＬＲＵ方式でリプレース制御されるようになっている。
【０１２６】
先頭アドレスＢＳＡの例えば下位ビットがデコーダＤＥＣ３、ＤＥＣ４に入力される。各デコーダは、各ウェイのテーブルの１エントリを先頭アドレスＢＳＡの下位ビットに基づいて選択する。各ウェイにおいて選択されたエントリの先頭アドレスＢＳＡ、分岐先アドレスＢＴＡ及び分岐回数ＣＯＵＮＴが読み出される。こうして読み出された先頭アドレスは、先頭アドレスレジスタＢＳＡ３、ＢＳＡ４、分岐先アドレスは、分岐先アドレスレジスタＢＴＡ３、ＢＴＡ４、分岐回数は、分岐回数レジスタＣＮＴ３、ＣＮＴ４で保持される。
【０１２７】
コンパレータＣＭＰ３は、先頭アドレスＢＳＡと先頭アドレスレジスタＢＳＡ３の値と比較し、一致したときにヒット信号ｈｉｔｂ１をアクティブ（例えば「１」）にする。コンパレータＣＭＰ４は、先頭アドレスＢＳＡと先頭アドレスレジスタＢＳＡ４の値と比較し、一致したときにヒット信号ｈｉｔｂ２をアクティブ（例えば「１」）にする。
【０１２８】
分岐回数レジスタＣＮＴ３の値は、インクリメンタＩＮＣ３（広義にはカウンタ）でインクリメントされる。分岐回数レジスタＣＮＴ４の値は、インクリメンタＩＮＣ４（広義にはカウンタ）でインクリメントされる。
【０１２９】
セレクタＳＥＬ３は、選択制御信号ｓｅｌ３に基づいて、分岐先アドレスレジスタＢＴＡ３又は分岐先アドレスレジスタＢＴＡ４の値を選択出力して、ホットパス情報として追加されると共に、次の基本ブロックの先頭アドレスとして分岐履歴テーブル３２０に入力される。
【０１３０】
セレクタＳＥＬ４は、選択制御信号ｓｅｌ４に基づいて、分岐回数レジスタＣＮＴ３の値又はインクリメンタＩＮＣ３の出力を選択して、選択出力ＣＮＴｓ３を出力する。そして、選択出力ＣＮＴｓ３により、デコーダＤＥＣ３で選択されたエントリの分岐回数ＣＯＵＮＴを更新する。セレクタＳＥＬ５は、選択制御信号ｓｅｌ５に基づいて、分岐回数レジスタＣＮＴ４の値又はインクリメンタＩＮＣ４の出力を選択して、選択出力ＣＮＴｓ４を出力する。そして、選択出力ＣＮＴｓ４により、デコーダＤＥＣ４で選択されたエントリの分岐回数ＣＯＵＮＴを更新する。
【０１３１】
図１７（Ａ）に示すように、分岐履歴管理部２２０又は分岐履歴テーブル３２０は、ヒット判定部２２２を含む。ヒット判定部２２２には、ヒット信号ｈｉｔｂ１、ｈｉｔｂ２、選択出力ＣＮＴｓ３、ＣＮＴｓ４が入力され、選択制御信号ｓｅｌ３、ｓｅｌ４、ｓｅｌ５、ライトイネーブルｗｅ３、ｗｅ４を出力する。
【０１３２】
図１７（Ｂ）に、図１７（Ａ）のヒット判定部２２２の動作説明図を示す。
【０１３３】
ヒット判定部２２２は、ヒット信号ｈｉｔｂ１がアクティブのとき、選択制御信号ｓｅｌ４をアクティブにしてインクリメンタＩＮＣ３の出力で分岐履歴テーブル３２０を更新するように制御する。またヒット判定部２２２は、ヒット信号ｈｉｔｂ２がアクティブのとき、選択制御信号ｓｅｌ５をアクティブにしてインクリメンタＩＮＣ４の出力で分岐履歴テーブル３２０を更新するように制御する。
【０１３４】
更に、ヒット判定部２２２は、ヒット信号ｈｉｔｂ１、ｈｉｔｂ２がアクティブのとき、分岐回数の大きい方のウェイを選択する。そのため、ヒット判定部２２２は、選択出力ＣＮＴｓ３が選択出力ＣＮＴｓ４以上のとき、選択制御信号ｓｅｌ４をアクティブに設定すると共に、選択制御信号ｓｅｌ５を非アクティブに設定する。またヒット判定部２２２は、選択出力ＣＮＴｓ３が選択出力ＣＮＴｓ４より小さいとき、選択制御信号ｓｅｌ４を非アクティブに設定すると共に、選択制御信号ｓｅｌ５をアクティブに設定する。更に、ヒット判定部２２２は、選択制御信号ｓｅｌ４と同様の制御で選択制御信号ｓｅｌ３を出力する。
【０１３５】
更にまた、ヒット判定部２２２は、ヒット信号ｈｉｔｂ１、ｈｉｔｂ２が非アクティブのとき、セレクタＳＥＬ３、ＳＥＬ４でいずれも出力されないように制御すると共に、ＬＲＵ制御ビットＬＲＵ３、ＬＲＵ４を用いてＬＲＵ制御を行い、今回入力された先頭アドレスＢＳＡを書き込むためのライトイネーブルｗｅ３、ｗｅ４の一方をアクティブにする。ライトイネーブルｗｅ３がアクティブのとき、先頭アドレスＢＳＡがデコーダＤＥＣ３で選択されたエントリに書き込まれると共に、分岐回数ＣＯＵＮＴとして「１」が書き込まれる。ライトイネーブルｗｅ４がアクティブのとき、先頭アドレスＢＳＡがデコーダＤＥＣ４で選択されたエントリに書き込まれると共に、分岐回数ＣＯＵＮＴとして「１」が書き込まれる。
【０１３６】
以上のように、分岐履歴テーブル３２０が、記憶情報をセットアソシアティブ方式で記憶し、各ウェイ（セット）には、基本ブロックの先頭アドレス、当該基本ブロックに含まれる分岐命令の分岐先アドレス（ターゲットアドレス）、及び分岐回数が記憶される。そして、該分岐命令に対応して記憶された分岐命令のうち分岐回数が最も多いウェイ（セット）の分岐命令の分岐先アドレスを出力できる。
【０１３７】
３．  その他
本発明は上記の実施形態に限定されるものではない。
【０１３８】
図１８に、図１の情報処理装置の変形例のブロック図を示す。
【０１３９】
図１８において図１と同一部分には同一符号を付し、適宜説明を省略する。本変形例における情報処理装置５００は、ホットパス処理部１２０が情報処理装置５００内に設けられる。そして、ホットパス処理部１２０が、プロファイラ３０からのホットパス情報に基づいて最適化処理を行い、最適化処理結果をアクセラレータ２０に出力する。ここで、最適化処理結果は、ホットパス中の命令列のうち不要なコードが削除された命令列、ホットパス中の命令列を並列動作させるために変更した命令列、又はアクセラレータ２０のハードウェア構成を変更するためのハードウェア構成情報等である。
【０１４０】
なお、本発明は上述した実施の形態に限定されるものではなく、本発明の要旨の範囲内で種々の変形実施が可能である。
【０１４１】
また、本発明のうち従属請求項に係る発明においては、従属先の請求項の構成要件の一部を省略する構成とすることもできる。また、本発明の１の独立請求項に係る発明の要部を、他の独立請求項に従属させることもできる。
【図面の簡単な説明】
【０１４２】
【図１】本実施形態における情報処理装置の構成例のブロック図。
【図２】本実施形態における基本ブロックの説明図。
【図３】図１の情報処理装置の処理の一例の概要のフローを示す図。
【図４】本実施形態における高頻度で繰り返し実行される実行命令部分の説明図。
【図５】図３のホットパスの説明図。
【図６】図１のプロファイラの構成の概要を示す図。
【図７】図６の実行履歴テーブルの構成の概要を示す図。
【図８】図６の分岐履歴テーブルの構成の概要を示す図。
【図９】図９（Ａ）、図９（Ｂ）は本実施形態における管理テーブル部の説明図。
【図１０】本実施形態におけるプロファイラの処理の概要のフローを示す図。
【図１１】実行履歴管理部の処理例のフロー図。
【図１２】分岐履歴管理部の処理例のフロー図。
【図１３】本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図１４】図１４（Ａ）、図１４（Ｂ）は本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図１５】図１５（Ａ）、図１５（Ｂ）は本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図１６】本実施形態における分岐履歴テーブルと分岐履歴管理部の要部の構成例を示す図。
【図１７】本実施形態における分岐履歴テーブルと分岐履歴管理部の要部の構成例を示す図。
【図１８】図１の情報処理装置の変形例のブロック図。
【符号の説明】
【０１４３】
１０  ＣＰＵ
２０  アクセラレータ
３０  プロファイラ
５０  バス
１００、５００  情報処理装置
１１０  メモリ
１２０  ホットパス処理部
２００  制御部
２１０  実行履歴管理部
２１２、２２２  ヒット判定部
２１４  実行履歴収集開始制御部
２１６  閾値設定レジスタ
２２０  分岐履歴管理部
３００  管理テーブル部
３１０  実行履歴テーブル
３２０  分岐履歴テーブル
【図１】
2008250867.tif 000003
【図２】
2008250867.tif 000004
【図３】
2008250867.tif 000005
【図４】
2008250867.tif 000006
【図５】
2008250867.tif 000007
【図６】
2008250867.tif 000008
【図７】
2008250867.tif 000009
【図８】
2008250867.tif 000010
【図９】
2008250867.tif 000011
【図１０】
2008250867.tif 000012
【図１１】
2008250867.tif 000013
【図１２】
2008250867.tif 000014
【図１３】
2008250867.tif 000015
【図１４】
2008250867.tif 000016
【図１５】
2008250867.tif 000017
【図１６】
2008250867.tif 000018
【図１７】
2008250867.tif 000019
【図１８】
2008250867.tif 000020