Language Support for Pipelining Wavefront Computations

Bradford L. Chamberlain
E Christopher Lewis
Lawrence Snyder

In Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing (LCPC'99), pages 318-332, August 1999
(an earlier version of this work appeared as technical report UW-CSE-98-11-02)

Abstract: Wavefront computations, characterized by a data dependent flow of computation across a data space, are receiving increasing attention as an important class of parallel computations. Though sophisticated compiler optimizations can often produce efficient pipelined implementations from sequential representations, we argue that a language-based approach to representing wavefront computations is a more practical technique. A language-based approach is simple for the programmer yet unambiguously parallel. In this paper we introduce simple array language extensions that directly support wavefront computations. We show how a programmer may reason about the extensions' legality and performance; we describe their implementation and give performance data demonstrating the importance of parallelizing these codes.

postscript | PDF