17.

2 Detailed Routing
The global routing step determines the channels to be used for each interconnect.
Using this information the detailed router decides the exact location and layers
for each interconnect. Figure 17.9 (a) shows typical metal rules. These rules
determine the m1 routing pitch ( track pitch , track spacing , or just pitch ). We
can set the m1 pitch to one of three values:
1. via-to-via ( VTV ) pitch (or spacing),
2. via-to-line ( VTL or line-to-via ) pitch, or
3. line-to-line ( LTL ) pitch.
The same choices apply to the m2 and other metal layers if they are present.
Via-to-via spacing allows the router to place vias adjacent to each other.
Via-to-line spacing is hard to use in practice because it restricts the router to
nonadjacent vias. Using line-to-line spacing prevents the router from placing a
via at all without using jogs and is rarely used. Via-to-via spacing is the easiest
for a router to use and the most common. Using either via-to-line or via-to-via
spacing means that the routing pitch is larger than the minimum metal pitch.
Sometimes people draw a distinction between a cut and a via when they talk
about large connections such as shown in Figure 17.10 (a). We split or stitch a
large via into identically sized cuts (sometimes called a waffle via ). Because of
the profile of the metal in a contact and the way current flows into a contact,
often the total resistance of several small cuts is less than that of one large cut.
Using identically sized cuts also means the processing conditions during contact
etching, which may vary with the area and perimeter of a contact, are the same
for every cut on the chip.
In a stacked via the contact cuts all overlap in a layout plot and it is impossible to
tell just how many vias on which layers are present. Figure 17.10 (bf) show an
alternative way to draw contacts and vias. Though this is not a standard, using the
diagonal box convention makes it possible to recognize stacked vias and contacts
on a layout (in any orientation). I shall use these conventions when it is
necessary.
FIGURE 17.9 The metal routing pitch. (a) An example of l -based metal design
rules for m1 and via1 (m1/m2 via). (b) Via-to-via pitch for adjacent vias.
(c) Via-to-line (or line-to-via) pitch for nonadjacent vias. (d) Line-to-line pitch
with no vias.

FIGURE 17.10 (a) A large m1 to m2 via. The black squares represent the holes
(or cuts) that are etched in the insulating material between the m1 and 2 layers.
(b) A m1 to m2 via (a via1). (c) A contact from m1 to diffusion or polysilicon (a
contact). (d) A via1 placed over (or stacked over) a contact. (e) A m2 to m3 via
(a via2) (f) A via2 stacked over a via1 stacked over a contact. Notice that the
black square in parts bc do not represent the actual location of the cuts. The
black squares are offset so you can recognize stacked vias and contacts.

In a two-level metal CMOS ASIC technology we complete the wiring using the
two different metal layers for the horizontal and vertical directions, one layer for
each direction. This is Manhattan routing , because the results look similar to the
rectangular northsouth and eastwest layout of streets in New York City. Thus,
for example, if terminals are on the m2 layer, then we route the horizontal
branches in a channel using m2 and the vertical trunks using m1. Figure 17.11
shows that, although we may choose a preferred direction for each metal layer
(for example, m1 for horizontal routing and m2 for vertical routing), this may
lead to problems in cases that have both horizontal and vertical channels. In these
cases we define a preferred metal layer in the direction of the channel spine. In
Figure 17.11 , because the logic cell connectors are on m2, any vertical channel
has to use vias at every logic cell location. By changing the orientation of the
metal directions in vertical channels, we can avoid this, and instead we only need
to place vias at the intersection of horizontal and vertical channels.

FIGURE 17.11 An expanded view of part of a cell-based ASIC. (a) Both

channel 4 and channel 5 use m1 in the horizontal direction and m2 in the vertical
direction. If the logic cell connectors are on m2 this requires vias to be placed at
every logic cell connector in channel 4. (b) Channel 4 and 5 are routed with m1
along the direction of the channel spine (the long direction of the channel). Now
vias are required only for nets 1 and 2, at the intersection of the channels.

Figure 17.12 shows an imaginary logic cell with connectors. Double-entry logic
cells intended for two-level metal routing have connectors at the top and bottom
of the logic cell, usually in m2. Logic cells intended for processes with three or
more levels of metal have connectors in the center of the cell, again usually on
m2. Logic cells may use both m1 and m2 internally, but the use of m2 is usually
minimized. The router normally uses a simplified view of the logic cell called a
phantom . The phantom contains only the logic cell information that the router
needs: the connector locations, types, and names; the abutment and bounding
boxes; enough layer information to be able to place cells without violating design
rules; and a blockage map the locations of any metal inside the cell that blocks
routing.
FIGURE 17.12 The different types of connections that can be made to a cell.
This cell has connectors at the top and bottom of the cell (normal for cells
intended for use with a two-level metal process) and internal connectors (normal
for logic cells intended for use with a three-level metal process). The
interconnect and connections are drawn to scale.

Figure 17.13 illustrates some terms used in the detailed routing of a channel. The
channel spine in Figure 17.13 is horizontal with terminals at the top and the
bottom, but a channel can also be vertical. In either case terminals are spaced
along the longest edges of the channel at given, fixed locations. Terminals are
usually located on a grid defined by the routing pitch on that layer (we say
terminals are either on-grid or off-grid ). We make connections between
terminals using interconnects that consist of one or more trunks running parallel
to the length of the channel and branches that connect the trunk to the terminals.
If more than one trunk is used, the trunks are connected by doglegs . Connections
exit the channel at pseudoterminals .
FIGURE 17.13 Terms used in channel routing. (a) A channel with four
horizontal tracks. (b) An expanded view of the left-hand portion of the channel
showing (approximately to scale) how the m1 and m2 layers connect to the logic
cells on either side of the channel. (c) The construction of a via1 (m1/m2 via).

The trunk and branch connections run in tracks (equispaced, like railway tracks).
If the trunk connections use m1, the horizontal track spacing (usually just called
the track spacing for channel routing) is equal to the m1 routing pitch. The
maximum number of interconnects we need in a channel multiplied by the
horizontal track spacing gives the minimum height of a channel (see
Section 17.2.2 on how to determine the maximum number of interconnects
needed). Each terminal occupies a column . If the branches use m2, the column
spacing (or vertical track spacing ) is equal to the m2 routing pitch.

17.2.1 Goals and Objectives

The goal of detailed routing is to complete all the connections between logic
cells. 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.
In some cases the detailed router may not be able to complete the routing in the
area provided. In the case of a cell-based ASIC or sea-of-gates array, it is
possible to increase the channel size and try the routing steps again. A channeled
gate array or FPGA has fixed routing resources and in these cases we must start
all over again with floorplanning and placement, or use a larger chip.

17.2.2 Measurement of Channel Density

We can describe a channel-routing problem by specifying two lists of nets: one
for the top edge of the channel and one for the bottom edge. The position of the
net number in the list gives the column position. The net number zero represents
a vacant or unused terminal. Figure 17.14 shows a channel with the numbered
terminals to be connected along the top and the bottom of the channel.
We call the number of nets that cross a line drawn vertically anywhere in a
channel the local density . We call the maximum local density of the channel the
global density or sometimes just channel density . Figure 17.14 has a channel
density of 4. Channel density is an important measure in routingit tells a router
the absolute fewest number of horizontal interconnects that it needs at the point
where the local density is highest. In two-level routing (all the horizontal
interconnects run on one routing layer) the channel density determines the
minimum height of the channel. The channel capacity is the maximum number of
interconnects that a channel can hold. If the channel density is greater than the
channel capacity, that channel definitely cannot be routed (to learn how channel
density is calculated, see Section 17.2.5 ).

FIGURE 17.14 The definitions of local channel density and global channel
density. Lines represent the m1 and m2 interconnect in the channel to simplify
the drawing.

17.2.3 Algorithms
We start discussion of routing methods by simplifying the general
channel-routing problem. The restricted channel-routing problem limits each net
in a channel to use only one horizontal segment. In other words the channel
router uses only one trunk for each net. This restriction has the effect of
minimizing the number of connections between the routing layers. This is
equivalent to minimizing the number of vias used by the channel router in a
two-layer metal technology. Minimizing the number of vias is an important
objective in routing a channel, but it is not always practical. Sometimes
constraints will force a channel router to use jogs or other methods to complete
the routing (see Section 17.2.5 ). Next, though, we shall study an algorithm that
solves the restricted channel-routing problem.

17.2.4 Left-Edge Algorithm

The left-edge algorithm ( LEA ) is the basis for several routing algorithms [
Hashimoto and Stevens, 1971]. The LEA applies to two-layer channel routing,
using one layer for the trunks and the other layer for the branches. For example,
m1 may be used in the horizontal direction and m2 in the vertical direction. The
LEA proceeds as follows:
1. Sort the nets according to the leftmost edges of the nets horizontal
segment.
2. Assign the first net on the list to the first free track.
3. Assign the next net on the list, which will fit, to the track.
4. Repeat this process from step 3 until no more nets will fit in the current
track.
5. Repeat steps 24 until all nets have been assigned to tracks.
6. Connect the net segments to the top and bottom of the channel.
 FIGURE 17.15 Left-edge algorithm. (a) Sorted list of segments.
(b) Assignment to tracks. (c) Completed channel route (with m1 and m2
interconnect represented by lines).

Figure 17.15 illustrates the LEA. The algorithm works as long as none of the
branches touchwhich may occur if there are terminals in the same column
belonging to different nets. In this situation we have to make sure that the trunk
that connects to the top of the channel is placed above the lower trunk. Otherwise
two branches will overlap and short the nets together. In the next section we shall
examine this situation more closely.

17.2.5 Constraints and Routing Graphs

Two terminals that are in the same column in a channel create a vertical
constraint . We say that the terminal at the top of the column imposes a vertical
constraint on the lower terminal. We can draw a graph showing the vertical
constraints imposed by terminals. The nodes in a vertical-constraint graph
represent terminals. A vertical constraint between two terminals is shown by an
edge of the graph connecting the two terminals. A graph that contains
information in the direction of an edge is a directed graph . The arrow on the
graph edge shows the direction of the constraintpointing to the lower terminal,
which is constrained. Figure 17.16 (a) shows an example of a channel, and
Figure 17.16 (b) shows its vertical constraint graph.
FIGURE 17.16 Routing graphs. (a) Channel with a global density of 4. (b) The
vertical constraint graph. If two nets occupy the same column, the net at the top
of the channel imposes a vertical constraint on the net at the bottom. For
example, net 2 imposes a vertical constraint on net 4. Thus the interconnect for
net 4 must use a track above net 2. (c) Horizontal-constraint graph. If the
segments of two nets overlap, they are connected in the horizontal-constraint
graph. This graph determines the global channel density.

We can also define a horizontal constraint and a corresponding

horizontal-constraint graph . If the trunk for net 1 overlaps the trunk of net 2, then
we say there is a horizontal constraint between net 1 and net 2. Unlike a vertical
constraint, a horizontal constraint has no direction. Figure 17.16 (c) shows an
example of a horizontal constraint graph and shows a group of 4 terminals
(numbered 3, 5, 6, and 7) that must all overlap. Since this is the largest such
group, the global channel density is 4.
If there are no vertical constraints at all in a channel, we can guarantee that the
LEA will find the minimum number of routing tracks. The addition of vertical
constraints transforms the restricted routing problem into an NP-complete
problem. There is also an arrangement of vertical constraints that none of the
algorithms based on the LEA can cope with. In Figure 17.17 (a) net 1 is above
net 2 in the first column of the channel. Thus net 1 imposes a vertical constraint
on net 2. Net 2 is above net 1 in the last column of the channel. Then net 2 also
imposes a vertical constraint on net 1. It is impossible to route this arrangement
using two routing layers with the restriction of using only one trunk for each net.
If we construct the vertical-constraint graph for this situation, shown in
Figure 17.17 (b), there is a loop or cycle between nets 1 and 2. If there is any
such vertical-constraint cycle (or cyclic constraint ) between two or more nets,
the LEA will fail. A dogleg router removes the restriction that each net can use
only one track or trunk. Figure 17.17 (c) shows how adding a dogleg permits a
channel with a cyclic constraint to be routed.

FIGURE 17.17 The

addition of a dogleg, an
extra trunk, in the wiring
of a net can resolve cyclic
vertical constraints.

The channel-routing algorithms we have described so far do not allow

interconnects on one layer to run on top of other interconnects on a different
layer. These algorithms allow interconnects to cross at right angles to each other
on different layers, but not to overlap . When we remove the restriction that
horizontal and vertical routing must use different layers, the density of a channel
is no longer the lower bound for the number of tracks required. For two routing
layers the ultimate lower bound becomes half of the channel density. The
practical reasoning for restricting overlap is the parasitic overlap capacitance
between signal interconnects. As the dimensions of the metal interconnect are
reduced, the capacitance between adjacent interconnects on the same layer (
coupling capacitance ) is comparable to the capacitance of interconnects that
overlap on different layers ( overlap capacitance ). Thus, allowing a short overlap
between interconnects on different layers may not be as bad as allowing two
interconnects to run adjacent to each other for a long distance on the same layer.
Some routers allow you to specify that two interconnects must not run adjacent to
each other for more than a specified length.
The channel height is fixed for channeled gate arrays; it is variable in discrete
steps for channelless gate arrays; it is continuously variable for cell-based ASICs.
However, for all these types of ASICs, the channel wiring is fully customized and
so may be compacted or compressed after a channel router has completed the
interconnect. The use of channel-routing compaction for a two-layer channel can
reduce the channel height by 15 percent to 20 percent [ Cheng et al., 1992].
Modern channel routers are capable of routing a channel at or near the theoretical
minimum density. We can thus consider channel routing a solved problem. Most
of the difficulty in detailed routing now comes from the need to route more than
two layers and to route arbitrary shaped regions. These problems are best handled
by area routers.

17.2.6 Area-Routing Algorithms

There are many algorithms used for the detailed routing of general-shaped areas
(see the paper by Ohtsuki in [ Ohtsuki, 1986]). Many of these were originally
developed for PCB wiring. The first group we shall cover and the earliest to be
used historically are the grid-expansion or maze-running algorithms. A second
group of methods, which are more efficient, are the line-search algorithms.
FIGURE 17.18 The Lee maze-running
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.)

Figure 17.18 illustrates the Lee maze-running algorithm . The goal is to find a
path from X to Yi.e., from the start (or source) to the finish (or target)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.
Algorithms that use lines rather than waves to search for connections are more
efficient than algorithms based on the Lee algorithm. Figure 17.19 illustrates the
Hightower algorithm a line-search algorithm (or line-probe algorithm ):
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.
FIGURE 17.19 Hightower
area-routing algorithm. (a)
Escape lines are constructed
from source (X) and target (Y)
toward each other until they hit
obstacles. (b) An escape point
is found on the escape line so
that the next escape line
perpendicular to the original
misses the next obstacle. The
path is complete when escape
lines from source and target
meet.

The Hightower algorithm is faster and requires less memory than methods based
on the Lee algorithm.
17.2.7 Multilevel Routing
Using two-layer routing , if the logic cells do not contain any m2, it is possible to
complete some routing in m2 using over-the-cell (OTC) routing. Sometimes poly
is used for short connections in the channel in a two-level metal technology; this
is known as 2.5-layer routing . Using a third level of metal in three-layer routing ,
there is a choice of approaches. Reserved-layer routing restricts all the
interconnect on each layer to flow in one direction in a given routing area (for
example, in a channel, either parallel or perpendicular to the channel spine).
Unreserved-layer routing moves in both horizontal and vertical directions on a
given layer. Most routers use reserved routing. Reserved three-level metal routing
offers another choice: Either use m1 and m3 for horizontal routing (parallel to the
channel spine), with m2 for vertical routing ( HVH routing ) or use VHV routing
. Since the logic cell interconnect usually blocks most of the area on the m1 layer,
HVH routing is normally used. It is also important to consider the pitch of the
layers when routing in the same direction on two different layers. Using HVH
routing it is preferable for the m3 pitch to be a simple multiple of the m1 pitch
(ideally they are the same). Some processes have more than three levels of metal.
Sometimes the upper one or two metal layers have a coarser pitch than the lower
layers and are used in multilevel routing for power and clock lines rather than for
signal interconnect.
Figure 17.20 shows an example of three-layer channel routing. The logic cells are
64 l high, the m1 routing pitch is 8 l, and the m2 and m3 routing pitch is 16 l .
The channel in Figure 17.20 is the same as the channel using two-layer metal
shown in Figure 17.13 , but using three-level metal reduces the channel height
from 40 l ( = 5 ¥ 8 l ) to 16 l . Submicron processes try to use the same metal
pitch on all metal layers. This makes routing easier but processing more difficult.
FIGURE 17.20 Three-level channel routing. In this diagram the m2 and m3
routing pitch is set to twice the m1 routing pitch. Routing density can be
increased further if all the routing pitches can be made equala difficult process
challenge.

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. The point at which this
happens depends on not only the number of metal layers and channel density, but
also the routing resources (the blockages and feedthroughs) in the logic cell. This
the cell porosity . Designing porous cells that help to minimize routing area is an
art. For example, it is quite common to be able to produce a smaller chip using
larger logic cells if the larger cells have more routing resources.

17.2.8 Timing-Driven Detailed Routing

In detailed routing the global router has already set the path the interconnect will
follow. At this point little can be done to improve timing except to reduce the
number of vias, alter the interconnect width to optimize delay, and minimize
overlap capacitance. The gains here are relatively small, but for very long
branching nets even small gains may be important. For high-frequency clock nets
it may be important to shape and chamfer (round) the interconnect to match
impedances at branches and control reflections at corners.

17.2.9 Final Routing Steps

If the algorithms to estimate congestion in the floorplanning tool accurately
perfectly reflected the algorithms used by the global router and detailed router,
routing completion should be guaranteed. Often, however, the detailed router will
not be able to completely route all the nets. These problematical nets are known
as unroutes . Routers handle this situation in one of two ways. The first method
leaves the problematical nets unconnected. The second method completes all
interconnects anyway but with some design-rule violations (the problematical
nets may be shorted to other nets, for example). Some tools flag these problems
as a warning (in fact there can be no more serious error).
If there are many unroutes the designer needs to discover the reason and return to
the floorplanner and change channel sizes (for a cell-based ASIC) or increase the
base-array size (for a gate array). Returning to the global router and changing bin
sizes or adjusting the algorithms may also help. In drastic cases it may be
necessary to change the floorplan. If just a handful of difficult nets remain to be
routed, some tools allow the designer to perform hand edits using a rip-up and
reroute router (sometimes this is done automatically by the detailed router as a
last phase in the routing procedure anyway). This capability also permits
engineering change orders ( ECO )corresponding to the little yellow wires on a
PCB. One of the last steps in routing is via removal 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.
17.3 Special Routing
The routing of nets that require special attention, clock and power nets for
example, is normally done before detailed routing of signal nets. The architecture
and structure of these nets is performed as part of floorplanning, but the sizing
and topology of these nets is finalized as part of the routing step.

17.3.1 Clock Routing

Gate arrays normally use a clock spine (a regular grid), eliminating the need for
special routing (see Section 16.1.6, Clock Planning). The clock distribution grid
is designed at the same time as the gate-array base to ensure a minimum clock
skew and minimum clock latencygiven 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 equalusing 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).

FIGURE 17.21 Clock routing. (a) A clock network for the cell-based ASIC
from Figure 16.11. (b) Equalizing the interconnect segments between CLK and
all destinations (by including jogs if necessary) minimizes clock skew.

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 (for circuit
extraction, see Section 17.4 ) 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 to be discussed next.
Clock skew induced by hot-electron wearout was mentioned in Section 16.1.6,
Clock Planning. Another factor contributing to unpredictable clock skew is
changes in clock-buffer delays with variations in power-supply voltage due to
data-dependent activity. This activity-induced clock skew can easily be larger
than the skew achievable using a clock router. For example, there is little point in
using software capable of reducing clock skew to less than 100 ps if, due to
fluctuations in power-supply voltage when part of the chip becomes active, the
clock-network delays change by 200 ps.
The power buses supplying the buffers driving the clock spine carry direct
current ( unidirectional current or DC), but the clock spine itself carries
alternating current ( bidirectional current or AC). The difference between
electromigration failure rates due to AC and DC leads to different rules for sizing
clock buses. As we explained in Section 16.1.6, Clock Planning, the fastest way
to drive a large load in CMOS is to taper successive stages by approximately e ª
3. This is not necessarily the smallest-area or lowest-power approach, however [
Veendrick, 1984].

17.3.2 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 2 exp E / k T , (17.9)

where J is the current density; E is approximately 0.5 eV; k , Boltzmanns

constant, is 8.62 ¥ 10 5 eVK 1 ; and T is absolute temperature in kelvins.
There are a number of different approaches to model the effect of an AC
component. A typical expression is
A J 2 exp E / k T
MTTF = , (17.10)
 J | J | + k AC/DC | J | 2

where J is the average of J(t) , and | J | is the average of | J |. The constant k AC/DC
relates the relative effects of AC and DC and is typically between 0.01 and
0.0001. Electromigration problems become serious with a MTTF of less than 10 5
hours (approximately 10 years) for current densities (DC) greater than 0.5 GAm
2 at temperatures above 150 °C.

Table 17.1 lists example metallization reliability rules limits for the current you
can pass through a metal layer, contact, or viafor the typical 0.5 m m three-level
metal CMOS process, G5. The limit of 1 mA of current per square micron of
metal cross section is a good rule-of-thumb to follow for current density in
aluminum-based interconnect.
Some CMOS processes also have maximum metal-width rules (or fat-metal rules
). This is because stress (especially at the corners of the die, which occurs during
die attach mounting the die on the chip carrier) can cause large metal areas to
lift. A solution to this problem is to place slots in the wide metal lines. These
rules are dependent on the ASIC vendors level of experience.
To determine the power-bus widths we need to determine the bus currents. The
largest problem is emulating the systems operating conditions. Input vectors to
test the system are not necessarily representative of actual system operation.
Clock-bus sizing depends strongly on the parameter k AC/DC in Eq. 17.10 , since
the clock spine carries alternating current. (For the sources of power dissipation
in CMOS, see Section 15.5, Power Dissipation.)
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 to model the effects of IR drops under worst-case conditions.
TABLE 17.1 Metallization reliability rules for a typical 0.5 micron ( l = 0.25 m
m) CMOS process.
Current limit Metal thickness
Layer/contact/via Resistance 3
1 2
m1 1 mA m m 1 7000 Å 95 m W /square
m2 1 mA m m 1 7000 Å 95 m W /square
m3 2 mA m m 1 12,000 Å 48 m W /square
0.8 m m square m1 contact to
0.7 mA 11 W
diffusion
0.8 m m square m1 contact to
0.7 mA 16 W
poly
0.8 m m square m1/m2 via
0.7 mA 3.6 W
(via1)
0.8 m m square m2/m3 via
0.7 mA 3.6 W
(via2)

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 a specified intervals. Alternatively the
number of standard cells that can be placed in a row may be limited during
placement. The power router forms an interdigitated comb structure, minimizing
the number of times a VDD or VSS power bus needs to change layers. This is
achieved by routing with a routing bias on preferred layers. For example, VDD
may be routed with a left-and-down bias on m1, with VSS routed using
right-and-up bias on m2.
Three-level metal processes either use a m3 with a thickness and pitch that is
comparable to m1 and m2 (which usually have approximately the same thickness
and pitch) or they use metal that is much thicker (up to twice as thick as m1 and
m2) with a coarser pitch (up to twice as wide as m1 and m2). The factor that
determines the m3/4/5 properties is normally the sophistication of the fabrication
process.
In a three-level metal process, power routing is similar to two-level metal ASICs.
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.
Using three or more layers of metal for routing, it is possible to eliminate some of
the channels completely. In these cases we complete all the routing in m2 and m3
on top of the logic cells using connectors placed in the center of the cells on m1.
If we can eliminate the channels between cell rows, we can flip rows about a
horizontal axis and abut adjacent rows together (a technique known as flip and
abut ). If the power buses are at the top (VDD) and bottom (VSS) of the cells in
m1 we can abut or overlap the power buses (joining VDD to VDD and VSS to
VSS in alternate rows).
Power distribution schemes are also a function of process and packaging
technology. Recall that flip-chip technology allows pads to be placed anywhere
on a chip (see Section 16.1.5, I/O and Power Planning, especially
Figure 16.13d). Four-level metal and aggressive stacked-via rules allow I/O pad
circuits to be placed in the core. The problems with this approach include placing
the ESD and latch-up protection circuits required in the I/O pads (normally kept
widely separated from core logic) adjacent to the logic cells in the core.
1. At 125 °C for unidirectional current. Limits for 110 °C are ¥ 1.5 higher. Limits
for 85 °C are ¥ 3 higher. Current limits for bidirectional current are ¥ 1.5 higher
than the unidirectional limits.
2. 10,000 Å (ten thousand angstroms) = 1 m m.
3. Worst case at 110 °C.
17.4 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 or CIF widths and dimensions 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. Since this is a problem
that is dealt with by the ASIC vendor and not the design software vendor, ASIC
designers normally have to ask very carefully about the details of this problem.
Table 17.2 shows values for the parasitic capacitances for a typical 1 m m CMOS
process. Notice that the fringing capacitance is greater than the parallel-plate
(area) capacitance for all layers except poly. Next, we shall describe how the
parasitic information is passed between tools.

17.4.1 SPF, RSPF, and DSPF

The standard parasitic format ( SPF ) (developed by Cadence [ 1990], now in the
hands of OVI) 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. Figure 17.22 shows the different types of simplified models that regular and
reduced SPF support. 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.
TABLE 17.2 Parasitic capacitances for a typical 1 m m ( l = 0.5 m m)
three-level metal CMOS process. 1
Element Area / fF m m 2 Fringing / fF m m 1
poly (over gate oxide) to
1.73 NA 2
substrate
poly (over field oxide) to
0.058 0.043
substrate
m1 to diffusion or poly 0.055 0.049
m1 to substrate 0.031 0.044
m2 to diffusion 0.019 0.038
m2 to substrate 0.015 0.035
m2 to poly 0.022 0.040
m2 to m1 0.035 0.046
m3 to diffusion 0.011 0.034
m3 to substrate 0.010 0.033
m3 to poly 0.012 0.034
m3 to m1 0.016 0.039
m3 to m2 0.035 0.049
n+ junction (at 0V bias) 0.36 NA
p+ junction (at 0V bias) 0.46 NA
FIGURE 17.22 The regular and reduced standard parasitic format (SPF) models
for interconnect. (a) An example of an interconnect network with fanout. The
driving-point admittance of the interconnect network is Y ( s ). (b) The SPF
model of the interconnect. (c) The lumped-capacitance interconnect model.
(d) The lumped-RC interconnect model. (e) The PI segment interconnect model
(notice the capacitor nearest the output node is labeled C 2 rather than C 1 ). The
values of C , R , C 1 , and C 2 are calculated so that Y 1 ( s ), Y 2 ( s ), and Y 3 ( s
) are the first-, second-, and third-order Taylor-series approximations to Y ( s ).

The key features of regular and reduced SPF are as follows:

● The loading effect of a net as seen by the driving gate is represented by
choosing one of three different RC networks: lumped-C, lumped-RC, or PI
segment (selected when generating the SPF) [ OBrien and Savarino,
1989].
● The pin-to-pin delays of each path in the net are modeled by a simple RC
delay (one for each path). This can be the Elmore constant for each path
(see Section 17.1.2 ), but it need not be.

Here is an example regular SPF file for just one net that uses the PI segment
model shown in Figure 17.22 (e):

#Design Name : EXAMPLE1

#Date : 6 August 1995
#Time : 12:00:00
#Resistance Units : 1 ohms
#Capacitance Units : 1 pico farads
#Syntax :
#N <netName>
#C <capVal>
# F <from CompName> <fromPinName>
# GC <conductance>
#|
# REQ <res>
# GRC <conductance>
# T <toCompName> <toPinName> RC <rcConstant> A <value>
#|
# RPI <res>
# C1 <cap>
# C2 <cap>
# GPI <conductance>
# T <toCompName> <toPinName> RC <rcConstant> A <value>
# [Link] = PI
# [Link] = PP
N CLOCK
C 3.66
F ROOT Z
RPI 8.85
C1 2.49
C2 1.17
GPI = 0.0
T DF1 G RC 22.20
T DF2 G RC 13.05
This file describes the following:
● The preamble contains the file format.

● This representation uses the PI segment model ( Figure 17.22 e).

● This net uses pin-to-pin timing.

● The driving gate of this net is ROOT and the output pin name is Z .
● The PI segment elements have values: C1 = 2.49 pF, C2 = 1.17 pF, RPI =
8.85 W . Notice the order of C1 and C2 in Figure 17.22 (e). The element
GPI is not normally used in SPF files.
● The delay from output pin Z of ROOT to input pin G of DF1 is 22.20 ns.
● The delay from pin Z of ROOT to pin G of DF2 is 13.05 ns.
The reduced SPF ( RSPF) contains the same information as regular SPF, but uses
the SPICE format. Here is an example RSPF file that corresponds to the previous
regular SPF example:
* Design Name : EXAMPLE1
* Date : 6 August 1995
* Time : 12:00:00
* Resistance Units : 1 ohms
* Capacitance Units : 1 pico farads
*| RSPF 1.0
*| DELIMITER "_"
.SUBCKT EXAMPLE1 OUT IN
*| GROUND_NET VSS
* [Link] = PP
*|NET CLOCK 3.66PF
*|DRIVER ROOT_Z ROOT Z
*|S (ROOT_Z_OUTP1 0.0 0.0)
R2 ROOT_Z ROOT_Z_OUTP1 8.85
C1 ROOT_Z_OUTP1 VSS 2.49PF
C2 ROOT_Z VSS 1.17PF
*|LOAD DF2_G DF1 G
*|S (DF1_G_INP1 0.0 0.0)
E1 DF1_G_INP1 VSS ROOT_Z VSS 1.0
R3 DF1_G_INP1 DF1_G 22.20
C3 DF1_G VSS 1.0PF
*|LOAD DF2_G DF2 G
*|S (DF2_G_INP1 0.0 0.0)
E2 DF2_G_INP1 VSS ROOT_Z VSS 1.0
R4 DF2_G_INP1 DF2_G 13.05
C4 DF2_G VSS 1.0PF
*Instance Section
XDF1 DF1_Q DF1_QN DF1_D DF1_G DF1_CD DF1_VDD DF1_VSS DFF3
XDF2 DF2_Q DF2_QN DF2_D DF2_G DF2_CD DF2_VDD DF2_VSS DFF3
XROOT ROOT_Z ROOT_A ROOT_VDD ROOT_VSS BUF
.ENDS
.END
This file has the following features:
● The PI segment elements ( C1 , C2 , and R2 ) have the same values as the
previous example.
● The pin-to-pin delays are modeled at each of the gate inputs with a
capacitor of value 1 pF ( C3 and C4 here) and a resistor ( R3 and R4 )
adjusted to give the correct RC delay. Since the load on the output gate is
modeled by the PI segment it does not matter what value of capacitance is
chosen here.
● The RC elements at the gate inputs are driven by ideal voltage sources ( E1
and E2 ) that are equal to the voltage at the output of the driving gate.
The detailed SPF ( DSPF) shows the resistance and capacitance of each segment
in a net, again in a SPICE format. There are no models or assumptions on
calculating the net delays in this format. Here is an example DSPF file that
describes the interconnect shown in Figure 17.23 (a):

.SUBCKT BUFFER OUT IN

* Net Section
*|GROUND_NET VSS
*|NET IN 3.8E-01PF
*|P (IN I 0.0 0.0 5.0)
*|I (INV1:A INV A I 0.0 10.0 5.0)
C1 IN VSS 1.1E-01PF
C2 INV1:A VSS 2.7E-01PF
R1 IN INV1:A 1.7E00
*|NET OUT 1.54E-01PF
*|S (OUT:1 30.0 10.0)
*|P (OUT O 0.0 30.0 0.0)
*|I (INV:OUT INV1 OUT O 0.0 20.0 10.0)
C3 INV1:OUT VSS 1.4E-01PF
C4 OUT:1 VSS 6.3E-03PF
C5 OUT VSS 7.7E-03PF
R2 INV1:OUT OUT:1 3.11E00
R3 OUT:1 OUT 3.03E00
*Instance Section
XINV1 INV:A INV1:OUT INV
.ENDS
The nonstandard SPICE statements in DSPF are comments that start with '*|' and
have the following formats:
*|I(InstancePinName InstanceName PinName PinType PinCap X Y)
*|P(PinName PinType PinCap X Y)
*|NET NetName NetCap
*|S(SubNodeName X Y)
*|GROUND_NET NetName
Figure 17.23 (b) illustrates the meanings of the DSPF terms: InstancePinName ,
InstanceName , PinName , NetName , and SubNodeName . The PinType is I (for
IN) or O (the letter 'O', not zero, for OUT). The NetCap is the total capacitance
on each net. Thus for net IN, the net capacitance is
0.38 pF = C1 + C2 = 0.11 pF + 0.27 pF.
This particular file does not use the pin capacitances, PinCap . Since the DSPF
represents every interconnect segment, DSPF files can be very large in size
(hundreds of megabytes).

FIGURE 17.23 The detailed standard parasitic format (DSPF) for interconnect
representation. (a) An example network with two m2 paths connected to a logic
cell, INV1. The grid shows the coordinates. (b) The equivalent DSPF circuit
corresponding to the DSPF file in the text.

17.4.2 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. Since the detailed router normally works with logic-cell phantoms, 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. Normally the ASIC vendor will perform this
check using its own software as a type of incoming inspection. The Cadence
Dracula software is one de facto standard in this area, and you will often hear
reference to a Dracula deck that consists of the Dracula code describing an ASIC
vendors design rules. Sometimes ASIC vendors will give their Dracula decks to
customers so that the customers can perform the DRCs themselves.
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. The LVS check is not as straightforward as it may sound, however.
The first problem with an LVS check is that the transistor-level netlist for a large
ASIC forms an enormous graph. LVS software essentially has to match this
graph against a reference graph that describes the design. Ensuring that every
node corresponds exactly to a corresponding element in the schematic (or HDL
code) is a very difficult task. The first step is normally to match certain key nodes
(such as the power supplies, inputs, and outputs), but the process can very
quickly become bogged down in the thousands of mismatch errors that are
inevitably generated initially.
The second problem with an LVS check is creating a true reference. The starting
point may be HDL code or a schematic. However, logic synthesis, test insertion,
clock-tree synthesis, logical-to-physical pad mapping, and several other design
steps each modify the netlist. The reference netlist may not be what we wish to
fabricate. In this case designers increasingly resort to formal verification that
extracts a Boolean description of the function of the layout and compare that to a
known good HDL description.

17.4.3 Mask Preparation

Final preparation for the ASIC artwork includes the addition of a maskwork
symbol (M inside a circle), copyright symbol (C inside a circle), and company
logos on each mask layer. A bonding editor creates a bonding diagram that will
show the connection of pads to the lead carrier as well as checking that there are
no design-rule violations (bond wires that are too close to each other or that leave
the chip at extreme angles). We also add the kerf (which contains alignment
marks, mask identification, and other artifacts required in fabrication), the scribe
lines (the area where the die will be separated from each other by a diamond
saw), and any special hermetic edge-seal structures (usually metal).
The final output of the design process is normally a magnetic tape written in
Caltech Intermediate Format ( CIF , a public domain text format) or GDSII
Stream (formerly also called Calma Stream, now Cadence Stream), which is a
proprietary binary format. The tape is processed by the ASIC vendor or foundry
(the fab ) before being transferred to the mask shop .
If the layout contains drawn n -diffusion and p -diffusion regions, then the fab
generates the active (thin-oxide), p -type implant, and n -type implant layers. The
fab then runs another polygon-level DRC to check polygon spacing and overlap
for all mask levels. A grace value (typically 0.01 m m) is included to prevent
false errors stemming from rounding problems and so on. The fab will then adjust
the mask dimensions for fabrication either by bloating (expanding), shrinking,
and merging shapes in a procedure called sizing or mask tooling . The exact
procedures are described in a tooling specification . A mask bias is an amount
added to a drawn polygon to allow for a difference between the mask size and the
feature as it will eventually appear in silicon. The most common adjustment is to
the active mask to allow for the birds beak effect , which causes an active area to
be several tenths of a micron smaller on silicon than on the mask.
The mask shop will use e-beam mask equipment to generate metal (usually
chromium) on glass masks or reticles . The e-beam spot size determines the
resolution of the mask-making equipment and is usually 0.05 m m or 0.025 m m
(the smaller the spot size, the more expensive is the mask). The spot size is
significant when we break the integer-lambda scaling rules in a deep-submicron
process. For example, for a 0.35 m m process ( l = 0.175 m m), a 1.5 l separation
is 0.525 m m, which requires more expensive mask-making equipment with a
0.025 m m spot size. For critical layers (usually the polysilicon mask) the mask
shop may use optical proximity correction ( OPC ), which adjusts the position of
the mask edges to allow for light diffraction and reflection (the deep-UV light
used for printing mask images on the wafer has a wavelength comparable to the
minimum feature sizes).

1. Fringing capacitances are per isolated line. Closely spaced lines will have
reduced fringing capacitance and increased interline capacitance, with increased
total capacitance.
2. NA = not applicable.
17.5 Summary
The completion of routing finishes the ASIC physical design process. Routing is
a complicated problem best divided into two steps: global and detailed routing.
Global routing plans the wiring by finding the channels to be used for each path.
There are differences between global routing for different types of ASICs, but the
algorithms to find the shortest path are similar. Two main approaches to global
routing are: one net at a time, or all nets at once. With the inclusion of
timing-driven routing objectives, the routing problem becomes much harder and
requires understanding the differences between finding the shortest net and
finding the net with the shortest delay. Different types of detail routing include
channel routing and area-based or maze routing. Detailed routing with two layers
of metal is a fairly well understood problem.
The most important points in this chapter are:
● Routing is divided into global and detailed routing.

● Routing algorithms should match the placement algorithms.

● Routing is not complete if there are unroutes.

● Clock and power nets are handled as special cases.

● Clock-net widths and power-bus widths must usually be set by hand.

● DRC and LVS checks are needed before a design is complete.