JPH11272520A - プロセッサパイプラインにおいて多数の潜在的に同時の命令をサンプリングする装置 - Google Patents

Abstract

(57)【要約】 【課題】 プロセッサパイプラインにおいて多数の潜在
的に同時の命令をサンプリングする装置を提供する。 【解決手段】 システムのプロセッサパイプラインにお
いて多数の同時実行命令をサンプリングする装置が提供
される。パイプラインは、複数の処理段を有している。
この装置は、命令がパイプラインの第１段へフェッチさ
れるときに選択される多数の命令を識別する。多数の選
択された命令のサブセットは、パイプラインにおいて同
時に実行される。多数の選択された命令のいずれかがパ
イプラインのいずれかの段にある間にシステムの状態情
報がサンプリングされる。全ての選択された命令がパイ
プラインを出るときにソフトウェアに通知がなされ、従
ってソフトウェアは、いずれの状態情報も読み取ること
ができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般に、コンピュ
ータシステムの性能測定に係り、より詳細には、多数の
同時実行命令をサンプリングすることに係る。

【０００２】

【従来の技術】コンピュータプロセッサは、益々高速に
なっているが、ソフトウェアアプリケーションの性能
は、それに歩調が合っていない。大型の商業用途の場合
に、命令当たりの平均プロセッササイクル（ＣＰＩ）値
が２．５ないし３という大きさである。４ウェイ命令イ
ッシュープロセッサでは、ＣＰＩが３であることは、１
２ごとに１つのイッシュースロットしか良好に使用され
ないことになる。ソフトウェアスループットがハードウ
ェアの改良となぜ歩調が合わないかを理解することが重
要である。このような問題をメモリの待ち時間に転嫁す
るのが一般的であり、実際に、多くのソフトウェアアプ
リケーションは、データ転送が完了するのを待機して多
数のサイクルを費やす。しかしながら、分岐予想ミスの
ような他の問題も、プロセッササイクルを浪費する。一
般的な原因とは独立して、システムアーキテクチャー並
びにハードウェア及びソフトウェアエンジニアは、複雑
なプロセッサを組み込んだ近代的なコンピュータシステ
ムの性能を改善するために、どの命令がストールしてい
るかそしてなぜかを知る必要がある。

【０００３】通常、これは、システムが動作している間
にその振る舞いの「プロファイル」を発生することによ
り行われる。プロファイルとは、性能データの記録であ
る。しばしば、プロファイルは、性能のボトルネックを
容易に識別できるようにグラフ的に発生される。プロフ
ァイル形成は、計装及び模擬により行うことができる。
計装では、プログラムの実行中に特定事象を監視するた
めにプログラムに付加的なコードが追加される。模擬
は、実際のシステムでプログラムを実行するのではな
く、人為的な環境においてプログラム全体の振る舞いを
エミュレートするように試みる。これら２つの方法は、
各々、欠点を有する。計装は、追加命令及び余計なデー
タ参照のためにプログラム真の振る舞いを擾乱させる。
模擬は、実際のシステムにおいてプログラムを実行する
場合に比して実質的な性能オーバーヘッドを犠牲にして
擾乱を回避する。更に、計装又は模擬では、大規模なソ
フトウェアシステム全体、即ちアプリケーション、オペ
レーティングシステム及びデバイスドライバコードをプ
ロファイリングすることが通常困難である。

【０００４】プロセッサのプロファイル情報を与えるた
めに、ハードウェア実施の事象サンプリングを使用する
こともできる。ハードウェアサンプリングは、模擬及び
計装に勝る多数の効果を有し、即ち性能を測定するため
にソフトウェアプログラムを変更する必要がない。サン
プリングは、比較的低いオーバーヘッドで全システムに
作用する。実際に、最近では、低いオーバーヘッドのサ
ンプリングをベースとするプロファイリングを使用し
て、パイプラインストール及びそれらの原因に関する詳
細な命令レベル情報を収集することができる。しかしな
がら、多くのハードウェアサンプリング技術は、特定の
事象を測定するように設計されているので融通性に欠け
る。デジタル社のＡｌｐｈａ ＡＸＰ２１１６４、イン
テル社のペンティウイム・プロ及びＭＩＰＳ１００００
は、データキャッシュ（Ｄキャッシュ）ミス、命令キャ
ッシュ（Ｉキャッシュ）ミス及び分岐予想ミスのような
種々の事象をカウントすることのできる事象カウンタを
形成する。これらの事象カウンタは、カウンタがオーバ
ーフローするときに割り込みを発生し、従って、カウン
タの性能データを高レベルのソフトウェアでサンプリン
グすることができる。

【０００５】事象カウンタは、特定のプログラム又はそ
の一部分を実行する間にシステムが招いた分岐予想ミス
の数のような集合情報を捕獲するのに有用である。しか
しながら、既知の事象カウンタは、どの分岐命令が頻繁
に予想ミスを生じるかのように状態情報を個々の命令に
帰属させる点で有用性が低い。これは、事象カウンタが
オーバーフローしそして割り込みを生じるときには、そ
の事象を生じた命令のプログラムカウンタ（ＰＣ）がも
はや使用できないためである。命令をアウトオブオーダ
ー（順序ずれして）でイッシューすることのできるプロ
セッサの動的なオペレーションを推測することが特に問
題である。実際に、アウトオブオーダープロセッサで実
行されるソフトウェアプログラムの振る舞いは極めて不
可解で且つ理解が困難である。その具体的な例としてア
ウトオブオーダーのＡｌｐｈａ２１２６４プロセッサで
の命令の流れについて考える。

【０００６】スーパースカラープロセッサアーキテクチ
ャー 実行順序 アウトオブオーダープロセッサは、命令を正しい順序で
フェッチしそしてリタイアするが、命令をそれらのデー
タ依存性に基づいて処理する。命令の処理は、レジスタ
のマッピング、命令の発生及び実行を含む。命令は、そ
れがフェッチされたときから、それがリタイア又はアボ
ートするときまで、「フライト中」であると言える。各
プロセッササイクル中に、プロセッサパイプラインの第
１段は、命令キャッシュ（Ｉキャッシュ）から命令のセ
ットをフェッチする。命令のセットはデコードされる。
命令デコーダは、フェッチされたセットのどの命令が命
令流の一部分であるかを識別する。

【０００７】フェッチすべき次の命令のＰＣを分析する
には多数のサイクルを要するので、ＰＣは、通常、分岐
又はジャンププレディクタ（予想子）により前もって予
想される。予想を誤ったときには、プロセッサは、「不
良」実行経路を占有する予想ミス命令をアボート（中
止）し、そして「良好」経路において命令のフェッチを
再スタートする。命令を順序ずれ状態で実行できるよう
にするために、命令のオペランドに指定されたレジスタ
は、「読み取り後の書き込み」及び「書き込み後の書き
込み」競合を防止するように動的に名前を付け直され
る。この名前の付け直しは、アーキテクチャー即ち「仮
想」レジスタを物理的レジスタへとマッピングすること
により達成される。従って、同じ仮想レジスタに書き込
む２つの命令は、それらが異なる物理的レジスタに書き
込みそして仮想レジスタの消費者が適切な値を得るの
で、順序ずれ状態で安全に実行することができる。

【０００８】レジスタマップ型命令は、そのオペランド
が計算されそして適当な形式の機能的「実行」ユニット
が得られるまで、イッシュー待ち行列に存在する。命令
によって使用される物理的なレジスタは、命令がイッシ
ューされるサイクルで読み取られる。命令は、それらが
実行された後に、リタイアの準備ができたとマークさ
れ、そしてプログラム順序における全ての手前のリタイ
ア準備命令がリタイアしたときに、即ち命令が正しいプ
ログラム順序でリタイアするときに、プロセッサにより
リタイアされる。リタイアの際に、プロセッサは、命令
によりなされる変更をシステムのアーキテクチャー「状
態」へコミットし、そして命令により消費されたリソー
スを解除する。

【０００９】予想ミス 分岐が誤って予想されるようなある場合には、命令をト
ラップし又は破棄しなければならない。これが生じたと
きには、現在の推測的な構造状態が、予想ミスが生じた
実行点へと戻され、正しい命令においてフェッチが続け
られる。

【００１０】遅延 多数の事象が命令の実行を遅らせる。パイプラインの前
方において、フェッチユニットは、Ｉキャッシュミスの
ためにストールするか、又はフェッチユニットは、予想
ミスのために不良経路に沿って命令をフェッチすること
がある。マップ手段は、空いた物理的レジスタが欠乏す
るか、又はイッシュー待ち行列に空きスロットが欠乏す
るためにストールすることがある。イッシュー待ち行列
の命令はそれらのレジスタ依存性が満足されるか又は機
能的実行ユニットが使用できるようになるのを待機す
る。命令は、データキャッシュミスによりストールする
ことがある。命令は、それらが不良経路を下るように推
測的に発生されるか、又はプロセッサが割り込みを行っ
たためにとラップされることがある。これら事象の多く
は、例えば、コードの検査により静的に予想することが
困難であり、それらは全てシステムの性能を低下させ
る。この形式の状態情報を捕獲するのに単純な事象カウ
ンタでは不充分である。加えて、遅延の長さを厳密に測
定して、どの遅延に特に注目すべきかを決定することは
困難である。

【００１１】プログラマー又は最適化ツールが、スーパ
ースカラー及びアウトオブオーダープロセッサ、又はこ
の点については任意のアーキテクチャー設計のプロセッ
サのような複雑なコンピュータシステムのソフトウェア
及びハードウェア要素の性能を改善できるように、事象
を特定の命令及びマシン状態に直接的に帰属させること
が強く望まれる。

【００１２】

【発明が解決しようとする課題】公知の事象カウンタに
伴う問題 既知の事象カウンタに伴う主な問題は、カウンタをオー
バーフローさせた事象を生じさせた命令が、通常は、例
外的ＰＣよりかなり前にフェッチされることであり、即
ち、このＰＣは、オーバーフローを生じさせた命令のも
のではない。フェッチと割り込みとの間の遅延の長さ
は、一般に、予想できない量である。この予想できない
事象分布は、事象を特定の命令に適切に帰属させること
を困難にする。順序ずれ及び予測的実行は、この問題を
増幅するが、これは、Ａｌｐｈａ２１１６４プロセッサ
のようなインオーダー（順序正しい）マシンにも存在す
る。例えば、Ａｌｐｈａ２１１６４（インオーダー）プ
ロセッサ対ペンチウム・プロ（アウトオブオーダー）プ
ロセッサに対してＤキャッシュ基準事象カウントを監視
しながら、性能カウンタ割り込みハンドラーに与えられ
るプログラムカウンタ値を比較する。例示的プログラム
は、ランダムメモリアクセス命令、例えば、ロード命令
と、それに続く、ナルオペレーション命令（ｎｏｐ）の
ハンドラーとを含むループより成る。

【００１３】インオーダー型のＡｌｐｈａプロセッサで
は、全ての性能カウンタ事象（例えば、キャッシュミ
ス）は、事象の６サイクル後に実行される命令に帰属さ
れ、ロードアクセス後の７番目の命令においてサンプル
の大きなピークを生じる。このスキューした事象分布
は、理想的なものではない。しかしながら、単一の大き
なピークがあるために、静的な分析は、時々、このピー
クから後方に作用し、その事象を生じさせた実際の命令
を識別することができるが、これは、非常に単純なプロ
グラムに対する最良の推測以上のものは何もない。アウ
トオブオーダー型のペンティウム・プロで実行される同
一のプログラムの場合に、事象サンプルは、次の２５個
の命令にわたって広く分布され、スキューを示すだけで
なく、著しい不鮮明さも示す。サンプルの広い分布は、
特定の事象を、その事象を生じた特定の命令に帰属させ
るのをほぼ不可能にする。他のハードウェア事象をカウ
ントするときにも同様の振る舞いが生じる。

【００１４】スキュー又は不鮮明さのある事象サンプル
分布に加えて、従来の事象カウンタは、付加的な問題で
悩まされている。通常、事象カウンタより多くの当該事
象があり、全ての当該事象を同時に監視することは、不
可能でないまでも、困難である。プロセッサの複雑さが
増すと、この問題が一層悪化する。加えて、事象カウン
タは、事象が発生したという事実しか記録せず、その事
象に関する付加的な状態情報を与えない。多数の種類の
事象に対し、キャッシュミス事象にサービスする待ち時
間のような付加的な情報が極めて有用である。更に、公
知のカウンタは、一般に、事象をコードの「ブラインド
スポット」に帰属させることができない。ブラインドス
ポットとは、割り込み権が与えられるまで事象が確認さ
れないために、高優先順位システムルーチン及びＰＡＬ
コードのような割り込み不能コードである。そのときま
でに、プロセッサの状態は著しく変化し、おそらく偽の
情報を与える。

【００１５】ストール対ボトルネック パイプライン式のインオーダープロセッサにおいて、パ
イプライン段で１つの命令がストールすると、その後の
命令がそのパイプライン段に通過することが妨げられ
る。それ故、インオーダープロセッサでは「ボトルネッ
ク」命令を識別することが比較的容易であり、即ちボト
ルネック命令は、パイプラインのどこかでストールする
傾向がある。インオーダープロセッサの場合、命令が各
パイプライン段を通るときにその待ち時間を測定し、そ
してその測定された待ち時間を、各パイプライン段にお
けるその命令の理想的な待ち時間と比較することによ
り、ストールを識別することができる。命令は、ある段
を通過する最小待ち時間より長い時間を必要とするとき
に、その段においてストールしたと仮定することができ
る。

【００１６】しかしながら、アウトオブオーダープロセ
ッサでは、あるパイプライン段でストールした命令に対
して他の命令がそのパイプライン段を通過することがあ
る。実際に、ストールした命令の付加的な待ち時間は、
他の命令の処理によって完全にマスクされ、実際に、ス
トールした命令は、観察されるプログラム完了を遅延し
ないことがある。インオーダーシステムにおいても、あ
るパイプライン段のストールは、別のパイプライン段が
ボトルネックであるときにはプログラムの全実行時間に
影響しない。例えば、メモリ集中のプログラムの実行中
には、Ｄキャッシュミスにより遅延される実行ユニット
からの「バックプレッシャー」のために、命令パイプラ
インのフェッチ手段及びマップ手段がしばしばストール
することがある。

【００１７】理想的には、キャッシュミスを生じるメモ
リオペレーションを一次ボトルネックとして分類する。
フェッチ手段及びマップ手段のストールは、実際には、
キャッシュミスによる遅延の非兆候状態であり、即ち二
次ボトルネックである。ストールが他の命令によりマス
クされない命令を識別し、そしてそれらを真のボトルネ
ックとして識別することが望ましい。更に、プログラム
の振る舞いを改善するためには、非兆候（二次）ボトル
ネックよりもカジュアル（一次）のボトルネックに焦点
を合わせることが必要である。このようにパイプライン
段のボトルネックをカジュアル及び非兆候と分類するこ
とは、パイプラインの状態並びにフライト中命令のデー
タ及びリソース依存性を詳細に知ることが必要である
が、これらは、良く知られたように、単純な事象カウン
タから得ることができない。

【００１８】１９９２年９月２９日付のウェスコット氏
等の「命令サンプリング手段(Instruction Sampling In
strumentation)」と題する米国特許第５，１５１，９８
１号は、アウトオブオーダーの実行マシンにおいて命令
ベースのサンプリングを行うハードウェアメカニズムを
提案している。ウェスコット氏等の解決策には多数の欠
点がある。第１に、この解決策は、サンプリングされる
コードの長さ及びサンプリングレートに基づいて命令サ
ンプルの流れをバイアスし得る。第２に、このシステム
は、リタイアした命令のみをサンプリングし、フェッチ
した全ての命令をサンプリングするのではなく、その幾
つかがアボートされる。第３に、ウェスコット氏等のメ
カニズムにより収集される情報は、例えば、キャッシュ
ミスのような個々の事象属性に集中するが、命令間の関
係を決定するための有用な情報を与えるものではない。

【００１９】最近、「ロード通知(informing loads) 」
と称するハードウェアメカニズムが提案されている。こ
れについては、１９９６年５月２２日のプロシーディン
グズ第２３アニュアルインターナショナルシンポジウム
・オン・コンピュータアーキテクチャー、第２６０−２
７０ページに掲載されたホロイッツ氏等の「インフォー
ムドメモリオペレーション：近代的なプロセッサにおけ
るメモリ性能フィードバックの供給(Informed memory o
perations: Providing memory performance feedback i
n modern processors)」を参照されたい。この場合は、
メモリオペレーションに続いて、そのメモリオペレーシ
ョンがキャッシュにおいてミスした場合及びその場合に
のみ条件分岐オペレーションを行うことができる。プロ
ファイリングについては特に設計されていないが、この
メカニズムは、特にＤキャッシュミスの事象情報のみを
収集するのに使用できる。

【００２０】キャッシュミスルックアサイド（ＣＭＬ）
バッファと称する他の特殊なハードウェアにおいては、
高いレベル２のキャッシュミスレートに悩まされる仮想
メモリページが識別される。この詳細な説明について
は、１９９４年１０月４日のプロシーディングズ・オブ
・ザ・シックスス・インターナショナルコンファレンス
・オン・アーキテクチャルサポート・フォア・プログラ
ミングランゲッジ・アンド・オペレーティングシステ
ム、第１５８−１７０ページに掲載されたバーシャド氏
等の「大型の直接マップ式キャッシュにおける競合ミス
の動的な回避(Avoiding conflict misses dynamically
in large direct-mapped caches)」を参照されたい。イ
ンテル社のペンティウムのようなプロセッサは、分岐プ
レディクタの分岐ターゲットバッファ（ＢＴＢ）の内容
をソフトウェアで読み取ることができる。ソフトウェア
でＢＴＢを周期的に読み取ることにより、コンテ氏等
は、プログラムの限界実行頻度を推定するための非常に
オーバーヘッドの低い技術を開発した。これについて
は、１９９４年１１月３０日のプロシーディングズ・オ
ブ・第２７アニュアルインターナショナルシンポジウム
・オン・マイクロアーキテクチャ、第１２−２１ページ
に掲載された「プロファイル駆動の最適化をサポートす
るための分岐ハンドリングハードウェアの使用(Using b
ranch handling hardware tosupport profile-driven o
ptimization) 」を参照されたい。

【００２１】この解決策は、関連サンプリング情報を記
憶する「プロファイル記録」に含まれた分岐方向情報を
追跡することにより得られるものと同様の情報を形成す
る。最近、コンテ氏等は、分岐が実行される回数及び実
行されない回数をカウントするプロファイルバッファと
称する付加的なハードウェアの断片を提案している。こ
れについては、１９９６年１２月２日のプロシーディン
グズ・オブ・第２９アニュアルインターナショナルシン
ポジウム・オン・マイクロアーキテクチャー、第３６−
４５ページに掲載された「プロファイルバッファを使用
する正確且つ実際的なプロファイル駆動の編集(Accurat
e and practical profile-driven compilation using t
he profile buffer)」を参照されたい。

【００２２】

【課題を解決するための手段】本発明によれば、プロセ
ッサのオペレーションを測定するための装置及び方法で
あって、従来のメカニズムとは異なる装置及び方法が提
供される。事象をカウントし、そして事象カウンタがオ
ーバーフローしたときにプログラムカウンタをサンプリ
ングするのではなく、本発明の装置及び方法は、命令を
ランダムに選択し、そしてその選択された命令に対して
詳細な状態情報をサンプリングすることに依存する。周
期的に、プロセッサの動作中に、プロファイリングされ
るべき命令がランダムに選択され、そして命令の実行中
に何が起きたかのプロファイル記録がプロセッサの内部
プロファイルレジスタのセットに累積される。選択され
た命令の処理が終了し、例えば、命令がリタイアし、ア
ボートし又はトラップした後に、割り込みが発生され
る。パイプラインにおいて命令がいかに処理されたかの
詳細を特徴付ける記録情報を内部プロファイルレジスタ
からソフトウェアによりサンプリングすることができ
る。

【００２３】プロファイルレジスタは、命令の実行に関
する多数の有用な事実を記録することができる。性能情
報は、例えば、選択された命令が実行パイプラインの各
段において費やしたサイクルの数、即ち段の待ち時間、
命令がＩキャッシュ又はＤキャッシュミスを受けたかど
うか、メモリオペランドの有効アドレス又は分岐／ジャ
ンプターゲット、そして命令がリタイア又はアボートさ
れたかどうかを含むことができる。順序正しく実行する
（インオーダー型）プロセッサにおいては、サンプルさ
れた命令のフェッチ−リタイア待ち時間が与えられたと
きに各命令に起因する全ストールサイクル数を推定する
ことができる。これは、１つのストールした命令が別の
ストールした命令とオーバーラップすることがないの
で、ボトルネックを識別するのに充分である。

【００２４】順序ずれして実行する（アウトオブオーダ
ー型）プロセッサにおいては、ほとんどのストールがお
そらくオーバーラップし、そしてそのストールした命令
の周りで順序ずれして発生される他の命令によりマスク
される。これは、ストールした命令の識別を困難なもの
にする。更に、ボトルネックを識別するためには、各命
令が実行される間に同時性の平均レベルに関する情報を
収集することが必要となる。特殊目的のハードウェア
は、プロファイリングされた命令が実行される間に発生
する命令の数をカウント及び記録して、同時実行のレベ
ルを測定することができる。しかしながら、これは、発
生するがアボートされ、従って、リタイアしない命令を
考慮に入れるものではない。そこで、有用な同時性の量
の測定値が与えられる。有用な同時性は、並列に発生し
そして所与の命令で首尾良くリタイアする命令の平均数
である。発生するがその後にアボートされる命令は、有
用ではない。従って、ストールが有用な同時性によりマ
スクされない命令をボトルネックとして分類することが
できる。この別の方法を説明するために、アウトオブオ
ーダープロセッサにおいて性能ボトルネックの位置を正
確に示すための重要なメトリックは、所与の命令が実行
される間に費やされた発生スロットの数である。

【００２５】従って、有用な同時性を測定するために、
「対ごとのサンプリング(pair-wisesampling)」と称す
る技術が提供される。基本的な考え方は、ネスト形態の
サンプリングを実行することである。ここでは、第１の
プロファイリングされた命令と同時に実行できる命令の
ウインドウが動的に定義される。命令のウインドウから
プロファイリングするために第２の命令がランダムに選
択される。プロファイリングされた及び第２の命令は、
プロファイル情報を収集できるところのサンプル対を形
成する。対ごとのサンプリングは、各命令に起因する費
やされた発生スロットの数を容易に決定すると共に、ボ
トルネックの位置を既知の技術よりもかなり正確に指示
する。一般に、対ごとのサンプリングは、非常に融通性
があり、種々様々な当該同時性及び利用メトリックを決
定することのできる分析の基礎を形成する。

【００２６】より詳細には、プロセッサのパイプライン
により処理される１つ以上の命令を周期的に且つランダ
ムに選択し、そして実行パイプラインの段を経て命令が
進行する間にプロファイル情報を収集するための装置及
び方法が提供される。高レベルのソフトウェアは、次い
で、この情報を種々の仕方で後処理することができ、例
えば、同じ命令の多数の実行から情報を収集することに
より後処理することができる。捕獲することのできる情
報は、例えば、命令のアドレス（プログラムカウンタ即
ちＰＣ）、命令が命令キャッシュミスを受けたかどう
か、及びミスにサービスするために被る待ち時間を含
む。命令がメモリオペレーションを実行する場合には、
命令がデータキャッシュミスを受けたかどうか決定し、
そしてメモリ要求を満足するための待ち時間を測定す
る。更に、命令が各パイプライン段において費やす時間
の長さを測定することができる。又、プロファイル情報
は、命令がリタイアしたかアボートしたかを指示すると
共に、後者の場合には、どんな種類のトラップが命令の
実行をアボートしたかも指示することができる。

【００２７】命令が実行パイプラインを経て進行すると
きにプロファイリングレジスタのセットに情報が収集さ
れる。命令の実行が終了すると、それがリタイアするか
又はアボートするために、上位レベルのソフトウェアに
割り込みが与えられる。次いで、ソフトウェアは、プロ
ファイリングレジスタに存在する情報を種々の方法で処
理することができる。サンプリングされる性能情報は、
プロファイルで指示される最適化にとって非常に有用で
あるが、事象の発生を集合的にカウントするようなハー
ドウェア事象カウンタとしても多数の使い方がある。こ
こに開示する技術は、既存の性能監視ハードウェアに対
する改良であり、そして命令を順序ずれして発生できる
近代的なマイクロプロセッサにおいて比較的低いハード
ウェアコストで効率的に実施することができる。

【００２８】より詳細には、システムのプロセッサパイ
プラインにおいて多数の同時実行命令をサンプリングす
るための装置が提供される。パイプラインは、複数の処
理段を有する。この装置は、パイプラインの第１段へ命
令がフェッチされたときに選択される多数の命令を識別
する。多数の選択された命令のサブセットは、パイプラ
インにおいて同時に実行される。多数の選択された命令
のいずれかがパイプラインのいずれかの段にある間にシ
ステムの状態情報がサンプリングされる。全ての選択さ
れた命令がパイプラインを出るときにソフトウェアに通
知して、ソフトウェアがいずれの状態情報も読み取れる
ようにする。

【００２９】

【発明の実施の形態】システムの概要 図１は、ここに開示するサンプリング方法及び装置を使
用することのできるコンピュータシステム１００を示
す。このシステム１００は、バスライン１４０で接続さ
れた１つ以上のプロセッサ１１０、オフチップメモリ１
２０及び入力／出力インターフェイス（Ｉ／Ｏ）１３０
を備えている。プロセッサ１１０は、例えば、デジタル
イクイップメント社のＡｌｐｈａ２１２６４プロセッサ
のように、集積半導体チップにおいて、機能的実行ユニ
ットを含む多数の実行パイプライン１１１、命令キャッ
シュ（Ｉキャッシュ）１１２及びオンチップデータキャ
ッシュ（Ｄキャッシュ）１１３として実施することがで
きる。又、プロセッサチップ１１０は、以下に詳細に述
べるように、選択された命令に対してプロセッサ状態を
サンプリングするためのハードウェア１１９も備えてい
る。オフチップメモリ１２０は、汎用キャッシュ（Ｂキ
ャッシュ又はＳＲＡＭ）１２１と、揮発性メモリ（ＤＲ
ＡＭ）１２２と、永続的メモリ（ディスク）１２３とを
含むハイアラーキー構成をとることができる。Ｉ／Ｏ１
３０は、システム１００に対してデータを入力及び出力
するのに使用できる。

【００３０】オペレーション システム１００のオペレーション中に、ソフトウェアプ
ログラムの命令及びデータがメモリ１２０に記憶され
る。命令及びデータは、既知のコンパイラー、リンカー
及びローダー技術を使用して従来のやり方で発生され
る。命令及びデータは、キャッシュ１１２−１１３を経
て１つのプロセッサ１１０の実行パイプライン１１１に
転送される。パイプラインにおいて、命令が実行のため
にデコードされる。ある命令は、データに作用する。他
の命令は、プログラムの実行流を制御する。命令を実行
しながら詳細な性能データを収集することが所望され
る。性能データは、メモリオペレーション及び実行流に
関連付けることができる。

【００３１】プロセッサパイプライン 図２ａは、図１の１つのプロセッサ１１０の実行パイプ
ライン２００を示すもので、これは、例えば、フェッ
チ、マップ、イッシュー、実行及びリタイアユニット、
各々、２１０、２２０、２３０、２４０及び２５０とし
てシリアルに構成された複数の段を有する。パイプライ
ン２００が情報（データ及び命令）を処理するレート
は、ライン２０１上のシステムクロック信号、即ちいわ
ゆるクロック「サイクル」により制御される。各クロッ
クサイクルは、パイプライン２００の段が個々の量の処
理を実行できるときの「スロット」即ち時間間隔を定義
する。処理スロットは、通常、順方向命令を搬送し、そ
して以下に述べる実行ユニットの場合は、以下一般に
「データ項目」と称するデータを搬送する。例えば、分
岐予想ミス又はキャッシュミス或いはパイプラインスト
ールのような場合には、クロックはサイクルを続ける
が、有意義な命令は順方向に送られない。

【００３２】１つの効果として、本発明の装置及び方法
は、「廃物(garbage) 」即ち非有効データを搬送するプ
ロセッサスロットに関する状態情報をサンプリングする
ことができる。これらは、「浪費(wasted)」スロットと
して知られている。浪費スロットを識別しそしてサンプ
リングすることは、タスクを最適化するための重要な先
駆手段である。というのは、浪費スロットは、有効に機
能せず、従って、システム性能を低下するからである。
それ故、一般に、ここでサンプリングされるものは、公
知技術のように単なる「事象」又は「命令」ではなく、
プロセッサスロットが有効な命令に関連したものである
か無効の命令に関連したものであるかに関わりなくパイ
プライン２００を経てプロセッサスロットをプッシュす
ることに関連した状態情報をである。

【００３３】フェッチユニット Ｂキャッシュ１２１は、データ項目を各々Ｉキャッシュ
１１２及びＤキャッシュ１１３に転送する。フェッチユ
ニット２１０は、仮想アドレスを物理的アドレスへと解
析するためのある形式の変換ルックアサイドバッファ
（ＴＬＢ）２０５を使用して、実行されるべき次の命令
をＩキャッシュ１１２からフェッチする。Ｉキャッシュ
１１２からフェッチされる項目は、一般的に、実行可能
な命令である。しかしながら、これらは、Ｉキャッシュ
が「廃物」データ即ち非命令をミスする場合のように、
無効命令でもよい。単一のプロセッササイクル中に「命
令」のセットがフェッチされるのが好ましい。このセッ
トは、例えば、４つの命令を含むことができる。換言す
れば、パイプライン２００は、４スロット巾である。ス
ロットの数は、使用可能な実行ユニットの数に基づく。
他の形式のプロセッサは、単一プロセッササイクル中に
より少数の又はより多数の命令をフェッチすることがで
きる。一般に、これは、各サイクルがキャッシュから４
つの処理スロットを満たすことを意味する。あるスロッ
トは、Ｉキャッシュ１１２が使用可能なデータをもたな
いときに浪費される。全ての処理を休止、停止するので
はなく、スロットはいかなる場合にも順方向に搬送され
て、サンプリングの目的で使用できるようにされるが、
スロットの廃物「命令」は、実行のために発生されるこ
とがない。フェッチ中に、選択された命令は、サンプリ
ング又はシステムプロファイリングを許すために付加的
な情報で増強することができる。増強命令は、図４を参
照して以下に説明する。他の実施においては、選択され
た命令の増強が、イッシューユニット２３０を含むプロ
セッサのいかなる段でも実行できることに注意された
い。

【００３４】マップユニット システム１００では、パイプライン２００の次の段のマ
ップユニット２２０を用いて命令のオペランドが物理的
レジスタに動的に指定又は「マップ」される。マップユ
ニットは、物理的レジスタをアーキテクチャー即ち「仮
想」レジスタに指定する。換言すれば、仮想レジスタと
物理的レジスタとの間には１対１の対応がなくてもよ
い。

【００３５】イッシューユニット 次の段において、フェッチされた命令は、イッシューユ
ニット２３０によって順序付けされる。イッシューユニ
ット２３０は、実行されるべき次の命令のための待ち行
列ヘッド(a head-of-the-queue) エントリ２３１を有す
るイッシュー待ち行列を備えている。命令に必要なリソ
ースが使用できないために、イッシューユニット２３０
の１つ以上の命令がストールされ得ることに注意された
い。それ故、ストールされた命令の「周り」で待ち行列
２３０から他の保留中命令が順序ずれして発生される。
正しい実行順序は、以下に述べるリタイアユニット２５
０で確認される。

【００３６】実行ユニット 命令は、機能的実行ユニット（Ｅ０・・・Ｅ３）２４１
及びｌｄ／ｓｔユニット２４２へ発生される。実行ユニ
ット２４１の各々は、特定形式のオペレータコード（ｏ
ｐコード）、例えば、整数及び浮動小数点演算、分岐及
びジャンプ命令等で命令を取り扱うように設計される。
ｌｄ／ｓｔユニット２４２は、メモリアクセス命令を実
行し、例えば、Ｄキャッシュ１１３に対してデータをロ
ード及び記憶する。ｌｄ／ｓｔユニット２４２は、長い
遅延を経験するために特別に識別される。又、長い待ち
時間を伴うメモリアクセス命令は、スループットを改善
するために、データがプロセッサに送り込まれるかなり
前に「完了」となる。

【００３７】リタイアユニット 命令の実行の終了は、リタイアユニット２５０により処
理される。リタイアユニット２５０は、処理状態をコミ
ットする。ある命令は、アボートするか、又はとラップ
されることに注意されたい。例えば、実行流は、命令が
フェッチされた後に変化するか、又は命令は、例外トラ
ップを被ることがある。このような場合に、パイプライ
ンに既にある命令及び全ての後続命令は破棄され、そし
て推測的処理状態がロールバックされる。ここでの１つ
の効果として、破棄又は「アボート」された命令も、浪
費プロセッサスロットと同様にプロファイリングされ
る。換言すれば、終了とは、完全に実行された有効命令
をリタイアし、部分的に実行された有効命令を後処理
し、或いは無効命令又は浪費スロットを破棄することを
意味する。

【００３８】本発明の技術の根底にある基本的な考え方
は、パイプライン２００の段を経て進むときに、選択さ
れた「スロット」、主として命令において「データ項
目」の処理を行うものである。プロファイリングハード
ウェアは、詳細な状態情報を動的に収集する。状態情報
は、いずれのパイプライン段からでも又はシステム１０
０のどこからでも到来することができ、例えば、第１及
び第２レベルキャッシュ又は他のサブシステムから到来
することができる。状態情報は、特定事象に直接起因し
得る。ここでの設計戦略は、プロファイル記録において
静的に決定することが困難な情報を収集することであ
る。これは、プロファイル記録を性能ツールとして又は
プロファイルで指令される最適化として有用なものにす
るか、或いはサンプリング及び分析に直接応答する動的
な調整を含むオペレーティングシステム及びアプリケー
ションレベルソフトウェアにおけるリソース割り当てポ
リシー判断を行う上で有用なものにする。本発明の方法
及び装置は、実際の機能的システムにおいて作用するよ
う設計されることを想起されたい。

【００３９】プロファイル記録の一部分としてセーブす
るのにどんな状態情報に関心があるかを決定するため
に、図２ｂに示すように、近代的なアウトオブオーダー
マイクロプロセッサのパイプライン２００の種々の段に
理論的に得られる情報を検査することが有用である。図
２ｂに示すように、パイプラインの段は、フェッチ２１
０、マップ２２０、イッシュー２３０、実行２４０及び
リタイア２５０である。これらの段のいずれかの間に、
特定の実施形態に基づき、パイプライン２００で処理さ
れるいずれかの「フライト中」命令２０２をライン５１
２によりサンプリングのために選択することができる。
この選択は、カウンタ５１０の値により制御される。カ
ウンタの値は、ライン（ｉｎｉｔ）により初期化するこ
とができる。

【００４０】命令アドレス（ＰＣ）２８１、分岐経過ビ
ット（ＨＩＳＴ）２８２、段の待ち時間２８３、分岐実
行指示（Ｔ）２８７、データアドレス（ＡＤＤＲ）２８
４、データミス（ＭＩＳＳ）２８５及びリタイア状態２
８６のような状態情報は、ライン２８８においてサンプ
リングすることができる。選択された命令の処理が終了
すると、ライン２８９に割り込み信号を発生することが
できる。割り込み信号２８９は、ソフトウェアでライン
２９９を経て状態情報２８１−２８６をサンプリングす
ることができるようにする。或いは又、ソフトウェア
は、内部プロセッサレジスタ５４１を経てライン２８９
をポーリングすることもできる。

【００４１】スーパースカラーのアウトオブオーダープ
ロセッサアーキテクチャー アウトオブオーダー実行プロセッサは、正しい順序で命
令をフェッチ及びリタイアするが、それらのデータ依存
性に基づいて命令を実行する。命令は、それがフェッチ
されたときから、それが終了するまで、例えば、リタイ
ア又はアボートするまで、「フライト中」であると言え
る。命令は、マッピングの後、イッシューユニット２３
０に入れられ、そして入力オペランドを保持するレジス
タが更新されるまでそこで待機する。各プロセッササイ
クルごとに、フェッチユニット２１０は、命令キャッシ
ュ１１２から命令のセットをフェッチしてデコードす
る。フェッチユニット２１０の一部分である命令デコー
ダは、フェッチされたセットの中のどの命令が命令流の
一部分であるかを識別する。フェッチすべき次の命令の
プログラムカウンタ（ＰＣ）を分析するには多数のサイ
クルを必要とするので、次のＰＣは、フェッチユニット
２１０の一部分である分岐又はジャンププレディクタに
より予想される。予想が間違っている場合には、プロセ
ッサは、その予想ミスした命令、即ち「不良」経路にお
いてフェッチされた命令をアボートし、そして「良好」
経路においてフェッチ命令を再スタートする。命令を順
序ずれして実行できるようにするために、レジスタはマ
ップユニット２２０により動的に名前が付け直され、
「読み取り後の書き込み」及び「書き込み後の書き込
み」競合を防止する。同じ仮想レジスタに書き込む２つ
の命令は、順序ずれ状態で安全に実行することができ
る。というのは、それらは、異なる物理的レジスタに書
き込みするのであり、そして仮想レジスタの消費者が適
切な値を得るからである。命令は、正しい順序でフェッ
チされ、マップされそしてリタイアされるが、順序ずれ
状態で実行することができる。

【００４２】レジスタマップユニット２２０は、フェッ
チされた命令のオペランドを有効な物理的レジスタに指
定する。即ち、レジスタオペランドの仮想名は、プロセ
ッサの物理的なレジスタスペースに対して名前付けし直
される。次いで、命令は命令待ち行列２３０へ送られ、
そこで、実行の前に２つの事象を待機する。第１に、そ
れらのレジスタ依存性を分析しなければならない。第２
に、命令に必要なリソース、例えば、実行ユニット、レ
ジスタ、キャッシュポート、メモリ待ち行列等が使用で
きねばならない。これは、現在マップされたいかなる命
令に対しても、必要なリソースを再割り当てできないこ
とを意味する。ある命令に対してこれら２つの条件が満
たされると、命令オペランドが物理的レジスタファイル
において探索される。次いで、オペランドレジスタの内
容及び命令に関するある情報が適当な実行ユニット２４
０へ送られて実行される。命令が実行を終了し、そして
命令がプロセッサにおいて最も古い「非リタイア」命令
であるときに、命令がリタイアする。これは、命令によ
り使用されるリソース、例えば、物理的レジスタ及びキ
ャッシュポートを解放する。

【００４３】多数の事象が命令の実行を遅延させること
がある。パイプラインの前方では、フェッチユニット２
１０がＩキャッシュ１１２のミスによりストールするか
又はフェッチユニット２１０が予想ミス経路の命令をフ
ェッチすることがある。マップユニット２２０は、空き
の物理的レジスタの欠乏、又はイッシューユニット２３
０における空きスロットの欠乏によりストールすること
がある。イッシューユニット２３０における命令は、そ
れらのレジスタ依存性が満足されるのを待機するか、又
は実行ユニット２４０が使用できるのを待機する。命令
は、Ｄキャッシュにおけるミスによりストールすること
がある。命令は、それらが不良経路に沿って推測的に発
生されるか、又はプロセッサが不法なオペレーション又
はメモリアドレスのような割り込みを行ったためにトラ
ップされることがある。これら条件の多くは、コンパイ
ル時に予想することが困難であり、それらは全てシステ
ム１００の性能を低下させる。これにより、ライン２８
８に得られる情報をサンプリングすることが重要とな
る。

【００４４】プロファイル情報レジスタ それ故、図３に示すように、サンプリングされる各命令
ごとにプロファイル情報を記憶するためのメモリ３００
が設けられる。メモリ３００は、レジスタファイル又は
バッファの形態でよい。換言すれば、サンプリングされ
る選択済み命令は、レジスタファイル３００で直接識別
される。レジスタファイル３００は、複数のレジスタを
含むことができる。或いは又、ファイル３００は、多数
のフィールドをもつ単一のインデックス可能なレジスタ
として実施することができる。ファイル３００は、図２
ｂのライン２８８によりパイプライン２００の要素に接
続され、従って、選択された命令に関連した性能情報を
パイプライン２００の各段に対して捕獲することができ
る。プロファイルレジスタ３００は、公知技術で見られ
る単純な「事象」カウンタ以上のものであり、ここで
は、これらレジスタは、特定の既知の命令及び事象に起
因する性能情報を収集することに注意されたい。

【００４５】図３において、各レジスタに対して割り当
てられるビットの数は、そこに記憶される情報の形式、
例えば、命令アドレス（６４ビット）、サイクルカウン
ト、即ち待ち時間（８又は１０ビット）、個別事象（１
ビット／事象）等々に依存している。これらの数は単な
る指針に過ぎない。他の実施形態は、種々のレジスタ３
００に対して異なるビット数を使用することができ、こ
れは設計上の選択肢である。好ましい実施形態では、プ
ロファイルＰＣレジスタ３１０は、選択された命令のＰ
Ｃを記憶する。以下に述べるように、プロファイリング
されている命令は、アサートされた「プロファイル」ビ
ットを有する。又、ＰＣレジスタ３１０は、選択された
命令のｏｐコードを含むこともできる。更に、マルチス
レッド式実行を許すプロセッサについては、レジスタ３
１０の付加的なビットがスレッドの識別子を記憶するこ
とができる。レジスタ３１０の他のフィールドは、プロ
セス識別子、アドレススペース番号、ＣＰＵ番号、及び
実行されている命令の命令番号（ｉｎｕｍ）を記憶する
ことができる。更に、多数の論理レジスタセット、即ち
ハードウェアコンテクスト及び同時実行スレッドを有す
るプロセッサでは、レジスタ３１０がハードウェアコン
テクスト及びスレッド識別子である。この情報を記憶す
ることにより、プロファイル情報を特定の命令に直接起
因させることができる。更に、サンプリングされた情報
は、アドレスの範囲、ｏｐコード、実行スレッド、アド
レススペース、等々に基づいてフィルタすることができ
る。

【００４６】プロファイル有効アドレスレジスタ３２０
には、選択された命令に関連したアドレスがロードされ
る。命令がロード又は記憶のようなメモリアクセス命令
である場合には、有効な６４ビット仮想メモリアドレス
が捕獲される。命令がジャンプ又は分岐である場合に
は、ターゲットＰＣが記録される。本発明のサンプリン
グ技術の１つの効果として、パイプライン２００によっ
て処理される全ての「命令」は、サンプリングレートに
関わりなく、サンプリングのために選択される確率が等
しい。命令は、有効な命令、無効の命令、非割り込み命
令、又は「廃物」命令である。従って、捕獲された有効
アドレスは、プログラムの全体的な振る舞いを統計学的
に表す。サンプリングされた命令の有効アドレスを捕獲
することにより、メモリアクセス及び実行流を、実際の
動的な実行に正確に関連付けることができる。

【００４７】プロファイル事象カウンタ３３０は、例え
ば、１ビットフィールドに区画化される。１ビットフィ
ールドは、選択された命令に対する事象を記録する。命
令が最初に選択されるときに、レジスタがクリアされ
る。事象は、キャッシュミス、分岐予想ミス、リソース
競合、トラップ及び例外条件、リタイア／アボート／無
効、ＴＬＢミス、実行／非実行、データ依存性ストー
ル、リソース依存性ストール、等々を含む。この実施形
態では、多数の事象を単一の命令に起因させることがで
きる。リタイア及びアボートの両命令に対して事象情報
が収集されることに注意されたい。事象レジスタ３３０
のサイズを減少するために、あるビットフィールドを使
用して、命令のｏｐコードに基づき異なる形式の相互に
排他的な事象を記録することができる。

【００４８】プロファイル経路レジスタ３４０は、分岐
経過テーブルから最近の分岐実行／非実行情報を捕獲す
るのに使用される。分岐経過テーブルは、他の用途に対
して良く知られている。グローバルな分岐実行経過は、
選択された命令をフェッチした実行経路を指示するのに
使用できる。命令は、この情報を有効なものにするため
に分岐命令である必要はないことに注意されたい。経路
情報の使用は、以下で詳細に説明する。待ち時間レジス
タ３５０は、選択された命令が、例えば、パイプライン
２００の種々の段間をフライト中である間に、チェック
ポイントにおいて得られたタイミング情報を記憶する。
チェックポイントは、命令がストールされて、ある事象
又はリソースを待機する場所に基づいて、プロセッサご
とに異なる。各待ち時間レジスタ３５０は、２つのチェ
ックポイント間で命令が費やすサイクル数をカウントす
る。

【００４９】選択された命令がチェックポイントを通過
し、即ちパイプライン２００の次の段に入るときに、そ
れに対応する待ち時間レジスタ３５０が最初にクリアさ
れ、そして１サイクル当たり１回増加され、やがて、命
令が次のチェックポイントを通過し、次の待ち時間レジ
スタが初期化されそしてカウントを開始する。待ち時間
レジスタ３５０の数は、特定の実施形態におけるパイプ
ライン２００の段数に基づく。命令がアボート又はリタ
イアするときには、待ち時間レジスタ３５０に完全な待
ち時間プロファイルが記憶される。収集すべき潜在的に
有用な待ち時間のリストは、フェッチ対マップ、マップ
対データレディ、データレディ対実行、実行対リタイア
レディ、リタイアレディ対リタイア遅延を含む。メモリ
命令（ロード及び記憶）の場合、待ち時間は、イッシュ
ー対完了である。この最後の待ち時間は、あるメモリオ
ペレーションは、それらが作用するデータが実際にプロ
セッサに送られる前にリタイアの準備ができるという点
で、他の待ち時間とは異なる。これらの待ち時間は、レ
ジスタ３５０で直接カウントすることもできるし、或い
はレジスタが生のサイクルカウントを収集することもで
き、この場合に、プロファイリングソフトウェアは、次
々の段に対する生のカウント間の差を計算して、実際の
待ち時間を決定する。例えば、パイプライン待ち時間ク
ロックサイクルをカウントする回路は、図６を参照して
以下に詳細に説明する。

【００５０】レジスタ３００における情報の更新は、遅
延が受け入れられた直後に行う必要はない。必要とされ
るのは、選択された命令が完了した（リタイア又はアボ
ートした）ことを知らせる割り込みを、レジスタファイ
ル３００の全ての情報が更新されるまで遅延するか、或
いは割り込みハンドラーを、プロファイルファイル３０
０が更新されるまでストールできるようにすることだけ
である。プロファイルレジスタファイル３００を複写で
きることに注意されたい。プロファイルレジスタファイ
ルの多数のコピーがある場合には、シリアルに又は同時
にプロファイリングするために多数の命令を選択するこ
とができる。この場合には、各選択された命令が、以下
に述べるように、特定のレジスタファイルで明確に識別
される。オーバーヘッドの量を減少するために単一の割
り込み信号に応答して多数のレジスタファイルをサンプ
リングすることができる。

【００５１】増強命令 図４に示すように、各命令４００はサンプルフィールド
を含む。例えば、このサンプルフィールドは、「サンプ
ル」ビット（Ｓ）４０１と称する１ビットタグである。
サンプルビット４０１がアサートされると、サンプリン
グのために命令が選択される。ビット４０１をアサート
すると、プロファイル情報を収集するサンプリングハー
ドウェアが作動されると共に、選択された命令が完了し
た（リタイア又はアボートされた）ときに割り込みを生
じさせる。或いは又、フェッチされた各「命令」を「ｉ
ｎｕｍ」値で連続的に番号付けすることもできる。この
場合には、特定のｉｎｕｍ値をもつ命令を選択すること
ができる。命令を選択するメカニズムについては、以下
に述べる。

【００５２】プロファイルレジスタファイル３００は、
フィールドが更新されそして割り込み信号が発生された
ときに読み取ることができる。割り込み信号は、特権付
きのプロファイリングソフトウェア（ＰＳＷ）がプロフ
ァイルレジスタ３００の内容を処理できるようにする。
多数のサンプルが記録される場合には、単一の割り込み
で、多数の選択された命令に対して性能データをサンプ
リングできることに注意されたい。実施形態に基づき、
増強命令４００は、次の付加的なフィールド、即ち３つ
までの命令オペランド（ｏｐ１、ｏｐ２及びｏｐ３）４
１１−４１３と、プログラムカウンタ（ＰＣ）４２０
と、オペレータコード（ｏｐコード）４３０とを含むこ
とができる。有効フィールド（Ｖ）４３１は、１ビット
フィールドを真又は偽にセットすることにより、選択さ
れたスロットにおける「命令」が有効であるかどうか指
示することができる。フィールド４４０及び４５０は、
命令に関連したＩキャッシュ及びＴＬＢミスを各々指示
するために指定することができる。単一の命令が多数の
オペランドを含み得るので、その命令に対して多数のミ
スが考えられることに注意されたい。

【００５３】プロファイルレジスタファイルＩＤ 若干複雑な設計では、多数の命令を同時にプロファイル
することができる。この実施形態では、複数のレジスタ
ファイル３００、或いはサブフィールドを伴う単一の大
きなレジスタがあり、ファイル３００の数は、同時にプ
ロファイルすることのできるフライト中命令の数に対応
する。このケースを取り扱うために、命令４００は、サ
ンプルレジスタファイル識別子（ＩＤ）フィールド４０
２も含むように増強される。これは、多数のレジスタフ
ァイル３００の１つにプロファイル情報を直接リンクで
きるようにする。上記したように、ここでは、選択され
た命令とプロファイルレジスタとの間に直接的な関連が
ある。それ故、レジスタに収集されるプロファイル情報
は、特定の命令に直接起因し得る。一度に１つのフライ
ト中命令しかプロファイリングされないときでも、ファ
イル即ちレジスタ３００をＩＤフィールド４０２でイン
デックスして、プロファイリングソフトの割り込みハン
ドラーのコストを多数の命令サンプルにわたり償還でき
るようにするのが有用である。命令セット内の命令が選
択された命令であるかどうかを決定することは、「ワイ
ヤドＯＲ」オペレーションを用いて行うことができる。

【００５４】ランダムサンプリング 本発明のプロファイリングのオーバーヘッドは、同時に
プロファイリングすることのできる命令の数を制限する
ことにより減少され、例えば、ビット４０１がセットさ
れる。プログラム又はプログラムの一部分において各命
令をプロファイリングするのではなく、ここでは、プロ
ファイリングされるべき命令が、プロセッサパイプライ
ン２００の特定の段階中に、例えば、フェッチの間に選
択され、そしてその選択された命令がサンプルビット４
０１のアサートによりタグ付けされる。サンプルビット
４０１がアサートされた場合には、パイプライン２００
の要素がプロファイル情報をプロファイルレジスタファ
イル３００へ送る。ここに記載する命令レベルプロファ
イリングをサポートする詳細について以下に述べる。

【００５５】フライト中状態 第１に、プロセッサパイプライン２００を通過する各デ
コードされた命令状態は、上記のように、付加的な情報
で増強される。命令は、それがフェッチされたときか
ら、それがリタイア又はアボートするときまで、フライ
ト中であるとみなされる。上述したように、命令は、少
なくとも１つのサンプルビット４０１で増強される。サ
ンプルビット４０１は、各フライト中命令及びキャッシ
ュ／メモリ要求の状態の一部分である。ビット４０１が
アサートされると、このビットは、この命令に対してプ
ロファイリング情報が記録されることを示し、さもなく
ば、記録されないことを示す。簡単な設計においては、
一度に１つのフライト中命令のみが、そのサンプルビッ
ト４０１をアサートすることが許される。サンプルビッ
ト４０１は、選択された命令に対し、その命令がリタイ
アするか又はアボートされるまで、アサートされたまま
となる。多数のレジスタファイル３００をもつ更に複雑
な設計では、多数のフライト中命令を個々にプロファイ
リングすることができ、そして付加的なビットをアサー
トすることができる。

【００５６】プロファイルされた命令の選択及びサンプ
リング フェッチ段の実施について図５に示したように、プロフ
ァイリングされるべき命令の選択及びプロファイル情報
のサンプリングは、次のように行われる。フェッチカウ
ンタ５１０は、例えば、特権付きプロファイリングソフ
トウェア（ＰＳＷ）５２０によりライン５１１を経て初
期化される。ＰＳＷ５２０は、所定サイズを有する値の
間隔からランダムに選択された値でカウンタ５１０を初
期化することができる。従って、サンプリングされた命
令は、命令の実行における特定のパターンと相関しな
い。間隔のサイズは、サンプリングの平均頻度を決定す
る。カウンタ５１０の値を初期化するための他のランダ
ム化技術（ハードウェアを含む）も使用できる。

【００５７】例えば、公知技術の場合のように命令が固
定頻度でサンプリングされるときのように、ランダムサ
ンプリングが行われないと、例えば、システム１００の
収集オペレーションのように、フェッチされた全ての命
令の統計学的に正しいプロファイルを発生することがで
きない。これは、サンプリングレートに対して比較的重
要でない多数の命令を含む実行ループを有する実行スレ
ッド、例えば、命令を有しそしてサンプリング間隔が６
５５３６個の命令であるループに対して、特に言えるこ
とである。他の通常のサンプリングも同じ問題を有す
る。そこで、２つの命令の一方のみからのサンプルが常
に収集される。１つの効果として、ランダムに選択され
た命令は、サンプリング間隔の長さとは独立した相関を
発生する。各命令４００がフェッチされるたびに、カウ
ンタ５１０がパイプライン２００のフェッチユニット２
１０によりその初期値から増加されるか、或いは別の実
施形態では、減少される。カウンタ５１０が、その実施
形態に基づいて、オーバーフローするか又はアンダーフ
ローしたときに、現在フェッチされた命令がそのサンプ
ルビット４０１をアサートし、そしてＩＤフィールド４
０２は、多数の命令がサンプリングのために選択された
ときにも初期化することができる。

【００５８】別の実施形態では、カウンタ５１０は、各
命令がフェッチされるたびではなく各サイクルごとに増
加され、例えば、カウンタ５１０は、フェッチの機会を
カウントし、実際にフェッチされる命令をカウントする
のではない。例えば、フェッチユニット２１０が各クロ
ックサイクル中にＩキャッシュ１１２から４つの項目を
フェッチできる場合には、４つのフェッチ機会がある。
Ｉキャッシュからの１つ以上のフェッチがミスとなるか
又は「不良」命令をフェッチすることがある。ミスの場
合には、ミスした命令に対して使用できるスロットが
「廃物」を含み、命令を無効とマークすることが必要に
なる。不良命令は、不良の実行経路に存在するものであ
るか、又はさもなくば、アボートされる。フェッチされ
た命令ではなくサイクルをカウントする場合には、設計
を効果的に簡単化する。フェッチされた有効な命令のみ
をカウントする場合には、かなり複雑なものとなる。と
いうのは、制御流が、フェッチされた命令のグループに
向かって又はそこから分岐することができ、従って、全
ての命令をデコードしてどれが有効であるかを決定する
ことが必要となり、もはや、カウンタを４だけ増加する
だけの簡単なことではなくなるからである。

【００５９】１つの効果として、サイクル中にＩキャッ
シュからフェッチされた全てのもの（良好な命令、不良
の命令、廃物命令）をサンプリングのために選択し、Ｉ
キャッシュ１１２及びパイプライン２００の真の性能を
決定することができる。ここでは、バイアスはなく、従
って、システム性能の統計学的に正しい推定値が得られ
る。これは、短い固定の時間周期中に又は離間された固
定の間隔で各有効な命令のみを選択する既知の技術とは
区別されるものである。何れの場合にも、オーバーヘッ
ドを最小にすることが戦略である。システム全体の性能
データを捕獲することのできる技術はない。

【００６０】命令のフィルタ動作 選択されたものは、フィルタ５０５によりフィルタする
ことができる。フィルタ動作は、命令ｏｐコード、オペ
ランド、或いは例えば、ある時間周期内で第１形式の命
令の後に別の形式の命令が続くといったより複雑なフィ
ルタ基準に基づいて行うことができる。パイプライン２
００への入力においてフィルタ動作を行う場合には、カ
ウンタ５１０をリセットすることができる。これを行う
方法は、多数ある。１つの方法では、カウンタ５１０の
現在初期値が初期値(init)レジスタ５１３に記憶され
る。命令がフィルタされるときには、初期値レジスタ５
１３に記憶された値がカウンタ５１０に再ロードされ、
初期のランダム化選択が想起される。

【００６１】命令が増強された後に、パイプライン２０
０は、図２ｂのプロファイル情報２８１−２８６をレジ
スタファイル３００（１つ又は複数）に供給する。リタ
イアユニット２５０は、命令の完了又はアボートに応答
して、プロファイル情報をファイリングを完了し、そし
てライン５４０に割り込み信号を発生して、ＰＳＷ５２
０がプロファイル情報をサンプリングできるようにす
る。或いは、ＰＳＷ５２０は、内部プロセッサレジスタ
又はメモリ位置（５４１）を経てライン５４０をポーリ
ングすることもできる。本発明の技術の１つの特徴とし
て、公知のあるプロファイリング技術とは対照的に、た
とえ本発明の技術がプロセッサにわたる状態に関する正
確な情報を与えるものであっても、プロセッサのサイク
ルタイムに何ら影響を与えない。唯一の時間制約は、プ
ロファイルレジスタ３００がサンプリングされる前に全
てのプロファイル情報を記録しなければならないことで
ある。

【００６２】待ち時間カウンタ 図６は、例示的な待ち時間、フェッチ対マップ（Ｆ
Ｍ）、マップ対イッシュー（ＭＩ）、イッシュー対リタ
イア（ＩＲ）、フェッチ対トラップ（ＦＴ）、及びイッ
シュー対ｌｄｓｔ（ＩＬＳ）をカウントするための回路
６００を示す。この回路６００は、ライン６１１により
ラッチ６２０に接続されたサイクルカウンタ６１０を備
えている。サイクルカウンタ６１０及びラッチ６２０
は、ライン６０１上の信号Ｐｆｅｔｃｈにより初期化さ
れる。この信号は、プロファイリングされるべき命令が
フェッチされるときに発生され、例えば、サンプルビッ
ト４０１から導出される信号である。カウンタ６１０
は、ライン６０９のクロック信号により増加される。各
クロック信号は、１つのプロセッササイクルに対応す
る。命令４００がパイプライン２００の段を経て進行す
るときに、パイプライン２００の段遷移がライン６０２
−６０６の信号、各々、Ｐｍａｐ、Ｐｉｓｓｕｅ、Ｐｒ
ｅｔｉｒｅ、Ｐｔｒａｐ及びＰＬＳｄｏｎｅをトリガー
する。対応するラッチ６２０は、図３のプロファイル待
ち時間レジスタ（又はフィールド）３５０に記憶するた
めにライン６１２−６１６において読み取ることができ
る。

【００６３】プロファイリングアプリケーション 上記のプロファイリングハードウェアは、種々の異なる
方法で使用することができる。本発明の技術は、個々の
命令の実行に関する非常に詳細な情報を与えるので、１
つのアプリケーションで非常に多数の命令をプロファイ
リングすることができる。サンプル情報はメモリバッフ
ァに記憶され、プロファイリングツールにより後で処理
されて、詳細な命令レベル情報を形成することができ
る。この情報は、例えば、各ロード命令に対するロード
待ち時間のヒストグラム、命令実行時間のヒストグラ
ム、及びおそらくは各命令に対するパイプライン状態の
適度に包括的な分析を発生するのに使用できる。この解
決策により与えられる情報の量は、おそらく、かなり多
くなるので、本発明の技術の全メモリオーバーヘッド
も、相当の量のメモリトラフィックが含まれるために、
かなり大きなものとなる。例えば、１秒当たり１０億の
命令がフェッチされ、そして各１万のフェッチされる命
令ごとにサンプリングが実行される場合には、プロファ
イル情報のデータレートが１秒当たり約２．４ＭＢとな
る。以下、プロファイル情報を収集することにより帯域
巾を減少するためのソフトウェア実施方法について説明
する。

【００６４】出力プロファイル情報をフィルタすること
によるデータの減少 サンプリングされるデータの量は、プロファイル記録の
あるフィールド、例えば、プロファイルレジスタ３００
のデータを、それらが明確に要求されるときを除いて、
無視することにより、減少することができる。システム
１００のユーザは、異なるレベルのプロファイリングを
望むことがある。最低のオーバーヘッドモードでは、プ
ロファイリングアプリケーションソフトウェアは、ＰＣ
及びリタイア−遅延フィールドのみを用いてプログラム
の全部又は一部分に対してプロファイルレポートを発生
することができる。実行されるべき最適化に基づき、平
均化又は他の統計学的メトリック、例えば、最小、最大
又は標準偏差の計算により他のＰＣごとの(per-PC)値を
要約することができる。データを処理するための更なる
時間が与えられると、プロファイリングアプリケーショ
ンは、種々の命令待ち時間のヒストグラムを形成するこ
とができる。

【００６５】有効なメモリアドレス、分岐ターゲットア
ドレス及び分岐経過サンプルは、おそらく、他のフィー
ルドよりも経費のかかる処理を必要とする。これらのフ
ィールドは、おそらく、特定の最適化タスクを実行する
ためにデータを収集するとき以外は無視することができ
る。命令と命令との間の命令間フェッチ距離がサイクル
で与えられると、プロファイリングアプリケーション
は、同時性のレベルに関する情報も収集することができ
る。又、プロファイリング情報のフィルタ動作は、例え
ば、マスクレジスタ又はプログラマブルロジックのよう
なハードウェア手段により行うこともできる。例えば、
キャッシュミスがあったとき又は命令がリタイアしたと
きにのみサンプルリングするか、或いはｏｐコード、オ
ペランド、アドレス、事象及び待ち時間の他のブール組
合せのみをサンプリングする。

【００６６】ハードウェアオペレーションの決定 本発明のプロファイリング技術は、Ａｌｐｈａ２１２６
４プロセッサのようなアウトオブオーダーイッシュープ
ロセッサの内部動作の正確な理解を得るために使用する
ことができる。この形式のマシン編成に関して注目すべ
き第１の事柄の１つは、パイプライン２００において命
令がストールする場所が多数ありそしてストールする理
由が非常に多数あることである。例えば、ある命令は、
イッシューユニット２３０においてストールすることが
ある。というのは、そのオペランドの幾つかがデータレ
ディでなく、選択された命令の実行に必要なリソースの
幾つかが使用できず、又はその命令に先立って他の命令
が実行されるべく選択されるからである。

【００６７】ある命令は、仮想−物理的レジスタマッピ
ングを行うマップ段においてストールすることがある。
というのは、マシンが物理的レジスタからのものであ
り、フライト中の命令が非常に多数あり、或いはイッシ
ューユニット２３０がいっぱいである（実行されようと
している命令を入れる場所がないことを意味する）ため
である。或いは又、ある命令は、リタイアユニットにお
いてストールすることがある。というのは、プログラム
順に既にイッシューされた命令がまだ完了していないか
らである。命令がどこでストールされたか、なぜストー
ルされたかそしてどれほどの時間ストールされたかを正
確に決定することは、主に、その命令が実行されるとき
のマシンの正確な状態によって左右される。プロセッサ
がこのように動的であるために、ソフトウェア性能ツー
ルでこの状態を静的に決定することは困難である。

【００６８】オペレーションの概要 図７ａに示すように、プロファイリング方法７００は、
次のステップを含むことができる。プロファイリング状
態は、ステップ７１０において初期化される。ここで、
レジスタがクリアされ、そしてカウンタに初期値が指定
される。ステップ７２０において、命令がフェッチされ
そしてカウントされる。ステップ７３０において、初期
化以来フェッチされた命令の数が所定のランダム数に等
しいときに命令が選択される。選択された命令は、その
選択を指示するよう増強される。選択された命令が実行
パイプライン２００を経て進むときに、ステップ７４０
においてプロファイル情報が収集される。完了（リタイ
ア又はアボート）時に、収集された情報がステップ７４
０においてサンプリングされる。サンプリングされた情
報は、その後の処理のためにバッファすることができ
る。又、特定のプロファイリング状態をサンプリング
し、より詳細な情報を抽出することもできる。

【００６９】処理された命令の特性の統計値の推定 図７ｂに示されたように、プロセス７９９は、パイプラ
イン２００により処理される命令の特性の統計値を推定
する。プロセス７９９は、次のステップを含むことがで
きる。ステップ７５１は、ステップ７５０において上記
したようにサンプリングされたプロファイル記録３００
を読み取る。記録は、選択された命令が完了したときに
読み取られる。ステップ７６０において、サンプルは、
システムの状態情報を考慮するファンクション７５５に
基づいて選択又は破棄される。例えば、ファンクション
７５５は、選択された命令のアドレス、プロセス識別
子、アドレススペース番号、ハードウェアコンテクスト
識別子、又はスレッド識別子のような状態情報７５６を
入力として得る。又、ファンクション７５５は、経路識
別情報、ｏｐコード、オペランド、待ち時間、又は選択
された命令により経験する事象のような状態情報も使用
することができる。事象情報は、リタイア／アボート／
無効状態、キャッシュヒット／ミス、分岐予想ミス、ト
ラップ状態ＴＬＢヒット／ミス、及びデータリソース依
存性状態、等々である。

【００７０】ステップ７６０は、ファンクション７５５
に基づいてサンプルのサブセットを発生する。ステップ
７８０において、統計値７９０が決定される。これら統
計値は、サンプリングされた命令の特性の平均値、標準
偏差、ヒストグラム（分布）及びエラー限界を含むこと
ができる。例えば、特定の事象が発生する平均レート
や、命令実行の平均待ち時間や、メモリアクセスがあ
る。又、プロセス、スレッド又はハードウェアコンテク
ストの実行レートの平均値も決定できる。ヒストグラム
は、命令実行、メモリアクセスレート又は待ち時間のよ
うな分布を示すことができる。エラーの限界は、サンプ
リングされている特定の特性に対してサンプルの数の平
方根の逆数で近似することができる。

【００７１】Ｎ個ごとのサンプリング ここに開示するプロファイリング技術は、Ｎ個ごとの(N
-wise)サンプリングを実行するのにも使用できる。ここ
で、多数の同時実行命令間の相互作用の動的な状態を捕
獲することができる。単一のフライト中命令をプロファ
イリングするのではなく、２つ以上の個別の命令が同時
にプロファイリングされる。選択された命令間の動的な
「距離」は、フェッチされた命令の数、又はフライト中
の命令を「分離」するプロセッササイクルの数として測
定することができる。カウンタ５１０によりカウントさ
れる事象のいずれかを用いて、選択された命令間の距
離、例えば、クロックサイクル、フェッチされた命令等
を測定することができる。Ｎ個ごとのサンプリングされ
た命令に対するプロファイル情報は、多数の考えられる
用途を有する。第１に、情報を分析して、有用な同時性
レベルを測定することができる。これは、真のボトルネ
ックを探索できるようにする。真のボトルネックは、長
いストールが低い同時性で結合されることを特徴とす
る。又、Ｎ個ごとのサンプルは、経路のプロファイリン
グを容易にすると共に、経路に沿った少なくとも２つの
ポイントを含むように経路を制限することにより実行経
路候補を明確化することができる。更に、Ｎ個ごとのサ
ンプリングから、詳細なプロセッサパイプライン状態を
統計学的に再構成することもできる。ここで、命令のグ
ループの選択は、命令間のある類似性の尺度、例えば、
最近の分岐経過、ストール、命令形式、又は他の最近の
状態経過をベースとすることができる。

【００７２】有効な同時性の測定 アウトオブオーダープロセッサにおいて性能のボトルネ
ックを正確に位置決めするには、ストール時間及び同時
性レベルの両方に関する詳細な情報を必要とする。イン
オーダープロセッサとは対照的に、長い待ち時間の命令
がストールされる間にプロセッサを効率的に利用するに
充分な同時性があるときには、長い待ち時間の命令が問
題とならない。同時性情報を得るための１つの解決策
は、全パイプライン状態のスナップショットを得ること
である。これは、同時実行命令のセットが所与の時点で
パイプラインの段のどこにあるかを直接的に露呈する。
しかしながら、全パイプラインの状態をサンプリングレ
ジスタ及びバッファに「ダンプ」することは、時間及び
スペースの両面で非常に経費がかかる。更に、発生され
る多量のデータは、おそらく、サンプリングのコストを
償還するように効率的に収集することができない。更に
悪いことに、この解決策は、リタイアする命令しか「有
効」としてカウントされず、そしてフェッチされた命令
がアボートするところの情報がまだ分からないので、実
際上不充分である。

【００７３】ネスト状の対ごとのサンプリング Ｎ個ごとのサンプリングの１つの形式は、単一命令プロ
ファイリングと全パイプラインスナップショットとの間
の妥協を最小にする。ここで、統計学的な対ごとの(pai
r-wise) サンプリングがネスト状に行われ、所与の選択
された命令に対して、同時に実行し得る別の命令が直接
サンプリングされる。ネスト状のＮ個ごとのサンプリングに対するハードウェ
アサポート Ｎ個ごとのサンプリングは、次のハードウェア特徴を含
む。第１に、ハードウェアは、少なくとも２つの同時フ
ライト中命令に対しプロファイル情報を捕獲できねばな
らない。プロファイルレジスタのセットは、プロファイ
ル記録の多数の個別のセットをサポートするために複写
されねばならず、そして単一サンプルビット４０１は、
より一般的なＩＤフィールド４０２へと増強されねばな
らない。第２に、ハードウェアは、サンプリングレート
の変更により、選択された命令間の距離を動的に変更で
きねばならない。これは、ハードウェア又はソフトウェ
アによって行うことができる。同時サンプリング命令
（Ｎ個ごと、但しＮ＞１）のセットのサイズは、カウン
タ及びレジスタの付加的な複写でより大きくすることが
できる。

【００７４】例えば、特権付きプロファイリングソフト
ウェア５２０は、対ごとのケースでは２つのフェッチカ
ウンタ５１０の初期値がランダムに選択されるところの
間隔のサイズを動的に変更することができる。これは、
一対の命令に対するサンプル間フェッチ距離を同時に特
定できるようにする。ハードウェアは、ソフトウェアレ
ベルでの最大の融通性を得るために比較的大きなサンプ
ル間フェッチ距離をサポートすることができる。第２の
フェッチカウンタがコアフェッチ命令カウンタ５１０と
同じサイズであって、充分な距離に離れた２つの独立し
た命令を選択できるのが理想的である。Ａｌｐｈａ２１
２６４プロセッサの場合には１０ビットカウンタで充分
である。フェッチ命令をカウントするときに同時性を測
定するには、それより小さなカウンタで充分であり、サ
イクルがカウントされる場合には、それより大きなカウ
ンタが必要とされる。ネスト状のＮ個ごとのサンプリン
グについては、ハードウェアは、サンプル間フェッチ・
対・フェッチ待ち時間もサイクルで測定して、多数の待
ち時間レジスタ３５０を時間的に相関させることができ
ねばならない。

【００７５】ネスト状のＮ個ごとのサンプリングアプリ
ケーション 高レベルアプリケーションソフトウェアは、ネスト状の
Ｎ個ごとのサンプリングを用いて、有効な同時性を測定
することができる。ここでの重要な考え方は、潜在的に
同時に実行し得る命令セットのサンプリングを許すこと
である。ネスト状のサンプリングは、通常のサンプリン
グを正当化する同じ統計学的引数に基づくもので、即ち
サンプリングが繰り返し適用される。Ｎ個ごとのサンプ
リングは２つのサンプリングレベルを含むので、著しく
実行されるコードについては最も効果的である。明らか
に、これは、最も重要なところでもある。

【００７６】定義された同時性 図８に示すように、４巾のパイプラインにおける所与の
選択された命令Ｉ（８１０）に対し、潜在的に同時の命
令とは、ある動的な実行中に命令Ｉと共にプロセッサパ
イプライン２００に共存する命令である。これは、命令
Ｉがフェッチされる前に種々の実行段に存在する命令
と、命令Ｉがリタイア又はアボートされる前にフェッチ
される命令とを含む。例えば、Ａｌｐｈａ２１２６４プ
ロセッサは、８０個のフライト中命令を許すものであ
る。しかしながら、実際には、同時即ちフライト中命令
の実数は、おそらく、ハードウェアでサポートされるピ
ーク値より相当に小さい。他方、予想ミス又は不良経路
に沿った推測的実行は、潜在的同時性のウインドウを増
加することができる。Ａｌｐｈａ２１２６４プロセッサ
において同時性を検討するために、命令Ｉ（８１０）の
周りのウインドウＷ８２０の適度なサイズが約１００個
の命令を含まねばならないことが提案された。他の実施
形態については、ウインドウの適当なサイズを実験で決
定することができる。例えば、約１００個の潜在的な同
時命令であるサイズＷのウインドウが与えられると、選
択される命令間のフェッチ距離をランダム化することに
より非バイアスのサンプリングを行うことができる。例
えば、対ごとの各サンプル＜Ｉ１、Ｉ２＞（８３１及び
８３２）に対し、サンプル間フェッチ距離は、１とＷと
の間に均一に分布した擬似ランダム数にセットされる。
このように、第１の選択された命令Ｉ１と第２の選択さ
れた命令Ｉ２との間でサンプル間距離をランダムに変更
すると、命令が実際に時間的に重畳するところの多量の
統計学的情報が捕獲される。

【００７７】同時重畳の分析 種々のサンプル間フェッチ距離をもつ同時選択される命
令のセットに対するプロファイル情報は、有効な同時性
統計値を直接的に表す。対応するサンプル情報の各セッ
トを使用し、第１命令Ｉ１から時間的に前方にそして第
２命令Ｉ２から時間的に後方に見ることにより同時性情
報を決定することができる。各Ｎ個ごとの選択された命
令に対して記録されるプロファイル情報は、両命令＜Ｉ
１、Ｉ２＞が所与の時間にプロセッサパイプライン２０
０に存在するようなインスタンスを正確に考慮する待ち
時間を含まねばならない。更に、待ち時間レジスタのセ
ットを相関させるためには、サンプル間フェッチ待ち行
列が記録されねばならない。又、ネスト状のプロファイ
リングは、放棄した実行経路において命令＜Ｉ１、Ｉ２
＞が完了したときを指示することもできる。この詳細な
情報を統計学的に収集して、有効な同時性レベルを反映
する種々のメトリックを形成することができる。

【００７８】浪費イッシュースロットの測定 種々のサンプル間フェッチ距離をもつ対ごとの命令サン
プル＜Ｉ１、Ｉ２＞の収集は、有効な同時性統計値を直
接的に表す。対ごとの各サンプルを使用して、第１命令
から時間的に前方にそして第２命令から時間的に後方に
見ることにより同時性情報を計算する。命令Ｉの後にフ
ェッチされた命令に対する性能情報を測定するために、
＜Ｉ、Ｉ２＞の形態の対を考える。命令Ｉの前にフェッ
チされた命令に対する性能を測定するために、＜Ｉ１、
Ｉ＞の形態のサンプルされた対を考える。対ごとの各サ
ンプル＜Ｉ１、Ｉ２＞に対して記録されるプロファイル
データは、待ち時間レジスタ３５０に記憶される値であ
って、各時点にプロセッサパイプライン２００のどこに
Ｉ１及びＩ２があるかを指示する値と、２セットの待ち
時間レジスタ３５０を相関させることのできるサンプル
間フェッチ待ち時間とを含む。又、プロファイル記録
は、対＜Ｉ１、Ｉ２＞がリタイアするかどうかも指示す
る。

【００７９】この詳細な情報を統計学的に収集して、有
効な同時性レベルを反映する種々のメトリックを形成す
ることができる。例えば、命令Ｉに対する１つの関心の
ある同時性の尺度は、Ｉがフライト中である間に浪費し
たイッシュースロットの平均数である。浪費したイッシ
ュースロットの数は、図９に示すように決定できる。Ｉ
及びＩ２がリタイアするような形式＜Ｉ、Ｉ２＞のサン
プルの数をＦ１とし、サンプルと共に記録される待ち時
間は、Ｉ及びＩ２の実行が重畳することを指示する（ス
テップ９１０）。それ故、有効な順方向重畳を伴うサン
プル対の全数をカウントし、これはＦ１で表される。同
様に、ステップ９２０において、Ｉ及びＩ２の両方がリ
タイアしそしてそれらの実行が重畳するような形式＜Ｉ
１、Ｉ＞のサンプルの数をＢ１とする。即ち、第２の命
令が第１の命令に対してサンプリングされる場合には順
方向に、そして第１の命令が第２の命令に対してサンプ
リングされる場合には逆方向に、各対が２回考慮され
る。

【００８０】次いで、ステップ９３０において、一致す
るサンプルの数Ｆ１＋Ｂ１に潜在的な同時性のサンプル
ウインドウのサイズＷを乗算することにより、命令Ｉが
フライト中である間にイッシューされる有効命令の数を
統計学的に推定し、即ち形成されるイッシュースロット
の数は、Ｗｘ（Ｆ１＋Ｂ１）となる。イッシュースロッ
トで測定される命令Ｉの累積的待ち時間Ｌ１、例えば、
Ａｌｐｈａ２１２６４プロセッサで持続できる４／サイ
クルを付加的に決定することにより、ステップ９４０に
おいて、命令Ｉの実行中に浪費したイッシュースロット
（ＷＩＳ）の全数を次のように要約することができる。 ＷＩＳ＝Ｌ１−（Ｗｘ（Ｆ１＋Ｂ１）） 値ＷＩＳは、命令Ｉの実行当たりの浪費イッシュースロ
ットの割合又は平均数を表すように容易に拡張すること
ができる。好都合にも、この平均に寄与する値を増分的
に収集し、データ収集中にコンパクトな記憶を行うこと
ができる。又、これは、１９９７年３月３日に出願され
たウエイル氏等の「プロセッサ性能カウンタの高頻度サ
ンプリング(High Frequency Sampling of Processor Pe
rformance Counters) 」と題する米国特許出願第０８／
８１２，８９９号に開示されたような効率的なデータ減
少技術を可能にする。

【００８１】命令Ｉがフライト中である間にリタイアし
た命令の数、又は命令Ｉの周りでイッシューされた命令
の数のような他の同時性メトリックも同様に決定するこ
とができる。最終的に、命令Ｉが特定のパイプライン段
にある間の特定の実行ユニット２４０の平均的な利用の
ような更に詳細な情報も抽出又は収集することができ
る。

【００８２】単一プロセッササイクル中にパイプライン
段により処理される命令の瞬時平均数の決定 図１０に示すように、異なる形式の多路サンプリングを
使用して、固定サイズのプロセッササイクル数にわたり
パイプラインにより処理される命令の平均数を決定する
ことができる。図１０は、例えば、リタイアされる命令
の瞬時平均数を決定するための回路を示す。プロセッサ
サイクル中に、パイプライン２２０のいずれの段１００
１についても、同様の回路を使用して、フェッチ、マッ
プ、イッシュー又は実行される命令の平均数を決定する
ことができる。装置１０００において、先入れ先出し
（ＦＩＦＯ）待ち行列１０１０及びＮ容量の加算器１０
２０の各々は、単一のプロセッササイクル中にパイプラ
インの特定の段１００１により処理される命令の数（カ
ウント１００２）を受け取り、例えば、フェッチ、マッ
プ、イッシュー又は実行される命令の数を受け取る。Ｆ
ＩＦＯ待ち行列１０１０におけるエントリの数（Ｐ）１
０２２は、平均値が決定されるところのサイクルの数を
決定する。Ｐは、ハードウェアで設定されてもよいし、
ソフトウェアで設定されてもよい。値Ｐは、平均値が決
定されるところのサイクルのウインドウを制御する。加
算器１０１０はスケール型カウントレジスタ１０４０に
接続され、従って、このレジスタ１０４０は、Ｎ個のサ
イクル中にリタイアした命令の全数を累積することがで
きる。ＦＩＦＯ待ち行列１０２０及びレジスタ１０４０
は、ライン１０２１及び１０４１を経て初期化すること
ができる。減算器１０３０は、それまでのＮ−１サイク
ルにリタイアした命令の数をレジスタ１０４０から減算
し、例えば、ＦＩＦＯ待ち行列１０１０のヘッドエント
リに記憶されたカウントを減算する。レジスタ１０４０
の出力は追跡されたサイクルの数（Ｐ）で除算され（１
０５０）、段１００１で処理された実際の命令の動特性
即ち瞬時平均数１０６０を形成する。瞬時平均値は、プ
ロファイルレジスタ３００に捕獲されるか、或いはソフ
トウェアで読み取り可能なプロセッサレジスタ又はメモ
リ位置に記憶される。

【００８３】サンプルされた命令がリタイアした命令で
あるときには、コンピュータにより行われた実際の
「真」の有効作業を計算することができる。これは、相
対的なプロセッサ性能を指示するためにしばしば引用さ
れる「生」の命令フェッチレートよりも良好な指示であ
る。例えば、特定のアーキテクチャーは、大きなフェッ
チレートをもつことができるが、パイプラインにおける
ストールが性能を低下することがある。

【００８４】命令のクラスター化 又、サンプルされた状態情報を使用し、同時性情報を収
集しながら当該ケースを識別することもできる。例え
ば、命令Ｉがキャッシュの１つにおいて「ヒット」する
ときに平均同時性レベルを計算し、次いで、平均同時性
レベルを、命令Ｉがキャッシュミスを招く場合と比較す
ることが有用である。変化する同時性レベルと相関する
ために検討すべき他の当該特徴は、レジスタ依存性スト
ール、キャッシュミスストール、分岐予想ミスストー
ル、及び最近の分岐経過を含む。一般に、Ｎ個ごとのサ
ンプリングは、Ｗ個の命令のウインドウにわたりＦ（Ｉ
１、Ｉ２）と表すことのできるファンクションの値をサ
ンプリングすることにより種々の異なるメトリックを統
計学的に計算できるようにする著しい融通性を与える。
対応する公知のハードウェアメカニズムとは対照的に、
ここに与えられる融通性は、Ｎ個ごとのサンプリング
を、複雑なプロセッサに関する同時性情報を捕獲するた
めの非常に優れた選択肢にする。これは、新規なメトリ
ック及び分析技術の設計を可能にするためである。標準
的なＳＰＥＣベンチマークソフトウェアを実行するプロ
セッサでの実験では、統計学的に収集されたサンプルを
ベースとするメトリックは、低いオーバーヘッドの完全
な情報で得られた値に収斂することが示されている。

【００８５】経路プロファイル 命令のクラスターをプロファイリングする付加的な効果
は、経路プロファイルが得られることである。経路プロ
ファイルは、多数のコンパイラー最適化及びトレースス
ケジューリングに有用である。更に、最近の分岐実行経
過と共にプログラムの実行経路に沿った多数のポイント
を制限することにより、経路プロファイルが明確化され
る。この明確化は、Ｎ個ごとのサンプリングとで改善さ
れ、即ちＮが増加するにつれて、明確化が改善される。
著しく実行されるコードの場合には、同時プログラム
が、全ての実行命令に対しパイプライン２００の各段に
おいて命令の相対的な実行順序を示すことができる。従
って、ここでは、オペレーティングシステムにおける実
行パイプライン２００の実際のオペレーションを統計学
的に再構成することができる。

【００８６】ランダムにサンプルされるプロファイル情
報の他のアプリケーション マイクロプロセッサの最新の世代は、考えられる最高の
性能を与えるためにコンピュータアーキテクチャーが許
す全ての策略を利用する。これらのマイクロプロセッサ
は、サイクル当たり多数の命令をフェッチし、イッシュ
ーしそしてコミットする。更に、これらのプロセッサ
は、命令を順序ずれして実行する。それらのあるもの
は、メモリオペレーションも順序ずれして実行する。不
都合なことに、プロセッサにより使用される多数の発見
的メカニズムが命令及びメモリオペレーションを順序ず
れしてイッシューするので、性能特性がかなり変化し得
る。１つの効果として、ここに述べるプロファイリング
技術は、システム１００の性能を自動的に改善できるよ
うに、システムがプログラムの性能を充分詳細に測定で
きるようにすることである。

【００８７】最適化 又、本発明のプロファイリング技術は、システム１００
の最適化を実行するのにも使用できる。以下の説明は、
プログラマー及びコンパイラーで指令されるソフトウェ
アプログラムの最適化を手引きするよう意図されたもの
である。

【００８８】ハードウェアの最適化 アウトオブオーダーのスーパースカラーマイクロプロセ
ッサは、データ及びリソースの利用状態に基づいて命令
をスケジューリングし直すので、コンパイル−時間命令
スケジューリングは、構造的に簡単なプロセッサの場合
よりも重要性がかなり低い。ここでは、主なボトルネッ
クは、命令フェッチ及びメモリオペレーションによるも
のである。より詳細には、分岐又はジャンプ予想ミス、
オンチップキャッシュミス、及びＴＬＢ欠陥によりプロ
セッサパイプライン２００においてサイクルが失われ
る。これらは、静的に推測することが不可能でないまで
も困難な状態である。又、高レベルオフチップオペレー
ションにおける遅延に対しても、キャッシュミス、リソ
ーストラップ及び順序づけトラップのために、サイクル
が失われる。失われたサイクルは、時間を浪費する。従
来の事象カウンタでは、これらの性能低下事象の合計数
を測定することはできるが、失われたサイクルをプログ
ラムの特定の命令に起因させることは不可能ではないま
でも非常に困難である。ここに述べるプロファイリング
技術は、ユーザが主な性能問題を測定して、それら問題
を特定の命令に相関させることができるようにする。

【００８９】フロントエンド最適化 性能の助けとなる１つのフロントエンド最適化は、基本
的ブロックにおいて命令をそして手順において基本的ブ
ロックを順序付けし直すことである。基本的ブロックと
は、１つの単位として直線的に実行されるか又は全く実
行されない命令のセットとして定義される。手順とは、
一般に、コール命令を経て到達する基本的ブロックの凝
集セットである。手順は、多数の基本的ブロックを含む
ことができる。基本的ブロックにおいて命令をそして手
順において基本的ブロックを順序付けし直すことは、ペ
ージ及びキャッシュの一時的な位置を最適化すると共
に、分岐の数を減少するように実行流及びデータアクセ
スを変更できるようにする。分岐は、実行流しか再指令
せずそしてデータにおいて有効に作用しないので、サイ
クルを浪費する。この最適化は、入力として、制御流グ
ラフエッジ周波数を知る必要がある。

【００９０】トレースの形成 同様に、命令のスケジューリングを追跡するために、コ
ンパイラーは、制御流グラフのエッジ又は経路周波数を
必要とする。トレーススケジューラは、各基本的ブロッ
ク又はより大きな実行経路を実行するのにどれほどの時
間を要するかの推定値を有するときは非常の良好なジョ
ブを行うことができる。アルタ・ビスタサーチエンジン
のような大規模な動作システムの場合には、これを従来
のツールでリアルタイムに測定することが困難である。

【００９１】ホット／コールド最適化及び経路情報 トレーススケジューリング及びホット／コールド最適化
のような多数のコンパイラー最適化は、プログラムによ
りどの実行経路が頻繁にとられるかを知ることに依存し
ている。これらは「ホット」経路と称する。最近まで、
計装又は模擬のいずれかによりプログラムをプロファイ
リングすることにより、頻繁に実行される経路が推測さ
れて、基本的なブロック又はエッジカウントが収集さ
れ、そしてこれらのカウントを用いて、ホット及びコー
ルド経路が間接的に推測される。最近、経路情報を直接
収集するための技術が使用されている。これらの技術は
正確な経路情報を与えるが、非常に高いオーバーヘッド
をもつ傾向があり、アクティブな大規模コンピュータシ
ステムを測定するには不適当である。本発明のプロファ
イリングでは、経路情報を最小のオーバーヘッドでラン
ダムに捕獲することができ、そして実際の実行流の統計
学的に正しい概観を依然として表すことができる。

【００９２】分岐経過レジスタ ほとんどの近代的なマイクロプロセッサは、グローバル
な分岐経過レジスタにおいて最後のＮ個の分岐の方向を
追跡する。分岐経過レジスタは、移動ウインドウとし
て、最近の分岐予想を観察し、そしてそれに応じて将来
の命令フェッチに作用を及ぼすことができる。命令のＰ
Ｃがサンプリングされると共に、このレジスタの内容を
命令フェッチ時間に捕獲することにより、時には、制御
流グラフの静的な分析を使用して、プロセッサがとらね
ばならない最後のＮ個の分岐により厳密な経路を仮定す
ることができる。しかしながら、従来の経過レジスタ
は、通常、分岐の方向しか含まず、実際のターゲット行
先を含まないので、情報が不正確なものとなる。特に、
制御流の合流は、実際にとられた経路を識別する上であ
いまいさを招く。又、分岐コードの実行を生じさせる非
同期事象、例えば、割り込み又はコンテクストスイッチ
は、分岐経過ビットを汚染することがある。しかしなが
ら、これらの事象は、比較的稀であり、そしてオペレー
ティングシステムにおけるそれらの発生は、コードにわ
たってランダムに分布されねばならない。頻度の高い経
路を識別するのが目的であるから、予想不能な非同期事
象により発生される「ノイズ性」の分岐経過ビットによ
り生じるものを含む頻度の低い経路を無視することがで
きる。図１１に示す命令シーケンスについて考える。Ｐ
ＣアドレスＡ−Ｅ（１１０１−１１０５）に命令があ
る。アドレスＡ及びＣにおける命令１１０１及び１１０
３は、分岐型の命令である。ＥのＰＣをもつ命令１１０
５があって、グローバルな分岐経過における最後のビッ
トが１である場合には、ＣＤＥで終わるいかなる経路も
除外することができる。というのは、このような経路の
最後の分岐が失敗に終わり、それ故、グローバルな分岐
経過に対応しないからである。しかしながら、ポイント
Ｅにおける異なる制御経路の合体により、実行された真
の経路がＡＥ（１１１０）又はＡＢＣＥ（１１１１）で
あったときを決定することができない。

【００９３】制御流グラフの合流によるあいまいさ 図１２は、サンプリングされたＰＣ値を入力として使用
して、プログラム流の静的な分析を実行することのでき
るプロセス１２００を示す。選択された命令の経路サン
プルがステップ１２１０において上記のように捕獲され
る。マシンへの影響を最小にするために、サンプリング
された命令はランダムに選択されるのが好ましい。各
「経路」サンプル１２２０は、サンプリングされた第１
命令Ｉ１のＰＣ１と、命令Ｉ１までの最後のＮ個の条件
付き分岐によりとられる方向（ＢＲＡＮＣＨ ＨＩＳ
Ｔ）とを含む。

【００９４】任意であるが、サンプリングされた情報
は、第１命令の直前に実行される第２命令（Ｉ２）のＰ
Ｃ２で増強することもできるし、或いは最後のＭ個の分
岐のＰＣ値に適用されるあるファンクション、例えば、
ある数の下位ビット又はハッシュ関数を用いて決定され
たビットを選択するファンクションに基づいて選択され
た情報で増強することもできる。ステップ１２４０にお
いて、経路サンプルを使用して、プログラムの制御流グ
ラフの逆方向分析を実行する。この分析は、サンプリン
グされたデータに一致する実行経路を識別することがで
き（１２５０）、そしてこの情報を収集して、最適化か
ら更に効果が得られる頻繁に実行される経路を識別する
ことができる（１２６０）。

【００９５】例えば、図１１を参照すれば、命令Ｅにお
いて、１の分岐経過長さが与えられると、経過ビット
「１」により、ソフトウェアツールは、経路セグメント
ＡＥ１１１０及びＡＢＣＥ（１１０１−１１０５）を考
えられる経路として識別することができる。分岐経過ビ
ットの値が与えられたときに、静的な分析が、可能性と
して、単一経路セグメントしか識別できないときに、考
えられる最良の成果が得られる。又、プロセスの最近の
実行経過に関する他の情報も、特定の命令に到達するた
めにとられた実行経路を識別する上で助けとなる。有効
な情報の１つの断片は、最近実行された命令の第２のＰ
Ｃ値の知識である。おそらくＮ個ごとのサンプリングと
共に多数のＰＣ値を使用することにより、１つのＰＣし
か含まない経路を除外することができる。

【００９６】所与のクラスの最後のＭ個の命令のサンプ
リング 図１３に示す別の技術においては、ハードウェアは、パ
イプラインの任意の選択された段、例えばリタイアユニ
ットで処理された最後のＭ個の命令の各々から少数のビ
ット（Ｂ）を捕獲することができる。Ｂビット１３０３
は、ＰＣの下位のＢビットでもよいし、或いはＢビット
は、ＰＣ１３０４に適用されるハードウェア実施ファン
クションＦ１３１０を使用して選択することもでき、即
ちＢ←Ｆ（ＰＣ）である。ファンクション１３１０がハ
ッシュ関数である場合には、分岐アドレスの非均一な分
布が回避される。命令のクラスは、例えば、条件分岐、
コール、リターン、アクセス（ロード又は記憶）命令、
間接的分岐、及び間接的コール１３２１−１３２６とし
て識別することができる。クラスは、比較器又はマルチ
プレクサのような選択メカニズム１３２０によりライン
１３２１を経て選択することができる。又、クラスは、
パイプラインの段、例えば、フェッチ、マップ又はリタ
イア等により識別することもできる。クラスＩＤ１３１
９は、ソフトウェアにより制御される。

【００９７】選択されたビットは、ＭｘＢビット巾のシ
フトレジスタ１３００に記憶することができる。このレ
ジスタは、ソフトウェアの内部レジスタとして或いはメ
モリ位置として図５のＰＳＷ５２０へアクセスすること
ができる。識別されたクラスの命令１３２１−３１２４
が処理されるときには、シフトレジスタ１３００は、そ
の上位のＢビット１３０２を破棄するようにシフトされ
る。命令のＰＣ１３０４の選択されたＢビット１３０３
は、空きビット１３０５へとシフトされる。従って、レ
ジスタ１３００は、これら形式の命令に対し指紋即ち
「経路符号」として働く。レジスタ１３００は、例え
ば、実行された最新のＭ個の分岐を制限する助けをす
る。というのは、現在経路符号に一致しない経路は、考
慮対象から排除できるからである。分岐命令１３２１に
対し、図２の分岐実行指示２８７を使用して、サンプリ
ングをトリガーすることができる。

【００９８】経路符号により得られる精度の改善は、相
当のものとなり、例えば、Ｂ＝４、Ｍ＝６のように、最
後の６個の分岐から４つのビットを節約するだけでも、
標準的なＳｐｅｃＩｎｔ９５ベンチマークプログラムに
対する実行経路を決定する精度が２倍になる。経路符号
及びグローバルな分岐経過を使用すると、トレースを次
のように分析することができる。トレースにおいて実行
される各命令に対し、次のいずれかに達するまで経路セ
グメントを決定するように逆方向に進行する。 ａ）グローバルな分岐経過ビットが尽きる、又は ｂ）命令を含むルーチンの開始点に到達する。

【００９９】制御流グラフの逆方向進行中に手順のコー
ル命令に遭遇したときには、コールされた手順を通して
逆方向に進行し、そして最終的に、そのコールされた全
ルーチンを通して逆方向に作用するに充分な分岐経過が
あるときに、コール側手順に復帰する。従って、実行流
のより正確な概観が与えられる。

【０１００】キャッシュ及びＴＬＢヒットレートの増強 キャッシュ又は変換ルックアサイドバッファ（ＴＬＢ）
における高いミスレートは、システムの性能を著しく低
下する。公知の解決策は、一般に、キャッシュミスアド
レスを収集する特殊なハードウェア又は特殊なソフトウ
ェア機構、例えば、ＴＬＢを周期的にフラッシュするも
のに依存している。観察されたミスパターンは、頻繁に
アクセスされるページ即ち「ホット」ページのおおよそ
の理解を与え、これは、仮想／物理ページマッピングポ
リシーに影響するように使用することができる。しかし
ながら、完全な分析を行うのに必要なアドレス情報は、
事象が検出されるときまでに得られない。図１４は、よ
り正確な仮想／物理ページマッピングを実行するのに使
用できるプロセス１４００を示す。ステップ１４１０で
は、マッピングされるべきコードがシステムにおいて実
行される。ステップ１４２０では、メモリをアクセスす
るオペレーション（ロード及び記憶）がサンプリングの
ために選択される。オーバーヘッドを最小にするために
サンプリングはランダムであるのが好ましい。命令が実
行される間に、有効な仮想メモリアドレスが、ステップ
１４３０において、キャッシュ及びＴＬＢミスと共に識
別され、従って、１つの効果として、事象及びアドレス
を特定の命令に直接的に起因させることができる。同様
に、ステップ１４４０において、高いアクセスレートで
隣接ページを識別することができる。ステップ１４５０
では、キャッシュ及びＴＬＢにおけるアクセス競合を減
少するために、仮想／物理ページマッピングを調整する
ことができる。ステップ１４６０では、隣接ページを大
きな「スーパーページ」へと合成し、ページングオーバ
ーヘッドを減少することができる。

【０１０１】キャッシュ又はＴＬＢにおいて捕獲され損
なったメモリ参照の仮想アドレスは特定の命令に直接的
に起因させて、ページマッピングポリシーを誘導するに
必要な情報の形式を厳密に与えることができる。アプリ
ケーションのメモリ参照流に関する情報を使用して、オ
ペレーティングシステムの仮想／物理マッピングポリシ
ーを動的に制御すると、大きな直接マップ式キャッシュ
における競合ミスを首尾良く回避し、スーパーページの
形成によるＴＬＢミスレートを低減し、そしてページの
複写及び移動による非均一メモリアクセス時間（ＮＵＭ
Ａ）マルチプロセッサにおける遠隔メモリ参照の数を減
少することができる。

【０１０２】改良された命令スケジューリング コード最適化の間に行われる１つの重要なタスクは、理
想的な命令スケジューリングである。理想的な命令スケ
ジューリングは、メモリ待ち時間による遅延を最小にす
るようにコードを順序付けし直す。基本的なブロックに
おける隣接命令の静的な順序付けは、前世代のインオー
ダー型ＲＩＳＣプロセッサの場合よりも重要性が低い
が、巨視的な命令スケジューリングは、アウトオブオー
ダー型プロセッサにおいて非常に重要である。命令スケ
ジューリングについての１つの非常に困難なものは、ロ
ード及び記憶のスケジューリングである。これは、静的
なスケジューラが、メモリアクセス命令を最適にスケジ
ュールできるようにする厳密な依存性情報を常に有して
いないからである。加えて、メモリアクセス命令の待ち
時間を厳密に予想することが困難である。命令スケジュ
ーラは、通常、メモリアクセスに関する正確な情報が不
充分であるから、一般に、Ｄキャッシュヒットを仮定し
てロード及び記憶をスケジュールする。或いは又、バラ
ンス型スケジューリングは、ロード当たり等しい量の待
ち時間を含むスケジュールを発生するよう試みる。これ
は、ロード／記憶オペレーションがキャッシュにおいて
常にヒットすると常時仮定することに勝る改良である。

【０１０３】マルチスレッド型プロセッサにおけるスレ
ッドのスケジューリング マルチスレッド型プロセッサにおいては、上記プロファ
イリング方法を用いて得たスレッドのリソース利用に関
する情報を使用して、全体的なリソース利用度及びスル
ープットを最大にするようにスレッドをスケジューリン
グすることができる。２つのスレッドがリソースの相補
的な使い方を有し、例えば、一方のスレッドが主として
整数演算ユニットを使用するが、他方のユニットは主と
して浮動小数点演算ユニットを使用する場合には、２つ
のスレッドが異なる機能的実行ユニットを使用するの
で、２つのスレッドを同時に動作するようにスケジュー
リングすることができる。同様に、２つのスレッドが競
合するリソース使用を有し、例えば、両スレッドが浮動
小数点演算ユニットを頻繁に使用する場合には、それら
を異なる時間に動作するようにスケジューリングするこ
とができる。

【０１０４】図１４ｂは、プロセッサの利用度によりス
レッドをスケジューリングするためのプロセスを示す。
オペレーティングシステムにおいて実行されるスレッド
のリソース利用度がステップ１４７０において測定され
る。ステップ１４７５では、リソースの利用度が収集さ
れ、そしてそのリソース利用度に基づいてスレッドがセ
ットへと分類される。本発明のサンプリングでは、各ス
レッドが、プロセッサにおける各クラスのリソース、例
えば、整数演算ユニット、浮動小数点演算ユニット、メ
モリユニット、分岐ユニット、イッシューユニット等々
をいかに使用するかを決定することができる。ステップ
１４８０では、スレッドのリソース利用度を比較して、
非競合実行スケジュールを決定する。所与のクラスのリ
ソースに対する１組のスレッドの合成利用度により、そ
のクラスのリソースが完全利用状態より著しく多く利用
されている場合には、その組のスレッドを一緒にスケジ
ューリングしてはならず（ステップ１４９０）、逆に、
合成利用度により、そのクラスのリソースが完全利用状
態以下で利用されるか或いは完全利用状態より若干多め
に利用される場合には、それらを一緒にスケジューリン
グするのが有益である（ステップ１４８５）。

【０１０５】図１５は、命令のスケジューリングを実行
するのに使用できるプロセス１５００を示す。マシンコ
ード１５１０は、図１のシステム１００で実行される。
コードが実行される間に、メモリオペレーション命令の
待ち時間がステップ１５２０において上記のように測定
される。多数の命令、例えば、命令対に対する測定値を
ステップ１５３０においてサンプリングすることができ
る。サンプリングは、オーバーヘッドを減少するために
ランダムに行うことができる。同じＰＣをもつ命令に対
してサンプリングされたデータは、ステップ１５４０に
おいて収集されて、例えば、待ち時間のヒストグラム
（ＨＩＳＴ）１５４１が形成される。ステップ１５６０
では、マシンコードが順序付けし直される。この再順序
付けは、収集されたヒストグラム情報１５４１に基づ
く。例えば、長い待ち時間をもつメモリオペレーション
は、それらに依存するオペレーションからできるだけ離
れるように進められる。ステップ１５６０は、リストス
ケジューリング或いはトレーススケジューリングのよう
なスケジューリングアルゴリズムを使用することができ
る。ランダムサンプリングによりロード及び記憶待ち時
間を収集する場合には、各命令を待ち時間のヒストグラ
ムに基づいてスケジューリングすることができる。本発
明の技術は、全キャッシュシュミレーションの経費を被
ることなく待ち時間情報を収集することにより最適化を
導出するように使用できる。

【０１０６】プリフェッチ命令の挿入 図１６は、測定された待ち時間に基づいてプリフェッチ
命令を挿入するためのプロセスを示す。プリフェッチ命
令の挿入は、メモリから返送されるべきデータを待機す
ることにより生じるプロセッサストールを隠す上で助け
となる技術である。データが実際に必要とされる充分前
にメモリシステムに要求を発生し、そして時々はデータ
が必要になると決定される直前にデータを要求すること
により、コンパイラー及びオプチマイザーは、メモリか
らデータをフェッチするための待ち時間のほとんど又は
全部をしばしば隠すことができる。しかしながら、性能
を実際に改善するためには、著しい待ち時間を実際に経
験するメモリオペレーションに対してのみプリフェッチ
命令を挿入することが望ましく、即ち長い待ち時間を実
際に被らないメモリオペレーションにプリフェッチ命令
を挿入すると、付加的なプリフェッチ命令を実行しなけ
ればならないためにプログラムが実際上低速化されてし
まう。メモリオペレーション、特に、プリフェッチから
利益を得るロードオペレーションを識別するために、プ
ログラム内の種々のメモリオペレーションにより経験す
る平均待ち時間に関する統計学的データを収集すること
が所望される。その一般的な構成が図１６に示されてい
る。ステップ１６１０では、プログラム内のメモリオペ
レーションに対するメモリオペレーション待ち時間が測
定される。ステップ１６２０では、同じプログラムカウ
ンタ（ＰＣ）値をもつ命令に対しサンプリングされたメ
モリオペレーション情報が収集される。ステップ１６３
０では、プリフェッチを挿入すべき大きなメモリ待ち時
間をもつメモリオペレーションのサブセットが識別され
る。

【０１０７】ステップ１６４０では、実行頻度情報及び
測定された待ち時間情報に基づき、これらのメモリオペ
レーションに対してプリフェッチ命令を挿入するのに有
益な位置が識別される。ステップ１６５０では、その適
当な位置にプリフェッチ命令が挿入される。待ち時間
は、上記のように測定することができる。１つの方法
は、サンプリングハードウェアでメモリオペレーション
の待ち時間を直接測定することである。別の方法は、ロ
ード命令が対の第１サンプルでありそしてロードからの
データの使用が対の第２サンプルであるである場合に、
対構成でサンプリングを行いそして対を探索することに
よるものである。２つのサンプルにおいて待ち時間情報
を探し、そして特に２つのサンプルのイッシュー時間の
差を探すことにより、ロードオペレーションに対するメ
モリシステム待ち時間を推定することができる。

【０１０８】以上、特定の実施形態について詳細に説明
した。当業者であれば、上記実施形態を変更しても、幾
つかの又は全ての効果が達成されることが明らかであろ
う。それ故、本発明の精神及び範囲内に包含されるこの
ような修正や変更は全て請求の範囲内に含まれるものと
する。

【図面の簡単な説明】

【図１】命令駆動状態サンプリングを伴うコンピュータ
システムのブロック図である。

【図２ａ】サンプリングされた命令を処理するためのマ
イクロプロセッサ実行パイプラインのブロック図であ
る。

【図２ｂ】サンプリングすることのできる状態情報を示
すパイプラインのブロック図である。

【図３】プロファイル情報を記憶するためのレジスタフ
ァイルのブロック図である。

【図４】増強された命令のブロック図である。

【図５】選択された命令をプロファイリングするための
流れ線図である。

【図６】パイプライン待ち時間を測定するための回路を
示す回路図である。

【図７】プロセスの流れ線図である。

【図７ａ】命令をサンプリングするプロセスの流れ線図
である。

【図７ｂ】プロセッサパイプラインにより処理される命
令の特性の統計値を推定するためのプロセスを示す流れ
線図である。

【図８ａ】命令の同時実行を示す図である。

【図８ｂ】命令の同時実行を示す図である。

【図８ｃ】命令の同時実行を示す図である。

【図９】費やされる発生スロットを決定するプロセスを
示す流れ線図である。

【図１０】プロセッササイクル中に処理される命令の平
均数を決定するための装置のブロック図である。

【図１１】命令シーケンスの制御の流れを示すグラフで
ある。

【図１２】制御流を識別するプロセスのデータの流れを
示す図である。

【図１３】分岐経過を収集する装置のブロック図であ
る。

【図１４ａ】ページマッピングプロセスの流れ線図であ
る。

【図１４ｂ】スレッドスケジューリングプロセスの流れ
線図である。

【図１５】メモリ待ち時間の影響を受ける命令スケジュ
ーラの流れ線図である。

【図１６】プリフェッチ命令を挿入するためのプロセッ
サ１６００の流れ線図である。

【符号の説明】

１００ コンピュータシステム １１０ プロセッサ １１１ パイプライン １１２ データキャッシュ（Ｄキャッシュ） １１３ 命令キャッシュ（Ｉキャッシュ） １１９ プロセッサ状態をサンプリングするハードウェ
ア １２０ オフチップメモリ １２１ 汎用キャッシュ １２２ 揮発性メモリ １２３ 永続的メモリ １３０ 入力／出力インターフェイス（Ｉ／Ｏ） １４０ バスライン ２００ 実行パイプライン ２０５ 変換ルックアサイドバッファ（ＴＬＢ） ２１０ フェッチユニット ２２０ マップユニット ２３０ イッシューユニット ２４０ 実行ユニット ２５０ リタイアユニット

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェフリー エイ ディーン アメリカ合衆国 カリフォルニア州 94025 メンロ パーク フィフティーン ス アベニュー 884 (72)発明者 ジェームズ イー ヒックス アメリカ合衆国 マサチューセッツ州 02159 ニュートン ボウ ロード 63 (72)発明者 ダニエル エル ライブホールズ アメリカ合衆国 マサチューセッツ州 02138 ケンブリッジ リーザーヴォア ストリート 74 (72)発明者 エドワード ジェイ マックレーラン アメリカ合衆国 マサチューセッツ州 01746 ホーリストン ワシントン パー ス ５ (72)発明者 カール エイ ウォールドスパージャー アメリカ合衆国 カリフォルニア州 94027 アサートン パーク ドライヴ 27 (72)発明者 ウィリアム イー ウィール アメリカ合衆国 カリフォルニア州 94114 サン フランシスコ クリッパー ストリート 280

Claims (33)

【特許請求の範囲】
1. 【請求項１】 複数の処理段を有するシステムのプロセ
   ッサパイプラインにおいて命令をサンプリングする装置
   であって、 パイプラインの第１段へ命令をフェッチする手段と；フ
   ェッチされた命令のいずれかのサブセットを選択された
   命令として識別する手段と；選択された命令のいずれか
   がパイプラインのいずれかの段にある間にシステムの状
   態情報をサンプリングする手段と；全ての選択された命
   令がパイプラインを出るときにソフトウェアに通知し
   て、ソフトウェアがいずれかの状態情報を読み取れるよ
   うにする手段と；を備えたことを特徴とする装置。
2. 【請求項２】 上記選択された命令は、パイプラインに
   より完全に処理される有効命令と、パイプラインを出る
   前にアボートされる有効命令と、パイプラインを出る前
   に部分的に処理される無効命令とを含む請求項１に記載
   の装置。
3. 【請求項３】 上記命令は、それらがサンプリングのた
   めに選択されたことを指示する付加的なフィールドによ
   り識別される請求項１に記載の装置。
4. 【請求項４】 上記付加的なフィールドは、パイプライ
   ンにおける各命令の多数のサンプルビットと、上記サン
   プリング手段をアクチベートするようにサンプルビット
   をアサートする手段とを備えた請求項３に記載の装置。
5. 【請求項５】 上記付加的なフィールドは、命令番号を
   記憶し、そして比較器レジスタに維持される請求項３に
   記載の装置。
6. 【請求項６】 サンプリングされた各命令に関連した状
   態情報は、そのサンプリングされた命令を識別するフィ
   ールドによりインデックスされるレジスタに記憶される
   請求項１に記載の装置。
7. 【請求項７】 上記状態情報は、サンプル間事象カウン
   トを含む請求項１に記載の装置。
8. 【請求項８】 上記事象カウントは、一対の選択された
   命令のフェッチ間のサイクル数を含む請求項７に記載の
   装置。
9. 【請求項９】 上記事象カウントは、一対の選択された
   命令間にリタイアする命令の数を含む請求項７に記載の
   装置。
10. 【請求項１０】 上記事象カウントは、一対の選択され
    た命令間にパイプラインの特定の段に入る命令の数を含
    む請求項７に記載の装置。
11. 【請求項１１】 上記事象カウントは、一対の選択され
    た命令間にフェッチされた分岐命令の数を含む請求項７
    に記載の装置。
12. 【請求項１２】 上記事象カウントは、プロセッサ、メ
    モリシステム、ネットワーク又はＩ／Ｏサブシステム事
    象の測定値を含む請求項７に記載の装置。
13. 【請求項１３】 複数のサンプリングカウンタと、 各サンプリングカウンタを特定の値に初期化する手段
    と、 上記サンプリングカウンタの１つが特定事象に応答して
    オーバーフローしたときに上記選択手段をアクチベート
    する手段と、を更に備えた請求項１に記載の装置。
14. 【請求項１４】 上記選択手段は、上記複数のサンプリ
    ングカウンタがのどれがオーバーフローするかに基づい
    て個別のタグで上記選択された命令を識別する手段を含
    む請求項１３に記載の装置。
15. 【請求項１５】 各特定の値は、サンプリングの平均頻
    度を特定するためにある間隔の数字からランダムに選択
    される請求項１３に記載の装置。
16. 【請求項１６】 上記数字の間隔のサイズは、サンプリ
    ングの平均頻度を動的に変えるように変更される請求項
    １５に記載の装置。
17. 【請求項１７】 上記ランダム数字はソフトウェアで計
    算され、そしてハードウェアレジスタに記憶される請求
    項１５に記載の装置。
18. 【請求項１８】 上記ランダム数字は、ハードウェア回
    路により発生される請求項１５に記載の装置。
19. 【請求項１９】 上記状態情報は、選択された命令を識
    別する情報を含む請求項１に記載の装置。
20. 【請求項２０】 上記状態情報は、選択された命令のア
    ドレスを含む請求項１９に記載の装置。
21. 【請求項２１】 上記状態情報は、選択された命令を実
    行するプロセスの識別を含む請求項１９に記載の装置。
22. 【請求項２２】 上記状態情報は、アドレススペース番
    号を含む請求項１９に記載の装置。
23. 【請求項２３】 上記状態情報は、ハードウェアコンテ
    クスト識別子を含む請求項１９に記載の装置。
24. 【請求項２４】 上記状態情報は、スレッド識別子を含
    む請求項１９に記載の装置。
25. 【請求項２５】 上記ソフトウェアに通知する手段は、
    全ての選択された命令がパイプラインを出るときに割り
    込みを発生する請求項１に記載の装置。
26. 【請求項２６】 上記ソフトウェアに通知する手段は、
    全ての選択された命令がパイプラインを出たことを指示
    するためにソフトウェアによりポーリングできるフラグ
    を含む請求項１に記載の装置。
27. 【請求項２７】 上記特定の事象は、有効なフェッチさ
    れた命令である請求項１３に記載の装置。
28. 【請求項２８】 フェッチのレートがクロックにより決
    定され、そして上記特定の事象は、単一の潜在的なフェ
    ッチされた命令に対応するクロックサイクルの小区分で
    ある請求項１３に記載の装置。
29. 【請求項２９】 上記特定の事象は、パイプラインのい
    ずれかの特定の段への命令の導入である請求項１３に記
    載の装置。
30. 【請求項３０】 上記状態情報は、選択された命令のリ
    タイア／アボート状態を含む請求項１に記載の装置。
31. 【請求項３１】 上記状態情報は、選択された命令を処
    理する間に検出される事象を含む請求項１に記載の装
    置。
32. 【請求項３２】 上記状態情報は、選択された命令によ
    り経験する待ち時間を含む請求項１に記載の装置。
33. 【請求項３３】 上記事象カウントは、パイプラインの
    特定の段に入る一対の選択された命令間に経過するサイ
    クル数を含む請求項７に記載の装置。