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

AN OPTIMIZED TWO-DIMENSIONAL COMPACTION OF BUILDING-BLOCK LAYOUT

研究积木块布图的二维压缩问题,提出一种采用分枝定界法的真正的二维压缩算法。该算法以空余空间面积为研究对象,直接以压缩的目的——芯片面积最小化为目标。定义一种压缩树作为分枝定界法的基础。力图将所有的积木块尽可能向芯片的一个角压缩。实验结果表明算法是可行的。

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.