TRIVIAL GLOBAL WIRING OF LARGE CHIPS: A STATISTICAL ANALYSIS.

Abstract

A two-dimensional stochastic model of the global wiring of a VLSI chip or macro is defined; prominent in the definition is the property that the probability of connecting two pins is solely a function of the distance between the cells containing them. Given a global wiring, row and column widths (and macro size) are defined by the widest cells in each row and column. A lower bound is placed on the expected size of the macro with perfect wiring. An upper bound is placed on the expected size of the macro with a trival (all 'L's) wiring scheme. From these bounds it is shown that the fraction difference between the trivial and perfect wirings approaches zero as the log of the number of columns divided by the square root of the average row size.