The parallel for Directive and Loop Scheduling

While the basic #pragma omp parallel directive requires threads to manually partition work, OpenMP provides a specialized worksharing construct for loops: #pragma omp parallel for.

When applied to a for loop, the compiler and runtime system automatically divide the loop iterations among the threads in the team.

5.7 The `parallel for` Worksharing Directive

Consider the serial trapezoidal rule loop:

h = (b - a) / n;
approx = (f(a) + f(b)) / 2.0;

#pragma omp parallel for num_threads(thread_count) \
    reduction(+: approx)
for (i = 1; i <= n - 1; i++) {
    approx += f(a + i * h);
}
approx = h * approx;

Differences Between `parallel` and `parallel for`

#pragma omp parallel: Spawns a team of threads where every thread executes the exact same block of code. Work partitioning must be coded explicitly by the programmer using my_rank.
#pragma omp parallel for: Spawns a team of threads and automatically distributes the loop iterations among the threads. By default, most systems assign contiguous blocks of iterations (e.g., the first $n / p$ iterations go to Thread 0, the next to Thread 1, etc.).

Automatic Loop Index Scoping

Inside a parallel for construct:

The loop control variable (i) is automatically private to each thread. Each thread maintains its own private counter to prevent race conditions during loop increments (i++).
Other variables declared before the directive default to shared (unless modified by clauses like reduction or private).

5.8 Restrictions: Canonical Loop Forms

OpenMP cannot parallelize arbitrary loops. The number of iterations must be determinable by the runtime prior to executing the loop. Consequently, OpenMP only parallelizes for loops in canonical form:

Table 5.2: Canonical Form for Parallelizable `for` Loops

Loop Element	Legal Syntax and Expressions
Initialization	`index = start;`
Test Condition	`index < end;` • `index <= end;` • `index >= end;` • `index > end;`
Increment	`index++` • `++index` • `index--` • `--index` • `index += incr` • `index -= incr`

Key Restrictions:

The index variable must have integer or pointer type (floating-point indices are illegal).
The expressions start, end, and incr must not change during loop execution.
The index variable may only be modified by the loop’s increment expression.
Single Exit Requirement: Jumps into or out of the loop body via break, return, or goto are prohibited because they create multiple exit points. Calls to exit() are the only allowable early termination.

/* COMPILER ERROR: Invalid exit from structured block */
#pragma omp parallel for num_threads(thread_count)
for (i = 0; i < n; i++) {
    if (A[i] == key) return i; /* ILLEGAL: gcc rejects this */
}

5.9 Data Dependences and Loop-Carried Dependences

Even if a loop compiles without errors, it may yield incorrect results if it contains data dependences.

Consider calculating the Fibonacci sequence:

fibo[0] = fibo[1] = 1;
#pragma omp parallel for num_threads(thread_count)
for (i = 2; i < n; i++) {
    fibo[i] = fibo[i - 1] + fibo[i - 2]; /* LOOP-CARRIED DEPENDENCE */
}

When run with multiple threads, this produces incorrect results such as 1 1 2 3 5 8 0 0 0 0. Iteration $i = 6$ requires fibo[5] and fibo[4], which are calculated by another thread. If the second thread runs before the first thread computes those elements, it reads uninitialized memory.

Intra-Iteration vs. Loop-Carried Dependences

Intra-Iteration Dependence (Safe):

#pragma omp parallel for
for (i = 0; i < n; i++) {
    x[i] = a + i * h;
    y[i] = exp(x[i]); /* Safe: depends only on statement within iteration i */
}

Loop-Carried Dependence (Hazardous): An iteration reads or writes a variable updated in a different iteration. Loops with loop-carried dependences cannot be directly parallelized with parallel for.

5.10 Case Study: Estimating $\pi$ and Variable Scoping

Approximating $\pi$ via the Leibniz series:

\pi = 4 \sum_{k=0}^{\infty} \frac{(-1)^k}{2k + 1} = 4 \left( 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \dots \right)

Sequential code:

double factor = 1.0;
double sum = 0.0;
for (k = 0; k < n; k++) {
    sum += factor / (2 * k + 1);
    factor = -factor; /* Loop-carried dependence on factor! */
}
pi_approx = 4.0 * sum;

Step 1: Eliminating the Loop-Carried Dependence

We observe that in iteration $k$ , the value of factor is simply $(-1)^k$ :

\text{factor} = \begin{cases} +1.0 & \text{if } k \text{ is even} \\ -1.0 & \text{if } k \text{ is odd} \end{cases}

factor = (k % 2 == 0) ? 1.0 : -1.0;
sum += factor / (2 * k + 1);

Step 2: Ensuring Private Scope for `factor`

Because factor was declared before the loop, it defaults to shared scope. If Thread 0 calculates factor = 1.0 and Thread 1 overwrites it with -1.0 before Thread 0 updates sum, the result is corrupted.

We must make factor private using the private clause:

double sum = 0.0;
double factor;

#pragma omp parallel for num_threads(thread_count) \
    reduction(+: sum) private(factor)
for (k = 0; k < n; k++) {
    factor = (k % 2 == 0) ? 1.0 : -1.0;
    sum += factor / (2 * k + 1);
}

5.10.1 Scoping Discipline: The `default(none)` Clause

To eliminate accidental race conditions caused by implicit scoping, best practice dictates using default(none):

double sum = 0.0;

#pragma omp parallel for num_threads(thread_count) \
    default(none) reduction(+: sum) private(k, factor) shared(n)
for (k = 0; k < n; k++) {
    factor = (k % 2 == 0) ? 1.0 : -1.0;
    sum += factor / (2 * k + 1);
}

With default(none), the compiler generates a build error if any variable declared outside the construct lacks an explicit scoping clause (shared, private, or reduction).

5.11 Loop Scheduling and Load Balancing

By default, OpenMP partitions $n$ iterations into equal, contiguous blocks of size $n / \text{thread\_count}$ .

While optimal when all iterations require identical CPU time, block partitioning causes severe load imbalance if iteration execution times vary:

/* Iteration workload increases linearly with i */
for (i = 0; i <= n; i++) {
    sum += f(i); /* where f(i) does i iterations of work */
}

Under block partitioning, Thread $p-1$ does substantially more work than Thread 0, leaving earlier threads idle while the last thread struggles to finish.

In an empirical benchmark with $n = 10,000$ on 2 threads:

Default block schedule: Runtime $= 2.76\,\text{s}$ (Speedup $= 1.33\times$ )
Cyclic schedule: Runtime $= 1.84\,\text{s}$ (Speedup $= 1.99\times$ , near linear!)

5.11.1 The `schedule` Clause

\text{Syntax:} \quad \text{schedule}(<\text{type}> [, <\text{chunksize}>])

flowchart TD
  subgraph SchedTypes["Figure 5.5: OpenMP Scheduling Types (4 threads, 32 iterations)"]
      direction TB
      subgraph StaticDefault["schedule(static) - Default Block"]
          T0_S["Thread 0: Iterations 0-7"]
          T1_S["Thread 1: Iterations 8-15"]
          T2_S["Thread 2: Iterations 16-23"]
          T3_S["Thread 3: Iterations 24-31"]
      end
      subgraph StaticChunk["schedule(static, 2) - Cyclic Blocks"]
          T0_C["Thread 0: 0-1, 8-9, 16-17, 24-25"]
          T1_C["Thread 1: 2-3, 10-11, 18-19, 26-27"]
          T2_C["Thread 2: 4-5, 12-13, 20-21, 28-29"]
          T3_C["Thread 3: 6-7, 14-15, 22-23, 30-31"]
      end
      subgraph Dynamic["schedule(dynamic, 2) - Work Queue"]
          D["Chunks of size 2 assigned on first-come, first-served basis"]
      end
      subgraph Guided["schedule(guided) - Decreasing Chunks"]
          G["Initial large chunk (~remaining / p), progressively decreasing to chunksize"]
      end
  end

Detailed Comparison of Scheduling Types

static:
- Iterations are partitioned and assigned to threads at compile/startup time before execution starts.
- schedule(static, chunksize) distributes chunks round-robin across threads.
- schedule(static, 1) yields pure round-robin cyclic distribution.
- Advantages: Zero runtime synchronization overhead; excellent cache locality on NUMA systems.
dynamic:
- Iterations are broken into chunks of size chunksize.
- Threads grab a chunk from a shared work-queue; upon completing a chunk, a thread dynamically requests another.
- Advantages: Excellent load balancing when iteration runtimes are unpredictable.
- Disadvantages: Runtime queue locking introduces scheduling overhead.
guided:
- Threads dynamically request chunks as in dynamic, but chunk size decreases exponentially over time: $\text{chunk\_size} \approx \frac{\text{remaining iterations}}{\text{thread\_count}}$
- Decreases down to chunksize (or 1 by default).
- Advantages: Mitigates queue contention at the beginning while providing fine-grained load balancing at the end.

Table 5.4: Guided Schedule Iteration Assignment ( $n = 10,000, \text{threads} = 2$ )

Thread	Assigned Iteration Range	Chunk Size	Remaining Unassigned Iterations
0	1 – 5000	5000	4999
1	5001 – 7500	2500	2499
1	7501 – 8750	1250	1249
1	8751 – 9375	625	624
0	9376 – 9687	312	312
1	9688 – 9843	156	156
0	9844 – 9921	78	78
1	9922 – 9960	39	39
1	9961 – 9980	20	19
1	9981 – 9990	10	9
1	9991 – 9995	5	4
0	9996 – 9997	2	2
1	9998 – 9998	1	1
0	9999 – 9999	1	0

5.11.2 The `runtime` Schedule and `OMP_SCHEDULE`

To benchmark schedules without recompiling, specify schedule(runtime). The schedule policy is then set via the environment variable OMP_SCHEDULE:

$ export OMP_SCHEDULE="static,1"
$ ./omp_program 4

$ export OMP_SCHEDULE="dynamic,64"
$ ./omp_program 4

$ export OMP_SCHEDULE="guided,16"
$ ./omp_program 4

Choosing the Right Schedule

Uniform Iteration Times: Use schedule(static) (minimal overhead).
Monotonically Increasing/Decreasing Workload: Use schedule(static, small_chunk) or schedule(guided).
Unpredictable or Highly Variable Workload: Use schedule(dynamic, chunk) or schedule(guided).

The parallel for Directive and Loop Scheduling

5.7 The parallel for Worksharing Directive

Differences Between parallel and parallel for