Chapter 31 — Key Takeaways (Why Parallel?)

A one-page reference to the laws and vocabulary that govern every parallel program. Keep it beside you through Chapters 32–35.

The vocabulary

The two laws (memorize these)

Amdahl (fixed problem, "how much faster?"):
   S(N) = 1 / ((1-p) + p/N)          ceiling  S_max = 1/(1-p)

Gustafson (grow problem, "how much bigger?"):
   S(N) = s + (1-s)*N                (linear in N; no ceiling)

   p = parallel fraction     1-p = s = serial fraction     N = processors

Amdahl at a glance (why the serial fraction is the tyrant)

The last few percent of serial code dominate the ceiling. Attack the serial fraction before you buy cores.

Strong scaling erodes efficiency (fixed problem, $p = 0.95$)

Same 5% serial fraction; by 64 cores three-quarters of the machine is idle. That is the law, not a bug.

The taxonomy of parallelism

Coarrays span both CPU rows — Fortran's native, standardized PGAS model, one notation for shared and distributed memory. No external library. (Chapter 32.)

Which question am I asking?

Diagnosing a scaling study (Karp–Flatt)

experimentally determined serial fraction from a measured speedup S on N cores:
   e = (1/S - 1/N) / (1 - 1/N)

   e CONSTANT across N  ->  a real fixed serial fraction (Amdahl-limited);
                            fix the algorithm or switch to weak scaling
   e RISING   across N  ->  parallel overhead (communication, sync) growing with N;
                            fix the parallel structure; stop adding cores

Pitfalls

• Quoting a speedup without its core count. "15× speedup" is meaningless alone — 15× on 16 cores is superb, on 512 cores is a failure. Report speedup and $N$, ideally with efficiency $S/N$.
• Confusing Moore's Law with Dennard scaling. Moore (transistor count) continued; Dennard (power density) ended — that is why clocks stalled.
• Parallelizing before optimizing serially. Speedup is measured against the serial baseline and capped by the serial fraction. Make it fast first (Part VII), then parallel.
• Trying to parallelize across time steps. Step $n+1$ depends on step $n$ — a hard dependency. Parallelize within a step, not across the time loop.
• Expecting the Amdahl number. Real speedup falls below Amdahl's ideal by the overhead of thread launch, messages, and host-device transfer — costs the clean law ignores.

Numbers and rules worth carrying

• Ceiling $S_{\max} = 1/(1-p)$ — the single most important number in parallel computing.
• 90% parallel ⇒ never beat 10×. 99% parallel ⇒ 100×. The jump is 10×, from a 9-point change.
• Clocks stalled at a few GHz around 2005; performance since comes from more cores, not faster ones.
• Efficiency $E = S/N$; perfect (linear) speedup is $E = 1$.

Project piece added this chapter

No new solver code — a plan and an estimate. From the profiled serial fraction (illustratively $p = 0.98$: stencil parallel, setup + VTK I/O serial), Amdahl's Law gives the solver's ideal speedup and its hard ceiling:

   p = 0.98  ->  8 cores 7.0x,  16 cores 12.3x,  64 cores 28.3x,  ceiling 50x

The stencil update is the data-parallel hot spot; the time loop is a hard sequential dependency. Make the serial fast first, parallelize the hot spot, and measure the real speedup against this ideal — the overhead is the gap. The solver goes parallel for real in Chapter 32.