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

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

国内特許コード P110005973
整理番号 QP070040
掲載日 2011年11月28日
出願番号 特願2007-094075
公開番号 特開2008-250867
登録番号 特許第4892387号
出願日 平成19年3月30日(2007.3.30)
公開日 平成20年10月16日(2008.10.16)
登録日 平成23年12月22日(2011.12.22)
発明者
  • 吉松 則文
  • 吉田 真
  • 村上 和彰
  • 須賀 敦浩
出願人
  • 財団法人福岡県産業・科学技術振興財団
  • 国立大学法人九州大学
  • 富士通株式会社
発明の名称 実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体
発明の概要

【課題】 少ないメモリ容量で、高速に実行頻度の高い命令列の実行パスを検出できる実行パス検出装置等を提供する。
【解決手段】 実行頻度が高い命令列の実行パスを検出するための実行パス検出装置は、分岐命令を含む命令列を1ブロックとする命令列ブロックの先頭アドレスの命令の実行回数が格納される実行履歴テーブル310と、分岐命令の分岐履歴が格納される分岐履歴テーブル320と、分岐命令の分岐履歴を収集する処理を行う分岐履歴管理部220とを含み、実行回数が所与の閾値を超えたことを条件に、分岐履歴管理部220が、分岐履歴の収集を開始すると共に、実行パスを特定するためのパス情報を分岐履歴に基づいて出力する。
【選択図】 図6

従来技術、競合技術の概要


アプリケーションプログラムを実行するプロセッサの処理の高速化や低消費電力化を実現するために、プログラムの局所性に着目した手法が提案されている。この手法は、プログラムを実行する上でクリティカルな命令列を発見し、該命令列の処理の最適化を図ることで処理の高速化や低消費電力化を実現するものである。このようなクリティカルな命令列を発見する手法として、命令列に含まれる分岐命令の実行履歴を利用する手法がある。



例えば特許文献1には、命令列の命令が実行される方向とは逆方向である戻り方向に分岐する分岐命令の実行回数に着目してループ構造の命令部分を検出し、ループ構造の命令の実行回数が多いと判断されるパス経路を記録する分岐履歴記録装置が開示されている。即ち、特許文献1では、プログラムのループ構造の部分に局所性が存在するという仮定の下で、該パス経路を実行頻度の高い命令列の実行パスとして検出する。



また、例えば特許文献2には、分岐命令の分岐履歴が格納されるプロファイラテーブルと、戻り方向の分岐先アドレス及び分岐回数が格納される戻り分岐先テーブルとを設け、戻り分岐先テーブルの分岐先アドレスとプロファイラテーブルに格納された分岐履歴とに基づいて、実行頻度の高い命令列の実行パスを検出する推定装置が開示されている。

【特許文献1】特開2000-148482号公報

【特許文献2】特開2005-92532号公報

産業上の利用分野


本発明は、実行パス検出装置、情報処理装置、実行パス検出方法、プログラム及び記録媒体に関する。

特許請求の範囲 【請求項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記載のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
産業区分
  • 演算制御装置
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2007094075thum.jpg
出願権利状態 権利存続中
上記の特許・技術に関心のある方は、下記問合せ先にご相談下さい。


PAGE TOP

close
close
close
close
close
close
close