キャッシュ汚染減少方法および装置

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	キャッシュ汚染減少方法および装置
【発明者】	【氏名】ジェイムス・イー・マコーミック・ジュニア【氏名】スティーブン・アール・アンディ
【要約】	【課題】利用頻度の高いキャッシュを保持する方法を提供する。【解決手段】非参照データをキャッシュ２０２へと書き込むときに、該非参照データを低使用頻度としてマークするステップ３０４と、参照データをキャッシュ２０２へと書き込むときに、該参照データを高使用頻度としてマークするステップ３０６と、前記キャッシュからデータ値をフェッチする際に、その使用状況を高使用頻度に更新するステップと、新しいデータ４００を前記キャッシュへと書き込むときに、低使用頻度としてマークされたデータに前記新しいデータを上書きするステップとを含んでなるキャッシュ汚染減少方法３００を提供する。

【特許請求の範囲】
【請求項１】非参照データをキャッシュへと書き込むときに、該非参照データを低使用頻度としてマークするステップと、参照データを前記キャッシュへと書き込むときに、該参照データを高使用頻度としてマークするステップと、前記キャッシュからデータ値をフェッチする際に、その使用状況を高使用頻度に更新するステップと、新しいデータを前記キャッシュへと書き込むときに、低使用頻度としてマークされたデータに前記新しいデータを上書きするステップとを含んでなるキャッシュ汚染減少方法。
【請求項２】キャッシュからフェッチされたデータ値の状況を最高使用頻度に更新するステップと、前記非参照データを前記キャッシュへと書き込むときに、該非参照データを最低使用頻度としてマークするステップと、前記参照データを前記キャッシュへと書き込むときに、該参照データを最高使用頻度としてマークするステップと、最低使用頻度としてマークされたデータに前記新しいデータを上書きするステップとを含む方法であって、バッファにフェッチ・データとプリフェッチ・データを記憶するステップと、前記バッファに記憶されたフェッチ・データを参照として最初にマークするステップと、前記バッファに記憶されたプリフェッチ・データを非参照として最初にマークするステップと、前記バッファからデータをフェッチする際に、前記フェッチしたデータを参照としてマークするステップと、前記バッファに記憶されたデータを前記キャッシュへと周期的に書き込むステップとをさらに含んでなる請求項１に記載の方法。
【請求項３】データ・エントリおよび一時的な使用エントリを含むキャッシュと、データ・エントリへとデータを書込む際に少なくとも１つの一時的な使用エントリを更新する手段であって、前記少なくとも１つの一時的な使用エントリが、非参照データを少頻度使用としてマークし、参照データを高使用頻度としてマークするように更新され、前記キャッシュからいくつかの一時的な使用エントリを書込み動作中に読み取り、前記いくつかの一時的な使用エントリによって低使用頻度としてマークされたデータ・エントリを識別し、前記識別したデータ・エントリへと新しいデータを書き込むための手段とを含んでなる汚染低減キャッシュ構造。
【請求項４】前記キャッシュが、ｎ個のウェイのセット・アソシエーティブ・キャッシュであり、ある一時的な使用エントリが前記キャッシュ内の各集合のｎ個のデータ・エントリに対応し、それぞれの一時的な使用エントリが特定の集合のｎ個のデータ・エントリの高使用頻度状況または低使用頻度状況のパターンを指定する請求項３に記載の汚染低減キャッシュ構造。
【請求項５】前記キャッシュが、ｎ個のウェイのセット・アソシエーティブ・キャッシュであり、ある一時的な使用エントリが前記キャッシュ内の各集合のｎ個のデータ・エントリに対応し、特定の一時的な使用エントリの各ビットが前記キャッシュのｎ個のウェイのうちの異なる２つに記憶された２つのデータ値の間の一時的な使用関係を指定する請求項３に記載の汚染低減キャッシュ構造。
【請求項６】バッファと、前記バッファに記憶されたプリフェッチ・データを非参照として最初にマークする手段と、前記バッファからフェッチされたデータを参照としてマークする手段と、データ値とその対応する参照状況を前記バッファから前記キャッシュへと転送するバスとをさらに含んでなる請求項３に記載の汚染低減キャッシュ構造。
【請求項７】前記バッファに記憶されたフェッチ・データを参照として最初にマークする手段をさらに含んでいる請求項６に記載の汚染低減キャッシュ構造。
【請求項８】複数のデータ・アレイおよびデータ状況アレイと、ここで、前記データ状況アレイに記憶されたビット・パターンが前記複数のデータ・アレイに記憶された対応するデータ値の一時的な使用順序を示し、新しいデータを前記キャッシュへと書き込むときに、ビット・パターンとその対応するデータ値をアドレス指定する論理機構と、前記アドレス指定されたビット・パターンを更新する論理機構であって、前記新しいデータの参照状況を受け取る入力と、前記アドレス指定したデータ値のうちのどのデータ値に前記新しいデータを上書きするかの指示を受け取る入力と、前記論理機構の入力に応じて更新ビット・パターンを提供する出力とを含み、前記更新ビット・パターンが、前記参照状況が「参照」である場合には、前記新しいデータを高使用頻度としてマークし、前記参照状況が「非参照」である場合には、前記新しいデータを低使用頻度としてマークする論理機構とを含んでなる汚染低減キャッシュ。
【請求項９】前記キャッシュが、ｎ個のウェイのセット・アソシエーティブ・キャッシュであり、各ビット・パターンが、１集合のｎ個のデータ・エントリに対応する請求項８に記載の汚染低減キャッシュ。
【請求項１０】特定のビット・パターンにおける各ビットが、前記キャッシュのｎ個の手段のうちの異なる２つに記憶された２つのデータ値間の一時的な使用関係を指定する請求項９に記載の汚染低減キャッシュ。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、キャッシュ内のデータの記憶に関し、より詳細には、キャッシュ汚染の低減に関する。本明細書において、キャッシュ汚染とは、１）キャッシュからフェッチされる可能性の高いデータがキャッシュからフェッチされる可能性の低いデータによって上書きされること、および２）近い将来に再使用される見込みのないデータがキャッシュ内に保存されることと定義される。
【０００２】本明細書において、「データ」という語は、２つの意味で使用されることに注意されたい。ある意味において、コンピュータの機能ユニットによって追加され、移動され、あるいは消費される特定のデータ値を指すために使用される。別の意味において、「データ」は、コンピュータの機能ユニットで消費される特定のデータ値および／または実行される命令を指すために使用される。前の段落において、「データ」という語はその包括的な意味で使用されている。
【０００３】
【従来の技術】最新のコンピュータ・システムは、いつかの機能ユニット１０４および記憶階層１０２を含む。機能ユニットは、記憶階層１０６および１０８の一部と、機能ユニットと記憶階層との間で命令およびデータを転送する制御論理機構と共に中央処理装置（または、「プロセッサ」１００）を構成する。図１を参照されたい。機能ユニットは、整数処理装置と、浮動小数点処理装置と、分岐ターゲット加算器と、命令フェッチ・ユニットと、データ・フェッチ・ユニット等を含みうる。
【０００４】プロセッサが命令およびデータを消費できる速度は、機能ユニットと記憶階層との間で命令およびデータを転送することができる速度に大きく依存する。そのような転送速度を高める試みにおいて、多くのコンピュータ・システムは、メモリ・キャッシュ１０６、１０８の階層を使用する。
【０００５】キャッシュは、単に、プロセッサの機能ユニットが近い将来消費すると思われるメイン・メモリ１１０の内容の一部分を一時的に保持するために使用される小さい高速バッファ・メモリである。キャッシュの主な目的は、命令またはデータのフェッチ（fetch）のためにメモリ・アクセスを実行するのにかかる時間を短縮することである。キャッシュ・メモリに記憶された情報は、メイン・メモリ内にある情報よりもかなり短い時間でアクセスすることができる。したがって、キャッシュ・メモリを備えたプロセッサは、命令およびデータをフェッチし、および／または、記憶するのにかかる時間がはるかに少ない。キャッシュ階層では、一般に、下の方のレベルのキャッシュほど、メイン・メモリおよび／または上の方のレベルのキャッシュに記憶された命令およびデータの小さいサブセットを記憶する。しかしながら、下の方のレベルのキャッシュほど、フェッチされた命令およびデータを機能ユニットに速い転送速度で提供する傾向もある。
【０００６】命令およびデータは、メイン・メモリから取り出されるよりもかなり早くキャッシュから取り出されるため、機能ユニットが次に消費する可能性の高い命令とデータをキャッシュに入れておくことが望ましい。この目的を達成するために、プロセッサの中には命令とデータを推論的にフェッチするものもある。すなわち、条件付き命令（たとえば、分岐命令）の結果を予測し、ターゲット・コード・セクション（target code section）から命令およびデータをフェッチする。条件付き命令の実行で第１の結果が得られることが予測される場合は、ターゲット・コード・セクションが連続コード・セクション(sequential code section)と同義である可能性がある。条件付き命令の実行で第２の結果が得られることが予測される場合は、ターゲット・コード・セクションを分岐するために、命令およびデータを非連続コード・セクション(non-sequential code section)からフェッチするようにプログラム・フローの再指定（redirection）が必要である。
【０００７】前の段落で説明した予測したプログラム・フローの結果としてメモリから取り出される命令とデータは、「フェッチ」データとして知られる。しかしながら、追加の命令とデータがメモリから取り出されることがある。そのような追加の命令とデータは、「プリフェッチ」データとして知られる。プリフェッチ・データは、１）代替プログラム・フロー・パスから取り出される命令およびデータと、２）命令がハードウェアにキャッシュ内にロードすることを明示的に要求する命令およびデータと、３）命令に符号化されたヒントがトリガとなって取り出される命令およびデータとを含みうる。
【０００８】キャッシュの中にはフェッチ・データだけを記憶するものもあるが、他のキャッシュは、フェッチ・データおよびプリフェッチ・データの両方を記憶する。キャッシュがプリフェッチ・データを記憶するとき、プリフェッチ・データの一部分は機能ユニットによってけっして消費されないであろう。キャッシュ内の不要なプリフェッチ・データの記憶は、本明細書において「キャッシュ汚染」と呼ばれる（また、本明細書では「プリフェッチ汚染」と呼ばれる）。また、キャッシュ汚染は、データの現在の必要性がなくなったかなり後でフェッチ・データがキャッシュにずっと記憶されていることにより生じる。キャッシュ汚染のこの第２の形態は、本明細書ではしばしば「フェッチ汚染」と呼ばれる。
【０００９】キャッシュ汚染を減少させるためにいくつかの方法が考案された。１つの方法は、新しいキャッシュ・データを最低使用頻度のキャッシュ・データに上書きすることを含む。したがって、最低使用頻度（あるいは最低近時使用頻度、leastrecently used：以下、「ＬＲＵ」とよぶ）交換アルゴリズムは、データ使用率の追跡を必要とする。多くのＬＲＵベースのアルゴリズムが存在するが、真のＬＲＵアルゴリズムは、単に、キャッシュに記憶されたデータ値の一時的な使用順序（temporal use order）をランク付けすることである。ｎ個のウェイのセット・アソシエーティブ・キャッシュ(n-way set-associative cache)では、たとえば、それぞれの索引付けしたデータ値の集合のうちのデータ値が、最高使用頻度から最低使用頻度までランク付けされることがある。新しいデータ値をそのようなキャッシュに書き込むとき、その新しいデータ値は、一般に、１）一集合のデータ値の中の最低使用頻度のデータ値を上書きし、２）その集合の中の最高使用頻度のデータ値としてランク付けされる。したがって、その集合の中の他のデータ値の使用ランクが格下げされる。
【００１０】キャッシュがフェッチ・データおよびプリフェッチ・データを記憶する場合に、キャッシュにデータを記憶するためにＬＲＵベースのアルゴリズムを使用すると問題が生じることがある。ＬＲＵベースのアルゴリズムの使用は、古いフェッチ・データの記憶による汚染を軽減することになるが、このアルゴリズムを使用することによって、キャッシュのデータ・エントリがプリフェッチ・データでさらに汚染され、それによりプリフェッチ・キャッシュの汚染が増大することがある。
【００１１】キャッシュ汚染を減少させるもう１つの方法と、フェッチおよびプリフェッチ・キャッシュ汚染を緩和する方法とは、データの記憶ためにＬＲＵベースのアルゴリズムを実行するがキャッシュ２０２内にフェッチ・データだけを記憶することである。そのような解決策は、バッファ２０４内の上位レベルのメモリ２０８から取り出されたフェッチおよびプリフェッチ・データを記憶し、そしてバッファからキャッシュへのデータの書込みを行うことによって実現することができる。図２を参照されたい。フェッチ・データは、バッファからキャッシュにいつでも（たとえば、キャッシュ・フィル・ポート帯域幅（cache fill port bandwidth）がそれを許容するときに）書き込むことができる。データをバッファからフェッチできる場合には、すなわちキャッシュをバイパスすることができる場合は、このデータの状態を「フェッチ済み（fetched）」にし、またこのデータをキャッシュへと書込む準備をすることができる。
【００１２】バッファからキャッシュにどのデータ値を書込むべきかを決定しやすくするために、データを参照状況（たとえば、単一参照ビット）と共にバッファに記憶することができる。バッファに記憶する前または後に、バッファに記憶されたデータ値が既にフェッチされたかどうかを示す第１の値に参照ビットを設定することができる。これと同様に、バッファに記憶されたデータ値だけが既にプリフェッチされていることを示す第２の値に参照ビットを設定することができる。参照ビットを使用してどのデータ値をキャッシュに書き込むかが決定するため、本明細書では、バッファからキャッシュに書き込まれるフェッチ・データ値は「参照（referenced）」データ値と呼ばれ、またバッファからキャッシュに書き込まれる他のすべてのデータ値は、「非参照(non-referenced)」データ値と呼ばれる。
【００１３】
【発明が解決しようとする課題】一般に、前述の方法で使用されるバッファは小さい（おそらく、ほぼ８エントリ）。バッファが大きすぎると、キャッシュと同じようになり、その有効性と効率が多少失われる。しかしながら、小さいサイズのバッファも問題を含むことがある。非汚染プリフェッチが、フェッチよりもかなり前に生じた場合、または多くの汚染プリフェッチが生じた場合には、バッファの容量をすぐに超え、有用なプリフェッチ・データが失われることがある。したがって、バッファは、キャッシュ内の汚染を減少させるが、データの上書きによってプリフェッチ・データの大きな部分を失う危険がある。当該技術分野において知られているように、上の方のレベルのキャッシュ（または、メイン・メモリ）からデータ値を再フェッチすることは、タイミングおよびリソース使用率の両方の点で犠牲が大きいことがある（たとえば、上の方のレベルのキャッシュの読取りポートや、上の方のレベルのキャッシュと機能停止した(stalled)パイプラインとの間のすべてのバスやその他のリソースを使用しなければならないことがある）。したがって、プリフェッチ・データの損失が生じる可能性が低いキャッシュ汚染を減少させるためのより良い方法および装置が必要である。
【００１４】
【課題を解決するための手段】本発明により、本明細書において、キャッシュにフェッチ・データとプリフェッチ・データの両方を保存することを試みながらキャッシュ汚染を減少させるための方法および装置を開示する。
【００１５】たとえば、キャッシュ汚染を減少させる第１の好ましい方法は、キャッシュに書き込むときに非参照データを低使用頻度としてマークし、キャッシュに書き込むときに参照データを高使用頻度としてマークする段階を含む。キャッシュからデータ値を次にフェッチするとき、その使用状況が、より高使用頻度に更新されることがある。新しいデータをキャッシュに書き込むとき、新しいデータは、低使用頻度としてマークされたデータに上書きされる。
【００１６】要するに、前述の方法は、新しいキャッシュ・データを常に最高使用頻度としてマークするＬＲＵ規則を不要にする。その代わりに、新しいフェッチ・データは、高使用頻度（あるいは高近時使用頻度）としてマークされる（また、ほとんどの場合、最高使用頻度としてマークされる）。一方、新しいプリフェッチ・データは、低使用頻度（あるいは低近時使用頻度）としてマークされる（また、ほとんどの場合、最低使用頻度としてマークされる）。ｎウェイ（n-way）のセット・アソシエーティブ・キャッシュ（set-associative cache）において、これは、プリフェッチ・データの記憶をキャッシュのエントリの１／ｎに制限しながら、フェッチ・データの記憶にキャッシュのエントリの（ｎ－１）／ｎを残しておく効果を有する。したがって、不要なプリフェッチ・データによって生じる可能性のある汚染がキャッシュの１／ｎに制限される。しかしながら、実際には、多くのプリフェッチ・データ値は結局のところ新しいデータで上書きする前にフェッチされるため、不要なプリフェッチ・データによる汚染はほとんどなく、それらのフェッチの際に、それらの使用状況を最高使用頻度に更新することができ、それによりキャッシュ内の連続的な管理が保証される。
【００１７】また、たとえば、前述の方法を実現する汚染低減キャッシュ構造の第１の好ましい実施形態は、いくつかのデータ・エントリと、いくつかの一時的な使用エントリ（temporal use entry）と、一時的な使用エントリを対応するデータ・エントリへとデータ書込みの際に更新する手段と、１）書込み動作中にキャッシュから少なくとも１つの一時的な使用エントリを読み取り、２）少なくとも１つの一時的な使用エントリが低使用頻度としてマークしたデータ・エントリを識別し、３）識別したデータ・エントリへと新しいデータを書込む手段とを含む。データ・エントリへのデータ書込みの際に一時的な使用エントリを更新する手段が、１）非参照データを低使用頻度としてマークし、２）参照データを高使用頻度としてマークすることが好ましい。本発明の好ましい実施形態において、部分的に上位レベルのメモリとキャッシュとの間のインタフェースとして役立つバッファが、データを参照または非参照としてマークするために使用される。しかしながら、当業者によって知られているように、データのフェッチ状況またはプリフェッチ状況（または、参照状況または非参照状況）は、様々な方法で追跡することができる。
【００１８】前述のように、参照データは、機能ユニットがデータを必要とするためにフェッチされたデータであり、非参照データは、単にプリフェッチされたデータである。
【００１９】前述のキャッシュ構造は、従来技術のキャッシュ構造に追加の支援論理機構をほとんど必要とせず、さらに必要なデータがキャッシュ内に保持されることを保証しながらキャッシュ汚染を減少させるはたらきをする。
【００２０】本発明の以上その他の重要な利点および目的はさらに詳しく説明され、あるいは添付した説明、図面、および特許請求の範囲から明らかになるであろう。
【００２１】本発明の例示的な現在の好ましい実施形態を図面に示す。
【００２２】
【発明の実施の形態】図３は、キャッシュ汚染を減少させるための好ましい方法３００を示す。方法３００は、キャッシュに書き込むときに非参照データを低使用頻度（あるいは低近時使用頻度、less recently used）としてマークするステップ３０２、３０４と、キャッシュに書き込むときに参照データを高使用頻度（あるいは高近時使用頻度、more recently used）としてマークするステップ３０２、３０６とを含む。ｎウェイのセット・アソシエーティブ・キャッシュ（n-way set-associative cache）内の１「集合（set）」のデータ・エントリのうち１つのエントリに新しいデータ値を書き込む場合に、修正したデータ・セット内の他のデータ値の使用状況も更新する必要がありうる（３０８）。キャッシュからデータ値をフェッチする際、その使用状況が高使用頻度に更新される。キャッシュへと新しいデータを書き込むとき、新しいデータは、低使用頻度としてマークされたデータに上書きされる。データという語は、この説明において包括的な意味で使用され、データ（すなわち、特定のデータ値）と命令の両方を指すことに注意されたい。
【００２３】上記方法３００は、フェッチ・データの記憶にキャッシュのエントリの（ｎ－１）／ｎを残しておき、プリフェッチ・データの記憶をキャッシュのエントリの１／ｎに制限するという効果を有する。したがって、不要なプリフェッチ・データによる汚染がキャッシュの１／ｎに制限される。しかしながら、実際には、多くのプリフェッチ・データ値は、新しいデータによって上書きされる前に最終的にフェッチされるため、不要なプリフェッチ・データによる汚染がきわめて少なく、それらのフェッチの際に、それらの使用状況が最高使用頻度に格上げされ、これによりキャッシュ内の連続的な保守が保証される。
【００２４】図２に、前述の方法３００を実現するための汚染低減キャッシュ構造２００の好ましい実施形態を示す。キャッシュ構造２００は、一般に、キャッシュ２０２とバッファ２０４とを含む。キャッシュ２０２は、様々な方法で実現することができるが、いくつかのデータ・エントリ５０２、５０４、５０６、５０８といくつかの一時的な使用エントリ５１８とを含むことが好ましい。キャッシュ２０２が、ｎ個のウェイのセット・アソシエーティブ・キャッシュ（図３を参照）として実現される場合は、データ・エントリ５０２～５０８をキャッシュのｎ個のアレイ５１０、５１２、５１４、５１６間に分割することができる。一時的な使用エントリ５１８（本明細書ではしばしば「データ状況エントリ（data status entry）」と呼ばれる）は、ウェイアレイ（way array）５１０～５１６内または、より好ましくは、別個のデータ状況アレイ５２０内に保持されることがある。
【００２５】図２に示した例示的なキャッシュ２０２は、命令キャッシュであるように示され、したがって、命令がキャッシュ２０２からフェッチされるときに命令ポインタ（instruction pointer：以下、「ＩＰ」とよぶ）２０７の値でアドレス指定されることがある。あるいは、新しいデータ４００をキャッシュ２０２へと書き込むときに、バッファ２０４からバス２０３に提供されるアドレス４０２によってキャッシュ２０２をアドレス指定することができる。ＩＰ値２０７は、ＩＰジェネレータ・マルチプレクサ２０６（ＩＰＧＥＮＭＵＸ）から得られ、マルチプレクサ２０６は、適切なＩＰ値２０７を生成するために様々な入力と制御を受けることができる。当業者は、図２のキャッシュ構造２００を、本発明の原理から逸脱することなくデータの記憶、または混合した命令およびデータの記憶のために修正できることを容易に理解されよう。
【００２６】バッファ２０４は、部分的に、上位レベルのメモリ２０８（たとえば、上位レベルのキャッシュ）とキャッシュ２０２の間のインタフェースとしてはたらく。しかしながら、バッファ２０４は、他の目的に役立つこともある。たとえば、機能ユニットが機能停止してフェッチしたデータの到着が保留される場合には、フェッチしたデータをキャッシュ２０２内に記憶することなく機能ユニットに直接にバイパスすることが望ましいことがありうる。このように、キャッシュ２０２によって課される読み取り遅延または書込み遅延を発生させることなくデータを機能ユニットに提供することができる。バッファ２０４からデータをフェッチする準備をする場合には、マルチプレクサ２１０を使用して、キャッシュ２０２とバッファ２０４からデータを機能ユニットに交互に提供することができる。
【００２７】バッファ２０４が、本発明の必須部分ではなく、命令および／またはデータを「参照」または「非参照」としてマークするための何か他の方法が提供される場合には必要でないこともあることに注意されたい。たとえば、命令フェッチ・ユニットが、命令のフェッチ状況またはプリフェッチ状況を示すビットを生成し、フェッチした命令またはプリフェッチした命令と同期した待ち行列にこのビットを送ることができる。
【００２８】図４は、図２のバッファ２０４の好ましい実施形態を示す。１つの実施形態において、バッファ２０４は、データ値４００と、メモリ・アドレス４０２および参照状況４０４（たとえば、参照ビット）のテーブルとを含みうる。各データ値４００は、対応するアドレス４０２および参照状況４０４と関連付けられる。データ値の参照状況４０４は、そのフェッチ状況またはプリフェッチ状況を追跡するために使用される。したがって、たとえば、データ４００が上の方のレベルのメモリ２０８からフェッチされる結果としてデータ値４００がバッファ２０４に書込まれる場合には、参照ビット４０４を第１の状態（たとえば、論理「１」または「参照」状態）にセットすることができる。同様に、データ４００が上の方のレベルのメモリ２０８からプリフェッチされる結果としてデータ値４００がバッファ２０４に書き込まれる場合には、参照ビット４０４を第２の状態にセットすることができる。既にプリフェッチされているデータが後でフェッチされ、データがキャッシュ２０２内ではなくバッファ２０４内にある場合には、データをバッファ２０４から直接フェッチすることができる。そのようなフェッチの際、更新論理機構（update logic）４０８を使用して、にデータ値の参照ビットを更新して「参照」（すなわち、フェッチされた）状況を反映させることができる。
【００２９】あるいは、データ値（たとえば、命令）がバッファ２０４からフェッチされる場合には、バッファ２０４に記憶された参照ビット４０４を第１の状態（たとえば、論理「０」）に初期化して、そして、第２の状態（たとえば、論理「１」）に更新することができる。
【００３０】データをバッファ２０４からキャッシュ２０２に書き込むタイミングは様々な要素の影響を受けることがあるが、そのような書込みは、できるだけ早く行われるか、キャッシュ・フィル・ポート帯域幅（cache fill port bandwidth）がそれを許容するときに行われることが好ましい。バッファ２０４がオーバフローすると必要な命令が失われることがあり、失われた命令はパイプラインが機能停止している間に再びフェッチする必要がある。当該技術分野で知られているように、バッファ２０４をキャッシュ２０２に結合するバス２０３の使用を管理するバス制御論理機構を設けてもよい。
【００３１】図５は、図２のキャッシュ２０２の好ましい実施形態を示す。キャッシュ２０２は、４個のウェイのセット・アソシエーティブ・キャッシュとして示される。バッファ２０４からキャッシュ２０２にデータ値４００を書き込むために、データ値のアドレス４０２のすべてまたは一部分を使用して、キャッシュ２０２内の１集合のデータ・エントリ５０２～５０８に索引付けされる。また、これに対応する一時的な使用エントリ５１８がアドレス指定される。
【００３２】アドレス４０２をキャッシュ２０２に提示するときまたはその付近で、対応するデータ値４００が、それぞれウェイアレイ５１０～５１６のデータ入力に提示される。データ値４００を書き込む方法は、４つのイネーブル線（enable line）５３０、５３２、５３４、５３６の状況によって決定され、キャッシュの書込み中そのうちの１つだけがアクティブ（active）になる。アクティブなイネーブル線は、デコーダ５２４によって復号された一時的な使用エントリ５１８の値によって決定される。
【００３３】それぞれの一時的な使用エントリ５１８は、データ・エントリ５０２～５０８の対応する集合の一時的な使用順序を指定する。１集合のｎ個のデータ値５０２～５０８の各データ値に固有の使用状況が割り当てられ、ｎ個のデータ値の使用状況の可能な順序をすべて追跡したい場合には、一時的な使用エントリ５１８は、たとえば、ｌｏｇ₂ｎ！個のビットを含むことができ、ここで、ｎ！（ｎの階乗）は、ｎ個のデータ値が取りうる異なる順序の数である。したがって、４個のウェイのセット・アソシエーティブ・キャッシュ内の一時的な使用エントリ５１８は、５つのビットを含みうる。しかしながら、一時的な使用エントリ５１８は、一時的な使用エントリ５１８を記憶するために使われる方法に依存している他の数のビットを含みうる。様々なデータ状況の記憶方法については、この説明の後で方でより詳しく説明する。
【００３４】一時的な使用エントリ５１８からビット・パターンを読み取る際に、ビット・パターンを復号化して（５２４）、イネーブル線５３０～５３４のうちの１つにイネーブル信号を生成することができる。キャッシュ２０２が、真のＬＲＵアルゴリズムを実施する場合には、ビット・パターン５１８を復号化して、新しいデータが、アクセスしたデータ・セット４０３のうちの最低使用頻度のデータ値に常に書き込まれるようにすることができる。しかしながら、キャッシュ２０２は、また、たとえば１集合のデータ値４０３の各データ値に固有の使用状況を割り当てる「疑似（pseudo）」ＬＲＵアルゴリズムを実施することができる。たとえば、１集合の４つのデータ値のうちの２つの値に「高使用頻度」の状況を割り当て、他の２つのデータ値に「低使用頻度」の状況が割り当てることができる。そのような疑似ＬＲＵアルゴリズムは、１つの一時的な使用エントリ５１８に記憶する必要があるビットの数が少なく、したがってデータ状況アレイ５２０とキャッシュ２０２のサイズを小さくすることができることに注意されたい。しかしながら、そのようなアルゴリズムの使用は、また、本明細書で開示する新規な汚染低減技術の利点のうちの一部を軽減する傾向がある。
【００３５】本発明により、新しいキャッシュ・データを最低使用頻度のキャッシュ・データに上書きするが、典型的な従来のＬＲＵベースのアルゴリズムのようにすべての新しいキャッシュ・データ値に「最高使用頻度」の状況を割り当てるわけではないことが好ましい。より正確に言うと、「参照」の新しいデータは、最高使用頻度（または、少なくとも高使用頻度）としてキャッシュ２０２へと書き込まれ、また「非参照」の新しいデータは、最低使用頻度（または、少なくとも低使用頻度）としてキャッシュへと書き込まれる。
【００３６】使用状況のそのような選択的な割当てを達成するために、データ状況アレイ５２０から読み取ったビット・パターンを、バス５２８を介して更新論理機構５２６に提供することができる。新しいデータをキャッシュ２０２に書き込む際に、更新論理機構５２６は、バッファ２０４から対応する参照ビット４０４を受け取り、１）データ・セットの前の使用状況５１８、および／または、２）１集合のアドレス指定されたデータ値５０２～５０８のうちのどのデータ値に新しいデータを上書きすべきかの指示と組み合わせてこの参照ビット４０４を使用して、更新された使用状況を生成する。更新した使用状況は、データ状況アレイ５２０に記憶される。
【００３７】データ使用状況は、データ値がキャッシュ２０２からフェッチされるときにも更新される。使用状況は、たとえば、１）ウェイヒット信号（way hit signal）５３８～５４４を使用状況更新論理機構５２６に提供し、２）フェッチしたデータ値に対応するデータ・セット５０２～５０８の使用状況５１８を読み取り、そして、３）アクセスしたデータ・セット５０２～５０８の新しい使用状況を生成することによって更新することができ、新しい使用状況は、ウェイヒット信号５３８～５４４とアクセスしたデータ・セットの前の使用状況５１８の関数である。
【００３８】図７および図８は、２つの例示的な使用状況の更新を示す。図７において、１集合の４つのデータ・エントリは、（左から右に）最高使用頻度、最低使用頻度、第２の最高使用頻度、および第３の最高使用頻度（すなわち、集合的に古い状況７００）のそれぞれの使用状況を有するデータ値を含む。新しい「参照」データ値をこの集合のデータ値へと書き込む際に、最低使用頻度のデータ値が上書き用に選択される。上書きが完了した後（または、上書きが行われているとき）、４つのデータ・エントリの使用状況７００のパターンは、（左から右に）第２の最高使用頻度、最高使用頻度、第３の最高使用頻度、および最低使用頻度（すなわち、集合的に新しい状況７０２）に更新される。
【００３９】図８で、新しい「非参照」データ値が、図７に最初に現われていた同じ集合のデータ値に書き込まれる。この場合も、最低使用頻度データ値が上書き用に選択される。しかしながら、上書きが完了した後（または、上書きが行われている間）、（左から右に）第２の最高使用頻度、最高使用頻度、第３の最高使用頻度、および最低使用頻度（すなわち、集合的に新しい状況８０２）の４つのデータ・エントリの使用状況のパターンはそのままである。
【００４０】図７と図８に示したシナリオから、「参照」データ値は、長い期間キャッシュ２０２内に保持される可能性があり、「非参照」データ値は、特定のデータ・セット５０２～５０８に次に新しいデータが書き込まれることによって上書きされる可能性があることが分かる。参照データ値がフェッチ・データに対応し、非参照データ値がプリフェッチ・データに対応する場合は、おそらくフェッチ・データがキャッシュ２０２内に保持されプリフェッチ・データが上書きされる。実際に、プリフェッチ・データは、そのデータ・セット５０２～５０８に次に新しいデータが書き込まれる前にフェッチされる場合だけキャッシュ２０２内に保持される。
【００４１】当業者は、データ状況アレイ５２０に記憶される一時的な使用エントリ５１８を様々な代替の形式で記憶することができることを理解されよう。そのような１つの形式は、「System for Write-only Least recently-used Updates」(HP整理番号10001583-1)と題するStephen R. Undyの米国特許出願に開示されており、これらは、開示されているすべての事柄に関して引用することにより本明細書の一部をなすものとする。Undyの特許出願に開示されているように、一時的な使用順序ビット・パターン５１８の各ビットは、キャッシュのｎ個のウェイのうちの異なる２つに記憶された２つのデータ値の一時的な使用関係を指定することができる。一時的な使用順序ビット・パターン５１８がそのように記憶されるとき、状況更新論理機構５２６は、データをキャッシュ２０２からフェッチするときに、更新するビット・パターン５１８の既存の状態を最初に知ることなくビット・パターン５１８を更新することができる。
【００４２】データ状況アレイ５２０にデータを記憶するために、Undyの特許出願に開示された一時的な使用順序ビット・パターンを記憶する方法を使用する場合は、状況更新論理機構５２６を図６に示したように構成することができる。状況更新論理機構５２６が２つの部分６２４および６２６を含むように示されていることに注意されたい。第１の部分６２４は、キャッシュ２０２からデータをフェッチしたときにデータ状況アレイ５２０をどのように更新するか決定する。第２の部分６２６は、キャッシュ２０２へと新しいデータを書込むときにデータ状況アレイ５２０をどのように更新するかを決定する。また、データ状況アレイ５２０は、２つのポート（ＰＯＲＴ＿０６００とＰＯＲＴ＿１６０２）を含むことが好ましいことに注意されたい。このように、キャッシュ２０２への新しいデータの書込みに応じて、１つの一時的な使用エントリをフェッチに応じて更新し、もう１つの一時的な使用エントリを読み取り、復号し、更新することができる。
【００４３】キャッシュ２０２からデータ値がフェッチされたとき、ウェイヒット信号５３８～５４４がテーブル索引装置６１０に提供される。テーブル索引装置６１０は、１集合のイネーブル・ビット６２０（そのうちのいくつかがアサート（assert）される）と新しい一時的な使用順序６２２を生成するために使用される。テーブル索引装置６１０に提示されるウェイヒット信号５３８～５４４のそれぞれの組み合せは、アサートされたイネーブル・ビット６２０の別の部分集合を生成し、それぞれのアサートされたイネーブル・ビットは、一時的な使用エントリ５１８内の異なるビットの書込みを可能にする。
【００４４】前の一時的な使用順序５１８に対する変更を表す一時的な使用順序６２２のビットだけをデータ状況アレイ５２０に書き込む必要があり、したがって、前に参照したUndyの特許に記載されているように、適切なイネーブル・ビット６２０のアサートおよびアサート解除によって、新しい一時的な使用順序６２２のうちのどのビットが変更された可能性があるかを識別する。ＩＰアドレス２０７の値は、更新論理機構５２６がデータ状況アレイ５２０内の特定の一時的な使用エントリ５１８を更新することを要求する。
【００４５】キャッシュ２０２へと新しいデータ値４００を書き込む際に、アドレス指定された一時的な使用エントリ５１８が、復号され（５２４）、適切な参照ビット４０４と共にテーブル索引装置６０８に入力される。これと共に、復号された一時的な使用順序５１８および参照ビット４０４を使用して新しい一時的な使用順序６１６および１集合のイネーブル・ビット６１４をアドレス指定する。そして、新しい一時的な使用ビット６１６が、データ状況アレイ５２０の適切にアドレス指定されたエントリへと、データ・フェッチの後でデータ状況アレイ５２０へと書き込まれるのと同じように書き込まれる（違いは、書込みにＰＯＲＴ＿０ではなくＰＯＲＴ１を使用することである）。本発明により、一時的な使用エントリ５１８は、更新論理機構５２６に送られた参照ビット４０４が新しいキャッシュ・データが「参照」された（すなわち、データがフェッチされた）ことを示すときに最高使用頻度としてアクセスしたウェイ（way）をマークし、あるいは、参照ビット４０４データが「非参照」された（すなわち、データだけがプリフェッチされた）ことを示すときに最低使用頻度としてマークするようにアクセスしたウェイ(way)を更新する。
【００４６】ＰＯＲＴ＿１に送られるアドレス６１２が、バッファ２０４からアドレス４０２を受け取るマルチプレクサ６０４から得られることに注意されたい。マルチプレクサ６０４は、マルチプレクサ６０４のある入力に結合された待ち行列６０６と共に、データ状況アレイ５２０の読み取りおよび書込みがパイプライン方式（pipeline fashion）で実行されるときにデータ状況アレイ５２０の読み取りおよび書込みの管理の支援をする。キャッシュ２０２へと新しいデータ４００を書込む際に、データ状況５１８を更新する前にデータ状況５１８の読み取りを一般的に実行する必要がある。マルチプレクサ６０４の非待機入力を介してアドレス４０２をデータ状況アレイ５２０に送ることによって、データ状況５１８の読み取りを実行することができる。データ状況５１８の更新中に、マルチプレクサの待機入力を介してデータ状況アレイ５２０にアドレスを提供することができる。
【００４７】本明細書に本発明の例示的な現在の好ましい実施形態を詳細に説明したが、本発明の概念を他の状況で様々に実施し利用することができ、併記の特許請求の範囲が、従来技術によって制限されることを除きそのような変形を含むように解釈されるべきであることを理解されたい。

【出願人】	【識別番号】３９８０３８５８０【氏名又は名称】ヒューレット・パッカード・カンパニー【氏名又は名称原語表記】ＨＥＷＬＥＴＴ－ＰＡＣＫＡＲＤＣＯＭＰＡＮＹ
【出願日】	平成１３年９月１４日（２００１．９．１４）
【代理人】	【識別番号】１０００９９６２３【弁理士】【氏名又は名称】奥山尚一（外２名）
【公開番号】	特開２００２－１０８７０５（Ｐ２００２－１０８７０５Ａ）
【公開日】	平成１４年４月１２日（２００２．４．１２）
【出願番号】	特願２００１－２７９２３５（Ｐ２００１－２７９２３５）