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