Speculative execution

Source: Wikipedia, the free encyclopedia.

Speculative execution is an

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

database systems.[1][2][3]

Speculative multithreading is a special case of speculative execution.

Overview

Modern

conditional branch instructions using schemes that predict the execution path of a program based on the history of branch executions.[2] 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.[4]

Variants

Speculative computation was a related earlier concept.[5]

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 exponentially with each level of branch executed eagerly.[6]

Predictive execution

See also: Pipeline (computing)
Main article: 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 predictors and memory dependence prediction. A generalized form is sometimes referred to as value prediction.[7]

Runahead

This paragraph is an excerpt from Runahead.[edit]
memory wall. The technique may also be used for other purposes, such as pre-computing branch outcomes to achieve highly accurate branch prediction.[8]

Related concepts

Lazy execution

Main article: Lazy evaluation

Lazy execution is the opposite of eager execution, and does not involve speculation. The incorporation of speculative execution into implementations of the

Eager Haskell, a variant of the language, is designed around the idea of speculative execution. A 2003 PhD thesis made GHC support a kind of speculative execution with an abortion mechanism to back out in case of a bad choice called optimistic execution.[9] It was deemed too complicated.[10]

Security vulnerabilities

See also: Transient execution CPU vulnerability

Starting in 2017, a series of security vulnerabilities were found in the implementations of speculative execution on common processor architectures which effectively enabled an elevation of privileges.

These include:

See also

References

  1. ISBN 978-3-540-49991-6
    .
  2. ^
    doi:10.1109/MASCOT.1998.693711
    . Retrieved 18 January 2011.
  3. ^ Kung, H. T.; John T. Robinson (June 1981). "On optimistic methods for concurrency control" (PDF). ACM Trans. Database Syst. Vol. 6. Archived (PDF) from the original on August 31, 2019.
  4. ISBN 978-3-540-55253-6
    . Retrieved 18 January 2011.
  5. ISBN 3-540-52782-6. Archived from the original
    on 2017-02-07. Retrieved 2018-01-26.
  6. ISBN 978-3-540-64798-0
    . Retrieved 21 January 2011.
  7. ISBN 9781558605398
    . Retrieved 5 January 2018.
  8. S2CID 239011545
    .
  9. ^ Jones, Simon Peyton; Ennals, Robert (1 August 2003). "Optimistic Evaluation: a fast evaluation strategy for non-strict programs". Retrieved 15 May 2019 – via www.microsoft.com. {{cite journal}}: Cite journal requires |journal= (help)
  10. ^ "[Haskell] Optimistic Evaluation?". 31 August 2006.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Speculative_execution&oldid=1191590411"