Multi-clock path analysis using propositional satisfiability

Kazuhiro Nakamura; Shinji Maruoka; Shinji Kimura; Katsumasa Watanabe

doi:10.1145/368434.368533

Multi-clock path analysis using propositional satisfiability

Kazuhiro Nakamura, Shinji Maruoka, Shinji Kimura, Katsumasa Watanabe

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000
Pages	81-86
Number of pages	6
DOIs	https://doi.org/10.1145/368434.368533
Publication status	Published - 2000 Dec 1
Externally published	Yes
Event	2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000 - Yokohama, Japan Duration: 2000 Jan 25 → 2000 Jan 28

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference	2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000
Country/Territory	Japan
City	Yokohama
Period	00/1/25 → 00/1/28

ASJC Scopus subject areas

Computer Science Applications
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1145/368434.368533

Cite this

Multi-clock path analysis using propositional satisfiability. / Nakamura, Kazuhiro; Maruoka, Shinji; Kimura, Shinji et al.
Proceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000. 2000. p. 81-86 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Nakamura, K, Maruoka, S, Kimura, S & Watanabe, K 2000, Multi-clock path analysis using propositional satisfiability. in Proceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 81-86, 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000, Yokohama, Japan, 00/1/25. https://doi.org/10.1145/368434.368533

@inproceedings{5e98b5fb1baf47e8aea86b3edd832e1b,

title = "Multi-clock path analysis using propositional satisfiability",

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.",

author = "Kazuhiro Nakamura and Shinji Maruoka and Shinji Kimura and Katsumasa Watanabe",

year = "2000",

month = dec,

day = "1",

doi = "10.1145/368434.368533",

language = "English",

isbn = "0780359747",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

pages = "81--86",

booktitle = "Proceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000",

note = "2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000 ; Conference date: 25-01-2000 Through 28-01-2000",

}

TY - GEN

T1 - Multi-clock path analysis using propositional satisfiability

AU - Nakamura, Kazuhiro

AU - Maruoka, Shinji

AU - Kimura, Shinji

AU - Watanabe, Katsumasa

PY - 2000/12/1

Y1 - 2000/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=50249097657&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50249097657&partnerID=8YFLogxK

U2 - 10.1145/368434.368533

DO - 10.1145/368434.368533

M3 - Conference contribution

AN - SCOPUS:50249097657

SN - 0780359747

SN - 9780780359741

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 81

EP - 86

BT - Proceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000

T2 - 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000

Y2 - 25 January 2000 through 28 January 2000

ER -

Multi-clock path analysis using propositional satisfiability

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this