parallel debugging
**Parallel Debugging** is the **discipline of detecting, diagnosing, and fixing concurrency bugs (race conditions, deadlocks, livelocks, ordering violations) in multi-threaded and distributed programs** — inherently more difficult than sequential debugging because bugs are non-deterministic, may only manifest under specific timing conditions, and often disappear when instrumentation (probes, printf) is added.
**Why Parallel Bugs Are Hard**
- **Non-deterministic**: Same input produces different behavior depending on thread scheduling.
- **Heisenbug effect**: Adding debug output changes timing → bug disappears.
- **Exponential interleavings**: N threads with M operations each → M^N possible interleavings.
- **Rare manifestation**: A race condition may trigger once in 10,000 runs.
**Types of Concurrency Bugs**
| Bug Type | Symptom | Detection Method |
|----------|---------|----------------|
| Data Race | Corrupted data, crashes | ThreadSanitizer, Helgrind |
| Deadlock | Program hangs | Lock ordering analysis, timeouts |
| Livelock | Threads running but no progress | Manual analysis |
| Atomicity Violation | Incorrect intermediate state visible | Model checking |
| Order Violation | Operations execute in wrong order | Happens-before analysis |
**Detection Tools**
**ThreadSanitizer (TSan)**
- Compiler instrumentation tool (GCC/Clang: `-fsanitize=thread`).
- Tracks all memory accesses and synchronization operations.
- Detects data races using the **happens-before** relation.
- Overhead: 5-15x slowdown, 5-10x memory increase.
- Widely used: Google runs TSan on most C++ codebases.
**Helgrind (Valgrind)**
- Valgrind-based race detector.
- Slower than TSan (20-50x overhead) but catches different bug classes.
- Also detects lock ordering violations (potential deadlocks).
**CUDA-Memcheck / Compute Sanitizer**
- NVIDIA tool for detecting GPU memory errors and race conditions.
- `compute-sanitizer --tool racecheck ./my_gpu_program`
- Detects shared memory races in CUDA kernels.
**Debugging Strategies**
- **Deterministic replay**: Record thread interleaving → replay exact same execution for debugging (rr, Intel Inspector).
- **Stress testing**: Run with many threads, vary CPU affinity, add sleep/yield to perturb timing.
- **Lock ordering discipline**: Always acquire locks in consistent global order → prevents deadlocks.
- **Immutability**: Share only immutable data between threads → eliminates data races by design.
- **Message passing**: Communicate via channels/queues instead of shared memory → eliminates shared mutable state.
Parallel debugging is **the most challenging aspect of concurrent programming** — the non-deterministic nature of concurrency bugs means that testing alone cannot guarantee their absence, making systematic approaches like sanitizers, formal methods, and race-free programming patterns essential for building reliable parallel systems.