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
- Robert D. Blumofe
- Christopher F. Joerg
- Bradley C. Kuszmaul
- Charles E. Leiserson
- Keith H. Randall
- Yuli Zhou
References
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- PVM: A framework for parallel distributed computing
- The Parallel Evaluation of General Arithmetic Expressions
- MULTILISP: a language for concurrent symbolic computation
- Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine
- Data parallel algorithms
- Proceedings 35th Annual Symposium on Foundations of Computer Science
- Scheduler activations
- Scheduling multithreaded computations by work stealing