The idea: one pragma splits a loop among threads
OpenMP is the standard way to run a C, C++ or Fortran loop on several cores of one machine. You add one line above the loop, #pragma omp parallel for, and compile with -fopenmp. At the pragma the running thread, the master, forks a team of threads. The iterations of the loop are split among the team. At the end of the loop there is an implicit barrier: every thread waits until all are done. Then the team joins and only the master goes on.
The canvas runs a loop of 16 iterations on 4 threads. The body is sum += a[i] with a[i] = i, so the right answer is 0 + 1 + … + 15 = 120. Each iteration takes a fixed number of time units, its cost, shown under it in the strip. With growing costs (1, 1, 2, 2, …, 8, 8) the late iterations are slow, like a loop over a triangle of a matrix. The costs add up to 72, so 4 perfectly balanced threads would finish at 72 / 4 = 18.
The chart below the strip has one row per thread and time going right. A coloured bar is a chunk of iterations that the thread runs back to back. A grey bar is time spent waiting at the barrier. The makespan is when the last thread finishes; idle is the waiting time of all threads added up, 4 × makespan − 72.
The schedule clause
Which thread runs which iterations is set by schedule(kind[, chunk]). A chunk is a run of consecutive iterations that one thread takes as a unit.
| Clause | Who decides | Chunks for 16 iterations, 4 threads |
|---|---|---|
schedule(static) | fixed before the loop starts | 4 blocks of about equal size: 0–3, 4–7, 8–11, 12–15 |
schedule(static, c) | fixed before the loop starts | chunks of c dealt round robin: chunk k goes to thread k mod 4 |
schedule(dynamic, c) | at run time, by a shared counter | a free thread takes the next c iterations (c = 1 if left out) |
schedule(guided, c) | at run time, by a shared counter | like dynamic, but the chunk is about remaining / threads, never below c |
With no schedule clause the choice is up to the implementation; GCC and most others use static. schedule(runtime) reads the choice from the environment variable OMP_SCHEDULE, so you can try schedules without recompiling.
Load imbalance: idle time at the barrier
schedule(static) cuts the loop into 4 equal blocks of iterations, but not of work. With growing costs T0 gets 1 + 1 + 2 + 2 = 6 units and T3 gets 7 + 7 + 8 + 8 = 30. T0 then waits 24 units at the barrier. The loop takes 30 instead of 18, idle is 48, and the efficiency is 72 / (4 × 30) = 60% (Demo 1).
schedule(static, 1) deals the iterations like cards: T0 gets 0, 4, 8, 12, T1 gets 1, 5, 9, 13, and so on. Every thread now gets some cheap and some heavy iterations: 16, 16, 20 and 20 units. The makespan drops to 20 and idle to 8, with no extra cost at run time, because the split is still fixed in advance (Demo 2). Small static chunks work well when the cost changes smoothly with i.
dynamic: take the next chunk when you are free
With schedule(dynamic, 1) the runtime keeps a shared counter, shown as next in shared memory. A thread that is free does an atomic fetch-and-add on it and runs the iterations it got. Nobody needs to know the costs in advance: a thread that drew a cheap iteration simply comes back sooner. On the growing loop the result is the same 20 as static, 1, but it took 16 trips to the shared counter instead of none (Demo 3). Each trip is an atomic operation on a cache line that all cores share, which costs time on a real machine.
A bigger chunk means fewer trips but coarser balance. schedule(dynamic, 4) makes only 4 trips, and on this loop it gives exactly the blocks of static: makespan 30 again. Try it with the TRY IT controls.
Dynamic wins when the costs do not follow a pattern you can plan for. With the heavy first costs (8, 8, 7, 7, …, 1, 1), the cheap iterations at the end fill the gaps: all four threads finish at exactly 18, with no idle time (Demo 5). schedule(static, 1) gives 20 on the same loop.
guided: big chunks first, small ones at the end
schedule(guided) tries to get the balance of dynamic with fewer trips. Each chunk is about the remaining iterations divided by the number of threads, and never smaller than the chunk argument. On 16 iterations the chunks are ⌈16/4⌉ = 4, then ⌈12/4⌉ = 3, 3, 2, and then 1, 1, 1, 1: 8 trips instead of 16. On the growing loop the makespan is 21, almost as good as dynamic (Demo 4).
Guided assumes the early iterations are no heavier than the late ones. With heavy iterations first, the first and biggest chunk, 0–3, costs 8 + 8 + 7 + 7 = 30 units, and T0 alone sets the makespan to 30 while the others finish by 17 (Demo 6). The exact chunk sizes of guided are up to the implementation; the page uses ⌈remaining / threads⌉, as GCC's libgomp does.
| Run | Makespan | Idle | Counter trips |
|---|---|---|---|
| growing, static | 30 | 48 | 0 |
| growing, static, 1 | 20 | 8 | 0 |
| growing, dynamic, 1 | 20 | 8 | 16 |
| growing, dynamic, 4 | 30 | 48 | 4 |
| growing, guided | 21 | 12 | 8 |
| heavy first, dynamic, 1 | 18 | 0 | 16 |
| heavy first, guided | 30 | 48 | 8 |
Shared, private and reduction
Inside the parallel loop every variable is either shared (one copy that all threads read and write) or private (each thread has its own copy). The loop index i is private automatically. A variable declared before the pragma, like sum, is shared unless a clause says otherwise.
So without a clause, all four threads do sum += a[i] on the same variable. That is a read, an add and a write, and two threads can read the same old value before either writes. On the page, updates in the same time unit always collide. With static, 1 on growing costs the iterations end in pairs, so 8 updates are lost and the sum is 64 instead of 120 (Demo 7). On a real machine collisions happen only sometimes, so the answer changes from run to run. Race Condition shows the interleaving step by step.
reduction(+:sum) fixes it. Each thread gets a private sum that starts at 0, adds its own iterations into it, and at the end of the loop OpenMP adds the private copies into the shared one: 24 + 28 + 32 + 36 = 120. That is how Demo 2 ends: the same loop and schedule as Demo 7, with the clause. There is no lock inside the loop. #pragma omp atomic on the update would also give 120, but then every one of the 16 updates waits for the shared cache line.
| Clause | Meaning |
|---|---|
shared(x) | one x for the whole team (the default for variables declared outside) |
private(x) | each thread has its own x, not initialized |
firstprivate(x) | private, initialized with the value x had before the loop |
lastprivate(x) | private, and after the loop x has the value from the last iteration |
reduction(op:x) | private copies starting at the identity of op (0 for +), combined with op at the end |
Writing default(none) on the pragma forces you to name every variable in one of these clauses, which catches forgotten shared variables at compile time.
Choosing a schedule
- Every iteration costs the same:
static. No run-time cost, and each thread touches one contiguous block, which is good for caches. - Cost changes smoothly with i (triangular loops):
staticwith a small chunk. - Cost is unpredictable (search, adaptive meshes, Mandelbrot rows):
dynamicwith a chunk big enough that the counter trips are cheap compared with the work. - Unpredictable cost and many iterations:
guided, unless the heavy work is at the start.
The serial code before and after the loop, and the idle time, limit the speedup; see Amdahl's and Gustafson's laws. Recursive work that does not fit a loop is better served by tasks and work stealing, as in Java's ForkJoinPool. OpenMP threads share memory on one machine; across machines programs use message passing, as in MPI, where MPI_Reduce plays the role of the reduction clause. The cores themselves are on Parallel Hardware.
See also Parallel Prefix Sum, a parallel loop whose rounds depend on each other, counted as work and span.
What the page leaves out
The page has a fixed team of 4 threads, whole time units and no cost for forking, for a counter trip or for the barrier. Real loops have thousands of iterations, so chunks are much bigger than 1. Ties between free threads go to the lower thread id; in real OpenMP whoever wins the atomic goes first. Left out: schedule(auto), the monotonic and nonmonotonic modifiers, nowait (no barrier at the end of the loop), collapse, ordered, critical, OpenMP tasks and simd, nested teams, thread affinity (OMP_PROC_BIND), false sharing between private data on one cache line, and NUMA placement of memory. The toy race rule (updates in the same time unit always collide) is much more regular than real hardware.