| 講演名 | 2005-12-02 時間付き信号遷移グラフの効率的縮約について(VLSIの設計/検証/テスト及び一般(デザインガイア)) 米田 友洋 /, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 非同期式回路の論理合成を効率良く行うため, 分割に基づく論理合成法が提案されている.この手法では, 各出力毎に十分な数の入力信号集合を求め, それ以外の信号に関するトランジションを(可能ならば)削除することにより, 仕様となる信号遷移グラフを縮約する.これにより, 探索する状態空間を削減し, 効率的に論理合成を行うことができる.この手法を有限幅遅延を持つ非同期式回路の合成に拡張するには, 時間付き信号遷移グラフを縮約する必要があるが, 時間なしの場合と同程度に縮約を行おうとすると, 必要な時間情報が失われ, 最適な回路が合成できなくなる.一方, 時間情報を完全に保存しようとすると, 非常に限定的な縮約しか行えず, 分割に基づく論理合成手法の長所が失われる.そこで, 本稿では, 合成される回路の最適性を考慮し, それに影響を与えないトランジションのみを削除するアルゴリズムを提案する.実験結果から, 提案手法は各種のベンチマーク回路に問題なく適用できること, および, 比較的大きな回路では非常に効果的に時間付き信号遷移グラフの縮約が行えることが分かった. |
| 抄録(英) | In the decomposition based synthesis method, for each output signal, an input signal set sufficient to synthesize a circuit for the output is first obtained, and the signal transition graph (STG) used as a specification is contracted to include only transitions on this input signal set and the output, from which the circuit for the output is synthesized efficiently. In order to extend this approach for the timed circuit synthesis, the contraction algorithm needs to handle timed STGs. A simple extension of the untimed contraction algorithm, however, loses several timing information, causing it to synthesize non-optimal circuits. On the other hand, an exact contraction algorithm that preserves the timing information precisely can be applied to only a small class of transitions, which degrades the performance of the decomposition based method. This paper proposes a way to contract timed STGs effectively without losing the optimality of the synthesized circuits. According to the experimental results, the proposed method can handle a wide variety of benchmark circuits successfully, and for large specifications, a significant reduction in the size of STGs is obtained by the proposed contraction method with almost no redundant gates. |
| キーワード(和) | 縮約 / 時間付き信号遷移グラフ / 有限幅遅延非同期式回路 / 分割に基づく論理合成 |
| キーワード(英) | Contraction / timed signal transition graphs / timed circuits / decomposition based logic synthesis |
| 資料番号 | VLD2005-86,ICD2005-181,DC2005-63 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2005/11/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 時間付き信号遷移グラフの効率的縮約について(VLSIの設計/検証/テスト及び一般(デザインガイア)) |
| サブタイトル（和） | |
| タイトル（英） | Effective Contraction of Timed STGs for Decomposition Based Timed Circuit Synthesis |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 縮約 / Contraction |
| キーワード(2)（和/英） | 時間付き信号遷移グラフ / timed signal transition graphs |
| キーワード(3)（和/英） | 有限幅遅延非同期式回路 / timed circuits |
| キーワード(4)（和/英） | 分割に基づく論理合成 / decomposition based logic synthesis |
| 第 1 著者 氏名（和/英） | 米田 友洋 / / Tomohiro YONEDA |
| 第 1 著者 所属（和/英） | 国立情報学研究所 / National Institute of Informatics |
| 発表年月日 | 2005-12-02 |
| 資料番号 | VLD2005-86,ICD2005-181,DC2005-63 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 443 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |