Improving graph partitioning for modern graphs and architectures

Dominique Lasalle, Md Mostofa Ali Patwary, Nadathur Satish, Narayanan Sundaram, Pradeep Dubey, George Karypis

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

30 Scopus citations

Abstract

Graph partitioning is an important preprocessing step in applications dealing with sparse-irregular data. As such, the ability to efficiently partition a graph in parallel is crucial to the performance of these applications. The number of compute cores in a compute node continues to increase, demanding ever more scalability from shared-memory graph partitioners. In this paper we present algorithmic improvements to the multithreaded graph partitioner mt-Metis. We experimentally evaluate our methods on a 36 core machine, using 20 difierent graphs from a variety of domains. Our improvements decrease the runtime by 1.5-11.7 and improve strong scaling by 82%.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Workshop on Irregular Applications
Subtitle of host publicationArchitectures and Algorithms, IA3 2015
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450340014
DOIs
StatePublished - Nov 15 2015
Event5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 - Austin, United States
Duration: Nov 15 2015 → …

Publication series

NameProceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015

Other

Other5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015
Country/TerritoryUnited States
CityAustin
Period11/15/15 → …

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. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.

Fingerprint

Dive into the research topics of 'Improving graph partitioning for modern graphs and architectures'. Together they form a unique fingerprint.

Cite this