Graph contraction for physical optimization methods

LAUR Repository

Show simple item record

dc.contributor.author Mansour, Nashat
dc.contributor.author Ponnusamy, A.
dc.contributor.author Choudhary, A.
dc.contributor.author Fox, G. C.
dc.date.accessioned 2018-05-24T06:53:43Z
dc.date.available 2018-05-24T06:53:43Z
dc.date.copyright 1993 en_US
dc.date.issued 2018-05-24
dc.identifier.isbn 0-89791-600-X en_US
dc.identifier.uri http://hdl.handle.net/10725/7931
dc.description.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. en_US
dc.language.iso en en_US
dc.publisher ACM en_US
dc.title Graph contraction for physical optimization methods en_US
dc.type Conference Paper / Proceeding en_US
dc.title.subtitle a quality-cost tradeoff for mapping data on parallel computers en_US
dc.author.school SAS en_US
dc.author.idnumber 198629170 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1145/165939.165942 en_US
dc.identifier.ctation Mansour, N., Ponnusamy, R., Choudhary, A., & Fox, G. C. (1993, August). 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 (pp. 1-10). ACM. en_US
dc.author.email nmansour@lau.edu.lb en_US
dc.conference.date July 19 - 23, 1993 en_US
dc.conference.pages 1-10 en_US
dc.conference.place Tokyo, Japan en_US
dc.conference.title ICS '93 Proceedings of the 7th international conference on Supercomputing en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://dl.acm.org/citation.cfm?id=165942 en_US
dc.orcid.id https://orcid.org/0000-0002-3603-8284 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account