フォルスシェアリングとキャッシュライン競合の原理

コヒーレンスの単位はラインであってバイトではない

マルチコアで「並列化したのに速くならない、むしろコアを増やすほど遅い」という現象の典型的な犯人がフォルスシェアリング（偽共有）です。原因は一点に集約されます──キャッシュコヒーレンシはキャッシュライン（多くの x86/ARM 実装で 64 バイト）単位で管理され、バイト単位ではないことです。

各コアは自分の L1/L2 に同じラインのコピーを持てますが、MESI などのコヒーレンシプロトコルは「あるコアがラインへ書くなら、他コアの同一ラインコピーをすべて無効化（Invalidate）してから書く」という規律で整合を保ちます。この無効化の粒度がラインなので、そのライン上のどのバイトを書いたかは区別されません。論理的に無関係な 2 つの変数でも、同じ 64B ラインに同居していれば、片方への書き込みがもう片方のコピーを巻き添えで無効化します。これがフォルスシェアリング、すなわち「共有していないのにハードウェアは共有しているとみなす」状態です。

ピンポンが起きる仕組み

具体例で追います。counter[0] をコア A が、counter[1] をコア B が更新する、互いに独立なはずのコードです。

struct {
    long a;   // コア A だけが更新
    long b;   // コア B だけが更新
} shared;     // a と b は隣接 → 同一ラインに同居

a と b は隣接配置されるため、ほぼ確実に同じ 64B ラインに乗ります。すると次が繰り返されます。

1. コア A が a に書く。プロトコルは A のラインを **Modified（所有・他は無効）**にし、B 側のコピーを Invalid にする。
2. コア B が b に書こうとするが、B のコピーは Invalid。B は最新ラインを A から取り寄せ（あるいはディレクトリ経由で所有権を奪い）、自分が Modified になる。今度は A 側が Invalid。
3. 次に A が a に書くと、また B から奪い返す。

この所有権の往復をキャッシュラインピンポンと呼びます。実データ（a の値、b の値）は互いに不要なのに、ライン全体がコア間バスやコヒーレントインターコネクトを行き来します。各往復は L1 ヒット（約 1ns）ではなく、リモート L2/L3 やインターコネクト往復（数十 ns〜）になり、スループットが桁で落ちます。コア数を増やすほど競合者が増え、負のスケーリングさえ起こります。

ミス分類への位置づけ：3C＋コヒーレンス

単一コアのキャッシュミスは初期参照・容量・競合の**3C（Compulsory / Capacity / Conflict）に分類されますが、マルチコアではこれに第4のC＝コヒーレンスミス（Coherence miss）**が加わります。フォルスシェアリングによるミスはこのコヒーレンスミスに属します。

重要なのは、コヒーレンスミスは容量を増やしても消えない点です。L3 を倍にしても、無効化はライン単位の論理で起きるため無関係です。さらに偽共有は真の共有（True sharing）と区別が必要です。真の共有は複数コアが同じ論理データを実際に読み書きするため通信が本質的に必要ですが、偽共有は配置を変えれば通信そのものが消える──ここが対策可能性の分かれ目です。

防ぐ原理：ホットな変数を別ラインへ追い出す

対策はすべて「同時に別コアが書く変数を、物理的に別のキャッシュラインへ分離する」という一点に帰着します。

パディングとアラインメント

各コア専用のデータを 64B 境界に整列させ、ライン丸ごとを占有させます。

struct counter {
    long value;
    char pad[64 - sizeof(long)]; // 残りを埋め、次の counter を別ラインへ
} __attribute__((aligned(64)));

struct counter counters[NCORES]; // 各要素が独立したラインを占有

aligned(64) で先頭をライン境界に合わせ、pad でライン末尾まで埋めます。両方が要る点に注意してください。アラインメントだけだと隣接要素が同じラインの後半に食い込み、パディングだけだと配列先頭がライン中央から始まって 1 要素が 2 ラインにまたがり得ます。C++17 なら std::hardware_destructive_interference_size（＝偽共有を避けるべき最小間隔）を使うと、64 という即値をハードコードせずに済みます。

配置・分離・スレッドローカル化

• 構造体のフィールド並べ替え: 読み取り専用（コア間で共有してよい）フィールドと、頻繁に書かれるフィールドを別ラインに分ける。ホットでミュータブルなフィールド同士も離す。
• スレッドローカル集約: 各スレッドが自分専用のローカル変数（別ライン、理想的には別ページ）に加算し、最後に一度だけ合算する。これが最も確実で、書き込み中のコヒーレンス通信をゼロにできる。ヒストグラムや統計カウンタの定番。
• 配列のストライド配置: スレッド i が arr[i] ではなく arr[i * STRIDE] を使い、隣接スレッドのアクセスをライン境界より広く離す。
• 共有の最小化: そもそも書き込みを共有領域から追い出し、最後の縮約（reduction）だけで交わるよう設計を変える。

まとめ

• キャッシュコヒーレンシはキャッシュライン（典型 64B）単位で働くため、無関係な変数でも同一ラインに同居すると互いの書き込みで無効化し合う。
• 所有権がコア間を往復するラインピンポンで、L1 ヒット相当だったアクセスがインターコネクト往復に化け、スループットが桁落ち・負のスケーリングを招く。
• これは 3C に加わるコヒーレンスミスであり、容量増では消えず、偽共有は真の共有と違って配置変更で根絶できる。
• 対策はホットな変数を別ラインへ追い出すこと──64B アラインメント＋パディング、スレッドローカル集約、ストライド配置が中心で、perf c2c で裏取りする。

CPU 側でミスをどう隠すかはアウトオブオーダー実行が、依存とストールの基礎はパイプラインハザードが掘り下げます。