Parallel Algorithms: Work, Span & Decomposition

A parallel algorithm is not a sequential loop with more threads. It is a dependency design: split the computation into operations, state which results each operation needs, and expose every operation that may run concurrently. Work measures the total computation; span measures the longest unavoidable dependency chain. Only after both are sound does processor count enter the analysis.

The computation DAG #

Represent one execution as a directed acyclic graph (DAG):

• a vertex is a unit-time operation in the abstract model;
• an edge $u\rightarrow v$ means $v$ cannot execute until $u$ completes;
• sources are initially ready; a sink represents completion.

Independent vertices may run together. The model describes semantic dependencies rather than a particular assignment of tasks to workers.

flowchart LR
    A1["a+b"] --> C1["(a+b)+(c+d)"]
    A2["c+d"] --> C1
    A3["e+f"] --> C2["(e+f)+(g+h)"]
    A4["g+h"] --> C2
    C1 --> Z["total"]
    C2 --> Z

For this eight-value reduction, the DAG has seven additions but only three dependent layers.

Any execution on $P$ processors obeys two lower bounds:

$$T_P\ge\frac{W}{P} \qquad\text{and}\qquad T_P\ge S.$$

The first is a capacity bound; $P$ processors cannot perform more than $P$ operations per step. The second is a dependency bound; processors cannot shorten a causal chain. Therefore

$$T_P\ge\max(W/P,S).$$

Brent's scheduling principle supplies the matching idealized upper shape: schedule ready operations greedily and

$$T_P\le \frac{W-S}{P}+S\le W/P+S.$$

The useful consequence is not an exact hardware prediction. It is a design target: keep work near the best sequential algorithm and make span much smaller than work.

Work efficiency comes before speedup #

A parallel algorithm is work-efficient when $W$ is asymptotically no worse than a good sequential algorithm for the same problem. An algorithm with tiny span but $n^2$ work may lose to a sequential $O(n\log n)$ algorithm even on many processors.

Define measured speedup and efficiency as

$$\mathop{\mathrm{speedup}}(P)=T_1/T_P, \qquad \mathop{\mathrm{efficiency}}(P)=\frac{T_1}{P T_P}.$$

Use the same implementation quality and workload when interpreting them. Apparent superlinear speedup often signals a changed cache regime, memory capacity, algorithm, or baseline—not more than $P$ units of abstract compute per step.

The ratio $W/S$ estimates the useful processor ceiling. When $P\gg W/S$, the span bound dominates and extra processors mostly wait. The exact crossover arrives earlier once scheduling, communication, and memory costs are included.

Worked example: reduction #

A left-to-right sum has

$$W=n-1,\qquad S=n-1.$$

Reassociating an associative operation into a balanced binary tree preserves $W=n-1$ but reduces span to $\lceil\log_2 n\rceil$. The algorithm now exposes roughly $n/\log n$ average parallelism.

At level 0, add adjacent input pairs; at level 1, add adjacent pair-sums; continue until one result remains. If $P<n/2$, each level can process its ready operations in batches, and the $W/P+S$ bound captures both limited throughput and the logarithmic chain.

Prefix scan: parallelizing an apparent chain #

Given an associative operator $\oplus$, identity $e$, and input $[x_0,\ldots,x_{n-1}]$, an exclusive scan returns

$$[e,\ x_0,\ x_0\oplus x_1,\ldots,x_0\oplus\cdots\oplus x_{n-2}].$$

Each prefix appears to depend on the previous one, but Blelloch's tree algorithm separates the computation:

1. up-sweep: build partial reductions in a balanced tree;
2. set the root to $e$;
3. down-sweep: propagate the reduction of all preceding leaves to each child.

For a power-of-two length, both passes have $O(n)$ total work and $O(\log n)$ span. Padding or an irregular tree handles other lengths. The scan is work-efficient and becomes a building block for stream compaction, radix partitioning, polynomial evaluation, sparse allocation, and many graph algorithms.

A tempting alternative computes every prefix with its own parallel reduction. Its span is still logarithmic, but its total work is $\Theta(n^2)$; it spends processors to hide an avoidable algorithmic cost. Work/span analysis exposes that failure immediately.

Decomposition patterns #

Good decomposition separates three questions:

1. Coverage: does every required unit of work execute exactly as the algorithm requires?
2. Dependencies: are all read-after-write, write-after-read, and write-after-write constraints represented?
3. Granularity: is each task large enough to amortize spawn, queue, synchronization, and cache costs?

Removing a true dependency creates a race or wrong result. Adding a false dependency preserves correctness but lengthens span. That is why dependency analysis—not thread count—is the core algorithmic skill.

Scheduling irregular task trees #

Static equal-size partitions work when task costs are predictable. Recursive search, sparse graphs, and adaptive meshes create uneven subtrees. A work-stealing scheduler lets an idle worker take ready work from another worker's deque.

Cilk's analysis formalizes this for structured fork–join computations: under its assumptions, randomized work stealing achieves expected running time of the form

$$T_P=O(W/P+S).$$

The theorem is conditional on the computation model, scheduler, and cost assumptions. Blocking I/O, priority constraints, unstructured futures, memory contention, or tasks whose runtime changes with placement can fall outside it. Work stealing balances ready tasks; it does not remove an algorithm's critical path or memory bottleneck.

Amdahl's limit and scaling the question #

If a fraction $f$ of a fixed workload remains serial and the rest parallelizes perfectly, normalized time on $P$ processors is

$$T_P=f+\frac{1-f}{P},$$

so speedup is

$$S_P=\frac{1}{f+(1-f)/P}\le\frac1f.$$

With $f=0.05$, unlimited processors cannot exceed $20\times$ speedup in this model. The serial fraction includes not only visibly sequential code but also critical-path dependencies and overhead that does not shrink with $P$.

Amdahl's law answers strong scaling: how fast can the same problem instance run? Weak scaling grows the problem with processor count and asks whether time stays controlled. Larger instances may expose more parallel work, but scaling the input does not repeal dependencies; it changes the experiment. Always state which quantity is held fixed.

Sorting networks: a schedule in hardware-like form #

A comparator takes two values and emits (min,max). A sorting network connects fixed comparators on fixed wires; its comparison pattern is independent of input values.

• size is the number of comparators, analogous to work;
• depth is the number of comparator layers when disjoint comparators in one layer run together, analogous to span.

Batcher's bitonic sorting network sorts powers of two with $O(n\log^2 n)$ comparators and $O(\log^2 n)$ depth. It uses more work than optimal sequential comparison sorting but offers a regular, branch-free, data-oblivious schedule. That trade can be attractive in circuits, SIMD-like execution, and settings where a fixed access pattern matters.

Network correctness has two parts: each comparator preserves the multiset, and the full network orders every input. The zero–one principle reduces the latter proof for comparison networks to binary inputs—but does not make exhaustive testing practical for large $n$ without further structure.

The hardware model eventually matters #

Work/span abstracts away costs that often dominate:

• cache misses, memory bandwidth, NUMA placement, and false sharing;
• message latency, bandwidth, and collective communication;
• synchronization, atomic operations, barriers, and task creation;
• vector width and divergence;
• replication, retries, and failures in distributed execution.

Two DAGs with identical $W$ and $S$ can perform very differently if one streams contiguous memory and the other issues dependent random loads. Refine the model with block transfers, communication volume/rounds, or measured per-task costs when those resources are load-bearing. See CPU caches for the locality layer and memory models for the execution semantics of shared state.

Parallel-algorithm audit #

1. What are the DAG vertices and true dependency edges?
2. What are $W$, $S$, and $W/S$ in the declared cost model?
3. Is the parallel algorithm work-efficient against the best relevant sequential baseline?
4. Which operator laws justify reassociation or reordering?
5. What is the worst load imbalance, and can idle workers reach ready work?
6. Is task grain large enough to pay for scheduling and synchronization?
7. Does the claimed speedup use strong or weak scaling and the same baseline?
8. Which serial fraction or critical path sets the Amdahl/span ceiling?
9. Are bandwidth, cache, NUMA, or communication costs absent from the abstract proof but dominant in the implementation?
10. Is output deterministic, reproducible within a tolerance, or deliberately schedule-dependent?

The central optimization order is: remove avoidable work, shorten genuine dependencies, expose enough coarse ready tasks, and only then tune their placement on a real machine.