一种积木块布图的优化二维压缩算法  

AN OPTIMIZED TWO-DIMENSIONAL COMPACTION OF BUILDING-BLOCK LAYOUT

作　　者：朱雪花[1] 刘美轮 

机构地区：[1]天津大学电力及自动化工程系

出　　处：《天津大学学报》1991年第3期25-29,共5页Journal of Tianjin University(Science and Technology)

基　　金：国家自然科学基金资助项目

摘　　要：研究积木块布图的二维压缩问题,提出一种采用分枝定界法的真正的二维压缩算法。该算法以空余空间面积为研究对象,直接以压缩的目的——芯片面积最小化为目标。定义一种压缩树作为分枝定界法的基础。力图将所有的积木块尽可能向芯片的一个角压缩。实验结果表明算法是可行的。The two-dimensional compaction problem of building-block layout is considered in this paper. Unlike the existing compaction algorithms, we present a truly two-dimensional compaction scheme which starts off with the point of view of two-dimension, looks spare space of a block as considered object and chip area as objective function directly. In the approach, using a branch-and-bound algorithm on the basis of a compaction tree, we attempt to move all blocks towards a corner of the chip. The experimental results have shown that the method is effective.

关 键 词：积木块 布图 芯片 布线 压缩 VLSI 

分 类 号：TN402[电子电信—微电子学与固体电子学]