deterministic parallel
**Deterministic Parallel Execution** is the **guarantee that a parallel program produces bit-identical results across multiple runs, despite non-deterministic thread scheduling and floating-point operation ordering** — critical for debugging parallel applications, regulatory compliance in safety-critical systems, scientific reproducibility, and ML training where non-deterministic gradients can cause divergent training runs, requiring careful control of thread ordering, reduction algorithms, and random number generation to achieve reproducibility at the cost of some performance.
**Sources of Non-Determinism**
| Source | Why Non-Deterministic | Impact |
|--------|---------------------|--------|
| Floating-point reduction order | (a+b)+c ≠ a+(b+c) in FP | Different sum each run |
| Atomic operation ordering | Thread arrival order varies | Different accumulation order |
| GPU warp scheduling | SM schedules warps non-deterministically | Affects atomic/reduction order |
| Random number seeds | Different seeds per run | Different stochastic choices |
| cuDNN algorithm selection | Auto-tuner picks different algorithms | Different numerical results |
| Thread scheduling (OS) | OS scheduler non-deterministic | Timing-dependent behavior |
**Floating-Point Ordering Problem**
```python
# Sequential (deterministic):
result = 0.0
for x in data:
result += x # Always same order → same result
# Parallel (non-deterministic):
# Run 1: (a+b) + (c+d) = 10.000000000001
# Run 2: (a+c) + (b+d) = 10.000000000002
# Different tree reduction orderings → different floating-point rounding
```
**Making CUDA Deterministic**
```python
import torch
import os
# 1. Set random seeds everywhere
torch.manual_seed(42)
torch.cuda.manual_seed_all(42)
np.random.seed(42)
random.seed(42)
# 2. Force deterministic cuDNN
torch.backends.cudnn.deterministic = True
torch.backends.cudnn.benchmark = False
# 3. Force deterministic CUDA operations
os.environ["CUBLAS_WORKSPACE_CONFIG"] = ":4096:8"
torch.use_deterministic_algorithms(True)
# 4. Deterministic DataLoader
dataloader = DataLoader(dataset, shuffle=True,
generator=torch.Generator().manual_seed(42),
worker_init_fn=seed_worker)
```
**Deterministic Reductions**
| Approach | Deterministic? | Performance |
|----------|---------------|------------|
| Sequential accumulation | Yes | Slowest |
| Fixed-order tree reduction | Yes | Good |
| Atomic operations | No (arrival-order dependent) | Fast |
| Kahan summation (compensated) | More accurate but still order-dependent | Medium |
| Integer fixed-point | Yes (exact arithmetic) | Medium |
**Deterministic Parallel Sorting**
- Non-deterministic: Equal-key elements may appear in different order.
- Fix: Use stable sort (preserves insertion order of equal elements).
- GPU: CUB stable sort → deterministic key-value pairing.
**Cost of Determinism**
| Operation | Non-Deterministic | Deterministic | Overhead |
|-----------|------------------|---------------|----------|
| cuDNN convolution | Auto-tuned | Specific algorithm forced | 10-30% |
| Scatter/gather | Atomic-based | Sorted + sequential | 20-50% |
| Batch normalization | Parallel reduction | Fixed-order reduction | 5-15% |
| Overall training | Fastest | Reproducible | 10-25% |
**When Determinism Matters**
- **Debugging**: Non-deterministic bugs impossible to reproduce → determinism essential.
- **Regulatory**: Medical AI, autonomous vehicles → must prove reproducibility.
- **Science**: Research results must be reproducible by other labs.
- **Testing**: CI/CD for ML models → deterministic training for regression testing.
Deterministic parallel execution is **the reproducibility guarantee that transforms parallel computing from unpredictable to scientifically rigorous** — while non-determinism is the natural state of parallel programs due to floating-point arithmetic and thread scheduling, achieving bitwise reproducibility through fixed reduction orderings, seeded random generators, and deterministic algorithm selection is increasingly required for trustworthy AI, regulatory compliance, and the basic scientific principle that experiments must be reproducible.