Document Open Access Logo

Deep Multilevel Graph Partitioning

Authors Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, Daniel Seemaier

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.48.pdf
  • Filesize: 1.58 MB
  • 17 pages

Document Identifiers

Author Details

Lars Gottesbüren
  • Karlsruhe Institute of Technology, Germany
Tobias Heuer
  • Karlsruhe Institute of Technology, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Germany
Christian Schulz
  • Universität Heidelberg, Germany
Daniel Seemaier
  • Karlsruhe Institute of Technology, Germany

Funding

The authors acknowledge support by the State of Baden-Württemberg through bwHPC. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 882500).

Cite AsGet BibTex

Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier. Deep Multilevel Graph Partitioning. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.48

Abstract

Partitioning a graph into blocks of "roughly equal" weight while cutting only few edges is a fundamental problem in computer science with a wide range of applications. In particular, the problem is a building block in applications that require parallel processing. While the amount of available cores in parallel architectures has significantly increased in recent years, state-of-the-art graph partitioning algorithms do not work well if the input needs to be partitioned into a large number of blocks. Often currently available algorithms compute highly imbalanced solutions, solutions of low quality, or have excessive running time for this case. This is due to the fact that most high-quality general-purpose graph partitioners are multilevel algorithms which perform graph coarsening to build a hierarchy of graphs, initial partitioning to compute an initial solution, and local improvement to improve the solution throughout the hierarchy. However, for large number of blocks, the smallest graph in the hierarchy that is used for initial partitioning still has to be large. In this work, we substantially mitigate these problems by introducing deep multilevel graph partitioning and a shared-memory implementation thereof. Our scheme continues the multilevel approach deep into initial partitioning - integrating it into a framework where recursive bipartitioning and direct k-way partitioning are combined such that they can operate with high performance and quality. Our integrated approach is stronger, more flexible, arguably more elegant, and reduces bottlenecks for parallelization compared to existing multilevel approaches. For example, for large number of blocks our algorithm is on average at least an order of magnitude faster than competing algorithms while computing partitions with comparable solution quality. At the same time, our algorithm consistently produces balanced solutions. Moreover, for small number of blocks, our algorithms are the fastest among competing systems with comparable quality.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • graph partitioning
  • graph algorithms
  • multilevel
  • shared-memory
  • parallel

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Intel Threading Building Blocks. https://www.threadingbuildingblocks.org/. Google Scholar
  2. Y. Akhremtsev. Parallel and External High Quality Graph Partitioning. PhD thesis, Karlsruher Institut für Technologie (KIT), 2019. URL: https://doi.org/10.5445/IR/1000098895.
  3. Y. Akhremtsev, T. Heuer, P. Sanders, and S. Schlag. Engineering a direct k-way Hypergraph Partitioning Algorithm. In 19th Workshop on Algorithm Engineering and Experiments, (ALENEX), pages 28-42, 2017. Google Scholar
  4. Y. Akhremtsev, P. Sanders, and C. Schulz. High-Quality Shared-Memory Graph Partitioning. IEEE Transactions on Parallel and Distributed Systems, 31(11):2710-2722, 2020. URL: https://doi.org/10.1109/TPDS.2020.3001645.
  5. K. Andreev and H. Räcke. Balanced Graph Partitioning. Theory of Computing Systems, 39(6):929-939, 2006. Google Scholar
  6. D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors. 10th DIMACS Implementation Challenge - Graph Partitioning and Graph Clustering, 2012. Google Scholar
  7. C. Bichot and P. Siarry, editors. Graph Partitioning. Wiley, 2011. Google Scholar
  8. A. Buluc, H. Meyerhenke, I.a Safro, P. Sanders, and C. Schulz. Recent Advances in Graph Partitioning. In Algorithm Engineering, volume 9220 of LNCS, pages 117-158. Springer, 2014. Google Scholar
  9. U. V. Catalyurek and C. Aykanat. Hypergraph-partitioning based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems (TPDS), 10(7):673-693, 1999. Google Scholar
  10. Ü. V. Çatalyürek, M. Deveci, K. Kaya, and B. Ucar. Multithreaded Clustering for Multi-Level Hypergraph Partitioning. In IEEE 26th International Symposium on Parallel and Distributed Processing (IPDPS), pages 848-859. IEEE, 2012. Google Scholar
  11. C. Chevalier and F. Pellegrini. PT-Scotch. Parallel Computing, pages 318-331, 2008. Google Scholar
  12. T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1):1:1-1:25, 2011. Google Scholar
  13. K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and Ü. V. Catalyürek. Parallel Hypergraph Partitioning for Scientific Computing. In 20th International Conference on Parallel and Distributed Processing, (IPDPS), pages 124-124. IEEE, 2006. Google Scholar
  14. E. D. Dolan and J. J. Moré. Benchmarking Optimization Software with Performance Profiles. Math. Program., 91(2):201-213, 2002. URL: https://doi.org/10.1007/s101070100263.
  15. C. M. Fiduccia and R. M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. In Proceedings of the 19th Conference on Design Automation, pages 175-181, 1982. Google Scholar
  16. D. Funke, S. Lamm, P. Sanders, C. Schulz, D. Strash, and M. von Looz. Communication-free Massively Distributed Graph Generation. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2018. Google Scholar
  17. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, volume 174. W.H. Freeman, San Francisco, 1979. Google Scholar
  18. L. Gottesbüren, T. Heuer, P. Sanders, and S. Schlag. Shared-Memory n-level Hypergraph Partitioning. arXiv preprint arXiv:2104.08107, 2021. Google Scholar
  19. L. Gottesbüren, T. Heuer, P. Sanders, and S. Schlag. Scalable Shared-Memory Hypergraph Partitioning. In 23rd Workshop on Algorithm Engineering and Experiments, (ALENEX 2021), pages 16-30. SIAM, 2021. Google Scholar
  20. T. Heuer, N. Maas, and S. Schlag. Multilevel Hypergraph Partitioning with Vertex Weights Revisited. In 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France, volume 190 of LIPIcs, pages 8:1-8:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SEA.2021.8.
  21. T. Heuer and S. Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In 16th International Symposium on Experimental Algorithms, (SEA), pages 21:1-21:19, 2017. Google Scholar
  22. M. Holtgrewe, P. Sanders, and C. Schulz. Engineering a Scalable High Quality Graph Partitioner. 24th IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pages 1-12, 2010. Google Scholar
  23. G. Karypis and V. Kumar. Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs. In Proceedings of the ACM/IEEE Conference on Supercomputing, 1996. Google Scholar
  24. G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, 20(1):359-392, 1998. Google Scholar
  25. G. Karypis and V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. Journal on Parallel and Distributed Compututing, 48(1):96-129, 1998. Google Scholar
  26. F. Khorasani, R. Gupta, and L. N. Bhuyan. Scalable SIMD-Efficient Graph Processing on GPUs. In Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques, PACT '15, pages 39-50, 2015. Google Scholar
  27. University of Milano Laboratory of Web Algorithms. Datasets. URL: http://law.di.unimi.it/datasets.php.
  28. D. LaSalle and G. Karypis. Multi-threaded Graph Partitioning. In 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 225-236, 2013. Google Scholar
  29. D. Lasalle and G. Karypis. Multi-threaded Graph Partitioning. In 27th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2013, Cambridge, MA, USA, May 20-24, 2013, pages 225-236, 2013. URL: https://doi.org/10.1109/IPDPS.2013.50.
  30. D. LaSalle and G. Karypis. A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning. In 45th International Conference on Parallel Processing (ICPP), pages 236-241, 2016. Google Scholar
  31. D. LaSalle, Md. M. A. Patwary, N. Satish, N. Sundaram, P. Dubey, and G. Karypis. Improving Graph Partitioning for Modern Graphs and Architectures. In Proceedings of the 5th Workshop on Irregular Applications - Architectures and Algorithms, IA3 2015, Austin, Texas, USA, November 15, 2015, pages 14:1-14:4. ACM, 2015. URL: https://doi.org/10.1145/2833179.2833188.
  32. J. Leskovec. Stanford Network Analysis Package (SNAP). Google Scholar
  33. M. Birn and V. Osipov and P. Sanders and C. Schulz and N. Sitchinava. Efficient Parallel and External Matching. In Euro-Par, volume 8097 of LNCS, pages 659-670. Springer, 2013. Google Scholar
  34. H. Meyerhenke, P. Sanders, and C. Schulz. Partitioning Complex Networks via Size-Constrained Clustering. In Experimental Algorithms, volume 8504 of LNCS, pages 351-363. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07959-2_30.
  35. H. Meyerhenke, P. Sanders, and C. Schulz. Parallel Graph Partitioning for Complex Networks. IEEE Transactions on Parallel and Distributed Systems, 28(9):2625-2638, 2017. URL: https://doi.org/10.1109/TPDS.2017.2671868.
  36. U. N. Raghavan, R. Albert, and S. Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical review E, 76(3):036106, 2007. Google Scholar
  37. P. Sanders and C. Schulz. Engineering Multilevel Graph Partitioning Algorithms. In 19th European Symposium on Algorithms (ESA), volume 6942 of LNCS, pages 469-480. Springer, 2011. Google Scholar
  38. S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. In 18th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 53-67, 2016. Google Scholar
  39. K. Schloegel, G. Karypis, and V. Kumar. Graph Partitioning for High Performance Scientific Simulations. In The Sourcebook of Parallel Computing, pages 491-541, 2003. Google Scholar
  40. C. Schulz and D. Strash. Graph Partitioning: Formulations and Applications to Big Data. In Encyclopedia of Big Data Technologies. Springer, 2019. URL: https://doi.org/10.1007/978-3-319-63962-8_312-2.
  41. G. M. Slota, K. Madduri, and S. Rajamanickam. PuLP: Scalable Multi-Objective Multi-Constraint Partitioning for Small-World Networks. In 2014 IEEE International Conference on Big Data (Big Data), pages 481-490, 2014. URL: https://doi.org/10.1109/BigData.2014.7004265.
  42. N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. In 49th Design Automation Conference, (DAC), pages 774-782, 2012. Google Scholar
  43. C. Walshaw and M. Cross. JOSTLE: Parallel Multilevel Graph-Partitioning Software - An Overview. In Mesh Partitioning Techniques and Domain Decomposition Techniques, pages 27-58. 2007. Google Scholar
  44. S. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, and J. Demmel. Optimization of Sparse Matrix-Vector Multiplication on Emerging Multicore Platforms. In SC '07: Proceedings of the 2007 ACM/IEEE Conference on Supercomputing, pages 1-12, 2007. URL: https://doi.org/10.1145/1362622.1362674.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact