Congestion-driven placement using a new multi-partitioning heuristic
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A novel hierarchical top down placement technique is presented for circuits implemented in the sea-of-gates design style. It is based on a new hypergraph multi-partitioning algorithm, whose time complexity is linear in the number of pins of a circuit. The partitioning algorithm uses Steiner tress for the modeling of net topologies, which allows taking wiring congestion into account during placement. This leads to a more sophisticated balance criterion compared to conventional min-cut algorithms and consequently to a better distribution of active elements and wiring over the chip area. Experimental results show that the application of the new method makes the wiring of designs considerably easier.Keywords
This publication has 12 references indexed in Scilit:
- Partitioning logic to optimize routability on graph structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A quadrisection-based combined place and route scheme for standard cellsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- An evolution-based approach to partitioning ASIC systemsPublished by Association for Computing Machinery (ACM) ,1989
- Multiple-way network partitioningIEEE Transactions on Computers, 1989
- Min-cost partitioning on a tree structure and applicationsPublished by Association for Computing Machinery (ACM) ,1989
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph RepresentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966