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

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

摘要/Abstract

摘要：

超图平衡二划分是超大规模集成电路物理设计的重要一环。Kernighan-Lin算法和Fiduccia-Mattheyses算法等迭代优化算法是求解该NP-困难问题的常用方法。然而, 这些算法具有以下缺点: 一是对于较差的初始解, 算法容易陷入局部最优。二是由于平衡条件的约束, 顶点的移动受到诸多限制。针对上述问题, 本文将超图平衡二划分问题转化为0-1规划问题, 并设计了求解该问题的离散迭代算法, 在一定程度上克服了传统的迭代算法受平衡条件与初始解约束的缺点。在ISPD98电路划分测试样例上, 本文的算法取得了比Fiduccia-Mattheyses算法质量更高的解。在20次随机实验中, 本文的平均割边数比Fiduccia-Mattheyses算法少13.2%。将本文的结果作为Fiduccia-Mattheyses算法的初始解作进一步优化, 所产生的平均割边数比Fiduccia-Mattheyses算法少30.1%。不仅如此, 本文的算法还可以嵌入到多级划分算法框架中, 取得的平均割边数比multilevel partitioning (MLPart) 少3.6%。

关键词: 超图, 平衡二划分, 最小割, 0-1规划

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

中图分类号:

O221.2

刘欣恬, 朱文兴. 超图平衡二划分的离散迭代优化算法[J]. 运筹学学报（中英文）, 2025, 29(2): 128-140.

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

图/表 4

图1

表1

表2

本文的算法与常用超图划分算法的对比"

电路	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

表2

表3

参考文献 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]	吴志伟, 康丽英. 可消去超图p-谱半径的极值问题[J]. 运筹学学报（中英文）, 2025, 29(2): 194-200.
[2]	杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.
[3]	吕文蓉, 单而芳. 具有超图合作结构的Banzhaf值[J]. 运筹学学报, 2023, 27(3): 159-168.
[4]	王蝶, 康丽英. 一般超图的张量谱性质[J]. 运筹学学报, 2023, 27(1): 138-148.
[5]	韩佳玉, 于志强, 赵加贵, 单而芳. 超图对策的组内和组间位置值[J]. 运筹学学报, 2022, 26(4): 107-118.
[6]	赵静, 单而芳, 赵加贵. 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021, 25(1): 123-131.
[7]	童林肯, 单而芳. 超图的限制边连通度与最优限制边连通[J]. 运筹学学报, 2020, 24(4): 145-152.
[8]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.
[9]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[10]	隋允康, 李臻臻, 李宏, 陈国庆. 基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法[J]. 运筹学学报, 2017, 21(3): 35-44.
[11]	李姗, 单而芳, 张琳. 5-正则图的全控制数的一个注记[J]. 运筹学学报, 2017, 21(1): 125-128.
[12]	林苡, 倪振羽, 单而芳. 5-一致超图的全横贯[J]. 运筹学学报, 2016, 20(2): 97-104.
[13]	张欣玥, 黄正海, 李志明. 基于判别超图和非负矩阵分解的人脸识别方法[J]. 运筹学学报, 2015, 19(3): 108-115.
[14]	张惠珍, 魏欣, 马良. 求解0-1线性整数规划问题的有界单纯形法[J]. 运筹学学报, 2014, 18(3): 71-78.