(57)【要約】【課題】コンピュータ・システム内でキャッシュ整合性を維持するためのメカニズムおよび方法を提供すること。【解決手段】要求が、キャッシュ・ブロックへの排他的アクセスを能動デバイスＤ１から能動デバイスＤ２へ転送すると、Ｄ１からデータを送信することがそのブロックへのＤｌのアクセス権を終了させ、Ｄ２でのデータの受信がアクセス権を開始させる。要求がＤ１でのキャッシュ・ブロックへの排他的アクセスをＤ２との共用状態に変更すると、Ｄ１からデータを送信することがＤ１の排他的アクセス権を終了させ、Ｄ２でのデータの到達がそのアクセス権を開始させる。要求が、共用状態からＤ２での排他的アクセスにキャッシュ・ブロックを転送すると、Ｄ２以外のすべての能動デバイスとそのキャッシュ・ブロックを所有する能動デバイスでのアクセス権がその要求の受信時に終了し、キャッシュ・ブロックを所有する能動デバイスのアクセス権が、データを送信した時に終了し、Ｄ２での排他的アクセス権がＤ２が以前の所有者からデータを受信した時に開始する。【選択図】    図８
2005148771.tif 000002
【特許請求の範囲】
【請求項１】
システム・メモリと、
前記システム・メモリ内に格納されたデータにアクセスするよう構成された第１の能動デバイスであって、その第１の能動デバイスによってアクセスされたデータを格納するよう構成された第１のキャッシュを備える第１の能動デバイスと、
前記第１の能動デバイスと前記システム・メモリの間でアドレス・トランザクションを伝達するためのアドレス・ネットワークと、
前記第１の能動デバイスと前記システム・メモリの間でデータ・トランザクションを伝達するためのデータ・ネットワークとを有し、
所与のブロックに対応するアクセス権が、対応するデータ・パケットが前記データ・ネットワークを通って前記第１のキャッシュによって受信されることに応答して前記第１のキャッシュ遷移に割り当てられるコンピュータ・システム。
【請求項２】
第２のキャッシュを含む第２の能動デバイスをさらに備え、別のブロックに対応するアクセス権が、別の対応するデータ・パケットが前記データ・ネットワークを通って前記第２のキャッシュによって受信されることに応答して前記第２のキャッシュ遷移に割り当てられる請求項１に記載のコンピュータ・システム。
【請求項３】
前記所与のブロックに対応する所有権状態が、対応するアドレス・トランザクションを受信することに応答して前記第１のキャッシュ遷移に割り当てられる請求項２に記載のコンピュータ・システム。
【請求項４】
前記対応するアドレス・トランザクションが、前記アドレス・ネットワークを通って前記第１のキャッシュによって受信される請求項３に記載のコンピュータ・システム。
【請求項５】
前記対応するアドレス・トランザクションがｒｅａｄ−ｔｏ−ｏｗｎトランザクションである請求項４に記載のコンピュータ・システム。
【請求項６】
前記第１のキャッシュによって受信された前記対応するデータ・パケットが、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションに応答して前記第２の能動デバイスから前記データ・ネットワークを通って伝達される請求項５に記載のコンピュータ・システム。
【請求項７】
前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが、前記第１の能動デバイスによって開始され、前記アドレス・ネットワークを通って伝達される請求項６に記載のコンピュータ・システム。
【請求項８】
第３のキャッシュを含む第３の能動デバイスをさらに備え、対応するブロックのアクセス権が、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが前記アドレス・ネットワークを通って前記第３のキャッシュによって受信されることに応答して読取りアクセス権から無効アクセス権への前記第３のキャッシュ遷移に割り当てられる請求項７に記載のコンピュータ・システム。
【請求項９】
ブロックのアクセス権が、前記第２の能動デバイスが前記対応するデータ・パケットを送信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項７に記載のコンピュータ・システム。
【請求項１０】
前記ブロックに対応する所有権状態が、前記第２のキャッシュが前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションを受信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項９に記載のコンピュータ・システム。
【請求項１１】
前記アドレス・ネットワークが、順序づけられた同報プロパティを実施する請求項１に記載のコンピュータ・システム。
【請求項１２】
前記アドレス・ネットワークおよび前記データ・ネットワークが、同期された同報プロパティを実施する請求項１１に記載のコンピュータ・システム。
【請求項１３】
前記対応するデータ・パケットが、前記第１の能動デバイスによって開始されたｗｒｉｔｅ  ｓｔｒｅａｍトランザクションに応答して前記データ・ネットワークを通って前記第１のキャッシュに提供され、前記対応するデータ・パケットが、前記ｗｒｉｔｅ  ｓｔｒｅａｍトランザクションに対応するキャッシュ・ブロックの以前の所有者によって送信される請求項１に記載のコンピュータ・システム。
【請求項１４】
前記対応するデータ・パケットが、キャッシュ・ブロックに対応するデータを除外する符号化された応答である請求項１３に記載のコンピュータ・システム。
【請求項１５】
コンピュータ・システム内でコヒーレンシを維持するための方法であって、
第１のコヒーレンス要求を生成する第１の能動デバイスと、
アドレス・ネットワークを通って前記第１のコヒーレンス要求を伝達することと、
前記第１のコヒーレンス要求に応答してデータ・ネットワークを通って前記第１のコヒーレンス要求に対応するデータ・パケットを送信するデバイスと、
前記対応するデータ・パケットを受信することに応答して前記第１の能動デバイスにキャッシュされたブロックに対応するアクセス権を変更することとを含む方法。
【請求項１６】
前記デバイスが第２の能動デバイスである請求項１５に記載の方法。
【請求項１７】
前記対応するデータ・パケットを送信することに応答して前記第２の能動デバイスにキャッシュされた対応するブロックに対応するアクセス権を変更することをさらに含む請求項１６に記載の方法。
【請求項１８】
前記第１のコヒーレンス要求を受信する第３の能動デバイスをさらに備えた請求項１７に記載の方法。
【請求項１９】
前記第３の能動デバイスが前記アドレス・ネットワークを通って前記コヒーレンス要求を受信することに応答して前記第３の能動デバイスにキャッシュされたブロックのアクセス権を変更することをさらに含む請求項１８に記載の方法。
【請求項２０】
順序づけられた同報プロパティに従って前記アドレス・ネットワークを通ってアドレス・トランザクションを伝達することをさらに含む請求項１５に記載の方法。
【請求項２１】
同期された同報プロパティに従って前記アドレス・ネットワークを通ってアドレス・トランザクションを、および前記データ・ネットワークを通ってデータ・パケットを伝達することをさらに含む請求項２０に記載の方法。
【請求項２２】
システム・メモリと、
前記システム・メモリ内に格納されたデータにアクセスするよう構成された第１の能動デバイスであって、その第１の能動デバイスによってアクセスされたデータを格納するよう構成された第１のキャッシュを備えた第１の能動デバイスと、
前記第１の能動デバイスと前記システム・メモリの間でアドレス・トランザクションを伝達するためのアドレス・ネットワークと、
前記第１の能動デバイスと前記システム・メモリの間でデータ・トランザクションを伝達するためのデータ・ネットワークとを有し、
メモリ・アクセス・オペレーションに応答して前記第１のキャッシュに割り当てられた所与のブロックの所有権の遷移が、前記メモリ・アクセス・オペレーションに応答して前記所与のブロックへのアクセス権の遷移とは異なる時間に起きるコンピュータ・システム。
【請求項２３】
前記所与のブロックへのアクセス権が、前記第１のキャッシュが前記データ・ネットワークを通って対応するデータ・パケットを受信することに応答して前記第１のキャッシュ遷移に割り当てられる請求項２２に記載のコンピュータ・システム。
【請求項２４】
第２のキャッシュを含む第２の能動デバイスをさらに備え、別のブロックに対応するアクセス権が、別の対応するデータ・パケットが前記データ・ネットワークを通って前記第２のキャッシュによって受信されることに応答して前記第２のキャッシュ遷移に割り当てられる請求項２３に記載のコンピュータ・システム。
【請求項２５】
前記所与のブロックに対応する所有権状態が、対応するアドレス・トランザクションに応答して前記第１のキャッシュ遷移に割り当てられる請求項２４に記載のコンピュータ・システム。
【請求項２６】
前記対応するアドレス・トランザクションが、前記アドレス・ネットワークを通って前記第１のキャッシュによって受信される請求項２５に記載のコンピュータ・システム。
【請求項２７】
前記対応するアドレス・トランザクションがｒｅａｄ−ｔｏ−ｏｗｎトランザクションである請求項２６に記載のコンピュータ・システム。
【請求項２８】
前記第１のキャッシュによって受信された前記対応するデータ・パケットが、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションに応答して前記第２の能動デバイスから前記データ・ネットワークを通って伝達される請求項２７に記載のコンピュータ・システム。
【請求項２９】
前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが、前記第１の能動デバイスによって開始され、前記アドレス・ネットワークを通って伝達される請求項２８に記載のコンピュータ・システム。
【請求項３０】
第３のキャッシュを含む第３の能動デバイスをさらに備え、対応するブロックのアクセス権が、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが前記アドレス・ネットワークを通って前記第３のキャッシュによって受信されることに応答して読取りアクセス権から無効アクセス権への前記第３のキャッシュ遷移に割り当てられる請求項２９に記載のコンピュータ・システム。
【請求項３１】
ブロックのアクセス権が、前記第２の能動デバイスが前記対応するデータ・パケットを送信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項２９に記載のコンピュータ・システム。
【請求項３２】
前記ブロックに対応する所有権状態が、前記第２のキャッシュが前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションを受信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項３１に記載のコンピュータ・システム。
【請求項３３】
前記アドレス・ネットワークが、順序づけられた同報プロパティを実施する請求項２２に記載のコンピュータ・システム。
【請求項３４】
前記アドレス・ネットワークおよび前記データ・ネットワークが、同期された同報プロパティを実施する請求項３３に記載のコンピュータ・システム。
【請求項３５】
前記対応するデータ・パケットが、前記第１の能動デバイスによって開始されたｗｒｉｔｅ  ｓｔｒｅａｍトランザクションに応答して前記データ・ネットワークを通って前記第１のキャッシュに提供され、前記対応するデータ・パケットが、前記ｗｒｉｔｅ  ｓｔｒｅａｍトランザクションに対応するキャッシュ・ブロックの以前の所有者によって送信される請求項２４に記載のコンピュータ・システム。
【請求項３６】
前記対応するデータ・パケットが、キャッシュ・ブロックに対応するデータを除外する符号化された応答である請求項３５に記載のコンピュータ・システム。
【請求項３７】
システム・メモリと、
前記システム・メモリ内に格納されたデータにアクセスするよう構成された第１の能動デバイスであって、その第１の能動デバイスによってアクセスされたデータを格納するよう構成された第１のキャッシュを備えた第１の能動デバイスと、
第２のキャッシュを備える第２の能動デバイスと、
前記第１の能動デバイス、前記第２の能動デバイス、前記システム・メモリの間でアドレス・トランザクションを同報するよう構成され、順序づけられた同報プロパティを実装したアドレス・ネットワークと
前記第１の能動デバイスと前記システム・メモリの間でデータ・トランザクションを伝達するためのデータ・ネットワークとを有し、
所与のブロックに対応するアクセス権が、対応するデータ・パケットが前記データ・ネットワークを通って前記第１のキャッシュによって受信されることに応答して前記第１のキャッシュ遷移に割り当てられるコンピュータ・システム。
【請求項３８】
別のブロックに対応するアクセス権が、別の対応するデータ・パケットが前記データ・ネットワークを通って前記第２のキャッシュによって受信されることに応答して前記第２のキャッシュ遷移に割り当てられる請求項３７に記載のコンピュータ・システム。
【請求項３９】
前記アドレス・ネットワークおよび前記データ・ネットワークが同期された同報プロパティを実装する請求項３８に記載のコンピュータ・システム。
【請求項４０】
対応するアドレス・トランザクションが、前記アドレス・ネットワークを通って前記第１のキャッシュによって受信される請求項３９に記載のコンピュータ・システム。
【請求項４１】
前記対応するアドレス・トランザクションがｒｅａｄ−ｔｏ−ｏｗｎトランザクションである請求項４０に記載のコンピュータ・システム。
【請求項４２】
前記第１のキャッシュによって受信された前記対応するデータ・パケットが、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションに応答して前記第２の能動デバイスから前記データ・ネットワークを通って伝達される請求項４１に記載のコンピュータ・システム。
【請求項４３】
前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが、前記第１の能動デバイスによって開始され、前記アドレス・ネットワークを通って伝達される請求項４２に記載のコンピュータ・システム。
【請求項４４】
第３のキャッシュを含む第３の能動デバイスをさらに備え、対応するブロックのアクセス権が、前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションが前記アドレス・ネットワークを通って前記第３のキャッシュによって受信されることに応答して共用状態から無効状態への前記第３のキャッシュ遷移に割り当てられる請求項４３に記載のコンピュータ・システム。
【請求項４５】
ブロックのアクセス権が、前記第２の能動デバイスが前記対応するデータ・パケットを送信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項４３に記載のコンピュータ・システム。
【請求項４６】
前記ブロックに対応する所有権状態が、前記第２のキャッシュが前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクションを受信することに応答して前記ｒｅａｄ−ｔｏ−ｏｗｎトランザクション遷移に対応する前記第２のキャッシュに割り当てられる請求項４５に記載のコンピュータ・システム。
【請求項４７】
コンピュータ・システム内でコヒーレンシを維持する方法であって、
第１のコヒーレンス要求を生成する第１の能動デバイスと、
アドレス・ネットワークを通って前記第１のコヒーレンス要求を同報することととを含み、前記アドレス・ネットワークが、順序づけられた同報プロパティを実装し、
さらに、前記第１のコヒーレンス要求に応答してデータ・ネットワークを通って前記第１のコヒーレンス要求に対応するデータ・パケットを送信するデバイスと、
前記対応するデータ・パケットを受信することに応答して前記第１の能動デバイスにキャッシュされたブロックに対応するアクセス権を変更することとを含む方法。
【請求項４８】
前記デバイスが第２の能動デバイスである請求項４７に記載の方法。
【請求項４９】
前記対応するデータ・パケットを送信することに応答して前記第２の能動デバイスにキャッシュされた対応するブロックに対応するアクセス権を変更することをさらに含む請求項４８に記載の方法。
【請求項５０】
前記第１のコヒーレンス要求を受信する第３の能動デバイスをさらに備えた請求項４９に記載の方法。
【請求項５１】
前記第３の能動デバイスが前記アドレス・ネットワークを通って前記コヒーレンス要求を受信することに応答して前記第３の能動デバイスにキャッシュされたブロックのアクセス権を変更することをさらに含む請求項５０に記載の方法。
【請求項５２】
同期された同報プロパティに従って前記アドレス・ネットワークを通ってアドレス・トランザクションを、前記データ・ネットワークを通ってデータ・パケットを伝達することをさらに含む請求項５１に記載の方法。
【請求項５３】
第１のコヒーレンス要求を生成するよう構成された第１の能動デバイスと、
アドレス・ネットワークを通って前記第１のコヒーレンス要求を伝達する手段と、
前記第１のコヒーレンス要求に応答してデータ・ネットワークを通って前記第１のコヒーレンス要求に対応するデータ・パケットを送信するよう構成されたデバイスと、
前記対応するデータ・パケットを受信することに応答して前記第１の能動デバイスにキャッシュされたブロックに対応するアクセス権を変更するための手段とを備えたコンピュータ・システム。
【請求項５４】
前記デバイスが第２の能動デバイスである請求項５３に記載のコンピュータ・システム。
【請求項５５】
前記対応するデータ・パケットを送信することに応答して前記第２の能動デバイスにキャッシュされた対応するブロックに対応するアクセス権を変更するための手段をさらに備えた請求項５４に記載のコンピュータ・システム。
【請求項５６】
前記第１のコヒーレンス要求を受信するよう構成された第３の能動デバイスをさらに備えた請求項５５に記載のコンピュータ・システム。
【請求項５７】
前記第３の能動デバイスが前記アドレス・ネットワークを通って前記コヒーレンス要求を受信することに応答して前記第３の能動デバイスにキャッシュされたブロックのアクセス権を変更するための手段をさらに備えた請求項５６に記載のコンピュータ・システム。
【請求項５８】
順序づけられた同報プロパティに従って前記アドレス・ネットワークを通ってアドレス・トランザクションを伝達するための手段をさらに備えた請求項５３に記載のコンピュータ・システム。
【請求項５９】
同期された同報プロパティに従って前記アドレス・ネットワークを通ってアドレス・トランザクションを、前記データ・ネットワークを通ってデータ・パケットを伝達するための手段をさらに備えた請求項５８に記載のコンピュータ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチプロセッサ・コンピュータ・システムの分野に関し、より詳細には、共用メモリ・アーキテクチャを有するマルチプロセッサ・コンピュータ・システム内で用いられるコヒーレンシ・プロトコルに関する。
【０００２】
【従来の技術】
マルチプロセッシング・コンピュータ・システムには、計算タスクを実行するために用いることのできる複数のプロセッサが備えられる。他方のプロセッサが無関係な計算タスクを実行している間に、一方のプロセッサが特定の計算タスクを実行できる。あるいは、特定の計算タスクの構成要素を複数のプロセッサ間に分散させて、全体として計算タスクを実行するのに必要な時間を減少できる。
【０００３】
商用マルチプロセッシング・コンピュータ・システムの中で評判の良いアーキテクチャが、複数のプロセッサが共通メモリを共用する共用メモリ・アーキテクチャである。共用メモリ・マルチプロセッシング・システムにおいては、一般に、キャッシュ階層がプロセッサと共用メモリの間に実装されている。特定のアドレスが所与の時間に正確に１つのデータ値を格納する共用メモリ・モデルを維持するために、共用メモリ・マルチプロセッシング・システムはキャッシュ・コヒーレンシを用いる。一般的に言って、特定のメモリ・アドレスに格納されたデータに対するオペレーションの効果が、キャッシュ階層内のデータのそれぞれのコピー内に反映されれば、オペレーションはコヒーレントである。たとえば、特定のメモリ・アドレスに格納されたデータが更新された場合、古いデータのコピーを格納しているキャッシュにその更新が供給される。あるいは、古いデータのコピーをキャッシュ内で無効化して、その後の当該メモリ・アドレスへのアクセスのとき更新されたコピーを主記憶装置からキャッシュに転送するようにしてもよい。
【０００４】
共用メモリ・マルチプロセッシング・システムは、一般に、スヌーピング・キャッシュ・コヒーレンシ・プロトコルまたはディレクトリベースのキャッシュ・コヒーレンシ・プロトコルのいずれかを用いる。スヌーピング・プロトコルを用いるシステムにおいては、コヒーレンス要求が、トータル・オーダ・アドレス・ネットワークを通ってすべてのプロセッサ（またはキャッシュ・サブシステム）およびメモリに同報される。それぞれのプロセッサが、他のプロセッサから要求を「スヌープ」し、そのキャッシュ・タグを更新、かつ／または別のプロセッサにデータを提供することによりしかるべく応答する。たとえば、データの共用コピーを有するサブシステムが、ブロックへの排他的アクセスのためのコヒーレンス要求を観測した場合は、そのコピーは一般に無効化される。同様に、データのブロックを現在所有するサブシステムが、そのブロックに対するコヒーレンス要求を観察した場合は、そのブロックを所有しているサブシステムは、そのデータを要求側に提供し、必要ならばそのコピーを無効化することにより応答する。すべてのプロセッサおよびメモリが同じ順序で要求を観察するので、トータル・オーダでコヒーレンス要求を配信することにより、正しいコヒーレンス・プロトコル挙動が維持される。
【０００５】
標準スヌーピング・プロトコルにおいては、要求が同じ順序ですべてのデバイスに到達し、プロセッサのアクセス権が、要求が受信される順序で修正される。アドレス・ネットワークから分離したポイント・ツー・ポイント交換ネットワーク、アドレス・ネットワークから分離した同報ネットワーク、または同じハードウェアをアドレス・ネットワークと共用する論理同報ネットワークであるデータ・ネットワークを使用して、キャッシュとメモリの間でデータ転送が起きる。一般に、所与のキャッシュ・ブロックの所有権の変更は、そのブロックへのアクセス権の変更と同時に起きる。
【０００６】
残念なことに、標準スヌーピング・プロトコルには、大きな性能上の欠点がある。具体的には、プロセッサのアクセス権がスヌープが受信される順序で変更するという要件により、性能が制限されることである。たとえば、プロセッサがキャッシュ・ブロックＡおよびＢに対して、この順序で要求を出し、キャッシュ・ブロックＡについてのデータを受信する前に、キャッシュ・ブロックＢについてのデータを受信する（または既に持っている）可能性がある。この場合、プロセッサは、一般に、キャッシュ・ブロックＢについてのデータを使用する前に、キャッシュ・ブロックＡについてのデータを受信するまで待たなければならず、従って待ち時間が増加する。この要件に関連する衝撃は、このようなプロセッサは受信される順序でデータを使用できる可能性が高いので、たとえそれが要求された順序と異なっていたとしても、アウトオブオーダ実行、先取り、プロセッサ毎の複数コア、および／またはマルチスレッドをサポートするプロセッサで特に高い。
【０００７】
キャッシュ整合性に対する他の標準アプローチでは、ディレクトリベースのプロトコルを使用する。ディレクトリベースのプロトコルを実施するシステムにおいては、アドレス・ネットワークとデータ・ネットワークの両方が、一般に、ポイント・ツー・ポイントの交換ネットワークである。プロセッサがキャッシュ・ブロックを要求した場合、その要求は、キャッシュ・ブロックのコピーとそのアクセス権を有するプロセッサに関する情報を維持するディレクトリへ送信される。次いで、ディレクトリは、そのアクセス権を変更しなければならないプロセッサ、かつ／または要求に対してデータを提供しなければならないプロセッサに要求を転送する（または必要とあれば、ディレクトリは、メモリ内のキャッシュ・ブロックのコピーにアクセスし、要求側にデータを提供する）。送信されたそれぞれのプロセッサに要求がいつ到達したかを知ることができないので、その要求を受信するすべてのプロセッサは、一般に、プロトコルに従って、要求側またはディレクトリのいずれかにデータを提供するかまたは応答（ＡＣＫ）メッセージを送信することにより、受信に応答しなければならない。
【０００８】
【発明が解決しようとする課題】
ディレクトリベースのプロトコルを実装する代表的なシステムは、さまざまな欠点に関連している。たとえばこのようなシステムは、最初にディレクトリに、次いで関連プロセッサに行くことを要求する要件により、および／または応答メッセージを待つ必要から、高い待ち時間を有することがある。さらに、多数のプロセッサが、（キャッシュ・ブロックが、広く共用されている状態から排他的な状態まで遷移する場合などの）要求を受信しなければならない場合に、プロセッサのすべてが、一般に、ＡＣＫを同じ宛先に送信しなければならず、従ってそのＡＣＫの宛先近くのネットワーク内に輻輳が生じる原因となり、かつそのＡＣＫの受信を扱うための複雑な論理が必要となる。最後に、ディレクトリ自体にコストがかかり、システムへの複雑性も増すことになる。
【０００９】
【課題を解決するための手段】
コンピュータ・システム内でキャッシュ整合性を維持するためのメカニズムおよび方法が提供される。一実施態様では、コンピュータ・システムが、アドレス・ネットワークやデータ・ネットワークを通ってシステム・メモリに関連するデータにアクセスするよう構成されたシステム・メモリと複数の能動デバイスとを備えている。能動デバイスのそれぞれを、データをキャッシュするよう構成できる。第１の能動デバイス内に割り当てられた所与のブロックに対応するアクセス権を、対応するデータ・パケットがデータ・ネットワークを通って受信されることに応答して遷移するよう構成できる。さらに、所与のブロックの所有権の遷移が、その所与のブロックへのアクセス権が変更される時間とは異なる時間に起こってもよい。
【００１０】
特定の実施態様では、要求が、能動デバイスＤ１から第２の能動デバイスＤ２にキャッシュ・ブロックへの排他的アクセスを転送した場合に、ＤＩからデータを送信することがそのブロックへのＤ１のアクセス権を終了させ、Ｄ２でのデータの受信がそのアクセス権を開始させる。要求が、能動デバイスＤ１でのキャッシュ・ブロックへの排他的アクセスを能動デバイスＤ２との共用状態（すなわち、それぞれが読取りアクセス権を有する）に変更した場合に、Ｄ１からデータを送信することがＤ１の排他的アクセス権を終了させ、Ｄ２でのデータの到達がそのアクセス権を開始させる。要求が、共用状態から能動デバイスＤ２での排他的アクセスにキャッシュ・ブロックを転送した場合に、Ｄ２以外のすべての能動デバイスおよび（あれば）キャッシュ・ブロックを所有する能動デバイスでのアクセス権は、その要求の受信時に終了し、キャッシュ・ブロックを所有する能動デバイスのアクセス権は、データを送信した時に終了し、Ｄ２での排他的アクセス権は、Ｄ２が以前の所有者からデータを受信した時に開始される。
【００１１】
本発明の他の目的および利点は、以下の詳細な説明を添付図面を参照しながら読むことにより自明となろう。
【００１２】
本発明はさまざまな修正態様および代替態様が可能であるが、本発明の特定の実施態様を図面内に例として示し、本明細書で詳細に記述する。しかし、図面および詳細な説明は、開示されている特定の態様に本発明を限定するものではなく、むしろその反対に、頭記の請求の範囲に定義した本発明の趣旨および範囲内に含まれるすべての修正態様、均等物、代替態様を包含するものであることを理解されたい。
【００１３】
【発明の実施の形態】
まず図１を参照すると、コンピュータ・システム１４０の一実施形態のブロック図が示されている。コンピュータ・システム１４０には、アドレス・ネットワーク１５０およびデータ・ネットワーク１５２を通って相互接続された、処理サブシステム１４２Ａ、１４２Ｂと、メモリ・サブシステム１４４Ａ、１４４Ｂと、Ｉ／Ｏサブシステム１４６とが含まれる。図１の実施形態では、処理サブシステム１４２、メモリ・サブシステム１４４、Ｉ／Ｏサブシステム１４６のそれぞれを、クライアント・デバイスと呼ぶ。５つのクライアント・デバイスが図１に示されているが、任意の数のクライアント・デバイスを用いるコンピュータ・システム１４０の実施形態が想定されることに留意されたい。特定の参照数字の後に文字の付いた素子は、本明細書においては一括して参照数字のみで記すことがある。たとえば、処理サブシステム１４２Ａ〜１４２Ｂを、一括して処理サブシステム１４２などと記す。
【００１４】
一般的に言って、処理サブシステム１４２およびＩ／Ｏサブシステム１４６のそれぞれが、メモリ・サブシステム１４４にアクセスできる。メモリ・サブシステム１４４へのアクセスを実行するよう構成されたデバイスを、本明細書においては「能動」デバイスと呼ぶ。スプリット・トランザクション・パケットを使用して、アドレス・ネットワーク１５０上でアドレス・トランザクションを、およびデータ・ネットワーク１５２上でデータを伝達するように図１のそれぞれのクライアントを構成することができる。処理サブシステム１４２は、さまざまな特定のキャッシュ配置に構成できる１つまたは複数の命令キャッシュとデータ・キャッシュを有することができる。たとえば、セット・アソシエィティブまたは直接マッピングされた構成を、処理サブシステム１４２内のキャッシュにより用いることができる。ノード１４０内の処理サブシステム１４２のそれぞれが、恐らくデータをキャッシングして、メモリ・サブシステム１４４内のデータにアクセスすることがあるので、処理サブシステム１４２とメモリ・サブシステム１４４間でコヒーレンシが維持されなければならない。これについては、以下にさらに記載する。
【００１５】
メモリ・サブシステム１４４は、処理サブシステム１４２やＩ／Ｏサブシステム１４６によって使用されるデータ・コードおよび命令コードを格納するようになっている。メモリ・サブシステム１４４が、動的ランダム・アクセス・メモリ（ＤＲＡＭ）を備えることが好ましいが、他のタイプのメモリも使用できる。コンピュータ・システム１４０のアドレス空間内のそれぞれのアドレスを、アドレスのホーム・サブシステムと呼ぶ特定のメモリ・サブシステム１４４に割り当てることができる。
【００１６】
Ｉ／Ｏサブシステム１４６は、たとえば、入力出力ブリッジ、グラフィックス・デバイス、ネットワーキング・デバイスなどの周辺デバイスの例である。さまざまな実施形態では、Ｉ／Ｏサブシステム１４６は、メモリ・サブシステム１４４の１つの中にマッピングされたアドレスに関連するデータをキャッシュするための処理サブシステム１４２のそれと同様のキャッシュ・メモリ・サブシステムを含むことができる。
【００１７】
一実施形態では、データ・ネットワーク１５２は、論理ポイント・ツー・ポイント・ネットワークでよい。データ・ネットワーク１５２を、電気バス、回線交換ネットワーク、またはパケット交換ネットワークとして実装できる。データ・ネットワーク１５２がパケット交換ネットワークである実施形態では、パケットを、ワームホール、蓄積転送、または仮想カットスルーなどの技術を使用して、データ・ネットワークを通って送信できる。回線交換ネットワークでは、特定のクライアント・デバイスが、交換相互接続メカニズムを通じて確立できる専用ポイント・ツー・ポイント・リンクを介して、直接第２のクライアント・デバイスと通信できる。第３のクライアント・デバイスと通信するために、特定のクライアント・デバイスは、第２のクライアント・デバイスと通信するために使用されるものとは異なる、交換相互接続によって確立されたリンクを利用する。データ・ネットワーク１５２が、クライアント・デバイスＣ１がデータ・メッセージＤ２を送信する前にデータ・メッセージＤ１を送信し、クライアント・デバイスＣ２がＤ１とＤ２の両方を受信する場合には、Ｃ２は、Ｄ２を受信する前にＤ１を受信するように、ソース／宛先順序付けプロパティを実装できる。
【００１８】
図１の実施形態では、アドレス・ネットワーク１５０が、アドレス・トランザクションがすべてのクライアント・デバイスに伝達される同報ネットワークを実施する。アドレス・ネットワーク１５０を、アドレス・トランザクションを同報するよう構成されたポイント・ツー・ポイントの交換ネットワークを使用して物理的に具体化できる。アドレス・ネットワーク１５０およびデータ・ネットワーク１５２を、多段スイッチング階層を使用して実施できる。代替実施形態では、アドレス・ネットワーク１５０を、共通バス構造を使用して実施できる。アドレス・ネットワーク１５０を、データ・ネットワーク１５２から分離されたハードウェア内またはデータ・ネットワーク１５２と共用されるハードウェア内で具体化できる。
【００１９】
アドレス・ネットワーク１５０が、処理サブシステム１４２、メモリ・サブシステム１４４、Ｉ／Ｏサブシステム１４６の間の通信を調整する。アドレス・ネットワーク１５０上のメッセージを、一般に、アドレス・パケットと呼ぶ。アドレス・パケットがメモリ・サブシステム１４４内の記憶装置の場所を参照すると、アドレス・ネットワーク１５０上のアドレス・パケット内で伝達されたアドレスを介して参照された場所が指定される。その後、アドレス・ネットワーク１５０上のアドレス・パケットに対応するデータが、データ・ネットワーク１５２上で伝達される。代表的なアドレス・パケットが、アクセス権のための要求（たとえば、キャッシュ可能なコヒーレンシ・ユニットの読取り可能または書込み可能コピー）またはキャッシュ不可能なメモリ場所への読取りまたは書込みを実行するための要求に対応する。アドレス・パケットが、コヒーレンス・トランザクションを開始するためにデバイスによって送信されることがある。図１に示されているコンピュータ・システム１４０では、コヒーレンス・トランザクションが、アドレス・ネットワーク１５０およびデータ・ネットワーク１５２上に１つまたは複数のパケットを含むことができる。代表的なコヒーレンス・トランザクションが、少なくとも１つのアドレス・パケットと１つまたは複数のデータ・パケットとを必要とする。これらのパケットが、データ転送、所有権転送、および／またはアクセス特権の変更を実装する。アドレス・ネットワーク１５０は、所与のキャッシュ可能なコヒーレンシ・ユニットを必要とするトランザクションのための順序付けポイントとして働くことができ、従ってこのようなトランザクションが互いに「前」または「後」に起きるとみなせることに留意されたい。キャッシュ不可能なコヒーレンシ・ユニットを含むトランザクションに対する順序付けポイントは、そのトランザクションのターゲット・デバイスである。
【００２０】
一実施形態では、ｒｅａｄ−ｔｏ−ｓｈａｒｅ（ＲＴＳ）トランザクションを、キャッシュ・ブロックの読取り専用コピーを要求するために、アドレス・ネットワーク１５０上の能動デバイスによって開始できる。同様に、ｒｅａｄ−ｔｏ−ｏｗｎ（ＲＴＯ）トランザクションを、キャッシュ・ブロックの書込み可能コピーを要求するために、能動デバイスによって開始できる。他のコヒーレンス・トランザクションも同様に、所望の場合、アドレス・ネットワーク１５０上の能動デバイスによって開始できる。
【００２１】
図２は、コンピュータ・システム１４０の一実施形態によってサポートできる、それぞれのための記述を含む、さまざまなトランザクションを示すチャートである。例示されているように、ｒｅａｄ−ｔｏ−ｓｈａｒｅおよびｒｅａｄ−ｔｏ−ｏｗｎトランザクションに加えてさらに、サポートできるコヒーレンス・トランザクションが、ｒｅａｄ−ｓｔｒｅａｍ（ＲＳ）トランザクションと、ｗｒｉｔｅ−ｓｔｒｅａｍ（ＷＳ）トランザクションと、ｗｒｉｔｅ−ｂａｃｋ（ＷＢ）トランザクションと、ｗｒｉｔｅ−ｂａｃｋ  ｓｈａｒｅｄ（ＷＢＳ）トランザクションとを含む。ｒｅａｄ−ｓｔｒｅａｍトランザクションが、キャッシュ・ブロックのｒｅａｄ−ｏｎｃｅコピーを要求する。ｗｒｉｔｅ−ｓｔｒｅａｍトランザクションは、全キャッシュ・ブロックを書き込み、そのキャッシュ・ブロックをメモリに送信するための要求である。ｗｒｉｔｅ−ｂａｃｋトランザクションは、所有しているデバイスからメモリへキャッシュ・ブロックを送信するための要求であり、ここで、所有しているデバイスはコピーを保存しない。最後に、ｗｒｉｔｅ−ｂａｃｋ  ｓｈａｒｅｄトランザクションは、所有しているデバイスからメモリへキャッシュ・ブロックを送信するための要求であり、ここで、所有しているデバイスは読取り専用コピーを保存する。能動デバイスを、たとえば、Ｉ／Ｏ読取りおよび書込みトランザクションと割込みトランザクションなどのアドレス・ネットワーク１５０上の他のトランザクション・タイプを開始するよう構成することもできる。一実施形態では、ｒｅａｄ−ｔｏ−ｗｒｉｔｅｂａｃｋ（ＲＴＷＢ）トランザクションを、Ｉ／Ｏブリッジ（または他のデバイス）が、キャッシュ・ブロックの所有権を得ずに、かつキャッシュ・ブロックのための外部要求に応答せずに、キャッシュ・ブロックの一部に書込みを実行できるようにサポートすることもできる。
【００２２】
特定のアドレスを有する符号化されたパケットの形式でアドレス・ネットワーク１５０上でトランザクションを伝達できることに留意されたい。データ・ネットワーク１５２上で伝達されるデータ・パケットが、以下に記載するトランザクションＩＤを使用する対応するアドレス・トランザクションに関連する。
【００２３】
一実施形態では、キャッシュ可能なトランザクションが、データ・ネットワーク１５２上の開始クライアントによって受信される少なくとも１つのパケットとなる。さらに、トランザクションの中には、パケットがデータ・ネットワーク１５２上の開始クライアントから送信されることを必要とするものがある。図３は、コンピュータ・システム１４０の一実施形態に従って、さまざまなトランザクションから生じる可能性のあるデータ・ネットワーク１５２上のデータ・パケット転送を示す図である。ＰＲＮデータ・パケット・タイプは、データを送信するために、書込みトランザクションの宛先から書込みトランザクションのソースへ送信されたプル要求である。ＡＣＫデータ・パケット・タイプは、ｗｒｉｔｅ  ｓｔｒｅａｍトランザクションを完了できる所有しているデバイスからの肯定応答である。ＮＡＣＫデータ・パケット・タイプは、ＷＢ、ＷＢＳをアボートするメモリへのまたはＩＮＴトランザクションをアボートするイニシエータへの否定応答である。
【００２４】
イニシエータがトランザクションを開始すると、そのトランザクションのためのアドレス・パケットは、イニシエータのデバイスＩＤおよびパケットＩＤによって形成されるトランザクションＩＤを有することができ、これはイニシエータによって割り当てられる。イニシエータが受信するＤＡＴＡパケット、ＡＣＫパケットおよび／またはＰＲＮパケットは、イニシエータのデバイスＩＤをパケットのルーティング・プレフィックスに入れることにより、データ・ネットワーク１５２を通ってイニシエータにルーティングできる。さらに、ＤＡＴＡパケット、ＡＣＫパケットおよび／またはＰＲＮパケットは、イニシエータによって割り当てられたパケットＩＤに一致する宛先パケットＩＤフィールドを有することができ、従ってイニシエータが、ＤＡＴＡパケット、ＡＣＫパケットおよび／またはＰＲＮパケットを正しいトランザクションに一致させることができるようになる。そのうえ、ＰＲＮパケットが、ソースのデバイスＩＤおよびパケットＩＤから構成されるプルＩＤを有することができ、これはソース（つまり、ＰＲＮパケットを送信したクライアント）によって割り当てられる。ＰＲＮパケットを受信した後、イニシエータは、ＤＡＴＡパケットまたはＮＡＣＫパケットをＰＲＮのソースに送信できる。このＤＡＴＡパケットまたはＮＡＣＫパケットを、ＰＲＮのソースのデバイスＩＤをパケットのルーティング・プレフィックスに入れることによってルーティングでき、それを正しいＰＲＮに一致できるようにする宛先パケットＩＤフィールドを有することができる（さらに、パケットは、それがＰＲＮに応答して送信されたことを示すフラグを有し、従ってトランザクションＩＤとプルＩＤとの混乱を避けることができる）。
【００２５】
一実施形態では、ＷＳに応答して送信できるＡＣＫパケットは、データを有さない。ＡＣＫパケットは、以前の所有者の無効化を示すために使用できる。イニシエータがキャッシュ可能なトランザクションに応答して受信するＰＲＮパケットは、キャッシュ・ブロックをマップするメモリ・デバイスによって送信される。イニシエータが送信するＤＡＴＡまたはＮＡＣＫパケットは、キャッシュ・ブロック（これはまたイニシエータによって受信されるＰＲＮのソースでもある）をマップするメモリ・デバイスに送信される。
【００２６】
図３に例示されているように、イニシエータは、ＲＴＷＢトランザクションのための別個のＤＡＴＡパケットおよびＰＲＮパケットを受信できる。しかし、キャッシュ・ブロックの所有者がそのキャッシュ・ブロックをマップするメモリ・デバイスである場合は、これらの２つのパケットは、同じクライアントによって送信される。従って、一実施形態では、この状況下で２つのパケットを送信するのではなく、ＤＡＴＡパケットとＰＲＮパケットの情報を組み合せた単一のＤＡＴＡＰパケットが送信できる。同様に、キャッシュ・ブロックの所有者が、そのキャッシュ・ブロックをマップするメモリ・デバイスである場合には、ＰＲＮパケットとＡＣＫパケットの情報を組み合せた単一のＰＲＡＣＫパケットがＷＳトランザクションに応答して送信できる。最後に、イニシエータがキャッシュ・ブロックの所有者であるような場合に、イニシエータは、ＤＡＴＡパケットまたはＡＣＫパケットをそれ自体に送信しない（これは論理的に、イニシエータからイニシエータを去らないそれ自体へのＤＡＴＡパケットまたはＡＣＫパケットの送信と見ることができる）。同様に、イニシエータがキャッシュ・ブロックをマップするメモリ・デバイスであるような場合には、イニシエータは、ＰＲＮパケットをそれ自体に送信しないことがあり、またＤＡＴＡまたはＮＡＣＫパケットをそれ自体に送信する必要もない。
【００２７】
図１の実施形態では、キャッシュ不可能なトランザクションが、同様に、データ・ネットワークからの開始クライアントによって受信される少なくとも１つのパケットとなり、トランザクションの中には、パケットがデータ・ネットワーク上の開始クライアント・デバイスから送信されることを必要とするものがある。図４は、データ・ネットワーク１５２上で伝達できる結果として生じるデータ・パケット・タイプとともに、コンピュータ・システム１４０の一実施形態でサポートできるさまざまなキャッシュ不可能なトランザクション・タイプを示す図である。図４の列は、左から右の順序で、アドレスおよびデータ・ネットワーク上で送信されるパケットのシーケンスを示す。
【００２８】
キャッシュ可能なデータ転送について記載したように、イニシエータがキャッシュ不可能なトランザクション・タイプに応答して受信できるＤＡＴＡパケット、ＰＲＮパケット、またはＮＡＣＫパケットは、データ・ネットワーク１５２を通ってイニシエータにルーティングされ、トランザクションＩＤを使用して受信側で正しいトランザクションに一致できる。同様に、キャッシュ可能なトランザクションについて記載したように、イニシエータが送信するＤＡＴＡパケットは、その宛先にルーティングされ、プルＩＤを使用してその宛先で正しいトランザクションに一致できる。
【００２９】
ＲＩＯトランザクションおよびＷＩＯトランザクションについては、イニシエータが受信するＤＡＴＡパケットおよび／またはＰＲＮパケットは、ブロックをマップするクライアントから送信される。ＩＮＴトランザクションについては、イニシエータが受信するＰＲＮパケットまたはＮＡＣＫパケットは、（ＩＮＴパケットのアドレス・フィールド内で指定できる）割込みのターゲットから送信される。イニシエータがＤＡＴＡパケットを送信すると、それは、ＤＡＴＡパケットをそれが受信したＰＲＮのソースに送信する。イニシエータが、ＤＡＴＡパケット、ＰＲＮパケット、またはＮＡＣＫパケットのソースと宛先の両方である場合は、ＤＡＴＡパケット、ＰＲＮパケットまたはＮＡＣＫパケットを送信する必要がないことに留意されたい。また、イニシエータがＩＮＴトランザクションに応答してＰＲＮパケットを受信すると、イニシエータはデータ・パケットを送信することにも留意されたい。イニシエータがＩＮＴトランザクションに応答してＮＡＣＫパケットを受信すると、イニシエータは、データ・ネットワーク上でパケットを送信しないことがある。
【００３０】
以下にさらに詳細に記述するように、一実施形態では、コンピュータ・システム１４０が、以下の２つのプロパティを満たすよう構成される（ここで、必要とあれば、コヒーレンス・プロトコルに従って、受信側のプロセッサでのパケットに応答して所有権状態および／またはアクセス権の変更がなされた場合に、パケットが「受信」されるよう定義される）。
１）順序づけられた同報。アドレス同報Ｂ１が、プロセッサ（または他のデバイス）Ｐ１で他のアドレス同報Ｂ２の前に受信されると、Ｂ１も、他のすべてのプロセッサ（および他のすべての能動デバイス）Ｐ２でＢ２の前に受信される。２）同期された同報。Ｐ１がアドレス同報Ｂ１を受信した後に、データ・パケットＤ１がプロセッサ（または他のデバイス）Ｐ１から送信され、Ｄ１がプロセッサ（または他のデバイス）Ｐ２で受信されると、Ｐ２はＤ１を受信する前に、Ｂ１を受信する。
【００３１】
コンピュータ・システム１４０が、キャッシュ・コヒーレンス・プロトコルを用いて、キャッシュを備えたライアントにメモリのコヒーレント・ビューを提供する。このために、それぞれのキャッシュ・ブロックのための状態情報を、それぞれの能動デバイス内で維持できる。状態情報は、能動デバイスのアクセス権および能動デバイスの所有権責任を指定する。
【００３２】
特定のキャッシュ・ブロックのための状態情報によって指定されたアクセス権を使用して、クライアント・デバイスが所与のオペレーション（すなわち、ロードまたは格納オペレーション）およびそのオペレーションが１つまたは複数の部分的またはトータル・オーダ内に現れることのできる場所に関する制約をコミットできるかどうかを判断する。一実施形態では、メモリ・アクセス・オペレーションは、「グローバル・オーダ」と呼ぶ、単一のトータル・オーダで現れる。このような実施形態では、オペレーションをグローバル・オーダで入れることのできる場所に対するこれらの制約を使用して、たとえば特に、シーケンシャルに整合性のあるメモリ・モデルまたはｔｏｔａｌ−ｓｔｏｒｅ−ｏｒｄｅｒ（ＴＳＯ）などのさまざまな周知のメモリ・モデルをサポートできる。
【００３３】
特定のキャッシュ・ブロックのための状態情報によって指定される所有権責任は、クライアント・デバイスがキャッシュ・ブロックのデータをそれを要求する別のクライアントに提供する責任があるかどうかを示す。クライアント・デバイスが、データをそれを要求する別のクライアントに提供する責任がある場合は、キャッシュ・ブロックを所有する。
【００３４】
一実施形態では、コンピュータ・システム１４０によって用いられるコヒーレンス・プロトコルは、以下のプロパティに関連する。
１）所有権状態の変更が、アドレス・パケットの受信に応答して起きる。アドレス・パケットを送信すること、データ・パケットを送信すること、データ・パケットを受信することは、所有権状態に影響を及ぼさない。
２）能動デバイスが、その所有権責任に関連するデータを有さずにキャッシュ・ブロックを所有できる。
３）アドレス・パケットを受信すること、データ・パケットを送信すること、データ・パケットを受信することで、アクセス権が遷移する。アドレス・パケットを送信することは、アクセス権に影響を及ぼさない（他のパケットが処理される方法に影響を及ぼす可能性はあるが）。
４）キャッシュ・ブロックへのアクセス権を有する能動デバイスは、常に、そのアクセス権に関連するデータを有する。
５）アドレス・パケットの受信は、特定のデータ・パケットの受信に基づいてブロックされない。たとえば、要求されているデータも受信される前に、局所読取り要求パケットを受信することが可能である。
【００３５】
コンピュータ・システム１４０によって用いられるプロトコル内でアクセス権および所有権状態が別個に遷移できるので、コヒーレンス状態のさまざまな組み合せが可能である。図５Ａおよび５Ｂは、コンピュータ・システム１４０の一実施形態で可能なアクセス権および所有権状態のタイプを示す図である。図５Ｃは、アクセス権と所有権状態の可能な組み合せを示す図である。これらの組み合せが、周知のＭＯＳＩプロトコルなどの従来のコヒーレンス・プロトコルの組み合せとは異なることに留意されたい。他の実施形態では他の特定の形式のアクセス権が定義できることにも留意されたい。
【００３６】
図５Ａに例示されているように、Ｗ（Ｗｒｉｔｅ）アクセス権が、読取りおよび書込みの両方を可能にする。Ａ（Ａｌｌ−Ｗｒｉｔｅ）アクセス権が、書込みのみを可能にし、全キャッシュ・ブロックが書き込まれることを必要とする。Ｒ（Ｒｅａｄ）アクセス権が読取りのみを可能にする。Ｔ（Ｔｒａｎｓｉｅｎｔ−Ｒｅａｄ）アクセス権が、読取りのみを可能にするが、以下に記載するように、ＷまたはＲアクセス権の下で実行される読取りとは異なり、Ｔアクセス権の下で実行される読取りを再順序づけることができる。最後に、Ｉ（Ｉｎｖａｌｉｄ）アクセス権は、読取りも書込みも可能にしない。システムが最初に初期化されると、すべての能動デバイスが、すべてのキャッシュ・ブロックのためのＩアクセス権を有する。以下にさらに記載するように、キャッシュ・ブロックがＡアクセス権状態にある場合には、全キャッシュ・ブロックを修正しなければならないので、この修正の前にキャッシュ・ブロック内に入れられているデータは、必要ではなく、かつ存在していない可能性がある。その代りに、データが存在しない場合は、データを表すトークンとして作用するＡＣＫパケットが受け取られていなければならない。
【００３７】
図５Ｂに例示されているように、能動デバイスが、所与のキャッシュ・ブロックについて、Ｏ（ｏｗｎｅｒ（所有者））所有権状態またはＮ（ｎｏｎ−ｏｗｎｅｒ（非所有者））所有権状態を有することができる。いずれの状態においても、キャッシュ・ブロックに対応するデータが、キャッシュ内に存在する場合も存在しない場合もある。
【００３８】
いったん能動デバイスが所与のアクセス権を取得すると、それは、多くの読取りおよび／または書込みを実行することにより、アクセス権を失うまで、そのアクセス権を繰り返し行使できる。Ａ（Ａｌｌ−Ｗｒｉｔｅ（全書き込み））以外のアクセス権については、たとえそのアクセス権がそうすることを可能にしたとしても、能動デバイスは、所与のキャッシュ・ブロックを読み取ることも書き込むこともできない。Ａアクセス権は、全ブロックが書き込まれることを必要とするため、従って能動デバイスは、ブロック内のそれぞれのバイトへ少なくとも１つの書込みを実行しなければならない。
【００３９】
図１の実施形態では、アクセス権の変更が、アドレス・パケットを受信すること、データ・パケットを送信すること、またはデータ・パケットを受信することに応答して起きることがある。一般的に言って、また以下にさらに詳細に記述するように、要求が、キャッシュ・ブロックへの排他的アクセスをプロセッサＰ１からプロセッサＰ２へ転送すると、Ｐ１からデータを送信することが、そのブロックへのＰ１のアクセス権を終了させ、Ｐ２でデータを受信することが、そのアクセス権を開始させる。要求が、プロセッサＰ１でのキャッシュ・ブロックへの排他的アクセスを、プロセッサＰ２との共用状態（すなわち、それぞれが読取りアクセス権を有する）へ変更すると、Ｐ１からデータを送信することが、Ｐ１の書込みアクセス権を終了させ（引き続きキャッシュ・ブロックを読み取ることができるが）、Ｐ２でのデータの到達が、その共用アクセス権を開始させる。要求が、共用状態からプロセッサＰ２での排他的アクセスへキャッシュ・ブロックを転送すると、Ｐ２以外のすべてのプロセッサおよび（あれば）キャッシュ・ブロックを所有するプロセッサでのアクセス権を、同報要求の受信時に終了させ、（ある場合には）キャッシュ・ブロックを所有するプロセッサのアクセス権を、それがデータを送信した時に終了させ、Ｐ２での書込みアクセス権を、いったんＰ２が以前の所有者から（またはメモリから）データを受信すると開始させる。最後に、要求がキャッシュ・ブロックを既に共用している１組のプロセッサにプロセッサＰ２を追加すると、プロセッサはアクセス権を失わず、Ｐ２は、データを受信した時に読取りアクセス権を得る。
【００４０】
所有権責任が、アドレス・パケットの受信に応答して遷移できる。図１の実施形態では、データ・パケットを送信することおよび受信することが、所有権責任に影響を及ぼさない。図６は、コンピュータ・システム１４０の一実施形態における特定のトランザクションに応答する所有権遷移を示すチャートである。図６では、「以前の所有者」は、所有権が変更されていないことを示し、「イニシエータ」は、トランザクションを開始したクライアントが所有者となったことを示し、「メモリ」は、キャッシュ・ブロックをマップするメモリ・サブシステム１４４が所有者となったことを示す。キャッシュ・ブロックの所有者は、キャッシュ・ブロックをマップする能動デバイスまたはメモリ・デバイスのいずれかである。データ・パケットまたはＡＣＫパケットを要求するキャッシュ可能なトランザクションＴが与えられると、Ｔの直前にキャッシュ・ブロックの所有者であったクライアントは、要求されたデータ・パケットまたはＡＣＫパケットを送信する。システムが最初に初期化された時は、メモリが、それぞれのキャッシュ・ブロックに対する所有者である。
【００４１】
コンピュータ・システム１４０の一実施形態におけるクライアント・デバイスのアクセス権および所有権責任の遷移については、図７Ａ〜７Ｆに示したコヒーレンス・オペレーションの例を参照すれば、より良く理解できるであろう。図７Ａは、能動デバイスＤ１がＷアクセス権および所有権を有し、能動デバイスＤ２がＲアクセス権を得るためにＲＴＳを開始する状況を示す図である。この場合、Ｄ１が、アドレス・ネットワーク１５０を通ってＤ２からＲＴＳパケットを受信する。ＲＴＳに応答して、Ｄ１が、対応するデータ・パケット（要求されたデータを含み）をデバイスＤ２に送信する。Ｄ１が、対応するデータ・パケットをＤ２に送信する前に、追加のアドレスおよび／またはデータ・パケットを受信できることに留意されたい。Ｄ１が対応するデータ・パケットをＤ２に送信すると、Ｄ１は、そのＷアクセス権を失い、そのアクセス権をＲアクセス権に変更する。Ｄ２が対応するデータ・パケットを受信すると、Ｒアクセス権（Ｄ２のアクセス権は以前はＩであった）を取得する。Ｄ１は、引き続きキャッシュ・ブロックの所有権を維持する。
【００４２】
図７Ｂは、能動デバイスＤｌがＷアクセス権および所有権を有し、能動デバイスＤ２がＷアクセス権を得るためにＲＴＯトランザクションを開始する状況を示す図である。この場合、Ｄｌが、アドレス・ネットワーク１５０を介してＤ２からＲＴＯパケットを受信する。その結果、Ｄ１が、その所有権状態をＮ（ｎｏｔｏｗｎｅｒ）に変更し、対応するデータ・パケットをＤ２に送信する。しかし、Ｄ１が、対応するデータ・パケットをＤ２に送信する前に、追加のアドレスおよび／またはデータ・パケットを受信できることに留意されたい。また、Ｄ２がアドレス・ネットワーク１５０を介してそのオウンＲＴＯを受信することにも留意されたい。Ｄ１が対応するデータ・パケットをＤ２に送信すると、Ｄ１はそのＷアクセス権を失い、その権利をＩアクセス権に変更する。Ｄ２がアドレス・ネットワーク１５０を介して自身のＲＴＯを受信すると、その所有権状態は、Ｏ（ｏｗｎｅｄ）に変更する。Ｄ２が対応するデータ・パケットを受信すると、Ｗアクセス権を取得する。
【００４３】
図７Ｃは、能動デバイスＤ１がＲアクセス権および所有権を有し、能動デバイスＤ２もまたＲアクセス権を有する（が所有権は有さない）、かつ能動デバイスＤ３がＷアクセス権を得るためにＲＴＯを発行する（Ｄ３は、最初ＩまたはＲアクセス権のいずれかを有する可能性がある）状況を示す図である。この場合、Ｄｌが、アドレス・ネットワーク１５０を介してＤ３からＲＴＯを受信する。その結果、Ｄ１が、その所有権状態をＮに変更し、対応するデータ・パケットをＤ３に送信する。しかし、Ｄ１が、対応するデータ・パケットをＤ３に送信する前に、追加のアドレスおよび／またはデータ・パケットを受信できることに留意されたい。Ｄ１が対応するデータ・パケットをＤ３に送信すると、Ｄ１は、そのアクセス権をＩアクセス権に変更する。さらに、Ｄ２はまた、アドレス・ネットワーク１５０を介してＲＴＯも受信する。ＲＴＯを受信すると、Ｄ２は、そのＲアクセス権をＩアクセス権に変更する。その上、Ｄ３がアドレス・ネットワーク１５０を介して自身のＲＴＯを受信すると、その所有権状態はＯに変更される。対応するデータ・パケットを受信すると、Ｄ３はＷアクセス権を取得する。無効化ＲＴＯパケットがＤ２に到達する前に、対応するデータ・パケットおよびローカルＲＴＯを、Ｄ３によって受信できることに留意されたい。この場合、Ｄ３がそれを書き込み始めた後でさえも、Ｄ２は引き続きキャッシュ・ブロックを読み取ることができる。
【００４４】
図７Ｄは、能動デバイスＤ１がＲアクセス権および所有権を有し、能動デバイスＤ２がＲアクセス権を有し、能動デバイスＤ３がＲアクセス権を得るためにＲＴＳを発行する状況を示す図である。この場合、Ｄ１が、アドレス・ネットワーク１５０を介してＤ３からＲＴＳを受信する。その結果、Ｄ１は、対応するデータ・パケットをＤ３に送信する。Ｄ３が対応するデータ・パケットを受信すると、そのアクセス権は、Ｉアクセス権からＲアクセス権に変更する。Ｄ１およびＤ２でのＲＴＳの受信により、Ｄ１またはＤ２でのアクセス権の変更は起きない。その上、所有権の変更も生じない。
【００４５】
全キャッシュ・ブロックが能動デバイスによって書き込まれ、メモリに送信されるＷＳ（Ｗｒｉｔｅ  Ｓｔｒｅａｍ）トランザクションの場合は、ＷＳを実行するデバイスは、ごく最近（アドレス同報順序で）キャッシュ・ブロックを所有した処理サブシステム１４２（またはメモリ・サブシステム１４４）から、ＡＣＫパケットを受信できる。このＡＣＫパケットが正規データ・メッセージ内の正しい場所にあり（また実際にデータ・メッセージが使用でき）、このようなＡＣＫメッセージの１つのみをＷＳに応答して送信できることに留意されたい。
【００４６】
図７Ｅは、能動デバイスＤ１がＲまたはＷアクセス権および所有権を有し、能動デバイスＤ２がＷＳトランザクションを発行する状況を示す図である。図示のように、ＷＳトランザクションは、アドレス・ネットワーク１５０を通ってキャッシュ・ブロックをマップするメモリ・サブシステム１４４およびＤ１によって受信される。その結果、Ｄ１が、対応するＡＣＫパケットをＤ２に送信する。しかし、Ｄ１が、対応するＡＣＫパケットをＤ２に送信する前に、追加のアドレスおよび／またはデータ・パケットを受信できることに留意されたい。Ｄ１が対応するＡＣＫパケットをＤ２に送信すると、Ｄ１は、そのアクセス権をＩアクセス権に変更する。Ｄ２がＤ１からＡＣＫパケットを受信すると、そのアクセス権がＡ（Ａｌｌ−Ｗｒｉｔｅ）に変更する。さらに、キャッシュ・ブロックをマップするメモリ・サブシステム（Ｍ）が、データ・ネットワーク１５２上でＰＲＮパケットをＤ２に転送する。Ｄ２が全キャッシュ・ブロックに書き込むと、Ｄ２は、データ・パケットをメモリ・サブシステムＭに転送する。アドレス・ネットワーク１５０を通ってＷＳトランザクションを受信した時に、Ｄ１は、その所有権状態をＮ（ｎｏｔ−ｏｗｎｅｄ）に変更し、メモリ・サブシステムＭはその所有権状態をｏｗｎｅｄに変更する。
【００４７】
図７Ｆは、能動デバイスＤ１がＷアクセス権および所有権を有し、データをメモリにライト・バックするためにＷＢトランザクションを発行する状況を示す図である。キャッシュ・ブロックをマップするメモリ・サブシステム（Ｍ）は、アドレス・ネットワーク１５０を通ってＷＢパケットを受信し、それに応答して、データ・ネットワーク１５２を通ってＤ１にＰＲＮパケットを転送する。その結果、Ｄ１が、対応するデータ・パケットをメモリＭに送信する。Ｄ１が、対応するデータ・パケットをメモリＭに送信する前に、追加のアドレスおよび／またはデータ・パケットを受信できることに留意されたい。Ｄ１がアドレス・ネットワーク１５０を通って自身のＷＢを受信すると、その所有権状態はＮに変更する。Ｄ１が対応するデータ・パケットをメモリＭに送信すると、そのアクセス権はＩアクセス権に変更される。このシーケンスのトランザクションの後、メモリＭが、キャッシュ・ブロックの所有者となる。ＷＢＳ（ｗｒｉｔｅ−ｂａｃｋ  ｓｈａｒｅｄ）トランザクションも、同様に扱うことができる。
【００４８】
上述したような能動デバイス内でアクセス権を変更するための基本的な規則を用いるコンピュータ・システムのさまざまな変形形態が考えられると想定される。このようなコンピュータ・システムは、有利なことに、効率的なオペレーションを達成しつつキャッシュ整合性を維持する。図７Ａ〜７Ｆと合わせて上述したトランザクションのサブセットを実装するコンピュータ・システム１４０の実施形態が可能であることに留意されたい。その上、他の特定のトランザクション・タイプも、所望の場合実装形態に従ってサポートできる。
【００４９】
所与のトランザクション・タイプについて上述した特定のパケット転送についての変形形態も可能であることにも留意されたい。さらに、上述した実施形態では、所有権遷移がアドレス・パケットの受信に応答して実行されるが、所有権遷移は、他の実施形態では、あるコヒーレンス・トランザクションの結果として異なる方式で実行できる。
【００５０】
さらに上述の説明によれば、所有しているデバイスが、別のデバイスによって開始された（ＲＴＯまたはＲＴＳなどの）トランザクションに応答して、対応するデータ・パケットをただちに送信しないことがある。一実施形態では、最大期間（たとえば、クロック・サイクルの最大数など）を使用して、レスポンシブ・データ・パケットを送信する前に、能動デバイスが費やすことのできる全時間を制限できる。
【００５１】
さまざまなメカニズムを使用して、上記で識別された同期された同報プロパティを得ることができる。たとえば、所与のトランザクションに対応するすべての同報が、同じサイクル上ですべてのデバイスに到達することを保障するために、単一のクロック上を動作するグローバルな同期システムを作り、かつアドレス・ネットワーク１５０内の経路をチューニングすることにより、同期された同報プロパティを得ることができる。このようなシステムでは、それらを待ち行列内にバッファせずに、アドレス・パケットを受信できる。このような実装形態が可能であるが、それよりも、ソースのクロックが特定のパケットとともに送信されるソース同期信号方式を使用して、より高い通信速度を可能にすることが望ましいであろう。このような実装形態では、パケットが受信されるサイクルは予め知られていない可能性がある。さらに、アドレス・ネットワーク１５０をフロー制御せずに、デバイスが一時的にパケットを受信できるようにするために、入ってくるアドレス・パケットのための待ち行列を提供することがさらに望ましいであろう。
【００５２】
したがって、グローバルな同期システムを必要とせずに同期された同報プロパティを維持し、かつアドレス・パケットをバッファできるようにするコンピュータ・システム１４０の一実装形態に関する詳細について、次に図８と合わせて記述する。図８は、コンピュータ・システム１４０の処理サブシステム１４２のそれぞれの一実施形態の詳細を示すブロック図である。図８の実施形態には、処理ユニット７０２と、キャッシュ７１０と、待ち行列７２０Ａ〜７２０Ｄとが含まれる。待ち行列７２０Ａ〜７２０Ｂは、データ・リンク７３０を介してデータ・ネットワーク１５２に結合され、待ち行列７２０Ｃ〜７２０Ｄは、アドレス・リンク７４０を介してアドレス・ネットワーク１５０に結合される。待ち行列７２０のそれぞれが、それぞれがアドレスまたはデータ・パケットを格納するよう構成された複数のエントリを有する。処理ユニット７０２が、キャッシュ７１０に結合された状態として示されている。階層的キャッシュ構造を使用して、キャッシュ７１０が実装されている。
【００５３】
処理ユニット７０２が、メモリ・サブシステム１４４内に格納されたデータに関する命令を実行し、オペレーションを実行するよう構成される。キャッシュ７１０を、メモリ・サブシステム１４４から検索された命令および／またはデータのコピーを格納するよう構成できる。データおよび／または命令のコピーを格納することに加えて、キャッシュ７１０はまた、上述したように、キャッシュ７１０内の特定のキャッシュ・ブロックのコヒーレンシ状態を示す状態情報７１２も有する。上記によれば、処理ユニット７０２が特定のキャッシュ・ブロックへの読取りまたは書取りを試み、キャッシュ状態情報７１２が、処理ユニット７０２が所望のオペレーションを実行するための十分なアクセス権を有さないことを示す場合は、コヒーレンシ要求を有するアドレス・トランザクションを、アドレス・ネットワーク１５０上で伝達するためのａｄｄｒｅｓｓ  ｏｕｔ待ち行列７２０Ｄ内に挿入できる。その後、キャッシュ・ブロックに対応するデータを、ｄａｔａ−ｉｎ待ち行列７２０Ｂを介して受信できる。
【００５４】
さらに、処理サブシステム１４２が、別の能動デバイスによって開始された（またはそれ自体によって開始された）ｒｅａｄ−ｔｏ−ｏｗｎやｒｅａｄ−ｔｏ−ｓｈａｒｅトランザクションなどのａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃを介してコヒーレンシ・デマンドを受信できる。たとえば、処理サブシステム１４２が、メモリ・ブロックのための外部デバイスによって開始されたｒｅａｄ−ｔｏ−ｏｗｎ要求に対応するトランザクションを受信した場合は、対応するメモリ・ブロックは、ｄａｔａ  ｏｕｔ待ち行列７２０Ａを介して戻すことができ（たとえば、キャッシュ・ブロックが処理サブシステム１４２によって所有されていた場合）、かつ／または上述したように、そのブロックのための状態情報７１２を無効に変更できる。他のコヒーレンス・トランザクションおよびキャッシュ不可能なトランザクションも同様に、ａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃを通って受信できる。同様の待ち行列メカニズムを使用して、メモリ・サブシステム１４４およびＩ／Ｏサブシステム１４６を実施できる。
【００５５】
あるネットワーク伝達プロパティに従ってアドレス・ネットワーク１５０およびデータ・ネットワーク１５２を実施することにより、かつ／またはある待ち行列制御プロパティに従って待ち行列７２０を制御することにより、上述した同期された同報プロパティを維持できる。いくつかの実施形態では、（アドレス・ネットワーク１５０上で伝達された）同報が第１のクライアント・デバイスに到達した時から、同じ同報が第２のクライアント・デバイスに到達する時までの最大スキューが、第１から第２のクライアント・デバイスへデータ・ネットワーク１５２上で送信されるメッセージのための最小待ち時間以下となるように、アドレス・ネットワーク１５０およびデータ・ネットワーク１５２が実施される。このような実装形態により以下のネットワーク伝達プロパティが生じる（同期された同報プロパティと同一であるが、但し、パケット受信（すなわち、パケットが受信側のデバイス内の所有権状態および／またはアクセス権に影響を及ぼす場合）ではなく、パケット到達（すなわち、パケットがｉｎ−ｑｕｅｕｅ７２０Ｂおよび７２０Ｃに到達する場合）について記載していることを除く）。データ・パケットＤ１がプロセッサＰ１からプロセッサＰ２に送信され、Ｄ１が送信される前に、同報Ｂ１がＰ１に到達すると、Ｄ１がＰ２に到達する前に、Ｂ１がＰ２に到達する。
【００５６】
ネットワーク伝達プロパティがこのようなシステムに対して適用できることを検証するために、上記のネットワーク伝達プロパティで言及したパケットＢ１およびＤ１について考察し、さまざまな事象が起きる時の記号を以下に定義する。
【００５７】
【表１】
記号    事象
Ｗ      Ｐ１でのＢ１の到達
Ｘ      Ｐ１からのＤ１の送信
Ｙ      Ｐ２でのＢ１の到達
Ｚ      Ｐ２でのＤ１の到達
【００５８】
記号「＜」を使用して、ある事象が別の事象の前に起きることを示す。例えば、Ａ＜Ｂは、事象Ａが事象Ｂの前に起きることを示す。記号「＜＝」を使用して、ある事象が別の事象の前にまたは同時に起きることを示す。たとえば、Ａ＜＝Ｂは、事象Ａが事象Ｂの前にまたは同時に起きることを示す。また、所与の同報がＰ１に到達した時間からその所与の同報がＰ２に到達する時間までの最大期間をＳで表し、パケットがデータ・ネットワーク上でＰ１から（Ｐ２に向けて）送信された時間からそのパケットがＰ２に到達する時間までの最小時間をＬで表す。記号「＋」を使用して、ある事象への時間の追加を示す。たとえば、Ａ＋Ｓは、事象ＡへのＳの追加を示す。
【００５９】
Ｗ＜Ｘ、すなわち、Ｐ１がＤ１を送信する前に、Ｂ１がＰ１に到達すると仮定する。ネットワーク伝達プロパティが適用できることを証明するためには、Ｙ＜Ｚ、すなわち、Ｄ１がＰ２に到達する前に、Ｂ１がＰ２に到達することが示されなければならない。Ｙ＜＝Ｗ＋Ｓ（Ｓの定義から）、Ｗ＜Ｘ（上記の仮定から）、およびＳ＜＝Ｌ（アドレス・ネットワークおよびデータ・ネットワークの構築から）であることに留意されたい。従って、Ｙ＜Ｘ＋Ｌとなる。その上、Ｘ＋Ｌ＜＝Ｚ（Ｌの定義から）であるので、従ってＹ＜Ｚとなり（かつネットワーク伝達プロパティが適用できることになる）。
【００６０】
ネットワーク伝達プロパティが適用できるようにアドレス・ネットワーク１５０および１５２を実施することに加えて、ａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃおよびｄａｔａ−ｉｎ待ち行列７２０Ｂが、アドレスおよびデータ・ネットワークからのパケットが、到達時に各待ち行列内に入れられ、かつそれらが待ち行列内に入れられた順序で（すなわち、先入れ先出しで）除去（かつ従って受信）されるように、待ち行列制御回路７６０によって制御される。その上、データ・パケットより早く到達したすべてのアドレス・パケットがａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃから除去されるまで処理するために、データ・パケットは、ｄａｔａ−ｉｎ待ち行列７２０Ｂから除去されない。
【００６１】
一実施形態では、待ち行列制御回路７６０を、それがａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃの末尾にあるエントリ内に格納された時に、アドレス・パケットとともにポインタを格納するよう構成できる。ポインタは、ｄａｔａ−ｉｎ待ち行列７２０Ｂ内の次の使用可能なエントリ（すなわち、ｄａｔａ−ｉｎ待ち行列７２０Ｃが、到達する次のデータ・パケットを格納するために使用するエントリ）を示す。このような実施形態では、ａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃの先頭からポップされた後に、アドレス・パケットが受信される（すなわち、それらが、キャッシュ７１０内の対応するブロックのアクセス権に影響を及ぼす）。ａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃの先頭にあるアドレス・パケットに対応するポインタが、特定のデータ・パケットを含むエントリに後続するｄａｔａ−ｉｎ待ち行列７２０Ｂのエントリを指すまで、特定のデータ・パケットが受信される（すなわち、アクセス権が影響を受けるような方式でキャッシュ７１０によって処理される）ことを防ぐように、待ち行列制御回路７６０を構成できる。この方式により、データ・パケットより早く到達したすべてのアドレス・パケットがａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃから除去されるまで処理するために、データ・パケットは、ｄａｔａ−ｉｎ待ち行列７２０Ｂから除去されない。
【００６２】
代替実施形態では、パケットがｄａｔａ−ｉｎ待ち行列７２０Ｂに入れられた場合は常に、トークンをａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃに入れるように、待ち行列制御回路７６０を構成できる。このような実施形態では、そのマッチング・トークンがａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃから除去されるまで、待ち行列制御７６０は、パケットがｄａｔａ−ｉｎ待ち行列７２０Ｂから除去されるのを防ぐことができる。待ち行列７２０に関連するパケットの処理を制御するための待ち行列制御回路７６０のさまざまな他の特定の実装形態が想定されることに留意されたい。
【００６３】
この方式でａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃおよびｄａｔａ−ｉｎ待ち行列７２０Ｂを制御することにより、かつ上述したネットワーク伝達プロパティに従ってアドレス・ネットワーク１５０およびデータ・ネットワーク１５２を実装することにより、コンピュータ・システム１４０が、同期された同報プロパティを維持できる。このことを証明するために、同期された同報プロパティの定義と同様にパケットＢ１およびＤ１を考察し、時間を以下のように定義する。
【００６４】
【表２】
記号    事象
Ｗ      Ｐ１でのＢ１の到達
Ｗ’    Ｐ１でのＢ１の処理
Ｘ      Ｐ１からのＤ１の送信
Ｙ      Ｐ２でのＢ１の到達
Ｙ’    Ｐ２でのＢ１の処理
Ｚ      Ｐ２でのＤ１の到達
Ｚ’    Ｐ２でのＤ１の処理
【００６５】
Ｗ’＜Ｘであると仮定する。同期された同報プロパティが適用できることを証明するためには、Ｙ’＜Ｚ’であることを示さなければならない。（パケットが、受信され処理できるようになる前に、到達しなければならないので）Ｗ＜＝Ｗ’であり、従ってＷ＜Ｘとなることに留意されたい。従って、Ｙ＜Ｚ（ネットワーク伝達プロパティから）となる。その結果、ｄａｔａ−ｉｎ待ち行列７２０Ｂ内のデータ・パケットがａｄｄｒｅｓｓ−ｉｎ待ち行列７２０Ｃ内のアドレス・パケットに追いつくことができないので、Ｙ’＜Ｚ’となる。
【００６６】
次に図９を参照すると、図１の処理サブシステム１４２のそれぞれの一実施形態に関するさらなる詳細が示されている。図８のそれに対応する回路部分には、同じ番号が付けられている。
【００６７】
図９は、処理ユニット７０２、キャッシュ７１０、データおよびアドレス待ち行列７２０に結合するインターフェイス・コントローラ９００を示す図である。インターフェイス・コントローラ９００が、アドレス・ネットワーク１５０およびデータ・ネットワーク１５２を通って処理サブシステム１４２を他のクライアント・デバイスにインターフェイスすることに関連する機能を制御するよう設けられる。より詳細には、インターフェイス・コントローラ９００が、ｒｅａｄ−ｔｏ−ｓｈａｒｅおよびｒｅａｄ−ｔｏ−ｏｗｎトランザクションの生成を必要とするロードおよび格納要求などの他のクライアント・デバイスへの外部通信（たとえば、パケット送信）を必要とする処理ユニット７０２によって開始されるさまざまな要求を処理するよう構成される。また、インターフェイス・コントローラ９００は、他のクライアント・デバイスによって開始されるトランザクションに対応する通信を処理するよう構成されている。特定の実装形態では、インターフェイス・コントローラ９００が、図７Ａ〜７Ｆに例示されているようなコヒーレンス・オペレーションの処理に関連するものを含み、上記の記述に従ってトランザクションを処理するための機能を有する。このために、過渡的状態コントローラ９０２として表される機能が、未処理のローカル・トランザクション（つまり、安定した完了状態に達していない処理サブシステム１４２によって開始されるトランザクション）を処理するためにインターフェイス・コントローラ９００内に設けられる。このオペレーションをサポートするために、（状態情報を含む）コヒーレンス・オペレーションの処理に関係する情報が、インターフェイス・コントローラ９００とキャッシュ７１０の間で通過できる。過渡的状態コントローラ９０２が、複数の独立した状態機械（図示せず）を有することができ、そのそれぞれを、単一の未処理のローカル・トランザクションを完了するまで処理するよう構成できる。
【００６８】
システムによってサポートできる実装形態およびトランザクションのタイプに従って、過渡的状態コントローラ９０２によって表される機能を、未処理のトランザクションに関連するさまざまな過渡的状態を維持するよう構成できる。たとえば、図７Ｂに例示したトランザクションの例から、デバイスＤ２が、自身のＲＴＯを受信した後かつデバイスＤ１から対応するデータ・パケットを受信する前に、過渡的状態ＩＯを入力する。同様に、対応するデータ・パケットがデバイスＤ２に送信されるまで、デバイスＤ１が、維持されているデバイスＤ２からＲＴＯを受信することに応答して過渡的状態ＷＮを入力する。一実施形態では、過渡的状態コントローラ９０２が、保留状態のローカル・トランザクションのためのこのような過渡的状態を維持し、それにより、このようなローカル・トランザクションが完了して安定状態になるまで、コヒーレンス・プロトコルに従ってアドレスおよびデータ・パケットの処理を制御する。
【００６９】
再び図５Ｃを参照して、状態ＷＯ、ＲＯ、ＲＮ、ＩＮが、周知のＭＯＳＩコヒーレンス・プロトコルによって定義される対応する状態に等しいことに留意されたい。状態ＷＮに加えて、これらの４つの状態は安定状態である。図５Ｃに表された他の状態は過渡的であり、インターフェイス・コントローラ９００によるローカル・トランザクションの処理中のみに存在する。さらに、一実施形態では、このようなキャッシュ・ブロックについて状態ＷＮから状態ＲＮへただちにダウングレードすることが可能であるので、ローカル・トランザクション保留を有さないキャッシュ・ブロックに対して、状態ＷＮは維持されないことがある。その結果、特定の実装形態では、状態情報の２ビットのみが、キャッシュ７１０の状態情報記憶装置７１２内のそれぞれのキャッシュ・ブロックに対して維持される。状態ＷＯ、ＲＯ、ＲＮ、ＩＮに対応する２ビットの符号化が実現される。このような実施形態では、保留状態のローカル・トランザクションに対応する過渡的状態情報を、過渡的状態コントローラ９０２によって別個に維持できる。
【００７０】
コヒーレンス・トランザクションが能動デバイスによって開始され、同じキャッシュ・ブロックへのコヒーレンス・トランザクションが別の能動デバイス内で保留状態である場合、さまざまな追加の過渡的状態も生じることがある。たとえば、図１０は、能動デバイスＤ１がＷアクセス権および所有権を有し、能動デバイスＤ２がＷアクセス権を得るためにＲＴＯトランザクションを開始する状況を示す図である。Ｄ１がＤ２からアドレス・ネットワーク１５０を通ってＲＴＯパケットを受信すると、Ｄｌはその所有権状態をＮ（ｎｏｎ−ｏｗｎｅｒ）に変更する。Ｄ２は、アドレス・ネットワーク１５０を通ってそのオウンＲＴＯを受信すると、その所有権状態をＯ（ｏｗｎｅｒ）に変更する。その後、対応するデータ・パケットがＤ２でＤ１から受信される前に、別の能動デバイスＤ３が、アドレス・ネットワーク１５０を通ってＤ２によって受信される同じキャッシュ・ブロックに別のＲＴＯを発行することが可能であろう。この状況で、第２のＲＴＯが受信されると、Ｄ２がその所有権状態をＮ（ｎｏｎ−ｏｗｎｅｒ）に変更できる。さらに、Ｄ３がアドレス・ネットワーク１５０を通ってそのオウンＲＴＯを受信すると、その所有権状態はＯ（ｏｗｎｅｒ）に変更する。対応するデータ・パケットがＤ２によってＤ１から受信されると、Ｄ２のアクセス権が書込みアクセス権に変更する。Ｄ２は、所望の場合に、この書込みアクセス権を繰り返し行使できる。しばらくした後、対応するデータ・パケットをＤ２からＤ３に送信できる。データがＤ３によって受信されると、Ｗアクセス権を取得する。このようなオペレーションおよび過渡的状態遷移を、必要な場合に、サポートできるトランザクションのタイプおよび起きる可能性のあるパケット送信および受信の特定のシーケンスに基づいて、および所与の実装形態のために選択できる特定のコヒーレンス方法に基づいて、過渡的状態コントローラ９０２によって表される機能によって実行し維持することができる。
【００７１】
例示されているように、図９に表されているインターフェイス・コントローラ９００が、さらにプロミス・アレイ９０４も有することができる。上述したように、コヒーレンス・トランザクションに応答して、キャッシュ・ブロックを所有する処理サブシステムが、キャッシュ・ブロックのためのデータを別のデバイスに転送するために必要とされることがある。しかし、キャッシュ・ブロックを所有する処理サブシステムが、トランザクションが受信された時に、対応するデータを有さないことがある。プロミス・アレイ９０４が、コヒーレンス・プロトコルによって命令されている保留状態のコヒーレンス・トランザクションに応答してデータ・ネットワーク１５２上で他のデバイスに伝達されなければならないデータ・パケットを識別する情報を格納するよう構成される。
【００７２】
さまざまな記憶装置構造を使用して、プロミス・アレイ９０４を実装できる。たとえば、データ・パケットを伝達しなければならないすべての未処理のトランザクションに対応する情報を格納するのに十分な大きさのフル・サイズのアレイを使用して、プロミス・アレイ９０４を実装できる。特定の実装形態では、システム内のそれぞれの能動デバイスが、キャッシュ・ブロック毎にせいぜい１つの未処理のトランザクションを有することができる。この方式により、他のデバイスに転送するのに必要となる可能性のある最大数のデータ・パケットが束縛され、プロミス・アレイの全サイズを、このような最大数のデータ・プロミスを考慮するよう選択できる。代替構成では、プロミス・アレイ９０４が一杯となり、追加のデータ・プロミスに対応する追加情報を格納できない事象において、アドレス・トランザクションがフロー制御されることがある。プロミス・アレイ９０４が、複数のエントリを有することができ、それぞれが、転送する必要のある特定のデータ・パケットを識別する情報およびデータ・パケットを転送しなければならない宛先を識別する情報を格納するよう構成される。特定の実装形態では、リンクされたリストを使用して、プロミス・アレイ９０４を実施できる。
【００７３】
次に図１１を参照すると、上述したコヒーレンス・プロトコルの一般的な形態を用いるシステムが、場合によっては枯渇問題を経験する可能性があることに留意されたい。より詳細には、例示されているように、能動デバイスＤ１が、アドレス・ネットワーク１５０上でｒｅａｄ−ｔｏ−ｓｈａｒｅ（ＲＴＳ）トランザクションを伝達することにより、ロード・オペレーションを実行するために、キャッシュ・ブロックの読取り専用コピーを要求することがある。しかし、以前に記載したように、対応するデータ・パケットが、しばらく後までＤ２（すなわち、所有しているデバイス）からＤ１に伝達されないことがある。対応するデータ・パケットを受信する前に、デバイスＤ１が、キャッシュ・ブロックをＩ（Ｉｎｖａｌｉｄ）状態に保つ。対応するデータ・パケットを受信する前に、デバイスＤ３が、対応するデータ・パケットの前にＤ１によって受信されたＲＴＯ（または他の無効化トランザクション）を開始することが可能である。この状況により、以前に受信されたＲＴＯが第１の要求の効果を無効にできるので、デバイスＤ１がキャッシュ・ブロックへの読取りアクセス権を得ることを防止できる。デバイスＤ１が、再びロードを満たすことを試みるために別のＲＴＳを発行できるが、追加のｒｅａｄ−ｔｏ−ｏｗｎオペレーションを、引き続きデバイスＤ１が必要なアクセス権を得ることを防止する他の能動デバイスによって再び開始できる。場合によっては、キャッシュ・ブロックへの排他的アクセスのための要求により、キャッシュ・ブロックへの共用アクセスための要求を無制限の回数、無効にでき、従って枯渇が生じる。
【００７４】
あるロードをクリティカル・ロードと定義することにより、このような枯渇状況を避けることができる。一般的に言って、クリティカル・ロードとは、プログラム順序に違反することなくグローバル・オーダで論理的に再順序づけることのできる能動デバイスによって開始されるロード・オペレーションを指す。ＴＳＯ（Ｔｏｔａｌ  Ｓｔｏｒｅ  Ｏｒｄｅｒ）メモリ・モデルを実装する一実施形態では、それが処理ユニット７０２によって開始された最も古いコミットされていないロード・オペレーションである場合、ロード・オペレーションはクリティカル・ロードである。枯渇を避けるために、未処理のＲＴＳがクリティカル・ロードに対応するという指示および（ＲＴＳのための対応するデータ・パケットが受信される前の）同じブロックへの介在する外部ＲＴＯトランザクションの受信に応答して、過渡的状態コントローラ９０２を、データ・パケットの受信時にキャッシュ・ブロックへのＴ（Ｔｒａｎｓｉｅｎｔ−Ｒｅａｄ）アクセス権を提供するよう構成できる。Ｔアクセス権により、データ・パケットが受信された場合に、ロードを満たすことができる。ロードが満たされた後、キャッシュ・ブロックの状態は、Ｉ（Ｉｎｖａｌｉｄ）にダウングレードされる。このメカニズムにより、クリティカル・ロードを、プログラム順序に違反することなくグローバル・オーダで論理的に再順序づけることができる。ロードは、所有者（デバイスＤ２）が対応するデータ・パケットをＤ１に（またはＤ３）に送信した直後であるが、ＲＴＯを実行しているデバイス（デバイスＤ３）がその対応するデータ・パケットを受信する前のある時点で論理的に起きたと見ることができる。この方式により、デバイスＤｌにロードを満たすよう提供される値は、この時点の前のすべての書込みの値を含み、この時点の後の書込みの値のいずれをも含まない。
【００７５】
特定の実装形態では、処理ユニット７０２が、ロードが、ロード要求がインターフェイス・コントローラ９００に伝達された時の最も古いコミットされていないロードであるという指示を提供できる。別の実施形態では、ロードを、ローカルＲＴＳがアドレス・ネットワーク１５０上で伝達された時点の最も古いコミットされていないロードである場合に、クリティカル・ロードとして示すことができる。さらなる実施形態では、ロードを、外部無効化ＲＴＯが受信された時点の最も古いコミットされていないロードである場合に、クリティカル・ロードとして示すことができる。
【００７６】
図１１と合わせて記述したシナリオにおいて、ＲＴＳがクリティカル・ロードに関連するものとして示されない場合は、過渡的状態コントローラ９０２が、対応するデータを受信することに応答して、キャッシュ・ブロックを（Ｔ状態を割り当てるのではなく）Ｉ（Ｉｎｖａｌｉｄ）状態に維持できることに留意されたい。
【００７７】
他のメモリ・モデルを実装するシステムにおいて、他の条件が存在する場合には、ロード・オペレーションがクリティカル・ロード（すなわち、グローバル・オーダで論理的に再順序づけられたロード・オペレーション）であり得ることにも留意されたい。たとえば、シーケンシャルな整合性を実現するシステムにおいて、より古いコミットされていないロードまたは格納オペレーションがない場合には、ロード・オペレーションをクリティカル・ロードとして定義できる。
【００７８】
上述したシステムにおいて、数々の変形形態が想定される。たとえば、上述したアドレス・ネットワーク１５０が同報ネットワークを実装するが、アドレス・トランザクションをポイント・ツー・ポイントでまたはクライアント・デバイスのサブセットに伝達できる他のシステムが想定される。このようなシステムは、能動デバイス内のアクセス権を遷移するための上述したプロトコルの一般的な形態を用いることができる。
【００７９】
さらに、図１２に表わされているように、メモリ・サブシステム１４４が処理サブシステム１４２の機能と統合される実施形態が可能であることに留意されたい。このような実施形態では、特定のコヒーレンス・トランザクションについて上述したアドレスおよび／またはデータ・ネットワーク上のあるパケットの伝達は、不必要であろう。
【００８０】
上記の実施形態についてかなり詳細にわたって記述してきたが、他のバージョンも可能である。上記の開示を十分に理解されたならば、かずかずの変形形態および修正形態が当業者には自明のこととなろう。頭記の特許請求の範囲は、すべてのこのような変形形態および修正形態を包含するものと解釈すべきである。
【図面の簡単な説明】
【図１】マルチプロセッシング・コンピュータ・システムを示すブロック図である。
【図２】コンピュータ・システムの一実施形態においてサポートできるさまざまなトランザクションを示すチャートである。
【図３】コンピュータ・システムの一実施形態によるデータ・パケット転送を示す図である。
【図４】コンピュータ・システムの一実施形態においてサポートできるさまざまなキャッシュ不可能なトランザクション・タイプを示す図である。
【図５Ａ】コンピュータ・システムの一実施形態において可能なアクセス権および所有権の状態のタイプを示す図である。
【図５Ｂ】コンピュータ・システムの一実施形態において可能なアクセス権および所有権の状態のタイプを示す図である。
【図５Ｃ】アクセス権および所有権の状態の可能な組合わせを示す図である。
【図６】コンピュータ・システムの一実施形態において特定のトランザクションに応答する所有権遷移を示すチャートである。
【図７Ａ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図７Ｂ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図７Ｃ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図７Ｄ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図７Ｅ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図７Ｆ】コンピュータ・システムの一実施形態において実施できるコヒーレンス・オペレーションの例を示す図である。
【図８】図１の処理サブシステムのそれぞれの一実施形態の詳細を示すブロック図である。
【図９】図１の処理サブシステムのそれぞれの一実施形態に関するさらに詳細を示すブロック図である。
【図１０】同じキャッシュ・ブロックについて開始される複数のコヒーレンス・トランザクションを示す図である。
【図１１】コンピュータ・システムの一実施形態による能動デバイス間の通信を示す図である。
【図１２】マルチプロセッシング・コンピュータ・システムの別の実施形態を示すブロック図である。
【符号の説明】
１４０  コンピュータ・システム
１４２  処理サブシステム
１４４  メモリ・サブシステム
１４６  Ｉ／Ｏサブシステム
１５０  アドレス・ネットワーク
１５２  データ・ネットワーク
７０２  処理ユニット
７１０  キャッシュ
７１２  状態情報
７２０  待ち行列
７３０  データ・リンク
７４０  アドレス・リンク
７６０  待ち行列制御回路
９００  インターフェイス・コントローラ
９０２  過渡的状態コントローラ
９０４  プロミス・アレイ
【図１】
2005148771.tif 000003
【図２】
2005148771.tif 000004
【図３】
2005148771.tif 000005
【図４】
2005148771.tif 000006
【図５Ａ】
2005148771.tif 000007
【図５Ｂ】
2005148771.tif 000008
【図５Ｃ】
2005148771.tif 000009
【図６】
2005148771.tif 000010
【図７Ａ】
2005148771.tif 000011
【図７Ｂ】
2005148771.tif 000012
【図７Ｃ】
2005148771.tif 000013
【図７Ｄ】
2005148771.tif 000014
【図７Ｅ】
2005148771.tif 000015
【図７Ｆ】
2005148771.tif 000016
【図８】
2005148771.tif 000017
【図９】
2005148771.tif 000018
【図１０】
2005148771.tif 000019
【図１１】
2005148771.tif 000020
【図１２】
2005148771.tif 000021