Title
Mapping Unstructured Computational Graphs for Adaptive and Nonuniform Computational Environments
Document Type
Article
Date
1995
Keywords
Graph partitioning, Nonuniform machines, Heterogeneous computing, Irregular problems, Network of workstations
Language
English
Disciplines
Computer Sciences
Description/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 on 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.
Recommended Citation
Kaddoura, Maher; Ou, Chao Wei; and Ranka, Sanjay, "Mapping Unstructured Computational Graphs for Adaptive and Nonuniform Computational Environments" (1995). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 41.
https://surface.syr.edu/lcsmith_other/41
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
