OpenMP: Reusing Threads and Scheduling Loops

Module 14

Two questions about parallel loops

In Module 13, one parallel for directive divided a loop among the threads. We let OpenMP make two decisions for us. Today we look at both, following §§5.6–5.7 of Pacheco and Malensek:

  1. When are the threads started? A loop nested inside another loop could start a new team on every pass. Can one team be reused?
  2. Which thread gets which iterations? Equal shares of iterations are not equal shares of work when some iterations cost more than others.

Our programs are:

As before, compile and run these on PicoCluster with -fopenmp.

Odd-even sort, again

We sorted with neighbor exchanges in Module 7, where each MPI process held one value. With threads, the whole list sits in one shared array, so a “neighbor exchange” is just a swap of two elements.

An even phase compares the pairs starting at even indices, and an odd phase compares the pairs starting at odd indices. With n values, n phases are enough to sort any list. For n = 8:

Phase Pairs compared
Even (0,1), (2,3), (4,5), (6,7)
Odd (1,2), (3,4), (5,6)

Find the dependences. Use the test from Module 13: does one iteration read or write something another iteration writes?

  • Inside one phase, are two different pairs ever using the same element?
  • Between phases, can phase p + 1 start before phase p has finished?

Within a phase, the pairs do not overlap, so those comparisons can happen at the same time on different threads. The inner loops have no loop-carried dependence.

The outer loop does. Phase p + 1 compares elements that phase p may have just swapped, so the phases must happen in order. We can parallelize inside a phase but not across phases.

This is why §5.6 moves from bubble sort to odd-even sort. In an ordinary bubble sort, each comparison can use the result of the one just before it, so the inner loop has a loop-carried dependence too.

First version: parallel for in each phase

The core of omp_odd_even1.c follows that reasoning directly:

for (int phase = 0; phase < n; phase++) {
    if (phase % 2 == 0) {
#       pragma omp parallel for num_threads(thread_count) \
            default(none) shared(a, n)
        for (int i = 1; i < n; i += 2) {
            if (a[i - 1] > a[i]) {
                int tmp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = tmp;
            }
        }
    } else {
#       pragma omp parallel for num_threads(thread_count) \
            default(none) shared(a, n)
        for (int i = 1; i < n - 1; i += 2) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i + 1];
                a[i + 1] = a[i];
                a[i] = tmp;
            }
        }
    }
}

What keeps the phases in order? parallel for has an implicit barrier at the end of the loop, so the next phase cannot begin until every thread finishes this one. This is the same phase pattern as Module 11, except that we did not have to write the barrier.

There is a possible cost. Each pass through the outer loop reaches a parallel for directive, and each one may start and end a team of threads. With 20,000 values, that is 20,000 parallel regions.

Second version: one team, two for directives

The for directive, without the word parallel, divides a loop among the threads of a team that already exists. It starts no threads. The core of omp_odd_even2.c starts the team once, before the outer loop:

#   pragma omp parallel num_threads(thread_count) \
        default(none) shared(a, n)
for (int phase = 0; phase < n; phase++) {
    if (phase % 2 == 0) {
#       pragma omp for
        for (int i = 1; i < n; i += 2) {
            /* compare and swap a[i - 1] and a[i] */
        }
    } else {
#       pragma omp for
        for (int i = 1; i < n - 1; i += 2) {
            /* compare and swap a[i] and a[i + 1] */
        }
    }
}

Read this carefully, because the two directives do different jobs:

Directive Which loop What happens
parallel Outer phase loop Every thread runs every phase. The outer loop is not divided.
for Inner i loop The threads share this phase’s iterations, then wait at an implicit barrier.

Discuss: phase is declared in the for statement, inside the parallel region, so each thread has its own copy. What would go wrong if all the threads shared one phase? The book’s version declares it earlier and lists it in private(phase).

Build and compare

Both programs take a thread count and a list size, fill the list with the same pseudorandom values, and check the result. Lists of 20 values or fewer are printed. Start small, then time the default of 20,000 values:

gcc -Wall -O2 -fopenmp -o omp_odd_even1 omp_odd_even1.c
gcc -Wall -O2 -fopenmp -o omp_odd_even2 omp_odd_even2.c
./omp_odd_even2 4 8
./omp_odd_even1 4
./omp_odd_even2 4

Every run should print Sorted: yes. Fill in your times, running each a few times:

Threads Version 1: parallel for (s) Version 2: for (s) Book, version 1 (s) Book, version 2 (s)
1 0.770 0.732
2 0.453 0.376
4 0.305 0.239

The book’s system ran version 2 at least 17% faster with two or more threads. Your results may look quite different, and that is worth discussing.

  • Many OpenMP implementations keep a pool of idle threads rather than creating new ones for each region. That can shrink the gap between the versions.
  • Each phase does a small amount of work and ends with a barrier. If the threads spend as long waiting and coordinating as they do swapping, more threads may not help, and they can even make the program slower.

Try a larger list, such as ./omp_odd_even2 4 50000, to see whether the picture changes. Compare the same thread counts with ./omp_odd_even1. As always, trust your measurements over anyone’s expectation, including the book’s.

Experiment: remove the barrier

The clause nowait removes the implicit barrier at the end of a for directive. In omp_odd_even2.c, change both # pragma omp for lines to:

#       pragma omp for nowait

Predict: What can a fast thread do now that it could not do before? Compile it and run ./omp_odd_even2 4 20 several times. Look at the printed list as well as the Sorted line.

Threads no longer wait for each other between phases, so one thread can be several phases ahead of another. Pairs from different phases overlap, which makes this a data race. The list is often left out of order. A swap can also interrupt another swap, so values can even be lost or duplicated. The barrier is doing necessary work here. Restore the program when you finish.

Scheduling: who gets which iterations?

So far, we have mostly gotten OpenMP’s default division: roughly equal blocks of consecutive iterations. Assigning iterations to threads is called scheduling, and the schedule clause controls it on a parallel for or for directive (§5.7):

schedule(<type>, <chunksize>)

A chunk is a group of consecutive iterations. The chunk size is optional.

Type How iterations are assigned
static Before the loop starts. Chunks go to the threads in round-robin order. Without a chunk size, each thread gets one block of about equal size.
dynamic While the loop runs. A thread that finishes a chunk asks for another. The default chunk size is 1.
guided Like dynamic, but the chunks start large and shrink as the work runs out.
runtime Read the schedule from the OMP_SCHEDULE environment variable when the program runs.

See the schedule

The heart of omp_schedule_map.c records each iteration’s thread. schedule(runtime) lets us try many schedules without recompiling. Every fourth iteration deliberately takes longer.

#   pragma omp parallel for num_threads(thread_count) schedule(runtime)
for (int i = 0; i < N; i++) {
    owner[i] = omp_get_thread_num();
    usleep(i % 4 == 0 ? 5000 : 1000);  /* Every fourth iteration takes longer */
}

Writing owner[i] is safe, because each iteration writes a different element. usleep pauses a thread for a number of microseconds, which gives us uneven iterations without much computing.

Predict: With 12 iterations and 3 threads, write down the thread for each iteration under static,1, static,2, and static,4. Then check:

gcc -Wall -O2 -fopenmp -o omp_schedule_map omp_schedule_map.c
OMP_SCHEDULE="static,1" ./omp_schedule_map 3
OMP_SCHEDULE="static,2" ./omp_schedule_map 3
OMP_SCHEDULE="static,4" ./omp_schedule_map 3

Putting OMP_SCHEDULE="…" before a command sets that variable for that one command. Now run these several times each:

OMP_SCHEDULE="static" ./omp_schedule_map 3
OMP_SCHEDULE="dynamic" ./omp_schedule_map 3
OMP_SCHEDULE="dynamic,2" ./omp_schedule_map 3
OMP_SCHEDULE="guided" ./omp_schedule_map 3

The static maps should be the same on every run. Do the dynamic and guided maps change? Which threads get the iterations right after a slow one?

ImportantSet OMP_SCHEDULE on every run

If OMP_SCHEDULE is not set, a schedule(runtime) loop uses a schedule chosen by the implementation. It is not necessarily the same as leaving out the schedule clause. To see a block division, set OMP_SCHEDULE="static".

When the iterations are not equal

Here is the book’s example, in omp_sin_sum.c. The function f(i) calls sin about i times, so iteration i costs about i units of work:

double f(long i) {
    long first = i * (i + 1) / 2;
    long last = first + i;
    double result = 0.0;

    for (long j = first; j <= last; j++) {
        result += sin(j);
    }
    return result;
}

Predict: With a block schedule and two threads, thread 0 gets the cheap first half of the loop and thread 1 gets the expensive second half. What fraction of the work does thread 1 do? What is the best possible speedup? Try the same reasoning for four threads.

The work up to iteration \(x\) grows like \(x^2\). So the first half of the iterations holds only \((1/2)^2 = 1/4\) of the work, and thread 1 has the other \(3/4\). The loop finishes when thread 1 does, so the best speedup is \(1 / (3/4) \approx 1.33\). That is exactly the speedup in the book.

With four threads, the blocks hold \(1/16\), \(3/16\), \(5/16\), and \(7/16\) of the work. The best speedup is \(16/7 \approx 2.29\), even with four cores available.

To see the imbalance, the program records when each thread finishes its share:

#   pragma omp parallel num_threads(thread_count) \
        default(none) shared(n, finished, start) reduction(+: sum)
{
#   pragma omp for schedule(runtime) nowait
    for (long i = 0; i <= n; i++) {
        sum += f(i);
    }
    finished[omp_get_thread_num()] = omp_get_wtime() - start;
}

Here nowait is safe and useful. Nothing after the loop depends on the other threads’ work, and it lets each thread record its own finishing time, instead of all of them waiting at a barrier and recording about the same time. The parallel region still ends with its own barrier.

Compile with -lm, because the program uses sin:

gcc -Wall -O2 -fopenmp -o omp_sin_sum omp_sin_sum.c -lm
OMP_SCHEDULE="static" ./omp_sin_sum 1
for s in static static,1 dynamic dynamic,100 guided; do OMP_SCHEDULE="$s" ./omp_sin_sum 4; done

Every run should print a sum of 1.888923. Record what you see for four threads:

Schedule Elapsed time (s) Speedup over 1 thread First and last thread finish times (s)
static
static,1
dynamic
dynamic,100
guided

Discuss: With static, how long do the early threads sit idle? How do the finish times change with the other schedules?

Scheduling is not free

A dynamic schedule makes threads coordinate each time they need more iterations. That overhead hardly matters when each iteration is expensive. It matters a lot when iterations are cheap.

Try it: Open your omp_trap_for.c from Module 13. Change n to 50000000, add schedule(runtime) to the directive, and recompile. Each trapezoid costs almost nothing, and all of them cost the same.

OMP_SCHEDULE="static" ./omp_trap_for 4
OMP_SCHEDULE="dynamic" ./omp_trap_for 4
OMP_SCHEDULE="dynamic,1000" ./omp_trap_for 4
OMP_SCHEDULE="guided" ./omp_trap_for 4

How much slower is plain dynamic, with its chunk size of 1? What does a chunk size of 1000 change? Restore n and the directive when you finish.

Which schedule should you use?

Section 5.7.5 suggests this order of thinking:

  1. If the default performs well, stop. A schedule clause adds overhead, generally least for static and most for guided.
  2. If iterations cost about the same, the default is probably best.
  3. If the cost rises or falls steadily, try static with a small chunk size.
  4. If you cannot predict the cost of an iteration, use schedule(runtime) and experiment with OMP_SCHEDULE.

Practice: choose a schedule

What would you try first, and why?

  • A. Add two arrays element by element.
  • B. A loop in which iteration i fills in row i of a triangular table, which has i + 1 entries.
  • C. Test each integer for primality, as in Project 2, stopping at the first divisor found.
  • D. One billion very cheap, identical iterations, with schedule(dynamic) suggested by a classmate.
  • A: The default. Every iteration costs the same.
  • B: static with a small chunk size, such as static,1. The cost rises steadily, like our sine sum.
  • C: dynamic or guided with a moderate chunk size. Even numbers finish immediately, while primes need the most trial divisions, so the cost is uneven and hard to predict. A chunk size above 1 reduces overhead. Experiment.
  • D: Not dynamic with chunk size 1. The threads would spend their time requesting iterations, as you saw with the trapezoid loop. Use the default.

Check your understanding

  1. What is the difference between # pragma omp parallel for and # pragma omp for?
  2. In omp_odd_even2.c, how many times does each thread run the outer phase loop?
  3. Why can the comparisons in one phase run at the same time, when the phases themselves cannot?
  4. What does nowait do? Why does it break odd-even sort but not omp_sin_sum.c?
  5. With 12 iterations and 3 threads, which iterations does thread 1 get under schedule(static, 2)?
  6. Why can a block schedule give four threads a speedup of only about 2.29 in the sine sum?
  7. Why not use schedule(dynamic) on every loop?
  1. parallel for starts a new team and divides the loop among it. for divides the loop among the threads of the team that already exists.
  2. Every thread runs all n passes. Only the inner loops’ iterations are shared.
  3. Pairs in one phase do not overlap, but a later phase compares elements that an earlier phase may have swapped.
  4. It removes the implicit barrier at the end of a for directive. Odd-even sort needs that barrier to keep the phases in order. In omp_sin_sum.c, nothing after the loop depends on the other threads’ results until the region ends, and the region has its own barrier.
  5. Iterations 2, 3, 8, and 9.
  6. The last thread has \(7/16\) of the work, and the loop cannot finish before it does. The other threads sit idle at the end.
  7. It adds overhead every time a thread requests more iterations. With cheap, equal iterations, that overhead can far exceed the work itself.
Back to top