(57)【要約】      （修正有）【課題】修正、排他的、共有、無効、及びフォワード（MESIF）の5つの状態を有するキャッシュ・コヒーレント・プロトコルを提供する。【解決手段】MESIFキャッシュ・コヒーレント・プロトコルは、更なる複製を行い得る、データの単一複製を指定するフォワード（F）状態を含む。F状態におけるキャッシュ・ラインは、キャッシュ・ラインの複製の要求に応答するのに用いられる。一実施例では、新たに作成される複製がF状態に置かれ、先行してF状態にあったキャッシュ・ラインは共有（S）状態又は無効（I）状態に置かれる。よって、キャッシュ・ラインが共有されている場合、1つの共有複製はF状態にあり、キャッシュ・ラインの残りの複製はS状態にある。【選択図】図４
2013058225.tif 000002
【特許請求の範囲】
【請求項１】
システムにおける何れの他のノードとも各ノードが直接に通信することができる完全に接続されたポイント・ツー・ポイント・システムにおいて、
複数のキャッシュ・メモリを有するシステムにおける1つ又は複数のキャッシュ・メモリにデータ・ブロックの複製を記憶させる工程であって、関連付けられたプロセッサを各キャッシュ・メモリが有し、前記データ・ブロックの前記複製のうちの１つの複製がフォワード状態において記憶され、前記データ・ブロックの前記複製のうちのその他の複製が共有状態において記憶される工程；
前記フォワード状態において記憶された前記データ・ブロックの前記複製を、該データ・ブロックの複製の要求に応答するのに用いる対象として指定する工程；
該データ・ブロックの該要求に、該データ・ブロックの該指定複製を記憶している該キャッシュ・メモリに該データ・ブロックの複製を提供することによって応答する工程；
前記複製が提供される前記キャッシュ・メモリによって記憶された前記データ・ブロックの前記複製を前記共有状態に変更させる工程：及び
要求側のキャッシュ・メモリに、前記データ・ブロックの受信された複製を前記フォワード状態において記憶させる工程を備え、該データ・ブロックが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、該データ・ブロックの要求に、該データ・ブロックの該指定複製を記憶している該キャッシュ・メモリに該データ・ブロックの複製を提供することによって応答する工程が：
該データ・ブロックの要求を受信する工程；
該データ・ブロックの複製が局所キャッシュ・メモリに記憶されているか否かを判定する工程；
該データ・ブロックの複製が該局所キャッシュ・メモリに記憶されている場合、該記憶データ・ブロックが該データ・ブロックの該指定複製であるか否かを判定する工程；及び
該データ・ブロックの複製を要求側キャッシュ・メモリに、該記憶データ・ブロックが該データ・ブロックの該指定複製である場合に送信する工程；
を備えることを特徴とする方法。
【請求項３】
システムにおける何れの他のノードとも各ノードが直接に通信することができる完全に接続されたポイント・ツー・ポイント・システムにおいて、
データ・セグメントの複製の要求を要求側ノードからマルチノード・システムの1つ又は複数のノードに送信する工程；
を備え；
該要求を受信する該1つ又は複数のノードのうちの１つは該データ・セグメントを非キャッシュ・メモリに記憶させるホーム・ノードであり；
該ホーム・ノードでないノードは、該要求側ノードに対するピア・ノードであり；
該ピア・ノードは、該ピア・ノードの各々に関連したキャッシュ・メモリにおいて、複製を、該複製がある場合に記憶させ；
更に、前記ピア・ノードの何れも該データ・セグメントの共有可能な複製を記憶していない場合に、該ホーム・ノードから該データ・セグメントの複製を提供する工程；及び
フォワード状態において該データ・セグメントの複製を記憶する該ピア・ノードから該データ・セグメントの複製を提供する工程；
を備え；
複数のピア・ノードによって記憶される該データ・セグメントの複数の複製のうちの１つのみが該フォワード状態において指定され、前記データ・セグメントの前記複製のうちのその他の複製が共有状態において記憶され、
更に、受信側ノードにより、前記データ・セグメントの前記提供された複製を前記フォワード状態において記憶させる工程：及び
提供側ノードによって記憶された前記データ・セグメントの前記複製を前記共有状態において記憶させる工程を備えることを特徴とする方法。
【請求項４】
請求項3記載の方法であって、更に：
該データ・セグメントの複製を記憶している唯一のピア・ノードが指定ピア・ノードである場合に、該データ・セグメントの複製を有する該指定ピア・ノードから該データ・セグメントの複製を提供することを特徴とする方法。
【請求項５】
請求項3記載の方法であって、更に：
該要求側ノードに提供される、該データ・セグメントの該複製を該フォワード状態にあるものとして指定する工程；及び
該要求側ノードからの該データ・セグメントの該要求に応じて該データ・セグメントの該複製を提供した該ピア・ノードにおける該データ・セグメントの該複製を、該フォワード状態から共有状態に変更する工程；
を備えることを特徴とする方法。
【請求項６】
請求項3記載の方法であって、該データ・セグメントの複製の要求を該要求側ノードから該マルチノード・システムの1つ又は複数のノードに送信する工程が：
該要求を該マルチノード・システムの非要求ノード全てにブロードキャストする工程；
を備えることを特徴とする方法。
【請求項７】
請求項5記載の方法であって、該データ・セグメントの複製の要求を該要求側ノードから該マルチノード・システムの1つ又は複数のノードに送信する工程が：
該要求を該マルチノード・システムの非要求ノード全ての部分集合に送信する工程；
を備えることを特徴とする方法。
【請求項８】
請求項3記載の方法であって、該データ・セグメントが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項９】
請求項3記載の方法であって、該データ・セグメントが：
キャッシュ・ラインよりも小さなデータ・ブロック；
を備えることを特徴とする方法。
【請求項１０】
請求項3記載の方法であって、該データ・セグメントが：
キャッシュ・ラインよりも大きなデータ・ブロック；
を備えることを特徴とする方法。
【請求項１１】
システムであって：
メモリ・システムと結合されて、データ・セグメントの元の複製を記憶するホーム・ノード；及び
複数のピア・ノードそれぞれと、前記ホーム・ノードとの間のポイント・ツー・ポイント・システムを介して前記ホーム・ノードと結合される複数のピア・ノード；
を備え；
該複数のピア・ノードは、一複製がフォワード状態において記憶され、残りの複製が共有状態において記憶される、前記データ・セグメントの複数の複製を記憶するためのキャッシュ・メモリを有し；
該データ・セグメントの複製を要求する要求側のピア・ノードによる、ポイント・ツー・ポイント・リンクそれぞれを介して他のピア・ノード全て及び前記ホーム・ノードに送信される要求に応じて：
非要求ピア・ノードがフォワード状態において該データ・セグメントの複製を有する場合に、該非要求ピア・ノードが該データ・セグメントの複製を提供し；
非要求ピア・ノードの何れも該フォワード状態において該データ・セグメントの複製を有しない場合に、該ホーム・ノードが該データ・セグメントの複製を提供し；
更に、該データ・セグメントの1つ又は複数のキャッシュ複製のうちの1つのみが、該要求に先行して該フォワード状態にあり、提供側ノードは次いで、前記データ・セグメントの前記複製を前記共有状態において記憶し、受信側ノードに、前記データ・セグメントの前記受信された複製を前記フォワード状態において記憶させることを特徴とするシステム。
【請求項１２】
請求項11記載のシステムであって、該データ・セグメントが：
キャッシュ・ライン；
を備えることを特徴とするシステム。
【請求項１３】
請求項11記載のシステムであって、該データ・セグメントが：
キャッシュ・ラインよりも小さなデータ・ブロック；
を備えることを特徴とするシステム。
【請求項１４】
請求項11記載のシステムであって、該データ・セグメントが：
キャッシュ・ラインよりも大きなデータ・ブロック；
を備えることを特徴とするシステム。
【請求項１５】
請求項11記載のシステムであって、該要求側のピア・ノードが：
該データ・セグメントの該要求を、該ホーム・ノードと、該非要求ピア・ノードの各々とにブロードキャストすることを特徴とするシステム。
【請求項１６】
請求項11記載のシステムであって、該要求側のピア・ノードが：
該データ・セグメントの該要求を、該ホーム・ノードと、該非要求ピア・ノードの各々との部分集合にブロードキャストすることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、キャッシュ・メモリに関し、特に、マルチプロセッサ・システムにおけるキャッシュ・コヒーレンス・プロトコルにおいて用いるフォワード（F）状態に関する。
【背景技術】
【０００２】
大半のキャッシュ・コヒーレント・プロトコルは、データを何れかの数のシステム構成部分（例えば、プロセッサ）間で共有し得る共有状態を有する。共有（S）状態は、システム構成部分がデータの読み取りのみの複製を要求し、データが別のシステム構成部分において排他的（E）状態に既にあった場合に生じる。要求するシステム構成部分と、データの複製を有していたシステム構成部分は各々、データを共有状態においてマーキングする。データが共有状態にある場合、そのデータは、データの読み取りのみの複製を要求するシステム構成部分によって自由に複製することが可能である。
【０００３】
バス・ベースのマルチプロセッサ・システムでは、キャッシュ・コヒーレント・プロトコルは通常、システム構成部分が共有データを要求側システム構成部分に備えることを可能にしない。その代わりに、データはメモリ・システムから直接取り出される。ディレクトリ・ベースのキャッシュ・コヒーレント・プロトコルでは、メモリ・システムは共有の複製を要求側システム構成部分に備えるものでもある。キャッシュ・ライン状態（更には、したがって、データ状態）のディレクトリは、システム構成部分とメモリとの間にあり、よってデータはメモリから取り出され、要求するシステム構成部分に送出される。
【０００４】
共有状態は、システム構成部分間でポイント・ツー・ポイント相互接続ネットワークを用いるマルチプロセッサ・システムにおいて数多くの課題を、特にキャッシュ・ライン状態を追跡するうえでディレクトリに依存しない場合に、もたらし得る。そのようなシステムにおける課題を制限するよう、システム構成部分からの要求が直接、メモリ・システムにルーティングされ、更にメモリ・システムが要求をブロードキャストしてデータ（キャッシュ・ライン）状態を判定し、別のシステム構成部分から応答を収集し、要求が満たされた場合にデータがどの状態にあるものであるかを判定する役目を担うということを先行技術は暗示している。これらのプロトコルは、データを戻すのに：１）要求側からメモリまで；2)別のシステム構成部分へのメモリ・ブロードキャスト要求；３）メモリ・システムに対するシステム構成部分の応答；及び４）メモリ・システムによる、要求側に対するデータの転送；の４つのホップをもたらす。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
完全に接続されるポイント・ツー・ポイント・システムにおいて要求を満たすことに関するレーテンシを低下させるよう、要求システム構成部分はその要求を、全ての別のシステム構成部分、更にはメモリ・システムにブロードキャストすることが可能である。別のシステム構成部分は、共有状態においてデータを有する場合、データを要求側に直接供給することが可能である。複数のシステム構成部分が同時に同じデータを要求し、複数の別のシステム構成部分はデータを共有状態において有する場合に問題が生じる。要求側システム構成部分は潜在的には複数のデータ返答を処理しなければならない。1つ又は複数のシステム構成部分が共有データを修正する権利を要求する場合に更に多くの課題が生じる。
【０００６】
システム構成部分の１つがデータを修正したい場合、その構成部分は、要求データを修正するうえでの、システムの残りからの許可を依頼する「request-for-ownership」（RFO）を出さなければならない。RFOが付与された後、データの状態は共有状態から、データが修正されたという旨を示す別の（例えば、修正）状態に変更される。
【０００７】
図示すれば、図1a及び図1bは、先行技術のキャッシュ・コヒーレント・プロトコルを有する４ノード・システムの概念図である。図1bの例では、破線は先行して送出されたメッセージを表し、実線は説明しているメッセージを表す。このシステムでは、修正（M）、排他的（E）、共有（S）、及び無効（I）の４つの伝統的なキャッシュ・ライン状態のみが用いられる。これは、MESIキャッシュ・コヒーレント・プロトコルとして知られている。ノード110、120及び130は、キャッシュ・メモリに要求データ（例えば、キャッシュ・ライン）の複製を記憶するピア・ノードである。ホーム・ノード140はメモリにデータの元の複製を記憶するか、データの修正バージョンを、修正がメモリにもう一度書き込まれる場合に記憶する。すなわち、ホーム・ノード140は、データの非キャッシュ複製の役目を担う。図1aの例では、ノード120及び130はいずれも要求データの複製をキャッシュ・メモリに記憶させ、データは共有（S）状態にある。
【０００８】
ピア・ノード110が、データを修正する権利を要求するRFOを出すと、ピア・ノード110はRFOをシステムの別のノードにブロードキャストする。図1bに示すように、ノード120及び130はいずれも、要求データの複製を備えることによって、ピア・ノード110からの要求に応答する。ノード120もノード130も要求データの複製を備えることができるので、ピア・ノード110は要求データの複数の複製を受信し、照合調整することができなければならない。このことは、ピア・ノード110の設計に複雑度を付加する。システムにおけるノード数が増加するにつれ、この要件によって更に複雑度が増加し、それによってシステム設計の費用と複雑度が増加する。
【０００９】
複数の要求ノードが各々、要求データの複製を、例えば、3つ以上のノードから受信する、より複雑な場合も存在し得る。よって、各ノードは、要求データの複数の競合複製を解決してシステム機能が適切なものになるようにすることができなければならない。
【課題を解決するための手段】
【００１０】
マルチノード・システムにおけるキャッシュ・コヒーレンスのためにフォワード（F）状態を用いることについて説明する。F状態は、読み取りのみの要求であってもRFO要求であっても、要求側システム構成部分で受信される複数データ複製を気にせずに現行所有システム構成部分から要求側システム構成部分に共有データを送信することを可能にする。
【００１１】
F状態は、MOESI（修正、所有者、排他的、共有、及び無効）として知られる先行技術のキャッシュ・コヒーレンス・プロトコルにおけるO状態とは、O状態にデータを有するシステム構成部分がシステムにおける唯一の更新データ値を有するという点で異なる。更に、それはメモリ・システムにおける複製と整合していない。このことは、所有データを取り戻すと、そのデータをもう一度送出してメモリ・システムに記憶させることをシステム構成部分に要求する。F状態は、データ値がメモリ・システムにおける複製と一致しているということを示す。システム構成部分がF状態におけるデータを取り戻す場合、構成部分は単に、メモリ・システムにデータをもう一度記憶させることなくデータを取り除くことが可能である。
【００１２】
下記明細書では、説明の目的で、数多くの特定の詳細を表して、本発明を徹底的が分かるようにしている。しかし、本発明はこれらの特定の詳細の一部なしで実施可能であるということは当業者に明らかとなる。別の場合には、構造及び装置を構成図形式で表して本発明を分かりにくくしないようにしている。
【００１３】
下記明細書では、5つの状態（修正、排他的、共有、無効、フォワード）を含むキャッシュ・コヒーレント・プロトコルを表し、このプロトコルはMESIFプロトコルとしても表す。別の実施例では、フォワード状態は、MESI状態以外に用いること及び/又はMESI状態に加えて用いることが可能である。すなわち、そのうちの１つがフォワード状態であるその５つの状態は必要でない。
【００１４】
キャッシュ・コヒーレント・プロトコルを備えるために、いくつかのキャッシュ・コヒーレント・プロトコル・メッセージ種類を説明する。予備事項として、キャッシュ・コヒーレントに用いるメッセージの要約を以下に備える。説明するメッセージの全てがF状態を有するコヒーレント・プロトコルを備えることを必要とする訳ではないが、メッセージ・グループを用いて、F状態を有するキャッシュ・コヒーレント・プロトコルを備えることが可能である。
【００１５】
要求メッセージ
以下のメッセージは、要求側ノード（システム構成部分）からのデータ/動作要求である。これらのメッセージは、システムのノード全てにブロードキャストされる。
【００１６】
ポート読み取りライン（PRL）：これは、例えばキャッシュ・ラインなどのデータ・セグメントの複製の要求である。
【００１７】
ポート読み取り無効化ライン（PRIL）：これは、データの、提供側のノードの複製が無効化されるデータ・セグメントの複製の要求である。これは、「request-for-ownership」（RFO）の種類のメッセージである。
【００１８】
ポート書き込みライン（PWL）：このメッセージは、データ（例えば、修正キャッシュ・ライン）をメモリに書き込ませる。このメッセージは、「dirty  eviction」としても表し得る。
【００１９】
応答メッセージ
以下のメッセージは、ピア（すなわち、非ホーム）・ノードから要求側ノードに上記要求に応じて送出されるメッセージである。ホーム・ノードは、要求キャッシュ・ラインに相当するメモリ・システムを含むノードである。
【００２０】
無効状態応答（IACK）：このメッセージは、応答を送出するノードが、要求データの無効複製を有するか、要求データの複製を何ら有していない場合の要求（PRL、PRIL、PWL）への応答である。
【００２１】
共有状態応答（SACK）：このメッセージは、応答を送出するノードが共有状態における要求データの複製を有し、この複製を確保する場合の要求への応答である。
【００２２】
データ受信の応答（DACK）：このメッセージは、要求データの受信を応答する。
【００２３】
競合：このメッセージは、要求キャッシュ・ラインに対して同時に待ち状態にある要求が存在しているということを示す。
【００２４】
ホーム・ノードへのメッセージ
このメッセージはホーム・ノードにピア・ノードによって送信される。
【００２５】
読み取り（競合）：このメッセージは、ホーム・ノードからデータを要求し、競合がある場合には競合を全て示す。
【００２６】
CNCL（競合）：このメッセージは、ピア・ノードにおけるヒットに応じてホーム・ノードに送出され、競合がある場合には競合を全て示す。このメッセージはホーム・ノードのプリフェッチ動作を取り消す。
【００２７】
ホーム・ノードからのメッセージ
このメッセージはホーム・ノードからピア・ノード及び/又は要求側ノードに送出される：
データ：このメッセージは要求データを含み、要求側ノードによって用いられる対象のデータの状態（M/E/F/S）を示し得る。
【００２８】
応答（ACK）：このメッセージは、要求データが要求側ノードに送出されたということを示す。
【００２９】
ウェイト：このメッセージは、受信ノードに、更にメッセージを送出する前に着信データを待つようにさせる。
【００３０】
転送（XFR）：このメッセージは、受信ノードに、メッセージに示すノードにデータを転送させる。
【００３１】
MESIFキャッシュ・コヒーレント・プロトコルの概要
本明細書及び特許請求の範囲には、修正、排他的、共有、無効及びフォワード（MESIF）の５つの状態を有するキャッシュ・コヒーレント・プロトコルを記載する。MESIFキャッシュ・コヒーレント・プロトコルは、更に複製を行うことが可能な、データの単一の複製を指定するフォワード（F）状態を含む。F状態におけるキャッシュ・ラインは、キャッシュ・ラインの複製の要求へ応答するのに用いられる。一実施例では、新たに作成される複製はF状態に置かれ、別のシステム構成部分（非ホーム・ノード）において先行してF状態にあったキャッシュ・ラインは共有（S）状態又は無効（I）状態に置かれる。よって、キャッシュ・ラインが共有される場合、1つのシステム構成部分における１つの共有の複製はF状態にあり、別のシステム構成部分におけるキャッシュ・ラインの残りの複製はS状態にある。
【００３２】
本明細書及び特許請求の範囲記載のMESIFプロトコルは新しいものであるが、これは、本質的には、単一の直列化バスの制約なしのスヌーピング・プロトコルであるからである。スヌーピング・キャッシュ・プロトコルのように、MESIFはデータのキャッシュ複製を備えているノードに依存してコヒーレント状態を維持する。同期・集中ブロードキャストではなくポイント・ツー・ポイント・リンクを用いることは、タイム・ワープ、すなわち別のノードから視るとイベントが別の順序で生じているように見えるということ、の課題をもたらす。MESIFプロトコルは、潜在的なエラーが発生する可能性がある時点を認識し、そのエラーが正しく処理されるということを確かめて、ターム・ワープを正しく処理する。ホーム・ノードの考え方は主に、非キャッシュ複製が存在している場所を判定するものであるが、ホーム・ノードは、競合とタイム・ワープの課題を解決するために、全てのトランザクションにおいて、すなわちクリティカル・パス上にない場合でも、参加することが可能である。この手法の同時ブロードキャスト特性のために、MESIFは、データのキャッシュ可能な複製を大半の場合に、考えられる最小のレーテンシ、すなわち単一の、要求と応答との往復において取得して、スヌーピング・プロトコルに関連した低レーテンシを達成する。
【００３３】
タイム・ワープの課題を無視すれば、システムにおいて一意のキャッシュ複製が存在する場合に2ホップのアクセスを達成することが可能である。F状態を導入することによって、この可能性を、複数の複製が存在する通常の場合に拡張させる。本質的には、F状態は、複数のノードが応答することが可能である場合にどのノードが応答することとするかを判定する「five-among-equals」を確立する。
【００３４】
MESIFプロトコルでは、ピア・ノード全てとホーム・ノードとに初期要求をブロードキャストする。複製は、状態E、状態F、又は状態Mにキャッシュされる場合、応答に含まれる。要求が満たされた旨をホーム・ノードに通知する第２メッセージが更にホーム・ノードに送出される。要求ラインがキャッシュされていない場合又はS状態の複製しか存在しない場合には、ホーム・ノードに送出される第２要求が、ホーム・ノードがこの時点では既にそのメモリからフェッチした場合がある先行要求を確認するのに用いられる。いずれの場合でも、ホーム・ノードは、同期化の目的と競合解決の目的で第２要求に応答しなければならない（。ホーム・ノードは、更に、同様に第１要求に応答しなければならないが、これらは場合によっては組み合わせることが可能である。）なお、ホーム・ノードは、1つ又は複数のキャッシュを有し得るので、何れかの別のノードと同様に初期の要求に応答し得る。
【００３５】
全ての応答を待つのではなくデータが到着するとすぐにデータをノードが用いることを可能にすることによって問題が生じる。よって、データの複製を受信するノードは、受信するとすぐに内部でデータを用いることが可能であるが、データを用いる効果が、ノードがホームから確認を受信するまでシステムの残りに対して視える状態にされない場合がある。確認は、ノードがそのコピーを別のノードに転送しなければならないという旨の命令と、ノードをそれ自体のキャッシュから場合によっては取り戻す命令を含む場合もある。
【００３６】
ノードが、キャッシュ・データを供給することによって、別のノードからの要求に応答する場合、データを転送したということに応答する、ホーム・ノードからの応答を受信するまで、同じキャッシュ・ラインに受信する全ての別の要求を据え置き、それによって、全てのノードが（場合によっては書き込み可能な）キャッシュ・ラインの転送の同じ順序に従うようにする。
【００３７】
ホーム・ノードは、非キャッシュ・データのリポジトリであるが、要求を生成するプロセッサを有し、1つ又は複数のキャッシュを含む場合もある。何れかの別のノードのように、ホーム・ノード・プロセッサが失敗する場合、ホーム・ノードは、要求を全ての別の（ピア）ノードにブロードキャストしなければならず、ホーム・ノードに到着する何れかの別の要求を処理することになるように、要求を内部で処理しなければならない。なお、これは、ホーム・ノードがメッセージをそれ自体（ホーム・ノード）に明示的に送出しないという点で特別な場合である。更に、局所でキャッシュされているデータの外部要求が到着する場合、ホーム・ノードは、ホーム・ノードからの後の応答があいまいでないようにする方法で応答しなければならない。すなわち、ホーム・ノードは、データを供給することによって初期の要求に応答する場合があるが、ホーム・ノードは第２要求にホーム・ノードとして応答しなければならないということもある。
【００３８】
プロトコルの変形は、ホーム・ノードがデータの非キャッシュ複製によって、このデータは有効であるか否かが分かっていない状態で応答することを可能にし、データが非適切に供給された場合を解決することは、要求側ノードと、ホーム・ノードからの第２応答に任せられる。
【図面の簡単な説明】
【００３９】
【図１ａ】先行技術のキャッシュ・コヒーレンス・プロトコルを有する4ノード・システムの概念図である。
【図１ｂ】先行技術のキャッシュ・コヒーレンス・プロトコルを有する4ノード・システムの別の概念図である。
【図２ａ】データをそのホーム・ノードから要求側ノードまでフォワード状態を用いて転送する概念の図である。
【図２ｂ】データをそのホーム・ノードから要求側ノードまでフォワード状態を用いて転送する概念の別の図である。
【図３ａ】データをピア・ノード間でフォワード状態を用いて転送する概念の図である。
【図３ｂ】データをピア・ノード間でフォワード状態を用いて転送する概念の別の図である。
【図３ｃ】データをピア・ノード間でフォワード状態を用いて転送する概念の更に別の図である。
【図４】データの複製を、フォワード状態を用いて備える手法の一実施例に相当する流れ図である。
【図５】ノードの一実施例の構成図である。
【図６】マルチプロセッサ・システムの一実施例の図である。
【発明を実施するための形態】
【００４０】
本発明は制約ではなく例として、添付図面の図において図示し、同様な参照数字は同様な構成要素を表す。
【実施例】
【００４１】
フォワード状態の概要
一実施例では、要求が非同期でブロードキャストされるシステムにおいてフォワード状態を用いており、応答がシステムにおけるノード全てによってみられるということが可能でなく、データをF状態において記憶させたノードは、有効複製がメモリに（例えば、ホーム・ノードによって）記憶されるので、一意の複製を有することが可能でないということを表す。よって、O状態におけるデータがデータの唯一の有効複製である、MOESIプロトコルの所有状態とは違って、F状態におけるデータは、取り去られるか、所望される場合S状態に変換されることが可能である。
【００４２】
F状態は、要求データの有効複製がメモリにおいて存在するという意味合いにおいて「first  among  equals」の考え方として表すことが可能である。先行技術のプロトコル（例えば、MOESI及びSCI）はこの場合を備えるものでない。MOESIプロトコルは、有効な複製がメモリにおいて維持されていないので、所有複製を維持する。所有コピーは、メモリにおける複製を更新することによってのみ除去し得る。SCIプロトコルは、要求が処理対象のディレクトリ・ノードに送出されるので、ブロードキャスト・プロトコルではない。
【００４３】
図２a及び図2bは、データをそのホーム・ノードから２つのピア・ノードの各々にフォワード状態を用いて転送する概念の図である。図2aと図2b更には図3a乃至図3bの例では、破線は先行して送出されたメッセージを表し、実線は説明しているメッセージを表す。図を明瞭な状態に保つために、メッセージ群（例えば、PRILと、相当するIACK）が解決される場合、メッセージを表す線は図面にもう含まれない。
【００４４】
以下の記載は、マルチノード・システム内部のノードによって備えられる。一実施例では、非ホーム・ノードは、内部キャッシュ・メモリ及び/又は外部キャッシュ・メモリを有するプロセッサを含む。別の実施例では、非ホーム・ノードは別の電子システムと相互接続される電子システム（例えば、コンピュータ・システム、移動体機器）である。更に別の実施例では、全てのノードは、内部キャッシュ・メモリと、それに接続されているメモリ・システムとを有するプロセッサであり得る。上記の最後の実施例では、ノードは、要求データがノードのメモリ・システムをホームとする場合に要求に対するホーム・ノードとしての役割を果たし得る。
【００４５】
図2aは、要求データ群（例えば、キャッシュ・ライン）がホーム・ノード240のみに記憶されているマルチノード・システムである。この状況は、例えば、データ群が初めてアクセスされる時点で起こり得る。データは、ホーム・ノード240に関連したメモリに記憶され、ノード210、220及び230のうちの何れかに関連したキャッシュ・メモリに記憶されない。ピア・ノード230は、PRLメッセージをシステムのノード全てにブロードキャストすることによってデータ・ブロックを要求する。ピア・ノード230は、別の種類のメッセージ、例えばPRILメッセージを用いてデータ・ブロックを要求し得る。
【００４６】
図2bは、ピア・ノード230によるデータの要求に応じた図2aのマルチノード・システムを示す。ノード210及び220は、ノード210とノード220とのキャッシュ・メモリが要求データの有効な複製を含んでいない旨を示すIACKメッセージをピア・ノード230に送出する。ホーム・ノード240は要求データをピア・ノード230にDataEメッセージにおいて送出する。DataEメッセージは、要求データをピア・ノード230にE状態において記憶させることとする旨をピア・ノード230に示す。
【００４７】
別のピア・ノード、例えばピア・ノード220が同じキャッシュ・ラインに後続要求を行う場合、ピア・ノード230は、（ホーム・ノード240が備えるようなDataEメッセージではなく）DataEメッセージによってピア・ノード220からのPRL要求に応答することによってキャッシュ・ラインをピア・ノード220に直接備える。ピア・ノード230はキャッシュ・ラインのその複製を共有状態（S）に移行させる。更に、ピア・ノード220は、ピア・ノード230からのDataFメッセージとともにピア・ノード210からの応答を受信すると、CNCL()メッセージをホーム・ノード240に送出する。ホーム・ノード240は更に、ACKメッセージをピア・ノード220に送出し、それによって、ピア・ノード220がキャッシュ・ラインをF状態に保つことを可能にする。ピア・ノード220は更に、DataFによって同じキャッシュ・ラインへの後続要求に応答することが可能である。
【００４８】
一実施例では、F状態におけるデータの複製は、追加の複製を後続要求ノードに備えるのに用いる複製である。よって、F状態におけるデータは、将来の、データの複製の要求に応じるのに用いられる。データの、新たに作成されるデータはF状態に置かれ、F状態に先行してあったデータの複製はS状態に置かれる。すなわち、データが共有される場合、1つの共有複製はF状態にあり、データの残りの複製がある場合には、それらはS状態にある。あるいは、要求データの複製のソースは、F状態に維持され、新たなコピーはS状態において記憶される。
【００４９】
F状態におけるデータの単一複製は、少なくとも２つの効果を備える。まず、キャッシュ間応答は通常、メモリとキャッシュとの間の応答よりも高速である。よって、複製を要求側ノードに備えるのに用いられる、データの単一の、指定キャッシュ複製を有することは、マルチノード・システムの全体性能を増加させ得る。
【００５０】
第２に、F状態は、S状態から修正（M）状態へのデータの移行を単純化する。F状態にはデータの1つの複製しか存在しないので、このことは、競合要求を解決する単一点を可能にし、この移行を全ての別の複製を無効にすることに変える。冗長な複製を備えるよう、F状態における複製を用いることによって、この期間中に複製が激増することを禁止することがより単純になる。
【００５１】
図3a乃至図3cは、フォワード状態を用いてピア・ノード間でデータを転送する概念を示す。図3aは、先行して要求され、（例えば、図2a及び2bに示す）ピア・ノード230にF状態において現在記憶されているピア・ノード210を示す。データを要求するよう、ピア・ノード210はPRLメッセージをシステムの別のノードにブロードキャストする（ピア・ノード210はPRLメッセージをノードの部分集合に送信することも可能である。）。ピア・ノード220は、要求データの有効な複製を有していないという旨を示すIACKメッセージによって応答する。ピア・ノード230は、DataFメッセージによって応答し、ピア・ノード210にデータの複製を備え、データをF状態に記憶させることとする旨をピア・ノード210に示す。別の実施例では、ピア・ノード230によって記憶される要求データの複製はS状態に置かれる。
【００５２】
図3bは、ピア・ノード230からの要求データの複製の受信に応じたピア・ノード210からのメッセージを示す。ピア・ノード210は、ピア・ノード220及び230からの応答全てを受信すると、ピア・ノード210からのPRLメッセージに応じて開始される動作のフェッチをホーム・ノード240が停止させ、PRLメッセージに関して存在する既知の競合は何らないということを示すCNCL()メッセージをホーム・ノード240に送出する。ホーム・ノード240は更にACKメッセージをノード210に送出する。
【００５３】
図3cは、ピア・ノード230からピア・ノード220までのデータの転送を終了する、ホーム・ノード240からの最終メッセージを示す。一実施例では、ピア・ノード210は、ACKメッセージを受信すると、ピア・ノード210が要求データをピア・ノード230から受信した旨を示すDACKメッセージをピア・ノード230に送出する。別の実施例では、ノード230に対してDACKメッセージをピア・ノード210に送出させるのではなく、ホーム・ノード240がDACKメッセージをピア・ノード230に送出することが可能である。別の実施例では、ピア・ノード210からのCNCL()メッセージは、ピア・ノード230からデータをピア・ノード210が受信した旨を示す情報を含むので、ホーム・ノード240は、どのピア・ノードがDACKメッセージを受信することになるかを追跡することが可能である。
【００５４】
図2a及び図2bと、図3a乃至図3cとの例は４ノード・システムに関して表しているが、本明細書及び特許請求の範囲記載の手法は何れかのサイズのマルチノード・システムに適用可能である。図2a及び図2bと、図3a乃至図3cとのノードは、データを記憶し、データの複製を要求することが可能な何れかの種類の構成部分を表すことが意図されている。例えば、ノードは、マルチプロセッサ・コンピュータ・システムにおけるキャッシュ・メモリであってよく、ネットワークにおけるコンピュータ・システムであってよく、より高度なシステム内部の1つ又は複数の、プロセッサ及び/又はキャッシュ・メモリの群であってよい。
【００５５】
処理フローの一実施例
図4は、フォワード状態を用いてデータの複製を備える手法の一実施例に相当する流れ図である。一実施例では、ノードがデータを要求する場合、要求側ノードはデータ（例えば、PRILメッセージ）の要求をシステムの別のノード全てにブロードキャストする(410)。別の実施例では、要求は、システム内部のノードの部分集合に送信されてもよく、ネットワーク接続を介して別のノードに送信されてもよい。
【００５６】
応答メッセージはシステムにおける別のノードから受信される（415）。上記のように、応答メッセージはいくつかの形式を呈し得る。要求側ノードは、要求データの有効な複製を有しない、システムにおけるノードから1つ又は複数のｘACK（例えば、IACK、SACK）メッセージを受信する。要求側ノードは、F状態における要求データの複製を有するDATAx（例えば、DataF、DataM）メッセージをホーム・ノードとピア・ノードとの何れかから受信することにもなる。
【００５７】
全ての応答が受信されると(420)、要求側ノードは、READメッセージ又はCANCELメッセージを、識別競合のリストとともにホーム・ノードに送出する(425)。ACKメッセージがホーム・ノードから受信される場合(430)、データは、DATAメッセージによって示される状態において記憶される。ACKメッセージではなくXFERメッセージがホーム・ノードから受信される場合、要求ノードはホーム・ノードからのXFERメッセージを処理する。
【００５８】
XFERメッセージに応じて、要求ノードはDATAメッセージを、XFERメッセージによって示されるノードに送出する(445)。データを無効化することとする旨をXFERメッセージが示す場合(450)、要求側ノードは確保されているデータの複製を無効化する(455)。XFERメッセージが要求ノードにデータの複製を無効化させるものでない場合(450)、要求側ノードはデータをS状態において記憶させる(460)。
【００５９】
ノードの例示的実施例
図5は、ノードの一実施例の構成図である。ノード500は、単一プロセッサ、キャッシュ・メモリ、メモリ・コントローラ及びメモリとともに示す。しかし、何れかの数の、構成部分のうちの何れかをノードに含むことが可能である。更に、別の構成部分及び/又は異なる構成部分（例えば、バス・ブリッジ）をノードに含めることも可能である。
【００６０】
プロセッサ510は、公知の何れかの種類のプロセッサであり得る。一実施例では、プロセッサ510はキャッシュ・メモリ520を含む。別の実施例では、プロセッサ510の外部にあるキャッシュ・メモリ520及び/又は、プロセッサ510の内部又は外部にある別のキャッシュ・メモリを含み得る。
【００６１】
メモリ・コントローラ530はキャッシュ・メモリ520及びメモリ540と結合される。メモリ・コントローラ530は、プロセッサ510、キャッシュ・メモリ520及びメモリ540の間のインタフェースとして動作する。一実施例では、メモリ・コントローラ530は、本明細書及び特許請求の範囲記載のキャッシュ・コヒーレント・プロトコルによってキャッシュ・コヒーレント状態を維持する。メモリ・コントローラ530は別のノードとノード・リンク550を介して相互作用する。別の実施例では、プロセッサ510はメモリ・コントローラ530と相互作用して本明細書及び特許請求の範囲記載のキャッシュ・コヒーレント状態を維持し、プロセッサ510は別のノードと別のノード・リンク555を介して相互作用する。
【００６２】
マルチプロセッサ・システムの例示的実施例
図6は、マルチプロセッサ・システムの一実施例である。マルチプロセッサ・システム600は、例えば、コンピュータ・システム、リアルタイム監視システムなどの、複数のプロセッサを有する種々のシステムを表すことが意図されている。別のマルチプロセッサ・システムの構成部分は、より多い構成部分、より少ない構成部分、及び/又は異なる構成部分を含み得る。特定の場合には、本明細書及び特許請求の範囲記載のキャッシュ管理手法は、単一プロセッサ・システムにもマルチプロセッサ・システムにも適用し得る。マルチプロセッサ・システム600は、マルチノード・システムとして動作するよう構成し得る。
【００６３】
マルチプロセッサ・システム600は、情報を伝達するよう、バス・システム610又は別の通信装置を含む。バス・システム610は、何れかの数の、バスと、関連した相互接続回路、例えばバス・ブリッジを含み得る。プロセッサ620はバス・システム610と結合されて情報を処理する。プロセッサ620は、キャッシュ・メモリ622、例えばレベル・ゼロ(L0)キャッシュ・メモリとキャッシュ・コントローラ624とを含み得る。一実施例では、プロセッサ620は、何れかの種類のキャッシュ・メモリであり得るキャッシュ625とも結合される。別の実施例では、キャッシュ625は、バス・システム610と結合し得る。別の種類のプロセッサ・キャッシュ構成を用い得るものでもある。
【００６４】
一実施例では、キャッシュ・コントローラ624は、例えば、プロセッサ620内部のバスであり得るキャッシュ・メモリ・インタフェース628を介してキャッシュ・メモリ622に結合される。キャッシュ・コントローラは、プロセッサ620と外部キャッシュ・メモリとの間のインタフェースを備えるキャッシュ・インタフェース626を介してキャッシュ・メモリ625と結合される。
【００６５】
マルチプロセッサ・システム600は更に、キャッシュ・メモリ632とキャッシュ・コントローラ634とを備えているプロセッサ630を含む。キャッシュ・コントローラ634は、キャッシュ・インタフェース638を介してキャッシュ・メモリ632と結合される。同様に、キャッシュ・コントローラ634はキャッシュ・インタフェース636を介してキャッシュ・メモリ635と結合される。一実施例では、キャッシュ・メモリ635はプロセッサ630と結合される。
【００６６】
マルチプロセッサ・システム600は２つのプロセッサによって示しているが、マルチプロセッサ・システム600は、何れかの数のプロセッサ及び/又はコプロセッサを含み得る。マルチプロセッサ・システム600は更に、バス・システム610と結合されるメモリ・システム640を含む。メモリ・システム640は、動的メモリ装置（例えば、ランダム・アクセス・メモリ）並びに静的メモリ装置（例えば、読み取り専用メモリ、CD-ROM、ディスク記憶機構、フラッシュ・メモリ）及び、適宜、関連したドライブを含み得る。メモリ・システム640のメモリ装置は、マルチプロセッサ・システム600のプロセッサによって実行される対象の情報及び命令を記憶するのに用いる。メモリ・システム640は、プロセッサによる命令の実行中に一時変数又は別の中間的な情報を記憶するのに用い得るものでもある。
【００６７】
命令は、磁気ディスク、読み取り専用メモリ（ROM）集積回路、CD-ROM、DVDなどの静的記憶装置又は動的記憶装置から有線又は無線などの遠隔接続を介してメモリ・システム640に備え得る。別の実施例では、配線回路を、ソフトウェア命令の代わりに用いるかソフトウェア命令と組み合わせて用いることが可能である。よって、命令シーケンスの実行は、ハードウェア回路とソフトウェア命令との何れかの特定の組み合わせに限定されるものでない。
【００６８】
マルチプロセッサ・システム600は更に、ローカル・エリア・ネットワーク及び/又はインターネットなどのネットワークにアクセスを備えるネットワーク・インタフェース650を含む。ネットワーク・インタフェース650は、遠隔の電子的にアクセス可能な媒体との間で命令を通信することを含み得る無線ネットワーク・インタフェース及び/又は有線ネットワーク・インタフェースを備え得る。電子的にアクセス可能な媒体は、電子機器（例えば、コンピュータ、携帯情報端末、セルラ電話機）によって判読可能な形式におけるコンテンツ（例えば、コンピュータ実行可能命令）を備える（すなわち、記憶及び/又は伝送する）何れかの機構を含む。
【００６９】
例えば、マシン・アクセス可能媒体は：読み取り専用メモリ（ROM）；ランダム・アクセス・メモリ（RAM）；磁気ディスク記憶媒体；光記憶媒体；フラッシュ・メモリ装置；伝搬信号（例えば、搬送波、赤外線信号、ディジタル信号）の電気形態、光形態、音響形態又は別の形態を含む。
【００７０】
マルチプロセッサ・システム600は、情報を表示するよう、陰極線管（ＣＲＴ）ディスプレイ又は液晶（ＬＣＤ）ディスプレイなどのディスプレイ装置660を含み得るものでもある。例えば英数字キーやその他のキーを有するキーボードを含む入力装置670は、通常、バス610に結合されて、プロセッサ620及び/又は630に情報及びコマンド選択を通信する。別の種類のユーザ入力装置は、プロセッサ620及び630に方向情報及びコマンド選択を通信し、ディスプレイ装置660上でカーソルの動きを制御する、マウス、トラックボール、又はカーソル方向キーなどのカーソル制御装置である。
【００７１】
結論
本明細書における「one  embodiment」又は「an  embodiment」への言及は、実施例に関して記載されている特定の特徴、構造又は特性が本発明の少なくとも１つの実施例に含まれているということを表す。本明細書の種々の箇所に「in  one  embodiment」の句が出てくることは、必ずしも全て同じ実施例を表すわけではない。
【００７２】
上記明細書では、本発明はその特定の実施例を参照しながら記載されている。しかし、その特定の実施例には種々の修正及び変更を、本発明の、より広い範囲に及ぶ趣旨及び範囲から逸脱することなく行い得るということは明らかとなる。よって、本明細書及び添付図面は制約ではなく例として解されることとする。F状態は、バス・ベースのマルチプロセッサ・システムにおいて用い得る。
【図１ａ】
2013058225.tif 000003
【図１ｂ】
2013058225.tif 000004
【図２ａ】
2013058225.tif 000005
【図２ｂ】
2013058225.tif 000006
【図３ａ】
2013058225.tif 000007
【図３ｂ】
2013058225.tif 000008
【図３ｃ】
2013058225.tif 000009
【図４】
2013058225.tif 000010
【図５】
2013058225.tif 000011
【図６】
2013058225.tif 000012