gpu-multithreading

name	gpu-multithreading
description	Practitioner knowledge base for parallel, multithreaded, and GPU programming — the design methodology, performance laws, and cross-technology optimization playbook. Use when designing or optimizing parallel software: choosing a parallel decomposition (PCAM, geometric/pipeline/master-worker patterns); reasoning about speedup and scalability (Amdahl, Gustafson, roofline, arithmetic intensity); writing shared-memory code (C++ threads, mutexes, atomics, memory_order, condition variables, lock-free/CAS, false sharing, deadlock); distributed-memory message passing (MPI, domain decomposition, halo exchange, collectives); GPU programming (CUDA/OpenCL thread hierarchy, warps, coalescing, shared-memory tiling, occupancy, host-device transfer); directive-based parallelism (OpenMP fork-join, data-sharing clauses, reductions); OpenMP GPU offload in depth (target/teams/distribute, the map clause and target-data regions, declare target, unified shared memory, async multi-device offload, the Eightfold Path to performance); high-level GPU template libraries (Thrust transform/reduce/scan/sort); load balancing (static/DLT, dynamic/work-stealing/master-worker); or diagnosing parallel performance and correctness pitfalls (data races, uncoalesced access, benchmark-timing errors, floating-point non-reproducibility). Self-contained: the CUDA, MPI, OpenMP, and OpenCL chapters carry concrete APIs, host-program skeletons, code, and parameter tables — usable for hands-on coding, not just design.
allowed-tools	["Read","Grep"]
argument-hint	["topic","technology (cuda/mpi/openmp)","pattern","or chapter (e.g. ch03)"]

GPU & Multithreaded Parallel Programming

Scope: design methodology · performance laws · shared/distributed/GPU programming models · OpenMP GPU offload · optimization | Chapters: 13 | Generated: 2026-06-09

How to Use This Skill

• Without arguments — load the core decision rules below.
• With a topic — ask about decomposition, Amdahl, coalescing, false sharing, load balancing, memory_order; I find and read the relevant chapter.
• With a technology — ask about CUDA, MPI, OpenMP; I load that chapter.
• With a chapter — ask for ch03; I load that file.

When you ask about something not in the Core section, I read the relevant chapter (and cheatsheet.md / patterns.md / glossary.md). The CUDA, MPI, OpenMP, and OpenCL chapters are self-contained — they carry concrete APIs, host-program skeletons, code, and parameter tables for hands-on coding.

---

Core Decision Framework

Pick the programming model from the memory model (Ch 1)

Shared address space, one node → threads / OpenMP. Separate address spaces, many nodes → MPI. Massive data-parallel arithmetic → GPU (CUDA / OpenCL / Thrust). Real HPC node → hybrid (MPI + OpenMP/GPU). CPUs hide latency with caches; GPUs hide it with occupancy — algorithms must match.

Design with PCAM + a decomposition pattern (Ch 2)

Partition → Communicate → Agglomerate → Map. The task dependency graph is the central artifact. Pattern by work shape: embarrassingly parallel (independent), divide-and-conquer (recursive), geometric/domain + halo (grids/stencils — the HPC workhorse), pipeline (streaming; slowest stage sets rate), master–worker (irregular). Maximize surface-to-volume in geometric decomposition.

Know the ceilings (Ch 3)

Amdahl (strong scaling): S ≤ 1/((1−α)+α/N), capped at 1/(1−α) — attack the serial fraction first. Gustafson (weak scaling): S = (1−α)+αN, ~linear as problems grow. Roofline: arithmetic intensity (FLOPs/byte) locates a kernel as memory-bound (reuse/tile) or compute-bound (vectorize/FMA).

Shared-memory correctness (Ch 4–5)

Shared mutable state → mutex or atomic (read-only/thread-local need neither); data race = UB. Always RAII locks (scoped_lock for multiple, or global order → no deadlock). cv.wait with a predicate. Default atomics seq_cst; weaken to acquire/release only with a happens-before proof. Watch false sharing. Start with coarse locking; earn lock-free (CAS loops, ABA-aware) with profiler evidence.

GPU performance order (Ch 7–8, 10)

1. Coalesce global access (SoA, contiguous per warp) — #1 lever. 2) Tile through shared memory (raise arithmetic intensity). 3) Occupancy to hide latency. 4) Minimize warp divergence. 5) Minimize + overlap host↔device copies. CUDA↔OpenCL maps thread/block/grid ↔ work-item/work-group/NDRange. Prefer high-level primitives (transform/reduce/scan/sort) over hand kernels.

Distributed memory (Ch 6)

SPMD over a communicator; communication is the bottleneck — minimize, batch, overlap (Irecv/Isend + interior compute). Prefer collectives over point-to-point loops; Sendrecv/nonblocking to avoid deadlock. Domain decomposition + halo exchange is the dominant pattern.

Load balancing (Ch 11) & pitfalls (Ch 12)

Static (proportional/DLT) for predictable work; dynamic (master–worker, work stealing) for irregular. Balance heterogeneous hardware by measured throughput. Always synchronize before timing async GPU/MPI work — a missing sync produces the classic impossible ">100× speedup." Parallel floating-point reductions reorder additions → not bitwise reproducible.

---

Chapter Index

#	Title	Key Topics
ch01	Hardware & Parallelism Taxonomy	Flynn, SIMD/MIMD/SPMD, shared/distributed, NUMA, GPU hierarchy
ch02	Decomposition & PCAM	PCAM, dependency graph, geometric/pipeline/master-worker patterns
ch03	Performance Laws & Scalability	Amdahl, Gustafson, roofline, arithmetic intensity
ch04	C++ Threads & Concurrency	thread/jthread, mutex, CV, atomics, memory_order, deadlock
ch05	Parallel Data Structures	locking spectrum, lock-free/CAS, ABA, scan, reduction
ch06	Distributed Memory (MPI)	SPMD, point-to-point, collectives, halo exchange, overlap
ch07	GPU Programming (CUDA)	grid/block/thread, warps, coalescing, shared-memory tiling, occupancy
ch08	Portable Accelerators (OpenCL)	NDRange, work-items, CUDA↔OpenCL map, runtime compile, SYCL
ch09	Shared Memory (OpenMP)	fork-join, data-sharing clauses, reduction, schedule, target offload
ch10	High-Level GPU (Thrust)	device_vector, transform/reduce/scan/sort, fancy iterators, fusion
ch11	Load Balancing	static/DLT, dynamic, master-worker, work stealing, tuple space
ch12	Optimization & Pitfalls	triage order, data races, false sharing, timing discipline, FP reproducibility
ch13	OpenMP GPU Offload	target/teams/distribute, map & target-data regions, declare target, USM, async multi-device, Eightfold Path

Topic Index

• Amdahl / Gustafson / scalability → ch03
• arithmetic intensity / roofline → ch03, ch12
• atomics / memory_order / CAS → ch04, ch05
• coalescing / SoA layout → ch07, ch12
• collectives (Bcast/Allreduce) → ch06
• condition variables → ch04
• CUDA (grid/block/warp/SM) → ch07
• data race / false sharing / deadlock → ch04, ch12
• decomposition patterns → ch02
• domain decomposition / halo exchange → ch02, ch06
• Flynn taxonomy / SIMD / MIMD / SPMD → ch01
• load balancing (static/dynamic/DLT/work-stealing) → ch11
• lock-free / wait-free → ch05
• master–worker / task farm → ch02, ch11
• MPI / message passing → ch06
• mutex / RAII locking → ch04
• OpenCL / NDRange / work-items → ch08
• OpenMP / fork-join / clauses → ch09
• OpenMP GPU offload (target/teams/distribute) → ch13, ch09
• map clause / target-data regions / data movement → ch13
• declare target / unified shared memory (USM) → ch13
• async offload / multi-device (nowait/depend/device) → ch13
• variant directives / performance portability → ch13
• Eightfold Path to performance → ch13
• occupancy / warp divergence → ch07, ch13
• PCAM methodology → ch02
• pipeline pattern → ch02
• reduction / scan (prefix sum) → ch05, ch09
• roofline / memory-vs-compute bound → ch03, ch12
• shared-memory tiling → ch07
• Thrust / high-level GPU primitives → ch10
• benchmark timing / synchronization → ch12
• floating-point reproducibility → ch05, ch12

Supporting Files

• glossary.md — every key term with its defining chapter
• patterns.md — concrete techniques (PCAM, halo exchange, tiling, CAS loop, overlap, synchronized benchmarking)
• cheatsheet.md — decision rules: model picker, decomposition picker, GPU optimization order, CUDA↔OpenCL map, pitfall→fix

---

Scope & Limits

This skill covers parallel-programming end to end: the design methodology and performance laws, the cross-technology optimization playbook, and self-contained, hands-on chapters for C++ threads, MPI, CUDA, OpenCL, OpenMP, and Thrust — each with concrete APIs, host-program skeletons, code, and parameter tables. It targets the durable model and the practical coding patterns rather than exhaustively enumerating every API entry point or the newest spec revision's micro-features; for the latest version-specific spec minutiae the upstream specifications remain the final word. For language-standard concurrency/memory-model questions, see iso-cpp-2023 (C++) or iso-c-9899-2024 (C).