From the January 2010 Issue...

Scalable Node-Level Computation Kernels for Parallel Exact Inference

By Yinglong Xia and Viktor K. Prasanna

In this paper, we investigate data parallelism in exact inference with respect to arbitrary junction trees. Exact inference is a key problem in exploring probabilistic graphical models, where the computation complexity increases dramatically with clique width and the number of states of random variables. We study potential table representation and scalable algorithms for node-level primitives. Based on such node-level primitives, we propose computation kernels for evidence collection and evidence distribution. A data parallel algorithm for exact inference is presented using the proposed computation kernels.

View the PDF of this article       View this issue in the digital library