[super94.abs]

J. Subhlok, D. O'Hallaron, T. Gross, P. Dinda, and J. Webb,
"Communication and Memory Requirements as the Basis for Mapping Task
and Data Parallel Programs", in Proc. Supercomputing '94, Washington,
DC, Nov, 1994, pp. 330-339.

Abstract: For a wide variety of applications, both task and data
parallelism must be exploited to achieve the best possible performance
on a multicomputer. Recent research has underlined the importance of
exploiting task and data parallelism in a single compiler framework,
and such a compiler can map a single source program in many different
ways onto a parallel machine. There are several complex tradeoffs
between task and data parallelism, depending on the characteristics of
the program to be executed, most significantly the memory and
communication requirements, and the performance parameters of the
target parallel machine.  In this paper, we isolate and examine the
specific characteristics of programs that determine the performance
for different mappings on a parallel machine, and present a framework
for obtaining a good mapping. The framework is applicable to
applications that process a stream of input, and whose computation
structure is fairly static and predictable.  We describe three
applications that were developed with our compiler: fast Fourier
transforms, narrowband tracking radar and multibaseline stereo,
examine the tradeoffs between various mappings for them, and show how
the framework was used to obtain efficient mappings.  We believe that
application and tool developers interested in combining task and data
parallelism will find the ideas and the results in this paper useful.