CS 4170 / 5170 · Week 13 · Wednesday, Nov 18 · review

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.

Every wrong answer and every slowdown on this page comes from one of the six questions. The skill is saying which one, and what line of OpenMP fixes it.

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.

#AskWhat answers it in OpenMPGet it wrong and
1Who owns each variable?shared, private, firstprivate, reduction, or declare it inside the loopwrong answers
2Does 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 writeswrong answers, sometimes
3What does keeping it right cost?critical, atomic and locks pay once per update; reduction pays once per threadright answers, slowly
4Do the iterations cost the same?the schedule clause: static for even work, dynamic for uneven workidle threads, or a trip per iteration
5Is each piece of work big enough?the chunk size, and the task cutoffmore bookkeeping than work, or too few pieces
6Do different threads write the same cache line?count in a local variable and write onceno 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
Bug, fine, or fine but slow?

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
Bug, fine, or fine but slow?

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
Bug, fine, or fine but slow?

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?

Snippet 3 passed its test at -O2 and failed at -O0. A test that passes does not prove a loop race-free.

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]++;
        }
    }
}
Bug, fine, or fine but slow?

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];
    }
}
Bug, fine, or fine but slow?

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?

Rare is not safe. Snippet 5 printed one wrong element in 2 × 10⁷, and a different number each run.

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);
}
Which line makes this loop parallel and right?

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);
}
Fill the blank twice: (A) for this loop, where late iterations cost far more than early ones, and (B) for a loop where every iteration costs the same.

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];
}
A plain parallel for gives wrong answers on both. What makes each one safe?

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);
    }
}
Three blanks. (1) appears twice.

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?

A clause can fix who owns a variable, how the work is dealt, and how an accumulation is combined. It cannot fix an iteration that needs the result of the one before it.

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.

NumberIn wordsFormula
Speedup Sone-thread time divided by p-thread timeS = T₁ / Tₚ
Efficiency Espeedup divided by the number of threads; 1 is idealE = S / p
Karp–Flatt ethe serial fraction that would explain this speedup; read its trend across pe = (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.

Which snippet from this page would draw this curve?

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.

One value of e does not name a cause. Its trend does: flat is a serial part, rising is a cost that grows with the threads, falling is uneven shares.

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.

The pairing is a fact to remember. The idea underneath is what you understand: different words, same mechanism, is a right answer.

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.

  1. Log in (put your OSC username in place of OSC_USERNAME):

    ssh OSC_USERNAME@cardinal.osc.edu
  2. 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
    salloc or srun fails?

    Skip the allocation. From the login node, paste this once; every srun below 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 "$@"; }
  3. 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
  4. 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 reduction
    Show the program
    s4_dynamic.cppB: dynamic,1 against static
    Show the program
    s5_counts.cppC: neighbouring counters against a local
    Show the program
  5. 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
done
What 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
done
What 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
done
What 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.

Write down one number from each experiment at 48 threads, and the mechanism that explains it. That pairing, a number and its mechanism, is the whole skill.

Check yourself

Six questions, instant feedback, nothing recorded.

1. A loop reads scale, set to 2.5 before the parallel region, and never writes it. Which data-sharing choice is correct and simplest?
A variable that is only read can stay shared. private would give each thread an uninitialized copy (snippet 1); firstprivate would work but copies for no reason.
2. Why is reduction(+:sum) much faster than putting sum += i inside critical?
Both give the right sum. critical makes every add wait its turn: 100,000,000 trips through the lock for n = 100,000,000. reduction makes one combine per thread.
3. Every iteration of a loop costs the same. Which schedule, and why?
Equal costs need no balancing, so anything dynamic only adds trips to a shared counter. On Cardinal at 48 threads the flat loop took 0.021 s with static and 5.8 s with dynamic, 1.
4. a[i] = a[i - 1] + b[i] inside a parallel for. What makes it correct?
The value is carried from each iteration to the next. A critical keeps two threads from writing at once but does not put the iterations in order. The scan does about 2n additions instead of n, and can run in parallel.
5. The task quicksort of 10,000,000 ints took 0.120 s with a cutoff of 10,000 and 0.807 s with a cutoff of 1, on the same 48 threads. Why is cutoff 1 slower?
A small cutoff means many small tasks: 19,999,998 of them here. Too few tasks is the other end: a cutoff of 5,000,000 left 4 pieces for 48 threads and took 0.590 s.
6. "An idle processor is the same waste at any scale" is the idea underneath which pairing?
Load balance: both hand out work on demand so nobody sits idle, and both pay a synchronized trip per hand-out.
← → keys also work