(57)【要約】【課題】マルチプロセッサ・データ処理システムに関し、特にキャッシュ中のラインの様々なコヒーレンス状態の様々なディレクトリ要求を利用してメモリ・サブシステムの性能を改善したディレクトリ・アーキテクチャを提供する。【解決手段】多数のノードを伴い、各ノードが複数のプロセッサを含み、各プロセッサが関連キャッシュを有する、分散共有メモリ・マルチプロセッサ・システムのための分割疎ディレクトリを提供する。分割疎ディレクトリは、コヒーレンス制御装置、一時的状態バッファ及び外部ディレクトリを含むメモリ・サブシステム内に存在する。分割疎ディレクトリはノード中のキャッシュ・ラインに関する情報を保存するが、その際一時的状態バッファは遷移キャッシュ・ラインに関する情報を保持し、外部ディレクトリは非遷移キャッシュ・ラインに関する状態情報を保持する。【選択図】図４
2006277762.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサと、
前記複数のプロセッサのそれぞれに対応して設けられ、各々複数のキャッシュ・ライン・エントリを保存するように構築された複数のキャッシュと、
前記複数のキャッシュ中のキャッシュ・ライン・エントリ状態を把握するための状態情報を保持するディレクトリと、
前記ディレクトリに含まれる前記状態情報の読み出し及び書き込みを行う制御装置と、を備え、
前記ディレクトリの第１の部分は、前記複数のキャッシュ・ライン・エントリの第１サブセットに関する一時的状態情報を保持し、
前記ディレクトリの第２部分が前記複数のキャッシュ・ライン・エントリの第２サブセットに関する非一次的状態を保持することを特徴とする、データ処理システム。
【請求項２】
データ処理システムであって、
メモリ・バスに結合された複数のプロセッサを有し、各プロセッサが複数のキャッシュ・ライン・エントリを保存するキャッシュを有するノードと、
前記メモリ・バスに結合するバス・インタフェース素子と、
前記キャッシュ中のキャッシュ・ライン・エントリの一時的状態情報を保持する第１の部分と、非一次的状態情報を保持する第２の部分とを有するディレクトリと、
前記ディレクトリから状態情報を読み出して前記状態情報を更新する、前記バス・インタフェース素子と前記ディレクトリに結合されたコヒーレンス制御装置とを備えるデータ処理システム。
【請求項３】
メモリ・バスに結合され、各々がキャッシュ・メモリを有する複数のプロセッサを備えたノードを含むデータ処理システムにおけるキャッシュ・コヒーレンス維持方法において、
キャッシュされたメモリ・ロケーションに関する情報をディレクトリに保存する際に、前記ディレクトリの第１部分に第１のキャッシュ・ライン・エントリに関する遷移状態情報を保持し、前記ディレクトリの第２部分に第２のキャッシュ・ライン・エントリに関する非遷移状態情報を保持することを特徴とする、キャッシュ・コヒーレンス維持方法。
【請求項４】
プロセッサと、
前記プロセッサに対応して設けられ、複数のキャッシュ・ライン・エントリを保存するように構築されたキャッシュと、
前記キャッシュに保存されたキャッシュ・ライン・エントリの状態を示す状態情報を保持するディレクトリと、
前記ディレクトリに含まれる前記状態情報の読み出し及び書き込みを行う制御装置と、を備え、
前記ディレクトリの第１部分は、前記複数のキャッシュ・ライン・エントリの第１サブセットに関する一時的状態情報を保持し、
前記ディレクトリの第２部分が前記複数のキャッシュ・ライン・エントリの第２サブセットに関する非一次的状態を保持することを特徴とする、データ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチプロセッサ・データ処理システムに関し、特にマルチバス共有メモリ・システムを伴う複数のマルチプロセッサのキャッシュ・コヒーレンスに関する。
【０００２】
コンピュータ・システムの中には、１つのプログラムに対して並行して動作し、プログラムの実行速度を上げることのできる多数のプロセッサによって構築されているものがある。こうしたマルチプロセッサ・システムのアーキテクチャは、多数のプロセッサ間の通信に使用される機構によって分類される。共有メモリ・アーキテクチャでは、すべてのプロセッサは１つの大きなメモリにアクセスし、この共有メモリの読み出し及び書き込みを行うことによって互いに通信する。
【０００３】
なお、本出願は、１９９８年５月８日出願の米国仮出願第６０／０８４，７９５号の利益を請求する。
本出願は、１９９８年３月１２日出願の「パイプライン化されたスヌーピープロトコルを有する相互接続用マルチプロセッサノードのためのキャッシュコヒーレンスユニット」と題された同時係属中の米国特許出願第０９／０４１，５６８号、１９９８年１月７日出願の「統合されたメッセージパッシングサポートを備える分散共有メモリマルチプロセッサのためのメモリ保護メカニズム」と題された同時係属中の米国特許出願第０９／００３，７７１号及び、１９９８年１月７日出願の「分散共有メモリマルチプロセッサシステムのための統合化されたメッセージパッシングとメモリ保護を備えるキャッシュコヒーレンスユニット」と題された同時係属中の米国特許出願第０９／００３，７２１号に関連するが、これらは引用によって本出願の記載に援用する。
【背景技術】
【０００４】
コンピュータ・システム・ノードは、プロセッサ・サブシステムとメモリ・サブシステムに分割される。メモリ・サブシステムには主ダイナミック・ランダムアクセス・メモリ（ＤＲＡＭ）が含まれ、いくつかの接続されたプロセッサからの要求に応答してメモリからデータを提供する。普通、メモリ・サブシステムでデータにアクセスするために費やされる時間の量はプロセッサの速度と比較してかなり長いので、プロセッサには動作を改善するためキャッシュを備えることが多い。キャッシュはプロセッサと主メモリの間に接続された小さなメモリで、主メモリのロケーションの最近使用されたデータを保存する。転送によってキャッシュを出入りできるデータの最小単位を「ライン」と呼ぶ。
【０００５】
プロセッサ・サブシステムにはプロセッサと１つかそれ以上のキャッシュが含まれる。キャッシュは主メモリ・サブシステムよりかなり速いアクセス時間を有するが普通かなり小さい。小さなキャッシュは主メモリにあるすべてのデータを保持することができないので、現在保持しているデータのアドレス（タグと呼ばれる）と値の両方を保存しなければならない。特定のラインを要求する場合、プロセッサはまずそのアドレスを現在キャッシュにある各タグと突き合わせ、そのラインがキャッシュにあるかを調べる。一致がない場合、メモリ・サブシステムは要求を主メモリに伝える。
【０００６】
すべてのキャッシュ・スキームは主メモリを物理的に連続したセグメントに分割する。キャッシュは普通、合計がセグメントと同じサイズになる一連のラインとして編成される。タグは、どのセグメントが現在キャッシュを占めているかを識別するために使用される。要求されたアドレスを有するラインがキャッシュに含まれている場合、そのラインのデータがプロセッサに転送される。そのラインがキャッシュにない場合、そのラインを含む主メモリのセグメントがキャッシュにフェッチされ、そのラインがプロセッサに転送される。
【０００７】
直接マップ・キャッシュ・メモリでは、セグメントはキャッシュ・ラインという形を取り、そのライン番号は主メモリ・アドレスから容易に計算できる。
連想キャッシュは、任意のセグメントのラインが任意のキャッシュ・ラインにロードされる点で直接マップ・キャッシュと異なっている。キャッシュ・ラインはデータ自身とさらにセグメント番号を記憶する必要がある。キャッシュの探索を可能にするため、連想キャッシュには、キャッシュのライン毎のセグメント番号に対するセグメント番号アドレスを同時に検査する回路が含まれている。この追加回路のため、連想キャッシュはより高価になる。
【０００８】
セット連想マッピングは、直接マッピングと連想キャッシュ両方のアーキテクチャを結合する。セット連想キャッシュは、各々が多数のラインを含む多数のセットとして編成される。セット連想マッピングでは、キャッシュ・セットはアドレス・セグメント番号によって決定されるが、セット内のラインはアドレス・セグメント番号によって決定されない。通常、セット連想キャッシュは双方向であり、すなわちキャッシュに２つのセットが存在するので、要求されたメモリ・ラインを提供する際直接マップ・キャッシュに対してキャッシュ・ヒット率が大きく改善される。
【０００９】
図１は、メモリ中のデータを新しく要求するステップ１０２で開始される、通常の先行技術キャッシュ・メモリ・アクセス・アルゴリズム１００のフローチャートを示す。ステップ１０４では、要求されたデータ・アドレスがキャッシュ・タグと比較される。ステップ１０６は要求されたデータがキャッシュにあるか否かを判定する。ステップ１０６で、データの有効なコピーがキャッシュにない場合、ステップ１０８でメモリ・サブシステムは要求されたデータを主メモリからキャッシュ・メモリにフェッチする。要求されたデータがキャッシュにある場合、ステップ１１０でメモリ・サブシステムは要求を出したプロセッサにデータを転送する。データがプロセッサに転送された後、メモリ・アクセス・アルゴリズムはステップ１０２に戻り、次のメモリ要求を待つ。
【００１０】
共有メモリマルチプロセッサ・システムでは、各プロセッサは通常固有のキャッシュを有するので、システムは多数のキャッシュを有することになる。各キャッシュは所定のデータ項目のコピーを保持できるので、すべてのキャッシュの状態がプロセッサの１つによって書かれた最新のコピーと一貫性のある最新のものであるように維持することが重要である。キャッシュまたは主メモリから、メモリ・サブシステムの動作を管理する一組の規則であるプロセッサのメモリ・モデルの規定通りに、正しい値を返すことはメモリ・サブシステムの責任である。これはキャッシュ・コヒーレンス・プロトコルの使用を通じて達成される。
【００１１】
従って、主メモリに加えて、メモリ・サブシステムには、システムのキャッシュ・コヒーレンスを維持するためにキャッシュ・コヒーレンス・プロトコルが使用する制御情報を含むキャッシュ・コヒーレンス・ディレクトリが含まれる。従来のディレクトリは、メモリ・ロケーション・データがシステムのどこかのキャッシュに存在するか否かを示す状態情報を伴う各メモリ・ロケーションのエントリを有する。主メモリ・ラインが存在するノードはそのラインのホーム・ノードと呼ばれる。ディレクトリが存在するノードはローカル・ノードと呼ばれ、他のノードはリモート・ノードと呼ばれる。コヒーレンス・プロトコルは各キャッシュ・ラインの状態を把握し、データの最新のコピーがプロセッサに与えられることを保証する。また、このプロトコルは、要求に応答してなされるすべての遷移とトランザクションを指定する。キャッシュ・ライン上で行われるすべての処理はディレクトリに保存された状態に反映される。一般的なスキームは３つの永続状態を使用してこれを達成する。「無効」状態は、ラインがどこにもキャッシュされず主メモリが唯一のコピーである場合に存在する。「共有」状態は、リモート・ノード（プロセッサのグループ）がラインの有効なコピーを有する場合に存在する。これは「グローバル共有状態」、すなわちローカル・ノードの何れかのキャッシュまたは少なくとも１つのリモート・キャッシュがラインの有効なコピーを有するグローバル・キャッシュ・コヒーレンス状態と混同してはならない。こうした有効なラインは読み取り専用であり、主メモリのコピーと同一である。「ダーティ」状態は、ラインがリモート・ノードの１つのキャッシュだけで有効な場合に存在する。そのコピーがそのプロセッサによって修正され、主メモリが古いデータを含んでいることがある。
【００１２】
図２は、キャッシュ・コヒーレンス・ディレクトリを使用するメモリ・アクセス・アルゴリズム２００のフローチャートを示す。ステップ２０２で、メモリ中のデータの新しい要求によってアルゴリズムが開始される。ステップ２０４では、アルゴリズムは要求されたデータ・アドレスをキャッシュ・コヒーレンス・ディレクトリ中のディレクトリ・タグと比較する。
【００１３】
ステップ２０６では、アルゴリズムはキャッシュ・コヒーレンス・ディレクトリから要求されたデータの状態を判定する。ステップ２０６で状態が「無効」である（すなわち、キャッシュにデータの有効なコピーがない）場合、ステップ２０８でアルゴリズムは要求されたデータを主メモリまたはローカル・キャッシュからキャッシュ・メモリにフェッチする。ステップ２０６で状態が「共有」である（すなわち、要求されたデータがリモート・ノードのキャッシュにある）場合、ステップ２１２でアルゴリズムはデータをメモリからフェッチし、要求が「保存」である場合、キャッシュされたコピーを無効にする。ステップ２０６で状態が「ダーティ」である（すなわち、データの最新バージョンが１つのキャッシュでだけ有効である）場合、ステップ２１０でアルゴリズムは要求されたデータをキャッシュからフェッチする。
【００１４】
データの有効なコピーがフェッチされると、ステップ２１４でアルゴリズムはデータを要求を出したプロセッサに転送する。データがプロセッサに転送された後、メモリ・アクセス・アルゴリズムはステップ２０２に戻り、次のメモリ要求を待つ。
【００１５】
コヒーレンス・プロトコルは、ラインが遷移中であることを示すため他の遷移状態を使用することがある。十分な時間を与えれば、こうした遷移状態は３つの永続状態の１つに復帰する。
【００１６】
キャッシュ・コヒーレンス・プロトコルは通常有限状態マシンによって実現されるが、そこではデータの最新の値がどこに存在するかを状態が決定する。状態値はメモリ中のすべてのラインに明示的または暗示的に関連しなければならない。通常、ある状態情報を各キャッシュのキャッシュ・タグに追加することによって明示的関連付けがなされる。キャッシュされていないラインについては、状態値がシステム中のどこにもタグの一致がないということを暗示しており、最新の値は主メモリにあることが分かる。
【００１７】
プロセッサの要求がある毎に、メモリ・サブシステムはシステムのすべてのキャッシュのすべてのキャッシュ・タグを調べなければならない。これを行う２つの方法が存在する。「スヌーピー・プロトコル」と呼ばれることもある第１の方法では、各キャッシュはすべての要求を「のぞき回り(snoop) 」、データの最新のコピーを有している場合メモリ・サブシステムに信号を送る。「ディレクトリ・ベース・キャッシュ・コヒーレンス・プロトコル」と呼ばれることもある第２の方法では、メモリ・サブシステムは各キャッシュのタグのコピーを保持し、最新のコピーのロケーションを発見することができる。
【００１８】
キャッシュ・コヒーレンス不均一メモリ・アーキテクチャ（ｃｃ−ＮＵＭＡ）マシンでは、いくつかのメモリ・サブシステムが互いにリンクされ、キャッシュ・コヒーレンス・プロトコルを使用してメモリ・サブシステム間の正しいメモリ・モデルを強化し、単一共有メモリ・システムを形成する。すなわち、マシンはメモリ・サブシステムの追加によって拡張され、メモリへの通信経路の帯域幅が拡大する。同様に、キャッシュ・コヒーレンス・プロトコルもディレクトリ・ベースにすることでスケーラブルなものにすることができる。メモリ・サブシステムを追加すればするほど、ディレクトリの数も多くなる。ディレクトリはシステムのノード間で分散される。各ディレクトリはすべてのキャッシュ・ラインの状態を追跡する。従って、ディレクトリ・サイズはキャッシュの合計サイズに比例し、ディレクトリはディレクトリ・エントリのセット連想キャッシュとして編成される。
【００１９】
直接マッピングは常にセグメントを同じ位置に置くので、キャッシュが一杯の時どのラインを置換するかという問題は回避される。しかし、完全連想及びセット連想キャッシュ・マッピング・スキームは、キャッシュのどのセグメントを新たに要求されたセグメントで置換するかを決定する置換プロトコルが必要である。最も一般的なプロトコルは「最低使用頻度」（ＬＲＵ）プロトコルであるが、これは最も長い時間使用されなかったセグメントを置換する。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
図３は、バス３１８によって主ＤＲＡＭメモリ３２２のメモリ制御装置３２０に接続されたそれぞれのローカル・キャッシュ３１０、３１２、３１４及び３１６を有する多数のＣＰＵ３０２、３０４、３０６及び３０８を含む従来技術システム３００を示す。この例の疎でないディレクトリでは、主メモリ３２２は、各メモリ・ラインのロケーションについて、ディレクトリ３２４のエントリのために確保された空間を有する。有効なディレクトリ・エントリの数を決定するキャッシュされたラインの合計数は普通主メモリのラインの合計数よりかなり少ないため、これはメモリ空間の浪費である。ディレクトリ３２４がすべてのコヒーレンス状態を保持するために同じメモリ３２２が使用され、短期間の遷移状態にあるライン専用のディレクトリが利用できるより高速で小さなメモリがないため、これはメモリ帯域幅の浪費でもある。
【００２１】
従来技術のキャッシュ・コヒーレンス・プロトコルは、ディレクトリ構造が遷移ライン状態と非遷移ライン状態を区別しないという欠点がある。普通、遷移状態と非遷移状態の間の遷移は１つだけだが、遷移状態間に多数の遷移があり得る。すなわち、ラインが遷移する時多数の状態変化が発生するため追加のディレクトリ帯域幅が必要になる。
【００２２】
従って、必要なものは、キャッシュ中のラインの様々なコヒーレンス状態の様々なディレクトリ要求を利用してメモリ・サブシステムの性能を改善することのできる最適なディレクトリ・アーキテクチャを提供するキャッシュ・コヒーレンス・プロトコルである。本発明はそれを提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明には、多数のキャッシュ・ライン・エントリを保存するキャッシュに接続された少なくとも１つのプロセッサを各々有する多数のマルチプロセッサ・ノード、コヒーレンス制御装置及び、キャッシュ中のキャッシュ・ライン状態を把握するディレクトリが含まれる。このディレクトリには、キャッシュのラインの第１サブセットに関する一時的状態情報を保持する第１部分と、キャッシュのラインの第２サブセットに関する非一時的状態情報を保持する第２部分とが含まれる。
【００２４】
本発明は、キャッシュ・コヒーレンス状態を保持するために必要な外部記憶装置の量を減少させる。ラインが遷移状態にある時間の量は非常に短く、ある時間に遷移状態にあるラインはごく少数なので、本発明は一時的状態バッファのサイズも減少させる。さらに、本発明は、多数の遷移状態を通じて、遷移のための外部ディレクトリへのアクセスを除去し、コヒーレンス・プロトコルの総合的な処理能力を増大する。
【発明の効果】
【００２５】
本発明によれば、キャッシュ・コヒーレンス状態を保持するために必要な外部記憶装置の量を減少させる。ラインが遷移状態にある時間の量は非常に短く、ある時間に遷移状態にあるラインはごく少数なので、本発明は一時的状態バッファのサイズも減少させる。さらに、本発明は、多数の遷移状態を通じて、遷移のための外部ディレクトリへのアクセスを除去し、コヒーレンス・プロトコルの総合的な処理能力を増大する。
【００２６】
ここで説明した実施形態の例は例示を目的とし、制限することを企図するものではない。従って、当業技術分野に熟練した者は、他の実施形態が請求項の範囲と精神から離れることなく実行されることが認識されるだろう。
【発明を実施するための最良の形態】
【００２７】
本発明のこれらと他の利点は、当業技術分野に熟練した者には以下の詳細な説明と添付の図面から明らかになるだろう。
本発明は、ディレクトリ・ベース・キャッシュ・コヒーレンス・プロトコルにおいてキャッシュ・コヒーレンス状態情報を使用する。すなわち本発明には、永続状態を保持する外部ランダムアクセス・メモリ（ＲＡＭ）と、遷移状態を保持する内部バッファとが含まれる。従って、バッファが、キャッシュ・コヒーレンス状態情報に加えて状態とデータ値の両方を保存する従来技術のシステムに対して本発明は有利である。このバッファは普通、遷移によってメモリを出入りするラインのための内部完全連想キャッシュ拡張である。また本発明によって、多くの状態遷移が内部バッファの中で完全になされるようになるため、外部ディレクトリの必要な帯域幅が減少し、総合的な処理能力が増大する。従来技術の分割遷移システムは、何らかの状態更新がある度に外部ディレクトリＲＡＭに対して読み出しサイクルと書き込みサイクルを行わなければならない。
【００２８】
図４は、多数の接続されたノード４０２、．．．、４０８及び４１０を備えるｃｃＮＵＭＡシステム４００の概要を示す。各ノードには、ノード４１０について図示するように、１つのメモリ・サブシステム４４０に接続されたそれぞれのキャッシュ４２２、４２４、．．．、及び４３０を有するいくつかの数のプロセッサ４１２、４１４、．．．、及び４２０が含まれる。メモリ・サブシステム４４０には、外部ディレクトリ４６０、主メモリ４９０及び、コヒーレンス制御装置４５０と一時的状態バッファ４７０を含むコヒーレンス制御チップ４８０が含まれる。コヒーレンス制御装置４５０は、外部ディレクトリ４６０と一時的状態バッファ４７０に含まれる状態情報を読み出し及び書き込みを行う。
【００２９】
外部ディレクトリ４６０は、普通既製のＲＡＭを使用して実現される。一度に実行される「読み出し」または「書き込み」は１つだけだが、読み出しと書き込みをパイプラインすることができ、読み出しまたは書き込みを完了するには普通多数のシステム・サイクルを要する。これは普通セット連想または直接マップ・キャッシュとして実現される。セット連想の場合、各セットは、コヒーレンス制御装置４５０によって使用されるタグ、状態及び他の情報を各々含む多数のエントリを備えている。通常、「最低使用頻度」（ＬＲＵ）フィールド等の、コヒーレンス制御装置４５０によるエントリの割り当て及び割り当て解除を可能にする少量の他の情報も存在する。コヒーレンス制御装置４５０は、ＲＡＭに対する基本的な読み出し及び書き込み操作を行うことによって外部ディレクトリ４６０を管理する。これは既製のＲＡＭであるので、その動作は周知でありここで詳細には説明しない。
【００３０】
一時的状態バッファ４７０は、コヒーレンス制御装置４５０によって使用されるタグ、状態及びその他の情報を各々含む多数のエントリを含んでいる。一時的状態バッファ４７０で行われる操作は、エントリの割り当て、エントリの割り当て解除及びエントリの更新である。さらに、一時的状態バッファ４７０は、すべてのエントリが割り当てられたことをコヒーレンス制御装置４５０に示す出力を有する。これらの操作も一時的状態バッファ４７０で同時に行われる。
【００３１】
割り当てには未使用エントリを発見することが含まれる。未使用エントリは、各エントリの明示的ビットを有するか、またはエントリの状態を「無効」に設定するかの何れかによって示される。未使用エントリは任意に選択されるが、１つの簡単な方法は優先順位デコーダ（図示せず）の使用によるものである。割り当ては、状態を「有効」値として書き込み、エントリのすべてのフィールドを書き込むことによって行われる。その後一時的状態バッファ４７０はコヒーレンス制御装置４５０に割り当てされたエントリの数を戻す。
【００３２】
割り当て解除は、エントリか、または連想ルックアップかの何れかによってなされる。エントリによってなされる場合、コヒーレンス制御装置４５０は割り当て解除すべきエントリの数を提供する。連想ルックアップによってなされる場合、一時的状態バッファ４７０はアドレスを一時的状態バッファ４７０中のすべてのタグと比較し、どのエントリを割り当て解除すべきかを決定する。割り当て解除は、明示的ビットを「無効」として設定するか、または状態を「無効」状態として設定するかの何れかによってなされる。コヒーレンス制御装置４５０は、一時的状態バッファ４７０中の有効なエントリを更新することができる。それはまず、明示的エントリ番号を使用するか、または連想ルックアップを使用するかの何れかによってどのエントリを更新すべきかを決定する。次に一時的状態バッファ４７０は、コヒーレンス制御装置４５０によって指定された、タグ・フィールドでなく状態フィールドを含む、何らかのフィールドの書き込みを行う。
【００３３】
図５は、一時的状態バッファ４７０を使用するローカル読み出し操作５００のフローチャートである。このアルゴリズムは、ステップ５０２でプロセッサ４１２が、ローカル・ノード４１０中のロケーションを参照するアドレスによるロード命令を実行することで開始される。ステップ５０４では、プロセッサ４１２がまずこの要求をキャッシュ４２２に伝え、ステップ５０６で、ラインの有効なコピーを有するか否かが検査される。有効なコピーを有する場合、ステップ５０８でキャッシュ４２２はラインを提供し、ロード命令を終了する。有効なコピーを有さない場合、ステップ５１０でキャッシュ４２２は要求をメモリ・サブシステム４４０に伝える。ステップ５１２では、メモリ・サブシステム４４０のコヒーレンス制御装置４５０はまずアドレスを、外部ディレクトリ４６０と一時的状態バッファ４７０の両方のエントリと比較し、何らかの状態情報がこれらのディレクトリ中のアドレスと一致するかを調べる。一致しない場合、データ・ラインの最新の値は主メモリにあるはずなので、ステップ５１４でメモリ・サブシステム４４０はデータ・ラインを主メモリ４９０からフェッチし、ロード命令は終了する。ステップ５１２でアルゴリズムが一致するアドレスが一時的状態バッファ４７０に保存されていることを発見した場合、ステップ５１６でコヒーレンス制御装置４５０はこのラインについて要求がすでに出されていると判断する。これをどう処理するかはコヒーレンス・プロトコルに依存するが、この状況を処理する１つの方法がステップ５１８に示されており、そこではアルゴリズムは単にプロセッサ４１２に要求を再試行するよう命令する。
【００３４】
ステップ５１２で一致するアドレスが外部ディレクトリ４６０にあるとアルゴリズムが判断し、最新の値がどこか他のノードに存在することを示す場合、ステップ５２０でコヒーレンス制御装置４５０はメッセージをそのノードに送信し、一時的状態バッファ４７０中のこのラインのエントリを割り当て、バッファ４７０中に以前存在したラインを遷移状態にする。ステップ５２２で、コヒーレンス制御装置４５０は、コヒーレンス制御装置４５０がデータを待っていることを要求を出したプロセッサ４１２に知らせることによって、現在のトランザクションを完了する。その後コヒーレンス制御装置４５０は自由に新しい要求を処理することができる。
【００３５】
後に、ステップ５２４で、要求されたデータがリモート・ノードから到着し、ステップ５２６でコヒーレンス制御装置４５０は一時的状態バッファ４７０のラインを参照し、遷移状態を検索する。この遷移状態は、コヒーレンス制御装置４５０に、データをどこに転送すべきか、また最終的な永続状態は何であるべきかを告げる。ステップ５２８で、コヒーレンス制御装置４５０は、新しいトランザクションを開始して、データを要求を出したプロセッサ４１２に送信し、一時的状態バッファ・エントリを割り当て解除し、外部ディレクトリ４６０を最終永続状態に更新し、ロード命令を終了する。
【００３６】
以上述べたように、本発明によれば、キャッシュ・コヒーレンス状態を保持するために必要な外部記憶装置の量を減少させる。ラインが遷移状態にある時間の量は非常に短く、ある時間に遷移状態にあるラインはごく少数なので、本発明は一時的状態バッファのサイズも減少させる。さらに、本発明は、多数の遷移状態を通じて、遷移のための外部ディレクトリへのアクセスを除去し、コヒーレンス・プロトコルの総合的な処理能力を増大する。
【００３７】
ここで説明した実施形態の例は例示を目的とし、制限することを企図するものではない。従って、当業技術分野に熟練した者は、他の実施形態が請求項の範囲と精神から離れることなく実行されることが認識されるだろう。
【図面の簡単な説明】
【００３８】
【図１】先行技術のキャッシュ・メモリ・アクセス・アルゴリズムのフローチャートである。
【図２】キャッシュ・コヒーレンス・ディレクトリを使用する従来技術のキャッシュ・メモリ・アクセス・アルゴリズムのフローチャートである。
【図３】バスによって主メモリに接続された固有のローカル・キャッシュを各々有する多数のＣＰＵを含む従来技術のシステムの構成図である。
【図４】各々多数のプロセッサとキャッシュを含む多数の相互接続されたノード、コヒーレンス制御装置、外部ディレクトリ及び一時的状態バッファを有するｃｃＮＵＭＡシステムの構成図である。
【図５】図４のｃｃＮＵＭＡシステムの一時的状態バッファを使用するローカル読み出し操作のフローチャートである。
【符号の説明】
【００３９】
３０２、３０４、３０６、３０８    ＣＰＵ
３１０、３１２、３１４、３１６    キャッシュ
３２０    メモリ制御装置
３２２    メモリ
３２４    ディレクトリ
４０２、４０８、４１０    ノード
４１２、４１４、４２０    プロセッサ
４２２、４２４、４３０    キャッシュ
４４０    メモリ・サブシステム
４５０    コヒーレンス制御装置
４６０    外部ディレクトリ
４７０    一時的状態バッファ
４８０    コヒーレンス制御チップ
４９０    主メモリ
【図１】
2006277762.tif 000003
【図２】
2006277762.tif 000004
【図３】
2006277762.tif 000005
【図４】
2006277762.tif 000006
【図５】
2006277762.tif 000007