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.

Time goes left to right. The master thread T0 runs alone, then forks at the pragma into four threads T0 to T3. Each thread runs a different set of loop iterations, for different lengths of time. Threads that finish early wait, shown in grey, until the barrier line. After the barrier only T0 continues.
Fork at the pragma, split the iterations, wait at the barrier, join: the loop lasts as long as its busiest thread.

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.

ClauseWho decidesChunks for 16 iterations, 4 threads
schedule(static)fixed before the loop starts4 blocks of about equal size: 0–3, 4–7, 8–11, 12–15
schedule(static, c)fixed before the loop startschunks of c dealt round robin: chunk k goes to thread k mod 4
schedule(dynamic, c)at run time, by a shared countera free thread takes the next c iterations (c = 1 if left out)
schedule(guided, c)at run time, by a shared counterlike 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.

Two Gantt charts for the growing-cost loop on 4 threads. schedule(static): T0 busy 6, T1 14, T2 22, T3 30, with grey idle bars of 24, 16 and 8; makespan 30. schedule(static, 1): T0 and T1 busy 16, T2 and T3 busy 20; small idle bars of 4; makespan 20. A dashed line marks the ideal 18.
Same loop, same 72 units of work: equal blocks finish at 30, round-robin chunks of 1 at 20 (ideal 18).

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.

RunMakespanIdleCounter trips
growing, static30480
growing, static, 12080
growing, dynamic, 120816
growing, dynamic, 430484
growing, guided21128
heavy first, dynamic, 118016
heavy first, guided30488

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.

Left, shared sum: T0 and T1 both read sum = 0, T0 writes 0 and T1 writes 1, so T0's update is lost; the final sum is 64. Right, reduction: each of T0 to T3 has a private sum, 24, 28, 32 and 36, which are added into the shared sum at the end: 120.
A shared sum loses updates when two threads write at once; reduction gives each thread its own sum and adds them once at the end.
ClauseMeaning
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): static with a small chunk.
  • Cost is unpredictable (search, adaptive meshes, Mandelbrot rows): dynamic with 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.

On the mind map

Open the Computer Architecture mind mapComputerArchitectureAbstraction and numbers: layers and bit patternsAbstraction and numbersCombinational logic: output depends only on inputsCombinational logicSequential logic: state held by a clockSequential logicMIPS software: how C becomes machine wordsMIPS softwareThe processor: datapath plus controlThe processorPipelines and parallelism: more instructions at oncePipelines and parallelismMemory and I/O: small fast near, big slow farMemory and I/OMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches splitOpen the Computer Architecture mind mapComputer Architecturemore instructions at oncePipelines and parallelismMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches split
This page on the Computer Architecture mind map · 42 pages in 7 branches · open it to see the whole map and test yourself in recall mode.