平面集成电路布图规划面积最小化精确求解方法

An Exact Method for Area Minimization in Planar Integrated Circuit Floorplanning

摘要

为解决集成电路平面布图规划问题中的布图模块面积最小化问题 (RPAMP)，提升电路运行效率，提出了一种宏观问题转换的两阶段精确求解方法。该方法将 RPAMP 转化为一系列二维条带装箱问题 (SPP) 进行求解。第 1 阶段，通过自适应选择策略，将 RPAMP 的宽度固定为最小面积下界对应的候选宽度，从而将问题转化为一系列的条带装箱问题进行求解。第 2 阶段，提出一种基于 Benders′ 分解的精确求解算法来解决条带装箱问题。首先，固定条带的高度，将其转化为二维矩形装箱问题 (RPP)。随后，将 RPP 分解为主问题和子问题，并不断添加割平面来逼近问题最优解。如果 RPP 不可行，则记录当前条带的下界高度并重新选择候选宽度进行迭代计算，直至找到 RPAMP 的最优解。实验结果表明，所提出的方法能够在合理的时间内为中小型实例找到最佳解决方案，特别是对于实例 n10，找到了比文献中更优的解决方案。

Abstract

To address the rectangular packing area minimization problem (RPAMP) in integrated circuit floorplanning and improve circuit performance, a two-stage exact algorithm based on macro problem transformation is proposed. The RPAMP is reformulated as a series of two-dimensional strip packing problems (SPP) for solution. In the first stage, an adaptive selection strategy is employed to set the width of RPAMP to the candidate width corresponding to the minimum-area lower bound, thereby converting the problem into a series of SPPs. In the second stage, an exact solution algorithm based on Benders′ decomposition is proposed to solve the SPP. Specifically, by fixing the height of strips, the problem is transformed into a two-dimensional rectangle packing problem (RPP). Then, the RPP is decomposed into a master problem and subproblems, and cutting planes are added iteratively to approximate the optimal solution. If the RPP is infeasible, the current lower bound of the strip height is recorded, and a new candidate width is selected for iteration until the optimal solution to the RPAMP is found. Experimental results show that the proposed method can find the optimal solution for small to medium-sized instances within reasonable computational time. In particular, for instance n10, it derives a better solution than that obtained in the literature.

关键词

平面规划 / 面积最小化 / 条带装箱 / 精确算法 / Benders′ 分解

Key words

floorplanning / area minimization / strip packing / exact algorithm / Benders′ decomposition

参考文献

[1] 史梓慧, 欧阳丹彤, 张立明. 超大规模集成电路布图规划方法研究综述[J]. 吉林大学学报 (理学版), 2025, 63(1): 139-150.

[2] Shi Zihui, Ouyang Dantong, Zhang Liming. Research review of floorplanning methods for very large scale integration[J]. Journal of Jilin University (Science Edition), 2025, 63(1): 139-150.

[3] Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packing by the sequence-pair[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, 15(12): 1518-1524.

[4] Lin J M, Chang Y W. TCG: a transitive closure graph-based representation for non-slicing floorplans[C/OL]// Proceedings of the 38th annual Design Automation Conference. (2005-05-23). https://ieeexplore.ieee.org/document/935608.

[5] Guo P N, Cheng C K, Yoshimura T. An O-tree representation of non-slicing floorplan and its applications[C/OL]// Proceedings of the 36th annual ACM/IEEE Design Automation Conference. USA: New Orleans. (2002-08-06). https://ieeexplore.ieee.org/document/781324.

[6] Chang Y C, Chang Y W, Wu G M, et al. B*-trees: a new representation for non-slicing floorplans [C/OL]// Proceedings of the 37th Annual Design Automation Conference. USA: Los Angeles. (2002-08-06). https://ieeexplore.ieee.org/document/855354.

[7] Tang X, Tian R, Wong D. Fast evaluation of sequence pair in block placement by longest common subsequence computation[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000, 20(12): 106-111.

[8] 赵耀忠. 求解 VLSI 布图规划问题的自适应迭代模拟退火算法研究[D]. 武汉: 华中科技大学, 2024.

[9] Tang M, Yao X. A memetic algorithm for VLSI floorplanning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(1): 62-69.

[10] 郑建山. 基于多目标优化的 VLSI 版图规划算法研究[D]. 福州: 福州大学, 2019.

[11] Yao W, Lin Y, Li L. Learning placement order for constructive floorplanning[J]. Integration, 2025, 100: 102293.

[12] Bortfeldt A. A reduction approach for solving the rectangle packing area minimization problem[J]. European Journal of Operational Research, 2013, 224(3): 486-496.

[13] He K, Ji P, Li C. Dynamic reduction heuristics for the rectangle packing area minimization problem[J]. European Journal of Operational Research, 2015, 241(3): 674-685.

[14] Wei L, Zhu W, Lim A, et al. An adaptive selection approach for the 2D rectangle packing area minimization problem[J]. Omega, 2018, 80: 22-30.

[15] Clautiaux F, Carlier J, Moukrim A. A new exact method for the two-dimensional orthogonal packing problem[J]. European Journal of Operational Research, 2007, 183(3): 1196-1211.

[16] Alvarez-Valdes R, Parreño F, Tamarit J M. A branch and bound algorithm for the strip packing problem[J]. OR Spectrum, 2009, 31: 431-459.

[17] Boschetti M A, Montaletti L. An exact algorithm for the two-dimensional strip-packing problem[J]. Operations Research, 2010, 58(6): 1774-1791.

[18] Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem[J]. INFORMS Journal on Computing, 2003, 15(3): 310-319.

[19] Rahmaniani R, Crainic T G, Gendreau M, et al. The Benders decomposition algorithm: a literature review[J]. European Journal of Operational Research, 2017, 259(3): 801-817.

[20] Côté J F, Dell'amico M, Iori M. Combinatorial Benders′ cuts for the strip packing problem[J]. Operations Research, 2014, 62(3): 643-661.

[21] Burke E K, Kendall G, Whitwell G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4): 655-671.

[22] Aşik Ö B, Özcan E. Bidirectional best-fit heuristic for orthogonal rectangular strip packing[J]. Annals of Operations Research, 2009, 172: 405-427.

[23] Imahori S, Yagiura M. The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio[J]. Computers & Operations Research, 2010, 37(2): 325-333.

[24] Yang S, Han S, Ye W. A simple randomized algorithm for two-dimensional strip packing[J]. Computers & Operations Research, 2013, 40(1): 1-8.

[25] Wei L, Hu Q, Leung S, et al. An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation[J]. Computers & Operations Research, 2017, 80: 113-127.

[26] 孙健, 徐宁, 吴建, 等 . 一种基于共轭次梯度算法的非光滑布图规划方法[J]. 计算机应用研究, 2024, 41(9): 2751-2757.

[27] Sun Jian, Xu Ning, Wu Jian, et al. Non-smooth floorplanning method based on conjugate sub-gradient algorithm[J]. Application Research of Computers, 2024, 41(9): 2751-2757.

[28] Chan H H, Markov I L. Practical slicing and non-slicing block-packing without simulated annealing[C/OL]// Proceedings of the 14th ACM Great Lakes Symposium on VLSI. (2004-04-26). 2004: 282-287. https://dl.acm.org/doi/10.1145/988952.989020.

[29] Tsai J, Wang P, Lin M. An efficient deterministic optimization approach for rectangular packing problems[J]. Optimization, 2013, 62(7): 989-1002.

[30] Yao S, Zhang H, Liu Q, et al. Combinatorial Benders′ decomposition for the constrained two-dimensional non-guillotine cutting problem with defects[J]. International Journal of Production Research, 2024, 62(23): 8299-8325.

[31] Côté J, Iori M. The meet-in-the-middle principle for cutting and packing problems[J]. INFORMS Journal on Computing, 2018, 30(4): 646-661.

[32] Carlier J, Clautiaux F, Moukrim A. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation[J]. Computers & Operations Research, 2007, 34(8): 2223-2250.

基金资助

国家自然科学基金面上项目(72271062)

国家自然科学基金面上项目(52575565)

广东省自然科学基金杰出青年项目(2022B1515020076)