fib, What a Task Costs, and the Cutoff
One program, timed live. Read fib.cpp, run it at five cutoffs, work out what a task costs by subtracting a run without tasks from a run with them, and reason toward a cutoff from the shape of the numbers.
Concept map
Wednesday was a code walk: one program, run live, and the reasoning done out loud. Everything on this page comes from fib.cpp and its timings.
fib.cpp: a task for each child, until the call is too small
Branch lecture11, src/fib.cpp. The two children are tasks; a call below the cutoff is finished serially, in one piece; the parent waits for its two children before adding.
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; }
main runs fibSerial(n) first, then fibParallel(n, cutoff) inside parallel / single, times both, and prints the task count from countTasks, the same recursion without the pragmas. So the number you see is exact, not estimated.
./fib 35 36 and ./fib 35 1. How many tasks does each make? At cutoff 36 the very first call has n = 35 < 36, so fibSerial does everything: zero tasks. At cutoff 1 every call with n ≥ 2 makes two tasks: 29,860,702 of them, because fib(35) is about 30 million calls.
fib(35) cutoff 36 threads 1 tasks 0 serial 0.014 s = 9227465 parallel 0.014 s = 9227465 fib(35) cutoff 1 threads 1 tasks 29860702 serial 0.014 s = 9227465 parallel 1.910 s = 9227465
The same program, five cutoffs
Laptop, 2 cores, min of 5. The work is identical in every row: the same adds, the same answer. Only the task count changes.
14.84 s, almost 8× slower than one thread. Every task is pushed to and popped from one shared pool, and 30 million task records are allocated and freed; with two threads every one of those operations is contended. Adding a thread made the bad end worse.
Drag the cutoff. The row is the measured run; the bar is how the time splits between the serial work (0.014 s, the same every time) and whatever the tasks added.
What a task costs: subtraction
Cutoff 36 and cutoff 1 do the same work. The difference in time is the tasks, and nothing else. Divide by the task count and you have the cost of one.
(1.910 − 0.014) s ÷ 29,860,702 = 0.0635 µs, about 64 ns, to make, queue, run and retire one task when no other thread touches the pool. Units matter: the subtraction is in seconds, the count is tens of millions, so the answer is tens of nanoseconds.
Two threads were busy for 14.84 s: 29.7 thread-seconds for 0.014 s of work. Per task that is about 0.99 µs of thread time, roughly 16× the one-thread cost. The cost of a task is not a constant of OpenMP; it depends on how many threads are fighting for the pool. On Cardinal with 48 threads the same run takes 74 s, about 119 µs of thread time per task.
Your own numbers
Type a run with tasks, a run without, and the task count. The subtraction is the whole method.
Picking the cutoff
Cutoff 20 and 30 were both good on the laptop. The question Wednesday ended on: would they be on 48 threads? Two conditions, in words.
Left end: too many tasks
Every task is paid for, and the price goes up with more threads sharing the pool. A task is worth making only if the work inside it is much larger than its cost — the cost measured at the thread count you will use.
Right end: too few tasks
Cutoff 30 makes 40 tasks. Plenty for 2 threads. With 48, most threads would have nothing, and the run ends when the last big piece finishes on one thread. There must be enough tasks that no single piece is left running alone at the end.
No. A task has to carry far more than its 100 µs cost — say a millisecond — and 14 ms of work can be cut into only about 14 such pieces. 48 threads need many more than that. Cutoff 20's 5,166 tasks each carry about 3 µs of work, far below the cost. The two conditions cannot both hold: the problem is too small for the machine. The fix is fewer threads or a bigger problem, not a cleverer cutoff. Monday's quicksort on 10⁷ elements does have a cutoff that works on 48 threads: 10⁴ to 10⁵.
In words on Wednesday; as a chart and a formula
The quicksort sweep from Monday, rerun on Cardinal with 48 threads (Oct 30, min of 5). The label on each point is the task count the program printed.
The formulas
cost of one task = (time with tasks − time without) ÷ tasks, at your thread count.
Left edge: work in a task ≥ about 10 × that cost.
Right edge: tasks ≥ about 10 × threads, so no piece runs alone at the end.
Pick the middle of what is left; check with three runs.
Reading the curve
c = 1: 2 × 10⁷ tasks, each paid for; with 48 threads on one pool the cost per task is tens of µs.
c = 10⁴ – 10⁵: the floor, 0.12 s. Not 1.20 ÷ 48 = 0.025 s, because the first partitions of the whole array run on one thread before there is anything to share.
c = 5 × 10⁶: the first partition leaves two halves of 5 × 10⁶ and each is sorted serially on one thread. The run waits for that one piece, about half the serial time. Idle threads are the symptom; the long piece is the cause.
Run it on Cardinal
Measure the cost of a task yourself, at 1, 2 and 8 threads, and see which fib cutoffs survive 8 threads. Branch lecture11, program fib. About 15 minutes.
-
The lecture branch, built
If you built
lecture11on Monday, skip to step 2. Otherwise:git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/openmp.git openmpif you have not cloned yet, then:ssh <your-username>@cardinal.osc.edu cd openmp git fetch class git checkout -b lecture11 class/fa2026-openmp/lecture11 module load gcc/12.3.0 cd Default && make OSC && cd ..
-
Get cores of your own
Modules do not persist between logins: after a new login, run
module load gcc/12.3.0again.salloc -N 1 -n 1 -c 8 -t 00:15:00 -A PCS0313
Experiments
A · The cost of a task at 1, 2 and 8 threads
Predict first: does the cost go up or down with threads, and by how much? The 8-thread cutoff-1 run can take a minute or more; that is the point.
for t in 1 2 8; do
echo "== $t threads"
OMP_NUM_THREADS=$t srun -c 8 ./Default/fib 35 36
OMP_NUM_THREADS=$t srun -c 8 ./Default/fib 35 1
doneWhat you should see
Both runs print tasks: 0 at cutoff 36 and 29,860,702 at cutoff 1, on every machine. Cost of one task = (cutoff-1 time − cutoff-36 time) × threads ÷ 29,860,702. Cardinal on 1 thread: (2.32 − 0.018) s ÷ 29.9 M ≈ 77 ns. On 48 threads the same run took 73.8 s, about 119 µs of thread time per task. Your 8-thread number lands between those.
B · Which cutoffs survive 8 threads?
On the laptop, 20 and 30 beat serial on 2 threads. Predict which of these beat serial on 8 before you run.
for c in 36 30 25 20 15 10; do
echo "== cutoff $c"
OMP_NUM_THREADS=8 srun -c 8 ./Default/fib 35 $c
doneWhat you should see
Task counts are arithmetic and match the laptop: 0, 40, 5,166 at cutoff 20, 635,620 at 10. The times are yours. Expect the good middle to be narrower than on 2 threads, and cutoff 10 to be clearly slower than serial: the cost per task has gone up, so a task has to carry more work to be worth it.
C · The real fix for a small problem
OMP_NUM_THREADS=2 srun -c 8 ./Default/fib 35 25 OMP_NUM_THREADS=8 srun -c 8 ./Default/fib 35 25 OMP_NUM_THREADS=8 srun -c 8 ./Default/fib 42 25
What you should see
fib(35) at the same cutoff: compare 2 threads with 8. Then fib(42), about 29× the work, at the same cutoff on 8 threads: the tasks are the same size, there are 29× more of them, and now 8 threads have something to do. Fewer threads or a bigger problem: those are the two levers when the cutoff has nothing left to give.
Check yourself
Six questions, instant feedback, nothing recorded.
./fib 35 36 prints tasks 0. Why?