A heuristic standard cell placement algorithm using constrained multistage graph model
- 1 January 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 7 (11) , 1205-1214
- https://doi.org/10.1109/43.9190
Abstract
A fast heuristic algorithm is presented for the constructive placement of standard cells based on the so-called constrained multistage graph (CMSG) model, which has a linear time complexity in the number of cells. The first step of this algorithm performs the row assignment of each cell by converting the circuit connectivity into the CMSG, where each stage of the CMSG corresponds to a cell-row in the final layout. In the second step, called the line sweep method, the position of each cell within the row is determined one by one so that the local channel density is minimized. Experimental results on benchmark circuits show that the proposed algorithm yields very competitive results in terms of the number of feedthrough cells and channel density, which was verified by the comparison of the proposed algorithm with the simulated annealing (SA) and other iterative methods such as pairwise interchange, or generalized force-directed relaxation. A theoretical time complexity analysis performed show that the complexity of the proposed algorithm is O(n), where n denotes the number of cells. This result is substantiated with experimental resultsKeywords
This publication has 15 references indexed in Scilit:
- Standard cell placement using simulated sinteringPublished by Association for Computing Machinery (ACM) ,1987
- TimberWolf3.2: A New Standard Cell Placement and Global Routing PackagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- On the relative placement and the transportation problem for standard-cell layoutPublished by Association for Computing Machinery (ACM) ,1986
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- A Standard Cell Initial Placement StrategyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Automatic Placement Algorithms for High Packing density VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Linear Ordering and Application to PlacementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- A placement algorithm for polycell LSI and ITS evaluationPublished by Association for Computing Machinery (ACM) ,1982
- All approach to the two-dimensional placement problem in circuit layoutIEEE Transactions on Circuits and Systems, 1978
- Design automation of MOS artworkComputer, 1974