Optimising Parallel Pattern-matching by Source-level Program Transformation

While, L. and Field, T.

Parallel pattern-matching (PPM) provides true commutative implementation of functions defined by cases in functional languages, because no argument is given precedence over any other. However, the requirement for concurrency (in general) to support these semantics means that current implementations incur a significant performance penalty over simple, traditional left-to-right semantics. We describe a source-level program transformation scheme that analyses a PPM definition and is often able to generate an equivalent definition that can be executed without concurrency. Where sequential implementation is not possible, the scheme is sometimes able to generate an equivalent definition that reduces the number of concurrent threads required to execute a definition. This transformation scheme promises to deliver a major improvement in the performance of PPM implementations.

Cite as: While, L. and Field, T. (2005). Optimising Parallel Pattern-matching by Source-level Program Transformation. In Proc. Twenty-Eighth Australasian Computer Science Conference (ACSC2005), Newcastle, Australia. CRPIT, 38. Estivill-Castro, V., Ed. ACS. 239-248.

(from crpit.com) (local if available)