💻 computer science

GPU-Accelerated Belief Propagation for Program Analysis

The paper introduces FastLBP, a GPU-accelerated Belief Propagation framework that employs a unified representation for flexible update strategies and efficient parallel execution to achieve significant speedups over existing CPU and GPU methods while maintaining accuracy in large-scale program analysis.

Original authors: Haoyu Feng, Xin Zhang

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Haoyu Feng, Xin Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled web of clues to figure out where a hidden treasure is buried. In the world of computer science, this is often called "program analysis," where software engineers try to find bugs (the hidden treasures) in huge codebases. To do this, they use a mathematical tool called Belief Propagation. Think of this tool like a game of "telephone" played by thousands of tiny messengers. Each messenger stands at a crossroads in the code, holding a piece of information. They shout their current guess to their neighbors, who listen, mix it with their own knowledge, and shout back a new, better guess. They keep doing this, passing messages back and forth, until everyone agrees on where the treasure is.

However, when the code is huge, this game of telephone becomes incredibly slow. The messengers have to whisper to each other millions of times, and doing it one by one takes forever. Scientists have tried to speed this up by using GPUs (Graphics Processing Units), which are super-fast computer chips originally designed to draw video game graphics. GPUs are like a stadium filled with thousands of workers who can all shout at once. But there's a catch: the rules of the game sometimes require the messengers to shout in a specific order, or to listen to the very latest whisper from a neighbor before shouting their own. If you force all the workers to shout at the exact same time (which GPUs love to do), the game breaks, and the answer becomes wrong. This paper tackles the challenge of teaching these super-fast GPU workers how to play a complex, rule-heavy game of telephone without messing up the clues.

The researchers, Haoyu Feng and Xin Zhang from Peking University, have built a new system called FastLBP. Their main discovery is that they can make Belief Propagation run much faster on GPUs without breaking the complex rules that program analysis requires. They found that existing GPU tools were too rigid; they could only handle simple, "shout-at-once" scenarios. But real-world bug hunting often needs a more flexible approach, where some messengers wait for others to finish before they speak. FastLBP solves this by acting like a smart game master. Before the shouting starts, it analyzes the map of connections and groups the messengers into teams. It tells Team A to shout, then Team B, then Team C, ensuring that no one speaks out of turn, while still letting thousands of people in each team shout simultaneously.

Furthermore, the paper shows that FastLBP is incredibly efficient at handling specific types of logical rules found in code, known as "local structures." Imagine if the messengers realized that 90% of the time, they were just repeating the same phrase. Instead of writing out the whole sentence every time, they could just say "copy the last one." FastLBP does this mathematically, skipping unnecessary calculations to save massive amounts of time.

When the team tested their system, the results were striking. On a program analysis tool called SmartFL, FastLBP was 17.42 times faster than the best existing computer-based (CPU) methods and 6.14 times faster than the best existing GPU methods. On another tool called BINGO, it was 2.82 times faster than the CPU version. Perhaps most importantly, the paper demonstrates that FastLBP doesn't just run faster; it runs smarter. It supports flexible update strategies that other GPU tools simply cannot handle. In tests, when the researchers forced a rigid, "shout-at-once" strategy (which other GPU tools use), the system produced much worse results, missing many true bugs. FastLBP, by allowing the messengers to follow the correct, flexible order, maintained high accuracy while still being lightning-fast. The authors conclude that by combining a smart scheduling system with a memory-efficient design, they have created a tool that makes finding bugs in large software projects significantly quicker and more reliable, without sacrificing the correctness of the answers.

Technical Summary: FastLBP – GPU-Accelerated Belief Propagation for Program Analysis

Problem Statement

Belief Propagation (BP) is a fundamental approximate inference algorithm for Probabilistic Graphical Models (PGMs), widely applied in program analysis tasks such as fault localization (e.g., SmartFL) and bug detection (e.g., BINGO). However, applying BP to large-scale program analysis faces two primary challenges:

Computational Cost: Large-scale software generates massive PGMs, making the iterative message-passing process computationally expensive on traditional CPU-based approaches.
Limitations of Existing GPU Solutions: While GPUs offer massive parallelism, existing GPU-based BP frameworks (e.g., PGMax) suffer from two critical limitations when applied to program analysis:
- Inflexible Update Strategies: They typically support only synchronous BP (updating all messages simultaneously). However, program analysis applications often require asynchronous or round-robin update strategies to ensure convergence stability and accuracy, which existing GPU implementations cannot support due to complex data dependencies.
- Inefficient Handling of Local Structures: Program analysis constraints (e.g., probabilistic Horn clauses) often exhibit "local structures" where many variable assignments share identical probability values. Traditional GPU approaches use dense tabular representations that fail to exploit these redundancies, resulting in exponential computational complexity ( $O(n \cdot 2^n)$ ) rather than the linear time ( $O(n)$ ) achievable with specialized algorithms.

Methodology

The authors present FastLBP, a GPU-accelerated BP framework designed specifically to address the generality and efficiency gaps in program analysis. The framework consists of three core technical components:

1. Unified Representation and Dependency Analysis

To support flexible update strategies (including asynchronous and round-robin schedules) on GPUs, FastLBP introduces a unified intermediate representation: a preordered set $(E, \lesssim)$ over the edge set $E$ of the factor graph.

Semantics: Specifying $e_1 \lesssim e_2$ ensures that the message update on edge $e_1$ occurs no later than on $e_2$ within a single iteration.
Dependency Analysis: The system performs a dependency analysis algorithm that identifies groups of messages that can be updated in parallel without violating the user-specified update semantics. By partitioning edges into ordered groups based on the Hasse diagram of the preorder, FastLBP preserves the semantics of asynchronous schedules while exposing parallelism for GPU execution.

2. GPU Implementation of BP with Local Structures

To address the inefficiency of dense representations, FastLBP implements BP with local structures on the GPU.

Algorithmic Optimization: Instead of enumerating all factor assignments, the algorithm groups assignments with identical probability values. This reduces the complexity of factor-to-variable message computation from exponential to linear time.
Thread Mapping: The framework assigns individual GPU threads to compute single messages. Each thread evaluates a sequence of sub-messages corresponding to the grouped assignments.
Memory Organization: To handle the large, sparse graphs typical of program analysis, FastLBP utilizes a Compressed Sparse Row (CSR) format for message storage. It organizes messages such that rows are indexed by factor identifiers (for factor-to-variable messages) or variable identifiers (for variable-to-factor messages), ensuring contiguous memory access and reducing indexing overhead. Factor configurations are stored in a flattened array with indicator values, avoiding the memory explosion of dense tables.

3. Execution Workflow

The FastLBP workflow involves:

Initialization: Allocating GPU memory using the CSR layout.
Dependency Analysis: Partitioning edges into parallelizable batches based on the update strategy.
Kernel Launch: Launching GPU kernels for each batch, where threads compute messages in two phases (variable-to-factor, then factor-to-variable) to avoid read-after-write dependencies.
Message Passing: Iterating until convergence or a specified iteration limit.

Key Contributions

The paper claims the following contributions:

FastLBP Framework: A GPU-accelerated BP framework for program analysis that enables flexible update strategies and efficient inference on large-scale PGMs.
Unified Strategy Representation: A formal preordered set representation for user-specified update strategies and a corresponding dependency analysis algorithm that enables effective parallelization while preserving update semantics.
Efficient GPU Implementation: A novel GPU implementation of BP with local structures that assigns threads to single messages and utilizes compact memory layouts to reduce computational complexity and memory footprint.
High-Performance Prototype: An implementation in C++ and CUDA that demonstrates significant speedups over state-of-the-art approaches while maintaining accuracy.

Experimental Results

The authors evaluated FastLBP using two representative program analysis benchmarks: SmartFL (probabilistic fault localization) and BINGO (Bayesian program analysis). The baselines included a state-of-the-art CPU-based approach (Wu et al. [30]) and a state-of-the-art GPU-based approach (PGMax [37]).

Efficiency on SmartFL:
- Compared to the CPU baseline (Wu et al.), FastLBP achieved an average speedup of 17.42×.
- Compared to the GPU baseline (PGMax), FastLBP achieved an average speedup of 6.14×.
- PGMax failed to run on the largest benchmark (Chart-15) due to out-of-memory errors, whereas FastLBP succeeded due to its memory-efficient local structure representation.
Efficiency on BINGO:
- Using an asynchronous update strategy (which PGMax does not support), FastLBP achieved an average speedup of 2.82× over the CPU baseline.
- On larger graphs (excluding small benchmarks where overhead dominates), the speedup increased to 5.12×, with a maximum of 10.46×.
Accuracy and Quality:
- FastLBP maintained high accuracy, with relative errors in marginal probabilities less than $10^{-8}$ compared to the CPU baseline.
- In terms of inference quality metrics (inversion count, Rank-100%-T, Rank-90%-T), FastLBP showed negligible differences from the CPU baseline.
- In contrast, PGMax (restricted to synchronous BP) showed significantly degraded results (e.g., a 256% increase in inversion count), highlighting the necessity of flexible update strategies for program analysis.

Significance

The paper argues that FastLBP addresses the critical trade-off between generality and efficiency in GPU-accelerated program analysis. By enabling flexible update strategies (specifically asynchronous ones required for convergence in complex analysis tasks) and optimizing for local structures inherent in program semantics, FastLBP allows program analysis systems to scale to larger software projects without sacrificing the accuracy or convergence properties provided by CPU-based sequential implementations. The work demonstrates that GPU acceleration is viable for program analysis only when the implementation is tailored to the specific structural and scheduling requirements of the domain, rather than relying on generic, synchronous-only approaches.