The Algorithm Study Of Deep Submicron Statistical Static Timing Analysis

With the continuously scaling of feature size for integrated circuits, controllingthe process precisely for the dies in large scale integrated circuits becomes moreand more difficult. If the process parameters changes, the electric parameters willalso change, this fact makes the precise performance evaluation of the integratedcircuits be a challenging task. Timing analysis is an efficient method to evaluate theperformance of circuits, traditional timing analysis methods mainly calculate thecircuit delay with the worst-case model by using Multi Process Corners technology,and do not take the statistical characteristic of the process variations into account.However, as the intra-die process variations exert an increasing influence on circuits,this kind of method will lead to more and more pessimistic performance evaluationresults, such embarrassing conditions provide the statistical static timing analysis(SSTA) with a good opportunity of development. This thesis, from the aspects of amodified process distribution modeling algorism considering spatial correlationsand a new principle parameters selection method based on support vector machine(SVM), improves the accuracy and reduces the number of parameters for SSTA.Conventional algorisms do not consider the weight between the spatialcorrelations of process parameters in the distribution model. To improve theaccuracy of decomposing spatial correlations for the algorism, this dissertationtakes the steps illustrates as follows: Firstly, model the inter-die and intra-dieprocess variations as truncated Gaussian distributions separately. Secondly, analysesthe location relationship between different die squares in the normal quad-treedistribution model. Thirdly, construct and solve multi-level distributed spatialcorrelation equations related to Gaussian functions to obtain the fitting weightcoefficients of adjacent and diagonal intra-die squares. Finally, the spatialcorrelations can be decomposed into weighted independent variables, so that thegate and interconnect delay of the valid paths in the design under analysis (DUA)can be approximated as a linear combination of them, thus the statisticalcharacteristics of the circuit delay can be obtained.In the aspect of principle parameters selection, this paper applies SVMtechnology to deal with the set of independent random variable bases. The newalgorism can make maximum elimination of the secondary bases in the set bysolving a convex quadratic problem, and extract the part that the designers areconcerned, so that the amount of data that need to be handled in the traversalfunction module will be reduced greatly. At last, the statistical data such asprobability density function of output transition time can be drawn out by exertingstatistical timing graph traversal, and the circuit delay considering the process variations can be predicted.The complexity of analyzing the intra-die spatial correlation are reducedeffectively by quad-tree decomposition and SVM classification. The timecomplexity of the proposed algorithm is O((Ng+NI) p4n) in the best case, where Ngisthe number of total gates in the DUA, NIis the number of total interconnects in theDUA, p is the number of parameters considered and n is the number of total levelsin the modified quad-tree model. Since the total number of squares increasesexponentially, a small n is enough to bring out good accuracy. Therefore，the timecomplexity of the new algorithm is almost linear to the total number of gates andinterconnects in the DUA, the simulation results of ISCAS89circuits show that theproposed algorithm’s relative error is about2%compared to the preciseMonte-Carlo method, thus proves the high accuracy of the proposed algorism.