Parallelism

Levels of Parallelism

Instruction-Level Parallelism (ILP)

ILP is the number of independent instructions in a program that can execute simultaneously.

Limits on ILP:

Techniques to exploit ILP:

SIMD / Vector Parallelism

One instruction operates on a vector of values simultaneously.

x86 SIMD Extensions

Example: adding 8 pairs of floats in one AVX instruction vs 8 scalar adds:

// Scalar: 8 iterations
for (int i = 0; i < 8; i++) c[i] = a[i] + b[i];

// AVX (conceptually): one instruction
__m256 va = _mm256_loadu_ps(a);    // load 8 floats
__m256 vb = _mm256_loadu_ps(b);    // load 8 floats
__m256 vc = _mm256_add_ps(va, vb); // add 8 pairs

Thread-Level Parallelism (TLP)

SMT (Simultaneous Multi-Threading)

Multiple hardware threads (logical processors) share the same physical core's execution units. Intel calls this Hyper-Threading (HT).

HT adds ~5–30% throughput for mixed workloads; may reduce single-thread performance (resource competition). Disabled on some security-sensitive servers (Spectre-class attacks).

Multi-Core

Multiple complete CPU cores on one die, sharing L3 cache and memory controller.

Amdahl's Law

S(n) = 1 / (s + (1 − s) / n)

Where: - S(n) = speedup with n processors - s = serial fraction (cannot be parallelized) - (1 − s) = parallelizable fraction

Amdahl's Law shows that the serial fraction dominates at large core counts. Reducing s is more valuable than adding cores.

Gustafson's Law (Scaled Speedup)

When the problem size scales with the number of processors:

S(n) = n − s(n − 1)

More optimistic: if you fix time and scale problem size, efficiency stays high. Models scientific computing (e.g., larger simulations, not the same simulation faster).

Memory Consistency and Synchronization

Synchronization Primitives

Lock Implementation (x86)

// Compare-and-swap spin lock
void lock(int *l) {
    while (__sync_val_compare_and_swap(l, 0, 1) != 0)
        _mm_pause();  // hint to CPU: spin loop
}
void unlock(int *l) {
    __sync_lock_release(l);  // atomic store 0 with release fence
}

Cache Effects on Synchronization

- False sharing: two threads write to different variables that share a cache line. Cache coherence thrashes the line between cores even though the threads don't logically share data. - Fix: pad variables to 64-byte (cache line) boundaries.

// Bad: x and y share a cache line
struct { int x; int y; } shared;

// Good: each on its own line
struct { int x; char _pad[60]; int y; char _pad2[60]; } padded;

GPU Architecture

GPUs exemplify SIMT (Single Instruction Multiple Threads) — a hardware variant of SIMD:

NVIDIA H100 (Hopper) overview:

Multi-Processor Interconnects

Bisection bandwidth: bandwidth across a cut that divides the network into two equal halves. Key metric for all-to-all communication (e.g., MPI Allreduce in deep learning).