When the Parallelism Isn’t a Loop

Concept map

Three moves, in the lecture's order: a few fixed pieces, then work you discover as you go, then how small a piece of work can usefully be. Click a node to jump to it.

Everything here runs from the openmp repository, branch lecture11: six small programs, one per idea — sections, tasks_bug, tasks_fixed, quicksort, fib, treesum. Each prints its serial answer next to its parallel one; the number after the program name is the knob. Every time on this page is from the course test machine (2 cores, shared with other jobs, g++ 13 -O2, min of 5 interleaved runs, Oct 30). Where Cardinal (48 cores, Oct 30) measured something different, the Cardinal section says so.

Wrote vs. made

A loop gave the runtime its pieces for free: the iterations. When the work is not a loop, someone has to make the pieces. Three nouns, kept apart for the rest of the page: a section is a piece you wrote, a task is a piece the program makes, a thread runs pieces.

Thread ≠ task. A thread runs many tasks in sequence; a task runs on exactly one thread, exactly once. That is why the same task code runs at t = 2 and t = 48 without a change.

Sections: a few fixed pieces

sections.cpp. Three different pieces of work, sizes 1 : 2 : 3. One thread alone takes 6 units. Each section runs once, on some thread, and nobody leaves the region until all three are done.

#pragma omp parallel sections
{
    #pragma omp section
    {
        result[0] = spin(1 * units, 1.0);
    }

    #pragma omp section
    {
        result[1] = spin(2 * units, 2.0);
    }

    #pragma omp section
    {
        result[2] = spin(3 * units, 3.0);
    }
}// Implicit barrier: the slowest thread decides.

Hand out the sections yourself

The real run

$ OMP_NUM_THREADS=1 ./sections 3e7
section 0  size 1  thread 0  0.058 s
section 1  size 2  thread 0  0.118 s
section 2  size 3  thread 0  0.171 s
region 0.348 s
$ OMP_NUM_THREADS=2 ./sections 3e7
section 0  size 1  thread 0  0.056 s
section 1  size 2  thread 1  0.119 s
section 2  size 3  thread 0  0.168 s
region 0.224 s
results match serial: yes

Real output, one run each, test machine, 2 cores (the first run's last line cut). Min of 5: 0.227 s / 0.337 s = 0.67. The model: 4 / 6 = 0.67. Which thread gets which section changes between runs; on 2 threads one thread always ends up with sizes 1 and 3.

One thread makes tasks; all of them run

The start of main() in quicksort.cpp. Every task program in this course starts this way. A task is a piece of work plus the data it needs, dropped in a shared pool; idle threads take work from the pool.

// The team: t threads.
#pragma omp parallel
{
    // ONE thread starts the recursion.
    #pragma omp single    {        parallelQuicksort(a, 0, n - 1, cutoff);
    }}
// Everyone else waits at single's barrier, and runs
// tasks while it waits. This barrier ends only when
// EVERY task, at every depth, is done.

Quicksort: two tasks per partition

parallelQuicksort from quicksort.cpp. After partition, every element of a[lo..p] is ≤ the pivot ≤ every element of a[p+1..hi], so the two halves can be sorted at the same time with no lock.

void parallelQuicksort(int* a, long lo, long hi, long cutoff) {

    if (lo >= hi) {
        return;
    }

    // A small piece is not worth a task.
    if (hi - lo + 1 < cutoff) {        serialQuicksort(a, lo, hi);        return;    }

    long p = partition(a, lo, hi);

    #pragma omp task
    {
        parallelQuicksort(a, lo, p, cutoff);
    }

    #pragma omp task
    {
        parallelQuicksort(a, p + 1, hi, cutoff);
    }

    // No taskwait: nobody here reads the sorted halves.
}

Watch the tasks appear

A task reads a shared variable when it runs

tasks_bug.cpp, part 1. 16 tasks, one per index. out has 17 slots, all −1; out[16] is a spare. square(k) does a little work, then returns k².

int g_i;                                // file scope: shared

#pragma omp parallel
{
    #pragma omp single
    {
        for (g_i = 0; g_i < N; g_i++) {            #pragma omp task
            {
                out[g_i] = square(g_i);
            }
        }
    }
}

$ OMP_NUM_THREADS=2 ./tasks_bug          # g++ 13
out[0..15] = . . . 9 . . . . . . . . . . . .
out[16] (spare) = 256
bug 1: 1 of 16 slots right

$ OMP_NUM_THREADS=1 ./tasks_bug          # g++ 13
out[0..15] = . . . . . . . . . . . . . . . .
out[16] (spare) = 256
$ OMP_NUM_THREADS=1 ./tasks_bug_clang    # clang 18
out[0..15] = 0 1 4 9 16 25 36 49 64 81 ...
bug 1: 16 of 16 slots right

Step through one thread

A global is not required for this bug. By the rules, a plain local int i declared before the parallel region is shared in the region and so shared in the task: the same bug. One compiler can happen to mask it, which is why the program uses a global — so g++, the Cardinal compiler, shows it every time.

What a task can see

The rules with no default clause. Inputs travel by copy; a result the parent reads has to be shared, and the parent has to wait for it.

// tasks_bug.cpp, part 2
#pragma omp single
{
    long x = 0;

    #pragma omp task
    {
        x = fibSerial(20);
    }

    #pragma omp taskwait

    result = x;
}

bug 2: x = 0   (fib(20) = 6765)

The reference row, measured

treesum.cpp sums a tree of 2²⁰ − 1 ints (about 4 MB) twice: passing a pointer, and passing a const std::vector<int>&. With a depth cutoff of 6 each version makes 126 tasks. Each by-reference task copies the whole 4 MB tree.

When a task returns something: three waits

Quicksort never waits: its tasks write disjoint ranges and return nothing, so the barrier at the end of single is the only wait it needs. This is the one thing quicksort cannot show you, so the example changes to fibParallel from fib.cpp — the smallest program where a task hands a value back. Each call makes two tasks and needs both answers back, so x and y are shared and the call waits for its two children before it adds them.

long fibParallel(int n, int cutoff) {

    if (n < 2) {
        return n;
    }

    // A small call is not worth a task.
    if (n < cutoff) {
        return fibSerial(n);
    }

    long x;
    long y;

    // shared: the answer has to come back to this x and y.
    #pragma omp task shared(x)
    {
        x = fibParallel(n - 1, cutoff);
    }

    #pragma omp task shared(y)
    {
        y = fibParallel(n - 2, cutoff);
    }

    // Wait for my two children, then read what they wrote.
    #pragma omp taskwait
    return x + y;
}

The cutoff curve

./quicksort 1e7 c: sort n = 10⁷ ints, and sweep the cutoff c from 1 to 2 × 10⁷. A piece smaller than c is sorted serially, with no task.

Which way does the knob turn?

"Cutoff" means opposite things in different codes. Both kinds put a floor under the size of a task; they turn in opposite directions.

Run it on Cardinal

Branch lecture11: six programs, each built into Default/. About 20 minutes. Every number quoted above is from the 2-core test machine. Each experiment below also gives what Cardinal measured on Oct 30 (node c0318, gcc 12.3, 48 cores, min of 5); yours will land near those, and the shapes are what to compare.

1. Fetch and check out the lecture branch

   If you have not cloned the OpenMP repository yet: git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/openmp.git openmp first.

   ssh <your-username>@cardinal.osc.edu
   cd openmp
   git fetch class
   git checkout -b lecture11 class/fa2026-openmp/lecture11

   copy

2. Build all six, then get cores of your own

   Modules do not persist between logins. The login node is shared; anything you time goes in an allocation.

   module load gcc/12.3.0
   cd Default && make OSC && cd ..
   salloc -N 1 -n 1 -c 8 -t 00:15:00 -A PCS0313

   copy

   Every run: OMP_NUM_THREADS=t srun -c 8 ./Default/<program> [knob]. The thread count always comes from OMP_NUM_THREADS.

Experiments

for t in 1 2 3 4; do
    echo "== $t threads"
    OMP_NUM_THREADS=$t srun -c 8 ./Default/sections 3e7
done

for t in 1 2; do
    OMP_NUM_THREADS=$t srun -c 8 ./Default/tasks_bug
    OMP_NUM_THREADS=$t srun -c 8 ./Default/tasks_fixed
done

for c in 1 100 1000 100000 1e6 2e7; do
    echo "== cutoff $c"
    OMP_NUM_THREADS=8 srun -c 8 ./Default/quicksort 1e7 $c
done

OMP_NUM_THREADS=1 srun -c 8 ./Default/treesum 20 6
OMP_NUM_THREADS=1 srun -c 8 ./Default/treesum 20 30

exit
sbatch jobScript.slurm