In this article, we present a new full-chip statistical leakage estimation considering the spatial correlation condition (strong or weak). The new algorithm can deliver linear time, O ( N ), time complexity, where N is the number of grids on chip. The proposed algorithm adopts a set of uncorrelated virtual variables over grid cells to represent the original physical random variables and the cell size is determined by the spatial correlation length. In this way, each physical variable is always represented by virtual variables locally. We prove the number of neighbor cells for each grid cell is not related to the condition of spatial correlation (from no correlation to 100% correlated), which leads to linear time complexity in terms of number of gates. We compute the gate leakage by the orthogonal polynomials-based collocation method. The total leakage of a whole chip can be computed by simply summing up the coefficients of corresponding orthogonal polynomials in each grid cell. Furthermore, we develop a look-up table to cache statistical information for each type of gate instead of calculating leakage for every single instance of gate on a chip. As a result, a new statistical leakage characterization in Standard Cell Library (SCL) is put forward. Furthermore, an incremental analysis algorithm is proposed to update the chip-level statistical leakage information efficiently after a few changes are made. The proposed method has no restrictions on static leakage models, or types of leakage distributions. The large circuit examples in 45nm CMOS process demonstrate the proposed algorithm is 1000X faster than a recently proposed grid-based method with similar accuracy and many orders of magnitude times speedup over the Monte Carlo method. Experimental results also show the incremental analysis provides about 10X further speedup. We expect the incremental analysis could achieve more speedup over the full leakage analysis for larger problem sizes.

This paper proposes a new parameterized dynamic thermal modeling algorithm for emerging thermal-aware design and optimization for high-performance microprocessor design at architecture and package levels. Compared with existing behavioral thermal modeling algorithms, the proposed method can build the compact models from more general transient power and temperature waveforms used as training data. Such an approach can make the modeling process much easier and less restrictive than before and, thus, more amenable for practical measured data. The new method, called ParThermSID, consists of two steps. First, the response surface method based on second-order polynomials is applied to build the parameterized models at each time point for all of the given sampling nodes in the parameter space. Second, an improved subspace system identification method, called ThermSID, is employed to build the discrete state space models, by construction of the Hankel matrix and state space realization, for each time-varying coefficient of the polynomials generated in the first step. To overcome the overfitting problems of the subspace method, the new method employs an overfitting mitigation technique to improve model accuracy and predictive ability. Experimental results on a practical quad-core microprocessor show that the generated parameterized thermal model matches the given data very well. The compact models generated by ParThermSID also offer two orders of magnitude speedup over the commercial thermal analysis tool FloTHERM on the given example. The results also show that ThermSID is more accurate than the existing ThermPOF method.

It is well known that model order reduction for circuits with many terminals remains a challenging problem. One reason is that existing approaches are based on a centralized framework, in which each input-output pair is implicitly assumed to be equally interacted and the matrix-valued transfer function is assumed to be fully populated. In this paper, we attempt to address this long-standing problem using a decentralized model order reduction scheme, in which a multi-input multi-output system is decoupled into a number of subsystems and each subsystem corresponds to one output and several dominant inputs. The decoupling process is based on the relative gain array, which measures the degree of interaction of each input-output pair. For each decoupled subsystem, passive reduction can be easily achieved using existing reduction techniques. The proposed method is suitable for resistance-dominant interconnects such as on-chip power grids, substrate planes where extremely compact models can be obtained. Simulation results demonstrate the advantage of the proposed method compared to the existing approaches.

In this paper, we propose a new performance bound analysis of analog circuits considering process variations. We model the variations of component values as intervals measured from tested chip and manufacture processes. The new method applies a graph-based symbolic analysis and affine interval arithmetic to derive the variational transfer functions of analog circuits (linearized) with variational coefficients in forms of intervals. Then the frequency response bounds (maximum and minimum) are obtained by performing analysis of a finite number of transfer functions given by the Kharitonov's polynomial functions. We show that symbolic de-cancellation is critical for the affine interval analysis. The response bound given by the Kharitonov's functions are conservative given the correlations among coefficient intervals in transfer functions. Experimental results demonstrate the effectiveness of the proposed compared to the Monte Carlo method.

Full-chip statistical leakage power analysis typically requires quadratic time complexity in the presence of spatial correlation. When spatial correlation are strong (with large spatial correlation length), efficient linear time complexity analysis can be attained as the number of variational variables can be significantly reduced. However this is not the case for circuits where gate leakage currents are weakly correlated. In this paper, we present a linear time algorithm for statistical leakage power analysis in the presence of weak spatial correlation. The new algorithm exploits the fact that gate leakage current can be efficiently computed locally when correlation is weak. We adopt a newly proposed spatial correlation model where a new set of location-dependent uncorrelated variables are defined over virtual grids to represent the original physical random variables via fitting. To compute the leakage current of a gate on the new set of variables, the new method uses the orthogonal polynomials based collocation method, which can be applied to any gate leakage models. The total leakage currents are then computed by simply summing up the resulting orthogonal polynomials (their coefficients) on the new set of variables for all gates. Experimental results show that the proposed method is about two orders of magnitude faster than the recently proposed grid-based method [3] with similar accuracy and many orders of magnitude times over the Monte Carlo method.

This paper proposes a new architecture-level thermal modeling method to address the emerging thermal related analysis and optimization problem for high-performance multi-core microprocessor design. The new approach builds the thermal behavioral models from the measured or simulated thermal and power information at the architecture level for multi-core processors. Compared with existing behavioral thermal modeling algorithms, the proposed method can build the behavioral models from given arbitrary transient power and temperature waveforms used as the training data. Such an approach can make the modeling process much easier and less restrictive than before, and more amenable for practical measured data. The new method is based on a subspace identification method to build the thermal models, which first generates a Hankel matrix of Markov parameters, from which state matrices are obtained through minimum square optimization. To overcome the overfitting problems of the subspace method, the new method employs an overfitting mitigation technique to improve model accuracy and predictive ability. Experimental results on a real quad-core microprocessor show that ThermSID is more accurate than the existing ThermPOF method. Furthermore, the proposed overfitting mitigation technique is shown to significantly improve modeling accuracy and predictability.

In this paper, we present an approved linear-time algorithm for statistical leakage analysis in the present of any spatial correlation condition (strong or weak). The new algorithm adopts a new set of uncorrelated variables over virtual grids to represent the original physical random variables and the grid size (thus of number of new random variables) is determined by the spatial correlation length. In this way, each physical variable is always represented by virtual variables locally. We prove that the number of neighboring virtual grids for each grid is not related to condition of spatial correlation, which leads to linear time complexity in terms of number of gates. We compute the gate leakage by the orthogonal polynomials based collocation method. The total leakage of a whole chip can be computed by simply summing up the coefficients of corresponding orthogonal polynomials for each grid. Furthermore, look-up table can be created to cache statistical information for each type of gates in library instead of calculating leakage for every single gate on chip. As a result, we end up with O(N) time complexity, where N is the number of grids on chip. The proposed method has no restrictions on static leakage models, types of statistical distributions for leakage currents. Experimental results show that the proposed method is about 1000X faster than the recently proposed grid-based method [2] with similar accuracy and many orders of magnitude times over the Monte Carlo method.

In this paper, we propose a novel statistical capacitance extraction method for interconnect conductors considering process variations. The new method is called statCap, where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then, an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After this, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Finally, we present a method to extend statCap to the second-order form to give more accurate results without loss of efficiency compared to the linear models. We show the derivation of the analytic second-order orthogonal polynomials for the variational capacitance integral equations. Experimental results show that statCap is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical conductor structures.

In this paper, we present a novel statistical full-chip leakage power analysis method. The new method can provide a general framework to derive the full-chip leakage current or power in a closed form in terms of the variational parameters, such as the channel length, the gate oxide thickness, etc. It can accommodate various spatial correlations. The new method employs the orthogonal polynomials to represent the variational gate leakages in a closed form first, which is generated by a fast multi-dimensional Gaussian quadrature method. The total leakage currents then are computed by simply summing up the resulting orthogonal polynomials (their coefficients). Unlike many existing approaches, no grid-based partitioning and approximation are required. Instead, the spatial correlations are naturally handled by orthogonal decompositions. The proposed method is very efficient and it becomes linear in the presence of strong spatial correlations. Experimental results show that the proposed method is about 10× faster than the recently proposed method [4] with constant better accuracy.

In this paper, we propose a novel statistical capacitance extraction method for interconnects considering process variations. The new method, called statCap, is based on the spectral stochastic method where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After that, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Experimental results show that our method is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical interconnect structures.