講演名 | 1998/7/31 ZBDDによる二分決定グラフの非明示的表現 山内 仁, 高橋 浩光, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 二分決定グラフ(Binary Decision Diagrams;以下BDD)は, 論理関数を計算機上で効率良く表現する方法として広く用いられているが, 近年の回路の大規模化により, BDDでも記憶領域が不足するような論理関数がしばしば出現し, 問題となっている.これに対して, 著者らはBDDの非明示的表現法(implicit representation of BDDs;以下iBDD)を提案し, さらにその演算効率を向上させる手法を提案した.しかしながら, 演算効率の向上と引き替えに記憶量が増大していた.本稿では, iBDDの内部表現にBDDではなくゼロサプレスBDDを用いることにより, 記憶量の削減をはかる手法を提案する.MCNC, ISCAS85の両ベンチマークに対する実験により, BDDを内部表現に用いる従来手法と比較して記憶量が60-70%に削減されるとともに, 演算時間が短縮できることが確かめられた. |
抄録(英) | Binary Decision Diagrams (BDD) is used on computer aided design of VLSI, because of that's goodness of memory spacing on computers for representing boolean functions. Recently, though, big size boolean functions such that are not able to be represented by BDD appear on VLSI design. We presented an implicit representation of BDDs (iBDD), and its improvement representation method to manipulate faster. This improvement was achieved fast manipulation but required more memory for representation. In this paper, we change internal representation of iBDD from BDD to zero-supressed BDD which is effective to represent combination sets that BDD. Experimental results on MCNC and ISCAS85 benchmarks says this method requires only 60-70% memories than formar method and reduces manipulation time. |
キーワード(和) | 二分決定グラフ / ゼロサプレスBDD / 非明示的表現 / 論理関数 / 計算機援用設計 |
キーワード(英) | BDD / zero-supressed BDD / implicit representation / boolean function / computer aided design |
資料番号 | VLD98-36 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 1998/7/31(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | ZBDDによる二分決定グラフの非明示的表現 |
サブタイトル(和) | |
タイトル(英) | Implicit Representation of Binary Decision Diagrams with Zero-Suppressed BDD |
サブタイトル(和) | |
キーワード(1)(和/英) | 二分決定グラフ / BDD |
キーワード(2)(和/英) | ゼロサプレスBDD / zero-supressed BDD |
キーワード(3)(和/英) | 非明示的表現 / implicit representation |
キーワード(4)(和/英) | 論理関数 / boolean function |
キーワード(5)(和/英) | 計算機援用設計 / computer aided design |
第 1 著者 氏名(和/英) | 山内 仁 / Hitoshi Yamauchi |
第 1 著者 所属(和/英) | 岡山県立大学情報工学部情報通信工学科 Department of Communication Engineering, Faculty of Computer Science and System Engineering, Okayama Prefectural University |
第 2 著者 氏名(和/英) | 高橋 浩光 / Hiromitsu Takahashi |
第 2 著者 所属(和/英) | 岡山県立大学情報工学部情報通信工学科 Department of Communication Engineering, Faculty of Computer Science and System Engineering, Okayama Prefectural University |
発表年月日 | 1998/7/31 |
資料番号 | VLD98-36 |
巻番号(vol) | vol.98 |
号番号(no) | 232 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |