Speculative execution is an

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

technique where a

computer system A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These progr ...

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 if extra

resources Resource refers to all the materials available in our environment which are technologically accessible, economically feasible and culturally sustainable and help us to satisfy our needs and wants. Resources can broadly be classified upon their a ...

are available. This approach is employed in a variety of areas, including

branch prediction In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow ...

in pipelined

processors A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, ...

, value prediction for exploiting value locality, prefetching

memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...

and files, and

optimistic concurrency control Optimistic concurrency control (OCC), also known as optimistic locking, is a concurrency control method applied to transactional systems such as relational database management systems and software transactional memory. OCC assumes that multiple tran ...

database systems In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...

.Lazy and Speculative Execution

Butler Lampson Butler W. Lampson, ForMemRS, (born December 23, 1943) is an American computer scientist best known for his contributions to the development and implementation of distributed personal computing. Education and early life After graduating from t ...

Microsoft Research Microsoft Research (MSR) is the research subsidiary of Microsoft. It was created in 1991 by Richard Rashid, Bill Gates and Nathan Myhrvold with the intent to advance state-of-the-art computing and solve difficult world problems through technologi ...

OPODIS, Bordeaux, France 12 December 2006 Speculative multithreading is a special case of speculative execution.

Overview

Modern pipelined

microprocessor A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circu ...

s use speculative execution to reduce the cost of

conditional branch A branch is an instruction in a computer program that can cause a computer to begin executing a different instruction sequence and thus deviate from its default behavior of executing instructions in order. ''Branch'' (or ''branching'', ''branc ...

instructions using schemes that predict the execution path of a program based on the history of branch executions. 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 A branch, sometimes called a ramus in botany, is a woody structural member connected to the central trunk (botany), trunk of a tree (or sometimes a shrub). Large branches are known as boughs and small branches are known as twigs. The term '' ...

Variants

''Speculative computation'' was a related earlier concept.

Eager execution

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

. With limited resources, eager execution should be employed carefully, since the number of resources needed grows

exponentially Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above * Exponential decay, decrease at a rate proportional to value *Exp ...

with each level of branch executed eagerly.

Predictive execution

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 In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow ...

s and

memory dependence prediction Memory dependence prediction is a technique, employed by high-performance out-of-order execution microprocessors that execute memory access operations (loads and stores) out of program order, to predict true dependencies between loads and stores at ...

. A generalized form is sometimes referred to as value prediction.

Related concepts

Lazy execution

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 () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lang ...

, a lazy language, is a current research topic.

Eager Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...

, 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''. It was deemed too complicated.https://mail.haskell.org/pipermail/haskell/2006-August/018424.html

Security vulnerabilities

Starting in 2017, a series of

security vulnerabilities Vulnerabilities are flaws in a computer system that weaken the overall security of the device/system. Vulnerabilities can be weaknesses in either the hardware itself, or the software that runs on the hardware. Vulnerabilities can be exploited by ...

were found in the implementations of speculative execution on common processor architectures which effectively enabled an elevation of privileges. These include: * Foreshadow *

Meltdown Meltdown may refer to: Science and technology * Nuclear meltdown, a severe nuclear reactor accident * Meltdown (security vulnerability), affecting computer processors * Mutational meltdown, in population genetics Arts and entertainment Music * Me ...

Microarchitectural Data Sampling The Microarchitectural Data Sampling (MDS) vulnerabilities are a set of weaknesses in Intel x86 microprocessors that use hyper-threading, and leak data across protection boundaries that are architecturally supposed to be secure. The attacks exp ...

Spectre Spectre, specter or the spectre may refer to: Religion and spirituality * Vision (spirituality) * Apparitional experience * Ghost Arts and entertainment Film and television * ''Spectre'' (1977 film), a made-for-television film produced and writ ...

SPOILER Spoiler is a security vulnerability on modern computer central processing units that use speculative execution. It exploits side-effects of speculative execution to improve the efficiency of Rowhammer and other related memory and cache attacks. Ac ...

Pacman originally called ''Puck Man'' in Japan, is a 1980 maze action video game developed and released by Namco for arcades. In North America, the game was released by Midway Manufacturing as part of its licensing agreement with Namco America. ...

References

{{CPU technologies Instruction processing Concurrency (computer science)