CAJ | 학술논문

二维矩形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％.
이유구형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％.