/ プログラム/ 発表一覧/ 著者一覧企業展示一覧/ jsai2015ホーム /

1E2-4 BDD簡約化アルゴリズムの並列化

*セッションの無断動画配信はご遠慮下さい。

Tweet #jsai2015 このエントリーをはてなブックマークに追加

05月30日(Sat) 10:20〜11:40 E会場(5F北-中講義室 (593))
1E2 「推論・探索」

演題番号1E2-4
題目BDD簡約化アルゴリズムの並列化
著者竹内 聖悟(JST ERATO 湊離散構造処理系プロジェクト)
藤本 武彦(北海道大学大学院 情報科学研究科)
安田 宜仁(JST ERATO)
湊 真一(北海道大学 大学院 情報科学研究科)
時間05月30日(Sat) 11:20〜11:40
概要圧縮データ構造のBDD,ZDDは圧縮したまま演算が可能だが、そのためには唯一性が必要である。そのための簡約化アルゴリズムがKnuthにより提案されており、本稿では簡約化の新しい並列化手法を提案する。不完全な簡約化を並列に行い、小さくしたBDD, ZDDを前処理と並行して処理する。クリークが並行するグラフ上での単純経路を表すZDDに対して実験し、8スレッドで4倍の高速化を得た。
論文PDFファイル