Lecture 7: Races and Parallelism

What this lecture covers

This lecture develops the formal tools for reasoning about parallel programs written in Cilk: how to detect and avoid determinacy races, and how to measure how much parallelism a program actually has. It builds directly on the previous lecture's introduction to Cilk's cilk_spawn, cilk_sync and cilk_for constructs and the four concurrency platforms.

After watching, you should be able to explain what a determinacy race is and why it doesn't always reproduce, model a Cilk program's execution as a computation DAG, compute its work and span, use those quantities to bound achievable speedup, and describe how Cilk's greedy and work-stealing schedulers achieve near-linear speedup when there is enough parallel slackness.

Key ideas

• Determinacy race: two logically parallel instructions access the same memory location and at least one writes it; the result can differ depending on execution order, and the bug may not appear on every run.
• Read race vs. write race: a race is a read race if one instruction reads and the other writes; a write race if both write. Two code sections are independent if no such races exist between them.
• Computation DAG: a directed acyclic graph of strands (sequential instruction runs with no spawn, sync or return) connected by spawn, call, return and continue edges, built dynamically as a Cilk program executes.
• Work (T1): total time to run the computation on one processor, equal to the number of nodes (strands) in the DAG.
• Span (T∞): the length of the longest path through the DAG, equal to the execution time on an unbounded number of processors.
• Parallelism: T1 / T∞, the theoretical maximum speedup achievable regardless of processor count.
• Work law and span law: TP ≥ T1/P and TP ≥ T∞, which bound achievable running time on P processors.
• Greedy scheduler bound: any greedy scheduler achieves TP ≤ T1/P + T∞, within a factor of two of optimal, and gives near-linear speedup when parallel slackness (T1 / (P·T∞)) is high.
• Work stealing: Cilk's scheduler, where an idle worker steals from the top of a random other worker's deque; expected running time is T1/P + O(T∞).

Walkthrough

Recap of Cilk constructs and race avoidance tips (1:02)

The lecture reviews cilk_spawn/cilk_sync and cilk_for from the prior lecture, then lists rules for avoiding races: iterations of a cilk_for must be independent, and code between a spawn and its matching sync must be independent of the parent's code. It notes that a spawned function's arguments are safely evaluated by the parent before the spawn, and warns that races can appear in packed structs on some architectures (though not on the Intel machines used in the course).

Determinacy races (4:06)

Using real-world examples (the Therac-25 radiation machine and the 2003 North American blackout), the lecture defines a determinacy race and works through a concrete example: two parallel loop iterations each incrementing a shared variable x via load-increment-store, which can interleave to produce a wrong final value. It distinguishes read races from write races and introduces the Cilksan race detector (-fsanitize=cilk), which is guaranteed to report any possible race, unlike best-effort detectors.

Computation DAGs (18:20)

The Fibonacci example from the previous lecture is unfolded step by step into a computation DAG, with spawn edges producing two children (a spawned child and a continuation), call edges producing one child, and return edges passing results back up. The DAG is built dynamically at runtime and is processor-oblivious — nothing in the code or graph mentions the number of processors.

Work, span and Amdahl's law (26:28)

Assuming each strand takes unit time, the lecture first applies Amdahl's law to the example DAG (18 nodes, 3 forced-sequential nodes) to get a loose speedup bound of 6, then introduces the tighter work/span framework: work T1 (18), span T∞ (9), giving parallelism T1/T∞ = 2. It states and justifies the work law and span law, and shows how work and span compose under series and parallel composition of subcomputations.

Speedup types and Cilkscale (38:05)

The lecture defines sub-linear, linear and (in theory, impossible under this model) super-linear speedup, applies the work/span analysis to the Fibonacci DAG (work 17, span 8, parallelism 2.125), and introduces Cilkscale, the Cilk tool that instruments a serial run to report work and span and generate speedup-bound plots. A parallel quicksort example, where the partition step runs sequentially, is analyzed to show its span is Θ(n) and parallelism only Θ(log n) — much lower than a fully parallel implementation would achieve.

Scheduling theory: the greedy scheduler (53:28)

The lecture introduces a centralized greedy scheduler that, at each step, executes as many ready strands as possible (a complete step) or all ready strands (an incomplete step) up to the processor count. Graham's 1968 theorem bounds its running time as TP ≤ T1/P + T∞, proved by bounding the number of complete steps by T1/P and incomplete steps by T∞. Corollaries show the greedy scheduler is within 2x of optimal and achieves near-linear speedup when parallel slackness is at least around 10.

Cilk's work-stealing scheduler and cactus stacks (1:02:40)

Cilk's actual scheduler is a distributed work-stealing scheduler: each worker keeps a deque of ready strands, working from the bottom like a normal call stack, and an idle worker steals from the top of a random victim's deque. Its expected running time is T1/P + O(T∞). A sketch proof relates the expected number of steals to the span. The lecture closes by describing Cilk's "cactus stack," which lets each task see its own stack frame and those of its ancestors, and bounds the total stack space of a P-processor execution by P times the single-processor stack space.

Before you watch

• Watch the previous lecture on multicore programming and Cilk basics (cilk_spawn, cilk_sync, cilk_for), since this lecture assumes familiarity with that syntax and the Fibonacci example.
• Comfort with recursion and basic graph terminology (DAG, path length) will help with the computation-DAG analysis.

Check your understanding

1. Why can a determinacy race bug fail to appear on most runs of a program, and why does that make it hard to find through testing?
2. In a computation DAG, what is the difference between work and span, and how do they combine to define parallelism?
3. Why does Amdahl's law give a looser (less useful) upper bound on speedup than the work/span analysis in the lecture's example?
4. Why did the parallel quicksort example achieve only Θ(log n) parallelism, and what change would increase it?
5. According to the greedy scheduler theorem, why does high parallel slackness (T1 / (P·T∞)) lead to near-linear speedup?