speculative execution parallel
**Speculative Execution in Parallel Systems** is the **technique of optimistically executing tasks in parallel before knowing whether their results will be needed** — gambling that the computation will be useful and discarding results if the speculation was wrong, converting sequential dependencies into parallel execution at the cost of potentially wasted work.
**Types of Speculative Parallelism**
| Type | What's Speculated | Example |
|------|-------------------|--------|
| Branch Speculation | Which branch will be taken | CPU branch prediction |
| Value Speculation | What value a variable will have | Memory value prediction |
| Thread-Level Speculation (TLS) | Whether loop iterations are independent | Parallel loop execution |
| Task Speculation | Which task results will be needed | Search/optimization |
| Speculative Locking | Whether lock will be acquired | Transactional execution |
**Thread-Level Speculation (TLS)**
- **Problem**: Loop iterations may have data dependencies → compiler can't parallelize.
- **TLS Approach**: Run iterations in parallel optimistically.
- Each thread buffers its memory writes (speculative state).
- Hardware or software checks for dependency violations.
- If violation detected: Roll back the younger thread's work and re-execute.
- If no violation: Commit speculative state.
**Hardware TLS (Historical)**
- Sun ROCK processor: Hardware support for TLS (cancelled).
- IBM POWER8/9: Hardware Transactional Memory can enable TLS.
- Intel TSX: Transactional Synchronization Extensions — limited TLS support.
- TSX disabled on many Intel CPUs due to bugs → HW TLS largely unrealized.
**Software Speculative Parallelism**
- **Speculative task execution**: For task DAGs where some edges are "maybe" dependencies.
- Execute tasks assuming no dependency → check at commit.
- If conflict: Replay dependent tasks.
- **Or-parallelism**: Try multiple search paths in parallel → use first to find solution, cancel rest.
- Used in: SAT solvers, game tree search, optimization.
**Speculation in Database Systems**
- **Optimistic Concurrency Control (OCC)**: Transactions execute without locks.
- At commit: Validate no conflicts with other transactions.
- If conflict: Abort and retry.
- Works well when conflicts are rare (read-heavy workloads).
**Cost-Benefit Analysis**
- Benefit: $T_{parallel} = T_{serial} / P$ when speculation is correct.
- Cost: Wasted work (power, memory, cache pollution) when wrong.
- Break-even: Speculation profitable when $P_{correct} > 1/P$ (probability correct × speedup > wasted work).
- In practice: Useful when speculation correctness rate > 80-90%.
**Modern Applications**
- **CPU branch prediction**: 95-99% accuracy → massive ILP gains.
- **Prefetching**: Speculate which cache lines will be needed → load ahead of demand.
- **Speculative decoding (LLM)**: Small model predicts next tokens → large model verifies in parallel → 2-3x inference speedup.
Speculative execution is **a fundamental technique for extracting parallelism from sequential programs** — by betting on likely outcomes and performing work optimistically, it overcomes the fundamental limits of data and control dependencies that would otherwise force serial execution.