Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization

Lu Zheng, Ole J. Mengshoel, Jike ChongUAI 2011

TL;DR

This paper tackles the computational bottleneck of belief propagation in Bayesian networks by parallelizing message computations on GPUs. They introduce a novel approach to compute each message in parallel, achieving significant speedups (up to 9.18x) on real-world Bayesian networks, especially those with larger separator potential tables.

What Problem Does This Paper Address?

Bayesian networks (BNs) are powerful tools for reasoning under uncertainty, and exact inference is often performed using belief propagation on junction trees. However, this process can be computationally intensive, especially for BNs with complex structures or variables with many states. The complexity arises from the size of "cliques" (groups of related variables) in the junction tree, which directly impacts the size of "potential tables" that need to be processed. When these tables become very large, the computation becomes a significant bottleneck, hindering real-time applications or use within iterative algorithms like the EM algorithm. This paper aims to alleviate this by accelerating the core message-passing operation on GPUs.

Methods

The authors' core contribution is a novel approach to parallelize the computation of each individual message passed between nodes in a junction tree. Standard belief propagation involves two main steps for message passing: marginalization (summing out variables) and scattering (updating a neighbor's potential table).

Their key innovation lies in how they parallelize these steps:

  • Index Mapping Tables: They introduce "index mapping tables" that pre-compute the relationships between elements in a clique's potential table and the elements in the separator's potential table. This allows each thread to efficiently access only the relevant data for its specific computation, avoiding redundant scanning of large tables.
  • Node-Level Parallelism: They leverage the massive parallelism of GPUs by assigning a separate thread to compute each element of a separator's potential table. This is particularly effective when the separator's potential table is large, as it offers many independent computations.
  • CUDA Implementation: The parallelized message computation is implemented as a CUDA kernel, allowing it to run on NVIDIA GPUs. They also explore optimizing thread block and grid sizes for different junction tree structures.

Datasets

The paper evaluates their approach on eight Bayesian networks from various problem domains, including "Mildew," "Diabetes," "Barley," "Pigs," "Munin2," "Munin3," "Munin4," and "Water." These networks are publicly available from http://bndg.cs.aau.dk/html/bayesian_networks.html. The paper does not introduce new benchmarks but uses these existing networks to demonstrate the performance of their parallel algorithm.

Key Insights and Ideas

  • Parallelizing the Atomic Operation: The most impactful insight is that parallelizing the computation of each individual message (the atomic operation of belief propagation) is a viable strategy. This allows for fine-grained parallelism that can be integrated into existing belief propagation algorithms without modification.
  • The Importance of Separator Size: The performance of their GPU-accelerated approach is strongly correlated with the size of the separator potential tables. Larger separators offer more independent computations, leading to higher speedups. This is a crucial finding for understanding where GPU acceleration is most beneficial.
  • Trade-offs in GPU Computing: The paper highlights the practical challenges of GPU computing, such as kernel invocation overhead and memory latency. These factors can limit the theoretical speedup achievable, especially for networks with many small separators or complex junction tree structures.
  • Memory Layout Matters: Optimizing the memory layout of the index mapping tables on the GPU significantly impacts performance by reducing bank conflicts and improving data access efficiency.

Key Results

  • Speedups: The implemented GPU parallelization achieved speedups ranging from 0.68x to 9.18x compared to a sequential CPU implementation.
  • Correlation with Separator Size: Networks with larger average separator potential tables (e.g., "Barley") showed significantly higher speedups than those with predominantly small separators (e.g., "Pigs").
  • Kernel Overhead: Kernel overhead can be a significant factor, especially for networks with many small separators, impacting overall performance. For "Munin3," overhead accounted for up to 36% of execution time.
  • Memory Layout Improvement: An advanced memory layout for mapping tables provided a 20%-30% improvement in overall speedup.

Limitations and Future Work

  • Performance on Small Separators: The paper acknowledges that their approach is less effective for junction trees with many small separators, where parallelism opportunities are limited and kernel overhead becomes more dominant.
  • Future Work: The authors propose improving performance for small separators by merging them into larger ones. They also suggest further research into optimizing parallel belief propagation over such modified junction trees. Additionally, exploring more advanced techniques to mitigate kernel overhead and memory latency would be beneficial.

Summary updated

BibTeX
@inproceedings{zheng2011belief,
  author = {Lu Zheng and Ole J. Mengshoel and Jike Chong},
  title = {{Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure