アウト・オブ・オーダー実行

アウト・オブ・オーダー実行（アウト・オブ・オーダーじっこう、英: out-of-order execution）とは、高性能プロセッサにおいてクロックあたりの命令実行数（IPC）を増やし性能を向上させる手法の1つである。これは、機械語プログラム中の命令の並び順に依存せず、データなどの依存関係から見て処理可能な命令を逐次開始・実行・完了させるものである。頭文字で'OoO'または'O-o-O'と書かれることもある。「順序を守らない実行」の意である。

プロセッサの設計と実装において、命令レベルの並列性（Instruction-level parallelism; ILP）を高めることは重要な目標であり、スーパースケーラにより1サイクルあたり2命令を越えることが可能になった。しかし、フォンノイマンアーキテクチャの前提である逐次実行が、並列化を施す上での障壁となる。アウト・オブ・オーダー実行（以下、OoO）は、結果（意味）に影響を与えないことを保証しながら、可能な限り順序に従わずに実行することで、複数命令の同時実行の可能性を広げる最適化手法の1つである。

アウト・オブ・オーダー実行に対して、順序通りに実行することをイン・オーダー実行と言う。

歴史

最初にアウト・オブ・オーダー実行を行ったマシンは、1960年代のCDC 6600である^[1]。6600ではscoreboardingという手法が発明され、ライト・アフター・ライト (WAW) 及びライト・アフター・リード (WAR) を解決しているが、レジスタ・リネーミングは行っていない。続いてIBMのSystem/360 モデル91がTomasuloのアルゴリズム（データを更新する場合、共通データバスにブロードキャストする）を導入した^[1]。scoreboardingとTomasuloのアルゴリズムは、いずれもこの分野における基本的なアイディアである。

アウト・オブ・オーダー実行は、ある種のデータフロー手法とも言える。データフローマシンは1980年代のコンピュータアーキテクチャ研究の主戦場であった。この分野に関連する研究をリードしたのはYale Pattと彼の開発したHPSmシミュレータである。

現実のコンピュータでは、ゼロ除算やページフォールトといった例外が発生するが、アウト・オブ・オーダー実行中のそれらへの対処は難しい問題である。1985年のJ.E. Smith & A.R. Pleszkunの論文により、アウト・オブ・オーダー実行において例外をうまく処理する手法が示された。

最初にアウト・オブ・オーダー実行を商用化したマイクロプロセッサは1990年発表のPOWER1である。x86ではP6マイクロアーキテクチャ（Pentium Pro、1995年）およびCyrix 6x86（1995年）が最初である。他には、IBMとモトローラのPowerPC 601 (1992/1993)、富士通とHALのSparc641 (1995)、ヒューレット・パッカードのPA-8000 (1996)、MIPSのMIPS R10000 (1996)、AMD K5 (1996)、DEC Alphaの21264 (1998)などがある。

アウト・オブ・オーダー実行を特に採用しないプロセッサには、サンのUltraSPARC（SPARC T3以前の場合。富士通のSPARC64では実現）、インテルとヒューレット・パッカードが共同開発したItanium、トランスメタのCrusoeなどがある。これらのプロセッサでは、レジスタウィンドウがレジスタリネーミングと相性が悪い、プロセッサコアの命令体系にVLIWを採用しコア外のコンパイラなどで依存や並列実行を解決している、依存関係が無い異なるスレッドの命令を並列実行することで性能を向上させている、といった理由でOoOが採用されていない。

原理上、アウト・オブ・オーダー実行のためにはプロセッサの素子数が増加し電力消費が増えること、また、相互依存性が高いコードでは性能が低下することから、AtomやARMのようにアウト・オブ・オーダー機能を省略し、マルチコアとクロックの向上を組み合わせる手法が主流になっている。

基本的コンセプト

イン・オーダー実行プロセッサ

古い時代のプロセッサでは、通常次のようなステップで命令が実行された。

命令フェッチ（命令を読み込む）。
入力オペランド（計算に必要なデータ）が（例えばメモリからレジスタ上に読み込まれて）既に用意されていれば、命令は適当な実行ユニット（functional unit）に割り当てられ、さもなければオペランドが用意されるまでプロセッサは命令の実行を止めて待つ。
命令が適当な実行ユニットで実行される。
実行ユニットは実行結果をレジスタファイルに返す。

アウト・オブ・オーダー実行プロセッサ

OoO（アウト・オブ・オーダー）では、命令及び実行結果を一時的に溜めておく場所を作り、命令の実行を次のように細分化する。

命令フェッチ。
命令にリオーダ・バッファ（reorder buffer）のエントリを割り当てる。
命令を命令待ち行列または命令発行キュー（reservation station, issue queue）に送る（dispatch）。
命令待ち行列内の命令は、入力オペランドが得られるまで実行されない。入力オペランドが得られた段階で、待ち行列内にそれより古い命令があっても先に待ち行列から取り除かれ、実行されることになる。
命令が適当な実行ユニットに対して発行（issue）され、実行される。
実行結果がリオーダ・バッファに格納される。
リオーダ・バッファ内の命令のうち、最も古い命令の実行が完了すると、その実行結果はレジスタファイルに書き戻され、命令はリオーダ・バッファから取り除かれる。これを卒業（graduation）ないしリタイア（retire）ステージと呼ぶ。命令待ち行列とは異なり、より新しい命令が実行完了状態であっても、それより古い命令がリオーダ・バッファ内にリタイアせずに残っている場合は、その（より新しい）命令がリタイアすることはできない。

OoOの鍵となるコンセプトは、ある命令の実行に必要なデータが得られない状態でも、プロセッサの動作を止めずに他の命令を実行し続けることである。イン・オーダー実行では必要なデータが全部揃わないと（2）の段階で実行が止まってしまう。この点を改善したのがOoOである。

OoOプロセッサはこの「空き時間」を他の「準備ができている」命令に当て、後にリタイアステージで実行結果をレジスタファイルに反映させる順序を修正することで、順序通り命令を実行したのと同じ結果が得られるようにする。本来のプログラムコードに書かれた命令の順序は「プログラム順」（program order）と呼ばれるが、この種のプロセッサの内部では「データ順」（data order）で扱われる。つまり、データないしオペランドがプロセッサのレジスタに用意される順序である。これら二種類の順序間の変換を行い、同時に出力に論理的な整合性を持たせるためには相当複雑な回路が必要である。プロセッサはまるでランダムな順序で命令を実行するように見える。

命令パイプラインが深くなり、主記憶装置（あるいはキャッシュメモリ）に比べプロセッサが高速になるほど、OoOの威力は増す。例えば、現代のプロセッサはメモリの数倍の速さで動作しており（＝メモリを読み書きするのに多くのサイクル数を必要とする）、バス上にデータが乗るのを待つのは非常にサイクル数を無駄にすることになる。

→「フォン・ノイマン・ボトルネック」を参照

デコードと発行の分離によって、順序通りでない発行が可能になった

OoOパラダイムによってもたらされた違いの一つに、待ち行列を用意することによって、命令をデコードし実行ユニットに割り振るステップ(dispatch step)と実際に命令を発行するステップ(issue step)とを分離することができ、同時に、卒業ステージと実行ステージとを分離することができる点がある。インオーダー時代のプロセッサではこれらはパイプラインによって完全に一体化していた。OoOではこれらを分離することができ、このパラダイムは以前は「分離アーキテクチャ」(decoupled architecture)と呼ばれていた。

偽のオペランド依存性（本当は必要でないのに、特定のオペランドが要求されているように見えること）は順序通りでない命令の発行をさまたげ得る。これを避けるために、レジスタ・リネーミングという技法が用いられる。このスキームでは、アーキテクチャ上のレジスタ数より実際の（物理的）レジスタ数の方が多い。複数の物理的なレジスタに同一の（アーキテクチャ上の）レジスタ名を割り当てることで、同じ名前で異なったヴァージョンのレジスタが複数個同時に存在するようにみせかけることができる。

処理の実行と結果の書き込みを分離することで、プログラムの再起動が可能になった

実行結果を格納する待ち行列は分岐予想が外れた時及び例外/トラップの処理の際発生する問題を解決するために必須である。例外が起きた場合はプログラム順で命令が実行されることが必要になるが、結果待ち行列があるおかげで、例外を起こした後でも当該プログラムを再実行することができる。以前実行した分岐命令の予測が失敗した際や、例外が発生した際は、この待ち行列から（まだ書き込まれていない段階で）ゴミになってしまった結果を削除することができる。

分岐をまたいだ命令の発行は現在も未解決の問題で、投機的実行という名で知られる。

選択されるマイクロアーキテクチャ

命令の割り振りを格納する待ち行列は一本化されているのか、複数存在するのか?

IBM PowerPC では複数の待ち行列を用意し、機能ユニットによって異なるものを用いたが、ほとんどは唯一の待ち行列を採用している。IBMは複数の待ち行列をreservation stationsと呼んでいる。

結果待ち行列は物理的に存在するのか、それともレジスタファイルに直接書き込まれるのか。後者の場合、レジスタ・リネーミング機能によって、つまりレジスタマップ（アーキテクチャ上レジスタ名、実際の物理レジスタ番号、そのレジスタを使う（予定）の命令の組を管理する表）によって代替されるのではないか。

初期のインテルのOoOプロセッサはRe-order Bufferという名の結果待ち行列を持っていたが、後のほとんどのOoOプロセッサはレジスタマップによる処理を用いている。

脆弱性

O-o-Oの手法に起因した、MeltdownやSpectreといった脆弱性が2018年1月に発表され、業界に衝撃を与えたた^[2]。

脚注

[脚注の使い方]

^ ^a ^b Hisa Ando 2011, p. 86.
^ Bright, Peter (January 5, 2018). “Meltdown and Spectre: Here's what Intel, Apple, Microsoft, others are doing about it”. Ars Technica. January 6, 2018閲覧。

参考文献

Hisa Ando『プロセッサを支える技術 : 果てしなくスピードを追求する世界』技術評論社、2011年1月25日。ISBN 978-4-7741-4521-1。

歴史