Introduction to parallel computing lays out the basic vocabulary this wiki's Parallel computing section builds on, before diving into any specific mechanism. Parallelism means doing more than one unit of work at the same physical time; it is worth being precise about what “unit of work” and “at the same time” mean, because the terms below get reused constantly in every other article in this section.

Parallelism is multiple things physically executing at once, which requires multiple execution units (cores, GPU lanes, machines). Concurrency is a program structured as multiple logically independent tasks, whether or not they actually run at the same instant; a single core can be concurrent (switching rapidly between tasks) without ever being parallel. Every parallel system is concurrent, but not every concurrent system is parallel, a single-core OS scheduler juggling many threads is a classic example of concurrency without parallelism.

Two threads on the same SMP machine can communicate by writing to a variable both can see directly; this is the shared memory model, and it's what OpenMP and raw pthreads target. Processes on separate machines have no memory in common at all; they communicate by explicitly sending messages over an Interconnect, the distributed memory model that MPI targets. Most real HPC systems combine both: MPI processes across nodes, each node internally parallelized with threads.

Shared memory (one node):      Distributed memory (across nodes):
  thread A --\                   process A -- interconnect -- process B
  thread B --+-- shared var        (no memory in common at all)

Amdahl's law and Gustafson's law describe the same underlying tension from two angles: how much a fixed-size problem can be sped up by adding processors (Amdahl, pessimistic, bounded by the sequential fraction), versus how much a growing problem can be sped up as processors are added alongside it (Gustafson, closer to linear in practice). Which one describes a given workload depends on whether the problem size is fixed or grows with the available hardware, which in turn shapes almost every architectural decision covered elsewhere in this section: cache design, synchronization choice, and communication pattern all look different depending on which regime a workload lives in.

The Parallel computing map is organized roughly bottom-up from here: hardware fundamentals (Cache, NUMA, Interconnect), then the primitives built on that hardware (Atomics, synchronization primitives, Lock), then the programming models that use those primitives (OpenMP, MPI, CUDA).