JP7249272B2 - キャッシュ、キャッシュを有するプロセッサ、及び、キャッシュ制御方法 - Google Patents

Description

（関連出願の相互参照）
本願は、２０１６年８月１２日に出願された米国特許出願第１５／２３５，２１４の利益を主張し、その内容は、完全に記載されているかのように、参照により本明細書に組み込まれるものとする。

変換索引バッファ（ＴＬＢ）は、メモリシステムのアドレスを指定する際に使用される仮想アドレスから物理アドレスへの変換を記憶するキャッシュである。ＴＬＢは、仮想アドレスを使用してメモリを参照する動作が多いので、コンピュータ動作を高速化することができる。ＴＬＢが無いと、このような動作は、変換を取得するためにメインシステムメモリにアクセスする必要があるので、長いレイテンシが発生する。したがって、ＴＬＢ動作を改善すると、コンピュータの動作速度を向上させることができる。

添付の図面と共に例として与えられる以下の説明から、より詳細な理解が得られるであろう。

１つ以上の開示された実施形態を実施することができる例示的なデバイスのブロック図である。 一実施例による、プロセッサ－メモリインタフェースシステムのブロック図である。 一実施例による、変換索引バッファのブロック図である。 一実施例による、キャッシュミスの場合に最長未使用時間（least-recently-used）データを変更する動作を示すブロック図である。 一実施例による、変換索引バッファの最長未使用時間データを更新する方法のフロー図である。

本開示は、変換索引バッファ（ＴＬＢ）の動作を向上させる技術に関する。ＴＬＢの特定のエントリが、大きいページサイズに関連付けられたデータを用いて更新される場合、ＴＬＢは、当該ＴＬＢエントリが最長未使用時間のエントリではないことを示すために、当該大きいページサイズの当該ＴＬＢエントリの置換ポリシーデータ（最長未使用時間（ＬＲＵ）データ等）を更新する。小さいページから大きいページサイズのＴＬＢエントリがエビクトされるのを抑制するために、ＴＬＢは、ＴＬＢエントリが最長未使用時間のエントリではないことを示すように、小さいページサイズのＴＬＢエントリの置換ポリシーデータも更新する。

変更されたＴＬＢエントリがこれらのページサイズの最長未使用時間のエントリではないことを示すために、小さいページサイズのＬＲＵデータを調整することは、小さいメモリページのＴＬＢエントリが、大きいページサイズのＴＬＢエントリをエビクトすることを抑制するのに役立つ。したがって、大きいページの変換は、小さいページの変換よりも「持続的」である。大きいページの変換は、システムメモリの大部分を使用可能にする。したがって、大きいページの変換の持続性を高めることで、ＴＬＧがシステムメモリの大部分をいつでも利用できるようになるので、ＴＬＢで発生するミスの量が少なくなり、ページテーブルから変換を取得するのにかかる全体のレイテンシが短縮される。これにより、ＴＬＢの全体的な速度及びパフォーマンスと、概して仮想アドレスを用いたメモリ動作の全体的な速度及びパフォーマンスと、が向上する。

図１は、本開示の態様が実施される例示的なデバイス１００のブロック図である。デバイス１００は、例えば、コンピュータ、ゲームデバイス、ハンドヘルドデバイス、セットトップボックス、テレビ、携帯電話又はタブレットコンピュータを含む。デバイス１００は、プロセッサ１０２と、メモリ１０４と、ストレージデバイス１０６と、１つ以上の入力デバイス１０８と、１つ以上の出力デバイス１１０と、を含む。また、デバイス１００は、入力ドライバ１１２及び出力ドライバ１１４をオプションで含むことができる。デバイス１００は、図１に示されていない追加のコンポーネントを含んでもよいことを理解されたい。

プロセッサ１０２は、中央処理装置（ＣＰＵ）、グラフィックス処理装置（ＧＰＵ）、同じダイ上に配置されたＣＰＵ及びＧＰＵ、又は、１つ以上のプロセッサコアを含み、各プロセッサコアはＣＰＵ又はＧＰＵである。メモリ１０４は、プロセッサ１０２と同じダイ上に配置されてもよいし、プロセッサ１０２とは別に配置されてもよい。メモリ１０４は、例えば、ランダムアクセスメモリ（ＲＡＭ）、ダイナミックＲＡＭ若しくはキャッシュ等の揮発性又は不揮発性メモリを含む。

ストレージデバイス１０６は、例えば、ハードディスクドライブ、ソリッドステートドライブ、光ディスク若しくはフラッシュドライブ等の固定又は取り外し可能なストレージデバイスを含む。入力デバイス１０８は、キーボード、キーパッド、タッチスクリーン、タッチパッド、検出器、マイクロフォン、加速度計、ジャイロスコープ、バイオメトリックスキャナ又はネットワーク接続（例えば、無線ＩＥＥＥ８０２信号を送信及び／若しくは受信するための無線ローカルエリアネットワークカード）を含む。出力デバイス１１０は、ディスプレイ、スピーカ、プリンタ、触覚フィードバック装置、１つ以上のライト、アンテナ又はネットワーク接続（例えば、無線ＩＥＥＥ８０２信号を送信及び／若しくは受信するための無線ローカルエリアネットワークカード）を含む。

入力ドライバ１１２は、プロセッサ１０２及び入力デバイス１０８と通信し、プロセッサ１０２が入力デバイス１０８から入力を受信することを可能にする。出力ドライバ１１４は、プロセッサ１０２及び出力デバイス１１０と通信し、プロセッサ１０２が出力デバイス１１０に出力を送信することを可能にする。入力ドライバ１１２及び出力ドライバ１１４は、オプションのコンポーネントであり、デバイス１００は、入力ドライバ１１２及び出力ドライバ１１４が存在しない場合であっても同様に動作することに留意されたい。

図２は、一実施例による、プロセッサ－メモリインタフェースシステム２００の態様を示すブロック図である。図示するように、プロセッサ－メモリインタフェースシステム２００は、図１のプロセッサ１０２と、図１のメモリ１０４と、を含む。

プロセッサ１０２は、データを処理するための命令を実行するコア２０２を含む。また、プロセッサ１０２は、変換索引バッファ（ＴＬＢ）２０６に接続されたメモリ管理ユニット（ＭＭＵ）２０４を含む。プロセッサ１０２によって実行される命令は、物理アドレス（通常、オペレーティングシステムの動作に関連する）又は仮想アドレス（通常、ユーザモードのアプリケーションに関連する）を介してメモリを参照することができる。アプリケーションに対して仮想アドレス空間を使用することによって、これらのアプリケーションを隔離することができ、これらのアプリケーションが、他のアプリケーション又はオペレーティングシステムに関連するメモリに書き込みを行って、他のアプリケーションの動作又はオペレーティングシステムに誤って干渉することが抑制される。

プロセッサ１０２は、仮想アドレスを介したメモリ１０４のアクセスを容易にするために、ＭＭＵ２０４を含む。ＭＭＵ２０４は、コア２０２から受信した仮想アドレスを物理アドレスに変換し、これらの物理アドレスを介してメモリ１０４にアクセスする。仮想アドレスがどのように物理アドレスに変換されるかを示すデータは、メモリ１０４内のページテーブル２０８に記憶される。アドレスは、バイト又はワードに変換されない代わりに、ページ番号に変換される。より具体的には、ページテーブル２０８は、単一ページを表すのに十分な数のアドレスの最上位ビットを含む仮想ページ番号を、物理ページ番号に変換する。アドレスの最下位ビットは変換されず、物理アドレス及び仮想アドレスの両方で同じである。

ＴＬＢ２０６は、ページテーブル２０８のキャッシュとして機能する。ＴＬＢ２０６が無いと、あらゆる仮想メモリアドレスルックアップがシステムメモリ１０４へのアクセスを必要とするため、メモリアクセスのレイテンシが増大する。ＴＬＢ２０６によって提供されるキャッシングは、このレイテンシを短縮するのに役立つ。しかしながら、ＴＬＢ２０６は、通常、ページテーブル２０８内の全ての変換の完全なコピーを含まない。コア２０２は、動作中、メモリアクセス命令を実行することの一環として、ＭＭＵ２０４に対して仮想メモリアドレスの変換を要求する。これに応じて、ＭＭＵ２０４は、変換のためにＴＬＢ２０６を検索する。キャッシュヒットの場合（ＴＬＢ２０６が変換を含むことを意味する）、ＭＭＵ２０４は、この変換から物理アドレスを取得し、取得した物理アドレスを用いて、メモリアクセス要求をメモリ１０４に送信する。キャッシュミスの場合（ＴＬＢ２０６が変換を含まないことを意味する）、ＭＭＵ２０４は、ページテーブルウォークを実行して、必要な変換についてページテーブル２０８を検索する。次に、ＭＭＵ２０４は、この変換をＴＬＢ２０６に配置し、ＴＬＢ２０６に十分なスペースが存在しない場合には、別のエントリをエビクトする。ＭＭＵ２０４は、最近得られた変換に基づいてメモリアクセスを実行する。

アドレス変換における難しさを示す１つの態様は、異なるページサイズの可能性である。より具体的には、異なるサイズのメモリページをメモリ１０４に記憶させるという選択肢は、異なるサイズのページの変換を、どのようにＴＬＢ２０６にキャッシュするかという課題を提起する。

図３は、一実施例による、変換索引バッファ（ＴＬＢ）３００のブロック図である。図示するように、ＴＬＢ３００は、異なるページサイズのページの変換を記憶するページテーブル２０８のキャッシュとして高性能用途に適合されたスキュード（skewed）アソシアティブキャッシュとして実装される。図３に示す例示的なＴＬＢ３００は、４つのウェイ３０４の７つのセットと、７行の最長未使用時間（ＬＲＵ）データと、ＬＲＵデータの行毎に４つのＬＲＵエントリと、を含む。例示的なアドレス３０２が示されている。例示的なＴＬＢ３００は、図２に示すＴＬＢ２０６の一例である。例示的な仮想アドレス３０２は、インデックス３１４と、タグ３１０と、選択ビット３１２と、を含み、特定のページサイズ３０８に関連付けられている。ページサイズ３０８は、仮想アドレス３０２にデータを記憶するメモリページのサイズを示す。

スキュードアソシアティブキャッシュは、セットアソシアティブキャッシュの変形であり、キャッシュミスの可能性を低減することができる。キャッシュは、ルックアップに応じてペイロードデータを提供する。様々なタイプのキャッシュ（セットアソシアティブキャッシュを含む）では、アドレスのキャッシュインデックス部分を使用して、当該インデックスを有するアドレスのデータを記憶することができるキャッシュ内のエントリを識別する。ダイレクトマッピングキャッシュでは、キャッシュインデックスは、キャッシュ内の単一のエントリを一意に識別する。したがって、ダイレクトマッピングキャッシュでは、特定のアドレスのエントリを、単一のキャッシュエントリにしか記憶することができない。フルアソシアティブキャッシュでは、全てのアドレスを任意のキャッシュエントリに記憶することができる。セットアソシアティブキャッシュでは、特定のキャッシュインデックス値をキャッシュ内のエントリ数ｎにマッピングすることができる。ここで、ｎは、１より大きく、キャッシュサイズより小さい（ｎ＝１のキャッシュは、ダイレクトマッピングキャッシュであり、ｎ＝キャッシュサイズのキャッシュは、フルアソシアティブキャッシュである）。セットアソシアティブキャッシュでは、キャッシュインデックスは、特定のセットにマッピングされ、各セットは、複数のキャッシュエントリを含む。また、キャッシュ全体は、ｎ個の「バンク」（「ウェイ」とも呼ばれる）に分割される。セットアソシアティブキャッシュ内の特定のキャッシュエントリは、セット番号とバンク（ウェイ）番号との特定の組み合わせによって識別される。

スキュードアソシアティブキャッシュは、セットアソシアティブキャッシュの変形であり、セットの選択はウェイによって異なる。ＴＬＢ３００は、スキュードアソシアティブキャッシュとして実装される。したがって、ＴＬＢ３００では、任意の特定のアドレスを異なるウェイの異なるセットにマッピングすることができる。

さらに、スキュードアソシアティブなＴＬＢ３００は、異なるサイズのページの変換に対応する。より具体的には、あらゆるウェイ３０４内のあらゆるエントリが、あらゆる可能なページサイズの変換を記憶することができる。各仮想アドレスは、各ウェイ３０４において、可能性のある一意のマッピング位置を有する。しかしながら、アドレスとページサイズとのあらゆる組み合わせを、あらゆるウェイ３０４に記憶することはできない。特定のアドレスを記憶することができるウェイ３０４は、ページサイズ関数により特定される。ページサイズ関数は、次のように定義される。ＴＬＢ３００の所定のウェイＩ及び所定の仮想アドレスＡについて、仮想ページのサイズが、ページサイズ関数であるＳ（Ａ、Ｉ）である場合にのみ、仮想アドレスＡを含むページＰ（Ａ）をウェイＩにマッピングすることができる。換言すると、ページサイズ関数は、仮想アドレスとページサイズとの組み合わせ毎に、当該仮想アドレスが何れのウェイにマッピング可能であるかを示している。ページサイズ関数は、仮想アドレス３０２の選択ビット３１２に基づいて結果を生成する。技術的に実現可能なページサイズ関数の任意の実装を使用することができる。

ページサイズ関数の機能は、選択関数Ｓｅｌ（Ａ）によって表すこともできる。選択関数は、所定のアドレスに対して単一の数値を生成する。選択関数によって生成された数値は、何れのページサイズが何れのウェイにマッピングされているかを示す。図３のＴＬＢ３００の例では、ＴＬＢ３００は、４つのウェイを含む。２つのウェイ（ウェイ０及びウェイ１）は、第１グループ３１６（１）にまとめられ、他の２つのウェイ（ウェイ２及びウェイ３）は、第２グループ３１６（２）にまとめられている。さらに、ＴＬＢ３００は、２つの異なるサイズのページの変換を記憶するように構成されている。選択関数の値が０である場合、第１ウェイグループ３１６（１）が第１サイズのページを記憶し、第２ウェイグループ３１６（２）が第２サイズのページを記憶することを示している。選択関数の値が１である場合、第１ウェイグループ３１６（１）が第２サイズのページを記憶し、第２ウェイグループ３１６（２）が第１サイズのページを記憶することを示している。一手法では、ページサイズ関数（したがって、選択関数）は、図３に示すように、仮想アドレス３０２のマッピングビットに基づいている。１つの例示的な選択関数では、異なる選択ビット３１２が異なる選択値に割り当てられている。一例では、アドレスは、３つの選択ビット３１２を有する。値０００、００１、０１０、０１１が選択値０に割り当てられている。値１００、１０１、１１０、１１１が選択値１に割り当てられている。他の技術的に実現可能な選択関数（又は、ページサイズ関数）を使用してもよい。

特定のアドレス及びページサイズに適したセットは、インデックス化関数（indexing function）に基づいて特定される。より具体的には、インデックス化関数は、アドレスと、ページサイズと、ページサイズ関数の出力と、を入力として受信し、アドレスとページサイズとの組み合わせを記憶することができるウェイ毎に、特定のセットを出力する。図３の例では、インデックス化関数は、仮想アドレス３０２のインデックス部分３１４と、ページサイズ３０８と、選択関数の出力（仮想アドレス３０２の選択ビット３１２に基づいている）と、を入力として受信し、アドレスを記憶することができるウェイの各々に対してセット番号を出力する。一例では、インデックス化関数は、ウェイのグループ３１６内のセット毎に同じセットを出力する（上述したように、ウェイのグループ３１６は、ページ選択の目的で共にグループ化されたウェイ３０４を含む）。

上述したように、ＭＭＵ２０４は、ＴＬＢ３００を用いて、仮想アドレス３０２及びページサイズに基づいてＴＬＢ３００をインデックス化することによって、仮想アドレス３０２を物理アドレスに変換する。ＴＬＢ３００のスキュードアソシアティブ性のために、ＴＬＢ３００は、特定の仮想アドレス及びページサイズの組み合わせに対して、仮想アドレス／ページサイズの組み合わせを記憶することができる複数のウェイを含む。したがって、ＭＭＵ２０４は、仮想アドレス３０２の変換を試みるために、インデックス化関数に基づいてセットを識別し、ページサイズ関数に基づいて複数の可能なウェイを識別する。ＭＭＵ２０４は、アドレス３０２のタグ部分３１０を、識別したセット及びウェイ内の１つのエントリのタグ３１０と一致させることを試みる。タグ３１０が１つのエントリにおいて一致する場合にはヒットが発生し、タグ３１０が一致しない場合にはミスが発生する。

ミスの場合、ＭＭＵ２０４は、仮想アドレス３０２に関連する変換をページテーブル２０８に要求し、受信した変換をＴＬＢ３００の１つのＴＬＢエントリ３０１に配置する。ＭＭＵ２０４は、アドレス３０２、ページサイズ３０８及び最長未使用時間（ＬＲＵ）データ３０６を調べる置換ポリシーに基づいて、何れのＴＬＢエントリ３０１に変換を配置するかを決定する。

特定のアドレス及びページサイズの組み合わせに対して、当該アドレスのエントリを複数のウェイ３０４に記憶することができる。ＭＭＵ２０４は、フェッチされた変換を記憶するウェイ３０４を決定するために、ＬＲＵデータ３０６を調べる。ＬＲＵデータ３０６は、選択値／ページサイズの組み合わせ毎にＬＲＵエントリ３０８を含む。図３の例示的なＴＬＢ３００では、選択値０／サイズ１の組み合わせに対して１つのＬＲＵエントリ３０８が存在し、選択値０／サイズ２の組み合わせに対して１つのＬＲＵエントリ３０８が存在し、選択値１／サイズ１の組み合わせに対して１つのＬＲＵエントリ３０８が存在し、選択値１／サイズ２の組み合わせに対して１つのＬＲＵエントリ３０８が存在する。より多くのページサイズを有するＴＬＢでは、追加のＬＲＵエントリを含む。

各ＬＲＵエントリ３０８は、選択値／ページサイズの組み合わせに対して、特定の選択値／ページサイズの組み合わせの変換を記憶することができるウェイのうち何れのウェイ３０４が最長未使用時間のウェイであるとみなされるかを示す。例えば、選択値０及びサイズ１のページサイズ（及びセット１）に関して、ＬＲＵエントリ３０８（１）は、ウェイ０又はウェイ１の何れが、最長未使用時間のエントリ３０１とみなされるエントリ３０１を記憶しているかを示す。同様に、選択値１及びサイズ２のページサイズに関して、ＬＲＵエントリ３０８（４）は、ウェイ０又はウェイ１の何れが、最長未使用時間のエントリ３０１とみなされるエントリ３０１を記憶しているかを示す。

上記は、任意の特定のウェイグループ３１６に関して、インデックス化関数が、任意の特定のアドレスを、当該ウェイグループ３１６と同じセットにマッピングすることを想定していることに留意されたい。「ウェイグループ」３１６という用語は、任意の特定の仮想アドレスが同じセットにマッピングされるウェイ３０４の集合を指す。図３では、２つのウェイグループ３１６が存在する。第１ウェイグループ３１６は、ウェイ０及びウェイ１を含み、第２ウェイグループ３１６は、ウェイ２及びウェイ３を含む。

「ウェイグループ」３１６の概念は、ＬＲＵデータが選択値／ページサイズ毎に記憶されることを可能にする。より具体的には、ＭＭＵ２０４が特定のアドレス／ページサイズの組み合わせを何れのウェイグループ３１６にマッピングすることができるかを決定すると、この概念により、異なるウェイ間で有意義な比較を行うことができる。一例では、特定のアドレス／ページサイズの組み合わせがウェイ０及びウェイ１から構成されたウェイグループ３１６に属するとＭＭＵ２０４が決定すると、ウェイ３０４をグループ化することは、対応するＬＲＵエントリ３０８が、ＭＭＵ２０４に対して、ウェイグループ３１６内のウェイのうち１つのウェイを最長未使用時間のウェイとして識別させるのを可能にすることを意味する。

置換アルゴリズムの一例では、各ウェイグループ３１６は２つのウェイ３０４を含む。ＬＲＵデータ３０６は、セット毎に１つのＬＲＵエントリ３０８と、選択関数値と、ページサイズと、の組み合わせを含む。各ＬＲＵエントリ３０８は１ビットである。このビットは、特定のページサイズについて、特定のウェイグループ３１６内の２つのウェイのうち何れのウェイが最長未使用時間のＴＬＢエントリを記憶し、これにより、ＭＭＵ２０４が新たにフェッチした変換をＴＬＢに書き込む場合に何れが置き換えられるのかを示す。一例では、第１セットと、第１ウェイグループ３１６（ウェイ０及びウェイ１）と、第１ページサイズと、に関連付けられたエントリは、ウェイ０が最長未使用時間のＴＬＢエントリを記憶することを示す。同じセット及びウェイグループ３１６（ウェイ０及びウェイ１）と、第２ページサイズと、に関連付けられたエントリは、ウェイ１が最長未使用時間のＴＬＢエントリを記憶することを示す。これらの特定の値は、変換されるアドレスが第１ページサイズ又は第２ページサイズのメモリページ内に存在するか否かに応じて、ウェイグループ３１６内で異なる置換が行われることを意味する。

本明細書では、特定のＬＲＵ置換ポリシーが説明されているが、他の置換ポリシーも可能である。例えば、擬似ＬＲＵ（ＰＬＲＵ）、ツリー（tree）ｐＬＲＵ等を用いる置換アルゴリズムを使用することができる。さらに、置換アルゴリズムは、ウェイグループ３１６が３つ以上のウェイ３０４を含むシナリオで使用されてもよい。このようなシナリオでは、各ＬＲＵデータエントリは、複数のビットを記憶することができる。

大きいページ及び小さいページの両方を任意の特定のウェイ３０４に記憶することができるということは、小さいページが大きいページを置き換えることができることを意味する。さらに、ＬＲＵデータがページサイズ毎に記憶されるということは、１つのページサイズの置換データが、特定のＴＬＢエントリが置き換えられることを示し、別のページサイズの置換データが、異なるＴＬＢエントリが置き換えられることを示すことを意味する。この可能性は、小さいページの変換による大きいページの変換のエビクトの発生が有利ではない状況において、かかるエビクトが可能であることを意味する。

一例では、ＭＭＵ２０４は、小さいページサイズのＴＬＢエントリをセット１のウェイ０に書き込み、小さいページのセット１ではウェイ０及びウェイ１のうちウェイ１が最長未使用時間のウェイであることを示すように、対応するＬＲＵエントリを更新する。次に、ＭＭＵ２０４は、大きいページサイズのＴＬＢエントリをセット１のウェイ１に書き込み、大きいページのセット１では、ウェイ０及びウェイ１のうちウェイ０が最長未使用時間のウェイであることを示すように、対応するＬＲＵエントリを更新する。次いで、ＭＭＵ２０４は、小さいページサイズのＴＬＢエントリをセット１に書き込む。ＭＭＵ２０４は、ＬＲＵデータに基づいて、セット１では、小さいページに関して、ウェイ０及びウェイ１のうちウェイ１が最長未使用時間のウェイであると判別する。したがって、ＭＭＵ２０４は、小さいページサイズのＴＬＢエントリをセット１のウェイ１に書き込む。しかしながら、この動作により、セット１のウェイ１に記憶された大きいページの新たに追加されたＴＬＢエントリがエビクトされることになる。

事実上、小さいページの新たな変換は、大きいページの新たな変換をエビクトした。大きいページの変換は、小さいページの変換よりも優先されるべきであるため、この動作は望ましくない。より具体的には、大きいページの変換は、小さいページの変換よりも多くのシステムメモリをカバーするため、小さいページの変換を追加するために大きいページの変換をエビクトすることは、ＴＬＢが処理可能なシステムメモリが減少して、ＴＬＢにおいてミスが発生する可能性が増大するという影響がある。小さいページの変換をＴＬＢに書き込む場合、この変換を何処かに記憶する必要がある。しかしながら、この変換を、大きいページサイズの最長未使用時間エントリではないＴＬＢエントリに記憶することによって、大きいページサイズの最長未使用時間エントリよりも（少なくとも最長未使用時間の置換セマンティクスの観点から）関連性が高いとみなされる大きいページサイズの変換がエビクトされる。これらの理由により、追加の置換アルゴリズム技術が以下に提供される。

図４は、一実施例による、キャッシュミスの場合にＬＲＵデータを変更する動作を示すブロック図である。図示するように、図４は、第１動作４００と、第２動作４１０と、第３動作４２０と、第４動作４３０と、を示す。

第１動作、第２動作、第３動作及び第４動作は、大きいページの変換が、小さいページの変換よりもＬＲＵ内でより持続的になることを可能にする方法でＬＲＵデータを変更する技術を示す。全般的に、これらの動作は、大きいサイズのページのＬＲＵデータが更新される場合に、小さいサイズのページのＬＲＵデータを更新することを含む。より具体的には、ＭＭＵ２０４は、大きいページの変換がＴＬＢに配置されるべきであると決定すると、当該大きいページのＬＲＵデータエントリ３０８と、対応する小さいページのＬＲＵデータエントリ３０８との両方を更新する。より具体的には、大きいサイズのページ内のアドレスに対するキャッシュミスを検出すると、ＭＭＵ２０４は、当該大きいページの変換を配置すべき特定のＴＬＢエントリを識別する。このＴＬＢエントリは、特定のセット及びウェイによって定義されることに留意されたい。ＭＭＵ２０４は、変換をそのＴＬＢエントリに配置し、最近更新したＴＬＢエントリが最長未使用時間データを含まないことを示すように、対応するＬＲＵデータを更新する。この更新されたＬＲＵデータは、選択値、セット及びページサイズによって定義される。さらに、ＭＭＵ２０４は、（セット及び選択値によって定義される）同じＴＬＢエントリが最長未使用時間のエントリではないことを示すように、当該同じＴＬＢエントリ及び小さいページサイズのＬＲＵデータを更新する。小さいページサイズに対するこの追加の更新は、小さいページサイズの同じウェイグループ３１６へのその後の更新が、最近追加された大きいページサイズの変換をエビクトするのを抑制するという効果を有する。

実際には、この追加の更新動作によって、大きいページサイズの変換が、この追加の更新動作が行われなかった場合よりも持続性が高くなる。大きいページの変換は、システムメモリの大部分を利用する。したがって、大きいページの変換の持続性を高めることは、システムメモリの大部分でＴＬＢ３００をいつでも利用することを可能にし、これにより、ＴＬＢ３００で発生するミスの数を減らし、ページテーブル２０８から変換を取得するのにかかる全体のレイテンシを短縮し、ＴＬＢ３００の全体的な速度及びパフォーマンスと、概して仮想アドレスを用いたメモリ動作の全体的な速度及びパフォーマンスとを向上させる。

図４に示す動作は、上記の技術の一例である。図４の各動作は、ＴＬＢのいくつかのセットと、２つのウェイグループ３１６にグループ化された４つのウェイ（０、１及び２、３）と、第１セットのＬＲＵデータと、を示す。各セットが対応するＬＲＵデータを有することを理解されたいが、簡単にするために、ＬＲＵデータは、第１セット以外の何れのセットにも示されていない。

第１動作４００において、ＭＭＵ２０４は、ページサイズ４Ｋのページ内のアドレスの変換を既に処理し始めている（この例では、４Ｋが小さいページサイズであり、２ＭＢが大きいページサイズである）。また、ＭＭＵ２０４は、ＴＬＢ内でミスが発生したと判別し、ページテーブル２０８から変換を受信し、アドレスに基づいて選択値を０として計算し、選択値０及びページサイズ４Ｋに一致するウェイを識別し、アドレス及びページサイズ関数に基づいてセット（図の最上部のセット）を識別している。さらに、ＭＭＵ２０４は、新たに受信した変換を記憶するためのウェイグループ３１６（０及び１を含む）を識別し、ＬＲＵデータ３０６に基づいて、変換を記憶するための１つのウェイを識別している。識別されたウェイは、ウェイ０である。したがって、ＭＭＵ２０４は、新たに受信した変換を、セット１及びウェイ０で見つけられたＴＬＢエントリ（すなわち、数字「１」で示されたＴＬＢエントリ）に記憶すべきであると決定する。この決定に応じて、ＭＭＵ２０４は、ＬＲＵデータ３０６を更新する。具体的には、ＭＭＵ２０４は、最長未使用時間のＴＬＢエントリがＴＬＢエントリ２であることを示すように、選択値０、ページサイズ４Ｋ及びセット１のＬＲＵデータエントリ３０８を更新する。ＭＭＵ２０４は、４Ｋが最小のページサイズであるため、他のＬＲＵデータを更新しない。

第２動作、すなわち動作４１０は、選択値が１であることを除いて、動作４００と同様である。ページサイズは、依然として４Ｋである。選択値が１であるため、フェッチされた変換は、ウェイ０及びウェイ１の何れかのＴＬＢエントリではなく、ウェイ２及びウェイ３の何れかのＴＬＢエントリ（具体的には、ウェイ２のＴＬＢエントリ３）を置き換える。動作４００のように、ＭＭＵ２０４は、ページサイズが４Ｋであるため、他のＬＲＵデータを更新しない。

第３動作、すなわち動作４２０は、変換のアドレスが、大きいサイズ（２ＭＢ）のページ内のアドレスである場合の動作である。ＴＬＢでミスが発生すると、ＭＭＵ２０４は、ページテーブル２０８から変換を取得する。ＭＭＵ２０４は、このアドレスを処理して、選択値が０であると判別する。ＭＭＵ２０４は、ＬＲＵデータ３０６を調べて、最近受信した変換を記憶するＴＬＢエントリが、３と示されたＴＬＢエントリであると判別する。ＭＭＵ２０４は、ページテーブル２０８から取得した変換を記憶するＴＬＢエントリを判別した後に、選択値とページサイズとの組み合わせのＬＲＵデータ３０６を更新する。より具体的には、ＭＭＵ２０４は、４と示されたＴＬＢエントリが最長未使用時間のエントリであること（エントリ３が書き込まれたばかりであるため）を示すように、選択値０及びページサイズ２Ｍに対応するＬＲＵデータエントリ３０８を更新する。さらに、フェッチされたアドレスは、大きいページサイズを有するメモリページ内のアドレスに対するものであるため、ＭＭＵ２０４は、同じウェイグループ３１６に対応するが、小さいページサイズのＬＲＵデータエントリ３０８を更新する。このＬＲＵデータエントリは、選択値１及びページサイズ４Ｋのデータエントリである。ＭＭＵ２０４は、ＴＬＢエントリ４が最長未使用時間のエントリであることも示すように、このＬＲＵデータエントリを更新する。小さいサイズのページのＬＲＵデータエントリを更新することは、ウェイの同じセットのＴＬＢミスによって、書き込まれたばかりの大きいページサイズのＴＬＢエントリがエビクトされるのを抑制することに役立つ。

第４動作４３０は、第４動作のアドレスが選択値０ではなく選択値１と評価したことを除いて、第３動作４２０と同様である。したがって、ＭＭＵ２０４は、選択値０／２ＭＢ及び選択値１／４Ｋを更新するのではなく、選択値０／４Ｋ及び選択値１／２ＭＢを更新する。

インデックス化関数は、単純化のためだけに、各動作において１を設定するように評価するものとして示されている。インデックス化関数は、何れのセットに対しても評価することができる。図３及び図４では、２つのウェイグループと、グループ毎に２つのウェイと、２つのページサイズと、のみが示されているが、本明細書で説明する技術は、異なる数のウェイグループと、異なる数のグループ毎のウェイと、異なる数のページサイズと、を有するＴＬＢに適用することができる。より多くのページサイズの場合、各サイズは、関連するウェイグループを有する。対応するＴＬＢエントリの変換をフェッチすることによってＭＭＵ２０４が特定のページサイズのＬＲＵデータを更新する場合には、ＭＭＵ２０４は、新たに取得された変換を受信したＴＬＢエントリが最長未使用時間のエントリではないことを示すように、小さいページサイズ毎のＬＲＵデータも更新する。

図５は、一実施例による、変換索引バッファの最長未使用時間データを更新する方法５００のフロー図である。図１～図４に関連して示され説明されたシステムについて説明が行われたが、技術的に実行可能な順序で方法を実行するように構成された任意のシステムも本開示の範囲内にあることを理解されたい。

図示するように、方法５００は、ステップ５０２から開始し、ステップ５０２において、ＭＭＵ２０４は、仮想アドレスから物理アドレスへの変換がＴＬＢ３００内に存在しないことに起因するＴＬＢ３００内のミスを検出する。ＭＭＵ２０４は、ページテーブル２０８から要求された変換をフェッチする。ステップ５０４において、ＭＭＵ２０４は、変換された仮想アドレスのページサイズを判別する。特定のアドレスのページサイズ情報は、ページテーブル２０８、又は、構成レジスタ（ｘ８６アーキテクチャに存在するメモリタイプ範囲レジスタ等が挙げられるが、これに限定されない）のセットから取得することができる。また、ＭＭＵ２０４は、ページサイズ関数及びアドレスに基づいて選択値を計算する。選択値は、何れのウェイグループ３１６が何れのページサイズに割り当てられているかを示す。

ステップ５０６において、ＭＭＵ２０４は、ページサイズ、選択値、アドレス及びＬＲＵデータに基づいて、アドレス変換を記憶するためのＴＬＢ内のセット及びウェイを識別する。より具体的には、ＭＭＵ２０４は、ページサイズ関数及びページサイズに基づいて、変換を記憶することができる可能性のあるウェイを識別し、識別したウェイについてインデックス化関数に基づいてインデックス化の結果を計算して、変換を配置可能なセットを決定し、ＬＲＵデータに基づいて、識別したセット内で変換を記憶する特定のウェイを識別する。例えば、ＬＲＵデータが、識別したウェイ及び識別したセットの特定のＴＬＢエントリが最長未使用時間のウェイであることを示す場合、ＭＭＵ２０４は、当該ＴＬＢエントリを、新たに取得した変換を配置するエントリとして識別する。

ステップ５０８において、ＭＭＵ２０４は、変換を、識別したセット及びウェイに記憶し、識別したセット、選択値及びページサイズのＬＲＵデータを更新する。上述したように、ＬＲＵデータは、セット毎に、また、選択値及びページサイズの組み合わせ毎に存在する。ＬＲＵデータは、識別したセット内及び適切なウェイグループ３１６（選択値及びページサイズに基づいて識別されたウェイグループ３１６）内で何れのＴＬＢエントリが最長未使用時間データを記憶しているかを示す。ＭＭＵ２０４は、更新されたＴＬＢエントリ以外の、適切なウェイグループ３１６内及び識別したセット内のＴＬＢエントリが最長未使用時間データを記憶していることを示すように、セット／選択値／ページサイズのＬＲＵデータを更新する。一例では、各ウェイグループ３１６は、２つのウェイを含む。ステップ５０８において、１つのウェイのエントリが更新されると、ＭＭＵ２０４は、そのウェイグループ３１６内の別のウェイが最長未使用時間のウェイであることを示すように、ＬＲＵデータを更新する。別の例では、各ウェイグループ３１６は、３つ以上のウェイを含む。このような場合には、ＭＭＵ２０４は、更新されたＴＬＢエントリと同じセット及びウェイグループ３１６内の他のＴＬＢエントリが、更新されたＴＬＢエントリよりも最長未使用時間のデータを含むことを示すように、ＬＲＵデータを更新する。

ステップ５１０において、ＭＭＵ２０４は、特定のセット／選択値／ページサイズの組み合わせのＬＲＵデータの更新に応じて、同じセットではあるが、異なるページサイズ／選択値の組み合わせのＬＲＵデータを更新する。より具体的には、ＭＭＵ２０４は、更新されたＬＲＵデータと同じセットのＬＲＵデータであって、ステップ５０８でＬＲＵデータが更新されたウェイグループ３１６と一致する各ページサイズ／選択値の組み合わせに関するＬＲＵデータを更新する。ＭＭＵ２０４は、このようなＬＲＵデータを更新して、ステップ５０８でＴＬＢエントリが変更されたページサイズよりも小さいページサイズ毎に、ステップ５０８で更新されたＴＬＢエントリが最長未使用時間のＴＬＢエントリではないことを示す。このような小さいページサイズのＬＲＵデータを更新することは、大きいページサイズのＴＬＢエントリが、小さいページのＴＬＢエントリよりも持続的になることを容易にする。

本明細書で説明する技術は、ＴＬＢの動作を向上させる。より具体的には、変更されたＴＬＢエントリが小さいページサイズの最長未使用時間のエントリではないことを示すために、小さいページサイズのＬＲＵデータを調整することは、小さいメモリページのＴＬＢエントリが、大きいメモリページのＴＬＢエントリをエビクトすることを抑制するのに役立つ。したがって、大きいページの変換は、小さいページの変換よりも「持続的」である。大きいページの変換は、システムメモリの大部分を利用する。したがって、大きいページの変換の持続性を高めることは、システムメモリの大部分でＴＬＢ３００をいつでも利用することができるのを容易にし、これにより、ＴＬＢ３００内で発生するミスの量を減らし、ページテーブル２０８から変換を取得するのにかかる全体のレイテンシを短縮し、ＴＬＢ３００の全体的な速度及びパフォーマンスと、概して仮想アドレスを用いるメモリ動作の全体的な速度及びパフォーマンスと、を向上させる。

スキュードアソシアティブキャッシュの文脈で説明したが、上記で提供された技術は、セットアソシアティブキャッシュにも適用することができる。このようなセットアソシアティブキャッシュ内のウェイは、上述したようにウェイグループ３１６にグループ化され、各ウェイグループ３１６は、アドレスに依存する選択関数（又は、ページサイズ関数）に基づいて選択される。このようなセットアソシアティブキャッシュは、同じアドレスが異なるウェイグループ３１６内の異なるセットにマッピングされるというスキュードアソシアティブ特性を示さない。その代わりに、アドレスは、各ウェイグループ３１６内の同じセットにマッピングされる。セットアソシアティブキャッシュのＬＲＵデータは、上記と同様の方法で記憶される。

さらに、コンピュータシステムの標準ＭＭＵ内の変換索引バッファの文脈で説明したが、上記で提供された技術は、ＣＰＵ等のプロセッサではなく、入出力デバイスのアドレス変換サービスを提供する入出力ＭＭＵ等の他のＭＭＵにおいて使用することができる。さらに、キャッシュが異なるレベルの汎用性のアドレス変換をキャッシュする限り、上述した技術は、ＴＬＢ以外のキャッシュにも適用することができる。例えば、上記の技術は、インターネットプロトコルアドレスの異なる部分（例えば、ＸＸＸ．ＸＸＸ．＿＿＿対ＸＸＸ．ＸＸＸ．ＸＸＸ．＿＿＿は、ＩＰアドレスの１つのクラス対ＩＰアドレスの別のクラス（例えばクラスＡ対クラスＢ）を表す）に関するインターネットプロトコルアドレス変換を記憶するキャッシュにおいて使用することができる。「汎用性のレベル」という用語は、特定のキャッシュエントリによってカバーされるアドレス空間の部分を指す。ＴＬＢの場合、「より高いレベルの汎用性」は、大きいページサイズの変換に対応し、「より小さいレベルの汎用性」（又は、「より具体的なレベルの汎用性」）は、小さいページサイズの変換に対応する。ＩＰアドレス変換では、小さいＩＰアドレス部分の変換（つまり、より多くの合計ＩＰアドレスをカバーする）は、大きいＩＰアドレス部分の変換よりも高いレベルの汎用性を有する。任意の実施態様では、上記の教示は、より高いレベルの汎用性を有するキャッシュエントリの置換ポリシーデータを更新する場合に、より小さいレベルの汎用性を有する同じキャッシュエントリの置換ポリシーデータに対して同様の更新が行われることを指示する。ＴＬＢではない任意のキャッシュの実施態様では、ＭＭＵの動作は、このようなキャッシュを管理するキャッシュコントローラによって実行されるとみなすことができる。

いくつかの例示的なＬＲＵメカニズムが上記のように提供されたが、ＬＲＵメカニズムは、技術的に実行可能なＬＲＵ技術であってもよい（又は、非ＬＲＵ置換技術であってもよい）。さらに、技術的に実現可能なページサイズ関数、選択関数及びインデックス化関数を使用することができる。

変換索引バッファを含むキャッシュの置換ポリシーデータを更新する方法が本明細書に開示されている。キャッシュの第１キャッシュエントリに対する更新が検出される。第１キャッシュエントリに対応する第１置換ポリシーデータエントリであって、第１ページサイズに関連する第１置換ポリシーデータエントリに対する第１変更が検出される。第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリであって、第１キャッシュエントリに関連する第２置換ポリシーデータエントリが識別される。第１変更は、第２置換ポリシーデータエントリに対して行われる。

いくつかの例では、第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている。いくつかの例では、キャッシュは、複数のウェイグループにグループ化された複数のウェイを含み、第１置換ポリシーデータエントリは、ウェイグループのうち第１キャッシュエントリを含む第１ウェイグループの置換ポリシーデータを記憶し、第２置換ポリシーデータエントリは、第１ウェイグループの置換ポリシーデータを記憶する。

いくつかの例では、第１キャッシュエントリは、第１メモリページの変換を記憶し、第１メモリページは、第１ウェイグループ内のキャッシュの第１セット、及び、複数のウェイグループのうち第２ウェイグループ内のキャッシュの第２セットにマッピングされており、第２セットは、第１セットとは異なるセットである。いくつかの例では、方法は、キャッシュ内のミスを検出することと、ミスに応じて、キャッシュ内に配置されたアイテムをフェッチすることと、アイテムに関連するアドレス及びアイテムに関連するページサイズに基づいて、アイテムのためのセット及びウェイグループを識別することと、第１置換ポリシーデータエントリに基づいて、ウェイグループ内のウェイを識別することと、を含む。キャッシュの第１キャッシュエントリに対する更新は、識別されたウェイ、セット及びウェイグループに対して実行される。いくつかの例では、ウェイグループ内のウェイを識別することは、アイテムに関連するページサイズの最長未使用時間のキャッシュエントリをウェイグループ内のウェイが記憶していることを第１置換ポリシーデータエントリが示すことを判別することを含む。

いくつかの例では、第１置換ポリシーデータエントリは、ウェイグループ内の何れのウェイが最長未使用時間データを含むかを示す１ビットを含む。いくつかの例では、方法は、キャッシュの第２キャッシュエントリに対する第２更新を検出することと、第２キャッシュエントリに対応する第３置換ポリシーデータエントリであって、第２ページサイズに関連する第３置換ポリシーデータエントリに対する第２変更を検出することと、第２ページサイズがキャッシュ内のデータの最小ページサイズであることを判別することと、を含み、第３置換ポリシーデータエントリがキャッシュ内のデータの最小ページサイズに関連していることに応じて、他の置換データが変更されない。

本明細書では、キャッシュも提供される。キャッシュは、キャッシュデータを記憶するキャッシュメモリであって、変換索引バッファを含むキャッシュメモリと、置換ポリシーデータを記憶する置換ポリシーメモリと、キャッシュコントローラと、を含む。キャッシュコントローラは、キャッシュメモリの第１キャッシュエントリに対する更新を検出し、第１キャッシュエントリに対応する第１置換ポリシーデータエントリであって、第１ページサイズに関連する第１置換ポリシーデータエントリに対する第１変更を検出し、第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリであって、第１キャッシュエントリに関連する第２置換ポリシーデータエントリを識別し、第２置換ポリシーデータエントリに対して第１変更を行うように構成されている。

いくつかの例では、第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている。いくつかの例では、キャッシュは、複数のウェイグループにグループ化された複数のウェイを含み、第１置換ポリシーデータエントリは、ウェイグループのうち第１キャッシュエントリを含む第１ウェイグループの置換ポリシーデータを記憶し、第２置換ポリシーデータエントリは、第１ウェイグループの置換ポリシーデータを記憶する。

いくつかの例では、第１キャッシュエントリは、第１メモリページの変換を記憶し、第１メモリページは、第１ウェイグループ内のキャッシュの第１セット、及び、複数のウェイグループのうち第２ウェイグループ内のキャッシュの第２セットにマッピングされており、第２セットは、第１セットとは異なるセットである。いくつかの例では、キャッシュコントローラは、キャッシュ内のミスを検出し、ミスに応じて、キャッシュ内に配置されたアイテムをフェッチし、アイテムに関連するアドレス及びアイテムに関連するページサイズに基づいて、アイテムのためのセット及びウェイグループを識別し、第１置換ポリシーデータエントリに基づいて、ウェイグループ内のウェイを識別するように構成されている。キャッシュの第１キャッシュエントリに対する更新は、識別されたウェイ、セット及びウェイグループに対して実行される。いくつかの例では、ウェイグループ内のウェイを識別することは、アイテムに関連するページサイズの最長未使用時間のキャッシュエントリをウェイグループ内のウェイが記憶していることを第１置換ポリシーデータエントリが示すことを判別することを含む。

いくつかの例では、第１置換ポリシーデータエントリは、ウェイグループ内の何れのウェイが最長未使用時間データを含むかを示す１ビットを含む。いくつかの例では、キャッシュコントローラは、キャッシュの第２キャッシュエントリに対する第２更新を検出し、第２キャッシュエントリに対応する第３置換ポリシーデータエントリであって、第２ページサイズに関連する第３置換ポリシーデータエントリに対する第２変更を検出し、第２ページサイズがキャッシュ内のデータの最小ページサイズであることを判別するように構成されており、第３置換ポリシーデータエントリがキャッシュ内のデータの最小ページサイズに関連していることに応じて、他の置換データが変更されない。

命令を実行するように構成された実行パイプラインと、キャッシュと、を備えるプロセッサも提供される。キャッシュは、キャッシュデータを記憶するキャッシュメモリであって、命令の仮想メモリアドレスを物理メモリアドレスに変換する変換索引バッファを含むキャッシュメモリと、置換ポリシーデータを記憶する置換ポリシーメモリと、キャッシュコントローラと、を備える。キャッシュコントローラは、キャッシュメモリの第１キャッシュエントリに対する更新を検出し、第１キャッシュエントリに対応する第１置換ポリシーデータエントリであって、第１ページサイズに関連する第１置換ポリシーデータエントリに対する第１変更を検出し、第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリであって、第１キャッシュエントリに関連する第２置換ポリシーデータエントリを識別し、第２置換ポリシーデータエントリに対して第１変更を行うように構成されている。

いくつかの例では、第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている。いくつかの例では、キャッシュは、複数のウェイグループにグループ化された複数のウェイを含み、第１置換ポリシーデータエントリは、ウェイグループのうち第１キャッシュエントリを含む第１ウェイグループの置換ポリシーデータを記憶し、第２置換ポリシーデータエントリは、第１ウェイグループの置換ポリシーデータを記憶する。いくつかの例では、第１キャッシュエントリは、第１メモリページの変換を記憶し、第１メモリページは、第１ウェイグループ内のキャッシュの第１セット、及び、複数のウェイグループのうち第２ウェイグループ内のキャッシュの第２セットにマッピングされており、第２セットは、第１セットとは異なるセットである。

本明細書における開示に基づいて多くの変形が可能であることを理解されたい。上記では、特徴及び要素が特定の組み合わせで説明されているが、各特徴又は要素は、他の特徴及び要素無しに単独で使用されてもよいし、他の特徴及び要素を伴って又は伴わずに様々な組み合わせで使用されてもよい。

提供された方法は、汎用コンピュータ、プロセッサ又はプロセッサコアで実施されてもよい。適切なプロセッサには、例として、汎用プロセッサ、専用プロセッサ、従来のプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、複数のマイクロプロセッサ、ＤＳＰコアに関連する１つ以上のマイクロプロセッサ、コントローラ、マイクロコントローラ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）回路、他のタイプの集積回路（ＩＣ）、及び／又は、ステートマシンが含まれる。このようなプロセッサは、処理されたハードウェア記述言語（ＨＤＬ）命令（このような命令は、コンピュータ可読媒体に記憶することが可能である）の結果及びネットリストを含む他の中間データを用いて製造プロセスを構成することによって製造され得る。このようなプロセスの結果は、実施形態の態様を実施するプロセッサを製造するために半導体製造プロセスにおいて使用されるマスクワークであってもよい。

本明細書で提供された方法又はフローチャートは、汎用コンピュータ又はプロセッサによる実行のために非一時的なコンピュータ可読記憶媒体に組み込まれたコンピュータプログラム、ソフトウェア又はファームウェアで実施されてもよい。非一時的なコンピュータ可読記憶媒体の例には、例えば読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、レジスタ、キャッシュメモリ、半導体メモリデバイス、内蔵ハードディスク、リムーバブルディスク等の磁気媒体、光磁気記憶媒体、例えばＣＤ－ＲＯＭディスク及びデジタル多用途ディスク（ＤＶＤ）等の光学媒体が含まれる。

Claims (17)

1. キャッシュコントローラが、第１アドレス空間から第２アドレス空間への変換を記憶するキャッシュであって、複数のウェイグループに分割された複数のウェイをそれぞれ含む複数のセットを有するキャッシュの置換ポリシーデータを更新する方法であって、
   前記キャッシュコントローラが、
   前記キャッシュの第１キャッシュエントリに対する更新を検出することであって、前記キャッシュの第１キャッシュエントリは、前記複数のセットのうち第１セット及び前記複数のウェイグループのうち第１ウェイグループに関連している、ことと、
   前記第１キャッシュエントリに対する更新に応じて、前記第１キャッシュエントリ及び第１ウェイグループに対応する第１置換ポリシーデータエントリを変更することであって、前記第１置換ポリシーデータエントリは第１ページサイズに関連しており、前記変更することは、前記キャッシュの前記第１キャッシュエントリが前記第１ページサイズの最長未使用時間のエントリではないことを前記第１置換ポリシーデータエントリに示させる、ことと、
   前記第１置換ポリシーデータエントリを変更したことに応じて、前記第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリを識別することであって、前記第２置換ポリシーデータエントリは、前記第１キャッシュエントリ及び前記第１ウェイグループに関連する、ことと、
   前記キャッシュの第１キャッシュエントリが前記第２ページサイズの最長未使用時間のエントリではないことを示すように、前記第２置換ポリシーデータエントリを変更することと、を含む、
   方法。
2. 前記第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている、
   請求項１の方法。
3. 前記第１キャッシュエントリは、第１メモリページの変換を記憶し、
   前記第１メモリページは、前記第１ウェイグループ内の前記キャッシュの第１セット、及び、前記複数のウェイグループのうち第２ウェイグループ内の前記キャッシュの第２セットに関連付けられており、前記第２セットは、前記第１セットとは異なるセットであり、前記第１メモリページは、ページサイズに基づいて、前記第１ウェイグループ内の前記キャッシュの第１セット、又は、前記第２ウェイグループ内の前記キャッシュの第２セットにマッピングされている、
   請求項１の方法。
4. 前記キャッシュ内のミスを検出することと、
   前記ミスに応じて、前記キャッシュの前記第１キャッシュエントリに配置されたアイテムをフェッチすることと、
   前記アイテムに関連するアドレス及び前記アイテムに関連する第１ページサイズに基づいて、前記アイテムの前記第１セット及び前記第１ウェイグループを識別することと、
   前記第１置換ポリシーデータエントリに基づいて、前記第１ウェイグループ内のウェイを識別することと、を含み、
   前記キャッシュの前記第１キャッシュエントリに対する更新は、識別されたウェイ、セット及びウェイグループに対して実行される、
   請求項１の方法。
5. 前記第１ウェイグループ内のウェイを識別することは、
   前記アイテムに関連する前記第１ページサイズの最長未使用時間のキャッシュエントリを前記第１ウェイグループ内の前記ウェイが記憶していることを前記第１置換ポリシーデータエントリが示すことを判別することを含む、
   請求項４の方法。
6. 前記第１置換ポリシーデータエントリは、前記第１ウェイグループ内の何れのウェイが最長未使用時間データを含むかを示す１ビットを含む、
   請求項４の方法。
7. 前記キャッシュの第２キャッシュエントリに対する第２更新を検出することと、
   前記第２キャッシュエントリに対応する第３置換ポリシーデータエントリであって、前記第２ページサイズに関連する第３置換ポリシーデータエントリに対する第２変更を検出することと、
   前記第２ページサイズが前記キャッシュ内のデータの最小のページサイズであることを判別することと、を含み、
   前記第３置換ポリシーデータエントリが前記キャッシュ内のデータの最小のページサイズに関連していることに応じて、他の置換データが変更されない、
   請求項１の方法。
8. 第１アドレス空間から第２アドレス空間への変換を記憶し、複数のウェイグループに分割された複数のウェイをそれぞれ含む複数のセットを有するキャッシュであって、
   キャッシュデータを記憶するキャッシュメモリと、
   置換ポリシーデータを記憶する置換ポリシーメモリと、
   キャッシュコントローラと、を備え、
   前記キャッシュコントローラは、
   前記キャッシュメモリの第１キャッシュエントリに対する更新を検出することであって、前記キャッシュの第１キャッシュエントリは、前記複数のセットのうち第１セット及び前記複数のウェイグループのうち第１ウェイグループに関連している、ことと、
   前記第１キャッシュエントリに対する更新に応じて、前記第１キャッシュエントリ及び第１ウェイグループに対応する第１置換ポリシーデータエントリを変更することであって、前記第１置換ポリシーデータエントリは第１ページサイズに関連しており、前記変更することは、前記キャッシュの前記第１キャッシュエントリが前記第１ページサイズの最長未使用時間のエントリではないことを前記第１置換ポリシーデータエントリに示させる、ことと、
   前記第１置換ポリシーデータエントリを変更したことに応じて、前記第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリを識別することであって、前記第２置換ポリシーデータエントリは、前記第１キャッシュエントリ及び前記第１ウェイグループに関連する、ことと、
   前記キャッシュの第１キャッシュエントリが前記第２ページサイズの最長未使用時間のエントリではないことを示すように、前記第２置換ポリシーデータエントリを変更することと、
   を行うように構成されている、
   キャッシュ。
9. 前記第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている、
   請求項８のキャッシュ。
10. 前記第１キャッシュエントリは、第１メモリページの変換を記憶し、
    前記第１メモリページは、前記第１ウェイグループ内の前記キャッシュの第１セット、及び、前記複数のウェイグループのうちの第２ウェイグループ内の前記キャッシュの第２セットに関連付けられており、前記第２セットは、前記第１セットとは異なるセットであり、前記第１メモリページは、ページサイズに基づいて、前記第１ウェイグループ内の前記キャッシュの第１セット、又は、前記第２ウェイグループ内の前記キャッシュの第２セットにマッピングされている、
    請求項８のキャッシュ。
11. 前記キャッシュコントローラは、
    前記キャッシュメモリ内のミスを検出し、
    前記ミスに応じて、前記キャッシュの前記第１キャッシュエントリに配置されたアイテムをフェッチし、
    前記アイテムに関連するアドレス及び前記アイテムに関連する第１ページサイズに基づいて、前記アイテムの前記第１セット及び前記第１ウェイグループを識別し、
    前記第１置換ポリシーデータエントリに基づいて、前記第１ウェイグループ内のウェイを識別するように構成されており、
    前記キャッシュの前記第１キャッシュエントリに対する更新は、識別されたウェイ、セット及びウェイグループに対して実行される、
    請求項８のキャッシュ。
12. 前記キャッシュコントローラは、
    前記アイテムに関連する前記第１ページサイズの最長未使用時間のキャッシュエントリを前記第１ウェイグループ内の前記ウェイが記憶していることを前記第１置換ポリシーデータエントリが示すことを判別することによって、前記第１ウェイグループ内の前記ウェイを識別するように構成されている、
    請求項１１のキャッシュ。
13. 前記第１置換ポリシーデータエントリは、前記第１ウェイグループ内の何れのウェイが最長未使用時間データを含むかを示す１ビットを含む、
    請求項１１のキャッシュ。
14. 前記キャッシュコントローラは、
    前記キャッシュの第２キャッシュエントリに対する第２更新を検出し、
    前記第２キャッシュエントリに対応する第３置換ポリシーデータエントリであって、前記第２ページサイズに関連する第３置換ポリシーデータエントリに対する第２変更を検出し、
    前記第２ページサイズが前記キャッシュ内のデータの最小のページサイズであることを判別するように構成されており、
    前記第３置換ポリシーデータエントリが前記キャッシュ内のデータの最小のページサイズに関連していることに応じて、他の置換データが変更されない、
    請求項８のキャッシュ。
15. 命令を実行するように構成された実行パイプラインと、
    第１アドレス空間から第２アドレス空間への変換を記憶するキャッシュであって、複数のウェイグループに分割された複数のウェイをそれぞれ含む複数のセットを有するキャッシュと、を備えるプロセッサであって、
    前記キャッシュは、
    キャッシュデータを記憶するキャッシュメモリと、
    置換ポリシーデータを記憶する置換ポリシーメモリと、
    キャッシュコントローラと、を備え、
    前記キャッシュコントローラは、
    前記キャッシュメモリの第１キャッシュエントリに対する更新を検出することであって、前記キャッシュの第１キャッシュエントリは、前記複数のセットのうち第１セット及び前記複数のウェイグループのうち第１ウェイグループに関連している、ことと、
    前記第１キャッシュエントリに対する更新に応じて、前記第１キャッシュエントリ及び第１ウェイグループに対応する第１置換ポリシーデータエントリを変更することであって、前記第１置換ポリシーデータエントリは第１ページサイズに関連しており、前記変更することは、前記キャッシュの前記第１キャッシュエントリが前記第１ページサイズの最長未使用時間のエントリではないことを前記第１置換ポリシーデータエントリに示させる、ことと、
    前記第１置換ポリシーデータエントリを変更したことに応じて、前記第１ページサイズよりも小さい第２ページサイズに関連する第２置換ポリシーデータエントリを識別することであって、前記第２置換ポリシーデータエントリは、前記第１キャッシュエントリに関連する、ことと、
    前記キャッシュの第１キャッシュエントリが前記第２ページサイズの最長未使用時間のエントリではないことを示すように、前記第２置換ポリシーデータエントリを変更することと、
    を実行するように構成されている、
    プロセッサ。
16. 前記第１キャッシュエントリは、仮想アドレスから物理アドレスへの変換を記憶するように構成されている、
    請求項１５のプロセッサ。
17. 前記第１キャッシュエントリは、第１メモリページの変換を記憶し、
    前記第１メモリページは、前記第１ウェイグループ内の前記キャッシュの第１セット、及び、前記複数のウェイグループのうち第２ウェイグループ内の前記キャッシュの第２セットに関連付けられており、前記第２セットは、前記第１セットとは異なるセットであり、前記第１メモリページは、ページサイズに基づいて、前記第１ウェイグループ内の前記キャッシュの第１セット、又は、前記第２ウェイグループ内の前記キャッシュの第２セットにマッピングされている、
    請求項１５のプロセッサ。

Images