(57)【要約】共有メモリ多重プロセッサコンピュータシステム（１００）で用いられるキャッシュコヒーレンシディレクトリ（３０３）である。データ構造（４００）は、キャッシュ可能な記憶場所の各々に関連し、データ構造は、排他的状態（５０１）、共有状態（５０２）、アンキャッシュ状態（５０３）、ビジー状態（５０６）、ロック状態（５０４）、およびペンディング状態（５２４）を表す状態値を記憶するための場所を含む。キャッシュラインが現在１つ以上の他のプロセッサによって用いられている間に、ビジー状態およびペンディング状態が共働してあるプロセッサによって将来用いられるためにキャッシュラインを確保する。
2004505346.tif 000002
【特許請求の範囲】
【請求項１】
複数の独立したプロセッサノードと、複数の記憶場所を含む共有メモリとを含む多重プロセッサシステム内でアトミックアンキャッシュ参照を実現するための方法であって、前記方法は、
少なくともいくつかのプロセッサノード内でキャッシュを実現するステップを含み、各キャッシュは複数のキャッシュエントリを含み、前記方法はさらに、
状態機械を各記憶場所に関連づけるステップを含み、状態機械は、排他的状態、ロック状態、ビジー状態、ペンディング状態、アンキャッシュ状態、共有状態、およびビジーアンキャッシュ状態を含み、前記方法はさらに、
記憶場所の内容を第１のプロセッサノードのキャッシュにコピーすることを含む現在のメモリ動作を行なうステップと、
記憶場所を含むペンディングメモリ動作に応答して、第１のプロセッサノード内のキャッシュラインは第２のプロセッサノードが望む情報のコピーを含むことを表し、さらには記憶場所のための状態機械をビジー状態に遷移するステップと、
第１のプロセッサノードが現在の動作を終了させたという表示に応答して、記憶場所のための状態機械をペンディング状態に遷移するステップとを含み、ペンディング状態の間、記憶場所はいずれのプロセッサノードによるアクセスからもロックされる、方法。
【請求項２】
状態機械は、第２のプロセッサノードがペンディング状態の間ペンディング動作を進める準備が整っているという表示にのみ応答する、請求項１に記載の方法。
【請求項３】
ビジー状態は、キャッシュコヒーレンシトランザクションを完了するプロセスにある第１のプロセッサノードの識別と、ペンディングキャッシュコヒーレンシ動作を有する第２のプロセッサノードの識別とを含む、請求項１に記載の方法。
【請求項４】
ビジー状態に遷移するステップは、
排他的状態からビジー状態に遷移するステップと、
第１のプロセッサノードに要求を送信して第１のプロセッサノードのキャッシュ内のキャッシュラインを無効にして排他的状態を終了するステップと、
ビジー状態内で保持される未処理の回答数値を１の値に設定するステップと、
キャッシュラインが第１のプロセッサノードのキャッシュ内で無効にされることを第１のプロセッサノードが確認するまで、ビジー状態にとどまるステップとを含む、請求項３に記載の方法。
【請求項５】
ビジー状態の間、第１のプロセッサノードからのキャッシュラインアクセスのみが可能にされる、請求項４に記載の方法。
【請求項６】
ビジー状態に遷移するステップは、
共有状態からビジー状態へと遷移するステップを含み、共有状態は、現在キャッシュラインのコピーを有する各プロセッサノードを表すノード存在ベクトルを含み、前記ビジー状態に遷移するステップはさらに、
ノード存在ベクトル内で表される各プロセッサノードに要求を送信してキャッシュラインを無効にして共有状態を終了するステップと、
ビジー状態内で保持される未処理の回答数値を、ノード存在ベクトル内で表されるプロセッサノードの数に等しい値に設定するステップと、
キャッシュラインがそれ自体のキャッシュ内で無効にされることをノード存在ベクトル内の各プロセッサノードが確認するまで、ビジー状態にとどまるステップとを含む、請求項３に記載の方法。
【請求項７】
共有メモリ多重プロセッサコンピュータのためのキャッシュコヒーレンシディレクトリであって、
各キャッシュ可能な記憶場所に関連したデータ構造を含み、データ構造は、排他的状態、共有状態、アンキャッシュ状態、ビジー状態、ビジーアンキャッシュ状態、ロック状態、およびペンディング状態を表す状態値を記憶するための場所を含み、ビジー状態およびペンディング状態は、キャッシュラインが現在１つ以上の他のプロセッサによって用いられている間、プロセッサによる将来の使用に備えるためにキャッシュラインを共働して確保する、キャッシュコヒーレンシディレクトリ。
【請求項８】
キャッシュ記憶場所にアクセスするための要求に応答して、データ構造内に記憶される、要求される記憶場所に関連した状態値を判断するための手段と、
キャッシュ記憶場所にアクセスするための要求に応答して状態値に基づいてキャッシュコヒーレンシ動作を発行するための手段と、
キャッシュ記憶場所にアクセスするための要求に応答して、予め規定される順序で表される状態間で状態値を遷移させるための手段とをさらに含む、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項９】
排他的状態は、キャッシュラインへの排他的アクセスを有するノードが０または１つであることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１０】
共有状態は、キャッシュラインへの共有アクセスを有するノードが０または１つ以上であることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１１】
アンキャッシュ状態は、キャッシュラインへの排他的または共有アクセスを有するノードが０であることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１２】
ビジーおよびビジーアンキャッシュ状態は、キャッシュラインが排他的状態または共有状態のいずれかから遷移したことを表し、さらにはキャッシュラインが未処理のキャッシュコヒーレンシ回答を有することを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１３】
ペンディング状態は、キャッシュラインが排他的または共有もしくはビジー状態にあった間にキャッシュラインに対する要求を示した別のノードのために確保されている排他的状態からキャッシュラインが解放されたことを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１４】
計算システムであって、
通信バスに結合される複数のプロセッサノードと、
各プロセッサノード内のキャッシュメモリとを含み、キャッシュメモリは複数のキャッシュラインを含み、前記計算システムはさらに、
複数のキャッシュ可能な場所を含む共有メモリと、
共有メモリの各キャッシュ可能な場所と関連した状態機械とを含み、状態機械は、関連のキャッシュ可能な場所が現在第１のプロセッサノードによって用いられ、さらには第２のプロセッサノードによる将来の使用に備えるために確保されていることを表す状態を実現する、計算システム。
【請求項１５】
状態機械はさらに、
関連のキャッシュラインが現在ビジーであることを表す値を保持するビジー状態と、どのプロセッサが関連のキャッシュラインを制御するのかという表示と、どのプロセッサが将来用いるためにキャッシュラインを確保しているのかという表示とを含む、請求項１４に記載の計算システム。
【請求項１６】
状態機械はさらに、関連のキャッシュラインが現在ロックされていて、第２のプロセッサからの表示によってのみペンディング状態から遷移され得ることを表す値を保持するペンディング状態を含む、請求項１４に記載の計算システム。
【請求項１７】
状態機械は、関連の記憶場所が他のいずれかのプロセッサによってキャッシュ可能である状態に入ることなしに、第１のプロセッサによる排他制御を表す状態から、第２のプロセッサの排他制御を表す状態へと遷移する、請求項１４に記載の計算システム。
【請求項１８】
各プロセッサノードは、共有フロントサイドバスによって互いと結合される２つ以上のプロセッサを含む、請求項１４に記載の計算システム。
【請求項１９】
各プロセッサノードのフロントサイドバスを通信バスに結合するブリッジ回路をさらに含む、請求項１８に記載の計算システム。
【発明の詳細な説明】
【０００１】
【発明の背景】
［発明の分野］
この発明は、一般に、マイクロプロセッサシステムに関し、より具体的には、多重プロセッサコンピュータシステム内でキャッシュコヒーレンシおよびアトミックトランザクションを提供するためのシステムおよび方法に関する。
【０００２】
［関連の背景］
マイクロプロセッサは、コンピュータプログラムが特定する命令に従ってデータを処理する。従来のシステムでの命令およびデータは、メモリバスによってプロセッサに結合されたメモリ内に記憶される。コンピュータプログラムは、並列処理をうまく活かすために、ますますコンパイルされている。並列処理によって、複雑なプログラムは同時に実行されるそれほど複雑でない複数のルーチンとして実行可能となって性能が向上する。
【０００３】
伝統的に、マイクロプロセッサは、マイクロプロセッサがメモリアドレススペースを完全に制御する環境で単一の命令ストリームを処理するように設計された。多重プロセッサコンピュータシステムが開発されて並列に動作する複数のデータプロセッサを設けることによって実行時間が短縮された。初期の多重プロセッサシステムは、複数のプロセッサのアクティビティを調整するように特別に設計された特徴を含んだ専用のプロセッサを用いた。さらに、ソフトウェアは、多くの場合、ある特定の多重プロセッサプラットフォーム用に特別にコンパイルされた。これらの要因によって、多重処理の入手および維持は費用のかかるものとなった。
【０００４】
低コストで高性能のマイクロプロセッサがさらに利用可能となったことによって、汎用の多重処理コンピュータが実現可能となる。ここで用いられるように、用語「マイクロプロセッサ」および「プロセッサ」は、複合命令セットコンピュータ（ＣＩＳＣ）、縮小命令セットコンピュータ（ＲＩＳＣ）、およびハイブリッドを含む。しかし、汎用のマイクロプロセッサは、大規模な多重処理のために特別に設計されているわけではない。いくつかのマイクロプロセッサは、システム内で最大４つのプロセッサの構成をサポートする。これらの限界を超えるためには、専用のハードウェア、ファームウェア、およびソフトウェアを用いてシステム内の種々のマイクロプロセッサのアクティビティを調整しなければならない。
【０００５】
メモリ管理が、多重プロセッサシステム設計者が直面するより困難な調整問題の１つである。基本的に、その問題は、各プロセッサが同時に動作してメモリ内容にアクセスし、修正変更する間に、各プロセッサがいかなる所与の時にもメモリ内に記憶されたデータの一貫したビューを有することを保証することに関する。この問題は、プロセッサの数が増えるにつれて、かなり複雑となる。
【０００６】
「共有メモリ」および「分散メモリ」と呼ばれることもある、２つの基本的なアーキテクチャが発達した。分散メモリは、独自の範囲のメモリを各プロセッサまたはプロセッサの小さなグループに割当てる。分散メモリシステムでは、所与のメモリスペースに割当てられた少数のプロセッサのみが、それらのメモリアクセスアクティビティを調整する必要がある。この割当てによって、メモリ内容へのアクセスおよびそれらの処理に付随したタスクがかなり簡素化される。しかし、メモリは物理的に区分されているため、相乗作用はより少なく、したがって、プロセッサをさらに加えることによって達成される性能の向上も少ししか得られない。
【０００７】
すべてのプロセッサが共通のメモリアドレススペースを共有することが有利である。共有メモリシステムでは、ハードウェアおよびソフトウェアメカニズムを用いて、各プロセッサの観点からのメモリの一貫したビューを維持する。共有メモリによって、プロセッサが関連プロセス上で動作し、プロセス間でデータを共有することができる。共有メモリシステムは、プロセッサ間でのより大きな相乗作用の可能性を提供するが、メモリ管理がより複雑になるという犠牲を伴う。
【０００８】
マイクロプロセッサの性能を向上させた重要な進歩のうちの１つは、チップ上のキャッシュメモリを他のマイクロプロセッサ機能ユニットと一体化させたことである。キャッシュメモリによって、プロセッサはメインメモリサブシステムからのデータおよび命令のうち頻繁に用いられる部分のコピーを、隣接して結合された、低ラテンシキャッシュメモリ内に記憶することが可能となる。キャッシュメモリがデータを供給する場合、メインメモリアクセスに関連したラテンシがなくなる。キャッシュメモリシステムでは、１つ以上のプロセッサキャッシュ内のデータコピーとメインメモリそれ自体との間のコヒーレンシの保証が必要とされている。
【０００９】
単一のプロセッサシステムでは、コヒーレンシは、比較的単純明快な事柄である。なぜならば、ある所与のメモリアドレススペースに対して１つのキャッシュシステム階層しか存在しないためである。区分されたメモリシステムにおいても、１つ、または多くても数個のキャッシュサブシステムが単一のメモリ区分に対応する。しかし、共有メモリシステムでは、ある所与の記憶場所は、システム内のいずれのプロセッサのいずれのキャッシュ内にも記憶され得る。１つのプロセッサがそれ自体のキャッシュまたはメインメモリ内でデータを処理するためには、他のプロセッサが同時にそのデータを処理できないことを保証しなければならない。典型的なシステムでは、これは、キャッシュサブシステムおよび／またはプロセッサ間での高帯域幅通信を必要とする。さらに、従来のマイクロプロセッサは、オペレーティングシステムおよびアプリケーションソフトウェアが４つよりも多いプロセッサ数から８つまでのプロセッサ上で動作するように調整するための専用のハードウェアサポートを必要とする。
【００１０】
キャッシュシステムは、典型的にはアトミックユニットとしてアクセスされる複数のキャッシュラインとして編成される。各キャッシュラインは、たとえば、キャッシュラインが有効であるか（つまり、メインメモリと一貫しているか）、それが「不正」であるか（つまり、変更されているか）等を示す１組の状態情報に関連付けられる。共有メモリシステムは多くの場合、（マルチ状態）プロトコルを用い、ここでは、各キャッシュラインは状態情報を含む。たとえば、“ＭＥＳＩ”プロトコルは、キャッシュラインが修正変更されているか、排他的であるか、共有されているか、または無効であるか（ＭＥＳＩ）を示す状態情報を含む。代替的なコヒーレンシプロトコルは「更新」プロトコルを含み、これは、新しいデータ値を、その値のキャッシュコピーを保持する各プロセッサに送って各キャッシュコピーを更新する。オーナーシッププロトコルは、キャッシュ間でオーナートークンを渡してどのキャッシュが書込許可を有するか、さらにはどのキャッシュが最新バージョンのデータを保持するかを示す。
【００１１】
ＭＥＳＩシステムでは、非共有キャッシュラインがアクセスされると、それは排他的（Ｅ）と示される。後続の読出は、状態を変化させないが、キャッシュラインに対する後続の書込は、状態を修正変更（Ｍ）に変化させる。別のプロセッサがデータをそのプロセッサのキャッシュにロードするようであれば、ラインは共有（Ｓ）と示される。共有キャッシュラインにデータを書込むためには、すべてのプロセッサ、または少なくとも共有データのコピーを有するすべてのプロセッサに無効コマンドが送られなければならない。プロセッサが修正変更ラインからデータをロードし得る前に、修正変更キャッシュラインを有するプロセッサは、データをメモリに書込み、それを共有と示さなければならない。無効（Ｉ）と示されるキャッシュラインに対するいずれの読出または書込も、結果としてキャッシュミスとなる。
【００１２】
同様の問題が、いかなるアトミックメモリ動作についても存在する。アトミックメモリ動作とは、読出または書込動作が共有記憶場所に対して行なわれるものである。共有記憶場所がアンキャッシュである場合でさえも、アトミックメモリ動作は、共有記憶場所にアクセスしているいずれのプロセッサもアトミック動作が完了するまでその場所の読出を行なわないことを確実にする様態で、完了しなければならない。
【００１３】
すべてのプロセッサおよびメインメモリが共通バスを用いて物理的に接続されている共有メモリ多重プロセッサシステムでは、あるプロセッサは、他のプロセッサのこの状態情報を照会または「探索」し得る。さらに、要求を行なうプロセッサは、この状態情報を処理して、たとえば、あるキャッシュラインを無効にすることによって所与の記憶場所への所望のアクセスを得ることができる。しかし、探索によって各プロセッサのキャッシュにアクセスすることは、時間のかかるプロセスである。さらに、それは混乱を起こさせる。なぜならば、探索要求は、キャッシュアクセスのために、プロセッサがそれ自体の命令を実行しようとすることによって生じる多数の進行中のキャッシュ要求と調停しなければならないためである。プロセッサの数が増えるにつれて、この種のコヒーレンシプロトコルに付随したオーバーヘッドは、実際的でなくなる。
【００１４】
他のコヒーレンシシステムは、プロセッサがメモリ管理システムにリプレースメント暗示を提供することを必要とする。これらの暗示は、プロセッサがキャッシュラインの現在の状態（たとえば、キャッシュラインがある特定のプロセッサに限られたままであるか）の表示で共働するメカニズムを提供する。リプレースメント暗示を用いることによって利点が提供されるが、この要件は、多重プロセッサシステムのために用いられ得る利用可能なマイクロプロセッサの種類をかなり制限する。リプレースメント暗示を提供するプロセッサを必要としないか、またはそれに依存しないアトミックメモリ動作およびキャッシュコヒーレンシを提供するシステムおよび方法が必要とされている。
【００１５】
探索ベースのコヒーレンシ実現例に付随した工学的な問題点とスケーラビリティの問題点との両方を解決するために、ディレクトリアプローチが用いられる。どのプロセッサがメモリのどのラインを保持するかについての情報およびラインについてのＭＥＳＩ状態情報のスーパーセットを保持するようなデータ構造が用いられる。各キャッシュを探索するのではなく、中央のディレクトリ構造を照会して各メモリラインの状態が判断され得る。ディレクトリを調べた後、要求を行なうプロセッサにメモリラインを割当てるために必要なキャッシュコヒーレンシ動作のみが必要とされる。ディレクトリは、フルマップ、コアースマップ、部分マップ、またはリンクリストとして実現され得る。
【００１６】
代替的には、ホストバスロックを用いて非常に強制的な様態で最小単位を保証し得る。アンキャッシュメモリを備えたインテル（Ｉｎｔｅｌ）アーキテクチャ３２（ＩＡ３２）命令セットでのアトミック動作サポートは、２つのバス動作、すなわち、読出とそれに続く書込とを必要とする。これらの動作が行なわれている間、バスロックは、表明され、他のプロセッサがバスの使われていないバンド幅を利用することを妨げる。これは、多数のプロセッサおよび他の構成要素がホストバスを共有するコンピュータシステムでは特に不利益である。ホストバスを用いるいずれかのエージェントによってバスロックを表明することにより、他のものが、メモリに対するいずれかのバストランザクションを開始または完了することが妨げられる。
【００１７】
より複雑な多重プロセッサアーキテクチャは、各プロセッサボードが共有フロントサイドバスでもって共に結合される多数のプロセッサを含む、多数のプロセッサボードを組合せる。このようなシステムでは、多数のボードは、互いと相互接続され、フロントサイドバスから独立した相互接続ネットワークを用いるメモリと相互接続される。本質的に、多重処理ボードの各々は、独立したフロントサイドバスを有する。フロントサイドバスはすべてのシステムプロセッサによって共有されているわけではないため、フロントサイドバス上でのみ動作するバスロックおよびバス探索等のコヒーレンシメカニズムの実現は、不可能ではないが、困難である。
【００１８】
したがって、オーバーヘッドを最小にするように効率的に動作するキャッシュコヒーレンシメカニズムおよび方法を提供することが望ましい。より具体的には、従来のキャッシュコヒーレンシメカニズムまたはバスロックメカニズムのいずれかに依存することのないキャッシュ管理を提供するための手段が必要とされている。さらに、多数の独立したフロントサイドバスを備えたシステム上で動作するキャッシュコヒーレンシメカニズムが必要とされている。
【００１９】
【発明の概要】
簡単に説明すると、この発明は、多重プロセッサシステム内で（アトミック参照を含む）アンキャッシュ参照とキャッシュ参照との両方を実現するためのシステムおよび方法を含む。多重プロセッサシステムは、各々が１つ以上のプロセッサを有する複数の独立したプロセッサノードを含む。複数の記憶場所を含む共有メモリは、プロセッサノードの各々によってアクセス可能である。キャッシュは、プロセッサノードのうちの少なくともいくつかの中で実現され、各キャッシュは複数のキャッシュエントリを含む。状態機械は各記憶場所と関連付けられ、状態機械は、排他的状態、ロック状態、ビジー状態、ペンディング状態、アンキャッシュ状態、共有状態、およびビジーアンキャッシュ状態を含む。記憶場所の内容を第１のプロセッサノードのキャッシュにコピーすることを含む、現在のメモリ動作が行なわれる。記憶場所を含むペンディングメモリ動作に応答して、記憶場所のための状態機械が処理されて、第１のプロセッサノード内のキャッシュラインが、第２のプロセッサノードが望む情報のコピーを含むことが示される。このとき、状態機械はビジー状態に遷移する。第１のプロセッサノードが現在の動作を終了したという表示に応答して、状態機械はペンディング状態に遷移する。ペンディング状態の間、記憶場所は、いずれのプロセッサノードによるアクセスからもロックされる。
【００２０】
別の局面では、この発明は、共有メモリ多重プロセッサコンピュータのためのキャッシュコヒーレンシディレクトリを含む。データ構造は、キャッシュ可能な記憶場所の各々に関連付けられる。データ構造は、排他的状態、共有状態、アンキャッシュ状態、ビジー状態、ビジーアンキャッシュ状態、ロック状態、およびペンディング状態を示す状態値を記憶するための場所を有する。他の１つ以上のプロセッサがキャッシュラインを現在用いている間に、ビジー状態およびペンディング状態はあるプロセッサによる将来の使用に備えるためにキャッシュラインを共働して確保する。
【００２１】
さらに別の局面では、この発明は、通信バスに結合される複数のプロセッサノードを有する計算システムを含む。各プロセッサノードは、共有フロントサイドバスによってともに結合される２つ以上のプロセッサを含む。プロセッサノードの各々の中のキャッシュメモリであって、そのキャッシュメモリは複数のキャッシュラインを含む。共有メモリは、複数のキャッシュ可能な場所を含み、すべてのプロセッサノード間で共有されるアドレススペースによって規定される。状態機械は、共有メモリのキャッシュ可能な場所の各々に関連付けられ、状態機械は、関連付けられたキャッシュ可能な場所は現在第１のプロセッサノードによって用いられていて、第２のプロセッサノードによる将来の使用に備えるために確保されていることを示す状態を実現する。
【００２２】
【好ましい実施例の詳細な説明】
この発明は、一体化されたキャッシュメモリを有するいくつかの実質的に同一のマイクロプロセッサを含む汎用多重処理計算システムに関して例示および説明される。この種類の計算システムは、この発明の特徴および原理を例示するには優れたツールであるが、異なる種類のセットのプロセッサも用いられ得ることが理解されるべきである。いくつかのプロセッサは一体化されたキャッシュを含んでもよく、いくつかのプロセッサは外部キャッシュを含んでもよく、さらに他のプロセッサはキャッシュを全く有さなくてもよい。この発明は共有メモリシステムに関して例示されるが、ある特定の局面は区分されたメモリシステムでの応用も有する。したがって、ここで与えられる特定の例は、例示および理解のために提供されているのであり、特に指示されない限り、この発明の限定として理解されるべきではない。さらに、この発明の重要な特徴は、それが容易に上向き、および下向きに調整されてある特定のアプリケーションまたはプロセッサ数のニーズを満たすことである。したがって、特に指示がない限り、この発明は、極めて大きくてより複雑なネットワーク環境および従来のローカルエリアネットワーク（ＬＡＮ）システム等の小さなネットワーク環境に適用できる。
【００２３】
図１は、この発明が実現される多重プロセッサコンピュータ環境を示す。多重プロセッサコンピュータシステム１００は、Ｎ個のプロセッサボード１０１を組込む。各プロセッサボード１０１は、ある特定の例では一体化されたキャッシュメモリを有するプロセッサＰ１およびＰ２等の１つ以上のマイクロプロセッサを含む。プロセッサボード１０１は、共通のフロントサイドバス１０４を共有し、さらにはブリッジ１０７を介してホストバスネットワーク１０２へとつながる共通のゲートウェイを共有するグループで構成され得る。例示的なプロセッサは、単一のプロセッサとして、または最大８つのプロセッサのクラスタで構成され得る、インテル社（Ｉｎｔｅｌ Ｃｏｒｐｏｒａｔｉｏｎ）が製造するペンティアム（Ｒ）ＩＩＩジーオン（Ｘｅｏｎ）（商標）プロセッサである。
【００２４】
プロセッサ１０１は、ホストバスネットワーク１０２を介して共有メモリ１０３に双方向に結合される。ホストバスネットワーク１０２は好ましくは、フルクロスバ接続を実現し、いずれのプロセッサボード１０１も、いずれかのメモリバンク１０５内で実現されるいずれの記憶場所にもアクセスすることが可能となる。共有メモリ１０３は、複数のＭ個のメモリバンク１０５として構成される。各メモリバンク１０５は、メモリ構成要素のグループを含み得る。好ましくは、共有メモリ１０３は複数の「ライン」として編成され、各ラインは、アーキテクチャによって規定された、プロセッサ１０１内のキャッシュのラインサイズに基づいた大きさにされる。メモリまたはキャッシュ内のラインは、最小のアクセス可能なデータユニットであるが、この発明は、ライン内でのアドレス指定を可能にするメモリアーキテクチャをサポートする。
【００２５】
各プロセッサボード１０１は、フロントサイドバスクロスバ１０６を含み得るが、これは、ローカルメモリ１０８および周辺コンポーネント相互接続（ｐｅｒｉｐｈｅｒａｌ ｃｏｍｐｏｎｅｎｔ ｉｎｔｅｒｃｏｎｎｅｃｔ）（ＰＣＩ）ブリッジ１１０へのアクセスを可能にする。ある特定の例では、ローカルメモリ１０８は、共有メモリ１０３のアドレススペース内に含まれておらず、ＦＳＢクロスバ１０６と同じフロントサイドバス１０４に結合されるプロセッサＰ１とＰ２との間でのみ共有される。ＰＣＩブリッジ１１０は、従来のＰＣＩデバイスが、たとえば、外部ネットワーク１１１および／または記憶装置１１２にアクセスすることと、それらへの接続を管理することとをサポートする。ＰＣＩデバイスが他のボード１０１を通して利用可能な場合、いくつかのプロセッサボード１０１はＰＣＩブリッジ機能を除去し得ることが企図される。
【００２６】
注目すべきは、各プロセッサボード１０１のフロントサイドバス１０４が、他のすべてのプロセッサボード１０１のフロントサイドバス１０４から独立していることである。したがって、アトミック動作またはキャッシュ一貫性を実行するためにＩＡ３２命令セットによって提供されるいずれのメカニズムも、異なるボード１０１上に位置するプロセッサ間では動作しない。
【００２７】
プロセッサＰ１またはＰ２が、メモリ１０３内の目標場所からのロード、またはその場所への記憶を要求する命令を実行するとき、メモリ動作が行なわれる。入出力装置および周辺装置もメモリにアクセスし得るが、説明を簡潔にするために、ここでの例は、プロセッサが行なうメモリ動作のみを指す。メモリ動作の実行時、プロセッサはまず、目標の記憶場所がキャッシュ内で表されていて、有効で、さらにはアクセス可能であるかどうかを判断する。キャッシュは、メモリ動作を実行するプロセッサのボード上にあってもよいし、または外部キャッシュメモリ内に存在してもよい。キャッシュミスの場合、メモリ動作はブリッジ１０７によって処理される。ブリッジ１０７は、アクセス要求をホストバスネットワーク１０２に対して生成し、目標場所アドレス、動作の種類（たとえば、読出／書込）、および、ある特定の実現例で必要とされ得る他の制御情報を特定する。共有メモリ１０３は、要求を受取り、特定された記憶場所にアクセスする。読出動作の場合、要求されたデータは、ホストバスネットワーク１０２を通して渡される応答を介して、アクセス要求を生成したブリッジ１０７に戻される。書込トランザクションは、書込が行なわれたという肯定応答を返し得る。共有メモリ１０３内でエラーが生じた場合、ブリッジ１０７への応答は、エラーについての情報を示す条件コードを含み得る。
【００２８】
図２は、ある具体的な実現例およびこの実現例のための相互接続ストラテジを例示する。図２の実現例では、ＳＥＧＭＥＮＴ＿０からＳＥＧＭＥＮＴ＿１５で示された１６のセグメントが存在する。各セグメントはプロセッサグループ２０１を含む。ある特定の例でのプロセッサグループ２０１は、１６対のプロセッサ（たとえば、１６のプロセッサボード１０１）を含み、各々は、ブリッジ１０７によって実現される双方向データおよびコマンドバスインターフェイスを通してプロセッサスイッチ２０２に結合される。プロセッサスイッチ２０２は、各メモリバンクグループ２０５のための中継線２１４への出力を含む。同様に、各メモリスイッチ２０３は、各プロセッサグループ２０１のための中継線２１４への出力を含む。この様態で、いずれのプロセッサグループも、プロセッサスイッチ２０２およびメモリスイッチ２０３の適切な構成によっていずれかのメモリバンクグループに選択的に結合され得る。
【００２９】
図３は、この発明に従ったメモリバンク３００に関連付けられる重要なキャッシュコヒーレンシメカニズムを示す。メモリスイッチ２０３は、（図２で示される）中継線２１４と通信を行なってメモリアクセス要求を送信および受信する。メモリアクセス要求の受信時、メモリスイッチ２０３は、目標メモリアドレスおよびノード識別を含む情報、および制御モード情報をキャッシュコヒーレンシチップ３０１に渡す。目標メモリアドレスは、メモリバンクデータ部３０２内の場所を指す。ノードＩＤは、メモリ動作への回答を開始または受信している多重プロセッサシステム内のある特定のプロセッサボード１０１を示す値である。ある特定の実施例では、この情報は、さまざまな種類の情報のために規定されたフィールドを有するデータパケットとして、スイッチ２０３とキャッシュコヒーレンシチップ３０１との間で渡される。
【００３０】
キャッシュコヒーレンシチップ３０１は、ＡＳＩＣ等のカスタム集積回路として、プログラム可能なゲートアレイ等の１回限りの、または再プログラム可能な論理的装置として、または従来の回路基板またはマルチチップモジュール内で結合される個別部品として、実現され得る。キャッシュコヒーレンシチップ３０１は、メモリアドレスを用いてキャッシュコヒーレンシディレクトリ３０３にアクセスする。キャッシュコヒーレンシディレクトリ３０３は、ある特定のメモリバンクデータ部３２０の共有メモリアドレススペース内の各メモリライン（つまり、キャッシュライン）のためのマルチビットエントリを含む。エントリは、対応するメモリラインの現在の状態を示す値を含む。
【００３１】
ある特定の例では、メモリバンクは６４−２５６メガバイトのメモリをサポートするように構成されており、したがって、ディレクトリ３０３は、２５６ビット長メモリラインのために約２００万から８００万のエントリを含み得る（つまり、キャッシュライン当り３２バイト）。ある特定の例では、ディレクトリ３０３内の各エントリは、３６ビット長である。以下でより詳細に説明されるように、あるエントリ内のいずれかの特定のビットに与えられる意味がエントリの状態に依存する点で、エントリは固定されたフォーマットを有さない。
【００３２】
キャッシュコヒーレンシディレクトリ３０３はまた、どのプロセッサノード１０１がディレクトリ３０３内で現在表されているのかを示すノード存在ベクトルを含み得る。ある特定の例では、１６ビット値がビットマップの態様で用いられて、１６のプロセッサノード１０１のうちのどれが表されているのかが示される。各ビットは、多数のプロセッサを含むクラスタまたはセグメントを表し得る。ノード存在ベクトルは迅速に照会されてどのノードがキャッシュコヒーレンシ動作を知らされなければならないかが識別され得る。
【００３３】
好ましくは、メモリバンク３００は、エラー訂正メカニズム３０４も含み得る。キャッシュコヒーレンシチップ３０１は、スイッチ２０３からのメモリアクセスパケットの一部としてモードビットを受取る。これらのモードビットは、表１で示すように、どの種類のデータパケットがメモリスイッチによって示されているのか、または表２においてどの種類のパケットがメモリスイッチ２０３に示されているのかを表す。エラー訂正メカニズム３０４はモード情報を用いて、可能であれば、コヒーレンシディレクトリ３０３にアクセスする前にエラーを識別および訂正する。エラー訂正コードを用いてデータを訂正する。アドレスエラーは、パリティビットによって識別され、通常、訂正可能ではない。これらのメカニズムによって、プロセッサノード１０１とメモリバンク３００との間の通信中に生じるビットエラーが引起こすメモリエラーを回避することができる。
【００３４】
表１で用いられる用語は、インテルアーキテクチャ用語を用いているが、他のプロセッサアーキテクチャも、実質的に同じバス動作を説明するために実質的に同じ用語を有する。表１では、“ＢＲＬ”はバス読出ラインを意味し、“ＢＷＬ”はバス書込ラインを意味する。“ＢＲＩＬ”は、バス読出および無効ラインを指す。“ＨＩＴＭ♯”は、修正変更データ上のヒットを意味し、“ＨＩＴ♯”は、クリーンデータ上のヒットを意味する。
【００３５】
【表１】
2004505346.tif 000003
【００３６】
【表２】
2004505346.tif 000004
【００３７】
動作において、メモリ要求はスイッチ２０３によって表され、メモリ回答はメモリバンク３００によって生成される。メモリ要求は、ある特定のキャッシュコヒーレンシ動作を暗に示すメモリアドレスから読出され、またはそこに書込まれ得る。メモリ要求はまた、ある特定されるラインを共有するための、またはある特定されるラインを無効にするためのコマンド等の明示的なキャッシュコヒーレンシ要求であってもよい。回答は、データおよびキャッシュコヒーレンシ状態を含み得る。メモリバンク３００はまた、エラー条件が要求によって生成されたこと、要求された動作の単純な完了または肯定応答、および要求を再試行するための表示を示す回答を生成し得る。
【００３８】
図４は、例示的なキャッシュコヒーレンシディレクトリエントリ４００を示す。図４の具体的な例は、以下で定義される状態独自のフィールドを有する３６ビットエントリである。しかし、この発明の教示から逸脱することなしに、異なるエントリサイズが、異なったフィールドサイズ、指定、および機能とともに用いられ得ることが企図される。種々のニーモニックが、表３で規定されるような例および説明で用いられる。
【００３９】
【表３】
2004505346.tif 000005
【００４０】
一般に、３つの最上位ビット＜３３：３５＞を用いて、７つのキャッシュ状態（排他的、共有、アンキャッシュ、ビジー、ビジー＿アンキャッシュ、ロック、およびペンディング）のうちのいずれがキャッシュラインに適用可能であるかが示される。ビット３５は排他性を示し、ビット３４は共有／ロック状態を示し、ビット３３はビジー状態を示すが、この割当はこの発明の実施に重要なものではない。
【００４１】
残りのビットの解釈は、どのキャッシュ状態が表示されているかの認識に依存する。最下位ビット＜３１：０＞は、共有キャッシュ状態ではノード存在ベクトルを保持する。非共有キャッシュ状態では、ビット＜１６：２０＞はペンディングノードＩＤ（ＰＩＤ）値を保持し、ビット＜２１：２５＞は現在のディレクトリプロセッサノードＩＤ（ＤＩＤ）値を保持する。図４のある特定の例では、ビット＜３０：２６＞はカウンタ値を保持する。状態の大部分がすべてのフィールドを用いるわけではない。用いられないフィールドは、無視され、いかなる値を有してもよく、またはある特定の実現例では除去されてもよい。しかし、図５で示される一般的なフォーマットを有することによって、状態遷移は簡素化される。なぜならば、ディレクトリ状態情報の一部（たとえば、ＤＩＤ値）は、既にディレクトリエントリ内に記憶され得るためである。
【００４２】
排他的な状態では、ＤＩＤフィールドは、排他的アクセスを保持するプロセッサノード１０１を識別するノードＩＤ値を保持する。共有状態では、ノード存在ベクトルのみが必要とされて、どのノードがキャッシュラインへの共有アクセスを有するのかが示される。ビジー状態では、ＤＩＤが、（仮にも存在するのならば）排他的アクセスを現在保持しているノードＩＤを表す。ＰＩＤフィールドは、ペンディングキャッシュコヒーレンシ要求を備えたプロセッサノード１０１を識別する。ビジー状態はまた、いくつかの未処理のトランザクションを示す回答数（つまり、予想される回答数）を表すフィールドを含む。ペンディング状態は、ＰＩＤ値のみを用いる。回答数値が０の場合の上述のビジー状態は、ペンディング状態と実質的に同じ（つまり、別名）である。ロック状態は、ＤＩＤフィールドのみを用いてロックキャッシュラインを所有するプロセッサノード１０１を表す。
【００４３】
ビジー＿アンキャッシュフィールドは、排他的または共有のいずれかであったキャッシュラインがアンキャッシュ書込を有したことと、さらにはキャッシュラインは無効化が完了するのを待機していることとを表す。ビジー＿アンキャッシュ状態は、ＤＩＤフィールドを用いて、アンキャッシュ書込を実行したプロセッサノード１０１を識別し、回答数フィールドを用いて、無効化が完了したことを示す予想される回答数を表す。アンキャッシュ状態は、フィールド値のいずれも用いず、キャッシュラインが現在いずれのノードのキャッシュ階層にも割当てられていないことを示す。
【００４４】
図５は、この発明に従ったキャッシュコヒーレンシメカニズム動作を示す状態図である。図５で示される状態は、キャッシュコヒーレンシディレクトリ３０３内に記憶される適切な値によって、所与のメモリラインのために実現される。図５で示されるメモリ状態は、関連付けられるキャッシュラインに関して一般的な意味を有する。
・排他的：キャッシュラインへの排他的アクセスを有するノードは０または１つである
・共有：キャッシュラインを有するノードは０または１つ以上である
・アンキャッシュ：１つのノードもキャッシュラインを有さない
・ビジーおよびビジーアンキャッシュ：キャッシュコヒーレンシ要求が完了するのを待機する
・ロック：アンキャッシュロック動作が進行中である
・ペンディング：排他的状態変化を開始したノードからの再試行を待つ
この発明に従ったキャッシュコヒーレンシプロトコルは、７つの規定されたキャッシュコヒーレンシ状態の間の２４の遷移を規定する。表４は、関連の動作とともに種々のキャッシュコヒーレンシシナリオを示す。表４では、以下の用語が注目されるべきである。
【００４５】
記号→は、キャッシュコヒーレンシ要求が送信されることを示す。
ＯＲＣは、キャッシュコヒーレンシ無効動作およびロック動作で用いられる未処理の回答数を意味する。
【００４６】
回答コード：
ＥＲＲＯＲは、要求される動作およびキャッシュライン状態が一貫していないことを示す。
【００４７】
ＣＭＰＬ（完了）は、キャッシュラインの排他的およびアンキャッシュ動作の通常の完了を示す。
【００４８】
ＣＭＰＬ＿ＳＨＲは、通常の完了−キャッシュライン共有（ＨＩＴ♯）を示す。
【００４９】
ＲＥＴＲＹは、要求が現時点で処理され得ないことを示す。再び試みよ。
ＲＥＴＲＹ＿ＢＥは、要求が現時点で処理され得ないことを示す。再び試みよ。しかし、元の要求がＢＩＬならば、ＢＲＩＬに変換し、データで回答せよ。
【００５０】
ビジーは、トランザクションが完全なペンディングであるとき、ＰＩＤは有効であることを暗に示す。
【００５１】
ビジーＵＣは、トランザクションが完全なラインアンキャッシュ（ｌｉｎｅ ｕｎｃａｃｈｅｄ）であるとき、関連付けられるＰＩＤを有さない。
【００５２】
さらに、表４全体を通してＳＨＲＶＥＣＴ［］を用いてノード存在ベクトル［］が示される。表４での各状態遷移は、図５における同様に番号付けされた遷移に一致する。表４では、状態遷移が示され、続いて、図４で示されるキャッシュコヒーレンシディレクトリエントリ内のどのフィールドが用いられるのかを示す第１列目が示される。第２列目は、メモリのインバウンド状態を示し、第３列目は、ディレクトリエントリを修正変更するために取られる動作を示す。
【００５３】
【表４】
2004505346.tif 000006
【００５４】
【表５】
2004505346.tif 000007
【００５５】
あるノードがメモリ内のあるラインに対してキャッシュ読出を開始するたびに、ノード内のトランザクションの完了時のキャッシュラインの状態は、以下のうちのいずれかであり得る。
ノード
・排他的：他のノードがそのラインを有さなかった場合。
・共有：１つ以上のノードがそのラインを有する場合。
【００５６】
あるノードがあるキャッシュラインに対して排他的アクセスを要求するたびに、以下が起こり得る。
キャッシュコヒーレンシディレクトリ
・排他的：キャッシュコヒーレンシ無効要求が、キャッシュラインへの排他的アクセスを有する現在のノードに送信される。
・共有：キャッシュコヒーレンシ無効要求が、キャッシュコヒーレンシディレクトリエントリ内のノード存在ベクトル内で設定されるすべてのノードに送信される。
・ロックまたはビジー：ノードは、ラインがアンキャッシュ状態になることを待機しているメモリをポーリングする（上の排他的および共有と同様であるが、要求を行うノードは状態変化を引起こさない）。
・アンキャッシュ：ノードは即座に、ラインへの排他的アクセスを許可される。
【００５７】
排他的モードまたは共有モードのいずれかでは、要求を行うノードが排他的にラインにアクセスし得る前に、要求を行うノードは、メモリバンクをポーリングし、キャッシュコヒーレンシ無効要求の完了を待機しなければならない。
【００５８】
キャッシュラインが排他的状態または共有状態のいずれかからビジー状態へと遷移する場合、その対応するキャッシュコヒーレンシディレクトリエントリ内の「未処理の回答数」（ＯＲＣ）は、キャッシュコヒーレンシ要求を受信するノードから予想される回答数に設定される。現在排他的なラインを無効にする、または共有するためのキャッシュコヒーレンシ要求に対してノード当り１つの回答のみが存在する。
【００５９】
現在共有されているラインに対して、キャッシュコヒーレンシ無効化のために多数の回答が存在する。なぜならば、ディレクトリの存在ベクトルサブフィールド内の各ビットは多数のノードを表わし得るためである。しかし、存在ベクトル内の個々のビットは、固定された既知の数の物理的ノードを表わす。例示的な実現例は、存在ベクトル内のビット当り１つのノードを規定する。
一般的なトランザクションフロー
・読出（Ｒｄ）（キャッシュ／アンキャッシュ）、アンキャッシュ書込−ノードで始まり、メモリに送られ、肯定応答／再試行パケットがブリッジに戻される。
・キャッシュコヒーレンシ動作−メモリバンクで始まり、ノードに送られ、（データを備えた／備えない）回答がメモリバンクに戻される。
・ライトバック−ノードで始まり、メモリバンクで終了する。通常の処理では、肯定応答はメモリバンクから戻されない。
【００６０】
以下は、キャッシュコヒーレンシプロセスの一般的なイベントシーケンスを説明する。
【００６１】
１．キャッシュラインの初期状態は、アンキャッシュである。
２．アンキャッシュラインは、以下の動作によって排他的状態または共有状態のいずれかにアップグレードされる。
・排他的（Ｅｘ）：ノードキャッシュデータまたは排他的読出動作。ノードがキャッシュラインへの排他的アクセスを有する間、所有ノード（つまり、ＤＩＤ）によるいかなる動作も許可される。
・共有（Ｓｈｒ）：ノードキャッシュコード読出。
【００６２】
３．排他的に保持されるキャッシュラインは、排他的または共有のいずれかに遷移し得る。
・Ｅｘ：別のノードがキャッシュラインの共有読出を行ない、キャッシュラインは、元のノード内にもはや存在しない。
・Ｅｘ：別のノードがキャッシュラインの排他的読出を行なう。キャッシュラインは、無効要求とともに排他的からアンキャッシュへとダウングレードされる。一旦キャッシュラインがアンキャッシュ状態に戻ると、要求を行う元のノードは順方向の進行を行なうことができる。例示的な実現例では、元のリクエスタ以外の後続のノードが、キャッシュラインにアクセスすることをブロックする備えがある。
・Ｓｈｒ：別のノードがキャッシュラインの共有読出を行ない、キャッシュラインは依然として現在、元のノード内でアクティブである。元のノードからアクセスされるキャッシュラインは、修正変更されたデータの、起こり得るライトバックによって共有にダウングレードされる。例では、
４．ノードが排他的書込動作および／または読出アンキャッシュ動作（通常、アンキャッシュ入力／出力）を行なう場合、排他的および共有ラインは、アンキャッシュにダウングレードされる。上述のイベント３とは異なり、一旦キャッシュラインの状態がアンキャッシュとなると、要求を行う元のノードがそのトランザクションを完了する前に、他のノードがキャッシュラインにアクセスすることを防ぐ備えは存在しない。しかし、両方の状況では、要求を行う元のノードは絶え間なくその要求を再試行しているため、全状態遷移フローは再開され得る。
【００６３】
５．排他的または共有キャッシュラインに対する、定義上ではアンキャッシュ動作である、ロック読出および書込は、ラインをアンキャッシュにダウングレードさせる。アンキャッシュから、ラインはロックにアップグレードされる。ノードが既にキャッシュラインへの排他的アクセスを有し、さらにはロック動作が実行される（ＬＯＣＫ♯）場合、キャッシュラインは、まずアンキャッシュに完全にダウングレードされる必要なしに、ロック状態に遷移する。
【００６４】
ここで説明されるキャッシュコヒーレンシ方法およびメカニズムは、ＭＥＳＩプロトコル等の従来のコヒーレンシプロトコルと比較していくつかの利点を提供する。多重プロセッサシステムにおけるキャッシュコヒーレンシトランザクションは、あるキャッシュライン上の排他制御を一方のプロセッサから別のプロセッサへと移行させるためのものである。従来のディレクトリベースのプロトコルを用いると、これは、排他的からアンキャッシュまたは共有へのキャッシュライン状態遷移を必要とする。キャッシュラインが現在利用可能であるというメッセージが第２のプロセッサに返され、第２のプロセッサは、現時点でアンキャッシュのラインに対する読出を再試行し、それを排他的へとアップグレードさせる。アンキャッシュまたは共有状態の間、他のいずれかのプロセッサが介入し、ライン上で排他制御を行ない、第２のプロセッサの活動を阻み得る。
【００６５】
対照的に、この発明は、第１のプロセッサによって制御が保持されている間に第２のプロセッサがキャッシュラインを確保することを可能にするように機能するビジーおよびペンディング状態を提供する。これは、排他的アクセスを望むプロセッサが繰返し失敗するという「競合」状態を防ぐ。表５は、実線の遷移が第１のプロセッサによる動作を示し、さらには破線の遷移が第２のプロセッサによる動作を示す図６で示される状態および状態遷移に関連して、この移行プロセス内のステップを説明する。
【００６６】
【表６】
2004505346.tif 000008
【００６７】
多重プロセッサコンピュータアーキテクチャにおけるキャッシュコヒーレンシおよびアトミックメモリ動作を提供するためのシステムおよび方法が提供されていることが理解されるべきである。この発明は、コヒーレンシおよびアトミックメモリ動作を提供するために、マイクロプロセッサ独自の特徴であるバス探索またはリプレースメント暗示を必要とせず、またはそれらに依存しない。したがって、この発明は、マイクロプロセッサの選択に関する柔軟性が大きい状態で実現可能であり、非常に多いプロセッサ数へと容易に調整できる。さらに、この発明は、大きなプロセッサ数の設計全体にわたってのメモリスペースの共有をサポートする。
【００６８】
この発明は、ある程度詳細に説明および例示されてきたが、本開示は例としてのみなされ、前掲の請求項で示されるように、この発明の思想および範囲から逸脱することなしに、当業者は部分的な組合わせおよび取合わせによる多くの変更に頼ることができることが理解される。
【図面の簡単な説明】
【図１】この発明が実現される多重プロセッサコンピュータ環境を示す図である。
【図２】この発明に従った例示的な多重プロセッサの一部を示す図である。
【図３】この発明に従ったメモリバンクに関連付けられるキャッシュコヒーレンシメカニズムを示す図である。
【図４】例示的なキャッシュコヒーレンシディレクトリエントリを示す図である。
【図５】この発明に従ったキャッシュコヒーレンシメカニズムの動作を例示する状態図である。
【図６】記憶場所のオーナーシップを第１のプロセッサノードから第２のプロセッサノードへと移すために用いられる状態遷移を示す簡素化された状態図である。
【図１】
2004505346.tif 000009
【図２】
2004505346.tif 000010
【図３】
2004505346.tif 000011
【図４】
2004505346.tif 000012
【図５】
2004505346.tif 000013
【図６】
2004505346.tif 000014
【国際公開パンフレット】
2004505346.tif 000015
2004505346.tif 000016
2004505346.tif 000017
2004505346.tif 000018
2004505346.tif 000019
2004505346.tif 000020
2004505346.tif 000021
2004505346.tif 000022
2004505346.tif 000023
2004505346.tif 000024
2004505346.tif 000025
2004505346.tif 000026
2004505346.tif 000027
2004505346.tif 000028
2004505346.tif 000029
2004505346.tif 000030
2004505346.tif 000031
2004505346.tif 000032
2004505346.tif 000033
2004505346.tif 000034
2004505346.tif 000035
2004505346.tif 000036
2004505346.tif 000037
2004505346.tif 000038
2004505346.tif 000039
2004505346.tif 000040
2004505346.tif 000041
2004505346.tif 000042
2004505346.tif 000043
2004505346.tif 000044
2004505346.tif 000045
2004505346.tif 000046
2004505346.tif 000047
2004505346.tif 000048
【手続補正書】
【提出日】平成14年5月16日(2002.5.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の独立したプロセッサノードと、複数の記憶場所を含む共有メモリとを含む多重プロセッサシステム内でアトミックアンキャッシュ参照を実現するための方法であって、前記方法は、
少なくともいくつかのプロセッサノード内でキャッシュを実現するステップを含み、各キャッシュは複数のキャッシュエントリを含み、前記方法はさらに、
状態機械を各記憶場所に関連づけるステップを含み、状態機械は、排他的状態、ロック状態、ビジー状態、ペンディング状態、アンキャッシュ状態、共有状態、およびビジーアンキャッシュ状態を含み、前記方法はさらに、
記憶場所の内容を第１のプロセッサノードのキャッシュにコピーすることを含む現在のメモリ動作を行なうステップと、
記憶場所を含むペンディングメモリ動作に応答して、第１のプロセッサノード内のキャッシュラインは第２のプロセッサノードが望む情報のコピーを含むことを表し、さらには記憶場所のための状態機械をビジー状態に遷移するステップと、
第１のプロセッサノードが現在の動作を終了させたという表示に応答して、記憶場所のための状態機械をペンディング状態に遷移するステップとを含み、ペンディング状態の間、記憶場所はいずれのプロセッサノードによるアクセスからもロックされる、方法。
【請求項２】
状態機械は、第２のプロセッサノードがペンディング状態の間ペンディング動作を進める準備が整っているという表示にのみ応答する、請求項１に記載の方法。
【請求項３】
ビジー状態は、キャッシュコヒーレンシトランザクションを完了するプロセスにある第１のプロセッサノードの識別と、ペンディングキャッシュコヒーレンシ動作を有する第２のプロセッサノードの識別とを含む、請求項１に記載の方法。
【請求項４】
ビジー状態に遷移するステップは、
排他的状態からビジー状態に遷移するステップと、
第１のプロセッサノードに要求を送信して第１のプロセッサノードのキャッシュ内のキャッシュラインを無効にして排他的状態を終了するステップと、
ビジー状態内で保持される未処理の回答数値を１の値に設定するステップと、
キャッシュラインが第１のプロセッサノードのキャッシュ内で無効にされることを第１のプロセッサノードが確認するまで、ビジー状態にとどまるステップとを含む、請求項３に記載の方法。
【請求項５】
ビジー状態の間、第１のプロセッサノードからのキャッシュラインアクセスのみが可能にされる、請求項４に記載の方法。
【請求項６】
ビジー状態に遷移するステップは、
共有状態からビジー状態へと遷移するステップを含み、共有状態は、現在キャッシュラインのコピーを有する各プロセッサノードを表すノード存在ベクトルを含み、前記ビジー状態に遷移するステップはさらに、
ノード存在ベクトル内で表される各プロセッサノードに要求を送信してキャッシュラインを無効にして共有状態を終了するステップと、
ビジー状態内で保持される未処理の回答数値を、ノード存在ベクトル内で表されるプロセッサノードの数に等しい値に設定するステップと、
キャッシュラインがそれ自体のキャッシュ内で無効にされることをノード存在ベクトル内の各プロセッサノードが確認するまで、ビジー状態にとどまるステップとを含む、請求項３に記載の方法。
【請求項７】
共有メモリ多重プロセッサコンピュータのためのキャッシュコヒーレンシディレクトリであって、
各キャッシュ可能な記憶場所に関連したデータ構造を含み、データ構造は、排他的状態、共有状態、アンキャッシュ状態、ビジー状態、ビジーアンキャッシュ状態、ロック状態、およびペンディング状態を表す状態値を記憶するための場所を含み、ビジー状態およびペンディング状態は、キャッシュラインが現在１つ以上の他のプロセッサによって用いられている間、プロセッサによる将来の使用に備えるためにキャッシュラインを共働して確保する、キャッシュコヒーレンシディレクトリ。
【請求項８】
キャッシュ記憶場所にアクセスするための要求に応答して、データ構造内に記憶される、要求される記憶場所に関連した状態値を判断するための手段と、
キャッシュ記憶場所にアクセスするための要求に応答して状態値に基づいてキャッシュコヒーレンシ動作を発行するための手段と、
キャッシュ記憶場所にアクセスするための要求に応答して、予め規定される順序で表される状態間で状態値を遷移させるための手段とをさらに含む、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項９】
排他的状態は、キャッシュラインへの排他的アクセスを有するノードが０または１つであることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１０】
共有状態は、キャッシュラインへの共有アクセスを有するノードが０または１つ以上であることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１１】
アンキャッシュ状態は、キャッシュラインへの排他的または共有アクセスを有するノードが０であることを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１２】
ビジーおよびビジーアンキャッシュ状態は、キャッシュラインが排他的状態または共有状態のいずれかから遷移したことを表し、さらにはキャッシュラインが未処理のキャッシュコヒーレンシ回答を有することを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１３】
ペンディング状態は、キャッシュラインが排他的または共有もしくはビジー状態にあった間にキャッシュラインに対する要求を示した別のノードのために確保されている排他的状態からキャッシュラインが解放されたことを表す、請求項７に記載のキャッシュコヒーレンシディレクトリ。
【請求項１４】
計算システムであって、
通信バスに結合される複数のプロセッサノードと、
各プロセッサノード内のキャッシュメモリとを含み、キャッシュメモリは複数のキャッシュラインを含み、前記計算システムはさらに、
複数のキャッシュ可能な場所を含む共有メモリと、
共有メモリの各キャッシュ可能な場所に関連した状態機械とを含み、状態機械は、関連のキャッシュ可能な場所が第１のプロセッサノードによって現在用いられ、さらには第２のプロセッサノードによる将来の使用に備えるために確保されていることを表す状態を実現し、状態機械はまた、関連のキャッシュラインが現在ビジーであることを表す値を保持するビジー状態と、どのプロセッサが関連のキャッシュラインを制御するのかという表示と、どのプロセッサが将来用いるためにキャッシュラインを確保しているのかという表示とを含む、計算システム。
【請求項１５】
状態機械はさらに、関連のキャッシュラインが現在ロックされていて、第２のプロセッサからの表示によってのみペンディング状態から遷移され得ることを表す値を保持するペンディング状態を含む、請求項１４に記載の計算システム。
【請求項１６】
状態機械は、関連の記憶場所が他のいずれかのプロセッサによってキャッシュ可能である状態に入ることなしに、第１のプロセッサによる排他制御を表す状態から、第２のプロセッサの排他制御を表す状態へと遷移する、請求項１４に記載の計算システム。
【請求項１７】
各プロセッサノードは、共有フロントサイドバスによって互いと結合される２つ以上のプロセッサを含む、請求項１４に記載の計算システム。
【請求項１８】
各プロセッサノードのフロントサイドバスを通信バスに結合するブリッジ回路をさらに含む、請求項１７に記載の計算システム。
【請求項１９】
計算システムであって、
通信バスに結合される複数のプロセッサノードと、
各プロセッサノード内のキャッシュメモリとを含み、キャッシュメモリは複数のキャッシュラインを含み、前記計算システムはさらに、
複数のキャッシュ可能な場所を含む共有メモリと、
共有メモリの各キャッシュ可能な場所に関連付けられた状態機械とを含み、状態機械は、関連付けられたキャッシュ可能な場所が第１のプロセッサノードによって現在使用されており、さらには第２のプロセッサノードによる将来の使用に備えるために確保されていることを表す状態を実現する、計算システム。
【国際調査報告】
2004505346.tif 000049