About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Integration, the VLSI Journal
Paper
An algorithm for optimal two-dimensional compaction of VLSI layouts
Abstract
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.