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.
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: