1Statistical Analysis of Power Grid NetworksConsidering Lognormal Leakage Current Variationswith Spatial CorrelationNing Mi, Student Member, IEEE, Jeffrey Fan, Student Member, IEEE,and Sheldon X.-D. Tan, Senior Member, IEEEDepartment of Electrical EngineeringUniversity of California, Riverside, CA 92521, USAAbstract— As the technology scales into 90nm and below,process-induced variations become more pronounced. In thispaper, we propose an efficient stochastic method for analyzingthe voltage drop variations of on-chip power grid networks,considering log-normal leakage current variations with spatialcorrelation. The new analysis is based on the Hermite polynomialchaos (PC) representation of random processes. Different fromthe existing Hermite PC based method for power grid analysis,which models all the random variations as Gaussian processeswithout considering spatial correlation. The new method focuseson the impacts of stochastic sub-threshold leakage currents,which are modeled as log-normal distribution random variables,on the power grid voltage variations. To consider the spatialcorrelation, we apply orthogonal decomposition to map thecorrelated random variables into independent variables. Ourexperiment results show that the new method is more accuratethan the Gaussian-only Hermite PC method using the Taylorexpansion method for analyzing leakage current variations, andtwo orders of magnitude faster than the Monte Carlo methodwith small variance errors. We also show that the spatialcorrelation may lead to large errors if not being considered inthe statistical analysis.Index Terms— Power grid networks, Hermite polynomials,Principal component analysis, Spatial correlationI. INTRODUCTIONPROCESS-INDUCED variability has huge impacts on thecircuit performance in the sub-90nm VLSI technolo-gies [10], [9]. One important aspect of the variations comesfrom the chip leakage currents. Leakage currents come fromdifferent sources. The dominant factor is the sub-thresholdleakage current. The reason is that sub-threshold leakagecurrent has a rapid increasing rate (about 5X-10X increaseper technology generation [2]), and it is highly sensitiveto threshold voltage Vthvariations, due to the exponentialrelationship between sub-threshold current Iof fand thresholdvoltage Vthas shown below [14],Iof f= Is0eVgs−VthnVT(1 − e−VdsVT) (1)where Is0is a constant related to the device characteristics,VTis the thermal voltage, and n is a constant.Clearly, the leakage current has exponential dependency onthe threshold voltage Vth. In the sequel, the leakage currentThis work is supported in part by NSF CAREER Award CCF-0448534,NSF grant OISE-0451688 and NSF grant OISE-0623038.is mainly referred to as the sub-threshold leakage current.Detailed analysis shows that Iof fis also an exponentialfunction of the channel length L [12]. So, if we model Vthor Las the random variables with Gaussian variations due to inter-die or intra-die process variations, then the leakage currentswill have a log-normal distribution as shown in [12]. On topof this, those random variables are spatially correlated withina die, due to the nature of the many physical and chemicalmanufacture processes [9].Due to the importance of the impacts on leakage cur-rents on the circuit performances, especially on the on-chippower delivery networks, a number of research works havebeen proposed recently to perform the stochastic analysis ofpower grid networks under process-induced leakage currentvariations. The voltage drop of power grid networks subjectto the leakage current variations was first studied in [3],[4]. This method assumes that the log-normal distribution ofthe node voltage drop is due to log-normal leakage currentinputs and is based on a localized Monte Carlo (sampling)method to compute the variance of the node voltage drop.However, this localized sampling method is limited to thestatic DC solution of power grids modeled as resistor-onlynetworks. Therefore, it can only compute the responses tothe standby leakage currents. However, the dynamic leakagecurrents become more significant, especially when the sleeptransistors are intensively used nowadays for reducing leakagepowers. In [13], [11], impulse responses are used to computethe means and variances of node voltage responses due togeneral current variations. But this method needs to know theimpulse response from all the current sources to all the nodes,which is expensive to compute for a large network. In [12],the probability density function (pdf) of leakage currents arecomputed based on the Gaussian variations of channel length.Recently, a stochastic simulation method for interconnectand power grid networks has been proposed [7], [15]. Thismethod is based on the orthogonal polynomial chaos ex-pansion of random processes to represent and solve for thestochastic responses of linear systems. The major benefitof this method is its compatibility with current transientsimulation framework: it solves for some coefficients of theorthogonal polynomials, which can be done by using normaltransient simulations of the original circuits with deterministicinputs to compute variances of node responses. Some existing1-4244-9707-X/06/$20.00 ©2006 IEEE2approaches [7] model all the parameter variations as Gaussian(or approximate them as Gaussian variations by using first-order Taylor expansion) [15]. Those methods also fail to con-sider the spatial correlation in the process parameter randomvariables.In this paper, we apply the orthogonal polynomial basedmethods (also called spectral statistical method) to deal withleakage current inputs with log-normal distributions and spatialcorrelations. We show how to represent a log-normal distri-bution in terms of Hermite polynomials, assuming Gaussiandistribution of threshold voltage Vthin consideration of intra-die variation. To consider the spatial correlation, we applyorthogonal decomposition via principal component analysisto map the correlated random variables into independentvariables. To the best knowledge of the authors, the proposedmethod is the first method being able to perform statisticalanalysis on power grids with variation dynamic leakage cur-rents having log-normal distributions and spatial correlations.Experiment results show that the proposed method predicatesthe variances of the resulting log-normal-like node voltagedrops more accurately than Taylor expansion based Gaussianapproximation method.II. PROBLEM FORMULATI O NA. Power Grid