Parallel Concurrent ML.
John Reppy, Claudio Russo, and Yingqi Xiao.
In Proceedings of the 14th ACM SIGPLAN International
Conference on Functional Programming (ICFP 2009), pages 257--268, New York,
NY, September 2009. ACM.
[ bib |
DOI |
.pdf ]
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, despite the extra overhead of multiprocessor synchronization.
Toward a parallel implementation of Concurrent ML.
John Reppy and Yingqi Xiao.
In Proceedings of the Workshop on Declarative Aspects of
Multicore Programming (DAMP 2008), January 2008.
[ bib |
.pdf ]
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.We are pursuing such an implementation as part of the Manticore project. In this paper, we describe a parallel implementation of Asymmetric CML (ACML), which is a subset of CML that does not support output guards. We describe an optimistic concurrency protocol for implementing CML synchronization. This protocol has been implemented as part of the Manticore system.
Specialization of CML message-passing primitives.
John Reppy and Yingqi Xiao.
In Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages (POPL 2007), pages 315--326, January
2007.
[ bib |
DOI |
.pdf ]
Concurrent ML (CML) is a statically-typed higher-order concurrent language that is embedded in Standard ML. Its most notable feature is its support for first-class synchronous operations. This mechanism allows programmers to encapsulate complicated communication and synchronization protocols as first-class abstractions, which encourages a modular style of programming where the underlying channels used to communicate with a given thread are hidden behind data and type abstraction.While CML has been in active use for well over a decade, little attention has been paid to optimizing CML programs. In this paper, we present a new program analysis for statically-typed higher-order concurrent languages that enables the compile-time specialization of communication operations. This specialization is particularly important in a multiprocessor or multicore setting, where the synchronization overhead for general-purpose operations are high. Preliminary results from a prototype that we have built demonstrate that specialized channel operations are much faster than the general-purpose operations.
Our analysis technique is modular (i.e., it analyzes and optimizes a single unit of abstraction at a time), which plays to the modular style of many CML programs. The analysis consists of three steps: the first is a type-sensitive control-flow analysis that uses the program's type-abstractions to compute more precise results. The second is the construction of an extended control-flow graph using the results of the CFA. The last step is an iterative analysis over the graph that approximates the usage patterns of known channels. Our analysis is designed to detect special patterns of use, such as one-shot channels, fan-in channels, and fan-out channels. We have proven the safety of our analysis and state those results.
Concurrent Programming in ML.
John H. Reppy.
Cambridge University Press, Cambridge, England, 1999.
[ bib ]
The Essence of Concurrent ML.
Prakash Panangaden and John Reppy.
In Flemming Nielson, editor, ML with Concurrency, Chapter 1.
Springer-Verlag, 1997.
[ bib ]
A Multi-threaded Higher-order User Interface Toolkit.
Emden R. Gansner and John H. Reppy.
In User Interface Software, Bass and Dewan (Eds.), Volume 1 of
Software Trends, pages 61--80. John Wiley & Sons, 1993.
[ bib |
.pdf ]
Concurrent ML: Design, application and semantics.
John H. Reppy.
In Peter Lauer, editor, Functional Programming, Concurrency,
Simulation and Automated Reasoning, number 693 in Lecture Notes in Computer
Science. Springer-Verlag, New York, NY, 1993.
[ bib ]
Higher-order Concurrency.
John H. Reppy.
PhD thesis, Cornell University, 1992.
Available as Computer Science Technical Report 92-1285.
[ bib ]
eXene.
Emden R. Gansner and John H. Reppy.
In Third International Workshop on ML, September 1991.
[ bib |
.pdf ]
CML: A higher-order concurrent language.
John H. Reppy.
In Proceedings of the SIGPLAN 1991 Conference on Programming
Language Design and Implementation, pages 293--305, New York, NY, June 1991.
ACM.
[ bib |
.pdf ]
This file was generated by bibtex2html 1.98.