Chapter 28 Exercises — Profiling and Benchmarking

DataField.Dev

Chapter 28 Exercises — Profiling and Benchmarking

These exercises train the one habit that makes every later optimization chapter pay off: measure before you touch anything. Several ask you to read a profiler's output and decide what it means; a few ask you to write correct timing code; and the back-of-the-envelope problems make you compute the size of the prize before spending effort on it. Because performance is machine-specific, you will predict shapes and ratios far more often than absolute numbers — that is the discipline, not a limitation.

The difficulty tiers are:

⭐ Foundational — one idea, short code or a single reading of a profile.
⭐⭐ Applied — combine timing, profiling, and classification into a decision.
⭐⭐⭐ Challenge — a derivation, a full benchmark harness, or a subtle measurement trap.

Problems marked † have full worked solutions in appendices/answers-to-selected.md (and, for code, in this chapter's code/exercise-solutions.f90). Odd-numbered problems are also solved there. Everything compiles with gfortran -std=f2018 -Wall. Two standing rules apply with special force in this chapter: predict the shape of the output before you run it, and never report a timing you cannot reproduce — a benchmark you cannot repeat is a rumour, not a measurement.

Part A — Type, Compile, and Run (predict first)

A1 ⭐† Compile and run example-01-timing-cpu-vs-wall.f90. Before running, predict the exact value of array sum and explain why it is exact (what is special about summing ten million ones in real(dp)?). Then run it three times and report the three wall times. Are they identical? Explain in one sentence why the sum is reproducible but the time is not.

A2 ⭐ Compile and run example-02-timers-module.f90. Confirm the array sum matches A1's. Now move the call tic() to before the allocate and x = 1.0_dp, and re-run. What did you just start measuring that you were not measuring before, and which of the two placements answers "how long does the sweep take?"

A3 ⭐⭐† Given count_start, count_end, and count_rate, compute the elapsed seconds by hand for two cases: (i) start $3{,}200{,}000$, end $3{,}700{,}000$, rate $1{,}000{,}000$; and (ii) a clock that wrapped once — count_max $999{,}999$, start $999{,}900$, end $100$, rate $100{,}000$. Show the wrap correction, then confirm with solve_a3 in code/exercise-solutions.f90.

A4 ⭐† Before compiling project-checkpoint.f90, predict the entire $5\times5$ sanity block it prints after two steps. (You may reuse the Chapter 24 hand-trace.) Then compile and run, and confirm the block is bit-for-bit what you predicted. Why is the maxval u = 100.00 line of the timed run also exactly predictable, even though the per-step time is not?

Part B — Timing Correctly (find the bug)

B5 ⭐⭐† Find the bug. A colleague's timer "gives crazy numbers, sometimes negative":

integer :: c0, c1
real(dp) :: secs
call system_clock(c0)
! ... work ...
call system_clock(c1)
secs = (c1 - c0) / 1000.0_dp        ! "the clock is in milliseconds, right?"

Name three distinct bugs here (hint: the integer kind, the hard-coded rate, and one more), and rewrite the four lines correctly. Why does the default-integer clock make the "sometimes negative" symptom likely?

B6 ⭐⭐ Find the bug. This benchmark reports a suspiciously fast time:

$ gfortran -std=f2018 -Wall -O0 -pg -g solver.f90 -o solver   # then gprof...

Two things are wrong with using this build to decide what to optimize. State both, and give the compile command you should have used instead.

B7 ⭐⭐ For each scenario, predict whether system_clock (wall) and cpu_time (CPU) will roughly agree, and if not, which is larger and why: (a) a serial matrix multiply on an idle laptop; (b) a program that reads a 10 GB file and sums it; (c) an 8-thread OpenMP reduction; (d) your job on a login node shared with twenty other users.

Part C — Memory-Bound vs Compute-Bound

C8 ⭐ Classify each kernel as (probably) memory-bound or compute-bound, in one line each, by estimating its arithmetic intensity: (a) y = y + a*x over a million elements; (b) evaluating a degree-20 polynomial at each of a million points (Horner's rule); (c) the five-point stencil; (d) a dense $2000\times2000$ matrix multiply.

C9 ⭐⭐† Design the "add arithmetic" experiment for a loop you suspect is memory-bound. Write the two loop bodies (original, and original-plus-a-cheap-extra-flop-on-register-data), say exactly what re-timing should show in each case, and explain why the extra flop must not introduce any new memory traffic for the test to be valid.

C10 ⭐⭐† Compute the arithmetic intensity (flops per byte) of (i) axpy (y = y + a*x: two loads and a store of 8-byte reals, two flops) and (ii) the five-point stencil (~one fresh 8-byte load and one store, ~6 flops). Classify each. Confirm with solve_c10 in code/exercise-solutions.f90, and state which chapter's techniques (Ch. 29's blocking or Ch. 21's tuned BLAS) each classification points you toward.

C11 ⭐⭐⭐ A hand-rolled triple-loop matrix multiply and LAPACK/BLAS dgemm do the same $O(n^3)$ flops, yet dgemm is far faster. Argue, in terms of arithmetic intensity and data reuse, why the naïve version is memory-bound while dgemm is engineered to be compute-bound. What single technique (Ch. 29) is doing most of the work?

Part D — Profiling with gprof

D12 ⭐ From this representative flat profile, answer: which is the hot loop's home, what fraction of the whole run is spent outside it, and roughly how many times was it called per step?

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 81.0      4.05     4.05     4000     1.01     1.01  laplacian_
 14.0      4.75     0.70     2000     0.35     2.38  step_
  5.0      5.00     0.25        1   250.00  5000.00  MAIN__

D13 ⭐⭐† From the call-graph excerpt below, state who calls laplacian_, how much of step_'s time is "self" versus "children," and why optimizing step_'s own body (not the stencil) would be nearly useless.

[2]     95.0     0.85      3.90     2000         step_ [2]
                 3.90      0.00     2000/2000      laplacian_ [3]

D14 ⭐⭐ Explain concretely how profiling a -O0 build can point you at the wrong function. Give a plausible example of a helper routine that looks hot at -O0 and disappears at -O2.

D15 ⭐⭐ Port it. A data scientist profiles Python with python -m cProfile sim.py and reads the cumtime column. Write the equivalent three-command gprof workflow for a Fortran program, and map each Python step to its Fortran counterpart. Where does the Fortran workflow need a flag the Python one does not?

Part E — Benchmarking Methodology

E16 ⭐⭐† You collect four run times: 0.10, 0.10, 0.10, 0.30 seconds. Compute the mean and the median by hand. Which better represents the code's typical speed, and why is the mean misleading here? Confirm with solve_e16 in code/exercise-solutions.f90.

E17 ⭐⭐⭐† Design it. Write a reusable benchmark harness subroutine bench(kernel, n_rep, best, med) (taking the kernel as a procedure argument) that warms up, repeats n_rep times, and returns both the minimum and the median time. State how you defeat dead-code elimination and why you return two statistics.

E18 ⭐⭐ Find the bug. This "benchmark" reports essentially zero time at -O2:

call tic()
do i = 1, n
  y(i) = 2.0_dp * x(i)          ! y is never used again
end do
t = toc()
print *, 'time:', t

What did the optimizer do, and what one line makes the measurement real again?

E19 ⭐⭐ For each goal, say whether you would report the minimum or the median of your repeated timings, and why: (a) "what is the fastest this kernel can go on this CPU?"; (b) "what latency will a user typically see in production, where the machine is busy?"

Part F — Cache Behaviour (cachegrind)

F20 ⭐⭐ From this representative cachegrind summary, compute the D1 read-miss rate from the raw counts and say whether it looks like a good or bad loop order for a column-major array:

==999== D1  misses:  76,000,000 rd
==999== D   refs:   300,000,000 rd

F21 ⭐⭐† Two versions of the stencil sweep differ only in loop nesting. Predict which has the lower D1 miss rate and why, and explain why their D refs (total data references) are identical. Which chapter proved this effect qualitatively, and which measured it?

F22 ⭐⭐⭐ cachegrind reports a 19% D1 miss rate on your hot line, but perf stat on the same code reports a much smaller time penalty than you expected from that rate. Give two reasons the simulated miss rate and the real time cost can diverge, and state which tool you trust for "why" versus "how much."

Part G — Back of the Envelope

G23 ⭐⭐† A flat profile says one routine is 78% of your runtime. Compute the best-possible whole-program speedup if you made it (a) infinitely fast and (b) exactly $4\times$ faster. Is the week it would take to get $4\times$ worth it? Confirm the two numbers with solve_g23 in code/exercise-solutions.f90.

G24 ⭐⭐ A $2000\times2000$ real(dp) stencil sweep touches roughly two arrays' worth of data per step (~64 MB). At 5000 steps, estimate the total bytes streamed, and — given a memory bandwidth of ~20 GB/s — estimate the bandwidth-bound floor on the runtime. Compare with the flops (~6 per cell) to argue the run is memory-bound. (Order of magnitude; show the arithmetic.)

G25 ⭐⭐⭐ gprof samples ~100 times per second. If a run takes 0.3 s, roughly how many samples land in a routine that is 10% of the time, and why is the resulting percentage statistically untrustworthy? How long must the run be for that routine to collect ~1000 samples? State the methodology lesson.

Part H — Interleaved (earlier chapters)

H26 ⭐⭐ (Chapter 6.) The solver's laplacian is pure; the timers module's tic/toc are not. Explain, from the definition of pure, why each classification is correct, and why pure on the kernel helps both the optimizer and your ability to benchmark it cleanly.

H27 ⭐⭐† (Chapter 27.) In one paragraph, explain in cache-line terms why the inner loop should run over the first array index on a Fortran 2D array, and connect that directly to the D1 miss-rate difference you read in Part F. Which is cause and which is measurement?

H28 ⭐⭐ (Chapter 5.) The stencil can be written as a single whole-interior array-section statement or as an explicit nested loop. For profiling, which form makes the hot loop easier to see in gprof, and what does that cost you in readability? Is there a right answer?

H29 ⭐⭐ (Chapter 13.) You met valgrind's memcheck for memory errors in Chapter 13; this chapter used its cachegrind. State what each tool measures, why you would never run both in the same invocation, and which one you reach for when a correct program is merely slow.

Solutions to the starred, odd-numbered, and †-marked problems are in appendices/answers-to-selected.md; the compilable ones are in code/exercise-solutions.f90. If your measured numbers differ from a "representative" figure here, that is expected and correct — compare ratios and shapes, and trust your own machine.