Bound-based identification of timing-violating paths under variability

We introduce a bound-based technique to identify the top M timing-violating paths in a circuit under variability. These are the paths with the highest violation probability (i.e., C_p) which is the probability that a path (i.e., p) violates the timing constraint. To compute C_p, we require the violation probabilities of the nodes (i.e., C_n) and edges (i.e., C_e) on the path. First, we show computing C_n and C_e of all the nodes and edges requires only two rounds of Statistical Static Timing Analysis and then for each node/edge we need one table lookup for probability calculation using a technique known as Pearson Curve. Given C_n and C_e, our major contribution is in computing upper and lower bounds for C_p of an arbitrary path segment. We show constant-time for incremental update of the bounds when extending a path segment to a longer one. These bounds can be used to exactly construct the top violating paths. If the goal is to find the single most-violating path, we show a bound-based formulation that can prune a large portion of circuit without losing optimality. In our simulations, we verify the correctness and accuracy of our bounds for individual paths. We also verify identification of selected paths using Monte Carlo simulation. We obtain near-optimal accuracy with fast runtimes.