An Equational Language for Data-Parallelism

Abstract

Data-parallelism provides a clean conceptual framework for parallel programming. We are developing two programming languages: a high level equational language, called EL*, and a low-level implementation language. Both languages exploit data-parallelism instead of control-parallelism. EL* is a declarative data-parallel language. EL* programs are high-level equational specifications that use extensive pattern-matching and recursion. The language's syntax and semantics are intended to be clear and simple. Recursive forms are restricted to enable translation to efficient data-parallel operations. EL* programs are compiled into FP*, a variant of Backus's FP, where parallel operations are more explicit and low-level. The target language has a rich set of functions for performing communication, and computation. It also has a powerful set of combining forms that generate large highly-parallel functions from smaller program units. Prototype compilers have been implemented for both languages, and they demonstrate good performance. Several linear algebra and non-numeric problems have been programmed with relative ease using EL*. We are currently developing compilation techniques for a wider range of scientific problems that have more complex parallel solutions, and are continuing to expand the language's scope.