On Computing Criticality in Refactored Timing Graphs

The maximum operator in statistical static timing analysis (SSTA) is a decent approximation for timing sign-off, but often causes significant error in SSTA applications. This paper presents a timing criticality computation method based on non-maximum analytic operators in a parameterized SSTA. After an SSTA run, the proposed method computes the criticality for all edges and nodes in a single graph traversal. Although we do not employ the max operator in the computation process, the error in the maximum operator still degrades the accuracy of the computed criticality because the criticality is a joint probability of expressions, including arrival times, which are computed by the maximum operator during SSTA. To address this issue, we employ the refactoring technique, which was recently proposed to reduce common path pessimism in combinational circuits. This paper shows that refactoring is also very useful in reducing the maximum-induced error in arrival times, and how existing graph-based algorithms can be geared toward refactoring. Our experimental results show that the proposed method reduces the error of the criticality significantly compared to the conventional cutset-based method.

I. Introduction

The variability of process parameters has been increasing in every new technology node and has posed a significant challenge in circuit timing analysis. As process variations increase, static timing analysis produces more pessimistic results, which lead designers and tools to fix false timing violations, increasing design time and resulting in suboptimal designs. To reduce the pessimism, more sophisticated static timing analysis methods [1], [7], [8] have been proposed, and statistical static timing analysis (SSTA) is considered the most accurate one.