2020/03/21

アウト・オブ・オーダー実行に気を付けよう

現代のアーキテクチャのコンピュータでマルチスレッド・プログラミングをする場合には、アウト・オブ・オーダー実行のことを理解しておく必要があります。
プログラマの皆さんは、「プログラムは思った通りに動くのではない。書いた通りに動くのだ。」と教わってきたと思いますが、イマドキのコンピュータでは、書いた通りには動いていません。
アウト・オブ・オーダー実行について、しっかり理解しておきましょう。

アウト・オブ・オーダー実行とは？

現代のコンピュータの CPU には、アウト・オブ・オーダー実行 (OoO) という機能が実装されています。アウト・オブ・オーダー実行とは、命令を記述されている順序通りに実行せず、効率向上のために実行順序を入れ替えるという CPU 内の最適化機構のことです。実行順序を入れ替えることによって CPU の実行ユニットの稼働率を上げられる場合、入れ替えを実行します。そうすることによって全体として性能が向上することになります。
ちなみに、アウト・オブ・オーダー実行の反対語は、イン・オーダー実行 (書かれた通りに逐次実行) です。

なぜ実行順序を入れ替えるだけで性能が向上するの？

なぜ、実行順序を入れ替えることで性能が向上するのでしょうか？ 理由は大きく分けて2つあります。

  1. 命令パイプライン効率化
  2. メインメモリと CPU の速度差による待ち時間の効率化

命令パイプラインの効率化


現代の CPU は多段の命令パイプラインを持っています。Intel x86 系 CPU であれば、だいたい14〜20段のパイプラインになっています。
命令パイプラインというのは、1つの命令の解釈から実行におけるステップを細かく分割して、複数の命令の処理を並行して進めていけるようにした仕組みです。CPU 内部の機構を有効活用するための重要な仕組みです。
命令パイプラインは、命令の実行が完了する前に次に実行すべき命令を決めなければ、性能に寄与しません。そこで、アウト・オブ・オーダー実行が用いられます。例えば命令Aの結果を後続の命令Bがインプットとして使うという場合、命令Aの完了まで命令Bの処理をスタートできません。しかし、その後ろに命令Cがあって、命令Aや命令Bの結果を必要としていなければ、先に実行しても差し支えないはずです。このときに、命令Bより先に命令Cをパイプラインに載せてしまいます。こうすることで、パイプラインの利用効率が向上し、全体として性能が向上することになります。

メインメモリと CPU の速度差による待ち時間の効率化

現代のコンピュータ・アーキテクチャでは、メインメモリに比べて CPU のクロックが数倍高くなっています。そのため、メインメモリにアクセスする命令は、何クロックも待ちを生じます。
この間、実行しておける命令を実行するために、やはりアウト・オブ・オーダー実行が機能します。

アウト・オブ・オーダー実行で何が起きるか？

アウト・オブ・オーダー実行では、スレッド内のセマンティクスを壊さないように命令をリオーダー (順序変更) します。例えば、以下のようなコードがあったとします。
a := 1 + 2;
b := 3 + 4;
c := a + b;

アウト・オブ・オーダー実行が行われる環境では、1行目と2行目のどちらが先に行われるかは分かりません。3行目は、1行目、2行目の結果を使用するので、1行目、2行目共に完了してから実行されます。

しかし、アウト・オブ・オーダー実行は、スレッド間のセマンティクスについては注意を払いません。例えば、以下のような処理を行わせたいとしましょう。

  1. 子スレッド1: flag が true になるまでループして待ち、true になったら x の値を表示する
  2. 子スレッド2: x に値をセットした後、flag を true にする

そこで、以下のようなコードを書きます。

子スレッド1:
LOOP:
  if flag is false, then goto LOOP;
print x;

子スレッド2:
x := 100;
flag := true;

イン・オーダー実行では、子スレッド2が x に値をセットした後に flag を true にするという記述通りの順序で動作するため、期待した動作をします。
しかし、アウト・オブ・オーダー実行では、子スレッド2の1行目と2行目がリオーダーされる可能性があります。この実行順序は子スレッド2の内部のセマンティクスに影響しないためです。しかし子スレッド1は、子スレッド2がリオーダーされてしまうと、x に値がセットされる前にループを抜けてしまうことになり、期待した動作をしなくなってしまいます。
これを回避するためには、x と flag の更新がアトミックに行われるよう同期処理を入れる等の対策が必要となります。

アウト・オブ・オーダー実行は、コンピュータの性能を向上させるためにとても大事な機構ですが、マルチスレッドでは予期しない結果を招くことがあるので、マルチスレッド・プログラミングをする際には、よく注意しておきましょう。