Parallel Splash Belief Propagation
Abstract
As computer architectures transition towards exponentially increasing parallelism we are forced to adopt parallelism at a fundamental level in the design of machine learning algorithms. In this paper we focus on parallel graphical model inference. We demonstrate that the natural, synchronous parallelization of belief propagation is highly inefficient. By bounding the achievable parallel performance in chain graphical models we develop a theoretical understanding of the parallel limitations of belief propagation. We then provide a new parallel belief propagation algorithm which achieves optimal performance. Using several challenging real-world tasks, we empirically evaluate the performance of our algorithm on large cyclic graphical models where we achieve near linear parallel scaling and outperform alternative algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 2010
- Accession Number
- ADA527892
Entities
People
- Carlos Guestrin
- Joseph M Gonzalez
- Yucheng Low
Organizations
- Carnegie Mellon University