Title :
Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis
Author :
Sorkin, Gregory B.
Author_Institution :
IBM T. J. Watson Research Center, Yorktown Heights, NY, USA
fDate :
9/1/1987 12:00:00 AM
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 :
H infinity control; Pins; Random variables; Routing; Stochastic processes; Upper bound; Very large scale integration; Wires; Wiring;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.1987.1270325