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. / text

A degree-constrained subgraph construction (DCS) problem aims to find an optimal spanning subgraph (w.r.t an objective function) subject to certain degree constraints on the vertices. DCS generalizes many combinatorial optimization problems such as Matchings and Edge Covers and has many practical and real-world applications. This thesis focuses on DCS problems where there are only upper and lower bounds on the degrees, known as b-matching and b-edge cover problems, respectively. We explore linear and submodular functions as the objective functions of the subgraph construction.<br><br>The contributions of this thesis involve both the design of new approximation algorithms for these DCS problems, and also their applications to real-world contexts.<br>We designed, developed, and implemented several approximation algorithms for DCS problems. Although some of these problems can be solved exactly in polynomial time, often these algorithms are expensive, tedious to implement, and have little to no concurrency. On the contrary, many of the approximation algorithms developed here run in nearly linear time, are simple to implement, and are concurrent. Using the local dominance framework, we developed the first parallel algorithm submodular b-matching. For weighted b-edge cover, we improved the classic Greedy algorithm using the lazy evaluation technique. We also propose and analyze several approximation algorithms using the primal-dual linear programming framework and reductions to matching. We evaluate the practical performance of these algorithms through extensive experimental results.<br><br>The second contribution of the thesis is to utilize the novel algorithms in real-world applications. We employ submodular b-matching to generate a balanced task assignment for processors to build Fock matrices in the NWChemEx quantum chemistry software. Our load-balanced assignment results in a four-fold speedup per iteration of the Fock matrix computation and scales to 14,000 cores of the Summit supercomputer at Oak Ridge National Laboratory. Using approximate b-edge cover, we propose the first shared-memory and distributed-memory parallel algorithms for the adaptive anonymity problem. Minimum weighted b-edge cover and maximum weight b-matching are shown to be applicable to constructing graphs from datasets for machine learning tasks. We provide a mathematical optimization framework connecting the graph construction problem to the DCS problem.