%0 Journal Article
%T An Efficient Quasi-physical and Quasi-human Block-packing Algorithm<br>一种求解矩形块布局问题的拟物拟人算法
%A HUANG WemQi
%A CHEN DuamBing
%A <br>黄文奇
%A 陈端兵
%J 计算机科学
%D 2005
%I 
%X 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.
%K Packing
%K VLSI floorplanning
%K Quasi-physical and quasi-human algorithm
%K Corner-occupying action
%K Clustering<br>Packing
%K VLSI布图规划
%K 拟物拟人算法
%K 占角动作
%K 聚类
%K 布局问题
%K 求解算法
%K 矩形
%K CompaSS
%K 计算时间
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=F76D1A60505EF420&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=708DD6B15D2464E8&sid=B1F98368A47B8888&eid=50BBDFAC8381694B&journal_id=1002-137X&journal_name=计算机科学&referenced_num=2&reference_num=12