# Introduction to parallel computing
**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 vs concurrency

**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.

## Shared memory vs distributed memory

Two threads on the same [[smp|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)
```

## The two laws that bound speedup

[[amdahls-law|Amdahl's law]] and [[gustafsons-law|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-primitve|synchronization]] choice, and communication pattern all look different depending on which regime a workload lives in.

## Where to go from here

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-primitve|synchronization primitives]], [[lock]]), then the programming models that use those primitives ([[openmp]], [[mpi]], [[cuda]]).