<<>>


Figure 1.    Channel routing terminology is defined after [Lor88].  This more general channel model is required by general cell 
design systems.  Terminals are not required to be on a grid and varying wire widths are allowed.


Figure 2.    In a constraint graph the nodes represent trunk segments and the directed arcs represent constraints caused by branch 
layer wires.  In this example segment 2 must be above segment 3.  Thus, either routing (a) or (b) is allowed by the constraint 
graph (c).


Figure 3.    To break cycles in the vertical constraint graph, a segment is divided into an upper and a lower segment.  A 
nonterminal dogleg is used to connect the segments.


Figure 4.    It is not always possible to insert a nonterminal dogleg within a channel.  Completion can still be guaranteed when 
doglegs can be deferred to one of the intersecting channels.


Figure 5.    In rare cases, breaks with two nonterminal doglegs are better than breaks with one nonterminal dogleg.  Such extreme 
cases rarely occur and are effectively discriminated against when they do occur.


Figure 6.    Even though extra doglegs are inserted as indicated by the X, no penalty is incurred.  The better routings, (b) and 
(d), are selected by the (terminal) dogleg router.


Figure 10.    Search ranges for doglegs can be prioritized based on the configuration of terminals.  Any dogleg in region 1 is no 
worse than any dogleg in region 2.  Likewise for regions 2 and 3.

    GenerateAcyclicVerticalConstraintGraph: PROCEDURE [vcg, terminals, nets, rules] RETURNS [acyclicVcg, pins]
        pins _ terminals                      (*pins are terminals plus nonterminal doglegs *)
        WHILE cycles exist in vcg DO
            density _ CurrentTrackDensity[pins, nets]    (* Cost of Doglegs *)
            segsInCycle _ ChooseACycle[vcg]
            doglegbest _ worstPossibleDogleg
            FOR each trunkSegment in segsInCycle DO
                searchRanges _ GenerateRangesForSeg[trunkSegment]    (* Reducing the Search Space *)
                FOR each range in searchRanges WHILE no dogleg found DO
                    FOR each appropriate position in range DO    (* Reducing the Search Space *)
                        IF DoglegAllowed[trunkSegment, position, vcg, pins, nets, rules] THEN
                                (* Where Doglegs Are Allowed *)
                            dogleg _ GenerateDogleg[trunkSegment, position]    (* Breaking the Segments *)
                            IF BetterThan[dogleg, doglegbest, density] THEN    (* Cost of Doglegs *)
                                doglegbest _ dogleg
                    END FOR each appropriate position
                    IF no dogleg found for this trunkSegment THEN
                        doglegleft _ GenerateDogleg[trunkSegment, leftEndOfChannel] (* Breaking the Segments *)
                        doglegright _ GenerateDogleg[trunkSegment, rightEndOfChannel] (* Breaking the Segments *)
                        IF BetterThan[doglegleft, doglegbest, density] THEN    (* Cost of Doglegs *)
                            doglegbest _ doglegleft
                        IF BetterThan[doglegright, doglegbest, density]  THEN    (* Cost of Doglegs *)
                            doglegbest _ doglegright
                END FOR each range in searchRanges
            END FOR each trunkSegment
            Insert doglegbest into pins, vcg, nets
        END WHILE cycles exist
        RETURN [vcg, pins]
Algorithm 1.    This algorithm generates an acyclic vertical constraint graph by inserting nonterminal doglegs.  Bold comments 
refer to subsections in Section 3.2.


    Constraining: PROCEDURE [item1, item2, rules] RETURNS [Boolean]
        w1 _ Max [item1.w, rules.branch.viaSize]
        w2 _ Max [item2.w, rule.branch.viaSize]
        constraining _ SELECT FROM
            item1.p = item2.p:    TRUE
            item1.p < item2.p:    (item2.p-w2) - (item1.p+w1) < rules.branch.minSpace
            item1p > item2.p:    (item1.p-w1) - (item2.p+w2) < rules.branch.minSpace
        END SELECT
        RETURN [constraining];
Algorithm 2.    This algorithm determines if two branch layer items (terminals or nonterminal doglegs) interact with each other 
(in a design rule sense).

Table 1. Characteristics of Example Channels
Example    Density    Nets    Pins    Cycles    Source    Comments
    (
1    532    123    361    2    High Speed Cache    Rectilinear Sides; 3 different wire widths
2    1404    569    1575    13    High Speed Cache    3 different wire widths
3    612    94    297    3    High Speed Cache    Rectilinear Sides; 3 different wire widths
4    1108     272    748    8    Memory Controller    Dogleg in Vdd Bus; 2 different wire widths