Parallel Exact Inference on a CPU-GPGPU Heterogenous System
Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, USA
39th International Conference on Parallel Processing (ICPP), 2010
@conference{jeon2010parallel,
title={Parallel Exact Inference on a CPU-GPGPU Heterogenous System},
author={Jeon, H. and Xia, Y. and Prasanna, V.K.},
booktitle={2010 39th International Conference on Parallel Processing},
pages={61–70},
issn={0190-3918},
year={2010},
organization={IEEE}
}
Exact inference is a key problem in exploring probabilistic graphical models. The computational complexity of inference increases dramatically with the parameters of the graphical model. To achieve scalability over hundreds of threads remains a fundamental challenge. In this paper, we use a lightweight scheduler hosted by the CPU to allocate cliques in junction trees to the GPGPU at run time. The scheduler merges multiple small cliques or splits large cliques dynamically so as to maximize the utilization of the GPGPU resources. We implement node level primitives on the GPGPU to process the cliques assigned by the CPU. We propose a conflict free potential table organization and an efficient data layout for coalescing memory accesses. In addition, we develop a double buffering based asynchronous data transfer between CPU and GPGPU to overlap clique processing on the GPGPU with data transfer and scheduling activities. Our implementation achieved 30x speedup compared with state-of-the-art multicore processors.
April 4, 2011 by hgpu
