Global harmony: coupled noise analysis for full-chip RC interconnect networks

ABSTRACT

Noise is becoming one of the most important metrics in the design of VLSI systems, certainly of comparable importance to area, timing, and power. In this paper, we describe Global Harmony, a methodology for the analysis of coupling noise in the global interconnect of large VLSI chips, being developed for the design of high-performance microprocessors. The architecture of Global Harmony involves a careful combination of static noise analysis, static timing analysis, and reduced-order modelling techniques. We describe a reduced-order modelling approach that allows for passive multiport reduction of RC netlists as impedance macromodels while preserving the symmetry and sparsity of the state matrices for efficient storage. We describe how the macromodels are practically employed to perform coupling analysis and how timing constraints can be used to limit pessimism in the analysis.

REFERENCES

• 1: L. T. Pillage and R. A. Rohrer. Asymptotic Waveform Evaluation for Timing Analysis. IEEE Trans. CAD, 9(4):352-366, April 1990.
• 2: Kenneth L. Shepard , Vinod Narayanan, Noise in deep submicron digital design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.524-531, November 10-14, 1996, San Jose, California, United States
• 3: K. L. Shepard , S. M. Carey , E. K. Cho , B. W. Curran , R. F. Hatch , D. E. Hoffman , S. A. McCabe , G. A. Northrop , R. Seigler, Design methodology for the S/390 parallel enterprise server G4 microprocessors, IBM Journal of Research and Development, v.41 n.4-5, p.515-547, July/Sept. 1997
• 4: Delay Calculation Language (DCL) and Procedural Interface (PI). Technical report, CAD Framework Initiative. Version 1.0.1.
• 5: V. Raghavan , J. E. Bracken , R. A. Rohrer, AWESpice: a general tool for the accurate and efficient simulation of interconnect problems, Proceedings of the 29th ACM/IEEE conference on Design automation, p.87-92, June 08-12, 1992, Anaheim, California, United States
• 6: Seok-Yoon Kim , Nanda Gopal , Lawrence T. Pillage, AWE macromodels of VLSI interconnect for circuit simulation, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.64-70, November 1992, Santa Clara, California, United States
• 7: Seok-Yoon Kim, Nanda Gopal, and Lawrence T. Pillage. Time-domain macromodels for VLSI interconnect analysis. IEEE Trans. CAD, 13:1257- 1270, 1994.
• 8: R. W. Freund , P. Feldmann, Reduced-order modeling of large passive linear circuits by means of the SYPVL algorithm, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.280-287, November 10-14, 1996, San Jose, California, United States
• 9: Roland W. Freund , Noël M. Nachtigal, Software for simplified Lanczos and QMR algorithms, Applied Numerical Mathematics, v.19 n.3, p.319-341, Dec. 1995 [doi>10.1016/0168-9274(95)00089-5]
• 10: G. H. Golub and C. F. Van Loan. Matrix Computation. The Johns Hopkins University Press, third edition, 1996.
• 11: P. Feldmann , R. W. Freund, Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.474-479, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217573]
• 12: Jane K. Cullum , Ralph A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Vol. 1, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 13: G. H. Golub and R. Underwood. The block lanczos method for computing eigenvalues. In J. R. Rice, editor, MathmaticaI Software III, pages 361-377. Academic Press, New York, 1977.
• 14: J. Cullum and W. E. Donath. A block lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace for large, sparse symmetric matrices. In Proceeding of the IEEE Conference on Decision and Control, pages 505-509, 1974.
• 15: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 16: Anshul Gupta and Fred Gustavson. WSSMP: Watson symmetric sparse matrix package. Technical report, IBM T.J. Watson Research Center, 1997. Research Report RC 20645.
• 17: P. Feldmann and R. W. Freund. Efficient linear circuit analysis by Pad6 approximation via the Lanczos process. IEEE Trans. CAD, 14:639-649, May 1995.
• 18: Imad M. Jaimoukha , Ebrahim M. Kasenally, Oblique Projection Methods for Large Scale Model Reduction, SIAM Journal on Matrix Analysis and Applications, v.16 n.2, p.602-627, April 1995 [doi>10.1137/S0895479893250740]
• 19: I. M. Elfadel , David D. Ling, Zeros and passivity of Arnoldi-reduced-order models for interconnect networks, Proceedings of the 34th annual conference on Design automation, p.28-33, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266030]
• 20: L. Miguel Silveira , Mattan Kamon , Ibrahim Elfadel , Jacob White, A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.288-294, November 10-14, 1996, San Jose, California, United States
• 21: E. S. Kuh and R. A Rohrer. Theory of Linear Active Networks. Holden-Day, 1967.
• 22: E. A. Guillemin. Synthesis of Passive Networks. John Wiley and Sons, 1957.
• 23: K. S. Narendra and J. H. Taylor. Frequency Domain Criterion for Absolute Stability. Academic Press, 1973.
• 24: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 25: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 26: Curtis L. Ratzlaff, Satyamurthy Pullela, and Lawrence T. Pillage. Modelling the RC-interconnect effects in a hierarchical timing analyzer. In Custom Integrated Circuits Conference, pages 15.6.1 - 15.6.4, 1992.
• 27: J. E. Bracken, V. Raghavan, and R. A. Rohrer. Interconnect Simulation with Asymptotic Waveform Evaluation. IEEE Trans. Circuits Syst., 39(11):869-878, November 1992.

INDEX TERMS

Primary 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)

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

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification

Keywords:
noise, static timing analysis, interconnect