%0 Conference Paper %1 Cilk %A Blumofe, Robert D. %A Joerg, Christopher F. %A Kuszmaul, Bradley C. %A Leiserson, Charles E. %A Randall, Keith H. %A Zhou, Yuli %B Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) %C New York, NY, USA %D 1995 %I ACM %K Concurrency PhD Proposal SharedMemory %N 8 %P 207--216 %R 10.1145/209937.209958 %T Cilk: An Efficient Multithreaded Runtime System %V 30 %X 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.

@inproceedings{Cilk, 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.}, added-at = {2008-09-05T10:58:31.000+0200}, address = {New York, NY, USA}, author = {Blumofe, Robert D. and Joerg, Christopher F. and Kuszmaul, Bradley C. and Leiserson, Charles E. and Randall, Keith H. and Zhou, Yuli}, biburl = {https://www.bibsonomy.org/bibtex/26f3f007e1676c1744cd2fe8f239f0be6/gron}, booktitle = {Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)}, description = {Cilk}, doi = {10.1145/209937.209958}, interhash = {a967789c2d187c4c501b5dc343f7fc3d}, intrahash = {6f3f007e1676c1744cd2fe8f239f0be6}, issn = {0362-1340}, keywords = {Concurrency PhD Proposal SharedMemory}, month = {July}, number = 8, pages = {207--216}, publisher = {ACM}, timestamp = {2013-12-04T16:54:41.000+0100}, title = {Cilk: An Efficient Multithreaded Runtime System}, volume = 30, year = 1995 }