Browse Prior Art Database

Techniques for Improving Multi-partitioning Algorithm

IP.com Disclosure Number: IPCOM000103736D
Original Publication Date: 1993-Jan-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 5 page(s) / 199K

Publishing Venue

IBM

Related People

Luk, WK: AUTHOR [+2]

Abstract

Two techniques are described which, when incorporated into a multi-way circuit partitioning algorithm, can improve the partitioning result significantly. These two techniques are (i) clustering/de-clustering, and (ii) bounds-squeezing.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 30% of the total text.

Techniques for Improving Multi-partitioning Algorithm

       Two techniques are described which, when incorporated
into a multi-way circuit partitioning algorithm, can improve the
partitioning result significantly.  These two techniques are (i)
clustering/de-clustering, and (ii) bounds-squeezing.

      Results obtained by many partitioning algorithms (e.g., [1,2])
are very sensitive to the given starting partition.  In order to get
close to optimal result, a large number of random starting points are
tried, and the best one is picked.  As an example, we applied the
multi-way partitioning algorithm MP on a design (chip A), the
partitioning (rough placement) obtained is compared with a benchmark
placement of the chip obtained by simulated annealing.  The following
partitioning cost function is minimized:

                            (Image Omitted)

where G is the set of all grid lines superimposed over the chip area,
cg is the cost assigned to the grid line g to account for wire length
and wiring congestion, ng . is the number of nets crossing the grid
line g, N is the set of all signal nets, ln is the total length
of the net n, Ln is the upper bound on the length of the the
net n,f() is a function with f(x) = 0 for x < 0  and increases
abruptly when x > 0, and k1, k2 are constants.

      Start with a random placement of the circuits, and repeatedly
apply the algorithm MP to improve the partitioning (rough placement)
until no significant improvement is observed (the decrease in the
cost function after a single pass is less than, say, one percent).
In this experiment, the chip was divided into 64 (8 by 8) equal-sized
rectangles, and the grid coincides with the boundaries of the
rectangles.  A comparison of our results with the benchmark is as
shown in Tables 1 and 2.

      Number of Crossings
 Vertical Grid Lines   51  320  375  311  302  340  365  346  56
 Horizontal Grid Lines 58  426  444  443  494  518  494  426  51
   Total Crossings  = 5820, Total Wire Length Violations = 98
            Table 1: Benchmark Placement of the Chip (8x8)

      Number of Crossings
 Vertical Grid Lines   51  413  775  988 1121 1094  857  513  56
 Horizontal Grid Lines 58  526  858 1165 1136 1027  717  314  51
   Total Crossings  = 11720, Total Wire Length Violations  = 475
     Table 2: Placement from Multi-way Partitioning Algorithm MP
(8x8)

      The result from MP is much worse than the benchmark placement
obtained from simulated annealing.  Next we present two techniques:
(1) clustering and de-clustering, and (2) bounds-squeezing to improve
the partitioning algorithm.

      Instead of moving individual circuits around, we group the
circuits together into clusters, and move one whole cluster at a
time.  The following clustering algorithm was used; other clustering
algorithms can be incorporated into this approach also.
1.  At the begi...