Fast interval-valued statistical interconnect modeling and reduction

ABSTRACT

Correlated interval representations of range uncertainty offer an attractive solution for approximating computations on statistical quantities. The key idea is to use finite intervals to approximate the essential mass of a pdf as it moves through numerical operators; the resulting compact interval-valued solution can be easily interpreted as a statistical distribution and efficiently sampled. This paper describes improved interval-valued algorithms for AWE/PRIMA model order reduction for tree-structured interconnect with correlated $RLC$ parameter variations. By moving to a faster interval-valued linear solver based on path-tracing ideas, and making more optimal trade-offs between interval- and scalar-valued computations, we can extract delay statistics roughly 10X faster than a classical Monte Carlo simulation loop, with accuracy to within 5%.

REFERENCES

• 1: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 2: Sarvesh Bhardwaj , Sarma B. K. Vrudhula , David Blaauw, "AU: Timing Analysis Under Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.615, November 09-13, 2003 [doi>10.1109/ICCAD.2003.1]
• 3: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 4: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 5: Jiayong Le , Xin Li , Lawrence T. Pileggi, STAC: statistical timing analysis with correlation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996665]
• 6: Ying Liu , Lawrence T. Pileggi , Andrzej J. Strojwas, Model order-reduction of RC(L) interconnect including variational analysis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.201-206, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309914]
• 7: Xin Li , Jiayong Le , P. Gopalakrishnan , L. T. Pileggi, Asymptotic probability extraction for non-normal distributions of circuit performance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.2-9, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382533]
• 8: J. Wang , P. Ghanta , S. Vrudhula, Stochastic analysis of interconnect performance in the presence of process variations, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.880-886, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382698]
• 9: L. Daniel, O. C. Siong, L. S. Chay, K. H. Lee, and J. White, "Multi-parameter moment-matching model-reduction approach for generating geometrically parameterized interconnect performance models," TCAD, 2004.
• 10: Kanak Agarwal , Dennis Sylvester , David Blaauw , Frank Liu , Sani Nassif , Sarma Vrudhula, Variational delay metrics for interconnect timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996675]
• 11: J. Stolfi and L. H. de Figueiredo, Self-Validated Numerical Methods and Applications. Brazilian Mathematics Colloquium Monograph, IMPA, Rio De Janeiro, Brazil, 1997.
• 12: J. D. Ma , R. A. Rutenbar, Interval-valued reduced order statistical interconnect modeling, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.460-467, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382621]
• 13: L. T. Pillage and R. A. Rohrer, "Asymptotic waveform evaluation for timing analysis," TCAD, 1990.
• 14: A. Odabasioglu, M. Celik, and L. T. Pileggi, "PRIMA: Passive reduced-order interconnect macromodeling algorithm," TCAD, 1998.
• 15: C. L. Ratzlaff and L. T. Pillage, "RICE: Rapid interconnect circuit evaluation using AWE," TCAD, 1994.
• 16: A. Odabasioglu and L. T. Pileggi, "RICE 5: Rapid interconnect circuit evaluation version 5," Reference Manual, 1997.
• 17: R. E. Moore, Interval Analysis. Prentice-Hall, 1966.
• 18: Claire Fang Fang , Rob A. Rutenbar, Probabilistic interval-valued computation: representing and reasoning about uncertainty in dsp and vlsi design, Carnegie Mellon University, Pittsburgh, PA, 2005
• 19: S. Nassif, "Modeling and analysis of manufacturing variations," in CICC, 2001.
• 20: V. Mehrotra, S. Nassif, D. Boning, and J. Chung, "Modeling the effects of manufacturing variation on high-speed microprocessor interconnect performance," in IEDM, 1998.
• 21: Ying Liu , Sani R. Nassif , Lawrence T. Pileggi , Andrzej J. Strojwas, Impact of interconnect variations on the clock skew of a gigahertz microprocessor, Proceedings of the 37th conference on Design automation, p.168-171, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337365]
• 22: R. Burch, F. N. Najm, P. Yang, and T. N. Trick, "A Monte Carlo approach for power estimation," TVLSI, 1993.
• 23: L. V. Kolev, Interval Methods for Circuit Analysis. World Scientific, 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
affine arithmetic, interval-valued statistical interconnect analysis, manufacturing variation