超图平衡二划分的离散迭代优化算法

doi:10.15960/j.cnki.issn.1007-6093.2025.02.010

Abstract

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

CLC Number:

O221.2

Xintian LIU, Wenxing ZHU. A discrete iterative method for hypergraph bananced bi-partitioning[J]. Operations Research Transactions, 2025, 29(2): 128-140.

Figures/Tables 4

电路	FM						1-邻域搜索
电路	最小值	比例	均值	比例	时间/s	比例	最小值	比例	均值	比例	时间/s	比例
ibm01	365	1	528.5	1	0.43	1	425	1.164	710.3	1.344	1.20	2.788
ibm02	337	1	465.9	1	0.79	1	449	1.332	916.0	1.966	4.24	5.369
ibm03	1 205	1	2 383.6	1	0.88	1	2 284	1.895	3 693.5	1.550	3.89	4.415
ibm04	830	1	1 579.2	1	1.05	1	1 221	1.471	2 981.0	1.888	4.42	4.211
ibm05	2 725	1	3 255.4	1	2.53	1	3 113	1.142	5 216.9	1.603	7.91	3.126
ibm06	1 003	1	1 517.8	1	1.71	1	2 187	2.180	4 303.0	2.835	6.64	3.880
ibm07	1 242	1	1 902.2	1	2.93	1	1 607	1.294	3 079.6	1.619	8.57	2.926
ibm08	1 505	1	3 008.2	1	2.45	1	1 752	1.164	4 600.5	1.529	17.16	7.003
ibm09	826	1	5 894.2	1	4.19	1	2 166	2.622	8 640.1	1.466	15.41	3.678
ibm10	1 907	1	2 598.8	1	4.39	1	2 697	1.414	3 635.0	1.399	20.58	4.689
ibm11	1 988	1	4 304.5	1	8.97	1	3 989	2.007	6 364.8	1.479	18.21	2.030
ibm12	3 196	1	4 191.2	1	6.31	1	6 999	2.190	10 350.1	2.469	20.17	3.197
ibm13	1 336	1	1 944.1	1	8.60	1	1 841	1.378	3 553.0	1.828	25.52	2.968
ibm14	4 285	1	6 984.3	1	13.88	1	7 153	1.669	12 523.2	1.793	105.56	7.605
ibm15	7 441	1	8 761.8	1	14.24	1	9 921	1.333	13 869.3	1.583	97.73	6.863
ibm16	3 655	1	8 556.9	1	22.48	1	4 701	1.286	12 892.7	1.507	178.91	7.959
ibm17	4 263	1	6 878	1	24.09	1	9 864	2.314	18 078.7	2.628	216.28	8.978
ibm18	2 016	1	3 564.3	1	28.06	1	4 428	2.196	8 043.3	2.257	248.15	8.844
平均		1		1		1		1.670		1.819		5.029

电路	本文的算法						本文的算法叠加FM算法
电路	最小值	比例	均值	比例	时间/s	比例	最小值	比例	均值	比例
ibm01	251	0.688	412.3	0.780	3.43	7.977	222	0.608	348.8	0.660
ibm02	306	0.908	404.7	0.869	13.13	16.620	266	0.789	337.8	0.725
ibm03	1 397	1.159	2 058.9	0.864	9.36	10.636	1 088	0.903	1 678.9	0.704
ibm04	762	0.918	1 509.6	0.956	10.67	10.162	660	0.795	1 074.9	0.681
ibm05	2 141	0.786	2 428.4	0.746	19.41	7.672	1 849	0.679	2 179.6	0.670
ibm06	1 070	1.067	1 737.3	1.145	14.88	8.702	903	0.900	1 430.3	0.942
ibm07	1 069	0.861	1 732.1	0.911	23.46	8.007	738	0.594	1 247.5	0.656
ibm08	1 543	1.025	2 194.4	0.729	49.43	20.176	1 315	0.874	1 768.9	0.588
ibm09	843	1.021	2 501.5	0.424	35.47	8.465	795	0.962	2 055.1	0.349
ibm10	1 590	0.834	2 232.6	0.859	47.49	10.818	1 269	0.665	1 789.1	0.688
ibm11	1 712	0.861	3 246.4	0.754	48.14	5.367	1 423	0.716	3 093.1	0.719
ibm12	3 127	0.978	4 088.8	0.976	57.95	9.184	2 248	0.703	3 273.2	0.781
ibm13	1 450	1.085	2 085.2	1.073	71.18	8.277	1 218	0.912	1 595.0	0.820
ibm14	3 188	0.744	5 407.9	0.774	277.19	19.970	2 145	0.501	4 475.6	0.641
ibm15	5 606	0.753	8 383.8	0.957	258.679	18.166	4 907	0.659	6 532.4	0.746
ibm16	2 888	0.790	6 322.3	0.739	486.338	21.634	2 199	0.602	5 159.8	0.603
ibm17	3 993	0.937	6 961.9	1.012	650.93	27.021	3 497	0.820	5 445.4	0.792
ibm18	2 045	1.014	3 745.0	1.051	794.63	28.319	1 775	0.880	2 943.4	0.826
平均		0.913		0.868		13.732		0.754		0.699

References 34

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. doi: 10.1109/71.605773
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. doi: 10.1109/71.780863
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. doi: 10.1002/j.1538-7305.1970.tb01770.x
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. doi: 10.1126/science.220.4598.671
21	Bui T N , Moon B R . Genetic algorithm and graph partitioning[J]. IEEE Transactions on Computers, 1996, 45 (7): 841- 855. doi: 10.1109/12.508322
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. doi: 10.1109/TCAD.2008.923063
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. doi: 10.1016/j.jpdc.2007.09.006
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. doi: 10.1137/S0036144502409019
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. doi: 10.4018/jamc.2010102605

电路	单元	I/O	模块	线网	引脚	电路	单元	I/O	模块	线网	引脚
ibm01	12 506	246	12 752	14 111	50 566	ibm10	68 685	744	69 429	75 196	297 567
ibm02	19 342	259	19 601	19 584	81 199	ibm11	70 152	406	70 558	81 454	280 786
ibm03	22 853	283	23 136	27 401	93 573	ibm12	70 439	637	71 076	77 240	317 760
ibm04	27 220	287	27 507	31 970	105 859	ibm13	83 709	490	84 199	99 666	357 075
ibm05	28 146	1 201	29 347	28 446	126 308	ibm14	147 088	517	147 605	152 772	546 816
ibm06	32 332	166	32 498	34 826	128 182	ibm15	161 187	383	161 570	186 608	715 823
ibm07	45 639	287	45 926	48 117	175 639	ibm16	182 980	504	183 484	190 048	778 823
ibm08	51 023	286	51 309	50 513	204 890	ibm17	184 752	743	185 495	189 581	860 036
ibm09	53 110	285	53 395	60 902	222 088	ibm18	210 341	272	210 613	201 920	819 697

电路	MLPart			将本文的算法用在MLPart的初始划分阶段
电路	最小值	均值	时间/s	最小值	比例	均值	比例	时间/s	比例
ibm01	215	242.1	1.35	215	1.000	243.1	1.004	1.71	1.267
ibm02	255	291.1	1.98	250	0.980	269.0	0.924	9.93	5.015
ibm03	657	779.7	4.94	640	0.974	716.1	0.918	8.16	1.652
ibm04	453	497.4	2.44	441	0.974	470.7	0.946	9.39	3.848
ibm05	1 744	1 763.2	4.05	1 706	0.978	1 749.4	0.992	8.14	2.010
ibm06	363	401.8	2.97	364	1.003	382.1	0.951	7.93	2.670
ibm07	760	799.4	6.81	737	0.970	787.7	0.985	12.58	1.847
ibm08	1 170	1 205.0	5.93	1 137	0.972	1 196.2	0.993	22.27	3.755
ibm09	534	676.6	5.80	528	0.989	657.0	0.971	9.44	1.628
ibm10	817	1 037.1	9.15	792	0.969	957.0	0.923	19.26	2.105
ibm11	721	792.2	7.65	714	0.990	773.8	0.977	11.53	1.507
ibm12	2 174	2 265.1	9.57	2 177	1.001	2 254.8	0.995	10.52	1.099
ibm13	927	1 098.6	11.83	902	0.973	1 033.1	0.940	13.16	1.112
ibm14	1 579	1 761.2	17.56	1 511	0.957	1 628.1	0.924	38.35	2.184
ibm15	1 918	2 292.4	18.67	1 806	0.942	2 193.5	0.957	45.78	2.452
ibm16	1 671	1 805.1	23.64	1 665	0.996	1 772.9	0.982	41.22	1.744
ibm17	2 279	2 390.4	31.39	2 229	0.978	2 334.8	0.977	57.55	1.833
ibm18	1 552	1 628.5	23.49	1 526	0.983	1 616.7	0.993	59.55	2.535
平均					0.979		0.964		2.237

[1]	Guidong YU, Hui YUAN, Xinyu XIE. The second largest signless Laplacian spectral radius of uniform supertree with diameter [J]. Operations Research Transactions, 2025, 29(4): 241-248.
[2]	Zhiwei WU, Liying KANG. The extremal p-spectral radius of cancellative hypergraphs [J]. Operations Research Transactions, 2025, 29(2): 194-200.
[3]	Yu YANG, Zhongxun ZHU, Junpeng ZHOU. The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius [J]. Operations Research Transactions, 2025, 29(1): 185-197.
[4]	Wenrong LYU, Erfang SHAN. The Banzhaf value for hypergraph communication situations [J]. Operations Research Transactions, 2023, 27(3): 159-168.
[5]	Die WANG, Liying KANG. Tensor spectral properties of general hypergraphs [J]. Operations Research Transactions, 2023, 27(1): 138-148.
[6]	HAN Jiayu, YU Zhiqiang, ZHAO Jiagui, SHAN Erfang. The within groups and the between groups Position values on hypergraph games [J]. Operations Research Transactions, 2022, 26(4): 107-118.
[7]	Jing ZHAO, Erfang SHAN, Jiagui ZHAO. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131.
[8]	TONG Linken, SHAN Erfang. The restricted edge-connectivity and λ'-optimality of hypergraphs [J]. Operations Research Transactions, 2020, 24(4): 145-152.
[9]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[10]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[11]	SUI Yunkang, LI Zhenzhen, LI Hong, CHEN Guoqing. Continuous solution method for 0-1 programming based on the sinusoidal smooth polish function [J]. Operations Research Transactions, 2017, 21(3): 35-44.
[12]	LI Shan, SHAN Erfang, ZHANG Lin. A note on total domination in 5-regular graphs [J]. Operations Research Transactions, 2017, 21(1): 125-128.
[13]	LIN Yi, NI Zhenyu, SHAN Erfang. Total transversals in 5-uniform hypergraphs [J]. Operations Research Transactions, 2016, 20(2): 97-104.
[14]	ZHANG Xinyue, HUANG Zhenghai, LI Zhiming. A face recognition method based on discriminative hypergraph and nonnegative matrix factorization [J]. Operations Research Transactions, 2015, 19(3): 108-115.
[15]	ZHANG Huizhen, WEI Xin, MA Liang. The bounded simplex method to solve the 0-1 linear integer programming problem [J]. Operations Research Transactions, 2014, 18(3): 71-78.

A discrete iterative method for hypergraph bananced bi-partitioning

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 34

Related Articles 15

Recommended Articles

Metrics

Comments