Most modern, automatic layout systems for VLSI circuits are based on channel routing. The wide range of uses and the importance of channel routing have inspired many good channel routing algorithms. However, no existing algorithm is sufficiently general to be used as the only detailed router in modern design automation systems. No channel router can simultaneously route channels with cyclic vertical constraints, with rectilinear channels and with wires and terminals that can have different widths and spacings. This paper presents a new algorithm for resolving cyclic vertical constraints. When this algorithm is used with a constraint-based channel router, these drawbacks are overcome. This new algorithm is implemented within a constrained left-edge and dogleg channel router and is sufficiently general that it is the only general purpose, detailed router within the Xerox PARC DATools system.

Most modern, automatic systems for VLSI circuit layout are based on channel routing. Channel routing algorithms are used within module generators to stitch the active circuit elements together and are used as detailed routers within standard cell, gate array, and general cell automatic layout systems.

The wide range of uses and the importance of detailed routing in automatic layout systems have inspired many good channel routing algorithms. Taken as a whole, these algorithms provide a wide range of capabilities. However, many existing algorithms were (implicitly) developed with standard cell and gate array requirements in mind. No existing algorithm is sufficiently general to be used as the single detailed router in modern, VLSI design automation systems. The existing algorithms suffer from one or more of the following drawbacks:

This simplified model is not appropriate in modern, general cell design environments. In very large circuits, complete automation is mandatory. Neither the designer nor the other parts of the design automation system is able to alter the arrangement of terminals on the sides of the channels to accommodate the router. Typically, power and clock busses are wider than signal wires and must be routed in the channels. In larger circuits, power busses must be tapered (width varies along the length.) Channels with extreme variations along the boundary are the norm. Terminals can have different widths and spacings because the cells along the channel boundary may be constructed using radically different design styles.

One class of channel routing algorithms (the constraint-based algorithms) can (or can be generalized to) satisfy the variable geometry requirements (different widths and spacings for both terminals and wires and rectilinear channels). However, these algorithms cannot generate sufficiently rich wiring patterns to complete the interconnections for all possible problem instances. This paper presents a new algorithm for cyclic vertical constraint processing that allows these algorithms to guarantee completion of all the interconnections. This algorithm resolves cyclic constraints by adding non-terminal doglegs to enough wire segments to break all of the cycles. The resulting acyclic constraint graph can be used as input to any constraint-based channel router.

The next section evaluates existing channel routing algorithms in light of the requirements imposed by modern, VLSI design automation systems. Section 3 describes an algorithm for resolving cyclic vertical constraints by determining the locations and wire segments for non-terminal doglegs to break all of the cycles in the constraint graph. This algorithm is implemented as part of a dogleg channel router [Deu76]. Implementation enhancements, the subject of Section 4, include a switchbox routing capability and the ability to route wire segments with different widths and widths that vary along the lengths. Results are presented in Section 5. However, comparative results are not available since no other algorithm can route channels that demonstrate the effectiveness of this new algorithm. This router is sufficiently robust that it is the only general purpose router used at Xerox PARC.

Channel routing algorithms are very specialized; they can operate only on channels and consider only restricted wiring patterns as potential solutions. However, these restrictions allow the algorithms to consider all the interconnections simultaneously.

This article assumes a familiarity with channel routing; more background is available in [Bur86, Lor88]. Figure 1 illustrates the terminology used. Channel routing algorithms can be divided into three categories: constraint-based, greedy, and hierarchical. This section describes these categories in sufficient detail to understand their strengths and limitations for general cell, VLSI design.

Constraint-based channel routing algorithms concentrate on assigning trunk segments to tracks. The minimal requirements to prevent overlap of branch layer routing belonging to different nets are captured in a vertical constraint graph as illustrated in Figure 2. Thus, the constraint graph is a partial order of trunk segments. A complete order can be derived either by evaluating alternatives using geometric domain checks or by topological operations.

Unfortunately, the ability to guarantee that all interconnections can be routed remains problematic. Most of the algorithms discussed assume a vertical constraint graph that is free of cycles [Deu76, Yos82, Che86]. Authors assume that the terminals can be arranged by the designer or an automatic placement program [Per76] to provide a cycle-free problem instance. Several authors [Deu76, Sat80, Hig80] propose using non-terminal doglegs to break vertical constraint cycles but provide no algorithm for determining the positions. [Kel86] provides an algorithm but for a simplified channel model. Completion guarantees are not addressed. YACR2 [Ree85] can route channels with cyclic vertical constraints but does so inefficiently. It does not look for cycles but discovers them one at a time and must route the entire channel between iterations. The complicated heuristics are difficult to apply in a general routing model.

The greedy channel routing algorithm determines positions for wiring segments in a left-to-right, column-by-column scan [Riv82]. The wiring within each column is completely specified before the next column is processed. The algorithm specifies five greedy rules to assign wiring segments to positions.

The greedy algorithm typically produces very good resulting routes, and always finds a solution. Unfortunately, the rules require all of the terminals to be on a grid. If terminals were allowed to be off-grid, there would be an interaction between columns, and the column-by-column approach would be infeasible. Wide power terminals could interact with many signal terminals.

The third category of channel routing uses successive refinement in a hierarchical manner [Bur83]. First, the channel is split along the trunk direction into two routing regions and wiring segments are assigned to one of the two regions. This gives rise to a Two-By-N routing problem (with N columns or terminal positions). Both integer and dynamic programming solutions are described. Each routing region is then split into two more regions and the process continues until positions have been assigned for all wire segments.

This algorithm produces very good routing solutions for gate array and standard cell problems. However, the approach is not applicable for general cell layout systems because uniformity of the routing surface is a critical assumption. This integer and dynamic programming solutions require that terminals be on a grid and that wires have the same width.

Constraint-based algorithms come the closest to satisfying all of the requirements for general cell, VLSI design. These algorithms have been (or can be) extended to meet the variable geometry requirements. Furthermore, they can complete all interconnections when enhanced with an algorithm to resolve cyclic vertical constraints. The next section presents such an algorithm. The resulting acyclic graph can then be input to any constraint-based channel routing algorithm.

This section presents an algorithm to transform a vertical constraint graph with cycles into an acyclic graph by adding non-terminal doglegs to enough trunk segments to break all of the cycles. When used with a constraint-based channel router, this algorithm can guarantee completion of all routing. The algorithm minimizes the channel density by selecting the best, single dogleg to break each cycle. Because a single dogleg is used (more doglegs per cycle might be better) and because cycles are processed sequentially, the results may be less than optimal. Remember, however, that dogleg channel routing is NP-complete [Szy85] and that modern routing channels are too complex to enumerate all solutions and then choose the best. This means that we must resort to heuristics such as the one described here to find a minimal solution.

The remainder of this section describes the algorithm. Section 3.1 provides an overview and presents the actual algorithm while Section 3.2 provides more details. While this order of presentation separates some closely related topics, it does allow the concepts to be discussed before the details.

The algorithm determines how to break all the cycles in a vertical constraint graph. For each trunk segment within a cycle, the segment is broken by finding the least-cost dogleg that will divide the segment into two new segments that do not propagate any constraints. Then, the least-cost dogleg over all the trunk segments in the cycle is chosen to break the cycle.

To divide trunk a segment into two segments that do not propagate any constraints, we do the following. All of the terminals on the upper boundary of the channel are connected to a new segment (the upper segment) and the terminals on the lower boundary are connected to a separate, new segment (the lower segment). When the two new segments are connected using a non-terminal dogleg (that generates no new cycles), the existing cycle is broken as shown in Figure 3. Unless otherwise specified, the width of the dogleg wire is the same as the width of the trunk segment. This method of breaking cycles is simple and produces good results. More discussion is presented in Section 3.2.

Sometimes, it is not possible to find a position suitable for a non-terminal dogleg within the span of the channels. All possible positions might be unsuitable because of existing branch layer wiring, interference from other doglegs, or because a new constraint cycle would be created. When this happens, the dogleg must be deferred to one of the two intersecting channels as shown in Figure 4. With an appropriate design of the system in which the channel router is embedded [Kan76], it is possible to route all of the channels in an order that will allow the deferred doglegs to be routed at the same time the intersecting channels are routed. Rules that determine where a dogleg can be placed are discussed in Section 3.2.

The algorithm to transform a constraint graph with cycles into an acyclic graph is shown in Algorithm 1. Note that it is always possible to break every cycle because deferred doglegs are always possible.

The previous section discusses the concepts and presented an overview of the algorithm. This section provides more detail.

This approach always does the right thing for two-terminal nets (the majority of nets), but nets with three or more terminals can be routed inefficiently. An extreme example is shown in Figure 8. Fortunately, such extreme configurations rarely occur. Furthermore, the probability that all segments in a cycle would be broken in such a bad way is very small. (Remember that the best dogleg over all segments is chosen to break the cycle.)

Another drawback is that more non-terminal doglegs than necessary may be inserted if a (terminal) dogleg router [Deu76] is used. That router inserts doglegs at terminal locations; these doglegs can also break constraint cycles. When the algorithm discussed here is applied to the terminal configuration of Figure 9, it will break either the segment of net 1 or net 2 with a non-terminal dogleg as shown in Figures 9(a) and 9(c). However, the actual routing produced is shown in Figures 9(b) and 9(d). Just as the (terminal) dogleg router is not required to use terminal doglegs, neither is it required to use non-terminal doglegs. The (terminal) dogleg router selects from its several routings, the solution that 1) has the lowest channel density, 2) has the shortest branch length, and 3) has the smallest number of vias. The selected routings (Figures 9(b) and 9(d)) have equal densities and branch lengths but smaller via counts compared to the routings in Figures 9(a) and 9(c).

Note that the channel density as used in this paper is a generalization of that defined in [Deu76]. In that reference, channel density is defined as maximum count of segments whose extent includes any terminals abscissa. In the more general environment considered here, channel density is the maximum over all abscissa of the sum of segment widths and spaces that include an abscissa.

Of course, within the regions, it is not necessary to evaluate every possible position. In fact, no more than one inquiry per terminal plus at most one inquiry between terminals pairs plus the boundary positions need be searched.

The channel router that follows the algorithms to resolve cyclic constraints is based on the dogleg router [Deu76], but two extensions enhance the generality. The first enhancement generalizes trunk segments to allow different trunk segment widths and widths that can vary along the length. The second enhancement permits the channel router to route switchboxes (fixed terminals on the ends as well as the sides).

In order to route the generalized trunk segments, the concept of assigning trunks dynamically to statically defined tracks is retained. However, the function, Fitcheck, that checks if a trunk can be assigned to a track, must be generalized. When all trunks have the same width, Fitcheck only need check the horizontal extent of the trunk segments to determine a valid assignment. When trunks can have different widths, design rule interference with trunks on surrounding tracks must be checked.

The implementation of the channel router is also extended to allow switchbox routing. This allows fixed terminals on the ends as well as the sides of the channel. The following modifications are included:

The algorithm to resolve cyclic vertical constraints by inserting non-terminal doglegs and the (terminal) dogleg router is implemented in Cedar programming language and is a part of the DATools package [Bar88]. This is the only detailed router within this automatic layout system.

For instances of channel routing problems with acyclic vertical constraint graphs and with regular geometry (uniform widths and spaces for wire segments and terminals), this router produces the same results as the (terminal) dogleg router.

It is only with irregular geometry channels or cyclic constraints that differences appear. Plots 1, 2, 3 and 4 show channels produced by this router. These examples were taken from the highest (hierarchical) level of general cell circuits designed at Xerox PARC. Table 1 shows the characteristics of the channels. Note that these channels have much different characteristics than standard cell examples [Deu76]: more nets, more pins, lower pin density, and power busses in the channels. Packing is typically not as tight because no placer actively moves the terminals to reduce the channel density. These channels illustrate the types of problems that channel routers for general cell environments must solve.

The widespread use of channel routing has produced many good channel routing algorithms. However, most were inspired by standard cell and gate array layout styles and their simple, regular geometries. The requirements for general cell VLSI design are much more severe and no single channel router could meet the requirements. The algorithm presented here can efficiently transform a vertical constraint graph with cycles into an acyclic one. When this algorithm is combined with a constraint-based channel router, it can route channels with irregular geometries and also guarantees completion of all routing. Examples from four channels taken from VLSI designs illustrate the operation.