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:
| block | total | five runs | min | median |
|---|---|---|---|---|
| reduction | 12566370.364359 | 17, 16, 28, 30, 16 | 16 | 17 |
| critical | 12566370.364359 | 743, 1173, 997, 749, 777 | 743 | 777 |
| no clause | wrong every time | 17, 21, 27, 16, 17 | 16 | 17 |
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:
| policy | five runs | min | median |
|---|---|---|---|
| schedule(static) | 186, 181, 182, 181, 184 | 181 | 182 |
| schedule(dynamic, 1) | 127, 508, 136, 104, 105 | 104 | 127 |
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
- 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?
- Run the no-reduction loop with one thread. Is the answer right, and what does that say about testing on one thread?
- Change the schedule of the uneven loop to schedule(dynamic, 500) and time it. Which policy wins now?
- 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.
-
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.
-
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.
-
What does the loop with no clause produce?
Answer
A different wrong total on every run
The lost increments depend on the interleaving.
-
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.
-
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.
-
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.
-
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.
-
Why keep the serial result?
Answer
It is the answer the parallel version has to reproduce
Correctness first, then the speed.
-
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.
-
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