Parallelism and Work Distribution

A task checks whether its input is small enough to do directly. If not, it splits the input into independent pieces, forks them so they can run in parallel, then joins - waits for each piece to finish - and combines their results. Join gives completion and result visibility.

Map transforms each input record independently into key-value pairs. Shuffle regroups those pairs so that all values for the same key land together on one reducer. Reduce folds each key's group into a result. Without the regroup step a reducer would only see part of each key.

Split a repeated job into ordered steps called stages, each with its own worker and a queue in front of it. Different items sit in different stages at the same time, so all workers run at once. Steady-state throughput is one item per slowest stage's time.

Each split costs bookkeeping - creating, queueing and scheduling a task. Below some size that overhead exceeds the useful work, so the recursion would slow things down. Pick the threshold by measuring: choose the smallest size where parallel still beats sequential, comfortably above the break-even point.

The operation must be associative, so any bracketing of the same ordered elements gives the same answer, letting chunks combine in a tree. An identity element gives empty chunks a value to return, so partitioning is free. Commutativity is only needed if chunks may combine out of order.

Throughput is 1 per 50 ms (20/s), set by the slowest step; latency is at least 70 ms plus waiting. To improve it, attack only the 50 ms step: make it cheaper, split it into smaller sequential steps, or run several copies of it in parallel. Speeding up the 10 ms steps changes nothing.

Amdahl's law: for a fixed job with serial fraction s, speedup on N workers is 1 / (s + (1 - s)/N), capped at 1/s as N grows. At 5% serial the ceiling is 20x, however many workers you add.

Each worker owns a local task queue and normally runs tasks it created itself; a worker whose queue is empty steals a task from another worker's queue. Compared with one shared queue, nearly every handoff stays thread-local, so there is no central contention point and no coordinator assigning work.

Each unit costs a fixed overhead (submit, schedule, synchronise) on top of its useful work. Make units large enough that overhead is a small fraction of the work — typically at least tens of microseconds of work per unit — but small enough that you have several times more units than workers, so the tail after the last split is short. Too fine: overhead dominates. Too coarse: idle workers and a long tail.

Look for: per-unit scheduling overhead exceeding the work, contention on a shared lock or counter, false sharing of cache lines between workers, saturation of a shared resource (memory bandwidth, one disk, one connection pool), too little total work to amortise startup, and oversubscription causing context switches. Distinguish by checking whether speedup falls as workers are added — that points to contention or bandwidth, not overhead.

Blocked workers still occupy their pool slot, so throughput collapses and, if the blocked tasks are waiting on work that is queued behind them, the pool deadlocks. Keep the compute pool for CPU-bound non-blocking work; run blocking work on a separate, larger pool or an async path.

Always bounded. An unbounded queue turns a rate mismatch into unbounded memory and unbounded latency. Bounded means a full queue blocks the upstream stage and an empty queue stalls the downstream one — both visible, self-limiting signals. Size it to cover normal jitter only, since depth becomes latency.

Embarrassingly parallel means the work splits into independent pieces that need no communication or coordination while running — each piece reads only its own input and writes only its own output. Cross-piece dependencies, shared mutable state, order sensitivity, or contention on one shared resource disqualify it.

Block gives each worker one contiguous range — best locality, worst load balance under uneven costs. Round-robin interleaves items across workers — balances a smooth cost gradient, hurts locality. Dynamic handout gives workers a new chunk when they finish — best balance under unpredictable costs, at the price of coordination on the shared cursor. With highly variable per-item cost, use dynamic (or many small static chunks).

Forking both halves wastes the current thread, which then only waits; doing one half in place keeps it busy and halves the number of tasks. Forking then immediately joining is worse still - it serializes the two halves while paying full task overhead, giving sequential speed at parallel cost.

Both perform n-1 combines - the total work is the same. The chain is n-1 steps deep because each waits for the previous; the balanced tree is about log2(n) levels deep and each level's combines are independent. Depth, not operation count, is what limits parallel speed.

Speedup S = T(baseline) / T(N); efficiency E = S/N, the fraction of each worker that does useful work. The baseline must be the best sequential implementation, not the parallel code on one worker. Speedup above N (superlinear) is usually a cache or memory-hierarchy effect, not an error.

LIFO locally keeps execution depth-first: the newest task's data is still cache-hot and memory stays bounded. Thieves take the oldest task because, near the root of the computation, it is the largest subtree — so one steal buys a lot of work. Using opposite ends also keeps owner and thief off the same memory, so the local path needs almost no synchronization.

A combiner folds a worker's own key-value output locally before the exchange, cutting the data crossing the network. It is safe when the reduce operation is associative and commutative and its output type can be fed back in as input. For a mean, pre-aggregate (sum, count) pairs and divide at the end.

Key skew: one key (or a few hashing together) holds a huge share of the records, and a key cannot be split across workers, so its worker becomes the straggler. Options: pre-aggregate locally, salt the hot key into sub-keys and aggregate twice, or isolate hot keys. No ordering is guaranteed - not of values within a group, nor of outputs.

Pipelining raises throughput by keeping several items in flight, but one item still visits every stage in order and now also pays handoff and queue waiting. Per-item time = sum of stage service times + waiting. Little's law gives the wait: average time in system = items in system / throughput.

Amdahl fixes the problem size and asks how much faster it finishes; Gustafson fixes the runtime and asks how much bigger a problem you can solve. Scaled speedup is S = N - s(N-1), which grows with N because the parallel work grows too.

The sequential merges form a chain: the final merge alone touches every element, and nothing can shorten it. That chain is the critical path of the task graph and bounds the finish time no matter how many cores exist. Raise the ceiling by parallelizing the merge itself.

Decide by resource heterogeneity and serialization. If the steps need very different resources, or one step must be single-threaded, batched, or ordered, use stages sized independently. If items are homogeneous with no serial resource, a pool carrying each item end to end is simpler and keeps better locality.

A declining curve means coordination cost is growing faster than capacity, so more hardware will make it worse. Fit contention and coherence coefficients to the sweep: contention-dominated means split the bottleneck; coherence-dominated means partition or stop sharing. Meanwhile cap concurrency at the measured peak.

Work stealing assumes short, non-blocking, splittable, order-insensitive tasks. Blocking tasks park workers while their queued work sits unreachable; tasks too fine make steal and bookkeeping overhead dominate; tasks too coarse leave nothing to steal; and its last-in-first-out local order is deliberately unfair, so latency-sensitive requests need a separate fair pool.

It adds contention (serialization on shared resources, cost grows with N) and coherence (keeping shared state consistent, cost grows with N squared because it is pairwise). Once the quadratic coherence term outgrows the linear capacity gain, throughput peaks and then falls.

Child stealing: the spawned subtask goes on the deque, the spawning thread keeps running the parent. Continuation stealing: the thread jumps straight into the subtask and puts the parent's remainder (its continuation) on the deque. Continuation stealing matches sequential order and bounds outstanding tasks, but needs runtime or compiler support to capture a continuation, so libraries usually do child stealing.

Decompose by data if you need the job to scale with input size — parallel width then grows with the data and survives the move to a cluster. Decompose by task only where you need to overlap a fixed set of independent operations. The data choice commits you to a partition key, to state that is per-partition, and to a skew and rebalancing story.