A scheduling framework for general-purpose parallel languages

ABSTRACT

The trend in microprocessor design toward multicore and manycore processors means that future performance gains in software will largely come from harnessing parallelism. To realize such gains, we need languages and implementations that can enable parallelism at many different levels. For example, an application might use both explicit threads to implement course-grain parallelism for independent tasks and implicit threads for fine-grain data-parallel computation over a large array. An important aspect of this requirement is supporting a wide range of different scheduling mechanisms for parallel computation.

In this paper, we describe the scheduling framework that we have designed and implemented for Manticore, a strict parallel functional language. We take a micro-kernel approach in our design: the compiler and runtime support a small collection of scheduling primitives upon which complex scheduling policies can be implemented. This framework is extremely flexible and can support a wide range of different scheduling policies. It also supports the nesting of schedulers, which is key to both supporting multiple scheduling policies in the same application and to hierarchies of speculative parallel computations.

In addition to describing our framework, we also illustrate its expressiveness with several popular scheduling techniques. We present a (mostly) modular approach to extending our schedulers to support cancellation. This mechanism is essential for implementing eager and speculative parallelism. We finally evaluate our framework with a series of benchmarks and an analysis.

REFERENCES

• 1: Arora, N. S., R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors, 1998.
• 2: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 3: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 4: Blumofe, R. D., C. C. Leiserson, and B. Song. Automatic processor allocation for work-stealing jobs, 1998.
• 5: Robert D. Blumofe , Dionisios Papadopoulos, The performance of work stealing in multiprogrammed environments (extended abstract), Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.266-267, June 22-26, 1998, Madison, Wisconsin, United States
• 6: 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]
• 7: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 8: Manuel M. T. Chakravarty , Roman Leshchinskiy , Simon Peyton Jones , Gabriele Keller , Simon Marlow, Data parallel Haskell: a status report, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.10-18, January 16-16, 2007, Nice, France [doi>10.1145/1248648.1248652]
• 9: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 10: R. K. Dybvig , R. Hieb, Engines from continuations, Computer Languages, v.14 n.2, p.109-123, Aug. 1989 [doi>10.1016/0096-0551(89)90018-0]
• 11: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 12: John S. Danaher , I.-Ting Angelina Lee , Charles E. Leiserson, Programming with exceptions in JCilk, Science of Computer Programming, v.63 n.2, p.147-171, 1 December 2006 [doi>10.1016/j.scico.2006.05.008]
• 13: Alexandra Fedorova , Margo I. Seltzer, Operating system scheduling for chip multithreaded processors, Harvard University, Cambridge, MA, 2006
• 14: Marc Feeley, Polling efficiently on stock hardware, Proceedings of the conference on Functional programming languages and computer architecture, p.179-187, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165205]
• 15: Feitelson, D. G. Job scheduling in multiprogrammed parallel systems. Research Report RC 19790 (87657), IBM, October 1994. Second revision, August 1997.
• 16: Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany [doi>10.1145/1292535.1292539]
• 17: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 18: Matthew Fluet , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Manticore: a heterogeneous parallel language, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.37-44, January 16-16, 2007, Nice, France [doi>10.1145/1248648.1248656]
• 19: Matthew Fluet , Mike Rainey , John Reppy , Adam Shaw, Implicitly-threaded parallelism in Manticore, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 20: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 21: Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
• 22: Christopher T. Haynes , Daniel P. Friedman, Engines build process abstractions, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.18-24, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802018]
• 23: Christopher T. Haynes , Daniel P. Friedman , Mitchell Wand, Continuations and coroutines, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.293-298, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802046]
• 24: Carl Hauser , Christian Jacobi , Marvin Theimer , Brent Welch , Mark Weiser, Using threads in interactive systems: a case study, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.94-105, December 05-08, 1993, Asheville, North Carolina, United States
• 25: 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
• 26: Peng Li , Simon Marlow , Simon Peyton Jones , Andrew Tolmach, Lightweight concurrency primitives for GHC, Proceedings of the ACM SIGPLAN workshop on Haskell workshop, September 30-30, 2007, Freiburg, Germany [doi>10.1145/1291201.1291217]
• 27: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• 28: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 29: Nikhil, R. S. ID Language Reference Manual. Laboratory for Computer Science, MIT, Cambridge, MA, July 1991.
• 30: Randy B. Osborne, Speculative computation in multilisp, Proceedings of the 1990 ACM conference on LISP and functional programming, p.198-208, June 27-29, 1990, Nice, France [doi>10.1145/91556.91644]
• 31: Rainey, M. The Manticore runtime model. Master's dissertation, University of Chicago, January 2007. Available from http://manticore.cs.uchicago.edu.
• 32: Rainey, M. Prototyping nested schedulers. In Redex Workshop, September 2007.
• 33: Ramsey, N. Concurrent programming in ML. Technical Report CS-TR-262-90, Dept. of C.S., Princeton University, April 1990.
• 34: John H. Reppy, First-Class Synchronous Operations in Standard ML, Cornell University, Ithaca, NY, 1989
• 35: John H. Reppy, Asynchronous Signals is Standard ML, Cornell University, Ithaca, NY, 1990
• 36: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 37: John Reppy, Optimizing Nested Loops Using Local CPS Conversion, Higher-Order and Symbolic Computation, v.15 n.2-3, p.161-180, September 2002 [doi>10.1023/A:1020839128338]
• 38: John Reppy , Yingqi Xiao, Specialization of CML message-passing primitives, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 39: Reppy, J. and Y. Xiao. Toward a parallel implementation of Concurrent ML. In DAMP '08, New York, NY, January 2008. ACM.
• 40: Shaw, A. Data parallelism in Manticore. Master's dissertation, University of Chicago, July 2007. Available from http://manticore.cs.uchicago.edu.
• 41: Shivers, O. Continuations and threads: Expressing machine concurrency directly in advanced languages. In CW '97, New York, NY, January 1997. ACM.
• 42: 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]
• 43: Mitchell Wand, Continuation-based multiprocessing, Proceedings of the 1980 ACM conference on LISP and functional programming, p.19-28, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802786]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Languages, Performance

Keywords:
compilers, heterogeneous parallel languages, run-time systems, scheduling