Scalable Belief Propagation via Relaxed Scheduling

Vitaly Aksenov, Dan Alistarh, Janne H. KorhonenNeurIPS 2020 · OpenReview

Overview

The ability to leverage large-scale hardware parallelism has been a key enabler for recent progress in machine learning. However, classic algorithms like Belief Propagation (BP)—a cornerstone for inference in graphical models—often prove hard to parallelize efficiently without losing convergence guarantees. This paper introduces a method to make BP run significantly faster on modern multi-core hardware. By replacing strict, bottleneck-prone priority queues with "relaxed schedulers" that allow for slight out-of-order execution, the authors achieve massive parallel scalability without sacrificing the algorithm's accuracy.

The Challenge of Scheduling in Belief Propagation

Belief Propagation is an iterative message-passing algorithm used to calculate probabilities in complex networks, such as those found in error-correcting codes or image processing.

Message passing in Belief Propagation

The primary challenge in scaling BP lies in scheduling these messages.

  • Synchronous Scheduling: You can update all messages at once. This is easy to parallelize but often slow to converge and prone to oscillation.
  • Priority-based Scheduling: You update the most "important" messages first. This converges much faster but is inherently sequential. In a parallel setting, the single priority queue used to track these messages becomes a massive contention bottleneck—every processor fights for access to the same list, destroying performance.

The Solution: Relaxed Scheduling

To overcome this bottleneck, the authors propose Relaxed Priority-based Belief Propagation. Instead of relying on a single, perfect priority queue, they utilize a relaxed scheduler known as a Multiqueue.

Imagine that instead of one long line at a bank, there are 70 separate lines. To get a task, a processor picks two lines at random and takes the most important task from the better of the two. This relaxation means the system doesn't always process the absolute most important message next, but it is guaranteed to be among the most important.

Crucially, the authors provide mathematical analysis showing that on tree-like structures, this relaxed approach only adds a negligible amount of "wasted" updates while allowing all processors to work concurrently at full speed.

Experimental Setup

The researchers evaluated their approach on four distinct types of Markov Random Fields (MRFs):

  1. Binary Tree: A massive tree with $10^7$ nodes.
  2. Ising Model: A $1000 \times 1000$ grid commonly used in physics and image analysis.
  3. Potts Model: A more complex $1000 \times 1000$ grid.
  4. LDPC Code: A $(3, 6)$-Low-Density Parity Check code (size $3 \times 10^5$) used in high-speed communications.

They compared their relaxed versions against standard synchronous BP and previous state-of-the-art parallel methods like "Residual Splash."

Key Results and Performance

The results, tested on a 72-core Intel Xeon server, demonstrate that trading a slight loss in strict ordering for massive parallelism is highly effective.

Running time and update efficiency across different process counts
  • Speedups: On the Ising grid model, the relaxed approach was 14x faster than the sequential version and significantly outperformed previous parallel heuristics.
  • Efficiency: In terms of wall-clock time, the relaxed residual BP consistently beat synchronous BP, even though synchronous BP is theoretically "perfectly" parallel. While intuition suggests out-of-order updates might lead to massive amounts of redundant calculations, the empirical data shows the number of extra updates remains minimal.
  • Convergence: On the Potts model, some traditional non-relaxed parallel methods failed to converge entirely, whereas the relaxed implementation converged reliably and quickly.
  • Ease of Use: Unlike previous parallel BP variants that require users to tune "splash sizes" or "distance parameters," the relaxed residual BP works out of the box with almost no parameter fiddling.

Limitations and Future Work

While the algorithm performs excellently on loopy graphs (like grids) in practice, the formal mathematical proofs for why this works are currently limited to trees. Expanding this theory to loopy graphs remains an open challenge.

Looking forward, the authors suggest moving beyond a single multi-core machine to massively parallel distributed systems (clusters of many machines), where communication delays make relaxed scheduling even more critical. Furthermore, the "relaxed priority" framework could likely be applied to a wider family of iterative machine learning algorithms that currently struggle with parallelization.

Summary updated

Abstract

pre><code>The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers, which reduce parallelization overheads, in this context. We investigate the overheads of relaxation analytically, and present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.
BibTeX
@inproceedings{aksenov2020scalable,
  author = {Vitaly Aksenov and Dan Alistarh and Janne H. Korhonen},
  title = {{Scalable Belief Propagation via Relaxed Scheduling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=Pf-JpOsH6JJ},
}
Figure