Real-Time Stream Compaction for Sparse Machine Learning on FPGAs

This paper presents a latency-optimized, hierarchical sparsity compression pipeline implemented in Chisel for FPGAs, which rearranges sparse sensor data from multiple FIFO interfaces to fewer streams to enable efficient Graph Neural Network acceleration in high-throughput, low-latency first-level triggers for collider experiments like Belle II.

The Gist

Imagine you are running a high-speed train station (the Belle II particle detector) where thousands of passengers (data packets) arrive every second. Most of the time, the platforms are empty, but occasionally, a massive crowd rushes in.

Your goal is to get these passengers onto a very fast, but very small, express train (the Machine Learning chip) that can only carry a few people at a time. The problem? The express train needs to be full to run efficiently, but the passengers arrive in a chaotic, scattered mess with huge gaps of empty space between them. If you try to load them one by one as they arrive, the train sits half-empty, and the whole system slows down.

This paper presents a clever solution to that problem: a "Smart Crowd Manager" for data.

Here is the breakdown of what the researchers did, using everyday analogies:

1. The Problem: The "Sparse" Mess

In particle physics, detectors are like giant grids of sensors. Most of the time, nothing happens (the sensors are empty). But when a particle collision occurs, only a few sensors light up.

• The Old Way: Imagine trying to pack a suitcase by taking items from 100 different drawers, but 95 of those drawers are empty. You spend all your time checking empty drawers, and the suitcase (the data stream) is mostly air.
• The Consequence: The "express train" (the AI chip) has to wait around for the few actual items, wasting time and energy. This is too slow for the split-second decisions needed in a particle collider.

2. The Solution: The "Stream Compactor"

The authors built a hardware device (a Sparsity Compression Module) that acts like a super-efficient traffic cop.

• The Setup: It takes data coming from hundreds of input lanes (the 100 drawers).
• The Magic: It instantly scans all the lanes, ignores the empty ones, and shoves only the "real" data (the passengers) into a few output lanes.
• The Result: Instead of a long, bumpy line with huge gaps, you get a tight, dense line of passengers ready to board the express train immediately.

3. How It Works (The "Tree" and the "Crossbar")

The researchers designed this manager using a language called Chisel (which is like a blueprint for building computer chips). They organized it like a hierarchical tree:

• The Tree: Imagine a funnel. At the top, you have many branches. As you go down, the branches merge. The device looks at pairs of input streams, picks out the "real" data, and passes it down to the next level.
• The Crossbar: At the bottom, there is a smart switchboard (a crossbar). It's like a subway station with moving walkways. It knows exactly where to send the data so that the output lanes are perfectly balanced and ready for the AI.

4. Why It's a Big Deal

• Speed: This manager works in nanoseconds (billionths of a second). It's so fast that it doesn't slow down the train; it actually makes the train run smoother.
• Efficiency: In their test with the Belle II detector, this system reduced the workload for the AI by a factor of 324. That's like turning a 300-mile drive into a 1-mile drive just by removing all the empty road.
• Real-World Use: They didn't just draw it on paper; they built it on a real chip (an FPGA) and tested it. It's now part of the actual system that decides which particle collisions are interesting enough to keep for study.

The Bottom Line

Think of this paper as inventing a "Data Vacuum Cleaner."
In the past, scientists had to drag a heavy, slow vacuum through a room full of dust (data) and air (empty space). This new invention instantly sucks up all the dust, packs it into a tiny, dense bag, and hands it to the cleaning crew. This allows the crew (the AI) to work 300 times faster without getting tired, ensuring that no important particle collision is ever missed because the system was too slow to react.

In short: They figured out how to squeeze a lot of scattered, empty data into a tight, fast stream so that AI chips can process it instantly, making particle physics experiments much more powerful.

Technical Summary

1. Problem Statement

The paper addresses the challenge of deploying Graph Neural Networks (GNNs) in the first-level triggers of high-energy collider experiments, specifically focusing on the Belle II experiment.

• Hardware Constraints: First-level triggers operate under extreme constraints: hard real-time latency deadlines (approx. 4.4 µs), high throughput (up to 10 million detector snapshots/second), and limited FPGA resources.
• The Sparsity Issue: Particle physics data is inherently sparse (e.g., Figure 1 shows input densities often below 10%). However, dynamic GNNs (like GraVNet) typically have $O(N^2)$ computational complexity relative to the number of inputs. Processing all inputs (including zeros) wastes massive computational resources and bandwidth.
• The Gap: While GNN deployment strategies exist, there is a lack of end-to-end pipelines that handle dynamic input sparsity efficiently within the strict latency budgets of collider triggers. Existing stream compression methods focus on bandwidth reduction between platforms, not on preprocessing data for neural network inference on the same compute platform.

2. Methodology

The authors propose a hierarchical sparsity compression pipeline designed specifically for FPGAs to densify sparse data streams before they reach the GNN accelerator.

• Core Concept: The system rearranges data from $N_I$ parallel FIFO input interfaces (sensor frontends) into $N_O$ fewer parallel FIFO output interfaces connected to the ML accelerator. This removes "empty" (zero) data elements, creating dense streams for the GNN.
• Architecture:
  • Hierarchical Tree: The module uses a tree topology where cells compress $2 \cdot N_O$ input ports into $N_O$ output ports.
  • Stream Compaction Cell (The Core Unit): This unit performs two functions:
    1. Intra-stream alignment: Rearranges sparse input data into dense streams.
    2. Inter-stream alignment: Balances the dense streams across output ports.
  • Pipeline Stages:
    1. Prefetch: Data elements are loaded into registers over a static window $D$.
    2. Address Generation: A bitmask is generated from valid signals. A prefix sum is calculated, and two daisy-chained priority encoders select the addresses of the first two non-zero elements.
    3. Crossbar Routing: Based on calculated addresses, a crossbar forwards non-zero data elements to the correct output ports.
• Latency Model: The design achieves deterministic latency ($L$) defined by Equation 3.1:
  $$L = 3 \cdot \lceil \log_2(1 + \frac{N_I}{N_O}) \rceil \cdot f_{sys}$$
  This ensures the pipeline is stall-free with 100% utilization when the window depth $D$ is statically defined.

3. Key Contributions

1. Open-Source Hardware Generator: Implemented in Chisel (a hardware construction language), allowing users to configure the number of input/output ports ($N_I, N_O$), bitwidth, and FIFO depth. The generated modules are AXI-Stream compliant.
2. Latency-Optimized Architecture: A novel pipeline design that guarantees deterministic latency and 100% throughput, critical for hard real-time trigger systems.
3. Real-World Deployment: The concept was integrated into the GNN-ETM (Graph Neural Network Electromagnetic Calorimeter Trigger Module) for the Belle II experiment.
4. Comprehensive Evaluation: The authors evaluated the design across nine different configurations, analyzing latency, throughput, resource utilization, and scalability.

4. Results

The system was synthesized and placed/routed using AMD Vivado 2024 targeting the AMD Ultrascale XCVU190 FPGA (used in the Belle II Universal Trigger Board).

• Resource Utilization:
  • LUTs and Registers (FFs): Scale linearly with the number of input ports ($N_I$).
  • Output Ports ($N_O$): Resource usage scales worse than linearly with $N_O$ due to the increasing size of the internal crossbar.
  • Routeability: The number of occupied Configurable Logic Blocks (CLBs) closely matches the LUT count, indicating excellent routability on the FPGA.
• Frequency Performance:
  • Designs with fewer output ports ($N_O=2$) achieved the target 500 MHz.
  • Increasing $N_O$ to 8 reduced the maximum frequency to 277 MHz due to the larger crossbar logic.
• Performance Gain in Belle II:
  • In the specific deployment for the Belle II ECL trigger, the module reduced the computational load for the subsequent GNN inference by a factor of 324 compared to a naive approach (processing all inputs).
  • The latency overhead introduced by the compression module was below 60 ns, well within the 4.4 µs total trigger budget.

5. Significance

• Enabling ML in Triggers: This work demonstrates that complex, dynamic GNNs can be deployed in first-level triggers by effectively managing input sparsity, a previously unaddressed bottleneck.
• Scalability: The hierarchical, configurable nature of the Chisel generator allows the solution to scale for other large-scale scientific experiments beyond Belle II.
• Efficiency: By removing dynamic input sparsity, the approach maximizes the utilization of downstream hardware accelerators, making high-throughput, low-latency machine learning feasible on FPGAs.
• Open Science: The release of the source code on GitHub facilitates adoption and further development by the broader scientific community.