DocumentCode :
3145619
Title :
Self-Adaptive Evidence Propagation on Manycore Processors
Author :
Xia, Yinglong ; Prasanna, Viktor K.
Author_Institution :
T.J. Watson Res. Center, IBM, Yorktown Heights, NY, USA
fYear :
2011
fDate :
16-20 May 2011
Firstpage :
1407
Lastpage :
1416
Abstract :
Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. Evidence propagation is essentially a series of computations between the potential tables in cliques and separators of a given junction tree. In real applications, the size of the potential tables varies dramatically. Thus, to achieve scalability over dozens of threads remains a fundamental challenge for evidence propagation on many core processors. In this paper, we propose a self-adaptive method for evidence propagation on many core processors. Given an arbitrary junction tree, we convert evidence propagation in the junction tree into a task dependency graph. The proposed self-adaptive scheduler dynamically adjusts the number of threads for scheduling or executing tasks according to the task dependency graph. Such a self-adaptability prevents the schedulers being too idle or too busy during the scheduling process. We implemented the proposed method on the Sun UltraSPARC T2 (Niagara 2) platform that supports up to 64 hardware threads. Through a set of experiments, we show that the proposed method scales well with respect to various input junction trees and exhibits superior performance when compared with several baseline methods for evidence propagation.
Keywords :
computer graphics; inference mechanisms; multi-threading; probability; processor scheduling; trees (mathematics); Sun UltraSPARC T2 platform; arbitrary junction tree; hardware threads; inference mechanism; manycore processor; probabilistic graphical model; scheduling process; self-adaptive evidence propagation; self-adaptive method; self-adaptive scheduler; task dependency graph; Bayesian methods; Instruction sets; Junctions; Multicore processing; Processor scheduling; Random variables;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
ISSN :
1530-2075
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
Type :
conf
DOI :
10.1109/IPDPS.2011.298
Filename :
6008995
Link To Document :
بازگشت