投機的実行
投機的実行（とうきてきじっこう、英: speculative execution）とは、コンピュータシステムが必要でないかもしれない処理を実行する最適化技術である。実際にその処理が必要かどうかが分かる前に処理を行うことで、処理が必要だと分かった後に生じる遅延を防ぐことが目的である。もし結局その処理が必要でなかった場合、処理によって行われた変更の大部分は元に戻され、その結果は無視される[1][2]。
概要
[編集]投機的実行は性能最適化の一種である。その主たる考え方は、処理が必要とされるかどうかを知る「前」に実行するというもので、それによってその処理が必要だとわかった「後」でその処理をすることで生じる遅延を防ぐ。その処理が不要だったと判明した場合、その結果を単に無視する。目的は余分な計算資源が利用可能な場合に並行性を向上させることである。
以下のようなテクノロジーがこの考え方を採用している。
プロセッサ
[編集]近年のパイプライン化されたマイクロプロセッサは条件分岐命令のコストを削減するために、分岐命令の実行履歴に基づいてプログラムの実行経路を予測するという形で投機的実行を行っている[2]。これを分岐予測という。性能向上と計算資源の有効利用のためには、分岐する以前に、ある命令を実行すべきか判明する前から実行するようスケジュールされなければならないということが判明した[3]。
コンパイラ
[編集]マルチプロセッシングシステム向けのコンパイラ最適化における投機的実行とは、空いているプロセッサに次の実行ブロック内のコードを実行させるもので、その場合は他のプロセッサで実行中のコードとの間に依存関係がないことが前提である。この方式の利点は、個々のプロセッサとシステム全体の応答時間を削減できる点である。しかし、この賭けの分がない場合はパイプラインのフラッシュが発生するので、平均的ケースでも最終的にペナルティが生じる[4]。投機的に実行された命令列の効果を緩衝するためのハードウェアの補助を必要とするため、コンパイラによる投機的実行には制限がある。ハードウェアによるサポートがない場合、コンパイラは投機が失敗した場合でも副作用のない命令しか投機的に実行するようにしか命令を配置できない[5]。
積極的実行
[編集]積極的実行（eager execution）は投機的実行の一種であり、条件分岐の両方の経路を実行し、実際に条件分岐命令を実行して通ることが判明した経路の結果のみを採用する。計算資源に制限がなく、全ての分岐に対して積極的な投機的実行を行うことができれば、理論上完全な分岐予測（必ず当たる「神託」に擬して oracle executionとも呼ばれる）と同等の性能を発揮する。ただし、必要な資源量は条件分岐の数に対し指数関数的に増大する[6]。
ミクロなレベルでの積極的実行としては、演算装置における桁上げ選択加算器（足し算の桁上げ（繰り上がり）は、高速化の手法はあるものの、最下位桁から伝搬する性質がある。そこで、桁上げありの場合となしの場合の両方を計算し、最後に（あるいは次のクロックで）桁上げの情報に応じてどちらかを選択する）といったものがある。
遅延評価
[編集]遅延評価は投機的ではない。投機的実行と言える先行評価（eager evaluation）をHaskellプログラミング言語の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。Glasgow Haskell Compiler (GHC) の最近のバージョンでは、選択を間違った場合にやり直すアボート機能をそなえた一種の投機的実行をサポートしており、「楽観的評価」と呼ばれている[7]。
脆弱性
[編集]2018年頃より、汎用的なプロセッサでの投機的実行において、セキュリティ上の脆弱性があることが判明している。例えば、投機的実行においてアクセス禁止されているメモリ空間にアクセスするSpectreなどが知られている[8]。
電力消費
[編集]投機的実行は、性能を向上させるための技術であり、プロセッサが必要になる可能性のある処理を事前に実行することで、処理の遅延を最小限に抑えることを目的としている。しかし、この技術には電力消費に関する考慮が必要である。
投機的実行では、処理が実際に必要かどうかを事前に判断することなく処理を行うため、プロセッサは通常よりも多くの処理を行う。このため、実際には不要だった処理にかかる電力も消費される。特に、投機的実行が行われる際には、プロセッサが複数の命令を同時に処理するため、リソースの使用が増加し、電力消費も増加する。
例えば、投機的実行によって複数の命令が同時に実行される場合、キャッシュのヒット率が低下する可能性があり、これによりメモリの帯域幅の利用が増加し、さらに電力消費が増える。加えて、投機的に実行された処理が不要であった場合、その結果を破棄するために追加の電力が必要となる。このような場合、プロセッサは不要な処理を行ったり、その結果を無効にしたりするために、追加のエネルギーを消費することになる。
したがって、投機的実行の導入に際しては、性能向上と電力消費のバランスを取ることが重要である。性能を最大化するために投機的実行を利用しつつも、その電力消費を管理し、エネルギー効率を改善するための設計や制御技術が求められる。
出典
[編集]- ^ a b Lazy and Speculative Execution Butler Lampson Microsoft Research OPODIS, Bordeaux, France 12 December 2006
- ^ a b International Business Machines Corporation. Research Division; Prabhakar Raghavan; Hadas Schachnai; Mira Yaniv (1998). Dynamic schemes for speculative execution of code. IBM 2011年1月18日閲覧。
- ^ Bernd Krieg-Brückner (1992). ESOP '92: 4th European Symposium on Programming, Rennes, France. Springer. pp. 56–57. ISBN 9783540552536 2011年1月18日閲覧。
- ^ Phillip A. Laplante (2004). Real-time systems design and analysis. Wiley-IEEE. p. 391. ISBN 9780471228554 2011年1月21日閲覧。
- ^ David J. Lilja; Peter L. Bird (1 January 1994). The interaction of compilation technology and computer architecture. Springer. p. 16. ISBN 9780792394518 2011年1月21日閲覧。
- ^ Jurij Šilc; Borut Robič; Theo Ungerer (1999). Processor architecture: from dataflow to superscalar and beyond. Springer. pp. 148–150. ISBN 9783540647980 2011年1月21日閲覧。
- ^ Optimistic Evaluation: a fast evaluation strategy for non-strict programs
- ^ CPUの脆弱性「Spectre（スペクター）」と「Meltdown（メルトダウン）」 富士通
外部リンク
[編集]
- "Speculative computation in Multilisp."
- 情報処理学会 学会誌『情報処理』 Vol. 40, No. 2（1999年2月）インタラクティブ・エッセイ