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. 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 3. 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 4. 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 7. 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
 (mm)
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