Document Open Access Logo

Network Flow-Based Refinement for Multilevel Hypergraph Partitioning

Authors Tobias Heuer, Peter Sanders, Sebastian Schlag

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.1.pdf
  • Filesize: 3.07 MB
  • 19 pages

Document Identifiers

Author Details

Tobias Heuer
  • Karlsruhe Institute of Technology, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Germany
Sebastian Schlag
  • Karlsruhe Institute of Technology, Germany

Cite As Get BibTex

Tobias Heuer, Peter Sanders, and Sebastian Schlag. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SEA.2018.1

Abstract

We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a k-way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas while still having a running time comparable to that of hMetis.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Multilevel Hypergraph Partitioning
  • Network Flows
  • Refinement

Metrics

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

Related Versions

References

  1. P. Agrawal, B. Narendran, and N. Shivakumar. Multi-way partitioning of VLSI circuits. In 9th International Conference on VLSI Design, pages 393-399, 1996. Google Scholar
  2. 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
  3. C. J. Alpert. The ISPD98 Circuit Benchmark Suite. In International Symposium on Physical Design, (ISPD), pages 80-85, 1998. Google Scholar
  4. C. J. Alpert, J.-H. Huang, and A. B. Kahng. Multilevel Circuit Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(8):655-667, 1998. Google Scholar
  5. C. J. Alpert and A. B. Kahng. Recent Directions in Netlist Partitioning: a Survey. Integration, the VLSI Journal, 19(1-2):1-81, 1995. Google Scholar
  6. C. Aykanat, B. B. Cambazoglu, and B. 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. Google Scholar
  7. D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors. Proc. Graph Partitioning and Graph Clustering - 10th DIMACS Implementation Challenge Workshop, volume 588 of Contemporary Mathematics. AMS, 2013. URL: http://dx.doi.org/10.1090/conm/588.
  8. A. Belov, D. Diepold, M. Heule, and M. Järvisalo. The SAT Competition 2014. http://www.satcompetition.org/2014/, 2014.
  9. T. N. Bui and C. Jones. A Heuristic for Reducing Fill-In in Sparse Matrix Factorization. In SIAM Conference on Parallel Processing for Scientific Computing, pages 445-452, 1993. Google Scholar
  10. Ü. V. Catalyürek and C. Aykanat. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693, Jul 1999. Google Scholar
  11. J. Cong and M. Smith. A Parallel Bottom-up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design. In 30th Conference on Design Automation, (DAC), pages 755-760, 1993. Google Scholar
  12. N. J. Cox. Stata tip 96: Cube roots. Stata Journal, 11(1):149-154(6), 2011. URL: http://www.stata-journal.com/article.html?article=st0223.
  13. 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
  14. 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
  15. W.E. Donath. Logic partitioning. Physical Design Automation of VLSI Systems, pages 65-86, 1988. Google Scholar
  16. J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM, 19(2):248-264, 1972. Google Scholar
  17. C. Fiduccia and R. Mattheyses. A Linear Time Heuristic for Improving Network Partitions. In 19th ACM/IEEE Design Automation Conf., pages 175-181, 1982. Google Scholar
  18. D. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962. Google Scholar
  19. Lester R Ford and Delbert R Fulkerson. Maximal Flow through a Network. Canadian Journal of Mathematics, 8(3):399-404, 1956. Google Scholar
  20. A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. Google Scholar
  21. Andrew Goldberg, Sagi Hed, Haim Kaplan, Robert Tarjan, and Renato Werneck. Maximum Flows by Incremental Breadth-First Search. 19th European Symposium on Algorithms, (ESA), pages 457-468, 2011. Google Scholar
  22. S. Hauck and G. Borriello. An Evaluation of Bipartitioning Techniques. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(8):849-866, 1997. Google Scholar
  23. B. Hendrickson and R. Leland. A Multi-Level Algorithm For Partitioning Graphs. 1995 Conference on Supercomputing, (SC), 0:28, 1995. Google Scholar
  24. T. Heuer. High Quality Hypergraph Partitioning via Max-Flow-Min-Cut Computations. Master’s thesis, KIT, 2018. Google Scholar
  25. T. Heuer and S. Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In 16th International Symposium on Experimental Algorithms, (SEA), page 21:1–21:19, 2017. Google Scholar
  26. Heuer, T. and Sanders, P. and Schlag, S. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning, 2018. URL: http://arxiv.org/abs/1802.03587.
  27. T. C. Hu and K. Moerder. Multiterminal Flows in a Hypergraph. In T.C. Hu and E.S. Kuh, editors, VLSI Circuit Layout: Theory and Design, chapter 3, pages 87-93. IEEE Press, 1985. Google Scholar
  28. E. Ihler, D. Wagner, and F. Wagner. Modeling Hypergraphs by Graphs with the Same Mincut Properties. Information Processing Letters, 45(4):171-175, 1993. URL: http://dx.doi.org/10.1016/0020-0190(93)90115-P.
  29. I. Kabiljo, B. Karrer, M. Pundir, S. Pupyrev, A. Shalita, Y. Akhremtsev, and Presta. A. Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner. PVLDB, 10(11):1418-1429, 2017. Google Scholar
  30. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69-79, 1999. Google Scholar
  31. G. Karypis and V. Kumar. Multilevel K-way Hypergraph Partitioning. In 36th Design Automation Conference, (DAC), pages 343-348. ACM, 1999. Google Scholar
  32. B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49(2):291-307, Feb 1970. Google Scholar
  33. E. Lawler. Cutsets and Partitions of Hypergraphs. Networks, 3(3):275-285, 1973. Google Scholar
  34. E. Lawler. Combinatorial Optimization : Networks and Matroids. Holt, Rinehart, and Whinston, 1976. Google Scholar
  35. T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley &Sons, Inc., 1990. Google Scholar
  36. J. Li, J. Lillis, and C. K. Cheng. Linear decomposition algorithm for VLSI design applications. In 1995 International Conference on Computer Aided Design, (ICCAD), pages 223-228, Nov 1995. Google Scholar
  37. H. Liu and D. F. Wong. Network-Flow-Based Multiway Partitioning with Area and Pin Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(1):50-59, Jan 1998. Google Scholar
  38. Z. Mann and P. Papp. Formula partitioning revisited. In Daniel Le Berre, editor, POS-14. Fifth Pragmatics of SAT workshop, volume 27 of EPiC Series in Computing, pages 41-56. EasyChair, 2014. Google Scholar
  39. H. Meyerhenke, P. Sanders, and C. Schulz. Partitioning Complex Networks via Size-Constrained Clustering. In 13th International Symposium on Experimental Algorithms, (SEA), pages 351-363, 2014. Google Scholar
  40. D. A. Papa and I. L. Markov. Hypergraph Partitioning and Clustering. In T. F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. URL: http://dx.doi.org/10.1201/9781420010749.
  41. Jean-Claude Picard and Maurice Queyranne. On the Structure of all Minimum Cuts in a Network and Applications. Combinatorial Optimization II, pages 8-16, 1980. Google Scholar
  42. Joachim Pistorius and Michel Minoux. An Improved Direct Labeling Method for the Max-Flow Min-Cut Computation in Large Hypergraphs and Applications. International Transactions in Operational Research, 10(1):1-11, 2003. Google Scholar
  43. L. A. Sanchis. Multiple-way Network Partitioning. IEEE Transactions on Computers, 38(1):62-81, 1989. Google Scholar
  44. 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
  45. 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
  46. D. G. Schweikert and B. W. Kernighan. A Proper Model for the Partitioning of Electrical Circuits. In 9th Design Automation Workshop, (DAC), pages 57-62. ACM, 1972. Google Scholar
  47. A. Trifunovic. Parallel Algorithms for Hypergraph Partitioning. PhD thesis, University of London, 2006. Google Scholar
  48. A. Trifunović and W. J. Knottenbelt. Parallel Multilevel Algorithms for Hypergraph Partitioning. Journal of Parallel and Distributed Computing, 68(5):563-581, 2008. Google Scholar
  49. Ü. V. Çatalyürek and M. Deveci and K. Kaya and B. Uçar. UMPa: A multi-objective, multi-level partitioner for communication minimization. In Bader et al. [7], pages 53-66. URL: http://dx.doi.org/10.1090/conm/588.
  50. B. Uçar and C. Aykanat. Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies. SIAM Journal on Scientific Computing, 25(6):1837-1859, 2004. Google Scholar
  51. B. Vastenhouw and R. H. Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67-95, 2005. Google Scholar
  52. N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. In 49th Annual Design Automation Conference, (DAC), pages 774-782. ACM, 2012. Google Scholar
  53. S. Wichlund. On multilevel circuit partitioning. In International Conference on Computer-Aided Design, (ICCAD), ICCAD, pages 505-511. ACM, 1998. Google Scholar
  54. H. H. 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. Google Scholar
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