Exact Inference on Manycore Processors using Pointer Jumping

N. Ma, Y. Xia, and V. Prasanna (USA)


Exact Inference, Junction Tree, Pointer Jumping, Manycore System


Exact inference is a key problem in exploring probabilis tic graphical models. Most parallel algorithms for exact inference explore data and structural parallelism. These al gorithms result in limited performance if the input model offers limited data and structural parallelism. In this pa per, we study a pointer jumping based method on manycore systems for exact inference in junction trees. We adapt the technique for both evidence collection and evidence distri bution so as to ef´Čüciently process junction trees with mul tiple evidence cliques. We also study the impact of junc tion tree topology on evidence collection. We implement the proposed method on state-of-the-art manycore systems. Experimental results show that, for junction trees with lim ited data and structural parallelism, pointer jumping is well suited to accelerate exact inference on manycore systems.

Important Links:

Go Back