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

fYear

2000

fDate

9-9 June 2000

Firstpage

81

Lastpage

86

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ASPDAC.2000.835075

Filename

835075