Title :
Multi-clock path analysis using propositional satisfiability
Author :
Nakamura, Kazuhiro ; Maruoka, Shinji ; Kimura, Shinji ; Watanbe, K.
Author_Institution :
Graduate Sch. of Inf. Sci., Nara Inst. of Sci. & Technol., Ikoma, Japan
Abstract :
We present a satisfiability based multi-clock path analysis method. The method uses propositional satisfiability (SAT) in the detection of multi-clock paths. We show a method to reduce the multi-clock path detection problems to SAT problems. We also show heuristics on the conversion from multi-level circuits into CNF formulae. We have applied our method to ISCAS89 benchmarks and other sample circuits. Experimental results show the improvement on the manipulatable size of circuits by using SAT.
Keywords :
clocks; computability; delay estimation; logic CAD; multivalued logic circuits; sequential circuits; CNF formulae; ISCAS89 benchmarks; heuristics; multi-clock path analysis; multi-clock path detection problem; propositional satisfiability; sequential logic circuit; Automata; Circuit testing; Clocks; Delay effects; Delay estimation; Frequency estimation; Information analysis; Information science; Sequential circuits; Timing;
Conference_Titel :
Design Automation Conference, 2000. Proceedings of the ASP-DAC 2000. Asia and South Pacific
Conference_Location :
Yokohama, Japan
Print_ISBN :
0-7803-5973-9
DOI :
10.1109/ASPDAC.2000.835075
