Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Concurrent ML (CML) is a high-level message-passing language that supports the construction of first-class synchronous abstractions called events. This mechanism has proven quite effective over the years and has been incorporated in a number of other languages. While CML provides a concurrent programming model, its implementation has always been limited to uniprocessors. This limitation is exploited in the implementation of the synchronization protocol that underlies the event mechanism, but with the advent of cheap parallel processing on the desktop (and laptop), it is time for Parallel CML.

Parallel implementations of CML-like primitives for Java and Haskell exist, but build on high-level synchronization constructs that are unlikely to perform well. This paper presents a novel, parallel implementation of CML that exploits a purpose-built optimistic concurrency protocol designed for both correctness and performance on shared-memory multiprocessors. This work extends and completes an earlier protocol that supported just a strict subset of CML with synchronization on input, but not output events. Our main contributions are a model-checked reference implementation of the protocol and two concrete implementations. This paper focuses on Manticore's functional, continuation-based implementation but briefly discusses an independent, thread-based implementation written in C# and running on Microsoft's stock, parallel runtime. Although very different in detail, both derive from the same design. Experimental evaluation of the Manticore implementation reveals good performance, dispite the extra overhead of multiprocessor synchronization.

REFERENCES

• 1: R Bornat, A protocol for generalized occam, Software—Practice & Experience, v.16 n.9, p.783-799, Sept. 1986
• 2: G. N. Buckley , Abraham Silberschatz, An Effective Implementation for the Generalized Input-Output Construct of CSP, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.223-235, April 1983 [doi>10.1145/69624.357208]
• 3: The .NET Common Language Runtime. See http://msdn.microsoft.com/en-gb/netframework/.
• 4: Chrysanthakopoulos, G. and S. Singh. An asynchronous messaging library for C#. In Synchronization and Concurrency in Object-Oriented Languages (SCOOL), OOPSLA 2005 Workshop. UR Research, October 2005.
• 5: Demaine, E. D. Higher-order concurrency in Java. In WoTUG20, April 1997, pp. 34--47. Available from http://theory.csail.mit.edu/ edemaine/papers/WoTUG20/.
• 6: Protocols for Non-Deterministic Communication over Synchronous Channels, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.24, March 30-April 03, 1998
• 7: Kevin Donnelly , Matthew Fluet, Transactional events, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 8: Matthew Flatt , Robert Bruce Findler, Kill-safe synchronization abstractions, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 9: 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]
• 10: 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
• 11: Emden R. Gansner , John H. Reppy, A multi-threaded higher-order user interface toolkit, User interface software, John Wiley & Sons, Inc., New York, NY, 1993
• 12: Herlihy, M. and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers, New York, NY, 2008.
• 13: Knabe, F. A distributed protocol for channel-based communication with choice. Technical Report ECRC-92-16, European Computer-industry Research Center, October 1992.
• 14: Leroy, X. The Objective Caml System (release 3.00), April 2000. Available from http://caml.inria.fr.
• 15: mlton-concurMLton. Concurrent ML. Available at http://mlton.org/ConcurrentML.
• 16: Madanlal Musuvathi , Shaz Qadeer, Iterative context bounding for systematic testing of multithreaded programs, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 17: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 18: J. H. Reppy, Synchronous operations as first-class values, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.250-259, June 20-24, 1988, Atlanta, Georgia, United States
• 19: 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
• 20: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 21: Ritson, C. Multicore scheduling for lightweight communicating processes. Talk at the Workshop on Language and Runtime Support for Concurrent Systems, October 2008. Slides available from http://www.mm-net.org.uk/workshop171008/mmw07-slides.
• 22: George Russell, Events in Haskell, and how to implement them, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 23: 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
• 24: Reppy, J. and Y. Xiao. Toward a parallel implementation of Concurrent ML. In DAMP '08. ACM, January 2008.
• 25: TG2, E. T. C# language specification. See http://www.ecma-international.org/publications/standards/Ecma-334.htm.
• 26: Vella, K. Seamless parallel computing on heterogeneous networks of multiprocessor workstations. Ph.D. dissertation, University of Kent at Canterbury, December 1998.
• 27: Young, C., L. YN, T. Szymanski, J. Reppy, R. Pike, G. Narlikar, S. Mullender, and E. Grosse. Protium, an infrastructure for partitioned applications. In HotOS-X, January 2001, pp. 41--46.

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: Applicative (functional) languages; Concurrent, distributed, and parallel languages

General Terms:
Languages, Performance

Keywords:
concurrency, message passing, parallelism