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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
	2	Guy E. BIelloch. Programming parallel algorithms. In Proceedings of the 1992 Dartmouth Institute for Advanced Graduate Studies (DAGS) Symposium on Parallel Computation, pages 11- 18, Hanover, New Hampshire, June 1992.
	3	Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 356-368, Santa Fe, New Mexico, November 1994.
	4	Robert D. Blumofe and David S. Park. Scheduling large-scale parallel computations on networks of workstations. In Proceedings of the Third International Symposium on High Performance Distributed Computing, pages 96-105, San Francisco, California, August 1994.
	5	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	6	Eric A. Brewer and Robert Blumofe. Strata: A multi-layer communications library. Technical Report to appear, MIT Laboratory for Computer Science. Available as ftp: / / ftp. ics .mit. edu/pub/supertech/strata /strata. tar. Z.
	7	F. Warren Burton , M. Ronan Sleep, Executing functional programs on a virtual tree of processors, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.187-194, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806778]
	8	Martin C. Carlisle , Anne Rogers , John H. Reppy , Laurie J. Hendren, Early Experiences with Olden, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.1-20, August 12-14, 1993
	9	Rohit Chandra , Anoop Gupta , John L. Hennessy, COOL: An Object-Based Language for Parallel Programming, Computer, v.27 n.8, p.13-26, August 1994 [doi>10.1109/2.303616]
	10	J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.147-158, November 1989
	11	Eric C. Cooper and Richard R Draves. C Threads. Technical Report CMU-CS-88-154, School of Computer Science, Carnegie- Mellon University, June 1988.
	12	David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
	13	Ranier Feldmann , Peter Mysliwiete , Burkhard Monien, Studying overheads in massively parallel MIN/MAX-tree evaluation, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.94-103, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.192325]
	14	Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987 [doi>10.1145/22719.24067]
	15	Vincent W. Freeh, David K. Lowenthal, and Gregory R. Andrews. Distributed Filaments: Efficient fine-grain parallelism on a cluster of workstations. In Proceedings of the First Symposium on Operating Systems Design and Implementation, pages 201-213, Monterey, California, November 1994.
	16	R. L. Graham Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45:1563-1581, November 1966.
	17	R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416-429, March 1969.
	18	Michael Halbherr, Yuli Zhou, and Chris E Joerg. MIMD-style parallel programming with continuation-passing threads. In Proceedings of the 2nd International Workshop on Massive Parallelism: Hardware, Software, and Applications, Capn, Italy, September 1994.
	19	Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
	20	W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
	21	Wilson C. Hsieh , Paul Wang , William E. Weihl, Computation migration: enhancing locality for distributed-memory parallel systems, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.239-248, May 19-22, 1993, San Diego, California, United States
	22	Suresh Jagannathan , Jim Philbin, A customizable substrate for concurrent languages, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.55-81, June 15-19, 1992, San Francisco, California, United States
	23	Chris Joerg and Bradley C. Kuszmaul. Masswely parallel chess In Proceedings of the Third DIMACS Parallel Implementation Challenge, Rutgers University, New Jersey, October 1994. Available as ftp://theory.lcs.mit.edu /pub/cilk/dimacs 9 4. ps. Z.
	24	L. V. Kal6. The Chare kernel parallel programming system. In Proceedings of the 1990 International Conference on Parallel Processing, Volume II: Software, pages 17-25, August 1990.
	25	V. Karamcheti , A. Chien, Concert-efficient runtime support for concurrent object-oriented programming languages on stock hardware, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.598-607, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169806]
	26	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	27	Richard M. Karp , Yanjun Zhang, Randomized parallel algorithms for backtrack search and branch-and-bound computation, Journal of the ACM (JACM), v.40 n.3, p.765-789, July 1993 [doi>10.1145/174130.174145]
	28	D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
	29	Bradley C. Kuszmaul, Synchronized MIMD computing, Massachusetts Institute of Technology, Cambridge, MA, 1995
	30	Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
	31	Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165251]
	32	E. Mohr , D. A. Kranz , R. H. Halstead, Jr., Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.264-280, July 1991 [doi>10.1109/71.86103]
	33	Rishiyur S. Nikhil, A Multithreaded Implementation of Id using P-RISC Graphs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.390-405, August 12-14, 1993
	34	Rishiyur S. Nikhil, Cid: A Parallel, "Shared-Memory" C for Distributed-Memory Machines, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.376-390, August 08-10, 1994
	35	Vijay S. Pande, Christopher E Joerg, Alexander Yu Grosberg, and Toyolchi Tanaka. Enumerations of the hamiltonian walks on a cubic sublattice. Journal of Physics A. 27, 1994.
	36	Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
	37	Larry Rudolph , Miriam Slivkin-Allalouf , Eli Upfal, A simple load balancing scheme for task allocation in parallel machines, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.237-245, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113401]
	38	V. S. Sunderam, PVM: a framework for parallel distributed computing, Concurrency: Practice and Experience, v.2 n.4, p.315-339, Dec. 1990 [doi>10.1002/cpe.4330020404]
	39	Andrew S. Tanenbaum, Henri E, Bal, and M. Frans Kaashoek. Programming a distributed system using shared objects. In Proceedings of the Second International Symposium on High Performance Distributed Computing, pages 5-12, Spokane, Washington, July 1993.
	40	Mark T. Vandevoorde , Eric S. Roberts, Workcrews: an abstraction for controlling parallelism, International Journal of Parallel Programming, v.17 n.4, p.347-366, Aug. 1988 [doi>10.1007/BF01407910]
	41	I-Chen Wu , H. T. Kung, Communication complexity for parallel divide-and-conquer, Proceedings of the 32nd annual symposium on Foundations of computer science, p.151-162, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185364]

Collaborative Colleagues:

Robert D. Blumofe: colleagues

Christopher F. Joerg: colleagues

Bradley C. Kuszmaul: colleagues

Charles E. Leiserson: colleagues

Keith H. Randall: colleagues

Yuli Zhou: colleagues