A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning

Dominique Lasalle, George Karypis

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

11 Scopus citations

Abstract

Graph partitioning is important in distributing workloads on parallel compute systems, computing sparse matrix re-orderings, and designing VLSI circuits. Refinement algorithms are used to improve existing partitionings, and are essential for obtaining high-quality partitionings. Existing parallel refinement algorithms either extract concurrency by sacrificing in terms of quality, or preserve quality by restricting concurrency. In this work we present a new shared-memory parallel algorithm for refining an existing k-way partitioning that can break out of local minima and produce high-quality partitionings. This allows our algorithm to scale well in terms of the number of processing cores and produce clusterings of quality equal to serial algorithms. Our algorithm achieves speedups of 5.7-16.7&-using 24 cores, while exhibiting only 0.52% higher edgecuts than when run serially. This is 6.3x faster and 1.9% better quality than other parallel refinement algorithms which can break out of local minima.

Original languageEnglish (US)
Title of host publicationProceedings - 45th International Conference on Parallel Processing, ICPP 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages236-241
Number of pages6
ISBN (Electronic)9781509028238
DOIs
StatePublished - Sep 21 2016
Event45th International Conference on Parallel Processing, ICPP 2016 - Philadelphia, United States
Duration: Aug 16 2016Aug 19 2016

Publication series

NameProceedings of the International Conference on Parallel Processing
Volume2016-September
ISSN (Print)0190-3918

Other

Other45th International Conference on Parallel Processing, ICPP 2016
CountryUnited States
CityPhiladelphia
Period8/16/168/19/16

Bibliographical note

Funding Information:
This work was supported in part by NSF (IIS-0905220, OCI-1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788),Army Research Office (W911NF-14-1-0316), Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota.

Keywords

  • Graph partitioning
  • Local minima
  • Multithreading

Fingerprint Dive into the research topics of 'A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning'. Together they form a unique fingerprint.

Cite this