投機的実行
投機的実行（とうきてきじっこう、英: speculative execution）とは、コンピュータに必要としないかもしれない仕事をさせることである。この性能最適化技法は、パイプライン化されたプロセッサなどのシステムで使われている[1][2]。
概要
投機的実行は性能最適化の一種である。その主たる考え方は、仕事が確実に必要とされるかどうかを知る「前」に実行するというもので、それによってその仕事が必要だとわかった「後」でその仕事をしたときに生じる遅延を防ぐ。その仕事が全く不要だったと判明した場合、その結果を単に無視する。目的は余分な計算資源が利用可能な場合に並行性を向上させることである。
以下のようなテクノロジーがこの考え方を採用している。
プロセッサ
近年のパイプライン化されたマイクロプロセッサは条件分岐命令のコストを削減するために、分岐命令の実行履歴に基づいてプログラムの実行経路を予測するという形で投機的実行を行っている[2]。これを分岐予測という。性能向上と計算資源の有効利用のためには、分岐する以前に、ある命令を実行すべきか判明する前から実行するようスケジュールされなければならないということが判明した[3]。
コンパイラ
マルチプロセッシングシステム向けのコンパイラ最適化における投機的実行とは、空いているプロセッサに次の実行ブロック内のコードを実行させるもので、その場合は他のプロセッサで実行中のコードとの間に依存関係がないことが前提である。この方式の利点は、個々のプロセッサとシステム全体の応答時間を削減できる点である。しかし、この賭けの分がない場合はパイプラインのフラッシュが発生するので、平均的ケースでも最終的にペナルティが生じる[4]。投機的に実行された命令列の効果を緩衝するためのハードウェアの補助を必要とするため、コンパイラによる投機的実行には制限がある。ハードウェアによるサポートがない場合、コンパイラは投機が失敗した場合でも副作用のない命令しか投機的に実行するようにしか命令を配置できない[5]。
積極的実行
積極的実行(eager execution) は投機的実行の一種であり、条件分岐の両方の経路を実行し、実際に条件分岐命令を実行して通ることが判明した経路の結果のみを採用する。計算資源に制限がなく、あらゆる分岐に対して積極的な投機的実行を行うことができれば、理論上完全な分岐予測（必ず当たる「神託」に擬して oracle execution とも）と同等の性能を発揮する。ただし、必要な資源量は条件分岐の数に対し指数関数的に増大する[6]。
ミクロなレベルでの積極的実行としては、演算装置における桁上げ選択加算器（足し算の桁上げ（繰り上がり）は、高速化の手法はあるものの、最下位桁から伝搬する性質がある。そこで、桁上げありの場合となしの場合の両方を計算し、最後に（あるいは次のクロックで）桁上げの情報に応じてどちらかを選択する）といったものがある。
遅延評価
遅延評価は投機的ではない。投機的実行と言える先行評価（Eager evaluation）をHaskellプログラミング言語の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。Glasgow Haskell Compiler (GHC) の最近のバージョンでは、選択を間違った場合にやり直すアボート機能をそなえた一種の投機的実行をサポートしており、「悲観的評価」と呼ばれている[7]。
出典
外部リンク
テンプレート:CPU technologies- ↑ 1.0 1.1 Lazy and Speculative Execution Butler Lampson Microsoft Research OPODIS, Bordeaux, France 12 December 2006
- ↑ 2.0 2.1 テンプレート:Cite book
- ↑ テンプレート:Cite book
- ↑ テンプレート:Cite book
- ↑ テンプレート:Cite book
- ↑ テンプレート:Cite book
- ↑ Optimistic Evaluation: a fast evaluation strategy for non-strict programs
