Putting OpenMP Together: Judge It, Write It, Read Its Run
Wednesday's Showdown, at your own pace. Ask six questions of any loop, judge five snippets by their real output, write the pragma for four loops, compute the three numbers and diagnose one curve, then rebuild the payoff table from memory.
Concept map
Monday put the OpenMP module into six questions you can ask of any loop. This page makes you use them: code you judge by its output, pragmas you write, one run you read, and one table you rebuild from memory.
Six questions for any loop
Ask them in order, before you add a pragma. The first two decide whether the answer is right. The last four decide whether it is fast.
| # | Ask | What answers it in OpenMP | Get it wrong and |
|---|---|---|---|
| 1 | Who owns each variable? | shared, private, firstprivate, reduction, or declare it inside the loop | wrong answers |
| 2 | Does one iteration need another's result? | a copy, a reduction, or a different algorithm; never nowait in front of a loop that reads a neighbour's writes | wrong answers, sometimes |
| 3 | What does keeping it right cost? | critical, atomic and locks pay once per update; reduction pays once per thread | right answers, slowly |
| 4 | Do the iterations cost the same? | the schedule clause: static for even work, dynamic for uneven work | idle threads, or a trip per iteration |
| 5 | Is each piece of work big enough? | the chunk size, and the task cutoff | more bookkeeping than work, or too few pieces |
| 6 | Do different threads write the same cache line? | count in a local variable and write once | no race, still slow |
Which question?
Each line is something a program did. Pick the question that would have caught it.
Bug or fine? Snippets 1–3
For each: does it give wrong answers, the right answers, or the right answers slowly? Decide, then name the one-line fix before you check. Every reveal is the program's real output on a 2-thread test machine (not Cardinal).
Snippet 1 · Start at ten
int offset = 10; #pragma omp parallel for private(offset) for (long i = 0; i < n; i++) { a[i] = i + offset; } // wanted, n = 8: 10 11 12 13 14 15 16 17
private(offset) gives each thread its own offset, not initialized; here it happened to be 0, and could be anything. g++ -Wall warns that it may be used uninitialized. Fix: firstprivate(offset), so each copy starts at 10, or leave it shared: the loop only reads it.
$ OMP_NUM_THREADS=2 ./s1_offset 0 1 2 3 4 5 6 7
Question 1: who owns each variable?
Snippet 2 · A safe sum
long sum = 0; #pragma omp parallel for for (long i = 1; i <= n; i++) { #pragma omp critical { sum += i; } } // n = 100,000,000
The answer is right every time, but every add waits for the lock: 100,000,000 synchronized trips. Fix: reduction(+:sum). Each thread sums privately and the threads combine once at the end: 400× faster on two threads.
$ OMP_NUM_THREADS=2 ./s2_critical critical: 5000000050000000 in 8.558 s reduction: 5000000050000000 in 0.021 s
Question 3: what does keeping it right cost?
Snippet 3 · Square after adding one
double tmp; #pragma omp parallel for for (long i = 0; i < n; i++) { tmp = a[i] + 1.0; b[i] = tmp * tmp; } // n = 10,000,000; checked against the serial answer
tmp is declared outside the loop, so it is shared: one thread can overwrite it between another thread's write and read. At -O2 the compiler kept tmp in a register and the test passed; the race is still there by the language's rules. Fix: declare tmp inside the loop, or private(tmp). The wrong count changes from run to run.
$ OMP_NUM_THREADS=2 ./s3_O0 (built -O0) wrong elements: 58 of 10000000 $ OMP_NUM_THREADS=2 ./s3_O2 (built -O2) wrong elements: 0 of 10000000
Question 1: who owns each variable?
Bug or fine? Snippets 4–5
Same question, same machine. One of these gives the right answer; the other gives a wrong answer about once in twenty million elements.
Snippet 4 · Count the evens
long counts[64] = {0}; #pragma omp parallel { int myId = omp_get_thread_num(); #pragma omp for for (long i = 0; i < n; i++) { if (i % 2 == 0) { counts[myId]++; } } }
No race: each thread writes only its own entry. But eight 8-byte longs share one 64-byte cache line, so the line moves between cores on every write: false sharing. Fix: count in a local variable declared inside the parallel region and add it to the total once. That is what a reduction does for you. 11.6× faster on two threads.
$ OMP_NUM_THREADS=2 ./s5_counts (n = 400,000,000) counts[myId]: 0.908 s local: 0.078 s (min of 5) total = 200000000 both ways
Question 6: do different threads write the same cache line?
Snippet 5 · Fill, then add neighbours
#pragma omp parallel { #pragma omp for nowait for (long i = 0; i <= n; i++) { a[i] = 1.0; } #pragma omp for for (long i = 0; i < n; i++) { b[i] = a[i] + a[i + 1]; } }
Every omp for ends with a hidden wait for all threads. nowait removes it, so a thread can start the second loop while its neighbour is still filling a. At the edge of a thread's block, a[i + 1] belongs to the other thread. Fix: remove nowait. It is safe only when the next loop reads nothing another thread wrote.
$ OMP_NUM_THREADS=2 ./s6_nowait wrong elements over 20 trials: 1
Question 2: does one iteration need another's result?
Write the pragma
Four loops, each with a blank where the OpenMP goes. Write your line on paper first, exactly as you would type it, then pick the choice that matches. One of the four cannot be fixed by any clause.
Loop 1 · The trapezoid sum
double h = (b - a) / n; double sum = 0.0; double x; // ______ your line goes here ______ for (long i = 1; i < n; i++) { x = a + i * h; sum += f(x); }
h is only read, so it stays shared. x is written before it is read in every iteration, so each thread needs its own: private(x), or declare it inside the loop. sum is added to by every thread: reduction(+:sum). i, the loop variable, is private automatically. The last choice leaves x shared, which is snippet 3's race. The first empties h:
lecture09 · scope_PrivateBug: the same sum with private(h), f(x) = x*x on [0, 5] $ OMP_NUM_THREADS=1 ./Default/OMP scope_PrivateBug h*sum = 0 serial h*sum = 41.6666604167 CHECK scope_PrivateBug WRONG
Question 1: who owns each variable?
Loop 2 · Iteration i costs i
// The inner loop runs i times: iteration i costs i. double work(long i) { double r = 0.0; for (long j = 0; j < i; j++) { r += sin((double) j); } return r; } #pragma omp parallel for reduction(+:total) schedule(______) for (long i = 0; i < n; i++) { total += work(i); }
static splits the iterations before the loop, for free. On uneven work the last thread gets the heavy end and the other 47 finish and wait. dynamic hands out work on demand, and every hand-out is a trip to a shared counter. On even work there is nothing to balance, so dynamic, 1 only adds a trip per iteration: 276 times slower than static below. (When the cost is predictable, as it is here, static with a small chunk also balances it.)
lecture10 · real output, Cardinal, 48 threads
tri: iteration i costs i (n = 20000)
flat: every iteration the same (n = 1e8)
efficiency = speedup / threads
static dynamic,1 dynamic,64
tri: efficiency 0.29 0.99 0.84
flat: seconds 0.021 5.8 0.091
Question 4: do the iterations cost the same?
Loop 3 · Two neighbours
// Loop A: reads the element after it. for (long i = 0; i < n - 1; i++) { a[i] = a[i + 1] + b[i]; } // Loop B: reads the element before it. for (long i = 1; i < n; i++) { a[i] = a[i - 1] + b[i]; }
Loop A needs an old value, before a neighbour overwrites it. Copy a first and read from the copy; the price is n more words and a copy pass. Loop B needs a new value made by the iteration before it, all the way down the array. No clause removes that: it takes a different algorithm, the scan, at about 2n additions instead of n.
lecture10 · loop B with a plain parallel for, Cardinal, n = 1e6 $ OMP_NUM_THREADS=2 ./Default/OMP dep_Flow 1e6 --trials 100 CORRECT 0/100 (also 0/100 at 4, 8, 16 and 48 threads)
Question 2: does one iteration need another's result?
Loop 4 · Quicksort with tasks
void parallelQuicksort(int* a, long lo, long hi, long cutoff) { // ... a piece with fewer than cutoff elements // is sorted serially and returns here ... long p = partition(a, lo, hi); #pragma omp ___(1)___ { parallelQuicksort(a, lo, p, cutoff); } #pragma omp ___(1)___ { parallelQuicksort(a, p + 1, hi, cutoff); } } // The call, from main: #pragma omp ___(2)___ { #pragma omp ___(3)___ { parallelQuicksort(a, 0, n - 1, cutoff); } }
parallel makes the team. single lets one thread start the recursion while the others run tasks from the pool; without it, all 48 threads start the same sort on the same array. Each task is a piece of work any idle thread may pick up. The cutoff decides which pieces are worth a task, and both ends are slow for different reasons. At c = 1 there are 19,999,998 tasks and the program is mostly task bookkeeping. At c = 5,000,000 there are 4 pieces for 48 threads, so most threads have nothing to do.
lecture11 · real output, Cardinal, sorting 1e7 ints on 48 threads cutoff c tasks made time 1 19,999,998 0.807 s 10,000 4,012 0.120 s 5,000,000 4 0.590 s 20,000,000 0 1.203 s (no tasks: the serial sort)
Question 5: is each piece of work big enough?
Read the run
After the pragma is in, three numbers say whether it worked. p is the number of threads. T₁ is the one-thread time and Tₚ the p-thread time of the same program.
| Number | In words | Formula |
|---|---|---|
| Speedup S | one-thread time divided by p-thread time | S = T₁ / Tₚ |
| Efficiency E | speedup divided by the number of threads; 1 is ideal | E = S / p |
| Karp–Flatt e | the serial fraction that would explain this speedup; read its trend across p | e = (1/S − 1/p) / (1 − 1/p) |
Calculator
Your turn
Two timings, made up for practice. Work S, E and e on paper, type them, then check. Three significant figures is close enough.
One curve · faster, then slower (a model, not a measurement)
Speedup peaks at 10.1 near 24 threads, then falls to 7.2 at 48. Karp–Flatt e climbs in a straight line, from 0.005 to 0.12.
A rising e means the parallel machinery itself costs more as the team grows: more threads waiting for the same lock, or for the same cache line. Suspect whatever is paid once per update. Snippet 1 gives wrong answers, which no timing curve shows. Uneven shares make e fall as threads are added. A serial part keeps e flat.
The change to the pragma
critical or atomic on every update becomes a reduction. Neighbouring counters become a local variable, written once.
The run that proves it
Make the change and measure again. e should flatten. If it does not, the cost is somewhere else.
Model: time = 8 s ÷ p, plus 0.02 s for every extra thread.
The payoff table, from memory
Seven ideas you have met twice: once with messages, once with threads. Fill in what you can without looking, then show each row and compare. Nothing is stored or sent.
Run it on Cardinal
Three of the snippets, as whole programs with their timing, at 2, 8 and 48 threads. The test machine had two cores; Cardinal has 48 per socket.
Log in (put your OSC username in place of
OSC_USERNAME):ssh OSC_USERNAME@cardinal.osc.edu
Get one node for half an hour. Time nothing on the login node.
salloc -N 1 -n 1 -c 48 -t 00:30:00 -A PCS0313
sallocorsrunfails?Skip the allocation. From the login node, paste this once; every
srunbelow then queues its own short job. Paste it again after any new login.srun() { command srun -A PCS0313 -N 1 -n 1 -c 48 -t 00:10:00 "$@"; }Make a folder and load the compiler. Modules do not persist across logins, so repeat this line after any new login.
mkdir -p ~/showdown cd ~/showdown module load gcc/12.3.0
Create the three files. Each copy file button copies a command that writes the whole program; paste it into the terminal.
s2_critical.cppA: critical against reductionShow the program
s4_dynamic.cppB: dynamic,1 against staticShow the program
s5_counts.cppC: neighbouring counters against a localShow the program
Build all three on a compute node:
cd ~/showdown module load gcc/12.3.0 srun -c 48 g++ -O2 -fopenmp -o s2_critical s2_critical.cpp srun -c 48 g++ -O2 -fopenmp -o s4_dynamic s4_dynamic.cpp srun -c 48 g++ -O2 -fopenmp -o s5_counts s5_counts.cpp
Experiments
A · One lock per add
Predict first: does the gap between critical and reduction grow or shrink from 2 threads to 48?
cd ~/showdown
for t in 2 8 48; do
echo "== $t threads"
OMP_NUM_THREADS=$t srun -c 48 ./s2_critical
doneWhat you should see
On the 2-thread test machine: critical 8.558 s, reduction 0.021 s, the same sum. The 48-thread numbers are yours. Every add through the lock is a synchronized trip, and with more threads more of them wait in line; the reduction pays one combine per thread.
B · A trip per iteration
Predict first: at 48 threads, is dynamic,1 closer to static or further from it than at 2?
cd ~/showdown
for t in 2 8 48; do
echo "== $t threads"
OMP_NUM_THREADS=$t srun -c 48 ./s4_dynamic
doneWhat you should see
On the test machine: dynamic,1 3.229 s, static 0.058 s, min of 5. Every iteration costs the same, so there is nothing to balance; dynamic only adds a hand-out per iteration, and those hand-outs contend more as threads are added.
C · Neighbours on one cache line
Predict first: is the gap between counts[myId] and the local counter bigger at 2 threads or at 48?
cd ~/showdown
for t in 2 8 48; do
echo "== $t threads"
OMP_NUM_THREADS=$t srun -c 48 ./s5_counts
doneWhat you should see
On the 2-thread test machine: counts[myId] 0.908 s, local 0.078 s, the same total. Eight longs share one 64-byte line, so with 8 or more threads up to 8 writers fight over every line. The local counter lives on each thread's own stack and is written to the shared total once. The program prints a third timing, padded, which spaces the counters 64 bytes apart instead: the same cure by a different route.
Check yourself
Six questions, instant feedback, nothing recorded.
scale, set to 2.5 before the parallel region, and never writes it. Which data-sharing choice is correct and simplest?reduction(+:sum) much faster than putting sum += i inside critical?a[i] = a[i - 1] + b[i] inside a parallel for. What makes it correct?