(57)【要約】典型的なキャッシュアーキテクチャは、プログラムストリーム内に含まれるシーケンシャル命令および非シーケンシャル命令の両方に使用されるキャッシュウェイを予測するときに使用されるただ１つのキャッシュウェイ予測メモリを提供する。残念ながら、従来技術によるキャッシュウェイ予測方式の欠点の１つは、ジャンプ命令を含むブランチ命令のようなＰＣを非シーケンシャルに変更する命令を処理するときのそれの効率にある。非シーケンシャル命令をキャッシュするのを容易にするために、付加的なキャッシュウェイ予測メモリが、提供され、非シーケンシャル命令を処理する。したがって、プログラム実行中、判定回路が、命令の種類（２５２、２５３）に基づいて、シーケンシャルキャッシュウェイ（２５１）予測アレイまたは非シーケンシャルキャッシュウェイ（２７１）予測アレイのどちらを使用するかを判定する。有利には、改善されたキャッシュウェイ予測方式は、非シーケンシャル命令とともに使用されるとき、大きなキャッシュヒット率を提供する。
2005535955.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサによって実行されるプログラムストリーム内に含まれるシーケンシャル命令および非シーケンシャル命令を記憶しかつ取り出すのに使用されるキャッシュメモリであって、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたタグアレイであり、前記複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、タグアドレスを記憶する、前記タグアレイと、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたデータアレイであり、前記複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、命令に関係するデータバイトを記憶する、前記データアレイと、
複数の行として配置された複数の記憶ロケーションを有する第１のキャッシュウェイ予測アレイであり、前記複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第１のセットを記憶する、前記第１のキャッシュウェイ予測アレイと、
複数の行として配置された複数の記憶ロケーションを有する第２のキャッシュウェイ予測アレイであり、前記複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第２のセットを記憶する、前記第２のキャッシュウェイ予測アレイと、
プログラムストリームから命令を受信する判定回路であり、前記判定回路が、命令がシーケンシャル型命令および非シーケンシャル型命令のいずれであるかを判定し、それに基づいて、前記第１のキャッシュウェイ予測アレイおよび前記第２のキャッシュウェイ予測アレイの一方を個々にイネーブル状態にし、前記イネーブル状態にされた予測アレイが、要求アドレスにおいてアクセスされ、前記キャッシュウェイ予測ビットの第１のセットおよび前記キャッシュウェイ予測ビットの第２のセットの一方を個々に取り出し、取り出された前記予測ビットに基づいて、前記タグアレイおよび前記データアレイ内のキャッシュウェイをイネーブル状態にし、イネーブル状態にされた前記キャッシュウェイ内の前記タグアレイおよび前記データアレイから前記タグアドレスおよび前記データバイトをそれぞれ取り出すのを容易にする、前記判定回路と、
を備えたキャッシュメモリ。
【請求項２】
それぞれの行が、キャッシュセットである、請求項１に記載のキャッシュメモリ。
【請求項３】
前記プログラムストリーム内の命令を実行するときに前記プロセッサによって使用されるプログラムカウンタを備え、前記要求アドレスが、前記プログラムカウンタから得られる、請求項２に記載のキャッシュメモリ。
【請求項４】
前記判定回路が、前記プログラムカウンタによってインデックスされた前記命令がブランチ命令と異なる場合に、前記第１のキャッシュウェイ予測アレイをイネーブル状態にし、かつ、前記第２のキャッシュウェイ予測アレイをディスエーブル状態にする回路を備えた、請求項３に記載のキャッシュメモリ。
【請求項５】
前記判定回路が、前記プログラムカウンタによってインデックスされた前記命令がブランチ命令である場合に、前記第１のキャッシュウェイ予測アレイをディスエーブル状態にし、かつ、前記第２のキャッシュウェイ予測アレイをイネーブル状態にする回路を備えた、請求項３に記載のキャッシュメモリ。
【請求項６】
前記判定回路が、前記プログラムカウンタによってインデックスされた前記命令がジャンプ命令である場合に、前記第１のキャッシュウェイ予測アレイをディスエーブル状態にし、かつ、前記第２のキャッシュウェイ予測アレイをイネーブル状態にする回路を備えた、請求項３に記載のキャッシュメモリ。
【請求項７】
前記キャッシュウェイ予測アレイが、アドレス入力ポートを備え、前記アドレス入力ポートが、それぞれ、前記キャッシュウェイ予測アレイに平等に結合され、それによって、同じアドレスデータが、前記キャッシュウェイ予測アレイのそれぞれに提供され、前記キャッシュウェイ予測アレイから取り出されたデータの違いが、前記命令の種類に基づいて判定される、請求項２に記載のキャッシュメモリ。
【請求項８】
前記第１のキャッシュウェイ予測アレイが、前記第２のキャッシュウェイ予測アレイよりも多い記憶ロケーションを備えた、請求項２に記載のキャッシュメモリ。
【請求項９】
前記第２のキャッシュウェイ予測アレイが、前記第１のキャッシュウェイ予測アレイよりも多い記憶ロケーションを備えた、請求項２に記載のキャッシュメモリ。
【請求項１０】
前記キャッシュメモリが、命令データをキャッシュするのに使用される、請求項２に記載のキャッシュメモリ。
【請求項１１】
複数のキャッシュ予測アレイの中から１つのキャッシュ予測アレイをイネーブル状態にする方法であって、
プロセッサが次に実行するために、プログラムカウンタのアドレスに存在する命令を提供するステップと、
前記命令が予め定められた種類の命令かどうかを判定するステップと、
前記命令が予め定められた種類の命令でなければ、第１のキャッシュ予測アレイをイネーブル状態にし、命令が予め定められた種類の命令であれば、第２のキャッシュ予測アレイをイネーブル状態にするステップと、
を備えた方法。
【請求項１２】
予め定められた種類の命令が、ブランチ命令を含む、請求項１１に記載の方法。
【請求項１３】
前記ブランチ命令が、命令データストリーム内において前記プログラムカウンタを非シーケンシャルに変化させる、種類の命令である請求項１２に記載の方法。
【請求項１４】
前記ブランチ命令が、命令データの現在の電子ページを越えた値に前記プログラムカウンタを変更する命令からなる、請求項１３に記載の方法。
【請求項１５】
命令に関するデータを記憶したメモリであって、
プロセッサが次に実行するために、プログラムカウンタのアドレスに存在する命令を提供するステップと、
前記命令が予め定められた種類の命令かどうかを判定するステップと、
前記命令が予め定められた種類の命令でなければ、第１のキャッシュ予測アレイをイネーブル状態にし、前記命令が予め定められた種類の命令であれば、第２のキャッシュ予測アレイをイネーブル状態にするステップと、
を実行するためのメモリ。
【請求項１６】
前記データに基づいて、予め定められた種類の命令が、ブランチ命令を含む、請求項１５に記載の方法。
【請求項１７】
前記データに基づいて、ブランチ命令が、前記プログラムカウンタを非シーケンシャルアドレスにするような種類の命令である、請求項１６に記載の方法。
【請求項１８】
前記データに基づいて、ブランチ命令が、命令データの現在の電子ページを超えた値に前記プログラムカウンタを変更する命令からなる、請求項１７に記載の方法。
【請求項１９】
プログラムストリーム内に含まれるシーケンシャル命令および非シーケンシャル命令の記憶および取り出しに使用されるキャッシュメモリであって、
データの第１のセットのためのキャッシュウェイを予測するのに使用される第１のキャッシュウェイ予測アレイと、
データの第２のセットのためのキャッシュウェイを予測するのに使用される第２のキャッシュウェイ予測アレイと、
前記プログラムストリームから命令データを受信し、その命令データに基づいて、前記第１のキャッシュウェイ予測アレイおよび前記第２のキャッシュウェイ予測アレイの中から一方を選択する判定回路と、
を備えたキャッシュメモリ。
【請求項２０】
データを記憶した記憶媒体であって、前記データが、集積回路設計を実施するのに使用され、前記データが、回路エレメントを記述するデータを含み、回路エレメントが、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたタグアレイであり、前記複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、タグアドレスを記憶する、前記タグアレイと、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された前記複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたデータアレイであり、前記複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、命令に関係するデータバイトを記憶する、前記データアレイと、
複数の行として配置された複数の記憶ロケーションを有する第１のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第１のセットを記憶する、前記第１のキャッシュウェイ予測アレイと、
複数の行として配置された複数の記憶ロケーションを有する第２のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第２のセットを記憶する、前記第２のキャッシュウェイ予測アレイと、
前記プログラムストリームから命令を受信する判定回路であり、前記判定回路が、前記命令がシーケンシャル型命令および非シーケンシャル型命令のいずれであるかを判定し、それに基づいて、前記第１のキャッシュウェイ予測アレイおよび前記第２のキャッシュウェイ予測アレイの一方を個々にイネーブル状態にし、前記イネーブル状態にされた予測アレイが、要求アドレスにおいてアクセスされ、前記キャッシュウェイ予測ビットの第１のセットおよび前記キャッシュウェイ予測ビットの第２のセットの一方を個々に取り出し、前記取り出された予測ビットに基づいて、前記タグアレイおよび前記データアレイ内のキャッシュウェイをイネーブル状態にし、イネーブル状態にされた前記キャッシュウェイ内の前記タグアレイおよび前記データアレイから前記タグアドレスおよび前記データバイトをそれぞれ取り出すのを容易にする、前記判定回路と、
を含む、記憶媒体。
【請求項２１】
記憶媒体に記憶されたデータを備え、前記データが、プログラムストリーム内の命令を実行するときに前記プロセッサによって使用されるプログラムカウンタを記述し、前記要求アドレスが、前記プログラムカウンタから得られる、請求項２０に記載の記憶媒体。
【請求項２２】
記憶媒体に記憶されたデータを備え、前記データが、前記プログラムカウンタによってインデックスされた前記命令がブランチ命令ではないときに前記第１のキャッシュウェイ予測アレイをイネーブル状態にしかつ前記第２のキャッシュウェイ予測アレイをディスエーブル状態にする回路を記述する、請求項２１に記載の記憶媒体。
【請求項２３】
記憶媒体に記憶されたデータを備え、前記データが、前記プログラムカウンタによってインデックスされた前記命令がブランチ命令であるときに前記第１のキャッシュウェイ予測アレイをディスエーブル状態にしかつ前記第２のキャッシュウェイ予測アレイをイネーブル状態にする回路を記述する、請求項２１に記載の記憶媒体。
【請求項２４】
前記判定回路を記述する記憶媒体に記憶されたデータが、前記プログラムカウンタによってインデックスされた前記命令がジャンプ命令であるときに前記第１のキャッシュウェイ予測アレイをディスエーブル状態にしかつ前記第２のキャッシュウェイ予測アレイをイネーブル状態にする回路を記述するデータを含む、請求項２１に記載の記憶媒体。
【請求項２５】
前記キャッシュウェイ予測アレイを記述する記憶媒体に記憶されたデータが、アドレス入力ポートを記述するデータを含み、前記アドレス入力ポートが、それぞれ、前記キャッシュウェイ予測アレイに平等に結合され、それによって、同じアドレスデータが、前記キャッシュウェイ予測アレイのそれぞれに提供され、前記キャッシュウェイ予測アレイから取り出されたデータの違いが、前記命令の種類に基づいて判定される、請求項２０に記載の記憶媒体。
【請求項２６】
前記キャッシュウェイ予測アレイを記述する記憶媒体に記憶されたデータが、前記第２のキャッシュウェイ予測アレイよりも多い記憶ロケーションを備えた前記第１のキャッシュウェイ予測アレイを指示する、請求項２０に記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュウェイ予測に関し、より詳細には、非連続性の命令を含むプログラムストリーム内の命令を実行するときに使用するためのキャッシュウェイ予測の分野に関する。
【背景技術】
【０００２】
集積回路技術が、より小さな加工寸法にまで発展するにつれ、その結果として、より速い中央演算処理装置（ＣＰＵ）が、開発されている。残念ながら、典型的には命令データが記憶されるランダムアクセスメモリ（ＲＡＭ）の形態を有するメインメモリのアクセス時間は、まだ、ＣＰＵのアクセス時間には適合していない。ＣＰＵは、これらのより遅いデバイスから命令を取り出してその命令を処理するために、それらのデバイスにアクセスしなければならない。それらの命令を取り出すとき、ボトルネックが、ＣＰＵとより遅いＲＡＭとの間に現れる。典型的には、このボトルネックの効果を低減するために、キャッシュメモリが、メインメモリとＣＰＵとの間に実装され、もっとも最近に使用された（ＭＲＵ）命令およびデータをより短いレイテンシーでプロセッサに提供する。
【０００３】
キャッシュメモリは、典型的には、メインメモリよりもサイズが小さく、そして、メインメモリよりも速いアクセス時間を提供することが、当業者には知られている。これらのより速いアクセス時間は、典型的にはプロセッサ内に存在するキャッシュメモリ、または、プロセッサのすぐ近くに存在するキャッシュメモリによって容易に実現される。キャッシュメモリは、典型的には、メインメモリとは物理的に異なる種類のものである。メインメモリは、データを記憶するためのキャパシタを利用するものであり、キャパシタの電荷を維持するために、リフレッシュサイクルが、必要である。他方において、キャッシュメモリは、メインメモリのようにリフレッシュしなくてもよい。キャッシュメモリは、典型的には、スタティックランダムアクセスメモリ（ＳＲＡＭ）の形態を有し、それぞれのビットは、約６個のトランジスタを用いてリフレッシュすることなく、記憶される。ＳＲＡＭ内のビットを表現するのにより多くのトランジスタが使用されるので、この種のメモリのビット当たりのサイズは、ダイナミックＲＡＭよりもかなり大きく、そのために、また、ダイナミックＲＡＭよりも相当に高価である。したがって、キャッシュメモリは、コンピュータシステム内で節約しながら使用され、この比較的により小さい高速メモリは、典型的には、もっとも最近にプロセッサが使用したメインメモリのブロックの内容を保持するのに使用される。
【０００４】
キャッシュメモリの目的は、メインメモリからＣＰＵへ流れる情報の命令帯域幅およびデータ帯域幅を増大させることであり、また、メインメモリから情報を転送するときに必然的に発生するレイテンシーを減少させることである。帯域幅は、所定の時間量で転送することのできる情報量を決定し、レイテンシーは、所定の情報アイテムを取り出すのにかかる時間、言い換えれば、そのアイテムの要求時刻から供給時刻までに要する時間量を決定する。ダイレクトマッピングおよびキャッシュウェイセットアソシエイティブのような、この大きな帯域幅および小さなレイテンシーを提供するキャッシュメモリの様々な構成が、存在する。当然ながら、レイテンシーおよび帯域幅の両方は、キャッシュメモリの設計において重要なものであり、多くの当業者には、キャッシュウェイセットアソシエイティブキャッシュ構造が好ましいことは明らかなことである。
【０００５】
セットアソシエイティブ構造においては、ダイレクトマッピングキャッシュ構造の場合と同様に、キャッシュメモリは、典型的には、２つの部分、すなわち、データアレイおよびタグアレイに分割して構成される。タグアレイは、データアレイに記憶されたデータバイトに対応づけるためのタグアドレスを記憶するためのものである。典型的には、それぞれのタグエントリーは、データアレイエントリーに対応し、それぞれのタグエントリーは、それぞれのデータアレイエントリーに関するインデックス情報を記憶する。両方のアレイは、２次元であり、行および列として編成される。データアレイかまたはタグアレイ内の列は、典型的には、キャッシュウェイと呼ばれ、同じキャッシュメモリ内には、１つよりも多いキャッシュウェイが、存在してもよい。したがって、４キャッシュウェイセットアソシエイティブキャッシュメモリは、４つの列、すなわち、４つのキャッシュウェイによって構成され、また、データアレイおよびタグアレイの両方は、それぞれ、４つの列を有する。
【０００６】
プロセッサは、アセンブリラインの命令と同じようなやり方で、プログラムストリーム内に含まれる命令を実行する。プロセッサがプログラムストリームに含まれるいくつかの命令を実行するのを容易にするために、プロセッサパイプラインが、提供される。プロセッサパイプラインという用語は、タスクを達成するのに要するいくつかの処理ステップまたは処理ステージを意味し、処理ステップが、少なければ少ないほど、パイプラインは、より短く、かつ、より効率のよいものとなる。プロセッサパイプライン内のステージの深さは、そのステージによる時間遅延であると定義される。したがって、ステージの深さは、プロセッサの動作周波数に影響を及ぼす。その結果として、より多くのステージを有するより深いパイプラインが、プロセッサに実装されてきた。多くのステージを有することは、それぞれのステージがより短い時間遅延を有することになり、それによって、そのステージのより高い動作周波数を実現することができる。効率的なプロセッサの設計は、ステージの数とそのステージによる遅延とのバランスをとることである。したがって、ステージの数およびそれぞれのステージの深さの両方が、プロセッサの処理効率を決定する。プロセッサパイプライン内においては、それぞれのプロセッサパイプラインステージは、パイプライン内の次の処理ステージに実行を渡す前に、特定のタスクを実行する。プロセッサパイプライン内においては、命令は、順々にロードされる。すなわち、１つの命令の一部が、以前の命令の後に、処理される。プロセッサは、異なる命令の異なるステージを同時に処理するので、パイプラインを用いて、より短い期間により多くの命令を実行することができ、それによって、プログラムストリームを迅速に実行する。命令が、完全に処理されてしまえば、命令は、パイプラインから去る。
【０００７】
ＣＰＵが、パイプライン内の命令を実行しているとき、メインメモリおよびキャッシュメモリの両方が、アクセスされる。対応するデータバイトがメモリアクセス要求を満足するかどうかを確認するために、キャッシュメモリが、まず最初にアクセスされ、メモリアクセス要求を満足しなければ、メインメモリが、アクセスされる。キャッシュメモリアクセスオペレーションにおいては、セットアソシエイティブキャッシュが、ロード／ストアユニットによって、アクセスされ、そのロード／ストアユニットは、メモリアクセスアドレスに存在するデータを求めてデータキャッシュを探索する。キャッシュウェイ予測アレイは、データブロックがデータアレイ内に存在する可能性のもっとも高いキャッシュウェイへのインデックスを記憶したメモリである。キャッシュウェイ予測アレイは、典型的には、それぞれのエントリー内のいくつかのビットを記憶し、それぞれのエントリーは、メモリアクセスアドレスに関して、どのキャッシュウェイがもっとも最近に使用されたか（ＭＲＵ）を指示する。キャッシュウェイ予測アレイの行は、メモリアクセスアドレスにお互いに関連づけられる。潜在的なキャッシュウェイは、タグを比較する前にアクセスされるので、キャッシュウェイ予測アレイを提供することは、潜在的に処理時間を減少させる。キャッシュアクセスが、実行されるとき、データが潜在的に存在するかもしれないキャッシュウェイにアクセスするために、キャッシュウェイ予測アレイが、使用され、そのために、正しいキャッシュウェイ予測が達成されると、メモリアクセス時間を減少させる。当然ながら、これは、シーケンシャルタグ参照に続いてデータ構造参照がなされる場合のことである。タグおよびデータ構造に同時にアクセスするアプローチは、キャッシュウェイ予測に基づいたアプローチと同じアクセス時間を有する。キャッシュウェイ予測を用いる利点は、予測されたただ１つのキャッシュウェイしかデータアレイからアクセスされないことにある。したがって、消費電力を減少させることができ、かつ、ＳＲＡＭメモリ回路のより最適な物理的レイアウトを可能にする。
【０００８】
キャッシュウェイ予測の後、データアレイにおいては、予測ビットによって表現されるキャッシュウェイが、イネーブル状態にされるが、タグアレイにおいては、すべてのキャッシュウェイが、イネーブル状態にされる。データアレイにおいてただ１つのキャッシュウェイをイネーブル状態にすることは、消費電力を減少させる。後に、タグアレイから取り出されたタグアドレスを用いて、予測が正しいかどうか検査されるので、すべてのタグアレイウェイが、イネーブル状態にされる。典型的には、タグアドレスは、ビットサイズが、データアレイ内のエントリーから取り出されたデータよりも小さい。その結果として、タグアレイにおいてすべてのキャッシュウェイがイネーブル状態にされても、消費電力はそれほど問題にはならない。少ない消費電力は、とりわけ、サイクルごとに多くの命令情報が取り出されるマルチイシュースーパースケーラプロセッサまたは超長命令語（ＶＬＩＷ）プロセッサにおいて有益である。当然ながら、当業者には、これが命令キャッシュだけにあてはまり、データキャッシュにはあてはまらないことがわかるはずであり、これに関しては、以下で説明する。メモリアクセスアドレスと一致するかどうかを判定するために、タグアレイ内のタグアドレスが、検査される。キャッシュウェイ予測の精度に関するフィードバックを提供するために、タグ比較論理回路が、使用され、キャッシュが「ヒット」したかまたは「ミス」したかを検査するために、タグ比較が、実行される。一致したことがわかれば、アクセスは、キャッシュヒットであると判定され、キャッシュメモリは、データアレイから関連するデータバイトを提供する。一致しないことがわかれば、アクセスは、キャッシュミスであると判定される。キャッシュミスが、発生すると、プロセッサは、空回りサイクル（ｓｔａｌｌ  ｃｙｃｌｅ）に直面する。空回りサイクル中、ロード／ストアユニットは、要求されたデータをメインメモリから取り出し、このデータをプロセッサに提供し、それによって、プロセッサは、それが命令ストリームを実行するのを再開することができ、空回りサイクルを終了する。さらに、ロード／ストアユニットは、要求されたデータバイトをメインメモリからデータアレイ内へ転送する。さらに、取り出されたデータバイトに関連するメモリアクセスアドレスの一部分が、タグアレイ内に記憶される。最後に、キャッシュウェイ予測アレイが、更新され、メインメモリからデータバイトが転送されたキャッシュウェイを表現する。キャッシュウェイ予測アレイに関連したタグ比較論理回路を有することは、より大きなキャッシュヒット率を提供するキャッシュメモリを提供する。
【０００９】
キャッシュウェイ予測は、当業者にはよく知られており、その例は、発明の名称が「Ｓｕｐｅｒｓｃａｌａｒ  ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ  ｅｍｐｌｏｙｉｎｇ  ａｗａｙ  ［ｓｉｃ］  ｐｒｅｄｉｃｔｉｏｎ  ｓｔｒｕｃｔｕｒｅ（アウェイ［ｓｉｃ］予測構造を用いたスーパースケーラマイクロプロセッサ）」である従来技術の米国特許第５，７５２，０６９号に開示されている。ｎ−キャッシュウェイセットアソシエイティブキャッシュメモリにおいて、メモリアクセスアドレスに基づいて、要求されたキャッシュエレメントは、キャッシュメモリ内のいずれかのｎ−キャッシュウェイ内に存在するかまたはいずれのｎ−キャッシュウェイ内にも存在しない。
【００１０】
キャッシュウェイ予測に頼り、要求されたエレメントが存在しそうなキャッシュウェイを識別することによって、すべてのキャッシュウェイにアクセスするのではなく、識別されたキャッシュウェイにのみアクセスすることができ、それによって、消費電力を有利に減少させる。そのような方法においては、その後にプロセッサによって使用されるキャッシュラインまたはキャッシュワードを構成するために、データバイトは、選択されたキャッシュウェイから転送される。したがって、キャッシュウェイ予測は、消費電力を減少させるだけでなく、キャッシュメモリ内に含まれるデータへの改善されたアクセス時間をも提供する。誤った予測は、残念ながら、プロセッサの空回りサイクルを発生させ、それによって、プロセッサの性能を低下させ、消費電力を増大させる。幸いながら、キャッシュウェイ予測は、典型的には、少なくとも９０％が正しく、これは、９０％の潜在的な場合における最小待ち状態オペレーションを可能にすることによって、一般的には、システムの性能を改善する。
【００１１】
命令キャッシュの場合、キャッシュメモリの予測精度は、残念ながら、非シーケンシャル命令がプログラムストリーム内に付加されるにつれて減少する。非シーケンシャル命令は、ＣＰＵが、従来技術によるキャッシュウェイ予測アレイ技法を用いて予測することが難しいメモリロケーションにアクセスすることをもたらす。場合によっては、非シーケンシャル命令は、プログラムが、プログラムストリーム内の先立つ命令の結果に依存したメモリロケーションへブランチすることをもたらし、そのために、これらのブランチのステップサイズは、プログラムストリームが実行されるときに変化するかもしれない。したがって、非シーケンシャルプログラムを実行する場合の予測精度は、低下し、その結果として、より多くのキャッシュミスが、発生する。これは、プロセッサの空回りサイクルを増加させ、それによって、非効率的なプログラムストリームの実行をもたらし、消費電力を増大させる。シーケンシャル命令の場合、先読みプログラムカウンタが、使用され、予測メモリにアクセスする。残念ながら、プログラムストリーム内のブランチ命令を実行するとき、先読みプログラムカウンタは、キャッシュウェイ予測に使用することはできない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
命令キャッシュにおいて使用するためのより効率的なキャッシュウェイ予測方式を提供する必要があり、その方式は、消費電力を減少させ、かつ、非シーケンシャルプログラムを実行する場合にキャッシュウェイ予測を改善するものである。
【課題を解決するための手段】
【００１３】
本発明によれば、プロセッサによって実行されるプログラムストリーム内に含まれる（シーケンシャルおよび非シーケンシャル）命令を記憶しかつ取り出すのに使用されるキャッシュメモリが、提供され、このキャッシュメモリは、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたタグアレイであり、複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、タグアドレスを記憶する、前記タグアレイと、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたデータアレイであり、複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、命令を表現するデータバイトを記憶する、前記データアレイと、
複数の行として配置された複数の記憶ロケーションを有する第１のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第１のセットを記憶する、前記第１のキャッシュウェイ予測アレイと、
複数の行として配置された複数の記憶ロケーションを有する第２のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第２のセットを記憶する、前記第２のキャッシュウェイ予測アレイと、
プログラムストリームから命令を受信する判定回路であり、判定回路が、命令がシーケンシャル型命令および非シーケンシャル型命令のいずれであるかを判定し、それに基づいて、第１のキャッシュウェイ予測アレイおよび第２のキャッシュウェイ予測アレイの一方を個々にイネーブル状態にし、前記イネーブル状態にされた予測アレイが、要求アドレスにおいてアクセスされ、キャッシュウェイ予測ビットの第１のセットおよびキャッシュウェイ予測ビットの第２のセットの一方を個々に取り出し、取り出された予測ビットに基づいて、タグアレイおよびデータアレイ内のキャッシュウェイをイネーブル状態にし、イネーブル状態にされたキャッシュウェイ内のタグアレイおよびデータアレイからタグアドレスおよびデータバイトをそれぞれ取り出すのを容易にする、前記判定回路とを備える。
【００１４】
本発明の１つの態様によれば、複数のキャッシュ予測アレイの中から１つのキャッシュ予測アレイをイネーブル状態にする方法が、提供され、この方法は、
プロセッサが次に実行するために、プログラムカウンタのアドレスに存在する命令を提供するステップと、
命令が予め定められた種類の命令かどうかを判定するステップと、
命令が予め定められた種類の命令でなければ、第１のキャッシュ予測アレイをイネーブル状態にし、命令が予め定められた種類の命令であれば、第２のキャッシュ予測アレイをイネーブル状態にするステップと、を備える。
【００１５】
本発明の１つの態様によれば、プログラムストリーム内に含まれるシーケンシャル命令および非シーケンシャル命令の記憶および取り出しに使用されるキャッシュメモリが、提供され、このキャッシュメモリは、
データの第１のセットのためのキャッシュウェイを予測するのに使用される第１のキャッシュウェイ予測アレイと、
データの第２のセットのためのキャッシュウェイを予測するのに使用される第２のキャッシュウェイ予測アレイと、
プログラムストリームから命令データを受信し、その命令データに基づいて、第１のキャッシュウェイ予測アレイおよび第２のキャッシュウェイ予測アレイの中から一方を選択する判定回路と、を備える。
【００１６】
本発明のさらなる態様によれば、データを記憶した記憶媒体が、提供され、データが、集積回路設計を実施するのに使用され、データが、回路エレメントを記述するデータを含み、回路エレメントが、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたタグアレイであり、複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、タグアドレスを記憶する、前記タグアレイと、
複数の行の１つと複数のキャッシュウェイの１つとのそれぞれの交点に配置された複数の記憶ロケーションを有する前記複数の行および前記複数のキャッシュウェイとして配置されたデータアレイであり、複数の記憶ロケーションからの前記記憶ロケーションのそれぞれが、命令に関係するデータバイトを記憶する、前記データアレイと、
複数の行として配置された複数の記憶ロケーションを有する第１のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第１のセットを記憶する、前記第１のキャッシュウェイ予測アレイと、
複数の行として配置された複数の記憶ロケーションを有する第２のキャッシュウェイ予測アレイであり、複数の記憶ロケーションからの記憶ロケーションのそれぞれが、キャッシュウェイ予測ビットの第２のセットを記憶する、前記第２のキャッシュウェイ予測アレイと、
プログラムストリームから命令を受信する判定回路であり、判定回路が、命令がシーケンシャル型命令および非シーケンシャル型命令のいずれであるかを判定し、それに基づいて、第１のキャッシュウェイ予測アレイおよび第２のキャッシュウェイ予測アレイの一方を個々にイネーブル状態にし、前記イネーブル状態にされた予測アレイが、要求アドレスにおいてアクセスされ、キャッシュウェイ予測ビットの第１のセットおよびキャッシュウェイ予測ビットの第２のセットの一方を個々に取り出し、取り出された予測ビットに基づいて、タグアレイおよびデータアレイ内のキャッシュウェイをイネーブル状態にし、イネーブル状態にされたキャッシュウェイ内のタグアレイおよびデータアレイからタグアドレスおよびデータバイトをそれぞれ取り出すのを容易にする、前記判定回路と、を含む。
【００１７】
ここで、図面を参照して本発明を説明する。
【発明を実施するための最良の形態】
【００１８】
図１は、Ｒｏｂｅｒｔｓらに発行された発明の名称が「Ｓｕｐｅｒｓｃａｌａｒ  ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ  ｅｍｐｌｏｙｉｎｇ  ａｗａｙ  ［ｓｉｃ］  ｐｒｅｄｉｃｔｉｏｎ  ｓｔｒｕｃｔｕｒｅ（アウェイ［ｓｉｃ］予測構造を用いたスーパースケーラマイクロプロセッサ）」である米国特許第５，７５２，０６９号による従来技術のキャッシュアーキテクチャ２２４を示す。Ｒｏｂｅｒｔｓらによって開示された内容を考察することは、本発明を理解するのに都合がよいことかもしれない。従来技術に関する以下の記述は、データキャッシュに関して、キャッシュウェイ予測構造を説明するものであるが、類似する構造が、命令キャッシュにも同様に試みられることに注意されたい。
【００１９】
従来技術によるキャッシュアーキテクチャ２２４は、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３を備え、これらのアレイのそれぞれは、Ｎ−キャッシュウェイセットアソシエイティブである。出力ポートが、キャッシュデータアレイ２５３上に提供され、データバイトをキャッシュデータアレイ２５３から一組のキャッシュウェイデータバス２５５Ａ〜２５５Ｎ（まとめてキャッシュウェイデータバス２５５と呼ばれる）に提供する。そのために、クロックサイクルごとに、Ｎ個のデータバイトが、キャッシュデータアレイ２５３の出力ポートからキャッシュウェイデータバス２５５に提供される。
【００２０】
キャッシュウェイデータバス２５５は、Ｎ対１のキャッシュウェイ選択ブロック２５６に結合される。キャッシュウェイ選択ブロック２５６は、典型的には、複数のマルチプレクサからなり、それぞれのマルチプレクサは、キャッシュウェイデータバス２５５に結合され、また、キャッシュウェイ予測アレイ２５１からのキャッシュウェイ予測バス２５７に結合される。キャッシュウェイデータバス２５５のそれぞれは、ロード／ストアユニット（図示しない）からアドレス要求バス２５０上に提供された要求アドレスに基づいて、キャッシュウェイ予測アレイ２５１を用いて特定のキャッシュウェイがインデックスされたとき、その特定のキャッシュウェイからデータバイトを伝達する。セパレートキャッシュウェイ予測が、アドレス要求バス上の要求アドレスごとに実行され、要求アドレスごとに、キャッシュウェイ予測アレイ２５１が、キャッシュウェイ予測バス２５７を用いて、Ｎ対１のキャッシュウェイ選択ブロック２５６の中から１つのマルチプレクサをイネーブル状態にし、データキャッシュ２２４のＮ個のキャッシュウェイの中の１つを選択し、要求されたデータバイトをキャッシュデータアレイ２５３からＮ対１のキャッシュウェイ選択ブロック２５６上の出力ポートに結合されたデータバス２５８に提供する。要求アドレスごとの予測されたキャッシュウェイに関連するデータバイトは、データバス２５８上に伝達され、プロセッサ（図示しない）によって使用するために、ロード／ストアユニット（図示しない）に伝達される。
【００２１】
キャッシュウェイ予測アレイ２５１は、データアレイおよびタグアレイ内のキャッシュウェイを予測するときに使用するためのキャッシュウェイ予測ビットを記憶するように構成される。キャッシュウェイ予測アレイ２５１内に記憶された予測ビット‘ｎ’の値は、キャッシュウェイ２ｎの値に関係する。したがって、８−キャッシュウェイセットアソシエイティブキャッシュの場合、３ビットが、記憶され、４−キャッシュウェイセットアソシエイティブキャッシュの場合、２ビットしか記憶されない。例えば、８キャッシュウェイセットアソシエイティブキャッシュを使用する場合、８が、キャッシュのアソシアティビティであり、２３＝８であるので、予測メモリの幅は、３ビットである。予測アレイ内の深さすなわち行の数は、典型的には、２の累乗であり、所定のキャッシュウェイ予測精度を実現するために、調整することができる。３２ビットの要求アドレスＡ［３１：０］、２６＝６４バイトのキャッシュラインサイズ、および、予測メモリ内の２８個のエントリーを使用すれば、ビットＡ［１３：６］が、キャッシュウェイ予測アレイ２５１をインデックスするのに使用され、ここで、ビット１３からビット６までは、８個のロケーションビットであり、キャッシュウェイ予測アレイ２５１の深さを表現する。深さが深くなればなるほど、予測アレイは、異なる要求アドレスを区別する場合に、より好ましいものとなる。例えば、２つの異なる要求アドレスが、ビットロケーション１４において異なるだけであり、かつ、８個のロケーションビットが、予測アレイにアクセスするのに使用されるならば、同じキャッシュウェイが、２つの異なるアドレスに対して予測されるので、アドレスエイリアシングが、発生する。この同一のキャッシュウェイ予測は、ほとんどの場合、正しくないと考えられる。したがって、予測アレイの深さが、増加すれば、メモリ容量サイズを倍増するのを犠牲にして、アドレスエイリアシングは、減少し、それによって、予測精度を改善することができる。
【００２２】
キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３は、キャッシュウェイの数およびキャッシュセットの数に関して、同じように構成される。当然ながら、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３の特定のセットのための１つよりも多いキャッシュウェイ予測が、キャッシュウェイ予測アレイ２５１内に記憶されてもよい。例えば、キャッシュウェイ予測アレイ２５１が、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３の２倍のキャッシュセットを備えて構成されるならば、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３のセットごとに、２つのキャッシュウェイ予測が、キャッシュウェイ予測アレイ２５１内に記憶される。この場合、キャッシュウェイ予測アレイ２５１をインデックスするのに使用される要求アドレスからのビットの数は、典型的には、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３をインデックスするのに使用されるビットの数よりも１つだけ多い。この場合の余分な１ビットは、その要求アドレスのためのキャッシュウェイ予測として、記憶された２つのキャッシュウェイ予測のどちらが選択されるかを決定するものである。典型的には、与えられた要求アドレスのための正しいキャッシュウェイ予測を記憶する可能性は、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３のインデックスされたセットのために記憶されたキャッシュウェイ予測の数によって、増大する。したがって、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３のセットごとに１つよりも多いキャッシュウェイ予測アレイを有するキャッシュウェイ予測アレイを使用することによって、性能を増大させることができる。典型的には、キャッシュウェイ予測アレイ２５１は、行内に記憶された５１２個のキャッシュウェイ予測エントリーからなる線形アレイであり、上述したように、それぞれのキャッシュウェイ予測は、デコードされた値である。典型的には、キャッシュウェイ予測アレイ２５１は、セットの数にデータキャッシュアレイ２５３内のキャッシュウェイの数を乗じた数に等しいいくつかのキャッシュウェイ予測記憶ロケーションを備えた線形アレイである。
【００２３】
要求アドレスは、キャッシュタグアレイ２５２およびキャッシュデータアレイ２５３をインデックスするのに使用されるとともに、キャッシュウェイ予測アレイ２５１をインデックスするのにも使用される。キャッシュウェイ予測アレイ２５１は、インデックスされたキャッシュウェイ予測をキャッシュウェイ予測バス２５７上に伝達し、予測されたキャッシュウェイに関連するデータバイトをデータバス２５８上に伝達する。したがって、データキャッシュ２２４にアクセスを開始してからデータキャッシュ２２４によってデータが提供されるまでの時間遅延は、キャッシュウェイ予測アレイ２５１によって発生する時間遅延と、それに続いて、予測されたキャッシュウェイを用いて出力バイトを選択するために、出力ポートをイネーブル状態にすることに関連する小さな遅延とによって表現される。
【００２４】
さらに、キャッシュウェイ予測バス２５７は、タグ比較ブロック２５９にも結合される。タグ比較ブロック２５９は、要求アドレスが、予測されたキャッシュウェイを用いて、キャッシュヒットをもたらしたかどうか、別のキャッシュウェイを用いて、キャッシュヒットをもたらしたかどうか、あるいは、予測されたキャッシュウェイを用いて、キャッシュミスをもたらしたかどうかを判定するように構成された論理回路を備える。タグ比較ブロック２５９は、キャッシュウェイデータバス２５５に類似する一組のキャッシュウェイタグバス２６４Ａ〜２６４Ｎによって提供されるインデックスされたタグを要求アドレスと比較し、タグ比較からの実際のヒットキャッシュウェイが、キャッシュウェイ予測アレイ２５１からの予測されたキャッシュウェイと一致するかどうかを判定する。キャッシュタグアレイ２５２へのアクセスおよびそれに続くタグ比較は、与えられたクロックサイクル内で完了しなくてもよいので、タグ比較ブロック２５９は、関連するアドレスがデータキャッシュ２２４にアクセスするクロックサイクルの次のクロックサイクルの初期に信号を生成する。
【００２５】
予測されたキャッシュウェイにおけるヒットが、ロード要求に対して検出されると、信号が、ヒット予測キャッシュウェイバス２６０上にアサートされる。ヒット予測キャッシュウェイバス２６０は、タグ比較ブロック２５９とロード／ストアユニット（図示しない）および予約ステーション（図示しない）との間に結合される。それぞれの実現可能な要求アドレスに関連する信号は、ヒット予測キャッシュウェイバス２６０上に伝達され、ロード／ストアユニット２２２および予約ステーション２１０の両方は、それぞれの信号を、以前のクロックサイクルからの適切なアドレス要求に対応づけるように構成される。予測されたキャッシュウェイにおけるヒットは、以前のクロックサイクルにおいてデータバス２５８上に伝達されたデータが正しいことを指示する。そして、予約ステーションは、現在のクロックサイクルにおいて受信され実行されるあらゆる命令およびデータを廃棄してもよく、また、ロード／ストアユニットは、要求されたアドレスに関連するロード命令を廃棄してもよい。
【００２６】
非予測キャッシュウェイにおけるヒットが、ロード要求に対して検出されると、対応する信号が、ロード／ストアユニットおよび予約ステーションに結合されたヒット非予測キャッシュウェイバス２６１上にアサートされる。非予測キャッシュウェイにおけるヒットは、非予測キャッシュウェイヒットアドレスが以前のクロックサイクルにおいて伝達された要求アドレスバス２５０の一部分上に伝達された要求アドレスをロード／ストアユニットにキャンセルさせる。データキャッシュ２２４は、正しいデータをデータバス２５８上に伝達するのにアイドルポートを使用する。キャッシュウェイ予測は、修正され、そして、修正されたデータが、データバス２５８上に伝達される。キャッシュウェイ予測は、キャッシュウェイ予測制御ユニット２６５を介して修正される。キャッシュウェイ予測制御ユニット２６５は、ヒットキャッシュウェイバス２６３およびヒット非予測キャッシュウェイバス２６１上において、信号を受信する。非予測キャッシュウェイ信号におけるヒットが、アサートされると、ヒットが発生したキャッシュウェイは、ヒットキャッシュウェイバス２６３上に伝達される。キャッシュウェイ予測制御ユニット２６５は、ヒットしたキャッシュウェイを、キャッシュウェイ予測アレイ２５１上の書き込みポートに伝達し、以前のクロックサイクルからデータキャッシュ２２４によって記憶された関連アドレスによってインデックスされたロケーションにその値を書き込むようにキャッシュウェイ予測アレイ２５１に通知する。したがって、非予測キャッシュウェイにおけるヒットは、１つのクロックサイクルだけにペナルティが課される。さらに、予約ステーション２１０は、非予測キャッシュウェイにおけるヒットを検出し、関連するアドレスに関して以前のクロックサイクルにおいて転送されたデータを無効にする。正しくないデータをオペランドとして受信した命令が、この時点において、それぞれの機能ユニットによって実行されるならば、予約ステーションは、その他の予約ステーションに信号をアサートし、正しくないデータを指示するバッファーをリオーダーし、それによって、その他の予約ステーションおよびリオーダーバッファーは、正しくないデータによって命令を実行することから得られるあらゆる結果を無視する。
【００２７】
ミスが、検出されると、対応する信号が、ロード／ストアユニットおよび予約ステーションに結合されたミスバス２６２上にアサートされる。ロード／ストアユニットは、後にミスを処理するために、そのミスを記録し、そして、予約ステーションは、上述した非予測キャッシュウェイにおいてヒットした場合に類似する処理を実行する。キャッシュミスに対する正しい予測キャッシュウェイが、存在しないので、キャッシュウェイ予測アレイ２５１は、この場合には、変更されない。
【００２８】
キャッシュアーキテクチャ２２４は、典型的には、プログラムカウンタ（ＰＣ）を用いてアクセスされる。ＰＣは、プログラムストリーム内で実行される命令をインデックスするために、プロセッサによってインデックスとして使用される。プログラムストリーム内の命令が、アクセスされるとき、ＰＣは、キャッシュアーキテクチャ２２４にアクセスするための要求アドレスの役割をなす。シーケンシャルプログラムフローにおいては、プログラム内の命令は、プロセッサにＰＣを非シーケンシャルに変化させない命令にプロセッサがオペレーションを実行することをもたらす性質を有する。例えば、ジャンプ命令は、シーケンシャル命令とは異なり、それらのジャンプ命令は、ＰＣをプログラムストリームの別の部分へジャンプさせる。シーケンシャル命令の場合、ＰＣは、既知のステップだけ変化するので、キャッシュウェイ予測アレイをインデックスするために、要求アドレスは、ＰＣから容易に得ることができる。
【００２９】
残念ながら、上述した従来技術によるキャッシュウェイ予測方式の欠点の１つは、ジャンプ命令を含めてブランチ命令のような、ＰＣを非シーケンシャルに変化させる命令を処理するときのそれの効率にある。データアレイおよびタグアレイに先立ってキャッシュウェイ予測アレイにアクセスすることは、キャッシュウェイ予測アレイ２５１を利用できるようにするために、プロセッサパイプライン内に含まれるプログラムストリーム内の要求アドレスをより早く得ることができなければならない。シーケンシャルにプログラムを実行する場合、これは、処理時間の点においては大きな問題とはならない。しかしながら、ジャンプ命令のような非シーケンシャル命令が、プログラムストリーム内に存在する場合、ブランチロケーションに存在する命令を実行できるように、それらの非シーケンシャル命令は、プロセッサのＰＣに非シーケンシャルターゲットＰＣを提供することによって、このシーケンシャルプログラムストリームフローを中断する。
【００３０】
ブランチ命令という用語は、命令データストリーム内の命令コードを非シーケンシャルに実行するのを可能にする命令を意味するのに使用される。ここで使用されるジャンプ命令という用語は、現在のＰＣが指示するロケーションから少なくとも予め定められた距離にある命令データ内のロケーションにブランチするためのブランチ命令を意味する。
【００３１】
典型的には、超長命令語（ＶＬＩＷ）プロセッサのためにコンパイルされたプログラムストリームにおいては、複数の個々の命令が、ＶＬＩＷ命令内にグループ化され、ジャンプ命令が、プログラムストリーム内に頻繁に現れる。その結果として、性能低下が、これらのプロセッサシステムにおいて発生する。なぜなら、非シーケンシャルジャンプ命令が現れる頻度は、きわめて高いからである。キャッシュは、非シーケンシャル命令を適切に処理するようには設計されていないので、頻繁に現れるこの命令は、キャッシュミスを発生させる。非シーケンシャル命令のための正確なキャッシュウェイ予測は、従来技術を用いて十分に適切に実施することはできない。誤った予測は、命令フェッチパスに過度の遅延を発生させ、潜在的なプロセッサ性能低下をもたらす。
【００３２】
したがって、従来技術の欠点を克服するために、セパレートキャッシュウェイ予測アレイによってジャンプターゲットの命令キャッシュウェイ予測を実行するためのプロセスが、本発明の実施形態に基づいて開示される。図２ａは、非シーケンシャルジャンプターゲットとともに使用するためのキャッシュアーキテクチャ２０４を示す。この場合のキャッシュアーキテクチャ２０４は、付加的なキャッシュウェイ予測アレイ２７１を備え、それによって、２つのキャッシュウェイ予測アレイ、すなわち、非シーケンシャルキャッシュウェイ予測アレイ２７１およびシーケンシャルキャッシュウェイ予測アレイ２５１を有するキャッシュアーキテクチャ２０４を提供する。この場合のシーケンシャルキャッシュウェイ予測アレイ２５１は、従来技術である図１に示されるものと同じキャッシュウェイ予測アレイである。
【００３３】
非シーケンシャルキャッシュウェイ予測アレイ２７１は、プログラムストリーム内におけるプロセッサによって実行される非シーケンシャル命令をキャッシュするためのキャッシュウェイ予測ビットを記憶するように構成される。非シーケンシャルキャッシュウェイ予測アレイ２７１は、非シーケンシャル命令のＰＣを用いてインデックスされる。非シーケンシャルキャッシュウェイ予測アレイ２７１内に記憶された予測ビットの更新は、シーケンシャルキャッシュウェイ予測アレイ２５１に関する更新と同じようにして実行される。同様に、非シーケンシャルキャッシュウェイ予測アレイ２７１は、キャッシュウェイ予測バス２５７に結合され、キャッシュウェイ予測のために、Ｎ個のキャッシュウェイの中の１つをインデックスする。非シーケンシャルキャッシュウェイ予測アレイ２７１を用いたキャッシュウェイ予測および誤った予測のときの更新は、シーケンシャルキャッシュウェイ予測アレイ２５１の場合と同じようにして実行される。さらに、シーケンシャルキャッシュウェイ予測アレイを使用するかまたは非シーケンシャルキャッシュウェイ予測アレイを使用するかを判定するために、判定回路２９８が、キャッシュ２０４内に提供される。判定回路２９８は、アドレス要求バスを用いて、要求アドレスを受信し、また、シーケンシャルキャッシュウェイ予測アレイまたは非シーケンシャルキャッシュウェイ予測アレイの一方をイネーブル状態にするために、判定信号をプロセッサから受信する。
【００３４】
図２ｂは、非シーケンシャルキャッシュウェイ予測アレイ２７１にアクセスするためになされるステップを概略的に示す。非シーケンシャルキャッシュウェイ予測アレイは、ステップ２００１において、プロセッサが次に実行するために、プログラムカウンタのアドレスにおける命令を読み込むことによって、イネーブル状態にされる。符号２００２において、命令が予め定められた種類の命令かどうかを判定するステップが、実行される。命令が、予め定められた種類の命令でなければ、ステップ２００３において、シーケンシャルキャッシュウェイ予測アレイが、イネーブル状態にされる。命令が、予め定められた種類の命令であれば、ステップ２００４において、非シーケンシャルキャッシュウェイ予測アレイが、イネーブル状態にされる。典型的には、予め定められた種類の命令は、ここで説明したように、コードが非シーケンシャルに実行されることをもたらす命令である。
【００３５】
図３は、プロセッサのＰＣに関連づけられたプログラムストリーム内に含まれるいくつかのプログラム命令を示す。プログラムストリームは、２つの部分に分割され、第１の部分３００において、命令は、シーケンシャルフローをたどり、第２の部分３０１においては、命令は、非シーケンシャルフローをたどる。プログラムストリーム内の命令を実行するとき、非シーケンシャルキャッシュウェイ予測アレイ２７１は、ジャンプ命令の形態を有するブランチ命令のような非シーケンシャル命令を用いてアクセスされ、そして、シーケンシャルキャッシュウェイ予測アレイ２５１は、シーケンシャル命令を用いてアクセスされる。非シーケンシャルキャッシュウェイ予測アレイ２７１に提供される要求アドレスは、非シーケンシャルブランチ命令を含むＰＣのアドレスであり、ブランチ命令によってターゲットされたＰＣのアドレスではない。この前者の情報は、命令をデコードまたは実行するときのターゲットジャンプ命令のＰＣよりもきわめて早く、命令をフェッチするときにプロセッサパイプラインにおいて得ることができる。このオペレーションは、例によって、以下で説明される。
【００３６】
図３を参照すると、使用中、プロセッサは、プログラムストリームの実行をＰＣ１において開始する。キャッシュメモリ２０４にアクセスする場合、要求アドレスは、ＰＣのアドレスである。ＰＣ１においては、ＰＣ１が、シーケンシャルキャッシュウェイ予測アレイにアクセスするための要求アドレスとして使用される。キャッシュヒットであれば、キャッシュによって、‘命令１’が、プロセッサに提供される。‘命令１’を処理した後、ＰＣは、ＰＣ２にインクリメントされる。ＰＣ２の場合、要求アドレスは、ＰＣ１から予め計算されるか、または、ＰＣ２が、シーケンシャルキャッシュウェイ予測アレイにアクセスするのに使用される。‘命令２’を処理した後、ＰＣは、ＰＣ３にインクリメントされる。ＰＣ３の場合、要求アドレスは、ＰＣ１またはＰＣ２から予め計算されるか、または、ＰＣ３が、シーケンシャルキャッシュウェイ予測アレイにアクセスするのに使用される。ＰＣ３に配置された命令が、処理されてしまえば、ＰＣは、ＰＣ４にインクリメントされる。ＰＣ４の場合、要求アドレスは、ＰＣ１またはＰＣ２またはＰＣ３から予め計算されるか、または、ＰＣ４が、シーケンシャルキャッシュウェイ予測アレイにアクセスするのに使用される。以前の命令は、本質的に、シーケンシャル命令であるので、要求アドレスは、ＰＣから容易に決定される。ＰＣ４には、非シーケンシャル命令が、ジャンプ命令の形態で存在する。この直接ジャンプ命令が、実行されると、ＰＣをＰＣ１６に設定する責任がある。主として、２つの異なる種類のジャンプ命令が、存在し、それらは、直接ジャンプ命令および間接ジャンプ命令である。直接ジャンプ命令は、プログラムの実行によって変化することのない一定のジャンプサイズを有する。他方において、間接ジャンプ命令は、可変のジャンプサイズを有し、ジャンプ命令によってターゲットされるＰＣは、プログラムを実行しているときに動的に変化する。その結果として、間接ジャンプ命令がＰＣを再設定すべきロケーションは、予測するのが難しい。
【００３７】
ＰＣ４において、キャッシュメモリまたはメインメモリから命令を取り出した後、判定回路は、非シーケンシャルキャッシュウェイ予測アレイをイネーブル状態にし、かつ、シーケンシャルキャッシュウェイ予測アレイをディスエーブル状態にする。このようにして、ＰＣ４においてジャンプ命令を実行した後、ＰＣは、ＰＣ１６に設定される。ＰＣ１６においては、ＰＣ４におけるジャンプ命令のために、非シーケンシャルＰＣにジャンプするので、以前のどのアドレスからも要求アドレスを予め計算することはできない。その結果として、非シーケンシャルキャッシュウェイ予測アレイにアクセスしてキャッシュ２０４から‘命令１６’を取り出すために、ＰＣ４が、要求アドレスとして使用される。‘命令１６’を処理した後、ＰＣは、ＰＣ１７にインクリメントされる。ＰＣ１６における命令は、ジャンプ型命令ではないので、判定回路は、非シーケンシャルキャッシュウェイ予測アレイをディスエーブル状態にし、かつ、シーケンシャルキャッシュウェイ予測アレイをイネーブル状態にする。その結果として、ＰＣ１７においては、要求アドレスは、ＰＣ１６から予め計算されるか、または、ＰＣ１７が、要求アドレスとして使用されるかのいずれかである。
【００３８】
有利には、非シーケンシャルキャッシュウェイ予測アレイを使用することによって、ＰＣ４は、２つの異なる予測アレイのために、同じ要求アドレスの役割をなす。ＰＣ４においては、以前のシーケンシャルＰＣまたはＰＣ４から得られた要求アドレスを用いて、シーケンシャル予測アレイが、アクセスされ、そして、ＰＣ１６においては、ＰＣ４から得られた要求アドレスを用いて、非シーケンシャル予測アレイが、アクセスされる。２つの異なる予測アレイがなければ、キャッシュミスの率は、きわめて高い。なぜなら、要求アドレスの決定は、非シーケンシャルプログラムストリームが実行されることによって、容易なことではないからである。２つの異なる予測アレイを有することは、キャッシュミスに応じて、同じ予測アレイが同じアドレスに異なるデータバイトを上書きされることを排除する。
【００３９】
有利には、提案された方法は、直接ジャンプ命令である命令を備えたキャッシュウェイ予測において使用されると、高い予測精度を達成する。間接ジャンプ命令の場合、予測精度は、ターゲットされたＰＣを変更する周波数に依存する。
【００４０】
当然ながら、シーケンシャル予測アレイおよび非シーケンシャル予測アレイが、同じサイズでなければならない理由は何もない。例えば、プログラムストリームにおいてより多くの非シーケンシャル命令を実行する傾向のあるプロセッサの場合、シーケンシャル予測アレイよりも多い行を非シーケンシャル予測アレイに含めることは、好ましいことかもしれない。このように、非シーケンシャル予測アレイが、より多く使用されるので、より小さいサイズのシーケンシャル予測アレイを有することは、メモリコストを減少させる。当然ながら、プログラムストリームが、より多くのシーケンシャル命令を含むのであれば、より大きなシーケンシャル予測アレイを提供することが有利であることがわかる。
【００４１】
有利には、要求されたエレメントが存在しそうなキャッシュウェイを識別するための予測に頼ることによって、すべてのキャッシュウェイにアクセスするのではなく、識別されたキャッシュウェイだけにアクセスするだけで取り出すことができる。アクセスされるキャッシュウェイの数を１つに制限することによって、電力を減少させることができる。その他のキャッシュウェイまたはメインメモリにアクセスしなければならないことは、きわめてより多くの電力を消費し、したがって、正確なキャッシュウェイ予測は、消費電力が少ない解決方法を提供する。ポータブルコンピュータのような携帯型用途の場合、少ない消費電力が、優先される。当業者には、より多くのプロセッサのエネルギーが、キャッシュミスを解決する際に浪費されることがわかる。
【００４２】
さらに有利には、大きなキャッシュヒット率は、ほとんどの場合に、データアレイにおいてただ１つのキャッシュウェイだけをイネーブル状態にすればよいことを促進し、したがって、典型的には、もはやデータアレイのすべてのウェイに同時にアクセスしなくてもよく、それによって、消費電力を減少させる。これは、物理的なＳＲＡＭ回路において論理キャッシュウェイの様々な編成を使用することを容易にする。
【００４３】
本発明の精神および範囲を逸脱することなく、多くのその他の実施形態を考え出すことができる。
【図面の簡単な説明】
【００４４】
【図１】米国特許第５，７５２，０６９号による従来技術のキャッシュアーキテクチャを示す。
【図２ａ】本発明の実施形態によるキャッシュアーキテクチャを示す。
【図２ｂ】本発明の実施形態によるキャッシュアーキテクチャの動作ステップを示す。
【図３】プロセッサによって実行されるプログラムストリームを示し、シーケンシャル命令および非シーケンシャル命令を有する。
【符号の説明】
【００４５】
２２４  キャッシュアーキテクチャ
２５０  アドレス要求バス
２５１  キャッシュウェイ予測アレイ
２５２  キャッシュタグアレイ
２５３  キャッシュデータアレイ
２５５Ａ〜２５５Ｎ  キャッシュウェイデータバス
２５６  キャッシュウェイ選択ブロック
２５７  キャッシュウェイデータバス
２５８  データバス
２５９  タグ比較ブロック
２６０  ヒット予測キャッシュウェイバス
２６１  ヒット非予測キャッシュウェイバス
２６３  ヒットキャッシュウェイバス
２６５  キャッシュウェイ予測制御ユニット
２７１  非シーケンシャルキャッシュウェイ予測アレイ
２９８  判定回路
【図１】
2005535955.tif 000003
【図２ａ】
2005535955.tif 000004
【図２ｂ】
2005535955.tif 000005
【図３】
2005535955.tif 000006
【国際調査報告】
2005535955.tif 000007
2005535955.tif 000008
2005535955.tif 000009