The Cilk runtime system

The Cilk concurrency platform uses a scheduler that decides at runtime how to schedule and execute logically parallel tasks on parallel processors. The Cilk scheduler offers several benefits that allow Cilk programs to execute efficiently in a variety of environments:

  • The Cilk scheduler executes a Cilk computation in a provably efficient manner.

  • In practice, the Cilk scheduler employs whatever parallel processors happen to be available at runtime, even in multiprogrammed environments.

  • The Cilk scheduler ensures that the parallel performance of a Cilk computation is composable: if two Cilk computations are executed simultaneously on the same system, then these computations will not oversubscribe the parallel processors on the system.

What is parallelism?

The parallelism of a Cilk program can be measured quantitatively in terms of two performance measures: work and span. Conceptually, for a deterministic parallel program, the work of a computation, denoted \(T_1\), corresponds to the running time of that program on a single processor. Meanwhile the span of a computation, denoted \(T_\infty\), corresponds to the running time of that program on a hypothetical machine with an infinite number of processors. The parallelism of a computation is the ratio of its work divided by its span, that is, \(T_1/T_\infty\). The parallelism identifies to the maximum number of parallel processors that the program could use to get parallel speedup.

The Cilk scheduler provides a mathematical guarantee to execute a Cilk computation with work \(T_1\) and span \(T_\infty\) on \(P\) processors in time \(T_P \leq T_1/P + O(T_\infty)\). Using this scheduler, if the Cilk computation exhibits ample parallelism — where \(P \ll T_1/T_\infty\) — then the Cilk scheduler executes the computation with linear speedup, meaning that the computation runs on \(P\) processors in time \(T_P \approx T_1/P\).

Last updated: