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 13, 2026 at 03:13] – external edit 127.0.0.1parallel-computing [June 15, 2026 at 15:47] (current) – Ivan Janevski
Line 6: Line 6:
 ## Map of parallel computing ## Map of parallel computing
  
 +
 + - [[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]]  - [[openmp]]
  - [[mpi]]  - [[mpi]]
- + - [[queuing-theory]] 
-## Three paradigms + - [[numa]] 
- + - [[false-sharing]] 
-Parallel computing splits into three broad paradigms based on where the parallelism lives. + - [[aba-problem]] 
- + - [[trace-monoid]] 
-**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. + - [[hazard-pointer]] 
- + - [[cache-coherence]] 
-**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. + - [[roofline-model]] 
- + - [[numa]] 
-**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. + - [[embarrassingly-parallel]] 
- + - [[fork-join-model]] 
-## Performance and correctness + - [[rcu]] 
- + - [[lock]] 
-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. + - [[lock-convoy]] 
- + - [[lock-contention]] 
-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. + - [[spinlock]] 
- + - [[smp]] 
-## Practice + - [[flops]] 
- +   - [[gflops]] 
-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: +   - [[tflops]] 
- + - [[atomics]] 
-```c +   - [[atomic-ops]] 
-// compile: gcc -O2 -fopenmp -o sum sum.c +     - [[atomic-load-store]] 
-// run: OMP_NUM_THREADS=4 ./sum +       - [[atomic-load]] 
-// description: parallel reduction; compare timing against a serial baseline +       - [[atomic-store]] 
- +     - [[atomic-read-modify-write]] 
-#include <omp.h> +       - [[atomic-test-and-set]] 
-#include <stdio.h> +       - [[atomic-exchange]] or [[xchg]] 
- +       - [[atomic-compare-and-swap]] or [[cas]] 
-int main(void) { +     - [[atomic-fetch-modify]] 
-    long n = 1000000000L, sum = 0; +       - [[atomic-fetch-arithmetic]]  
-    double t = omp_get_wtime(); +         - [[atomic-fetch-inc]] 
-    #pragma omp parallel for reduction(+:sum) +         - [[atomic-fetch-dec]] 
-    for (long i = 0; i < n; i++) +         - [[atomic-fetch-add]] 
-        sum += i; +         - [[atomic-fetch-sub]] 
-    printf("sum=%ld  time=%.2fs\n", sum, omp_get_wtime() - t); +       - [[atomic-fetch-bitwise]] 
-    return 0; +         - [[atomic-fetch-and]] 
-} +         - [[atomic-fetch-or]] 
-``` +         - [[atomic-fetch-xor]] 
- +       - [[atomic-fetch-reduce]] 
-Build and run both versions: +         - [[atomic-fetch-min]] 
- +         - [[atomic-fetch-max]] 
-```bash +     - [[atomic-flag]] 
-$ gcc -O2 -o sum_serial sum.c +     - [[atomic-wait-notify]] 
-$ gcc -O2 -fopenmp -o sum_parallel sum.c +       - [[atomic-wait]]  
-$ ./sum_serial +       - [[atomic-notify-one]] 
-sum=499999999500000000  time=2.14s +       - [[atomic-notify-all]] 
-$ OMP_NUM_THREADS=4 ./sum_parallel +   - [[lock-free-queue]] 
-sum=499999999500000000  time=0.57s +   - [[memory-order]] 
-``` +     - [[memory-order-relaxed]] 
- +     - [[memory-order-consume]] 
-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. +     - [[memory-order-acquire]] 
- +     - [[memory-order-acq-rel]] 
-## Concepts +     - [[memory-order-seq-cst]] 
- + - [[treiber-stack]] 
- 1. [[amdahls-law|Amdahl's law]] + - [[michael-scott-queue]] 
- 2. [[gustafsons-law|Gustafson's law]] + - [[bespoke-algorithm]] 
- 3. [[roofline-model|Roofline model]] + - [[interconnect]] 
- 4. [[openmp|OpenMP]] +   - [[infiniband]] 
- 5. [[mpi|MPI]] +   - [[rdma]]
- 6. [[saxpy|SAXPY]] +
- 7. [[semaphore|Semaphore]] +
- 8. [[lock-free-queue|Lock-free queue]] +
- 9. [[aba-problem|ABA problem]] +
- 10. [[trace-monoid|Trace monoid]] +
- 11. [[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 | +
parallel-computing.1781320400.txt.gz · Last modified: by 127.0.0.1