TY - JOUR

T1 - Graph Contraction for Mapping Data on Parallel Computers

T2 - A Quality—Cost Tradeoff

AU - Ponnusamy, R.

AU - Fox, G. C.

AU - Mansour, N.

AU - Choudhary, A.

PY - 1994

Y1 - 1994

N2 - Mapping data to parallel computers aims at minimizing the execution time of the associated application. However, it can take an unacceptable amount of time in comparison with the execution time of the application if the size of the problem is large. In this article, first we motivate the case for graph contraction as a means for reducing the problem size. We restrict our discussion to applications where the problem domain can be described using a graph (e.g., computational fluid dynamics applications). Then we present a mapping-oriented parallel graph contraction (PGC) heuristic algorithm that yields a smaller representation of the problem to which mapping is then applied. The mapping solution for the original problem is obtained by a straightforward interpolation. We then present experimental results on using contracted graphs as inputs to two physical optimization methods; namely, genetic algorithm and simulated annealing. The experimental results show that the PGC algorithm still leads to a reasonably good quality mapping solutions to the original problem, while producing a substantial reduction in mapping time. Finally, we discuss the cost-quality tradeoffs in performing graph contraction.

AB - Mapping data to parallel computers aims at minimizing the execution time of the associated application. However, it can take an unacceptable amount of time in comparison with the execution time of the application if the size of the problem is large. In this article, first we motivate the case for graph contraction as a means for reducing the problem size. We restrict our discussion to applications where the problem domain can be described using a graph (e.g., computational fluid dynamics applications). Then we present a mapping-oriented parallel graph contraction (PGC) heuristic algorithm that yields a smaller representation of the problem to which mapping is then applied. The mapping solution for the original problem is obtained by a straightforward interpolation. We then present experimental results on using contracted graphs as inputs to two physical optimization methods; namely, genetic algorithm and simulated annealing. The experimental results show that the PGC algorithm still leads to a reasonably good quality mapping solutions to the original problem, while producing a substantial reduction in mapping time. Finally, we discuss the cost-quality tradeoffs in performing graph contraction.

UR - http://www.scopus.com/inward/record.url?scp=0028383253&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028383253&partnerID=8YFLogxK

U2 - 10.1155/1994/715918

DO - 10.1155/1994/715918

M3 - Article

AN - SCOPUS:0028383253

SN - 1058-9244

VL - 3

SP - 73

EP - 82

JO - Scientific Programming

JF - Scientific Programming

IS - 1

ER -