ROUTING: BASICS

• 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.
• Routing involves making physical interconnections between different components of a
design.
• It must honor connectivity as specified in the given netlist.
• It is a complicated and time-consuming task.
• Routing must meet tight constraints, including routing resources, design rules, timing, and
signal integrity constraints.
• Routing is usually split into global routing followed by detailed routing.
ROUTING : BASIC IDEA
Stages of Routing

• Global Routing
• Global routing creates the plan of routing for each net in terms of routing regions.
• The actual layout of nets is not created at this stage.
• Detailed Routing
• Detailed routing decides the actual layout of each net within the pre-assigned routing regions.
• Post-Routing Optimizations
• Post-routing optimizations involve localized changes to fix issues in the design.
GLOBAL ROUTING & DETAILED ROUTING
Decoder Chip after Placement & Routing
 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: inside the flexible blocks and between blocks.
 GLOBAL ROUTING : GOALS AND OBJECTIVES

• The input to the global router is a 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.
Goal:
• The goal of global routing is to provide complete instructions to the detailed router on
where to route every net.
Objectives:
• The objectives of global routing are one or more of the following:
• Minimize the total interconnect length.
• Maximize the probability that the detailed router can complete the routing.
• Minimize the critical path delay.
 GLOBAL ROUTING : GOALS AND OBJECTIVES
• In both floorplanning and placement, with minimum interconnect length as an objective,
it is necessary to find the shortest total path length connecting a set of terminals.
• This path is the MRST (Minimum Rectilinear Steiner Tree), which is hard to find.
• Often the global router needs to find a path that minimizes the delay between two
terminals.
• This is not necessarily the same as finding the shortest total path length for a set of
terminals.
 GLOBAL ROUTING METHODS

• Global routing cannot use the interconnect-length approximations, such as the half-
perimeter measure, that were used in placement.
• What is needed now is the actual path and not an approximation to the path length.
• 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

• There are two different ways that a global router normally handles this problem.
Order-independent Routing:
• In the 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.
• 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 Routing:
• Alternatively, 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.
 GLOBAL ROUTING METHODS
In order-dependent routing, 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.

This is implemented in the same way as for system partitioning and placement: A
constructed solution is successively changed, one interconnect path at a time, in a
series of random moves.
GLOBAL ROUTING METHODS

• In contrast to sequential global-routing methods, which handle nets one at a time, 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 top-down
approach.

Bottom-up approach:
• The bottom-up approach starts at the lowest level of hierarchy and globally routes the smallest
areas first.
GLOBAL ROUTING BETWEEN BLOCKS
GLOBAL ROUTING BETWEEN BLOCKS

•Figure 17.4 illustrates the global-routing problem for a cell-based ASIC.

•Each edge in the channel-intersection graph in Figure 17.4(c) represents a channel.

•The global router is restricted to using these channels.

•The weight of each edge in the graph corresponds to the length of the channel.

•The global router plans a path for each interconnect using this graph.
 GLOBAL ROUTING BETWEEN BLOCKS

• Figure 17.5 shows an example of global routing for a net with five terminals, labeled A1
through F1, for the cell-based ASIC shown in Figure 17.4.
• If a designer wishes to use minimum total interconnect path length as an objective, the
global router finds the minimum-length tree shown in Figure 17.5(b).
• This tree determines the channels the interconnects will use.
• For example, the shortest connection from A1 to B1 uses channels 2, 1, and 5 (in that
order).
• This is the information the global router passes to the detailed router.
• Figure 17.5(c) shows that minimizing the total path length may not correspond to
minimizing the path delay between two points.
GLOBAL ROUTING BETWEEN BLOCKS
GLOBAL ROUTING BETWEEN BLOCKS
•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 advantage is that the global router can allocate as many interconnects to
each channel as it likes, since that space is committed anyway.
•The disadvantage 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).
 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 also 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.
TERMINOLOGY
TERMINOLOGIES
HORIZONTAL CONSTRAINED GRAPH
HORIZONTAL CONSTRAINED GRAPH
HORIZONTAL CONSTRAINED GRAPH
VERTICAL CONSTRAINED GRAPH
VERTICAL CONSTRAINED GRAPH
VERTICAL CONSTRAINED GRAPH
LEFT-EDGE-ALGORITHM
LEFT-EDGE-ALGORITHM
ROUTING RESULT
DOGLEG ROUTING
DOGLEG ROUTING
DOGLEG ROUTING
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
AREA ROUTING (LEE MAZE-RUNNING ALGORITHM)
 Lee maze-running algorithm

• Figure 17.18 illustrates the Lee maze-running algorithm.

• The goal is to find a path from X to Y, i.e., from the start (or source) to the finish (or target), while
avoiding any obstacles.
• The algorithm is often called wave propagation because it sends out waves, which spread out like
those created by dropping a stone into a pond.
 Line-Search (probing) algorithms

• Line-probing algorithms search for routes directly based on the geometry.

• Unlike maze-routers, line-probing does not necessarily need a grid. Hence they
can be more memory efficient and faster.
• Example algorithms in the literature are:
• Hightower's algorithm
• Mikami-Tabuchi algorithm
• The above algorithms do not guarantee finding the shortest path between two
terminals.
Hightower Routing Algorithm
Hightower Routing Algorithm
• Algorithms that use lines rather than waves to search for connections are more
efficient than those based on the Lee algorithm. The Hightower algorithm, also
known as a line-search or line-probe algorithm, follows these steps:
• Lines are extended from both the source and the target toward each other.

• When an extended line, called an escape line, meets an obstacle, a point is

chosen on that line from which another escape line is projected at a right angle
to the original one. This chosen point is called the escape point.

• An escape point is placed on the line so that the next escape line just misses
the edge of the obstacle. Escape lines that emanate from the source and the
target eventually intersect to form the connection path.
Multi-Level Routing
Multi-Layer Routing
Over-The-Cell (OTC) Routing
Over-The-Cell (OTC) Routing

With three or more levels of metal routing, it is possible to reduce the channel height in a row-based
ASIC to zero.
All of the interconnect is then completed over the cell.
If all of the channels are eliminated, the core area (logic cells plus routing) is determined solely by
the logic-cell area.
Timing-Driven Detailed Routing
• In detailed routing, the global router has already determined the path that
the interconnect will follow.
• At this stage, there is little that can be done to improve timing, except for
reducing the number of vias, adjusting the interconnect width to optimize
delay, and minimizing overlap capacitance.
• Although the improvements achieved at this stage are relatively small, they
can still be significant for very long branching nets.
• For high-frequency clock nets, it is important to shape the interconnect to
match impedances at branching points.
 FINAL ROUTING STEPS
• If the algorithms used to estimate congestion in the floorplanning tool accurately
reflected the algorithms used by the global router and the detailed router, then routing
completion would be guaranteed.

• However, in practice, the detailed router often cannot completely route all the nets.

• These problematic nets are referred to as unroutes.

• Routers handle unrouted nets in two ways.

• The first method leaves the problematic nets unconnected.

• The second method completes all interconnections but may result in some design-rule
violations, such as shorting one net to another.

• Some tools flag these violations as warnings, although they can be serious errors.
 FINAL ROUTING STEPS
When there are many unrouted nets, the designer must identify the cause and return
to the floorplanner to make adjustments.

This may include changing channel sizes (for a cell-based ASIC) or the base-array
size (for a gate array).

The designer might also return to the global router to modify bin sizes or adjust the
routing algorithms. In severe cases, it may be necessary to change the floorplan
entirely.

If only a few difficult nets remain unrouted, some tools allow the designer to
perform manual edits using a rip-up and reroute router.

Sometimes this step is done automatically by the detailed router as part of the final
routing phase.
FINAL ROUTING STEPS
• This capability also permits Engineering change orders (ECO) correspond to
the little yellow wires on a PCB.
• One of the last steps in routing is via removal, and the detailed router looks to
see if it can eliminate any vias (which can contribute a significant amount to
the interconnect resistance) by changing layers or making other modifications
to the completed routing.
• Routing compaction can then be performed as the final step.
SPECIAL ROUTING

• The routing of nets that require special attention, such as clock and
power nets, is normally done before the detailed routing of signal
nets.
• The architecture and structure of these nets are defined as part of
floorplanning.
• The sizing and topology of these nets are finalized during the routing
step.
CLOCK ROUTING
•Gate arrays normally use a clock spine (a regular grid), which eliminates the need
for special routing.

•The clock distribution grid is designed at the same time as the gate-array base to
ensure minimum clock skew and minimum clock latency, given power dissipation
and clock buffer area limitations.

•Cell-based ASICs may use either a clock spine, a clock tree, or a hybrid approach.

•Figure 17.21 shows how a clock router may minimize clock skew in a clock spine
by making the path lengths, and thus net delays, to every leaf node equal, and by
using jogs in the interconnect paths if necessary.

•More sophisticated clock routers perform clock-tree synthesis (automatically

choosing the depth and structure of the clock tree) and clock-buffer insertion
(equalizing the delay to the leaf nodes by balancing interconnect delays and buffer
delays).
CLOCK ROUTING
CLOCK ROUTING
The clock tree may contain multiply-driven nodes (more than one active element driving
a net).

The net delay models that we have used break down in this case, and we may have to
extract the clock network and perform circuit simulation, followed by back-annotation of
the clock delays to the netlist , and the bus currents to the clock router.

The sizes of the clock buses depend on the current they must carry. The limits are set by
reliability issues.

Another factor contributing to unpredictable clock skew is changes in clock-buffer

delays with variations in power-supply voltage due to data-dependent activity.
 POWER ROUTING
• Each of the power buses has to be sized according to the current it will carry.
• Too much current in a power bus can lead to a failure through a mechanism known as
electromigration [Young and Christou, 1994].
• The required power-bus widths can be estimated automatically from library information, from a
separate power simulation tool, or by entering the power-bus widths to the routing software by
hand.
• Many routers use a default power-bus width so that it is quite easy to complete routing of an ASIC
without even knowing about this problem.
• For a direct current (DC), the mean time to failure (MTTF) due to electromigration is
experimentally found to obey the following equation:
• MTTF = A × J⁻² × exp(E / kT), (17.9)
• where:
• J is the current density,
• E is approximately 0.5 eV,
• k is Boltzmann's constant (8.62 × 10⁻⁵ eV/K), and
• T is the absolute temperature in kelvins.
POWER ROUTING

•Gate arrays normally use a regular power grid as part of the gate-array base.

•The gate-array logic cells contain two fixed-width power buses inside the cell,
running horizontally on m1.

•The horizontal m1 power buses are then strapped in a vertical direction by m2

buses, which run vertically across the chip.

•The resistance of the power grid is extracted and simulated with SPICE during
the base-array design.

•This is done to model the effects of IR drops under worst-case conditions.

 POWER ROUTING

•Standard cells are constructed in a similar fashion to gate-array cells, with power
buses running horizontally in m1 at the top and bottom of each cell.
•A row of standard cells uses end-cap cells that connect to the VDD and VSS power
buses placed by the power router.
•Power routing of cell-based ASICs may include the option to include vertical m2
straps at specified intervals.
•Alternatively, the number of standard cells that can be placed in a row may be limited
during placement.
•Power buses inside the logic cells are still normally run on m1.
•Using HVH routing, it would be possible to run the power buses on m3 and drop vias
all the way down to m1 when power is required in the cells.
•The problem with this approach is that it creates pillars of blockage across all three
layers.
 CIRCUIT EXTRACTION AND DRC
•After detailed routing is complete, the exact length and position of each
interconnect for every net is known.
•Now the parasitic capacitance and resistance associated with each interconnect,
via, and contact can be calculated.
•This data is generated by a circuit-extraction tool in one of the formats described
next.
•It is important to extract the parasitic values that will be on the silicon wafer.
•The mask data that are drawn in the logic cells are not necessarily the same as the
final silicon dimensions.
•Normally mask dimensions are altered from drawn values to allow for process bias
or other effects that occur during the transfer of the pattern from mask to silicon.
 SPF,RSPF AND DSPF FORMATS
• The standard parasitic format (SPF) (developed by Cadence ) describes interconnect delay
and loading due to parasitic resistance and capacitance.
• There are three different forms of SPF: two of them (regular SPF and reduced SPF) contain
the same information, but in different formats, and model the behavior of interconnect.
• The third form of SPF (detailed SPF) describes the actual parasitic resistance and
capacitance components of a net.
• The load at the output of gate A is represented by one of three models: lumped-C, lumped-
RC, or PI segment.
• The pin-to-pin delays are modeled by RC delays.
• You can represent the pin-to-pin interconnect delay by an ideal voltage source, V(A_1) in
this case, driving an RC network attached to each input pin.
• The actual pin-to-pin delays may not be calculated this way, however.
SPF,RSPF AND DSPF FORMATS
 DESIGN CHECKS

• ASIC designers perform two major checks before fabrication.

• The first check is a design-rule check (DRC) to ensure that nothing has gone
wrong in the process of assembling the logic cells and routing.
• The DRC may be performed at two levels.
• The first level of DRC is a phantom-level DRC, which checks for shorts, spacing
violations, or other design-rule problems between logic cells. This is principally a
check of the detailed router.
• If we have access to the real library-cell layouts (sometimes called hard layout),
we can instantiate the phantom cells and perform a second-level DRC at the
transistor level. This is principally a check of the correctness of the library cells.
DESIGN CHECKS
• The other check is a layout versus schematic (LVS) check to ensure that what is
about to be committed to silicon is what is really wanted. An electrical schematic
is extracted from the physical layout and compared to the netlist.
• This closes a loop between the logical and physical design processes and ensures
that both are the same.