| Presentation | 1999/11/27 Multi-Clock Path Analysis Based on Propositional Satisfiability Kazuhiro Nakamura, Shinji Maruoka, Shinji Kimura, Katsumasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We present a satisfiability based multi-clock path analysis method. Multi-clock paths are paths between registers where the propagation of signals can use more than 1 clock cycle. Multi-clock path analysis is important in deciding proper clock frequency and for logic optimization. At present, we only have methods based on state traversal which can be applied to medium sized circuits. In the paper we propose a new multi-clock path analysis method based on propositional satisfiability (SAT). The method reduces path analysis problems to SAT problems by converting the time-expanded multi-level circuit to CNF formula, and improves the size of applicable circuits. We introduce heuristics on converting multi-level circuits to CNF formulae to reduce the size of the formula and the time consumed by SAT procedure. We have applied our method to ISCAS89 benchmarks and other sample circuits. Experimental results show the improvement on the applicable size of circuits by our method. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Timing Verification / Maximum Delay Analysis / Multiple Clock Operations / Propositional Satisfiability |
| Paper # | VLD99-82 |
| Date of Issue |
| Conference Information | |
| Committee | VLD |
|---|---|
| Conference Date | 1999/11/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | VLSI Design Technologies (VLD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Multi-Clock Path Analysis Based on Propositional Satisfiability |
| Sub Title (in English) | |
| Keyword(1) | Timing Verification |
| Keyword(2) | Maximum Delay Analysis |
| Keyword(3) | Multiple Clock Operations |
| Keyword(4) | Propositional Satisfiability |
| 1st Author's Name | Kazuhiro Nakamura |
| 1st Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology() |
| 2nd Author's Name | Shinji Maruoka |
| 2nd Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology |
| 3rd Author's Name | Shinji Kimura |
| 3rd Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology |
| 4th Author's Name | Katsumasa Watanabe |
| 4th Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology |
| Date | 1999/11/27 |
| Paper # | VLD99-82 |
| Volume (vol) | vol.99 |
| Number (no) | 475 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |