JP2008016033A - 階層テーブルを管理するための方法およびコンピュータ・システム - Google Patents

Abstract

【課題】キャッシュが親のエントリを子のエントリと同期させるのに使用されるバッファ・インデックス機構を提供。
【解決手段】低レベル・テーブル中の複数のエントリをバッファされたインデックス値を備えた高レベル・テーブル中の単一のエントリにリンクする。このインデックス値は、高レベル・エントリが置き換えられもしくは無効化されるごとにインクリメントする。インデックス値の複数のセットが維持され、一つのセットを使い切ると他の一つのセットで処理を続行することができる。古い（ダーティな）セットからのインデックス値を備えた全ての対応する低レベルのエントリがそれからスクラブされる。その間、新しいエントリが新しい（クリーンな）セットから構築される。スクラビングはバックグラウンドで行うことができ、中断することができ、テーブルのリクエスト・サービス時間に悪影響を与えないような任意の時間に再開することができる。
【選択図】図１

Description

本発明はコンピュータのデザインに関し、特に、テーブルのリクエストのサービス時間に悪影響を与えず、過度のスペースやロジック（論理）を必要とせずに階層的なコンピュータ・テーブルにおけるエントリのコヒーレンシーを維持するのを可能にするトランスレーション・キャッシュを作ることができるようにする、コンピュータ中のアレイの階層構成に関する。

コンピュータでは、トランスレーション・キャッシュなどの動的な高速のアクセス・テーブル（アレイ）のデザインが、フラットな（単一レベルの）構成ではなく階層的な（マルチレベルの）構成を通じてしばしば向上される。マルチレベル方式は、おそらくは異なる幾つかのテーブルにおける特定のレベルと関連したエントリを、ある特定の高レベルのエントリと関連した低レベルのエントリごとに特徴付ける。高レベル（親）のエントリの意図は、それらの対応する低レベル（子）のエントリの全てに共通する情報を共有することである。これはスペース（チップ領域はマイクロプロセッサのデザインの、おそらく最も重要な構成要素である）を節約するだけでなく、多くの共通の機能が、多くの子のエントリの代わりに単一の親のエントリ上で実行できるようにし、これによって性能を改良し、デザインを簡単にすることができる。
なお、以下でＩＢＭはインターナショナル・ビジネス・マシーンズ・コーポレーションの登録商標である。ここで使用される他の名称も同社または他の会社の登録商標、商標または製品名であり得る。

ＩＢＭコンピュータ・システムおよび他のコンピュータ・システムであって、システムが階層テーブル中のエントリのコヒーレンシーを維持することができるキャッシュ・エントリを有する前記システムにおいて有用な階層構成を設けることによって、従来技術の欠点を克服し、あわせて更なる効果が得られる。

低レベル・テーブル中において複数のエントリは、高レベル（親）のエントリを備えることでそれらの対応する低レベル（子）のエントリの全てに共通する情報を共有することができるように、バッファされたインデックス（索引）を備える高レベル・テーブル中の一つのエントリにリンクされる。このインデックス値は、階層レベルのエントリが置き換えられ、もしくは無効化されるごとにインクリメントする。インデックス値の複数のセットは、一つのセットが使い尽くされるときにその複数のセットのうちの他の一つのセットで処理が続行できるように維持される。このインデックス管理で規定されるのは、具体的には「現在」、「ダーティ」および「クリーン」のインデックス・セットといったインデックス・セットの管理タイプを含むインデックス値を低レベルのエントリが有することである。これらのインデックス・セットを使用すると、新しいセットから新しいエントリが構築される間に、古い／ダーティなセットからのインデックス値を備える、対応する低レベルのエントリがスクラブ(scrub)され／無効化されるのを許容する。

このように、親のエントリを子と同期させるようにバッファされたインデックスを用いる階層構成を備え、そして子のエントリのバックグラウンド無効化（即ち、アレイの新しいリクエストが到来するなら、無効化を中断し、そのリクエストが満たされた後その無効化を再開すること）を許容するキャッシュ・デザインを本発明者は開発したと云える。キャッシュは簡単であり、スペース効率がよく、多様な状況に拡張可能である。このキャッシュは低レベルのテーブル中の（複数の）エントリを、バッファされたインデックス値を備えた高レベルのテーブル中の一つのエントリにリンクするのを利用する。このインデックス値は高レベルのエントリが入れ替えられもしくは無効化される（従ってその対応する低レベルのエントリとの関係を断つ）ごとにインクリメントする。「現在」、「ダーティ」、および「クリーン」のインデックス・セットを含む、インデックス値の複数のセットが維持される。一つのセットが使用し終わると、他の一つのセットで以って続行することができる。古い（ダーティな）セットからのインデックス値を備えた全ての対応する低レベルのエントリがスクラブ（無効化）されることができ、一方で新しいエントリが新しい（クリーンな）セットから構築される。スクラブすること即ちスクラビングは、高レベルのテーブル中の新しいエントリを低レベルのテーブル中の古いエントリと関連付けるというコヒーレンシー・リスクを防止する。このスクラビングはバックグラウンド（即ちテーブルの複数の処理リクエスト相互間）で行うことができ、中断でき、テーブルのリクエスト・サービス時間に悪影響を与えないような任意の時間に再開することができる。

エントリのコヒーレンシーを維持する本発明の方法は、実施の際、少しのビット（a few bits）しか必要とせず、使用の際そのテーブルの特性に合致させる必要に応じて拡張することができる。

追加の特徴および効果は本発明の技法を通じて理解される。本発明の他の実施例および側面をここで詳細に説明するが、特許請求の範囲に示した発明の一部と理解されたい。本発明をその効果および本発明の特徴とともに、よりよく理解するためにその説明および図面に言及する。

テーブル中の親のエントリで実行され得るバックグラウンド機能の例は無効化である。本発明がなければ、そのような親に関連する子のエントリが同様に無効化される。このように子を無効化するプロセスは面倒かもしれない。例えば、フォアグラウンド（即ち、無効化が完了するまでそのアレイの全ての新規なリクエストを遅らせる）でのアレイのエントリごとに徹底的にサーチするか、複雑さもしくは得ようとするチップ領域の点で高価な特別のハードウエア（CAMアレイなど）を必要とするか、あるいはその同じ親と関連する子のエントリを維持するように二重にリンクされたリストのような構造のための多くのスペースと関連ロジックとを必要とするなど、子を無効化するプロセスは面倒かもしれない。

この発明は、テーブルのリクエストのサービス時間に悪影響を及ぼさずに、もしくは過度のスペースやロジックを必要とせずに、階層コンピュータ・テーブル中のエントリのコヒーレンシーを維持するという問題を解決する。従来の解決策は、シリコン・チップ領域もしくは電力(power)（ＣＡＭアレイなど）の点で非常に高価なものにつくか、あるいは必要以上に複雑（二重にリンクされたリストなど）である。

本発明とみなせる主題を抽出し、特許請求の範囲に明示する。本発明の前記および他の目的、特徴および効果は添付図面と関連して以下の詳細な説明から明らかである。

ここで図面についてもっと詳細に云えば、図1では記憶システムおよびマイクロプロセッサを有し、またしばしばキャッシュ・アレイを含むコンピュータ・システムが、値を持つエントリからなる階層テーブルを含む階層記憶エレメントのアレイで以って構成され得ることが分かる。ここで簡単のために、二つのテーブルＨおよびＬがあり、Ｈが高レベル・エントリから、Ｌが低レベル・エントリからなると仮定しよう。現実には、もっと多くのレベル、あるいはもっと多くのテーブルがある場合、または一つのテーブルしかない（従って全てのエントリがそれを共用（シェア）する）場合を取り扱うことができよう。L中の各（有効な）エントリはＨ（いわば、その親）中の一つのエントリを指し示す。大きい値となり得る階層スキームの場合、Ｌ中の複数の子がＨ中の同じ親を指し示すことができると更に仮定できよう。Ｌ中に或るエントリを探し当てるというのは、しばしばＨ中にその対応する親を探し当てることになる。この一部となるかもしれないのは、Ｈ中で同じ親を共用するＬ中の全ての子に共通する情報を得ることであるが、もっと重要なことは、Ｌ中のエントリが、その対応する親が有効でないなら、最早有効でないかもしれないことである。図1のＨおよびＬの例を参照されたい。

図２で、Ｈは４個のエントリＡないしＤを含み、Ｌは８個のエントリａないしｈを含む。各エントリは有効なビット（１が有効、０が無効を表す）を含む。Ｌ中の各エントリはＨ中の親のエントリを指し示す。例えば、ｄがＢを指し示し、ｇがＤ（図示のとおり）を指し示す。Ｈ中のエントリは、もしもそれらの有効なビット・セット（この場合、ＢおよびＣが有効）を有するなら有効である。Ｌ中のエントリは、もしも下記の条件の両方を満たすなら有効である。（i）それらが有効なビット・セットを有すること、ならびに（ii）Ｈ中の有効なエントリを指し示すこと。例えば、ｇ（その有効なビット・セットを有するが有効でないDを指し示す）のようにa が無効である（その有効なビット・セットを有していない）が、ｄが有効である（その有効なビットがセットされ、そしてそれが有効なBを指し示す）。

H中のあるエントリＯは意図した（ハードウエアまたはソフトウエアの直接的なアクション）理由から、あるいは意図しない（不作為による経年変化 aging out）理由から無効になり得る。L中の対応する子は、H中の有効なエントリをもはや指し示さないので、無効になるというのが一つの副作用（side effect）である。しかしＯが新しい有効なエントリNと交換されるなら、Ｏの子全てがいまやその親でないNを指し示すという問題を有する。L中でＯの対応する子の全てを手動で通り抜けて無効化する（スクラビングと称するプロセス）よりも、単純なインデックス・スキームを用いることができ、そこでは或る数のインデックス・ビットIがHおよびL中の各エントリに加えられる。これらのインデックス・ビットは２＾Ｉ個の固有値をコード化できる。Ｈ中の各エントリはそのインデックスを０で開始し、新しいエントリが古いエントリを上書きするときに２＾Ｉ−１までインクリメントすることができる。Ｌ中の対応する子のエントリはそれらのインデックス値をその同じ値にセットさせている筈である。その結果、これらのインデックス値をＨ中のそれらの親のインデックス値に比較することによってこれらの子の有効性をチェックすることができ、これらのインデックス値を同じ値にセットするのを確保することができるであろう。図３はこのインデックス・スキームを示す。

図３では、HおよびLはエントリ毎に２ビットのインデックス・フィールドを含むように拡張される。あるエントリがLにインストールされると、そのインデックス値はH中のその親の値にセットされる。親のエントリがH中で入れ替えられると、なおもそれをポイントするL中の子が、一致するインデックスを有さなくなるようにその対応するインデックスがインクリメント（増分）される。これはL中のエントリの有効性のために以下の第３の基準を加える。（iii）これらのインデックス値はH中のそれらの親のエントリのインデックス値に等しい。例えば、エントリcは最早有効なエントリではない。何故ならばそれがその有効なビット・セットを有するが、それがH中の有効なエントリを指し示すのに、そのインデックス値がその親のインデックス値とは異なるからである。他方、dはなおも有効である。何故ならばそのインデックス値がその親Bのインデックス値と同じだからである。

同期を強化するためのインデックスについて新規なことはない。その一つの重要な実装の詳細は、全ての可能なインデックス値が循環してゆくときに生じるコヒーレンシーの複雑さにある。これは、H中の新しいエントリがL中の古いエントリと同じインデックス値（即ち、なおも以前の親を指し示しているその親からの古い子がまだ存在している間に完全にひと回り循環された親のエントリのためのインデックス値）を共有するように関連付けられるというリスクを招来する。実際にも、これはH中のエントリが無効にされ、そしてインデックス・フィールドがなかったときはいつも直面していた同じ現象である。インデックスは必要なスクラビングの頻度を単に下げるだけである。

インデックスは基本的な時間対空間のパフォーマンスのトレードオフを招来する。（エントリ・サイズに関して）効率的にするには、I（インデックス・ビットの数）をできるだけ小さくすることが必要である。また（オーバーヘッドに関して）効率的にするには、スクラビングを少なくするためにIをできるだけ大きくする必要がある。一般的には（キャッシュのような）動的アレイをその中に最近のデータを見つける機会を増すために（エントリに関して）できるだけ大きくする必要があるが、一方でエントリを見つけるアクセス時間を改善するためには（サイズに関して）動的アレイをできるだけ小さくする必要がある。これら両方の目的はIを小さくすることによって達成され、その結果、最適化の主たる関心はスクラビング・オーバーヘッドである。

一般性を失うことなく定義すると、H中のスロットごとにその特定のスロットに新しいエントリがインストールされる（即ち実在するエントリを一つ少ないインデックス値と置き換える）ときはいつも、インデックス・ビットが、０で始まり、２＾Ｉ−１まで１ずつインクリメントしそこから０に戻る符号のない２進数を構成する。インデックス値が０に循環して戻ってくるときのコヒーレンシー・リスクを取り扱うために、本発明では、バッファされたインデックス（即ちインデックス値の複数のセットを維持する）技法を提案する。図４を参照すると、新しいフィールドが（インデックス・セット）が加えられる。これは全ての意図および目的からインデックス・フィールドの追加の上位ビットとして機能する。即ち。インデックス・フィールドが循環するとき、その対応するインデックス・セット・フィールドがインクリメントされる。またL中のエントリの有効性のために以下の第４の基準が加えられる。（iv）それらのインデックス・セットがH中のそれらの親のインデックス・セットに等しい。例えば、図４ではｄが有効でなく（その親Cとは異なるインデックス・セットのため）、ｅが有効ではない（Ｃとは異なるインデックスのため）が、ｆは有効（インデックス・セットおよびインデックスがＣのと等しい）である。

前述のことに付随する最後の詳細はそのインデックス・セットの管理にある。これらは３種類のインデックス・セットである。
１．現在 − 現在インデックス・セットはH中のエントリにより現在使用されているものである。
２．ダーティ − ダーティ・インデックス・セットは使用中でないものであり、かつ有効なビット・セットを有するL中のエントリをそれに関連付けてしまっているかも知れないものである。
３．クリーン − クリーン・インデックス・セットは使用中でないものであり、かつ有効なビット・セットを有するL中のどのエントリもそれに関連づけていないものである。

全てのインデックス・セットはクリーンから開始するが、それは現在のセットとして識別されているものである。現在セットが使用済みになったら、それはダーティとなり、インデクシングはクリーン・セットが次の現在セットになって再開する。使用中ではないが、ダーティ・セットはスクラビングされることができ、斯してそれらをクリーン・セットに変換する。ダーティ・セットが必要とされない間にこのスクラビングが行われている限り（バックグラウンド・スクラビング）、コヒーレンシーがそのシステムへのあからさまな割り込みなしに維持される。もし現在セットが使用済みになり、そしてそれが新しいセットに切り替わる必要があり、すべての他のセットがダーティであればスクラビングは遅らせることができない。これはパフォーマンスにマイナスのインパクトを与える。スクラビングが行われている間（フォアグラウンド・スクラビング）、リクエストを留保するからである。

簡単のため、一つのインデックス・セット・ビット（即ち、２つのインデックス・セット）をとることができる。前述のとおり、インデックス・フィールドは全ての実際的な目的のため上位ビットとしてこのインデックス・セットを導入することができる。それからH中のエントリあたり一つの追加ビットを必要とする。即ち他のインデックス・セット（例えば現在でないセット）の状態で１はダーティである（そしてスクラビングが必要）ことを意味し、０はクリーンである（現在セットが使い切ったときにすぐ使用できる）ことを意味する。一般に、より多くのインデックス・セット・ビット、例えばS個を有する実施例の場合、そのダーティ・インデックス・セットに追従するためにS個のビットを必要とするであろう。例えば、この新しいフィールドは、このセットおよび現在セット（非排他的）の間のこれらの全てのインデックス・セットがダーティとみなされて、第１のダーティ・インデックス・セットを識別できるであろう。

図５は１インデックス・セット・ビットの実施例を示す。ここではインデックス・セット・ビットが上位ビットとしてインデックス・フィールド中に導入されている。Hを見ると、２個のダーティ・インデックス・セット、すなわちBに対し１、およびDに対し１というのがある。Bの現在のインデックス・セット（０）が幾つかの有効な値（すなわち１０および１１）を有するが、Dのは使い切っている。Dが新しいエントリと入れ替わるとき、それはダーティ・インデックス・セットを持つDを尚もポイントする任意のエントリをL中でスクラブするのを完了させるのが必要となろう。この場合、ｇがまさにそのようなエントリであり、その有効ビットが１であり、それがDをポイントし、そのインデックス・セットが０である（Dに対する現在のインデックス・セットではない）。ｇは新しいエントリがDに対し書き込まれる前にその有効ビット・セットを０しておくべきであったろう。これに対し、ｈがBのダーティ・インデックス・セットをポイントするとしても、新しいエントリがBに対し書き込まれることができよう。何故ならBの現在インデックス・セットにまだ余地があるからである。Bがインデックス・セットを切り替える前にｈがその有効ビット・セットを０にすることが必要なだけである。

実施例における考察
インデックス・ビットの数は、インデックス・セット・ビットの数と同様、スクラビングの頻度および効率、テーブルのアクティビティ・レートを含む多くの要素に依存しがちである。いずれかのフィールドを１ビットだけ増やすと、親および子の両方のエントリが１ビットだけ大きくなるという負担を伴いながらも、スクラビング相互間に要する時間量が倍になる（平均で）。更に、インデックス・セット・フィールドを１ビットだけ増やすと、（ダーティなインデックス・セットを管理するために）親のエントリを追加ビット分、大きくするが、スクラビング・プロセスのより多くの粒度（きめ細かさ）を許容し、もっと効果的なスクラビングを生じることができる。

バックグラウンド・スクラビングを実行する直接的な方法（実施例のHおよびLのテーブルの例を挙げて）では、動作していない期間中に、ダーティ・インデックス・セットを持つエントリを求めてHが探索される。一つのエントリが見つかると、ダーティ・インデックス・セットを持つ対応する子のエントリを求めてLで探索され、そのようなエントリが無効にされる。一旦Lが探索され、全ての適宜の子のエントリが無効にされるると、そのダーティ・インデックス・セットがクリーンにマークされ、ダーティ・インデックス・セットを持つ更なるエントリを求めてH中の探索を再開することができる。このバックグラウンド・スクラビング中に現れる何らかの必要なアクティビティ（HおよびLの一方又は両方のリクエスト）は不必要な遅延なしにそのリクエストを実行するためにスクラビングを中断し、そのリクエストが実行された後にスクラビングが中断したところから再開することができる。

本発明の機能はソフトウエア、ファームウエア、ハードウエアまたはその組み合わせで実行することができる。
一例として、本発明の一つ又は複数の特徴は、例えば一つ若しくはそれ以上のコンピュータ・プログラムやコンピュータ使用可能媒体で実現することができる。この媒体は、例えば本発明の機能を提供するためのコンピュータ読み取り可能なプログラム・コード手段を含んでいる。本発明のプログラムはコンピュータ・システムの一部として含まれていてもよいし、別個に販売されてもよい。

更に、コンピュータ（マシン）によって読み取り可能な少なくとも一つのプログラム記憶装置であって、本発明の機能を実行するコンピュータによって実行可能な命令群からなる少なくとも一つのプログラムを（有体物として）含むものを提供することもできる。

ここで開示する処理の流れは単なる一例である。個々に開示したこれらの処理の流れまたは手順（または動作）の多くの変形例が本発明の趣旨から逸脱することなく可能である。例えば、諸手順を異なる順序で実行したり、加除修正したりすることができる。これらの変形例の全てが特許請求の範囲に示す発明の一部と考えられたい。

本発明の好適な実施例を説明してきたが、今日および将来の当業者が、特許請求の範囲内に属する種々の改良を行えることが理解できよう。これらの特許請求の範囲は記載した発明の適正な保護を維持するように解釈されたい。

本発明の階層テーブルを有するコンピュータ・システムを示す図である。 階層テーブルのデザインを備えたトランスレーション・キャッシュを有する図１のコンピュータに於けるコンピュータ・キャッシュ・アレイの、高レベルのテーブルＨと、低レベルのテーブルＬとを有する階層テーブルの一例を示す図である。 エントリごとの２ビット・インデックス・フィールドを含むように拡張された図１および図２のＨおよびＬを示すインデキシング・デザインを示す図である。 インデックス・フィールドの追加の上位ビットとして機能し、かつ加えられてきた新しいインデックス・セット・フィールドを示す図である。 上位ビットとしてインデックス・フィールドにインデックス・セット・ビットが組み込まれ、上位のＨが２つのダーティ・インデックス・セット、Ｂのために１、Ｄのために１を有する、１インデックス・セット・ビットの実施例を示す図である。

Claims (13)

1. アレイの階層テーブルを管理する方法であって、
   値を持つエントリを含み、高レベル・テーブルおよび少なくとも一つの低レベル・テーブルを含む階層テーブル中の前記エントリのコヒーレンシーを維持するために、現在インデックス、ダーティ・インデックス、クリーン・インデックスを含む前記エントリのための複数のインデックス値を有するバッファを備えた前記高レベル・テーブル中の一つのエントリに、前記低レベル・テーブル中の複数のエントリをリンクした前記階層テーブルのアレイを維持することと、
   高レベルのエントリが置き換えられ若しくは無効化されるごとにインデックス値をインクリメントすることと、
   を含む方法。
2. 前記インデックス値は複数のセット分が維持され、一つのセットを使い切ると、前記複数のセットのうちの他の一つのセットで以って処理を続行する、請求項１に記載の方法。
3. 高レベルのエントリを有することで、その対応する低レベルのエントリの全てに共通の情報を共有することができるようにバッファされたインデックスを備えた高レベル・テーブル中の単一のエントリに、前記複数のエントリが低レベル・テーブルにおいてリンクされる、請求項１に記載の方法。
4. 前記高レベル・テーブルが親のエントリを含み、前記低レベル・テーブルが子のエントリを含み、そして高レベルの親のエントリを有することで、その対応する低レベルの子のエントリの全てに共通の情報を共有することができるようにバッファされたインデックスを備えた高レベル・テーブル中の単一のエントリに、前記複数のエントリが低レベル・テーブルにおいてリンクされる、請求項１に記載の方法。
5. 階層レベルのエントリが置き換えられ若しくは無効化されるごとにインデックス値がインクリメントする、請求項１に記載の方法。
6. 一つのセットを使い切ると、前記複数のセットのうちの他の一つのセットで以って処理を続行するように、複数のセットの前記インデックス値が維持される、請求項５に記載の方法。
7. 前記インデックス値のセットは、新しいエントリが新しいセットから構築されている間に、古いダーティなセットからのインデックス値を備えた、対応する低レベルのエントリが、スクラブされ無効化されるのを許容する、請求項６に記載の方法。
8. テーブルの新しいリクエストが到来すると、バックグラウンド無効化としてスクラビングもしくは無効化が生じる、請求項７に記載の方法。
9. アレイの新しいリクエストが到来すると、前記子のエントリのスクラビングもしくは無効化を中断した後にバックグラウンド無効化が生じ、前記子のエントリの前記新しいリクエストが満たされた後に、スクラビングもしくは無効化が再開する、請求項４に記載の方法。
10. 前記バッファ中のインデックス値を備えた高レベル・テーブル中の単一のエントリに、低レベル・テーブル中の複数のエントリをリンクすることを用い、
    前記インデックス値は、高レベルのエントリが置き替えられもしくは無効化され、かつその対応する低レベル・エントリのインデックス値のセットと切り離されるごとにインクリメントし、
    一つのセットを使い切ったときに前記他のセットのうちの一つのセットで以って処理を続行することができ、
    新しいエントリが新しいクリーン・セットから構築される間に、古いダーティなセットからのインデックス値を備えた全ての対応する低レベルのエントリがスクラブされ無効化されることができ、
    前記スクラビングは前記高レベル・テーブル中の新しいエントリに前記低レベル・テーブル中の古いエントリを関連させるのを防止する、請求項１に記載の方法。
11. 前記スクラビングは、前記バックグラウンドでかつ前記テーブルのリクエストを処理する間に行うことができ、中断することができ、そして前記テーブルのリクエスト・サービス期間に悪影響を与えることなく任意の時間に再開することができる、請求項１０に記載の方法。
12. 記憶システムおよびマイクロプロセッサを含むコンピュータ・システムであって、
    値を持つエントリの階層テーブルを含む階層記憶エレメントのアレイを有するキャッシュ・アレイを含み、
    前記階層テーブルが、前記エントリを含む高レベル・テーブルと少なくとも一つの低レベル・テーブルとを有し、
    前記階層テーブルが、現在インデックス、ダーティ・インデックス、クリーン・インデックスを含む前記エントリのための複数のインデックス値を有するバッファを備えた前記高レベル・テーブル中の一つのエントリに、前記低レベル・テーブル中の複数のエントリをリンクし、かつ
    高レベルのエントリが置き換えられ若しくは無効化されるごとにインデックス値をインクリメントする、
    コンピュータ・システム。
13. 前記キャッシュ・アレイがインデックス・セット管理のためのバッファを有し、前記インデックス・セットが
    高レベル・エントリにより現在使用されているセットであることを表す現在インデックス・セットと、
    使用中でなく、かつ有効なビット・セットを有する低レベル・テーブル中のエントリを関連付けてしまっているかも知れないセットであることを表すダーティ・インデックス・セットと、
    使用中でなく、かつ有効なビット・セットを有する低レベル・テーブル中のどのエントリも関連づけていないセットであることを表すクリーン・インデックス・セットと、
    を含む、請求項１２に記載のコンピュータ・システム。

Images