TOP > 国内特許検索 > 実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体 > 明細書

明細書 :実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4892387号 (P4892387)
公開番号 特開2008-250867 (P2008-250867A)
登録日 平成23年12月22日(2011.12.22)
発行日 平成24年3月7日(2012.3.7)
公開日 平成20年10月16日(2008.10.16)
発明の名称または考案の名称 実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体
国際特許分類 G06F  11/34        (2006.01)
G06F  11/28        (2006.01)
FI G06F 11/34 N
G06F 11/28 310E
G06F 11/34 C
請求項の数または発明の数 19
全頁数 24
出願番号 特願2007-094075 (P2007-094075)
出願日 平成19年3月30日(2007.3.30)
審査請求日 平成21年9月2日(2009.9.2)
特許権者または実用新案権者 【識別番号】391043332
【氏名又は名称】財団法人福岡県産業・科学技術振興財団
【識別番号】504145342
【氏名又は名称】国立大学法人九州大学
【識別番号】000005223
【氏名又は名称】富士通株式会社
発明者または考案者 【氏名】吉松 則文
【氏名】吉田 真
【氏名】村上 和彰
【氏名】須賀 敦浩
個別代理人の代理人 【識別番号】100124626、【弁理士】、【氏名又は名称】榎並 智和
審査官 【審査官】和田 財太
参考文献・文献 特開2005-092532(JP,A)
特開平10-320196(JP,A)
安江俊明(外3名),動的コンパイラにおける実行時経路情報の構造的収集手法の提案,情報処理学会論文誌,日本,社団法人情報処理学会,2003年11月15日,Vol.44,No.SIG15,p.24-p.35
増保智久(外5名),MediaBenchホットループ並列化のためのパスプロファイリング,第67回(平成17年)全国大会講演論文集(1) アーキテクチャ ソフトウェア科学・工学,日本,社団法人情報処理学会,2005年 3月 2日,p.1-203~p.1-204
野中雄一(外3名),パスプロファイルによるホットパス検出とオーバーヘッドの評価,情報処理学会研究報告,日本,社団法人情報処理学会,2002年 8月23日,Vol.2002,No.81,p.103-p.108
林田隆則(外1名),「プログラム実行の局所性」の活用法に関する検討,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2000年 7月26日,Vol.100,No.248,p.65-p.72
増保智久(外4名),動的最適化を支援する2レベルホットパス検出機構の設計,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2006年 7月26日,Vol.106,No.199,p.13-p.18
江島和仁(外2名),動的システム最適化技術SysteMorphの性能評価,情報処理学会研究報告,日本,社団法人情報処理学会,2006年 1月24日,Vol.2006,No.8,p.19-p.24
調査した分野 G06F 11/28-11/34
特許請求の範囲 【請求項1】
実行頻度が高い命令列の実行パスを検出するための実行パス検出装置であって、
分岐命令を含む命令列を1ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブルと、
前記分岐命令の分岐履歴が格納される分岐履歴テーブルと、
前記分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部とを含み、
前記実行回数が所与の閾値を超えたことを条件に、前記分岐履歴管理部が、前記分岐履歴の収集を開始すると共に、前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力することを特徴とする実行パス検出装置。
【請求項2】
請求項1において、
前記命令列ブロックの先頭アドレスの命令の実行回数をカウントするカウンタを含み、
前記実行履歴テーブルは、
前記先頭アドレスの命令毎に、実行回数を記憶することを特徴とする実行パス検出装置。
【請求項3】
請求項1又は2において、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していることを特徴とする実行パス検出装置。
【請求項4】
請求項1又は2において、
前記分岐履歴テーブルに登録すべき情報の少なくとも一部が、前記実行履歴テーブルの記憶領域に書き込まれることを特徴とする実行パス検出装置。
【請求項5】
請求項1乃至4のいずれかにおいて、
前記実行履歴テーブルに、
分岐命令の戻り方向の分岐先アドレスの命令の実行回数が格納されることを特徴とする実行パス検出装置。
【請求項6】
請求項1乃至5のいずれかにおいて、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記分岐履歴管理部が、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することを特徴とする実行パス検出装置。
【請求項7】
請求項1乃至6のいずれかにおいて、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することを特徴とする実行パス検出装置。
【請求項8】
請求項1乃至7のいずれかにおいて、
前記分岐履歴管理部が、
前記分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することを特徴とする実行パス検出装置。
【請求項9】
請求項1乃至8のいずれかにおいて、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴管理部が、
前記分岐履歴テーブルの記憶情報を無効化することを特徴とする実行パス検出装置。
【請求項10】
請求項1乃至9のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置とを含み、
前記実行パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理が最適化されることを特徴とする情報処理装置。
【請求項11】
請求項1乃至9のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置と、
前記実行パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理を最適化するパス処理部とを含むことを特徴とする情報処理装置。
【請求項12】
実行履歴テーブルと、分岐履歴テーブルと、制御部とを有する情報処理装置において、実行頻度が高い命令列の実行パスを検出するための実行パス検出方法であって、
前記制御部が、分岐命令を含む命令列を1ブロックとする命令列ブロックの先頭アドレスの命令の実行回数を前記実行履歴テーブルに登録するステップと、
前記制御部が、前記実行回数が所与の閾値を超えたことを条件に前記分岐命令の分岐履歴の収集を開始し、該分岐履歴を前記分岐履歴テーブルに登録するステップと、
前記制御部が、前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力するステップとを含むことを特徴とする実行パス検出方法。
【請求項13】
請求項12において、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していることを特徴とする実行パス検出方法。
【請求項14】
請求項12又は13において、
前記先頭アドレスが、
分岐命令の戻り方向の分岐先アドレスであり、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記制御部が、前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することを特徴とする実行パス検出方法。
【請求項15】
請求項12乃至14のいずれかにおいて、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することを特徴とする実行パス検出方法。
【請求項16】
請求項12乃至15のいずれかにおいて、
前記制御部が、該分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することを特徴とする実行パス検出方法。
【請求項17】
請求項12乃至16のいずれかにおいて、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記制御部が、前記分岐履歴テーブルの記憶情報を無効化することを特徴とする実行パス検出方法。
【請求項18】
コンピュータに、請求項12乃至17のいずれか記載の実行パス検出方法を実行させるためのプログラム。
【請求項19】
請求項18記載のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体に関する。
【背景技術】
【0002】
アプリケーションプログラムを実行するプロセッサの処理の高速化や低消費電力化を実現するために、プログラムの局所性に着目した手法が提案されている。この手法は、プログラムを実行する上でクリティカルな命令列を発見し、該命令列の処理の最適化を図ることで処理の高速化や低消費電力化を実現するものである。このようなクリティカルな命令列を発見する手法として、命令列に含まれる分岐命令の実行履歴を利用する手法がある。
【0003】
例えば特許文献1には、命令列の命令が実行される方向とは逆方向である戻り方向に分岐する分岐命令の実行回数に着目してループ構造の命令部分を検出し、ループ構造の命令の実行回数が多いと判断されるパス経路を記録する分岐履歴記録装置が開示されている。即ち、特許文献1では、プログラムのループ構造の部分に局所性が存在するという仮定の下で、該パス経路を実行頻度の高い命令列の実行パスとして検出する。
【0004】
また、例えば特許文献2には、分岐命令の分岐履歴が格納されるプロファイラテーブルと、戻り方向の分岐先アドレス及び分岐回数が格納される戻り分岐先テーブルとを設け、戻り分岐先テーブルの分岐先アドレスとプロファイラテーブルに格納された分岐履歴とに基づいて、実行頻度の高い命令列の実行パスを検出する推定装置が開示されている。

【特許文献1】特開2000-148482号公報
【特許文献2】特開2005-92532号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
しかしながら、特許文献1に開示された分岐履歴記録装置では、ソフトウェアで処理する必要がある。そのため、実行頻度の高い命令列の実行パスを検出するための処理時間が長くなり、プロセッサの処理中に、所望の命令列の実行パスを特定することが困難であるという問題がある。
【0006】
また、特許文献2に開示された推定装置では、膨大な分岐履歴や分岐先アドレスを記録しておく必要があり、分岐履歴や分岐先アドレス等を記憶する記憶領域が膨大になってしまうという問題がある。このような推定装置において、記憶領域を少なくしようとすると、退避等の必要性から処理が中断されてしまい、所望の命令列の実行パスを検出するための処理時間が長くなる。更に、特許文献2におけるSWプロファイラ部による処理が複雑であるため、ハードウェア化が困難であり、ソフトウェアで実現せざるを得なくなる。従って、特許文献1と同様に、プロセッサの処理中に、所望の命令列の実行パスを特定することは困難となる。
【0007】
本発明は、以上のような技術的課題に鑑みてなされたものであり、その目的とするところは、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置、情報処理装置、実行パス検出方法、その実行パス検出方法をコンピュータに実現させるプログラム、及び該プログラムを記録する記録媒体を提供することにある。
【課題を解決するための手段】
【0008】
上記課題を解決するために本発明は、
実行頻度が高い命令列の実行パスを検出するための実行パス検出装置であって、
分岐命令を含む命令列を1ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブルと、
前記分岐命令の分岐履歴が格納される分岐履歴テーブルと、
前記分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部とを含み、
前記実行回数が所与の閾値を超えたことを条件に、前記分岐履歴管理部が、前記分岐履歴の収集を開始すると共に、前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力する実行パス検出装置に関係する。
【0009】
また本発明に係る実行パス検出装置では、
前記命令列ブロックの先頭アドレスの命令の実行回数をカウントするカウンタを含み、
前記実行履歴テーブルは、
前記先頭アドレスの命令毎に、実行回数を記憶することができる。
【0010】
上記のいずれかの発明によれば、アプリケーションプログラムの局所性に着目して、高頻度で実行される命令列の繰り返し部分を検出してから、該繰り返し部分の分岐履歴を収集するようにしたので、アプリケーションプログラムにおいて実行頻度が高い命令列の実行パスを検出する際に膨大な分岐履歴を収集する必要がなくなる。そのため、本発明によれば、実行パスの検出精度の低下を抑えつつ、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できるようになる。
【0011】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していてもよい。
【0012】
また本発明に係る実行パス検出装置では、
前記分岐履歴テーブルに登録すべき情報の少なくとも一部が、前記実行履歴テーブルの記憶領域に書き込まれてもよい。
【0013】
上記のいずれかの発明においては、まず実行履歴テーブルを用いて高頻度で実行される命令列の繰り返し部分を検出してから、分岐履歴テーブルに該繰り返し部分の分岐履歴を収集する。そのため、分岐履歴を収集する段階では実行履歴テーブルを不要にできるため、本発明によれば、実行履歴テーブルと分岐履歴テーブルの記憶領域を共用するようにしたので、両テーブルのために必要な記憶容量の削減を図ることができる。
【0014】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルに、
分岐命令の戻り方向の分岐先アドレスの命令の実行回数が格納されてもよい。
【0015】
本発明によれば、戻り方向の分岐命令の実行履歴のみを収集するようにしたので、少ないメモリ容量で、高頻度で繰り返される実行部分を検出できるようになる。
【0016】
また本発明に係る実行パス検出装置では、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記分岐履歴管理部が、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することができる。
【0017】
本発明によれば、実行履歴テーブルを用いて検出した高頻度の繰り返し部分の分岐履歴の収集を行うことができるので、少ないメモリ容量で分岐履歴テーブルを構成できるようになる。
【0018】
また本発明に係る実行パス検出装置では、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することができる。
【0019】
また本発明に係る実行パス検出装置では、
前記分岐履歴管理部が、
前記分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することができる。
【0020】
上記のいずれかの発明によれば、分岐履歴テーブルに基づいてターゲットアドレス出力できるので、無駄なソフトウェア処理を省略して、高速に、実行パスを特定できるようになる。
【0021】
また本発明に係る実行パス検出装置では、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴管理部が、
前記分岐履歴テーブルの記憶情報を無効化することができる。
【0022】
本発明によれば、分岐履歴の収集を開始した後に、高頻度で繰り返される実行が行われなかったことを検出して分岐履歴テーブルを無効化するようにしたので、無駄にパス情報を収集する必要がなくなる。
【0023】
また本発明は、
上記のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置とを含み、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理が最適化される情報処理装置に関係する。
【0024】
また本発明は、
上記のいずれか記載の実行パス検出装置と、
アプリケーションプログラムを実行処理する中央演算処理装置と、
前記パス検出装置からの前記パス情報に基づいて、前記アプリケーションプログラムの処理を最適化するパス処理部とを含む情報処理装置に関係する。
【0025】
上記のいずれかの発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置が適用され、処理が最適化された情報処理装置を提供できる。
【0026】
また本発明は、
実行頻度が高い命令列の実行パスを検出するための実行パス検出方法であって、
分岐命令を含む命令列を1ブロックとする命令列ブロックの先頭アドレスの命令の実行回数を実行履歴テーブルに記憶するステップと、
前記実行回数が所与の閾値を超えたことを条件に前記分岐命令の分岐履歴の収集を開始し、該分岐履歴を分岐履歴テーブルに記憶するステップと、
前記実行パスを特定するためのパス情報を、前記分岐履歴に基づいて出力するステップとを含む実行パス検出方法に関係する。
【0027】
また本発明に係る実行パス検出方法では、
前記実行履歴テーブルの記憶領域の少なくとも一部が、前記分岐履歴テーブルの記憶領域と重複していてもよい。
【0028】
また本発明に係る実行パス検出方法では、
前記先頭アドレスが、
分岐命令の戻り方向の分岐先アドレスであり、
前記実行履歴テーブルが、前記先頭アドレス及び前記実行回数を記憶し、
前記閾値を超えた前記実行回数に関連付けて記憶される先頭アドレスを用いて、前記分岐履歴の収集を開始することができる。
【0029】
また本発明に係る実行パス検出方法では、
前記分岐履歴テーブルが、
記憶情報をセットアソシアティブ方式で記憶し、
各セットには、
前記先頭アドレス、当該命令列ブロックに含まれる分岐命令のターゲットアドレス、及び分岐回数が記憶され、
該分岐命令に対応して記憶されたターゲットアドレスのうち分岐回数が最も多いセットのターゲットアドレスを出力することができる。
【0030】
また本発明に係る実行パス検出方法では、
該分岐命令の分岐先アドレスをインデックスとして前記分岐履歴テーブルを検索して得られたターゲットアドレスをパス情報として出力することができる。
【0031】
また本発明に係る実行パス検出方法では、
前記分岐命令の分岐先が前記実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、
前記分岐履歴テーブルの記憶情報を無効化することができる。
【0032】
上記のいずれかの発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法を提供できる。
【0033】
また本発明は、
コンピュータに、上記のいずれか記載の実行パス検出方法を実行させるためのプログラムに関係する。
【0034】
本発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法をコンピュータに実現させるプログラムを提供できる。
【0035】
また本発明は、
上記記載のプログラムを記録したコンピュータ読み取り可能な記録媒体に関係する。
【0036】
本発明によれば、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出方法をコンピュータに実現させるプログラムを記録した記録媒体を提供できる。
【発明を実施するための最良の形態】
【0037】
以下、本発明の実施の形態について図面を用いて詳細に説明する。なお、以下に説明する実施の形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また以下で説明される構成のすべてが本発明の必須構成要件であるとは限らない。
【0038】
1. 情報処理装置
図1に、本実施形態における情報処理装置の構成例のブロック図を示す。
【0039】
情報処理装置100は、中央演算処理装置(Central Processing Unit:CPU)10と、アクセラレータ20と、プロファイラ(実行パス推定装置、実行パス検出装置)30とを含む。情報処理装置100は、バス50を含み、バス50を介して、CPU10、アクセラレータ20及びプロファイラ30との間でデータやアドレスのやり取りが行われる。また、情報処理装置100の外部には、メモリバス52を介してバス50と接続されるメモリ110が設けられており、CPU10、アクセラレータ20及びプロファイラ30はバス50及びメモリバス52を介してメモリ110にアクセスできるようになっている。
【0040】
CPU10は、CPU10の内蔵メモリ又はメモリ110に格納されたアプリケーションプログラムを読み込んで、該プログラムに対応した命令を実行する。
【0041】
アクセラレータ20は、CPU10に代わってCPU10が実行すべき処理を行う。アクセラレータ20の処理時間は、CPU10の処理時間より短い。アクセラレータ20の機能は、ハードウェア又はソフトウェアにより実現される。アクセラレータ20の機能がソフトウェアにより実現される場合には、アクセラレータ20がCPU及びメモリを有し、該メモリ又は図1のメモリ110に格納されたアクセラレータ用プログラムを読み込んで該プログラムに対応した処理を実行するCPUによりアクセラレータ20の機能が実現される。
【0042】
このようなアクセラレータ20は、例えば、より処理時間が短くなるように、又はより低消費電力となるように、CPU10が処理すべきプログラムの命令列を最適化させた状態で該プログラムの処理結果を生成する。アクセラレータ20は、例えばCPU10が処理すべきプログラムのうち不要な命令列が削除された命令列を実行することで、該プログラムを実行した場合のCPU10の処理結果と同じ結果をより短時間で得られるようになっている。また、例えばアクセラレータ20は、CPU10が処理すべきプログラムの命令列を並列に処理することで、該プログラムを実行した場合のCPU10の処理結果と同じ結果をより短時間で得られるようになっている。
【0043】
プロファイラ(広義には実行パス検出装置)30は、プログラムの実行中に実行頻度の高いループ構造のパス(実行パス、命令パス、ホットパス)を高精度で検出(推定)し、検出したパスを特定するための情報であるホットパス情報(広義にはパス情報)を出力する。プロファイラ30は、CPU10が実行するプログラムを構成する命令列のうち繰り返し実行される命令列を検出し、繰り返し実行される命令列の分岐履歴に基づいて実行頻度の高いパスを特定する処理を行う。
【0044】
更に情報処理装置100の外部には、ホットパス処理部120が設けられている。ホットパス処理部120は、プロファイラ30からのホットパス情報に基づいて実行頻度の高いループ構造のパスを特定し、このパスの処理を最適化することで情報処理装置100の処理時間を短縮させたり情報処理装置100の処理中の消費電力を低減させたりする。
【0045】
例えば、ホットパス処理部120は、プロファイラ30からのホットパス情報に基づいて特定した命令列のパスを並列処理させるように命令列を最適化したり、実行不要な命令を削除して命令列を最適化したりする。このとき、ホットパス処理部120は、最適化処理後の命令列をアクセラレータ20や該アクセラレータ20がアクセスするメモリに格納する。
【0046】
或いは、例えばホットパス処理部120は、プロファイラ30からのホットパス情報に基づいて特定した命令列のパスの処理時間が短くなるようにアクセラレータ20のハードウェア構成を変更したり、或いは該パスを処理する上で情報処理装置100の消費電力が低減するようにアクセラレータ20のハードウェア構成を変更したりする処理を行う。この場合、アクセラレータ20は動的再構成可能な回路であり、ホットパス処理部120が、動的再構成に必要なハードウェア構成情報をアクセラレータ20に供給する。
【0047】
次に、図1の情報処理装置100の処理の概要について説明する。
【0048】
本実施形態では、基本ブロックと呼ばれる命令列ブロックを単位に、命令列の実行パスを考える。
【0049】
図2に、本実施形態における基本ブロックの説明図を示す。
【0050】
アプリケーションプログラムを構成する命令列の実行パスを考えると、アプリケーションプログラムを構成する命令は、プログラムの実行の流れを変える分岐命令と、分岐命令以外の他の命令とに区別できる。そして、プログラムを構成する命令が、アドレス値の小さい命令からアドレス値の大きい命令の方向に順番に実行されるため、実行の流れを変える分岐命令毎に、命令列のブロックを区分できる。このブロックが、基本ブロックである。基本ブロックは、例えば直前の基本ブロックの最後の分岐命令の次の命令から始まり、アドレス値の大きい方向に命令が実行されたときの最初の分岐命令で終わる命令列のブロックである。
【0051】
図2では、基本ブロックBB1、BB2、・・・、BBK(Kは3以上の正の整数)が示されている。基本ブロックBB1は、このブロックの先頭アドレスBSA1の命令“inst1”に始まり、命令の実行方向に順次命令が実行され、アドレスBIA1の分岐命令“bne”で終わる。ここで分岐命令“bne”が条件分岐命令であるとすると、条件が「真」のときの分岐先アドレスがBSA3、条件が「偽」のときの分岐先アドレスがアドレスBIA1の次のアドレスであるBSA2である。
【0052】
基本ブロックBB2は、このブロックの先頭アドレスBSA2の命令“inst2”に始まり、命令の実行方向に順次命令が実行され、アドレスBIA2の分岐命令“br”で終わる。アドレスBSA2は、アドレスBIA1の分岐命令の分岐先アドレスであるため、アドレスBSA2は分岐ターゲットアドレスBTA1である。
【0053】
基本ブロックBB3は、このブロックの先頭アドレスBSA3の命令“inst3”に始まり、命令の実行方向に順次命令が実行され、同様にアドレスBIA3の分岐命令(図示せず)で終わる。アドレスBSA3は、アドレスBIA1の分岐命令の分岐先アドレスであるため、アドレスBSA3の分岐ターゲットアドレスBTA2である。
【0054】
従って、命令の実行パスを、基本ブロックBB1、BB2のパスとして表したり、基本ブロックBB1、BB3のパスとして表したりすることができる。
【0055】
図3に、図1の情報処理装置100の処理の一例の概要のフローを示す。
【0056】
まず、情報処理装置100のプロファイラ30は、アプリケーションプログラムを実行するCPU10の実行履歴を収集し、アプリケーションプログラムを構成する命令列のうち高頻度で繰り返し実行される実行命令部分を検出する(ステップS10)。このとき、アプリケーションプログラムを構成する命令列が、それぞれ1つの分岐命令を含む基本ブロックに区分でき、基本ブロック間の流れでプログラムの実行パスを特定できる。その結果、図4に示すように、例えば基本ブロックFから基本ブロックAに戻るパスが高頻度で繰り返し実行される実行命令部分として検出される。なお、図4では、基本ブロックA~Fが示されており、基本ブロックAから基本ブロックB~Gのいずれかの方向にプログラムの実行が流れるものとする。
【0057】
図3に示すように、次に、情報処理装置100は、ステップS10で検出した実行頻度の高い実行命令部分の分岐履歴の収集を開始する。そして、情報処理装置100は、収集した分岐履歴情報に基づいてパスを特定するホットパス情報を出力する(ステップS11)。
【0058】
ホットパス処理部120は、プロファイラ30からのホットパス情報を受けて、上述のようにホットパスの処理の最適化を行い(ステップS12)、一連の処理を終了する(エンド)。
【0059】
図5に、図3のホットパスの説明図を示す。
【0060】
図5において、図4と同じ基本ブロックA~Fが示されている。各基本ブロックは、当該基本ブロックの先頭アドレス(Basic block Start Address:BSA)の命令FIと、当該基本ブロックの最終アドレスである分岐命令アドレス(Branch Instruction Address:BIA)の分岐命令BIとを含む。各基本ブロック間を接続する矢印は、分岐命令により処理の流れが変えられたことを示し、この矢印に付される数値は該分岐命令による分岐回数を示す。
【0061】
例えば基本ブロックAの分岐命令BIの分岐先が2つあり、該分岐命令BIが条件分岐命令であることを示す。基本ブロックAから基本ブロックBへの矢印は、例えば基本ブロックAの分岐命令BIの条件が「真」のときの分岐先アドレスが基本ブロックBの先頭アドレスBSAであることを示す。そして、基本ブロックAから基本ブロックBへの処理の流れの変更が、履歴として800回であったことを意味している。また、基本ブロックAから基本ブロックCへの矢印は、例えば基本ブロックAの分岐命令BIの条件が「偽」のときの分岐先アドレスが基本ブロックCの先頭アドレスBSAであることを示す。そして、基本ブロックAから基本ブロックCへの処理の流れの変更が、履歴として200回であったことを意味している。
【0062】
これに対して、例えば基本ブロックDの分岐命令BIの分岐先は1つであり、該分岐命令BIが無条件分岐命令であることを示す。この無条件分岐は、履歴として700回であることを意味する。
【0063】
以上のような履歴を履歴情報として収集するため、基本ブロックの開始アドレスBSA、分岐先アドレスBTA(Branch Target Address)(広義にはターゲットアドレス)、分岐命令のアドレスBIA、分岐回数がテーブルを用いて管理される。そして、各基本ブロック間の分岐回数が多いルートがホットパスとして特定される。図5では、基本ブロックA、B、D、Fのルートがホットパスとなり、ホットパス情報として、基本ブロックA、B、D、Fの各基本ブロックの先頭アドレス列を出力することでホットパスが特定される。
【0064】
その結果、基本ブロックA、B、D、Fのパスの命令列の最適化により一層高い負荷をかける等して情報処理装置100の処理を重点的に最適化することができる。
【0065】
このように、本実施形態においては、プログラムの局所性に着目して、高頻度で実行される命令列の繰り返し部分を検出してから、該繰り返し部分の分岐履歴を収集するようにしたので、アプリケーションプログラムのホットパスを検出する際に膨大な分岐履歴を収集する必要がなくなる。そのため、本実施形態によれば、パスの検出精度の低下を抑えつつ、少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できるようになる。
【0066】
2. プロファイラの説明
次に、このようなホットパスの検出を行う図1のプロファイラ30について説明する。
【0067】
図6に、図1のプロファイラ30の構成の概要を示す。
【0068】
プロファイラ30は、制御部200と、管理テーブル部300とを含む。制御部200は、実行履歴管理部210、分岐履歴管理部220を含む。管理テーブル部300は、実行履歴テーブル310、分岐履歴テーブル320を含む。
【0069】
なお、制御部200の機能は、ソフトウェアで実現されてもよいし、専用のハードウェアにより実現されてもよい。制御部200がソフトウェアで実現される場合、後述する実行パスの検出方法を実現するプログラムを読み込んだプロファイラ30のCPUが処理を行う。また、管理テーブル部300は、後述するように実行履歴テーブル310と分岐履歴テーブル320の記憶領域を共用することが望ましい。
【0070】
実行履歴管理部210は、実行履歴テーブル310を管理する制御を行う。
【0071】
図7に、図6の実行履歴テーブル310の構成の概要を示す。
【0072】
実行履歴テーブル310は、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスBSAに関連付けて(対応して)、該先頭アドレスBSAの命令の実行回数COUNTが記憶される。即ち、基本ブロックの先頭アドレスBSAの命令の実行回数がカウントされ、実行履歴テーブル310には、基本ブロックの先頭アドレスの命令毎に、実行回数が記憶される。
【0073】
ここで、先頭アドレスBSAは、分岐命令の戻り方向の分岐先アドレスである。そのため、実行履歴テーブル310には、基本ブロックの先頭アドレスBSAではなく、該先頭アドレスBSAを戻り方向の分岐先アドレスとして登録してもよい。このように戻り方向の分岐命令の実行履歴のみを収集することで、少ないメモリ容量で、高頻度で繰り返される実行部分を検出できるようになる。
【0074】
そこで、実行履歴管理部210は、分岐命令を含む命令列を1ブロックとする基本ブロック(命令列ブロック)の先頭アドレスBSA、該先頭アドレスBSAの命令の実行回数を実行履歴テーブル310に登録、追加、検索等をする管理制御を行う。
【0075】
図6において、分岐履歴管理部220は、実行履歴テーブル310で管理される基本ブロックの先頭アドレスのうちいずれかの先頭アドレスの命令の実行回数が所与の閾値TH1を超えたことを条件に、分岐命令の分岐履歴の収集を開始し、その後、分岐履歴を収集する処理を行う。
【0076】
図8に、図6の分岐履歴テーブル320の構成の概要を示す。
【0077】
分岐履歴テーブル320は、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスBSAに関連付けて、分岐命令のアドレスBIA、該分岐命令の分岐先アドレスBTA、該分岐命令の分岐回数COUNTが記憶される。ここで、先頭アドレスBSAは、分岐命令の戻り方向の分岐先アドレスであったり、分岐命令の順方向の分岐先アドレスであったりする。
【0078】
そこで、分岐履歴管理部220は、基本ブロックの先頭アドレスBSA、分岐命令のアドレス、該分岐命令の分岐先アドレス、分岐回数を分岐履歴テーブル320に登録、追加、検索等をする管理制御を行う。また分岐履歴管理部220は、分岐履歴テーブル320に登録された分岐履歴に基づいてホットパス情報(実行頻度の高い実行パスを特定するためのパス情報)を出力する。
【0079】
なお、図8において、分岐履歴テーブル320に分岐命令のアドレスBIAを記憶させなくてもよい。しかしながら、分岐履歴テーブル320に分岐命令のアドレスBIAを記憶させることで、分岐先アドレスBTAの情報として分岐命令のアドレスBIAを基準としたオフセット情報を用いることができるので、分岐先アドレスBTAの記憶領域を削減できるようになる。
【0080】
ところで、本実施形態では、まず実行履歴テーブル310を用いて高頻度で実行される命令列の繰り返し部分を検出してから、分岐履歴テーブル320に該繰り返し部分の分岐履歴を収集するようにしている。そのため、分岐履歴を収集する段階では、実行履歴テーブル310を不要にできる。そこで、本実施形態では、実行履歴テーブル310と分岐履歴テーブル320の記憶領域を共用し、管理テーブル部300に設けられる記憶容量の削減を図ることができる。
【0081】
図9(A)、図9(B)に、本実施形態における管理テーブル部300の説明図を示す。
【0082】
図9(A)は、管理テーブル部300が有する共用テーブルの構成の概要を示す。共用テーブルは、複数のエントリを有する。各エントリには、基本ブロックの先頭アドレスBSAに関連付けて、分岐命令のアドレスBIA、該分岐命令の分岐先アドレスBTA、該分岐命令の分岐回数COUNTが記憶される。即ち、共用テーブルは、図8に示す分岐履歴テーブル320と同様の構成を有する。
【0083】
本実施形態では、図9(A)に示す共用テーブルを用いて、図7に示す実行履歴テーブル310の機能を実現する。
【0084】
即ち、図9(B)に示すように、図9(A)の管理テーブルのうち分岐命令のアドレスBIAと分岐先アドレスBTAの欄がディセーブルにされる(図9(B)の斜線部分)。その結果、共用履歴テーブルが実行履歴テーブル310として機能する場合には、基本ブロックBSAと回数COUNTの欄のみがイネーブルとなる。これにより、図9(A)に示す共用テーブルで、実行履歴テーブル310及び分岐履歴テーブル320の両方の機能を実現できる。
【0085】
このため、本実施形態では、実行履歴テーブル310の記憶領域の少なくとも一部が、分岐履歴テーブル320の記憶領域と重複しているということができる。また、分岐履歴テーブル320に登録すべき情報の少なくとも一部を、実行履歴テーブル310の記憶領域に書き込むことができる。
【0086】
以下では、管理テーブル部300が、図9(A)に示す共用テーブルの構成を有しているものとする。
【0087】
2.1 プロファイラの処理例
図10に、本実施形態におけるプロファイラ30の処理の概要のフローを示す。
【0088】
まず、プロファイラ30の分岐履歴管理部220は、共用テーブルを図9(B)に示すように実行履歴テーブルとして用いるための初期化処理を行う(ステップS20)。
【0089】
次に実行履歴管理部210は、実行履歴テーブルとして機能する共用テーブルを用いて実行履歴を収集する(ステップS21)。そして、実行履歴テーブルとして機能する共用テーブルに格納される基本ブロックの先頭アドレスの命令の実行回数が所与の閾値TH1を超えたか否かを判断することで、高頻度の繰り返しがあるか否かを判別する(ステップS22)。
【0090】
ステップS22において、高頻度の繰り返しがないと判別したとき(ステップS22:N)、実行履歴管理部210は、ステップS21に戻って実行履歴の収集を継続する。
【0091】
ステップS22において、高頻度の繰り返しがあると判別したとき(ステップS22:Y)、実行履歴管理部210は、その旨を分岐履歴管理部220に通知する。実行履歴管理部210又は分岐履歴管理部220は、共用テーブルを図9(A)に示すように分岐履歴テーブルとして用いるための初期化処理を行う(ステップS23)。
【0092】
その後、分岐履歴管理部220は、閾値TH1を超えた実行回数に関連付けて記憶される先頭アドレスを用いて、分岐履歴の収集を開始する。そして分岐履歴管理部220は、分岐履歴テーブルとして機能する共用テーブルを用いて分岐履歴の収集を行うと共に、分岐命令が入力される毎に分岐履歴情報に基づいて分岐回数の多い分岐先アドレスをパス情報として出力する(ステップS24)。分岐履歴管理部220は、公知の分岐履歴収集手法を用いて分岐命令、分岐先アドレスを登録、追加、リプレース等を行うが、更に分岐回数についても登録する。
【0093】
次に、分岐履歴管理部220は、分岐命令が入力される毎に、分岐履歴テーブルがミスヒットし、且つ該分岐命令の分岐先アドレスが、実行履歴テーブルに一度記録された基本ブロックの先頭アドレスと一致するか否かを検出することで、繰り返し処理の有無を判別する(ステップS25)。繰り返し処理がないと判別されたとき(分岐命令の分岐先が実行履歴テーブルに記録された先頭アドレスとならないとき)(ステップS25:Y)、分岐履歴管理部220は、分岐履歴テーブルの分岐履歴を廃棄(無効化、初期化)し(ステップS26)、ステップS20に戻る(リターン)。
【0094】
分岐履歴管理部220は、分岐命令の実行回数を保持している。そしてステップS25において、繰り返し処理があると判別されたとき(ステップS25:N)、分岐履歴管理部220は、所与のサンプリング期間内に分岐命令の実行回数が所与の閾値THX以上であるか否かを判別する(ステップS27)。サンプリング期間内に分岐命令の実行回数が閾値THX以上であると判別されたとき(ステップS27:Y)、分岐履歴管理部220は、ステップS24に戻り、分岐履歴の収集とホットパス情報の出力を継続する。一方、サンプリング期間内に分岐命令の実行回数が閾値THX以上ではないと判別されたとき(ステップS27:N)、分岐履歴管理部220は、分岐履歴テーブルの分岐履歴を廃棄(無効化)し(ステップS26)、ステップS20に戻る(リターン)。このように、ステップS27において閾値THX以上繰り返していないか否かを検出することで、ステップS22で検出された高頻度の繰り返し部分について必ずしもホットパスを検出する必要がなくなり、プロファイラ30が検出するホットパス情報の精度を高めることができる。
【0095】
以上のように、分岐命令の分岐先が実行履歴テーブルに記録された先頭アドレスとならないとき、又は予め決められた分岐命令の実行回数が所与のサンプリング時間内に達しなかったとき、分岐履歴管理部220が分岐履歴を廃棄できる。
【0096】
以上のような処理を、コンピュータを機能させるためのプログラムで実現してもよい。この場合、図1のメモリ110又はプロファイラ30の図示しないメモリに上記の処理を実現するためのプログラムを格納しておき、プロファイラ30の図示しないCPUがメモリ110又はプロファイラ30の図示しないメモリのプログラムを読み出すことで、上記の処理を実現できる。また、図1において、例えばメモリ110又はプロファイラ30の図示しないメモリに代えてコンピュータ読み取り可能な記録媒体で上記のプログラムを提供してもよい。この記録媒体は、コンピュータにより使用可能な記憶媒体であって、プログラムやデータなどの情報を格納するものであり、その機能は、光ディスク(CD、DVD)、光磁気ディスク(MO)、磁気ディスク、ハードディスク、磁気テープ、或いはメモリ(ROM)などのハードウェアにより実現できる。プロファイラ30の図示しないCPUは、この記憶媒体に格納される情報に基づいて本発明(本実施形態)の種々の処理を行う。即ちこの記憶媒体には、本発明(本実施形態)の手段を実行(実現)するための情報(プログラム或いはデータ)が格納される。
【0097】
図11に、実行履歴管理部210の処理例のフロー図を示す。
【0098】
まず、実行履歴管理部210は、例えばCPU10による分岐命令の実行を監視し、基本ブロックの先頭アドレスBSAとして該分岐命令の分岐先アドレスの入力を待つ(ステップS40:N)。基本ブロックの先頭アドレスBSAが入力されたとき(ステップS40:Y)、実行履歴管理部210は、該先頭アドレスBSAをインデックスとして、実行履歴テーブルとして機能する共用テーブルを検索する(ステップS41)。
【0099】
そして、ステップS41において共用テーブルを検索した結果、既に登録された先頭アドレスBSAがあるとき(ステップS42:Y)、実行履歴管理部210は、ステップS41で検索した先頭アドレスBSAに関連付けて記録された実行回数をインクリメントして更新する(ステップS43)。このとき、実行履歴管理部210は、ステップS43で更新した実行回数が所与の閾値TH1を超えたか否かを検出する(ステップS44)。実行回数が閾値TH1を超えたことが検出されたとき(ステップS44:Y)、実行履歴管理部210は、高頻度の繰り返し実行部分が存在したと判断し、当該先頭アドレスBSAを用いた分岐履歴の収集を開始するように分岐履歴収集イネーブルを設定し(ステップS45)、一連の処理を終了する(エンド)。
【0100】
一方、ステップS41において共用テーブルを検索した結果、既に登録された先頭アドレスBSAがないとき(ステップS42:N)、実行履歴管理部210は、入力された先頭アドレスBSAを実行履歴テーブルとして機能する共用テーブルに登録する処理を行い(ステップS46)、ステップS40に戻る。なお、実際には、先頭アドレスBSAと分岐先アドレスBTAとを比較し、分岐先アドレスが戻り方向であるときに、分岐先アドレスBTAを新たに追加する先頭アドレスBSAとして登録する。このとき、実行履歴テーブルとして機能する共用テーブルでは、必要に応じて記憶情報のリプレースが行われる。
【0101】
ステップS44において、実行回数が閾値TH1を超えていないことが検出されたとき(ステップS44:N)、実行履歴管理部210は、ステップS40に戻って次の基本ブロックの先頭アドレスBSAを待つ。
【0102】
以上のように、実行履歴管理部210は、実行履歴の収集を行うと共に、収集した実行履歴に基づいて、高頻度で繰り返される実行部分を検出し、分岐履歴の収集開始を指示できるようになっている。
【0103】
図12に、分岐履歴管理部220の処理例のフロー図を示す。
【0104】
まず、分岐履歴管理部220は、分岐履歴収集イネーブルが設定されているか否かを監視する(ステップS60:N)。分岐履歴収集イネーブルが設定されていることが検出されたとき(ステップS60:Y)、分岐履歴管理部220は、図11のステップS44で閾値TH1を超えたエントリの先頭アドレスBSAの入力を待つ(ステップS61:N)。この先頭アドレスBSAは、分岐命令の分岐先アドレスである。基本ブロックの先頭アドレスBSAが入力されたとき(ステップS61:Y)、分岐履歴管理部220は、該先頭アドレスBSAをインデックスとして、分岐履歴テーブルとして機能する共用テーブルを検索する(ステップS62)。
【0105】
そして、ステップS62において共用テーブルを検索した結果、既に登録された先頭アドレスBSAがあるとき(ステップS63:Y)、分岐履歴管理部220は、複数の先頭アドレスBSAが登録されているとき(ステップS64:Y)、分岐回数が最も多い分岐先アドレスをホットパス情報として出力する(ステップS65)と共に、当該分岐先アドレスに関連付けて記憶された分岐回数をインクリメントして更新し(ステップS65)、ステップS60に戻る(リターン)。
【0106】
ステップS64において、1つの先頭アドレスBSAのみが登録されているとき(ステップS64:N)、分岐履歴管理部220は、ヒットした分岐先アドレスをホットパス情報として出力すると共に、当該分岐先アドレスに関連付けて記憶された分岐回数をインクリメントして更新し(ステップS66)、ステップS60に戻る(リターン)。
【0107】
一方、ステップS62において共用テーブルを検索した結果、既に登録された先頭アドレスBSAがないとき(ステップS63:N)、分岐履歴管理部220は、入力された先頭アドレスBSAを分岐履歴テーブルとして機能する共用テーブルに登録する処理を行い(ステップS67)、ステップS60に戻る。このとき、分岐履歴テーブルとして機能する共用テーブルでは、必要に応じて記憶情報のリプレースが行われる。
【0108】
以上のように、分岐履歴管理部220は、分岐履歴の収集を行うと共に、収集した分岐履歴に基づいてホットパスを出力できるようになっている。このホットパスは、分岐履歴テーブルを検索して得られた分岐先アドレスを蓄積したホットパス情報として出力される。
【0109】
2.2 プロファイラの構成例
次に、本実施形態における実行履歴テーブル310、分岐履歴テーブル320、実行履歴管理部210、分岐履歴管理部220の要部の構成例について説明する。
【0110】
本実施形態では、実行履歴テーブル310及び分岐履歴テーブル320が、それぞれ2ウェイ-セットアソシアティブ方式で記憶情報を記憶するものとして説明するが、本発明が、ウェイ数や実行履歴テーブル310及び分岐履歴テーブル320の構成に限定されるものではない。例えば、実行履歴テーブル310及び分岐履歴テーブル320は、フルアソシアティブ方式で記憶情報を記憶してもよい。しかしながら、条件分岐命令の分岐先は2箇所であるため、2ウェイ構成とすることで、条件分岐命令の条件が「真」のときの分岐先アドレスと該条件が「偽」の分岐先アドレスとを記憶でき、分岐先アドレスの記憶管理を効率化できる上に無駄な記憶領域を設ける必要がなくなる。
【0111】
図13、図14(A)、図14(B)、図15(A)、図15(B)に、本実施形態における実行履歴テーブル310と実行履歴管理部210の要部の構成例を示す。
【0112】
実行履歴テーブル310は、2ウェイ-セットアソシアティブ方式で、基本ブロックの先頭アドレスBSA及び該先頭アドレスBSAの命令の実行回数COUNTを記憶する。両方のウェイは同様の構成を有し、各ウェイの記憶情報は公知のLRU(Least Recently Used)方式でリプレース制御されるようになっている。
【0113】
先頭アドレスBSAの例えば下位ビットがデコーダDEC1、DEC2に入力される。各デコーダは、各ウェイのテーブルの1エントリを先頭アドレスBSAの下位ビットに基づいて選択する。各ウェイにおいて選択されたエントリの先頭アドレス及び実行回数COUNTは読み出される。こうして読み出された先頭アドレスは、先頭アドレスレジスタBSA1、BSA2、実行回数は、実行回数レジスタCNT1、CNT2で保持される。
【0114】
コンパレータCMP1は、先頭アドレスBSAと先頭アドレスレジスタBSA1の値と比較し、一致したときにヒット信号hita1をアクティブ(例えば「1」)にする。コンパレータCMP2は、先頭アドレスBSAと先頭アドレスレジスタBSA2の値と比較し、一致したときにヒット信号hita2をアクティブ(例えば「1」)にする。
【0115】
実行回数レジスタCNT1の値は、インクリメンタINC1(広義にはカウンタ)でインクリメントされる。実行回数レジスタCNT2の値は、インクリメンタINC2(広義にはカウンタ)でインクリメントされる。
【0116】
セレクタSEL1は、選択制御信号sel1に基づいて、実行回数レジスタCNT1の値又はインクリメンタINC1の出力を選択して、選択出力CNTs1を出力する。そして、選択出力CNTs1により、デコーダDEC1で選択されたエントリの実行回数COUNTを更新する。セレクタSEL2は、選択制御信号sel2に基づいて、実行回数レジスタCNT2の値又はインクリメンタINC2の出力を選択して、選択出力CNTs2を出力する。そして、選択出力CNTs2により、デコーダDEC2で選択されたエントリの実行回数COUNTを更新する。
【0117】
図14(A)に示すように、実行履歴管理部210又は実行履歴テーブル310は、ヒット判定部212を含む。ヒット判定部212は、ヒット信号hita1、hita2が入力され、選択制御信号sel1、sel2、ライトイネーブルwe1、we2を出力する。
【0118】
図14(B)に、図14(A)のヒット判定部212の動作説明図を示す。
【0119】
ヒット判定部212は、ヒット信号hita1がアクティブのとき、選択制御信号sel1をアクティブにしてインクリメンタINC1の出力で実行履歴テーブル310を更新するように制御する。またヒット判定部212は、ヒット信号hita2がアクティブのとき、選択制御信号sel2をアクティブにしてインクリメンタINC2の出力で実行履歴テーブル310を更新するように制御する。
【0120】
更に、ヒット判定部212は、ヒット信号hita1、hita2が非アクティブのとき、セレクタSEL1、SEL2でいずれも出力されないように制御すると共に、LRU制御ビットLRU1、LRU2を用いてLRU制御を行い、先頭アドレスBSAを基準に分岐先アドレスBTAが戻り方向であるときにライトイネーブルwe1、we2の一方をアクティブにする。ライトイネーブルwe1がアクティブのとき、先頭アドレスBSAがデコーダDEC1で選択されたエントリに書き込まれると共に、実行回数COUNTとして「1」が書き込まれる。ライトイネーブルwe2がアクティブのとき、先頭アドレスBSAがデコーダDEC2で選択されたエントリに書き込まれると共に、実行回数COUNTとして「1」が書き込まれる。
【0121】
図15(A)に示すように、実行履歴管理部210又は実行履歴テーブル310は、分岐履歴収集開始制御部214、閾値TH1が設定される閾値設定レジスタ216を含む。分岐履歴収集開始制御部214には、ヒット信号hita1、hita2、選択出力CNTs1、CNTs2、閾値TH1が入力され、分岐履歴収集イネーブルを出力する。
【0122】
図15(B)に、図15(A)の分岐履歴収集開始制御部214の動作説明図を示す。
【0123】
分岐履歴収集開始制御部214は、ヒット信号hita1がアクティブのとき、選択出力CNTs1と閾値TH1とを比較し、選択出力CNTs1が閾値TH以上のとき分岐履歴イネーブルをアクティブ(例えば「1」)に設定する。また分岐履歴収集開始制御部214は、ヒット信号hita2がアクティブのとき、選択出力CNTs2と閾値TH1とを比較し、選択出力CNTs2が閾値TH以上のとき分岐履歴イネーブルをアクティブ(例えば「1」)に設定する。更に分岐履歴収集開始制御部214は、ヒット信号hita1、hita2が共に非アクティブのとき、分岐履歴収集イネーブルを非アクティブに設定する。
【0124】
図16、図17(A)、図17(B)に、本実施形態における分岐履歴テーブル320と分岐履歴管理部220の要部の構成例を示す。
【0125】
分岐履歴テーブル320は、2ウェイ-セットアソシアティブ方式で、基本ブロックの先頭アドレスBSA、当該基本ブロックの分岐命令の分岐先アドレスBTA、該分岐先アドレスへの分岐回数COUNTを記憶する。なお、図16では、分岐履歴テーブル320に分岐命令のアドレスBIAが記録されないものとする。両方のウェイは同様の構成を有し、各ウェイの記憶情報は公知のLRU方式でリプレース制御されるようになっている。
【0126】
先頭アドレスBSAの例えば下位ビットがデコーダDEC3、DEC4に入力される。各デコーダは、各ウェイのテーブルの1エントリを先頭アドレスBSAの下位ビットに基づいて選択する。各ウェイにおいて選択されたエントリの先頭アドレスBSA、分岐先アドレスBTA及び分岐回数COUNTが読み出される。こうして読み出された先頭アドレスは、先頭アドレスレジスタBSA3、BSA4、分岐先アドレスは、分岐先アドレスレジスタBTA3、BTA4、分岐回数は、分岐回数レジスタCNT3、CNT4で保持される。
【0127】
コンパレータCMP3は、先頭アドレスBSAと先頭アドレスレジスタBSA3の値と比較し、一致したときにヒット信号hitb1をアクティブ(例えば「1」)にする。コンパレータCMP4は、先頭アドレスBSAと先頭アドレスレジスタBSA4の値と比較し、一致したときにヒット信号hitb2をアクティブ(例えば「1」)にする。
【0128】
分岐回数レジスタCNT3の値は、インクリメンタINC3(広義にはカウンタ)でインクリメントされる。分岐回数レジスタCNT4の値は、インクリメンタINC4(広義にはカウンタ)でインクリメントされる。
【0129】
セレクタSEL3は、選択制御信号sel3に基づいて、分岐先アドレスレジスタBTA3又は分岐先アドレスレジスタBTA4の値を選択出力して、ホットパス情報として追加されると共に、次の基本ブロックの先頭アドレスとして分岐履歴テーブル320に入力される。
【0130】
セレクタSEL4は、選択制御信号sel4に基づいて、分岐回数レジスタCNT3の値又はインクリメンタINC3の出力を選択して、選択出力CNTs3を出力する。そして、選択出力CNTs3により、デコーダDEC3で選択されたエントリの分岐回数COUNTを更新する。セレクタSEL5は、選択制御信号sel5に基づいて、分岐回数レジスタCNT4の値又はインクリメンタINC4の出力を選択して、選択出力CNTs4を出力する。そして、選択出力CNTs4により、デコーダDEC4で選択されたエントリの分岐回数COUNTを更新する。
【0131】
図17(A)に示すように、分岐履歴管理部220又は分岐履歴テーブル320は、ヒット判定部222を含む。ヒット判定部222には、ヒット信号hitb1、hitb2、選択出力CNTs3、CNTs4が入力され、選択制御信号sel3、sel4、sel5、ライトイネーブルwe3、we4を出力する。
【0132】
図17(B)に、図17(A)のヒット判定部222の動作説明図を示す。
【0133】
ヒット判定部222は、ヒット信号hitb1がアクティブのとき、選択制御信号sel4をアクティブにしてインクリメンタINC3の出力で分岐履歴テーブル320を更新するように制御する。またヒット判定部222は、ヒット信号hitb2がアクティブのとき、選択制御信号sel5をアクティブにしてインクリメンタINC4の出力で分岐履歴テーブル320を更新するように制御する。
【0134】
更に、ヒット判定部222は、ヒット信号hitb1、hitb2がアクティブのとき、分岐回数の大きい方のウェイを選択する。そのため、ヒット判定部222は、選択出力CNTs3が選択出力CNTs4以上のとき、選択制御信号sel4をアクティブに設定すると共に、選択制御信号sel5を非アクティブに設定する。またヒット判定部222は、選択出力CNTs3が選択出力CNTs4より小さいとき、選択制御信号sel4を非アクティブに設定すると共に、選択制御信号sel5をアクティブに設定する。更に、ヒット判定部222は、選択制御信号sel4と同様の制御で選択制御信号sel3を出力する。
【0135】
更にまた、ヒット判定部222は、ヒット信号hitb1、hitb2が非アクティブのとき、セレクタSEL3、SEL4でいずれも出力されないように制御すると共に、LRU制御ビットLRU3、LRU4を用いてLRU制御を行い、今回入力された先頭アドレスBSAを書き込むためのライトイネーブルwe3、we4の一方をアクティブにする。ライトイネーブルwe3がアクティブのとき、先頭アドレスBSAがデコーダDEC3で選択されたエントリに書き込まれると共に、分岐回数COUNTとして「1」が書き込まれる。ライトイネーブルwe4がアクティブのとき、先頭アドレスBSAがデコーダDEC4で選択されたエントリに書き込まれると共に、分岐回数COUNTとして「1」が書き込まれる。
【0136】
以上のように、分岐履歴テーブル320が、記憶情報をセットアソシアティブ方式で記憶し、各ウェイ(セット)には、基本ブロックの先頭アドレス、当該基本ブロックに含まれる分岐命令の分岐先アドレス(ターゲットアドレス)、及び分岐回数が記憶される。そして、該分岐命令に対応して記憶された分岐命令のうち分岐回数が最も多いウェイ(セット)の分岐命令の分岐先アドレスを出力できる。
【0137】
3. その他
本発明は上記の実施形態に限定されるものではない。
【0138】
図18に、図1の情報処理装置の変形例のブロック図を示す。
【0139】
図18において図1と同一部分には同一符号を付し、適宜説明を省略する。本変形例における情報処理装置500は、ホットパス処理部120が情報処理装置500内に設けられる。そして、ホットパス処理部120が、プロファイラ30からのホットパス情報に基づいて最適化処理を行い、最適化処理結果をアクセラレータ20に出力する。ここで、最適化処理結果は、ホットパス中の命令列のうち不要なコードが削除された命令列、ホットパス中の命令列を並列動作させるために変更した命令列、又はアクセラレータ20のハードウェア構成を変更するためのハードウェア構成情報等である。
【0140】
なお、本発明は上述した実施の形態に限定されるものではなく、本発明の要旨の範囲内で種々の変形実施が可能である。
【0141】
また、本発明のうち従属請求項に係る発明においては、従属先の請求項の構成要件の一部を省略する構成とすることもできる。また、本発明の1の独立請求項に係る発明の要部を、他の独立請求項に従属させることもできる。
【図面の簡単な説明】
【0142】
【図1】本実施形態における情報処理装置の構成例のブロック図。
【図2】本実施形態における基本ブロックの説明図。
【図3】図1の情報処理装置の処理の一例の概要のフローを示す図。
【図4】本実施形態における高頻度で繰り返し実行される実行命令部分の説明図。
【図5】図3のホットパスの説明図。
【図6】図1のプロファイラの構成の概要を示す図。
【図7】図6の実行履歴テーブルの構成の概要を示す図。
【図8】図6の分岐履歴テーブルの構成の概要を示す図。
【図9】図9(A)、図9(B)は本実施形態における管理テーブル部の説明図。
【図10】本実施形態におけるプロファイラの処理の概要のフローを示す図。
【図11】実行履歴管理部の処理例のフロー図。
【図12】分岐履歴管理部の処理例のフロー図。
【図13】本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図14】図14(A)、図14(B)は本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図15】図15(A)、図15(B)は本実施形態における実行履歴テーブルと実行履歴管理部の要部の構成例を示す図。
【図16】本実施形態における分岐履歴テーブルと分岐履歴管理部の要部の構成例を示す図。
【図17】本実施形態における分岐履歴テーブルと分岐履歴管理部の要部の構成例を示す図。
【図18】図1の情報処理装置の変形例のブロック図。
【符号の説明】
【0143】
10 CPU
20 アクセラレータ
30 プロファイラ
50 バス
100、500 情報処理装置
110 メモリ
120 ホットパス処理部
200 制御部
210 実行履歴管理部
212、222 ヒット判定部
214 実行履歴収集開始制御部
216 閾値設定レジスタ
220 分岐履歴管理部
300 管理テーブル部
310 実行履歴テーブル
320 分岐履歴テーブル
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17