  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.
