SAT based timing analysis for fixed and rise/fall gate delay models

Abstract

This paper proposes a SAT based technique for timing analysis by an accurate modeling of event propagation within gate-level circuits. The accuracy of the result depends on the level of detail with which circuit activity is modeled. However, the combinatorial blowup in the size and complexity of the problem is the main bottleneck in any detailed modeling. The proposed technique overcomes this problem by an efficient SAT modeling of events at the nodes of the circuit which scales very smoothly with increase in size of the circuit without sacrificing on accuracy even with industry standard gate delays of 0.01 ns granularity. This improvement in performance enables the modeling of more complex gate delay models like the rise/fall delay model which can simulate circuit activity more realistically than the fixed gate delay model.