Application – Specific Integrated Circuits [ASIC]

Unit IV
Floor planning and placement: Goals and objectives, Measurement of delay in
Floor planning, Floor planning tools, Channel
definition, I/O and Power planning and Clock
planning.
Placement: Goals and Objectives, Min-cut Placement algorithm, Iterative
Placement Improvement, Time-driven placement methods, Physical
Design Flow.
(05+05) Hrs

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 1

 Application – Specific Integrated Circuits [ASIC]

FLOORPLANNING AND PLACEMENT

➢ The input to the floorplanning step is the output of system partitioning and design entry a

netlist.

➢ Floorplanning precedes placement, but we shall cover them together.

➢ The output of the placement step is a set of directions for the routing tools.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 2

 Application – Specific Integrated Circuits [ASIC]

Introduction - Floorplanning
Figure 16.3 illustrates that both interconnect delay and gate delay decrease as feature sizes are scaled down, but at
different rates. This is because interconnect capacitance tends to a limit of about 2 pFcm-1 for a minimum-width
wire while gate delay continues to decrease (see Section 17.4, Circuit Extraction and DRC).
Floorplanning allows us to predict this interconnect delay by estimating the interconnect length.

FIGURE 16.3 Interconnect and gate delays.

As feature sizes decrease, both average
interconnect delay and average gate delay
decrease at different rates. This is because
interconnect capacitance tends to a limit that
is independent of scaling. Interconnect delay
now dominates gate delay.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 3

 Application – Specific Integrated Circuits [ASIC]

Floorplanning Goals and Objectives

The input to a floorplanning tool is a hierarchical netlist that describes the interconnection of the blocks (RAM, ROM, ALU,
cache controller, and so on); the logic cells (NAND, NOR, D flip-flop, and so on) within the blocks; and the logic cell
connectors (the terms terminals, pins, or ports mean the same thing as connectors).
The netlist is a logical description of the ASIC; the floorplan is a physical description of an ASIC.
Floorplanning is thus a mapping between the logical description (the netlist) and the physical description (the floorplan).
The goals of floorplanning are to:
➢ arrange the blocks on a chip,
➢ decide the location of the I/O pads,
➢ decide the location and number of the power pads,
➢ decide the type of power distribution, and
➢ decide the location and type of clock distribution.
The objectives of floorplanning are to minimise the chip area and minimise delay. Measuring area is straightforward, but
measuring delay is more difficult. We shall explore this next.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 4

 Application – Specific Integrated Circuits [ASIC]

Die

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 5
 Application – Specific Integrated Circuits [ASIC]

Die

H
Core

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 6
 Application – Specific Integrated Circuits [ASIC]

Die

H
Core

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 7
 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 8

 Application – Specific Integrated Circuits [ASIC]

Block A Block B
Die
Block C
H
Core
Block D

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 9
 Application – Specific Integrated Circuits [ASIC]

Decap1
Block A Block B
Decap2 Die
Block C
H
Core
Block D

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 10
 Application – Specific Integrated Circuits [ASIC]

Decap1
D
Block A 3 Block B
Decap2 Die
Block C
H
Core
Block D

W
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 11
 Application – Specific Integrated Circuits [ASIC]

Block Block
A B

Block C

Block D

Vss

Vdd

contact
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 12
 Application – Specific Integrated Circuits [ASIC]

Block Block
A B

Block C

Block D

Vss

Vdd

contact
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 13
 Application – Specific Integrated Circuits [ASIC]

Block Block
I/O
A B

Block C

Block D

Vss

Vdd
contact

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 14

 Application – Specific Integrated Circuits [ASIC]

Power Pads

Block Block
Din Dout
A B

CLK in Block C CLK out

Block D

Vss

Vdd
contact

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 15

 Application – Specific Integrated Circuits [ASIC]

Measurement of Delay in Floorplanning

❖ Throughout the ASIC design process, we need to predict the performance of the final layout. In floorplanning,
we wish to predict the interconnect delay before we complete any routing.
❖ To predict delay, we need to know the parasitics associated with the interconnect:
❖ The interconnect capacitance (wiring capacitance or routing capacitance) as well as the interconnect
resistance.
❖ At the floorplanning stage, we know only the fan-out (FO) of a net (the number of gates driven by a net) and
the size of the block that the net belongs to.
❖ We cannot predict the resistance of the various pieces of the interconnect path since we do not yet know the
shape of the interconnect for a net.
❖ However, we can estimate the total length of the interconnect and thus estimate the total capacitance.
❖ We estimate interconnect length by collecting statistics from previously routed chips and analyzing the results.
❖ From these statistics, we create tables that predict the interconnect capacitance as a function of net fan-out and
block size.
❖ A Floorplanning tool can then use these predicted-capacitance tables (also known as interconnect-load
tables or wire-load tables).
❖ Figure 16.4 shows how we derive and use wire-load tables and illustrates the following facts:

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 16

 Application – Specific Integrated Circuits [ASIC]

Figure 16.4 Predicted capacitance.

a) Interconnect lengths as a function
of fanout (FO) and circuit-block size.
(b) Wire-load table. There is only one
capacitance value for each fanout
(typically the average value).
(c) The wire-load table predicts the
capacitance and delay of a net (with a
considerable error).
Net A and net B both have a fanout of
1, both have the same predicted net
delay, but net B, in fact, has a much
greater delay than net A in the actual
layout (of course, we shall not know
what the actual layout is until much
later in the design process).

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 17

 Application – Specific Integrated Circuits [ASIC]
➢ Typically, between 60 and 70 percent of nets have a FO = 1.
➢ The distribution for a FO = 1 has a very long tail, stretching to interconnects that run from corner to corner of the chip.
➢ The distribution for a FO = 1 often has two peaks, corresponding to a distribution for close neighbours in subgroups within a block,
superimposed on a distribution corresponding to routing between subgroups.
➢ We often see a twin-peaked distribution at the chip level, also corresponding to separate distributions for interblock routing (inside
blocks) and intrablock routing (between blocks).
➢ The distributions for FO > 1 are more symmetrical and flatter than for FO = 1.
➢ The wire-load tables can only contain one number, for example, the average net capacitance, for any one distribution. Many tools take a
worst-case approach and use the 80- or 90-percentile point instead of the average. Thus, a tool may use a predicted capacitance for which
we know 90 per cent of the nets will have less than the estimated capacitance.
➢ We need to repeat the statistical analysis for blocks with different sizes. For example, a net with an FO = 1 in a 25 k-gate block will have a
different(larger) average length than if the net were in a 5 k-gate block.
➢ The statistics depend on the shape (aspect ratio) of the block (usually, the statistics are only calculated for square blocks).
➢ The statistics will also depend on the type of netlist. For example, the distributions will be different for a netlist generated by setting a
constraint for minimum logic delay during synthesis, which tends to generate larger numbers of two-input NAND gates than for netlists
generated using minimum-area constraints.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 18

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 19

 Application – Specific Integrated Circuits [ASIC]

Floorplanning Tools
➢ Figure 16.6 (a) shows an initial random floorplan generated by a floorplanning tool.
➢ Two of the blocks, A and C in this example, are standard-cell areas (the chip shown in Figure 16.1 is one large standard-cell
area).
➢ These are flexible blocks (or variable blocks) because, although their total area is fixed, their shape (aspect ratio) and
connector locations may be adjusted during the placement step.
➢ The dimensions and connector locations of the other fixed blocks (perhaps RAM, ROM, compiled cells, or megacells) can
only be modified when they are created. We may force logic cells to be in selected flexible blocks by seeding.
➢ We choose seed cells by name. For example, ram_control* would select all logic cells whose names started with ram_control
to be placed in one flexible block. The special symbol, usually ' * ', is a wildcard symbol.
➢ Seeding may be hard or soft. A hard seed is fixed and not allowed to move during the remaining floorplanning and placement
steps.
➢ A soft seed is an initial suggestion only and can be altered, if necessary, by the floor planner. We may also use seed
connectors within flexible blocks, forcing certain nets to appear in a specified order or location at the boundary of a flexible
block.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 20
 Application – Specific Integrated Circuits [ASIC]
➢ The floorplanner can complete an estimated placement to determine the positions of connectors at the boundaries of the
flexible blocks.
➢ Figure 16.6 (b) illustrates a rat’s nest display of the connections between blocks. Connections are shown as bundles
between the centers of blocks or as flight lines between connectors.
➢ Figure 16.6 (c) and (d) show how we can move the blocks in a floorplanning tool to minimise routing congestion.
➢ Figure 16.7 (a) (c) shows how we can rearrange our chip to achieve a square aspect ratio.
➢ Figure 16.7 (c) also shows a congestion map, another form of routability display. There is no standard measure of
routability.
➢ One measure of congestion is the difference between the number of interconnects that we actually need, called the
channel density, and the channel capacity.
➢ Another measure, shown in Figure 16.7 (c), uses the ratio of channel density to the channel capacity. With practice, we
can create a good initial placement by floorplanning and a pictorial display.
➢ This is one area where the human ability to recognize patterns and spatial relations is currently superior to a computer
program’s ability.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 21

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.6 Floorplanning a

cell-based ASIC.
(a) Initial floorplan generated
by the floorplanning tool.
Two of the blocks are
flexible (A and C) and
contain rows of standard
cells (unplaced). A pop-up
window shows the status of
blockA.
(b) An estimated placement for
flexible blocks A and C.
The connector positions are
known, and a rat’s nest
display shows the heavy
congestion below block B.
(c) Moving blocks to improve
the floorplan.
(d) The updated display shows
the reduced congestion after
the changes.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 22

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.7 Congestion analysis.

(a) The initial floorplan with a 2:1.5 die
aspect ratio.
(b) Altering the floorplan to give a 1:1
chip aspect ratio.
(c) A trial floorplan with a congestion
map. Blocks A and C have been
placed so that we know the terminal
positions in the channels. Shading
indicates the ratio of channel density
to the channel capacity. Dark areas
show regions that cannot be routed
because the channel congestion
exceeds the estimated capacity.
(d) Resizing flexible blocks, A and C
alleviates congestion.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 23

 Application – Specific Integrated Circuits [ASIC]

Channel Definition
During the floorplanning step, we assign the areas between blocks that are to be used for interconnect. This process is known
as channel definition or channel allocation.
Figure 16.8 shows a T-shaped junction between two rectangular channels and illustrates why we must route the stem (vertical)
of the T before the bar. The general problem of choosing the order of rectangular channels to route is channel ordering.

FIGURE 16.8 Routing a T-

junction between two channels in
two-level metal.
The dots represent logic cell pins.
(a) Routing channel A (the stem
of the T) first allows us to
adjust the width of channel B.
(b) If we route channel B first
(the top of the T), this fixes
the width of channel A.
We have to route the stem of a T-
junction before we route the top.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 24

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.9 Defining the channel routing order for a slicing floorplan using a slicing tree.
(a) Make a cut all the way across the chip between circuit blocks. Continue slicing until each piece contains just one
circuit block. Each cut divides a piece into two without cutting through a circuit block.
(b) A sequence of cuts:1, 2, 3, and 4 that successively slice the chip until only circuit blocks are left.
(c) The slicing tree corresponding to the sequence of cuts gives the order in which to route the channels: 4, 3, 2, and
finally 1.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 25
 Application – Specific Integrated Circuits [ASIC]

✓ Figure 16.9 shows a floorplan of a chip containing several blocks. Suppose we cut along the block boundaries,
slicing the chip into two pieces ( Figure 16.9a).
✓ Then, suppose we can slice each of these pieces into two. If we can continue in this fashion until all the blocks
are separated, then we have a slicing floorplan (Figure 16.9 b).
✓ Figure 16.9 (c) shows how the sequence we use to slice the chip defines a hierarchy of the blocks.
✓ Reversing the slicing order ensures that we route the stems of all the channel T-junctions first.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 26

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.10 Cyclic constraints.

(a) A nonslicing floorplan with a cyclic constraint that prevents channel routing.
(b) In this case, it is difficult to find a slicing floorplan without increasing the chip area.
(c) This floorplan may be sliced (with initial cuts 1 or 2) and has no cyclic constraints, but it is inefficient in area use and
will be very difficult to route.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 27
 Application – Specific Integrated Circuits [ASIC]

➢ Figure 16.10 shows a floorplan that is not a slicing structure. We cannot cut the chip all the way across with a knife
without chopping a circuit block in two. This means we cannot route any of the channels in this floorplan without routing
all of the other channels first. We say there is a cyclic constraint in this floorplan. There are two solutions to this
problem. One solution is to move the blocks until we obtain a slicing floorplan. The other solution is to allow the use of
L-shaped, rather than rectangular, channels (or areas with fixed connectors on all sides, as a switch box). We need an
area-based router rather than a channel router to route L-shaped regions or switch boxes (see Section 17.2.6, Area-Routing
Algorithms).
➢ Figure 16.11 (a) displays the floorplan of the ASIC shown in Figure 16.7. We can remove the cyclic constraint by moving
the blocks again, but this increases the chip size.
➢ Figure 16.11 (b) shows an alternative solution. We merge the flexible standard cell areas A and C. We can do this by
selective flattening of the netlist. Sometimes flattening can reduce the routing area because routing between blocks is
usually less efficient than routing inside the row-based blocks.
➢ Figure 16.11 (b) shows the channel definition and routing order for our chip.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 28

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.11 Channel definition and ordering.

(a) We can eliminate the cyclic constraint by merging the blocks A and C.
(b) A slicing structure.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 29

 Application – Specific Integrated Circuits [ASIC]

I/O and Power Planning

➢ Every chip communicates with the outside world. Signals flow onto and off the chip, and we need to supply power.
➢ We need to consider the I/O and power constraints early in the floorplanning process.
➢ A silicon chip or die (plural die, dies, or dice) is mounted on a chip carrier inside a chip package.
➢ Connections are made by bonding the chip pads to fingers on a metal lead frame that is part of the package.
➢ The metal lead-frame fingers connect to the package pins. A die consists of a logic core inside a pad ring.
➢ Figure 16.12 (a) shows a pad-limited die, and Figure 16.12 (b) shows a core-limited die.
➢ On a pad-limited die, we use tall, thin pad-limited pads, which maximize the number of pads we can fit around the outside
of the chip. On a core-limited die, we use short, widecore-limited pads.
➢ Figure 16.12 (c) shows how we can use both types of pads to change the aspect ratio of a die to be different from that of
the core.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 30

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.12 Pad-limited and core-limited die.

(a) A pad-limited die. The number of pads determines the die size.
(b) A core-limited die: The core logic determines the die size.
(c) Using both pad-limited pads and core-limited pads for a square die.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 31
 Application – Specific Integrated Circuits [ASIC]

If we make an electrical connection between the substrate and a chip pad, or to a package pin, it must be to VDD (n-type
substrate) or VSS (p-type substrate). This substrate connection(for the whole chip) employs a down bond (or drop bond) to
the carrier.
We have several options:
➢ We can dedicate one (or more) chip pad(s) to down bond to the chip carrier.
➢ We can make a connection from a chip pad to the lead frame and downbond from the chip pad to the chip carrier.
➢ We can make a connection from a chip pad to the lead frame and downbond from the lead frame.
➢ We can down bond from the lead frame without using a chip pad.
➢ We can leave the substrate and/or chip carrier unconnected.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 32

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.13 Bonding pads.

(a) This chip uses both pad-
limited and core-limited
pads.
(b) A hybrid corner pad.
(c) A chip with stagger-bonded
pads.
(d) An area-bump bonded chip
(or flip-chip).
The chip is turned upside
down, and solder bumps
connect the pads to the lead
frame.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 33

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.14 Gate-array I/O

pads.
(a) Cell-based ASIC may contain
pad cells of different sizes and
widths.
(b) A corner of a gate-array base.
(c) Agate-array base with
different I/O cell and pad
pitches.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 34

 Application – Specific Integrated Circuits [ASIC]
FIGURE 16.15 Power distribution.
(a) Power distributed using m1 for
VSS and m2 for VDD. This helps
minimize the number of vias and
layer crossings needed, but causes
problems in the routing channels.
(b) In this floorplan, m1 is run
parallel to the longest side of all
channels, the channel spine. This
can make automatic routing easier,
but may increase the number of
vias and layer crossings.
(c) An expanded view of part of a
channel (interconnect is shown as
lines). If power runs on different
layers along the spine of a channel,
this forces signals to change
layers.
(d) A close-up of VDD and VSS buses
as they cross. Changing layers
requires a large number of via
contacts to reduce resistance.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 35

 Application – Specific Integrated Circuits [ASIC]

Clock Planning
➢ Figure 16.16 (a) shows a clock spine (not to be confused with a channel spine) routing scheme with all clock pins driven directly
from the clock driver. MGAs and FPGAs often use this fishbone type of clock distribution scheme.
➢ Figure 16.16 (b) shows a clock spine for a cell-based ASIC.
➢ Figure 16.16 (c) shows the clock-driver cell, often part of a special clock-pad cell.
➢ Figure 16.16 (d) illustrates clock skew and clock latency.
Since all clocked elements are driven from one net with a clock spine, skew is caused by differing interconnect lengths and loads. If
the clock-driver delay is much larger than the interconnect delays, a clock spine achieves minimum skew but with long latency.
➢ Figure 16.16 (c) illustrates the construction of a clock-driver cell.
➢ The delay through a chain of CMOS gates is minimized when the ratio between the input capacitance C1 and the output (load)
capacitance C2 is about 3 (exactly e ª 2.7, an exponential ratio, if we neglect the effect of parasitics).
➢ This means that the fastest way to drive a large load is to use a chain of buffers with their input and output loads chosen to
maintain this ratio, or taper (we use this as a noun and a verb). This is not necessarily the smallest or lowest-power method,
though.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 36

 Application – Specific Integrated Circuits [ASIC]
FIGURE 16.16 Clock distribution.
(a) A clock spine for a gate array.
(b) A clock spine for a cell-based
ASIC (typical chips have
thousands of clock nets).
(c) A clock spine is usually driven
from one or more clock-driver
cells. Delay in the driver cell is a
function of the number of stages
and the ratio of output to input
capacitance for each stage
(taper).
(d) Clock latency and clock skew.
We would like to minimize both
latency and skew.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 37

 Application – Specific Integrated Circuits [ASIC]
Suppose we have an ASIC with the following specifications:
✓ 40,000 flip-flops
✓ Input capacitance of the clock input to each flip-flop is 0.025 pF
✓ Clock frequency is 200 MHz
✓ VDD = 3.3 V
✓ Chip size is 20 mm on a side
✓ Clock spine consists of 200 lines across the chip
✓ Interconnect capacitance is 2 pFcm _1

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 38

 Application – Specific Integrated Circuits [ASIC]

➢ We can design a tree of clock

buffers so that the taper of each
stage is e ~ 2.7 by using a fanout of
three at each node, as shown in
Figure 16.17 (a) and (b).
➢ The clock tree, shown in Figure
16.17 (c), uses the same number of
stages as a clock pine, but with a
lower peak current for the inverter
buffers.
➢ Figure 16.17 (c) illustrates that we
now have another problem: we need
to balance the delay through the tree
carefully to minimize clock skew
(see Section 17.3.1, ClockRouting).

FIGURE 16.17 A clock tree.

(a) Minimum delay is achieved when the taper of successive stages is about 3.
(b) Using a fanout of three at successive nodes.
(c) A clock tree for the cell-based ASIC of Figure 16.16 b.
(d) We have to balance the clock arrival times at all of the leaf nodes to minimize clock skew.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 39
 Application – Specific Integrated Circuits [ASIC]

Introduction - Placement
• After completing a floorplan, we can begin placement of the logic cells within the flexible blocks.
• Placement is much more suited to automation than floor planning.

• Thus, we shall need measurement techniques and algorithms. After we complete floor planning and
placement, we can predict both intrablock and interblock capacitances.

• This allows us to return to logic synthesis with more accurate estimates of the capacitive loads that each logic
cell must drive.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 40

 Application – Specific Integrated Circuits [ASIC]
➢ CBIC, MGA, and FPGA
architectures all have rows of logic
cells separated by these are row-
based ASICs.
➢ Figure 16.18 shows an example of
the interconnect structure for a
CBIC. Interconnect runs in
horizontal and vertical directions in
the channels and in the vertical
direction by crossing through the
logic cells.
➢ Figure 16.18 (c) illustrates the fact
that it is possible to use over-the-cell
routing( OTC routing) in areas that
are not blocked. However, OTC
routing is complicated by the fact
that the logic cells themselves may
contain metal on the routing layers. FIGURE 16.18 Interconnect structure.
We shall return to this topic in (a) The two-level metal CBIC floor plans are shown in Figure 16.11 b.
Section 17.2.7, Multilevel Routing. (b) A channel from the flexible block A. This channel has a channel height equal to
➢ Figure 16.19 shows the interconnect the maximum channel density of 7 (there is room for seven interconnects to run
structure of a two-level metal MGA. horizontally in m1).
(c) A channel that uses OTC (over-the-cell) routing in m2.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 41
 Application – Specific Integrated Circuits [ASIC]

Logic Cells

Channel Height = 7

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 42

 Application – Specific Integrated Circuits [ASIC]
FIGURE 16.19 Gate-array interconnect.
(a) A small two-level metal gate
array(about 4.6 k-gate).
(b) Routing in a block.
(c) Channel routing showing channel
density and channel capacity.
The channel height on a gate array may
only be increased in increments of a row.
If the interconnect does not use up all of
the channel, the rest of the space is
wasted.
The interconnect in the channel runs in
m1 in the horizontal direction with m2 in
the vertical direction.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 43

 Application – Specific Integrated Circuits [ASIC]
Vertical interconnect uses feedthroughs (or feedthrus in the United States) to cross the logic cells. Here are some commonly
used terms with explanations (there are no generally accepted definitions):
❖ An unused vertical track (or just track) in a logic cell is called an uncommitted feedthrough (also built-in feedthrough,
implicit feedthrough, or jumper).
❖ A vertical strip of metal that runs from the top to the bottom of a cell (for double-entry cells), but has no connections inside
the cell, is also called a feedthrough or jumper.
❖ Two connectors for the same physical net are electrically equivalent connectors (or equipotential connectors). For
double-entry cells, these are usually at the top and bottom of the logic cell.
❖ A dedicated feedthrough cell (or) is an empty cell (with no logic)that can hold one or more vertical interconnects. These are
used if there are no other feedthroughs available.
❖ A feedthrough pin or feedthrough terminal is an input or output that has connections at both the top and bottom of the
standard cell.
❖ A spacer cell (usually the same as a feedthrough cell) is used to fill space in rows so that the ends of all rows in a flexible
block may be aligned to connect to power buses, for example.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 44

 Application – Specific Integrated Circuits [ASIC]

Placement Goals and Objectives

The goal of a placement tool is to arrange all the logic cells within the flexible blocks on a chip. Ideally, the objectives of the
placement step are to
➢ Guarantee the router can complete the routing step
➢ Minimize all the critical net delays
➢ Make the chip as dense as possible
We may also have the following additional objectives:
➢ Minimize power dissipation
➢ Minimize cross-talk between signals
Objectives such as these are difficult to define in a way that can be solved with an algorithm and even harder to actually meet.
Current placement tools use more specific and achievable criteria. The most commonly used placement objectives are one or
more of the following:
➢ Minimize the total estimated interconnect length
➢ Meet the timing requirements for critical nets
➢ Minimize the interconnect congestion
Each of these objectives in some way represents a compromise.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 45
 Application – Specific Integrated Circuits [ASIC]

Measurement of Placement Goals and Objectives

FIGURE 16.20 Placement using trees on
graphs.
(a) The floorplan from Figure 16.11b.
(b) An expanded view of the flexible block
A showing four rows of standard cells
for placement (typical blocks may
contain thousands or tens of thousands
of logic cells).
We want to find the length of the net shown
with four terminals, W through Z, given the
placement of four logic cells (labelled:
A.211, A.19, A.43, A.25).
(a) The problem for net (W, X, Y, Z) is
drawn as a graph. The shortest
connection is the minimum Steiner tree.
(b) The minimum rectilinear Steiner tree
using Manhattan routing. The
rectangular (Manhattan) interconnect-
length measures are shown for each
tree.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 46

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.21 Interconnect-length measures.

(a) Complete graph measure.
(b) Half-perimeter measure.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 47
 Application – Specific Integrated Circuits [ASIC]

1 2 3 4 5 6 7

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 48

 Application – Specific Integrated Circuits [ASIC]

1 5 2 3 4 6 7 8

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 49

 Application – Specific Integrated Circuits [ASIC]

1 5 2 3 4 6 7 8

One row
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 50
 Application – Specific Integrated Circuits [ASIC]

1 3

5 6

8 4

2 7

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 51

 Application – Specific Integrated Circuits [ASIC]

1 2

3 5

4 6

8 7

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 52

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 53

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 54

 Application – Specific Integrated Circuits [ASIC]

Wire Length Estimation

• Complete Graph
• Rectilinear Minimum Spanning tree
• Rectilinear Steiner minimum tree
• Half-perimeter wire length (HPWL)

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 55

 Application – Specific Integrated Circuits [ASIC]

• The complete graph has connections from each terminal to every other
terminal.

• The complete-graph measure adds all the interconnect lengths of the

complete-graph connection together and then divides by n /2, where n is the
number of terminals.
• We can justify this since, in a graph with n terminals, (n – 1)
interconnects will emanate from each terminal to join the other (n –1)
terminals in a complete graph connection. That makes n (n – 1)
interconnects in total. However, we have then made each connection twice.
So there are one-half this many, or n (n – 1)/2, interconnects needed for a
complete graph connection.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 56

 Application – Specific Integrated Circuits [ASIC]

❑ A minimum spanning tree (MST) or minimum

weight spanning tree is a subset of the edges
of a connected, edge-weighted undirected graph
that connects all the vertices together, without any
cycles and with the minimum possible total edge
weight.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 57

 Application – Specific Integrated Circuits [ASIC]

1. The minimum rectilinear Steiner tree ( MRST ) is

the shortest interconnect using a rectangular grid.
2. The determination of the MRST is, in general, an
NP-complete problem, which means it is hard to
solve. For small numbers of terminals, heuristic
algorithms do exist, but they are expensive to
compute.

Nondeterministic Turing machine accepts in Polynomial time.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 58

 Application – Specific Integrated Circuits [ASIC]

1. Efficient and most widely used.

2. Finds the smallest bounding rectangle that encloses
all the pins to be connected.
3. Estimated wire length is half the perimeter of this
rectangle. (w + L)
4. Always underestimates the wire length for congested
nets.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 59

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 60

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.22 Correlation between

FIGURE 16.23 Interconnect congestion for the cell-based ASIC from Figure 16.11(b).
total length of chip interconnect and
(a) Measurement of congestion.
the half-perimeter and complete-
(b) An expanded view of flexible block A shows a maximum cut line.
graph measures.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 61
 Application – Specific Integrated Circuits [ASIC]

Placement Algorithms
• There are two classes of placement algorithms commonly used in commercial CAD tools:
- Constructive placement
✓ Min-cut algorithm
✓ Eigenvalue method
- Iterative placement
✓ MIN-CUT PLACEMENT
• The min-cut placement method uses successive application of partitioning
- Cut the placement area into two pieces.
- Swap the logic cells to minimize the cut cost.
- Repeat the process from step 1, cutting smaller pieces until all the logic cells are placed.
• Usually we divide the placement area into bins .
• The size of a bin can vary, from a bin size equal to the base cell (for a gate array) to a bin size that
would hold several logic cells.
• We can start with a large bin size, to get a rough placement, and then reduce the in size to get
a final placement.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 62
 Application – Specific Integrated Circuits [ASIC]
FIGURE 16.24 Min-cut
placement.
(a) Divide the chip into bins
using a grid.
(b) Merge all connections to
the center of each bin.
(c) Make a cut and swap logic
cells between bins to
minimize the cost of the
cut.
(d) Take the cut pieces and
throw out all the edges that
are not inside the piece.
(e) Repeat the process with a
new cut and continue until
we reach the individual
bins.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 63

 Application – Specific Integrated Circuits [ASIC]

✓ Eigenvalue method

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 64

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 65

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 66

 Application – Specific Integrated Circuits [ASIC]

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 67

 Application – Specific Integrated Circuits [ASIC]

✓ Iterative Placement Improvement

• An iterative placement improvement algorithm takes an existing placement and tries to
improve it by moving the logic cells.
• There are two parts to the algorithm:
- The selection criteria that decides which logic cells to try moving.
- The measurement criteria that decides whether to move the selected cells.
• There are several interchange or iterative exchange methods that differ in their
selection and measurement criteria:
- Pairwise interchange,
- Force-directed interchange,
- Force-directed relaxation, and
- Force-directed pairwise relaxation.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 68

 Application – Specific Integrated Circuits [ASIC]
• All of these methods usually consider only pairs of logic cells to be exchanged. A source logic cell is picked
for trial exchange with a destination logic cell. We have already discussed the use of interchange
methods applied to the system partitioning step.

• The most widely used methods use group migration, especially the Kernighan–Lin algorithm.

• The pairwise-interchange algorithm is similar to the interchange algorithm used for iterative
improvement in the system partitioning step:

1. Select the source logic cell at random.

2. Try all the other logic cells in turn as the destination logic cell.

3. Use any of the measurement methods we have discussed to decide on whether to accept the
interchange.

4. The process repeats from step 1, selecting each logic cell in turn as a source logic cell.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 69

 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.26 Interchange.

(a) Swapping the source logic cell with a destination logic cell in pairwise interchange.
(b) Sometimes we have to swap more than two logic cells at a time to reach an optimum placement, but this is expensive in
computation time. Limiting the search to neighborhoods reduces the search time. Logic cells within a distance e of a logic cell
form an e-neighborhood.
(c) A one-neighborhood.
(d) A two-neighborhood
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 70
 Application – Specific Integrated Circuits [ASIC]
• Figure 16.26 (a) and (b) show how we can extend pairwise interchange to swap more than two logic cells at a time. If we
swap l logic cells at a time and find a locally optimum solution, we say that the solution is l -optimum.

• The neighborhood exchange algorithm is a modification to pairwise interchange that considers only destination logic cells
in a neighborhood —cells within a certain distance, e, of the source logic cell.

• Limiting the search area for the destination logic cell to the e -neighborhood reduces the search time.

• Figure 16.26 (c) and (d) show the one- and two-neighborhoods (based on Manhattan distance) for a logic cell.

• Neighborhoods are also used in some of the force-directed placement methods. Imagine identical springs connecting all
the logic cells we wish to place.

• The number of springs is equal to the number of connections between logic cells. The effect of the

springs is to pull connected logic cells together.

• The more highly connected the logic cells, the stronger the pull of the springs.

• The force on a logic cell i due to logic cell j is given by Hooke’s law, which says the force of a spring is proportional to its
extension.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 71
 Application – Specific Integrated Circuits [ASIC]
Figure 16.27 illustrates the force-directed placement algorithm.

FIGURE 16.27 Force-directed placement.

(a) A network with nine logic cells.
(b) We make a grid (one logic cell per bin).
(c) Forces are calculated as if springs were attached to the centers of each logic cell for each
connection. The two nets connecting logic cells A and I correspond to two springs.
(d) The forces are proportional to the spring extensions.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 72
 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.28 Force-directed iterative placement improvement.

(a) Force-directed interchange.
(b) Force-directed relaxation.
(c) Force-directed pairwise relaxation.

Figure 16.28 illustrates the different kinds of force-directed placement algorithms. The force-directed interchange algorithm
uses the force vector to select a pair of logic cells to swap. In force-directed relaxation, a chain of logic cells is moved. The
force-directed pairwise relaxation algorithm swaps one pair of logic cells at a time.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 73
 Application – Specific Integrated Circuits [ASIC]

✓ Placement Using Simulated Annealing

The principles of simulated annealing were explained in Section 15.7.8, Simulated Annealing. Because simulated annealing
requires so many iterations, it is critical that the placement objectives be easy and fast to calculate. The optimum
connection pattern, the MRST, is difficult to calculate. Using the half-perimeter measure (Section 16.2.3 ) corresponds to
minimizing the total interconnect length. Applying simulated annealing to placement, the algorithm is as follows:

1. Select logic cells for a trial interchange, usually at random.

2. Evaluate the objective function E for the new placement.
3. If D E is negative or zero, then exchange the logic cells. If D E is positive, then exchange the logic cells with a
probability of exp (D E / T).
4. Go back to step 1 for a fixed number of times, and then lower the temperature T according to a cooling schedule:

Tn +1 = 0.9 Tn, for example.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 74

 Application – Specific Integrated Circuits [ASIC]

✓ Timing-Driven Placement Methods

➢ Minimizing delay is becoming more and more important as a placement objective. There are two main approaches: net-
based and path-based. We know that we can use weights in our algorithms. The problem is to calculate the weights. One
method finds the n most critical paths (using a timing-analysis engine, possibly in the synthesis tool). The net weights
might then be the number of times each net appears in this list.
➢ The problem with this approach is that as soon as we fix (for example) the first 100 critical nets, suddenly another 200
become critical. This is rather like trying to put worms in a can. As soon as we open the lid to put one in, two more pop
out.
➢ Another method to find the net weights uses the zero-slack algorithm [ Hauge et al.,1987]. Figure 16.29 shows how this
works (all times are in nanoseconds).
➢ Figure 16.29 (a) shows a circuit with primary inputs at which we know the arrival times (this is the original definition;
some people use the term actual times ) of each signal. We also know the required times for the primary outputs the points
in time at which we want the signals to be valid.
➢ We can work forward from the primary inputs and backwards from the primary outputs to determine arrival and required
times at each input pin for each net. The difference between the required and arrival times at each input pin is the slack
time (the time we have to spare). The zero-slack algorithm adds delay to each net until the slacks are zero, as shown in
Figure 16.29 (b).
➢ The net delays can then be converted to weights or constraints in the placement. Notice that we have assumed that all the
gates on a net switch at the same time so that the net delay can be placed at the output of the gate driving the net, rather a
poor timing model, but the best we can use without any routing information.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 75

 Application – Specific Integrated Circuits [ASIC]
FIGURE 16.29 The zero-slack
algorithm.
(a) The circuit with no net delays.
(b) The zero-slack algorithm adds
net delays (at the outputs of
each gate, equivalent to
increasing the gate delay) to
reduce the slack times to zero.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 76

 Application – Specific Integrated Circuits [ASIC]

✓ Physical Design Flow

Historically, placement was included with routing as a single tool (the term P&R is often used for place and route). Because interconnect
delay now dominates gate delay, the trend is to include placement within a floorplanning tool and use a separate router. Figure 16.31 shows a
design flow using synthesis and a floor planning tool that includes placement. This flow consists of the following steps:
1. Design entry. The input is a logical description with no physical information.
2. Synthesis. The initial synthesis contains little or no information on anyinterconnect loading. The output of the synthesis tool
(typically an EDIF netlist) is the input to the floorplanner.
3. Initial floorplan. From the initial floorplan interblock capacitances are input to the synthesis tool as load constraints, and intrablock
capacitances are input as wire-load tables.
4. Synthesis with load constraints. At this point, the synthesis tool is able to resynthesize the logic based on estimates of the
interconnect capacitance each gate is driving. The synthesis tool produces a forward annotation file to constrain path delays in the
placement step.
5. Timing-driven placement. After placement using constraints from the synthesis tool, the location of every logic cell on the chip is
fixed and accurate estimates of interconnect delay can be passed back to the synthesis tool.
6. Synthesis with in-place optimization (IPO). The synthesis tool changes the drive strength of gates based on the accurate
interconnect delay estimates from the floorplanner without altering the netlist structure.
7. Detailed placement. The placement information is ready to be input to the routing step.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 77
 Application – Specific Integrated Circuits [ASIC]

FIGURE 16.31 Timing-driven

floorplanning and placement

design flow.
Compare with Figure 15.1 on p.
806.

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 78

 Application – Specific Integrated Circuits [ASIC]

Questions
1. Discuss the various steps involved in the floorplanning with a neat diagram.
2. Discuss goals and objectives of Floorplanning.
3. Discuss goals and objectives of placement.
4. Illustrate the Input Output padding or I/O and Power planning along with clock lanning in the floorplanning with
neat diagram.
5. Explain the following:
i. Power planning
ii. Clock planning
6. Explain the concept of measurement of delay in floor planning.
7. With example, explain a floorplanning tools.

Questions
1. Discuss wire length Estimation and its types.
2. Enumerate the placement algorithm and its two classes in detail.
3. Explain the eigenvalue algorithm for cell placement in ASIC Design.
4. Discuss Min-cut algorithms for cell placement in ASIC Design.
5. Explain placement using simulated annealing.
6. Explain the Iterative Placement Improvement for cell placement Design.
7. Explain the Timing driven placement method.
8. Explain the physical Design Flow with respect to placement.
Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 79
 Application – Specific Integrated Circuits [ASIC]

THANK YOU…☺

Hemanth T S Assistant Professor, Dept. of E&CE, AIET, Moodbidri. 80