Parallel Evidence Propagation on Multicore Processors

In this paper designs and implements an efficient technique for parallel evidence propagation on state-of-the-art multicore processor systems. Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. This paper proposes a rerooting algorithm to minimize the critical path in evidence propagation. The rerooted junction tree is used to construct a Directed Acyclic Graph (DAG) where each node represents a computation task for evidence propagation. This paper develops a collaborative scheduler to dynamically allocate the tasks to the cores of the processors. In addition, this paper integrates a task partitioning module in the scheduler to partition large tasks so as to achieve load balance across the cores.