Constructing maximal slicings from geometry

DOI10.1007/BF00289114MaRDI QIDQ1088412zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00289114

zbMATH Keywords

floorplanninghierarchicial global wiringisothetic non-overlapping rectanglesmacrosmaximal slicing treeVLSI custom chip design

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• Maximal cuts in arbitrary dimension
• Maximal slicings in spherical symmetry: Local existence and construction
• The geometry of the slice-ribbon problem
• ON RECONSTRUCTING POLYHEDRA FROM PARALLEL SLICES
• Slicing convex sets and measures by a hyperplane
• Slicing convex sets and measures by a hyperplane
• Maximal hyperplane sections of convex bodies
• Geometry of cuts and metrics
• Geometry of cuts and metrics
• The geometry of strict maximality

Cites work

• A note on the modeling space of Euler operators
• Optimal orientations of cells in slicing floorplan designs
• The Recognition of Series Parallel Digraphs

Cited in

(2)

• Complexity and approximability results for slicing floorplan designs.
• Minimum-Area Wiring for Slicing Structures

This page was built for publication: Constructing maximal slicings from geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1088412)