OpenMP: reductions and scheduling

A loop that adds to one variable is the case a parallel do cannot handle by itself: every thread writes the same memory and the last write wins. Fortran's answer is the reduction clause, OpenMP's general answer is the critical section, and the answer that costs nothing and is wrong is no clause at all. This lesson runs all three on the same loop, compares the totals and the clocks, and then measures the two scheduling policies on a loop whose iterations cost very different amounts.

REDUCTION(+:total)

reduction(+:s) tells the compiler that every thread may keep a private copy of s, adds into it, and that the copies are combined at the end. The clause is a promise about the operation, not a lock: the threads never touch the same memory during the loop, and the combine at the end is a few additions per thread whatever the loop length.

The file red.f90:

program ompred use, intrinsic :: iso_fortran_env, only: real64 use omp_lib implicit none integer, parameter :: n = 16000000 real(real64) :: s, x integer :: i, k, rate ! 1. reduction s = 0.0_real64 call system_clock(i, rate) !$omp parallel do reduction(+:s) private(x) do i = 1, n x = real(i, real64) / real(n, real64) s = s + 1.0_real64 / (1.0_real64 + x * x) end do !$omp end parallel do call system_clock(k, rate) print '(a,f20.6,a,f8.1,a)', 'reduction = ', s, ' ', real(k - i) / real(rate) * 1000.0, ' ms' ! 2. critical s = 0.0_real64 call system_clock(i, rate) !$omp parallel do private(x) do i = 1, n x = real(i, real64) / real(n, real64) !$omp critical s = s + 1.0_real64 / (1.0_real64 + x * x) !$omp end critical end do !$omp end parallel do call system_clock(k, rate) print '(a,f20.6,a,f8.1,a)', 'critical = ', s, ' ', real(k - i) / real(rate) * 1000.0, ' ms' ! 3. no protection: a race s = 0.0_real64 call system_clock(i, rate) !$omp parallel do private(x) do i = 1, n x = real(i, real64) / real(n, real64) s = s + 1.0_real64 / (1.0_real64 + x * x) end do !$omp end parallel do call system_clock(k, rate) print '(a,f20.6,a,f8.1,a)', 'no reduction = ', s, ' ', real(k - i) / real(rate) * 1000.0, ' ms' print '(a,i0)', 'threads = ', omp_get_max_threads() end program ompred

gfortran -Wall -Wextra -std=f2018 -O2 -fopenmp red.f90 -o red
OMP_NUM_THREADS=4 ./red

reduction = 12566370.364359 17.0 ms
critical = 12566370.364359 743.0 ms
no reduction = 3919658.580618 17.0 ms
threads = 4

CRITICAL and its cost

A critical section is a lock: one thread at a time may run the statements inside it. It is the general tool, and it gives the right answer for any operation, not only an addition. Here it wraps the single statement that adds to s, and the total is the same as the reduction's to the last printed digit.

It is 743 milliseconds against 17, a factor of more than forty. The reason is in the pattern: the critical section is entered sixteen million times, and every entry is a lock, an unlock and a stalled thread. A critical section around a whole block of work, entered once per thread or once per thousand iterations, is a different thing and a reasonable tool; one around an addition is a way to make a parallel program slower than the serial one.

The race without either

The third block is the same loop with no clause at all. s is shared, every thread reads it and writes it, and the increments are lost whenever two threads interleave. The total is 3.9 million instead of 12.6 million, and it is a different number on every run: other runs of this same binary printed 2270352.803667 and 3498703.063395.

Nothing about the program looks wrong, the compiler says nothing, and the loop is the fastest of the three. A race is not a crash and not a warning; it is a wrong answer whose value depends on timing, and it is the reason a parallel program needs a test on the result and not only on the output format.

The measured table

Machine: Intel(R) Core(TM) i3-6006U CPU @ 2.00GHz with 4 logical CPUs (nproc), two physical cores with hyper-threading, Alpine Linux 3.24.3, GNU Fortran (Alpine 15.2.0) 15.2.0, -O2 -fopenmp, four threads. Five runs of each block, in milliseconds:

blocktotalfive runsminmedian
reduction12566370.36435917, 16, 28, 30, 161617
critical12566370.364359743, 1173, 997, 749, 777743777
no clausewrong every time17, 21, 27, 16, 171617

The critical totals differ in the last digit between runs, 12566370.364359 and 12566370.364361: a sum of doubles depends on the order of the additions, and a lock does not fix the order. That is expected and harmless at this precision, and it is the reason a test of such a sum uses a relative tolerance and not equality.

SCHEDULE(STATIC) and DYNAMIC

The default distribution gives each thread a contiguous block of iterations, which is perfect when every iteration costs the same and terrible when they do not. The second program makes the cost grow with the index: iteration i does i additions, so the last block is the expensive one and the thread that gets it finishes long after the others.

program ompsched use, intrinsic :: iso_fortran_env, only: real64 use omp_lib implicit none integer, parameter :: n = 20000 real(real64) :: s, x integer :: i, k, t(2), rate s = 0.0_real64 call system_clock(t(1), rate) !$omp parallel do reduction(+:s) schedule(static) private(x, k) do i = 1, n x = 0.0_real64 do k = 1, i x = x + 1.0_real64 / real(k, real64) end do s = s + x end do !$omp end parallel do call system_clock(t(2), rate) print '(a,f18.6,a,f8.1,a)', 'static = ', s, ' ', real(t(2) - t(1)) / real(rate) * 1000.0, ' ms' s = 0.0_real64 call system_clock(t(1), rate) !$omp parallel do reduction(+:s) schedule(dynamic, 1) private(x, k) do i = 1, n x = 0.0_real64 do k = 1, i x = x + 1.0_real64 / real(k, real64) end do s = s + x end do !$omp end parallel do call system_clock(t(2), rate) print '(a,f18.6,a,f8.1,a)', 'dynamic, 1 = ', s, ' ', real(t(2) - t(1)) / real(rate) * 1000.0, ' ms' end program ompsched

gfortran -Wall -Wextra -std=f2018 -O2 -fopenmp sched.f90 -o sched
OMP_NUM_THREADS=4 ./sched

static = 189625.045073 181.0 ms
dynamic, 1 = 189625.045073 104.0 ms

The measured schedule table

Five runs of each policy on the same machine and flags:

policyfive runsminmedian
schedule(static)186, 181, 182, 181, 184181182
schedule(dynamic, 1)127, 508, 136, 104, 105104127

Dynamic scheduling is faster here by about 1.4 times on the median and 1.7 on the minimum, because it hands out iterations one at a time and no thread is left with the heaviest block. The 508 in the dynamic row is the shared machine, not the policy: a container competes with its host, and a single number from such a run means nothing.

The cost of dynamic is a lock per iteration: the loop above has twenty thousand iterations and each one is expensive, which is why the hand-out is cheap relative to the work. A dynamic schedule on a loop whose body is one multiplication would lose to static, and the usual compromise is schedule(dynamic, chunk) with a chunk size picked from the cost of one iteration.

A symbol on two clauses

A variable cannot be private and a reduction at the same time, and the compiler says so at the directive:

program badred implicit none integer :: i real :: s s = 0.0 !$omp parallel do reduction(+:s) private(s) do i = 1, 100 s = s + real(i) end do !$omp end parallel do print *, s end program badred

gfortran -Wall -Wextra -std=f2018 -fopenmp badred.f90 -o badred

badred.f90:7:33:

7 | !$omp parallel do reduction(+:s) private(s)
| 1
Error: Symbol 's' present on multiple clauses at (1)

The message comes from the OpenMP front end rather than the Fortran one, which is why it talks about clauses rather than variables. A private copy cannot be combined at the end, because the whole point of private is that nothing outside sees it.

Rules for a parallel loop

Write the serial version first and keep its result as the answer to compare against. Decide for every variable whether it is private or reduced, and name it: a default of shared is what makes the race of this lesson. Prefer a reduction to a critical section, and a critical section to nothing. And measure on the machine the program will run on, because the speedup of the first table is a property of two cores with hyper-threading, not of the flag.

The other half is the test. A parallel program needs a check that its answer is still the serial answer, at every thread count you intend to run, and the check must be a tolerance and not equality. Everything else about OpenMP, the scheduling, the affinity, the number of threads, is tuning around that one requirement.

Exercises

  1. Put the critical section around a block of a thousand iterations instead of one. How much does the time fall, and is the answer still right?
  2. Run the no-reduction loop with one thread. Is the answer right, and what does that say about testing on one thread?
  3. Change the schedule of the uneven loop to schedule(dynamic, 500) and time it. Which policy wins now?
  4. Use reduction(max:biggest) on the same loop and print the maximum. Which clause name does Fortran use for a maximum?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does reduction(+:s) do?

    Answer

    Gives every thread a private copy and combines them at the end

    The threads never touch the same memory during the loop.

  2. Why is a critical section around one addition so slow?

    Answer

    It enters the lock once per iteration and serialises the loop

    Sixteen million lock and unlock pairs.

  3. What does the loop with no clause produce?

    Answer

    A different wrong total on every run

    The lost increments depend on the interleaving.

  4. Why does dynamic scheduling win on the uneven loop?

    Answer

    It hands out iterations one at a time, so no thread gets the heavy block

    Static gives contiguous blocks of very different cost.

  5. When does dynamic scheduling lose?

    Answer

    When an iteration is so cheap that the hand-out costs more than the work

    A chunk size is the usual compromise.

  6. Why do two runs of the critical version differ in the last digit?

    Answer

    The order of the additions differs, and floating-point addition is not associative

    A tolerance test is the right check.

  7. What does gfortran report for reduction(+:s) private(s)?

    Answer

    Error: symbol present on multiple clauses

    A private copy cannot be combined at the end.

  8. Why keep the serial result?

    Answer

    It is the answer the parallel version has to reproduce

    Correctness first, then the speed.

  9. Why does the no-clause race give a correct answer with one thread?

    Answer

    With one thread there is no interleaving to lose an increment

    Races need two threads to show.

  10. What is the right test for a parallel sum?

    Answer

    A relative tolerance against the serial result at several thread counts

    The order of the additions changes the last digits.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev