Wiring space and length estimation in two-dimensional arrays

We propose a new global routing area estimation approach for high-performan ce very large scale integration and multichip modules (MCM's). The objectiv e is to route nets with minimum density of global cells, producing a four-b end routing for each two-terminal net. We propose an approximate upper boun d on global cell d(R) less than or equal to 2d(0) log(m/(2d(0))), in an m X m two-dimensional array, where do is the estimated lower-bound density. Th e total wirelength is (2 alpha + beta)4m(2)d(0)/3, where alpha + beta = 1 a nd alpha is the percentage of diagonal combinations and beta is the percent age of adjacent combinations of nets. If alpha less than or equal to beta ( this assumption holds since a good placement minimizes the longer wires), t hen the total wirelength is at most 2m(2)d(0). By counting on the adjacent and diagonal combinations separately in the cost function, d(R) less than o r equal to inverted right perpendicular4d(0)/3inverted left perpendicular X log(inverted right perpendicularm/(4d(0)/3)inverted left perpendicular. We verified that the bound obtained are realistic in the worst case. A soluti on to this problem can be used fur quick estimation of necessary wiring spa ce (for standard cell array designs) and difficulty of routing (for gate ar ray designs) in the early design planning stage.