Two-dimensional stochastic model for interconnections in master slice integrated circuits

Two-dimenslonal stochastic models for Interconnections in master slice LSI are described. Several limit theorems are derived for estimating the wiring area on large chips in terms of average wire length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R̄</tex> , average number of wires emanating from each logic block <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">λ</tex> , and wire trajectory parameters. The expected value of the maximum number of tracks per channel on an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N × N</tex> chip is shown to be less than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(ln N)</tex> as long as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R̄</tex> does not grow faster than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(ln N)</tex> . If <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R̄ > O(ln N)</tex> , then the expected maximum number of tracks is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(R̄)</tex> . Simple bounds on the expected wiring area are given and numerical results compared to the earlier work by Helier et al.