Improving Graph Partitioning for Modern Graphs and Architectures
| Dominique LaSalle, Md Mostofa Ali Patwary, Nadathur Satish, Narayanan Sundaram, Pradeep Dubey, and George Karypis |
| 5th Workshop on Irregular applications: Architectures and Algorithms, Supercomputing, 2015 |
Download Paper  |
| 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. Furthermore, datasets whose graphical representations have skewed degree distributions have gained in importance and exhibit very different characteristics than the graphs previously used in scientific computing. In this paper we present algorithmic improvements to the multi-threaded graph partitioner mt-Metis. We address issues re- lated to these new network-style graphs and explore techniques to improve performance and parallel scaling. We experimentally evaluate our methods on a 36 core machine, using 20 different graphs from a variety of domains. Our improvements decrease the runtime by 1.5 ? 11.7× and improve strong scaling by 82%. |
| Research topics: Graph partitioning | METIS | Parallel processing |