VLSI circuit partitioning by cluster-removal using iterative improvement techniques.
Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm and Krishnamurthy's Look-Ahead (LA) algorithm are widely used in VLSI CAD applications largely due to their time efficiency and ease of implementation. This class of algorithms is of the "local improvement" type. They generate relatively high quality results for small and medium size circuits. However, as VLSI circuits become larger, these algorithms are not so effective on them as direct partitioning tools. We propose new iterative-improvement methods that select cells to move with a view to moving clusters that straddle the two subsets of a partition into one of the subsets. The new algorithms significantly improve partition quality while preserving the advantage of time efficiency. Experimental results on 25 medium to large size ACM/SIGDA benchmark circuits show up to 70% improvement over FM in cutsize, with an average of per-circuit percent improvements of about 25%, and a total cut improvement of about 35%. They also outperform the recent placement-based partitioning tool Paraboli and the spectral partitioner MELO by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of iterative improvement algorithms in dealing with the increasing complexity of modern VLSI circuitry.
INTRODUCTION
The essence of VLSI circuit partitioning is to divide a circuit
into a number of subcircuits with minimum interconnections
between them. This can be accomplished by recursively
partitioning a circuit into two parts until we reach the
desired level of complexity. Thus two-way partitioning is a
basic problem in circuit partitioning and placement.
Kernighan and Lin [1] proposed the well-known KL
heuristic for graph partitioning. The KL algorithm starts
with a random initial two-way partition and proceeds by
swapping pair of cells iteratively. Schweikert and Kernighan
extended KL to hypergraphs so that it can partition
actual circuits. Fiduccia and Mattheyses [3] reduced the
complexity of the algorithm to linear-time with respect
to the number of pins in the circuit. This is done by
moving one cell at a time and using an efficient bucket
data structure. Krishnamurthy [4] enhanced FM by adding
higher level lookahead gains and improved the results for
small circuits. Recently, a number of clustering algorithms
[9, 10, 11, 12, 15] have been proposed and excellent results
have been obtained.
FM and LA are the most commonly used two-way partitioning
algorithms largely due to their excellent run times,
simple implementations and flexibility. However, this class
of iterative improvement algorithms have a common weak-
ness, viz., they only find solutions corresponding to local
minima. Because of their iterative improvement nature,
they can only evolve from an initial partition through very
shortsighted moves. Thus the results strongly depend on
the initial partition. In order to get a local minimum that
is close to the optimum partition, multiple runs on randomly
generated initial partitions are needed. As the circuit
size becomes large, the probability of finding a good
local minimum in one run will drop significantly. This
makes FM an unattractive choice for partitioning large cir-
cuits. As will become clear later, FM gives good results
on small to medium size circuits, but performs very poorly
on large circuits. Some clustering [8] or compaction [15]
techniques have been proposed to remedy the above weak-
ness. Very good results have been obtained at the cost of
considerable CPU time increases and implementation com-
plexities. In this paper, we will propose a technique that
significantly improves the ability of iterative improvement
methods like FM and LA for finding good local minima.
The new technique pays more attention to the neighbors of
moved cells and encourages the successive moves of closely
connected cells. This implicitly promotes the move of an
entire densely-connected group (a cluster) into one subset
of the partition. The large reduction in both the minimum
and average cutsize of multiple runs indicates that
the new technique is a more robust and stable approach.
The increase in implementation complexity and run time is
minimal. We also propose a sophisticated extension of this
basic technique, which explicitly identifies clusters during
the move sequence, and dynamically adapts the move sequence
to facilitate the move of clusters into one subset
of the partition. Very good results have been obtained at
reasonable CPU times.
In the next section, we briefly describe the FM and LA
algorithms and point out their shortcomings. Then in Section
3. we present our rationale for the new technique mentioned
above, and also propose a cluster-detecting algorithm
based on iterative improvement methods. Extensive experimental
results are presented in Section 4. along with dis-
cussions. Conclusions are in Section 5.
2. PREVIOUS ITERATIVE IMPROVEMENT
ALGORITHMS
A circuit netlist is usually modeled by a hypergraph
E), where V is the set of cells (also called nodes) in the
circuit, and E is the set of nets (also called hyperedges). We
will represent a net n i as a set of the cells that it connects.
A two-way partition of G is two disjoint subsets V1 and V2
such that each cell v 2 V belongs to either V1 or V2 . A net
is said to be cut if it has at least one cell in each subset
and uncut otherwise. We call this the cutstate of the net.
All the nets that are cut form a set called the cutset. The
objective of a two-way partitioning is to find a partition that
minimizes the size of the cutset (called the cutsize). Usually
there is a predetermined balance criterion on the size of the
subsets V1 , V2 , for example, 0:45 - jV i
2.
The FM algorithm [3] starts with a random initial par-
tition. Each cell u is assigned a gain g(u) which is the
immediate reduction in cutsize if the cell is moved to the
other subset of the partition:
where E(u) is the set of nets that will be immediately moved
out of the cutset on moving cell u, and I(u) is the set of
nets that will be newly introduced into the cutset. Put in
another way, a net in E(u) has only u in u's subset, and a
net in I(u) has all its cells in u's subset. c(n i ) is the weight
(cost) of the net n i which is assumed to be unity in this
paper unless otherwise specified.
The goal of FM is to move a cell at a time from one
subset to the other subset in an attempt to minimize the
cutsize of the final partition. The cell being selected for
the current move is called the base cell. At the start of the
process, the cell with maximum gain value in both subsets
is checked first to see if its move will violate the balance
criterion. If not, it is chosen as the base cell. Otherwise,
the cell with maximum gain in the other subset is chosen
as the base cell. The base cell, say u1 , is then moved to
the other subset and "locked"-the locking of a moved cell
is necessary to prevent thrashing (a cell being moved back
and forth) and being trapped in a bad local minimum. The
reduction in cutsize (in this case, the gain g(u1)) is inserted
in an ordered set S. The gains of all the affected neighbors
are updated-a cell v is said to be a neighbor of another
cell u, if v and u are connected by a common net. The
next base cell is chosen in the same way from the remaining
"free" (unlocked) cells and the move process proceeds until
all the cells are moved and locked. Then all the partial
are computed, and p is
chosen so that the partial sum Sp is the maximum. This
corresponds to the point of minimum cutsize in the entire
moving sequence. All the cells moved after up are reversed
to their previous subset so that the actually moved cells are
upg. This whole process is called a pass. A number
of passes are made until the maximum partial sum Sp is no
longer positive. This is a local minimum with respect to
the initial partition [V1 ; V2 ].
The FM algorithm has been criticized for its well-known
shortsightedness [4, 13]-it moves a cell based on the immediate
decrease in cutsize. Thus it tends to be trapped
in local minima that strongly depend on the initial random
partition. We will later point out some other consequences
of this shortsightedness that are related to the removal of
natural clusters, which occur in real circuits, from the cut-set

The FM gain calculation only considers critical nets
whose cutstate will change immediately after the move of
the cell. It is conceivable there will be many cells having
the same gain value since the gain is bounded above by pmax
and below by \Gammap max , where pmax is the maximum degree
of a cell. Krishnamurthy has proposed a lookahead gain
calculation scheme which includes less critical nets [4]. In
addition to FM gain, higher order gains are used to break
the ties.
3. CLUSTERING-BASED ITERATIVE
IMPROVEMENT METHODS
3.1. Case for a Cluster-Oriented Approach
A real VLSI circuit netlist can be visualized as an aggregation
of a number of highly connected subcircuits or clusters.
This fact has motivated the proposition of many clustering-based
algorithms. It is conceivable that there are many levels
of clusters with different degrees in the density of their
connectivities. A small group of densely interconnected cells
may be part of a larger but less densely connected cluster.
The goal of two-way partitioning is to determine a cut that
goes through the most weakly connected groups.
Iterative improvement algorithms like FM and LA start
with a randomly assigned partition that results in a binomial
distribution of cells in V1 and V2 . In such a distribu-
tion, the probability of finding r (r - m) cells in V1 and
in V2 in some group of m cells is:
r
where p (q) is the probability of a cell being assigned to V1
(V2 ). For a random partition, 0:5. The probability
distribution maximizes at deviation
m=2. For example, a group of 100 cells will have
the expected distribution of 50 cells in each subset with
a standard deviation of 5 cells. Therefore, for a cluster
with a fair number of cells, there is a very high probability
that it will initially be cut. Hence in an initial random
partition, most clusters will straddle the cutline, which is
an imaginary line that divides the cells into the two subsets
of the partition. This situation is illustrated in Figure 1(a).
For an iterative improvement algorithm to succeed, it
must be able to pull clusters straddling the cutline into one
subset. It is easy to visualize that there will be many cells
in different clusters with similar situations and therefore
the same gain values. Since there is no distinction between
cells with the same gain values but belonging to different
clusters, the FM algorithm may well start to work on many
clusters simultaneously, trying to pull them out of unfavorable
situations. However, cell movement is a two-way
process, and while some cells in a cluster are moved from
V2 to V1 , other cells in the same cluster might be moved
from V1 to V2 . Thus the cluster can be locked in the cutset
at an early stage -a cluster is said to be locked in the cutset
if it has locked cells in both subsets of the partition. This
is the situation of clusters C1 and C2 in Figure 1(b). Un-
fortunately, the moves made at an early stage (before the
maximum partial sum point) are the actual moves. Hence
these clusters will not be pulled out from the cutset in the
current pass, and in later passes the same scenario may
reappear.
Undoubtedly, FM does a good job of pulling small and
highly connected clusters to one side. This is because many
nets of a small cluster will be incident on each cell of the
cluster, and thus their gains capture significant information
about the cluster. Once a cell is moved from V1 to V2 , its
neighbors in V1 might have their gains raised and hence have
a better chance of being moved to V2 , while its neighbors in
V2 will get a negative gain contribution from nets connected
to the moved cell and hence tend to stay in V2 . Therefore a
small cluster has a good likelihood of being moved entirely
to V2 . However, when the size of a cluster is large, its
(b)
(a) (c)
Cutline Cutline Cutline

Figure

1. (a) In the initial partition, clusters straddle the cut-
line as a result of random cell assignment. (b) FM locks clusters
on the cutline by moving cells within one cluster in both direc-
tions. (c) Better approaches pull clusters out from the cutline by
moving cells within one cluster in a single direction.
structural properties cannot be simply represented in the
immediate connectivities of cells such as in FM and LA
gain calculations; for example, the cluster may consist of
subclusters. Although it might be easy for FM to move out
subclusters, it is also very likely that it will lock the bigger
clusters in the cutset.
To demonstrate the validity of the above observations,
let us consider the simple graph shown in Figure 2(a) that
shows a two-level clustered structure. Cells u 11
4 form a strongly connected subcluster C 1
subclusters
are similarly formed. Subclusters
1 construct a higher level but less densely
interconnected cluster C1 . Similar is the case for C2 , which
is composed of sublusters C 1
. After a random par-
tition, all the clusters as well as the subclusters straddle
the cutline. Initial FM gain calculation gives the gain values
indicated beside each cell in the figure. Cells u 11
3 and
3 belong to different clusters, but have similar situations,
and hence the same gain of 4. We assume a 50%-50% balance
criterion in which cells move alternately between the
two subsets V1 and V2 . The first four moves are shown by
the numbered dashed arrows in Figure 2(a). FM quickly
reaches the local minimum of cutsize 4 (further moves will
be reversed finally since the current point is the maximum
partial sum point). While FM succeeded in moving out
subclusters, it locked the higher level clusters C1 and C2 on
the cutline. Therefore it missed the optimal cut of one that
can be easily identified in the figure.
It is obvious now that a mechanism is needed to aid
iterative improvement algorithms in pulling out clusters
from the cutset. We propose a cluster-oriented framework
for gain calculation and base-cell selection that focuses on
nets connected to moved cells. It can be overlaid on any
iterative-improvement algorithm with any cell-gain calculation
scheme. It implicitly promotes the move of an entire
cluster by dynamically assigning higher weights to nets connected
to recently moved cells. This greatly enhances the
probability of finding a close-to-optimum cut in a circuit.
We also propose an extended version of this algorithm that
tries to identify clusters explicitly and then move them out
from the cutset.
3.2. Considering Clusters in Iterative Improvement
Methods
We first re-examine the cell gain calculation of FM. Initially,
cell gains are calculated based on the immediate benefits of
moving cells. After a cell is moved, the gains of its neighbors
C 1C 2Cutline Cutline Cutline Cutline
u4
FM gain
(b)
(a)

Figure

2. (a) FM only pulls out subclusters and finds a local
minimum in cutsize. (b) The new approach pulls out clusters
and finds the optimum cut.
are updated. At any stage in the move process, the total
gain of a cell can be broken down as the sum of the initial
gain component and the updated gain component. The
total gain indicates the overall situation of a cell, while the
updated gain component reflects the change in the cell's
status due to the movements of its neighbors.
An intuitive solution to the problem of an iterative-improvement
scheme "jumping around" and working on different
clusters simultaneously, as illustrated in Figs. 1(b)
and 2(a), thus locking them in the cutset, is to make
cell movement decisions based primarily on their updated
gain components. This minimizes distractions during the
cluster-pulling effort caused by cells not in the cluster currently
being moved, but with high total gains. In other
words, it allows the algorithm to concentrate on a single
cluster at a time for moves in one direction; note that the
updated gain component of a cell reflects its goodness for
moving with regard to the cluster currently being pulled
from the cutset. The initial gain of a cell, however, provides
useful information for choosing the starting seed for removal
of a cutset-straddling cluster-the cell with the highest gain
is most likely in such a cluster, and thus a very good starting
point. Once the move process has begun, nets connected
to moved cells should be given more weights so that the
updated gain components of cells become more important
than their initial gains. The utility of giving more weight
to nets connected to moved cells (and hence to the updated
gain components of cells) in facilitating the movement of
clusters from the cutset is established in the following set
of results [14].
We consider an iterative improvement partitioning process
like FM and assume that the probability (fint) that an
edge connects a pair of cells inside the cluster is uniformly
distributed, the probability (fext) that an edge connects a
cell in C to a cell outside C is also uniformly distributed,
and fint ? fext . This is similar to the uniformly distributed
random graph model used by Wei and Cheng in [6].
Theorem 1 If a cluster C is divided by the cutline into
subsets C1 2 V1 and C2 2 V2 , and C1 is moved to V2 by a
sequence of moves of its cells, then the cutsize of the partition
will decrease, if initially jC1 j - jC2 j, or first increase
and then decrease, if initially

Figure

4 illustrates Theorem 1.
Assume originally all net weights are one and when up-dating
the gain of a cell, each net connected to moved cells
Algorithm CLIP
1. Calculate the initial gain of all cells according to the iterative
improvement algorithm of choice (e.g., FM, LA,
PROP[13]).
2. Insert the cells into some sorted data structures (free-cell
the maximum gain cell as the first base cell to move.
3. Clear the gain of all cells to zero while keep their original
ordering in the data structure.
4. Move u and update the gain of its neighbors and their ranks
in the data structure as done in the chosen iterative improvement
algorithm. The gain of a cell now only contains
the updated part.
5. Choose the base cell based on the cell's updated gain and
the balance criterion. Move the cell, update its neighbors.
6. Repeat Step 5 until all cells are moved.
7. Find the point in the move sequence which corresponds to
the minimum cutsize, and reverse all the moves after this
point.

Figure

3. One pass of CLIP (CLuster-oriented Iterative-improvement
Partitioner)
is assigned a weight of at least 2pmax , where recall that
pmax is the maximum cell degree in the circuit.
Theorem 2 Once a cluster starts to move from V1 to V2 ,
there is a high probability that the whole cluster will be removed
from the cutset.
The example of Fig. 2 can be used to demonstrate the
advantage of the above approach. The cell gains are first
computed and the base cell is again u 11
3 . The first two
moves of u 11
3 and u 21
3 bring large negative gains to cells
3 and u 22
3 through the weighted edges. Therefore in the
subsequent two moves, they are not selected as would be
the case in FM. Instead, u 12
4 becomes the top cell in V1 ,
and is selected as the next cell to move. The sequence of
the first few moves are indicated by numbered arrows in the
figure (for details see [14]). After eight moves, C1 and C2
are moved out from the cutset, and we obtain the optimal
cut of one. Thus this process escapes the local minimum of
four in which the original FM algorithm was trapped.
3.3. A Cluster-Oriented Iterative-Improvement
Partitioner
From the above discussion, we propose a general gain calculation
and base-cell selection framework CLIP (for CLuster-
oriented Iterative-improvement Partitioner) presented in

Figure

3, that can be applied to any FM-type iterative improvement
algorithm. For implementation convenience, we
set the cell gains to zero after the initial gain calculation.
Cell gains are updated as in the original algorithm over
which CLIP is overlaid. Zeroing of initial gains followed
by gain updating is equivalent to giving nets connected to
moved cells a weight of infinity over nets with no moved
cells. The initial gain information is only reflected in the
initial ordering of cells.
After the first pass, most strongly connected clusters will
probably have been removed from the cutset. The few clusters
left in the cutset can be removed in the subsequent
passes. In later passes, another advantage of the above
cluster-oriented scheme is that clusters lying entirely in one
subset can be easily moved to the other subset. This is
because cell gains being cleared to zero in the initial stage
causes cells in a cluster to have less inertia in staying inside
their original subset. The benefit of cluster movement
between subsets is that larger but less densely connected
clusters (we call them superclusters) can be removed from
the cutset by moving their densely-connected constituent
End of
Cutsize
|C |
|C| |C|
d
Improvement
starting points

Figure

4. The cutsize change with the move of a cluster as
indicated in Theorem 1. When the cutsize does not improve, it
indicates the end of a cluster.
clusters from one subset to the other. By rearranging clusters
between the two subsets in this way, subsets V1 and V2
of the final partition will become the two largest but most
weakly connected superclusters, which implies that the cutsize
will be small. As opposed to FM, which tends to do
only local improvement within large clusters, the above new
scheme can explore a wider solution space, and hence has
less dependence on the initial partition.
Compared to other clustering-based approaches, such as
bottom-up compaction [15], top-down clustering [8] and vertex
ordering [10], CLIP does not explicitly bind cells together
as inseparable clusters. Instead, cells can be implicitly
regrouped into different clusters in subsequent passes.
Both the moving and possible regrouping of clusters are
guided directly by the ultimate objective-cutsize reduc-
tion. A possible advantage of this approach is that CLIP
has more freedom in searching for the optimum cut.
3.4. A Cluster Detection Method
Although the new framework CLIP has significant advantages
over the traditional iterative improvement approach,
it is possible to do even better. We start by asking the following
questions. First, how do we know when a cluster has
been pulled out? Furthermore, once we finish pulling out
the first cluster, how do we select the next starting point?
We address the former question first by determining what
happens when a cutline sweeps across a cluster-this is
equivalent to a cluster being pulled out from the cutset.
From Theorem 1, as we move a cluster from the cutset,
the overall cutsize will decrease until the cluster is entirely
removed from the cutset. In a practical partitioner, some
external cells may be moved across the cutline due to their
connections to moved cells in the cluster. However, since
they are randomly distributed across many clusters (and
thus do not belong to a specific cluster), their contribution
to the overall cutsize change will not be significant. As a
result, we obtain a cutsize change similar to that illustrated
in

Figure

4, which is a pictorial depiction of Theorem 1. Referring
to this figure, the movement of a cluster starts from
either point L1 or L2 . After it is removed from the cutset,
there is an overall improvement in cutsize. If in subsequent
moves no other cluster starts getting pulled out from the
cutset, the cutsize won't improve anymore.
Algorithm CDIP
1. Calculate the initial gain of all cells according to the iterative
improvement algorithm of choice.
2. Insert the cells into sorted data structures
subsets respectively. Select the maximum gain
cell as the first base cell to move.
3. Clear the gain of all cells to zero while keeping their original
ordering in T i
4. Move u and update the gain of its neighbors and their ranks
in T i as done in the chosen iterative improvement
algorithm. Start to count the move index j and to calculate
the partial sum S i;1
j for this first cluster, where . The
gain of a cell now only contains the updated part.
5. Repeat Steps 6 to 7 until all cells are moved and locked.
6. Choose the base cell based on the cell gain and balance
criterion. Move the cell, and update the neighbors as done
before.
7. If the current maximum partial sum S i;k
and the
current move index q
(a) Reverse the moves from q to p + 1.
(b) Choose the free cell with the maximum total
gain as the next base cell.
(c) For each free cell in V i , clear the cell gain except the
gain component from nets connected to the locked cells
in the same subset V i . Reorder cells in T i according to
the modified gain.
(d) Move the base cell v, update neighbors and start the
count of new move index j and the calculation of new
partial sum S i;k+1
j from this move.
8. Find the point in the moving sequence which corresponds
to the minimum cutsize, and reverse all the moves after this
point.

Figure

5. One pass of CDIP (Cluster-Detecting Iterative-improvement
Partitioner)
From this reasoning we propose the following cluster detecting
criterion: After the move process reaches a positive
maximum improvement point, and there is no further improvement
in the following ffi moves, we say that a cluster
has been moved out at the maximum improvement point; ffi
is a parameter of the algorithm. Referring to the cutsize
curve in Figure 4, the ffi cells moved after the minimum cutsize
is reached do not belong to the previous cluster. This
is in contrast to the two cluster detection criteria that Saab
proposed in his compaction algorithm [15], viz., (1) The cutsize
decreases for the first time after a sequence of moves;
(2) The last moved cell in the sequence has a positive gain.
We derived our detection criterion from the analytical results
in Section 3.2., and we use the partial sum of gains
of the sequence of node moves in our criterion, instead of
individual cell gains as in [15].
We now address the second question raised at the beginning
of this subsection. After reversing the ffi moves, we
come back to the end point of the current cluster. Subse-
quently, we need to select the next seed to start the move of
another cluster. For this purpose, the updated gain components
of cells should not be the determining factor. Rather,
the total gains of cells, which reflect their overall situation,
is more useful. Just like the situation at the beginning of
the pass, the cell with the maximum total gain is a good
seed to start with.
From the above discussion, a more sophisticated algorithm
CDIP (Cluster-Detecting Iterative-improvement Par-
titioner) is presented in Figure 5. This is an extension of
CLIP and can also be applied to any FM-type iterative improvement
algorithm. The detection of the end of the kth
cluster is done by monitoring the partial sum S i;k
for each cluster and each subset separately. After S i;k
becomes
positive and does not increase for ffi moves, we infer
Test of # of # of Test # of # of # of
Case Cells Nets Pins Case Cells Nets Pins
s1488 686 667 2079 biomed 6514 5742 21040
struct 1952 1920 5471 s38417 23949 23843 57613
19ks 2844 3282 10547

Table

1. Benchmark circuits' characteristics.
that the move of the current cluster ended at the point of
maximum partial sum S i;k
. We then reverse the moves to
this point, and select the cell with the maximum total gain,
which very likely belongs to an unmoved cluster, as the base
cell. After selecting this cell, the free cells are reordered in
a manner that reflects their relevant connectivities to previously
moved clusters. Since some cluster C was previously
moved from the cutset, say, into V2 , it is not desirable to
move the free cells of C in V2 to V1-doing so will lock
the cluster in the cutset. Therefore, as at beginning of the
pass, all gain components of cells are cleared to zero, with
the exception of those components that correspond to negative
gains corresponding to connections to locked neighbors
in the same subset. These high-weight negative gains that
are retained reflect the fact that some clusters were moved
previously in the pass, and that free cells strongly connected
to moved cells in these clusters likely belong to them and
thus should be given lower priorities for movement.
By using either of the two new partitioning algorithms,
CLIP or CDIP, we can find a good cut through weakly
connected clusters. In order to obtain even better results,
we can apply the original iterative improvement algorithm
as a post-processing phase to fine-tune the partition.
3.5. Complexity Analysis
In an implementation, both CLIP and CDIP have to be
overlaid on some chosen iterative improvement algorithm.
Let n be the number of cells, e the number of nets, p the
number of pins and d the average number of neighbors of
a cell. It is easy to show that CLIP doesn't increase the
order of time complexity. CLIP-FM and CLIP-LA (CLIP
applied to FM, LA) can still be implemented in O(p) if a
bucket list structure is used.
CDIP has two major additional operations beyond those
in the CLIP algorithm. After each detection of a cluster:
(1) The ffi moves are reversed, and (2) The free cells are
reordered. Assuming c clusters are detected in a pass, the
first operation implies cffi additional moves over the entire
pass, and the second operation causes c reorderings of all
cells. For a bucket list structure, where the insertion
of a cell into a bucket is a constant time operation, the
complexity of the first operation is O(cffid) (each extra move
requires O(d) time for updating d neighbors and reinserting
them in the bucket data structure), and the complexity of
the second operation is O(cn) over the entire pass. Thus
the complexity of CDIP is O(max(cffid; cn; p)) for CDIP-
FM and CDIP-LA for one pass. Empirical results presented
later show that CDIP is quite fast.
Minimum of 20 runs Average of 20 runs
Test Improvement % Cut Size Improvement %
Case CLIP CLIP CDIP CLIP CLIP CDIP CLIP CLIP CDIP CLIP CLIP CDIP
s1488 48 42 43 42 41 10.4 12.5 14.6 53.5 49.1 46.9 45.5 46.4 12.3 14.8 13.2
struct 46 44 37 33 36 19.6 28.3 21.7 58.0 49.6 45.6 46.8 46.8 21.3 19.3 19.4
19ks 140 130 119 107 105 15.0 23.6 25.0 171.7 169.0 150.3 136.1 134.6 12.4 20.7 21.6
p2 212 149 149 142 152 29.7 33.0 28.3 273.9 233.4 233.2 208.8 193.2 14.8 23.8 29.5
biomed
industry2 264 422 260 205 190 1.5 22.3 28.0 627.5 732.4 369.6 332.8 293.6 41.1 47.0 53.2
Subtotal 1740 1722 1436 1313 1292 17.5 24.5 25.7 2646 2585 1963 1773 1694 25.8 33.0 36.0
avq.small 347 608 223 146 148 35.7 57.9 57.3 578.6 815.5 335.1 309.9 311.7 42.1 46.5 46.1
avq.large 350 398 216 138 145 38.3 60.6 58.6 755.0 693.4 305.2 349.1 280.8 59.6 53.8 62.8
Subtotal 1394 2047 929 746 735 33.4 46.5 47.3 2734 3178 1363 1377 1238 49.1 48.6 53.8
Total 3134 3769 2365 2059 2027 24.5 34.3 35.3 5380 5763 1963 1773 1694 38.2 41.4 45.5
Average of % improvement 17.8 25.0 26.1 26.1 33.2 35.2

Table

2. Comparisons of CLIP and CDIP (applied to FM and LA3) to FM. CLIP-LA3 results are for shown
correspond first to medium-size circuits and then to large circuits.
Test Improvement over Paraboli
Paraboli FM CLIP CLIP CDIP CLIP FM CLIP CLIP CDIP CLIP
Case -FM f -LA3 f -LA3 f -PROP f -FM f -LA3 f -LA3 f -PROP f
s1488 50 46 43 42 41 43 8.0 14.0 16.0 18.0 14.0
struct
biomed 135
s13207 91 78 76 66 69 71 14.3 16.5 27.5 24.2 22.0
Subtotal 975 965 790 800 779 791 1.0 19.0 17.9 20.1 18.9
7.3
avq.small 224 297 200 129 139 144 -24.6 10.7 42.4 37.9 35.7
avq.large 139 350 185 127 137 143 -60.3 -24.9 8.6 1.4 -2.8
Subtotal 796 1205 822 709 713 688 -33.9 -3.2 10.9 10.4 13.6
Total cut 1771 2170 1612 1509 1492 1479 -22.5 8.8 14.8 15.8 17.5
Average of per-ckt % improvements -4.2 11.6 14.8 15.5 16.5

Table

3. Comparisons of various iterative improvement algorithms to Paraboli [11]. The results for the clustering-based iterative-improvement
algorithms in the table have been further improved by their corresponding original schemes (indicated by the subscript
results are the best cutsizes from 100 runs, while results for CLIP-LA3 f , CDIP-LA3 f and CLIP-PROP f are
the best cutsizes from 20 runs. CDIP-LA3 f results are for shown correspond first to medium-size circuits and then
to large circuits.
Test Improvement over MELO
MELO FM CLIP CLIP CDIP CLIP FM CLIP CLIP CDIP CLIP
Case -FM f -LA3 f -LA3 f -PROP f -FM f -LA3 f -LA3 f -PROP f
28 27 27 27 27 27 3.6 3.6 3.6 3.6 3.6
struct 38 41 33 33 36 33 -7.3 13.2 13.2 5.3 13.2
19ks 119 130 109 104 104 104 -8.5 8.4 12.6 12.6 12.6
44.3 43.0 44.3 46.8
biomed
Total cut 1554 1486 1193 1210 1177 1192 4.4 23.2 22.1 24.3 23.3
Average of per-ckt % improvements 3.2 17.4 17.0 18.8 18.5

Table

4. Comparisons of various iterative improvement algorithms to MELO [11]. The results in the table have been further
improved by the original schemes (indicated by the subscript f ). FM and CLIP-FM f results are the best cutsizes from 100 runs, while
results for CLIP-LA3 f , CDIP-LA3 f and CLIP-PROP f are the best cutsizes from 20 runs. CDIP-LA3 f results are for
4. EXPERIMENTAL RESULTS
All experiments have been done on ACM/SIGDA benchmark
circuits whose characteristics are listed in Table 1.
The circuit netlists were acquired from the authors of [10]
and [11]. All cutset results are for the 45-55% balance criterion

4.1. Comparisons to FM

Table

2 presents the results of applying CLIP to FM and
LA3 (LA algorithm with lookahead level of 3). Both the
minimum and average cutsizes over 20 runs are greatly improved
compared to their corresponding original schemes.
The overall minimum-cutsize improvements are 24.5% for
CLIP-FM over FM and 45.4% for CLIP-LA3 over LA3.
Note also from the table that while LA3 performs slightly
better than FM for small to medium-size circuits, it performs
much worse for large circuits-for an explanation of
this phenomenon the interested reader is referred to [14].
However, CLIP-LA3 now performs much better than FM
(by 24.5% for medium-size benchmarks and 46.5% for large-size
benchmarks, for an overall improvement of 34.3%), as
does CLIP-FM (by 8.6% and 19.7% for medium and large
size circuits, respectively). As is clearly evident, the most
improvements of the new schemes over FM are obtained for
large circuits. The largest improvement of CLIP-LA3 over
FM is about 70% for the circuit s38417. This clearly demonstrates
the ability of the new clustering-based schemes to
tackle large circuits.
The cluster detection method CDIP-LA3, obtained by
overlaying the CDIP scheme of Figure 5 on LA3, performs
even better. The minimum and average cutsizes are improved
over those of FM by 35.3% and 45.5%, respectively.
Both the minimum and average cutsizes are also superior
to those of CLIP-LA3. This indicates that CDIP is a better
and more stable partitioner than CLIP.
4.2. Comparisons to Paraboli and MELO
Finally, in Tables 3 and 4, we compare the original iterative
improvement and the new cluster-oriented iterative
improvement algorithms to two state-of-the-art partitioning
methods, the placement-based algorithm Paraboli [11]
and the spectral partitioner MELO [12]. Here, all the new
clustering-based iterative improvement algorithms are further
improved by the corresponding original schemes as indicated
at the end of Section 3.4. (e.g., CLIP-FM f is CLIP-
FM followed by FM improvement, CLIP-PROP f is CLIP-
PROP followed by PROP improvement, etc. Since FM is
very fast, we perform 100 runs of both FM and CLIP-FM f ;
all other iterative improvement algorithms' results are for
runs.
First, it is clear from the tables that the original FM algorithm
can obtain good results for medium-size circuits.
For this set of benchmarks, it is about 4% better than
MELO, and 1% better than Paraboli in total cut. How-
ever, for large size circuits, it falls far behind Paraboli (by
-22.5% in total cut). This confirms our earlier discussion
on the shortcomings of previous iterative methods. After
using the clustering-based techniques, CLIP and CDIP, all
of the four new algorithms CLIP-FM f , CLIP-LA3 f , CLIP-
PROP f and CDIP-LA3 f , are able to obtain cutsizes that
are overall better than Paraboli's. Total cut improvements
range from 8.8% to 17.5%. This demonstrates that iterative
algorithms can also partition large-size circuits very
effectively.
The best results are obtained by applying CLIP to PROP,
a probability-based iterative improvement partitioner [13].
PROP calculates cell gains based on the probability of a
cell being actually moved in a pass. Thus the cell gain calculation
is more accurate than that of either FM or LA.
Further, when CLIP is applied to FM and LA, neighbors
of moved nodes get updated only if they are connected to
them by critical or somewhat critical (for LA) nets. On
the other hand, in PROP, all nets are probabilistically crit-
ical, and thus all neighbors get updated, leading to a more
accurate reflection of a cell's move on them. The PROP
algorithm combined with CLIP overcomes the two fundamental
shortcomings in traditional iterative improvement
methods-inaccurate gain calculation and lack of a global
view of the cluster-oriented structure of circuits. Thus
it emerges as a very powerful partitioning tool and performs
about 17% better than Paraboli. When compared to
MELO [12], for which only results on medium-size circuits
are given, the differences between the new algorithms are
small, all showing about 23% better results in total cutsize
Test
Case -FM f -LA3 f -LA3 f -PROP f boli
struct 0.54 0.69 2.25 2.72 3.75 38 35.2
19ks 1.59 2.23 8.92 10.83 10.96 79
biomed 3.89 3.34 11.56 18.13 28.61 496 710.9
avq.small
avq.large 19.49 24.07 71.50 157.26 106.28 4135.0
Total
Total

Table

5. Comparisons of CPU times of various algorithms in
secs per run, and total times over all circuits and all runs made.
MELO was run on SUN SPARC10, Paraboli on DEC3000 Model
500 AXP, all others on SUN SPARC5 Model 85.
than MELO.
4.3. Run Time Comparisons
The run times of the iterative improvement algorithms are
very favorable compared to other purely clustering-based algorithms
like Paraboli and MELO (Table 5). Run times of
Paraboli and MELO are reported for the DEC3000 Model
500 AXP and SUN SPARC10 workstations, respectively,
while we have executed all CLIP and CDIP based algo-
rithms, as well as FM and LA, on the SUN SPARC5 Model
85 workstation. The data structures used to store free cells
for FM and LA are bucket structures as proposed in [3]
and [4], respectively. Despite the O(max(cffid; cn; p)) worst-case
time complexity of CDIP-LA3 f , in practice it uses less
than twice the CPU time of CLIP-LA3 f , which has a linear
run time. PROP uses a tree structure which makes it
easy to accommodate arbitrary net weight as is required
in performance-driven partitioning [7, 5]. Yet the run time
of CLIP-PROP f is quite reasonable. The total CPU times
of all four new algorithms are less than that of Paraboli.
Assuming the same speed for the three different worksta-
tions, CLIP-FMf is 1.9 times faster, CLIP-LA3f is 3.3
times faster, and both CDIP-LA3 f and CLIP-PROP f are
1.8 times faster than Paraboli. CLIP-PROP f is comparable
with MELO in run time, while CLIP-FM f , CLIP-LA3f
and CDIP-LA3 f are faster than MELO by factors of 1.2,
1.7 and 1.2, respectively. This also means that if equal CPU
times are allocated, the new algorithms can perform more
runs and generate even better cutsizes than those presented
in

Tables

and 4.
5. CONCLUSIONS
We proposed a new clustering-based approach that greatly
enhances the performance of iterative improvement meth-
ods. The new approach incorporates clustering mechanisms
naturally into traditional FM-type algorithms. This revives
the power of fast move-based iterative improvement algo-
rithms, making them capable of dealing with large-size cir-
cuits. They are significantly better, in terms of both cutset
quality and speed, than current state-of-the-art algorithms
like Paraboli [11] and MELO [12] that are purely clustering-
based, and deserve new attention in the development of
VLSI CAD tools.



--R

"An Efficient Heuristic Procedure for Partitioning Graphs"
"A Proper Model for the Partitioning of Electrical Circuits"
"A linear-time heuristic for improving network partitions"
"An improved min-cut algorithm for partitioning VLSI networks"
"Timing driven place- ment"
"Towards efficient hierarchical designs by ratio cut partitioning"
"A fast algorithm for performance driven placement"
"An Improved Two-way Partitioning Algorithm with Stable Performance"
"Fast Spectral Methods for Ratio Cut Partitioning and Clustering"
"A General Framework for Vertex Orderings, With Applications to Netlist Clustering"
"Partitioning Very Large Circuits Using Analytical Placement Techniques"
"Spectral Partitioning: The More Eigenvectors, the Better"
"A Probability-Based Approach to VLSI Circuit Partitioning"
"VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques"
"A Fast and Robust Network Bisection Algo- rithm"
--TR
A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design
A general framework for vertex orderings, with applications to netlist clustering
Partitioning very large circuits using analytical placement techniques
Spectral partitioning
On implementation choices for iterative improvement partitioning algorithms
A probability-based approach to VLSI circuit partitioning
New faster Kernighan-Lin-type graph-partitioning algorithms
A Fast and Robust Network Bisection Algorithm
A proper model for the partitioning of electrical circuits
A linear-time heuristic for improving network partitions

--CTR
Shantanu Dutt , Halim Theny, Partitioning around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
Yu-Liang Wu , Chak-Chung Cheung , David Ihsin Cheng , Hongbing Fan, Further improve circuit partitioning using GBAW logic perturbation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.3, p.451-460, June
Abhijit S. Deshpande , Sachin B. Patkar , H. Narayanan, Finding bipartition respecting natural dense clusters, Proceedings of the 9th International Conference on Circuits, p.1-6, July 11-13, 2005, Athens, Greece
new effective and efficient multi-level partitioning algorithm, Proceedings of the conference on Design, automation and test in Europe, p.112-116, March 27-30, 2000, Paris, France
Hsun-Cheng Lee , Ting-Chi Wang, Feasible two-way circuit partitioning with complex resource constraints, Proceedings of the 2000 conference on Asia South Pacific design automation, p.435-440, January 2000, Yokohama, Japan
Shawki Areibi , Zhen Yang, Effective memetic algorithms for VLSI design automation = genetic algorithms local search + multi-level clustering, Evolutionary Computation, v.12 n.3, p.327-353, September 2004
Andrew E. Caldwell , Hyun-Jin Choi , Andrew B. Kahng , Stefanus Mantik , Miodrag Potkonjak , Gang Qu , Jennifer L. Wong, Effective iterative techniques for fingerprinting design IP, Proceedings of the 36th ACM/IEEE conference on Design automation, p.843-848, June 21-25, 1999, New Orleans, Louisiana, United States
Wray L. Buntine , Lixin Su , A. Richard Newton , Andrew Mayer, Adaptive methods for netlist partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.356-363, November 09-13, 1997, San Jose, California, United States
Shantanu Dutt , Halim Theny, Partitioning using second-order information and stochastic-gain functions, Proceedings of the 1998 international symposium on Physical design, p.112-117, April 06-08, 1998, Monterey, California, United States
Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States
Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States
Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Hypergraph partitioning with fixed vertices, Proceedings of the 36th ACM/IEEE conference on Design automation, p.355-359, June 21-25, 1999, New Orleans, Louisiana, United States
Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California
A. E. Caldwell , A. B. Kahng , I. L. Markov, Optimal partitioners and end-case placers for standard-cell layout, Proceedings of the 1999 international symposium on Physical design, p.90-96, April 12-14, 1999, Monterey, California, United States
Huiqun Liu , Kai Zhu , D. F. Wong, Circuit partitioning with complex resource constraints in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.77-84, February 22-25, 1998, Monterey, California, United States
Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
Maogang Wang , Sung Lim , Jason Cong , Majid Sarrafzadeh, Multi-way partitioning using bi-partition heuristics, Proceedings of the 2000 conference on Asia South Pacific design automation, p.667, January 2000, Yokohama, Japan
Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States
Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
C. J. Alpert , A. E. Caldwell , A. B. Kahng , I. L. Markov, Partitioning with terminals: a new problem and new benchmarks, Proceedings of the 1999 international symposium on Physical design, p.151-157, April 12-14, 1999, Monterey, California, United States
Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002
Andrew B. Kahng , Xu Xu, Local unidirectional bias for smooth cutsize-delay tradeoff in performance-driven bipartitioning, Proceedings of the international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
John M. Emmert , Sandeep Lodha , Dinesh K. Bhatia, On Using Tabu Search for Design Automation of VLSI Systems, Journal of Heuristics, v.9 n.1, p.75-90, January
Jason Y. Zien , Pak K. Chan , Martine Schlag, Hybrid spectral/iterative partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.436-440, November 09-13, 1997, San Jose, California, United States
Vi Chi Chan , David Lewis, Hierarchical partitioning for field-programmable systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.428-435, November 09-13, 1997, San Jose, California, United States
Andrew E. Caldwell , Andrew B. Kahng , Andrew A. Kennings , Igor L. Markov, Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting, Proceedings of the 36th ACM/IEEE conference on Design automation, p.349-354, June 21-25, 1999, New Orleans, Louisiana, United States
Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.661-666, January 2000, Yokohama, Japan
Sverre Wichlund, On multilevel circuit partitioning, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.505-511, November 08-12, 1998, San Jose, California, United States
Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and implementation of move-based heuristics for VLSI hypergraph partitioning, Journal of Experimental Algorithmics (JEA), 5, p.5-es, 2000
G. Saab, An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs, IEEE Transactions on Computers, v.53 n.6, p.641-652, June 2004
fiduccia-mattheyses algorithm;cluster-removal;iterative improvement techniques;VLSI;ACM/SIGDA benchmark circuits;look-ahead algorithm;spectral partitioner MELO;partition quality;CAD;VLSI circuit partitioning