How do you choose task granularity — the amount of work per parallel unit — when each unit carries a fixed scheduling overhead? Explain the cost model and what goes wrong at each extreme.

## What granularity means **Granularity** is the amount of useful work in one schedulable unit. Fine-grained means many small units; coarse-grained means few large ones. The choice is not stylistic: it determines whether parallelising helps at all, because every unit carries a fixed cost that does no useful work. ## What the overhead actually consists of Per unit, independent of its size, you pay some subset of: - allocating or boxing the unit (a task object, a closure, a future); - pushing it onto a queue and, later, popping it — usually an atomic operation, sometimes a contended one; - the scheduler's bookkeeping, and a possible hand-off to another core; - cache effects — a unit that runs on a different core than the one that produced its data pays cold-cache and cross-socket costs; - synchronisation on completion — a join, a counter decrement, a wake-up; - for a memory-bound unit, the cost of losing whatever the producing core had warm. Order of magnitude: sub-microsecond for a well-tuned in-process scheduler, several microseconds if a hand-off and a wake-up occur, and milliseconds if the "unit" crosses a process or network boundary. The absolute number matters less than the ratio. ## The cost model With total work W, P workers, n units and per-unit overhead c: ``` T_parallel ≈ W/P + n·c/P + T_tail + T_serial ``` The overhead term grows linearly with n; the imbalance term shrinks as n grows. That opposition is the entire tradeoff. **Efficiency constraint.** You want overhead to be a small fraction f of useful work: ``` c / (W/n) ≤ f → W/n ≥ c/f ``` With c = 1 µs and f = 1%, each unit needs ≥ 100 µs of work. With f = 10%, ≥ 10 µs. This is the origin of the common rule of thumb "a task should be worth at least tens of microseconds" or "at least ~10,000 operations". **Balance constraint.** The tail is bounded by the duration of the last unit still running, so: ``` T_tail ≈ W/n → n ≥ k·P with k ≈ 4…16 ``` Over-partitioning is what lets a scheduler (particularly a work-stealing one) redistribute when unit costs turn out unequal. With n = P exactly, one unit that is twice as expensive as the rest doubles your wall clock. Combine them: `k·P ≤ n ≤ W·f/c`. If the interval is empty — that is, `k·P·c/f > W` — the input is too small to parallelise profitably. That is a legitimate and often correct answer. ## What goes wrong at each extreme **Too fine.** Overhead dominates and the parallel version can be slower than the sequential one, sometimes by a large multiple. Symptoms: high CPU with low useful throughput, scheduler queues hot, allocation rate spiking, and speedup that *decreases* as you add workers because contention on the shared queue rises. The pathological case is a per-element task for elements that take nanoseconds — you have wrapped a 2 ns operation in a 1 µs envelope. **Too coarse.** Workers finish early and idle. With 8 workers and 8 units where one takes twice as long, utilisation drops to about 56%. Coarse units also react badly to any unpredictability — a unit that hits a slow path, a cache miss storm, or a preempted thread cannot be redistributed once it has started. ## The sequential cutoff The standard implementation of "right granularity" in recursive decomposition is a threshold: ``` solve(range): if size(range) <= CUTOFF: return solve_sequentially(range) (left, right) = split(range) a = spawn solve(left) b = solve(right) # run one half on the current worker return combine(await a, b) ``` Two details matter. First, running one half inline on the current worker halves the number of scheduled units for free. Second, the cutoff should be expressed in *work*, not item count, when per-item cost varies — 1,000 short strings and 1,000 megabyte blobs are not the same unit. How to pick CUTOFF: measure. Time the sequential version at several input sizes, find the size at which one unit takes roughly 50–100× your measured per-task overhead, and check that the resulting unit count is still several times the worker count. Then sweep the value and look at the curve — it is usually flat over a wide range, which is good news: you need to be in the right order of magnitude, not exact. ## Adaptive alternatives Rather than a fixed cutoff, some schedulers decide dynamically: split only if another worker is idle (or if the local queue is empty), so granularity adapts to available parallelism at runtime. Guided chunking, which hands out progressively smaller chunks as remaining work shrinks, is the data-parallel analogue: coarse early for efficiency, fine late for balance. ## What to say in an interview Name both constraints, give the ratio reasoning rather than a magic number, mention that the number depends on the measured per-task overhead of the specific runtime, describe the recursive cutoff as the implementation, and end with "then I measure" — including measuring whether parallelising helped at all, since for small inputs the honest answer is that it does not.