Chapter 29 Quiz — Optimization Techniques

Twenty questions to check that loop order, fusion, blocking, the roofline, SIMD, do concurrent, and the "when to stop" judgment are solid before you move on to compiler flags. Aim for 16/20. Anything below that, revisit the section named in the "Topics to review" map at the end. Answers and one-line rationales are in the key.

Multiple choice

Q1. In Fortran's column-major storage of a(n,n), which element is adjacent in memory to a(i,j)? - (a) a(i,j+1) - (b) a(i+1,j) - (c) a(i+1,j+1) - (d) none — array elements are not contiguous

Q2. For a dense nested loop over a(i,j), the inner loop should run over: - (a) the second index j, to match C and NumPy. - (b) the first index i, for unit-stride column-major access. - (c) whichever is larger. - (d) it never matters for performance.

Q3. Loop fusion merges two loops over the same range in order to: - (a) do less arithmetic. - (b) touch each element once instead of twice, cutting memory traffic (and often a temporary array). - (c) make the code shorter to read. - (d) enable recursion.

Q4. Loop fission (splitting a loop) is most useful to: - (a) combine two temporaries into one. - (b) isolate a vectorizable part from a part that blocks vectorization. - (c) reduce the iteration count. - (d) change the computed result.

Q5. Cache blocking (tiling) most helps a kernel that: - (a) streams its data once with little reuse (a single stencil sweep). - (b) reuses each loaded value many times (matrix multiply). - (c) does no arithmetic. - (d) is already memory-bound.

Q6. A kernel is memory-bound when: - (a) it runs out of RAM. - (b) its arithmetic intensity is low, so it hits the memory-bandwidth ceiling before the arithmetic one. - (c) it has a memory leak. - (d) it uses allocatable arrays.

Q7. Auto-vectorization is: - (a) the programmer writing SIMD intrinsics by hand. - (b) the compiler automatically turning a scalar loop into SIMD instructions, no special syntax needed. - (c) running a loop on multiple cores. - (d) a NumPy feature only.

Q8. Which condition is required for the compiler to auto-vectorize an inner loop? - (a) It must call a subroutine each iteration. - (b) It must have a loop-carried dependency. - (c) Its iterations must be independent and unit-stride. - (d) It must use do while.

Q9. do concurrent primarily: - (a) guarantees the loop runs in parallel on all cores. - (b) asserts to the compiler that the iterations are independent, permitting (not guaranteeing) vector/parallel execution. - (c) is obsolescent, replaced by forall. - (d) makes the loop run in reverse.

Q10. The contiguous attribute on a pointer or assumed-shape dummy: - (a) makes the array larger. - (b) promises unit-stride storage, so the compiler can vectorize without a contiguity check or copy. - (c) allocates the array. - (d) forces the loop to run serially.

True/False (justify in one line)

Q11. True or false: Reordering a dependency-free loop for cache friendliness can change the computed result in the last bit.

Q12. True or false: Cache blocking a single Jacobi stencil sweep typically gives a large speedup.

Q13. True or false: For a memory-bound kernel already streaming its data the minimum number of times, making the arithmetic cleverer cannot speed it up.

Q14. True or false: do concurrent is safe to use even if one iteration reads a value another iteration writes, because the compiler checks independence for you.

Q15. True or false: A well-blocked matrix multiply you write yourself will typically match a tuned BLAS dgemm in speed.

Short answer

Q16. In one sentence, state the "biggest reliable win" optimization for dense Fortran and why it costs nothing in readability.

Q17. Explain why hoisting a division out of an inner loop is worth doing even though hoisting a multiply usually is not.

Q18. Give the payoff order for optimizing a hot numerical loop (four steps, largest payoff first).

What does this code print?

Q19. Two loop nests fill a(n,n) with the identical formula, one with i inner and one with j inner. What does this print, and what is the single word that describes the relationship between the two results?

print '(a, f6.1)', 'max diff = ', maxval(abs(a_iinner - a_jinner))

Q20. A programmer writes the stencil update with do concurrent but in place (writing into the same array it reads). Explain what is wrong and what the standard says about the result.

do concurrent (j = 2:ny-1, i = 2:nx-1)
  u(i,j) = u(i,j) + r*(u(i-1,j) + u(i+1,j) + u(i,j-1) + u(i,j+1) - 4.0_dp*u(i,j))
end do

Answer Key

Q Answer Rationale
1 b Column-major: the first index strides by one element; a(i+1,j) is adjacent.
2 b Inner loop over the first index gives unit-stride, cache-line-filling access.
3 b Fusion touches each element once, cutting memory traffic and often a temporary.
4 b Fission isolates a vectorizable part from one that blocks vectorization.
5 b Blocking captures reuse; matmul has $O(n)$ reuse, a single stencil sweep does not.
6 b Memory-bound = low arithmetic intensity, limited by bandwidth, not the arithmetic units.
7 b The compiler emits SIMD from an ordinary loop, no intrinsics written by you.
8 c Independent, unit-stride iterations are the core requirement.
9 b It asserts independence; it permits, but does not guarantee, vector/parallel execution.
10 b contiguous promises unit stride, restoring the vectorization assumption.
11 False A dependency-free reorder is bit-identical; only reassociating a reduction can change bits.
12 False A single sweep is memory-bound with little reuse; blocking it buys almost nothing.
13 True At the memory roofline the arithmetic units already idle; cleverer arithmetic cannot help.
14 False do concurrent is an unchecked promise; a hidden dependency gives undefined results.
15 False A tuned dgemm (all-cache blocking, hand-vectorized) beats a hand loop by ~an order of magnitude.
16 — Correct loop order (inner over the first index): unit stride, same source length, no readability cost.
17 — A floating-point divide costs many times a multiply, so doing it once instead of $n$ times per loop is a real saving; a multiply is cheap enough that hoisting it rarely matters.
18 — (1) -O2/-O3 + correct loop order; (2) fusion + hoisting; (3) vectorization (do concurrent, contiguous, -march=native); (4) rarely, hand-tuning — and for dense linear algebra, call BLAS.
19 max diff = 0.0 The two orders apply the identical per-element formula → identical results; only speed differs.
20 — The iterations are not independent — a point may read a neighbor another iteration already updated — so the independence promise is broken and the result is undefined (and would silently become Gauss–Seidel even if serial). Use a separate u_new.

Topics to review by question

Questions Section to review
1, 2, 19 §29.1 (loop reordering, column-major)
3, 4, 16, 17, 18 §29.1 (fusion, fission, hoisting)
5, 6, 12, 13 §29.2 (cache blocking, arithmetic intensity, roofline, memory-bound)
7, 8, 11 §29.3 (SIMD, auto-vectorization)
9, 14, 20 §29.3 (do concurrent, the independence promise)
10 §29.4 (contiguous, aliasing)
15 §29.5 (diminishing returns, why BLAS wins)