(57)【特許請求の範囲】
【請求項１】
コンピュータシステムにおいてプログラムの実行命令を分析するためのコンピュータ化された方法において、
ＣＰＵが、プログラムを分析して、第１命令が実行される場合に全てが実行される命令からなる基本的なブロック（２０２）、及び当該基本的なブロック間の実行の流れに基づき、サイクル等価クラスを形成することにより、命令の頻度等価クラスを決定するステップであって、各頻度等価クラスが、当該頻度等価クラス内において他の命令と互いに同じ実行頻度を有する命令を含むものであり、
頻度等価クラスに属する命令の実行中に、ＣＰＵが性能カウンタ（１１２）を読み出すステップであって、当該カウンタが、頻度等価クラスに属する命令を、サンプリング周期内で発生するために必要なプロセッササイクル数を示すサンプルカウント（２０９）のための値を生成するものであり、当該サンプリング周期が、プロセッササイクルの数に対する期間を表す期間に対応するものであり、
ＣＰＵが、頻度等価クラスに属する動的ストールを招かない短いシーケンスの命令に対するサンプルカウントと、発生待ち行列のヘッドにおいて前記短いシーケンスの命令が費やさねばならない最小サイクル数とに基づいて、頻度等価クラスに対する実行頻度を決定するステップであって、当該頻度等価クラスに命令が属するものである、
を含む方法。
【請求項２】
ＣＰＵが、頻度等価クラスに属する命令を前記サンプリング周期及び実行頻度において発生するために必要なプロセッササイクル数を示す、サンプルカウントに基づいて、当該サンプルカウントを当該実行頻度で除算することにより、命令を発生させるためのプロセッササイクルの平均数を決定するステップと、
ＣＰＵが、プログラムの実行前に、動的なストールがないという仮定でプログラムの命令をスケジューリングすることにより、命令によって発生された（incurred）静的ストールサイクルの数を決定し、
ＣＰＵが、実行中に発生する動的ストールサイクルの数ではなく、静的ストールサイクルの数のみをストールサイクルに含めてなされた前記スケジューリングに基づき、プログラムの命令を発生させるために要求される最小サイクル数を計算し、
ＣＰＵが、前記プロセッササイクルの平均数から、命令を発生するために要求される、前記最小サイクル数を減算することによって、命令によって発生された（incurred）動的ストールサイクルの数を決定する、
ステップを更に含む、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、コンピュータシステムに係り、より詳細には、コンピュータシステムの性能データの分析に係る。
【０００２】
【従来の技術】
動作しているコンピュータシステムの性能の測定は、ハードウェア及びソフトウェアエンジニアにより行われる頻繁で且つ非常に重要な作業である。ハードウェアエンジニアは、新しいコンピュータハードウェアが既存のオペレーティングシステム及びアプリケーションプログラムでいかに動作するかを決定するために性能データを必要とする。ソフトウェアエンジニアは、オペレーティングシステム、カーナル、デバイスドライバ及びアプリケーションソフトウェアプログラムの危険をはらんだ部分を識別する必要がある。
【０００３】
近代的な高速パイプライン型のマルチプロセッサシステムの性能を測定することが特に問題である。パイプライン型のマルチプロセッサシステムにおいては、各プロセッササイクルごとに多数の命令を発生することができる。プロセッササイクルは、プロセッサ動作のための基本的なタイミング間隔である。ストールがない場合には、命令は、各サイクルごとにパイプラインを経て１段階づつ進行する。従って、理想的に、システムは最も効率的に動作する。これは、一度に多数の命令を種々のパイプラインにおいて同時に実行できることを意味する。一般的に、命令のオペレータコード及びオペランドは、命令を完全に実行するためにいかに多くのプロセッササイクルが必要とされるかを決定する。しかしながら、オペレータコードは、命令を発生するためにいかに多くのサイクルが必要とされるかを指示せず、これは、命令を実行しながら動的に決定できるに過ぎない。
【０００４】
【発明が解決しようとする課題】
しかしながら、幾つかの命令は、互いに干渉し合う。例えば、次のロード又は条件分岐は、まだ不完全である命令の結果を必要とする。他の場合には、命令が特定のフローティングポイント演算ユニットのようなプロセッサリソースを待機する。これらの場合には、その後の命令の実行が、他の命令が完了するか又はリソースを使用できるようになるまでストールされる。命令がストールされる間には、デコード及び処理が保留とされ、プロセッサは、低い効率で動作する。換言すれば、命令の実行を完了するに必要なサイクルの数が、理想的に決定されるものよりも大きくなる。
【０００５】
いかに頻繁に命令が実行されるかの性能データを収集するのにプロファイリングシステムを使用することができる。ある公知のプロファイリングシステムは、プログラムが実行されるときにデータを収集できる命令を挿入するためにソース又はオブジェクトプログラムを変更することを必要とする。プログラムを変更することは、プログラムを再コンパイル及び／又は再リンクする必要があることを意味する。
【０００６】
更に、公知のプロファイリングシステムは、一般に、特定の命令の実行の頻度しか決定せず、命令を発生するのに必要なサイクルの数を決定しない。パイプライン式のマルチプロセッサシステムにおいては、種々の命令を発生するに必要なサイクルの数は、システムの性能の重要な指示子である。
【０００７】
ある既知のシステムの更に別の制約として、アプリケーションプログラムの命令に対してプロファイルを発生することしかできない。これは、アプリケーションプログラムがオペレーティングシステム手順をコールするときに、システムの手順により実行される実際の命令に関する性能データが収集されないことを意味する。あるプロファイリングシステムは、システムコールを処理するのに必要な時間長さを測定し、そしてシステムコールを処理する時間を命令の「平均」実行時間で除算することにより性能データを推定するよう試みるが、システム手順の命令の実際の実行に関して何も具体的なものは学習されない。
【０００８】
それ故、ソース又はオブジェクトコードファイルを変更する必要なくマシンで実行可能なプログラムをプロファイリングし、このようにプロファイリングされたプログラムを再コンパイル又はリンクする必要がないことが望まれる。更に、アプリケーション及びシステム（カーナル）レベルの両方のプログラムをプロファイリングすることが望まれる。更に、各命令が実行される回数をプロファイリングするだけでなく、各命令が発生されるときに生じるストールサイクルの平均数、及びそれらのストールが生じる理由も、プロファイリングすることが望まれる。
【０００９】
【課題を解決するための手段】
本発明は、コンピュータシステムの性能データを分析するためのコンピュータ化された方法を提供する。実行される命令の正規化されたサンプルカウントを含む性能データがプログラム実行中に収集される。プログラムは、命令の等価クラスを決定するために分析される。命令の等価クラスにおいて、全ての命令は、同じ回数で実行される。
本発明は、その広い形態において、コンピュータシステムの性能データを分析するための請求項１に記載の方法に係る。
【００１０】
各等価クラスの命令に対する実行頻度が推定される。実行頻度は、各等価クラスの各命令を発生するのに必要な平均サイクル数を決定するのに使用できる。各命令を発生するのに必要な最小サイクル数も決定される。平均「測定」サイクル数から最小値を減算することにより、各命令により被る動的なストールサイクルの数を決定することができる。動的なストールサイクルを経験する命令については、動的なストールサイクルの理由を排除プロセスにより推定できる。
【００１１】
本発明の好ましい実施形態においては、プログラムは、ノード及びアークを有する制御流れグラフとして表される。このグラフにおいて、各ノードは、プログラムの基本成分を表し、そしてノードを接続するアークは、基本成分間の実行流を表す。あるノードは、基本的ブロックとして識別される。特定の基本的ブロックの各命令は、同じ回数だけ実行され、従って、特定の基本的ブロックの全ての命令は、命令の等価クラスを形成する。同じ実行頻度を有する全てのノードは、同じ等価クラスに指定することができ、等価クラスをできるだけ大きくすることができる。
【００１２】
好ましくは、以下に述べるように、プログラムの手順を表す制御流れグラフの関連するノード及びアークが識別される。更に、手順の入口ノード及び出口ノードが識別される。流れグラフは、手順の入口及び出口ノードを互いに接続することにより拡張される。次いで、流れグラフは、強力に接続されたサブグラフへと分解される。特定の強力に接続されたサブグラフは、その強力に接続されたサブグラフのいずれかのノードから手順の他のノードへのアークがない場合には、デッドエンド成分として識別される。デッドエンド成分に入る全てのアークは、その手順の出口ノードへと再指向される。次いで、一般化された方法を使用して、上記拡張された制御流れグラフのサイクル等価ノード及びアークを識別し、頻度等価クラスを決定することができる。
【００１３】
最小サイクル数は、モデルスケジューラを用いてプログラムの命令を理想的にスケジューリングすることにより決定できる。この最小数は、静的なストール、即ちプログラムの実行の前に決定できるストールにより被るサイクルを含む。次いで、各命令のサンプルカウントを命令の実行頻度で除算し、各命令を発生するのに必要な平均サイクル数を決定することができる。各命令の平均サイクル数から最小サイクル数を減算すると、プログラムの各命令により被る動的なストールサイクルが生じる。
【００１４】
動的なストールサイクルを招く命令が識別されると、動的なストールサイクルを招く特定の命令を生じさせる全ての考えられる理由を排除プロセスにより推定することができる。特定のストールに基づき、プロセスは、命令−キャッシュミス、データ−キャッシュミス、分岐予想ミス、プロセス同期、実行ユニット競合及び書き込みバッファオーバーフロー等の理由を排除することができる。
【００１５】
【発明の実施の形態】
本発明は、添付図面を参照した特定の実施形態の以下の詳細な説明より容易に理解されよう。
システムの概要
図１に示すように、コンピュータシステム１００は、バス１４０により互いに接続された中央処理ユニット（ＣＰＵ）１１０、メモリサブシステム（メモリ）１２０、及び入力／出力インターフェイス（Ｉ／Ｏ）１３０を備えている。このシステム１００は、埋め込まれたシステム、ＰＣ、ワークステーション、メインフレーム、又はネットワークでリンクされたコンピュータシステムのクラスターである。
【００１６】
好ましい実施形態においては、ＣＰＵ１１０は、高速パイプラインを使用するように設計された１つ以上の個々のプロセッサチップ１１１を備えている。パイプラインでは、各プロセッサ１１１は、多数の実行ユニット１１３を用いて多数の命令を同時に発生しそしてそれに基づいて動作することができる。実行ユニット１１３は、整数演算、フローティングポイント演算、ロード、記憶、分岐等の種々のオペレーションを実行することができる。典型的に、パイプライン型プロセッサは、ＲＩＳＣアーキテクチャーを使用する。パイプライン型アーキテクチャーでは、命令がメモリからフェッチされ、発生待ち行列へとスケジューリングされ、実行され、そしてリタイアされる。
【００１７】
各プロセッサ１１１には、１組の性能カウンタ１１２が関連される。各組のカウンタ１１２は、複数のレジスタとして実施できる。これらのレジスタは、例えば実行される命令のようなシステムの性能を表すシステムの重要な事象の発生をカウントすることができる。これらレジスタは、増加することができ、そしてオーバーフロー時に、これらレジスタに割り込んで、レジスタに記憶されたカウントを性能データとしてサンプリングすることができる。
【００１８】
メモリサブシステム１２０は、静的、動的、ランダム、逐次、揮発性及び永続的記憶素子、又はその組合せを含むことができる。これらの記憶素子は、レジスタ、キャッシュ、ＤＲＡＭ、ディスク、テープ等である。キャッシュは、同じプロセッサチップ上のプロセッサと共に常駐する命令及びデータキャッシュ（Ｉキャッシュ及びＤキャッシュ）を含むことができる。
メモリ１２０は、マシンで実行可能な命令の形態のソフトウェアプログラム１２１と、命令によりアクセスされるデータ１２２とを記憶する。ソフトウェアプログラム１２１は、オペレーティングシステム、デバイスドライバ及びアプリケーションプログラムを含むと共に、以下に詳細に述べるようにシステム１００の性能データを測定しそして分析するのに使用されるプログラムを含むことができる。
【００１９】
Ｉ／Ｏ１３０は、プリンタやターミナルやキーボード等の入力／出力デバイスへのインターフェイスを含むことができる。又、Ｉ／Ｏ１３０は、ライン１５０を経て、他のコンピュータシステムにデータを通信するネットワークに接続することもできる。
バス１４０は、通常、アドレス、データ、制御及びタイミング信号を種々のシステム要素間に搬送するための複数のラインとして実施される。
【００２０】
一般的なオペレーション
システム１００のオペレーション中に、プログラム１２１の命令がプロセッサ１１１により実行される。各命令は、その命令によりどんなオペレーションを実行すべきかを知らせるオペレータコードを含む。又、命令は、オペレーション中に使用すべき付加的なデータを参照するための１つ以上のオペランドを含むこともできる。命令は、一般に、プログラムの実行流を制御するか、又はデータをアクセス（読み取り及び書き込み）する。又、処理速度を上げるために、プロセッサは、分岐予想ロジック（図示せず）も備えている。分岐予想ロジックは、予想される実行順序で命令をロードするように試みる。通常のオペレーティング環境を著しく妨げることなくシステム１００において実行されるプログラムのプロファイルを発生することが望まれる。プロファイルは、好ましい実施形態においては、プログラム１２１の種々の命令の各々により被る動的なストールサイクルの平均数の指示を含む。１つの効果として、各命令に対する動的なストールサイクルの平均数を使用して、プロセッサの発生待ち行列における命令ストールの考えられる動的な原因を決定することができる。
【００２１】
プロファイリングサブシステム
図２は、本発明の好ましい実施形態によるサブシステム２００の流れ線図である。このサブシステム２００は、制御流れ分析モジュール２１０と、性能データ分析器３００とを備えている。
マシンで実行可能なコードの形態のプログラム１２１は、制御流れ分析モジュール２１０に与えられる。プログラム１２１は、カーナル及びアプリケーションプログラム、例えば、完全に実行可能な「２進イメージ」を含むことができる。マシンコードを分析するためのプロセスの一例が、１９９６年７月２３日付けのスリバスタバ氏等の「コンピュータシステム性能を監視するシステム(System for Monitoring Computer System Performance) 」と題する米国特許第５，５３９，９０７号に開示されている。
【００２２】
制御流れ分析器２１０は、コード１２１をデータ構造体２０６に仕切る。この構造体２０６は、手順２０１を含み、そしてこれら手順２０１は、基本的なブロック２０２を含むことができる。仕切られた構造体２０６は、手順及び基本的なブロックを識別するための情報を含むことができる。通常、手順は、単一の入口ポイントと、単一の出口ポイントとを有する。基本的なブロック２０２は、第１命令が実行される場合に全てが実行される命令のグループ又はセットとして定義される。換言すれば、基本的なブロックのいずれか１つの命令の実行頻度が既知の場合には、そのブロックの全ての命令の実行頻度が分かる。というのは、全ての命令が同じ回数だけ実行されるからである。それ故、このような基本的なブロックの命令は、同じ頻度の等価クラスに属すると言える。
【００２３】
稀なケースでは、基本的なブロックの種々の命令を異なる回数で実行することができる。これは、基本的なブロックが等価クラスを自動的に構成しないことを意味する。例えば、ブロックの中間に割り込み又は例外条件が生じるが、その割り込み又は例外からの復帰がなされない場合には、ブロックのそれ以前の命令がそれ以降の命令よりも頻繁に実行されることになる。このような割り込み及び例外により導入される歪は、通常は僅かであり、そして歪がコードにおける特定の命令に相関されそして頻繁でもある非常に稀な環境を除くと無視することができる。
【００２４】
手順２０１及び基本的なブロック２０２の命令は、制御流れグラフ（ＣＦＧ）２０３を形成するように更に分析される。例えば、分岐及びジャンプのような命令を識別することにより、手順と基本的なブロックとの間の実行の流れを決定することができる。ＣＦＧ２０３において、ノード２０４（円）は、手順又は基本的なブロックを表し、そしてこれらノードを接続するエッジ２０５（指向されたアーク）は、ノード間の実行の流れを表す。制御流れグラフ２０３は、基本的なブロック及びアークのための頻度等価クラスを決定するのに使用される。基本的なブロック及びアークの両方を検討することにより、頻度等価クラスをできるだけ大きくすることができる。
【００２５】
マシンで実行できるコード１２１の分析に加えて、コード１２１は、実行のためにシステム１００にロードされる。実行中に、図１の性能カウンタ１１２をサンプリングして、サンプル２０９を発生することができる。これらサンプルは、例えば、コード１２１の各命令を発生するためにプロセッササイクルの平均数を指示することができる。発生のために実際に必要な平均サイクル数を、プログラムの理想的な実行中に必要なサイクル数と比較して、パイプラインストールの考えられる原因を決定することができる。
ＣＦＧ２０３、構造体２０６及びサンプル２０９は、性能データ分析器３００へ送られる。性能データ分析器３００は、例えば、各命令ごとに性能データ３４０を発生し、この性能データは、実行の頻度、命令を発生するのに必要な平均サイクル数（ｃｐｉ）、及びパイプラインストールの考えられる原因を含むことができる。
【００２６】
性能データのサンプリング
図３に示すように、性能データ分析器３００は、ステップ３１０で実行されたコードの命令に対しサンプルカウント２０９を収集する。性能データは、何らかの既知のプロファイリングシステムにより収集することができる。ステップ３２０では、実行される命令の実行頻度がサンプルカウントに基づいて推定される。ステップ３３０の間に、各命令に対する平均サイクル数３４０が決定される。平均サイクル数は、命令がいかに良好にスケジュールされたかそしてストールがいかに頻繁に生じるかの良好な指示である。この情報を使用して、システム１００のハードウェア及びソフトウェアの設計を改善すると共に、動的なパイプラインストールの原因を決定することができる。
【００２７】
導入される頻度推定値
図４は、図３のステップ３２０のサブステップ４００を示す。ステップ４１０において、制御流れグラフ２０３を使用し、コード１２１の命令が頻度等価クラスにグループ分けされる。頻度等価クラスとは、上記したように、同じ実行頻度を有すると分かっている命令又はアークのセットであり、例えば、同じ回数だけ実行された命令である。同じ等価クラスにおけるアークは、同じ回数だけ横断される。例えば、基本的なブロックがいかに頻繁に実行されるか分かっている場合には、その基本的ブロックの各命令の実行頻度も分かる。
【００２８】
命令の各頻度等価クラスに対する実行頻度は、ステップ４２０において推定され、初期頻度推定値が決定される。これらの初期頻度推定値は、ステップ４３０において純化処理されて、最終的な頻度推定値４４０が形成される。これら推定値は、クラス間制約４５１を使用して等価クラス間に推定頻度をローカルに且つグローバルに伝播することにより純化処理される。クラス間制約４５１は、以下に述べる設定ステップ４５０において制御流れグラフ２０３から導出される。
【００２９】
制御流れグラフの処理
図５及び６を使用して、図４のステップ４１０のサブステップ５００を詳細に説明する。ステップ４１０の目的は、制御流れグラフ２０３の分析に基づき命令及びアークを頻度等価クラスにグループ分けすることである。
定義によれば、命令は、それらがプログラムの実行において同じ回数だけ実行される場合に頻度等価である。同様に、基本的ブロック及び制御流れアークは、それらがプログラムの実行において同じ回数だけ実行され又は横断される場合に頻度等価である。同じ基本的ブロックにおける命令は、常に、頻度等価である。というのは、１つの命令が実行されるときには、定義により、他の全ての命令も実行されるからである。異なる基本的ブロックにおける命令は、それに対応する基本的ブロックが頻度等価である場合には、頻度等価となる。
【００３０】
従って、サブステップ５００は、頻度等価の基本的ブロック及び制御流れアークを識別することを目的とする。これは、頻度等価に密接に関連した特性であるサイクル等価である基本的ブロック及びアークを表すノードを識別するために制御流れグラフ２０３を分析することにより達成される。
定義によれば、グラフにおけるノード及びアークのセットは、そのグラフの各サイクル即ち閉じた経路がそれらを全て含むか又は全く含まない場合にサイクル等価となる。サイクル等価のノード及びアークを識別する方法は、プロシーディングズ・オブ・ＡＣＭ  ＳＩＧＰＬＡＮ  ’９４  コンファレンス・オン・プログラミング・ランゲッジ・デザイン・アンド・インプレメンテーション、１９９４年の第１７１−１８５ページに掲載されたジョンソン氏等の「プログラム構造ツリー：直線的な時間での制御領域の計算(The Program Structure Tree: Computing Control Regions in Linear Time)」に説明されている。しかしながら、グラフにおけるサイクル等価は、頻度等価を意味しない。以下の説明は、制御流れグラフを拡張しそしてグラフをサブグラフに分割することにより頻度等価をいかに決定するかについて述べる。次いで、各サブグラフに対するサイクル等価を決定することができる。
【００３１】
入口及び出口ノード
図６に示すように、手順のための制御流れグラフ５１４は、入口ノード５１２及び出口ノード５１３と称する２つの特殊なノードを含む。これらのノードは、制御が手順５１４に入りそして出るポイントを表す。公知の方法は、入口ノードから手順の他の各ノードへの経路がありそして他の各ノードから手順の出口ノードへの経路もあるような流れグラフの制御にのみ適用される。本発明は、これら制約を必ずしももたない更に一般的な制御流れグラフにも適用できるように方法を改善する。
【００３２】
拡張された流れグラフ
図５のステップ５１０において、制御流れグラフは、出口ノードから入口ノードへアーク５１５で拡張される。図６のステップ５１１は、ノード５１２−５１３及びアーク５１５のためのこの変換を示している。ステップ５２０において、拡張された制御流れグラフは、既知の方法を使用して強く接続されたサブグラフに分解され、これについては、例えば、ＳＩＡＭジャーナル・オン・コンピューティング、１（２）：１４６−１６０、１９７２年に掲載されたタージャン著の「深さ優先探索及びリニアグラフアルゴリズム(Depth-first search and linear graph algorithms)」を参照されたい。
【００３３】
定義によれば、グラフの強く接続された成分は、各ノードから他の各ノードへの経路が存在する最大サブグラフである。図６のステップ５２１は、この分解を示し、破線のボックス５２２−５２４で包囲された３つの強く接続されたサブグラフが生じる。
以下の説明の目的上、「デッドエンド」サブグラフ又は成分５２４とは、そのノードからグラフの他のノードへのアークをもたずに強く接続された成分として定義される。
【００３４】
ステップ５３０において、デッドエンドに入る全てのアークは、出口ノードへ再指向される。これは、図６のステップ５３１によりアーク５４２の再指向と共に示されている。ステップ５４０において、ジョンソン氏等により開発されたサイクル等価を計算する方法が各デッドエンド成分５２４に適用される。各デッドエンド成分５２４に対し、この方法は、デッドエンド成分５２４におけるノード及びアークのサイクル等価クラスを形成する。
ステップ５５０において、この方法は、グラフの残り部分に適用され、その残り部分に対するサイクル等価クラスを生じる。これら２つのステップは、図６のステップ５４１に示されている。これら最後の２つのステップで形成されたサイクル等価クラスは、元のグラフの頻度等価クラスを構成する。
【００３５】
頻度及び命令当たりのサイクル（ｃｐｉ）の推定
プログラムの各命令に対して実行頻度及び命令当たりのサイクル（ｃｐｉ）を推定する方法と、これらの値に基づいてパイプラインストールの理由を推論する方法とについて、以下に詳細に説明する。これらの方法（Ａ−Ｄ）は、次の順に説明する。
Ａ．性能のボトルネック又は問題、即ちパイプラインストールを、プログラムの個々の命令のレベルで識別するための方法；
Ｂ．プログラムの個々の命令の実行頻度を推定する方法；
Ｃ．動的なストールの考えられる原因を推論する方法；及び
Ｄ．本発明による性能カウンタを用いてプログラムの個々の命令の実行頻度を測定する方法（及び装置）。
【００３６】
これらの方法では、周期的なサンプリングに基づくサンプルカウントは、各々の命令が発生待ち行列のヘッドにおいて費やす合計時間のみに比例することに注意されたい。周期的なサンプリングは、実行頻度に関する情報を直接的に与えるものではない。実行頻度は、方法Ｂについて述べるサンプルカウントから推定することもできるし、又は方法Ｄを用いて直接測定することもできる。
【００３７】
性能の問題を識別する方法Ａ
図７に示されたように、方法Ａ（６００）に必要な入力データは、次のものを含む。
１．分析されるプログラム；
２．各命令のサンプルカウント。但し、このカウントは、発生された命令が、応答なしにリタイアされ、即ち応答に対する無カウント発生であって、例外条件の処理により再発生される命令であるときに、発生待ち行列のヘッドにおいて費やされる時間に比例する；そして
３．分析されるシステムのためのモデル又はシュミレータ。
【００３８】
第１に、プログラム６０１が実行されるときに、生のサンプルカウント６０３が命令に対して収集される。図３のステップ３１０も参照されたい。これは、異なるＰＣ値を有する命令に対しサンプルカウントが決定されることを意味する。サンプルカウントは、順序正しいプロセッサの発生待ち行列のヘッドにおいて命令が費やす時間（サイクル数）に比例する。いかなる性能カウンタサンプリング技術もここに使用できることを理解されたい。生のサンプルの異常は、ステップ６４０において除去（正規化）され、信頼性のあるサンプル６０４を発生することができる。異常は、多発生命令によるか、又はストールサイクルがその後発生される命令と重畳するような遅延実行を伴う命令によるものである。
【００３９】
第２に、システムのモデル又はシステムシュミレータ（６０２）を使用して、動的なストールがないという仮定でプログラムの命令を理想的にスケジューリングすることができる（６１０）。このステップは、全ての静的なストール及びそれらの原因を識別する。理想的なスケジュールから、ステップ６２０において、各命令を発生するのに必要な最小の（理想的な）サイクル数を識別することができる。
【００４０】
第３に、最小のサイクルカウント及び正規化されたサンプルカウント６３０を使用して、各命令の実行頻度をステップ６５０において推定することができる。実行頻度は、命令が「リタイア」された回数である。リタイアされたとは、命令が実行を完了したことを意味する。これは、少なくとも次の３つの方法で行うことができる。
１）いかなるプログラムについても、これは、上記第１ステップからのサンプルカウントのみに依存する以下の方法Ｂを用いて行うことができる。
２）決定論的アプリケーションプログラムについては、基本的ブロックの実行をカウントする従来のプロファイリング技術を用いて頻度を決定することもできる。この場合、プログラムは、従来のプロファイラを用いて実行され、実行頻度が得られる。この場合に、同等のサンプルカウントを得るために同じ入力データでプログラムを再実行しなければならない。
３）いかなるプログラムについても、これは、命令がリタイアされる割合をサンプリングするために改善されたハードウェア性能カウンタに依存する方法Ｄを用いて行うこともできる。
【００４１】
第４に、ステップ６６０において各命令の命令当たりのサイクル（ｃｐｉ）を決定し、即ち各命令を発生するのに必要とされる平均サイクル数を決定する。この値は、所与の命令に対するサンプルカウントをその実行頻度で除算することにより計算できる。図３のステップ３３０も参照されたい。
第５に、方法Ｃを使用して、各命令に対する動的なストールサイクルの数と、各ストールに対して考えられる原因をステップ６７０において識別する。動的なストールサイクルの数は、ｃｐｉから最小（理想的）サイクル数（上記方法Ａの第２ステップ）を減算することにより決定できる。これが分かると、動的なストールに対して考えられる原因を求めることができる。
【００４２】
実行頻度を推定する方法Ｂ
入力及び出力データ
図８に示すように、方法Ｂ（７００）に対して必要な入力データは、次のものを含む。
１．プログラム７０１；
２．サンプルカウント７０２；
３．プログラムの制御流れグラフ（ＣＦＧ）７０３；及び
４．サンプルを収集する間にプログラムが実行されたプロセッサに対する命令スケジューラ又はモデル７０４。
【００４３】
上記のＣＦＧにおいて、各ノードは、基本的なブロックを表し、そして基本的なブロックは、当然同じ回数だけ実行される命令のシーケンスである。グラフにおける各アークは、１つのブロックから別のブロックへの考えられる実行流を表す。この方法は、たとえＣＦＧがあるアークを欠落しても、ＣＦＧがおそらくアークを欠落しているとマークされる限り、機能する。ソース、オブジェクト又は実行可能なコードからＣＦＧを構成する方法は、不正確であるために、アークが欠落することがある。
【００４４】
命令スケジューラ７０４は、命令（ＩＮＳＴＲＵＣＴＩＯＮ）のアレーを入力として取り上げ、そしてそれら命令に対する理想的なスケジュール（ＳＨＥＤ）を出力として返送することができる。ＳＨＥＤは、整数のアレーの形態をとることができる。このアレーにおいて、アレーエレメントＳＨＥＤ（Ｉ）は、静的なストールのサイクル数が正確に分かり且つ動的なストールが生じないと仮定される理想的なケースのもとで命令（ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ））を発生するに必要とされるサイクル数である。
【００４５】
更に、命令スケジューラは、命令と命令との間の静的な依存性を識別しなければならない。ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）は、ｊ＜Ｉの場合にＩＮＳＴＲＵＣＴＩＯＮ（ｊ）に対して静的な依存性を有すると共に、ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）は、ＩＮＳＴＲＵＣＴＩＯＮ（ｊ）により使用されるプロセッサリソース又はその命令により計算された値を常に必要とするので、ＩＮＳＴＲＵＣＴＩＯＮ（ｊ）より早期にスケジュールすることができない。
【００４６】
静的な依存性を識別するために、命令スケジューラは、アレーＳＨＥＤに加えて、アレーＤＥＥＰも返送できる。アレーＤＥＥＰにおいては、アレーエレメントＤＥＥＰ（Ｉ）は、ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）がＩＮＳＴＲＵＣＴＩＯＮ（ｊ）に対して依存性を有するときに値ｊを有するか、又はＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）が依存性をもたないときに値０を有するかのいずれかである。ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）が多数の先行する命令に対して静的な依存性を有する場合には、ＤＥＥＰ（Ｉ）は、ＩＮＳＴＲＵＣＴＩＯＮ（Ｉ）に最も近い先行する命令を表す値にセットされねばならない。
【００４７】
この方法は、次のような値の対を出力データとして発生する。ＣＦＧ７０３の各ブロック及びアークに対し、頻度推定値は、（ＦＲＥＱＵＥＮＣＹ、ＣＯＮＦＩＤＥＮＣＥ）の形態であり、負の数値ではないＦＲＥＱＵＥＮＣＹは、頻度の推定値であり、そしてＣＯＮＦＩＤＥＮＣＥは、推定値ＦＲＥＱＵＥＮＣＹがいかに正確に予想されるかを示す値である。
頻度推定値は、サンプルを得るために使用されるサンプリング周期の単位である。例えば、サンプリング周期が６５，５３６サイクル当たり１サンプルである場合には、頻度推定値１００を有する基本的ブロックは、６，５５３，６００の推定回数だけ実行されている。
【００４８】
方法Ｂの概要
サンプルカウントは、ＣＦＧの部分に対する推定値を推論するために使用される。これら推定値は、理想的な命令スケジュールをベースとし、各々の「成功裡な実行」、即ち命令が首尾良くリタイアされるために、発生待ち行列のヘッドにおいて短いシーケンスの命令（しばしば単一の命令）が費やさねばならない最小サイクル数を識別する。
第１に、おそらくは動的なストールを招かない短いシーケンスの命令を識別する。ＣＦＧにおける幾つかの基本的ブロックは、このようなシーケンスをもたないことがある。
【００４９】
次いで、発生待ち行列のヘッドにおいて命令が費やす最小サイクル数（「成功裡な実行」当たり）でサンプルカウントの和を除算したものとして、動的なストールを伴わない命令シーケンスの実行頻度を推定する。動的なストールを招くことのある幾つかのシーケンスについては、以下に述べる別の発見を使用して、それらの頻度を推定する。
ＣＦＧの流れ制約を使用して、直接推定できないブロック及びアークに推定値を伝播することができる。先ず、ローカル伝播及び他の自然の発見を利用して、ＣＦＧのほとんどの残り部分に対して推定を行うことができる。次いで、各推定値に信頼値を指定して、推定値の精度を指示する。最後に、ガウス排除(Gaussian 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))    式３
未知の頻度の解が負の場合には、その解は使用しない。
制約Ｎ＞０は、式２及び３に対しＣＦＧ７０３の入口及び出口ブロックを取り扱うことに注意されたい。
ローカル伝播を行うために、負の頻度を導入するもの以外、単一の伝播がそれ以上考えられなくなるまでは、単一の伝播を単に実行する。
【００７３】
ステップ５．若干のサンプルをもつクラスの推定の実行：
この点において、推定値をもたないクラスがまだ若干存在する。というのは、それらが若干のサンプル又は発生ポイントを含むからである。ステップ５（７５０）は、このようなクラスに対し自然のままの推定を行う。
少なくとも１つの発生ポイントを含むが、頻度推定値に欠けるクラスＣに対して、クラスＣの頻度を推定する。
クラスＣにおける命令のサンプルの和を、ＭＡＸ（１、Ｃに対するｍｉｎ ｈｅａｄ ｑアレーの和）で除算する。
ステップ６．ローカル伝播の繰り返し：
ステップ７６０では、ローカル伝播が付加的な推定値と共に繰り返される。
【００７４】
ステップ７．残りの流れを用いた推定の実行：
この点において、幾つかのアークが、依然として、推定値をもたないクラスにある。頻度２００の１つの到来するアークと、未知の頻度の２つの出て行くアークと、既知の頻度１００の１つの出て行くアークとをもつ単一の基本的ブロックＢを伴うＣＦＧ部分Ｂについて考える。
ここでは、ローカル伝播は不可能である。というのは、推定値をもたない２つ以上の出て行くアークがあるからである。出て行くアークに対する自然のままの推定は、残りの流れ（２００−１００）を、推定値をもたない出て行くアークの数で除算することである。
【００７５】
ステップ７７０は、推定値をもたないクラスにおいて全てのアークを考えることによりこのような推定を行う。各アークの両エンドポイントを検査することによりこれを行う。更に、残りの流れが負である（これは、推定値が不正確であるために起こり得る）ときにはエンドポイントを無視する。
アークＡがブロックＢに接続されたｓｉｂｌｉｎｇ ａｒｃｓ（アークＡ、ブロックＢ）を、アークＡが接続されたのと同じ側でブロックＢに接続されたアークＡ’（Ａ以外）のセットして定義する。例えば、アークＡがブロックＢに入る場合には、ｓｉｂｌｉｎｇ ａｒｃｓ（Ａ、Ｂ）は、ブロックＢに入るＡ以外のアークのセットである。
【００７６】
次いで、ブロックＢに接続されたアークＡに対する残りの流れは、ｓｉｂｌｉｎｇ ａｒｃｓ（Ａ、Ｂ）にあって且つ頻度推定値ｆｒｅｑ（クラス（Ａ’））を、（頻度推定値＋１をもたないｓｉｂｌｉｎｇ ａｒｃｓ（Ａ、Ｂ）内のアークの数）で除算したものを有するアークＡ’に対し、
ｆｒｅｑ（ｃｌａｓｓ（Ｂ））−ｓｕｍ  ｆｒｅｑ（ｃｌａｓｓ（Ａ’））
となる。
推定値をもたずそして少なくとも１つのアークを含まない各クラスＣに対し、先ず、次の初期指定を行う。
Ｎ：＝０、及び
流れ：＝０
次いで、クラスＣの各アークＡと、Ａの各エンドポイントＢ、即ちＡのソース又はターゲットブロックにおけるＢとに対し、推定値ｆｒｅｑ（クラス（ｂ））及びｒｅｓｉｄｕａｌ ｆｌｏｗ（ｂ、Ａ）≧０の場合には、
流れ：＝流れ＋ｒｅｓｉｄｕａｌ ｆｌｏｗ（Ｂ、Ａ）、及び
Ｎ：＝Ｎ＋１
となる。
最後に、Ｎ＞０の場合には、Ｃの頻度を（流れ／Ｎ）と推定する。
【００７７】
ステップ８．推定値への信頼値の指定：
推定値の幾つかは、他のものよりも精度が高くなり勝ちである。例えば、サブステップ３で形成されたほとんどの推定値は、おそらく、エラーを蓄積することのあるローカル伝播により形成される推定値、又は若干のサンプル又は若干の発生ポイントをもつブロックに対して自然のままの推定を行うステップ５で形成された推定値、或いは残りの流れを用いてアークに対して自然のままの推定を行うステップ７で形成された推定値よりも精度が高い。
更に、ステップ３で作られる推定値の場合には、精度が次のものに相関する。
１）平均値に寄与する多数の発生ポイントを有する（サブステップ３．ｈ）。及び
２）平均値に寄与する多数の発生ポイントの比に小さな変化しかもたない。
従って、ステップ７８０において「信頼値」を指定することにより推定値の精度を確立することができる。好ましい実施形態は、３つの信頼値、即ち低、中間及び高の信頼値を有する。
【００７８】
高信頼性の推定値は、次の通りである。
ａ）同じ基本的ブロックに少なくとも２つの発生ポイントをもつクラスに対してステップ３．ａで形成された推定値；
ｂ）ステップ３．ｄで形成された推定値；及び
ｃ）少なくとも３つの比（Ｎ≧３）（但し、最大の比は、最小の比の１．２倍以上）を平均化することによりステップ３．ｈで形成された推定値≧１００。
しかしながら、ステップ３．ｇが推定に対して２回以上行われた場合には、推定値の信頼性が低い。
【００７９】
中程度の信頼性の推定値は、次の通りである。
ａ）２つの発生ポイントをもつクラスに対してステップ３．ａで形成された推定値；
ｂ）ステップ３で形成された推定値≧１００。しかしながら、ステップ３．ｇが推定に対して２回以上行われた場合には、推定値の信頼性が低い；及び
ｃ）完全なＣＦＳ（即ちアークの欠落がない）に対してステップ４（ローカル伝播）で形成された推定値≧１００。しかしながら、ステップ３．ｇが、「流入＝流出」方程式に使用される推定に対して２回以上行われた場合には、推定値の信頼性が低い。
低信頼性の推定値は、残りの推定値である。
【００８０】
ステップ９．（グローバルな）制約ソルバーの使用：
この点において、頻度等価クラスのほとんどに対し推定値及び信頼値が存在する。しかしながら、推定値は、流れ制約に違反することがある。図８のステップ７９０は、推定値が適度な限界を越えない限り、例えば、負の推定値が許されることがない限り、制約ソルバーを使用して、制約を満足するように推定値を修正する。
制約ソルバーの重要な特性は、次の通りである。
（１）ソルバーは、一次方程式の過少制約系を取り扱わねばならず、これらはＡｘ＝ｂと表すことができる。但し、Ａは、制約のマトリクスであり、そしてｘ及びｂは、ベクトルである。
（２）変数の初期推定値のベクトルｘと、変数の重みのベクトルｗとが与えられると、ソルバーは、ベクトルｘ−ｘ’の重み付けされた大きさを最小にする解ベクトルｘ’を見出す。重みのベクトルｗに対するベクトルｖの重み付けされた大きさは、次の通りである。
ｓｑｒｔ（ｓｕｍ〔ｉ＝１、ｎ〕（ｗ（Ｉ）＊（ｖ（Ｉ）2 ））
【００８１】
図８に示すように、ガウスの排除及びグラム−シュミット正規直交化のような標準的な線型代数技術を使用してこのようなソルバーを簡単に構成することができる。
ａ）ステップ７９１において流れ制約をもつマトリクスＡを設定する。推定値を有する各頻度等価クラスごとにマトリクスＡの１つの列を使用する。各流れ制約ごとに１つの行を使用する。流れ制約は、ステップ４の式２及び式３をＣＦＧのブロックに適用することにより得られる。しかしながら、流れ制約は、これが推定値をもたない頻度等価クラスを指すときには破棄され、或いは流れ制約は、式２又は式３の全ての変数が同じ頻度等価クラスにあるときには全て０の行を形成する。
【００８２】
流れ制約は、独特の１組の頻度値を決定するには不充分であるから、マトリクスＡは、一次方程式の過少制約系となる。
ｂ）ステップ７９２において頻度推定値でベクトルｘを初期化する。ｘ〔ｉ〕は、頻度等価クラスに対する推定値である。
ｃ）ステップ７９３において頻度クラスＩに対する重みベクトルｗ〔ｉ〕を、頻度クラスＩにおけるブロック及びアークの数に推定値ｘ〔ｉ〕のｃｏｎｆｉｄｅｎｃｅ ｗｅｉｇｈｔを乗算したものを、ｘ〔ｉ〕＝０の場合は１で除算し、さもなくば、ｘ〔ｉ〕で除算したものに等しくなるように初期化する。但し、ｘ及びｗは、長さが等しい。
【００８３】
これらの重みは、流れ制約に違反する推定値の相対的な変化を制御するために次のステップに使用される。例えば、制約マトリクスＡが、２つの推定値のみを等しくすべきであることを示す場合には、推定値ｘ〔１〕が次の量だけ増加される。
（ｗ〔１〕／（ｗ〔１〕＋ｗ〔２〕））ｘ（ｘ〔２〕−ｘ〔１〕）
高い信頼性の推定値の重みは、低い信頼性の推定値よりも大きくなければならない。好ましい実施形態は、変数ｃｏｎｆｉｄｅｎｃｅ ｗｅｉｇｈｔを次の値にセットする。
信頼性の低い推定値の場合は１；
中程度の信頼性の場合は１００；そして
信頼性の高い推定値の場合は１００００。
【００８４】
又、推定値の重みは、それらの大きさに逆比例しなければならない。従って、同じ信頼値をもつ競合する推定値は、各々、同じ割合だけ調整される。例えば、頻度が２つの到来するアークについて１０及び１でありそして出て行くアークについて１０であって、各推定値が同じ信頼値を有するような基本的ブロックを有する流れグラフについて考える。重みが全て等しい場合には、制約ソルバーは、各々、値９．６７、０．６７及び１０．３４を指定する。この解決策において、右のアークに対する推定値が３３％だけ変更される。
【００８５】
重みが正規化されるときには、この解決策は、各々、９．５２、０．９５及び１０．４７を形成する。従って、推定値の各々は、その元の値のほぼ５％変更される。
ｄ）ステップ７９４において、制約ソルバーを使用し、重みについて元の推定値に最も密接な解を見つける。
ｅ）ステップ７９５において、下限より小さい解をその下限にリセットする。推定値の下限は、ステップ３．ｇではｆｒｅｑ ｌｏｗｅｒ ｂｏｕｎｄであり或いはステップ３で推定値が形成されない場合には０である。
ｆ）ステップ７９６において、元の値から１０％以上変化した推定値に対する信頼値を「低い信頼性」にリセットする。
【００８６】
方法Ｃ：ストールサイクルの説明
図１１ないし１４を参照して、方法Ｃを以下に説明する。
全体的な解決策
各命令ごとにストールサイクルの平均数が決定されると、次のステップは、ストールに対して考えられる説明を推論することである。これは、システム設計者が性能問題の原因を理解すると共に、適当な解決策を案出する上で助けとなる。
【００８７】
性能カウンタは、動的なストールを生じることのある事象、例えば、データキャッシュミスの発生をサンプリングするのに使用できる。しかしながら、ほとんどのシステムにおいては、このような性能カウンタは、どの命令が所与の事象を生じさせたかを正確に識別しない。方法Ｃは、方法Ｂで計算された実行頻度及び命令当たりのサイクルの情報を、手順に対する制御流れグラフと共に使用して、各動的なストールに対する理由を決定する。
【００８８】
図１１は、ストールサイクルに対する考えられる説明を見出すための全体的な解決策を示す。ステップ９１１において、各基本的なブロックの命令は、プロセッサパイプラインの詳細なモデルを用いてスケジュールされる。パイプラインのオペレーションの記録は、各命令がストールされたサイクル数（９２０）、なぜ命令がストールされたかの理由、及びもし適当であれば、そのストールを生じさせた「カルプリット（罪人）」と称する手前の命令（９１２）とを生じる。例えば、ストールされた命令は、カルプリット命令により計算された結果を必要とする。
【００８９】
ステップ９３１において、既知の静的なストールサイクル（９２０）が上記のように決定された全ストールサイクル（９３０）から減算されて、各命令ごとに動的なストールサイクル（９４０）を形成する。動的なストールサイクルとは、プロセッサパイプラインにより課せられる制約では説明できないストールサイクルである。
【００９０】
ステップ９５１において、命令シーケンス及び個々の命令の特性、制御流れグラフ、及び上記のように得られた頻度推定値を含む（これらに限定されない）全ての使用可能な情報（９５０）を分析することにより、動的なストールサイクルのための考えられる説明が識別される。この分析は、動的なストールのための考えられる理由、及びもし適当であれば、カルプリット（全体的に９５２）を形成する。
【００９１】
特定の命令により被った動的なストールの考えられる説明を見出すために（ステップ９５１）、命令が一般にストールを生じるようにさせる全ての既知の理由が考慮される。これら理由の幾つかは、特定の場合には、除外（又は排除）することができる。この排除プロセスを以下に詳細に説明する。
以下に述べる分析技術に加えて、種々の種類の事象をカウントするハードウェア性能カウンタを用いて、動的ストールの理由を識別することもできる。Ｉキャッシュミスのような事象に対し、各命令ごとにこれら事象の頻度を識別するサンプルを得ることができる。
【００９２】
この情報は、命令について観察された動的なストールに対する各考えられる理由の寄与を決定するのに使用できる。所与の事象についてのサンプルは、各命令ごとに、その命令に対して事象が生じた回数の適当なカウントを与えねばならない。ある種の事象については、これは、方法Ｄにおいて以下に述べる形態のハードウェアサポートを必要とする。
【００９３】
一般に、除外できない理由は、特定のストールに対する考えられる説明として与えられる。排除は、各動的なストールに対し独特の説明を常には生じないが、しばしばそのようにすることができる。実際に、命令は、多数の理由で同時に又は異なる時期にストールされることがある。たとえ独特の理由を与えることができなくても、全ての考えられる理由を与えることは、ユーザがその可能性を絞り込む上で助けとなろう。動的なストールの幾つかの共通の原因を適当な条件のもとでいかに除外できるかについて以下に説明する。
【００９４】
Ｉキャッシュ又はＩＴＢミスの除外
動的なストールは、命令キャッシュ（Ｉキャッシュ）が命令をフェッチするためにアクセスされたが、必要な命令がＩキャッシュにないときに生じる。これをＩキャッシュミスと称する。この場合に、命令は、待ち時間の長いメモリからフェッチしなければならない。
同様に、動的なストールは、命令変換のルックアサイドバッファ（ＩＴＢ）が命令の仮想メモリアドレスを物理的なメモリアドレスに変換するためにアクセスされたが、必要な変換エントリーがＩＴＢにない（ＩＴＢミスと称する）ときに生じる。この場合には、命令フェッチを続ける前に必要なエントリーでＩＴＢを更新しなければならない。ストールされる命令の直前にフェッチされて実行される命令のアドレスによりある条件が満足される場合に、Ｉキャッシュ又はＩＴＢミスを除外することができる。
【００９５】
図１２は、Ｉキャッシュミスについて考えるケースを示す。（ＩＴＢミスは、以下に述べる。）３つの基本的なブロック１０３１、１０３２、１０３３が図示されている。ブロック１０３１及び１０３２は、ブロック１０３３をコールし、アーク１０３３−１０３４は、制御流れグラフに表されたようにそれらの間に流れる。又、命令１０１１−１３がブロック１０のライン１０２１−１０２４にいかにマップされ、そして基本的ブロック１０３３の命令がメモリにいかにレイアウトされるかも図示されている。図１２において、命令１０１１−１０１３は、斜線で示されており、そしてこれらライン間の分離は、破線で示されている。
【００９６】
命令１０１１、１０１２、１０１３により示されたように、多数のケースについて考慮する。ストールされた命令が基本的ブロックの始めに存在しない場合には、２つのサブケースがある。その命令、例えば、１０１２がキャッシュラインの始めにある（換言すれば、命令のアドレスがキャッシュラインサイズの整数倍である）場合には、Ｉキャッシュミスを除外することができない。というのは、命令が別のキャッシュラインにおいてその直前で実行されるからである。ストールされた命令（例えば、１０１３）がキャッシュラインの始めに存在しない場合には、Ｉキャッシュミスを除外することができる。
【００９７】
最終的に、命令、例えば１０１１が、基本的ブロックの始めに存在する場合には、それがキャッシュラインの始めにも存在するかどうかに関わりなく、以下先行項目ブロックと称する全ての基本的ブロック、例えば、１０３１、１０３２の最後の命令が検査される（先行項目ブロックから、制御は、ストールされた命令を含む基本的ブロック、例えば、１０３３へ流れる）。これらの命令が、全て、ストールされた命令、例えば１０１１と同じキャッシュラインにある場合には、Ｉキャッシュミスを除外することができる。命令は、それらのアドレスが、キャッシュラインサイズで除算したときに同じ商を生じる場合には、同じキャッシュラインに存在する。この分析は、以前に得られた頻度推定値に基づき、ストールされた命令を含む基本的ブロックよりも相当に低い頻度で実行される先行項目ブロックを無視する。
【００９８】
この分析が、データ及び命令の両方に対して単一のキャッシュしかもたないプロセッサ又はコンピュータシステムに適用される場合には、１つの付加的なチェックを行わねばならない。ストールされた命令がメモリをアクセスする直前にいずれか１つの命令が実行される場合には、Ｉキャッシュミスを除外することができない。これは、メモリアクセスが、ストールされた命令を含むキャッシュラインを変位して、アクセスされているデータのための余地を作るからである。
【００９９】
上記分析は、命令の実行が、制御流れグラフにより指示される順序を常にたどることを仮定する。割り込みは、この仮定に違反させることがある。しかしながら、割り込みは、あまり頻繁に生じることがなくそして命令ストリームにおいてランダムなポイントで生じるので、この仮定は、統計学的な意味では合理的に保持される。更に、例外も、この仮定に違反する。
【０１００】
或いは又、Ｉキャッシュミスの影響は、Ｉキャッシュミス事象についてプログラムカウンタを統計学的にサンプリングすることにより評価することができる。この方法は、時間経過に伴い、Ｉキャッシュミスのために各命令がいかに頻繁にストールされるかの正確な推定値を形成することができる。この推定値から、Ｉキャッシュミスに起因し得るストールサイクル（この命令により被る）の数についての上限が計算される。より詳細には、上限は、次のものの積である。
（ａ）この命令に対して観察されるＩキャッシュミス事象の数；
（ｂ）Ｉキャッシュミスに対するサンプリング周期（この多数のＩキャッシュミスのうちの各１つがサンプリングされる）；及び
（ｃ）Ｉキャッシュミスの最大ペナルティ（通常は、メインメモリのアクセス待ち時間）。
【０１０１】
その結果は、ストールされた命令が実行される推定回数で除算され、平均値が得られる。この平均値が小さい（例えば、サイクルの半分未満）場合には、Ｉキャッシュミスを、ストールについて考えられる説明として除外できる。さもなくば、理由がユーザに情報として与えられる。
ＩＴＢミスの分析も同様であるが、前記説明の「キャッシュライン」を「仮想メモリページ」として解釈しなければならない。
【０１０２】
Ｄキャッシュ又はＤＴＢミスの除外
又、動的なストールは、データキャッシュ（Ｄキャッシュ）がロード命令でアクセスされるが、必要なデータがＤキャッシュに存在しないときにも生じる。これは、Ｄキャッシュミスと称する。同様に、動的なストールは、データ変換ルックアサイドバッファ（ＤＴＢ）がデータの仮想メモリアドレスを物理的なメモリアドレスに変換するためにアクセスされたが、必要な変換エントリーがＤＴＢに存在しない（ＤＴＢミスと称する）ときにも生じる。
【０１０３】
異なるプロセッサ実施形態は、Ｄキャッシュミス又はＤＴＢミスが生じたときには異なる振る舞いをする。ある実施形態では、ロード命令自体がストールされる。この場合に、Ｄキャッシュミス又はＤＴＢミスは、ストールされた命令がロード命令でない場合に除外することができる。他の実施形態では、ロードは遅延を伴わずに発生されるが、ロードの結果を使用する命令は、その結果が実際に使用できるようになるまでストールされる。この場合には、命令ストリームにおいてレジスタが読み取られそして書き込まれる順序を分析しなければならない。
【０１０４】
Ｄキャッシュミス又はＤＴＢミスは、命令ストリームにおいてレジスタが読み取られそして書き込まれる順序及び仕方によってある条件が満足される場合には除外することができる。
ストールされた命令がＤキャッシュミス又はＤＴＢミスによりストールされたかどうかを決定するために、それが参照する各レジスタが考慮される。
図１４は、データミスによるストール除外するために実行することのできる分析を示す。図１４において、ブロック１２０１からブロック１２０２又はブロック１２０３へ実行が行われ、ブロック１２０４は、ブロック１２０２又は１２０３が実行された後に実行される。命令１２１３は、例えば、レジスタｔ０による参照を分析するに必要なデータが直ちに得られないことによりストールされる。
【０１０５】
レジスタｔ０については、ストールされた命令１２１３のレジスタｔ０を最後に参照した命令１２１１−１２１２が、以下に詳細に述べる仕方で識別される。このような命令がメモリからレジスタｔ０へデータをロードする場合には、Ｄキャッシュミス又はＤＴＢミスがストールのための考えられる説明とみなされ、その命令は、カルプリットとして識別される。これは、ストールされた命令により参照された各レジスタに適用される。これらレジスタのいずれもカルプリットを生じない場合には、Ｄキャッシュミス又はＤＴＢミスがストールのための考えられる説明として除外される。図１４において、例えば、Ｄキャッシュミス又はＤＴＢミスは、ロード命令１２１２で、カルプリットと考えられる。
【０１０６】
この分析で考慮すべき全ての命令を見出すために、同じブロック内のストールされた命令より前の命令が、最初に、それらのアドレスの下降順で検査される。それらのいずれもレジスタを参照しない場合には、制御がそのストールされた命令へと流れるところの基本的ブロックの命令も検査される（これも所与の基本的ブロックにおける命令のアドレスの下降順に）が、そのストールされた命令を含むものより著しく低い頻度で実行される基本的ブロックは、無視することができる。ストールされた命令の頻度推定値の小さな割合としてスレッシュホールドを計算することができ、そして頻度推定値がこのスレッシュホールドより低い基本的ブロックを無視することができる。
【０１０７】
基本的ブロックのこの検討は、例えば、ストールされた命令を含む基本的ブロックから始めて逆の制御流れグラフ（元のグラフにおける全ての制御流れアークの方向を逆転することによって形成された）において深さ優先探索を行うことにより実行できる。これについては、ホプクロフト氏等の「グラフ操作のための効率的なアルゴリズム(Efficient Algorithms for Graph Maniplation)」、コミュニケーションズ・オブ・ザ・ＡＣＭ、１６（６）：３７２−３７８、１９７３年を参照されたい。この探索において、基本的なブロックに隣接するものは、その基本的ブロック自体が当該レジスタを参照する命令を含む場合には、調べられる必要がない。
【０１０８】
好ましい実施形態は、データ及び命令が個別のキャッシュ及び個別の変換ルックアサイドバッファを有するコンピュータシステムを参照して説明したが、Ｉキャッシュ、ＩＴＢ、Ｄキャッシュ及びＤＴＢミスを除外するための方法は、データ及び命令が単一のキャッシュを共用するか、又はデータ及び命令が単一の変換ルックアサイドバッファを共用するか、或いはその両方であるようなプロセッサ及びコンピュータシステムにも適用できる。
【０１０９】
しかしながら、データ及び命令が単一のキャッシュ又は変換ルックアサイドバッファを共用する場合には、Ｄキャッシュ又はＤＴＢミスに対して付加的な理由を考慮しなければならない。例えば、メモリ位置Ａに１つの命令がロードされ、同じ基本的ブロックにおけるその後の命令がその命令自体にキャッシュミスを招きそしてキャッシュから位置Ａのデータを変位し、次いで、同じ基本的ブロックに依然として存在するその後の命令がＡにロードしようと試み、Ａの第２のロードがキャッシュにおいてミスとなると仮定する。Ｉキャッシュミスに関する情報を用いて、このような状態を除外することができる。
【０１１０】
分岐予想ミスの除外
又、動的なストールは、分岐命令の実際のターゲットがプロセッサの分岐予想ロジックにより予想されるターゲットと相違するときにも生じる。これは、分岐予想ミスと称する。ここでは、「分岐命令」は、プログラムの制御流を変更し得る命令を意味し、即ちそれらは、一般に「分岐」と称される命令を含むだけでなく、「ジャンプ」、サブルーチンコール、及び復帰命令等も含む。
【０１１１】
いかに多くの分岐予想ミスがストールに寄与するかは、制御が以下に述べるようにストールされた命令に到達するときに生じ得る分岐予想ミスの頻度についての上限を計算することにより推定できる。分岐予想ミスは、その寄与がある適当なスレッシュホールドより低い場合にはストールのための考えられる説明として除外することができ、或いは又、その寄与は、それがいかに小さくてもユーザに与えることができる。
基本的ブロックの始めにストールされた命令をいかに取り扱うかについて以下に説明する。ストールされた命令が基本的ブロックの第１の命令でない場合は、分岐予想ミスをストールの考えられる説明として直ちに除外することができる。それ以上の分析は、必要とされない。
【０１１２】
ストールされた命令の直前の分岐予想ミスの頻度の上限を見出すために、その命令の直前に実行される全ての基本的ブロックが、図１３に示すように検討される。この説明上、これらの基本的ブロックは、先行項目ブロック（例えば、１１０１、１１０２、１１０３、１１０４）と称され；これら先行項目ブロックからストールされた命令（ｓｕｂｑ）を含む基本的ブロックへの制御流れアークは、先行項目アーク（例えば、１１１１、１１１２、１１１３、１１１５）と称され；そして先行項目ブロックの最後の命令は、先行項目命令（例えば、ａｄｄｑ、ｂｒ、ｊｍｐ及びｂｅｑ命令）と称される。例えば、全ての先行項目ブロックが未知である場合には、基本的ブロックは、未知のコールされたサブルーチンからの「戻り」命令のターゲットであり、従って、未知の先行項目は、悲観的に、常に予想ミスであると仮定することができる。
【０１１３】
ストールされた命令について計算されるべき限界１１２２は、各先行項目命令に１つづつある個々の限界の和である。ここの限界は、ボックス１１２１として示されている。４つの形式の先行項目命令がある。最初の４つが図１３に示されている。即ち
（１）基本的ブロック１１０１におけるａｄｄｑ命令のような非分岐命令。個々の限界は、ゼロにセットされ、予想を行う必要がないので分岐予想ミスは生じない。残りのケースは、分岐命令−−実行の流れを変更し得る命令に関する。
（２）基本的ブロック１１０２におけるｂｒ命令のように、ターゲットアドレスが動的なプログラムの振る舞いに依存しない分岐命令（通常は無条件分岐）。個々の限界は、ゼロにセットされ、ターゲットアドレスは以前の確実性で分かるので分岐予想ミスは生じない。
（３）予想されたターゲットアドレスが実行可能にエンコードされる（例えばマシンコードに埋め込まれたプログラムカウンタオフセットとして）分岐命令。その例は、基本的ブロック１１０３におけるジャンプ命令である。予想されるターゲットアドレスは、実行可能性を検査することにより（例えば、命令をデコードすることにより）決定される。ターゲットアドレスは、ストールされた命令のアドレスと比較される。
【０１１４】
２つのアドレスが同一である場合には、個々の限界がゼロにセットされ、即ち予想であったために制御がストールされた命令に移行される場合には分岐予想ミスは生じない。さもなくば、個々の限界は、それに対応する先行項目アークのための頻度推定値にセットされ、即ちストールされた命令への各制御の移行は、予想とは異なり、ひいては、予想ミスとなる。例えば、アーク１１１３の限界は、予想された経路がアーク１１１３であった場合にゼロにセットされるが、予想された経路がアーク１１１４であった場合にはアーク１１１３の頻度推定値にセットされる。
（４）プロセッサのランタイム状態に基づき、制御を静的に知られたターゲットアドレスへ条件移行させる分岐命令。その例は、基本的ブロック１１０４におけるｂｅｑ命令である。この形式の命令の場合に、多くのプロセッサ設計では、動的な分岐予想技術を使用して、分岐が命令の以前の実行で行われたかどうかに基づき分岐が行われる（即ち、制御が移行される）かどうかを予想する。
【０１１５】
このような技術が、分析されているプロセッサに使用される場合には、個々の限界が、先行項目アークの頻度推定値か、又は図１３のアーク１１１６のように先行項目アークから発せられる他の制御流アーク（以下、別のアークと称する）の頻度推定値から計算された推定値かのいずれか小さい方にセットされる。この後者の推定値は、分岐がそれ以外のものより非常に頻繁に行われるか又はその逆である場合に、動的な分岐予想メカニズムがおそらく命令のほとんどの実行においてその結果を正しく予想するという仮定に基づいて選択される。
【０１１６】
特に、推定値は、動的な分岐予想メカニズムが、デジタル・イクイップメント社のアルファ２１１６４プロセッサに使用されるメカニズムと同様に、１つ以上のビットをもつ経過テーブルを使用する場合には、別のアーク１１１６の頻度推定値となる。これは、図１３にアーク１１１５として示されたケースである。
（５）他の分岐命令（図１３には示さず）。上記した以外の他の形式の分岐命令については、上記分析を使用して、分岐予想ミスの頻度に関する限界を推定できるが、他の点では、個々の限界が先行項目アークの頻度推定値にセットされ、このアークに沿った各制御移行は、悲観的に予想ミスであると仮定される。
【０１１７】
次いで、分岐予想ミスの頻度についての上限を使用して、所与の命令のストールサイクルに対する分岐予想ミスの寄与を推定することができる。特に、この寄与は、次のように計算することができる。
分岐予想ミスの頻度の上限を次のもので除算する：
ストールされた命令を常に含む基本ブロックの頻度：
ペナルティ。
但し、「ペナルティ」は、分岐予想ミスの間に被るパイプラインストールサイクルの数である。この数は、特定のプロセッサ実施形態に基づく。
【０１１８】
同期の除外
あるプロセッサアーキテクチャーは、他のプロセッサ、又は同じプロセッサで実行された以前の命令との同期オペレーションを実行する命令を有する。これらの同期オペレーションも、動的なストールを導入し得る。
例えば、デジタル・イクイップメント社のアルファマイクロプロセッサアーキテクチャーは、マルチプロセッサの他のプロセッサから見てプロセッサのメモリオペレーションを直列化するために動的なストールサイクルを導入する「メモリバリア」命令（ｍｂ）を有する。「トラップバリア」命令（ｔｒａｐｂ）は、全ての先行する命令がトラップを招くことなく完了するよう保証されるまで動的なストールを導入する。他のプロセッサアーキテクチャーは、同様の機能のための命令を有する。同期は、ストールされた命令が同期を実行しない場合にストールの考えられる説明として除外することができる。
【０１１９】
デジタル・イクイップメント社のあるアルファマイクロプロセッサでは、ｍｂ命令は、その後に生じる次のメモリアクセス命令にストールを生じさせる。これらプロセッサでは、ｍｂ命令を介しての同期は、ストールされた命令がメモリアクセス命令でないか、又はメモリアクセス命令ではあるがその直前にｍｂ命令が生じない場合には、ストールの考えられる説明として除外することができる。同様に、これらプロセッサでは、ｔｒａｐｂ命令自体は、全ての先行する命令がトラップを招くことなく完了するよう保証されるまでストールを生じ、ｔｒａｐｂ命令を介しての同期は、ストールされた命令それ自体がｔｒａｐｂ命令でない限り、ストールの考えられる説明として除外することができる。
【０１２０】
実行ユニットの競合の除外
又、動的なストールは、命令が実行準備されたときに使用できない１つ以上のプロセッサ実行ユニットを命令が必要とする場合にも生じる。例えば、実行ユニットは、手前の命令を実行している間には使用できない。この種のストールを生じる実行ユニットのセットは、プロセッサの実施形態に依存する。実行ユニットは、メモリアクセスユニット、レジスタオペレーションユニット、整数乗算及びフローティングポイント除算ユニットを含む。
このような実行ユニットの各々に対し、ストールされた命令がその実行ユニットを必要としない場合には、競合をストールの考えられる説明として除外することができる。例えば、「ａｄｄ」命令は、フローティングポイント除算ユニットの使用と競合しないので、決してストールされない。
【０１２１】
書き込みバッファオーバーフローの除外
又、動的なストールは、記憶命令が発生準備されたが、メモリ書き込みオペレーションを取り扱うプロセッサの書き込みバッファが、まだ処理されている手前の書き込み要求のためにいっぱいである場合にも生じる。これは、書き込みバッファオーバーフロート称される。
【０１２２】
ストールされた命令が記憶でない場合には、書き込みバッファオーバーフローは、ストールの考えられる説明として除外することができる。さもなくば、「最近実行された」命令がいずれも記憶でない場合にはおそらく考慮されない。より詳細には、同じ基本的ブロックにおけるストールされた命令の前の命令は、それらのアドレスの下降順に検査される。これらの命令がいずれも記憶でない場合には、制御がそのストールされた命令へと流れるところの基本的ブロックの命令も検査されるが、そのストールされた命令を含むものより相当に低い頻度で実行される基本的ブロックは、無視することができる。Ｄキャッシュ又はＤＴＢミスの取り扱いについて既に述べた探索技術をここに適用することができる。探索は、記憶命令又は手順のエントリーポイントに到達したときに終了する。
【０１２３】
ストールの他の原因の除外
上記の説明は、既存のプロセッサにおけるパイプラインストールのほとんどの一般的な理由を網羅する。現在又は将来のプロセッサにおける他の理由は、所与の形式の命令をストールさせることのある命令及びメカニズムにより必要とされるリソースを決定し、ひいては、静的なストールと、動的なストールの考えられる理由とを識別するためにプロセッサ実施形態の同様の分析により除外することができる。動的なストールが考えられる場合には、所与の命令へと通じる命令を上記のように検査し、それらのいずれかが所与の命令をストールさせるかどうか決定することができる。
【０１２４】
方法及び装置Ｄ：「リタイア」された命令を正確に測定するハードウェア性能カウンタ
本発明の好ましい実施形態において、命令の実行頻度は、「リタイア」カウンタを含む特定設計のハードウェアを用いて直接測定することができる。リタイアカウンタは、プログラムの各命令がリタイアされる回数に関する統計学的にサンプリングされた情報を与える。
【０１２５】
特に、図１５に示すように、ハードウェア１３００は、直列接続された命令キャッシュ（Ｉキャッシュ）１３１０、フェッチユニット１３２０、発生待ち行列１３３０、実行パイプライン１３４０、及びリタイアユニット１３５０を備えている。リタイアユニット１３５０は、リタイアカウンタ１３６０及び内部プロセッサレジスタ１３７０に接続される。更に、ハードウェアは、割り込みハンドラー１３８０及び性能データ１３９０を記憶するメモリ１３０１である。
【０１２６】
ハードウェアのオペレーション中に、フェッチユニット１３２０は、Ｉキャッシュ１３１０から命令をフェッチし、発生待ち行列１３３０に入れる。命令は、発生待ち行列から実行パイプライン１３４０へ送られる。好ましい実施形態において、単一のプロセッササイクル中に多数の命令を発生することができる。命令が首尾良く完了すると、リタイアユニット１３５０がリタイアカウンタ１３６０を増加する。リタイアされた命令に関連するプログラムカウンタ（ｐｃ）値がＩＰＲ１３７０に記憶される。カウンタ１３６０は、割り込み信号をライン１３６１に周期的に発生する。これに応答して、割り込みハンドラー１３８０は、カウンタ１３６０及びＩＰＲ１３７０をサンプリングし、性能データ１３９０を発生することができる。サンプリングされた性能データは、特定のプログラムアドレス（ｐｃ値）の命令がリタイアされる回数に実質的に比例する。
【０１２７】
カウンタに累積される「リタイア」事象の数は、カウンタの特定ビットのオーバーフロー時に割り込みを発生するようにカウンタをプリセットすることにより選択することができる。カウンタ１３６０は、セットライン１３６２上の信号によりセットすることができる。割り込みと割り込みとの間の任意の間隔は、割り込みハンドラーの終りのオーバーフロービット位置をセットすることにより選択できる。ランダム長さの間隔を選択することができる。或いは又、カウンタがカウントダウンレジスタとして実施される場合には、割り込みと割り込みとの間の間隔は、カウンタを選択された値にプリセットすることにより選択できる。ここでは、カウンタは、過少流即ちゼロ値の際に割り込む。
【０１２８】
性能カウンタの公知の実施形態では、割り込みハンドラーは、一般に、この割り込みハンドラーが完了したときに実行されるべき次の命令のプログラムカウンタ（ｐｃ）値にアクセスし、このｐｃ値は、「例外アドレス」又は「復帰ｐｃ」と称されることもある。
しかしながら、このｐｃ値を単に記憶するだけでは、手前の命令がリタイアされた回数を正確に反映しない。特に、命令がリタイアしそして性能カウンタがオーバーフローした場合には、命令が既に実行されている。この場合は、復帰ｐｃは、リタイアされた命令のｐｃ値を反映しない。
【０１２９】
割り込み処理の細部に基づき、復帰ｐｃは、命令ストリームにおいてリタイアにより割り込みが生じた命令の直後の命令であってもよいし、又はフェッチユニット、発生待ち行列及び実行パイプラインの種々の段階における命令の数に動的に基づいて、その後の可変数の命令であってもよい。
それ故、割り込みハンドラー１３８０が復帰ｐｃを単に記録するときは、「リタイア命令」カウンタを用いて各命令に対して記憶されたサンプルカウントは、命令の実行頻度を正確に反映しない。
【０１３０】
図１６に示された例示的な制御流れグラフの部分１４００について考える。５つの基本的ブロック１４０１−１４０５がループに編成され、各基本的ブロックは、単一の命令（１４１０−１４５０）で構成される。基本的ブロックの命令がリタイアするときには、「リタイア」カウンタがオーバーフローし、そして割り込みが発生され、割り込みハンドラーの復帰ｐｃ値が、実行されるべき次の命令となる。
【０１３１】
従って、命令１４２０のリタイアが割り込みを発生するときには、復帰ｐｃ値が命令１４４０であり、同様に、命令１４３０が割り込みを発生するときには、復帰ｐｃ値が、命令１４３０における条件分岐の結果に基づいて命令１４４０又は命令１４５０のいずれかとなる。従って、所与のｐｃ値に対して記録された同じカウントが、多数の先行する命令のリタイアを反映する。例えば、命令１４４０に対して記録された同じカウントは、命令１４２０の全てのリタイアの結果を命令１４３０の幾つかのリタイアに加えたものであり、同様に、命令１４５０に対して記憶されたカウントは、命令１４４０の全てのリタイアの結果を命令１４３０の幾つかのリタイアに加えたものである。一般に、この形式のサンプルデータが与えられると、各命令のリタイア事象の数を明確に決定することは不可能である。
【０１３２】
ここに述べるようにハードウェアを変更することにより、割り込みハンドラー１３８０により記録された情報が、実際にリタイアされる命令のプログラムカウンタ値を含むように確保することができる。本質的な考え方は、カウンタがオーバーフローしそして割り込みを発生するときに、リタイアにより割り込みを発生した正にその命令のプログラムカウンタ値を記録することである。このプログラムカウンタ値は、図１５の内部プロセッサレジスタ（ＩＰＲ）１３７０に記録することができる。ＩＰＲは、例えば、割り込みハンドラー１３８０により実行される特権命令により読み取ることができる。
【０１３３】
プログラムカウンタ値は、多数のやり方でリタイアユニット１３５０に得られるようにすることができる。これらの値は、命令と共に全プロセッサパイプラインを経て搬送することができる。より一般的には、命令がパイプラインを進行するときの命令の識別は、比較的小さな命令番号即ち「ｉｎｕｍ」である。ｉｎｕｍのサイズは、一度にパイプラインに存在することのできる全命令数より大きくなる必要はない。
【０１３４】
図１７に示すように、プログラムカウンタ値１５２０に対して実行命令のｉｎｕｍ識別１５１０をマッピングすることは、テーブル１５００を使用することにより実行できる。リタイアユニット１３５０は、リタイアを待機している命令、即ちパイプラインにある命令のｉｎｕｍ１３５２の待ち行列１３５１を、各命令をいつリタイアできるかを決定するのに使用される他の依存性情報（ＤＥＰ）１３５３と共に維持する。判断は、ロジック１３５４により行われる。命令がリタイアされるときは、そのｉｎｕｍ識別１３５２を用いて、それに対応するｐｃ値１５２０をテーブル１５００から抽出する。このｐｃ値は、次いで、ＩＰＲ１３７０に記憶することができる。
【０１３５】
リタイアカウンタ１３６０がオーバーフローするときにサンプルを記録するために発生される割り込み信号１３６１は、直ちに発生される必要がない。というのは、リタイアされる命令のｐｃ値がＩＰＲ１３７０に得られるからである。この値は、次の割り込みまで変化しない。従って、プロセッサのパイプラインの設計が、リタイアされた命令のｐｃ値を得るのに数サイクルを必要とするようなものであるときには、ｐｃ値がＩＰＲ１３７０に書き込まれた後のある時間に割り込み１３６１を発生することが許される。
【０１３６】
あるプロセッサにおいて、単一のプロセッササイクル中に多数の命令をリタイアすることができる。しかしながら、命令は、通常、「プログラム順序」でリタイアされ、即ちそれらが一度に１つづつ実行される場合に実行される順序でリタイアされる。これは、通常、命令を乱れた順序で発生できるプロセッサにおいても言えることである。
従って、同じプロセッササイクル中に命令のグループがリタイアされて、リタイアカウンタをオーバーフローさせるときには、リタイアする命令の少なくとも１つを、オーバーフローを生じさせた命令として識別できる。例えば、リタイアカウンタは、値Ｘに達したときにオーバーフローにセットされ、プロセッサのリタイアサイクルは、値Ｘ−Ｎでスタートし、そしてそのサイクル中にＫ個の命令がリタイアする。この場合に、Ｋ個の命令のグループにおけるＮ番目の命令は、オーバーフローを生じさせた命令であり、そのｐｃ値は、ＩＰＲ１３７０に記憶されねばならない。
【０１３７】
この技術は、他の種類の事象に対する他の種類の性能カウンタへと拡張することができる。一般に、いかなる事象に対しても、その事象に関連した情報を記録することが望まれ、例えば、その事象を生じた命令のｐｃ値を記録することができ、又はキャッシュにおいてミスしたメモリオペレーションによりアクセスされたデータの仮想アドレスを記録することができる。この付加的なデータのためにＩＰＲ１３７０のセットを維持し、そして適当な事象カウンタがオーバーフローしたときにＩＰＲ１３７０を更新することにより、各個々の命令又はメモリ位置に対して所与の事象のレートを反映するサンプルデータを直接的に得ることができる。
【０１３８】
サンプリングされた実行頻度データの質を改善する方法
ここに述べるハードウェアにより形成されるデータは、ノイズを含む傾向がある。又、データは、潜在的に重大な統計学的変化も含む。これらの変化は、次のような後処理段階において減少することができる。
１．各手順の制御流れグラフにおける基本的ブロックを、上記のように、頻度等価クラスにグループ分けする。稀な環境（例えば、ある手順が別の手順をコールし、これが第３の手順のコードへとジャンプし、第１の手順を終了するとき、又は割り込みが生じて、その割り込まれたコードへ決して復帰しないとき）を除いて、所与の頻度等価クラスにおける全ての基本的ブロックは、プログラムの各実行において同じ回数だけ実行することが保証され、従って、これら基本的ブロックの各々における全ての命令も同じ回数だけ実行する。
２．各々の頻度等価クラスに対し、そのクラスの各命令ごとにサンプルカウントの平均値を得ることにより新たな実行頻度推定値を決定する。
【０１３９】
以上、本発明の好ましい実施形態を詳細に説明したが、特許請求の範囲に規定した本発明の範囲から逸脱せずに種々の変更がなされ得ることが当業者に容易に明らかであろう。
【図面の簡単な説明】
【図１】本発明の好ましい実施形態によるプロファイリングサブシステムにより動作をプロファイリングすることのできるコンピュータシステムのブロック図である。
【図２】プロファイリングサブシステムの流れ線図である。
【図３】プログラムの各命令を発生するのに必要な平均サイクル数を決定するためのプロセスを示すブロック図である。
【図４】実行頻度を推定するプロセスのブロック図である。
【図５】命令の等価クラスを決定するプロセスのブロック図である。
【図６】拡張された制御流れグラフを示す図である。
【図７】初期頻度推定値及びストールサイクルを決定するプロセスを示すブロック図である。
【図８】頻度推定値をローカルに伝播するプロセスのブロック図である。
【図９】制約ソルバーのブロック図である。
【図１０】頻度推定値をグローバルに伝播するプロセスのブロック図である。
【図１１】動的なストールの理由を決定するための流れ線図である。
【図１２】基本的なブロックのキャッシュミスのブロック図である。
【図１３】異なる形式の先行項目ブロックを示すブロック図である。
【図１４】ストールされた命令により参照される手順を示すブロック図である。
【図１５】改良された性能カウンタを含むハードウェアのブロック図である。
【図１６】ループにおいて実行される基本的ブロックを示す図である。
【図１７】プログラムカウンタ値をルックアップするテーブルを含む性能データ収集プロセスのデータ流れ線図である。
【符号の説明】
１００  コンピュータシステム
１１０  中央処理ユニット（ＣＰＵ）
１１１  プロセッサチップ
１１２  カウンタ
１１３  実行ユニット
１２０  メモリサブシステム
１２１  ソフトウェアプログラム
１２２  データ
１３０  入力／出力インターフェイス
１４０  バス
２００  サブシステム
２０１  手順
２０２  基本的ブロック
２０３  制御流れグラフ（ＣＦＧ）
２０４  ノード
２０５  エッジ
２０６  データ構造体
２０９  サンプルカウンタ
２１０  制御流れ分析モジュール
３００  性能データ分析器
３４０  性能データ
【図１】
0004785213.tif 000002
【図２】
0004785213.tif 000003
【図３】
0004785213.tif 000004
【図４】
0004785213.tif 000005
【図５】
0004785213.tif 000006
【図６】
0004785213.tif 000007
【図７】
0004785213.tif 000008
【図８】
0004785213.tif 000009
【図９】
0004785213.tif 000010
【図１０】
0004785213.tif 000011
【図１１】
0004785213.tif 000012
【図１２】
0004785213.tif 000013
【図１３】
0004785213.tif 000014
【図１４】
0004785213.tif 000015
【図１５】
0004785213.tif 000016
【図１６】
0004785213.tif 000017
【図１７】
0004785213.tif 000018