JPH10504124A - ２方向セットアソシエーテイブ・キャッシュ・メモリ - Google Patents

Abstract

(57)【要約】 一実施形態では、２方向セットアソシアティブ・キャッシュ・メモリは、セット・アレイとデータ・アレイの両方を含む。データ・アレイは複数の要素を備え、これらの要素はそれぞれ、キャッシュ行を含むことができる。セット・アレイは複数のセットを備え、セット・アレイ内の各セットは、データ・アレイ内の要素に対応する。セット・アレイ内の各セットは、キャッシュ・メモリが受け取ったアドレスが、データ・アレイのそれに対応する要素に含まれるキャッシュ行に合致するかどうかを示す情報を含む。各セットに記憶されている情報は、タグと状態とを含む。タグは、データ・アレイ内の１つのキャッシュ行の参照を含む。特定のセットのタグが、キャッシュ・メモリが受け取ったアドレスに合致する場合、その特定のセットに関連付けられたキャッシュ行が、要求されたキャッシュ行である。特定のセットの状態は、その特定のセットにマップされているキャッシュ行の数を示す。

Description

【発明の詳細な説明】 ２方向セットアソシエーテイブ・キャッシュ・メモリ 発明の背景 発明の分野 本発明は、データ記憶の分野に関する。詳細には、本発明は、キャッシュ・メ モリ・サブシステムに関する。 背景 コンピュータ技術は引き続き進歩しており、マイクロプロセッサの動作速度は ますます高速になっている。このような高速マイクロプロセッサを利用するには 、データ記憶機能が、増加したこの速度に追従しなければならない。しかし、高 速メモリは非常に高価であり、このコストは、多数の現代のソフトウエア・プロ グラムが必要とするメモリの量が多いことによってさらに増大する。 高価なメモリの問題に対する１つの解決策は、キャッシュ・メモリ・サブシス テムによる解決策である。キャッシュ・メモリ・サブシステムとは、一般にシス テム・メモリ装置よりもずっと小型であるが、システム・メモリよりも著しく高 い速度で動作するメモリ装置である。キャッシュ・メモリの目的は、マイクロコ ンピュータが次に使用する情報（データであるか、それとも命令であるかにかか わらない）を含むことである。この情報は、キャッシュ・メモリが高速であるた め、マイクロプロセッサにずっと高速に返すことができる。 キャッシュ・メモリ・サブシステムの動作はそれぞれ異なるが、一般に、デー タはシステム・メモリとキャッシュ・メモリとの間でスワップされる。マイクロ プロセッサは、メモリに情報、たとえば、マイクロプロセッサが実行する命令と 命令に関係するデータのどちらかを要求するとき、所望の情報のメモリ・アドレ スをキャッシュ・メモリへ送る。キャッシュ・メモリは、その情報を含む場合、 それを示す信号をマイクロプロセッサに発行する。この信号を一般に「ヒット」 と呼ぶ。キャッシュ・メモリは次いで、要求された情報をマイクロプロセッサに 返す。したがって、マイクロプロセッサは、キャッシュ・メモリが高速であるた め、要求した情報をより高速に受け取ることができる。 しかし、キャッシュ・メモリが、マイクロプロセッサから要求された情報を含 まない場合、一般に「ミス」と呼ばれる信号がマイクロプロセッサに返される。 ミスは、マイクロプロセッサがより低速のシステム・メモリから情報を検索しな ければならないことをマイクロプロセッサに示す。別法として、キャッシュ・メ モリ・コントローラは、情報をシステム・メモリから検索し、マイクロプロセッ サに返さなければならない。どのサブシステムがシステム・メモリから情報を検 索するかにかかわらず、検索された情報はキャッシュ・メモリにも記憶される。 しかし、この情報をキャッシュ・メモリに記憶するには、キャッシュ内の他のデ ータに上書きする必要があることがある。すなわち、新しい情報が書き込まれる 位置に他の情報が含まれることがある。ある種のシステムでは、キャッシュ・メ モリの特定の位置に記憶されている情報をシステム・メモリに転送し、システム ・メモリに記憶されている情報をキャッシュ・メモリのその特定の位置に転送す ることによってこの状況が解決される。 キャッシュ・メモリが特定の位置の情報をシステム・メモリへ転送しなければ ならないかどうかは、使用されているキャッシュ方式にも依存する。たとえば、 ある種のキャッシュ方式では、キャッシュ内の情報が更新されるときにはいつで も情報がシステム・メモリへ転送される。したがって、システム・メモリから新 しい情報を検索する際、キャッシュ内の情報をシステム・メモリへ転送する必要 はない。 キャッシュ・メモリは一般に、システム・メモリよりもずっと小規模である。 したがって、キャッシュ・インデックスと呼ばれるメモリ・アドレスの一部のみ がキャッシュ・メモリのインデックスとして使用される。メモリ・アドレスの第 ２の部分は、一般に「タグ部」と呼ばれ、キャッシュ・メモリに記憶されている 情報が要求された情報であるかどうかを判定するために使用される。したがって 、複数のシステム・メモリ・アドレスがキャッシュ・メモリ内の同じスロットを 参照する。マイクロプロセッサが、すでに別のキャッシュ行によって使用されて い るキャッシュ・メモリのスロットに対応するメモリ・アドレスを要求すると、競 合が発生する。 キャッシュ・メモリ・サブシステムはしばしば、複数のキャッシュ行に分割さ れ、メモリ・アドレスのキャッシュ・インデックス部が、これらのキャッシュ行 のうちの１つに対応する。各キャッシュ行は複数のバイトを含み、マイクロプロ セッサから要求された特定のバイトは、メモリ・アドレスにおけるオフセットと して示される。システム・メモリも、しばしばキャッシュ・メモリと同じ行サイ ズに分割される。システム・メモリ内のこれらの行をデータ行と呼ぶ。 キャッシュ行の競合を解決する１つのタイプのキャッシュ・メモリ・サブシス テムは、当技術分野では直接マップ・キャッシュと呼ばれる。直接マップ・キャ ッシュでは、競合が発生すると、キャッシュに記憶されているキャッシュ行がシ ステム・メモリへ転送され、マイクロプロセッサからの要求に対応するデータ行 がキャッシュ・メモリ内のその位置へ転送される。そのようなキャッシング・シ ステムはいつかの利点を有する。第１に、キャッシュを実施するハードウェアの 複雑さが比較的簡単である。この位置のタグが要求と比較され、それらが合致す る場合、キャッシュ行がマイクロプロセッサに返され、合致しない場合、データ はシステム・メモリから検索される。 第２に、キャッシュ・メモリ・サブシステムのコストは比較的低い。この理由 は２つある。前述のように論理複雑度が低減されているため、システムのコスト が低減される。また、複雑度が低いので、キャッシュ・メモリは静的ランダム・ アクセス・メモリ（ＳＲＡＭ）セルを使用することができる。ＳＲＡＭは広く市 販されており、他の多数のタイプのメモリ・セルと比べて廉価である。 しかし、直接マップ・キャッシュは、ある種の状況の下では不適切に動作する 。たとえば、メモリ・アドレスＡとメモリ・アドレスＢが、共に、同じキャッシ ュ位置、すなわち位置Ｘを参照することとがありうる。マイクロプロセッサが最 初に、メモリ・アドレスＡを要求した場合、アドレスＡのデータは位置Ｘに記憶 される。マイクロプロセッサが次のクロック・サイクルでアドレスＢを要求した 場合、位置Ｘのデータがシステム・メモリ（アドレスＡ）に返され、アドレスＢ のデータが位置Ｘに記憶される。その場合、マイクロプロセッサによる次の要求 は、 再びアドレスＡを求めるものとなることがある。したがって、位置Ｘのデータは システム・メモリ（アドレスＢ）に返され、アドレスＡのデータは再び位置Ｘに 記憶される。したがって、マイクロプロセッサが、アドレスＡ、アドレスＢ、ア ドレスＡ、アドレスＢ、アドレスＡ、アドレスＢなどの順に要求を出した場合、 ヒット率（すなわち、キャッシュへのアクセスの総数に対するキャッシュ・ヒッ トの数）は非常に低くなる。したがって、マイクロプロセッサがアドレスＡとア ドレスＢを交互に要求すると直接マップ・キャッシュの性能が影響を受けること が分かる。 この性能上の欠点を解決する第２のタイプのキャッシュ・メモリは、２方向セ ットアソシアティブ・キャッシュ・メモリである。２方向セットアソシアティブ ・キャッシュは、共に動作する２つの直接マップ・キャッシュとみなすことので きる２つの「方向」を含む（このため、直接マップ・キャッシュを１方向キャッ シュと呼ぶこともある）。２方向キャッシュでは、競合が発生した場合、第１の 方向のキャッシュに記憶されているデータが第２の方向のキャッシュへ転送され 、新しいデータがシステム・メモリから第１の方向のキャッシュへ転送される。 したがって、両方のデータ行がキャッシュ・メモリに記憶される。したがって、 マイクロプロセッサが、前述のように、アドレスＡの要求とアドレスＢの要求と の間で連続的に切り替わる場合、各要求がキャッシュをヒットし、ヒット率が高 くなる。両方のデータ行は、第２の競合、すなわち同じ位置にアクセスする第３ の要求が発生するまでキャッシュに残る。 したがって、２方向キャッシュは、直接マップ・キャッシュの性能問題をある 程度解決することが分かる。しかし、このように性能を増大することは、いくつ かの犠牲を有する。第１に、２方向キャッシュを操作するための論理複雑度が大 きくなる。両方向の両方のキャッシュ行を監視するために追加論理機構を含めな ければならず、この論理機構は、マイクロプロセッサからの要求がキャッシュで ヒットするときには固有のデータを返さなければならない。第２に、２方向キャ ッシュは一般に、標準ＳＲＡＭではなくカスタマイズ・メモリ・セルを使用する 。したがって、キャッシュ・システムの財政上のコストが増大する。 コスト面の第３の問題は、２方向キャッシュの電力消費量が直接マップ・キャ ッシュの電力消費量よりも大きいことである。直接マップ・キャッシュがヒット が発生したかどうかを判定するためにアクセスするキャッシュ行は１つだけであ る。しかし、２方向キャッシュでは、ヒットが発生したかどうかを判定するため に両方のキャッシュ行がアクセスされ、ヒットが発生した場合は固有の行がマイ クロプロセッサに返される。したがって、２方向キャッシュは、２倍の数のキャ ッシュ行にアクセスするので、直接マップ・キャッシュの電力の２倍の電力を使 用することが分かる。 したがって、現代のマイクロプロセッサの増加した速度を利用するために高速 に動作するキャッシュ・メモリ・サブシステムを提供すると有利である。本発明 はそのような解決策を提供する。 さらに、直接マップ・キャッシュと２方向キャッシュの向上した性能との両方 の利点を有するキャッシュ・メモリ・サブシステムを提供すると有利である。本 発明は、それほど複雑ではなく、２方向キャッシュよりもコストが低く、かつ電 力使用量が低いことを特徴とするキャッシュ・メモリを提供する。本発明は、従 来型の直接マップ・キャッシュと比べて高いヒット率も実現する。 発明の概要 本明細書では２方向セットアソシアティブ・キャッシュ・メモリについて説明 する。一実施態様では、キャッシュ・メモリは、セット・アレイとデータ・アレ イの両方を含む。データ・アレイは、それぞれ、キャッシュ行を含むことができ る複数の要素を備える。セット・アレイは、それぞれ、データ・アレイ内の要素 に対応する、複数のセットを備える。セット・アレイ内の各セットは、キャッシ ュ・メモリが受け取ったアドレスが、データ・アレイの対応する要素内のキャッ シュ行に合致するかどうか（要素がキャッシュ行を含むと仮定する）を示す情報 を含む。 各セットは、タグ情報と状態情報とを含む。タグ情報は、データ・アレイ内の １つのキャッシュ行の参照である。特定のセットのタグが、キャッシュ・メモリ が受け取ったアドレスのタグ部に合致する場合、その特定のセットに関連付けら れたキャッシュ行が、要求されたキャッシュ行である。特定のセットの状態情報 は、その特定のセットにマップされているキャッシュ行の数を示す。 図面の簡単な説明 本発明を添付の図面に制限ではなく一例として図示する。図面において、同じ 参照符号は同様な要素を示す。 第１図は、本発明のコンピュータ・システムの一例の概要を示す図である。 第２図は、本発明の一実施形態におけるキャッシュ・メモリのセット・アレイ および対応するデータ・アレイを示す図である。 第３Ａ図は、本発明の一実施形態における最後に使用されたセット情報を判定 するためのビット・マップを示す図である。 第３Ｂ図は、本発明の代替実施形態における最後に使用されたセット情報を判 定する論理回路を示す図である。 第４図は、本発明の一実施形態におけるキャッシュ・メモリ・サブシステムの ブロック図である。 第５Ａ図は、第４図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 第５Ｂ図は、第４図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 第６図は、本発明の代替実施形態におけるキャッシュ・メモリ・サブシステム のブロック図である。 第７Ａ図は、第６図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 第７Ｂ図は、第６図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 第８図は、本発明の他の実施形態におけるキャッシュ・メモリ・サブシステム のブロック図である。 第９Ａ図は、第８図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 第９Ｂ図は、第８図のキャッシュ・メモリ・サブシステムを操作する際に本発 明の一実施形態が従うステップを示す図である。 詳細な説明 下記の詳細な説明では、本発明を完全に理解していただくために多数の特定の 詳細について述べる。しかし、当業者には、これらの特定の詳細なしで本発明を 実施できることが理解されよう。他の例では、本発明の態様を曖昧にしないよう に周知の方法、手順、構成要素、回路については詳しく説明しない。 第１図は、本発明のコンピュータ・システムの一例の概略図を示す。コンピュ ータ・システムは一般に、情報を伝達するシステム・バスまたはその他の通信装 置１００と、情報および命令を処理するためにバス１００に結合された中央演算 処理装置（ＣＰＵ）１０１とを備える。一実施態様では、本発明は、ＣＰＵ１０ １としてインテル（Ｉｎｔｅｌ）アーキテクチャ・マイクロプロセッサを含むが 、任意のタイプのマイクロプロセッサ・アーキテクチャを使用することができる 。一実施形態では、バス１００は、アドレス・バスと、データ・バスと、制御バ スとを含む。コンピュータ・システムは、ＣＰＵ１０１に関する情報および命令 を記憶するためにバス１００に結合されたシステム・メモリまたはランダム・ア クセス・メモリ（ＲＡＭ）１０４と、ＣＰＵ１０１に関する静的情報および命令 を記憶するためにバス１００に結合された読取り専用メモリ（ＲＯＭ）１０５と 、情報および命令を記憶するためにバス１００に結合された磁気ディスクやディ スク・ドライバなどのデータ記憶装置１０６と、コンピュータ・ユーザに情報を 表示するためにバス１００に結合された表示装置１０７と、選択された情報およ びコマンドをＣＰＵ１０１に伝達するためにバス１００に結合された英数字キー とファンクション・キーとを含む英数字入力装置１０８と、選択されたユーザ入 力情報およびコマンドをＣＰＵ１０１に伝達するためにバス１００に結合された カーソル制御装置１０９と、コンピュータ画像の視覚表現を与えるためにバス１ ００に結合されたプロッタやプリンタなどのハード・コピー装置１１１も含む。 本発明のコンピュータ・システムと共に使用される表示装置１０７は、液晶装 置でも、あるいは陰極線管でも、あるいはユーザが認識できるグラフィック画像 および英数字（漢字文字セット）を作成するのに適したその他の表示装置でもよ い。カーソル制御装置１０９によって、コンピュータ・ユーザは、表示装置１０ ７の表示画面上で視覚記号（たとえば、カーソルまたはポインタ）の二次元移動 を動的に表すことができる。所与の変位方向または変位方法の移動を表すことが できるトラックボールや、マウスや、ジョイスティックや、英数字入力装置１０ ８上の特殊キーを含め、カーソル制御装置の多数の実施態様が当技術分野におい て知られている。カーソルが、特殊キーおよびキー・シーケンス・コマンドを使 用するキーボードからの入力を介して命令し、あるいは作動させることができる ことを理解されたい。別法として、カーソルは、身体障害者向けに固有に開発さ れた装置を含め、特別に適応化されたいくつかのカーソル命令装置からの入力を 介して命令し、あるいは作動させることができる。 ＣＰＵ１０１は、ＣＰＵ１０１内の構成要素間で情報を伝達すると共に、それ らの構成要素とＣＰＵ１０１の外部の構成要素との間で情報を伝達する内部バス またはその他の通信装置１１５を含む。ＣＰＵ１０１には命令実行ユニット１１ ６も含まれる。命令実行ユニット１１６は、命令を受け取って実行し、コンピュ ータ・システム内のデータ記憶装置からデータを検索する。これらのデータおよ び命令は、システム・メモリ１０４、ＲＯＭ１０５、データ記憶装置１０６など に記憶することができる。ＣＰＵ１０１には、実行ユニット１１６によって使用 されるデータおよび命令を記憶するレベル１（Ｌ１）キャッシュ１１７も含まれ る。ＣＰＵ１０１が他の構成要素を含むが、図面を乱雑にし本発明を曖昧にする ことのないようにこれらの構成要素が図示されていないことに留意されたい。 ＣＰＵ１０１は、Ｌ２バス１１９を介してレベル２（Ｌ２）キャッシュ１１８ に結合される。Ｌ２キャッシュ１１８は、実行ユニット１１６によって使用され るデータおよび命令を記憶する追加キャッシュである。本発明の一実施形態では 、Ｌ２キャッシュ１１８はＬ１キャッシュ１１７よりも大規模であると共に低速 である。Ｌ２キャッシュ１１８は、Ｌ２キャッシュ１１８の動作を制御するＬ２ コントローラ１２０を含み、Ｌ２キャッシュ１１８に含まれるデータおよび命令 を記憶するＬ２ＲＡＭ１２１も含む。図の実施形態では、Ｌ２コントローラ１２ ０はＬ２キャッシュ１１８に含まれる。別法として、Ｌ２コントローラ１２０を ＣＰＵ１０１に含めることができる。 第１図のコンピュータ・システムが例示的なものに過ぎないことが理解されよ う。本発明のいくつかの実施態様では、コンピュータ・システムに追加プロセッ サまたはその他の構成要素を含めることができる。さらに、本発明のある種の実 施態様では、すべての前述の構成要素が必要とされるわけではなく、また、すべ ての前述の構成要素が含まれるわけでもない。たとえば、表示装置１０７または ハード・コピー装置１１１はバス１００に結合しなくてもよい。さらに、ある種 の実施態様では、構成要素を異なる方法で結合することができる。たとえば、Ｌ ２キャッシュ１１８を内部バス１１５ではなくシステム・バス１００に直接接続 することができる。 第２図は、本発明の一実施形態におけるキャッシュ・メモリのキャッシュ・イ ンデックスまたはセット・アレイ２０１と対応するデータ・アレイ２２１を示す 。セット・アレイ２０１は、２・ｎ個のデータセットを含み、データ・アレイ２ ２１は２・ｎ個の要素を含む。セット・アレイ２０１の各データ・セットは、デ ータ・アレイ２２１内の単一の要素に対応する。 図のセット・アレイ２０１は、物理的に連続する単一のアレイである。しかし 、セット・アレイ２０１は、２方向セットアソシアティブ・キャッシュとみなす ことができる。これは第２図では方向０および方向１によって示されており、各 方向はｎ個のセットを備える。キャッシュ・メモリが受け取るアドレスは、セッ ト・インデックス２０５などのセット・インデックスの部分を含む。セット・イ ンデックス２０５は、そのセットが方向０であるか、それとも方向１であるかに かかわらず、セット・アレイ２０１内の１つの特定のセットを固有に識別する。 したがって、セット・インデックス２０５のサイズ（すなわち、ビットの数）は 、セット・アレイ２０１内のセットの数によって決定される。 第２図に示したように方向０と方向１に分割した場合、方向０のセットを識別 するセット・インデックスと、方向１のセットを識別するセット・インデックス との間の差はセット・インデックスの最上位ビットである。たとえば、最上位ビ ットを含め、セット・インデックス２０５のすべてのビットが零である場合、セ ット・インデックス２０５はセット・アレイ２０１の方向０のセット１にマップ される。しかし、セット・インデックス２０５の最上位ビットが１であり、他の すべてのビットが零である場合、セット・インデックス２０５はセット・アレイ ２０１の方向１のセット１にマップされる。 したがって、セット・アレイ２０１は基本的に、直接マップ・キャッシュとし て動作できることが分かる。すなわち、セット・アレイ２０１への各セット・イ ンデックスは、セット・アレイ２０１の１つの特定のセットにマップされる。し かし、異なる方向の対応するセットにアクセスするには、セット・インデックス の最上位ビットをフリップするだけでよいことに留意されたい。したがって、た とえば方向１のセット４に関するセット・インデックスが与えられた場合、ユー ザが方向０のセット４にアクセスしたい場合は、セット・インデックスの最上位 ビットを０にフリップするだけでよい。 本発明の一実施形態では、セット・アレイ２０１内の各セットは、タグ・フィ ールドと状態フィールドとを含む。特定のセットのタグ・フィールドは、データ ・アレイ２２１の対応する要素に記憶されているキャッシュ行を識別する。たと えば、セット・アレイ２０１の方向０のセット２のタグ・フィールドは、データ ・アレイ２２１の要素２のメモリ・アドレスを示す。特定のセットのタグ・フィ ールドに記憶されている情報は、プロセッサからのメモリ・アドレス要求の一部 として受け取られる。セット・アレイ２０１内の特定のセットの状態フィールド は、下記で詳しく説明するように、セットにマップされているキャッシュ行の数 を示す。本発明の代替実施形態では、２つのセット・アレイが使用される。１つ のセット・アレイはタグ・フィールドを含み、それに対して第２のセット・アレ イは状態フィールドを含む。この実施形態については、下記で第４図を参照しな がら詳しく論じる。 当業者には、本発明の代替実施形態が追加情報を含むセット・アレイを使用で きることが理解されよう。たとえば、本発明の一実施形態では、セット・アレイ ２０１は、エラー検査に使用される各セットごとのパリティ・ビットを含み、（ たとえば、周知のＭＥＳＩプロトコルを使用して）キャッシュ行の妥当性を反映 する状況ビットも含む。 本発明の一実施態様では、セット・アレイ２０１は合計で１０２４個のセット を備える。したがって、各方向は、５１２個のセットを含み、セット・インデッ クス２０５は１０個のビットを備える。したがって、データ・アレイ２２１も１ ０２４個の要素を含む。本発明の一実施形態では、データ・アレイ２２１内の各 要素は、コンピュータ・システムの単一のキャッシュ行である。一実施態様では 、このキャッシュ行のサイズは３２バイトである。しかし、セット・アレイ、デ ータ・アレイ、キャッシュ行に関するこれらのサイズが例示的なものに過ぎず、 これらの構成要素が任意のサイズのものでよいことが理解されよう。 前述のように、セット・アレイ２０１内の各セットは、状態フィールドを含む ことができる。本発明の一実施形態では、状態フィールドは、この特定のセット にマップされているキャッシュ行の数を示す。各セット・インデックスは、１組 のセット・アレイ２０１を固有に識別する。しかし、複数のデータ行が同じセッ ト・インデックスを有することができるので、データ行がキャッシュ行としてキ ャッシュへ転送されるとき、本発明では、セット・インデックスを複数のキャッ シュ行にマップすることができる。この実施形態では、状態フィールドに関して ３つの可能な状態が存在する。この３つの状態は直接状態、対（ｐａｉｒｅｄ） 状態、借用（ｂｏｒｒｏｗｅｄ）状態である。 直接状態は、このセットには単一のキャッシュ行しかマップされていないこと を示す。すなわち、このセットに関連付けられているキャッシュ行は１つだけで ある。直接状態のセットは、借用状態と対状態のどちらかに遷移することも、あ るいは直接状態のままでいることもできる。 対状態のセットは、このセットに２つのキャッシュ行がマップされていること を示す。すなわち、このセットには２つのキャッシュ行が関連付けられている。 この状態では、一方のキャッシュ行に関連付けられた情報（すなわち、タグ、状 態、データなど）がこのセットおよび対応するデータ・アレイ要素に記憶されて いる。その場合、このセットを「一次」セットと呼ぶ。第２のキャッシュ行に関 連付けられた情報は、他方向の対応するセットおよびデータ・アレイ要素に記憶 されている。このセットを「パートナー」セットと呼ぶ。パートナー・セットは 、単に一次セットのセット・インデックスの最上位ビットをフリップすることに よってアクセスすることができる。たとえば、一次セットが方向０のセット４で ある場合、パートナー・セットは方向１のセット４である。対状態のセットは、 直 接状態へ遷移することも、あるいは対状態のままでいることもできる。 セットが借用状態である場合、このセットにはキャッシュ行はマップされてい ない。これは、下記の２つのことのうちの一方を示す。第１に、このセットは、 他方向の対応するセットによって使用することができる。すなわち、他方向の対 応するセットは対状態であり、このセットに第２のキャッシュ行がマップされて いる。第２に、他方向の対応するセットも借用状態である。これは、このセット にマップされているキャッシュ行も、あるいは他方向の対応するセット（すなわ ち、このセットのパートナー・セット）にマップされているキャッシュ行もない ことを示す。借用状態のセットは、直接状態に遷移することも、あるいは借用状 態のままでいることもできる。システム・スタートアップ時には、セット・アレ イ２０１内のすべてのセットが借用状態に初期設定される。 各一対の対応するセット（一対の対応するセットのセット・インデックスは、 最上位ビットのみが異なる）が一次／パートナー・セットの組合せであることに 留意されたい。どちらのセットが一次セットであってもよく、どちらのセットが パートナー・セットであってもよい。どちらのセットが一次セットであり、どち らのセットがパートナー・セットであるかは、セット・インデックスによって示 されるセットによって判定される。セット・インデックスによって示されるセッ トは一次セットであり、他方向の対応するセットはパートナー・セットである。 下記で詳しく論じるように、どちらのセットが一次セットであるかが、２つのセ ットのうちのどちらが最後に使用されたものかにも依存することにも留意された い。 さらに、特定のセットが対状態のときには常に、そのセットのパートナー・セ ットが借用状態であることに留意されたい。対／借用状態を使用することによっ て、２方向キャッシュが作成される。すなわち、特定のセットが対状態である場 合、そのセットは１つのキャッシュ行の情報を含み、そのパートナー・セットは 、このセットにマップされている第２のキャッシュ行の情報を含む。 したがって、２つのキャッシュ行間の競合が発生するまで、キャッシュ・メモ リが直接マップ・キャッシュとして動作することが分かる。そのような競合が発 生すると、キャッシュ・メモリは２方向セットアソシアティブ・キャッシュとし て動作する。 セット・アレイ２０１内の状態フィールドを使用することによって、要求がキ ャッシュでヒットするか、それともキャッシュをミスするかに関する予備判定を ある種の要求に対して下すことができる。プロセッサから受け取った要求が借用 状態のセットを示す場合、その要求は確実にミスする。すなわち、借用状態は、 このセットにキャッシュ行がマップされていないことを示す。したがって、この 要求のタグをセット・アレイ２０１の一次セットまたはパートナー・セットのタ グと比較する必要はない。 プロセッサからの要求が直接状態のセットを示す場合、その要求はキャッシュ でヒットすることも、あるいはミスすることもある。インデックスで示されたセ ットのタグ・フィールドをプロセッサからの要求のタグ・フィールドと比較し、 ヒットが発生するかどうかを判定しなければならない。しかし、直接状態が、こ のセットに単一の行しかマップされていないことを示しているので、パートナー ・セットを検査する必要はない。したがって、単一のセットのみのタグ・フィー ルドを、プロセッサから受け取ったアドレスのタグ・フィールドと比較する必要 がある。したがって、当業者には、セット・アレイ２０１の各セットが直接状態 と借用状態のどちらかであるとき、キャッシュが直接マップ・キャッシュとして 動作することが理解されよう。 プロセッサからの要求が対状態のセット・アレイ２０１内のセットを示す場合 、その要求はキャッシュでヒットすることも、あるいはミスすることもある。本 発明の一実施態様ではまず、この要求のタグ・フィールドが一次セット内のタグ ・フィールドと比較される。タグ・フィールドが合致する場合、一次セットに関 連付けられたキャッシュ行がプロセッサに返される。しかし、一次セットのタグ ・フィールドが要求のタグ・フィールドに合致しない場合、パートナー・セット のタグ・フィールドが要求のタグ・フィールドと比較される。パートナー・セッ トのタグと要求のタグ・フィールドが合致する場合、パートナー・セットに関連 付けられたキャッシュ行がプロセッサに返される。そうでない場合、プロセッサ にミス表示が返される。 したがって、セットが対状態のとき、そのセットとそのセットのパートナー・ セットは２方向キャッシュと同様に動作する。しかし、第２のセットが、第１の セットがミスであるときにしかアクセスされないので、２つのセットは完全に２ 方向キャッシュとして動作するわけではない。 本発明の一実施態様では、一次セットは、最後に使用された（ＭＲＵ）セット である。ＭＲＵセットは、プロセッサから最後にアクセスされたセットである。 したがって、一次セットは、下記で詳しく論じるように、一次セット−パートナ ー・セットの対のうちのどちらのセットでもよい。 第４図および第６図の実施形態では、Ｌ２キャッシュにアクセスする際にＭＲ Ｕ論理機構が使用される。ＭＲＵ論理機構（またはインディケータ）は、一次セ ット−パートナー・セットの対のうちのどちらがプロセッサからアクセスされた かを示す。第４図および第６図の実施形態では、ＭＲＵセットを一次セットと呼 び、最初に使用された（ＬＲＵ）セットをパートナー・セットと呼ぶ。プロセッ サからの要求がミスであるとき、一次セットとパートナー・セットのどちらかの キャッシュ行がシステム・メモリへ転送され、システム・メモリから来るキャッ シュ行用の自由位置が与えられる。一実施態様では、最初に使用されたキャッシ ュ行（すなわち、パートナー・セット）は、システム・メモリから来るキャッシ ュ行とスワップされるキャッシュ行である。したがって、ＭＲＵ論理機構を使用 することによって、システム・メモリへ転送すべき固有のキャッシュ行が分かる 。 第３Ａ図は、本発明の一実施形態において最後に使用されたセット情報を判定 するビット・マップを示す。第３Ａ図は、１０個の入力線と１つの出力線とを有 するビット・マップ３１０を示す。ビット・マップ３１０の１０個の入力線は、 セット・アレイ２０１のセット・インデックスの１０ビットである。したがって 、ビット・マップ３１０は、１０個の入力を用いて、１０２４個の固有の位置に アクセスすることができる。この１０個の入力が与えられた場合、ビット・マッ プ３１０は、単一ビット、すなわちＭＲＵビット３１１、すなわちビット・マッ プ３１０に入力された特定のセットに関するＭＲＵインディケータを出力する。 一実施態様では、ＭＲＵビット３１１が「０」である場合、最後に使用されたセ ットは、セット・インディケータの最上位ビットをフリップしないことによって 判定される。しかし、ＭＲＵビット３１１が「１」である場合、最後に使用され た セットは、セット・インデックスの最上位ビットをフリップすることによって示 される。たとえば、セット・インデックスは、セット・アレイ２１０内のセット を示す。ＭＲＵビット３１１が「０」である場合、そのセット・インデックスは 一次セットのインデックスである。しかし、ＭＲＵビット３１１が「１」である 場合、そのセット・インデックスはパートナー・セットのインデックスである。 第３Ｂ図は、本発明の代替実施形態において最後に使用されたセット情報を判 定する論理回路を示す。第３Ｂ図は、９つの入力線を有するビット・マップ３２ ０を示す。この９つの入力線は、プロセッサから受け取ったアドレスのセット・ インデックスの９つの最下位ビットである。セット・インデックスの最上位ビッ トは、ビット・マップ３２０からの出力と共に、従来型の排他的論理和ゲート３ ２２に入力される。次いで、排他的論理和ゲート３２２の出力が、ゲート３２２ に入力された最上位ビットではなくセット・インデックス（すなわち、ビット１ ４）の最上位ビットとして使用される。したがって、第３Ｂ図の回路の結果は、 第３Ａ図で説明したように最上位ビットをフリップするかどうかを示すのではな く実際の最上位ビットを示す。 本発明の一実施態様では、ＭＲＵ論理機構は、ビット・マップ（第３Ａ図のビ ット・マップ３１０と第３Ｂ図のビット・マップ３２０のどちらか）内の各位置 をシステム・スタートアップ時に零に設定することによって初期設定される。こ の実施形態では、ＭＲＵ論理機構は、第３Ａ図と第３Ｂ図のどちらかの論理回路 を使用して実施することができる。その場合、ＭＲＵ論理機構は、下記で詳しく 論じるように、セットが直接状態から対状態に遷移するときに更新される。 第４図は、本発明の一実施形態におけるキャッシュ・メモリ・サブシステムの ブロック図である。この実施形態では、ＭＲＵ論理機構と状態情報は共に、ＣＰ Ｕと同じ集積回路（ＩＣ）パッケージに記憶され、レベル２（Ｌ２）キャッシュ は、別のＩＣパッケージに含まれる。第４図は、ＣＰＵ４０２とＬ２キャッシュ ４０３の両方用の論理回路を示す。この２つのＩＣパッケージ間の分離は境界線 ４０１によって示されている。 ＣＰＵ４０２は、命令実行ユニット４０５と、レベル１（Ｌ１）キャッシュお よびコントローラ４０６と、ＭＲＵ論理機構４０７と、Ｌ２状態コントローラ４ ０８と、状態アレイ４０９とを含む。ＣＰＵ４０２内には、ＣＰＵ４０２の様々 な構成要素間で情報を伝達する内部バス４０４も含まれる。当業者には、論理演 算装置など、ＣＰＵ４０２の動作に必要な様々な追加構成要素もＣＰＵ４０２内 に含まれることが理解されよう。しかし、図面を乱雑にし本発明を曖昧にするこ とのないように、これらの追加構成要素は第４図には示されていない。 命令実行ユニット４０５は、コンピュータ・システム内で動作しているプログ ラムから検索された命令を実行する。この実行では、コンピュータ・システムの メモリから命令とデータの両方が検索される。実行ユニット４０５は、追加命令 またはデータを要求するときにはまず、Ｌ１キャッシュおよびコントローラ４０ ６に情報を要求する。実行ユニット４０５からの要求がＬ１キャッシュ４０６を ヒットする場合、要求された情報が実行ユニット４０５に返される。しかし、実 行ユニット４０５からの要求がＬ１キャッシュ４０６をミスする場合、Ｌ１キャ ッシュ・コントローラ４０６から受け取ったアドレスがＬ２状態コントローラ４ ０８に入力される。本発明の一実施形態では、Ｌ１キャッシュおよびコントロー ラ４０６は従来型のキャッシュ・メモリである。代替実施形態では、Ｌ１キャッ シュおよびコントローラ４０６は、本発明によるキャッシュ・メモリである。 ＭＲＵ論理機構４０７は、第３Ａ図および第３Ｂ図に示したような、ＭＲＵ情 報を提供する論理回路である。実行ユニット４０５からの要求は、Ｌ１キャッシ ュ４０６に入力されるのと同時にＭＲＵ論理機構４０７に入力され、それによっ てＬ２キャッシュ４０３内の特定のセットに関するＭＲＵ情報にＬ１キャッシュ ４０６と並列にアクセスすることができる。したがって、Ｌ１キャッシュおよび コントローラ４０６が要求のアドレスをＬ２状態コントローラ４０８に出力する のと同時に、Ｌ２状態コントローラ４０８は、上記で第３Ａ図で論じたＭＲＵビ ット３１１や第３Ｂ図で論じたビット１４などのＭＲＵ情報を得ることができる 。 Ｌ２状態コントローラ４０８は、Ｌ１キャッシュ４０６とＭＲＵ論理機構４０ ７の両方から入力を受け取る。Ｌ２状態コントローラ４０８は、ＭＲＵ論理機構 ４０７から受け取ったＭＲＵ情報と、Ｌ１キャッシュ４０６から受け取った要求 されたセット・インデックスの最下位ビットを組み合わせる。したがって、Ｌ２ 状態コントローラ４０８は、一次セット（すなわち、パートナー・セット−一次 セットの対のうちの最後に使用されたセット）のアドレスを生成する。 Ｌ２状態コントローラ４０８は状態アレイ４０９にも結合される。状態アレイ ４０９は、Ｌ２キャッシュ内の各セットごとの状態フィールドを含む。特定のセ ットに関する状態フィールドは、そのセットが直接状態であるか、それとも対状 態であるか、それとも借用状態であるかを示す。したがって、要求がＬ１キャッ シュをミスする場合、Ｌ２状態コントローラ４０８は、要求に関する一次セット の状態を判定する。したがって、セットが借用であり、したがって確実にミスす るかどうかなど予備的な情報に、Ｌ２キャッシュ４０３にアクセスせずにＣＰＵ ４０２と同じＩＣパッケージ内でアクセスすることができる。したがって、ある 種の状況の下では、Ｌ２キャッシュ４０３の別のＩＣパッケージにアクセスする 時間遅延を発生させずに実行ユニット４０５にミス表示を返すことができる。 要求がＬ１キャッシュ４０６をミスし、Ｌ２状態コントローラ４０８が、この セットが直接状態と対状態のどちらかであると判定した場合、Ｌ２キャッシュ４ ０３がアクセスされる。実行ユニット４０５からの要求されたアドレスは、Ｌ２ 状態コントローラ４０８からＬ２キャッシュ４０３に入力される。このアドレス は、アドレス４２０として示されており、３２ビットを備える。アドレス４２０ の最上位１６ビットは、実行ユニット４０５からの要求のタグ・フィールドを含 む。下記で詳しく論じるように、このタグ・フィールドを使用して、一次セット に関連付けられたキャッシュ行が要求に合致するかどうかが判定される。上記で 第２図を参照して説明したように、アドレス４２０のビット［１４：５］は、セ ット・アレイ４２２のインデックスである。アドレス４２０の最下位５ビットは 、データ・アレイ４２４のキャッシュ行内のオフセットである。すなわち、アド レス４２０のビット［４：０］は、ヒットの場合にはまず、要求されたキャッシ ュ行内のどのバイトを実行ユニット４０５に返すべきかを示す。 アドレス４２０に基づく一次セットがアクセスされ、そのセットのタグがタグ 比較論理機構４２６に入力される。タグ比較論理機構４２６によって、一次セッ トのタグとアドレス４２０から得たタグ・フィールドが比較される。次いで、こ の比較の結果が制御論理機構４２８に入力される。アドレス４２０のビット［１ ４：５］がデータ・アレイ４２４にも入力されることに留意されたい。したがっ て、データ・アレイ４２４の出力は、アドレス４２０によって示されたセットに 関連付けられたキャッシュ行である。タグ比較論理機構４２６が、一次セットの タグとアドレス４２０のタグが合致することを示す場合、制御論理機構４２８に よって、ヒット表示がデータ・アレイ４２４からのキャッシュ行と共にＣＰＵ４ ０２に返される。 しかし、タグ比較論理機構４２６が、タグが合致しないことを示す場合、制御 論理機構４２８は、一次セットの状態が直接であるか、それとも対であるかに応 じて、パートナー・セットを検査し、あるいはミスを返す。一次セットの状態は 、Ｌ２状態コントローラ４０８からの入力として受け取られる。一次セットの状 態が直接である場合、制御論理機構４２８はミス表示を返す。しかし、一次セッ トの状態が対である場合、制御論理機構４２８は、最初に使用された（ＬＲＵ） セットのセット・インデックスを使用してセット・アレイ４２２とデータ・アレ イ４２４の両方にアクセスする。前述のように、これは、セット・インデックス の最上位ビット、たとえばアドレス４２０のビット［１４］をフリップすること によって行われる。ＬＲＵセットのセット・アレイ４２２から得たタグは、タグ 比較論理機構４２６によって、アドレス４２０から受け取ったタグと比較される 。次いで、この比較の結果が制御論理機構４２８に出力される。タグ比較論理機 構４２６がヒットを示す場合、ＬＲＵセットに関連付けられたデータ・アレイ４ ２４のキャッシュ行が、ヒット表示と共にＣＰＵ４０２に返される。しかし、タ グ比較論理機構４２６がミスを示す場合、制御論理機構４２８はＣＰＵ４０２に ミス表示を返す。 本発明の一実施形態では、制御論理機構４２８が、Ｌ２キャッシュ４０３が必 要とするデータ行をシステム・メモリから検索する。代替実施形態では、Ｌ１キ ャッシュおよびコントローラ４０６が、必要なデータ行をシステム・メモリから 検索する。他の代替実施形態では、実行ユニット４０５が、必要なデータ行をシ ステム・メモリから検索する。 第５Ａ図および第５Ｂ図は、第４図のキャッシュ・メモリ・サブシステムを操 作する際に本発明の一実施形態が従うステップを示す。まずステップ５０５で、 ＣＰＵの実行ユニットから、情報を求める要求が発行される。本発明の一実施態 様では、この要求は、第４図に示したアドレス４２０などのアドレスの形のもの である。ステップ５０６で、実行ユニットからのこの要求を使用してＬ１キャッ シュがアクセスされ、ステップ５０８でＭＲＵ論理機構がアクセスされる。第５ Ａ図に示したように、ステップ５０６とステップ５０８は並行に実行される。 Ｌ１キャッシュおよびコントローラは、実行ユニットから要求を受け取ると、 ステップ５１０で、要求がＬ１キャッシュでヒットするかどうかを判定する。要 求がＬ１キャッシュでヒットする場合、ステップ５１２で、要求されたキャッシ ュ行がＬ１キャッシュから実行ユニットに返され、それによって要求が満たされ る。しかし、要求がＬ１キャッシュをミスする場合、Ｌ２状態コントローラはス テップ５１５で、実行ユニットからの要求によって示された一次セットが借用状 態であるかどうかを判定する。一次セットは、ステップ５０８で得たＭＲＵ情報 によって修正された、実行ユニットから受け取ったセット・アドレスによって示 されるセットである。パートナー・セットは、一次セット・アドレスの最下位ビ ット、およびフリップされた一次セット・アドレスの最上位ビットを使用して示 されるセットである。したがって、一次セットは最後に使用されたセットであり 、パートナー・セットは最初に使用されたセットである。 一次セットが借用状態である場合、Ｌ２状態コントローラはただちに、実行ユ ニットからの要求がＬ２キャッシュをミスすることを知る。したがってステップ ５２０で、要求されたデータ行がシステム・メモリから検索される。次いでステ ップ５２５で、システム・メモリから検索されたデータ行が実行ユニットに返さ れ、Ｌ２キャッシュにも返される。次いでステップ５３０で、一次セットに対応 する、Ｌ２キャッシュ内のデータ・アレイ行にキャッシュ行が記憶され、一次セ ットの状態とパートナー・セットの状態が共に直接状態に更新される。本発明の 一実施態様では、キャッシュ行はＬ１キャッシュにも記憶される。 ステップ５１５に戻ると、一次セットが借用状態ではない場合、Ｌ２状態コン トローラはステップ５３５で、一次セット・アドレスと、一次セットが直接状態 であるか、それとも対状態であるかのＬ２キャッシュへの表示の両方を出力する 。次いでステップ５４０で、Ｌ２キャッシュ内のタグ比較論理機構が、一次セッ トのタグと要求されたアドレスのタグが合致するかどうかを判定する。タグが合 致 する場合、ステップ５４２で、要求がＬ２キャッシュをヒットし、一次セットに 対応するキャッシュ行がＬ２キャッシュ内のデータ・アレイから実行ユニットに 返される。 しかし、ステップ５４０でタグが合致しない場合、Ｌ２キャッシュ内の制御論 理機構は第５Ｂ図のステップ５４４で、Ｌ２状態コントローラから受け取った入 力に基づいて一次セットが直接状態であるかどうかを判定する。一次セットが直 接状態である場合、ステップ５４５で、要求されたデータ行がシステム・メモリ から検索される。ステップ５５０で、このデータ行が実行ユニットに返され、パ ートナー・セットにも記憶される。本発明の一実施態様では、データ行はＬ１キ ャッシュにも記憶される。次いでステップ５５５で、ＭＲＵ論理機構が、パート ナー・セットが最後に使用されたセットであることを示すように更新される。次 いでステップ５６０で、一次セットの状態が対状態に更新され、パートナー・セ ットが借用状態に更新される。 本発明の一実施形態では、第３Ａ図に示したように、ＭＲＵ論理機構は、１０ 個の入力線を有するビット・マップを含む。この実施形態では、ＭＲＵ論理機構 は、一次セットのセット・インデックスの１０ビットによって決定されたビット ・マップ内の位置に「１」を記憶し、パートナー・セットのセット・インデック スの１０ビットによって決定されたビット・マップ内の位置に「０」を記憶する ことによって、パートナー・セットがＭＲＵセットであることを示すように更新 される（ステップ５５５）。本発明の代替実施形態では、ＭＲＵ論理機構は、第 ３Ｂ図に示したように、９つの入力線を有するビット・マップを含む。この実施 形態では、ＭＲＵ論理機構は、一次セットのセット・インデックスの最下位９ビ ットによって決定されたビット・マップ内の位置にあるビットをフリップするこ とによって、パートナー・セットがＭＲＵセットであることを示すように更新さ れる。 ステップ５４４に戻ると、一次セットの状態が直接でも借用でもない場合、一 次セットは対状態でなければならない。一次セットのタグはすでにステップ５４ ０で、要求のタグには一致しないことが分かっている。したがって、タグ比較論 理機構はステップ５７５で、パートナー・セットのタグが要求のタグに合致する かどうかを判定する。ステップ５７５で要求がパートナー・セットをヒットする （すなわち、タグが合致する）場合、ステップ５８０で、パートナー・セットに 関連付けられたキャッシュ行がＬ２キャッシュから実行ユニットに返される。次 いでステップ５８５で、ＭＲＵ論理機構が、前のＬＲＵセットが現在はＭＲＵセ ットであることを示すように更新される。ＭＲＵ論理機構は、上記でステップ５ ５５で論じたように更新される。 ステップ５７５に戻ると、要求がパートナー・セットをミスする（すなわち、 タグが合致しない）場合、ステップ５９０で、要求されたデータ行がシステム・ メモリから検索される。このデータ行は次いでステップ５９５で、実行ユニット とＬ２キャッシュの両方に返される。一実施態様では、データ行はＬ１キャッシ ュにも返され記憶される。Ｌ２キャッシュはこのデータ行をパートナー・セット に記憶する。次いでステップ５８５で、ＭＲＵ論理機構が、前のＬＲＵセットが 現在はＭＲＵセットであることを示すように更新される。 第６図は、本発明の代替実施形態におけるキャッシュ・メモリ・サブシステム のブロック図である。第６図に示した実施形態は第４図に示した実施形態に類似 しているが、セット・アレイ内の各セットごとの状態情報は、ＣＰＵ６０２と同 じＩＣパッケージではなく、Ｌ２キャッシュ６０３と同じＩＣパッケージに記憶 される。第６図は、境界線６０１で分離されたＣＰＵ６０２とＬ２キャッシュ６ ０３を示す。 ＣＰＵ６０２は、内部バス６０４と、命令実行ユニット６０５と、Ｌ１キャッ シュおよびコントローラ６０６とを含む。これらの構成要素の動作については、 上記で第４図を参照しながら論じた。ＣＰＵ６０２は、第４図のＭＲＵ論理機構 ４０７と同様なＭＲＵ論理機構６０７も含む。しかし、ＭＲＵ論理機構６０７は 、Ｌ１キャッシュ６０６から受け取ったセット・インデックスの最上位ビットを フリップするかどうかを判定し、必要に応じて、一次セットのインデックスを得 るために最上位ビットをフリップする。したがって、ＭＲＵ論理機構６０７から Ｌ２キャッシュ６０３に入力されるアドレス６２０のセット・インデックス部分 は、一次セット（すなわち、最後に使用されたセット）のセット・インデックス を含む。上記で第４図のアドレス４２０に関連して論じたように、第６図のアド レス ６２０は３２ビットを備える。ビット［３１：１５］はアドレスのタグ・フィー ルドであり、ビット［１４：５］はセット・インデックスであり、ビット［４： ０］はキャッシュ行のオフセットである。 セット・アレイ６２２の各セットは、タグ・フィールドと状態フィールドとを 含む。セット・アレイ６２２はアドレス６２０のビット［１４：５］によって示 され、インデックスで示されたセットのタグ情報および状態情報はそれぞれ、タ グ比較論理機構６２６および状態比較論理機構６２７に入力される。タグ比較論 理機構６２６は、インデックスで示されたセットのタグをアドレス６２０のタグ と比較し、結果を制御論理機構６２８に出力する。同様に、状態比較論理機構６ ２７は、インデックスで示されたセットの状態を判定し、この情報を制御論理機 構６２８に出力する。状態比較論理機構６２７は、このセットが直接状態である か、それとも対状態であるか、それとも借用状態であるかを示す。 制御論理機構６２８は、入力として、タグ比較論理機構６２６からタグ比較の 結果を受け取り、状態比較論理機構６２７からインデックスで示されたセットの 状態を受け取る。この情報に基づいて、制御論理機構６２８は、実行ユニット６ ０５からの要求がＬ２キャッシュ６０３をヒットするか、それともミスするかを 判定する。 制御論理機構６２８は、タグ比較論理機構６２６からの結果と、状態比較論理 機構６２７から受け取ったインデックスで示されたセットの状態に応じて、ヒッ ト表示とミス表示のどちらかを実行ユニット６０５に返す。インデックスで示さ れたセットの状態が対である場合、一次セットとパートナー・セットの両方に制 御論理機構６２８からアクセスする必要があることに留意されたい。両方のセッ トが制御論理機構６２８からアクセスされるかどうかと、実行ユニット６０５か らヒット表示が返されるか、それともミス表示が返されるかについて、下記で第 ７Ａ図および第７Ｂ図を参照しながら詳しく論じる。 本発明の一実施形態では、制御論理機構６２８が、必要なデータ行をシステム ・メモリから検索する。代替実施形態では、Ｌ１キャッシュおよびコントローラ ６０６が、必要なデータ行をシステム・メモリから検索する。他の代替実施形態 では、実行ユニット６０５が、必要なデータ行をシステム・メモリから検索する 。 第７Ａ図および第７Ｂ図は、第６図のキャッシュ・メモリ・サブシステムを操 作する際に本発明の一実施形態が従うステップを示す。最初にステップ７０５で 、プロセッサ上の実行ユニットから要求が発行される。情報を求めるこの要求は 、データ行またはキャッシュ行を求める要求であり、プロセッサが使用する命令 情報またはデータ情報を含むことができる。本発明の一実施態様では、この要求 はアドレスである。 実行ユニットからの要求は、ステップ７０６でＬ１キャッシュに入力されると 共に、ステップ７０８でＭＲＵ論理機構に入力される。ステップ７０８でアクセ スされたＭＲＵ論理機構は、後述のように本発明によって必要に応じて使用され るＬ２キャッシュ内のインデックスで示されたセットに関する一次セット（すな わち、最後に使用されたセット）を示す。Ｌ１キャッシュは、実行ユニットから 要求を受け取ると、ステップ７１０で、要求がＬ１キャッシュでヒットするかど うかを判定する。要求がＬ１キャッシュでヒットする場合、ステップ７１２で、 要求されたキャッシュ行がＬ１キャッシュから実行ユニットに返される。 要求がＬ１キャッシュをミスする場合、ステップ７１５で、タグ比較論理機構 が、一次セットのタグと要求のタグが合致するかどうかを判定する。これは、前 述のように、実行ユニットからの要求のタグ・フィールドをＬ２キャッシュのセ ット・アレイ内の一次セットのタグ・フィールドと比較することによって行われ る。タグが合致する場合、ステップ７２０で、要求されたキャッシュ行がＬ２キ ャッシュから実行ユニットに返される。 しかし、タグが合致しない場合、ステップ７２５で、Ｌ２キャッシュ内の制御 論理機構が、一次セットが借用状態であるかどうかを判定する。一次セットが借 用状態である場合、要求はＬ２キャッシュをミスする。したがって、要求された データ行はステップ７３０で、コンピュータ・システムのシステム・メモリから 検索される。このデータ行はステップ７３５で、実行ユニットとＬ２キャッシュ の両方に返される。システム・メモリから検索されたデータ行は、実行ユニット からの最初の要求によって示されたセット（すなわち、一次セット）に対応する Ｌ２キャッシュのデータ・アレイに記憶される。次いでステップ７４０で、一次 セットの状態が直接状態に更新され、パートナー・セットの状態も直接状態に更 新される。本発明の一実施態様では、データ行はＬ１キャッシュおよびコントロ ーラにも記憶される。 ステップ７２５に戻ると、一次セットが借用状態ではない場合、第７Ｂ図のス テップ７４５で、一次セットが直接状態であるかどうかに関する判定が下される 。一次セットが直接状態である場合、ステップ７５０で、要求されたデータ行が システム・メモリから検索される。このデータ行はステップ７５５で、実行ユニ ットに返され、Ｌ２キャッシュ内のパートナー・セットに記憶される。一実施態 様では、データ行はＬ１キャッシュにも記憶される。次いでステップ７６０で、 一次セット用のＭＲＵ論理機構が、パートナー・セットが最後に使用されたセッ トであることを示すように更新される。ＭＲＵ論理機構は、上記で第５Ａ図およ び第５Ｂ図を参照しながら論じたように更新される。次いでステップ７６５で、 一次セットの状態が対状態に更新され、パートナー・セットの状態が借用状態に 更新される。 ステップ７４５に戻ると、パートナー・セットは、直接状態でも、あるいは借 用状態でもない場合、対状態でなければならない。すでにステップ７１５で、要 求が一次セットをヒットするかどうかに関する判定を下したので、ステップ７７ ０で、要求がパートナー・セットをヒットするかどうか（すなわち、パートナー ・セットのタグと要求のタグが合致するかどうか）に関する判断を下す。タグが 合致する場合、ステップ７７５で、要求されたキャッシュ行がＬ２キャッシュか ら実行ユニットに返される。次いでステップ７８０で、ＭＲＵ論理機構が、パー トナー・セットが最後に使用されたセットであることを示すように更新される。 ＭＲＵ論理機構は、上記で第５Ａ図および第５Ｂ図を参照しながら論じたように 更新される。 しかし、タグが合致しない場合、ステップ７８５で、要求されたデータ行がシ ステム・メモリから検索される。このデータ行はステップ７９０で、実行ユニッ トに返されると共に、Ｌ２キャッシュ内のパートナー・セットに記憶される。一 実施態様では、データ行はＬ１キャッシュにも記憶される。次いでステップ７８ ０で、ＭＲＵ論理機構が、前述のように、パートナー・セットが最後に使用され たセットであることを示すように更新される。 第８図は、本発明の他の実施形態におけるキャッシュ・メモリ・サブシステム のブロック図である。第８図のキャッシュ・メモリ・サブシステムは、第６図の システムに類似しており、境界線８０１で分離されたＣＰＵ８０２とＬ２キャッ シュ８０３とを含む。ＣＰＵ８０２は、内部バス８０４と、命令実行ユニット８ ０５と、Ｌ１キャッシュおよびコントローラ８０６とを含む。これらの構成要素 の動作は、上記で第４図および第６図を参照しながら論じたとおりである。しか し、ＣＰＵ８０２が、第６図のＭＲＵ論理機構６０７と同様なＭＲＵ論理機構を 含まないことに留意されたい。第８図の実施形態では、最後に使用されたセット は、下記で詳しく論じるように、必要に応じてキャッシュ行をスワップされた一 次セットである。 Ｌ２キャッシュ８０３は、第６図のＬ２キャッシュ６０３に類似している。Ｌ ２キャッシュ８０３は、第６図のＬ２キャッシュ６０３と同様に、セット・アレ イ８２２と、データ・アレイ８２４と、タグ比較論理機構８２６と、状態比較論 理機構８２７と、制御論理機構８２８とを含む。タグ比較論理機構８２６は、要 求８２０のタグ・フィールドとセット・アレイ８２２のインデックスで示された セットのタグ・フィールドを比較し、結果を制御論理機構８２８に出力する。同 様に、状態比較論理機構８２７は、セット・アレイ８２２内のインデックスで示 されたセットの状態を判定し、結果を制御論理機構８２８に出力する。第８図の 実施形態では、一次セットは、ＭＲＵ論理機構に基づく修正なしの、実行ユニッ ト８０５からの要求によって示されたセットである。 Ｌ２キャッシュ８０３は、制御論理機構８２８、セット・アレイ８２２、デー タ・アレイ８２４に結合されたスワップ論理機構８３０も含む。第８図の実施形 態では、最後に使用されたセットは常に、対状態のセットに維持される。したが って、ビット・マップなどの追加ＭＲＵインディケータなしでも、どのセットが 最後に使用されたセットであるかを判定することができる。 スワップ論理機構８３０は、スワップ制御論理機構８３１と、セット・アレイ ・バッファ８３２と、データ・アレイ・バッファ８３３とを含む。セット・アレ イ・バッファ８３２は従来型のバッファであり、１組のセット・アレイ８２２に 記憶されるタグ・フィールドおよびその他のデータ用の一次記憶位置である。デ ータ・アレイ・バッファ８３３は従来型のバッファであり、データ・アレイ８２ ４の要素に記憶されるキャッシュ行用の一次記憶位置である。スワップ制御論理 機構８３１は、セット・アレイ８２２およびデータ・アレイ８２４から得た情報 の、１つのセットから他のセットへの転送を制御する。スワップ論理機構８３０ は、制御論理機構８２８からの指示に応じて２つのセットを切り替える。これは 、２つの状況で行われる。第１の状況は、インデックスで示されたセットが直接 状態であるが、要求がキャッシュをミスするときである。この状況では、要求さ れた線は、システム・メモリから検索されＬ２キャッシュ８０３のパートナー・ セットに記憶される。次いで、下記で第９Ａ図および第９Ｂ図を参照しながら詳 しく論じるように、パートナー・セットとインデックスで示されたセットがスワ ップされる。同様に、インデックスで示されたセットが対状態であり、要求が一 次セットをミスする場合、キャッシュ行がシステム・メモリからパートナー・セ ットに検索され、スワップを行わなければならず、あるいは要求がパートナー・ セットをヒットし、その場合、パートナー・セットが最後に使用されたセットで あると、スワップが行われる。このことについては、下記で第９Ａ図および第９ Ｂ図を参照しながら詳しく論じる。 第９Ａ図および第９Ｂ図は、第８図のキャッシュ・メモリ・サブシステムを操 作する際に本発明の一実施形態が従うステップを示す。最初にステップ９０５で 、プロセッサ上の実行ユニットから要求が発行される。本発明の一実施態様では 、この要求はアドレスの形のものである。ステップ９０８で、この要求に基づい て、Ｌ１キャッシュがアクセスされる。ステップ９１０で、要求がＬ１キャッシ ュでヒットする場合、ステップ９１２で、要求されたキャッシュ行がＬ１キャッ シュから実行ユニットに返される。 しかし、要求がＬ１キャッシュをミスする場合、その要求はＬ２キャッシュへ 送られ、ステップ９１５で、タグ比較論理機構が、要求のタグと一次セットのタ グが合致するかどうかを判定する。タグが合致する場合、要求はＬ２キャッシュ をヒットし、ステップ９１７で、要求されたキャッシュ行がＬ２キャッシュから 実行ユニットに返される。しかし、タグが合致しない場合、Ｌ２キャッシュは、 一次セットの状態を調べる。 ステップ９２０で、状態比較論理機構が、一次セットが借用状態であるかどう かを判定する。一次セットが借用状態である場合、ステップ９２５で、システム ・メモリからデータ行が検索される。次いでステップ９３０で、データ行が実行 ユニットおよびＬ２キャッシュに返される。一実施態様では、データ行はＬ１キ ャッシュにも記憶される。Ｌ２キャッシュは、このデータ行を一次セットに記憶 し、ステップ９３５で、一次セットとパートナー・セットの両方の状態を直接に 更新する。 ステップ９２０に戻ると、一次セットが借用状態ではない場合、第９Ｂ図のス テップ９４０で、状態比較論理機構が、このセットが直接状態であるかどうかを 判定する。一次セットが直接状態である場合、ステップ９４５で、システム・メ モリからデータ行が検索される。データ行は次いでステップ９５０で、実行ユニ ットに返され、Ｌ２キャッシュ内のパートナー・セットにも記憶される。一実施 態様では、データ行はＬ１キャッシュにも記憶される。次いでステップ９５５で 、Ｌ２キャッシュ内のスワップ論理機構が、一次セットとパートナー・セットと の間で行をスワップする。次いでステップ９６０で、一次セットの状態が、対状 態に更新され、パートナー・セットの状態が借用状態に更新される。したがって 、データ行をシステム・メモリからパートナー・セットに検索し、次いでパート ナー・セットと一次セットをスワップすることによって、一次セットは最後に使 用されたキャッシュ行を含むことがわかる。 スワップ制御論理機構は、データ・アレイ内の２つのデータ行ならびにセット ・アレイの関連するタグ（およびその他のパリティ・ビット）を切り替えること によって、一次セットの行とパートナー・セットの行をスワップする。セット・ アレイに記憶されている状態情報が切り替えられないことに留意されたい。この スワッピングは、様々な従来型の方法のうちの任意の方法で行うことができる。 たとえば、本発明の一実施態様では、スワップすべき一次セットのデータ・アレ イおよびセット・アレイ内の情報が、２つのアレイからスワップ制御論理機構内 のバッファへ転送される。次いで、スワップすべきパートナー・セットのデータ ・アレイおよびセット・アレイ内の情報が一次セットのアレイへ転送される。次 いで、スワップ・バッファに記憶されている情報がパートナー・セットのアレイ へ転送され、それによって一次セットとパートナー・セットに含まれるデータお よび情報が切り替えられる。 ステップ９４０に戻ると、一次セットが直接状態ではない場合、ステップ９６ ５で、タグ比較論理機構が、要求のタグとパートナー・セットのタグが合致する かどうかを判定する。タグが合致する場合、ステップ９７０で、要求されたキャ ッシュ行がパートナー・セットから実行ユニットに返される。次いでステップ９ ７５で、Ｌ２キャッシュ内のスワップ制御論理機構が、一次セット内の行とパー トナー・セット内の行をスワップする。したがって、一次セットは対状態のまま で、パートナー・セットは借用状態のままであり、一次セットは、最後に使用さ れたキャッシュ行を含む。 ステップ９６５に戻ると、タグが合致しない場合、ステップ９８０で、要求さ れたデータ行がシステム・メモリから検索される。ステップ９８５で、要求され たデータ行が、システム・メモリから検索され、実行ユニットに返され、Ｌ２キ ャッシュ内のパートナー・セットに記憶される。一実施態様では、データ行はＬ １キャッシュにも記憶される。ステップ９７５で、Ｌ２キャッシュ内のスワップ 制御論理機構が一次セットの行とパートナー・セットの行をスワップする。 したがって、第９Ａ図および第９Ｂ図に示した実施形態では、要求が一次セッ トとパートナー・セットの両方をミスすると、要求されたデータ行が、システム ・メモリから検索され、インデックスで示されたセットのパートナー・セットに 記憶され、次いで一次セットのキャッシュ行とパートナー・セットのキャッシュ 行がスワップされることがわかる。したがって、一次セットは対状態のままで、 パートナー・セットは借用状態のままであり、一次セットは最後に使用されたキ ャッシュ行を含む。 本発明の代替実施形態では、Ｌ２キャッシュは、システム・メモリから得たデ ータ行を、前述とは異なりパートナー・セットではなく、直接、一次セットに記 憶する。データ行を直接、一次セットに記憶することによって、Ｌ２キャッシュ は、一次セットとパートナー・セットをスワップする必要がなくなる。 上記の説明は、要求がＬ１キャッシュをミスするがＬ２キャッシュでヒットす るときのＬ１キャッシュの更新については論じていないが、Ｌ２キャッシュでの キャッシュ行ヒットを、ＣＰＵの命令実行ユニットに返すだけでなくＬ１キャッ シュに記憶することもできることに留意されたい。当業者には理解されるように 、この状況でＬ１キャッシュが更新されるかどうかは、使用されるキャッシュ方 式に依存する。 上記の説明が、Ｌ１キャッシュとＬ２キャッシュの両方を有するコンピュータ ・システムについて論じたものであることに留意されたい。しかし、単一のキャ ッシュしか有さないシステムが本発明のキャッシュ・メモリを使用できることを 理解されたい。 同様に、上記の説明は、Ｌ２キャッシュで実施される本発明のキャッシュ・メ モリについて説明したものである。しかし、本発明の教示が任意のレベルのキャ ッシュに適用でき、特にＬ２キャッシュに限らないことが理解されよう。たとえ ば、Ｌ１キャッシュしか有さないシステムが前述のように実施される。ただし、 ２つのキャッシュではなく１つのキャッシュのみをヒットするように、からの要 求が検査される。当業者には、本発明をＬ１キャッシュで使用する際、アドレス をキャッシュに入力するのと同時に、ＭＲＵインディケータからＭＲＵ情報を得 ることはできないことが理解されよう。 さらに、上記の説明は、システム・メモリからデータ行を検索する必要がある ときにシステム・メモリへキャッシュ行を転送するキャッシュ・メモリについて 説明している。しかし、他のキャッシュ方式を本発明の趣旨および範囲内で使用 することができる。たとえば、本発明の一実施形態では、キャッシュ・メモリ内 でキャッシュ行を更新するときには常に、システム・メモリ内でもキャッシュ行 を更新することができる。したがって、あるキャッシュ位置へデータ行が転送さ れるとき、システム・メモリがすでにキャッシュ行のコピーを含んでいるので、 システム・メモリへのキャッシュ行の転送は行われない。 したがって、本発明のキャッシュ・メモリ・サブシステムは、直接マップ・キ ャッシュと２方向セットアソシアティブ・キャッシュの両方の利点を与える。直 接マップ・キャッシュのより低い電力消費量および論理複雑度が、２方向セット アソシアティブ・キャッシュのより高いヒット率と組み合わされる。また、本発 明の一実施形態では、キャッシュを含むＩＣパッケージにアクセスせずに、ある 種の要求がキャッシュをミスすることを判定することができ、そのためミス表示 応答速度が向上する。 また、当業者には、上記の説明が２方向キャッシュとして動作できるキャッシ ュについて論じたものであるが、他の多方向キャッシュも本発明の趣旨および範 囲内であることが理解されよう。たとえば、本発明の教示を従来型の２方向キャ ッシュに適用し、それによって、２方向キャッシュの利点と４方向キャッシュの 利点を組み合わせた４方向キャッシュを作成することができる。 当業者には、上記の説明を読んだ後に本発明の多数の変更および修正が理解さ れようが、一例として図示し説明した特定の実施形態が本発明を制限するものと みなすべきものではないことを理解されたい。したがって、特定の実施形態の詳 細の参照は、請求の範囲を制限するものではなく、請求項は基本的に、本発明に 必須とみなされる特徴のみを記載したものである。 したがって、２方向セットアソシアティブ・キャッシュ・メモリについて説明 した。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)， ＡＭ，ＡＴ，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，Ｃ Ａ，ＣＨ，ＣＮ，ＣＺ，ＣＺ，ＤＥ，ＤＥ，ＤＫ，ＤＫ ，ＥＥ，ＥＥ，ＥＳ，ＦＩ，ＦＩ，ＧＢ，ＧＥ，ＨＵ， ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，Ｌ Ｒ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＮ，ＭＷ，ＭＸ ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ， ＳＧ，ＳＩ，ＳＫ，ＳＫ，ＴＪ，ＴＭ，ＴＴ，ＵＡ，Ｕ Ｇ，ＵＺ，ＶＮ

Claims (1)

1. 【特許請求の範囲】 １．データ・アレイが複数の要素を備えているとき、入力アドレスがキャッシ ュ・メモリ・システムのデータ・アレイに含まれるかどうかを示すキャッシュ・ インデックスにおいて、 それぞれが前記データ・アレイの要素の一つに対応する、複数のデータセット を備え、 前記複数のデータセットの第１のセットが、第１のタグと第１の状態とを有し 、 前記第１のタグが、前記データ・アレイの前記複数の要素の第１の要素に記憶 されている第１のキャッシュ行のＩＤを示す第１の複数のビットを備え、 前記第１の状態が、前記第１のセットにマップされているいくつかのキャッシ ュ行を示す第１の状態インデックスを備え、前記各キャッシュ行が、前記データ ・アレイの要素に対応することを特徴とするキャッシュ・インデックス。 ２．直接状態である前記第１の状態が、単一の行が前記第１のセットにマップ されていることを示す請求項１に記載のキャッシュ・インデックス。 ３．対状態である前記第１の状態が、第１の行と第２の行が共に前記第１のセ ットにマップされていることを示す請求項１に記載のキャッシュ・インデックス 。 ４．借用状態である前記第１の状態が、前記第１のセットにマップされている 行がないことを示す請求項１に記載のキャッシュ・インデックス。 ５．さらに、第２のセットを備え、その第２のセットは前記複数のセットのう ちの１つであり、その第２のセットが、第２の複数のビットを備える第２のタグ と第２の状態とを含むことを特徴とする請求項１に記載のキャッシュ・インデッ クス。 ６．前記第１のセットに第１の行と第２の行が共にマップされている場合、前 記第１の複数のビットが前記第１の行を参照し、前記第２の複数のビットが前記 第２の行を参照することを特徴とする請求項５に記載のキャッシュ・インデック ス。 ７．前記キャッシュ・インデックスが、タグ・アレイと状態アレイとを備える ことを特徴とする請求項１に記載のキャッシュ・インデックス。 ８．中央演算処理装置（ＣＰＵ）を有するコンピュータ・システムで使用され るキャッシュ・メモリ・サブシステムにおいて、 複数の要素を有するデータ・アレイと、 セット・アレイとを備え、前記セット・アレイが、 それぞれ、前記データ・アレイの単一の要素に対応し、第１のセットが、第 １のタグ・フィールドと第１の状態フィールドとを含み、第２のセットが、第２ のタグ・フィールドと第２の状態フィールドとを含む、複数のセットと、 前記第１のセットが、前記第２のセットよりも後に前記ＣＰＵからアクセス されたかどうかを示す、前記第１のセットに対応する最後に使用されたセット（ ＭＲＵ）インディケータとを含むことを特徴とするキャッシュ・メモリ・サブシ ステム。 ９．前記ＭＲＵインディケータが、ビット・マップであることを特徴とする請 求項８に記載のサブシステム。 １０．前記ビット・マップが、入力として、前記セット・アレイの第３のセッ トを固有に識別する第２の複数のビットを前記ＣＰＵから受け取り、前記第１の セットが最後に使用されたセットであるか、それとも前記第２のセットが最後に 使用されたセットであるかを示すＭＲＵビットを出力することを特徴とする請求 項９に記載のサブシステム。 １１．さらに、排他的論理和ゲートを備え、前記ビット・マップが、入力とし て、第２の複数のビットを前記ＣＰＵから受け取り、前記第２の複数のビットが 、第３の複数のビットの最上位ビットを除く前記第３の複数のビットのすべての ビットであり、前記第３の複数のビットが、前記セット・アレイの第３のセット を固有に識別し、前記単一のビットおよび前記最上位ビットが、前記排他的論理 和ゲートに入力され、前記排他的論理和ゲートが、前記第１のセットが最後に使 用されたセットであるか、それとも前記第２のセットが最後に使用されたセット であるかを示すＭＲＵビットを出力する請求項９に記載のサブシステム。 １２．前記第１の状態フィールドおよび前記第２の状態フィールドがそれぞれ 、３つの可能な状態のうちの１つの状態であり、前記３つの可能な状態が、直接 状態、借用状態、対状態である請求項８に記載のサブシステム。 １３．前記ＭＲＵインディケータが最初、前記第１のセットが最後に使用され たセットであることを示し、かつ前記ＭＲＵインディケータが、前記第１の状態 フィールドが前記対状態のとき、前記ＣＰＵから前記キャッシュ・サブシステム への要求に応答して、前記第２のセットが最後に使用されたセットであることを 示すように修正される請求項１２に記載のサブシステム。 １４．前記ＭＲＵインディケータが最初、前記第１のセットが最後に使用され たセットであることを示し、かつ前記ＭＲＵインディケータが、前記第１の状態 フィールドが前記直接状態であり前記キャッシュ・サブシステムへの要求が前記 第１のセットに配置されていないとき、前記要求に応答して、前記第２のセット が最後に使用されたセットであることを示すように修正される請求項１２に記載 のサブシステム。 １５．前記ＭＲＵインディケータおよび前記ＣＰＵが、同じ集積回路パッケー ジに含まれる請求項８に記載のサブシステム。 １６．前記第１の状態フィールドおよび前記第２の状態フィールドが、前記集 積回路パッケージに含まれる請求項１５に記載のサブシステム。 １７．中央演算処理装置（ＣＰＵ）を有するコンピュータ・システムで使用さ れるキャッシュ・メモリ・サブシステムにおいて、 複数の要素を有するデータ・アレイと、 セット・アレイとを備え、前記セット・アレイは、 前記データ・アレイの単一の要素にそれぞれが対応し、第１のセットが第１ のタグ・フィールドと第１の状態フィールドとを含み、第２のセットが第２のタ グ・フィールドと第２の状態フィールドとを含む、複数のセットと、 第１のキャッシュ行と第２のキャッシュ行をスワップし、そのスワップが、 最初に前記データ・アレイの第１の要素に配置されていた第１のキャッシュ行を 前記データ・アレイの第２の要素に入れ、最初に前記第２の要素に配置されてい た第２のキャッシュ行を前記第１の要素に入れるスワップ制御装置とを備えるこ とを特徴とするキャッシュ・メモリ・サブシステム。 １８．前記第１の状態フィールドおよび前記第２の状態フィールドがそれぞれ 、３つの可能な状態のうちの１つであり、その３つの可能な状態は、直接状態、 借 用状態、対状態である請求項１７に記載のサブシステム。 １９．前記スワップ制御装置が、前記第１の状態フィールドが前記対状態であ るとき、前記ＣＰＵから前記キャッシュ・サブシステムへの要求に応答して前記 スワッピングを実行する請求項１８に記載のサブシステム。 ２０．前記スワップ制御装置が、前記第１の状態フィールドが前記直接状態で あり前記ＣＰＵから前記キャッシュ・サブシステムへの要求が前記第１のセット に配置されていないとき、前記要求に応答して前記スワッピングを実行する請求 項１８に記載のサブシステム。 ２１．システム・メモリとキャッシュ・メモリ・サブシステムとを含むコンピ ュータ・システムの中央演算処理装置（ＣＰＵ）から要求されたデータ行を前記 ＣＰＵに返す方法であって、前記キャッシュ・メモリ・サブシステムはレベル１ （Ｌ１）キャッシュとレベル２（Ｌ２）キャッシュと有し、前記Ｌ２キャッシュ は複数のキャッシュ行を有し、その複数のキャッシュ行の各キャッシュ行は、前 記複数のキャッシュ行のうちの他のキャッシュ行のパートナー・キャッシュ行で ある前記方法が、 （ａ）前記データ行が、前記Ｌ１キャッシュに記憶されているかどうかを判定 するステップと、 （ｂ）前記キャッシュ行が前記Ｌ１キャッシュに記憶されている場合、前記デ ータ行を前記ＣＰＵに返すステップと、 （ｃ）前記データ行に対応する前記Ｌ２キャッシュ内のキャッシュ行が借用状 態であるかどうかを判定するステップと、 （ｄ）前記システム・メモリから前記データ行を検索し、前記データ行に対応 する前記Ｌ２キャッシュ内の前記キャッシュ行に前記データを記憶するステップ と、 （ｅ）前記キャッシュ行の状態を直接状態に更新するステップと を含むことを特徴とする方法。 ２２．さらに、 前記Ｌ２キャッシュ内の前記キャッシュ行が、前記ＣＰＵから要求されたデー タ行であるかどうかを判定するステップと、 前記データ行に対応する前記Ｌ２キャッシュ内の前記キャッシュ行が直接状態 であるかどうかを判定するステップとを含むことを特徴とする請求項２１に記載 の方法。 ２３．さらに、前記キャッシュ行を前記Ｌ２キャッシュから前記ＣＰＵに返す ステップを含むことを特徴とする請求項２２に記載の方法。 ２４．さらに、 前記システム・メモリから前記データ行を検索し、前記データ行に対応する前 記Ｌ２キャッシュ内の前記キャッシュ行に前記データを記憶するステップと、 前記データ行を前記ＣＰＵに返すステップと、 前記キャッシュ行の状態を対状態に更新するステップと、 前記パートナーセットキャッシュ行の状態を借用状態に更新するステップとを 含むことを特徴とする請求項２２に記載の方法。 ２５．さらに、 一次セットおよびパートナー・セットのうちの最初に使用されたセット内のキ ャッシュ行が、要求されたデータ行であるかどうかを判定するステップと、 前記最初に使用されたセットを最後に使用されたセットになるように更新する ステップとを含むことを特徴とする請求項２２に記載の方法。 ２６．さらに、前記キャッシュ行を前記Ｌ２キャッシュの前記最初に使用され たセットから前記ＣＰＵに返すステップを含むことを特徴とする請求項２５に記 載の方法。 ２７．さらに、前記システム・メモリから前記データ行を検索し、前記データ 行に対応する前記Ｌ２キャッシュ内の前記キャッシュ行に前記データ行を記憶す るステップを含むことを特徴とする請求項２５に記載の方法。 ２８．前記最初に使用されたセットを更新するステップが、前記最初に使用さ れたセットと前記最後に使用されたセットをスワップすることを含むことを特徴 とする請求項２５に記載の方法。 ２９．コンピュータ・システムであって、 バスと、 前記バスに結合された中央演算処理装置（ＣＰＵ）と、 キャッシュ・メモリ・サブシステムとを備え、前記キャッシュ・メモリ・サブ システムが、 複数の要素を有するデータ・アレイと、 前記データ・アレイの単一の要素にそれぞれが対応し、第１のセットが第１ のタグ・フィールドと第１の状態フィールドとを含み、第２のセットが第２のタ グ・フィールドと第２の状態フィールドとを含む複数のセットを含むセット・ア レイとを含み、 前記コンピュータ・システムはさらに、 最後に使用された（ＭＲＵ）セット、すなわち前記第１のセットと前記第２の セットのどちらかを維持する手段を備えるコンピュータ・システム。 ３０．前記第１のセットに対応し、前記第１のセットが前記第２のセットより も後に前記ＣＰＵからアクセスされたかどうかを示すＭＲＵインディケータを、 前記維持手段が備えることを特徴とする請求項２９に記載のシステム。 ３１．第１のキャッシュ行と第２のキャッシュ行をスワップし、前記スワッピ ングが、最初に前記データ・アレイの第１の要素に配置されていた第１のキャッ シュ行を前記データ・アレイの第２の要素に入れ、最初に前記第２の要素に配置 されていた第２のキャッシュ行を前記第１の要素に入れるスワップ制御装置を、 前記維持装置が備えることを特徴とする請求項２９に記載のシステム。 ３２．前記第１の状態フィールドおよび前記第２の状態フィールドがそれぞれ 、３つの可能な状態のうちの１つであり、前記３つの可能な状態が、直接状態、 借用状態、対状態であることを特徴とする請求項２９に記載のシステム。