Cilk

Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul et al. · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · 1995

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.

Cited by 1,021 works. doi:10.1145/209936.209958 Open-access PDF

Authors

References