Approximate timing analysis of combinational circuits under the XBD0 model

Abstract

This paper is concerned with approximate delay computation algorithms for combinational circuits. As a result of intensive research in the early 90's [3, 8] efficient tools exist which can analyze circuits of thousands of gates in a few minutes or even in seconds for many cases. However, the computation time of these tools is not so predictable since the internal engine of the analysis is either a SAT solver [8] or a modified ATPG algorithm [3], both of which are just heuristic algorithms for an NP-complete problem. Although they are highly tuned for CAD applications, there exists a class of problem instances which exhibits the worst-case exponential CPU time behavior. In the context of timing analysis, circuits with a high amount of reconvergence, e.g. C6288 of the ISCAS benchmark suite, are known to be difficult to analyze under sophisticated delay models even with state-of-the-art techniques. For example [8] could not complete the analysis of C6288 under the mapped delay model. To m...