RCLK Extraction, Sparsification and Model Order Reduction

Primary investigator (PI)

• Prof. Lei He

Attended students

• Hao Yu
• Yiyu Shi

Funding sources

Related project

Research Outcomes

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.

Publications