Improving graph partitioning for modern graphs and architectures

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

doi:10.1145/2833179.2833188

Improving graph partitioning for modern graphs and architectures

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

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

38 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 language	English (US)
Title of host publication	Proceedings of the 5th Workshop on Irregular Applications
Subtitle of host publication	Architectures and Algorithms, IA3 2015
Publisher	Association for Computing Machinery, Inc
ISBN (Electronic)	9781450340014
DOIs	https://doi.org/10.1145/2833179.2833188
State	Published - Nov 15 2015
Event	5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 - Austin, United States Duration: Nov 15 2015 → …

Publication series

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

Other

Other	5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015
Country/Territory	United States
City	Austin
Period	11/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.

Publisher link

10.1145/2833179.2833188

Find It

Find It at U of M Libraries

Cite this

Lasalle, D., Patwary, M. M. A., Satish, N., Sundaram, N., Dubey, P., & Karypis, G. (2015). Improving graph partitioning for modern graphs and architectures. In Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 Article a14 (Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015). Association for Computing Machinery, Inc. https://doi.org/10.1145/2833179.2833188

Improving graph partitioning for modern graphs and architectures. / Lasalle, Dominique; Patwary, Md Mostofa Ali; Satish, Nadathur et al.
Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015. Association for Computing Machinery, Inc, 2015. a14 (Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lasalle, D, Patwary, MMA, Satish, N, Sundaram, N, Dubey, P & Karypis, G 2015, Improving graph partitioning for modern graphs and architectures. in Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015., a14, Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015, Association for Computing Machinery, Inc, 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015, Austin, United States, 11/15/15. https://doi.org/10.1145/2833179.2833188

Lasalle D, Patwary MMA, Satish N, Sundaram N, Dubey P, Karypis G. Improving graph partitioning for modern graphs and architectures. In Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015. Association for Computing Machinery, Inc. 2015. a14. (Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015). doi: 10.1145/2833179.2833188

Lasalle, Dominique ; Patwary, Md Mostofa Ali ; Satish, Nadathur et al. / Improving graph partitioning for modern graphs and architectures. Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015. Association for Computing Machinery, Inc, 2015. (Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015).

@inproceedings{1ae3893b7e7b4d9991bc5b620283fed2,

title = "Improving graph partitioning for modern graphs and architectures",

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%.",

author = "Dominique Lasalle and Patwary, {Md Mostofa Ali} and Nadathur Satish and Narayanan Sundaram and Pradeep Dubey and George Karypis",

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.; 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 ; Conference date: 15-11-2015",

year = "2015",

month = nov,

day = "15",

doi = "10.1145/2833179.2833188",

language = "English (US)",

series = "Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015",

publisher = "Association for Computing Machinery, Inc",

booktitle = "Proceedings of the 5th Workshop on Irregular Applications",

}

TY - GEN

T1 - Improving graph partitioning for modern graphs and architectures

AU - Lasalle, Dominique

AU - Patwary, Md Mostofa Ali

AU - Satish, Nadathur

AU - Sundaram, Narayanan

AU - Dubey, Pradeep

AU - Karypis, George

N1 - 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.

PY - 2015/11/15

Y1 - 2015/11/15

N2 - 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%.

AB - 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%.

UR - http://www.scopus.com/inward/record.url?scp=84966874373&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84966874373&partnerID=8YFLogxK

U2 - 10.1145/2833179.2833188

DO - 10.1145/2833179.2833188

M3 - Conference contribution

AN - SCOPUS:84966874373

T3 - Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015

BT - Proceedings of the 5th Workshop on Irregular Applications

PB - Association for Computing Machinery, Inc

T2 - 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015

Y2 - 15 November 2015

ER -

Improving graph partitioning for modern graphs and architectures

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this