Channel Routing With Non-Terminal Doglegs
Bryan Preas

University of Paderborn, 4790 Paderborn, FRG

and
Xerox Palo Alto Research Center, Palo Alto, CA 94304 USA
Abstract
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.
This work was supported, in part, by a Research Award from the Alexander von Humboldt Foundation, Bonn, FRG.
1. Introduction
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:
 (1) Guarantee completion of all of the interconnections in all cases. This problem usually occurs when cyclic vertical constraints are encountered. When the algorithms can process cyclic constraints, the underlying channel model must be simple.
 (2) Allow wire segments to have the different widths and widths that vary along the lengths, and allow the terminals (that are to be connected) to have different widths and spacings.
 (3) Permit the channel boundaries to be rectilinear or irregular.
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.
2. Channel Routing Algorithms
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.
2.1 Constraint-Based Channel Routing
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 as illustrated in Figure 2. 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].
Trunk Ordering Using Geometrical Checks. A complete ordering of the trunk segments can be determined by evaluating the alternative assignments of trunks (within the limits allowed by the vertical constraint graph) to tracks. The evaluations are performed using geometric design rule checks. Deutsch [Deu76] describes a (terminal) dogleg channel routing algorithm where trunk segments between two adjacent terminals on a net are restricted to one track. Doglegs are allowed only at terminal positions. More recently, a different approach to handling constraints was reported [Ree85]. This router assigns trunks to tracks but disregards some vertical constraints. A pattern router is then used to fix up the branch layer routing where constraint violations would occur.
Trunk Ordering Using Topological Operations. These algorithms use topological operations to derive a complete ordering among the trunk segments from the partial order of the constraint graph. [Yos82] defines an interval graph [Oht79], and merging operations on the constraint graph and the internal graph to determine which trunks are to be put on the same tracks. [Che86] defines an augmented constraint graph that contains both vertical (directed) constraints (to capture the branch layer constraints) and horizontal (undirected) constraints (to capture the trunk layer constraints). Operations are defined to assign directions to the horizontal constraints. Once directions are defined for the horizontal constraints, a complete ordering is defined.
Evaluation of Constraint-Based Algorithms. Most of these algorithms can (or can be generalized to) route wires and terminals with different widths and spacings. These algorithms can be adapted to use a general channel model
and can be extended to handle tapered trunk segments as described in Section 5.
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.
2.2 Greedy Channel Routing
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.
2.3 Hierarchical Channel Routing
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.
2.4 Channel Routing Summary
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.
3. Resolving Cyclic Vertical Constraints
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.
3.1 The Approach
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 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.
1 Typically, the width of the dogleg wire defaults to the width of the trunk segment. However, the client can specify more sophisticated behavior as a function of material, trunk width and current carrying requirements.
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, 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.
3.2 The Operations Within The Algorithm
The previous section discusses the concepts and
presented an overview of the algorithm. This section provides more detail.
Breaking the Segments. In Section 3.1, it is stated that to break a cycle, a segment in the cycle is broken into two new segments, one connecting the upper terminals and the other connecting the lower terminals. A single non—terminal dogleg that generates no new cycles connects these two new segments. This method has several advantages: it is easy to implement, the interactions among multiple doglegs within one net do not have to be considered, and legal positions for doglegs are not a function of the topology of its net (as would be the case, for example, if each two-terminal segment could be broken separately).
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. 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. (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 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 rejected routings in Figures 6(a) and 6(c).
2 Channel density is the maximum over all abscissa of the sum of segment widths and spaces that include an abscissa.
Cost of Doglegs. To compare alternative doglegs, a three-part cost comparison is used: net type, channel density 2 and trunk overlap. A dogleg on a power supply net is more expensive than a dogleg that is on a clock or signal net. Likewise, doglegs on clock nets are more expensive than doglegs on signal nets. If the nets are the same type then a second priority comparison is made. If dogleg1 results in a smaller channel density than dogleg2, then dogleg1 has the lowest cost. If the resulting densities are the same, then the dogleg that produces the smallest trunk overlap is selected. Overlap occurs when two segments of the same net both cross any abscissa. This comparison selects for the shortest wire length.
Where Doglegs Are Allowed. It is now possible to define the rules that determine whether it is possible to put a dogleg at a (horizontal) position within a channel [Kel86]. A non—terminal dogleg is forbidden if any of the following conditions is true:
 (1) If the dogleg would constrain (described below) terminals on both the top and bottom of the channel and those terminals belong to the same net. If this were allowed, it would be impossible to connect a net directly across a channel as shown in Figure 7.
 (2) If the dogleg would constrain an existing non—terminal dogleg. The constraint graph mechanism (as we have defined it) cannot represent the constraint that both segments a1 and a2 must be either above or below both segments b1 and b2 as illustrated in Figure 8. Hence, the configuration is disallowed.
 (3) If a dogleg would introduce a new constraint cycle. It is not appropriate to introduce a new constraint cycle in the process of breaking another. This rule can be stated in two parts:
 (3a) If the dogleg constrains an upper terminal, tu, and there is a directed path in the constraint graph from the dogleg segment to the segment connected to tu, or,
 (3b) If the dogleg constrains a lower terminal, tl, and there is a directed path in the constraint graph from the segment connected to tl to the dogleg segment.
Constraining. Given two items on the branch layer (terminals or non—terminal doglegs) and a set of design rules, Constraining returns a Boolean variable that indicates if the items constrain each other. With each branch layer item, we have an associated position, p, and a width, w. The operation of Constraining is illustrated by Figure 9 and Algorithm 2. Constraining answers the same question that InTheSameColumn answers in gridded channel routers.
Figure 7. A dogleg is not allowed if it would prohibit a net with simple topology from crossing a channel. In this case, net 1 can not be routed with a normal topology.
Figure 8. Both segments a1 and a2 must be either above or below both segments b1 and b2. Interacting doglegs are disallowed because the constraint graph cannot represent this complexity.
Figure 9. Branch layer items constrain each other if they are closer (horizontally) than the minimum branch spacing.
Reducing the Search Space. It is usually not necessary to search the entire channel before finding the best position to insert a dogleg. Based on the relationship of terminals on the upper and lower boundaries of the channel, ranges along the channel can be prioritized as shown in Figure 10. If any dogleg is allowed in region 1, then its cost is less than or equal to that of any dogleg in either regions 2. A similar statement can be made for regions 2 and 3. Thus, searching can terminate after a region has been processed if a dogleg has been found.
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.
4. Channel Router Implementations Extensions
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 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 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:
 (1) Track coordinates are assigned by considering the positions of the terminals on the channel's ends. Thus, the tracks' spacings may differ and require extra computation in Fitcheck.
 (2) Extra constraints must be included in the vertical constraint graph to capture the partial ordering required by the terminals on the ends of the channel.
 (3) Trunk segments connected to terminals on the channel ends are assigned permanently to the corresponding tracks.
 (4) Non-terminal doglegs are required to resolve any over-constrained trunks. For example, a trunk that connects a left end terminal in one track to a right end terminal in a second track must have a non—terminal dogleg.
5. Results
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.
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. Compaction (or a router that could break constraint chains) could significantly improve these examples.
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.
6. Conclusions
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.
References
[Bar88] Barth, R., L., Monier, and B. Serlet, "Patchwork: layout from schematic annotations," Proc. of 25th Design Automation Conference, pp 250-255, June, 1988.
[Bur83] Burstein, M., and R. Pelavin, "Hierarchical wire routing," IEEE Transactions on Computer-Aided Design, vol. CAD-2, no. 4, pp. 223-234, October 1983.
[Bur86] Burstein, M., "Channel routing," in Layout Design and Verification, T. Ohtsuki, editor, Elsevier Science Publishers B. V. (North Holland), Chapter 4, pp 133-167, 1986.
[Che86] Chen, H. H., and E. S. Kuh, "Glitter: a gridless variable-width channel router," IEEE Transactions on Computer-Aided Design, vol. CAD-5, no. 4, pp. 459-465, October 1986.
[Che88] Chen, H. H., Breaking Cycles And Vertical Constraints In Deutsch's New And More Difficult Channel-Routing Problems, RC 14161, IBM Research Report, November 1988.
[Deu76] Deutsch, D. N., "A 'dogleg' channel router," in Proc. 13th Design Automation Conference, pp. 425-433, June 1976.
[Deu85] Deutsch, D. N., "Compacted channel routing," in Proc. International Conference on Computer-Aided Design, pp. 223-225, November 1985.
[Deu89] Deutsch, D. N., "Two new and more difficult channel routing problems," in IEEE Transactions on Computer-Aided Design, vol. 8, no. 4, pp. 448, April, 1989.
[Hig80] Hightower, D. W., and R. L. Boyd, "A generalized channel router," in Proc. 17th Design Automation Conference, pp. 12-21, June 1980.
[Kel86] Keller, F. V., and D. A. Mlynksi, "A graph-theoretical channel-router for constraint-loop-problems," in Proc. 1986 IEEE International Symposium on Circuits and Systems, pp. 311-314, May 1986.
[Liu81] Liu, M. L., An Algorithm For Two-Layer Channel Routing With Cyclic Constraints, Memorandum UCB/ERL M81/M82, UC Berkeley, November 1981.
[Lor88]  Lorenzetti, M. J., and D. S. Baeder, "Routing," in Physical Design Automation of VLSI Systems, B. T. Preas and M. J. Lorenzetti, editors, Menlo Park, CA: Benjamin/Cummings Publishing Company, Inc., Chapter 5, pp 157-210, 1988.
[Ng86] Ng, C. H., "An industrial world channel router for non-rectangular channels," Proc. of 23th Design Automation Conference, pp 490-494, June, 1986.
[Oht79] Ohtsuki, T. O., H. Mori, E. S. Kuh, T. Kashiwahara, and T. Fujisawa, "One-dimensional logic gate assignment and interval graphs," IEEE Transactions on Circuits and Systems, vol. CAS-26, pp. 675-684, September 1979.
[Per76] G. Persky, "Pro-an automatic string placement program for polycell layout," in Proc. 13th Design Automation Conference, pp. 417-424, June 1976.
[Ree85] Reed, J., A. Sangiovanni-Vincentelli, and M. Santomauro, "A new symbolic channel router: yacr2," IEEE Transactions on Computer-Aided Design, vol. CAD-4, no. 3, pp. 208-219, July 1985.
[Roy87] Royal, J., H. Palczewski, H. VerHeyen, N. Naccache and J. Soukup, "Geometrical compaction in one dimension for channel routing," in Proc. 24th Design Automation Conference, pp. 140-145, June 1987.
[Riv82] Rivest, R. L. and C. M. Fiduccia, "A 'greedy' channel router," in Proc. 19th Design Automation Conference, pp. 418-424, June 1982.
[Sat80] Sato, K., H. Shimoyama, T. Nagai, M. Ozaki, and T. Yahara, "A 'grid-free' channel router," in Proc. 17th Design Automation Conference, pp. 22-30, June 1980.
[Szy85] Szymanski, T. G., "Dogleg channel routing is np-complete," IEEE Transactions on Computer-Aided Design, vol. CAD-4, no. 1, pp. 31-41, January 1985.
[You82] Yoshimura T. and E. Kuh, "Efficient algorithms for channel routing," IEEE Transactions on Computer-Aided Design, vol. CAD-1, no. 1, pp. 25-35, January 1982.
commands
InterpressCompose edacreduced.ip ← edacfinal.tioga.ip translate 0.75 1.25 in scale 0.77
SendIP edacreduced.ip
IPPreview edacreduced.ip
files:
///Users/Preas.pa/papers/EDACDraft.tioga
///Users/Preas.pa/papers/EDACFullPage.tioga
///Users/Preas.pa/datools/MCChannels.dale -- the MC channels
///Users/Preas.pa/datools/ModifiedDiscriminable.ColorMap -- NReadColors ModifiedDiscriminable
///Users/Preas.pa/datools/EDACFigures.dale
///7.0/Commands/ExpandedMargins.style
/firedrake/cedar/users/curry.pa/ScChannels.dale
last Updated:
December 17, 1989 3:35:50 pm PST