Document Open Access Logo

Parallel Flow-Based Hypergraph Partitioning

Authors Lars Gottesbüren, Tobias Heuer, Peter Sanders

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.5.pdf
  • Filesize: 4.05 MB
  • 21 pages

Document Identifiers

Author Details

Lars Gottesbüren
  • Karlsruhe Institute of Technology, Karlsruhe, Germany
Tobias Heuer
  • Karlsruhe Institute of Technology, Karlsruhe, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Karlsruhe, Germany

Funding

This work was partially supported by DFG grants WA654/19-2 and SA933/11-1. The authors acknowledge support by the state of Baden-Württemberg through bwHPC.

Cite As Get BibTex

Lars Gottesbüren, Tobias Heuer, and Peter Sanders. Parallel Flow-Based Hypergraph Partitioning. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SEA.2022.5

Abstract

We present a shared-memory parallelization of flow-based refinement, which is considered the most powerful iterative improvement technique for hypergraph partitioning at the moment. Flow-based refinement works on bipartitions, so current sequential partitioners schedule it on different block pairs to improve k-way partitions. We investigate two different sources of parallelism: a parallel scheduling scheme and a parallel maximum flow algorithm based on the well-known push-relabel algorithm. In addition to thoroughly engineered implementations, we propose several optimizations that substantially accelerate the algorithm in practice, enabling the use on extremely large hypergraphs (up to 1 billion pins). We integrate our approach in the state-of-the-art parallel multilevel framework Mt-KaHyPar and conduct extensive experiments on a benchmark set of more than 500 real-world hypergraphs, to show that the partition quality of our code is on par with the highest quality sequential code (KaHyPar), while being an order of magnitude faster with 10 threads.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Hypergraphs
  • Mathematics of computing → Graph algorithms
Keywords
  • multilevel hypergraph partitioning
  • shared-memory algorithms
  • maximum flow

Metrics

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

Related Versions

Supplementary Materials

References

  1. Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Engineering a Direct k-way Hypergraph Partitioning Algorithm. In 19th Workshop on Algorithm Engineering & Experiments (ALENEX), pages 28-42. SIAM, January 2017. URL: https://doi.org/10.1137/1.9781611974768.3.
  2. Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. High-Quality Shared-Memory Graph Partitioning. In European Conference on Parallel Processing (Euro-Par), pages 659-671. Springer, August 2017. URL: https://doi.org/10.1007/978-3-319-96983-1_47.
  3. Charles J. Alpert. The ISPD98 Circuit Benchmark Suite. In International Symposium on Physical Design (ISPD), pages 80-85, April 1998. URL: https://doi.org/10.1145/274535.274546.
  4. Charles J. Alpert and Andrew B. Kahng. Recent Directions in Netlist Partitioning: A Survey. Integration, 19(1-2):1-81, 1995. URL: https://doi.org/10.1016/0167-9260(95)00008-4.
  5. Reid Andersen. and Kevin J. Lang. An Algorithm for Improving Graph Partitions. In Proc. of the 19th ACM-SIAM Symposium on Discrete Algorithms, pages 651-660. Society for Industrial and Applied Mathematics, 2008. URL: https://doi.org/10.5555/1347082.1347154.
  6. Richard J. Anderson and João C. Setubal. A Parallel Implementation of the Push-Relabel Algorithm for the Maximum Flow Problem. J. Parallel Distributed Comput., 29(1):17-26, 1995. URL: https://doi.org/10.1006/jpdc.1995.1103.
  7. Aaron Archer, Kevin Aydin, Mohammad Hossein Bateni, Vahab S. Mirrokni, Aaron Schild, Ray Yang, and Richard Zhuang. Cache-Aware Load Balancing of Data Center Applications. Proceedings of the VLDB Endowment, 12(6):709-723, 2019. URL: https://doi.org/10.14778/3311880.3311887.
  8. Cevdet Aykanat, Berkant Barla Cambazoglu, and Bora Uçar. Multi-level Direct k-way Hypergraph Partitioning With Multiple Constraints and Fixed Vertices. Journal of Parallel and Distributed Computing, 68(5):609-625, 2008. URL: https://doi.org/10.1016/j.jpdc.2007.09.006.
  9. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partitioning and Graph Clustering, volume 588. American Mathematical Society Providence, RI, 2013. URL: https://doi.org/10.1090/conm/588.
  10. Niklas Baumstark, Guy E. Blelloch, and Julian Shun. Efficient implementation of a synchronous parallel push-relabel algorithm. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 106-117. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_10.
  11. Anton Belov, Daniel Diepold, Marijn Heule, and Matti Järvisalo. The SAT Competition 2014. http://www.satcompetition.org/2014/, 2014.
  12. Ümit V. Catalyurek and Cevdet Aykanat. Hypergraph-Partitioning-based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693, 1999. URL: https://doi.org/10.1109/71.780863.
  13. Boris V. Cherkassky and Andrew V. Goldberg. On Implementing the Push-Relabel Method for the Maximum Flow Problem. Algorithmica, 19(4):390-410, 1997. URL: https://doi.org/10.1007/PL00009180.
  14. Carlo Curino, Yang Zhang, Evan P. C. Jones, and Samuel Madden. Schism: a Workload-Driven Approach to Database Replication and Partitioning. Proceedings of the VLDB Endowment, 3(1):48-57, 2010. URL: https://doi.org/10.14778/1920841.1920853.
  15. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1):1:1-1:25, November 2011. URL: https://doi.org/10.1145/2049662.2049663.
  16. Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. Graph Partitioning with Natural Cuts. In Proc. of the 25th International Parallel and Distributed Processing Symposium, pages 1135-1146, 2011. URL: https://doi.org/10.1109/IPDPS.2011.108.
  17. Mehmet Deveci, Kamer Kaya, and Ümit V. Çatalyürek. Hypergraph Sparsification and Its Application to Partitioning. In 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, October 1-4, 2013, pages 200-209, 2013. URL: https://doi.org/10.1109/ICPP.2013.29.
  18. Karen D. Devine, Erik G. Boman, Robert T. Heaphy, Rob H. Bisseling, and Ümit V. Catalyurek. Parallel Hypergraph Partitioning for Scientific Computing. In IEEE Transactions on Parallel and Distributed Systems, pages 10-pp. IEEE, 2006. URL: https://doi.org/10.1109/IPDPS.2006.1639359.
  19. Elizabeth D. Dolan and Jorge J. Moré. Benchmarking Optimization Software with Performance Profiles. Mathematical Programming, 91(2):201-213, 2002. URL: https://doi.org/10.1007/s101070100263.
  20. Charles M. Fiduccia and Robert M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. In 19th Conference on Design Automation (DAC), pages 175-181, 1982. URL: https://doi.org/10.1145/800263.809204.
  21. Lester Randolph Ford and Delbert R Fulkerson. Maximal Flow through a Network. Canadian Journal of Mathematics, 8:399-404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  22. Andrew V. Goldberg and Robert Endre Tarjan. A New Approach to the Maximum-Flow Problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  23. Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced Flow-Based Multilevel Hypergraph Partitioning. 18th International Symposium on Experimental Algorithms (SEA), 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.11.
  24. Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In 27th European Symposium on Algorithms (ESA), pages 52:1-52:17, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.52.
  25. Lars Gottesbüren, Tobias Heuer, and Peter Sanders. Parallel Flow-Based Hypergraph Partitioning. Technical report, Karlsruhe Institute of Technology, 2022. Google Scholar
  26. Lars Gottesbüren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Scalable Shared-Memory Hypergraph Partitioning. In 23st Workshop on Algorithm Engineering & Experiments (ALENEX). SIAM, January 2021. URL: https://doi.org/10.1137/1.9781611976472.2.
  27. Lars Gottesbüren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Shared-Memory n-level Hypergraph Partitioning. In 24th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, January 2022. URL: https://doi.org/10.1137/1.9781611977042.11.
  28. Johnnie Gray and Stefanos Kourtis. Hyper-optimized tensor network contraction. Quantum, 5:410, 2021. URL: https://doi.org/10.22331/q-2021-03-15-410.
  29. Michael Hamann and Ben Strasser. Graph Bisection with Pareto Optimization. ACM Journal of Experimental Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3173045.
  30. Tobias Heuer, Peter Sanders, and Sebastian Schlag. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. ACM Journal of Experimental Algorithmics (JEA), 24(1):2.3:1-2.3:36, September 2019. URL: https://doi.org/10.1145/3329872.
  31. Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In 16th International Symposium on Experimental Algorithms (SEA), pages 21:1-21:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, June 2017. URL: https://doi.org/10.4230/LIPIcs.SEA.2017.21.
  32. Igor Kabiljo, Brian Karrer, Mayank Pundir, Sergey Pupyrev, Alon Shalita, Yaroslav Akhremtsev, and Alessandro Presta. Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner. In Proceedings of the VLDB Endowment, volume 10, pages 1418-1429, 2017. URL: https://doi.org/10.14778/3137628.3137650.
  33. Gökçehan Kara and Can C. Özturan. Graph Coloring Based Parallel Push-relabel Algorithm for the Maximum Flow Problem. ACM Transactions on Mathematical Software, 45(4):46:1-46:28, 2019. URL: https://doi.org/10.1145/3330481.
  34. George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69-79, 1999. URL: https://doi.org/10.1109/92.748202.
  35. George Karypis and Vipin Kumar. Multilevel k-way Hypergraph Partitioning. VLSI Design, 2000(3):285-300, 2000. URL: https://doi.org/10.1155/2000/19436.
  36. Alexander V. Karzanov. Determining the Maximal Flow in a Network by the Method of Preflows. In Soviet Mathematics Doklady, volume 15, pages 434-437, 1974. Google Scholar
  37. Brian W. Kernighan and Shen Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49(2):291-307, February 1970. Google Scholar
  38. Balakrishnan Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Computers, 33(5):438-446, 1984. URL: https://doi.org/10.1109/TC.1984.1676460.
  39. Kevin J. Lang and Satish Rao. A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. In Proc. of 10th International Integer Programming and Combinatorial Optimization Conference, volume 3064 of LNCS, pages 383-400. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-25960-2_25.
  40. Dominique LaSalle and George Karypis. Multi-Threaded Graph Partitioning. In IEEE Transactions on Parallel and Distributed Systems, pages 225-236. IEEE, 2013. URL: https://doi.org/10.1109/IPDPS.2013.50.
  41. Eugene L. Lawler. Cutsets and Partitions of Hypergraphs. Networks, 3(3):275-285, 1973. URL: https://doi.org/10.1002/net.3230030306.
  42. Sepideh Maleki, Udit Agarwal, Martin Burtscher, and Keshav Pingali. BiPart: A Parallel and Deterministic Hypergraph Partitioner. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 161-174, 2021. URL: https://doi.org/10.1145/3437801.3441611.
  43. Zoltán Á. Mann and Pál A. Papp. Formula Partitioning Revisited. In 5th Pragmatics of SAT Workshop, pages 41-56, 2014. URL: https://doi.org/10.29007/9skn.
  44. Vitaly Osipov and Peter Sanders. n-Level Graph Partitioning. In 18th European Symposium on Algorithms (ESA), pages 278-289. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15775-2_24.
  45. David A. Papa and Igor L. Markov. Hypergraph Partitioning and Clustering. In Handbook of Approximation Algorithms and Metaheuristics. Citeseer, 2007. URL: https://doi.org/10.1201/9781420010749.ch61.
  46. Chuck Pheatt. Intel Threading Building Blocks. Journal of Computing Sciences in Colleges, 23(4):298-298, 2008. Google Scholar
  47. Jean-Claude Picard and Maurice Queyranne. On the Structure of All Minimum Cuts in a Network and Applications. Math. Program., 22(1):121, 1982. URL: https://doi.org/10.1007/BF01581031.
  48. Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical Review E, 76(3):036106, 2007. URL: https://doi.org/10.1103/PhysRevE.76.036106.
  49. Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In 19th European Symposium on Algorithms (ESA), pages 469-480. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_40.
  50. Sebastian Schlag. High-Quality Hypergraph Partitioning. PhD thesis, Karlsruhe Institute of Technology, 2020. URL: https://doi.org/10.5445/IR/1000105953.
  51. Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Christian Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. In 18th Workshop on Algorithm Engineering & Experiments (ALENEX), pages 53-67. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974317.5.
  52. Yossi Shiloach and Uzi Vishkin. An O(n² log n) Parallel Max-Flow Algorithm. Journal of Algorithms, 3(2):128-146, 1982. URL: https://doi.org/10.1016/0196-6774(82)90013-X.
  53. Aleksandar Trifunovic and William J. Knottenbelt. Parkway 2.0: A Parallel Multilevel Hypergraph Partitioning Tool. In International Symposium on Computer and Information Sciences, pages 789-800. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30182-0_79.
  54. Natarajan Viswanathan, Charles J. Alpert, Cliff C. N. Sze, Zhuo Li, and Yaoguang Wei. The DAC 2012 Routability-Driven Placement Contest and Benchmark Suite. In 49th Conference on Design Automation (DAC), pages 774-782. ACM, June 2012. URL: https://doi.org/10.1145/2228360.2228500.
  55. Hannah Honghua Yang and D.F. Wong. Efficient Network Flow Based Min-Cut Balanced Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1533-1540, 1996. URL: https://doi.org/10.1007/978-1-4615-0292-0_41.
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 About DROPS Imprint Privacy Contact