(57)【要約】【課題】分岐命令があると、大きな分岐ペナルティが発生しうる。【解決手段】ＣＰＵ１０２に分岐動作を実行させる分岐命令と関連づけられた条件付プリフェッチ命令の第１部分に含まれる値を特定する。つづいて、条件付プリフェッチ命令の第２部分に含まれる、ターゲット命令のアドレスを特定する。条件が満たされたか否かを確認するために前記の値を評価する。条件が満たされたとき、ＣＰＵ１０２の命令キャッシュ１０４にターゲット命令のアドレスを開始アドレスとして１以上の命令をプリフェッチする。【選択図】図１
2006216040.tif 000002
【特許請求の範囲】
【請求項１】
以下の処理を含むことを特徴とする方法。
（ａ）プロセッサに分岐動作を実行させる分岐命令と関連づけられた条件付プリフェッチ命令の第１部分に含まれる値を特定する処理、
（ｂ）前記条件付プリフェッチ命令の第２部分に含まれる、ターゲット命令のアドレスを特定する処理、
（ｃ）条件が満たされたか否かを確認するために前記値を評価する処理、および、
（ｄ）前記条件が満たされたとき、前記プロセッサの命令バッファに前記ターゲット命令のアドレスを開始アドレスとして１以上の命令をプリフェッチする処理。
【請求項２】
請求項１に記載の方法において、前記値が非零のとき条件が満たされたとみなすことを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、前記条件付プリフェッチ命令は、前記値に基づいて、前記プロセッサにターゲット命令のプリフェッチを起動せしめることを特徴とする方法。
【請求項４】
請求項１から３のいずれかに記載の方法において、前記条件付プリフェッチ命令に応じ、前記プロセッサのハードウエアパイプラインに１以上の命令をプリロードする過程をさらに含むことを特徴とする方法。
【請求項５】
請求項１から４のいずれかに記載の方法において、前記条件付プリフェッチ命令の第１部分に含まれる値は、前記分岐命令を過去反復したときに分岐が発生したか否かを示す情報を含むことを特徴とする方法。
【請求項６】
請求項１から４のいずれかに記載の方法において、前記条件付プリフェッチ命令の第１部分に含まれる値は、前記分岐命令を過去反復したうちの２回について分岐が発生したか否かを示す情報を含むことを特徴とする方法。
【請求項７】
命令キャッシュを有し、条件付プリフェッチ命令に関連づけられた分岐制御命令を利用するプロセッサを動作させる方法であって、前記条件付プリフェッチ命令は条件テスト部分および命令アドレス部分を有するものであり、以下の処理を含むことを特徴とする方法。
（ａ）前記条件付プリフェッチ命令の条件テスト部分が真であると評価できるか否かを確認する処理、および、
（ｂ）前記条件付プリフェッチ命令の条件テスト部分が真であると評価できたとき、前記条件付プリフェッチ命令の命令アドレス部分で示されるアドレスを開始アドレスとして１以上の命令を前記プロセッサの命令キャッシュにプリロードする処理。
【請求項８】
請求項７に記載の方法において、前記条件テスト部分の値が非零であると評価されたとき、真であることを確認することを特徴とする方法。
【請求項９】
請求項７または８に記載の方法において、前記条件テストの結果に基づいて１以上の命令のプリフェッチを起動する処理をさらに含むことを特徴とする方法。
【請求項１０】
請求項７から９のいずれかに記載の方法において、前記条件テスト部分は前記分岐制御命令を過去反復したうち直近に反復した際に分岐が発生したか否かも示すことを特徴とする方法。
【請求項１１】
請求項７から９のいずれかに記載の方法において、前記条件テスト部分は前記分岐制御命令を過去反復したうち直近の２回に反復した際に分岐が発生したか否かも示すことを特徴とする方法。
【請求項１２】
プロセッサに以下の処理を実行せしめることを特徴とするコンピュータプログラム。
（ａ）プロセッサに分岐動作を実行させる分岐命令と関連づけられた条件付プリフェッチ命令の第１部分に含まれる値を特定する処理、
（ｂ）前記条件付プリフェッチ命令の第２部分に含まれる、ターゲット命令のアドレスを特定する処理、
（ｃ）条件が満たされたか否かを確認するために前記値を評価する処理、および、
（ｄ）前記条件が満たされたとき、前記プロセッサの命令バッファに前記ターゲット命令のアドレスを開始アドレスとして１以上の命令をプリフェッチする処理。
【請求項１３】
請求項１２に記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令は、前記条件の値に基づいて、前記プロセッサにターゲットとなる特定の命令をプロセッサの命令バッファへプリフェッチすることを起動せしめることを特徴とするコンピュータプログラム。
【請求項１４】
請求項１２または１３に記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令の第１部分はプロセッサのレジスタにロード可能な値を含むことを特徴とするコンピュータプログラム。
【請求項１５】
請求項１２から１４のいずれかに記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令の第２部分によって特定されたアドレスは、プロセッサキャッシュのオフセットを含むことを特徴とするコンピュータプログラム。
【請求項１６】
請求項１２から１５のいずれかに記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令はそれに関連するプログラム分岐命令に先だって置くことが可能であり、その結果、プロセッサが前記プログラム分岐命令を実行する前に前記ターゲットとなるアドレスを導くことを可能としたことを特徴とするコンピュータプログラム。
【請求項１７】
請求項１２から１６のいずれかに記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令は、プロセッサのハードウエアパイプラインへの命令のプリロードをソフトウエアから制御することを許可することを特徴とするコンピュータプログラム。
【請求項１８】
請求項１２から１７のいずれかに記載のコンピュータプログラムにおいて、前記条件付プリフェッチ命令の第１部分に含まれる値は、関連づけられた分岐命令を過去反復したときに分岐が発生したか否かを示す情報を含むことを特徴とするコンピュータプログラム。
【請求項１９】
分岐命令と関連する条件付プリフェッチ命令を含むプログラムによって制御されるプロセッサであって、前記プログラムにより、以下の処理を実行することを特徴とするプロセッサ。
（ａ）真または偽として評価される値を特定する、前記条件付プリフェッチ命令の第１部分をデコードする処理と、
（ｂ）特定のターゲット命令のアドレスを同定する、前記条件付プリフェッチ命令の第２部分をデコードする処理と、
（ｃ）前記値が真と評価されたとき、前記特定のターゲット命令をキャッシュからプロセッサの命令バッファへ移動させる動作に関連づけられたプリフェッチを実行する処理。
【請求項２０】
請求項１９に記載のプロセッサにおいて、前記特定のターゲット命令のプリフェッチ動作は、前記値の評価結果に基づいて、プロセッサにより実行可能であることを特徴とするプロセッサ。
【請求項２１】
請求項１９または２０に記載のプロセッサにおいて、前記値が非零のとき真と評価され、前記値が零のとき偽と評価されることを特徴とするプロセッサ。
【請求項２２】
請求項１９から２１のいずれかに記載のプロセッサにおいて、前記条件付プリフェッチ命令は、プロセッサのハードウエアパイプラインへの命令のプリロードをソフトウエアから制御することを許可することを特徴とするプロセッサ。
【請求項２３】
請求項１９から２２のいずれかに記載のプロセッサにおいて、前記条件付プリフェッチ命令の第１部分に含まれる評価のための前記値は、前記分岐命令を過去反復したときに分岐が発生したか否かを示す情報を含むことを特徴とするプロセッサ。
【請求項２４】
請求項１２から１８のいずれかに記載のコンピュータプログラムをコンピュータから読み取り可能に格納したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は命令実行を改善するコンピュータ処理のシステムおよび方法に関し、例えばパイプラインプロセッサにおける分岐命令の遅延を低減するシステムおよび方法に関する。
【背景技術】
【０００２】
プログラムの実行速度を上げるために、コンピュータのプロセッサは命令バッファを利用することが多い。「命令キャッシュ」ともよばれるそのようなバッファにより、プロセッサが別の命令を実行しているときに、次のいくつかの命令をパイプラインへキューイングすることができる。その結果、プロセッサがひとつの命令の実行が終わると、キャッシュにある次の命令が利用でき、すぐに実行可能となる。
【０００３】
最近のコンピュータシステムの多くは、ハードウエアまたはファームウエアで実装された１以上の命令キャッシュを使用し、命令スループットを改善するパイプラインアーキテクチャをもつプロセッサを利用する。
【０００４】
しかし、条件付ジャンプを処理する場合、命令キャッシュに命令をパイプライン化することは効果的ではないこともある。条件付ジャンプを実行すると、通常次に実行すべき命令群は、いま実行した条件付ジャンプ命令の直後に置かれた、現在命令キャッシュに入っているものであるか、またはキャッシュに入っていない異なるアドレスのものとなる。次に実行すべき命令が命令キャッシュに入っていないアドレスに置かれていれば、必要な命令が命令キャッシュへロードされる間、プロセッサは複数のクロックサイクルにわたり、（ＮＯＰ命令を実行することにより）実質的に処理を停止することになる。
【０００５】
したがって、条件付分岐やジャンプが設けられると、プロセッサは新しい命令群が読み出されるまで複数のクロックサイクルの間ウエイトする可能性がある。この分岐命令による遅延は「分岐ペナルティ」として知られている。分岐ペナルティは、すでにキャッシュに入っている命令へ分岐する際には短かくなるが、命令がキャッシュにロードされなければならないときは長くなる。
【０００６】
分岐ペナルティの実例として以下のプロセッサ命令群を考える。 
Code:   Inst  A0
Branch  COND,  L1
Inst  B0
L1:     Inst  C0
Inst  C1
【０００７】
このプロセッサ命令群の例でCONDが真（TRUE）、すなわち非零の場合、プログラムの実行は「Branch  COND,  L1」命令からラベルL1の「Inst C0」へジャンプする。そうでない場合、プログラムの実行はまず「Inst  B0」へ進む。「Branch  COND,  L1」命令を実行しているとき、ラベルL1にある命令がプロセッサの命令バッファに入っていなければ、プロセッサはその命令をバッファに読み込まなければならず、その間、プログラムの命令は全く実行できない。命令が命令バッファに読み込まれる間プロセッサが待機する無駄なクロックサイクルが分岐ペナルティの尺度となる。分岐ペナルティをさらに説明するために、上のプロセッサ命令群の例において実際に分岐が発生し、L1の命令がプロセッサの命令バッファに存在しなかったとする。
【０００８】
実行               サイクル
Inst  A0            1
L1へ分岐            2
NOP: ペナルティ     3
NOP: ペナルティ     4
.・・・
NOP: ペナルティ     16
NOP: ペナルティ     17
Inst  C0            18
Inst  C1            19
【０００９】
簡単のため、ここでは命令、分岐、NOPはいずれも１クロックサイクルで実行されるとする。また、「Inst  C0」命令をバッファに供給するために必要なクロックサイクルの数は単に説明のために１８とし、１８クロック目の前後でプロセッサに利用可能になるものとしている。この例では、「L1へ分岐」命令は２クロックサイクル目で実行されているにも拘わらず、１８クロックサイクル目まで待たなければ、「Inst  C0」命令が命令バッファに入ってプロセッサから利用可能とならない。したがって、この例で分岐ペナルティは１６クロックサイクルとなる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
分岐ペナルティを減らし、またはなくすためにいくつか方法が提案されている。これらの方法はハードウエアによるものとソフトウエアによるものがある。ハードウエアによる方法の中には、プロセッサの命令パイプラインのアーキテクチャを改善し、命令群の中で近い将来分岐が発生するか否かを予測し、プロセッサの命令バッファに必要な命令をプリフェッチまたはプリロードするものがある。理論上、パイプラインプロセッサは正しく整列された連続する命令ストリームを実行する際、マシンクロックサイクル毎に１つの命令を実行することができる。これは仮に各命令が複数の個別のマイクロ命令の実行を含み、または必要とする場合でさえ実現できることがある。
【００１１】
パイプラインアーキテクチャを利用する方法の中には、命令の分岐が発生するか否かを固定的なアルゴリズムで予測するものがある。しかし、アルゴリズムが変えられない以上、プロセッサで実行される各プログラムに最適化することができない欠点がある。
【００１２】
ハードウエアによる別の方法は、分岐履歴テーブル（ＢＨＴ：branch history table）を用いて分岐を予測する。ＢＨＴはビットマップのテーブル形式で、各エントリは実行中のプログラムの分岐命令に対応し、ビットはそれぞれ、分岐するしないに関するひとつの決定を表す。ＢＨＴの中には、各分岐命令について１ビットしかもたないものがあり、したがって、分岐命令があるたびに、分岐有無の予測はその命令について前回分岐が発生したか否かに従うに過ぎない。この方法は１ビットの動的予測ともいわれる。１ビットの予測では、ある条件付分岐が実際に発生すると、次回も発生すると予測する。逆に、分岐が発生しなかったときは、次回も発生しないと予測する。
【００１３】
ＢＨＴの中には、２ビットの動的予測をするものもある。２ビットの動的予測では、ある条件付分岐が過去２回つづけて発生したとき次回も分岐は発生すると予測する。逆に、過去２回とも分岐が発生しなかったときは、次回も分岐は発生しないと予測する。過去２回のうち分岐が１回だけ発生した場合、次回は直近に分岐が発生していれば発生すると予測し、そうでなければ発生しないと予測する。一般に、分岐がループや例外処理に用いられる場合、２ビットの動的予測を用いるＢＨＴは１ビットのものよりもよい結果をもたらす。分岐はループごと、または処理の実行ごとに１回しか発生しないためである。２ビット予測はより正確になるものの、同時にハードウエアのコストも大きくなる。そのため、いろいろな用途において、対象の状態があまり頻繁に変わらない場合、１ビットの予測で十分な場合もある。
【００１４】
ＢＨＴはプロセッサのリソースの相当量を利用するため、分岐ペナルティもかなり大きくなることがある。
【００１５】
一方、ソフトウエアによる方法は、特定のアドレスから命令のプリフェッチを起動する命令が用いられる。実装の例として、「HINT(ADDRESS)」命令の形式を用いる。プロセッサはHINT命令を発見すると即座に「ADDRESS」で示すアドレスを開始アドレスとして命令のプリフェッチを自動的に行う。HINT命令を実際の分岐命令の数命令前置くことにより、プログラマは、プロセッサが次の命令のフェッチを待つためのクロックサイクルを減らすことができる。
【００１６】
しかし、HINT(ADDRESS)命令を利用すると、無条件で命令プリフェッチが発生する点が問題となる。分岐の有無に関係なく、分岐アドレスにある命令がプリフェッチされてしまうので、プラグラマはHINT(ADDRESS)命令をどこに置くべきか決めなければならない。しかし、プログラマは分岐発生を常に正しく予測できるとは限らない。もしプログラマが判断を誤り、HINT(ADDRESS)命令を置いたにも拘わらず分岐が発生しなかった場合、プリフェッチは無駄な処理となる。その場合、誤った命令を捨て、パイプラインをフラッシュし、正しい命令列をリロードするために、大きな時間的ペナルティが生じる。パイプラインのサイズによっては、このペナルティは多大なものとなる。
【００１７】
分岐ペナルティを減らし、またはなくすためのこうしたハードウエア、ソフトウエアによる方法は、分岐の条件が成立する確率がプログラムの実行中変化するという事実も考慮していない。
【課題を解決するための手段】
【００１８】
本発明はこのような従来の課題に鑑みてなされたものであり、本発明のある態様は、プロセッサに分岐動作を実行させるために用いられる分岐命令と関連づけられた条件付プリフェッチ命令の第１部分に含まれる値を特定する処理を含む方法を提供する。つづいて、条件付プリフェッチ命令の第２部分にてターゲット命令のアドレスが特定される。つぎに、条件が満たされたかどうかを確認するために前記の値が評価される。条件が満たされていれば、ターゲット命令のアドレスを開始アドレスとして、１以上の命令がプロセッサの命令バッファにプリフェッチされる。
別の態様では、前記の値が非零のとき、ターゲット命令がプリフェッチされる。
【００１９】
本発明の別の態様は、命令キャッシュをもち、条件付プリフェッチ命令と関連づけられた分岐制御命令を用いるプロセッサを動作させる方法に関する。条件付プリフェッチ命令は条件テスト部分と命令アドレス部分を含む。この方法は以下の処理を含む。（ａ）前記条件付プリフェッチ命令の条件テスト部分が真であると評価できるか否かを確認する処理、および、（ｂ）前記条件付プリフェッチ命令の条件テスト部分が真であると評価できたとき、前記条件付プリフェッチ命令の命令アドレス部分で示されるアドレスを開始アドレスとして１以上の命令を前記プロセッサの命令バッファにプリロードする処理。
【００２０】
本発明の別の態様は、コンピュータプログラムに関する。このコンピュータプログラムは、プロセッサに以下の処理を実行せしめるものである。このプログラムにより、まず条件付プリフェッチ命令の第１部分に含まれる値が特定される。この条件付プリフェッチ命令は、プロセッサに分岐動作を実行させる分岐命令と関連づけられている。つぎに、条件付プリフェッチ命令の第２部分に含まれる、ターゲット命令のアドレスが特定される。前記の値は、条件が満たされたか否かを確認するために評価される。条件が満たされたとき、プロセッサの命令バッファにターゲット命令のアドレスを開始アドレスとして１以上の命令がプリフェッチされる。
【００２１】
本発明のさらに別の態様はプロセッサに関する。このプロセッサは、分岐命令と関連する条件付プリフェッチ命令を含むプログラムによって制御される。このプログラムによって、プロセッサは以下の処理を実行する。まず、評価されるべき値を特定する、条件付プリフェッチ命令の第１部分をデコードする。この値は真または偽として評価される。値が真と評価されたとき、条件付プリフェッチ命令の第２部分をデコードする。この第２部分は、特定のターゲット命令のアドレスを同定するもので、そのアドレスがプリフェッチされる。このプリフェッチ動作は、特定のターゲット命令をキャッシュからプロセッサの命令バッファへ移動させる動作に関連づけられている。
【００２２】
なお、以上の構成要素の任意の組合せ、本発明の処理や表現、それらの組合せを方法、装置、システムなどの間で変換したもの、本発明の処理をコンピュータによって実行可能なプログラムとしたもの、そのプログラムを記録媒体に格納したものもまた、本発明の態様として有効である。
【発明の効果】
【００２３】
本発明によれば、プロセッサの分岐動作を効率的に行うことができる。
【発明を実施するための最良の形態】
【００２４】
図１のごとく、本発明の実施の形態に係るコンピュータシステム１００は、ＣＰＵ１０２と、命令キャッシュ１０４と、ＣＰＵ１０２を命令キャッシュ１０４へ接続するパイプライン１０６およびデータバス１０８を備える。図１にはこれらの部品のみが記載されているが、典型的なシステム１００は多数の部品、周辺回路、および通信バスを含みうる。望ましい実施の形態では、システム１００は汎用コンピュータであり、通常パーソナルコンピュータに見られるように、例えばディスプレイ、ＣＤＲＯＭ、ハードディスクドライブ、マウス、キーボード、スピーカ、マイクロフォン、モデムおよびそれらを相互に接続するすべての部品など、付加的なすべての内部部品を有する。これらの部品は図１の明確化のために図示していない。システム１００はさらに、ワークステーション、ＰＤＡ（Personal Digital Assistance）、または命令を実行可能なプロセッサによって制御される装置やシステムを備えてもよい。
【００２５】
ＣＰＵ１０２は任意のタイプのプロセッサである。ＣＰＵ１０２はマルチプロセッサシステムでもよい。マルチプロセッサシステムでは、図示したものよりも複雑な命令キャッシュ１０４とパイプライン１０６が用いられる場合があるが、本発明はそのようなシステムにも適用できる。
【００２６】
命令キャッシュ１０４は任意のタイプのものでよい。例えば、命令キャッシュ１０４は４ワードのブロックを有する３２キロワードの命令キャッシュでもよい。もちろん、命令キャッシュ１０４は任意のワード数のブロックをもつ任意のサイズのものでよい。本明細書では「命令キャッシュ」と「命令バッファ」は同じ意味とし、特に使い分けを意図していない。
【００２７】
図１のごとく、ＣＰＵ１０２と命令キャッシュ１０４はパイプライン１０６によって接続されている。ある実施の形態では、このパイプラインはシステム１００が命令キャッシュ１０４とＣＰＵ１０２の間で命令を管理および移動するために利用するハードウエアとファームウエアの一方または両方を表す。例えば、多くのＣＰＵがそれぞれ対応する命令パイプラインとバッファを管理するための特別な回路をもっている。
【００２８】
望ましい実施の形態では、命令キャッシュ１０４とパイプライン１０６はＣＰＵ１０２とともに単一の集積回路（図示せず）のパッケージ内に封入される。パッケージに封入することにより、命令キャッシュ１０４、パイプライン１０６、ＣＰＵ１０２を近接して配置することができ、消費電力と命令転送時間を最小にすることができる。
【００２９】
ある実施の形態では、命令キャッシュ１０４とＣＰＵ１０２はそれぞれデータバス１０８と通信することにより、図示しない他の装置やメモリからの命令とデータの転送を可能とする。
【００３０】
図２は実施の形態に係る方法を説明するフローチャート２００を示す。好ましくは、ＣＰＵは命令を順に実行する。そのため、図２では「Inst  A0」２０２が最初に実行される。つぎに、ＣＰＵは「CPIF(val1, L1)」２０４を実行する。ここでCPIF命令は条件付命令プリフェッチの例である。この例では、プログラマは「Branch on COND1」命令２１０の数命令前にCPIF命令を置いている。この配置により、ＣＰＵが「Branch on COND1」命令２１０を実行するよりも前に、必要に応じて、分岐先アドレスにある命令をプリフェッチしておくための時間を作ることができる。
【００３１】
ある実施の形態では、「CPIF(val1, L1)」命令２０４によって、ＣＰＵまたはハードウエアによる命令パイプライン回路は、その命令の「val1」部分を評価する。好ましくは、処理２１６において、「val1」部分が非零、すなわち真と評価されたとき、ＣＰＵまたはハードウエアによる命令パイプライン回路は「L1」で与えられるアドレスにある命令からプリフェッチを始める（２１８）。
【００３２】
その間ＣＰＵは「Inst  A1」命令２０６をつづけて実行することができ、以下、命令列にある他の命令も同様である。ある時点で、ここでは「Inst  AN」２０８と表記された、「Branch on COND1」命令２１０の直前の命令が実行される。望ましい実施の形態では、「CPIF(val1, L1)」命令の「L1」部分によって与えられるアドレスに置かれた命令のプリフェッチ２１８は、ＣＰＵが「Branch on COND1」命令２１０を実行する前に完了する。
【００３３】
ＣＰＵが「Branch on COND1」命令２１０を実行するとき、「COND1」で与えられる条件は真または偽のいずれかである。好ましくは、COND1が偽のとき分岐は発生しないものとし、ＣＰＵはプログラムを次の命令列「Inst  B0」２１２、「Inst  B1」２１４の順で実行する。逆にCOND1
が真の場合は分岐が発生し、ＣＰＵは好ましくは「Inst  C0」２２２、「Inst  C1」２２４の順にプログラムを実行する。ＣＰＵが「Branch on COND1」命令２１０を実行するとき、「L1」部分によって与えられるアドレスに置かれた命令、すなわち、「Inst  C0」２２２、「Inst  C1」２２４などの命令のプリフェッチ２１８が完了していなければ、分岐ペナルティ２２０が発生する。
【００３４】
「CPIF(val1, L1)」命令２０４による分岐有無の予測が外れたとき、より大きな分岐ペナルティが発生する。例えば、「CPIF(val1, L1)」命令２０４は分岐の発生を予測しつつ、実際には分岐が発生したなったとき、命令キャッシュは「Inst  B0」命令２１２、「Inst  B1」命令２１４が必要なタイミングでこれらを有していない可能性がある。その場合、命令キャッシュをフラッシュしてリフィルする必要が生じうる。これはキャッシュミスとして知られる現象である。同様に、「CPIF(val1, L1)」命令２０４は分岐が発生しないと予測しつつ、実際には分岐が発生したとき、命令キャッシュは「Inst  C0」命令２２２、「Inst  C1」命令２２４が必要なタイミングでこれらを有していない可能性がある。その場合も命令キャッシュをフラッシュしてリフィルする必要が生じうる。
【００３５】
本発明のある態様は、任意の分岐の発生有無を動的に予測することにより、命令キャッシュのミスの回数を最少化する。ある実施の形態では、この動的予測はCPIF命令に埋め込まれた論理的条件をテストすることによって実現される。テストすべき条件を適切に選択すれば、プログラマは分岐予測の精度を大幅に高めることができる。
【００３６】
図２の例では、CPIF命令の比較的簡単なパラメータ「val1」が、非零（真）であるか零(偽)であるかを確認することによって評価される。非零の場合はプリフェッチを実行し、零の場合は実行しない。同様に、好ましくは、より複雑な「Branch on COND1」命令２１０の条件「COND1」を評価して分岐の有無を確認する。真または偽の状態が「Branch on COND1」命令の「COND1」と十分に対応するよう「val1」を選択することにより、プログラマは分岐予測の精度を改善できる。実施の形態では、現実には、「val1」と「COND1」を同一のものとしてもよい。
【００３７】
図３は、実施の形態に係る条件付プリフェッチ命令を実行する単純化されたプロセッサによる、より詳細なフローチャート３００である。通常動作において、プロセッサは命令ポインタでアドレッシングされる命令をデコードする（３０２）。プロセッサはデコードした命令が条件付プリフェッチ命令であるか否かを確認する（３０４）。もし条件付プリフェッチ命令でなければ、プロセッサは命令の実行３０６へ進む。命令の実行が終わればプロセッサの命令ポインタはインクリメントされ（３０８）、ポインタが後続の命令を指し、その命令がプロセッサによってデコードされる（３０２）。
【００３８】
もし命令が条件付プリフェッチ命令だったとき、プロセッサは条件付プリフェッチ命令の「値」部分を評価する（３１０）。好ましくは、条件付プリフェッチ命令は「CPIF(value, address)」の形式をもつ。ここで「CPIF」は命令ニーモニック、「value」は評価の対象となる式、「address」はvalue が真の場合にプリフェッチされるべき命令のプリフェッチ開始アドレスである。ここでは条件付プリフェッチ命令を表すニーモニックとしてCPIFを使ったが、もちろん、どのようなニーモニックであってもよい。
【００３９】
プロセッサはつづいて条件付プリフェッチ命令の「value」部分を評価する（３１２）。この値が非零であれば、これは真とされ、プロセッサは条件付プリフェッチ命令の「address」部分で示される位置の命令をプリフェッチする（３１４）。実施の形態では、プリフェッチされる命令数は任意であるが、命令キャッシュのサイズとプロセッサのパイプラインアーキテクチャとに関連していることが望ましい。
【００４０】
もし条件付プリフェッチ命令の「value」が零の場合、これは偽とされ、プロセッサはプリフェッチ動作を実行しない。そのかわり、プロセッサは処理を続行して命令ポインタをインクリメントし（３０８）、命令列の次の命令をデコードする（３０２）。
【００４１】
図３のフローチャートは説明のために簡略化されている。例えば、この技術分野でよく知られるごとく、多くのプロセッサは多様なマルチプロセッシングの中で利用され、その場合、任意の時刻においていくつかの命令がプロセッサのさまざまな実行段階にある。ある実施の形態は、そうしたマルチプロセッシングシステムの利用も想定する。そのような実施の形態では、プロセッサの各クロックサイクルにおいて、いくつかの命令がさまざまな実行段階にある状態を実現すべく、通常、より複雑な命令パイプラインアーキテクチャを利用する。
【００４２】
ある実施の形態では、プロセッサ自身が命令パイプラインと命令キャッシュを管理する。別の実施の形態では、命令パイプラインと命令キャッシュはプロセッサと関連はするものの、プロセッサの一部とはいえないハードウエアによって管理されてもよい。上述のごとく、あるプロセッサが別のプロセッサのために命令パイプラインや命令キャッシュを管理してもよい。
【００４３】
実施の形態の一例として、以下のプロセッサ命令群を考える。
Code:   Inst  A0
CPIF  VAL,  L1
Inst  A1
Inst  A2
Inst  A3
Branch  COND, L1
Inst  B0
L1:     Inst  C0
Inst  C1
【００４４】
このプロセッサ命令群の例では、もし「COND」が真、すなわち非零のとき、プログラムの実行は「Branch COND, L1」命令からラベルL1のある「Inst  C0」へジャンプする。「COND」が偽の場合は、プログラムの実行はまず「Inst  B0」命令へ進む。「Branch COND, L1」命令が実行されるとき、ラベルL1のある命令がプロセッサの命令バッファになければ、プロセッサに分岐ペナルティが発生する。
【００４５】
条件付プリフェッチ命令のこの用法をさらに説明するために、分岐が発生し、かつL1の位置の命令がプロセッサの命令キャッシュにない場合、上述のプロセッサ命令群の実行時間を検証する。ここでは、クロックサイクルを利用して説明する。
【００４６】
実行           サイクル    注釈
Inst  A0          1
CPIF VAL, L1      2        プリフェッチ開始
Inst  A1          3
Inst  A2          4
Inst  A3          5        プリフェッチ完了
L1へ分岐          6
Inst  C0          7
Inst  C1          8
【００４７】
ここで示したとおり、条件付プリフェッチ動作は、それを使わない場合に比べ、同様の状況においてプロセッサのクロックサイクル数を相当削減することができる。
【００４８】
別の実施の形態における条件付プリフェッチ命令の用途として、Ｃ言語のプラグラマによる条件付プリフェッチの利用が考えられる。もちろん、Ｃ言語に限らず、アランブラ言語やコンパイラ形式の言語も含む他のプログラミング言語でもよく、Ｃ、Ｃ＋＋、ＣＯＢＯＬ、Ｆｏｒｔｒａｎ、Ａｄａ、Ｐａｓｃａｌなどがその例である。さらに、インタプリタ形式の言語でもよく、ＢＡＳＩＣ、Ｊａｖａ（登録商標）、ＸＭＬなどがその例である。
【００４９】
Ｃ言語によるループの例（擬似コード）は以下のとおりである。
for ( i=0; i<n; i++ )
{
命令・・・
}   ／＊  条件付分岐  ＊／
【００５０】
条件付分岐は、コメント「／＊  条件付分岐  ＊／」が置かれた終わりの括弧“｝”に暗黙的に含まれている。「命令・・・」が実行されるたびにｉはインクリメントされ、ｎと比較される。ｉがｎ未満ならループは繰り返す。これはコンパイルされた機械語では、条件付分岐動作として実装されることが多い。
【００５１】
実施の形態を利用し、プログラマはこのＣ言語のループを以下のように書き換えてもよい。
L1:  for ( i=0; i<n; i++ )
{
CPIF( ( i != n-1), L1 );
命令・・・
}   ／＊  条件付分岐  ＊／
【００５２】
Ｃ言語によるこのバージョンでは、forループの先頭にアドレスラベルL1と、ループの最初に条件付プリフェッチ命令「CPIF」を追加している。ここで、条件付プリフェッチ命令について評価される値は（i != n-1）である。この式は、ループの最終回になるまで非零と評価される。そのため、最終回を除くループの各回においてアドレスL1の命令がプリフェッチされる。この方法により、プロセッサに分岐ペナルティを発生させることなく、ループを効率的に処理および実行できる。
【００５３】
ある実施の形態では、分岐ペナルティを最少化するために、CPIF命令とともに、１ビットまたは２ビットの分岐履歴を用いてもよい。例えば、分岐履歴はプロセッサの１ないし２のレジスタに保存してもよい。次の条件付分岐に先立ち、CPIF命令はレジスタに保存された値を評価されるべき式として利用してもよい。従来の分岐履歴テーブルは命令をプリフェッチすべきタイミングを決定する際、過去の履歴のみを利用した。しかし本発明のある態様では、より高いレベルの決定をなすパラメータのひとつとして分岐履歴テーブルに含まれる情報を利用する。この方法により、CPIF命令は１ビットないし２ビットの分岐履歴の利用によって得られる効果を併せ持つことができる。
【００５４】
以上述べたいろいろな実施の形態は互いに排他的ではなく、それらをさまざまな組合せで用いることにより、それぞれ固有の効果を達成することができる。以上に述べた、またはそれ以外の特徴の変形や組合せは、特許請求の範囲に定義した発明から外れることなく利用することができる。したがって、以上に述べた実施の形態の説明は、特許請求の範囲に定義された発明を制限するものではなく、単に例を示すためのものと理解されるべきである。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施の形態に係るシステムのブロック図である。
【図２】本発明の実施の形態に係る方法を説明するフローチャートである。
【図３】本発明の実施の形態に係る方法を説明するフローチャートである。
【符号の説明】
【００５６】
１００  コンピュータシステム、  １０２  ＣＰＵ、  １０４  命令キャッシュ、  １０６  パイプライン、  １０８  データバス。
【図１】
2006216040.tif 000003
【図２】
2006216040.tif 000004
【図３】
2006216040.tif 000005