Task Parallel Implementation of Belief Propagation in Factor Graphs

Factor graphs have been increasingly used as probabilistic graphical models. Belief propagation is a prominent algorithm for inference in factor graphs. Due to the high complexity of inference, parallel techniques for belief propagation are needed. In this paper, we explore task parallelism for belief propagation in an acyclic factor graph. Our approach consists of building a task dependency graph based on the input factor graph and then using a dynamic task scheduler to exploit task parallelism. We conducted experiments on a state-of-the-art multi-core system using a variety of acyclic factor graphs. The experimental results show the efficiency and scalability of the proposed approach with a 37x speedup on a 40-core system.