こんにちは、ヘルスケア事業本部のちょうです。前回

CPUレベルでなぜ並列プログラムはなぜ思った通りに動いてないのを分析しました。要するに、CPUのキャッシュ間でMESIなどのCache Coherenceプロトコルがあるものの、Store BufferとInvalidate Queueなど最適化するための仕組みによって、命令がreorderされたように見えます。

違う値を見ただけでまだいいですが、reorderにより並列プログラムの動作は予測できなくなり、つまりundefined behaviorは一番の問題です。reorderを制御するには、memory barrierという仕組みがあります。CPUアーキテクチャによって命令が変わるのですが、目的は一緒です：前後命令の実行に制限をかけます。

https://en.wikipedia.org/wiki/Memory_barrier

前回のプログラムで、 a = 1 と f = true の間に smp_mb() (symmetric multiprocessing memory barrier)を入れてみます。結果はどうなるでしょう。

CPU 0にfのキャッシュがあり、CPU 1にaのキャッシュがあるとする

int a = 0;
bool f = false;

void cpu0 {
  a = 1;
  smp_mb();
  f = true;
}

void cpu1 {
  while(!f);
  printf("%d\n", a);
}

CPU 0が a = 1 を実行する、aは自分のキャッシュにないので、MESIメッセージread invalidateを送信し、a = 1を自分のStore Bufferに入れる
CPU 1が while(!f); を実行する、fは自分のキャッシュにないので、MESIメッセージreadを送信する
CPU 0が smp_mb() を実行する、Store Bufferにあるエントリをマークする（つまり、a = 1）
CPU 0は f = true を実行する、自分のキャッシュにfがいる（ステータスModifiedもしくはExclusive）、本来ならキャッシュに書き込むのですが、Store Bufferにマークしたエントリがあり、f = trueをStore Bufferにマークせずに入れる
CPU 0はCPU 1からのreadメッセージを受信する、キャッシュにあるfの値（false）を送信する、同時にキャッシュにあるfをステータスSharedに変更する
CPU 1はCPU 0のレスポンスを受信する、b = falseを自分のキャッシュにインストールする
CPU 1は while(!f); を実行する、bはfalseなので、printfに進まない
CPU 1はCPU 0からのread invalidateメッセージを受信する、自分のキャッシュにあるaの値（0）を送信し、自分が持っているaを無効にする
CPU 0はCPU 1からのレスポンス（a=0）を受信する、Store Bufferを実行する
（CPU 0の）Store Bufferにあるa = 1をキャッシュに適応する、次マースしてないf = trueも実行しようとするが、キャッシュにあるfはステータスsharedであり
CPU 0はまずinvalidateメッセージを送信する
CPU 1はCPU 0からのinvalidateメッセージを受信する、自分のキャッシュにあるfを無効にして、acknowledgementメッセージを送信する
CPU 1は while(!f); を実行する、キャッシュにfがないので、readメッセージを送信する
CPU 0はCPU 1からのacknowledgementメッセージを受信する、キャッシュにあるfをExclusiveステータスに変更し、b = trueを適用する
CPU 0はCPU 1からのreadメッセージを受信する、fの値（true）を送信し、fのステータスをSharedに変更する
CPU 1はCPU 0からのレスポンスを受信する、fの値(true)をキャッシュにインストールする
CPU 1は while(!f); を実行する、fはtrueなので、次に進める
CPU 1は printf("%d\n", a) を実行する、キャッシュにaがないので、CPU 0から最新のaを値（1）をもらって、正しい結果を出力する

個人的な理解ですが、ここでポイントになるのは、Memory Barrierのあとに実行される命令は、前の命令の次に反映します。Store Bufferを非同期で処理するキューとして考えてみれば、a = 1を反映するまで時間かかるなら、次の命令を一緒にStore Bufferに入れて、順番の問題を避けられます。

ここで smp_mb() を書いてますが、CPUレベルで、つまりアセンブリコードでは、例えばx86アーキテクチャで、mfenceというコマンドになります。そして、

full memory barrier、mfence(memory fence)、store buffer, invalidate queueに影響すると理解してもいい
write memory barrier、sfence(store fence)、store bufferに影響すると理解してもいい
read memory barrier、lfence（load fence）、invalidate queueに影響すると理解してもいい

3つのタイプに分けてます。store bufferにどう影響するのは大体うえのような流れで（CPUアーキテクチャによって変わるので言い切れない）、invalidate queueにどう影響するというと、キャッシュから値を取る前にinvalidate queueをチェックして、もしinvalidate queueに入っていればまず無効にして、古い値を使ってしまうようなことを避けるのです。

直接memory barrierのコマンドを使う以外に、一部のコマンド、例えばx86においてatomic変数のRMW（Read-Modify-Write）、XADD, XCHGにLOCKというプリフィックスに追加すると、（full）memory barrierのような効果が得られます。ここのLOCKとカーネルが提供しているmutexなどは違います。資料によると、基本はCPUキャッシュ間のLOCKになり、場合によってメインメモリーとのLOCKになるそうです。興味ある方はCPUのマニュアルに参考してください。

memory barrierがあれば、並列プログラムが正しく書けるとは言えないです。資料には Multi-copy atomicity についてすこし紹介したのですが、正直自分は理解してない部分です。それと、直接memory barrierを使う場合はほとんどないと、カーネルか、例えば、mutex、プログラム言語レベルでMemory Modelとして別の形で利用されます。これらの中でhappends-beforeルールがあれば、それはmemory barrierが保証してくれます。

いかがでしょうか。CPUレベルで並列プログラムの基礎になるmemory barrierのこと、すこしお分かりになりましたか。そして次回の内容はC++11のMemory Modelを紹介して、うえのプログラムはC++11でどうなるかになります。