摘要
研究积木块布图的二维压缩问题,提出一种采用分枝定界法的真正的二维压缩算法。该算法以空余空间面积为研究对象,直接以压缩的目的——芯片面积最小化为目标。定义一种压缩树作为分枝定界法的基础。力图将所有的积木块尽可能向芯片的一个角压缩。实验结果表明算法是可行的。
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.
出处
《天津大学学报》
EI
CAS
CSCD
1991年第3期25-29,共5页
Journal of Tianjin University(Science and Technology)
基金
国家自然科学基金资助项目
关键词
积木块
布图
芯片
布线
压缩
VLSI
building-block layout, two-dimensional compaction, branch-and-bound. compaction tree