(57)【特許請求の範囲】
【請求項１】
キャッシュブロックのリプレースアルゴリズムにＬＲＵを使用したセットアソシアティブ方式のキャッシュ記憶装置を備えるプロセッサにおいて、
前記キャッシュ記憶装置は、プリフェッチ命令でフェッチしたデータを格納するウェイを制限する回路と、同一セットをアクセスする実行中のプリフェッチ命令の数により、リプレースウェイの決定方法を変更する回路を備え、
前記リプレースウェイの決定方法を変更する回路は、前記同一セットをアクセスする実行中のプリフェッチ命令の数がプリフェッチ命令で使用可能なウェイ数よりも小さい場合、所定のアルゴリズムに従って決定されたウェイをプリフェッチ命令で使用可能なウェイ内で、前記プリフェッチ命令の数だけシフトすることによりリプレースウェイを決定し、前記同一セットをアクセスする実行中のプリフェッチ命令の数がプリフェッチ命令で使用可能なウェイ数以上の場合、前記所定のアルゴリズムに従って決定されたリプレースウェイを、プリフェッチ命令で使用可能なウェイに制限せず、該当セット内の全ウェイ内で前記プリフェッチ命令の数分だけシフトしてリプレースウェイを決定する、プロセッサ。
【請求項２】
前記所定のアルゴリズムとは、ＬＲＵアルゴリズムである、請求項１記載のプロセッサ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算機システムにおけるキャッシュ記憶装置に係り、特に、将来使用される可能性の高いデータのキャッシュからの追い出しを抑止することができるキャッシュ記憶装置に関する。
【０００２】
【従来の技術】
計算機システムにおいて、コンピュータプログラムの主記憶参照には局所性があることが知られている。計算機システムでは、この性質を利用して、頻繁にアクセスされる主記憶データをキャッシュ記憶装置（以下、単にキャッシュと呼ぶ）と呼ばれる高速で小容量のメモリにコピーしておき、主記憶へのアクセスをこのキャッシュに対して行うことによって、メモリアクセスを高速化することが行われている。
【０００３】
キャッシュについては、例えば、「富田眞治、村上和彰、新實治男訳“コンピュータアーキテクチャ：設計・実現・評価の定量的アプローチ”日経ＢＰ社」の４０３〜４２８頁に詳しく述べられている。
【０００４】
キャッシュと主記憶との間のデータの管理は、ブロックと呼ばれる適当な大きさを単位として行われる。ブロックの大きさは、ブロックサイズと呼ばれる。キャッシュには、複数のブロックが格納されており、例えば、キャッシュの容量（キャッシュサイズ）が１２８Ｋバイト、ブロックサイズが１２８バイトの場合、キャッシュには１０２４個のブロックが格納される。
【０００５】
キャッシュに格納されたデータは、データアレイと呼ばれるメモリに保持される。キャッシュに主記憶上のどのブロックが保持されているかを識別するため、ブロックのアドレスがアドレスアレイと呼ばれるメモリに保持される。プロセッサにより参照されるデータがキャッシュ上にあるかどうかは、アドレスアレイに保持されたアドレスと、命令により参照されるアドレスとを比較することで判定される。
【０００６】
主記憶上のブロックをキャッシュ上のどこに配置するかによって、キャッシュの構成は３つの方式に分類できる。主記憶上の各ブロックのキャッシュ上での位置が、そのアドレスによって一意に決まるような方式をダイレクトマップ方式、主記憶上の各ブロックをキャッシュ上の任意の場所に配置できる方式をフルアソシアティブ方式、主記憶上のブロックをキャッシュ上のある決められた範囲内に配置できる方式をセットアソシアティブ方式と呼ぶ。
【０００７】
フルアソシアティブ方式の場合、キャッシュ上にデータが存在するかどうかを判定するためには、命令により参照されるアドレスと、キャッシュに格納されている全てのブロックのアドレスを比較しなければならず、ハードウエア量の点から現実的ではない。このため、主記憶上の各ブロックのマッピングには、一般には、ダイレクトマップ方式とセットアソシアティブ方式のいずれかが使用されている。
【０００８】
セットアソシアティブ方式のキャッシュは、その記憶領域がＮ行Ｍ列のブロックに分割される。各ブロックにはデータとブロックのアドレスが格納される。キャッシュの各行はセット、各列はウェイと呼ばれる。
【０００９】
セットアソシアティブ方式では、主記憶からフェッチされたブロックは、そのアドレスによって一意に決まるセット上の、いずれかのウェイに格納される。該当するセット内に無効なウェイが存在すれば、そのウェイにブロックが格納されるが、全てのウェイが有効な場合は、セット内のいずれかのウェイを主記憶に追い出して、新たに主記憶からフェッチしたブロックが格納される。
【００１０】
ブロックの追い出しが発生する場合、追い出しの対象となるウェイの決定方法としては、一般にＬＲＵ（Least Recently Used）アルゴリズムが使用されている。ＬＲＵアルゴリズムでは、該当セット内で最も遠い過去に参照されたデータが格納されたウェイが、追い出しの対象とされる。
【００１１】
キャッシュ上にデータが存在すれば、主記憶をアクセスする必要がないため、メモリアクセスを高速に行うことができる。しかし、キャッシュ上にデータが存在しない場合、そのデータを使用する命令の実行は、データが主記憶からフェッチされるまで遅延される。このようなキャッシュミスによる遅延時間を短縮するために、従来からプリフェッチと呼ぶ方法が用いられている。プリフェッチとは、ロード命令を実行する前に、プリフェッチ命令と呼ぶ命令を実行し、キャッシュ上に後続のロード命令で使用するデータをあらかじめフェッチしておき、ロード命令でキャッシュヒットさせる方法である。
【００１２】
【発明が解決しようとする課題】
一般に、プログラムのメモリアクセスパターンを解析すると、次のような特徴が現れる場合が非常に多い。
【００１３】
(1) あるアドレスのデータに対するアクセスは比較的短い時間内に再発する。
【００１４】
(2) ある一定時間内にアクセスされるデータは比較的近いアドレスに分布する。
【００１５】
前者は「時間的局所性」、後者は「空間的局所性」と呼ばれる。一般に、プリフェッチ命令によってキャッシュに持ってきたデータは、空間的局所性はあるが、時間的局所性はない。またスタックデータ等のスカラデータは、空間的局所性はないが、時間的局所性はある。
【００１６】
追い出しアルゴリズムにＬＲＵを用いたセットアソシアティブ方式のキャッシュ上で、“空間的局所性はあるが、時間的局所性がない”大きな配列をアクセスすると、スタック上のデータなどの時間的局所性のあるデータがキャッシュから追い出され、キャッシュ内のデータが上記の配列によって全て上書きされるという現象が発生する。
【００１７】
このような、時間的局所性のあるブロックが、空間的局所性はあるが時間的局所性のないブロックによってキャッシュから追い出されるという問題を解決するための技術が、例えば、特開平７−２８１９５７号公報に開示されている。この技術によれば、再利用される可能性のあるデータの最初の参照でＬＲＵがロックされ、該当データの最後の参照でＬＲＵのロックが解除される。
【００１８】
しかしながら、ＬＲＵのロック方式ではプロセスが切り替わった時にＬＲＵが動作しない可能性があり、またキャッシュの使用率が低下する可能性もある。例えば、あるプロセスＡにおいて、スタックの最初の参照でＬＲＵをロックしてから、ロックを解除するまでの間にプロセスＡがプロセスＢに切り替わった場合を考える。この場合、プロセスが切り替わっても、キャッシュのＬＲＵはロックされたままなので、ロックされたカラムにおける追い出し対象のブロックは、常にＬＲＵがロックされたときに追い出し対象であったブロックとなる。このため、プロセスＢにおける該当カラムは、ダイレクトマップのキャッシュと同様の動作になり、キャッシュの使用率が著しく低下する可能性がある。
【００１９】
このように、上述した従来技術では、ＬＲＵによって性能が低下する場合がある。そして、特開平７−２８１９５７号公報に開示されるようなＬＲＵのロック方式を使用した場合にも、マルチプロセス環境においてキャッシュの使用率が低下する恐れがあるという問題がある。
【００２０】
本発明の目的は、空間的局所性はあるが、時間的局所性が無いデータの参照によって、時間的局所性のあるデータがキャッシュから追い出されることを減少させることができ、また、マルチプロセス環境においても特別な処理を行うことなくＬＲＵを正常に動作させることができるキャッシュ記憶装置を提供することである。
【００２１】
【課題を解決するための手段】
上述した目的を達成するために、本発明のキャッシュ記憶装置は、同一のセットアドレスのデータを格納可能な複数のウェイを有するセットアソシアティブ方式のキャッシュ記憶装置において、キャッシュミスの発生時に、アクセス対象となったデータを含むブロックを格納するために使用されるリプレースウェイを制限することを指示するモード信号を入力する手段と、モード信号によりリプレースウェイが制限されるとき、複数のウェイの一部のウェイからリプレースウェイを決定するリプレースウェイ決定手段とを有することを特徴とする。
【００２２】
本発明の好ましい態様において、リプレースウェイの制限は、実行される命令がデータの先読みを行うためのプリフェッチ命令である場合に実行される。また、リプレースウェイは、同一のセットをアクセスする実行中のプリフェッチ命令の数に応じて決定される。
【００２３】
また、本発明の他の観点によれば、キャッシュブロックのリプレースアルゴリズムにＬＲＵを使用したセットアソシアティブ方式のキャッシュ記憶装置を備えるプロセッサにおいて、キャッシュ記憶装置に、プリフェッチ命令でフェッチしたデータを格納するウェイを制限する回路を設けたことを特徴とするプロセッサが提供される。このキャッシュ記憶装置は、同一セットをアクセスする実行中のプリフェッチ命令の数により、リプレースウェイの決定方法を変更する。
【００２４】
このように、時間的局所性が低いプリフェッチデータを格納するウェイを制限することにより、大規模データがプリフェッチ命令によってキャッシュにフェッチされる場合も、時間的局所性が高い、例えば、スカラデータがプリフェッチデータによってキャッシュから追い出されにくくすることができる。
【００２５】
【発明の実施の形態】
図１は、本発明の一実施形態による計算機システムの構成を示すブロック図である。計算機システム１は、複数のプロセッサ１０、主記憶装置２０、Ｉ／Ｏインタフェース３０を有している。これら、プロセッサ１０、主記憶装置２０、Ｉ／Ｏインタフェース３０は、バス４０を介して相互に接続される。Ｉ／Ｏインタフェース３０には、Ｉ／Ｏデバイスや外部ネットワークなどに接続される。各プロセッサ１０は、主記憶装置２０に格納されたプログラムを順次読み出して実行する。また、各プロセッサ１０は、プログラムの実行に伴って、主記憶装置２０に格納されているデータの読み出し、主記憶装置２０へのデータの書き込み等を実施する。
【００２６】
図２は、プロセッサ１０の構成例を示す概略のブロック図である。プロセッサ１０は、命令キャッシュ１１、ディスパッチユニット１２、浮動小数点演算ユニット１３、整数演算ユニット１４、分岐ユニット１５、レジスタ群１６、プロセッサバス制御ユニット１６、及びキャッシュ記憶装置１００を有している。
【００２７】
命令キャッシュ１１は、主記憶装置２０から読み出された命令を一時的に保持する。ディスパッチユニット１２は、命令キャッシュ１１から命令を読み出し、それをデコードして実行すべき演算に対応するユニットにディスパッチする。
【００２８】
浮動小数点演算ユニット１３、整数演算ユニット１４、及び分岐ユニット１５は、それぞれ、浮動小数点命令、固定小数点命令、分岐命令を実行する。キャッシュ記憶装置１００は、ディスパッチユニットによりディスパッチされるロード／ストア命令を実行するロードストアユニットと、主記憶装置２０に格納されたデータの一部のコピーを保持するメモリ部１０１を有する。
【００２９】
レジスタ群１６は、各ユニットが命令の実行に使用するデータを保持し、あるいは、各ユニットが命令の実行結果として出力するデータを保持するための各種のレジスタを有している。レジスタ群１６には、後述するモード信号の生成に用いられるレジスタであるＳＰＲ（Special Purpose Register）が含まれる。
【００３０】
プロセッサバス制御ユニット１７は、バス４０に接続する主記憶装置２０などとの間でのデータの入出力を制御する。
【００３１】
プロセッサ１０は、一般的に、１つのＬＳＩとして実装される。本実施形態では、プロセッサ１０内の内部にキャッシュ記憶装置１００を有するように構成されているが、キャッシュ記憶装置１００のメモリ部１０１を含む少なくとも一部をプロセッサ１０の外部に設けるようにしても構わない。
【００３２】
図３は、キャッシュ記憶装置１００の構成を示す概略のブロック図である。本実施形態のキャッシュ記憶装置は、１２８Ｋバイトのキャッシュサイズを有し、ブロックサイズが１２８バイト、４ウェイのセットアソシアティブ方式のキャッシュである。また、ブロックの置き換えアルゴリズムとしてＬＲＵが用いられ、ストアスルー方式で制御されるものとする。なお、図では、ロードストアユニット１８の中で、特に本発明と関係しない部分については図示を省略している。
【００３３】
キャッシュ記憶装置１００は、メモリ部１０１、セレクタ１０８、ヒット／ミス判定回路１２２、ＬＲＵエンコード回路１１０、プリフェッチウェイ制御回路１３０、ＬＲＵデコード回路１１２、選択ＲＯＷ制御回路１１３、及びＤＡＴＡ／ＴＡＧ／ＬＲＵ制御回路１２３を含んで構成される。
【００３４】
メモリ部１０１には、キャッシュされるデータを保持するデータアレイ、そのアドレス（タグ）を保持するアドレスアレイ、及びＬＲＵアレイ１１１が含まれる。データアレイ及びアドレスアレイは４つのカラム（ウェイ）に分かれており、それぞれのウェイは、データ及びタグを格納する２５６個のブロック（セット）を有する。ＬＲＵアレイ１１１には、各セットに対応して、メモリ部１０１に保持されたデータの参照履歴情報（ＬＲＵ情報）が保持される。
【００３５】
セレクタ１０８は、メモリ部１０１から読み出されたデータから出力すべきデータを選択する。ヒット／ミス判定回路１２２は、ＣＰＵから出力されるアドレスと、メモリ部１０１に保持されているタグ情報とに基づいて、目的のデータがキャッシュに存在するか否か、すなわちヒット／ミスの判定を行う。ＬＲＵエンコード回路１１０は、ＬＲＵアレイ１１１に書き込むＬＲＵ情報の値を作成する。プリフェッチウェイ制限回路１３０は、ＬＲＵアレイから読み出したＬＲＵ情報の値に対して、対象の命令がプリフェッチ命令である場合に、使用するウェイを制限する。ＬＲＵデコード回路１１２は、プリフェッチウェイ制限回路１３０から出力されるＬＲＵ情報の値に基づいて、キャッシュ記憶装置１００から追い出すデータを含むウェイを決定する。選択ＲＯＷ制御回路１１３は、データアレイおよびアドレスアレイから読み出したカラム内の４個のブロックのデータから１つを選択するためのセレクト信号１１８を作成する。ＤＡＴＡ／ＴＡＧ／ＬＲＵ制御回路１２３は、データアレイ、アドレスアレイ、及びＬＲＵアレイに対する書き込み、および読み出しを制御する。
【００３６】
以下、通常のロード命令の実行にともなう、キャッシュ記憶装置１００の動作、特にＬＲＵデコード回路１１２とＬＲＵエンコード回路１１０の動作について説明する。なお以下の説明において、アドレスは、４０ビットで構成され、上位２５ビットは、同一のセットに格納される可能性のある主記憶上のブロックのインデックス、次の８ビットがメモリ部１０１におけるセット位置を示すセット番号、下位７ビットがブロック内のオフセット値を表すものとする。これらの各ビット部分をそれぞれ、ブロックアドレス部、セットアドレス部、及びオフセットアドレス部と呼ぶ。また、プリフェッチ命令が、キャッシュミスの判明からデータがキャッシュ記憶装置１００にフェッチされるまでの状態にあるとき、このプリフェッチ命令はＯＮ─ＴＨＥ─ＦＬＹ状態であると呼ぶ。
【００３７】
ＣＰＵにより通常のロード命令が発行されると、命令により参照されるデータの主記憶における格納位置を示すアドレス１０２、データおよびタグを更新するか否かを表すデータ／タグ更新信号１０６、キャッシュ記憶装置１００からのデータの読み出しを指示するキャッシュ読み出し信号１０７が与えられる。
【００３８】
これらの信号が与えられると、まずアドレス１０２のセットアドレス部によって、データアレイ／アドレスアレイがアクセスされ、セット番号に対応するセット内のウェイ０、ウェイ１、ウェイ２、ウェイ３に格納されているデータおよびタグが読み出される。
【００３９】
次に、ＨＩＴ／ＭＩＳＳ判定回路１２２において、読み出された４個のタグの値と、ロード命令で参照されるアドレスのブロックアドレス部分が比較される。ＨＩＴ／ＭＩＳＳ判定回路１２２での比較において、読み出されたタグのいずれかがブロックアドレス部と一致していれば、ロード命令により参照されるブロックがキャッシュ上に存在することになる（キャッシュヒット）。このとき、ＨＩＴ／ＭＩＳＳ判定回路１２２は、ヒット信号１１６として‘１’を出力する。いずれのウェイとも一致しなければ、ロード命令により参照されるブロックはキャッシュ上には存在せず（キャッシュミス）、ヒット信号１１６として‘０’が出力される。
【００４０】
ＨＩＴ／ＭＩＳＳ判定回路１２２は、ヒット信号１１６とともに、ヒット時には、ヒットしたウェイのウェイ番号をヒットウェイ信号１１９として出力する。
【００４１】
選択ウェイ制御回路１１３は、ＨＩＴ／ＭＩＳＳ判定回路１２２の判定結果に応じて、読み出すべきウェイを決定する。判定結果がヒット（ヒット信号１１６＝‘１’）ならば、ヒットウェイ信号１１９によって与えられるウェイ番号を選択ウェイ信号１１７として出力する。この選択ウェイ信号１１７は、セレクタ１０８へのセレクト信号１１８としても使われる。セレクタ１０８は、セレクト信号１１８を使用して、同時に読み出した４個のデータおよびタグから１つをセレクトし、読み出しデータ１１４および読み出しタグ１１５をロード命令の結果として出力する。
【００４２】
ＨＩＴ／ＭＩＳＳ判定回路１２２での結果がミスの場合、選択ウェイ制御回路１１３は、ＬＲＵデコード回路１１２から出力されるＬＲＵウェイ信号１５１（追い出し対象ウェイを示すウェイ番号）を選択ウェイ信号１１７として出力する。その後、主記憶からデータがフェッチされて、更新データ１０３、更新タグ１０４が与えられ、１ブロック分のデータがメモリ部１０１に書き込まれる。このとき、データは、選択ウェイ信号１１７として出力された追い出し対象ウェイ番号に対応したウェイに書き込まれる。
【００４３】
キャッシュミス時に追い出し対象となるウェイは、プリフェッチウェイ制限回路１３０およびＬＲＵデコード回路１１２で決定される。ＬＲＵアレイ１１１から出力された該当セットのＬＲＵ情報の値は、まずプリフェッチウェイ制限回路１３０に入力される。このとき、命令がプリフェッチ命令で、モード信号１３４が‘１’であるときは、後述するように、使用可能なウェイを制限するようにＬＲＵ情報の値が変更される。プリフェッチ以外の命令では、ＬＲＵアレイ１１１から出力されたＬＲＵ情報の値は、ＬＲＵ信号１３２としてプリフェッチウェイ制限回路１３０からそのまま出力される。プリフェッチウェイ制限回路１３０から出力されたＬＲＵ情報の値は、ＬＲＵデコード回路１１２に入力され、追い出すべきウェイ番号がＬＲＵウェイ信号１５１として出力される。
【００４４】
図４は、本実施形態における４ウエイセットアソシアティブのＬＲＵの実現方法を表している。この方法では、各セットのＬＲＵ情報は、６ビットで表される。最も最近アクセスされたウェイの決定および、最も最近アクセスされたウェイへのＬＲＵ情報の更新が、６ビットのうちの３ビットを用いて行われる。
【００４５】
図４において、各ノード２０１、２０２、２０３、２０４は、４ウエイセットアソシアティブにおける各ウェイを表す。ノード間のエッジ（矢印）ＮＥＷＥＲ（０）〜ＮＥＷＥＲ（５）は、エッジの終点ノードが始点ノードよりも最近参照されたノードであることを表している。全てのエッジに対して始点であるノードは、最も遠い昔にアクセスされたノード（追い出し対象となるウェイに対応するノード）であり、全てのエッジに対して終点であるノードは最も最近アクセスされたノードである。図４に示す状態を初期状態とし、エッジの向きをＮＥＷＥＲ（０─５）＝（０、０、０、０、０、０）の６ビットで定義する。エッジの向きが逆になると、対応するビットは‘１’となり、全てのエッジが逆になると、ＮＥＷＥＲ（０─５）＝（１、１、１、１、１、１）として表される。この６ビットの情報がＬＲＵ情報として用いられ、ＬＲＵアレイ１１１に保持される。
【００４６】
キャッシュミス時には、ＬＲＵアレイ１１１から６ビットのＬＲＵ情報が出力され、プリフェッチウェイ制限回路１３０に入力される。通常のロード命令の場合、前述したようにプリフェッチウェイ制限回路１３０に入力された値は、そのままＬＲＵデコード回路１１２への入力となる。
【００４７】
図５は、ＬＲＵデコード回路１１２において、ＬＲＵ情報を使用して４ウエイのうちで最も遠い昔にアクセスされたウェイを決定するためのデコード表である。図において、各エントリに設定されている‘０’は、エッジの向きが図４に示す初期状態と同じであることを示し、‘１’は、エッジの向きが初期状態と反対であることを示す。ＬＲＵデコード回路１１２は、このデコード表３０１に示される論理に従って入力されたＬＲＵ情報を検査し、最も遠い昔にアクセスされたウェイを決定する。
【００４８】
例えば、ウェイ０が最も遠い昔にアクセスされたウェイとなるのは、ウェイ０とつながる矢印ＮＥＷＥＲ（０）、ＮＥＷＥＲ（３）、ＮＥＷＥＲ（４）の全てがウェイ０から出ている場合である。すなわち、各矢印が初期状態と同じＮＥＷＥＲ（０、３、４）＝（０、０、０）の場合である。同様に、ウェイ１が追い出しの対象となるのは、ＮＥＷＥＲ（０）が初期状態と異なり、ＮＥＷＥＲ（１）、（５）が初期状態と同じである、ＮＥＷＥＲ（０、１、５）＝（１、０、０）の場合である。
【００４９】
通常のロード命令の実行では、キャッシュヒット時、及びキャッシュミス時に主記憶からフェッチしたデータをキャッシュに書き込む際にＬＲＵ情報が更新される。前者の場合は、ロード命令の対象とされるデータを格納したウェイ、後者の場合は、新たにデータが書き込まれるウェイが最新（最も最近参照された）ウェイとなるようにＬＲＵ情報が更新される。
【００５０】
上述したように、キャッシュヒット時は、ＨＩＴ／ＭＩＳＳ判定回路１２２から出力されるヒットウェイ信号１１９が、また、キャッシュミス時は、ＬＲＵデコード回路１１２から出力されるＬＲＵウェイ信号１５１が選択ＷＡＹ制御回路１１３により選択され、選択ウェイ信号１１７として出力される。選択ウェイ信号１１７は、セレクタ１０９を介してＬＲＵエンコード回路１１０に入力される。ＬＲＵエンコード回路１１０は、入力された選択ウェイ信号１１７により示されるウェイ番号をＬＲＵアレイに登録するＮＥＷＥＲ（０─５）としてエンコードする。ＬＲＵアレイ１１１に設定されているＬＲＵ情報は、ＬＲＵエンコード回路１１０によりエンコードされた情報（ＮＥＷＥＲ（０─５））に基づいて更新される。
【００５１】
図６は、ＬＲＵエンコード回路１１０において、入力された選択ＷＡＹ信号で示されるウェイが最も最近アクセスされたウェイとして示されるように、ＬＲＵを変更するために用いられるエンコード表である。図において、各エントリに設定されている‘０’は、エッジの向きが図４に示す初期状態と同じであることを示し、‘１’は、エッジの向きが初期状態と反対であることを示す。ＬＲＵエンコード回路１１０は、このデコード表３０１に示される論理に従って入力された選択ＷＡＹ信号で示されるウェイが最新のものとなるように、ＬＲＵ情報を更新する情報を生成する。
【００５２】
例えば、ＬＲＵエンコード回路１１０への入力がウェイ０を示す場合、エンコード表３０２に従って、ＮＥＷＥＲ（０）、（３）、（４）に対応するＬＲＵ情報のビットを‘１’に変更する。これは図４において、ウェイ０に繋がる矢印が全てウェイ０を向くように変更することを意味する。同様にＬＲＵエンコード回路１１０への入力がウェイ１を示す場合は、ＮＥＷＥＲ（０）に対応するＬＲＵ情報のビットを‘０’に、NEWER（１）、（５）に対応するＬＲＵ情報のビットを‘１’にセットする。
【００５３】
次に、プリフェッチ命令の実行にともなう、キャッシュ記憶装置１００の動作について説明する。
【００５４】
通常のロード命令の実行においてキャッシュミスが発生すると、該当するセット内の全てのウェイの中で、最も遠い昔にアクセスされたウェイが追い出し対象として選択される。一方、プリフェッチ命令の場合、該当するセット内のプリフェッチ命令で使用が許されたウェイの中で、最も遠い昔にアクセスされたウェイが追い出し対象として選択される。本実施形態では、プリフェッチ命令で使用可能なウェイを、４個のウェイのうち、ウェイ０およびウェイ１の２個に制限する場合について説明する。なおこれは一実施例であり、プリフェッチ可能なウェイの数は、同様の方法で容易に変更することができる。
【００５５】
ＣＰＵによるプリフェッチ命令の実行にともない、通常のロード命令の場合と同様に、命令で参照されるアドレスのセットアドレス部によって、メモリ部１０１がアクセスされ、該当するセットのデータ、タグ、ＬＲＵ情報が読み出される。キャッシュヒットすれば、上述したロード命令の場合と同様に、該当するデータが読み出されてプリフェッチ命令の処理を終了する。この際、通常のロード命令と同様に、ヒットしたデータが格納されているウェイが、最も最近参照されたものとして示されるようにＬＲＵ情報が変更される。
【００５６】
プリフェッチ命令でキャッシュミスが発生すると、ロード命令の場合と同様に、選択ウェイ信号１１７として、追い出し対象のウェイを指定するウェイ番号が出力される。主記憶からフェッチされたデータブロックは、この追い出し対象のウェイに格納される。追い出し対象のウェイは、次のように決定される。
【００５７】
キャッシュミスが発生すると、ＬＲＵアレイ１１１から該当するセットのＬＲＵ情報であるＬＲＵ信号１３１が出力される。ＬＲＵ信号１３１は、プリフェッチウェイ制限回路１３０に入力される。プリフェッチウェイ制限回路１３０は、プリフェッチで使用可能なウェイに制限を加えたＬＲＵ信号１３２を出力する。ＬＲＵ信号１３２は、ＬＲＵデコード回路１１２に入力され、前述した通常のロード命令と同様にして、追い出し対象のウェイが決定される。
図７は、プリフェッチウェイ制限回路１３０の論理構成を示すブロック図である。ＬＲＵアレイ１１１から出力されるＬＲＵ信号１３１には、ＬＲＵＯＵＴ（０）─（５）の６つのビットが含まれる。プリフェッチ信号１３３は、キャッシュをアクセスしている命令がプリフェッチ命令であることを表す信号である。モード信号１３４は、プリフェッチウェイを制限するモードであることを表す信号である。モード信号１３４が‘１’のときは、プリフェッチで使用するウェイが制限される。モード信号１３４が‘０’のときは、プリフェッチ命令時もウェイの制限がされず、通常のロード命令と同様に、全てのウェイが使用される。
【００５８】
モード制限信号１３４としては、レジスタ群１６内のＳＰＲの特定のビットが用いられる。モード制限信号１３４を‘１’にセットするには、例えば、モード制限信号１３４に対応したビットが‘１’となる値をレジスタ群１６内の汎用レジスタにセットし、この汎用レジスタの値をＳＰＲにコピーする。このような処理によりＳＰＲのモード信号に対応した特定ビットに‘１’がセットされると、モード制限信号１３４として‘１’が出力され、それがキャッシュ記憶装置１００に与えられる。モード制限を解除する場合には、上記と同様にして、ＳＰＲの特定ビットに‘０’をセットすればよい。
【００５９】
ウェイ制限信号５００は、キャッシュ記憶装置１００をアクセスしている命令がプリフェッチ命令であり、かつプリフェッチウェイ制限モードである場合に、‘１’となる信号である。ウェイ制限信号５００が‘１’のとき、本回路の出力であるＮＥＷＥＲ（０）─（５）のうち、ＮＥＷＥＲ（１）、（３）、（４）、及び（５）が‘０’になる。このことは、図４において、ＮＥＷＥＲ（１）、（３）、（４）、及び（５）に対応する矢印を、ウェイ０、または１からウェイ２、または３に向かう矢印として固定することを意味する。つまり、ＮＥＷＥＲ（１）、（３）、（４）、及び（５）を‘０’に固定することで、ＬＲＵデコード回路１１２により、ウェイ０、１が、ウェイ２、３よりも昔にアクセスされたウェイとして認識されることになり、プリフェッチ命令の際に追い出しの対象となるウェイをウェイ０とウェイ１に制限できる。なお、ＮＥＷＥＲ（０）、（３）、（４）を‘０’固定することで、プリフェッチ命令で追い出しの対象として指定できるウェイをウェイ０だけに制限でき、また、ＮＥＷＥＲ（１）、（２）、（５）を‘０’固定することで、ウェイ０、１、２の３ウェイに制限することができる。
ＬＲＵデコード回路１１２は、プリフェッチウェイ制限回路１３０から出力されたＬＲＵ信号１３２に基づき、追い出し対象のウェイ番号を決定する。ＬＲＵデコード回路１１２は、デコード表３０１に示すデコード論理に基づいてＬＲＵ情報をウェイ番号に変換する。ＣＰＵにより発行された命令が、プリフェッチ命令以外の命令であれば、ＬＲＵデコード回路１１２は、この変換結果として得られるウェイ番号で指定されるウェイを追い出し対象として、そのウェイ番号を出力する。一方、プリフェッチ命令の場合は、さらにＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数を考慮して追い出し対象のウェイが決定される。
【００６０】
図８は、同一のセットに対するＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数を考慮した追い出し対象ウェイの決定制御論理を表す論理表である。プリフェッチ命令で追い出しウェイが制限されている場合は、デコード表３０１から得られたウェイ番号と、同一セット内のＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ数との関係から論理表３０３に従って出力される追い出し対象のウェイ番号が決定される。
【００６１】
論理表３０３に従うと、同一セットに対するＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数が０個の場合は、デコード表３０１の論理に従って決定された追い出し対象のウェイ番号がそのまま出力される。ＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数が１個の場合は、３０１から出力された追い出し対象のウェイは、既に実行されているプリフェッ チ命令で使用されるので、プリフェッチウェイでの使用を許されているウェイ１を追い出し対象とする。本実施形態では、プリフェッチで使用可能なウェイが２個に制限されているので、同一セットのＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数が１個以下ならば、制限されたウェイ内で追い出し対象のウェイが決定される。
【００６２】
ＬＲＵデコード回路１１２は、同一セットにおけるＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数が２個以上になると、プリフェッチ命令で使用できるウェイの制限を解除し、同一セット内の全てのウェイをプリフェッチ命令で使用できるように制御する。このウェイの制限の解除は、次のような状況でキャッシュミスの増加を抑止するために行われる。
【００６３】
・同一セットのＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令が２個の状態でプリフェッチ命令が実行された。
・この状態でプリフェッチ用の２個のウェイは、将来、先に出されたＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令で使用することが決まっている。
・追い出し対象のウェイをプリフェッチ用に制限したウェイのいずれか（ＯＮ─ＴＨＥ─ＦＬＹのプリフェッチがデータを書き込むウェイ）を追い出し対象にすると、データの読み出しが終わる前にブロックがキャッシュから追い出され、キャッシュミスが増加する可能性がある。
【００６４】
論理表３０３によると、同一セットのＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令が２個の状態でプリフェッチ命令が実行されると、ウェイ０、ウェイ１は既に予約されているので、デコード表３０１による変換の結果として得られたウェイが、ウェイ０ならばウェイ２、ウェイ１ならばウェイ３が追い出し対象として出力される。同様にＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令が３個の場合は、ウェイ３、あるいはウェイ２が追い出し対象として出力される。
【００６５】
本実施形態では、ＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令が２個または３個の時にデコード表３０１により得られる結果にしたがって、固定的にウェイ２、ウェイ３を追い出し対象としているが、ウェイ２、３の新旧関係をもとに追い出し対象ウェイを決定するようにすることもできる。
【００６６】
図９は、ＬＲＵデコード回路１１２の一構成例を示すブロック図である。
【００６７】
ＬＲＵデコード回路１１２への入力は、プリフェッチウェイ制限回路から出力されたＬＲＵ信号１３２、プリフェッチウェイを制限するモードであることを表すＭＯＤＥ信号１３４、及び、現在処理中の命令がプリフェッチ命令であることを表すプリフェッチ信号１３３である。ＬＲＵデコード回路１１２の出力は、選択したウェイ番号を示すＬＲＵウェイ信号１５１である。
【００６８】
入力されたＬＲＵ信号１３２は、まずリプレースウェイデコード回路７００によってウェイ番号に変換される。リプレースウェイデコード回路７００は、デコード表３０１の論理に従って入力されたＬＲＵ信号１３２を変換し、ウェイ０−３の一つを指定する４ビットの１次ＬＲＵウェイ信号７０１を出力する。１次ＬＲＵウェイ信号７０１は、デコード表３０１の論理により選択されたウェイに対応するビットが‘１’となる。
【００６９】
選択ウェイ決定回路７１０は、追い出しウェイとして選択されるウェイが制限されているときに、同一セットのＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数によって選択ウェイを決定する回路である。選択ウェイ決定回路７１０には、同一セットのプリフェッチ命令の数を表すプリフェッチ数信号（０一３）７０２と、リプレースウェイデコード回路７００でウェイ０が選択されたときに‘１’となるプリフェッチウェイ０信号７０３が入力される。これらの入力信号に基づいて、選択ウェイ決定回路７１０は、論理表３０３の論理に従って選択されるウェイを指定する２次ＬＲＵウェイ信号７０４を出力する。
【００７０】
１次ＬＲＵウェイ信号７０１、２次ＬＲＵウェイ信号７０４は、セレクタ７２０に入力される。セレクタ７２０は、モード信号１３４及びプリフェッチ信号１３３が入力される論理積ゲート７３０の出力として得られる切替信号７０５によって１次ＬＲＵウェイ信号７０１と２次ＬＲＵウェイ信号７０４を選択的に出力する。具体的には、モード信号１３４とプリフェッチ信号１３３が共に‘１’であり、プリフェッチ命令でウェイを制限するモードであれば、２次ＬＲＵウェイ信号７０２をＬＲＵウェイ信号１５１として出力し、それ以外の場合は、１次ＬＲＵウェイ信号７０１をＬＲＵウェイ信号１５１として出力する。
【００７１】
図１０は、“空間的局所性はあるが、時間的局所性がない”大きな配列のアクセスが発生するプログラムの一例である。
【００７２】
図１０に示すプログラムは、配列の各要素が８バイトの１００×１６０００の配列Ｓを１００×１６０００の配列Ｔにコピーするプログラムである。内側のループ８０１で１６０００個の要素のコピーが行われ、外側のループ８０２が１００回繰り返されて、全要素のコピーが行われる。外側ループ８０２の各繰り返しにおいて、外側ループ８０２内には、内側ループ８０１の実行が始まる前に、ライン８０３によりスタック上の局所変数へのアクセスがあると仮定する。また配列Ｓ、Ｔの先頭要素は１２８バイト境界に配置されていると仮定する。
【００７３】
このプログラムにおいて、配列Ｓ、Ｔに対するメモリ参照は、ある一定時間内に比較的近いアドレスに分布するが、同一アドレスに対する参照は一度しか発生しない。したがって、配列Ｓ、Ｔのメモリアクセスパターンには、空間的局所性はあるが、時間的局所性はないといえる。一方、ライン８０３で参照されるスタック上のデータは、外側ループ８０２の繰り返し毎に同一アドレスが参照されるので、時間的局所性があるといえる。
【００７４】
図１１は、図１０に示したプログラムの内側ループ８０１を疑似命令列で書き換えたものである。図１１に示すプログラムの内側ループ９０１は、配列Ｓの各要素をロードして、配列Ｔの各要素にストアする疑似命令列になる。内側ループ９０１は１６０００回繰り返される。配列Ｓの要素は８バイトなので、外側ループ８０２の１回の繰り返しで、キャッシュサイズと同じ１２８Ｋバイトのメモリ領域がシーケンシャルにアクセスされる。
【００７５】
図１２は、上述したプログラムにプリフェッチ命令を適用したプログラムの一例である。このプログラムでは、理解を容易にするために、内側のループ１００１を、そのループをアクセスするウェイ別に分割して記述してある。
【００７６】
このプログラムをプリフェッチ命令で使用するウェイを制限せずに実行した場合、外側ループ１０００の最初の繰り返しで、「局所変数の使用」１０１０によって、スタックのデータを格納するブロックがキャッシュ上にコピーされる。内側ループ１００２―１００５では、それぞれ１回の繰り返しで１２８バイトが使用され、内側ループ１００２−１００５の全繰り返しで１２８Ｋバイトが使用される。配列Ｓはシーケンシャにデータをアクセスするするので、最初の３２Ｋバイトではウェイ０が、次の３２Ｋバイトではウェイ１が、その次の３２Ｋバイトではウェイ２が、最後の３２Ｋバイトではウェイ３が使用される。つまり、内側ループ１００１を実行すると配列Ｓによってキャッシュ全体が上書きされてしまう。
【００７７】
このため、その後、外側ループ１０００の次の繰り返しにおいて、「局所変数の使用」１０１０により再びスタックが参照されたとき、キャッシュミスが発生する。このプログラムでは、外側ループ１０００の繰り返し毎に、「局所変数の使用」１０１０でキャッシュミスが発生する。
【００７８】
一方、モード信号１３４を‘１’にセットしてプリフェッチ命令で使用するウェイを制限すると、ループ１００２内で使用されるデータは、ウェイ０にプリフェッチされ、ループ１００３で使用されるデータは、ウェイ１にフェッチされる。次に、ループ１００４で使用されるデータをプリフェッチする際には、使用できるウェイが制限されるため、再びウェイ０にフェッチされる。同じように、次のループ１００５で使用されるデータは、ウェイ１にフェッチされる。
【００７９】
このように、プリフェッチ命令で使用できるウェイを制限することで、内側ループ１００１全体を実行した後でも、「局所変数の使用」１０１０で参照される局所変数がキャッシュ上に残っている可能性が高くなる。
以上説明したように、本実施形態によれば、プリフェッチ命令時にキャッシュミスが発生したときのキャッシュ記憶装置からの追い出しウェイを制限することで、空間的局所性はあるが、時間的局所性が無いデータの参照によって、時間的局所性のあるデータがキャッシュから追い出されることを減少させることができる、また、マルチプロセス環境においても特別な処理を行うことなくＬＲＵを正常に動作させることができる。
【００８０】
なお、本発明は上述した実施形態に限定されるものではなく、キャッシュサイズ、ブロックサイズ、あるいはウエイ数が異なるキャッシュ記憶装置にも適用することが可能である。また、ストアスルー方式のキャッシュ記憶装置に限らず、ストアイン方式のキャッシュ記憶装置にも適用可能である。
【００８１】
【発明の効果】
本発明によれば、プリフェッチ命令で使用できるウェイを制限する回路を具備することにより、プリフェッチ命令のような空間的局所性はあるが時間的局所性のないデータの参照によって、時間的局所性のあるデータがキャッシュからおいだされることを抑止することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態における計算機システムの構成を示す概略のブロック図である。
【図２】プロセッサの構成を示す概略のブロック図である。
【図３】キャッシュ記憶装置の構成を示す概略のブロック図である。
【図４】４ウエイセットアソシアティブのＬＲＵの実現方法を表す概念図である。
【図５】ＬＲＵ情報を使用して４ウエイのうちで最も遠い昔にアクセスされたウェイを決定するためのデコード表を示す図である。
【図６】ＬＲＵを変更するために用いられるエンコード表を示す図である
【図７】プリフェッチウェイ制限回路１３０の論理構成を示すブロック図である。
【図８】同一のセットに対するＯＮ─ＴＨＥ─ＦＬＹのプリフェッチ命令の数を考慮した追い出し対象ウェイの決定制御論理を表す論理表を示す図である。
【図９】ＬＲＵデコード回路１１２の一構成例を示すブロック図である。
【図１０】“空間的局所性はあるが、時間的局所性がない”大きな配列のアクセスが発生するプログラムの一例を示すソースプログラムである。
【図１１】図１０に示すプログラムの内側ループを疑似命令列で書き換えたプログラムのプログラムリストである。
【図１２】図１１に示すプログラムにプリフェッチ命令を適用したプログラムの一例を示すプログラムリストである。
【符号の説明】
１・・・計算機システム、１０・・・プロセッサ、２０・・・主記憶装置、１００・・・キャッシュ記憶装置、１０１・・・メモリ部、１０２・・・アドレス信号、１０８・・・セレクタ、１１０・・・ＬＲＵエンコード回路、１１１・・・ＬＲＵアレイ、１１２・・・ＬＲＵデコード回路、１１３・・・選択ウェイ制御回路、１２０・・・データ／タグ／ＬＲＵ制御信号、１２２・・・ヒット／ミス判定回路、１２３・・・データ／タグ／ＬＲＵ制御回路、１３０・・・プリフェッチウェイ制限回路、１３３・・・プリフェッチ信号、１３４・・・モード信号。
【図１】
0003812258.tif 000002
【図２】
0003812258.tif 000003
【図３】
0003812258.tif 000004
【図４】
0003812258.tif 000005
【図５】
0003812258.tif 000006
【図６】
0003812258.tif 000007
【図７】
0003812258.tif 000008
【図８】
0003812258.tif 000009
【図９】
0003812258.tif 000010
【図１０】
0003812258.tif 000011
【図１１】
0003812258.tif 000012
【図１２】
0003812258.tif 000013