Go back

Multi-core programming and cache coherency

· Updated:

slides web

拙訳

疑問（Questions）

  • キャッシュはどのようにしてコア間のデータを共有するのか？
  • 複数コアが同時にメモリを更新しようとするとき、どのようにしてデータの｜整合性を保つ《stay consistent》のか？

単純な2コアCPU（Simple 2-core CPU）

（画像）

キャッシング（Caching）

（画像）

  • データはキャッシュラインに格納される（64/128バイト）
  • 最近使われたキャッシュラインには高速にアクセスできる

メモリは遠く離れている（Memory Is Far Away）

（画像：PS3のアーキテクチャ）

ICB --- インターコネクトバス（ICB - Inter Connect Bus）

  • コアを接続する
  • データだけじゃない
  • キャッシュコヒーレンスなプロトコル
  • “キャッシュコヒーレンスな｜ドメイン《domain》”
    • 通常はすべてのプロセッサとすべてのコア

MESIプロトコル（MESI Protocol）

  • キャッシュコヒーレンス
  • どのキャッシュラインでも一度に変更できるのは1つのコアだけ
  • キャッシュラインは4つの状態を取ることができる1
    • M ｜変更《Modified》
      • そのキャッシュだけに存在し、メインメモリ上の値から変更されている
    • E ｜排他《Exclusive》
      • そのキャッシュだけに存在し、メインメモリ上の値と一致している（コピーを持つ）
    • S ｜共有《Shared》
      • 他のキャッシュにも存在し、すべてがメインメモリ上の値と一致している（コピーを持つ）
    • I ｜無効《Invalid》
      • キャッシュラインが古くなり、もはや正しくない

MESIプロトコルのメッセージ（MESI Protocol Message）

  • メッセージはキャッシュ間のコヒーレンシーを維持するためにICBで送られる
  • ICB上の誰もが’｜読み込み《Read》’メッセージに応答することができる
    • メモリコントローラだけでなく他のコアも

MESIのメッセージタイプ（MESI Message Types）

  • メッセージタイプ（キャッシュラインに関連するもの）
    • ｜読み込み《Read》 / ｜読み込み確認《Read Acknowledge》
    • RWITW --- ｜書き込み目的の読み込み《Read With Intent To Write》
      • 読み込み＋無効化
    • ｜無効化《Invalidate》 / ｜無効化確認《Invalidate Acknowledge》
      • このキャッシュラインを無効化するよう他のコアに依頼する
    • ｜書き戻し《Writeback》
      • キャッシュラインをメインメモリに書き戻す

キャッシュライン遷移（Cache line transitions）

  • キャッシュラインを読み込む
    • 無効 -> 排他
      • ひとつのコアだけがコピーを持つ場合
    • 無効 -> 共有
      • 他のコアもコピーを持つ場合
  • キャッシュラインに書き込む
    • 排他 -> 変更
    • 共有 -> 変更
      • 他のすべてのコアはそのコアが持つこのキャッシュラインを無効化する
  • 無効化するよう指示する
    • 排他 / 共有 -> 無効
    • 変更 -> 無効
      • メインメモリへの’書き戻し’を誘発する
  • 別のコアが変更済みキャッシュラインを読み込もうとする
    • 変更 -> 共有
      • メインメモリへの’書き戻し’を誘発する

選手入場（The Players…）

  • 例
    • コア0 --- プロデューサー
      • void foo() {data = 1; flag = 1;}
    • コア1 --- コンシューマー
      • void bar() {while (flag == 0); assert(data);}

キャッシュ所有権の例（Cache Ownership Example）

if (a) {
    b = 4;
}
  1. 前提として、
    • 初期値はa = 1、b = 0とする
    • aとbは別のキャッシュライン上にあるとする
    • コア0のキャッシュは空である
    • コア1のキャッシュはaとbを”排他”状態で持つとする
  2. コア0がif (a)を評価しようとするとき、
    1. コア0は自身のキャッシュにaを持っていないので、aを要求するために’読み込み(a)‘メッセージを送る
    2. コア1は要求に応答して’読み込み確認(a = 1)‘メッセージを送り、aを”共有”状態にする
    3. コア0は応答を受け取って自身のキャッシュにインストールする。これで、コア0は’a’による分岐を評価できるようになる
  3. コア0がb = 4を評価しようとするとき、
    1. コア0は自身のキャッシュにbを持っていないので、bを要求するために’RWITW(b)‘メッセージを送る
      • 今回は読み込み後に書き込む必要があるので、その意向を示すために’RWITW（書き込み目的の読み込み）‘を送る
    2. コア1は要求に応答して’RWITW(b = 0)‘メッセージを送り、bを”無効”状態にする
      • ‘RWITW’メッセージは’無効化’の要求でもある
    3. コア0は応答を受け取って自身のキャッシュに”排他”状態でインストールする。これで、コア0はbを単独で持っていることになる
    4. コア0はbに4を格納して”変更”状態にする。このときはまだメインメモリに書き戻していない

2コアCPU＋StoreQ（2-core CPU + Store Qs）

（画像）

StoreQの理由（Reasons for Store Q）

  • 不足分の/無効なキャッシュラインを待っている間のCPU実行ストールを軽減する
  • すると、キャッシュラインが｜他より先に使える状態《more readily available》であるなら、ロードはストアを”｜追い越す《pass》”ことができる
    • すでにローカルキャッシュで、または、隣接するコアによって使えるようになっているかもしれない
  • ローカルで動作しているコアに対してメモリが同じに見えることを保証するため、ロードに対するStoreQの｜スヌーピング《snooping》（覗き見）が必要
    • ストアがキャッシュにたどり着かなかったとしても、後続のロードは格納された値をロードするべき

StoreQ問題の例（Store Q Issue Example）

void foo() {
    data = 1;
    flag = 1;
}

: コア0

void bar() {
    while (flag == 0);
    assert(data);
}

: コア1

  1. 前提として、
    • コア0はfooを実行する
    • コア1はbarを実行する
    • flagのキャッシュラインはコア0が所有する
    • dataのキャッシュラインはコア1が所有する
  2. コア0がdata = 1;を評価するとき、
    1. コア0はストア命令をStoreQに保存する。dataがキャッシュに存在しないので、dataの’RWITW’メッセージを送る
  3. コア1がwhile (flag == 0);を評価するとき、
    1. コア1は、flagがキャッシュに存在しないので、flagの’読み込み’メッセージを送る
  4. コア0がflag = 1;を評価するとき、
    1. コア0はflagを所有しているので、キャッシュを1に更新して”変更”状態にする
    2. コア0はflagの読み込み要求に応答して’読み込み確認(flag = 1)‘を送り、flagを”共有”状態にしてメインメモリに書き戻す
    3. コア1は応答を受け取って自身のキャッシュに”共有”状態でインストールする
  5. コア1がassert(data);を評価するとき、
    1. dataは”排他”状態で持っているので、そのまま読み込まれる。アサート!!
      • data = 1;はここまでコア0のStoreQに保存されたままである
    2. コア1は遅れてきたRWITW要求に応答して’RWITW(data = 0)‘を送り、dataを”無効”状態にする
    3. コア0は応答を受け取り、自身のキャッシュに”排他”状態でインストールする
    4. コア0のStoreQはflagへの書き込みをコミットできるが、時すでに遅し。コア1は｜停止《halt》し、実行がストップする

どうやってこの問題を解決するか？（How do we solve this issue?）

  • すべてのキャッシュはメインメモリの一貫性のある視点を持つが、ローカルな書き込みはその範疇ではない
  • 格納されるデータは’キャッシュコヒーレントな領域《domain》’の一部であることを保証する方法が必要
    • すなわち、他のコアによって見えている
      • すなわち、他のコアがフェッチできる
  • StoreQをキャッシュにフラッシュできる？
    • メモリストアバリア（__mb_release）

メモリストアバリア（Memory Store Barirers）

  • メモリバリアより先行しているStoreQ中のすべてのデータがキャッシュ中に存在するようになるまで返らないCPU命令
    • CPUは悪！
  • コンパイラがこのバリアをまたいでメモリストアを最適化するのを防ぐ
    • コンパイラは悪！
  • そのキャッシュ中にデータが存在するようになれば、他のすべてのキャッシュでキャッシュラインが無効化されるため、他のすべてのキャッシュによって確認できるようになる
    • RWITW（書き込み目的の読み込み）
      • 読み込み＋無効化

StoreQ問題の例（修正版）

void foo() {
    data = 1;
    __mb_release();
    flag = 1;
}

: コア0

void bar() {
    while (flag == 0);
    assert(data);
}

: コア1

  1. 前提として、
    • コア0はfooを実行する
    • コア1はbarを実行する
    • flagのキャッシュラインはコア0が所有する
    • dataのキャッシュラインはコア1が所有する
  2. コア0がdata = 1;を評価するとき、
    1. コア0は書き込み命令をStoreQに保存する。その後、dataがキャッシュに存在しないので、dataの’RWITW’メッセージを送る
  3. コア1がwhile (flag == 0);を評価するとき、
    1. コア1は、flagがキャッシュに存在しないので、 flagの’読み込み’メッセージを送る
  4. コア0が__mb_release();を評価するとき、
    1. コア0はキャッシュをフラッシュするためにStoreQに対するメモリバリアでブロックする
    2. コア0はflagの読み込み要求を受け取って’読み込み確認(flag = 0)‘応答を送り、flagを”共有”状態にする
    3. コア1は読み込み応答を受け取り、自身のキャッシュに”共有”状態でインストールする
    4. コア1は遅れてきたRWITW要求に応答して’RWITW(data = 0)‘を送り、dataを”無効”状態にする
    5. コア0は応答を受け取り、自身のキャッシュに”排他”状態でインストールする
    6. コア0はStoreQのdataへの書き込みをキャッシュにコミットして、dataを”変更”状態にする
  5. コア0がflag = 1;を評価するとき、
    1. コア0はflagに1をセットしたいがflagは”共有”状態なので、まずflagの無効化要求メッセージを送る
    2. コア1は無効化要求を受け取って’無効化確認(flag)‘を送り、flagを”無効”状態にする
    3. コア0は応答を受け取るとflagを変更することができるようになる
  6. コア1がwhile (flag == 0);を再び評価するとき、
    1. コア1はflagが”無効”状態なのでflagの’読み込み’メッセージを送る
    2. コア0はflagの読み込要求に応答して’読み込み確認(flag = 1)‘を送り、flagをメインメモリに書き戻して”共有”状態にする
    3. コア1は応答を受け取り、自身のキャッシュにflagを”共有”状態でインストールする。これでwhile (flag == 0)のループから抜け出すことができる
  7. コア1がassert(data);を評価するとき、
    1. コア1は同様にしてdataを読み込む

2コアCPU＋StoreQ＋InvQ（2-core CPU + Store Qs + Inv Q）

（画像）

InvalidateQの理由（Reasons for Invalidate Q）

  • 他のコアからのより高速な無効化応答
    • ビジーなコアは応答するのに時間がかかる可能性がある
    • ‘無効化確認’応答はキャッシュがキャッシュラインを実際に無効化するまで送ることができない
  • 契約: キューに入れたメッセージで、そのキャッシュラインに対するものすべてが処理され終わるまで、そのキャッシュラインに対するMESIメッセージはこのコアによって送られることはない

InvalidateQ問題の例（Invalidate Q Issue Example）

  1. 前提として、
    • コア0はfooを実行する
    • コア1はbarを実行する
    • flagのキャッシュラインはコア0が所有する
    • dataのキャッシュラインはコア1が所有する
  2. コア0がdata = 1;を評価するとき、
    1. コア0は書き込み命令をStoreQに保存する。その後、dataがキャッシュに存在しないので、dataの’RWITW’メッセージを送る
  3. コア1がwhile (flag == 0);を評価するとき、
    1. コア1は、flagがキャッシュに存在しないので、 flagの’読み込み’メッセージを送る
  4. コア0が__mb_release();を評価するとき、
    1. コア0はキャッシュをフラッシュするためにStoreQに対するメモリバリアでブロックする
    2. コア1はRWITW要求に応答して’RWITW(data = 0)‘を送り、dataの無効化をInvQに記録する
    3. コア0は応答を受け取り、自身のキャッシュに”排他”状態でインストールする
    4. コア0はStoreQのdataへの書き込みをキャッシュにコミットして、dataを”変更”状態にする
  5. コア0がflag = 1;を評価するとき、
    1. コア0は、flagが”排他”状態であるため、flagを直接更新する
    2. コア0はflagの読み込み要求を受け取って’読み込み確認(flag = 0)‘応答を送り、flagをメインメモリに書き戻して”共有”状態にする
    3. コア1は読み込み応答を受け取り、自身のキャッシュに”共有”状態でインストールする
  6. コア1がassert(data);を評価するとき、
    1. コア1は、dataが”排他”状態であるため、メッセージは送らずに自身の古なった値を読み込む
      • dataの無効化処理はInvQに保存されたままである
    2. コア1はInvQからdataの無効化を適用するが遅すぎる。クラッシュ!!

どうやってこの問題を解決するか？（How do we solve this issue?）

  • 今回は、ローカルコアは読み込みを処理するときに持っているすべての情報を使っていない
    • なぜ？
      • スピード、スピード、スピード
  • すべての情報を使うことをコアに強制する方法はあるのか？
    • はい、‘InvalidateQ’をフラッシュできる
    • メモリロードバリア（__mb_acquire）

メモリロードバリア（Memory Load Barriers）

  • CPU命令
  • InvalidateQ内のすべてのメッセージが処理される
  • バリアに先立つすべてのロードが完了する
    • CPUは悪だって言ったよな！
  • コンパイラがこのバリアをまたいだメモリロードを最適化しないようにさせる
    • コンパイラは悪！
  • バリア後のデータ読み込みは他のキャッシュ/メインメモリから新しく引き出されることを保証する
    • 古くなったキャッシュラインを効果的に立ち退かせる

InvalidateQ問題の例（修正版）

void foo() {
    data = 1;
    __mb_release();
    flag = 1;
}

: コア0

void bar() {
    while (flag == 0);
    __mb_acquire();
    assert(data);
}

: コア1

  1. 前提として、
    • コア0はfooを実行する
    • コア1はbarを実行する
    • flagのキャッシュラインはコア0が所有する
    • dataのキャッシュラインはコア1が所有する
  2. コア0がdata = 1;を評価するとき、
    1. コア0は書き込み命令をStoreQに保存する。その後、dataがキャッシュに存在しないので、dataの’RWITW’メッセージを送る
  3. コア1がwhile (flag == 0);を評価するとき、
    1. コア1は、flagがキャッシュに存在しないので、 flagの’読み込み’メッセージを送る
  4. コア0が__mb_release();を評価するとき、
    1. コア0はキャッシュをフラッシュするためにStoreQに対するメモリバリアでブロックする
    2. コア1はRWITW要求に応答して’RWITW(data = 0)‘を送り、dataの無効化をInvQに記録する
    3. コア0は応答を受け取り、自身のキャッシュに”排他”状態でインストールする
    4. コア0はStoreQのdataへの書き込みをキャッシュにコミットして、dataを”変更”状態にする
  5. コア0がflag = 1;を評価するとき、
    1. コア0は、flagが”排他”状態であるため、flagを直接更新する
    2. コア0はflagの読み込み要求を受け取って’読み込み確認(flag = 0)‘応答を送り、flagをメインメモリに書き戻して”共有”状態にする
    3. コア1は読み込み応答を受け取り、自身のキャッシュに”共有”状態でインストールする
  6. コア1が__mb_acquire();を評価するとき、
    1. コア1はメモリバリアに到達し、InvalidateQが空になるまで待機する
    2. コア1はInvalidateQを処理し、dataを”無効”状態にする
    3. InvalidateQが空になったので、待機が明け実行を再開する
  7. コア1がassert(data);を評価するとき、
    1. コア1はdataが”無効”状態なのでdataの’読み込み’メッセージを送る
    2. コア0はdataの読み込要求に応答して’読み込み確認(flag = 1)‘を送り、dataをメインメモリに書き戻して”共有”状態にする
    3. コア1は応答を受け取り、自身のキャッシュにdataを”共有”状態でインストールする。これでassert(data)を通過できる

解決法(メモリバリア)（The Solutions (Memory Barriers)）

  • 2種類ある
    • ｜解放《release》セマンティクス__mb_release
      • StoreQをフラッシュする
      • プロデューサーの挙動
      • コンパイラがバリアをまたいでストアを移動できなくする
    • ｜取得《acquire》セマンティクス__mb_acquire
      • キャッシュInvalidateQをフラッシュする
      • 先立つロードが完了する
      • コンシューマーの挙動
      • コンパイラがバリアをまたいでロードを移動できなくする

メモリバリア --- 解放セマンティクス（Memory Barriers - Release Semantics）

  • コンパイラやCPUによる書き込みの｜並べ替え《reordering》を防ぐ
    • データへのアクセス権を配るときに使われる
  • x86/x64: _ReadWriteBarrier();、_mm_sfence();
    • コンパイラ固有命令、コンパイラの並び替えを防ぐ
  • PowerPC: __lwsync();
    • ハードウェアバリア、CPU書き込みの並び替えを防ぐ
  • 位置取りが重要！
    • データを書き込む
    • __mb_release()
    • 制御値を書き込む

メモリバリア --- 取得セマンティクス（Memory Barriers - Acquire Semantics）

  • コンパイラやCPUによる読み込みの並び替えを防ぐ
    • データへのアクセス権を得るときに使われる
  • x86/x64: _ReadWriteBarrier();、_mm_lfence();
    • コンパイラ固有命令、コンパイラの並び替えを防ぐ
  • PowerPC: __lwsync();またはisync();
    • ハードウェアバリア、CPU読み込みの並び替えを防ぐ
    • __lwsync();
      • これはStoreQ、InvQ、ロード待機を同期させる
    • __isync();
      • これはInvQを空にして、｜命令キャッシュ《I-cache》をクリアする。これは命令プリフェッチ、すなわち、投機的な読み込みを防ぐ。これはあとで読み込まれるいかなるデータも最新であることを保証する
  • 位置取りが重要！
    • 制御値を読み込む
    • __mb_aquire()
    • データを読み込む

lwsyncについての簡単なメモ（A quick note on lwsync()）

  • ストア→ロードの順を強制するわけではない
  • ‘取得’メモリバリアで気を付ける
Xbox360の並び替え同期なしlwsyncsync
読み込みが読み込みの先に移動するYNN
書き込みが書き込みの先に移動するYNN
書き込みが読み込みの先に移動するYNN
読み込みが書き込みの先に移動するYYN

フォールスシェアリング（False Sharing）

  • 異なるコアで処理される、同じキャッシュライン上のデータメンバーを持つのを回避する
    • これをやらないと、結果としてキャッシュラインが行ったり来たりしたりパフォーマンスが劣化したりすることになる
  • これを抑制するために、自身のキャッシュライン上に共有データのアクセス制御フラグを維持する

3つの独立層（Three Independent Layers）

  • 実行
    • CPUは、キャッシュがそのデータを持つ限り、キャッシュから独立して実行できる
  • キャッシュ
    • キャッシュはキャッシュコヒーレンシーを保証するためにメインメモリにいかなるデータも書き込む必要はない
    • 他の最適化として、本当に必要とされるまでメインメモリへの書き込みを更に抑制する方法が存在する（例: MOESI）
  • メインメモリ
    • I/Oデバイス（GPUの読み出し）はキャッシュではなくこれを見ている。他のデバイスがデータを読めるようにしたいなら、そのデータをちゃんとメインメモリに最後まで書き込む必要がある
    • メインメモリは本当に遠く離れている

コンペア・アンド・スワップ（CAS）（Compare And Swap (CAS)）

  • ｜整列《aligned》したネイティブサイズのメモリロケーションのアトミック更新
    • 32ビットや64ビット、時折その他のサイズも
  • メインメモリではなく、‘キャッシュレイヤー’で処理する
  • PowerPC
    • 予約付きロード（アドレス）
    • 条件付きストア（アドレス, 新しい値）
      • 成功（0）/失敗（0以外）を返す
  • Intel/AMD
    • CompareAndExchange（アドレス, 期待される値, 新しい値）
      • ‘アドレス’内の以前の値を返す
      • 以前の値 == 期待される値 ? 成功 : 失敗

例: コンペア・アンド・スワップ（CAS）（Example: Compare And Swap (CAS)）

  • PowerPC/PS3:
    • lwarx / stwcx
      • PowerPCプロセッサは一度にひとつの予約のみを保持できる
    • ほかのすべての先立つロード/ストアが他のコアから見えていることを保証しているわけではない
      • 解決策: CAS成功後に__lwsyncか__isyncを追加する
  • Intel/AMD
    • lock cmpxchg [ecx], edx
      • ecx --- 変数へのポインタ
      • eax --- 期待される変数の値
      • edx --- 変数 == eaxの場合に書き込む値
    • すべての先立つロード/ストアが他のコアから見えていることを保証している

取得の例（スピンロック）（Acquire Example (Spinlock)）

spinlock_64_try_mp:
    mr r5, r3          // r5はロックアドレス
    li r3, 1           // '成功'の戻り値をロード
1:
    lwarx r4, 0, r5    // 予約付きロード
    li r6, -1          // locked == -1
    cmpwi r4, 0
    bne-- 2f           // ロックされていれば、早期離脱する

    stwcx. r6, 0, r5   // 条件付きストア
    isync              // 投機的実行をキャンセルする
    beqlr++            // 成功すれば、CASは成功(r3 = 1)を返す
    b 1b               // そうでなければ、もう一度試す
2:
    li r6, -4
    stwcx. r5, r6, r1  // 保留中の予約をクリア(ダミー書き込み)
    li r3, 0           // ロックを得られず、失敗(r3 = 0)が返る
    blr

: AppleOSのコード

解放の例（スピンロック）（Release Example (Spinlock)）

spinlock_64_unlock_mp:
    lwsync         // アンロックの前に先立つストアを完了させる
    li r4, 0
    stw r4, 0(r3)
    blr

マルチコアプログラミングは難しい（Multi-Core Programming Is Hard）

  • 既存のOS同期プリミティブ（クリティカルセクション、ミューテックス、イベント）を使うことは賢明な判断である
  • …本当にパフォーマンスが欲しい場合でないならば
    • ミューテックスのロック = 数千サイクル
    • バリア = 約100サイクル

サイクル計測（Timings in cycles）

XBox PowerPCWindows Intel
lwsync33-4820-90
InterlockedIncrement CAS（OS関数）225-26036-90
クリティカルセクション（Acq+Rel）約34540-100
ミューテックス（Acq+Rel）約2350750-2500

スレッドセーフ != コンカレント（Thread-Safe != Concurrent）

  • スレッドセーフ（私個人の定義）
    • 多数のスレッドがこの関数を安全に呼び出すことができる
    • 2つ以上のスレッドでは｜進捗経過《progress》を保証しない2
  • コンカレント（私個人の定義）
    • 多数のスレッドがこの関数を安全に呼び出すことができる
    • ほとんどのスレッドはいつでも｜進捗良好《are having forward progress》2

ベストプラクティス（Best Practice）

  • OSが提供するクリティカルセクションを用いることを推奨する
  • 取得/解放メモリバリアを用いる
  • 共有するデータ/フラグを128バイト境界に｜整列《align》させる
    • ハードウェアプリフェッチによりIntel/AMDでも
  • PS3: 疑わしいときや、ロック後にデータを読み込むときは、lwsyncより｜前《over》にisyncを使う
  • チェックインする前にコードが機能していることを保証するため、コードがこのレベルで書かれたいかなるコードも同僚たちにレビューさせる

おみやげ（Take Away）

  • 他のレイヤーへのデータを強制するための固有の命令を使う
    • キャッシュレイヤー（他のコア） --- lwsyncとisync
    • メインメモリ（IOデバイス） --- eioioとsync
  • SPUプログラミングやDMAのやつに少し似ている
    • レイヤー間でデータを明示的に’転送’する
  • これはプロセッサの動作方法を非常に単純化して見ている
    • 例: メモリアクセスモード
      • Write-Through
      • Cache-Inhibited
      • Cache-Coherent
      • Guarded
  • ｜恐れよ！！《Be scared!!》
    • 恐ろしくないとしたら、このプレゼンテーションを理解していないということだ

Footnotes

  1. 訳注:参考 ↩

  2. 訳注:一方が他方の処理をブロックすることがあるかどうか、ということ？ ↩ ↩2

Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous Post
Optics
Next Post
Real Camera