Min-cut placement with global objective functions for large scale sea-of-gates arrays
Authors:
- 1 April 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 14 (4) , 434-446
Abstract
We present a new min-cut based placement algorithm for large scale sea-of-gates arrays. In the past all such algorithms were developed based on a single local optimization function, called the sequential cut line objective function. Our algorithm incorporates global objective functions into this traditional framework of min-cut placement. In particular, we introduce a new global objective function based on the congestions for cut lines and use it for the selection of their sequence. We also use the total cut value objective function in the determination of the sizes and connectivities of clusters that are to be used in the early stages of min-cut partitioning. The incorporation of such global objective functions yields additional reductions of wire congestions in the entire as well as local chip areas. With the automatic selection and use of such clusters and a cut line sequence, our algorithm can produce, in a short time and at a low cost, final placement results that achieve the 100% completion of wiring on chips of fixed sizes. This has led to its successful production use, having generated more than 400 CMOS sea-of-gates array chips of 1.5 K to 150 K raw gatesKeywords
This publication has 11 references indexed in Scilit:
- A hierarchical floor-planning, placement, and routing tool for sea-of-gates designs1989
- ORCA a sea-of-gates place and route system1989
- TimberWolf3.2: A New Standard Cell Placement and Global Routing Package1986
- A Method of Improving the Terminal Assignment in the Channel Routing for Gate ArraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- A Linear-Time Heuristic for Improving Network Partitions1982
- A Hierarchical Placement Procedure with a Simple Blocking Scheme1979
- A Placement Capability Based on Partitioning1979
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970