アウト・オブ・オーダー実行（-じっこう、）とは、高性能プロセッサにおいてクロックあたりの命令実行数（IPC値）を増やし性能を上げるための手法の1つで、機械語プログラム中の命令の並び順に依らず、データなどの依存関係から見て処理可能な命令について逐次開始・実行・完了させるものである。頭文字で'OoO'あるいは'O-o-O'とも書かれる。「順序を守らない実行」の意である。プロセッサの設計と実装において、命令レベルの並列性（"Instruction-level parallelism"; ILP）を高めることは1つの目標でありスーパースケーラにより1サイクルあたり2命令を越えることが可能になったが、フォンノイマンアーキテクチャの前提である逐次実行が、並列化を施す上での障壁となる。アウト・オブ・オーダー実行（以下、OoO）は、結果（意味）に影響を与えないことを保証しながら可能な限り順序に従わずどんどん実行することにより、複数命令の同時実行の可能性を広げる最適化手法の1つである。アウト・オブ・オーダー実行に対して、順序通り実行することを、イン・オーダー実行と言う。最初にアウト・オブ・オーダー実行を行ったマシンは、1960年代のCDC 6600とされている。6600ではscoreboardingという手法が発明された。ライト・アフター・ライト (WAW) 及びライト・アフター・リード (WAR) を解決しているが、レジスタ・リネーミングは行っていない。続いてIBM System/360 モデル91がTomasuloのアルゴリズム（データを更新する場合、共通データバスにブロードキャストする）を導入した。scoreboardingとTomasuloのアルゴリズムはどちらもこの分野における基本的なアイディアである。アウト・オブ・オーダー実行はある種のデータフロー手法とも言える。データフローマシンは1980年代のコンピュータアーキテクチャー研究の主戦場であった。1980年代にこの分野に関連する研究をリードしたのはYale Pattと彼の開発になるHPSmシミュレータであった。現実のコンピュータでは、ゼロ除算やページフォールトといった例外が発生するが、アウト・オブ・オーダー実行中のそれらへの対処は頭の痛い問題である。1985年のJ.E.Smith & A.R.Pleszkunの論文によって、アウト・オブ・オーダー実行において例外をうまく処理する手法が示された。最初にアウト・オブ・オーダー実行を行った商用マイクロプロセッサは1990年発表のPOWER1とされている。x86ではP6マイクロアーキテクチャ（Pentium Pro、1995年）が初である。他には、IBMとモトローラのPowerPC 601 (1992/1993)、富士通とHALのSparc641 (1995)、ヒューレット・パッカードのPA-8000 (1996)、MIPSの MIPS R10000 (1996)、AMD K5 (1996)、DEC Alpha の 21264 (1998)などがある。OoOではないことを特に示す意味があるだろうプロセッサには、サンのUltraSPARC（SPARC T3以前の場合。富士通のSPARC64では実現）、インテルとヒューレット・パッカードが共同開発したItanium、トランスメタのCrusoeなどがある。これらでは、レジスタウィンドウがレジスタリネーミングと相性が悪い、プロセッサコアの命令体系にVLIWを採用しコア外のコンパイラなどで依存や並列実行を解決している、依存関係が無い異なるスレッドの命令を並列実行することで性能を得ている、といった理由でOoOが採用されていない。原理上、アウト・オブ・オーダー実行のためには性能比以上にプロセッサが複雑になる傾向があるため、たとえば電力効率が求められる組込みプロセッサにはあまり採用されていない。古い時代のプロセッサでは、通常次のようなステップで命令が実行された。OoOでは、命令及び実行結果を一時溜めておく場所を作り、命令の実行を次のように細分化する。OoOの鍵になるコンセプトはある命令の実行に必要なデータが得られない状態でも、プロセッサの動作を止めず他の命令を実行し続けられるようにすることである。インオーダ実行では必要なデータが全部揃わないと(2)の段階で実行が止まってしまう。この点を改善したのがOoOである。OoOプロセッサはこの半端な時間（スロット）を他の「準備ができている」命令に当て、後にリタイアステージで実行結果をレジスタファイルに反映させる順序を修正することで、順序通り命令を実行したのと同じ結果が得られるようにする。本来のプログラムコードに書かれた命令の順序は「プログラム順」(program order)と呼ばれるが、この種のプロセッサの内部では「データ順」(data order)で扱われる。つまり、データないしオペランドがプロセッサのレジスタに用意される順序である。これら二種類の順序間の変換を行い、同時に出力に論理的な整合性を持たせるためには相当複雑な回路が必要である。プロセッサはまるでランダムな順序で命令を実行するように見える。命令パイプラインが深くなり、主記憶装置（あるいはキャッシュメモリ）に比べプロセッサが高速になる程OoOの威力は増す。例えば、現代のプロセッサはメモリの数倍の速さで動作しており（＝メモリを読み書きするのに沢山のサイクル数を必要とする）、バス上にデータが乗るのを待つのは非常にサイクル数を無駄にすることになる（ノイマンズ・ボトルネック参照）。OoOパラダイムによってもたらされた違いの一つに、待ち行列を用意することによって、命令をデコードし実行ユニットに割り振るステップ(dispatch step)と実際に命令を発行するステップ(issue step)とを分離することができ、同時に、卒業ステージと実行ステージとを分離することができる点がある。インオーダー時代のプロセッサではこれらはパイプラインによって完全に一体化していた。OoOではこれらを分離することができ、このパラダイムは以前は「分離アーキテクチャ」(decoupled architecture)と呼ばれていた。偽のオペランド依存性（本当は必要でないのに、特定のオペランドが要求されているように見えること）は順序通りでない命令の発行をさまたげ得る。これを避けるために、レジスタ・リネーミングという技法が用いられる。このスキームでは、アーキテクチャ上のレジスタ数より実際の（物理的）レジスタ数の方が多い。複数の物理的なレジスタに同一の（アーキテクチャ上の）レジスタ名を割り当てることで、同じ名前で異なったヴァージョンのレジスタが複数個同時に存在するようにみせかけることができる。実行結果を格納する待ち行列は分岐予想が外れた時及び例外/トラップの処理の際発生する問題を解決するために必須である。例外が起きた場合はプログラム順で命令が実行されることが必要になるが、結果待ち行列があるおかげで、例外を起こした後でも当該プログラムを再実行することができる。以前実行した分岐命令の予測が失敗した際や、例外が発生した際は、この待ち行列から（まだ書き込まれていない段階で）ゴミになってしまった結果を削除することができる。分岐をまたいだ命令の発行は現在も未解決の問題で、投機的実行という名で知られる。

出典:wikipedia