UNIT IV
ROUTING
Contents
• Global Routing
Measurement of interconnect delay
Methods
Fixed blocks and Flexible blocks
Timing driven methods
• Detailed routing
Goals and objectives
Measurement of channel density
Algorithms
Special Routing
Introduction
Once the designer has floorplanned a chip and the logic cells within the
flexible blocks have been placed, it is time to make the connections by
routing the chip.
This is still a hard problem that is made easier by dividing it into smaller
problems.
Routing is usually split into global routing followed by detailed routing .
FIGURE 17.1 The core of the Viterbi decoder chip after placement (a screen shot
from Cadence Cell Ensemble)
FIGURE 17.2 The core of the Viterbi decoder chip after the completion of global and
detailed routing (a screen shot from Cadence Cell Ensemble). This chip uses two-level
metal. Although you cannot see the difference, m1 runs in the horizontal direction and m2
in the vertical direction.
Routing
• Connect the various standard cells using wires
• Input:
– Cell locations, netlist
• Output:
– Geometric layout of each net connecting various
standard cells
• Two-step process
– Global routing
– Detailed routing
6
Global routing vs detailed
routing*
7
Routing problem formulation
• Objective
– 100% connectivity of a system
– Minimize area
– Minimize wirelength
• Constraints
– Number of routing layers
– Design rules
– Timing (delay)
– Crosstalk
– Process variations
8
Global Routing
• The details of global routing differ slightly between cell-based ASICs, gate
arrays, and FPGAs, but the principles are the same in each case.
• A global router does not make any connections, it just plans them
• We typically global route the whole chip (or large pieces if it is a large chip)
before detail routing the whole chip (or the pieces).
• There are two types of areas to global route:
– between blocks
– inside the flexible blocks
Goals and Objectives
• Input: The floorplan that includes the locations of all the fixed and flexible
blocks; the placement information for flexible blocks; and the locations of all
the logic cells.
• The goal of global routing :-To provide complete instructions to the detailed
router on where to route every net.
• The objectives of global routing are,
– Minimize the total interconnect length.
– Maximize the probability that the detailed router can
complete the routing.
– Minimize the critical path delay.
Measurement of Interconnect Delay
• After placement, the logic cell positions are fixed and the global router can afford to use better
estimates of the interconnect delay.
• To illustrate one method, we shall use the Elmore constant to estimate the interconnect delay for the
circuit shown in Figure 17.3 .
FIGURE 17.3 Measuring the delay of a net. (a) A simple circuit with an inverter A driving a net with a
fanout of two. Voltages V 1 , V 2 , V 3 , and V 4 are the voltages at intermediate points along the net.
(b) The layout showing the net segments (pieces of interconnect). (c) The RC model with each
segment replaced by a capacitance and resistance. The ideal switch and pull-down resistance R pd
model the inverter A.
The problem is to find the voltages at the inputs to logic cells B and C taking
into account the parasitic resistance and capacitance of the metal interconnect.
Figure 17.3 (c) models logic cell A as an ideal switch with a pull-down
resistance equal to R pd and models the metal interconnect using resistors and
capacitors for each segment of the interconnect.
The Elmore constant for node 4 (labeled V 4 ) in the network shown in Figure 17.3 (c) is
tD4 = ΣR k 4 C k (17.1)
k=1
= R 14 C 1 + R 24 C 2 + R 34 C 3 + R 44 C 4 ,
where, R 14 R pd + R 1 (resistance to V0 shared by
= (17.2)
node 1 and 4)
R 24 = R pd + R 1
R 34 = R pd + R 1 + R 3
R 44 = R pd + R 1 + R 3 + R 4
In Eq. 17.2 notice that R 24 = R pd + R 1 (and not R pd + R 1 + R 2 ) because
R 1 is the resistance to V0 (ground) shared by node 2 and node 4.
Suppose we have the following parameters (from the generic 0.5 m m CMOS
process, G5) for the layout shown in Figure 17.3 (b):
• m2 resistance is 50 m ohm /square.
• m2 capacitance (for a minimum-width line) is 0.2 pFmm –1 .
• 4X inverter delay is 0.02 ns + 0.5 C L ns ( C L is in picofarads).
• Delay is measured using 0.35/0.65 output trip points.
• m2 minimum width is 3 lamda = 0.9 m m.
• 1X inverter input capacitance is 0.02 pF (a standard load).
First we need to find the pull-down resistance, R pd , of the 4X inverter.
If we model the gate with a linear pull-down resistor, R pd , driving a load C L ,
The output waveform is exp – t /( C L R pd ) (normalized to 1V).
The output reaches 63 percent of its final value when t = C L R pd , because
exp (–1) = 0.63. Then,because the delay is measured with a 0.65 trip point
Thus,
R pd = 500 ohm .
• R1= R2 = 6ohm
• R3=56 ohm
• R4=112ohm
• C1=0.02 pF
• C2 =0.04 pF
• C3=0.2 pF
• C4=0.42 pF
Now we can calculate the path resistance, Rki, values (notice that Rki = Rki):
R14 = 500 W + 6 W =506 W
R24 = 500 W + 6 W =506 W
R34 =500 W + 6 W + 56 W =562 W
R44 =500 W + 6 W + 56 W + 112 W =674 W (17.5)
Finally, we can calculate Elmore’s constants for node 4 and node 2 as follows :
tD4 = R 14 C 1 + R 24 C 2 + R 34 C 3 + R 44 C 4 (17.6)
= (506)(0.02) + (506)(0.04)
+ (562)(0.2) + (674)(0.42)
= 425 ps .
t D2 = R 12 C 1 + R 22 C 2 + R 32 C 3 + R 42 C 4 (17.7)
= ( R pd + R 1 )( C 2 + C 3 + C 4 )
+ ( R pd + R 1 + R 2 ) C 2
= (500 + 6 + 6)(0.04)
+ (500 + 6)(0.02 + 0.2 + 0.2)
= 344 ps .
and t D4 – t D2 = (425 – 344) = 81 ps.
A lumped-delay model neglects the effects of interconnect resistance and
simply sums all the node capacitances (the lumped capacitance ) as follows:
t D = R pd ( C 1 + C 2 + C 3 + C 4 ) (17.8)
= (500) (0.02 + 0.04 + 0.2 + 0.42)
= 340 ps .
Measurement of Interconnect Delay (contd.,)
• Even using the Elmore constant we still made the following assumptions in
estimating the path delays:
• A step-function waveform drives the net.
• The delay is measured from when the gate input changes.
• The delay is equal to the time constant of an exponential waveform
that approximates the actual output waveform.
• The interconnect is modeled by discrete resistance and
capacitance elements.
• The global router could use more sophisticated estimates that remove some
of these assumptions, but there is a limit to the accuracy with which delay
can be estimated during global routing
• When the global router attempts to minimize interconnect delay, there is an
important difference between a path and a net.
Global Routing Methods
• Global routing cannot use the interconnect-length approximations, such as
the half-perimeter measure
•
• However, many of the methods used in global routing are still based on the
solutions to the tree on a graph problem.
• sequential routing :
One approach to global routing takes each net in turn and
calculates the shortest path using tree on graph algorithms—with the added
restriction of using the available channels. This process is known as
sequential routing.
As a sequential routing algorithm proceeds, some channels will become more
congested since they hold more interconnects than others. In the case of
FPGAs and channeled gate arrays, the channels have a fixed channel capacity
and can only hold a certain number of interconnects.
Global Routing Methods (contd.,)
• There are two different ways that a global router normally handles this problem.
[Link] independent Routing
[Link] dependent Routing
• Using order-independent routing , a global router proceeds by routing each net,
ignoring how crowded the channels are. Whether a particular net is processed first or
last does not matter, the channel assignment will be the same.
•
• Disadvantage :In order-independent routing, after all the interconnects are assigned
to channels, the global router returns to those channels that are the most crowded
and reassigns some interconnects to other, less crowded, channels.
• order dependent :A global router can consider the number of interconnects already
placed in various channels as it proceeds. In this case the global routing is order
dependent —the routing is still sequential, but now the order of processing the nets
will affect the results.
• Iterative improvement or simulated annealing may be applied to the solutions found
from both order-dependent and order-independent algorithms.
Global Routing Methods (contd.,)
• Hierarchical routing handles all nets at a particular level at once.
• Rather than handling all of the nets on the chip at the same time, the global-
routing problem is made more tractable by dividing the chip area into levels
of hierarchy.
• By considering only one level of hierarchy at a time the size of the problem
is reduced at each level.
• There are two ways to traverse the levels of hierarchy.
• top-down approach :- Starting at the whole chip, or highest level, and
proceeding down to the logic cells is the.
• The bottom-up approach starts at the lowest level of hierarchy and globally
routes the smallest areas first.
Global Routing Between Blocks
FIGURE 17.4 Global routing for a cell-based ASIC formulated as a graph
problem. (a) A cell-based ASIC with numbered channels. (b) The channels form
the edges of a graph. (c) The channel-intersection graph. Each channel
corresponds to an edge on a graph whose weight corresponds to the channel
length.
Global Routing Between Blocks
( contd.,)
FIGURE 17.5 Finding paths in global routing. (a) A cell-based ASIC showing a single
net with a fanout of four (five terminals). We have to order the numbered channels to
complete the interconnect path for terminals A1 through F1. (b) The terminals are
projected to the center of the nearest channel, forming a graph. A minimum-length tree
for the net that uses the channels and takes into account the channel capacities. (c) The
minimum-length tree does not necessarily correspond to minimum delay. If we wish to
minimize the delay from terminal A1 to D1, a different tree might be better.
Global Routing Between Blocks
( contd.,)
• Global routing is very similar for cell-based ASICs and gate arrays, but there is a very
important difference between the types of channels in these ASICs.
• The size of the channels in sea-of-gates arrays, channelless gate arrays, and cell-
based ASICs can be varied to make sure there is enough space to complete the
wiring.
• In channeled gate-arrays and FPGAs the size, number, and location of channels are
fixed.
• The good news is that the global router can allocate as many interconnects to each
channel as it likes, since that space is committed anyway.
• The bad news is that there is a maximum number of interconnects that each channel
can hold.
• If the global router needs more room, even in just one channel on the whole chip, the
designer has to repeat the placement-and-routing steps and try again (or use a bigger
chip).
Global Routing Inside Flexible Blocks
FIGURE 17.6 Gate-array global routing. (a) A small gate array. (b) An enlarged view of the routing.
The top channel uses three rows of gate-array base cells; the other channels use only one. (c) A
further enlarged view showing how the routing in the channels connects to the logic cells. (d) One of
the logic cells, an inverter. (e) There are seven horizontal wiring tracks available in one row of gate-
array base cells—the channel capacity is thus 7
Global Routing Inside Flexible Blocks (contd.,)
FIGURE 17.7 The gate-array inverter from Figure 17.6 d. (a) An oxide-
isolated gate-array base cell, showing the diffusion and polysilicon
layers. (b) The metal and contact layers for the inverter in a 2LM (two-
level metal) process. (c) The router’s view of the cell in a 3LM process.
Global Routing Inside Flexible Blocks
FIGURE 17.8 Global routing a gate array. (a) A single global-routing cell (GRC or routing bin) containing 2-by-4
gate-array base cells. For this choice of routing bin the maximum horizontal track capacity is 14, the maximum
vertical track capacity is 12. The routing bin labeled C3 contains three logic cells, two of which have feedthroughs
marked 'f'. This results in the edge capacities shown. (b) A view of the top left-hand corner of the gate array
showing 28 routing bins. The global router uses the edge capacities to find a sequence of routing bins to connect
the nets.
Timing-Driven Methods
• As in timing-driven placement, there are two main approaches to timing-driven routing:
– net-based and path-based.
• Path-based methods are more sophisticated.
For example, if there is a critical path from logic cell A to B to C, the global
router may increase the delay due to the interconnect between logic cells A and B if
it can reduce the delay between logic cells B and C.
• Placement and global routing tools may or may not use the same algorithm to
estimate net delay. If these tools are from different companies, the algorithms are
probably different.
• The algorithms must be compatible, however. There is no use performing placement
to minimize predicted delay if the global router uses completely different
measurement methods.
• Companies that produce floorplanning and placement tools make sure that the
output is compatible with different routing tools—often to the extent of using
different algorithms to target different routers.
Back-annotation
• After global routing is complete it is possible to accurately predict what the length
of each interconnect in every net will be after detailed routing, probably to within 5
percent.
• The global router can give us not just an estimate of the total net length (which
was all we knew at the placement stage), but the resistance and capacitance of
each path in each net. This RC information is used to calculate net delays.
• We can back-annotate this net delay information to the synthesis tool for in-
place optimization or to a timing verifier to make sure there are no timing surprises.
• Differences in timing predictions at this point arise due to the different ways in
which the placement algorithms estimate the paths and the way the global
router actually builds the paths.
Detailed Routing
Goal:
• The goal of detailed routing is to complete all the connections between logic
cells.
Objectives:
• The most common objective is to minimize one or more of the following:
– The total interconnect length and area
– The number of layer changes that the connections have to make
– The delay of critical paths
• Minimizing the number of layer changes corresponds to minimizing the
number of vias that add parasitic resistance and capacitance to a
connection.
Measurement of Channel Density
Definition of Local and Global channel density
• 0 unused terminal. 3,4,3 net number or column position
• Number of nets that cross a line drawn vertically anywhere in a channel is called
Local density. Channel density is a important measure in routing.
• Channel Capcitity finds the minimum height of the channel.
• Maximum local density of channel is Global density
• Channel density is less than or equal to Channel capacity.
• ALGORITHMS
Left-edge algorithm
a. Sorted list of segments
b. Assignments to tracks
c. Completed channel route
LEA is a basis for several routing algorithms. LEA applies to two layer
channel routing . One layer – trunks . Other – branches.
m1 may be used in HORIZONTAL. m2 – vertical direction.
Vertical constraint : two terminals are in the same column in a channel create
a vertical constraint.
Constraints and Routing Graphs
Dog-Leg router
• A dogleg router removes the restriction that each net can use only one
track or trunk.
Area Routing Algorithm- Lee-Maze algorithm
• The algorithm finds a path from source (X) to target (Y) by emitting a wave from both the
source and the target at the same time. Successive outward moves are marked in each bin.
• Once the target is reached, the path is found by backtracking (if there is a choice of bins
with equal labeled values, we choose the bin that avoids changing direction). (The original
form of the Lee algorithm uses a single wave.)
1.
Hightower Area routing algorithm(Line search )
1. Extend lines from both the source and target toward each other.
2. When an extended line, known as an escape line , meets an obstacle,
choose a point on the escape line from which to project another escape line at
right angles to the old one. This point is the escape point .
3. Place an escape point on the line so that the next escape line just misses the
edge of the obstacle. Escape lines emanating from the source and target
intersect to form the path.