Speculative multithreading

Thread Level Speculation (TLS), also known as Speculative Multithreading (SpMT) is a runtime parallelization technique which uncovers parallelism that static (compile-time) parallelization techniques fail to exploit. This particular case of speculative execution occurs at the thread level as opposed to the instruction level and can be implemented both in hardware as well as in software.

Yiapanis, Paraskevas; Rosas-Ham, Demian; Brown, Gavin; Lujan, Mikel (2013). "Optimizing Software Runtime Systems for Speculative Parallelization". ACM Transactions on Architecture and Code Optimization (TACO). 9 (4). doi:10.1145/2400682.2400698.
Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012). "Speculative separation for privatization and reductions" (PDF). Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '12. pp. 359–370. doi:10.1145/2254064.2254107.
Bhowmik, Anasua; Franklin, Manoj (2002). "A General Compiler Framework for Speculative Multithreading". Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures. SPAA '02. pp. 99–108. doi:10.1145/564870.564885.
Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). Softspec: Software-based Speculative Parallelism (PDF). FDDO-3. pp. 1–10.
Chen, Michael K.; Olukotun, Kunle (1998). "Exploiting Method-Level Parallelism in Single-Threaded Java Programs". International Conference on Parallel Architectures and Compilation Techniques. PACT 1998. pp. 176–184. doi:10.1109/PACT.1998.727190.
Chen, Michael K.; Olukotun, Kunle (2003). "The Jrpm System for Dynamically Parallelizing Java Programs". Proceedings of the 30th annual international symposium on Computer architecture. 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". Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming. 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". Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation. 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" (PDF). JILP. 5: 1–21.
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". Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. 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" (PDF). Proceedings of the 18th international conference on Languages and Compilers for Parallel Computing. LCPC '05. LNCS. 4339. pp. 304–318. doi:10.1007/978-3-540-69330-7_21.
Porter, Leo; Choi, Bumyong; Tullsen, Dean M. (2009). "Mapping Out a Path from Hardware Transactional Memory to Speculative Multithreading". 18th International Conference on Parallel Architectures and Compilation Techniques. 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" (PDF). JILP. 3: 1–28.
Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). "The STAMPede Approach to Thread-Level Speculation". TOCS. 23 (3): 253–300. doi:10.1145/1082469.1082471.
Whaley, John; Kozyrakis, Christos (2005). "Heuristics for Profile-driven Method-level Speculative Parallelization". International Conference on Parallel Processing. ICPP 2005. pp. 147–156. doi:10.1109/ICPP.2005.44.
Renau, Jose; Strauss, Karin; Ceze, Luis; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). "Energy-Efficient Thread-Level Speculation" (PDF). IEEE Micro. 26 (1): 80–91. doi:10.1109/MM.2006.11.
Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Speculative Parallel Execution on JVM". UK Workshop on HPNC. pp. 1–20.
Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). "A Lightweight In-Place Implementation for Software Thread-Level Speculation" (PDF). Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. SPAA '09. pp. 1–10. doi:10.1145/1583991.1584050.

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 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
APIs	Ateji PX Boost.Thread Chapel Charm++ Cilk Coarray Fortran CUDA Dryad C++ AMP Global Arrays MPI OpenMP OpenCL OpenHMPP OpenACC TPL PLINQ PVM POSIX Threads RaftLib UPC TBB ZPL
Problems	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

CPU technologies
Architecture	Turing machine Post–Turing machine Universal Turing machine Quantum Turing machine Belt machine Stack machine Register machine Counter machine Pointer machine Random access machine Random access stored program machine Finite-state machine Queue automaton Von Neumann Harvard (modified) Dataflow TTA Cellular Artificial neural network Machine learning Deep learning Neural processing unit (NPU) Convolutional neural network Load/store architecture Register memory architecture Endianness FIFO Zero-copy NUMA HUMA HSA Mobile computing Surface computing Wearable computing Heterogeneous computing Parallel computing Concurrent computing Distributed computing Cloud computing Amorphous computing Ubiquitous computing Fabric computing Cognitive computing Unconventional computing Hypercomputation Quantum computing Adiabatic quantum computing Linear optical quantum computing Reversible computing Reverse computation Reconfigurable computing Optical computing Ternary computer Analogous computing Mechanical computing Hybrid computing Digital computing DNA computing Peptide computing Chemical computing Organic computing Wetware computing Neuromorphic computing Symmetric multiprocessing (SMP) Asymmetric multiprocessing (AMP) Cache hierarchy Memory hierarchy
ISA types	ASIP CISC RISC EDGE (TRIPS) VLIW (EPIC) MISC OISC NISC ZISC Comparison
ISAs	x86 z/Architecture ARM MIPS Power Architecture (PowerPC) SPARC Mill Itanium (IA-64) Alpha Prism SuperH V850 Clipper VAX Unicore PA-RISC MicroBlaze RISC-V
Word size	1-bit 2-bit 4-bit 8-bit 9-bit 10-bit 12-bit 15-bit 16-bit 18-bit 22-bit 24-bit 25-bit 26-bit 27-bit 31-bit 32-bit 33-bit 34-bit 36-bit 39-bit 40-bit 48-bit 50-bit 60-bit 64-bit 128-bit 256-bit 512-bit Variable
Execution	Instruction pipelining Bubble Operand forwarding Out-of-order execution Register renaming Speculative execution Branch predictor Memory dependence prediction Hazards
Parallelism level	Bit Bit-serial Word Instruction Pipelining Scalar Superscalar Task Thread Process Data Vector Memory
Multithreading	Temporal Simultaneous (SMT) (Hyper-threading) Speculative (SpMT) Preemptive Cooperative Clustered Multi-Thread (CMT) Hardware scout
Flynn's taxonomy	SISD SIMD (SWAR) SIMT MISD MIMD SPMD Addressing mode
CPU performance	Transistor count Instructions per second (IPS) Instructions per cycle (IPC) Cycles per instruction (CPI) Floating-point operations per second (FLOPS) Transactions per second (TPS) Synaptic Updates Per Second (SUPS) Performance per watt Orders of magnitude (computing) Cache performance measurement and metric CORDIC (FPU emulation)
Core count	Single-core processor Multi-core processor Manycore processor
Types	Central processing unit (CPU) GPGPU AI accelerator Vision processing unit (VPU) Vector processor Barrel processor Stream processor Digital signal processor (DSP) I/O processor/DMA controller Network processor Baseband processor Physics processing unit (PPU) Coprocessor Secure cryptoprocessor ASIC FPGA FPOA CPLD Microcontroller Microprocessor Mobile processor Notebook processor Ultra-low-voltage processor Multi-core processor Manycore processor Tile processor Multi-chip module (MCM) Chip stack multi-chip modules System on a chip (SoC) Multiprocessor system-on-chip (MPSoC) Programmable System-on-Chip (PSoC) Network on a chip (NoC)
Components	Execution unit (EU) Arithmetic logic unit (ALU) Address generation unit (AGU) Floating-point unit (FPU) Load-store unit (LSU) Branch predictor Unified Reservation Station Barrel shifter Uncore Sum addressed decoder (SAD) Front-side bus Back-side bus Northbridge (computing) Southbridge (computing) Adder (electronics) Binary multiplier Binary decoder Address decoder Multiplexer Demultiplexer Registers Cache Memory management unit (MMU) Input–output memory management unit (IOMMU) Integrated Memory Controller (IMC) Power Management Unit (PMU) Translation lookaside buffer (TLB) Stack engine Register file Processor register Hardware register Memory buffer register (MBR) Program counter Microcode ROM Datapath Control unit Instruction unit Re-order buffer Data buffer Write buffer Coprocessor Electronic switch Electronic circuit Integrated circuit Three-dimensional integrated circuit Boolean circuit Digital circuit Analog circuit Mixed-signal integrated circuit Power management integrated circuit Quantum circuit Logic gate Combinational logic Sequential logic Emitter-coupled logic (ECL) Transistor–transistor logic (TTL) Glue logic Quantum gate Gate array Counter (digital) Bus (computing) Semiconductor device Clock rate CPU multiplier Vision chip Memristor
Power management	APM ACPI Dynamic frequency scaling Dynamic voltage scaling Clock gating
Hardware security	Non-executable memory (NX bit) Memory Protection Extensions (Intel MPX) Intel Secure Key Hardware restriction (firmware) Software Guard Extensions (Intel SGX) Trusted Execution Technology Trusted Platform Module (TPM) Secure cryptoprocessor Hardware security module Hengzhi chip
Related	History of general-purpose CPUs Microprocessor chronology Processor design

Conheça Walt Disney World

Speculative multithreading

Further reading