GUI並列性を用いたZBDD圧縮多重線形関数のより高速な評価

MINATO Shin-ichi; ONSJOE Mikael; WATANABE Osamu

文献

J-GLOBAL ID：201102263874124541 整理番号：11A0545840

GUI並列性を用いたZBDD圧縮多重線形関数のより高速な評価

Faster Evaluation of ZBDD Compressed Multi-Linear Functions with GPU Parallelism

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=11A0545840&from=J-GLOBAL&jstjournalNo=U0055A") }}

著者 (3件)： , ,
資料名：
号： 274 ページ： C-274 (WEB ONLY) 発行年： 2011年01月
JST資料番号： U0055A ISSN： 1342-2812 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

ZBDD(ゼロ抑止二値ディシジョンダイアグラム)の圧縮系として表現される大規模Bayesネットワークでの限界確率を表現する多重線形関数を評価することを目的として,本論文では,GUI並列性を用いたZBDD圧縮多重線形関数のより高速な評価手法を提案した。GPUプログラムの中にZBDD圧縮型MLF(多重線形関数)の変換手法を具体的に示し,各種BayesネットワークMLFに対するZBDD解析後に得られたレベルのサイズ上のヒストグラムを示した。次にカスタムCPU ZBDDコンパイラを取り上げて論じ,ある数の親を持つノードがどの程度存在するのかの結果を各ネットワークに対して示した。評価実験を行い,いくつかの大規模ネットワークに対し,Tesla C1060 GPU実装では,最適化単一スレッド実装(2.5GHz AMD Phenom CPU)よりも少なくとも6倍高速化されており,最適化されていないgccバージョンよりも16倍高速化されていることを示した。具体的にはZBDDにおけるノード数と処理時間の関係を示した。またGPU上でのさらなる性能向上方式を示し,その結果を与えた。

, , , , , , , , , ,
, ,

専用演算制御装置 , 人間機械系 , グラフ理論基礎

引用文献 (5件)：

Bayesian Network Repository, http://www.cs.huji.ac.il/ galel/Repository/
S. Minato,“Zero-suppressed BDDs for set manipulation in combinatorial problems, in Proc. of 30th ACM/IEEE Design Automation Conference (DAC’93), pp. 272-277, Jun.1993.
S. Minato, K. Satoh, and T. Sato, Compiling Bayesian networks by symbolic probability calculation based on Zero-suppressed BDDs, in Proc. of 20th International Joint Conference of Arti cial Intelligence (IJCAI-2007), pp. 2550-2555. Jan.2007.
Nvidia: CUDA Programming Guide, ver.2.3.1., http://www.nvidia.com/object/cuda develop.html, Aug 26(2009).
W. Takahashi and S. Minato, Synthesis of fast calculation programs from ZDDs for representing Bayesian networks and its evaluation, in Proc. IEICE/IPSJ Forum on Information technology 2010, D-009, Vol.2, pp. 411-414, Sep. 2010 (in Japanese).

, , ,

前のページに戻る