University of California Los Angeles
Design Automation Laboratory



RCLK Extraction, Sparsification and Model Order Reduction

Primary investigator (PI)

  • Prof. Lei He

Attended students

Funding sources

SRC project 1100 (2003-2006)
UC-Micro project (2003-2006)

Related project

System-in-Package and 3D integration

Research Outcomes

Inductance extraction and circuit model generation : We presented the first publications in the literature on library-based inductance models [ B2 , C11 , C12 , C17] ([C11] was nominated for Best Paper Award in the 1999 IEEE Custom Integrated Circuit Conference), which have become widely used in the industry. We also proposed an accurate vector potential equivalent circuit (VPEC) model to obtain provably passive and reduced complexity circuit model for interconnects with coupling inductance at DAC'03 [ C33 ] and TCAD (IEEE Trans. On CAD) [J19]. The L-inverse element (called susceptance) can be derived from VPEC model from first principle. Moreover, different from the existing susceptance based models that are not compatible with SPICE, the VPEC model can be analyzed by SPICE directly. As a result, it enables a passive and efficient sparsification of inductance. Experiments show that the full VPEC model is as accurate as the full PEEC (partial element equivalent circuit) model but consumes less simulation time than the full PEEC model does. Moreover, the sparsified VPEC model is orders of magnitude (1000X) faster and produces a waveform with small errors (3%) compared to the full PEEC model.

Wideband model order reduction and model realization: We further developed an elimination based circuit reduction for VPEC model. We show that using VPEC to model L-inverse element, and further reduced by a hierarchical Block-Gaussian-elimination based circuit reduction, we can obtain an order-reduced compact model for RLCK circuit with correct dc value. In contrast, no existing model reduction method considering L-inverse can generate the correct dc value. We also found that the reduced macro-model can be realized as RLC elements in a relaxed Foster's form. This result is published by TCAD [C60, J24 ].

Block structure-preserving model reduction : We proposed a block structure preserving model order reduction (BSMOR), where the blocks can be derived based on specific applications such as block current characterization of the substrate or power/ground grid. Increasing block numbers leads to more matched poles using the same Krylov space and also increases the sparse ratio for state matrices of resulting macro-models. Moreover, the reduction preserves the block structure that can be transformed in a bordered-block-diagonal form. As a result, it further enables a partioned circuit analysis. Experiment shows that our method has a 20X smaller reduction time and much lower model complexity compared to the golden standard PRIMA under a same error bound. The initial results were presented at BMAS'05 [ C74 ]. Our recent results found an optimum block structure with better accuracy and efficiency of model order reduction, and also extended to the inductive network with over 10x improvement on accuracy and runtime compared to the existing approaches [C94].

Model order reduction for RCS circuits with multiple non-impulse sources: The existing moment matching methods are not able to accurately model both large number of ports and susceptance. Most recently, we propose an MSMOR (multiple-source-model-order-reduction) method for RCS (S stands for susceptance) circuits with large numbers of non-impulse current sources. We employ a right-hand-side excitation current vector to replace the port incident matrix such that an MIMO system is transformed into an equivalent superposed SISO system to avoid accuracy loss in block moment matching, and develop a generalized second-order Arnoldi method based orthonormalization to simultaneously accurately handle susceptance and all kinds of non-impulse current sources. Compared with existing EKS and IEKS approaches able to consider non-impulse sources but not susceptance, MSMOR is slightly faster and is more accurate in high frequency range and at DC. With same model order, MSMOR reduces time domain waveform error by 33X compared to EKS/IEKS and by 47X compared with the best block moment matching method applicable to susceptance. The initial results was presented at ISPD'06 [C83].

Fast Analysis of Structured Power Grid by Triangularization Based Structure Preserving Model Order Reduction: A Triangularization Based Structure preserving (TBS) model order reduction is proposed to verify power integrity of on-chip structured power grid. The power grid is represented by interconnected basic blocks according to current density, and basic blocks are further clustered into compact blocks, each with a unique pole distribution. Then, the system is transformed into a triangular system, where compact blocks are in its diagonal and the system poles are determined only by the diagonal blocks. Finally, projection matrices are constructed and applied for compact blocks separately. The resulting macromodel has more matched poles and is more accurate than the one using flat projection. It is also sparse and enables a two-level analysis for simulation time reduction. Compared to existing approaches, TBS in experiments achieves up to 133X and 109X speedup in macromodel building and simulation respectively, and reduces waveform error by 33X [C85].

EMPIRE: An Efficient and Compact Multiple-Parameterized Model Order Reduction Method: In physical design and optimization for VLSI/ULSI, parameterized model order reduction can be used to handle large design objectives. We propose an edacient yet accurate parameterized model order reduction method EMPIRE for physical design with multiple parameters. It is the first practical algorithm moments of different parameters with different accuracy according to their influence on the objective under study. Experiment results show that compared with the best existing algorithm CORE which uses explicit moment matching for the parameters, EMPIRE results in 47:8X improved accuracy at a similar runtime [C99, C107].

Efficient Decoupling Capacitance Budgeting Considering Operation and Process Variations: This paper solves the variation-aware on-chip decoupling capacitance (decap) budgeting problem. Unlike previous work assuming the worst-case current load, we develop a novel stochastic current model, which efficiently and accurately captures operation variation such as temporal correlation between clock cycles and logic-induced correlation between ports. The models also considers current variation due to process variation with spatial correlation. We then propose an iterative alternative programming algorithm to solve the decap budgeting problem under the stochastic current model. Experiments using industrial examples show that compared with the baseline model which assumes maximum currents at all ports and under the same decap area constraint, the model considering temporal correlation reduces the noise by up to 5X, and the model considering both temporal and logic-induced correlations reduces the noise by up to 17X. Compared with the model using deterministic process parameters, considering process variation (Leff variation in this paper) reduces the mean noise by up to 4X and the 3 sigma noise by up to 13X. While the existing stochastic optimization has been used mainly for process variation purpose, this paper to the best of our knowledge is the first in-depth study on stochastic optimization taking into account both operation and process variations for power network design. We convincingly show that considering operation variation is highly beneficial for power integrity optimization and this should be researched for optimizing signal and thermal integrity as well [C108].

PiCAP: 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 multiprocessors 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. This work was presented at DAC'09.


B2. L. He, ``Interconnect Modeling and Design with Consideration of On-Chip Inductance,'' a chapter in Layout Optimizations in VLSI Designs , edited by D. Z. Du and S. Sapatnekar, Kluwer Academic Publishers, Nov. 2001, pp 155-190, (pdf).
J19. H. Yu and L. He, ``A Provably Passive and Cost Efficient Model for Inductive Interconnects,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 24, Issue 8, Aug. 2005, Pages:1283 - 1294. (pdf)
J24. Z. Qi, H. Yu, P. Liu, S. Tan and L. He, " Wideband Passive Multi-Port Model Order Reduction and Realization of RLCM Circuits", accepted by IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13 pages. (pdf).
C11. L. He, N. Chang, S. Lin, and O. S. Nakagawa, "An Efficient Inductance Modeling for On-chip Interconnects", (nomination for Best Paper Award) IEEE Custom Integrated Circuits Conference, pp. 457-460, May 1999. (pdf)
C12. N. Chang, S. Lin, L. He, O. S. Nakagawa, and W. Xie, "Clocktree RLC extraction with Efficient Inductance Modeling", Design Automation and Test in Europe, pages: 522-526, Paris, France, March 2000 (pdf)
C18. M. Xu and L. He, "An efficient model for frequency-based on-chip inductance," IEEE/ACM International Great Lakes Symposium on VLSI, 115-120, March 2001. (pdf)
C33. H. Yu, and L. He, "Vector Potential Equivalent Circuit Based on PEEC Inversion, " IEEE/ACM Design Automation Conference, 718-723, June 2003. (pdf)
C74. H. Yu, L. He, and Sheldon X.D. Tan, "Block Structure Preserving Model Reduction for Linear Circuits with Large Numbers of Ports", IEEE International Behavioral Modeling and Simulation Conference, September 22-23, 2005. (pdf)
C60. Z. Qi, S. X.-D. Tan, H. Yu, L. He and P. Liu, "Wideband Modeling of RF/Analog Circuits via Hierarchical Multi-Point Model Order Reduction" IEEE/ACM Asia and South Pacific Design Automation Conference, Shanghai, China, Jan. 2005, p224-229.(pdf)
C83. Yiyu Shi, Hao Yu and Lei He, "Generalized Second-Order Arnoldi Method for Model Order Reduction with Multiple Non-impulse Sources", IEEE/ACM International Symposium on Physical Design, San Jose, CA, pp. 25-32, April 2006. (pdf) (ppt)
C85. Hao Yu, Yiyu Shi and Lei He, "Fast Analysis of Structured Power Grid by Triangularization Based Structure Preserving Model", in proceedings of IEEE/ACM Design Automation Conference, San Francisco, CA, pp. 205-210, July 2006. (nomination for Best Paper Award) (pdf) (ppt)
C94. Hao Yu, Yiyu Shi, and Lei He, "A First Order Block Structure Preserving Model Order Reduction with Inversed Inductance", IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 2006. (pdf) (ppt)
C99. Yiyu Shi and Lei He, "EMPIRE: An Efficient and Compact Multiple-Parameterized Model Order Reduction Method for Physical Optimizaion", International Symposium on Physical Design (ISPD), Austin, Texas, 51-58, March 2007. (pdf) (ppt)
C107. Yiyu Shi and Lei He, "EMPIRE: An Efficient and Compact Multiple-Parameterized Model Order Reduction Method for Physical Optimizaion", SRC Techcon Conference, 2007. (pdf) (ppt)
C108. Yiyu Shi, Jinjun Xiong, Chunchen Liu and Lei He, "Efficient Decoupling Capacitance Budgeting Considering Current Correlation Including Process Variation", IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 2007. (nomination for Best Paper Award) (pdf) (ppt)
C130. Fang Gong, Hao Yu, and Lei He, "PiCAP: A Parallel and Incrementel Capacitance Extraction Considering Stochastic Process Variation", DAC 2009

Send your comments to our webmaster.
Last update: 01-31-2008