(57)【要約】【課題】  プログラム実行中に実行頻度の高いループ構造のパスを高精度で推定し得る推定装置を得る。【解決手段】  入力される分岐命令のアドレスである分岐アドレスと分岐先アドレスと各分岐命令の実行回数とを１エントリとして格納するテーブルであって、入力される分岐アドレス及び分岐先アドレスと既に格納された分岐アドレス及び分岐先アドレスとが同じ場合には各エントリにおける分岐回数を更新し、異なる場合には新エントリを追加して分岐履歴を格納するプロファイラテーブルと、プロファイラテーブルが格納する分岐履歴のうち戻り分岐の分岐先アドレス及びその分岐回数とを１エントリとして格納する戻り分岐先テーブルと、戻り分岐先テーブルに格納された分岐先アドレスのうち何れかを先頭アドレスに決定する決定手段と、決定手段が決定した先頭アドレスとプロファイラテーブルの分岐履歴により、実行頻度が高い命令パスを推定する推定手段とを設ける。【選択図】  図５
2005092532.tif 000002
【特許請求の範囲】
【請求項１】
複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、
入力される上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するプロファイラテーブルと、
上記プロファイラテーブルが格納する分岐履歴のうち上記分岐先アドレスが上記分岐アドレスよりも小さいエントリの上記分岐回数を上記分岐先アドレス毎に合算し、その分岐先アドレスと当該合算回数とを１つのエントリとして格納する戻り分岐先テーブルと、
上記戻り分岐先テーブルに格納された分岐先アドレスのうちいずれかを先頭アドレスに決定する決定手段と、
上記決定手段が決定した先頭アドレス及び上記プロファイラテーブルに格納された分岐履歴により上記実行される頻度が高い命令パスを推定する推定手段とを備えた、推定装置。
【請求項２】
上記推定手段は、
上記決定手段が決定した上記先頭アドレス以降に実行されるアドレスが、分岐命令を表すアドレスであるか否かを順次判断する第１の処理を実行し、
上記第１の処理により分岐命令を表すアドレスではないと判断した場合に、当該アドレスを記憶する第２の処理を実行し、
上記第１の処理により分岐命令を表すアドレスであると判断した場合に、上記プロファイラテーブルに格納された分岐履歴により上記分岐命令を表すアドレスであると判断したアドレスと同じ分岐アドレスのエントリを検索し、同じ分岐アドレスのエントリが存在する場合は当該エントリのアドレスを記憶して、検索されたエントリにおける分岐先アドレスが上記先頭アドレスと同じであるか否かを判断する第３の処理を実行し、
上記第３の処理により先頭アドレスと同じでないと判断した場合に、当該エントリの分岐先アドレスにジャンプして、当該アドレスを基準として上記第１〜第３の処理を繰り返し実行する第４の処理を実行し、
上記第３の処理により先頭アドレスと同じと判断した場合に、決定された上記先頭アドレスと上記第２、第３の処理により記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第５の処理を実行する、請求項１記載の推定装置。
【請求項３】
上記推定手段は、上記第３の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリにおける分岐先アドレスを選択し、当該分岐先アドレスが上記先頭アドレスと同じであるかを判断する処理を実行する、請求項２記載の推定装置。
【請求項４】
入力される上記各分岐先アドレスが次回に分岐する際の基本ブロック開始アドレスとして保存され、
上記プロファイラテーブルは、入力される上記分岐アドレスと上記分岐先アドレスと上記分岐回数とに加え、上記保存された基本ブロック開始アドレスも１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレス並びに保存された基本ブロック開始アドレスと既に格納された上記分岐アドレス、上記分岐先アドレス及び基本ブロック開始アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加することにより構成されるものであり、
上記推定手段は、決定した上記先頭アドレスと同じ基本ブロック開始アドレスのエントリを検索し、検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐アドレスまでを記憶し、当該エントリにおける分岐先アドレスを次の検索アドレスとする第１の処理を実行し、
上記第１の処理により検索されたエントリにおける上記分岐先アドレスと同じ基本ブロック開始アドレスのエントリをさらに検索し、当該さらに検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐先アドレスまでを記憶する第２の処理を実行し、
上記第２の処理における上記分岐先アドレスが上記決定された先頭アドレスと同じときに上記第２の処理における記憶を終了し、上記決定された先頭アドレスと上記第１の処理及び上記第２の処理により記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第３の処理を実行する、請求項１記載の推定装置。
【請求項５】
上記推定手段は、上記第１の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリを検索したエントリとして選択する、請求項４記載の推定装置。
【請求項６】
上記推定手段は、上記第２の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリを検索したエントリとして選択する、請求項４又は５記載の推定装置。
【請求項７】
上記決定手段は、上記戻り分岐先テーブルに格納された上記合算回数の値が所定閾値よりも大きな値のエントリを選択して決定する、請求項１〜６の何れかに記載の推定装置。
【請求項８】
複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定システムにおいて、
請求項１の推定装置と、
請求項１の推定装置の動作をアシストするアシスト装置とを備え、
上記アシスト装置は、
上記機械命令から分岐命令を選択し、選択された上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスとを出力する選択手段と、
入力される上記分岐アドレスと上記分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、上記入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するアシスト側プロファイラテーブルと、
上記アシスト側プロファイラテーブルが所定の格納上限に到達したとき、格納された分岐履歴を表す情報を上記アシスト側プロファイラテーブルから請求項１記載の推定装置に一括出力させ、上記アシスト側プロファイラテーブルをリードクリアするリードクリア手段とを有する、推定システム。
【請求項９】
上記所定の格納上限は、格納可能な分岐回数の上限又は格納可能なエントリ数の上限を含む、請求項８記載の推定システム。
【請求項１０】
上記アシスト装置は、
所定のサンプルレートが設定されたレジスタと、
上記レジスタに設定された上記サンプルレートに基づいて上記選択手段が選択した分岐命令をサンプリングするサンプリング手段とを有する、請求項８又は９に記載の推定システム。
【請求項１１】
複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定方法において、
入力される上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するプロファイラテーブルが設けられ、
上記プロファイラテーブルが格納する分岐履歴のうち上記分岐先アドレスが上記分岐アドレスよりも小さいエントリの上記分岐回数を上記分岐先アドレス毎に合算し、その分岐先アドレスと当該合算回数とを１つのエントリとして格納する戻り分岐先テーブルが設けられ、
決定手段が上記戻り分岐先テーブルに格納された分岐先アドレスのうちいずれかを先頭アドレスに決定する決定ステップと、
推定手段が上記決定手段により決定された先頭アドレス及び上記プロファイラテーブルに格納された分岐履歴により上記実行される頻度が高い命令パスを推定する推定ステップとを含む、推定方法。
【請求項１２】
上記推定ステップは、推定手段が、
上記決定手段により決定された上記先頭アドレス以降に実行されるアドレスが分岐命令を表すアドレスであるか否かを順次判断する第１のステップと、
上記第１のステップにより分岐命令を表すアドレスではないと判断された場合に、当該アドレスを記憶する第２のステップと、
上記第１のステップにより分岐命令を表すアドレスであると判断された場合に、上記プロファイラテーブルに格納された分岐履歴により上記分岐命令を表すアドレスであると判断したアドレスと同じ分岐アドレスのエントリを検索し、同じ分岐アドレスのエントリが存在する場合は当該エントリのアドレスを記憶して、検索されたエントリにおける分岐先アドレスが上記先頭アドレスと同じであるか否かを判断する第３のステップと、
上記第３のステップにより先頭アドレスと同じでないと判断された場合に、当該エントリの分岐先アドレスにジャンプして、当該アドレスを基準として上記第１〜第３のステップを繰り返し実行する第４のステップと、
上記第３のステップにより先頭アドレスと同じと判断した場合に、決定された上記先頭アドレスと上記第２、第３のステップにより記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第５のステップとを含む、請求項１１記載の推定方法。
【請求項１３】
入力される上記各分岐先アドレスが次回に分岐する際の基本ブロック開始アドレスとして保存されており、
上記プロファイラテーブルは、入力される上記分岐アドレスと上記分岐先アドレスと上記分岐回数とに加え、上記保存された基本ブロック開始アドレスも１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレス並びに保存された基本ブロック開始アドレスと既に格納された上記分岐アドレス、上記分岐先アドレス及び基本ブロック開始アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加しており、
上記推定ステップは、推定手段が、決定された上記先頭アドレスと同じ基本ブロック開始アドレスのエントリを検索し、検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐アドレスまでを記憶し、当該エントリにおける分岐先アドレスを次の検索アドレスとする第１のステップと、
上記第１ステップにより検索されたエントリにおける上記分岐先アドレスと同じ基本ブロック開始アドレスのエントリをさらに検索し、当該さらに検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐先アドレスまでを記憶する第２のステップと、
上記第２のステップにおける上記分岐先アドレスが上記決定された先頭アドレスと同じときに上記第２のステップにおける記憶を終了し、上記決定された先頭アドレスと上記第１のステップ及び上記第２のステップにより記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第３のステップとを含む、請求項１１記載の推定方法。
【請求項１４】
コンピュータに請求項１１、１２又は１３の推定方法を実行させるためのコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アプリケーションプログラムの振る舞いに関する情報をその実行中に収集する技術、いわゆるオンラインプロファイリング技術に関するものであり、特にプロセッサで実行される命令の内、高頻度で実行される命令パスを推定する推定装置に関するものである。
【背景技術】
【０００２】
プロセッサにおいて実行中のプログラムの分岐履歴情報等を取得し、アプリケーションプログラムについて動的最適化に利用し得る情報を収集するオンラインプロファイリングについては、いくつかの技術が提案されている。
【０００３】
例えば、プロセッサコアで実行される命令パスの基本ブロックをトラバースしてループ構造のパスを検出し、かつ当該ループ構造の開始アドレスと終了アドレスを検出し、開始アドレスを初期値０として、パス終了アドレスから開始アドレスの方向に、最も近い分岐アドレスを順次検索していき、実行オブジェクトが当該分岐アドレスを通過する度に当該分岐アドレスの経路に重み付け（＋１）を加算して行き、重み付けされた分岐アドレスに最も近い分岐アドレスが上記開始アドレスになった時点で処理を終了する技術がある。このプロファイリング技術は、開始アドレスを初期値０として実行オブジェクトが重み付けされた経路を通過する度に重み付け値を加算していくと、パス毎にユニークな積算値が決定するため、パスについての積算値が何回発生したかをカウントすることにより、高頻度で実行されたパスを検出するものである（非特許文献１）。
【０００４】
また、オンラインで行われる他のプロファイリング技術として、戻り分岐の実行回数に着目し、まずループ構造のパスのパス開始アドレスを決定し、プロファイリングの前提として頻繁に実行されるパスはパス開始アドレスを決定した直後にも同じパスが繰り返し実行されるものと仮定し、上記パス開始アドレス決定時にそのパス開始アドレスを通過して、そのパス開始アドレスに戻り分岐により戻ったパス、即ち分岐目標アドレスが当該分岐命令のプログラムカウントより低いプログラムカウントとであることをトレース終了条件として実行頻度の高いループを決定するものが提案されている（非特許文献２、特許文献１）。
【０００５】
また、コンパイラ装置等において原始プログラムの分岐やループについて分岐回数を減少する最適化を行うために、実行パス上の分岐命令の実行回数を示すプロファイル情報を作成するものが提案されている（特許文献２）。
【０００６】
【非特許文献１】バル，Ｔ（Ｂａｌｌ，Ｔ）、ラルス，Ｊ・Ｒ（Ｌａｒｕｓ，Ｊ．Ｒ．）著「エフィシャント  パス  プロファイリング（Ｅｆｆｉｃｉｅｎｔ  ｐａｔｈ  ｐｒｏｆｉｌｉｎｇ）」第２９回マイクロアーキテクチャー国際シンポジウム会報、１９９６年パリ（Ｉｎ  Ｐｒｏｃ．Ｏｆ  ｔｈｅ  ２９ｔｈ  Ｉｎｔ．Ｓｙｍｐ．Ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ，Ｐａｒｉｓ．１９９６）
【０００７】
【非特許文献２】バラ，Ｖ（Ｂａｌａ，Ｖ）、デュスタワルド，Ｅ（Ｄｕｅｓｔｅｒｗａｌｄ，Ｅ）、バナジア，Ｓ（Ｂａｎｅｒｊｉａ，Ｓ．）著「ダイナモ：トランスパーレント  ランタイム  オプティマイゼーション  システム」（Ｄｙｎａｍｏ：Ａ  ｔｒａｎｓｐａｒｅｎｔ  ｒｕｎｔｉｍｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｓｙｓｔｅｍ）２０００年プログラミング  ランゲージ  デザイン  アンド  インプリメンテーション学会会報、２０００年６月バンクーバー（Ｉｎ  Ｐｒｏｃ．Ｏｆ  ｔｈｅ  ２０００  Ｃｏｎｆ．ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｖａｎｃｏｕｖｅｒ，Ｂ．Ｃ．，Ｊｕｎｅ  ２０００）
【特許文献１】特開２０００−１４８４８２号公報（「００３５」〜、図７）
【０００８】
【特許文献２】特開平８−８７４１７号公報（図８）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところで、上記非特許文献１記載の技術は、上述のようにアプリケーションプログラムの実行前にプロセッサコアで実行される命令パスの基本ブロックをトラバースしてループ構造のパスを検出するというパス構造の事前解析を行わなければならないため、実行オーバーヘッドによるアプリケーションプログラムの実行速度の低下等、パフォーマンス低下等の影響が大きいとの問題がある。
【００１０】
また、上記非特許文献２、特許文献１の技術は、オンラインでプロファイリングを行うことが可能であるが、高頻度に実行されるパスの決定がパス開始アドレスの見つかった直後に通過したパスとするため、実装上は有利であっても、必ずしもパス開始アドレスが決定した瞬間に実行頻度の高いパスを実行するとは限らないので、推定処理の正確さの点で問題がある。
【００１１】
また、上記特許文献２の技術は、実行パス上の分岐命令の実行回数を示すプロファイル情報を作成するものであるが、いわゆる原始プログラムにおける分岐回数等のプロファイル情報を収集するだけのものであり、高頻度で実行されるループ構造のパスを推定するものではない。
【００１２】
本発明は、プログラム実行前のパス構造の事前解析が不要であり、かつオーバーヘッドが小さく、プロセッサで実行される機械命令において実行頻度の高いループ構造の命令パスの推定を正確に行うことのできる推定装置、推定方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は上記課題を解決するため、
第１に、複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、入力される上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するプロファイラテーブルと、上記プロファイラテーブルが格納する分岐履歴のうち上記分岐先アドレスが上記分岐アドレスよりも小さいエントリの上記分岐回数を上記分岐先アドレス毎に合算し、その分岐先アドレスと当該合算回数とを１つのエントリとして格納する戻り分岐先テーブルと、上記戻り分岐先テーブルに格納された分岐先アドレスのうちいずれかを先頭アドレスに決定する決定手段と、上記決定手段が決定した先頭アドレス及び上記プロファイラテーブルに格納された分岐履歴により上記実行される頻度が高い命令パスを推定する推定手段とを備えた、推定装置により構成されるものである。
【００１４】
上記プロファイラテーブルは例えばＳＷテーブルメモリ（２０）内のＳＷプロファイラテーブル（２０’）等により構成することができる。上記分岐回数の更新は例えばＳＷテーブルエントリのマージ手段（２１）による分岐カウンタの合算処理（図１６Ｐ６等）、上記新たなエントリの追加は上記マージ手段（２１）によるエントリの新規追加処理（図１６Ｐ７）等により実現することができる。上記戻り分岐先テーブルは例えばＳＷプロファイラ部２の戻り分岐先テーブル（２３’）等により構成することができる。当該テーブル（２３’）における上記分岐回数の合算は、例えば戻り分岐エントリ検索手段（２４）によるＢＩＡ＞ＢＴＡのエントリの検索処理（図１７Ｐ２等）及び同一エントリのマージ手段（２５）による戻り分岐テーブル（２３’）における上記エントリのカウンタ値の合算処理（図１７Ｐ５等）により実現することができる。上記決定手段は、例えば戻り分岐先テーブル（２３’）に格納された分岐先アドレスの内、所定の閾値を超える分岐回数の分岐先アドレスを先頭アドレス（ホットパスヘッドアドレス候補）として決定するホットパスヘッドアドレス決定手段（２６）により構成することができる。上記推定手段は、例えば上記先頭アドレスから実行オブジェクトをトラバースして分岐命令を検出するまで命令アドレスをホットパステーブル（３４）に登録する実行オブジェクトのトラバース手段（２８）、分岐命令を検出すると上記プロファイラテーブル（２０’）において当該分岐命令のアドレスと同一の分岐アドレスのエントリを検索しそのエントリのＢＴＡアドレスを選択する同一ＢＩＡエントリ検索手段（２９）、当該分岐アドレスと分岐先アドレスをホットパステーブルに登録し、同一ＢＩＡのエントリの分岐先アドレスが先頭アドレスと同一か否かを検出するホットパス検索終了決定手段（３１）、同一でない場合はトラバースを再開する実行オブジェクトのトラバース再開アドレス決定手段（３２）、同一である場合は、上記ホットパステーブル（３４）に登録された分岐アドレス等の内容を実行される頻度が高い命令パスとして出力するホットパス保存出力手段（３３）等により構成することができる。
【００１５】
第２に、上記推定手段は、上記決定手段が決定した上記先頭アドレス以降に実行されるアドレスが、分岐命令を表すアドレスであるか否かを順次判断する第１の処理を実行し、上記第１の処理により分岐命令を表すアドレスではないと判断した場合に、当該アドレスを記憶する第２の処理を実行し、上記第１の処理により分岐命令を表すアドレスであると判断した場合に、上記プロファイラテーブルに格納された分岐履歴により上記分岐命令を表すアドレスであると判断されたアドレスと同じ分岐アドレスのエントリを検索し、同じ分岐アドレスのエントリが存在する場合は当該エントリのアドレスを記憶して、検索されたエントリにおける分岐先アドレスが上記先頭アドレスと同じであるか否かを判断する第３の処理を実行し、上記第３の処理により先頭アドレスと同じでないと判断した場合に、当該エントリの分岐先アドレスにジャンプして、当該アドレスを基準として上記第１〜第３の処理を繰り返し実行する第４の処理を実行し、上記第３の処理により先頭アドレスと同じと判断した場合に、決定された上記先頭アドレスと上記第２、第３の処理により記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第５の処理を実行する、上記第１記載の推定装置により構成されるものである。
【００１６】
上記第１の処理は、例えば実行オブジェクトのトラバース手段（２８）が実行オブジェクトをトラバースして先頭アドレスの次に実行されるアドレスから分岐命令を検出する処理（図１８Ｐ１６等）、上記第２の処理は、例えば上記トラバース手段（２８）による当該アドレスのホットパステーブル（３４）への登録処理（図１８Ｐ１７等）、上記第３の処理は、例えば上記トラバース手段（２８）で分岐命令を検出した場合において、例えば同一ＢＩＡエントリ検索手段（２９）がＳＷプロファイラテーブル（２０’）から上記分岐命令のアドレスと同一の分岐アドレスのエントリを検索する処理（図１７Ｐ２１等）、上記トラバース手段（２８）による分岐アドレス等のホットパステーブル（３４）への登録処理（図１８Ｐ２３、Ｐ２４等）、ホットパス検索終了決定手段（３１）による上記エントリの分岐先アドレスが先頭アドレスと同一であるかを判断する処理（図１８Ｐ２５等）により行うことができる。上記第４の処理は、実行オブジェクトのトラバース再開アドレス決定手段（３２）による当該エントリの分岐先アドレスへジャンプして当該アドレスを基準として、例えば当該アドレスの次の実行アドレスから分岐命令を検索する処理（図１８Ｐ２６等）、上記第５の処理は、例えば上記検索終了決定手段（３１）により上記分岐先アドレスが上記先頭アドレスと同じであると判断された場合に、ホットパス保存出力手段（３３）により上記ホットパステーブル（３４）の内容を出力して当該テーブル（３４）に登録された命令パスを実行される頻度が高い命令パスとして推定する処理（図１８Ｐ２７等）により行うことができる。
【００１７】
第３に、上記推定手段は、上記第３の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリにおける分岐先アドレスを選択し、当該分岐先アドレスが上記先頭アドレスと同じであるかを判断する処理を実行する、上記第２記載の推定装置により構成されるものである。
【００１８】
このような処理は、複数エントリを検出した場合において、ホットパスとするＢＴＡの決定手段（３０）がＳＷプロファイラテーブル（２０’）においてカウント数の大きいエントリのＢＴＡを選択する処理（図１８Ｐ２２等）により行うことができる。
【００１９】
第４に、入力される上記各分岐先アドレスが次回に分岐する際の基本ブロック開始アドレスとして保存され、上記プロファイラテーブルは、入力される上記分岐アドレスと上記分岐先アドレスと上記分岐回数とに加え、上記保存された基本ブロック開始アドレスも１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレス並びに保存された基本ブロック開始アドレスと既に格納された上記分岐アドレス、上記分岐先アドレス及び基本ブロック開始アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加することにより構成されるものであり、上記推定手段は、決定した上記先頭アドレスと同じ基本ブロック開始アドレスのエントリを検索し、検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐アドレスまでを記憶し、当該エントリにおける分岐先アドレスを次の検索アドレスとする第１の処理を実行し、上記第１の処理により検索されたエントリにおける上記分岐先アドレスと同じ基本ブロック開始アドレスのエントリをさらに検索し、当該さらに検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐先アドレスまでを記憶する第２の処理を実行し、上記第２の処理における上記分岐先アドレスが上記決定された先頭アドレスと同じときに上記第２の処理における記憶を終了し、上記決定された先頭アドレスと上記第１の処理及び上記第２の処理により記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第３の処理を実行する、上記第１記載の推定装置により構成されるものである。
【００２０】
上記次回に分岐する際の基本ブロック開始アドレスの保存は例えばＨＷアシスト装置（１）における前分岐命令蓄積レジスタ（９’）により行うことができる。上記プロファイラテーブルは例えばＳＷテーブルメモリ２０内に作成されるＳＷプロファイラテーブル（２０”）等により構成することができる。上記第１の処理は、例えば同一ＢＳＡエントリ検索手段（２９’）がＳＷプロファイラテーブル（２０”）において上記先頭アドレスと同じ基本ブロック開始アドレスのエントリを検索する処理（図２１Ｐ１２等）、ＢＳＡエントリ検索手段（２８’）による検索されたエントリにおけるＢＳＡからＢＩＡまでをホットパステーブル（３４’）に登録する処理（図２１Ｐ１３等）、及びホットパスとするＢＴＡの決定手段（３０）による上記エントリにおける分岐先アドレス（ＢＴＡ）を検索アドレスとして決定する処理（図２１Ｐ１５等）により行うことができる。上記第２の処理は、例えば上記ＢＳＡエントリ検索手段（２９’）が当該検索アドレス（ＢＴＡ）と同一の基本ブロック開始アドレス（ＢＳＡ）のエントリを検索する処理（図２１Ｐ１７等）、及び上記検索手段（２８’）によるＢＳＡからＢＴＡまでをホットパステーブルに登録する処理（図２１Ｐ２０等）により行うことができる。上記第３の処理は、例えばホットパス検索終了決定手段（３１）が検索アドレス（ＢＴＡ）が上記先頭アドレスと同じか否かを判断する処理（図２１Ｐ２１等）、同一の場合にホットパス保存出力手段（３３）によるホットパステーブル（３４’）に登録された命令パスを出力し、当該命令パスを実行される頻度が高い命令パスとして推定する処理（図２１Ｐ２３等）により行うことができる。
【００２１】
第５に、上記推定手段は、上記第１の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリを検索したエントリとして選択する、上記第４記載の推定装置により構成されるものである。
【００２２】
このような処理は、例えば同一ＢＳＡエントリの検索手段（２９’）により先頭アドレス＝ＢＳＡのエントリの内ＢＴＡが異なるエントリが複数あるか否かを判断する処理（図２１Ｐ１４等）、及びホットパスとするＢＴＡの決定手段（３０）によりカウント数が大きいエントリのＢＴＡの選択処理（図２１Ｐ１６等）により行うことができる。
【００２３】
第６に、上記推定手段は、上記第２の処理において複数のエントリを検索したときには、上記複数のエントリのうちから上記分岐回数の値が大きなエントリを検索したエントリとして選択する、上記第４又は５記載の推定装置により構成されるものである。
【００２４】
このような処理は、例えば上記検索手段（２９’）により検索アドレス＝ＢＳＡのエントリの内、ＢＴＡが異なるエントリが複数あるか否かを判断する処理（図２１Ｐ１８等）、ホットパスとするＢＴＡの決定手段（３０）によりカウント数の大きいエントリのＢＴＡを選択する処理（図２１Ｐ１９等）により行うことができる。
【００２５】
第７に、上記決定手段は、上記戻り分岐先テーブルに格納された上記合算回数の値が所定閾値よりも大きな値のエントリを選択して決定する上記第１から６のいずれかに記載の推定装置により構成されるものである。
【００２６】
このような処理は、ホットパスアドレス決定手段（２６）がホットパスヘッドアドレス閾値決定レジスタ（２７）の閾値と戻り分岐先テーブル（２３’）のカウント値を比較する処理（図１７Ｐ８、Ｐ９、図２０Ｐ６、Ｐ７等）により行うことができる。また、上記決定手段において複数のエントリを検索したときには、最小アドレスの分岐先アドレスを先頭アドレスに選択して決定することが好ましい（図１７Ｐ１２、Ｐ１４、図２０Ｐ７、Ｐ９等）。
【００２７】
第８に、複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定システムにおいて、上記第１の推定装置と、上記第１の推定装置の動作をアシストするアシスト装置とを備え、上記アシスト装置は、上記機械命令から分岐命令を選択し、選択された上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスとを出力する選択手段と、入力される上記分岐アドレスと上記分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、上記入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するアシスト側プロファイラテーブルと、上記アシスト側プロファイラテーブルが所定の格納上限に到達したとき、格納された分岐履歴を表す情報を上記アシスト側プロファイラテーブルから上記第１記載の推定装置に一括出力させ、上記アシスト側プロファイラテーブルをリードクリアするリードクリア手段とを有する、推定システムにより構成されるものである。
【００２８】
上記第１の推定装置はＳＷプロファイラ部（２）により構成することができる。上記アシスト装置はＨＷアシスト装置（１）により構成することができる。上記選択手段は例えば分岐命令選択部（７）、サンプリング部（８）等により構成することができる。上記アシスト側プロファイラテーブルは例えばテーブルメモリ（１２）内に構成されるＨＷプロファイラテーブル（１２’）により構成することができる。上記リードクリア手段は例えばテーブル空きエントリ管理部（１３）、テーブル読み出し削除部（１６）、ソフトウェアへの割り込み通知部（１５）等により構成することができる。
【００２９】
第９に、上記所定の格納上限は、格納可能な分岐回数の上限又は格納可能なエントリ数の上限を含む、上記第８記載の推定システムにより構成されるものである。
【００３０】
このような分岐回数の上限又は格納可能なエントリ数の上限は、例えばテーブル空きエントリ管理部（１３）がＨＷプロファイラテーブル（１３’）のカウント数又はエントリ数を監視することにより行うことができる。
【００３１】
また、上記アシスト装置は、上記格納された分岐履歴が上記アシスト側プロファイラテーブルから上記第１記載の推定装置に出力されるときに上記格納された分岐履歴を表す情報を圧縮した情報列を生成する圧縮手段を有する、上記第８又は９記載の推定システムにより構成することが好ましい。この圧縮手段は、サンプリング部（８）から入力する「分岐アドレス、分岐先アドレス」を示す情報列ｔ１、ｔ２等をその出現回数（分岐回数）によりまとめた（ｔ１、１０）、（ｔ２、１０）等の圧縮情報列として上記推定装置に送出する分岐情報圧縮手段（１０’）により構成することが好ましい。
【００３２】
また、上記第１記載の推定装置は、上記アシスト側プロファイラテーブルが所定の格納上限に到達したことを表す信号が入力されたことに応答して、上記アシスト側プロファイラテーブルから一括出力された分岐履歴を表す情報を一時保存する保存手段を備え、上記第１記載の推定装置におけるプロファイラテーブルは、上記保存手段に一時保存された分岐履歴情報を表す情報に従ってエントリ単位の格納処理を行う、上記第８又は９に記載の推定システムにより構成することが好ましい。
【００３３】
上記保存手段は、例えばＳＷプロファイラ部（２）のＨＷプロファイラテーブル一時保存手段（１７）、バッファーメモリ（１７’）により構成することができる。上記エントリ単位の格納処理は、例えばＳＷプロファイラ部（２）におけるテーブルエントリ比較手段（１９）、ＨＷテーブルエントリのマージ手段（２１）により行うことができる。
【００３４】
第１０に、上記アシスト装置は、所定のサンプルレートが設定されたレジスタと、上記レジスタに設定された上記サンプルレートに基づいて上記選択手段が選択した分岐命令をサンプリングするサンプリング手段とを有する、上記第８又は９に記載の推定システムにより構成されるものである。
【００３５】
上記レジスタはサンプリング間隔制御レジスタ（９）、上記サンプリング手段はサンプリング部（８）等により構成することができる。
【００３６】
第１１に、複数の分岐命令を含む機械命令による命令パスのうち実行される頻度が高い命令パスを推定する推定方法において、入力される上記各分岐命令のアドレスである分岐アドレスと上記各分岐命令が分岐を指示するアドレスである分岐先アドレスと上記各分岐命令が実行されることによる分岐回数とを１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレスと既に格納された上記分岐アドレス及び上記分岐先アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加して、分岐履歴を格納するプロファイラテーブルが設けられ、上記プロファイラテーブルが格納する分岐履歴のうち上記分岐先アドレスが上記分岐アドレスよりも小さいエントリの上記分岐回数を上記分岐先アドレス毎に合算し、その分岐先アドレスと当該合算回数とを１つのエントリとして格納する戻り分岐先テーブルが設けられ、決定手段が上記戻り分岐先テーブルに格納された分岐先アドレスのうちいずれかを先頭アドレスに決定する決定ステップと、推定手段が上記決定手段により決定された先頭アドレス及び上記プロファイラテーブルに格納された分岐履歴により上記実行される頻度が高い命令パスを推定する推定ステップとを含む、推定方法により構成されるものである。
【００３７】
第１２に、上記推定ステップは、推定手段が、上記決定手段により決定された上記先頭アドレス以降に実行されるアドレスが分岐命令を表すアドレスであるか否かを順次判断する第１のステップと、上記第１のステップにより分岐命令を表すアドレスではないと判断された場合に、当該アドレスを記憶する第２のステップと、上記第１のステップにより分岐命令を表すアドレスであると判断された場合に、上記プロファイラテーブルに格納された分岐履歴により上記分岐命令を表すアドレスであると判断したアドレスと同じ分岐アドレスのエントリを検索し、同じ分岐アドレスのエントリが存在する場合は当該エントリのアドレスを記憶して、検索されたエントリにおける分岐先アドレスが上記先頭アドレスと同じであるか否かを判断する第３のステップと、上記第３のステップにより先頭アドレスと同じでないと判断された場合に、当該エントリの分岐先アドレスにジャンプして、当該アドレスを基準として上記第１〜第３のステップを繰り返し実行する第４のステップと、上記第３のステップにより先頭アドレスと同じと判断した場合に、決定された上記先頭アドレスと上記第２、第３のステップにより記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第５のステップとを含む、上記第１１記載の推定方法により構成されるものである。
【００３８】
第１３に、入力される上記各分岐先アドレスが次回に分岐する際の基本ブロック開始アドレスとして保存されており、上記プロファイラテーブルは、入力される上記分岐アドレスと上記分岐先アドレスと上記分岐回数とに加え、上記保存された基本ブロック開始アドレスも１つのエントリとして格納するテーブルであって、入力される上記分岐アドレス及び上記分岐先アドレス並びに保存された基本ブロック開始アドレスと既に格納された上記分岐アドレス、上記分岐先アドレス及び基本ブロック開始アドレスとが同じ場合には上記各エントリにおける上記分岐回数を更新し、異なる場合には新たなエントリを追加しており、上記推定ステップは、推定手段が、決定された上記先頭アドレスと同じ基本ブロック開始アドレスのエントリを検索し、検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐アドレスまでを記憶し、当該エントリにおける分岐先アドレスを次の検索アドレスとする第１のステップと、上記第１ステップにより検索されたエントリにおける上記分岐先アドレスと同じ基本ブロック開始アドレスのエントリをさらに検索し、当該さらに検索されたエントリにおける上記基本ブロック開始アドレスから上記分岐先アドレスまでを記憶する第２のステップと、上記第２のステップにおける上記分岐先アドレスが上記決定された先頭アドレスと同じときに上記第２のステップにおける記憶を終了し、上記決定された先頭アドレスと上記第１のステップ及び上記第２のステップにより記憶された一連の順次のアドレスとによる命令パスを上記実行される頻度が高い命令パスとして推定する第３のステップとを含む、上記第１１記載の推定方法により構成されるものである。
【００３９】
第１４に、コンピュータに上記第１１、１２又は１３の推定方法を実行させるためのコンピュータプログラムにより構成されるものである。
【００４０】
第１５に、上記第１４に記載のコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体により構成されるものである。
【００４１】
尚、本欄において本発明の構成、動作等に対応して実施形態中の符号をカッコ書で記載したが、これは対応関係を明確にするために便宜上付したものであり、本発明の構成がこれらの構成部材に限定されるものではない。
【発明の効果】
【００４２】
以上のように、本発明によれば、パス構造の事前解析が不要であり、オンラインでプロファイリングを行うことができ、かつホットパスの推定精度の高い推定装置を実現することができる。
【００４３】
また、推定処理に際して収集に必要な情報が少ないため、ソフトウェア実行処理が軽減され、オーバーヘッドを小さくすることができる。
【００４４】
また、推定処理に際して基本ブロック開始アドレスを用いることにより、実行オブジェクトのトラバースの不要な推定精度の高い推定装置を実現し得る。
【００４５】
ソフトウェアにより構成された推定装置をアシストするハードウェアによるアシスト装置を設け該装置にてアシスト側プロファイラテーブルを生成するように構成したので、推定処理においてソフトウェアのオーバーヘッドを軽減することができる。
【００４６】
また、分岐命令収集にサンプリングを行うため、サンプリングレートの適宜の設定により、プロファイラテーブルを記憶するためのメモリ容量を低減し得る。
【００４７】
また、先頭アドレスを検出した後に、プロファイラテーブルに基づいて検出した分岐アドレスの分岐回数の大きい方のエントリを選択しながら推定処理を行うため、極めて精度の高い推定処理を実現し得るものである。
【発明を実施するための最良の形態】
【００４８】
以下、本発明の実施の形態を添付図面に基づいて説明する。
【００４９】
本発明に係る推定装置の全体構成は、図１に示すようにＣＰＵコア５で実行されるアプリケーションプログラムの機械命令を選択してハードウェアプロファイラテーブル１２’（図８参照）（以下、「ＨＷプロファイラテーブル」という）を作成するものであって、ハードウェアで構成されるハードウェアアシスト装置１（以下「ＨＷアシスト装置」という）と、ソフトウェアにより構成されたものであって、上記ＨＷプロファイラテーブル１２’に基づいてソフトウェアプロファイラーテーブル２０’（図１１参照）（以下「ＳＷプロファイラテーブル」という）等を作成し、実行頻度の高いパスの推定処理を行うソフトウェアプロファイラ部２（以下「ＳＷプロファイラ部」という）により構成される。上記ＨＷアシスト装置１において、３はＣＰＵコア５で実行される機械命令のうち、分岐命令を選択するセレクタ、４はセレクタ３から入力する分岐アドレスデータ情報を圧縮し、当該圧縮した分岐アドレス情報列をＳＷプロファイラ部２に送出するハードウェアコンプレッサ（以下、「ＨＷコンプレッサ」という）であり、上記ＳＷプロファイラ部２は、上記情報列を蓄積し、上記多頻度実行パスを推定する処理を行うものである。ここで、上記分岐アドレスデータ情報とは、上記分岐命令のアドレス情報であり、例えば分岐命令の「分岐アドレス」とその分岐先のアドレスを示す「分岐先アドレス」を一組とする集合列（（分岐アドレス、分岐先アドレス）＝ｔ１等）であり、図１中ｔ１、ｔ２、ｔ３等で示されるものをいう。また、上記圧縮した分岐アドレス情報列とは、上記分岐アドレスデータ情報の集合列ｔ１、ｔ２、ｔ３等をその出現回数で纏めた情報列であり、例えば上記アドレス情報がｔ１、ｔ２、ｔ１、ｔ２、ｔ３、ｔ２・・・等であれば、（ｔ１、２）、（ｔ２，３）、（ｔ３，１）等の情報列をいう（図１参照）。
【００５０】
図１に示すような推定装置は、システムＬＳＩ上において、図２に示すように構成される。即ち、上記ＨＷアシスト部１はオンラインプロファイラブロック１ａにハードウェアとして構成され、上記ＳＷプロファイラ部２はメモリブロック６内にランタイムソフトウェアとして格納される。上記ＣＰＵ５はアプリケーションプログラムを実行するものであるが、本発明に係る推定装置はいわゆるオンラインプロファイラとして動作するものであり、当該ＣＰＵコア５におけるアプリケーションプログラムの実行時にアプリケーション本体の動作と並行して動作するものである。尚、図２はカメラ付携帯電話等に適用する場合の一例である。
【００５１】
上記ＨＷアシスト装置１の上記セレクタ３で選択する機械命令のパスは図６に示すようなループパス構造を対象とする。同図において、ＡからＪまでの各ブロックは基本ブロックと呼ばれ、各基本ブロックには機械命令が順に並び、最後に分岐命令が位置している（図７の基本ブロックＡ，Ｂ，Ｃ参照）。尚、同図中、Ｂ→Ｄのように分岐先が１個の場合は無条件分岐、Ｃ→Ｅ、Ｆのように分岐先が２個の場合は条件分岐であることを意味する。ここで、本実施形態においては、図６中の実線で示されたループ（Ａ→Ｂ→Ｄ→Ｇ→Ａ）を高頻度に実行されるループ構造のパス（以下、「ホットパス」という）、破線で示されたループを実線のパスに比べて実行頻度が低いパスと仮定する。図６においては、「ＡＢＤＧＡ、ＡＢＤＧＪＡ、ＡＢＤＨＪＡ、ＡＣＥＩＪＡ、ＡＣＦＩＪＡ」の５個のループパスが存在するが、この実線の高頻度で実行されるポットパスをオンラインで推定する推定装置を提供することが本発明の目的である。尚、説明の簡単のため各基本ブロックの機械命令の先頭アドレスと分岐命令のアドレス（基本ブロックの最終アドレス）を図６に示すように定め、各基本ブロックにおけるアドレスは連続しているものとする。
【００５２】
ここで、以下の実施形態中に使用する本アルゴリズムのデータ構造及び用語を以下の通り定義する。
【００５３】
「分岐アドレス」（ＢＩＡ：Ｂｒａｎｃｈ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ａｄｄｒｅｓｓ）・・分岐命令のアドレスをいう。例えば図６の基本ブロックＡの最終アドレス「１０」等をいう。
【００５４】
「分岐先アドレス」（ＢＴＡ：Ｂｒａｎｃｈ  Ｔａｒｇｅｔ  Ａｄｄｒｅｓｓ）・・分岐命令が分岐を指示するアドレスをいう。図６の基本ブロックＡでは基本ブロックＢ又はＣの先頭アドレス「１１」又は「５１」等をいう。
【００５５】
「分岐回数」（ＢＣ：Ｂｒａｎｃｈ  Ｃｏｕｎｔ）・・分岐アドレス、分岐先アドレスで命令が実行された回数をいう。図６の基本ブロックでは命令の矢印の通過回数をいう。
【００５６】
「ＨＷプロファイラテーブル１２’」（図８参照）・・「分岐アドレス、分岐先アドレス、分岐回数（カウント数）」が１エントリとして記録されるＨＷアシスト装置１内のテーブルをいう。具体的には同アシスト装置１のテーブルメモリ１２（図３）内に形成される。尚、図８のテーブル１２’を含め、以下の説明図（図９〜１３、図２３〜２５）における各テーブルの記憶エリア内には、分岐アドレス、分岐先アドレスの他、分岐命令等の「機械命令」を記載しているが、これは説明のわかりやすさから便宜上記載しているに過ぎず、実際に記憶されるのは各命令に関連するアドレス情報のみである。
【００５７】
「ＳＷプロファイラテーブル２０’」（図１１参照）・・ＨＷアシスト装置１から割り込み通知を受け、ＨＷプロファイラテーブル１２’の内容（「分岐アドレス、分岐先アドレス、カウント数」）を記録するＳＷプロファイラ部２のテーブル２０’をいう。具体的には同プロファイラ部２のＳＷテーブルメモリ２０（図５）内に形成される。
【００５８】
「戻り分岐先テーブル２３’」（図１２参照）・・ＳＷプロファイラテーブル２０’から戻り分岐しているエントリ（ＢＩＡ＞ＢＴＡ）を選択し、分岐先アドレスが同じエントリのカウント数を合算して分岐先アドレス（ＢＴＡ）、分岐回数を１エントリにまとめたテーブルをいう。具体的には同アシスト部２の戻り分岐先テーブル生成手段２３（図５）内に形成されるものである。
【００５９】
「ホットパスアドレステーブル３４」（図１３参照）・・ＳＷプロファイラ部２により、推定されたホットパス上の全ての命令アドレスを記録するテーブルをいう。
【００６０】
「ＨＷプロファイラテーブル一時保存バッファ１７’」（図５参照）・・ＨＷアシスト装置１からの割り込み通知後、読み出したＨＷプロファイラテーブル１２’の内容を一時保存するバッファメモリをいう。
【００６１】
「ホットパス」・・図６の基本ブロックの経路の内、他の経路より高頻度で実行されるパス（経路）でループ構造であるパスをホットパスという。
【００６２】
「ホットパス開始アドレス」・・ホットパスにおいて、戻り分岐により戻った先頭のアドレスをホットパス開始アドレスという。
【００６３】
「基本ブロック開始アドレス」（ＢＳＡ：Ｂａｓｉｃ  ｂｌｏｃｋ  Ｓｔａｒｔ  Ａｄｄｒｅｓｓ）・・前回の分岐の際の分岐先アドレスをいい、第２の実施形態において使用する基本ブロックの開始アドレスをいう。
【００６４】
「実行オブジェクト」・・各基本ブロックにて実行される機械命令により構成されたアプリケーションプログラム等のオブジェクトをいう（図１４参照）。
【００６５】
（１）第１の実施形態
（ａ）ＨＷアシスト装置１について（図３参照）
図３に本発明に係るＨＷアシスト装置１の具体的構成図を示す。同図において、７は分岐命令選択部であり、プロセッサ５の命令実行ユニット５ａで実行されるアプリケーションプログラム等の機械命令の内、分岐命令及びそのアドレスを選択してサンプリング部８に送出するものである。
【００６６】
８はサンプリング部であり、サンプリング間隔制御レジスタ９により設定されたサンプルレートにより上記選択部７から送られてくる分岐命令をサンプリングカウンタ８ａでカウントしながらサンプリングし、サンプリングされた分岐命令のアドレス及びその分岐先アドレス（ｔ１、ｔ２等）を次段のテーブルエントリ比較部１１に送出するものである。上記サンプリング間隔制御レジスタ９に設定されるサンプルレートは、上記分岐命令選択部７において検出された分岐命令の全てを選択するレート（１／１回周期）、或いは２回分岐命令の検出の内１回のみを検出するレート（１／２回周期）、その他１／４，１／８、１／１６、１／３２回周期等の各種レートのサンプリングの設定を行うことができる。
【００６７】
１０はＨＷアシストテーブル管理部であり、当該管理部１０のテーブルメモリ１２内に図８に示すＨＷプロファイラテーブル１２’が形成される。この管理部１０は一例として図４に示されるように構成することができる。当該管理部１０において、１１は上記サンプリング部８から送られてきた分岐アドレス及び分岐先アドレスのエントリが既にＨＷプロファイラテーブル１２’に存在するか否かを判断するテーブルエントリ比較部である。図４においては、分岐先アドレスの比較器１１ａ、分岐アドレスの比較器１１ｂにより構成され、テーブルアドレスポインタ１１ｃにより指定されるＨＷアシストテーブル１２’上のエントリ（分岐アドレス、分岐先アドレス、分岐回数）を一時レジスタ１１ｄに順次読み出し、当該読み出したエントリの分岐先アドレスと分岐アドレスがサンプリング部８から入力した分岐先アドレスと分岐アドレスに一致するか否かを比較するものである。
【００６８】
１４ａはテーブルエントリ更新追加部であり、上記テーブルエントリ比較部１１が上記ＨＷプロファイラテーブル１２’にエントリがないと判断した場合は、上記ＨＷプロファイラテーブル１２’に、当該分岐命令の「分岐アドレス、分岐先アドレス」をカウント数「１」にて新規エントリとして追加するものである（図８（イ）エントリ（ａ）参照）。１４ｂは同じエントリのカウンタ加算部であり、上記比較部１１が既に同一エントリがあると判断した場合は、上記プロファイラテーブル１２’の当該エントリのカウント数をインクリメント（＋１）するものである（図８（ロ）エントリ（ｂ）参照）。図４においてはこれらの手段は、比較器１１ａ，１１ｂに各々接続された新規エントリライトデータ生成部１４ａ’、及び分岐カウント更新データ生成部１４ｂ’により構成され、上記比較器１１ａ，１１ｂにてエントリがないと判断した場合に、上記生成部１４ａ’が上記ＨＷプロファイラテーブル１２’に新規エントリを追加する処理を行い、エントリありと判断された場合は上記生成部１４ｂ’が当該エントリのカウント数をインクリメントする処理を行うように構成することができる。このように、サンプリング部８から入力する情報列（ｔ１、ｔ２等）はＨＷプロファイラテーブル１２’内においては、その出現回数（分岐回数）で纏められて（ｔ１，１０）、（ｔ２，１０１）等の圧縮された形で記録されていく。上記新規エントリの書き込み時は、テーブルヘッドポインタレジスタ１４ｆが上記テーブル１２’の空き先頭アドレスを指示し、該ポインタにより指示されたアドレスを新規エントリのライトアドレス生成部１４ｃにて生成して上記テーブル１２’が書き込み可能状態に設定される。また、分岐カウントの加算時は、分岐カウント更新ポインタ１４ｄにより更新すべきカウントを有するエントリのアドレスが指示され、当該アドレスが更新エントリライトアドレス生成部１４ｅにて生成され上記テーブル１２’が書き込み可能状態に設定される。
【００６９】
１３は、テーブル空きエントリ管理部であり、上記テーブル１２’の各エントリのカウント数を監視しており、該カウント数がオーバーフローした場合（例えばカウンタ１２ａのカウント数が「９９９９９」となった場合）（図９（イ）エントリ（ｃ）参照）、又は上記プロファイラテーブル１２’が最大エントリ数（例えば「５」）に達した場合（図９（ロ）参照）、ソフトウェアへの割り込み通知部１５及びテーブル読み出し削除部１６に通知するものである。図４においては、上記ＨＷプロファイラテーブル１２’のテーブルヘッドポインタレジスタ１４ｆによりＨＷプロファイラテーブル１２’の空きエントリが指示され、テーブルフル判定部１３ａにおいて当該ポインタにより指示されたエントリの分岐カウント値及びエントリ数を監視するように構成することができる。
【００７０】
１５はソフトウェアへの割り込み通知部であり、上記テーブル空きエントリ管理部１３から上記テーブル１２’がオーバーフローした旨又は最大エントリ数に達した旨の通知があるとＳＷプロファイラ部２へ割り込みを通知を行うものである。図４においては、上記テーブルフル判定部１３ａからの通知に基づいてＳＷプロファイラ部２へ割り込みを行うテーブル読み出し部１５ａにより構成することができる。
【００７１】
１６はテーブル読み出し削除部であり、上記割り込み通知部１５が上記割り込み通知を行うことに基づいて、上記ＨＷプロファイラテーブル１２’内の内容、即ち（ｔ１、１００）、（ｔ２、１００）等の圧縮された情報列を一度に全て読み出して、ＳＷプロファイラ部２のＨＷプロファイラテーブル一時保存手段１７に送出するものである。この読み出し削除部１６は上記読み出し後は、上記ＨＷプロファイラテーブル１２’の内容をクリアする（図９（ハ）参照）。図４においては、上記テーブル読み出し部１５ａにより構成することができ、上記テーブルフル判定部１３ａからの通知に基づいて上記ＨＷプロファイラテーブル１２’の内容を読み出して上記ＳＷプロファイラ部２に送出し、上記テーブルヘッドポインタレジスタ１４ｆをゼロクリアするように構成することができる。このように、上記サンプリング部８から入力されるアドレス情報は、上記管理手段１０により圧縮された情報列としてＳＷプロファイラ部２に送出される。従って、上記比較部１１、新規追加部１４ａ，カウンタ加算部１４ｂ，テーブルメモリ１２、エントリ管理部１３、読み出し削除部１６等により分岐情報圧縮手段１０’（ＨＷコンプレッサ４）が構成されている。
【００７２】
（ｂ）ＳＷプロファイラ部２（ホットパス推定装置）について（図５参照）
次に、ＳＷプロファイラ部２の構成を図５の機能ブロックに基づいて説明する。１７はＨＷプロファイラ一次保存手段であり、上記割り込み通知部１５からの割り込み通知に基づいて、上記読み出し削除部１６から送られてくるＨＷプロファイラテーブル１２’の圧縮情報をバッファメモリ１７’に一旦記憶するものである。
【００７３】
１８はＳＷプロファイラテーブル管理手段であり、ＳＷテーブルメモリ２０内に図１１に示すＳＷプロファイラテーブル２０’を作成するものである。当該管理手段１８において、１９はテーブルエントリ比較手段であり、上記バッファメモリ１７’に上記ＨＷプロファイラテーブル１２’の内容が一時保存されると、上記ＳＷプロファイラテーブル２０’の内容と上記バッファメモリ１７’の内容を比較して上記ＳＷプロファイラテーブル２０’に同じエントリが有るか否かを判断するものである。
【００７４】
２１はＨＷテーブルエントリのマージ手段であり、上記比較手段１９が同一エントリがあると判断した場合は、上記ＳＷプロファイラテーブル２０’上の当該エントリのカウント数を合算し（図１０（ロ）エントリ（ｅ）参照）、上記比較手段１９が同一エントリが存在しないと判断した場合は、そのエントリの「分岐アドレス、分岐先アドレス」をそのエントリのカウント数で新規登録する処理を行うものである（図９（イ）エントリ（ｄ）参照）。かかる処理により上記ＳＷテーブルメモリ２０に図１１に示すようなＳＷプロファイラテーブル２０’が作成されるものである。
【００７５】
２３は戻り分岐先テーブル生成手段であり、図１２に示す戻り分岐先テーブル２３’を生成するものである。当該生成手段２３において、２４は戻り分岐エントリ検索手段であり、テーブル読み出し手段２２を介して上記ＳＷプロファイラテーブル２０’の分岐アドレス（ＢＩＡ）と分岐先アドレス（ＢＴＡ）とを順次比較していき、ＢＩＡ＞ＢＴＡのエントリ、即ち戻り分岐であるエントリを検索するものである。
【００７６】
２５は同一エントリのマージ手段であり、上記検索手段２４が検索したＢＩＡ＞ＢＴＡの戻り分岐のエントリが戻り分岐先テーブル２３’に存在しない場合は、当該エントリの分岐先アドレス（ＢＴＡ）をそのカウント数で当該テーブル２３’に登録し、上記検索手段１１が検索したＢＩＡ＞ＢＴＡの戻り分岐のエントリが既に上記テーブル２３’に登録されている場合は、当該エントリのカウント数を合算し、このようにして上記分岐先テーブル２３’（図１２）を作成するものである。
【００７７】
２６はホットパスヘッドアドレス決定手段であり、ホットパスヘッドアドレス閾値決定レジスタ２７に予め定められた閾値と、上記戻り分岐先テーブル２３’のエントリの各カウント数とを比較し、上記閾値を超えるカウント数のエントリがある場合は、当該エントリの分岐先アドレス（ＢＴＡ）をホットパスヘッドアドレス候補として認識する処理を行うものである。具体的には、上記閾値を超えるエントリが存在せず、ホットパスヘッドアドレス候補が存在しない場合は処理を終了し、当該候補が１個存在する場合は、当該エントリの分岐先アドレス（ＢＴＡ）（例えば図１２のアドレス「１」）をホットパスヘッドアドレス候補として図１３に示すホットパステーブル３４の先頭エリア（ｕ）に登録するものである。また、このようなホットパスヘッドアドレス候補が複数存在する場合は、未だホットパスヘッドアドレス候補となっていない分岐先アドレス（ＢＴＡ）でアドレスが最小の分岐先アドレス（ＢＴＡ）をホットパスヘッドアドレス候補として上記ホットパステーブル３４の先頭エリア（ｕ）に登録するものである。尚、上記閾値決定レジスタ２７にて設定される閾値はアプリケーションプログラムの実行状況等に応じて任意に設定することができるものである。
【００７８】
２８は実行オブジェクトのトラバース手段であり、上記ホットパスヘッドアドレス候補を検出開始アドレスとして実行オブジェクトをトラバースして分岐命令を検索していくものである。具体的には、実行オブジェクトにおいて、上記ホットパスヘッドアドレス候補（例えばアドレス「１」）の次に実行されるアドレス「２」の命令Ａ２から順次、その命令が分岐命令であるか否かを検索していく（図１４参照）。そして次のアドレスが分岐命令でない場合は、その実行オブジェクトの検出アドレス（例えばアドレス「２」）をホットパステーブル３４の上記ホットパスヘッドアドレス候補の次のエリア（ｖ）に登録し、検出アドレスの次のアドレス（例えばアドレス「３」）を次の検出アドレスとして当該アドレスについて同様の処理を繰り返す。上記検出アドレスが分岐命令であると判断した場合は（例えば、基本ブロックＡの分岐命令Ａ、アドレス「１０」）、当該アドレスを同一ＢＩＡエントリの検索手段２９に通知する処理を行うものである。
【００７９】
２９は同一ＢＩＡエントリの検索手段であり、上記トラバース手段２８において実行オブジェクトにて分岐命令（例えばアドレス「１０」の分岐命令Ａ）を検出した場合は、ＳＷプロファイラテーブル２０’を参照し、検出した分岐命令のアドレス（上記アドレス「１０」）と同一の分岐アドレス（ＢＩＡ）が存在するか否かを検索する。そして、ＳＷプロファイラテーブル２０’に同一の分岐アドレス（ＢＩＡ）がない場合は、次のホットパスヘッドアドレス候補を検索する処理に移行する。上記ＳＷプロファイラテーブル２０’に同一の分岐アドレス（ＢＩＡ）が存在した場合は、ホットパスとするＢＴＡ決定手段３０にそのアドレス（たとえば、上記アドレス「１０」）を通知するものである。
【００８０】
３０はホットパスとするＢＴＡ決定手段であり、上記検索手段２９からの通知に基づいて、ＳＷプロファイラテーブル２０’にＢＩＡ＝検出した分岐命令のアドレス（例えば、分岐アドレス「１０」）のエントリが２個以上あるか否かを検出し、２個以上ある場合は、カウント数の大きいエントリの分岐先アドレス（ＢＴＡ）を選択し（テーブル２０’の例えばエントリ（ｇ））、１個の場合は、当該エントリの分岐先アドレス（ＢＴＡ）を選択し、選択したエントリの分岐先アドレス（ＢＴＡ）をホットパス検索終了決定手段３１に通知するものである。
【００８１】
３１はホットパス検索終了決定手段であり、上記決定手段３０で選択したエントリの分岐先アドレス（ＢＴＡ）（例えばエントリ（ｇ）の分岐先アドレス「１１」）がホットパスヘッドアドレス候補（例えばアドレス「１」）と同一であるか否かを判断するものである。
【００８２】
３２は実行オブジェクトのトラバース再開アドレス決定手段であり、上記終了決定手段３１が選択したエントリの分岐先アドレス（ＢＴＡ）（上記分岐先アドレス「１１」）がホットパスヘッドアドレス候補（例えば上記アドレス「１」）と同一でないと判断した場合は、当該エントリの分岐先アドレス（ＢＴＡ）（上記アドレス「１１」）にジャンプして、当該アドレスの次のアドレス（例えばアドレス「１２」）を検出アドレスとして当該検出アドレスを上記トラバース手段２８に通知するものである。尚、上記トラバース手段２８では通知された検出アドレス（上記アドレス「１２」）から実行オブジェクトのトラバースを再開する。
【００８３】
３３はホットパス保存出力手段であり、上記ホットパス検索終了決定手段３１が選択したエントリの分岐先アドレス（ＢＴＡ）がホットパスアドレス候補と同一であると判断した場合は、ホットパステーブル３４の内容を全て出力し、戻り分岐先テーブル２３’の内容をクリアする。ここで、出力されたホットパステーブルの内容がホットパスとなる。
【００８４】
（ｃ）動作説明
本発明の推定装置は上述のように構成されるものであるから、次に、本発明の装置の動作を図１５から図１８のフローチャートに基づいて説明する。
【００８５】
（ｃ−１）ＨＷアシスト動作（図１５参照）
まず、ＣＰＵ５においてアプリケーションプログラムが実行され、図６に示すループパス構造の基本ブロックが矢印に示すように実行されるものとする。ここで、ＨＷアシスト装置１の分岐命令選択部７はＣＰＵ５の命令実行ユニット５ａにおいて分岐命令が実行される度に、当該分岐命令のアドレス及び分岐先アドレスを選択してサンプリング部８に送出する（図１５Ｐ１）。サンプリング部８は入力する分岐命令をサンプリングカウンタ８ａでカウントし、カウント値がサンプリング間隔制御レジスタ９に設定されているサンプリングレート（ここでは１／１回周期とする）に等しくなった時点、即ち、この場合は全ての分岐命令の検出の度に分岐命令の分岐アドレス及び分岐先アドレスをテーブルエントリ比較部１１に送出していく（図１５Ｐ２、Ｐ３）。尚、上記サンプリング部８は上記サンプリングカウンタ８ａのカウント値がサンプリングレートに等しくなった時点でサンプリングカウンタ８ａをクリアしていく（図１５Ｐ４）。
【００８６】
上記テーブルエントリ比較部１１は、上記サンプリング部８から入力する分岐命令の分岐アドレス及び分岐先アドレスがテーブルメモリ１２内のＨＷプロファイラテーブル１２’に既に存在しているか否かを判断し（図１５Ｐ５）、該エントリが存在しないと判断された場合は、テーブルエントリの新規追加部１４ａが、上記テーブル１２’に空エントリがあるいか否かを検出し、空きエントリが存在すると判断した場合は、当該分岐命令の「分岐アドレス、分岐先アドレス」をカウント数「１」で上記ＨＷプロファイラテーブル１２’に登録する（図１５Ｐ６、Ｐ７、図８（イ）エントリ（ａ）参照）。このような処理を繰り返し行うことで上記ＨＷプロファイラテーブル１２’にエントリを順次追加してく。
【００８７】
また、上記比較部１１が、上記サンプリング部８から入力する分岐命令の上記アドレス情報が上記ＨＷプロファイラテーブル１２’に既に存在していると判断した場合は、同じエントリのカウンタ加算部１４ｂが当該エントリのカウント数をインクリメント（＋１）する（図１５Ｐ８、図８（ロ）エントリ（ｂ）参照）。そして、テーブル空きエントリ管理部１３はＨＷプロファイラテーブル１２’の各エントリのカウント数がオーバーフローしたか否かを判断し、オーバーフローしていないと判断した場合は、上記比較部１１及び上記加算部１４ｂにて同様の処理を繰り返し行い、これにより各エントリのカウント数が順次インクリメントされていく（図１５Ｐ８、Ｐ９）。
【００８８】
また、上記テーブル空きエントリ管理部１３が上記テーブル１２’に空エントリが存在しないと判断した場合は（図１５Ｐ６）、ＨＷプロファイラテーブル１２’に最大エントリ数まで分岐命令が記録されたことになるので、ソフトウェアへの割り込み通知部１５がＳＷプロファイラ部２に割り込み通知を行った後、テーブル読み出し削除部１６が上記ＨＷプロファイラテーブル１２’の全ての内容を（ｔ１，１００）、（ｔ２、１００）等の圧縮情報列として読み出し、当該情報列をＳＷプロファイラ部２のＨＷプロファイラテーブル一時保存手段１７に送出し、上記テーブル１２’をクリアする（図１５Ｐ１０）。
【００８９】
また、上記テーブル空きエントリ管理部１３が上記テーブル１２’のカウント数が「９９９９９」となりオーバーフローしたと判断した場合は（図１５Ｐ９）、同様に割り込み通知部１５がＳＷプロファイラ部２に割り込み通知を行った後、読み出し削除部１６が上記ＨＷプロファイラテーブル１２’の全ての内容を上記圧縮情報列として読み出し、ＳＷプロファイラ部２のＨＷプロファイラテーブル一時保存手段１７に送出し、上記テーブル１２’をクリアする（図１５Ｐ１０）。
【００９０】
（ｃ−２）ＳＷプロファイラ部２の動作（図１６〜）
上記ソフトウェアプロファイラ部２のＨＷプロファイラテーブル一時保存手段１７は、上記割り込み通知に基づいて送られてきた上記ＨＷプロファイラテーブル１２’の内容を一時保存バッファメモリ１７’に全て書き込む（図１６Ｐ１、Ｐ２）。
【００９１】
すると、テーブルエントリ比較手段１９は、上記バッファメモリ１７’の各エントリ内容とＳＷテーブルメモリ２０内のＳＷプロファイラテーブル２０’の各エントリの内容との比較を行う（図１６Ｐ３、Ｐ４）。当該比較が終了すると、ＨＷテーブルエントリマージ手段２１は、上記比較手段１９の比較結果に基づいて、ＳＷプロファイラテーブル２０’にバッファメモリ１７’と同じエントリが存在する場合は、当該ＳＷプロファイラテーブル２０’のカウント数にバッファメモリ１７’の同一エントリのカウント数を合算する（図１６Ｐ５、Ｐ６、図１０（ロ）エントリ（ｅ）参照）。また、上記マージ手段２１は、ＳＷプロファイラテーブル２０’にバッファメモリ１７’と同じエントリが存在しない場合は、該バッファメモリ１７’の内容、即ち、「分岐アドレス、分岐先アドレス、カウント数」をそのまま新規登録する（図１６Ｐ７、図１０（イ）エントリ（ｄ）参照）。このような処理により、上記ＳＷプロファイラテーブル２０’には、図１１に示すような分岐命令の履歴を示すテーブルが形成される。
【００９２】
上記ＳＷプロファイラテーブル２０’が作成された時点で、即ち、上記バッファメモリ１７’の全エントリについての比較が終了し次の割り込み通知の待機状態となった時点で（図１６Ｐ４、Ｐ１）、図１７に示すホットパス推定処理が行われる。まず、戻り分岐先テーブル生成手段２３の戻り分岐エントリ検索手段２４が、上記ＳＷプロファイラテーブル２０’に登録されている各エントリの分岐アドレス（ＢＩＡ）と分岐先アドレス（ＢＴＡ）とを順次比較していき、ＢＩＡ＞ＢＴＡ、即ち、戻り分岐であるエントリが存在するか否かを判断する（図１７Ｐ１，Ｐ２）。そして、ＢＩＡ＞ＢＴＡのエントリ（図１１のＳＷプロファイラテーブル２０’においてエントリ（ｋ）の「分岐命令Ｊ」（１００＞１）とエントリ（ｍ）の「分岐命令Ｇ」（４０＞１））が存在する場合は、同一エントリのマージ手段２５がそのエントリと同一のエントリが戻り分岐先テーブル２３’（図１２）に既に存在するか否かを判断し（図１７Ｐ３）、同一エントリが存在しない場合は、当該機械命令Ａ１の分岐先アドレス「１」をそのカウント数「９００」で上記戻り分岐先テーブル２３’に新規登録する（図１７Ｐ４、図１２（イ）参照）。上記マージ手段２５は上記エントリと同一のエントリが存在する場合は、戻り分岐先テーブル２３’の当該エントリのカウント数に新規エントリのカウント数を合算する（図１７Ｐ５、図１２（ロ）参照）。本実施形態では、上記エントリ「ｋ」と「ｍ」のカウント数「９００」と「６００」が合算されて「１５００」となる。
【００９３】
このようにして、上記ＳＷプロファイラテーブル２０’中の全てのエントリについてＢＩＡ＞ＢＴＡであるか否かが比較され、戻り分岐のエントリの分岐先アドレス（ＢＴＡ）及びそのカウント数が戻り分岐先テーブル２３’に記憶されていく（図１７Ｐ６）。この結果、戻り分岐先テーブル２３’には図１２（ロ）に示すように、ＢＩＡ＞ＢＴＡであるエントリの分岐先アドレス（ＢＴＡ）「１」及びそのカウント数の合算「１５００」が登録される。
【００９４】
全ての戻り分岐アドレスについて上記戻り分岐先テーブル２３’への登録が終了すると（図１７Ｐ６）、ホットパスヘッドアドレス決定手段２６は、上記分岐先テーブル２３’の各エントリのカウント数とホットパスヘッドアドレス閾値決定レジスタ２７に登録されている閾値（この場合「１０００」とする）とを比較していき（図１７Ｐ７）、上記閾値を超えているカウント数である分岐先アドレスをホットパスヘッドアドレス候補として認識する（図１７Ｐ８、Ｐ９）。このような閾値との比較動作を上記戻り分岐先テーブル２３’に登録されている全てのエントリについて行う（図１７Ｐ１０）。本実施形態の場合、上記戻り分岐テーブル２３’の分岐先アドレス「１」のカウント数「１５００」は閾値「１０００」を超えているので、当該分岐先アドレス（ＢＴＡ）「１」がホットパスヘッドアドレス候補として認識される。
【００９５】
その後、上記決定手段２６はホットパスヘッドアドレス候補が１個の場合は、当該候補の分岐命令Ａ１の分岐先アドレス「１」をホットパステーブル３４（図１３）の先頭エリア（ｕ）に登録する（図１７Ｐ１１、Ｐ１２，Ｐ１３）。上記ホットパスアドレス候補が複数存在する場合は、当該候補の内、未だホットパスヘッドアドレス候補となっていない分岐先アドレスの内、最小アドレスの分岐命令の分岐先アドレスをホットパステーブル３４に同様に登録する（図１７Ｐ１２、Ｐ１４）。上記決定手段２６は上記ステップＰ１１において、ホットパスアドレス候補が存在しない場合は、処理を終了する。
【００９６】
上記ホットパステーブル３４にホットパスヘッドアドレス候補「１」が登録されると、実行オブジェクトトラバース手段２８が、上記決定手段２６で決定したホットパスヘッドアドレス候補「１」を検出開始アドレスとして、実行オブジェクトのトラバースを行う（図１８Ｐ１５、図１４参照）。即ち、上記トラバース手段２８は、上記検出開始アドレス「１」の次の命令Ａ２のアドレス「２」が分岐命令であるか否かを判断する（図１８Ｐ１６）。そして、分岐命令でないと判断した場合は、その機械命令Ａ２とアドレス「２」をホットパステーブル３４における上記ホットパスアドレス候補の次の記録エリア（ｖ）に登録し（図１３参照）、当該アドレスの次のアドレス「３」を検出アドレスとして、当該アドレスの機械命令（本実施形態では命令「Ａ３」）が分岐命令であるか否かを同様に検索していく（図１８Ｐ１７，Ｐ１８）。従って、かかる処理により、分岐命令が検出されない限り、ホットパステーブル３４に上記機械命令のアドレスが順次記録されていく（図１３参照）。尚、上記ステップＰ１８にて全てのアドレスにて分岐命令が検出されなかった場合は処理を終了する。
【００９７】
上記ステップＰ１６において分岐命令を検出し、その検出アドレスが分岐命令Ａの分岐アドレス「１０」である場合は、同一ＢＩＡエントリ検索手段２９がＳＷプロファイラテーブル２０’を参照し、当該検出分岐命令のアドレス「１０」と同一アドレスが当該テーブル２０’の分岐アドレス（ＢＩＡ）に存在するか否かを検索する（図１８Ｐ１９）。そして上記検索手段２９がＳＷプロファイラテーブル２０’において、検出分岐アドレス＝分岐アドレス（ＢＩＡ）が存在すると判断した場合は（図１８Ｐ２０）、次にホットパスとするＢＴＡ決定手段３０が当該検出分岐アドレス＝ＢＩＡのエントリが２個以上あるか否かを判断し（図１８Ｐ２１）、２個以上ある場合はカウント数の大きい方のエントリの分岐先アドレス（ＢＴＡ）を選択する（図１８Ｐ２２）。本実施形態の場合、ＳＷプロファイラテーブル２０’には、分岐アドレス（ＢＩＡ）＝１０のエントリが２つ存在するので（図１１におけるエントリ（ｇ）と（ｏ））、カウント数の大きいエントリである分岐先アドレス（ＢＴＡ）が「１１」、カウント数「１０００」のエントリ（ｇ）が選択される。その後、上記トラバース手段２８が上記検出分岐アドレス「１０」と選択された分岐先アドレス「１１」をホットパステーブル３４に登録する（図１８Ｐ２３、Ｐ２４、図１３）。上記ステップＰ２１で検出分岐アドレス＝ＢＩＡのエントリが１個の場合は当該エントリの分岐先アドレス（ＢＴＡ）が選択され、当該分岐アドレスと分岐先アドレスがホットパステーブル３４に登録される（図１８Ｐ２１、Ｐ２３、Ｐ２４）。その後、ホットパス検索終了決定手段３１は、上記選択された分岐先アドレス（ＢＴＡ）「１１」について、当該分岐先アドレス（ＢＴＡ）が上記ホットパスヘッドアドレス候補「１」と同一か否か判断し（図１８Ｐ２５）、本実施形態の場合、未だ同一でないので、実行オブジェクトのトラバース再開アドレス決定手段３２が、実行オブジェクトの当該分岐先アドレス「１１」にジャンプして、当該分岐先アドレス「１１」の次の実行アドレス「１２」を検出開始アドレスとして、上記ステップＰ１６からの処理を繰り返す（図１８Ｐ２６）。このようにして、上記ホットパスヘッドアドレス候補「１」から順次カウント数の大きい分岐命令、即ち実行頻度の高い分岐命令がホットパステーブル３４に登録されていく。上記ステップＰ２０において、ＳＷプロファイラテーブル２０’にステップＰ１６にて検出された分岐命令のアドレスと同一の分岐アドレスが存在しない場合は、図１７のステップＰ１１に戻って次のホットパスヘッドアドレス候補を選択して（図１７Ｐ１１〜Ｐ１４）、ステップＰ１５からの処理を繰り返す。上記ステップＰ１１にてホットパスヘッドアドレス候補が存在しない場合は処理を終了する。
【００９８】
上記ステップＰ２６から引き続いて、上記検出アドレス「１２」から順次、実行オブジェクトのトラバースが行われ（図１８Ｐ１６）、分岐命令が検出されるまでは、当該機械命令のアドレスがホットパステーブルに順次登録されていく（図１８Ｐ１７）。そして、ステップＰ１６において分岐命令Ｂ、分岐アドレス「２０」が検出されると、ＳＷプロファイラテーブル２０’から当該アドレス「２０」の分岐アドレス（ＢＩＡ）（エントリ（ｈ））が検出され（図１８Ｐ１９、Ｐ２０）、ステップＰ２３、Ｐ２４においてＢＩＡ「２０」とＢＴＡ「２１」がホットパステーブル３４に登録され、ステップＰ２５において当該ＢＴＡ「２１」はホットパスヘッド候補「１」と同一でないと判断され、当該エントリ（ｈ）のＢＴＡであるアドレス「２１」にジャンプする。そして、該アドレス「２１」から順次トラバースが行われ、同様にステップＰ１６において次の分岐命令Ｄ、分岐アドレス「３０」が検出される。当該分岐アドレス「３０」はＳＷプロファイラテーブル２０’に２つのエントリ（ｉ）（ｌ）が存在するため、ステップＰ２２においてカウント数の大きいエントリ（ｌ）（命令Ｇ１、分岐先アドレス「３１」）が選択される。そしてステップＰ２３、Ｐ２４においてＢＩＡ「３０」とＢＴＡ「３１」がホットパステーブル３４に登録され、ステップＰ２５においても当該ＢＴＡ「３１」は未だホットパスヘッドアドレス候補「１」と一致しないので、さらに、ステップＰ２６にて当該アドレス「３１」にジャンプして、当該アドレス「３１」から実行オブジェクトのトラバースが行われる。そして、再びステップＰ１６において分岐命令が検出されるまで機械命令とアドレスがホットパステーブル３４に登録されていく。本実施形態ではホットパステーブル３４に基本ブロックＧのアドレス「３９」までが登録されたとする。
【００９９】
その後、ステップＰ１６において、次の分岐命令として分岐アドレス「４０」が検出されると、上記ステップＰ２１にてＳＷプロファイラテーブル２０’において、ＢＩＡ＝分岐アドレス「４０」のエントリが検索され（エントリ（ｍ）（ｎ））、ステップＰ２２においてカウント数の大きいエントリ（ｍ）の分岐先アドレス「１」が選択され、上記ステップＰ２３、Ｐ２４において、当該ＢＩＡ＝「４０」とＢＴＡ＝「１」がホットパステーブル３４に登録され、ステップＰ２５において当該分岐先アドレス「１」とホットパスヘッドアドレス候補「１」の一致が検出される。この時点で、図６の基本ブロックの実線で示されたループ構造の命令パスが上記ホットパステーブル３４に登録されたことになる。
【０１００】
そこで、ステップＰ２７において、ホットパス保存出力手段３３が上記ホットパステーブル３４の内容、即ち、ホットパスヘッドアドレス候補「１」（記録エリア（ｕ））から命令Ａ１、アドレス「１」（記録エリア（ｙ））までの内容を保存した上で出力する。
【０１０１】
上述のように、上記検索終了決定手段３１において、上記分岐先アドレス（ＢＴＡ）がホットパスヘッドアドレス候補に一致すると判断したとき（図１８Ｐ２５）、実行オブジェクトにおいて機械命令のループが上記ホットパスヘッドアドレス候補「１」に戻ったことになるので、この時点でホットパステーブル３４には実行頻度の高いループ、即ちホットパスのループを構成するアドレスが登録されたことになる。従って、上記ステップＰ２５にて一致を検出すると、ホットパス保存出力手段３１が上記ホットパステーブル３４の内容を保存した上で出力し、上記ホットパステーブル３４、戻り分岐先テーブル２３’の内容をクリアして処理を終了する（図１８Ｐ２７、Ｐ２８）。
【０１０２】
以上のように、上記第１の実施形態によれば、アプリケーションプログラムのパス構造の事前解析が不要であり、アプリケーションプログラムに特別なプログラムを付加することなく、オンラインでプロファイリングを行うことができ、ホットパスの推定精度の高い推定装置を実現することができる。
【０１０３】
また、推定処理に際して収集に必要な情報が、機械命令の「分岐アドレス、分岐先アドレス、分岐回数」と少ないため、ソフトウェア実行処理が軽減され、オーバーヘッドを小さくすることができ、アプリケーションプログラムの実行速度の低下等、パフォーマンスの低下を抑えることができる。
【０１０４】
また、ソフトウェアにより構成された推定装置をアシストするハードウェアによるアシスト装置を設け、同装置におけるＨＷプロファイラテーブル１２’に分岐履歴情報を一旦登録し、その後当該分岐情報をＳＷプロファイラ部２へ一括して送出するように構成したので、ＨＷプロファイラテーブル作成時に、ＳＷプロファイラ部２から直接プロセッサの分岐情報を取得する等、アプリケーションプログラムに割り込みをかける必要がなく、このためソフトウェアのオーバーヘッドを軽減することができる。
【０１０５】
また、分岐命令収集にサンプリングを行うため、サンプリングレートの適宜の設定により、プロファイラテーブルを記憶するためのメモリ容量を低減し得る。
【０１０６】
また、ホットパスヘッドアドレス候補の検出は、適宜サンプリングされた分岐アドレス情報にて行い、ホットパスの推定は上記候補のアドレスを基準として実行オブジェクトをトラバースすることにより行われれるため、完全でない分岐情報収集であってもサンプリングレート、或いは閾値設定等を適宜行うことにより、精度の高いパスプロファイリングが可能である。
【０１０７】
また、プロファイラテーブルには、分岐アドレスと分岐先アドレスをその出現回数（分岐回数）で纏めて登録するので、各テーブル１２’、２０’等のメモリ容量を低減することができるし、ＨＷアシスト装置１からＳＷプロファイラ部２への情報の伝送も（ｔ１、１００）等の圧縮された情報列で行うことができ、効率的なシステムを構築し得る。
【０１０８】
また、高頻度で実行されるパスの決定が、各パスの分岐条件成立、不成立回数の情報を元に行われるため、パス情報の決定が正確であり、その結果、精度の高い推定処理を行うことができる。即ち、各パスの条件分岐をも考慮した上で該条件分岐においては分岐回数の大きい方を選択する処理により実行頻度の高い命令パスを選択していくため、精度の高い推定を行うことができる。
【０１０９】
また、戻り分岐である分岐先アドレスのカウント数としての閾値を基準にホットパスヘッドアドレス候補を検出しているため、閾値設定を変更することで、アプリケーションプログラムの動作状況等に対応した適切なホットパスヘッドの推定処理を実現することができる。
【０１１０】
また、本推定装置は、ホットパスヘッドアドレス候補を検出した後に、実行オブジェクトのトラバースを行い、ＳＷプロファイラテーブル２０’に基づいて、検出した分岐アドレスの分岐回数の大きい方のエントリを選択しながら推定処理を行うため、精度の極めて高い推定装置を実現し得る。
【０１１１】
また、かかる推定処理において、選択した分岐命令のアドレスをホットパステーブル３４に記録しながら推定処理を行うため、推定処理の終了条件（ＢＴＡ＝ホットパスヘッドアドレス候補）に到達した時点において、ホットパステーブル３４に既にホットパスのアドレスが全て記録されており、その後は当該ホットパステーブルの内容を出力するだけでよいため、迅速な推定処理及びホットパスの保存を実現し得る。
【０１１２】
また、ハードウェア回路のコスト、ソフトウェアコードの実装コストとプロファイリングのパス推定の正確さ、プロファイラ自体の実行オーバーヘッドによるパフォーマンス低下はトレードオフの関係にあるが、サンプリングレートの選択、テーブルの実装規模、ホットパス決定の閾値設定値の選択等により容易に調整ができ、適用されるアプリケーションプログラム等に応じて最適な推定装置を実現できる。即ち、分岐命令収集にサンプリングを行い、完全でない分岐情報収集であっても閾値設定等を適宜行うことにより、精度の高いパスプロファイリングが可能である。
【０１１３】
（２）第２の実施形態（図１９〜）
この実施形態では、ＳＷプロファイラ部２における推定処理において、実行オブジェクトのトラバースを不要としたオンラインプロファイラアルゴリズムを示す（図１９から図２１参照）。尚、上記第１の実施形態と同一部分については同一符号を用い、以下の説明においては、第１の実施形態と相違部分を中心として説明する。
【０１１４】
（ａ）ＨＷアシスト装置について
上記図３で示したブロック図において、前分岐命令蓄積レジスタ９’を分岐命令選択部７とテーブルエントリ比較部１１との間に追加する。このレジスタ９’は、上記分岐命令選択部７から分岐命令及びそのアドレス情報を受け、分岐先アドレスを次回に分岐する際の基本ブロック開始アドレス（ＢＳＡ）として保存し、当該基本ブロック開始アドレスをテーブルエントリ比較部１１に送出するものである（図１９Ｐ１’）。ここで、基本ブロック開始アドレスは、例えば図６の基本ブロックＡでは、前回の分岐先アドレスである命令Ａ１のアドレス「１」、基本ブロックＢでは、前回の分岐先アドレスである命令Ｂ１のアドレス「１１」等である。
【０１１５】
また、ＨＷプロファイラテーブル１２”のエントリには図２３に示すように、基本ブロック開始アドレスＢＳＡが追加される。従って、例えば基本ブロックＡについてのエントリは、基本ブロック開始アドレスである「（命令Ａ１）アドレス１」、分岐アドレスである「（分岐命令Ａ）アドレス１０」、分岐先アドレスである「（命令Ｂ１）アドレス１１」及び「カウント数」となる。
【０１１６】
上記テーブルエントリ比較部１１は、上記サンプリング部８から入力する分岐先アドレス、分岐アドレスに基づいて上記ＨＷプロファイラテーブル１２”に既に同一エントリが存在するか否か判断し（図１９Ｐ５）、同一エントリが存在しない場合は、上記テーブルエントリ新規追加部１４ａがその分岐アドレス、分岐先アドレスに上記蓄積レジスタ９’に保存されている当該エントリの前回の分岐先アドレス（例えば基本ブロックＢであれば分岐先アドレス「１１」）を読み出して基本ブロック開始アドレスとしてこれらのアドレスをカウント数「１」で新規登録する（図１９Ｐ６、Ｐ７’）。また、既に同一エントリが存在する場合は、上記カウンタ加算部１４ｂがそのエントリのカウンタをインクリメント（＋１）し、割り込み発生まで順次ＨＷプロファイラテーブル１２”に登録していく（図１８Ｐ８〜Ｐ１０）。このような処理により、上記第１の実施形態と同様にＨＷプロファイラテーブル１２”（図２３）が生成されていく。
【０１１７】
（ｂ）ＳＷプロファイラ部２（図２２参照）
このＳＷプロファイラ部２においては、上記実行オブジェクトのトラバース手段２８の代わりにＢＳＡエントリ検索手段２８’を設け、実行オブジェクトのトラバース再開アドレス決定手段３２の代わりに検索アドレス決定手段３２’を設け、かつ上記同一ＢＴＡエントリ検索手段２９の代わりに同一ＢＳＡエントリ検索手段２９’を設け、当該ＢＳＡ検索手段２８’により、ＳＷプロファイラテーブル２０”（図２４）の基本ブロック開始アドレス（ＢＳＡ）の検索を行うものである。
【０１１８】
上記ＨＷプロファイラテーブル１２”からバッファメモリ１７’への一時登録、及びＳＷプロファイラテーブル２０”への各種データの登録処理は、図２４に示すようにＳＷプロファイラテーブル２０”に基本ブロック開始アドレス（ＢＳＡ）が追加される点を除いては、第１実施形態の図１６Ｐ１〜Ｐ７の処理と同一であり、当該処理により図２４に示すＳＷプロファイラテーブル２０”が形成される。
【０１１９】
上記ＳＷプロファイラテーブル２０”が作成された時点で、図２０以下に示すホットパス推定処理が行われる。図２２を参照して、まず戻り分岐先テーブル生成手段２３の戻り分岐エントリ検索手段２４が、上記ＳＷプロファイラテーブル２０”に登録されている各エントリの分岐アドレス（ＢＩＡ）と分岐先アドレス（ＢＴＡ）とを順次比較していき、ＢＩＡ＞ＢＴＡ、即ち、戻り分岐であるエントリが存在するか否かを判断する（図２０Ｐ１，Ｐ２）。そして、ＢＩＡ＞ＢＴＡのエントリ（図２４のＳＷプロファイラテーブル２０”において「分岐命令Ｊ」（１００＞１）と「分岐命令Ｇ」（４０＞１）のエントリ（ｋ）（ｍ））が存在する場合は、同一エントリのマージ手段２５がそのエントリと同一のエントリが戻り分岐先テーブル２３’に存在するか否かを判断し（図２０Ｐ３）、同一エントリが存在しない場合は、当該分岐先アドレス「１」をそのカウント数「９００」で上記戻り分岐先テーブル２３’に登録する（図２０Ｐ４、図１２（イ）参照）。上記マージ手段２５は上記エントリと同一のエントリが存在する場合は、当該エントリのカウント数を合算する（図２０Ｐ５、図１２（ロ）参照）。このようにして、上記ＳＷプロファイラテーブル２０”中の全てのエントリについてＢＩＡ＞ＢＴＡであるか否かが比較され、戻り分岐のエントリの分岐先アドレス及びカウント数が戻り分岐先テーブル２３’に記憶されていく（図２０Ｐ４、Ｐ５）。この結果、戻り分岐先テーブル２３’には図１２（ロ）に示すように、ＢＩＡ＞ＢＴＡであるエントリの分岐先アドレス「１」及びそのカウント数の合算「１５００」が登録される。
【０１２０】
そして、ホットパスヘッドアドレス決定手段２６は、上記分岐先テーブル２３’の各エントリのカウント数とホットパスヘッドアドレス閾値決定レジスタ２７に登録されている閾値（この場合「１０００」とする）とを比較していき（図２０Ｐ６）、上記閾値を超えているカウント数である分岐先アドレスが１個の場合は、その分岐先アドレスをホットパスヘッドアドレス候補として認識し、当該候補のアドレスをホットパステーブル３４’の先頭エリア（ｕ）に登録する（図２０Ｐ７、Ｐ８、図２５）。上記閾値を超えるＢＴＡ、即ちホットパスヘッドアドレス候補が複数ある場合は、上記第１の実施形態と同様に、ホットパスヘッド候補となっていないＢＴＡで最小アドレスの分岐先アドレス（ＢＴＡ）をホットパステーブルに登録する（図２０Ｐ７、Ｐ９）。そして、このような比較動作をＳＷプロファイラテーブル２０”の全てのエントリについて行う（図２０Ｐ１０）。本実施形態の場合、上記分岐先アドレス「１」のカウント数「１５００」は閾値「１０００」を超えているので、当該分岐先アドレス「１」がホットパスヘッドアドレス候補として認識される。
【０１２１】
その後、ＢＳＡエントリ検索手段２８’が、上記ホットパスヘッドアドレス候補（アドレス「１」）を検索開始アドレスとし（図２１Ｐ１１）、同一ＢＳＡエントリの検索手段２９’がＳＷプロファイラテーブル２０”にホットパスヘッドアドレス候補「１」と同一の基本ブロック開始アドレス（ＢＳＡ）が存在するか否かを検索する（図２１Ｐ１２）。本実施形態の場合は、エントリ（ｇ）にアドレス「１」の基本ブロック開始アドレスが存在するので、当該検索手段２８’は上記検索手段２９’からの通知に基づいてそのエントリの検索開始アドレス（ＢＩＡ）「１」から分岐アドレス（ＢＩＡ）「１０」までのアドレスをホットパステーブル３４’に記録する（図２１Ｐ１３、図２５）。尚、上記ステップＰ１２にてホットパスヘッドアドレス候補と同一のＢＳＡが存在しない場合は処理を終了する。
【０１２２】
次に、同一ＢＳＡエントリ検索手段２９’は、ＳＷプロファイラテーブル２０”に検索開始アドレス＝基本ブロック開始アドレス（ＢＳＡ）のエントリの内、ＢＴＡのみが異なるエントリが複数あるか否かを検索し（図２１Ｐ１４）、検索開始アドレス＝基本ブロック開始アドレス（ＢＳＡ）のエントリが１個の場合はホットパスとするＢＴＡの決定手段３０が当該エントリの分岐先アドレス（ＢＴＡ）を次の検索アドレスとし（図２１Ｐ１４、Ｐ１５）、そのようなエントリが複数ある場合は、上記決定手段３０がカウント数の大きいエントリの分岐先アドレス（ＢＴＡ）を次の検索アドレスとする（図２１Ｐ１６）。本実施形態の場合、上記検索開始アドレス「１」＝基本ブロック開始アドレス（ＢＳＡ）のエントリの内、ＢＴＡが異なるエントリ（ｇ）（ｏ）の２個存在するので、カウント数の大きいエントリ（ｇ）の分岐先アドレス（ＢＴＡ）「１１」が次の検索アドレスとなる。
【０１２３】
そして、上記エントリ検索手段２９’はＳＷプロファイラテーブル２０”上に上記次の検索アドレス「１１」＝基本ブロック開始アドレス（ＢＳＡ）が存在するか否かを判断し（図２１Ｐ１７）、そのようなエントリが存在する場合は、次の検索アドレス＝ＢＳＡのエントリの内、ＢＴＡが異なるエントリが複数あるか否かを判断し（図２１Ｐ１８）、そのようなエントリが複数存在する場合は、ホットパスとするＢＴＡの決定手段３０がカウント数の大きいエントリの分岐先アドレス（ＢＴＡ）を次の検索アドレスとし（図２１Ｐ１９）、当該エントリが１個の場合は、当該エントリの分岐先アドレス（ＢＴＡ）を次の検索アドレスとする（図２１Ｐ１８）。本実施形態の場合、上記分岐先アドレス「１１」＝基本ブロック開始アドレス（ＢＳＡ）のエントリは１個（エントリ（ｈ））なので、当該エントリ（ｈ）の分岐先アドレス「２１」が次の検索アドレスとなる。さらに、引き続いて上記ＢＳＡエントリ検索手段２８’は上記基本ブロック開始アドレス「１１」から分岐先アドレス「２１」までをホットパステーブル３３’に登録する（図２１Ｐ２０）。
【０１２４】
その後、ホットパス検索終了決定手段３１が当該分岐先アドレス「２１」がホットパスヘッドアドレス候補に等しいか否かを判断し（図２１Ｐ２１）、等しくない場合は、検索アドレスの決定手段３２’が当該分岐先アドレス「２１」を検索アドレスとして（図２１Ｐ２２）、上記ステップＰ１７に戻って同様の処理を繰り返し行う。これにより、上記ホットパステーブル３４’には実行頻度の高いパスのアドレスが順次記録されていく。具体的には、上記ステップＰ２２において上記分岐先アドレス（ＢＴＡ）「２１」が次の検索アドレスとなり、ステップＰ１７においてＢＳＡ＝次の検索アドレス「２１」のエントリ（ｉ）（ｌ）が検出され、ステップＰ１９においてカウント数の大きいエントリ（ｌ）の分岐先アドレス（ＢＴＡ）「３１」が選択され、ステップＰ２０においてＢＳＡ「２１」からＢＴＡ「３１」までがホットパステーブル３４’に記録され、ステップＰ２１において当該分岐先アドレス（ＢＴＡ）「３１」がホットパスアドレス候補「１」と同一でないと判断される。
【０１２５】
その後は、上記ＢＴＡ「３１」が次の検索アドレスとされ（図２１Ｐ２２）、ステップＰ１７においてＳＷプロファイラテーブル３４’にＢＳＡ＝検索アドレス「３１」のエントリ（ｍ）（ｎ）が検出され、上記ステップＰ１９においてカウント数の大きいエントリ（ｍ）のＢＴＡ「１」が選択され、上記ステップＰ２０においてＢＳＡ「３１」からＢＴＡ「１」までがホットパステーブル３４’に登録された上で、上記ステップＰ２１において当該検索アドレス「１」がホットパスヘッドアドレス候補「１」に等しいと判断される。
【０１２６】
このように、上記ステップＰ２１において、検索アドレス「１」がホットパスヘッドアドレス候補「１」に一致した場合、実行オブジェクトにおいて機械命令のループが上記ホットパスヘッドアドレス候補「１」に戻ったことになるので、この時点でホットパステーブル３４’には実行頻度の高いループ、即ちホットパスのループを構成するアドレスが登録されたことになる。従って、上記ステップＰ２１にて一致を検出すると、ホットパス保存出力手段３３が上記ホットパステーブル３４’の内容（記憶エリア（ｕ）から（ｚ）の内容）を保存した上で出力し、上記ホットパステーブル３４’、戻り分岐先テーブル２３’の内容をクリアして処理を終了する（図２１Ｐ２３、Ｐ２４）。尚、上記ステップＰ１２でホットパスヘッド＝ＢＳＡのエントリが存在しない場合、及び上記ステップＰ１７でＢＳＡ＝次検索アドレスが存在しない場合は、何れも処理を終了する。
【０１２７】
上述のように、第２の実施形態によれば、上記第１の実施形態と同様の効果を得られると共に、推定処理に際してＳＷプロファイラテーブル２０”に基本ブロック開始アドレス（ＢＳＡ）を用いることにより実行オブジェクトのトラバースが不要であるため、アプリケーションプログラムに対して割り込みを行うことなく推定処理を行うことができ、アプリケーションプログラムの動作性能の低下をより少なくすることができると共に、より高速の推定処理を実現し得るものである。
【０１２８】
また、トラバースを不要としても、基本ブロック開始アドレスＢＳＡ等に基づいて分岐回数の大きい命令パスをホットパステーブル３４’に記録していく処理を行うため、第１の実施形態と同様に精度の高い推定装置を実現し得るものである。
【図面の簡単な説明】
【０１２９】
【図１】本発明に係る推定装置の概念的ブロック図である。
【図２】同上推定装置をシステムＬＳＩ上に実装した場合の構成図である。
【図３】同上装置のＨＷアシスト装置のブロック図である。
【図４】同上ＨＷアシスト装置のブロック図である。
【図５】同上装置のＳＷプロファイラ部の機能ブロック図である。
【図６】同上装置における推定の対象となるパス構造を示す説明図である。
【図７】同上パス構造における基本ブロックを示す説明図である。
【図８】（イ）（ロ）共にＨＷプロファイラテーブルへのエントリの登録を示す図である。
【図９】（イ）（ロ）（ハ）は共にＨＷプロファイラテーブルを示すものであり、ＳＷプロファイラ部への読み出し状態を示す図である。
【図１０】（イ）（ロ）共にＳＷプロファイラテーブルへのエントリの登録を示す図である。
【図１１】ＳＷプロファイラテーブルを示す図である。
【図１２】（イ）（ロ）共に戻り分岐先テーブルを示す図である。
【図１３】ホットパステーブルを示す図である。
【図１４】実行オブジェクトのトラバース状況を示す図である。
【図１５】ＨＷアシスト装置における動作を示すフローチャートである。
【図１６】ＳＷプロファイラ部における動作を示すフローチャートである。
【図１７】ＳＷプロファイラ部における動作を示すフローチャートである。
【図１８】ＳＷプロファイラ部における動作を示すフローチャートである。
【図１９】第２の実施形態のＨＷアシスト装置における動作を示すフローチャートである。
【図２０】同上実施形態のＳＷプロファイラ部における動作を示すフローチャートである。
【図２１】同上実施形態のＳＷプロファイラ部における動作を示すフローチャートである。
【図２２】同上実施形態のＳＷプロファイラ部の機能ブロック図である。
【図２３】同上実施形態のＨＷプロファイラテーブルを示す図である。
【図２４】同上実施形態のＳＷプロファイラテーブルを示す図である。
【図２５】同上実施形態のホットパステーブルを示す図である。
【符号の説明】
【０１３０】
１  ＨＷアシスト装置
２  ＳＷプロファイラ部
５  プロセッサ
７  分岐命令選択手段
８  サンプリング部
９  サンプリング間隔制御レジスタ
９’  前分岐命令蓄積レジスタ
１１  テーブルエントリ比較部
１１ａ，１１ｂ  比較器
１２  テーブルメモリ
１２’、１２”    ＨＷプロファイラテーブル
２０  ＳＷテーブルメモリ
２０’，２０”    ＳＷプロファイラテーブル
２３’    戻り分岐先テーブル
３４，３４’    ホットパステーブル
【図１】
2005092532.tif 000003
【図２】
2005092532.tif 000004
【図３】
2005092532.tif 000005
【図４】
2005092532.tif 000006
【図５】
2005092532.tif 000007
【図６】
2005092532.tif 000008
【図７】
2005092532.tif 000009
【図８】
2005092532.tif 000010
【図９】
2005092532.tif 000011
【図１０】
2005092532.tif 000012
【図１１】
2005092532.tif 000013
【図１２】
2005092532.tif 000014
【図１３】
2005092532.tif 000015
【図１４】
2005092532.tif 000016
【図１５】
2005092532.tif 000017
【図１６】
2005092532.tif 000018
【図１７】
2005092532.tif 000019
【図１８】
2005092532.tif 000020
【図１９】
2005092532.tif 000021
【図２０】
2005092532.tif 000022
【図２１】
2005092532.tif 000023
【図２２】
2005092532.tif 000024
【図２３】
2005092532.tif 000025
【図２４】
2005092532.tif 000026
【図２５】
2005092532.tif 000027