On the general false path problem in timing analysis

The false path problem is often referred to as the problem of detecting the longest sensitizable path (a path that is not a false path is a sensitizable path). In the present work, a clear and precise definition of a false path is given. The general false path problem is formulated. The general false path problem is to detect whether a given path (not necessarily the longest one) is a false path. An efficient algorithm for solving the general false path problem is presented. Another algorithm which generates all the possible sensitizable paths with the delays greater than a given threshold T is proposed. As a result of the elimination of most of the false paths, a much higher confidence can be placed in the timing verifier. The efficiency and effectiveness of the latter algorithm are demonstrated by experimental results.