Speculative execution

Short description: Computer optimization technique

Speculative execution is an 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 if extra resources are available. This approach is employed in a variety of areas, including branch prediction in pipelined processors, value prediction for exploiting value locality, prefetching memory and files, and optimistic concurrency control in database systems.[1][2][3]

Speculative multithreading is a special case of speculative execution.

## Contents

* 1 Overview
* 2 Variants
* 2.1 Eager execution
* 2.2 Predictive execution
* 2.3 Runahead
* 3 Related concepts
* 3.1 Lazy execution
* 4 Security vulnerabilities
* 5 See also
* 6 References

## Overview

Modern pipelined microprocessors 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.[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 section is an excerpt from Runahead[ edit ]

Runahead is a technique that allows a computer processor to speculatively pre-process instructions during cache miss cycles. The pre-processed instructions are used to generate instruction and data stream prefetches by executing instructions leading to cache misses (typically called long latency loads) before they would normally occur, effectively hiding memory latency. In runahead, the processor uses the idle execution resources to calculate instruction and data stream addresses using the available information that is independent of a cache miss. Once the processor has resolved the initial cache miss, all runahead results are discarded, and the processor resumes execution as normal. The primary use case of the technique is to mitigate the effects of the 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 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 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

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:

* Foreshadow
* Meltdown
* Microarchitectural Data Sampling
* Spectre
* SPOILER
* Pacman

## See also

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

## References

1. ↑ Lampson, Butler (2006). "Lazy and Speculative Execution in Computer Systems" (in en). 10th International Conference on Principles of Distributed Systems. 4305. Bordeaux, France: Springer. pp. 1–2. doi:10.1007/11945529_1. ISBN 978-3-540-49991-6. https://link.springer.com/chapter/10.1007/11945529_1.
2. ↑ 2.0 2.1 Raghavan, Prabhakar; Shachnai, Hadas; Yaniv, Mira (1998). "Dynamic schemes for speculative execution of code". IEEE. pp. 309–314. doi:10.1109/MASCOT.1998.693711.
3. ↑ Kung, H. T.; John T. Robinson (June 1981). "On optimistic methods for concurrency control". 6. https://apps.dtic.mil/dtic/tr/fulltext/u2/a081452.pdf.
4. ↑ Bernd Krieg-Brückner (1992). ESOP '92: 4th European Symposium on Programming, Rennes, France, February 26-28, 1992: proceedings. Springer. pp. 56–57. ISBN 978-3-540-55253-6. https://books.google.com/books?id=AQbhbphyOsoC&pg=PA56. Retrieved 18 January 2011.
5. ↑ Randy B. Osborne (1990-03-21). "Speculative Computation in Multilisp". Parallel Lisp: Languages and Systems (PS). Lecture Notes in Computer Science. 441. Digital Equipment Corporation Research Lab. pp. 103–137. doi:10.1007/BFb0024152. ISBN 3-540-52782-6. http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html. Retrieved 2018-01-26.
6. ↑ Jurij Šilc; Borut Robič; Theo Ungerer (1999). Processor architecture: from dataflow to superscalar and beyond. Springer. pp. 148–150. ISBN 978-3-540-64798-0. https://archive.org/details/processorarchite0000silc. Retrieved 21 January 2011.
7. ↑ Mark D., Hill; Norman P., Jouppi; Gourindar S., Sohi (2000). Readings in Computer Architecture. Morgan Kaufman. ISBN 9781558605398. https://books.google.com/books?id=I7o8teBhz5wC&q=processor+predictive+execution&pg=PA178. Retrieved 5 January 2018.
8. ↑ Pruett, Stephen; Patt, Yale (October 2021). "Branch Runahead: An Alternative to Branch Prediction for Impossible to Predict Branches". MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture. MICRO '21. New York, NY, USA: Association for Computing Machinery. pp. 804–815. doi:10.1145/3466752.3480053. ISBN 978-1-4503-8557-2. https://dl.acm.org/doi/10.1145/3466752.3480053.
9. ↑ Jones, Simon Peyton; Ennals, Robert (1 August 2003). Optimistic Evaluation: a fast evaluation strategy for non-strict programs. https://www.microsoft.com/en-us/research/publication/optimistic-evaluation-fast-evaluation-strategy-non-strict-programs/. Retrieved 15 May 2019.
10. ↑ "[Haskell] Optimistic Evaluation?". 31 August 2006. https://mail.haskell.org/pipermail/haskell/2006-August/018424.html.

* v
* t
* e

Speculative execution security vulnerabilities

Variants|

* Bounds Check Bypass (Spectre, Variant 1)
* Bounds Check Bypass Store (Spectre-NG)
* Branch Target Injection (Spectre, Variant 2)
* Foreshadow
* Lazy FP state restore (Spectre-NG)
* Microarchitectural Data Sampling
* Rogue Data Cache Load (Meltdown, Variant 3)
* Rogue System Register Read (Spectre-NG, Variant 3a)
* Speculative Store Bypass (Spectre-NG, Variant 4)
* Spoiler

Topics|

* Cache side-channel attack
* Hardware security bug
* Speculative execution
* Transient execution CPU vulnerabilities

* v
* t
* e

Processor technologies

Models|

* Turing machine
* Universal
* Post–Turing
* Quantum
* Belt machine
* Stack machine
* Finite-state machine
* with datapath
* Hierarchical
* Queue automaton
* Register machines
* Counter
* Pointer
* Random-access
* Random-access stored program

Architecture|

* Microarchitecture
* Von Neumann
* Harvard
* modified
* Dataflow
* Transport-triggered
* Cellular
* Endianness
* Memory access
* NUMA
* HUMA
* Load/store
* Register/memory
* Cache hierarchy
* Memory hierarchy
* Virtual memory
* Secondary storage
* Heterogeneous
* Fabric
* Multiprocessing
* Cognitive
* Neuromorphic

Instruction set
architectures|

| Types|

* CISC
* RISC
* Application-specific
* EDGE
* TRIPS
* VLIW
* EPIC
* MISC
* OISC
* NISC
* ZISC
* comparison
* addressing modes

|

* x86
* ARM
* MIPS
* Power ISA
* SPARC
* Itanium
* Unicore
* MicroBlaze
* RISC-V
* others

Execution|

| Instruction pipelining|

* Pipeline stall
* Operand forwarding
* Classic RISC pipeline

|

Hazards|

* Data dependency
* Structural
* Control
* False sharing

Out-of-order|

* Tomasulo algorithm
* Reservation station
* Re-order buffer
* Register renaming

Speculative|

* Branch prediction
* Memory dependence prediction

Parallelism|

| Level|

* Bit
* Bit-serial
* Word
* Instruction
* Pipelining
* Scalar
* Superscalar
* Task
* Thread
* Process
* Data
* Vector
* Memory
* Distributed

|

Multithreading|

* Temporal
* Simultaneous
* Hyperthreading
* Speculative
* Preemptive
* Cooperative

Flynn's taxonomy|

* SISD
* SIMD
* SWAR
* SIMT
* MISD
* MIMD
* SPMD

Processor
performance|

* Transistor count
* Instructions per cycle (IPC)
* Cycles per instruction (CPI)
* Instructions per second (IPS)
* Floating-point operations per second (FLOPS)
* Transactions per second (TPS)
* Synaptic updates per second (SUPS)
* Performance per watt (PPW)
* Cache performance metrics
* Computer performance by orders of magnitude

Types|

* Central processing unit (CPU)
* Graphics processing unit (GPU)
* GPGPU
* Vector
* Barrel
* Stream
* Coprocessor
* ASIC
* FPGA
* CPLD
* Multi-chip module (MCM)
* System in package (SiP)

| By application|

* Microprocessor
* Microcontroller
* Mobile
* Notebook
* Ultra-low-voltage
* ASIP

|

Systems
on chip|

* System on a chip (SoC)
* Multiprocessor (MPSoC)
* Programmable (PSoC)
* Network on a chip (NoC)

Hardware
accelerators|

* AI accelerator
* Vision processing unit (VPU)
* Physics processing unit (PPU)
* Digital signal processor (DSP)
* Tensor processing unit (TPU)
* Secure cryptoprocessor
* Network processor
* Baseband processor

Word size|

* 1-bit
* 2-bit
* 4-bit
* 8-bit
* 16-bit
* 32-bit
* 48-bit
* 64-bit
* 128-bit
* 256-bit
* 512-bit
* others
* variable

Core count|

* Single-core
* Multi-core
* Manycore
* Heterogeneous architecture

Components|

* Core
* Cache
* CPU cache
* replacement policies
* coherence
* Bus
* Clock rate
* Clock signal
* FIFO

| Functional units|

* Arithmetic logic unit (ALU)
* Address generation unit (AGU)
* Floating-point unit (FPU)
* Memory management unit (MMU)
* Load–store unit
* Translation lookaside buffer (TLB)
* Integrated memory controller (IMC)

|

Logic|

* Combinational
* Sequential
* Glue
* Logic gate
* Quantum
* Array

Registers|

* Processor register
* Status register
* Stack register
* Register file
* Memory buffer
* Program counter

Control unit|

* Instruction unit
* Data buffer
* Write buffer
* Microcode ROM
* Counter

Datapath|

* Multiplexer
* Demultiplexer
* Adder
* Multiplier
* CPU
* Binary decoder
* Address decoder
* Sum addressed decoder
* Barrel shifter

Circuitry|

* Integrated circuit
* 3D
* Mixed-signal
* Power management
* Boolean
* Digital
* Analog
* Quantum
* Switch

Power
management|

* PMU
* APM
* ACPI
* Dynamic frequency scaling
* Dynamic voltage scaling
* Clock gating
* Performance per watt (PPW)
* Race to sleep

Related|

* History of general-purpose CPUs
* Microprocessor chronology
* Processor design
* Digital electronics
* Hardware security module
* Semiconductor device fabrication
* Tick–tock model

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Speculative execution. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Speculative_execution&oldid=4151180"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template