Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis

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 µ, it is shown from these bounds that the expected difference between the sizes of the trivial and perfect routings, expressed as afraction of the size of the perfect routing, approaches 0 as [formula omitted] It is also shown that with probability at least 1 - ε, the same fractional size increase is no more than [formula omitted]. Copyright © 1987 by The Institute of Electrical and Electronics Engineers, Inc.