Exercises: OpenMP

These exercises drill the one skill that makes or breaks shared-memory code: data scoping. Several ask you to predict output before you run it — do that honestly, because a parallel program that surprises you is a parallel program you do not yet understand. Compile everything with -fopenmp, and set the team size with the OMP_NUM_THREADS environment variable so you can compare your predictions against a known thread count. When a problem's answer depends on the number of threads, say so explicitly; when it does not, say that, and explain why — the ability to tell the two apart is most of what this chapter teaches.

A note on method for the whole set: whenever you find a race, do not "fix it until it works." A race that happens to give the right answer on your laptop today is still a bug, and it will surface on a busier machine tomorrow. Reason about why the corrected scoping is race-free, not just that the number came out right once.

Difficulty: ⭐ warm-up · ⭐⭐ standard · ⭐⭐⭐ deeper. Solutions: worked solutions to the daggered (†) and odd-numbered problems are in appendices/answers-to-selected.md; the compilable ones are in code/exercise-solutions.f90. Try every problem before you look.

Part A — Warm-ups ⭐

33.1 † In two or three sentences, describe the fork–join model: what happens to the number of running threads at !$omp parallel` and at `!$omp end parallel, and how many threads run the code between two parallel regions.

33.2 What compiler flag enables OpenMP in gfortran? What happens to lines beginning !$omp when you omit that flag, and why is that behaviour a feature rather than a bug? Give one practical benefit of a single source file that builds correctly both with and without the flag.

33.3 † What do omp_get_thread_num() and omp_get_num_threads() return? What is the thread id of the master thread, and what is the range of ids on a team of 6? Which module must you use to call them, and what happens if you forget to?

33.4 Name the four principal data-sharing attributes (shared, private, firstprivate, reduction) and give a one-line description of each. Then, for each, name one concrete kind of variable in the heat solver's step that would take that attribute (or say "none" and explain why).

Part B — Type, Compile, and Run (predict first) ⭐⭐

33.5 † Predict the output of this program run with OMP_NUM_THREADS=3. Say precisely which parts are deterministic and which are not, and why — then compile and check. If you run it ten times, what will stay the same and what will change?

program predict
  use omp_lib
  implicit none
  print '(a)', 'start'
  !$omp parallel
  print '(a,i0)', 'thread ', omp_get_thread_num()
  !$omp end parallel
  print '(a)', 'end'
end program predict

33.6 A work-sharing loop over 6 iterations runs with schedule(static) on OMP_NUM_THREADS=3, recording who(i) = omp_get_thread_num() for each iteration i. Write out the who array you expect, and justify it from how static divides the range. Would your answer be reproducible run to run? Would it be with schedule(dynamic)? Now change the thread count to 4 (6 iterations, 4 threads) and predict the assignment again — what happens to the leftover iterations?

33.7 † Predict the printed value of s from this loop, and state whether it depends on the thread count. Explain, in one sentence, what the runtime does with the four (or eight, or sixty-four) private copies of s. (Compilable solution in code/exercise-solutions.f90.)

s = 0.0_dp
!$omp parallel do default(none) private(i) reduction(+:s)
do i = 1, 100
  s = s + real(i, dp)
end do
!$omp end parallel do

Part C — Find the Bug ⭐⭐

33.8 † This routine, meant to normalize each row of a matrix so its entries sum to 1, gives a different answer every run — and in fact will not even compile as written with default(none). Identify every unscoped variable, explain why each missing one is a race (not merely an omission), and give the corrected directive. Which variable is scoped for you automatically, and which are you responsible for? (Fixed version in code/exercise-solutions.f90.)

!$omp parallel do default(none) shared(a) private(i)
do i = 1, nr
  rowsum = 0.0_dp
  do j = 1, nc
    rowsum = rowsum + a(i,j)
  end do
  do j = 1, nc
    a(i,j) = a(i,j) / rowsum
  end do
end do
!$omp end parallel do

33.9 A colleague sums an array with s declared shared and no reduction: s = s + x(i) inside a !$omp parallel do. It compiles, it never crashes, and in testing on their quiet laptop it even gave the right total a few times — but in production the total is wrong and changes each run. Walk through the read–add–write sequence to explain the data race, explain why a quiet machine hid it, and give the one-clause fix.

33.10 † Someone writes !$omp do` directly around a loop in a subroutine, with no enclosing `!$omp parallel, and reports "no speedup at all, but at least it still gives the right answer." Explain what actually happened at run time — why the answer is right and why there is no speedup — and give two distinct ways to fix it.

Part D — Data Scoping ⭐⭐

33.11 † For the loop below, classify every variable as shared, private, firstprivate, or reduction, and write the complete correct !$omp parallel do directive with default(none). Assume a, b, c are arrays, n and scale are set before the loop, and total accumulates a grand sum.

do i = 1, n
  tmp = b(i) * scale
  c(i) = a(i) + tmp
  total = total + c(i)
end do

33.12 When must a variable be firstprivate rather than plain private? Give a concrete two-line example where using private instead of firstprivate produces wrong or undefined results, and a second example where either would work (so the choice is about clarity, not correctness).

33.13 † The counter loop below uses !$omp atomic. Rewrite it with a reduction instead, and explain which is faster and why — referring both to contention on the shared counter and to false sharing (§33.5). Under what circumstance could you not replace an atomic with a reduction?

count = 0
!$omp parallel do default(none) shared(count, v, n) private(i)
do i = 1, n
  if (v(i) > 0.0_dp) then
    !$omp atomic
    count = count + 1
  end if
end do
!$omp end parallel do

Part E — Design It (extend the heat solver) ⭐⭐⭐

33.14 † Add a parallel convergence check to the solver: after each step, compute the largest change any interior cell underwent, $\max_{i,j}|u^{\text{new}}_{i,j} - u^{\text{old}}_{i,j}|$, so the driver can stop the run when the plate has settled to a steady state. Write it as an !$omp parallel do with the correct reduction, state why reduction(max:...) is the right tool, and name the identity value each thread's private copy starts from. (Compilable solution in code/exercise-solutions.f90.)

33.15 The Project Checkpoint forks a fresh team inside step, so a fresh team is created and destroyed on every time step — thousands or millions of forks over a run. Sketch a version that forks the team once, outside the time loop, using !$omp parallel` around the loop and `!$omp do on the interior sweep. Explain what this saves, name the one new hazard it introduces (hint: what per-step work is serial — the buffer commit, the boundary re-imposition — and which construct must guard it?), and say why the step-loop index must now be private.

33.16 † Add a parallel L2 residual of the field, $\sqrt{\sum_{i,j}(u_{i,j} - u^{\text{prev}}_{i,j})^2}$, a smoother steady-state monitor than the max change. Write the reduction loop, and hand-verify it on a field whose difference from the previous step is $3$ at one interior cell, $4$ at another, and $0$ everywhere else. Why is the sqrt taken outside the parallel region rather than inside the loop? (Compilable solution in code/exercise-solutions.f90.)

Part F — Back of the Envelope ⭐⭐⭐

Show your reasoning; order-of-magnitude answers are the point.

33.17 † A solver is measured at 96% parallel. Using Amdahl's Law from Chapter 31, compute (a) the hard ceiling on speedup, (b) the speedup on 8 threads, and (c) on 16 threads. What efficiency does the 16-thread number represent, and what would you advise a colleague who wants to run this fixed problem on 64 threads?

33.18 Forking and joining a team costs on the order of a microsecond. The heat solver's interior update does roughly a dozen floating-point operations per cell, at perhaps $10^{9}$ such cell-updates per second per core. Estimate the work per step for a $5 \times 5$ plate (9 interior cells) and for a $2000 \times 2000$ plate, compare each to the ~1 µs fork cost, and argue which one OpenMP will speed up and which it will slow down, and why. What does this tell you about where to put the parallel region?

33.19 † To "avoid the reduction," a programmer gives each of 8 threads its own slot in real(dp) :: partial(0:7) and writes partial(tid) = partial(tid) + x(i). How many bytes do those 8 slots occupy? Given a 64-byte cache line, do they share one line? Name the resulting performance problem, explain in one sentence why it makes a correct loop slow, and give the two standard fixes.

Part G — Interleaved ⭐⭐

Mixing OpenMP with earlier chapters.

33.20 † (Ch. 5) In the solver's do j …; do i … sweep, the inner index i must be on the inner loop and must be listed private. Give the distinct reason for each requirement — one about memory layout, one about threads — and explain why getting the first wrong costs performance while getting the second wrong costs correctness.

33.21 (Ch. 31) You measure 6× speedup on 8 threads, while Amdahl's Law predicted an ideal 7× for the solver's serial fraction. What is the gap called, and name two concrete causes from this chapter that would explain measured speedup falling short of the ideal. Is 6× on 8 threads a good result — what efficiency is it?

33.22 † (Ch. 24) Explain why the OpenMP solver produces exactly the same temperature field as the serial Chapter 24 solver on any thread count, even though which thread computes which column, and in what order, is nondeterministic. What property of the FTCS update guarantees this, and what would it mean if the parallel and serial answers did differ?

33.23 (Ch. 3) In a reduction, each thread's private copy of the accumulator is initialized to the operator's identity. What identity value is used for reduction(+:s), for reduction(*:p), and for reduction(max:m)? Why would initializing a max reduction's private copies to 0 instead of the correct identity give a wrong answer for an array of negative numbers?

33.24 (Ch. 29) Contrast !$omp parallel do with do concurrent. Give one advantage of each for parallelizing the stencil sweep, and say which one guarantees parallel execution versus merely permitting it.

33.25 † Port it. Translate this pure-Python sum-of-squares to a parallel Fortran loop with a reduction, and predict the printed value. Then explain, in one sentence, why the Fortran version matters when this reduction sits inside a ten-thousand-iteration outer loop. (Compilable solution in code/exercise-solutions.f90.)

s = 0.0
for i in range(1, 11):
    s += i * i
print(s)

33.26 What does the default(none) clause do, and why does this chapter recommend putting it on every parallel region despite the extra typing it forces? Name one class of bug it prevents and one class of bug it does not prevent (see Case Study 1).

33.27 † (Ch. 27, 29) !$omp do simd both shares a loop's iterations across threads and asks the compiler to vectorize each thread's chunk. Explain why these two forms of parallelism "multiply" rather than merely add, estimate the throughput of 8 threads each running 4-wide SIMD, and say why the whole-array style of the stencil (Chapter 5) makes a loop especially amenable to simd.

33.28 (Design) The driver writes a VTK frame every 100 steps — serial I/O that stalls all threads while one writes to disk. Describe how you could overlap that output with the next block of computation using !$omp sections` or `!$omp task (one section computes while another writes the previous frame). What data must be copied before the overlap is safe, and why?

33.29 † (Ch. 20) A colleague reports that the parallel L2 residual (Exercise 33.16) on a large field of real data disagrees with the serial version "in the 14th digit," and asks whether the reduction is buggy. Diagnose it: is this a data race, a rounding effect, or a genuine bug? Explain what causes the discrepancy, why it is bounded and tiny, and how a regression test for this routine should be written.

33.30 (Ch. 31, synthesis) A compute node has 2 sockets of 16 cores each (32 cores total). You run the memory-bound stencil on 32 threads and measure only ~12× speedup, far below both 32× and even Amdahl's generous ceiling. Give two hardware reasons — not captured by Amdahl's serial-fraction model — that a memory-bound kernel stops scaling well before you run out of cores, and name the chapter (and model) you would cross to in order to use more than one node's worth of hardware.

Solutions to the daggered and odd-numbered problems are in appendices/answers-to-selected.md; the compilable ones are collected in code/exercise-solutions.f90. The full OpenMP directive and clause reference is Appendix G, the parallel-programming reference.