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

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

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

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

1. 歴史
-----

最初にアウト・オブ・オーダー実行を行ったマシンは、1960年代のCDC 6600とされているHisa Ando。6600ではscoreboardingという手法が発明された。ライト・アフター・ライト  及びライト・アフター・リード  を解決しているが、レジスタ・リネーミングは行っていない。続いてIBM System/360 モデル91がTomasuloのアルゴリズムを導入したHisa Ando。scoreboardingとTomasuloのアルゴリズムはどちらもこの分野における基本的なアイディアである。

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

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

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

OoOではないことを特に示す意味があるだろうプロセッサには、サンのUltraSPARC、インテルとヒューレット・パッカードが共同開発したItanium、トランスメタのCrusoeなどがある。これらでは、レジスタウィンドウがレジスタリネーミングと相性が悪い、プロセッサコアの命令体系にVLIWを採用しコア外のコンパイラなどで依存や並列実行を解決している、依存関係が無い異なるスレッドの命令を並列実行することで性能を得ている、といった理由でOoOが採用されていない。

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

2. 基本的コンセプト
-----------

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

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

命令フェッチ
入力オペランドが既に用意されていれば、命令は適当な実行ユニットに割り当てられ、さもなければオペランドが用意されるまでプロセッサは命令の実行を止めて待つ。
命令が適当な実行ユニットで実行される。
実行ユニットは実行結果をレジスタファイルに返す。

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

OoOでは、命令及び実行結果を一時溜めておく場所を作り、命令の実行を次のように細分化する。

命令フェッチ。
命令にリオーダ・バッファのエントリを割り当てる。
命令を命令待ち行列または命令発行キューに送る。
命令待ち行列内の命令は、入力オペランドが得られるまで実行されない。入力オペランドが得られた段階で、待ち行列内にそれより古い命令があっても先に待ち行列から取り除かれ、実行されることになる。
命令が適当な実行ユニットに対して発行され、実行される。
実行結果がリオーダ・バッファに格納される。
リオーダ・バッファ内の命令のうち、最も古い命令の実行が完了すると、その実行結果はレジスタファイルに書き戻され、命令はリオーダ・バッファから取り除かれる。これを卒業ないしリタイアステージと呼ぶ。命令待ち行列とは異なり、より新しい命令が実行完了状態であっても、それより古い命令がリオーダ・バッファ内にリタイアせずに残っている場合は、その命令がリタイアすることはできない。OoOの鍵になるコンセプトはある命令の実行に必要なデータが得られない状態でも、プロセッサの動作を止めず他の命令を実行し続けられるようにすることである。インオーダ実行では必要なデータが全部揃わないとの段階で実行が止まってしまう。この点を改善したのがOoOである。

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

命令パイプラインが深くなり、主記憶装置に比べプロセッサが高速になる程OoOの威力は増す。例えば、現代のプロセッサはメモリの数倍の速さで動作しており、バス上にデータが乗るのを待つのは非常にサイクル数を無駄にすることになる。

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

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

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

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

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

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

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

命令の割り振りを格納する待ち行列は一本化されているのか、複数存在するのか?IBM PowerPC では複数の待ち行列を用意し、機能ユニットによって異なるものを用いたが、ほとんどは唯一の待ち行列を採用している。IBMは複数の待ち行列をreservation stationsと呼んでいる。
結果待ち行列は物理的に存在するのか、それともレジスタファイルに直接書き込まれるのか。後者の場合、レジスタ・リネーミング機能によって、つまりレジスタマップによって代替されるのではないか。初期のインテルのOoOプロセッサはRe-order Bufferという名の結果待ち行列を持っていたが、後のほとんどのOoOプロセッサはレジスタマップによる処理を用いている。

6. 脆弱性
------

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

7. 脚注
-----

8. 参考文献
-------

9. 関連項目
-------

ノイマン型
ノイマンズ・ボトルネック
レジスタ・リネーミング
投機的実行
分岐命令
VLIW
EPICアーキテクチャ
トランスピュータ
Meltdown
Spectre