The Implementation of the Cilk-5 Multithreaded Language

by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall.

1998 ACM SIGPLAN Conference on Programming Language
2008 Most Influential PLDI Paper Award (for 1998)
[Full text]


The fifth release of the multithreaded language Cilk uses a provably good ``work-stealing'' scheduling algorithm similar to the first system, but the runtime system has been completely reengineered. The efficiency of the new implementation was aided by a clear strategy that arose from a theoretical analysis of the scheduling algorithm: concentrate on minimizing overheads that contribute to the work, even at the expense of overheads that contribute to the critical path. Although it may seem counterintuitive to move overheads from the work of a computation to its critical path, this ``work-first'' principle has led to a portable Cilk-5 implementation in which the typical cost of spawning a parallel thread is only between 2 and 6 times the cost of a C function call on a variety of contemporary machines. Many Cilk programs run on one processor with virtually no degradation compared to equivalent C programs. This paper describes how the work-first principle was exploited in the design of Cilk-5's compiler and its runtime system. In particular, we present Cilk-5's novel ``two-clone'' compilation strategy and its Dijkstra-like mutual-exclusion protocol for implementing the ready deque in the work-stealing scheduler.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009