Cilk

TLDR

Cilk is a C‑based runtime system that supports multi‑threaded parallel programming and has been used for protein folding, graphics rendering, backtrack search, and the award‑winning Socrates chess program. The paper documents the efficiency of Cilk’s work‑stealing scheduler through empirical and analytical evaluation. The authors evaluate the scheduler on real and synthetic workloads running on the CM5, Paragon, Power Challenge, and MIT Phish workstations. The results show that work and critical‑path metrics accurately model performance, allowing programmers to focus on reducing them, and that for fully strict programs the scheduler achieves optimal space, time, and communication bounds within a constant factor.

Abstract

Cilk (pronounced “silk”) is a C-based runtime system for multi-threaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that on real and synthetic applications, the “work” and “critical path” of a Cilk computation can be used to accurately model performance. Consequently, a Cilk programmer can focus on reducing the work and critical path of his computation, insulated from load balancing and other runtime scheduling issues. We also prove that for the class of “fully strict” (well-structured) programs, the Cilk scheduler achieves space, time and communication bounds all within a constant factor of optimal. The Cilk runtime system currently runs on the Connection Machine CM5 MPP, the Intel Paragon MPP, the Silicon Graphics Power Challenge SMP, and the MIT Phish network of workstations. Applications written in Cilk include protein folding, graphic rendering, backtrack search, and the *Socrates chess program, which won third prize in the 1994 ACM International Computer Chess Championship.