(57)【要約】【課題】  使用頻度に基づいてラインをキャッシュし続けることができ、キャッシュ・メモリの全ヒット率を潜在的に上げることができるキャッシュ・システムを提供する。  【解決手段】  好適な実施形態では、ＤＦＩキャッシュ（Dynamic Frequent Instruction cache）に、主キャッシュと同時にクエリを行い、要求されたアドレスがいずれかのキャッシュにある場合、ヒットが生じる。ＤＦＩキャッシュは、主キャッシュよりも長く高頻度に用いられる命令を保持するので、主キャッシュは、ラインに次にアクセスする場合に、キャッシュ・ヒットの恩恵を受けながら、ラインを無効にすることができる。【選択図】  図１
2005149497.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システムのためのキャッシュ・システムであって、
複数の第１の命令をストアするための第１のキャッシュと、
複数の第２の命令をストアするための第２のキャッシュと、
を備え、前記複数の第１の命令の各々は対応したカウンタを有し、前記複数の第１の命令のうちある第１の命令がアクセスされた場合、当該第１の対応するカウンタを増分し、
前記第１の対応するカウンタが閾値に達した場合、前記複数の第１の命令のうち前記第１の命令を前記第２のキャッシュにコピーする、キャッシュ・システム。
【請求項２】
前記複数の第２の命令の各々は対応したカウンタを有し、前記複数の第２の命令のうちのある第２の命令がアクセスされた場合、前記複数の第１の他の全てのカウンタを減分する、請求項１に記載のキャッシュ・システム。
【請求項３】
前記第２のキャッシュから前記複数の第１の命令の前記第１の命令にアクセスする、請求項１に記載のキャッシュ・システム。
【請求項４】
前記対応するカウンタはハードウエア・カウンタから成り、
命令をフェッチする場合、当該命令は前記ハードウエア・カウンタ内で前記ハードウエア・カウンタのスタックの最下部に配置され、
前記命令に再びアクセスする場合、当該命令は前記スタック内で上方に移動し、
前記スタックがいっぱいになり、前記スタック内に新たな命令をストアする場合、前記新たな命令は前記ハードウエア・カウンタ内の最下部アドレスを置換する、請求項１に記載のキャッシュ・システム。
【請求項５】
前記第１のキャッシュは命令キャッシュであり、前記第２のキャッシュは、フルアソシアティブ方式で、ＬＰＵ（least recently used）ポリシーに従う、請求項１に記載のキャッシュ・システム。
【請求項６】
コンピュータ・システムにおいてキャッシュを管理する方法であって、
前記第１のキャッシュ内の各命令は対応するカウンタを有し、第１のキャッシュにおいて第１の命令についてチェックするステップと、
前記第１のキャッシュにおいて前記第１の命令が見つかった場合、第１の対応するカウンタを増分するステップと、
前記第１の対応するカウンタの値を閾値と比較するステップと、
前記第１の対応するカウンタが前記閾値を超えた場合、前記第１のキャッシュから第２のキャッシュに前記第１の命令を移動させるステップと、
を備える、方法。
【請求項７】
前記第２のキャッシュから前記第１に命令にアクセスするステップを更に備える、請求項６に記載の方法。
【請求項８】
前記第２のキャッシュの各命令は対応したカウンタを有し、前記第２のキャッシュの命令がアクセスされた場合、前記複数の第２の他の全てのカウンタを減分する、請求項６に記載の方法。
【請求項９】
前記対応するカウンタはハードウエア・カウンタから成り、
命令をフェッチする場合、当該命令は前記ハードウエア・カウンタ内で前記ハードウエア・カウンタのスタックの最下部に配置され、
前記命令に再びアクセスする場合、当該命令は前記スタック内で上方に移動し、
前記スタックがいっぱいになり、前記スタック内に新たな命令をストアする場合、前記新たな命令は前記ハードウエア・カウンタ内の最下部アドレスを置換する、請求項６に記載の方法。
【請求項１０】
前記第１のキャッシュは命令キャッシュであり、前記第２のキャッシュは、フルアソシアライブ方式で、ＬＰＵ（least recently used）ポリシーに従う、請求項６に記載の方法。
【請求項１１】
コンピュータ読み取り可能媒体内のコンピュータ・プログラムであって、
前記第１のキャッシュにおいてデータの各ラインは対応したカウンタを有し、第１のキャッシュにおいてデータの第１のラインについてチェックするための第１の命令と、
前記第１のキャッシュにおいて前記データの第１のラインが見つかった場合、第１の対応するカウンタを増分するための第２の命令と、
前記第１の対応するカウンタの値を閾値と比較するための第３の命令と、
前記第１の対応するカウンタが前記閾値を超えた場合、前記第１のキャッシュから第２のキャッシュに前記データの第１のラインを移動させるための第４の命令と、
を備える、コンピュータ・プログラム。
【請求項１２】
前記第２のキャッシュから前記第１に命令にアクセスするステップを更に備える、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
前記第２のキャッシュの各命令は対応したカウンタを有し、前記第２のキャッシュの命令がアクセスされた場合、前記複数の第２の他の全てのカウンタを減分する、請求項１１に記載のコンピュータ・プログラム。
【請求項１４】
前記対応するカウンタはハードウエア・カウンタから成り、
命令をフェッチする場合、これは前記ハードウエア・カウンタ内で前記ハードウエア・カウンタのスタックの最下部に配置され、
前記命令に再びアクセスする場合、当該命令は前記スタック内で上方に移動し、
前記スタックがいっぱいになり、前記スタック内に新たな命令をストアする場合、前記新たな命令は前記ハードウエア・カウンタ内の最下部アドレスを置換する、請求項１１に記載のコンピュータ・プログラム・プロダクト。
【請求項１５】
前記第１のキャッシュは命令キャッシュであり、前記第２のキャッシュは、フルアソシアティブ方式で、ＬＰＵ（least recently used）ポリシーに従う、請求項１１に記載のコンピュータ・プログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータ・メモリに関し、更に具体的には、頻繁にアクセスされるラインをストアするためのコンピュータ・キャッシュに関する。
【背景技術】
【０００２】
キャッシュとは、コンピュータにおいて用いられる上位レベルのメモリのことを指す。メモリ・システムを選択する場合、設計者は、通常、性能および速度と、コストおよびその他の制約とのバランスを取らなければならない。最も有効な機械を生成可能とするために、通常、多数の種類のメモリが実装される。
【０００３】
ほとんどのコンピュータ・システムにおいては、プロセッサは、最近要求した情報を再び要求する可能性が高い。高速であるが主メモリより容量が小さいキャッシュ・メモリは、プロセッサが用いた命令をストアするために用いられるので、キャッシュにストアされたアドレス・ラインが要求されると、キャッシュは、情報を主メモリから検索しなければならない場合よりも速くプロセッサに情報を提供することができる。従って、キャッシュ・メモリによって性能が向上する。
【０００４】
コンピュータ・システムにおいて、キャッシュ性能は、ますます重要になっている。要求されたラインがキャッシュに保持され、従って主メモリからフェッチする必要がない場合に生じるキャッシュ・ヒットは、コンピュータ・システムにおいて時間およびリソースを節約する。従って、一致するキャッシュ・ヒットの可能性を高め、できる限りミスを少なくするために、いくつかの種類のキャッシュが開発されている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術のシステムにおいて、いくつかの種類のキャッシュが用いられている。命令キャッシュ（I-caches）は、ストレージの時間的および空間的な局所性を利用して、主メモリから命令にアクセスすることに伴う遅延を生じることなく、命令フェッチを可能とする。しかしながら、頻繁に用いられるが時間的または空間的に離れているキャッシュ・ラインは、キャッシュの結合性およびサイズに応じてキャッシュから取り除かれる場合がある。キャッシュ・ミスの時、プロセッサは、主メモリからラインをフェッチする不利を招き、このため全体的な性能が低下する。
【０００６】
従って、ラインの使用頻度に基づいてラインをキャッシュし続けることができ、キャッシュ・メモリの全ヒット率を潜在的に上げることができる方法および装置を有することは有利であろう。
【課題を解決するための手段】
【０００７】
コンピュータ・システムのためのキャッシュ・システムには、第１の複数の命令をストアするための第１のキャッシュと、第２の複数の命令をストアするための第２のキャッシュとが備えられ、第１のキャッシュ内の命令は、命令にアクセスされた場合に増分する関連カウンタを有する。この実施形態では、カウンタが閾値に達すると、関連した命令は第１のキャッシュから第２のキャッシュにコピーされ、これは、第１のキャッシュにストアされるよりも長い間、維持されて、上書きされない。
【０００８】
本発明の新規な特徴と考えられるものは、特許請求の範囲に述べる。しかしながら、本発明自体は、好適な使用態様、更に別の目的および利点と共に、添付図面と関連付けて以下の例示的な実施形態の詳細な説明を参照することによって、最も良く理解されよう。
【発明を実施するための最良の形態】
【０００９】
ここで図面を参照し、特に図１を参照すると、本発明の好適な実施形態による、本発明を実施可能なデータ処理システムの図が示されている。コンピュータ１００は、システム・ユニット１０２、ビデオ・ディスプレイ端末１０４、キーボード１０６、フロッピ・ドライブならびに他の種類の永続的および着脱可能ストレージ媒体を含み得るストレージ・デバイス１０８、マウス１１０を含むものとして図示されている。パーソナル・コンピュータ１００と共に、例えばジョイスティック、タッチパッド、タッチ・スクリーン、トラックボール、マイクロフォン等、追加の入力デバイスが含まれる場合がある。コンピュータ１００は、ニューヨーク州アーモンクに位置するInternational Business Machines Corporationの製品であるＩＢＭ (R)  ＲＳ／６０００コンピュータまたはIntelliStationコンピュータ等の適切なコンピュータを用いて実施可能である。ここに表す図はコンピュータを示すが、本発明の他の実施形態は、ネットワーク・コンピュータ等の他の種類のデータ処理システムにおいて実施することも可能である。また、コンピュータ１００は、好ましくは、コンピュータ１００内で動作するコンピュータ読み取り可能媒体内にあるシステム・ソフトウエアによって実施可能なグラフィカル・ユーザ・インタフェースも含む。
【００１０】
ここで図２を参照すると、本発明を実施可能なデータ処理システムのブロック図が示されている。データ処理システム２００は、本発明のプロセスを実施するコードまたは命令を配置可能な図１のコンピュータ１００等、コンピュータの１例である。データ処理システム２００は、周辺要素相互接続（ＰＣＩ：peripheral component interconnect）ローカル・バス・アーキテクチャを用いる。図示する例はＰＣＩバスを用いるが、ＡＧＰ（Accelerated Graphics Port）およびＩＳＡアーキテクチャ（ＩＳＡ：Industry Standard Architecture）等の他のバス・アーキテクチャも使用可能である。プロセッサ２０２および主メモリ２０４は、ＰＣＩブリッジ２０８を介してＰＣＩローカル・バス２０６に接続されている。また、ＰＣＩブリッジ２０８は、プロセッサ２０２のための統合メモリ・コントローラおよびキャッシュ・メモリを含むことができる。ＰＣＩローカル・バス２０６に対する追加の接続は、直接要素相互接続を介して、または拡張ボードを介して行うことができる。図示の例では、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１０、小型コンピュータ・システム・インタフェースＳＣＳＩホスト・バス・アダプタ２１２、および拡張バス・インタフェース２１４が、直接要素接続によって、ＰＣＩローカル・バス２０６に接続されている。これに対して、オーディ・アダプタ２１６、グラフィクス・アダプタ２１８、およびオーディオ／ビデオ・アダプタ２１９は、拡張スロット内に挿入された拡張ボードによって、ＰＣＩローカル・バス２０６に接続されている。拡張バス・インタフェース２１４は、キーボードおよびマウス・アダプタ２２０、モデム２２２、および追加メモリ２２４のための接続を提供する。ＳＣＳＩホスト・バス・アダプタ２１２は、ハード・ディスク・ドライブ２２６、テープ・ドライブ２２８、およびＣＤ−ＲＯＭドライブ２３０のための接続を提供する。典型的なＰＣＩローカル・バスの実例は、３または４つのＰＣＩ拡張スロットまたは拡張コネクタをサポートする。
【００１１】
プロセッサ２０２上で、オペレーティング・システムが実行し、図２のデータ処理システム２００内の様々な構成要素を調整し制御するために用いられる。オペレーティング・システムは、Microsoft (R)社から入手可能なＷｉｎｄｏｗｓ２０００(R)等の市販のオペレーティング・システムとすることができる。Ｊａｖａ(R)等のオブジェクト指向プログラミング・システムが、オペレーティング・システムと関連して実行する場合があり、データ処理システム２００上で実行するＪａｖａ(R)プログラムまたはアプリケーションからオペレーティング・システムへの呼び出しを提供する。「Ｊａｖａ(R)」は、SunMicrosystems, Inc.の商標である。オペレーティング・システム、オブジェクト指向プログラミング・システム、およびアプリケーションまたはプログラムのための命令は、ハード・ディスク・ドライブ２２６等のストレージ・デバイス上に位置し、プロセッサ２０２によって実行するため主メモリ２０４にロードすることができる。
【００１２】
図２のハードウエアは実施に応じて変動し得ることは、当業者には認められよう。図２に示すハードウエアに加えて、またはその代わりに、フラッシュＲＯＭ（または同等の不揮発性メモリ）または光ディスク・ドライブ等、他の内部ハードウエアまたは周辺機器を使用可能である。また、本発明のプロセスは、マルチプロセッサ・データ処理システムにも適用することができる。
【００１３】
例えば、データ処理システム２００は、ネットワーク・コンピュータとして任意選択的に構成される場合、任意選択的な含有を示す図２の点線２３２に示すように、ＳＣＳＩホスト・バス・アダプタ２１２、ハード・ディスク・ドライブ２２６、テープ・ドライブ２２８、およびＣＤ−ＲＯＭ２３０を含まない場合がある。この場合、コンピュータは、クライアント・コンピュータと呼ぶのが適切であるが、ＬＡＮアダプタ２１０、モデム２２２等の何らかのタイプのネットワーク通信インタフェースを含まなければならない。別の例として、データ処理システム２００は、何らかのタイプのネットワーク通信インタフェースに頼ることなく、データ処理システム２００が何らかのタイプのネットワーク通信インタフェースを備えるにしても備えないにしても、ブート可能に構成されたスタンドアロンのシステムとすることができる。更に別の例として、データ処理システム２００は、パーソナル・デジタル・アシスタント（ＰＤＡ：personal digital assistant）とすることができ、オペレーティング・システム・ライフおよび／またはユーザが発生したデータをストアするための不揮発性メモリを提供するＲＯＭおよび／またはフラッシュＲＯＭと共に構成する。
【００１４】
図２の図示した例および上述の例は、アーキテクチャの限定を暗示することを意図していない。例えば、データ処理システム２００は、ＰＤＡの形態を取ることに加えて、ノートブック・コンピュータまたはハンドヘルド・コンピュータとすることも可能である。データ処理システム２００は、キオスク（kiosk）端末またはウエブ端末装置とすることも可能である。
【００１５】
本発明のプロセスは、例えば、主メモリ２０４、メモリ２２４等のメモリ、または１つ以上の周辺機器２２６〜２３０に位置することができるコンピュータが実施する命令を用いて、プロセッサ２０２によって実行される。
【００１６】
本発明は、例えば図１および２に示すシステムのようなコンピュータ・システムのための革新的なキャッシュ・システムを教示する。好適な実施形態では、本発明のキャッシュは、例えば、主メモリ２０４または他のキャッシュ・メモリの一部として実施される。
【００１７】
好適な実施形態の1例として、例えば命令キャッシュ（Ｉキャッシュ（I-cache））のような主キャッシュと共に、動的頻度命令キャッシュ（ＤＦＩ−ｃａｃｈｅ：DynamicFrequent Instruction cache）を実施する。双方のキャッシュには同時にクエリを行うので、いずれかのキャッシュにラインが保持されている場合、クエリは結果としてヒットとなる。
【００１８】
一実施形態では、主キャッシュにおける各ラインに、そのアドレス・ラインがアドレスされた場合にいつでも増分する関連カウンタを取り付けられる。カウンタがある数に達すると、そのラインは主キャッシュから除去されてＤＦＩキャッシュに配置される。ＤＦＩキャッシュは、これによって、主キャッシュよりも長く頻繁にアクセスされるラインを保持する。
【００１９】
別の実施形態では、主キャッシュに、最も多く参照されたラインをカウントするハードウエア・カウンタを追加する。主キャッシュからあるアイテムが取り除かれる場合、最高のカウンタ値が、どのラインを除去するかを決定する。除去されたラインは、好ましくはＤＦＩキャッシュに移されるので、最も頻繁にアクセスされるラインはキャッシュに長く残る。
【００２０】
図３は、本発明の好適な実施形態に一致する、コンピュータ・システムのキャッシュ・アーキテクチャを示す。この例では、２つのキャッシュを示す。すなわち、第１のキャッシュ３０２（命令キャッシュすなわちＩキャッシュ等）および動的頻度命令（ＤＦＩ）キャッシュ３００である。この例の第１のキャッシュ３０２は、Ｉキャッシュ３０２の各ライン３０６Ａ〜Ｃに対応するカウンタ３０８Ａ〜Ｃのためのスペースを含む。各ライン３０６Ａ〜Ｃには、カウンタ３０８Ａ〜Ｃの１つのカウンタが取り付けられ、ライン３０６Ａ等のラインがアクセスされると、そのカウンタ３０８Ａが増分される。この例は、第１のキャッシュとしてＩキャッシュに対する参照を行うが、他のタイプのキャッシュをその代わりに実施可能であることに留意すべきである。他のタイプのキャッシュとは、例えば、N. P. Jouppiによる、ＩＥＥＥ、ＣＨ２８８７−８／９／９０に発表された、「Improving Direct-Mapped Cache Performance by the Addition of a SmallFully-Associative Cache and Prefetch Buffers」に記載されたビクティム・キャッシュ（victim cache）等である。この文献は、参照により本願にも含まれるものとする。
【００２１】
カウンタが、所定の閾値（または、実施によっては可変閾値）に達した場合、ラインはＩキャッシュ３０２から除去されて、ＤＦＩキャッシュ３００内、例えばライン３０４Ａに配置される。この例では、ＤＦＩキャッシュは充分に関連付けられ、新しいラインを加える場合にどのラインを上書きするかを決定するためのＬＲＵ（Least Recently Used）ポリシーに従う。
【００２２】
ＤＦＩキャッシュは、追加キャッシュであり、例えば関連カウンタが閾値に達したことによって頻度が高いと決定した命令ラインをストアする。上述の例では、ＩキャシュおよびＤＦＩキャッシュで、好ましくは同時にクエリを行う。求められた命令が、ＤＦＩキャッシュまたはＩキャッシュにある場合、ヒットが生じる。ＤＦＩは、ある命令を頻度が高いと決定した場合に更新される。
【００２３】
本発明は、関連カウンタが閾値に達することによって「高頻度」命令ラインを説明するが、本発明の範囲内で、命令を「高頻度」と指定する他の方法も実施可能である。
【００２４】
ＤＦＩは、通常の命令キャッシュよりもキャッシュ内に高頻度で用いるラインを長く保持するので、通常の命令キャッシュは、高頻度で用いるラインと見なされたラインを含めて、ラインを無効にすることができる。かかる命令が再び要求された場合、これはＤＦＩキャッシュ内で見つかり、ヒットが生じる。従って、本発明の機構によって、いくつかのキャッシュ・ミスがヒットへと変わる。ラインがＤＦＩキャッシュのみで見つかった場合、そのラインはＤＦＩキャッシュのみに維持することができ、またはＤＦＩキャシュから削除して主キャッシュにコピーすることができ、またはＤＦＩキャッシュに保持して主キャッシュにコピーすることができる。好適な実施形態では、ＤＦＩキャッシュ内のアクセスされたラインの頻度も、カウンタを用いて測定する。例えば、最後の「Ｘ」回のアクセスを追跡するアルゴリズムを用いることができる。「Ｘ」は所定の数である。また、本発明の範囲内で、ＤＦＩキャッシュにおけるアクセスされたラインの頻度を追跡する他の方法も実施可能である。
【００２５】
ＤＦＩキャッシュは、ダイレクトマップ方式またはセットアソシアティブ方式のキャッシュとして構成することができ、そのサイズは、空間および性能の間の必要なトレードオフを与えるように選択すると好ましい。
【００２６】
別の例示的な実施形態では、キャッシュ・ライン３０６Ａにアクセスする場合に実施される、Ｉキャッシュ３０２の高頻度で用いられるキャッシュ・ライン３０６Ａに関連付けたカウンタ３０８Ａ等のカウンタを増分するだけでなく、Ｉキャッシュ３０２における他のキャッシュ・ラインに関連付けたカウンタを減分する。Ｉキャッシュにおいてラインを置換する場合、最小カウンタ数を有するラインを置換のために選択する。
【００２７】
このプロセスによって、ＤＦＩキャッシュ３００は、高頻度でアクセスされ、より長く保持される、もっと高いカウンタ値を有するラインを保持することができる。
【００２８】
図４は、本発明の好適な実施形態を実施するためのフローチャートを示す。この例のプロセスでは、例えばキャッシュ３０２のような主キャッシュにおいてキャッシュ・ヒットが起こると、カウンタを増分する。主キャッシュ３０２のラインのカウンタが閾値を超えると、そのラインは高頻度であると見なされ、そのラインは補助キャッシュに移動する。この例では、このように主キャッシュから補助キャッシュに移動したデータは、補助キャッシュからアクセスされる。
【００２９】
この例のプロセスでは、図３のキャッシュ３０２に類似した主キャッシュおよび図３のＤＦＩキャッシュ３００に類似した補助キャッシュを説明する。このプロセスは、主キャッシュにおいてメイン・アドレスを見つけたか否かのチェックによって開始する（ステップ４０２）。メモリ・アドレスが見つかると、そのキャッシュ・ラインに対応したカウンタを増分する（ステップ４０４）。カウンタが閾値を超えると（ステップ４０６）、補助キャッシュをチェックしてそれがいっぱいかどうかを調べる（ステップ４０８）。カウンタが閾値を超えない場合、データは単に主キャッシュからアクセスされ（ステップ４１６）、プロセスは終了する。
【００３０】
カウンタが閾値を越え、補助キャッシュがいっぱいである場合、補助キャッシュのエントリを置換のために選択する（ステップ４１０）。補助キャッシュがいっぱいでない場合、または補助キャッシュのエントリを置換のために選択した後、キャッシュ・ラインを主キャッシュから補助キャッシュに移動させる（ステップ４１２）。これは、主メモリからのキャッシュ・ラインの除去を含むことに留意すべきである。次に、データは、補助キャッシュからアクセスされ（ステップ４１４）、プロセスは終了する。
【００３１】
ステップ４０２において求めたメモリ・アドレスが主キャッシュ内で見つからない場合、補助キャッシュでメモリ・アドレスをチェックする（ステップ４１８）。これが見つかった場合、プロセスはステップ４１４に移り、データは補助キャッシュからアクセスされる（ステップ４１４）。補助キャッシュにメモリ・アドレスが存在しない場合、主キャッシュをチェックして、これがいっぱいかどうかを調べる（ステップ４２０）。主キャッシュがいっぱいである場合、主キャッシュのエントリを置換のため選択し（ステップ４２２）、データをコンピュータ・システムの主メモリから主キャッシュ内に移し（ステップ４２４）、プロセスは終了する。主キャッシュがいっぱいでない場合、データを主メモリから主キャッシュに移し（ステップ４２４）、プロセスは終了する。
【００３２】
図５は、本発明の好適な実施形態を実施するための別のフローチャートを示す。この例では、選択されたラインがキャッシュ内で見つかった場合、キャッシュ３０２の選択したライン３０６Ａのためのカウンタ３０８Ａを増分し、一方、他の全てのキャッシュ・ライン３０８Ｂ、３０６Ｃ等のためのカウンタ３０８Ｂ、３０８Ｃ等を減分する。キャッシュにおいてキャッシュ・ラインの置換が必要な場合、最少のカウンタを有するキャッシュ・ライン（従って、アクセス頻度が最低のもの）を置換する。
【００３３】
このプロセスは、キャッシュにおいてメモリ要求を受信することから開始する（ステップ５０２）。この例では、記載するキャッシュは、図３の主キャッシュ３０２に類似したものである。このキャッシュは、好ましくは、キャッシュの各ラインまたはメモリ・アドレスに関連したカウンタが備えられている。所望のアドレスがキャッシュ内にある場合（ステップ５０４）、そのラインの関連カウンタを増分する（ステップ５０６）。また、他の全てのカウンタを減分し（ステップ５０８）、プロセスは終了する。
【００３４】
所望のアドレスがキャッシュ内に存在しない場合（ステップ５０４）、最少のカウンタを有するキャッシュ・ラインを置換のために選択する（ステップ５１２）。次いで、選択したキャッシュ・ラインを新しいデータによって置換する（ステップ５１４）。そして、プロセスは終了する。
【００３５】
図６および７は、本発明の別の実施を示す。この例では、ハードウエア・カウンタ・スタック６００は、「Ａｄｄｒ８」６０４および「Ａｄｄｒ３」６０２を含む、個別のアドレス・ラインに関連したカウンタを示す。
【００３６】
この例では、主キャッシュは、図３に示したものと同じであるが、最も多く参照されたラインをカウントするハードウエア・カウンタ６００があることが異なる。アドレス・ラインがフェッチされると、これはハードウエア・カウンタ内のスタック最下部に配置される。そのアドレス・ラインが再びアドレスされると、その関連カウンタが増分し、そのアドレス・ラインはスタックを上昇する。このため、スタック内の上方のエントリは、スタック内の下方のエントリよりも多く参照されている。ハードウエアが、アドレス・ラインのためのカウンタでいっぱいになった場合、かつ新たなアドレス・ラインが参照された場合、スタックの最下部アドレス・ラインを置換のため選択する。
【００３７】
図６は、スタック内でアドレス３（６０２）がアドレス８（６０４）の下にある場合の例を示す。この場合、アドレス３（６０２）は、アドレス８（６０４）よりも小さいカウンタ値を有する。アドレス３（６０２）がもっとアクセスされると、そのカウンタ値が増加し、最終的にアドレス８（６０４）のカウンタ値を超える。図７は、アドレス３（６０２）のカウンタ値がアドレス８（６０４）よりも高くなった後のそれらの相対的な位置を示す。図７において、アドレス３（６０２）は、スタック内でアドレス８（６０４）よりも上方にある。この例で、新しいアドレスを参照すると、以下で説明するように、アドレスに関連するカウンタを置換のため選択する。
【００３８】
本発明のこのハードウエア・カウンタは、例えば、主キャッシュからどのアドレスを補助キャッシュに移すべきかを決定する際、および、補助キャッシュ（例えばＤＦＩキャッシュ）がいっぱいの場合にキャッシュ内のどのラインを除去するかを決定するために有用である。例えば、一実施形態では、主キャッシュがＩキャッシュであり、補助キャッシュがＤＦＩキャッシュである。Ｉキャッシュ内のアドレスは、各々、ハードウエア・カウンタ６００内の位置を有する。Ｉキャッシュがいっぱいであり、別のアドレス・ラインを追加しなければならない場合、アドレス・ラインを追い出して、空き場所を作らなければならない。Ｉキャッシュのどのラインを追い出すかの決定（および、好ましくは、ＤＦＩキャッシュに書き込む）は、ハードウエア・カウンタ６００を参照して行う。好適な実施形態では、最も頻繁にアクセスされたライン、すなわちハードウエア・カウンタ・スタック６００において最上部にあるものをＩキャッシュから除去する。この例では、新しいアドレスを加える場合、スタックの最下部に加えられるが、アドレス１は、Ｉキャッシュから完全に除去され、ＤＦＩキャッシュに配置される。アイテムがＩキャッシュから除去される場合、カウンタ６００からも除去される。
【００３９】
別の実施形態では、ＤＦＩキャッシュの各ラインは、それに関連したカウタンを有する。ＤＦＩキャッシュのラインがヒットすると、ＤＦＩキャッシュの他のラインに関連したカンタの値を減分する。このため、ＤＦＩキャッシュ内の高頻度で用いられるラインは、もっと低頻度で用いられるラインよりも高い値を有する。ＤＦＩキャッシュにおいてラインを置換する場合は、最小カウンタ数を有するラインを置換する。このように、ＤＦＩキャッシュは、高頻度で用いられるラインをＩキャッシュよりも長く保持する。
【００４０】
ＤＦＩキャッシュからラインを除去する場合、他の方法を用いてどのラインを除去するかを決定することができる。場合によっては、ヒットの最も少ないラインを除去することは望ましくないか、または非効率的であり得る。本発明の状況において、ワーキング・セット置換アルゴリズム等、ページ置換のための既知のアルゴリズムを実施可能である。かかるアルゴリズムは、経時的に動くウインドウを用い、指定した時間内に参照されないページまたはラインは、ワーキング・セットまたはキャッシュから除去される。
【００４１】
留意すべき重要なこととして、本発明は完全に機能するデータ処理システムに関連付けて説明したが、本発明のプロセスは、命令のコンピュータ読み取り可能媒体の形態および様々な形態で分配することができ、本発明は、この分配を実行するために実際に用いる信号搬送媒体の特定の種類には無関係に等しく適用されることは、当業者には理解されるであろう。コンピュータ読み取り可能媒体の例は、フロッピ・ディスク、ハード・ディスク・ドライブ、ＲＡＭ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の記録可能型媒体、ならびに、デジタルおよびアナログ通信リンク、例えば無線周波数および光波伝送等の伝送形態を用いた有線または無線通信リンク等の伝送型媒体を含む。コンピュータ読み取り可能媒体は、特定のデータ処理システムにおいて実際に用いるために復号される符号化フォーマットの形態を取ることができる。
【００４２】
本発明の記載は、例示および説明の目的のために提示し、包括的であることまたは開示した形態に本発明を限定することは意図していない。多くの修正および変更は、当業者には明らかであろう。実施形態は、本発明の原理、実際の用途を最も良く説明するため、更に、当業者に、本発明を理解させ、考えられる特定の使用に適切な様々な修正によって様々な実施形態を理解させるために、選択し記載したものである。
【図面の簡単な説明】
【００４３】
【図１】本発明の好適な実施形態の実施と一致するコンピュータ・システムのブロック図である。
【図２】本発明の好適な実施形態の実施と一致する例示的なコンピュータ・システムの構成要素の図を示す。
【図３】本発明の好適な実施形態によるキャッシュ・システムを示す。
【図４】本発明の好適な実施形態の実施と一致するプロセス・ステップのフローチャートを示す。
【図５】本発明の好適な実施形態の実施と一致するプロセス・ステップのフローチャートを示す。
【図６】本発明の好適な実施形態と一致するハードウエア・カウンタ・スタックを示す。
【図７】本発明の好適な実施形態と一致するハードウエア・カウンタ・スタックを示す。
【図１】
2005149497.tif 000003
【図２】
2005149497.tif 000004
【図３】
2005149497.tif 000005
【図４】
2005149497.tif 000006
【図５】
2005149497.tif 000007
【図６】
2005149497.tif 000008
【図７】
2005149497.tif 000009