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 TV 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.
展开▼
