Pointer Jumping for Exact Inference on Manycore Systems

We study the performance of a pointer jumping based exact inference algorithm for a special type of junction trees – a chain of cliques. Many traditional methods for exact inference result in unsatisfactory performance for such a type of junction trees due to limited parallelism. A pointer jumping based algorithm helps explore independent operations that can be run in parallel. Our analysis on the performance of the algorithm shows that a large number of processors with shared memory are particularly suitable for exact inference in a chain of cliques. The Intel® Manycore Testing Lab gives us an opportunity to experimentally evaluate our algorithm on a real manycore system – a 32-core Intel® Nehalem-EX based system. The experimental results show that the algorithm scales well with the number of cores, and that the algorithm achieves speedup with respect to the sequential algorithm when the number of cores is sufficiently large.

There are downloads available under the Creative Commons License license. Download Now

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.