RISC-Vも含め、コンピュータアーキテクチャでなかなか分かりにくい領域にメモリコンシステンシモデルモデルというものがある。メモリコンシステンシモデルとは何か？なぜ議論が必要なのか？メモリコンシステンシモデルをテストするリトマステストとは何なのか？理解ができていない部分がたくさんあるので、これを機に勉強してみることにした。
参考にしたのは、Memory Consistency Models, and how to compare them automatically というブログ。彼らは論文も出しているようだが、最初のイントロダクションが結構わかりやすかった。日本語でリトマステストについて纏めている資料はあまり存在しないので、勉強して自分の言葉に書き下してみる。
Memory Consistency Models, and how to compare them automaticallyjohnwickerson.wordpress.com
メモリコンシステンシモデルというのは、マルチプロセッサ環境においてメモリアクセスの順序を定義するもので、例を出してもなかなか難しい話なのだが、たとえばx86のコンピュータにおいて
- あるメモリ領域XにCPU0がデータを書きだす。
- 即時にあるメモリ領域XからCPU1がデータを読み出す。
普通に考えると、CPU0の書き出したデータはメモリに書き込まれ、次に実行されるCPU1のロード命令によってデータが読み込まれるので問題なくCPU0のデータがCPU1に読み込まれるるように思える。このようなプログラミンモデルを、「逐次一貫性モデル＝シーケンシャルコンシステンシ＝Sequential Consistency」と呼んでいる。
シーケンシャルコンシステンシの定義を調べてみると「並列プログラミングにおける一貫性モデルの一種。どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定されたとおりであること」と定義されている。
シーケンシャルコンシステンシの意味を理解するために少し簡単な例を出してみる。以下のプログラムは、1行目が初期値、2行目以降の左側はCPU0が実行するプログラム、右側はCPU1が実行するプログラムだと考えてほしい。
x = 0, y = 0 x = 1; || y = 1; r0 = y; || r1 = x;
r0, r1はレジスタだと思ってもらって問題ない。xとyはメモリアクセスで、つまり1行目はメモリに対するストア動作、2行目はメモリからのロード動作と言うことになる。 では、この結果r0とr1はどのような結果になるだろうか。以下のケースが考えられるのが普通だろう。
- 実行順序 "x = 1" --> "y = 1" --> "r0 = y" --> "r1 = x" : 結果は r0 = 1, r1 = 1となる。
- 実行順序 "x = 1" --> "r0 = y" --> "y = 1" --> "r1 = x" : 結果は r0 = 0, r1 = 1となる。
- 実行順序 "y = 1" --> "x = 1" --> "r0 = y" --> "r1 = x" : 結果は r0 = 1, r1 = 1となる。
- 実行順序 "y = 1" --> "r1 = x" --> "x = 1" --> "r0 = y" : 結果は r0 = 1, r1 = 0となる。
つまり、普通に考えて3種類の結果が得られる。このようにシーケンシャルコンシステンシでは、「ある処理は一瞬で実行され、システムに即時適用される」というように考えて良い。
しかし、驚いたことにx86ではこれ以外の結果が得られることがある。それはつまりr0 = 0, r1 = 0という結果だ。「最初にストアしたはずなのに隣のCPUから読み取れないの？」と思うかもしれないが、それはx86のCPUにはライトバッファというものが入っており、書きだしたデータを他のCPUから即時読めるわけではないからだ。
という訳で、理想と思われるシーケンシャルコンシステンシも実際にはなかなか実現不可能で、ハードウェアとしてマルチコアの動作を考えるときにもう少し緩い制限を持たせても良いのではないか、ということでいろんなメモリコンシステンシモデルが考えられている。
もう少しメモリアクセスの制限を緩くして考えてみることにする。シーケンシャルコンシステンシにおいて上記のモデルでは3種類の結果が得られると考えたが、頭を柔らかくしてもう少し制限を緩めてみよう。実際には4種類の結果が考えられる。
- CPU0 :
y = 1, CPU1 :x = 1 - CPU0 :
y = 0, CPU1 :x = 1 - CPU0 :
y = 1, CPU1 :x = 0 - CPU0 :
y = 0, CPU1 :x = 0
これらの結果が実際にはどのような経緯で発生しているのか、図で表してみよう。
省略語がたくさん出てきた。
点線で囲んでいるのは各スレッドを意味する。ここでは2つのスレッドが実行されている。
W x = 1というのはメモリ領域xに対する1の書き込み。W y = 1も同様。R y = 0というのはメモリ領域yからデータを読み込んで結果が0であったことを意味する。R x = 1も同様。sbという矢印はsequenced beforeという意味で、このプログラムはこの矢印の順番に実行されているということを示している。つまり、一番上のケースだとW x = 1が順番に実行され、R y = 1が次に実行されたということを意味する。rfという赤い矢印はread fromを意味し、メモリ領域に対する操作がこの順番で実行されたということを意味する。一番上の例であれば、W x = 1の操作がメモリに適用されてからR x = 1というメモリ操作が適用されたことを意味する。- 一方で
frという青い矢印はrfの逆で、from readとなり逆依存が発生してしまったことを意味する。上記の2番目の例だとR y = 0が先にメモリに対して適用されてしまい、その結果W x = 1が後に適用されたことを意味する。
この4種類の動作順序の候補に対して、次にメモリコンシステンシのルールに基づいて不可能な操作を除去していく。たとえば、シーケンシャルコンシステンシでは以下の制約があり、
- sbとfrによるループの形成
つまり一番下の動作は禁止されているということを意味する。したがってシーケンシャルコンシステンシでは4番目の動作はあり得ないということになる。
もう一つ、C言語の動作について見ておく。C言語やOpenGLなどにおいて、プログラムのコンシステンシの中にデータレース（あるCPUがあるメモリ領域からデータを読み取っている時、同時に別のCPUが同じメモリ領域にデータを書き込んでいる状態）が発生した場合、すべての実行が許可されるという状態になる。つまり、何が起きてもおかしくないという状態になってしまうのだ。
ここでは特殊な動作が混じっている。RELEASEと書かれたストア動作には、メモリ領域yに対するアクセス権限をすでに確保した状態であり、yに1をストアすると同時にその権限をリリースするということを意味する。同時に、AQQUIREと書かれた右のスレッドの動作では、メモリ領域yのアクセス権限取得を試みながら、yの値を読み込んでr0に書き込むという動作になる。これらにおいて可能性載る動作モデルをすべて書き下すと以下のようなる。
なんだか記号が多くなりすぎて難しくなってきたので1つずつ見ていきたい。まずは1番上のモデル。すべての依存がfrの逆依存になっており、yへの書き込み順序も逆になっており右側のスレッドでy=0が見えている（つまりメモリ領域yの操作において右側のスレッドが先にアクセスを行い権限取得に失敗したことを意味する）。yの同期に失敗してしまったため、スレッド間において順序を制御するものが何もなくなってしまい、xの読み込みでデータレースが発生してしまっている。つまり、矛盾していると考えられる動作ですら、そのような状態が発生してしまうということである。
2番目のモデルも同様にfrの逆依存になっており、yの書き込み順序が逆にメモリ領域yの操作において右側のスレッドが先にアクセスをおコアに権限取得に失敗したことを意味する。yの同期に失敗いてしまったが、xの動作には一貫性が取れている。つまり左側のスレッドで書き込んだxの値が右側のスレッドで読み取ることができている。この状況ではデータレースは発生していない。
3番目のモデルはyの権限取得に成功したケースだ。左側のスレッドのyの書き込みと権限開放が先に行われ、右側のスレッドが解放された権限の取得に成功している。従って右側のスレッドではyの値として1が見えている。しかし問題なのはこのケースではxの値に逆依存が発生してしまった。yに対するRELEASE → ACQUIREの動作において、RELEASEの前に実行されるメモリ操作はすべて完了されることが保証されているのに、xの値が読み取れていない。つまりこのxの読み取り動作には矛盾が発生していることを意味する。
4番目のモデルはすべてがうまく行ったケースだ。RELEASE → ACQUIREの権限取得に成功し、yの値が正しく左のスレッドから右のスレッドに見えている。そしてRELEASE → ACQUIREの順序保障に従って、左側のスレッドの書き出したxの値が右側のスレッドで正しく見えている。これはすべてがうまく行った場合のケースとなる。
メモリコンシステンシを比較しなければならない理由とは？
- プログラミング言語のメモリコンシステンシモデルは常に進化している。C言語のメモリコンシステンシは常に修正が加えられ、新しいものに進化している。これらを比較し、どのように変更されているのかを調査するのは、より良いプログラムを書くにあたり重要である。
- コンパイラレベルでのメモリコンシステンシモデルと、ハードウェアレベルでのメモリコンシステンシを比較することによってコンパイラのバグを発見できる可能性がある。ハードウェアとして許されているコンシステンシモデルでも、ソフトウェア（＝コンパイラ）により許可されていない場合それはバグとなりうる可能性がある。これらのバグは一般的なテストで発見することは難しく、これらの特殊なテストパタンによってテストされる必要性がある。現在でもこれらのバグが見つかることは珍しくない。
- コンパイラによる最適化の問題を防ぐ。例えばコンパイラによる最適化の段階で許されないメモリコンシステンシの問題を埋め込んでしまった場合、それはコンパイラのバグと考えるべきである。しかしこれらの最適化バグは通常のテストで発見することは難しく、メモリコンシステンシモデルを比較することによって検査されなければならない。
