On wirelength estimations for row-based placement
Authors:
- A.B. KahngAKA.B. Kahng
- S. MantikSMS. Mantik
- I.L. MarkovIMI.L. Markov
- A. ZelikovskyA. Zelikovsky
- 1 January 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 18 (9) , 1265-1278
Abstract
Wirelength estimation in very large scale integration layout is fundamental to any predetailed routing estimate of timing or routability. In this paper, we develop efficient wirelength estimation techniques appropriate for wirelength estimation during top-down floorplanning and placement of cell-based designs. Our methods give accurate, linear-time approaches, typically with sublinear time complexity for dynamic updating of estimates (e.g., for annealing placement). Our techniques offer advantages not only for early on-line wirelength estimation during top-down placement, but also for a posteriori estimation of routed wirelength given a final placement. In developing these new estimators, we have made several contributions, including (1) insight into the contrast between region-based and bounding box-based rectilinear Steiner minimal tree (RStMT) estimation techniques; (2) empirical assessment of the correlations between pin placements of a multipin net that is contained in a block; and (3) new wirelength estimates that are functions of a block's complexity (number of cell instances) and aspect ratioKeywords
This publication has 13 references indexed in Scilit:
- Global wires: harmful?1998
- Planning for performance1998
- A Priori Bounds on the Euclidean Traveling SalesmanSIAM Journal on Computing, 1995
- Closing the gap: near-optimal Steiner trees in polynomial timeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- Connectivity of Random LogicIEEE Transactions on Computers, 1982
- Two-dimensional stochastic model for interconnections in master slice integrated circuitsIEEE Transactions on Circuits and Systems, 1981
- Placement and average interconnection lengths of computer logicIEEE Transactions on Circuits and Systems, 1979
- The largest minimal rectilinear steiner trees for a set ofn points enclosed in a rectangle with given perimeterNetworks, 1979
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959