Interconnect implications of growth-based structural models for VLSI circuits

ABSTRACT

Power-law scaling phenomena that govern VLSI circuits have for several decades formed the foundation of VLSI interconnect estimation. This research investigates possible alternative power-law phenomena in VLSI circuits. In particular, we develop newrandom growthmodels and assess their implications for VLSI interconnect structure. We assess our models' predictions forfanout,crossing edge, andterminalscaling using test data from 21 industry standard-cell designs with up to 283K cells. Our work demonstrates the possibility of non-Rent based, yet equally plausible and well-fitting, structural models for VLSI circuits and their interconnections.

REFERENCES

• 1: A. Barabasi, R. Albert and H. Jeong, "Mean-field theory for scale-free random networks", Physica, vol. A 272, 1999, pp. 173-187, http://www.nd.edu/~networks/Papers/ physica.pdf.
• 2: A. E. Caldwell, A. B. Kahng and I. L. Markov, "Relaxed Partitioning Balance Constraints in Top-Down Placement", Proc. IEEE ASIC Conference, 1998, pp. 229-232.
• 3: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 4: Phillip Christie, Managing interconnect resources (tutorial), Proceedings of the 2000 international workshop on System-level interconnect prediction, p.1-51, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333139]
• 5: J. A. Davis, V. K. De and J. D. Meindl, "A Stochastic Wire- Length Distribution for Gigascale Integration(GSI)-part 1: Derivation and Validation", IEEE Trans. on Electron Dev., 45, 1998, pp. 580-589.
• 6: W. E. Donath, "Placement and Average Interconnection Lengths of Computer Logic", IEEE Trans. on Circuits and Systems CAS-26(4) (1979), pp. 272-277.
• 7: L. Hagen, A. B. Kahng, F. Kurdahi and C. Ramachandran, "On the Intrinsic Rent Parameter and New Spectra-Based Methods for Wireability Estimation", IEEE Trans. on CAD 13(1) (1994), pp. 27-37.
• 8: J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins, "The Web as a graph: measurements, models, and methods", Proc. International Conference on Combinatorics and Computing, 1999, pp. 26-28.
• 9: B. S. Landman and R. L. Russo, "On a Pin versus Block Relationship for Partitions of Logic Graphs", IEEE Trans. on Computers C-20 (1971), pp. 1469-1479.
• 10: D. Stroobandt, A Priori Wire Length Estimates for Digital Design, Kluwer Academic Publishers, 2000, pp. 140.
• 11: Dirk Stroobandt , Fadi J. Kurdahi, On the Characterization of Multi-Point Nets in Electronic Designs, Proceedings of the Great Lakes Symposium on VLSI '98, p.344, February 19-24, 1998
• 12: Payman Zarkesh-Ha , Jeffrey A. Davis , William Loh , James D. Meindl, Prediction of interconnect fan-out distribution using Rent's rule, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.107-112, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333040]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Design, Experimentation, Measurement, Performance, Theory