Callback —
Who Gets the Next i?
Same idea, other dialect. The schedule clause decides which thread runs which iterations; MPI's manager–worker makes the same decision with messages. Today we measure both on the same work.
Concept map
Three moves, in the deck's order: deal the iterations four ways, measure what each deal costs, then translate the winning deal into MPI. Click a node to jump to it.
Everything OpenMP on this page runs from the openmp repository, branch lecture10, method sched. The MPI program is a scratch file, not on any branch (the OpenMP repository stays OpenMP-only); its listing and output are on this page because the deck shows them. Every time on this page is from the course test machine (2 cores, shared with other jobs, g++ 13 -O2, min over 27 or 36 runs) — the Cardinal numbers for this branch do not exist yet. Monday was the Dependence row of the payoff table; today is the Load-balance row, with a preview of Granularity (Nov 4).
One loop, every schedule
sched() on lecture10. One binary sweeps every schedule because schedule(runtime) reads the schedule when the program runs, not when it compiles.
double work(bool tri, long i) {
if (!tri) {
return sin((double) i); // flat: one call, every i
}
double r = 0;
long start = i * (i + 1) / 2; // only keeps every j distinct
for (long j = start; j < start + i; j++) {
r += sin((double) j); // tri: this runs i times
}
return r;
}
omp_set_schedule(kind, chunk); // "dynamic,64": dynamic, 64
#pragma omp parallel reduction(+:sum)
{
int tid = omp_get_thread_num();
double c0 = threadCPU();
#pragma omp for schedule(runtime) nowait
for (long i = 0; i < n; i++) {
sum += work(tri, i);
}
busy[tid] = threadCPU() - c0; // my CPU time
finish[tid] = omp_get_wtime() - t0; // when I got here
}
The work
tri: the inner for runs from start to start + i, so iteration i makes exactly i sin() calls: work(0) makes none, work(9999) makes 9,999. Added up over n = 10⁴ iterations that is about 5 × 10⁷ calls. This is the old LoopScheduling code's f(i): cost grows linearly with i, so the iteration space is a triangle. flat: every iteration costs one call.
Two clauses, one line each
reduction on a bare parallel: a private sum per thread, added at the end — the same clause that fixed trap2_Reduction last Wednesday, here on a region instead of a loop. nowait: skip the barrier at the end of the omp for, so each thread records its own finish time. The region's own closing barrier still waits.
Why thread CPU time
threadCPU() is clock_gettime(CLOCK_THREAD_CPUTIME_ID): the CPU time this thread consumed. Unlike wall time, it does not grow when another process shares the core. On a shared 2-core test machine that is what makes the per-thread chart below trustworthy where the wall times are noisy.
What every run prints
- The work share per thread — counted (the sum of i over the iterations that thread ran), not timed. Shares are a property of the deal, not of the machine.
- Each thread's busy (CPU) seconds and finish time inside the loop.
CHECK sched ok|WRONGagainst the serial sum, thenELAPSED.
Command shape: OMP_NUM_THREADS=4 ./Default/OMP sched tri 10000 static. The schedule argument is one of static, static,64, dynamic,1, dynamic,64, guided. With OWNERS_CSV=file in the environment the run also writes which thread ran each i, one line per iteration — that is where the next screen's figure came from.
Four ways to deal the iterations
static and static,c are arithmetic done before the loop. dynamic and guided decide during it.
| Schedule | The rule | Decided |
|---|---|---|
| static | n/t in a row each. | before the loop |
| static,64 | chunks of 64, round robin: t0, t1, t2, t3, t0, … | before the loop |
| dynamic,64 | next chunk of 64 to whoever asks. | during the loop |
| guided | big chunks first, shrinking. libgomp sizes each as ⌈remaining / t⌉: 2500, 1875, 1407, 1055, 791, … | during the loop |
The OpenMP spec only says a guided chunk is "proportional to" unassigned iterations / threads and never below the chunk argument (guided,k). LLVM's libomp (clang, Intel) uses about remaining / (2t), so its first chunk at n = 10⁴, t = 4 would be about 1250. Say "big first, shrinking"; the exact sizes are the compiler's.
Who ran which i — sched tri 10000, 4 threads
Redrawn from the deck's description of its OWNERS_CSV runs (one run each, 4 threads on the 2-core test machine). static and static,64 are exact: they are arithmetic. For dynamic,64 and guided only the chunk sizes and the first owner are known from the deck and the CSV heads; the owners drawn are a model (next chunk to whichever thread is free, equal-speed threads) and are labelled so.
Deal it yourself
Small n so you can count the cells. Shares are counted work, as the program counts them. dynamic and guided show one possible assignment: the next chunk goes to whichever thread is free in a model where every thread runs at the same speed and a grab costs nothing. A real run differs.
A triangle of work
Iteration i costs i. Under schedule(static), each of the t threads gets one block of n/t consecutive i's — equal in number, not in cost.
schedule(static), work(i) = i. What fraction of the total work lands on thread 3? Then: the best possible speedup at 4 threads.static deals 2,500 iterations to each thread. A block's cost is its count × its average i:
| Thread | Iterations | Count | Average i | Cost ≈ count × average | Share of work |
|---|---|---|---|---|---|
| t0 | 0 … 2,499 | 2,500 | 1,250 | 3.1 M | 1/16 = 6.25 % |
| t1 | 2,500 … 4,999 | 2,500 | 3,750 | 9.4 M | 3/16 = 18.75 % |
| t2 | 5,000 … 7,499 | 2,500 | 6,250 | 15.6 M | 5/16 = 31.25 % |
| t3 | 7,500 … 9,999 | 2,500 | 8,750 | 21.9 M | 7/16 = 43.75 % |
Total ≈ 50 M. Same count, 7× the average cost of t0, so the shares are 1 : 3 : 5 : 7. The loop ends when t3 does: T ≥ 0.4375 × (one-thread time), so S ≤ 16/7 = 2.29. The program counts the same thing: sched tri 10000 static at 4 threads prints 6.2 / 18.7 / 31.3 / 43.8 % (exactly 6.25 / 18.75 / 31.25 / 43.75 with n finite).
Any number of threads: the last block holds (2t − 1)/t²
t is the number of threads; thread k (k = 0 … t − 1) owns share (2k + 1)/t² — the same count × average-i arithmetic as the table, for any t. At t = 4 that is 1, 3, 5, 7 sixteenths. Slide t and watch the biggest share, the speedup bound and the efficiency bound. Model, from the deck; the dots at t = 4 are the counted shares.
On Cardinal, the model's floor did not hold
The model says static's efficiency at 48 threads can be no worse than 0.51 if cost grows with i. Cardinal (sched tri 20000, min of 5, node c0111) measured 0.29.
| E(t), static | t = 2 | t = 8 | t = 48 |
|---|---|---|---|
| measured | 0.55 | 0.31 | 0.29 |
| model, cost grows with i | 0.75 | 0.53 | 0.51 |
The lower half of the i's used 8.5% of the CPU time; cost growing with i says 25%. So the cost grows faster than i: sin(j) slows down as j gets large, and j reaches 2·10⁸ here. The shape held — efficiency flat, Karp–Flatt falling — but the constant did not. That is a diagnosis: the mechanism was right, the exponent was wrong. A test you could run: time work(i) alone at i = 100 and i = 19,999.
What would you do about it? Commit an answer in your head before the next screen, which asks you to rank the five schedules.
Rank them at two threads
sched tri 10000 <schedule>, 2 threads. Same loop, same n = 10⁴; one thread takes 0.66 s whatever the schedule. The model says static can do no better than 0.66 × 3/4 = 0.50 s.
sched tri 10000 1 thread 2 threads S static 0.666 s 0.516 s 1.29 static,64 0.664 0.341 1.95 dynamic,1 0.659 0.350 1.90 dynamic,64 0.667 0.343 1.94 guided 0.659 0.343 1.94 model, static: S <= 4/3 = 1.33 T >= 0.50 s
Four schedules tie. Only the contiguous split loses. static landed at 1.29, just under the model's 1.33. static,64 is as good as dynamic here, with no run-time decisions at all: a fixed round-robin deal, no counter, no atomics, and it balances a linearly growing cost because every thread gets a slice from every part of the slope. The imbalance was predictable.
Real output, lecture10, course test machine (2 cores, shared with other jobs): min over 3 batches of 9 runs per cell. S against static at 1 thread (0.666 s). Single batches varied by up to 2× under load — static at 1 thread ranged 0.666–1.018 s — which is exactly why the course reduces with min-of-N. Do not quote these as Cardinal numbers.
Where the time went, thread by thread — sched tri 10000, 4 threads
Each bar is one thread's CPU-busy seconds inside the loop. static: 0.045, 0.131, 0.219, 0.306 s — proportional to the model's 1 : 3 : 5 : 7 (0.306/0.701 = 43.7%). Thread 0's 0.045 s against the 0.306 s the loop needs: idle for 85% of it. Every other schedule keeps all four near the mean. Under dynamic,1, thread 0 was busy 0.244 s — a thread that happens to hold a core longer takes more chunks — and all four threads finished at the same moment, 0.401 s. That is what dynamic does: work follows whoever is free.
Redrawn from the deck's numbers (one run each at 4 threads on the test machine, thread CPU clock). Only the static bars are given to three figures; the other schedules' bars are described as "near the line" and are not drawn.
The payoff line, said here in the deck: an idle processor is the same waste at any scale — a thread on one core, a rank on one node.
The price of asking
sched flat 1e7: 10⁷ iterations, each one sin() — about 14 ns of work (0.140 s / 10⁷, static at 1 thread, min of 36). Now every iteration costs the same, so there is nothing to balance.
0.353 s. (0.353 − 0.140)/10⁷ = 21 ns per grab, with nobody else touching the counter. dynamic,c is one atomic fetch-and-add on one shared counter per chunk; the grab still happens once per chunk at one thread. dynamic,64 at one thread: 0.143 s.
sched flat 1e7 1 thread 2 threads min of 36, test machine static 0.140 s 0.073 s dynamic,1 0.353 0.363 dynamic,64 0.143 0.078
0.363 s: slower than one thread. Every grab now pulls the counter's cache line from the other core (Week 8: the line is the unit of coherence). The grab gets slower than the work it hands out, and adding a thread makes the loop slower. Two cores fight over one line.
The model predicts both to three figures
Overhead ≈ t_grab / (c · t_iter), with t_iter = 14 ns and t_grab = 21 ns, both measured at one thread.
| chunk c | model overhead | predicted | measured (1 thread) |
|---|---|---|---|
| 1 | 21 / 14 = 1.5 → +150% | 0.140 × 2.5 = 0.350 s | 0.353 s (+152%) |
| 64 | 21 / (64 · 14) = 0.023 → +2.3% | 0.143 s | 0.143 s (+2.3%) |
The model is uncontended: it says nothing about the 2-thread row, where the counter's cache line is the bottleneck. Chunk size is the knob — c trades grab overhead against balance. That is granularity, the next screen and Nov 4's topic.
Chunk size: overhead vs tail
c is the number of iterations in one chunk. Each chunk costs one ask for work, then does c iterations. Overhead share = one ask ÷ (c × work per iteration); the tail — work left for one thread at the end — is at most one chunk. One line covers both dialects; only the price of an ask changes. This is the Granularity row, previewed as the deck previews it — Wed Nov 4 does the rest.
Slide the chunk
Two loops from today, one slider. Left: the flat 10⁷ loop, model cost of the grabs (one ask = 21 ns, work per iteration = 14 ns, both measured; the curve is the model). Right: the 10⁴ triangle, how much of the total work the last chunk holds — the tail that whoever draws it finishes alone. Exact arithmetic.
Too small
dynamic,1 on 14 ns iterations: +150%. The asking costs more than the work.
Too big
Chunk 1024 of a 10⁴ triangle: 10 chunks, and the last one (i = 9216 … 9999) holds 15% of all the work. Balance is gone.
The price of one ask: 21 ns vs ~4 µs
OpenMP grab: 21 ns, measured, uncontended. MPI request + reply: two messages, each with a fixed start-up cost of about 2 µs in the course's Week 5 model, so ≈ 4 µs (a model, not measured today). Ratio 4000/21 ≈ 190, so MPI chunks must hold ~200× more work. For 1% overhead: OpenMP chunk work ≥ 100 × 21 ns ≈ 2 µs; MPI ≥ 100 × 4 µs = 400 µs.
Manager–worker: rank 0 is the counter
Same idea, other dialect. Scratch mw.cpp, compiled with mpicxx -O2 — not on any branch: the OpenMP repository stays OpenMP-only, and it is not on the MPI branches either. Abridged as the deck abridges it.
OpenMP · dynamic, 64
One shared counter in memory: next = 0, 64, 128, …
Every thread asks the counter itself — one atomic fetch-and-add — gets a start index, runs its 64 iterations, and asks again.
Price of one ask: 21 ns (measured). Every thread does work.
MPI · manager–worker, 64
No shared memory, so rank 0 plays the counter: next = 0, 64, 128, …
A worker Sends its result ("done"); rank 0 Recvs from whoever finished and Sends back the next start — or STOP.
Price of one ask: ~4 µs (a round trip, model). Rank 0 only deals.
The code, abridged
if (rank == 0) { // MANAGER: rank 0 is the counter
// prime: send each worker one chunk start;
// next = (p - 1) * CH; active = p - 1
while (active > 0) {
Recv(&part, ANY_SOURCE, &st); // SOMEONE finished
total += part;
int tag = next < n ? WORK : STOP; // give THEM the next chunk
Send(&next, st.MPI_SOURCE, tag);
if (tag == WORK) {
next += CH;
}
else {
active--;
}
}
}
else { // WORKER: ask, compute, answer
for (;;) {
Recv(&lo, 0, ANY_TAG, &st);
if (st.MPI_TAG == STOP) {
break;
}
// part = sum of work(i), i in [lo, lo + CH)
Send(&part, 0);
}
}
The translation
Replace "atomic fetch-and-add on a counter" with "Recv from anyone, Send to whoever it was". next is the shared loop counter; one Recv + Send round trip replaces one atomic grab. MPI_ANY_SOURCE is what makes it dynamic: the manager does not decide who is next, arrival order does — Week 4's ANY_SOURCE race, used on purpose this time.
What OpenMP hid
Rank 0 does no work at all: one process in p is the counter. And each chunk costs a message round trip — about 4 µs on the course model (two messages, each with a ~2 µs fixed start-up cost), against the 21 ns grab measured on the previous screen.
Abridged: MPI_ prefixes, counts, datatypes and the communicator are dropped; the priming loop and the worker's inner loop are one comment each (the real file has them, with the next < n guard). Same work units as sched tri: work(i) is the identical function, CH the chunk size.
Watch the messages
n = 10,000, work(i) = i, as in the deck's run. Model: every worker runs at the same speed and a message costs nothing, so the assignment is one possible order — a real run's arrival order differs. Each chunk costs two messages: a Send from the manager and a result back; the end costs one STOP per worker.
mw 10000 1 — a round trip per iteration of the triangle, 10,000 of them. Compared with chunk 64?mw 10000 64 static T = 0.572 s
rank 1 work 25.0% rank 2 work 75.0%
mw 10000 64 (chunk 64) T = 0.410 s
rank 1 49.1% 75 ch rank 2 50.9% 82 ch
mw 10000 1 (chunk 1) T = 0.402 s
rank 1 52.0% 5080 ch rank 2 48.0% 4920 ch
mw 10000 1024 (chunk 1024) T = 0.486 s
rank 1 47.2% 5 ch rank 2 52.8% 5 ch
Static split: 25/75. Manager–worker: 49/51. The block split over 2 workers is the same (2k + 1)/t² as static, with t = 2: 1/4 and 3/4. Chunk 64 balances it. Chunk 1 is fine too: the average work(i) is 5,000 sin() calls ≈ 65 µs (13 ns each: 0.659 s / 5 × 10⁷), while a same-node round trip is on the order of a microsecond — the overhead ratio is tiny. Shrink the work per iteration to 14 ns (the flat loop) and chunk 1 in MPI would be hopeless: 4 µs of messaging per 14 ns of work. Chunk 1024: only 10 chunks; the last holds 15% of all the work, and whoever draws it finishes last. Too-big chunks bring the imbalance back.
Real output, Open MPI, course test machine (2 cores, 3 processes oversubscribed, mpiexec --oversubscribe -n 3), best of 5. Not Cardinal. Timings are noisy: 3 processes on 2 cores, and the manager spins in MPI_Recv (Open MPI polls), using CPU — 0.18 s busy in the chunk-1024 run. Read the shares, not the seconds.
The idea underneath
Four rows of the payoff table; today fills the third. Granularity is written exactly as it will be written everywhere else.
| Concept | Shared-memory form | Distributed form | The idea underneath |
|---|---|---|---|
| Decomposition | loop partition; schedule clause | explicit Scatter | someone decides who owns which data; OpenMP hides it |
| Dependence (Mon) | loop-carried dependence; races | send/recv ordering; deadlock | "A must precede B" — one fails silently, one loudly |
| Load balance (today) | schedule(dynamic) | manager–worker | an idle processor is the same waste at any scale |
| Granularity (Nov 4) | task cutoff (size of the smallest task) | message size (the knee where start-up cost stops dominating) | per-unit overhead sets a floor on useful work size |
Read the Load-balance row with today's numbers
OpenMP · static
MPI · static split
Underneath
Decomposition is the same table one row up: the schedule clause is the decomposition decision, and static is Scatter with equal counts. Today's chunk size is the Granularity row's idea applied to a loop; the table keeps its own wording. Nov 18 is the day this table gets rebuilt from memory.
Run it on Cardinal
Same branch as Monday: lecture10, method sched. About 20 minutes. There are no Cardinal numbers for this lecture yet — every time quoted on this page is from the 2-core test machine. You are producing the first Cardinal column.
-
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 openmpfirst. If you builtlecture10on Monday, skip to step 2.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 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 sched <tri|flat> [n] [schedule]. Thread count always fromOMP_NUM_THREADS. Schedules:static,static,64,dynamic,1,dynamic,64,guided.
Experiments
A · Four deals of the triangle, 4 threads: shares and finish times
for s in static static,64 dynamic,64 guided; do
echo "== $s"
OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP sched tri 10000 $s
doneWhat you should see
Under static the counted shares are 6.2 / 18.7 / 31.3 / 43.8 % — they are arithmetic, so Cardinal prints the same four numbers. Thread 0's finish time is far ahead of thread 3's; on the test machine thread 0 was idle for 85% of the loop. Under static,64, dynamic,64 and guided all four shares sit near 25% and the finish times bunch together; the dynamic and guided shares move a little from run to run, static,64's do not. CHECK sched ok every time. No Cardinal seconds exist to compare against; write yours down.
B · Rank five schedules at 2 threads
Write your order down before you run it. One run per cell is one sample; the deck's table is min of 27.
for s in static static,64 dynamic,1 dynamic,64 guided; do
echo -n "$s "
OMP_NUM_THREADS=2 srun -c 8 ./Default/OMP sched tri 10000 $s | grep ELAPSED
doneWhat you should see
The shape of the deck's table, not its seconds: four schedules close together and static clearly behind, at about 3/4 of the one-thread time or worse (the model's floor is 0.75 × T₁). Run static at OMP_NUM_THREADS=1 too and compute S yourself. Cardinal's cores are not the test machine's, so expect different absolute times.
C · The price of a grab: flat work, 1 and 2 threads
for t in 1 2; do
for s in static dynamic,1 dynamic,64; do
echo -n "t=$t $s "
OMP_NUM_THREADS=$t srun -c 8 ./Default/OMP sched flat 1e7 $s | grep ELAPSED
done
doneWhat you should see
At 1 thread, dynamic,1 far slower than static (test machine: 0.353 vs 0.140 s), dynamic,64 within a few percent of static. Your grab cost: (Tdynamic,1 − Tstatic) / 10⁷ — the test machine gave 21 ns. At 2 threads, static about halves; dynamic,1 does not improve, and on the test machine it got slower than one thread (0.363 s). Whether Cardinal's two cores contend the same way is your measurement.
D · Who ran which i
for s in static,64 dynamic,64 guided; do
OWNERS_CSV=owners_$s.csv OMP_NUM_THREADS=4 srun -c 8 ./Default/OMP sched tri 10000 $s > /dev/null
echo "== $s: $(uniq -c owners_$s.csv | wc -l) runs of consecutive i on one thread"
uniq -c owners_$s.csv | head -8
done
exit # release the allocationWhat you should see
The file has one line per iteration: the thread that ran it. uniq -c collapses consecutive iterations on the same thread into one run. static,64: 157 runs of 64 (the last of 16), threads 0, 1, 2, 3, 0, … — deterministic. dynamic,64: 157 chunks in principle; the test machine showed 130 runs because neighbouring chunks taken by the same thread merge. guided: 30 chunks of 2500, 1875, 1407, 1055, 791, … (26 runs after merging on the test machine). On Cardinal the dynamic and guided counts will differ; the static,64 count will not.
E · Optional: the batch sweep
sbatch jobScript.slurm # from the repository root; writes lec10/results/data.csvWhat you should see
jobScript.slurm on lecture10 runs the same sweep at 1–48 threads with n = 20,000, one node, one task, pinned with OMP_PROC_BIND=close OMP_PLACES=cores. It has not been run yet, so there is nothing to compare to except the model: for static at 48 threads, S ≤ 48²/95 = 24.3 and E ≤ 0.51 — one Cardinal socket, half of it idle on average. If your E for static sits near 0.5 while the other four climb, you have measured the triangle.
fa2026-openmp/lab05. Arrive with your R05 repository made and pushed — the 50 minutes are for the prediction, three TODOs and sbatch. Prediction in the first 5 minutes: with the fixed pilot, E at 48, the first t with E < 0.90, the Karp–Flatt trend. CHECK at 1, 7, 8 threads, submitted by minute 45. Due Sun Nov 1. R05's trapezoid loop has uniform iterations: which schedule does it want, and why? The deck asks; it does not answer. Reading: Pacheco & Malensek §5.7 (scheduling loops). Mon Nov 2: OpenMP III — sections and tasks. Wed Nov 4: task cutoff ≡ the message-size knee.Check yourself
Six questions, instant feedback, nothing recorded.
schedule(static). Thread 3's share of the work, and the best possible speedup?mw 10000 1024: two workers, chunks of 1024 on the triangle. Shares 47.2 / 52.8 %, 5 chunks each, yet T = 0.486 s against 0.410 s at chunk 64. What went wrong?