Speculative multithreading

Short description: Computer runtime parallelization technique

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)

This article's factual accuracy may be compromised due to out-of-date information. Please update this article to reflect recent events or newly available information. (March 2017)

|

This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2018) (Learn how and when to remove this template message)

|

(Learn how and when to remove this template message)

Thread Level Speculation (TLS), also known as Speculative Multi-threading, or Speculative Parallelization,[1] is a technique to speculatively execute a section of computer code that is anticipated to be executed later in parallel with the normal execution on a separate independent thread. Such a speculative thread may need to make assumptions about the values of input variables. If these prove to be invalid, then the portions of the speculative thread that rely on these input variables will need to be discarded and squashed. If the assumptions are correct the program can complete in a shorter time provided the thread was able to be scheduled efficiently.

## Description

TLS extracts threads from serial code and executes them speculatively in parallel with a safe thread. The speculative thread will need to be discarded or re-run if its presumptions on the input state prove to be invalid. It is a dynamic (runtime) parallelization technique that can uncover parallelism that static (compile-time) parallelization techniques may fail to exploit because at compile time thread independence cannot be guaranteed. For the technique to achieve the goal of reducing overall execute time, there must be available CPU resource that can be efficiently executed in parallel with the main safe thread.[2]

TLS assumes optimistically that a given portion of code (generally loops) can be safely executed in parallel. To do so, it divides the iteration space into chunks that are executed in parallel by different threads. A hardware or software monitor ensures that sequential semantics are kept (in other words, that the execution progresses as if the loop were executing sequentially). If a dependence violation appears, the speculative framework may choose to stop the entire parallel execution and restart it; to stop and restart the offending threads and all their successors, in order to be fed with correct data; or to stop exclusively the offending thread and its successors that have consumed incorrect data from it.[3]

## References

1. ↑ Estebanez, Alvaro (2017). "A Survey on Thread-Level Speculation Techniques". ACM Computing Surveys 49 (2): 1–39. doi:10.1145/2938369. https://dl.acm.org/doi/abs/10.1145/2938369.
2. ↑ Martínez, José F.; Torrellas, Josep (2002). "Speculative synchronization". Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) - ASPLOS '02. ACM. pp. 18. doi:10.1145/605397.605400. ISBN 1581135742. https://s3.amazonaws.com/academia.edu.documents/32836533/asplos02.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1542548785&Signature=wLPnjmhDH+0K/u5zWo1R/jna13Q=&response-content-disposition=inline; filename=Speculative_Synchronization_Applying_Thr.pdf.
3. ↑ García Yaguez, Alvaro (2014). "Squashing Alternatives for Software-based Speculative Parallelization". IEEE Transactions on Computers 63 (7): 1826–1839. doi:10.1109/TC.2013.46. Bibcode: 2014ITCmp..63.1826G.

## Further reading

* Yiapanis, Paraskevas; Brown, Gavin; Lujan, Mikel (2016). "Compiler-Driven Software Speculation for Thread-Level Parallelism". ACM Transactions on Programming Languages and Systems 38 (2): 1–45. doi:10.1145/2821505.

* Yiapanis, Paraskevas; Rosas-Ham, Demian; Brown, Gavin; Lujan, Mikel (2013). "Optimizing Software Runtime Systems for Speculative Parallelization". ACM Transactions on Architecture and Code Optimization 9 (4): 1–27. doi:10.1145/2400682.2400698.
* Llanos, Diego R. (2007). "New scheduling strategies for randomized incremental algorithms in the context of speculative parallelization". IEEE Transactions on Computers 56 (6): 839–852. doi:10.1109/TC.2007.1030. Bibcode: 2007ITCmp..56..839L.
* Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012). "Speculative separation for privatization and reductions". PLDI '12. pp. 359–370. doi:10.1145/2254064.2254107. http://liberty.princeton.edu/Publications/pldi12_privateer.pdf.
* Bhowmik, Anasua; Franklin, Manoj (2002). "A General Compiler Framework for Speculative Multithreading". SPAA '02. pp. 99–108. doi:10.1145/564870.564885.
* Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). "Softspec: Software-based Speculative Parallelism". FDDO-3. pp. 1–10. http://www.cag.lcs.mit.edu/softspec/FDDO.pdf.
* Chen, Michael K. (1998). "Exploiting Method-Level Parallelism in Single-Threaded Java Programs". PACT 1998. pp. 176–184. doi:10.1109/PACT.1998.727190.
* Chen, Michael K. (2003). "The Jrpm System for Dynamically Parallelizing Java Programs". ISCA '03. pp. 434–446. doi:10.1145/859618.859668.
* Cintra, Marcelo; Llanos, Diego R. (2003). "Toward Efficient and Robust Software Speculative Parallelization on Multiprocessors". PPoPP '03. pp. 13–24. doi:10.1145/781498.781501.
* Cook, Jonathan J. (2002). "Reverse Execution of Java Bytecode". The Computer Journal 45 (6): 608–619. doi:10.1093/comjnl/45.6.608.
* Quinones, Carlos Garcia; Madriles, Carlos; Sanchez, Jesus; Marcuello, Pedro; Gonzalez, Antonio; Tullsen, Dean M. (2005). "Mitosis Compiler: An Infrastructure for Speculative Threading Based on Pre-Computation Slices". PLDI '05. pp. 269–279. doi:10.1145/1065010.1065043.
* Hu, Shiwen; Bhargava, Ravi; John, Lizy Kurian (2003). "The Role of Return Value Prediction in Exploiting Speculative Method-Level Parallelism". JILP 5: 1–21. http://www.jilp.org/vol5/v5paper14.pdf.
* Kazi, Iffat H. (2000). A Dynamically Adaptive Parallelization Model Based on Speculative Multithreading (Ph.D. thesis). University of Minnesota. pp. 1–188.
* Pickett, Christopher J.F.; Verbrugge, Clark (2005). "SableSpMT: A Software Framework for Analysing Speculative Multithreading in Java". PASTE '05. pp. 59–66. doi:10.1145/1108792.1108809.
* Pickett, Christopher J.F.; Verbrugge, Clark (2005). "Software Thread Level Speculation for the Java Language and Virtual Machine Environment". LCPC '05. 4339. pp. 304–318. doi:10.1007/978-3-540-69330-7_21. http://www.sable.mcgill.ca/publications/papers/2005-5/pickett-05-software.pdf.
* Porter, Leo; Choi, Bumyong; Tullsen, Dean M. (2009). "Mapping Out a Path from Hardware Transactional Memory to Speculative Multithreading". PACT '09. pp. 313–324. doi:10.1109/PACT.2009.37.
* Rundberg, Peter; Stenstrom, Per (2001). "An All-Software Thread-Level Data Dependence Speculation System for Multiprocessors". JILP 3: 1–28. http://www.jilp.org/vol3/rundberg-jilp.pdf.
* Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). "The STAMPede Approach to Thread-Level Speculation". ACM Transactions on Computer Systems 23 (3): 253–300. doi:10.1145/1082469.1082471.
* Whaley, John; Kozyrakis, Christos (2005). "Heuristics for Profile-driven Method-level Speculative Parallelization". ICPP 2005. pp. 147–156. doi:10.1109/ICPP.2005.44.
* Renau, Jose (2006). "Energy-Efficient Thread-Level Speculation". IEEE Micro 26 (1): 80–91. doi:10.1109/MM.2006.11. Bibcode: 2006IMicr..26a..80R. http://www.soe.ucsc.edu/~renau/docs/toppicks06.pdf.
* Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Speculative Parallel Execution on JVM". pp. 1–20. http://www.cs.cf.ac.uk/hpjworkshop/papers/okpapers/speculative.ps.
* Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). "A Lightweight In-Place Implementation for Software Thread-Level Speculation". SPAA '09. pp. 1–10. doi:10.1145/1583991.1584050. http://timharris.co.uk/papers/2009-spaa.pdf.

* v
* t
* e

Parallel computing

General|

* Distributed computing
* Parallel computing
* Massively parallel
* Cloud computing
* High-performance computing
* Multiprocessing
* Manycore processor
* GPGPU
* Computer network
* Systolic array

Levels|

* Bit
* Instruction
* Thread
* Task
* Data
* Memory
* Loop
* Pipeline

Multithreading|

* Temporal
* Simultaneous (SMT)
* Speculative (SpMT)
* Preemptive
* Cooperative
* Clustered Multi-Thread (CMT)
* Hardware scout

Theory|

* PRAM model
* PEM Model
* Analysis of parallel algorithms
* Amdahl's law
* Gustafson's law
* Cost efficiency
* Karp–Flatt metric
* Slowdown
* Speedup

Elements|

* Process
* Thread
* Fiber
* Instruction window
* Array data structure

Coordination|

* Multiprocessing
* Memory coherency
* Cache coherency
* Cache invalidation
* Barrier
* Synchronization
* Application checkpointing

Programming|

* Stream processing
* Dataflow programming
* Models
* Implicit parallelism
* Explicit parallelism
* Concurrency
* Non-blocking algorithm

Hardware|

* Flynn's taxonomy
* SISD
* SIMD
* SIMT
* MISD
* MIMD
* Dataflow architecture
* Pipelined processor
* Superscalar processor
* Vector processor
* Multiprocessor
* symmetric
* asymmetric
* Memory
* shared
* distributed
* distributed shared
* UMA
* NUMA
* COMA
* Massively parallel computer
* Computer cluster
* Grid computer
* Hardware acceleration

APIs|

* Ateji PX
* Boost.Thread
* Chapel
* HPX
* Charm++
* Cilk
* Coarray Fortran
* CUDA
* HIP
* Dryad
* C++ AMP
* Global Arrays
* MPI
* OpenMP
* OpenCL
* OpenHMPP
* OpenACC
* TPL
* PLINQ
* PVM
* POSIX Threads
* RaftLib
* UPC
* TBB
* ZPL

Problems|

* Automatic parallelization
* Deadlock
* Livelock
* Deterministic algorithm
* Embarrassingly parallel
* Parallel slowdown
* Race condition
* Software lockout
* Scalability
* Starvation

* Category: parallel computing
* Media related to Parallel computing at Wikimedia Commons

* 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 multithreading. Read more

|

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