キャッシュの一貫性

コンピュータアーキテクチャにおいて、キャッシュコヒーレンスとは、複数のローカルキャッシュに保存されている共有リソースデータの均一性を指します。キャッシュコヒーレンスシステムでは、複数のクライアントが共有メモリリソースの同じ領域のキャッシュコピーを持っている場合、すべてのコピーは同じになります。キャッシュコヒーレンスがないと、あるクライアントがその領域に加えた変更が他のクライアントには反映されず、異なるクライアントが使用するデータが一致しないとエラーが発生する可能性があります。^[1]

キャッシュ一貫性プロトコルは、キャッシュ一貫性を維持するために使用されます。主な 2 つのタイプは、スヌーピングプロトコルとディレクトリ ベースプロトコルです。

キャッシュの一貫性は、各CPU が共有メモリ リソースの独自のローカル キャッシュを持つ可能性が あるマルチプロセッシングシステムで特に重要です。

各プロセッサに個別のキャッシュ メモリを備えた共有メモリマルチプロセッサ システムでは、共有データのコピーを多数持つことができます。1 つはメイン メモリに、もう 1 つはそれを要求した各プロセッサのローカル キャッシュにあります。データのコピーの 1 つが変更されると、他のコピーもその変更を反映する必要があります。キャッシュ コヒーレンスは、共有オペランド (データ) の値の変更がシステム全体にタイムリーに伝播することを保証する規律です。^[2]

キャッシュコヒーレンスの要件は以下のとおりです。^[3]

書き込み伝播

いずれかのキャッシュ内のデータに対する変更は、ピア キャッシュ内の他のコピー (そのキャッシュ ラインの) に伝播される必要があります。

トランザクションのシリアル化

単一のメモリ位置への読み取り/書き込みは、すべてのプロセッサで同じ順序で認識される必要があります。

理論的には、コヒーレンスはロード/ストアの粒度で実行できます。しかし、実際にはキャッシュブロックの粒度で実行されるのが一般的です。^[4]

コヒーレンスは、単一のアドレス位置への読み取りと書き込みの動作を定義します。^[3]

異なるキャッシュ メモリに同時に発生するデータの 1 つのタイプは、キャッシュ コヒーレンス、または一部のシステムではグローバル メモリと呼ばれます。

マルチプロセッサシステムでは、複数のプロセッサがメモリ位置Xのコピーをキャッシュしているとします。キャッシュコヒーレンスを実現するには、次の条件が必要です。^[5]

1. プロセッサ P が位置 X に対して読み取りを行った後、同じプロセッサ P が位置 X に対して書き込みを行った場合、P による書き込み命令と読み取り命令の間に別のプロセッサによる位置 X への書き込みが行われなければ、X は常に P によって書き込まれた値を返す必要があります。
2. プロセッサ P1 による位置 X への読み取りの後に別のプロセッサ P2 による位置 X への書き込みが行われ、この 2 つのアクセスの間にプロセッサによる X への書き込みがまったく発生せず、読み取りと書き込みが十分に分離されている場合、X は常に P2 によって書き込まれた値を返す必要があります。この条件は、メモリの一貫性のあるビューの概念を定義します。共有メモリ位置への書き込みを伝播することで、すべてのキャッシュがメモリの一貫性のあるビューを持つことが保証されます。プロセッサ P1 が P2 による書き込みの後でも X の古い値を読み取る場合、メモリは一貫性がないと言えます。

上記の条件は、キャッシュの一貫性に必要な書き込み伝播の基準を満たしています。ただし、トランザクションのシリアル化の条件を満たしていないため、十分ではありません。これをわかりやすく説明するために、次の例を考えてみましょう。

マルチプロセッサ システムは、4 つのプロセッサ (P1、P2、P3、P4) で構成され、すべてのプロセッサに、初期値が 0 である共有変数Sのキャッシュされたコピーが含まれています。プロセッサ P1 は、 Sの値を (キャッシュされたコピー内で) 10 に変更し、続いてプロセッサ P2 は、自身のキャッシュされたコピー内でSの値を 20 に変更します。書き込みの伝播のみを保証する場合、 P3 と P4は、 P1 と P2 によるSの変更を確実に認識します。ただし、 P3 は、 P2 による変更を確認した後に P1 による変更を確認し、 Sの読み取り時に 10 を返す可能性があります。一方、 P4 は、 P1 と P2 による変更を、変更が行われた順序で確認し、Sの読み取り時に 20 を返す可能性があります。これで、プロセッサ P3 と P4 は、メモリの一貫性のないビューを持つことになります。

したがって、トランザクションのシリアル化を満たし、キャッシュの一貫性を実現するには、このセクションで説明した前の 2 つの条件に加えて、次の条件も満たす必要があります。

• 同じ場所への書き込みは順序付けられていなければなりません。言い換えれば、場所Xが2つの異なる値AとBをこの順序で任意の2つのプロセッサから受け取った場合、プロセッサは場所XをBとして読み取ってからAとして読み取ることはできません。場所Xは値AとBの順序で認識される必要があります。^[6]

コヒーレント システムの別の定義は、シーケンシャル コンシステンシメモリ モデルの定義によるものです。「キャッシュ コヒーレント システムは、各スレッドのプログラム順序を尊重する完全な順序で、すべてのスレッドのロードとストアを単一のメモリ位置に対して実行しているように見える必要があります。」 ^[4]したがって、キャッシュ コヒーレント システムとシーケンシャル コンシステンシ システムの唯一の違いは、定義で言及されているアドレス位置の数です (キャッシュ コヒーレント システムの場合は単一のメモリ位置、シーケンシャル コンシステンシ システムの場合はすべてのメモリ位置)。

別の定義は、「同じメモリ位置へのすべての書き込みが何らかの順序で実行される場合、マルチプロセッサはキャッシュ一貫性がある」というものである。^[7]

まれに、特にアルゴリズムでは、一貫性は参照の局所性を指すこともあります。同じデータの複数のコピーが異なるキャッシュに同時に存在する可能性があり、プロセッサが独自のコピーを自由に更新できる場合、メモリのビューに一貫性がなくなる可能性があります。

一貫性を保証する最も一般的な 2 つのメカニズムは、スヌーピングとディレクトリ ベースであり、それぞれに利点と欠点があります。^[8]十分な帯域幅が利用できる場合は、スヌーピング ベースのプロトコルの方が高速になる傾向があります。これは、すべてのトランザクションがすべてのプロセッサから参照される要求/応答であるためです。欠点は、スヌーピングがスケーラブルではないことです。すべての要求はシステム内のすべてのノードにブロードキャストされる必要があるため、システムが大きくなるにつれて、(論理または物理) バスのサイズとそれが提供する帯域幅を増やす必要があります。一方、ディレクトリは、レイテンシが長くなる傾向がありますが (3 ホップの要求/転送/応答の場合)、メッセージがポイントツーポイントでありブロードキャストではないため、使用する帯域幅ははるかに少なくなります。このため、大規模なシステム (>64 プロセッサ) の多くでは、このタイプのキャッシュ一貫性が使用されています。

1983年に初めて導入された^[9]スヌーピングは、個々のキャッシュがキャッシュされているメモリ位置へのアクセスのアドレスラインを監視するプロセスです。^[5]書き込み無効化プロトコルと書き込み更新プロトコルはこのメカニズムを利用しています。

スヌーピング機構では、スヌープフィルタは、各エントリが 1 つ以上のノードによって所有される可能性のあるキャッシュラインを表す複数のエントリを維持することによって、スヌーピングトラフィックを削減します。エントリの 1 つを置き換える必要がある場合、スヌープフィルタは、各エントリ内のプレゼンスベクトルから判断して、最も少ないノードによって所有されるキャッシュラインを表すエントリを置き換え用に選択します。最も少ないノードによって複数のキャッシュラインが所有されている場合は、時間的またはその他のタイプのアルゴリズムを使用して選択を絞り込みます。^[10]

ディレクトリベースのシステムでは、共有されるデータは、キャッシュ間の一貫性を維持する共通ディレクトリに配置されます。ディレクトリは、プロセッサがプライマリ メモリからキャッシュにエントリをロードするための許可を求めるフィルターとして機能します。エントリが変更されると、ディレクトリはそのエントリを含む他のキャッシュを更新するか、無効にします。

分散共有メモリシステムは、疎結合システム内のメモリブロック間の一貫性を維持するためにこれらのメカニズムを模倣します。^[11]

コヒーレンス プロトコルは、マルチプロセッサ システムにキャッシュ コヒーレンスを適用します。その目的は、2 つのクライアントが同じ共有データに対して異なる値を認識しないようにすることです。

プロトコルは、一貫性のための基本的な要件を実装する必要があります。ターゲット システムまたはアプリケーションに合わせてカスタマイズできます。

プロトコルは、スヌーピー ベースまたはディレクトリ ベースに分類することもできます。通常、初期のシステムでは、ディレクトリが共有されるデータと共有者を追跡するディレクトリ ベースのプロトコルが使用されていました。スヌーピー プロトコルでは、トランザクション要求 (読み取り、書き込み、またはアップグレード) がすべてのプロセッサに送信されます。すべてのプロセッサが要求をスヌープし、適切に応答します。

スヌーピー プロトコルでの書き込み伝播は、次のいずれかの方法で実装できます。

書き込み無効化

キャッシュがコピーを持っている場所への書き込み操作が観察されると、キャッシュコントローラはスヌープされたメモリ場所の自身のコピーを無効にし、次のアクセス時にメインメモリから新しい値を読み取るように強制します。^[5]

書き込み更新

キャッシュにコピーがある場所への書き込み操作が検出されると、キャッシュ コントローラは、スヌープされたメモリ場所の独自のコピーを新しいデータで更新します。

プロトコル設計で、共有データのコピーが変更されるたびに、他のすべてのコピーを「更新」して変更を反映する必要があると規定されている場合、それは書き込み更新プロトコルです。設計で、いずれかのプロセッサによるキャッシュされたコピーへの書き込みによって、他のプロセッサがキャッシュされたコピーを破棄または無効化する必要があると規定されている場合、それは書き込み無効化プロトコルです。

ただし、スケーラビリティはブロードキャスト プロトコルの欠点の 1 つです。

コヒーレンスを維持するために、MSI、MESI (別名イリノイ)、MOSI、MOESI、MERSI、MESIF、write-once、 Synapse 、 Berkeley 、Firefly、Dragon プロトコルなど、さまざまなモデルとプロトコルが考案されてきました。^[2] 2011 年に、ARM 社はSoCでコヒーレンスを処理するためにAMBA 4 ACE ^{[12]を提案しました。} ARM 社のAMBA CHI (Coherent Hub Interface) 仕様^[13]は、 AMBA5 仕様グループに属し、完全にコヒーレントなプロセッサを接続するためのインターフェイスを定義しています。

• 一貫性モデル
• ディレクトリベースの一貫性
• 記憶の壁
• 非均一メモリアクセス(NUMA)
• 偽りの共有

• パターソン、デイビッド、ヘネシー、ジョン(2009)。コンピュータの構成と設計(第 4 版)。モーガン カウフマン。ISBN 978-0-12-374493-7。
• ハンディ、ジム (1998)。キャッシュメモリブック(第 2 版)。モーガン カウフマン。ISBN 9780123229809。
• Sorin, Daniel; Hill, Mark; Wood, David (2011)。メモリの一貫性とキャッシュの一貫性に関する入門書( PDF )。Morgan and Claypool。ISBN 978-1608455645. 2017年10月20日閲覧。
• Steinke, Robert C .; Nutt, Gary J. (2004 年 9 月 1 日)。 「共有メモリの一貫性に関する統一理論」。Journal of the ACM。51 ( 5): 800–849。arXiv : cs/0208027。doi : 10.1145/1017460.1017464。S2CID 3206071  。