(57)【要約】  物理分散キャッシュメモリシステムは、相互接続ネットワークと、第１レベルのキャッシュメモリ・スライスと、第２レベルのキャッシュメモリ・スライスとを有する。第１レベルのキャッシュメモリ・スライスは、相互接続ネットワークに結合され、タグ付き順序保存要求を生成する。各タグ付き順序保存要求は、要求側識別表示と保存シーケンス・トークンとを有するタグを有する。第２レベルのキャッシュメモリ・スライスは、相互接続ネットワークに結合され、タグ付き順序保存要求の各タグに応じて、物理キャッシュメモリシステムを通じて順番に順序保存要求を実行する。
2007509439.tif 000002
【特許請求の範囲】
【請求項１】
相互接続ネットワークと、
前記相互接続ネットワークに結合され、要求側識別表示と保存シーケンス・トークンとを有するタグ付き順序保存要求を生成する第１レベルのキャッシュメモリ・スライスと、
前記相互接続ネットワークに結合され、前記タグ付き順序保存要求の各タグに応じて、物理分散キャッシュメモリシステムを通じて順番に順序保存要求を実行する第２レベルのキャッシュメモリ・スライスと
を有する物理分散キャッシュメモリシステム。
【請求項２】
請求項１に記載の物理分散キャッシュメモリシステムであって、
前記タグ付き順序保存要求のうち１つ以上は、前記第２レベルのキャッシュメモリ・スライスのうち少なくとも１つにより、ばらばらの順番で受信される物理分散キャッシュメモリシステム。
【請求項３】
請求項１に記載の物理分散キャッシュメモリシステムであって、
前記第１レベルのキャッシュメモリ・スライスのそれぞれは、前記タグ付き順序保存要求を生成する固有の要求側識別表示とシーケンス・トークン・レジスタとを有する物理分散キャッシュメモリシステム。
【請求項４】
請求項１に記載の物理分散キャッシュメモリシステムであって、
前記第２レベルのキャッシュメモリ・スライスのそれぞれは、前記物理分散キャッシュメモリシステムを通じて順番に前記順序保存要求を実行するキャッシュ・シーケンス・アレイを有する物理分散キャッシュメモリシステム。
【請求項５】
請求項４に記載の物理分散キャッシュメモリシステムであって、
前記キャッシュ・シーケンス・アレイは、キャッシュ・シーケンス・エントリとして順序保存要求に関連する保存シーケンス・トークンを保存するキャッシュ・シーケンス・アレイ・テーブルを有し、
前記キャッシュ・シーケンス・エントリは、前記キャッシュメモリ・スライスが現在実行することができる１つ以上の順序保存要求を示す物理分散キャッシュメモリシステム。
【請求項６】
請求項４に記載の物理分散キャッシュメモリシステムであって、
前記第２レベルのキャッシュメモリ・スライスのそれぞれは、前記キャッシュ・シーケンス・アレイに結合された制御ロジックを更に有し、
前記制御ロジックは、前記順序保存要求の順番の実行を制御し、前記第２レベルのキャッシュメモリ・スライスを更新するキャッシュ・シーケンス・アレイを生成する物理分散キャッシュメモリシステム。
【請求項７】
請求項１に記載の物理分散キャッシュメモリシステムであって、
前記第１レベルのキャッシュメモリ・スライスは、それぞれプロセッサに結合され、前記タグ付き順序保存要求を生成する物理分散キャッシュメモリシステム。
【請求項８】
請求項７に記載の物理分散キャッシュメモリシステムであって、
前記プロセッサは、前記タグ付き順序保存要求を生成する内部キャッシュメモリを有する物理分散キャッシュメモリシステム。
【請求項９】
請求項１に記載の物理分散キャッシュメモリシステムであって、
１つ以上のプロセッサに結合された上位レベルのキャッシュメモリを更に有する物理分散キャッシュメモリシステム。
【請求項１０】
請求項９に記載の物理分散キャッシュメモリシステムであって、
前記１つ以上のプロセッサは、前記タグ付き順序保存要求を生成する内部キャッシュメモリを有する物理分散キャッシュメモリシステム。
【請求項１１】
請求項９に記載の物理分散キャッシュメモリシステムであって、
前記上位レベルのキャッシュメモリは、前記タグ付き順序保存要求を生成する物理分散キャッシュメモリシステム。
【請求項１２】
物理分散キャッシュメモリシステムにおける順序保存要求用の方法であって、
要求側識別表示と保存シーケンス番号とを示す順序保存要求にタグを付与し、
タグ付き順序保存要求を前記物理分散キャッシュメモリシステムのキャッシュメモリ・スライスに送信し、
前記要求側識別表示に関連する予想シーケンス番号と、前記保存シーケンス番号とを比較し、
前記保存シーケンス番号が前記予想シーケンス番号に合致する場合、前記順序保存要求を実行することを有する方法。
【請求項１３】
請求項１２に記載の方法であって、
前記保存シーケンス番号が前記予想シーケンス番号に合致しない場合、後の実行のために、前記タグ付き順序保存要求を保存することを更に有する方法。
【請求項１４】
請求項１２に記載の方法であって、
前記順序保存要求を実行したことに応じて、前記要求側識別表示に関連する前記予想シーケンス番号を更新することを更に有する方法。
【請求項１５】
請求項１２に記載の方法であって、
前記順序保存要求を実行する前に、要求側により行われた前の順序保存要求が実行されているか否かを決定し、そうである場合には、前記順序保存要求を実行することを更に有する方法。
【請求項１６】
請求項１５に記載の方法であって、
前記決定することは、前記順序保存要求を実行するために、前記前の順序保存要求に関連する保存シーケンス番号と、前記要求側識別表示とが、前記キャッシュメモリ・スライスにより受信されているか否かを決定する方法。
【請求項１７】
請求項１５に記載の方法であって、
前記要求側により行われた全ての前の順序保存要求が実行されていないと決定されたときに、全ての前の順序保存要求が実行されるまで、現行の順序保存の実行が遅れる方法。
【請求項１８】
順序保存要求の順番の実行のために、キャッシュメモリに結合されるデータ信号フローであって、
順序保存要求を開始した要求側を示す要求側識別子と、
前記順序保存要求のシーケンスを示すトークン値と、
前記要求側識別子及び前記トークン値が前記キャッシュメモリにより読み取られるように利用可能であることを示すメッセージ識別子と
を有するデータ信号フロー。
【請求項１９】
請求項１８に記載のデータ信号フローであって、
前記メッセージ識別子は、前記要求側識別子及び前記トークン値が順序保存要求に付与されることを更に示すデータ信号フロー。
【請求項２０】
請求項１９に記載のデータ信号フローであって、
前記順序保存要求と、
データを保存するアドレスと、
保存される前記順序保存要求のデータと
を更に有するデータ信号フロー。
【請求項２１】
請求項１８に記載のデータ信号フローであって、
前記メッセージ識別子は、前記要求側識別子及び前記トークン値がキャッシュ・シーケンス・アレイを更新するためのものであることを更に示す方法。
【請求項２２】
１つ以上のレベルのプロセッサ・キャッシュメモリをそれぞれ有する複数のプロセッサと、
前記複数のプロセッサに結合され、複数のプライマリ相互接続ネットワークと、前記プライマリ相互接続ネットワークに結合された複数のキャッシュメモリ・スライスとを有する分散キャッシュメモリシステムと、
前記複数のプロセッサと前記分散キャッシュメモリシステムの前記プライマリ相互接続ネットワークとの間に結合された複数のキャッシュメモリと
を有する処理ユニットであって、
プロセッサ又はキャッシュメモリは、前記分散キャッシュメモリシステムの前記複数のキャッシュメモリ・スライスの順序保存要求に付与するタグを生成するための固有の要求側識別表示とシーケンス・トークン・レジスタとを有し、前記タグは、要求側識別表示と前記要求側識別表示に関連するシーケンス・トークンとを有し、
各キャッシュメモリ・スライスは、前記分散キャッシュメモリシステムを通じて順番に前記順序保存要求を実行するキャッシュ・シーケンス・アレイを有する処理ユニット。
【請求項２３】
請求項２２に記載の処理ユニットであって、
前記複数のキャッシュメモリ・スライスの前記順序保存要求のうち１つ以上は、少なくとも１つのキャッシュメモリ・スライスによりばらばらの順番で受信される処理ユニット。
【請求項２４】
請求項２２に記載の処理ユニットであって、
前記キャッシュ・シーケンス・アレイは、キャッシュ・シーケンス・エントリとして順序保存要求に関連する保存シーケンス・トークンを保存するキャッシュ・シーケンス・アレイ・テーブルを有し、
前記キャッシュ・シーケンス・エントリは、前記キャッシュメモリ・スライスが現在実行することができる順序保存要求を示す処理ユニット。
【請求項２５】
請求項２４に記載の処理ユニットであって、
前記複数のキャッシュメモリ・スライスのうち１つのキャッシュメモリ・スライスは、その順番を示す所定の要求側のキャッシュ・シーケンス・エントリに合致するシーケンス・トークンを有する順序保存要求を受信し、
前記１つのキャッシュメモリ・スライスは、現行の順序保存要求を実行する処理ユニット。
【請求項２６】
請求項２５に記載の処理ユニットであって、
前記１つのキャッシュメモリ・スライスは、前記複数のキャッシュメモリ・スライスの前記キャッシュ・シーケンス・エントリを更に更新する処理ユニット。
【請求項２７】
請求項２４に記載の処理ユニットであって、
前記複数のキャッシュメモリ・スライスのうち１つのキャッシュメモリ・スライスは、そのばらばらの順番を示す所定の要求側のキャッシュ・シーケンス・エントリに合致しないシーケンス・トークンを有する順序保存要求を受信し、
前記１つのキャッシュメモリ・スライスは、他の順序保存要求との後の順番の実行のために、現行の順序保存要求を保存する処理ユニット。
【請求項２８】
入出力装置と、
ダイナミック・ランダムアクセスメモリと、
前記ダイナミック・ランダムアクセスメモリ及び前記入出力装置に結合されたマルチプロセッサ・プロセッサと
を有するコンピュータシステムであって、
前記マルチプロセッサ・プロセッサは、
１つ以上のレベルのプロセッサ・キャッシュメモリをそれぞれ有する複数のプロセッサと、
前記複数のプロセッサに結合され、相互接続ネットワークと、前記相互接続ネットワークに結合された複数のキャッシュメモリ・スライスとを有する分散キャッシュメモリシステムと、
前記複数のプロセッサと前記相互接続ネットワークとの間に結合された複数のキャッシュメモリと
を有し、
プロセッサ又はキャッシュメモリは、前記分散キャッシュメモリシステムの前記複数のキャッシュメモリ・スライスの順序保存要求に付与するタグを生成するための固有の要求側識別表示とシーケンス・トークン・レジスタとを有し、前記タグは、要求側識別表示と前記要求側識別表示に関連するシーケンス・トークンとを有し、
各キャッシュメモリ・スライスは、前記分散キャッシュメモリシステムを通じて順番に前記順序保存要求を実行するキャッシュ・シーケンス・アレイを有するコンピュータシステム。
【請求項２９】
請求項２８に記載のコンピュータシステムであって、
前記複数のキャッシュメモリ・スライスのうち１つは、その順番を示す所定の要求側のキャッシュ・シーケンス・エントリに合致するシーケンス・トークンを有する順序保存要求を受信し、
前記１つのキャッシュメモリ・スライスは、現行の順序保存要求を実行するコンピュータシステム。
【請求項３０】
請求項２９に記載のコンピュータシステムであって、
前記１つのキャッシュメモリ・スライスは、前記複数のキャッシュメモリ・スライスの前記キャッシュ・シーケンス・エントリを更に更新する処理ユニット。
【請求項３１】
請求項２８に記載のコンピュータシステムであって、
順序保存要求は、要求側の他の順序要求に関して順番の実行を必要とする要求側の保存要求であるコンピュータシステム。
【請求項３２】
請求項３１に記載のコンピュータシステムであって、
前の順序保存要求は、現行の順序保存要求が処理可能になる前に処理を必要とするコンピュータシステム。
【請求項３３】
請求項３０に記載のコンピュータシステムであって、
無順序保存要求は、要求側の他の順序要求に関してばらばらの順番で実行可能な要求側の保存要求であるコンピュータシステム。
【請求項３４】
相互接続ネットワークと、
前記相互接続ネットワークに結合され、要求側識別表示と保存シーケンス・トークンとを含むタグをそれぞれ有するタグ付き順序保存要求を前記相互接続ネットワークに結合する複数のプロセッサと、
前記相互接続ネットワークに結合され、前記タグ付き順序保存要求の各タグに応じて、順番に前記複数のプロセッサから順序保存要求を実行する複数のキャッシュメモリ・スライスと
を有する集積回路を有するマルチプロセッサ。
【請求項３５】
請求項３４に記載のマルチプロセッサであって、
順序保存要求は、要求側の他の順序要求に関して順番の実行を必要とする保存要求であるマルチプロセッサ。
【請求項３６】
請求項３５に記載のマルチプロセッサであって、
前の順序保存要求は、現行の順序保存要求が処理可能になる前に処理を必要とするマルチプロセッサ。
【請求項３７】
請求項３５に記載のマルチプロセッサであって、
無順序保存要求は、他の順序要求に関してばらばらの順番で実行可能な保存要求であるマルチプロセッサ。
【請求項３８】
請求項３４に記載のマルチプロセッサであって、
前記複数のキャッシュメモリ・スライスのそれぞれは、前記総合接続ネットワークを通じて順番に前記順序保存要求を実行するキャッシュ・シーケンス・アレイを有するマルチプロセッサ。
【請求項３９】
請求項３８に記載のマルチプロセッサであって、
前記キャッシュ・シーケンス・アレイは、キャッシュ・シーケンス・エントリとして順序保存要求に関連する保存シーケンス・トークンを保存するキャッシュ・シーケンス・アレイ・テーブルを有し、
前記キャッシュ・シーケンス・エントリは、前記キャッシュメモリ・スライスが現在実行することができる順序保存要求を示すマルチプロセッサ。
【請求項４０】
請求項３４に記載のマルチプロセッサであって、
前記複数のキャッシュメモリ・スライスは、前記複数のプロセッサにより共有される分散キャッシュメモリシステムから前記相互接続ネットワークに結合されるマルチプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してキャッシュメモリ管理に関し、特に無順序ネットワークで共有分散キャッシュメモリシステムに順序保存を提供することに関する。
【背景技術】
【０００２】
低速メインメモリへの平均アクセス時間を改善するために、プロセッサと低速メインメモリとの間に高速キャッシュメモリを使用することは周知である。キャッシュメモリの使用は、プロセッサの実行性能を改善し得る。当初ではキャッシュメモリはプロセッサから離れていたが、後に技術の改善と共にプロセッサの一体部分になった。キャッシュメモリがプロセッサの一体部分になると、キャッシュメモリへのアクセス時間が更に低減され得る。
【０００３】
複数レベルのキャッシュメモリがプロセッサとメインメモリとの間に取り入れられている。一般的に、キャッシュメモリの速度が増加すると、キャッシュメモリがプロセッサに近くなるが、そのサイズが減少する。異なるように解釈すると、キャッシュメモリのサイズが一般的に増加し、アクセス時間が増加すると、キャッシュメモリがプロセッサから離れる。しかし、特に命令が他の命令又はメモリへのアドレスに分岐又はジャンプしたときに、複数レベルのキャッシュメモリはキャッシュ管理を複雑化する。
【０００４】
プロセッサの内部又は外部のメモリコントローラ又はキャッシュコントローラは、メインメモリとプロセッサとの間でキャッシュメモリのキャッシュ管理を提供するために使用されている。キャッシュメモリの使用を最大化し、プロセッサが低速メインメモリからデータ／命令を読み取るため又は低速メインメモリにデータ／命令を書き込むために必要なキャッシュへのミスの数を低減するために、様々なキャッシュメモリ管理アルゴリズムが取り入れられている。共有され得るデータブロックの状態をトラッキングすることにより、キャッシュメモリに保存されたデータの一貫性を維持するために、キャッシュ・コヒーレンス・プロトコル（cache  coherence  protocol）が取り入れられている。他のキャッシュメモリ管理アルゴリズムも取り入れられている。
【発明を実施するための最良の形態】
【０００５】
本発明の以下の詳細な説明では、本発明の完全な理解を提供するために、複数の特定の詳細が示されている。しかし、本発明はこれらの特定の詳細がなくても実施され得ることが、当業者に明らかである。その他に、不要に本発明の態様をあいまいにしないように、周知の方法、手順、構成要素及び回路については説明しない。
【０００６】
本発明の一実施例は、論理的に共有されているが物理的に分散されたキャッシュを共有する複数のプロセッサを備えたシステムを扱う。複数のプロセッサは、相互接続ネットワークで物理的に分散されたキャッシュと通信する。相互接続ネットワークは、１つのプロセッサ又はキャッシュ（“要求側”）から同じ又は異なるキャッシュへの要求の順序を保存しない無順序ネットワークである。更に、相互接続ネットワークで１つのキャッシュが他のキャッシュに送信し得るメッセージもまた、ネットワークにより順番に保持されない。しかし、メッセージは、要求側により送出された順番に実行することを必要とすることがある。これらのメッセージは、順序要求（ordered  request）と呼ばれることがある。順番に実行されることを必要としないメッセージは、無順序要求（non-ordered  request）と呼ばれることがある。要求側により発行された保存要求は、順序保存要求でもよく、無順序保存要求でもよい。
【０００７】
順序要求のサブセットが順序保存要求である。以下に更に説明する順序保存要求は、要求側により発行された他の順序保存要求に関して、順番に実行を必要とする要求側の保存要求である。前の順序保存要求は、現行の順序保存要求が処理される前に処理されなければならない。すなわち、現行の順序保存要求は、後の順序保存要求が処理される前に処理されなければならない。無順序保存要求は、要求側の他の順序要求に関して、ばらばらの順番で実行可能な要求側の保存要求である。
【０００８】
論理的に共有されたキャッシュメモリは、キャッシュメモリの特定のアドレスブロックが物理的に分散されたキャッシュメモリの異なるチャンク（chunk）により管理されるように分割されてもよい。
【０００９】
他の実施例では、論理的に共有されたキャッシのキャッシュ管理は、特定のメモリ一貫性モデルがプロセッサからメインメモリへの特定の保存の処理に設定されるという順序要件を扱う。特別の順番の処理を必要とする特定の保存は、ここでは“順序保存（ordered  store）”又は“順序保存要求（ordered  store  request）”と呼ばれる。その他に、保存は特別の順番の処理を必要としなくてもよく、ここでは“無順序保存（unordered  store）”、“無順序保存要求（unordered  store  request）”又は“無順序保存要求（non-ordered  store  request）”と呼ばれる。これらの無順序保存要求は、ばらばらの順番で実行又は処理可能である。順序保存要求の処理は、現行の順序保存要求の前に発行された前の順序保存要求が、現行の順序保存要求の実行の前に完全に処理されることを必要とする。
【００１０】
１つのプロセッサからの順序保存要求を処理する簡単な低性能の方法は、プロセッサからの全ての前の順序保存要求がキャッシュメモリシステムにより処理されるまで、プロセッサが新しい順序保存要求を発行することを抑制することが挙げられる。しかし、複数のプロセッサからの順序保存要求を処理するマルチプロセッサシステムでは、それほど簡単ではない。マルチプロセッサシステムにおいて複数のプロセッサからの順序保存要求を処理する方法は、更に複雑になる。
【００１１】
本発明の実施例では、順序保存要求を処理する簡単な低性能の方法は、マルチプロセッサシステムをサポートするために、少量の更なる要求トラッキングハードウェアを使用することにより、共有メモリシステムを備えたプロセッサのネットワークで並列処理を利用するように、複数のプロセッサを追加することで改善される。本発明の他の実施例では、ネットワークプロセッサの並列処理は、同時に又は重複する時間間隔で、ネットワークの１つのプロセッサから複数の順序保存要求を処理可能である。１つのプロセッサは、無順序ネットワークでキャッシュシステムに新しい順序保存要求を送信する前に、前の順序保存が完全に完了することを待機する必要はない。
【００１２】
図１を参照すると、本発明が使用され得る一般的なコンピュータシステム100のブロック図が図示されている。コンピュータシステム100は、中央処理ユニット（CPU）101と、入出力装置（I/O）102（キーボード、モデム、プリンタ、外部記憶装置等）と、モニタ装置（M）103（CRT又はグラフィックディスプレイ等）と、情報を保存するメモリ104とを有する。モニタ装置（M）103は、視覚又は聴覚フォーマットのような人間に理解できるフォーマットでコンピュータ情報を提供する。システム100は、メディアアクセスコントローラ（MAC：media  access  controller）のようなネットワーク処理システム又はコンピュータシステムを含む複数の異なるシステムでもよい。
【００１３】
図２Ａを参照すると、本発明の実施例が使用され得る中央処理装置101Aのブロック図が図示されている。中央処理装置101Aは、図示のように結合されたマイクロプロセッサ201と、プログラム命令を保存するメインメモリ202と、ディスク記憶装置203を有する。マイクロプロセッサ201は、１つ以上の実行ユニット210と、少なくとも１つのキャッシュメモリ212と、キャッシュコントローラ214とを有する。マイクロプロセッサ201は、メインメモリ202へのアクセスを制御するための別々のメモリコントローラ216を有してもよい。この場合、メモリコントローラは、マイクロプロセッサ201の他の要素とメインメモリ202とをインタフェース接続する。理想的には、実行ユニット210は、低速メインメモリ202に直接アクセスする必要なく、キャッシュメモリ212にデータを読み／書きする。すなわち、実行ユニットがキャッシュメモリ212へのミスを回避することが望ましい。キャッシュメモリ212のサイズに物理的な制限が存在する。しかし、マルチプロセッサシステムでは、システムは、各プロセッサの内部のキャッシュメモリ212が論理的に共有され得るように設計可能である。他の実施例では、プロセッサ内の１つ以上の内部キャッシュメモリに加えて、１つ以上の外部キャッシュメモリが備えられ、マルチプロセッサシステムの相互接続ネットワークで複数のプロセッサにより論理的に共有されてもよい。
【００１４】
ディスク記憶装置203は、フロッピー（登録商標）ディスク、ZIPディスク、DVDディスク、ハードディスク、再書込可能光ディスク、フラッシュメモリ又はその他の不揮発性記憶装置でもよい。マイクロプロセッサ201及びディスク記憶装置203は、メモリバスでメモリ202に情報を読み書きすることができる。このように、マイクロプロセッサ201及びディスク記憶装置203は、プログラム実行中にメモリ202内のメモリ位置を変更することができる。ディスク記憶装置203がこれを直接行うために、直接メモリアクセスを備えたディスクコントローラを有し、そのディスクコントローラはメモリへの保存を実行可能であり、それによってコードを変更可能である。コントローラはメモリに直接アクセスすることができるため、直接メモリアクセス（DMA：Direct  Memory  Access）エージェントの一例である。メモリに情報を保存するために直接アクセスを有する他の装置もDMAエージェントである。メモリ202は、一般的にはダイナミック・ランダムアクセスメモリ（DRAM：dynamic  random  access  memory）であるが、その他の形式の再書込可能記憶装置でもよい。
【００１５】
ディスク記憶装置203又はその他のソース（I/O装置102）に保存されたプログラムの初期実行時に、マイクロプロセッサ201は、ディスク記憶装置203又は他のソースに保存されたプログラム命令及びデータを読み取り、それらをメモリ202に書き込む。メモリ202内に保存されたプログラム命令の１つ以上のページ又はその一部は、命令キャッシュ（図３に図示せず）に保存するために、マイクロプロセッサ201により読み取られる（すなわち“フェッチ”される）。命令キャッシュに保存されたプログラム命令のいくつかは、マイクロプロセッサ201による実行のために、命令パイプライン（図示せず）に読み取られてもよい。メモリ202内に保存されたデータの１つ以上のページ又はその一部は、データキャッシュに保存するために、マイクロプロセッサ201により読み取られてもよい（すなわち“フェッチ”される）。他の実施例では、命令とデータとの双方が同じキャッシュメモリに保存されてもよい。
【００１６】
図２Ｂを参照すると、本発明の実施例が使用され得るマルチプロセッサシステム101Bのブロック図が図示されている。マルチプロセッサシステム101Bは、マルチプロセッサ中央処理装置でもよい。マルチプロセッサシステム101Bは、複数のプロセッサ201A-201Jを有する。複数のプロセッサ201A-201Jのそれぞれは、１つ以上の実行ユニット210A-201Nを有する。実行ユニットは、コアと呼ばれることもある。複数のプロセッサ201A-201Jのそれぞれは、１つ以上の実行ユニット210A-210Jに結合する１つ以上のレベルの内部キャッシュメモリ・スライス（CMS：cache  memory  slice）212A-212Mを更に有してもよい。複数のプロセッサ210A-210Jのそれぞれは、I/O装置及び／又はモニタ装置に結合してもよい。
【００１７】
マルチプロセッサシステム101Bは、相互接続ネットワークを通じて相互に結合され、複数のプロセッサ201A-201Jに結合された１つ以上のレベルの外部キャッシュメモリ・スライス（CMS：cache  memory  slice）212A’-212L’を更に有する。マルチプロセッサシステム101Bは、相互接続ネットワーク250に結合された１つ以上のメインメモリ202A-202Kと、相互接続ネットワーク250に結合されたディスク記憶装置203とを更に有してもよい。
【００１８】
プロセッサ202A-201J、キャッシュメモリ・スライス212A’-212L’及びディスク記憶装置203は、メインメモリ202A-202Kに情報を直接読み書きしてもよい。すなわち、メインメモリ202A-202Kは、プロセッサ202A-201Jとキャッシュメモリ・スライス212A’-212L’とディスク記憶装置203とにより共有可能である。更に、相互接続ネットワーク250を通じて、プロセッサ202A-201Jとメインメモリ202A-202Kとキャッシュメモリ・スライス212A’-212L’とディスク記憶装置203との間で、メッセージが伝達されてもよい。相互接続ネットワーク250でメッセージングを使用することにより、マルチプロセッサシステム101Bで順序保存要求の順番の実行又は処理が提供されてもよい。
【００１９】
図３Ａを参照すると、マルチプロセッサシステム101Cのブロック図が図示されている。マルチプロセッサシステム101Cは、プライマリ相互接続ネットワーク300Aと、内部キャッシュメモリ312Aをそれぞれ有する複数のプロセッサ301A-301Jと、複数のプロセッサ301A-301Jと相互接続ネットワーク300Aとの間に結合された１つ以上の上位レベルキャッシュメモリ312Bと、相互接続ネットワーク300Aに結合されたキャッシュメモリ・スライス312Cのレベルと、相互接続ネットワーク300Aに結合されたキャッシュメモリ・スライス312Dの他のレベルと、セカンダリ相互接続ネットワーク300Bを通じてプライマリ相互接続ネットワーク300Aに結合されたキャッシュメモリ・スライス312Eのその他のレベルとを有してもよい。
【００２０】
マルチプロセッサシステム101Cは、１つ以上のメインメモリ302A、302B及び／又は302Cを更に有してもよい。メインメモリ302Aは、プライマリ相互接続ネットワーク300Aに直接結合されてもよい。メインメモリ302Bは、セカンダリ相互接続ネットワーク300Bを通じてプライマリ相互接続ネットワーク300Aに結合されてもよい。メインメモリ302Cは、セカンダリ相互接続ネットワーク300Bを通じて低レベルキャッシュメモリ・スライス312Eとプライマリ相互接続ネットワーク300Aとに結合されてもよい。
【００２１】
内部キャッシュメモリ312A、１つ以上の上位レベルキャッシュメモリ312B、キャッシュメモリ・スライス312Cのレベル、キャッシュメモリ・スライス312Dのレベル及びキャッシュメモリ・スライス312Eのレベルは、物理的に分散されたマルチレベルキャッシュメモリシステムの実施例を形成してもよい。物理的に分散されたマルチレベルメモリシステムの実施例は、キャッシュメモリ・スライスに含まれるメインメモリ302A、302Bを備える。
【００２２】
プロセッサ、キャッシュメモリ・スライス及びメインメモリは、相互接続ネットワークのノードとして考えられてもよい。メッセージは、１つのノードから他のノードに相互接続ネットワークを通じて流れてもよく、１つのノードから他の全てのノードにブロードキャストされてもよい。マルチプロセッサシステム101C並びに相互接続ネットワーク300A及び300Bのトポロジは、バス型ネットワークトポロジ、ツリー型ネットワークトポロジ、リング型ネットワークトポロジ、グリッド若しくはメッシュ型ネットワークトポロジ、トーラス型ネットワークトポロジ、超立方体型ネットワークトポロジ、全接続型トポロジ、又はそれらの組み合わせでもよい。
【００２３】
相互接続ネットワーク300A及び300Bは、集積回路で経路設定されたワイヤートレース（wire  trace）、同じ集積回路で経路設定されたバス、及び／又は同じ集積回路の機能ブロック間の１つ以上のスイッチでもよい。代替として、相互接続ネットワーク300A及び300Bは、集積回路の間に経路設定されたワイヤートレース、集積回路の間のバス、及び／又は集積回路の間の１つ以上のスイッチでもよい。プライマリ相互接続ネットワーク300Aとセカンダリ相互接続ネットワーク300Bとを相互接続するために、スイッチ、ブリッジ又はルータ（図示せず）が使用されてもよく、それにより、メッセージがそれに従ってあちこちに通過してもよい。
【００２４】
メッセージは相互接続ネットワークを通じて流れるため、ノードからノードに経路設定されるときに又はノードから全ノードに経路設定されるときに、異なる遅延を受けることがある。これらの異なる遅延は、メッセージ転送の無順序のシーケンスを引き起こすことがある。すなわち、相互接続ネットワークは、順番の保存要求を処理するときの無順序ネットワークである。
【００２５】
図３Ｂを参照すると、マルチプロセッサシステム101C’のブロック図が図示されている。図３Ｂは、プライマリ相互接続ネットワーク300Aを含む図３Ａのシステム101C’の大部分が単一のモノリシック集積回路（IC：integrated  circuit）チップ350の一部でもよいことを示している。すなわち、メインメモリ302Cを除いて、システム101Cの要素は、システム101C’に示すように単一のシリコンチップ350に併せて一体化されてもよい。
【００２６】
図３Ｃを参照すると、マルチプロセッサシステム101C’’のブロック図が図示されている。図３Ｃは、複数の集積回路（IC：integrated  circuit）チップ360A-360Bの一部であるプライマリ相互接続ネットワーク300Aで集積回路境界を通じてシステム101Cが分割されてもよいことを示している。システム101Cの要素は、複数のシリコンチップに併せて一体化されてもよい。代替として、マルチプロセッサシステム101C’’の要素は、共通バックプレーン又はマザーボードのプリント基板（PCB：print  circuit  board）のトレース等を通じて相互に電気結合された１つ以上のプリント基板でもよい。
【００２７】
図４を参照すると、物理分散キャッシュメモリシステム400のブロック図の論理図が図示されている。物理分散キャッシュメモリシステム400は、ハッシュ・アドレスを生成するアドレス・ハッシュ制御ロジック404と、プライマリ相互接続ネットワーク300A又はプライマリ相互接続ネットワーク300A及びセカンダリ相互接続ネットワーク300Bでハッシュ・アドレスでのメッセージを受信する１つ以上のキャッシュメモリ・スライス412A-412Kとを有する。１つ以上のキャッシュメモリ・スライス412A-412Kのそれぞれは、メモリセル414A-414Kの１つ以上のブロックを有する。
【００２８】
物理分散キャッシュメモリシステム400は、プロセッサ又はキャッシュメモリのような要求側により共有される。メモリセルの１つのアドレスブロックが１つのキャッシュメモリ・スライスに関連付けられて、メモリセルの次のアドレスブロックが他のキャッシュメモリ・スライスに関連付けられるように、物理分散キャッシュメモリシステム400は複数の方法で分割されてもよい。要求側からのアドレス402は、キャッシュメモリ・スライスと、そのメモリセルの１つ以上のブロックとを選択するために、アドレス・ハッシュ・ロジック404によりハッシュされる。
【００２９】
図３Ａ及び４を参照すると、１つ以上のプロセッサ301A-301Jは、順序保存要求が物理分散キャッシュシステム400により実行されることを要求することができる。代替として、１つ以上のキャッシュメモリ312A、312B又は分散キャッシュメモリシステム400の階層の上位レベルのキャッシュメモリ・スライスは、順序保存要求が分散キャッシュメモリシステム400の他のレベルにより実行されることを要求することができる。このような要求を行うキャッシュメモリ・スライスは、一般的にプロセッサの近くである。このような要求を行うキャッシュメモリは、プロセッサの内部キャッシュメモリ312A又は上位レベルキャッシュメモリ312Bを有してもよい。順序保存を要求するプロセッサとキャッシュメモリとキャッシュメモリ・スライスとを併せて、要求側と呼ぶことがある。各要求側は、順序保存要求を生成する制御ロジック及び他のハードウェア要素を有する。以下の説明では、“Nc”は物理分散キャッシュを構成するキャッシュメモリ・スライスの数を表し、“Np”は分散キャッシュを共有する要求側の数を表す。
【００３０】
一時的に図７を参照すると、メモリ階層の１つのレベルのプロセッサ／キャッシュ要求側701が、順序保存要求の順番の実行を行うことができるメモリ階層の異なるレベルのキャッシュメモリ・スライス702A及び702Bと通信するように図示されている。
【００３１】
各プロセッサ／キャッシュ要求側701は、“j”の一定値を有する固有の要求側識別子（“RID：requestor  identifier”）704と、“t”の変数値を有する単一のトークン・レジスタ（“TR：token  register”）706とを有する。固有の要求側識別子は、固有の要求側識別表示とも呼ばれることがある。トークン・レジスタは、シーケンス・トークン・レジスタと呼ばれることがあり、トークン値“t”はまた、保存シーケンス・トークン又は保存シーケンス番号と呼ばれることがある。トークン・レジスタ（“TR：token  register”）706は、“b”ビット幅であり、プロセッサ／要求側によりサポートされる未解決の順序保存要求の数に応じて、2bビット幅を有することができる。“S”は各プロセッサがサポートする未解決の順序保存要求を表すと仮定すると、トークン・レジスタのビット数は、“b”=ceiling[log2(S)]の式から決定され得る。トークン・レジスタにより保持される値はまた、要求側シーケンス・トークンとも呼ばれることがある。トークン・レジスタは、順序保存要求が生成される毎に増加し得る。トークン・レジスタは、その最大値を超えて増加したときに、その初期値（一般的に0）にラップアラウンド（すなわちロールオーバー）して戻ることができる。しかし、一実施例では、最大ネットワーク待ち時間（すなわち最大ネットワーク遅延）に比較して、Sは十分に大きく、“b”のビット数も十分に大きい。それにより、トークン・レジスタがロールオーバーするときまでに、プロセッサは全てを処理している。他の実施例では、ロールオーバーしようとしているTRレジスタを備えたプロセッサ／要求側は、各キャッシュメモリ・スライスをポーリングし、それぞれが全てのタグ付きメモリ要求を処理してS-1に到達したか否かを決定する。全てのキャッシュメモリ・スライスが終了したことをプロセッサに応答すると、プロセッサは、その所定のTRレジスタがロールオーバーすることを許可し得る。
【００３２】
要求側識別子（“RID：requestor  identifier”）704の値“j”は固有である。すなわち、要求側識別子の２つの値は、分散キャッシュメモリシステムでの同じマルチプロセッサシステムで同じではない。各要求側識別子（“RID”）704の値“j”が固有であるため、各レジスタ701のトークン・レジスタの値“t”は、“j”と“t”とを一緒に付加することにより、固有になり得る。すなわち、相互接続ネットワークで分散キャッシュメモリシステムに通信される前に、トークンに要求側識別子を追加することにより、トークン・レジスタTRを“固有”にすることができる。
【００３３】
順序保存要求の順番の実行を行うことができる分散キャッシュメモリのメモリ階層の各キャッシュメモリ・スライス（キャッシュメモリ・スライス702A及び702B等）は、キャッシュ・シーケンス・アレイ（CSA：cache  sequence  array）712を有する。キャッシュ・シーケンス・アレイ（CSA）712は、“b”ビット幅の“Np”のエントリを備えたテーブルである。キャッシュ・シーケンス・アレイ（CSA）712は、要求側識別子（“RID”）704毎に、分散キャッシュシステムの所定のキャッシュメモリ・スライスにより処理可能な次の順序保存の識別を決定する。Npの要求側が存在するため、キャッシュ・シーケンス・アレイ（CSA）にはNpのエントリが存在する。
【００３４】
図５Ａ−５Ｂを参照する。図５Ａは、タグ付き順序保存要求500の一般的なフィールドの図を示している。図５Ｂは、CSA更新510の一般的なフィールドの図を示している。順序保存要求をサポートするために、要求側識別子（RID）フィールド501（“j”の値）と、トークン・レジスタ値フィールド502（“t”の値）と、メッセージ識別子（MID：message  identifier）フィールド504とのビットフィールドが、タグ付き順序保存要求500とCSA更新510との双方で使用される。要求側識別子（RID）フィールド501（“j”の値）と、トークン・レジスタ値フィールド502（“t”の値）とのビットフィールドは、併せてTRU503と呼ばれることがある。すなわち、TRU504は、要求側id“j”と要求側jのトークン・レジスタTRの値“t”との連結を表す。TRU504の値は“j.t”として表示されることもできる。ただし、jは要求側識別子であり、“t”は要求側jのトークン・レジスタTRの値である。
【００３５】
メッセージ識別子（MID）フィールド504は、順序保存要求（OSR：ordered  store  request）504A又はCSA更新504Bを示すコードである。他のメッセージ形式を示すために、メッセージ識別子（MID）フィールド504の他のコードが使用されてもよい。
【００３６】
メッセージ識別子フィールド504がタグ付き保存要求500の順序保存要求（OSR）コード504Aを示す場合、アドレスフィールド505及びデータフィールド506がタグ付き順序保存要求500の一部として含まれる。換言すると、要求側識別子（RID）フィールド501（“j”の値）及びトークン・レジスタ値フィールド502（“t”の値）のビットフィールドは相互に連結され、保存されるアドレス505とデータ506とを含む順序保存要求コード504Aに追加される。このように、タグ付き順序保存要求500が形成される。
【００３７】
メッセージ識別子フィールド504がCSA更新コード504Bを示し、順序保存要求（OSR）コード504Aを示さない場合、アドレスフィールド505及びデータフィールド506は、分散キャッシュメモリシステム400に送信されるメッセージに含まれない。この場合、要求側識別子（RID）フィールド501（“j”の値）及びトークン・レジスタ値フィールド502（“t”の値）のビットフィールドは、処理された順序保存要求に基づき、CSA更新コード504Bに付加される。
【００３８】
一実施例では、タグ付き順序保存要求500及びCSA更新510のデータビットフィールドは、相互接続ネットワーク300A、300Bで、要求側からキャッシュメモリ・スライスに又は１つのキャッシュメモリ・スライスから他のキャッシュメモリ・スライスにパケットで流れてもよい。他の実施例では、タグ付き順序保存要求500及びCSA更新510のデータビットフィールドは、相互接続ネットワークの並列相互接続バスで並列に流れてもよい。他の実施例では、タグ付き順序保存要求510及びCSA更新510のデータビットフィールドは、相互接続ネットワークの直列相互接続で連続的に流れてもよい。更に他の実施例では、タグ付き順序保存要求500及びCSA更新510のデータビットフィールドは、相互接続ネットワークで並列又は直列の１つ以上のパケットの組み合わせにより流れてもよい。その他に、タグ付き順序保存要求500は要求側により生成されて相互接続ネットワークに送信され、CSA更新510は順序保存要求を実行したキャッシュメモリ・スライスにより生成されて相互接続ネットワークに送信される。
【００３９】
図６Ａを参照すると、キャッシュメモリ・スライス602のブロック図が図示されている。キャッシュメモリ・スライス602は、キャッシュメモリ・スライスの単一のインスタンスを示している。キャッシュメモリ・スライス602は、キャッシュ・シーケンス・アレイ604と、順序保存要求の順番の実行をサポートするキャッシュ制御ロジック606とを有する。キャッシュ制御ロジック606はまた、キャッシュメモリに関連する一般的なキャッシュ制御機能を提供することができる。キャッシュメモリ・スライス602は、図６Ａに図示するように相互に結合された要求バッファ608と、キャッシュ・タグ・ビット610と、キャッシュ・データ・アレイ612と、タグ照合ロジック614と、列選択616とを更に有する。
【００４０】
要求バッファ608は、キューでの処理のために、キャッシュ保存要求を一時的に保持する。一般的にキャッシュ・タグ・ビット610は、有効ビットと他の状態ビットと共にメモリセルのキャッシュラインの内容を特定するのに役立つ上位アドレスビットである。キャッシュ・データ・アレイ612は、データを保存するためのメモリセルの行及び列の配列である。タグ照合ロジック614は、所定のキャッシュメモリ・スライスにヒット又はミスが存在するか否かを決定する。ヒットは、所望のデータが所定のキャッシュメモリ・スライスのキャッシュ・データ・アレイ612内に保存されていることを示す。ミスは、所望のデータがキャッシュ・データ・アレイ612内に保存されておらず、要求が分散キャッシュメモリシステムの階層の次のレベルに渡される必要があることを示す。列選択616は、メモリセルの列がキャッシュ・データ・アレイ612から選択されるべきであるか否かについて、ヒット及びミスの指示に応じる。
【００４１】
キャッシュ・シーケンス・アレイ604により、キャッシュメモリ・スライス602が物理分散キャッシュメモリシステムを通じて順番に順序保存要求を実行することが可能になる。キャッシュ・シーケンス・アレイ604は、キャッシュ・シーケンスのエントリとして１つ以上の順序保存要求に関連する１つ以上の保存シーケンス・トークンを保存する。
【００４２】
図６Ｂを参照すると、キャッシュ・シーケンス・アレイ（CSA：cache  sequence  array）604のブロック図が図示されている。キャッシュ・シーケンス・アレイ（CSA）604は、キャッシュ・シーケンス・アレイ（CSA）テーブル632を有する。キャッシュ・シーケンス・アレイ（CSA）テーブル632は、要求側j毎に保存シーケンス・トークンtを保存する。要求側識別子jは、キャッシュ・シーケンス・アレイ（CSA）テーブル632へのアドレスとして機能し、それによってアドレス指定されたデータをキャッシュ制御ロジック606に送信する。
【００４３】
キャッシュ・シーケンス・アレイ（CSA）テーブル632の各キャッシュ・シーケンスのエントリは、所定のキャッシュメモリ・スライスが所定の要求側jから順番に実行し得る現行の保存シーケンス・タグtを示す。順序保存要求がその要求側jのキャッシュ・シーケンス・エントリに一致する所定のキャッシュメモリ・スライス602にハッシュされている場合、キャッシュメモリ・スライスは順序保存要求を実行する。異なる順序保存要求がその要求側jのキャッシュ・シーケンス・エントリに一致しない所定のキャッシュメモリ・スライス602にハッシュされている場合、キャッシュメモリ・スライスは現時点で順序保存要求を実行しないが、その代わりに、後の処理のために要求バッファ608又は他のキューにそれを保持する。このように、順序保存要求は順番に実行可能である。
【００４４】
キャッシュメモリ・スライス内のキャッシュ・シーケンス・アレイ（CSA）テーブル632は、要求側毎に１つの順序保存要求エントリを維持する。このように、各キャッシュメモリ・スライスは、要求側j毎に順序保存要求の実行順序を維持することができる。
【００４５】
図７を参照すると、順序保存要求の順番の実行の例示的なシーケンスを示すブロック図は、タグ付き順序保存要求を生成し、順序保存要求を実行し、キャッシュ・シーケンス更新メッセージを発行することを有する。
【００４６】
前述のように、各プロセッサ／キャッシュ要求側701は、“j”の値を有する固有の要求側識別子（“RID”）704と、“t”の値を有する単一のトークン・レジスタ（“TR”）706とを有する。各プロセッサ／キャッシュ要求側701は、順序保存要求（例えば、ST.REL  A、ST.REL  B）を保存するワークキュー707と、タグ付き順序保存要求500の生成を制御して、その中のメモリセル及び適切なキャッシュメモリ・スライスを選択するためにアドレスをハッシュ又は変換する制御ロジック708とを更に有する。
【００４７】
前述のように、順序保存要求の順番の実行を行うことができる分散キャッシュメモリのメモリ階層の各キャッシュメモリ・スライスは、キャッシュ・シーケンス・アレイ（CSA）を有する。図７は、キャッシュ・シーケンス・アレイ（CSA）712を有するキャッシュメモリ・スライスk702A及びキャッシュメモリ・スライスm702Bを示している。
【００４８】
動作中に、要求側j701は、要求側IDjと現行のトークン・レジスタ値tとを付加して、キュー707内にある順序保存要求の１つのアドレスを使用して、タグ付き順序保存要求500を生成する。要求側j701のコントローラ708は、タグ付き順序保存要求500を発行する。順序保存要求は値“j.t”でタグ付けされる。時間Xにおいて、矢印721で示すように、ST.REL  Aのタグ付き順序保存要求はキャッシュ・スライスk702Aに送信される。要求側j701において、ST.REL  Aのタグ付き順序保存要求がキャッシュ・スライスk702Aに送信された後に、トークン・レジスタ706が(t+1)の値に増加する。
【００４９】
例えば、要求側j701が、物理分散キャッシュメモリシステムへのタグ付き順序保存要求として異なるアドレス“A”及び“B”にタグ付けして発行する準備ができている“ST.REL  A”及び“ST.REL  B”で示す２つの順序保存要求を有することを仮定する。順序保存要求“ST.REL  A”は順序保存要求“ST.REL  B”より古く、順番の実行を実現するために最初に処理されなければならない。しかし、異なるアドレス“A”及び“B”を用いて、２つの順序保存要求“ST.REL  A”及び“ST.REL  B”は異なる部分（物理分散キャッシュメモリシステムのキャッシュメモリ・スライスk702A及びキャッシュメモリ・スライスm702B）により処理される。
【００５０】
矢印721で示すように、まず、要求側j701は、“j.t”でタグ付けされた順序保存要求“ST.REL  A”でキャッシュメモリ・スライスk702Aにタグ付き順序保存要求を発行する。キャッシュメモリ・スライスk702Aがこのタグ付き順序保存要求を処理すると、保存を実行して更新を実行する。すなわち、矢印722で示すように、キャッシュメモリ・スライスk702Aは、他の全てのキャッシュメモリ・スライスに“j.x”を有するキャッシュ・シーケンス・アレイ（CSA）更新をブロードキャストする。値x=t+1である。キャッシュメモリ・スライスk702Aは、そのCSA更新を実行するために要求側jに対応するその自分のCSA[j]のエントリを増加する。
【００５１】
ST.REL  Aのタグ付き順序保存要求を受信すると、キャッシュメモリ・スライスk702Aは、順番にタグ付き順序保存要求を実行することができるか否かを決定する。これを行うために、キャッシュ・スライスk702Aは、そのキャッシュ・シーケンス・アレイ（CSA）712と、要求側j701のエントリとを調べる。キャッシュメモリ・スライスk702Aが順番にタグ付き順序保存要求を実行することができるか否かを決定する方法は、図９Ａ及び９Ｂを参照して以下に更に説明する。キャッシュメモリ・スライスk702Aが順番にタグ付き順序保存要求を実行することができることを決定することを仮定すると、それはこれを行う。キャッシュメモリ・スライスk702AがST.REL  Aのタグ付き順序保存要求を処理又は実行した後に、tの値は(t+1)に増加して要求側IDjを付与され、値j.t+1で他の全てのキャッシュメモリ・スライスに対するCSA更新510を生成及び発行する。矢印722は、CSA更新がキャッシュメモリ・スライスm702Bを含む他の全てのキャッシュメモリ・スライスに送信されることを示している。これは、CSA更新を受信したキャッシュが“j.t+1”の値を有するタグ付き順序保存要求を処理することができることを示している。
【００５２】
タグ付き順序保存要求は、様々な理由で所定のキャッシュメモリ・スライスでバラバラの順番になる。例えば、CSA更新が所定のキャッシュメモリ・スライスで適時に受信されなかったため、タグ付き順序保存要求がバラバラの順番になる可能性がある。他の例として、前の順序保存要求が完全に処理されてCSA更新が発行される前に他のタグ付き順序保存要求が発行されたため、タグ付き順序保存要求がバラバラの順番になる可能性がある。更に他の例として、全てのCSA更新が所定の要求側jの他のキャッシュメモリ・スライスから受信される前に後のタグ付き順序保存要求が受信されたため、タグ付き順序保存要求がバラバラの順番になる可能性がある。
【００５３】
例を続けると、時間X+e（eは正数である）に、矢印723で示すように、要求側jは、“j.(t+1)”でタグ付けされた順序保存要求“ST.REL  B”を含むタグ付き順序保存要求をキャッシュメモリ・スライスm702Bに発行する。要求側j701において、ST.REL  Bのタグ付き順序保存要求がキャッシュ・スライスm702Bに送信された後に、トークン・レジスタ706が(t+2)の値に増加する。
【００５４】
ST.REL  Bのタグ付き順序保存要求を受信すると、キャッシュメモリ・スライスm702Bは、順番にタグ付き順序保存要求を実行することができるか否かを決定する。これを行うために、キャッシュ・スライスm702Bは、そのキャッシュ・シーケンス・アレイ（CSA）712と、要求側j701のエントリとを調べる。
【００５５】
キャッシュメモリ・スライスm702Bは、CSA712の要求側jのCSA[j]のそのエントリが(t+1)に等しいか否かを確認する。この場合に、キャッシュメモリ・スライスk702Aが順序保存要求“ST.REL  A”を既に処理しており、キャッシュメモリ・スライス702Bmが対応のCSA更新を受信したことを仮定すると、キャッシュメモリ・スライス702Bm（300）は、要求側jのCSA[j]のそのエントリが(t+1)に等しいため、“ST.REL  B”を処理することができる。
【００５６】
しかし、キャッシュメモリ・スライスk702AからのCSA更新がキャッシュメモリ・スライスm702Bに到達する前に、要求側jが順序保存要求“ST.REL  B”を発行することを仮定すると、キャッシュメモリ・スライスm702Bは、トークン“j.x”を備えたCSA更新が到達するまで、“ST.REL  B”を含むタグ付き順序保存要求をネットワーク又はローカルバッファに保持し続ける。この場合、CSA更新はバラバラの順番になり、キャッシュメモリ・スライスは、処理用に有する順序保存要求を適切に処理しなければならない。
【００５７】
キャッシュメモリ・スライスm702Bが順番にタグ付き順序保存要求を実行することができることを決定することを仮定すると、それはこれを行う。キャッシュメモリ・スライスm702BがST.REL  Bのタグ付き順序保存要求を処理又は実行した後に、(t+1)の値は(t+2)に増加して要求側IDjを付与され、値j.t+2で他の全てのキャッシュメモリ・スライスに対するCSA更新510を生成及び発行する。矢印724は、CSA更新がキャッシュメモリ・スライスm702Aを含む他の全てのキャッシュメモリ・スライスに送信されることを示している。これは、CSA更新を受信したキャッシュが“j.t+2”の値を有するタグ付き順序保存要求を処理することができることを示している。
【００５８】
キャッシュメモリ・スライスm702Bが“j.t+1”の値でのCSA更新を受信していないことを仮定すると、“j.t+1”の値を備えたタグ付き順序保存要求を順番に実行することができない。キャッシュメモリ・スライスm702Bは、“j.t+1”の値を備えたタグ付き順序保存要求を実行する前に、“j.t+1”の値を備えたCSA更新を受信するまで待機しなければならない。
【００５９】
図８を参照すると、タグ付き順序保存要求をサポートするために要求側j701の制御ロジック708により実行される制御機能のフローチャートが図示されている。前述のように、この説明では、数字“Np”は分散キャッシュを共有するプロセッサの数を表す。
【００６０】
800において、システムは初期化又はリセットされる。802において、全てのプロセッサ及びキャッシュ要求側j701は、そのトークン・レジスタTR706及びトークン値“t”を初期値（0等）に設定する。以下に更に説明するように、各キャッシュメモリ・スライスのキャッシュ・シーケンス・アレイ（キャッシュメモリ・スライス702A、702Bのキャッシュ・シーケンス・アレイ712等）の全てのエントリも同様に、“t”について同じ初期値（0等）に設定される
804において、制御ロジックは、要求側j701が順序保存要求を物理分散キャッシュメモリシステムに送信する準備ができているか否かを決定する。そうでない場合には、制御ロジックは804にループバックし、基本的に順序保存要求の発行を待機する。順序保存要求が処理のために物理分散キャッシュメモリシステムに送信された場合、制御ロジックは806に進む。
【００６１】
806において、順序保存要求は、図５Ａに示すように、RID“j”501とトークン・レジスタ値“t”502とを含むTRUタグ503の現行の値でタグ付けされる。TRUタグ503の値は“j.t”として示される。次に制御ロジックは808に進む。
【００６２】
808において、要求側j701の制御ロジック708はトークン・レジスタTR706を増加し、それにより、tの現行の値は、次の順序保存要求で後に使用するためにt+1の値を割り当てられる。次に制御ロジックは810に進む。
【００６３】
810において、タグ付き順序保存要求500が物理分散キャッシュメモリシステムに発行される。タグ付き順序保存要求のアドレスはハッシュされ、タグ付き順序保存要求は適切なキャッシュメモリ・スライス（キャッシュメモリ・スライスk702A等）に送信される。
【００６４】
図９Ａは、タグ付き順序保存要求をサポートするために各キャッシュメモリ・スライスの制御ロジック714により実行される制御機能の第１のフローチャートである。図９Ｂは、タグ付き順序保存要求をサポートするために各キャッシュメモリ・スライスの制御ロジック714により実行される制御機能の第２のフローチャートである。
【００６５】
図９Ａを参照すると、順序保存要求が処理可能であるか否かを決定することについて、各キャッシュメモリ・スライスの制御ロジック714により実行される制御機能のフローチャートが図示されている。900において、800で前述したように、システムが初期化又はリセットされる。902において、各キャッシュメモリ・スライスのキャッシュ・シーケンス・アレイ712の全てのエントリは、“t”の初期値（0等）に設定される。これは、各要求側j701がそのトークン・レジスタTR706について有する初期トークン値“t”と一致する。次に制御ロジックは904に進む。
【００６６】
904において、各キャッシュメモリ・スライスの制御ロジックは、要求側からタグ付き順序保存要求501を受信しているか否かを決定する。そうでない場合、制御ロジックは904にループバックし、基本的にタグ付き順序保存要求の受信を待機する。タグ付き順序保存要求が処理のために受信された場合、制御ロジックは906に進む。
【００６７】
906において、TRUタグj.tはタグ付き順序保存要求から抽出され、順序保存要求が所定のキャッシュメモリ・スライスにより処理可能であるか否かを決定する。受信した要求側識別子“j”の値について、キャッシュメモリ・スライスは順序保存要求の値（値CSA[j]（0の初期値を仮定すると、jは0〜(S-1)の値をとる））を行ったプロセッサのキャッシュ・シーケンス・エントリを読み取る。“S”が、各プロセッサがサポートする未解決の順序保存の数を表すことを思い出されたい。
【００６８】
908において、要求側jのCSA[j]エントリ、予想シーケンス番号は、順序保存要求のタグの“t”の部分と比較される。CSA[j]が順序保存要求のタグの“t”の部分と一致する場合、要求は処理可能である。CSA[j]がタグの“t”の部分と等しくない場合、タグは一致せず、制御ロジックは913に進む。CSA[j]がタグの“t”の部分と等しい場合、タグは一致し、制御ロジックは912に進む。
【００６９】
913において、対応するタグ付き順序保存要求（タグを含む）が、後の処理のためにキャッシュの通常のワークキューに保存される。
【００７０】
912において、タグが一致する場合（CSA[j]=t）、キャッシュは順序保存要求を処理して914に進む。
【００７１】
914において、CSA[j]エントリが所定の要求側について増加し、制御ロジックは916に進む。
【００７２】
916において、CSA更新が他の全てのキャッシュメモリ・スライスに発行される。タグ付き順序保存要求を処理した所定のキャッシュメモリ・スライスは、システムの他の全てのキャッシュメモリ・スライスにトークンj.(t+1)を発行し、（処理するものがある場合に）トークン値t+1に対応する要求側jからのメッセージを処理することができることを示す。要求側はまた、その自分のトークンを増加させ、CSA更新の後に何らかの一致する要求についてワークキューを検査する。
【００７３】
ばらばらのCSA更新の処理について説明する。前述のように、物理分散キャッシュメモリ・スライスのネットワークは、順番に処理可能なように、タグ付き順序保存要求を並び替えることができる。しかし、物理分散キャッシュメモリ・スライスのネットワークはまた、同様に各キャッシュメモリ・スライスにより受信されたCSA更新も並び替えることができる。
【００７４】
一時的に図７を参照して、例えばキャッシュメモリ・スライス701Aが近くのキャッシュに連続してタグ更新j.(t+1)及びj.(t+2)を含む２つのCSA更新を送出し、キャッシュメモリ・スライス702Bにばらばらの順番で到達したことについて検討する。更に、キャッシュメモリ・スライス702Bがタグ更新j.(t+1)及びj.(t+2)を含むCSA更新を待機する必要があるタグ付き順序保存要求を有するが、キャッシュメモリ・スライス702Aからタグ更新j.t+2を示す唯一のCSA更新を受信したことを仮定する。このシナリオでは、CSA更新は順序が狂っている。
【００７５】
キャッシュメモリ・スライスが狂った順序でCSA更新メッセージのタグ更新を受信した場合（タグ更新j.t+1、j.t+2、j.t+3及びj.t+4を受信する前にタグ更新j.t+5を受信した場合）、何らかの他のキャッシュメモリ・スライスは、j.t+2、j.t+3等を順番に生成してタグ更新j.t+5の発行を起動するために順番にj.t+1を受信する必要がある。従って、キャッシュメモリ・スライスが前の更新を受信せずにタグ更新j.t+nを受信した場合、タグ更新j.t+nの受信時に、キャッシュがj.t+nを含むそれまでの全ての順序保存を処理することが安全である。
【００７６】
t+nの更なる動作は2bを法として実行される。ただし、bはタグのカウンタ部分のビット数である。カウンタが限られた数のbビットを有するため、更なる動作は、最大カウンタ値を超過して小さい値にロールオーバーしてもよい。ロールオーバー状態の否定的な影響を回避するように注意しなければならない。一実施例では、ビット“b”の数は、最大ネットワーク待ち時間（すなわち最大ネットワーク遅延）に比較して十分であり、それにより、トークン・レジスタがロールオーバーするときまでに、プロセッサは全ての前の順序保存要求を処理している。他の実施例では、ロールオーバーしてもよいTRレジスタを備えたプロセッサ／要求側は、各キャッシュメモリ・スライスにポーリングし、それぞれが全てのタグ付きメモリ要求を処理してS-1に到達しているか否かを決定する。全てのキャッシュメモリ・スライスが終了したとプロセッサに応答すると、プロセッサは、その所定のTRレジスタがロールオーバーすることを許可する。
【００７７】
各要求側のTRカウンタは、限られた数のビット（“b”ビット）であり、従って、“b”ビットでタグを生成する。すなわち、最大カウンタ値及びタグの“t”は2b-1である。
【００７８】
キャッシュメモリ・スライスk702Aがj.2b-2のタグを備えたCSA更新を受信したが、j.0〜j.2b-3のタグ値を備えたものを含むその他のCSA更新を受信していないことを仮定する。更に、キャッシュメモリ・スライスk702Aがその順序保存要求の全てを処理し、j.2b-1のタグ値でCSA更新を送出することを仮定する。j.2b-1のタグ更新を備えたCSA更新の発行は、他のキャッシュメモリ・スライス（キャッシュメモリ・スライスm702B等）がその他のCSA更新を待機せずにj.2b-1を有するタグ付き順序保存要求を処理することを起動してもよい。その後、キャッシュメモリ・スライスm702Bは、タグj.0がj.2b-1の次のカウンタ値であるため、j.0の更新タグを備えたCSA更新メッセージを発行してもよい。
【００７９】
図９Ｂを参照すると、キャッシュメモリ・スライスの制御ロジックにより実行される制御機能のフローチャートが、タグ更新の処理について図示されている。
【００８０】
950において、各キャッシュメモリ・スライスの制御ロジックにより実行されるCSA更新ルーチンは、電源投入時又はリセット時に初期化される。
【００８１】
952において、制御ロジックは、キャッシュメモリ・スライスがタグ更新j.tを備えたCSA更新メッセージを受信しているか否かを決定する。そうでない場合、制御ロジックは952にループバックし、基本的にタグ更新の受信を待機する。タグ更新j.tを備えたCSA更新メッセージが受信されると、制御ロジックは972に進む。
【００８２】
972において、制御ロジックは、CSA[j]をtに等しく設定することにより、キャッシュ・シーケンス・アレイ・テーブルへの現行のエントリを更新する。次に974において、制御ロジックは、“j.t”のタグを備えた何らかの保留の順序保存要求をキャッシュメモリ・スライスに処理させる。順序保存要求を処理した後に、980において、制御ロジックは952に戻り、次の更新を受信する。
【００８３】
特定の実施例について説明し、添付図面に図示したが、このような実施例は広い説明の単なる例示であり、限定ではないことがわかる。また、様々な他の変更が当業者に思いつくため、本発明は図示及び記載の特定の構成及び配置に限定されないことがわかる。例えば、本発明又はその特徴の一部をハードウェア、ファームウェア、ソフトウェア又はその組み合わせで実施することが可能である。その場合、ソフトウェアはプロセッサ読取可能記憶媒体（磁気、光又は半導体記憶装置等）に提供される。
【図面の簡単な説明】
【００８４】
【図１】本発明が使用され得る一般的なコンピュータシステムのブロック図
【図２Ａ】本発明が使用され得る中央処理装置のブロック図
【図２Ｂ】本発明が使用され得るマルチプロセッサ中央処理装置のブロック図
【図３Ａ】本発明が使用され得るマルチプロセッサシステムの実施例のブロック図
【図３Ｂ】本発明が使用され得るマルチプロセッサシステムの他の実施例のブロック図
【図３Ｃ】本発明が使用され得るマルチプロセッサシステムの他の実施例のブロック図
【図４】論理共有・物理分散キャッシュメモリシステムのブロック図
【図５Ａ】タグ付き順序保存要求の一般的なフィールドの図
【図５Ｂ】CSA更新の一般的なフィールドの図
【図６Ａ】キャッシュメモリ・スライスのブロック図
【図６Ｂ】キャッシュ・シーケンス・アレイ（CSA：cache  sequence  array）のブロック図
【図７】順序保存要求の順番の実行の例示的なシーケンスのブロック図
【図８】タグ付き順序保存要求をサポートするために要求側の制御ロジックにより実行される制御機能のフローチャート
【図９Ａ】順序保存要求が処理可能か否かについて各キャッシュメモリ・スライスの制御ロジックにより実行される制御機能のフローチャート
【図９Ｂ】タグ更新を処理する各キャッシュメモリ・スライスの制御ロジックにより実行される制御機能のフローチャート
【図１】
2007509439.tif 000003
【図２Ａ】
2007509439.tif 000004
【図２Ｂ】
2007509439.tif 000005
【図３Ａ】
2007509439.tif 000006
【図３Ｂ】
2007509439.tif 000007
【図３Ｃ】
2007509439.tif 000008
【図４】
2007509439.tif 000009
【図５Ａ】
2007509439.tif 000010
【図５Ｂ】
2007509439.tif 000011
【図６Ａ】
2007509439.tif 000012
【図６Ｂ】
2007509439.tif 000013
【図７】
2007509439.tif 000014
【図８】
2007509439.tif 000015
【図９Ａ】
2007509439.tif 000016
【図９Ｂ】
2007509439.tif 000017
【国際調査報告】
2007509439.tif 000018
2007509439.tif 000019
2007509439.tif 000020
2007509439.tif 000021
2007509439.tif 000022