High-Performance Computing Basics

High-performance quantum computation starts with an algorithm and representation whose cost fits the scientific question. Parallel hardware can reduce execution time, but it cannot remove exponential state-space growth or rescue an unnecessarily dense formulation. Performance comparisons are meaningful only at matched physical accuracy.

Required background. Dense and sparse operators supplies storage costs; error budgets defines the accuracy to preserve.

Operation counts and memory demand

A complex statevector for $n$ qubits has $2^n$ entries. At 16 bytes per complex binary64 value, one $n=30$ vector uses $16$ GiB. A second vector, workspaces, and stored Krylov vectors multiply this requirement. A density matrix stores $4^n$ entries and reaches the same value-storage demand at $n=15$.

These are representation costs, not universal lower bounds for every quantum task. Symmetry sectors, low entanglement, stabilizer structure, and targeted observables may permit much smaller descriptions. The many-body chapter and tensor-network chapter explain the corresponding restrictions.

Count the dominant operation: matrix-vector products, factorizations, tensor contractions, FFTs, or independent trajectories. Include setup and data conversion. A fast kernel is irrelevant if assembling its inputs dominates the run.

Arithmetic intensity and data movement

Define arithmetic intensity $I$ as floating-point operations per byte moved from the memory level under consideration. A simple roofline bound is

$$P\le\min(P_{\mathrm{peak}},BI),$$

where $P$ is achieved operations per second and $B$ is sustained bandwidth. This is a performance model, not a promise that either limit is attained. Access patterns, synchronization, instruction mix, and insufficient concurrency can lower performance further.

As an illustrative real-valued stencil, let $y_j=a x_{j-1}+b_jx_j+a x_{j+1}$. It uses three multiplications and two additions per point. If adjacent $x$ values are perfectly reused, reading one new $x$, one $b$, and writing one $y$ costs roughly 24 bytes per point in binary64, ignoring write-allocation and other traffic. Thus $I\approx5/24$ operations per byte. At an assumed bandwidth of $200$ GB/s, the bandwidth ceiling is about $42$ billion operations per second, regardless of a much higher arithmetic peak.

The example explains why local stencils often benefit more from reducing memory traffic than from counting multiplications. Dense matrix multiplication can reuse blocks of data repeatedly and has a different intensity profile.

Strong and weak scaling

Strong scaling keeps the total problem fixed while increasing processor count $p$. Speedup is $S(p)=T(1)/T(p)$ and parallel efficiency is $S(p)/p$. If a fraction $f$ of the serial runtime cannot be parallelized and overhead is ignored,

$$S(p)\le\frac1{f+(1-f)/p}.$$

For $f=0.05$, even infinitely many processors cannot exceed speedup 20 in this model. Real communication and load imbalance can make the limit smaller.

Weak scaling increases problem size with processor count, usually keeping local work approximately fixed. Report how the scientific problem changes: adding grid points by enlarging a box differs from refining the same domain. Weak scaling is a throughput statement and does not automatically imply a speedup for one fixed experiment.

Profiling a scientific run

Measure representative end-to-end runs after any required initialization or compilation, and report both setup and steady-state time when they matter. Profile enough to identify the dominant kernels and memory use. Record thread/process counts, precision, problem size, solver iterations, and residuals together with timing.

Avoid nested oversubscription: launching many worker processes while each dense library also uses every CPU core can increase contention. Conversely, reducing threads without measuring may underuse a large dense kernel. The appropriate policy depends on the mix of outer independent tasks and inner parallel linear algebra.

Use a smaller verified calculation as a regression reference while optimizing. Compare observables and invariants, not only wall time. Reordering sums or changing precision can alter the numerical answer; an optimization remains valid only if the agreed error budget still holds.

Choosing the next improvement

First remove avoidable mathematical work: use an exact symmetry, apply an exponential to a vector instead of forming it, or compute a few eigenpairs instead of all of them. Then improve data layout and reuse. Only afterward decide whether distribution or acceleration fits the remaining bottleneck. Parallelization patterns and accelerator notes address these choices in more detail.

Exercises

A run spends 40% of its time in a kernel that can be accelerated by a factor of eight. What is the overall speedup if everything else stays fixed?

Solution

The new time is $0.6+0.4/8=0.65$ of the original, so the overall speedup is $1/0.65\approx1.54$. Reporting an eightfold application speedup would confuse a kernel measurement with end-to-end performance.

References

• Hager, G., and G. Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2010 — profiling, memory hierarchies, and parallel scaling.
• Williams, S., A. Waterman, and D. Patterson, “Roofline: An Insightful Visual Performance Model for Multicore Architectures,” Communications of the ACM 52(4), 65–76 (2009), author repository — arithmetic intensity and performance ceilings.