Statistical timing analysis of flip-flops considering codependent setup and hold times

Safar Hatami, Hamed Abrishami, Massoud PedramACM Great Lakes Symposium on VLSI 2008 · DOI

TL;DR

This paper introduces a novel statistical static timing analysis (SSTA) method that accounts for the statistical interdependence of setup and hold times in flip-flops. By accurately modeling these codependent timing characteristics, the approach provides a more realistic assessment of circuit timing violations, leading to improved design reliability and performance.

What Problem Does This Paper Address?

As integrated circuits shrink to nanometer scales (e.g., 45nm and below), process variations become a significant challenge. These variations introduce uncertainty in the timing behavior of circuit components, making traditional static timing analysis (STA) methods, which rely on fixed "corner" values, increasingly inaccurate and potentially leading to over-constrained or unreliable designs. Statistical Static Timing Analysis (SSTA) aims to address this by considering the probabilistic nature of these variations. However, a critical gap exists in accurately modeling the codependence of setup and hold times for flip-flops. Typically, these are treated as independent, which is a simplification that can lead to errors. This paper tackles the problem of characterizing and utilizing the statistical codependence of setup and hold times within an SSTA framework to achieve more accurate timing verification.

Methods

The paper proposes a three-step methodology for statistical codependent setup and hold time (CSHT) characterization:

  1. Piecewise Linear Approximation of CSHT Contours: The probability mass function (pmf) of codependent setup and hold time contours is approximated using piecewise linear curves. This is achieved by considering the probability density functions (pdfs) of the underlying process variation sources. A key technique introduced is a Backward Euler Based Search (BEBS) algorithm to efficiently generate these contours. BEBS uses a three-point piecewise linear approximation and iteratively searches for points on the contour, offering a significant speedup (10x-20x) over conventional methods.
  2. Computation of Required Setup and Hold Times: The pmf of the required setup time (RST) and required hold time (RHT) for each flip-flop in the design is computed. This involves defining statistical required setup time (SRST) and statistical required hold time (SRHT) as random variables.
  3. Probability of Timing Violation Calculation: The computed pmfs from steps 1 and 2 are used to determine the probability of individual flip-flops satisfying timing constraints. This results in a "Statistical Pass Value" (SPV) for each flip-flop, which is then aggregated into a histogram representing the overall pass probability distribution for the design. The paper also introduces a method to partition the setup/hold plane into regions with fixed total probability, facilitating the calculation of SPV.

Datasets

The paper does not explicitly mention using pre-existing datasets for training or evaluation. Instead, it focuses on a methodology applied to a True Single Phase Clocking (TSPC) flip-flop. The evaluation involves comparing the BEBS algorithm's results against conventional methods and Monte-Carlo simulations.

Key Insights and Ideas

  • Codependence is Crucial: The paper strongly emphasizes that setup and hold times are not independent and that ignoring this codependence leads to inaccurate timing analysis.
  • BEBS Algorithm Efficiency: The proposed Backward Euler Based Search (BEBS) algorithm is a significant contribution, offering a much faster and efficient way to characterize CSHT contours compared to existing methods.
  • Probabilistic Pass/Fail: Moving beyond deterministic pass/fail counts, the method provides a probabilistic "pass probability" histogram, giving designers a richer understanding of timing robustness.
  • Impact of Process Variations: The work clearly demonstrates how process variations (like Leff and Vth) directly influence the CSHT contours and, consequently, the timing reliability of flip-flops.

Key Results

  • The BEBS algorithm was validated and showed a speedup of 10x to 20x over conventional methods for CSHT characterization.
  • The proposed method was applied to a TSPC flip-flop, and the resulting statistical pass value (SPV) was compared with Monte-Carlo simulations, showing good agreement. For example, a Monte-Carlo simulation estimated an SPV of approximately 2/3, which was closely matched by the proposed technique.
  • The paper illustrates the impact of variations in Leff and Vth on the CSHT contours, showing how these parameters shift and deform the contours.

Limitations and Future Work

  • Assumptions: The paper assumes that the slope of the CSHT contour changes smoothly and that the critical line random variables (CLRVs) are normally distributed. While these assumptions are justified by the authors' experience, they might not hold universally.
  • Complexity of Partitioning: The partitioning of the setup/hold plane into regions for SPV calculation, while effective, can become complex with a large number of borderlines.
  • Future Work: The authors suggest that the proposed methodology can be extended to characterize other sequential elements and to incorporate more complex statistical models for process variations. Further exploration of the impact of spatial correlations in process variations on CSHT could also be a valuable future direction.

Summary updated

BibTeX
@inproceedings{hatami2008statistical,
  author = {Safar Hatami and Hamed Abrishami and Massoud Pedram},
  title = {{Statistical timing analysis of flip-flops considering codependent setup and hold times}},
  booktitle = {ACM Great Lakes Symposium on VLSI},
  year = {2008},
  doi = {10.1145/1366110.1366135},
}
Figure