Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses (1982), the algorithm of Krishnamurthy (1984), and Sanchis's extensions of these algorithms to multiway partitioning (1989) all rely on efficient data structures to select the modules to be moved from one partition to the other. The implementation choices for one of these data structures, the gain bucket, is investigated. Surprisingly, selection from gain buckets maintained as last-in-first-out (LIFO) stacks leads to significantly better results than gain buckets maintained randomly (as in previous studies of the FM algorithm or as first-in-first-out (FIFO) queues. In particular, LIFO buckets result in a 36% improvement over random buckets and a 43% improvement over FIFO buckets for minimum-cut bisection. Eliminating randomization from the bucket selection not only improves the solution quality, but has a greater impact on FM performance than adding the Krishnamurthy gain vector. The LIFO selection scheme also results in improvement over random schemes for multiway partitioning and for more sophisticated partitioning strategies such as the two-phase FM methodology. Finally, by combining insights from the LIFO gain buckets with the Krishnamurthy higher-level gain formulation, a new higher-level gain formulation is proposed. This alternative formulation results in a further 22% reduction in the average cut cost when compared directly to the Krishnamurthy formulation for higher-level gains, assuming LIFO organization for the gain buckets.

VLSI netlist partitioning has been addressed chiefly by iterative methods (e.g. Kernighan-Lin and Fiduccia-Mattheyses) and spectral methods (e.g. Hagen-Kahng). Iterative methods are the de facto industry standard, but suffer diminished stability and solution quality when instances grow large. Spectral methods have achieved high-quality solutions, particularly for the ratio cut objective, but suffer excessive memory requirements and the inability to capture practical constraints (preplacements, variable module areas, etc.). This work develops a new approach to Fiduccia-Mattheyses (FM)-based iterative partitioning. We combine two concepts: (1) problem reduction using clustering and the two-phase FM methodology and (2) adaptive multistart, i.e. the intelligent selection of starting points for the iterative optimization, based on the results of previous optimizations. The resulting clustered adaptive multistart (CAMS) methodology substantially improves upon previous partitioning results in the literature, for both unit module areas and actual module areas, and for both the min-cut bisection and minimum ratio cut objectives. The CAMS method is surprisingly fast and has very stable solution quality, even for large benchmark instances. It has been applied as the basis of a clustering methodology within an industry placement tool.

We show h o w t o quantify the suboptimality o f heuristic algorithms for NP-hard problems arising in VLSI layout.Our approach is based on the notion of constructing new scaled instances from an initial problem instance.From the given problem instance, we essentially construct doubled, tripled, etc. instances which h a v e optimum solution costs at most twice, three times, etc. that of the original instance.By executing the heuristic on these scaled instances, and then comparing the growth of solution cost with the growth of instance size, we can measure the scaling suboptimality of the heuristic.We give experimentally determined scaling behavior of several placement and partitioning heuristics; these results suggest that sigini cant improvement remains possible over current state-of-the-art methods.

The complexity of circuit designs has necessitated a top-down approach to layout synthesis. A large body of work shows that a good layout hierarchy, or partitioning tree, as measured by the associated Rent parameter, will correspond to an area-efficient layout. We define the intrinsic Rent parameter of a netlist to be the minimum possible Rent parameter of any partitioning tree for the netlist. Experimental results show that spectra-based ratio cut partitioning algorithms yield partitioning trees with the lowest observed Rent parameter over all benchmarks and over all algorithms tested. For examples where the intrinsic Rent parameter is known, spectral ratio cut partitioning yields a partitioning tree with Rent parameter essentially identical to this theoretical optimum. These results have deep implications with respect to both the choice of partitioning algorithms for top-down layout, as well as new approaches to layout area estimation. The paper concludes with directions for future research, including several promising techniques for fast estimation of the (intrinsic) Rent parameter.>

It is pointed out that the complexity of next-generation VLSI systems will exceed the capabilities of top-down layout synthesis algorithms, particularly in netlist partitioning and module placement. Bottom-up clustering is needed to condense the netlist so that the problem size becomes tractable to existing optimization methods. Here, the DS quality measure, a general metric for evaluation of clustering algorithms, is established. The DC metric in turn motivates the RW-ST algorithm, a self-tuning clustering method based on random walks in the circuit netlist. RW-ST efficiently captures a globally good circuit clustering. When incorporated within a two-phase iterative Fiduccia-Mattheyses partitioning strategy, the RW-ST clustering method improves bisection width by an average of 17% over previous matching-based methods.>

Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approximation of the optimal ratio cut partition cost. It is also demonstrated that fast Lanczos-type methods for the sparse symmetric eigenvalue problem are a robust basis for computing heuristic ratio cuts based on the eigenvector of this second eigenvalue. Effective clustering methods are an immediate by-product of the second eigenvector computation and are very successful on the difficult input classes proposed in the CAD literature. The intersection graph representation of the circuit netlist is considered, as a basis for partitioning, a heuristic based on spectral ratio cut partitioning of the netlist intersection graph is proposed. The partitioning heuristics were tested on industry benchmark suites, and the results were good in terms of both solution quality and runtime. Several types of algorithmic speedups and directions for future work are discussed.>

The ratio cut partitioning objective function successfully embodies both the traditional min-cut and equipartition goals of partitioning. Fiduccia-Mattheyses style ratio cut heuristics have achieved cost savings averaging over 39% for circuit partitioning and over 50% for hardware simulation applications. The authors show a theoretical correspondence between the optimal ratio cut partition cost and the second smallest eigenvalue of a particular netlist-derived matrix, and present fast Lanczos-based methods for computing heuristic ratio cuts from the eigenvector of this second eigenvalue. Results are better than those of previous methods, e.g. by an average of 17% for the Primary MCNC benchmarks. An efficient clustering method, also based on the second eigenvector, is very successful on the 'difficult' input classes in the CAD (computer-aided design) literature. Extensions and directions for future work are also considered.>