| 摘要: |
| 二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%. |
| 关键词: NP难度 布局优化 布图规划 面积最小化 启发式 |
| DOI：10.3724/SP.J.1001.2013.04404 |
| 分类号: |
| 基金项目:国家自然科学基金(61173180, 61272014) |
|
| Heuristics for Solving the 2D Rectangle Packing Area Minimization Problem Basing on a Dynamic Reduction Method |
|
HE Kun1, JI Peng-Li1, LI Chu-Min1,2
|
|
1.School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;2.School of Computer Science and Technology, University of Picardie Jules Verne, Amiens 80039, France
|
| Abstract: |
| This paper addresses an NP-hard layout optimization problem with a high computational complexity: the two-dimensional rectangle packing area minimization problem (RPAMP), which is a core issue of floorplanning problem in the very-large-scale integration (VLSI) design. First, by dynamically designing the two dimensions of the large rectangular frame, the study reduces the solving of a RPAMP to the solving of a series of two-dimensional rectangle packing decision problems (RPDP). Then, based on a best-fit-degree approach for the RPDP, the designs a least-damage-first algorithm for the RPDP, which further takes the consideration of the current placement's impact on global compaction and of its negative effect on local space's integrity. Next, by combining the method of dynamically designing two dimensions of the rectangular frame, a final dynamic reduction algorithm is proposed for solving the RPAMP. Experiments were on 15 RPAMP instances (including the well-known MCNC instances and GSRC instances). Computational results show that the proposed algorithm refreshed the current best solutions on nine instances. At the same time it also matchs the current best records on two other instances. The obtained average filling rate is 98.50%, which improved the current best results reported in the literature by 0.85%. |
| Key words: NP hard layout optimization floorplanning area minimization heuristic |
