A new methodology is presented for the solution of the multilayer routing problem that has the potential to outperform channel based multi-layer routing algorithms by expanding the routing regions to include areas over the cells. It is assumed that four routing layers are available. Routing is completed in two steps; a selected group of nets is routed in the between-cell areas using existing channel routing algorithms and the first two routing layers. Then the remaining nets are routed over the entire layout area, between-cell and over-cell areas, using a new two-dimensional router and the next two routing layers. The router used for over-cell routing recognizes arbitrarily sized obstacles, for example, due to power and ground routing or sensitive circuits in the underlying cells. The proposed router was tested on a number of macro-cell layout examples. Advantages of dedicating two routing layers for over-cell routing is illustrated. Results show a significant reduction in total layout area, wire length and number of via when compared to results obtained using two-layer or multi-layer channel routing methods.

A new procedure for VLSI floor planning that minimizes routing parasitics is presented. The procedure, based on rectangular dualization, maximizes adjacency of modules that are heavily connected or connected by critical nets. Wiring macros are introduced to provide routing area for those modules that cannot be located adjacent to one another; these macros are located by planarizing the system interconnectivity graph using an edge crossing strategy that minimizes the cost of intersection. The rectangular dual is compacted using heuristics to approximate a quadratic area constraint by one or more linear constraints, thereby reducing the complexity of compaction from that of quadratic programming to linear programming.

A new graph-theoretic representation of the placement of rectangular IC blocks of arbitrary size and aspect ratio is proposed. This representation, called a relaxed digraph, provides an efficient model for two-dimensional calculations of minimum area layouts. Unlike other digraph models, the structure of the relaxed digraph represents an entire class of layout configurations derivable from a given initial placement of blocks. This model, therefore, provides greater flexibility in block placement than can be obtained from stiff digraph representations. A necessary and sufficient condition is derived for the existence of a nonoverlapping arrangement of rectangular cells in terms of the relaxed digraph representation. Based on this result, a fixed digraph representation can be selected from the relaxed digraphs that minimizes the layout area. The minimization utilizes positional constraints imposed by the relaxed digraphs and estimated routing space requirements. The area minimization is formulated as a quadratic optimization problem and solved using mathematical programming methods. The resulting modified digraph can then be used as a graph model for further calculations of a minimum area and routing-feasible layout.

Abstract Let one face of a cube be dissected into rectangles, no 4 of which meet at a single point. The dual graph of this configuration is a 4‐connected triangulated plane graph. This paper shows that any 4‐connected plane triangulation with at least 6 vertices and at least one vertex of degree 4 is dual to a cube with one face dissected into rectangles. The proof of this result contains an implicit algorithm for obtaining such a dissection. The paper also discusses a related problem: Given a graph G with all faces triangular except the outer face, does there exist a dissection of a rectangle into rectangles for which G describes the adjacency relations among the rectangles?

An analytical method is proposed for solving a routing area compaction problem in building block integrated circuits. Related minimization is performed with a linear programming technique. Minimum channel dimensions are calculated for a preliminary routing; these dimensions are used to construct routing constraints. Placement constraints are added for the interrelations between placement and routing. This combined set of constraints leads to a least overestimation of routing area and under certain conditions guarantees routing feasibility. Computational complexity and existence of a solution are discussed.