Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 6 (5) , 820-827
- https://doi.org/10.1109/tcad.1987.1270325
Abstract
A two-dimensional stochastic model of the global wiring of a VLSI chip in a standard-cell or sea-of-gates design style is defined; prominent in the model is the property that the probability of connecting two pins is solely a function of the distance between the cells containing them. It is also assumed that each net consists of just two pins. A lower bound is placed on the expected size of the chip with the best possible wiring. An upper bound is placed on the expected size of the chip with a trivial (all randomly-oriented "L"s) wiring scheme. If the chip size is m rows by n columns and the size of the average row is /overbar μ/ the sizes of the trivial and perfect routings, expressed as a fraction of the size of the perfect routing, approaches 0 as √2 log (n)/ /overbar μ/ It is also shown that with probability at least 1 - ∊ size increase is no more than √2 log (mn/∊/ /overbar μ/.Keywords
This publication has 8 references indexed in Scilit:
- Stochastic Models for Wireability Analysis of Gate ArraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986
- Provably good routing in graphs: regular arraysPublished by Association for Computing Machinery (ACM) ,1985
- Global wire routing in two-dimensional arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Connectivity of Random LogicIEEE Transactions on Computers, 1982
- Wire Length Distribution for Placements of Computer LogicIBM Journal of Research and Development, 1981
- 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
- On the Distribution of the Number of Successes in Independent TrialsThe Annals of Mathematical Statistics, 1956