(57)【特許請求の範囲】
【請求項１】
複数のキャッシュ・ラインを有するキャッシュ・メモリの制御方法であって、
第１のページ・インデックスおよび第１のタグを備えている第１のアドレスによって識別される第１のメイン・メモリ・ロケーションの中に第１のデータ・アイテムを格納するステップと、
前記第１のページ・インデックスおよび第２のタグを備えている第２のアドレスによって識別される第２のメイン・メモリ・ロケーションの中に第２のデータ・アイテムを格納するステップと、
前記第１のページ・インデックスによって識別される第１のキャッシュ・ラインの中に前記第１のデータ・アイテムを格納するステップと、
前記第２のアドレスでキャッシュ・メモリを参照するステップと、
前記第１のキャッシュ・ラインの中に格納されている前記第１のデータ・アイテムを前記第２のデータ・アイテムに置き換えるステップと、
前記第１のキャッシュ・ラインへのアクセス回数に対する当該キャッシュ・ラインにおける置換回数の比率を所定のしきい値と比較するステップと、
前記比較において前記比率が前記しきい値を超えた場合には、
前記第１のタグを第３のメイン・メモリ・ロケーションの中に格納するステップと、
前記第２のタグを第４のメイン・メモリ・ロケーションの中に格納するステップと、
の各ステップを有することを特徴とするキャッシュ・メモリの制御方法。
【請求項２】
複数のキャッシュ・ライン（５４）を有するキャッシュ・メモリのキャッシュ・コントローラ（１６）であって、
第１のページ・インデックスにより識別されるキャッシュ・ラインのスラッシング回数を更新するためのページ・インデックス・モニタ（１０２）と、
前記ページ・インデックス・モニタに接続され、置換トラッキング・コントローラ（１２２）と置換トラッキング・レジスタ（１２４）とを含むページ・インデックス・トラッカ（１２０）と、
を備え、
前記置換トラッキング・コントローラは、前記キャッシュ・ラインへのアクセス回数に対する前記キャッシュ・ラインの中に格納されている第１のデータ・アイテムが第２のデータ・アイテムに置き換った回数の比率が、所定のしきい値を超えた場合には、当該キャッシュ・ラインのページ・インデックスの値を前記置換トラッキング・レジスタ内に格納すると共に、前記置き換ったデータ・アイテムに係るタグの値を記憶し、
前記第１のデータ・アイテムは、前記第１のページ・インデックスと第１のタグを備えている第１のアドレスによって識別される第１のメイン・メモリ・ロケーションの中に格納され、
前記第２のデータ・アイテムは、前記第１のページ・インデックスと第２のタグを備えている第２のアドレスによって識別される第２のメイン・メモリ・ロケーションの中に格納される、
ことを特徴とするキャッシュ・コントローラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概して、キャッシュ・メモリに関し、特に、キャッシュ・メモリにおけるスラッシングを検出してそれを減らすことによってキャッシュ・メモリの性能を改善するための方法および装置に関する。
【０００２】
【従来の技術、及び、発明が解決しようとする課題】
キャッシュ・メモリは中央処理ユニット（ＣＰＵ）に対するメモリへのアクセス時間を減らすためにデータ処理システムの中で通常使われる。キャッシュ・メモリは比較的小規模で高速のメモリであり、その中にアクティブなデータ・アイテム（プログラムの命令および／またはデータ）が置かれる。キャッシュ・メモリは、通常、メイン・メモリより５倍から１０倍高速であり、通常はＣＰＵそのものの速度に近付く。最も頻繁にアクセスされるデータ・アイテムを高速のキャッシュ・メモリの中に保持することによって、平均のメモリ・アクセス時間がキャッシュのアクセス時間に近付く。
【０００３】
アクティブなプログラム・データ・アイテムは「参照の局所性（ｌｏｃａｌｉｔｙ  ｏｆ  ｒｅｆｅｒｅｎｃｅ）」として知られている性質を利用することによって、キャッシュ・メモリの中に保持することができる。参照の局所性の性質は、ほとんどのコンピュータ・プログラムの実行が複数のループについて順次行われるように進行することを認める。この代表的な進行の結果として、ＣＰＵは特定の局所化されたメモリ領域の中の一組の命令を繰り返し実行する。同様に、データに対するメモリの参照も局所化される傾向がある。というのは、テーブル・ルックアップ・ルーチンまたは他の繰返し型のルーチンは、通常、データの小部分に対して繰り返し参照するからである。
【０００４】
参照の局所性の性質の観点から、現在処理されているメイン・メモリからのデータ・アイテム（データおよび／または命令）の１つのブロックを格納するために小規模で高速のキャッシュ・メモリを提供することができる。キャッシュのサイズはメイン・メモリのサイズに比べてごく小さいが、プログラムの参照の局所性の性質のために、メモリ要求の大部分がキャッシュ・メモリの中に置かれる。比較的小規模で比較的高速のキャッシュ・メモリおよび、比較的大規模で比較的低速のメイン・メモリを備えているコンピュータ・システムにおいて、ＣＰＵはメモリ・アクセス命令が処理される時にキャッシュを調べる。所望のデータ・アイテム（データおよび／または命令）がキャッシュの中に見つかった場合、そのデータはキャッシュから読み出される。しかし、データ・アイテムがキャッシュの中に見つからなかった場合、そのデータ・アイテムはメイン・メモリからＣＰＵへ転送され、その所望のデータ・アイテムを含んでいるデータ・アイテムのブロックがメイン・メモリからキャッシュ・メモリへ転送される。したがって、メモリへのその後の参照においては、参照の局所性の性質のために、要求されたデータ・アイテムがキャッシュ・メモリの中で見つかる可能性が高い。
【０００５】
キャッシュ・メモリの構造の代表的な形式としては、直接マップ型のキャッシュおよび連想キャッシュがある。直接マップ型のキャッシュは最も単純で最も高速のキャッシュ・メモリを提供するが、特定のデータ・アイテムを１つのロケーションだけに置くことができるキャッシュ・ロケーションの数を厳しく制限する。頻繁に使われる２個以上のデータ・アイテムが、直接マップ型のキャッシュの中の同じロケーションに対してマップされる時、そしてこれらのデータ・アイテムがループ内でのようにサイクリックな方法でプログラムによって使われる場合、キャッシュのスラッシングが発生する。
【０００６】
キャッシュ・メモリの環境において、スラッシングは、ＣＰＵによるメモリ参照に応答して、被参照データ・アイテムを含んでいるキャッシュ・ラインを、キャッシュ・メモリと外部メモリとの間でスワップするためにそのほとんどすべての時間を費やす、キャッシュ・メモリの状態として定義される。特に、各データ・アイテムが参照される時、それはその前にあったものを取り除き、比較的低速のメイン・メモリのアクセスを発生させる。キャッシュのスラッシングが発生すると、メイン・メモリへのアクセスが頻繁に強制的に行われることによって、プログラムの実行速度が極端に低下する可能性がある。
【０００７】
連想型のキャッシュ・メモリはデータ・アイテムがマップする２つまたはそれ以上のロケーションを提供する。結果として、連想キャッシュはキャッシュ・メモリの中の最も最近に使われたデータ・アイテムが見つかる確率を増加させることによって、キャッシュのスラッシングの可能性を減らす。しかし、サイクリックに参照されるデータ・アイテムの集合全体を同時に保持するのに十分なメモリ・ロケーションを含んでいないキャッシュ・メモリの中の、一組のロケーションに対してマップする一組のデータ・アイテムの中を、コンピュータ・システムが巡回している場合には、連想のキャッシュ・メモリにおいてもキャッシュのスラッシングが発生する可能性がある。
【０００８】
本発明の目的は、どのメモリ参照がスラッシングを起こす原因になっているかを検出することによって、直接マップ型のキャッシュ・メモリおよび連想型のキャッシュ・メモリの性能を改善するための方法および装置を提供することである。
【０００９】
【課題を解決するための手段】
本発明の一つの態様によれば、複数のキャッシュ・ラインを有するキャッシュ・メモリの制御方法であって、第１のページ・インデックスおよび第１のタグを備えている第１のアドレスによって識別される第１のメイン・メモリ・ロケーションの中に第１のデータ・アイテムを格納するステップと、前記第１のページ・インデックスおよび第２のタグを備えている第２のアドレスによって識別される第２のメイン・メモリ・ロケーションの中に第２のデータ・アイテムを格納するステップと、前記第１のページ・インデックスによって識別される第１のキャッシュ・ラインの中に前記第１のデータ・アイテムを格納するステップと、前記第２のアドレスでキャッシュ・メモリを参照するステップと、前記第１のキャッシュ・ラインの中に格納されている前記第１のデータ・アイテムを前記第２のデータ・アイテムに置き換えるステップと、前記第１のキャッシュ・ラインへのアクセス回数に対する当該キャッシュ・ラインにおける置換回数の比率を所定のしきい値と比較するステップと、前記比較において前記比率が前記しきい値を超えた場合には、前記第１のタグを第３のメイン・メモリ・ロケーションの中に格納するステップと、前記第２のタグを第４のメイン・メモリ・ロケーションの中に格納するステップと、の各ステップを有することを特徴とするキャッシュ・メモリの制御方法を提供するものである。
【００１０】
本発明の他の態様によれば、複数のキャッシュ・ラインを有するキャッシュ・メモリのキャッシュ・コントローラであって、第１のページ・インデックスにより識別されるキャッシュ・ラインのスラッシング回数を更新するためのページ・インデックス・モニタと、前記ページ・インデックス・モニタに接続され、置換トラッキング・コントローラと置換トラッキング・レジスタとを含むページ・インデックス・トラッカと、を備え、前記置換トラッキング・コントローラは、前記キャッシュ・ラインへのアクセス回数に対する前記キャッシュ・ラインの中に格納されている第１のデータ・アイテムが第２のデータ・アイテムに置き換った回数の比率が、所定のしきい値を超えた場合には、当該キャッシュ・ラインのページ・インデックスの値を前記置換トラッキング・レジスタ内に格納すると共に、前記置き換ったデータ・アイテムに係るタグの値を記憶し、前記第１のデータ・アイテムは、前記第１のページ・インデックスと第１のタグを備えている第１のアドレスによって識別される第１のメイン・メモリ・ロケーションの中に格納され、前記第２のデータ・アイテムは、前記第１のページ・インデックスと第２のタグを備えている第２のアドレスによって識別される第２のメイン・メモリ・ロケーションの中に格納される、ことを特徴とするキャッシュ・コントローラを提供するものである。
【００１１】
本開示のために、キロバイト（ＫＢ）は２10バイト、すなわち、１，０２４バイトとして定義され、メガバイト（ＭＢ）は２20バイト、すなわち、１，０４８，５７６バイトとして定義され、そしてギガバイト（ＧＢ）は２30バイト、すなわち、１，０７３，７４１，８２４バイトとして定義されている。さらに、末尾にＫが付く数値はその数値が１，０２４倍されることを意味し、そして末尾にＭが付く数値は１，０４８，５７６倍されることを意味する。
【００１２】
本発明の１つの実施形態が、付属の図面を参照しながら例を示す方法によって以下に記述される。
【００１３】
【発明の実施の形態】
図１を参照すると、本発明の特徴が組み込まれているコンピュータ・システムの一例１０の単純化されたブロック図が示されている。コンピュータ・システム１０はキャッシュ・コントローラ１６およびＣＰＵバス１８を通じてシステム・バス１４に結合されている中央処理ユニット（ＣＰＵ）１２を含む。メイン・メモリ、すなわち、物理メモリ２０はシステム・バス１４に接続されていてそれによってアクセスされ、キャッシュ・メモリ２２はキャッシュ・コントローラ１６に接続されていて、キャッシュ・メモリ２２はＣＰＵバス１８によって直接にアクセスされるようになっている。ＣＰＵ１２は仮想メモリ管理システムを組み込んでおり、データのページがメイン・メモリ２０によって提供される物理メモリとディスク２４の形での二次の記憶装置との間でスワップされるようになっている。
【００１４】
記述されているこの実施形態において、キャッシュ・メモリ２２は直接マップ型のキャッシュ・メモリであってよい。しかし、キャッシュ・メモリ２２は２ウェイまたは４ウェイの連想キャッシュ・メモリなどの連想キャッシュ・メモリであってもよいことを理解されたい。図１のＣＰＵ１２は内部キャッシュ・メモリを備えていてもよく、それには命令キャッシュ、すなわち、Ｉキャッシュ２８およびデータ・キャッシュ、すなわち、Ｄキャッシュ３０が含まれている。コンピュータ・システム１０によって使われるメモリ・サブシステムはこのように階層構造になっていて、その最高速のメモリは内部キャッシュ２８および３０であり、次に高速のメモリはキャッシュ・メモリ２２であり、その次はメイン・メモリ２０であり、そして最後はディスク２４の中のスワップ空間である。
【００１５】
最高速のメモリ・サブシステムと最低速のメモリ・サブシステムとの間のスピード（すなわち、アクセス・タイム）の差は何桁の程度にもなる。内部キャッシュ２８および２３およびキャッシュ２２は、通常、少数のＣＰＵサイクル内でアクセスされ、一方メイン・メモリ２０は、通常、１０〜１００またはそれ以上のＣＰＵサイクルの範囲においてアクセスされ、そしてディスク２４に対するページのスワップは数百〜数千のＣＰＵサイクルを必要とするのが通常である。したがって、コンピュータ・システムの性能は現在使用中の命令およびデータをキャッシュ２２、２８、および３０の中に維持しておくことによって大きく変わる。
【００１６】
図２に示されているように、ＣＰＵ１２は仮想メモリ空間３２の中の１つのバイトを定義している仮想アドレスを形成し、そしてその仮想アドレスを物理メモリ空間３４の内部の１つの物理アドレスに変換することによって、メイン・メモリ２０に対する参照を発生する。仮想メモリ空間３２は、オペレーティング・システムによってアクセスされることが可能な、コンピュータ・システム１０またはその一部分のアーキテクチャ的な仕様によって定義される。しかし、物理メモリ空間３４はメイン・メモリ２０の量によって制限される。
【００１７】
この実施形態のコンピュータ・システム１０は、メイン・メモリ２０のバイトを参照するために３２ビットの仮想アドレスを発生する。したがって、コンピュータ・システム１０は４ＧＢのバイト・アドレッシング可能な仮想メモリ空間３２を備えている。さらに、この実施形態のコンピュータ・システム１０は６４ＭＢのメイン・メモリ２０および、３２バイトのキャッシュ・ラインを有する４ＭＢの直接マップ型キャッシュ２２を備えている。また、この実施形態のコンピュータ・システム１０は４ＫＢのページを使って仮想メモリ空間３２を物理メモリ空間３４に対してマップする。
【００１８】
上記のように、仮想メモリ空間３２から物理メモリ空間３４への変換は４ＫＢのページ単位で行われる。すなわち、仮想ページ３５の４ＫＢの連続したブロック（図２）が物理ページ３７の４ＫＢの連続したブロック（図２）に対してマップする。ページ・テーブル（図には示されていない）がメイン・メモリ２０の中に維持され、仮想メモリ空間３２と物理メモリ空間３４との間の変換を提供する。変換バッファ２６（図１）をＣＰＵ１２の中に含めることができる。これは最も最近の変換に対するページ・テーブル・エントリーを維持し、データ参照を行う前にその変換を得るためにメイン・メモリ２０の中のページ・テーブルを参照しなくて済むようにしている。
【００１９】
現在実行中のタスク（およびオペレーティング・システム自身）によって使われているページだけが、或る時期においてメイン・メモリ２０の中にあるのが普通である。物理ページ３７への変換はメイン・メモリ２０の中に実際にある物理ページ３７だけに対するページ・テーブルの中にある。ＣＰＵ１２によって参照されようとしている仮想ページ３５がメイン・メモリ２０の中に見つからない時、ページ・フォルトが実行されてスワップ操作が開始され、その中でメイン・メモリ２０の物理ページ３７が、ディスク・メモリ２４の中に維持されている所望の仮想ページ３５とスワップされる。
【００２０】
ここで図３を参照すると、仮想アドレス８６の物理アドレス３６に対するマッピング、および物理アドレス３６のキャッシュ・インデックス４２とページ・インデックス・フィールド９４へのマッピングの図が示されている。仮想アドレス８６は仮想ページ・フレーム番号（ＶＰＮ）フィールド８８およびオフセット・フィールド９１を含んでいる。オフセット・フィールド９１は仮想ページ３５の中のどのバイトをＣＰＵが参照しているかを提示する。実施形態では４ＫＢの仮想ページ３５を使うので、４ＫＢのページの各バイトをユニークに識別するためには、オフセット・フィールド９１は最低１２ビットの幅でなければならない。したがって、オフセット・フィールド９１は仮想アドレス８６の１２個の下位ビット（ＬＳＢ）（Ａ１１〜Ａ０）からなり、それによって仮想ページ３５の４Ｋ個のバイトをユニークに識別するために必要な４Ｋ個のユニークな値を提供している。
【００２１】
ＶＰＮフィールド８８は仮想メモリ空間３２の中のどの仮想ページ３５をＣＰＵ１２が参照しているかを提示する。この実施形態では４ＫＢの仮想ページ３５から成る４ＧＢの仮想メモリ空間３２を備えているので、ＶＰＮフィールド８８は４ＧＢの仮想メモリ空間３２の１Ｍ個の仮想ページ３５をユニークに識別するために、最低２０ビットの幅でなければならない。したがって、ＶＰＮフィールド８８は仮想アドレス８６の上位ビット（ＭＳＢ）（Ａ３１〜Ａ１２）から作られ、それによって仮想メモリ空間３２の１Ｍ個の仮想ページ３５をユニークに識別するための１Ｍ個の値を提供している。
【００２２】
物理アドレス３６はページ・フレーム番号（ＰＦＮ）フィールド３８とオフセット・フィールド４０とに分割することができる。オフセット・フィールド４０は物理メモリ空間３４の物理ページ３７の中のどのバイトに対してＣＰＵが参照しているかを定義する。実施形態においては物理ページ４７は４ＫＢであるので、オフセット・フィールド９１は４ＫＢの物理ページ３７の各バイトをユニークに識別するために、最低１２ビットの幅でなければならない。したがって、オフセット・フィールド４０は物理アドレス８６の１２個の下位ビット（ＬＳＢ）（Ａ１１〜Ａ０）から作られ、それによって物理ページ３７の４Ｋ個のバイトを識別するための４Ｋ個のユニークな値を提供している。仮想アドレス８６のオフセット・フィールド９１および物理アドレス３６のオフセット・フィールド４０は両方とも１２ビット幅であり、そして両方とも４ＫＢのメモリ空間をユニークに識別するために使われるので、ＣＰＵ１２は仮想アドレス８６を物理アドレス３６に対してマップする時にオフセット・フィールド９１の値を変える必要はない。
【００２３】
ＰＦＮフィールド３８は物理メモリ空間３４の中のどの物理ページ３７に対してＣＰＵが参照しているかを提示する。実施形態では４ＫＢの物理ページ３７から作られている物理メモリ空間３４を提示するためにメイン・メモリ２０の６４ＭＢだけを備えているので、ＰＦＮフィールド３８は６４ＭＢの物理アドレス空間のうちの１６Ｋ個の物理ページ３７をユニークに識別するために、最低１４ビットの幅でなければならない。
【００２４】
しかし、物理メモリ空間３４はメモリ・モジュールを追加するか、あるいはメイン・メモリ２０の既存のメモリ・モジュールを追加することによって、コンピュータ・システム１０の中で簡単に増設することができる。結果として、ＰＦＮフィールド３８はコンピュータ・システム１０がユニークに識別することができるだけのメモリ（この実施形態においては４ＧＢ）をユニークに識別するために十分なビットを含んでいる必要がある。したがって、ＰＦＮ３８は物理アドレス８６の２０個の上位ビット（ＭＳＢ）（Ａ３１〜Ａ１２）から作られ、それによって、４ＧＢのメイン・メモリ２０が存在した場合でも、コンピュータ・システム１０がユニークに識別することができる１Ｍ個のページをユニークに識別するための１Ｍ個の値を提供している。
【００２５】
この実施形態におけるＣＰＵ１２は４ＧＢのデータに対して仮想アドレス８６を発生することができる。しかし、メイン・メモリ２０は６４ＭＢしかない。結果として、ＶＰＮフィールド８８に対する可能な値のほとんどは、ＣＰＵ１２がＰＦＮフィールド３８として使うためには無効である。というのは、その結果の物理アドレス３６は、メイン・メモリ２の中に対応するロケーションがないメモリ・ロケーションを参照するからである。したがって、ＣＰＵ１２はメイン・メモリ２０の中の１つのテーブルと変換バッファ２６を維持し、メイン・メモリ２０の中のロケーションに対応するＰＦＮフィールド３８のための１６Ｋ個の値に対して、ＶＰＮフィールド８８のための１Ｍ個のユニークな値をマップする。
【００２６】
図４において、通常はキャッシュ・コントローラ１６（図１）の一部であるタグ／ステート記憶６０と一緒に、直接マップ型のキャッシュ２２（図１）の図が示されている。直接マップ型のキャッシュ２２はキャッシュ・ライン・デコーダ５０およびいくつかのキャッシュ・ライン５４を含む。タグ／ステート記憶６０はタグ／ステート・デコーダ６２および、キャッシュ２２の各キャッシュ・ライン５４に対するタグ／ステート・ライン６６を含む。
【００２７】
キャッシュ２２（またはメイン・メモリ２０）にアクセスするために使われるＣＰＵバス１８上の物理アドレス３６は、オフセット・フィールド４４と、インデックス・フィールド４２と、タグ・フィールド４０とを含む。オフセット・フィールド４４はキャッシュ・ライン５４の内部のバイト（またはワード）を選択する。インデックス・フィールド４２はキャッシュ・ライン・デコーダ５０へ印加されてキャッシュ２２の内部のキャッシュ・ライン５４を選択し、また、タグ／ステート・デコーダ６２へ印加されて、選択されたキャッシュ・ライン５４に対応するタグ／ステート記憶６０の内部のタグ／ステート・ライン６６を選択する。タグ・フィールド４０はキャッシュ・ライン５４がどの物理アドレス３６に対応するかをユニークに識別するために使われる。
【００２８】
タグ／ステート記憶６０は、キャッシュ２２のキャッシュ・ライン５４に対応しているいくつかのタグ・フィールド６５および、ステート・フィールド６７を保持する。ステート・フィールド６７はそのデータが有効（ｖａｌｉｄ）／またはダーティ（ｄｉｒｔｙ）であるかどうかなどの、キャッシュ・ライン５４に対応している格納されたデータの状態を決定するために使われる。キャッシュ・ライン５４の中のデータは各種の理由のために無効である可能性がある。例えば、そのデータは以前のプロセスがキャッシュ・ライン５４に対して行われたか、あるいは別のプロセッサまたはＤＭＡデバイスがキャッシュ・ライン５４に対してマップするメイン・メモリ２０の中の１つのロケーションに対して書込みを行ったために、そのキャッシュ・ライン５４を無効にしたかの理由でそのデータが無効になっている可能性がある。
【００２９】
さらに、キャッシュ・ライン５４の中に格納されているデータは、ライトバック・キャッシュの環境においてダーティになっている可能性がある。その場合、データは先ずキャッシュ２２に対して書かれ、そして後でメイン・メモリ２０に対して書き込まれる。このダーティ・ビットによって、キャッシュ・ライン５４の中に含まれているデータが他のデータによって置き換えられる前に、メイン・メモリ２０またはディスク・メモリ２４に対して書き込まれる必要があるかどうかを決定することができる。
【００３０】
タグ／ステート・デコーダ６０はインデックス・フィールド４２の中の値を使って、キャッシュ・ライン・デコーダ５０によって選択されたキャッシュ・ライン５４に対応するタグ・フィールド６５およびステート・フィールド６７を選択する。タグ／ステート・デコーダ６２によって選択されたタグ・フィールド６５およびステート・フィールド６７の中に格納されている値は、タグ・フィールド４０の値と一緒にステート信号ゼネレータ６８へ送られる。ステート信号ゼネレータ６８はタグ・フィールド６５の値がタグ・フィールド４０の値とマッチし、そしてステート・フィールド６７に対する値がその選択されたキャッシュ・ライン５４の中に格納されているデータが有効であることを示している場合、出力信号線７０上にキャッシュ・ヒット信号を発生する。上記の条件が満足されなかった場合、ステート・ゼネレータ６８は出力信号線７０上にキャッシュ・ミス信号を発生する。キャッシュ・ミスが発生すると、メイン・メモリ２０への参照がなされなければならない。したがって、物理アドレス３６がキャッシュ・コントローラ１６を通じてシステム・バス１４へ渡されて、メイン・メモリ２０からそのデータを得る。
【００３１】
ステート信号ゼネレータ６８は出力信号線７２上にキャッシュ・アクセス信号を発生し、そして出力信号線７４上にキャッシュ置換信号も発生する。アクセス信号はキャッシュ２２に対する参照によって、ステート信号ゼネレータ６８がタグ・フィールド６５およびステート・フィールド６７から値を受け取るたびに発生される。さらに、置換信号はキャッシュ・ミスが発生してメイン・メモリ２０からのデータで置き換えられることになるキャッシュ・ライン５４が、現在キャッシュ・ライン５４に対応しているステート・フィールド６７によって示されているような有効な値を含んでいる時に発生される。
【００３２】
上記のように、キャッシュ２２は３２バイトのデータをそれぞれ格納することができるキャッシュ・ライン５４を含む。結果として、キャッシュ・ライン５４の中の１つのバイトをユニークに識別するために使われるオフセット・フィールドは各キャッシュ・ライン５４の３２バイトを識別するために最低５ビットの幅でなければならない。したがって、物理アドレス３６の５個のＬＳＢ（Ａ４〜Ａ０）がオフセット・フィールド４４のために使われ、それによってキャッシュ・ライン５４の３２バイトを識別するための３２個のユニークな値を提供している。さらに、上記のように、キャッシュ２２は４ＭＢのデータを格納することができ、そして各キャッシュ・ラインは３２バイトのデータを格納することができる。したがって、キャッシュ２２は１２８Ｋ（４ＭＢ／３２バイト）のキャッシュ・ライン５４を含む。結果として、キャッシュ２２の内部の各キャッシュ・ライン５４をユニークに識別するために使われるインデックス・フィールド４２は、１２８Ｋ個の可能なキャッシュ・ライン５４のそれぞれをユニークに識別するために、最低１７ビットの幅でなければならない。したがって、物理アドレス３６のオフセット・フィールド４４に続いている１７個のＬＳＢ（Ａ２１〜Ａ５）がインデックス・フィールド４２として使われる。最後に、タグ・フィールド４０は物理アドレス３６の１０個のＭＳＢ（Ａ３１〜Ａ２２）から構成され、それによって、各キャッシュ・ライン５４の中に格納される仮想メモリ空間３２の１Ｋ個の可能な３２バイト・ブロックのそれぞれを識別するための１Ｋ個のユニークな値を提供している。
【００３３】
前へ戻って図３を参照すると、物理アドレス３６のページ・インデックス・フィールド９０がＰＦＮフィールド３８とインデックス・フィールド４２のオーバラップとして定義されている。したがって、この実施形態において、ページ・インデックス・フィールド９０は物理アドレス３６のビットＡ２１〜Ａ１２から作られている。仮想ページ３５を物理ページ３７へ、そして物理ページ３７をキャッシュ２２へマップするこの方式の結果として、ページ・インデックス・フィールド９５に対する値が同じであるすべての物理ページ３７は、キャッシュ２２の中の同じロケーションに対してマップする。ＣＰＵ１２がページ・インデックス・フィールド９０に対する値が同じである２つの物理ページ３７をサイクリックに参照する場合、キャッシュ２２の参照されるキャッシュ・ライン５４が繰り返し置き換えられるように２つの物理ページに対する繰返し参照が発生した場合、スラッシング状態が発生する可能性がある。
【００３４】
メイン・メモリ２０のどの物理ページ３７がキャッシュ２２をスラッシュさせる原因となっているかをコンピュータ・システム１０が検出できる場合、ＣＰＵ１２はその状況を救済することができる。それは（１）スラッシュしている物理ページ３７を移動し、それらのページ・インデックス・フィールド９０の値が異なるようにすることおよび（２）変換バッファ２６およびメイン・メモリ２０の中に格納されている変換テーブルを更新し、そのスラッシュしている物理ページ３７に対応している仮想ページ３５がその移動された物理ページ３７に対して正しくマップするようにすることによって行われる。そうすることによって、以前にスラッシュしていた物理ページ３７はキャッシュ２２の中の同じロケーションに対してマップされなくなり、結果として互いにスラッシュしなくなる。
【００３５】
スラッシュしている物理ページ３７が仮想メモリ空間３２から仮想メモリ空間３４へマップし直される前に、スラッシュしている物理ページ３７が先ず最初に検出されなければならない。これらのスラッシュしている物理ページ３７の存在はもちろんデータに依存し、そしてアプリケーション・ソフトウエアに依存している。したがって、スラッシングが発生する実行時点より前にそれを予測することは実質的に不可能である。さらに、そのソフトウエアの別の呼出しにおいて、スラッシングのインスタンスはおそらくプログラムの中の異なる時刻および場所において発生し得る。言い換えれば、問題のソフトウエアはスラッシングが存在しているかどうかが決定される前に、そしてスラッシングの各インスタンスの局所性が知られる前に、実行されていなければならない。
【００３６】
ここで図５を参照すると、キャッシュ・コントローラ１６（図１）のスラッシングの検出および削減の回路（ＴＤＲＣ）１００が示されている。ＴＤＲＣ１００はページ・インデックス・モニタ（ＰＩＭ）１０２およびページ・インデックス・トラッカ（ＰＩＴ）１２０を含み、それらはキャッシュ２２をスラッシュさせている物理ページ３７を正しく決定する。ＰＩＭ１０２はページ・インデックス・モニタ・コントローラ（ＰＩＭＣ）１０４）およびページ・インデックス・モニタ・メモリ（ＰＩＭＭ）１０６を含む。
【００３７】
ステート信号ゼネレータ６８（図４）によって発生された信号に応答して、ＰＩＭＣ１０４はＰＩＭＭ１０６の内容を制御し、更新する。この実施形態において、ＰＩＭＭ１０６はページ・インデックス・フィールド９０のユニークな各値に対するカウント・ライン１０８を含む。この実施形態の中ではページ・インデックス・フィールド９０は１０ビットなので、ページ・インデックス・フィールド９０に対する１Ｋ個のユニークな値がある。したがって、１Ｋ個の可能なインデックス値に対応しているＰＩＭＭ１０６の中の１Ｋ個のカウント・ライン１０８がある。
【００３８】
各カウント・ライン１０８は置換カウント・フィールド（ＲＣ）１１０およびアクセス・カウント・フィールド（ＡＣ）１１２を含む。置換カウント・フィールド１１０は、キャッシュ２２の中のページ・インデックス・フィールド９０によって識別されるデータが置き換えられた回数を表している値を格納する。アクセス・カウント・フィールド１１２はページ・インデックス・フィールド９０によって識別されたキャッシュ２２の中のデータがアクセスされた回数を表している値を格納する。
【００３９】
ページ・インデックス・トラッカ１２０はページ・インデックス置換トラッキング・コントローラ（ＰＩＲＴＣ）１２２と、いくつかのページ・インデックス置換トラッキング・レジスタ（ＰＩＲＴＲ）１２４および各ＰＩＲＴＲ１２４に対する置換トラッキング記憶（ＲＴＳ）１３６とを含む。各ＰＩＲＴＲ１２４はページ・インデックス・フィールド１２６、アクティベーション・フィールド１２８、およびカウント・フィールド１３０を含む。ページ・インデックス・フィールド１２６は物理アドレス３６のページ・インデックス・フィールド９０を格納するのに十分な幅がある。言い換えれば、この実施形態においては、ページ・インデックス・フィールド１２６は１０ビット幅である。この実施形態におけるアクティベーション・フィールド１２８は１ビット幅であり、ＰＩＲＴＲ１２４がアクティブな情報を含んでいるかどうかを判定するために、ＰＩＲＴＣ１２２によって使われる。さらに、カウント・フィールド１３０はＰＩＲＲＴＲ１２４が活性化されて以来、ページ・インデックス１２６によって識別されたデータがキャッシュ２２の中で置換された回数を表している値を格納する。
【００４０】
ＲＴＳ１３６はカウント・フィールド１３０の可能な各値に対する置換ライン１３８を備えている。各置換ライン１３８はカウント・フィールド１３０によってユニークに識別され、古いタグ・フィールド１３２、および新しいタグ・フィールド１３４を含む。古いタグ・フィールド１３２は現在のメモリ参照によって置換されたキャッシュ２２の中の情報に対応しているタグ・フィールド４０の値を格納する。新しいタグ・フィールド１３４はキャッシュ２２の中の情報を置き換えた現在のメモリ参照のタグ・フィールド４０の値を格納する。この実施形態のタグ・フィールド４０は１０ビット幅なので、古いタグ・フィールド１３２および新しいタグ・フィールド１３４は両方ともそれぞれ１０ビット幅であり、それらはタグ・フィールド４０の値を格納することができるようになっている。
【００４１】
コンピュータ・システム１０の動作中に、直接マップ型のキャッシュ２２が次のようにして初期化される。（１）タグ／ステート記憶６６（図４）のステート・フィールド６７（図４）の有効ビットを不活性化する。（２）すべての置換レジスタ１２４（図５）に対するアクティベーション・フィールド１２８（図５）を非活性化する。（３）すべての置換カウント・フィールド１１０およびアクセス・カウント・フィールド１１２を０に設定する。キャッシュ２２の初期化は、通常、電源投入時またはキャッシュ２２がスラッシュされた時に行われる。（キャッシュのフラッシングはすべてのデータをメモリへ書き戻し、すべてのキャッシュ・ラインを無効化することを意味する）。
【００４２】
ここで図６を参照すると、キャッシュ２２が初期化された後のスラッシングの検出および削減の回路（ＴＤＲＣ）１００（図５）の動作を説明している手続き的フローチャート３００が示されている。ＴＤＲＣ１００の動作はＰＩＭＣ１０４が信号線７２上でステート信号ゼネレータ６８（図４）からのキャッシュ・アクセス信号を受信した時に初期化される（ステート３１０）。キャッシュ・アクセス信号をステート信号ゼネレータ６８から受け取ると、ＰＩＭＣ１０４はページ・インデックス・フィールド９０によって識別されるアクセス・カウント・フィールド１１２をインクリメントする（ステート３２０）。また、ＰＩＭＣ１０４はステート信号ゼネレータ６８から信号線７４上でキャッシュ置換信号を受け取った場合、そのページ・インデックス・フィールド９０によって識別される置換カウント・フィールド１１０をインクリメントする。
【００４３】
置換カウント・フィールド１１０およびアクセス・カウント・フィールド１１２に対して使われるビットの数が限定されているので、オーバフロー状態が発生する可能性がある。アクセス・カウント・フィールド１１２または置換カウント・フィールド１１０の中に格納されている値をインクリメントすることによってオーバフロー状態になった場合、ＰＩＭＣ１０４はアクセス・カウント・フィールド１１２および置換カウント・フィールド１１０の中に格納されている値を下げ、アクセス・カウント・フィールド１１２に対する置換カウント・フィールド１１０の比率の値がこれらの２つのフィールドの以前の比率と同じであるように保たれる。ＰＩＭＣ１０４はアクセス・カウント・フィールド１１２および置換カウント・フィールド１１０の値を同じビット数だけシフトすることによって、この結果を得ることができる。
【００４４】
ＰＩＭＣ１０４がアクセス・カウント・フィールド１１２および置換カウント・フィールド１１０のビット値を同じビット数だけシフトすることによって、この結果を得ることができる。ＰＩＭＣ１０４がアクセス・カウント・フィールド１１２の中に格納されている値および、おそらく置換カウント・フィールド１１０の中に格納されている値を更新した後、ＰＩＭＣ１０４はスラッシング比（アクセス・カウント・フィールド１１２の中に格納されている値に対する、置換カウント・フィールド１１０の中に格納されている値の比として定義される）が所定のしきい値（Ｘ）より大きいかどうかを判定する（ステップ３３０）。スラッシング比がしきい値（Ｘ）より大きくなかった場合、ＴＤＲＣ１００は現在のメモリ参照の処理を行い、そしてＴＤＲＣ１００はステップ３９０へ進む。スラッシング比（ＲＣ／ＡＣ）がしきい値（Ｘ）より大きかった場合、ＰＩＭＣ１０４は信号線１４０上でＰＩＲＴＣ１２２に対して信号を送る。この実施形態においては、しきい値（Ｘ）はプログラマブルであり、それによってキャッシュ２２の性能をコンピュータ・システム１０の動作状態における違いに対して調整することができる。
【００４５】
スラッシング比（ＲＣ／ＡＣ）はページ・インデックス・フィールド９０に対するメモリ参照当たりのキャッシュ・ラインの置換の回数を表す。ページ・インデックス・フィールド９０に対するすべてのメモリ参照がキャッシュ２２にキャッシュ・ライン５４を置換させた場合、スラッシング比（ＲＣ／ＡＣ）は１に等しくなる。結果として、ページ・インデックス・フィールド９０に対するスラッシング比が１であることは、ページ・インデックス・フィールド９０に対するメモリ参照に対して何も性能の向上を提供していないことを意味する。というのは、メモリ参照を行なうたびにそれぞれのキャッシュ・ライン５４の中のデータを置換するためにメイン・メモリ２０に対する参照が行われるからである。
【００４６】
多くのコンピュータ・システムにおいて、スラッシング比が０．１０や０．０５程度の小さい値であっても、大きな性能低下が発生する。結果として、しきい値（Ｘ）はほとんどのコンピュータ・システムに対して０．０５と０．１０との間の値で十分であるのが通常である。そのような低いしきい値の結果として、置換カウント・フィールド１１０はアクセス・カウント・フィールド１１２より幅が広い必要はない。置換カウント・フィールド１１０の幅がｍ／３ビットであって、アクセス・カウント・フィールド１１２の幅が２ｍ／３ビットであれば十分な結果が得られると考えられている。ここでｍは置換カウント・フィールド１１０とアクセス・カウント・フィールド１１２を組み合わせたビット幅である。
【００４７】
信号線１４０上で信号を受信すると、ルーチンはステップ３４０へ進み、そこでＰＩＲＴＣ１２２はアクティブなＰＩＲＴＲ１２４がページ・インデックス・フィールド９０の値に対して割り当てられているかどうかを判定する。アクティブなＰＩＲＴＲ１２４が割り当てられていた場合、このルーチンはステップ３５０へ進む。しかし、アクティブなＰＩＲＴＲ１２４が割り当てられていなかった場合、ＰＩＲＴＣ１２２は、（１）ページ・インデックス・フィールド９０の値をページ・インデックス・フィールド１２６へロードし、そして（２）アクティベーション・ビット１２８を活性化することによって、１つのＰＩＲＴＲ１２４を割り当てる。ＰＩＲＴＲ１２４をページ・インデックス・フィールド９０に対して割り当てた後、ＰＩＲＴＣ１２２はステップ３５０へ進む。ＰＩＲＴＣ１２２は、実装が単純で、実行が速く、そしてＰＩＲＴＲの１２４を割り当てるためにＣＰＵ１２の使用率が小さい（可能な場合は０である）利点を有する非常に単純な割り当て方式によって、ＰＩＲＴＲ１２４に対してページ・インデックスを割り当てるための各種の割り当て方式が使えることを理解されたい。
【００４８】
ステップ３５０において、ＰＩＲＴＣ１２２はカウント・フィールド１３０、古いタグ・フィールド１３２、および新しいタグ・フィールド１３４を、ページ・インデックス・フィールド９０に対して割り当てられているＰＩＲＴＲ１２４に対して更新する。特に、ＰＩＲＴＣ１２２は古いタグ・フィールド１３２に置換されるキャッシュ・ライン５４に対応しているタグ・フィールド６５（図４）の値を格納することによって、古いタグ・フィールド１３２を更新する。さらにＰＩＲＴＣ１２２は新しいタグ・フィールド１３４の中に、置換しているキャッシュ・ライン５４に対応しているタグ・フィールド４０の値を格納することによって、新しいタグ・フィールド１３４を更新する。最後に、ＰＩＲＴＣ１２２はカウント・フィールド１３０の中に格納されている値をインクリメントすることによって、カウント・フィールド１３０を更新する。この実施形態においては、カウント・フィールド１３０は古いタグ１３２および新しいタグ１３４のための値を格納するために、ＲＴＳ１３６の中のどの記憶場所を使うかを識別するためのインデックスとして使われるが、ＲＴＳ１３６の中の記憶場所を割り当てるために各種の他の手段が使えることを理解されたい。
【００４９】
ステップ３７０において、ＰＩＲＴＣ１２２は、カウント・フィールド１３０の中に格納されている値をインクリメントすることの結果として、カウント・フィールド１３０がオーバフローしたかどうかを判定する。カウント・フィールド１３０がオーバフローしなかったとＰＩＲＴＣ１２２が判定した場合、ＴＤＲＣ１００はその物理アドレス３６の処理を終了し、ＴＤＲＣ１００はステップ３９０へ進む。カウント・フィールド１３０の中に格納されている値をインクリメントした結果、オーバフロー状態になった場合、ＴＤＲＣ１００はステップ３８０へ進む。ＴＤＲＣ１００はカウント・フィールド１３０が或る所定のオーバフローより小さいしきい値に達した時にステップ３８０へ進むように設計できることを理解されたい。言い換えれば、カウント・フィールド１３０がｊ個の可能な値を持ち、ＲＴＳ１３０がｊ個のペアの記憶場所を持っていた場合、ＴＤＲＣ１００はｊ個以下のペアの古いタグ１３２および新しいタグ１３４の値が格納された時にステップ３８０へ進むように設計することができる。
【００５０】
ステップ３８０において、ＰＩＲＴＣ１２２はＣＰＵ１２に対して割込みが送られるようにする。ＣＰＵ１２はページ・インデックス・フィールド１２６の中およびＲＴＳ１３０の中に格納されている値を得ることによって、その割込みを処理する。ＣＰＵ１２がページ・インデックス・フィールド１２６およびＲＴＳ１３６の中に格納されている値を得ると、ＣＰＵ１２はその古いタグ・フィールド１３２、新しいタグ・フィールド１３４、およびページ・インデックス・フィールド１２６から、キャッシュ２２の中に同じロケーションに対してマップされていることの結果としてどの物理ページ３７がスラッシング状態を生じているかを判定することができる。
【００５１】
ＣＰＵ１２がスラッシングを起こしている物理ページを決定すると、ＣＰＵ１２はそのスラッシングを起こしている物理ページ３７を物理メモリ２０の中に移動し、それらがページ・インデックス・フィールド９０に対して異なる値を持つようにすることによって、その検出している物理ページ３７の間のスラッシングを減らすことができる。前に戻って図２を参照すると、物理ページ３７Ａが物理ページ３７Ｂとスラッシングを起こしていることをＣＰＵ１２が判定した状況が示されており、その場合、ＣＰＵ１２は上記の結果を次のようにして得ることができる。（１）割り当てられていない仮想ページ３５Ｃを物理ページ３７Ｂに対してマップする。（２）物理ページ３７Ｂに元々関連付けられていた仮想ページ３５Ｂを、ページ・インデックス・フィールド９０の値が異なる物理ページ３７Ｃに対してマップする。（３）物理ページ３７Ｂからのデータを物理ページ３７Ｃへコピーする。この方法でマップすることによって、以前にスラッシングを起こしていたページ３７Ａと３７Ｂは、それぞれキャッシュ２２の中の同じロケーションに対してはマップされない物理ページ３７Ａおよび３７Ｃの中に格納され、結果として互いにスラッシュしなくなる。
【００５２】
スラッシュしている物理ページ３７に対する新しい物理ページ３７を選定するためのアルゴリズムは、そのスラッシュしている物理ページ３７のページ・インデックス・フィールド９０を単にデクリメントまたはインクリメントするか、あるいはコンピュータ・システム１０がスラッシュしている物理ページ３７に対してページ・インデックス値の異なる未割当ての物理ページ３７を割り当てることもできる。未割当ての物理ページ３７を使うことによって、移動された物理ページ３７はメイン・メモリ２０の中に既に存在している物理ページ３７との間、あるいはディスク２４との間でスワップされる必要はない。
【図面の簡単な説明】
【図１】本発明の特徴を組み込んでいるコンピュータ・システムの一例の単純化されたブロック図である。
【図２】仮想メモリ空間と物理メモリ空間との間の関係を示す図である。
【図３】仮想アドレスから物理アドレスへのマッピング、および仮想アドレスからキャッシュ・インデックスおよびページ・インデックスへのマッピングを示す図である。
【図４】タグ／ステート記憶と一緒に、図１の直接マップ型のキャッシュの単純化されたブロック図である。
【図５】図１のキャッシュ・コントローラのスラッシングの検出および削減の回路を示している単純化されたブロック図である。
【図６】図５のスラッシングの検出および削減の回路の動作を示すフローチャートである。
【図１】
0004128642.tif 000002
【図２】
0004128642.tif 000003
【図３】
0004128642.tif 000004
【図４】
0004128642.tif 000005
【図５】
0004128642.tif 000006
【図６】
0004128642.tif 000007