12/01/1997 09:00 AM
Computer Engineering
As the increasing complexity of IC design, layout reuse becomes more important. The design for renewed fabrication processes usually maintains the layout technology but using different design rules. First we extract devices and group them as a set of macro device blocks. After shrinking the macro device blocks, we would like to pack the rectilinear shaped blocks together while maintaining the original topological relationship. Such problem is referred to as Topology Constrained Rectilinear Block Packing problem. In this paper, we propose an efficient data representation for a special class of rectilinear polygons, called Ordered Convex Rectilinear Polygons, using Bounded Slicing Grid (BSG) structure. Based on both Sequence Pair (SP) and BSG structure, we propose an algorithm, which independently compacts x and y dimension under the topology constraints given the blocks are ordered convex shapes. By augumenting or further partitioning the arbitrary rectilinear polygons into the ordered convex shapes, this method can be extended to handle the general rectilinear shaped blocks.
