JP7062696B2 - 仮想キャッシュにおける仮想および実変換の共有 - Google Patents

Description

本開示は、デジタル・コンピュータ・システムの分野に関し、より詳細には、キャッシュ・メモリへのアクセスを制御するための方法に関する。

最近のマイクロプロセッサ・アーキテクチャは、ソフトウェアがいわゆる「仮想」（または時に「論理」と呼ばれる）アドレスを使用してメモリ位置を参照するようにする。メモリ・アクセス自体は、「物理」（または時に「絶対」と呼ばれる）アドレスを使用して行われる。２つの間で変換するために、典型的に、変換ルックアサイド・バッファ（ＴＬＢ）と呼ばれるデータ構造が伴う。変換するプロセスは時に、特にＩＢＭ（Ｒ）ｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ）では、動的アドレス変換（ＤＡＴ）と呼ばれる。

典型的なマイクロプロセッサ・システムでは、プロセッサ・コアの「近くに」メモリ内容のコピーを保つことによってメモリ・アクセスを高速化するために、数レベルのキャッシュが使用される。ＤＡＴをサポートするキャッシュ実装に関して、頻繁に使用される実装は、論理アドレスの一部を使用してキャッシュ・ディレクトリへインデックス付けし、そしてルックアップ要求が比較される、いわゆる「タグ」情報は絶対アドレスを使用している。これは、プログラムによって使用される論理アドレスの絶対アドレスへの変換を必要としており、通常ＴＬＢにおけるルックアップを伴う。

しかしながら、ますます増大するマイクロプロセッサ・コア・キャッシュと共に、ＴＬＢも増大しなければならず、そしてディレクトリ・ルックアップに加えてＴＬＢルックアップの電力消費はマイクロプロセッサ・コア電力の著しい一因である。また、ＴＬＢルックアップ自体がクリティカル・パスの一部になることになるので、ＴＬＢのサイズはタイミング制約によって制限される。

米国特許出願第１５／６２５，２２３号

したがって、当技術分野では上記の問題に対処する必要がある。

様々な実施形態が、独立請求項の主題によって記載される、キャッシュ・メモリへのアクセスを制御するための方法、装置およびコンピュータ・プログラム製品を提供する。有利な実施形態は従属請求項に記載される。本発明の実施形態は、それらが相互に排他的でなければ、互いと自由に組み合わされることができる。

一実施形態が、プロセッサにおける仮想キャッシュ・ディレクトリを対象とする。プロセッサは、仮想メモリおよび複数スレッドをサポートするように構成される。本仮想キャッシュ・ディレクトリは複数のディレクトリ・エントリを含み、各エントリはキャッシュ・ラインと関連付けられる。各キャッシュ・ラインはタグを有する。タグは、論理アドレス、アドレス空間識別子、実アドレス・ビット・インジケータ、および仮想アドレス対実アドレス・インジケータを含む。

一実施形態が、仮想メモリ・サポートを伴うプロセッサのための１次プロセッサ・キャッシュを動作させる方法を対象とする。プロセッサは論理インデックス付きかつ論理タグ付きキャッシュ・ディレクトリを使用し、そしてディレクトリにおけるエントリは、対応する論理メモリ・アドレスに加えて絶対メモリ・アドレスを、および論理アドレスが実アドレスと同じであることを示す仮想対実フラグを含む。本方法は、キャッシュ・ディレクトリにおける第１のエントリにおける論理メモリ・アドレスにコードを記憶する。一旦コードが記憶されると、ユーザ・コードが下位のオペレーティング・システムを呼び出す。オペレーティング・システムは絶対メモリ・アドレスからコードを読み取る。一旦コードが絶対メモリ・アドレスから読み取られると、第１のエントリにトランスロードが実行される。トランスロードに続いて、本方法は、絶対メモリ・アドレスが論理メモリ・アドレスに等しいかどうかを判定する。絶対メモリ・アドレスが論理メモリ・アドレスに等しければ、仮想対実フラグはオンに設定されて、絶対および論理メモリ・アドレスが同じであることを示す。

以下に本発明の実施形態が、図面を参照しつつ、単に例として、更に詳細に説明される。

本開示の一例に従ってコンピュータ・システムを例示する。 ２レベル・キャッシュを持つキャッシュ・メモリのキャッシュ構造にアクセスするための図を例示するブロック図である。 図２のキャッシュ・メモリを動作させるための方法のフローチャートである。 図２のキャッシュ・メモリにおいてシノニムを解決するための方法のフローチャートである。 キャッシュ・メモリへのアクセスを制御するための方法のフローチャートである。 実施形態に係るタグの略図である。 共有メモリを通じたデータ転送のプロセスを例示するフローチャートである。 実施形態に係るキャッシュへの仮想対実の拡張を例示するフローチャートである。 実施形態に係る拡張を使用するディレクトリ比較の略図である。 実施形態に係るタグの略図である。 実施形態に係る第１のスレッドによってキャッシュ・ラインにアクセスするためのプロセスを例示するフローチャートである。 実施形態に係る第２のスレッドによって共有キャッシュ・ラインにアクセスするためのプロセスを例示するフローチャートである。 実施形態に係る組み合わされた図１１および図１２のプロセスを例示する決定木である。 実施形態に係るＬ１キャッシュ・ミスの解決を例示するフローチャートである。 異なる変換を使用するスレッドに対してキャッシュを共有する略図である。 実施形態に係るディレクトリ・エントリの部分を共有する略図である。 実施形態に係るディレクトリ・エントリの部分スレッド共有のプロセスを実装する決定木である。

本発明の様々な実施形態の説明が例示の目的で提示されることになるが、網羅的であるとは、または開示される実施形態に限定されるとは意図されない。記載される実施形態の範囲および思想から逸脱することなく、多くの変更および変形が当業者にとって明らかであろう。本明細書で使用される技術用語は、実施形態の原理、実際的応用もしくは市場で見つかる技術に対する技術的改良を最もよく説明するように、または当業者が理解することを可能にするように選ばれた。

キャッシュ・メモリはセット・アソシアティブ・キャッシュである。

本方法は、全ての変換関連情報をＬ１キャッシュに記憶する論理インデックス付き、論理タグ付きディレクトリを使用する。できる限り多くの電力を節約するために、本方法は、セット・ディレクトリを使用して、その他のＬ１キャッシュ構造に対する潜在的なヒット・セットを選択している。セット・ディレクトリはキャッシュ・アレイ遅延選択として使用され、それ故に従前の設計と比較して電力および領域予算を増すことはない。セット・ディレクトリを使用して、更なる電力を節約するために、従前のセット・アソシアティブ・ディレクトリ構造の代わりに「垂直スタック」ディレクトリ（すなわち有効化ディレクトリ）が使用される。結果として、常に一度に１つのセットだけが読み出されることができる一方で、先行技術では所与のインデックスに属する全てのセットが並列に読み取られ得る。例えば、キャッシュ・ディレクトリがシノニム問題を解決するために使用されることができるので、有効化ディレクトリ・セットは並列にアクセスされる必要はなくてもよい。

本方法は、Ｌ１キャッシュ・ヒットがより高レベルのキャッシュからの有効化を必要とする先行技術の方法と比較して高速アクセス時間および更に低い電力消費の改善されたセット・アソシアティブ・キャッシュ・メモリを提供する利点を有することができる。

その比較的大きなサイズのため、ＴＬＢは通常、メモリ・アレイに近接して配置されることができない。結果として、セット・アソシアティブ・キャッシュ・メモリの総キャッシュ・アクセス時間は、そのＴＬＢおよびメモリ・アレイのサイズと共に増加する。本方法は、論理タグ付きかつ論理インデックス付き有効化ディレクトリを使用し、したがってＬ１キャッシュ・ヒット信号発生のためにＴＬＢに給電する必要を回避することができる。

一実施形態によれば、第２の検索がセットにおけるキャッシュ・ラインの存在を確認しない場合、ミス信号を発生する。ミス信号は、要求された実効アドレス（論理または仮想アドレスとも称される）に対するキャッシュ・ミスを示すキャッシュ・ミス信号である。キャッシュ・ミス信号は、第１の検索がセット・ディレクトリに要求された論理アドレスを見つけることに失敗した場合にも発生されてもよい。発生されたミス信号に応答して、要求されたキャッシュ・ラインは、より高いキャッシュ・レベルにおいてまたはメインメモリ（例えばＲＡＭ）において検索されてもよい。

一実施形態によれば、キャッシュ・メモリは変換ルックアサイド・バッファＴＬＢを更に備えており、１次キャッシュ・ディレクトリにおける所与のエントリが有効ビット、実効アドレスの一部分およびセット・インデックスを記憶しており、第２の検索がセットにおけるキャッシュ・ラインの存在を確認しない場合、本方法は、１次キャッシュ・ディレクトリにおいてライン・インデックス・ビットを検索して、１次キャッシュ・ディレクトリにおける各セットに対する論理ポインタに帰着することであって、論理ポインタがセット・インデックスおよび実効アドレスの一部分を備える、ことと、論理ポインタのうちセット・インデックスがセット識別子に一致する論理ポインタを選択することと、実効アドレスと関連する絶対アドレスを特定するためにＴＬＢにおいて実効アドレスを検索することと、キャッシュ・メモリのより高レベルの２次キャッシュ・ディレクトリにおける各セットにおける実効アドレスに対応するエントリであって、他の絶対アドレスを備える、エントリを得るために２次キャッシュ・ディレクトリにおいて実効アドレスを検索することと、２次キャッシュ・ディレクトリの各得られた絶対アドレスをＴＬＢの絶対アドレスと比較して、２次キャッシュ・ディレクトリのセットの他のセット識別子に帰着することと、他のセット識別子を有する２次キャッシュ・ディレクトリのセットのエントリの論理アドレスを選択された論理ポインタと比較し、そして比較結果に基づいてミス信号を確認するまたはセットおよび有効化ディレクトリを更新することとを更に含む。

ＴＬＢおよびより高レベルのキャッシュは例えば、より低レベルのキャッシュにおけるキャッシュ・ミスの場合に使用される。これは、より低いキャッシュ・レベルでのキャッシュ・ミスの信頼できる有効化または確認を提供してもよい。

一実施形態によれば、１次キャッシュ・ディレクトリの検索は第１の検索と並列に行われる。この実施形態は、データへのアクセスを更に高速化することができる。

一実施形態によれば、本方法は、論理ポインタの有効ビットが有効状態に設定されている場合にヒット信号の発生が行われることを更に含む。有効ビットは、キャッシュ・ラインにおけるデータが有効であるか否かを示す情報のビットである。これは、さもなければ無効化されたデータにアクセスして、引き起こされる訂正を処理するために必要とされるであろう処理時間を更に節約することができる。

一実施形態によれば、ＴＬＢにおける検索および２次キャッシュ・ディレクトリにおける検索は並列に行われる。この実施形態は、データへのアクセスを更に高速化することができる。

一実施形態によれば、第１の群のビットはタグ・フィールドからの最下位ビットであり、そして第２の群のビットはタグ・フィールドからの最上位ビットである。第２の群のビットは、セット・ディレクトリの検索結果を確認するために第１の群のビットに相補的であってもよい。例えば、実効アドレスが０：４９ビットのタグ・フィールドを有する場合、第１の群のビットは３７：４９であってもよく、そして第２の群のビットは０：３６であってもよい。しかしながら、タグ・フィールド０：４９のいかなる部分集合でも第１または第２の群のビットとして使用されることができる。第１の群のビットの幅（すなわちビット数）は、誤った予測（あまり小さくない）とタイミング（あまり広い比較でない）制約との間のトレード・オフに基づいてもよい。第１の群のために実効アドレスのライン・インデックス（５０：５５）の隣のビットを使用することは、それが小さなメモリ・フットプリントのプログラムのためにも働くので、有益であり得る。例えば、ビット０：１２が第１の群のために使用される場合、巨大なプログラムだけが０：１２で異なる実効アドレスを有することができ、通常サイズのプログラムは１つのセットを使用し得るだけであるので、大抵のプログラムはｎ－ｗａｙ（例えばｎ＝８）連想を使用することができない可能性がある。言い換えれば、第１の群のビット（例えば３７：４９）は、それらが大抵のメモリ・アクセスに対して異なるがライン・インデックスと重複しないように選ばれる。

一実施形態によれば、有効化ディレクトリは、キャッシュ・メモリの全てのセットの各キャッシュ・ラインごとに１つのディレクトリ・エントリを保持する１つの物理アレイ構造から構築される。この実施形態は、一度に１つのセットだけが読み出されることができることを可能にしてもよい一方で、先行技術では所与のインデックスに属する全てのセットが並列に読み取られ得る。この実施形態は、したがってデータへのアクセスを更に高速化することができる。例えば、セット・ディレクトリの結果（例えばセット識別子）は、有効化ディレクトリを検索するためのライン・インデックス（例えばビット５０：５５）への拡張として使用されてもよい。

一実施形態によれば、１次キャッシュ・ディレクトリにおける所与のエントリが有効ビット、実効アドレスの一部分およびセット・インデックスを記憶しており、本方法は、第１の検索と並列に、１次キャッシュ・ディレクトリにおいてライン・インデックス・ビットを検索して、１次キャッシュ・ディレクトリにおける各セットに対する有効ビット値に帰着することと、有効ビット値のうち関連するセット・インデックスがセット識別子に一致する有効ビット値を選択することであって、有効ビット値が有効状態を示す場合にヒット信号の発生が行われる、こととを更に含む。これは、さもなければ無効化されたデータにアクセスして、引き起こされる訂正を処理するために必要とされるであろう処理時間を更に節約することができる。

一実施形態によれば、１次キャッシュ・ディレクトリはＬ１レベル・キャッシュ・ディレクトリである。一実施形態によれば、２次キャッシュ・ディレクトリはＬ２レベル・キャッシュ・ディレクトリである。これらの実施形態は、従来のシステムにシームレスに統合されてもよい。

一実施形態によれば、キャッシュ・メモリは、２次キャッシュ・ディレクトリを更に備えるマルチ・レベル・キャッシュ・ディレクトリである。キャッシュ・メモリはセット選択メモリである。

一実施形態によれば、１次キャッシュ・ディレクトリにおける所与のエントリが有効ビット、実効アドレスの一部分およびセット・インデックスを記憶する。本方法は、実効アドレスの第２の実効アドレス・シノニムを受けることと、第２の実効アドレスを使用して第１および第２の検索を繰り返すことと、第２の検索が第２の実効アドレスによって参照されるキャッシュ・ラインの存在を確認しない場合、第２の実効アドレスに対応するセット・ディレクトリのエントリを無効化することと、ミスを検出するために第２の実効アドレスを使用して第１の検索を行うことと、１次キャッシュ・ディレクトリにおいて第２の実効アドレスを検索して、１次キャッシュ・ディレクトリにおける各セットに対する論理ポインタに帰着することであって、論理ポインタがセット・インデックスおよび第２の実効アドレスの一部分を備える、ことと、キャッシュ・メモリのより高レベルの２次キャッシュ・ディレクトリにおける各セットにおける第２の実効アドレスに対応するエントリを得るために２次キャッシュ・ディレクトリにおいて第２の実効アドレスを検索することと、２次キャッシュ・ディレクトリのセットのエントリの論理アドレスを論理ポインタの各々と比較し、そして比較結果に基づいて１次キャッシュ・ディレクトリにおけるキャッシュ・ラインの存在を確認することと、実効アドレスに関連したエントリを第２の実効アドレスで上書きすることによってセットおよび有効化ディレクトリを更新することと、第１の検索、第２の検索および条件付きヒット信号の発生を繰り返すこととを更に含む。この実施形態は、キャッシュ・メモリでのシノニム問題を効率的に解決する利点を有することができる。それは、次のレベルのキャッシュに依存することによってシノニム問題を解決する。それは、Ｌ１キャッシュ・ディレクトリを使用してＬ１キャッシュおよびＬ２キャッシュを結びつける。

図１は、本開示の一例に従ってコンピュータ・システム１００を例示する。コンピュータ・システム１００は、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ（ＩＢＭ（Ｒ））によって提供されるｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ）に基づいてもよい。コンピュータ・システム１００はセット・アソシアティブ・キャッシュ・メモリ構造を使用してもよい。コンピュータ・システム１００は、少なくとも１つの処理ユニット１０１を備える。処理ユニット１０１は、入出力（Ｉ／Ｏ）デバイス１１４（表示モニタ、キーボードおよび永久記憶デバイスなど）、プログラム命令を実行するために処理ユニットによって使用されるメモリ・デバイス１１６（ランダム・アクセス・メモリまたはＲＡＭなど）、ならびに主要目的が、コンピュータが最初にオンにされるたびに周辺機器の１つを捜してそれからオペレーティング・システムをロードすることであるファームウェア１１８を含め、様々な周辺デバイスに接続されてもよい。処理ユニット１０１は、汎用インターコネクトまたはバス１２０を含め、様々な手段によって周辺デバイス（例えばファームウェア１１８、入出力デバイス１１４およびメモリ１１６）と通信する。

処理ユニット１０１は、コンピュータを動作させるためにプログラム命令を実行する複数のレジスタおよび実行ユニットを有するプロセッサ・コア１２２を含む。例証的な処理ユニットには、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎによって市販されるＰｏｗｅｒＰＣ（ＴＭ）プロセッサを含む。処理ユニット１０１は、１つまたは複数のキャッシュも有することができる。例えば、処理ユニット１０１は、２つのキャッシュ１２６および１３０を備えるとして図示される。キャッシュは、メモリ１１６から値をロードするより長いステップを回避することによって処理を高速化するために、プロセッサによって繰り返しアクセスされる可能性がある値を一時的に記憶するために使用される。

キャッシュ１２６および１３０は、プロセッサがメモリ１１６から前もって転送されたデータまたは命令の部分集合への比較的高速アクセス時間を達成することを可能にするセット・アソシアティブ・キャッシュである。

キャッシュ１２６はプロセッサ・コア１２２と一体的にパッケージされてもよい。キャッシュ１２６は、高速メモリ・デバイスを使用して実装される命令アレイ（図示せず）およびデータ・アレイ１４１を備えてもよい。命令およびデータは、オペランドが命令対データである演算をプロセッサ・コアが要求しているかどうかを示す信号を調べることによって、それぞれのキャッシュに向けられてもよい。キャッシュ１２６は、データ・アレイ１４１と関連するキャッシュ・ディレクトリ１４２を更に備えてもよい。例えば、データ・アレイ１４１における各キャッシュ・ラインは、キャッシュ・ディレクトリ１４２に対応するエントリを有する。キャッシュ・ディレクトリ１４２は、実効アドレスによって特定されるデータがデータ・アレイ１４１に記憶されているかどうかを示してもよい。例えば、実効アドレスを参照するプロセッサ命令がキャッシュ１２６に提供されることができる。実効アドレスがキャッシュ・ディレクトリ１４２にある場合、プロセッサは、アクセス基準が満たされていることを条件として、それがデータ・アレイ１４１から参照されたデータを得ることができると知っており、アクセス基準は有効ビットが設定されていること等を要求してもよい。例えば、実効アドレスは、タグ・フィールド、ライン・インデックス・フィールドおよびバイト・フィールドを含む。実効アドレスのタグ・フィールドは、本明細書に記載されるようにキャッシュ「ヒット」情報を提供するために活用される。実効アドレスのライン・インデックス・フィールドは、ライン・インデックス・フィールドによってインデックス付けされる、例えばデータ・キャッシュ・アレイ１４１内のＮ個のキャッシュ・ラインを得るために活用され、ＮはＮ－アソシアティブ・キャッシュ・メモリにおけるセット数である。Ｎ個のキャッシュ・ラインの１つがセット識別子を使用して選択されてもよく（遅延選択の一部として）、そして実効アドレスのバイト・フィールドは、選択されたキャッシュ・ライン内の特定のバイトにインデックス付けするために活用される。

データ・アレイ１４１およびキャッシュ・ディレクトリ１４２は、例えば、４Ｍまたは８Ｍ個のチップ・アレイの構成で容易に入手可能であるように、従来のメモリ・アレイから構築されてもよい。キャッシュ１２６は、例えばプロセッサ・コア１２２とキャッシュとの間のデータの転送を管理するキャッシュ・コントローラ（図示せず）と関連付けられる。

データ・キャッシュ・アレイ１４１は、様々なデータ値を個々に記憶する多くのキャッシュ・ラインを有する。キャッシュ・ラインは、「セット」と呼ばれるキャッシュ・ラインの群へ分けられる。例証的なキャッシュ・ラインは、状態ビット・フィールド、排他性ビット・フィールド、および実行命令またはデータを記憶するための値フィールドを含む。状態ビット・フィールドおよび包括性ビット・フィールドは、マルチプロセッサ・コンピュータ・システムにおけるキャッシュ・コヒーレンシを維持するために使用される。アドレス・タグは、対応するメモリ・ブロックの完全アドレスの部分集合である。アドレス・タグ・フィールド内のタグの１つとの到来する実効アドレスの比較一致がキャッシュ「ヒット」を示す。キャッシュにおけるアドレス・タグ（ならびに時に状態ビットおよび包括性ビット・フィールド）の全ての集合がディレクトリと称され、そして値フィールドの全ての集合がキャッシュ・エントリ・アレイである。

キャッシュ１２６はレベル１（Ｌ１）キャッシュと称されてもよく、そしてキャッシュ１３０は、それが（Ｌ１）キャッシュ１２６をサポートするので、レベル２（Ｌ２）キャッシュと称されてもよい。例えば、キャッシュ１３０は、メモリ１１６とＬ１キャッシュとの間の媒介として作用してもよく、そしてより長いアクセス・ペナルティではあるが、Ｌ１キャッシュができるより大量の情報（命令およびデータ）を記憶することができる。例えば、キャッシュ１３０は２５６または５１２キロバイトの記憶容量を有してもよい一方で、Ｌ１キャッシュは６４キロバイトの総記憶を有してもよい。キャッシュ１３０はバス１２０に接続され、そしてメモリ１１６からプロセッサ・コア１２２への情報の全てのロードがキャッシュ１３０を通して起こってもよい。図１が２レベル・キャッシュ階層だけを描くとはいえ、多レベルの直列に接続されるキャッシュがあるマルチ・レベル・キャッシュ階層が提供されることができる。例えば、処理ユニット１０１の部品は単一の集積チップにパッケージされてもよい。

図１には、実効アドレスを対応する絶対アドレスに変換するための変換ルックアサイド・バッファ（ＴＬＢ）１４３も図示される。詳細には、ＴＬＢ１４３は、実効アドレスのページ番号部分を対応する実ページ番号に変換してもよい。例えば、実効アドレスのタグ・フィールドがＴＬＢ１４３に送られて、対応する実ページ番号に変換されてもよい。

他の例では、コンピュータ・システム１００は、第１のもの（ＴＬＢ１）が第１のレベルのバッファであり、そして第２のもの（ＴＬＢ２）が、上記第１のものに見つからないアドレスの場合に第１のものにアドレス情報を供給するように配置される第２のレベルの変換ルックアサイド・バッファである、少なくとも２つの変換ルックアサイド・バッファを備えてもよい。例えば、メモリにおけるアドレス変換テーブルは多段構造であってもよい。例えば、２段テーブルの場合、第１レベルのテーブルは、セグメント・テーブルと呼ばれており、エントリを含み、各々ポイントによってＭＢのメモリを第２レベルのテーブルにマッピングし、これはページ・テーブルと呼ばれており、４ＫＢのメモリをマッピングする２５６個のエントリを含む。ＴＬＢ２は２種類のエントリ：１ＭＢセグメントおよび個々の４ＫＢページを有してもよい。第１レベルＴＬＢ（ＴＬＢ１）で変換が入手可能でない場合、必要とされる変換を提供する４ＫＢページ・エントリを求めてＴＬＢ２が検索される。そうでなければ、ＴＬＢ２は、変換されることになるアドレスを含むセグメントのためのセグメント・エントリを求めて検索される。そのようなエントリが見つけられれば、メモリにおけるセグメント・テーブルにアクセスしなくても適切なページ・テーブルが直接アクセスされることができるので、メモリにおける両テーブルを使用する変換は省かれる。そして、ＴＬＢ１はエントリの２次元アレイ、例えば、３２エントリ長かつ４エントリ幅を備えてもよい。各エントリは、変換された仮想アドレスおよびそれが変換した実アドレスを含む。この例では、ＴＬＢ１４３はＴＬＢ１であってもよい。

一例では、コンピュータ・システム１００は、ＩＢＭ（Ｒ）のｚ／ＶＭ（Ｒ）などの仮想化環境におけるハードウェア資源として使用されてもよい。例えば、処理ユニット１０１は、仮想マシンまたは論理区画においてハイパーバイザ下で実行するゲストから要求を受けてもよい。

図２は、本開示の一例に従って実効アドレス（または論理アドレスもしくは仮想アドレス）２０１を介して２レベル・キャッシュを持つキャッシュ・メモリのキャッシュ構造２００にアクセスするための図を例示するブロック図である。キャッシュ・メモリは、例えばＬ１キャッシュにｍセットおよびＬ２キャッシュにｎセットを備えるセット・アソシアティブ・キャッシュである。ｍはｎに等しくても等しくなくてもよい。キャッシュ構造２００は、Ｌ１キャッシュ２２６およびＬ２キャッシュ２３０を備える。Ｌ１キャッシュ２２６は、図１を参照しつつ記載されるように、データ・キャッシュ・アレイ１４１およびキャッシュ・ディレクトリ１４２を備える。図２では、Ｌ１キャッシュ２２６はセット・ディレクトリ２０３および有効化ディレクトリ２０５を更に備える。Ｌ２キャッシュ２３０はキャッシュ・ディレクトリ２４２およびキャッシュ・アレイ（図示せず）を備える。

セット・ディレクトリ２０３は、実効アドレス２０１のライン・インデックス・フィールド２１０のライン・インデックス・ビットを使用して論理的にインデックス付けされ、かつ実効アドレス２０１のタグ・フィールド２１２の第１の群のビット２１２ａを使用して論理的にタグ付けされる。有効化ディレクトリ２０５は、実効アドレス２０１のライン・インデックス・フィールド２１０のライン・インデックス・ビットおよびセット・ビットを使用して論理的にインデックス付けされる。有効化ディレクトリ２０５は、実効アドレス２０１のタグ・フィールド２１２の第２の群のビット２１２ｂを使用して論理的にタグ付けされる。第１および第２の群のビット２１２ａおよび２１２ｂは例証目的で非重複に図示される。しかしながら、第１の群および第２のビットは重複してもよい。例えば、第２の群のビットは、緩和された、例えばセット・ディレクトリおよび有効化ディレクトリが常に厳密に同期している必要がないことを許容する、セット・ディレクトリ更新規則を有することを可能にすることができるビット０：４９から成ってもよい。

セット・ディレクトリ２０３の各エントリは少なくとも第１の群のビット２１２ａおよび有効ビットを備える。例えばプロセッサ・コアがスレッド（例えばスレッドｔｈ１およびｔｈ２）をサポートする場合、エントリは各スレッドと関連する有効ビットを備えてもよい（例えば、エントリは次の通りであってもよい：ＬＡ．３７：４９，ｔｈ０ ｖｌｄ，ｔｈ１ ｖｌｄ）。有効化ディレクトリ２０５の各エントリは少なくとも第２の群のビットを備える。一例では、有効化ディレクトリ２０５のエントリは有効ビット、排他性ビットおよびキーを更に備える。有効ビットは、エントリが有効であると示す。排他性ビットは、キャッシュ・ラインが排他的に所有されていると示す。それが排他性ビットと呼ばれるのは、１つのコアがラインを排他的に有する場合、他のいかなるコアも関連ラインのコピーを有することができないからである。キャッシュ・ラインは、データが変更されると排他的に要求される。そして多くのコアがラインをリード・オンリ状態で有することができる。キーは保護のための記憶キーであり、そして任意の他の種々の情報の集合を含んでもよい。一例では、有効化ディレクトリ２０５のエントリはＡＳＣＥ要素およびＲＥＡＬ要素を更に備えており、ＡＳＣＥはアドレス空間制御要素（動的アドレス変換テーブルへのポインタ）を指し、そしてＲＥＡＬ要素は、エントリが実のエントリであることを示す。

Ｌ１およびＬ２キャッシュ・アレイ１４１はメモリ１１６からのデータ・コピーを保持し、そしてＬ１およびＬ２ディレクトリ１４２および２４２における各エントリは第２の群のビット２１２ｂ、アドレス空間識別子等を保持する。Ｌ１ディレクトリ１４２は例えば以下のフィールドを含む：有効ビット、論理アドレス、例えば４５：４９、およびＬ２セットＩＤ。有効ビットは、Ｌ１ディレクトリ・エントリが有効であるまたは有効でないと示す。論理アドレス４５：４９は、Ｌ２ディレクトリのアクセスを許容するＬ１論理アドレス５０：５５の拡張である。Ｌ２セットＩＤは、どのＬ２ディレクトリ・セットがＬ１キャッシュ・エントリを含むかを特定する。例えば、Ｌ１ディレクトリ１４２のエントリは次の通りであってもよい：ｓｅｔ０－Ｌ２ＣＣ（４５：４９），ｔｈ０ ｌｏｇｄｉｒ ｖｌｄ，ｔｈ１ ｌｏｇｄｉｒ ｖｌｄ，ｐｔｒｄｉｒ ｖｌｄ、ここでＬ２ＣＣ（４５：４９）は実効アドレス（論理アドレスとも称される）のビット４５：４９である。データのためのＬ２がサイズ４Ｍである一方で、命令のためのＬ２はサイズ２Ｍであるので、ビット４５はデータ・キャッシュのためだけに記憶される。「ｌｏｇｄｉｒ ｖｌｄ」は、Ｌ１キャッシュに記憶されている変換が有効であることを示す。「ｐｔｒｄｉｒ ｖｌｄ」は、Ｌ１キャッシュにおけるデータが有効であることを示す有効ビットである。ビット「４５：４９」ビットは例えばキャッシュ・サイズ（例えば行数）から導出されてもよい。例えば、Ｌ１キャッシュがセットごとに６４行を有する場合、ライン・インデックスは５０：５５であり、そしてＬ２がセットごとに１０２４行を有する場合、インデックス付けはより広くなり、インデックス４５：５５に帰着してもよい。しかしながら、Ｌ１ディレクトリが既に５０：５５でインデックス付けされているので、Ｌ２座標を指すことは、Ｌ１ディレクトリのエントリにＬＡ．４６：４９だけおよびＬ２セットＩＤを維持することによって行われてもよい。

図２の説明を簡易化するために、Ｌ１キャッシュの簡易例が考えられてもよい。この例では、Ｌ１キャッシュは６４行で８セット（すなわちｍ＝８）を有し、そしてキャッシュ・ラインは６４ビット（０：６３）を有する論理アドレス（略してＬＡ（０：６３））を使用してアドレスされる。したがって、この例のライン・サイズは２５６バイトである。この例では、セット・ディレクトリ２０３はタグ（第１の群のビット）としてＬＡ（３７：４９）を使用してもよい。有効化ディレクトリ２０５のタグは、ＬＡ（０：４９）またはＬＡ（０：３６）に加えて、異なるアドレス空間の間を区別するために必要とされる追加情報であってもよい。

有効化ディレクトリが行ごとに１つのディレクトリ・エントリを保持する１つの物理アレイ構造から構築されるので、有効化ディレクトリ２０５は「スタック」論理ディレクトリと称されてもよい。上記例に従って、有効化ディレクトリは、各々６４行を有する８つのアレイ構造の代わりに、８×６４行＝５１２行から成る。そのような構造の利点は、アレイ行が限定数のビットだけを有することができる（物理的理由で）ことであってもよい。より多くの行を追加することは、行の幅を延長することまたはより多くのアレイ構造を追加することに対して、比較的低オーバーヘッドで済む。「スタック」手法は、それが使用する領域および電力が少なくなるので、有利であり得る。Ｌ１キャッシュ・ディレクトリ１４２は、しかしながら、各々６４行を有する８つのアレイ構造を有する。

図２は、Ｌ１キャッシュ・ディレクトリ１４２およびＬ２キャッシュ・ディレクトリ２４２の構造の詳細を更に例示する。Ｌ１キャッシュ・ディレクトリ１４２は、複数のＬ１セット、例えばｍ個のＬ１セットおよびそれぞれのコンパレータＬ１ＣＰ１－Ｌ１ＣＰｍを持つセット・アソシアティブ・ディレクトリ構造から成る。Ｌ２キャッシュ・ディレクトリ２４２は、複数のＬ２セット、例えばｎ個のＬ２セットおよびそれぞれのコンパレータＬ２ＣＰ１－Ｌ２ＣＰｎを持つセット・アソシアティブ・ディレクトリ構造から成る。Ｌ２キャッシュ・ディレクトリ２４２は、インデックスとして実効アドレス２０１の一部を、およびタグとして絶対アドレスを使用している。

例えば、Ｌ２ディレクトリのエントリは以下を備えてもよい：「ｓｅｔ０－ＡＡ．１７：５１」、ここでｓｅｔ０はエントリを備えるセットのセット・インデックスであり、ＡＡはＬ２ディレクトリにインデックス付けするために使用される実効アドレスと関連する絶対アドレスである。他の例では、Ｌ２ディレクトリのエントリは２つの追加要素「キー（０：３），ＦＰ」を更に備えてもよく、ここで「キー」は、コンピュータ・システム１００の動作のアーキテクチャ原理（例えばｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ））に記載される規則に従って合致する必要がある４ビット・タグであり、そしてＦＰ（取出し保護）はキー比較を可能にする。

キャッシュ構造２００は、ＴＬＢ１４３を更に備える。

キャッシュ・ルックアップでは、セット・ディレクトリ２０３はインデックスＬＡ（５０：５５）および第１の群のビットＬＡ（３７：４９）を入力として受け、そしてセット・ディレクトリ２０３は、要求されたキャッシュ・ラインを保持する、Ｓｅｔ（０：７）と称されるセットＩＤを有するセットを生成または予測する。例えば、セット・ディレクトリ２０３は、セットＩＤを見つけるために検索されてもよい。インデックスＬＡ（５０：５５）に加えてセットＩＤ（Ｓｅｔ（０：７））を使用して、有効化ディレクトリ２０５は、タグ比較２２０を使用してキャッシュ・ヒットを確認するためにルックアップされて、有効化ディレクトリ２０５における対応するディレクトリ・エントリを特定することに帰着してもよい。例えば、そのために、セット・ディレクトリ２０３によって決定されたセットＩＤは８つの６４行セクションのうちの１つを選択するために使用され、そしてＬＡ（５０：５５）はセクション内の行を選択するために使用される。

セット・ディレクトリ２０３を検索することと並列に、Ｌ１キャッシュ・ディレクトリ１４２は、このディレクトリ・エントリに対する有効ビットを取り出すためにルックアップされる。複数のエントリがすぐに無効化されなければならない可能性があるので、有効部分はＬ１キャッシュ・ディレクトリ１４２の一部である。タグ比較２２０がヒット２４４となり、かつ有効ビットが設定されていれば、有効比較２４０がキャッシュ・ヒットと判明されたことを示す。そうでなければ、キャッシュ・ミス２４５と判明されてもよい。データ・アレイ１４１は、セット・ディレクトリ２０３からセット識別子を受けてもよく、そして実効アドレス２０１のライン・インデックス２１０およびバイト・オフセット２１３ならびにセット識別子を使用して要求されたキャッシュ・ラインのデータを提供してもよい。キャッシュ・ミスの場合、提供されるデータがキャッシュ・ミスに対応することを示すために警告が提供されてもよい。

キャッシュ・ミス２４５と判明された場合にまたはセット・ディレクトリ２０３における検索が失敗した（キャッシュ・ミスに帰着した）場合にだけ、図２の下部におけるデータ構造が関与されることになる。すなわち、ＴＬＢ１４３は実効アドレス２０１を使用して、およびヒット比較２５１を使用して（論理アドレス２０１の一部およびアドレス空間識別子などの変換関連情報を含む）ルックアップされ、要求に対する絶対アドレスが判定される。ヒット比較２５１はＴＬＢ自体の比較論理によって行われてもよい。ＴＬＢ１４３を検索することと並列に、Ｌ２キャッシュ・ディレクトリ２４２は、例えば実効アドレス２０１のビット４６：５５を使用してルックアップされる。そして、ヒット比較２６１が、ＴＬＢによって出力された絶対アドレスを論理アドレス２０１を使用して特定されたＬ２キャッシュ・ディレクトリの絶対アドレスと比較することによって、Ｌ２キャッシュ・ディレクトリ２４２においてヒットを求めて検索する。ヒット比較２６１の結果は、どのＬ２セットがヒットとなったか（図面はＬ２キャッシュにおける８セット（すなわちｎ＝８）を前提とする）の指標である。このヒット情報は次いで、Ｌ２キャッシュでヒットしたラインがＬ１キャッシュにも既に記憶されているかどうかを確かめるためにＬ１ ｄｉｒ比較２７０で使用される。そのために、Ｌ１ ｄｉｒ比較２７０は、Ｌ２キャッシュへの受け入れた入力論理ポインタ（ｏｕｔ１からｏｕｔｍと称される）も使用する。各論理ポインタ（例えばｏｕｔ１）は、それぞれのＬ１セットと関連付けられ、かつインデックスＬＡ（５０：５５）に対応するＬ１ディレクトリのエントリのＬ２インデックスおよびＬ２セットＩＤおよび有効ビットを備える。

図３は、図２のキャッシュ・メモリを動作させるための方法のフローチャートである。所与のキャッシュ・ラインにアクセスする、例えば実効または論理アドレスを介するアクセス要求を受けた上で、セット・ディレクトリ２０３（ｓｅｔｐと称される）およびＬ１キャッシュ・ディレクトリ１４２（ｐｔｒｄｉｒと称される）がステップ３１０でアクセスされる。このアクセスは例えば並列であってもよい。セット・ディレクトリ２０３およびＬ１キャッシュ・ディレクトリ１４２へのアクセスは、実効アドレスのライン・インデックス・ビット（例えばＬＡ（５０：５５））を使用して行われる。セット・ディレクトリ２０３へのアクセスは、キャッシュ・ラインが存在するセットを示すセット識別子に帰着してもしなくてもよい。Ｌ１キャッシュ・ディレクトリ１４２へのアクセスは、Ｌ１キャッシュ・ディレクトリが入力として実効アドレスのライン・インデックス・ビットだけを使用するので、それぞれのＬ１セットの複数のエントリに帰着してもしなくてもよい。

セット・ディレクトリ２０３を検索することから生じるキャッシュ・ミスの場合（照会２２０）、ステップ３８０～３８７が行われてもよい。キャッシュ・ヒットの場合（照会２２０）、ステップ３３０～３７０が行われてもよく、そしてセット・ディレクトリ２０３は、要求されたキャッシュ・ラインが存在するセットを示すセット識別子を提供してもよい。

ステップ３３０では、有効化ディレクトリ２０５（ｌｏｇｄｉｒと称される）は、セット・ディレクトリ２０３から受けられるセット識別子および実効アドレスのライン・インデックス・ビット（例えばＬＡ（５０：５５））を使用して検索されてもよい。

アドレスされたキャッシュ・ラインと関連する有効ビットがステップ３４０で判定されてもよい。これは、複数のエントリのうちセット識別子を使用するエントリを選択し、そして選択されたエントリの有効ビット値を読むことによって判定されてもよい。

有効化ディレクトリ２０５が検索３３０の結果としてキャッシュ・ミスを提供する、または有効ビットが無効状態を示している値を有する場合（３５０）、ステップ３１０の検索によってヒットされたセット・ディレクトリのエントリは無効化されてもよい３７０。そうでなければ、例えばヒット信号を提供することによって、ステップ３６０でキャッシュ・ヒットが解決されてもよい。

ステップ３８０で、要求の論理アドレスを使用して、ＴＬＢルックアップが行われる。このルックアップの結果は一致する絶対アドレスである。次に、ステップ３８１で、Ｌ２キャッシュ・ディレクトリ２４２がルックアップされ、そしてＴＬＢから供給される絶対アドレスに対して比較される。Ｌ２ミスの場合、ステップ３８２が３８３に分岐してＬ１ミスかつＬ２ミスと解決する。Ｌ１ミスかつＬ２ミスと解決した後に、次の要求に応じてセット・ディレクトリ２０３にキャッシュ・ラインが見つけられることができるように、全てのデータ構造が更新される。

ステップ３８２がＬ２ヒットとなると、ステップ３８４が、ステップ３１０における検索によって特定されたＬ１キャッシュ・ディレクトリ内容をＬ２ディレクトリ内容に対して比較して、キャッシュ・ラインが実際にＬ１にあるかどうかを確かめる。比較結果がＬ１ヒットを示す場合、ステップ３８５がステップ３８６に分岐することを決定する。これは、要求がセット・ディレクトリ２０３でヒットしなかったが、キャッシュ・ラインは実際にＬ１キャッシュにある場合である。これは例えば、セット・ディレクトリが正しくないための場合である可能性がある、または現在の要求がこれまでにＬ１に記憶されたシノニムとは異なるシノニムに対するため（現在の要求にとっては「セット・ディレクトリは正しくなかった」と言うことと同じである）であり得る。いずれでも、ステップ３８６はセット・ディレクトリ２０３および有効化ディレクトリ２０５を更新して現在の要求に一致させる。実際のデータ転送が起こる必要はない。ステップ３８５がＬ１ヒットとならない場合、これは、キャッシュ・ラインがＬ１キャッシュにない－どのシノニムにしても－が、Ｌ２キャッシュにはあることを示す。したがって、ステップ３８７で、Ｌ１ミスと解決され、これには、要求が繰り返された際にＬ１ヒットと判明されるように、Ｌ２からＬ１にデータを転送し、そしてセット・ディレクトリおよび有効化ディレクトリを更新することを含む。

ステップ３７０、３８３、３８６および３８７の各々に続いては、明らかにＬ１ヒットに帰着するであろう要求を繰り返すためのステップ３９９である。

図４は、本開示に従って図２のキャッシュ・メモリにおいてシノニムを解決するための方法のフローチャートである。

ステップ４０１で、第２の実効アドレス（シノニムＢと称される）が受けられる。第２の実効アドレスは、シノニムＡと称される前に処理された実効アドレスのシノニムである。言い換えれば、シノニムＢがキャッシュ・ラインに対して使用される一方で、他のシノニムＡが既にＬ１キャッシュにある。

例証目的で、図４は、アドレス・シノニムＡおよびＢを１６進法で図示する。簡潔にするために、２０ビット・アドレス（５つの１６進数字）が示される。この例では、キャッシュ・ラインへのバイト・インデックスまたはオフセットは示されない。ビットは左から右に番号付けされる（ビット０が最上位ビットである）ので、各アドレスはビット０：１９を有する。シノニムＡ＝１２３４５およびシノニムＢ＝６７８９５。この例では、セット・ディレクトリ２０３は、ビット１６：１９（すなわちアドレスの最後の１６進数字）を使用してインデックス付けされてもよく、かつビット８：１５を使用してタグ付けされてもよい。図４に図示されるように、３つのユースケース例Ａ）～Ｃ）４３０が描かれる。

ユースケースＡ）では、シノニムＡおよびＢはセット・ディレクトリ２０３に同じインデックス（ｓｅｔｐインデックス＝５）を有し、かつ異なるタグを有する。シノニムＡおよびＢは同じ絶対アドレスにマッピングする。

ユースケースＢでは、シノニムＡおよびＢはセット・ディレクトリ２０３に同じインデックス（ｓｅｔｐインデックス＝５）および同じタグを有する。シノニムＡおよびＢは同じ絶対アドレスにマッピングする。

ユースケースＣでは、ラインＡおよびＢは、セット・ディレクトリ２０３に同じインデックス（ｓｅｔｐインデックス＝５）および同じタグを有する。しかしながら、それらは異なる絶対アドレスにマッピングする。

ステップ４０３で、セット・ディレクトリ２０３は、要求されたシノニムＢに対してキャッシュ・ヒットを特定するために検索される。これは、セット・ディレクトリ２０３が最終的に実際にヒットとならなかったセットを提供したので、「セット・ディレクトリ誤り」ケースと考えられる。

しかしながら、ステップ４０５で、有効化ディレクトリ２０５におけるシノニムＢの検索がキャッシュ・ミスに帰着する。ルックアップがシノニムＡに対してであれば、有効化ディレクトリ２０５における検索はヒットとなるであろう（そしてステップ３６０が実行されてもよい）。しかしながら、アクセスがシノニムＢに対してであったので、有効化ディレクトリ２０５から読まれるアドレスは要求されたアドレスに一致しないことになる。

ステップ４０７で、セット・ディレクトリ２０３におけるシノニムＢに対応するエントリが無効化される。そして、シノニムＢを使用する繰返しアクセスがステップ４０９でトリガされる。

ステップ４０３～４２０はユースケースＢ）およびＣ）に対して実行される。

ステップ４１１で、セット・ディレクトリ２０３は、要求されたシノニムＢに対してキャッシュ・ミスを特定するために検索される。

ステップ４１１のキャッシュ・ミスを特定した上で、ステップ４１３が実行される。ステップ４１３（ステップ３８４を行う）で、シノニムＢと関連するＬ１キャッシュ・ディレクトリ内容がシノニムＢと関連するＬ２ディレクトリ内容に対して比較されて、キャッシュ・ラインが実際にＬ１にあることを見つける。

ステップ４１３でキャッシュ・ヒットを特定したまたは見つけた上で、セット・ディレクトリ２０３および有効化ディレクトリ２０５はステップ４１５で更新されてもよい。更新は、例えばシノニムＡ情報をシノニムＢで上書きすることによって行われてもよい。

ステップ４１５の更新を行った上で、シノニムＢを使用するアクセスの繰返しがステップ４１７でトリガされてもよい。繰返しアクセスは、ステップ４１８でのセット・ディレクトリ・ヒットに続いてステップ４１９で有効化ディレクトリ・ヒットに帰着し、ステップ４２０でキャッシュ・アクセスが解決されることに帰着する。

ステップ４１１～４２０はユースケースＡ）に対して実行されてもよい。例えば、ユースケースＡ）のシノニムＢが受けられると、ステップ４１１でミスと判明されてもよい。言い換えれば、ユースケースＡ）の受け入れたシノニムＢに対してステップ４１１～４２０だけが実行されてもよい。

図５は、タグ・フィールド２１２およびキャッシュ・ライン・インデックス・フィールド２１０を備える実効アドレス、例えば２０１を介するキャッシュ・メモリ、例えば２００へのアクセスを制御するための方法のフローチャートである。

ステップ５０１で、タグ・フィールド２１２の第１の群のビット２１２ａおよび第２の群のビット２１２ｂが判定されてもよい。

ステップ５０３で、実効アドレスのライン・インデックス・ビットおよび第１の群のビット２１２ａがセット・ディレクトリ２０３において検索されてもよく、それによって実効アドレス２０１のキャッシュ・ラインを含むセットを示すためにセット識別子が生成される。

ステップ５０５で、ステップ５０３で提供されたセット識別子を有するセットにおけるキャッシュ・ラインの存在を検証するために、セット識別子ならびに実効アドレス２０１のライン・インデックス・ビット２１０および第２の群のビット２１２ｂが有効化ディレクトリ２０５において検索されてもよい。このステップ５０５は、キャッシュ・ラインが有効化ディレクトリ２０５に存在するかどうかを示すことによって、セットにおけるキャッシュ・ラインの存在または非存在を示しても、または確認してもよい。

ステップ５０５の第２の検索に基づいてセットにおけるキャッシュ・ラインの存在を判定することに応答して、ステップ５０７でヒット信号が発生されてもよい。ヒット信号は、データ・アレイ１４１からキャッシュ・ラインのデータを提供するために使用されてもよい。

一例では、ステップ５０３もしくはステップ５０５またはその両方は、検索されたアドレスがそれぞれセット・ディレクトリ２０３および有効化ディレクトリに見つけられない点でキャッシュ・ミスに帰着してもよい。この場合、キャッシュ・ミスは、ステップ３８０から３９９に関しては記載されるように、ＴＬＢ１４３および２次キャッシュ・ディレクトリ２４２にアクセスすることによって確認されてもよい。

ＴＬＢ無効化

一実施形態によれば、本方法は、有効化ディレクトリの有効化ディレクトリ・エントリを無効化するための要求を受けることに応答して、１次キャッシュ・ディレクトリにおける対応する１次キャッシュ・ディレクトリ・エントリの有効ビットをそれに応じて設定することを更に含む。

一実施形態によれば、本方法は、１次キャッシュ・ディレクトリと関連付けて第１の補助データ構造を設けることであって、第１の補助データ構造の各エントリがマルチプロセッサ・システムのＴＬＢパージ要求に示される情報を反映する実効アドレスのビットを備える、ことと、受けた要求に対応する第１の補助データ構造におけるエントリを特定することであって、特定されるエントリが１次キャッシュ・ディレクトリ・エントリを示す、こととを更に含む。

例えば、ゲスト・オペレーティング・システムのためのアドレス空間が対応するハイパーバイザによって削除される場合、キャッシュ・ラインはまだＬ１キャッシュにある。しかし、それらに対する有効な変換はもはやない。これは、Ｌ１キャッシュにおけるデータが、削除された変換を使用する要求によってアクセス可能であるべきでないことを意味する。これらのエントリをアクセス不可能にするために、それらは、Ｌ１キャッシュ・ディレクトリが論理的にタグ付けされているため、Ｌ１キャッシュにおいて無効化されるべきである。無効化の前に、影響されるエントリが見つけられるべきである。例えば、特定のエントリがゲスト・オペレーティング・システムに属することを示すために、有効化ディレクトリにおけるエントリ情報の一部としてビットが使用されてもよい。ＴＬＢ無効化がそのゲスト・オペレーティング・システムに関連した全ての変換情報を削除する場合、ゲスト・ビットが設定された有効化ディレクトリ２０５における全てのディレクトリ・エントリが無効化されるべきである。

有効化ディレクトリ２０５では、エントリが無効化（またはパージ）されるべきか否かを見抜くために注目されることができるエントリは常に１つだけである。この問題を軽減するために、Ｌ１ディレクトリ１４２は、有効化ディレクトリ２０５における各エントリに対する変換関連情報を保持する副構造「ｐｔｒｄｉｒｅｘｔ」（すなわち第１の補助データ構造）が拡張される。Ｌ１ディレクトリと同様に、第１の補助データ構造において全てのセットが並列にアクセスされることができる。例えば、第１の補助データ構造のエントリが「ｓｅｔ０－ｔｈ ＡＳＣＥ（４４：４９），ＰＧＳＺ（０：１），ＳＸ（３７：４３）」を備えてもよく、ここでＰＧＳＺはページ・サイズを指し（例えば、動的アドレス変換結果は４ｋ、１Ｍまたは２Ｇページ・サイズであることができる）、ＳＸ（３７：４３）は実効アドレスのビット３７：４３を指し、そしてＡＳＣＥ（４４：４９）はそれぞれのスレッドｔｈによってアドレス空間識別子として使用される実効アドレスのビット４４：４９である。

例えば、アドレス空間制御要素（ＡＳＣＥ）によって示される仮想記憶と関連する一連の仮想アドレスがアドレス空間と呼ばれてもよい。アドレス空間はユーザ間の隔離の程度を提供するために使用されてもよい。第１の補助データ構造の構造は、ＡＳＣＥビットを使用してより効率的な方式で所与のアドレス空間と関連するエントリをパージすることを可能にすることができる。

この副構造により、或る変換だけに影響するべきであるＴＬＢ無効化が、有効化ディレクトリにおける全てのエントリを１つずつスクラブすることによってよりもより著しく速く行われることができる。

副構造ｐｔｒｄｉｒｅｘｔは有効化ディレクトリ２０５の任意の更新と共に書き込まれる。ｐｔｒｄｉｒｅｘｔのサイズとＴＬＢ無効化の精度との間でトレード・オフがなされることができる。ゲスト対ハイパーバイザ所有のケースに対処するため、区別を行うために単一のビットが必要とされる。ＴＬＢパージが、ｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ）におけるＡＳＣＥ、すなわち５１ビット値に加えて或る制御情報などのアドレス空間識別子に基づいて行われる場合、どのエントリがパージされなければならず、どれがその必要がないかをフィルタリングするために数ビットだけまたは数ビットのハッシュを記憶するのに十分であろう。ｐｔｒｄｉｒｅｘｔの実装例は、ＡＳＣＥビットの一部、ゲスト・レベル識別子ビット、ページ・サイズ指標（複数のページ・サイズをサポートするＴＬＢアーキテクチャのため）、セグメント・インデックスまたはセグメント・インデックスの一部（より高レベルが「セグメント・テーブル」と呼ばれ、そしてセグメント・テーブルに基づく無効化が可能である、マルチ・レベル・ページ・テーブルをサポートするＴＬＢアーキテクチャのため）を保持し得る。例えば、有効ビットがＬ１ディレクトリ・エントリの一部である場合、エントリの実際の無効化は、所与のＬ１ディレクトリにおけるセットの全てのエントリに並列に行われることもできる。

以下の図を説明する目的で、以下の技術用語が使用される。

実際のメモリ・アクセスは「実」アドレスを使用して行われる。これは、例えば、主メモリ位置をアドレスする６４ビット値であり得る。しかしながら、アドレス指定方式に対する任意の値または手法が使用されることができる。

プロセッサ・コア上で実行する命令は「論理」アドレスを使用する。動的アドレス変換（ＤＡＴ）が使用されない場合、プロセッサは「実」アドレス指定モードで動作しており、プログラムによって使用される論理アドレスは実アドレスとしても使用される。

ＤＡＴが使用される場合、プロセッサは「仮想」アドレス指定モードで動作している。仮想アドレス指定情報は、命令によって指定される論理アドレスに加えて、例えば、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ（ＩＢＭ（Ｒ））によって提供されるｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ）に見られるアドレス空間制御要素（ＡＳＣＥ）など、特定のアドレス空間を識別する追加情報を含む。しかしながら、他の仮想対実変換手法が使用されることができる。この仮想アドレス指定モードは、異なる論理対実アドレス・マッピングを使用してあらゆるプログラムにそれ自体のアドレス空間を与えるために使用されることができる。

仮想キャッシュ

仮想キャッシュのディレクトリ１４２（「ｌｏｇｄｉｒ」）タグ６００（本明細書で「ｌｏｇｄｉｒ」と称される）は、従前の変換ルックアサイド・バッファ（ＴＬＢ）１４３が典型的に保持するであろう変換に関連した全ての情報を保持する。図６は、実施形態に係る例証的なｌｏｇｄｉｒタグ６００の略図である。タグ６００は、ビット０：４９として例示される論理アドレス・ビット６０１、アドレス空間識別子（ここでは「ＡＳＣＥ」として例示される）６０２、「実」ビット指標Ｒ６０３（アドレスを仮想対実として標記する）、仮想対実アドレス・インジケータ６０４、および潜在的に他の内容６０５を含む。

図１～５に関して上記した手法において、および参照により内容全体が本明細書に組み込まれる、２０１７年６月１６日出願の「Cache structure using a logical directory」という名称の同時係属米国特許出願第１５／６２５，２２３号において、複数の変換が同時にディレクトリに共存することができない。

実および仮想変換

オペレーティング・システムは、しばしば実アドレスを直接使用する。すなわち、プロセッサによって保持される実際の情報、命令またはデータを見つけるために、アドレス変換は必要とされない。仮想キャッシュのｌｏｇｄｉｒにおいて、これは、アドレス変換が必要とされないことを示すように「Ｒ」ビット６０３を設定することによって、エントリが「実」アドレスとして標記されることを意味する。

しかしながら、関連オペレーティング・システムの上で実行する各プログラムが通常、例えばＤＡＴを使用して、それ自身のアドレス空間で、仮想メモリを提供することを維持する。そのようにアクセスされるキャッシュ・ラインは、「Ｒ」ビット６０３がクリアされることによって識別されることができる。すなわち、「Ｒ」ビット６０３は、アドレスが実アドレスでないこと、およびそのキャッシュ・ラインと関連する実際の情報、データまたは命令を見つけるためにアドレス変換が必要とされることを示すように設定される。

オペレーティング・システムとユーザ・コード（例えばオペレーション・システムの上で動作するプログラム）との間で共有される或るアドレス範囲に関して、オペレーティング・システムは、論理アドレスを同じ実アドレスへ変換するユーザ・コードに対する仮想アドレス・マッピングを作成してもよい。例えば、オペレーティング・システムとユーザ・コードとの間で情報を交換するためにアドレス０ｘ１０００が使用されると仮定する。オペレーティング・システムは、実アドレスを使用して全てのメモリにアクセスする。ユーザ・コードは、仮想アドレスを使用して全てのメモリにアクセスする。ユーザ・コードに対して、論理アドレス０ｘ１０００は実アドレス０ｘ１０００にマッピングされる。

図７は、仮想対実ビット６０４がｌｏｇｄｉｒタグ６００に存在しない（例えば含まれない）が、仮想および実アドレスが同じアドレスである場合の、共有メモリ位置を通じたデータ転送のためのプロセスを例示する。この手法では、共有メモリ位置を通じたデータ転送のために以下の一連のイベントが発生する。

ユーザ・コードが仮想アドレスにコードを記憶するとプロセスが開始する。これはステップ７１０に例示される。例えば、ユーザ・コードは、仮想アドレスに機能コードを記憶することができる。この説明の目的で、仮想アドレスは０ｘ１０００である。しかしながら、いかなるアドレスも使用されることができる。これを実装するために、ｌｏｇｄｉｒ６００は、０ｘ１０００の論理アドレス（例えば仮想アドレスを示す）に、ＤＡＴがオンでＲビットがオフの、この特定のキャッシュ・ラインに対する仮想ディレクトリ・エントリを作成する。キャッシュ・ラインに対するこのエントリの値は、アドレス空間がキャッシュ・ラインにコードを記憶したユーザ・コードのためであることを示す。

次に、ユーザ・コードは下位のオペレーティング・システムを呼び出す。これはステップ７２０に例示される。ユーザ・コードは、オペレーティング・システムと関連するプロトコルを使用して下位のオペレーティング・システムを呼び出すが、その詳細は本明細書で更に詳細には論じられない。一部の実施形態において、下位のオペレーティング・システムは、仮想マシンが下位のオペレーティング・システムの上で実行することを可能にするハイパーバイザを通じてユーザ・コードによってアクセスされる。

ユーザ・コードからの呼出しに応答して、オペレーティング・システムは実アドレスからコードを読み取る。これはステップ７３０に例示される。このステップで、オペレーティング・システムは０ｘ１０００の実アドレス（仮想アドレスと同じ）からコードを読み取る。これはｌｏｇｄｉｒミスに帰着する。実アドレスとして、アクセスが、実ビット６０３がオン（例えばＲ＝１）にされたｌｏｇｄｉｒにおけるエントリを探しているからである。そのため、Ｒ＝０シノニムは、図１～５に関して上記したトランスロード・プロセスを使用してクリーンアップされるべきである。このクリーンアップはステップ７４０に例示される。クリーンアップの結果として、キャッシュ・ラインに対するｌｏｇｄｉｒエントリは、キャッシュ・ラインに対する現実のエントリに更新されることになる。これは、論理アドレス０ｘ１０００に対して、ＤＡＴがオフに設定されてＲビット６０３がオンに設定されることに帰着する。

ユーザ・コードが仮想アドレス０ｘ１０００に他の機能コードを記憶する各以降の反復に応じて、実ビットがオンに設定されるためｌｏｇｄｉｒミスが発生することになる。これは、シノニムが再びクリーンアップされなければならず、そしてｌｏｇｄｉｒがそれに応じて更新されることに帰着する。これは、共有アドレスの使用ごとに繰り返し得る。論理アドレス対実マッピングが異なる異なるｌｏｇｄｉｒエントリを有することが可能であるので、本明細書で論じられるＲビット６０３の比較が必要であることが留意されるべきである。すなわち、仮想アドレスおよび実アドレスは同じ論理アドレスでない。

図７に関して以上例示したこれらの仮想／実アドレス・シノニム・クリーンアップ動作に対処するために、論理ディレクトリに新たなビットが追加されることができる。これが仮想対実インジケータ６０４である。このビット６０４は「Ｖ＝Ｒ」（「仮想アドレスが実アドレスに等しい」）と呼ばれてもよい。Ｖ＝Ｒビット６０４は、ＤＡＴオン・アドレス変換の結果である実アドレスが、それの起点であった論理アドレスと同じである（すなわち論理アドレスが実アドレスである）場合に設定される。図７に関して上記した例では、Ｖ＝Ｒビットは、ユーザ・コードのための仮想アドレス０ｘ１０００を実アドレス０ｘ１０００へ変換した結果として設定されるものである。

仮想アドレスが実アドレスと同じであるＶ＝Ｒビットの値を設定するために、アドレス変換のプロセスが拡張される。図８は、拡張プロセスを例示する。ステップ８１０は、以前の従来のアドレス変換プロセスを例示する。いかなるアドレス変換プロセスもこのステップで実装されることができる。変換プロセスに入力するために、論理アドレスの要求８０１または実対ＤＡＴオン要求８０２が受けられる。要求に応答して、プロセスは、実アドレスの要求があるかどうかを判定する。これはステップ８２０に例示される。要求が実アドレスに対する場合、結果的な実アドレスおよび入力論理アドレスが同一であれば、新たなコンパレータがＶ＝Ｒ指標を出力する。これはステップ８３０に例示される。

追加的に、実施形態において、ＴＬＢ１４３は、ＴＬＢヒットがＶ＝Ｒ情報も返すことができるように、あらゆるＴＬＢエントリにおいてＶ＝Ｒビットによって拡張される。代替的に、Ｖ＝Ｒ指標は、あらゆるＴＬＢルックアップ後に再計算されることもできる。この手法では、ＴＬＢルックアップ・パスにＶ＝Ｒ比較プロセスを有することを犠牲にして、ＴＬＢにおける追加ビットを節約することが可能である。

仮想としても実アドレスとしてもエントリへのアクセスを許容するために、ディレクトリ・ヒット比較論理も強化される。実施形態において、Ｖ＝Ｒアドレスに対するルックアップが仮想キャッシュ・ルックアップの一部として行われる場合、通常のディレクトリ比較論理が適用される。しかしながら、ルックアップが実アドレスに対して行われ、かつディレクトリ・エントリにおけるＶ＝Ｒビットが設定されている場合、ＡＳＣＥなどの全てのＤＡＴオン情報が無視される。このようにして、ディレクトリ・エントリは仮想としても実エントリとしても使用されることができる。図９は、本開示のＶ＝Ｒ論理を含むディレクトリ比較の実装例を例示する。図９の下の３方向ＡＮＤ９１０がキャッシュ・ラインに対する「ヒット」情報を計算する。ＡＮＤ９１０の左入力９２０はｌｏｇｄｉｒにおけるＤＡＴオン状態に関連する情報の比較を扱う。ＤＡＴがオンであり、かつ入力がＶ＝Ｒケースのための入力を受ける場合、およびそれが実アドレス要求であり、かつＶ＝Ｒビットが設定されている場合、ＤＡＴオン情報は無視される。ＡＮＤ９１０の中入力９３０は論理アドレス比較の結果を受ける。ＡＮＤ９１０の右入力９４０は要求されたアドレス・モードで比較を制限する。要求が仮想であり、かつディレクトリ・エントリも仮想であるか、両方とも実であるか、強化Ｖ＝Ｒにより、要求が実であり、かつエントリがＶ＝Ｒである。図８および９に関して論じたこの強化は、ステップ７５０として図７に例示されるプロセスへ挿入される。このステップでは、ステップ７４０でのシノニムのクリーンアップに続いて、Ｖ＝Ｒビットは、Ｖ＝Ｒがオンまたは真であると示す値に設定される。一部の実施形態において、ユーザ・コードまたはオペレーティング・システムが仮想アドレスであると考えるものにアクセスする際にそれらによって使用される論理に応じて、ＤＡＴはこの時点でオンにリセットされることができる。

ここで図１０～１７に転じて、異なるスレッドにわたって変換を管理するためのプロセスが論じられる。

異なるスレッドにおける変換

仮想キャッシュのディレクトリ１４２（「ｌｏｇｄｉｒ」）タグは、ＴＬＢ１４３などのＴＬＢが通常保持する変換に関連した全ての情報を保持する。図１０は、例示的な実施形態に係るタグ例１０００を例示する。タグ１０００は、論理アドレス・ビット０：４９（１００１）、アドレス空間識別子１００２（「ＡＳＣＥ」）、「実」ビット指標１００３（通常オペレーティング・システム使用のために、アドレスを、アドレス変換を必要としないとして標記する）、およびキャッシュ・ヒット対ミスを判定するために必要とされるまたは有用な他の内容、集合的に１００４を含む。一部の実施形態において、タグは、図６～９に関して上記したＶ＝Ｒビットを含むことができる。

Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ（ＩＢＭ（Ｒ））によって提供されるｚ／Ａｒｃｈｉｔｅｃｔｕｒｅ（Ｒ）などの、一部のマイクロプロセッサ・アーキテクチャでは、アドレス変換有効性はスレッドごとに規定される。したがって、１つのスレッドによって作成されるｌｏｇｄｉｒにおけるキャッシュ・ディレクトリ・エントリは必ずしも他のスレッドに対して有効であるわけではない。ディレクトリ・ルックアップ・プロセスは、実アドレス変換を行うことを含まない。したがって、ディレクトリ・ルックアップ・プロセスは、アドレス変換が現在有効であるかどうかを確かめることを含まない。代わりに、アドレス変換は、エントリの作成か更新かに応じて行われる（そしてその有効性が確かめられる）。

図１～５に関して上記した手法において、および参照により内容全体が再び本明細書に組み込まれる、２０１７年６月１６日出願の「Cache structure using a logical directory」という名称の同時係属米国特許出願第１５／６２５，２２３号において、キャッシュ・ディレクトリ・エントリを作成したスレッドを識別する追加フィールドでディレクトリ・タグを拡張することによって、複数のスレッドがサポートされることができる。上記した規則に従って、スレッド所有は、キャッシュ・ディレクトリ・エントリの現在の所有者と異なるスレッドが共有キャッシュ・ラインにアクセスしたいときに（「トランスロード」を実行することによって）スレッド間で切り替わる。共有キャッシュ・ラインの所有の変化が頻繁に起こる場合、キャッシュ・ラインの所有のこの絶えず続く切替えは性能問題を生じさせる。

本開示は、キャッシュ・ディレクトリにスレッドごと有効ビット１００５を追加することによってこの性能問題に対処する。上記した設計では、これは、ｐｔｒｄｉｒにおいてスレッドごと有効ビットを追加することによって達成される。ＴＬＢ無効化は、ＴＬＢ無効化を行うスレッドに対するエントリだけに注目し、そしてそのスレッドの有効ビットだけをオフにすることによって作用することもできる。このようにして、キャッシュ・ラインは、１つのスレッドがそのラインにその変換を「失った」後でさえ、他のスレッドにとってアクセス可能なままである。

本実施形態において、スレッドがキャッシュ・ラインに対していかなる有効な変換も有することなくＬ１キャッシュにキャッシュ・ラインを所有することが可能である。変換にアクセスするスレッドの両方とも独立して無効化されるそれらの変換を有し得たため、有効な変換のないキャッシュ・ラインに対するエントリに帰着する。一部の実施形態において他のマイクロアーキテクチャ理由で、「まだＬ１にキャッシュ・ライン」ビットが所望され、キャッシュ・ディレクトリに、完全なキャッシュ・ライン無効化に応じてのみオフにされることができる他の有効ビット（「ライン有効」ビット）１００６が追加されることができる。完全なキャッシュ・ライン無効化は、例えば、他のプロセッサ・コアからの相互無効として起こることができる。この手法を利用する実施形態において、キャッシュ・ラインは、ルックアップ・スレッドの有効ビットが設定されていれば、所与のルックアップに対して有効とみなされ、キャッシュ・ラインへの変換を有効と識別し、そして「ライン有効」ビットが設定される。

キャッシュ・ディレクトリへのスレッドごと有効ビットの追加により、２つのスレッドが同じ変換を使用して同じキャッシュ・ラインを共有するようにするプロセスが図１１および図１２に関して下記される。下記されるプロセスは、２つの異なるスレッドが同じキャッシュ・ラインにアクセスする、およびプロセスの初めにキャッシュ・ラインがＬ１キャッシュにないが、既にＬ２キャッシュにあったと仮定する。図１３は、図１１および図１２の詳細な決定プロセスを説明および例示する。

図１１は、実施形態に係る、特定のキャッシュ・ラインにアクセスしようとする第１のスレッドのプロセスを例示する。第１のスレッドがＬ１キャッシュにｌｏｇｄｉｒミスがあると判定するとプロセスが開始する。これはステップ１１１０に例示される。スレッドがキャッシュ・ディレクトリにおいて特定のエントリを見つけようとするとｌｏｇｄｉｒミスが発生する。スレッドが特定のキャッシュ・ラインを求めてＬ１キャッシュを検索するが、Ｌ１キャッシュにキャッシュ・ラインを見つけられないとキャッシュ・ミスが発生する。

ｌｏｇｄｉｒミスに続いて、プロセスはｐｔｒｄｉｒ比較を行い続ける。これはステップ１１２０に例示される。このステップで、プロセスは、キャッシュ・ラインがＬ１キャッシュに全く見つけられないと判定する。ｐｔｒｄｉｒ比較は、ｐｔｒｄｉｒ対Ｌ２ディレクトリ／ＴＬＢルックアップのために使用される任意の公知のプロセスを通じて行われる。

次に、プロセスはＬ２ディレクトリ比較を行って、所望のキャッシュ・ラインを見つける。これはステップ１１３０に例示される。このステップで、プロセスは、キャッシュ・ラインがＬ２キャッシュに存在すると判定する。キャッシュ・ラインがＬ２キャッシュに見つけられなければ、プロセスは、それが所望のキャッシュ・ラインを見つける時まで、Ｌ３キャッシュまたはプロセッサ構造に存在する任意のより低レベルのキャッシュに対してこのステップを繰り返すであろう。キャッシュ・ラインがＬ２キャッシュに見つけられるので、プロセスは、Ｌ１キャッシュへリロードするためにこのキャッシュ・ラインを特定する。

一旦キャッシュ・ラインがＬ２またはより低いキャッシュに特定されると、プロセスは続いて、Ｌ１キャッシュにキャッシュ・ラインのための新しいディレクトリ・エントリを作成する。これはステップ１１４０に例示される。このステップで、プロセスは、キャッシュ・ディレクトリにおける既に従来のエントリを上書きするように選ぶことができる。一部の実施形態において、上書きするエントリは最も古いエントリである。一部の実施形態において、上書きされるエントリは、一定期間の間アクセスされなかったエントリである。他の実施形態において、エントリは、最少のアクセスを有するエントリである。しかしながら、ディレクトリ・エントリを上書きするように選択するためのいかなる手法も使用されることができる。一旦ディレクトリ・エントリが上書きのために選択されると、プロセスは続いて、キャッシュ・ラインに対するＬ１キャッシュ・データ構造を更新し、そして第１のスレッドがキャッシュ・ラインの所有者であることを示すためにスレッドに対して有効性ビットを設定する。同時に、第２の所有スレッドに対する有効性ビットはキャッシュ・ラインに関して無効化される。その他のスレッドが上書きされているディレクトリ・エントリに設定された有効ビットを有し得たので、その他のスレッドに対する有効性ビットの無効化が行われる。新たな変換（キャッシュ・ライン・エントリ）は必ずしもその他の（第２の）スレッドに対しても有効であるわけではない。

キャッシュ・ラインがＬ１キャッシュへロードされた後、第１のスレッドは必要に応じてこのエントリでヒットすることができる。これはステップ１１５０に例示される。すなわち、第１のスレッドは、Ｌ１キャッシュにおける関連ｌｏｇｄｉｒにアクセスして見つけることができる。

図１２は、実施形態に係る、図１１のプロセスに続いて、第２のスレッドがキャッシュ・エントリをルックアップするプロセスを例示するプロセス図である。図１２のプロセスは、図１１に関して上記したプロセスと同様であり、そして図１２の説明の目的で、同様のステップの詳細はここで更に詳細には論じられない。第２のスレッドがｌｏｇｄｉｒルックアップを行って、Ｌ１キャッシュでｌｏｇｄｉｒに対するヒットを見つけるとプロセスが開始する。これはステップ１２１０に例示される。

キャッシュ・ラインがＬ１キャッシュにあったという判定に続いて、プロセスは、キャッシュ・ラインが第２のスレッドに対して有効でないと判定する。これはステップ１２２０に例示される。エントリに対する変換の有効性が第１のスレッドに対してだけ決定されたので、第２のスレッドに対する有効性は有効でない。キャッシュ・ラインが第２のスレッドに対して有効であるかどうかを判定するためのプロセスは、キャッシュ・ラインが有効であると判定する任意の公知の方法を使用して実行されることができる。

キャッシュ・ラインが第２のスレッドに対して有効でないので、ｐｔｒｄｉｒおよびＬ２ディレクトリ／ＴＬＢルックアップが行われる。これはステップ１２３０に例示される。このステップで、第２のスレッドは、キャッシュ・ラインがＬ１キャッシュに存在すると判定する。（図１１のプロセスによってＬ１に移動された）。キャッシュ・ライン・ヒットの位置は、ステップ１２１０でｌｏｇｄｉｒヒットが見つけられたのと同じキャッシュ・ラインであると判定される。同じキャッシュ・ラインでのこのヒットは、変換が既にＬ１キャッシュにあり、そして変換が第１のスレッドに対する変換に一致することを確認する。

第２のスレッドに対するＬ１キャッシュの有効ビットがオンにされる。これはステップ１２４０に例示される。更に、第１のスレッド対する有効ビットもオンのままにされる。これは、第１のスレッドも第２のスレッドも並列にキャッシュ・ラインを使用することができることに帰着する。

図１３は、実施形態に係る決定木として表現される図１１および図１２の複合プロセスを例示する略図である。

ステップ１３１０でｌｏｇｄｉｒヒットとならず、そしてステップ１３２０でｐｔｒｄｉｒヒットとならない場合、キャッシュ・ラインは現在Ｌ１キャッシュにない。そこで、ステップ１３３０は、Ｌ２ディレクトリ・ルックアップ結果に基づいて、Ｌ２キャッシュからキャッシュ・ラインをリロードする（パス（Ａ））かＬ３キャッシュ・パス（Ｂ）か（図１４に関して更に詳細に論じられる）を判定する。

しかしながら、ステップ１３２０でのｐｔｒｄｉｒ比較がヒットとなれば、ラインは既にＬ１キャッシュにある。例では、Ｌ１ディレクトリは、現在の要求スレッド情報に一致するように更新される（ステップ１３２１）。現在のスレッドに対する有効ビットが設定され、全ての他に対する有効ビットは無効化される（ステップ１３２２）。再び、このステップが行われるのは、現在の要求の情報へのディレクトリ更新の結果として、ディレクトリにおける変換情報がもはや他のスレッドに対して正しくない場合があるからである。

ｌｏｇｄｉｒ比較がヒットを示すが、ステップ１３４０で要求スレッドに対する有効ビットが設定されていない場合、決定木は次にステップ１３５０に移動してｐｔｒｄｉｒ比較結果を確かめる。ヒットとならなければ、キャッシュ・ラインはＬ１になく、ステップ１３６０に続き、ステップ１３３０と同様に、キャッシュ・ラインをＬ１へ持ってくる。ｐｔｒｄｉｒ比較１３５０がヒットを示す場合、ステップ１３７０がｐｔｒｄｉｒヒットｓｅｔｉｄをステップ１３１０からのｌｏｇｄｉｒヒットｓｅｔｉｄに対して比較する。それらが一致すれば、現在の要求のキャッシュ・ラインは既にＬ１にあり、ｌｏｇｄｉｒタグ情報は正しい。第２のスレッドに対して有効ビットが見つからないだけである。したがって、現在の要求スレッドに対する有効ビットがオンにされ、そして他の有効ビットが既にアクティブであれば、キャッシュ・ラインは今や複数のスレッド間で共有される。ｓｅｔｉｄ比較１３７０が異なるｓｅｔｉｄでＬ１ヒットがあったことを示す場合、そのエントリは、現在の要求スレッド情報に更新され、現在の要求スレッドの有効ビットが設定され、そして全ての他のスレッドの有効ビットは再びクリアされる。これはステップ１３７１に例示される

図１４は、実施形態に係るＬ１キャッシュ・ミスの解決を例示するフローチャートである。プロセス１４００への入力は図１３のパスＡかパスＢかから達成される。パスＡはＬ１キャッシュ・ミスおよびＬ２キャッシュ・ヒットを表す一方で、パスＢはＬ１キャッシュ・ミスおよびＬ２キャッシュ・ミスを表す。パスＡからプロセス１４００に入ると、ステップ１４０１でＬ２キャッシュからのキャッシュ・ラインがフェッチされる。パスＢからプロセス１４００に入ると、ステップ１４０２でＬ３キャッシュからキャッシュ・ラインがフェッチされる。一旦ラインがフェッチされると、プロセスはステップ１４０３で、各繰返しルックアップでＬ３キャッシュ・ラインでヒットするように全てのＬ２データ構造を書き込む。ステップ１４０１か１４０３か（入力パスに応じて）に続いてプロセスは合併する。ステップ１４１０で、各後続のルックアップに応じてこのキャッシュ・ラインでヒットするようにＬ１データ構造が書き込まれる。ステップ１４２０で、キャッシュ・ライン・エントリにおける有効ビットは、特定のキャッシュ・ラインを要求した対応するスレッドに対して設定される。ルックアップはステップ１４３０で繰り返されることができる。

異なるスレッドにおける異なる変換

同時マルチスレッディング・コア（ＳＭＴ）では、各スレッドは潜在的に、スレッド間で共有される絶対アドレスに対するそれ自身の変換を必要とする。上記したスレッド共有手法では、これは、スレッド１がＬ１ディレクトリ・ルックアップ中に正しい情報（例えば論理アドレス、ＡＳＣＥ、…）を見つけられないことに帰着する。したがって、たとえｐｔｒｄｉｒ対Ｌ２ディレクトリ／ＴＬＢ比較プロセスが、正しいキャッシュ・ラインが既にＬ１キャッシュにあることを示しても、このスレッドに対する有効ビットを設定することは誤りであろう。異なる変換（すなわち第１のスレッドからのもの）は、結局そのラインのために使用されるであろう。この手法では、あたかもキャッシュ・ラインにスレッドごとディレクトリ有効ビットが存在しない、すなわちトランスロードを行うかのように、状況は扱われることができる。従来の（第１の）スレッドのｌｏｇｄｉｒエントリが第２のスレッドの情報で上書きされ、そしてその他の第１のスレッドの有効ビットはオフにされる。

図１５は、実施形態に係る異なる変換を使用するｌｏｇｄｉｒにおけるキャッシュ・ラインを共有するための解決策を例示する。２つのスレッドを前提として、完全なディレクトリ・タグ情報が複製される。タグ比較結果は、要求が第１のスレッド・ディレクトリに対する第１のスレッドに対してであること、および要求が第２のスレッド・ディレクトリに対する第２のスレッドに対してであることで、更に制限される。ヒット信号の１つがアクティブであればディレクトリ・ヒットが発生する。

一部の実施形態において、実際に両方のディレクトリに給電する必要はない。要求のスレッドＩＤはプロセスの初期に知られているであろう。対応するスレッドＩＤの知識は、その「他の」スレッドに対するある構造をオフにするために使用されることができる。そこで、ｌｏｇｄｉｒ領域が複製される、一部の実施形態において、特に、領域制約されるより電力制約されるデュアル・スレッドコアに対して。この手法は、キャッシュ・ラインを共有したいスレッドのＬ１キャッシュ・ルックアップにおいてタグ比較結果を考慮する必要を排除する。スレッドはその独自のディレクトリ・エントリを有しており、その他のスレッドの従来のディレクトリ・エントリに一致する必要はない。

図１６は、ディレクトリ内容の一部がスレッド間で共有される手法を例示する。この手法は、部分的に異なるタグ情報だけを許容する。したがって、スレッドごとディレクトリに関与するオーバーヘッドの一部が節約されることができる。要点は、スレッド間の実アドレス共有シナリオに応じて、タグ情報の全てが異なるわけではないということである。例えば、異なるスレッドで実行する異なるプログラム間で共有されるメモリは、同じ論理アドレスにマッピングされて、異なるアドレス空間識別子を使用することができるだけである。その場合、ＡＳＣＥだけはスレッドごとに異ならなければならない。これは、共有ライブラリを使用するときにしばしば発生する。

一部の実施形態において、タグは次いで、スレッドごとに（第１のスレッド／第２のスレッド専用ｌｏｇｄｉｒに）複製されるＡＳＣＥ部分およびスレッド共有ｌｏｇｄｉｒに記憶される残りのビットへ分割される。再び、スレッド専用構造は現在のスレッドの要求に対してだけ給電されさえすればよい。最終的なヒットは、スレッドごとおよびスレッド共有タグ・ヒットの結果として計算される。

図１７は、実施形態に係るｌｏｇｄｉｒにおけるスレッドごと情報の部分共有を処理するように変更された図１３に係る決定木の略図である。図１７におけるパスＡおよびＢへの参照は図１４のパスを指す。ディレクトリにおける別々のスレッド専用およびスレッド共有部分により、キャッシュ・ルックアップで行われることになる決定は、図１３から僅かに変更される。ステップ１３１０は、ｌｏｇｄｉｒのスレッド共有部分に基づいて決定するように変更される。これはステップ１７１０に例示される。ステップ１３４０は、要求スレッドに対する有効ビットおよびｌｏｇｄｉｒ専用ヒットの結果に基づいて決定するように変更される。これはステップ１７４０に例示される。ステップ１３７１は、有効ビットを更新するだけでなく、ｌｏｇｄｉｒのスレッド専用部分を書き込むようにも変更される。これはステップ１７７１に例示される。しかし、ステップ１７７０におけるｐｔｒｄｉｒ比較が「間違った」ｓｅｔｉｄ（例えばスレッド共有ヒットしたものでない）でヒットとなれば、Ｌ１ディレクトリ内容は更新されるべきである。これは、ｌｏｇｄｉｒのスレッド共有およびスレッド専用部分を共に含む。これは、他のスレッドに対する有効変換を知ることなくスレッド共有部分を更新することが、その他のスレッドの有効ビットがオフにされるべきであることを必要とするためである。

本発明の態様が、本発明の実施形態に係る方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート例もしくはブロック図またはその両方を参照しつつ本明細書に記載される。フローチャート例もしくはブロック図またはその両方の各ブロック、およびフローチャート例もしくはブロック図またはその両方におけるブロックの組合せがコンピュータ可読プログラム命令によって実装されることができることが理解されるであろう。

本発明は、システム、方法もしくはコンピュータ・プログラム製品またはその組合せであってもよい。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実施させるためにコンピュータ可読プログラム命令を有する１つまたは複数のコンピュータ可読記憶媒体を含んでもよい。

コンピュータ可読記憶媒体は、命令実行デバイスによる使用のための命令を保持および記憶することができる有形デバイスであることができる。コンピュータ可読記憶媒体は、例えば、電子記憶デバイス、磁気記憶デバイス、光記憶デバイス、電磁記憶デバイス、半導体記憶デバイス、または上記の任意の適切な組合せであってもよいが、これらに限定されない。コンピュータ可読記憶媒体のより具体的な例の非網羅的な列挙には以下を含む：ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリ・メモリ（ＲＯＭ）、消去可能プログラマブル・リード・オンリ・メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク・リード・オンリ・メモリ（ＣＤ－ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー・ディスク、パンチ・カードまたは命令が記録された溝に隆起された構造などの機械的に符合化されたデバイス、および上記の任意の適切な組合せ。コンピュータ可読記憶媒体は、本明細書で使用される場合、電波もしくは他の自由に伝搬する電磁波、導波管もしくは他の伝送媒体を通って伝搬する電磁波（例えば、光ファイバ・ケーブルを通る光パルス）、または電線を通って伝送される電気信号など、それ自体が一過性信号であると解釈されないものとする。

本明細書に記載されるコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体からそれぞれのコンピューティング／処理デバイスに、あるいはネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークもしくは無線ネットワークまたはその組合せを介して外部コンピュータまたは外部記憶デバイスにダウンロードされることができる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータもしくはエッジ・サーバまたはその組合せを備えてもよい。各コンピューティング／処理デバイスにおけるネットワーク・アダプタ・カードまたはネットワーク・インタフェースが、ネットワークからコンピュータ可読プログラム命令を受信し、そしてコンピュータ可読プログラム命令をそれぞれのコンピューティング／処理デバイス内のコンピュータ可読記憶媒体への記憶のために転送する。

本発明の動作を実施するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ、またはＳｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋等などのオブジェクト指向プログラミング言語および「Ｃ」プログラミング言語もしくは同様のプログラミング言語などの従来の手続き型プログラミング言語を含む、１つもしくは複数のプログラミング言語の任意の組合せで書かれたソース・コードかオブジェクト・コードかであってもよい。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンド・アロン・ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でかつ部分的にリモート・コンピュータ上で、または完全にリモート・コンピュータもしくはサーバ上で実行されてもよい。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含む、任意の種類のネットワークを通じてユーザのコンピュータに接続されてもよく、または外部コンピュータに接続がなされてもよい（例えば、インターネット・サービス・プロバイダを使用してインターネットを通じて）。一部の実施形態において、例えば、プログラマブル論理回路網、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）またはプログラマブル論理アレイ（ＰＬＡ）を含む電子回路網は、本発明の態様を行うために、コンピュータ可読プログラム命令の状態情報を活用して電子回路網を特性化することによってコンピュータ可読プログラム命令を実行してもよい。

本発明の態様が、本発明の実施形態に係る方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート例もしくはブロック図またはその両方を参照しつつ本明細書に記載される。フローチャート例もしくはブロック図またはその両方の各ブロック、およびフローチャート例もしくはブロック図またはその両方におけるブロックの組合せがコンピュータ可読プログラム命令によって実装されることができることが理解されるであろう。

これらのコンピュータ可読プログラム命令は、命令が、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサを介して実行し、フローチャートもしくはブロック図のまたはその両方の１つまたは複数のブロックに指定される機能／行為を実装するための手段を生じさせるように、汎用コンピュータ、専用コンピュータまたは他のプログラマブル・データ処理装置のプロセッサに提供されてマシンを生成してもよい。これらのコンピュータ可読プログラム命令はまた、命令が記憶されたコンピュータ可読記憶媒体が、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックに指定される機能／行為の態様を実装する命令を含む製品を構成するように、コンピュータ、プログラマブル・データ処理装置もしくは他のデバイスまたはその組合せに特定の方式で機能するよう指令することができるコンピュータ可読記憶媒体に記憶されてもよい。

コンピュータ可読プログラム命令はまた、コンピュータ、他のプログラマブル装置または他のデバイス上で実行される命令が、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックに指定される機能／行為を実装するように、コンピュータ、他のプログラマブル・データ処理装置または他のデバイスへロードされて、コンピュータ、他のプログラマブル装置または他のデバイス上で一連の動作ステップが行われてコンピュータ実装プロセスを生成させてもよい。

図におけるフローチャートおよびブロック図は、本発明の様々な実施形態に係るシステム、方法およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能性および動作を例示する。この点で、フローチャートまたはブロック図における各ブロックは、モジュール、セグメントまたは命令の一部分を表現してもよく、それは指定された論理機能を実装するための１つまたは複数の実行可能命令を備える。一部の代替実装では、ブロックに示される機能は、図に示される順序と異なって起こってもよい。例えば、連続して図示される２つのブロックが、実際には、実質的に並行して実行されてもよく、またはブロックは、時に逆順に実行されてもよく、関与する機能性次第である。ブロック図もしくはフローチャート例またはその両方の各ブロック、およびブロック図もしくはフローチャート例またはその両方におけるブロックの組合せが、指定された機能もしくは行為を行うまたは専用ハードウェアおよびコンピュータ命令の組合せを実施する専用ハードウェア・ベースのシステムによって実装されることができることも留意されるであろう。

Claims (19)

1. 仮想メモリ・サポートを有するプロセッサにおける、仮想キャッシュ・ディレクトリであって、前記仮想キャッシュ・ディレクトリが複数のディレクトリ・エントリを有し、各エントリがキャッシュ・ラインと関連し、前記キャッシュ・ラインが、
   前記複数のディレクトリ・エントリの各々と関連するタグを備え、前記タグが、
   論理アドレスと、
   アドレス空間識別子と、
   実アドレス・ビット・インジケータと、
   仮想アドレス対実アドレス・インジケータと、
   を備える、
   仮想キャッシュ・ディレクトリ。
2. 前記仮想アドレス対実アドレス・インジケータが単一ビットである、請求項１に記載の仮想キャッシュ・ディレクトリ。
3. 前記仮想アドレス対実アドレス・インジケータが、前記論理アドレスが実アドレスと同じであるときに設定される、請求項１に記載の仮想キャッシュ・ディレクトリ。
4. 前記仮想アドレス対実アドレス・インジケータが設定されると、動的アドレス変換が行われない、請求項１に記載の仮想キャッシュ・ディレクトリ。
5. 前記仮想アドレス対実アドレス・インジケータが、変換ルックアサイド・バッファにおけるルックアップごとに再計算される、請求項１に記載の仮想キャッシュ・ディレクトリ。
6. 仮想メモリ・サポートを伴うプロセッサのためのプロセッサ・キャッシュを動作させる方法であって、論理インデックス付きかつ論理タグ付きキャッシュ・ディレクトリが使用され、かつ前記ディレクトリにおけるエントリが、対応する論理メモリ・アドレスに加えて絶対メモリ・アドレスを、および仮想対実フラグを含み、前記方法が、
   前記キャッシュ・ディレクトリにおける第１のエントリにおける論理メモリ・アドレスにコードを記憶することと、
   ユーザ・コードによって、下位のオペレーティング・システムを呼び出すことと、
   前記オペレーティング・システムによって、前記絶対メモリ・アドレスから前記コードを読み取ることと、
   前記第１のエントリにトランスロードを実行することと、
   前記絶対メモリ・アドレスが前記論理メモリ・アドレスに等しいかどうかを判定することと、
   前記絶対メモリ・アドレスが前記論理メモリ・アドレスに等しいと判定することに応答して、前記仮想対実フラグをオンに設定することと、
   を含む、方法。
7. 前記ユーザ・コードがハイパーバイザを通じて前記下位のオペレーティング・システムにアクセスする、請求項６に記載の方法。
8. コードを記憶することが、動的アドレス変換フラグがオンに設定されかつ実ビット・フラグがオフに設定されたエントリのために、前記キャッシュにディレクトリ・エントリを作成する、請求項６に記載の方法。
9. トランスロードを実行することが、前記動的アドレス変換フラグをオフにかつ前記実ビット・フラグをオンにする、請求項８に記載の方法。
10. 前記仮想対実フラグがオンに設定されると、前記動的アドレス変換フラグの状態が無視される、請求項８に記載の方法。
11. 変換ルックアサイド・バッファが、前記仮想対実フラグに関連した情報を返すように構成される、請求項６に記載の方法。
12. 各変換ルックアサイド・バッファ・ルックアップごとに、前記仮想対実フラグが再計算される、請求項１１に記載の方法。
13. 仮想メモリ・サポートを伴うプロセッサを動作させるためのコンピュータ・プログラムであって、論理インデックス付きかつ論理タグ付きキャッシュ・ディレクトリが使用され、かつ前記ディレクトリにおけるエントリが、対応する論理メモリ・アドレスに加えて絶対メモリ・アドレスを、および仮想対実フラグを含み、コンピュータに、
    前記キャッシュ・ディレクトリにおける第１のエントリにおける論理メモリ・アドレスにコードを記憶することと、
    ユーザ・コードによって、下位のオペレーティング・システムを呼び出すことと、
    前記オペレーティング・システムによって、前記絶対メモリ・アドレスから前記コードを読み取ることと、
    前記第１のエントリにトランスロードを実行することと、
    前記絶対メモリ・アドレスが前記論理メモリ・アドレスに等しいかどうかを判定することと、
    前記絶対メモリ・アドレスが前記論理メモリ・アドレスに等しいと判定することに応答して、前記仮想対実フラグをオンに設定することと、
    を含む方法を実行させる、
    コンピュータ・プログラム。
14. 前記ユーザ・コードがハイパーバイザを通じて前記下位のオペレーティング・システムにアクセスする、請求項１３に記載のコンピュータ・プログラム。
15. コードを記憶することが、動的アドレス変換フラグがオンに設定されかつ実ビット・フラグがオフに設定されたエントリのために、前記キャッシュにディレクトリ・エントリを作成する、請求項１３に記載のコンピュータ・プログラム。
16. トランスロードを実行することが、前記動的アドレス変換フラグをオフにかつ前記実ビット・フラグをオンにする、請求項１５に記載のコンピュータ・プログラム。
17. 前記仮想対実フラグがオンに設定されると、前記動的アドレス変換フラグの状態が無視される、請求項１５に記載のコンピュータ・プログラム。
18. 変換ルックアサイド・バッファが、前記仮想対実フラグに関連した情報を返すように構成される、請求項１３に記載のコンピュータ・プログラム。
19. 各変換ルックアサイド・バッファ・ルックアップごとに、前記仮想対実フラグが再計算される、請求項１８に記載のコンピュータ・プログラム。

Images