NPAC Technical Report SCCS-728

An Architecture-Independent Locally-Improving Transformation of Computational Graphs Embedded in K-Dimensions

Chao-Wei Ou, Manoj Gunwani, Sanjay Ranka

Submitted December 1 1994


Abstract

A large number of data-parallel applications can be represented as computational graphs from the perspective of parallel computing. The nodes of these graphs represent tasks that can be executed concurrently, while the edges represent the interactions between them. Further, the computational graphs derived from many applications are such that the vertices correspond to two- or three-dimensional coordinates, and the interaction between computations is limited to vertices that are physically proximate.

In this paper we show that graphs with these properties can be transformed into simple architecture-independent representations that encapsulate the locality in these graphs. This representation allows a fast mapping of the computational graph onto the underlying architecture at the time of execution. This is necessary for environments where available computational resources can be determined only at the time of execution or that change during execution.


PostScript version of the paper