Statistical timing verification for transparently latched circuits

High-performance integrated-circuit designs need to verify the clock schedules as they usually have level-sensitive latches for their speed. With process variations, the verification needs to compute the probability of correct clocking. Because of complex statistical correlations and accumulated inaccuracy of statistical operations, traditional iterative approaches have difficulties in getting accurate results. A statistical check of the structural conditions for correct clocking is proposed instead, where the central problem is to compute the probability of having a positive cycle in a graph with random edge weights. The authors proposed two algorithms to handle this. The proposed algorithms traverse the graph only several times to reduce the correlations among iterations, and it considers not only data delay variations but also clock-skew variations. Although the first algorithm is a heuristic algorithm that may overestimate timing yields, experimental results show that it has an error of 0.16% on average in comparison with the Monte Carlo (MC) simulation. Based on a cycle-breaking technique, the second heuristic algorithm can conservatively estimate timing yields. Both algorithms are much more efficient than the MC simulation.