IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO.

6, JUNE 2009 791

Analog Placement Based on

Symmetry-Island Formulation
Po-Hung Lin, Yao-Wen Chang, Member, IEEE, and Shyh-Chang Lin

Abstract—To reduce the effect of parasitic mismatches and by placing the symmetric devices closed to each other. Failure
circuit sensitivity to thermal gradients or process variations for to adequately balance thermal coupling in a differential circuit
analog circuits, some pairs of modules need to be placed symmet- can even introduce unwanted oscillations [3]. Furthermore,
rically with respect to a common axis, and the symmetric modules
are preferred to be placed at closest proximity for better elec- the symmetric modules are preferred to be placed at closest
trical properties. Most previous works handle the problem with proximity for better parasitic matching and other electrical
symmetry constraints by imposing symmetric-feasible conditions properties.
in floorplan representations and using cost functions to minimize
the distance between symmetric modules. Such approaches are
inefficient due to the large search space and cannot guarantee the A. Previous Work
closest proximity of symmetry modules. In this paper, we present
the first linear-time-packing algorithm for the placement with The problem of analog placement considering symmetry
symmetry constraints using the topological floorplan representa- constraints has been extensively studied in the literature. Most
tions. We first introduce the concept of a symmetry island which
is formed by modules of the same symmetry group in a single
of these works used the simulated-annealing (SA) algorithm
connected placement. Based on this concept and the B∗ -tree rep- [4] in combination with floorplan representations to handle
resentation, we propose automatically symmetric-feasible (ASF) symmetry constraints. We can classify these representations
B∗ -trees to directly model the placement of a symmetry island. We into two major categories: 1) the absolute representation and
then present hierarchical B∗ -trees (HB∗ -trees) which can simulta- 2) the topological representation.
neously optimize the placement with both symmetry islands and
nonsymmetric modules. Unlike the previous works, our approach
An absolute representation was proposed by Jepsen and
can place the symmetry modules in a symmetry group in close Gellat [5]. For this representation, each module is associ-
proximity and significantly reduce the search space based on the ated with an absolute coordinate on a gridless plane. It op-
symmetry-island formulation. In particular, the packing time for erates on a module by changing its coordinate directly. The
an ASF-B∗ -tree or an HB∗ -tree is the same as that for a plain KOAN/ANAGRAM II [2], PUPPY-A [6], and LAYLA [7]
B∗ -tree (only linear) and much faster than previous works. Experi-
mental results show that our approach achieves the best-published
systems all adopted the absolute representation to handle the
quality and runtime efficiency for analog placement. placement of analog modules. The main weakness of the ab-
solute method lies in the fact that it may generate an infeasible
Index Terms—Analog circuit, floorplanning, physical design,
placement.
placement with overlapped modules. Therefore, a postprocess-
ing step must be performed to eliminate this condition, which
I. I NTRODUCTION implies a longer computation time.
Recently, most previous works apply topological floor-

F OR ANALOG layout design, some pairs of modules need

to be placed symmetrically with respect to a common axis.
The symmetric placement has several advantages: It reduces
plan representations due to its flexibility and effectiveness.
Balasa et al. derived the symmetric-feasible conditions for
several popular floorplan representations including sequence
the effect of parasitic mismatches which may lead to higher pairs (SPs) [8], O-tree [9], and binary trees [10]. To explore
offset voltages and degrade power-supply rejection ratio [2]. the solution space in the symmetric-feasible binary trees, they
It can also reduce the circuit sensitivity to process variations augmented the B∗ -tree [11] using various data structures, in-
cluding segment trees [3], [12], red–black trees [13], and de-
Manuscript received May 31, 2008; revised October 15, 2008 and January 6, terministic skip lists [14]. Lin et al. [15] also presented the
2009. Current version published May 20, 2009. This paper was presented in part symmetric-feasible conditions for the TCG-S representation.
at the 2007 ACM/IEEE Design Automation Conference (DAC’07) [1]. This
work was supported in part by Springsoft, by Etron, by TSMC, and by the
Three more recent works [16]–[18] further took advantage of
National Science Council of Taiwan under Grants NSC-096-2917-I-002-121, the symmetric-feasible condition in SPs [8]. Koda et al. [16]
NSC 93-2815-C-002-046-E, NSC 94-2215-E-002-005, and NSC 94-2752-E- proposed a linear-programming-based method, and Tam et al.
002-008-PAE. This paper was recommended by Associate Editor H. E. Graeb.
P.-H. Lin is with the Graduate Institute of Electronics Engineering, National
[17] introduced a dummy node and additional constraint edges
Taiwan University, Taipei 106, Taiwan (e-mail: [email protected]). for each symmetry group after obtaining a symmetric-feasible
Y.-W. Chang is with the Graduate Institute of Electronics Engineering and SP. Krishnamoorthy et al. [18] proposed an O(m · n lg lg n)
the Department of Electrical Engineering, National Taiwan University, Taipei
106, Taiwan (e-mail: [email protected]). packing-time algorithm by employing the priority queue, where
S.-C. Lin is with the Physical Design Group, Springsoft, Inc., Hsinchu 300, m is the number of symmetry groups and n is the number
Taiwan (e-mail: [email protected]). of modules. More recently, Zhang et al. [19] further im-
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org. proved the perturbation time of the TCG representation from
Digital Object Identifier 10.1109/TCAD.2009.2017433 O(n2 ) to O(n).
0278-0070/$25.00 © 2009 IEEE
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 792 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

Most of the previous works showed that the symmetric- TABLE I

COMPARISONS OF POPULAR PREVIOUS WORKS AND OUR APPROACHES.
feasible conditions in the topological representations can han- n: THE NUMBER OF MODULES; m: THE NUMBER OF SYMMETRY PAIRS
dle the placement problem with a symmetry group effectively.
However, it is time-consuming to generate a relatively larger
scale placement with several symmetry groups. For example,
Koda et al. [16] reported that it takes almost an hour on a
3.2-GHz Pentium PC to generate a symmetric placement of
110 modules with five symmetry groups.
We observed several problems/deficiencies in the previous
works for analog placement: First, most previous works em-
ployed either an initial scan or a postprocessing with penalty
to avoid or fix the violation of the symmetric-feasible con-
dition for each perturbation during the SA process. There is
no direct representation that can guarantee the symmetric-
feasible condition in the representation itself. It is clear that
such approaches are inefficient due to the large search space and
fixing overheads. Consequently, the previous works using topo- tion requires modules in a symmetry island to be connected,
logical floorplan representations need O(m · n lg lg n) time for which corresponds to common cases in analog placements.
packing n modules. Second, most previous works used cost We can leverage this property to prune the solution subspace
functions or weights to penalize the solution with symmetric formed with nonsymmetry-island placements, leading to effi-
modules far from each other. Obviously, such approaches can- cient and effective operations of the ASF-B∗ -trees. According
not guarantee the close proximity (or even the adjacency) of to our empirical results, in particular, this solution pruning
symmetry modules. does not degrade the resulting solution quality for practical
applications.
Table I compares state-of-the-art previous works using
B. Our Contributions
the topological floorplan representations and our approach
In this paper, we present the first linear-time-packing algo- (ASF-B∗ -tree + HB∗ -tree).
rithm for the placement with symmetry constraints, compared The remainder of this paper is organized as follows.
to the previous works that need O(m · n lg lg n) time. Specif- Section II gives the preliminaries about the symmetry con-
ically, the packing complexity of the previous works [8]–[10], straints, symmetry islands, and the B∗ -tree representation.
[15]–[17], [19] are all O(n2 ) time while those of [3], [12]–[14] Section III presents how to model the placement of a symmetry
need O(n lg n) time (the work in [18] requires O(m · n lg lg n) group as a symmetry island using the ASF-B∗ -tree. Section IV
time, which was the fastest previous work). proposes the hierarchical framework, HB∗ -tree, and Section V
We first introduce the concept of symmetry island that keeps presents our placement algorithm. Section VI reports the exper-
modules of the same symmetry group connected to each other imental results, and finally, Section VII concludes this paper.
so that the circuit sensitivity to thermal gradients or process
variations can be reduced. Based on this concept and the B∗ -
II. P RELIMINARIES
tree representation [11], we propose a representation called au-
tomatically symmetric-feasible (ASF)-B∗ -trees that can model In this section, we first introduce the symmetry constraints
the compacted placement of a symmetry island (i.e., the sym- for analog placement, the definitions of symmetry types, and
metric placement of the modules in a symmetry group). Specif- the concept of symmetry islands. Then, we review the B∗ -tree
ically, an ASF-B∗ -tree corresponds to a symmetry island with a representation in [11] on which this paper is based.
rectilinear placement. It guarantees a symmetric placement and
does not need to verify/fix the symmetric-feasible conditions
A. Symmetry Constraints
during SA perturbations.
We then present a hierarchical framework called hierarchi- Symmetry constraints can be formulated in terms of symme-
cal B∗ -trees (HB∗ -trees) which can simultaneously optimize try types, symmetry groups, symmetry pairs, and self-symmetric
the placement with both symmetry islands and nonsymmetric modules. In analog layout design, a symmetry group may
modules and dynamically update the rectilinear shape for the contain some symmetry pairs and self-symmetric modules with
modules in a symmetry island. In particular, the overall time respect to a certain symmetry type. A symmetry type may
complexity for packing an ASF-B∗ -tree or an HB∗ -tree is correspond to a symmetry axis in either horizontal or vertical
the same as that for a plain B∗ -tree (only linear) and much direction. Fig. 1 shows two different symmetry types with either
faster than previous works. Experimental results based on the vertical or horizontal symmetry axis.
MCNC benchmarks [15] and the real industry designs used For the symmetric placement with the vertical (horizontal)
in [16] show that our approach produces the best published symmetry axis shown in Fig. 1(a) [Fig. 1(b)], a symmetry pair
results and runtime efficiency for analog placement. Further- with two modules of the same dimensions and orientations
more, the scalability of our approach is much better than those should be placed symmetrically along the vertical (horizon-
of the previous works. It should be noted that our formula- tal) symmetry axis. A self-symmetric module whose internal
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 793

denote the respective width and length of the device, and SP

denotes the variation of P under the device spacing Dx

A2P
σ 2 (ΔP ) = + SP2 Dx2 . (3)
WL
We assume that the device dimensions of modules in a
symmetry pair are the same. According to the above equation,
Fig. 1. Two symmetry types. (a) Symmetric placement with the vertical the larger the distance between the symmetry pair, the greater
symmetry axis. (b) Symmetric placement with the horizontal symmetry axis. differences between their electrical properties. Therefore, it
TABLE II is of significant importance for the symmetric devices of a
NOTATIONS IN THIS PAPER symmetry group to be placed in close proximity. Fig. 2(a) shows
an analog circuit of a two-stage CMOS operational amplifier
containing the differential input subcircuit. The devices M 1,
M 2, M 3, M 4, and M 5 in the differential input subcircuit
form a symmetry group S = {(M 1, M 2), (M 3, M 4), M 5}.
Fig. 2(b) and (c) shows two corresponding layouts with dif-
ferent placement styles for the symmetry group S. The layout
style in Fig. 2(c) is generally considered much better than that
in Fig. 2(b) because the symmetric modules of the same sym-
metry group are placed at closer proximity (or even adjacent)
to each other. Consequently, the sensitivities due to process
variations can be minimized, and the circuit performance can
structure is self-symmetric must have its center placed at the be improved.
symmetry axis. Based on the placement with the closest proximity for a
We use the notations listed in Table II throughout this paper. symmetry group as shown in Fig. 2(c), we introduce the concept
Let S = {S1 , S2 , . . . , Sm } be a set of m symmetry groups of symmetry islands and give its definition as follows.
whose coordinate(s) of the symmetry axis (axes) is (are) de- Definition 1: A symmetry island is a placement of a symme-
noted by x̂i or ŷi (x̂i and ŷi ), 1 ≤ i ≤ n. A symmetry group try group in which each module in the group abuts at least one
Si = {(b1 , b1 ), (b2 , b2 ), . . . , (bp , bp ), bs1 , bs2 , . . . , bsq } consists of of the other modules in the same group, and all modules in the
p symmetry pairs and q self-symmetric modules, where (bj , bj ) symmetry group form a connected placement.
denotes a symmetry pair and bsk denotes a self-symmetric mod- We further use the example in Fig. 3 to explain the concept of
ule. Let (xj , yj ) and (xj , yj ) denote the respective coordinates symmetry islands. The symmetry group S1 in Fig. 3(a) forms a
of the centers of two modules bj and bj in a symmetry pair symmetry island but that in Fig. 3(b) does not, since it results in
(bj , bj ), respectively, and (xsk , yks ) denotes the coordinate of two disconnected components. The placement style in Fig. 3(a)
the center of the self-symmetric module bsk . The symmetric is preferred in analog layout design due to its better electrical
placement of a symmetry group Si with the vertical (horizontal) properties.
symmetry axis must satisfy (1) [(2)]
C. Review of B∗ -Trees
xj + xj
= 2 × x̂i ∀j = 1, 2, . . . , p
Since this paper is based on the B∗ -tree representation [11],
yj = yj ∀j = 1, 2, . . . , p we shall first give a brief review over the representation. A
xs k = x̂i ∀k = 1, 2, . . . , q (1) B∗ -tree is an ordered binary tree representing a compacted
xj = xj ∀j = 1, 2, . . . , p placement, in which every module can no longer move left and
yj + yj = 2 × ŷi ∀j = 1, 2, . . . , p bottom. As shown in Fig. 4, every node of a B∗ -tree corresponds
y s k = ŷi ∀k = 1, 2, . . . , q. (2) to a module of a compacted placement. The root of a B∗ -
tree corresponds to the module on the bottom-left corner. For
each node n corresponding to a module b, the left child of n
represents the lowest adjacent module on the right side of b,
B. Symmetry Island
while the right child of n represents the first module above b
Before introducing the symmetry island, we shall first inves- with the same horizontal coordinate.
tigate the effect of the symmetric device layout on the electrical Given a B∗ -tree, we can calculate the coordinate of each
matching properties of the symmetric devices. Pelgrom et al. module by a preorder tree traversal. Suppose the module bi ,
[20] measured the mismatch between MOS transistors with represented by the node ni , has the bottom-left coordinate
various electrical parameters as a function of device areas, dis- (xi , yi ), the width wi , and the height hi . Then, for the left child
tances, and orientations. According to Pelgrom et al. [20], the nj of ni , xj = xi + wi ; for the right child nk of ni , xk = xi .
difference of an electrical parameter P between two rectangular In addition, we maintain a contour structure to calculate the
devices is modeled by the standard deviation, as shown in (3), y-coordinates. Thus, starting from the root node, whose bottom-
where AP is the area proportionality constant for P , W and L left coordinate is (0, 0), then visiting the root’s left subtree and,
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 794 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

Fig. 2. Example analog circuit and two different layout styles for the circuit. (a) Schematic of a two-stage CMOS operational amplifier, where the differential
input subcircuit forms a symmetry group. (b) Layout design of the circuit in (a), where the devices of a symmetry group are not placed close to each other.
(c) Another layout design of the circuit in (a), where the devices of a symmetry group are placed close to each other.

Fig. 3. Two symmetric-placement examples of a symmetry group S1 =

{(b1 , b1 ), (b2 , b2 )}. (a) S1 forms a symmetry island. (b) S1 cannot form a Fig. 5. (a) Placement example of a symmetry group with a vertical symmetry
symmetry island. axis. (b) Selecting a representative for each symmetry pair and self-symmetric
module. (c) ASF-B∗ -tree (also a representative B∗ -tree) representing the place-
ment of the symmetry group, where the dash circled nodes represent the left-
boundary modules.

B∗ -trees, the ASF-B∗ -tree can represent only compacted sym-

metric placement; in particular, there exists a unique corre-
spondence between a compacted symmetric placement of a
symmetry group and its induced ASF-B∗ -tree which results in
Fig. 4. (a) Compacted placement [same as in Fig. 3(a)]. (b) B∗ -tree represent- a symmetry island. We first present the definitions and prop-
ing the compacted placement in (a). erties of the ASF−B∗ -tree and then prove the correspondence
between a symmetry island and its induced ASF-B∗ -tree.
then, its right subtree, this preorder-tree-traversal procedure, Before introducing the ASF-B∗ -tree, we should define the
also known as B∗ -tree packing, calculates all coordinates of representative of a symmetry pair, the representative of a self-
the modules in the placement. Using a doubly linked list to symmetric module, and the representative B∗ -tree.
implement the contour structure, the total packing time is linear Definition 2: The representative brj of a symmetry pair
to the number of modules. (bj , bj ) is bj .
Definition 3: The representative brk of a self-symmetric mod-
ule bsk is the right (top) half of bsk in a symmetric placement with
III. P LACEMENT OF A S YMMETRY G ROUP
respect to a (horizontal) symmetry axis.
In this section, we propose the ASF-B∗ -tree to consider the For the example shown in Fig. 5, the representative br1 of the
symmetric placement of a symmetry group and the packing symmetry pair {b1 , b1 } is b1 , while the representative br0 of the
of the symmetry modules to make a symmetry island. Like self-symmetric module bs0 is the right half of bs0 .
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 795

It should be noted that each symmetry pair or self-symmetric

module must have its own representative module. Therefore, the
number of the representatives in a symmetry group should be
the same as the number of symmetry pairs and self-symmetric
modules. We define the representative B∗ -tree as follows.
Definition 4: A representative B∗ -tree is a B∗ -tree containing
only the representative nodes that correspond to representative
modules. Fig. 6. (a) Placement example of a symmetry group with a horizontal sym-
In the following, we describe how to obtain an ASF-B∗ -tree metry axis. (b) Selecting a representative module for each symmetry pair
by making a representative B∗ -tree symmetric feasible for sym- and self-symmetric module. (c) ASF-B∗ -tree (also a representative B∗ -tree)
representing the placement of the symmetry group, where the dash circled
metric placements with vertical and horizontal symmetry axes. nodes represent the bottom-boundary modules.
We first introduce the mirrored placement of the representative
modules for a symmetry group.
Definition 5: The mirrored placement of the representative w/h and w /h , where w = w and h = h . The representative
modules for a symmetry group Si is to place the nonrepresen- of the symmetry pair (b, b ) is b .
tative modules on the mirrored positions of the representative Given the coordinate of the representative b and the vertical
ones for each symmetry pair or each self-symmetric module in symmetry axis x̂, the coordinate of the symmetric module b can
Si with respect to its symmetry axis (axes). Furthermore, the be calculated by (1). We have x = 2 × x̂ − x and y = y  . After
representative and the nonrepresentative modules of each self- transposing x̂ to the left side and having the absolute value on
symmetric module are not disjointed. both sides, we have |x − x̂| = |x̂ − x |. Since the representative
We are now ready to define the symmetric-feasible condition is not on the symmetry axis, we have |x − x̂| = |x̂ − x | ≥
of a representative B∗ -tree for the symmetric placements. w/2. It means that the distances from the symmetry axis to
Definition 6: A representative B∗ -tree is symmetric feasible the centers of b and b are greater than or equal to half of the
if the mirrored placement of the representative modules can be width of b or b . Since b and b are on different sides of the
obtained after packing the representative B∗ -tree. symmetry axis, b and b will not overlap each other. Therefore,
In Fig. 5(a), the modules in the symmetry group S = the symmetric-feasible condition is always satisfied. The case
{(b1 , b1 ), bs0 , bs2 , bs3 } are placed symmetrically with respect to for a symmetry group with a horizontal symmetry axis can be
the vertical axis. To construct the corresponding representative proved similarly. Q.E.D.
B∗ -tree, we should select the representative module of each According to Lemma 1 and the boundary constraints [21] in
symmetry pair and self-symmetric module and consider the the B∗ -trees, we have the following property for the symmetric-
placement on the right half-plane. Fig. 5(b) shows the rep- feasible representative B∗ -trees representing 1-D symmetric
resentative modules, and Fig. 5(c) shows the corresponding placement.
representative B∗ -tree of the symmetric placement. Each node Property 1: The left-boundary (right-boundary) constraint
in the representative B∗ -tree corresponds to a representative for the symmetric placement with respect to a vertical (horizon-
module. tal) symmetry axis: The representative node of a self-symmetric
To make the representative B∗ -tree symmetry symmetric fea- module should always be on the rightmost (leftmost) branch of
sible, we have the following lemmas which gives the symmetry the representative B∗ -tree.
condition for a self-symmetric module and a symmetry pair. Based on the above property, the nodes representing the mod-
Lemma 1: The representative of a self-symmetric module ules on the left boundary should be on the rightmost branch, as
must abut the symmetry axis. shown in Fig. 5(c).
Proof: Let S be a symmetry group with a vertical symme- Similarly, we can get the symmetric-feasible representative
try axis and bs be a self-symmetric module in S. The symmetry B∗ -tree of the symmetric placement when the symmetry axis
axis of S is denoted by x̂, and the center of bs is denoted by is in the horizontal direction. In this case, we only consider
(xs , y s ). the top half-plane during the placement of the representative
Based on (1), the symmetry axis x̂ always passes through the modules. Fig. 6(c) shows the representative B∗ -tree of the
center (xs , y s ) of the self-symmetric module bs , i.e., x̂ = xs . symmetry group S = {(b0 , b0 ), bs1 , bs2 , bs3 } having the symmet-
According to Definition 3, the representative br of bs is the right ric placement with respect to the horizontal symmetry axis
half of bs . Therefore, the center (xs , y s ) of bs must be on the in Fig. 6(a). Again, the representatives of the self-symmetric
left boundary of br . To keep the symmetric-feasible condition modules should abut the horizontal symmetry axis which is on
x̂ = xs , br must abut the symmetry axis x̂. The case for a the bottom boundary of the top half-plane. Therefore, the nodes
symmetry group with a horizontal symmetry axis can be proved representing the modules on the bottom boundary should be on
similarly. Q.E.D. the leftmost branch, as shown in Fig. 6(c).
Lemma 2: The representative of a symmetry pair not on a Based on Definition 4 and Property 1, we define an ASF-
symmetry axis is always symmetric feasible. B∗ -tree as follows.
Proof: Let S be a symmetry group with a vertical symme- Definition 7: An ASF-B∗ -tree is a representative B∗ -tree
try axis and (b, b ) be a symmetry pair in S. The symmetry axis which satisfies Property 1.
of S is denoted by x̂. The respective centers of b and b are (x, y) Once an ASF-B∗ -tree is packed, the coordinates of these
and (x , y  ), and the respective widths/heights of b and b are representatives are obtained. We can further calculate the
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 796 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

coordinates of their symmetric modules based on (1) and (2)

with the given coordinates of the symmetry axes, x̂i and ŷi .
Then, we have the symmetric placement of a symmetry group,
and it automatically forms a symmetry island.
Based on Lemmas 1 and 2, we have the following theorems.
Theorem 1: An ASF-B∗ -tree is symmetric feasible in a sym-
metric placement of a symmetry group with respect to either a
vertical or a horizontal symmetry axis. Fig. 7. HB∗ -tree for the placement in Fig. 3(a).
Proof: An ASF-B∗ -tree is symmetric feasible if all
the representatives in the ASF-B∗ -tree are symmetric fea-
sible. There are four kinds of representatives, and the
symmetric-feasible condition for each is defined and proved
in Lemmas 1 and 2. Therefore, an ASF-B∗ -tree is symmet-
ric feasible in a symmetric placement of a symmetry group
with respect to either a vertical or a horizontal symmetry
axis. Q.E.D.
Theorem 2: The packing of an ASF-B∗ -tree results in a
symmetry island of the corresponding symmetry group.
Proof: It is obvious that all the representative modules
will form a connected placement after packing. We set the
coordinate(s) of the symmetry axis (axes) to the left or (and) the
bottom boundary (boundaries) of the connected placement of
the representative modules. The coordinates of the symmetric
modules can be calculated by (1) and (2). The symmetric Fig. 8. (a) ASF-B∗ -tree of a symmetry group S0 . (b) Horizontal and vertical
modules also form a connected placement, and the boundary contours of the corresponding placement. (c) Symmetry island and its effective
of the connected placement also abut the symmetry axis (axes). contours. (d) HB∗ -tree for the rectilinear symmetry island.
Therefore, the whole symmetry group forms a connected place-
ment, and each module in the group abuts at least one of the A. HB∗ -Tree Representation
other modules in the same group. The packing of an ASF-B∗ -
Fig. 7 shows an HB∗ -tree for the placement in Fig. 3(a). Two
tree, thus, results in a symmetry island of the corresponding
symmetry groups, S1 and S2 , are represented by two hierarchy
symmetry group. Q.E.D.
nodes, nS1 and nS2 , and each hierarchy node contains an ASF-
Theorem 3: There exists a unique correspondence between
B∗ -tree that corresponds to a symmetry island in the symmetric
a compacted symmetric placement of a symmetry group and its
placement.
induced ASF-B∗ -tree.
The symmetry islands are often not rectangular but are of rec-
Proof: According to Chang et al. [11], there is a unique
tilinear shapes. For example, in Fig. 8(c), the symmetry island
correspondence between an admissible placement and its in-
of the symmetry group S0 is of the rectilinear shape. Therefore,
duced B∗ -tree. After obtaining the placement of the repre-
we should augment the HB∗ -tree in Fig. 7 to handle rectilinear
sentative modules, we simply get the mirrored placement of
symmetry islands. Wu et al. [22] proposed a method to deal
the symmetric ones. The mirrored placement is also unique.
with rectilinear modules by slicing a rectilinear module into
Therefore, there exists a unique correspondence between a
several rectangular submodules along each vertical boundary.
compacted symmetric placement of a symmetry group and its
However, it is complicated to maintain the relationship between
induced ASF-B∗ -tree. Q.E.D.
the submodules during B∗ -tree perturbations.
Based on the earlier theorems, we can correctly find a
Instead of slicing a rectilinear symmetry island, we introduce
corresponding symmetric placement for an ASF-B∗ -tree very
contour nodes to represent top horizontal contour segments of
efficiently, by avoiding searching in redundant solution spaces.
the symmetry island. In Fig. 8(c), there are three horizontal
It will be clear later in Section VI that these nice properties of
contour segments: c00 , c01 , and c02 . We augment the HB∗ -tree
ASF-B∗ -trees lead to superior solution quality and efficiency
by introducing the three contour nodes, n00 , n01 , n02 , as shown
for analog placement.
in Fig. 8(d). Each contour node keeps the coordinates of the
corresponding horizontal contour segment. The relationship of
IV. H IERARCHICAL F RAMEWORK a hierarchy node, its contour nodes, and other regular module
nodes is described as follows.
We propose a hierarchical framework, called hierarchical
Property 2: Properties for an HB∗ -tree.
B∗ -tree (HB∗ -tree for short), to handle the simultaneous place-
ment of modules in symmetry islands and nonsymmetric mod- 1) The left child of a hierarchy node, if any, must be a
ules. In an HB∗ -tree, the symmetry island of each symmetry noncontour node.
group can be in any rectilinear shapes, and symmetry and 2) The right child of a hierarchy node must be the contour
nonsymmetric modules are simultaneously placed to optimize node representing the leftmost top horizontal contour
the placement. segment of the symmetry island.
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 797

3) The left child of a contour node, if any, must be the

contour node representing the next contour segment on
the right side.
4) The right child of a contour node, if any, must be a
noncontour node.
5) The children of a regular module node must be noncon-
tour nodes. Fig. 9. Packing procedure including the contour updates of the ASF-B∗ -tree
6) The parent of a contour node cannot be a regular module in Fig. 8(a).
node.
Proof: Given a symmetry group S0 , bS0 denotes the sym-
metry island of S0 , nS0 denotes the corresponding hierarchy
node, and n0i represents the ith top contour segment of bS0
from left to right.
1) Since the contour node n0i represents the ith top contour
segment of bS0 , it is impossible for n0i to be the left child
of nS0 that corresponds to the lowest adjacent module on Fig. 10. Generation of the bottom contour of the symmetry island based on
the right side of bS0 , based on the B∗ -tree definition. The the dual vertical contours. (a) Convex points obtained by traversing the dual
vertical contours from bottom to top. (b) Bottom horizontal contour connected
property thus follows. by the convex points.
2) According to the definition of the B∗ -tree, the right child
of nS0 represents the first module above bS0 . Since the B. ASF-B∗ -Tree Packing
top horizontal contour segments of bS0 always abut bS0 ,
The packing of the ASF-B∗ -tree is similar to that of the
other modules cannot be placed between bS0 and its top ∗
B -tree [11] which follows the preorder-tree-traversal proce-
contour segments. Therefore, the right child of nS0 must
dure to calculate the coordinates of the modules. During the
be a contour node representing the leftmost top horizontal
packing, two double-linked lists are implemented to keep both
contour segment of bS0 .
horizontal and vertical contour structures. Fig. 9 shows the
3) By the contour-node definition, the contour node n0,i
packing procedure of the example ASF-B∗ -tree in Fig. 8(a). The
represents the ith top contour segment of bS0 from left
bold (red) lines denote the horizontal contour, while the dotted
to right, and the left child of n0,i , if any, is n0,i+1 ,
(green) lines represent the vertical contour.
representing the next [(i + 1)th] contour segments. If n0,i
After obtaining the coordinates of all representative modules
represents the last (the rightmost) top contour segment,
in the symmetry group, we can calculate the coordinates of
the left child of n0i is empty.
the symmetric modules and the extended contours based on
4) The right child of the contour node n0i represents the first
either (1) or (2). Fig. 8(b) shows the resulting placement of the
module above the ith top contour segment of bS0 . If there
symmetry group and the contours of the symmetry island for
exists another contour node n0j that is the right child of
the ASF-B∗ -tree shown in Fig. 8(a). As shown in Fig. 8(b), the
n0i , both contour segments will overlap each other with
symmetry island contains one top horizontal and dual vertical
n0j ’s contour segment on top of that of n0i , implying that
contours. To further calculate the bottom horizontal contour of
n0i is not a contour node. A contraction.
the symmetry island, we need to traverse both vertical contours
5) Based on the second and the third properties of the HB∗ -
from bottom to top and keep the convex points as shown in
tree, the contour node n0i cannot be the left or right child
Fig. 10(a). By connecting the convex points horizontally, we
of a regular module node. The property thus follows.
can obtain the bottom horizontal contour of the symmetry
6) Based on the construction of the HB∗ -tree, the parent of a
island, as shown in Fig. 10(b).
contour node is either a contour node or a hierarchy node.
Q.E.D.
C. HB∗ -Tree Packing
Fig. 8(a) shows the ASF-B∗ -tree of the symmetry group
S0 = {(b0 , b0 ), (b1 , b1 ), (b2 , b2 )}. In Fig. 8(b), the horizontal The HB∗ -tree packing also adopts the preorder-tree-traversal
and vertical contours are obtained from the rectilinear outline procedure. When a hierarchy node is traversed, the ASF-B∗ -
after packing the ASF-B∗ -tree. Fig. 8(c) shows the symmetry tree in the hierarchy node should be packed first to obtain
island and the effective horizontal and vertical contours. The the contours of the symmetry island described previously. The
horizontal contour segments are denoted as c00 , c01 , and c02 contours are then stored in the corresponding hierarchy node.
from left to right. Therefore, we have a hierarchy node nS0 During packing a hierarchy node representing a symmetry
representing the symmetry island of the symmetry group S0 , island, we should calculate the best packing coordinate for the
and three contour nodes n00 , n01 , and n02 representing the bottom boundary of the symmetry island, based on the bottom
contour segments. The relationship between the hierarchy node contour shown in Fig. 10(b). We then proceed to pack the
and its contour nodes is shown in the HB∗ -tree in Fig. 8(d). left child of the hierarchy node. After the left child and all
After introducing the representation and the properties of its descendants are packed, we pack the first contour node of
HB∗ -trees, we present the packing procedure for ASF-B∗ -trees the symmetry island, followed by the second one, and so on.
and HB∗ -trees. When packing the contour nodes, we only need to update their
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 798 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

We first consider the packing for the ASF-B∗ -tree of the

symmetry group Si in a hierarchy node. It consists of two steps.
The first step is the packing for all representative modules.
The second step is the calculation of the coordinate of each
symmetric module.
According to Chang et al. [11], the packing for a B∗ -tree
takes linear time, so the time complexity of the first step is
O(n(Si )). Since it takes constant time to calculate the coor-
dinate of a symmetric module, it also takes O(n(Si )) time to
compute the coordinates of all the symmetric modules in Si .
Combining both steps, we have the O(n(Si )) time complexity
for the packing of an ASF-B∗ -tree of Si .
Second, we consider the packing for the HB∗ -tree. If all the
symmetry islands of m symmetry groups are in a rectangular
shape. We can ignore the contour nodes in the HB∗ -tree, and
it takes O(m + n̂) time to pack the HB∗ -tree. However, if any
symmetry island is in a rectilinear shape, we need to consider
the packing of the hierarchy node representing this symmetry
Fig. 11. (a) HB∗ -tree representing 20 modules with two symmetry groups S0 island, particularly the additional contour nodes.
and S1 . (b) Resulting placement after packing the HB∗ -tree. The bottom contour of the symmetry island of Si is obtained
when the corresponding ASF-B∗ -tree of the symmetry group
coordinates and replace the hierarchy node in the contour data is packed, and the number of the bottom contour segments is
structure of the HB∗ -tree. O(n(Si )). By comparing the current packing contour segments
Fig. 11(a) shows an HB∗ -tree representing 20 modules with and the bottom contour segments of the symmetry island from
two symmetry groups S0 and S1 . For the packing, the two ASF- left to right, it also takes O(n(Si )) time to get the coordinates
B∗ -trees in nS0 and nS1 are packed first, and the rectilinear of the modules in the symmetry island Si .
m
outlines of the two symmetry islands are obtained. Then, the To sum up, it takes O(m  + i=1 n(Si ) + n̂) time to pack
nodes, n5 , n6 , n7 , n8 , and n9 , are packed in the depth-first the HB∗ -tree. Since n = i=1 n(Si ) + n̂, the packing time can
m

search order. The temporal contour list is n5 , n6 , n7 , n9 . By be reduced to O(m + n) time. Since the number of symmetry
calculating the rectilinear outlines between the temporal con- group m is upper bounded by the number of total modules n,
tour list and the bottom boundary of the symmetry island S0 , the packing time is O(n). Q.E.D.
the dead space between the previously packed modules and the It should be noted that this is the fastest algorithm in the lit-
symmetry island can be minimized. The updated temporal con- erature for the placement with symmetry constraints, as shown
tour list becomes nS0 , n7 , n9 . Continuing the packing pro- in Table I.
cedure, we can obtain the resulting placement of the HB∗ -tree
in Fig. 11(b) finally. Although the purpose of the packing is
D. Advanced Symmetry Constraints
to obtain a compacted placement, we might need to allocate
sufficient white space for the surrounding wells or guard rings For some analog layout applications, the symmetry con-
based on the device types, such as NMOS or PMOS transistors. straints could be even more complex than what we have con-
When packing a node, the device type of the corresponding sidered. We brief the handling of two kinds of such symmetry
module should be compared with those of the previously constraints in the following.
packed modules in the current contour list. If the device types 1) Multiple Symmetry-Group Alignment: In some analog
are different, the currently packed module should be snapped to layouts, the symmetry axes of different symmetry groups are
a position to reserve sufficient white space for the surrounding required to be aligned to share a common symmetry axis. To
wells or guard rings. align multiple symmetry groups with respect to a common
We have the following theorem for the packing complexity. vertical (horizontal) symmetry axis, we can insert a zero-
Theorem 4: The packing for an ASF-B∗ -tree or an HB∗ -tree height (zero-width) dummy block right at the left (bottom)
takes linear time. of each to-be-aligned symmetry island. We then introduce a
Proof: Given a design with n modules (including symme- dummy node as the parent of the hierarchy node representing
try and nonsymmetry ones) and m symmetry groups, let n̂ be the corresponding symmetry island in the HB∗ -tree, where the
the number of nonsymmetric modules and n(Si ) be the number hierarchy node is the left (right) child of the dummy node.
of modules in  each symmetry group Si , where n(Si ) ≥ 1. We By adjusting the width (height) of each dummy block, the
have n = n̂ + m i=1 n(Si ). symmetry islands of different symmetry groups can be aligned
For the HB∗ -tree representing the symmetric placement
 of with respect to a common vertical (horizontal) symmetry axis.
the given design, there are m hierarchy nodes, O( m i=1 n(S i )) Such an alignment technique is an extension of the work
contour nodes, and n̂ module nodes. For the ASF-B∗ -tree of in [23].
the symmetry group Si in a hierarchy node, there are O(n(Si )) 2) Hierarchical Symmetry: In some fully symmetric analog
representative nodes. designs, the device layouts should be hierarchically symmetric.
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 799

A symmetry group Si may also contain a self-symmetry group

Sjs and/or a symmetry-group pair (Sk , Sk ). Consequently, the
top-level symmetry group STop contains all device modules
and other symmetry groups hierarchically. Based on the pro-
posed symmetry-island and tree formulations, a hierarchical
tree structure [24] that mixes both the ASF-B∗ -trees and the
HB∗ -trees can be constructed. The optimized fully symmetric
placement with the hierarchical symmetry constraint can then
be obtained by searching a desired configuration of the tree
structure and packing the trees to form the symmetry islands
hierarchically.

E. Application to Hierarchical Clustering Constraint

Fig. 12. Integrating nonsymmetric modules into symmetry groups. (a) Non-
Besides handling the symmetry constraints based on the symmetric modules form the self-symmetric module cluster C1 = {b3 , b4 } in
symmetry-island formulation, the proposed hierarchical frame- the symmetry group S1 = {(b1 , b1 ), (b2 , b2 ), C1s }. (b) Nonsymmetric mod-
work, HB∗ -trees, can also effectively manage the hierarchical ules form two clusters, C2 = {b7 , b8 } and C2 = {b9 }, as a symmetry pair in
the symmetry group S2 = {bs5 , (b6 , b6 ), (C2 , C2 )}.
clustering constraint in analog placement or mixed-signal floor-
planning based on the intrinsic hierarchical tree structure. V. A LGORITHM
Let C = {C1 , C2 , . . . , Cl } be a set of device module clus-
ters. Each cluster contains at least two modules, or one module Our algorithm is based on the SA [4]. Given a set of modules
and one of the other clusters, or two of the other clusters. If the and symmetry constraints as the inputs, we construct an initial
cluster Ci contains the cluster Cj , we call Ci a supercluster and solution represented by an HB∗ -tree and, then, perturb it to
Cj a subcluster. The hierarchical clustering constraint limits all search for a desired configuration until a predefined termination
the device modules and/or subclusters of the same supercluster condition is satisfied. The cost function Φ(P ) of the placement
to a connected placement. is defined in (4), where α and β are user-specified parameters,
To formulate the hierarchical clustering constraint using AP is the area of the bounding rectangle for the placement, and
the HB∗ -trees, each of the hierarchy nodes nC1 , nC2 , . . . , nCl WP is the half-perimeter wire length
denotes a cluster. Each hierarchy node nCi further contains
Φ(P ) = α × AP + β × WP . (4)
another HB∗ -tree to represent the topological relation of the
device modules and/or the subclusters in the supercluster de-
noted by nCi . After hierarchically constructing the HB∗ -trees, A. HB∗ -Tree Perturbation
the placement can be optimized by searching a desired con-
figuration of the HB∗ -trees while the inner placement of each We apply the following operations to perturb an HB∗ -tree.
cluster is connected. 1) Op1: Rotate a module.
2) Op2: Move a node to another place.
3) Op3: Swap two nodes.
F. Consideration of Nonsymmetry-Island Placements In the perturbation, the nonhierarchy nodes have higher prob-
abilities to be selected because rotating, moving, or swapping
In addition to the preferred symmetry-island placements the hierarchy nodes might incur a big jump in finding the next
in analog layouts, the proposed ASF-B∗ -trees and HB∗ -trees solution. It is well known that such a big jump might deteriorate
can also generate a nonsymmetry-island placement by inte- the solution quality during the SA process. It should be noted
grating nonsymmetric modules as a self-symmetric module that, due to the special structure of the HB∗ -tree, we cannot
cluster or a symmetry pair consisting of two module clusters move a nonhierarchy node to the right child of a hierarchy node
in a symmetry group represented by an ASF-B∗ -tree. Fig. 12 or the left child of a contour node. The contour nodes are always
shows two examples, including the symmetric placements and moved along with its hierarchy node which cannot be moved
the corresponding ASF-B∗ -trees, which integrate nonsymmet- individually.
ric module clusters into symmetry groups. In Fig. 12(a), the
nonsymmetric modules, b3 and b4 , form the self-symmetric
B. ASF-B∗ -Tree Perturbation
module cluster C1 in the symmetry group S1 . After packing
the B∗ -tree representing the placement of the nonsymmetric In addition to the aforementioned Op1, Op2, and Op3 for
modules, the representative node nrC1 is introduced in the ASF- HB∗ -tree perturbation, we introduce the operations, Op4 and
B∗ -tree representing a symmetric placement of S1 . Similarly, Op5, to perturb the ASF-B∗ -trees. It should be noted that
in Fig. 12(b), the nonsymmetric modules, b7 , b8 , and b9 , form Property 1 should always be satisfied when perturbing an ASF-
two clusters, C2 and C2 , as a symmetry pair in the symmetry B∗ -tree according to the definition of the ASF-B∗ -trees in
group S2 . In the corresponding ASF-B∗ -tree, the representative Definition 7.
node nrC2 is introduced to denote the larger dimensions of the 1) Op4: Change a representative.
placements of C2 and C2 . 2) Op5: Convert a symmetry type.
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 800 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

Fig. 13. Rotating the self-symmetric module bs1 in the symmetry group
S = {bs0 , bs1 } results in the shape change of its representative br1 . Fig. 14. Changing the representative of the symmetry pair (b1 , b1 ) from b1
to b1 may result in shorter wire length between b1 and b3 .
1) Module Rotation: When rotating modules in a symmetry
group, the corresponding ASF-B∗ -tree is unchanged. We should
consider two cases of symmetry-module rotation.
Case 1) Rotate a symmetry pair.
Case 2) Rotate a self-symmetric module.
In case 1), both modules of a symmetry pair should be rotated
at the same time so that they can still be symmetrically placed Fig. 15. Changing the representative of the self-symmetric module bs1 may
with respect to a symmetry axis. In case 2), after rotating a result in shorter wire length between bs1 and b3 .
self-symmetric module, the shape of its representative should
be updated accordingly, as shown in Fig. 13.
2) Node Movement: When moving a node to another place in
an ASF-B∗ -tree, we should consider the following two cases.
Case 1) Move a node representing the representative of a
symmetry pair.
Case 2) Move a node representing the representative of a
self-symmetric module.
In case 1), we can move the representative node of a sym- Fig. 16. Converting the symmetry type from (a) vertical symmetry to
(b) horizontal symmetry.
metry pair to anywhere in an ASF-B∗ -tree. In case 2), however,
we can only move the representative node of a self-symmetric
module along the rightmost (leftmost) branch of the ASF-
B∗ -tree for vertical (horizontal) symmetric placement so that
Property 1 is satisfied.
3) Node Swapping: When swapping two nodes in an ASF-
B∗ -tree, we consider the following two cases.
Case 1) Both nodes represent the representatives of two
different symmetry pairs.
Fig. 17. Converting the symmetry type from (a) horizontal symmetry to
Case 2) At least one node represents the representative of a (b) vertical symmetry.
self-symmetric module.
In case 1), we can arbitrarily swap two nodes representing the according to its symmetry axis. As shown in Fig. 15, changing
representatives of two different symmetry pairs. However, we the representative of the self-symmetric module bs1 by flipping
should be very careful for case 2). If at least one of the swapped it horizontally may result in shorter wire length between bs1 and
nodes represents the representative of a self-symmetric module, b3 . Obviously, each operation takes constant time.
the other node must be located on the same branch (i.e., the left- 5) Symmetry-Type Conversion: For symmetry-type conver-
most or the rightmost branch) of the ASF-B∗ -tree. Therefore, sion of a symmetry group, we should consider both conversions
Property 1 is still satisfied after node swapping. between the vertical symmetry and the horizontal one.
4) Representative Change: The purpose of changing a rep- Case 1) Convert the symmetry type from vertical symmetry
resentative for a symmetry pair or a self-symmetric module is to to horizontal one.
optimize the wire length, while the area is kept unchanged after Case 2) Convert the symmetry type from horizontal symme-
changing the representative. We can change the representative try to vertical one.
of either a symmetry pair or a self-symmetric module. To convert the symmetry type of a symmetry group from
Case 1) Change the representative of a symmetry pair. vertical symmetry to horizontal one or vice versa, we first rotate
Case 2) Change the representative of a self-symmetric every module including the representative and, then, swap the
module. left and the right children of each node in the given ASF-B∗ -
In case 1), for a symmetry pair (bj , bj ), we can simply change tree. Figs. 16 and 17 show the respective examples for the
the representative from bj to bj or from bj to bj . Fig. 14 shows conversions of cases 1) and 2).
that changing the representative of the symmetry pair (b1 , b1 ) It should be noted that the symmetry type is usually pre-
from b1 to b1 may result in shorter wire length between b1 and defined based on the power/ground lines or signal flows in
b3 . Similarly, in case 2), for a self-symmetric module bsk , we can the layout by the analog designers. Therefore, Op5 is seldom
change its representative by flipping it horizontally or vertically applied in real applications.
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 801

TABLE III
MCNC BENCHMARK CIRCUITS

TABLE IV
INDUSTRY BENCHMARK CIRCUITS

The placement of S0 forms a new symmetry island, as shown in

Fig. 18(b) which has only one top contour segment. Therefore,
the contour nodes n01 and n02 disappear, and the nodes n3 and
n5 become dangling nodes. We first find the nearest contour
node of n3 , which is n00 . Since n00 already has the right child
n2 , the leftmost skewed child of n2 should be searched. In this
case, we directly assign n3 to be the left child of n2 because n2
has no left child. After n3 is assigned to a proper tree location,
the nearest contour node of n5 is then searched, which is also
n00 . Since n00 already has the right child n2 , the leftmost
skewed child is searched, which is n3 . We assign n3 to be the
parent of n5 , and n5 is the left child of n3 .
Fig. 18. Example of updating contour-related nodes. (a) HB∗ -tree and its
corresponding placement containing the symmetry group S0 = {(b0 , b0 ),
(b1 , b1 )}. (b) Intermediate HB∗ -tree after perturbing the ASFB∗ -tree in the hi-
erarchy node nS0 and the corresponding symmetry island of S0 . The contour- VI. E XPERIMENTAL R ESULTS
related nodes, n3 and n5 , become dangling. (c) HB∗ -tree after updating the
contour-related nodes and its corresponding placement. We implemented our placement algorithm in the C++ pro-
gramming language on a 3.2-GHz Intel Pentium4 PC under the
C. Contour-Node-Related Updates Linux operating system. We performed two sets of experiments:
One is based on the four MCNC benchmarks (apte, hp, ami33,
Once an ASF-B∗ -tree is perturbed, the number of the cor-
and ami49) used in [15], and the other consists of two real
responding contour nodes in the HB∗ -tree might be changed.
industry analog designs (biasynth_2p4g and lnamixbias_2p4g)
The tree structure might have to be updated accordingly. If the
used in [12] and [16] (note that they both were extracted by
number of contour nodes representing the horizontal contour
Koda et al. [16] from [12, Figs. 9 and 10]). Table III lists
segments of the symmetry island is increased, the structure of
the names of the MCNC benchmark circuits (“Circuit”), the
the HB∗ -tree can be kept unchanged. However, if that of the
numbers of modules (“# of Mod.”), the numbers of sym-
contour nodes is decreased, some other nodes in the HB∗ -tree
metry modules (“# of Sym. Mod.”), and the total module
might not have parents. We call such nodes dangling node,
areas (“Mod. Area”). Table IV lists the names of the indus-
and we should reassign new parents for these nodes. To keep
try benchmark circuits (“Circuit”), the numbers of modules
the relative placement topology before and after perturbing an
(“# of Mod.”), the numbers of symmetry modules (“# of
ASF-B∗ -tree, we first find the nearest contour node for each
Sym. Mod.”), and the total module areas (“Mod. Area”).
dangling node. If the nearest contour node has no right child,
Our approach is based on SA. A left skewed HB∗ -tree was
it is the parent of the dangling node, and the dangling node
constructed as the initial solution. The initial temperature T0
will be its right child. If the nearest contour node has a right
was calculated by (5), where Δavg is the average uphill cost and
child, we continuously traverse the leftmost skewed child of
P is the initial probability to accept uphill solutions. During the
the right child. The leftmost skewed child will be the parent of
SA process, the temperature was reduced at the rate of 0.9 for
the dangling node, and the dangling node is assigned to its left
each subsequent pass, and 20 000 iterations were performed at
child. It takes amortized constant time to update the contour-
each temperature/pass
related nodes.
Fig. 18 shows an example of updating contour-related nodes. T0 = −Δavg / ln P. (5)
In Fig. 18(a), there are initially three contour nodes representing
the three top contour segments of the symmetry island of the In the first set of experiments, we compared our algorithm
symmetry group S0 . After performing Op2 to perturb the ASF- with the following works: SPs [8], segment trees [3], TCG-S
B∗ -tree in nS0 , the representative node nr1 is moved from the [15], and SPs with dummy nodes [17]. Table V lists the names
left child to the right child of the other representative node nr0 . of the MCNC benchmark circuits (“Circuit”), the total areas
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 802 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

TABLE V
COMPARISONS OF AREA UTILIZATION AND CPU TIMES FOR SP (ON SUN SPARC ULTRA-60 433 MHz), SEGMENT TREE (SEG. TREE) (ON SUN SPARC
ULTRA-60 433 MHz), TCG-S (ON SUN SPARC ULTRA-60 433 MHz), SP WITH DUMMY NODES (SP w. DUMMY) (ON PENTIUM4 3.2 GHz),
AND O UR HB∗ -T REE ( ON P ENTIUM 4 3.2 GHz) W ITH A REA O PTIMIZATION A LONE , S AME AS THE P REVIOUS W ORKS , AND W ITH
SIMULTANEOUS AREA AND WIRE-LENGTH OPTIMIZATION [HB∗ -TREE (AREA+WL)], BASED ON THE MCNC BENCHMARKS

TABLE VI
COMPARISONS OF AREA UTILIZATION AND CPU TIMES FOR SP (ON SUN BLADE 100 500 MHz), SEGMENT TREE (SEG. TREE)
(ON SUN BLADE 100 500 MHz), SP+LP (PENTIUM4 3.2 GHz), SP WITH DUMMY NODES (SP w. DUMMY) (ON PENTIUM4 3.2 GHz),
AND HB∗ -T REE ( ON P ENTIUM 4 3.2 GHz), B ASED ON T WO R EAL I NDUSTRY B ENCHMARKS

(“Area”), and the runtimes (“Time”) for the aforementioned

works and our HB∗ -tree with area optimization alone, same as
the previous works, and with simultaneous area and wire-length
optimization. The results of the works in [3], [8], and [15] are
taken from [15], and those of [17] are based on the package
provided by the authors. The results show that our HB∗ -tree
achieves average area reductions of 3%, 2%, 1%, and 2% over
[3], [8], [15], and [17], respectively. Note that the improvements
should not be considered marginal, since the previous works
have pushed the solution quality close to their limits. The main
reason for the area improvement over the previous works is
that our approach benefits from both the symmetry-island for-
mulation and the short packing time of the proposed floorplan
representations. Based on the symmetry-island formulation, the
undesired solutions are pruned, and thus, we do not waste the
time to search inferior solutions during SA. With the short
packing time, we can search for more solutions within the same
time limit. Consequently, our approach has greater possibility
to find better solutions in shorter running time. For the running
time, our algorithm is about 4.09× faster than in [17]. Since
all other previous works ran on different platforms, it is not
easy to report the speedups of our algorithm. Nevertheless, it
is obvious from the table that our algorithm runs much faster
Fig. 19. Resulting placement of ami49 with simultaneous area and wire-
than the previous works. length optimization, which contains the symmetry group, S = {(b19 , b21 ),
In the second set of experiments, we compared our algo- bs30 , bs48 }.
rithm with SPs in [8], segment trees in [12], SPs with linear
programming in [16], and SPs with dummy nodes in [17]. be changed. To make fair comparisons with the previous works,
Table VI lists the names of the industry benchmark circuits, we also performed our algorithm without module rotation. Our
the total areas, and the runtime for SPs, segment trees, SPs results show only 2.4% and 4% area overheads without the
with linear programming, SPs with dummy nodes, and HB∗ - rotation, compared to the results of SPs with linear program-
tree. The results show that our algorithm achieved average ming [16] and our approach, respectively. For the running time,
area reductions of 7.1%, 6.6%, 1.6%, and 10.3% over [8], our approach achieves significant speedups over the previous
[12], [16], and [17], respectively. In some applications, the works, which is about 39.88× and 5.68× faster than those
orientations of analog device modules may not be allowed to in [16] and [17], respectively. Again, the previous works [8],
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 LIN et al.: ANALOG PLACEMENT BASED ON SYMMETRY-ISLAND FORMULATION 803

Fig. 20. Resulting placement of biasynth_2p4g with three symmetry groups. (a) Resulting placement without module rotation. (b) Resulting placement with
module rotation.

[12] ran on different platforms, and thus, we do not report the ACKNOWLEDGMENT
corresponding speedups; yet, it is obvious that our algorithm
The authors would like to thank Prof. E. F. Y. Young and
runs much faster than the previous works. It is clear from the
Y.-C. Tam of the Chinese University of Hong Kong for provid-
two experiments that our algorithm achieves the best quality
ing the package of their work [17] for the comparative studies.
and efficiency than all published works.
Fig. 19 shows the resulting placement of ami49 with si-
multaneous area and wire-length optimization, which contains R EFERENCES
the symmetry group S = {(b19 , b21 ), bs30 , bs48 }. Fig. 20 shows
[1] P.-H. Lin and S.-C. Lin, “Analog placement based on novel symmetry-
the resulting placements of biasynth_2p4g with the symmetry island formulation,” in Proc. ACM/IEEE Des. Autom. Conf., Jun. 2007,
modules being colored. pp. 465–470.
[2] J. Cohn, D. Garrod, R. Rutenbar, and L. Carley, “KOAN/ANAGRAM II:
New tools for device-level analog placement and routing,” IEEE J. Solid-
VII. C ONCLUSION AND F UTURE W ORK State Circuits, vol. 26, no. 3, pp. 330–342, Mar. 1991.
[3] F. Balasa, S. Maruvada, and K. Krishnamoorthy, “Efficient solution space
We have proposed the first linear-time-packing algorithm exploration based on segment trees in analog placement with symme-
try constraints,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Des.,
for the placement with symmetry constraints, based on the Nov. 2002, pp. 497–502.
symmetry-island formulation that prunes the solution subspace [4] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization
by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680,
formed with nonsymmetry-island placements. We have intro- May 1983.
duced the concept of symmetry islands and presented the ASF- [5] D. Jepsen and C. Gelatt, Jr., “Macro placement by Monte Carlo anneal-
B∗ -trees to directly model the placement of a symmetry island. ing,” in Proc. IEEE Int. Conf. Comput. Des., Nov. 1983, pp. 495–498.
[6] E. Malavasi, E. Charbon, E. Felt, and A. Sangiovanni-Vincentelli,
We have also presented the hierarchical HB∗ -trees to simultane- “Automation of IC layout with analog constraints,” IEEE Trans.
ously optimize the placement with both symmetry islands and Comput.-Aided Design Integr. Circuits Syst., vol. 15, no. 8, pp. 923–942,
nonsymmetric modules. Experimental results have shown that Aug. 1996.
[7] K. Lampaert, G. Gielen, and W. Sansen, “A performance-driven place-
our approach achieves the best-published quality and runtime ment tool for analog integrated circuits,” IEEE J. Solid-State Circuits,
efficiency for analog placement. vol. 30, no. 7, pp. 773–780, Jul. 1995.
Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.
 804 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 28, NO. 6, JUNE 2009

[8] F. Balasa and K. Lampaert, “Symmetry within the sequence-pair repre- Yao-Wen Chang (S’94–A’96–M’96) received the
sentation in the context of placement for analog design,” IEEE Trans. B.S. degree from National Taiwan University (NTU),
Comput.-Aided Design Integr. Circuits Syst., vol. 19, no. 7, pp. 721–731, Taipei, Taiwan, in 1988, and the M.S. and Ph.D.
Jul. 2000. degrees from the University of Texas at Austin in
[9] Y. Pang, F. Balasa, K. Lampaert, and C.-K. Cheng, “Block placement with 1993 and 1996, respectively, all in computer science.
symmetry constraints based on the o-tree non-slicing representation,” in He is a Professor in the Department of Electrical
Proc. ACM/IEEE Des. Autom. Conf., 2000, pp. 464–467. Engineering and the Graduate Institute of Electron-
[10] F. Balasa, “Modeling non-slicing floorplans with binary trees,” in Proc. ics Engineering, NTU. He is currently also a Vis-
IEEE/ACM Int. Conf. Compu.-Aided Des., 2000, pp. 13–16. iting Professor at Waseda University, Kitakyushu,
[11] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B∗ -trees: A Japan. He was with National Chiao Tung University
new representation for non-slicing floorplans,” in Proc. ACM/IEEE Des. (NCTU), Hsinchu, Taiwan from 1996 to 2001 and
Autom. Conf., 2000, pp. 458–463. IBM T. J. Watson Research Center in the summer of 1994. His current research
[12] F. Balasa, S. Maruvada, and K. Krishnamoorthy, “On the exploration interests lie in VLSI physical design, design for manufacturability/reliability,
of the solution space in analog placement with symmetry constraints,” and design automation for biochips. He has been working closely with industry
IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 23, no. 2, in these areas. He has co-edited one textbook on EDA and coauthored one book
pp. 177–191, Feb. 2004. on routing and over 150 ACM/IEEE conference/journal papers in these areas.
[13] F. Balasa, S. Maruvada, and K. Krishnamoorthy, “Using red–black inter- Dr. Chang is a winner of the 2009 ACM ISPD Clock Network Synthesis
val trees in device-level analog placement with symmetry constraints,” Contest, the 2008 ACM ISPD Global Routing Contest, and the 2006 ACM
in Proc. IEEE/ACM Asia South Pacific Des. Autom. Conf., Jan. 2003, ISPD Placement Contest. He is a recipient of Best Paper Award at ICCD-95
pp. 777–782. and 12 Best Paper Award Nominations from DAC (four times), ICCAD (twice),
[14] S. Maruvada, A. Berkman, K. Krishnamoorthy, and F. Balasa, “Determin- ISPD (three times), ACM TODAES, ASP-DAC, and ICCD in the past eight
istic skip lists in analog topological placement,” in Proc. IEEE Int. Conf. years. He has received many research awards, such as the 2007 Outstanding
ASIC, Oct. 2005, vol. 2, pp. 834–837. Research Award, the inaugural 2005 First-Class Principal Investigator Award,
[15] J.-M. Lin, G.-M. Wu, Y.-W. Chang, and J.-H. Chuang, “Placement with and the 2004 Dr. Wu Ta You Memorial Award, all from National Science
symmetry constraints for analog layout design using TCG-S,” in Proc. Council of Taiwan, and the 2004 MXIC Young Chair Professorship from the
IEEE/ACM Asia South Pacific Des. Autom. Conf., Jan. 2005, vol. 2, MXIC Corp, and excellent teaching awards from NTU (five times) and NCTU.
pp. 1135–1138. He is currently an associate editor of IEEE TRANSACTIONS ON COMPUTER-
[16] S. Koda, C. Kodama, and K. Fujiyoshi, “Linear programming-based cell
AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS (TCAD) and an
placement with symmetry constraints for analog IC layout,” IEEE Trans.
editor of the Journal of Information Science and Engineering (JISE) and the
Comput.-Aided Design Integr. Circuits Syst., vol. 26, no. 4, pp. 659–668,
Journal of Electrical and Computer Engineering (JECE). He has served on
Apr. 2007.
the ICCAD Executive Committee, the ASP-DAC Steering Committee, the
[17] Y.-C. Tam, Y. Young, and C. Chu, “Analog placement with symmetry
ACM/SIGDA Physical Design Technical Committee, the ACM ISPD and IEEE
and other placement constraints,” in Proc. IEEE/ACM Int. Conf. Comput.-
FPT Organizing Committees, and the technical program committees of ASP-
Aided Des., Nov. 2006, pp. 349–354.
[18] K. Krishnamoorthy, S. Maruvada, and F. Balasa, “Topological placement DAC, DAC, DATE, FPL, FPT, GLSVLSI, ICCAD, ICCD, IECON, ISPD,
with multiple symmetry groups of devices for analog layout design,” in SOCC, TENCON, and VLSI-DAT. He is currently an independent board di-
Proc. IEEE Int. Symp. Circuits Syst., May 2007, pp. 2032–2035. rector of Genesys Logic, Inc., a technical consultant of RealTek Semiconductor
[19] L. Zhang, C.-J. R. Shi, and Y. Jiang, “Symmetry-aware placement with Corp., a member of board of governors of Taiwan IC Design Society, and a
transitive closure graphs for analog layout design,” in Proc. IEEE/ACM member of the IEEE Circuits and Systems Society, ACM, and ACM/SIGDA.
Asia South Pacific Des. Autom. Conf., Mar. 2008, pp. 180–185.
[20] M. Pelgrom, A. Duinmaijer, and A. Welbers, “Matching properties of
MOS transistors,” IEEE J. Solid-State Circuits, vol. 24, no. 5, pp. 1433–
1439, Oct. 1989.
[21] J.-M. Lin, H.-E. Yi, and Y.-W. Chang, “Module placement with boundary
constraints using B∗ -trees,” Proc. Inst. Elect. Eng.—Circuits, Devices
Syst., vol. 149, no. 4, pp. 251–256, Aug. 2002.
[22] G.-M. Wu, Y.-C. Chang, and Y.-W. Chang, “Rectilinear block placement
using B∗ -trees,” ACM Trans. Design Autom. Electron. Syst., vol. 8, no. 2,
pp. 188–202, Apr. 2003.
[23] M.-C. Wu and Y.-W. Chang, “Placement with alignment and performance
constraints using the b∗ -tree representation,” in Proc. IEEE Int. Conf.
Comput. Des., Oct. 2004, pp. 568–571.
[24] P.-H. Lin and S.-C. Lin, “Analog placement based on hierarchical module
clustering,” in Proc. ACM/IEEE Des. Autom. Conf., Jun. 2008, pp. 50–55.

Po-Hung Lin received the B.S. and M.S. degrees in

electronics engineering from National Chiao Tung
University, Hsinchu, Taiwan, in 1998 and 2000, re- Shyh-Chang Lin received the B.S. degree in control
spectively. He is currently working toward the Ph.D. engineering from National Chiao Tung University,
degree in the Graduate Institute of Electronics Engi- Hsinchu, Taiwan, in 1989 and the M.S. and Ph.D.
neering, National Taiwan University, Taipei, Taiwan. degrees in electrical engineering from Michigan
From 2000 to 2007, he was with Springsoft, Inc., State University, East Lansing, in 1993 and 1997,
Hsinchu. In 2008, he was a Visiting Scholar in the respectively.
Department of Electrical and Computer Engineer- He is currently with the Physical Design Group,
ing, University of Illinois at Urbana–Champaign, Springsoft, Inc., Hsinchu. His research interests in-
Urbana. His research interests include analog design clude analog layout automation and physical design
automation and very large scale integration physical synthesis. automation for very large scale integration.

Authorized licensed use limited to: University of Science & Technology of China. Downloaded on January 21,2024 at 14:44:58 UTC from IEEE Xplore. Restrictions apply.