Amdahl, Gustafson and a Real Scaling Curve: Fitting the Serial Fraction of a Python Pool

The reduction post ended with a scaling curve that bent at four threads because half the cores are efficiency cores. Amdahl's and Gustafson's laws model the other reason curves bend: the part of a run that does not get faster with more workers. They answer two different questions, and the clearest way to see what each says is to fit both to a measured curve, here from Python's multiprocessing on an Apple-silicon laptop (Apple M1, hw.ncpu = 8).

Two laws, two questions

Strong scaling fixes the problem and adds processes: how much sooner does this job finish? If a fraction $f$ of the one-process run time cannot be parallelised and the rest divides perfectly,

That is Amdahl's law (1967), and the ceiling $1/f$ is the famous part: with $f=0.05$ no number of processes beats 20×.

Weak scaling fixes the work per process and grows the problem with $p$: how much more work fits in the same time? Gustafson (1988) measured $f$ on the parallel run instead. If the $p$-process run spends a fraction $f$ of its time in serial code, one process would need $f+(1-f)p$ of that time for the same work, so the scaled speed-up is

a straight line with no ceiling. The two $f$ divide by different run times, so they need not agree even for the same program. Efficiency is $E(p)=S(p)/p$.

Solving Amdahl's law for $f$ at each measured point gives the Karp–Flatt metric $e(p)=(1/S(p)-1/p)/(1-1/p)$. If $e(p)$ grows with $p$, something costs more as processes are added, and the model has no term for that.

The experiment

The workload is the midpoint rule for $\pi ={\int }_0^{1}4/(1+x^2)dx$, computed with NumPy in blocks of $2^{14}$ points so the 128 KiB temporaries stay in cache. Every run creates its own pool, so worker start-up is part of the measured time, and a barrier in the pool's initializer separates start-up from compute.

import multiprocessing as mp
import time
import numpy as np

def integrate(lo, hi, n, block=1 << 14):
    h, s = 1.0 / n, 0.0
    for a in range(lo, hi, block):
        x = (np.arange(a, min(a + block, hi), dtype=np.float64) + 0.5) * h
        s += float(np.sum(4.0 / (1.0 + x * x)))
    return s * h

def task(args):
    return integrate(*args)

def ready(barrier):
    barrier.wait()                    # this worker has started and imported NumPy

def run(p, n, ntasks):
    step = n // ntasks
    tasks = [(i * step, (i + 1) * step, n) for i in range(ntasks)]
    barrier = mp.Barrier(p + 1)
    t0 = time.perf_counter()
    pool = mp.Pool(p, initializer=ready, initargs=(barrier,))
    barrier.wait()                    # all p workers are up
    t1 = time.perf_counter()
    pi = sum(pool.imap_unordered(task, tasks, chunksize=1))
    t2 = time.perf_counter()
    pool.close(); pool.join()
    return time.perf_counter() - t0, t1 - t0, t2 - t1, pi

if __name__ == "__main__":
    for p in range(1, 9):
        print("strong", p, run(p, 1 << 30, 256))        # fixed total: 2^30 points
        print("weak  ", p, run(p, p << 27, 32 * p))     # fixed per process: 2^27 points

imap_unordered with chunksize=1 hands out tasks one at a time, so workers on fast cores take more of them. The eight-process weak run is exactly the strong problem. Software: Python 3.14.0 (standard build, with a GIL), NumPy 2.3.4, SciPy 1.16.2, and the spawn start method, the macOS default since Python 3.8. Each number is the median of seven runs with process counts interleaved; the laptop was in ordinary use, so the min–max bars are part of the result. All 119 runs returned $\pi$ to within $2.1\times {10}^{-14}$.

Strong scaling and the fit

Calling integrate directly in the parent takes 1.90 s. A pool of one worker takes 2.16 s, of which 0.26 s (12 %) is start-up.

The speed-up reaches 2.5 at four processes, stays near it through seven and drops to 2.16 at eight. The compute phase alone still speeds up 4.33 times on eight processes (short of 8 because processes five to eight run on efficiency cores), but start-up grows from 0.26 s to 0.45 s as more interpreters start at once, and at eight processes it is 45 % of the run.

Least squares on all eight speed-ups gives $f=0.294\pm 0.024$, a ceiling of $1/f=3.4$, and a root-mean-square residual of 0.25. Fitting only $p\le 4$ gives $f=0.197$ with a residual of 0.025: below the efficiency cores, Amdahl's model describes this program almost exactly. Over the full range it does not; the Karp–Flatt column climbs from 0.17 to 0.39, and a single $f$ can only follow a curve that rises and then falls by splitting the difference. A fitted $f$ summarises one machine, one problem size and one range of $p$, so report the range and the residual with it.

from scipy.optimize import curve_fit

p = np.arange(1, 9)
S = T[0] / T                                   # T: median strong-scaling times
amdahl = lambda p, f: 1.0 / (f + (1.0 - f) / p)
(f_A,), cov = curve_fit(amdahl, p, S, p0=[0.05], bounds=(0, 1))   # nonlinear least squares on S
Sw = p * Tw[0] / Tw                            # Tw: median weak-scaling times
f_G = np.sum((p - 1) * (p - Sw)) / np.sum((p - 1) ** 2)            # S = p - f(p-1) is linear in f
e = (1 / S[1:] - 1 / p[1:]) / (1 - 1 / p[1:])                     # Karp-Flatt, p >= 2

Weak scaling and Gustafson

With $2^{27}$ points per process, one process needs 0.50 s and eight need 0.99 s for eight times the work: a weak efficiency $T_w(1)/T_w(p)$ of 0.51, or a throughput gain $p{T}_w(1)/T_w(p)$ of 4.07. That gain is what weak-scaling plots usually call the scaled speed-up, but it is not Gustafson's. Its baseline, $p{T}_w(1)$, charges a single worker for $p$ start-ups, and the one-worker weak run is half start-up (0.26 s of its 0.50 s); Gustafson's one-process time counts the serial part once. Up to four processes the efficiency stays between 0.84 and 0.95; the efficiency cores bend the curve again, and a straight line cannot follow a bend. A least-squares line $p-f(p-1)$ through the throughput gains has $f=0.461$ and a residual of 0.50 ($f=0.184$ for $p\le 4$), but with this baseline the parameter only describes the curve; it is not the serial fraction of any run.

The most useful line in the table is the last one. The eight-process weak and strong runs are the same job, $2^{30}$ points on eight workers, and took 0.985 s and 0.998 s. Against one worker running that same job (2.156 s) the speed-up is 2.2×; against eight copies of the small one-worker run it is 4.1×. Only the baseline differs, and the second one includes seven start-ups that a single worker would never pay. A speed-up quoted without its baseline can mean either.

Where the overhead comes from

Process start-up. With spawn, every worker is a new interpreter that imports the main module and NumPy before it takes a task. Python's documentation calls spawn slow next to fork and forkserver, but fork is unsafe on macOS because system libraries may have started threads, and since Python 3.14 the Linux default is forkserver. The fix is the same everywhere: create the pool once and reuse it.

Pickling. A task description pickles to about 30 bytes, and a trivial round trip through pool.apply costs 0.66 ms. Data is different: sending a 128 MiB array to a worker and summing it there took 0.111 s, against 0.010 s for np.sum in the parent. Send instructions to generate data, or use multiprocessing.shared_memory.

The GIL is irrelevant here. Each process has its own interpreter and its own GIL, so no lock is shared. With eight threads instead, a pure-Python version of the integral ($2^{24}$ points) took 1.25 s against 1.26 s on one thread, and eight already-started processes took 0.30 s. The NumPy version got slower on threads, 0.91 s against 0.50 s for $2^{28}$ points, because every ufunc call on a $2^{14}$ block releases and re-acquires the GIL and eight threads contend for it; eight processes took 0.13 s.

Memory bandwidth. The right panel repeats the strong-scaling run with $2^{20}$-point blocks, so each temporary is 8 MiB and every pass streams through DRAM. One process is only 8 % slower than with small blocks (2.06 s against 1.90 s), but more processes do not help: the speed-up is 1.04 at two and 0.79 at eight. A direct check agrees: processes copying their own 64 MiB arrays reached 32.8 GB/s (bytes read plus written) with one process, 39.5 with two, 34.3 with four and 24.8 with eight. One or two cores saturate the memory system, so a memory-bound kernel has no parallel speed-up to give.

TIP

Before fitting anything, split the wall time the way the barrier does here: start-up, compute, teardown. A serial fraction measured that way is a number you can act on (reuse the pool, ship less data, block for the cache); a fitted $f$ only tells you that something did not scale.

Further reading

• Gene Amdahl, Validity of the single processor approach to achieving large scale computing capabilities, AFIPS 1967.
• John Gustafson, Reevaluating Amdahl's law, Communications of the ACM, 1988.
• Alan Karp and Horace Flatt, Measuring parallel processor performance, Communications of the ACM, 1990, which introduces the experimentally determined serial fraction.
• The multiprocessing documentation, especially the section on start methods, and the pickle documentation.
• NumPy's notes on thread safety and when it releases the GIL.