こんにちは、ヘルスケア事業部のちょうです。今日は並列プログラミングによくある間違うコード及びその原因について共有したいと思います。

まずはコード（抜粋、C言語）

int a = 0;
bool f = false;

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

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

関数cpu0とcpu1が別々のスレッドで実行されると、結果がどうなるでしょう。

1？もちろんそのはずですが、100回やると、たまに0も出るかもしれません。

驚かないでぐださい、普段シリアルで書いたコードがパラレルで実行されるといろんな「不思議なこと」が起こるのです。結果は0の場合、ただaが1になる前の値です。言い換えれば、ステートメント1と2を交換されたような現象です。

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

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

この現象はいわゆるreorder、ステートメントが並べ替えされたようなことです。実はreorderはすくなくとも３つの段階で発生します。

コンパイル
CPUで実行する
CPUのキャッシュによるreorderような現象

reorderはシリアルプログラムでも発生します。コンパイラーはオプションを指定すれば最適化のための並び替えを止めることができます。CPUが命令を同時実行するのは初耳ではないと思います。シリアルとパラレルプログラムの違いといえば、3番しかないです。それについて説明します。

複数CPUのあるシステムを考えましょう。複数CPU＋メインメモリー

CPUはメインメモリーをアクセスするときの遅延を考えると、CPUのキャッシュが必要になります。ここまではほとんどの方が知っていると思います。

f:id:unifa_tech:20180723172443p:plain

Symmetric multiprocessing - Wikipedia

キャッシュがあると、CPU0のキャッシュにあるaの値はCPU1から参照できないのではと考える方がいると思いますが、ハードウェアエンジニアはすでにそれを意識して、CPU間のキャッシュコヒーレンシ（Cache Coherence）プロトコルを作りました。その一つはMESIです。

MESIは4つのステータスの頭文字です。

Modified, Exclusive, Shared, Invalid

https://ja.wikipedia.org/wiki/MESI%E3%83%97%E3%83%AD%E3%83%88%E3%82%B3%E3%83%AB

MESIがある限り、メインメモリー経由せずにほかのCPUキャッシュから最新の値を取ってきたり、自分は変数の値を変えてほかのCPUを通知したりすることができます。そうすると、cpu0で書き込んだaの値はcpu1に読み取れるはずです。

が、問題はCPUとキャッシュの間に書き込みのバッファ（Store Buffer）、それにキャッシュの無効を示すInvalidate Queueがあって、結果プログラム順で実行してもあとのステートメントが先にキャッシュに書き込まれ、非同期の処理で途中で値を参照すると古い値になるかもしれない。現象としてはreorderと似てます。

CPU 0は元々変数f、CPU 1は元々変数aのキャッシュを持っているとする

CPU 0は a = 1 を実行する、自分のキャッシュにaがないのでStore Bufferに a -> 1 を追加し、MESIのread invalidateメッセージを送信する
CPU 1は while(!f); を実行する、自分のキャッシュにfがないので、MESIのreadメッセージを送信する
CPU 0は b = true を実行する、自分のキャッシュに（MもしくはE状態として）いるので、キャッシュの値を上書きする
CPU 0はCPU 1からのreadメッセージを受け、新しい値trueを返信し、キャッシュにある値をS（共有）ステータスにする
CPU 1はreadのレスポンスを受け、fの値を自分のキャッシュにインストールする
CPU 1は while(!f); を実行する、fがtrueなので、次へ進む
CPU 1は printf("%d\n", a) を実行する、自分のキャッシュにaがあるのですが、古い値0であり、結果は0になる
CPU 1はCPU 0からのread invalidateメッセージを受け、自分を持っているaを無効し、返信する
CPU 0はCPU 1からのレスポンスを受け、Store Bufferにある a = 1 をキャッシュに反映する

こうするといけないので、reorderを制御する仕組み、memory barrier(あるいはfence)が必要になります。それは次回で共有します。

いかがでしょうか。なんで並列プログラムは変な動きになるのかについて考えたことがありますか。その答えはCPUにあるかもしれません。

参考になれば幸いです。

資料

Memory Barriers: a Hardware View for Software Hackers

http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf

ユニファ開発者ブログ

ユニファ株式会社プロダクトデベロップメント本部メンバーによるブログです。

なぜ違う値を見たのかーー並列実行におけるCPUの動作

資料