Statistical Timing Analysis for VLSI Networks in the Presence of Weak Correlations and Non-Gaussian Gate Delay

The context of this Thesis is novel algorithms for timing verification of Integrated Circuit (IC) designs. The continuous reduction of feature size is creating new challenges for the timing analysis of the ICs as process--related uncertainties begin to dominate behaviour. As technology continues to scale down, the impact of variations (such as process--voltage--temperature variations) on timing grows. Moreover, with the decreasing size of transistors and interconnect width, the variations of electrical characteristics can be of the same order as their nominal values. This has created a new wave of interest in research on timing verification and introduced the need for an update to traditional algorithms. As a result, the use of Statistical Static Timing Analysis (SSTA) approaches is increasing. In this Thesis, the problem of SSTA is studied at both gate and circuit levels to address three of the most challenging problems: (i) non-Gaussian delay of logic gates, (ii) computation of the max-operation, and (iii) correlations. At the circuit level, the SSTA problem is considered from the point of view of correlated extremes. The contribution to the Extreme Value Statistics is made, and the corrections to the Gumbel law in the case of weak correlations are proposed. An algorithm for estimating the covariance matrix of timing graphs is derived. At the gate level, an exact analytical expression for the distribution of the gate delay, as well as its four moments, is obtained. Utilising this result, a Gaussian comb model (a variation of Gaussian Mixture Models) is proposed to represent non-Gaussian distributions. This allowed the not NP-hard formulation of an algorithm for the traversal of the non-Gaussian distributions through a timing graph. The obtained results are compared against numerical simulations.