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.
Supplemental Material
- Bornat, R. A protocol for generalized occam. SP&E, 16(9), September 1986, pp. 783--799. Google ScholarDigital Library
- Buckley, G. N. and A. Silberschatz. An effective implementation for the generalized input-output construct of CSP. ACM TOPLAS, 5(2), April 1983, pp. 223--235. Google ScholarDigital Library
- The .NET Common Language Runtime. See http://msdn.microsoft.com/en-gb/netframework/.Google Scholar
- 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.Google Scholar
- 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/.Google Scholar
- Demaine, E. D. Protocols for non-deterministic communication over synchronous channels. In IPPS/SPDP'98, March 1998, pp. 24--30. Available from http://theory.csail.mit.edu/ edemaine/papers/IPPS98/. Google ScholarDigital Library
- Donnelly, K. and M. Fluet. Transactional events. In ICFP '06, Portland, Oregon, USA, 2006. ACM, pp. 124--135. Google ScholarDigital Library
- Flatt, M. and R. B. Findler. Kill-safe synchronization abstractions. In PLDI '04, June 2004, pp. 47--58. Google ScholarDigital Library
- 7}manticore-ml07Fluet, M., N. Ford, M. Rainey, J. Reppy, A. Shaw, and Y. Xiao. Status report: The Manticore project. In ML '07. ACM, October 2007, pp. 15--24. Google ScholarDigital Library
- Fluet, M., M. Rainey, and J. Reppy. A scheduling framework for general-purpose parallel languages. In ICFP '08, Victoria, BC, Candada, September 2008. ACM, pp. 241--252. Google ScholarDigital Library
- Gansner, E. R. and J. H. Reppy. A Multi-threaded Higher-order User Interface Toolkit, vol. 1 of Software Trends, pp. 61--80. John Wiley&Sons, 1993. Google ScholarDigital Library
- Herlihy, M. and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers, New York, NY, 2008. Google ScholarDigital Library
- Knabe, F. A distributed protocol for channel-based communication with choice. Technical Report ECRC-92-16, European Computer-industry Research Center, October 1992.Google ScholarCross Ref
- Leroy, X. The Objective Caml System (release 3.00), April 2000. Available from http://caml.inria.fr.Google Scholar
- mlton-concurMLton. Concurrent ML. Available at http://mlton.org/ConcurrentML.Google Scholar
- Musuvathi, M. and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In PLDI '07, San Diego, CA, June 2007. ACM, pp. 446--455. Google ScholarDigital Library
- Milner, R., M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised). The MIT Press, Cambridge, MA, 1997. Google ScholarDigital Library
- Reppy, J. H. Synchronous operations as first-class values. In PLDI '88, June 1988, pp. 250--259. Google ScholarDigital Library
- Reppy, J. H. CML: A higher-order concurrent language. In PLDI '91. ACM, June 1991, pp. 293--305. Google ScholarDigital Library
- Reppy, J. H. Concurrent Programming in ML. Cambridge University Press, Cambridge, England, 1999. Google ScholarDigital Library
- 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.Google Scholar
- Russell, G. Events in Haskell, and how to implement them. In ICFP '01, September 2001, pp. 157--168. Google ScholarDigital Library
- Reppy, J. and Y. Xiao. Specialization of CML message-passing primitives. In POPL '07. ACM, January 2007, pp. 315--326. Google ScholarDigital Library
- Reppy, J. and Y. Xiao. Toward a parallel implementation of Concurrent ML. In DAMP '08. ACM, January 2008.Google Scholar
- TG2, E. T. C# language specification. See http://www.ecma-international.org/publications/standards/Ecma-334.htm.Google Scholar
- Vella, K. Seamless parallel computing on heterogeneous networks of multiprocessor workstations. Ph.D. dissertation, University of Kent at Canterbury, December 1998.Google Scholar
- 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.Google ScholarCross Ref
Index Terms
- Parallel concurrent ML
Recommendations
Parallel concurrent ML
ICFP '09Concurrent 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 ...
Added Concurrency to Improve MPI Performance on Multicore
ICPP '12: Proceedings of the 2012 41st International Conference on Parallel ProcessingMPI implementations typically equate an MPI process with an OS-process, resulting in a coarse-grain programming model where MPI processes are bound to the physical cores. Fine-Grain (FG-MPI) extends the MPICH2 implementation of MPI and implements an ...
Benchmark Evaluation of the IBM SP2 for Parallel Signal Processing
This paper evaluates the IBM SP2 architecture, the AIX parallel programming environment, and the IBM message-passing library (MPL) through STAP (Space-Time Adaptive Processing) benchmark experiments. Only coarse-grain parallelism was exploited on the ...
Comments