求解二维矩形Packing面积最小化问题的动态归约算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61173180, 61272014)


Heuristics for Solving the 2D Rectangle Packing Area Minimization Problem Basing on a Dynamic Reduction Method
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    二维矩形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%.

    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%.

    参考文献
    相似文献
    引证文献
引用本文

何琨,姬朋立,李初民.求解二维矩形Packing面积最小化问题的动态归约算法.软件学报,2013,24(9):2078-2088

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-12-03
  • 最后修改日期:2013-01-25
  • 录用日期:
  • 在线发布日期: 2013-09-07
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号