Week 10 · OpenMP II · Companion to lecture 10a

OpenMP II —
A Must Precede B

Last Monday every loop you parallelized was independent. Today: the loops that are not, how to tell from the source, how to remove the dependence, and why a racy loop can pass your tests.

Concept map

Three moves, in order: classify the dependence from the source, remove it (or enforce it), then detect what you missed. Click a node to jump to it.

todaylater

Today in one line: find what must precede what; remove it, or enforce it — and never trust one clean run.

Everything on this page runs from the openmp repository, branch lecture10, src/main.cpp. Every method prints a CHECK line against a serial answer computed in the same run. Every count of runs on this page is from the course test machine (2 cores, shared with other jobs, g++ 13 -O2) — the Cardinal numbers for this branch do not exist yet.

Mark this section done

Four loops. Which can take `#pragma omp parallel for` as written?

For each: does any iteration read or write something another iteration writes? If yes: which iteration, and how many iterations apart? D declares tmp before the loop.

Classify all four. The reveal opens when the last one is placed.

Two threads. B, C and D are all wrong — but not in the same way.

$ OMP_NUM_THREADS=2 ./Default/OMP dep_<X>
CHECK dep_Flow WRONG (499999 of 1000000 elements wrong, first at i = 500001)
CHECK dep_Anti WRONG (1 of 1000000 elements wrong, first at i = 499999)
CHECK dep_Temp WRONG (1201 of 1000000 elements wrong, first at i = 28072)
CHECK dep_TempPrivate ok   # tmp inside

Real output, lecture10 at n = 10⁶, course test machine (2 cores, g++ 13 -O2). A is not shown: it is independent. dep_Temp's count varies run to run; dep_Flow and dep_Anti give these counts on almost every run at 2 threads, but they are races too.

Three shapes of wrong

The bar is the 10⁶-element array, split into two static chunks. Red marks wrong elements. For B and C the positions are the deck's exact ones; for D only the count (1,201) is measured — the positions drawn here are an illustration of "scattered".

A print of the first ten elements of a after each loop. Which of the three wrong results would it catch?

B only — half the array is wrong, so the start must be. B and D — the scattered errors will land somewhere in the first ten. All three — a million-element array has no way to hide 499,999 errors. None of them.

The first wrong element is at 28,072 or later. B's wall starts at thread 1's first iteration, i = 500,001; C's one needle is at the chunk boundary, i = 499,999; D's first error happened to be at 28,072. Thread 0's chunk starts clean in every case. Spot-checking the front of an array is not a test. CHECK compares every element against the serial run.

Mark this section done

Three dependences, one question

Two different iterations i < j touch the same location X, and at least one writes it. Distance: j − i. (Pacheco & Malensek §5.5.)

Flow (RAW)

a[i] = a[i-1]+…

j reads what i wrote. Distance 1. A value travels from i to j. This one is real.

Anti (WAR)

a[i] = a[i+1]+…

i reads what j will overwrite. Distance 1. Only the storage is shared.

Output (WAW)

last = x[i];

Every iteration writes the same place. The sequentially last write must win.

Only flow carries a value. Anti and output are about names — and a name can be copied or privatized. Map the four loops onto the cards: B is flow, C is anti, D's tmp has both anti and output dependences on the name tmp but no value passes between iterations.

Why the flow bug is a wall

n = 10⁶, t = 2, static chunks. Thread 1 starts at i = 500,001 and reads a[500,000] — the last element of thread 0's chunk, which thread 0 writes at the end of its work. Thread 1 reads it at the start of its own. It gets the stale value and keeps going; every a[i] after that is built on it. 499,999 wrong.

Distance d under static chunks

A dependence of distance d links iteration i to iteration i + d. With contiguous chunks, the two ends of that pair land on different threads only for the last d iterations of each chunk — so at most d(t − 1) iterations can collide. The array is drawn with n = 24 so you can count the cells.

threads t 2 distance d 1

The test to carry in your head: could I run the iterations in reverse order, or shuffled, and get the same answer? If yes, parallel for is safe.

Mark this section done

Every removal has a price

Each BUG method on lecture10 has its fix beside it. Walk top to bottom: the price goes up.

Loop (method)	Dependence	Removal	What it costs
`tmp = …; y[i] = g(tmp)+tmp` (dep_Temp)	anti + output on tmp	privatize: declare tmp inside	nothing
`sum += x[i]` (dep_Sum)	flow on sum	`reduction(+:sum)`	t partial sums + one combine
`last = x[i]` (dep_Output)	output	`lastprivate(last)`: private copies; the last iteration's value is copied out	one copy-out at the end
`a[i] = a[i+1]+b[i]` (dep_Anti)	anti, distance 1	read from a copy of a	n more words + a copy pass
`factor = -factor` (pi_Legacy)	flow on factor	compute it from i	nothing
`a[i] = a[i-1]+b[i]` (dep_Flow)	flow, distance 1	change the algorithm: a scan (prefix sum, next screen)	~2n additions instead of n

The last row cannot be renamed away. A true flow dependence is removed by a different algorithm, and you pay for it in work. The fixes: dep_TempPrivate, dep_SumReduce, dep_OutputLast, dep_AntiCopy, pi_Fixed, dep_FlowScan — all print CHECK ok at 1, 2, 3, 4, 7 threads on the test machine.

lastprivate is introduced here, and only here, as the named removal for an output dependence: one clause, one sentence: private copies, and the sequentially last iteration's value is copied out.

The cheapest row, done wrong: last year's π loop

Pacheco's serial π loop carries factor = -factor from iteration to iteration: a flow dependence on factor, distance 1. The sign is a function of i, so compute it from i. The old openMp/LoopDeps code had that idea — and this is what it wrote.

double factor = 1.0;

#pragma omp parallel for reduction(+:sum) private(factor)
for (long i = 0; i < n; i++) {
    sum += factor / (2 * i + 1);
    if (i % 2 == 0) { factor =  1.0; }
    else            { factor = -1.0; }
}

pi_Legacy at one thread. What does CHECK say?

ok — one thread is the serial case; nothing can race. WRONG, but close: the signs lag by one term, so the series converges to a nearby number. WRONG, and not close — the first term is garbage. It does not compile: private and reduction cannot name different variables.

$ OMP_NUM_THREADS=1 ./Default/OMP pi_Legacy
CHECK pi_Legacy WRONG (pi = -nan, serial = 3.14159165359)

Two bugs. private(factor) gives each thread an uninitialized copy — the = 1.0 outside the region never reaches it — so the first term of every thread is garbage (here, -nan, and nan swallows the sum). And the sign is set after it is used, so even firstprivate would leave every term with the previous term's sign. Wrong at 1 thread. Not every parallel bug is a race, and "it's the serial case" is not a reason to skip CHECK at t = 1.

The fix is the table's cheapest row: factor = (i % 2 == 0) ? 1.0 : -1.0; computed before use. No carried value, no clause needed. pi_Fixed: CHECK ok at 1, 2, 3, 4, 7 threads.

Mark this section done

A prefix sum: more work, shorter chain

This is "change the algorithm". dep_FlowScan() on lecture10. Three phases; two waits, and both are part of the algorithm.

#pragma omp parallel
{
    int tid = omp_get_thread_num();
    int t   = omp_get_num_threads();

    #pragma omp single
    total.assign(t + 1, 0);               // then everyone waits

    long lo = n * tid / t;
    long hi = n * (tid + 1) / t;
    long long s = 0;

    for (i = lo; i < hi; i++) {           // phase 1
        s += b[i];
        a[i] = s;
    }
    total[tid + 1] = s;

    #pragma omp barrier

    #pragma omp single                     // phase 2: t-long serial scan
    for (k = 1; k <= t; k++) {
        total[k] += total[k - 1];
    }

    long long off = total[tid];
    for (i = lo; i < hi; i++) {           // phase 3
        a[i] += off;
    }
}

Three phases

Each thread scans its own block from zero.
One thread scans the t block totals.
Each thread adds its offset.

Two constructs

single: exactly one thread (any one) runs the next statement; the rest wait at its end — an implicit barrier. barrier: no one passes until all arrive.

Why the barrier before the second single?

Every thread must have written total[tid+1] before one thread scans them. The single's own implicit barrier then holds everyone until the scan is done, before anyone reads total[tid].

Step through it

threads

About 2n additions instead of n; the serial chain is n/t + t long, not n. On one thread this version is slower than the serial loop. That is the trade: more total work for a shorter dependency chain. CHECK dep_FlowScan ok at 1, 2, 3, 4, 7 threads. No speedup is quoted here on purpose: 10⁶ integer adds is memory-bound, the test machine has 2 cores, and the Cardinal run is not in yet. You will time it yourself below.

Mark this section done

Odd–even sort: the barrier is the fix

oddeven_OneRegion(). One team, n phases. Within a phase: disjoint pairs, no dependence. Between phases: flow.

#pragma omp parallel
for (int phase = 0; phase < N; phase++) {
    if (phase % 2 == 0) {
        #pragma omp for
        for (int i = 1; i < N; i += 2) {
            if (a[i-1] > a[i]) std::swap(a[i-1], a[i]);
        }
    } else {
        #pragma omp for
        for (int i = 1; i < N - 1; i += 2) {
            if (a[i] > a[i+1]) std::swap(a[i], a[i+1]);
        }
    }    // implicit barrier: phase k+1 waits for phase k
}

Two orders

omp for inside parallel: the team already exists; it just splits this loop among them, then waits (a barrier). No new fork.
Within a phase the pairs are disjoint: no dependence. Between phases: flow. The implicit barrier at the end of each omp for is what enforces it.
nowait drops that barrier: oddeven_Nowait 2000 --trials 100 gives CORRECT 0/100 at 2, 4 and 8 threads on the test machine. This one fails loudly and every time.

Phase by phase, 8 elements, 2 threads

With the barrier, every thread finishes phase k before anyone starts k+1. The nowait run shows one possible interleaving: thread 1 is never held back, so it runs its pairs of every phase before thread 0 has touched its own. The real interleaving differs run to run; the result is unsorted 100 times out of 100.

One team beats n teams

Pacheco's first version, oddeven_TwoRegions, opens a new parallel for every phase: n = 20,000 forks and joins. oddeven_OneRegion creates the team once.

n = 20,000, test machine, min over 15 runs (3 batches of 5)
                     t = 1      t = 2
oddeven_TwoRegions   0.333 s    0.167 s
oddeven_OneRegion    0.313 s    0.148 s
(0.167 − 0.148) / 20,000 ≈ 1 µs per extra fork/join

The machine was shared with other jobs; an earlier batch taken under heavier load gave 1.49 s and 3.44 s for the same two methods, which is why min-of-N matters. Also on the branch: oddeven_Legacy, the old OddEvenSort code, which took the vector by value and sorted a copy. CHECK WRONG at every thread count including 1 — a bug CHECK catches that has nothing to do with threads.

Mark this section done

The Week 9 race, run 100 times

sum += x[i] on a shared sum, n = 10⁶, no reduction clause. Run it 100 times at 2 threads, at 4, at 8. Count the runs whose sum matches serial. The test machine has 2 cores: at 4 and 8, threads take turns.

double sum = 0;

#pragma omp parallel for
for (long i = 0; i < n; i++) {
    sum += x[i];
}

Commit three numbers out of 100 — for 2, 4 and 8 threads — then pick the row that is closest to yours.

2 thr 4 thr 8 thr

Close to 0 / 0 / 0 — Week 9 showed this loop giving a wrong sum. Around 50 at every thread count — a coin flip. Most runs right at 2 and 4, fewer at 8. 100 / 100 / 100 — n = 10⁶ is too small to race.

Right 89 times in 100. The race is still there every time.

Real counts, course test machine (2 cores, shared with other jobs, g++ 13 -O2), --trials 100. Not Cardinal: the Cardinal run (jobScript.slurm → lec10/results/races.txt) has not been done, and an idle node with threads starting within microseconds of each other should look very different. Do not borrow these numbers for Cardinal.

The mechanism

At -O2 the compiler may assume no other thread touches sum (a data race is undefined behaviour), so each thread loads sum once at the start of its chunk, adds the whole chunk in a register, and stores once at the end. The run is right only if one chunk finished before the other began — the loop was right exactly when it did not really run in parallel. On a shared 2-core box with load average 4–12, one thread is often parked for a whole sub-millisecond chunk.

Why this does not contradict Week 9

n	chunk at t = 2	right
10⁶ (today)	about 0.5 ms	89 of 100
2·10⁷ (Week 9, `sum_Race`)	about 10 ms, 20× longer	1 of 20 — 19 of 20 wrong
10⁸	about 25 ms	0 of 20

Same race; n and chunk length differ. The longer the chunk, the less likely one finishes before the other starts.

Honesty about the numbers

A rerun of the same table gave dep_Sum 71 / 47 / 74. An earlier batch of the same binary gave dep_Temp 53 / 70 / 88, dep_Flow 39 / 0 / 0, dep_Output 61 / 21 / 7, and dep_Sum at n = 1000 gave 14 / 100 / 100 once and 100 / 81 / 84 another time. Those swings are the lesson: the count is a property of the machine, the load and the moment, not of the code.

Two rows to read carefully. dep_Temp is the genuinely small window — a few nanoseconds between the write of tmp and its read after g() — so it really is "right most of the time". dep_Flow is almost never right because its collision is the chunk boundary, where the reader arrives at the start of its work and the writer at the end of its own; it can only be right if the reader starts late. R06's What If (Nov 13) asks how often a racy recurrence comes out right: match the loop's shape to the row before you borrow a number.

Mark this section done

A passing run is one sample

Three detectors, in order of cost. In shared memory the loud failure is something you build yourself.

CHECK against serial. Integers exactly; floating-point sums within 1e-9 relative, because a reduction reassociates. Free, and you already do it.
Repeat runs. R06 asks for CORRECT 20/20 at 48 threads. Cheap, but weak: at 89 in 100 per run, 20 clean runs in a row happen 0.89²⁰ ≈ 10% of the time. A 1-in-1000 race needs thousands of runs.
A thread sanitizer. It watches the memory accesses, not the answer, so it reports a race on a run that came out right. It instruments every load and store and tracks happens-before. Price: 5–15× slower and more memory — run it once, on a small n.

How much do N clean runs prove?

per-run pass rate 0.890 runs in a row 20

p^N: the chance that a loop which passes a single run with probability p passes N in a row — and your test says "clean". The deck's point: at p = 0.89 and N = 20, about one time in ten. Slide the pass rate up to 0.999 and watch what 20 runs are worth against a rare race.

Our g++ build

g++ -fsanitize=thread cannot see libgomp's barriers and fork, so it reports "races" on correct code too.
Test machine, t = 2, n = 10⁴, g++ 13 -O1 -fsanitize=thread: 10 reports on dep_Temp, 9 on the fixed dep_TempPrivate, 14 on dep_FlowScan.
Archer = clang -fsanitize=thread + LLVM's libomp, with TSAN_OPTIONS="ignore_noninstrumented_modules=1". It knows OpenMP's synchronization. Use it if Cardinal has it (R06 says how to tell). g++'s reports are not evidence either way.

From R06 on, a race Archer reports means your code is wrong even if every answer looked right.

Mark this section done

The same bug in two dialects

"A must precede B." Threads and messages break it differently. This is row 3 of the payoff table; Wednesday adds the load-balance row.

OpenMP

a[i] = a[i-1]+b[i]

Nothing stops thread 1 from reading early. It gets a stale value and keeps going: a plausible wrong answer.

MPI

Send(…); Recv(…);

Both ranks call a blocking Send first. Past the eager limit each Send waits for a Recv never reached: the job hangs.

Underneath

A before B

Shared memory fails silently. Messages fail loudly. Same missing order.

Which failure would you rather ship? A hang is found in an afternoon. A race that passes 89 runs in 100 (dep_Sum) is not. In MPI the value only arrives by a message, so a missing order shows up as a wait that never ends. In OpenMP the value is already "there" in shared memory — just the old one — so nothing waits. In shared memory you must build the loud failure yourself: CHECK, repeat runs, a sanitizer.

Five more to classify

From the old "what's wrong" exercise, condensed. Name what is wrong with today's vocabulary; the fix is revealed when you pick.

Row 2 is worth saying aloud: changing the schedule changes who races, not whether they race. Row 4 previews Nov 9 (atomics, false sharing): per-thread histograms avoid both the race and the contention.

Mark this section done

Run it on Cardinal

New branch: lecture10. Same repository as last week. About 20 minutes. Every method prints CHECK; with --trials N it prints CORRECT k/N and ELAPSED is the minimum.

Fetch and check out the lecture branch

If you have not cloned yet: git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/openmp.git openmp first.
```
ssh <your-username>@cardinal.osc.edu
cd openmp
git fetch class
git checkout -b lecture10 class/fa2026-openmp/lecture10
```
Build, then get cores of your own

Modules do not persist between logins. The login node is shared; anything you count or time goes in an allocation.
```
module load gcc/12.3.0
cd Default && make OSC && cd ..
salloc -N 1 -n 1 -c 8 -t 00:15:00 -A PCS0313
```
Every run: OMP_NUM_THREADS=t srun -c 8 ./Default/OMP <method> [n] [--trials N]. Thread count always from OMP_NUM_THREADS. Default n = 10⁶ (oddeven: 20,000; use 2000 with --trials).

Experiments

A · The flow wall, and the algorithm that removes it

OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP dep_Flow     | grep -E 'CHECK|ELAPSED'
OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP dep_FlowScan | grep -E 'CHECK|ELAPSED'

What you should see

CHECK dep_Flow WRONG (… elements wrong, first at i = …) — with four chunks, expect the first wrong element at the first chunk boundary and the count to run through most of the array. CHECK dep_FlowScan ok. Compare the two ELAPSED lines yourself; the page quotes no speedup for the scan, and neither should you until you have run it at t = 1 as well.

B · The three shapes of wrong, at two threads

for m in dep_Flow dep_Anti dep_Temp dep_TempPrivate; do
    OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP $m | grep CHECK
done

What you should see

On the test machine: a wall (499,999 of 10⁶), a needle (1 of 10⁶, at i = 499,999), a scatter (about 0.1%, varying run to run), and ok. On Cardinal the counts for dep_Flow and dep_Anti should have the same shape; dep_Temp's count is a race and will differ. If dep_Anti shows 0 wrong, run it again: a boundary is wrong only if the neighbour got there first.

C · The Week 9 race, 100 times

Write down your k/100 for t = 2 and t = 8 before you run it.

OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP dep_Sum 1e6 --trials 100 | grep -E 'CORRECT|ELAPSED'
OMP_NUM_THREADS=8 srun -c 8 ./Default/OMP dep_Sum 1e6 --trials 100 | grep -E 'CORRECT|ELAPSED'

What you should see

CORRECT k/100 with a k you cannot predict from the code — that is the point. The test machine's 89 / 70 came from a shared 2-core box where a thread is often parked; an idle Cardinal node with 8 real cores and threads starting within microseconds of each other should be lower, possibly far lower. Run each line twice and compare the two k's. Then dep_SumReduce 1e6 --trials 100 for 100/100.

D · Drop the barrier

OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP oddeven_Nowait    2000 --trials 100 | grep CORRECT
OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP oddeven_OneRegion 2000 --trials 100 | grep CORRECT

What you should see

CORRECT 0/100 for the nowait version, on any machine: without the barrier, phase k+1 starts on a half-finished phase k. Then 100/100. This is the race that fails loudly and every time.

E · A bug that is not a race

OMP_NUM_THREADS=1 srun -c 8 ./Default/OMP pi_Legacy | grep CHECK
OMP_NUM_THREADS=1 srun -c 8 ./Default/OMP pi_Fixed  | grep CHECK
exit    # release the allocation

What you should see

CHECK pi_Legacy WRONG (pi = -nan, serial = 3.14159165359) on the test machine — at one thread. Then CHECK pi_Fixed ok. CHECK at t = 1 is the test people skip.

Before Friday Oct 30 (R05 lab): branch fa2026-openmp/lab05. Arrive with your R05 repository made and pushed — LAB05.md steps 1–3, including git config push.default upstream — or you lose the period to setup. R05 is the trapezoid, x² on [0, 5]: strong n = 10⁹, weak 10⁹ per thread, t = 1 … 48 on one socket, CHECK within 1e-9 relative at 1, 7, 8 threads, then sbatch, min of 5. The lab ends at "job submitted". Due Sun Nov 1. Reading: Pacheco & Malensek §5.5 and §5.6.2.

Mark this section done

Concept map

Four loops. Which can take #pragma omp parallel for as written?

Two threads. B, C and D are all wrong — but not in the same way.

Three shapes of wrong

Three dependences, one question

Flow (RAW)

Anti (WAR)

Output (WAW)

Why the flow bug is a wall

Distance d under static chunks

Every removal has a price

The cheapest row, done wrong: last year's π loop

A prefix sum: more work, shorter chain

Three phases

Two constructs

Why the barrier before the second single?

Step through it

Odd–even sort: the barrier is the fix

Two orders

Phase by phase, 8 elements, 2 threads

One team beats n teams

The Week 9 race, run 100 times

The mechanism

Why this does not contradict Week 9

Honesty about the numbers

A passing run is one sample

How much do N clean runs prove?

Our g++ build

The same bug in two dialects

OpenMP

MPI

Underneath

Five more to classify

Run it on Cardinal

Fetch and check out the lecture branch

Build, then get cores of your own

Experiments

A · The flow wall, and the algorithm that removes it

B · The three shapes of wrong, at two threads

C · The Week 9 race, 100 times

D · Drop the barrier

E · A bug that is not a race

Check yourself

Four loops. Which can take `#pragma omp parallel for` as written?