Multithreaded Algorithms

By the end of this lesson you will be able to draw the computation dag of a multithreaded procedure, compute its work T₁, span T∞ and parallelism, run a greedy scheduler on P processors step by step (counting complete and incomplete steps) and check the bound T_P ≤ T₁/P + T∞, spot a determinacy race before it bites, and analyse pFib, matVec and its parallel-for loop, the two parallel matrix multiplications, binarySearch, and the parallel merge sort with pMerge. Everything runs from scratch: no threads knowledge assumed, and every dag, schedule and number below is computed live by JavaScript in this page.

Words you will meet (each is explained again where it first matters). Processor: one worker that can execute one instruction at a time (a cook in a kitchen). Serial code: one instruction after another. Parallel: several things at the same time on different processors. Strand: a stretch of ordinary instructions with no spawn, sync or return inside. Dag: directed acyclic graph, arrows and no loops. Work T₁, span T∞, parallelism T₁/T∞: how much total computing, how long the unavoidable chain is, and their ratio. Scheduler: the run-time manager that hands ready strands to free processors. Determinacy race: two parallel strands touching the same memory cell with at least one writing. You will also use ideas from C02 (merge sort, binary search), C04 (recurrences, the master theorem, matrix multiplication) and C24 (longest path in a dag).

0. The dynamic-multithreading model

Imagine a kitchen with several cooks (processors). A recipe is a list of steps, and some steps do not depend on each other: chopping onions and boiling water can happen at the same time, but you cannot serve the soup before both are done. A multithreaded algorithm is such a recipe: you mark which steps may happen at the same time, and a scheduler (the kitchen manager) hands ready steps to free cooks. You never say which cook does what.

Dynamic multithreading adds three keywords to ordinary pseudocode:

spawn in front of a procedure call: the parent may keep going while the child runs. "May", not "must": the scheduler decides.
sync: the parent waits until all children it spawned have returned. There is an implicit sync before every return.
parallel for: the loop iterations may run at the same time (the compiler turns it into a spawn tree, shown below).

Delete those keywords and you get the serialization: an ordinary serial algorithm that computes the same answer. The multithreaded program must be race-free for that to be true.

Small example. Suppose a task is "do A (3 time units), then at the same time do B (4 units) and C (2 units), then do D (1 unit) once both are finished". One cook needs 3 + 4 + 2 + 1 = 10 units (the work). With as many cooks as you like, the time is 3 + max(4, 2) + 1 = 8 units (the span), because B is the slower branch. So this task can never go more than 10/8 = 1.25 times faster, however many cooks you hire. (In the first player below the same task is written S(3,P(4,2),1) and shows work 12 and span 10, because the drawing adds a fork strand and a sync strand of cost 1 each.)

Strands, the computation dag, work, span and parallelism

The picture of one run is the computation dag (dag = directed acyclic graph: arrows, no loops). Each vertex is a strand, a stretch of instructions with no spawn/sync/return inside. In this lesson every strand is drawn as a circle numbered in serial execution order, with its cost written under it when it is more than 1. Four kinds of edge:

spawn edge (blue): from the strand that spawns to the first strand of the spawned child.
call edge (purple): from a strand to the first strand of an ordinary called child.
continuation edge (grey): to the next strand of the same procedure.
return edge (green, dashed): from a child's last strand to the parent's strand after the sync.

Three strands are in series if there is a path from one to the next (one must finish first) and in parallel otherwise. To practise, the three players below let you write a small parallel program as a formula: a number is one strand of that cost, S(A, B, ...) runs the parts one after another, and P(A, B) spawns A, calls B and syncs. A P node is drawn as a fork strand (cost 1, it spawns A and calls B) and a sync strand (cost 1). The player builds the dag strand by strand, then computes the work T₁ (sum of all costs), the span T∞ (the most expensive path, drawn in red) and the parallelism T₁/T∞, and finally the greedy schedule.

Composition laws (checked by the page against the dag on every run): in series both work and span add; in parallel work adds but span is the larger of the two spans (plus the two Θ(1) fork and sync strands in our drawing).

The same two composition rules as code (the page's drawing adds a fork strand and a sync strand to every parallel node, so S(3,P(4,2),1) has work 12 and span 10 instead of 10 and 8):

Input size → what's feasible. A dag with V strands and E edges gives work and span in Θ(V + E): V = 10⁶ is instant. But the dag of pFib(40) has about 10⁹ strands, so for big inputs get T₁ and T∞ from the recurrences instead of building the dag.

Work is not "the number of processors busy". A common slip is to add spans in parallel: P(3, 4) has span 4 (plus overhead), not 7. The other slip is to think a big dag must have a big span: pFib(30) has millions of strands but a span of only 60.

The span of a dag is its longest path, exactly the critical path of the longest-path-in-a-dag method (C24): process the strands in topological order and set finish(v) = cost(v) + max finish over predecessors. That takes Θ(V + E) time, and it is what dagWorkSpan in verify/c27.dart does. Because every strand runs a constant amount of instructions before the next parallel-control statement, the model ignores the cost of spawning itself; real schedulers add overhead, so coarsen the leaves.

Work T₁ = the sum of all strand costs (time on 1 processor). Span T∞ = the most expensive path through the dag (time on unlimited processors). Parallelism = T₁/T∞. Two laws for P processors: work law T_P ≥ T₁/P and span law T_P ≥ T∞. Speedup T₁/T_P is at most min(P, T₁/T∞).

The laws as code. Work law, span law, the best conceivable time and the largest possible speedup are one-liners (pFib(5) has T₁ = 29, T∞ = 10, so on 2 processors no run can beat 14.5):

Every dag example below is computed by a JavaScript implementation of the real procedure running inside this page: it builds the dag in serial order (one frame per strand), then computes T₁, T∞ and parallelism, then simulates the greedy scheduler on P processors (one frame per scheduling moment, showing which strand sits on which processor) and finally checks the bound. Strand costs are 1 unless the caption says otherwise; the scheduler is a simple list scheduler (lowest-numbered ready strand first, lowest-numbered free processor first).

0b. The greedy scheduler and its bound

A kitchen manager with P cooks follows one rule: never leave a cook idle while some dish is ready to be started. That is a greedy scheduler. It is not the smartest possible (it does not look ahead), but the greedy bound says it is never far from the best: it finishes within T₁/P + T∞. And since the best possible time is at least max(T₁/P, T∞), being within a factor 2 of it is guaranteed (the factor-2 corollary).

Small example. Five one-unit strands: strand 1 first, then strands 2, 3, 4 (all ready at once), then strand 5 needs all of them. Work T₁ = 5, span T∞ = 3. With P = 2 processors: time step 1 only strand 1 is ready (1 < 2, an incomplete step, one cook idles), step 2 has three ready strands so two run (a complete step), step 3 has one ready strand (strand 4, incomplete), step 4 strand 5 (incomplete): total 4 steps. The bound says at most 5/2 + 3 = 5.5, and 4 ≤ 5.5.

Call a time step complete if at least P strands are ready (every processor works) and incomplete if fewer are ready (a greedy scheduler then runs all of them). The proof of the greedy bound has two halves, and the player shows both as live counters:

A complete step does P units of work, so there can be at most ⌊T₁/P⌋ of them.
In an incomplete step all ready strands run, and every strand at the start of a longest remaining path is ready, so the remaining span (the longest path among the unfinished strands) drops by exactly 1. So there are at most T∞ incomplete steps. The player prints the remaining span before and after every step.

Add the two counts: T_P ≤ T₁/P + T∞. In this section every strand costs 1 so each time step is one unit; the dags in the player are written as a list of arrows u>v (strand u must finish before v), with strands numbered so that every arrow goes to a larger number. The first example is a 14-strand fork-join dag with a wide first stage, a three-way join and a final pair of branches.

The greedy guarantee, the slackness and the factor-2 corollary as code, with the scheduler that produced the numbers of the players (a list scheduler with strand costs; P = 1 returns T₁, many processors return T∞):

Input size → what's feasible. Simulating the greedy schedule is Θ(V + E) tracking plus the sorting of ready strands: V ≤ 24 in the player, V = 2000 in the Dart panel above (well under a second), V = 10⁶ needs a heap for the ready list.

When "optimising" backfires, computed. A renderer has work T₁ = 3000 ms and span T∞ = 2 ms. An "optimised" version halves the work but adds a serial set-up step: T₁′ = 1800 ms and T∞′ = 11 ms. Using T_P ≈ T₁/P + T∞ (the greedy bound, a good estimate in practice):

The same numbers as code: with the greedy bound as an estimate the "optimised" version wins on 16 processors (123.5 against 189.5) and loses on 512 (14.5 against 7.9):

The bound is an upper bound guarantee for a greedy scheduler, not the exact running time. A real run is between max(T₁/P, T∞) and T₁/P + T∞; the player's greedy time landed between the two. Do not report "T_P = T₁/P + T∞" as a measurement.

Greedy scheduler: T_P ≤ T₁/P + T∞, so it is within a factor 2 of optimal, and when the slackness (T₁/T∞)/P is at least about 10 the time is nearly T₁/P: perfect linear speedup.

1. The basics of dynamic multithreading

pFib

Fibonacci by recursion: to get F(n) ask two helpers for F(n-1) and F(n-2) and add. With spawn, you hand the first question to a helper and start on the second yourself, then sync (wait for the helper) and add.

Small example. pFib(2) spawns pFib(1) (returns 1) and calls pFib(0) (returns 0). The parent has 3 strands (A: test and spawn, B: the call, C: sync and add) and each base call is 1 strand, so work = 3 + 1 + 1 = 5. The longest chain is A, then B, the call, then C: 4 strands, so span 4. pFib(5) has work 29 and span 10.

The two calls are independent (they share no variables), so it is safe. The serial version has running time T(n) = T(n-1) + T(n-2) + Θ(1) = Θ(φⁿ) with φ = (1+√5)/2 ≈ 1.618. Because we do the same work as the serial code, work is Θ(φⁿ). The span follows the longer of the two branches: T∞(n) = max(T∞(n-1), T∞(n-2)) + Θ(1) = T∞(n-1) + Θ(1) = Θ(n). So the parallelism is Θ(φⁿ/n), which grows very fast.

Dart is 0-indexed but this procedure has no arrays, so the code is identical to the pseudocode with the keywords deleted. The play button steps through the dag strand by strand. Each non-base call has 3 strands: A (test and spawn), B (the call), C (sync and add). For n = 5 that gives 29 strands and a longest path of 10.

Analysis table computed from the dags on this page (work, span, parallelism). Span is exactly 2n for n ≥ 2 and work grows by a factor of about φ each step. This is the cost table behind the recurrences: the work column follows W(n) = W(n-1) + W(n-2) + 3 and the span column S(n) = S(n-1) + 2.

Growth made visible in Dart: the work ratio between consecutive n tends to φ ≈ 1.618, the span gains exactly 2, and parallelism = work/span explodes:

Input size → what's feasible. n ≤ 30 (2F₃₁ − 1 ≈ 2.7·10⁶ calls) runs in a blink even serially; n = 50 needs 2F₅₁ − 1 ≈ 4.1·10¹⁰ calls, so parallelism cannot rescue a φⁿ algorithm: use the Θ(n) loop for big n.

Spawning does not create a thread that must run at once. If you run pFib on 1 processor the spawned child simply runs first and you get the serial execution. Speedup can never exceed P, and never exceeds the parallelism T₁/T∞ either.

pFib: work Θ(φⁿ) (same as serial FIB), span Θ(n), parallelism Θ(φⁿ/n). It is a teaching example, not a fast way to compute Fibonacci numbers (fast doubling and matrix powers are far faster).

matVec and matVecMainLoop: parallel loops

Handing out n homework sheets to a class: instead of the teacher walking to every desk in turn, she splits the pile in half, gives one half to a helper who splits again, and so on. It takes about lg n rounds of splitting, not n.

Small example. Rows 0..3 of a matrix must each produce one entry of y. matVecMainLoop(…, 0, 3) has i ≠ i2 so mid = 1: it spawns rows 0..1 and calls rows 2..3; each of those splits once more into single rows (i = i2), and a single row runs the serial j loop. So the tree has depth 2 = lg 4.

parallel for i in 0 .. n − 1 is compiled into a divide-and-conquer spawn tree. The strand that splits is drawn as a divide strand (spawn the left half, call the right half) and after both halves return a sync strand joins them. matVec first sets y[i] = 0 in one parallel for (lines 3-4), then the main loop is a second parallel for over the rows i (lines 5-7), and each row does a serial inner loop over j costing n. Work is Θ(n²) (the spawn tree has n leaves and n-1 internal nodes, so its overhead is only Θ(n)). Span is Θ(lg n) for each tree plus Θ(n) for the slowest row, so Θ(n) and the parallelism is Θ(n). In general, a parallel for of n iterations has span Θ(lg n) + the span of the slowest iteration.

First the full matVec (the two parallel loops and the return), then the auxiliary loop matVecMainLoop alone.

Cost tables computed from the dags: matVec (both loops plus return) and matVecMainLoop alone. Doubling n multiplies work by about 4 and span by about 2.

A parallel for over m iterations as a spawn tree: every internal node is a divide strand plus a sync strand (2 strands), so work is 2(m − 1) + m·(leaf cost) and span is 2⌈lg m⌉ + leaf. Dividing by the claimed order shows matVec is Θ(n²) work and Θ(n) span:

Input size → what's feasible. n ≤ 10⁴ gives n² = 10⁸ multiply-adds (about a second serially, so splitting the rows over cores helps); n = 10⁵ would be 10¹⁰ operations and an 80 GB matrix, which no loop structure fixes.

Do not also parallelise the inner j loop of the matrix-vector product: every j iteration writes to the same y[i], which is a determinacy race (next section, matVecWrong).

A parallel for of n iterations costs Θ(lg n) extra span for the spawn tree and Θ(n) extra work. matVec: work Θ(n²), span Θ(n), parallelism Θ(n).

raceExample and matVecWrong: determinacy races

Two people share a notepad with the number 0 written in it, and each is told "read the number, add 1 in your head, write the result". If they do it one after the other the notepad says 2. If both read 0 before either writes, both write 1, and one increment vanishes.

Small example. Interleaving A₁ A₂ A₃ B₁ B₂ B₃ (A entirely first): A reads 0, adds, writes 1; B reads 1, adds, writes 2. Correct. Interleaving A₁ B₁ A₂ B₂ A₃ B₃: both read 0, both write 1. Wrong. Of the 20 ways to interleave two strands of 3 steps, only 2 are right (below).

A determinacy race exists when two logically parallel strands touch the same memory location and at least one writes. The program x = 0; parallel for i in 0 .. 1: x = x + 1 looks harmless, but x = x + 1 is really three machine steps: read x into a private register, increment the register, write it back. Any interleaving of the two strands' three steps is possible, and the scheduler picks one, so the answer depends on luck. This is why the chapter requires parallel strands to be independent. Real disasters (the Therac-25 radiation machine, the 2003 North-American blackout) trace back to races.

matVecWrong (a tempting but faulty version) parallelises the inner loop too, to get span Θ(lg n): parallel for j updates the same y[i] from n strands at once. The three players below run two of those j strands, with a_i1·x_1 = A's term and a_i2·x_2 = B's term, and show y[i] after every interleaving step. The correct sum is the two terms added; a lost update leaves only one of them.

matVecWrong as code: two parallel for j iterations A and B add their terms into the same y[i]. Only 2 of the 20 interleavings give a + b, whatever the terms:

Input size → what's feasible. A race does not depend on size: 2 strands × 3 steps have 20 interleavings, 3 × 3 have 1,680 and 4 × 4 have 63,063,000, so testing cannot enumerate them and you must reason that parallel iterations write different cells.

Races do not only appear between the two obvious strands: spawn evaluates the child's arguments in the parent before the spawn, but anything the parent does after the spawn and before the sync is logically parallel with the child. Reading a spawned child's result before sync is a race too.

A race with the same value written can be harmless (two strands both storing 5), and locks or atomic instructions can make a racy program correct. This lesson deliberately avoids all that: strands that run in parallel must simply be independent, so that the program equals its serialization.

A race is not a slowdown, it is a wrong (or sometimes-wrong) answer. It can pass every test and still fail in production, because it only appears for particular interleavings.

2. Multithreaded matrix multiplication

pSquareMatrixMultiply

To fill an n×n table of answers, every cell c[i][j] is its own little job: a dot product of row i of A with column j of B. The n² jobs do not affect each other, so give them all to different cooks. Each job itself is a serial loop of n multiply-adds.

Small example. For n = 2 the four cells c[0][0], c[0][1], c[1][0], c[1][1] are independent jobs. Each is "set to 0, then 2 multiply-adds", cost n + 1 = 3. The outer loop splits rows 0..1 into row 0 and row 1, and each row splits its two columns: 3 divide-or-sync strands per level of the trees, plus 4 heavy leaf strands.

Take the triple loop and make the outer two loops parallel for; keep the inner k loop serial (parallelising it would race on c[i][j]). Work is Θ(n³), the same as the serial algorithm. Span is Θ(lg n) + Θ(lg n) + Θ(n) = Θ(n), because of the serial k loop. Parallelism Θ(n³)/Θ(n) = Θ(n²). The dags show an outer spawn tree, an inner spawn tree under every outer leaf, and a heavy leaf strand (cost n+1) for each (i,j).

Cost table computed from the dags. The work column is dominated by the n² leaves of cost n + 1; the span column by one leaf plus the two spawn-tree depths.

Growth as code (work/n³, span/n and parallelism/n² each settle near a constant):

Input size → what's feasible. n ≤ 500 (n³ = 1.25·10⁸) is fine; n = 5000 is 1.25·10¹¹ multiply-adds, still minutes even on 16 cores, so use cache blocking or Strassen instead of a bigger machine.

Making the k loop a parallel for as well looks like it would give span Θ(lg n), but every k iteration adds into the same c[i][j]: a race. The correct fix (see the interview question on log-span matrix multiply) sums the n products with a divide-and-conquer reduction into temporary storage.

pSquareMatrixMultiply: work Θ(n³), span Θ(n), parallelism Θ(n²).

pMatMulRecursive

Split each matrix into four quarters. The product needs eight quarter-size products (each block of C is a sum of two of them). Give seven to helpers, do the eighth yourself, wait, then add the two halves of every block together, again with all cooks in parallel.

Small example. For n = 2 the quarters are single numbers: the eight products are eight multiplications of two numbers (one strand each), then the four sums c[i][j] + t[i][j] (a parallel for over 4 entries) finish the job. With c[0][0] = a[0][0]·b[0][0] + a[0][1]·b[1][0], one product lands in c00 and the other in t00; line 17 adds them.

It needs a temporary matrix t so that the two products for each block can be computed at the same time without both writing into c. Work: M₁(n) = 8·M₁(n/2) + Θ(n²) = Θ(n³) (master theorem case 1, C04). Span: the eight products run in parallel and the addition is a doubly-nested parallel for with span Θ(lg n): M∞(n) = M∞(n/2) + Θ(lg n) = Θ(lg² n) (this is not master-theorem shaped; unroll it instead). Parallelism Θ(n³/lg² n). To keep the drawings readable the dag uses a true base case n = 1 (one strand), so the drawable sizes are n = 1 and n = 2; n = 4 already has 208 strands. (A simplification: a faithful dag would chain the seven spawns of lines 6-12 through seven tiny continuation strands; the drawing fans all eight spawn/call edges out of one strand, which changes the work and the span only by constants.) The table extends the same recurrence to larger n.

Cost table: the first two rows are real dags, the rest use the same recurrences W(n) = 8 W(n/2) + Θ(n²) and S(n) = S(n/2) + Θ(lg n) (see mmW, mmS in the page and mmWork, mmSpan in verify/c27.dart). Watch the span grow by only a few dozen while the work grows by 8 each time n doubles.

Growth as code for n = 2^k: the work ratio per doubling tends to 8, span/lg²n settles, and parallelism = work/span grows enormously:

Input size → what's feasible. n a power of two with n ≤ 1024 (n³ ≈ 10⁹): the recursion has depth lg n ≤ 10; the temporary matrices cost Θ(n²) memory per level, so n = 10⁴ already strains memory.

Without the temporary matrix t, the eight products would need to add into the same four blocks of c: two spawned calls writing c00 at once is a race. The price of the temporary is Θ(n²) extra memory per level and the extra addition pass.

Multithreaded Strassen has the same shape: 10 sum/difference matrices in a parallel for (Θ(lg n) span), 7 spawned products, a parallel-for combination. Work Θ(n^{lg 7}), span Θ(lg² n), parallelism Θ(n^{lg 7}/lg² n): slightly less than pMatMulRecursive but with less total work.

pMatMulRecursive: work Θ(n³), span Θ(lg² n), parallelism Θ(n³/lg² n): far more parallel than pSquareMatrixMultiply, at the cost of a temporary matrix.

3. Multithreaded merge sort

mergeSortPrime: the naive parallel merge sort

Two friends sort half a deck each at the same time, but then one person merges the two sorted halves alone while the friend watches. However many friends you have, the last merge at the top of the recursion is a one-person job that takes n steps.

Small example. Sorting [3,1,2,4]: two halves [3,1] and [2,4] are sorted in parallel, each by another split; then a serial merge of 4 elements costs 4 on its own. That single strand of cost n is already on the critical path, however parallel everything below it is.

The naive version, mergeSortPrime, spawns one recursive call and then calls the ordinary serial merge. Work is Θ(n lg n), but the span is T∞(n) = T∞(n/2) + Θ(n) = Θ(n) because the serial merge is on the critical path, so the parallelism is only Θ(lg n). In the dags below merge is one strand of cost n. Compare the parallelism column with pMergeSort's further down: this is the number the whole section improves.

Input size → what's feasible. n = 10⁶ numbers: work n lg n ≈ 2·10⁷ is fine, but parallelism is only about lg n ≈ 20, so extra processors beyond ~20 sit idle; the serial merge is the bottleneck.

Spawning the recursion is not enough: parallelism is limited by the serial parts on the critical path. A quick sanity check of any parallel algorithm is to ask "which single step of cost Θ(n) is on the longest path?".

mergeSortPrime: work Θ(n lg n), span Θ(n), parallelism only Θ(lg n). The fix is a merge that is itself parallel: pMerge.

binarySearch (the serial helper of pMerge)

Looking a word up in a dictionary: open in the middle, see whether your word comes before or after, throw away the wrong half, repeat. Here the "dictionary" is a sorted array and the answer is not "found or not" but "the index where x would be inserted to keep the array sorted".

Small example. Sorted t = [1, 3, 5, 7, 9] (indices 0..4), x = 6, p = 0, r = 4. low = 0, high = 5. mid = 2: x ≤ t[2] = 5 is false, so low = 3. mid = 4: x ≤ 9 is true, so high = 4. mid = 3: x ≤ 7 true, so high = 3. low = high = 3, return 3: 6 belongs at index 3, between 5 and 7.

The procedure returns the first index q in [p, r+1] with x ≤ t[q] (or r + 1 if x is larger than everything, or p if the range is empty). It is serial, halves the window each time, and so takes Θ(lg n) work and span. pMerge uses it to split the smaller array at the value of the larger array's median.

The "Θ(lg n)" claim as code: count the passes and compare with ⌊lg n⌋ + 1, which is n.bitLength in Dart:

Input size → what's feasible. n = 10⁹ sorted values need at most 30 probes; a linear scan would need up to 10⁹ steps, far too slow for many queries.

This binarySearch returns an insertion index, and high starts at max(p, r + 1), one past the last cell. Writing r instead makes the search unable to answer "after everything". With duplicates it returns the first index whose value is ≥ x (x ≤ t[mid] moves high, never low).

The loop invariant: every index below low holds a value < x, and every index at or above high holds a value ≥ x (or lies beyond the range). The window t[low..high-1] shrinks by at least half each pass, so the loop runs at most ⌊lg n⌋ + 1 times (each player prints the actual count against this bound).

binarySearch: Θ(lg n) time, serial; returns the insertion point. Work and span of the call are both Θ(lg n).

pMerge

To merge two sorted piles, take the middle card x of the bigger pile. Everything left of x in its pile is smaller than x. Use binary search to find where x fits in the other pile: that also splits the other pile. Now x has a known final position, and the two sides (smaller-than-x cards, larger-than-x cards) can be merged completely independently, by different helpers.

Small example. Merge [2,4,7,9] and [1,3,5,6,8]. The bigger pile is the second one; its median is 5 (index 2 of that pile). binarySearch in [2,4,7,9] puts 5 after 2 and 4 and before 7, so 5 lands at output index 2 + 2 = 4. Merge {1,3} with {2,4} on the left and {6,8} with {7,9} on the right, at the same time.

Precisely (n₁ ≥ n₂ after swapping): q₁ is the median of the larger array, q₂ comes from binarySearch (Θ(lg n)), q₃ = p₃ + (q₁−p₁) + (q₂−p₂) is where x lands in the output a. The two recursive merges are spawn + call. Because the larger array is halved and x's insert point splits the smaller one, each recursive call has at most 3n/4 elements, so the span is PM∞(n) = PM∞(3n/4) + Θ(lg n) = Θ(lg² n). The work satisfies PM₁(n) = PM₁(αn) + PM₁((1−α)n) + O(lg n) with 1/4 ≤ α ≤ 3/4 and solves to Θ(n) (substitution method). Parallelism Θ(n/lg² n). In the dag a strand that does the binary search costs 1 plus the number of probes.

Why at most 3n/4? After swapping, the larger array has n₁ ≥ n/2 elements. Its median leaves ⌊n₁/2⌋ ≤ n₁/2 on the left and at most n₁/2 on the right, and the smaller array (n₂ ≤ n₁) can send all of its elements to one side. So one recursive call gets at most n₁/2 + n₂ ≤ n₁/2 + (n − n₁) = n − n₁/2 ≤ 3n/4. The table below shows the actual sizes of the two recursive merges for hand-picked and for 5000 pseudo-random pairs.

Cost table computed from real pMerge dags on two interleaved sorted arrays of n numbers each: the work stays close to linear in n, the span grows like lg² n (a few strands per binary-search probe on the longest path).

The two claims about pMerge as code: work and span for interleaved lists of n numbers (work/(2n) and span/lg²n stay bounded), and the 3/4 rule (no recursive call gets more than 3n/4 elements):

Input size → what's feasible. n = 10⁶ elements: work is about 10⁶·c, span about lg²(10⁶) ≈ 400, so parallelism is about 2,500: pMerge keeps thousands of processors busy, where a serial merge cannot use more than one.

Taking the median of the smaller array instead would let one side keep almost everything (a chain of nearly-empty splits, span Θ(n)); that is why lines 2-4 swap so that array 1 is the larger. Also, binarySearch must search the other array, over its own range p₂..r₂, not the whole t.

pMerge: work Θ(n), span Θ(lg² n), parallelism Θ(n/lg² n). Median of the larger array + binary search in the smaller = two independent merges of ≤ 3n/4 elements.

pMergeSort

Sort a deck by cutting it in two, giving one half to a helper, sorting the other half yourself, waiting, and then merging the two sorted halves with the team-merge above.

Small example. Sort [5,2,4,1]: spawn pMergeSort on [5,2] and call it on [4,1]; each splits again into singles and merges with pMerge, giving [2,5] and [1,4]; the sync waits; then pMerge combines them into [1,2,4,5].

Work is the same recurrence as serial merge sort, PMS₁(n) = 2·PMS₁(n/2) + Θ(n) = Θ(n lg n). Span: PMS∞(n) = PMS∞(n/2) + Θ(lg² n) = Θ(lg³ n). Parallelism Θ(n lg n)/Θ(lg³ n) = Θ(n/lg² n), an exponential improvement over mergeSortPrime's Θ(lg n). In practice you stop recursing at a coarse base case and use a fast serial sort there. In the dags below, each merge is drawn with the real pMerge strands from the previous section (their captions say "inside pMerge").

The span recurrence as a table. Unrolling PMS∞(n) = PMS∞(n/2) + lg²(n) for n = 1024 adds the merge span of one level per row (constants dropped): 10² + 9² + … + 1² = 385, and lg³(1024)/3 ≈ 333, so the total is Θ(lg³ n). The work column shows every level doing about n work, hence n lg n in total.

mergeSortPrime against pMergeSort, computed from the dags: the same sort, with the serial merge (one strand of cost n) against pMerge. Parallelism of the first grows like lg n, of the second like n/lg² n.

The sort's span recurrence and its parallelism as code, next to mergeSortPrime (strand-model numbers from the dags):

Input size → what's feasible. n = 10⁶: work n lg n ≈ 2·10⁷, span lg³n ≈ 7.9·10³, parallelism about 2,500. Below a few thousand elements the spawn overhead is larger than the work, so coarsen the base case (see the interview question on coarsening).

Line 10's pMerge needs the two halves fully sorted, so the sync on line 9 cannot be dropped: without it pMerge would read half-written data, a race.

pMergeSort: work Θ(n lg n), span Θ(lg³ n), parallelism Θ(n/lg² n). Coarsen the base case in practice.

Real parallelism in Dart, and Amdahl's law

The idealised model is a kitchen where all cooks share one big counter and a manager instantly hands out work. Dart's real parallelism is a set of separate kitchens (isolates) with no shared counter: you mail ingredients in (a copy) and mail the finished dish back. Nobody can spill on somebody else's bench, but mailing costs time.

The dag model is the ideal machine. Dart's real tool for parallel CPU work is the isolate, a worker with its own memory that talks by messages (see D15 · Isolates and Concurrency). Compare it with the idealised fork-join model:

Spawn / sync model	Dart isolates
Threads share one memory.	Each isolate has its own heap: arguments are copied in, results copied out (numbers, lists, strings are copyable).
A spawn costs about a function call.	Isolate.run costs milliseconds to start, so spawn only large chunks, near the top of the recursion (grain size).
A work-stealing scheduler balances strands, guaranteeing about T₁/P + T∞.	You choose the chunks; nothing rebalances them for you.
`sync` waits for the children.	`await` (or `Future.wait` for several) waits for the results.
Determinacy races are the main danger.	Isolates cannot race on shared memory, but async code on one isolate can still lose updates across an `await` (see the race panel above).

Because isolates share no memory, races on shared variables cannot happen; the price is copying the inputs. The panels below give the Dart equivalents: Isolate.run is spawn, await/Future.wait is sync. They are verified in verify/c27.dart and use a coarse cut-off, so they are not the fine-grained dags drawn above.

Wrapping every recursive call in Isolate.run would create thousands of isolates and be slower than the serial code. The model's "spawn is cheap" assumption is false for isolates; the fix is the coarsening described in the interview bank.

Amdahl's law. If a fraction f of the work is inherently serial, the speedup on P processors is at most 1/(f + (1−f)/P), and never more than 1/f however many processors you add. It is the same idea as the span law: the serial part is a critical path.

Amdahl's law as code, for a serial fraction f = 0.1 on 1, 10, 100 and 1000 processors (never above 1/f = 10):

Input size → what's feasible. Isolates pay off only when a chunk costs well over a millisecond (roughly 10⁵ or more simple operations); for n ≤ 10⁴ the serial loop wins.

Isolate.run ≈ spawn, await ≈ sync, but copy costs and start-up costs mean you parallelise big chunks, not single calls. Amdahl's 1/f and the span law say the same thing: the serial part limits speedup.

Quiz

Interview questions

Cheat sheet

Procedure	Work T₁ (best / avg / worst)	Span T∞	Parallelism	Space	When to use / note
pFib	Θ(φⁿ) all cases	Θ(n)	Θ(φⁿ/n)	Θ(n) stack	teaching example; work same as serial
matVec	Θ(n²) all cases	Θ(n)	Θ(n)	Θ(n) for y	rows in parallel, inner j loop serial
matVecMainLoop	Θ(n²)	Θ(n)	Θ(n)	Θ(lg n) spawn depth	how a parallel for is compiled
matVecWrong	Θ(n²)	Θ(lg n) but incorrect	none: racy	Θ(n)	never use; races on y[i]
pSquareMatrixMultiply	Θ(n³)	Θ(n)	Θ(n²)	Θ(n²) for C	simple, no temporary; k loop serial to avoid a race
pMatMulRecursive	Θ(n³)	Θ(lg² n)	Θ(n³/lg² n)	Θ(n²) temporaries per level	more parallelism; needs temporary T
mergeSortPrime (serial merge)	Θ(n lg n)	Θ(n)	Θ(lg n)	Θ(n)	serial merge is the bottleneck
binarySearch	Θ(1) best / Θ(lg n) worst	Θ(lg n)	1 (serial)	Θ(1)	insertion point in a sorted range; helper of pMerge
pMerge	Θ(n)	Θ(lg² n)	Θ(n/lg² n)	Θ(n) output, O(lg n) stack	binary search splits the smaller array
pMergeSort	Θ(n lg n)	Θ(lg³ n)	Θ(n/lg² n)	Θ(n) per level (T)	coarsen the base case in practice
Greedy scheduler	T_P ≤ T₁/P + T∞	-	-	-	within factor 2 of optimal; slackness ≥ 10 gives near-linear speedup

Laws: T_P ≥ T₁/P (work), T_P ≥ T∞ (span), greedy T_P ≤ T₁/P + T∞, speedup ≤ min(P, T₁/T∞), slackness = (T₁/T∞)/P (want ≥ 10). Composition: series adds work and span, parallel adds work and takes the max span. Spawn/sync/parallel for; parallel strands must be race-free.