Nano-scale Integrated Circuits Statistical Timing Analysis And Yield Optimization Method Study

The great improvements of the semiconductor industry depend on continuously technology scaling,which provides device with better performance and exponentially increasing integration capability.However,complex nano-technology such as sub-wavelength lithography and chemical-mechanical polishing will cause more and more large process variations and therefore seriously deteriorate the yield.The yield loss is primarily due to non-Gaussian critical path delay distributions arising from process variations.The most advanced statistical static timing analysis(SSTA) methods can now provide accurate predictions about these distributions before manufacture.But it is still hard to make yield optimization during chip design stage since the circuit optimization methods driven by those statistical timing information are not available now.Yield loss problem has become a fateful and critical problem for nanometer chip design.In order to address the critical yield analysis and optimization problem mentioned above,several works have been done in this dissertation.Firstly a stochastic sparse-grid collocation method with input truncation and an adaptive stochastic collocation method are proposed for solving the critical MAX problem in SSTA.The proposed methods can achieve better efficiency and accuracy compared with the existing methods.Based on the simulation results from SSTA,a novel timing yield driven clock skew scheduling method is proposed,which can address non-Gaussian distributions on critical path delays.The algorithms proposed in the above research work are listed below.1.Statistical static timing analysis method considering nanometer process variations.(1).In order to solve the critical MAX problem during SSTA,a Stochastic Sparse-grid Collocation Method(SSCM) is proposed in this paper.Compared with the existing work,the proposed method can provide stabler approximation results than the most accurate algorithm up to now,which is based on the stochastic Galerkin method with dimension reduction technique.Secondly,the proposed SSCM could avoid the exponential increase of the number of collocation points generated by direct tensor product scheme in the high dimensional random space.Combined with the intput truncation technique proposed in this paper,the SSCM requires shortest computing time compared with most of the other methods and 100x faster than 10,000 Monte Carlo method.(2).Based on SSCM,a novel adaptive algorithm(ASCM) is proposed for MAX approximation.The proposed ASCM adaptively chooses the optimal algorithm from a set of stochastic collocation methods by considering different input conditions of MAX operator and makes a good trade-off between efficiency and accuracy. Experimental results on ISCAS' 85 benchmark circuits have shown that the proposed method has up to 10x improvements in the accuracy while using the same order of computation time compared with the existing methods.2.Clock skew scheduling for yield optimization considering nanometer process variations.(1).A general probleme formulation is proposed for timing yield driven clock skew scheduling problem and non-Gaussian critical path delay distributions can be accurately addressed for the first time.With a MIN-MAX style,the proposed formulation covers most of the previous formulations which were proposed in the top-level conferences such as ICCAD and DAC since 1990.Furthermore,the limitations of those existing methods are indicated with statistical interpretations.(2) A general minimum balancing(GMB) algorithm is proposed for solving the yield optimization problem with the proposed formulation.The efficiency of the algorithm is enhanced by a fast Piece-wise linear interpolation based numerical algorithm for computing the inverse CDF involved in the formulation.Compared with the best results by two representative existing methods,which include the one with the name EVEN was proposed in ICCAD1999 by C.Albrecht and Professor Jens Vygen,et.al. from Born University,and the one with the name PROP proposed in ICCAD2004 by Professor Charlie Chung-Ping Chen,Kewal K.Saluja,et.al.from University of Wisconsin,Madison,the proposed GMB method significantly exceeds in the yield optimization with up to 33.6%and averagely 17.7%improvements,which are tested on benchmark ISCAS' 89 benchmark circuits.