Exact Inference on Manycore Processors using Pointer Jumping

Ning Ma, Yinglong Xia, Victor K. Prasanna2010 · DOI

TL;DR

This paper introduces a novel parallel algorithm for exact inference in probabilistic graphical models, specifically targeting manycore processors. By adapting the "pointer jumping" technique to junction trees, the authors achieve efficient inference even for models with limited inherent parallelism, outperforming existing methods in certain scenarios.

What Problem Does This Paper Address?

Probabilistic graphical models, like Bayesian networks, are powerful tools for representing complex systems and reasoning under uncertainty. However, performing "exact inference" – calculating the probability of certain events given observed evidence – is computationally expensive, often NP-hard. While many parallel algorithms exist, they typically rely on exploiting either data parallelism (parallelizing computations within a single clique) or structural parallelism (parallelizing computations across independent cliques). These approaches struggle when the graphical model lacks significant data or structural parallelism, leading to limited performance gains. This paper addresses this limitation by proposing a parallel inference method that can effectively handle models with limited parallelism.

Methods

The core contribution of this paper is the adaptation of the "pointer jumping" technique for exact inference in junction trees on manycore systems. The standard approach for exact inference in Bayesian networks involves converting the network into a junction tree and then performing two passes: evidence collection (from leaves to root) and evidence distribution (from root to leaves).

The authors adapt pointer jumping to both these passes. Pointer jumping, originally used for list processing, allows for logarithmic time operations by repeatedly doubling the "jump" distance. In this context, it's used to efficiently propagate evidence across the junction tree. Specifically, they modify the evidence propagation formulas to work with pointer jumping, allowing cliques to receive evidence from ancestors multiple levels up in a logarithmic number of iterations. This method is designed to be effective even when structural parallelism is scarce, as it focuses on efficiently updating each clique by leveraging the pointer jumping mechanism.

Datasets

Not discussed in the paper. The paper focuses on evaluating the algorithm's performance on synthetically generated junction tree topologies.

Key Insights and Ideas

  • Pointer Jumping for Inference: The most significant insight is the successful adaptation of pointer jumping, a technique typically used for list operations, to the complex domain of probabilistic inference in junction trees. This opens up new avenues for parallelizing inference.
  • Handling Limited Parallelism: The pointer jumping approach demonstrates a clear advantage for junction trees that lack substantial data or structural parallelism, a scenario where traditional parallel methods falter.
  • Topology Matters: The performance of the pointer jumping algorithm, particularly during evidence collection, is shown to be sensitive to the junction tree's topology. "Slim trees" (where width is less than height) are particularly interesting for evaluating this method.
  • Trade-offs in Parallelism: The paper highlights the trade-offs between different types of parallelism. While structural parallelism is beneficial for some algorithms (like SEI), pointer jumping offers an alternative when it's limited.

Key Results

The paper presents experimental results on 32-core Intel Nehalem-EX and 24-core AMD Magny-Cours systems, focusing on the Nehalem-EX.

  • Chains: For chain-like junction trees (minimal structural parallelism), the proposed pointer jumping algorithm scaled very well with the number of cores, eventually outperforming the baseline "scheduling-based exact inference" (SEI) algorithm, especially at higher core counts.
  • Balanced Trees: For balanced trees with significant structural parallelism, both the proposed algorithm and SEI scaled well. SEI showed slightly better scalability, likely due to its more effective load balancing in this scenario.
  • Slim Trees:
    • Slim Tree 1: The proposed algorithm scaled well, with performance less affected by the parameter 'b' (controlling structural parallelism) compared to SEI.
  • Slim Tree 2: Increasing 'b' led to load imbalance in the proposed algorithm, causing SEI to perform better at higher 'b' values. However, with small 'b' and many cores, the proposed algorithm was faster.
  • Slim Tree 3: The proposed algorithm performed best when 'b' was small, again outperforming SEI when sufficient cores were available.

Overall, the proposed algorithm demonstrates superior scalability and performance in scenarios with limited structural parallelism, making it a valuable approach for manycore systems.

Limitations and Future Work

  • Load Balancing: The authors acknowledge that load imbalance can occur during evidence collection in the proposed algorithm, especially when updating cliques with many children. They plan to improve load balancing across threads.
  • Hybrid Approach: They intend to extend the algorithm by integrating methods that explore structural parallelism and data parallelism, allowing the system to automatically choose the best approach for a given junction tree.
  • Clique Update Parallelization: Further investigation into parallelizing the clique update process itself (specifically, the propagation from children to parents) is planned.
  • Real-world Models: The experiments were conducted on synthetically generated trees. Future work could involve evaluating the algorithm on real-world Bayesian networks.

Summary updated

Abstract

Exact inference is a key problem in exploring probabilistic graphical models. Most parallel algorithms for exact inference explore data and structural parallelism. These algorithms result in limited performance if the input model offers limited data and structural parallelism. In this paper, we study a pointer jumping based method on manycore systems for exact inference in junction trees. We adapt the technique for both evidence collection and evidence distribution so as to efficiently process junction trees with multiple evidence cliques. We also study the impact of junction tree topology on evidence collection. We implement the proposed method on state-of-the-art manycore systems. Experimental results show that, for junction trees with limited data and structural parallelism, pointer jumping is well suited to accelerate exact inference on manycore systems.
BibTeX
@misc{ma2010exact,
  author = {Ning Ma and Yinglong Xia and Victor K. Prasanna},
  title = {{Exact Inference on Manycore Processors using Pointer Jumping}},
  year = {2010},
  doi = {10.2316/p.2010.724-064},
}
Figure