Parallelism on the CPU

Updated

October 28, 2026

Parallelism on the CPU

Before programming thousands of lockstep cores on a GPU, we must build a mechanical understanding of how modern CPUs execute concurrent and parallel work. High-performance computing is fundamentally an exercise in orchestrating physical execution units while feeding them data fast enough to prevent pipeline stalls.

Modern CPUs extract performance across three distinct tiers of parallelism: 1. Instruction-Level Parallelism (ILP): Pipelining, superscalar dispatch, out-of-order execution, and branch prediction within a single core. 2. Data-Level Parallelism (SIMD): Single Instruction, Multiple Data execution where one machine instruction operates over a register packed with multiple independent values. 3. Thread-Level Parallelism (TLP): Multiple independent execution streams running concurrently across physical and logical processor cores.

1. Instruction-Level Parallelism (ILP) and Microarchitecture

A modern CPU core is not a simple sequential state machine. It is an asynchronous processing pipeline designed to retire multiple micro-operations (uops) per clock cycle.

       +--------------------------------------------------------+
       |                  Fetch & Branch Predict                |
       +---------------------------+----------------------------+
                                   |
       +---------------------------v----------------------------+
       |                  Decode & Macro-Op Fusion              |
       +---------------------------+----------------------------+
                                   |
       +---------------------------v----------------------------+
       |          Register Alias Table (RAT) & Rename           |
       +---------------------------+----------------------------+
                                   |
       +---------------------------v----------------------------+
       |            Reorder Buffer (ROB) & Reservation          |
       +-------+------------+------------+------------+---------+
               |            |            |            |
          +----v----+  +----v----+  +----v----+  +----v----+
          | ALU Port|  | ALU Port|  | SIMD/FMA|  |Load/Store|
          +---------+  +---------+  +---------+  +---------+

The Out-of-Order Engine

  1. Instruction Fetch & Branch Prediction: The CPU fetches instructions ahead of the current program counter using branch target buffers (BTB) and direction predictors. When a branch is mispredicted, the entire speculative pipeline must be flushed, costing 15 to 20 cycles of wasted energy.
  2. Decode and Micro-op Generation: Complex x86 instructions are broken down into simpler, RISC-like micro-operations (uops).
  3. Register Renaming & Reservation Stations: To break false register dependencies (Write-After-Read and Write-After-Write hazards), the CPU maps architectural registers (e.g., rax, ymm0) to a much larger pool of physical registers.
  4. Out-of-Order (OoO) Dispatch: Independent instructions whose operands are ready in the cache or register file execute out of program order across parallel execution ports.
  5. In-Order Retirement: The Reorder Buffer (ROB) ensures that memory state updates and architectural register commits happen in strict program order, guaranteeing consistent exception semantics.

2. SIMD: Vectorized Data Parallelism

While ILP extracts parallelism implicitly from scalar instructions, SIMD (Single Instruction, Multiple Data) makes data parallelism explicit. Instead of performing arithmetic on a single 32-bit floating-point value, SIMD instructions load, operate upon, and store entire vectors of values simultaneously.

Vector Widths Across Hardware Architectures

Vector Extension Vector Width 32-bit Floats per Vector Target Architecture
x86 SSE2 128-bit 4 Legacy x86-64
x86 AVX2 256-bit 8 Intel Haswell+ / AMD Zen2+
x86 AVX-512 512-bit 16 Intel Skylake-SP / Emerald Rapids, AMD Zen4+
x86 AVX10 256 / 512-bit 8 or 16 Modern Intel Architecture
ARM Neon 128-bit 4 Apple Silicon, ARM Neoverse V1/V2, Cortex-A
ARM SVE / SVE2 Scalable (128–2048b) Variable Fujitsu A64FX, AWS Graviton3/4

Explicit AVX2 Vector Operations in C++

When performance is paramount, reliance on compiler autovectorization is risky. Compilers frequently fail to vectorize loops due to pointer aliasing concerns or unknown loop boundary alignments. Engineers write architecture-specific intrinsic functions:

#include <immintrin.h>
#include <iostream>
#include <vector>

void vector_fma_avx2(const float* __restrict__ a,
                    const float* __restrict__ b,
                    const float* __restrict__ c,
                    float* __restrict__ out,
                    size_t n) {
    size_t i = 0;
    
    // Process 8 floats per iteration using 256-bit AVX2 registers
    for (; i + 8 <= n; i += 8) {
        // Load vectors from memory
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_loadu_ps(&c[i]);

        // Fused Multiply-Add: out = (va * vb) + vc
        // Computes 8 FMAs (16 floating point operations) in 4-5 cycles latency
        __m256 vres = _mm256_fmadd_ps(va, vb, vc);

        // Store back to destination
        _mm256_storeu_ps(&out[i], vres);
    }

    // Scalar cleanup tail loop
    for (; i < n; ++i) {
        out[i] = a[i] * b[i] + c[i];
    }
}

Alignment and Vector Loads

  • _mm256_loadu_ps: Unaligned load. Safe across any memory address, but incurs small penalty if crossing a 64-byte cache line boundary.
  • _mm256_load_ps: Aligned load. Requires the source address to be strictly 32-byte aligned (alignas(32) or posix_memalign). A non-aligned pointer will trigger a hardware general protection fault (SIGSEGV).

3. Thread-Level Parallelism: Heavyweight vs Lightweight

To leverage multi-core CPUs, applications distribute work across threads. How threads are modeled dramatically impacts context switching overhead and memory footprint.

OS Heavyweight Threads:
  [Kernel Scheduler] ---> [Core 0: OS Thread (2-8 MB Stack)]  (Switch: ~1-3 us)
                     ---> [Core 1: OS Thread (2-8 MB Stack)]

Lightweight User-Space Green Threads / Fibers:
  [OS Thread / SM]    ---> [Fiber A (2 KB)] -> [Fiber B (2 KB)] -> [Fiber C (2 KB)]

The Cost of OS Threads

POSIX threads (pthread_create) or OpenMP workers (#pragma omp parallel for) allocate their own kernel task structure and a fixed memory stack (typically 2 MB to 8 MB). - When an OS thread context switches, the CPU must switch privilege rings into the kernel, save and restore architectural register state (including wide AVX-512 state), and suffer TLB and cache pollution. - Total latency: 1,000 to 3,000 CPU cycles (1–3 microseconds).

User-Space Concurrency (M:N Models)

Modern programming environments decouple logical concurrency from physical OS threads: - Go Goroutines: Allocate a dynamic 2 KB stack that grows on demand. The runtime multiplexes thousands of goroutines across a fixed thread pool (GOMAXPROCS), switching in user space within ~10 to 50 nanoseconds. - Java Virtual Threads (Project Loom): Suspendable continuation objects stored on the garbage-collected heap. - Rust Tokio: Futures compiled into zero-allocation state machines driven by a lock-free work-stealing executor.

4. Cache Lines and False Sharing

CPU memory controllers do not fetch individual 4-byte floating-point numbers from system DRAM. All transfers between main memory and CPU caches occur in fixed chunks of 64 bytes, called cache lines.

The False Sharing Trap

When two distinct threads running on separate CPU cores write to independent variables that happen to sit within the same 64-byte cache line, the CPU hardware coherence engine (e.g., MESI protocol) must invalidate that entire cache line across both cores back and forth:

                  64-Byte Cache Line
+-----------------------------------+-----------------------------------+
| Thread 0 Counter: uint64_t (8 B)  | Thread 1 Counter: uint64_t (8 B)  |
+-----------------------------------+-----------------------------------+
                  ^                                   ^
                  |                                   |
          Core 0 writes                       Core 1 writes
          (Invalidates Core 1)                (Invalidates Core 0)

This phenomenon—false sharing—can slow down multi-threaded code by a factor of 50x to 100x, reducing parallel throughput below that of a single-threaded loop.

Remediation via Padding

// Bad: Threads write to adjacent elements in an array
struct BadThreadState {
    uint64_t counter; // 8 bytes -> adjacent elements share a 64B line!
};

// Good: Align to 64 bytes (the hardware cache line size)
struct alignas(64) GoodThreadState {
    uint64_t counter;
    // 56 bytes of implicit padding inserted by the compiler
};

5. Architectural Contrast: CPU vs GPU Design Philosophy

Why do GPUs dominate machine learning and scientific compute when CPUs have such sophisticated out-of-order execution engines?

CPU Architecture (Latency-Optimized):
+--------------------------------------------------------------+
| [Control: Branch Predictor, Out-of-Order Engine]             |
| [Large L1 / L2 / L3 Caches (Tens of Megabytes)]              |
| [A Few Powerful ALU / FMA Execution Cores (8-64 Cores)]      |
+--------------------------------------------------------------+

GPU Architecture (Throughput-Optimized):
+--------------------------------------------------------------+
| [Control] [Control] [Control] [Control]                      |
| [Thousands of Compact ALU / Tensor Cores]                    |
| [High-Bandwidth HBM3 / GDDR Memory Interface]                |
+--------------------------------------------------------------+
Dimension Modern Server CPU (e.g. AMD Genoa / Intel Xeon) Modern Data Center GPU (e.g. NVIDIA H100)
Optimization Target Minimum latency for a single sequence Maximum aggregate throughput
Physical Cores 64 – 128 complex cores 132 – 144 Streaming Multiprocessors (16,896 cores)
Control Logic Heavy: speculative, out-of-order Light: SIMT lockstep warps, in-order dispatch
Cache Hierarchy Massive: ~384 MB L3 cache Compact: 50 MB L2 cache, 228 KB SM SRAM
Memory Bandwidth 300 – 460 GB/s (DDR5) 3,350 GB/s (HBM3)
FP32 Compute 4 – 8 TFLOP/s 67 TFLOP/s (Vector) / 989 TFLOP/s (Tensor)

Understanding this trade-off is the foundation of accelerated computing: CPUs excel at complex branching, low latency, and irregular memory traversals. GPUs excel at massive arithmetic intensity and regular, uniform matrix operations.