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, the existing algorithms were developed with the geometric regularity of standard cell and gate array designs in mind. As a result, the published algorithms suffer from one or more of the following deficiencies:

The 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 may have different and irregular 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 channel boundaries). However, the published algorithms cannot generate sufficiently rich wiring patterns to complete the interconnections for all possible problem instances. This paper presents a new algorithm for resolving cyclic vertical constraints 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 constraint cycles. The resulting acyclic constraint graph can be used as input to any constraint-based channel router. However, to overcome all of the deficiencies mentioned above, the router must utilize a generalized channel model.

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 wire segments for, and the locations of, non-terminal doglegs to 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. 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 detailed router used at Xerox PARC.

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.

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 such an algorithm but for a simplified channel model appropriate only for standard cell or gate array designs. The algorithm in [Kel86] also incorporates a parameter that prevents routing completion guarantees. YACR2 [Ree85] can route channels with cyclic vertical constraints but the published heuristics apply only to geometrically simple channel models. The complicated heuristics are difficult to apply in a general routing model. Furthermore, YACR2 does not look for cycles but discovers them one at a time and must route the entire channel between iterations.

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

This algorithm produces very good routing solutions for regular (standard cell and gate array) problems. 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 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.

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

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

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

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:

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 [Lor88].

It is only with irregular geometry channels or cyclic constraints that differences appear. Deutsch's More Difficult Examples [Deu89] are routed in 28 (LEFT) and 34 (RIGHT) tracks. Many more constraints are present in these More Difficult Examples (compared to the original example) and the long constraint chains contribute to the high track count. A channel router that could break constraint chains could do significantly better on these examples. 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.