Detailed Routing
Detailed Routing
Find actual geometric layout of each net within assigned routing regions. No layouts of two different nets should intersect on the same layer. Problem is solved incrementally, one region at a time in a predefined order.
Global Routing
Detailed Routing
Compaction
CAD for VLSI 2
A Routing Example
CAD for VLSI
After Global Routing
The two-stage routing method is a powerful technique for routing in VLSI circuits. During the global routing stage
The routing region is partitioned into a collection of rectangular regions. To interconnect each net, a sequence of sub-regions to be used is determined. All nets crossing a given boundary of a routing region are called floating terminals. Once the sub-region is routed, these floating terminals become fixed terminals for subsequent regions.
CAD for VLSI
Order of Routing Regions
Slicing placement topology Nets can be routed by considering channels 1, 2 and 3 in order. 1 3 2
Non-slicing placement topology. Channels with cyclic constraints. Some of the routing regions are to be considered as switchboxes.
1 2
4 3
CAD for VLSI
Channels and Switchboxes
There are normally two kinds of rectilinear regions.
Channels: routing regions having two parallel rows of fixed terminals. Switchboxes: generalizations of channels that allow fixed terminals on all four sides of the region.
Channel
Switchbox
CAD for VLSI
Routing Considerations
Number of terminals
Majority of nets are two-terminal ones. For some nets like clock and power, number of terminals can be very large. Each multi-terminal net can be decomposed into several two-terminal nets.
Net width
Power and ground nets have greater width. Signal nets have less width.
CAD for VLSI
Contd.
Via restrictions
Regular: only between adjacent layers. Stacked: passing through more than two layers.
Boundary type
Regular: straight border of routing region Irregular
Number of layers
Modern fabrication technology allows at least five layers of routing.
Net types
Critical: power, ground, clock nets Non-critical: signal nets
CAD for VLSI
Routing Models
Grid-based model
A grid is super-imposed on the routing region. Wires follow paths along the grid lines.
Gridless model
Does not follow the gridded approach.
CAD for VLSI
Models for Multi-Layer Routing
Unreserved layer model
Any net segment is allowed to be placed in any layer.
Reserved layer model
Certain types of segments are restricted to particular layer(s). Two-layer (HV, VH) Three-layer (VHV, HVH)
CAD for VLSI
10
Illustration
HVH Model
VHV Model
Unreserved Layer Model
CAD for VLSI 11
Channel Routing
In channel routing, interconnections are made within a rectangular region having no obstructions.
A majority of modern-day ASICs use channel routers. Algorithms are efficient and simple. Guarantees 100% completion if channel width is adjustable.
Some terminologies:
Track: horizontal row available for routing. Trunk: horizontal wire segment. Branch: vertical wire segment connecting trunks to terminals. Via: connection between a branch and a trunk.
CAD for VLSI
12
Channel Routing Problem :: Terminologies
1 2 0 2 3 Upper boundary
Lower boundary
Net list:: TOP = [1 2 0 2 3 ] BOT = [3 3 1 1 0 ] 1 2 0 2 3
1
CAD for VLSI
0
13
Problem Formulation
The channel is defined by a rectangular region with two rows of terminals along its top and bottom sides.
Each terminal is assigned a number between 0 and N. Terminals having the same label i belong to the same net i. A 0 indicates no connection.
The netlist is usually represented by two vectors TOP and BOT.
TOP(k) and BOT(k) represents the labels on the grid points on the top and bottom sides of the channel in column k, respectively.
CAD for VLSI
14
Contd.
The task of the channel router is to:
Assign horizontal segments of nets to tracks. Assign vertical segments to connect Horizontal segments of the same net in different tracks. The terminals of the net to horizontal segments of the net.
Channel height should be minimized. Horizontal and vertical constraints must not be violated.
CAD for VLSI
15
Contd.
Horizontal constraints between two nets:
The horizontal span of two nets overlaps each other. The nets must be assigned to separate tracks.
Vertical constraints between two nets:
There exists a column such that the terminal i on top of the column belongs to one net, and the terminal j on bottom of the column belongs to the other net. Net i must be assigned a track above that for net j.
CAD for VLSI
16
Horizontal Constraint Graph (HCG)
It is a graph where vertices represent nets, and edges represent horizontal constraints.
1 5 2 0 2 1 1 0 3 4 0 5 2 3 0 1 2 5 3 4 0 0 2 3 4 3 1
CAD for VLSI
17
Vertical Constraint Graph (VCG)
It is a directed graph where vertices represent nets, and edges represent vertical constraints.
1 5 2 0 2 1 1 0 3 4 0 4 3 0 1 2 5 3 4 0 0 2 3 1
3 5
CAD for VLSI
18
Two-layer Channel Routing
Left-Edge Algorithms (LEA)
Basic Left-Edge Algorithm Left-Edge Algorithm with Vertical Constraints Dogleg Router
Constraint-Graph Based Algorithm
Net Merge Channel Router Gridless Channel Router
Greedy Channel Router Hierarchical Channel Router
CAD for VLSI
19
Basic Left Edge Algorithm
Assumptions:
Only two-terminal nets. No vertical constraints. HV layer model. Doglegs are not allowed.
Basic Steps:
Sort the nets according to the x-coordinate of the leftmost terminal of the net. Route the nets one-by-one according to the order. For a net, scan the tracks from top to bottom, and assign it to the first track that can accommodate it.
In the absence of vertical constraints, the algorithm produces a minimum-track solution.
CAD for VLSI 20
Contd.
Extension to Left-Edge Algorithm
Vertical constraints may exist, but there are no directed cycles in the VCG. Select a net for routing if
The x-coordinate of the leftmost terminal is the least. There is no edge incident on the vertex corresponding to that net in the VCG.
After routing a net, the corresponding vertex and the incident edges are deleted from the VCG. Other considerations same as the basic left-edge algorithm.
CAD for VLSI
21
Illustration
1 0 1 4 2 5 4 7 5 0 0 8
2 1
3 3
0 7
6 8
6
CAD for VLSI
VCG
22
Dogleg Router
Drawback of LEA
The entire net is on a single track. Sometimes leads to routing with more tracks than necessary.
Doglegs are used to place parts of the same net on different tracks.
A dogleg is a vertical segment that connects two trunks located in two different tracks. May lead to a reduction in channel height.
CAD for VLSI
23
Contd.
Dogleg router allows multi-terminal nets and vertical constraints.
Multi-terminal nets can be broken into a series of twoterminal nets.
Cannot handle cyclic vertical constraints.
CAD for VLSI
24
Example
1 1 2 3 2 0 1 1 2 3 2 0
No dogleg 3 tracks
With dogleg 2 tracks
CAD for VLSI
25
Dogleg Router: Algorithm
Step 1:
If cycle exists in the VCG, return with failure.
Step 2:
Split each multi-terminal net into a sequence of 2-terminal nets.
A net 2 .. 2 .. 2 will get broken as 2a .. 2a 2b .. 2b.
HCG and VCG gets modified accordingly.
Step 3:
Apply the extended left-edge algorithm to the modified problem.
CAD for VLSI
26
Illustration
0 1 2 2 4 3 0 0 1 2
0 2a 2b
2b
4a
3b
2a
2b 1 2a 0 3a 3a 3b 0 4a 4b 4b 4a
3a 3b
27
CAD for VLSI
2a 2b
2b
4a
3b
2b
4a
4b
2a
3a
3b
2a
3a
3a 3b
4a 4b
4b
CAD for VLSI
28
Net Merge Channel Router
Due to Yoshimura and Kuh. Basic idea:
If there is a path of length p in the VCG, at least p horizontal tracks are required to route the channel. Try to minimize the longest path in the VCG. Merge nodes of VCG to achieve this goal.
Does not allow doglegs or cycles in the VCG. How does it work?
Partition the routing channel into a number of regions called zones. Nets from adjacent zones are merged. Merged nets are treated as a composite net and assigned to a single track.
CAD for VLSI 29
Contd.
Key steps of the algorithm:
a) b) c) Zone representation Net merging Track assignment
An example: 0 1 4 5 1 6 7 0 4 9 10 10
9
30
CAD for VLSI
Step 1: Zone Representation
Let S(i) denote the set of nets whose horizontal segments intersect column i. Take only those S(i) which are maximal, that is, not a proper subset of some other S(j). Define a zone for each of the maximal sets. In terms of HCG / interval graph, a zone corresponds to a maximal clique in the graph.
CAD for VLSI
31
Zone Representation Zone Table
Column 1 2 3 4 5 6 7 8 9 10 11 12 S(i) {2} {1,2,3} {1,2,3,4,5} {1,2,3,4,5} {1,2,4,5} {2,4,6} {4,6,7} {4,7,8} {4,7,8,9} {7,8,9} {7,9,10} {9,10} Zone Z1 Z2
1 2 3
Z3
7
Z4
8 9
Z5
4 5 6
10
2 3 4 5
1 5 3
4 9 8
10 7 6
32
CAD for VLSI
VCG
Step 2: Net Merging
Let Ni and Nj be two nets for which the following conditions are satisfied:
There is no edge between vi and vj in HCG. There is no directed path between vi and vj in VCG.
Nets Ni and Nj can then be merged to form a new composite net.
Modifies VCG by merging nodes vi and vj into a single node vi.j. Modifies HCG / zone representation by replacing nodes vi and vj by a net vi-j, which occupies the consecutive zones including those of nets Ni and Nj.
CAD for VLSI
33
Contd.
The process is iterative:
Pairs of nodes are successively merged. At every step of the iteration, in case of multiple choices, merge the net-pair that minimizes the length of the longest path in the VCG. That is, the increase in length is minimum.
A result:
If the original VCG has no cycles, then the updated VCG with merged nodes will not have cycles either.
CAD for VLSI
34
Contd.
Iteration 1 of the example:
We can merge nets pairs (1,6), (3,6) or (5,6).
1.6 5 3 2
4 9 8
10 7 1 5.6 3 2 4 9 8 10
1 5 3.6 7 2
4 9 8
10 7
Best Choice
CAD for VLSI 35
Contd.
Successive iteration steps: 10 10 4 5.6 3 2 9 8 2 3.8 2 3.8 1.7 5.6.9 5.6.9 4 1.7
4.10
1.7
CAD for VLSI
36
Step 3: Track Assignment
Each node in the final graph is assigned a separate track. Actually we apply the left-edge algorithm to assign horizontal tracks to the merged nets.
The list of nets sorted on their left edges, subject to the vertical constraint, is: [ 4-10, 1-7, 5-6-9, 2, 3-8 ] Track 1: Track 2: Track 3: Track 4: Track 5: Nets 4 and 10 Nets 1 and 7 Nets 5, 6 and 9 Net 2 Nets 3 and 8
CAD for VLSI
37
The Final Solution
0 1 4 5 1 6 7 0 4 9 10 10
6
CAD for VLSI
9
38
Greedy Channel Router
The routing algorithms discussed so far route the channel one net at a time.
Based on left-edge algorithm or some of its variation.
The Greedy Channel Router algorithm routes the channel column by column starting from the left.
Apply a sequence of greedy but intelligent heuristic at each column. Objective is to maximize the number of tracks available in the next column.
Can handle problems with cycles in VCG.
May need additional columns at the end of the channel.
CAD for VLSI
39
Contd.
Some of the heuristics used:
Place all segments column by column, starting from the leftmost column. Connect any terminal to the trunk segment of the corresponding net. Collapse any split net using a vertical segment. Try to reduce the distance between two tracks of same net. Try to move the nets closer to the boundary which contains the next terminal of that net. Add additional tracks if needed.
CAD for VLSI
40
Channel Routed using a Greedy Router
1 3 2 1 3 4 1 2 3
CAD for VLSI
41
Hierarchical Channel Router
Uses a divide-and-conquer approach. A routing problem in mn grid is reduced to 2n grid. Each column in these sub-grids is treated as a supercell. Capacity of each vertical boundary is the sum of corresponding boundary capacities. Nets are routed one at a time in the 2n grid. Each row of 2n is partitioned into 2n grid. Terminal position for the new 2n grids are defined by the routing in the previous hierarchy.
CAD for VLSI
42
Example
Reducing (mn) grid to (2n) grid
CAD for VLSI 43
Example (contd.)
First level of hierarchy
Second level of hierarchy
CAD for VLSI 44
Comparison of Two-Layer Channel Routers
LEA Model Dogleg Vertical constraint Cyclic constraint
Gridbased No No / Yes No
Dogleg
Gridbased Yes Yes No
Net Merge
Gridbased Yes Yes No
Greedy
Gridbased Yes Yes Yes
Hierarchical
Gridbased Yes Yes Yes
CAD for VLSI
45
Three-Layer Channel Routing Algorithms
Several approaches:
Extended Net Merge Channel Router HVH Routing from HV Solution Hybrid HVH-VHV Router
CAD for VLSI
46
HVH Routing from HV Solution
Very similar to the Y-K algorithm.
Systematically transform a two-layer routing solution into a three-layer routing solution. In Y-K algorithm, nets are merged so that all merged nets forming a composite net are assigned to one track. Here, the composite nets are merged together to form super-composite nets.
Objective:
Reduce the number of super-composite nets.
CAD for VLSI
47
Contd.
Two composite nets in a super-composite net can be assigned to different layers on the same track. A track-ordering graph is used to find the optimal pair of composite nets to be merged.
Vertices represent the composite (tracks) in a given twolayer solution. The directed edges represent the ordering restrictions on pairs of tracks.
Composite interval ti must be routed above composite interval tj, if there exists a net Npti and Nqtj, such that Np and Nq have a vertical constraint.
CAD for VLSI
48
Track ordering graph
CAD for VLSI
49
An optimal scheduling solution
Graph representation
CAD for VLSI
50
Limitations of HVH or VHV Router
CAD for VLSI
51
Partitioning for Hybrid Routing
CAD for VLSI
52
Hybrid HVH-VHV Router
Uses both HVH and VHV routing schemes. Pure HVH and VHV are special cases of Hybrid Router. It partitions the channel into two portions not necessarily of the same size.
One portion is for HVH and the other for VHV. One track is required for interconnection between the two portions.
CAD for VLSI
53
CAD for VLSI
54
Switchbox Routing
A switchbox is a generalization of a channel.
Has terminals on all four sides.
More difficult than channel routing problem.
Main objective of channel routing is to minimize the channel height. Main objective of switchbox routing is to ensure that all the nets are routed.
Classification of algorithms:
Greedy router Rip up and reroute routers BEAVER (based on computational geometry)
CAD for VLSI
55
CAD for VLSI
56
Summary
The detailed routing problem is solved by routing the channels and switchboxes. Routing results may differ based on the routing model used.
Grid-based. Based on assigning layer of different net segments.
The objectives for routing a channel is to minimize channel density, the length of routing nets, and the number of vias. The main objective of channel routing is to minimize the total routing area. The objective of switchbox routing is to determine the routability.
CAD for VLSI
57