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.
From: Haoyu Feng [view email]
[v1]
Fri, 26 Sep 2025 13:30:30 UTC (3,902 KB)
[v2]
Sat, 18 Jul 2026 03:58:03 UTC (147 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。