ICCAD 2005 paper review and comment. By Yan Lin

A. Statistical Gate Sizing
    1. K. Chopra and et al, "Parametric Yield Maximization using Gate Sizing based on Efficient Statistical Power and Delay Gradient Computation"
    Comment: This paper studies gate sizing for yield maximization. Both timing and power yield as well as the reversed correlation between timing and power are considered. It's not clear that which deterministic gate sizing algorithm is used as a base. The gate sizing algorithm is based on gradient re-calculation in a non-linear optimization framework. The yield gradient for each gate is obtained by calculating the timing/power yield change due to a small perturbation in gate size for each gate. The number of iteration is n where n is number of gates in netlist. In each iteration, yield gradient is calculated for each gate.
    A naive brute-force algorithm is first presented. SSTA and power yeild analysis is performed for each gate for gradient calculation in each iteration. The yield gradient calculation time complexity is O(n_g n²) where n_g is the number of variation sources.
    The author also presents a heuristic for incremental SSTA. Circuit delay pdf is estimated by updating arrival time pdf for only a sub-set of gates. SSTA is only performed once before yield gradient calculation for each gate. The max information can be re-used using heap in gate yield gradient calculation with average time complexity of O(n_g n log(n)). However, some error is introduced by this heuristic. And the maximum error is shown to be  less then 7.4% overall all test designs.
    It is shown that the second approach achieves 3X-20X for all designs. However, the speed-up is measured only for yield gradient calculation. It's not clear the overall speed-up when considering the runtime for non-linear optimizer. When using nominal value plus one sigma as the cut off value for power and timing, the yield improvement is from 2% to 20%.
    2. M. R. Guthaus and et al, "Gate Sizing Using Incremental Parameterized Statistical Timing Analysis"
    Comment: This paper presents statistical gate sizing leveraging an block-based SSTA for timing optimization. The algorithm is based on TILOS. The authors justify their canonical delay model, which is presumed in other work, with experimental data. The authors also provide an insight on why and when the mean delay value may be larger than the nominal delay value. For candidate gate selection, two  methods are studied. The first one selects gate using statistical slack while the second one uses statistical criticality. It is shown that the second one serves better with a clear explanation (although quite straightforward). 
    3. D. Sinha, N. Shenoy and H. Zhou, "Statistical Gate Sizing for Timing Yield Optimization"
    Comment: This paper also studies gate sizing leveraging an block-based SSTA for timing optimization. The algorithm is based on a perturbation-based sizing algorithm. In each iteration, a few candidates are selected with yield improvement. A sub-set of all candidates are selected based on maximum cumulative yield improvement. Maximization of slack_mean/slack_sigma is proved to be equal as maximization of timing yield. However, this is dependent on the cut-off delay selection for slack calculation. The author does not make it clear. The author also provides another cost function as to maximize slack_mean - 3* slack_sigma, which maximize the worst case and heuristically maximize timing yield. When using the nominal delay given by static optimization method (corresponding to 50% timing yield), and average 80% timing yield is achieved by statistical method.
  Interestingly, the authors point out that the statistical method may choose a larger gate with larger nominal delay but smaller variance compared to static method. However, as shown in the paper, one design actually achieves smaller nominal delay using statistical method. The author does NOT explain this issue at all and does NOT show nominal delay for other designs, which I believe to be the critical issue for timing yield improvement. In fact, 1.0X delay achieved in static method is used to evaluate timing yield. In this case, timing yield cannot be improved without a smaller nominal delay.

B. Statistical Criticality Analysis
    Statistical criticality for a path/node/edge is defined as the probability that this path/node/edge is timing critical considering variation. The statistical criticality based on arrival tightness probability (ATP) in "First order incremental block-based statistical timing analysis" [Chandu et al, DAC04] ignores the correlation due to path convergence and is only true when paths are independent. The following two papers address this problem and provide solutions from two different aspects.
    1. Y. Zhan and et al, "Statistical Critical Path Analysis Considering Correlations"
    Comment: This paper calculates path statistical criticality from probability point of view. Quadratic instead of first order canonical delay model is used in this work to consider non-linear effect. Two methods are provided based on the derived formula. The first one is based moment matching and is analytic. The second one is based on Monte Carlo but for the formula. The results are compared to true Monte Carlo based on statistical criticality definition. It is shown that analytic method and the proposed MC achieve an average of 1.5% and 0.5% for path criticality compared to the true MC, respectively. The method based on ATP can introduce up to 38% of error compared to true MC.
    2. X. Li and et al, "Defining Statistical Sensitivity for Timing Optimization of Logic Circuit with Large-Scale and Environmental Variations"
   Comment:   This paper studies path/edge statistical criticality from sensitivity point of view. The sensitivity is defined as statistical circuit delay change if a path/edge delay is perturbed by a small value. The author proves that their sensitivity is equal to statistical criticality. The author also provides an method to calculate sensitivity based on moment-matching and bread-first propagation. It is shown that the average error for statistical criticality based on sensitivity is 0.5% (up to 3.4%) compared to Monte Carlo simulation.