Exercises: Why Parallel?

This is a conceptual chapter, so these exercises lean toward reasoning and estimating rather than typing — but the reasoning is quantitative, and several problems ask you to compute a speedup exactly and then confirm it against the runnable calculators in code/. The single most valuable habit to build here is reaching for Amdahl's Law before committing to a parallel design: five minutes of arithmetic can save a week of disappointment.

Difficulty: ⭐ warm-up · ⭐⭐ standard · ⭐⭐⭐ deeper. Solutions: worked solutions to the daggered (†) and odd-numbered problems are in appendices/answers-to-selected.md; the computational ones are also worked as runnable code in code/exercise-solutions.f90. Try every problem before you look. Compile everything with gfortran -std=f2018 -Wall.

Part A — The End of the Free Lunch ⭐

31.1 † Two "laws" are often confused in this story. State which one ended around 2005 and gave us the free lunch of automatic speedups, and which one continued. In one sentence each, say what each law is actually about.

31.2 Physically, why did single-core clock frequencies stop rising in the mid-2000s? Name the limit (one phrase is enough) and explain why it caps clock speed rather than transistor count.

31.3 † You run a purely serial program on a compute node with 64 cores. Roughly what fraction of the node's compute capability are you using? Explain in one sentence why the phrase "the free lunch is over" captures your situation.

31.4 True or false, with a one-sentence justification: "Moore's Law ended, and that is why programmers now have to write parallel code."

Part B — Amdahl's Law ⭐⭐

State the formula you use, then compute. Confirm the daggered ones against code/exercise-solutions.f90.

31.5 † A program is 75% parallelizable ($p = 0.75$). (a) What is the maximum speedup on any number of cores? (b) What speedup do you actually get on 4 cores?

31.6 A program is 99% parallelizable. (a) What is its ceiling? (b) Compute its speedup on 16 cores and on 100 cores. (c) What does the gap between (a) and (b) tell you about buying more cores?

31.7 † You profiled a code and found it 90% parallel. (a) Compute its speedup on 8 cores and on 1000 cores. (b) The 1000-core number is barely larger than the 8-core number — explain, in terms of Amdahl's Law, why a 125× increase in cores bought almost nothing.

31.8 A program is only 50% parallelizable. Show, from the ceiling formula, that no machine — not even one with infinitely many cores — can make it more than 2× faster. Why is a 50% serial fraction a red flag before you start?

31.9 † Tabulate the Amdahl ceiling $S_{\max} = 1/(1-p)$ for $p = 0.90,\ 0.95,\ 0.99,\ 0.999$. Each step removes serial code that "sounds small." What does the pattern say about where an HPC engineer should spend optimization effort?

Part C — Gustafson's Law and Scaling ⭐⭐

31.10 † Using Gustafson's Law with a serial fraction $s = 0.10$, compute the scaled speedup on 16 processors. Then compute Amdahl's fixed-problem speedup at the same fraction ($p = 0.90$) and 16 cores. Explain, in one sentence, why the two numbers differ so much.

31.11 In your own words (no formula), explain why "10% serial" caps Amdahl's speedup at 10× but places no ceiling on Gustafson's. What assumption does each law make about the problem size?

31.12 † A code achieves a 40× speedup on 64 cores. (a) What is its parallel efficiency? (b) Using the Karp–Flatt relation $e = (1/S - 1/N)/(1 - 1/N)$, back out the serial fraction that a pure Amdahl model says produced this result. (c) Is 40× on 64 cores a good result? Justify.

31.13 Classify each as strong scaling or weak scaling: (a) You hold a $4096 \times 4096$ grid fixed and run it on 1, 4, 16, and 64 cores, hoping the run time falls. (b) You give each core a fixed $512 \times 512$ tile and grow the grid as you add cores, hoping the run time stays flat.

Part D — The Taxonomy ⭐

31.14 † Match each situation to a memory model (shared / distributed / GPU) and the Fortran tool you would reach for: (a) an 8-core laptop, the whole grid fits in RAM; (b) a 4000-node cluster, the grid is far too big for one node; (c) a stencil update over a hundred million cells, and one NVIDIA GPU available; (d) you want native, standardized Fortran parallelism with no external library.

31.15 Label each as data parallelism or task parallelism: (a) applying the same five-point stencil to every interior cell of the plate; (b) reading the next input file while computing on the current one; (c) running the same image filter over ten million pixels; (d) a kitchen where one cook grills, one plates, and one washes, all at once.

31.16 † Coarrays appear in both the shared-memory and distributed-memory rows of the taxonomy table in §31.3. Explain why one model can span both, and name the abstraction (three words) that makes this possible.

Part E — Find the Bug ⭐⭐

Each is a flawed statement or snippet. Diagnose it and give the correct version.

31.17 † A teammate writes in a design document: "Our kernel is 80% parallel, so on 100 cores we will get roughly an 80× speedup." What is wrong, and what speedup does Amdahl's Law actually predict at 100 cores? What is the ceiling?

31.18 A poster claims: "Our new solver achieves a 30× speedup — proof that it scales excellently." What single essential piece of information is missing, and why can the claim not be evaluated without it?

31.19 † This function is meant to return Amdahl speedup but returns the wrong answer. Two things look suspicious — the pfrac / ncores (is that integer division?) and the overall shape. Identify which is the real bug, explain why the other is a red herring, and fix it. For pfrac = 0.90, ncores = 8 it returns 0.2125; it should return about 4.71.

pure function speedup(pfrac, ncores) result(s)
  real(dp), intent(in) :: pfrac
  integer,  intent(in) :: ncores
  real(dp) :: s
  s = (1.0_dp - pfrac) + pfrac / real(ncores, dp)
end function speedup

31.20 A developer proposes: "To speed up the heat solver, let's run time steps $n$ and $n+1$ on two cores at the same time." Explain why this is impossible for this algorithm, and identify the property of the time loop that forbids it.

Part F — Design It and Back of the Envelope ⭐⭐⭐

31.21 † (Design it — solver.) In your own words, write the five-step "think before you parallelize" plan from §31.5 as it applies to the heat solver. For each step, give the one-sentence answer for this specific solver: which part is the data-parallel hot spot, and which dependency makes the time loop sequential?

31.22 (Back of the envelope.) A profiling run of the solver reports: setup 3.0 s (serial); 10,000 time steps at 0.5 ms each (the parallelizable stencil sweep); and 100 output frames at 20 ms each (serial I/O). (a) What is the total run time? (b) What is the serial fraction $1 - p$? (c) What is the Amdahl ceiling? (d) What speedup would 16 cores give?

31.23 † (Back of the envelope — inversion.) You want at least a 30× speedup, and you will run on 64 cores. Using the Karp–Flatt relation, what is the largest serial fraction your program can have and still reach 30× at 64 cores? (Confirm against code/exercise-solutions.f90.)

31.24 (Design it — solver.) The solver's periodic I/O is the serial 2% that caps its ideal speedup at 50× (the Project Checkpoint). Propose two concrete ways to raise that ceiling, and tie each to a technique or chapter later in this part.

Part G — Interleaved (Chapters 27 and 29) ⭐⭐

31.25 † (Ch. 27.) Why does §31.5 insist you fix the column-major loop order of the stencil sweep before parallelizing it? Connect your answer to the serial fraction in Amdahl's Law.

31.26 (Ch. 29.) Name one optimization from Chapter 29 (loop reordering, cache blocking, SIMD vectorization, do concurrent, contiguous). Does it compete with parallelism for the same speedup, or complement it? Explain in two sentences.

31.27 † (Ch. 5 + 24.) The finite-difference update computes each interior cell's new temperature from the old values of its four neighbours, using two arrays (current and next). Explain why this specific structure makes the interior update "embarrassingly parallel" within a single time step, and what would break if the update instead read new neighbour values as it went.

31.28 † (Synthesis.) Write a small program that reads a measured speedup S and a core count N and prints the Karp–Flatt serial fraction $e = (1/S - 1/N)/(1 - 1/N)$. Test it with S = 15.4217, N = 64; you should recover $e = 0.0500$ — the serial fraction of the 95%-parallel program from §31.2. What would a rising value of $e$ across increasing N tell you about your parallel code?

Solutions to the daggered and odd-numbered problems are in appendices/answers-to-selected.md; the computational ones are worked as runnable, hand-checked code in code/exercise-solutions.f90. The design problems (31.21, 31.24) have model answers plus room for your own reasoning — if your plan attacks the serial fraction first, parallelizes the data-parallel hot spot, and respects the time-loop dependency, you are on the right track.