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 -