NPAC Technical Report SCCS-725
Mapping Unstructured Computational Graphs for Adaptive and Nonuniform Computational Environments
Maher Kaddoura, Chao-Wei Ou, Sanjay Ranka
Submitted August 2 191994
Abstract
In this paper we study the problem of mapping a large class of
irregular and loosely synchronous data-parallel applications in a
nonuniform and adaptive computational environment.
The computational
structure of these applications can be
described in terms of a computational graph, where nodes of the graph
represent computational tasks and edges describe the communication
between tasks.
Parallelization of these applications onto nonuniform computational
environments requires partitioning the graph
among the processors in such fashion that the computation load on each node is
proportional to its computational power, while communication is
minimized.
We discuss the applicability of current methods for
graph partitioning for such environments.
For an adaptive computational environment,
the partitioning of the graph needs to be
updated as the environment adapts, hence most algorithms described
in the literature are computationally prohibitive. We discuss novel
strategies that allow for fast remapping.