# A primer on parallel computing Before any qc-rs specifics, this chapter builds the vocabulary the rest of Part IV uses — assuming **no** prior HPC knowledge. What is parallelism, what are threads and processes, why is a cluster different from a big laptop, and how much speedup can you actually expect? ## Why parallelism: doing work at the same time A single CPU **core** executes one stream of instructions. A quantum-chemistry calculation is billions of arithmetic operations, and on one core they happen **one after another**. Modern hardware has **many cores** (a laptop has 4–16, a server 64–256), and clusters have many **machines**. Parallelism means **splitting the work so pieces run at the same time** on different cores or machines, cutting the *wall-clock* time (the time you actually wait) even though the total work is unchanged. The catch is that not all work divides cleanly: some steps depend on earlier results, and coordinating the pieces costs time. How much you gain depends on how *parallelizable* your problem is — quantified below. ## Threads vs processes: shared vs distributed memory There are two fundamentally different ways to run pieces in parallel, and the difference — **how they share data** — drives everything in Part IV. :::{prf:definition} Threads and processes :label: def-thread-process - A **process** is an independent running program with its **own private memory**. Two processes cannot see each other's data directly; to share, they must **send messages** (copy data between them). - A **thread** is one stream of execution *inside* a process. Multiple threads of one process **share the same memory**, so they can work on the same data with no copying. ::: This gives the two classic parallelism models: - **Shared memory** (threads): several cores of **one machine** work on one copy of the data in RAM. Fast (no copying) and simple, but limited to a single machine's cores and memory. → [Threads & BLAS](threads-and-blas.md). - **Distributed memory** (processes / **MPI**): many processes, possibly on **different machines**, each hold *part* of the data and exchange pieces by passing messages over a network. Scales to thousands of cores and huge problems, but the programmer must manage what lives where and when to communicate. → [MPI & interconnects](mpi-and-interconnects.md). A **GPU** is a third model — thousands of tiny cores with their own memory, ideal for the same operation applied to massive arrays. → [GPU / CUDA](gpu-cuda.md). A real HPC run often nests all three: **MPI** across machines, **threads** within each machine, and a **GPU** attached to each. ## How much faster? Amdahl's law Parallelism has a hard ceiling: the part of a program that **cannot** be parallelized limits the total speedup, no matter how many cores you throw at it. :::{prf:theorem} Amdahl's law :label: thm-amdahl If a fraction $p$ of a program's runtime is parallelizable (and $1-p$ is inherently serial), the speedup on $N$ cores is $$ S(N) = \frac{1}{(1-p) + \dfrac{p}{N}} \;\xrightarrow{N\to\infty}\; \frac{1}{1-p}. $$ So if 90% is parallel ($p=0.9$), the maximum speedup is $1/(1-0.9) = 10\times$ — **even with infinitely many cores**. The serial 10% dominates at scale. ::: The practical lessons: (1) doubling the cores does **not** halve the time once the serial part matters; (2) adding cores past the point of diminishing returns wastes them; and (3) reducing the serial fraction (or the communication overhead) is often worth more than adding hardware. This is why qc-rs parallelizes the **expensive** steps (integral assembly, the XC grid, J/K builds) and why a small molecule may run *no faster* on 16 cores than on 4 — its work is too small to outweigh the coordination cost. :::{tip} Measure, don't assume Always check the **actual wall-clock time** at a couple of core counts before committing to a big job — a calculation that is too small, or dominated by a serial step, will not speed up, and you will just occupy cores others could use. "Report the absolute time, not only the ratio" applies to your own runs too. ::: ## The hardware landscape - **Multicore CPU** (your laptop or one server node): shared memory, driven by **threads**. The first and easiest speedup. - **Cluster** (many nodes joined by a network): distributed memory, driven by **MPI**. The nodes talk over an **interconnect** — ordinary Ethernet/TCP (slow) or **InfiniBand** (fast, ~35× the bandwidth), which matters enormously for communication-heavy steps (next chapters). - **GPU**: a massively-parallel accelerator for array-heavy kernels, an optional add-on per node. ## Where this leaves us You now have the concepts: cores and wall-clock, threads (shared memory) vs processes/MPI (distributed memory) vs GPU, and Amdahl's ceiling. The next three chapters map each onto a qc-rs knob — starting with the simplest and most useful, [threads](threads-and-blas.md). :::{exercise} :label: ex-primer 1. A colleague says "I gave my job 64 cores but it only ran 6× faster — the software is broken." Using Amdahl's law, give an innocent explanation. What parallel fraction $p$ gives a 6× *ceiling*? 2. You have one 128-core machine and a 4-machine cluster (32 cores each). For a job that needs to share a large array constantly, which is likely better, and why? 3. Why does adding cores never change the converged energy of an SCF, only the time? ::: :::{solution} ex-primer :class: dropdown 1. The serial fraction is limiting. A 6× ceiling means $1/(1-p) = 6$, i.e. $p \approx 0.83$ — about 17% of the job is inherently serial (or communication-bound), so 64 cores cannot do better than ~6×. Nothing is broken; the problem is just not parallel enough. 2. The **single 128-core machine** — it uses **shared memory** (threads), so constantly sharing a large array costs nothing (no copying). On the cluster, the same sharing would mean sending the array over the network every time, which for a communication-bound job is far slower. 3. The energy is defined by the physics (the converged density), not by *how* the arithmetic is divided among cores. Parallelism only changes the order/placement of the same operations, so the result is identical (up to floating-point reduction order). :::