ヘテロジニアスMDDにおける平均パス長の最小化法について

• Item type: SIG Technical Reports(1)
• 公開日: 2003-11-27
• タイトル: ヘテロジニアスMDDにおける平均パス長の最小化法について
• タイトル / 言語: en
• タイトル: Minimization of Average Path Lengths for Heterogeneous MDDs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州工業大学大学院情報システム専攻
• 著者所属: 九州工業大学電子情報工学科／九州工業大学マイクロ化総合技術センタ
• 著者所属(英): en
• 著者所属(英): Graduate school of Computer Science and Information System, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Electronics, Kyushu Institute of Technology/Center for Microelectronic Systems, Kyushu Institute of Technology
• 著者名: 永山, 忍; 笹尾, 勤
• 著者名(英): Shinobu, Nagayama; Tsutomu, Sasao
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，ヘテロジニアスMDD（Multi-valued Decision Diagram）の平均パス長最小化アルゴリズムおよび平均パス長縮小のための発見的アルゴリズムを提案する．ヘテロジニアスMDDでは多値変数はそれぞれ異なる変域を持ってよく，二値変数の分割を考慮することによって，論理関数を短い平均パス長でコンパクトに表現できる．ベンチマーク関数を用いた実験により，ヘテロジニアスMDDではメモリ量を増やすことなく，ROBDD（Reduced Ordered Binary Decision Diagram）に比べ，平均パス長を約半分に縮小できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an exact and a heuristic minimization algorithms of average path lengths (APLs) for heterogeneous multi-valued decision diagrams (MDDs). In a heterogeneous MDD, each multi-valued variable can take different domain. To represent a binary logic function using a heterogeneous MDD, we partition the binary variables into groups, and treat them as multi-valued variables. By considering partitions of binary variables, we can obtain heterogeneous MDDs that represent logic functions more compactly and have smaller APLs than reduced ordered binary decision diagrams (ROBDDs). Experimental results usign 21 benchmark functions show that the APLs of the heterogeneous MDDs can be reduced into a half of corresponding ROBDDs, on average, without increasing the memory size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2003, 号 120(2003-SLDM-112), p. 253-258, 発行日 2003-11-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会