Image corruption by motion artifacts is an ingrained problem in Magnetic Resonance Imaging (MRI). In this work, we propose a neural network-based regularization term to enhance Autofocusing, a classic optimization-based method to remove motion artifacts. The method takes the best of both worlds: the optimization-based routine iteratively executes the blind demotion and deep learning-based prior penalizes for unrealistic restorations and speeds up the convergence. We validate the method on three models of motion trajectories, using synthetic and real noisy data. The method proves resilient to noise and anatomic structure variation, outperforming the state-of-the-art demotion methods.

The list of Professor Alberto Sangiovanni-Vincentelli's research contributions is astounding in length and breadth, yet does not entirely capture what this author believes is his true genius. In so many areas of computer-aided design, Sangiovanni-Vincentelli provided the intellectual framework, often nucleating a research community in the process. Of personal familiarity is the area of transistor-level timing simulation, now better known as "Fast SPICE". In the decades since Sangiovanni-Vincentelli's papers on circuit simulation, relaxation, and third generation techniques, simulation sizes have grown from thousands to millions of transistors, vectorized main frames have given way to GPUs and multicores and clouds, yet his papers are still the defining taxonomy for the field.

Rapidly diversifying technology and declining computational costs are popularizing technologically flexible simulation and verification techniques, even at some cost in performance. This paper investigates a data-driven, sampling-based approach for computing substrate Green's functions, which is more technology flexible than specialized layered media methods, at the cost of speed and accuracy. Our method is based on assuming that grid-sampled Green's functions can be well approximated by Toeplitz-plus-Hankel (TPH) matrices, and uses a least squares procedure to recover a TPH matrix from a small number of samples. We show that sample location is crucial, and that good sample locations are the ones that minimize an associated graph-diameter-based condition number estimate. The method's expected effectiveness is demonstrated on noise-polluted samples of layered media Green's functions. More surprisingly, we show that the method is effective even when applied to a substrate geometry that is only mildly planar.

The dynamic behaviors of signaling pathways can provide clues to pathway mechanisms. In cancer cells, excessive phosphorylation and activation of the Akt pathway is responsible for cell survival advantages. In normal cells, serum stimulation causes brief peaks of extremely high Akt phosphorylation before reaching a moderate steady-state. Previous modeling assumed this peak and decline behavior (i.e., "overshoot") was due to receptor internalization. In this work, we modeled the dynamics of the overshoot as a tool for gaining insight into Akt pathway function. We built an ordinary differential equation (ODE) model describing pathway activation immediately upstream of Akt phosphorylation at Thr308 (Aktp308). The model was fit to experimental measurements of Aktp308, total Akt, and phosphatidylinositol (3,4,5)-trisphosphate (PIP3), from mouse embryonic fibroblasts with serum stimulation. The canonical Akt activation model (the null hypothesis) was unable to recapitulate the observed delay between the peak of PIP3 (at 2 minutes), and the peak of Aktp308 (at 30-60 minutes). From this we conclude that the peak and decline behavior of Aktp308 is not caused by PIP3 dynamics. Models for alternative hypotheses were constructed by allowing an arbitrary dynamic curve to perturb each of 5 steps of the pathway. All 5 of the alternative models could reproduce the observed delay. To distinguish among the alternatives, simulations suggested which species and timepoints would show strong differences. Time-series experiments with membrane fractionation and PI3K inhibition were performed, and incompatible hypotheses were excluded. We conclude that the peak and decline behavior of Aktp308 is caused by a non-canonical effect that retains Akt at the membrane, and not by receptor internalization. Furthermore, we provide a novel spline-based method for simulating the network implications of an unknown effect, and we demonstrate a process of hypothesis management for guiding efficient experiments.

The TGF-β/Smad signaling system decreases its activity through strong negative regulation. Several molecular mechanisms of negative regulation have been published, but the relative impact of each mechanism on the overall system is unknown. In this work, we used computational and experimental methods to assess multiple negative regulatory effects on Smad signaling in HaCaT cells. Previously reported negative regulatory effects were classified by time-scale: degradation of phosphorylated R-Smad and I-Smad-induced receptor degradation were slow-mode effects, and dephosphorylation of R-Smad was a fast-mode effect. We modeled combinations of these effects, but found no combination capable of explaining the observed dynamics of TGF-β/Smad signaling. We then proposed a negative feedback loop with upregulation of the phosphatase PPM1A. The resulting model was able to explain the dynamics of Smad signaling, under both short and long exposures to TGF-β. Consistent with this model, immuno-blots showed PPM1A levels to be significantly increased within 30 min after TGF-β stimulation. Lastly, our model was able to resolve an apparent contradiction in the published literature, concerning the dynamics of phosphorylated R-Smad degradation. We conclude that the dynamics of Smad negative regulation cannot be explained by the negative regulatory effects that had previously been modeled, and we provide evidence for a new negative feedback loop through PPM1A upregulation. This work shows that tight coupling of computational and experiments approaches can yield improved understanding of complex pathways.

6.002x is the first electronic circuits course to be taught online to tens of thousands of students. The goal of the 6.002x experiment was to explore ways to use computer assisted instruction to surpass the quality of traditional residential teaching. By providing superior on-line content delivery and assessment, we hope to both be able to educate people without access to education, and to improve residential education by allowing professors to focus on higher value tasks. We improved on the classroom experience in several ways. Students can actively monitor their current levels of mastery and to self-pace in response. They can identify and break through misconceptions before moving on to more advanced material. The massive scale of the classroom has participants on-line 24/7, allowing students to ask questions and receive peer answers in almost real-time. The platform allows for substantial data collection on testing, allowing us to incrementally and scientifically improve courses. Finally, the amount of effort that can be invested into a course is much greater when it can be amortized across tens of thousands. In order to achieve this, we had to overcome a number of challenges: finding mechanisms to allow automated grading, overcoming the lack of in-person interactions, and overcoming the lack of student access to laboratory equipment. The course was shown successful in both residential and mass-scale settings.

MOTIVATION: Computational models of biological signalling networks, based on ordinary differential equations (ODEs), have generated many insights into cellular dynamics, but the model-building process typically requires estimating rate parameters based on experimentally observed concentrations. New proteomic methods can measure concentrations for all molecular species in a pathway; this creates a new opportunity to decompose the optimization of rate parameters. RESULTS: In contrast with conventional parameter estimation methods that minimize the disagreement between simulated and observed concentrations, the SPEDRE method fits spline curves through observed concentration points, estimates derivatives and then matches the derivatives to the production and consumption of each species. This reformulation of the problem permits an extreme decomposition of the high-dimensional optimization into a product of low-dimensional factors, each factor enforcing the equality of one ODE at one time slice. Coarsely discretized solutions to the factors can be computed systematically. Then the discrete solutions are combined using loopy belief propagation, and refined using local optimization. SPEDRE has unique asymptotic behaviour with runtime polynomial in the number of molecules and timepoints, but exponential in the degree of the biochemical network. SPEDRE performance is comparatively evaluated on a novel model of Akt activation dynamics including redox-mediated inactivation of PTEN (phosphatase and tensin homologue). AVAILABILITY AND IMPLEMENTATION: Web service, software and supplementary information are available at www.LtkLab.org/SPEDRE SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: TRAIL has been widely studied for the ability to kill cancer cells selectively, but its clinical usefulness has been hindered by the development of resistance. Multiple compounds have been identified that sensitize cancer cells to TRAIL-induced apoptosis. The drug LY303511 (LY30), combined with TRAIL, caused synergistic (greater than additive) killing of multiple cancer cell lines. We used mathematical modelling and ordinary differential equations to represent how LY30 and TRAIL individually affect HeLa cells, and to predict how the combined treatment achieves synergy. RESULTS: Model-based predictions were compared with in vitro experiments. The combination treatment model was successful at mimicking the synergistic levels of cell death caused by LY30 and TRAIL combined. However, there were significant failures of the model to mimic upstream activation at early time points, particularly the slope of caspase-8 activation. This flaw in the model led us to perform additional measurements of early caspase-8 activation. Surprisingly, caspase-8 exhibited a transient decrease in activity after LY30 treatment, prior to strong activation. cFLIP, an inhibitor of caspase-8 activation, was up-regulated briefly after 30 min of LY30 treatment, followed by a significant down-regulation over prolonged exposure. A further model suggested that LY30-induced fluctuation of cFLIP might result from tilting the ratio of two key species of reactive oxygen species (ROS), superoxide and hydrogen peroxide. Computational modelling extracted novel biological implications from measured dynamics, identified time intervals with unexplained effects, and clarified the non-monotonic effects of the drug LY30 on cFLIP during cancer cell apoptosis.

We present a few modifications that stabilize nonlinear reduced order models generated by discrete empirical interpolation methods. We combine a different approach to linearization with a multipoint stabilization technique. The examples used to demonstrate our method's effectiveness are a nonlinear transmission line, a micromachined switch, and a nonlinear thermal model for an RF amplifier.

Computing parametric sensitivities for oscillators has a now well-understood subtlety associated with the indeterminacy of phase. A less universal, but still vexing, subtlety arises when an oscillator is described by a system of differential equations with "hidden" conservation constraints (HCC's); defined as weighted sums of state variables that are time-invariant. If there are HCC's, as is commonly the case for models of biochemical oscillators but rarely the case for practical circuit oscillators, the now-standard approach to computing parametric sensitivities can yield incorrect results. In addition, the monodromy matrix (the matrix of state sensitivities over one oscillation period), is often defective in a way that interferes with the usual approach to computing oscillator phase noise. In this paper we analyze the HCC case, and show that by augmenting the standard sensitivity approach with explicit HCC's, one can recover the correct parametric sensitivities. In addition, we prove that there is a typically satisfied condition that guarantees that a system with HCCs will have a defective monodromy matrix. A deliberately "flawed" ring oscillator circuit and a cyanobacterial circadian clock biochemical oscillator are used to demonstrate the parametric sensitivity problem and its resolution, and to show the issue of the defective monodromy matrix.

Integrated circuit (IC) designers make use of suites of tools in order to produce designs that routinely perform as expected when manufactured. This remarkable predictability has persisted for nearly two decades, even as fabrication technology has evolved dramatically, because the transistor has remained the fundamental building block and fabrication technology has narrowly focused on making good transistors. For emerging applications of micro- and nanotechnology; such as photonics, sensing, chemical processing, biology, and medicine; there is far more technological diversity and therefore transistor-centric design tools are of limited use. The lack of tools to aid in developing manufacturable designs in emerging technologies has led to near decade long delays between prototype demonstration and available product, and the result has been a stifling of innovation.

Brute-force simulation approaches to estimating serial-link bit-error rates (BERs) become computationally intractable for the case when BERs are low and the interconnect electrical response is slow enough to generate intersymbol interference that spans dozens of bit periods. Electrical-level statistical simulation approaches based on superposing pulse responses were developed to address this problem, but such pulse-based methods have difficulty analyzing jitter and rise/fall asymmetry. In this paper we present a superposing-edge approach for statistical simulation, as edge-based methods handle rise/fall asymmetry and jitter in straightforward way. We also resolve a key problem in using edge-based approaches, that edges are always correlated, by deriving an efficient inductive approach for propagating the edge correlations. Examples are presented demonstrating the edge-based method's accuracy and effectiveness in analyzing combinations of uniform, Gaussian, and periodic distributed random jitter.

The need to determine electrostatic fields in domains bounded by molecular surfaces arises in a number of nanotechnology applications including: biomolecule design, carbon nanotube simulation, and molecular electron transport analysis. Molecular surfaces are typically smooth, without the corners common in electrical interconnect problems, but are often so geometrically complicated that numerical evaluation of the associated electrostatic fields is extremely time-consuming. In this paper we describe and demonstrate a meshless spectrally-accurate integral equation method that only requires a description of the molecular surface in the form of a collection of surface points. Our meshless method is a synthesis of techniques, suitably adapted, including: spherical harmonic surface interpolation, spectral-element-like integral equation discretization, integral desingularization via variable transformation, and matrix-implicit iterative matrix solution. The spectral accuracy of this combined method is verified using analytically solvable sphere and ellipsoid problems, and then its accuracy and efficiency is demonstrated numerically by solving capacitance and coupled Poisson/linearized Poisson-Boltzmann problems associated with a commonly used model of a molecule in solution. The results demonstrate that for a tolerance of 10 −3 this new approach reduces the number of unknowns by as much as two orders of magnitude over the more commonly used flat panel methods.

Designers of RF circuits such as power amplifiers, mixers, and filters make extensive use of simulation tools which perform periodic steady-state analysis and its extensions, but until the mid 1990s, the computational costs of these simulation tools restricted designers from simulating the behavior of complete RF subsystems. The introduction of fast matrix-implicit iterative algorithms completely changed this situation, and extensions of these fast methods are providing tools which can perform periodic, quasi-periodic, and periodic noise analysis of circuits with thousands of devices. Even though there are a number of research groups continuing to develop extensions of matrix-implicit methods, there is still no compact characterization which introduces the novice researcher to the fundamental issues. In this paper, we examine the basic periodic steady-state problem and provide both examples and linear algebra abstractions to demonstrate connections between seemingly dissimilar methods and to try to provide a more general framework for fast methods than the standard time-versus-frequency domain characterization of finite-difference, basis-collocation, and shooting methods

Electrostatic analysis of complicated molecular surfaces arises in a number of nanotechnology applications including: biomolecule design, carbon nanotube simulation, and molecular electron transport. Molecular surfaces are typically smooth, without the corners common in electrical interconnect problems, and are candidates for methods with higher order convergence than that of the commonly used flat panel methods. In this paper we describe and demonstrate a spectrally accurate approach for analyzing molecular surfaces described by a collection of surface points. The method is a synthesis of several techniques, and starts by using least squares to fit a high order spherical harmonic surface representation to the given points. Then this analytic representation is used to construct a differentiable map from the molecular suface to a cube, an orthogonal basis is generated on the rectangular cube surfaces, and a change of variables is used to desingularize the required integrals of products of basis functions and Green's function. Finally, an efficient method for solving the discretized system using a matrix-implicit scheme is described. The combined method is demonstrated on an analytically solvable sphere problem, capacitance calculation of complicated molecular surface, and a coupled Poisson/Poisson-Boltzmann problem associated with a biomolecule. The results demonstrate that for a tolerance of 10-3 this new approach requires one to two orders of magnitude fewer unknowns than a flat panel method.

This paper presents a fast boundary-element method (BEM) algorithm that is well suited for solving electrostatics problems that arise in traditional and bio-microelectromechanical systems (bio-MEMS) design. The algorithm, FFTSVD, is Green's-function-independent for low-frequency kernels and efficient for inhomogeneous problems. FFTSVD is a multiscale algorithm that decomposes the problem domain using an octree and uses sampling to calculate low-rank approximations to dominant source distributions and responses. Long-range interactions at each length scale are computed using the FFT. Computational results illustrate that the FFTSVD algorithm performs better than precorrected-FFT (pFFT)-style algorithms or the multipole-style algorithms in FastCap.

In this paper, we present a technique for automatically extracting nonlinear macromodels of biomedical microelectromechanical systems devices from physical simulation. The technique is a modification of the recently developed trajectory piecewise-linear approach, but uses ideas from balanced truncation to produce much lower order and more accurate models. The key result is a perturbation analysis of an instability problem with the reduction algorithm, and a simple modification that makes the algorithm more robust. Results are presented from examples to demonstrate dramatic improvements in reduced model accuracy and show the limitations of the method.

For a wide variety of micromachined devices, designers need accurate analysis of fluid drag forces for complicated three-dimensional (3-D) problems. This paper describes FastStokes, a recently developed 3-D fluid analysis program. FastStokes rapidly computes drag forces on complicated structures by solving an integral formulation of the Stokes equation using a precorrected fast Fourier transform (PFFT)-accelerated boundary element method (BEM). The specializations of the PFFT algorithm to the Stokes flow problem are described, and computational results are presented. Timing results are used to demonstrate that FastStokes scales almost linearly with problem complexity, can easily analyze structures as complicated as an entire comb drive in under an hour, and can produce results that accurately match measured data.

An efficient approach to full-wave impedance extraction is developed that accounts for substrate effects through the use of two-layer media Green's functions in a mixed-potential-integral-equation (MPIE) solver. Particularly, the choice of implementation for the layered media Green's functions motivates the development of accelerated techniques for both volume and surface integrations in the solver. Solver accuracy is validated against measurements taken on fabricated devices; solver efficiency is demonstrated by its 9.8X reduction in cost in comparison to the traditional integration approach.

Existing Full-wave Model Order Reduction (FMOR) approaches are based on Expanded Taylor Series Approximations (ETAS) of the oscillatory full-wave system matrix. The accuracy of such approaches hinges on the worst case interaction distances, producing accurate models over a very narrow band of frequencies. In this paper we present Segregation by Primary Phase Factors (SPPF), a novel algorithm for FMOR enabling wideband interconnect impedance analysis. SPPF extracts exponential terms (primary phase factors) and then approximates the smoother remainder with an ETAS, thus resulting in good accuracies over a very wide band of frequencies. We also present a technique to improve conditioning for the required computation. Example results are given for simple interconnect structures modeled using a discretized mixed potential integral equation formulation.

In this paper we are concerned with developing more reliable model reduction algorithms. We have focused on less common, but real, examples that fail to be effectively reduced by almost all of the currently popular model reduction methods. The failure of these popular methods is due to the fact that they all separately examine controllability and observability. We then present a new method based on several modifications and extensions of the recently developed AISIAD algorithm. The modified AISAID method is demonstrated on a wide variety of examples, including electrical interconnect, micromachined devices, and heat flow to show that the method is reliable. Our modified AISAID method is either nearly equivalent or far superior to any of the other reduction methods suitable for large scale problems.

In this paper we describe several novel sparsification techniques used in a fast stochastic integral equation solver to compute the mean value and the variance of capacitance of 3D interconnects with random surface roughness. With the combination of these numerical techniques, the computational cost has been reduced from O(N/sup 4/) to O(Nlog/sup 2/(N)), where N is the number of panels used for the discretization of nominal smooth surfaces. Numerical experiments show that the proposed numerical techniques are accurate and efficient.

In this paper, we describe the algorithms used in FastImp, a program for accurate analysis of wide-band electromagnetic effects in very complicated geometries of conductors. The program is based on a recently developed surface integral formulation and a precorrected fast Fourier transform (FFT) accelerated iterative method, but includes a new piecewise quadrature panel integration scheme, a new scaling and preconditioning technique as well as a generalized grid interpolation and projection strategy. Computational results are given on a variety of integrated circuit interconnect structures to demonstrate that FastImp is robust and can accurately analyze very complicated geometries of conductors.

The ability of micromachining, or MEMS, technology to directly manipulate micron- and nanometer-sized objects makes it an idea technology for a wide range of biological and biomedical applications, and has led to a sub field in bioMEMs design. Although BioMEMS is attracting substantial attention and research, development has been hampered by the lack of computer-aided design tools. The available tools are far behind those for integrated circuit design, and therefore successful bioMEMS designers require very sophisticated processing expertise. It is the purpose of this paper to encourage research in this rapidly evolving computer-aided design field, by providing the briefest of summaries and an extensive set of pointers to literature.

In This work we describe a stochastic integral equation method for computing the mean value and the variance of capacitance of interconnects with random surface roughness. An ensemble average Green's function is combined with a matrix Neumann expansion to compute nominal capacitance and its variance. This method avoids the time-consuming Monte Carlo simulations and the discretization of rough surfaces. Numerical experiments show that the results of the new method agree very well with Monte Carlo simulation results.

In this paper, we describe an approach for generating accurate geometrically parameterized integrated circuit interconnect models that are efficient enough for use in interconnect synthesis. The model-generation approach presented is automatic, and is based on a multiparameter moment matching model-reduction algorithm. A moment-matching theorem proof for the algorithm is derived, as well as a complexity analysis for the model-order growth. The effectiveness of the technique is tested using a capacitance extraction example, where the plate spacing is considered as the geometric parameter, and a multiline bus example, where both wire spacing and wire width are considered as geometric parameters. Experimental results demonstrate that the generated models accurately predict capacitance values for the capacitor example, and both delay and cross-talk effects over a reasonably wide range of spacing and width variation for the multiline bus example.

In this paper we propose a method for generating reduced models for a class of nonlinear dynamical systems, based on truncated balanced realization (TBR) algorithm and a recently developed trajectory piecewise-linear (TPWL) model order reduction approach. We also present a scheme which uses both Krylov-based and TBR-based projections. Computational results, obtained for examples of nonlinear circuits and a micro-electro-mechanical system (MEMS), indicate that the proposed reduction scheme generates nonlinear macromodels with superior accuracy as compared to reduction algorithms based solely on Krylov subspace projections, while maintaining a relatively low model extraction cost.

In this paper we describe the algorithms used in FastImp, a program for accurate analysis of wide-band electromagnetic effects in very complicated geometries of conductors. The program is based on a recently developed surface integral formulation and a precorrected-FFT accelerated iterative method, but includes a new scaling and preconditioning technique as well as a generalized grid interpolation and projection strategy. Computational results are given on a variety of integrated circuit interconnect structures to demonstrate that FastImp is robust and can accurately analyze very complicated geometries of conductors.

Detailed electromagnetic analysis of three-dimensional structures in multi-layered dielectric media is critical for automatic generation of equivalent circuit models for the interconnects and packages in RF or mixed signal integrated circuits. In this paper we present a new wideband surface integral formulation that can be readily combined with the well-established layered Green's function techniques. In discretizing the formulation, we have used the well-known RWG linear basis function to reduce the number of unknowns. Using a so-called loop-star basis transformation and the frequency normalization, the accuracy at low frequencies has been improved substantially. Several numerical examples are used to validate the accuracy and robustness of this new formulation.

In this paper, we present an approach to nonlinear model reduction based on representing a nonlinear system with a piecewise-linear system and then reducing each of the pieces with a Krylov projection. However, rather than approximating the individual components as piecewise linear and then composing hundreds of components to make a system with exponentially many different linear regions, we instead generate a small set of linearizations about the state trajectory which is the response to a "training input." Computational results and performance data are presented for an example of a micromachined switch and selected nonlinear circuits. These examples demonstrate that the macromodels obtained with the proposed reduction algorithm are significantly more accurate than models obtained with linear or recently developed quadratic reduction techniques. Also, we propose a procedure for a posteriori estimation of the simulation error, which may be used to determine the accuracy of the extracted trajectory piecewise-linear reduced-order models. Finally, it is shown that the proposed model order reduction technique is computationally inexpensive, and that the models can be constructed "on the fly," to accelerate simulation of the system response.

In this paper we present an improvement to the fictitious magnetic charge approach to computing inductances in the presence of permeable materials. The improvement replaces integration over a "non-piercing" surface with a line integral and an efficient quadrature scheme. Eliminating the need to generate non-piercing surfaces substantially simplifies handling problems with general geometries of permeable materials. Computational results are presented to demonstrate the accuracy and versatility of the new method.

Modeling the exponentially varying current distributions in conductor interiors associated with high frequency interconnect behavior causes a rapid increase in the computation time and memory required even by recently developed fast electromagnetic analysis programs. In this paper we describe a procedure to generate numerically a set of basis functions which efficiently represent conductor current variation, and thus improving solver efficiency. The method is based on solving a sequence of template problems, and is easily generalized to arbitrary conductor cross-sections. Results are presented to demonstrate that the numerically computed basis functions are seven to twenty times more efficient than the commonly used piece-wise constant basis functions.

Computer simulation is an important tool for improving our understanding of biomolecule electrostatics, in part to aid in drug design. However, the numerical techniques used in these simulation tools do not exploit fast solver approaches widely used in analyzing integrated circuit interconnects. In this paper we describe one popular formulation used to analyze biomolecule electrostatics, present an integral formulation of the problem, and apply the precorrected-FFT method to accelerate the solution of the integral equations.

In this paper we present a fast and efficient program for extraction of the frequency dependent inductance of structures with permeable materials. The program, FastMag, uses a magnetic surface charge formulation, efficient techniques for evaluating the required integrals, and a preconditioned GMRES method to solve the resulting linear system. Results from examples are presented to demonstrate the accuracy and versatility of the FastMag program.

In this paper we describe an approach for generating geometrically-parameterized integrated-circuit interconnect models that are efficient enough for use in interconnect synthesis. The model generation approach presented is automatic, and is based on a multi-parameter model-reduction algorithm. The effectiveness of the technique is tested using a multi-line bus example, where both wire spacing and wire width are considered as geometric parameters. Experimental results demonstrate that the generated models accurately predict both delay and cross-talk effects over a wide range of spacing and width variation.

With process technology and functional integration advancing steadily, chips are continuing to grow in area while critical dimensions are shrinking. This has led to the emergence of on-chip inductance to be a factor whose effect on performance and on signal integrity has to be managed by chip designers and has to be sometimes traded off against other performance parameters. In this paper, we cover several techniques to reduce on-chip inductance which in turn improve timing predictability and reduce signal delay and crosstalk noise. We present experimental results obtained from simulations of a typical high performance bus structure and a clock tree structure to examine the effectiveness of some of the different inductance reduction techniques.

The goal of this work was to simulate the effect of the finite conductivity of semiconductor substrates on the on-chip coupling inductance and then to investigate the effect of the on-chip coupling inductance on circuit crosstalk. In addition, the limitations of standard approaches for estimating coupling inductance are examined. A method for the reduction of the coupling inductance and its effect on circuit crosstalk is also discussed.

In this paper, we present an efficient method to model the interior of the conductors in a quasi-static or full-wave integral equation solver. We show how interconnect cross-sectional current distributions can be modeled using a small number of conduction modes as basis functions for the discretization of the Mixed Potential Integral Equation (MPIE). Two examples are presented to demonstrate the computational attractiveness of our method. In particular, we show how our new approach can successfully and efficiently capture skin effects, proximity effects and transmission line resonances.

Many physical synthesis tools interdigitate signal and power lines to reduce cross-talk, and thus, improve signal integrity and timing predictability. Such approaches are extremely effective at reducing cross-talk at circuit speeds where inductive effects are inconsequential. In this paper, we use a detailed distributed RLC model to show that inductive cross-talk effects are substantial in long busses associated with 0.18 micron technology. Simulation experiments are then used to demonstrate that cross-talk in such high speed technologies is much better controlled by re-deploying interdigitated power lines to perform differential signaling.

Interconnect structures including dielectrics can be modeled by an integral equation method using volume currents and surface charges for the conductors, and volume polarization currents and surface charges for the dielectrics. In this paper we describe a mesh analysis approach for computing the discretized currents in both the conductors and the dielectrics. We then show that this fully mesh-based formulation can be cast into a form using provably positive semidefinite matrices, making for easy application of Krylov-subspace based model-reduction schemes to generate accurate guaranteed passive reduced-order models. Several printed circuit board examples are given to demonstrate the effectiveness of the strategy.

More aggressive design practices have created renewed interest in techniques for analyzing substrate coupling problems. Most previous work has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting resistance matrix, whose number of nonzero entries grows quadratically with the number of contacts. Wavelet-like methods have been applied to sparsifying the resistance matrix representing the substrate coupling, but the accuracy of the method is very sensitive to the particulars of the contact layout. In this paper we show that for the substrate problem it is possible to improve considerably on the wavelet-like methods by making use of the algorithmic structure common to the fast multipole and wavelet-like algorithms, but making judicious use of low-rank approximations. The approach, motivated by the hierarchical SVD algorithm, can achieve more than an order of magnitude better accuracy for commensurate sparsity, or can achieve much better sparsity at commensurate accuracy, when compared to the wavelet-like algorithm.

In this paper we present an approach to the nonlinear model reduction based on representing the nonlinear system with a piecewise-linear system and then reducing each of the pieces with a Krylov projection. However, rather than approximating the individual components as piecewise-linear and then composing hundreds of components to make a system with exponentially many different linear regions, we instead generate a small set of linearizations about the state trajectory which is the response to a 'training input'. Computational results and performance data are presented for a nonlinear circuit and a micromachined fixed-fixed beam example. These examples demonstrate that the macromodels obtained with the proposed reduction algorithm are significantly more accurate than models obtained with linear or the recently developed quadratic reduction techniques. Finally, it is shown that the proposed technique is computationally inexpensive, and that the models can be constructed 'on-the-fly', to accelerate simulation of the system response.

In order for parasitic extraction of high-speed integrated circuit interconnect to be sufficiently efficient, and fit with model-order reduction techniques, a robust wideband surface integral formulation is essential. One recently developed surface integral formulation has shown promise, but was plagued with numerical difficulties of poorly understood origin. We show that one of that formulation's difficulties was related to the inaccuracy in the approach to evaluate integrals over discretization panels, and we present an accurate approach based on an adapted piecewise quadrature scheme. We also show that the condition number of the original system of integral equations can be reduced by differentiating one of the integral equations. Computational results on a ring and a spiral inductor are used to show that the new quadrature scheme and the differentiated integral formulation improve accuracy and accelerate the convergence of iterative solution methods.

This paper introduces a new integral formulation to calculate charge densities of conductor systems that may include multiple dielectric materials. We show that the conditioning of our formulation is much better than that of the standard equivalent charge formulation. When combined with a nonstandard discretization scheme, results can be obtained with higher accuracy at reduced numerical cost. We present a multipole accelerated implementation of our formulation. The results demonstrate that the new approach can cut the iteration count by a factor between two and four. Moreover, we will demonstrate that in the presence of sparsification errors and multiple dielectric materials second-kind formulations are much more accurate than the standard first-kind formulations.

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 presen t a rank-one update method for updating reduced-order models of interconnect parasitics when driv e resistances or load capacitances change, as commonly occurs during timing analysis. These rank-one updates are extremely inexpensive, do not require reexamining the original in terconnect netw ork, and most importantly are provably equivalent to rereducing the original netw ork. This abstract con tains the proof only for the case of varying the driver resistance, but examples are given to show that the exactness holds more generally. In particular, a cross-talk case is examined where the conductance matrix is singular.

In this survey paper, we describe and contrast three different approaches for extending circuit simulation to include micromachined devices. The most commonly used method, that of using physical insight to develop parameterized macromodels, is presented first. The issues associated with fitting the parameters to simulation data while incorporating design attribute dependencies are considered. The numerical model order reduction approach to macromodeling is presented second, and some of the issues associated with fast solvers and model reduction are summarized. Lastly, we describe the recently developed circuit-based approach for simulating micromachined devices, and describe the design hierarchy and the use of a catalog of parts.

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.

Article Interconnect analysis: from 3-D structures to circuit models Share on Authors: M. Kamon Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , N. Marques Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , Y. Massoud Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , L. Silveira Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , J. White Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 910–914https://doi.org/10.1145/309847.310097Online:01 June 1999Publication History 8citation278DownloadsMetricsTotal Citations8Total Downloads278Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper we present a new algorithm for computing reduced-order models of interconnect which utilizes the dominant controllable subspace of the system.The dominant controllable modes are computed via a new iterative Lyapunov equation solver, Vector ADI.This new algorithm is as inexpensive as Krylov subspace-based moment matching methods, and often produces a better approximation over a wide frequency range.A spiral inductor and a transmission line example show this new method can be much more accurate than moment matching via Arnoldi.

Matrix-implicit Krylov-subspace methods have made it possible to efficiently compute the periodic steady-state of large circuits using either the time-domain shooting-Newton method or the frequencydomain harmonic balance method. However, the harmonic balance methods are not so efficient at computing steady-state solutions with rapid transitions, and the low-order integration methods typically used with shooting-Newton methods are not so efficient when high accuracy is required. In this paper we describe a Time-Mapped Harmonic Balance method (TMHB), a fast Krylovsubspace spectral method that overcomes the inefficiency of standard harmonic balance in the case of rapid transitions. TMHB features a non-uniform grid to resolve the sharp features in the signals. Results on several examples demonstrate that the TMHB method achieves several orders of magnitude improvement in accuracy compared to the standard harmonic balance method. The TMHB method is also several times faster than the standard harmonic balance method in reaching identical solution accuracy. 1

The many levels of metal used in aggressive deep submicron pro-cess technologies has made fast and accurate capacitance extrac-tion of complicated 3-D geometries of conductors essential, and many novel approaches have been recently developed. In this paper we present an accelerated boundary-element method, like the well-known FASTCAP program, but instead of using an adaptive fast multipole algorithm we use a numerically generated multiscale ba-sis for constructing a sparse representation of the dense boundary-element matrix. Results are presented to demonstrate that the mul-tiscale method can be applied to complicated geometries, generates a sparser boundary-element matrix than the adaptive fast multipole method, and provides an inexpensive but effective preconditioner. Examples are used to show that the better sparsification and the ef-fective preconditioner yield a method that can be 25 times faster than FASTCAP while still maintain accuracy in the smallest cou-pling capacitances. 1

Krylov-subspace based methods for generating low-order models of complicated interconnect are extremely effective, but there is no optimality theory for the resulting models. Alternatively, methods based on truncating a balanced realization (TBR), in which the observability and controllability gramians have been diagonalized, do have an optimality property but are too computationally expensive to use on complicated problems. In this paper we present a method for computing reduced-order models of interconnect by projection via the orthogonalized union of the approximate dominant eigenspaces of the system's controllability and observability gramians. The approximate dominant eigenspaces are obtained efficiently using an iterative Lyapunov equation solver, Vector ADI, which requires only linear matrix-vector solves. A spiral inductor and a transmission line example are used to demonstrate that the new method accurately approximates the TBR results and gives much more accurate wideband models than Krylov subspace-based moment matching methods.

A new surface integral formulation and discretization approach for computing electromagnetoquasistatic impedance of general conductors is described. The key advantages of the formulation is that it avoids volume discretization of the conductors and the substrate, and a single discretization is accurate over the entire frequency range. Computational results from an on-chip inductor, a connector and a transmission line are used to show that the formulation is accurate and is "acceleration" ready. That is, the results demonstrate that an efficiently computed preconditioner insures rapid iterative method convergence and tests with projection show the required kernels can be approximated easily using a coarse grid.

The extraction of substrate coupling resistances can be formulated as a first-kind integral equation, which requires only discretization of the two-dimensional contacts. However, the result is a dense matrix problem which is too expensive to store or to factor directly. Instead, we present a novel, multigrid iterative method which converges more rapidly than previously applied Krylov-subspace methods. At each level in the multigrid hierarchy, we avoid dense matrix-vector multiplication by using moment-matching approximations and a sparsification algorithm based on eigendecomposition. Results on realistic examples demonstrate that the combined approach is up to an order of magnitude faster than a Krylov-subspace method with sparsification, and orders of magnitude faster than not using sparsification at all.

As VLSI circuit speeds have increased, reliable chip and system design can no longer be performed without accurate three-dimensional interconnect models. In this paper, we describe an integral equation aproach to modeling the impedance of inter-connect structures accounting for both the charge accumulation on the surface of conductors and the current traveling in their interior: Our formulation, based on a combination of nodal and mesh analysis, has the required properties to be combined with Model Order Reduction techniques to generate accurate and guaranteed passive low order Interconnect models for efficient inclusion in standard circuit simulators. Furthermore, the formulation is shown to be more flexible and efficient than previously reported methods.

Because magnetic effects have a much longer spatial range than electrostatic effects, an interconnect line with large inductance will be sensitive to distant variations in interconnect topology. This long range sensitivity makes it difficult to balance delays in nets like clock trees, so for such nets inductance must be minimized. In this paper we use two- and three-dimensional electromagnetic field solvers to compare dedicated ground planes to a less area-consuming approach, interdigitating the signal line with ground lines. The surprising conclusion is that with very little area penalty, interdigitated ground lines are more effective at minimizing self-inductance than ground planes.

As VLSI circuit speeds have increased, the need for accurate three-dimensional interconnect models has become essential to accurate chip and system design. In this paper we describe an integral equation approach to modeling the impedance of interconnect structures accounting for both the charge accumulation on the surface of conductors and the current traveling along conductors. Unlike previous methods, our approach is based on a modified nodal analysis formulation and can be used directly to generate guaranteed passive low order interconnect models for efficient inclusion in a standard circuit simulator.

In this paper we describe a computationally efficient approach to generating reduced-order models from PEEC-based three-dimensional electromagnetic analysis programs. It is shown that a recycled multipole-accelerated approach applied to recent model order reduction techniques requires nearly two orders of magnitude fewer floating point operations than direct techniques thus allowing the analysis of larger, more complex three-dimensional geometries.

Accurately accounting for three-dimensional (3-D) geometry and distributed RC effects in on-chip interconnect is important for predicting crosstalk in memory cells, analog circuits, and regions of congested routing in digital circuits. In this paper we describe a multipole-accelerated, mixed surface-volume formulation, and a preconditioned model-order reduction algorithm for distributed RC, or electroquasistatic, simulation of 3-D integrated circuit interconnect. The difficulties arising from the ill conditioning inherent in the dynamic problem is effectively resolved by a combined surface-volume approach. Results are presented to demonstrate that the computational cost for extracting a complete reduced-order model is order N, where N is the number of surface unknowns. Finally, the multipole-accelerated code is used to investigate the accuracy of the one-dimensional diffusion equation for long RC lines.

We address the problem of estimating the average switching activity of combinational circuits under random input sequences. Switching activity is strongly affected by gate delays, and for this reason we use a variable delay model in estimating switching activity. Unlike most probabilistic methods that estimate switching activity, our method takes into account correlation caused at internal gates in the circuit due to reconvergence of input signals. This method assumes a particular delay model and further assumes that the primary inputs to the combinational circuit are uncorrelated. Both these assumptions can be relaxed at the cost of increased complexity. We describe extensions to handle transmission gates and inertial delays in this paper.

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.

Article Free Access Share on Multipole accelerated capacitance calculation for structures with multiple dielectrics with high permittivity ratios Authors: Johannes Tausch MIT Department of EECS, Cambridge, MA MIT Department of EECS, Cambridge, MAView Profile , Jacob White MIT Department of EECS, Cambridge, MA MIT Department of EECS, Cambridge, MAView Profile Authors Info & Claims DAC '96: Proceedings of the 33rd annual Design Automation ConferenceJune 1996 Pages 367–370https://doi.org/10.1145/240518.240588Published:01 June 1996Publication History 3citation230DownloadsMetricsTotal Citations3Total Downloads230Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we present a preconditioned recycled Krylov-subspace method to accelerate a recently developed approach for AC and noise analysis of linear periodically-varying communication circuits. Examples are given to show that the combined method can be used to analyze switching filter frequency response, mixer 1/f noise frequency translation, and amplifier intermodulation distortion. In addition, it is shown that for large circuits the pre-conditioned recycled Krylov-subspace method is up to forty times faster than the standard optimized direct methods.

Pade approximation is an often-used method for reducing the order of a finite-dimensional, linear, time invariant, signal model. It is known to suffer from two problems: numerical instability during the computation of the Pade coefficients and lack of guaranteed stability for the resulting reduced model even when the original system is stable. We show how the numerical instability problem can be avoided using the Arnoldi algorithm applied to an appropriately chosen Krylov subspace. Moreover, we give an easily computable sufficient condition on the system matrix that guarantees the stability of the reduced model at any approximation order.

Since the first papers on asymptotic waveform evaluation (AWE), Pade-based reduced order models have become standard for improving coupled circuit-interconnect simulation efficiency. Such models can be accurately computed using bi-orthogonalization algorithms like Pade via Lanczos (PVL), but the resulting Pade approximates can still be unstable even when generated from stable RLC circuits. For certain classes of RC circuits it has been shown that congruence transforms, like the Arnoldi algorithm, can generate guaranteed stable and passive reduced-order models. In this paper we present a computationally efficient model-order reduction technique, the coordinate-transformed Arnoldi algorithm, and show that this method generates arbitrarily accurate and guaranteed stable reduced-order models for RLC circuits. Examples are presented which demonstrates the enhanced stability and efficiency of the new method.

Simulating transients in semiconductor devices involves numerically solving the time-dependent drift-diffusion equations, usually in two or three space dimensions. Because of the computation cost of these simulations, methods that perform careful domain decomposition so as to exploit parallel processing have received much recent attention. In this paper, we describe using accelerated waveform relaxation (WR) to perform parallel device transient simulation using both clusters of workstations and the IBM SP-2. The accelerated WR algorithms are compared to pointwise direct and iterative methods, and it is shown that the accelerated WR method is competitive on a single processor. In addition, it is shown that with a domain decomposition chosen for rapid iterative method convergence rather than parallel efficiency, the pointwise methods parallelize poorly but the WR method achieves near linear speedup (with respect to the number of processors) on the IBM SP-2.

This paper describes a Galerkin/spherical harmonics approach for solving the coupled Poisson-Boltzmann system of equations for the electron distribution function and the electric potential, which can then be used to calculate other parameters of interest such as current flow and electron temperature. The Galerkin approach described here has some pragmatic advantages in space-dependent problems over more commonly used term-matching techniques for arbitrary order spherical harmonic expansions in momentum space, but the method requires a careful treatment of the boundary conditions and upwinded discretization methods. Results are presented for nonuniformly doped one-dimensional devices using up to third order spherical harmonics to show the importance of including higher order harmonics to accurately calculate the distribution function in high field regions.

It has recently been shown that the boundaryelement method can be used to perform accurate cross-talk simulations of three-dimensional integrated circuit interconnect. However, the computational complexity grows as , where is the number of surface unknowns. Straightforward application of the fast-multipole algorithm reduces the computational complexity to order , but produces magnified errors due to the ill-conditioning of the steady-state problem. We present a mixed surface-volume approach and prove that the formulation results in the exact steadystate solution, independent of the multipole approximations. Numerical experiments are presented to demonstrate the accuracy and efficiency of this technique. On a realistic example, the new method runs fifteen times faster than using dense-matrix iterative methods.

Since the rst papers on asymptotic waveform evaluation (AWE), reduced order models have become standard for improving interconnect simulation eciency, and very recent w ork has demonstrated that bi-orthogonalization algorithms can be used to robustly generate AWE-style macromodels.In this paper we describe using block Arnoldi-based orthogonalization methods to generate reduced order models from FastHenry, a m ultipole-accelerated three dimensional inductance extraction program.Examples are analyzed to demonstrate the eciency and accuracy of the block Arnoldi algorithm.

Gaussian-elimination based shooting-Newton methods, a commonly used approach for computing steady-state solutions, grow in computational complexity like N 3 , where N is the number of circuit equations.Just using iterative methods to solve the shooting-Newton equations results in an algorithm which is still order N 2 because of the cost of calculating the dense sensitivity matrix.Below, a matrix-free Krylov-subspace approach is presented, and the method is shown to reduce shooting-Newton computational complexity to that of ordinary transient analysis.Results from several examples are given to demonstrate that the matrix-free approach is more than ten times faster than using iterative methods alone for circuits with as few as 400 equations.2 Shooting Methods Finding the periodic steady-state solution of a circuit involves nding the initial condition for the circuit's associated system of dierential equations such that the solution at the end of the period matches the initial condition.More precisely, nding the steady-state solution means nding a particular solution to the circuit equations, as

Multipole-accelerated surface-volume methods have proved to be very efficient techniques for delay and cross-talk simulation of three-dimensional integrated circuit interconnect. However, to be efficiently combined with transistor circuitry in a SPICE-level simulation, reduced-order models which have accurate low-frequency behavior must be constructed. Asymptotic Waveform Evaluation (AWE) or Pade-via-Lanczos (PVL) algorithms can not be used directly to construct the reduced-order models from the surface-volume formulation, because the formulation generates dense matrices which are too expensive to factor. In this paper we describe a two-level approach to efficiently generating reduced-order models with accurate low frequency behavior. First, reduced-order models which match Taylor series terms at s=/spl infin/ are efficiently generated from the surface-volume formulation using an Arnoldi method, and then these fairly high-order models are used to efficiently construct lower-order models which snatch Taylor series terms at s=0. Examples are given to demonstrate the accuracy of the resultant low-order model.

In this paper we describe an algorithm for ecient circuit-level simulation of transmission lines which can be speci ed by tables of frequency-dependent scattering parameters.The approach uses a forced stable section-by-section `2 minimization approach to construct a high order rational function approximation to the frequency domain data, and then applies guaranteed stable balanced realization techniques to reduce the order of the rational function.The rational function is then incorporated in a circuit simulator using fast recursive convolution.An example of a transmission line with skin-eect is examined to both demonstrate the eectiveness of the approach and to show its generality. 31

In [1], it was shown that an equation formulation based on mesh analysis can be combined with a GMRES-style iterative matrix solution technique to make a reasonably fast 3-D frequency dependent inductance and resistance extraction algorithm. Unfortunately, both the computation time and memory required for that approach grow faster than n/sup 2/, where n is the number of volume-filaments. In this paper, we show that it is possible to use multipole-acceleration to reduce both required memory and computation time to nearly order n. Results from examples are given to demonstrate that the multipole acceleration can reduce required computation time and memory by more than an order of magnitude for realistic packaging problems.

In this paper, two approaches to self-consistent electromechanical analysis of three-dimensional micro-electro-mechanical structures are described. Both approaches combine finite-element mechanical analysis with multipole-accelerated electrostatic analysis, the first using a relaxation algorithm and the second using a surface/Newton generalized conjugate-residual scheme. Examples are given to demonstrate the relative merits of the two approaches.

In this paper we compare accelerated waveform relaxation algorithms to pointwise methods for the transient simulation of semiconductor devices on parallel machines. Experimental results are presented for simulations on small clusters of workstations and on an Intel iPSC/860. The results show that accelerated waveform methods are competitive with standard pointwise methods on serial machines, but are significantly faster on loosely-coupled MIMD machines.

This paper presents the algorithms for CMVSIM, a program for performing the transient simulation of grid based analog signal processors on a massively parallel computer. A grid-based equation formulation approach and a block-diagonal preconditioned CGS algorithm are described, and it is shown how they are used to efficiently perform transient simulation using the massively parallel Connection Machine. Experimental results using CMVSIM to simulate realistic image processing circuits are given to demonstrate that the algorithms presented are effective for a general class of grid-based signal processors. In particular, the results presented demonstrate that CMVSIM: running on a full-size Connection Machine can be as much as 650 times faster than what is, to the authors' knowledge, the fastest serial transient simulation algorithm running on a SUN-4/490 workstation.>

The authors develop a robust and efficient numerical solution of the hydrodynamic model, which solves the energy balance equation, and compare predictions of this model, using one set of parameters, with experimental nMOSFET characteristics for a range of channel lengths down to ultrashort channels. The substrate current is calculated by direct integration of the energy distribution function, which uses the computed temperature to obtain the number of high energy electrons. The drain current calculated using this method is accurate for a range of channel lengths and biases, and correctly predicts the observed enhanced transconductance for ultrashort-channel devices. The substrate current matches the experimental data for a range of channel lengths and biases above threshold with one set of physically reasonable parameters.>

The combination of a mesh analysis equation formulation technique with a preconditioned GMRES matrix solution algorithm to accelerate the determination of inductances of complex three-dimensional structures is described. Addition of the preconditioner to GMRES can reduce the cost of solution to m/sup 2/ operations compared to m/sup 2/ for direct inversion. Results from FASTHENRY, a 3-D inductance extraction program, demonstrate that the iterative approach can accelerate solution times by more than an order of magnitude.>

It is shown that a simplified model of power dissipation relates maximizing dissipation to maximizing gate output activity, appropriately weighted to account for differing load capacitances. To find the input or input sequence that minimizes the weighted activity, algorithms are given for transforming the problem to a weighted max-satisfiability problem, and exact and approximate algorithms for solving weighted max-satisfiability are presented. Algorithms for constructing the max-satisfiability problem for both dynamic and static CMOS, where for the latter dissipation caused by glitching is considered, are presented. The authors present efficient exact and approximate methods for solving weighted max-satisfiability and show that these methods are viable for large-scale problems through examination of experimental results.>

The stability and accuracy properties of exponentially fit integration algorithms applied to the test problem x=-Ax are compared with the more standard backward-Euler and semi-implicit methods. For the analysis, A in IR/sup n*n/ is assumed to be connectedly diagonally dominant with positive diagonals, as this models the equations resulting from the way MOS transistors and interconnect parasitics are treated in circuit-level timing simulation programs. Examples are used to demonstrate that all the exponential-fitting methods, and the semi-implicit methods, are much less accurate than backward-Euler for tightly coupled stiff problems, and an example is given which destabilizes one of the exponential-fitting methods. It is then proved that in the limit of large time steps, the more stable exponential-fitting methods become equivalent to a semi-implicit algorithm. It is shown that the backward-Euler, semi-implicit, and certain exponentially fit algorithms are multirate A-stable.>

A conjugate-direction based acceleration to the waveform relaxation (WR) algorithm is derived. Experimental results demonstrated the effectiveness of the acceleration when solving the large, sparsely connected algebraic and differential system generated by standard spatial discretization of the 2D time-dependent semiconductor device equations. The waveform conjugate-direction methods were up to 15 times faster than ordinary WR.>

A modified envelope-following method for simulation of clocked analog circuits is described. The modification makes the envelope-following algorithm more efficient, as unnecessary numerical integration is avoided when computing the envelope of 'quasi-algebraic' components in the solution vector. An automatic method for determining the quasi-algebraic solution components is described, and experimental results are given which demonstrate that this modified method reduces the number of computer clock cycles needed to accurately determine the envelope.>

Several improvements to the multipole-accelerated 3-D capacitance extraction program previously described are presented. A new adaptive multipole algorithm is given, and a preconditioning strategy for accelerated iterative method convergence is described. Results using these algorithms to compute the capacitance of general three-dimensional structures are presented, and they demonstrate that the modified approach is nearly as accurate as the more standard direct factorization algorithm, and can be as much as two orders of magnitude faster.>

A fast algorithm for computing the capacitance of a complicated three-dimensional geometry of ideal conductors in a uniform dielectric is described and its performance in the capacitance extractor FastCap is examined. The algorithm is an acceleration of the boundary-element technique for solving the integral equation associated with the multiconductor capacitance extraction problem. The authors present a generalized conjugate residual iterative algorithm with a multipole approximation to compute the iterates. This combination reduces the complexity so that accurate multiconductor capacitance calculations grow nearly as nm, where m is the number of conductors. Performance comparisons on integrated circuit bus crossing problems show that for problems with as few as 12 conductors the multipole accelerated boundary element method can be nearly 500 times faster than Gaussian-elimination-based algorithms, and five to ten times faster than the iterative method alone, depending on required accuracy.>

Specialized algorithms for circuit-level simulation of grid-based analog signal processing arrays on a massively parallel processor are described and implementation results presented. The trapezoidal rule is used to discretize the differential equations that describe the analog array behavior, Newton's method is used to solve the nonlinear equations generated at each time-step, and a block conjugate-gradient squared algorithm is used to solve the linear equations generated by Newton's method. Excellent parallel performance of the algorithm is achieved through the use of a novel, but very natural, mapping of the circuit data onto the massively parallel architecture. The mapping takes advantage of the underlying computer architecture and the structure of the analog array problem. Experimental results demonstrate that a full-size Connection Machine can provide a 1400 times speedup over a SUN-4/280 workstation.>

A new relaxation algorithm for circuit simulation that combines the advantages of iterated timing analysis (ITA) and waveform relaxation (WR) is described. The method is based on using an iterative stepsize refinement strategy with a waveform-relaxation-newton (WRN) algorithm. All three relaxation techniques, ITA, WR, and WRN, are compared, and experimental results that indicate the strengths and weaknesses of the methods are presented. In addition, a new convergence proof for the waveform-Newton (WN) method for systems with nonlinear capacitors is provided. Finally, it is shown that the step-refined WRN algorithm can be implemented on a parallel processor in such a way that different subsystems can be processed in parallel and the solution at different timepoints of the same subsystem can also be computed in parallel.>

The authors present experimental results demonstrating the effectiveness of waveform relaxation (WR) for solving the large, sparsely connected algebraic and differential system generated by standard spatial discretization of the two-dimensional time-dependent semiconductor device equation. The experiments demonstrate that WR converges in a uniform manner, and that there is typically some multirate behavior in a device that the WR algorithm can exploit. Speed and accuracy comparisons are made between standard direct methods, red/black Gauss-Seidel WR, and red/black overrelaxed WR. For their experiments, calculated terminal currents matched well between the methods, and overrelaxed WR was up to a factor of 3 faster than direct methods.>

The transient behavior of circuits like switching power converters and switched capacitor filters are expensive to simulate because they are clocked at a frequency whose period is orders of magnitude smaller than the time interval of interest to the designer. It is possible to reduce the simulation time without compromising accuracy by exploiting the fact that the behavior of such a circuit in a given high-frequency clock cycle is similar, but not identical, to its behavior in the preceding and following cycles. In particular, the envelope of the high-frequency clock can be followed by accurately computing the circuit behavior over occasional cycles. The authors describe the implementation of an envelope-following method that is particularly efficient for switching power and filter circuits, and they present results demonstrating the method's effectiveness.>

A variable-band relaxation algorithm for solving large linear systems is developed as an alternative to Gauss-Jacobi relaxation. This algorithm seeks to improve the reliability of Gauss-Jacobi relaxation by extracting a variable-sized band from the matrix and solving that band directly. This leads to a relaxation algorithm with provably better convergence properties. The algorithm can be used effectively on a massively parallel computer because band matrices can be solved in log(n) time on n/2 processors. Test results are presented which compare the convergence properties of variable-band and Gauss-Jacobi relaxation.>