Statistical timing analysis using bounds and selective enumeration
Statistical timing analysis using bounds and selective enumeration
复制标题
使用界限和选择性枚举进行统计时序分析
DOI：
10.1145/589411.589417
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
D. Blaauw
中科院分区：
文献类型：
--
作者：
Aseem Agarwal;V. Zolotov;D. Blaauw
管芯内工艺变化的影响越来越大，因此需要进行统计时序分析，其中门延迟被建模为随机变量。统计时序分析传统上遭受指数运行时间复杂度与电路的大小，由于在电路中的重新收敛路径创建的依赖性。在本文中，我们提出了一种新的方法来统计时序分析，使用统计界和选择枚举来细化这些界限。首先，我们给出了电路统计延迟的正式定义，并从该定义推导出统计时序分析方法。由于这种方法找到确切的统计延迟具有指数运行时间复杂度与电路的大小，我们还提出了一种新的方法计算统计界具有线性运行时间复杂度。我们证明了所提出的界限的正确性。由于我们提供了真实统计延迟的上下界，因此我们可以确定边界的质量。如果计算出的边界是不够接近彼此，我们建议使用一个启发式迭代提高边界使用选择性枚举的样本空间与额外的运行时间。所提出的方法在基准电路上进行了实现和测试。结果表明，建议的界限只有一个小的误差，这可以进一步减少使用选择性枚举适度的额外运行时间。
The growing impact of within-die process variation has created the need for statistical timing analysis, where gate delays are modeled as random variables. Statistical timing analysis has traditionally suffered from exponential run time complexity with circuit size, due to the dependencies created by reconverging paths in the circuit. In this paper, we propose a new approach to statistical timing analysis which uses statistical bounds and selective enumeration to refine these bounds. First, we provide a formal definition of the statistical delay of a circuit and derive a statistical timing analysis method from this definition. Since this method for finding the exact statistical delay has exponential run time complexity with circuit size, we also propose a new method for computing statistical bounds which has linear run time complexity. We prove the correctness of the proposed bounds. Since we provide both a lower and upper bound on the true statistical delay, we can determine the quality of the bounds. If the computed bounds are not sufficiently close to each other, we propose the use of a heuristic to iteratively improve the bounds using selective enumeration of the sample space with additional run time. The proposed methods were implemented and tested on benchmark circuits. The results demonstrate that the proposed bounds have only a small error, which could be further reduced using selective enumeration with modest additional run time.