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