閾値関数のBDDの並列実装

• Item type: SIG Technical Reports(1)
• 公開日: 1995-08-24
• タイトル: 閾値関数のBDDの並列実装
• タイトル / 言語: en
• タイトル: PARALLEL CONSTRUCTION OF A BDD REPRESENTING A THRESHOLD FUNCTION
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, the University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, the University of Tokyo
• 著者名: 丹羽, 純平; 今井, 浩
• 著者名(英): Junpei, Niwa; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Akersによって提案された二分決定グラフ(D)は、論理関数を表現するDACである。BryantによるBDD間の論理演算を効率良く行なうアルゴリズムにより、BDDはVLSI CAD等の様々な分野で使われるようになった。近年では組合せ問題にも応用されるようになった。本稿では、閾値関数を表すBDDを構築する新しいアルゴリズムを提案する。動的計画法を用いた前処理を行なった後でBDDを出力サイズに比例した計算量でトップダウンに構築するものである。我々は更に上述のアルゴリズムを並列化してそれをAP1000＋上で実装し、実験により既存のアルゴリズムで構築できなかったサイズのBDDを迅速に構築できることを示した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A Binary Decision Diagram (BDD), proposed by Akers, is a DAG representing a boolean function. Through the development of the efficient algorithms of boolean operations on BDDs Bryant, it has been used in various fields, such as VLSI CAD. Recently it has been applied to combinatorics. We propose a new algorithm of constructing a BDD representing a threshold function. After a preprocessing stage using a dynamic programing, we construct the BDD in a top-down manner with time proportional to the output size. Furthermore we parallelize the algorithm and implement it on AP1000+, and the experiment shows that the BDD which could not be constructed by the existing algorithm is constructed quickly.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 1995, 号 81(1995-HPC-057), p. 73-78, 発行日 1995-08-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会