Fast Circuit Delay Calculation Based on SAT Solvers

Traditional time unrolling based circuit delay calculation method is inefficient in the case that large circuits are analyzed or accurate delay models are adopted.In order to speedup circuit delay calculation, an improved method by sub-circuit extraction is proposed in this paper.On one hand, a sub-circuit is constructed by analyzing output constraints and extracting related logic cones from the unrolled circuit.The circuit delay is checked on the extracted sub-circuit instead of the unrolled circuit, thus the calculation process is speeded up.On the other hand, the concept of abstract circuit is proposed and preprocess is applied on it to find out the shared structures among extracted sub-circuits.The learning clauses derived from preprocessing can be utilized to speed up SAT solving at each checking step.Experimental results on ISCAS85 and ISCAS89 benchmark demonstrate that the proposed approach can improve the efficiency of circuit delay calculation by about 8 times over the traditional method on average.