Parallel Concurrent ML

摘要

Concurrent ML (CML) is a high-level message-passing language that supports the construction of first-class synchronous abstrac-tions 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 imple-mentation 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 Paral-lel 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, par-allel implementation of CML that exploits a purpose-built opti-mistic concurrency protocol designed for both correctness and per-formance 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 fo-cuses on Manticore's functional, continuation-based implementa-tion but briefly discusses an independent, thread-based implemen-tation written in C# and running on Microsoft's stock, parallel run-time. 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 multipro-cessor synchronization.