Work, Span, and the Bound on Parallel Execution Time

A sequential cost model counts operations. For parallel algorithms that count is necessary but not sufficient: two programs with identical operation counts can differ in running time by the width of the machine, because the operations constrain each other. The standard way to capture the constraint is to model the computation as a directed acyclic graph.

Two numbers instead of one

Nodes of the graph are unit-cost operations: an addition, a comparison, a load. Edges are dependencies; an edge from one node to another means the second cannot start before the first finishes. Work, written W, is the number of nodes. Span, written D and also called depth or critical-path length, is the number of nodes on the longest path. A sequential execution is a topological order of the graph and takes W steps.

Summing n numbers shows the distinction. A left-to-right loop has W = n−1 and D = n−1, because every addition waits for its predecessor. A balanced tree has the same W and D = ⌈log₂ n⌉. Both compute the same value; only the dependency structure differs. At n = 2²⁰ the loop has a span of about a million steps and the tree has a span of 20.

The ratio W/D is the parallelism of the computation: the average number of operations that can be in flight at once. It bounds the number of processors that can be put to use. If W/D is 4, then eight processors cannot improve the DAG; four is the ceiling regardless of how the work is scheduled. This is why the phrase “embarrassingly parallel” is not about the total amount of work but about how little of it is chained together.

Span is a property of the algorithm, not of the machine and not of the loop decoration. It is the minimum number of steps any schedule must take, achieved only when a longest remaining path is always executed without delay. Adding more processors changes neither W nor D.

Brent’s bound and the greedy schedule

Given W, D, and P processors, the running time T_P is bracketed by two bounds:

$$T_P ;\ge; \max!\left(\left\lceil \frac{W}{P} \right\rceil,; D\right)$$

The first term divides the total work among the processors; the second is the critical path, which no amount of parallelism shortens. The upper bound is Brent’s theorem:

$$T_P ;\le; \frac{W - D}{P} + D$$

The argument is a schedule, not an average. Place the D nodes of a longest path in sequence, and between consecutive path nodes insert at most (W − D)/P of the remaining work distributed over the processors. Any greedy schedule, meaning one that never leaves a processor idle while a ready node exists, meets that bound. Brent proved the result for arithmetic expression evaluation; the argument depends only on unit-cost nodes and the DAG, so it applies to any fork-join computation.

Numbers make the two terms concrete. Take W = 10⁹ additions and D = 10⁴. With P = 64 the lower bound is max(1.56 × 10⁷, 10⁴) ≈ 1.56 × 10⁷, and the upper bound is (10⁹ − 10⁴)/64 + 10⁴, essentially the same figure. Work dominates. Raise P to 10⁶ and the work term falls to 1000, but D = 10⁴ still floors the running time: speedup saturates at W/D = 10⁵, so only a tenth of the processors can ever be busy at once and the rest idle for the whole run. Span, not processor count, is the binding constraint once P exceeds the parallelism.

The bound is also why schedulers do not need to solve the NP-hard problem of finding the optimal makespan. A greedy schedule satisfies T_P ≤ 2·T_P* where T_P* is the optimal time, so any work-conserving policy is within a factor of two of optimal for unit-cost DAGs. Work stealing is work-conserving and attains O(W/P + D) in expectation, which is the subject of the scheduler article.

Reading span off the recursion

Fork-join algorithms usually arrive as recurrences, and the two quantities separate cleanly:

W(n) = W(n₁) + W(n₂) + 1
D(n) = max(D(n₁), D(n₂)) + 1

Work adds across the branches; span takes the maximum, because the branches run concurrently but the join still waits for the slower one. Three examples show how much the answer varies:

• Reduction over n elements: W = n − 1, D = log₂ n. Parallelism grows linearly with n.
• Merge sort with a sequential merge: W = Θ(n log n), D = Θ(n), because the merge is a serial chain over the output. Parallelism is only Θ(log n), so a merge sort on this shape stops scaling at a few dozen processors however many cores are available.
• Dense n×n matrix multiplication: Θ(n³) work; each of the n² outputs sums n products, and if those sums are formed as trees and the outputs are independent, the span is Θ(log n) up to blocking details, giving parallelism Θ(n³/log n).

The pattern generalises: an algorithm with polylogarithmic span and near-linear work scales; one with linear span is sequential no matter how the loop is written. Parallelising a merge, a scan, or a partition is therefore the recurring technical problem in parallel algorithm design, and the work-efficiency question is always the second half of it: a parallel algorithm that does asymptotically more work than the best sequential one has to beat it by a factor that grows with n before it wins at all.

A DAG written as code

#include <thread>

// Sum a[lo..hi). Work n-1 additions; span ceil(log2 n) plus spawn costs.
long par_sum(const long* a, int lo, int hi, int cutoff) {
    if (hi - lo <= cutoff) {              // sequential cut-off bounds overhead
        long s = 0;
        for (int i = lo; i < hi; ++i) s += a[i];
        return s;
    }
    int mid = lo + (hi - lo) / 2;
    long left;
    std::thread t([&] { left = par_sum(a, lo, mid, cutoff); });
    long right = par_sum(a, mid, hi, cutoff);
    t.join();
    return left + right;                  // this addition depends on both halves
}

The join is the graph edge: the final addition cannot execute until both halves have finished. The cut-off is what keeps the model honest. Without it, W includes one task per element and the per-task overhead — tens to hundreds of cycles for a deque push in a work-stealing runtime, tens of thousands for creating an operating-system thread as the code above does — dwarfs the arithmetic. Choosing that threshold is the granularity problem, and it is where the unit-cost assumption first breaks.

Note also what the code does not do: it assumes a is not concurrently modified. If another thread wrote to the array during the sum, the accesses would be unsynchronised, the value read by each node would depend on interleaving, and the DAG would not describe the execution at all. What that costs, and how it differs from a merely schedule-dependent result, is taken up in the memory-model article.

Where the model stops being true

Three assumptions are load-bearing, and each fails on real hardware.

Unit cost. A node that misses to DRAM costs hundreds of cycles rather than one, and two nodes on different cores may contend for the same cache line. A parallel algorithm can therefore have ideal W and D and still run slower than its sequential counterpart at small n.

Free spawn. The model charges one step for creating a task and nothing for a scheduler decision. Real runtimes charge both, which is why the DAG that matters is the one after cut-offs have been applied, not the source-level recursion.

Fixed graph. The DAG is derived from the program and its input. For data-dependent algorithms such as graph search, sparse factorisation, and branch-and-bound, the graph changes with the data, so W and D computed for one input say little about another. The usual response is to state the bounds for the worst case and accept that the common case may have far less parallelism.

The model survives all three because it gives a lower bound. If W/D is small, no implementation will scale, whatever the constant factors or the memory system. Where the model and the hardware disagree is in the cost of moving data, which is why the PRAM gap and communication volume are the necessary corrections rather than optional refinements.