Strong and Weak Scaling: What Amdahl and Gustafson Actually Bound

Two jobs can both be called “scaling studies” and answer opposite questions. One fixes the problem and adds processors, asking how much faster the same computation finishes. The other fixes the work per processor and adds processors, asking how much larger a problem can be solved in the same time. The first is bounded by the part of the code that cannot be parallelized. The second is bounded by how fast the cost of coordination grows with the process count. Confusing them produces the standard argument in which one person cites a hard limit and another cites near-linear speedup, and both are right about different experiments.

Two questions that look like one

Strong scaling holds the problem size N fixed and varies the process count P. The measured quantity is speedup, S(P) = T(1) / T(P), and efficiency, E(P) = S(P) / P. Efficiency of one means every added process contributed its full share; efficiency of one half means half the capacity was wasted. Strong scaling is the right question when the problem is fixed by the application, as in a forecast that must finish before a deadline.

Weak scaling holds the work per process fixed, so N grows with P. The measured quantity is usually the time at P relative to the time at one process with one process’s worth of work, and the ideal is a flat line. Weak scaling is the right question when the goal is to solve the largest problem the machine can hold, which is the usual justification for buying more nodes.

The two curves can look completely different for the same code. A solver with a fixed 2 percent serial section will flatten in strong scaling by a factor of fifty, while its weak scaling may stay near 90 percent efficiency to the largest machine available. Neither number contradicts the other; they are measurements of different functions.

The serial fraction and its ceiling

Amdahl’s argument partitions the runtime at one process into a serial part s and a parallel part 1 - s, and assumes the parallel part divides perfectly. Then

S(P) = 1 / (s + (1 - s) / P)

which tends to 1/s as P grows. A serial fraction of 5 percent caps speedup at twenty; 1 percent caps it at a hundred; 0.1 percent caps it at a thousand. The bound is brutal because it applies to the whole runtime, including initialization, input parsing, output writing, and any phase that only one rank performs.

The assumption that the serial part stays constant is the weak point. Some serial work is genuinely fixed, such as reading a small parameter file. Some is fixed per rank but appears serial in the model, such as the setup of a distributed data structure, and grows with P rather than staying constant. Some shrinks as the problem grows, which is Gustafson’s observation: if the problem size grows with the process count, the serial fraction of the larger problem is a smaller share of a larger total, and the achievable speedup is approximately s + (1 - s) P rather than 1/s.

Gustafson’s reformulation is not a refutation of Amdahl. It changes the experiment from fixed time to fixed problem, or equivalently from latency to throughput. The useful reading is that Amdahl bounds what a fixed problem can gain from more processors, and Gustafson describes what a growing problem can gain. A code that weak-scales well can still be a poor choice for a fixed-size job, and the reverse.

There is also a measurement version of the serial fraction that does not require instrumenting the code. The Karp-Flatt metric takes a measured speedup S at P processes and estimates the non-parallel fraction as

e = (1/S - 1/P) / (1 - 1/P)

If e stays roughly constant across process counts, the limit is a genuine serial section. If e rises with P, the cause is overhead that grows with the process count, such as communication or synchronization, rather than a fixed serial phase. That distinction determines whether the fix is to parallelize the remaining phase or to reduce coordination.

Isoefficiency: how fast the problem must grow

Weak scaling measures one path through the space of problem sizes. Isoefficiency analysis asks a stronger question: for a given algorithm and machine, how must the problem size grow with P to keep efficiency constant? The answer is a function W(P), and its growth rate classifies the algorithm.

For the halo exchange of a three-dimensional block decomposition, the per-iteration cost per rank has a compute term proportional to N^3/P and a communication term proportional to N^2/P^(2/3). Keeping their ratio constant requires N proportional to P^(1/3), so the total work N^3 grows linearly with P. Linear isoefficiency is the best case for a local method: doubling the machine doubles the problem that can be solved at the same efficiency, apart from constants.

A global reduction per iteration changes the classification. If each iteration ends with an allreduce, the latency term grows as log P while the per-rank compute term stays proportional to N^3/P. Holding the ratio constant now requires N^3 proportional to P log P, so the problem must grow slightly faster than the machine. The logarithm is small, but it is the difference between an algorithm that scales indefinitely and one whose efficiency drifts down at every doubling.

An elliptic solver is worse, because the iteration count grows with the grid. Jacobi applied to a Poisson problem with N points per side needs on the order of N^2 iterations to reduce the error by a fixed factor, so the total work is N^5. Holding efficiency constant requires N proportional to P^(1/3), and the total work then grows as P^(5/3). Multigrid, whose iteration count is nearly independent of the grid size, restores total work N^3 and linear isoefficiency. The arithmetic per point is the same; the difference is entirely in how many times it is repeated.

Reading a scaling curve honestly

A scaling curve is only as good as the timing methodology behind it.

The first rule is that the reported time is the maximum over ranks, not the mean. An iteration completes when the last rank finishes, so a mean hides exactly the imbalance that limits scaling. The second is that the baseline must be the same code. Measuring T(1) with a serial build and T(P) with a parallel build compares two programs, and the parallel one may be slower per flop because of ghost layers, different data layouts, or additional arithmetic. The third is that initialization and output must be excluded or reported separately; a run that writes a large restart file at the end charges the parallel configuration for work that does not scale.

A fourth issue is memory. At fixed problem size, the per-rank working set shrinks as P grows, and it can drop below the last-level cache. The per-rank arithmetic then gets faster for a reason unrelated to parallelism, and the measured speedup can exceed P. Superlinear speedup is real in this sense: it comes from the memory hierarchy, not from doing less work. It is also a sign that the baseline was memory-bound, so the curve says more about the cache than about the algorithm.

#include <stdio.h>

/* Report strong-scaling efficiency and the Karp-Flatt serial fraction.
   times[0] is the one-process baseline; p is the process count. */
void report(int n, const double *times, const int *p)
{
    double t1 = times[0];
    for (int i = 0; i < n; i++) {
        double s = t1 / times[i];
        double e = s / (double)p[i];
        double kf = (1.0 / s - 1.0 / (double)p[i]) /
                    (1.0 - 1.0 / (double)p[i]);
        printf("P=%4d  S=%7.2f  E=%6.3f  e=%6.4f\n", p[i], s, e, kf);
    }
}

The Karp-Flatt column is the diagnostic. A flat column points at a serial phase; a rising one points at overhead that grows with the process count.

When the curve bends for reasons the model misses

The cost models above assume that each rank’s work is identical and that the machine behaves the same at every scale. Neither holds at the far end of a scaling study.

Memory bandwidth per core falls as more cores share a node’s memory controllers, so the per-rank arithmetic rate is not constant across P even at fixed work per rank. The NUMA placement article treats this in detail; for scaling purposes the consequence is that weak scaling can degrade without any increase in communication.

The interconnect’s effective bandwidth also depends on the traffic pattern. A decomposition that maps neighbouring subdomains to ranks that are far apart in the network pays for every halo message, and the mapping is chosen by the scheduler, not by the code. At small process counts the fabric has spare capacity and the effect is invisible; at large counts, bisection bandwidth becomes the binding constraint. A scaling curve that bends only above a few thousand ranks is often a placement effect rather than an algorithmic one.

Finally, the operating system and the job runtime contribute noise that is negligible at one node and visible at many. A barrier waits for the slowest rank, and the slowest rank is increasingly likely to have been interrupted. The effect is small per event and grows with the number of ranks, which is one reason very large jobs are benchmarked with repeated runs and a reported minimum or median rather than a single sample.