中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 2: 128 - 140

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.02.010

Research Article

A discrete iterative method for hypergraph bananced bi-partitioning

Expand
  • 1. School of Mathematics and Statistics, Fuzhou University, Fuzhou 350116, Fujian, China
    2. Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350116, Fujian, China

Received date: 2022-04-19

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

Abstract

The problem of hypergraph balanced bipartitioning has become a vital part of very large scale integration circuit physical design. Iterative methods such as Kernighan-Lin and Fiduccia-Mattheyses heuristics have been used to solve this NP-hard problem and perform well. However, these methods have some disadvantages as follows. First, an initial solution of poor quality will easily get trapped in bad local optima. Second, the movement of vertices is restricted to balanced partition. To resolve these issues, we transform the hypergraph bi-partitioning problem into a 0-1 programming. Then an iterative algorithm is designed to solve the problem, which overcomes the shortcomings of traditional iterative algorithms. Our algorithm performs better than Fiduccia-Mattheyses on the ISPD98 hypergraph partitioning benchmarks. Our results have an average improvement of 13.2% over Fiduccia-Mattheyses. If taking our results as initial solutions of the Fiduccia-Mattheyses heuristic, the average cut count is reduced by 30.1%. Moreover, our algorithm can be incorporated into a multilevel partitioning framework, and the partition result has an average improvement of 3.6%.

Key words： hypergraph; balanced bipartitioning; min-cut; 0-1 programming

Cite this article

Xintian LIU, Wenxing ZHU . A discrete iterative method for hypergraph bananced bi-partitioning[J]. Operations Research Transactions, 2025 , 29(2) : 128 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.010

References

1 Wang M, Yang X, Sarrafzadeh M. DRAGON2000: Standard-cell placement tool for large industry circuits [C]//Proceedings of IEEE/ACM International Conference on Computer Aided Design, 2000: 260-263.
2 Pawanekar S, Kapoor K, Trivedi G. Kapees: A new tool for sandard cell placement [M]//VLSI Design and Test, Berlin: Springer, 2013: 66-73.
3 Sahoo D, Iyer S K, Jain J, et al. A partitioning methodology for BDD-based verification [M]//Formal Methods in Computer-Aided Design, Berlin: Springer, 2004: 399-413.
4 Luo S, Liu L, Wang H, et al. Implementation of a parallel graph partition algorithm to speed up BSP computing [C]//$11$th International Conference on Fuzzy Systems and Knowledge Discovery, 2014: 740-744.
5 Ou C , Ranka S . Parallel incremental graph partitioning[J]. IEEE Transactions on Parallel and Distributed Systems, 1997, 8 (8): 884- 896.
6 Devine K D, Boman E G, Heaphy R T, et al. Parallel hypergraph partitioning for scientific computing [C]//Proceedings of the $20$th IEEE International Parallel and Distributed Processing, 2006: 1-10.
7 Zha H, He X, Ding C, et al. Bipartite graph partitioning and data clustering [C]//Proceedings of the $10$th International Conference on Information and Knowledge Management, 2001: 25-32.
8 Catalyurek U V , Aykanat C . Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication[J]. IEEE Transactions on Parallel and Distributed Systems, 1999, 10 (7): 673- 693.
9 Boman E G, Wolf M M. A nested dissection partitioning method for parallel sparse matrix-vector multiplication [C]//IEEE High Performance Extreme Computing Conference, 2013: 1-6.
10 Garey M R , Johnson D S . Computers and Intractability$:$ A Guide to the Theory of NP-Completeness[M]. San Francisco: W.H. Freeman and Company, 1979.
11 Hagen L, Mahng A B. A new approach to effective circuit clustering [C]//Proceedings of IEEE/ACM International Conference on Computer Aided Design, 1992: 422-427.
12 Yang H H, Wong D F. Efficient network flow based min-cut balanced partitioning [M]//The Best of ICCAD$: $ $20$ Years of Excellence in Computer-Aided Design, Boston: Springer US, 2003: 521-534.
13 Jocksch A. A diffusion process for graph partitioning: Its solutions and their improvement [M]//Parallel Processing and Applied Mathematics, Cham, Switzerland: Springer International Publishing, 2016: 218-227.
14 Kernighan B W , Lin S . An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49 (2): 291- 307.
15 Fiduccia C M, Mattheyses R M. A linear-time heuristic for improving network partitions [C]//Proceedings of the $19$th Design Automation Conference, 1982: 175-181.
16 Dutt S. New faster Kernighan-Lin-type graph-partitioning algorithms [C]//Proceedings of IEEE/ACM International Conference on Computer Aided Design, 1993: 370-377.
17 Schweikert D G, Kernighan B W. A proper model for the partitioning of electrical circuits [C]//Proceedings of the $9$th Design Automation Workshop, 1972: 57-62.
18 Hagen L W, Huang D J, Kahng A B. On implementation choices for iterative improvement partitioning algorithms [C]//Proceedings of the Conference on European Design Automation, 1995: 144-149.
19 Krishnamurthy B . An improved min-cut algonthm for partitioning VLSI networks[J]. IEEE Transactions on Computers, 1984, 33 (5): 438- 446.
20 Kirkpatrick S , Gelatt C D , Vecchi M P . Optimization by simulated annealing[J]. Science, 1983, 220 (4598): 671- 680.
21 Bui T N , Moon B R . Genetic algorithm and graph partitioning[J]. IEEE Transactions on Computers, 1996, 45 (7): 841- 855.
22 Johnson D S , Aragon C R , Mcgeoch L A . Optimization by simulated annealing: An experimental evaluation; part 1, graph partitioning[J]. Operations Research, 1991, 37 (6): 865- 892.
23 Pawanekar S, Trivedi G. Analytical Partitioning: Improvement over FM [M]//VLSI Design and Test, Singapore: Springer, 2017: 718-730.
24 Pawanekar S , Kapoor K , Trivedi G . NAP: A nonlinear analytical hypergraph partitioning method[J]. IETE Journal of Research, 2016, 63 (1): 60- 71.
25 Lu J , Chen P , Chang C , et al. ePlace: Electrostatics-based placement using fast Fourier transform and Nesterov's method[J]. ACM Transactions on Design Automation of Electronic Systems, 2015, 20 (2): 1- 34.
26 Chen T , Jiang Z , Hsu T , et al. NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27 (7): 1228- 1240.
27 Karypis G, Aggarwal R, Kumar V, et al. Multilevel hypergraph partitioning: Applications in VLSI domain [C]//Proceedings of the $34$th Annual Design Automation Conference, 1997: 526-529.
28 Caldwell A E, Kahng A B, Markov I L. Improved algorithms for hypergraph bipartitioning [C]//Proceedings of Asia and South Pacific Design Automation Conference, 2000: 661-666.
29 Schlag S, Henne V, Heuer T, et al. K-way hypergraph partitioning via $n$-level recursive bisection [C]//Proceedings of the $18$th Workshop on Algorithm Engineering and Experiments, 2015: 53-67.
30 Aykanatk C , Cambazoglub B B , Ucar B . Multi-level direct $k$-way hypergraph partitioning with multiple constraints and fixed vertices[J]. Journal of Parallel and Distributed Computing, 2008, 68 (5): 609- 625.
31 Vastenhouw B , Bisseling R H . A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[J]. SIAM Review, 2005, 47 (1): 67- 95.
32 Caldwell A, Kahng A B, Markov I. ISPD98 hyergraph partitioning benchmarks [EB/OL]. [2022-04-17]. https://vlsicad.ucsd.edu/UCLAWeb/cheese/ispd98.html.
33 Kennings A, Markov I. Analytical minimization of half-perimeter wirelength [C]//Proceedings of 2000 Design Automation Conference, 2000: 179-184.
34 Alidaee B , Kochenberger G A , Wang H . Theorems supporting $r$-flip search for pseudo-boolean optimization[J]. International Journal of Applied Metaheuristic Computing, 2010, 1 (1): 93- 109.
Options
Outlines

/

〈 〉