An algorithm for optimal two-dimensional compaction of VLSI layouts

The two-dimensional compaction problem in VLSI layouts is considered. The basic building blocks are assumed to be rectangles with input, output terminals on the boundary. Furthermore, they are connected by wires which have fixed width but can be stretched or shrunk. Jogs are allowed. The goal is to compact the layout subject to minimum distance constraints and topological constraints such that its bounding rectangle has minimum area. Instead of the widely used, two consecutive one-dimensional compaction approach, we attempt to do compaction simultaneously in both directions. The problem is formulated rigorously and is proven to be NP-complete. Then a branch-and-bound search algorithm is proposed. This algorithm starts with a totally collapsed layout (except for topological constraints) and then removes the distance violations one by one intelligently, keeping only the best legal layout obtained so far. By careful consideration of the constraints, the search tree can be efficiently pruned in many ways. © 1983 Elsevier Science Publishers B.V.