Many automatic layout systems for VLSI circuits employ channel routing as the basic interconnection function. The wide range of uses and the importance of channel routing have inspired many good channel routing algorithms. However, many algorithms were developed with the geometric regularity of standard cell and gate array designs in mind. As a result these algorithms have difficulty routing channels with geometric generality (rectilinear boundaries and wires and terminals that can have different widths and irregular spacings) and simultaneously guaranteeing completion of all routes. This paper presents an algorithm for resolving cyclic vertical constraints using a general channel model. When this algorithm is combined with a constraint-based channel router, routing completion can be guaranteed, even for routing problems with generalized geometries. This algorithm is implemented with a constrain-based, alternating-edge, dogleg channel router. Extensions are described which permit the channel router to implement switchbox routing.

Many 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 of these algorithms were developed with the geometric regularity of standard cell and gate array designs in mind. As a result, the algorithms cannot simultaneously do all the following:

A simple channel model, which is appropriate for standard cells and gate arrays, is not appropriate in modern, general cell design environments. In very large circuits, complete automation is mandatory. Neither the designer nor the other functions within 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 (the width of a wire varies along its length). Channels with extreme rectilinear variations along the boundary are the norm. Terminals typically have different and irregular widths and spacings because the cells along the channel boundary are 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 channel boundaries). However, the published algorithms cannot generate sufficiently rich wiring patterns to complete the interconnections for all possible problem instances. This paper presents an algorithm for resolving cyclic vertical constraints that allows these constraint-based 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 constraint cycles. The altered wire segments and the resulting acyclic constraint graph can be used as input to most constraint-based channel routers.

The following 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 wire segments, and the locations of non-terminal doglegs along the segments, that will break all of the cycles in the constraint graph. This algorithm is implemented in conjunction with 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 as well as tapered trunk segments. Results of routing representative general cell channels are presented in Section 5. Results of routing the two Deutsch's More Difficult Examples [Deu89] are also presented, although these examples are not representative of modern, general cell problems.

Channel routing algorithms are highly specialized; they can operate only on channels and consider only restricted wiring patterns as potential solutions. However, these algorithms produce good results because the restrictions allow many routing combinations to be considered 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 operate by assigning trunk segments to tracks. A vertical constraint graph is a partial ordering of trunk segments that captures the requirements that prevent overlap of branch layer routing belonging to different nets. A complete ordering of the trunk segments is derived either by evaluating alternatives using geometric domain checks or by topological operations. After complete ordering, segment locations may be determined using compaction techniques [Deu85, Roy87].

Unfortunately, the ability to guarantee that all interconnections can be routed within a general channel model remains problematic. Some 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 (appropriate for standard cell or gate array designs). Recently, Chen [Che88] addresses breaking cycles using topological operations. YACR2 [Ree85] can route channels with cyclic vertical constraints, and this algorithm has been extended to use rectilinear channels [Ng86]. However, the published heuristics are difficult to apply in a general channel model. Furthermore, YACR2 does not look for cycles but discovers them one at a time and must reroute the entire channel if the fix up fails.

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 tracks.

The greedy algorithm typically produces very good resulting routes, and always finds a solution. Unfortunately, the greedy rules require a completely regular channel model: all of the terminals must be on a uniform grid. If terminals were allowed to be off-grid or were allowed to have varying widths, 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 and invalidate the greedy rules.

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 (two regions with N terminal positions). Each routing region is then split into two more regions and the process continues until regions correspond to tracks.

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

The greedy and hierarchical routing algorithms depend on a simple channel model in very fundamental ways and are not appropriate for general cell design. However, the constraint-based algorithms can be (or have been) extended to meet the variable geometry requirements. Furthermore, they can complete all interconnections when enhanced with an algorithm to resolve cyclic vertical constraints. The resulting acyclic vertical constraint graph and the added non-terminal doglegs can then be input to any constraint-based channel routing algorithm. The next section presents such an 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 constraint cycles. When used with a constraint-based channel router, this algorithm can guarantee completion of all routing. This approach has the further advantage that a generalized channel model can be easily incorporated. The algorithm minimizes channel density by selecting the best single dogleg to break each cycle.

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 constraint cycles. Then, the least-cost dogleg over all the trunk segments in the cycle is chosen to break the cycle.

In general, channel routing algorithms simplify the routing alternatives in such a way to allow many routing combinations to be evaluated simultaneously. We follow this paradigm. 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 2. 1 This method of breaking cycles is simple and produces good results. Remember, however, that dogleg channel routing is NP-complete [Szy85] and that modern routing channels are too complex for one 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.

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 3. With an appropriate design of the system in which the channel router is embedded, 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.

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 operations within the algorithm are discussed in more detail in the next section.

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

Poor choices for non—terminal doglegs are possible but are rarely seen in practice because the cost function effectively discriminates against poor choices. This approach does the right thing for two-terminal nets (the majority of nets), but nets with three or more terminals can be routed inefficiently. 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 in the cycle is chosen to break the cycle.)

It is possible 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 4, it will break either the segment of net 1 or net 2 with a non—terminal dogleg as shown in Figures 4(a) and 4(c). However, the actual routing produced is shown in Figures 4(b) and 4(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 4(b) and 4(d)) have equal densities and branch lengths but smaller via counts compared to the rejected routings in Figures 4(a) and 4(c).

Of course, within the regions, it is not necessary to evaluate every possible position. 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 is used with the algorithms described in this paper is based on the dogleg router [Deu76], but two extensions enhance the generality. The first enhance-ment 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 dynamically assigning trunks 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 or tapered 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. Of course no completion guarantees can be made for switchbox routing. 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. Deutsch's Difficult Example is routed in 20 tracks.

Table 1 summarizes the routing of four representative, general cell channels. These examples were taken from the highest (hierarchical) level of general cell circuits designed at Xerox PARC. These channels have much different characteristics than standard cell examples: more nets, more pins, lower pin density, and power busses in the channels. Track packing is almost always less dense 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, many 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 general, constraint-based channel router, it can route channels with irregular geometries and also can guarantee completion of all routing.