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.

Definition 5 (Threads and processes)

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

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

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.

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.

Theorem 3 (Amdahl’s law)

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.

Exercise 16

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 to Exercise 16

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