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 [June 15, 2026 at 15:47] (current) – Ivan Janevski
@@ Line 4: / Line 4: @@
 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.
-## Three paradigms
+## Map of parallel computing
-Parallel computing splits into three broad paradigms based on where the parallelism lives.
-**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.
-**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
-// run: OMP_NUM_THREADS=4 ./sum
-// description: parallel reduction; compare timing against a serial baseline
-#include <omp.h>
-#include <stdio.h>
-int main(void) {
-    long n = 1000000000L, sum = 0;
-    double t = omp_get_wtime();
-    #pragma omp parallel for reduction(+:sum)
-    for (long i = 0; i < n; i++)
-        sum += i;
-    printf("sum=%ld  time=%.2fs\n", sum, omp_get_wtime() - t);
-    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 |
+ - [[introduction-to-parallel-computing]]
+ - [[saxpy]]
+ - [[synchronization-primitve]]
+   - [[sync-semaphore]]
+   - [[sync-mutex]]
+   - [[sync-monitor]]
+   - [[sync-linda]]
+   - [[sync-csp]]
+   - [[sync-mbox]]
+ - [[numbers-every-programmer-should-know]]
+ - [[amdahls-law]]
+ - [[gustafsons-law]]
+ - [[cache]]
+   - [[l1-cache]]
+   - [[l2-cache]]
+   - [[l3-cache]]
+   - [[cache-coherence]]
+     - [[cache-snoopy-protocols]]
+        - [[wti]]
+        - [[msi]]
+        - [[mesi]]
+        - [[moesi]]
+        - [[dragon]]
+        - [[firefly]]
+     - [[cache-directory-protocols]]
+ - [[cuda]]
+ - [[openmp]]
+ - [[mpi]]
+ - [[queuing-theory]]
+ - [[numa]]
+ - [[false-sharing]]
+ - [[aba-problem]]
+ - [[trace-monoid]]
+ - [[hazard-pointer]]
+ - [[cache-coherence]]
+ - [[roofline-model]]
+ - [[numa]]
+ - [[embarrassingly-parallel]]
+ - [[fork-join-model]]
+ - [[rcu]]
+ - [[lock]]
+ - [[lock-convoy]]
+ - [[lock-contention]]
+ - [[spinlock]]
+ - [[smp]]
+ - [[flops]]
+   - [[gflops]]
+   - [[tflops]]
+ - [[atomics]]
+   - [[atomic-ops]]
+     - [[atomic-load-store]]
+       - [[atomic-load]]
+       - [[atomic-store]]
+     - [[atomic-read-modify-write]]
+       - [[atomic-test-and-set]]
+       - [[atomic-exchange]] or [[xchg]]
+       - [[atomic-compare-and-swap]] or [[cas]]
+     - [[atomic-fetch-modify]]
+       - [[atomic-fetch-arithmetic]]
+         - [[atomic-fetch-inc]]
+         - [[atomic-fetch-dec]]
+         - [[atomic-fetch-add]]
+         - [[atomic-fetch-sub]]
+       - [[atomic-fetch-bitwise]]
+         - [[atomic-fetch-and]]
+         - [[atomic-fetch-or]]
+         - [[atomic-fetch-xor]]
+       - [[atomic-fetch-reduce]]
+         - [[atomic-fetch-min]]
+         - [[atomic-fetch-max]]
+     - [[atomic-flag]]
+     - [[atomic-wait-notify]]
+       - [[atomic-wait]]
+       - [[atomic-notify-one]]
+       - [[atomic-notify-all]]
+   - [[lock-free-queue]]
+   - [[memory-order]]
+     - [[memory-order-relaxed]]
+     - [[memory-order-consume]]
+     - [[memory-order-acquire]]
+     - [[memory-order-acq-rel]]
+     - [[memory-order-seq-cst]]
+ - [[treiber-stack]]
+ - [[michael-scott-queue]]
+ - [[bespoke-algorithm]]
+ - [[interconnect]]
+   - [[infiniband]]
+   - [[rdma]]