Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

Click here to sign up for SAGE Journal Email Alerts today!

Sign In to gain access to subscriptions and/or personal tools.
International Journal of High Performance Computing Applications
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Walshaw, C. H.
Right arrow Articles by Everett, M. G.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

A Localized Algorithm for Optimizing Unstructured Mesh Partitions

Chris H. Walshaw

SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY OF GREENWICH LONDON, SE18 6PF U.K.

Mark Cross

SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY OF GREENWICH LONDON, SE18 6PF U.K.

Martin G. Everett

SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY OF GREENWICH LONDON, SE18 6PF U.K.

A new method is described for optimizing graph parti tions that arise in mapping unstructured mesh calcula tions to parallel computers. The method employs a combination of iterative techniques to evenly balance the workload and minimize the number and volume of interprocessor communications. When combined with a fast direct-partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two- stage process proves itself to be a powerful and flexi ble solution to the static graph-partitioning problem. A clustering technique can also be employed to speed up the whole process. Experiments, on graphs with up to a million nodes, indicate that the resulting code is up to an order of magnitude faster than existing state- of-the-art techniques such as Multilevel Recursive Spectral Bisection, while providing partitions of equiv alent quality.

International Journal of High Performance Computing Applications, Vol. 9, No. 4, 280-295 (1995)
DOI: 10.1177/109434209500900403
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?