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, dogleg
best, 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[dogleg
left, dogleg
best, density]
THEN
(*
Cost of Doglegs *)
doglegbest ← doglegleft
IF BetterThan[dogleg
right, dogleg
best, 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 [item
1, item
2, 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