Ivan's wiki

Site Tools

parallel-computing

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
parallel-computing [June 15, 2026 at 07:41] – Ivan Janevskiparallel-computing [June 15, 2026 at 15:47] (current) – Ivan Janevski
Line 7: Line 7:
  
  
- 1. [[amdahls-law|Amdahl's law]] + - [[introduction-to-parallel-computing]] 
- 2. [[gustafsons-law|Gustafson's law]] + - [[saxpy]] 
- 3. [[roofline-model|Roofline model]] + - [[synchronization-primitve]] 
- 4. [[openmp|OpenMP]] +   - [[sync-semaphore]] 
- 5. [[mpi|MPI]] +   - [[sync-mutex]] 
- 6. [[saxpy|SAXPY]] +   - [[sync-monitor]] 
- 7. [[semaphore|Semaphore]] +   - [[sync-linda]] 
- 8. [[lock-free-queue|Lock-free queue]] +   - [[sync-csp]] 
- 9. [[aba-problem|ABA problem]] +   - [[sync-mbox]] 
- 10. [[trace-monoid|Trace monoid]] + - [[numbers-every-programmer-should-know]] 
- 11. [[numbers-every-programmer-should-know|Numbers every programmer should know]] + - [[amdahls-law]] 
- + - [[gustafsons-law]] 
- + - [[cache]] 
-## Three paradigms +   - [[l1-cache]] 
- +   - [[l2-cache]] 
-Parallel computing splits into three broad paradigms based on where the parallelism lives. +   - [[l3-cache]] 
- +   - [[cache-coherence]] 
-**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. +     - [[cache-snoopy-protocols]] 
- +        - [[wti]] 
-**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. +        - [[msi]] 
- +        - [[mesi]] 
-**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. +        - [[moesi]] 
- +        - [[dragon]] 
-## Performance and correctness +        - [[firefly]] 
- +     - [[cache-directory-protocols]] 
-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. + - [[cuda]] 
- + - [[openmp]] 
-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. + - [[mpi]] 
- + - [[queuing-theory]] 
-## Practice + - [[numa]] 
- + - [[false-sharing]] 
-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: + - [[aba-problem]] 
- + - [[trace-monoid]] 
-```c + - [[hazard-pointer]] 
-// compile: gcc -O2 -fopenmp -o sum sum.c + - [[cache-coherence]] 
-// run: OMP_NUM_THREADS=4 ./sum + - [[roofline-model]] 
-// description: parallel reduction; compare timing against a serial baseline + - [[numa]] 
- + - [[embarrassingly-parallel]] 
-#include <omp.h> + - [[fork-join-model]] 
-#include <stdio.h> + - [[rcu]] 
- + - [[lock]] 
-int main(void) { + - [[lock-convoy]] 
-    long n = 1000000000L, sum = 0; + - [[lock-contention]] 
-    double t = omp_get_wtime(); + - [[spinlock]] 
-    #pragma omp parallel for reduction(+:sum) + - [[smp]] 
-    for (long i = 0; i < n; i++) + - [[flops]] 
-        sum += i; +   - [[gflops]] 
-    printf("sum=%ld  time=%.2fs\n", sum, omp_get_wtime() - t); +   - [[tflops]] 
-    return 0; + - [[atomics]] 
-} +   - [[atomic-ops]] 
-``` +     - [[atomic-load-store]] 
- +       - [[atomic-load]] 
-Build and run both versions: +       - [[atomic-store]] 
- +     - [[atomic-read-modify-write]] 
-```bash +       - [[atomic-test-and-set]] 
-$ gcc -O2 -o sum_serial sum.c +       - [[atomic-exchange]] or [[xchg]] 
-$ gcc -O2 -fopenmp -o sum_parallel sum.c +       - [[atomic-compare-and-swap]] or [[cas]] 
-$ ./sum_serial +     - [[atomic-fetch-modify]] 
-sum=499999999500000000  time=2.14s +       - [[atomic-fetch-arithmetic]]  
-$ OMP_NUM_THREADS=4 ./sum_parallel +         - [[atomic-fetch-inc]] 
-sum=499999999500000000  time=0.57s +         - [[atomic-fetch-dec]] 
-``` +         - [[atomic-fetch-add]] 
- +         - [[atomic-fetch-sub]] 
-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. +       - [[atomic-fetch-bitwise]] 
- +         - [[atomic-fetch-and]] 
-## Overview +         - [[atomic-fetch-or]] 
- +         - [[atomic-fetch-xor]] 
-### Paradigms +       - [[atomic-fetch-reduce]] 
- +         - [[atomic-fetch-min]] 
-^ Paradigm ^ Memory model ^ API ^ Typical scale ^ +         - [[atomic-fetch-max]] 
-| Shared-memory | Common address space | [[openmp|OpenMP]], pthreads | Single node | +     - [[atomic-flag]] 
-| Distributed-memory | Private per process | [[mpi|MPI]] | Multi-node cluster | +     - [[atomic-wait-notify]] 
-| GPU | Host + device | CUDA, HIP, OpenCL | Single GPU | +       - [[atomic-wait]]  
-| Hybrid | Mixed | MPI + OpenMP, MPI + CUDA | Multi-node + GPU | +       - [[atomic-notify-one]] 
- +       - [[atomic-notify-all]] 
-### Laws and models +   - [[lock-free-queue]] 
- +   - [[memory-order]] 
-^ Name ^ Formula ^ What it predicts ^ +     - [[memory-order-relaxed]] 
-| [[amdahls-law|Amdahl's law]] | $S = \dfrac{1}{s + (1-s)/p}$ | Maximum speedup given serial fraction $s$ and $p$ processors | +     - [[memory-order-consume]] 
-| [[gustafsons-law|Gustafson's law]] | $S = p - s(p-1)$ | Speedup when problem size scales with $p$ | +     - [[memory-order-acquire]] 
-| [[roofline-model|Roofline model]] | $\min(\pi,\; I \cdot \beta)$ | Whether a kernel is compute-bound or memory-bandwidth-bound | +     - [[memory-order-acq-rel]] 
- +     - [[memory-order-seq-cst]] 
-### Common failure modes + - [[treiber-stack]] 
- + - [[michael-scott-queue]] 
-^ Issue ^ Cause ^ Detection ^ + - [[bespoke-algorithm]] 
-| Race condition | Concurrent unsynchronized read/write | Helgrind, ThreadSanitizer | + - [[interconnect]] 
-| Deadlock | Circular lock dependency | Missing progress; `gdb` `info threads` | +   - [[infiniband]] 
-| False sharing | Two variables in the same cache line | `perf c2c`, cache miss counters | +   - [[rdma]]
-| Load imbalance | Unequal work distribution | Per-thread time profile | +
-| Memory ordering | Relaxed atomics with wrong assumptions | Litmus tests; address and memory sanitizers | +
parallel-computing.1781509281.txt.gz · Last modified: by Ivan Janevski