Week 9 · OpenMP I · Companion to lecture 09a

One Process,
Many Threads

Five weeks of MPI taught you to move data on purpose. Today nothing moves: every thread can already see everything. That removes most of the code, and all of the protection.

Concept map

Click a node to jump to it. Grey nodes are later lectures.

todaylater

The thread through all of it: sharing is free; collisions are yours. private, firstprivate and reduction are how you say who owns what.

Mark this section done

The bridge: what you did in MPI, and what changes

One address space changes everything. Every row below is something you already know from Weeks 3–7.

	MPI (Weeks 3–7)	OpenMP (from today)
Unit of work	process · rank 0 … p−1	thread · id 0 … t−1
Memory	each rank has its own copy of every variable	one copy, and every thread can see it
Moving data	Send / Recv / Bcast / Scatter — you write it	nothing to write: just read the variable
Who owns which data	you decide, explicitly (Scatter, n/p)	the loop schedule decides, silently
A mistake looks like	a hang or an abort — loud	a plausible wrong number — silent
Launch	`srun -n p ./MPI`	`OMP_NUM_THREADS=t ./OMP` (one task)

Quick check. In MPI, could rank 3 accidentally overwrite rank 5's partial sum? In OpenMP, could thread 3 overwrite thread 5's?

Yes in both — a bug is a bug. No in MPI, yes in OpenMP. Yes in MPI, no in OpenMP — the runtime protects threads. No in both — each has its own variables.

In MPI, rank 3 has no way to name rank 5's memory; the only route is a message. In OpenMP both threads can see the same variable, so if both use it, one write can clobber the other. That is what "no protection" means, and it is the theme of the next three weeks.

Mark this section done

Fork, run the block t times, join

Before the pragma, one thread. At it, the runtime forks a team. Every thread runs the whole block. At the closing brace nobody continues until everyone has finished.

// lecture09 · hello_Threads()
std::vector<int> seen(t, 0);        // before the region: shared

#pragma omp parallel                // fork: t threads start here
{
    int tid = omp_get_thread_num(); // inside: private. 0 … t-1
    int nt  = omp_get_num_threads(); // t

    printf("Hello from thread %d of %d\n", tid, nt);

    seen[tid] += 1;                 // own slot: no collision
}                                   // join: implicit barrier

// CHECK: every id 0 … t-1 appears exactly once

MPI map: omp_get_thread_num is MPI_Comm_rank; omp_get_num_threads is MPI_Comm_size. Outside a parallel region num_threads is 1.

threads 4

$ OMP_NUM_THREADS=4 ./Default/OMP hello_Threads

The order changes every run. The real run on the course test machine printed 2, 1, 0, 3. Why printf and not cout? One printf call writes one line; a cout << chain is several calls, and threads interleave between them.

Mark this section done

Who owns which iteration?

parallel for hands out the iterations. In Week 4 you wrote this split by hand. Here the schedule decides, and does not tell you.

16 iterations, 3 threads, #pragma omp parallel for. Which iterations does thread 0 run? Somebody gets an extra one — who?

Round-robin: thread 0 gets 0, 3, 6, 9, 12, 15. Blocks of 5, and the last thread takes the extra: 0–4, 5–9, 10–15. Blocks, and the first thread takes the extra: 0–5, 6–10, 11–15. Random — the runtime assigns iterations as threads become free.

Contiguous blocks, and the first n % t = 1 thread takes one extra. That is exactly Week 4's fourthMethod: base = n / p, extra = n % p, and the first extra ranks take one more. The difference: you wrote nothing. No myA, no myN, no remainder bug.

$ OMP_NUM_THREADS=3 ./Default/OMP for_Owners 16
thread 0: iterations 0..5    (6)
thread 1: iterations 6..10   (5)
thread 2: iterations 11..15  (5)
CHECK for_Owners ok

Explore the split

n threads 3

Try t = 7 with n = 16: 3, 3, 2, 2, 2, 2, 2. Honest caveat: with no schedule clause the default is implementation-defined. GCC's libgomp and LLVM's libomp both use static, but the spec does not promise it. If the split matters, write schedule(static) and say so. schedule(dynamic) is Wednesday Oct 28.

Mark this section done

Shared, private, firstprivate

Shared is the default. That is the convenient choice and the dangerous one.

shared	One variable, every thread sees it. The default for anything declared before the region.
private(x)	Each thread gets a new x. It starts uninitialized; the outer value does not come in.
firstprivate(x)	Each thread gets a new x, initialized from the value before the region. Either way the copies vanish at the join: the outer x is unchanged.
automatic	Declared inside the region, or the index of the loop directly under `parallel for`: private. An inner loop's `j` declared outside is shared.
default(none)	The compiler makes you name the scope of every variable. Use it when unsure.

Memory picture

Before the region, h = 0.5 is set once. Pick the clause and watch where it lands in three threads.

Shared memory (one copy)

Someone privatized h "to be safe". Sum of f(a + i·h), f(x) = x², on [0, 5], n = 10⁷. Right answer: h·sum ≈ 41.67. With one thread, what prints?

double h = (b - a) / n;
double s = 0.0;

#pragma omp parallel for private(h) reduction(+:s)
for (long i = 1; i < n; i++)
    s += f(a + i * h);

41.67 — one thread cannot race, so nothing can go wrong. A little off — the private copy loses a few bits. Something undefined — 0, garbage, or nan depending on the compiler. A compile error — you cannot privatize a variable you only read.

Wrong at one thread. Not a race: a new, empty h. private(h) declares a new h inside each thread; nothing is copied in. g++ 13 at -O2 happened to give 0, so every term is f(0) = 0. clang 18, same source, gives nan. That is what undefined behaviour means.

$ make all
warning: 'h' may be used uninitialized
$ OMP_NUM_THREADS=1 ./Default/OMP scope_PrivateBug
h*sum = 0   serial h*sum = 41.6666604167
CHECK scope_PrivateBug WRONG
(t = 2, 3, 4, 7: the same)
clang++ -O2, same source:   h*sum = nan
firstprivate(h):  41.6666604167   CHECK ok

The compiler warned. Read warnings. Fix: firstprivate(h), or leave h shared — it is only read.

Rule of thumb. Declare it inside the loop if you can. Only read, never written? Leave it shared. Written by every thread? It needs its own copy — or a reduction.

Mark this section done

The race

Add 0 + 1 + … + (n − 1). n = 2·10⁷, two threads, no protection.

long sum = 0;

#pragma omp parallel for
for (long i = 0; i < n; i++)
    sum += i;

Exact answer: 199,999,990,000,000. Right or wrong? If wrong — too big or too small? Run it 20 times: how many are wrong?

Right every time — addition is addition. Wrong sometimes, could be too big or too small. Wrong most of the time, always too small. Wrong every time, always too big.

Wrong 19 times in 20 at t = 2, and always too small. Lost updates can only lose, never add.

expected         199999990000000
t=1              199999990000000   CHECK ok
t=2              149999995000000   CHECK WRONG
t=2               49999995000000   CHECK WRONG
t=2              199999990000000   CHECK ok
t=4               62499997500000   CHECK WRONG

20 runs each:  t=1  0 wrong
               t=2  19 wrong
               t=4  17 wrong

149999995000000 is exactly thread 1's half: 10⁷ + … + (2·10⁷ − 1). Thread 0's entire contribution is gone. The one right answer in 20: one thread finished before the other started. That is the most dangerous outcome — it passes a test.

Step through it

sum += i is three steps: load sum, add i, store sum. A tiny model: n = 6, two threads, thread 0 owns 0–2, thread 1 owns 3–5. Pick an interleaving and step.

thread 0 · i = 0, 1, 2

—

shared `sum`

thread 1 · i = 3, 4, 5

—

Expected: 0+1+2+3+4+5 = 15.

Mark this section done

Three ways to make it right

critical and atomic protect every update. reduction removes the sharing: n synchronizations become t.

// (1) critical: a lock around the block; one thread at a time. n lock handoffs.
#pragma omp parallel for
for (long i = 0; i < n; i++) {
    #pragma omp critical
    sum += i;
}

// (2) atomic: one hardware read-modify-write per update. Still n, on one cache line.
#pragma omp parallel for
for (long i = 0; i < n; i++) {
    #pragma omp atomic
    sum += i;
}

// (3) reduction: a private sum per thread, starting at 0; t partials combined at the end.
#pragma omp parallel for reduction(+:sum)
for (long i = 0; i < n; i++)
    sum += i;

Count the synchronizations

n threads 2

	What waits	Synchronizations
critical	every update, through one lock
atomic	every update, one locked add on one cache line
reduction	only the final combine, one per thread

reduction is MPI_Reduce in Week 4's clothes: the runtime gives every thread a private sum initialised to the identity (0 for +), lets each run its share with no synchronization, and combines t partials once. The count is the point, not the shape.

Measured on Cardinal, Oct 19 2026

One node, gcc/12.3.0, OMP_PROC_BIND=close OMP_PLACES=cores, n = 2·10⁷, min of 5. Log scale. Hover a point.

ms	t=1	2	4	8	16	48
sum_Race (wrong)	7.46	3.73	1.87	0.938	0.474	0.168
sum_Critical	411	1819	2796	3897	4752	8559
sum_Atomic	134	417	424	497	507	524
sum_Reduction	7.45	3.73	1.87	0.937	0.469	0.166

critical gets slower with every thread added: 20.5 ns per update at t = 1, 428 ns at t = 48 — about 52,000× behind reduction. Each update moves the lock's cache line between cores.
atomic jumps 3× from one thread to two, then stays flat. n locked adds on one line, however many cores.
reduction: speedup 44.9 at 48 threads. sum_Race is exactly as fast — and wrong. Fast and wrong is still wrong.

A colleague says: "critical and atomic are both O(n) synchronizations, so they should scale about the same." The Cardinal data says otherwise. Why does critical keep getting worse while atomic flattens?

atomic uses more threads internally, so it hides the cost. A critical section is a lock: acquire, update, release, and the lock itself bounces between cores on every handoff. An atomic is one hardware instruction on the data line — contended, but no separate lock to pass around. The compiler converts atomic into a reduction behind the scenes. critical is only slow because of printf inside it.

Both serialize every update, so neither can beat n × (one update in turn). The lock adds a second shared object to the fight, and a handoff is far more than one instruction. atomic hits a ceiling at the cache-line transfer rate; critical keeps paying more as more threads queue for the lock. Neither is the answer when a reduction fits.

Mark this section done

Run it on Cardinal

Everything above is real output from branch lecture09. Reproduce it, then break it on purpose. About 25 minutes.

Log in and clone the class repository (once)

VS Code Remote-SSH to cardinal.osc.edu, Code Server from ondemand.osc.edu, or plain ssh. If you cloned openmp for R05 already, skip the clone. SETUP.md on the branch covers SSH keys for GitLab.
```
ssh <your-username>@cardinal.osc.edu
git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/openmp.git openmp
cd openmp
```

Check out the lecture branch

git fetch class
git checkout -b lecture09 class/fa2026-openmp/lecture09
ls                                     # LECTURE09.md  src/  Default/  harness/  jobScript.slurm

Load the compiler and build

Modules do not persist across logins. Expect one warning: 'h' may be used uninitialized. It is the bug in scope_PrivateBug. Leave it.
```
module load gcc/12.3.0
cd Default && make OSC && cd ..
```
Get cores of your own

The login node is shared. Correctness runs are fine there at tiny sizes; anything you time goes in an allocation. Eight cores for fifteen minutes is enough for all of this.
```
salloc -N 1 -n 1 -c 8 -t 00:15:00 -A PCS0313
```
Inside the allocation, every run is OMP_NUM_THREADS=t srun -c 8 ./Default/OMP <method> [n]. The thread count always comes from the environment variable, never an argument. Every method ends in CHECK … ok or WRONG, then ELAPSED.

Experiments

Each one has a "what you should see". Predict first, then open it.

A · The order moves

OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP hello_Threads
OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP hello_Threads
OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP hello_Threads

What you should see

Four lines each time, CHECK hello_Threads ok each time, and the order of the four lines changes between runs. If it does not change in three runs, try six — a 4-thread fork is fast enough that one ordering can repeat. Also note the THREADS 4 line: the team the environment variable actually gave you.

B · Who got which iteration, at an awkward t

OMP_NUM_THREADS=3 srun -c 8 ./Default/OMP for_Owners 16
OMP_NUM_THREADS=7 srun -c 8 ./Default/OMP for_Owners 16
OMP_NUM_THREADS=7 srun -c 8 ./Default/OMP for_Owners 100

What you should see

t = 3: 0..5, 6..10, 11..15. t = 7, n = 16: 3, 3, 2, 2, 2, 2, 2. t = 7, n = 100: 100 = 7·14 + 2, so the first two threads get 15 and the rest 14. Compare with the explorer above. Then ask: who decided this? You did not write a line of it.

C · Wrong at one thread

OMP_NUM_THREADS=1 srun -c 8 ./Default/OMP scope_PrivateBug
OMP_NUM_THREADS=1 srun -c 8 ./Default/OMP scope_Firstprivate
OMP_NUM_THREADS=8 srun -c 8 ./Default/OMP scope_PrivateBug

What you should see

scope_PrivateBug is WRONG at t = 1 and at t = 8 — same number. A race depends on timing; this depends only on the pragma. scope_Firstprivate is ok. On Cardinal's gcc 12 the wrong value is 0; on your laptop under clang it may be nan. Both are "undefined", which is the lesson.

D · The race, five times

for i in 1 2 3 4 5; do OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP sum_Race | grep CHECK; done
for i in 1 2 3 4 5; do OMP_NUM_THREADS=8 srun -c 8 ./Default/OMP sum_Race | grep CHECK; done

What you should see

Mostly WRONG. Occasionally ok — and that is the one to worry about, because a test that passes once can ship. Run the full line (without grep) once and look at the wrong number: at -O2 each thread keeps sum in a register and stores it once, so the wrong answer is usually exactly one thread's share, not a few lost updates.

E · Correct three ways: read ELAPSED

for m in sum_Critical sum_Atomic sum_Reduction; do
    OMP_NUM_THREADS=1 srun -c 8 ./Default/OMP $m | grep -E 'CHECK|ELAPSED'
done
for m in sum_Critical sum_Atomic sum_Reduction; do
    OMP_NUM_THREADS=8 srun -c 8 ./Default/OMP $m | grep -E 'CHECK|ELAPSED'
done

What you should see

All six ok. At t = 8 the Cardinal table above says roughly: critical ≈ 3.9 s, atomic ≈ 0.5 s, reduction ≈ 0.9 ms. Yours will differ in the milliseconds (single run, not min-of-5) but not in the order, and critical at 8 should be slower than critical at 1. Then type exit to release the allocation.

F · Stretch: the whole sweep as a batch job

exit                                   # leave the salloc first
sbatch jobScript.slurm                 # from the repository root
squeue -u $USER
# when it finishes:
cat lec09/results/reduced.txt
grep -c WRONG lec09/results/run_t*.txt

What you should see

A 48-core, min-of-5 reproduction of the table above, about 15 minutes in the queue plus run time. The only WRONG lines should be scope_PrivateBug (every t) and sum_Race (t ≥ 2, usually). Anything else WRONG is news — tell me.

Break it yourself. Open src/main.cpp, change sum_Reduction's clause to firstprivate(sum), rebuild, run at t = 4. Predict the number before you run it. Then put it back (git checkout src/main.cpp).

Mark this section done

What comes next

Wed — code walk (09b)

The trapezoid rule three ways, from the old course code: TrapRule1, 2, 3. Same problem as Week 4: x² on [0, 5]. Watch what disappears from the code, and what bug comes back. Branch lecture09, the trap methods.

Then

Fri: Quiz 2 — MPI only, nothing from today. Mon: OpenMP II, loop-carried dependence and races that pass your test. R05 posted; Fri Oct 30 lab: trapezoid strong and weak scaling.

One address space: sharing is free, collisions are yours. private, firstprivate, reduction are how you say who owns what.

Mark this section done

Concept map

The bridge: what you did in MPI, and what changes

Fork, run the block t times, join

Who owns which iteration?

Explore the split

Shared, private, firstprivate

Memory picture

Shared memory (one copy)

The race

Step through it

thread 0 · i = 0, 1, 2

shared sum

thread 1 · i = 3, 4, 5

Three ways to make it right

Count the synchronizations

Measured on Cardinal, Oct 19 2026

Run it on Cardinal

Log in and clone the class repository (once)

Check out the lecture branch

Load the compiler and build

Get cores of your own

Experiments

A · The order moves

B · Who got which iteration, at an awkward t

C · Wrong at one thread

D · The race, five times

E · Correct three ways: read ELAPSED

F · Stretch: the whole sweep as a batch job

Check yourself

What comes next

Wed — code walk (09b)

Then

shared `sum`