JP6392286B2 - マルチレベルのキャッシュ階層におけるキャストアウトを低減するための装置および方法 - Google Patents

Description

本開示は、一般に、キャッシュメモリの分野に関し、より明確には、命令、データおよびビクティムキャッシュを有するメモリシステムに関する。

携帯電話、ラップトップコンピュータ、携帯情報端末(personal digital assistant)（ＰＤＡ）などのような多くのポータブル製品は、通信およびマルチメディアプログラムのようなプログラムを実行するプロセッサを利用する。そのような製品の処理システムは、命令およびデータを記憶するためのプロセッサおよびメモリコンプレックス（memory complex）を含む。大容量メインメモリは、一般的に、プロセッササイクル時間と比較して、遅いアクセス時間を有している。結果として、メモリコンプレックスは、従来、キャッシュメモリの容量およびパフォーマンスに基づいた階層で、最も高いパフォーマンスおよび最も低い容量のキャッシュがプロセッサに最も近く位置して、構成されている。例えば、レベル１命令キャッシュおよびレベル１データキャッシュは、一般に、プロセッサに直接アタッチ（attach）されるであろう。そしてレベル２ユニファイキャッシュ（unified cache）は、レベル１（Ｌ１）命令およびデータキャッシュに接続される。さらに、システムメモリは、レベル２（Ｌ２）ユニファイキャッシュに接続される。レベル１命令キャッシュは、一般に、プロセッサの速度で動作し、レベル２ユニファイキャッシュは、レベル１キャッシュより遅く動作するがシステムメモリより速いアクセスタイムを有している。他のメモリ構成は豊富であり、例えば、メモリ階層は、Ｌ１およびＬ２キャッシュに加えてレベル３キャッシュを有する。他のメモリ構成は、レベル１キャッシュおよびシステムメモリのみを使用することがある。

メモリ構成は、包含的キャッシュ（inclusive cache）、狭義包含的キャッシュ（strictly inclusive cache）、排他的キャッシュ（exclusive cache）、またはこれらのキャッシュタイプの組み合わせとして動作するキャッシュの階層から構成されることがある。ここの定義によって、互いに排他的な任意の２つのレベルのキャッシュは、同じキャッシュラインを含むことができない。互いに包含的な任意の２つのレベルのキャッシュは、同じキャッシュラインを含むことができる。互いに狭義に包含的な任意の２つのレベルのキャッシュは、より大きなキャッシュ、通常、上位レベルキャッシュがより小さなキャッシュ、通常、下位レベルキャッシュにおける全てのラインを含まなければならないことを意味する。３つ以上のマルチレベルキャッシュメモリ構成において、任意の２つ以上のキャッシュレベルは、排他的のように１つのタイプのキャッシュとして作動することがあり、残りのキャッシュレベルは、包含的のように１つの他のタイプのキャッシュとして動作することがある。

命令キャッシュは、一般に、命令キャッシュにおいて単一のアドレスに位置する複数の命令をサポートするように構築される。データキャッシュは、一般に、データキャッシュにおいて単一のアドレスに位置する複数のデータユニットをサポートするために構築される、ここでデータユニットはプロセッサに依存するバイトの可変数であることがある。この複数の命令またはデータユニットは、一般に、キャッシュラインまたは単にラインと呼ばれる。例えば、プロセッサは、Ｌ１キャッシュからの命令またはデータユニットをフェッチし、命令またはデータユニットがキャッシュにおいて存在する場合、「ヒット（hit）」が生じ、命令またはデータユニットがプロセッサに提供される。命令またはデータユニットがＬ１キャッシュにおいて存在しない場合、「ミス（miss）」が生じる。ミスは、キャッシュラインにおいていかなる場所の命令またはデータユニットアクセスに生じることがある。ミスが生じたとき、キャッシュにおけるラインは、ミスされた命令を含む新しいラインと置換される。置換手段は、どのキャッシュラインを置換するか決定するために使用される。例えば、最も使用されていないキャッシュラインを選択するかビクティムすることは、最長時間未使用（least recently used）（ＬＲＵ）手段を表す。置換されるように選択されたキャッシュラインは、ビクティムキャッシュラインである。

キャッシュラインは、さらに、有効ビットおよびダーティ（dirty）ビットのような多数のステータス（status）ビットと関連されることがある。有効ビットは、命令またはデータがキャッシュラインにおいて存在することを示す。ダーティビットは、キャッシュラインへの変更が生じたかどうかを示す。ライトバック（write-back）キャッシュにおいて、ダーティビットは、キャッシュラインが置換されることになっているとき、メモリシステム階層における次の上位メモリレベルに変更がライトバックされる必要があることを示す。

ビクティムキャッシュは、レベル１キャッシュのようなキャッシュに接続された、または、隣接する上位レベルキャッシュに一体化された別個のバッファであることがある。ビクティムキャッシュラインは、ビクティムラインが立ち退かせられる直後に必要であること、および、ビクティムキャッシュからの要求があるときビクティムラインにアクセスすることが上位レベルのメモリ階層からビクティムラインにアクセスするより早いという想定のもとにビクティムキャッシュにおいて割り当てられることがある。ビクティムキャッシュが隣接する上位レベルキャッシュにおいて一体化されたと同時に、ラインが下位レベルキャッシュから置換されたとき、および、上位レベルキャッシュに割り当てられたときにキャストアウトが生じ、これにより、下位レベルキャッシュのビクティムをキャッシュする。下位レベルキャッシュは、すべての置換されたライン、ダーティおよび非ダーティ（non-dirty）の両方を上位レベルキャッシュに送信する。ある場合において、ビクティムラインは、すでにビクティムキャッシュにおいて存在することがあり、すでに存在するラインを再び書き直すことは電力を消費し、ビクティムキャッシュへの帯域幅を低減する。

本開示は、メモリシステムにおける電力要求を低減することがポータブルアプリケーションにとって、および、一般に、処理システムにおける電力要求を低減することにとって重要であることを認識する。そのような目的のために、発明の実施形態は、置換されたキャッシュラインの割り当てを低減するためのトラッキング方法をアドレスする。ラインは、下位レベルキャッシュにおいて置換されるために選択されている。選択されたラインが上位レベルキャッシュに存在することを示す選択されたラインに関連した情報は、識別される。上位レベルキャッシュにおける選択されたラインの割り当ては、識別された情報に基づいて防がれる。選択されたラインの割り当てを防ぐことは、割り当てに関連するであろう電力を節約する。

発明の他の実施形態は、キャストアウトを低減する方法をアドレスする。レベルＸキャッシュにおけるミスに応じて、割り当て情報は、ミスに関連したキャッシュラインのタグのレベルＸキャッシュにおいて保管される。割り当て情報は、キャッシュラインがレベルＸ＋１キャッシュにおいて割り当てられていたかどうかを示す。ラインは、レベルＸキャッシュにおいて置換されるために選択される。レベルＸキャッシュからレベルＸ＋１キャッシュへの選択されたラインのキャストアウトは、レベルＸ＋１キャッシュにおいてキャッシュラインが割り当てられたことを示す、選択されたラインの割り当て情報に応じて防がれる。

発明の他の実施形態は、複数のキャッシュレベルを有するメモリシステムをアドレスする。下位レベルキャッシュは、それぞれ割り当てビットを持つ複数の第１キャッシュラインを記憶するように構成される。複数の第１キャッシュラインのうち１つに関連した割り当てビットは、複数の第１キャッシュラインのうち１つが上位レベルキャッシュにおいて割り当てられたどうかを示す。キャストアウトロジック回路は、複数の第１キャッシュラインからの置換のために選択された第１キャッシュラインが、選択された第１キャッシュラインに関連する割り当てビットに基づいて上位レベルキャッシュにおけるキャッシュラインで過多のキャッシュラインかどうかを決定するように構成される。上位レベルキャッシュへの選択された第１キャッシュラインのキャストアウトは、選択された第１キャッシュラインの割り当てビットに応じて防がれる。

本発明の他の実施形態が、発明の様々な実施形態が示され、例として説明された次の詳細な記述から当業者に容易に明白になるであろうことは理解される。理解されるように、発明は、本発明からすべて外れることなく、他のおよび異なる実施形態があり、そのそれぞれ細部が様々の他の点において変更することできる。したがって、図面および詳細な説明は、限定的ではなく、本質的な例としてみなされることになっている。

図１は、無線通信システムを示す。 図２は、キャストアウトが低減される典型的なプロセッサおよびメモリコンプレックスの機能的なブロック図である。 図３は、キャストアウトを低減するためのプロセスを示すフロー図である。

詳細な説明

添付された図面と関連して下記に説明された詳細な説明は、本発明の様々な典型的な実施形態の説明として意図され、本発明が実施されることがある実施形態のみを表すことを意図していない。詳細な説明は、本発明の理解を提供する目的で特定の詳細を含む。しかしながら、当業者にとって、本発明がこれらの特定の詳細なしで実施されることがあることは明白であろう。ある場合において、よく知られているコンポーネントおよび要素は、本発明の概念を不明瞭にすることを防ぐためにブロック図の形式で示される。

図１は、発明の実施形態が有利に用いられることがある典型的な無線通信システム１００を示す。例として、図１は、３つのリモートユニット１２０、１３０ならびに１５０、および、２つの基地局１４０を示す。共通の無線通信システムがより多くのリモートユニットおよび基地局を有することがあることが認識されるであろう。リモートユニット１２０、１３０および１５０は、コンポーネント１２５Ａ、１２５Ｃおよび１２５Ｂとしてそれぞれ表されるハードウェアコンポーネント、ソフトウェアコンポーネントまたは両方を含む、それはさらに下記に述べられるような発明を具体化するのに適している。図１は、基地局１４０からリモートユニット１２０、１３０および１５０への順方向リンクシグナル１８０、および、リモートユニット１２０、１３０および１５０から基地局１４０への逆方向リンクシグナル１９０を示す。

図１において、リモートユニット１２０は携帯電話として示され、リモートユニット１３０はポータブルコンピュータとして示され、リモートユニット１５０は無線ローカルループ（wireless local loop）システムにおける固定されたロケーションリモート（fixed location remote）ユニットとして示される。例として、リモートユニットは、代替として、携帯電話、ページャ、ウォーキートーキ（walkie talkies）、ハンドヘルド個人用通信システム（handheld personal communication system）（PCS）ユニット個人用データアシスタント（personal data assistant）のようなポータブルデータユニット、またはメータ読み取り機器のような固定されたロケーションデータ（location data）ユニットであることがある。図１は、開示の教えによってリモートユニットを示すが、開示はこれらの典型的に示されたユニットに限定されていない。発明の実施形態は、レベル１キャッシュおよびレベル２キャッシュのようなメモリ階層の少なくとも２つのレベルを備えたプロセッサを有する任意の装置で適切に実施されることがある。

図２は、キャストアウトが低減される典型的なプロセッサおよびメモリコンプレックス２００の機能的なブロック図である。典型的なプロセッサおよびメモリコンプレックス２００は、プロセッサ２０２、Ｌ１キャッシュラインアレイ２０４およびＬ１キャッシュコントロールユニット２０６を備えたレベル１キャッシュ（Ｌ１キャッシュ）２０３、包含的レベル２キャッシュ（Ｌ２キャッシュ）２０８、およびシステムメモリ２１０を含む。Ｌ１キャッシュコントロールユニット２０６は、セットアソシエイティブ（set associative）キャッシュまたは完全アソシエイティブ（fully associative）キャッシュのような様々なタイプのキャッシュにおいて使用されることがあるように、タグのマッチングするためのキャストアウトロジック回路２１２およびレベル１コンテントアドレス指定可能メモリ（content addressable memory）（L1 CAM）２１４を含む。プロセッサコンプレックスに接続されることがある周辺装置は、説明の明瞭さのために示されていない。典型的なプロセッサおよびメモリコンプレックス２００は、キャッシュ２０３ならびに２０８およびシステムメモリ２１０に記憶されたプログラムコードを実行するためのコンポーネント１２５Ａ−Ｃにおいて発明の様々な実施形態において適切に実施されることがある。

Ｌ１キャッシュラインアレイ２０４は、キャッシュライン２１５−２１７のような複数のラインを含むことがある。１つの実施形態において、Ｌ１キャッシュ２０３は、各ラインが複数のデータユニットから構成されたデータキャッシュである。他の実施形態において、Ｌ１キャッシュ２０３は、各ラインが複数の命令から構成された命令キャッシュである。さらなる実施形態において、Ｌ１キャッシュ２０３は、各ラインが複数の命令またはデータユニットから構成されたユニファイキャッシュである。例えば、各ラインは、インスタンス化された（instantiated）キャッシュの実施形態に適切であり、複数の要素（Ｕ０、Ｕ１、…、Ｕ７）２１８−２２５のそれぞれから構成されている。各ラインと関連するのは、さらに下記で詳しく説明されるように、タグ２２６、ダーティビット（Ｄ）２２８、力置換キャストアウトビット（force replacement castout）（FRC）２３０である。キャッシュライン２１５−２１７は、ラインアドレス２３１−２３３のそれぞれにおけるＬ１キャッシュラインアレイ２０４で存在する。Ｌ１キャッシュコントロールユニット２０６は、キャッシュラインにアクセスするためにＩ／ＤＡインターフェース２３５で受信された命令アドレスまたはデータアドレス（Ｉ／ＤＡ）２３４に応答するアドレスコントロールロジックを含む。Ｉ／ＤＡ２３４は、タグ２３６、ラインアドレスフィールド（line address field）２３８、命令／データ「Ｕ」フィールド２４０、およびバイト「Ｂ」フィールド２４２によって構成されることがある。

典型的なプロセッサおよびメモリコンプレックス２００において命令またはデータユニットをフェッチするために、プロセッサ２０２は、フェッチされる所望の命令／データの命令／データアドレス（Ｉ／ＤＡ）２３４を生成し、フェッチアドレスをＬ１キャッシュコントロールユニット２０６へと送信する。受信されたＩ／ＤＡ２３４に基づいて、Ｌ１キャッシュコントロールユニット２０６は、命令またはデータがＬ１キャッシュラインアレイ２０４において存在するかどうかをチェックする。このチェックは、例えば、Ｉ／ＤＡ２３４によって選択されたライン２１５と関連したマッチングするタグ２４４をチェックする比較ロジックの使用を通じて、遂行される。命令またはデータが存在する場合、マッチまたはヒットが生じ、Ｌ１キャッシュコントロールユニット２０６はＬ１キャッシュ２０３において命令またはデータが存在することを示す。命令またはデータが存在しない場合、マッチがないまたはミスが見つかり、Ｌ１キャッシュコントロールユニット２０６はＬ１キャッシュ２０３において命令またはデータが存在しないというミス指示を提供する。

命令またはデータが存在する場合、命令／データフェッチアドレスにおける命令またはデータは、Ｌ１キャッシュラインアレイ２０４から選択される。その後、命令またはデータは、命令／データアウトバス（instruction/data out bus）２４６でプロセッサ２０２に送信される。

命令／データがキャッシュにおいて存在しない場合、ミス情報は、ミスが生じたことを示すミスシグナル２４８によってＬ２キャッシュ２０８に提供される。Ｌ１キャッシュ２０３においてミスを発見する際に、Ｌ２キャッシュ２０８から所望の命令／データをフェッチする試みがなされる。Ｌ２キャッシュ２０８において所望の命令／データが存在する場合、それはメモリバスインターフェース（memory bus interface）２５０で提供される。Ｌ２キャッシュ２０８において所望の命令／データが存在しない場合、それはシステムメモリ２１０からフェッチされる。

Ｌ２キャッシュ２０８からの力置換キャストアウト（force replacement castout）（FRC）シグナル２５４は、メモリバスインターフェース２５０で送信された所望の命令／データとともに下位Ｌ１キャッシュ２０３に送信される。ＦＲＣシグナル２５４は、上位レベルＬ２キャッシュ２０８におけるヒットによって、供給された命令／データが得られたどうかを示す。例えば、「０」状態のＦＲＣシグナル２５４は、所望の命令／データがＬ２キャッシュ２０８から供給されたことを示す。「１」状態のＦＲＣシグナル２５４は、所望の命令／データがシステムメモリ２１０からのように、Ｌ２キャッシュ２０８の上の他のレベルのメモリから供給されたことを示す。ＦＲＣシグナル２５４は、例えば、ライン２１５−２１７のような、適切なキャッシュラインと関連したタグに沿ってＦＲＣビット２５６−２５８としてＬ１キャッシュ２０３において記憶される。要求されたラインがＬ２キャッシュ２０８およびＬ１キャッシュ２０３におけるミスであるとき、Ｌ１キャッシュ２０３がＬ２キャッシュ２０８の上の次のレベルのメモリによって供給されるのに対して、Ｌ２キャッシュ２０８はミスのときラインを割り当てない。

下位レベルキャッシュがラインを置換しなければならないとき、ラインは下位レベルキャッシュにおけるラインとともに記憶された情報に応答して次のレベルのキャッシュにおいて割り当てられることがある。例えば、Ｌ１キャッシュ２０３のような下位レベルキャッシュが、「１」状態のダーティビット２５９によって示されるような、ダーティ指示を備えた、キャッシュライン２１５のような、置換されるラインを選択する場合、キャストアウトロジック回路２１２は、キャッシュライン２１５が次のレベルのメモリ階層に割り当てられるように決定をする。「０」状態のダーティビット２６０を備えたキャッシュライン２１６のような、ダーティでなく、かつ、アクティブ、例えば「１」状態に設定された関連したＦＲＣビット２５６を有している、キャッシュラインが、置換されるために選択される場合、キャッシュライン２１６は、次のレベルのメモリ階層に割り当てられる。ＦＲＣビット２５６は、そのディレクトリにおいてラインが見つからなかった次のレベルのメモリ階層によって提供されたＦＲＣシグナル２５４指示に応じてアクティブに設定される。「０」状態のそのダーティビット２６１を備えたキャッシュライン２１７のような、置換されるために選択されたキャッシュラインが、ダーティでなく、非アクティブ、例えば「０」状態に設定された関連するＦＲＣビット２５８を有している場合、キャッシュライン２１７は、次のレベルのメモリ階層に割り当てられない。キャストアウトは、ラインがダーティでなく、ＦＲＣビット２５８がその非アクティブ状態によって、このキャッシュライン２１７が次のレベルのメモリ階層に存在すると示すため要求されない。つまり、上位レベルキャッシュは、ダーティビットが設定、または、ＦＲＣビットが設定されるとき、下位レベルにおける置換されたキャッシュラインに応答してキャッシュラインを割り当てる。ＦＲＣビットのそのような使用を通じて、過多のキャストアウトは、抑えられ、それによって、上位レベルのメモリ階層への不必要なアクセスを防ぐことによって電力およびアクセスサイクルを節約する。

図３は、キャストアウトを低減するためのプロセス３００を示すフロー図である。プロセス３００において、メモリレベルは、インデックス（Ｘ）、（Ｘ＋１）または（Ｘ＋２）によって示される、ここで、例えば、Ｘ＝１でＬ１、Ｌ２、およびＬ３メモリレベルが示されることがある。さらに、プロセス３００のブロックの説明は、図２における機能的な要素の参照番号を含む。

プロセス３００は、ブロック３０２において命令またはデータユニットをフェッチするプロセッサ２０２のようなプロセッサで始まる。決定ブロック３０４において、要求された命令／データがＬ１キャッシュ２０３のようなＬ（Ｘ）キャッシュに位置することができるかどうか決定される。命令／データが位置することができる場合、要求された命令／データがブロック３０６でＬ（Ｘ）キャッシュからフェッチされ、命令／データがブロック３０８でプロセッサに戻る。

命令／データがＬ（Ｘ）キャッシュに位置することができない場合、ミス指示が生成され、ブロック３１０において、要求された命令／データがＬ２キャッシュ２０８のようなＬ（Ｘ＋１）キャッシュにおいて位置することができるかどうかを判断する。命令／データが位置することができる場合、要求された命令／データがブロック３１６でＬ（Ｘ＋１）キャッシュからフェッチされる。ブロック３１８において、ＦＲＣビット２５８のような力置換キャストアウト（FRC）ビットは、Ｌ１キャッシュ２０３がＬ２キャッシュ２０８にこの命令／データを送信することを防ぐために、Ｌ１キャッシュ２０３の、キャッシュライン２１７に関連するような、タグラインで「０」状態に設定される。

ブロック３１０に戻って、命令／データがＬ（Ｘ＋１）キャッシュにおいて位置することができない場合、ミス指示が生成される。ブロック３１２において、要求された命令／データは、プロセッサおよびメモリコンプレックス２００のシステムメモリ２１０またはＬ３キャッシュのような、Ｌ（Ｘ＋２）レベル以上のメモリ階層のレベルからフェッチされる。ブロック３１４において、ＦＲＣビット、例えば、ＦＲＣビット２５６は、「１」状態に設定され、キャッシュライン２１６のような、選択されたラインに関連したタグとともに記憶される。

決定ブロック３２０において、Ｌ１キャッシュ２０３のような、Ｌ（Ｘ）キャッシュにおいてラインが置換されるべきかどうか決定される。Ｌ（Ｘ）においてラインが置換されるべきことが決定した場合、それはさらに決定ブロック３２２において、選択されたライン、ビクティムラインが、「１」状態のダーティビット２５９によって示されるように、ダーティかどうか決定される。選択されたビクティムラインがダーティである場合、ビクティムラインは、ブロック３２４で、Ｌ２キャッシュ２０８のような、Ｌ（Ｘ＋１）キャッシュにおいて割り当てられる。ダーティビット２６０および２６１によって示されるように、選択されたビクティムラインがダーティでない場合、ＦＲＣビットは、決定ブロック３２６においてアクティブに設定されているかどうか決定するためにチェックされる。決定ブロック３２６において、ＦＲＣビット２５６のケースのように、ＦＲＣビットがアクティブであると決定された場合、ビクティムラインは、ブロック３２４で、Ｌ２キャッシュ２０８のような、Ｌ（Ｘ＋１）キャッシュにおいて割り当てられる。

決定ブロック３２０においてラインが置換されるべきでないと決定された場合、または、決定ブロック３２６において、ＦＲＣビットが、ＦＲＣビット２５８のケースのように、「０」状態のような、非アクティブであると決定された場合、要求された命令／データは、ブロック３２８で、Ｌ１キャッシュ２０３のような、Ｌ（Ｘ）キャッシュにおいて割り当てられる。要求された命令／データは、さらに、ブロック３３０においてプロセッサ２０２のような要求プロセッサに戻る。そのような方法において、Ｌ（Ｘ＋１）キャッシュへの過多のキャストアウトが防がれ、それによって電力を節約し、メモリ階層においてキャッシュアクセス帯域幅を改善する。

本明細書に開示された実施形態と関連して説明された様々な例となるロジカルブロック、モジュール、回路、要素、および／またはコンポーネントは、汎用プロセッサ（general purpose processor）、デジタルシグナルプロセッサ（digital signal processor）（ＤＳＰ）、特定用途向け集積回路（application specific integrated circuit）（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（field programmable gate array）（ＦＰＧＡ）または他のプログラマブルロジックコンポーネント、ディスクリートゲート（discrete gate）またはトランジスタロジック、ディスクリートハードウェア（discrete hardware）コンポーネント、または、本明細書で説明された機能を実行するように設計されたそれらの任意の組み合わせ、とともに実装または実行されることがある。汎用プロセッサは、マイクロプロセッサであることがあるが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または、定常マシンであることがある。プロセッサは、計算デバイスの組み合わせ、例えば、ＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰのコアと接続された１つ以上のマイクロプロセッサ、または他の任意のそのような構成として実施されることもある。

本明細書に開示された実施形態と関連して説明された方法は、ハードウェア、プロセッサによって実行されたソフトウェアモジュール、または２つの組み合わせに直接実施されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭ（登録商標）メモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または、当業者において知られている記憶媒体の形式に存在してもよい。記憶媒体は、記憶媒体からプロセッサが情報を読み込み、記憶媒体に情報を書き込むことができるようなプロセッサにつながれることがある。代替として、記憶装置は、プロセッサと一体的であることがある。

発明が、命令キャッシュ、データキャッシュ、および他のタイプのキャッシュについての例となる実施形態のコンテキストに示される一方で、様々な広いインプリメンテーションが、上述した説明および下記に続く請求項と一致して、当業者によって使用されることが認識されるであろう。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
置換されたキャッシュラインの割り当てを低減するためのトラッキング方法であって、
下位レベルキャッシュにおいて置換されるべきラインを選択することと、
前記選択ラインが上位レベルキャッシュに存在すると示す前記選択されたラインと関連する情報を識別することと、
前記識別された情報に基づいて前記上位レベルキャッシュにおいて前記選択されたラインの割り当てを防ぐことと、
を備えたトラキング方法。
［Ｃ２］
前記下位レベルキャッシュにおけるミスに応じて、ミスによって前記下位レベルキャッシュにおいて割り当てられたキャッシュラインのタグを有する割り当て情報、前記キャッシュラインが前記上位レベルキャッシュにおいて割り当てられたかどうかを示す割り当て情報を記憶することと、
をさらに備えたＣ１のトラッキング方法。
［Ｃ３］
前記選択されたラインをダーティとして識別することと、
前記上位レベルキャッシュにおいて前記選択されたラインを割り当てることと、
をさらに備えたＣ１のトラッキング方法。
［Ｃ４］
前記選択されたラインを表す前記選択されたラインと関連する前記識別された情報が前記上位レベルキャッシュにおいて存在しないと決定することと、
前記上位レベルキャッシュにおける前記選択されたラインを割り当てることと、
をさらに備えたＣ１のトラッキング方法。
［Ｃ５］
前記選択されたラインをダーティでないとして識別することと、をさらに備えたＣ１のトラッキング方法。
［Ｃ６］
前記上位レベルキャッシュからデータユニットをフェッチすることと、
前記割り当て指示を前記上位レベルキャッシュにおいて前記データユニットが存在することを表す状態に設定することと、
をさらに備えたＣ２のトラッキング方法。
［Ｃ７］
前記上位レベルキャッシュの上の前記メモリ階層のレベルからデータユニットをフェッチすることと、
前記割り当てられた指示を前記上位レベルキャッシュにおいて前記データユニットが存在しないと表す状態に設定することと、
をさらに備えたＣ２のトラッキング方法。
［Ｃ８］
前記上位レベルキャッシュは、ビクティムキャッシュとして動作するＣ１のトラッキング方法。
［Ｃ９］
キャストアウトを低減する方法であって、
レベルＸキャッシュにおけるミスに応じて、前記ミスに関連するキャッシュラインのタグにおける割り当て情報、レベルＸ＋１キャッシュにおいて前記キャッシュラインが割り当てられたかどうか識別する割り当て情報を、レベルＸキャッシュにおいて記憶することと、
前記レベルＸキャッシュにおいて置換されるべきラインを選択することと、
前記レベルＸ＋１キャッシュにおいて前記キャッシュラインが割り当てられたか示す前記選択されたラインの前記割り当てられた情報に応じて、レベルＸキャッシュからレベルＸ＋１キャッシュへの前記選択されたラインのキャストアウトを防ぐことと、
を備えたトラッキング方法。
［Ｃ１０］
前記選択されたラインをダーティとして識別することと、
前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと、
をさらに備えたＣ９の方法。
［Ｃ１１］
前記選択されたラインを示す前記選択されたラインと関連する前記割り当て情報が前記レベルＸ＋１キャッシュにおいて存在しないことを決定することと、
前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと、
をさらに備えたＣ９の方法。
［Ｃ１２］
前記選択ラインをダーティでないとして識別することと、
をさらに備えたＣ９の方法。
［Ｃ１３］
前記レベルＸ＋１キャッシュからデータユニットをフェッチすることと、
前記割り当て情報を前記データユニットが前記レベルＸ＋１キャッシュにおいて存在することを表す状態に設定することと、
をさらに備えたＣ９の方法。
［Ｃ１４］
前記レベルＸ＋１キャッシュの上のメモリ階層のレベルからデータユニットをフェッチすることと、
前記割り当て情報を前記データユニットが前記レベルＸ＋１キャッシュに存在しないことを表す状態に設定することと、
をさらに備えたＣ９の方法。
［Ｃ１５］
前記レベルＸキャッシュは、レベルＸの命令キャッシュであるＣ９の方法。
［Ｃ１６］
複数のキャッシュレベルを有するメモリシステムであって、
複数の第１キャッシュラインのそれぞれを割り当てビットで記憶するように構成された下位レベルキャッシュと、割り当てビットのそれぞれは前記割り当てビットと関連する前記第１キャッシュラインが上位レベルキャッシュにおいて割り当てられたかどうかを示す、
前記複数の第１キャッシュラインから置換するために選択された第１キャッシュラインが、前記選択された第１キャッシュラインと関連する前記割り当てビットに基づいて前記上位レベルキャッシュにおいてキャッシュラインで過多の（redundant）キャッシュラインであるかどうかを決定するように、および、前記選択された第１キャッシュラインの前記割り当てビットに応じて前記選択された第１キャッシュラインの前記上位レベルキャッシュへのキャストアウトを防ぐように、構成されたキャストアウトロジック回路と、
を備えたメモリシステム。
［Ｃ１７］
前記上位レベルキャッシュは、
複数の第２キャッシュラインと、
前記下位レベルキャッシュにおけるミスに応じ、前記ミスに関連した前記キャッシュラインが前記上位レベルキャッシュにおいて割り当てられたかどうかに基づく割り当てシグナルを生成するように構成されたロジック回路と、前記割り当てシグナルは前記ミスがキャッシュラインと関連すると記憶のために前記下位レベルキャッシュと通信する、
を備えたＣ１６のメモリシステム。
［Ｃ１８］
前記キャストロジック回路は、前記割り当てビットを前記割り当てシグナルの前記状態に設定することをさらに備えたＣ１７のメモリシステム。
［Ｃ１９］
前記下位レベルキャッシュは、データキャッシュであるＣ１６のメモリシステム。
［Ｃ２０］
前記上位レベルキャッシュは、ユニファイドキャッシュであるＣ１７のメモリシステム。

Claims (22)

1. コンピュータ可読プログラムデータおよびコードで符号化されたコンピュータ可読非一時的媒体であって、前記プログラムデータおよびコードは、実行されたとき、
   レベルＸ＋１キャッシュにおいてフェッチアドレスをヒットさせるメモリアクセスに応じて、レベルＸキャッシュにおいて置換されるべき選択されたラインにアクセスすることと、
   前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在しないことを示す割り当て指示、および前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在することを示す割り当て指示に応じて、前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと
   を行うように動作可能であるコンピュータ可読非一時的媒体。
2. 実行されたとき、
   前記選択されたラインをダーティとして識別することと、
   前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと、
   を行うように動作可能であるデータおよび命令をさらに備えた請求項１のコンピュータ可読非一時的媒体。
3. アサートされていないダーティビットは、前記選択されたラインが修正されていないことを示す請求項１のコンピュータ可読非一時的媒体。
4. 実行されたとき、
   前記レベルＸ＋１キャッシュからデータユニットをフェッチすることと、
   前記割り当て指示を前記レベルＸ＋１キャッシュにおいて前記データユニットが存在することを表す状態に設定することと、
   を行うように動作可能であるデータおよび命令をさらに備えた請求項１のコンピュータ可読非一時的媒体。
5. 実行されたとき、
   前記レベルＸ＋１キャッシュの上のメモリ階層のレベルからデータユニットをフェッチすることと、
   前記割り当てられた指示を前記レベルＸ＋１キャッシュにおいて前記データユニットが存在しないことを表す状態に設定することと、
   を行うように動作可能であるデータおよび命令をさらに備えた請求項１のコンピュータ可読非一時的媒体。
6. 前記レベルＸ＋１キャッシュは、ビクティムキャッシュとして動作する請求項１のコンピュータ可読非一時的媒体。
7. 前記選択されたラインは、前記レベルＸ＋１キャッシュの最長時間未使用の置換手段によって決定された前記レベルＸ＋１キャッシュにおけるアドレスにて割り当てられる請求項１のコンピュータ可読非一時的媒体。
8. 実行されたとき、
   前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在し、修正されていないことを示す前記選択されたラインに関連する情報を識別することと、
   前記識別された情報に応じて、前記レベルＸ＋１キャッシュにおける前記選択されたラインの割り当てを防ぐことと、
   を行うように動作可能であるデータおよび命令をさらに備えた請求項１のコンピュータ可読非一時的媒体。
9. コンピュータ可読プログラムデータおよびコードで符号化されたコンピュータ可読非一時的媒体であって、前記プログラムデータおよびコードは、実行されたとき、
   レベルＸ＋１キャッシュにおいてフェッチアドレスをヒットさせるメモリアクセスに応じて、レベルＸキャッシュにおいて置換されるべき選択されたラインにアクセスすることと、
   前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在しないことを示す割り当てビット、および前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在することを示す割り当てビットに応じて、前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと
   を行うように動作可能であるコンピュータ可読非一時的媒体。
10. 実行されたとき、
    前記選択されたラインをダーティとして識別することと、
    前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと、
    を行うように動作可能であるデータおよび命令をさらに備えた請求項９のコンピュータ可読非一時的媒体。
11. 実行されたとき、
    前記選択されたラインに関連する前記割り当てビットが、前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在しないことを示すこと、および前記選択されたラインがダーティでないことをダーティビットが示すことを決定することと、
    前記レベルＸ＋１キャッシュにおいて前記選択されたラインを割り当てることと、
    を行うように動作可能であるデータおよび命令をさらに備えた請求項９のコンピュータ可読非一時的媒体。
12. アサートされていないダーティビットは、前記選択されたラインが修正されていないことを示す請求項９のコンピュータ可読非一時的媒体。
13. 実行されたとき、
    前記レベルＸ＋１キャッシュからデータユニットをフェッチすることと、
    前記割り当てビットを前記データユニットが前記レベルＸ＋１キャッシュにおいて存在することを表す状態に設定することと、
    を行うように動作可能であるデータおよび命令をさらに備えた請求項９のコンピュータ可読非一時的媒体。
14. 前記選択されたラインは、前記レベルＸ＋１キャッシュの最長時間未使用の置換手段によって決定された前記レベルＸ＋１キャッシュにおけるアドレスにて割り当てられる請求項９のコンピュータ可読非一時的媒体。
15. 実行されたとき、
    前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在することを示す前記選択されたラインの割り当てビットに応じて、前記レベルＸキャッシュから前記レベルＸ＋１キャッシュへの前記選択されたラインのキャストアウトを防ぐように動作可能であるデータおよび命令をさらに備えた請求項９のコンピュータ可読非一時的媒体。
16. 複数のキャッシュレベルを有するメモリシステムであって、
    レベルＸキャッシュにおいて複数の第１キャッシュラインのそれぞれを割り当てビットで記憶するための手段と、割り当てビットのそれぞれは前記割り当てビットに関連する前記複数の第１キャッシュラインのうちの１つがレベルＸ＋１キャッシュにおいて割り当てられたかどうかを示す、
    前記レベルＸ＋１キャッシュにおいてフェッチアドレスをヒットさせるアクセスのために、選択された第１キャッシュラインが前記レベルＸ＋１キャッシュにおいて存在しないことを示す割り当てビットに基づいて、前記選択された第１キャッシュラインを前記レベルＸ＋１キャッシュにキャストアウトするために、および前記選択された第１キャッシュラインが前記レベルＸ＋１キャッシュにおいてキャッシュラインと重複することを示す前記選択された第１キャッシュラインの前記割り当てビットに応じて、前記選択された第１キャッシュラインの前記レベルＸ＋１キャッシュへのキャストアウトを防ぐために、前記複数の第１キャッシュラインから置換するために前記選択された第１キャッシュラインが、前記レベルＸ＋１キャッシュにおいて前記フェッチアドレスをヒットさせるメモリアクセスに応じて、前記選択された第１キャッシュラインに関連する前記割り当てビットに基づいて前記レベルＸ＋１キャッシュにおいてキャッシュラインと重複するキャッシュラインであるかどうかを決定するための手段と、ここにおいて、キャッシュラインおよび関連する割り当てビットは、前記レベルＸ＋１キャッシュにおいて前記フェッチアドレスをヒットさせる前記アクセスのために、前記レベルＸキャッシュにおいて記憶され、前記関連する割り当てビットは、前記選択された第１キャッシュラインが前記レベルＸ＋１キャッシュにおいて存在することを表す、
    を備えたメモリシステム。
17. 前記レベルＸ＋１キャッシュは、
    複数の第２キャッシュラインと、
    前記レベルＸキャッシュにおけるミスに応じて、前記ミスに関連する前記キャッシュラインが前記レベルＸ＋１キャッシュにおいて割り当てられたかどうかに基づく割り当てシグナルを生成するための手段と、前記割り当てシグナルは、前記ミスに関連する前記キャッシュラインにおける前記割り当てビットとして、記憶のために前記レベルＸキャッシュに通信される、
    を備えた請求項１６のメモリシステム。
18. 前記割り当てビットを前記割り当てシグナルの状態に設定するための手段をさらに備えた請求項１７のメモリシステム。
19. 前記レベルＸキャッシュは、データキャッシュである請求項１６のメモリシステム。
20. 前記レベルＸ＋１キャッシュは、包含的キャッシュである請求項１７のメモリシステム。
21. 前記選択された第１キャッシュラインは、前記レベルＸ＋１キャッシュの最長時間未使用の置換手段によって決定された前記レベルＸ＋１キャッシュにおけるアドレスへキャストアウトされる請求項１６のメモリシステム。
22. コンピュータ可読プログラムデータおよびコードで符号化されたコンピュータ可読非一時的媒体であって、前記プログラムデータおよびコードは、実行されたとき、
    レベルＸ＋１キャッシュにおいてフェッチアドレスをヒットさせるメモリアクセスに応じて、レベルＸキャッシュにおいて置換されるべき選択されたラインにアクセスすることと、
    前記選択されたラインが前記レベルＸ＋１キャッシュにおいて存在しないことを示す前記選択されたラインに関連する情報を識別することと、
    前記レベルＸ＋１キャッシュにおいて前記フェッチアドレスをヒットさせる前記メモリアクセスのために、前記レベルＸ＋１キャッシュの最長時間未使用の置換手段によって決定された前記レベルＸ＋１キャッシュにおけるアドレスにて前記識別された情報に応じて、前記選択されたラインを割り当てることと、
    を行うように動作可能であるコンピュータ可読非一時的媒体。

Images