(57)【特許請求の範囲】
【請求項１】
複数のメモリキャッシュと、
前記複数のメモリキャッシュにおけるラインのうち、メモリ内の対応するラインが同一でない可能性があるラインであって、該キャッシュによって所有されているラインのそれぞれについて、該ラインのアドレス参照、および、該ラインをどのキャッシュが所有するかを示す標示、を含むリストと、を備えており、
前記キャッシュによって所有されているラインは、該ラインを所有する該キャッシュによって変更されたラインおよび変更される可能性のあるラインであり、
前記リストは、共有されるラインおよびキャッシュされていないラインについてのアドレス参照と、該アドレス参照に対応するデータと、を含まないよう構成される、
コンピュータシステム。
【請求項２】
前記アドレス参照は、タグである、請求項１に記載のコンピュータシステム。
【請求項３】
どのキャッシュがラインを所有するかの前記標示は、１ビットで表される、請求項１に記載のコンピュータシステム。
【請求項４】
前記リストが保持することができる前記アドレス参照の数は、前記複数のメモリキャッシュに格納されることができるラインの合計数よりも実質的に少ない、請求項１に記載のコンピュータシステム。
【請求項５】
前記リストは、前記コンピュータシステム内のすべての装置によって共有される１つのリストである、請求項１に記載のコンピュータシステム。
【請求項６】
前記メモリ内のデータのコピーを要求することができるすべての装置は、前記リストのローカルコピーを保持する、請求項１に記載のコンピュータシステム。
【請求項７】
コンピュータシステムにおいてキャッシュコヒーレンシを維持するための方法であって、
キャッシュによって所有されているラインのそれぞれについて、該ラインのアドレス参照を、リストに登録するステップであって、該キャッシュによって所有されているラインは、該ラインを所有するキャッシュによって変更されたラインまたは該キャッシュによって変更される可能性のあるラインである、ステップと、
共有されるラインおよびキャッシュされていないラインについてのアドレス参照については、前記リスト内に登録しないステップと、
或るラインの所有権が変更されるときにのみ、前記リストを更新するステップと、
を含む方法。
【請求項８】
或るラインがメモリに書き込まれるとき、前記リストから、該ラインに対するアドレス参照を削除するステップ、
をさらに含む、請求項７に記載の方法。
【請求項９】
或るラインが前記リストに登録されておらず、かつ、該ラインの所有権が或る装置によって要求されたとき、該リストに新しいエントリを割り当てるステップ、
をさらに含む、請求項７に記載の方法。
【請求項１０】
前記リストに新しいエントリを割り当てる前記ステップはさらに、
前記リストから他のラインを除去するステップと、
前記除去された該他のラインをメモリにコピーするステップと、
を含む、請求項９に記載の方法。
【請求項１１】
或るラインが、所定時間より長い間前記リスト内に存在しているとき、該リストから、該ラインへのアドレス参照を削除するステップ、
をさらに含む、請求項７に記載の方法。
【請求項１２】
前記リストが満杯になるのを防ぐように、該リストが満杯でない場合であっても、該リストから、或るラインへのアドレス参照を削除するステップ、
をさらに含む、請求項７に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータシステムのキャッシュメモリシステムに関し、より具体的には、マルチプロセッサコンピュータシステムのキャッシュメモリシステムのためのコヒーレンシプロトコルに関する。
【０００２】
【従来の技術】
大部分のコンピュータシステムは、多重レベル階層のメモリシステムを用いており、そのメモリシステムは、最も高いレベルの階層では相対的に高速であるが、コストが高く、容量が制限されており、最も低いレベルの階層では、低速であるが、コストも低く、容量も大きい。典型的には、該階層は、キャッシュと呼ばれる、プロセッサの集積回路内に物理的に統合されているか、または高速化のためにプロセッサに物理的に近い位置に実装される小型で高速のメモリを備える。個別の命令キャッシュおよびデータキャッシュが存在する場合がある。また、多重レベルのキャッシュが存在する場合もある。
【０００３】
あるキャッシュと次に低いレベルのメモリ階層との間で転送することができる最小のメモリ量は、ライン、ブロックあるいはページと呼ばれる。本特許明細書では「ライン」という用語が用いるが、本発明は、ブロックまたはページを用いるシステムにも同様に適用されうる。一般に、キャッシュにインデックスを付けるためにラインアドレスのビットのうちのいくつかを用いており、各物理アドレスのビットの残りは、データとともに、タグとして格納される。
【０００４】
多くのコンピュータシステムは複数のプロセッサを用いており、各プロセッサは多重レベルのキャッシュを備える場合がある。キャッシュの中には、複数のプロセッサによって共有されるものもある。すべてのプロセッサおよびキャッシュは、共通のメインメモリを共有する場合がある。特定のラインが、複数のプロセッサについてメモリ内およびキャッシュ階層内に同時に存在する場合がある。キャッシュ内のラインのすべてのコピーは同一でなければならず、この特性をコヒーレンシと呼ぶ。複数のプロセッサについてコヒーレンシを維持するためのプロトコルは、キャッシュコヒーレンスプロトコルと呼ばれる。プロセッサがラインの内容を変更した場合、該１つの変更されたコピーのみが有効であり、キャッシュおよびメモリ内の他のすべてのコピーは更新または無効化されなければならない。メモリ内のラインのコピーがキャッシュ内のコピーと同一でない場合には、メモリ内のそのラインは「ステイル（stale）」ラインと呼ばれ、キャッシュ内のラインは「ダーティ（dirty）」であると呼ばれる。変更されたラインの「最新のコピー」は、最後に変更されたコピーである。そのラインがキャッシュされているが変更されていない場合には、メモリ内のコピーも含めていずれのコピーも最新のコピーとなりうる。そのラインがキャッシュされていない場合には、あるラインの最新のコピーはメモリ内に存在する。
【０００５】
キャッシュコヒーレンスプロトコルは一般に、それぞれのキャッシュされたラインを、複数の状態のうちの１つにする。１つの一般的なアプローチは、キャッシュ内の各ラインに対して３つのとりうる状態を用いる。あらゆるラインがキャッシュ内に置かれる前に、すべてのエントリは、「無効状態」と呼ばれるデフォルト状態にある。キャッシュされていない物理的なラインがキャッシュ内に置かれると、キャッシュ内のそのエントリの状態は、無効状態から「共有状態」に変更される。あるラインがキャッシュ内で変更されると、メモリにおいても直ちに変更されることができる（これは、ライトスルーと呼ばれる）。代替的に、キャッシュは、キャッシュ内の変更されたラインが無効化されるか、または置き換えられる場合にのみ、該変更されたラインをメモリに書き込むことができる（ライトバックと呼ばれる）。ライトバックキャッシュの場合、そのキャッシュ内のラインが変更されたとき、そのキャッシュ内のエントリの状態は、「変更された状態」に変更される。ここに記載される３状態の割当ては、３つの各状態の最初の文字をとって、ＭＳＩプロトコルと呼ばれる場合がある。
【０００６】
一般的な変形形態によって、１つの状態が追加される。その変形形態では、物理的なラインがキャッシュにコピーされるときに、他のすべてのキャッシュ内に該ラインのコピーが存在しない場合には、該ラインは「排他的な」状態に置かれる。用語「排他的」は、厳密に１つのキャッシュ階層がそのラインのコピーを有することを意味する。あるラインが、第１のプロセッサのためのキャッシュ階層において「排他的な」状態にあり、第２のプロセッサが同じラインを要求した場合には、そのラインは２つのキャッシュ階層にコピーされることになり、それぞれのキャッシュのエントリの状態は「共有状態」に設定される。ここに記載された４状態の割当ては、４つの各状態の最初の文字をとって、ＭＥＳＩプロトコルと呼ばれることがある。他に多くの変形形態が存在する。
【０００７】
キャッシュが、ラインを変更するための許可を有する場合には、何らかのさらなるコヒーレンシのトランザクションを発行することなく、ラインを「所有する」。キャッシュがラインを所有する場合には、そのラインは潜在的にダーティであり（変更可能であり）、実際にダーティである（変更された）場合がある。ラインには、１つの「所有者」のみが存在することができる。ラインの現在の所有者が該ラインを変更した場合には、該ラインの最新のコピーは常に現在の所有者から得られる。ラインが変更されなかった場合には、メモリ内のコピーも含めていずれのコピーも該ラインの最新のコピーでありうる。任意のキャッシュコヒーレンスプロトコルにおいて、キャッシュラインの最新のコピーは、（現在の所有者があれば）現在の所有者から抽出され、そのデータのコピーが要求者に送られなければならない。そのラインが変更されることになる場合には、所有権は要求者によって取得され、共有されたコピーのすべてが無効化されなければならない。
【０００８】
ラインの所有者の場所を判定するために３つの一般的なアプローチがあり、多くの変形形態および混成形態が存在する。スヌーピングプロトコルまたはスヌープ型プロトコルと呼ばれる１つのアプローチでは、所有者は未知であり、要求されたラインの最新のコピーの場所を判定するために、すべてのキャッシュが問合せ（スヌープ）されなければならない。システム内の任意の装置による、あるキャッシュラインにアクセスするためのすべての要求は、システム内のすべてのキャッシュに転送される。結果として、該ラインの最新のコピーの場所が特定され、コピーが要求者に供給される。
【０００９】
ディレクトリ型プロトコルと呼ばれる第２のアプローチでは、メモリシステム内のすべてのラインの状態についての情報を保持するためのメモリが設けられる。たとえば、メモリ内のすべてのラインについて、ディレクトリは、それぞれのキャッシュ階層について、キャッシュ階層がラインのコピーを有するか否かを示す１ビットと、該キャッシュ階層が所有権を有するか否かを示す１ビットとを含むことができる。あるキャッシュラインにアクセスするためのすべての要求に対して所有者を判定するために、そのディレクトリが調査されなければならない。その後、そのラインの最新のコピーが抽出され、要求者に送られる。典型的には、ディレクトリのタグおよび状態ビットはメインメモリに格納される。状態情報の要求がメインメモリを循環し、これには、メインメモリの待ち時間が生ずる。
【００１０】
第３のアプローチはグローバルコヒーレンシフィルタであり、これは、キャッシュシステム内のすべてのラインについてタグを有する。コヒーレンシーフィルタは、システム内のすべてのキャッシュについて、集中的に格納される第のセットのタグを有するスヌープシステムである。キャッシュラインの要求は、すべてのキャッシュではなく、この中央のフィルタに転送される。コヒーレンシーフィルタのためのタグは、典型的には小型で高速なメモリに格納される。
【００１１】
１つのバスまたは数本のみのバスを有する比較的小型のシステムの場合、スヌープ型プロトコルが最も良好な性能を与える。しかしながら、スヌープ型システムではバスのトラフィックが増加し、大規模なシステムの場合には、スヌープトラフィックが全体的な性能を制限するようになる。ディレクトリ型システムでは、ラインを抽出するのに必要な時間（待ち時間）が増加するが、スヌープ型システムに比べて必要なバストラフィックが少ない。大規模な多重バスシステムの場合、バストラフィックは待ち時間よりも重要な場合があり、ディレクトリ型システムは典型的には最も良好な全体性能を与える。多くのコンピュータシステムは、スヌープ型プロトコルとディレクトリ型プロトコルとからなる、ある種の混成プロトコルを用いる。たとえば、多重バスシステムの場合、各ローカルバス上のコヒーレンシについてはスヌープ型プロトコルが用いられ、バス間のコヒーレンシについてはディレクトリ型プロトコルが用いられる場合がある。
【００１２】
【発明が解決しようとする課題】
改善されたキャッシュコヒーレンスプロトコル、具体的には、大規模な多重バスマルチプロセッサシステムのための改善されたキャッシュコヒーレンスプロトコルが必要とされている。
【００１３】
【課題を解決するための手段】
本発明によるコンピュータシステムは、キャッシュが所有権を有するシステム内のすべてのキャッシュラインについてのタグのリスト（グローバルオーナーシップタグリスト（ＧＯＴＬ）と呼ぶ）を保持する。すなわち、ＧＯＴＬ内の各タグについて、対応するラインはダーティか、または潜在的にダーティ（変更可能）である。ある装置によってあるラインが要求されたならば、そのラインのタグが、ＧＯＴＬに対して比較される。要求されたラインが要求者によって共有可能であるかまたは要求者によって所有されるかによって、さらに要求されたラインがＧＯＴＬ内にあるかどうかによって、（１）共有可能で、ＧＯＴＬミス、（２）共有可能で、ＧＯＴＬヒット、（３）所有され、ＧＯＴＬミス、（４）所有され、ＧＯＴＬヒット、の４つのケースが存在する。ケース（１）の場合、そのラインはＧＯＴＬには存在せず、キャッシュには所有権がなく、そのため該ラインはメモリから抽出される。共有可能なラインについてＧＯＴＬを更新する必要はない。ケース（２）の場合、要求側装置がラインを要求するが所有権がなく、そのラインはＧＯＴＬ内にある。キャッシュの中には所有権を有するものがあり、最新のデータが要求者に返送される。所有者が、コヒーレンシトランザクションを発行することなくそのラインを変更する場合があるので、そのラインが所有されたままである場合にはコヒーレンシを侵害する可能性がある。よって、所有権は取り消されなければならない（ＧＯＴＬ内のエントリが削除される）。ケース（３）の場合、要求側装置は所有権を要求し、そのラインはメモリから抽出され、ＧＯＴＬ内に新しいエントリのための空間が割り当てられ、そのラインが要求者によって現在所有されていることを示すようにする。ケース（４）の場合、要求側装置は所有権を要求し、ラインはＧＯＴＬ内に存在する。キャッシュの中には所有権を有するものがあり、データの最新のコピーおよび所有権の両方が要求者に転送される。ケース（４）の場合、所有権は変更され、新しい所有権を示すようＧＯＴＬが更新される。
【００１４】
１つの中央ＧＯＴＬを設けてもよい。代替的に、ＧＯＴＬを分散して設けてもよい。後者の場合、メモリデータのコピーを要求することができるすべての装置（たとえば、プロセッサ、バスブリッジおよびスヌープフィルタ）が、ＧＯＴＬのローカルな同一コピーを保持する。１つのＧＯＴＬ内のタグの数は、システム内のすべてのキャッシュにおけるラインの数より著しく少ない。限定されたサイズのＧＯＴＬの場合、既存のタグは、新しいタグのための空間を確保するために取り除かれることが必要な場合がある。取り除かれたタグに関連するラインは、そのラインが実際に変更された場合には、メモリにライトバックされなければならない。典型的には、１つのＧＯＴＬは、ディレクトリまたはグローバルコヒーレンシフィルタより著しく小さくすることができ、ディレクトリ型システムまたはグローバルコヒーレンシフィルタシステムよりも良好な性能を提供することができる。さらに、メインメモリのサイズが変更された場合であっても、またはキャッシュサイズが変更された場合であっても、ＧＯＴＬのサイズは固定したままにすることができる。これは、ＧＯＴＬが、システム内のすべてのキャッシュラインではなく、システム内の変更された、または変更可能なラインのみを含むためである。
【００１５】
【発明の実施の形態】
任意のキャッシュコヒーレンスプロトコルの場合、要求されたラインが所有されていない（ダーティでも潜在的にダーティでもない）場合には、任意のコピー、特にメインメモリ内のコピーで十分である。ラインがダーティにされる可能性がある場合には、所有権を、（現在の所有者が存在するならば）現在の所有者から要求側装置に移さなければならない。ラインが既にダーティである場合には、最新のコピーが要求者に返送され、所有権を、現在の所有者から要求側装置に移さなければならない。したがって、あるラインがキャッシュによって所有されているか否かは、多重キャッシュシステムのコヒーレンスについて必要とされる情報の不可欠な部分である。コヒーレンスの目的のために、キャッシュされたラインが２つのみのメタ状態、すなわち所有された状態あるいは共有可能な状態を有するシステムについて考える。共有可能なキャッシュラインのすべては、いかなる装置によっても所有されない。所有されたキャッシュラインのすべては、潜在的に変更可能である。ある装置が、所有されたラインおよびその所有者のリストにアクセスすると、その装置は、コヒーレンスの目的のために各ラインの状態について知る必要があるすべての情報を効率的に知ることができる。
【００１６】
本発明によれば、コンピュータシステムは、システム内のすべての所有されたキャッシュラインについて、タグおよびその所有者のリスト（グローバルオーナーシップタグリスト（ＧＯＴＬ）と呼ぶ）を保持することができる。システムの中には、メタ状態である「所有された状態」が単一状態に対応するものもある。たとえば、ＭＳＩシステムの場合、ＧＯＴＬは、「変更された状態」を有するシステム内のすべてのラインのリストを保持することができる。ＭＥＳＩシステムの場合、「排他的な」状態のラインが変更されたとき、その状態は「変更された状態」にローカルに変更される。しかしながら、コピーは１つしか存在しないので、状態の変化をシステムの他の部分に知らせる必要はない。ＭＥＳＩあるいは類似のシステムの場合、ラインが「排他的な」状態に割り当てられたときには、ＧＯＴＬはそのリストに該ラインを追加する必要がある。これは、そのラインが後に、システムの残りの部分に通知することなく変更される場合があるからである。したがって、ＭＥＳＩシステムの場合、コンピュータシステムは、「排他的な」状態または「変更された」状態を有するシステム内のすべてのラインのリストを保持することができる。
【００１７】
１つの中央ＧＯＴＬが設けることもできる。代替的に、ＧＯＴＬを分散させて設け、メモリデータのコピーを要求することができるすべての装置が、ＧＯＴＬの同一のコピーを保持することができる。メモリデータのコピーを要求することができる装置には、例として、プロセッサ、バスブリッジおよびスヌープフィルタが含まれる。いずれの実施形態の場合でも、あるラインがある装置によって要求された場合には、そのラインについてのタグが、ＧＯＴＬ（中央リスト、または要求側装置によって保持されるリスト）に対して比較される。
【００１８】
図１および図２は、４つのとり得る状態を示す。図１では、ある装置がラインを要求するが、所有権は要求しない（ステップ１００）。タグがＧＯＴＬ内にない場合には（テスト１０２）、キャッシュが該ラインを所有しておらず、該ラインはメモリからコピーされる（ステップ１０４）。該ラインがＧＯＴＬ内にある場合には（かつ、要求者が所有者でない場合には）、そのラインの最新のコピーが取得される（ステップ１０６）。所有者は、コヒーレンシトランザクションを発行することなくラインを変更することができるので、そのラインが所有されたままである場合には、コヒーレンシを侵害する可能性がある。したがって、ＧＯＴＬ内のエントリは取り除かれ、そのラインはメモリにコピーされる（ステップ１０８）。図２では、ある装置がラインおよび該ラインの所有権を要求する（ステップ２００）。タグがＧＯＴＬ内にない場合には（テスト２０２）、そのラインはメモリからコピーされる（ステップ２０４）。さらに、要求側装置が今やそのラインの所有者であるので、新しい所有権を示すために、ＧＯＴＬに新しいエントリが割り当てられなければならない（ステップ２０６）。新しいエントリを割り当てるために、既存のエントリを取り除かなければならない場合があることに留意されたい。これについては後に詳細に説明される。タグがＧＯＴＬ内にある場合には（かつ、要求者が所有者でない場合には）、そのラインの最新のコピーを取得する（ステップ２０８）。いずれの場合にも、所有権は移され（ステップ２１０）、新しい所有権を示すようＧＯＴＬが更新される（ステップ２１２）。
【００１９】
図３の（Ａ）は、分散されたＧＯＴＬと多重バスとを有する、例示的なキャッシュコヒーレントな共有メモリを備えたマルチプロセッサコンピュータシステムを示す。図３の（Ａ）のコンピュータシステムは複数のノードを有しており、各ノードは、ＣＰＵ３００と、キャッシュメモリ３０２と、ＧＯＴＬ３０４とを備える。すべてのノードはメインメモリ３０６を共有し、メモリトランザクションについてメモリバス３０８を共有する。図３の（Ａ）では、コヒーレンシバストラフィックは、別個のコヒーレンシバス３１０に移される。コヒーレンシバス３１０は、代替的に、トランザクションを順序付けることができるネットワークまたは任意の相互接続システムであることができ、各ＧＯＴＬは同じ順序のトランザクションを見ることとなる。複数のＣＰＵが１つのキャッシュメモリを共有することができ、複数のＣＰＵが１つのＧＯＴＬを共有することもできる。図３の（Ｂ）は、図３の（Ａ）の場合と同じ２バスシステムを示すが、コヒーレンシバス３１０上に中央ＧＯＴＬ３１２を有する。
【００２０】
図４の（Ａ）は、分散されたＧＯＴＬを有する、他の例示的なシステムを示す。図４の（Ａ）のコンピュータシステムは複数のノードを有し、各ノードは、ＣＰＵ４００と、キャッシュメモリ４０２と、ＧＯＴＬ４０４とを備える。すべてのノードがメインメモリ４０６を共有する。コヒーレンシバストラフィックは、専用のコヒーレンシバス４０８を用いる。ノードとメインメモリとの間の通信は、ポイント・ツー・ポイントである。複数のＣＰＵが１つのキャッシュメモリを共有することができ、複数のＣＰＵが１つのＧＯＴＬを共有することもできる。図４の（Ｂ）は、図４の（Ａ）と同じポイント・ツー・ポイントのメモリ通信を示すが、コヒーレンシバス４０８上に中央ＧＯＴＬ４１０を有する。ポイント・ツー・ポイント通信を用いて、すべてのノードが同時にメインメモリ４０６にアクセスすることができる。図４の（Ａ）および図４の（Ｂ）のようなシステムによって、メモリトランザクションの大部分が、グローバルにスヌープすることを必要とせず、かつスヌープレスポンスを待つことを必要せずに、メモリに直接送信されることが可能になる。さらに、グローバルなアービトレーション（arbitration；調停）およびスヌープの待ち行列による遅延が低減される。一般に、ポイント・ツー・ポイント技術は、バス技術より高速に実施されることができる。したがって、図４の（Ａ）および図４の（Ｂ）のようなシステムは、図３の（Ａ）および図３の（Ｂ）のようなシステムと比べて、かなり改善された性能を有することができる。
【００２１】
中央ＧＯＴＬ構成の場合、ラインの状態を求めるために何らかのバストラフィックが必要とされるが、これはメモリを循環することなく、メモリの読出しより短い待ち時間で行うことができる。共有されたラインの他のコピーがまだ使用中であることを示すためにタグを更新するようメモリコントローラまたはフィルタに要求するディレクトリ型システムまたはグローバルコヒーレンシフィルタとは対照的に、ＧＯＴＬ型システムでは、該共有されたラインの単なる読出しにおいてはリストを更新する必要はない。ＧＯＴＬが更新される必要があるのは、ラインが所有から共有へまたは共有から所有へ遷移するときか、または所有権が変更されるときだけであり、コヒーレンシバス上で生じなければならないトランザクションのみである。したがって、中央のＧＯＴＬは、ディレクトリ型システムおよびグローバルコヒーレンシフィルタシステムよりも性能が改善される。
【００２２】
分散型のＧＯＴＬ構成の場合、同報通信（ブロードキャスト）トラフィックとなるのは、所有権の要求だけである。分散型ＧＯＴＬの実施形態では、所有されたラインを抽出する場合には、システムは、該ラインの状態を求めるためのさらなるバストラフィックを必要とせずに、データおよび所有権の転移を指示することができる。したがって、分散型ＧＯＴＬシステムでは、ＧＯＴＬのコピーを複数持つという犠牲をはらうことにより、中央ＧＯＴＬシステムよりも性能が改善される。
【００２３】
ラインの所有権が変更されるとき、以前の所有者は、そのラインのコピーを無効化しなければならない。ＧＯＴＬに新しいラインエントリが追加されるときには必ず、すべてのキャッシュが、該ラインのローカルコピーを無効化しなければならない。分散型ＧＯＴＬの場合には、ＧＯＴＬに関連する各キャッシュは、ラインの挿入要求の同報通信を観測した際に、該ラインのコピーを無効化する。こうして、割当てトランザクションの受信によって、ローカルバス上に無効トランザクションが起動される。
【００２４】
上記のように、ＧＯＴＬは、ディレクトリおよびグローバルコヒーレンシフィルタに対して性能を改善する。代替形態に対する、ＧＯＴＬのさらに重要な利点はサイズである。ＧＯＴＬを、ディレクトリまたはグローバルコヒーレンシフィルタよりも著しく小さくすることができる。ディレクトリは、メモリ内の全ラインを参照することができなければならない。グローバルコヒーレンシフィルタは、すべてのキャッシュ内の全ラインを参照しなければならない。対照的に、ＧＯＴＬは、所有されたラインのみを参照すればよい（しかも、キャッシュされたラインは所有されていないものが多い）。さらにメモリが追加される場合には、ディレクトリはサイズを拡張しなければならない。キャッシュが追加される場合には、グローバルコヒーレンシフィルタはサイズを拡張しなければならない。対照的に、ＧＯＴＬのサイズは所有されるラインの数を制限することができるので、メモリおよびキャッシュが追加される場合であっても、ＧＯＴＬは１つのサイズのまま固定することができる。
【００２５】
制限されたサイズのＧＯＴＬが満杯になる場合がある。該リストが満杯である場合には、新しく所有されたラインのための空間を確保するために、以前に所有されたラインを取り除かなければならない。これは、キャッシュの場合によく知られている問題であり、多くの知られている置換えアルゴリズムを用いて、どのラインを置き換えるかを判定することができる。たとえば、最も前に所有されたラインを取り除くことができ（先入れ先出し）、または擬似ランダムに取り除くこともでき、その他の方法もある。取り除かれたタグに関連するラインは、実際に変更された場合にはメモリにライトバックされなければならない。ＧＯＴＬが分散され、すべてのＧＯＴＬが同じ取り除きアルゴリズムを用いる場合には、すべてのＧＯＴＬが同じ挿入要求を見ることとなるので、付加的な同報通信を行う必要もなく、すべてが同じラインを取り除くこととなる。
【００２６】
満杯のリストのための置換えアルゴリズムに加えて、リストが満杯になるのを防ぐことができるようにする方式を用いてもよい。たとえば、所有されたラインは、特定のイベントが生じたときにメモリにライトバックされることができる。たとえば、各エントリの存在期間をモニタすることができ、指定された期間よりも長い間リスト内に存在している場合に、そのラインを取り除く。代替的に、アイドル時間中に、リストが満杯でない場合であっても、置換えアルゴリズムが、メモリにライトバックされるべき所有されたラインを選択して、対応するタグをリストから削除することができる。
【００２７】
他のキャッシュコヒーレンスプロトコルと同様に、ＧＯＴＬ型システムは、同時に生じた同じラインについての要求を調停（arbitrate）しなければならない。所有権が遷移する特定の順序は、すべての装置が従わなければならない。スヌープ型システムでは、アービトレーションおよび順序付けは、２つの要求が衝突するバスによって実施される。ディレクトリ型システムでは、アービトレーションおよび順序付けはタグのマネージャによって実施される。ＧＯＴＬ型システムは、アービトレーションおよび順序付けについては、スヌープ型システム、ディレクトリ型システム、またはその混成システムのいずれかを用いる。中央ＧＯＴＬ型システムは、順序を調整し制御するために、コヒーレンシバスアーキテクチャまたはメモリコントローラのような中央リソースを用いることができる。分散型のＧＯＴＬ型システムは、業界の標準的なアービトレーション技術を用いることができる。
【００２８】
本発明に関する上記の記載は、例示および説明するために提供されている。それは、本発明を余すところなく述べることや、本発明を厳密に開示された形態に限定することを意図しているわけではなく、他の変更形態および変形形態が、上記の教示に鑑みて実現可能である。その実施形態は、本発明の原理およびその実用的な応用形態を最もわかりやすく説明し、それにより、他の当業者が、意図している特定の使用形態に適するように、種々の変更形態および変形形態で本発明を最もよく利用できるようにするために選択され、記載されている。特許請求の範囲は、本発明の他の代替の実施形態を含むものと解釈されるべきである。
【００２９】
本発明は、以下の実施態様を含む。
【００３０】
（１）複数のメモリキャッシュ（３０２、４０２）と、
メモリ（３０６、４０６）内の対応するラインが同一でない可能性があるラインについて、前記複数のメモリキャッシュ内のアドレス参照と、どのキャッシュがそれぞれのラインを所有するかの標示とを含むリスト（３０４、３１２、４０４、４１０）とを備え、
前記リストは、共有されるラインおよびキャッシュされていないラインについてのアドレス参照と、該アドレス参照に対応するデータとを含まないコンピュータシステム。
【００３１】
（２）前記アドレス参照はタグである上記（１）に記載のコンピュータシステム。
【００３２】
（３）どのキャッシュがラインを所有するかの前記標示は、１ビットである上記（１）に記載のコンピュータシステム。
【００３３】
（４）前記リストが保持することができる前記アドレス参照の数は、前記複数のメモリキャッシュに格納されることができるラインの合計数より実質的に少ない上記（１）に記載のコンピュータシステム。
【００３４】
（５）前記リストは、前記コンピュータシステム内のすべての装置によって共有される１つのリスト（３１２、４１０）である上記（１）に記載のコンピュータシステム。
【００３５】
（６）メモリデータのコピーを要求することができるすべての装置は、前記リストのローカルコピーを保持する上記（１）に記載のコンピュータシステム。
【００３６】
（７）コンピュータシステムにおいてキャッシュコヒーレンシを保持するための方法であって、リスト（３０４、３１２、４０４、４１０）内に、所有されるすべてのラインについてのアドレス参照を入力するステップと、
共有されるキャッシュおよびキャッシュされていないラインについてのアドレス参照は、前記リスト内に入力しないステップと、
ラインの所有権が変更されるときにのみ、前記リストを更新するステップ（２１２）と、を含む方法。
【００３７】
（８）ラインがメモリに書き込まれるとき、前記リストから、該ラインに対するアドレス参照を削除するステップ（１０８）をさらに含む上記（７）に記載の方法。
【００３８】
（９）ラインが前記リストにおいて参照されておらず、該ラインの所有権が装置によって要求されるとき、該リストに新しいエントリを割り当てるステップ（２０６）をさらに含む上記（７）に記載の方法。
【００３９】
（１０）前記リストに新しいエントリを割り当てる前記ステップはさらに、
前記リストからラインを除去するステップと、
前記除去されたラインをメモリにコピーするステップとを含む上記（９）に記載の方法。
【００４０】
（１１）前記ラインが、指定された時間より長い間前記リスト内に存在しているとき、該リストから、該ラインへのアドレス参照を削除するステップをさらに含む上記（７）に記載の方法。
【００４１】
（１２）前記リストが満杯になるのを防ぐことができるように、該リストが満杯でない場合でも、該リストから、ラインへのアドレス参照を削除するステップをさらに含む上記（７）に記載の方法。
【００４２】
【発明の効果】
本発明によれば、大規模な多重バスマルチプロセッサシステムのための改善されたキャッシュコヒーレンスプロトコルを実現することができる。
【図面の簡単な説明】
【図１】本発明による、ＧＯＴＬを有するシステムにおいて、所有権を要求することを伴わないライン要求の流れ図。
【図２】本発明による、ＧＯＴＬを有するシステムにおける、所有権を要求する流れ図。
【図３】別個のコヒーレンシーバスを有し、ＧＯＴＬを有する例示的なコンピュータシステムのブロック図。
【図４】メインメモリへのポイント・ツー・ポイント接続を有し、ＧＯＴＬを有する第２の例示的なコンピュータシステムのブロック図。
【符号の説明】
３０２、４０２  キャッシュメモリ
３０４、３１２、４０４、４１０  リスト
３０６、４０６  メモリ
【図１】
0004008224.tif 000002
【図２】
0004008224.tif 000003
【図３】
0004008224.tif 000004
【図４】
0004008224.tif 000005