AESOP home

Publications

Optimising Parallel Pattern-matching by Source-level Program Transformation

R. Lyndon While, A. J. Field

Conference or Workshop Paper
ACSC'05, 28th Australasian Computer Science Conference
January, 2005
ACM International Conference Proceedings
Volume 38
pp.239–248
Australian Computer Society
Abstract

Parallel pattern matching provides true commutative implementation of functions defined by cases in functional languages, because no argument is given precedence over any other. We present a formal semantics of parallel pattern matching and describe an implementation in Haskell that maps individual argument component matches into Concurrent Haskell threads. The performance of the Concurrent Haskell implementation is evaluated via benchmarking. The requirement for concurrency (in general) to support the semantics means that current implementations can often incur a significant performance penalty compared with sequential schemes, such as left-to-right matching. We describe a source-level program transformation scheme that analyses a parallel pattern matching definition and is often able to generate an equivalent definition that can be executed within a single thread. Where sequential implementation is not possible, the scheme is sometimes able to generate an equivalent definition that reduces the number of concurrent threads required.

PDF of full publication (186.8 kilobytes)
(need help viewing PDF files?)

Information from pubs.doc.ic.ac.uk/pattern-matching-optimisation.