Distributed Evidence Propagation in Junction Trees - Xia, Yinglong; Prasanna, Viktor K. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2010)
Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. In this paper, we propose a novel approach for evidence propagation on clusters. We decompose a junction tree into a set of sub trees, and then perform evidence propagation in the sub trees in parallel. The partially updated sub trees are merged after evidence collection. In addition, we propose a technique to explore tradeoff between overhead due to startup latency of message passing and bandwidth utilization efficiency. We implemented the proposed method on state-of-the-art clusters using MPI. Experimental results show that the proposed method exhibits superior performance compared with the baseline methods.