Implicitly-threaded parallelism in Manticore

ABSTRACT

The increasing availability of commodity multicore processors is making parallel computing available to the masses. Traditional parallel languages are largely intended for large-scale scientific computing and tend not to be well-suited to programming the applications one typically finds on a desktop system. Thus we need new parallel-language designs that address a broader spectrum of applications. In this paper, we present Manticore, a language for building parallel applications on commodity multicore hardware including a diverse collection of parallel constructs for different granularities of work. We focus on the implicitly-threaded parallel constructs in our high-level functional language. We concentrate on those elements that distinguish our design from related ones, namely, a novel parallel binding form, a nondeterministic parallel case form, and exceptions in the presence of data parallelism. These features differentiate the present work from related work on functional data parallel language designs, which has focused largely on parallel problems with regular structure and the compiler transformations --- most notably, flattening --- that make such designs feasible. We describe our implementation strategies and present some detailed examples utilizing various mechanisms of our language.

REFERENCES

• 1: 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]
• 2: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 3: Hans-J. Boehm , Russ Atkinson , Michael Plass, Ropes: an alternative to strings, Software—Practice & Experience, v.25 n.12, p.1315-1330, Dec. 1995 [doi>10.1002/spe.4380251203]
• 4: Barton, R., D. Adkins, H. Prokop, M. Frigo, C. Joerg, M. Renard, D. Dailey, and C. Leiserson. Cilk Pousse, 1998. Viewed on March 20, 2008 at 2:45 PM.
• 5: Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038]
• 6: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.213-225, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 8: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, ACM SIGPLAN Notices, v.30 n.8, p.207-216, Aug. 1995
• 9: Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996 [doi>10.1145/227234.227246]
• 10: Manuel M. T. Chakravarty , Gabriele Keller, More types for nested data parallel programming, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.94-105, September 2000
• 11: Manuel M. T. Chakravarty , Gabriele Keller , Roman Lechtchinsky , W. Pfannenstiel, Nepal - Nested Data Parallelism in Haskell, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.524-534, August 28-31, 2001
• 12: 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]
• 13: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 14: Dailey, D. and C. E. Leiserson. Using Cilk to write multiprocessor chess programs. The Journal of the International Computer Chess Association, 2002.
• 15: 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]
• 16: 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]
• 17: Matthew Fluet , Mike Rainey , John Reppy, A scheduling framework for general-purpose parallel languages, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 18: Jean-Luc Gaudiot , Tom DeBoni , John Feo , Wim Böhm , Walid Najjar , Patrick Miller, The Sisal Model of Functional Programming and its Implementation, Proceedings of the 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis, p.112, March 17-21, 1997
• 19: GHC. The Glasgow Haskell Compiler. Available from http://www.haskell.org/ghc.
• 20: Emden R. Gansner , John H. Reppy, The standard ML basis library, Cambridge University Press, New York, NY, 2002
• 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: Hammond, K. Parallel SML: a Functional Language and its Implementation in Dactl. The MIT Press, Cambridge, MA, 1991.
• 23: Hedqvist, P. A parallel and multithreaded ERLANG implementation. Master's dissertation, Computer Science Department, Uppsala University, Uppsala, Sweden, June 1998.
• 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: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 26: Jones, M. P. and P. Hudak. Implicit and explicit parallel programming in Haskell. Technical Report Research Report YALEU/DCS/RR-982, Yale University, August 1993.
• 27: Leshchinskiy, R., M. M. T. Chakravarty, and G. Keller. Higher order flattening. In V. Alexandrov, D. van Albada, P. Sloot, and J. Dongarra (eds.), ICCS '06, number 3992 in LNCS, New York, NY, May 2006. Springer-Verlag, pp. 920--928.
• 28: Xavier Leroy , François Pessaux, Type-based analysis of uncaught exceptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.340-377, March 2000 [doi>10.1145/349214.349230]
• 29: Luckham, D. Programming with Specifications. Texts and Monographs in Computer Science. Springer-Verlag, 1990.
• 30: Implicit parallel programming in pH, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 31: Nikhil, R. S. ID Language Reference Manual. Laboratory for Computer Science, MIT, Cambridge, MA, July 1991.
• 32: D. L. Parnas, A technique for software module specification with examples, Communications of the ACM, v.15 n.5, p.330-336, May 1972 [doi>10.1145/355602.361309]
• 33: Rob Pike , Sean Dorward , Robert Griesemer , Sean Quinlan, Interpreting the data: Parallel analysis with Sawzall, Scientific Programming, v.13 n.4, p.277-298, October 2005
• 34: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 35: Simon Peyton Jones , Alastair Reid , Fergus Henderson , Tony Hoare , Simon Marlow, A semantics for imprecise exceptions, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.25-36, May 01-04, 1999, Atlanta, Georgia, United States
• 36: Rainey, M. The Manticore runtime model. Master's dissertation, University of Chicago, January 2007. Available from http://manticore.cs.uchicago.edu.
• 37: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 38: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 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: P. W. Trinder , K. Hammond , H.-W. Loidl , S. L. Peyton Jones, Algorithm + strategy = parallelism, Journal of Functional Programming, v.8 n.1, p.23-60, January 1998 [doi>10.1017/S0956796897002967]
• 42: Tarditi, D., S. Puri, and J. Oglesby. Accelerator: using data parallelism to program gpus for general-purpose uses. SIGOPS Oper. Syst. Rev., 40(5), 2006, pp. 325--335.
• 43: Kwangkeun Yi, An abstract interpretation for estimating uncaught exceptions in standard ML programs, Science of Computer Programming, v.31 n.1, p.147-173, May 1998 [doi>10.1016/S0167-6423(96)00044-5]

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; Applicative (functional) languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages

Keywords:
data parallelism, exceptions, implictly-threaded parallelism, parallel binding, parallel case