Parallel Programming Notes (OpenMP, MPI, CUDA)

15 August 2025 - 5 mins read time
Tags: parallel computing OpenMP MPI CUDA GPU

This note is adapted from course materials for 1TD070 Parallel and Distributed Programming at Uppsala University. Instructor: course teaching staff.

Central Question

Parallel programming asks: where is the time really going, and can work be reorganized so processors spend less time waiting?

Performance is shaped by three constraints:

Adding threads is rarely the first fix. A good workflow is: make the serial code clear, improve locality, expose parallelism, choose the memory model, then measure scaling.

Triangle connecting algorithmic parallelism, data movement, and synchronization overhead.
Parallel speed comes from balancing three forces: independent work, data locality, and coordination cost.

1. Speedup, Efficiency, and Scaling Limits

If $T_s$ is the best serial time and $T_p$ the time on $p$ processing units, then

\[S_p=\frac{T_s}{T_p},\qquad E_p=\frac{S_p}{p}.\]

Amdahl’s law shows the strong-scaling ceiling:

\[S_p\le \frac{1}{f+\frac{1-f}{p}},\]

where $f$ is the serial fraction. In practice, communication, synchronization, cache misses, and load imbalance increase the effective serial fraction.

Strong scaling fixes problem size and increases processors. Weak scaling grows problem size with processor count. Both are needed: strong scaling reveals overhead, while weak scaling reveals whether the method can handle larger problems.

2. Memory Hierarchy and Locality

Most programs do not run near peak floating-point throughput because data movement is the bottleneck. The hierarchy is registers, cache, DRAM, node memory, network, and storage.

Performance improves when code increases:

Matrix multiplication illustrates the principle. The naive algorithm performs $O(n^3)$ arithmetic, but poor loop order and cache reuse can make it memory-bound. Blocking or tiling reuses submatrices and shifts work toward compute-bound behavior.

Memory hierarchy and roofline-like relationship between arithmetic intensity and achievable performance.
Locality optimization raises arithmetic intensity, often unlocking more performance than simply adding parallel workers.

3. Shared Memory with OpenMP

OpenMP uses directives to express parallel regions over shared memory. Core constructs include parallel, for, single, sections, task, critical, atomic, barrier, and reduction.

Scheduling controls iteration distribution:

The key correctness question is dependence. Independent loop iterations parallelize directly. Reductions require structured combination. Prefix scans and loop-carried dependencies require algorithmic restructuring.

OpenMP loop scheduling and dependency patterns including independent work, reduction, and loop-carried dependence.
OpenMP performance depends on both scheduling and dependence structure; not every loop is parallel just because it has many iterations.

4. Distributed Memory with MPI

MPI assumes each process has private memory. Communication is explicit, so design begins with data partitioning.

A distributed algorithm should specify:

  1. domain decomposition,
  2. local computation,
  3. halo or neighbor exchange,
  4. collective communication,
  5. load-balance strategy.

Point-to-point communication uses send and receive calls. Nonblocking communication can overlap data transfer with useful computation if dependencies allow. Collectives express common patterns such as broadcast, scatter, gather, reduce, and all-reduce.

The central cost model is that communication has latency and bandwidth terms. Fewer, larger messages often beat many tiny messages, but memory pressure and overlap opportunities matter.

MPI domain decomposition with local subdomains, halo exchange, and collective reduction.
MPI scalability comes from decomposing data so most work is local and communication is structured, sparse, and overlappable.

5. GPU Programming with CUDA

CUDA separates host orchestration from device kernels:

Kernel<<<numBlocks, blockSize>>>(...);

Threads form blocks, blocks form a grid, and warps execute in SIMT fashion. GPUs reward regular data-parallel work and punish divergence, irregular memory access, and excessive synchronization.

Important patterns include:

For matrix multiplication, a tiled kernel loads subblocks into shared memory and reuses them across many multiply-adds. This reduces global memory traffic and is the same locality story as CPU blocking, but expressed in GPU memory hierarchy.

CUDA grid of thread blocks loading tiles from global memory into shared memory for matrix multiplication.
CUDA performance usually comes from mapping data-parallel work onto grids while staging reused data through shared memory.

6. Case Study: Gaussian Elimination and Dense Linear Algebra

Gaussian elimination with partial pivoting computes

\[PA=LU.\]

Naive elimination uses many low-intensity vector operations. Modern dense linear algebra reorganizes work into blocked updates so most time is spent in matrix-matrix operations. This is the BLAS-3 lesson:

The same idea appears in neural-network training, where matrix multiplication, elementwise maps, and reductions dominate forward and backward propagation.

What This Framework Lets Us Do

Parallel programming gives a practical path from multicore CPUs to distributed clusters and GPUs. It turns performance work into an evidence-driven process: dependency analysis, locality improvement, memory-model choice, and scaling measurement.

Where the Framework Stops Being Reliable

Benchmarks can mislead if problem size, NUMA placement, I/O, network contention, compiler flags, or warm-up behavior are uncontrolled. Race conditions and nondeterministic reductions can also make “fast” code scientifically wrong.

Where the Subject Leads Next

The next steps are performance modeling, roofline analysis, task runtimes, hybrid MPI+OpenMP, GPU collectives, distributed deep learning, and reproducible high-performance computing.

Technical and Editorial Audit

Main Sources Used in This Note