Data Parallelism for Belief Propagation in Factor Graphs

• Nam Ma University of Southern California
• Yinglong Xia IBM Thomas J. Watson Research Center
• Viktor K. Prasanna University of Southern California

Resumo

We investigate data parallelism for belief propagation in a cyclic factor graphs on multicore/many core processors. Belief propagation is a key problem in exploring factor graphs, a probabilistic graphical model that has found applications in many domains. In this paper, we identify basic operations called node level primitives for updating the distribution tables in a factor graph. We develop algorithms for these primitives to explore data parallelism. We also propose a complete belief propagation algorithm to perform exact inference in such graphs. We implement the proposed algorithms on state-of-the-art multicore processors and show that the proposed algorithms exhibit good scalability using a representative set of factor graphs. On a 32-core Intel Nehalem-EX based system, we achieve 30× speedup for the primitives and 29× for the complete algorithm using factor graphs with large distribution tables.

Palavras-chave: Belief propagation, Parallel processing, Message systems, Program processors, Complexity theory, Inference algorithms, Random variables, data parallelism, belief propagation, multicore processors, factor graphs