(57)【特許請求の範囲】
【請求項１】
命令フェッチパイプラインにおいて、命令キャッシュを参照し、キャッシュミスを引き起こすことと（このときのアドレスを、以下「第１の命令アドレス」という）；
前記第１の命令アドレスでＢＴＡＣ（分岐ターゲットアドレスキャッシュ）をアクセスし、前記第１の命令アドレスに、成立すると予測される分岐命令が関連している場合には、その分岐ターゲットアドレスである第２の命令アドレスを得ることと；
前記第１の命令アドレスに関連づけられる第１の命令を検索するために、より高いレベルのメモリトランザクションを開始することと；
前記のより高いレベルのメモリトランザクションの待ち時間の間に、前記命令キャッシュから、前記第２の命令アドレスに関連づけられるいずれの命令も検索することなく、前記第２の命令アドレスに関連づけられる第２の命令が前記命令キャッシュにおいて保存されているかどうかを、確かめることと；
リフェッチレジスタに前記第１の命令アドレスを保存することと、命令フェッチパイプラインから前記第１の命令アドレスをフラッシュすることと、前記第２の命令アドレスを命令フェッチパイプラインへロードすることと、引き続いて前記第１の命令アドレスを前記リフェッチレジスタから前記命令フェッチパイプラインへとリロードすることと、なお、前記第２の命令アドレスは、命令フェッチパイプラインを通して流れ、前記分岐命令の分岐の成立が確定した場合に、前記命令キャッシュから命令を検索するために用いられる；
を備える命令フェッチパイプラインに命令アドレスをロードする方法。
【請求項２】
前記第２の命令アドレスを得ることは、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスを用いて、前記ＢＴＡＣ（分岐ターゲットアドレスキャッシュ）にアクセスすることを含む、請求項１に記載の方法。
【請求項３】
前記ＢＴＡＣ（分岐ターゲットアドレスキャッシュ）における各エントリは、前に成立と評価された分岐命令を含んでいる１つまたは複数の命令を備えた、対応するフェッチグループに関連付けられている、請求項２に記載の方法。
【請求項４】
前に成立と評価された前記分岐命令の評価を予測すること、をさらに備える請求項３に記載の方法。
【請求項５】
前記分岐命令の前記評価を予測することは、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスを使用して、前記分岐命令の過去の評価のインジケーションを保存しているＢＨＴ（分岐履歴テーブル）にアクセスすることをさらに備える、請求項４に記載の方法。
【請求項６】
前記第２の命令アドレスを得ることは、前記ＢＴＡＣ（分岐ターゲットアドレスキャッシュ）にアクセスすることと、ＢＨＴ（分岐履歴テーブル）にアクセスすることとを含んでおり、
前記ＢＴＡＣ（分岐ターゲットアドレスキャッシュ）は、前に実施された分岐命令に関連付けられた分岐ターゲットアドレスを保存し、そして
前記ＢＨＴ（分岐履歴テーブル）は、前記分岐命令が、成立すると評価されるのかどうか、あるいは成立しないと評価されるのかどうかについての予測を示す、
請求項１に記載の方法。
【請求項７】
前記第１の命令アドレスに関連する、前記のより高いレベルのメモリトランザクションの待ち時間の間に、前記第２の命令アドレスに関連づけられる前記の命令が前記命令キャッシュの中に見つからないことを確かめた後に、前記第２の命令を検索するために、第２のより高いレベルのメモリトランザクションを開始することをさらに備える、請求項１に記載の方法。
【請求項８】
成立すると予測された前記分岐命令は、前記第１の命令アドレスに、あるいは前記第１の命令アドレスに続くアドレスに関連する、請求項１に記載の方法。
【請求項９】
もし前記第２の命令アドレスが前記命令キャッシュにおいてミスするときは、前記のより高いレベルのメモリトランザクションの待ち時間の間に、前記第２の命令アドレスを使用して高次メモリアクセスを開始すること、をさらに備える請求項１に記載の方法。
【請求項１０】
前記第２の命令アドレスに関連付けられる第２の命令が前記キャッシュにおいて保存されているかどうかを確かめる動作が実行されるかどうかの決定は、前記第２の命令アドレスに関連づけられる属性に少なくとも部分的に基づいて行なわれる、請求項１に記載の方法。
【請求項１１】
前記予測される分岐ターゲットアドレスは、前記命令フェッチパイプラインにおいて前記予測される分岐ターゲットアドレスに関連づけられる分岐ターゲットアドレスフラグに応じて、前記命令フェッチパイプラインからプリフェッチレジスタへとロードされる、請求項１０に記載の方法。
【請求項１２】
前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連づけられる分岐命令が成立すると予測されるとき、前記分岐命令の予測される分岐ターゲットアドレスである前記第２の命令アドレスを用いて、前記第２の命令アドレスに関連付けられる第２の命令が前記キャッシュにおいて保存されているかどうかを確かめる動作を実行することと；
成立すると予測される分岐命令が、前記第１の命令アドレスに、あるいは前記第１の命令アドレスに続くアドレスに関連づけられないときは、前記第１の命令アドレスによってアドレス指定された命令キャッシュラインの次のシーケンシャル命令キャッシュラインのアドレスである第２の命令アドレスを用いて、前記第２の命令アドレスに関連付けられる第２の命令が前記キャッシュにおいて保存されているかどうかを確かめる動作を実行することと；
を含み、
いずれの場合においても、前記第２の命令アドレスを用いた前記動作は、前記第１の命令アドレスについての前記より高いレベルのメモリトランザクションの間に、発生する、
請求項１に記載の方法。
【請求項１３】
フェッチステージパイプラインを含んでいる命令実行パイプラインと；
前記フェッチステージパイプラインからの要求に応じて第1の命令の命令アドレスに関連付けられたヒットインジケーションまたはミスインジケーションの一方を提供するように、そして、
前記ヒットインジケーションに応じて、前記第１の命令をさらに提供するように、
動作する命令キャッシュメモリと；
前記ミスインジケーションに応じて、前記第１の命令を提供するように動作する高次メモリと；
前記第１の命令アドレスに関連付けられた分岐命令を検出して前記分岐命令に関連する分岐評価予測を供給し、前記分岐評価予測が「成立する」である場合には予測される分岐ターゲットアドレスを供給するように動作する分岐予測回路と；
前記第１の命令アドレスを使用する前記フェッチオペレーションが、前記命令キャッシュメモリにおいてミスし、前記第１の命令アドレスを見つけるために、前記高次メモリへのアクセスを開始する、そして
前記分岐予測回路によって提供される前記分岐予測が「成立する」と予測される、
ときに、
前記第１の命令アドレスを見つけるための前記高次メモリへのアクセスの間に、前記予測された分岐ターゲットアドレスが命令キャッシュにおいて保存されているかどうかを確かめて、ミスの場合には高次メモリへのアクセスを開始するように動作する制御回路と；
前記予測された分岐ターゲットアドレスが前記フェッチステージパイプラインを通して流れることを可能にするために、前記第１の命令アドレスが前記フェッチステージパイプラインからフラッシュされた後、前記第１の命令アドレスを見つけるための前記高次メモリへの前記アクセスの間に、前記第１の命令アドレスを保存するように、そして、前記予測された分岐ターゲットアドレスが前記フェッチステージパイプラインへとロードされた後に、前記第１の命令アドレスを前記フェッチステージパイプラインにリロードするように、動作するリフェッチレジスタと；
を備えるプロセッサ。
【発明の詳細な説明】
【背景】
【０００１】
（発明の分野）
本発明は、一般にプロセッサの命令のプリフェッチ(prefetching)に関し、具体的には非シーケンシャル命令(non-sequential instruction)のプリフェッチに関する。
【０００２】
（関連背景）
マイクロプロセッサは、ポータブル電子デバイス(portable electronic devices)を含んでいる、多種多様なアプリケーションにおいて、計算のタスク(computational tasks)を実行する。多くのケースにおいて、追加の機能および特徴がポータブル電子デバイスおよび他のアプリケーションにおいてインプリメントされる(implemented)ことを可能にするために、プロセッサのパフォーマンス(performance)を最大限にすることが、主な設計目的である。さらに、電力消費量(power consumption)は、制限されたバッテリー容量を有しているポータブル電子デバイスにおける特有の懸念である。したがって、パフォーマンスを増やし、電力消費量を削減する、プロセッサの設計が望ましい。
【０００３】
最近のプロセッサは、１つまたは複数の命令実行パイプライン(instruction execution pipelines)を使用しており、ここで、多くのマルチステップのシーケンシャル命令(sequential instructions)の実施は、全体的なプロセッサのパフォーマンスを改善するために、オーバーラップされている(overlapped)。ほとんどのプログラムの空間および時間の局所参照性プロパティ(spatial and temporal locality properties)を利用して、最近実施された命令は、キャッシュ−高速の、大抵はオンチップメモリ−において、実施パイプラインによって、すぐに使えるアクセスのために(for ready access)保存される。
【０００４】
多くのプロセッサは、２つのレベルの高速キャッシュ(high-speed caches)を使用している。そのようなプロセッサにおいて、第１レベルは、データを保存するためのデータキャッシュ(data cache)と、命令を記憶するための命令キャッシュ(instruction cache)と、を従来備えている。データキャッシュと命令キャッシュは、別々であってもよいし、または、一体化(unified)されていてもよい。第２レベル（Ｌ２）キャッシュは、例えば動的ランダムアクセスメモリ(Dynamic Random Access Memory)（ＤＲＡＭ）、フラッシュメモリ、ハードディスクドライブ、光学ドライブ、および同様のもののような、マイクロプロセッサに外付けのメモリと第１レベルキャッシュの間で、高速メモリバッファを提供している。
【０００５】
キャッシュメモリの一般的なスタイルは、ランダムアクセスメモリ(Random Access Memory)（ＲＡＭ）に結合されたコンテントアドレサブルメモリ(Content Addressable Memory)（ＣＡＭ）を備えている。キャッシュは、完全なあるいは部分的な、以前にアクセスされた、ＣＡＭにおいて保存されたメモリアドレスに対して、メモリアドレスを比較することによってアクセスされる。アドレスがＣＡＭアドレスとマッチする(matches)場合、キャッシュは、「ヒット(hit)」を示し、マッチングＣＡＭアドレスに対応するＲＡＭにおけるロケーションから、データの「ライン(line)」（命令キャッシュのケースにおいては、１つまたは複数の命令を備えるかもしれない）をさらに提供することができる。もし比較アドレスが、ＣＡＭに保存されたいずれのメモリアドレスともマッチしない場合、キャッシュは、「ミス(miss)」を示す。第１レベルのキャッシュにおけるミスは、通常、Ｌ２キャッシュアクセスをトリガし(triggers)、それは、第１レベルのキャッシュアクセスよりも、より多くの数の処理サイクルを必要とする。Ｌ２キャッシュにおけるミスは、メインメモリへのアクセスをトリガし、より大きな遅れ(delay)さえも招く。
【０００６】
ＣＡＭ比較（例えば、アドレスがキャッシュにおいてヒットする(hits)かどうか決定すること）は、比較的電力効率がよい(power efficient)。しかしながら、ヒットのイベント(event)においてキャッシュＲＡＭからデータあるいは命令を検索することは、大量の電力を消費する。したがって、いくつかのプロセッサは、その時にキャッシュからそれらの命令を実際に検索する電力ペナルティ(power penalty)を受けることなく、望まれる命令が命令キャッシュにおいて保存されているかどうかを有利に確かめるために、プリフェッチオペレーション(prefetch operation)を利用する。ここに使用されているように、用語、「プリフェッチ(prefetch)」あるいは「プリフェッチオペレーション(prefetch operation)」は、ヒットあるいはミスをもたらす(yields)制限された命令キャッシュアクセスを指しており、アドレスがヒットする場合にはキャッシュから命令を検索することなく、命令アドレスに関連づけられる１つまたは複数の命令が命令キャッシュにおいて保存されているかどうかを示す。すなわち、プリフェッチオペレーションは、ＲＡＭにではなく、命令キャッシュＣＡＭにアクセスする。ここに使用されているように、用語「フェッチ(fetch)」あるいは「フェッチオペレーション(fetch operation)」は、キャッシュヒット(cache hit)の場合にキャッシュから１つまたは複数の命令を検索する命令キャッシュアクセスを含むメモリオペレーションを指す。ここにおいてより十分に説明されているように、フェッチオペレーションは、分岐予測回路(branch prediction circuits)、例えば分岐ターゲットアドレスキャッシュ(branch target address cache)および分岐履歴テーブル(branch history table)、に更にアクセスするが、プリフェッチオペレーションはしない。フェッチオペレーションとプリフェッチオペレーションの両方−両方とも命令キャッシュアクセスを実行する−は、プロセッサパイプラインの同じセクションにおいて起こる可能性があるということは注目されるべきである。
【０００７】
従来の命令のプリフェッチは、シーケンシャル命令アドレス(sequential instruction addresses)に基づいて、命令キャッシュのヒット／ミスのルックアップ(hit/miss lookups)を実行することを含んでいる。例えば、第１の命令アドレス(first instruction address)が命令キャッシュミス(instruction cache miss)を引き起こす(causes)場合には、そのアドレスについてのＬ２キャッシュアクセス時間は、第２のアドレス、次のシーケンシャルキャッシュラインのそれを計算するように使用されることができる。この第２のアドレスをプリフェッチすることは、シーケンシャルキャッシュライン(sequential cache line)が命令キャッシュにおいて存在しているかどうかを確かめる。それがない（すなわち、第２のアドレスがミスする(misses)）場合には、次のシーケンシャルキャッシュラインについてのＬ２キャッシュフェッチは、最初のＬ２キャッシュアクセスについてのアクセス時間(access time for the first L2 cache access)の後ろにそれを効率的に隠して、開始されることができる。他方では、次のシーケンシャルキャッシュラインが命令キャッシュにおいて存在する（すなわち、第２のアドレスがヒットする）場合には、プリフェッチは、ＲＡＭを読み取らず、Ｌ２リクエストは開始されない。この時点で、プリフェッチは完了したと思われる。したがって、プリフェッチオペレーションは、次のシーケンシャルキャッシュラインのアドレスが命令キャッシュをミスする場合には、オーバーラップされたＬ２アクセスを可能にするが、アドレスがヒットする場合には、シーケンシャル命令を実際にフェッチする電力コストを招かない。シーケンシャル命令アドレスをプリフェッチすることは、いくつかの分岐命令を含むあるいは分岐命令を含まないソフトウェアを実施するときに、パフォーマンスおよび電力マネジメントの改善の両方を提供する。しかしながら、シーケンシャル命令アドレスをプリフェッチすることは、頻繁な分岐命令(frequent branch instructions)を含んでいるソフトウェアを実施するときに利益を提供しない、というのは、シーケンシャルアドレスからプリフェッチされた命令は、分岐に起因して実施されそうにないからである。
【本開示の概要】
【０００８】
１つまたは複数の実施形態によれば、プリフェッチオペレーションは、非シーケンシャル(すなわち分岐)命令アドレス上で実行される。具体的に、第１の命令アドレスが命令キャッシュにおいてミスし、フェッチオペレーションの一部として高次メモリ(higher-order memory)にアクセスし、分岐予測回路が第１の命令アドレスあるいは第１の命令アドレスに続くアドレス(an address following the first instruction address)に関連づけられる分岐命令を検出し、そしてさらに、分岐が成立と評価するであろうこと(the branch will evaluate taken)を予測する場合には、プリフェッチオペレーションは、高次メモリアクセスの間に、次のシーケンシャルキャッシュラインアドレスの代わりに、予測された分岐ターゲットアドレスを使用して、実行される。もし予測された分岐ターゲットアドレスがプリフェッチオペレーションの間に、命令キャッシュにおいてヒットする場合には、関連する命令は、電力を維持する(conserve)ために、検索されない。予測された分岐ターゲットアドレスが命令キャッシュにおいてミスする場合には、高次メモリアクセスは、前記予測された分岐命令アドレスを使用して、起動するであろう。いずれの場合においても、第１の命令アドレスは、その高次メモリアクセスから命令の戻り(return)を待つために、フェッチステージパイプラインへとリロードされる(re-loaded)。
【０００９】
１つの実施形態は、命令をフェッチする方法に関連する。命令キャッシュは、キャッシュミスを引き起こす、第１の命令アドレスを用いてアクセスされる。第２の命令アドレスが得られ、それは、第１の命令アドレスあるいは第１の命令アドレスに続くアドレスに関連づけられる、予測された成立分岐命令(predicted-taken branch instruction)の分岐ターゲットアドレスである。より高いレベルメモリトランザクション(higher-level memory transaction)は、第１の命令アドレスに関連づけられる１つまたは複数の命令を検索するために、開始される。より高いレベルメモリトランザクションの間に、第２の命令アドレスに関連づけられる１つまたは複数の命令のうちの、命令キャッシュにおいて、存在が、もしあれば、命令キャッシュからいずれの命令も検索しないで、確かめられる。
【００１０】
別の実施形態は命令をフェッチする方法に関する。１つまたは複数の命令は、第１の命令アドレスを用いてフェッチされる。第１の命令アドレスが第１レベル命令キャッシュにおいてミスし、高次メモリアクセスを開始し、第１の命令アドレスあるいは第１の命令アドレスに続くアドレスに関連づけられる分岐命令が成立と予測される(is predicted taken)場合には、命令は、第１の命令アドレスの高次メモリアクセスの間に、分岐命令の予測された分岐ターゲットアドレスである第２の命令アドレスを用いてプリフェッチされる。
【００１１】
さらに、別の実施形態は、プロセッサに関する。プロセッサは、フェッチあるいはプリフェッチオペレーションにおいて、適用される命令アドレスについてのヒットあるいはミスのインジケーション(indication)を提供するように、そして、フェッチオペレーションにおいては命令をさらに供給するように、動作する命令キャッシュメモリを含んでいる。プロセッサは、また、適用される命令アドレスがフェッチオペレーションにおいて命令キャッシュをミスする場合に命令を提供するように動作する高次メモリと、フェッチステージパイプラインを含んでいる命令実行パイプラインと、第１の命令アドレスあるいは第１の命令アドレスに続くアドレスに関連づけられる分岐命令を検出するように、そして、分岐評価予測(branch evaluation prediction)と予測された分岐ターゲットアドレスを提供するように動作する分岐予測回路と、を含んでいる。プロセッサは、第１の命令アドレスが命令キャッシュをミスし、高次メモリにアクセスし、分岐予測回路が、第１の命令アドレスあるいは第１の命令アドレスに続くアドレスを使用してフェッチステージパイプラインにおけるフェッチオペレーションにおいて、成立分岐(a taken branch)を予測するときに、予測された分岐ターゲットアドレスを使用して、フェッチステージパイプラインにおけるプリフェッチオペレーションを起動するように動作する制御回路(control circuits)、をさらに含んでいる。
【００１２】
もちろん、本発明は、上記の特徴および利点に限定されていない。当業者は、以下の詳細な説明を読むことにより、また、添付図面を見ることにより、さらなる特徴および利点を理解するであろう。
【図面の簡単な説明】
【００１３】
【図１】図１は、プロセッサの機能ブロック図である。
【図２】図２は、プロセッサ命令ユニットのプリフェッチおよびフェッチステージの機能ブロック図である。
【図３】図３は、命令アドレスをプリフェッチする方法を図示しているフロー図である。
【図４】図４は、命令ユニットのプリフェッチおよびフェッチのステージを通じてシーケンシャルアドレスのフローを図示しているステート図である。
【図５】図５は、命令ユニットのプリフェッチおよびフェッチのステージを通じて非シーケンシャルアドレスのフローを図示しているステート図である。
【図６】図６は、命令ユニットのプリフェッチおよびフェッチのステージを通じて、非シーケンシャルアドレスのフローを図示しているステート図であり、ここで、分岐命令は、高次メモリアクセスを起動する命令アドレスに続くアドレスに関連づけられる。
【詳細な説明】
【００１４】
図１は、シーケンシャルおよび非シーケンシャル命令のプリフェッチの両方を実行するプロセッサ１０の一実施形態を図示する。フェッチされている命令フェッチグループのアドレスが命令キャッシュにおいてミスする場合には、高次メモリアクセスが開始される。これに応じて、メモリアクセスが未定のままである(pending)間に、次の命令アドレスのそのアドレスに関連づけられるフェッチグループ内の分岐命令が成立されると予測される場合には、プロセッサ１０は、予測された成立分岐命令(the predicted taken branch instruction)に関連づけられる分岐ターゲットアドレスを得て、プリフェッチする。第１のアドレスがミスし、フェッチグループが成立と予測される分岐命令を含まない場合には、プロセッサ１０は、次のシーケンシャルキャッシュラインのアドレスをプリフェッチする。いずれの場合においても、プリフェッチアドレスが命令キャッシュにおいてミスする場合には、高次メモリアクセスは、開始される。代替的に、プリフェッチアドレスが命令キャッシュにおいてヒットする場合、命令キャッシュから命令を検索するために電力を消費することなく、プリフェッチオペレーションは完了する。
【００１５】
より詳細には、プロセッサ１０は、命令ユニット１２、１つまたは複数の実行ユニット１４、第１レベルのデータキャッシュ１６および命令キャッシュ１８、第２レベル（Ｌ２）キャッシュ２０、そして、バスインタフェースユニット(bus interface unit)２２、を含んでいる。命令ユニット１２は、実行ユニット１４に対して、命令フローの集中的制御(centralized control)を供給する。実行ユニット１４は、命令ユニット１２によってディスパッチされた(dispatched)命令を実施する。データキャッシュ１６および命令キャッシュ１８は、それぞれ、データと命令を保存する。バスインタフェースユニット２２は、データ、命令、アドレス、および制御信号を、プロセッサ１０におよびプロセッサ１０から、トランスファするためのメカニズムを提供するけれども、Ｌ２キャッシュ２０は、データキャッシュ１６および命令キャッシュ１８と、プロセッサ１０に外付けのメモリ（示されてはいない）との間で、高速メモリバッファを提供する。
【００１６】
命令ユニット１２は、プリフェッチステージ２４、フェッチステージ２６、そしてデコードステージ２８を含んでいる。プリフェッチステアリング論理(prefetch steering logic)３０の制御下のプリフェッチステージ２４は、現在フェッチされている命令フェッチグループにおいて予測された成立分岐命令(predicted-taken branch instructions)の存在に基づいて、２つの命令プリフェッチ技術のうちの１つを実施する。フェッチステージ２６は、命令キャッシュ１８、Ｌ２キャッシュメモリ２０および／またはメインメモリ（示されていない）から命令データを検索し、そして、デコードステージ２８は、検索された命令をデコードする。命令ユニット１２は、命令キュー(instruction queue)３２、命令ディスパッチユニット３４、そして、分岐予測ユニット(Branch Prediction Unit)（ＢＰＵ）３６をさらに含んでいる。命令キュー３２は、デコードステージ２８によってデコードされた命令を保存し、命令ディスパッチユニット３４は、適切な実行ユニット１４に対して、キューに入れられた命令(queued instructions)をディスパッチする。ＢＰＵ３６は、分岐命令を検出し、検出される分岐のタイプに依存して、様々な分岐予測メカニズムを、例えば、分岐ターゲットアドレスを、および／または、特定の分岐が成立であるか不成立であるかを、予測することによって、実施する。
【００１７】
分岐検出および予測において助けるために、命令ユニット１２は、分岐ターゲットアドレスキャッシュ３８(Branch Target Address Cache)（ＢＴＡＣ）と、分岐履歴テーブル４０(Branch History Table)（ＢＨＴ）と、を含んでいる。ＢＴＡＣ３８は、前に実施された分岐命令に関連付けられた分岐ターゲットアドレスを保存する。従来のＢＴＡＣｓは、複数のエントリ(a plurality of entries)を備えており、それぞれは、単一の、既知で、前に成立と評価された分岐命令に対応する命令アドレスによってインデクス付けされ、また、各ＢＴＡＣエントリは、分岐命令に対応する単一の分岐ターゲットアドレスを供給している。最新のプロセッサは、しばしば、一度に２つまたはそれ以上の命令をフェッチする。したがって、ＢＴＡＣエントリは、１つ以上の命令に関連づけられていてもよい。
【００１８】
本出願の譲渡人に受け渡され、参照によってここに組み込まれた、米国仮特許出願第１１／３８２，５２７号、「ブロックベースの分岐ターゲットアドレスキャッシュ(Block-Based Branch Target Address Cache)」は、それぞれのエントリが１ブロックの命令に関連付けられる複数エントリを保存しているブロックベースのＢＴＡＣを開示しており、ここで、ブロックにおける１つまたは複数の命令は、成立と評価された分岐命令である。ＢＴＡＣエントリは、関連するブロック内の命令が成立分岐命令であるインジケータと、成立分岐の分岐ターゲットアドレスと、を含んでいる。ＢＴＡＣエントリは、ブロックにおけるすべての命令に共通であるアドレスビットによってインデクス付けされる（すなわち、ブロック内の命令を選択する下位アドレスビットを打ち切ることによって）。したがってブロックサイズと、相対的なブロック境界(relative block borders)の両方は、固定されている。
【００１９】
本出願の譲渡人に受け渡され、参照によってここに組み込まれた、米国仮特許出願第１１／４２２，１８６号、「スライディングウィンドウ、ブロックベースの分岐ターゲットアドレスキャッシュ(Sliding-Window, Block-Based Branch Target Address Cache)」は、各ＢＴＡＣがフェッチグループに関連づけられる、ブロックベースのＢＴＡＣを開示しており、また、フェッチグループにおいて第１の命令アドレスによってインデクス付けされる。フェッチグループは異なる方法（例えば、別の分岐のターゲットで始める）において形成されることができるので、各ＢＴＡＣエントリによって表わされている命令のグループは固定されていない。各ＢＴＡＣエントリは、フェッチグループ内の命令が成立分岐命令であるインジケータと、成立分岐の分岐ターゲットアドレスと、を含んでいる。
【００２０】
ここに使用されているように、単一の命令フェッチオペレーションにおいて命令キャッシュ１８からフェッチされる１つまたは複数の命令は、グループにおける命令の数、グループのストラクチャ、あるいは、それを定義しアドレス指定するために使用されるアドレッシングメカニズム(addressing mechanism)にかかわらず、「フェッチグループ(fetch group)」と呼ばれる。ここに主張され開示された非シーケンシャルプリフェッチは、命令が、単独で、あるいは、ブロックのグループで、フェッチされるかいずれにせよ、命令をプリフェッチすることが有利で適用可能である。単一のフェッチオペレーションにおいて検索される１つまたは複数の命令を指すための、用語「フェッチグループ(fetch group)」のここにおける使用は、限定されていない。
【００２１】
フェッチオペレーションの間に、ＢＴＡＣ３８と命令キャッシュ１８に平行してアクセスされる、ＢＨＴ４０は、分岐予測でＢＰＵ３６を提供する。ＢＨＴ４０は、一実施形態において、それぞれが分岐命令に関連づけられる例えば２ビット飽和カウンタ(two-bit saturation counters)、のアレイを備えている。一実施形態においては、分岐命令が成立と評価するたびに、カウンタはインクリメントされる(incremented)ことができ、そして、分岐命令が不成立と評価するときにデクリメントされる(decremented)ことができる。その後で、カウンタ値は、予測（最上位ビットのみを考慮することによって）と、予測の強度あるいは信頼性の両方を示している、例えば、
１１−強く予測される成立(Strongly predicted taken)
１０−弱く予測される成立(Weakly predicted taken)
０１−弱く予測される不成立(Weakly predicted not taken)
００−強く予測される不成立(Strongly predicted not taken)
ＢＨＴ４０は、ＢＴＡＣ４０と平行して、命令アドレスの一部によってインデクス付けされる。正確さを向上し、ＢＨＴ４０をより効率的に利用するために、当技術分野において知られているように、命令アドレスは、ＢＨＴ４０をインデクス付けする前に、最新のグローバル分岐評価履歴（ｇｓｅｌｅｃｔあるいはｇｓｈａｒｅ）と論理的に組み合わせられることができる。
【００２２】
命令ユニット１２のＢＰＵ３６は、現在フェッチされている命令フェッチグループにおいて分岐命令を検出し、その評価を予測し、予測される分岐ターゲットアドレスを提供するために、ＢＴＡＣ３８およびＢＨＴ４０によって保持される情報を使用する。ここに説明されているように、命令フェッチグループアドレスが命令キャッシュにおいてミスする場合には、命令ユニット１２は、それに関連づけられる命令が命令キャッシュにおいて存在しているかを決定するために、予測される分岐ターゲットアドレスをプリフェッチし、もしそうでない場合には、命令フェッチグループアドレスについての高次メモリアクセスの待ち時間(latency)の間に、予測される分岐ターゲットアドレスにおいて、命令を検索する高次メモリアクセスを起動する。
【００２３】
図２は、命令ユニット１２の選択されたエレメントに加えて、プリフェッチおよびフェッチステージ２４−２６の一実施形態を図示している。注意：フェッチステージ２６と、ＢＴＡＣ３８、ＢＨＴ４０、命令キャッシュ１８、およびＬ２キャッシュ２０が接続している図２において示される点線は、フェッチステージ２６がこれらのエレメントに対してアクセスを有しているということを図示しているが、直接の物理的な接続(direct physical connections)を必ずしも意味していない。プリフェッチステージ２４は、プリフェッチステアリング論理あるいはｍｕｘ３０、プリフェッチアドレスを保持するためのレジスタ４２、リフェッチレジスタ(refetch register)５６、キャッシュアクセスステアリング論理４４、インクリメンタ４６、およびインクリメント−アンド−マスク回路(increment-and-mask circuit)４８、を含んでいる。
【００２４】
プリフェッチステアリングｍｕｘ３０は、次のシーケンシャル命令キャッシュラインのアドレス、あるいは、非シーケンシャル命令アドレスのいずれかを、（ＦＥＴＣＨ１あるいはＦＥＴＣＨ２のいずれかから）プリフェッチレジスタ４２へと方向づける(directs)。どの命令アドレスが操作するかについての決定は、より高いレベルのメモリ―Ｌ２キャッシュ２０あるいは外部メモリ―から現在アクセスされているフェッチグループが既知で、予測された成立、分岐命令を含むかどうか、に基づいている。すなわち、もしより高いレベルのメモリから現在フェッチされている命令のうちの１つが予測された成立分岐命令である場合には、そのときには、その命令についての分岐ターゲットアドレスは、そのアドレスに関連づけられる命令が命令キャッシュ１８において存在しているかどうかを確かめるために、プリフェッチされる。そうでなければ、次のシーケンシャルキャッシュラインのアドレスがプリフェッチされる、すなわち、ＦＥＴＣＨ３におけるアドレスは、インクリメント−アンド−マスク論理４８によって変更されている(altered)。
【００２５】
フェッチステージ２６は、２つの命令キャッシュアクセスパイプラインステージ、すなわち、ＦＥＴＣＨ１ステージ５０とＦＥＴＣＨ２ステージ５２を含んでおり、それぞれは、フェッチあるいはプリフェッチオペレーションのいずれかについて、命令キャッシュ１８にアクセスするための論理とレジスタを備えている。さらに、フェッチステージ２６は、また、命令キャッシュ１８におけるミスのイベントにおいて、例えばＬ２キャッシュ２０のような、より高いレベルのメモリにアクセスするための、第３のフェッチパイプラインステージ、ＦＥＴＣＨ３ステージ５４、を含んでいる。いくつかの実施形態においては、キャッシュにアクセスすることはマルチプル処理サイクルを行い(takes)、したがって、マルチプルの命令キャッシュアクセスパイプラインステージ５０、５２を含んでいる。他の実施形態においては、キャッシュルックアップ(cache lookup)は、１つの処理サイクルにおいて完全に実行されることができ、したがって、ただ１つの命令キャッシュアクセスパイプラインステージを必要とする。ただ説明を簡単にするだけのために、以下に説明される実施形態は、２つのサイクルアクセス命令キャッシュ１８に対応しており、ここで、アドレス比較は、第１のサイクルの間に終わっており、比較結果は、第２サイクルの間に提供される。しかしながら、当業者は、キャッシュルックアップを実行するフェッチステージ２６が、任意の数のアクセスサイクル、例えば単一サイクルアクセスキャッシュ、を有する命令キャッシュを適応させる(accommodating)のに適切な任意の数のパイプラインステージを備えることができるということをすぐに理解するであろう。
【００２６】
命令のフェッチグループに関連づけられる第１の命令アドレスは、図３のフロー図のブロック１００で図示されているように、フェッチステージ２６パイプラインへとロードされる。命令キャッシュアクセスパイプラインステージ−ＦＥＴＣＨ１ステージ５０およびＦＥＴＣＨ２ステージ５２−は、命令キャッシュ１８から命令のフェッチグループを検索するためにフェッチオペレーションにおいてキャッシュアクセスを実行する（ブロック１０２）。命令キャッシュルックアップは、第１のキャッシュアクセスサイクルの間に命令キャッシュ１８のＣＡＭストラクチャにおいて保存される部分的アドレスあるいはアドレスと、ＦＥＴＣＨ１ステージ５０において第１の命令アドレスを比較することによって実行される。第２のサイクルの間に、ＦＥＴＣＨ１ステージ５０におけるアドレスは、ＦＥＴＣＨ２ステージ５２へとドロップし、命令キャッシュ１８は、ヒットあるいはミスを示す（ブロック１０４）。ヒットのイベントにおいては、対応する命令は、命令キャッシュ１８から検索され、第１の命令アドレスがＦＥＴＣＨ３ステージ５４を通じて通過した後デコードステージ２８（ブロック１０６）に提供される。ミスのイベントにおいては、第１の命令アドレスは、ＦＥＴＣＨ３ステージ５４に対して提供され、ここでより高いレベルのメモリトランザクション、例えばＬ２キャッシュ２０アクセス、が開始される（ブロック１０８）。
【００２７】
第１のキャッシュアクセスサイクルの間命令キャッシュ１８アクセス（ブロック１０２）と同時に、第１の命令アドレスは、フェッチオペレーションの一部として、ＢＴＡＣ３８およびＢＨＴ４０に示されている（ブロック１１０）。ＢＴＡＣにおけるヒットは、ターゲットされるフェッチグループにおける分岐命令が前に成立と評価された、ということを示しており、第１の命令アドレスに対応するＢＨＴ４０エントリは、分岐命令の最新の評価のインジケーションを提供する。この情報は、分岐予測を公式化するために(formulate)ＢＰＵ３６によって使用されており（ブロック１１２）、それは、プリフェッチステージ２４においてキャッシュアクセスステアリング論理４４に提供されている。キャッシュアクセスステアリング論理４４は、分岐命令が検出され、成立と予測される場合に、ＢＴＡＣ３８からＦＥＴＣＨ１ステージ５０へと、分岐ターゲットアドレスを操作する(steers)（ブロック１１６）。一実施形態においては、これが発生する(occurs)とき、分岐ターゲットアドレス(branch target address)（ＢＴＡ）フラグはセットされ、そして、アドレスがＢＴＡＣ３８からロードされたということを示して、ＢＴＡフラグは、フェッチステージ２６パイプラインを通じて分岐ターゲットアドレスに、付随する(accompanies)。分岐命令が検出されない、あるいは、分岐が不成立と予測される場合には、キャッシュアクセスステアリング４４は、シーケンシャルアドレスを、ＦＥＴＣＨ１ステージ５０の出力上で操作して、インクリメンタ４６を介して、ＦＥＴＣＨ１ステージ５０（例、次の連続フェッチグループ(next successive fetch group)）へと、ロードする（ブロック１１４）。
【００２８】
第１の命令アドレスが命令キャッシュにおいてミスし（ブロック１０４）、高次メモリアクセスを起動する（ブロック１０８）場合、プリフェッチステージ２４は、進行中のより高いレベルのメモリトランザクションの待ち時間の間に、プリフェッチオペレーションを実行して、プリフェッチオペレーションを開始する。すなわち、Ｌ２キャッシュあるいはメインメモリトランザクションが処理中にある間に、後に続く命令キャッシュ(subsequent instruction cache)１８−キャッシュ１８のヒットのイベントにおいていずれの命令も戻さないが、キャッシュ１８のミスのイベントにおいて高次メモリアクセスを開始する−のアクセスが実行される、したがって、高次メモリアクセスの後ろにプリフェッチオペレーションを「隠す」。一実施形態においては、プリフェッチステージ２４は、ＦＥＴＣＨ３ステージ５４から起動されるＬ２アクセスリクエストに応じて、プリフェッチオペレーションを開始する。
【００２９】
同時に(concurrently)プリフェッチされるべき命令アドレス−ここでは第２命令アドレスと呼ばれる−は、高次メモリにアクセスする第１の命令アドレスに対して、シーケンシャルあるいは非シーケンシャルであってもよい。ＢＴＡＣ３８が、現在フェッチグループにおける分岐命令がフェッチされていないことを示す場合、あるいは、ＢＰＵ３６が不成立と評価する分岐を予測する場合、同時にプリフェッチされる命令アドレスは、現在フェッチされているキャッシュラインに続く次のシーケンシャルキャッシュラインのアドレスである（ブロック１１８）。このアドレスはＦＥＴＣＨ３ステージ５４の出力上で動作して、インクリメント−アンド−マスク回路４８によって生成される。代替的に、現在フェッチされているフェッチグループが分岐命令を含み、分岐は成立と予測される場合には、そのときは、同時にプリフェッチされるべき命令アドレスは、ＢＴＡＣ３８によって提供される分岐ターゲットアドレスであり（ブロック１２０）、それは、ＢＰＵ３６による成立予測と、ＢＴＡＣ３８ヒットとの結果として、ＢＴＡフラグに沿って、フェッチステージ２６パイプラインへと自動的にロードされる。いずれの場合においても、第１のアドレスが命令キャッシュ１８においてミスし（ブロック１０４）、高次メモリアクセスを起動した（ブロック１０８）場合、第２アドレスは、ただプリフェッチされる。
【００３０】
図２を参照すると、第２の命令アドレス−ＦＥＴＣＨ１ステージ５０あるいはＦＥＴＣＨステージ５２からの分岐ターゲットアドレスあるいはシーケンシャルアドレス−は、プリフェッチステアリングｍｕｘ３０によって選択され、プリフェッチレジスタ４２へとロードされる。一実施形態においては、ＦＥＴＣＨ１あるいはＦＥＴＣＨ２レグ(leg)は、関連されたアドレスがＢＴＡＣ３８からフェッチステージ２６パイプラインへとロードされたということを示して、対応するレジスタ５０、５２におけるＢＴＡフラグに応じて、選択される。ＢＴＡフラグが検出されない場合には、次のシーケンシャルキャッシュラインアドレスは、インクリメント−アンド−マスク論理４８からロードされる。
【００３１】
プリフェッチレジスタ４２は、キャッシュアクセスステアリング論理４４に対する複数の入力（他の入力は、介入ベクトルアドレス、および同様のものを含むことが出来る）のうちの１つである。図２には図示されていないけれども、ある属性は、プリフェッチされるべき命令アドレスに沿って、プリフェッチレジスタ４２において含まれている。これらの属性は、フェッチオペレーションからプリフェッチオペレーションを区別し、命令キャッシュ１８がプリフェッチオペレーションにおいてアクセスされるとき、第２の命令アドレスを使用して、属性は、第２の命令アドレスに沿ってフェッチステージ２６パイプラインを通じて伝播する。第２の命令アドレスあるいはプリフェッチ属性のいずれも、プリフェッチオペレーションの一部としてデコードステージ２８に受け渡されず、それは、いずれの命令も検索することなく、フェッチステージ２６において終了する。
【００３２】
プリフェッチオペレーションは、少なくとも３つの著しい点においてフェッチオペレーションとは異なる。第１に、プリフェッチ命令アドレスは、命令キャッシュ１８においてヒットする場合、キャッシュ１８は、かなりの電力節約を提供して、いずれの命令も戻さない。第２に、フェッチオペレーションの間に、ＢＴＡＣ３８およびＢＨＴ４０は、命令キャッシュ１８と同時にアクセスされ、プリフェッチオペレーションにおいては、さらなる電力節約は、ＢＴＡＣ３８およびＢＨＴ４０アクセスを抑制すること(suppressing)によって実現される。第３に、プリフェッチ命令アドレスが命令キャッシュ１８においてヒットする場合、プリフェッチオペレーションは完了しており、アドレスはフェッチステージ２６パイプラインから、フラッシュされる(flushed)。プリフェッチ命令アドレスが命令キャッシュ１８においてミスする場合、それは、フェッチステージ２６パイプラインからフラッシュされている前に、それ自体の高次メモリアクセスを開始する。対照的に、フェッチオペレーションは、デコードステージに命令を提供することによって、完成する。フェッチオペレーションおよびプリフェッチオペレーションの両方は、フェッチステージ２６パイプラインにおいて発生するということに注目してください。
【００３３】
図２において図示される実施形態において、分岐命令が検出され、成立と予測されるときに、高次メモリに現在アクセスしているフェッチグループにおける予測された成立分岐命令の分岐ターゲットアドレスは、フェッチステージ２６パイプラインへと自動的にロードされ、そして、ＢＴＡフラグがセットされる。その後で、ＢＴＡフラグに応じて、プリフェッチオペレーションのためのフェッチステージ２６パイプラインへとリロードされる前に、分岐ターゲットアドレスは、そのあと、プリフェッチセレクションｍｕｘ３０およびプリフェッチレジスタ４２を通じて循環する(cycled)。これは、プリフェッチレジスタ４２からフェッチステージ２６パイプラインに入るいずれの命令アドレスについてのプリフェッチオペレーション（フェッチオペレーションに対立するものとして）を自動的に定義する、プリフェッチ属性(prefetch attributes)を利用するためである。別の実施形態において、例えば比較的短い待ち時間Ｌ２キャッシュ２０を備えたもの、分岐ターゲットアドレスがＢＴＡＣ３８ヒットおよびＢＰＵ３６成立予測の結果としてフェッチステージ２６パイプラインへとロードされるときに、デフォルトするフェッチオペレーションは、プリフェッチレジスタ４２を通じて分岐ターゲットアドレスを循環させないで、プリフェッチオペレーションに「オンザフライ(on the fly)」で変換されることができる。当業者は、本開示の教示が与えられる場合に、与えられたアプリケーションの制約について最適のインプリメンテーションを理解するであろう。
【００３４】
第２命令アドレスが高次メモリに現在アクセスしているフェッチグループに対する次のシーケンシャルキャッシュラインのアドレスであろうと（図３、ブロック１１８）、あるいは、そのフェッチグループにおける予測された成立分岐命令の分岐ターゲットアドレスであろうと（ブロック１２０）いずれにせよ、ＦＥＴＣＨ１ステージ５０およびＦＥＴＣＨ２ステージ５２でキャッシュルックアップについての命令キャッシュ１８に提供される（ブロック１２２）。第２アドレスが命令キャッシュ１８においてヒットする場合（ブロック１２４）、第２アドレスは、フェッチステージ２６パイプラインからフラッシュされ、第１の命令アドレスは、フェッチステージ２６パイプラインへとリロードされ（ブロック１２８）、また、プリフェッチオペレーションは完了する（ブロック１３０）。他方で、第２命令アドレスが命令キャッシュ１８においてミスする場合（ブロック１２４）、ＦＥＴＣＨ３ステージ５４に伝播し、フェッチステージ２６パイプラインからフラッシュされている前に、例えばＬ２キャッシュ２０アクセス（ブロック１２６）のような、第２の高次メモリアクセスを開始する。
【００３５】
いずれの場合においても、第１の命令アドレスは、リフェッチレジスタ５６においてその間に保存されており、キャッシュアクセスステアリング論理４４を通じてフェッチステージ２６パイプラインへと引き続いてロードされる（ブロック１２８）ので、第１の命令アドレスは、命令が第１の高次メモリアクセスから戻されるときに、ＦＥＴＣＨ３ステージ５４にあるであろう。これは、プリフェッチオペレーションを完了し、第２のアドレスは、フェッチステージ２６パイプラインからフラッシュされる(ブロック１３０)。第１の命令がプリフェッチレジスタ４２からキャッシュアクセスステアリング論理４４に入らないので、第１の命令がフェッチステージ２６パイプラインに再び入るときに、フェッチオペレーションは、開始される。第１の命令は、命令キャッシュ１８において（再び）ミスするであろう。フェッチオペレーションは、ＢＴＡＣ３８およびＢＨＴ４０にアクセスするであろう、また、ＢＰＵ３６は、（同じ）分岐予測を（再び）公式化し、キャッシュアクセスステアリング論理に対してそれを提供するであろう。
【００３６】
予測された成立分岐のイベントにおいては、分岐ターゲットアドレス(それは第２、あるいはプリフェッチされた、命令アドレス)は、キャッシュステアリング論理４４によって、ＢＴＡフラグで、フェッチステージ２６パイプラインへとロードされ、フェッチオペレーションは開始される。この第２のアドレスは、命令キャッシュ１８において（再び）ミスするであろう。しかしながら、高次メモリのそのアクセス（例、Ｌ２キャッシュ２０アクセス）は、プリフェッチオペレーションの間に、すでに開始されている。第１の命令アドレスは、ＦＥＴＣＨ３ステージ５４に伝播し、高次メモリからその命令を待つであろう（ブロック１３２）。第２命令アドレスはそれの後ろにあり、それの対応する高次メモリアクセスがすでに起動している状態で、ＦＥＴＣＨ３ステージ５４に同様に到達し(arrive at)、そして、高次メモリからその命令を待つであろう（ブロック１３４）。
【００３７】
図４は、第１の命令アドレスＡに応じて、命令ユニット１２のプリフェッチステージ２４およびフェッチステージ２６を通じて命令アドレスのサイクルごとの動き(cycle-by-cycle movement)を図示する。この例においては、アドレスＡは、キャッシュルックアップおよびＬ２キャッシュ２０アクセスの間(during)命令キャッシュ１８ミスを結果としてもたらし、アドレスＡに関連づけられるフェッチグループは、不成立であるとＢＰＵ３６によって予測される１つまたは複数の分岐命令を含んでいるか、あるいは、既知の分岐命令を含んでいない。
【００３８】
第１の処理サイクルの間に、フェッチオペレーションは、ＡをＦＥＴＣＨ１ステージ５０へのロードと、命令キャッシュ１８、ＢＴＡＣ３８、そしてＢＨＴ４０の同時アクセスによって、始まる。その後で、アドレスＡは、第２の処理サイクルの間にＦＥＴＣＨ２ステージ５２へとロードされ、また、比較の結果は、キャッシュ１８ミス、ＢＴＡＣミス、および／または不成立分岐予測を示す。また、第２のサイクルの間に、次のシーケンシャル命令アドレス（８バイトを含んでいるフェッチグループの説明のための且つ非制限のケースにおける、Ａ＋０ｘ８）は、ＦＥＴＣＨ１ステージ５０の出力上で動作しているインクリメンタ４６を介してＦＥＴＣＨ１ステージ５０へとロードされる。第３のサイクルの間に、フェッチプロセスは、ＡがＦＥＴＣＨ３ステージ５４へとロードされると継続し、対応するＬ２キャッシュ２０あるいはメインメモリアクセスリクエストが開始される。また、Ａ＋０ｘ８は、ＦＥＴＣＨ２ステージ５２へとドロップされ、次のシーケンシャル命令アドレス（Ａ＋０ｘ１０）は、ＦＥＴＣＨ１ステージ５０にロードされる。
【００３９】
アドレスＡはＢＴＡＣ３８からフェッチステージ２６パイプラインへとロードされないので、ＦＥＴＣＨ１ステージ５０およびＦＥＴＣＨ２ステージ５２におけるＢＴＡフラグは以前の処理サイクルの間にセットされない。結果として、第４の処理サイクルの間に、プリフェッチステアリングｍｕｘ３０は、プリフェッチレジスタ４２に、ＦＥＴＣＨ３ステージ５４の出力上で動作しているインクリメント−アンド−マスク回路４８によってコンピュートされた、次のシーケンシャルキャッシュライン（Ａ＋０ｘ２０）のアドレスを、方向付ける。有効なアドレスでロードされているプリフェッチレジスタ４２に応じて、フェッチステージ２６パイプラインは、第５サイクルの間にそれを無効にしたまま、プリフェッチオペレーションがパイプラインを通じて自由に流れることを可能にするために、第４のサイクルの間にフラッシュされている。
【００４０】
第２アドレスＡ＋０ｘ２０は、サイクル６の間にＦＥＴＣＨ１ステージ５０へとロードされ、それは、ＢＴＡＣ３８あるいはＢＨＴ４０アクセスではない限定されたキャッシュ１８アクセスをトリガする。キャッシュ１８アクセスの第２サイクルの間に（サイクル７）、ＡはＦＥＴＣＨ１ステージ５０へとリフェッチレジスタ５６からリロードされるが、Ａ＋０ｘ２０は、ＦＥＴＣＨ２ステージ５２へとロードされる。Ｌ２アクセスが第１の命令Ａについて完了するとき、Ａは、ＦＥＴＣＨ１ステージ５０へとリロードされるので、最終的には(so that ultimately)、Ａは、ＦＥＴＣＨ３ステージ５４において待機するであろう（それが待っているときプリフェッチオペレーションは生じない）。したがって、第２の命令Ａ＋０ｘ２０についての命令キャッシュルックアップは、第１の命令Ａに関連づけられるより高いレベルのメモリトランザクションの後ろに隠されている。
【００４１】
現在の例においては、第２の命令Ａ＋０ｘ２０による命令キャッシュ１８アクセスは、キャッシュミスをもたらす。これは、サイクル８の間に、第２の命令Ａ＋０ｘ２０についてのＬ２キャッシュ２０アクセスリクエストをトリガし、それは、また、第１の命令ＡによるＬ２キャッシュ２０アクセスの待ち時間によって「隠されて(hidden)」いる。図４に図示される残余サイクル(remaining cycles)は、Ａ、Ａ＋０ｘ８、およびＡ＋０ｘ１０は、プリフェッチステージ２４およびフェッチステージ２６によって再処理されるということを示しており、したがって、第１の命令Ａに関連づけられるフェッチグループが戻されるとき、第２の命令Ａ＋０×２０についての命令キャッシュルックアップおよびＬ２キャッシュ２０リクエスト(an instruction cache lookup and L2 cache 20 request for the second instruction A+0x20)を適応させている間ずっと、それらのアドレスはデコードの準備が出来ているということを確かめる。
【００４２】
図５は、第１命令アドレスＡに応じて命令ユニット１２のプリフェッチステージ２４およびフェッチステージ２６を通じて命令アドレスのサイクルごとの動きを図示しており、それは、また、命令キャッシュ１８においてミスし、起動し、Ｌ２キャッシュ２０はアクセスする。前の例と異なり、アドレスＡに関連づけられるフェッチグループは、成立と予測される既知の分岐命令を含んでいる。
【００４３】
処理サイクル１および２の間に、命令アドレスＡは、命令キャッシュ１８においてミスを、ＢＴＡＣ３８においてヒットを、そしてＢＰＵ３６による成立予測を、引き起こす。したがって、サイクル３において、キャッシュアクセスステアリング論理４４は、ＢＴＡＣ３８からＦＥＴＣＨ１ステージ５０に分岐ターゲットアドレスＢを方向づけ、また、ＦＥＴＣＨ１ステージ５０においてＢＴＡフラグ（＊によって表示されている）をセットする。第１の命令アドレスＡは、ＦＥＴＣＨ３ステージ５４へとロードされ、そして、Ｌ２キャッシュ２０リクエストが発行される。分岐予測に応じて、Ａに続くすべてのシーケンシャル命令アドレスは、フェッチステージ２６パイプライン（この例においては、ＦＥＴＣＨ２ステージ５２におけるＡ＋０ｘ８）からフラッシュされる。
【００４４】
命令キャッシュ１８においてミスしている第１の命令アドレスＡに応じて、第２の命令フェッチアドレスは、第１の命令ＡについてのＬ２キャッシュ２０アクセス時間の間に、プリフェッチされる。ＦＥＴＣＨ１ステージ５０におけるＢＴＡフラグに応じて、分岐ターゲットアドレスＢは、Ａのフェッチグループに対して次のシーケンシャルキャッシュラインのアドレスよりむしろプリフェッチされる。したがって、アドレスＢは、プリフェッチセレクションｍｕｘ３０（ＦＥＴＣＨ１を選択する）によって選択され、サイクル４においてプリフェッチレジスタ４２へとロードされる。またサイクル４の間に、分岐ターゲットアドレスＢおよびＢＴＡフラグは、ＦＥＴＣＨ２ステージ５２に移り(proceed to)、アドレスＢは、インクリメンタ４６によってインクリメントされ、キャッシュアクセスステアリング論理４４によってＦＥＴＣＨ１ステージ５０へとロードされる。
【００４５】
サイクル５において、全体のフェッチステージ２６パイプラインは、プリフェッチオペレーションを容易にするためにフラッシュされている。第６および第７の処理サイクルの間に、キャッシュアクセスステアリング論理４４は、フェッチステージ２６パイプラインに対してプリフェッチアドレスＢを方向付けており、そしてキャッシュ１８アクセスは、―しかしＢＴＡＣ３８あるいはＢＨＴ４０アクセスではない―実行されている。またサイクル７において、第１の命令アドレスＡは、リフェッチレジスタ５６から、キャッシュアクセスステアリング論理４４によってフェッチステージ２６パイプラインへとリロードされる。
【００４６】
第２の、あるいはプリフェッチ、アドレスＢは、命令キャッシュ１８（サイクル７）においてミスしており、したがって、サイクル８においてアドレスＢについて発行されているＬ２キャッシュ２０リクエストを結果としてもたらす。もしアドレスＢが命令キャッシュ１８においてヒットする場合には、プリフェッチオペレーションは完了し、プロセッサは、アドレスＢに関連づけられる命令が命令キャッシュ１８において存在しているということを知り、Ｌ２キャッシュ２０アクセスが必要とされない、ということに注目してください。
【００４７】
またサイクル８においては、アドレスＡは、命令キャッシュ１８において（再び）ミスする。第１の命令アドレスＡは、プリフェッチレジスタ４２ではなくリフェッチレジスタ５６からキャッシュアクセスステアリング論理４４に入ったので、プリフェッチオペレーションではなく、フェッチオペレーションは、アドレスＡを使用して実行される。したがって、ＢＴＡＣ３８およびＢＨＴ４０もまたアクセスされ、第１の命令Ａについて成立分岐予測とＢＴＡＣ３８ヒットを結果としてもたらす。このことは、サイクル９において、Ａ（この例においては、ＦＥＴＣＨ２ステージ５２）の後ろですべてのシーケンシャルインクリメントされたアドレスをフラッシュすることと、そして、ＦＥＴＣＨ１ステージ５０へと、ＢＴＡフラグに沿って、ＢＴＡＣ３８から分岐ターゲットアドレスＢをロードすることと、をもたらす。
【００４８】
この時点で、第１の命令アドレスＡおよび分岐ターゲットアドレスＢの相対的なオーダリング(relative ordering)は、もとに戻される(restored)。第１の命令アドレスＡは、ＦＥＴＣＨ３ステージ５４においてあり、Ｌ２キャッシュ２０あるいはメインメモリから命令を待っている。分岐ターゲットアドレスＢは、フェッチステージ２６パイプラインを通じて処理し、命令キャッシュ１８においてミスし、そして、その進行中のＬ２アクセスの結果を待ってＦＥＴＣＨ３ステージ５４において次第に停止するようになるであろう(come to rest)。しかしながら、リクエストは、サイクル８において−命令ＡによるＬ２キャッシュ２０アクセスの待ち時間の間に、前に発行されていたので、このＬ２アクセスから命令を受信することを経験した待ち時間は低減しているように見えるであろう。
【００４９】
図６は、命令キャッシュ１８においてミスする第１の命令アドレスＡに応じて、命令ユニット１２のプリフェッチステージ２４およびフェッチステージ２６を通じて命令アドレスのサイクルごとの動きを図示し、そして、Ｌ２アクセスを起動する。この例においては、アドレスＡに関連づけられるフェッチグループは、既知の分岐命令を含んでいないが、次のアドレスＡ＋０ｘ８に関連づけられるフェッチグループは、成立と予測される既知の分岐命令を含んでいる。
【００５０】
命令アドレスＡは、サイクル１においてフェッチステージ２６パイプラインへとロードされ、サイクル２においてＢＴＡＣ３８および命令キャッシュ１８においてミスする。サイクル３において、命令アドレスＡは、ＦＥＴＣＨ３ステージ５４に移るが、サイクル４までＬ２キャッシュ２０アクセスリクエストを開始しない。これは、例えば、新しいリクエストを作るために空ける(to free up room)のに必要なペンディングキャッシュ管理オペレーション(a pending cache management operation)に起因しているかもしれない。サイクル３の間に、命令アドレスＡがＬ２を作る前に、次のシーケンシャルフェッチグループについての命令アドレスＡ＋０ｘ８は、命令キャッシュ１８においてミスするが、ＢＴＡＣ３８においてヒットし、分岐命令は、成立と予測される。これに応じて、サイクル４において、分岐ターゲットアドレスＢは、キャッシュアクセスステアリング論理４４によってＦＥＴＣＨ１ステージ５０に操作され、ＢＴＡフラグがセットされる。
【００５１】
サイクル５において、命令アドレスＡについてのＬ２キャッシュ２０アクセスリクエストに応じて、プリフェッチステージ２４は、プリフェッチオペレーションを開始する。ＦＥＴＣＨ１ステージ５０においてセットされているＢＴＡフラグに応じて、分岐ターゲットアドレスＢは、プリフェッチセレクションｍｕｘ３０によって操作され、プリフェッチレジスタ４２へとロードされる。命令アドレスＡは、ＦＥＴＣＨ３ステージ５４からリフェッチレジスタ５６に保存され、次のサイクルにおいては、フェッチステージ２６パイプラインは、プリフェッチオペレーションを容易にするために、フラッシュされる。
【００５２】
プリフェッチオペレーションは、分岐ターゲットアドレスＢが、命令キャッシュ１８（抑制されているＢＴＡＣ３９およびＢＨＴ４０アクセス）においてミスする状態で、上記に説明されているように処理し、Ｌ２キャッシュ２０リクエストを起動するためにＦＥＴＣＨ３ステージ５４に移る。このことは、プリフェッチオペレーションを完了し、命令アドレスＡは、フェッチステージ２６パイプラインへとリロードされる。通常のフェッチオペレーション処理を介して、Ｌ２アクセスから命令を受信するために適切な関連オーダ(proper relative order)において、命令アドレスＡ＋０ｘ８およびＢはフェッチステージ２６パイプラインへと起動される。
【００５３】
この例においては、命令アドレスＡ＋０ｘ８は、命令キャッシュ１８においてミスしたが、Ｌ２キャッシュ２０アクセスを実行しなかった。命令キャッシュ１８、２０ラインが命令フェッチグループのサイズよりも大きい場合、命令アドレスＡ＋０ｘ８に関連づけられるフェッチグループは、統計的に、命令アドレスＡに関連づけられるフェッチグループと同じキャッシュラインにおいて存在する可能性がある。もしこれが本当であるならば、両方のフェッチグループについての命令は、命令アドレスＡを使用するＬ２キャッシュ２０アクセスによって、命令キャッシュ１８へと、ロードされる。本当ではない場合（統計的にはまれ）においては、命令アドレスＡ＋０ｘ８に関連づけられるフェッチグループは、Ｌ２キャッシュ２０から別々にフェッチされなくてはならない。しかしながら、この場合においてでさえ、分岐ターゲットアドレスＢを使用するプリフェッチオペレーションが、予測される命令アドレスＢに関連づけられるフェッチグループを命令キャッシュ１８へと効率的な方法でロードするのに有効的であった。代替的に、アドレスＢが命令キャッシュ１８においてヒットする場合、プリフェッチオペレーションは、そのときに命令キャッシュ１８からそれらを抽出することに関連づけられたパワードレイン(power drain)を回避している間、関連する命令が存在するということをヴェリファイする(verify)のに有効的であった。
【００５４】
本発明は、特定の特徴、態様、およびそれらの実施形態に関して、ここに説明されてきたけれども、多くの変形、修正、および他の実施形態は、本発明の広い範囲内で可能であり、したがって、すべての変形、修正、および実施形態は、本発明の範囲内にあるものとしてみなされるべきであるということは、明らかであろう。したがって、本実施形態は、すべての態様において限定のためではない説明のためとして解釈されるべきであり、添付された特許請求の範囲の意味および同等な範囲(the meaning and equivalency range)の中に入るすべての変更は、そこに包含されるように意図されている。
以下に、本願発明の当初の［特許請求の範囲］に記載された発明を付記する。
［１］
キャッシュミスを引き起こす第１の命令アクセスを用いて、命令キャッシュにアクセスすることと、
予測された成立分岐命令の分岐ターゲットアドレスである第２の命令アドレスを得ることと、
前記第１の命令アドレスに関連づけられる１つまたは複数の命令を検索するために、より高いレベルのメモリトランザクションを開始することと、
前記命令キャッシュからいずれの命令も検索することなく、前記第２の命令アドレスに関連づけられる１つまたは複数の命令が前記命令キャッシュにおいて保存されているかどうかを、前記より高いレベルのメモリトランザクションの間に、確かめることと、
を備える命令をフェッチする方法。
［２］
第２の命令アドレスを得ることは、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスを用いて、分岐ターゲットアドレスキャッシュにアクセスすることを備える、［１］に記載の方法。
［３］
前記分岐ターゲットアドレスキャッシュにおける各エントリは、１つまたは複数の命令のフェッチグループに関連付けられており、そのうちの少なくとも１つは前に成立と評価された分岐命令である、［２］に記載の方法。
［４］
前に成立と評価された前記分岐命令の前記評価を予測すること、をさらに備える［３］に記載の方法。
［５］
前記分岐命令の前記評価を予測することは、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスを使用して、前記分岐命令の過去の評価のインジケーションを保存している分岐履歴テーブルにアクセスすることをさらに備える、［４］に記載の方法。
［６］
属性を前記第２の命令アドレスに関連づけること、をさらに備え、前記属性は、前記第２の命令アドレスに関連付けられる１つまたは複数の命令が前記命令キャッシュにおいて保存されているかどうかを確かめるとき、前記命令キャッシュからいずれの命令も検索されるべきではないということを示している、［１］に記載の方法。
［７］
もし前記第２の命令アドレスに関連づけられる命令が前記命令キャッシュにおいて保存されていない場合には、前記第２の命令アドレスに関連づけられる１つまたは複数の命令を検索するためにより高いレベルのメモリトランザクションを開始すること、をさらに備える［１］に記載の方法。
［８］
前記命令キャッシュにアクセスするために前記第２の命令アドレスが命令フェッチパイプラインを通して流れる間に、前記第１の命令アドレスを保存することと、そして、引き続いて前記命令フェッチパイプラインへと前記第１の命令アドレスをリロードすることと、をさらに備える［７］に記載の方法。
［９］
前記予測された成立分岐命令は、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連づけられる、［１］に記載の方法。
［１０］
第１の命令アドレスを用いて１つまたは複数の命令をフェッチすることと、
もし前記第１の命令アドレスが第１レベル命令キャッシュにおいてミスし、高次メモリアクセスと予測された成立分岐命令とを開始する場合には、前記第１の命令アドレスの前記高次メモリアクセスの間に、前記の分岐命令の予測される分岐ターゲットアドレスである第２の命令アドレスを用いて命令をプリフェッチすることと、
を備える命令をフェッチする方法。
［１１］
前記予測される分岐ターゲットアドレスは、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスによってインデクス付けされる分岐ターゲットアドレスキャッシュから検索される、［１０］に記載の方法。
［１２］
もし前記第２の命令アドレスが第１レベル命令キャッシュにおいてミスする場合には、前記第１の命令アドレスの前記高次メモリアクセスの間に、前記第２の命令アドレスを使用して高次メモリアクセスを開始すること、をさらに備える［１０］に記載の方法。
［１３］
フェッチあるいはプリフェッチオペレーションが実行されるかどうかは、プリフェッチレジスタにおいて命令アドレスに関連づけられる属性によって決定される、［１０］に記載の方法。
［１４］
前記予測される分岐ターゲットアドレスは、命令フェッチパイプラインにおいて前記予測される分岐ターゲットアドレスに関連づけられる分岐ターゲットアドレスフラグに応じて、前記プリフェッチレジスタへとロードされる、［１３］に記載の方法。
［１５］
前記予測された成立分岐命令は、前記第１の命令アドレスに関連づけられ、あるいは前記第１の命令アドレスに続くアドレスは成立と予測される、［９］に記載の方法。
［１６］
フェッチあるいはプリフェッチのオペレーションにおいて、適用される命令アドレスについてヒットあるいはミスのインジケーションを提供するように、そして、フェッチオペレーションにおいて命令をさらに提供するように、動作する命令キャッシュメモリと、
もし適用される命令アドレスがフェッチオペレーションにおいて前記の命令キャッシュをミスする場合には、命令を提供するように動作する高次メモリと、
フェッチステージパイプラインを含んでいる命令実行パイプラインと、
第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連付けられる分岐命令を検出するように、また、分岐評価予測と予測される分岐ターゲットアドレスとを供給するように、動作する分岐予測回路と、
前記第１の命令アドレスが、前記命令キャッシュをミスし、前記高次メモリにアクセスし、そして前記分岐予測回路が、前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスを使用して、前記フェッチステージパイプラインにおけるフェッチオペレーションにおいて成立分岐を予測するときに、前記予測される分岐ターゲットアドレスを使用して前記フェッチステージパイプラインにおけるプリフェッチオペレーションを起動するように動作する制御回路と、
を備えているプロセッサ。
［１７］
さらに、前記高次メモリは、第２レベル（Ｌ２）キャッシュメモリを備えている、［１６］に記載のプロセッサ。
［１８］
もし前記予測される分岐ターゲットアドレスが前記プリフェッチオペレーションの間に前記命令キャッシュにおいてミスする場合は、前記制御回路は、前記予測される分岐ターゲットアドレスについてのＬ２キャッシュアクセスを起動するようにさらに動作する、［１７］に記載のプロセッサ。
［１９］
前記予測される分岐ターゲットアドレスについての前記Ｌ２キャッシュアクセスは、前記第１の命令アドレスについての前記Ｌ２キャッシュアクセスが未定の間起動される、［１８］に記載のプロセッサ。
［２０］
さらに、前記高次メモリは、メインメモリを備えている、［１６］に記載のプロセッサ。
［２１］
前記フェッチステージパイプラインにおいて分岐ターゲットアドレス（ＢＴＡ）フラグ、をさらに備えており、前記分岐予測回路が第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連付けられる分岐命令を検出するときに、前記制御回路は、前記予測される分岐ターゲットアドレスを使用し、前記ＢＴＡフラグをセットして、前記フェッチステージパイプラインにおけるフェッチオペレーションを起動するように動作する、［１６］に記載のプロセッサ。
［２２］
前記ＢＴＡフラグと、高次メモリアクセスを起動する前記第１の命令アドレスと、に応じて、前記フェッチステージパイプラインから前記予測される分岐ターゲットアドレスを保存するように動作するプリフェッチレジスタ、をさらに備え、前記プリフェッチレジスタにおいて保存される前記命令アドレスが前記フェッチステージパイプラインへと起動されるときに、前記プリフェッチレジスタは、さらに、プリフェッチオペレーションを示している属性を含んでいる、［２１］に記載のプロセッサ。
［２３］
前記プリフェッチレジスタは、前記フェッチステージパイプラインにおいてＢＴＡフラグがないことと高次メモリアクセスを起動する前記第１の命令アドレスとに応じて、前記第１の命令アドレスから計算される次のシーケンシャルキャッシュラインの前記のアドレスを保存するように動作する、［２２］に記載のプロセッサ。
［２４］
前記第１の命令アドレスを保存するように、そして、前記プリフェッチオペレーションに続いて前記フェッチステージパイプラインへと前記第１の命令アドレスをリロードするように、動作する、リフェッチレジスタ、をさらに備えている［１６］に記載のプロセッサ。
［２５］
第１レベル命令キャッシュにおいてミスし、高次メモリアクセスを開始する第１の命令アドレスを用いて１つまたは複数の命令をフェッチすることと、
もし前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連づけられる分岐命令が成立と予測される場合には、前記分岐命令の予測される分岐ターゲットアドレスである第２の命令アドレスを用いて命令をプリフェッチすることと、
もしどんな予測される成立分岐命令も前記第１の命令アドレスあるいは前記第１の命令アドレスに続くアドレスに関連づけられない場合には、前記第１の命令アドレスによってアドレス指定された前記キャッシュラインに続いて次のシーケンシャル命令キャッシュラインの前記アドレスである第２の命令アドレスを用いて命令をプリフェッチすることと、
を備え、
いずれの場合においても、前記第２の命令アドレスを用いた前記のプリフェッチオペレーションは、前記第１の命令アドレスについての前記高次メモリアクセスの間に、発生する、
命令をフェッチする方法。
［２６］
前記第２の命令アドレスを用いた前記のプリフェッチオペレーションに続いて前記第１の命令アドレスをリフェッチすること、をさらに備える［２５］に記載の方法。
【図１】
0005410281.tif 000002
【図２】
0005410281.tif 000003
【図３】
0005410281.tif 000004
【図４】
0005410281.tif 000005
【図５】
0005410281.tif 000006
【図６】
0005410281.tif 000007