アウト・オブ・オーダー実行
出典: フリー百科事典『ウィキペディア（Wikipedia）』
アウト・オブ・オーダー実行（-じっこう、英語: out-of-order execution）とは、コンピュータ科学でのパラダイムの一つであり、命令実行効率を上げるために、ほとんどの高速マイクロプロセッサが有している機能である。アクロニムの'OoO'でも書かれる。「順序を守らない実行」の意。
これらのプロセッサは、高速化のために、できるだけサイクル（プロセッサが命令を実行する基準となる時間の単位）数の節約を図ろうとしている。ある種の遅延はサイクル数の浪費であり、うまくすればそのCPUサイクルはハイパースレッディングのような用途にふりわけることができる。アウト・オブ・オーダー実行はそのための最適化法の一つである。具体的には、互いに依存関係がない複数の命令で、与えられたプログラムコードにおける順序より効率的な実行順序がある場合、それらを置き換えてしまうもの。
以下OoOと略す。
目次 |
[編集] 歴史
OoOは制限付きデータフロー計算法の一種である。データフローマシンは1980年代のコンピュータアーキテクチャー研究の主戦場であって、研究をリードしたのはYale Pattと彼の開発になるHPSmシミュレータであった。1985年のJ.E.Smith & A.R.Pleszkun の論文によって、アウトオブオーダーマシン（out-of-order machine、順序通りに処理しない装置）が例外をうまく処理することができることが証明された。
最初にOoOを搭載した装置は恐らく1964年のCDC 6600であろう。この機種ではコンフリクトを解決するためのスコアボードが用意された。この方法でライト・アフター・ライト (WAW)及びライト・アフター・リード (WAR)問題は解決できたが、レジスタ・リネーミング機能を含まなかった。三年後の1966年、IBM 360/91がTomasulo algorithm（データを更新する場合、共通データバスにブロードキャストする）を導入した。IBMはまた、1990年に最初のOoOマイクロプロセッサであるPOWER1を発表した。OoOが広く用いられるようになったのは1995年に発表されたインテルのペンティアム・プロ(Pentium Pro)からである。IBM、インテル以外のほとんどのCPUベンダも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のスキームが論理的に複雑だからである。チップ面積を大きくしシリコンウェハ1枚から取れるチュップ数を少なくし歩留を悪化させるOoOは、低コストであることが求められるローエンドのプロセッサにはあまり採用されていない。
[編集] 基本的コンセプト
[編集] イン・オーダー実行プロセッサ
古い時代のプロセッサでは、通常次のようなステップで命令が実行された。
- 命令フェッチ（命令を読み込む）
- 入力オペランド（計算に必要なデータ）が既に用意されていれば（例えばメモリからレジスタ上に読み込まれて）、命令は適当な実行ユニット(functional unit)に割り当てられ、さもなければオペランドが用意されるまでプロセッサは命令の実行を止めて待つ。
- 命令が適当な実行ユニットで実行される。
- 実行ユニットは実行結果をレジスタファイルに返す。
[編集] アウト・オブ・オーダー実行プロセッサ
OoOでは、命令及び実行結果を一時溜めておく場所を作り、命令の実行を次のように細分化する。
- 命令フェッチ。
- 命令を命令待ち行列または命令バッファ(instruction queue, instruction buffer, reservation stations)に格納する。
- 命令バッファ内の命令は、入力オペランドが得られるまで実行されない。入力オペランドが得られた段階で、バッファ内にそれより古い命令があっても先にバッファから取り除かれ、実行されることになる。
- 命令が適当な実行ユニットに対して発行(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プロセッサはレジスタマップによる処理を用いている。
[編集] 関連項目
 |
この「アウト・オブ・オーダー実行」は、コンピュータに関連した書きかけです。この記事を加筆して下さる人を求めています。（Portal:コンピュータ） |
