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.