| 講演名 | 1999/11/27 充足可能性判定手法に基づいたマルチクロックパス解析 中村 一博, 丸岡 新治, 木村 晋二, 渡邊 勝正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 通常,順序回路のタイミング検証は,レジスタ間の信号伝搬が全て1クロックであるという仮定のもとで行われるが,2クロックで伝搬しても良い経路(マルチクロックパス)の存在が知られており,そのような経路を特定してタイミング検証を行うことが重要である.これまでに,記号実行を用いたマルチクロックパスの解析手法が提案されているが,大規模回路への適用が困難であった.本論文では,論理式の充足可能性を判定するSATアルゴリズムの応用によりマルチクロックパス解析を行う手法を提案する, |
| 抄録(英) | 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. |
| キーワード(和) | 論理回路のタイミング検証 / 最大遅延解析 / マルチクロック演算 / 充足可能性判定 |
| キーワード(英) | Timing Verification / Maximum Delay Analysis / Multiple Clock Operations / Propositional Satisfiability |
| 資料番号 | VLD99-82 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1999/11/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 充足可能性判定手法に基づいたマルチクロックパス解析 |
| サブタイトル（和） | |
| タイトル（英） | Multi-Clock Path Analysis Based on Propositional Satisfiability |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 論理回路のタイミング検証 / Timing Verification |
| キーワード(2)（和/英） | 最大遅延解析 / Maximum Delay Analysis |
| キーワード(3)（和/英） | マルチクロック演算 / Multiple Clock Operations |
| キーワード(4)（和/英） | 充足可能性判定 / Propositional Satisfiability |
| 第 1 著者 氏名（和/英） | 中村 一博 / Kazuhiro Nakamura |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 丸岡 新治 / Shinji Maruoka |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 木村 晋二 / Shinji Kimura |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 4 著者 氏名（和/英） | 渡邊 勝正 / Katsumasa Watanabe |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 発表年月日 | 1999/11/27 |
| 資料番号 | VLD99-82 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 475 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |