Case Study 1: Reading a Scaling Study

"The speedup number tells you that something is wrong. The serial fraction tells you what."

Executive Summary

Two teams hand you scaling data for two parallel codes and ask the same question: why does it stop scaling? Both codes are stuck below 10× no matter how many cores they get, and both teams are about to "fix" it by requesting a bigger allocation — more cores. This study is the analysis that stops them from wasting it. You will take raw wall-clock timings, compute speedup and parallel efficiency, and then apply one sharp diagnostic — the Karp–Flatt metric, which backs the serial fraction out of a measured speedup — to tell the two cases apart. One code is limited by a genuine, fixed serial fraction that Amdahl's Law caps; the other is limited by parallel overhead that grows with the core count. They look identical on a speedup plot and require opposite fixes, and the Karp–Flatt number is what distinguishes them. Nothing here is parallel code; it is the arithmetic you do about parallel code, and it is the most useful hour you can spend before requesting a single extra core.

Skills applied: computing speedup $S = T_1/T_N$ and efficiency $E = S/N$ (§31.4); Amdahl's Law and its ceiling (§31.2); strong scaling as an experiment (§31.4); the Karp–Flatt inversion of Amdahl's Law; distinguishing a fixed serial fraction from communication overhead (§31.4, ⚡ Performance Note).

Background

Both teams ran the same strong-scaling experiment: a fixed problem, timed on 2, 4, 8, 16, 32, and 64 cores, against a one-core baseline of $T_1 = 8000$ s. Here is what they measured (seconds):

Glance at the two columns and Code B looks better early — it is faster at 2, 4, and 8 cores. But something alarming happens to Code B past 16 cores: its time rises. At 64 cores Code B is slower than at 16. Code A never does that; it keeps getting faster, just by less and less. Two different diseases. Let us diagnose them properly instead of squinting at times.

Phase 1 — Speedup and Efficiency

The first two quantities are mechanical. Speedup is the baseline time over the parallel time, $S(N) = T_1 / T_N$; efficiency is speedup per core, $E(N) = S(N)/N$, the fraction of each core you actually harness. For Code A, working the numbers by hand:

Code A's speedup climbs steadily toward — you may recognize these exact numbers — the curve of a 95%-parallel program (§31.2). Its efficiency decays smoothly from 95% to 24%, the textbook signature of Amdahl's strong-scaling wall. This is a well-behaved parallel code that is simply running into its serial fraction. More cores keep helping, just with diminishing returns.

Code B is the puzzle. Its speedup rises to about 9× at 16 cores, then falls — 8.88× at 32, 6.20× at 64 — and its efficiency craters to under 10%. A code whose speedup goes down when you add cores is not merely hitting a ceiling; it is being actively harmed by the extra cores. Efficiency alone tells you Code B is sick; it does not tell you why. For that we need one more number.

Phase 2 — The Karp–Flatt Metric: Backing Out the Serial Fraction

Amdahl's Law runs forward: given a serial fraction, predict the speedup. Run it backward and you get a diagnostic. Solve $S = 1/\big(e + (1-e)/N\big)$ for the serial fraction $e$, and you get the Karp–Flatt metric (Karp and Flatt, 1990):

$$ e = \frac{\dfrac{1}{S} - \dfrac{1}{N}}{1 - \dfrac{1}{N}}. $$

It is the experimentally determined serial fraction — the serial fraction that a pure Amdahl model would need to explain the speedup you actually measured. Its power is in how it behaves across core counts. If a program's only problem is a genuine fixed serial section, then $e$ comes out constant at every $N$ — because that is exactly the model Amdahl's Law assumes. If instead $e$ rises with $N$, the extra "serial-looking" time is not a fixed section at all; it is per-core overhead — communication, synchronization, load imbalance — that grows as you add cores, and which Amdahl's clean model never included. Constant $e$ says fix your algorithm's serial part; rising $e$ says fix your parallel overhead. Same speedup plot, opposite prescriptions.

Phase 3 — Run the Numbers on the Sick Code

Here is a short analysis program that ingests Code B's timings and prints speedup, efficiency, and the Karp–Flatt fraction at each core count:

program scaling_analysis
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  integer,  parameter :: cores(6) = [2, 4, 8, 16, 32, 64]
  real(dp), parameter :: t1 = 8000.0_dp
  real(dp), parameter :: t(6) = [4096.0_dp, 2168.0_dp, 1252.0_dp, &
                                  890.0_dp,  901.0_dp, 1290.5_dp]
  integer  :: k, n
  real(dp) :: s, e, kf, invn

  print '(a)', ' cores    time(s)    speedup efficiency Karp-Flatt'
  do k = 1, size(cores)
    n    = cores(k)
    s    = t1 / t(k)
    e    = s / real(n, dp)
    invn = 1.0_dp / real(n, dp)
    kf   = (1.0_dp / s - invn) / (1.0_dp - invn)
    print '(i6, f11.2, f11.4, f11.4, f11.4)', n, t(k), s, e, kf
  end do
end program scaling_analysis

$ gfortran -std=f2018 -Wall scaling_analysis.f90 -o scaling && ./scaling
 cores    time(s)    speedup efficiency Karp-Flatt
     2    4096.00     1.9531     0.9766     0.0240
     4    2168.00     3.6900     0.9225     0.0280
     8    1252.00     6.3898     0.7987     0.0360
    16     890.00     8.9888     0.5618     0.0520
    32     901.00     8.8790     0.2775     0.0840
    64    1290.50     6.1991     0.0969     0.1480

There it is, in the last column. Code B's Karp–Flatt fraction is not constant — it climbs steadily from 2.4% at 2 cores to 14.8% at 64. Now compare Code A. If you run the same analysis on Code A's times, the Karp–Flatt column reads 0.0500 at every single core count — flat as a table. (Check one by hand: at $N = 64$, $S = 8000/518.75 = 15.4217$, so $e = (1/15.4217 - 1/64)/(1 - 1/64) = (0.064844 - 0.015625)/0.984375 = 0.0500$.) Two codes, two completely different stories, told by one column.

Phase 4 — The Diagnosis

• Code A: a fixed serial fraction. Karp–Flatt is constant at 0.05. Code A genuinely has 5% of its work that will not parallelize — an inherently sequential phase, or serial setup/output that Amdahl's Law caps at $1/0.05 = 20\times$. The decaying efficiency is not a bug; it is the law. Adding cores keeps helping (the speedup rises monotonically toward 20), just with the diminishing returns Amdahl guarantees.
• Code B: growing overhead. Karp–Flatt rises, so the limiting cost is not a fixed serial section — it is overhead that scales with the core count. The likely culprit for a stencil code is communication: as you cut the plate into more tiles, the number and total size of boundary exchanges grows, and past 16 cores that communication cost overtakes the shrinking per-core compute. That is why Code B's time turns around and rises — you are paying more to talk than you save by splitting the work.

Phase 5 — What Each Team Should Do

The prescriptions are opposite, which is the whole reason this analysis was worth an hour:

• Code A should not request more cores for this fixed problem — Amdahl forbids the payoff, and 64 cores already wastes three-quarters of the machine. The useful moves are to shrink the serial 5% (overlap or parallelize the sequential phase) or to switch the question to weak scaling and grow the problem so Gustafson, not Amdahl, sets the ceiling.
• Code B should stop adding cores immediately — past 16 they make it slower — and attack the communication. Bigger tiles per core (fewer, larger messages), non-blocking exchanges that overlap with computation, or a better decomposition are the levers. This is precisely the craft of halo exchange in Chapter 34; the diagnosis here is what tells you to reach for it. For Code B, the sweet spot is around 16 cores, and buying more is buying slowdown.

Neither answer was visible in the raw times. Both fell out of one backward run of Amdahl's Law.

Discussion Questions

1. Code B is faster than Code A at 2, 4, and 8 cores, yet Code A is the healthier code. Explain how both can be true, and which code you would rather own for a run on 128 cores.
2. The Karp–Flatt metric assumes the pure Amdahl model. What real effect does it fold into the "serial fraction" when that assumption is violated — and why is a rising value the tell?
3. Code A's efficiency at 64 cores is 24%, and it is called "well-behaved," while Code B's 10% is called "sick." Is a healthy-but-low efficiency ever a reason not to use the cores? When would 24% be acceptable?

Your Turn: Extensions

• Option A. Feed Code A's times (4200, 2300, 1350, 875, 637.5, 518.75) into the analysis program and confirm the Karp–Flatt column is a flat 0.0500. Then confirm by hand that its speedups match a 95%-parallel Amdahl curve.
• Option B. Add a column to the program that prints, for each $N$, the ideal Amdahl speedup for Code A's serial fraction (0.05) beside the measured one, so the gap (the overhead) is visible at a glance. For Code A the gap is zero; construct a Code C where it is not.
• Option C. Extend Code B's model out to 128 and 256 cores by continuing the pattern (time keeps rising). At what core count does Code B become slower than the serial baseline of 8000 s? What does that say about the danger of "just add cores"?

Key Takeaways

• Speedup and efficiency detect a problem; the Karp–Flatt metric identifies it. Compute all three from any strong-scaling table before you change anything.
• A constant Karp–Flatt fraction across core counts means a genuine fixed serial fraction — Amdahl-limited; attack the sequential code or switch to weak scaling.
• A rising Karp–Flatt fraction means overhead that grows with cores (usually communication) — attack the parallel structure, and stop adding cores past the point where speedup turns around.
• A speedup number without its core count, and a scaling plot without a serial-fraction analysis, are both incomplete. The arithmetic you do about a parallel program is as important as the program.