アウトオブオーダー実行

アウトオブオーダー実行は、プロセッサが命令を厳密にプログラム順に実行するのではなく、オペランドの準備が整い次第実行することを可能にする。これは、レジスタリネーミングとバッファリングを用いて並列性を露呈させつつ、インオーダーな結果を生成する。

Definition

アウトオブオーダー実行は、プロセッサが命令の実行を動的に再順序付けし、オペランドが利用可能になり次第、独立した命令を実行するマイクロアーキテクチャ技術である。これは、バッファリングとリネーミングを用いて、逐次的でインオーダーな完了という外観を維持する。

Scope

このトピックでは、動的スケジューリング、すなわちリザベーションステーション、偽の依存関係を除去するためのレジスタリネーミング、インオーダーコミットを強制するリオーダーバッファ、および投機的実行の回復について扱う。これはトマシューロのアルゴリズムに直接基づいている。分岐方向の予測（分岐予測）や、より広範な並列性の存在量（命令レベル並列性）については除外し、命令の再順序付け機構そのものに焦点を当てる。

Core questions

• プロセッサはどのようにしてプログラム順序外で命令を実行しながら、正確なインオーダーの結果を生成できるのか？
• レジスタリネーミングは、ライトアフターリードおよびライトアフターライトの依存関係をどのように排除するのか？
• リザベーションステーションとリオーダーバッファはどのような貢献をするのか？
• アウトオブオーダーコアにおいて、例外と誤予測はどのように正確に回復されるのか？

Key concepts

• 動的スケジューリング
• リザベーションステーション
• レジスタリネーミング
• 共通データバス
• リオーダーバッファ
• インオーダーコミット
• 正確な例外
• 投機的実行回復

Key theories

トマシューロのアルゴリズム

トマシューロのスキームは、リザベーションステーションと共通データバスを用いてレジスタをリネームし、オペランドが利用可能になり次第、命令を機能ユニットにディスパッチする。これにより、真のデータ依存関係のみを尊重するアウトオブオーダー実行が可能となる。

インオーダーコミットによる正確な例外処理

リオーダーバッファは、アウトオブオーダー命令の結果を保持し、プログラム順にコミットする。これにより、例外や誤予測が、あたかも実行が厳密に逐次的であったかのように正確に処理される。

Mechanisms

デコードされた命令は物理レジスタにリネームされ、リザベーションステーションまたは発行キューに配置される。そこで、結果バス上でブロードキャストされるオペランドを待機する。準備が整うと、利用可能な機能ユニット上で任意の順序で実行される。リオーダーバッファは元のプログラム順序を追跡し、結果を順次コミットする。誤予測や例外が発生した場合は投機的な結果を破棄し、アーキテクチャ状態が常に正確であることを保証する。

Clinical relevance

アウトオブオーダー実行は、高性能CPUの核となるエンジンであり、独立した作業を見つけることでメモリおよび実行のレイテンシを隠蔽する。また、セキュリティ上の影響も持つ。投機的でアウトオブオーダーな作業は、破棄される前に一時的にデータにアクセスできるため、SpectreやMeltdownといったマイクロアーキテクチャのサイドチャネル攻撃を可能にした。

History

トマシューロは1967年にIBM System/360 Model 91で動的スケジューリングを導入した。1980年代に開発された、正確な例外処理のためのリオーダーバッファとの組み合わせにより、アウトオブオーダー実行は汎用プロセッサにとって実用的なものとなり、1990年代半ば以降、高性能設計における標準となった。

Debates

性能対複雑性、電力、およびセキュリティ

アウトオブオーダー実行は強力なシングルスレッド性能を提供するが、ハードウェアの複雑性や電力において大きなコストを伴い、その投機的実行は悪用可能であることが判明している。このため、どれだけ積極的に投機的実行を行うか、あるいはより単純で効率的、またはより安全な設計を優先するかについて議論が続いている。

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

命令がアウトオブオーダーで実行される場合、プログラムはどのようにして依然として正しいのか？

プロセッサは実行を再順序付けするだけであり、結果を再順序付けするわけではない。レジスタリネーミングにより、真のデータ依存関係が尊重され、リオーダーバッファが元のプログラム順序で結果をコミットするため、可視的なアーキテクチャ状態は逐次実行が生成するものと全く同じになる。

レジスタリネーミングとは何か？

レジスタリネーミングは、命令で指定されたアーキテクチャレジスタを、より大きな物理レジスタのプールにマッピングする。これにより、レジスタ名の再利用から生じる偽の（名前）依存関係が除去され、レジスタストレージを巡る競合なしに、より多くの独立した命令が並列に実行できるようになる。