.\" deqn encycv3.ms | ditroff -t -ms | dipress -t -f /usr/local/lib/font > encycv3.interpress
.\" lpr -t  encycv3.interpress
.\" toplunger  encycv3.interpress
.nr PS 10
.nr VS 14
.nr LL 6.0i  \"line length
.nr Tm 1.0i  \"distance between header and top of page
.nr HM 1.5i  \"header margin
.nr FM 1.5i+\n(VSu  \"foot margin
.nr PD 0.3v  \"paragraph spacing
.hy 14   \" restrictions on hyphenation
.de PR \" define a proceedings reference
.KS
.IP [\\$1] 10
\\$2, \*Q\\$3,\*U in \\fI\\$4\\fP, \\$5.
.KE
..
.de BR \" define a book reference
.KS
.IP [\\$1] 10
\\$2, \\fI\\$3\\fP.  \\$4, \\$5.
.KE
..
.de TR \" define a Transaction reference
.KS
.IP [\\$1] 10
\\$2, \*Q\\$3,\*U \\fI\\$4\\fP, \\$5.
.KE
..
.de WR \" define a Workshop reference
.KS
.IP [\\$1] 10
\\$2, \*Q\\$3,\*U presented at \\fI\\$4\\fP, \\$5.
.KE
..
.\" PP - regular paragraph copied from /usr/local/lib/ditmac/tmac.s and modified
.de PP
.RT
.if \\n(1T .sp \\n(PDu
.ne 2
.ti +\\n(PIu
..
.\" LP - left paragraph copied from /usr/local/lib/ditmac/tmac.s and modified
.de LP
.RT
.if \\n(1T .sp \\n(PDu
.ne 2
.ti \\n(.iu
..
.\" SH - section header copied from /usr/local/lib/ditmac/tmac.s and modified
.de SH
.ti \\n(.iu
.RT
.ne 4
.B
..
.de MH	\"start new main section. print section header and change page header
.	\"parameter is section title (string)
.LP
.LG
.B
\\$1
.OH 'Automatic Placement And Floorplanning For VLSI Circuits' '%'
.\"rt page header, section and page number
..
.de MA \"rest of line is to appear as math entry
\\fI\\$1\\fP\\$2
..
.de FR \"italicize a foreign word
\\fI\\$1\\fP\\$2
..
.de SL \"smaller fonts
\\s-2\\$1\\s+2\\$2
..
.de IX 	\"first item to appear as an index entry, second item (punctuation
.	\"or s for plural) just goes on line
\\$1\\$2
.\" .tm \\$1\t\\n(PN\" print out to index file
..
.de DX \"rest of line is to appear as an index entry and is a defining
.      \"reference for this entry
\\&\\fI\\$1\\fP\\$2 \" put item into text in italics
.\" .tm \\$1\t\\n(PN\t*\" print out to index file
..
.ds CH 
.\"
.\"	The binding margin is kept in \n(BM in units.
.\"	    Here, you only get to specify the binding margin,
.\"		not the page offsets.
.nr BM 1.25i
.\"
.\"	Change the page offset so there are binding margins.
.\"	This assumes the paper is 8.5 inches wide.
.de PO
.if o .nr PO \\n(BMu
.if e .nr PO 8.5i-\\n(LLu-\\n(BMu
.\"	.tm PO sez: %=\\n%	LL=\\n(LLu	BM=\\n(BMu	PO=\\n(POu
..
.\"
.\"	The rest of this file is the .NP macro copied from
.\"		/usr/local/lib/ditmac/tmac.s
.\"	with a call to .PO added before setting the page offset.
.de NP
.if !\\n(LT .nr LT \\n(LLu
.if \\n(FM+\\n(HM>=\\n(.p \{\
.	tm HM + FM longer than page
.	ab
.\}
.if "\*(.T"vp" .CM
.if !\\n(HM .nr HM 1i
.PO
.po \\n(POu
.nr PF \\n(.f
.nr PX \\n(.s
.ft 1
.ps \\n(PS
'sp \\n(Tmu
.PT
'sp |\\n(HMu
.HD	\"undefined
.ps \\n(PX
.ft \\n(PF
.nr XX 0 1
.nr YY 0-\\n(FMu
.ch FO 16i
.ch FX 17i
.ch FO -\\n(FMu
.ch FX \\n(.pu-\\n(FMu
.if \\n(MF .FV
.nr MF 0
.mk
.os
.ev 1
.if !\\n(TD .if \\n(TC<5 .XK
.nr TC 0
.ev
.nr TQ \\n(.i
.nr TK \\n(.u
.if \\n(IT \{\
.	in 0
.	nf
.	TT
.	in \\n(TQu
.	if \\n(TK .fi
.\}
.ns
.mk #T
..
.\" caption start
.de Cp
.sp
.ce 1
..
.\" long caption start
.de Ci
.sp
.IP "\\$1" 13
..
.\" caption end
.de Cz
.ce 0
.sp 0.1i
..
.EQ
delim $$
.EN
.TL
.LG
Automatic Placement and
 
Floorplanning for VLSI Circuits
.EH 'Automatic Placement and Floorplanning for VLSI Circuits' '%'
.AU
Bryan T. Preas
.AI
Xerox Palo Alto Research Center
Palo Alto, California
.AU
Patrick G. Karger
.AI
Tektronix/CAE Systems Division
Beaverton, Oregon
.MH "1.\ \ Introduction"
.LP
This article describes the placement and floorplanning functions
within automatic layout systems.  Automatic 
.IX "placement"
and
.IX "floorplanning"
are defined and the data abstractions, or models, are discussed.  
The important algorithms, as well as their applications within layout systems,
are described.
References are provided to allow the article's use as an introduction to 
the literature.  
.PP
.DX "Physical design"
of an electronic circuit consists of transforming a circuit design
specification into a physical representation that can be used to manufacture the
circuit.  The speed with which this transformation takes place is greatly
enhanced by the use of automatic layout techniques.
.DX "Automatic layout"
is a
subset of the physical design process that maps a
.IX "structural representation"
of the circuit into a physical representation
consisting of geometric coordinates for all of the circuit elements and the
wiring that interconnects the elements.  The
.IX "structural representation"
that is input to the layout process consists of a list of circuit elements, or 
.DX "component" "s,"
that are to be included in the layout, and a list of
.IX "signal set" "s"
indicating the terminals, or 
.DX "pin" "s"
on the 
.IX "component" "s,"
that are to be made electrically common by the layout process.  The
.DX "interconnection net" "s,"
or simply 
.DX "net" "s,"
are the connections among the
.IX "signal set" "s."  
Preas and Lorenzetti provide an in-depth discussion of the physical design
process
[Pre88].  
.PP
Automatic layout consists of two primary functions: determining 
.IX "position" "s"
of 
.IX "component" "s" 
on a
.IX "layout surface" ","
called 
.DX "placement"
(which in a broader sense, includes floorplanning) and interconnecting the 
.IX "component" "s" 
with wiring, called 
.DX "routing" ","
according to a set of
.DX "design rule" "s."  
Although 
.IX "placement"
and 
.IX "routing"
are intimately related and interdependent, historically they have been
separated because of computational complexity.
Automatic 
.IX "placement" ","
the focus of this article, is responsible for determining the locations of the 
.IX "components" 
within the circuit being designed, subject to the 
.DX "constraint" "s"
imposed by the designer and the 
.IX "design rule" "s."
Sometimes the term placement is used in a narrow
sense to mean the positioning of components of a fixed size and shape
on the layout surface. (This is sometimes called component placement.)
The term is also used in a broader sense to refer to any function involved
in positioning components on a layout surface; this broader
definition includes floorplanning.
Although, this is somewhat confusing, both usages of the term
placement are well
established, and therefore, both are used here; the context should serve
to clarify the usage.
.PP
Good 
.IX "placement"
is a key aspect of automatic layout, but it sometimes receives insufficient
attention. A poor 
.IX "placement"
can leave the router with a difficult or impossible task, whereas a good 
.IX "placement"
can make a router's job easy.  Also, 
.IX "placement"
directly determines the minimum length of the interconnection wiring, and since
wiring delay may be the dominant part of the response time of electrical signals
on the wiring, 
.IX "placement"
often determines the performance of the physical circuit.  
.PP
The design of very large scale integrated (\s-2VLSI\s0) systems and the associated 
.IX "placement"
subproblems are typically defined hierarchically.
Placement algorithms normally operate on one hierarchical cell at
a time; the 
.IX "placement"
of (sub)
.IX "component" "s"
within a single (higher level) 
.IX "component"
is normally considered as a separate problem with boundary conditions defined by
the other
.IX "components"
at the same level as the (higher level) 
.IX "component" "."
Because of the confusion of 
.IX "component" "s"
at different levels of the design hierarchy, the term 
.DX "placeable objects"
is used to refer to the 
.IX "component" "s"
being placed.  
.PP
This article defines the 
.IX "placement"
problem and categorizes and reviews the 
.IX "placement"
techniques that are available.  It concentrates on 
.IX "placement"
of 
.IX "component" "s"
in the upper and intermediate levels of the design hierarchy.  The components
may be small- to medium-scale integration gates, or they may be large functional
units such as microprocessors or memories.  Specifically
excluded from discussion is the generation of the lowest or 
.DX "leaf cells"
of a hierarchical structure.
A more complete description of automatic placement is available in Chapter 4 of
[Pre88].
.PP
Section 2 describes the 
.IX "placement problem"
while Section 3 describes abstractions used: the components being placed; the
interconnection nets; and the layout surface on which the components
reside. As a result of a
.DX "technology-independent"
presentation, the placement concepts are applicable to electronic circuit
design for a wide range of circuit manufacturing technologies and design
styles, including
.DX "hybrid chip carrier" "s,"
and silicon \s-2VLSI\s0 circuits such as
.DX "gate array" "s,"
.DX "standard cell"
designs and 
.DX "general cell"
designs.  The basic algorithms (the focus of Sections 4 through 6) must be
tailored to the specific applications, design styles and fabrication
technologies; this is the topic of Section 7.    
.PP
Component placement methods fall into two groups: 
.IX "constructive"
and 
.IX "iterative" "."
.DX "Constructive methods" ","
described in Section 4, produce a 
.DX "complete placement"
(all 
.IX "component" "s"
have assigned 
.IX "position" "s)"
based on a 
.DX "partial placement"
(some or all 
.IX "component" "s"
do not have assigned 
.IX "position" "s)"
as input.
.DX "Iterative"
methods, discussed in Section 5, improve a
.IX "complete placement"
by modifying it to produce a better,
.IX "complete placement" "."  
The size and
shape of the circuit elements are determined as part of the design process for some
.SL "VLSI"
design styles; floorplanning, described in Section 6, aids this process.  
Floorplanning occurs before placement in the design process,
but is is discussed after placement in this article.
This order allows floorplanning to be discussed as an extension of placement.
.PP
A large number of techniques for placement and floorplanning have
been developed.  The only hope of describing the seemingly myriad variations is
to impose a taxonomy and to explain the basic algorithms.  Variations
are described as deviations from the basic algorithms.
.MH "2.\ \ Description of the Placement Problem"
.LP
.SH 
Component Placement
.LP
The 
.DX "placement problem"
consists of mapping the 
.IX "component" "s"
in a
.IX "structural representation"
onto 
.DX "position" "s"
on a
.IX "layout surface" "."  
Pins on the 
.IX "component" "s"
define locations at which the circuitry within the 
.IX "component"
connects to interconnection 
.IX "routing"
among the circuitry.  
External pins designate the interface area between the circuitry inside and the
environment outside of the 
.IX "component"
being designed; they are the 
.IX "pin" "s"
of the 
.IX "component"
at the next higher level of hierarchy.  The subsets of 
.IX "pin" "s,"
termed 
.DX "signal set" "s,"
which are to be connected by wiring to form electrically common 
.IX "interconnection net" "s,"
are part of the 
.IX "structural representation" "."  
.PP
The actual goal of 
.IX "placement"
is to determine non-overlapping 
.IX "position" "s"
for the 
.IX "component" "s"
that permit completely automatic 
.IX "routing"
of the interconnection wiring in a small area.  It may be necessary to honor any
number of other (possibly conflicting) goals, such as minimizing layout area or
cross talk among the signals carried by the wiring, equalizing heat dissipation
across the
.IX "layout surface" ","
or maximizing circuit performance.  Since
such goals are difficult to cast into objective functions that can be evaluated
by a computer, more restricted objective functions must be substituted.  When a 
.IX "placement"
operation derives a good 
.IX "placement"
as measured by a restricted objective, it is hoped that the 
.IX "placement"
is also good with respect to the actual goal.  The restricted objective
function is used as a metric to compare alternative 
.IX "placement" "s."
Ideally, it should accurately reflect the
actual goal, and should be fast to compute.  These conflicting goals have lead
to a plethora of objective functions; some are discussed in the next section.  
.PP
Placement problems may contain many thousands of
.IX "component" "s."
This results in huge 
.IX "placement"
state spaces.  For example, a design with
$1000$
.IX "component" "s"
(modest by today's standards) has approximately
$10 sup 2562$
different 
.IX "placement" "s."
To put this number in perspective, if a computer that could evaluate a trial 
.IX "placement"
in one microsecond had begun enumerating those 
.IX "placement" "s"
at the beginning of the universe, today it would have evaluated
$10 sup 24$
states.  To further complicate matters, it has been shown that the 
.IX "placement problem"
is nondeterministic polynomial (\s-2NP\s+2)-complete.
Thus, optimum solutions cannot be
guaranteed and methods based on
heuristics must be used for all but the smallest problems.  
.SH
Floorplanning
.LP
Early in the process of designing
.SL "VLSI"
circuits,
designers must make far reaching decisions based on incomplete or tentative
information.  The external interface of 
.IX "cell" "s"
(size and shape and the 
.IX "position" "s"
of the 
.IX "pin" "s)"
must sometimes be determined before the 
.IX "cell"
has been designed.  
In addition to placing the components (instances of the cells), floorplanning must determine
constraints on external interfaces 
for those 
.IX "cell" "s"
that have flexible interfaces.
Floorplanning is related to 
.IX "placement"
and many of the same techniques are used.  However, floorplanning is performed
earlier in the design process where less information and more flexibility exists.
This extra degree
of freedom (the flexibility of the cells) makes the problem significantly more
difficult.  
.MH "3.\ \ Abstract Models of Placement"
.LP
In order to apply an algorithm to a real problem, the problem must be
transformed into an abstract 
.IX "model" "."
Abstraction replaces an object with a simplified model that defines the
interaction of the object with its environment; details of internal organization
are deleted.  This reduces the amount of data, adds structure to the problem,
and makes the problem easier to solve.  After the algorithm is applied in the
abstract domain the abstract results must be transformed back into the real
domain.  This section describes the abstract 
.IX "model" "s"
that are important to 
.IX "placement"
algorithms.  The important aspects of electronic circuits that must be modeled
are the circuit elements, the interconnections and the carrier.  The 
.IX "model" "s"
of these aspects, the cell and 
.IX "component" ","
the 
.IX "pin" ","
the 
.IX "interconnection net" ","
the objective function and the
.IX "layout surface" ","
and their relation to the physical circuit are discussed.  
.SH
Cells and Components 
.LP
Automatic 
.IX "placement"
systems typically use an object/instance
paradigm to describe the circuit structure.  The definition of a circuit element
(the
.IX "object" ")"
is called a
.DX "cell"
and describes how the circuit element is constructed from
transistors or other primitives; these elements are 
.IX "placeable object" "s"
which may have been obtained from a library or constructed by any of the
physical
design methods.  Figure 1 shows one view of a cell consisting of a D latch.  The
figure illustrates the properties of the cell that are
important for 
.IX "placement" "."
Many of the details of the cell definition are abstracted away; only those
properties that are important to the electrical and
physical interface with the rest of the circuit and the
.IX "layout surface"
are considered.
An important aspect of the cell-based design style is that cells exhibit local
autonomy over their internal area and function.  Thus, a means for controlling
the interaction between the inside and outside of a cell is needed.  Pins
provide the appropriate abstraction.
Pins define the area at which the internal circuitry of a cell connects to the
external circuitry.
.KF
.sp 1.5i
.Ci "\fBFigure 1\fP"
This cell definition is a D latch from a standard cell library.  
Only the information important to
placement is retained by the cell abstraction.
.Cz
.KE
.PP
While cells carry the information pertaining to the definition of circuit
elements, the 
.IX "component" "s"
carry the information pertaining to their application; thus a 
.DX "component"
is an
.IX "instance"
of a cell.  Since the 
.IX "component" "s"
are those entities that are placed, they must carry the 
.IX "placement"
information: current location and orientation (rotation and reflection).
.SH
Interconnection Nets
.LP
The circuit elements, as represented by their abstractions (cells and 
.IX "component" "s),"
must be interconnected according to the 
.IX "signal set"
specifications.  It is the responsibility of the 
.IX "placement"
function to place the 
.IX "component" "s"
so that the interconnection wiring can be effectively routed.  Thus, an
important factor within a placer is the modeling of the wiring.  
.PP
It is important to model the topology of the interconnection nets
since the actual wiring paths will be determined by a router and are unknown
during placement.  
Assume the 
.IX "pin" "s"
of a 
.IX "signal set"
to be vertices of an undirected graph; then the connections among them form the
arcs of a graph.  Automatic layout systems, the circuit elements, routers, and
the manufacturing technologies combine to impose restrictions on the form of the
connection tree.  Figure 2 shows examples of the interconnection forms.
Topologies for interconnection nets with only two pins are simple; only one arc
is meaningful.  Nets with three or more pins are more complex. The most general 
.IX "form,"
called a Steiner tree, permits vertices of the connection graph to be at
.IX "pin" "s"
as well as at locations other than the 
.IX "pin" "s,"
and places no restrictions on the 
.DX "degree"
(the number of incident connections) of the vertices.  This is typical of
connections within integrated circuits.  A more restrictive interconnection
method is the spanning tree in which the vertices are restricted to be at the 
.IX "pin"
locations.  Other restrictions may apply; for example, 
.DX "wire-wrap"
fabrication imposes 
.IX "constraint" "s"
on the 
.IX "degree"
of the vertices because the posts that implement the 
.IX "pin" "s"
have a fixed height and thus can have a limited number of connected wires
(typically three).  An even more restricted method of interconnection is the
chain where no branching of the interconnection wiring (\fIi.e.,\fP 
.IX "degree"
of vertices \(<= 2) is permitted.  Some 
.IX "placement"
algorithms 
.IX "model"
the interconnection tree as a complete graph for computational simplicity
although the 
.IX "interconnection net"
will be routed more simply. Placement systems may 
.IX "model"
these interconnection topologies directly or they may use simpler
approximations.
.KF
.nf
.ta 1.5iC 4.5iC 
.sp 1.8i
	(a)\ Steiner\ Tree	(b)\ Steiner\ Tree\ with\ Trunk
	\ \ \ \ \ Rectilinear\ Length\ =\ 14	\ \ Rectilinear\ Length\ =\ 15
.sp 1.9i
	(b)\ Minimum\ Spanning\ Tree	(c)\ Chain
	\ \ Rectilinear\ Length\ =\ 16	\ \ Rectilinear\ Length\ =\ 17
.sp 1.9i
.ta 3.0iC 
	(e)\ Complete\ Graph
	\ \ \ \ Rectilinear\ Length\ =\ 42
.Cp
\fBFigure 2\fP\ \ These interconnection topologies are important for placement.
.Cz
.fi
.KE
.SH
Objective Functions
.LP
The quality of a 
.IX "placement"
is based on many factors; some examples are routing completion rate, circuit
performance
characteristics, and layout area.  Metrics based on these factors can compare
alternative 
.IX "placement" "s"
and are used by 
.IX "placement"
algorithms to compute a 
.DX "score"
which measures the quality of a 
.IX "placement" "."
The metrics are divided into two
classes: those that assume that the 
.IX "net"
.IX "routing" "s"
do not interact with other 
.IX "net" "s,"
and those that account for this interaction, or 
.DX "congestion" "."
Congestion metrics may also consider the interaction of 
.IX "net" "s"
with the 
.IX "component" "s"
or predefined features on the
.IX "layout surface" "."
.LP
\fBNet Metrics.\fP  The simplest metrics assume that the 
.IX "net" "s"
can be routed without interfering with each other or with the 
.IX "component" "s."
One widely used metric is 
.DX "wire length" ";"
this is the sum over all the 
.IX "net" "s"
of the lengths of the interconnection trees.  The length of an interconnection
tree is the sum of the individual arcs of the tree.  This metric is fast to
compute and the algorithm is easy to implement.
Another technique to measure 
.IX "placement"
quality 
.IX "models"
the connections as springs that exert forces on 
.IX "component" "s."
This leads to a force metric where a good 
.IX "placement"
is one that minimizes the sum of forces on the 
.IX "component" "s."
.LP
\fBCongestion Metrics.\fP  The 
.IX "net"
metrics quantify only the amount of wiring; they do not measure where the wiring
is located.  This can lead to wiring build-up or 
.IX "congestion"
as demonstrated by Figure 3.  In this example, a smaller wire length leads to
incomplete 
.IX "routing"
because wiring is in the \*Qwrong\*U place.  The second class of
interconnection metrics incorporates the interaction among the 
.IX "net" "s,"
the 
.IX "component" "s"
and the
.IX "layout surface"
in the measure of 
.IX "placement"
quality.
Congestion metrics often correlate better with 
.IX "routability"
than do wire length metrics because the areas where 
.IX "routing"
resources are needed are included in the metric.  
.KF
.sp 1.75i
.IP (a)
Two tracks are required.  All connections can be routed if two tracks are
available.
.sp 1.75i
.IP (b)
This placement has a shorter wire length than the placement in (a), but three
tracks are required.
A routing failure occurs if only two tracks are available.
.Ci "\fBFigure 3\fP"
Wire length reduction can cause routing failures.  This illustrates that
placement that minimizes wire length can be worse than a placement with longer
wire length if the wiring is in the \*Qwrong\*U place.
.Cz
.KE
.SH
Layout Surface 
.LP
The characteristics of the physical surface or 
.DX "carrier"
on which the circuit elements are placed must be modeled.  The abstraction of
the carrier
is called the 
.DX "layout surface" "."
Carrier 
.IX "model" "s"
divide into two categories: geometric and topological.  
.LP
\fBThe Geometric Model. \fP
.DX "Geometric models"
are appropriate for the
.IX "gate array"
style; the aspects of 
.IX "placement"
such as size and shape of the layout surface and
.IX "external pin"
.IX "position" "s"
do not change during the layout process.  
Some 
.IX "geometric model" "s"
place 
.IX "component" "s"
on a continuous plane and use geometric interference checking.  
Other 
.IX "model" "s"
restrict 
.IX "component" "s"
to fixed 
.IX "position" "s"
called
.DX "slot" "s;"
this gives rise to a 
.IX "placement"
approach which assigns 
.IX "component" "s"
to 
.IX "slot" "s"
that carry the geometric coordinates.  This approach is simple when all 
.IX "component" "s"
fit uniformly in all 
.IX "slot" "s;"
matters become much more complicated when 
.IX "component" "s"
vary in size or can be assigned to only a subset of the 
.IX "slot" "s."
.LP
\fBThe Topological Model.\fP The second category of
.IX "layout surface"
applies to 
.IX "standard cell"
and 
.IX "general cell"
.SL "VLSI"
design styles; the size, shape, and 
.IX "external pin"
.IX "position" "s"
of the cell being laid out as well as the 
.IX "component" "s'"
.IX "position" "s"
are determined by the layout system.  Furthermore, these 
.IX "position" "s"
are interdependent in complex ways and vary during the layout process.  For
example, 
.IX "routing"
areas can be made the exact size necessary to accommodate the interconnections.
This suggests a 
.DX "topological model"
composed of directed and undirected graphs.  Such a 
.IX "model"
provides an efficient representation of 
.IX "placement" ","
is easy to modify as the 
.IX "placement"
changes, and allows rapid computation of geometric functions of topology.  
.PP
A 
.IX "placement"
composed of rectangular 
.IX "component" "s"
can be explicitly represented as a 
.DX "rectangular dissection" "."  
It can be represented as an undirected planar graph (called a 
.DX "channel intersection graph" ")"
where the vertices represent the intersections of the dissection, and the edges
represent the adjacencies of the intersection [Pre79].
A 
.IX "placement"
composed of rectangular 
.IX "component" "s"
can also be represented by a pair of directed graphs (one for the horizontal
direction and one for the vertical direction).  The vertices of the horizontal
graph represent the vertical lines of the
dissection and the edges indicate if a line is to the right of another
line of the dissection.  
A similar description holds for the vertical graph.  These graphs, called
.DX "channel position graph" "s"
allow the 
.IX "position" "s"
of the 
.IX "component" "s"
to be easily computed.  
An extension of the basic (rectangular) 
.IX "model"
represents the 
.IX "placement"
of a subset of rectilinear shaped 
.IX "component" "s"
(arbitrary rectangles with arbitrary rectangles removed from 0 to 4 of the
corners) [Pre85].  
.MH "4\. \ Constructive Placement Algorithms"
.LP
An overview of 
.IX "component placement"
techniques is provided in this and the following section.  These techniques are
divided into 
.IX "constructive placement"
(the topic of this section) and iterative
.IX "placement"
(discussed in Section 5).
Constructive placement algorithms share the characteristic that their input is a
.IX "partial placement"
and their output is a
.IX "complete placement" "."
Although some 
.IX "constructive placement"
algorithms permit a 
.DX "seed"
.IX "placement"
as an initial condition, the ability to operate on unplaced 
.IX "component" "s"
differentiates these algorithms from the iterative 
algorithms.  Constructive placement
algorithms are used for initial placement, and are normally followed by one or
more (iterative)
.IX "placement"
improvement algorithms.  
Constructive placement techniques as a group are discussed and compared with
various 
.IX "placement"
improvement algorithms in [Han76].
The 
.IX "constructive placement"
algorithms are divided into the following classes: cluster growth,
partitioning-based 
.IX "placement" ","
global techniques, and
.IX "branch-and-bound"
techniques. These classes are
discussed below.  
.SH
Cluster Growth
.LP
Cluster growth 
.IX "constructive placement"
is a 
.DX "bottom-up"
method (consistently considers the most detailed level of abstraction) that
operates by selecting 
.IX "component" "s"
and adding them to a partial, or incomplete, placement.  This method is
differentiated from other placement methods in that cluster growth selects and
places the 
.IX "component" "s"
independently.  
.PP
The generic cluster growth algorithm is shown in Figure 4 and its operation
is illustrated in Figure 5.  In Figure 5, the dots represent the 
.IX "slot" "s"
in which the rectangular 
.IX "component" "s"
may be placed.  The first step is to determine a 
.IX "seed"
.IX "placement" "."
The 
.IX "component" "s"
in the 
.IX "seed"
.IX "placement"
and their 
.IX "position" "s"
may be chosen by the user in order to guide the 
.IX "placement"
process or may be determined algorithmically.  Next, unplaced 
.IX "component" "s"
are sequentially
selected and placed
in relation to those 
.IX "component" "s"
already placed.  This process continues until all 
.IX "component" "s"
are placed.  
.KF
.BD
\fIseedComponents\fP := Determine component(s) for seed
\fIcurrentPlacement\fP := \fI\s-2PLACE\s+2\fP [\fIseedComponents\fP, \
\fIcurrentPlacement\fP]
\fBuntil\fP all components are placed \fBdo\fP
   \fIselectedComponents\fP := \fI\s-2SELECT\s+2\fP [\fIcurrentPlacement\fP]
   \fIcurrentPlacement\fP := \fI\s-2PLACE\s+2\fP [\fIselectedComponents\fP, \
\fIcurrentPlacement\fP]
\fBendloop\fP
.DF
.Ci "\fBFigure 4\fP"
The cluster growth placement algorithm selects unplaced components and places
them in the slots that result in the best score.
.Cz
.KE
.KF
.sp 3i
.Ci "\fBFigure 5\fP"
This illustrates the operation of the cluster growth placement algorithm given
in Figure 4.  Unplaced components are selected and placed in relation to the
already placed components.
.Cz
.KE
.PP
The 
.IX "position" "s"
adjacent to previously placed 
.IX "component" "s,"
(the 
.DX "candidate"
.IX "positions" ")"
are investigated by calculating the 
.IX "score" 
that results when the selected 
.IX "component"
is placed in the 
.IX "candidate"
.IX "position" "s."
The
\fI\s-2SELECT\s+2\fP
function of the cluster growth algorithms determines the order in which unplaced
.IX "component" "s"
are included in the 
.IX "placement" "."
The order is determined by how \*Qstrongly\*U the unplaced 
.IX "component" "s"
are connected to the placed 
.IX "component" "s."
The
\fI\s-2PLACE\s+2\fP
function determines the best 
.IX "position" "s"
for the selected 
.IX "component" "s."
The 
.IX "component"
is placed at the 
.IX "candidate"
.IX "position"
that results in the best 
.IX "score" "."
By necessity the 
.IX "score"
must be based on incomplete information since unplaced 
.IX "component" "s"
cannot contribute to the scoring.
.DX "Ties"
can be resolved by a secondary metric such as finding the 
.IX "candidate"
.IX "position"
closest to the \*Qcenter of gravity\*U of the 
.IX "component"
directly connected to the 
.IX "candidate"
.IX "component" "."  
.PP
The complexity of the cluster growth
algorithms is of course dependent on the number of interconnections and the
number of 
.IX "pin" "s"
per net, but the dominant factor is the number of 
.IX "component" "s,"
$n$; the algorithms have a
computational complexity of
$n sup 2$.
These algorithms are easy to
implement but modern systems favor the partitioning-based or global
methods for initial 
.IX "placement" "."
These methods are described in the following two sections.  
.SH
Partitioning-Based Placement
.LP
Placement algorithms based on partitioning divide 
.IX "component" "s"
into two or more partitions, or \fIblocks\fP, while reserving space for the 
.IX "component" "s"
during the partitioning process; these algorithms are widely used in modern
layout systems. This 
.DX "top-down"
design approach considers higher levels of abstraction before it considers more
detailed levels, and tends to avoid heavy wiring 
.IX "congestion"
typically found in the center of the
.IX "layout surface" "."  
These algorithms differ from the cluster growth algorithms in the following way:
partitioning-based algorithms consider all interconnections in parallel and
then move the components in steps by partitioning the components into specific
areas of the layout surface.
.LP
\fBPartitioning Foundations.  \fP While determining optimal partitioning is
\s-2NP\s+2-complete, several good heuristics have been developed. Kernighan and
Lin
[Ker70] developed a 2-way
partitioning scheme based on iterative improvement of an initial (possibly
random) partitioning. The procedure, based
on pairwise exchange, judiciously selects the pairs to exchange and allows
multiple exchanges to occur before deciding to accept the sequence of exchanges.
.PP
While this heuristic works quite well for general graph partitioning, it does
not take into account a special property of electrical circuits: a group of
vertices in a single 
.IX "net"
do not have to be interconnected pairwise; they need only be connected by a
spanning tree. Schweikert and Kernighan [Sch72]
modified the Kernighan-Lin algorithm to keep track of the
decrease in the number of 
.IX "net" "s"
cut if a 
.IX "component"
moves from one partition to the other.  Improvements are judged over a sequence
of exchanges so that groups of 
.IX "component" "s"
which are highly interconnected can move from one partition to the other.  
.PP
Fiduccia and Mattheyses [Fid82] developed a further modification that allows
only a single 
.IX "component"
to be moved at a time from one partition to the other. The 
.IX "component"
is chosen based on its effect on both the net-cut 
.IX "score"
and the balance of the size of the partitions. This results in a linear time
heuristic for a single pass through the 
.IX "component" "s."
The Fiduccia-Mattheyses technique is
not quite as good as the Kernighan-Lin technique but the execution time is
substantially reduced [Dun85].  
.LP
\fBPlacement Based on Partitioning.  \fP Using the various partitioning
algorithms, many min-cut 
.IX "placement"
techniques have been developed. The algorithms are distinguished by how finely
the
layout surface is partitioned into blocks (\fIi.e.\fP, how many 
.IX "component" "s"
are in a block) before the 
.IX "component" "s"
are placed,
how and where cutlines are generated, and
how connections to external 
.IX "component" "s"
(not in the block currently being partitioned) are treated.  
.PP
The bipartitioning algorithms, illustrated in Figure 6, divide the 
.IX "component" "s"
into two sets such that the weighted number of connections between the sets is
minimized, and the total 
.IX "component"
area in each set is approximately equal. This process is repeated recursively
until each partition contains only one 
.IX "component"
[Bre77].
This technique
physically partitions the components into blocks on the layout surface; each
block has an exact physical
location and when each block contains only one 
.IX "component" ","
the circuit is completely placed.
Lauther [Lau79] developed a partitioning-based 
.IX "placement"
technique where the blocks generated during the partitioning process are
represented by polar graphs which retain information about the relative 
.IX "position" "s"
of the blocks.
.KF
.sp 2.5i
.ce 1
(a)  Original Placement
.sp 2.5i
.ce 1
(b)  Improved Placement
.Ci "\fBFigure 6\fP"
Min-cut placement places components on either side of a cut in such a manner as
to minimize the number of interconnections crossing the cut.
.Cz
.KE
.PP
Most partitioning-based algorithms consider only the connections between 
.IX "component" "s"
within the block being partitioned.  However, connections to other 
.IX "component" "s"
also influence the result.
One min-cut procedure introduces 
.DX "terminal propagation"
[Dun85].
This technique reflects external components' positions onto the boundary of the
block being partitioned.  
.PP
The partitioning-based algorithms make use of the interconnection information at
a global level and defer local considerations until late in the 
.IX "placement"
process. Although these procedures produce good results, they are
computationally expensive. These methods also tend to have difficulty
when 
.IX "component" "s"
are constrained to fixed 
.IX "position" "s"
or when partitions of grossly unequal areas are produced.  
.SH
Global Placement
.LP
All 
.IX "placement"
techniques keep global notions of better or worse 
.IX "placement" "s,"
but
.IX "global placement"
techniques are distinguished by the way in which they move 
.IX "component" "s."
Global methods move all of the 
.IX "component" "s"
simultaneously along an
$n$-dimensional
gradient.  This contrasts to cluster growth methods that consider each 
.IX "component"
sequentially, and to partitioning methods that first divide the 
.IX "component" "s"
by partitioning and then deal with the 
.IX "component" "s"
individually.  
Global placement techniques divide into two categories:
quadratic assignment and convex function optimization.
It is possible to find the optimum solution to the quadratic assignment
and convex function optimization problems associated with a placement problem.  
However, an optimum solution to the quadratic assignment
or convex function optimization problem does not guarantee an optimum solution
to the original 
.IX "placement problem" "."
The global methods use a quadratic objective function that
heavily penalizes long 
.IX "net" "s."
As a result connection lengths tend to cluster tightly around the mean 
.IX "net"
length.  This produces small standard deviations of 
.IX "net"
lengths compared to linear functions but the effect on 
.IX "routability"
is yet to be determined.  
Both methods also use a complete graph to 
.IX "model"
the 
.IX "interconnection net"
topology.  Thus, if all 
.IX "net" "s"
have the same weight, 
.IX "net" "s"
with more than two 
.IX "pin" "s"
can have a disproportionately large impact [Sch72].  This may be compensated for
by
weighting 
.IX "net" "s"
according to the number of 
.IX "pin" "s,"
$p$,
according to
$1 / (p-1)$,
$2 / p$,
or
$ ( {2 / p} ) sup 3/2$
[Fra86].  
.LP
\fBQuadratic Assignment.\fP  The quadratic assignment problem is usually
formulated as follows: given a cost matrix
$C = [c sub { ij }]$,
where
$c sub { ij }$
is the strength of the connection (number and weight of connections) between two
.IX "component" "s"
$i$
and
$j$,
and a distance matrix
$D = [d sub { kl }]$,
where
$d sub { kl }$
is the distance between 
.IX "position" "s"
$k$
and
.MA "l" "."
Minimize
$sum from { i, ~ j } ~ c sub { ij } d sub { P sub i P sub j }$
over all permutations,
$P$,
of the 
.IX "component" "s'"
.IX "position" "s."
Hanan and Kurtzberg
[Han72] describe the quadratic assignment method and how a 
.IX "placement problem"
can be transformed into (approximated by) an associated quadratic assignment
problem.  Although
the quadratic assignment method uses a quadratic metric, it does not exploit the
convexity of the metric.
.LP
\fBConvex Function Optimization.\fP  It is possible to formulate the 
.IX "placement problem"
as an objective to be minimized, and to use conventional mathematical
optimization techniques to solve the problem. Optimization techniques work best
when both the domain and the objective function are convex; in this case only a
single minimum exists.  Through appropriate abstractions that produce a convex
domain (primarily the absence of 
.IX "slot" "s"
and of 
.IX "component" "s"
with finite size) and the use of a quadratic metric, it is possible to transform
a 
.IX "placement problem"
into one that may be solved using gradient techniques.  
.PP
In general, these techniques suffer from an inability to deal with practical 
.IX "constraint" "s"
such as finite 
.IX "component"
size and 
.IX "constraint" "s"
imposed on 
.IX "component"
.IX "position" "s."
These drawbacks are addressed by Blanks [Bla85] through the use of
quadratic 
.IX "constraint" "s"
and a two-step procedure to map the global (ideal) 
.IX "placement"
onto the
.IX "layout surface"
without violating any physical 
.IX "constraint" "s."
Sha
and Dutton
[Sha85] attempt to alleviate the need for the second step by encoding all
geometric information into 
.IX "constraint" "s"
placed on the scoring function.  
A multi-dimensional geometric approach which couples Eigenvector
probes and linear assignment to provide a more systematic mapping of the ideal 
.IX "placement"
onto the carrier [Fra86].  Since few comparisons have been performed, it is
difficult to
evaluate the relative merits of the global methods versus other 
.IX "placement"
methods; however, good results have been reported [Bla85, Fra86].
.SH
Branch-and-Bound Placement
.LP
The
.IX "branch-and-bound"
method can be used to find an optimum solution for small 
.IX "placement problem" "s."
This is done by systematically searching a decision tree representing all
possible placements. The \*Qbranch\*U step divides the solution state space
(creates
a branch in the decision tree)
while the \*Qbound\*U
step prunes the decision tree.  The \*Qbound\*U step potentially reduces
computational requirements: the more accurately the lower bound is calculated,
the sharper the pruning.  However, there is a trade-off: it takes longer to
calculate a more accurate lower bound.  Due to the necessity to either calculate
accurate lower bounds or explore a large number of branches, this technique is
quite time consuming.  Heuristics have been suggested to prune the tree
[Han72]; these
heuristics have a computational complexity of
$n sup 3$
or
$n sup 4$.  
Although
.IX "branch-and-bound"
algorithms do not appear in modern layout systems, the technique is interesting
for theoretical studies where
optimum solutions are required for small problems.
.MH "5.\ \ Iterative Placement"
.LP
The goal of 
.IX "iterative"
.IX "placement"
is to manipulate a 
.IX "complete placement"
to produce an improved, 
.IX "complete placement" "."
This process is iterated until some
stopping criterion is met.  For example, the stopping criterion might be
relative or absolute improvement in the 
.IX "placement"
metric, or perhaps the time expended in the 
.IX "iterative"
process.  Within one iteration loop, 
.IX "component" "s"
are selected and moved
to alternate locations.  If the resulting configuration is better than the
previous, the new configuration is retained; otherwise the previous
configuration is
restored.  The improvement process and the more important 
.IX "iterative"
improvement algorithms are discussed in this section.  
.SH
Three Phases of Iterative Placement
.LP
Many different iterative 
.IX "placement"
techniques exist.  Even though they differ substantially, they share the same
underlying structure and have three main phases: selection, movement, and
scoring.  The generic form of 
.IX "iterative"
improvement 
.IX "placement"
algorithms is shown in Figure 7.  These three phases are discussed next.  
.KF
.BD
 \fIcurrentScore\fP := \fI\s-2SCORE\s+2\fP [\fIcurrentPlacement\fP]
\fBuntil\fP stopping criterion is satisfied \fBdo\fP
   \fIselectedComponents\fP := \fI\s-2SELECT\s+2\fP [\fIcurrentPlacement\fP]
   \fItrialPlacement\fP := \fI\s-2MOVE\s+2\fP [\fIselectedComponents\fP, \
\fIcurrentPlacement\fP]
   \fItrialScore\fP := \fI\s-2SCORE\s+2\fP [\fItrialPlacement\fP]
   \fBif\fP \fItrialScore\fP < \fIcurrentScore\fP \fBthen\fP
      \fIcurrentScore\fP := \fItrialScore\fP
      \fIcurrentPlacement\fP := \fItrialPlacement\fP
   \fBelse\fP \fIcurrentPlacement\fP := \fI\s-2MOVE\s+2\fP [\fIselectedComponents\fP, \
\fItrialPlacement\fP]
\fBendloop\fP { \fBuntil\fP stopping criterion is satisfied }
.DF
.Ci "\fBFigure 7\fP"
The generic iterative improvement placement algorithm is defined in terms of
\fI\s-2SELECT\s+2\fP, \fI\s-2MOVE\s+2\fP, and \fI\s-2SCORE\s+2\fP functions.
.Cz
.KE
.LP
\fBSelection.\fP  The
.MA "\s-2SELECT\s+2"
function chooses the 
.IX "component" "s"
to participate in movement.  This mechanism reduces the set of all possible
combinations of 
.IX "component" "s"
to move simultaneously to a computationally feasible subset.  The selection
process may simply select 
.IX "component" "s"
to be interchanged in a predefined sequence (such as trying all possible pairs),
or may involve intelligence to select those 
.IX "component" "s"
which are placed poorly.  Incorporating intelligence into the selection process
typically allows 
.IX "placement"
to converge more quickly, but may not improve the quality of the solution.
There is also a danger that an overly restrictive selection function may miss
productive moves and degrade the quality of the solution.  
.LP
\fBMovement.\fP  Once the 
.IX "component" "s"
are selected for trial interchange, the
.MA "\s-2MOVE\s+2"
function determines the new locations for the selected 
.IX "component" "s."
If a pair of 
.IX "component" "s"
is selected, then the 
.IX "component" "s'"
.IX "position" "s"
are interchanged.  Of course, it must, be physically possible for each 
.IX "component"
to fit at the location of the other.  
Some 
.IX "iterative"
placers are limited to moving 
.IX "component" "s"
among 
.IX "position" "s"
which are 
.IX "slot" "s"
for certain types of 
.IX "component" "s."
This restriction eliminates the need to dynamically check for
.IX "component"
overlap and thus results in much faster 
.IX "placement"
techniques at the sacrifice of 
.IX "placement"
quality.  
.LP
\fBScoring.\fP  After the selected 
.IX "component" "s"
have been moved to new 
.IX "position" "s,"
the objective function measures the quality of the new arrangement.
At this stage, the representation of interconnections should be as accurate as
possible consistent with the time available for 
.IX "iterative"
improvement; the interconnection graph should correspond to the actual
routes that will be generated.  The scoring metric may be the same as that used
by the initial placer or may incorporate more detail concerning the 
.IX "routing"
resources.  The 
.IX "iterative"
.IX "placement"
scoring metric should work in concert with any metric used by the initial
placer; otherwise any initial 
.IX "placement"
quality is wasted.  
.SH
Iterative Improvement Techniques
.LP
Now that the three main functions within the 
.IX "iterative"
.IX "placement"
loop have been described, the various 
.IX "iterative"
algorithms will be reviewed in terms of these functions.  
.LP
\fBInterchange.\fP  In 
.DX "pairwise interchange"
each 
.IX "component"
is selected in turn to be the 
.DX "primary"
.IX "component"
and is trial interchanged with each other 
.IX "component" "."
If a trial interchange results in an improved 
.IX "placement" ","
the interchange is accepted; otherwise the 
.IX "component" "s"
are returned to their previous 
.IX "position" "s."
Any objective function can be used as the basis for acceptance of an exchange.
This technique results in
$n(n - 1)/2$
trial interchanges, making the computational complexity
$O(n sup 2 )$,
where
.MA "n"
is the number of 
.IX "component" "s."
The 
.DX "neighborhood interchange"
technique is similar to 
.IX "pairwise interchange" ";"
however, the 
.IX "primary"
.IX "component"
is interchanged only with 
.IX "component" "s"
in its vicinity.
.LP
\fBForce Directed Methods.\fP  
.DX "Force directed interchange"
uses a force analog to select 
.IX "component" "s"
to move as well as to determine the 
.IX "position" "s"
to which the 
.IX "component" "s"
should be moved.  However, the 
.IX "position"
to which the selected 
.IX "component"
should be moved may already be occupied by another 
.IX "component" "."
Furthermore, the location of the selected 
.IX "component"
may not be a good 
.IX "position"
for the 
.IX "component"
occupying its favored 
.IX "position" "s."
Experimental
results using force directed interchange are given in [Han76].  
.PP
.DX "Force directed relaxation"
is similar to the force directed interchange method.
In this technique, however, the 
.IX "primary"
.IX "component"
is positioned in the compatible 
.IX "slot"
nearest to the desired zero force point.  The 
.IX "component"
that was occupying that 
.IX "slot"
is chosen as the next 
.IX "primary"
.IX "component" "."
The process results in a series of 
.IX "component" "s"
to be relaxed.
.PP
The 
.DX "force directed pairwise relaxation"
method [Han76] also uses force vectors to find the zero force
target locations for each 
.IX "component" "."
In this method, however, the 
.IX "primary"
.IX "component"
is not allowed to initiate a series as in 
.IX "force directed relaxation" "."
Instead the 
.IX "primary"
.IX "component"
.MA "A"
is trial-interchanged with a 
.IX "component"
.MA "B"
in the vicinity of the target location only if the target location of
.MA "B"
is in the vicinity of 
.IX "component"
.MA "A" "."  
The interchange is accepted only if the 
.IX "placement"
.IX "score"
improves.
.PP
Force directed techniques share the characteristic that the force is a
restrictive selection method.  Iteration converges quickly but the process tends
to stop even when many productive exchanges still remain.  
.LP
\fBUnconnected Sets.\fP  Steinberg describes a technique [Ste61] that selects 
.IX "component" "s"
by dividing them into sets of 
.IX "component" "s"
which have no 
nets in common, or
.DX "unconnected sets"
of components. Each component in such a set can be trial-placed without
considering the other components of the set.  The 
.IX "placement"
of these 
.IX "component" "s"
can be obtained by solving the resulting linear assignment problem since the 
.IX "score"
does not depend on the interaction of the 
.IX "components" "'"
locations.  After each unconnected set has been processed, the
cycle is complete.
Experience with this technique indicates limited
success because 
.IX "component" "s"
in highly interconnected groupings (a common occurrence in modern circuits) are
not moved with respect to each other, and 
.IX "net" "s"
with large numbers of 
.IX "pin" "s"
(for example, clocks) limit 
.IX "component"
movement.
.LP
\fBSimulated Annealing.\fP  The previous techniques share the characteristic
that trials are accepted only if the 
.IX "score"
does not increase.  This limitation can cause the 
.IX "placement"
to reach a local minima but miss the global optimum.  Kirkpatrick
.FR "et al."
[Kir83] describe an technique, 
.DX "simulated annealing" ","
that addresses this issue.  
.PP
The optimization of a circuit 
.IX "placement"
with a very large number of 
.IX "component" "s"
is analogous to the process of annealing in which a material is melted and
cooled slowly so that it will crystallize into a highly ordered state.  The
energy corresponds to the 
.IX "placement"
.IX "score"
and an 
.DX "annealing schedule"
specifies the beginning and ending 
.IX "score" "s"
as well as the rate of change of the score.  The method begins with a random initial 
.IX "placement" "."
An altered 
.IX "placement"
is generated and the resulting change in 
.IX "score" ","
$ \(*D s $,
is calculated.  If
$ \(*D s < 0 $
(the system went to a lower energy level) then the move is accepted.  If
$ \(*D s \(>= 0 $
then the move is accepted with probability
.MA "e\s-2\u\(mi\(*Ds/t\d\s+2" ".  "
As the simulated temperature
.MA "t"
decreases, the probability of accepting an increased 
.IX "score"
decreases.  
.PP
The objective function used for scoring may be any of the functions described in
Section 3; wire length and 
.IX "net"
half-perimeter are often used.  This method has been used extensively as an 
.IX "iterative"
improvement technique.  The generic 
.IX "iterative"
.IX "placement"
algorithm is rearranged (as shown in Figure 8) to illustrate the 
.IX "simulated annealing"
concepts.  
.KF
.BD
 \fIt\fP := \fIt\fP\d\s-20\s+2\u
\fIcurrentPlacement\fP := randomInitialPlacement
\fIcurrentScore\fP := \fI\s-2SCORE\s+2\fP [\fIcurrentPlacement\fP]
\fBuntil\fP freezing point reached \fBdo\fP
   \fBuntil\fP freezing point reached \fBdo\fP
     \fIselectedComponents\fP := \fI\s-2SELECT\s+2\fP [atRandom]
     \fItrialPlacement\fP := \fI\s-2MOVE\s+2\fP [\fIselectedComponents,\fP \
atRandom]
     \fItrialScore\fP := \fI\s-2SCORE\s+2\fP [\fItrialPlacement\fP]
      \(*Ds := \fItrialScore\fP - \fIcurrentScore\fP
      \fBif\fP \(*Ds < 0 \fBthen\fP \fIcurrentScore\fP := \fItrialScore\fP
      \fBelse begin\fP
          \fIr\fP := uniformly random number {0 \(<= \fIr\fP \(<= 1}
          \fBif\fP \fIr\fP < $e sup {- \(*Ds / t}$ \fBthen\fP \fIcurrentScore\fP := \fItrialScore\fP
         \fBelse\fP \fIcurrentPlacement\fP := \fI\s-2MOVE\s+2\fP [\fIselectedComponents\fP, \fItrialPlacement\fP]
      \fBend\fP
   \fBendloop\fP
   \fIt\fP := \(*a\fIt\fP {0 < \(*a < 1}
\fBendloop\fP
.DF
.Ci "\fBFigure 8\fP"
Simulated annealing placement uses random selection, movement, and acceptance to
explore the placement state space.  This method produces good placements
at the expense of long runtimes.
.Cz
.KE
.PP 
.IX "Simulated annealing"
can climb out of local minima to find a global optimum if the proper conditions
on the 
.IX "annealing schedule"
are satisfied.  However, in practical problems this implies an infinite number
of
iterations at each temperature. This is clearly impossible, but massive
computational resources are required for practical
problems.  Thus various approaches have been proposed to speed up the process.
The
approaches fall into three categories: move set design, cost function
manipulation, and cooling schedule improvements
.PP
One move set design is based on range limiting [Sec84]. This discards moves involving components which are more than some specified distance apart; the specified distance decreases as temperature decreases.  
Cost
function manipulation may involve altering the probability of acceptance or
approximating the objective function at high temperatures.
A 
.DX "rejectionless method" ,
in which the probability of selecting a move is based on its probability of
being accepted, is described in [Gre84].
.PP
Annealing schedule improvements are the third approach to improving 
.IX "simulated annealing"
performance.  An 
.IX "annealing schedule"
is composed of a beginning temperature, a temperature decrement, an equilibrium
condition at each temperature, and a convergence condition.  White proposes the
use of an initial temperature that is much greater than the standard deviation
of the cost distribution that occurs when all moves are accepted [Whi84].  
A widely used temperature decrement is a geometric progression,
$t~:=~alpha t$, where typical
$\(*a$
is
0.95.  
Huang [Hua86] derives the temperature decrement,
$t~:=~te~sup -0.7t$,
based on the condition required to maintain quasi-equilibrium.  The equilibrium
condition at each temperature may be a fixed Markov chain length, a
minimum acceptance, or a dynamic Markov chain length.  A typical
stopping criterion is when the average 
.IX "score"
is unchanged for a few consecutive temperatures.  
Even with these speed-up techniques, 
.IX "simulated annealing"
remains computationally intensive compared to other techniques, but it is robust
over a wide range of problem types.
.SH
Summary of Placement Techniques
.LP
While finding the optimum solution to the general 
.IX "placement problem"
is
.SL "NP" "-complete,"
the 
.IX "placement"
methods discussed provide heuristic techniques which attempt to provide a
\*Qgood\*U
.IX "placement" "."
These techniques are divided into two categories: 
.IX "constructive placement"
and iterative 
.IX "placement" "."
Many other heuristics are possible, but the methods
discussed represent the most popular 
.IX "placement"
techniques.  
.MH "6.\ \ Floorplanning"
.LP
During the early stages in the design of electronic systems, decisions are made
which have a dramatic effect on the quality (performance, density or area)
of the resulting circuit design.  Choices must be made in partitioning functions
into physical cells and in choosing interface characteristics
(such as size, shape and pin positions) of the cells.
These choices are difficult because they must be made with
relatively little information and because the effects are
hard to predict and
may not become apparent until much later in the design process.  
.PP
Floorplanning is closely related to 
.IX "general cell"
.IX "placement"
(described in the 
next section).  Both problems are concerned with the 
.IX "placement"
of (usually
rectangular) cells of arbitrary aspect and size such that the total area
occupied by the cells and their interconnections is minimized.  Thus, many
techniques of 
.IX "general cell"
.IX "placement"
have been adapted to
floorplanning.  However, floorplanning has an extra degree of freedom: at
least some of the 
.IX "cell" "s'"
interface characteristics
must be determined and fixed.  The flexibility in the
interface of the cells is constrained by the function and layout of the cells
and must be modeled by the floorplanner.  
.SH
Models of Floorplanning
.LP
Because of the similarity to 
.IX "general cell"
.IX "placement" ","
many floorplanning
techniques use the 
.IX "model" "s"
described in Section 3.  The most important
exception is in the modeling of the cells; floorplanning algorithms must 
.IX "model"
the cells' interface flexibility and any 
.IX "constraint" "s"
on that flexibility.  
Three classes of cells are used in floorplanning:
.IP \(bu  
Some cells are already laid out and are stored in a library.  These fixed cells
comprise the class used by 
.IX "placement"
algorithms; all of their interface
characteristics are known and fixed.  
.IP \(bu  
The designs of some cells are known but their layouts are flexible and
can be influenced by the
results of floorplanning.  For example, the standard
layout method can produce
a wide range of shapes for a given design.  
Programmable logic arrays can be
distorted through folding or layout design.  Several versions of a cell with
different characteristics may be stored in a library.  
.IP \(bu  
Cells of a third class are flexible because their designs (and perhaps even the
design methods) are uncertain or not known.  In this case it is difficult for
designers or algorithms to specify either nominal interface characteristics
or 
.IX "constraint" "s"
thereon.  
.PP
An important aspect of cell modeling is estimation of area and shape.  Four
approaches have been reported: experimental, analytical, procedural
and knowledge-based.  
Experimental approaches develop area estimates through empirical formulas
and are usually tuned to a design style or even to a
particular system [Kur86].  Analytical approaches concentrate on wireability analysis
and 
.IX "routing"
area analysis [Hel77].  
Procedural cell 
.IX "model" "s"
have the ability to sense their context (for example, the 
neighboring cells and their relation to the subject cell) and optimize their
interface characteristics for the current 
.IX "position."  
Knowledge-based approaches can operate on more uncertain cell designs.  
A more precise method of area estimation is available if a slicing structure 
is used and 
.IX "constraint" "s"
on shapes of all of the children 
.IX "component" "s"
of a cell
are known.  Otten describes a method of computing the bounds on shapes that a 
cell can assume based on the bounds on shapes of its constituent 
.IX "component" "s"
[Ott86].  
.SH
Approaches to Floorplanning
.LP
There are three major thrusts in floorplanning. One thrust accepts that
floorplanning is so difficult that a circuit designer must be an integral
part of the process; therefore interactive graphics must be included in
addition to algorithmic approaches. The second major thrust uses
floorplanning in the initial stages of design synthesis to develop
.IX "constraint" "s"
that can be passed to later, separate stages in the design process.
The third major thrust relies on the existence of powerful module 
generators that can generate modules to specifications.  This allows the
floorplanner to be integrated with layout generators and permits truly automatic
layout.  
.PP
Many approaches have been proposed for solving floorplanning problems, but the
methods may be grouped as constructive and iterative.  
Constructive methods include cluster growth,
connectivity clustering, and
partitioning/slicing.  
The 
placement
methods described in
[Pre79] have been adapted to floorplanning by using procedural
methods to estimate or define cell shapes during each placement trial.
A clustering method based
on circuit connectivity is described in [Dai86].  Clusters are mapped onto floorplan templates
that have simplified topologies.  Complex circuits are planned by recursively
applying the same algorithm.  
Partitioning/slicing placement has also been applied to floorplanning
with some degree of success.
Constructive floorplanning methods share
the characteristic that they algorithmically construct a 
.IX "floorplan" "."
.PP
In contrast to the constructive floorplanning
methods, iterative techniques operate on
complete floorplans to improve the layout quality. These methods
fall into three categories: interchange, relaxation, and knowledge-based.
The iterative placement
algorithms described in Section 5 have been adapted to floorplanning.  These algorithms have been generalized to handle flexible cell shapes and to define new floorplanning states.  Typically, cells
are optimized at the time of interchange.  In some cases the channel 
position and channel intersection graphs of the topological model
are manipulated directly [Pre79]
to perform 
.IX "pairwise interchange" ".  "
In other cases the regularity of slicing
structures is exploited to define new floorplanning states.  
Relaxation is different from
interchange techniques in that relaxation implies an obvious or preferred
next state.
The relaxation method consists of modifying
the channel graphs of the 
layout surface
as well as the cell shapes.
Knowledge-based floorplanning approaches have also been tried [Wat86].
.PP
It is extremely difficult to compare floorplanning approaches because results
are highly dependent on the circuit design, the design styles and the
design methodology.  Furthermore, since floorplanning occurs early in the
design process, the subsequent layout steps can partially mask the quality
of floorplanning.  As a result comparisons are non-existent.  
.MH "7.\ \ Applications of Placement and Floorplanning Algorithms"
.LP
So far, discussion has been limited to 
.IX "model" "s"
and 
.IX "technology-independent"
algorithms for 
.IX "component placement"
and floorplanning.  However, the ways in which the algorithms are
applied can vary significantly depending on problem and design environment
attributes.  Some of these attributes are explored in this section: large number
of 
.IX "component" "s,"
design styles, circuit performance criticality.
.SH
Large Number of Components
.LP
Most 
.IX "placement"
algorithms operate on 
.DX "flat"
representations of hierarchical descriptions; this means the 
.IX "placement"
algorithms do not make use of information at higher or lower levels of their
design hierarchy.  However, since 
.IX "placement"
algorithms may be
$O(n sup 2 )$
or higher, it may be impossible to consider all 
.IX "placeable object" "s"
within a containing 
.IX "component"
simultaneously in a very large circuit.  At this point there are three
choices: partitioning, hierarchical 
.IX "placement" ","
hardware accelerators or multiple processors.  
.LP
\fBPartitioning.\fP  In this approach 
.IX "flat"
.IX "placement problem" "s"
are divided into separate but interdependent subproblems that are solved
sequentially.  The subproblems are not independent since the decisions made in
one subproblem affect the others; decisions which improve the 
.IX "placement"
within one partition might degrade the overall 
.IX "placement" "."
However, subdividing the problem reduces the complexity of the problem.  For an
algorithm which has complexity of
$O(n sup \(pt )$
($n$ is the number of 
.IX "component" "s"
and $\(pt > 1$),
a problem which is subdivided into
.MA "p"
parts has a complexity of
$O( p(n/p) sup \(pt )$
or
$O({n sup \(pt} / { p sup { \(pt - 1 }} )$.  
Khokhani
.FR "et al."
[Kho81] describe a method that partitions a circuit into \*Qsuper nodes,\*U and
uses
.IX "constructive initial placement"
and iterative 
.IX "placement"
to improve the assignment of the super nodes to \*Qsuper locations.\*U  Next the
super nodes are decomposed into primitives and placed.  
.LP
\fBHierarchy.\fP  In hierarchical 
.IX "placement" ","
problem complexity is reduced by subdividing the circuit into multiple levels.
The top level divides the circuit into first level 
.IX "component" "s,"
which are themselves partitioned into lower level components. This subdivision
continues recursively until (for purposes of placement) primitive placement
components are defined. The hierarchical subdivision may be the same as that
defined in the 
.IX "structural representation"
or the layout system may provide automatic hierarchical partitioning
before invoking 
.IX "placement"
algorithms separately on the resultant 
.IX "component" "s."  
.LP
\fBHardware Accelerators and Multiple Processors.\fP  It is possible to reduce
the execution times through the use of special-purpose hardware optimized for 
.IX "placement"
tasks and/or multiple processors that
allow parallel processing.
An in-depth discussion of the architectures of hardware accelerators is not
attempted here; a discussion of special-purpose hardware for design
automation is
given in [Bla84].  
A discussion of a 
.IX "placement"
hardware accelerator implementation with comparative results is
given in [Spi85].
.PP
Hancock and DasGupta [Han86]
discuss multi-processors applied to design automation problems as well as
discussing the multiprocessor configuration known as the
hypercube.  
Kravitz and Rutenbar [Kra86] give a taxonomy of
parallel algorithms as well as three different implementations
of parallel algorithms for 
.IX "simulated annealing"
on 1 to 4 processors.  
They present the concepts of object and function decomposition; object
decomposition is an assignment of entities (such as cells or 
.IX "net" "s)"
to processors
while function decomposition is an assignment of operations (such as wire length
calculation) to processors.  They also present the idea of
static versus dynamic decomposition; this describes whether
the assignment of objects or functions to processors is done once or changes
over time.  
.SH
Layout Design Styles
.LP
The demands placed on and the design of 
.IX "placement"
algorithms vary greatly depending on the design style that is addressed.  The
styles considered here are
.IX "gate array" ","
.IX "standard cell" ","
and 
.IX "general cell" "."  
More information on \s-2VLSI\s+2 design styles can be found in Chapter 1 of
[Pre88].
.LP
\fBGate Arrays.\fP  Since 
.IX "gate array" "s"
have fixed, legal gate sites, the 
.IX "placement"
algorithms must have knowledge of these sites and any location restrictions for
various cells.  For instance \s-2I/O\s0 pad sites are around the periphery and
\s-2I/O\s0
drivers are near the periphery. Furthermore, the total routing resources are
fixed before the layout process begins, so it is important to use the resources
wisely. Thus it may
be necessary to 
.IX "model"
.IX "congestion"
in the 
.IX "placement"
objective function. It is sometimes possible to find alternate 
.IX "placements"
which have longer wire lengths but less 
.IX "congestion" "." 
.LP
\fBStandard Cells.\fP  In 
.IX "standard cell"
designs, 
.IX "component"
and 
.IX "routing"
area sizes and positions are not fixed.  The layout size is defined dynamically
by the layout
program based on the requirements of the specific circuit.  While the final
topology is arranged with rows of 
.IX "standard cell" "s"
and 
.IX "routing"
channels between the rows, the number, lengths and 
.IX "position" "s"
of the 
.IX "component"
rows and the 
.IX "routing"
channels can be adjusted dynamically.  
The cells may have varying heights and widths and are retrieved from a library
or constructed using module generation techniques.
Power is usually distributed through the cells and does not intrude on the 
.IX "routing"
area.  
It is necessary to make trade-offs between the number
and size of the channels and the number of rows.  Rows lengths must be kept
uniform or space is wasted at the end of short rows.  Additionally, it is
beneficial to consider 
.IX "routing"
density uniformity along the cell rows.
These issues necessitate significantly different capabilities in the 
.IX "placement"
algorithms and underlying data structures compared to gate arrays.  Metrics such as wire length must be
augmented to account for the dynamic nature of the design style.  Due to the
complexity of dynamically adjusting cell rows and 
.IX "routing"
channels, the underlying data structure is typically a topological 
.IX "model" "."  
.LP
\fBGeneral Cells.\fP  General cell 
.IX "placement"
further extends the topological 
.IX "model" "."
General cells are not restricted to have similar sizes or be arranged in rows.
This adds considerable complexity.  Careful consideration must be given to the 
.IX "placement"
of the large cells since their 
.IX "position" "s"
will have a large impact on the resulting topology. 
Also, the 
.IX "placement"
.IX "model"
must account for 
.IX "routing"
resources needed in the vicinity of each 
.IX "component" ","
since the way in which the various 
.IX "component" "s"
fit together and the way the 
.IX "routing"
areas align is extremely important.  
.PP
The basic 
.IX "placement"
algorithms discussed in Sections 4 and 5 have been adapted to
general cell 
.IX "placement" "."
The reader is also directed to Section 6 because of the many
similarities with floorplanning.  However, the general nature of the two
dimensional cell 
.IX "placement problem"
(the lack of a predefined array of 
.IX "slot" "s"
for 
.IX "gate array" "s"
or rows for 
.IX "standard cell"
design styles) has led to 
.IX "placement"
techniques that are applicable to 
.IX "general cell"
.IX "placement" "."
These techniques include cluster growth [Pre79], clustering, merging
and rearranging [Che84], force directed approaches [Qui79], 
.IX "global placement"
[Bla85], and partitioning [Lau79].    
.SH
Placement Based on Circuit Performance
.LP
Two primary factors influence the propagation delay along a path
in the circuit;
switching delays of the 
.IX "component" "s"
along the path, and 
interconnection delays caused primarily by resistance and capacitance of the
wiring.
Until recently, propagation delays were not considered
important during placement because the switching delays dominated the
interconnection delays (interconnection delay is the only factor that placement
can influence).  However, fabrication processes are improving and switching
delays are dropping substantially; thus, it is important to consider performance
during the 
.IX "placement"
process since 
.IX "placement"
determines the minimum delays of the 
.IX "net" "s"
of a circuit. Consideration of circuit performance during placement is referred
to as performance-based or timing-driven placement.  
.PP
There are many ways to include performance
considerations in the 
.IX "placement"
process.  However, since 
.IX "placement"
can only impact performance characteristics through the interconnections, all of
the techniques modify the objective function to influence the length and
topology of the wiring paths.  
One performance-based placement system is able to
derive the timing requirements on the 
.IX "net" "s"
as a function of the 
.IX "structural representation" ","
the timing parameters of the cells and the input to output delay requirements of
the circuit [Bur85].  
This system generates all possible paths through the circuit; the criticality of each path is
determined automatically.  Based on the 
.DX "timing margin" ","
(the difference between the required and predicted delay) the 
net priorities are set and placement is performed.
.MH "8.\ \ Conclusion"
.LP
Automated 
.IX "placement"
is important because it greatly influences the amount of and the location of
wiring required to interconnect the 
.IX "component" "s."
The 
.IX "placement"
phase impacts the router's ability to complete the required interconnections, as
well as effects the performance of the circuit.
The 
.IX "placement"
.IX "model" "s"
and algorithms chosen for a particular layout system depend on many factors.
When considering speed versus performance tradeoffs, it is difficult, if not
impossible, to find a single 
.IX "model"
and algorithm which works best for all circuits encountered.  
.PP
This article describes the major 
.IX "placement"
algorithms that are available.  A large number of choices is available because
electronic circuits have a wide variety of attributes that must be considered.
Good 
.IX "placement"
is critical in order to generate high quality layouts.  Inclusion of superior 
.IX "placement"
techniques is therefore essential to the success of a design automation system.
.SH
.LG
References
.TR "Bla84" "Blank, T." "A survey of hardware accelerators used in computer-\
aided design" "\s-2IEEE\s+2 Design and Test of Computers" "vol. 1, no. 3, \
pp. 21-39, 1984"
.BR "Bla85" "Blanks, J. P." "Use of a Quadratic Objective Function for the \
Placement Problem in \s-2VLSI\s+2 Design" "Doctoral Dissertation, Department \
of Electrical Engineering" "University of Texas at Austin, 1985"
.PR "Bre77" "Breuer, M. A." "A class of min-cut placement algorithms" "Proc. \
of the 14th Design Automation Conf." "pp. 284-290, 1977"
.PR "Bur85" "Burstein, M., and M. N. Youssef" "Timing-influenced layout \
designs" "Proceedings of the 22nd Design Automation Conference" "pp. 124-130, \
1985"
.PR "Che84" "Chen, C. C., and E. S. Kuh" "Automatic placement for building \
block layout" "Digest of International Conference on Computer-Aided Design" \
"pp. 90-92, 1984"
.PR "Dai86" "Dai, W., and E. S. Kuh" "Hierarchical floorplanning for building \
block layout" "Digest of Intl. Conf. on Computer-Aided Design" "pp. 454-457, \
1986"
.TR "Dun85" "Dunlop, A. E., and B. W. Kernighan" "A procedure for placement of \
standard-cell \s-2VLSI\s+2 circuits" "\s-2IEEE\s+2 Transactions on \
Computer-Aided-Design of Circuits and Systems" "vol. \s-2CAD\s+2-4, no. 1, \
pp. 92-98, 1985"
.PR "Fra86" "Frankle, J., and R. M. Karp" "Circuit placements and cost bounds \
by Eigenvector decomposition" "Digest of the International Conference on \
Computer-Aided Design" "pp. 414-417, 1986"
.PR "Fid82" "Fiduccia, C. M., and R. M. Mattheyses" "A linear-time heuristic \
for improving network partitions" "Proceedings 19th Design Automation \
Conference" "pp. 175-181, 1982"
.PR "Gre84" "Greene J. W., and K. J. Supowit" "Simulated annealing without \
rejected moves" "Proceedings of the International Conference on Computer \
Design" "pp. 658-663, 1984"
.PR "Han72" "Hanan M., and J. M. Kurtzberg" "Placement techniques" \
"Design Automation of Digital Systems. Volume 1: Theory and \
Techniques" "edited by M. A. \
Breuer, Englewood Cliffs, New Jersey: Prentice-Hall, Inc, pp. 213-282, 1972"
.PR "Han76" "Hanan, M., P. K. Wolff, Sr., and B. J. Agule" "Some experimental \
results on placement techniques" "Proceedings of the 13th Design Automation \
Conference" "pp. 214-224, 1976"
.PR "Han86" "Hancock, J. M., and S. DasGupta" "Tutorial on parallel processing \
for design automation applications" "Proceedings of the 23rd Design Automation \
Conference" "pp. 69-77, 1986"
.PR "Hel77" "Heller, W. R., W. F. Mikhail, and W. E. Donath" "Prediction of \
wiring space requirements for \s-2LSI\s+2" "Proc. of the 14th Design \
Automation Conf." "pp. 32-42, 1977"
.PR "Hua86" "Huang, M. D., F. Romeo, and A. Sangiovanni-Vincentelli" "An \
efficient general cooling schedule for simulated annealing" "Proceedings of \
the International Conference on Computer-Aided Design" "pp. 381-384, \
1986"
.TR "Ker70" "Kernighan, B. W., and S. Lin" "An efficient heuristic procedure \
for partitioning graphs" "Bell System Technical Journal" "vol. 49, no. 2, pp. \
291-307, 1970"
.PR "Kho81" "Khokhani, K. H., A. M. Patel, W. Ferguson, J. Sessa, and D. Hatton" "Placement of variable size circuits on LSI masterslices" "Proceedings of the 18th Design Automation Conference" "pp. 426-434, 1981"
.PR "Kir83" "Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi" "Optimization by \
simulated annealing" "Science" "vol. 220, no. 4598, pp. 671-680, 1983"
.PR "Kra86" "Kravitz, S. A., and R. A. Rutenbar" "Multiprocessor-based \
placement by simulated annealing" "Proceedings of the 23rd Design Automation \
Conference" "pp. 567-573, 1986"
.PR "Kur86" "Kurdahi, F. J., and A. C. Parker" "\s-2PLEST\s+2: a program for area estimation of \s-2VLSI\s+2 integrated circuits" "Proc. of the 23rd Design Automation Conf." "pp. 467-473, 1986"
.PR "Lau79" "Lauther, U." "A min-cut placement algorithm for general cell \
assemblies based on a graph representation" "Proceedings 16th Design \
Automation Conference" "pp. 1-10, 1979"
.PR "Ott86" "Otten, R. H. J. M." "Annealing applied to floorplan design in a \
layout compiler" "Automation '86 High Technology Computer Conference \
Proceedings" "pp. 185-228, 1986"
.PR "Pre79" "Preas, B. T., and W. M. vanCleemput" "Placement algorithms for \
arbitrarily shaped blocks" "Proceedings of the 16th Design Automation \
Conference" "pp. 474-480, 1979"
.PR "Pre85" "Preas, B. T., and C. S. Chow" \
"Placement and routing algorithms for topological integrated circuit layout" \
"Proc. of the Intl. Symposium on Circuits and Systems\fR, pp. 17-20, 1985"
.BR "Pre88" "Preas, B. T., and M. J. Lorenzetti, editors" "Physical Design \
Automation of \s-2VLSI\s+2 Systems" "Menlo Park, California, Benjamin-Cummings \
Publishing Company Inc." "1988"
.TR "Qui79" "Quinn, N. R., and M. A. Breuer" "A force-directed component \
placement procedure for printed circuit boards" "\s-2IEEE\s+2 Transactions on \
Circuits and Systems" "vol. \s-2CAS\s+2-26, pp. 377-388, 1979"
.PR "Sch72" "Schweikert, D. G., and B. W. Kernighan" "A proper model for the \
partitioning of electrical circuits" "Proceedings of the 9th Design Automation \
Workshop" "pp. 57-62, 1972"
.PR "Sec84" "Sechen, C., and A. L. Sangiovanni-Vincentelli" "The timberwolf \
placement and routing package" "Proceedings of the 1984 Custom Integrated \
Circuit Conference" "1984"
.PR "Sha85" "Sha, L., and R. W. Dutton" "An analytical algorithm for placement \
of arbitrarily sized rectangular blocks" "Proceedings of the 22nd Design \
Automation Conference" "pp. 602-608, 1985"
.PR "Spi85" "Spira, P. M., and C. Hage" "Hardware acceleration of gate array \
layout" "Proceedings of the 22nd Design Automation Conference" "pp. 359-366, \
1985"
.TR "Ste61" "Steinberg, L." "The backboard wiring problem: a placement \
algorithm" "\s-2SIAM\s+2 Review" "vol. 3, no. 1, pp. 37-50, 1961"
.PR "Wat86" "Watanabe, H., and B. Ackland" \
"Flute \(em a floorplanning agent for full custom \s-2VLSI\s+2 design" \
"Proceedings of the 23rd Design Automation Conference" "pp. 601-607, 1986"
.PR "Whi84" "White, S. R." "Concepts of scale in simulated annealing" \
"Proceedings of the International Conference on Computer Design" "pp. 646-651, \
1984"