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|
|State||Published - Nov 15 2015|
|Event||5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 - Austin, United States|
Duration: Nov 15 2015 → …
|Name||Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015|
|Other||5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015|
|Period||11/15/15 → …|
Bibliographical noteFunding 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.