メモリアクセスのセマンティクスとApple siliconの裏技(?)について

アウト・オブ・オーダー実行について補足

前回の記事で「アウト・オブ・オーダー実行」について特に説明せずに話を進めてしまったことに気づいたので、まずはそれについて簡単に補足しておこう。

コンピューターの性能向上の歴史はレイテンシーとの戦いの歴史でもある。

colin-scott.github.io

上のサイトは年代毎にコンピューターシステムでの各種レイテンシーがどのように変化していったかを紹介している。1990年代前半はキャッシュメモリとメインメモリとの間のレイテンシー差はそれほど大きくなかったが、その後の技術革新によって現在はL1キャッシュとメインメモリとの間に100倍くらいのレイテンシー差があるようになってしまった。これはつまり、プログラム実行中にメインメモリへのアクセスが発生してしまうと、それだけ長いレイテンシーの間CPUの処理を進めることができなくなってしまうことを意味する。そのため、このメインメモリへのアクセスの遅さをいかにカバーするかというのがCPUの性能向上における大きなテーマとなっている。

アウト・オブ・オーダー実行もそのための技術の一つで、プログラムコード上の命令列の順序に依らずメモリアクセスの準備が整った命令から実行することで、メインメモリへのアクセス待ちのためにCPUが遊んでしまうような状況を減らす、というものである。

ただし「プログラム上の順序に依らない実行」といっても、意味が変わってしまうようなものはもちろん認められない。例えば以下のようなコードを考えてみよう。

int a = 0;
int b = 0;
int c = 0;

CPU1:
  a = 1;
  b = 2;
  c = a + b;

ここで b = 2; の書き込みだけ後回しにして最終的に c == 1 になってしまうようでは当然ダメである。しかし一方で、最終的に a == 1 && b == 2 && c == 3 になるのであれば、変数a, b, cそれぞれへの書き込みはどのような順序で行われても構わない、という点が重要である。 c = a + b; の右辺が3になることは変数a, bのメモリアドレスへ実際にアクセスしなくてもわかる(このような技術をBypassあるいはForwardingと呼ぶ)ので、例えば変数bへのアクセスが大幅に遅れてしまったとしても変数cへの書き込みは先に完了させられる、といったことができるようになる。

メモリアクセスの「セマンティクス」

さて、メモリモデルの話に戻ろう。前回の記事で

デフォルトでは「強いメモリモデル」を提供せずにもっと緩い条件を認める一方、一部のマルチスレッドプログラム用にメモリアクセスの順序を明示的に指定するための機械語命令を用意したアーキテクチャ

という話をしたが、ここで言う「もっと緩い条件」や「メモリアクセスの順序を明示的に指定する」とは具体的にどんなことだろうか? 同じ「弱いメモリモデル」のアーキテクチャだとされるARMとPowerPCとの間でもメモリアクセスの仕様については大きく差があるし、「どの命令を使用するとメモリアクセスの順序をどう指定できるか」というのはそれこそ各CPUの詳細なドキュメントを個別に読み解かなければならないような話である。

だからといって、メモリアクセスの挙動を理解してプログラムコードを書くには各CPUアーキテクチャの細かな仕様を把握する必要があるというのでは無理がある。そこで、「プログラムコードを書く側が期待する挙動」に着目して、メモリアクセスの順序についてCPU(やコンパイラ)が満たすべき抽象的なルールを何種類かに分類して定義するということが行われた。分類されたメモリアクセスの挙動は、それぞれが満たすべきルールを持つ「セマンティクス」として表される。大きく3つに分けることができるこの「メモリアクセスのセマンティクス」とは以下のようなものである。

Relaxedセマンティック
Release/Acquireセマンティック
Sequentially consistent (SeqCst)セマンティック

それぞれについて説明していこう。

Relaxedセマンティック

Relaxedセマンティックが満たすべきルールは以下の2つである。

あるCPU(スレッド)が行うメモリアクセスは、同じCPU(スレッド)からはプログラム上の順序と矛盾しないように見えなければならない。
同じメモリアドレスに対するアクセスは全てのCPU(スレッド)間で同一の順序として観測される。

1つめのルールは先程アウト・オブ・オーダー実行について述べたことと同じである。つまり、同一CPU(スレッド)から見た結果が変わらない限りにおいては、実際のメモリアクセスの順序を変えてもよいことを意味している。

2つめのルールはキャッシュコヒーレンシに関するものである。現代のマルチプロセッサシステムではキャッシュコヒーレンシという仕組みにより、同じメモリアドレスに対するアクセスが一貫性を持つように制御されている。CPUがあるアドレスに書き込みを行う場合、同じアドレスに対する他のCPU上のキャッシュをinvalidateする、といった制御が自動的に行われているのである。Relaxedセマンティックもそのような仕組みが存在することを想定しているので、同一アドレスに対するアクセス順序は常に一貫性を持つと決められている。

ただしこのルールは裏を返すと、「異なるCPU(スレッド)間において異なるメモリアドレスに対するアクセスが観測される順序は基本的に不定であり、またその順序はCPU(スレッド)間で一貫性が保たれていなくてもよい」ということを意味している。すなわち、異なるメモリアドレスに対するアウト・オブ・オーダー実行については特に制限しない、ということになる。

このように、Relaxedセマンティックでは現代のマルチプロセッサシステムが持つべき最低限のルールだけを定義しており、そのルールを満たす限りにおいて、アウト・オブ・オーダー実行などの最適化を最大限に認めている。その点では、Relaxedセマンティックは最もオーバーヘッドの少ないセマンティックと言うことができる。

Release/Acquireセマンティック

Release/Acquireセマンティックとは、メモリへの書き込み(ストア)アクセスに付随するReleaseセマンティックと読み込み(ロード)アクセスに付随するAcquireセマンティックの総称である。Release/Acquireセマンティックが満たすべきルールは、Relaxedセマンティックが持つ2つのルールに以下を加えたものになる。

あるCPU(スレッド)がReleaseセマンティックで書き込んだ値を別のCPU(スレッド)がAcquireセマンティックで読み込んだ場合、「Releaseセマンティックの書き込みよりもプログラム順で前にある全てのメモリアクセス(セマンティクスは問わない)」と「Acquireセマンティックの読み込みよりもプログラム順で後にある全てのメモリアクセス(セマンティクスは問わない)」の間で前後関係が強制される。

文章だとわかりにくいので具体的な例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  a = 1;  // Relaxedセマンティック
  b = 1;  // Releaseセマンティック

CPU2:
  int r1 = b;  // Acquireセマンティック
  int r2 = a;  // Relaxedセマンティック

// 変数aへのアクセスはRelaxedセマンティック、
// 変数bへのアクセスはRelease/Acquireセマンティックで行われるとする。
// このとき、 "r1 == 1 && r2 == 0" という結果は起こり得ない。

r1 == 1 だと仮定したときに変数bへの読み書きに注目すると、これはCPU1が b = 1; で書き込んだ値をCPU2が int r1 = b; で読み込んだことを意味する。ここでRelease/Acquireセマンティックのルールを適用すると、「b = 1; よりもプログラム順で前にある a = 1;」と「int r1 = b; よりもプログラム順で後にある int r2 = a;」の間で前後関係が強制される、すなわち「a = 1; は int r2 = a; よりも前である」ことが決まる。故にこの場合は r2 == 1 でなければならないと結論づけられるのである。

別の例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  int r2 = a;  // Relaxedセマンティック
  b = 1;  // Releaseセマンティック

CPU2:
  int r1 = b;  // Acquireセマンティック
  a = 1;  // Relaxedセマンティック

// 変数aへのアクセスはRelaxedセマンティック、
// 変数bへのアクセスはRelease/Acquireセマンティックで行われるとする。
// このとき、 "r1 == 1 && r2 == 1" という結果は起こり得ない。

先程と同様に r1 == 1 と仮定して変数bへの読み書きに注目すると、CPU1が b = 1; で書き込んだ値をCPU2が int r1 = b; で読み込んでいることになる。ここでRelease/Acquireセマンティックのルールを適用すると、「b = 1; よりもプログラム順で前にある int r2 = a;」と「int r1 = b; よりもプログラム順で後にある a = 1;」の間で前後関係が強制される、すなわち「int r2 = a; は a = 1; よりも前である」ことが決まる。故にこの場合は r2 == 0 でなければならないと結論づけられるのである。

Release/Acquireセマンティックを用いることで、異なるCPU間で観測されるメモリアクセスの順序について制限をかけることができる。Mutexのような排他制御を行うライブラリは、異なるCPU(スレッド)がそれぞれのクリティカルセクション内で行った操作の順序付けを保証するためにRelease/Acquireセマンティックを内部で使用している。また、Channelのようなスレッド間でデータをやり取りするためのライブラリも、送信側が書き込んだ内容が確実に受信側から見えることを保証するためにRelease/Acquireセマンティックを内部で使用している。

このようにRelease/Acquireセマンティックは特にスレッドライブラリにおいて重要な仕組みとなるが、一方でこのセマンティックの使用によりアウト・オブ・オーダー実行などの最適化にはある程度の制限がかかることになる。この点で、Release/AcquireセマンティックはRelaxedセマンティックよりもオーバーヘッドが大きいと考えることができる。

Sequentially consistent (SeqCst)セマンティック

Sequentially consistent (SeqCst)セマンティックとは、Release/Acquireセマンティックまでの全てのルールに加えて以下のルールを持つものである。

Sequentially consistent (SeqCst)セマンティックを持つ全てのメモリアクセスは、全てのCPU(スレッド)の間で逐次一貫性(sequential consistency)を持たなければならない。

これも具体的な例を挙げよう。

int a = 0;
int b = 0;

CPU1:
  a = 1;  // SeqCstセマンティック
  int r1 = b;  // SeqCstセマンティック

CPU2:
  b = 1;  // SeqCstセマンティック
  int r2 = a;  // SeqCstセマンティック

// 変数a, bへのアクセスは全てSeqCstセマンティックで行われるとする。
// このとき、 "r1 == 0 && r2 == 0" という結果は起こり得ない。

もしこのコードで "r1 == 0 && r2 == 0" という結果が得られたとすると、実際に変数a, bへの読み書きが行われた順序としてプログラムコードと矛盾しない一貫性のある順序を示すことができないことがわかるだろうか。このように、異なるCPU(スレッド)間の異なるメモリアドレスに対するアクセスの順序も一貫性を持つことを要求するのがSeqCstセマンティックである。

一方で、このサンプルコードにおいてSeqCstセマンティックの代わりにRelease/Acquireセマンティックを用いた場合は、 "r1 == 0 && r2 == 0" が起こり得ないことを保証できない点にも注意してもらいたい。Release/Acquireセマンティックのルールは「あるCPUが書き込んだ値を別のCPUが読み込んだとき」に適用可能であって、この例のようにどちらのCPUも他方のCPUが書き込んだ値を読み込んでいない場合には適用できないのである。

SeqCstセマンティックの持つ強い一貫性はプログラムを書く側からするとわかりやすいルールではあるが、CPU側からすると「先行する書き込みの内容が確実に他CPUから見えるようになる(globally visible)まで後続の処理を進めることができない」という制限になる。これはパイプライン処理の観点からすると非常に大きなペナルティとなるため、実行コストはRelease/Acquireセマンティックよりも更に大きくなる。すなわち、SeqCstセマンティックはRelease/Acquireセマンティックよりも更にオーバーヘッドが大きいと言うことができる。

x86-64メモリモデルの分析

さて、これまで述べてきた3つのセマンティクスをそれぞれのオーバーヘッドとともに再掲しよう。

Relaxedセマンティック (オーバーヘッド無)
Release/Acquireセマンティック (オーバーヘッド小〜中)
Sequentially consistent (SeqCst)セマンティック (オーバーヘッド大)

これらのセマンティクスを持つメモリアクセスを実際にx86-64 アーキテクチャ上で行うにはどうすればよいか考えてみよう。

前回の記事で述べたように、x86-64 アーキテクチャで複数のメモリアドレスに対する書き込みと読み込みの順序はそれぞれ「他のCPUから変更が見えるようになる(globally visible)順序」と矛盾しないようになっている。これは、x86-64のメモリアクセスがデフォルトでRelease/Acquireセマンティックを持っていることを意味する。つまり、Release/Acquireセマンティックを必要とするメモリアクセスをx86-64の機械語命令にコンパイルする際は、x86-64の通常のストア・ロード命令である MOV 命令を使用すればよい、ということになる。

この MOV 命令は、Relaxedセマンティックのメモリアクセスに対しても使用することができる。これはRelaxedセマンティックとRelease/Acquireセマンティックの関係から明らかである。

一方で、この MOV 命令はそれ単体ではSeqCstセマンティックを満たさない。x86-64でSeqCstセマンティックを満たすためには、ストア命令として XCHG 命令を使用するか MOV と MFENCE の2命令を続けて使用する必要がある。

といったことが以下のサイトに書かれてある。

www.cl.cam.ac.uk

このように、CPUのストア・ロード命令がどのようなセマンティクスを持つか調べることにより、プログラムコードに必要とされるセマンティクスを満たすにはどの命令を使用すれば良いのかがわかるのである。

ARM(AArch64)メモリモデルの分析

同様にしてARMの64bitアーキテクチャ(AArch64)についてもメモリモデルのセマンティクスを調べてみよう。といっても先程の "C/C++11 mappings" のページを下にスクロールすれば答えは書いてある。

AArch64の通常のストア・ロード命令 STR/LDR はRelaxedセマンティックを持っている。

Release/Acquireセマンティックが必要なところは STR/LDR 命令では不十分なので、代わりに STLR/LDAR 命令を使用する。

興味深いのはSeqCstセマンティックについてで、それに対しても単体の STLR/LDAR 命令だけで十分だとされている。つまり、AArch64の STLR/LDAR 命令は実際はSeqCstセマンティックを持っているということになる。

AArch64がRelease/AcquireセマンティックとSeqCstセマンティックのために別々の命令を用意しなかった理由については良くわからない。しかし、先程の "C/C++11 mappings" のページはARMのエンジニアのレビューも受けているようなので、書いてある内容が間違っているわけではなさそうである。

Rosetta2によるストア・ロード命令の変換

さて、これでようやくRosetta2の話をする準備が整った。

Rosetta2とはx86-64のバイナリをAArch64のバイナリに変換して実行してくれるツールである。この変換において、プログラムコードの多くの部分で使われるストア・ロード命令をどのようにマッピングするかが、変換後のバイナリの動作に大きく影響することは容易に想像がつくだろう。

仮にx86-64の MOV 命令をAArch64の STR/LDR 命令にマッピングするように変換したとしよう。元のプログラムコードが MOV 命令をRelaxedセマンティックのつもりで使用していたなら、変換後のバイナリも正しく動作する。しかし、元のコードが MOV 命令をRelease/Acquireセマンティックが必要な場所で使用していたとすると、STR/LDR 命令はそのセマンティックを満たさないために誤動作する可能性がある。具体的には、マルチスレッドのコードで他スレッドの予期せぬ値を読み取ってしまってクラッシュするなどの不具合が考えられる。

つまり、x86-64のバイナリを見るだけでは MOV 命令がRelaxedとRelease/Acquireのどちらのセマンティックで用いられているかは判断できないので、安全側に倒して全てRelease/Acquireセマンティックだと仮定して変換する必要がある、ということになる。そうすると、x86-64バイナリの MOV 命令は全てAArch64の STLR/LDAR 命令に変換しなければならなくなるが、これだと今度はパフォーマンス上の問題が出てくる。

前節で述べたように、AArch64の STLR/LDAR 命令は実際にはSeqCstセマンティックを持っている。よってこれを MOV 命令の変換先として用いてしまうと、SeqCstセマンティックのオーバーヘッドの大きさのために、変換後のバイナリの実行速度はかなり遅くなってしまうだろう。

Apple silicon のTSOモード(?)

さて、このx86-64とAArch64との間のセマンティクスのギャップによる問題に対して、Appleのエンジニアはとんでもない裏技を使ったようである。

github.com

TSO (Total Store Ordering) とは、デフォルトのストア・ロード命令がRelease/Acquireセマンティックを持つようになるメモリモデル、つまりx86-64と同等のメモリモデルのことである。Apple siliconにはメモリモデルをこのTSOに変更するモードが搭載されており、Rosetta2はこれを使用しているとのことである。

つまり、Rosetta2はx86-64の MOV 命令をAArch64の STR/LDR 命令に変換し、その変換後のバイナリを上記のTSOモードを有効にしたプロセスとして実行しているということである。このTSOモードにおいては STR/LDR 命令もRelease/Acquireセマンティックで動作するので、Relaxedセマンティックによる不具合も発生せず、またSeqCstセマンティックによるパフォーマンス劣化も起こさないということになる。

このTSOモード(?)というのは少なくとも現時点ではARMの正式な仕様として定義されているものではないようなので、AppleがM1プロセッサだけに搭載した特別なカスタマイズということになる。まさに裏技というしかない。

さて、また長くなってしまったので今回はここまで。次回は参照カウントについての話をしよう。