Study of Timing Yield Optimization and Rectilinear Polygon Generation Algorithm

With the decreasing of integrate circuit’s feature size, the process parameters of chips have serious variations. The process variations have severe influence on the timing analysis of integrate circuit. The precise modeling of process variations is the prerequisite of statistical timing analysis. Intra-die variation is one part of the process variation. It is one of the dominant factors affecting chip’s performance and behaves spatial correlation. With the decreasing of feature size, the spatial correlation of intra-die variation becomes more and more complicated. The traditional parametric approach fails to describe the corresponding correlation function correctly. Recent study found out that the spatial correlation of intra-die variation is different in different directions, which is called anisotropic. To improve the accuracy of the spatial correlation modeling of intra-die variation, this thesis presents a non-parametric approach for estimation, using B-spline function as the basis function of the correlation function. The result accords with the statistical characteristics of the samples. Clock skew scheduling is a method utilizing the clock skew to optimize the circuit’s performance. The clock period minimization and timing failure probability minimization are two conflicting targets in clock skew scheduling. Considering the influence of process variations, traditional yield driven clock skew scheduling can be described as a series of minimum ratio cycle problems. However, the description assumed that the critical path delay is Gaussian distribution which is no longer suitable for the nanometer process of next generation. Latest study has presented a method considering non Gaussian distribution. This method solved the optimization problem by generalized Lawler’s algorithm. To accelerate the solving of the optimization problem, this thesis further presents several improved algorithm. The experimental result shows that the improved algorithm is faster than the former algorithm. The test of EDA algorithm needs rectilinear polygons in different layouts which come from real cases and randomly generated cases. Sometimes, the real cases cannotcover all the cases in complex algorithm. In this thesis, a practical algorithm that generates random rectilinear polygon is proposed, which can flexibly generate layout cases of different distributions and sizes. We prove that the new algorithm is guaranteed to terminate within finite steps