Unit 7: Detailed Routing

․Course contents:
¾Channel routing
¾ Full-chip routing

․Readings
¾ W&C&C: Chapter 12

¾ S&Y: Chapter 7

1
Courtesy of Y.-W. Chang
Channel/Switchbox Routing

2
Courtesy of Y.-W. Chang
Order of Routing Regions and L-Channels
(a) No conflicts in case of routing in the order of 1, 2, and
3.
(b) No ordering is possible to avoid conflicts.
(c) The situation of (b) can be resolved by using L-
channels.
(d) An L-channel can be decomposed into two channels
and a switchbox.

3
Courtesy of Y.-W. Chang
 Routing Considerations

․Number of terminals (two-terminal vs. multi-terminal

nets)
․Net widths (power and ground vs. signal nets)
․Via restrictions (stacked vs. conventional vias)
․Boundary types (regular vs. irregular)
․Number of layers (two vs. three, more layers?)
․Net types (critical vs. non-critical nets)

4
Courtesy of Y.-W. Chang
 Routing Models
․Grid-based model:
¾ A grid is super-imposed on the routing region.
¾ Wires follow paths along the grid lines.
¾ Pitch: distance between two gridded lines
․Gridless model:
¾ Any model that does not follow this “gridded” approach.

5
Courtesy of Y.-W. Chang
 Models for Multi-Layer Routing
․Unreserved layer model: Any net segment is allowed
to be placed in any layer.
¾ Less popular, but wrong-way jogs?
․Reserved layer model: Certain type of segments are
restricted to particular layer(s).
¾ More popular model
¾ Two-layer: HV (horizontal-Vertical), VH
¾ Three-layer: HVH, VHV

6
Courtesy of Y.-W. Chang
Terminology for Channel Routing Problems

․ Local density at column i, d(i): total # of nets that crosses

column i.
․ Channel density: maximum local density
¾ # of horizontal tracks required ³ channel density.

7
Courtesy of Y.-W. Chang
 Channel Routing Problem
․Assignments of horizontal segments of nets to tracks.
․Assignments of vertical segments to connect
¾ horizontal segments of the same net in different tracks, and
¾ the terminals of the net to horizontal segments of the net.
․Horizontal and vertical constraints must not be violated.
¾ Horizontal constraints between two nets: The horizontal span of
two nets overlaps each other.
¾ Vertical constraints between two nets: There exists a column
such that the terminal on top of the column belongs to one net
and the terminal on bottom of the column belongs to the other
net.
․Objective: Channel height is minimized (i.e., channel
area is minimized).

8
Courtesy of Y.-W. Chang
 Horizontal Constraint Graph (HCG)
․HCG G = (V, E) is undirected graph where
¾ V = { vi | vi represents a net ni}
¾ E = {(vi, vj)| a horizontal constraint exists between ni and nj}.
․For graph G: vertices Û nets; edge (i, j) Û net i
overlaps net j.

9
Courtesy of Y.-W. Chang
 Vertical Constraint Graph (VCG)
․VCG G = (V, E) is directed graph where
¾ V = { vi | vi represents a net ni}
¾ E = {(vi, vj)| a vertical constraint exists between ni and nj}.
․For graph G: vertices Û nets; edge i ® j Û net i must
be above net j.

10
Courtesy of Y.-W. Chang
2-L Channel Routing: Basic Left-Edge Algorithm
․ Hashimoto & Stevens, “Wire routing by optimizing channel
assignment within large apertures,” DAC-71.
․ No vertical constraint.
․ HV-layer model is used.
․ Doglegs are not allowed.
․ Treat each net as an interval.
․ Intervals are sorted according to their left-end x-coordinates.
․ Intervals (nets) are routed one-by-one according to the order.
․ For a net, tracks are scanned from top to bottom, and the
first track that can accommodate the net is assigned to the
net.
․ Optimality: produces a routing solution with the minimum #
of tracks (if no vertical constraint).

11
Courtesy of Y.-W. Chang
 Basic Left-Edge Algorithm
Algorithm: Basic_Left-Edge(U, track[j])
U: set of unassigned intervals (nets) I1, …, In;
Ij=[sj, ej]: interval j with left-end x-coordinate sj and right-end ej;
track[j]: track to which net j is assigned.

1 begin
2 U ¬ {I1, I2 , …, In};
3 t ¬ 0;
4 while (U ¹ Æ ) do
5 t ¬ t + 1;
6 watermark ¬ 0;
7 while (there is an Ij Î U s.t. sj > watermark) do
8 Pick the interval Ij Î U with sj > watermark,
nearest watermark;
9 track[j] ¬ t;
10 watermark ¬ ej;
11 U ¬ U - {Ij};
12 end
12
Courtesy of Y.-W. Chang
 Basic Left-Edge Example
․ U = {I1, I2, …, I6}; I1 = [1, 3], I2 = [2, 6], I3 = [4, 8], I4 = [5, 10], I5 = [7,
11], I6 = [9, 12].
․ t =1:
¾ Route I1: watermark = 3;

¾ Route I3 : watermark = 8;

¾ Route I6: watermark = 12;

․ t = 2:
¾ Route I2 : watermark = 6;

¾ Route I5 : watermark = 11;

․ t = 3: Route I4

13
Courtesy of Y.-W. Chang
 Basic Left-Edge Algorithm
․If there is no vertical constraint, the basic left-edge
algorithm is optimal.
․If there is any vertical constraint, the algorithm no
longer guarantees optimal solution.

14
Courtesy of Y.-W. Chang
 Constrained Left-Edge Algorithm
Algorithm: Constrained_Left-Edge(U, track[j])
U: set of unassigned intervals (nets) I1, …, In;
Ij=[sj, ej]: interval j with left-end x-coordinate sj and right-end ej;
track[j]: track to which net j is assigned.

1 begin
2 U ¬ { I1, I2, …, In};
3 t ¬ 0;
4 while (U ¹ Æ) do
5 t ¬ t + 1;
6 watermark ¬ 0;
7 while (there is an unconstrained Ij Î U s.t. sj >
watermark) do
8 Pick the interval Ij Î U that is unconstrained,
with sj > watermark, nearest watermark;
9 track[j] ¬ t;
10 watermark ¬ ej;
11 U ¬ U - {Ij};
12 end
15
Courtesy of Y.-W. Chang
 Constrained Left-Edge Example
․ I1 = [1, 3], I2 = [1, 5], I3 = [6, 8], I4 = [10, 11], I5= [2, 6], I6 = [7,
9].
․ Track 1: Route I1 (cannot route I3); Route I6; Route I4.
․ Track 2: Route I2; cannot route I3.
․ Track 3: Route I5.
․ Track 4: Route I3.

16
Courtesy of Y.-W. Chang
 Dogleg Channel Router
․ Deutsch, “A dogleg channel router,” 13rd DAC, 1976.
․ Drawback of Left-Edge: cannot handle the cases with
constraint cycles.
¾ Doglegs are used to resolve constraint cycle.

․ Drawback of Left-Edge: the entire net is on a single track.

¾ Doglegs are used to place parts of a net on different tracks to
minimize channel height.
¾ Might incur penalty for additional vias.

17
Courtesy of Y.-W. Chang
 Dogleg Channel Router
․Each multi-terminal net is broken into a set of 2-
terminal nets.
․Two parameters are used to control routing:
¾ Range: Determine the # of consecutive 2-terminal subnets of
the same net that can be placed on the same track.
¾ Routing sequence: Specifies the starting position and the
direction of routing along the channel.
․Modified Left-Edge Algorithm is applied to each subnet.

18
Courtesy of Y.-W. Chang
 Framework Evolution
․Billions of transistors may be fabricated in a single chip
for nanometer technology.
․Need frameworks for very large-scale designs.
․Framework evolution for EDA tools: Flat è Hierarchical
è Multilevel

Multilevel

Hierarchical

Flat

Source: Intel (ISSCC-03)

19
Courtesy of Y.-W. Chang
 Flat Routing Framework
․Sequential approaches
¾ Maze searching
¾ Line searching
․ Concurrent approaches
¾ Network-flow based algorithms
¾ Linear assignment formulation
․ Drawback: hard to handle larger problems

Sequential Concurrent

20
Courtesy of Y.-W. Chang
 Hierarchical Routing Framework
․The hierarchical approach recursively divides a routing
region into a set of subregions and solve those
subproblems independently.
․Drawbacks: lack the global information for the interaction
among subregions.

21
Courtesy of Y.-W. Chang
 Hierarchical Routing Revisited
․ Global routing can be formulated as a linear assignment problem:
¾ xi,j = 1 if net i is assigned to section j; xi,j = 0 otherwise.
¾ Each net crosses the cut line exactly once:
¾ Capacity constraint of each section:
¾ wij: cost of assigning net i to section j. Minimize

a
a
cut
line
b
b
chip plane

22
Courtesy of Y.-W. Chang
 Multilevel Full-Chip Routing Framework
․ Lin and Chang, “A novel framework for multilevel routing considering
routability and performance,” ICCAD-2002 (TCAD, 2003).
․ Multilevel framework: coarsening followed by uncoarsening.
․ Coarsening (bottom-up) stage:
¾ Constructs the net topology based on the minimum spanning
tree.
¾ Processes routing tiles one by one at each level, and only local
nets (connections) are routed.
¾ Applies two-stage routing of global routing followed by detailed
routing.
¾ Uses the L-shaped & Z-shaped pattern routing.

¾ Performs resource estimation after detailed routing to guide the

routing at the next level.

․ Uncoarsening (top-down) stage
¾ Completes the failed nets (connections) from the coarsening
stage.
¾ Uses a global and a detailed maze routers to refine the solution.

23
Courtesy of Y.-W. Chang
A Multilevel Full-Chip Routing Framework

24
Courtesy of Y.-W. Chang
 Coarsening Stage
․Build MSTs for all nets and decompose them into two-
pin connections.
․Route local nets (connections) from level 0.
¾ Two-stage routing (global + detailed routing) for a

local net.

an MST edge global route detailed route

level k level 0 level k

25
Courtesy of Y.-W. Chang
 Global Routing

․Apply pattern routing for global routing

¾ Use L-shaped and Z-shaped connections to route
nets.
¾ Has lower time complexity than maze routing.

Lower L-Shaped Upper L-Shaped Z-Shaped

connection connection connection

26
Courtesy of Y.-W. Chang
 Detailed Routing
․Via minimization
¾Modify the maze router to minimize the number of
bends.
․Local refinement
¾ Apply general maze routing to improve the detailed

routing results.
․Resource estimation
¾ Update the edge weights of the routing graph after

detailed routing.

27
Courtesy of Y.-W. Chang
 Via Minimization

Wave
Back
Propagation
Trace
1 0 1 1 1 1 1
3 2 3 4 5 6 7
1 0 1 Unrouteable
2 1 2 Obstacle
b (u)
0 0 3
2 2
d (u) 1 S 1 7 T
1 0 2 2
2 1 6 7
1 0 1 1 1 1 1
3 2 3 4 5 6 7

28
Courtesy of Y.-W. Chang
 Local Refinement
․Local refinement improves detailed routing results by
merging two connections which are decomposed from
the same net.

an MST edge global route detailed route

level k level 0 level k

29
Courtesy of Y.-W. Chang
 Resource Estimation
․Global routing cost is the summation of congestions of
all routed edges.
․Define the congestion, Ce, of an edge e by
1
Ce = ( pe - d e )
,
2
where pe and de are the capacity and density, respectively.
․Update the congestion of routed edges to guide the
subsequent global routing.

30
Courtesy of Y.-W. Chang
 Uncoarsening Global Routing
․Use maze routing.
․Iterative refinement of a failed net is stop when a route
is found or several tries have been made.

Coarsening stage Uncoarsening stage

31
Courtesy of Y.-W. Chang
 Routing Comparisons
• 100% routing completion for all (11) benchmark circuits
– Three-level routing: 0 completion (ISPD-2K)
– Hierarchical routing: 2 completions (ICCAD-2001)
– Previous multilevel routing: 2 completions (ICCAD-2001)
• Can complete routings using even fewer routing layers.

32
Courtesy of Y.-W. Chang
 Routing Solution for Prim2
• 0.18um technology, pitch = 1 um, 8109 nets.
• Two layers, 100% routing completion.

33
Courtesy of Y.-W. Chang
 Summary: Detailed Routing
․Channel routing is considered a well solved problem.
․Hierarchical and multilevel are keys to handle large-
scale routing problems.
․Routing frameworks
¾ Λ-shaped routing: ICCAD-02 (TCAD-03); ASP-DAC-05 (TCAD-
07)
¾ V-shaped routing: ASP-DAC-06
¾ Two-pass bottom-up routing: DAC-06 (TCAD-08)
․Routing considerations for nanometer technology
¾ Noise (crosstalk) constraints
¾ Buffer insertion for timing optimization
¾ Additional design rules: antenna effect, redundant via, OPC
(optical proximity correction), CMP (chemical mechanical
polishing), double patterning, e-beam
¾ Electromigration constraints
34
Courtesy of Y.-W. Chang
 Appendix A:
Other Channel Routing
Algorithms

35
Courtesy of Y.-W. Chang
 Yoshimura-Kuh (YK) Algorithm
․Yoshimura & Kuh, “Efficient algorithms for channel
routing,” IEEE TCAD, Jan. 1982.
․YK algorithm considers both HCG and VCG.
․Nets are assigned to minimize the effect of vertical
constraint chains in VCG.
․Does not allow “unrestricted” doglegs and cannot
handle vertical constraint cycles.
․Algorithm consists of two major steps:
¾ Zone representation of horizontal segments.

¾ Merging of nets.

․The two steps are carried out to minimize vertical

constraints and track assignment.
․Same idea can be extended to three-layer channel
routing (Chen & Liu, IEEE TCAD, 1984)
36
Courtesy of Y.-W. Chang
 Zone Representation of Horizontal Segments
․ Zones are maximal clique in the interval graph of horizontal net
segments.
․ S(i): set of nets whose horizontal segments intersect Column i.
․ Zone numbers are assigned to the columns at which S(i) is
maximum.

37
Courtesy of Y.-W. Chang
 Merging of Nets
․Two nets ni and nj can be merged if
¾ there is no edge between vi and vj in HCG,
¾ no directed path exists between vi and vj in VCG.

38
Courtesy of Y.-W. Chang
 Zone Processing

․Track 1 (Track 2): net (1, 7) or net 4; track 3: net (5, 6,

9); track 4 (track 5): net 2 or net (3, 8)

39
Courtesy of Y.-W. Chang
 Minimizing the Longest Path
․Merge 2 nodes so as to minimize the increase of the
longest path length in the VCG.
․Heuristic rule to select nets to merge sequentially.

40
Courtesy of Y.-W. Chang
 Algorithm for Merging Nets
Algorithm: Net_Merging(zs, zt)
zs: Leftmost zone;
zt: rightmost zone;

1 begin
2 L ¬ { };
3 zs ¬ leftmost zone; zt ¬ rightmost zone;
4 for z ¬ zs to zt do
5 L ¬ L + {nets which terminate at or before zone z};
6 R ¬ {nets which begin at zone z+1};
7 Merge L and R so as to minimize the increase of the
longest path in the vertical constraint graph;
8 L ¬ L - {n1, n2, …, nj}, where {n1, n2, …, nj} are the nets
merged at Step 7;
9 end

41
Courtesy of Y.-W. Chang
 Implementation
․Procedure to select 2 nodes for merging
¾ For m Î LEFT (set of nodes on the left path)

¾ For n Î RIGHT, m Î LEFT

․Two steps
¾ Find m* Î LEFT which maximizes f(m)
¾ Find n* Î RIGHT which minimizes g(n, m*)

42
Courtesy of Y.-W. Chang
 Algorithm for the Implementation

Algorithm: Merge_Implementation(LEFT, RIGHT)

LEFT: left s-to-t path;
RIGHT: right s-to-t path;

1 begin
2 while LEFT ¹ Æ do
3 Among LEFT, find m* which maximizes f(m);
4 Among RIGHT, find n* which minimizes g(n, m*), and
which is neither ancestor nor successor of m*;
5 Merge n* and m*;
6 Remove m* and n* from LEFT and RIGHT, respectively;
7 end

43
Courtesy of Y.-W. Chang
 Merging Considerations
․A merging of 2 nodes may block subsequent mergings.

44
Courtesy of Y.-W. Chang
 Second Approach Based on Matching

․Global merging of
nets using
algorithms for
maximum
cardinality
matching.
․Delay net merging.

45
Courtesy of Y.-W. Chang
 Cyclic Conflicts
․Simultaneous merging can produce cyclic conflicts.

․How to modify a matching with cyclic conflicts to get a

feasible matching?

46
Courtesy of Y.-W. Chang
 Feasible Matching
algorithm
․Bipartite graph Gh = (N, Eh): Gh Ex = a set of edges in
Gh.
․The merging corresponding to any matching on Gh is
feasible Û Ex = Æ.
․The merging corresponding to any matching on Gr = (N,
Eh - Ex) is feasible.
․Procedures to get a feasible matching
¾ Find a matching in Gh.
¾ Apply an algorithm to the graph Gm = (N, M) (M: set of
edges in the matching)
¾ If Ex = Æ then the matching is feasible!
¾ Else apply an algorithm to Gh and obtain E’x; compute a
new matching in (N, Eh – E’x).

47
Courtesy of Y.-W. Chang
Identifing Ex

48
Courtesy of Y.-W. Chang
 Feasibility Condition
․The merging corresponding to any matching on Gr = (N,
Eh - Ex) is feasible (no cycle in VCG).

49
Courtesy of Y.-W. Chang
 Comments on the YK Algorithm
․Use a process “merging of subnets” to avoid
unnecessary introduction of dogleg.
¾ Subnet i and subnet j can be merged only if merging
subnet i and subnet j will not increase the longest path
length passing through node i and node j on VCG.
․Need not start at Zone 1. Can obtain better results by
starting at the maximum density zone.
¾ Chan, “A new channel routing algorithm,” CIT VLSI
Design Conf., 1983.

50
Courtesy of Y.-W. Chang
 Restricted vs. Unrestricted Doglegging
․Unrestricted doglegging: Allow a dogleg even at a
position where there is no pin.
․Restricted doglegging: Allow a dogleg only at a
position where there is a pin belonging to that net.
․The YK channel router does not allow unrestricted
doglegging.

51
Courtesy of Y.-W. Chang
 Greedy Channel Router
․Rivest & Fiduccia, “A greedy channel router,” DAC-82,
(IEEE TCAD, May 1983).
․Always succeed (even if cyclic conflict is present)
․Allows unrestricted dogleg
․Allows a net to occupy more than 1 track at a given
column.
․May use a few columns off the edge.

52
Courtesy of Y.-W. Chang
 Overview of Greedy Router
․ Left-to-right, column-by-column scan.
1 begin
2 c ¬ 0;
3 while (not done) do
4 c ¬ c + 1;
5 Complete wiring at column c;
6 end
․ In general, a net may be
1. empty (net 5)
2. unsplit (nets 1, 4)
3. split (net 3)
4. completed (net 2) 0

53
Courtesy of Y.-W. Chang
 Greedy Heuristics
․At each column, the greedy router tries to maximize the
utility of the wiring produced:
¾ A: Make minimal feasible top/bottom connections;

¾ B: Collapse split nets;

¾ C: Move split nets closer to one another;

¾ D: Raise rising nets/Lower falling nets;

¾ E: Widen channel when necessary;

¾ F: Extend to next column.

54
Courtesy of Y.-W. Chang
A: Make Minimal Feasible Top/Bottom Connections

55
Courtesy of Y.-W. Chang
B: Collapse Split Nets

56
Courtesy of Y.-W. Chang
 Heuristics: C, D, E, and F
․ C: Move split nets closer to one another;
․ D: Raise rising nets/Lower falling nets;
․ E: Widen channel when necessary;
․ F: Extend to next column.

57
Courtesy of Y.-W. Chang
 Parameters to Greedy Router
․Initial-channel-width: icw
․Minimum-jog-length: mjl
․Steady-net-constant: snc (window size in terms of # of
columns; determines # of times a multipin net changes
tracks)
․Usually start icw as d, the density.
․mjl controls the number of vias, use a large mjl for
fewer vias.
․snc also controls # of vias. Typically, snc = 10.

58
Courtesy of Y.-W. Chang
 Greedy Routing Example

․ C3: Connect pin 5 to T3 ® Jog net 5 from T3 to T2 (since net 5 is rising).

․ C4: Connect pin 5 to T2 ® Jog net 5 from T2 to T3 (since net 5 is falling).
․ C 6: Connect pin 1 to T0 ® Jog net 1 from T0 to T3 (since net 1 is falling).
․ C 7: Connect pin 7 to T5 ® Merge tracks T2 and T5 (last pin 7).
․ C 8: Connect pin 1 to T5 ® Jog net 6 from T0 to T2 and net 1 from T5 to T3.
․ … … … … … …
59
Courtesy of Y.-W. Chang
Comparison of Two-Layer Channel Routers

60
Courtesy of Y.-W. Chang
 Comparison of Two-Layer Channel Routers
․Comparison using the benchmark example: Deutsch's
“difficult example.”
․Channel density: 19

61
Courtesy of Y.-W. Chang
 Robust Channel Router
․Yoeli, “A robust channel router,” IEEE TCAD, 1991.
․Alternates between top and bottom tracks until the
center is reached.
․The working side is called the current side.
․Net weights are used to guide the assignment of
segments in a track, which
¾ favor nets that contribute to the channel density;
¾ favor nets with terminals at the current side;
¾ penalize nets whose routing at the current side would
cause vertical constraint violations.
․Allows unrestricted doglegs by rip-up and re-route.

62
Courtesy of Y.-W. Chang
 Robust Channel Router
․ Select the set of nets for the current side by solving the
maximum weighted independent set problem for interval
graphs.
¾ NP-complete for general graphs, but can be solved efficiently
for interval graphs using dynamic programming.
․ Main ideas:
¾ The interval for net i is denoted by [ximin, ximax]; its weight is wi.
¾ Process channel from left to right column; the optimal cost for
position c is denoted by total[c];
¾ A net n with a rightmost terminal at position c is taken into the
solution if total[c – 1] < wn + total[xnmin – 1].
․ Can apply maze routers to fix local congestion or to post-
process the results. (Why not apply maze routers to channel
routing directly??)

63
Courtesy of Y.-W. Chang
 Interval Graphs
․There is a vertex for each interval.
․Vertices corresponding to overlapping intervals are
connected by an edge.
․Solving the track assignment problem is equivalent to
finding a minimal vertex coloring of the graph.

64
Courtesy of Y.-W. Chang
 Weight Computation
1 2 3 4 3
d(1) = 1
d(2) = 2
d(3) = 2
d(4) = 3 (nets 2, 3, 4)
d(5) = 2
1 2 4
․ Computation of the weight wi for net i:
1. favor nets that contribute to the channel density: add a large B
to wi.
2. favor nets with current side terminals at column x: add d(x) to wi.
3. penalize nets whose routing at the current side would cause
vertical constraint violations: subtract Kd(x) from wi, K = 5 ~ 10.
¾ Assume B = 1000 and K = 5 in the 1 iteration (top side):
st

n w1 = (0) + (1) + (-5 * 2) = -9

n Net 1 does not contribute to the channel density

n One net 1 terminal on the top

n Routing net 1 causes a vertical constraint from net 2 at

column 2 whose density is 2

65
Courtesy of Y.-W. Chang
 Weight Computation (cont’d)
1 2 3 4 3
d(1) = 1
d(2) = 2
d(3) = 2
d(4) = 3 (nets 2, 3, 4)
d(5) = 2
1 2 4
․Computation of the weight wi for net i:
1. favor nets that contribute to the channel density: add a large B
to wi.
2. favor nets with current side terminals at column x: add d(x) to wi.
3. penalize nets whose routing at the current side would cause
vertical constraint violations: subtract Kd(x) from wi, K = 5 ~ 10.
¾ Assume B = 1000 and K = 5 in the 1 iteration (top side):
st

n w1 = (0) + (1) + (-5 * 2) = -9

n w2 = (1000) + (2) + (-5 * 3) = 987

n w3 = (1000) + (2+2) + (0) = 1004

n w4 = (1000) + (3) + (-5 * 2) = 993

66
Courtesy of Y.-W. Chang
 Top-Row Net Selection
1 2 3 4 3 1 2 3 4 3

1 2 4 1 2 4
․ w1 = -9, w2 = 987, w3 = 1004, w4 = 993.
․ A net n with a rightmost terminal at position c is taken into the
solution if: total[c – 1] < wn + total[xnmin – 1].
total[1] = 0 selected_net[1] = 0
total[2] = max(0, 0-9) = 0 selected_net[2] = 0
total[3] = 0 selected_net[3] = 0
total[4] = max(0, w2+total[1]) = 987 selected_net[4] = 2
total[5] = max(987, 0+1004, 0+993) = 1004 selected_net[5] = 3
․ Select nets backwards from right to left and with no horizontal
constraints: Only net 3 is selected for the top row. (Net 2 is not
selected since it overlaps with net 3.)
67
Courtesy of Y.-W. Chang
 Bottom-Row Net Selection
1 2 3 4 3 1 2 3 4 3

1 2 4
1 2 4
․ 2nd iteration: bottom-row selection
¾ w1 = (1000) + (2) + (0) = 1002
¾ w2 = (1000) + (2) + (-5 * 2) = 992
¾ w4 = (1000) + (1) + (-5 * 2) = 991
total[1] = 0 selected_net[1] = 0
total[2] = max(0, 0+1002) = 1002 selected_net[2] = 1
total[3] = 1002 selected_net[3] = 0
total[4] = max(1002, 0+992) = 1002 selected_net[4] = 0
total[5] = max(1002, 1002+991) = 1993 selected_net[5] = 4
․ Nets 4 and 1are selected for the bottom row.
68
Courtesy of Y.-W. Chang
 Maze Routing + Rip-up & Re-route
1 2 3 4 3
1 2 3 4 3

1 2 4
1 2 4
․3rd iteration
¾ Routing net 2 in the middle row leads to an infeasible
solution.
¾ Apply maze routing and rip-up and re-route nets 2 and 4
to fix the solution.

69
Courtesy of Y.-W. Chang
 Robust Channel Router

/* for */

/* if */
/* for */

70
Courtesy of Y.-W. Chang
 Appendix B:
Switchbox Routing

71
Courtesy of Y.-W. Chang
 Greedy Switchbox Router
․ Luk, “A greedy switchbox routing,” INTEGRATION, the VLSI
Journal, 1985.
․ Based on the greedy channel router (Rivest & Fiduccia).
․ Terminals on left boundary are brought to the 1st column as
horizontal tracks.
․ Nets are jogged to target rows in additional to jogging to next top or
bottom terminals.
․ Various jogging schemes are applied.

72
Courtesy of Y.-W. Chang
 Jogging Schemes
․JogR: Nets with terminals on the right boundary; the jog
is performed until matching the right positions.
․JogT/B: Nets with terminals only on the top and bottom;
similar to the greedy channel router.
․JogT/B: JogR: First perform JogT/B; switch to JogR when
the last top or bottom terminal appears.

73
Courtesy of Y.-W. Chang
 Appendix C:
Over-the-Cell Routing

74
Courtesy of Y.-W. Chang
 Over-the-Cell Routing
․ Routing over the cell rows is possible due to the limited use
of the 2nd (M2) metal layers within the cells.
․ Divide the over-the-cell routing problem into 3 steps: (1)
routing over the cell, (2) choosing the net segments, and (3)
routing within the channel.
․ Reference: Cong & Liu, “Over-the-cell channel routing,”
IEEE TCAD, Apr. 1990.

75
Courtesy of Y.-W. Chang
 Over-the-Cell Channel Routing
․Cong & Liu, “Over-the-cell channel routing,” IEEE
TCAD, Apr. 1990.

76
Courtesy of Y.-W. Chang
 Supowit's Algorithm
․ Supowit, “Finding a maximum planar subset of a set of nets
in a channel,” IEEE TCAD, 1987.
․ Problem: Given a set of chords, find a maximum planar
subset of chords.
¾ Label the vertices on the circle 0 to 2n-1.
¾ Compute MIS(i, j): size of maximum independent set between
vertices i and j, i < j.
¾ Answer = MIS(0, 2n-1).

Vertices on the circle

77
Courtesy of Y.-W. Chang
Dynamic Programming in Supowit's Algorithm
․Apply dynamic programming to compute MIS(i, j ).

78
Courtesy of Y.-W. Chang
 Appendix D:
Gridless Routing

79
Courtesy of Y.-W. Chang
 Gridless Full-Chip Routing
․Chen and Chang, “Multilevel full-chip gridless routing
considering optical proximity correction,” ASPDAC-05.
․Is based on the multilevel routing framework.
․Applies the implicit connection graph to transform the
gridless structure into a “grid”-like structure.
․Adopts the interval tree to do range query for identifying
obstacles and available spaces.
․Congestion metric is based on available routing space in
a region.
․Gridless routing is needed for handling some nanometer
effects like OPC, metal slotting, etc.

80
Courtesy of Y.-W. Chang
 Implicit Connection Graph
․Given a set of obstacles and a source s and sink t
․GS is an orthogonal grid graph

81
Courtesy of Y.-W. Chang
 Implicit Representation of GS
․Store x, y coordinates into two sorted arrays
․O(n) space & O(n lg n)-time pre-construction (n: # of
rectangles)
y1
y2 T
y3
y4
y5
y6
y7 S
y8

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
82
Courtesy of Y.-W. Chang
 Interval Tree
․ Partition the chip plane into rows and keep a query tree for
each row.
․ The query tree stores cut blocks in the internal nodes.
․ Uncut blocks are stores in the leaf nodes.
․ Question: Is q in free space? Need average O(lg n) time to
answer.

b
b
q c d
d
c

83
Courtesy of Y.-W. Chang
 Block Insertion
․To insert a block (say, block e), we traverse the query
tree from the root down to an internal node until it is
cut, or a leaf node if it is uncut.
․Average time complexity: O(lg n).

b e
b
q c d
d
e
c

84
Courtesy of Y.-W. Chang
 Block Deletion
․To delete a block (say, block c), we traverse the query
tree from the root down to a node that stores the block
name and delete the block.
․Average time complexity: O(lg n).

b e
b
q c d
d
e
c

85
Courtesy of Y.-W. Chang
 Complexity Summary
․ Interval (query) tree

Average Complexity

Memory Usage O(n2)

Block Insertion O(lg n)
Block Deletion O(lg n)
Point Finding O(lg n)
Neighbor Finding O(1)

n: number of blocks

86
Courtesy of Y.-W. Chang
 Routing Solution for s5378

The routing solution of

”s5378” with non-
uniform (above) and
uniform (below) nets

Courtesy of Tai-Chen Chen

87
Courtesy of Y.-W. Chang
 Appendix E:
V-Shaped Gridless Routing

G2 To-be-routed net G2
Already-routed net

G1 G1

Uncoarsening Coarsening
G0 G0

Uncoarsening Coarsening

88
Courtesy of Y.-W. Chang
 Λ-Shaped Multilevel Routing

Perform global pattern routing and Use global maze routing and
Dijkstra’s shortest path detailed routing Dijkstra’s shortest path detailed
for local connections and then estimate routing to reroute failed
routing resource for the next level. connections and refine the solution.

Coarsening Uncoarsening

Coarsening Uncoarsening

G2 G2
G1 G1
G0 To-be-routed net G0
Already-routed net

Does not have the view of the global configuration

at the earlier stages.
89
Courtesy of Y.-W. Chang
 V-Shaped Multilevel Framework

G2 To-be-routed net G2
Already-routed net

G1 G1

Uncoarsening Coarsening
G0 G0

Uncoarsening Coarsening

Perform global pattern routing and Use global maze routing and Dijkstra’s
Dijkstra’s shortest path detailed routing shortest path detailed routing to
for local nets and then estimate routing reroute failed connections and refine
resource for the next level. the solution.

Consider the global effects at the earlier stages.

90
Courtesy of Y.-W. Chang
 Design Flow

Channel density
initialization
Uncoarsening stage Coarsening stage

Global pattern routing Global maze routing

Detailed routing Detailed routing

N N
Lowest level? Top level?

Y Y

Final routing
91
Courtesy of Y.-W. Chang
 Channel Density Initialization and Updated

․Making the global routing, detailed routing, and

resource estimation interact with each other can
significantly improve routing completion rates
¾ Only guide the latter nets passing through the area with lower
congestion
¾ Cannot avoid determining the bad global path of an early routed
net without considering the routing resource of succeeding nets.
․Initialize the congestion map based on the pin
distribution and the global-path prediction of all nets
․Update the congestion map dynamically based on both
the already routed nets and the estimated unrouted nets
․Have better congestion control throughout the whole
routing process

92
Courtesy of Y.-W. Chang
 Uncoarsening Stage
․Global effect is the highest consideration in this stage
Longer nets are more critical
¾

․Start from the coarsest tiles of level k; route level nets

at each level

To-be-routed net
G2 G2
Already-routed net

G1 G1

Uncoarsening Coarsening
un G0 G0
co
ar
se Uncoarsening Coarsening
ni
ng

93
Courtesy of Y.-W. Chang
 Coarsening Stage
․Routability is the highest consideration in this stage
Shorter connections are more critical
¾

․Repeat the same steps as the uncoarsening stage

¾ Perform maze routing at the global routing stage

To-be-routed net
G2 G2
Already-routed net

G1 G1

Uncoarsening Coarsening
G0 G0

Uncoarsening Coarsening g
in
s en
a r
co
94
Courtesy of Y.-W. Chang
 Cost Function for Global Routing
․The cost function is the sum of the maximum channel
congestion and the average of the total path congestion
¾ Can avoid selecting a path with lower total path congestion and
higher channel congestion path
¾ Can avoid selecting a path with higher overall path congestion
when two path have the same maximum channel congestion

ce: the congestion of edge e

0.4 0.1
f g T
P1 has the minimal total path congestion
0.4 0.6 0.3
0.3 d 0.6 e
P2 and P3 have the same maximum
P3 c
P1 channel congestion
0.7 P2 0.6 0.2 P3 has the minimum cost
S 0.9 a 0.1 b
95
Courtesy of Y.-W. Chang
 Triple-Line Graph (TLG) Model
․Find a design-rule-correct path and avoid redundant
wires
․Construct the obstacle zones (gray areas) from the
obstacles by taking design rules into account
¾ expand the obstacle for a range which is the sum of the obstacle
spacing and the half width of the routing wire
¾ The area outside of the obstacle zones is available for placing
the center lines of wires and mid-points of contacts
obstacle
obstacles zones
S S
T T

a routing example obstacle zones construction 96

Courtesy of Y.-W. Chang
 TLG Model (Cont’d)
․Collect all x-coordinates and y-coordinates of
¾ the source and the target
¾ the boundaries of all obstacle zones
¾ the centers of all obstacle zones (P-lines and C-lines)
․Generate a vertical (horizontal) dashed line for each x-
coordinate (y-coordinate)
․Construct a connection graph
¾ a node in the connection graph denotes an intersection of a
horizontal and a vertical dashed lines
obstacles
S S
T T

a routing exampleCourtesy of Y.-W. Chang

a connection graph 97
 P-Lines
․To avoid design-rule-incorrect paths
¾ pass the center of the obstacle zone
¾ Is perpendicular to the routing direction of the obstacle zone

Wi/2

S
DS
T
obstacle

P-line

a routing example
S T S T

unroutable
point

A design-rule-incorrect path A design-rule-correct path

98
Courtesy of Y.-W. Chang
 C-Lines
․To avoid redundant wires
¾ pass the center of the obstacle zone
¾ Is parallel to the routing direction of the obstacle zone
S
Wi/2

DS

pre-routed wire T
C-lines
S a routing example S

T T
touch points
A path with an redundant wire A path without redundant wires99
Courtesy of Y.-W. Chang