Speculative execution


Speculative execution

In computer science, speculative execution is the execution of code, the result of which may not be needed. In the context of functional programming, the term "speculative evaluation" is used instead.

Types

Generally, statements and definitions in a program can be divided into three types:
* things which must be run and are mandatory
* things which do not need to be run because they are irrelevant
* statements which cannot be proven to be in either of the first two groups

The first group does not benefit from speculative execution because its members need to run anyway.

The second group can be quietly discarded much like lazy evaluation would discard its members.

The third group is the target of speculative evaluation, as its members can be run concurrently with the mandatory computations until they are needed or shown to be of the second group; this concurrency means that speculative execution can be parallelized.

Function

Speculative execution is a performance optimization. It is only useful when early execution consumes less time and space than later execution would, and the savings are enough to compensate, in the long run, for the possible wasted effort of computing a value which is never used.

Modern pipelined microprocessors use speculative execution to reduce the cost of conditional branch instructions. When a conditional branch instruction is encountered, the processor guesses which way the branch is most likely to go (this is called branch prediction), and immediately starts executing instructions from that point. If the guess later proves to be incorrect, all computation past the branch point is discarded. The early execution is relatively cheap because the pipeline stages involved would otherwise lie dormant until the next instruction was known. However, wasted instructions consume CPU cycles that could have otherwise delivered performance, and on a laptop, those cycles consume batteries. There is always a penalty for a mispredicted branch. Many microprocessors (such as the Intel Pentium II and successors) have a conditional move instruction. This is an operation to move data, usually, between a register and memory, if a condition is met. There is no branching any more, and the misprediction penalty is less.

Eager Execution

Though it is seldom referred to as such, eager execution is also a form of speculative execution (although the situation is complicated by the presence of side effects). Early execution is often cheaper because values needed for the computation are likely to be available on the stack and need not be stored and later retrieved from the heap. It can also be substantially more expensive, for instance in the case of generating the list of integers from 1 to 1,000,000. Programmers writing code in a strict programming language avoid these cases by using explicit laziness or by circumlocution (which can become very elaborate).

Lazy Evaluation

Lazy evaluation does not speculate. The incorporation of speculative execution into implementations of the Haskell programming language is a current research topic. Eager Haskell is designed around the idea of speculative execution. Recent versions of GHC support a kind of speculative execution called optimistic execution. [http://research.microsoft.com/~simonpj/papers/optimistic/]

External links

* [http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html "Speculative computation in Multilisp."]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Speculative execution — Bei einer Speculative execution werden untätige Prozessor Ressourcen verwendet um für einen potentiellen zukünftigen Stand des Programmflusses Berechnung vorauszuführen und Ergebnisse bereitzuhalten. Hintergrund Speculative Execution ist eine… …   Deutsch Wikipedia

  • Speculative multithreading — (SpMT), also known as thread level speculation (TLS), is a dynamic parallelization technique that depends on out of order execution to achieve speedup on multiprocessor CPUs. It is a kind of speculative execution that occurs at the thread level… …   Wikipedia

  • Exécution spéculative — En informatique, L exécution spéculative correspond au lancement anticipé d une instruction, c est à dire sans être certain que celle ci ait réellement besoin d être exécutée. Types Généralement, on peut distinguer trois type d instructions et de …   Wikipédia en Français

  • Exécution out-of-order — L exécution out of order (« dans le désordre » en anglais) d instructions par un processeur consiste à réorganiser l ordre dans lequel les instructions d un programme vont s exécuter. Ces instructions ne sont alors pas forcément… …   Wikipédia en Français

  • exécution — ● n. f. ►EXEC Désigne le moment pendant lequelle le processeur travaille pour le programme, interprétant ses ordres, calculant, traitant ses données, etc. Par exemple: l exécution du programme s est très bien passée: seulement 92 % des bulletins… …   Dictionnaire d'informatique francophone

  • exécution spéculative — ● loc. f. ►EXEC Dans les plus récents processeurs, capacité à exécuter les instructions d un programme dans le désordre, par exemple celles qui suivent un branchement conditionnel avant qu on ne connaisse le résultat du test. En d autres termes,… …   Dictionnaire d'informatique francophone

  • Out-of-order execution — In computer engineering, out of order execution (OoOE or OOE) is a paradigm used in most high performance microprocessors to make use of instruction cycles that would otherwise be wasted by a certain type of costly delay. In this paradigm, a… …   Wikipedia

  • Comparison of CPU architectures — Contents 1 Factors 1.1 Bits 1.2 Operands 1.3 Endianess 2 Architectures …   Wikipedia

  • Instruction level parallelism — (ILP) is a measure of how many of the operations in a computer program can be performed simultaneously. Consider the following program: 1. e = a + b 2. f = c + d 3. g = e * fOperation 3 depends on the results of operations 1 and 2, so it cannot… …   Wikipedia

  • Central processing unit — CPU redirects here. For other uses, see CPU (disambiguation). An Intel 80486DX2 CPU from above An Intel 80486DX2 from below …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.