This work presents an analytical approach for analyzing electromigration (EM) in modern technologies that use copper dual damascene (Cu DD) interconnects. In these technologies, due to design rule and methodology constraints, wires are typically laid out unidirectionally in each metal layer; since EM in Cu DD interconnects do not cross layer boundaries, the problem reduces to one of analyzing EM in multisegment interconnect lines. In contrast with traditional empirical methodologies, our approach is based on physics-based modeling, directly solving the differential equations that model EM-induced stress. This article places a focus on interconnect lines, for reasons described above, and introduces the new concept of boundary reflections of stress flux that ascribes a physical (wave-like) analogy to the transient stress behavior in a finite multisegment line. This framework is used to derive analytical expressions of transient EM stress for lines with any number of segments, which can also be tailored to include the appropriate number of terms for any desired level of accuracy. The approach is applied to both the nucleation phase and the postvoiding phase on large power grid benchmarks. These experiments demonstrate excellent accuracy as compared to accurate numerical solution, as well as linear complexity with the number of segments for evaluating stress at a specified point and time.

Multiple Input Switching (MIS) effects commonly induce undesired glitch pulses at the output of CMOS gates, potentially leading to circuit malfunction and significant power consumption. Thus, accurate and efficient glitch modeling is crucial for the design of high-performance, low-power, and reliable ICs. In this work, we present a new gate-level approach for modeling glitch effects under MIS. Unlike previous studies, we leverage efficient Machine Learning (ML) techniques to accurately estimate the glitch shape characteristics, propagation delay, and power consumption. To this end, we evaluate various ML engines and explore different Artificial Neural Network (ANN) architectures. Moreover, we introduce a seamless workflow to integrate our ANNs into existing standard cell libraries, striking an optimal balance between model size and accuracy in gate-level glitch modeling. Experimental evaluation on gates implemented in 7 nm FinFET technology demonstrates that the proposed models achieve an average error of 2.19% against SPICE simulation while maintaining a minimal memory footprint.

As semiconductor manufacturing technologies progress beyond the current 3nm, the demand for more compact and powerful VLSI circuits obliges on-chip power grid networks to become denser, resulting in a substantial increase in current densities. Consequently, Electromigration (EM) has emerged as a critical reliability concern since it can lead to voids on the metal wires and, consequently, large IR drops. In this paper, we present an EM/IR-aware wire sizing methodology based on the Particle Swarm Optimization (PSO) algorithm. Our methodology can be effectively applied to contemporary power grid networks to achieve the targeted lifetimes of the chip, and simultaneously resize the wires for area reduction. The advantage is that the proposed approach is able to deal with high-dimensional search spaces, which is imperative in our problem. Experimental results using the large-scale industrial IBM power grid benchmarks indicate that our new approach can increase the lifespan of the power grid up to 6.47 × while effectively reducing the area up to 65%.

As integrated circuit technologies are moving to smaller technology nodes, Electromigration (EM) has become one of the most challenging problems facing the EDA industry. While numerical approaches have been widely deployed since they can handle complicated interconnect structures, they tend to be much slower than analytical approaches. In this paper, we present a fast semi-analytical approach, based on the matrix exponential, for the solution of Korhonen's stress equation at discrete spatial points of interconnect trees, which enables the analytical calculation of EM stress at any time and point independently. The proposed approach is combined with the extended Krylov subspace method to accurately simulate large EM models and accelerate the calculation of the final solution. Experimental evaluation on OpenROAD benchmarks demonstrates that our method achieves 0.5% average relative error over the COMSOL industrial tool while being up to three orders of magnitude faster.

Efficient sound density simulation for room acoustic models is a challenging problem, due to the need for the solution of large-scale systems of equations that require unreasonably long computational times. However, in many cases, the measurement of sound density is not required to be computed at every point of the entire room but only at certain spots. This makes the room acoustic problem amenable to Model Order Reduction (MOR) techniques. Moment-Matching (MM) techniques are well established and can be directly applied in the resulting sound diffusion equation. In this paper, we propose a computationally efficient MM algorithm based on extended Krylov subspace method, that can generate very compact models in order to efficiently simulate them across many time-steps. Experimental results demonstrate a speedup up to 1016× with relative error less than 0.5%.

The analysis of transient stress buildup in on-chip interconnects due to electromigration (EM) requires the solution of partial differential equations (PDEs) with appropriate boundary conditions, but prior approaches have been computationally expensive. This paper uses a stress-electrical equivalence to map the solution of the system of PDEs for a general multisegment interconnect to an RC network. For tree structures, this system is solved in linear time in the frequency domain using model order reduction (MOR) techniques. We present two MOR approaches: one that is not guaranteed to provide a stable approximant due to the presence of the mass-conservation equation, but empirically does so for a large fraction of testcases; and another that is guaranteed-stable. To achieve a guaranteed-stable solution, the approach approximates the RC circuit in a Krylov space and captures the impact of mass conservation in the form of a mass conservation excitation. However, the latter is observed to be slightly less accurate than the first approach when it does provide a solution. The method demonstrates excellent accuracy against a commercial numerical solver, and is scalable, solving transient EM analysis problems on large power grid interconnect benchmarks.

Traditional approaches to analyzing electromigration (EM) in on-chip interconnects are largely driven by semi-empirical models. However, such methods are inexact for the typical multisegment lines that are found in modern integrated circuits. This paper overviews recent advances in analyzing EM in on-chip interconnect structures based on physics-based models that use partial differential equations, with appropriate boundary conditions, to capture the impact of electron-wind and back-stress forces within an interconnect, across multiple wire segments. Methods for both steady-state and transient analysis are presented, highlighting approaches that can solve these problems with a computation time that is linear in the number of wire segments in the interconnect.

As integrated circuit technologies move below 10 nm, Electromigration (EM) has become an issue of great concern for the longterm reliability due to the stricter performance, thermal and power requirements. The problem of EM becomes even more pronounced in power grids due to the large unidirectional currents flowing in these structures. The attention for EM analysis during the past years has been drawn to accurate physics-based models describing the interplay between the electron wind force and the back stress force, in a single Partial Differential Equation (PDE) involving wire stress. In this paper, we present a fast semi-analytical approach for the solution of the stress PDE at discrete spatial points in multi-segment lines of power grids, which allows the analytical calculation of EM stress independently at any time in these lines. Our method exploits the specific form of the discrete stress coefficient matrix whose eigenvalues and eigenvectors are known beforehand. Thus, a closed-form equation can be constructed with almost linear time complexity without the need of time discretization. This closed-form equation can be subsequently used at any given time in transient stress analysis. Our experimental results, using the industrial IBM power grid benchmarks, demonstrate that our method has excellent accuracy compared to the industrial tool COMSOL while being orders of magnitude times faster.

During the past decade, Model Order Reduction (MOR) has become key enabler for the efficient simulation of large circuit models. MOR techniques based on moment-matching are well established due to their simplicity and computational performance in the reduction process. However, moment-matching methods based on the ordinary Krylov subspace are usually inadequate to accurately approximate the original circuit behaviour. In this paper, we present a moment-matching method which is based on the extended Krylov subspace and exploits the superposition property in order to deal with many terminals. The proposed method can handle large-scale regular and singular circuits, and generate accurate and efficient reduced-order models for circuit simulation. Experimental results on industrial IBM power grid benchmarks demonstrate that our method achieves an error reduction up to 83.69% over a standard Krylov subspace technique.

Traditional methods that test for electromigration (EM) failure in multisegment interconnects, over the lifespan of an IC, are based on the use of the Blech criterion, followed by Black's equation. Such methods analyze each segment independently, but are well known to be inaccurate due to stress buildup over multiple segments. This paper introduces the new concept of boundary reflections of stress flow that ascribes a physical (wave-like) interpretation to the transient stress behavior in a finite multisegment line. This can provide a framework for deriving analytical expressions of transient EM stress for lines with any number of segments, which can also be tailored to include the appropriate number of terms for any desired level of accuracy. The proposed method is shown to have excellent accuracy, through evaluations against the FEM solver COMSOL, as well as scalability, through its application on large power grid benchmarks.

The integration of more components into modern integrated circuits (ICs) has led to very large RLC parasitic networks consisting of millions of nodes that have to be simulated in many times or frequencies to verify the proper operation of the chip. Model order reduction (MOR) techniques have been employed routinely to substitute the large-scale parasitic model with a model of lower order with a similar response at the input-output ports. However, established MOR techniques generally result in dense system matrices that render their simulation impractical. To this end, in this article, we propose a methodology for the sparsification of the dense circuit matrices resulting from MOR of general RLC circuits, which employs a sequence of algorithms based on the computation of the nearest diagonally dominant matrix and the sparsification of the corresponding graph. In addition, we describe a procedure for synthesizing the sparsified reduced-order model into an RLC circuit with only positive elements. Experimental results indicate that a high sparsity ratio of the reduced system matrices can be achieved with very small loss of accuracy.

As process geometries shrink below 45 nm, accurate and efficient gate-level timing analysis becomes even more challenging. Modern VLSI interconnects are more resistive, signals no longer resemble saturated ramps, and gate input pins exhibit a significant Miller effect. Over recent years, the semiconductor industry has adopted current source models (CSMs) for accurate gate modeling. Industrial gate models, however, are precharacterized assuming capacitive loads, which poses significant challenges to the approximation of the highly resistive load interconnect with an effective capacitance ( Ceff). In fact, most related works are either computationally expensive or unable to approximate the output slew. Furthermore, they require additional precharacterization and ignore the Miller effect. In this article, we present an iterative methodology for fast and accurate gate delay estimation. The proposed approach accurately computes the driver output waveform, using closed-form formulas to calculate a Ceffper waveform segment, while accounting for their interdependence. Thus, it allows for variable analysis resolution exploiting an accuracy/runtime tradeoff. In contrast to prior works, our approach is compatible with conventional CSMs and considers the impact of Miller capacitance. We evaluate our method on representative driver-load test circuits consisting of interconnects with arbitrary RC characteristics and ASU ASAP 7-nm standard cells. The proposed method achieves 1.3% and 2.5% delay and slew root-mean-square percentage error (RMSPE) against SPICE, respectively. In addition, it provides high efficiency, as it converges in 2.3 iterations on average.

During the past decade, model order reduction (MOR) has become key enabler for the efficient simulation of large circuit models. MOR techniques based on balanced truncation (BT) offer very good error estimates and can provide compact models with any desired accuracy over the whole range of frequencies (from dc to infinity). However, in most applications the circuit is only intended to operate at specific frequency windows, which means that the reduced-order model can become unnecessarily large to achieve approximation over all frequencies. In this article, we present a frequency-limited approach which, combined with an efficient low-rank sparse implementation of the extended Krylov subspace (EKS) method, can handle large input models and provably leads to reduced-order models that are either smaller or exhibit better accuracy than full-frequency BT.

The integration of more components into ICs due to the ever increasing technology scaling has led to very large parasitic networks consisting of million of nodes, which have to be simulated in many times or frequencies to verify the proper operation of the chip. Model Order Reduction techniques have been employed routinely to substitute the large scale parasitic model by a model of lower order with similar response at the input/output ports. However, all established MOR techniques result in dense system matrices that render their simulation impractical. To this end, in this paper we propose a methodology for the sparsification of the dense circuit matrices resulting from Model Order Reduction, which employs a sequence of algorithms based on the computation of the nearest diagonally dominant matrix and the sparsification of the corresponding graph. Experimental results indicate that a high sparsity ratio of the reduced system matrices can be achieved with very small loss of accuracy.

The integration of more components into modern Systems-on-Chip (SoCs) has led to very large RLC parasitic networks consisting of million of nodes, which have to be simulated in many times or frequencies to verify the proper operation of the chip. Model Order Reduction techniques have been employed routinely to substitute the large scale parasitic model by a model of lower order with similar response at the input/output ports. However, all established MOR techniques result in dense system matrices that render their simulation impractical. To this end, in this paper we propose a methodology for the sparsification of the dense circuit matrices resulting from Model Order Reduction of general RLC circuits, which employs a sequence of algorithms based on the computation of the nearest diagonally dominant matrix and the sparsification of the corresponding graph. Experimental results indicate that a high sparsity ratio of the reduced system matrices can be achieved with very small loss of accuracy.

The verification of integrated Circuits (ICs) in deep submicron technologies requires that all mutual inductive effects are taken into account to properly validate the performance and reliable operation of the chip. However, the inclusion of all mutual inductive couplings results in a fully dense inductance matrix that renders the circuit simulation computationally prohibitive. In this paper, we present efficient techniques for the solution of the linear systems arising in transient analysis of large mutually inductive circuits. These techniques involve the compression of the dense inductance matrix block by low-rank products in hierarchical matrix format, as well as the development of a Schur-complement preconditioner for the iterative solution of the transient linear system (which comprises sparse blocks alongside the dense inductance block). Experimental results indicate that substantial compression rates of the inductance matrix can be achieved without compromising accuracy, along with considerable reduction in iteration counts and execution time of iterative solution methods.

Manufacturing process variation in sub-20nm processes has introduced ever increasing overhead in Static Timing Analysis (STA) in order to guarantee the reliable operation of the circuit. Chip designers apply corner-based analysis and add guard-bands to design parameters in order to take into account the impact of process variation on timing. However, the aforementioned techniques are either too slow as the number of design parameters proliferates with the integration of more components into a chip or inaccurate due to the assumption that the worst case delay resides at the corners of design parameters. In this paper, we present a novel statistical methodology, which relies on Extreme Value Theory (EVT), to estimate the worst case delay of VLSI circuits under variations in gate/interconnect parameters. Despite the previous statistical approaches toward maximum delay estimation, our methodology can be applied regardless of the underlying gate/interconnect delay model or any assumption about the distribution of the Arrival Time (AT) at every circuit node, making it very appealing for integration to any level of timing analysis abstraction (from spice-to-gate level) and provide fast yet accurate results. Experimental results on ISCAS85/ISCAS89 circuits show that the estimated maximum AT at the Primary Outputs (POs) can be within 5% of the true maximum AT, at the cost of a few thousand Monte Carlo simulations.

Efficient analysis of on-chip power delivery networks is one of the most challenging problems facing the electronic design automation industry today. The fast dc and transient simulation of power grids is necessary to determine the proper operation of the integrated circuits at the design phase, but is made very difficult by the sheer size of modern power grids, reaching quite a few million nodes in nanometer-scale integrated circuits. This paper presents two efficient and highly parallel preconditioning mechanisms for the analysis of large-scale power grids of near-2-D structure (with small via resistances) or 3-D structure (with large via resistances) by iterative solution methods. The proposed preconditioners approximate the matrices of practical power grids well enough to ensure fast convergence of the iterative method, while their application within the core of the method is based on a fast transform solver which makes use of a series of independent fast Fourier transforms. Apart from the near-optimal operation complexity, the main characteristics of a fast transform solver are the large degree of multilevel parallelism and low memory requirements, which enable harnessing the computational resources of massively parallel architectures like graphics processing units (GPUs). Experimental evaluation of the proposed methodology on a set of large-scale industrial benchmarks demonstrates nearly two orders of magnitude speedup and reduction in memory footprint over parallel implementations of state-of-the-art direct and iterative methods, when GPUs are utilized.

The inverse of the inductance matrix (reluctance matrix) is amenable to sparsification to a much greater extent than the inductance matrix itself. However, the inversion and subsequent truncation of a large dense inductance matrix to obtain the sparse inverse is very time-consuming, and previously proposed window-based techniques cannot provide adequate accuracy. In this paper we propose a method for selective inversion of the inductance matrix to a prescribed sparsity ratio, which is also amenable to parallelization on modern architectures. Experimental results demonstrate its potential to provide efficient and accurate approximation of the reluctance matrix for simulation of large-scale RLC circuits.

This paper introduces a novel approach towards the statistical analysis of modern high-speed I/O and similar communication links, which is capable of reliably to determine extremely low (∼10−12or lower) bit error rates (BER) by using techniques from extreme value theory (EVT). The new method requires only a small amount of voltage values at the received eye center, which can be generated by running circuit/system level simulations or measuring fabricated I/O circuits, to predict link BERs. Unlike conventional techniques, no simplifying assumptions on link noise and interference sources are required making this approach extremely portable to any communication system operating with very low BER. Our experimental results show that the BER estimates from the proposed methodology are on the same order of magnitude as traditional time domain, transient eye diagram simulations for links with BER of 10−6and 10−5operating at 9.6 and 10.1 Gbps respectively.

Efficient analysis of massive on-chip power delivery networks is among the most challenging problems facing the EDA industry today. Due to Joule heating effect and the temperature dependence of resistivity, temperature is one of the most important factors that affect IR drop and must be taken into account in power grid analysis. However, the sheer size of modern power delivery networks (comprising several thousands or millions of nodes) usually forces designers to neglect thermal effects during IR drop analysis in order to simplify and accelerate simulation. As a result, the absence of accurate estimates of Joule heating effect on IR drop analysis introduces significant uncertainty in the evaluation of circuit functionality. This work presents a new approach for fast electrical-thermal co-simulation of large-scale power grids found in contemporary nanometer-scale ICs. A state-of-the-art iterative method is combined with an efficient and extremely parallel preconditioning mechanism, which enables harnessing the computational resources of massively parallel architectures, such as graphics processing units (GPUs). Experimental results demonstrate that the proposed method achieves a speedup of 66.1X for a 3.1M-node design over a state-of-the-art direct method and a speedup of 22.2X for a 20.9M-node design over a state-of-the-art iterative method when GPUs are utilized.

Efficient analysis of massive on-chip power delivery networks is among the most challenging problems facing the EDA industry today. In this paper, we present a new preconditioned iterative method for fast DC and transient simulation of large-scale power grids found in contemporary nanometer-scale ICs. The emphasis is placed on the preconditioner which reduces the number of iterations by a factor of 5X for a 2.6M-node industrial design and by 72.6X for a 6.2M-node synthetic benchmark, compared with incomplete factorization preconditioners. Moreover, owing to the preconditioner's special structure that allows utilizing a Fast Transform solver, the preconditioning system can be solved in a near-optimal number of operations, while it is extremely amenable to parallel computation on massively parallel architectures like graphics processing units (GPUs). Experimental results demonstrate that our method achieves a speed-up of 214.3X and 138.7X for a 2.6M-node industrial design, and a speed-up of 1610.5X and 438X for a 3.1M-node synthetic design, over state-of-the-art direct and iterative solvers respectively when GPUs are utilized. At the same time, its matrix-less formulation allows for reducing the memory footprint by up to 33% compared to the memory requirements of the best available iterative solver.

Validating the robustness of power distribution in modern IC design is a crucial but very difficult problem, due to the vast number of possible working modes and the high operating frequencies which necessitate the modeling of power grid as a general RLC network. In this paper we provide a characterization of the worst-case current waveform excitations that produce the maximum voltage drop among all possible working modes of the IC. In addition, we give a practical methodology to estimate these worst-case excitations on the basis of a sample of the excitation space acquired via plain circuit simulation. In the course of characterizing the worst-case excitations we also establish that the voltage drop function for RLC grid models has nonnegative coefficients, which has been an open problem so far.

Accurate simulation of digital circuits is an essential part of the design process. High precision models are generally used to confirm logic behavior and estimate power dissipation, which has become an extremely important design parameter. Unfortunately high precision analysis is expensive in computer execution time, and there is always a trade-off between accuracy and speed. This work proposes a new circuit simulation approach by storing a set of pre-characterized transition configurations for each standard library cell in a lookup table. The lookup table contains information about the voltage and the current transient waveform produced by SPICE simulation. The method achieves good accuracy levels for yielding the total or partial current waveform of a circuit in significantly less time compared to SPICE or other commercial tools.

Identifying worst-case voltage drop conditions in every module supplied by the power grid is a crucial problem in modern IC design. In this paper we develop a novel methodology for power grid verification which is based on accurately constructing the space of current variations of the supplied modules and locating its precise points that yield the worst-case voltage drop conditions. The construction of the current space is performed via plain simulation and statistical extrapolation using results from extreme value theory. The method overcomes limitations of past methods which either relied on loosely bounding the worst-case voltage drop, or abstracted the current space in a vague and incomplete set of bound-type constraints. Experimental results verify the potential of the proposed method to identify worst-case conditions and demonstrate the pessimism inherent in previous bound-type approaches.

The problem of optimum design of tree-shaped power distribution networks with respect to the voltage drop effect is addressed in this paper. An approach for the width adjustment of the power lines supplying the circuit's major functional blocks is formulated, so that the network occupies the minimum possible area under specific voltage drop constraints at all blocks. The optimization approach is based on precise maximum current estimates derived by statistical means from recent advances in the field of extreme value theory. Experimental tests include the design of power grid for a choice of different topologies and voltage drop tolerances in a typical benchmark circuit.

A Monte Carlo approach for maximum power estimation in CMOS very large scale integration (VLSI) circuits is proposed. The approach is based on the largely unexploited area of statistics known as extreme value theory. Within this framework, it attempts to appropriately model the extreme behavior of the probability distribution of the peak instantaneous power drawn from the power supply bus, in order to yield a close estimate of its maximum possible value. The approach features a relatively small number of necessary input patterns that does not depend on the circuit size, user-specified accuracy, and confidence levels for the final estimate, simplicity in the algorithmic implementation, noniterative single-loop execution, highly accurate simulation-based operation, and easy integration within the design flow of CMOS VLSI circuits. Experimental results establish the above claims and demonstrate the overall efficiency of the proposed approach to address the problem of maximum power estimation.