「投機的実行」の版間の差分

'''投機的実行'''（とうきてきじっこう、[[英語{{Lang-en-short|英]]: speculative execution）execution}}）とは、[[コンピュータ]]に必要としないかもしれない仕事をさせることである。この性能[[最適化 (情報工学)|最適化]]技法は、[[命令パイプライン|パイプライン化]]された[[CPU|プロセッサ]]などのシステムで使われている<ref name="Lampson">[http://research.microsoft.com/en-us/um/people/blampson/slides/lazyandspeculative.ppt Lazy and Speculative Execution] [[バトラー・ランプソン|Butler Lampson]] [[マイクロソフトリサーチ|Microsoft Research]] OPODIS, Bordeaux, France 12 December 2006</ref><ref name="DivisionRaghavan1998">{{Cite book |author1=International Business Machines Corporation. Research Division |author2=Prabhakar Raghavan |author3=Hadas Schachnai |coauthors=Mira Yaniv |title=Dynamic schemes for speculative execution of code |url= http://books.google.com/books?id=eBgMGwAACAAJ |accessdate=2011-01-18 |year=1998 |publisher=IBM}}</ref>。

近年の[[命令パイプライン|パイプライン化]]された[[マイクロプロセッサ]]は[[分岐命令|条件分岐命令]]のコストを削減するために、分岐命令の実行履歴に基づいてプログラムの実行経路を予測するという形で投機的実行を行っている<ref name="DivisionRaghavan1998"/>。これを[[分岐予測]]という。性能向上と計算資源の有効利用のためには、分岐する以前に、ある命令を実行すべきか判明する前から実行するようスケジュールされなければならないということが判明した<ref name="Krieg-Brückner1992">{{Cite book |author=Bernd Krieg-Brückner |title=ESOP '92: 4th European Symposium on Programming, Rennes, France |url= http://books.google.com/books?id=AQbhbphyOsoC&pg=PA56 |accessdate=2011-01-18 |year=1992 |publisher=Springer |isbn=9783540552536 |pages=56–57}}</ref>。

[[マルチプロセッシング]]システム向けの[[コンパイラ最適化]]における投機的実行とは、空いているプロセッサに次の実行ブロック内のコードを実行させるもので、その場合は他のプロセッサで実行中のコードとの間に依存関係がないことが前提である。この方式の利点は、個々のプロセッサとシステム全体の応答時間を削減できる点である。しかし、この賭けの分がない場合はパイプラインのフラッシュが発生するので、平均的ケースでも最終的にペナルティが生じる<ref name="Laplante2004">{{Cite book |author=Phillip A. Laplante |title=Real-time systems design and analysis |url= http://books.google.com/books?id=kIhdeGVtb-kC&pg=PA391 |accessdate=2011-01-21 |year=2004 |publisher=Wiley-IEEE |isbn=9780471228554 |page=391}}</ref>。投機的に実行された命令列の効果を緩衝するためのハードウェアの補助を必要とするため、コンパイラによる投機的実行には制限がある。ハードウェアによるサポートがない場合、コンパイラは投機が失敗した場合でも[[副作用 (プログラム)|副作用]]のない命令しか投機的に実行するようにしか命令を配置できない<ref name="LiljaBird1994">{{Cite book |author1=David J. Lilja |author2=Peter L. Bird |title=The interaction of compilation technology and computer architecture |url= http://books.google.com/books?id=D67qFdGbrw0C&pg=PA16 |accessdate= 2011-01-21 |date=1 January 1994 |publisher=Springer |isbn=9780792394518 |page=16}}</ref>。

'''積極的実行''' (eager execution) は投機的実行の一種であり、条件分岐の両方の経路を実行し、実際に条件分岐命令を実行して通ることが判明した経路の結果のみを採用する。計算資源に制限がなく、あらゆる分岐に対して積極的な投機的実行を行うことができれば、理論上完全な[[分岐予測]]（必ず当たる「神託」に擬して ''oracle execution'' とも）と同等の性能を発揮する。ただし、必要な資源量は条件分岐の数に対し指数関数的に増大する<ref name="ŠilcRobič1999">{{Cite book |author1=Jurij Šilc |author2=Borut Robič |author3=Theo Ungerer |title=Processor architecture: from dataflow to superscalar and beyond |url= http://books.google.com/books?id=JEYKyfZ3yF0C&pg=PA148 |accessdate=2011-01-21 |year=1999 |publisher=Springer |isbn=9783540647980 |pages=148–150}}</ref>。

[[遅延評価]]は投機的ではない。投機的実行と言える[[先行評価]]（Eager evaluation）(eager evaluation) を[[Haskell|Haskellプログラミング言語]]の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。Glasgow Haskell Compiler ([[:en:Glasgow Haskell Compiler|GHCGlasgow Haskell Compiler]] (GHC) の最近のバージョンでは、選択を間違った場合にやり直すアボート機能をそなえた一種の投機的実行をサポートしており、「悲観的評価」と呼ばれている<ref name="Robert Ennals and Simon Peyton Jones">[http://research.microsoft.com/~simonpj/papers/optimistic/ Optimistic Evaluation: a fast evaluation strategy for non-strict programs]</ref>。