13. The Cilk Runtime System

What this lecture covers

Earlier lectures taught you to write and reason about Cilk programs using spawn, sync, and cilk_for, and to analyze their work and span. This lecture opens the runtime system itself and asks how those three keywords actually turn into scheduling and load balancing on real hardware. It follows the Cilk compiler and the libcilk-rts runtime library as they cooperate to implement work stealing.

By the end, you can explain why a single worker executes Cilk code almost like ordinary serial code, how a thief processor jumps into the middle of a function another processor was running, why Cilk needs a "cactus stack" instead of one shared call stack, and how a sync statement waits only on its own nested subcomputations rather than stalling the whole program.

Key ideas

• Work-first principle: the runtime optimizes the ordinary serial execution path, even if that makes steals (the rare case) more expensive.
• Deque (worker queue): each worker keeps a deque of stack frames, separate from the call stack, with head and tail pointers; the worker pushes and pops from the tail, and thieves steal from the head.
• Spawn helper function: the compiler splits a spawning function into the original function plus a generated "spawn helper" that performs the actual spawned call and stores its result.
• Cilk RTS stack frame: a small structure added as a local variable to spawning functions and spawn helpers, holding a setjmp context buffer, a flags field, and a parent pointer.
• setjmp/longjmp: setjmp saves the instruction pointer, stack pointer, and callee-saved registers before a spawn; a thief later uses longjmp on that saved buffer to resume execution as if returning from setjmp a second time, skipping the spawned call and falling into its continuation.
• THE protocol: the concurrency protocol guarding deque access; the owning worker optimistically pops from the tail without locking, only falling back to acquire a lock when that pop appears to fail; a thief always locks first.
• Cactus stack: because a thief cannot safely reuse the victim's call stack (function calls would corrupt it), the thief runs on its own stack but points its base pointer at the victim's frame, giving every worker a consistent view of shared ancestor frames without sharing storage for calls made underneath them.
• Full frames: a tree of runtime structures, separate from Cilk RTS stack frames, that tracks outstanding (suspended) subcomputations so a sync can wait only on its own children.

Walkthrough

Required functionality and the fib example (6:05)

Using the recursive Fibonacci program, the lecture traces execution as more processors join: the first processor runs serially until a spawn, then dives into the newly spawned call; idle processors steal the leftover continuation and jump straight into a function already in progress. This raises the lecture's core questions: how does a thief resume a function it didn't start, how does sync wait on only the right subcomputations, and how does the system give every worker a consistent view of the stack (the cactus stack)? A quick aside notes that hardware cache coherence, not the runtime, handles memory consistency; cilk_for is compiled into spawns and syncs by the compiler.

Performance goals: work-first principle (21:13)

The lecture revisits the work-stealing running-time bound, T_P proportional to T1/P plus the span, and splits it into time spent doing useful work versus time spent stealing. To get near-linear speedup relative to the original serial program, you need both ample parallelism (T1/T_infinity much greater than P) and high work efficiency (serial running time close to the parallel work T1). The runtime's design choice follows directly: optimize the common serial path even at some cost to the rarer steal path.

Implementing the worker deque (27:20)

Using a small running example (foo spawns bar, then calls baz, then syncs), the lecture shows the compiler-generated C code: a spawning function and a separate spawn helper, each carrying a Cilk RTS stack frame. It walks the fields of that frame (context buffer, flags, parent pointer) and of the worker structure (deque head/tail, pointer to the current stack frame), then traces, statement by statement, how enter_frame, setjmp, cilk_rts_detach, pop_frame, and leave_frame update these structures as foo spawns bar and later returns.

Stealing a continuation (49:40)

The lecture details the THE protocol for concurrent deque access, then shows a thief dequeuing a frame from the head, pointing its current-stack-frame pointer at it, and using longjmp on the saved setjmp buffer to resume execution exactly at the spawn's continuation, with the right registers restored.

The cactus stack (1:05:04)

Because a thief calling further functions on the victim's stack would corrupt frames the victim still needs, each worker needs its own stack. The lecture shows the trick: the thief sets its base pointer to the stolen frame (in the victim's stack) but its stack pointer to its own stack, so it can read shared ancestor state while pushing new frames safely on its own stack. This is also why the Cilk compiler disables the "omit frame pointer" optimization for functions with a stealable continuation.

Synchronization and full frames (1:12:07)

When a worker hits a sync with outstanding spawned subcomputations, it must not block; it becomes a thief while its frame persists so the pending subcomputation can later resume it. The runtime tracks this with a tree of "full frames" recording parent/child relationships and outstanding children, separate from the lighter Cilk RTS stack frames used for the fast path. The lecture animates how stealing propagates full frames down the tree and how, in the common case of no outstanding children, a sync is resolved cheaply using flag bits rather than the full protocol.

Before you watch

• Be comfortable with Cilk's spawn/sync/cilk_for model and computation DAGs, work, and span, from earlier lectures.
• Review the work-stealing scheduling bound and the idea of randomized work stealing.
• Recall the standard C calling convention, especially the roles of the base pointer and stack pointer.

Check your understanding

1. Why does the Cilk runtime optimize the ordinary serial execution path rather than the steal path?
2. Walk through what happens to the worker's deque and stack frame pointers when foo spawns bar.
3. Why can't a thief simply execute on the victim's call stack, and how does the cactus stack trick solve this?
4. How does longjmp let a thief resume a function's continuation without having executed the original setjmp call itself?
5. Why must a worker that hits a sync with outstanding children preserve its stack frame instead of discarding it?