How do you measure the parallel efficiency of a program, which baseline should the measurement use, and what does it mean if you observe a speedup greater than the number of processors used?

## The two numbers **Speedup** compares runtimes: `S(N) = T_ref / T(N)` **Efficiency** normalizes speedup by the resources spent: `E(N) = S(N) / N` Efficiency is the number that matters for decisions, because it converts directly into cost. `E = 0.5` means half your hardware spend produced nothing. Speedup alone flatters you: 20x sounds impressive until you learn it took 64 workers (31% efficient) rather than 24 (83%). ## Choosing the baseline honestly `T_ref` is where measurements are most often quietly rigged. Three candidate baselines: 1. **Best sequential algorithm** — the correct choice. A parallel algorithm often does *more total work* than the best serial one (redundant computation, extra passes, different data structures). Comparing against the best serial code exposes that. 2. **Parallel code with N = 1** — the common shortcut, and misleading. It includes the parallel implementation's own overhead in the baseline, so that overhead cancels out and efficiency looks better than it is. Report it as *relative* or *self-relative* speedup and label it as such. 3. **The old production system** — fine for a business claim, useless for judging parallel quality, because it mixes in every other change. Always state which baseline you used. An unlabelled speedup number is not a measurement. ## Reading the efficiency curve Run a sweep — 1, 2, 4, 8, 16, 32 workers — and plot efficiency. Typical shapes: - **Gentle decline** (100% -> 85% -> 70%): normal. Overhead grows slowly. Your operating point is where efficiency crosses your cost threshold. - **Sharp cliff** at some N: you hit a shared resource — one lock, one disk, saturated memory bandwidth, a single coordinator. - **Flat, then throughput falls** at high N: coordination cost is now growing faster than added capacity. Neither Amdahl nor Gustafson can produce a decreasing curve; models with an explicit interaction penalty are needed to describe it. From a measured speedup you can back out an experimentally determined serial fraction with the **Karp-Flatt metric**: `e = (1/S - 1/N) / (1 - 1/N)` The diagnostic value is in its *trend*. If `e` stays roughly constant as N grows, your losses really are a fixed sequential section — Amdahl's picture. If `e` rises with N, the losses are overhead that grows with worker count (synchronization, communication, imbalance), and adding workers is actively getting worse, not just less good. ## Measuring so the numbers mean something - **Same input, same machine, same build.** Changing input size mid-sweep silently switches you from strong to weak scaling. - **Warm up.** JIT compilation, page faults, cold caches, and connection setup distort the first runs. - **Repeat and report a distribution.** Use median or a percentile; a single run measures noise as much as scaling. Parallel runs are more variable than serial ones because they inherit scheduler jitter from every worker. - **Pin down the environment.** Frequency scaling, turbo boost, hyper-threaded siblings counted as "cores", noisy neighbours, and thermal throttling all corrupt scaling studies. Two hyper-threads on one physical core are not two cores' worth of capacity. - **Watch total resource cost, not just wall time.** CPU-seconds consumed usually *rises* with N even as wall time falls; that is the price of the speedup and it should be an explicit part of the decision. ## Superlinear speedup Efficiency above 100% looks impossible — how can 8 workers be more than 8 times faster? The usual causes are legitimate: 1. **Aggregate cache capacity.** Eight workers bring eight private caches. If the sequential run's working set spilled to main memory and each worker's 1/8 slice fits in local cache, the per-unit work genuinely gets cheaper. This is the dominant explanation for memory-bound workloads. 2. **Search anomalies.** In branch-and-bound or any search with early exit, a parallel run may stumble on the answer immediately while the sequential order would have explored a long fruitless branch first. This is luck, and it varies wildly run to run. 3. **Overlapping stalls.** While one worker waits on memory or I/O, another computes — resources that sat idle sequentially now get used. Illegitimate causes to rule out first: an unfair baseline (unoptimized serial code), different inputs or precision between runs, measuring a cold serial run against warm parallel ones, or a parallel version that skips work the serial version does. Investigate before you celebrate — but do not declare it impossible, because on memory-bound code it is common and reproducible. ## What to say in an interview Give the formulas, insist on a named baseline, report efficiency alongside speedup, describe the sweep and what the curve's shape diagnoses, and treat superlinear results as a hypothesis to test rather than an error or a triumph.