Speculative execution in computer systems is doing work, the result of which may not be needed. This performance optimization

Optimization (computer science)

In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...

 technique is used in pipelined

Instruction pipeline

An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....

 processors and other systems.

Main idea

Speculative execution is a performance optimization

Optimization (computer science)

In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...

. The main idea is to do work that may not be needed. The target is to provide more concurrency

Concurrency (computer science)

In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...

 if extra resources

Resource (computer science)

A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource...

 are available.

The following technologies employ this idea:

• Prefetching in memory
  Prefetching
  Prefetching may refer to:* Instruction prefetch, in computer architecture, a microprocessor speedup technique* Prefetch input queue , in computer architecture, pre-loading machine code from memory...
  
   and File system
  File system
  A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...
  
  
• Branch prediction
  Branch predictor
  In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline...
  
  
• Optimistic concurrency control
  Optimistic concurrency control
  In the field of relational database management systems, optimistic concurrency control is a concurrency control method that assumes that multiple transactions can complete without affecting each other, and that therefore transactions can proceed without locking the data resources that they affect...
  
   in database systems
  Relational database management system
  A relational database management system is a database management system that is based on the relational model as introduced by E. F. Codd. Most popular databases currently in use are based on the relational database model....
  
  

Processors

Modern pipelined

Instruction pipeline

An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....

 microprocessor

Microprocessor

A microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...

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. It turns out that in order to improve performance and utilization of computer resources, some instructions have to be scheduled ahead of time in a place that is not determined that such instructions have to be executed at all, ahead of branch

Branch predictor

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline...

.

Compilers

In compiler optimization

Compiler optimization

Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...

 for multiprocessing

Multiprocessing

Multiprocessing is the use of two or more central processing units within a single computer system. The term also refers to the ability of a system to support more than one processor and/or the ability to allocate tasks between them...

 systems, speculative execution involves an idle processor executing code in the next processor block, in case there is no dependency on code that could be running on other processors. The benefit of this scheme is reducing response time for individual processors and the overall system. However, there is a net penalty for the average case, since in the case of a bad bet, the pipelines should be flushed. The compiler is limited in issuing speculative execution instruction, since it requires hardware assistance to buffer the effects of speculatively-executed instructions. Without hardware support, the compiler could only issue speculative instructions which have no side effects

Side effect (computer science)

In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...

 in case of wrong speculation.

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 branch prediction. With limited resources eager execution should be employed carefully since the number of resources needed grows exponentially with each level of branches executed eagerly.

Lazy Evaluation

Lazy evaluation

Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...

 does not speculate. The incorporation of speculative execution into implementations of the Haskell programming language

Haskell (programming language)

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

 is a current research topic. Eager Haskell is designed around the idea of speculative execution. Recent versions of GHC

Glasgow Haskell Compiler

The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...

support a kind of speculative execution with an abortion mechanism to back out in case of a bad choice called optimistic execution.

External links

• "Speculative computation in Multilisp."