Differences

This shows you the differences between two versions of the page.

--- parallel-computing [June 12, 2026 at 18:42] – external edit 127.0.0.1
+++ parallel-computing [August 22, 2026 at 15:22] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 # Parallel computing
-**Parallel computing** is a style of programming where a computation is broken into parts that run simultaneously across multiple processors, cores, or machines. The motivation is straightforward: a single core has a clock speed ceiling, and modern CPUs gain performance by adding more cores rather than running each core faster. To take advantage of that, programs have to be written with parallelism in mind.
-Not every program benefits equally. [[amdahls-law|Amdahl's law]] shows that the sequential fraction of a program — the part that cannot be parallelized — sets a hard ceiling on speedup regardless of how many cores you add. [[gustafsons-law|Gustafson's law]] is the more optimistic counterpart: if you scale the problem size alongside the hardware, speedup grows linearly. In practice, HPC workloads follow Gustafson's regime — you buy more nodes to solve a bigger problem, not just to solve the same one faster.
+**[Parallel computing](https://en.wikipedia.org/wiki/Parallel_computing)** is a computational model where work is broken into parts that execute simultaneously across multiple processors, cores, or machines. Modern CPUs gain performance through additional cores rather than clock speed increases, so exploiting parallelism is essential for performance.
-## Three paradigms
+[[amdahls-law|Amdahl's law]] shows the sequential fraction limits speedup; [[gustafsons-law|Gustafson's law]] shows that scaling problem size with hardware yields near-linear speedup.
-Parallel computing splits into three broad paradigms based on where the parallelism lives.
+## Example
-**Shared-memory parallelism** runs multiple threads on a single machine with a common address space. [[openmp|OpenMP]] is the standard approach in C, C++, and Fortran: a few `#pragma omp` directives turn a serial loop into a parallel one. Threads communicate by reading and writing shared variables, which makes synchronization — mutexes, barriers, atomics — the main source of bugs and overhead.
+This example shows a simple parallel computation using OpenMP.
-**Distributed-memory parallelism** runs processes across separate machines (or separate address spaces on one machine), each with its own private memory. [[mpi|MPI]] is the dominant standard. Processes communicate explicitly by sending and receiving messages. There is no shared state to race on, but the programmer is responsible for every byte that crosses a process boundary. MPI is the backbone of large cluster workloads.
-**GPU parallelism** offloads computation to a GPU, which can run thousands of lightweight threads simultaneously. CUDA is NVIDIA's programming model for this. GPU parallelism is best suited for problems where the same operation is applied to a large array of data — matrix multiplication, FFTs, stencil operations. The bottleneck is usually memory bandwidth and the cost of transferring data between host (CPU) memory and device (GPU) memory.
-## Performance and correctness
-Parallel programs introduce failure modes that serial programs don't have: race conditions, deadlocks, false sharing, memory ordering issues. A race condition occurs when two threads read and write shared data without synchronization and the outcome depends on the order of execution. A deadlock occurs when two threads are each waiting for a lock the other holds. False sharing is a subtler hardware-level issue: two threads write to different variables that happen to sit in the same cache line, causing the cache coherence protocol to thrash.
-On the performance side, the [[roofline-model|roofline model]] is a useful frame for understanding whether a kernel is compute-bound or memory-bandwidth-bound, which determines where to focus optimization effort. For quick empirical benchmarks, [[saxpy]] — a simple vector operation — is a standard starting point for measuring memory bandwidth.
-## Practice
-The fastest way to see parallelism pay off is to compile the same program twice — once without threading, once with — and time both. Here is a parallel sum using OpenMP:
 ```c
-// compile: gcc -O2 -fopenmp -o sum sum.c
+// compile: gcc -fopenmp -o parallel parallel.c
-// run: OMP_NUM_THREADS=4 ./sum
+// run: ./parallel
-// description: parallel reduction; compare timing against a serial baseline
+// description: parallel loop computing array sum
 #include <omp.h>
 #include <stdio.h>
-int main(void) {
+int main() {
-    long n = 1000000000L, sum = 0;
+    int arr[100];
-    double t = omp_get_wtime();
+    for (int i = 0; i < 100; i++) arr[i] = i;
-    #pragma omp parallel for reduction(+:sum)
-    for (long i = 0; i < n; i++)
+    int sum = 0;
-        sum += i;
+#pragma omp parallel for reduction(+:sum)
-    printf("sum=%ld  time=%.2fs\n", sum, omp_get_wtime() - t);
+    for (int i = 0; i < 100; i++) {
+        sum += arr[i];
+    }
+    printf("Sum: %d\n", sum);
     return 0;
 }
 ```
-Build and run both versions:
-```bash
-$ gcc -O2 -o sum_serial sum.c
-$ gcc -O2 -fopenmp -o sum_parallel sum.c
-$ ./sum_serial
-sum=499999999500000000  time=2.14s
-$ OMP_NUM_THREADS=4 ./sum_parallel
-sum=499999999500000000  time=0.57s
-```
-The parallel version runs roughly 4× faster on 4 cores. The answer is identical — the `reduction(+:sum)` clause handles synchronization. Try setting `OMP_NUM_THREADS` from 1 up to your core count and plot the speedup. It will flatten before reaching the theoretical maximum; that is Amdahl's law in action.
-## Concepts
-. [[amdahls-law|Amdahl's law]]
-. [[gustafsons-law|Gustafson's law]]
-. [[roofline-model|Roofline model]]
-. [[openmp|OpenMP]]
-. [[mpi|MPI]]
-. [[saxpy|SAXPY]]
-. [[semaphore|Semaphore]]
-. [[lock-free-queue|Lock-free queue]]
-. [[aba-problem|ABA problem]]
-. [[trace-monoid|Trace monoid]]
-. [[numbers-every-programmer-should-know|Numbers every programmer should know]]
-## Overview
-### Paradigms
-^ Paradigm ^ Memory model ^ API ^ Typical scale ^
-| Shared-memory | Common address space | [[openmp|OpenMP]], pthreads | Single node |
-| Distributed-memory | Private per process | [[mpi|MPI]] | Multi-node cluster |
-| GPU | Host + device | CUDA, HIP, OpenCL | Single GPU |
-| Hybrid | Mixed | MPI + OpenMP, MPI + CUDA | Multi-node + GPU |
-### Laws and models
-^ Name ^ Formula ^ What it predicts ^
-| [[amdahls-law|Amdahl's law]] | $S = \dfrac{1}{s + (1-s)/p}$ | Maximum speedup given serial fraction $s$ and $p$ processors |
-| [[gustafsons-law|Gustafson's law]] | $S = p - s(p-1)$ | Speedup when problem size scales with $p$ |
-| [[roofline-model|Roofline model]] | $\min(\pi,\; I \cdot \beta)$ | Whether a kernel is compute-bound or memory-bandwidth-bound |
-### Common failure modes
-^ Issue ^ Cause ^ Detection ^
-| Race condition | Concurrent unsynchronized read/write | Helgrind, ThreadSanitizer |
-| Deadlock | Circular lock dependency | Missing progress; `gdb` `info threads` |
-| False sharing | Two variables in the same cache line | `perf c2c`, cache miss counters |
-| Load imbalance | Unequal work distribution | Per-thread time profile |
-| Memory ordering | Relaxed atomics with wrong assumptions | Litmus tests; address and memory sanitizers |