Finding deterministic solution from underdetermined equation: large-scale performance modeling by least angle regression

ABSTRACT

The aggressive scaling of IC technology results in high-dimensional, strongly-nonlinear performance variability that cannot be efficiently captured by traditional modeling techniques. In this paper, we adapt a novel L₁-norm regularization method to address this modeling challenge. Our goal is to solve a large number of (e.g., 10⁴~10⁶) model coefficients from a small set of (e.g., 10²~10³) sampling points without over-fitting. This is facilitated by exploiting the underlying sparsity of model coefficients. Namely, although numerous basis functions are needed to span the high-dimensional, strongly-nonlinear variation space, only a few of them play an important role for a given performance of interest. An efficient algorithm of least angle regression (LAR) is applied to automatically select these important basis functions based on a limited number of simulation samples. Several circuit examples designed in a commercial 65nm process demonstrate that LAR achieves up to 25x speedup compared with the traditional least-squares fitting.

REFERENCES

• 1: Semiconductor Industry Associate, International Technology Roadmap for Semiconductors, 2007.
• 2: X. Li, J. Le, L. Pileggi and A. Strojwas, "Projection-based performance modeling for inter/intra-die variations," IEEE ICCAD, pp. 721--727, 2005.
• 3: Z. Feng and P. Li, "Performance-oriented statistical parameter reduction of parameterized systems via reduced rank regression," IEEE ICCAD, pp. 868--875, 2006.
• 4: A. Singhee and R. Rutenbar, "Beyond low-order statistical response surfaces: latent variable regression for efficient, highly nonlinear fitting," IEEE DAC, pp. 256--261, 2007.
• 5: A. Mitev, M. Marefat, D. Ma and J. Wang, "Principle Hessian direction based parameter reduction for interconnect networks with process variation," IEEE ICCAD, pp. 632--637, 2007.
• 6: X. Li and H. Liu, "Statistical regression for efficient high-dimensional modeling of analog and mixed-signal performance variations," IEEE DAC, pp. 38--43, 2008.
• 7: X. Li, J. Le, P. Gopalakrishnan and L. Pileggi, "Asymptotic probability extraction for non-normal distributions of circuit performance," IEEE ICCAD, pp. 2--9, 2004.
• 8: B. Efron, T. Hastie and I. Johnstone, "Least angle regression," The Annals of Statistics, vol. 32, no. 2, pp. 407--499, 2004.
• 9: E. Candes, "Compressive sampling," International Congress of Mathematicians, 2006.
• 10: J. Tropp and A. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit," IEEE Trans. Information Theory, vol. 53, no. 12, pp. 4655--4666, 2007.
• 11: G. Seber, Multivariate Observations, Wiley Series, 1984.
• 12: T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning, Springer, 2003.
• 13: S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
process variation, response surface modeling