PiCAP: a parallel and incremental capacitance extraction considering stochastic process variation

ABSTRACT

It is unknown how to include stochastic process variation into fast-multipole-method (FMM) for a full chip capacitance extraction. This paper presents a parallel FMM extraction using stochastic polynomial expanded geometrical moments. It utilizes multi-processors to evaluate in parallel for the stochastic potential interaction and its matrix-vector product (MVP) with charge. Moreover, a generalized minimal residual (GMRES) method with deflation is modified to incrementally consider the nominal value and the variance. The overall extraction flow is called piCAP. Experiments show that the parallel MVP in piCAP is up to 3X faster than the serial MVP, and the incremental GMRES in piCAP is up to 15X faster than non-incremental GMRES methods.

REFERENCES

• 1: Y. Liu, S. Nassif, L. Pileggi, and A. Strojwas, "Impact of interconnect variations on the clock skew of a gigahertz microprocessor," in Proc. ACM/IEEE Design Automation Conf. (DAC), 2000.
• 2: R. Chang, Y. Cao, and C. Spanos, "Modeling the electrical effects of metal dishing due to CMP for on-chip interconnect optimization," IEEE Trans. on Semi. Manufacturing, pp. 1577--1583, 2004.
• 3: Z. Zhu and J. White, "Fastsies: A fast stochastic integral equation solver for modeling the rough surface effect," in Proc. IEEE/ACM Int. Conf. Computer-aided-design (ICCAD), 2005.
• 4: H. Zhu, X. Zeng, W. Cai, J. Xue, and D. Zhou, "A sparse grid based spectral stochastic collocation method for variations-aware capacitance extraction of interconnects under nanometer process technology," in Proc. IEEE/ACM Design, Automation, and Test in Europe (DATE), 2007.
• 5: J. Cui, G. Chen, R. Shen, S. X.-D. Tan, W. Yu, and J. Tong, "Variational capacitance modeling using orthogonal polynomial method," in Proc. ACM/IEEE Great Lake VLSI, 2008.
• 6: T. El-Moselhy and L. Daniel, "Stochastic integral equation solver for efficient variation-aware interconnect extraction," in Proc. ACM/IEEE Design Automation Conf. (DAC), 2008.
• 7: K. Narbos and J. White, "FastCap: A multipole accelerated 3D capacitance extraction program," IEEE Tran. on Computer-aided-design (TCAD), pp. 1447--1459, 1991.
• 8: S. Kapur and D. Long, "Ies3: a fast integral equation solver for efficient3-dimensional extraction," in Proc. IEEE/ACM Int. Conf. Computer-aided-design (ICCAD), 1997.
• 9: W. Shi, J. Liu, N. Kakani, and T. Yu, "A fast hierarchical algorithm for 3-d capacitance extraction," in Proc. ACM/IEEE Design Automation Conf. (DAC), 1998.
• 10: S. Vrudhula, J. M. Wang, and P. Ghanta, "Hermite polynomial based interconnect analysis in the presence of process variations," IEEE Tran. on Computer-aided-design (TCAD), pp. 2001--2011, 2006.
• 11: M. Pelgrom, A. Duinmaijer, and A. Welbers, "Matching properties of MOS transistors," IEEE J. of Solid State Circuits, pp. 1433--1439, 1989.
• 12: J. D. Jackson, Classical Electrodynamics. John Wiley and Sons, 1975.
• 13: C. Brau, Modern Problems In Classical Electrodynamics. Oxford Univ. Press, 2004.
• 14: L. Giraud, S. Gratton, and E. Martin, "Incremental spectral preconditioners for sequences of linear systems," Appl. Num. Math., pp. 1164--1180, 2007.
• 15: V. Simoncini and D. Szyld, "Recent computational developments in Krylov subspace methods for linear systems," Num. Lin. Alg. with Appl., pp. 1--59, 2007.
• 16: G. W. Stewart, Matrix algorithms (Volume II): Eigensystems. SIAM, 2001.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
capacitance extraction, incremental precondition, parallel fast-multipole method, stochastic geometrical moments