(57)【要約】キャッシュラインを投機的に無効にするように形成されたキャッシュコントローラ４１９は、エラーチェックが完了するのを待機する代わりに、無効リクエストまたは命令に直ちに応答することができる。エラーチェックによって、無効が誤っていて実行されるべきでないことが決定された場合、キャッシュコントローラは、エラーチェックが完了するまで、投機的に無効にされたキャッシュラインが変更されるのを防ぐ。このように、この無効が後で誤っていることが判明した場合、投機的な無効はリバースすることができる。エラーが全く検出されずに、エラーチェックが完了した場合は、投機的な無効は投機的でなくなる。
2004529435.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサ（４０９）と、
システムメモリ（４２５）と、
前記プロセッサと接続されており、複数のキャッシュライン記憶領域を有するキャッシュ（４２３）と、
第１リクエストを受け取るために接続されており、前記第１リクエストに応じて、第１キャッシュライン記憶領域の第１キャッシュラインを投機的に無効にするように形成されると共に、前記第１キャッシュラインを投機的に無効にすることに応じて、前記第１キャッシュラインの無効が投機的でなくなるまで、前記第１キャッシュライン記憶領域が変更されるのを防ぐように形成される、キャッシュコントローラ（４１９）と、
前記第１リクエストに対応する少なくとも一つのチェックを実行するために形成されるエラー検出ユニット（６０３）と、を含み、
前記チェックが実行され、エラーを検出しない場合、前記第１キャッシュラインの無効は投機的でなくなる、
コンピュータシステム。
【請求項２】
前記キャッシュコントローラ（４１９）は、前記第１キャッシュラインに関連する有効ビットをトグルすることによって、前記第１キャッシュラインを投機的に無効にするように形成される、
請求項１記載のコンピュータシステム。
【請求項３】
前記キャッシュコントローラ（４１９）は、前記チェックが実行され、エラーを検出する場合、前記第１キャッシュラインに関連する前記有効ビットをトグルすることによって、前記投機的な実行をリバースするようにさらに形成される、
請求項２記載のコンピュータシステム。
【請求項４】
キャッシュ（４２３）中のラインを投機的に無効にする方法であって、
前記キャッシュ中の前記ラインを無効にするリクエストを受け付けるステップと、
前記無効が誤っているかどうかを決定するチェックを開始するステップと、
前記受け付けるステップに応じて前記ラインを投機的に無効にするステップと、
前記チェックのうちの一つが前記無効は誤っていると決定することに応じて、前記ラインが有効であると示すことによって、前記投機的な無効をリバースするステップと、
を含み、
前記投機的に無効にするステップは、前記ラインが無効であることを示すステップと、前記チェックが完了するまで、前記ラインがその後変更されるのを防ぐステップと、を含む、方法。
【請求項５】
前記投機的に無効にするステップは、前記ラインに関連する有効ビットをトグルすることを含む、
請求項４記載の方法。
【請求項６】
複数のキャッシュライン記憶領域を有するキャッシュ（４２３）と、
第１リクエストを受け付けるために接続されており、前記第１リクエストの受け付けに応じて、第１キャッシュライン記憶領域中の第１キャッシュラインを投機的に無効にするように形成され、さらに、前記投機的な無効が誤っていることが検出される場合、前記第１キャッシュラインの前記投機的な無効をリバースするように形成され、前記投機的な無効が誤っているかどうかを検出するために所定のサイクル数を必要とするキャッシュコントローラ（４１９）と、
前記キャッシュコントローラが前記第１キャッシュラインを投機的に無効にするのに応じて、前記所定のサイクル数の間、前記第１キャッシュラインが変更されるのを防ぐように形成される、投機的無効コントローラ（５０６）と、を有し、
前記投機的な無効は、前記所定のサイクル数の後に投機的でなくなる、
キャッシュサブシステム。
【請求項７】
前記キャッシュコントローラ（４１９）は、前記第１キャッシュラインに関連する有効ビットをトグルすることによって、前記第１キャッシュラインを投機的に無効にするように形成される、
請求項６記載のキャッシュサブシステム。
【請求項８】
前記キャッシュコントローラ（４１９）はさらに、前記第１キャッシュラインに関連する前記有効ビットをトグルすることにより、前記投機的な実行をリバースするように形成される、
請求項７記載のキャッシュサブシステム。
【請求項９】
前記投機的無効コントローラ（５０６）はさらに、前記所定のサイクル数の間、前記キャッシュコントローラが、投機的に無効にされた前記第１キャッシュラインを変更するまたはそれに依存する追加のリクエストを受け付けるのを防ぐように形成されている、
請求項６記載のキャッシュサブシステム。
【請求項１０】
前記投機的無効コントローラ（５０６）は、前記キャッシュコントローラが前記第１キャッシュラインを投機的に無効にするのに応じて、レジスタ（５０４）に前記第１キャッシュラインのタグの最初の部分をロードするように形成される、
請求項９記載のキャッシュサブシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ、特に、キャッシュ中のラインを無効にすることに関する。
【背景技術】
【０００２】
一般的に、メインシステムメモリは速度よりも記録密度に重きをおいて設計されているので、マイクロプロセッサ設計者は、マイクロプロセッサが直接メインメモリにアクセスする必要性を軽減させるために、設計にキャッシュを加えた。
キャッシュは、メインメモリよりもさらに速くアクセスできる、小さなメモリである。コンピュータシステムは、多くの異なるレベルのキャッシュを有している。例えば、コンピュータシステムは、「レベル１（Ｌ１）」キャッシュおよび「レベル２（Ｌ２）」キャッシュを有している。これらのキャッシュは、マイクロプロセッサに一般的に統合される。
キャッシュは、メインシステムメモリに使用されているメモリ（一般的には、ＤＲＡＭ（dynamic random access memories）またはＳＤＲＡＭ（synchronous dynamic random access memories））よりも速いアクセス時間を有しているＳＲＡＭ（static random access memories）のような、速いメモリセルから一般的に構成される。
ＳＲＡＭはより高速であるが、記録密度が低く、またコストが高いので、メインシステムメモリに一般的には使用されない。
【０００３】
また、他の多くのタイプのキャッシングも可能である。
例えば、メインシステムメモリは、そのシステムのより遅いダイレクトアクセス記憶装置（例えば、ハードディスクドライブ）のキャッシュの役割をする。ハードドライブのような他のデバイスもまた、それらの性能を改良するための内部キャッシュを含んでいる。
【０００４】
マイクロプロセッサがメモリからのデータを必要とする場合、マイクロプロセッサは、一般的に、必要なデータがキャッシュに入れられたかどうか確かめるため、まずＬ１キャッシュをチェックする。Ｌ１キャッシュに入れられていない場合、Ｌ２キャッシュをチェックする。
同時に、Ｌ２キャッシュをミスする場合に備え、そのデータはメモリに対してもリクエストされる。
Ｌ２キャッシュがそのデータを格納している場合、Ｌ２キャッシュは、一般的にメインシステムメモリよりもはるかに高い速度、またより低いレイテンシで、マイクロプロセッサにそのデータを供給する。また、そのデータがメモリに対してリクエストされていた場合、そのリクエストはキャンセルされる。
データがＬ１キャッシュまたはＬ２キャッシュに入れられていない場合（「キャッシュミス」と呼ばれる）、そのデータは、メインシステムメモリまたは色々なタイプの大容量記憶装置（例えば、ハードディスクドライブ）から読み込まれる。
メモリにアクセスすることは、Ｌ１キャッシュからデータにアクセスすることに比べて、かなり多くのクロックサイクルを必要とする。同様に、データがメインシステムメモリにない場合に、大容量記憶装置のデータにアクセスすることはさらに多くのサイクルを必要とする。
【０００５】
キャッシュは、一般的にはメモリアクセスの局所性（locality of reference）の原理で動作し、これは、最も最近使用されたデータ（その近くのアドレスのデータ）が、それ以外のデータよりもアクセスされる可能性が高いことを示す。
コンピュータソフトウェアは、一般的に、あらかじめ実行されたコードが再実行されるループおよびブランチを有するので、この法則は有効である。
キャッシュに最近アクセスされた命令およびデータを格納することによって、マイクロプロセッサが命令とデータとがメインメモリから読み込まれるのを待つ必要がないので、システム性能が増加する。
【０００６】
マイクロプロセッサとコンピュータシステムの設計者は、メモリアクセスの局所性の原理をさらに一歩進めて、ブランチ予測のようなテクニックを使用することによって、それらがマイクロプロセッサによって実際に必要とされる前に、先を見越してキャッシュ内に命令およびデータを格納させている。
さらに、命令またはデータのバイトがメモリから読まれる場合、その命令またはデータに続くバイトが追加して読み込まれ、キャッシュに入れられる。
メモリアクセスの局所性の原理は、これらの命令とデータバイトがプロセッサによって必要となる可能性が他のデータや命令よりも一般的に高いことを示す。
【０００７】
キャッシュの中にシステムメモリをマップ（マッピング）するいくつかの異なる方法がある。よくあるアプローチの一つは、ｎウェイ・セットアソシアティブキャッシュを利用する。このキャッシュは、複数のセットに分割される。各セットは、ｎ個のキャッシュラインを含んでいる。キャッシュラインは、連続するバイトのグループ（例えば、３２または６４バイト)である。
効率性を上げるために、キャッシュメモリのトランザクションは一般的に、単一のバイト毎というよりキャッシュライン毎に行われる。
メインメモリ中のキャッシュに入れることができるロケーションは、各々、キャッシュラインのセットのうちの１つに割り当てられる。その結果、各ロケーションは、その割り当てられたセット内のｎ個の場所のうちのどのキャッシュにでも入れることができる。
ｎウェイ・セットアソシアティブキャッシュの特別なケースの一つは、ダイレクトマップキャッシュである。ｎ＝１であるダイレクトマップキャッシュでは、各メモリロケーションがキャッシュ中の単なる一つのロケーションにマップされ得る。
ｎウェイ・セットアソシアティブキャッシュの他の特別なケースは、フルアソシアティブキャッシュである。このケースでは、ｎ＝ｍであり、ｍがそのキャッシュ中のラインの数である（つまり、ただ一つのセット」がある）。このケースでは、各メモリロケーションは、そのキャッシュ中の全てのロケーションにもマップされ得る。
【０００８】
キャッシュへの基本的な２つの動作性能の基準は、ヒット率（すなわち、メモリアクセスの合計数に対する、キャッシュで見つかるメモリアクセスの比率）と検索速度（すなわち、どれだけ速くヒットまたはミスの判断ができるか）である。
ダイレクトマップキャッシュでは、検索速度はヒット率を犠牲にして最適化される。
これは、ヒットまたはミスの判断をすることが比較的容易である（メモリロケーションは、単に１つのキャッシュラインへマップするだけなので、そのラインだけをチェックする。)が、複数のメモリロケーションが一つのキャッシュラインへマップするので、高いヒット率を持つのは困難であるからである。
反対に、フルアソシアティブキャッシュは、検索速度を犠牲にする一方、ヒット率を最適化する。
すべてのメモリロケーションをすべてのキャッシュラインにマップすることを許可することは、ヒットする確率を改善するが、各メモリロケーションを探すためにすべてのキャッシュラインを検索しなければならないため、検索の複雑さを大幅に増加させる。
セットアソシアティブキャッシュは、フルアソシアティブキャッシュよりも速い検索速度を提供する一方、ダイレクトマップキャッシュよりも大きなアソシアティビティ（すなわち、より高いヒット率)を提供する意味で、二つのキャッシュ方式の折衷案である。
【０００９】
キャッシュサイズは、多くの要因（ダイサイズ、電力消費およびコストを含む。)によって制限されているため、キャッシュに情報をロードする場合、注意を要する。
新たな命令およびデータのための場所を作るために、キャッシュ中の既存の命令およびデータを上書きするため、または無効にするためのポリシー決定は、設計者の関心が高い分野である。
したがって、ｎ＞１であるセットアソシアティブキャッシュ（すなわち、特定のメモリロケーションをキャッシュするためのラインの選択の余地がある）中で、どのキャッシュラインを新しいデータで満たすべきかを決定するための方法が必要である。
よくある解決策は、キャッシュされた各メモリロケーションに対するアクセスの相対的な順位をトラックし、次に、最も少ない使用頻度の命令またはデータを、新しい命令またはデータに取り替えるものである。
この解決策は、最近アクセスされたキャッシュラインが再びアクセスされる可能性があるという法則に基づく。他の解決策は、ランダムな置換およびＦＩＦＯテクニックを含む。
【００１０】
平均的には、最低使用頻度（ＬＲＵ）のキャッシュ置換アルゴリズムは、他のアルゴリズムよりもよい性能を提供する。
しかしながら、ｎウェイ・セットアソシアティブキャッシュ中の最低使用頻度（ＬＲＵ）キャッシュラインを決定するための従来のアプローチは、ＬＲＵアルゴリズムをインプリメントするために、カウンタおよびｎウェイ・マルチプレクサを含む相当量の複雑なハードウェアを必要とする。さらに、各キャッシュエントリのステータスビットは、各エントリの使用量をトラックする。
新しいエントリがセット中でなされる場合、ステータスビットはどのキャッシュラインの使用頻度が最低か、または無効であるかを決定するためにスキャンされる。最低使用頻度ラインまたは無効なラインはその後、新しいエントリに場所を空けるために追い出される。
従来のＬＲＵ置換アルゴリズムの欠点は、相当量のハードウェアとアルゴリズムをインプリメントするのに必要なステータスビットの時間を多く必要とするとともに、そのセットに無効なエントリがないかをスキャンするために時間とハードウェアが必要なことである。
【００１１】
一般的に、キャッシュサブシステムの性能を改良することが望ましい。例えば、プロセッサ速度の改良と共に、より多くのデータをより速く供給することができるキャッシュサブシステムを提供することが望ましい。
【発明の開示】
【００１２】
キャッシュラインを無効にすることは多くの場合有用である。
しかしながら、キャッシュラインの無効（無効処理）は、多くの根本的な要因に依存する可能性がある。多くの状況では、エラーチェックがこれらの根本的な要因が正確だったかどうか断定するために行なわる。これらの要因が正確でない場合、その無効は誤りであるので行なわれるべきではない。
エラーチェックを完了するためには相当量の時間がかかることがあるため、無効リクエストがキャッシュコントローラによって実際に読み込まれるとき、その無効が誤っているかどうかに関する決定は不確定である。その結果、無効リクエストは、キャッシュコントローラが他のペンディング中のタスクに移行するのを防ぐために、エラーチェックが終わるまで待機することをキャッシュコントローラに要求することができる。
同時に、キャッシュラインの無効が誤っていることは稀であるため、エラーチェックが完了するのをキャッシュコントローラが待機する時間が無駄になることが多い。
【００１３】
キャッシュコントローラが投機的にキャッシュラインを無効にするように形成される場合、キャッシュコントローラはエラーチェックの完了を待機する代わりに、無効リクエストに直ちに応答することができる。
キャッシュコントローラはまた、無効が誤っていて行なわれるべきでない稀な状況を処理するために、エラーチェックが完了するまで、投機的に無効にされたキャッシュラインが変更されるのを防ぐことができる。このように、後でその無効が誤っていた場合、投機的な無効をリバースする（覆す）ことができる。
【００１４】
よって、投機的にキャッシュラインを無効にする方法およびシステムの様々な実施例を開示する。
一つの実施例では、コンピュータシステムは、プロセッサ、システムメモリ、キャッシュコントローラ、キャッシュおよびエラー検出ユニットを含む。
キャッシュは、プロセッサに接続され、多くのキャッシュライン記憶領域を含む。キャッシュコントローラは、第１キャッシュラインを無効にする第１リクエストを受け取るために接続される。第１リクエストの受け取りに応じ、キャッシュコントローラは投機的に第１キャッシュラインを無効にするように形成される。
後に、投機的な無効をリバースする必要があるときのために第１キャッシュラインを保存するため、第１キャッシュラインの無効が投機的でなくなるまで、キャッシュコントローラはさらに第１キャッシュライン記憶領域が変更されるのを防ぐように形成される。
エラー検出ユニットは、第１リクエストに対応する少なくとも１つのチェックを行なうように形成される。エラー検出ユニットは、例えばキャッシュコントローラ自体であり、そのチェックは、投機的な無効（例えば、より高いレベルのキャッシュからのフィルリクエストに応じた排他キャッシュでのヒット）に結びついた処理が第１キャッシュラインの状態において適切だったことを確かめるためのチェックを含む。エラー検出ユニットがチェックを行なってエラーを検出しなければ、第１キャッシュラインの無効は投機的でなくなる。
【００１５】
１つの実施例では、キャッシュコントローラは、第１キャッシュラインに関連した有効ビットをトグル（反転）することにより、第１キャッシュラインを投機的に無効にするように形成される。
従って、投機的な無効をリバースすることは、第１キャッシュラインが再び有効なことを示すために再度有効ビットをトグルすることを含んでいてもよい。
さらに、いくつかの実施例では、キャッシュコントローラは第１キャッシュラインのデータまたはその状態に依存するリクエストを、第１キャッシュラインの無効が投機的でなくなるまで受け入れないように形成される。
このように、投機的な無効が投機的ではなくなるかリバースされるまで、これらのリクエストは遅延されることがある。
一般にキャッシュコントローラは、第１キャッシュラインの無効が投機的でなくなるまで、リクエストのタイプに基づく追加のリクエスト、または投機的に無効にされた第１キャッシュラインに依存するか、または投機的に無効にされた第１キャッシュラインを変更するリクエストを受け入れないように、形成される。
例えば、キャッシュコントローラは、追加のリクエスト（第１キャッシュラインをヒットするより高いレベルのキャッシュからのフィルリクエスト、第１キャッシュラインへのプローブ・リクエストまたはステートチェンジ・リクエスト、置換のために第１キャッシュラインを選択するより高いレベルのキャッシュからのコピーバック）を受け入れないように形成されてもよい。
キャッシュコントローラは、第１キャッシュラインのタグの一部と一致する追加のリクエストを受け入れないように形成することもできる。
【００１６】
いくつかの実施例では、投機的な無効の一部として、キャッシュコントローラは、第１キャッシュラインに関連した投機的な無効置換事前状態(例えば、置換のためのラインを選択した状態)を保存し、かつあたかも第１キャッシュラインが無効にされたかのように、第１キャッシュラインの投機的な無効置換事後状態を更新するように形成される。
投機的な無効がその後誤っていると決定された場合、キャッシュコントローラは、投機的な無効をリバースするとき、保存された投機的な無効置換事前状態を回復することができる。
【００１７】
別の実施例では、投機的にキャッシュのラインを無効にする方法が示される。
この方法は、キャッシュのラインが無効にされる結果になるリクエストを受け入れるステップ、その無効が誤っているかどうか決定するチェックを開始するステップ、投機的にラインを無効にするステップを含む。
投機的にラインを無効にするステップは、そのチェックが完了するまで、ラインが無効であることを示すステップ、その後ラインが変更されるのを防ぐステップを含む。
この方法はさらに、上記チェックのうちの一つによってその無効が誤っていると決定された場合、ラインが再び有効であることを示すことによって投機的な無効をリバースするステップを含む。
【００１８】
別の実施例では、排他キャッシュの第１キャッシュラインを投機的に無効にする方法が示される。
この方法は、より高いレベルのキャッシュからのフィルリクエストを受け入れるステップ、フィルリクエストが排他キャッシュの中でヒットするか決定するステップ、そのフィルリクエストが誤って開始されたかどうかのチェックを開始するステップ、そして、フィルリクエストが排他キャッシュの中でヒットした場合、排他キャッシュからより高いレベルのキャッシュに第１キャッシュラインを供給すること、を含み得る。
第１キャッシュラインがより高いレベルのキャッシュに供給される場合、チェックがまだ完了していなければ、第１キャッシュラインは投機的に無効にされる。
投機的に無効にするステップは、第１キャッシュラインが無効であることを示すステップ、チェックが完成するまで第１キャッシュラインがその後変更されるのを防ぐステップを含んでいてもよい。
【００１９】
さらに別の実施例では、キャッシュサブシステムが示される。このキャッシュサブシステムは、キャッシュと、キャッシュコントローラとを含む。
キャッシュコントローラは、投機的に第１キャッシュラインを無効にするように形成される。
投機的な無効が誤っていると検出された場合、キャッシュコントローラは、投機的な無効をリバースするように形成され得る。
キャッシュサブシステムはまた、その無効が投機的でなくなるまで、第１キャッシュラインが変更されるのを防ぐように形成された投機的無効コントローラを含んでいてもよい。
投機的な無効が誤っているかどうかを検出することは、所定のサイクル数を必要とすることがあり、それゆえ投機的な無効は、その所定のサイクル数の後にならないと投機的ではなくならない。
【００２０】
本発明は、様々な修正および代替が可能であるが、この中の特定の実施例を図面に記載した例で示し、詳細に説明する。
しかしながら、図面および詳細な説明は、発明を開示された特別の形式に制限するものではない。それどころか、本発明は添付の請求項によって定義されるような本発明の趣旨およびその範囲内にある変形例、均等物および代替物に及ぶ。
【本発明の実施態様】
【００２１】
＜キャッシュサブシステム＞
下記の図６および図７に示されるようなコンピュータシステムは、一般的にはキャッシュサブシステムを使用する。
一般的には、これらのキャッシュサブシステムは、プロセッサに統合されたＬ１キャッシュおよび統合されていないＬ２キャッシュを含む。
しかしながら、プロセス技術の進歩によって、半導体デバイスのより高い集積化が可能となるにつれて、マイクロプロセッサ設計者は、性能をより良くする方法として、現在、第２レベル（Ｌ２）のキャッシュをチップ上に含めることができる。
Ｌ２キャッシュの統合によって、信号ピンを通じて通信する必要がなくなるため、Ｌ１とＬ２のキャッシュ間の転送レイテンシおよび転送帯域幅が改良され得る。
【００２２】
従来のアプローチは、一次キャッシュ（Ｌ１）を、付加的なアクセスレイテンシーを負うことなく、できるだけ大きなＬ１キャッシュを作ることを目標として設計した。
従来、この大きなＬ１キャッシュは、通常はＬ１キャッシュと同一またはより大きい大きさであって、通常はＬ１キャッシュよりも大きいがシステムメモリよりは小さいレイテンシを有するＬ２キャッシュによって補完される。
【００２３】
Ｌ２キャッシュは、統合的（inclusive） 、排他的（exclusive）、またはそのどちらでもないように設計することができる。
理想的な統合的なＬ２キャッシュは、図１Ａのベン図に示すように、Ｌ１キャッシュにあるすべてのラインはＬ２キャッシュにもある。対照的に、理想的な排他的なＬ２キャッシュでは、図１Ｂのベン図に示すように、Ｌ１キャッシュにあるラインはＬ２キャッシュにはない。
図１Ａまたは図１Ｂに示すように、いくつかの実施例では、統合的なＬ２キャッシュおよび排他的なＬ２キャッシュの両方とも、システムメモリに関しては統合的であり得るため、「排他的な」Ｌ２キャッシュはＬ１キャッシュに関してのみ排他的である。
統合的でも排他的でもないキャッシュシステムでは、Ｌ２キャッシュに格納されるラインは、どのラインがＬ１キャッシュに格納されるかに依存しない。したがってまた、Ｌ１キャッシュ中のラインがＬ２キャッシュの中に存在するか否かに関しての保証はない。
【００２４】
これらの各法則には、利点と欠点の両方がある。一般的には、ほとんどのＬ２キャッシュは統合的である。統合キャッシュでは、Ｌ１からＬ２へのデータ転送の数は減少する。
Ｌ２キャッシュに変更されていないＬ１ヴィクティム（victim）をコピーバックする必要がないので、この転送数の減少が生じる。ヴィクティムは、再度使用される前に、メインメモリにライトバックされる（書き戻される）データブロックである。
例えば、Ｌ１キャッシュフィルが既存のラインの置換を必要とする場合、入ってくるラインに場所を空けるために、既存のラインまたはヴィクティムは、Ｌ１キャッシュから放出される。統合キャッシュでは、Ｌ１ヴィクティムのコピーは、既にＬ２キャッシュにある。
したがって、Ｌ１キャッシュで、Ｌ１ヴィクティムが変更されていない場合、同一のラインが既に存在するので、Ｌ２キャッシュにそのラインをコピーする必要はない。
オフチップＬ２キャッシュについては、Ｌ１キャッシュ中のラインがＬ２キャッシュにあることが保証されるため、Ｌ１からＬ２へのコピーバックする間に外部のＬ２タグ検査を行なう必要がないので、統合性もまた非常に重要である。さらに、Ｌ２キャッシュは、例えば、インラインのＬ２構成が使用される場合、Ｌ１キャッシュ用のスヌープフィルタとなる。
【００２５】
統合キャッシュの主な欠点の一つは、有効なキャッシュのサイズを減少させることである。
Ｌ１中のすべてのラインがＬ２にもあるので、図１Ａに示すように、Ｌ１キャッシュとＬ２キャッシュをあわせた有効なキャッシュサイズは、Ｌ２キャッシュのサイズとなる。これが、一般的にＬ２キャッシュがＬ１キャッシュよりも大きい理由の一つである。
他の欠点は、統合性を維持する必要のためにキャッシュコントローラ設計がより複雑になることである。
例えば、潜在的なＬ２ヴィクティムが選択されている場合、統合キャッシュコントローラは、Ｌ２ヴィクティムがＬ１キャッシュに現在存在しないことを確かめるためにＬ１キャッシュをバックプルーブ（back-probe）しなければならない。
潜在的なＬ２ヴィクティムがＬ１キャッシュに存在する場合、統合性を維持するために別のヴィクティムを選択しなければならない。
代わりに、他の実施例では、潜在的なＬ２ヴィクティムがさらにＬ１キャッシュに存在する場合、統合性は、（別のＬ２ヴィクティムを選択するのではなく）Ｌ１キャッシュの対応するラインを無効にすることによって維持される。
【００２６】
キャッシュは一般的に、記録密度が低くてメモリのコストが高く、特にＬ２キャッシュが一般的には統合的でＬ１キャッシュよりも大きいことから、Ｌ２キャッシュの統合は、コストおよびチップ上の実際上の面積的な見地の両方から歴史的に好まれない設計選択であった。
【００２７】
図１Ｂで示すように、排他キャッシュは、統合キャッシュとは対照的に、Ｌ１とＬ２のキャッシュとが結合したサイズと等しい、より大きい有効なキャッシュサイズを提供できる。このより大きな有効なキャッシュサイズは、よりよいヒット率をもたらし得る。さらに、Ｌ２ヴィクティムを追い出す場合にＬ１キャッシュにバックプルーブする必要がないので、Ｌ２コントローラの複雑さは減少される。
【００２８】
排他キャッシュを使用する場合、Ｌ１キャッシュとＬ２キャッシュの間の転送数は増加する。
例えば、Ｌ１ヴィクティムは、変更されたかどうかにかかわらず、メモリアクセスの局所性の原理に従って、Ｌ２キャッシュにコピーされるので、Ｌ１からＬ２へのデータ転送の数は増加することがある。
Ｌ１ヴィクティムは、Ｌ２キャッシュ中の他のどのラインよりも使用頻度が高い可能性があるので、Ｌ２キャッシュにＬ１ヴィクティムを格納することにより、メモリアクセスの局所性の原理を満足させ得る。
いくつかの例では、増加したＬ１からＬ２へのトラヒックは、Ｌ１とＬ２のキャッシュ間の通信リンクに依存して、統合キャッシュをより望ましくすることができる。
【００２９】
排他キャッシュは、さらに他のキャッシング・アプリケーションにおいても有用である。
例えば、グラフィックスシステムまたはハードディスクドライブと共に使用されるマルチレベルキャッシュサブシステムを設計することは有用である。
これらの実施例では、統合キャッシュに必要とされる付加的なキャッシュメモリの量と同じ量のキャッシュメモリを必要とすることなく、キャッシュサブシステムの有効なサイズを増加させるために排他キャッシュを使用することは望ましい。
いくつかの実施例では、排他キャッシュは、より高いレベルのキャッシュとしてそれが同じ基板に統合されていないとしても、実用的な設計選択である。
【００３０】
図２は、実行コア４０９によって使用されるシステムメモリ４２５からのデータラインおよび／または命令ラインを格納するように形成されるキャッシュサブシステム４０７の一実施例である。
実行コア４０９は、キャッシュサブシステムコントローラ４１９にアドレスバス４１１上のアドレスを提示することによって、データを要求する。そのアドレスは、仮想アドレスであってもよい。
この例では、同じキャッシュサブシステムコントローラ４１９がＬ１キャッシュおよびＬ２キャッシュの両方を制御しているが、個別のＬ１コントローラおよびＬ２コントローラを他の実施例として使用してもよい。Ｌ２キャッシュ４２３は、統合的、排他的、またはそのどちらでもないものとすることができる。
【００３１】
実行コア４０９からのアドレスの受信に応答して、キャッシュサブシステムコントローラ４１９は、Ｌ１キャッシュ４１７にそのアドレスを提供することができる。
いくつかの実施例では、Ｌ１キャッシュ４１７は、線形に、または仮想的にアドレスされ得る。したがって、実行コア４０９から受け取ったアドレスが仮想アドレスである場合、Ｌ１キャッシュ４１７にそれを提供する前にアドレスを翻訳する必要はない。
対照的に、Ｌ２キャッシュ４２３は、いくつかの実施例で物理的にアドレスされ得る。したがって、Ｌ１キャッシュ４１７にミスが生じた場合、仮想アドレスはＬ２キャッシュ４２３への提供の前に翻訳される必要がある。
他の実施例では、両方のキャッシュは同じように（例えば、仮想的にまたは物理的に）アドレスされ得る。
【００３２】
Ｌ１のフィルリクエストがＬ２キャッシュ４２３をミスした場合、そのラインはシステムメモリ４２５にリクエストされ得る。そして、Ｌ１キャッシュ４１７の中に導かれる（例えば、Ｌ２キャッシュ４２３が排他的である場合）。またはＬ２キャッシュとＬ１キャッシュの双方に導かれる（例えば、Ｌ２キャッシュ４２３が統合的である場合）。
Ｌ１キャッシュ４１７中のリクエストされたラインをフィルするために、Ｌ１ヴィクティムが作成され、Ｌ２キャッシュ４２３にコピーバックされ得る（Ｌ２キャッシュ４２３が排他的である場合、Ｌ１ヴィクティムがクリーンであるか変更されるかどうかに関わらず、またはＬ２キャッシュ４２３が統合的である場合、Ｌ１ヴィクティムが変更されるかどうかに関わらず)。
Ｌ２キャッシュ４２３が排他的な場合、このコピーバックは、Ｌ２ラインの立ち退きを要求することもある。したがって、Ｌ２ヴィクティムが作成される可能性があると共に、ヴィクティムが変更される場合、メモリ４２５にライトバックされ得る。
Ｌ２キャッシュ４２３が排他的な実施例では、Ｌ１キャッシュとＬ２キャッシュの両方のキャッシュは、一つまたはそれ以上のヴィクティムバッファ４２１を共有し得る。ヴィクティムバッファ４２１は、それらが排他的なＬ２キャッシュ４２３（それらがＬ１ヴィクティムである場合）または、システムメモリ４２５（それらが変更済のＬ２ヴィクティムである場合）にコピーバックされるヴィクティムラインをバッファリングする。
【００３３】
Ｌ１フィルリクエストがＬ２キャッシュ４２３でヒットする場合、そのラインはＬ１キャッシュ４１７にコピーされ得る。
そのＬ１リクエストがＬ２排他キャッシュ４２３でヒットすれば、排他性を維持することに関連する理由によって、ヒットラインを有効にしておくのではなく、無効にすることが望ましい。たとえば、ラインが無効にされれば、キャッシュサブシステム４０７にはそのラインのコピーが一つだけある。
このことは、ある瞬間にそのラインのどのコピーがより新しいかをトラックする必要がないので、キャッシュサブシステム４０７のための制御ロジックを非常に単純化し得る。
さらに、ラインを無効にすることは、排他キャッシュシステムによって提示されたより大きな有効なキャッシュサイズが実現されることを可能にして、Ｌ２キャッシュ４２３中の場所を解放する。
しかしながら、ラインが無効にされる前に、無効に結びつくオペレーション（例えば、Ｌ２キャッシュへのフィルリクエストを生成するＬ１キャッシュのミス）が誤って行なわれたかどうか断定するためのいくつかのチェックを行うことができる。そのチェックによってエラーが露呈する場合、そのオペレーションをキャンセルすると共に／または、後で再試行することができる。
このようにして、これらのチェックが無効を引き起こす条件が誤っていないことを示す場合にのみ、無効化が実行される。
【００３４】
また、統合キャッシュ中で、あるいは排他的でも統合的でもないキャッシュ中で、ラインが無効にされ得る多くの状況がある。
排他キャッシュでの無効のように、これらのチェックは、無効にする命令が誤っていたかどうかを断定する様々なチェックに結局依存する。
例えば、命令がアウトオブオーダー（out of order）で実行されている場合、ある命令は分岐予測の結果、フェッチされることがある。
この分岐予測が正しくないことが判明した場合、フェッチされた命令の実行は取り消される必要があると共に／または、フェッチされた命令の実行の影響はリバースされる必要がある。
あるいはまた、非優先モード中でアウトオブオーダーで実行される命令は、優先命令であり得る。
これらの命令のうちの一つが、キャッシュから実際にラインをフラッシュせずに、キャッシュラインまたはブロックを無効にする命令であり、その命令がＬ１キャッシュ中のラインを無効にする場合、さらに統合的なＬ２キャッシュ中のそのラインのコピーを無効にすることは望ましい。
しかしながら、あるチェックが、後に分岐予測の誤りまたは優先違反を発見した場合、一つの例外が生成され得る。また、例外を生成する命令に起因する無効がリバースされる必要がある。
このように、キャッシュの無効は例外チェックに依存する。
【００３５】
他のチェックの例は、コンピュータシステム中のデータの他のバージョンをオーダリング要求に応じるためにチェックすることを含む。
例えば、リクエストされたデータラインの変更済のコピーは、バッファ（例えば、より高いレベルのキャッシュからの書込みバッファあるいはヴィクティムバッファ）に格納される。
この変更済のコピーは、下位レベルのキャッシュに格納されたコピーよりも最近に変更されている可能性がある。よって、そのようなコピーが発見された場合、リクエストしているデバイスがリクエストされたデータの最も直近の変更済のコピーを受け取るように、下位レベルキャッシュへのフィルリクエストは取り消される。
【００３６】
実行される可能性のあるその他のチェックは、エイリアスチェックである。エイリアスチェックは、仮想アドレスキャッシュで生じ得る問題を検索することを含む。仮想記憶システムは、複数の仮想アドレスにメモリの一つの物理ページをマッピングする。
これらの異なる仮想アドレス（すなわち、エイリアス）は、仮想アドレスキャッシュ中の複数の場所にキャッシュされる。
例えば、それが異なるキャッシュラインおよび異なる仮想ページへマップする二つまたは二つ以上の異なる仮想アドレスにマップする場合、単一の物理ページからのデータは、仮想アドレスキャッシュ内の複数の場所に、潜在的にキャッシュされる。
その結果、一つの仮想アドレスを使用して、あるラインをリクエストすることは、たとえヒットを生成する可能性のある異なるエイリアスを使用して同じラインをリクエストしたとしても、ミスを生成する可能性がある。
エイリアスチェックは、仮想アドレスキャッシュ中のエイリアスされたラインに明白なミスが実際にヒットしたことを検出することができる。
例えば、一実施例では、仮想アドレスされたＬ１キャッシュは、独立した命令およびデータキャッシュを含む。
同じデータのコピーが命令とデータキャッシュの両方に同時に存在するように、Ｌ１キャッシュが形成される。Ｌ１コントローラは、データキャッシュ中のＬ１ヴィクティムを選択する場合に、エイリアスされたコピーをチェックするようには形成されない可能性がある。
その結果、Ｌ１ヴィクティムは、たとえそのラインのエイリアスされたコピーが、命令キャッシュ（あるいはヴィクティムがその命令キャッシュから選択された場合のデータキャッシュ)にまだ存在していても、排他的なＬ２キャッシュにコピーバックされる。
その結果、エイリアスチェックが完了する前に、そのデータのためのその後のフィルリクエストはＬ１でミスする可能性があるが、Ｌ２でヒットする可能性がある。
エイリアスチェックによってＬ１キャッシュのエイリアスされたコピーを発見されるので、そのラインはＬ２キャッシュ中で無効にされるべきではない。
したがって、以上のような実施例では、排他キャッシュ中の無効は、エイリアスチェックの結果に依存する。
【００３７】
チェックのさらに別の例では、ラインの状態に基づいて、そのラインにアクセスできるかどうかを決定する。多くのシステムが、各ラインのＭＥＳＩまたはＭＯＥＳＩ（Modified, Owned, Exclusive, Shared, Invalid）状態をトラックする。
ライン上であるオペレーションを行なうことが許容できるかどうかは、そのラインの状態による。
例えば、Ｌ１命令キャッシュからのフィルリクエストが、Ｌ２キャッシュ中の変更済のラインにヒットする場合、変更済のＬ２ラインがメモリに書き出された後まで、フィルリクエストに対応することは適切ではない（例えば、命令キャッシュがキャッシュコヒーレンシの状態を格納しない場合、そのような制限が使用されてもよい。）。
したがって、あるチェックは、特別のアクセスが、そのラインの現状を考慮に入れて、適切かどうか決めることを含んでいる。
【００３８】
したがって、排他的キャッシュまたは統合キャッシュのどちらにおいても、キャッシュラインは、別のキャッシュのオペレーションの一部として、またはその結果として、無効にされる。
同時にこれらの無効は、完了までに比較的長い時間を要する様々なチェックの結果によってリバースされ得る。
チェックが完了する後までその無効を遅らせるとすると、キャッシュは、チェック待ちに不適当な時間を費やす可能性がある。
キャッシュコントローラが、チェックが完了するまでそのラインを無効にするのを待機する場合、キャッシュは他のオペレーションを行うことができず、それゆえこの遅延は、キャッシュ性能に悪い影響を与える。
あるいはまた、チェックが完成する前に、キャッシュコントローラが無効を実行する場合、その無効がその後誤っていることが明らかになった場合、その無効にされたラインを回復する方法はない。
その結果、チェックを行うことがキャッシュサブシステムの精度を改良するが、この改良された精度は、性能を犠牲にして実現される。
【００３９】
＜キャッシュコントローラ＞
図２で示されるようなキャッシュサブシステムの性能を改善するために、リクエストの検査が完了していなくても、キャッシュコントローラは命令またはリクエストに応じてキャッシュラインを投機的に無効にするように形成される。
例えば、下位レベルの排他キャッシュのアクセスレイテンシを最小限にするために、ミスがより高いレベルのキャッシュに検出されるとすぐに、フィルリクエスト（このリクエストが排他キャッシュの中でヒットする場合、排他キャッシュのラインを最終的に無効にする。）は、下位レベルの排他キャッシュコントローラへ送られる。
これはエイリアシングおよび、オーダリング要求のような様々なチェックが行なわれる前に、下位レベルの排他キャッシュコントローラへリクエストを送信することを含んでいる。これらのチェックは、完了するまでいくつかのサイクルを要するが、それらが実際に誤っていることは稀である。
したがって、チェックが完了する前に投機的にキャッシュラインを無効にすることは、同時に不要な遅延を回避する一方、一般的に正確な結果を生む。
できる限りより良い効率を提供することに加えて、投機的な無効を行なうためにキャッシュコントローラを形成することに起因し得る利益の一つは、より良いリソースの使用量効率の向上である。
例えば、排他キャッシュコントローラは、各コマンドを別々に実行しなければならない代わりに、単一のコマンドとしてタグ検査および投機的な無効を実行することができる。
【００４０】
実際にチェックに失敗した稀な場合においては、チェックに失敗した問題が変更された後、無効を引き起こす命令またはリクエストは取り消され、遅延され、及び／または、再試行される。
例えば、命令キャッシュからのフィルリクエストが排他的なＬ２キャッシュの中でヒットする場合、そのリクエストは、Ｌ２キャッシュ中のヒットラインが変更済の状態である場合、取り消される。
しかしながら、ヒットラインが投機的に無効にされた場合、チェックが完了する時に無効をリバースすることは不可能なことがあり得る。
この状況を回避するために、投機的な無効を実行するように形成されるキャッシュコントローラは、また、その後そのチェックに失敗した場合に、投機的に無効にされたラインを元に戻すことを可能にする回復方法を提供するように形成される。
【００４１】
一つの実施例では、キャッシュコントローラは、チェックの完了後まで投機的に無効にされたラインが変更されるのを防ぐことによって、そのような回復メカニズムを提供する。
このように、投機的にラインを無効にすることは、キャッシュコントローラが、投機的に無効にされたラインを変更しない他のオペレーションに移すことを可能にする。
例えば、いくつかの実施例では、キャッシュコントローラに、ラインが投機的に無効にされる時間と、チェックが完了する時間との間に、いくつかのリクエストが与えられる。
これらの連続的な命令またはリクエスト、そして投機的な無効の間のコンフリクトを防ぐために（投機的な無効が後にリバースされる場合に備えて）、キャッシュコントローラは潜在的なコンフリクトをもたらすどんなリクエストも受け入れないように形成することができる。
キャッシュコントローラは、それらのリクエストが実際にそのラインを変更しなくても、投機的に無効にされたラインに関係するリクエストを遮るように形成することもできる。
例えば、投機的な無効が結局リバースされる場合（例えば、チェックのうちの一つがエラーを示すため）、チェック完了後まで、これらの変更を行わないリクエストを受け入れないことにより、あたかもそのラインが無効であるかのように、リクエストが誤って処理されるのを防ぐ。
したがって、一つの実施例では、キャッシュコントローラは、投機的に無効にされたラインのタグの一部と一致するタグがあるどんなリクエストあるいは命令も受け入れないように形成される。
【００４２】
わずかにより詳細な実施例では、キャッシュコントローラは、与えられたリクエストまたは命令のタイプによって、及び／または命令の潜在的な影響に基づいてリクエストを受け入れないように形成される。
例えば、キャッシュコントローラは、投機的に無効にされたラインのタグと一致するフィルリクエスト、プローブあるいは状態変更を遮る（screen out）ように形成される。
さらに、キャッシュコントローラは、タグ一致およびそのラインの置換状態の両方に基づいて、投機的に無効にされたラインを置換するコピーバックまたはフィルを受理しないように形成される。
例えば、コピーバックが投機的に無効にされたラインのタグと一致し、そのラインがセット中の最低使用頻度ラインである場合、ＬＲＵ置換が使用されているとすると、通常、そのラインは、コピーバックと置換される。
あるいはまた、キャッシュコントローラは、コピーバックを受理するが、（現在の置換状態を無視して）投機的に無効にされたラインの代わりに別のラインを置換するように形成される。
投機的に無効にされたラインの置換状態が、コピーバックまたはフィルが、投機的に無効にされたライン（例えば、ＬＲＵ置換手法が使用されており、投機的に無効にされたラインがＬＲＵラインではない。）に上書きしないであろうことを示す場合、キャッシュコントローラは、リクエストを受け入れるように形成される。
【００４３】
一つの実施例では、図３で示すように、キャッシュコントローラは、アドレスコンフリクト検出ハードウェア５００を含む。
アドレスコンフリクト検出ハードウェアは、投機的に無効にされているラインに帰着するリクエストと、ラインが無効にされる時間と、投機的な無効用のチェックが完了する時間の間で受信された後続するリクエストまたは命令との間の、相互作用を検出するように形成され得る。
【００４４】
アドレスコンフリクト検出ハードウェア５００は、投機的に無効にされたラインに対応するアドレスの全てまたは一部を格納するように形成されたアドレスレジスタ５０４を含む。例えば、アドレスレジスタ５０４は、投機的に無効にされたラインのタグを格納する。
投機的に複数のラインを無効にする能力を提供するために、これらのレジスタ５０４のいくつかは記憶装置５０２で提供される。
コンパレータ５０１は、係属中のリクエストのアドレスを、アドレスレジスタ５０４および／または記憶装置５０２の中のアドレスと比較する。
アドレスが一致しない場合、コンパレータ５０１は、イネーブル信号をアサートする。
キャッシュコントローラは、イネーブル信号の状態に基づいて、係属中のリクエストの受け入れを許可し、または許可しない。
例えば、係属中のリクエストのアドレスが投機的に無効にされたラインに対応するアドレス（またはアドレスの一部）と一致する場合、コンパレータ５０１は、イネーブル信号をディアサート（deassert）し、その結果キャッシュコントローラに係属中のリクエストを受け入れさせないようにする。
【００４５】
投機的な無効コントローラ５０６は、いくつかの実施例においてアドレスコンフリクト検出ハードウェア５００を制御する。
投機的な無効コントローラ５０６は、投機的に無効にされたラインのアドレスの一部またはタグの一部を記憶装置５０２のレジスタ５０４のうちの一つにロードするように形成される。
投機的な無効コントローラ５０６は、あるチェックにかかる最大サイクル数の間、投機的に無効にされたラインが変更されるのを防ぐように形成される。
例えば、投機的な無効コントローラ５０６は、エイリアスチェックが完了するのに必要なサイクル数の間、投機的に無効にされたラインが変更されるのを防ぐように形成される。
別の実施例では、投機的な無効コントローラ５０６は、例外チェックが完了するのに必要なサイクル数の間、投機的に無効にされたラインが変更されるのを防ぐ。
【００４６】
一つの実施例では、投機的な無効コントローラ５０６は、レジスタ５０４に投機的に無効にされたラインのタグの一部またはアドレスの一部をロードし、そのレジスタの値をコンパレータ５０１によって入ってくるリクエストと比較することにより、あるサイクル数の間、投機的に無効にされたラインが変更されるのを防ぐ。
指定されたサイクル数の後、投機的な無効コントローラ５０６は、レジスタ５０４をクリアするか、または、これ以上レジスタ５０４の値を入って来るリクエストと比較しないようにコンパレーター５０１に命じる。
投機的な無効コントローラも、変更されるのを防ぐべき投機的に無効にされたラインがない場合、イネーブル信号をアサートすることにより、コンパレータ５０１をバイパスするように形成される。
【００４７】
一つの実施例では、チェックが完了するまで、アドレスコンフリクト検出ハードウェア５００は、それらが投機的に無効にされたラインに関係しない限り、キャッシュコントローラが追加のフィルリクエストを受理することを可能にする。
同様に、それらが投機的に無効にされたラインを含んでいない限り、追加のプルーブまたは状態変更リクエストが受け入れられる。また、置換を行うために投機的に無効にされたラインを選ばない限り、Ｌ１からＬ２へのコピーバックが受け入れられる。
したがって、追加の比較によりあるタイプの命令を検出し、それらの命令だけが、記憶装置５０２のアドレスレジスタ５０４の値と比較される。
【００４８】
Ｌ１からＬ２へのコピーバックが投機的に無効にされたラインを選択するかどうか検出するために、アドレスコンフリクト検出ハードウェアは、置換のためにどのラインが選択されるかを検出するための追加ロジックを含む。
例えば、ＬＲＵ置換を使用するＮウェイ・セットアソシアティブキャッシュでは、コピーバックは、通常はセット中の最低使用頻度ラインを置換する。
しかしながら、適切なセット中の最低使用頻度ラインが投機的に無効にされたラインである場合、コピーバックは受理されない。
あるいはまた、コピーバックを受理しない代わりにそのコピーバックは受理されるが、投機的に無効にされたラインを置換する代わりに、コピーバックは、投機的に無効にされたラインのＬＲＵ状態を無視して、セット中の別のラインを置換する。
したがって、アドレスコンフリクト検出ハードウェア５００は、投機的に無効にされたラインが、ラインまたはラインを含んでいるセットの置換状態（例えば、ＬＲＵ状態、ＦＩＦＯ等）に依存するコピーバックによって置換されるどうかを決定するロジックを含む。
コピーバックが投機的に無効にされたラインを置換する場合、アドレスコンフリクト検出ハードウェア５００は、イネーブル信号をディアサートするか、または別のラインを置換するコピーバックを行う。
【００４９】
図２に戻り、以上のように、チェックが完了するのにかかるサイクルを待つ代わりに、第１リクエストまたは命令に関連するチェックがまだ完了していない場合、キャッシュコントローラ４１９が、第１リクエストまたは命令に応じて投機的にラインを無効にするように形成される。
キャッシュコントローラは、そのラインが無効であるとマークする（例えば、有効ビットを有効から無効にトグルする）ことによって、投機的にラインを無効にする。
好ましい実施例では、キャッシュコントローラは、いずれかのチェックに失敗した場合にラインが容易に無効にされないように、ラインに格納されたデータに影響を与えることなく、ラインが無効であることを示すことができる。
キャッシュコントローラ４１９はまた、投機的に無効にされた変更されるのを防ぐために、アドレスコンフリクト検出ハードウェア５００のような保護メカニズムを含んでいてもよい。
従って、キャッシュコントローラ４１９は、投機的にラインを無効にすると共に、保護メカニズムを作動させる。
例えば、図３で示す保護メカニズムが作動させることで、投機的に無効にされたラインに対応するアドレスのすべてあるいは一部は、アドレスレジスタ５０４にロードされる。
無効に対応するチェックにおいて失敗した場合、キャッシュコントローラ４１９は、ラインがもう一度有効である（例えば、有効ビットを無効から有効にトグルする。）ことを示すことにより、投機的な無効をリバースする。キャッシュコントローラ４１９はまた、チェックが完了した後、保護メカニズムをシャットオフするように形成される。
【００５０】
既に記載したように、多くの実施例では、キャッシュコントローラ４１９は、ある種の置換手法を使用して、キャッシュ中のラインを置換する。
例えば、キャッシュコントローラはＬＲＵまたはＦＩＦＯの置換手法を使用する。そのような手法を実行するために、キャッシュコントローラは、各ラインまたはライン群のために置換状態情報を保存できる。
ＬＲＵ置換手法を実行する実施例では、この置換状態は、キャッシュの各ライン、またはキャッシュの一部（例えば、セットアソシエイティブキャッシュのセット）の相対的な使用量の状態を示してもよい。
あるいはまた、ＦＩＦＯ置換手法を実行する実施例では、置換状態は、各ラインが、どれくらいの時間、キャッシュまたはそのキャッシュの一部の他のラインと関連のあるキャッシュの一部（例えば、セット）にあったかを示してもよい。
【００５１】
ラインが投機的に無効にされる場合、投機的な無効があたかも投機的でない無効のように、キャッシュまたはキャッシュの一部に対応する置換状態が更新される。
しかしながら、投機的な無効がその後取り消される場合、更新された置換状態情報は、ラインのための適切な置換状態を反映しない可能性がある。
これを補償するために、キャッシュコントローラ４１９は、無効を反映するために置換状態を更新する前に、投機的にラインを無効にする際に先在する置換状態を保存するように形成される。
投機的な無効がその後リバースされる場合、キャッシュコントローラ４１９は、保存された置換状態を元に戻すように形成される。
このように、いくつかの実施例では、キャッシュコントローラ４１９は、投機的な無効を行なう場合に置換状態を変更し保存するように形成される。
【００５２】
図４Ａおよび図４Ｂは、排他キャッシュ中の投機的な無効を行なう方法の実施例の一つを示す。
機能ブロックは、記載された実施例において、ある規則で配列されているが、この配置は単なる例であり、この方法が特定の時間的な順序を要求することを意味しないので、他の実施例が機能ブロックの異なる配置を使用する可能性がある。
フィルリクエストは排他キャッシュコントローラによって受け付けられる（ステップ６０１）。いくつかの実施例では、排他キャッシュは、Ｌ２キャッシュであり、排他キャッシュコントローラは、実際にＬ１キャッシュとＬ２キャッシュの両方を制御する。
排他キャッシュがリクエストを受け付ける前または受け付けた後のある時点では、チェックは、リクエストしているキャッシュのミス、および／または、リクエストに起因する排他キャッシュ中のヒットによって開始される（ステップ６０３）。
【００５３】
ステップ６０１で受け付けられたフィルリクエストが、排他キャッシュでヒットした場合、ステップ６０５に示すように、排他キャッシュは、リクエストしているキャッシュにデータのリクエストされたラインを供給する。
便宜上、リクエストされたラインは「ＬｉｎｅＮ」として示す。
排他性を維持するために、ステップ６０７で示されるように、排他キャッシュコントローラは、ＬｉｎｅＮを無効にすることができる。
しかしながら、ステップ６０３で開始されたチェックが完了する前にこの無効が生じる可能性があるため、キャッシュコントローラは、無効を投機的に行なう。
チェックに失敗した場合にその無効をリバースするために、ステップ６０７で、キャッシュコントローラはまた、無効がその置換状態情報に影響する場合にＬｉｎｅＮに対応する以前の置換状態情報（例えば、ＬＲＵ情報またはＦＩＦＯ情報のような、セットまたはキャッシュ中のどのラインが最初に置換されるかを決定する情報）を保存し、無効を反映するために置換状態情報を更新する。
【００５４】
投機的な無効のための追加要素は、ＬｉｎｅＮを保護する保護メカニズムを作動させる排他キャッシュコントローラを含んでいてもよい。
したがって、他のリクエストを受け付けるために排他キャッシュコントローラを解放すべくＬｉｎｅＮが無効にされている一方、排他キャッシュコントローラは、チェックの完了後までＬｉｎｅＮに潜在的に影響するか依存するリクエストを受け入れることを遅延または拒絶することがある。
このように、ステップ６１１で、新規なリクエストが排他キャッシュに提示され、そのリクエストがＬｉｎｅＮに潜在的に影響するか依存する場合、ステップ６１３で示されるように、キャッシュコントローラはリクエストを受け付けない。例えば、キャッシュコントローラは、ＬｉｎｅＮを上書きするリクエストを受け付けない。
しかしながら、そのリクエストがＬｉｎｅＮに関係がない場合、排他キャッシュはリクエストを受け付けて、ステップ６１７に示すように、それに従って処理することができる。
いくつかの実施例では、排他キャッシュコントローラは、リクエストのタグがＬｉｎｅＮのタグと一致するかどうかチェックすることにより、リクエストが潜在的にＬｉｎｅＮに影響するかどうか決めることができる。
一つの実施例では、コピーバックリクエストが提示される場合、排他キャッシュコントローラは、ＬｉｎｅＮが、現在の置換状態において、コピーバックによって置換されるかどうか決定するロジックをさらに含んでいてもよい。
ＬｉｎｅＮが置換され得る場合、排他キャッシュコントローラは、コピーバックを受け付けない、あるいはコピーバックを受け付けるが、ＬｉｎｅＮの代わりに別のラインを置換することを強制する。
ステップ６０３で開始されたチェックが失敗した場合、排他キャッシュコントローラは、ステップ６２３で無効をリバースするために、回復メカニズムを使用することができる。
例えば、排他キャッシュコントローラは再びラインを有効であるとマークし（例えば、有効ビットを無効から有効にトグルすることによって)、ＬｉｎｅＮに対応する前の無効置換状態情報を回復することができる。
代わりに、ステップ６０３で開始されたチェックをパスした場合、排他キャッシュコントローラは、投機的に無効にされたＬｉｎｅＮに潜在的に影響し得るリクエストの遮断を中止する。
一旦チェックをパスすれば、その無効は投機的でない無効として扱うことができ、したがって、置換状態情報がステップ６０７で保存される場合、一旦チェックが完了すれば、保存された情報はもはや維持されない。
【００５５】
いくつかの実施例では、キャッシュコントローラがステップ６０１で受け付けられたリクエストを完了する前に、ステップ６０３で開始されたチェックのうちのいくつかは完了し、これらのチェックのうちのどれかが失敗した場合、ラインが投機的に無効にされる前に、そのリクエストを取り消すことができる。
この状況で、キャッシュコントローラは、ステップ６０７で示された投機的な無効の実行とは反対に、投機的にラインを無効にしてはならない。
【００５６】
ステップ６０１で受け付けられたフィルリクエストが、排他キャッシュでミスする場合、ステップ６０９で示されるように、リクエストしているキャッシュは、まだそのように実行されていなければ、より低いレベルのキャッシュまたはシステムメモリにフィルリクエストを送ることができる。
多くの実施例では、リクエストしているキャッシュは、フィルリクエストが排他キャッシュでミスする際にシステムメモリのレイテンシを最小限にするために、フィルリクエストを排他キャッシュに送るのと同時に、システムメモリにも送る。
フィルリクエストを送った後に、排他キャッシュは、他のリクエストを受信し、それらに応答することができる。
【００５７】
図５では、キャッシュが排他的、統合的、または排他的でも統合的でもないかどうかにかかわらず、キャッシュで投機的な無効を行なう方法の実施例が提供される。
ステップ７０１で、キャッシュコントローラは、命令またはリクエストを受け付ける。
例えば、受け付けた命令は、フィルリクエスト、コピーバック、プルーブ、状態変更または無効であり得る。
このリクエストを充足するには、結局受け付けられるキャッシュのラインが無効にされることが要求される。
しかしながら、ある種のチェックは、ステップ７０３で示されるように、命令、リクエスト（例えば、より高いレベルのキャッシュのミス）、または無効に通じるイベント（例えば、排他キャッシュのヒット）の存在下で実行され、これらのチェックに失敗した場合、そのリクエストおよび／または無効は、取り消される。
これらのチェックは、完了するまでにいくつかのサイクルを必要とするので、チェックが完了するまで、キャッシュコントローラが新規なリクエストの受け付けを継続するように、キャッシュコントローラは、投機的にラインを無効にする。
したがって、ステップ７０７で、キャッシュコントローラは、ラインの有効ビットをトグルすることによってそのラインを投機的に無効にし、その無効が、無効にされたラインに対応する置換状態情報に影響する場合、前の置換状態情報を保存し、かつ、無効を反映するために置換状態情報を更新する。
【００５８】
キャッシュコントローラは、ステップ７０３で開始されたチェックが完了するまで、投機的に無効にされたラインに影響または依存し得るリクエストを受け付けないことによって、投機的に無効にされたラインが変更されるのを防ぐことができる。
したがって、潜在的に無効にされたラインに関係がある新規なリクエストが示され、チェックが完了していない場合、キャッシュコントローラは、ステップ７１９に示すように、リクエストを受け付けない。
キャッシュコントローラは、投機的に無効にされたラインへ潜在的に関係がないリクエストを、ステップ７１７で受け付けることができる。
チェックをパスする場合、無効はもはや投機的ではないので、キャッシュコントローラは、投機的に無効にされたラインが変更されるのを防ぐことを中止する。
しかしながら、チェックに失敗した場合、キャッシュコントローラは、ステップ７２３で示されるように、それが有効であることを示すために無効にされたラインの有効ビットをトグルし、置換状態情報が保存されている場合には保存された置換状態情報を元に戻すことによって、無効をリバースすることができる。
【００５９】
いくつかの実施例では、キャッシュコントローラが、ステップ７０１で受け付けられたリクエストを完了する前にいずれかのチェックに失敗すると、ラインを投機的に無効にする前に、そのリクエストを取り消すことができる。
この状況で、キャッシュコントローラは、ステップ７０７で示された投機的な無効とは反対に、投機的にラインを無効にしてはならない。
【００６０】
＜コンピュータシステム＞
図６は、バスブリッジ２０２によって様々なシステムコンポーネントにつながれたプロセッサ１０を含むコンピュータシステム２００の一実施例を示すブロック図である。
コンピュータシステムの他の実施例は存在し、また想起し得る。
記載されたシステムでは、メインメモリ２０４は、メモリバス２０６によって、バスブリッジ２０２に接続される。また、グラフィックコントローラ２０８は、ＡＧＰバス２１０によって、バスブリッジ２０２に接続される。ＰＣＩデバイス２１２Ａないし２１２Ｂは、ＰＣＩバス２１４によって、バスブリッジ２０２に接続される。第２バスブリッジ２１６はまた、ＥＩＳＡ／ＩＳＡバス２２０によって、一つ以上のＥＩＳＡあるいはＩＳＡデバイス２１８に電気的なインタフェースを提供するために採用される。
この例において、プロセッサ１０は、ＣＰＵバス２２４によって、バスブリッジ２０２に接続され、またオプションのＬ２キャッシュ２２８に接続される。
いくつかの実施例では、プロセッサ１０は、図示しない統合Ｌ１キャッシュを含んでいてもよい。
【００６１】
バスブリッジ２０２は、プロセッサ１０、メインメモリ２０４、グラフィックコントローラ２０８、およびＰＣＩバス２１４に付けられたデバイス間の、インタフェースを提供する。
オペレーションが、バスブリッジ２０２に接続されたデバイスの一つから受信される場合、バスブリッジ２０２は、オペレーションのターゲットを識別する。
（例えば、特定のデバイスまたはＰＣＩバス２１４の場合は、そのターゲットは、ＰＣＩバス２１４上にある。）
バスブリッジ２０２は、目標のデバイスへオペレーションを送る。
バスブリッジ２０２は、一般的に、オペレーションを、ソースデバイスまたはバスで使用されるプロトコルからターゲットデバイスまたはバスで使用されるプロトコルに翻訳する。
【００６２】
ＰＣＩバス２１４にＩＳＡ／ＥＩＳＡバスへのインタフェースを提供するのに加えて、第２バスブリッジ２１６に、追加の機能を組込むことができる。
第２バスブリッジ２１６から外部の、または第２バスブリッジ２１６に統合された、図示しないＩ／Ｏコントローラはまた、キーボードとマウス２２２、および様々なシリアルとパラレルのポートの動作をサポートするために、コンピュータシステム２００内に含まれていてもよい。
図示しない外部キャッシュユニットはまた、他の実施例においてプロセッサ１０とバスブリッジ２０２の間のＣＰＵバス２２４に接続されていてもよい。
あるいはまた、外部キャッシュは、バスブリッジ２０２に接続されていてもよいし、外部キャッシュのためのキャッシュ制御ロジックは、バスブリッジ２０２に統合されていてもよい。
L２キャッシュ２２８は、プロセッサ１０のバックサイド仕様として示される。
L２キャッシュ２２８は、プロセッサ１０と分離していてもよいし、カートリッジ中でプロセッサ１０と統合されていてもよいし（例えば、スロット１またはスロットＡ）、または、半導体基板上でプロセッサ１０と統合されていてもよい。
【００６３】
メインメモリ２０４は、アプリケーションプログラムが格納されるメモリであって、それからプロセッサ１０が主として実行するメモリである。好ましいメインメモリ２０４は、ＤＲＡＭ（Dynamic Random Access Memory）を含む。
例えば、複数のバンクを有するＳＤＲＡＭ（Synchronous DRAM）またはRambus DRAM（ＲＤＲＡＭ）が適切である。
【００６４】
２１２Ａないし２１２ＢのＰＣＩデバイスは、ネットワークインターフェースカード、ビデオアクセラレータ、オーディオカード、ハードまたはフロッピーディスクドライブ、ドライブコントローラ、ＳＣＳＩ（Small Computer Systems Interface）アダプタ、および電話カードのような、様々な周辺機器を例示したものである。
同様に、ＩＳＡデバイス２１８は、モデム、サウンドカード、そして、ＧＰＩＢ、またはフィールドバスのインターフェースカードのような様々なデータ取得カードのような様々なタイプの周辺機器を例示したものである。
【００６５】
グラフィックコントローラ２０８は、ディスプレイ２２６上のテキストおよびイメージのレンダリングを制御するために提供される。
グラフィックコントローラ２０８は、メインメモリ２０４へ、およびそのメインメモリ２０４から効果的にシフトできる三次元のデータ構造をレンダリングするための当該技術分野において一般的なグラフィックアクセラレータを含む。
したがって、グラフィックコントローラ２０８は、それがバスブリッジ２０２内のターゲットインタフェースへのアクセスをリクエストし、受け取ることができ、そのためメインメモリ２０４にアクセスできるという点でＡＧＰバス２１０のマスターであり得る。
専用のグラフィックスバスは、メインメモリ２０４からのデータの迅速なリトリーブを提供する。
あるオペレーションについては、グラフィックコントローラ２０８は、ＡＧＰバス２１０上でＰＣＩプロトコルトランザクションを生成するようにさらに形成され得る。
バスブリッジ２０２のＡＧＰインタフェースはこのように、ＰＣＩプロトコルターゲットおよびイニシエータトランザクションと同様に、ＡＧＰプロトコルトランザクションをもサポートする機能を含んでいてもよい。
ディスプレイ２２６は、イメージまたはテキストを表示できるすべての電子ディスプレイである。適切なディスプレイ２２６は、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）等を含む。
【００６６】
上述の記載では、例としてＡＧＰ、ＰＣＩおよびＩＳＡまたはＥＩＳＡバスが使用されているが、所望のどのようなバス構造にでも置換可能である。
さらに、コンピュータシステム２００が追加のプロセッサ（例えば、コンピュータシステム２００のオプションのコンポーネントとして示されたプロセッサ１０ａ）を含む多重プロセッシングコンピュータシステムであってもよい。プロセッサ１０ａは、プロセッサ１０と同種のものでもよい。
より詳細には、プロセッサ１０ａは、プロセッサ１０と完全同一のコピーであってもよい。
プロセッサ１０ａは、図６に示すように、独立したバスによってバスブリッジ２０２に接続されていてもよいし、あるいは、ＣＰＵバス２２４をプロセッサ１０と共有していてもよい。
さらに、プロセッサ１０ａは、Ｌ２キャッシュ２２８と類似するオプションのＬ２キャッシュ２２８ａに接続されていてもよい。
【００６７】
＜マルチノード処理システム＞
図７は、コンピュータシステム３００の他の実施例を示す。
コンピュータシステムの他の実施例は存在し、また想起し得る。
図７の具体例では、コンピュータシステム３００は、いくつかの処理ノード３１２Ａ，３１２Ｂ，３１２Ｃ，３１２Ｄを含む。
各処理ノードは、それぞれ処理ノード３１２Ａないし３１２Ｄに含まれた、メモリーコントローラ３１６Ａないし３１６Ｄによって、それぞれメモリ３１４Ａないし３１４Ｄに接続される。
さらに、処理ノード３１２Ａないし３１２Ｄは、処理ノード３１２Ａないし３１２Ｄ間の通信に使用されるインタフェースロジックを含む。
例えば、処理ノード３１２Ａは、処理ノード３１２Ｂと通信するためのインタフェースロジック３１８Ａ、処理ノード３１２Ｃと通信するためのインタフェースロジック３１８Ｂ、および図示しないさらに他の処理ノードと通信するための第三のインタフェースロジック３１８Ｃを含む。
同様に、処理ノード３１２Ｂは、インタフェースロジック３１８Ｄ、３１８Ｅおよび３１８Ｆを含む。処理ノード３１２Ｃは、インタフェースロジック３１８Ｇ、３１８Ｈ、および３１８Ｉを含む。そして処理ノード３１２Ｄは、インタフェースロジック３１８Ｊ、３１８Ｋおよび３１８Ｌを含む。
処理ノード３１２Ｄは、インタフェースロジック３１８Ｌによって多くのＩ／Ｏデバイス（例えば、デイジーチェーン構成中のデバイス３２０Ａないし３２０Ｂ）と通信するように接続される。
他の処理ノードは、同様の方法で、他のＩ／Ｏデバイスと通信できる。
【００６８】
処理ノード３１２Ａないし３１２Ｄは、処理間ノード通信のためのパケットベースのリンクを実現する。
本実施例では、リンクは一方向のラインのセットとして実現される（例えば、ライン３２４Ａは、処理ノード３１２Ａから処理ノード３１２Ｂにパケットを送信するために使用され、ライン３２４Ｂは、処理ノード３１２Ｂから処理ノード３１２Ａにパケットを送信するために使用される）。
ライン３２４Ｃないし３２４Ｈの他のセットは、図７に示すような他の処理ノード間のパケットを送信するために使用される。
一般に、ライン３２４の各セットは、一つ以上のデータライン、データラインに対応する一つ以上のクロックライン、および伝達されているパケットのタイプを示す一つ以上の制御ラインを含む。
リンクは、処理ノード間の通信のキャッシュコヒーレント方式において、または処理ノードとＩ／Ｏデバイス（またはＰＣＩバスかＩＳＡバスのような、従来の構造のＩ／Ｏバスへのバスブリッジ）の間の通信の非コヒーレント方式において動作する。
さらにリンクは、示されるようなＩ／Ｏデバイス間のデイジーチェーン構造を使用して、非コヒーレント方式で動作してもよい。
ある処理ノードから別のノードに送信されるパケットが、一つ以上の中間ノードを介して通過してもよい。
例えば、処理ノード３１２Ａから処理ノード３１２Ｄに送信されたパケットは、図７に示すように、処理ノード３１２Ｂまたは処理ノード３１２Ｃのいずれかを通過することができる。他のどのような適切なルーティングのアルゴリズムも使用することができる。
コンピュータシステム３００の他の実施例は、図７で示す実施例において、より多くの、またはより少数の処理ノードを含んでいてもよい。
【００６９】
パケットは一般的に、ノード間のライン３２４上の一以上のビットタイミングとして送信される。ビットタイミングは、対応するクロックライン上のクロック信号の立ち上がりエッジまたは立ち下がりエッジである。
パケットは、トランザクションを開始するためのコマンドパケット、キャッシュコヒーレンシを維持するためのプルーブパケット、およびプルーブとコマンドに応答する応答パケット、を含んでいてもよい。
【００７０】
処理ノード３１２Ａないし３１２Ｄは、メモリーコントローラとインタフェースロジックに加えて、一つ以上のプロセッサを含んでいてもよい。
広義には、処理ノードは少なくとも1つのプロセッサを含んでおり、必要に応じてメモリおよび他のロジックと通信するためのメモリコントローラを含んでいてもよい。
より詳しくは、各処理ノード３１２Ａないし３１２Ｄは、プロセッサ１０の一つ以上のコピーを含んでいてもよい。
外部インタフェースユニット１８は、メモリコントローラ３１６とともに、ノード内にインタフェースロジック３１８を含んでいてもよい。
【００７１】
メモリ３１４Ａないし３１４Ｄは、適切などのようなメモリデバイスを含んでいてもよい。例えば、メモリ３１４Ａないし３１４Ｄは、一つ以上のラムバスＤＲＡＭ（ＲＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、スタティックＲＡＭ等を含んでいてもよい。
コンピュータシステム３００のアドレス空間は、メモリ３１４Ａないし３１４Ｄ間で分割される。
各処理ノード３１２Ａないし３１２Ｄは、どのアドレスがメモリ３１４Ａないし３１４Ｄのどのメモリにマッピングされるか、つまり、特別のアドレス用のメモリーリクエストがどの処理ノード３１２Ａないし３１２Ｄに送られるべきか、を決定するために使用されるメモリーマップを含んでいる。
一つの実施例では、コンピュータシステム３００内のアドレスのコヒーレントポイントは、そのアドレスに対応するバイトを格納するメモリに接続されたメモリコントローラ３１６Ａないし３１６Ｄである。
言いかえれば、メモリコントローラ３１６Ａないし３１６Ｄは、対応するメモリ３１４Ａないし３１４Ｄへの各メモリアクセスが、キャッシュコヒーレントな方法で起こることを保証する。
メモリコントローラ３１６Ａないし３１６Ｄは、メモリ３１４Ａないし３１４Ｄに接続するための制御回路を含んでいてもよい。
さらに、メモリコントローラ３１６Ａないし３１６Ｄは、メモリリクエストをキューするためのリクエストキューを含んでいてもよい。
【００７２】
一般に、インタフェースロジック３１８Ａないし３１８Ｌは、リンクからパケットを受け取るために、およびリンクで送信されるパケットをバッファするために、様々なバッファを含む。
コンピュータシステム３００は、パケットを送信するのに適切などのようなフロー制御メカニズムも使用することができる。
例えば、一つの実施例では、各インタフェースロジック３１８は、そのインタフェースロジックが接続されるリンクの他端におけるレシーバ内の各タイプのバッファの数（カウント）を格納する。
受信インタフェースロジックが、パケットを格納するためのフリーバッファを有しないとすれば、インタフェースロジックはパケットを送信しない。
パケットを前方に送ることによって受信バッファが解放されるとともに、受信インタフェースロジックは、バッファが解放されたことを示すため、送信インタフェースロジックにメッセージを送信する。
このようなメカニズムは、「クーポンベースの」システムとして呼ばれる。
【００７３】
Ｉ／Ｏデバイス３２０Ａおよび３２０Ｂは、適切なＩ／Ｏデバイスであればどのようなものであってもよい。
例えば、Ｉ／Ｏデバイス３２０Ａおよび３２０Ｂは、そのデバイスが接続され得る他のコンピュータシステムと通信するためのデバイス（例えば、ネットワークインターフェースカードまたはモデム）を含んでいてもよい。
さらに、Ｉ／Ｏデバイス３２０Ａおよび３２０Ｂは、ビデオアクセラレータ、オーディオカード、ハードまたはフロッピーディスクドライブ、ドライブコントローラ、ＳＣＳＩ（スカジー）アダプタ、電話カード、サウンドカード、ＧＰＩＢまたはフィールドバス・インターフェースカードのような様々なデータ取得カードを含んでいてもよい。
ここでは、「Ｉ／Ｏデバイス」という用語は、「周辺機器」という用語と同じ意味である。
【００７４】
以上の開示が完全に認識されれば、多数の変形例や変更例は当業者に明白になる。このような変形例および変更例をすべて包含するように、請求項は解釈される。
【産業上の利用可能性】
【００７５】
この発明は、キャッシュに、産業上利用することができる。
【図面の簡単な説明】
【００７６】
【図１Ａ】本発明の一実施例の、統合キャッシュの関係を示すベン図。
【図１Ｂ】本発明の一実施例の、排他キャッシュの関係を示すベン図。
【図２】本発明のキャッシュサブシステムの一実施例のブロック図。
【図３】図２で示されるようなキャッシュサブシステムと共に使用されるアドレスコンフリクトを検出するハードウェアの一実施例を示す図。
【図４Ａ】本発明の一実施例による排他的なキャッシュでどのように無効が実行されるかを示すフローチャート。
【図４Ｂ】図４Ａのフローチャートの続きを示す図。
【図５】キャッシュが統合的であるか排他的であるか、またはそれ以外であるかどうかにかかわらず、投機的にキャッシュ中のラインを無効にする方法の一実施例を示す図。
【図６】本発明のコンピュータシステムの一実施例を示すブロック図。
【図７】本発明のマルチノード処理システムの一実施例を示す図。
【図１Ａ】
2004529435.tif 000003
【図１Ｂ】
2004529435.tif 000004
【図２】
2004529435.tif 000005
【図３】
2004529435.tif 000006
【図４Ａ】
2004529435.tif 000007
【図４Ｂ】
2004529435.tif 000008
【図５】
2004529435.tif 000009
【図６】
2004529435.tif 000010
【図７】
2004529435.tif 000011
【国際公開パンフレット】
2004529435.tif 000012
2004529435.tif 000013
2004529435.tif 000014
2004529435.tif 000015
2004529435.tif 000016
2004529435.tif 000017
2004529435.tif 000018
2004529435.tif 000019
2004529435.tif 000020
2004529435.tif 000021
2004529435.tif 000022
2004529435.tif 000023
2004529435.tif 000024
2004529435.tif 000025
2004529435.tif 000026
2004529435.tif 000027
2004529435.tif 000028
2004529435.tif 000029
2004529435.tif 000030
2004529435.tif 000031
2004529435.tif 000032
2004529435.tif 000033
2004529435.tif 000034
2004529435.tif 000035
2004529435.tif 000036
2004529435.tif 000037
【国際公開パンフレット（コレクトバージョン）】
2004529435.tif 000038
【手続補正書】
【提出日】平成15年7月9日(2003.7.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
キャッシュ（４２３）中のラインを投機的に無効にする方法であって、
リクエストを受け付けるステップと、
前記無効が誤っているかどうか決定するチェックを開始するステップと、
前記受け付けに応じて、前記ラインを投機的に無効にするステップと、
前記チェックの一つが前記無効は誤っていると決定することに応じて、前記ラインが有効であると示すことによって、前記投機的な無効をリバースするステップと、
を含み、
前記投機的に無効にするステップは、前記ラインが無効であることを示すステップと、前記チェックが完了するまで、前記ラインがその後置換されるのを防ぐステップとを含む、方法。
【請求項２】
前記投機的に無効にするステップは、前記ラインに関連する有効ビットをトグルするステップを含む、
請求項１記載の方法。
【請求項３】
前記無効が誤っているかどうかを決定するステップは、所定のサイクル数が必要であり、投機的な無効は、前記サイクル数の後、投機的ではなくなる、
請求項１または２記載の方法。
【請求項４】
前記所定のサイクル数の間、前記投機的に無効にされた第１キャッシュラインを変更、または前記投機的に無効にされた第１キャッシュラインに依存する追加のリクエストの受け取りをブロックするステップを含む、
請求項３記載の方法。
【請求項５】
複数のキャッシュライン記憶領域を有するキャッシュ（４２３）と、
第１リクエストを受け付けるために接続されており、前記第１リクエストの受け付けに応答して、第１キャッシュライン記憶領域中の第１キャッシュラインを投機的に無効にするように形成され、さらに、前記第１キャッシュラインを投機的に無効にすることに応答して、前記第１キャッシュラインの無効が投機的でなくなるまで、前記第１キャッシュラインが置換されることを防ぐように形成されるキャッシュコントローラ（４１９）と、
前記第１リクエストに対応する少なくとも一つのチェックを実行するように形成されるエラー検出ユニット（６０３）とを有しており、
前記チェックが実行され、エラーを検出しない場合、前記第１キャッシュラインの無効は投機的でなくなり、
前記エラーを検出するためには、所定のサイクル数が必要である、
キャッシュサブシステム。
【請求項６】
前記キャッシュコントローラ（４１９）は、前記第１キャッシュラインに関連する有効ビットをトグルすることによって、前記第１キャッシュラインを投機的に無効にするように形成される、
請求項５記載のキャッシュサブシステム。
【請求項７】
前記キャッシュコントローラ（４１９）はさらに、前記第１キャッシュラインに関連する前記有効ビットをトグルすることにより、前記投機的な実行をリバースするように形成される、
請求項６記載のキャッシュサブシステム。
【請求項８】
前記投機的な無効コントローラ（５０６）はさらに、前記キャッシュコントローラ（４１９）が前記第１キャッシュラインを投機的に無効にするのに応答して、前記所定のサイクル数の間、前記第１キャッシュラインが置換されることを防ぐように形成され、
前記投機的な無効は、前記所定のサイクル数の後に投機的でなくなる、
請求項５ないし７のいずれかの項記載のキャッシュサブシステム。
【請求項９】
前記投機的な無効コントローラ（５０６）はさらに、前記所定のサイクル数の間、前記キャッシュコントローラ（４１９）が、投機的に無効にされた前記第１キャッシュラインを変更する、またはそれに依存する追加のリクエストを受け付けるのを防ぐように形成される、
請求項８記載のキャッシュサブシステム。
【請求項１０】
前記投機的な無効コントローラ（５０６）は、前記キャッシュコントローラ（４１９）が前記第１キャッシュラインを投機的に無効にするのに応答して、レジスタ（５０４）に前記第１キャッシュラインのタグの最初の部分をロードするように形成される、
請求項８または９記載のキャッシュサブシステム。
【国際調査報告】
2004529435.tif 000039
2004529435.tif 000040