JPH11288373A - コンピュ―タ・システム - Google Patents

Abstract

(57)【要約】 【課題】コンピュータ・システムのプロセッサのレジス
タについて、特定のレジスタを読み取ろうとする命令が
停止するかどうかを示す使用可能状態を保持するデータ
構造を含むコンピュータ・システムを提供する。 【解決手段】待ち時間調査命令はそのデータ構造からレ
ジスタの使用可能状態を検索し、レジスタの中にこの使
用可能状態を格納する。その後、条件分岐命令が、レジ
スタの中に格納された使用可能状態に基づいて、プログ
ラム実行パスを決定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、コンピュータ・シ
ステムの中で実行されるコンピュータ命令に関するもの
である。より詳細には、本発明は、レジスタの内容への
アクセスがコンピュータ・システム上のプログラム実行
を停止する原因となるかどうかを判定し、それによって
メモリの待ち時間を示すコンピュータ命令に関するもの
である。

【０００２】

【従来の技術】一般的なコンピュータ・システムには、
１つまたは複数のプロセッサ、メモリ・システム、およ
び記憶媒体が含まれる。メモリ・システムには、一般に
メイン・メモリ、およびメイン・メモリとプロセッサの
間に接続された、１つまたは複数のキャッシュ・メモリ
が含まれる。記憶媒体は、ハードディスク装置、フロッ
ピー・ディスク装置、ＣＤ−ＲＯＭ装置、および同様の
物を備える。

【０００３】コンピュータ・システムは、連続する命令
から構成されるコンピュータ・プログラムを実行するこ
とによってタスクを実行する。コンピュータ・システム
の性能は、命令を実行する速度に著しく影響される。

【０００４】１つの一般的なタイプの命令は、メモリか
らオペランドを検索しそのオペランドをプロセッサのレ
ジスタ中に格納するロード命令である。オペランドをキ
ャッシュ・メモリの中に格納した場合、それは迅速に検
索される。これは当業者には「キャッシュ・ヒット(cac
he hit)」として周知である。しかしながら、オペラン
ドがメイン・メモリの中でのみ使用可能である場合、オ
ペランドをレジスタの中にロードするのにかなり長い時
間がかかることもある。これは当業者には「キャッシュ
・ミス(cache miss)」として周知である。キャッシュ・
ミスの後、オペランドをメモリからレジスタにロードす
ることを必要とする命令に出会うまで、多くのコンピュ
ータ・システムでは命令を実行し続ける。このような命
令に出会った時、プロセッサはその命令の実行を停止
し、ロードが終了するのを待つ。この技術は当業者には
「ストール・オン・ユーズ(stall on use)」として周知
であり、この方式をサポートするキャッシュ・メモリ
は、「非ブロッキング・キャッシュ(non-blocking cach
e)」として周知である。

【０００５】プロセッサの性能はメイン・メモリ・シス
テムの性能よりも急速に向上している。現在のコンピュ
ータ・システムでは、メイン・メモリからオペランドを
検索するのに１００プロセッサ・サイクルまでも必要で
あり、将来のコンピュータ・システムでは１０００以上
のプロセッサ・サイクルが必要になるだろうと予測され
る。従って、最適なシステム性能を達成するため、プロ
セッサが、オペランドをメイン・メモリから読み出して
いる間に、実行することのできる他の命令を有すること
を保証することが重要である。理想的には、ロードが完
了するのを待つ間プロセッサは停止してはならない。

【０００６】いくつかのコンピュータ・システムでは順
序を入れ替えてすなわちアウト・オブ・オーダ(out-of-
order)で命令を実行することができ、従ってロードが完
了するのを待つ間に他の命令を実行することによって停
止を延期することができる。しかしながら、アウト・オ
ブ・オーダの実行は複雑なハードウェアを必要とし、ア
ウト・オブ・オーダで実行することに適した命令ウィン
ドウは比較的小さい（２００〜３００命令以下）。さら
に、ＣＰＵのより多くの論理素子がアウト・オブ・オー
ダ実行のサポートに占有されるので、命令（インストラ
クション）によって指定される機能を遂行するために使
用可能な論理素子はより少なくなる。

【０００７】他の技術では、オペランドが使用不能なた
め現在のストリームの命令を続行することができないと
判定した時、プロセッサがコンテキストを切り換えるこ
とができる。例えば、ＣＰＵ内部で複数のコンテキスト
を保持することができ、停止時には他のコンテキストに
単に切り換える。しかしながらこの方法は、複数のコン
テキストを保持するための追加のハードウェアを必要と
し、従ってアウト・オブ・オーダの実行のように命令が
指定する機能を実行するのに使用可能なハードウェアを
減少させる。また停止時に割り込みが発生し、ソフトウ
ェアが何か他のスレッドもしくはプロセスに切り換わる
こともあり得る。ディスクからのデータの検索などのよ
り長い待ち時間に関してこの方法がうまく動作する一
方、メイン・メモリからのデータのアクセスなどより短
い待ち時間を取り扱う際起こるオーバヘッドによって、
この方法は不可能になる。

【０００８】他の技術は、コンピュータ・プログラムの
コンパイル時、実行する命令に関する様々なオペランド
の待ち時間をモデル化することである。待ち時間モデル
に基づいて命令をスケジュールすることによって、コン
パイラは停止をかなり削減することができる。例えば、
キャッシュ・ミスが３０ＣＰＵサイクルを必要とするだ
ろうと待ち時間モデルが示し、特定のロード命令がキャ
ッシュ・ミスを派生するだろうとコンパイラが判定する
ことができた場合、コンパイラはそのオペランドが必要
になる少なくとも３０サイクル前にそのオペランドを検
索するためのメモリ・プリフェッチ・オペレーションを
スケジュールすることができる。

【０００９】不幸にも、コンパイル時に待ち時間を予測
することは、多くの場合困難である。コンパイラが、特
定のロードがキャッシュ・ミスもしくはキャッシュ・ヒ
ットを引き起こすかどうかを判定することができない場
合もある。さらに、多くの場合、単一バージョンの「収
縮包装（シュリンク・ラップ：shrink wrup）」のソフ
トウェアが特定の命令セットのために市販される。しか
しながら、性能およびアーキテクチャにおいて実質的に
異なる広く多様なコンピュータ・システム上でこのよう
なソフトウェアを実行することもできる。例えば、Ｐｅ
ｎｔｉｕｍ（Ｒ）（ペンティアム（商標））ＣＰＵを搭
載し、外部Ｌ２キャッシュを持たず、高速ページ・モー
ドＤＲＡＭメモリを持つラップトップ・コンピュータか
ら、（各ＣＰＵがＬ１およびＬ２キャッシュを持つ）複
数のＰｅｎｔｉｕｍ（Ｒ）ＩＩ（ペンティアム（商標）
ツー）ＣＰＵ、および同期式ＤＲＡＭメモリを持つコン
ピュータ・ワークステーションまでの範囲にわたるコン
ピュータ・システム上で、Ｉｎｔｅｌ ｘ８６（インテ
ル ｘ８６シリーズ）命令セットで書かれたプログラム
を実行することもできる。

【００１０】Mark Horowitz、Margaret Martonosi、Tod
d Mowry、およびMichael Smithによる「Informing Load
s: Enabling Software to Observe and React to Memor
y Behavior（通知ロード：ソフトウェアがメモリ動作に
対して監視し反応することができるようにすること）」
という題名の１９９５年７月に出版された第１の論文
と、「Informing Memory Operations: Providing Memor
y Performance Feedbackin Modern Processors（通知メ
モリ・オペレーション：現代のプロセッサにおけるメモ
リ・パフォーマンス・フィードバックの提供）」という
題名の第２の論文に、ダイナミックで多様な待ち時間に
ついて説明している。本明細書ではこれら両方の論文を
参照する。これらの論文では、「informing load instr
uctions（通知ロード命令）」と呼ばれる命令のクラス
を提案している。ロード・オペレーションがキャッシュ
・ヒットを引き起こす場合、通知ロード命令によって、
スキップされる通知ロード命令の直後の命令が実行さ
れ、ロード・オペレーションがキャッシュ・ミスを引き
起こす場合、通知ロード命令の直後の命令が実行され
る。通知ロードは実行を停止させない非ブロッキング・
ロードである。通知ロード・オペレーションの直後に分
岐命令をスケジュールすることによって、通知ロード・
オペレーションが原因であるキャッシュ・ミスを保守す
る間、通知ロード命令によってコンパイラが代替の動作
をスケジュールすることができる。

【００１１】通知ロード・オペレーションは、特定のオ
ペランドが第１レベルのキャッシュの中にあるかどうか
を示すが、待ち時間の量を示さない。オペランドがＬ２
キャッシュの中にあることもあり、メイン・メモリの中
にあることもあり、あるいは他のＣＰＵのキャッシュの
中にダーティ・ラインとして存在することもある。従っ
て通知ロード・オペレーションは、コンパイラに待ち時
間の量に基づいて代替のコード・スレッドをスケジュー
ルする方法を提供しない。また、通知ロードそれ自体の
実行後レジスタの内容が使用可能であることを確認する
プログラムのためのメカニズムも、通知ロードは提供し
ない。

【００１２】

【発明が解決しようとする課題および課題を解決するた
めの手段】本発明は、コンピュータ・システムのプロセ
ッサのレジスタについての使用可能状態を保持するデー
タ構造を含むコンピュータ・システムであって、この使
用可能状態は特定のレジスタを読み取ろうとする命令が
停止するかどうかを示す。このコンピュータ・システム
はまた、１つまたは複数のレジスタの使用可能状態に基
づいて、プログラム実行のパスを変更する１つまたは複
数の命令を復号し実行することができる命令復号／実行
回路も含む。

【００１３】一実施形態において、待ち時間調査命令は
そのデータ構造からレジスタの使用可能状態を検索し、
レジスタの中にこの使用可能状態を格納する。その後、
条件分岐命令が、レジスタの中に格納された使用可能状
態に基づいて、プログラム実行パスを決定する。別の実
施形態では、条件分岐命令がレジスタの使用可能状態を
判定するため直接データ構造を照会し、使用可能状態に
基づいて実行パスを決定する。

【００１４】本発明は、メモリ・オペレーションの待ち
時間をプログラムに公開し、従ってコンパイラが変化す
る待ち時間に基づいて代替の実行スレッドをスケジュー
ルすることができる。レジスタの内容の使用可能性に基
づいて代替の実行スレッドをスケジュールすることによ
って、停止が最小限になる。コンパイラが、キャッシュ
・ヒットおよびキャッシュ・ミスが引き起こす待ち時間
を正確にモデル化することができる場合、予測されるキ
ャッシュ・イベントに対応する定義済の時間間隔でレジ
スタ内容の使用可能性をチェックするようコードをスケ
ジュールすることができる。あるいは、コンパイラが待
ち時間を正確にモデル化することができない場合、コン
パイラは、定期的にレジスタ内容の使用可能性に関して
チェックするようコードをスケジュールすることができ
る。

【００１５】さらにまた、コンパイラはコードを最適化
するために本発明を使用することもできる。本発明は、
プログラム実行中にデータを収集するための強力な方法
を提供する。プログラムの再コンパイル時、実行ファイ
ルを最適化するためこの収集したデータを使用すること
ができる。また、コンパイラは、パフォーマンスを監視
し、基本的には実行時に「オン・ザ・フライ(on-the-fl
y)で」それ自体を再コンパイルするコードをスケジュー
ルするため、本発明を使用することもできる。

【００１６】本発明の最も推進する特徴の１つは、多数
の現代のコンピュータ・アーキテクチャの中で実施する
のが容易なことである。「ストール・オン・ユーズ」技
術をサポートし、「非ブロッキング・キャッシュ」を含
むプロセッサは一般に、プロセッサのレジスタについて
の使用可能状態を提供することができるデータ構造を含
む。このようなプロセッサ設計において、条件分岐命令
がレジスタの使用可能状態をテストすることができるよ
うにする命令をコード化するのは、比較的容易な設計の
仕事である。

【００１７】

【発明の実施の形態】本発明は、オペランドがレジスタ
の中で使用可能かどうかを判定するコンピュータ命令を
実行することができる、コンピュータ・システムであ
る。様々な時間間隔で本発明の命令を実行することによ
って、メモリ・ロード・オペレーションの待ち時間を調
査することができる。

【００１８】図１は、従来技術のコンピュータ・システ
ム１０のブロック図である。コンピュータ・システム１
０は、中央処理装置（ＣＰＵ）１２、レベル１（Ｌ１）
キャッシュ・メモリ装置１４、レベル２（Ｌ２）キャッ
シュ・メモリ装置１６、およびメイン・メモリ装置１８
を含む。Ｌ１キャッシュ・メモリ装置１４は、ＣＰＵ１
２に密接に接続する比較的少量の高速で高価なメモリを
備え、メイン・メモリ装置１８のメモリ内容のサブセッ
トを格納する。多数の従来技術のＣＰＵは、ＣＰＵそれ
自体と同一の集積回路上にＬ１キャッシュを含む。一般
に、１または２命令クロック・サイクル内で、Ｌ１キャ
ッシュ・メモリ装置１４からＣＰＵ１２のレジスタの中
にメモリ・オペランドをロードすることができる。

【００１９】Ｌ１キャッシュ・メモリ装置１４と比較す
ると、Ｌ２キャッシュ・メモリ装置１６は、比較的大き
な（かつ比較的遅い）量のメモリを備える。Ｌ２キャッ
シュ・メモリ装置１６もまた、メイン・メモリ装置１８
の内容のサブセットを格納する。一般に、数命令クロッ
ク・サイクル内でＬ２キャッシュ・メモリ装置１６から
メモリ・オペランドをロードすることができる。

【００２０】メイン・メモリ装置１８は、大量で比較的
遅いメモリを備える。メイン・メモリ装置１８からＣＰ
Ｕ１２のレジスタの中にメモリ・オペランドをロードす
るのに、１００以上の命令クロック・サイクルを要する
こともある。

【００２１】コンピュータ・システム１０が多数の従来
技術の構成を表す一方、もちろん多数の他の構成もあ
る。例えば、より多数のもしくはより少数のキャッシュ
・メモリを持つことが一般的である。また、数個のキャ
ッシュを共用し他のキャッシュに排他的アクセスを行う
ことができる、複数のプロセッサを持つことも一般的で
ある。

【００２２】メモリ・オペレーションの待ち時間が、特
定のメモリ・オペランドを特定のキャッシュ・メモリ装
置の中に格納するかどうかによって異なることに留意さ
れたい。コンパイラが、オペランドは特定のキャッシュ
・メモリ装置の中にあるかどうかを予測し、それに従っ
てコードをスケジュールすることができることが頻繁に
ある。しかしながら、コンパイラが、キャッシュ・メモ
リのいずれかにオペランドがあるかどうかを判定するこ
とができないこともまた一般的である。

【００２３】多数の従来技術のコンピュータ・システム
において、オペランドをメモリからレジスタの中にロー
ドするロード命令がキャッシュ・ミスを派生した時、Ｃ
ＰＵは停止しない。むしろ、ＣＰＵは、そのレジスタの
内容を必要とする後の命令に到達するまで命令の実行を
続行する。オペランドをメモリからロードし終っていた
ら、この後の命令を実行する。オペランドがメモリから
まだロードされていなかった場合、キャッシュ・ミスへ
の手当てが済むまで、（少なくとも後の命令の）実行を
中断する。キャッシュ・ミスに対する手当てが済んだと
ころで、この後の命令から実行が再開される。この技術
は当業者には「ストール・オン・ユーズ」として周知で
あり、この方式をサポートするキャッシュ・メモリは
「非ブロッキング・キャッシュ」として周知である。

【００２４】図２は、レジスタの内容が使用可能でない
時にプロセッサが実行を中断すべきかどうかを判定する
ための一般的な従来技術の技法の簡略図である。図２に
おいて、ＣＰＵ１２はレジスタ２０、使用不能フラグ２
２、および停止信号装置２４を含む。命令復号装置、浮
動小数点実行装置、整数実行装置、メモリ・アクセス装
置、および相当物が提供する機能など他のＣＰＵ機能を
ボックス２６で包括的に表現する。

【００２５】ＣＰＵ１２が実行を中断すべきかどうかを
判定する方法を理解するため、ＣＰＵ１２がレジスタ１
（ｒ₁）の内容で指定されたメモリ位置の内容をレジス
タ０（ｒ₀）の中にロードするロード命令の実行を開始
したと仮定されたい。この命令は下記のように表現する
ことができる。

【００２６】ｌｄ ｒ₀＝［ｒ₁］

【００２７】さらに、ｒ₁の内容によって指定されたメ
モリ位置の内容がＬ１キャッシュ・メモリ装置１４の中
にあると仮定されたい。命令の実行時、ｒ₀の内容が使
用不能であることを示すため、ｒ₀に関連する使用不能
フラグ２２を「１」にセットする。次の命令クロック・
サイクルで、ｒ₀をＬ１キャッシュ・メモリ装置１４よ
りロードし、ｒ₀の内容が使用可能であることを示すた
め、ｒ₀に関連する使用不能フラグ２２を「０」にクリ
アする。

【００２８】ここで、次の命令が下記のものであると仮
定されたい。

【００２９】ａｄｄ ｒ₃＝ｒ₀，ｒ₂

【００３０】この命令は、ｒ₀およびｒ₂の内容を加算
し、その結果をｒ₃の中に格納する。ｒ₂の内容が使用可
能であり、従ってｒ₂に関連する使用不能フラグ２２を
「０」にクリアしたと仮定されたい。命令の実行開始
時、停止信号装置２４はｒ₀およびｒ₂に関連する使用不
能フラグ２２に基づいて停止信号を生成する。両方のレ
ジスタの内容が使用可能であるため、停止信号を表明せ
ず加算命令を実行する。

【００３１】次に、ｒ₁の内容によって指定されたメモ
リ位置の内容を、キャッシュ・メモリ装置１４もしくは
１６ではなく、メイン・メモリ１８の中に格納すること
を除いて、同一順の命令を実行すると仮定されたい。従
って、次の命令クロック・サイクルで加算命令を実行す
る時、ｒ₀の内容は使用可能ではない。停止信号装置２
４が停止信号を表明（アサート）し、それをＣＰＵ１２
がメイン・メモリ装置１８からｒ₀の中にそのメモリの
内容をロードするまで実行を停止するために使用する。
メモリの内容がロードされた時、加算命令の実行が完了
する。

【００３２】もちろん、図２を参照して上記で述べた例
は簡略化されている。パイプライン実行をサポートする
ＣＰＵでは、より複雑なメカニズムによって使用不能フ
ラグ２２が提供する機能が提供される。命令フェッチ
（ＩＦ）の段階と、命令復号およびレジスタ・フェッチ
（ＲＤ）の段階と、実行（ＥＸ）の段階と、データ・メ
モリ・アクセス（ＭＥ）の段階と、レジスタ書き戻し
（ＷＢ）の段階から構成される、５段階パイプラインを
持つＣＰＵについて考察されたい。また、かかるプロセ
ッサが、トランザクションの結果を受け取る宛先レジス
タを指定するレジスタ・アドレスを含むテーブルの中に
各アクティブ・エントリを持つ、未解決メモリ読取トラ
ンザクション・テーブルを有すると仮定されたい。レジ
スタの内容が使用可能でないため命令が停止する場合、
ＲＤ段階で停止する。ＲＤ段階で停止信号を生成するた
め、パイプラインの後の段階中の任意の命令、または未
解決メモリ読取トランザクション・テーブル中の任意の
トランザクションが、ＲＤ段階で読み取るレジスタの中
にデータを格納するかどうかを判定しなければならな
い。従って、このようなプロセッサの中では、ＲＤ段階
の命令のソース・レジスタを、後の段階の命令の宛先レ
ジスタ、および未解決メモリ読取トランザクション・テ
ーブルのアクティブ・エントリの中に格納する宛先レジ
スタと比較する一連の比較装置およびＯＲゲートが、全
ての比較装置からの結果を共にＯＲすることによって生
成した停止信号を使って、図２の中の使用不能フラグ２
２および停止信号装置２４が実行する機能を実行する。
もちろん、当業者には、レジスタの内容が使用可能であ
るかどうかを追跡するため、多様に異なるデータ構造お
よび技術を使用することもできることを認識するであろ
う。さらに、当業者はまた、使用不能であるレジスタの
内容を必要とする命令に対してのみ実行を停止する必要
があることを認識するであろう。他の命令の実行、およ
び他の無関係のＣＰＵ機能は続行してもよい。

【００３３】本発明は、レジスタの内容が使用可能であ
るかどうか、またはそのレジスタにアクセスすることに
よって実行の停止を引き起こすかどうかを、コンピュー
タ・プログラムが確認することができるようにするため
のメカニズムを提供する。図３はＣＰＵ２８の簡略化し
たブロック図である。図３は、本発明を実施するため図
１のＣＰＵ１２をどのように修正するかを示す。ＣＰＵ
１２と同様に、ＣＰＵ２８はレジスタ３０、使用不能フ
ラグ３２、および停止信号装置３４を含む。ＣＰＵ２８
はまた、任意の使用不能フラグ３２の内容を任意のレジ
スタ３０の中に発送あるいはルーティングすることがで
きるマルチプレクサ３６も含む。最後に、ボックス３８
が表すＣＰＵ機能は、本発明に従って命令を復号し（下
記に述べる）、マルチプレクサ３６を制御することがで
きる回路を含む。

【００３４】マルチプレクサ３６は、使用不能フラグを
レジスタの中にリンクすることができる任意のメカニズ
ムを表す。本発明を理解するため、マルチプレクサ３６
を使用不能フラグ３２およびレジスタ３０とリンクする
別々のデータ・パスを示す。しかしながら、当業者は、
レジスタの中に至る１ビットの共通データ・パスを使用
不能フラグの１つに格納された値まで延ばすことによっ
て、マルチプレクサ３６が表す機能を実施することがよ
くあることを認識するであろう。さらに図２を参照して
上記で述べたように、パイプライン・プロセッサでは、
パイプラインの後の段階および未解決メモリ読取トラン
ザクション・テーブルの中で、ソース・レジスタ・アド
レスを宛先レジスタ・アドレスと比較する比較装置が、
使用不能フラグ３２が実行する機能を実行することもで
きる。本明細書で使用するように、「使用不能フラグ」
という用語はこのような方法で生成された使用可能状態
を含む。

【００３５】本発明によるコンピュータ命令を復号する
ため必要とされる回路をボックス３８で表現する。当従
来技術の技術者は、本発明による命令に関してオペレー
ション・コードを適正に定義し、その命令を復号するた
めの適正な復号論理を設計し、本明細書で述べた機能を
実施するようマルチプレクサ３６を操作するため、本明
細書の教示をどのように適合させるかを認識するであろ
う。

【００３６】待ち時間調査命令と呼ばれる本発明による
命令について考察されたい。このような命令の１つの書
式（フォーマット）は、次の通りである。

【００３７】ｌｐｒｏｂｅ ｒ_i=ｒ_j

【００３８】ｌｐｒｏｂｅ命令の実行時、ｒ_jに関連す
る使用不能フラグ３２をｒ_iの中に格納する。従って、
ｒ_jの内容が使用可能である場合ｒ_iの内容は「０」であ
り、ｒ_jの内容が使用不能である場合、ｒ_iの内容は
「１」である。次に、レジスタｒ_jにアクセスする命令
を実行すべきかどうかを判定するため、条件分岐命令を
介してｒ_iの内容をテストする。もちろん、本発明によ
る他の命令もまた可能である。例えば一実施形態では、
プロセッサが動作の分岐を制御するために使用する条件
（または属性あるいは述語（predicate)）レジスタを含
むこともあり、指定された使用不能フラグ３２を指定さ
れた条件レジスタに転送するよう、ｌｐｒｏｂｅ命令を
定義することもできる。別の実施形態では、条件分岐が
基づくこともできるレジスタとして使用不能フラグを取
り扱うよう、分岐命令のクラスを定義することもでき
る。このような命令に関する１つの書式は、次の通りで
ある。

【００３９】ｂr ｒ_jｕｆ，ｍｉｓｓ

【００４０】このような命令は、ｒ_jに関連する使用不
能フラグが使用不能である場合のみ、アドレスｍｉｓｓ
に分岐する。

【００４１】もちろん、多数の他の命令コード化が可能
である。本発明の鍵は、コンピュータ命令が、レジスタ
をアクセスする命令が停止するかどうかを判定するた
め、レジスタの内容が使用可能であるかどうかを判定す
るのに使用するデータ構造もしくは技術を照会すること
もでき、その照会結果に基づいて実行スレッドを変更す
ることができることである。従って、本発明はレジスタ
・ロード・オペレーションの待ち時間をコンパイラに公
開し、それによってコンパイラが、レジスタの内容が使
用可能であるかどうかに基づいて代替のスレッドをスケ
ジュールすることができる。

【００４２】図４は、本発明のコンピュータ命令の簡単
な応用例を示す。図３の中のＣＰＵ２８などの本発明に
よるＣＰＵが、図１の中のコンピュータ・システム１０
などのＬ１およびＬ２キャッシュ装置とメイン・メモリ
装置を有するコンピュータ・システムの中に存在すると
仮定されたい。さらに、コンパイラがＬ１およびＬ２の
キャッシュ・ヒットおよびキャッシュ・ミスの待ち時間
を予測する正確な待ち時間モデルを持ち、ｒ₁の内容で
指定されたメモリの内容をｒ₀の中にロードし、ｒ₀の内
容とｒ₂の内容を加算し、その結果をｒ₃の中に格納する
コードを、コンパイラがスケジュールしなければならな
いと仮定されたい。また、このコンパイラがｒ₂の内容
が使用可能であることを予測することができることも仮
定されたい。

【００４３】最初に、コンパイラはコード・セグメント
４０をスケジュールする。コード・セグメント４０の最
初の命令がｒ₁の内容で指定されたメモリの内容をｒ₀の
中にロードする。次の命令は、ｒ₀に関連する使用不能
フラグ３２の内容と一緒にレジスタｒ₄をロードするｌ
ｐｒｏｂｅ命令である。次の命令は、レジスタｒ₄の内
容をテストする分岐命令である。ｒ₀の内容が使用可能
である場合、ｒ₄は「０」となり分岐は失敗し、これは
Ｌ１キャッシュ・ヒットと一致する。次の命令は、ｒ₀
の内容とｒ₂の内容を加算しその結果をｒ₃の中に格納す
る。セグメント４０中の残りのコードは、Ｌ１キャッシ
ュ・ヒットの仮定に基づいて最適化されたコードであ
る。ｒ₀の内容が使用不能である場合、ｒ₄は「１」とな
り、分岐はアドレスあるいはラベルｍｉｓｓ＿１にある
コード・セグメント４２に実行を誘導する。

【００４４】最初にコード・セグメント４２は、Ｌ１キ
ャッシュ・ミスの仮定に基づいて最適化した一連の命令
を実行する。コンパイラは、ｒ₀の中にロードしたメモ
リの内容をＬ２キャッシュの中に格納すると仮定し、ｒ
₁の内容によって指定されたメモリの内容をＬ２キャッ
シュから検索することができるとコンパイラが予測する
時間の間に、実行することもできる他の命令を識別しス
ケジュールする。これらの命令の実行後、ｒ₀に関連す
る使用不能フラグ３２と一緒にｒ₄をロードする他のｌ
ｐｒｏｂｅ命令を実行する。次の命令はｒ₄の内容をテ
ストする分岐命令である。ｒ₀の内容が使用可能である
場合、この分岐は失敗し、これはＬ２キャッシュ・ヒッ
トと一致する。次に、加算命令およびＬ２キャッシュ・
ヒットに基づいてスケジュールした他の命令によって実
行が続行される。しかしながら、ｒ₀の内容が使用可能
でない場合、分岐はアドレスｍｉｓｓ＿２にあるコード
・セグメント４４に行く。

【００４５】コード・セグメント４４の中で、コンパイ
ラはＬ２キャッシュ・ミスのために最適化したコードの
最初の部分をスケジュールしている。コンパイラの待ち
時間モデルは、最初の部分を実行した後、Ｌ２キャッシ
ュ・ミスを保守することができるのに十分な時間が経過
し、ｒ₀の内容が使用可能になるだろうと予測する。そ
の後、Ｌ２キャッシュ・ミスの仮定に基づいて実行する
ようコンパイラがスケジュールした他の命令と共に、加
算命令を実行する。

【００４６】前述の例は、未知であるが限定された定義
済の待ち時間セットを有するレジスタ・ロードの周辺の
コードをスケジュールするため、コンパイラが本発明の
命令をどのように使用することができるかを示す。ｌｐ
ｒｏｂｅ命令を定期的な時間間隔でスケジュールするこ
とによって、ロードしたデータが他のＣＰＵのダーティ
・キャッシュ・ラインの中に保持されている時など、待
ち時間セットを定義することができない時もまたコード
をスケジュールすることができる。

【００４７】さらにまた、コンパイラがコードを最適化
するのにも本発明を使用することができる。例えば、プ
ロファイル・ベースの最適化（ＰＢＯ:profile-based o
ptimization）実行セッションの間にデータを収集する
ことは、当業者には周知である。その場合、最適化実行
可能版プログラムを作るため、この収集したデータを使
用してプログラムを再コンパイルする。キャッシュ・ミ
スを検出しメモリ待ち時間を計測するためにｌｐｒｏｂ
ｅ命令を使用することもできるので、本発明は、ＰＢＯ
セッションの間にデータを収集するための強力な方法を
提供する。

【００４８】本発明の別の応用例は、連続実行時最適化
である。コンピュータ・システム構成の数は急増し続け
ると予想される。将来、異なるメモリ構成やＣＰＵの数
を持つ様々なコンピュータ・システム上で、１つのコン
パイル済コンピュータ・プログラムが効果的に実行され
ることが一般的になるであろう。プログラムのコンパイ
ル時、可能な構成をすべて予測するのは実用的ではな
い。従って、パフォーマンスを監視し、基本的に実行時
「直接」再コンパイルするコードをプログラムが含むこ
とが期待される。本発明は、プログラムがそのパフォー
マンスを監視し、それによってコードを再スケジュール
するためのメカニズムを提供する。従来技術と異なり、
本発明によって、プログラムがレジスタ・ロードよりキ
ャッシュ・ヒットを派生するかどうかを判定することが
できるだけでなく、プログラムがまた、レジスタの内容
が使用可能になる間どのくらいの時間がかかるかを計測
することもできる。

【００４９】レジスタの内容が使用可能でない時プログ
ラムの実行パスを変更するため、本発明を使用すること
ができる一方、アウト・オブ・オーダの命令実行が可能
なコンピュータ・システムにおいてキャッシュ・プリフ
ェッチ・オペレーションを制御するためにもまた、本発
明を使用することができる。例えば、メモリからロード
した値に基づいて分岐条件を決定すると仮定されたい。
ロードした値がキャッシュの中にある場合、プロセッサ
がその結果を計算し分岐条件を解析する前に長い時間は
かからない。従って、プリフェッチを必要とするロード
命令が実行パス上にあるかどうかがすぐに分かるため、
投機的キャッシュ・プリフェッチ・オペレーションを開
始する潜在的な利益は小さい。利益が小さいため、不要
なデータでキャッシュを汚染しないようにプリフェッチ
・オペレーションを避けるのが望ましい。一方、分岐条
件を決定するため必要なロードがキャッシュ・ミスを派
生する場合、プロセッサがその分岐条件を解析するのに
多少時間がかかる。この状況では、予想される（しかし
未確認の）実行パスに沿うロード命令に対する投機的プ
リフェッチ・オペレーションを実行する利益は、より大
きい。本発明は、コンパイラが、分岐条件を迅速に解析
するかどうかを判定するコードをスケジュールし、それ
によって投機的プリフェッチ・オペレーションを含む実
行パスをたどるべきかどうかを決定することができる、
オーバヘッドの少ないメカニズムを提供する。

【００５０】本発明の最も大きな利益の１つは、実施す
るのが比較的簡単であることと、「ストール・オン・ユ
ーズ」技術をサポートし、「非ブロッキング」キャッシ
ュを含むプロセッサ・アーキテクチャの中に追加の回路
をほとんど必要としないことである。このようなプロセ
ッサは既に停止信号を生成する実質的回路を含んでい
る。本発明によると、このようなプロセッサに追加すべ
きものは、特定のレジスタに関する停止信号を生成する
回路を活動化し、その停止信号の結果を他のレジスタに
格納する（もしくは停止信号に基づいて分岐する）命令
だけである。従って、その命令を復号し、宛先レジスタ
のデータ・パスの中へ既に存在する停止信号の進路を変
更する少数のゲートによって、本発明を実施することが
できる。

【００５１】本発明について好ましい実施形態を参照し
て述べたが、当業者は、本発明の精神と範囲を超えるこ
となく形式もしくは詳細において変更することもできる
ことを認識するであろう。

【００５２】以上、本発明の実施例について詳述した
が、以下、本発明の各実施態様の例を示す。

【００５３】（実施態様１）メイン・メモリ装置と、前
記メイン・メモリ装置に接続された１以上のキャッシュ
・メモリ装置と、ＣＰＵとを有するコンピュータ・シス
テムにおいて、前記ＣＰＵは、１以上のレジスタと、前
記レジスタの各々の使用可能状態を保持するデータ構造
であって、前期使用可能状態とは、特定のレジスタを読
み取ろうとしている命令が停止するかどうかを示す、
と、１以上の前記レジスタの前記使用可能状態に基づい
てプログラム実行パスを変更する１以上の命令を復号し
実行することができる、命令復号および実行回路とを含
むことを特徴とするコンピュータ・システム。

【００５４】（実施態様２）前記データ構造は、１以上
の使用不能フラグを有し、各使用不能フラグは１つのレ
ジスタに対応する実施態様１に記載のコンピュータ・シ
ステム。

【００５５】（実施態様３）選択したレジスタおよび選
択した使用不能フラグを指定する第１の命令が定義さ
れ、前記命令復号／実行回路は、選択した使用不能フラ
グの前記使用可能状態を選択したレジスタにルーティン
グすることができるマルチプレクサを含む、実施態様２
に記載のコンピュータ・システム。

【００５６】（実施態様４）前記データ構造は、ソース
・レジスタと一連の宛先レジスタとの間の比較を含む、
実施態様１に記載のコンピュータ・システム。

【００５７】（実施態様５）レジスタ中の内容の使用可
能性に基づいてプログラム内で代替の実行スレッドを選
択する方法において、前記レジスタの内容が使用可能で
あるかどうかを判定するため、データ構造を照会する前
記プログラムの命令を実行するステップと、前記レジス
タの内容が使用可能である場合、第１の実行スレッドを
選択するステップと、前記レジスタの前記内容が使用不
能である場合、第２の実行スレッドを選択するステップ
とを含む方法。

【００５８】（実施態様６）前記レジスタの内容が使用
可能であるかどうかを判定するためにデータ構造を照会
するステップは、第１のレジスタの使用可能状態を、前
記第１のレジスタに関連する使用不能フラグから第２の
レジスタに転送する命令を実行するステップを含む、実
施態様５に記載の方法。

【００５９】（実施態様７）前記レジスタの内容が使用
可能である場合は、第１の実行スレッドを選択するステ
ップが、また前記レジスタの前記内容が使用不能である
場合は、第２の実行スレッドを選択するステップが、前
記第２のレジスタの内容に基づいて前記第１もしくは第
２の実行スレッドのいずれかに実行の経路を定める、条
件分岐命令を実行するステップを共に含む、実施態様５
に記載の方法。

【００６０】（実施態様８）命令が読み取るために検索
しているレジスタの内容がまだ使用可能でない時、前記
命令の実行を停止することができる停止回路を有するコ
ンピュータ・システムにおいて、前記停止回路の実質的
部分を使用して前記レジスタの内容の使用可能状態を判
定し、前記レジスタの前記使用可能状態に基づいてプロ
グラム実行パスを変更する、１以上の命令を復号し実行
することができる、命令復号／実行回路を備えることを
特徴とするコンピュータ・システム。

【００６１】

【発明の効果】以上のように、本発明を用いると、コン
ピュータ・システムのプロセッサのレジスタについて、
特定のレジスタを読み取ろうとする命令が停止するかど
うかを示す使用可能状態を保持するデータ構造を含むコ
ンピュータ・システムを提供することができる。

【００６２】また、本発明の利益の１つは、実施するの
が比較的簡単であることと、「ストール・オン・ユー
ズ」技術をサポートし、「非ブロッキング」キャッシュ
を含むプロセッサ・アーキテクチャの中に追加の回路を
ほとんど必要としないことである。

【図面の簡単な説明】

【図１】中央処理装置（ＣＰＵ）、レベル１（Ｌ１）キ
ャッシュ・メモリ装置、レベル２（Ｌ２）キャッシュ・
メモリ装置、およびメイン・メモリ装置を含む、従来技
術のコンピュータ・システムのブロック図である。

【図２】レジスタの内容が使用可能でないためプロセッ
サが実行を中断すべきかどうかを判定するための、一般
的な従来技術の技法の簡略図である。

【図３】本発明によるＣＰＵの簡略ブロック図である。

【図４】本発明が提供するコンピュータ命令の簡単な応
用例を示す図である。

【符号の説明】

２８：ＣＰＵ ３０：レジスタ ３２：使用不能フラグ ３４：停止信号装置 ３６：マルチプレクサ ３８：他のＣＰＵ機能

Claims (1)

【特許請求の範囲】
1. 【請求項１】メイン・メモリ装置と、 前記メイン・メモリ装置に接続された１以上のキャッシ
   ュ・メモリ装置と、 ＣＰＵとを有するコンピュータ・システムにおいて、 前記ＣＰＵは、 １以上のレジスタと、 前記レジスタの各々の使用可能状態を保持するデータ構
   造であって、前期使用可能状態とは、特定のレジスタを
   読み取ろうとしている命令が停止するかどうかを示す、
   と、 １以上の前記レジスタの前記使用可能状態に基づいてプ
   ログラム実行パスを変更する１以上の命令を復号し実行
   することができる、命令復号および実行回路とを含むこ
   とを特徴とするコンピュータ・システム。