Skip to main content
Article
Exploring Multiple Dimensions of Parallelism in Junction Tree Message Passing
Models for Spatial, Temporal and Network Data -- A UAI Application Workshop (2013)
  • Lu Zheng, Carnegie Mellon University
  • Ole J Mengshoel, Carnegie Mellon University
Abstract
Belief propagation over junction trees is known to be computationally challenging in the general case. One way of addressing this computational challenge is to use node-level parallel computing, and parallelize the computation associated with each separator potential table cell. However, this approach is not efficient for junction trees that mainly contain small separators. In this paper, we analyze this problem, and address it by studying a new dimension of node-level parallelism, namely arithmetic parallelism. In addition, on the graph level, we use a clique merging technique to further adapt junction trees to parallel computing platforms. We apply our parallel approach to both marginal and most probable explanation (MPE) inference in junction trees. In experiments with a Graphics Processing Unit (GPU), we obtain for marginal inference an average speedup of 5.54x and a maximum speedup of 11.94x; speedups for MPE inference are similar.
Keywords
  • belief propagation,
  • parallel computing,
  • GPUs,
  • junction trees,
  • Bayesian networks
Publication Date
July, 2013
Publisher Statement
@inproceedings{zheng13exploring,
 author = {Zheng, L. and Mengshoel, O. J.},
 title     = {Exploring Multiple Dimensions of Parallelism in Junction
               Tree Message Passing},
 booktitle = {Proc. of UAI Application Workshops}, 
 year = {2013},
 month  = {July},
 address = {Bellevue, WA}
}
Citation Information
Lu Zheng and Ole J Mengshoel. "Exploring Multiple Dimensions of Parallelism in Junction Tree Message Passing" Models for Spatial, Temporal and Network Data -- A UAI Application Workshop (2013)
Available at: http://works.bepress.com/ole_mengshoel/42/