# キャッシュコヒーレンスプロトコル ## 定義 キャッシュコヒーレンス(cache coherence)とは、あるメモリ位置Xへの読み取りが常にXへの最新の書き込みの値を返すという性質である。形式的には(1)プロセッサPによるXへの書き込みの直後にPが行うXの読み取りは、その間に他プロセッサの書き込みがなければ必ずPが書いた値を返す、(2)十分な時間差があれば他プロセッサの書き込みの値を読み取れる、(3)同一アドレスへの複数の書き込みはすべてのプロセッサから同じ順序で観測される(書き込みの直列化、write serialization)、という3条件で定義される。マルチプロセッサでキャッシュされた共有データが複数の私有キャッシュに複製されると、ある1コアの書き込みが他コアのキャッシュに古い値として残ってしまうためこの問題が生じる。コヒーレンスを回復する方式は大きくスヌーピング(snooping)とディレクトリベース(directory-based)の2系統に分かれる。スヌーピングは共有バス上の全トランザクションを各キャッシュが監視し、自分が保持するアドレスへの書き込みを検知したら無効化・更新する方式で、ブロードキャストの単純さゆえに実装しやすいが、バス帯域がプロセッサ数に対してボトルネックになる。ディレクトリベースは各メモリブロックの共有状態を単一の場所(ディレクトリ)に集約し、無効化を実際にそのブロックを保持するノードだけへ選択的に送ることでブロードキャストを避け、分散メモリマルチプロセッサへスケールできる。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 5 Thread-Level Parallelism]] §5.2, §5.4) 代表的な状態遷移プロトコルはMSI(Modified/Shared/Invalid)を基本とし、単一キャッシュにのみクリーンな状態で存在することを示すExclusive状態を加えたMESI(Intel系が採用、i7はさらにForward状態を加えたMESIF)、Modified状態からメモリへの書き戻しなしに所有権のみを移すOwned状態を加えたMOESI(AMD Opteronが採用)という拡張系列を持つ。(Source: §5.2) ## 横断的知見 - **同じ「スヌーピーキャッシュ」という機構を、教科書の抽象度がまったく異なる形で提示している**。[[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]] §10.2.4は、キャッシュコヒーレンスを「一時的な不変条件違反を外部に見せない厳密一貫性の一種」という一般設計原則の具体例として提示し、共有バス上の書き込みトランザクションを各私有キャッシュが監視して無効化・更新するという機構を2〜3段落・図1枚で説明し、詳細はHennessy & Patterson『Computer Architecture: A Quantitative Approach』の該当章(旧版では第8章)を参照するよう促すにとどめる。本章はまさにその参照先であり、単純な「無効化するか更新するか」の二択(write invalidate対write update)から始めて、MSI/MESI/MOESIという段階的な状態拡張、書き込みミスの非原子性(バス調停・所有権確立・無効化応答が単一サイクルで済まない問題)、タグの複製やL3ディレクトリによる帯域スケーリング策まで、MITOCWの教科書が意図的に踏み込まなかった実装詳細を体系化する。同一の機構が「一般設計原則の一事例」として簡潔に扱われる文脈と、「マルチプロセッサアーキテクチャの中核設計問題」として数十ページを割いて扱われる文脈の両方に登場するという事実は、キャッシュコヒーレンスが分散システム設計論とコンピュータアーキテクチャ論の交差点に位置する概念であることを示す。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]] §10.2.4, [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 5 Thread-Level Parallelism]] §5.2) - **[[メモリ階層とキャッシュ]]が記録する「コヒーレンシコストは40〜75サイクル」という実測値を、本ページはその発生源であるプロトコルの状態遷移として説明できる**。『詳解 システム・パフォーマンス 第2版』§6.4.1.3.4が報告するこのコストは、MSI/MESIプロトコルにおいて他コアが共有・変更済みのラインへアクセスした際に生じるバス調停・無効化・(必要なら)ライトバックの合計時間に対応する。本章の定量例(8プロセッサ・L2要求15サイクルの構成でコヒーレンストラフィックがL2帯域の50%を超えないためにはコヒーレンスミス率0.73%以下が必要)は、この40〜75サイクルという単発コストが、コヒーレンスミス率の上限という形でシステム全体のスケーラビリティ制約に変換される過程を定量的に示す一次資料である。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 5 Thread-Level Parallelism]] §5.2, [[メモリ階層とキャッシュ]]) ## 未解決の問い - MITOCW教科書が示す蛍光ペン方式(shared変数をキャッシュ対象から除外する、Javaのvolatile相当)は、本章のMSI/MESI/MOESIのような状態遷移プロトコルと共存可能な補完策として実機で使われているか、それとも代替策として選ばれる場面(組み込み・低コア数)があるか。 - ディレクトリベースコヒーレンスにおけるビット vector 方式は「数百プロセッサ規模まで実用的」と本章は述べるが(§5.4)、それを超える規模(HPCクラスタ・warehouse-scale computer)で使われるスケーラブルなディレクトリ表現(疎行列表現・階層ディレクトリなど)の詳細は本章の範囲外([[Appendix I]]参照とされる)。関連する `.raw` 未取り込みの Appendix I がwiki化されれば、この問いに直接答えられる可能性がある。 - 非対称NUMAインターコネクト([[非対称NUMAインターコネクト]])を持つシステムでは、ディレクトリの配置(メモリと同じノードに置くか、独立に分散するか)がコヒーレンストラフィックの帯域消費パターンにどう影響するか。両概念を横断した定量評価は現時点で ingest したソースには見当たらない。 ## 関連 - [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 5 Thread-Level Parallelism]] — 本概念の主要出典。スヌーピング/ディレクトリの詳細な状態遷移とスケーラビリティ限界を扱う。 - [[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]] — スヌーピーキャッシュを一般設計原則(厳密一貫性)の一事例として簡潔に導入する教科書。 - [[メモリ階層とキャッシュ]] — コヒーレンシコスト(40〜75サイクル)の実測値を記録する上位概念。 - [[メモリ一貫性モデル]] — コヒーレンスとは独立した「異なるアドレス間の順序」を扱う姉妹概念。 - [[非対称NUMAインターコネクト]] / [[NUMAメモリ配置]] — ディレクトリの物理配置と相互接続トポロジが関わる関連概念。 - [[分散キャッシュ]] — ソフトウェアレイヤーでの分散キャッシュ無効化(pubsubベースの無効化伝播など)という、ハードウェアコヒーレンスとは異なる層の類似問題。 ## 出典 - [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 5 Thread-Level Parallelism]] §5.2, §5.4, §5.8 - [[@2009__MITOCW__Principles of Computer System Design - Chapter 10 Consistency]] §10.2.4