アウト・オブ・オーダー実行とは? わかりやすく解説

Weblio 辞書 > コンピュータ > IT用語辞典 > アウト・オブ・オーダー実行の意味・解説 

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

【英】out of order execution

アウト・オブ・オーダー実行とは、マイクロプロセッサの処理を高速化するための手法の1つで、プログラム記述されている順序とは異な順序プログラム中の命令実行することである。

マイクロプロセッサのほかの用語一覧
CPU:  A5チップ  A5X  A6チップ  アウト・オブ・オーダー実行  アドレス指定方式  インサーキットエミュレータ  オーバークロック

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/10/29 02:44 UTC 版)

アウト・オブ・オーダー実行(アウト・オブ・オーダーじっこう、: 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)、MIPSMIPS R10000 (1996)、AMD K5 (1996)、DEC Alpha21264 (1998)などがある。

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

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

基本的コンセプト

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

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

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

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

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

  1. 命令フェッチ。
  2. 命令にリオーダ・バッファ(reorder buffer)のエントリを割り当てる。
  3. 命令を命令待ち行列または命令発行キュー(reservation station, issue queue)に送る(dispatch)。
  4. 命令待ち行列内の命令は、入力オペランドが得られるまで実行されない。入力オペランドが得られた段階で、待ち行列内にそれより古い命令があっても先に待ち行列から取り除かれ、実行されることになる。
  5. 命令が適当な実行ユニットに対して発行(issue)され、実行される。
  6. 実行結果がリオーダ・バッファに格納される。
  7. リオーダ・バッファ内の命令のうち、最も古い命令の実行が完了すると、その実行結果はレジスタファイルに書き戻され、命令はリオーダ・バッファから取り除かれる。これを卒業(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の手法に起因した、MeltdownSpectreといった脆弱性が2018年1月に発表され、業界に衝撃を与えたた[2]

脚注

  1. ^ a b Hisa Ando 2011, p. 86.
  2. ^ 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 

関連項目


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

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/11/05 07:56 UTC 版)

命令レベルの並列性」の記事における「アウト・オブ・オーダー実行」の解説

メモリアクセスによるパイプラインストールを減らす。だが製造価格大きく影響するほどのハードウェアリソースを必要とするため、かつては純粋な実装現実的でなかった。近年新しスキーム提案改良加えたアーキテクチャ実装により実現している。

※この「アウト・オブ・オーダー実行」の解説は、「命令レベルの並列性」の解説の一部です。
「アウト・オブ・オーダー実行」を含む「命令レベルの並列性」の記事については、「命令レベルの並列性」の概要を参照ください。

ウィキペディア小見出し辞書の「アウト・オブ・オーダー実行」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「アウト・オブ・オーダー実行」の関連用語

アウト・オブ・オーダー実行のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



アウト・オブ・オーダー実行のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2025 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【アウト・オブ・オーダー実行】の記事を利用しております。
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのアウト・オブ・オーダー実行 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの命令レベルの並列性 (改訂履歴)、Alpha 21264 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS