Cilk is a C-based runtime system for multithreaded parallel programming, designed to provide efficient and predictable performance. The paper documents the efficiency of Cilk's work-stealing scheduler, both empirically and analytically. It shows that the "work" and "critical path" of a Cilk computation can be used to accurately model performance, allowing programmers to focus on reducing these metrics. For "fully strict" programs, the scheduler achieves space, time, and communication bounds within a constant factor of optimal. Cilk runs on various parallel computing platforms, including the Connection Machine CMS MPP, Intel Paragon MPP, Silicon Graphics Power Challenge SMP, and the MIT Phish network of workstations. Applications developed using 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. The paper also describes the Cilk programming environment and implementation, the work-stealing scheduler, and empirical performance results for several applications. It demonstrates that Cilk achieves near-optimal performance, with nearly perfect linear speedup when the critical path is short compared to the average parallelism. Theoretical analysis shows that for "fully strict" programs, Cilk's scheduler is efficient in terms of space, time, and communication. The authors conclude by discussing future directions, including extending Cilk's capabilities to broaden its applicability while maintaining performance guarantees.Cilk is a C-based runtime system for multithreaded parallel programming, designed to provide efficient and predictable performance. The paper documents the efficiency of Cilk's work-stealing scheduler, both empirically and analytically. It shows that the "work" and "critical path" of a Cilk computation can be used to accurately model performance, allowing programmers to focus on reducing these metrics. For "fully strict" programs, the scheduler achieves space, time, and communication bounds within a constant factor of optimal. Cilk runs on various parallel computing platforms, including the Connection Machine CMS MPP, Intel Paragon MPP, Silicon Graphics Power Challenge SMP, and the MIT Phish network of workstations. Applications developed using 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. The paper also describes the Cilk programming environment and implementation, the work-stealing scheduler, and empirical performance results for several applications. It demonstrates that Cilk achieves near-optimal performance, with nearly perfect linear speedup when the critical path is short compared to the average parallelism. Theoretical analysis shows that for "fully strict" programs, Cilk's scheduler is efficient in terms of space, time, and communication. The authors conclude by discussing future directions, including extending Cilk's capabilities to broaden its applicability while maintaining performance guarantees.