A physical design system is being developed which is intended to significantly reduce the time required to design very large integrated circuits (IC's). The system is composed of a chip assembler, various module generators, an interactive layout editor, a standard cell placement and routing system, and a general cell floor planning, placement, and routing system. The general cell layout system is the subject of this paper. The general cell layout system can be used in an interactive or algorithmic mode and supports a hierarchical design methodology; however, this paper will concentrate on the models and algorithms necessary to lay out one component. The inputs to the system are interconnection requirements and component information.

The general cell layout system is composed of three major parts: the topological model, floor planning and placement, and routing. The topological model, discussed in Section 2, provides an important level of abstraction for the layout algorithms. Floor planning and placement, outlined in Section 3, are responsible for determining the relative positions for the components and for organizing the routing area into channels. Floor planning also determines constraints on the size, shape and pin positions for components yet to be designed. Routing, discussed in Section 4, determines the locations for the necessary wiring. This two step process consists of global routing followed by detailed routing which assigns wiring locations with respect to the routing channels. After detailed routing is complete for all of the channels, locations for the components and routing channels are assigned to provide just enough space for the routing. Floor planning, placement, and routing algorithms are active research topics.

The general cell layout problem is inherently a two dimensional problem; however, the language used to implement a solution is sequential. This means that layers of abstraction must be built to represent the problem in a more tractable form. An important abstraction and a unifying theme among floor planning, placement, and routing is the topological model in which only relative positions of components and routing areas are important. This model automatically compensates for changes in components and routing areas as they expand or contract to conform to the changing design. It is necessary to convert to the geometrical domain only to compare alternative layouts during the optimization process, or as the final step before generating the masks.

The general cell layout problem conforms well to the topological model. Only constraints within the circuit under consideration affect the locations of entities within the layout; there are no manufacturing steps which impose fixed coordinates external to the design as is the case with gate arrays or printed circuit boards.

The topological model reduces the complexity of IC layout by abstracting out the geometrical information (geometry). Computation of geometry is deferred until needed. The advantages of this approach are the following: removing and adding both components and wiring are simple; topological operations are well defined; mapping the layout problem into the geometrical domain is well defined and fast; routing areas can always be made just large enough to accommodate the required wiring; and, the complexity of dealing with the masses of geometrical data is obviated.

The elements of the layout problem included in the topological model are the external pins which serve as the information ports for communicating with the containing component, the sub-components within the component under consideration, and the routing areas or channels. When a distinction must be made among components at different hierarchical levels, "current component" will refer to the component currently being laid out while "sub-component" will refer to a circuit primitive within the current component.

Components are modeled at varying levels of detail in the layout system. Pins on components must be located so that they can be reached, with no design rule violations, by a straight wire segment on one of the routing layers. External pins for the current component are internal pins at the next higher level, and therefore, must conform to the same restrictions. Component outlines have basic shapes of rectangles of arbitrary size and shape with arbitrary rectangles removed from zero to four of the corners as shown in Figure 1. The floor planning process allows some or all of the components to be undefined or soft; therefore it is necessary to determine size, shape and pin position constraints for those components. Characteristics of soft components, such as restrictions on height, width, area, and aspect ratio are defined procedurely to permit a high degree of extensibility. However, some soft component models are predefined: a custom cell model, a standard cell model, and a tile model. The routing process extends the notion of basic shape to accommodate indentations and protrusions along the side of a component.

The routing area is organized into channels, as shown by example in Figure 1, which are maintained throughout the layout process. Within the floor planning and placement process, channels serve to define the topology of the layout. They divide the space into topological holes each of which contains one component. To the router the channels describe the areas reserved for the wiring. The channel widths may vary throughout the layout process depending on the number of wiring tracks required; the exact widths are determined only after all channels have been routed. The channel lengths are determined by the positions of the channels that they intersects at their extreme points. Channel intersections may take the form of Tees, Els or Crosses as shown in Figure 1. With each side of a component there exists one associated channel.

Graph models which support general cell layout with components modeled as rectangles [Kani, Preas] have been extended to permit more complex components and to increase the resolution, and therefore the accuracy, of global routing. Three graphs are used to model the layout surface: the horizontal channel position graph, the vertical channel position graph and the channel intersection graph. The channel position graphs are used primarily to map the layout from the topological domain into the geometrical domain, while the channel intersection graph is used in topology modification and global routing.

Although only the vertical channel position graph is described, the horizontal channel position graph is analogous. The vertical channel position graph is a directed acyclic graph with nodes that represent the horizontal channels while the arcs represent vertical dimensions of components. Figure 2 shows the vertical channel position graph corresponding to the layout shown in Figure 1.

The channel intersection graph is an undirected graph in which the nodes represent intersections of horizontal and vertical channels or positions along the channels where the channel widths change because of changes in component dimensions.

In order for the topological model to be useful, three classes of operations are necessary: operations which map geometrical domain problems into the topological domain; operations which compute aspects of geometry, given an existing topology; and, operations which modify or manipulate a topology.

The DefineChannels operation maps a geometrical domain layout problem into the topological domain. The input to this operation is a set of components on a plane. First, an input verification procedure is invoked to ensure that the components do not overlap. Second, an outline is constructed around each component; the outline always contains the component and is made as large as possible without intersecting or containing any other outlines. Third, a primary direction is chosen and all outlines perpendicular to this direction are collapsed along the primary direction into channels. Fourth, the remaining outlines are collapsed along the secondary direction. It may be necessary to reposition the components so the channels lie only in the white space among the components; this step is performed automatically by the Geomertize operation described below. The execution time of the DefineChannels operation is not critical since it is invoked only once at the beginning of the layout process.

Execution time is important for the operations to compute aspects of geometry, given the graph models. The operations outlined below are provided by the topological model and are linear in the number of edges and nodes [Deo].

The ShortestPath operation on the channel intersection graph finds the shortest path (or a number of shortest paths) from a source node to a set of target nodes and has a worst case execution time proportional to the square of the number of nodes.

Operations to modify or manipulate the layout topology are necessary to perform the optimization functions of floor planning and placement, and are described in the next section.

Floor planning and placement procedures are responsible for determining the relative positions of the components and external pins, as well as organizing the routing area into channels. Since interconnection wiring can consume over one half of the total area for modern IC's, it is imperative that the channel topology and the channel widths be accurately modeled during floor planning and placement. Floor planning is distinguished from placement by the type of components manipulated. Placement is a bottom-up process, and therefore determines relative locations for predefined components. Alternatively, floor planning is a top-down process. Since some, or perhaps all, of the components have not been designed, floor planning must determine constraints on component's size, shape, and pin positions. If floor planning is done well, it should obviate the need for placement since components and channels will be packed in the most advantageous way during the top-down design process. This section discusses the primitive operations used to manipulate the topological model of the layout as well as the algorithms used for floor planning and placement. Placement is described first because it is conceptually simpler; floor planning is discussed as an extension to placement.

Primitive operations are available to the floor planning and placement algorithms in order to manipulate the layout. They are part of the topological model and are divided into the following categories: component operators, topology modification operators, and context operators. The channel topology ideas follow those described in [Preas] with extensions for more complex component shapes and more complicated channel intersections.

The component operators manipulate aspects of components. The Orientation operator modifies a component orientation by reflection and/or rotation while Shrink and Grow operators that follow the notion of [Slutz] are available to remove and add components, respectively. During a Grow operation a topological hole is created by dividing an existing channel into two channels along its length. At each end of the division, the limit is defined by a corner that is cut from a component or by a channel that intersects the channel being divided Shrink is a logical inverse operation to Grow and removes a component and collapses the bounding channels.

Topology modification operators are available to manipulate the routing channel topology. A logical inverse for each operation except ClearCorners is also available. The operators form a complete set in that any channel topology can be created using a sequence of these operations. Examples are shown in Figure 3.

Each primitive operator is backed by an undo stack and a redo queue that can be used to construct more complicated, or composite, operations. A backtrack feature, supported by the undo stack, and a tracking feature, supported by the redo queue, make heuristic searches over the layout simple to implement and the redo queue makes keeping multiple solutions both simple and efficient. In addition, save and restore operators are available for complete context switches.

A heuristic approach, built on the primitive operations, is used for both initial placement and placement improvement. This section discusses a recursive, look ahead search procedure and then describes how it is used to solve general cell placement problems.

At the core of the placement heuristic is a procedure called LookAheadSearch, which makes its decision of where to place a particular component by recursively placing some number of other components and choosing the best solution at the leaves of the search tree. This gives a look ahead capability to the placement procedure. Three parameters control the LookAheadSearch procedure:

The LookAheadSearch procedure first generates the feasible placements for the component being placed by Growing a topological hole and applying topology modification operators locally. The search tree is pruned at this level by saving the b best placements for this component. Second, repeat the first step to a depth of d. Third, evaluate the result at depth d and keep the s best solutions. These solutions correspond to the s best positions to place the first component. b^d possibilities are evaluated to find these solutions.

Implementation of the LookAheadSearch procedure is simple with the undo stack and the redo queue. To restore a previous state it is necessary to pop a reverse operation from the undo stack, execute that operation, and delete a forward operation for the head of the redo queue. To remember a path through the search tree, it is necessary to make a copy of the redo queue for the appropriate number of entries.

Initial placement and placement improvement are implemented as heuristics using LookAheadSearch. The initial placement algorithm first determines a placement for a set of seed components. Second, channels are constructed using DefineChannels. Third, unplaced components are selected and placed using LookAheadSearch.

The placement improvement algorithm takes a complete placement as input and iteratively improves it by removing as set of components and replacing them using LookAheadSearch. The process converges until it converges.

Two factors which significantly affect the quality of the placement are component ordering and channel width estimation. Component ordering for initial placement depends on the characteristics of the components. Large variations in component sizes imply ordering by component area, while relatively uniform component sizes imply that ordering based on connectivity to the already placed components should be used. For placement improvement the majority, but not all, of time should be spent trying to improve the placement of components that lie on a critical path of a channel position graph.

Accurate estimation of routing channel widths is difficult because of the tradeoff between accuracy and execution time. The most accurate method is global routing, but since this takes on the order of minutes, it is feasible only for small problems. A more reasonable approach is to assume that routing channels within the bounding rectangle of a net have equal probability of containing a segment of that net.

Two approaches are being investigated for floor planning. The first approach is based on the look ahead technique used by placement and the second is a min-cut technique. In the look ahead technique, any time a soft component is placed a new shape is determined for that component. A Compress operation is defined which modifies the shapes of soft components within the layout to reduce the layout area; it is effective if a large number of components are soft.

The min-cut technique [Lauther] uses a top-down approach to construct a layout. First a min-cut tree is constructed based on the interconnection information, and a rectangular block with area equal to the total area of all the components is placed and channels are constructed around it. This block represents the root node of the min-cut tree. Second, the block is alternately partitioned vertically or horizontally into blocks, each representing a branch from the root node. The area of each block corresponds to the total area of the components belonging to the branch. Third, step 2 is repeated for each resultant block with alternating cut directions until each block is a separate component. To incorporate the partitioning of blocks, a Spawn operation takes a block and Spawns two children of the desired shape by partitioning in the desired direction. This operation is supported by the undo and redo facilities.

The routing portion of the general cell layout system determines the detailed paths for all of the interconnections using a two step process consisting of global routing and detailed routing. Global routing finds strategic paths while detailed routing refines the global routing by assigning wire segments to individual tracks within the channel. Only after detailed routing is complete for all channels are the positions determined for the components and the routing channels. The topological model automatically makes adjustments of the layout to fit changes in routing.

The purpose of global routing is to even the wiring demand over the channels so that the layout area is as small as possible. It assigns wire segments to channels but not to individual tracks within the channels, and is divided into initial global routing and a global routing improvement steps. Both steps depend on the ShortestPath primitive in the topological model.

The problem of determining the global routing for a single interconnection is mapped into a shortest path problem through the channel intersection graph by setting the arc weights appropriately. First the pins of the interconnection are mapped as nodes onto on the channel intersection graph; the node representing the output pin is marked as a source while the input pins are marked as targets. Arc weights are assigned corresponding to the area that would be added to the layout if one wiring track were added to the channel segment represented by the arc. In order for the total path length of the interconnection to represent the area it adds to the layout, it is necessary to use a path finding algorithm in which intermediate nodes are given permanent labels [Dijkstra] and to modify the weights of the arcs corresponding to a channel if the channel width is increased at one channel segment [Wisniewski].

Using the shortest path algorithm discussed in the previous paragraph and the topological model, initial global route and global route improvement are simple. Initial global route simply invokes the shortest path procedure sequentially for each net. Routing nets in order from shortest to longest has been found to be effective. Global route improvement iteratively improves the routing by removing and rerouting sets of nets. The improvement process continues until the process converges.

The detailed routing step determines exact locations within the channels (or portions of the channels) for the wire segments that have been assigned to that channel by global routing. Channel routing algorithms are used for those channels that have pins along one side or on two opposite sides of the channel [Deutsch] while a switchbox router [Hsu] is used for those channels that cannot be routed by the channel router.

It is necessary to determine an ordering for the detailed routing of the channels so that once a channel is routed, the pins along that channel do not move with respect to each other. The approach uses an extension of [Kani, Preas] that allows El shaped channel intersections within the body of the layout. The extensions require that El intersection constraints be added to the route order constraints (two channels that intersect in an El each constrain each other). The parallel channel order rule is also extended to add constraints at El intersections and Cross intersections that terminate in El intersections.