Granularity and the Sequential Cut-Off

Every parallel algorithm design begins by assuming unit-cost operations and free task creation. Neither holds. Creating a task, handing it to another worker, and joining it back costs on the order of hundreds to thousands of cycles in a typical runtime, and the task itself may be a handful of additions. The sequential cut-off, which stops spawning below a threshold and runs the rest as a loop, is the single knob that reconciles the model with the machine, and choosing its value is a calculation, not a guess.

The overhead a task carries

A spawned task pays for several things, and they scale differently:

• Bookkeeping: allocate a task record, push it on a deque, later pop or steal it. Tens of cycles in a good runtime.
• Synchronisation: a join requires an atomic decrement and possibly a wake-up. A contended atomic operation on a shared cache line costs more than an uncontended one by an order of magnitude.
• Cache migration: if the task is stolen, its data is in the parent’s cache, not the thief’s. A steal that immediately misses to DRAM costs hundreds of cycles per line touched, and the number of lines is proportional to the task’s working set.
• Loss of sequential optimisation: a small loop that the compiler would unroll, vectorise, or keep in registers is broken into function calls with opaque boundaries.

The first two are roughly constant per task; the third scales with the task’s data footprint; the fourth scales with how much arithmetic the task does. That difference is why the cut-off is often expressed as “at least this many elements” rather than “at least this many cycles”, because the element count correlates with both arithmetic and footprint for uniform workloads.

A useful rule of thumb: a task should contain at least a few thousand simple operations before it is worth spawning. At a 3 GHz clock and a task overhead of a few thousand cycles, that is roughly a microsecond of work. Tasks below that make the runtime’s own cost comparable to the computation, and utilisation collapses because workers spend their time in scheduler code rather than in the task.

The recursion that stops early

The standard form is a recursion with a threshold:

#include <algorithm>
#include <cstddef>
#include <future>

template <class T>
void pmerge(T* a, size_t n, size_t cutoff) {
    if (n <= cutoff) {                 // sequential base case
        std::sort(a, a + n);           // no spawning, no joins
        return;
    }
    size_t h = n / 2;
    auto fut = std::async(std::launch::async, [&] { pmerge(a, h, cutoff); });
    pmerge(a + h, n - h, cutoff);      // run the second half on this thread
    fut.wait();                        // join
    std::inplace_merge(a, a + h, a + n);
}

The threshold changes the work and the span of the resulting DAG in different ways:

• Work is asymptotically unchanged, because the base cases do the same arithmetic the parallel branches would have done; what disappears is the task overhead the branches would have paid. The small effect that does remain comes from the base case running as a tight loop rather than as a set of calls, which usually lowers work per element.
• Span rises, because the bottom of the recursion, which was log(cutoff) levels deep with parallel branches, collapses into one sequential block whose cost is proportional to cutoff.

If the sequential sort of cutoff elements costs c·cutoff·log(cutoff) and the parallel levels above cost n/P plus log(n/cutoff) merge steps, the total time is approximately n/P + c·cutoff·log(cutoff) + log(n/cutoff)·merge_cost. The cutoff term is a floor: making it smaller reduces the floor but increases the number of tasks by a factor of two per halving. The number of tasks at threshold s over n elements is n/s, so each halving of s doubles the scheduling traffic.

Locating the optimum

The calculation is a balance between two terms that respond in opposite directions to s, the task size in elements:

$$T(s) ;\approx; \underbrace{\frac{W}{P}}{\text{work term}} ;+; \underbrace{c_s \cdot \frac{n}{s}}{\text{task overhead}} ;+; \underbrace{c_q \cdot s}_{\text{sequential tail}}$$

where c_s is the per-task overhead in time units and c_q the per-element cost of the sequential base case. Differentiating with respect to s gives an optimum at

$$s^* = \sqrt{\frac{c_s , n}{c_q}}$$

so the optimal granularity grows as the square root of the input size: larger inputs warrant larger tasks, because the number of tasks otherwise grows linearly and the overhead term dominates. It also grows with c_s, the runtime’s task cost, which is why a runtime with cheap tasks can afford a smaller cut-off.

The formula is a scaling argument, not a measurement, and the constants matter. What it says reliably is the direction: quadrupling n doubles the optimal task size. It also explains why a fixed cutoff of, say, 1024 elements is a reasonable default across a wide range of n, because the square root makes the optimum shallow, so being off by a factor of two or four in s costs only a modest fraction of the achievable time.

Three corrections matter in practice. First, the model assumes the sequential base case is the only serial part; if the combine step (the merge, the partition, the join) is serial, it contributes a term proportional to n that no cutoff removes, and the span analysis is the place to look for that. Second, memory-bound tasks have a much larger effective c_q per element than arithmetic-bound ones, because the sequential loop streams memory at a rate the parallel version cannot exceed; for those, a larger s is better since the base case is the only phase that runs at full bandwidth. Third, the effective P is not the core count when the machine is shared; a cutoff tuned for exclusive use will oversubscribe when other work is present.

Cut-offs that are not about size

Some thresholds are structural rather than numeric. The common ones:

A depth limit. Stop spawning after log₂(P) levels so the tree has exactly P leaves, one per processor. This gives perfect balance for uniform work and no scheduler traffic at all; it is the static-partitioning extreme, and it fails when work per leaf varies.

A work estimate. In irregular problems, the threshold is on remaining work rather than element count: a branch-and-bound node stops spawning when its bound says the subtree is small, which keeps the task count proportional to the useful work rather than to the input size.

A memory limit. In an external-memory or GPU kernel, the cut-off is the size that fits in the target memory level: a block of a few thousand elements in shared memory, or a few hundred kilobytes in L2. The threshold is then set by a hardware constant, not by overhead balance.

A contention limit. When the combine step takes a lock or updates a shared counter, the cut-off must keep the number of combines below the point where the lock becomes the bottleneck. That is usually a much larger threshold than the overhead calculation suggests.

What happens when the cut-off is wrong

Too small: the task count exceeds what the runtime can schedule, failed steals rise, workers spend most of their time in pop and steal, and wall time can exceed the sequential time. The signature is high task counts and low utilisation, with each task running for microseconds or less. On a runtime with a contended global counter, the atomic operation itself becomes the bottleneck and adding processors makes the run slower, the parallel equivalent of thrashing.

Too large: the DAG has few tasks, the tail is long, and the last phase runs on one processor while the rest idle. The signature is good utilisation at the start and a long serial tail. With a cut-off equal to n, the program is sequential by construction.

Both failures are visible in a trace and both are frequently blamed on the scheduler. The scheduler is doing what it was told; the task size is the input it was given.

A subtler failure is a cut-off that is right for the arithmetic but wrong for the memory. A base case that sorts 4096 elements may fit in L1 on one machine and spill on another, changing c_q by an order of magnitude and moving the optimum by a factor of three. This is the reason library implementations expose the threshold rather than hard-coding it, and the reason it should be tuned on the target machine’s memory hierarchy rather than inherited from a paper.

The threshold and determinism

The cut-off also interacts with reproducibility. A computation whose tree shape depends on the cutoff produces a fixed shape for a fixed cutoff, so a reduction over that shape gives the same floating-point result every run. Changing the cutoff changes the shape and hence the rounding. That makes the cutoff part of the numerical contract, not just a performance knob, and it is the practical way to get a reproducible reduction without an order-independent accumulator.

The interaction with work stealing runs the other way: a task that is stolen may execute on a different core, so the memory-locality assumption behind the base case’s efficiency depends on how often steals happen. Runtimes that split large tasks on steal, rather than moving them whole, keep the base cases local; runtimes that move whole tasks can turn a well-sized base case into a cache-miss-bound one.