Skip to main content
Parallel Programming · lesson 2 of 8

Beginner

2

Intermediate

5

Advanced

1

Also part of Parallel Programming

2
Open the Parallel Programming page →
Parallel Programming beginner Lesson 2 of 8

OpenMP Scheduling: Static's Load Imbalance, Measured

Static scheduling hands out equal-sized, fixed chunks up front — great when every iteration costs the same, a real 30% slower when they don't. Dynamic scheduling fixes it, measured, not asserted.

By SkillByExample · Published

parallel-programming openmp scheduling load-balancing

Two schedules, identical total work, a real measured time difference — because one of them assumes every iteration costs the same, and the workload here doesn’t.

Static scheduling: fixed chunks, decided up front

// schedule_static.c
#include <stdio.h>
#include <omp.h>

int main() {
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for schedule(static)
        for (int i = 0; i < 8; i++) {
            printf("thread %d handles iteration %d\n", omp_get_thread_num(), i);
        }
    }
    return 0;
}
gcc -fopenmp -o schedule_static schedule_static.c
./schedule_static
thread 0 handles iteration 0
thread 0 handles iteration 1
thread 1 handles iteration 2
thread 1 handles iteration 3
thread 3 handles iteration 6
thread 3 handles iteration 7
thread 2 handles iteration 4
thread 2 handles iteration 5

8 iterations, 4 threads, 2 each — assigned in contiguous blocks (0-1, 2-3, 4-5, 6-7) purely by iteration index, before any iteration has actually run.

The bug: static scheduling on uneven work

// imbalance.c
#include <stdio.h>
#include <omp.h>
#include <unistd.h>

int main() {
    double start = omp_get_wtime();
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for schedule(static)
        for (int i = 0; i < 8; i++) {
            usleep(i * 100000);  // later iterations take longer
            printf("thread %d finished iteration %d\n", omp_get_thread_num(), i);
        }
    }
    printf("static schedule total time: %.2f s\n", omp_get_wtime() - start);
    return 0;
}
gcc -fopenmp -o imbalance imbalance.c
./imbalance
thread 0 finished iteration 0
thread 0 finished iteration 1
thread 1 finished iteration 2
thread 2 finished iteration 4
thread 1 finished iteration 3
thread 3 finished iteration 6
thread 2 finished iteration 5
thread 3 finished iteration 7
static schedule total time: 1.30 s

Thread 0 (iterations 0-1) finishes almost instantly; thread 3 (iterations 6-7, the two slowest) takes the full 1.3 seconds by itself. The other three threads sit idle waiting — total time is bounded by the slowest thread’s chunk, not the average across all four.

The fix: dynamic scheduling, measured

// balanced.c
#include <stdio.h>
#include <omp.h>
#include <unistd.h>

int main() {
    double start = omp_get_wtime();
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for schedule(dynamic, 1)
        for (int i = 0; i < 8; i++) {
            usleep(i * 100000);
            printf("thread %d finished iteration %d\n", omp_get_thread_num(), i);
        }
    }
    printf("dynamic schedule total time: %.2f s\n", omp_get_wtime() - start);
    return 0;
}
gcc -fopenmp -o balanced balanced.c
./balanced
thread 1 finished iteration 0
thread 3 finished iteration 1
thread 0 finished iteration 2
thread 2 finished iteration 3
thread 1 finished iteration 4
thread 3 finished iteration 5
thread 0 finished iteration 6
thread 2 finished iteration 7
dynamic schedule total time: 1.00 s

1.00s versus 1.30s — measured, not asserted, a real 23% improvement on identical work. schedule(dynamic, 1) hands out one iteration at a time to whichever thread finishes its current one first, so a thread that draws an early (cheap) iteration immediately grabs another instead of sitting idle while another thread works through a late (expensive) one.

Practice

1. Set an explicit chunk size on static scheduling and confirm it matches the default. 
#pragma omp for schedule(static, 2)
thread 0 handles iteration 0
thread 0 handles iteration 1
thread 1 handles iteration 2
thread 1 handles iteration 3
thread 3 handles iteration 6
thread 3 handles iteration 7
thread 2 handles iteration 4
thread 2 handles iteration 5

Identical to the unmodified schedule(static) result — with 8 iterations and 4 threads, the implicit default chunk size is already 8/4 = 2, so spelling it out explicitly changes nothing here. It matters once the iteration count doesn’t divide evenly by the thread count.

2. Try requesting more threads via the environment variable and see why nothing changes. 
OMP_NUM_THREADS=16 ./schedule_static
thread 0 handles iteration 0
thread 0 handles iteration 1
thread 3 handles iteration 6
thread 3 handles iteration 7
thread 1 handles iteration 2
thread 1 handles iteration 3
thread 2 handles iteration 4
thread 2 handles iteration 5

Still exactly 4 threads, same 2-iteration chunks as before — schedule_static.c hardcodes num_threads(4) in its pragma, which overrides OMP_NUM_THREADS the same way it did in the previous lesson. The environment variable only takes effect when the source code doesn’t already specify a thread count.

3. Increase the dynamic chunk size to 4 and measure what happens to the imbalance. 
#pragma omp for schedule(dynamic, 4)
thread 1 finished iteration 0
thread 1 finished iteration 1
thread 1 finished iteration 2
thread 0 finished iteration 4
thread 1 finished iteration 3
thread 0 finished iteration 5
thread 0 finished iteration 6
thread 0 finished iteration 7
dynamic(4) schedule total time: 2.20 s

Worse than the original static version’s 1.30s — with chunk size 4, 8 iterations only produce two chunks total (0-3 and 4-7), so only 2 of the 4 threads get any work at all, and whichever one draws the second chunk (4-7, the four slowest iterations combined) runs all four sequentially by itself. A chunk size too large throws away dynamic scheduling’s whole advantage — fine-grained rebalancing — while still paying its coordination overhead. 1.30s (static) < 2.20s (dynamic, chunk 4) < the 1.00s this lesson’s chunk size of 1 actually achieved: chunk size is a real tuning parameter, not a detail to default without measuring.

Next: race conditions — the sum that comes out wrong, and the reduction clause that fixes it.

Frequently Asked Questions

What does schedule(static) actually do?
It divides the loop's iteration range into contiguous chunks up front — before any work runs — and assigns one chunk per thread. With 8 iterations and 4 threads, that's iterations 0-1, 2-3, 4-5, 6-7, one pair per thread, decided entirely by iteration count with no knowledge of how long each iteration will actually take.
Why did static scheduling finish slower than dynamic on the same work?
The simulated work in this lesson gets longer as the iteration index increases, so the thread assigned the last chunk (iterations 6-7) ends up with by far the most total work — and every other thread finishes early and sits idle waiting for it. Total time is bounded by the slowest thread, not the average, so an uneven static split can make the whole parallel region only as fast as its worst-assigned thread.
How does dynamic scheduling avoid that imbalance?
Instead of committing to fixed assignments up front, dynamic scheduling hands out one chunk at a time to whichever thread finishes its current chunk first — so a thread that gets an easy, fast iteration immediately picks up more work instead of sitting idle while another thread struggles through a slow one. The tradeoff is more scheduling overhead per chunk, which matters when chunks are numerous and cheap rather than few and expensive.
What does the chunk size in schedule(dynamic, 1) control?
How many iterations are handed out per request — 1 means a thread grabs a single iteration at a time before asking for the next, which gives the finest-grained load balancing at the cost of the most scheduling overhead. A larger chunk size trades some balance for less overhead, useful when individual iterations are cheap enough that per-iteration scheduling would dominate the runtime.
When is static scheduling actually the right choice?
When every iteration costs roughly the same amount of work — a plain elementwise array operation, for instance. Static has the least scheduling overhead of any option because the assignment is computed once, up front, with no runtime coordination between threads at all; that overhead saving only pays off when there's no load imbalance for it to make worse.