JPH10254700A - 個々の命令の実行頻度をサンプリングするプロセッサ性能カウンタ - Google Patents

Abstract

(57)【要約】 【課題】 コンピュータシステムの性能関連事象をカウ
ントするための性能カウンタを提供する。 【解決手段】 プロセッサは、実行パイプラインと、こ
の実行パイプラインの端に接続されたリタイアユニット
とを備えている。プロセッサは、プログラムの命令を実
行する。命令が実行される間に性能データを収集する装
置は、プロセッサのリタイアユニットに接続されたレジ
スタを備えている。実行パイプラインから命令がリタイ
アされるときにレジスタを増加するための手段が設けら
れる。又、この装置は、レジスタが所定値まで増加され
たときに割り込みハンドラーに割り込みを発生するため
の手段も備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般に、コンピュ
ータシステムに係り、より詳細には、コンピュータシス
テムの性能関連事象をカウントするための性能カウンタ
に係る。

【０００２】

【従来の技術】動作しているコンピュータシステムの性
能データの収集は、ハードウェア及びソフトウェアエン
ジニアにより行われる頻繁で且つ非常に重要な作業であ
る。ハードウェアエンジニアは、新しいコンピュータハ
ードウェアが既存のオペレーティングシステム及びアプ
リケーションプログラムでいかに動作するかを決定する
ために性能データを必要とする。

【０００３】プロセッサ、メモリ及びキャッシュのよう
なハードウェア構造体の特定の設計は、同じ１組のプロ
グラムに対して著しく異なるそして時には予想し得ない
使い方をすることがある。ハードウェアの欠陥を識別し
て、将来の設計においてそれらを修正できるようにする
ことが重要である。性能データは、ソフトウェアがいか
に効率的にハードウェアを使用するかを識別できると共
に、改良されたシステムを設計する上で助けとなる。

【０００４】ソフトウェアエンジニアは、プログラムの
重大な部分を識別する必要がある。例えば、コンパイラ
ーの著者は、コンパイラーが命令を実行のためにいかに
スケジュールするか、又はソフトウェアに最適な入力を
与えるために条件分岐の実行をいかに良好に予想するか
を見出さねばならない。同様に、オペレーティングシス
テム、カーナル、デバイスドライバ、及びアプリケーシ
ョンソフトウェアプログラムの性能を理解することが重
要である。

【０００５】

【発明が解決しようとする課題】コンピュータシステム
の動作環境を妨げることなく、ハードウェア及びソフト
ウェアシステムの性能を正確に監視することが問題であ
る。特に、性能データが何日又は何週間といった長期間
にわたって収集される場合に問題となる。多くの場合
に、性能監視システムは、手作りされる。システムのオ
ペレーションが監視システムにより影響されないよう確
保するために、コストのかかるハードウェア及びソフト
ウェア変更を行う必要がある。

【０００６】コンピュータシステムの性能を監視できる
１つの方法は、性能カウンタを使用することによるもの
である。性能カウンタは、システムにおける重大な事象
の発生を「カウント」する。重大な事象は、例えば、キ
ャッシュミス、命令実行、Ｉ／Ｏデータ転送要求、等々
を含む。性能カウンタを周期的にサンプリングすること
により、システムの性能を推論することができる。

【０００７】更に、実際の事象をサンプリングするため
に、事象に関連してアクセスされる命令又はデータを厳
密に知ることも有用である。しかしながら、ほとんどの
性能カウンタでは、割り込みにおいて得られるプログラ
ムカウンタ（ｐｃ）値は、カウンタをサンプリングする
割り込みが処理を完了した後に実行されるべき次の命令
のｐｃ（割り込み復帰アドレス）である。ほとんどの場
合に、割り込み復帰後に実行されるべき次の命令は、割
り込みを生じた事象を生じさせた命令ではなくて、その
後の命令である。それ故、アクセス時に、重大なプロセ
ッサ事象を表す命令又はデータの位置を直接的に決定す
ることが望ましい。

【０００８】

【課題を解決するための手段】本発明によれば、１つ以
上のプロセッサを含むコンピュータシステムにおいて性
能データを収集するための装置が提供される。コンピュ
ータシステムは、１つ以上のプロセッサを含むことがで
きる。プロセッサは、実行パイプラインと、この実行パ
イプラインの端に接続されたリタイアユニットとを含
む。本発明は、その広い形態において、プロセッサの性
能データを収集するための請求項１に記載の装置に係
る。

【０００９】性能データを収集する装置は、プロセッサ
のリタイアユニットに接続されたレジスタを備えてい
る。このレジスタは、命令が実行パイプラインからリタ
イアされるときにレジスタを増加するための手段に接続
される。レジスタが所定値まで増加されたときに割り込
みハンドラーへ割り込みを発生する手段は、割り込みハ
ンドラーがレジスタをサンプリングできるようにする。

【００１０】本発明の好ましい実施形態において、上記
装置は、リタイアによりカウンタをオーバーフローさせ
そして割り込みを生じさせるような命令に関連したプロ
グラムカウンタ値を記憶するための内部プロセッサレジ
スタも備えている。プログラムカウンタ値の識別は、命
令がリタイアされるときに内部プロセッサレジスタに記
録することができる。これは、個々の命令に対しリタイ
ア率の正確な統計学的サンプルを収集できるようにす
る。

【００１１】

【発明の実施の形態】本発明は、添付図面を参照した特
定の実施形態の以下の詳細な説明より容易に理解されよ
う。システムの概要 図１に示すように、コンピュータシステム１００は、バ
ス１４０により互いに接続された中央処理ユニット（Ｃ
ＰＵ）１１０、メモリサブシステム（メモリ）１２０、
及び入力／出力インターフェイス（Ｉ／Ｏ）１３０を備
えている。このシステム１００は、埋め込まれたシステ
ム、ＰＣ、ワークステーション、メインフレーム、又は
ネットワークでリンクされたコンピュータシステムのク
ラスターである。

【００１２】好ましい実施形態においては、ＣＰＵ１１
０は、高速パイプラインを使用するように設計された１
つ以上の個々のプロセッサチップ１１１を備えている。
パイプラインでは、各プロセッサ１１１は、多数の実行
ユニット１１３を用いて多数の命令を同時に発生しそし
てそれに基づいて動作することができる。実行ユニット
１１３は、整数演算、フローティングポイント演算、ロ
ード、記憶、分岐等の種々のオペレーションを実行する
ことができる。典型的に、パイプライン型プロセッサ
は、ＲＩＳＣアーキテクチャーを使用する。パイプライ
ン型アーキテクチャーでは、命令がメモリからフェッチ
され、発生待ち行列へとスケジューリングされ、実行さ
れ、そしてリタイアされる。

【００１３】各プロセッサ１１１には、１組の性能カウ
ンタ１１２が関連される。各組のカウンタ１１２は、複
数のレジスタとして実施できる。これらのレジスタは、
例えば実行される命令のようなシステムの性能を表すシ
ステムの重要な事象の発生をカウントすることができ
る。これらレジスタは、増加することができ、そしてオ
ーバーフロー時に、これらレジスタに割り込んで、レジ
スタに記憶されたカウントを性能データとしてサンプリ
ングすることができる。

【００１４】メモリサブシステム１２０は、静的、動
的、ランダム、逐次、揮発性及び永続的記憶素子、又は
その組合せを含むことができる。これらの記憶素子は、
レジスタ、キャッシュ、ＤＲＡＭ、ディスク、テープ等
である。キャッシュは、同じプロセッサチップ上のプロ
セッサと共に常駐する命令及びデータキャッシュ（Ｉキ
ャッシュ及びＤキャッシュ）を含むことができる。メモ
リ１２０は、マシンで実行可能な命令の形態のソフトウ
ェアプログラム１２１と、命令によりアクセスされるデ
ータ１２２とを記憶する。ソフトウェアプログラム１２
１は、オペレーティングシステム、デバイスドライバ及
びアプリケーションプログラムを含むと共に、以下に詳
細に述べるようにシステム１００の性能データを測定し
そして分析するのに使用されるプログラムを含むことが
できる。

【００１５】Ｉ／Ｏ１３０は、プリンタやターミナルや
キーボード等の入力／出力デバイスへのインターフェイ
スを含むことができる。又、Ｉ／Ｏ１３０は、ライン１
５０を経て、他のコンピュータシステムにデータを通信
するネットワークに接続することもできる。バス１４０
は、通常、アドレス、データ、制御及びタイミング信号
を種々のシステム要素間に搬送するための複数のライン
として実施される。

【００１６】一般的なオペレーション システム１００のオペレーション中に、プログラム１２
１の命令がプロセッサ１１１により実行される。各命令
は、その命令によりどんなオペレーションを実行すべき
かを知らせるオペレータコードを含む。又、命令は、オ
ペレーション中に使用すべき付加的なデータを参照する
ための１つ以上のオペランドを含むこともできる。命令
は、一般に、プログラムの実行流を制御するか、又はデ
ータをアクセス（読み取り及び書き込み）する。又、処
理速度を上げるために、プロセッサは、分岐予想ロジッ
ク（図示せず）も備えている。分岐予想ロジックは、予
想される実行順序で命令をロードするように試みる。通
常のオペレーティング環境を著しく妨げることなくシス
テム１００において実行されるプログラムのプロファイ
ルを発生することが望まれる。プロファイルは、好まし
い実施形態においては、プログラム１２１の種々の命令
の各々により被る動的なストールサイクルの平均数の指
示を含む。１つの効果として、各命令に対する動的なス
トールサイクルの平均数を使用して、プロセッサの発生
待ち行列における命令ストールの考えられる動的な原因
を決定することができる。

【００１７】プロファイリングサブシステム 図２は、本発明の好ましい実施形態によるサブシステム
２００の流れ線図である。このサブシステム２００は、
制御流れ分析モジュール２１０と、性能データ分析器３
００とを備えている。マシンで実行可能なコードの形態
のプログラム１２１は、制御流れ分析モジュール２１０
に与えられる。プログラム１２１は、カーナル及びアプ
リケーションプログラム、例えば、完全に実行可能な
「２進イメージ」を含むことができる。マシンコードを
分析するためのプロセスの一例が、１９９６年７月２３
日付けのスリバスタバ氏等の「コンピュータシステム性
能を監視するシステム(System for Monitoring Compute
r System Performance) 」と題する米国特許第５，５３
９，９０７号に開示されている。

【００１８】制御流れ分析器２１０は、コード１２１を
データ構造体２０６に仕切る。この構造体２０６は、手
順２０１を含み、そしてこれら手順２０１は、基本的な
ブロック２０２を含むことができる。仕切られた構造体
２０６は、手順及び基本的なブロックを識別するための
情報を含むことができる。通常、手順は、単一の入口ポ
イントと、単一の出口ポイントとを有する。基本的なブ
ロック２０２は、第１命令が実行される場合に全てが実
行される命令のグループ又はセットとして定義される。
換言すれば、基本的なブロックのいずれか１つの命令の
実行頻度が既知の場合には、そのブロックの全ての命令
の実行頻度が分かる。というのは、全ての命令が同じ回
数だけ実行されるからである。それ故、このような基本
的なブロックの命令は、同じ頻度の等価クラスに属する
と言える。

【００１９】稀なケースでは、基本的なブロックの種々
の命令を異なる回数で実行することができる。これは、
基本的なブロックが等価クラスを自動的に構成しないこ
とを意味する。例えば、ブロックの中間に割り込み又は
例外条件が生じるが、その割り込み又は例外からの復帰
がなされない場合には、ブロックのそれ以前の命令がそ
れ以降の命令よりも頻繁に実行されることになる。この
ような割り込み及び例外により導入される歪は、通常は
僅かであり、そして歪がコードにおける特定の命令に相
関されそして頻繁でもある非常に稀な環境を除くと無視
することができる。

【００２０】手順２０１及び基本的なブロック２０２の
命令は、制御流れグラフ（ＣＦＧ）２０３を形成するよ
うに更に分析される。例えば、分岐及びジャンプのよう
な命令を識別することにより、手順と基本的なブロック
との間の実行の流れを決定することができる。ＣＦＧ２
０３において、ノード２０４（円）は、手順又は基本的
なブロックを表し、そしてこれらノードを接続するエッ
ジ２０５（指向されたアーク）は、ノード間の実行の流
れを表す。制御流れグラフ２０３は、基本的なブロック
及びアークのための頻度等価クラスを決定するのに使用
される。基本的なブロック及びアークの両方を検討する
ことにより、頻度等価クラスをできるだけ大きくするこ
とができる。

【００２１】マシンで実行できるコード１２１の分析に
加えて、コード１２１は、実行のためにシステム１００
にロードされる。実行中に、図１の性能カウンタ１１２
をサンプリングして、サンプル２０９を発生することが
できる。これらサンプルは、例えば、コード１２１の各
命令を発生するためにプロセッササイクルの平均数を指
示することができる。発生のために実際に必要な平均サ
イクル数を、プログラムの理想的な実行中に必要なサイ
クル数と比較して、パイプラインストールの考えられる
原因を決定することができる。ＣＦＧ２０３、構造体２
０６及びサンプル２０９は、性能データ分析器３００へ
送られる。性能データ分析器３００は、例えば、各命令
ごとに性能データ３４０を発生し、この性能データは、
実行の頻度、命令を発生するのに必要な平均サイクル数
（ｃｐｉ）、及びパイプラインストールの考えられる原
因を含むことができる。

【００２２】性能データのサンプリング 図３に示すように、性能データ分析器３００は、ステッ
プ３１０で実行されたコードの命令に対しサンプルカウ
ント２０９を収集する。性能データは、何らかの既知の
プロファイリングシステムにより収集することができ
る。ステップ３２０では、実行される命令の実行頻度が
サンプルカウントに基づいて推定される。ステップ３３
０の間に、各命令に対する平均サイクル数３４０が決定
される。平均サイクル数は、命令がいかに良好にスケジ
ュールされたかそしてストールがいかに頻繁に生じるか
の良好な指示である。この情報を使用して、システム１
００のハードウェア及びソフトウェアの設計を改善する
と共に、動的なパイプラインストールの原因を決定する
ことができる。

【００２３】導入される頻度推定値 図４は、図３のステップ３２０のサブステップ４００を
示す。ステップ４１０において、制御流れグラフ２０３
を使用し、コード１２１の命令が頻度等価クラスにグル
ープ分けされる。頻度等価クラスとは、上記したよう
に、同じ実行頻度を有すると分かっている命令又はアー
クのセットであり、例えば、同じ回数だけ実行された命
令である。同じ等価クラスにおけるアークは、同じ回数
だけ横断される。例えば、基本的なブロックがいかに頻
繁に実行されるか分かっている場合には、その基本的ブ
ロックの各命令の実行頻度も分かる。

【００２４】命令の各頻度等価クラスに対する実行頻度
は、ステップ４２０において推定され、初期頻度推定値
が決定される。これらの初期頻度推定値は、ステップ４
３０において純化処理されて、最終的な頻度推定値４４
０が形成される。これら推定値は、クラス間制約４５１
を使用して等価クラス間に推定頻度をローカルに且つグ
ローバルに伝播することにより純化処理される。クラス
間制約４５１は、以下に述べる設定ステップ４５０にお
いて制御流れグラフ２０３から導出される。

【００２５】制御流れグラフの処理 図５及び６を使用して、図４のステップ４１０のサブス
テップ５００を詳細に説明する。ステップ４１０の目的
は、制御流れグラフ２０３の分析に基づき命令及びアー
クを頻度等価クラスにグループ分けすることである。定
義によれば、命令は、それらがプログラムの実行におい
て同じ回数だけ実行される場合に頻度等価である。同様
に、基本的ブロック及び制御流れアークは、それらがプ
ログラムの実行において同じ回数だけ実行され又は横断
される場合に頻度等価である。同じ基本的ブロックにお
ける命令は、常に、頻度等価である。というのは、１つ
の命令が実行されるときには、定義により、他の全ての
命令も実行されるからである。異なる基本的ブロックに
おける命令は、それに対応する基本的ブロックが頻度等
価である場合には、頻度等価となる。

【００２６】従って、サブステップ５００は、頻度等価
の基本的ブロック及び制御流れアークを識別することを
目的とする。これは、頻度等価に密接に関連した特性で
あるサイクル等価である基本的ブロック及びアークを表
すノードを識別するために制御流れグラフ２０３を分析
することにより達成される。定義によれば、グラフにお
けるノード及びアークのセットは、そのグラフの各サイ
クル即ち閉じた経路がそれらを全て含むか又は全く含ま
ない場合にサイクル等価となる。サイクル等価のノード
及びアークを識別する方法は、プロシーディングズ・オ
ブ・ＡＣＭ ＳＩＧＰＬＡＮ ’９４ コンファレンス
・オン・プログラミング・ランゲッジ・デザイン・アン
ド・インプレメンテーション、１９９４年の第１７１−
１８５ページに掲載されたジョンソン氏等の「プログラ
ム構造ツリー：直線的な時間での制御領域の計算(The P
rogram Structure Tree: Computing Control Regions i
n Linear Time)」に説明されている。しかしながら、グ
ラフにおけるサイクル等価は、頻度等価を意味しない。
以下の説明は、制御流れグラフを拡張しそしてグラフを
サブグラフに分割することにより頻度等価をいかに決定
するかについて述べる。次いで、各サブグラフに対する
サイクル等価を決定することができる。

【００２７】入口及び出口ノード 図６に示すように、手順のための制御流れグラフ５１４
は、入口ノード５１２及び出口ノード５１３と称する２
つの特殊なノードを含む。これらのノードは、制御が手
順５１４に入りそして出るポイントを表す。公知の方法
は、入口ノードから手順の他の各ノードへの経路があり
そして他の各ノードから手順の出口ノードへの経路もあ
るような流れグラフの制御にのみ適用される。本発明
は、これら制約を必ずしももたない更に一般的な制御流
れグラフにも適用できるように方法を改善する。

【００２８】拡張された流れグラフ 図５のステップ５１０において、制御流れグラフは、出
口ノードから入口ノードへアーク５１５で拡張される。
図６のステップ５１１は、ノード５１２−５１３及びア
ーク５１５のためのこの変換を示している。ステップ５
２０において、拡張された制御流れグラフは、既知の方
法を使用して強く接続されたサブグラフに分解され、こ
れについては、例えば、ＳＩＡＭジャーナル・オン・コ
ンピューティング、１（２）：１４６−１６０、１９７
２年に掲載されたタージャン著の「深さ優先探索及びリ
ニアグラフアルゴリズム(Depth-first search and line
argraph algorithms)」を参照されたい。

【００２９】定義によれば、グラフの強く接続された成
分は、各ノードから他の各ノードへの経路が存在する最
大サブグラフである。図６のステップ５２１は、この分
解を示し、破線のボックス５２２−５２４で包囲された
３つの強く接続されたサブグラフが生じる。以下の説明
の目的上、「デッドエンド」サブグラフ又は成分５２４
とは、そのノードからグラフの他のノードへのアークを
もたずに強く接続された成分として定義される。

【００３０】ステップ５３０において、デッドエンドに
入る全てのアークは、出口ノードへ再指向される。これ
は、図６のステップ５３１によりアーク５４２の再指向
と共に示されている。ステップ５４０において、ジョン
ソン氏等により開発されたサイクル等価を計算する方法
が各デッドエンド成分５２４に適用される。各デッドエ
ンド成分５２４に対し、この方法は、デッドエンド成分
５２４におけるノード及びアークのサイクル等価クラス
を形成する。ステップ５５０において、この方法は、グ
ラフの残り部分に適用され、その残り部分に対するサイ
クル等価クラスを生じる。これら２つのステップは、図
６のステップ５４１に示されている。これら最後の２つ
のステップで形成されたサイクル等価クラスは、元のグ
ラフの頻度等価クラスを構成する。

【００３１】頻度及び命令当たりのサイクル（ｃｐｉ）
の推定 プログラムの各命令に対して実行頻度及び命令当たりの
サイクル（ｃｐｉ）を推定する方法と、これらの値に基
づいてパイプラインストールの理由を推論する方法とに
ついて、以下に詳細に説明する。これらの方法（Ａ−
Ｄ）は、次の順に説明する。 Ａ．性能のボトルネック又は問題、即ちパイプラインス
トールを、プログラムの個々の命令のレベルで識別する
ための方法； Ｂ．プログラムの個々の命令の実行頻度を推定する方
法； Ｃ．動的なストールの考えられる原因を推論する方法；
及び Ｄ．本発明による性能カウンタを用いてプログラムの個
々の命令の実行頻度を測定する方法（及び装置）。

【００３２】これらの方法では、周期的なサンプリング
に基づくサンプルカウントは、各々の命令が発生待ち行
列のヘッドにおいて費やす合計時間のみに比例すること
に注意されたい。周期的なサンプリングは、実行頻度に
関する情報を直接的に与えるものではない。実行頻度
は、方法Ｂについて述べるサンプルカウントから推定す
ることもできるし、又は方法Ｄを用いて直接測定するこ
ともできる。

【００３３】性能の問題を識別する方法Ａ 図７に示されたように、方法Ａ（６００）に必要な入力
データは、次のものを含む。 １．分析されるプログラム； ２．各命令のサンプルカウント。但し、このカウント
は、発生された命令が、応答なしにリタイアされ、即ち
応答に対する無カウント発生であって、例外条件の処理
により再発生される命令であるときに、発生待ち行列の
ヘッドにおいて費やされる時間に比例する；そして ３．分析されるシステムのためのモデル又はシュミレー
タ。

【００３４】第１に、プログラム６０１が実行されると
きに、生のサンプルカウント６０３が命令に対して収集
される。図３のステップ３１０も参照されたい。これ
は、異なるＰＣ値を有する命令に対しサンプルカウント
が決定されることを意味する。サンプルカウントは、順
序正しいプロセッサの発生待ち行列のヘッドにおいて命
令が費やす時間（サイクル数）に比例する。いかなる性
能カウンタサンプリング技術もここに使用できることを
理解されたい。生のサンプルの異常は、ステップ６４０
において除去（正規化）され、信頼性のあるサンプル６
０４を発生することができる。異常は、多発生命令によ
るか、又はストールサイクルがその後発生される命令と
重畳するような遅延実行を伴う命令によるものである。

【００３５】第２に、システムのモデル又はシステムシ
ュミレータ（６０２）を使用して、動的なストールがな
いという仮定でプログラムの命令を理想的にスケジュー
リングすることができる（６１０）。このステップは、
全ての静的なストール及びそれらの原因を識別する。理
想的なスケジュールから、ステップ６２０において、各
命令を発生するのに必要な最小の（理想的な）サイクル
数を識別することができる。

【００３６】第３に、最小のサイクルカウント及び正規
化されたサンプルカウント６３０を使用して、各命令の
実行頻度をステップ６５０において推定することができ
る。実行頻度は、命令が「リタイア」された回数であ
る。リタイアされたとは、命令が実行を完了したことを
意味する。これは、少なくとも次の３つの方法で行うこ
とができる。 １）いかなるプログラムについても、これは、上記第１
ステップからのサンプルカウントのみに依存する以下の
方法Ｂを用いて行うことができる。 ２）決定論的アプリケーションプログラムについては、
基本的ブロックの実行をカウントする従来のプロファイ
リング技術を用いて頻度を決定することもできる。この
場合、プログラムは、従来のプロファイラを用いて実行
され、実行頻度が得られる。この場合に、同等のサンプ
ルカウントを得るために同じ入力データでプログラムを
再実行しなければならない。 ３）いかなるプログラムについても、これは、命令がリ
タイアされる割合をサンプリングするために改善された
ハードウェア性能カウンタに依存する方法Ｄを用いて行
うこともできる。

【００３７】第４に、ステップ６６０において各命令の
命令当たりのサイクル（ｃｐｉ）を決定し、即ち各命令
を発生するのに必要とされる平均サイクル数を決定す
る。この値は、所与の命令に対するサンプルカウントを
その実行頻度で除算することにより計算できる。図３の
ステップ３３０も参照されたい。第５に、方法Ｃを使用
して、各命令に対する動的なストールサイクルの数と、
各ストールに対して考えられる原因をステップ６７０に
おいて識別する。動的なストールサイクルの数は、ｃｐ
ｉから最小（理想的）サイクル数（上記方法Ａの第２ス
テップ）を減算することにより決定できる。これが分か
ると、動的なストールに対して考えられる原因を求める
ことができる。

【００３８】実行頻度を推定する方法Ｂ 入力及び出力データ 図８に示すように、方法Ｂ（７００）に対して必要な入
力データは、次のものを含む。 １．プログラム７０１； ２．サンプルカウント７０２； ３．プログラムの制御流れグラフ（ＣＦＧ）７０３；及
び ４．サンプルを収集する間にプログラムが実行されたプ
ロセッサに対する命令スケジューラ又はモデル７０４。

【００３９】上記のＣＦＧにおいて、各ノードは、基本
的なブロックを表し、そして基本的なブロックは、当然
同じ回数だけ実行される命令のシーケンスである。グラ
フにおける各アークは、１つのブロックから別のブロッ
クへの考えられる実行流を表す。この方法は、たとえＣ
ＦＧがあるアークを欠落しても、ＣＦＧがおそらくアー
クを欠落しているとマークされる限り、機能する。ソー
ス、オブジェクト又は実行可能なコードからＣＦＧを構
成する方法は、不正確であるために、アークが欠落する
ことがある。

【００４０】命令スケジューラ７０４は、命令（ＩＮＳ
ＴＲＵＣＴＩＯＮ）のアレーを入力として取り上げ、そ
してそれら命令に対する理想的なスケジュール（ＳＨＥ
Ｄ）を出力として返送することができる。ＳＨＥＤは、
整数のアレーの形態をとることができる。このアレーに
おいて、アレーエレメントＳＨＥＤ（Ｉ）は、静的なス
トールのサイクル数が正確に分かり且つ動的なストール
が生じないと仮定される理想的なケースのもとで命令
（ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ））を発生するに必要と
されるサイクル数である。

【００４１】更に、命令スケジューラは、命令と命令と
の間の静的な依存性を識別しなければならない。ＩＮＳ
ＴＲＵＣＴＩＯＮ（Ｉ）は、ｊ＜Ｉの場合にＩＮＳＴＲ
ＵＣＴＩＯＮ（ｊ）に対して静的な依存性を有すると共
に、ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）は、ＩＮＳＴＲＵＣ
ＴＩＯＮ（ｊ）により使用されるプロセッサリソース又
はその命令により計算された値を常に必要とするので、
ＩＮＳＴＲＵＣＴＩＯＮ（ｊ）より早期にスケジュール
することができない。

【００４２】静的な依存性を識別するために、命令スケ
ジューラは、アレーＳＨＥＤに加えて、アレーＤＥＥＰ
も返送できる。アレーＤＥＥＰにおいては、アレーエレ
メントＤＥＥＰ（Ｉ）は、ＩＮＳＴＲＵＣＴＩＯＮ
（Ｉ）がＩＮＳＴＲＵＣＴＩＯＮ（ｊ）に対して依存性
を有するときに値ｊを有するか、又はＩＮＳＴＲＵＣＴ
ＩＯＮ（Ｉ）が依存性をもたないときに値０を有するか
のいずれかである。ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）が多
数の先行する命令に対して静的な依存性を有する場合に
は、ＤＥＥＰ（Ｉ）は、ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）
に最も近い先行する命令を表す値にセットされねばなら
ない。

【００４３】この方法は、次のような値の対を出力デー
タとして発生する。ＣＦＧ７０３の各ブロック及びアー
クに対し、頻度推定値は、（ＦＲＥＱＵＥＮＣＹ、ＣＯ
ＮＦＩＤＥＮＣＥ）の形態であり、負の数値ではないＦ
ＲＥＱＵＥＮＣＹは、頻度の推定値であり、そしてＣＯ
ＮＦＩＤＥＮＣＥは、推定値ＦＲＥＱＵＥＮＣＹがいか
に正確に予想されるかを示す値である。頻度推定値は、
サンプルを得るために使用されるサンプリング周期の単
位である。例えば、サンプリング周期が６５，５３６サ
イクル当たり１サンプルである場合には、頻度推定値１
００を有する基本的ブロックは、６，５５３，６００の
推定回数だけ実行されている。

【００４４】方法Ｂの概要 サンプルカウントは、ＣＦＧの部分に対する推定値を推
論するために使用される。これら推定値は、理想的な命
令スケジュールをベースとし、各々の「成功裡な実
行」、即ち命令が首尾良くリタイアされるために、発生
待ち行列のヘッドにおいて短いシーケンスの命令（しば
しば単一の命令）が費やさねばならない最小サイクル数
を識別する。第１に、おそらくは動的なストールを招か
ない短いシーケンスの命令を識別する。ＣＦＧにおける
幾つかの基本的ブロックは、このようなシーケンスをも
たないことがある。

【００４５】次いで、発生待ち行列のヘッドにおいて命
令が費やす最小サイクル数（「成功裡な実行」当たり）
でサンプルカウントの和を除算したものとして、動的な
ストールを伴わない命令シーケンスの実行頻度を推定す
る。動的なストールを招くことのある幾つかのシーケン
スについては、以下に述べる別の発見を使用して、それ
らの頻度を推定する。ＣＦＧの流れ制約を使用して、直
接推定できないブロック及びアークに推定値を伝播する
ことができる。先ず、ローカル伝播及び他の自然の発見
を利用して、ＣＦＧのほとんどの残り部分に対して推定
を行うことができる。次いで、各推定値に信頼値を指定
して、推定値の精度を指示する。最後に、ガウス排除(G
aussian Elimination)及び変形グラム−シュミット方法
に基づく制約ソルバー(solver)を使用し、初期推定値に
「最も密接な」流れ制約に対する解決策を見出す。

【００４６】通常は、初期推定値は、流れ制約に違反す
る。ここでは、信頼値を使用するようにグラム−シュミ
ット方法を変形し、即ち信頼性の高い推定値にあまり影
響を及ぼさない解決策は、信頼性の低い推定値に影響を
及ぼす解決策よりも「密接である」と考えられる。不当
に高い又は低い解決策の推定値、例えば、負の信頼値を
生じるような解決策の推定値は、これを修正する。

【００４７】方法Ｂの詳細な説明 ＣＦＧの各手順に対し、次のステップを実行する。ステップ１ ．頻度等価値の決定： ＣＦＧ７０３がアークを欠落しない限り、頻度等価アル
ゴリズムを使用して、ＣＦＧのブロック及びアークを、
メンバーが同じ「実行頻度」を有するセットに仕切る。
これらのセットは、「頻度等価クラス」（ＦＲＥＱ）７
１１又は簡単に「クラス」と称する。

【００４８】ＣＦＧ７０３がアークを欠落する場合に
は、各ブロック及び各アークごとに頻度等価クラスを形
成する。各ブロック又はアークは、厳密に１つの頻度等
価クラスに入ることに注意されたい。又、頻度等価クラ
スの基本的なブロックにおける各命令は、同じ回数だけ
実行されねばならないことにも注意されたい。定義によ
れば、Ｂが頻度等価クラスＣの基本的なブロックである
場合に、ブロックＢの各命令は、Ｃの頻度等価クラスを
有する。

【００４９】ステップ２．理想的スケジュール及び値ｍ
ｉｎ ｈｅａｄ ｑの決定： 各々の基本的なブロックごとに、モデル命令スケジュー
ラを使用して、ブロックにおける命令のシーケンスに対
し動的なストールを伴わない理想的なスケジュールであ
るアレーＳＣＨＥＤ７２１と、命令に対する静的な依存
性情報であるアレーＤＥＥＰ７２２の両方を決定する。
又、ブロックの各命令に対し値「ｍｉｎ ｈｅａｄ ｑ」
のアレーも決定する。ＳＨＥＤは、ブロックの各命令に
対し、動的なストールが生じない限り、第１の命令が直
ちに発生するという仮定に基づいて、命令を発生するに
必要なサイクルの数を与える。ＤＥＥＰは、ブロックの
各命令に対し、それが依存するところの最も密接な先行
する命令の数を与える。ｍｉｎ ｈｅａｄ ｑの値は、
発生待ち行列のヘッドにおいて命令が費やす最小（理想
的）サイクル数を表す。多数の先行項目をもつブロック
については、命令スケジューラへの入力が単にブロック
における命令のシーケンスとなる。

【００５０】ブロックＢが独特の一連の先行項目ブロッ
ク、例えば、Ｐ１、Ｐ２・・・Ｐｎを有していて、Ｐ１
がＢの唯一の先行項目であり、Ｐ２がＰ１の唯一の先行
項目であり、・・・そしてＰｎ−１がＰｎの唯一の先行
項目である場合には、命令スケジューラへの入力は、ブ
ロックの実行順序、即ちＰｎ、Ｐｎ−１・・・Ｐ２、Ｐ
１そしてＢにおけるブロックの命令の連鎖でなければな
らない。先行ブロックの命令を使用する目的は、特定の
ブロックが実行されるところのコンテクストに関するよ
り多くの情報を命令スケジューラに与えることにより命
令のより正確なスケジュールを得ることである。

【００５１】ブロックＰ１ないしＰｎにおける命令の全
数をＯＦＦＳＥＴとする。（ブロックが多数の先行項目
を有する場合には、ＯＦＦＳＥＴは０である。）次い
で、各命令Ｉに対し、理想的な命令スケジューリングの
もとで命令が発生待ち行列のヘッドにあると予想される
サイクル数を計算する。多数の先行項目をもつ基本的ブ
ロックにおける第１命令以外の全ての命令に対し、次の
ようにセットする。 ｍｉｎ ｈｅａｄ ｑ〔ｉ〕＝ｓｃｈｅｄ〔ｉ＋ｏｆｆ
ｓｅｔ〕−ｓｃｈｅｄ〔ｉ＋ｏｆｆｓｅｔ−１〕 多数の先行項目を有し、即ちｏｆｆｓｅｔ＝０である基
本的ブロックの第１命令即ちＩ＝０に対し、推定値ｍｉ
ｎ ｈｅａｄ ｑ

〔０〕＝１を使用する。

【００５２】多数の連続する命令が同じサイクルに発生
されるときには、第１命令のみが、ｍｉｎ ｈｅａｄ
ｑアレーに非ゼロ値を有することに注意されたい。これ
は、多発生命令のグループにおいて、発生待ち行列のヘ
ッドには第１の命令しか現れないからである。この第１
命令は、「発生ポイント」と称される。性能カウンタ
は、発生ポイントである命令の性能データしか収集でき
ない。発生待ち行列において更に深部に同時に発生され
る他の命令に対する性能データは、使用できないので、
例えば、実行頻度のような性能データを以下に述べるよ
うに推論しなければならない。

【００５３】ステップ３．幾つかのブロックに対する頻
度の推定： 頻度を推定するための基本的な戦略は、命令Ｉが動的な
ストールを伴わずに発生する場合に、サンプリングのエ
ラー及び以下に述べる他の問題を無視すると、その頻度
が次の式で表されるという一般的な言説に依存する。 頻度〔ｉ〕＝サンプル〔ｉ〕／ｍｉｎ ｈｅａｄ ｑ〔ｉ〕 式１ 但し、サンプル〔ｉ〕は、命令Ｉに対して同じカウント
である。ｍｉｎ ｈｅａｄ ｑ〔ｉ〕が０である場合に
は、命令Ｉの頻度は、この式を用いて直接決定すること
ができない。

【００５４】ある命令が動的なストールを招く場合、サ
ンプル〔ｉ〕／ｍｉｎ ｈｅａｄ ｑ〔ｉ〕の比は、頻度
より大きくなるだけである。というのは、サンプル
〔ｉ〕は増加するが、ｍｉｎ ｈｅａｄ ｑ〔ｉ〕は一
定に保たれるからである。頻度を推定するために好まし
い実施形態により使用される発見は、これら両方の言説
を利用する。特定の頻度等価クラスＣに充分に多数の命
令が与えられると、幾つかの命令が動的なストールをも
たないと仮定することが妥当となる。従って、セットに
おける幾つかの最小の比｛サンプル〔ｉ〕／ｍｉｎ ｈ
ｅａｄ ｑ〔ｉ〕｝を平均化することによりクラスＣに
おける命令の実行頻度を推定することができる。ここ
で、ＩＮＳＴＲＵＣＴＩＯＮ Ｉは、クラスＣにあり、
そしてＩは、発生ポイントであり、即ちｍｉｎ ｈｅａ
ｄ ｑ〔ｉ〕＞０である。

【００５５】式１が導き出す頻度値が小さ過ぎる状態が
幾つかある。第１に、基本的ブロックＢがＣＦＧに多数
の先行項目を有するときには、上記ステップ２で決定さ
れたｍｉｎ ｈｅａｄ ｑアレーは、不正確なものとな
る。例えば、制御が先行項目ブロックＰ１からブロック
Ｂに入るときは、Ｂの最初の命令が、Ｐ１の最後の命令
と共に二重発生されることがある。この場合に、ブロッ
クＢのｍｉｎ ｈｅａｄ ｑ

〔０〕は、０でなければな
らないが、ステップ２では、それが１にセットされる。

【００５６】式１が導き出す頻度値が小さ過ぎる別の状
態は、命令が「長い依存性」を有するときに生じる。Ｉ
ＮＳＴＲＵＣＴＩＯＮ Ｉは、理想的なスケジュールに
基づいてＩＮＳＴＲＵＣＴＩＯＮ Ｉを早期に発生でき
ない理由が、ＩＮＳＴＲＵＣＴＩＯＮ ｊにより使用さ
れたリソースをＩＮＳＴＲＵＣＴＩＯＮ Ｉが必要とす
るためであるときに、先行するＩＮＳＴＲＵＣＴＩＯＮ
ｊに対して依存性を有する。ＩＮＳＴＲＵＣＴＩＯＮ
ｊに対するＩＮＳＴＲＵＣＴＩＯＮ Ｉの依存性は、
Ｉ＞ｊ＋１の場合、即ちＩＮＳＴＲＵＣＴＩＯＮ ｊと
Ｉとの間に付加的な命令があるときに、「長い依存性」
となる。

【００５７】ＩＮＳＴＲＵＣＴＩＯＮ ｊとＩとの間の
命令が動的なストールを招き、即ち介在する命令が発生
待ち行列のヘッドにおいて予想以上の時間を費やすとき
に、問題が生じる。その結果、ＩＮＳＴＲＵＣＴＩＯＮ
Ｉは、発生待ち行列のヘッドにおいて予想以下の時間
を費やすことになり、サンプル〔ｉ〕は、予想より小さ
くなり、そして式１は、不正確な値を生じる。

【００５８】この問題に対して少なくとも２つの救済策
がある。その１つは、頻度を推定するときに長い依存性
を有する命令を無視することである。別の救済策は、Ｉ
ＮＳＴＲＵＣＴＩＯＮ ｊに対して長い依存性を有する
ＩＮＳＴＲＵＣＴＩＯＮ Ｉに対し、サンプル〔ｉ〕／
ｍｉｎ ｈｅａｄ ｑ〔ｉ〕の比を、（サンプル〔ｊ＋
１・・・Ｉ〕の和）／（ｍｉｎ ｈｅａｄ ｑ〔ｊ＋１
・・・Ｉ〕の和）に置き換えることである。

【００５９】推定方法の低レベルの細部の多くは、平均
化されるべき比をいかに選択するかを含む。高いレベル
においては、以下に実施される重要なポイントの幾つか
は、次のものを含む。等価クラスＣが発生ポイントにお
いて命令を含み、そして以下の方法Ｃに使用されるがご
とき分析により決定されるように、命令が決して動的な
ストールを招いてはならない場合には、これらの発生ポ
イントに対して決定された比を使用するのが最良であ
る。以下のサブステップ３．ｃ及び３．ｆを参照された
い。所与のプロセッサ構成の場合に、通常は、ストール
の時間長さに上限がある。この上限は、頻度についての
下限に換算することができる。以下のサブステップ３．
ｄを参照されたい。

【００６０】サンプリングエラーがない場合には、スト
ールサイクルを全く生じないか又は僅かに生じるだけで
ある多数の発生ポイントが、ほぼ同じ比をもつことにな
る。サンプリングエラーは、比に若干の変化を導入する
が、最大の比は、おそらく、最小の比の１．５倍以下で
ある。以下のサブステップ３．ｇを参照されたい。ある
クラスが、非常に多数の発生ポイントを有する場合に
は、それらの発生ポイントのある最小の一部分が、動的
なストールを伴わずに発生しなければならない。従っ
て、ある最小数の比を平均化して、推定値を計算しなけ
ればならない。この発生ポイントを以前の発生ポイント
と共に使用して、サンプル又は分析における何らかの異
常のために不当に低いか又は高い比を破棄することがで
きる。サブステップ３．ｇを参照されたい。

【００６１】ステップ３の詳細な説明 少なくとも１つの命令を含む各頻度等価クラスＣに対
し、図１０に示すように次のサブステップ３ａないし３
ｈを実行する。 ａ．クラスＣが少なくとも１つの発生ポイントを含み、
そして等価クラスＣの全ての命令がサンプルカウント０
を有するときには、ステップ８１０において、Ｃの頻度
を０と推定する。さもなくば、サブステップ３．ｂに進
む。 ｂ．クラスＣの命令に対する全サンプルカウントが、例
えば、Ｃにおける発生ポイントの全数の４倍というスレ
ッシュホールドより小さいときには、ステップ８２０に
おいて、クラスＣに対し推定を行わない。 ｃ．ステップ８３０において、推定値の下限であるｆｒ
ｅｑ ｌｏｗｅｒ ｂｏｕｎｄを、クラスＣにおける命
令の最大サンプルカウントをプログラムを実行した特定
のハードウェアに対して考えられる最大ストールサイク
ルで除算したものにセットする。例えば、特定のプロセ
ッサ実施形態では、ストールが２５６サイクルより決し
て長くならないことがある。ｆｒｅｑ ｌｏｗｅｒ ｂ
ｏｕｎｄが１より小さい場合には、それを１にセットす
る。ｆｒｅｑ ｌｏｗｅｒ ｂｏｕｎｄは、例えば、サ
ンプリングされた性能データの異常のために不当に低い
比を破棄するのに使用される。

【００６２】ｄ．命令は、例えば、方法Ｃの技術を使用
することにより動的なストールの全ての共通の原因を排
除できるときにはストール不能となる。ステップ８４０
において、アレーＵｎｓｔａｌｌａｂｌｅＲａｔｉｏｓ
（ＲＡＴＩＯＳ）への次の比を計算する。即ち、ＤＥＰ
（Ｉ）＝０であるクラスＣの各発生ポイントに対し、Ｉ
がストール不能である場合には、 サンプル〔ｉ〕／ｍｉｎ ｈｅａｄ ｑ〔ｉ〕 である。ＤＥＰ（Ｉ）＝０でないクラスＣの各発生ポイ
ントに対し、ＤＥＰ（Ｉ）＋１ないしＩがストール不能
である場合には、 （サンプル〔ＤＥＰ（Ｉ）＋１・・・Ｉ〕の和）／（ｍ
ｉｎ ｈｅａｄ ｑ〔ｄｅｐ〔ｉ〕＋１・・・Ｉ〕の
和） である。アレーＲＡＴＩＯＳが空でない場合には、クラ
スＣの頻度をアレーＲＡＴＩＯＳにおける比の平均値と
して推定する。但し、これは、平均値が少なくともｆｒ
ｅｑ ｌｏｗｅｒ ｂｏｕｎｄと同じ大きさの場合であ
る。さもなくば、サブステップ３．ｅへ進む。

【００６３】ｅ．ＤＥＰ（Ｉ）＝０であるクラスＣのメ
ンバーの各発生ポイントに対し、 サンプル〔ｉ〕／ｍｉｎ ｈｅａｄ ｑ〔ｉ〕 である。ＤＥＰ（Ｉ）＝０でないクラスＣの各発生ポイ
ントに対し、 （サンプル〔ＤＥＰ（Ｉ）＋１・・・Ｉ〕の和）／（ｍ
ｉｎ ｈｅａｄ ｑ〔ＤＥＰ〔Ｉ〕＋１・・・Ｉ〕の
和） である。 ｆ．ｆｒｅｑ ｌｏｗｅｒ ｂｏｕｎｄより小さいＲＡ
ＴＩＯＳのエレメントは破棄する（ステップ８６０）。
他のエレメントがない場合には、クラスＣに対する推定
は行わない。 ｇ．ｆｒｅｑ ｕｐｐｅｒ ｂｏｕｎｄより大きいＲＡ
ＴＩＯＳのエレメントは破棄する（ステップ８７０）。
好ましい実施形態においては、ｆｒｅｑ ｕｐｐｅｒ
ｂｏｕｎｄは、次のように決定される。即ち、ＲＡＴＩ
ＯＳにおける最小のエレメントをｘとすると、ｘ＜１５
の場合には、次のようになる。 ｆｒｅｑ ｕｐｐｅｒ ｂｏｕｎｄ＝ＭＩＮ（２０、２
＊ｘ） さもなくば、ｆｒｅｑ ｕｐｐｅｒ ｂｏｕｎｄ＝１．
５＊ｘ

【００６４】ここでの目的は、クラスＣの発生ポイント
に対する頻度の適度に大きなサブセットを、クラスＣの
実行頻度を推定するように平均化するための考えられる
候補として識別することである。アレーＲＡＴＩＯＳの
長さが、クラスＣの発生ポイントの数の１／８以下であ
る場合には、アレーＲＡＴＩＯＳにおける頻度値は、サ
ンプリングエラー又は他の問題により異常に低くなるこ
とが考えられる。ｆｒｅｑ ｌｏｗｅｒ ｂｏｕｎｄを
ｓｑｒｔ（２）＊ｘにセットし、そしてサブステップ
３．ｅに戻ることにより、大きな値について検討する。
しかしながら、これが、クラスＣに対してサブステップ
３．ｇを実行する３回目である場合には、クラスＣに対
して推定は行わない。

【００６５】ｈ．ステップ８８０において頻度をＮ個の
最も小さい比の平均値として推定する。高いレベルにお
いては、解決される問題は、平均値に含むべき最も小さ
い比の数であるＮを選択することである。Ｎを小さくす
ることと、Ｎを大きくすることの間にはテンションがあ
る。Ｎが小さい場合には、統計学的なサンプリングエラ
ー又はある異常により、低いサンプルカウントを有する
発生ポイントの比のみを平均化する機会が増加する。Ｎ
が大きい場合には、動的なストールが存在する発生ポイ
ントの比を含む機会が増加し、推定値を非常に大きなも
のにする。例えば、１つの実施形態は、Ｎを次のように
選択する。 Ｎ＝ＭＩＮ（ｌｅｎｇｔｈ（ＲＡＴＩＯＳ）、 ＭＡＸ（３、 発生ポイントの数／４、 最小の比のせいぜい１．１倍である比の数））

【００６６】ステップ４．推定値のローカル伝播の実
行： この点において、頻度等価クラスのあるものだけが頻度
推定値を有する。ローカル伝播は、「流入＝流出」制約
を用いて、既存の推定値から付加的なクラスに対する頻
度推定値を決定する（ステップ７４０）。制約は、実行
流が等価クラスに入る全回数が、実行流がそのクラスか
ら出る全回数に等しくなければならないことを利用す
る。例えば、１つの入力アークと、３つの出力アークを
もつ基本的ブロックＢを伴うＣＦＧ部分を考え、入力ア
ークの頻度が２００で、そして３つの出力アークの頻度
が、左から右へ、未知、２５及び１００であると仮定す
る。

【００６７】制約「流入＝流出」を使用して、部分Ｂの
頻度を２００と決定することができる。次いで、最も左
の既存のアークの頻度は、７５、即ち（２００−（２５
＋１００））と計算することができる。多数（Ｎ）の到
来するアークをもつブロックがあり、即ちＮがゼロ０よ
り大きく、そしてＮ個のアークのクラス及びブロックの
クラスの１つ以外の全ての頻度に対して推定値があると
きには、単一の伝播が可能である。伝播は、次の式を解
くことにより行われる。即ち、単一の未知の頻度に対
し、 freq(class(block)) = sum[i=1,N] of freq(class(incoming arc I)) 式２ 未知の頻度の解が負の場合には、その解は使用しない。

【００６８】同様に、Ｎ個の出て行くアークをもつブロ
ックがあり、即ちＮがゼロより大きく、そしてＮ個のア
ークのクラス及びブロックのクラスの１つ以外の全ての
頻度に対して推定値があるときには、単一の伝播が可能
である。伝播は、次の式を解くことにより行われる。即
ち、単一の未知の頻度に対し、 freq(class(block)) = sum[i=1,N] of freq(class(outgoing arc I)) 式３ 未知の頻度の解が負の場合には、その解は使用しない。
制約Ｎ＞０は、式２及び３に対しＣＦＧ７０３の入口及
び出口ブロックを取り扱うことに注意されたい。ローカ
ル伝播を行うために、負の頻度を導入するもの以外、単
一の伝播がそれ以上考えられなくなるまでは、単一の伝
播を単に実行する。

【００６９】ステップ５．若干のサンプルをもつクラス
の推定の実行： この点において、推定値をもたないクラスがまだ若干存
在する。というのは、それらが若干のサンプル又は発生
ポイントを含むからである。ステップ５（７５０）は、
このようなクラスに対し自然のままの推定を行う。少な
くとも１つの発生ポイントを含むが、頻度推定値に欠け
るクラスＣに対して、クラスＣの頻度を推定する。クラ
スＣにおける命令のサンプルの和を、ＭＡＸ（１、Ｃに
対するｍｉｎ ｈｅａｄ ｑアレーの和）で除算する。ステップ６ ．ローカル伝播の繰り返し： ステップ７６０では、ローカル伝播が付加的な推定値と
共に繰り返される。

【００７０】ステップ７．残りの流れを用いた推定の実
行： この点において、幾つかのアークが、依然として、推定
値をもたないクラスにある。頻度２００の１つの到来す
るアークと、未知の頻度の２つの出て行くアークと、既
知の頻度１００の１つの出て行くアークとをもつ単一の
基本的ブロックＢを伴うＣＦＧ部分Ｂについて考える。
ここでは、ローカル伝播は不可能である。というのは、
推定値をもたない２つ以上の出て行くアークがあるから
である。出て行くアークに対する自然のままの推定は、
残りの流れ（２００−１００）を、推定値をもたない出
て行くアークの数で除算することである。

【００７１】ステップ７７０は、推定値をもたないクラ
スにおいて全てのアークを考えることによりこのような
推定を行う。各アークの両エンドポイントを検査するこ
とによりこれを行う。更に、残りの流れが負である（こ
れは、推定値が不正確であるために起こり得る）ときに
はエンドポイントを無視する。アークＡがブロックＢに
接続されたｓｉｂｌｉｎｇ ａｒｃｓ（アークＡ、ブロ
ックＢ）を、アークＡが接続されたのと同じ側でブロッ
クＢに接続されたアークＡ’（Ａ以外）のセットして定
義する。例えば、アークＡがブロックＢに入る場合に
は、ｓｉｂｌｉｎｇ ａｒｃｓ（Ａ、Ｂ）は、ブロック
Ｂに入るＡ以外のアークのセットである。

【００７２】次いで、ブロックＢに接続されたアークＡ
に対する残りの流れは、ｓｉｂｌｉｎｇ ａｒｃｓ
（Ａ、Ｂ）にあって且つ頻度推定値ｆｒｅｑ（クラス
（Ａ’））を、（頻度推定値＋１をもたないｓｉｂｌｉ
ｎｇ ａｒｃｓ（Ａ、Ｂ）内のアークの数）で除算した
ものを有するアークＡ’に対し、 ｆｒｅｑ（ｃｌａｓｓ（Ｂ））−ｓｕｍ ｆｒｅｑ（ｃ
ｌａｓｓ（Ａ’）） となる。推定値をもたずそして少なくとも１つのアーク
を含まない各クラスＣに対し、先ず、次の初期指定を行
う。 Ｎ：＝０、及び 流れ：＝０ 次いで、クラスＣの各アークＡと、Ａの各エンドポイン
トＢ、即ちＡのソース又はターゲットブロックにおける
Ｂとに対し、推定値ｆｒｅｑ（クラス（ｂ））及びｒｅ
ｓｉｄｕａｌ ｆｌｏｗ（ｂ、Ａ）≧０の場合には、 流れ：＝流れ＋ｒｅｓｉｄｕａｌ ｆｌｏｗ（Ｂ、
Ａ）、及び Ｎ：＝Ｎ＋１ となる。最後に、Ｎ＞０の場合には、Ｃの頻度を（流れ
／Ｎ）と推定する。

【００７３】ステップ８．推定値への信頼値の指定： 推定値の幾つかは、他のものよりも精度が高くなり勝ち
である。例えば、サブステップ３で形成されたほとんど
の推定値は、おそらく、エラーを蓄積することのあるロ
ーカル伝播により形成される推定値、又は若干のサンプ
ル又は若干の発生ポイントをもつブロックに対して自然
のままの推定を行うステップ５で形成された推定値、或
いは残りの流れを用いてアークに対して自然のままの推
定を行うステップ７で形成された推定値よりも精度が高
い。更に、ステップ３で作られる推定値の場合には、精
度が次のものに相関する。 １）平均値に寄与する多数の発生ポイントを有する（サ
ブステップ３．ｈ）。及び ２）平均値に寄与する多数の発生ポイントの比に小さな
変化しかもたない。 従って、ステップ７８０において「信頼値」を指定する
ことにより推定値の精度を確立することができる。好ま
しい実施形態は、３つの信頼値、即ち低、中間及び高の
信頼値を有する。

【００７４】高信頼性の推定値は、次の通りである。 ａ）同じ基本的ブロックに少なくとも２つの発生ポイン
トをもつクラスに対してステップ３．ａで形成された推
定値； ｂ）ステップ３．ｄで形成された推定値；及び ｃ）少なくとも３つの比（Ｎ≧３）（但し、最大の比
は、最小の比の１．２倍以上）を平均化することにより
ステップ３．ｈで形成された推定値≧１００。 しかしながら、ステップ３．ｇが推定に対して２回以上
行われた場合には、推定値の信頼性が低い。

【００７５】中程度の信頼性の推定値は、次の通りであ
る。 ａ）２つの発生ポイントをもつクラスに対してステップ
３．ａで形成された推定値； ｂ）ステップ３で形成された推定値≧１００。しかしな
がら、ステップ３．ｇが推定に対して２回以上行われた
場合には、推定値の信頼性が低い；及び ｃ）完全なＣＦＳ（即ちアークの欠落がない）に対して
ステップ４（ローカル伝播）で形成された推定値≧１０
０。しかしながら、ステップ３．ｇが、「流入＝流出」
方程式に使用される推定に対して２回以上行われた場合
には、推定値の信頼性が低い。 低信頼性の推定値は、残りの推定値である。

【００７６】ステップ９．（グローバルな）制約ソルバ
ーの使用： この点において、頻度等価クラスのほとんどに対し推定
値及び信頼値が存在する。しかしながら、推定値は、流
れ制約に違反することがある。図８のステップ７９０
は、推定値が適度な限界を越えない限り、例えば、負の
推定値が許されることがない限り、制約ソルバーを使用
して、制約を満足するように推定値を修正する。制約ソ
ルバーの重要な特性は、次の通りである。 （１）ソルバーは、一次方程式の過少制約系を取り扱わ
ねばならず、これらはＡｘ＝ｂと表すことができる。但
し、Ａは、制約のマトリクスであり、そしてｘ及びｂ
は、ベクトルである。 （２）変数の初期推定値のベクトルｘと、変数の重みの
ベクトルｗとが与えられると、ソルバーは、ベクトルｘ
−ｘ’の重み付けされた大きさを最小にする解ベクトル
ｘ’を見出す。重みのベクトルｗに対するベクトルｖの
重み付けされた大きさは、次の通りである。 ｓｑｒｔ（ｓｕｍ〔ｉ＝１、ｎ〕（ｗ（Ｉ）＊（ｖ
（Ｉ）² ））

【００７７】図８に示すように、ガウスの排除及びグラ
ム−シュミット正規直交化のような標準的な線型代数技
術を使用してこのようなソルバーを簡単に構成すること
ができる。 ａ）ステップ７９１において流れ制約をもつマトリクス
Ａを設定する。推定値を有する各頻度等価クラスごとに
マトリクスＡの１つの列を使用する。各流れ制約ごとに
１つの行を使用する。流れ制約は、ステップ４の式２及
び式３をＣＦＧのブロックに適用することにより得られ
る。しかしながら、流れ制約は、これが推定値をもたな
い頻度等価クラスを指すときには破棄され、或いは流れ
制約は、式２又は式３の全ての変数が同じ頻度等価クラ
スにあるときには全て０の行を形成する。

【００７８】流れ制約は、独特の１組の頻度値を決定す
るには不充分であるから、マトリクスＡは、一次方程式
の過少制約系となる。 ｂ）ステップ７９２において頻度推定値でベクトルｘを
初期化する。ｘ〔ｉ〕は、頻度等価クラスに対する推定
値である。 ｃ）ステップ７９３において頻度クラスＩに対する重み
ベクトルｗ〔ｉ〕を、頻度クラスＩにおけるブロック及
びアークの数に推定値ｘ〔ｉ〕のｃｏｎｆｉｄｅｎｃｅ
ｗｅｉｇｈｔを乗算したものを、ｘ〔ｉ〕＝０の場合
は１で除算し、さもなくば、ｘ〔ｉ〕で除算したものに
等しくなるように初期化する。但し、ｘ及びｗは、長さ
が等しい。

【００７９】これらの重みは、流れ制約に違反する推定
値の相対的な変化を制御するために次のステップに使用
される。例えば、制約マトリクスＡが、２つの推定値の
みを等しくすべきであることを示す場合には、推定値ｘ
〔１〕が次の量だけ増加される。 （ｗ〔１〕／（ｗ〔１〕＋ｗ〔２〕））ｘ（ｘ〔２〕−
ｘ〔１〕） 高い信頼性の推定値の重みは、低い信頼性の推定値より
も大きくなければならない。好ましい実施形態は、変数
ｃｏｎｆｉｄｅｎｃｅ ｗｅｉｇｈｔを次の値にセット
する。 信頼性の低い推定値の場合は１； 中程度の信頼性の場合は１００；そして 信頼性の高い推定値の場合は１００００。

【００８０】又、推定値の重みは、それらの大きさに逆
比例しなければならない。従って、同じ信頼値をもつ競
合する推定値は、各々、同じ割合だけ調整される。例え
ば、頻度が２つの到来するアークについて１０及び１で
ありそして出て行くアークについて１０であって、各推
定値が同じ信頼値を有するような基本的ブロックを有す
る流れグラフについて考える。重みが全て等しい場合に
は、制約ソルバーは、各々、値９．６７、０．６７及び
１０．３４を指定する。この解決策において、右のアー
クに対する推定値が３３％だけ変更される。

【００８１】重みが正規化されるときには、この解決策
は、各々、９．５２、０．９５及び１０．４７を形成す
る。従って、推定値の各々は、その元の値のほぼ５％変
更される。 ｄ）ステップ７９４において、制約ソルバーを使用し、
重みについて元の推定値に最も密接な解を見つける。 ｅ）ステップ７９５において、下限より小さい解をその
下限にリセットする。推定値の下限は、ステップ３．ｇ
ではｆｒｅｑ ｌｏｗｅｒ ｂｏｕｎｄであり或いはス
テップ３で推定値が形成されない場合には０である。 ｆ）ステップ７９６において、元の値から１０％以上変
化した推定値に対する信頼値を「低い信頼性」にリセッ
トする。

【００８２】方法Ｃ：ストールサイクルの説明 図１１ないし１４を参照して、方法Ｃを以下に説明す
る。全体的な解決策 各命令ごとにストールサイクルの平均数が決定される
と、次のステップは、ストールに対して考えられる説明
を推論することである。これは、システム設計者が性能
問題の原因を理解すると共に、適当な解決策を案出する
上で助けとなる。

【００８３】性能カウンタは、動的なストールを生じる
ことのある事象、例えば、データキャッシュミスの発生
をサンプリングするのに使用できる。しかしながら、ほ
とんどのシステムにおいては、このような性能カウンタ
は、どの命令が所与の事象を生じさせたかを正確に識別
しない。方法Ｃは、方法Ｂで計算された実行頻度及び命
令当たりのサイクルの情報を、手順に対する制御流れグ
ラフと共に使用して、各動的なストールに対する理由を
決定する。

【００８４】図１１は、ストールサイクルに対する考え
られる説明を見出すための全体的な解決策を示す。ステ
ップ９１１において、各基本的なブロックの命令は、プ
ロセッサパイプラインの詳細なモデルを用いてスケジュ
ールされる。パイプラインのオペレーションの記録は、
各命令がストールされたサイクル数（９２０）、なぜ命
令がストールされたかの理由、及びもし適当であれば、
そのストールを生じさせた「カルプリット（罪人）」と
称する手前の命令（９１２）とを生じる。例えば、スト
ールされた命令は、カルプリット命令により計算された
結果を必要とする。

【００８５】ステップ９３１において、既知の静的なス
トールサイクル（９２０）が上記のように決定された全
ストールサイクル（９３０）から減算されて、各命令ご
とに動的なストールサイクル（９４０）を形成する。動
的なストールサイクルとは、プロセッサパイプラインに
より課せられる制約では説明できないストールサイクル
である。

【００８６】ステップ９５１において、命令シーケンス
及び個々の命令の特性、制御流れグラフ、及び上記のよ
うに得られた頻度推定値を含む（これらに限定されな
い）全ての使用可能な情報（９５０）を分析することに
より、動的なストールサイクルのための考えられる説明
が識別される。この分析は、動的なストールのための考
えられる理由、及びもし適当であれば、カルプリット
（全体的に９５２）を形成する。

【００８７】特定の命令により被った動的なストールの
考えられる説明を見出すために（ステップ９５１）、命
令が一般にストールを生じるようにさせる全ての既知の
理由が考慮される。これら理由の幾つかは、特定の場合
には、除外（又は排除）することができる。この排除プ
ロセスを以下に詳細に説明する。以下に述べる分析技術
に加えて、種々の種類の事象をカウントするハードウェ
ア性能カウンタを用いて、動的ストールの理由を識別す
ることもできる。Ｉキャッシュミスのような事象に対
し、各命令ごとにこれら事象の頻度を識別するサンプル
を得ることができる。

【００８８】この情報は、命令について観察された動的
なストールに対する各考えられる理由の寄与を決定する
のに使用できる。所与の事象についてのサンプルは、各
命令ごとに、その命令に対して事象が生じた回数の適当
なカウントを与えねばならない。ある種の事象について
は、これは、方法Ｄにおいて以下に述べる形態のハード
ウェアサポートを必要とする。

【００８９】一般に、除外できない理由は、特定のスト
ールに対する考えられる説明として与えられる。排除
は、各動的なストールに対し独特の説明を常には生じな
いが、しばしばそのようにすることができる。実際に、
命令は、多数の理由で同時に又は異なる時期にストール
されることがある。たとえ独特の理由を与えることがで
きなくても、全ての考えられる理由を与えることは、ユ
ーザがその可能性を絞り込む上で助けとなろう。動的な
ストールの幾つかの共通の原因を適当な条件のもとでい
かに除外できるかについて以下に説明する。

【００９０】Ｉキャッシュ又はＩＴＢミスの除外 動的なストールは、命令キャッシュ（Ｉキャッシュ）が
命令をフェッチするためにアクセスされたが、必要な命
令がＩキャッシュにないときに生じる。これをＩキャッ
シュミスと称する。この場合に、命令は、待ち時間の長
いメモリからフェッチしなければならない。同様に、動
的なストールは、命令変換のルックアサイドバッファ
（ＩＴＢ）が命令の仮想メモリアドレスを物理的なメモ
リアドレスに変換するためにアクセスされたが、必要な
変換エントリーがＩＴＢにない（ＩＴＢミスと称する）
ときに生じる。この場合には、命令フェッチを続ける前
に必要なエントリーでＩＴＢを更新しなければならな
い。ストールされる命令の直前にフェッチされて実行さ
れる命令のアドレスによりある条件が満足される場合
に、Ｉキャッシュ又はＩＴＢミスを除外することができ
る。

【００９１】図１２は、Ｉキャッシュミスについて考え
るケースを示す。（ＩＴＢミスは、以下に述べる。）３
つの基本的なブロック１０３１、１０３２、１０３３が
図示されている。ブロック１０３１及び１０３２は、ブ
ロック１０３３をコールし、アーク１０３３−１０３４
は、制御流れグラフに表されたようにそれらの間に流れ
る。又、命令１０１１−１３がブロック１０のライン１
０２１−１０２４にいかにマップされ、そして基本的ブ
ロック１０３３の命令がメモリにいかにレイアウトされ
るかも図示されている。図１２において、命令１０１１
−１０１３は、斜線で示されており、そしてこれらライ
ン間の分離は、破線で示されている。

【００９２】命令１０１１、１０１２、１０１３により
示されたように、多数のケースについて考慮する。スト
ールされた命令が基本的ブロックの始めに存在しない場
合には、２つのサブケースがある。その命令、例えば、
１０１２がキャッシュラインの始めにある（換言すれ
ば、命令のアドレスがキャッシュラインサイズの整数倍
である）場合には、Ｉキャッシュミスを除外することが
できない。というのは、命令が別のキャッシュラインに
おいてその直前で実行されるからである。ストールされ
た命令（例えば、１０１３）がキャッシュラインの始め
に存在しない場合には、Ｉキャッシュミスを除外するこ
とができる。

【００９３】最終的に、命令、例えば１０１１が、基本
的ブロックの始めに存在する場合には、それがキャッシ
ュラインの始めにも存在するかどうかに関わりなく、以
下先行項目ブロックと称する全ての基本的ブロック、例
えば、１０３１、１０３２の最後の命令が検査される
（先行項目ブロックから、制御は、ストールされた命令
を含む基本的ブロック、例えば、１０３３へ流れる）。
これらの命令が、全て、ストールされた命令、例えば１
０１１と同じキャッシュラインにある場合には、Ｉキャ
ッシュミスを除外することができる。命令は、それらの
アドレスが、キャッシュラインサイズで除算したときに
同じ商を生じる場合には、同じキャッシュラインに存在
する。この分析は、以前に得られた頻度推定値に基づ
き、ストールされた命令を含む基本的ブロックよりも相
当に低い頻度で実行される先行項目ブロックを無視す
る。

【００９４】この分析が、データ及び命令の両方に対し
て単一のキャッシュしかもたないプロセッサ又はコンピ
ュータシステムに適用される場合には、１つの付加的な
チェックを行わねばならない。ストールされた命令がメ
モリをアクセスする直前にいずれか１つの命令が実行さ
れる場合には、Ｉキャッシュミスを除外することができ
ない。これは、メモリアクセスが、ストールされた命令
を含むキャッシュラインを変位して、アクセスされてい
るデータのための余地を作るからである。

【００９５】上記分析は、命令の実行が、制御流れグラ
フにより指示される順序を常にたどることを仮定する。
割り込みは、この仮定に違反させることがある。しかし
ながら、割り込みは、あまり頻繁に生じることがなくそ
して命令ストリームにおいてランダムなポイントで生じ
るので、この仮定は、統計学的な意味では合理的に保持
される。更に、例外も、この仮定に違反する。

【００９６】或いは又、Ｉキャッシュミスの影響は、Ｉ
キャッシュミス事象についてプログラムカウンタを統計
学的にサンプリングすることにより評価することができ
る。この方法は、時間経過に伴い、Ｉキャッシュミスの
ために各命令がいかに頻繁にストールされるかの正確な
推定値を形成することができる。この推定値から、Ｉキ
ャッシュミスに起因し得るストールサイクル（この命令
により被る）の数についての上限が計算される。より詳
細には、上限は、次のものの積である。 （ａ）この命令に対して観察されるＩキャッシュミス事
象の数； （ｂ）Ｉキャッシュミスに対するサンプリング周期（こ
の多数のＩキャッシュミスのうちの各１つがサンプリン
グされる）；及び （ｃ）Ｉキャッシュミスの最大ペナルティ（通常は、メ
インメモリのアクセス待ち時間）。

【００９７】その結果は、ストールされた命令が実行さ
れる推定回数で除算され、平均値が得られる。この平均
値が小さい（例えば、サイクルの半分未満）場合には、
Ｉキャッシュミスを、ストールについて考えられる説明
として除外できる。さもなくば、理由がユーザに情報と
して与えられる。ＩＴＢミスの分析も同様であるが、前
記説明の「キャッシュライン」を「仮想メモリページ」
として解釈しなければならない。

【００９８】Ｄキャッシュ又はＤＴＢミスの除外 又、動的なストールは、データキャッシュ（Ｄキャッシ
ュ）がロード命令でアクセスされるが、必要なデータが
Ｄキャッシュに存在しないときにも生じる。これは、Ｄ
キャッシュミスと称する。同様に、動的なストールは、
データ変換ルックアサイドバッファ（ＤＴＢ）がデータ
の仮想メモリアドレスを物理的なメモリアドレスに変換
するためにアクセスされたが、必要な変換エントリーが
ＤＴＢに存在しない（ＤＴＢミスと称する）ときにも生
じる。

【００９９】異なるプロセッサ実施形態は、Ｄキャッシ
ュミス又はＤＴＢミスが生じたときには異なる振る舞い
をする。ある実施形態では、ロード命令自体がストール
される。この場合に、Ｄキャッシュミス又はＤＴＢミス
は、ストールされた命令がロード命令でない場合に除外
することができる。他の実施形態では、ロードは遅延を
伴わずに発生されるが、ロードの結果を使用する命令
は、その結果が実際に使用できるようになるまでストー
ルされる。この場合には、命令ストリームにおいてレジ
スタが読み取られそして書き込まれる順序を分析しなけ
ればならない。

【０１００】Ｄキャッシュミス又はＤＴＢミスは、命令
ストリームにおいてレジスタが読み取られそして書き込
まれる順序及び仕方によってある条件が満足される場合
には除外することができる。ストールされた命令がＤキ
ャッシュミス又はＤＴＢミスによりストールされたかど
うかを決定するために、それが参照する各レジスタが考
慮される。図１４は、データミスによるストールを除外
するために実行することのできる分析を示す。図１４に
おいては、ブロック１２０１からブロック１２０２又は
ブロック１２０３へ実行が行われ、ブロック１２０４
は、ブロック１２０２又は１２０３が実行された後に実
行される。命令１２１３は、例えば、レジスタｔ０によ
る参照を分析するに必要なデータが直ちに得られないこ
とによりストールされる。

【０１０１】レジスタｔ０については、ストールされた
命令１２１３のレジスタｔ０を最後に参照した命令１２
１１−１２１２が、以下に詳細に述べる仕方で識別され
る。このような命令がメモリからレジスタｔ０へデータ
をロードする場合には、Ｄキャッシュミス又はＤＴＢミ
スがストールのための考えられる説明とみなされ、その
命令は、カルプリットとして識別される。これは、スト
ールされた命令により参照された各レジスタに適用され
る。これらレジスタのいずれもカルプリットを生じない
場合には、Ｄキャッシュミス又はＤＴＢミスがストール
のための考えられる説明として除外される。図１４にお
いて、例えば、Ｄキャッシュミス又はＤＴＢミスは、ロ
ード命令１２１２で、カルプリットと考えられる。

【０１０２】この分析で考慮すべき全ての命令を見出す
ために、同じブロック内のストールされた命令より前の
命令が、最初に、それらのアドレスの下降順で検査され
る。それらのいずれもレジスタを参照しない場合には、
制御がそのストールされた命令へと流れるところの基本
的ブロックの命令も検査される（これも所与の基本的ブ
ロックにおける命令のアドレスの下降順に）が、そのス
トールされた命令を含むものより著しく低い頻度で実行
される基本的ブロックは、無視することができる。スト
ールされた命令の頻度推定値の小さな割合としてスレッ
シュホールドを計算することができ、そして頻度推定値
がこのスレッシュホールドより低い基本的ブロックを無
視することができる。

【０１０３】基本的ブロックのこの検討は、例えば、ス
トールされた命令を含む基本的ブロックから始めて逆の
制御流れグラフ（元のグラフにおける全ての制御流れア
ークの方向を逆転することによって形成された）におい
て深さ優先探索を行うことにより実行できる。これにつ
いては、ホプクロフト氏等の「グラフ操作のための効率
的なアルゴリズム(Efficient Algorithms for Graph Ma
niplation)」、コミュニケーションズ・オブ・ザ・ＡＣ
Ｍ、１６（６）：３７２−３７８、１９７３年を参照さ
れたい。この探索において、基本的なブロックに隣接す
るものは、その基本的ブロック自体が当該レジスタを参
照する命令を含む場合には、調べられる必要がない。

【０１０４】好ましい実施形態は、データ及び命令が個
別のキャッシュ及び個別の変換ルックアサイドバッファ
を有するコンピュータシステムを参照して説明したが、
Ｉキャッシュ、ＩＴＢ、Ｄキャッシュ及びＤＴＢミスを
除外するための方法は、データ及び命令が単一のキャッ
シュを共用するか、又はデータ及び命令が単一の変換ル
ックアサイドバッファを共用するか、或いはその両方で
あるようなプロセッサ及びコンピュータシステムにも適
用できる。

【０１０５】しかしながら、データ及び命令が単一のキ
ャッシュ又は変換ルックアサイドバッファを共用する場
合には、Ｄキャッシュ又はＤＴＢミスに対して付加的な
理由を考慮しなければならない。例えば、メモリ位置Ａ
に１つの命令がロードされ、同じ基本的ブロックにおけ
るその後の命令がその命令自体にキャッシュミスを招き
そしてキャッシュから位置Ａのデータを変位し、次い
で、同じ基本的ブロックに依然として存在するその後の
命令がＡにロードしようと試み、Ａの第２のロードがキ
ャッシュにおいてミスとなると仮定する。Ｉキャッシュ
ミスに関する情報を用いて、このような状態を除外する
ことができる。

【０１０６】分岐予想ミスの除外 又、動的なストールは、分岐命令の実際のターゲットが
プロセッサの分岐予想ロジックにより予想されるターゲ
ットと相違するときにも生じる。これは、分岐予想ミス
と称する。ここでは、「分岐命令」は、プログラムの制
御流を変更し得る命令を意味し、即ちそれらは、一般に
「分岐」と称される命令を含むだけでなく、「ジャン
プ」、サブルーチンコール、及び復帰命令等も含む。

【０１０７】いかに多くの分岐予想ミスがストールに寄
与するかは、制御が以下に述べるようにストールされた
命令に到達するときに生じ得る分岐予想ミスの頻度につ
いての上限を計算することにより推定できる。分岐予想
ミスは、その寄与がある適当なスレッシュホールドより
低い場合にはストールのための考えられる説明として除
外することができ、或いは又、その寄与は、それがいか
に小さくてもユーザに与えることができる。基本的ブロ
ックの始めにストールされた命令をいかに取り扱うかに
ついて以下に説明する。ストールされた命令が基本的ブ
ロックの第１の命令でない場合は、分岐予想ミスをスト
ールの考えられる説明として直ちに除外することができ
る。それ以上の分析は、必要とされない。

【０１０８】ストールされた命令の直前の分岐予想ミス
の頻度の上限を見出すために、その命令の直前に実行さ
れる全ての基本的ブロックが、図１３に示すように検討
される。この説明上、これらの基本的ブロックは、先行
項目ブロック（例えば、１１０１、１１０２、１１０
３、１１０４）と称され；これら先行項目ブロックから
ストールされた命令（ｓｕｂｑ）を含む基本的ブロック
への制御流れアークは、先行項目アーク（例えば、１１
１１、１１１２、１１１３、１１１５）と称され；そし
て先行項目ブロックの最後の命令は、先行項目命令（例
えば、ａｄｄｑ、ｂｒ、ｊｍｐ及びｂｅｑ命令）と称さ
れる。例えば、全ての先行項目ブロックが未知である場
合には、基本的ブロックは、未知のコールされたサブル
ーチンからの「戻り」命令のターゲットであり、従っ
て、未知の先行項目は、悲観的に、常に予想ミスである
と仮定することができる。

【０１０９】ストールされた命令について計算されるべ
き限界１１２２は、各先行項目命令に１つづつある個々
の限界の和である。ここの限界は、ボックス１１２１と
して示されている。４つの形式の先行項目命令がある。
最初の４つが図１３に示されている。即ち （１）基本的ブロック１１０１におけるａｄｄｑ命令の
ような非分岐命令。個々の限界は、ゼロにセットされ、
予想を行う必要がないので分岐予想ミスは生じない。残
りのケースは、分岐命令−−実行の流れを変更し得る命
令に関する。 （２）基本的ブロック１１０２におけるｂｒ命令のよう
に、ターゲットアドレスが動的なプログラムの振る舞い
に依存しない分岐命令（通常は無条件分岐）。個々の限
界は、ゼロにセットされ、ターゲットアドレスは以前の
確実性で分かるので分岐予想ミスは生じない。 （３）予想されたターゲットアドレスが実行可能にエン
コードされる（例えばマシンコードに埋め込まれたプロ
グラムカウンタオフセットとして）分岐命令。その例
は、基本的ブロック１１０３におけるジャンプ命令であ
る。予想されるターゲットアドレスは、実行可能性を検
査することにより（例えば、命令をデコードすることに
より）決定される。ターゲットアドレスは、ストールさ
れた命令のアドレスと比較される。

【０１１０】２つのアドレスが同一である場合には、個
々の限界がゼロにセットされ、即ち予想であったために
制御がストールされた命令に移行される場合には分岐予
想ミスは生じない。さもなくば、個々の限界は、それに
対応する先行項目アークのための頻度推定値にセットさ
れ、即ちストールされた命令への各制御の移行は、予想
とは異なり、ひいては、予想ミスとなる。例えば、アー
ク１１１３の限界は、予想された経路がアーク１１１３
であった場合にゼロにセットされるが、予想された経路
がアーク１１１４であった場合にはアーク１１１３の頻
度推定値にセットされる。 （４）プロセッサのランタイム状態に基づき、制御を静
的に知られたターゲットアドレスへ条件移行させる分岐
命令。その例は、基本的ブロック１１０４におけるｂｅ
ｑ命令である。この形式の命令の場合に、多くのプロセ
ッサ設計では、動的な分岐予想技術を使用して、分岐が
命令の以前の実行で行われたかどうかに基づき分岐が行
われる（即ち、制御が移行される）かどうかを予想す
る。

【０１１１】このような技術が、分析されているプロセ
ッサに使用される場合には、個々の限界が、先行項目ア
ークの頻度推定値か、又は図１３のアーク１１１６のよ
うに先行項目アークから発せられる他の制御流アーク
（以下、別のアークと称する）の頻度推定値から計算さ
れた推定値かのいずれか小さい方にセットされる。この
後者の推定値は、分岐がそれ以外のものより非常に頻繁
に行われるか又はその逆である場合に、動的な分岐予想
メカニズムがおそらく命令のほとんどの実行においてそ
の結果を正しく予想するという仮定に基づいて選択され
る。

【０１１２】特に、推定値は、動的な分岐予想メカニズ
ムが、デジタル・イクイップメント社のアルファ２１１
６４プロセッサに使用されるメカニズムと同様に、１つ
以上のビットをもつ経過テーブルを使用する場合には、
別のアーク１１１６の頻度推定値となる。これは、図１
３にアーク１１１５として示されたケースである。 （５）他の分岐命令（図１３には示さず）。上記した以
外の他の形式の分岐命令については、上記分析を使用し
て、分岐予想ミスの頻度に関する限界を推定できるが、
他の点では、個々の限界が先行項目アークの頻度推定値
にセットされ、このアークに沿った各制御移行は、悲観
的に予想ミスであると仮定される。

【０１１３】次いで、分岐予想ミスの頻度についての上
限を使用して、所与の命令のストールサイクルに対する
分岐予想ミスの寄与を推定することができる。特に、こ
の寄与は、次のように計算することができる。 分岐予想ミスの頻度の上限を次のもので除算する： ストールされた命令を常に含む基本ブロックの頻度： ペナルティ。 但し、「ペナルティ」は、分岐予想ミスの間に被るパイ
プラインストールサイクルの数である。この数は、特定
のプロセッサ実施形態に基づく。

【０１１４】同期の除外 あるプロセッサアーキテクチャーは、他のプロセッサ、
又は同じプロセッサで実行された以前の命令との同期オ
ペレーションを実行する命令を有する。これらの同期オ
ペレーションも、動的なストールを導入し得る。例え
ば、デジタル・イクイップメント社のアルファマイクロ
プロセッサアーキテクチャーは、マルチプロセッサの他
のプロセッサから見てプロセッサのメモリオペレーショ
ンを直列化するために動的なストールサイクルを導入す
る「メモリバリア」命令（ｍｂ）を有する。「トラップ
バリア」命令（ｔｒａｐｂ）は、全ての先行する命令が
トラップを招くことなく完了するよう保証されるまで動
的なストールを導入する。他のプロセッサアーキテクチ
ャーは、同様の機能のための命令を有する。同期は、ス
トールされた命令が同期を実行しない場合にストールの
考えられる説明として除外することができる。

【０１１５】デジタル・イクイップメント社のあるアル
ファマイクロプロセッサでは、ｍｂ命令は、その後に生
じる次のメモリアクセス命令にストールを生じさせる。
これらプロセッサでは、ｍｂ命令を介しての同期は、ス
トールされた命令がメモリアクセス命令でないか、又は
メモリアクセス命令ではあるがその直前にｍｂ命令が生
じない場合には、ストールの考えられる説明として除外
することができる。同様に、これらプロセッサでは、ｔ
ｒａｐｂ命令自体は、全ての先行する命令がトラップを
招くことなく完了するよう保証されるまでストールを生
じ、ｔｒａｐｂ命令を介しての同期は、ストールされた
命令それ自体がｔｒａｐｂ命令でない限り、ストールの
考えられる説明として除外することができる。

【０１１６】実行ユニットの競合の除外 又、動的なストールは、命令が実行準備されたときに使
用できない１つ以上のプロセッサ実行ユニットを命令が
必要とする場合にも生じる。例えば、実行ユニットは、
手前の命令を実行している間には使用できない。この種
のストールを生じる実行ユニットのセットは、プロセッ
サの実施形態に依存する。実行ユニットは、メモリアク
セスユニット、レジスタオペレーションユニット、整数
乗算及びフローティングポイント除算ユニットを含む。
このような実行ユニットの各々に対し、ストールされた
命令がその実行ユニットを必要としない場合には、競合
をストールの考えられる説明として除外することができ
る。例えば、「ａｄｄ」命令は、フローティングポイン
ト除算ユニットの使用と競合しないので、決してストー
ルされない。

【０１１７】書き込みバッファオーバーフローの除外 又、動的なストールは、記憶命令が発生準備されたが、
メモリ書き込みオペレーションを取り扱うプロセッサの
書き込みバッファが、まだ処理されている手前の書き込
み要求のためにいっぱいである場合にも生じる。これ
は、書き込みバッファオーバーフロート称される。

【０１１８】ストールされた命令が記憶でない場合に
は、書き込みバッファオーバーフローは、ストールの考
えられる説明として除外することができる。さもなく
ば、「最近実行された」命令がいずれも記憶でない場合
にはおそらく考慮されない。より詳細には、同じ基本的
ブロックにおけるストールされた命令の前の命令は、そ
れらのアドレスの下降順に検査される。これらの命令が
いずれも記憶でない場合には、制御がそのストールされ
た命令へと流れるところの基本的ブロックの命令も検査
されるが、そのストールされた命令を含むものより相当
に低い頻度で実行される基本的ブロックは、無視するこ
とができる。Ｄキャッシュ又はＤＴＢミスの取り扱いに
ついて既に述べた探索技術をここに適用することができ
る。探索は、記憶命令又は手順のエントリーポイントに
到達したときに終了する。

【０１１９】ストールの他の原因の除外 上記の説明は、既存のプロセッサにおけるパイプライン
ストールのほとんどの一般的な理由を網羅する。現在又
は将来のプロセッサにおける他の理由は、所与の形式の
命令をストールさせることのある命令及びメカニズムに
より必要とされるリソースを決定し、ひいては、静的な
ストールと、動的なストールの考えられる理由とを識別
するためにプロセッサ実施形態の同様の分析により除外
することができる。動的なストールが考えられる場合に
は、所与の命令へと通じる命令を上記のように検査し、
それらのいずれかが所与の命令をストールさせるかどう
か決定することができる。

【０１２０】方法及び装置Ｄ：「リタイア」された命令
を正確に測定するハードウェア性能カウンタ 本発明の好ましい実施形態において、命令の実行頻度
は、「リタイア」カウンタを含む特定設計のハードウェ
アを用いて直接測定することができる。リタイアカウン
タは、プログラムの各命令がリタイアされる回数に関す
る統計学的にサンプリングされた情報を与える。

【０１２１】特に、図１５に示すように、ハードウェア
１３００は、直列接続された命令キャッシュ（Ｉキャッ
シュ）１３１０、フェッチユニット１３２０、発生待ち
行列１３３０、実行パイプライン１３４０、及びリタイ
アユニット１３５０を備えている。リタイアユニット１
３５０は、リタイアカウンタ１３６０及び内部プロセッ
サレジスタ１３７０に接続される。更に、ハードウェア
は、割り込みハンドラー１３８０及び性能データ１３９
０を記憶するメモリ１３０１である。

【０１２２】ハードウェアのオペレーション中に、フェ
ッチユニット１３２０は、Ｉキャッシュ１３１０から命
令をフェッチし、発生待ち行列１３３０に入れる。命令
は、発生待ち行列から実行パイプライン１３４０へ送ら
れる。好ましい実施形態において、単一のプロセッササ
イクル中に多数の命令を発生することができる。命令が
首尾良く完了すると、リタイアユニット１３５０がリタ
イアカウンタ１３６０を増加する。カウンタ１３６０
は、割り込み信号をライン１３６１に周期的に発生し、
このとき、それに関連したプログラムカウンタ（ｐｃ）
値がＩＰＲ１３７０に記憶される。これに応答して、割
り込みハンドラー１３８０は、カウンタ１３６０及びＩ
ＰＲ１３７０をサンプリングし、性能データ１３９０を
発生することができる。サンプリングされた性能データ
は、特定のプログラムアドレス（ｐｃ値）の命令がリタ
イアされる回数に実質的に比例する。

【０１２３】カウンタに累積される「リタイア」事象の
数は、カウンタの特定ビットのオーバーフロー時に割り
込みを発生するようにカウンタをプリセットすることに
より選択することができる。カウンタ１３６０は、セッ
トライン１３６２上の信号によりセットすることができ
る。割り込みと割り込みとの間の任意の間隔は、カウン
タを所定値にセットすることにより選択できる。ランダ
ム長さの間隔を選択することができる。或いは又、カウ
ンタがカウントダウンレジスタとして実施される場合に
は、割り込みと割り込みとの間の間隔は、カウンタを選
択された値にプリセットすることにより選択できる。こ
こでは、カウンタは、過少流即ちゼロ値の際に割り込
む。

【０１２４】性能カウンタの公知の実施形態では、割り
込みハンドラーは、一般に、この割り込みハンドラーが
完了したときに実行されるべき次の命令のプログラムカ
ウンタ（ｐｃ）値にアクセスし、このｐｃ値は、「例外
アドレス」又は「復帰ｐｃ」と称されることもある。し
かしながら、このｐｃ値を単に記憶するだけでは、手前
の命令がリタイアされた回数を正確に反映しない。特
に、命令がリタイアしそして性能カウンタがオーバーフ
ローした場合には、そのオーバーフローを生じた命令が
既に実行されている。この場合は、復帰ｐｃは、リタイ
アされた命令のｐｃ値を反映しない。

【０１２５】割り込み処理の細部に基づき、復帰ｐｃ
は、命令ストリームにおいてリタイアにより割り込みが
生じた命令の直後の命令であってもよいし、又はフェッ
チユニット、発生待ち行列及び実行パイプラインの種々
の段階における命令の数に動的に基づいて、その後の可
変数の命令であってもよい。それ故、割り込みハンドラ
ー１３８０が復帰ｐｃを単に記録するときは、「リタイ
ア命令」カウンタを用いて各命令に対して記憶されたサ
ンプルカウントは、命令の実行頻度を正確に反映しな
い。

【０１２６】図１６に示された例示的な制御流れグラフ
の部分１４００について考える。５つの基本的ブロック
１４０１−１４０５がループに編成され、各基本的ブロ
ックは、単一の命令（１４１０−１４５０）で構成され
る。基本的ブロックの命令がリタイアするときには、
「リタイア」カウンタがオーバーフローし、そして割り
込みが発生され、割り込みハンドラーの復帰ｐｃ値が、
実行されるべき次の命令となる。

【０１２７】従って、命令１４２０のリタイアが割り込
みを発生するときには、復帰ｐｃ値が命令１４４０であ
り、同様に、命令１４３０が割り込みを発生するときに
は、復帰ｐｃ値が、命令１４３０における条件分岐の結
果に基づいて命令１４４０又は命令１４５０のいずれか
となる。従って、所与のｐｃ値に対して記録された同じ
カウントが、多数の先行する命令のリタイアを反映す
る。例えば、命令１４４０に対して記録された同じカウ
ントは、命令１４２０の全てのリタイアの結果を命令１
４３０の幾つかのリタイアに加えたものであり、同様
に、命令１４５０に対して記憶されたカウントは、命令
１４４０の全てのリタイアの結果を命令１４３０の幾つ
かのリタイアに加えたものである。一般に、この形式の
サンプルデータが与えられると、各命令のリタイア事象
の数を明確に決定することは不可能である。

【０１２８】ここに述べるようにハードウェアを変更す
ることにより、割り込みハンドラー１３８０により記録
された情報が、実際にリタイアされる命令のプログラム
カウンタ値を含むように確保することができる。本質的
な考え方は、カウンタがオーバーフローしそして割り込
みを発生するときに、リタイアにより割り込みを発生し
た正にその命令のプログラムカウンタ値を記録すること
である。このプログラムカウンタ値は、図１５の内部プ
ロセッサレジスタ（ＩＰＲ）１３７０に記録することが
できる。ＩＰＲは、例えば、割り込みハンドラー１３８
０により実行される特権命令により読み取ることができ
る。

【０１２９】プログラムカウンタ値は、多数のやり方で
リタイアユニット１３５０に得られるようにすることが
できる。これらの値は、命令と共に全プロセッサパイプ
ラインを経て搬送することができる。より一般的には、
命令がパイプラインを進行するときの命令の識別は、比
較的小さな命令番号即ち「ｉｎｕｍ」である。ｉｎｕｍ
のサイズは、一度にパイプラインに存在することのでき
る全命令数より大きくなる必要はない。

【０１３０】図１７に示すように、プログラムカウンタ
値１５２０に対して実行命令のｉｎｕｍ識別１５１０を
マッピングすることは、テーブル１５００を使用するこ
とにより実行できる。リタイアユニット１３５０は、リ
タイアを待機している命令、即ちパイプラインにある命
令のｉｎｕｍ１３５２の待ち行列１３５１を、各命令を
いつリタイアできるかを決定するのに使用される他の依
存性情報（ＤＥＰ）１３５３と共に維持する。判断は、
ロジック１３５４により行われる。命令がリタイアされ
るときは、そのｉｎｕｍ識別１３５２を用いて、それに
対応するｐｃ値１５２０をテーブル１５００から抽出す
る。このｐｃ値は、次いで、ＩＰＲ１３７０に記憶する
ことができる。

【０１３１】リタイアカウンタ１３６０がオーバーフロ
ーするときにサンプルを記録するために発生される割り
込み信号１３６１は、直ちに発生される必要がない。と
いうのは、リタイアされる命令のｐｃ値がＩＰＲ１３７
０に得られるからである。この値は、次の割り込みまで
変化しない。従って、プロセッサのパイプラインの設計
が、リタイアされた命令のｐｃ値を得るのに数サイクル
を必要とするようなものであるときには、ｐｃ値がＩＰ
Ｒ１３７０に書き込まれた後のある時間に割り込み１３
６１を発生することが許される。

【０１３２】あるプロセッサにおいて、単一のプロセッ
ササイクル中に多数の命令をリタイアすることができ
る。しかしながら、命令は、通常、「プログラム順序」
でリタイアされ、即ちそれらが一度に１つづつ実行され
る場合に実行される順序でリタイアされる。これは、通
常、命令を乱れた順序で発生できるプロセッサにおいて
も言えることである。従って、同じプロセッササイクル
中に命令のグループがリタイアされて、リタイアカウン
タをオーバーフローさせるときには、リタイアする命令
の少なくとも１つを、オーバーフローを生じさせた命令
として識別できる。例えば、リタイアカウンタは、値Ｘ
に達したときにオーバーフローにセットされ、プロセッ
サのリタイアサイクルは、値Ｘ−Ｎでスタートし、そし
てそのサイクル中にＫ個の命令がリタイアする。この場
合に、Ｋ個の命令のグループにおけるＮ番目の命令は、
オーバーフローを生じさせた命令であり、そのｐｃ値
は、ＩＰＲ１３７０に記憶されねばならない。

【０１３３】この技術は、他の種類の事象に対する他の
種類の性能カウンタへと拡張することができる。一般
に、いかなる事象に対しても、その事象に関連した情報
を記録することが望まれ、例えば、その事象を生じた命
令のｐｃ値を記録することができ、又はキャッシュにお
いてミスしたメモリオペレーションによりアクセスされ
たデータの仮想アドレスを記録することができる。この
付加的なデータのためにＩＰＲ１３７０のセットを維持
し、そして適当な事象カウンタがオーバーフローしたと
きにＩＰＲ１３７０を更新することにより、各個々の命
令又はメモリ位置に対して所与の事象のレートを反映す
るサンプルデータを直接的に得ることができる。

【０１３４】サンプリングされた実行頻度データの質を
改善する方法 ここに述べるハードウェアにより形成されるデータは、
ノイズを含む傾向がある。又、データは、潜在的に重大
な統計学的変化も含む。これらの変化は、次のような後
処理段階において減少することができる。 １．各手順の制御流れグラフにおける基本的ブロック
を、上記のように、頻度等価クラスにグループ分けす
る。稀な環境（例えば、ある手順が別の手順をコール
し、これが第３の手順のコードへとジャンプし、第１の
手順を終了するとき、又は割り込みが生じて、その割り
込まれたコードへ決して復帰しないとき）を除いて、所
与の頻度等価クラスにおける全ての基本的ブロックは、
プログラムの各実行において同じ回数だけ実行すること
が保証され、従って、これら基本的ブロックの各々にお
ける全ての命令も同じ回数だけ実行する。 ２．各々の頻度等価クラスに対し、そのクラスの各命令
ごとにサンプルカウントの平均値を得ることにより新た
な実行頻度推定値を決定する。あるクラスの命令のサン
プルカウントの変化が非常に大きい（例えば、平均の５
０％以上）場合には、それにより得られる頻度推定値
は、「低い信頼性」と判断される。

【０１３５】以上、本発明の好ましい実施形態を詳細に
説明したが、特許請求の範囲に規定した本発明の範囲か
ら逸脱せずに種々の変更がなされ得ることが当業者に容
易に明らかであろう。

【図面の簡単な説明】

【図１】本発明の好ましい実施形態によるプロファイリ
ングサブシステムにより動作をプロファイリングするこ
とのできるコンピュータシステムのブロック図である。

【図２】プロファイリングサブシステムの流れ線図であ
る。

【図３】プログラムの各命令を発生するのに必要な平均
サイクル数を決定するためのプロセスを示すブロック図
である。

【図４】実行頻度を推定するプロセスのブロック図であ
る。

【図５】命令の等価クラスを決定するプロセスのブロッ
ク図である。

【図６】拡張された制御流れグラフを示す図である。

【図７】初期頻度推定値及びストールサイクルを決定す
るプロセスを示すブロック図である。

【図８】頻度推定値をローカルに伝播するプロセスのブ
ロック図である。

【図９】制約ソルバーのブロック図である。

【図１０】頻度推定値をグローバルに伝播するプロセス
のブロック図である。

【図１１】動的なストールの理由を決定するための流れ
線図である。

【図１２】基本的なブロックのキャッシュミスのブロッ
ク図である。

【図１３】異なる形式の先行項目ブロックを示すブロッ
ク図である。

【図１４】ストールされた命令により参照される手順を
示すブロック図である。

【図１５】改良された性能カウンタを含むハードウェア
のブロック図である。

【図１６】ループにおいて実行される基本的ブロックを
示す図である。

【図１７】プログラムカウンタ値をルックアップするテ
ーブルを含む性能データ収集プロセスのデータ流れ線図
である。

【符号の説明】

１００ コンピュータシステム １１０ 中央処理ユニット（ＣＰＵ） １１１ プロセッサチップ １１２ カウンタ １１３ 実行ユニット １２０ メモリサブシステム １２１ ソフトウェアプログラム １２２ データ １３０ 入力／出力インターフェイス １４０ バス ２００ サブシステム ２０１ 手順 ２０２ 基本的ブロック ２０３ 制御流れグラフ（ＣＦＧ） ２０４ ノード ２０５ エッジ ２０６ データ構造体 ２０９ サンプルカウンタ ２１０ 制御流れ分析モジュール ３００ 性能データ分析器 ３４０ 性能データ

───────────────────────────────────────────────────── フロントページの続き (72)発明者 シュン タク アルバート レウン アメリカ合衆国 カリフォルニア州 94043 マウンテン ヴィュー モンテシ ト アベニュー 1285−24 (72)発明者 ウィリアム ウェイール アメリカ合衆国 カリフォルニア州 94114 サン フランシスコ クリッパー ストリート 280 (72)発明者 マーク ティー ヴァンデヴールド アメリカ合衆国 カリフォルニア州 94086 サニーヴェイル コーラル アベ ニュー 1159

Claims (3)

【特許請求の範囲】
1. 【請求項１】 実行パイプラインと、この実行パイプラ
   インの端に接続されたリタイアユニットとを含むプロセ
   ッサの性能データを収集する装置において、 上記プロセッサのリタイアユニットに接続されたレジス
   タと、 上記実行パイプラインから命令がリタイアされるときに
   上記レジスタを増加する手段と、 上記レジスタが所定値まで増加されたときに割り込みハ
   ンドラーに割り込みを発生する手段と、を備えたことを
   特徴とする装置。
2. 【請求項２】 リタイアにより上記レジスタを増加さ
   せ、オーバーフローさせ、そして割り込みを発生させる
   ような命令に関連したプログラムカウンタ値を記憶する
   ための内部プロセッサレジスタを更に備えた請求項１に
   記載の装置。
3. 【請求項３】 命令が実行される間に上記内部プロセッ
   サレジスタに記録するために上記プログラムカウンタ値
   を識別する手段を更に備えた請求項２に記載の装置。