parallel computing

**Parallel Computing** — the practice of performing multiple computations simultaneously by dividing work across multiple processing elements, enabling dramatic speedups for large-scale problems. **Fundamental Concepts** - **Parallelism vs. Concurrency**: Parallelism physically executes multiple tasks at the same instant (multiple cores). Concurrency manages multiple tasks that may overlap in time but don't necessarily run simultaneously (e.g., async I/O on a single core). - **Amdahl's Law**: The theoretical speedup is limited by the serial fraction of the program. If $f$ is the fraction that must run serially, maximum speedup with $N$ processors is $S = 1 / (f + (1-f)/N)$. Even with infinite processors, a program that is 10% serial can only achieve 10x speedup. - **Gustafson's Law**: A more optimistic view — as the problem size scales with processor count, the serial fraction becomes relatively smaller, enabling near-linear speedup for larger problems. - **Speed-Up and Efficiency**: Speedup $S = T_1 / T_p$ (serial time / parallel time). Efficiency $E = S / P$ (speedup / processors). Ideal is linear speedup ($S = P$), but communication overhead and load imbalance reduce efficiency. **Types of Parallelism** - **Data Parallelism**: Apply the same operation to different data elements simultaneously. Example: GPU SIMT (Single Instruction, Multiple Threads) executing the same kernel on thousands of data points. The dominant paradigm in deep learning training. - **Task Parallelism**: Different processing elements perform different tasks on different (or the same) data. Example: a pipeline where stage A preprocesses while stage B computes while stage C outputs. - **Pipeline Parallelism**: Divide a sequential computation into stages, each processed by a different unit. Used in CPU instruction pipelines and distributed model training (GPipe, PipeDream). - **Instruction-Level Parallelism (ILP)**: CPUs execute multiple independent instructions per cycle using superscalar execution, out-of-order execution, and speculative execution. **Parallel Architectures** - **Multi-Core CPUs**: 4-128+ cores sharing main memory (cache-coherent NUMA). Best for task-parallel and moderately data-parallel workloads. - **GPUs**: Thousands of simple cores organized in Streaming Multiprocessors (SMs). Optimized for massive data parallelism — matrix operations, rendering, scientific computing. NVIDIA CUDA ecosystem dominates. - **SIMD/Vector Units**: Single instruction operates on wide data vectors (AVX-512: 16 float32s per instruction). Present in both CPUs and GPUs. - **Distributed Systems**: Multiple machines connected by network (InfiniBand, Ethernet). Frameworks: MPI (Message Passing Interface), NCCL (GPU collective communications), Gloo. - **FPGAs/ASICs**: Custom hardware parallelism — FPGAs for reconfigurable parallelism, ASICs (like Google TPUs) for fixed-function maximum throughput. **Programming Models** - **Shared Memory**: Threads access common memory space. OpenMP (pragma-based), pthreads (POSIX), C++ std::thread. Challenges: race conditions, deadlocks, cache coherence overhead. - **Message Passing**: Processes communicate by sending/receiving messages. MPI is the standard for HPC clusters. No shared state — easier reasoning but explicit communication. - **GPU Programming**: CUDA (NVIDIA), ROCm/HIP (AMD), OpenCL (cross-platform). Write kernels that execute on thousands of threads organized in grids of thread blocks. - **Data-Parallel Frameworks**: MapReduce, Apache Spark, Dask — abstract parallelism over distributed datasets. Higher-level than raw threads/MPI. - **Async/Event-Driven**: Node.js event loop, Python asyncio, Rust tokio — concurrent I/O without threads. Not truly parallel but highly scalable for I/O-bound workloads. **Key Challenges** - **Synchronization**: Coordinating access to shared resources. Mutexes, semaphores, barriers, and atomic operations add overhead and risk deadlock. - **Communication Overhead**: Moving data between processors/nodes takes time. The computation-to-communication ratio determines parallel efficiency. - **Load Balancing**: Uneven work distribution leaves processors idle. Dynamic scheduling and work-stealing algorithms help. - **Memory Consistency**: Different cores may see memory updates in different orders. Memory models (sequential consistency, relaxed ordering) define guarantees. - **Debugging**: Race conditions and Heisenbugs are notoriously difficult to reproduce and diagnose. Tools: ThreadSanitizer, CUDA-memcheck, Intel Inspector. **Parallel Computing in AI/ML** - **Data Parallelism**: Replicate the model across GPUs, split mini-batches, average gradients (PyTorch DDP, Horovod). - **Model/Tensor Parallelism**: Partition model layers across GPUs (Megatron-LM column/row parallelism). - **Pipeline Parallelism**: Split model layers into stages across GPUs with micro-batch pipelining. - **3D Parallelism**: Combine data + tensor + pipeline parallelism for training models with hundreds of billions of parameters (GPT-3, LLaMA 405B). **Parallel Computing** is the engine behind modern HPC, AI training, and real-time systems — understanding its principles, architectures, and trade-offs is essential for leveraging hardware effectively.