Efficient and effective placement for very large circuits

Proceedings of 1993 International Conference on Computer Aided Design (ICCAD)Published 30 December 2002

Wenlong Sun, Carl Sechen

DOI10.1109/iccad.1993.580051

Citations53

TL;DR

A new hierarchical annealing-based placement program which yields total wire length reductions of up to 9% while consuming up to 7.5 times less CPU time in comparison to TimberWolfSC v6.0.

Abstract

We present two major extensions to the implementation of simulated annealing for row-based placement which have enabled it to obtain the best results ever reported for a large set of MCNC benchmark circuits while using the least computation time ever reported for remotely comparable results. Our results indicate that chip area reductions up to 16% can be expected, compared with TimberWolfSC v6.0. Our new hierarchical annealing-based placement program yields total wire length reductions of up to 9% while consuming up to 7.5 times less CPU time in comparison to TimberWolfSC v6.0. In comparison to the Gordian/Domino program, our new program yields total wire lengths which are always lower (up to 9% lower) and our program is always faster for circuits with more than 5000 cells (which represents the range of circuit sizes of interest).

Keywords

Computer ScienceEngineering

ScienceOptimization by Simulated Annealing

44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more

A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsGORDIAN: VLSI placement by quadratic programming and slicing optimization

526 Citations1991Jürgen M. Kleinhans, Georg Sigl +2 more

The authors present a placement method for cell-based layout styles that is composed of alternating and interacting global optimization and partitioning steps that are followed by an optimization of the area utilization.

RITUAL: a performance driven placement algorithm for small cell ICs

122 Citations2002A. Srinivasan, K. Chaudhary +1 more

An efficient algorithm, RITUAL (residual iterative technique for updating all Lagrange multipliers), for obtaining a placement of cell-based ICs subject to performance constraints is described and yields very good results, as is shown on a set of real examples.

Finding clusters in VLSI circuits

106 Citations2002J. Garbers, Hans Jürgen Prömel +1 more

A fast heuristic algorithm based on a simple, local criterion is proposed that is able to prove that for highly structured circuits the clusters found by this algorithm correspond with high probability to the 'natural' clusters.

IEEE/ACM International Conference on Computer-Aided DesignA new approach to effective circuit clustering

104 Citations1992Hagen, Kahng

The DS quality measure, a general metric for evaluation of clustering algorithms, is established and motivates the RW-ST algorithm, a self-tuning clustering method based on random walks in the circuit netlist, which efficiently captures a globally good circuit clustering.

Performance of a new annealing schedule

72 Citations2003J. Lam, Jean-Marc Delosme

A simulated annealing schedule is derived and its application to the standard cell placement and the traveling salesman problems results in a two to twenty-four times speedup over annealed schedules currently available in the literature.

IEEE/ACM International Conference on Computer-Aided DesignA probabilistic multicommodity-flow solution to circuit clustering problems

58 Citations1992Yeh Yeh, Cheng Cheng +1 more

A probabilistic, multicommodity flow based algorithm is proposed and tested under the clustering metric and it is shown that this algorithm generates promising results with respect to the proposed metric.

Random walks for circuit clustering

40 Citations2002J. Cong, L. Hagen +1 more

The authors introduce a fast, parallelizable approach to circuit clustering based on analysis of random walks in the netlist that yields good clustering solutions for classes of 'difficult' inputs in the literature and for industry benchmark circuits.

Clustering based simulated annealing for standard cell placement

31 Citations2003Shivaji Mallela, L.K. Grover

The authors present a novel technique for reducing the effective problem size for simulated annealing without compromising the solution quality, and report a factor-of-two-to-three speed-up in CPU time, together with a 6- to-17% improvement in the estimated wire length.

IEEE/ACM International Conference on Computer-Aided DesignAccurate net models for placement improvement by network flow methods

15 Citations1992Doll, Johannes +1 more

An efficient iterative improvement procedure for row based cell placement is described and it is shown that minimizing the net length estimated with the net model also minimizes the half perimeter of a rectangle enclosing all pins of a net.