The clock frequency of a digital IC is limited by its slowest paths, designated by speedpaths. Given the extreme complexity involved in modeling modern IC technologies, often speedpath predictions provided by timing analysis tools are not correct. Therefore, several practical techniques have recently been proposed for design debugging, that combine silicon stepping of improved versions of a circuit with subsequent correlation between measured and predicted data. Addressing these issues, this paper proposes a set of techniques that enable the designer to obtain reduced subsets of paths, guaranteed to contain all the speedpaths of a given circuit or block. Such subsets can be computed either from timing models, prior to fabrication, or incorporating actual delay measurements from fabricated instances.

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.

Traditional integrated circuit timing sign-off consists of verifying a design for a set of carefully chosen combinations of process and operating parameter extremes, referred to as corners. Such corners are usually chosen based on the knowledge of designers and process engineers, and are expected to cover the worst-case fabrication and operating scenarios. With increasingly more detailed attention to variability, the number of potential conditions to examine can be exponentially large, more than is possible to handle with straightforward exhaustive analysis. This paper presents efficient yet exact techniques for computing worst-delay and worst-slack corners of combinational and sequential digital integrated circuits. Results show that the proposed techniques enable efficient and accurate detection of failing conditions while accounting for timing variability due to process variations.

Modern deep sub-micron ultra-large scale integration designs with hundreds of millions of devices require huge grids for power distribution. Such grids, operating with decreasing power supply voltages, are a design limiting factor and accurate analysis of their behavior is of paramount importance as any voltage drops can seriously impact performance or functionality. As power grid models have millions of unknowns, highly optimized special-purpose simulation tools are required to handle the time and memory complexity of solving for their dynamic behavior. In this paper, we propose a hierarchical matrix representation of the power grid model that is both space and time efficient. With this representation, reduced storage matrix factors are efficiently computed and applied in the analysis at every time-step of the simulation. Results show an almost linear complexity growth, namelyO(n loga(n)), for some small constant a, in both space and time, when using this matrix representation. Comparisons of our academic implementation with production-quality code prove this method to be very efficient when dealing with the simulation of large power grid models.

Boolean satisfiability (SAT) based methods have traditionally been popular for formally verifying properties for digital circuits. We present a novel methodology for formulating a SPICE-type circuit simulation problem as a satisfiability problem. We start with a circuit level netlist, capture the non-linear behavior of the circuits at the transistor level via conservative approximations and transform the simulation problem into a search problem that can be exhaustively explored via a SAT solver. Thus, for DC as well as fixed time-step based transient and periodic steady state (PSS) simulation formulations, the solutions produced by the solver are formal in nature. We also present algorithms for abstraction refinement and smart interval generation to improve the computational efficiency of our proposed solution scheme. We have implemented our ideas into a tool called fSpice which is the first attempt at building a formal SPICE engine. We demonstrate the applicability of our ideas by showing experimental results using pruned versions of real designs that faced challenges during chip tape-out. Categories and Subject Descriptors I.6.5 [Simulation and Modeling]: Model Development General Terms Algorithms, Design

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.

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.

Modern deep sub-micron ULSI designs with hundreds of millions of devices require huge grids for power distribution. Such grids, operating with increasingly low-power voltages, are a design limiting factor and accurate analysis of their behavior is of paramount importance as any voltage drops can seriously impact performance or functionality. As power grid models have millions of unknowns, highly optimized special purpose simulation tools are required to handle the time and memory complexity of solving for their dynamic behavior. In this work, we propose a hierarchical matrix representation of the power grid model that is both space and time efficient. With this representation, reduced storage matrix factors are efficiently computed and applied in the analysis at every time-step of the simulation. Results show an almost linear complexity growth, namely O(n loga(n)), for some small constant a, in both space and time, when using this matrix representation. Comparisons of our academic implementation with production-quality code proves this method to be very efficient when dealing with the simulation of large power grid models.

The current shift from sequential to multicore and manycore processors presents serious challenges to software developers. A significant part of the industrial and research communities believes that either a) they can squeak by or b) the right compiler, parallel language etc will save them. Such ad hoc responses are likely to prove neither correct nor sustainable. To systematically find and exploit parallelism, and to achieve forward scalability - that is, designs which efficiently scale to much larger numbers of cores -- will require re-architecting software applications such as EDA.

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.

In this paper, we discuss the multi-interval Chebyshev (MIC) method for analog and radio-frequency (RF) circuit simulations. The method has been applied in a wide variety of circuit analyses including periodic steady-state, time-varying small signal, and cyclostationary noise analyses for both driven and autonomous circuits. In contrast to traditional analog/RF circuit simulations using either low-order time-domain integration methods or harmonic balance methods, we show that the MIC method can efficiently achieve high accuracy on strongly nonlinear circuits possessing waveforms with rapid transitions. In addition, it has the same flexibility in simulating frequency-dependent components as the harmonic balance methods but can use similar preconditioning strategies and matrix-implicit Krylov-subspace solvers as time-domain techniques, leading to good convergence on nonlinear problems.

We present a waveform based variational static timing analysis methodology. It is a timing paradigm that lies midway between convention static delay approximations and full dynamic (SPICE-level) analysis. The core idea is to break the modulation of waveforms processed by a circuit into two parts: (a) non-linear circuit elements e.g., transistors, diodes etc. and (b) linear elements: transmission line, RLC network etc. The non-linear and linear parts of the circuit are then solved using a combination of current-source modeling, model order reduction methodology, perturbation analysis and learning-based Galerkin methods which helps us get SPICE-like accuracies. The proposed method is potentially as robust and 10-20times faster than current-source based gate modeling methodologies

Variability in digital integrated circuits makes timing verification an increasingly challenging task. Statistical static timing analysis has been proposed as a solution to this problem, but most of the work has concentrated in the development of timing engines for computing delay propagation. Such tools rely on the availability of delay formulas accounting for both cell and interconnect delay. In this paper, we concentrate on the impact of interconnect on delay and propose an extension to the standard modeling strategies that is variation-aware and compatible with such statistical engines. Our approach, based on a specific type of perturbation analysis, allows for the analytical computation of the quantities needed for statistical delay propagation. We also show how perturbation analysis can be performed when only the standard delay table lookup models are available for the standard cells. Results from applying our proposed modeling strategy to computing delays and slews in several instances accurately match similar results obtained using electrical level simulation

Multipoint projection methods have gained much notoriety in model-order reduction of linear, nonlinear, and parameter-varying systems. A well-known difficulty with such methods lies in the need for clever point selection to attain model compactness and accuracy. In this paper, the authors present a method for sample point selection in multipoint projection-based model-order reduction. The proposed technique, which is borrowed from the statistical modeling area, is based on resampling schemes to estimate error and can be coupled with recently proposed order reduction schemes to efficiently produce accurate models. Two alternative implementations are presented: 1) a rigorous linear-matrix-inequality-based technique and 2) a simpler, more efficient, heuristic search. The goal of this paper is to answer two questions. First, can this alternative metric be effective in selecting sample points in the sense of placing points in regions of high error without recourse to evaluation of the larger system? Second, if the metric is effective in this sense, under what conditions are substantial improvements in the model reduction efficiency achieved? Results are shown that indicate that the metric is indeed effective in a variety of settings, therefore opening the possibility for performing adaptive error control

This work presents a model reduction algorithm motivated by a connection between frequency-domain projection methods and approximation of truncated balanced realizations. The method is computationally simple to implement, has near-optimal error properties, and possesses simple error estimation and order-control procedures. Usage of the method also enables straightforward exploitation of information about the particular application and setting, as well as circuit functional information, such as frequency weighting information and correlations between network port waveforms. When such specific information is available, standard truncated balanced realization algorithms generate models far from optimal according to statistical decision criteria. Examples are shown to demonstrate that the method can outperform the standard order reduction techniques by providing similar accuracy with lower order models or superior accuracy for the same size model.

In this paper we present a model reduction algorithm that circumvents some of the issues encountered for parasitic networks with large numbers of input/output "ports". Our approach is based on the premise that for such networks, there are typically strong dependencies between the input waveforms at different network "ports". We present an approximate truncated balanced realizations procedure that, by exploiting such correlation information, produces much more compact models compared to standard algorithms such as PRIMA.

This paper presents a model reduction algorithm motivated by a connection between frequency domain projection methods and approximation of truncated balanced realizations. The method produces guaranteed passive models, has near-optimal error properties, is computationally simple to implement, contains error estimators, and can incorporate frequency weighting information in a straightforward manner. Examples are shown to prove that the method can outperform the standard order reduction techniques by providing similar accuracy with lower models or superior accuracy for the same size model.

We demonstrate an algorithm for interconnect modeling in the presence of process variation based on extension of the truncated balanced realization model reduction algorithm to multi-dimensional, parameter varying systems. Our scheme, based on a set of estimators of the variational TBR projection spaces, is simple to implement, contains embedded error estimators, and leads to nearly optimally sized models.

In this paper, we present a methodology for generating guaranteed passive time-domain models of subsystems described by tabulated frequency-domain data obtained through measurement or through physical simulation. Such descriptions are commonly used to represent on- and off-chip interconnect effects, package parasitics, and passive devices common in high-frequency integrated circuit applications. The approach, which incorporates passivity constraints via convex optimization algorithms, is guaranteed to produce a passive-system model that is optimal in the sense of having minimum error in the frequency band of interest over all models with a prescribed set of system poles. We demonstrate that this algorithm is computationally practical for generating accurate high-order models of data sets representing realistic, complicated multiinput, multioutput systems.

The problem of automated macromodel generation is interesting from the viewpoint of system-level design because if small, accurate reduced-order models of system component blocks can be extracted, then much larger portions of a design, or more complicated systems, can be simulated or verified than if the analysis were to have to proceed at a detailed level. The prospect of generating the reduced model from a detailed analysis of component blocks is attractive because then the influence of second-order device effects or parasitic components on the overall system performance can be assessed. In this way overly conservative design specifications can be avoided. This paper reports on experiences with extending model reduction techniques to nonlinear systems of differential-algebraic equations, specifically, systems representative of RF circuit components. The discussion proceeds from linear time-varying, to weakly nonlinear, to nonlinear time-varying analysis, relying generally on perturbational techniques to handle deviations from the linear time-invariant case. The main intent is to explore which perturbational techniques work, which do not, and outline some problems that remain to be solved in developing robust, general nonlinear reduction methods.

The major concerns in state-of-the-art model reduction algorithms are: achieving accurate models of sufficiently small size, numerically stable and efficient generation of the models, and preservation of system properties such as passivity. Algorithms, such as PRIMA, generate guaranteed-passive models for systems with special internal structure, using numerically stable and efficient Krylov-subspace iterations. Truncated balanced realization (TBR) algorithms, as used to date in the design automation community, can achieve smaller models with better error control, but do not necessarily preserve passivity. In this paper, we show how to construct TBR-like methods that generate guaranteed passive reduced models and in addition are applicable to state-space systems with arbitrary internal structure.

This paper presents a class of algorithms suitable for model reduction of distributed systems. Distributed systems are not suitable for treatment by standard model-reduction algorithms such as PRIMA, PVL, and the Arnoldi schemes because they generate matrices that are dependent on frequency (or other parameters) and cannot be put in a lumped or state-space form. Our algorithms build on well-known projection-based reduction techniques, and so require only matrix-vector product operations and are thus suitable for operation in conjunction with electromagnetic analysis codes that use iterative solution methods and fast-multipole acceleration techniques. Under the condition that the starting systems satisfy system-theoretic properties required of physical systems, the reduced systems can be guaranteed to be passive. For distributed systems, we argue that causality of the underlying representation is as important a consideration.

The major concerns in state-of-the-art model reduction algorithms are: achieving accurate models of sufficiently small size, numerically stable and efficient generation of the models, and preservation of system properties such as passivity. Algorithms such as PRIMA generate guaranteed-passive models, for systems with special internal structure, using numerically stable and efficient Krylov-subspace iterations. Truncated Balanced Realization (TBR) algorithms, as used to date in the design automation community, can achieve smaller models with better error control, but do not necessarily preserve passivity. In this paper we show how to construct TBR-like methods that guarantee passive reduced models and in addition are applicable to state-space systems with arbitrary internal structure.

Simulation of RF circuits often demands analysis of distributed component models that are described via frequency-dependent multi-port Y, Z, or S parameters. Frequency-domain methods such as harmonic balance are able to handle these components without difficulty, while they are more difficult for time-domain simulation methods to treat. In this paper, we propose a hybrid frequency-time approach to treat these components in steady-state time-domain simulations. Efficiency is achieved through the use of the multi-interval Chebyshev (MIC) simulation method and a low-order rational-fitting model for preconditioning matrix-implicit Krylov-subspace solvers.

As system integration evolves and tighter design constraints must be met, it becomes necessary to account for the non-ideal behavior of all the elements in a system. For high-speed digital, and microwave systems, it is increasingly important to model previously neglected frequency domain effects. In this paper, results from Nevanlinna-Pick interpolation theory are used to develop a bounded real matrix rational approximation algorithm. A method is presented that allows for the generation of guaranteed passive rational function models of passive systems by approximating their scattering parameter matrices. Since the order of the models may in some cases be high, an incremental fitting strategy is also proposed that allows for the generation of smaller models while still meeting the required passivity and accuracy requirements. Results of the application of the proposed method to several real-world examples are also shown.

Verification of contemporary integrated circuits requires accurate modeling of high-frequency effects in all passive component sub-systems. Often, descriptions of those subsystems are only available in the frequency-domain. In this paper, we propose a simple, scalar, constrained-passive rational approximation scheme that incorporates a grid-based test for strict positive realness. In contrast to similar recent work based on convex optimization and the positive real lemma, the methodology is potentially more efficient, since it does not introduce a quadratic number of auxiliary variables, is potentially more accurate, since pole locations can be re-adjusted during the optimization, but possibly less reliable, since it relies on the solution of optimization problems that are not convex. There-fore, because of the use of local constrained non-convex optimization, the generation of feasible initial guesses is also considered.

Wireless transceivers for digital telecommunications are heterogeneous systems that combine digital hardware, software and analog circuitry. The pressure to miniaturization and lower power consumption for these transceivers imposes tight specifications on their analog RF parts. Many aspects of RF circuits cannot be simulated accurately and efficiently with a classical circuit-level SPICE approach. In this paper three important simulation problems for RF circuits are addressed: 1. High-level simulation of analog and RF blocks for the determination of the specifications of the circuits. 2. Accurate circuit-level simulation of nonlinear circuits with time constants that differ largely. 3. Efficient and accurate computation of phase noise in RF oscillators. For each of these problems, solutions are proposed. These solutions illustrate that accurate and efficient simulations of RF communication circuits need a heterogeneous variety of advanced algorithms.

Shrinking feature sizes and increasing speeds of operation make interconnect-related effects very relevant for current circuit verification methodologies. Reliable and accurate system verification requires the full analysis of circuits together with the environment that surrounds them, including the common substrate, the packaging structures, and perhaps even board information. In this paper we discuss circuit-level simulation algorithms that enable the analysis of the impact of strongly coupled interconnect structures on nonlinear circuit operation, so as to allow reliable and accurate system verification.

The sudden increase in systems-on-a-chip designs has renewed interest in techniques for analyzing and eliminating substrate coupling problems. Previous work on the substrate coupling analysis has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting network whose number of resistors grows quadratically with the number of contacts. In this paper we show that an approach inspired by wavelets can be used in two ways. First, the wavelet method can be used to accurately sparsify the dense contact conductance matrix. In addition, we show that the method can be used to compute the sparse representation directly. Computational results are presented that show that for a problems with a few thousand contacts, the method can be almost ten times faster at constructing the matrix.

In this paper we present a generalization of popular linear model reduction methods, such as Lanczos- and Arnoldi-based algorithms based on rational approximation, to systems whose response to interesting external inputs can be described by a few terms in a functional series expansion such as a Volterra series. The approach allows automatic generation of macromodels that include frequency-dependent nonlinear effects.

Most RF circuit analysis tools use either shooting-Newton or harmonic balance methods. Neither can efficiently achieve high accuracy on strongly nonlinear circuits possessing waveforms with rapid transitions. We present a multi-interval-Chebyshev (MIC) method that discretizes the circuit equations by dividing the simulation domain into a set of intervals whose size is adaptively chosen and using Chebyshev polynomials to represent the solution in each interval. The MIC method has excellent stability properties, is as effective at solving nonlinear problems as shooting techniques, can achieve high resolution on a wide variety of circuits, and in conjunction with an appropriate preconditioner can be combined with matrix-implicit Krylov-subspace solvers to analyze large circuits with moderate computational cost.

The problem of computing rational function approximations to tabulated frequency data is of paramount importance in the modeling arena.In this paper we present a method for generating a state space model from tabular data in the frequency domain that solves some of the numerical difficulties associated with the traditional fitting techniques used in linear least squares approximations.An extension to the MIMO case is also derived.

Design of communications circuits often requires computing steady-state responses to multiple periodic inputs of differing frequencies.Mixed frequency-time (MFT) approaches are orders of magnitude more efficient than transient circuit simulation, and perform better on highly nonlinear problems than traditional algorithms such as harmonic balance.We present algorithms for solving the huge nonlinear equation systems the MFT approach generates from practical circuits.

h this paper a method is presented for model reduction of systemsdescribedby time-var-ying differential-algebraicequations.~i method aUowsautomated extraction of reduced modek for nordinearM blocks,such as mixers and ~ters, that havea near-Enear signalpath but may containstronglynordinear time-varyingcomponents. me modek have the accuracy of a transistor-levelnordinearsimulationbut are very compact and so can be used in system-levelsimulationand design.me modelreductionprocedureis basedona multipointrational approximationalgorithm formed by orthogonalprojection of the originaltime-varyingHnearsystemintoan approximate@lov subspace.me modek obtainedfrom the approximate fiylovsubspaceprojector an be obtainedmuch more easilythan the exact projectors but shownegligibledifferencein accuracy.1 Overview me problemof automatedmacromodelgenerationis interesting from the viewpoint of system-level design because if small, accurate reduced-order models of system component blocks can be extracted, then much larger portions of a design, or more complicated systems, can be simulated or verified than if the analysis were to have to proceed at a detailed level.me prospect of generating the reduced model from a detailed analysis of component blocks is attractive because then the influence ofsecond-orderdevice effects or parasitic components on the ovedl system performance can be assessed.In this way overly conservative design specifications can be avoided.mere has been considerable recent interest, primarily in the context of simulation of electrical interconnect, in extracting loworder models of lumped (often passive) components that are timeinvariant.mere are many systems, however, that are not linear time-invariant &~) but can be accurately modeled as linear timevarying (LW).For example, if a nordinear circuit model is tineanzed around a time-varying large signal, the resulting model is linear time-varying.In pficular, many RF components (e.g., mixers and filters) are designed to have a near-linear response in the signal path, but may have strongly nonlinear response to other excitations, such as the clock of a switched-capacitor filter, or a mixer's local oscillator.Such components are prime candidates for LN model reduction.Clearly, the set of circuits that can be accurately modeled as tinear-time varying is much larger than the set that cart be described as LV.

No abstract available.

In this paper we present a new algorithm for accelerating the potential calculation which occurs in the inner loop of iterative algorithms for solving electromagnetic boundary integral equations. Such integral equations arise, for example, in the extraction of coupling capacitances in three-dimensional (3-D) geometries. We present extensive experimental comparisons with the capacitance extraction code FASTCAP and demonstrate that, for a wide variety of geometries commonly encountered in integrated circuit packaging, on-chip interconnect and micro-electro-mechanical systems, the new "precorrected-FFT" algorithm is superior to the fast multipole algorithm used in FASTCAP in terms of execution time and memory use. At engineering accuracies, in terms of a speed-memory product, the new algorithm can be superior to the fast multipole based schemes by more than an order of magnitude.