TY - GEN

T1 - Graph contraction for physical optimization methods

T2 - 7th International Conference on Supercomputing, ICS 1993

AU - Mansour, N.

AU - Ponnusamy, R.

AU - Choudhary, A.

AU - Fox, G. C.

N1 - Funding Information:
“ This work was sponsored in part by DARPA under contract DARPA contract no. DABT63-91-C-O028 and in part by NSF grant MIP-911 0810. The content of the information does not necessarily reflect the position of the policy of the Government and no official endorsement should be inferred.
Funding Information:
We would like to thank Dimitri Mavriplis for providing us with his unstructured meshes. We also would to thank R. Das and J. Saltz for providing us PARTI software. This work was sponsored in part by DARPA under contract no. DABT63-91-C-O028 and in part NSF grant MIP-911081O.
Publisher Copyright:
© 1993 ACM.

PY - 1993/8/1

Y1 - 1993/8/1

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 paper, 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 straight-forward 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 paper, 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 straight-forward 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=85002001368&partnerID=8YFLogxK

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

U2 - 10.1145/165939.165942

DO - 10.1145/165939.165942

M3 - Conference contribution

AN - SCOPUS:85002001368

T3 - Proceedings of the International Conference on Supercomputing

SP - 1

EP - 10

BT - Proceedings of the 7th International Conference on Supercomputing, ICS 1993

PB - Association for Computing Machinery

Y2 - 19 July 1993 through 23 July 1993

ER -