(57)【要約】本発明によるデータ処理システムは、プロセッサ（Ｐ）とメモリ階層を備えている。その最上位レベルはプロセッサに接続するキャッシュである。メモリ階層は、ライト・アロケート方式に従って動作するキャッシュ・コントローラ（ＣＣ１）を備える上位キャッシュ（Ｃ１）と、上位キャッシュ（Ｃ１）に接続し、キャッシュ・コントローラ（ＣＣ２）を備える下位キャッシュ（Ｃ２）とを備えている。上位キャッシュのサイズは下位キャッシュのサイズを下回る。両方のキャッシュ（Ｃ１、Ｃ２）は、キャッシュ内のデータ（Ｄ１、Ｄ２）が有効かどうかを示す補助情報（Ｖ１、Ｖ２）を管理する。下位キャッシュ（Ｃ２）のライン・サイズは、上位キャッシュ（Ｃ１）のライン・サイズの整数倍である。上位キャッシュ（Ｃ１）の補助情報（Ｖ１）は、下位キャッシュ（Ｃ２）の補助情報（Ｖ２）より細かい粒度でデータ・エレメントＤ１に関連する。上位キャッシュ（Ｃ１）は下位キャッシュ（Ｃ２）のどのデータがより細かい粒度で上書きされるかを示すライトマスク（ＷＭ）をデータ・ライン（ＤＬ）と共に下位キャッシュ（Ｃ２）に送信するように調整されている。上位キャッシュ（Ｃ１）が提供するライン（ＤＬ）が完全に有効であることをライトマスク（ＷＭ）が示す場合に、１つ下のレベル（Ｍ）からのラインのフェッチが抑制される。この場合は下位キャッシュのコントローラ（ＣＣ２）が下位キャッシュ（Ｃ２）に前記キャッシュ・ラインをフェッチせずに割り当てる。
2006501563.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサおよびメモリ階層を備えるデータ処理システムであって、前記階層の最上位レベルはプロセッサに接続するキャッシュであり、
前記メモリ階層の上位キャッシュはライト・アロケート方式に従って動作するキャッシュ・コントローラを備えており、
下位キャッシュは前記上位キャッシュに接続し、キャッシュ・コントローラを備えており、
前記上位キャッシュのサイズは前記下位キャッシュのサイズを下回り、
両方のキャッシュはキャッシュ内のデータが有効かどうかを示す補助情報を管理しており、
前記下位キャッシュのライン・サイズは前記上位キャッシュのライン・サイズの整数倍であり、前記上位キャッシュの補助情報は前記下位キャッシュの補助情報より細かい粒度（granularity)でデータ・エレメントに関連付けられており、
前記上位キャッシュは前記下位キャッシュのどのデータが細かい粒度で上書きされるかを示すライトマスクをデータ・ラインと共に前記下位キャッシュに送信するように調整されており、前記下位キャッシュのキャッシュ・コントローラはラインがまだキャッシングされず、前記上位キャッシュが提供する前記ラインのデータが一部のみ有効であることを前記ライトマスクが示す場合にメモリ階層で１つ下のレベルから前記ラインをフェッチするように調整されており、前記上位キャッシュが提供する前記ラインが前記下位キャッシュ内の粗い粒度の補助情報に従って有効であることを前記ライトマスクが示す場合に前記１つ下のレベルからのラインのフェッチが抑制されており、この場合に前記下位キャッシュのコントローラが前記下位キャッシュに前記キャッシュ・ラインをフェッチせずに割り当てることを特徴とするシステム。
【請求項２】
１つまたは複数のプロセッサをさらに備えており、メモリ階層は前記下位キャッシュより下位のメモリを備えており、前記他のプロセッサとこれを共有する請求項１に記載のデータ処理システム。
【請求項３】
下位キャッシュと上位キャッシュのキャッシュ・ラインは同数のデータ・エレメントを備える請求項１または２に記載のデータ処理システム。
【請求項４】
上位キャッシュは書き込み専用のキャッシュであることを特徴とする前記請求項のいずれか一項に記載のデータ処理システム。
【請求項５】
上位キャッシュは唯一のキャッシュ・ラインを備える前記請求項のいずれか一項に記載のデータ処理システム。
【請求項６】
プロセッサおよびメモリ階層を備えるデータ処理システムを動作させる方法であって、前記階層の最上位レベルはプロセッサに接続するキャッシュであり、
前記メモリ階層の上位キャッシュはライト・アロケート方式に従って動作するキャッシュ・コントローラを備えており
下位キャッシュは前記上位キャッシュに接続し、キャッシュ・コントローラを備えており、
前記上位キャッシュのサイズは前記下位キャッシュのサイズを下回り、
両方のキャッシュはそれぞれに格納されたデータが有効かどうかを示す補助情報を管理し、
前記下位キャッシュのライン・サイズは前記上位キャッシュのライン・サイズの整数倍であり、前記上位キャッシュの補助情報は前記下位キャッシュの補助情報より細かい粒度でデータ・エレメントに関連付けられており、
前記方法に従って、
前記上位キャッシュは前記下位キャッシュのどのデータが細かい粒度で上書きされるかを示すライトマスクをデータ・ラインと共に前記下位キャッシュに送信するように調整されており、
前記下位キャッシュのキャッシュ・コントローラはラインがまだキャッシングされず、前記上位キャッシュが提供する前記ラインのデータが一部のみ有効であることを前記ライトマスクが示す場合に、メモリ階層で１つ下のレベルから前記ラインをフェッチするように調整されており、
前記上位キャッシュが提供する前記ラインが前記下位キャッシュ内の粗い粒度の補助情報に従って有効であることを前記ライトマスクが示す場合に、前記１つ下のレベルからのラインのフェッチが抑制されており、この場合に前記下位キャッシュのコントローラが前記下位キャッシュに前記キャッシュ・ラインをフェッチせずに割り当てることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層状のメモリ構造を備えるデータ処理システムに関する。メモリの階層構造は、高速のプロセッサ・サイクル時間と低速のメモリ・アクセス時間との隔たりを埋める役割を果たす。一般に、このようなメモリ階層はプロセッサに接続する小容量であるが高速の１次キャッシュ（最上位）と、前記１次キャッシュに接続するやや低速ではあるが比較的容量の大きな２次キャッシュで構成される。１つ下の下位のレベルにメイン・メモリがあってもよいが、２次キャッシュとメモリの間にもう１つのさらに大規模なキャッシュが存在してもよい。メモリ階層の最下位には、たとえば磁気ディスクや光ディスクのような大容量記憶媒体がある。それ以外の場合、メイン・メモリにネットワークやモデム接続を介してデータを提供してもよい。本出願で考察する基本的な概念については、"Hennessy, John L., et al., Computer Architecture--A Quantitative Approach" (Morgan Kaufmann Publishers, Inc., San Mateo, Calif., 1990)を始めとする多くの資料に詳しく説明されている。Hennessyの文献、特に第８章では、本発明が取り組むキャッシュ・メモリの問題について詳細に説明している。
【背景技術】
【０００２】
多くのキャッシュ・コントローラには、「フェッチオンライト（fetch-on-write）」方式が採用されている。つまり、書き込みミス（write miss）が発生したときに、キャッシュ・ラインがメモリからフェッチされてキャッシュに挿入され、キャッシュ内でアドレスを指定したワード（addressed word）が更新される。このラインは、特定の期間だけキャッシュ内に存在し、同じ領域への後続の書き込みに備える。この方式は、多くの書き込みがキャッシュ内でヒットし、直接メモリ・トラフィックを生成しないので、メモリ・トラフィックの量を削減するという利点があることから一般的に選択されている。この方式では、アドレス・タグが有効か無効か、およびデータ・コンテンツがクリーンかダーティーか（書き込まれている）を示すために、キャッシュ・ラインあたり２つの管理ビットが必要である（データ・コンテンツとアドレス・タグの他に）。「ダーティー」なキャッシュ・ラインは、キャッシュが新しいワードの場所を再利用しようとする場合、または（例外的に）プロセッサで明示的な「フラッシュ」操作を実行する場合に、メモリにライト・バックされる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ストリーミング（マルチメディア）データを操作する場合、通常、入力ストリームと出力ストリームではタスクが区別される。出力ストリームは、プロセッサによってメモリベースのバッファに書き込まれる。こうしたストリーム（こうした書き込み）が行われると、「フェッチオンライト」ポリシーによってまずメモリ・ブロックをキャッシュにフェッチするための無駄なメモリ・トラフィックが生成される（電力消費と時間遅延が発生する）。さらに、書き込み操作が完了する前にデータをキャッシュに読み込むことの遅延（レーテンシ）により、効率が低下する。こうして読み込まれたデータは明らかに無駄であり、そのすべてが上書きされる。
【０００４】
書き込みミスの「フェッチオンライト」を回避する既知の技術に「ノー・ライト・アロケート（no-write-allocate）」方式がある。この方法では書き込まれたデータがキャッシュを迂回するにすぎない。この方式では、一般的に望まれるメモリ・トラフィックの削減は達成されない。
【課題を解決するための手段】
【０００５】
低使用頻度の技術によってライト・アロケート（write allocate）方式における「フェッチオンライト」が回避される。この技術では、キャッシュ管理により多くのビットを追加する。すなわち各キャッシュ・ラインのデータ・バイトごとに「有効」ビットが導入される。これで、キャッシュ・ラインごとに唯一の「ダーティー」ビットはこの「データ有効」ビット・セットに置き換えられる。こうした処理システム（冒頭の段落に従ったシステム）は、US5,307,477から理解される。書き込みミスが発生すると、新しいキャッシュ・ラインが「割り当て」られ（キャッシュ内に場所が割り当てられ、アドレス・タグと「アドレス有効（address-valid）」ビットが設定される」）、実際に書き込まれるバイトのみを挿入し、対応する「データ有効」ビットを設定することで書き込み操作が完了する。このキャッシュ・ラインをメモリにフラッシュする必要がある場合は、そのデータの一部のみが「有効」であり、これが通常はメモリ・システムの役割を果たし、メモリ書き込み操作に「バイト・ダーティー・マスク（byte dirty mask）」を指定できる。この方式では、キャッシュ管理が強化され（バイトあたり１有効ビット）、メモリ・インターフェイスが複雑になる（「ダーティー・マスク」を送信するためのワイヤリング（ｗｉｒｅｓ）の追加）が、全体的に「フェッチオンライト」が回避されるのは明らかである。
【０００６】
本発明の目的は、無駄な「フェッチオンライト」を回避することでメモリ・トラフィックを削減し、メモリ遅延ペナルティーを軽減することであり、補助データ全体の量はメモリ階層全体のサイズに比較して小規模に維持されている。本発明により、本データ処理システムは請求項１に記載の特徴的な機能によって特徴付けられる。
【０００７】
本発明によるデータ処理システムでは、上位キャッシュ（higher ranked cache）が下位キャッシュ（lower ranked cache）内のキャッシュ・ラインのサブセットを置き換えるか、キャッシュ・ライン全体を置き換えるかを下位キャッシュのキャッシュ・コントローラがライトマスクから認識するので、無駄なフェッチオンライトが回避される。キャッシュ・ラインのサブセットが置き換えられる場合に、下位キャッシュ内のラインがまだ使用できなければ、まずメモリ階層で１つ下のレベルからキャッシュ・ラインをフェッチする。しかし、上位キャッシュが下位キャッシュ内のキャッシュ・ライン全体を置き換える場合は、下位キャッシュのキャッシュ・コントローラはライトマスクからこれを認識し、不要なフェッチオンライトを回避する。こうしたケースでフェッチオンライトが回避されるので、データ処理システムの動作速度は全体として向上する。上位キャッシュは相対的に管理を強化された状態を維持するが、下位キャッシュ内の補助情報は上位キャッシュ内の補助情報より粗い粒度（at a courser granularity）でデータ・エレメントに関連し、上位キャッシュは下位キャッシュより小規模なので、全体的な管理のオーバーヘッドは比較的小規模である。
【０００８】
本発明は、請求項２に示すようにマルチプロセッサ・システムでは特に有利である。この方法では、２台のプロセッサが同時に共有メモリへのアクセスを要求する頻度が低下する。これにより、マルチプロセッサ・システムの動作速度が向上する。最適な結果を得るには、マルチプロセッサ・システムを構成するプロセッサのそれぞれが、請求項１で定義する独自のメモリ階層を備えているのが好ましい。
【０００９】
下位キャッシュと上位キャッシュのライン・サイズの比率は、１を超える整数倍（たとえば２倍）である。この場合は、ライトマスクでそのコンテンツ全体が置き換えるように指定された下位キャッシュのラインに上位キャッシュが最初のラインを書き込む場合に、通常は下位キャッシュが２等分のそれぞれについて「データ有効」ビットを備えており、下位キャッシュが新しい大きなキャッシュ・ラインを割り当て、書き込まれたデータを格納し、対応する「データ有効」ビットをのみを設定することができる。完全なライトマスクを使用して上位キャッシュから下位キャッシュの代わりの半分への第２の書き込みをすることによって、大きなキャッシュ・ラインを完全にすることができる。あるいは、ライトマスクでコンテンツを部分的に置き換えるように指定された第２の書き込みをする場合は、まず前記下位キャッシュ内のライン全体をフェッチする必要がある。ここで、フェッチされたデータには、上位キャッシュからの最初の書き込みの間にすでに書き込まれた場所にデータが格納されている。この場合は、前にキャッシュに書き込まれたデータ（「データ有効」ビットを使用して特定される）がメモリから読み出されるデータより優先されるような方法で、メモリから到着するデータがすでにキャッシュ内にあるデータとマージされる。続いて、下位キャッシュ内でメモリから到着するデータは、ライトマスクで指定するように、上位キャッシュから到着するデータによって部分的に上書きされる。請求項３に記載の好ましい実施形態では、すでに下位キャッシュ内にあるデータとのマージは不要であり、ライトマスクに従った上位キャッシュから到着するデータとのマージだけで十分である。
【００１０】
請求項４に記載の実施形態において、書き込みミスの結果としてのキャッシュ内のデータ割り当ては、別のリード・キャッシュにおける読み出しミスの結果として全体的にデータ割り当てとは別に発生する。こうしてリード・キャッシュの割り当て領域とライト・キャッシュの割り当て領域を分離することで、書き込みに関する割り当てによって重要な読み出しデータがキャッシュから押し出される可能性がなくなるので、特にストリーミング・データを処理する場合のシステム・パフォーマンスが向上する。リード・キャッシュとライト・キャッシュが分離している場合は、これらのキャッシュ間で一貫したメモリ・ビューを維持するために、追加の（既知の）技術が必要である。一般に、この技術によってライト・キャッシュ内で読み出し操作のアドレスをチェックし、一致する場合はライト・キャッシュから直接読み出すか、ライト・キャッシュ内のメモリへのフラッシュが行われる。
【００１１】
請求項５に記載の実施形態は、コスト対効果のきわめて高いソリューションである。シミュレーションにより、本発明による処理システムでは上位キャッシュのラインが唯一の場合にも、バックグラウンド・メモリの通信帯域幅が大幅に削減されることが示されている。
【００１２】
本発明のこうした態様あるいは他の態様について、添付の図面に関連して詳細に説明する。
【発明を実施するための最良の形態】
【００１３】
メモリ階層内の上位キャッシュＣ１はライト・アロケート方式に従って動作するキャッシュ・コントローラＣＣ１を備えており、下位キャッシュＣ２は上位キャッシュＣ１に結合され、キャッシュ・コントローラＣＣ２を備えている。図示された実施形態において、上位のキャッシュは最上位の（１次）キャッシュＣｌであり、下位のキャッシュは２次キャッシュＣ２である。ただし、本発明の目的では、上位キャッシュと下位キャッシュはメモリ階層内で互いに連続する２つのキャッシュ（たとえば２次キャッシュと３次キャッシュ）で十分である。通常、上位キャッシュは直接マップされるか、小規模なセットに関連して設定される。これで応答速度が向上する。下位キャッシュは、ヒット率を上げるために通常は比較的大規模なセットに関連して設定される。
【００１４】
上位キャッシュＣ１のサイズは下位キャッシュＣ２のサイズより小さい。いずれのキャッシュも、キャッシュ内にあるデータが有効かどうかを示す補助的な情報を管理する。
【００１５】
下位キャッシュは最終的にメイン・メモリＭに接続する。
【００１６】
本発明を説明するために、下位キャッシュＣ２と上位キャッシュＣ１を図２に詳細に示す。
【００１７】
本実施形態において、上位キャッシュＣｌは４つのラインを備えている。各ラインは、前記キャッシュ・ライン内のデータに対応するメモリ・アドレスを示すタグ情報ユニットを備えている。このデータには、ここでは４つのデータ・エレメントＤ１が含まれる。さらに、キャッシュ・ラインには補助情報Ｖ１が有効性ビット（validity bits）（データ・エレメントごとに１有効性ビット）が格納される。
【００１８】
一般に、Ｃ１はキャッシュ・ラインＬｌ内のバイトあたり１つの「有効」ビットＶ１（プロセッサの書き込み操作の粒度）を備えている。好ましい実施形態は、図２に示されており、Ｃ１キャッシュ・ラインの粒度でＣ２の「有効」ビットを備えるように選択できる。別の実施形態では、Ｃ２内に（４バイトまたは８バイト）ワードの粒度で「有効」ビットＶ２を備えている。
【００１９】
本発明のデータ処理システムは、下位キャッシュＣ２のライン・サイズが上位キャッシュＣ１のライン・サイズの整数倍であるという特徴を有する。図２に示す実施形態では、下位キャッシュＣ２のライン・サイズはＣ１の２倍である。つまり、Ｃ２内のラインはＣ１内のラインの２倍の数のデータ・エレメントで構成される。上位キャッシュＣ１の補助情報Ｖ１は、下位キャッシュＣ２の補助情報より細かい粒度でデータ・エレメントに関連付けられる。より具体的には、上位キャッシュＣ１では、キャッシュ・ラインに各データ・エレメントＤｌの有効性を示す補助情報（有効情報）Ｖ１が含まれる。下位キャッシュでは、有効情報Ｖ１は４データ・エレメント（上位キャッシュのライン・サイズに対応する）Ｄ２の粒度に関連付けられる。上位キャッシュＣ１は、下位キャッシュＣ２内のどのデータがより細かい粒度で上書きされるかを示すライトマスクＷＭをデータ・ラインＤＬと共に下位キャッシュＣ２に送信するように調整されている。ライトマスクＷＭは、Ｃ１の１つのキャッシュ・ラインに属する４つの有効ビットＶ１で構成される。
【００２０】
本発明によるデータ処理システムの動作について、図３に関連して詳細に説明する。
【００２１】
ステップ１で、Ｃ２はＣｌのキャッシュ・ラインとライトマスクおよびアドレスを受け取る。
【００２２】
ステップ２で、Ｃ２のタグがこのアドレスに一致するかどうかを確認する。
【００２３】
こうしたタグが見つからない場合は（Ｎ）、ステップ３が実行され、Ｃ２内で置き換えの「犠牲（ｖｉｃｔｉｍ）」となるラインが特定される。置き換えの対象となるラインを選択するには、本発明の範囲を外れた複数の方法を適用できる。たとえば、よく知られているものとしてＬＲＵ（least recently used：最近最も使われていないもの）方式がある。あるいは、たとえば無作為選択方式を適用してもよい。
【００２４】
ステップ３に続いてステップ４が実行され、この「犠牲」のタグ情報に「アドレス有効」と「ダーティー」があるかどうかを確認する。
【００２５】
これが真（Ｙ）の場合は、ステップ５でこの「犠牲」のタグ情報の「有効情報」がすべてセットされているかどうかを確認する。それ以外（Ｎ）の場合は、ステップ６で次の処理が行われる。
メモリから犠牲となるＣ２ライン・コンテンツの読み出し（Ｒｅａｄ）が発行される。
「有効情報」がセットされていない場所は、犠牲がメモリ・データで更新される。この犠牲のキャッシュ・ラインの「有効情報」ビットがすべてセットされる。
【００２６】
ステップ６に続いてステップ７が実行され、この犠牲のラインがメモリにフラッシュされる。ステップ５の判断の結果が肯定（Ｙ）の場合は、ステップ６を省略して直ちにステップ７が実行される。
【００２７】
ステップ７に続いてステップ８が実行され、次の処理を含む新しいライン割り当てが行われる。
タグ情報に新しいアドレスが設定される。
このアドレスが有効に設定される。
「有効情報」ビットがすべてリセットされる。
【００２８】
ステップ４の結果が否定の場合は、ステップ５、６、７を省略して直ちにステップ８が実行される。
【００２９】
ステップ８に続いてステップ９が実行される。ここで、Ｃ２内で（現在）タグが一致する１ラインについて、アドレスの一致するＣ２内のデータ・エレメントの「有効情報」がセットされているかどうかが判断される。ステップ２の判断の結果が肯定の場合は、直ちにステップ９が実行される。
【００３０】
ステップ９に続いてステップ１０が実行され、この「有効情報」がセットされず、かつライトマスクが一部のみに設定されているかどうかが確認される。
【００３１】
この条件を満たす場合は、次の処理を含むステップ１１が行われる。
メモリからＣ２キャッシュのライン・コンテンツの読み出しが発行される。
「有効情報」が設定されていない場所は、Ｃ２キャッシュ・ラインの一部がメモリのデータで更新される。
このＣ２キャッシュ・ラインの「有効情報」ビットがすべてセットされる。
【００３２】
ステップ１１に続いて、次のサブ・ステップを含むステップ１２が実行される。
Ｃ２データ・エレメントへのＣ１データのマスクされた書き込みが行われる。
このキャッシュの場所の「有効情報」がセットされる。
このＣ２キャッシュ・ラインの「タグ情報」内の「ダーティー・ビット」がセットされる。
【００３３】
ステップ１０の判断の結果が否定の場合は、直ちにステップ１２が実行される。
【００３４】
図４に、本発明の第２の実施形態を示す。ここで、データ処理システムは１台または複数台のプロセッサＰ、Ｐ’、Ｐ"を備えており、プロセッサＰのメモリ階層Ｃ１、Ｃ２、Ｍは、前記下位キャッシュのランクより下いランクのメモリを備えており、前記他のプロセッサとこれを共有する。図示された実施形態において、マルチプロセッサ・システムを構成するプロセッサのそれぞれが独自のメモリ階層を備えており、プロセッサＰ’の階層は上位キャッシュＣ１’と下位キャッシュＣ２’を備えている。プロセッサＰ"の階層は、上位キャッシュＣ１"と下位キャッシュＣ２"を備えている。
【図面の簡単な説明】
【００３５】
【図１】本発明の実装に適したデータ処理システムの第１の実施形態を簡略化して示す図である。
【図２】図１の一部を詳細に示す図である。
【図３】本発明によるデータ処理システムの動作方法を簡略化して示す図である。
【図４】本発明の実装に適したデータ処理システムの第２の実施形態を簡略化して示す図である。
【図１】
2006501563.tif 000003
【図２】
2006501563.tif 000004
【図３】
2006501563.tif 000005
【図４】
2006501563.tif 000006
【国際調査報告】
2006501563.tif 000007
2006501563.tif 000008