Wikipedia

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

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
しまあじ (会話 | 投稿記録)
94,774 回編集
Melan (会話 | 投稿記録)
25,487 回編集
en:Speculative execution（2012年1月23日 3:00:57(UTC)）の翻訳のマージ
1行目:
'''投機的実行'''（とうきてきじっこう、[[英語|英]]: speculative 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>。
{{複数の問題
|出典の明記=2011年12月
|Wikify=2011年12月
|Cleanup=2011年12月
}}
'''投機的実行'''(とうきてきじっこう、''speculative execution'')とは、[[コンピュータ]]が実際にはその結果を捨ててしまうかもしれないコードを実行することである。[[関数型言語]]では、"speculative evaluation"という用語が使われている。
 
== 概要 ==
投機的実行は最適化のひとつの手法である。
投機的実行は性能[[最適化 (情報工学)|最適化]]の一種である。その主たる考え方は、仕事が確実に必要とされるかどうかを知る「前」に実行するというもので、それによってその仕事が必要だとわかった「後」でその仕事をしたときに生じる遅延を防ぐ。その仕事が全く不要だったと判明した場合、その結果を単に無視する。目的は余分な[[計算資源]]が利用可能な場合に[[並行性]]を向上させることである。
これは、先に実行する方が後で実行するより時間的にも空間的にも得な場合に意味があり、結果として捨ててしまうことになる処理にかかった時間的、空間的損失よりも全体としての利益が大きくなければならない。
 
以下のようなテクノロジーがこの考え方を採用している。
最近の[[命令パイプライン|パイプライン化]]された[[マイクロプロセッサ]]では、[[条件付分岐]]命令のコストを削減するために投機的実行を使用している。
* [[記憶装置|メモリ]]と[[ファイルシステム]]における[[プリフェッチ]]
条件付分岐命令が現れた場合、プロセッサは分岐しそうかどうか予測し([[分岐予測]])、即座に決定した方の実行を開始する。
* [[分岐予測]]
その予測が後に間違っていたことがわかると、分岐命令以後の処理結果は全て捨てられてしまう。このように先に実行しなければ、パイプラインは分岐するかしないか判明するまで何もしないため、投機的に実行しても時間を浪費していることにはならない。
* [[関係データベース管理システム|データベースシステム]]における[[楽観的並行性制御]]<ref name="Lampson"/>
 
== プロセッサ ==
[[積極的実行]]は投機的実行の一種である(ただし副作用があるため、複雑さの度合いが異なる)。
近年の[[命令パイプライン|パイプライン化]]された[[マイクロプロセッサ]]は[[分岐命令|条件分岐命令]]のコストを削減するために、分岐命令の実行履歴に基づいてプログラムの実行経路を予測するという形で投機的実行を行っている<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>。
計算に必要な値はしばしばスタックから得られ、メモリに戻すことなく後でヒープ領域から取り出すことが多いため、先に実行しても高くつかない。<!-- ごめんなさい。この一文意味不明(訳者) -->
1から1,000,000までの整数のリストを作るような場合は実際のところやや高くつく。<!-- この一文も背景が不明なのでよくわからない-->
一般的な[[プログラミング言語]]でコードを書くプログラマは明示的に[[遅延評価|遅延性]]を導入したり、まわりくどい(複雑な)書き方をしたりすることで上記のようなケースを防ぐ。
 
== コンパイラ ==
[[遅延評価]]は投機的ではない。投機的実行を[[Haskell|Haskellプログラミング言語]]の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。
[[マルチプロセッシング]]システム向けの[[コンパイラ最適化]]における投機的実行とは、空いているプロセッサに次の実行ブロック内のコードを実行させるもので、その場合は他のプロセッサで実行中のコードとの間に依存関係がないことが前提である。この方式の利点は、個々のプロセッサとシステム全体の応答時間を削減できる点である。しかし、この賭けの分がない場合はパイプラインのフラッシュが発生するので、平均的ケースでも最終的にペナルティが生じる<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>。
Glasgow Haskell Compiler(GHC)は「悲観的評価」と名づけたある種の投機的実行をサポートしている。
<!--
なんか、いつのまにか言語の話になってるなあ
-->
 
== 積極的実行 ==
投機的実行の実装は複雑で難しい。次のような処理を例として説明する。
「[[先行評価|積極的実行]] (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>。
# あるデータ格納域へのポインタ''ptr''が存在する。''ptr''がゼロの場合、データ格納域が存在しないことを示す。
# ''ptr''がゼロでない場合、データ格納域に何らかの書き込みをする。
# ''ptr''がゼロの場合、何もしないで次の処理に移行する。
 
== 遅延評価 ==
この処理を何度も通っていて、ほとんど必ず''ptr''がデータ格納域を指している場合、投機的実行では分岐予測の結果にしたがって''ptr''の指すデータ格納域に書き込みを行おうとする。しかし、''ptr''がゼロであれば、それは不正なアドレスへの書き込みとなってしまう。投機的実行を行うコンピュータではこの不正書き込みで例外を発生してはならない。また、アドレスではなく書き込む内容が間違っている場合や、ロードしようとするアドレスが不正な場合など、投機的実行の実装の困難さは、このようなところにある。
[[遅延評価]]は投機的ではない。投機的実行を[[Haskell|Haskellプログラミング言語]]の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。 Glasgow Haskell Compiler ([[:en:Glasgow 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>。
 
== 出典 ==
{{Reflist|2}}
 
== 外部リンク ==
{{ウィキポータルリンク|コンピュータ}}
* [http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html "Speculative computation in Multilisp."]
 
{{CPU technologies}}
 
{{DEFAULTSORT:とうきてきしつこう}}
[[Category:コンピュータアーキテクチャ]]
{{Computer-stub}}
 
[[de:Speculative execution]]
「https://ja.wikipedia.org/wiki/投機的実行」から取得