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

    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. This approach reformulates the RPAMP as a series of two-dimensional strip packing problems (SPP) for solution. In the first stage, an adaptive selection strategy is employed to fix the width of RPAMP to the candidate width corresponding to the minimum area lower bound, thereby converting the problem into a series of strip packing problems. In the second stage, an exact solution algorithm based on Benders′ decomposition is proposed to solve the strip packing problem. First, by fixing the height of the strips, the problem is transformed into a two-dimensional rectangle packing problem (RPP). Then, the RPP is decomposed into a master problem and subproblems, with cutting planes 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 iterative computation 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 a reasonable time, especially for the instance n10, where a better solution than that in the literature was found.

       

    /

    返回文章
    返回