Graph contraction for physical optimization methods: A quality-cost tradeoff for mapping data on parallel computers

N. Mansour, R. Ponnusamy, A. Choudhary, G. C. Fox

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th International Conference on Supercomputing, ICS 1993
PublisherAssociation for Computing Machinery
Pages1-10
Number of pages10
ISBN (Electronic)089791600X
DOIs
StatePublished - Aug 1 1993
Event7th International Conference on Supercomputing, ICS 1993 - Tokyo, Japan
Duration: Jul 19 1993Jul 23 1993

Publication series

NameProceedings of the International Conference on Supercomputing
VolumePart F129670

Other

Other7th International Conference on Supercomputing, ICS 1993
CountryJapan
CityTokyo
Period7/19/937/23/93

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Graph contraction for physical optimization methods: A quality-cost tradeoff for mapping data on parallel computers'. Together they form a unique fingerprint.

  • Cite this

    Mansour, N., Ponnusamy, R., Choudhary, A., & Fox, G. C. (1993). Graph contraction for physical optimization methods: A quality-cost tradeoff for mapping data on parallel computers. In Proceedings of the 7th International Conference on Supercomputing, ICS 1993 (pp. 1-10). (Proceedings of the International Conference on Supercomputing; Vol. Part F129670). Association for Computing Machinery. https://doi.org/10.1145/165939.165942