Editing Speculative execution

{{short description|Computer optimization technique}}
'''Speculative execution''' is an [[optimization (computer science)|optimization]] technique where a [[computer system]] performs some task that may not be needed. Work is done before it is known whether it is actually needed, so as to prevent a delay that would have to be incurred by doing the work after it is known that it is needed. If it turns out the work was not needed after all, most changes made by the work are reverted and the results are ignored.

The objective is to provide more [[Concurrency (computer science)|concurrency]] if extra [[Resource (computer science)|resources]] are available. This approach is employed in a variety of areas, including [[branch predictor|branch prediction]] in [[instruction pipeline|pipelined]] [[CPU|processors]], value prediction for exploiting value locality, prefetching [[Instruction prefetch|memory]] and [[File system|files]], and [[optimistic concurrency control]] in [[Relational database management system|database systems]].<ref>{{Cite conference |last=Lampson |first=Butler |author-link=Butler Lampson |date=2006 |editor-last1=Momenzadeh |editor-first1=Mariam |editor-last2=Shvartsman |editor-first2=Alexander A. |title=Lazy and Speculative Execution in Computer Systems |url=https://link.springer.com/chapter/10.1007/11945529_1 |book-title=Principles of Distributed Systems |series=Lecture Notes in Computer Science |conference=10th International Conference on Principles of Distributed Systems |language=en |location=Bordeaux, France |publisher=Springer |volume=4305 |pages=1–2 |doi=10.1007/11945529_1 |isbn=978-3-540-49991-6|url-access=subscription }}</ref><ref name="DivisionRaghavan1998">{{cite conference
|last1=Raghavan
|first1=Prabhakar
|last2=Shachnai
|first2=Hadas
|last3=Yaniv
|first3=Mira
|title=Dynamic schemes for speculative execution of code
|url=https://ieeexplore.ieee.org/document/693711
|year=1998
|doi=10.1109/MASCOT.1998.693711
|book-title=Proceedings of the Sixth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems
|publisher=IEEE
|pages=309–314
|access-date=18 January 2011|url-access=subscription
}}</ref><ref>
{{cite conference
|author-link= H. T. Kung
|first= H. T. |last= Kung
|author2=John T. Robinson
|title= On optimistic methods for concurrency control
|book-title= ACM Trans. Database Syst.
|volume= 6
|number= 2
|date=June 1981
|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a081452.pdf|archive-url=https://web.archive.org/web/20190831230313/https://apps.dtic.mil/dtic/tr/fulltext/u2/a081452.pdf|url-status=live|archive-date=August 31, 2019}}</ref>

[[Speculative multithreading]] is a special case of speculative execution.

==Overview==
Modern [[instruction pipeline|pipelined]] [[microprocessor]]s use speculative execution to reduce the cost of [[conditional branch]] instructions using schemes that predict the execution path of a program based on the history of branch executions.<ref name="DivisionRaghavan1998"/> In order to improve performance and utilization of computer resources, instructions can be scheduled at a time when it has not yet been determined that the instructions will need to be executed, ahead of a [[branch predictor|branch]].<ref name="Krieg-Brückner1992">{{cite book|author=Bernd Krieg-Brückner|title=ESOP '92: 4th European Symposium on Programming, Rennes, France, February 26-28, 1992: proceedings|url=https://books.google.com/books?id=AQbhbphyOsoC&pg=PA56|access-date=18 January 2011|year=1992|publisher=Springer|isbn=978-3-540-55253-6|pages=56–57}}</ref>

==Variants==
''Speculative computation'' was a related earlier concept.<ref>{{cite book |chapter-url=http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html |chapter=Speculative Computation in Multilisp |author=Randy B. Osborne |title=Parallel Lisp: Languages and Systems |volume=441 |pages=103–137 |date=1990-03-21 |publisher=[[Digital Equipment Corporation#Research and people|Digital Equipment Corporation Research Lab]] |type=[[PostScript|PS]] |doi=10.1007/BFb0024152 |access-date=2018-01-26 |series=Lecture Notes in Computer Science |isbn=3-540-52782-6 |archive-date=2017-02-07 |archive-url=https://web.archive.org/web/20170207033142/http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html |url-status=dead }}</ref>

===Eager execution===
{{See also|Eager evaluation}}

Eager execution is a form of speculative execution where both sides of the conditional branch are executed; however, the results are committed only if the predicate is true. With unlimited resources, eager execution (also known as ''oracle execution'') would in theory provide the same performance as perfect [[branch prediction]]. With limited resources, eager execution should be employed carefully, since the number of resources needed grows [[exponential growth|exponentially]] with each level of branch executed eagerly.<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=https://archive.org/details/processorarchite0000silc|url-access=registration|access-date=21 January 2011|year=1999|publisher=Springer|isbn=978-3-540-64798-0|pages=[https://archive.org/details/processorarchite0000silc/page/148 148]–150}}</ref>

==={{Anchor|PREDICTIVE}}Predictive execution===
{{See also|Pipeline (computing)}}
{{Main| Branch predictor}}

Predictive execution is a form of speculative execution where some outcome is predicted and execution proceeds along the predicted path until the actual result is known. If the prediction is true, the predicted execution is allowed to commit; however, if there is a misprediction, execution has to be unrolled and re-executed. Common forms of this include [[branch predictor]]s and [[memory dependence prediction]]. A generalized form is sometimes referred to as value prediction.<ref>{{cite book|last1=Mark D.|first1=Hill|author-link2=Norman Jouppi|last2=Norman P.|first2=Jouppi|last3=Gourindar S.|first3=Sohi|title=Readings in Computer Architecture|date=2000|publisher=Morgan Kaufman|url=https://books.google.com/books?id=I7o8teBhz5wC&q=processor+predictive+execution&pg=PA178|access-date=5 January 2018|isbn=9781558605398}}</ref>

===Runahead===
{{excerpt|Runahead|paragraphs=1|only=paragraph}}

==Related concepts==

===Lazy execution===
{{Main|Lazy evaluation}}

Lazy execution is the opposite of eager execution, and does not involve speculation. The incorporation of speculative execution into implementations of the [[Haskell (programming language)|Haskell programming language]], a lazy language, is a current research topic. [[Eager Haskell]], a variant of the language, is designed around the idea of speculative execution. A 2003 PhD thesis made [[Glasgow Haskell Compiler|GHC]] support a kind of speculative execution with an abortion mechanism to back out in case of a bad choice called ''optimistic execution''.<ref name="Robert Ennals and Simon Peyton Jones">{{cite journal|url=https://www.microsoft.com/en-us/research/publication/optimistic-evaluation-fast-evaluation-strategy-non-strict-programs/|title=Optimistic Evaluation: a fast evaluation strategy for non-strict programs|first1=Simon Peyton|last1=Jones|first2=Robert|last2=Ennals|date=1 August 2003|access-date=15 May 2019|via=www.microsoft.com}}</ref> It was deemed too complicated.<ref>{{cite web | url=https://mail.haskell.org/pipermail/haskell/2006-August/018424.html | title=&#91;Haskell&#93; Optimistic Evaluation? | date=31 August 2006 }}</ref>

==Security vulnerabilities==

{{See also|Speculative execution CPU vulnerabilities}}

Starting in 2017, a series of [[vulnerability (computing)|security vulnerabilities]] were found in the implementations of speculative execution on common processor architectures which effectively enabled an elevation of [[privilege (computing)|privileges]].

These include:
* [[Foreshadow (security vulnerability)|Foreshadow]]
* [[Meltdown (security vulnerability)|Meltdown]]
* [[Microarchitectural Data Sampling]]
* [[Spectre (security vulnerability)|Spectre]]
* [[SPOILER (security vulnerability)|SPOILER]]
* [[Pacman (security vulnerability)|Pacman]]

== See also ==
* [[Anticiparallelism]]
* [[Out-of-order execution]]
* [[Slipstream (computer science)]]
* [[Speculative multithreading]]
* [[Hardware security bug]]
* [[Transient execution CPU vulnerability]]

==References==
{{Reflist|30em}}

{{Speculative execution exploits}}
{{CPU technologies}}

[[Category:Speculative execution| ]]
[[Category:Instruction processing]]
[[Category:Concurrency (computer science)]]