Refactoring-based statistical timing analysis and its applications to robust design and test synthesis

Technology scaling in the nanometer era comes with a significant amount of process variation, leading to lower yield and new types of defective parts. These challenges necessitate robust design to ensure adequate yield, and smarter testing to screen out bad chips. Statistical static timing analysis (SSTA) en- ables this but suffers from crude approximation algorithms.

This dissertation first studies the underlying theories of timing graphs and proposes two fundamental techniques enhancing the core statistical timing algorithms. We first propose the refactoring technique to capture topological correlation. Static timing analysis is based on levelized breadth-first traversal, which is a fundamental graph traversal technique and has been used for static timing analysis over the past decades. We show that there are numerous alternatives to the traversal because of an algebraic property, the distributivity of addition over maximum. This new interpretation extends the degrees of freedom of static timing analysis, which is exploited to improve the accuracy of SSTA. We also propose a novel operator for computing joint probabilities in SSTA. In many SSTA applications, this is very common but is done using the max operator which results in much error due to the linear approximation. The new operator provides significantly higher accuracy at a small cost of run time.

Second, based on the two fundamental studies, this dissertation devel- ops three applications. We propose a criticality computation method that is essential to robust design and test synthesis; The proposed method, combined with the two fundamental techniques, achieves drastic accuracy improvement over the state-of-the-art method, demonstrating the benefits in practical ap- plications. We formulate the statistical path selection problem for at-speed test as a gambling problem and present an elegant solution based on the Kelly criterion. To circumvent the coverage loss issue in statistical path selection, we propose a testability driven approach, making it a practical solution for coping with parametric defects.