アウト・オブ・オーダー実行
テンプレート:出典の明記 アウト・オブ・オーダー実行（-じっこう、テンプレート:Lang-en-short）とは、コンピュータ科学でのパラダイムの一つであり、命令実行効率を上げるために、多くのプロセッサで採用している実装手法の1つである。アクロニムの'OoO'あるいは'O-o-O'とも書かれる。「順序を守らない実行」の意。
プロセッサの設計と実装において、命令レベルの並列性（Instruction-level parallelism; ILP）を高めることは1つの目標でありスーパースケーラにより1サイクルあたり2命令を越えることが可能になったが、フォンノイマンアーキテクチャの前提である逐次実行が、並列化を施す上での障壁となっていた。アウト・オブ・オーダー実行（以下、OoO）は、順番を変えて実行することにより、複数命令の同時実行の可能性を広げる最適化手法の1つである。OoOと同時マルチスレッディング（Simultaneous Multithreading; SMT）を併用することで、さらに実行ユニットの稼働率を上げ、ILPを向上することが可能となる。また、OoOプロセッサであることはSMTを実装しやすくする。ただし、OoOであることはSMTプロセッサの必要要件ではない（例：Intel Atom）。
アウト・オブ・オーダー実行に対して、プログラムに書かれた通りに逐次実行することを、イン・オーダー実行と言う。
目次
歴史
OoOは制限付きデータフロー計算法の一種である。データフローマシンは1980年代のコンピュータアーキテクチャー研究の主戦場であって、研究をリードしたのはYale Pattと彼の開発になるHPSmシミュレータであった。1985年のJ.E.Smith & A.R.Pleszkun の論文によって、アウトオブオーダーマシン（out-of-order machine、順序通りに処理しない装置）が例外をうまく処理することができることが証明された。
最初にOoOを搭載したマシンは恐らく1964年のCDC 6600であろう。この機種ではコンフリクトを解決するためのスコアボードが用意された。この方法でライト・アフター・ライト (WAW)及びライト・アフター・リード (WAR)問題は解決できたが、レジスタ・リネーミング機能を含まなかった。1966年には IBM System/360 モデル91がTomasuloのアルゴリズム（データを更新する場合、共通データバスにブロードキャストする）を導入した。
マイクロプロセッサに最初にOoOが使用されたのは、1990年のIBM POWER1である。OoOが広く用いられるようになったのは1995年に発表されたインテルのペンティアム・プロ(Pentium Pro)からである。以後はIBMやインテル以外のほとんどのプロセッサベンダもOoOをとり入れるようになった。IBMとモトローラのPowerPC 601 (1992/1993)、富士通とHALのSparc641 (1995)、ヒューレット・パッカードのPA-8000 (1996)、MIPSの MIPS R10000 (1996)、AMD K5 (1996)、DEC Alpha の 21264 (1998)などである。
OoOを取り入れていない例外的なプロセッサには、サンのUltraSparc、インテルとヒューレット・パッカードが共同開発した Itanium、トランスメタの Crusoeなどがある。
OoOの一般化が1990年代半ばにずれ込んだのは、OoOのスキームが論理的に複雑だからである。使用ダイ面積に対して効率の悪いOoOは、電力効率の良さが求められる組込みプロセッサにはあまり採用されていない。
基本的コンセプト
イン・オーダー実行プロセッサ
古い時代のプロセッサでは、通常次のようなステップで命令が実行された。
- 命令フェッチ（命令を読み込む）
- 入力オペランド（計算に必要なデータ）が既に用意されていれば（例えばメモリからレジスタ上に読み込まれて）、命令は適当な実行ユニット(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プロセッサはレジスタマップによる処理を用いている。
