Graph Contraction for Mapping Data on Parallel Computers

LAUR Repository

Show simple item record

dc.contributor.author Mansour, N.
dc.contributor.author Ponnusamy, R.
dc.contributor.author Choudhary, A.
dc.contributor.author Fox, G. C.
dc.date.accessioned 2016-01-25T13:47:18Z
dc.date.available 2016-01-25T13:47:18Z
dc.date.copyright 1994
dc.date.issued 2016-01-25
dc.identifier.issn 1058-9244 en_US
dc.identifier.uri http://hdl.handle.net/10725/2949
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 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. en_US
dc.language.iso en en_US
dc.title Graph Contraction for Mapping Data on Parallel Computers en_US
dc.type Article en_US
dc.description.version Published en_US
dc.title.subtitle A Quality–Cost Tradeoff en_US
dc.author.school SAS en_US
dc.author.idnumber 198629170 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Scientific Programming en_US
dc.journal.volume 3 en_US
dc.journal.issue 1 en_US
dc.article.pages 73-82 en_US
dc.identifier.doi http://dx.doi.org/10.1155/1994/715918 en_US
dc.identifier.ctation Ponnusamy, R., Mansour, N., Choudhary, A., & Fox, G. C. (1994). Graph Contraction for Mapping Data on Parallel Computers: A Quality–Cost Tradeoff. Scientific Programming, 3(1), 73-82. en_US
dc.author.email nmansour@lau.edu.lb
dc.identifier.url http://www.hindawi.com/journals/sp/1994/715918/abs/

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account