Application – Specific Integrated Circuits [ASIC]

Unit III
Low-Level Design Entry: Schematic entry: Hierarchical design, The cell library,
Names, Schematic Icons & Symbols, Nets, Schematic
Entry for ASICs, Connections, vectored instances &
buses, Edit in place, attributes, Netlist screener.
ASIC Construction: Physical Design, CAD Tools, System partitioning, Estimating
ASIC size. Partitioning: Goals and objectives, Constructive
Partitioning, Iterative Partitioning Improvement, KL, FM and
Look Ahead algorithms.
(05+05) Hrs

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

 Application – Specific Integrated Circuits [ASIC]

Introduction: Low-Level Design Entry: Schematic Entry

• The purpose of design entry is to describe a microelectronic system to a set of Electronic Design
Automation (EDA) tools. Electronic systems were, and many still are, constructed from off-the-shelf
components, such as TTL ICs.
• Design entry for these systems now usually consists of drawing a picture, a schematic. The schematic
illustrates the connection of all components, representing the internal connectivity of an ASIC. This type of
design-entry process is called schematic entry, or schematic capture. A circuit schematic describes an ASIC in the
same way an architect’s plan describes a building.
• The circuit schematic is a picture, an easy format for us to understand and use, but computers need to work
with an ASCII or binary version of the schematic that we call a netlist. The output of a schematic-entry tool
is thus a netlist file that contains a description of all the components in a design and their interconnections.
• Not all the design information may be conveyed in a circuit schematic or netlist, because not all of the
functions of an ASIC are described by the connectivity information. For example, suppose we use a
programmable ASIC for some random logic functions.
• Part of the ASIC might be designed using a text language. In this case, the design entry also includes writing
the code. What if an ASIC in our system contains a programmable memory (PROM)? Is the PROM microcode, the
'1's and '0's, part of design entry? The operation of our system is certainly dependent on the correct programming of
the PROM.

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

 Application – Specific Integrated Circuits [ASIC]

• So perhaps the PROM code ought to be considered part of design entry.

• On the other hand, nobody would consider the operating system code that is loaded into RAM
on an ASIC to be a part of the design entry.
• Obviously, then, there are several different forms of design entry. In each case, it is important to
make sure that you have completely specified the system—not only so that it can be correctly
constructed, but so that someone else can understand how the system is put together. Design
entry is thus an important part of documentation.
• Until recently, most ASIC design entry used schematic entry. As ASICs have become more
complex, other design-entry methods are becoming common. Alternative design-entry methods can
use graphical methods, such as a schematic, or text files, such as a programming language.
• Using a Hardware Description Language (HDL) for design entry allows us to generate netlists
directly using logic synthesis.

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

 Application – Specific Integrated Circuits [ASIC]
Schematic Entry
• Schematic entry is the most common method of design entry for ASICs and is likely to be useful in one form
or another for some time. HDLs are replacing conventional gate-level schematic entry, but new graphical
tools based on schematic entry are now being used to create large amounts of HDL code. Circuit schematics are
drawn on schematic sheets.
• Standard schematic sheet sizes (Table 9.1) are ANSI A–E (more common in the United States) and
ISO A4–A0 (more common in Europe).
• Usually, a frame or border is drawn around the schematic containing boxes that list the name and number of
the schematic page, the designer, the date of the drawing, and a list of any modifications or changes

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

 Application – Specific Integrated Circuits [ASIC]
• Figure shows the “spades” and “shovels” the recognized symbols for AND, NAND, OR, and
NOR gates. One of the problems with these recommendations is that the corner points of the shapes
do not always lie on a grid point (using a reasonable grid size).

FIGURE: IEEE-recommended dimensions and their construction for logic-gate symbols. (a) NAND gate
(b) exclusive-OR gate (an OR gate is a subset).
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 5
 Application – Specific Integrated Circuits [ASIC]
• Figure shows some pictorial definitions of objects you can use in a simple schematic. We shall
discuss the different types of objects that might appear in an ASIC schematic first and then discuss
the different types of connections.

FIGURE: Terms used in circuit schematics.

• Schematic-entry tools for ASIC design are similar to those for printed-circuit board (PCB) design. The basic
object on a PCB schematic is a component or device —a TTL IC or resistor, for example. There may be
several hundred components on a typical PCB. If we think of a logic gate on an ASIC as being equivalent to a
component on a PCB, then a large ASIC contains hundreds of thousands of components. We can normally
draw every component on a few schematic sheets for a PCB, but drawing every component on an ASIC
schematic is impractical.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 6
 Application – Specific Integrated Circuits [ASIC]

Hierarchical Design
• Hierarchy reduces the size and complexity of a schematic. Suppose a building has 10 floors and
contains several hundred offices but only three different basic office plans.
• Furthermore, suppose each of the floors above the ground floor that contains the lobby is identical.
Then the plans for the whole building need only show detailed plans for the ground floor and one
of the upper floors.
• The plans for the upper floor need only show the locations of each office and the office type. We
can then use a separate set of three detailed plans for each of the different office types. All these
different plans together form a nested structure that is a hierarchical design.
• The plan for the whole building is the top-level plan. The plans for the individual offices are at
the lowest level.
• To clarify the relationship between different levels of hierarchy, we say that a sub-schematic (an
office) is a child of the parent schematic (the floor containing offices).
• An electrical schematic can contain sub-schematics. The sub-schematic, in turn, may contain other
sub-schematics. The figure illustrates the principles of schematic hierarchical design.

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

 Application – Specific Integrated Circuits [ASIC]

• The alternative to hierarchical design is to draw all of the ASIC components on one giant schematic, with no
hierarchy, in a flat design.

FIGURE: Schematic example

showing hierarchical design.
(a) The schematic of a half-
adder, the sub- schematic of
cell HADD.
(b) A schematic symbol for
the half adder.
(c) A schematic that uses the
half- adder cell.
(d) The hierarchy of cell
HADD.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 8
 Application – Specific Integrated Circuits [ASIC]
THE CELL LIBRARY
• Components in an ASIC schematic are chosen from a library of cells.
• Library elements for all types of ASICs are sometimes also known as modules .
• Unfortunately the term module will have a very specific meaning when we come to discuss hardware
description languages.
• To avoid any chance of confusion, here we use the term cell to mean either a cell, a module, a macro, or
a book from an ASIC library.
• Library cells are equivalent to the offices in our office building. Most ASIC companies provide a schematic
library of primitive gates to be used for schematic entry.
• The first problem with ASIC schematic libraries is that there are no naming conventions. For example, a
primitive two-input NAND gate in a Xilinx FPGA library does not have the same name as the two-input
NAND gate in an LSI Logic gate-array library.
• This means that you cannot take a schematic that you used to create a prototype product using a Xilinx FPGA
and use that schematic to create an LSI Logic gate array for production.
• As soon as you start entering a schematic using a library from an ASIC vendor, you are, to some extent,
making a commitment to use that vendor’s ASIC. Most ASIC designers are much happier maintaining a large
degree of vendor independence.

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

 Application – Specific Integrated Circuits [ASIC]

• A Second problem with ASIC schematic libraries is that there are no standards for cell behavior.
• For example, a two-input MUX in an Actel library operates so that the input labeled A is selected when the MUX select
input S = '0'. A two-input MUX in a VLSI Technology library operates in the reverse fashion, so that the input labeled B is
selected when S = '0’.
• These types of differences can cause hard-to-find problems when trying to convert a schematic from one vendor to another
by hand.
• These problems make changing or retargeting schematics from one vendor to another difficult. This process is sometimes
known as porting a design.
• Library cells that represent basic logic gates, such as a NAND gate, are known as primitive cells, usually referred to just
as cells.
• In a hierarchical ASIC design, a cell may be a NAND gate, a flip-flop, a multiplier, or even a microprocessor, for example.
• To use the office building analogy again, each of the three basic office types is a primitive cell. However, the plan for the
second floor is also a cell. The second-floor cell is a subschematic of the schematic for the whole building.
• There are two types of macros for MGAs and programmable ASICs. The most common type of macro is a hard macro
that includes placement information. A hard macro can change in position and orientation, but the relative location of the
transistors, other layout, and wiring inside the macro is fixed.
• A soft macro contains only connection information (between transistors for a gate array or between logic cells for a
programmable ASIC). Thus the placement and wiring for a soft macro can vary. This means that the timing parameters for
a soft macro can only be determined after you complete the place-and-route step. For this reason, the basic library
elements for MGAs and programmable ASICs, such as NAND gates, flip-flops, and so on, are hard macros.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 10
 Application – Specific Integrated Circuits [ASIC]

For your reference

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

 Application – Specific Integrated Circuits [ASIC]

NAMES
• Each of the cells, primitive or not, that you place on an ASIC schematic has a cell name .
• Each use of a cell is a different instance of that cell, and we give each instance a unique instance name .
• A cell instance is somewhere between a copy and a reference to a cell in a library.
• An analogy would be the pictures of hamburgers on the wall in a fast-food restaurant. The pictures are
somewhere between a copy and a reference to a real hamburger.
• We represent each cell instance by a picture or icon , also known as a symbol.
• We can represent primitive cells, such as NAND and NOR gates, with familiar icons that look like spades
and shovels.
• Some schematic editors offer the option of switching between these familiar icons and using the rectangular
IEEE standard symbols for logic gates. Unfortunately the term icon is also often used to refer to any of the
pictures on a schematic, including those that represent subschematics.
• There is no accepted way to differentiate between an icon that represents a primitive cell and one that
represents a subschematic that may be in turn a collection of primitive cells.
• In fact, there is usually no easy way to tell by looking at a schematic which icons represent primitive cells and
which represent subschematics.

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

 Application – Specific Integrated Circuits [ASIC]

SCHEMATIC ICONS AND SYMBOLS

• Most schematic-entry programs allow the designer to draw special or custom icons. In addition, the schematic
entry tool will also usually create an icon automatically for a subschematic that is used in a higher-level
schematic. This is a derived icon, or derived symbol. The external connections of the subschematic are
automatically attached to the icon, usually a rectangle.
• Figure 9.4 (c) shows what a derived icon for a cell, DLAT, might look like (we could also have drawn this by
hand). The subschematic for DLAT is shown in Figure 9.4 (b). We say that the inverter with the instance name
inv1 in the subschematic is a subcell (or submodule) of the cell DLAT. Alternatively, we say that cell instance
inv1 is a child of the cell DLAT, and cell DLAT is a parent of cell instance inv1.

FIGURE 9.4 A cell and its subschematic. (a) A schematic library containing icons for the primitive cells. (b) A
subschematic for a cell, DLAT, showing the instance names for the primitive cells. (c) A symbol for cell DLAT.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 13
 Application – Specific Integrated Circuits [ASIC]

• Figure 9.5 (a) shows a more complex subschematic for a 4-bit latch. Each primitive cell instance in this
schematic must have a unique name. This can get very tiresome for large circuits. Instead of creating
complex, but repetitive, subschematics for complex cells we can use hierarchy.

FIGURE 9.5 A 4-bit latch:

(a) drawn as a flat schematic
from gate-level primitives,
(b) drawn as four instances of
the cell symbol DLAT,
(c) drawn using a vectored
instance of the DLAT cell
symbol with cardinality of 4,
(d) drawn using a new cell
symbol with the cell name Four
Bit.

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

 Application – Specific Integrated Circuits [ASIC]

• Figure 9.5 (b) shows a hierarchical subschematic for a cell Four Bit, which in turn uses four instances of the
cell DLAT.
• The four instances of DLAT in Figure 9.5 (b) have different instance names: L1, L2, L3, and L4.
• Notice that we cannot use just one name for the four instances of DLAT to indicate that they are all the same
cell.
• If we did, we could not differentiate between L1 and L2, for example. The vertical row of instances in Figure
9.5 (b) looks like a vector of elements. Figure 9.5 (c) shows a vectored instance representing four copies of the
DLAT cell. We say the cardinality of this instance is 4.
• Tools normally use bold lines or some other distinguishing feature to represent a vectored instance. The
cardinality information is often shown as a vector.
• Thus L[1:4] represents four instances: L[1], L[2], L[3], L[4]. This is convenient because now we can see that
all subcells are identical copies of L, but we have a unique name for each.
• Finally, as shown in Figure 9.5 (d), we can create a new symbol for the 4-bit latch, FourBit.
• The symbol for FourBit has a 4-bit wide input bus for the four D inputs, and a 4-bit wide output bus for the
four Q outputs.
• The subschematic for FourBit could be either Figure 9.5 (a), (b), or (c) (though the exact naming of the inputs
and outputs and their attachment to the buses may be different in each case).

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

 Application – Specific Integrated Circuits [ASIC]

NETS
The schematics shown in Figure 9.4 contain both local nets and external nets. An example of a local
net in Figure 9.4 (b) is n1, the connection between the output terminal of the AND cell and1 to the OR cell
or1. When the four copies of this circuit are placed in the parent cell FourBit in Figure 9.5 (d), four copies of
net n1 are created. Since the four nets named n1 are not actually electrically connected, even though they have
the same name at the lowest hierarchical level, we must somehow find a way to uniquely identify each net.
The usual convention for naming nets in a hierarchical schematic uses the parent cell instance name as
a prefix to the local net name. A special character (':' '/' '$’ '#' for example) that is not allowed to appear in
names is used as a delimiter to separate the net name from the cell instance name. Supposing that we drew the
subschematic for cell FourBit as shown in Figure 9.5 (b), the four different nets labeled n1 might then
become:
FourBit .L1:n1 FourBit .L2:n1 FourBit .L3:n1 FourBit .L4:n1
This naming is usually done automatically by the schematic-entry tool. The schematic DLAT also
contains three external nets: D, EN, and Q. The terminals on the symbol DLAT connect these nets to other
nets in the hierarchical level above. For example, the signal Trigger:flag in Figure 9.4 (c) is also
[Link]:Q. Each schematic tool handles this situation differently, and life becomes especially difficult
when we need to refer to these nodes from a simulator outside the schematic tool, for example. HDLs such as
VHDL and Verilog have a very precise and well-defined standard for naming nets in hierarchical structures.

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

 Application – Specific Integrated Circuits [ASIC]

SCHEMATIC ENTRY FOR ASICS AND PCBS

A symbol on a schematic may represent a component, which may contain component parts. You are
more likely to come across the use of components in a PCB schematic. A component is slightly different from
an ASIC library cell. A simple example of a component would be a TTL gate, an SN74LS00N, that contains
four 2-input NAND gates. We call an SN74LS00N a component, and each of the individual NAND gates
inside is a component part. Another common example of a component would be a resistor pack single package
that contains several identical resistors.
In PCB design language, a component label or name is a reference designator. A reference designator
is a unique name attribute, such as R99, attached to each component. A reference designator, such as R99, has
two pieces: an alpha prefix R and a numerical suffix 99. To understand the difference between reference
designators and instance names, we need to look at the special requirements of PCB design.
PCBs usually contain packaged ASICs and other ICs that have pins that are soldered to a board. For
rectangular, dual-in-line (DIP) packages, the pins are numbered counterclockwise from the upper-left corner
looking down on the package.
IC symbols have a pin number for each part in the package. For example, the TTL 74174 hex D flip-
flop with clear contains six parts: six identical D flip-flops. The IC symbol representing this device has six Pin
Number attribute entries for the D input corresponding to the six possible input pins. They are pins 3, 4, 6, 11,
13, and 14.

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

 Application – Specific Integrated Circuits [ASIC]

There is no process in ASIC design directly equivalent to the process of part assignment
described above, and thus no need to use reference designators. The reference-designator naming
convention quickly becomes unwieldy if there are a large number of components in a design. For
example, how will we find a NAND gate named X3146 in an ASIC schematic with 100 pages?
Instead, for ASICs, we use a naming scheme based on hierarchy.
In large hierarchical ASIC designs, it is difficult to provide a unique reference designator to each
element. For this reason, ASIC designs use instance names to identify the individual components.
Meaningful names can be assigned to low-level components and also the symbols that represent
hierarchy. We derive the component names by joining all of the higher-level cell names together. A
special character is used as a delimiter and separates each level.

Examples of hierarchical instance names are:

[Link].and01

MotherBoard:Cache:RAM4:ReadBit4:Inverter2

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

 Application – Specific Integrated Circuits [ASIC]
CONNECTIONS
• Cell instances have terminals that are the inputs and outputs of the cell. Terminals are also
known as pins, connectors or signals.
• The term pin is widely used, but we shall try to use terminal, and reserve the term pin for the metal
leads on an ASIC package. The term pin is used in schematic entry and routing programs that are
primarily intended for PCB design.

FIGURE 9.6 An example of the use of a bus to simplify a schematic. (a) An address decoder without using a bus. (b) A
bus with bus rippers simplifies the schematic and reduces the possibility of making a mistake in creating and reading the
schematic.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 19
 Application – Specific Integrated Circuits [ASIC]

• Electrical connections between cell instances use wire segments or nets.

• We can group closely related nets, such as the 32 bits of a 32-bit digital word, together into a bus or
into buses (not busses).
• If signals on a bus are not closely related, we usually use the term bundle or array instead of bus. An
example of a bundle might be a bus for a SCSI disk system, containing not only data bits but
handshake and control signals too.
• Figure 9.6 shows an example of a bus in a schematic. If we need to access individual nets in a
bus or a bundle, we use a breakout (also known as a ripper, an EDIF term, or extractor).
• For example, a breakout is used to access bits 0–7 of a 32-bit bus. If we need to rearrange bits on a
bus, some schematic editors offer something called a swizzle.
• For example, we might use a swizzle to reorder the bits on an 8-bit bus so that the MSB becomes the
LSB and so on down to the LSB, which now becomes the MSB. Swizzles can be useful. For example,
we can multiply or divide a number by 2 by swizzling all the bits up or down one place on a bus.

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

 Application – Specific Integrated Circuits [ASIC]
VECTORED INSTANCES AND BUSES
• So far, the naming conventions are fairly
standard and easy to follow. However,
when we start to use vectored instances and
buses (as is now common in large ASICs),
there are potential areas of difficulty and
confusion.
• Figure 9.7 (a) shows a schematic for a 16-
bit latch that uses multiple copies of the
cell FourBit. The buses are labeled with the
appropriate bits. Figure 9.7 (b) shows a
new cell symbol for the 16-bit latch with
16-bit wide buses for the inputs, D, and
outputs, Q.

• FIGURE 9.7 A 16-bit latch:

(a) drawn as four instances of cell FourBit;
(b) drawn as a cell named SixteenBit;
(c) drawn as four multiple instances of cell FourBit.

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

 Application – Specific Integrated Circuits [ASIC]

• Figure 9.7 (c) shows an alternative representation of the 16-bit latch using a vectored instance of
FourBit with cardinality 4.
• Suppose we wish to make a connection to expressly one bit, D1 (we have used D1 as the first bit
rather than the more conventional D0, so that numbering is easier to follow).
• We also wish to make a connection to bits D9-D12, represented as D[9:12]. We do this using a
bus ripper. Now we have the rather awkward situation of bus naming shown in Figure 9.7 (c).
• Problems arise when we have “buses of buses” because the numbers for the bus widths do not
match on either side of a ripper. For this reason, it is best to use the single-bus approach shown
in Figure 9.7 (b) rather than the vectored-bus approach of Figure 9.7 (c).

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

 Application – Specific Integrated Circuits [ASIC]
EDIT-IN-PLACE
• Figure 9.7 (b) shows a symbol SixteenBit,
which uses the sub schematic shown in
Figure 9.7 (a) containing four copies of
FourBit, named NB1, NB2, NB3, and NB4
(the NB stands for nibble, which is half of a
word; a nibble is 4 bits for 8-bit words).
• Suppose we use the schematic-entry
program to edit the subcell NB1. L1, which
is an instance of DLAT inside NB1.
Perhaps we wish to change the D latch to a
D latch with a reset, for example. If the
schematic editor supports edit-in-place.
• We can edit a cell instance directly. After
we edit the cell, the program updates all the • FIGURE 9.7 A 16-bit latch:
DLAT subcells in the currently loaded cell (a) drawn as four instances of cell FourBit;
(b) drawn as a cell named SixteenBit;
to reflect the changes made. (c) drawn as four multiple instances of cell FourBit.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 23
 Application – Specific Integrated Circuits [ASIC]

• Using edit-in-place we can edit the cell Floor. Suppose we change some of the cell instances of cell
name NoWindowOffice to instances of cell name WindowOffice. When we finish editing and save
the cell Floor , we have effectively changed all of the floors that contain instances of this cell.
• Instead of editing a cell in place, you may really want to edit just one instance of a cell and leave
any other instances unchanged. In this case you must create a new cell with a new symbol and new,
unique cell name. It might also be wise to change the instance name of the new cell to avoid any
confusion.
• For example, we might change the third-floor plan of our office to be different from the other upper
floors. Suppose the third floor is now an instance of cell name FloorVIP instead of Floor. We could
continue to call the third-floor cell instance FloorThree , but it would be better to rename the
instance differently, FloorSpecial for example, to make it clear that it is different from all the other
floors.
• Some tools have the ability to alias nets. Aliasing creates a net name from the highest level in the
design. Local names are net names at the lowest level such as D , and Q in a flip-flop cell. These
local names are automatically replaced by the appropriate top-level names such as Clock1, or
Data2, using a dictionary. This greatly speeds tracing of signals through a design containing many
levels of hierarchy.

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

 Application – Specific Integrated Circuits [ASIC]

ATTRIBUTES
• You can attach a name, also known as an identifier or label, to a component, cell instance, net,
terminal, or connector. You can also attach an attribute, or property, which describes some aspect
of the component, cell instance, net, or connector. Each attribute has a name, and some attributes also
have values. The most common problems in working with schematics and netlists, especially when
you try to exchange schematic information between different tools, are problems in naming.
• Since cells and their contents have to be stored in a database, a cell name frequently corresponds (or
is mapped to) a filename. This then raises the problems of naming conventions including: case
sensitivity, name-collision resolution, dictionaries, handling of special characters (such as embedded
blanks or underscores), other special characters “common” (such as characters in foreign alphabets),
first-character restrictions, name-length problems (only 28 characters are permitted on an NFS
compatible filename), and so on.

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

 Application – Specific Integrated Circuits [ASIC]
NETLIST SCREENER
A surprising number of problems can be found by checking a schematic for obviously fatal errors. A
program that analyzes a schematic netlist for simple errors is sometimes called a schematic screener or netlist
screener. Errors that can be found by a netlist screener include:
• unconnected cell inputs,
• unconnected cell outputs,
• nets not driven by any cells,
• too many nets driven by one cell,
• nets driven by more than one cell.
The screener can work continuously as the designer is creating the schematic or can be run as a separate
program independently from schematic entry. Usually, the designer provides attributes that give the screener the
information necessary to perform the checks. A few of the typical attributes that schematic-entry programs use are
described next.

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

 Application – Specific Integrated Circuits [ASIC]

• A screener usually generates a list of errors together with the locations of the problem on the schematic
where appropriate. Some editors associate an identifier, or handle, to every piece of a schematic,
including comments and every net.
• Most schematic-entry programs work on a grid. The designer can control the size of the grid and
whether it is visible or not. When you place components or wires you can instruct the editor to force
your drawing to snap to grid.
• This simplifies the internal mechanics of the schematic-entry program. It also makes the transfer of
schematics between different EDA systems more manageable.
• More sophisticated options allow more complex searches, perhaps using wildcard matching. For
example, to find all three-input NAND gates (primitive cell name ND3) or three-input NOR gates
(primitive cell name NO3), you could search for cell name N*3, where * is a wildcard symbol standing
for any character.
• For large schematics it is useful to be able to generate a report on the used and unused reference
designators. An example would be:
Reference designator prefix: R
Unused reference designator numbers: 153, 154
Last used reference designator number: 180
• If you need this feature, you probably are not using enough hierarchy to simplify your design.

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

 Application – Specific Integrated Circuits [ASIC]
SCHEMANTIC-ENTRY TOOLS
• Some editors similarly offer icon edit-in-place as schematic edit-in-place for cells.
• Often, you have to toggle editing modes in the schematic-entry program to switch between editing cells and
editing cell icons.
• A schematic-entry program must keep track of when cells are edited. Normally, this is done by using a
timestamp or datestamp for each cell.
• This is a text field within the data file for each cell that holds the date and time that the cell was last
modified. When a new schematic or cell is loaded, the program needs to compare its timestamp with the
timestamps of any subcells. If any of the subcell timestamps are more recent, then the designer needs to be
alerted.
• Usually, a message appears to inform you that changes have been made to subcells since the last time the
cell currently loaded was saved. This may be what you expect, or it may be a warning that somehow a
subcell has been changed inadvertently (perhaps someone else changed it) since you last loaded that cell.
• It is exceedingly painful to move components if you have to rewire connections each time. Most schematic
editors allow you to move the components and drag any wires along with them.
• A cell library or a collection of libraries is a key part of the schematic-entry process. The ability to handle
and control these libraries is an important feature of any schematic editor. It should be easy to select
components from the library to be placed on a schematic.

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

 Application – Specific Integrated Circuits [ASIC]

• Most schematic-entry programs allow you to undo commands. This feature may be restricted
to simply undoing the last command that you entered, or may be an unlimited undo and redo,
allowing you to back up as many commands as you want in the current editing session.
• You can spend a lot of time in a schematic editor placing components and drawing the
connections between them. Features that simplify initial entry and allow modifications to be
made easily can make an enormous difference to the efficiency of the schematic-entry process.
• In large schematics it is necessary to continue large nets and signals across several pages of
schematics. Signals such as power and ground, VDD and GND, can be connected using global
nets or special connectors. Global nets allow the designer to label a net with the same name
at different places on a schematic page or on different pages without having to draw a
connection explicitly. The schematic editor treats these nets as though they were electrically
connected.
• Special connector symbols can be used for connections that cross schematic pages. An off-
page connector or multipage connector is a special symbol that will show and label a
connection to different schematic pages. More sophisticated editors can automatically label
these connectors with the page numbers of the destination connectors.

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

 Application – Specific Integrated Circuits [ASIC]

Back-Annotation
➢ After you enter a schematic, you simulate the design to make sure it works as expected.
➢ This completes the logical design. Next you move to ASIC physical design and complete the layout.
➢ Only after you complete the layout do you know the parasitic capacitance and therefore the delay associated
with the interconnect.
➢ This postroute delay information must be returned to the schematic in a process known as back-annotation.
➢ Then you can complete a final, postlayout simulation to make sure that the specifications for the ASIC are met.

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

 Application – Specific Integrated Circuits [ASIC]

ASIC Construction
• A town planner works out the number, types, and sizes of buildings in a development project.
• An architect designs each building, including the arrangement of the rooms in each building.
• Then a builder carries out the construction according to the architect’s drawings.
• Electrical wiring is one of the last steps in the construction of each building.
• The physical design of ASICs is normally divided into
- System Partitioning
- Floorplanning
- Placement
- Routing
• A microelectronic system is the town, and the ASICs are the buildings.
• System partitioning corresponds to town planning, ASIC floorplanning is the architect’s job,
placement is done by the builder, and the routing is done by the electrician. We shall design most,
but not all, ASICs using these design steps.

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

 Application – Specific Integrated Circuits [ASIC]

Physical Design
• Figure shows part of the design flow, the physical design
steps, for an ASIC (omitting simulation, test, and other
logical design steps that have already been covered).
• Some of the steps in Figure might be performed in a different
order from that shown. For example, we might,
depending on the size of the system, perform system
partitioning before we do any design entry or synthesis.
There may be some iteration between the different steps, too.
• FIGURE: Part of an ASIC design flow showing the system
partitioning, floorplanning, placement, and routing steps.
• These steps may be performed in a slightly different order,
iterated or omitted, depending on the type and size of the
system and its ASICs. As the focus shifts from logic to
interconnect, floorplanning assumes an increasingly important
role.
• Each of the steps shown in the figure must be performed, and
each depends on the previous step. However, the trend is
toward completing these steps in a parallel fashion and iterating,
rather than in a sequential manner.

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

 Application – Specific Integrated Circuits [ASIC]
• We must first apply system partitioning to divide a microelectronics system into separate ASICs.
• In floorplanning, we estimate sizes and set the initial relative locations of the various blocks in our ASIC
(sometimes we also call this chip planning). At the same time, we allocate space for the clock and power wiring and decide
on the location of the I/O and power pads.
• Placement defines the location of the logic cells within the flexible blocks and sets aside space for the
interconnect to each logic cell. Placement for a gate-array or standard-cell design assigns each logic cell to a position in
a row.
• For an FPGA, placement chooses which of the fixed logic resources on the chip are used for which logic cells.
Floorplanning and placement are closely related and are sometimes combined in a single CAD tool.
• Routing makes the connections between logic cells. Routing is a hard problem by itself and is normally split into two
distinct steps, called global and local routing.
• Global routing determines where the interconnections between the placed logic cells and blocks will be situated.
Only the routes to be used by the interconnections are decided in this step, not the actual locations of the interconnections
within the wiring areas.
• Global routing is sometimes called loose routing for this reason.
• Local routing joins the logic cells with interconnections. Information on which interconnection areas to use comes from
the global router.
• Only at his stage of layout do we finally decide on the width, mask layer, and exact location of the interconnections. Local
routing is also known as detailed routing
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 33
 Application – Specific Integrated Circuits [ASIC]

For your Reference

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

 Application – Specific Integrated Circuits [ASIC]

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

 Application – Specific Integrated Circuits [ASIC]

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

 Application – Specific Integrated Circuits [ASIC]

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

 Application – Specific Integrated Circuits [ASIC]

CAD Tools
• To develop a CAD tool, it is necessary to convert each of the physical design steps to a problem with
well-defined goals and objectives. The goals for each physical design step are the things we must
achieve.
• The objectives for each step are things we would like to meet on the way to achieving the goals.
Some examples of goals and objectives for each of the ASIC physical design steps are as follows:
✓System partitioning:
- Goal. Partition a system into multiple ASICs.
- Objectives. Minimize the number of external connections between the ASICs. Keep each ASIC
smaller than a maximum size.
✓Floorplanning:
- Goal. Calculate the sizes of all the blocks and assign them to locations.
- Objective. Keep the highly connected blocks physically close together.
✓Placement:
- Goal. Assign the interconnect areas and the location of all the logic cells within the flexible blocks.
- Objectives. Minimize the ASIC area and the interconnect density.

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

 Application – Specific Integrated Circuits [ASIC]

✓Global routing:
- Goal. Determine the location of all the interconnect.
- Objective. Minimize the total interconnect area used.
✓Detailed routing:
- Goal. Completely route all the interconnect on the chip.
- Objective. Minimize the total interconnect length used.
• There is no magic recipe involved in the choice of the ASIC physical design steps. These
steps have been chosen simply because, as tools and techniques have developed historically,
these steps proved to be the easiest way to split up the larger problem of ASIC physical
design.
• The boundaries between the steps are not cast in stone. For example, floorplanning and
placement are often thought of as one step, and in some tools placement and routing are
performed together

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

 Application – Specific Integrated Circuits [ASIC]
Methods and Algorithms
• A CAD tool needs methods or algorithms to generate a solution to each problem using a reasonable amount of
computer time.
• Often, there is no best solution possible to a particular problem, and the tools must use heuristic algorithms,
or rules of thumb, to try and find a good solution. The term algorithm is usually reserved for a method
that always gives a solution.
• We need to know how practical any algorithm is. We say the complexity of an algorithm is O (f (n)) (read as
order f (n)) if there are constants k and n 0 so that the running time of the algorithm
T (n is less than k f (n) for all n > n 0 [Sedgewick, 1988].
• Here n is a measure of the size of the problem (number of transistors, number of wires, and so on). In ASIC
design, n is usually very large. We have to be careful, though.
• The notation does not specify the units of time. An algorithm that is O (n 2) nanoseconds might be better
than an algorithm that is O (n) seconds, for quite large values of n.
• The notation O (n) refers to an upper limit on the running time of the algorithm. A practical example may
take less running time—it is just that we cannot prove it. We also have to be careful of the constants k and n 0.
• They can hide overhead present in the implementation, and may be large enough to mask the dependence
on n, up to large values of n.

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

 Application – Specific Integrated Circuits [ASIC]
The function f (n) is usually one of the following kinds:
✓ f (n) = constant. The algorithm is constant in time. In this case, the steps of the algorithm are repeated once
or just a few times. It would be nice if our algorithms had this property, but it does not usually happen
in ASIC design.
✓ f (n) = log n. The algorithm is logarithmic in time. This usually happens when a big problem is
(possibly recursively) transformed into a smaller one.
✓ f (n) = n. The algorithm is linear in time. This is a good situation for an ASIC algorithm that
works with n objects.
✓ f (n) = n log n. This type of algorithm arises when a large problem is split into a number of smaller
problems, each solved independently.
✓ f (n) = n 2. The algorithm is quadratic in time and usually only practical for small ASIC problems.
• If the time it takes to solve a problem increases with the size of the problem at a rate that is polynomial but
faster than quadratic (or worse in an exponential fashion), it is usually not appropriate for ASIC design.
• Even after subdividing the ASIC physical design problem into smaller steps, each of the steps still results in
problems that are hard to solve automatically.
• In fact, each of the ASIC physical design steps, in general, belongs to a class of mathematical problems known as
NP-complete problems. This means that it is unlikely we can find an algorithm to solve the problem exactly in
polynomial time.

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

 Application – Specific Integrated Circuits [ASIC]

• Suppose we find a practical method to solve our problem, even if we can find a solution we now
have a dilemma.
• How shall we know if we have a good solution if, because the problem is NP-complete, we cannot
find the optimum or best solution to which to compare it? We need to know how close we are to the
optimum solution to a problem, even if that optimum solution cannot be found exactly.
• We need to make a quantitative measurement of the quality of the solution that we are able to find.
• Often, we combine several parameters or metrics that measure our goals and objectives into a
measurement function or objective function. If we are minimizing the measurement function, it is
a cost function. If we are maximizing the measurement function, we call the function a gain
function (sometimes just gain).
• Now we are ready to solve each of the ASIC physical design steps with the following items in hand:
a set of goals and objectives, a way to measure the goals and objectives, and an algorithm or method
to find a solution that meets the goals and objectives.
• As designers attempt to achieve a desired ASIC performance, they make a continuous trade-off
between speed, area, power, and several other factors.
• Presently, CAD tools are not smart enough to be able to do this alone. In fact, current CAD tools are
only capable of finding a solution subject to a few, very simple, objectives.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 42
 Application – Specific Integrated Circuits [ASIC]
System Partitioning
• Microelectronic systems typically consist of many functional blocks. If a functional block is too large to fit
in one ASIC, we may have to split, or partition, the function into pieces using goals and objectives that we
need to specify.
• For example, we might want to minimise the number of pins for each ASIC to minimize package cost. We
can use CAD tools to help us with this type of system partitioning.
• Figure 15.2 shows the system diagram of the Sun Microsystems SPARCstation 1. The system is partitioned
as follows: the numbers refer to the labels in Figure 15.2.
✓ Nine custom ASICs (1–9)
✓ Memory subsystems (SIMMs, single-in-line memory modules): CPU cache (10), RAM (11), memory cache
(12, 13)
✓ Six ASSPs (application-specific standard products) for I/O (14–19)
✓ An ASSP for time of day (20)
✓ An EPROM (21)
✓ Video memory subsystem (22)
✓ One analog/digital ASSP DAC (digital-to-analog converter) (23)

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

 Application – Specific Integrated Circuits [ASIC]

FIGURE 15.2 The Sun Microsystems

SPARCstation 1 system block diagram.
The acronyms for the various ASICs are
listed in Table 15.1.

• Table 15.1 shows the details of the nine

custom ASICs used in the SPARCstation
1. Some of the partitioning of the system
shown in Figure 15.2 is determined by
whether to use ASSPs or custom ASICs.

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

 Application – Specific Integrated Circuits [ASIC]
• Some of these design
decisions are based on
intangible issues: time to
market, previous experience
with a technology, and the
ability to reuse part of a
design from a previous
product.
• No CAD tools can help with
such decisions. The goals and
objectives are too poorly
defined, and finding a way
to measure these factors is
very difficult.

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

 Application – Specific Integrated Circuits [ASIC]
• Table 15.2 shows the partitioning of the SPARCstation 10 so you can compare it to the SPARCstation 1.
• Notice that the gate counts of nearly all of the SPARCstation 10 ASICs have increased by a factor of 10, but the pin counts
have increased by a smaller factor.

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

 Application – Specific Integrated Circuits [ASIC]

Estimate ASIC size

• Table 15.3 shows some useful numbers for estimating ASIC die size. Suppose we wish to estimate the die size
of a 40 k-gate ASIC in a 0.35 mm gate array, three-level metal process with 166 I/O pads. For this ASIC the
minimum feature size is 0.35 mm.
• Thus l (one-half the minimum feature size) = 0.35 mm/2 = 0.175 mm. Using our data and Table 15.3 , we can
derive the following information. We know that 0.35 m m standard- cell density is roughly 5 ¥ 10–4 gate/ l2 .
From this we can calculate the gate density for a 0.35 m m gate array:
gate density = 0.35 mm standard-cell density ¥ (0.8 to 0.9)
= 4 ¥ 104 to 4.5 ¥ 104 gate/ l2. (15.1)
This gives the core size (logic and routing only) as
(4 ¥ 104 gates/gate density) ¥ routing factor ¥ (1/gate-array utilization)
= 4 ¥ 104/ (4 ¥ 104 to 4.5 ¥ 104) ¥ (1 to 2) ¥ 1/ (0.8 to 0.9) = 104 to 2.5 ¥ 108 12 = 4840 to 11,900 mil2.
We shall need to add (0.175/0.5) ¥ 2 ¥ (15 to 20) = 10.5 to 21 mil (per side) for the pad heights (we included the
effects of scaling in this calculation). With a pad pitch of 5 mil and roughly 166/4 = 42 I/Os per side (not counting
any power pads), we need a die at least 5 ¥ 42 = 210 mil on a side for the I/Os. Thus, the die size must be at least 210
¥ 210 = 4.4 ¥ 104 mil2 to fit 166 I/Os. die area only 1.19 ¥ 104 /(4.4 ¥ 104) = 27 % (at most) is used by the core logic.
This is a severely pad-limited design and we need to rethink the partitioning of this system.

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

 Application – Specific Integrated Circuits [ASIC]

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

 Application – Specific Integrated Circuits [ASIC]

FPGA Partitioning
• Many different issues have to be considered when partitioning a complex system into custom ASICs.
• There are no commercial tools that can help us with all of these issues—a spreadsheet is the best tool in this
case. Things are a little easier if we limit ourselves to partitioning a group of logic cells into FPGAs—and
restrict the FPGAs to be all of the same type.
ATM (Asynchronous Transfer Mode) Simulator
- We shall examine a hardware simulator for Asynchronous Transfer Mode ( ATM ).
- ATM is a signaling protocol for many different types of traffic, including constant bit rates (voice signals) as
well as variable bit rates (compressed video).
- The ATM Connection Simulator is a card that is connected to a computer. Under computer control the card
monitors and corrupts the ATM signals to simulate the effects of real networks.
- An example would be to test different video compression algorithms. Compressed video is very bursty (brief
periods of very high activity), has very strict delay constraints, and is susceptible to errors.
- ATM is based on ATM cells (packets). Each ATM cell has 53 bytes: a 5-byte header and a 48-byte
payload; Figure 15.4 shows the format of the ATM packet. The ATM Connection Simulator looks at the entire
header as an address

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

 Application – Specific Integrated Circuits [ASIC]

FIGURE 15.4 The asynchronous transfer mode (ATM) cell format.

The ATM protocol uses 53-byte cells or packets of information with a data payload and header information
for routing and error control
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 50
 Application – Specific Integrated Circuits [ASIC]

• Figure 15.5 shows the system block diagram of the ATM simulator designed by Craig Fujikami at the
University of Hawaii. Now produced by AdTech, the simulator emulates the characteristics of a single
connection in an ATM network and models ATM traffic policing, ATM cell delays, and ATM cell errors. The
simulator is partitioned into the three major blocks, shown in Figure 15.5, and connected to an IBM-
IBM-compatible PC through an Intel 80186 controller board together with an interface board. These three blocks
are
➢ The traffic policer, which regulates the input to the simulator.
➢ The delay generator, which delays ATM cells, reorders ATM cells, and inserts ATM cells with valid ATM cell
headers.
➢ The error generator, which produces bit errors and four random variables that are needed by the other two
blocks.
The error generator performs the following operations on ATM cells:
1. Payload bit error ratio generation. The user specifies the Bernoulli probability, pBER , of the payload bit error
ratio.
2. Random-variable generation for ATM cell loss, misinsertion, reordering, and deletion.
The delay generator delays, misinserts, and reorders the target ATM cells. Finally, the traffic policer performs the
following operations:
1. Performs header screening and remapping.
2. Checks ATM cell conformance.
3. Deletes selected ATM cells.

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

 Application – Specific Integrated Circuits [ASIC]

Table 15.7 shows the partitioning of the ATM board into 12 Lattice Logic FPGAs (ispLSI 1048)
corresponding to the 12 blocks shown in Figure 15.5 . The Lattice Logic ispLSI 1048 has 48 GLBs (generic
logic blocks) on each chip. This system was partitioned by handwith difficulty.

TABLE 15.7 Partitioning of the ATM board using Lattice Logic ispLSI 1048 FPGAs.
Each FPGA contains 48 generic logic blocks (GLBs).

Chip # Size Chip # Size

1 42 GLBs 7 36 GLBs
2 64 k-bit ¥ 8 SRAM 8 22 GLBs
3 38 GLBs 9 256 k-bit ¥ 16 SRAM
4 38 GLBs 10 43 GLBs
5 42 GLBs 11 40 GLBs
6 64 k-bit ¥ 16 SRAM 12 30 GLBs

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

 Application – Specific Integrated Circuits [ASIC]

Partitioning Methods
• System partitioning requires goals and objectives, methods and algorithms to find solutions, and ways to
evaluate these solutions. We start with measuring connectivity, proceed to an example that illustrates the
concepts of system partitioning and then to the algorithms for partitioning.
• Assume that we have decided which parts of the system will use ASICs. The goal of partitioning is to divide this
part of the system so that each partition is a single ASIC. To do this we may need to take into account any or all
of the following objectives:
✓ A maximum size for each ASIC
✓ A maximum number of ASICs
✓ A maximum number of connections for each ASIC
✓ A maximum number of total connections between all ASICs
• Partitioning Methods
1. Constructive Partitioning
2. Iterative Partitioning Improvement
3. The Kernighan–Lin Algorithm
4. The Ratio-CutAlgorithm
5. The Look-ahead Algorithm
6. Simulated Annealing
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 53
 Application – Specific Integrated Circuits [ASIC]
Constructive Partitioning
• The most common constructive partitioning algorithms use seed growth or cluster growth. A simple seed-
growth algorithm for constructive partitioning consists of the following steps:
1. Start a new partition with a seed logic cell.
2. Consider all the logic cells that are not yet in a partition. Select each of these logic cells in turn.
3. Calculate a gain function, g(m) , that measures the benefit of adding logic cell m to the current partition.
One measure of gain is the number of connections between logic cell m and the current partition.
4. Add the logic cell with the highest gain g(m) to the current partition.
5. Repeat the process from step 2. If you reach the limit of logic cells in a partition, start again at step 1.
• We may choose different gain functions according to our objectives (but we have to be careful to distinguish
between connections and nets). The algorithm starts with the choice of a seed logic cell (seed module, or just
seed). The logic cell with the most nets is a good choice as the seed logic cell.
• You can also use a set of seed logic cells known as a cluster. Some people also use the term clique —borrowed
from graph theory. A clique of a graph is a subset of nodes where each pair of nodes is connected by an edge—
like your group of friends at school where everyone knows everyone else in your clique.
• In some tools you can use schematic pages (at the leaf or lowest hierarchical level) as a starting point for
partitioning. If you use a high-level design language, you can use a Verilog module (different from a circuit
module) or VHDL entity/architecture as seeds (again at the leaf level).

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

 Application – Specific Integrated Circuits [ASIC]
Iterative Partitioning Improvement
• The most common iterative improvement algorithms are based on interchange and group
migration. The process of interchanging (swapping) logic cells in an effort to improve the partition is
an interchange method. If the swap improves the partition, we accept the trial interchange; otherwise,
we select a new set of logic cells to swap.
• There is a limit to what we can achieve with a partitioning algorithm based on simple
interchange. For example, Figure 15.7 (c) shows a partitioning of the network of part a using a
constructed partitioning algorithm with logic cell C as the seed. To get from the solution shown in
part c to the solution of part b, which has a minimum number of external connections, requires a
complicated swap.
• The three pairs: D and F, J and K, C and L need to be swapped—all at the same time. It would
take a very long time to consider all possible swaps of this complexity. A simple interchange
algorithm considers only one change and rejects it immediately if it is not an improvement.
Algorithms of this type are greedy algorithms in the sense that they will accept a move only if it
provides immediate benefit.
• Such short-sightedness leads an algorithm to a local minimum from which it cannot escape. Stuck in
a valley, a greedy algorithm is not prepared to walk over a hill to see if there is a better solution in the
next valley. This type of problem occurs repeatedly in CAD algorithms.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 55
 Application – Specific Integrated Circuits [ASIC]

• Group migration consists of swapping groups of logic cells between partitions. The group
migration algorithms are better than simple interchange methods at improving a solution but
are more complex. Almost all group migration methods are based on the powerful and general
Kernighan–Lin algorithm (K–L algorithm) that partitions a graph [ Kernighan and Lin, 1970].
• The problem of dividing a graph into two pieces, minimizing the nets that are cut, is the min-
cut problem—a very important one in VLSI design. As the next section shows, the K–L
algorithm can be applied to many different problems in ASIC design.

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

 Application – Specific Integrated Circuits [ASIC]

FIGURE 15.7 Partitioning example.

(a) We wish to partition this network into three ASICs with no
more than four logic cells per ASIC.
(b) A partitioning with five external connections (nets 2, 4, 5, 6,
and 8)the minimum number.
(c) A constructed partition using logic cell C as a seed. It is
difficult to get from this local minimum, with seven external
connections (2, 3, 5, 7, 9,11,12), to the optimum solution of
b.

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

 Application – Specific Integrated Circuits [ASIC]
The Kernighan–Lin Algorithm
• Figure 15.8 illustrates some of the terms and definitions needed to describe the K–L algorithm. External
edges cross between partitions; internal edges are contained inside a partition. Consider a network with
2 m nodes (where m is an integer) each of equal size. If we assign a cost to each edge of the network graph,
we can define a cost matrix C = c ij , where c ij = c ji and c ii = 0. If all connections are equal in importance,
the elements of the cost matrix are 1 or 0, and in this special case we usually call the matrix the connectivity
matrix. Costs higher than 1 could represent the number of wires in a bus, multiple connections to a single
logic cell, or nets that we need to keep close for timing reasons.

FIGURE 15.8 Terms used by the Kernighan-Lin

partitioning algorithm.
(a) An example network graph.
(b) The connectivity matrix, C; the columns and rows are
labeled to help you see how the matrix entries
correspond to the node numbers in the graph. For
example, C 17 (column 1, row 7) equals 1 because
nodes 1 and 7 are connected. In this example, all edges
have an equal weight of 1, but in general, the edges
may have different weights.

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

 Application – Specific Integrated Circuits [ASIC]
• Suppose we already have split a network into two partitions, A and B , each with m nodes (perhaps using a
constructed partitioning). Our goal now is to swap nodes between A and B with the objective of minimizing
the number of external edges connecting the two partitions. Each external edge may be weighted by a cost, and
our objective corresponds to minimizing a cost function that we shall call the total external cost, cut cost,
or cut weight, W :

• In Figure 15.8 (a) the cut weight is 4 (all the edges have weights of 1). In order to simplify the
measurement of the change in cut weight when we interchange nodes, we need some more definitions.
First, for any node a in partition A , we define an external edge cost, which measures the connections from
node a to B ,

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

 Application – Specific Integrated Circuits [ASIC]
• For example, in Figure 15.8 (a) E 1 = 1, and E 3 = 0. Second, we define the internal edge cost to measure the
internal connections to a ,

• So, in Figure 15.8 (a), I 1 = 0, and I 3 = 2. We define the edge costs for partition B in a similar way (so E 8
= 2, and I 8 = 1). The cost difference is the difference between external edge costs and internal edge costs,

• Thus, in Figure 15.8 (a) D 1 = 1, D 3 = – 2, and D 8 = 1. Now pick any node in A , and any node in B . If
we swap these nodes, a and b, we need to measure the reduction in cut weight, which we call the gain, g .
We can express g in terms of the edge costs as follows:

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

 Application – Specific Integrated Circuits [ASIC]

• The last term accounts for the fact that a and b may be connected.
• So, in Figure 15.8 (a), if we swap nodes 1 and 6, then
g = D1 + D6 – 2 c16 = 1 + 1.
If we swap nodes 2 and 8, then
g = D2 + D8 – 2 c28 = 1 + 2 – 2.
• The K–L algorithm finds a group of node pairs to swap that increases the gain even though swapping
individual node pairs from that group might decrease the gain. First we pretend to swap all of the nodes a
pair at a time. Pretend swaps are like studying chess games when you make a series of trial moves in your
head.
• This is the algorithm: .
1. Find two nodes, a i from A , and b i from B , so that the gain from swapping them is a maximum. The gain
is
gi = D ai + D bi – 2 c aibi . (15.18)
2. Next pretend swap a i and b i even if the gain g i is zero or negative, and do not consider a i and b i
eligible for being swapped again.
3. Repeat steps 1 and 2 a total of m times until all the nodes of A and B have been pretend swapped. We are
back where we started, but we have ordered pairs of nodes in A and B according to the gain from
interchanging those pairs.

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

 Application – Specific Integrated Circuits [ASIC]

4. Now we can choose which nodes we shall actually swap. Suppose we only swap the first n pairs of nodes
that we found in the preceding process. In other words we swap nodes X = a 1 , a 2 ,…, a n from A with
nodes Y = b 1 , b 2 ,…, b n from B. The total gain would be

5. We now choose n corresponding to the maximum value of G n .

• If the maximum value of G n > 0, then we swap the sets of nodes X and Y and thus reduce the cut weight
by G n . We use this new partitioning to start the process again at the first step. If the maximum value of G n =
0, then we cannot improve the current partitioning and we stop. We have found a locally optimum solution.
• Figure 15.9 shows an example of partitioning a graph using the K–L algorithm. Each completion of steps 1
through 5 is a pass through the algorithm. Kernighan and Lin found that typically 2–4 passes were required to
reach a solution.
• The most important feature of the K–L algorithm is that we are prepared to consider moves even though they
seem to make things worse. This is like unraveling a tangled ball of string or solving a Rubik’s cube puzzle.
• Sometimes you need to make things worse so they can get better later.
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 62
 Application – Specific Integrated Circuits [ASIC]

FIGURE 15.9 Partitioning a graph using the

KernighanLin algorithm.
(a) Shows how swapping node 1 of partition A
with node 6 of partition B results
in a gain of g = 1.
(b) A graph of the gain resulting from swapping
pairs of nodes.
(c) The total gain is equal to the sum of the
gains obtained at each step.

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

 Application – Specific Integrated Circuits [ASIC]
• The K–L algorithm works well for partitioning graphs. However, there are the following problems that we
need to address before we can apply the algorithm to network partitioning:
✓ It minimizes the number of edges cut, not the number of nets cut.
✓ It does not allow logic cells to be different sizes.
✓ It is expensive in computation time.
✓ It does not allow partitions to be unequal or find the optimum partition size.
✓ It does not allow for selected logic cells to be fixed in place.
✓ The results are random.
✓ It does not directly allow for more than two partitions.

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

 Application – Specific Integrated Circuits [ASIC]
The Ratio-Cut Algorithm
• The ratio-cut algorithm removes the restriction of constant partition sizes. The cut weight W for a cut that
divides a network into two partitions, A and B , is given by

• The K–L algorithm minimizes W while keeping partitions A and B the same size. The ratio of a cut is defined
as

• In this equation | A | and | B | are the sizes of partitions A and B . The size of a partition is equal to the number
of nodes it contains (also known as the set cardinality).
• The cut that minimizes R is called the ratio cut. The original description of the ratio-cut algorithm uses ratio
cuts to partition a network into small, highly connected groups. Then you form a reduced network from these
groups—each small group of logic cells forms a node in the reduced network. Finally, you use the F–M
algorithm to improve the reduced network
Hemanth T S Assistant Professor, Dept., of E&CE, AIET, Moodbidri. 65
 Application – Specific Integrated Circuits [ASIC]

The Look-ahead Algorithm

• Both the K–L and F–M algorithms consider only the immediate gain to be made by moving a node. When
there is a tie between nodes with equal gain (as often happens), there is no mechanism to make the best
choice.
• This is like playing chess looking only one move ahead. Figure 15.11 shows an example of two nodes that
have equal gains, but moving one of the nodes will allow a move that has a higher gain later.
• We call the gain for the initial move the first-level gain. Gains from subsequent moves are then second-level and
higher gains. We can define a gain vector that contains these gains.
• Figure 15.11 shows how the first-level and second-level gains are calculated. Using the gain vector allows us to
use a look-ahead algorithm in the choice of nodes to be swapped. This reduces both the mean and variation in the
number of cuts in the resulting partitions.

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

 Application – Specific Integrated Circuits [ASIC]
▪ FIGURE 15.11 An example of network
partitioning that shows the need to look
ahead when selecting logic cells to be moved
between partitions. Partitionings (a), (b), and
(c) show one sequence of moves,
partitionings (d), (e), and (f) show a second
sequence.
▪ The partitioning in (a) can be improved by
moving node 2 from A to B with a gain of 1.
▪ The result of this move is shown in (b).
▪ This partitioning can be improved by moving
node 3 to B, again with a gain of 1.
▪ The partitioning shown in (d) is the same as
(a). We can move node 5 to B with a gain of
1 as shown in (e), but now we can move
node 4 to B with a gain of 2.

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

 Application – Specific Integrated Circuits [ASIC]

Simulated Annealing
• A different approach to solving large graph problems (and other types of problems) that arise in VLSI
layout, including system partitioning, uses the simulated-annealing algorithm [ Kirkpatrick et al., 1983].
Simulated annealing takes an existing solution and then makes successive changes in a series of random
moves.
• Each move is accepted or rejected based on an energy function, calculated for each new trial
configuration. The minimums of the energy function correspond to possible solutions.
• The best solution is the global minimum. So far the description of simulated annealing is similar to the
interchange algorithms, but there is an important difference. In an interchange strategy we accept the new
trial configuration only if the energy function decreases, which means the new configuration is an
improvement.
• However, in the simulated-annealing algorithm, we accept the new configuration even if the energy
function increases for the new configuration—which means things are getting worse. The probability of
accepting a worse configuration is controlled by the exponential expression exp(–D E / T ), where D E is
the resulting increase in the energy function.
• The parameter T is a variable that we control and corresponds to the temperature in the annealing of a
metal cooling (this is why the process is called simulated annealing).

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

 Application – Specific Integrated Circuits [ASIC]
• We accept moves that seemingly take us away from a desirable solution to allow the system to escape from a
local minimum and find other, better, solutions.
• The name for this strategy is hill climbing. As the temperature is slowly decreased, we decrease the
probability of making moves that increase the energy function.
• Finally, as the temperature approaches zero, we refuse to make any moves that increase the energy of the
system and the system falls and comes to rest at the nearest local minimum.
• Hopefully, the solution that corresponds to the minimum we have found is a good one. The critical parameter
governing the behavior of the simulated-annealing algorithm is the rate at which the temperature T is reduced.
This rate is known as the cooling schedule. Often we set a parameter a that relates the temperatures, T i and T
i + 1 , at the i th and i + 1th iteration:

• To find a good solution, a local minimum close to the global minimum, requires a high initial temperature and
a slow cooling schedule.
• This results in many trial moves and very long computer run times [ Rose, Klebsch, and Wolf, 1990]. If we
are prepared to wait a long time (forever in the worst case), simulated annealing is useful because we can
guarantee that we can find the optimum solution.

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

 Application – Specific Integrated Circuits [ASIC]

Questions
1. Draw the IEEE recommended dimensions and their constructions for logic gate symbols, NAND gate and XOR gate.
2. Explain the Hierarchical design with a suitable example.
3. Describe the schematic entry method in ASIC Design.
4. Explain annotation in ASIC Design.
5. Explain the vectored instances and buses for 16-bit D-latch and draw the diagram for 4-bit D-latch.
6. Discuss the vectored instances for 16-bit D-Latch.
7. Discuss the local nets and external nets in the ASIC design.
8. Explain the Schematic ICONs and Symbols with suitable examples.
9. What is Netlist Screener? List the errors that can be found by netlist screeners and mention the methods to overcome.
10. Explain the following with respect to low-level design entry:
i. Edit in place
ii. Schematic icons and symbols
iii. Hierarchical design
iv. Nets
v. Vectored instances

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

 Application – Specific Integrated Circuits [ASIC]

Questions
1. Enumerate the physical design/ASIC design of ASICs.
2. List steps in ASIC Physical Design and describe the goals and objectives of each step.
3. Explain the system partitioning with a proper example
4. Discuss the FPGA Partitioning by taking the example of the ATM simulator cell format
5. Describe the list of partitioning methods and explain any two of them
6. Explain the following partitioning methods
i. Kernighan–Lin Algorithm
ii. Constructive Partitioning
5. Explain the following partitioning methods
i. Iterative partitioning improvement
ii. Ratio-Cut Algorithm
6. Explain the following partitioning methods
i. Look Ahead Algorithm
ii. Simulated Annealing
7. With relevant equations, explain KL algorithm. Construct the connectivity matrix for the network shown in the
figure below. Also, find the gain in the network graph shown if:
i. Nodes 1 and 6 are swapped.
ii. Nodes 2 and 8 are swapped.

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

 Application – Specific Integrated Circuits [ASIC]

THANK YOU…☺

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