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
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;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.298