DocumentCode :
167626
Title :
Wait-Free Primitives for Initializing Bayesian Network Structure Learning on Multicore Processors
Author :
Hsuan-Yi Chu ; Yinglong Xia ; Panangadan, Anand ; Prasanna, Viktor K.
Author_Institution :
Univ. of Southern California, Los Angeles, CA, USA
fYear :
2014
fDate :
19-23 May 2014
Firstpage :
1602
Lastpage :
1611
Abstract :
Structure learning is a key problem in using Bayesian networks for data mining tasks but its computation complexity increases dramatically with the number of features in the dataset. Thus, it is computationally intractable to extend structure learning to large networks without using a scalable parallel approach. This work explores computation primitives to parallelize the first phase of Cheng et al.´s (Artificial Intelligence, 137(1-2):43-90, 2002) Bayesian network structure learning algorithm. The proposed primitives are highly suitable for multithreading architectures. Firstly, we propose a wait-free table construction primitive for building potential tables from the training data in parallel. Notably, this primitive allows multiple cores to update a potential table simultaneously without appealing to any lock operation, allowing all cores to be fully utilized. Secondly, the marginalization primitive is proposed to enable efficient statistics tests to be performed on all pairs of variables in the learning algorithm. These primitives are quantitatively evaluated on a 32-core platform and the experiment results show 23:5× speedup compared to a single thread implementation.
Keywords :
belief networks; data mining; multi-threading; statistical testing; Bayesian network structure learning; computation complexity; data mining tasks; marginalization primitive; multicore processors; multithreading architectures; statistics testing; wait-free table construction primitive; Bayes methods; Complexity theory; Mutual information; Probability distribution; Program processors; Random variables; Training data;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International
Conference_Location :
Phoenix, AZ
Print_ISBN :
978-1-4799-4117-9
Type :
conf
DOI :
10.1109/IPDPSW.2014.179
Filename :
6969568
Link To Document :
بازگشت