A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.

The detection of timing constraint violation is crucial in reactive systems. A method of detecting deadline violation based on Floyd-Warshall shortest path algorithm has been proposed by Chodrow et al. We extend this method to detect the violation of minimum delay time in reactive systems where the repetition of event sequences frequently occurs.

This paper describes a procedural detailed compaction method for the symbolic layout design of CMOS leaf cells and its algorithmic aspects. Simple symbolic representations that are loosely designed by users in advance are automatically converted into densely compacted physical patterns in two phases: symbolic–to–pattern conversion and segment–based detailed compaction. Both phases are executed using user-defined procedures and a specified set of design rules. The detailed compaction utilizes a segment–based constraint graph generated by an extended plane sweep method where various kinds of design rules can be applied. Since various kinds of basic operations can be applied to the individual segments of patterns in the procedures, the detailed procedure for processing can be described in accordance with fabrication process technologies and the corresponding sets of design rules. This combined stepwise procedure provides a highly flexible framework for the symbolic layout of CMOS leaf cells. The proposed approach was implemented in a symbolic layout system called CAMEL. To date, more than 300 kinds of symbolic representations of CMOS leaf cells have been designed and are stored in the database. Using several different sets of design rules, symbolic representations have been automatically converted into compacted patterns without design rule violations. The areas of those generated patterns were averaged at 98% of the manually designed patterns. Even in the worst case, the increases in area were less than about 10% of the manually designed ones. Furthermore, since processing times are much shorter than manual design periods, for example, 300 kinds of symbolic representations can be converted to corresponding physical patterns in only a day. It is evident, through these practical design experiences with CAMEL, that our approach is more flexible and process–tolerant than conventional ones.

This paper describes a preconstrained compaction method and its application to the direct design-rule conversion of CMOS layouts. This approach can convert already designed physical patterns into compacted layouts that satisfy user-specified design rules. Furthermore, preconstrained compaction can eliminate unnecessarily extended diffusion areas and polysilicon wires which tend to be created with conventional longest path based compactions. Preconstrained compaction can be constructed by combining a longest path algorithm with forward and backward slack processes and a preconstraint generation process. This contrasts with previously proposed approaches based on longest path algorithms followed by iterative improvement processes, which include applications of linear programming. The layout styles in those approaches are usually limited to a model where fixed-shaped rectilinear blocks are moved so as to minimize the total length of rectilinear interconnections among the blocks. However, preconstrained compaction can be applied to reshaping polygonal patterns such as diffusion and channel areas. Thus, this compaction method makes it possible to reuse CMOS leaf and macro cell layouts even if design rules change. The proposed preconstrained compaction approach has been applied to direct design-rule conversion from 0.8-µm to 0.5-µm rules of CMOS layouts containing from several to 10,195 transistors. Experimental results demonstrate that a 10.6% reduction in diffusion areas can be achieved without unnecessary extensions of polysilicon wires with a 39% increase in processing times compared with conventional approaches.