Literature Review on Statistical Gate Sizing considering Process Variation
Commented by Yan Lin
Last update: 05/15/2006

Summary:
Statistical gate sizing has been studied in recent years. Only some relatively new publications in the literature are reviewed as below since the older ones become obsolete soon with the better understanding of process variation and the proposed more sophisticated SSTA algorithms. In general, statistical gate sizing can be categorized in two two groups,( I) iterative greedy algorithms with SSTA as evaluation in each iteration and (II) non-linear programming based sizing.

[1] A. Agarwal et al, "Statistical timing based optimization using gate sizing",  DATE'05 (pdf)
The problem formulation is to improve p-percentile (e.g. 99%) delay by gate sizing considering process variation. Two algorithms are presented. Both iteratively start from all min-size netlist and size up the gate with the largest sensitivity. SSTA is performed in each iteration in both algorithms. The first algorithm uses brute-force approach and perform SSTA for each gate in each iteration, which results in O(V*E) complexity in each iteration. An heuristic is presented in the second algorithm to calculate a lower-bound p-percentile delay. The second algorithm achieves around 10X speed-up compared to the first one. However, a more accurate algorithm may just calculates statistical criticality for all gates with O(n(V+E)) complexity in each iteration, such as [2].

[2] M. R. Guthaus and et al, "Gate Sizing Using Incremental Parameterized Statistical Timing Analysis", ICCAD'05 (pdf)
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). The complexity is O(n(V+E)) in each iteration.

[3] D. Sinha, N. Shenoy and H. Zhou, "Statistical Gate Sizing for Timing Yield Optimization", ICCAD'05 (pdf)
This paper 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. The complexity is O(n(V+E)) in each iteration.

[4] O. Neiroukh and X. Song, "Improving the process-variation tolerance of digital circuits using gate sizing and statistical techniques", DATE'05 (pdf)
This paper is to optimize timing considering process variation using gate sizing. It is a greedy iterative sizing algorithm with SSTA involved in each iteration.

[5] V. Agarwal and J. Wang, "Yield-area optimizations of digital circuits using non-dominated sorting genetic algorithm", ASPDAC'06 (pdf)
This paper presents the gate sizing algorithm to optimize timing yield and area using genetic algorithm. Atomic operations are presented for the genetic algorithm for gate sizing problem.

[6] S. Choi, B. Paul and K. Roy, "Novel sizing algorithm for yield improvement under process variation in nanometer technology", DAC'05 (pdf)
The problem formulation is to minimize area under timing constraint considering process variation. It's an iterative algorithm. In each iteration, Lagrangian relaxation (LR) method is performed for deterministic sizing. SSTA is then performed for the current solution and to update the delay constraint given the cut-off delay and target timing yield. The LR parameter lambda is also updated. However, the SSTA is not sophisticated. The mean delay is assumed as the same as the nominal delay as well. This assumption will result in over-optimistic timing yield estimation, i.e. the target timing yield may not be met after optimization.

[7] S. Sapatnekar and et al, "Robust gate sizing by geometric programming", DAC'05 (pdf)
The problem formulation is to minimize area under timing constraint considering process variation. The robust sizing problem is formulated as geometric programming extended from "an exact solution to the transistor sizing problem for cmos circuits using convex optimization" in TCAD'93. The delay estimated from spanning tree can be expressed in posynomial form, which avoid max operation. Although this estimation is NOT exact even in deterministic case, Monte Carlo simulation shows that the estimation is effective. On the other hand, it's unclear that what kind of process variation the authors have considered.