Constructing maximal slicings from geometry

Summary We present an optimal algorithm to determine whether a placement of N isothetic non-overlapping rectangles (macros) can be represented by a slicing tree, and if so, to find a representation of minimal height. A slicing is a recursive partition of the overall bounding rectangle, by straight horizontal or vertical cuts, into rectangular regions, each one containing exactly one macro. The algorithm first determines a representation of the empty space of the placement by means of maximally extended horizontal and vertical channels. A second phase then generates a maximal slicing tree (an ordered tree with unbounded degree and maximal branching, i.e., minimal height) in a top-down fashion. The complexity of each phase is O(N log N). The problem arises in steps (1) and (2) of our top-down approach to VLSI custom chip design, which consists of (1) floorplanning by slicing, (2) hierarchicial global wiring, and (3) detailed layout of macros.On leave from: Laboratory of Information Processing Science, Helsinki University of Technology, Espoo, FinlandOn leave from: Dipartimento di Elettrotecnica, Elettronica e Informatica, Università degli Studi di Trieste, Via Valerio, 10-34127 Trieste, Italy