A Partitioning-Independent Paradigm for Nested Data Parallelism
Abstract
A generalization of the data parallel model has been proposed by
Blelloch which permits the nesting of data parallel operators to specify
parallel computation across nested and irregular data structures.
In this paper we consider the costs of supporting the general model of
nested data parallelism, analyzing the requirements such a model
places upon an underlying model of execution. We propose
a new multi-node execution model which meets the needs of the paradigm
and is additionally generic in the partitioning
of data aggregates within the system.
The basis for our execution model is an abstract machine based upon
elementary notions of nodal multi-threading. We demonstrate the utility of
our proposal by providing
a full definition for a simple nestable one-dimensional data parallel
operator. We discuss the applicability of our
design to existing multi-processor machines, illustrating performance
statistics gathered from a prototype system we have constructed on the
Thinking Machines CM-5.