一种求解矩形块布局问题的拟物拟人算法  

An Efficient Quasi-physical and Quasi-human Block-packing Algorithm

作　　者：黄文奇[1] 陈端兵[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2005年第11期182-186,共5页Computer Science

基　　金：国家自然科学基金10471051

摘　　要：在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法。本文以人类上万年以来形成的经验为基础,利用“占角”和“聚类”两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局算法。用本文提出的算法,对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试,测试结果表明:计算所得布局结果的优度高,计算时间短。对MCNC和GSRC测试算例,除apte实例外,其它所有实例均得到了最优解,而计算时间都在10秒以内。与CBL算法、遗传算法和号称当今最好的CompaSS算法相比,本文算法所得结果的优度更高,计算时间更短。进一步的测试表明,本文提出的拟物拟人布局算法为当今的一种高效算法。A block-packing problem is raised in VLSI design. Many algorithms such as simulation annealing and genetic algorithm have been proposed to solve this problem. According to ten-thousand-year experience of human beings and two important quasi-physical and quasi-human strategies, i.e., comer-occupying and clustering, an efficient quasiphysical and quasi-human block-packing algorithm based on maximum cave degree first is proposed in this paper. Some benchmarks, such as MCNC and GSRC, are tested by the proposed algorithm, and high quality results are achieved in short runtime. All MCNC benchmarks, except apte, and all GSRC benchmarks can be packed with zero dead-space, while the runtime is less than 10 seconds. As compared with CBL, genetic algorithm and CompaSS, reputed to be the best block-packing algorithm up to now, the results are much better both in less dead-space and less runfime. Results of further experiments demonstrate that the algorithm proposed in this paper is a highly efficient algorithm nowadays.

关 键 词：PACKING VLSI布图规划 拟物拟人算法 占角动作 聚类 布局问题 求解算法 矩形 COMPASS 计算时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O22[自动化与计算机技术—计算机科学与技术]