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

Abstract

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">\bar{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">\lambda</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 \times 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">\bar{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">\bar{R} &gt; 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(\bar{R})</tex> . Simple bounds on the expected wiring area are given and numerical results compared to the earlier work by Helier et al.