Change search
ReferencesLink to record
Permanent link

Direct link
Study of Timing Yield Optimization and Rectilinear Polygon Generation Algorithm
KTH, School of Information and Communication Technology (ICT).
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
2011. , 67 p.
Trita-ICT-EX, 2011:37
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-121588OAI: diva2:619213
Educational program
Master of Science - System-on-Chip Design
Available from: 2013-05-02 Created: 2013-05-02 Last updated: 2013-05-02Bibliographically approved

Open Access in DiVA

fulltext(1238 kB)281 downloads
File information
File name FULLTEXT01.pdfFile size 1238 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 281 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 37 hits
ReferencesLink to record
Permanent link

Direct link