GPU-Accelerated Belief Propagation for Program Analysis

Abstract

Belief Propagation (BP) is a widely used approximate inference algorithm in probabilistic graphical models (PGMs), but is computationally expensive when applied to large-scale program analysis. Existing GPU-based approaches are unable to support flexible update strategies and have yet to integrate logical constraints with GPU acceleration, leading to challenges in both generality and efficiency. We present FastLBP, a GPU-accelerated BP framework for program analysis. We propose a unified representation for specifying flexible update strategies required in program analysis, along with a dependency analysis algorithm to enable parallel execution. Furthermore, we implement BP with local structures on GPUs by assigning individual threads to message computations and utilizing a memory-efficient representation. Experiments on SmartFL and BINGO show that FastLBP achieves average speedups of $17.42\times$ and $2.82\times$ over CPU-based approaches on SmartFL and BINGO, respectively, and $6.14\times$ over GPU-based approach on SmartFL, while preserving accuracy. Moreover, FastLBP supports update strategies that existing GPU-based approaches cannot support, demonstrating its improved generality for real-world program analysis.