Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50×50 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [ 1 ], while reducing the average total wire length.

As process nodes scale to more advanced technologies, post-layout simulations for integrated circuits have become increasingly complex, involving billions to trillions of nodes. The growing design complexity and transistor integration require more accurate and efficient post-layout SPICE simulations. However, existing methods for solving large-scale post-layout circuits face significant challenges due to high computational costs. In this paper, we propose a new approach, PiSPICE, which utilizes adjoint sensitivity analysis to identify critical parasitics and eliminate non-critical ones, effectively reducing the simulation scale and improving speed. By modeling parasitics and performing sensitivity analysis on pre-layout circuits, we significantly reduce the computational burden and avoid the overhead of directly analyzing sensitivities in large-scale postlayout circuits. By retaining only the critical parasitics and applying model order reduction to minimize their impact, while eliminating non-critical parasitics, PiSPICE achieves a speedup of up to 17.27 x in simulation with an error margin of less than 0.78% compared to the commercial simulator Spectre.

The increasing complexity of high-frequency circuits calls for efficient and accurate passive macromodeling techniques. Existing passivity enforcement methods, including those in commercial tools, often encounter convergence issues or compromise accuracy. The Domain-Alternated Optimization (DAO) framework seeks to restore accuracy through an additional optimization step but is hampered by high memory consumption and slow convergence, particularly for large-scale problems. This paper presents G-SpNN, a novel GPU-accelerated framework that recasts the passivity-enforced macromodeling problem as a neural network training task. This approach significantly enhances both the speed and scalability of passivity enforcement. Experimental results show that G-SpNN achieves an average speedup of $7.63 \times$ in convergence compared to DAO, while reducing memory usage by two orders of magnitude. This enables G-SpNN to handle complex, high-port-count circuits with greater accuracy and efficiency, paving the way for robust high-frequency circuit simulations.

Adjoint sensitivity analysis is critical in modern integrated circuit design and verification, but its computational intensity grows significantly with the circuit size, the number of objective functions, and the accumulation of time points. This growth can impede its wider application. The intimate link between the forward integration in transient analysis and the reverse integration in adjoint sensitivity analysis allows for the retention of Jacobian matrices from transient analysis, thereby speeding up sensitivity analysis. However, Jacobian matrices across multiple timesteps are often so large that they cannot be stored in memory during the forward integration process, necessitating disk storage and incurring significant I/O overhead. To address this, we develop a memory-efficient sensitivity analysis method that utilizes data compression to minimize memory overhead during simulation and enhance analysis efficiency. Our compression method can efficiently compress the sparse tensor that contains the Jacobian matrices over time by exploiting the spatiotemporal characteristics of the data and circuit attributes. It also introduces a shared-indices technique, a cutting-edge spatiotemporal prediction model, and robust residual encoding. We evaluate our compression method on 7 datasets from real-world simulations and demonstrate that it can reduce memory requirements by more than 16x on average, which is significantly more efficient than other state-of-the-art compression techniques.

This paper proposes a two-step fine-tuning assisted layout sizing (FALS) scheme with an efficient post-layout sampling feature, the key of which is to reuse abundant and cheap schematic information with Transfer Learning for quickly pruning design space and achieving global optimization. The innovation is that FALS is the first work to integrate the advantages of two-step optimization and high-accuracy model-based local optimization. The same optimization results can be achieved by FALS with significantly 10× less total run-time than the conventional DE.

The impact of process variation to advanced integrated circuits has become increasingly significant. Traditional sampling based yield analysis and optimization always require large amount of expensive simulations. This paper proposes an All Sensitivity Adversarial Importance Sampling (ASAIS) yield optimization method, which avoids samplings in outer optimization based on sensitivity. Moreover, Fast Sensitivity Importance Sampling (FSIS) yield analysis method is adopted as inner yield analysis to eliminate the sampling using transient sensitivity analysis. Experiments on SRAM show ASAIS generates more than 90X speedup of the entire yield optimization process, while FSIS speedup 3X-I5X over existing methods.

Transient sensitivity is useful for analyzing the gradients of objective functions with respect to given parameters. This is useful in variation and circuit optimization. The computational complexity for traditional transient sensitivity analysis for objective function with N time points is O(N2), which is too expensive for large N. In this paper we propose a transient sensitivity analysis method that reduces the computational complexity to O(N), enabling the analysis of performance metrices related to thousands of time points, such as SNDR, THD, SFDR, and etc.

Network acceleration has become a hot topic, for the substantial challenge in deploying such networks in real-time applications or on resource-limited devices. A wide variety of pruning-based acceleration methods were proposed to expend the sparsity of parameters, thus omit computations involving those pruned parameters. However, these element-wise pruning methods can hardly be efficiently used for accelerating without special-customized speed-up algorithms. Due to this difficulty, recent work has turned to prune filters or channels instead, which directly reduce the number of matrix multiplications. While Channel Pruning method reforms the original CNNs to a kernel-wisely or channel-wisely pruned one, Runtime Neural Pruning (RNP) argues that models pruned with static pruning methods will lose the ability for some hard tasks since some potentially significant weights are lost during the pruning process. Dynamically pruning the channels is found to be a good solution. In this paper, we propose to use Channel Threshold-Weighting (T-Weighting) modules to choose and prune unimportant feature channels at inference phase. As the pruning is done dynamically, it is called Dynamic Channel Pruning (DCP). DCP consists of the original convolutional network and a number of "Channel T-Weighting" modules at certain layers. The "Channel T-Weighting" module assigns weights to corresponding channels, pruning those channels whose weights are zero. Those pruned channels make the CNN accelerated, and those remained channels multiplying with weights help feature expression enhanced. The reason for not considering fully-connected layers are two-fold: 1. convolution operations occupying the vast majority of all computation cost. 2. DCP is not designed only for classification, but for many tasks taking CNN as their backbone networks. In this work, we propose as a specific choice for h(·) the thresholded sigmoid function to offer sparsity to w_l, called thresholded sigmoid (T-sigmoid), h(x) = σ(x)· 1{x > T}, where σ(·) refers to sigmoid function. 1{x} is boolean indicator function, where output being 1 when input x is True, and vice versa. The T-sigmoid function is inspired by spike-and-slab models, which formulates distributions over hidden variables as the product of a binary spike variable and a real-valued code. The DCP is trained in a layer-by-layer manner. We first train the "Channel T-Weighting" module, and then set the threshold based on the given pruned ratio, and adjust the threshold in an iterative way at the end. The proposed DCP could reach 5× speed-up with only 4.77% drops on ILSVRC2012 dataset. Comparing the increasing error with baseline methods (Filter Pruning, Channel Pruning and RNP), DCP outperforms other methods consistently as the speed-up ratio increasing. The experiment show that DCP also consistently outperforms the baseline model whenever for Cifar10 and Cifar100. By comparing the full model and accelerated model (3×), we can see that DCP generalized well on scenes classification task (on the Places365-Challenge dataset) with VGG-16, with the top-1 accuracy top-5 accuracy dropping 2.07% and 1.96% respectively. DCP (3×) trained with ResNet-50 also suffered slight drops, with the top-1 accuracy top-5 accuracy dropping 2.78% and 2.55% respectively, outperforming Channel Pruning (our impl.) by a large margin. For the detection task on the PASCAL VOC2007 dataset using Faster R-CNN, we observe 0.5% mAP drops and 1.7% mAP drops of our 2× acceleration model and 4× acceleration model respectively, showing little accuracy degradation, showing a competitive result for proving DCP generalized well on detection task.

Recently, facial landmark detection algorithms have achieved remarkable performance on static images. However, these algorithms are neither accurate nor stable in motion-blurred videos. The missing of structure information makes it difficult for state-of-the-art facial landmark detection algorithms to yield good results. In this paper, we propose a framework named FAB that takes advantage of structure consistency in the temporal dimension for facial landmark detection in motion-blurred videos. A structure predictor is proposed to predict the missing face structural information temporally, which serves as a geometry prior. This allows our framework to work as a virtuous circle. On one hand, the geometry prior helps our structure-aware deblurring network generates high quality deblurred images which lead to better landmark detection results. On the other hand, better landmark detection results help structure predictor generate better geometry prior for the next frame. Moreover, it is a flexible video-based framework that can incorporate any static image-based methods to provide a performance boost on video datasets. Extensive experiments on Blurred-300VW, the proposed Realworld Motion Blur (RWMB) datasets and 300VW demonstrate the superior performance to the state-of-the-art methods. Datasets and models will be publicly available at https://keqiangsun.github.io/projects/FAB/FAB.html.

Faster and more accurate variation characterizations of semiconductor devices/circuits are in great demand as process technologies scale down to Fin-FET era. Traditional methods with intensive data testing are extremely costly. In this paper, we propose a novel learning-based high-accuracy data prediction framework inspired by learning methods from computer vision to efficiently characterize variabilities of device/circuit behaviors induced by manufacturing process variations. The key idea is to adaptively learn the underlying data pattern among data with variations from a small set of already obtained data and utilize it to accurately predict the unmeasured data with minimum physical measurement cost. To realize this idea, novel regression modeling techniques based on Gaussian process regression and partial least squares regression with feature extraction and matching are developed. We applied our approach to real-time variation characterization for transistors with multiple geometries from a foundry 28nm CMOS process. The results show that the framework achieves about 14x time speed-up with on average 0.1% error for variation data prediction and under 0.3% error for statistical extraction compared to traditional physical measurements, which demonstrates the efficacy of the framework for accurate and fast variation analysis and statistical modeling.

Although automatic optimization for individual analog/RF modules has been studied for many years, design automation for analog/RF systems that contain a complicated hierarchy of mixed-signal modules is still very challenging as the lack of an efficient way to bridge between different level descriptions in the design hierarchy. In this paper, we applied sparse regression as a modeling tool to model the modules that need to be optimized and embedded the modules in a large system to accomplish a realistic 802.11ac system design. The wireless system specification (e.g. bit error rate) for comprehensively evaluating the analog/RF front-ends is used as the optimization objective. The proposed method is implemented by linking the block-level performance metrics to the wireless system using mixed-signal simulation platform with performance modeling and Pareto optimal fronts. By this method, the receiver for 802.11ac systems is successfully designed and the worst error vector magnitude (EVM) is decreased by 34% from coarse design.

SRAM cells usually require extremely low failure rate or equivalently extremely high production yield, making it impractical to perform yield analysis using Monte Carlo (MC) method as huge amount of samples are needed. Fast MC methods, e.g., importance sampling methods, are still too expensive as the anticipated failure rate is very low. In this paper, a new SRAM yield analysis method is proposed to tackle this issue. The key idea is to improve traditional importance sampling method with an efficient online surrogate model. Experimental results show that the proposed yield analysis method achieves $5\times $ -$22\times $ speedup over existing state-of-the-art techniques without sacrificing estimation accuracy. Sigma distribution and schmoo plot can be quickly generated by the proposed method, which is very useful for realistic applications. Based on the proposed yield analysis method, an efficient yield optimization method has been developed to further automate the SRAM cell design procedure where process variations can be fully considered. Experimental results show that a fully automatic yield optimization for SRAM cells can be done within only a few hours.

Passivity enforcement is an important issue for macromodeling for passive systems from measured or simulated data. Existing passivity enforcement techniques based on iteratively fixing the passivity either suffer from convergence issue or lack optimality that will sometimes lead to unacceptable error. In addition to the traditional two-stage (fitting plus enforcement) schemes, we propose a postenforcement optimization, which takes a passive yet not necessarily accurate model as the starting point, and performs local search to find the local optimum. A new technique, called domain-alternated optimization is proposed to eliminate passivity constraints while still guarantees strict passivity during the optimization. Experiments show that taking the models generated from existing enforcement methods, the proposed method can provide significant improvement on accuracy. The proposed method is efficient and can deal with problems up to a few tens of thousands of variables.

Passivity enforcement is important for macro-modeling for passive systems from measured or simulated S-parameter data. State-space systems generated from vector fitting usually present strong passivity violation outside the frequency bandwidth especially in the close-to-band (CTB) region. Removing such close-to-band violation is very difficult with existing passivity enforcement techniques without severely sacrificing the accuracy of the model. In this paper we propose a frequency data extension method which aims to reduce or even eliminate such close-to-band violations without sacrificing model accuracy. The generated model can be used in a later stage for further passivity enforcement. Experiments show that with applying the proposed method, the accuracy of the generated model can be significantly improved.

High-sigma analysis is important for estimating the probability of rare events. Traditional high-sigma analysis can only work for small-size (low-dimension) problems limiting to 10 ~ 20 random variables, mostly due to the difficulty of finding optimal boundary points. In this paper we propose an efficient method to deal with high-dimension problems. The proposed method is based on performing optimization in a series of low dimension parameter spaces. The final solution can be regarded as a greedy version of the global optimization. Experiments show that the proposed method can efficiently work with problems with > 100 independent variables.

Traditional BSIM MOSFET model extraction considers I-V/C-V curve fitting to capture DC non-linearity and S-parameter fitting to capture high-frequency small-signal behavior. This leads to poor accuracy when modeling MOSFETs in large-signal RF circuits such as power amplifiers, which require to model high-frequency large-signal behavior of MOSFETs. In this paper, we proposed an automatic method for automatically modeling high-frequency large-signal behavior for MOSFETs. The input is a pre-characterized MOSFET model and large-signal measurement data. The output is an enhanced model that model not only DC and S-parameter characteristics but also large-signal behavior. Experiments show that the proposed method can accurately capture both the nonlinear and dynamic behavior of RF MOSFET.

SRAM cells generally require an extremely low failure rate (i.e., high yield) in the per cell basis to ensure a reasonably moderate yield for the whole chip. Existing yield analysis methods still encounter issues related to multiple failure regions resulting from high-dimensional process parameter space and/or multiple performance specifications. This paper proposes a new method that combines the advantages of existing importance sampling and boundary searching methods, and avoids issues in both. The key idea is to first find all likely failure regions and then, do importance sampling on these regions. Surrogate models are used to further accelerate the method so that SPICE-simulations can be highly reduced. Experimental results show that the proposed method is suitable for handling problems with multiple failure regions. Meanwhile, it can provide 5X ~ 20X speed-up over other existing techniques.

Scalable compact models for passive elements are important in the Analog/RF circuit design and optimization. Traditional scalable modeling methods are mainly physical and manual based methods, which usually require deep physical insight and extensive human intervention. In this paper, an automatic scalable compact modeling method for generic passive elements is established. The proposed method is a unified parameter extraction and scalable modeling scheme with novel inner-loop correlated parameter extraction and outer-loop adaptive boundary compression techniques. Experimental results show that both accuracy and scalability have been achieved by the proposed method for industrial inductors and transformers with an acceptable computational cost.

The great availability of massively parallel computing platforms gives rise a question to the EDA industry--how can this be really helping the productivity of circuit designs. Scalability of traditional parallel methods have shown to be limited as the computational resources keep increasing. In this paper we propose a time-domain segmentation method for massively parallel transistor-level simulation for short-memory circuits. SNDR simulation for ADCs is selected as the application as ADCs are typical short-memory circuits and the SNDR simulation is very time consuming. Experiments with realistic Flash and SAR ADCs demonstrate 64x-78x speed-ups with 100 CPU cores. With minor, yet important modifications, the proposed method can even be applied to simulation of Σ-Δ modulator, which does not satisfy the short-memory condition due to the presence of integrator, and 52x speed-up is observed with 100 CPU cores. The implementation of the proposed method is extremely simple and no modification to simulator is needed.

Massively repeated structures such as SRAM cells usually require extremely low failure rate. This brings on a challenging issue for Monte Carlo based statistical yield analysis, as huge amount of samples have to be drawn in order to observe one single failure. Fast Monte Carlo methods, e.g. importance sampling methods, are still quite expensive as the anticipated failure rate is very low. In this paper, a new method is proposed to tackle this issue. The key idea is to improve traditional importance sampling method with an efficient online surrogate model. The proposed method improves the performance for both stages in importance sampling, i.e. finding the distorted probability density function, and the distorted sampling. Experimental results show that the proposed method is 1e2X∼1e5X faster than the standard Monte Carlo approach and achieves 5X∼22X speedup over existing state-of-the-art techniques without sacrificing estimation accuracy.

Automatic macromodeling for passive linear systems is useful in RF/mm-wave circuit designs. Traditional macromodeling approaches only capture the port parameters of the systems, enabling small-signal (AC) and large-signal (transient, PSS, etc) analyses, but lack the capability of noise modeling which is very important in RF/mm-wave circuit designs. In this letter, we propose to account for noise in a traditional state-space-based passive macromodeling method. The proposed approach is to generate a noise companion model that describes the noise behavior in addition to a traditional state-space model that describes the port parameters. The proposed model supports small-signal noise analysis, periodic noise analysis, and large-signal transient noise analysis. In addition, the proposed model can work with commercial simulators seamlessly without modification to the simulator. Examples validate the proposed modeling method.

The floating random walk (FRW) algorithm has several advantages for extracting 3D interconnect capacitance. However, for multi-layer dielectrics in VLSI technology, the efficiency of FRW algorithm would be degraded due to frequent stop of walks at dielectric interface and constraint of first-hop length especially in thin dielectrics. In this paper, we tackle these problems with the numerical characterization of Green's function for cross-interface transition probabilities and the corresponding weight value. We also present a space management technique with Octree data structure to reduce the time of each hop and parallelize the whole FRW by multi-threaded programming. Numerical results show large speedup brought by the proposed techniques for structures under the VLSI technology with thin dielectric layers.

Power consumption has become a major concern since the integrated circuit industry entered the nanometer design regime. Due to the increasing process variation, deterministic leakage power analysis becomes inadequate and thus statistical analysis is required. The challenges of statistical leakage analysis are that the huge number of random variables make trivial computation of the variance inO(N2) time impractical for realistic designs and that knowing only the first two moments is not sufficient to obtain the distribution of the full-chip leakage. In this paper, we introduce efficient linear time algorithms for statistical leakage analysis. To enable those algorithms, a fast matrix vector product technique is crucial, being applied not only to compute the second moment of the total leakage, but also, combined with a comonotonic approximation, to estimate the distribution function of the total leakage power. The computational complexity of the proposed algorithms is provablyO(N), and the experimental result is presented with detailed discussion, indicating promising improvement in terms of accuracy.

With the continuous shrinking of the feature size, the effect of stress on the performance of the IC device and circuit can no longer be ignored. In fact, stress engineering is becoming more and more widely used today in advanced IC manufacture processes to improve device performance. Different from the intentionally introduced stresses to improve circuit performance, the shallow-trench-isolation (STI) stress, which is exerted by STI wells on the active area of devices, is a by-product of the fabrication process and has increasingly significant impact on the circuit behavior. This paper proposes a complete flow to characterize the influence of STI stress on the performance of RF/analog circuits by considering detailed layout and process information. An accurate and efficient finite-element method-based stress simulator has been developed to extract stress distribution from layouts of IC designs. The existing MOSFET model is also enhanced to capture the effects of stress on mobility, threshold voltage. With the enhanced model, we are able to study the influence of layout-dependent STI stress on the performance of real circuits and establish corresponding optimization strategies. The proposed flow has been applied to a series of RF/analog IC designs based on a 90-nm CMOS technology.

Random process variations are often composed of location dependent part and distance dependent correlated part. While an accurate extraction of process variation is a prerequisite of both process improvement and circuit performance prediction, it is not an easy task to characterize such complicated spatial random process from a limited number of silicon data. For this purpose, kriging model was introduced to silicon society. This work forms a modified kriging model with L1-norm penalty which offers improved robustness. With the help of Least Angle Regression (LAR) in solving a core optimization sub-problem, this model can be characterized efficiently. Some promising results are presented with numerical experiments where a 3X improvement in model accuracy is shown.

Passivity enforcement is an important issue for macro-modeling for passive systems from measured or simulated data. Existing convex programming based methods are too expensive and thus are ruled out for realistic application. Other methods based on iteratively fixing the passivity through perturbing the eigenvalues of the Hamiltonian matrix either suffer from convergence issue or lack optimality which will sometimes lead to unacceptable error. In this paper we propose a novel framework for macro-modeling. In addition to the traditional two-stage (fixing plus enforcement) schemes, we propose a post-enforcement optimization, which takes a passive, while potentially not-so-accurate model, as the starting point, and performs local search to find the local optimum with passivity constraint or build-in passivity guarantee. A simple yet stable passive modeling generator is proposed to produce the starting model for optimization. Two algorithms are proposed for performing constrained and unconstrained optimizations. Experiments show that the accuracy of passivity-fixed model can be significantly improved with the proposed methods.

Existing approaches to statistical leakage analysis focus only on calculating the mean and variance of the total leakage. In practice, however, what concerns most is the tail behavior of the sum distribution, as it tells that to what extent the design will be safe or reliable. However, computing the tail distribution is much more difficult than computing the mean and variance. In this paper, we tackle this problem by making use of the recent developments in the area of financial and insurance analysis, as well as the fast evaluation algorithm for the variance of spatially correlated random sums. The proposed algorithm is provably of O(N) complexity. Experiments show that the algorithm provides 1% accuracy in modeling the tail behavior and it is 10X more accurate compared with existing methods that approximate the distribution by matching the moments of a lognormal distribution.

An efficient algorithmbased on the Extended Hamiltonian Pencil was proposed in [1] for systems with hybrid representation. Here we further extend the Extended Hamiltonian Pencil method to systems described with scattering representation, i.e. S-parameter systems. The derivation of the Extended Hamiltonian Pencil for S-parameter systems is presented. Some properties that allow passivity enforcement based on eigenvalue displacement are reported. Experimental results demonstrate the effectiveness of the proposed method.

With the continuous shrinking of feature size, various effects due to shallow-trench-isolation (STI) stress are becoming more and more significant. The resulting nonuniform distribution of stress affects the MOSFET characteristics and hence changes the circuit behavior. This paper proposes a complete flow to characterize the influence of STI stress on performance of RF/analog circuits based on layout design and process information. An accurate and efficient FEM-based stress simulator has been developed to handle the layout dependence. A comprehensive MOSFET model is also proposed to capture the effects of STI stress on mobility, threshold voltage, and leakage current. The influence of layout-dependent STI stress on the circuit performance is further studied, and the corresponding optimization strategies to circuit design are discussed. A realistic PLL design realized using 90nm CMOS technology is used as a test case for the proposed approach.

Passivity is an important property for a macro-model generated from measured or simulated data. Existence of purely imaginary eigenvalues of a Hamiltonian matrix provides useful information in assessing and correcting the passivity of a system. Since direct computation of eigenvalues is very expensive for large-scale systems, several authors have proposed to solve iteratively for a subset of the eigenvalues based on heuristic sampling along the imaginary axis. However, completeness is not guaranteed in such methods and thus potential risk of missing important eigenvalues is difficult to avoid. In this paper we are aiming at finding all eigenvalues efficiently to avoid both the high cost and the potential risk of missing important eigenvalues. The idea of the proposed method is to convert the Hamiltonian matrix to an equivalent sparse form, termed the "extended Hamiltonian pencil", and solve for its eigenvalues efficiently using a special eigensolver. Experiments on several realistic systems demonstrate an 80X speed-up compared with standard direct eigensolvers.

Statistical full-chip leakage analysis considering spatial correlation is highly expensive due to its O(N2) complexity for logic circuits with N gates. Although efforts have been made to reduce the cost at the loss of accuracy, existing methods are still unsuitable for large-scale problems. In this paper we resolve the problem by re-formulating the computation to one that can be done efficiently using a well-developed technique that has been widely used in fast EM simulation and machine learning areas. The resulting algorithm is provably of O(N) or O(N log N) complexity with well-defined and easily-controlled error bounds. Experiments show that using the proposed method it is feasible to handle milliongate circuits within only a few minutes on a regular desktop PC. The corresponding error is less than 0.5% compared to exhausted computation that takes more than 3 days. The proposed method is about 300X faster and 10X more accurate compared to existing grid-approximation method.

In this paper, we propose methods to accelerate the solution of multiple related linear systems of equations. Such systems arise, for example, in building pattern libraries for interconnect parasitic extraction, parasitic extraction under process variation, and parameterized interconnect characterization. Our techniques include methods based on a generalized form of ldquorecycledrdquo Krylov subspace methods that use the sharing of information between related systems of equations to accelerate the iterative solution and methods to reuse computational effort during system matrix setup. Experimental results on electrostatic problems demonstrate significant improvement over existing methods that are based on solving each system individually. The proposed methods are generic, fully treat nonlinear perturbations without approximation and can potentially be applied to a wide variety of application domains outside electrostatic analysis.

In this paper we propose methods for fast iterative solution of multiple related linear systems of equations. Such systems arise, for example, in building pattern libraries for interconnect parasitic extraction, parasitic extraction under process variation, and parameterized interconnect characterization. Our techniques are based on a generalized form of "recycled" Krylov subspace methods that use sharing of information between related systems of equations to accelerate the iterative solution. Experimental results on electromagnetics problems demonstrate that the proposed method can achieve a speed-up of 5X~30X compared to direct GMRES applied sequentially to the individual systems. These methods are generic, fully treat nonlinear perturbations without approximation, and can be applied in a wide variety of application domains outside electromagnetics.

This paper is concerned with model order reduction of large scale dynamic systems that have sparse matrix representations, particularly systems with large numbers of input/output ldquoports.rdquo We present an algorithm that combines the advantages of widely-used approaches such as PRIMA and TICER but avoids many of the drawbacks of both. The resulting algorithm is capable of high-order rational approximation, exploits network sparsity, preserves passivity, can be extended to general non-symmetric systems, and can be applied to networks with hundreds or thousands of ports. We develop a common mathematical framework that can encompass all three algorithms, show mathematical relations between them, and point out certain special cases where they are equivalent. We show examples from analysis of industrial on-chip RC/RLC networks that demonstrate performance advantages of more than three orders of magnitude.

An efficient method based on a direct boundary element method is proposed for extracting frequency-dependent substrate coupling parameters. A frequency-independent real-valued linear equation system is first solved. Then, the solution is transformed into frequency-dependent parameters at a specified frequency with the Sherman-Morrison-Woodbury formula. The first step is performed only once for a given structure, and the method is very efficient for extraction with multiple frequencies. The proposed method is compared with the Green's function-based method and the approach in our earlier paper for typical substrate structures. Numerical results demonstrate its accuracy, efficiency, and versatility.

An efficient algorithm for three-dimensional (3-D) capacitance extraction on multi-layered and lossy substrate is presented. The new algorithm represents a major improvement over the quasi-3D approach used in Green's function-based solvers by taking into consideration of the side-wall effects of the conductors. The accuracy and efficiency of the new algorithm is tested by examples.