A PARTITIONING-INDEPENDENT PARADIGM FOR NESTED DATA PARALLELISM

A generalization of the data parallel model has been proposed by Blell och which permits the nesting of data parallel operators to specify pa rallel computation across nested and irregular data structures. In thi s paper we consider the costs of supporting the general model of neste d data parallelism, analyzing the requirements such a model places upo n an underlying model of execution. We propose a new multi-node execut ion model which meets the needs of the paradigm and is additionally ge neric in the partitioning of data aggregates within the system. The ba sis for our execution model is an abstract machine based upon elementa ry notions of nodal multi-threading. We demonstrate the utility of our proposal by providing a full definition for a simple nestable one-dim ensional data parallel operator. We discuss the applicability of our d esign to existing multi-processor machines, illustrating performance s tatistics gathered from a prototype system we have constructed on the Thinking Machines CM-5.