Message Scheduling for Performant, Many-Core Belief Propagation
This work addresses performance bottlenecks in BP for applications like computer vision and error-correcting codes, offering an incremental improvement in scheduling for many-core systems.
The paper tackles the challenge of improving Belief Propagation (BP) performance on GPUs by addressing message scheduling, which affects speed and convergence tradeoffs, and introduces Randomized BP (RnBP) that outperforms existing methods on GPU benchmarks.
Belief Propagation (BP) is a message-passing algorithm for approximate inference over Probabilistic Graphical Models (PGMs), finding many applications such as computer vision, error-correcting codes, and protein-folding. While general, the convergence and speed of the algorithm has limited its practical use on difficult inference problems. As an algorithm that is highly amenable to parallelization, many-core Graphical Processing Units (GPUs) could significantly improve BP performance. Improving BP through many-core systems is non-trivial: the scheduling of messages in the algorithm strongly affects performance. We present a study of message scheduling for BP on GPUs. We demonstrate that BP exhibits a tradeoff between speed and convergence based on parallelism and show that existing message schedulings are not able to utilize this tradeoff. To this end, we present a novel randomized message scheduling approach, Randomized BP (RnBP), which outperforms existing methods on the GPU.