Real-Time Stream Compaction for Sparse Machine Learning on FPGAs

Die Autoren stellen einen für FPGAs optimierten, hierarchischen Kompressionspipeline vor, der in Chisel implementiert wurde und durch die Umwandlung spärlicher Sensor-Datenströme in dichte Eingaben die Hardware-Beschleunigung von Graph Neural Networks für Echtzeit-Trigger in Teilchendetektoren wie Belle II ermöglicht.

Das Wesentliche

Das große Problem: Der überfüllte Supermarkt

Stell dir vor, du arbeitest in einem riesigen Supermarkt (dem Teilchenbeschleuniger Belle II in Japan). Tausende von Kunden (den Teilchen) kommen gleichzeitig herein. Die Regale (die Sensoren) sind voll, aber die meisten Regale sind leer. Nur hier und da steht ein Kunde an einem Regal und nimmt ein Produkt.

In der Welt der Teilchenphysik passiert das Gleiche: Der Detektor produziert eine riesige Datenflut. Aber 90 % dieser Daten sind „leer" (es passiert nichts). Nur ganz selten gibt es ein interessantes Ereignis.

Das Problem für die Computer im Supermarkt (die FPGAs): Sie müssen jeden einzelnen Regalplatz prüfen, auch die leeren. Das kostet unglaublich viel Zeit und Energie. Wenn sie zu langsam sind, verpassen sie die interessanten Kunden, und der Supermarkt muss schließen (oder im Fall von Teilchenphysik: wertvolle Entdeckungen gehen verloren).

Die Lösung: Ein cleverer Türsteher mit einem Zauberstab

Die Autoren dieses Papiers haben eine Lösung entwickelt, die wie ein super-effizienter Türsteher funktioniert.

Stell dir vor, an der Kasse stehen 100 Kunden in einer Schlange (die Eingangsdaten). Aber 98 von ihnen haben nur leere Hände. Die Kasse (der Künstliche Intelligenz-Algorithmus, genauer gesagt ein Graph Neural Network) kann aber nur mit 2 Kunden gleichzeitig arbeiten. Wenn die Kasse auf die leeren Hände wartet, steht alles still.

Der neue Türsteher (das Sparsity-Compression-Modul) macht Folgendes:

1. Er schaut sich die 100 Kunden an.
2. Er ignoriert sofort alle, die leere Hände haben.
3. Er holt nur die 2 Kunden mit Produkten und stellt sie direkt vor die Kasse.
4. Alles passiert in einem Wimpernschlag (in Nanosekunden).

Dadurch muss die Kasse nicht mehr auf leere Hände warten. Sie kann sofort arbeiten. Das nennt man „Stream Compaction" (Datenström-Verdichtung).

Wie funktioniert das technisch? (Die Analogie der Wasserrohre)

Stell dir vor, du hast 100 dünne Wasserrohre, die Wasser in ein Becken leiten. Aber nur in 2 Rohren fließt wirklich Wasser; die anderen 98 sind trocken. Das Becken (der Computer) ist aber so gebaut, dass es nur 2 Rohre aufnehmen kann.

Normalerweise würde man versuchen, alle 100 Rohre anzuschließen. Das wäre chaotisch und teuer.
Die Erfinder haben stattdessen ein hohes, verzweigtes Rohrsystem gebaut:

• Alle 100 Rohre münden in dieses System.
• Das System hat einen „intelligenten Filter", der das trockene Wasser (die leeren Daten) aussortiert.
• Am Ende kommen nur noch die 2 Rohre mit echtem Wasser heraus, die perfekt auf das Becken passen.

Das Besondere an ihrer Erfindung ist, dass sie das nicht mit Software gemacht haben (das wäre zu langsam), sondern direkt in der Hardware (auf einem speziellen Chip, dem FPGA). Sie haben eine Art „Bauanleitung" (in einer Programmiersprache namens Chisel) geschrieben, die man wie einen Lego-Bausatz für jeden Supermarkt anpassen kann.

Warum ist das so wichtig?

In der Teilchenphysik (wie beim Belle II Experiment) gibt es eine harte Zeitgrenze. Der Computer muss innerhalb von 4,4 Mikrosekunden entscheiden, ob ein Ereignis interessant ist oder nicht. Das ist schneller als der menschliche Gedanke.

• Ohne diese Erfindung: Der Computer müsste alle leeren Daten prüfen. Er würde zu langsam sein und wichtige Entdeckungen verpassen.
• Mit dieser Erfindung: Der Computer bekommt nur die relevanten Daten. Die Rechenlast für die künstliche Intelligenz sinkt um den Faktor 324! Das ist, als würde man einen Berg von Papier in einen kleinen Stapel verwandeln, ohne den Inhalt zu verlieren.

Das Fazit

Die Forscher haben einen intelligenten Daten-Filter gebaut, der auf einem Chip sitzt. Er sortiert den „Müll" (leere Daten) aus, bevor die künstliche Intelligenz überhaupt anfängt zu denken.

• Für die Wissenschaft: Das bedeutet, dass man in Zukunft noch schnellere und intelligentere Algorithmen in den Teilchenbeschleunigern nutzen kann, um neue physikalische Geheimnisse zu lüften.
• Für uns alle: Es zeigt, wie man mit cleverem Ingenieurswesen (Hardware statt Software) enorme Geschwindigkeitsprobleme löst, die sonst unlösbar wären.

Kurz gesagt: Sie haben den Datenverkehr in einer überfüllten Stadt so geregelt, dass nur noch die wichtigen Autos durchkommen, damit der Verkehr nicht zum Stillstand kommt.

Technische Zusammenfassung

1. Problemstellung

In Teilchenphysik-Experimenten wie Belle II werden zunehmend Machine-Learning-Algorithmen, insbesondere Graph Neural Networks (GNNs), für die Auslösung (Trigger) auf der ersten Ebene eingesetzt. Diese Systeme müssen jedoch extrem strenge Anforderungen erfüllen:

• Latenz: Entscheidungen müssen deterministisch und innerhalb eines Budgets von wenigen Mikrosekunden (bei Belle II: 4,4 µs) getroffen werden.
• Durchsatz: Es müssen bis zu 10 Millionen Detektor-Snapshots pro Sekunde verarbeitet werden.
• Datencharakteristik: Die Eingangsdaten von Detektoren sind oft stark spärlich (sparse). In der elektromagnetischen Kalorimetrie (ECL) von Belle II ist beispielsweise nur ein kleiner Bruchteil der möglichen Datenwerte (Trigger Cells, TCs) in einem Ereignis von Null verschieden.
• Herausforderung: Dynamische GNNs (wie GraVNet) haben eine Rechenkomplexität von $O(N^2)$ in Bezug auf die Anzahl der Eingaben. Die Verarbeitung aller Eingänge (auch der Nullwerte) auf FPGA-Hardware führt zu einer ineffizienten Auslastung der Ressourcen und überschreitet oft die Latenzbudgets.

2. Methodik

Das Paper stellt einen Ansatz zur Echtzeit-Stream-Kompression (Real-Time Stream Compaction) vor, um die spärlichen Eingangsdaten vor der GNN-Inferenz zu verdichten.

• Ziel: Umwandlung einer großen Anzahl paralleler FIFO-Schnittstellen mit spärlichen Daten in eine kleinere Anzahl paralleler Schnittstellen mit dichten Datenströmen. Dies ermöglicht eine effiziente Nutzung der nachfolgenden Hardware-Beschleuniger.
• Architektur:
  • Hierarchische Pipeline: Das System besteht aus einem hierarchischen Baum von Kompressionsmodulen. Jedes Modul komprimiert $2 \cdot N_O$ Eingänge auf $N_O$ Ausgänge.
  • Stream Compaction Module: Das Kernmodul arbeitet in drei Pipeline-Stufen:
    1. Prefetch: Laden der Datenelemente in Register.
    2. Adressgenerierung: Erstellen eines Bitmasks aus den Valid-Signalen, Berechnung eines Präfix-Sums (Prefix Sum) über die gültigen Bits und Selektion der Adressen der ersten zwei nicht-null Elemente mittels Priority Encodern.
    3. Crossbar-Steuerung: Konfiguration eines Crossbars, um die nicht-null Elemente basierend auf den berechneten Adressen an die korrekten Ausgangsport zu leiten.
  • Fenster-Größe ($D$): Die Daten werden in statischen Fenstern von $D$ aufeinanderfolgenden Takten verarbeitet, um eine stau-freie (stall-free) Pipeline und 100% Auslastung zu gewährleisten.
• Implementierung: Der Entwurf wurde als Open-Source Hardware-Generator in der Beschreibungssprache Chisel implementiert. Die generierten Module sind AXI-Stream-konform und unterstützen Backpressure-Mechanismen.

3. Wichtige Beiträge

1. Open-Source Hardware-Generator: Ein vollständig konfigurierbarer Generator in Chisel, der Parameter wie Anzahl der Ein-/Ausgänge ($N_I, N_O$), Bitbreite und FIFO-Tiefe unterstützt.
2. Deterministische Latenz: Die Architektur garantiert eine feste Latenz, was für Echtzeitsysteme essenziell ist. Die Latenz $L$ wird durch die Formel $L = 3 \cdot \lceil \log_2(1 + N_I/N_O) \rceil \cdot f_{sys}$ bestimmt.
3. Integration in Belle II: Der Ansatz wurde erfolgreich in das GNN-ETM (Graph Neural Network Electromagnetic Calorimeter Trigger Module) des Belle II-First-Level-Triggers integriert.
4. Umfassende Evaluierung: Bewertung von Latenz, Durchsatz, Ressourcenverbrauch und Skalierbarkeit über verschiedene Konfigurationen hinweg.

4. Ergebnisse

Die Evaluierung erfolgte auf einem AMD Ultrascale XCVU190 FPGA (verwendet auf der Universal Trigger Board 4 von Belle II):

• Ressourcennutzung: Die Nutzung von Look-Up Tables (LUTs) und Registern (FFs) skaliert linear mit der Anzahl der Eingangsports. Die Anzahl der Ausgangsports hat einen stärker als linearen Einfluss auf die Ressourcen, bleibt aber gut handhabbar. Block-RAMs und DSPs werden nicht genutzt.
• Frequenz: Die erreichbare Systemfrequenz hängt von der Anzahl der Ausgangsports ab. Bei 2 Ausgangsports wurde die geforderte Frequenz erreicht; bei 8 Ausgangsports sank sie auf ca. 277 MHz (bedingt durch die Größe des Crossbars).
• Performance-Gewinn: Im spezifischen Anwendungsfall von Belle II konnte die Rechenlast für die nachfolgende GNN-Inferenz im Vergleich zu einem naiven Ansatz (Verarbeitung aller Eingänge) um einen Faktor von 324 reduziert werden.
• Latenz-Overhead: Der Overhead durch die Kompressionsstufe beträgt weniger als 60 ns, was weit unter dem gesamten Trigger-Latenzbudget liegt.

5. Bedeutung und Fazit

Dieses Werk adressiert eine kritische Lücke bei der Implementierung von Machine Learning auf FPGAs für Hochenergiephysik-Experimente.

• Effizienz: Durch die Entfernung der dynamischen Eingangs-Spärlichkeit wird die Hardware-Auslastung maximiert, ohne die Echtzeitanforderungen zu verletzen.
• Skalierbarkeit: Die Lösung ist nicht auf Belle II beschränkt, sondern kann für andere große wissenschaftliche Experimente adaptiert werden, die mit spärlichen Sensordaten und hohen Durchsatzanforderungen konfrontiert sind.
• Praktische Relevanz: Die erfolgreiche Integration in einen echten First-Level-Trigger beweist die Machbarkeit, GNNs in extremen Umgebungen mit Mikrosekunden-Latenz einzusetzen.

Zusammenfassend demonstriert das Paper, dass spärlichkeitsbewusste Kompression ein Schlüssel zur effizienten Beschleunigung von Machine Learning auf FPGAs ist, indem sie die Datenmenge auf das für die Inferenz tatsächlich notwendige Minimum reduziert. Der Quellcode ist öffentlich auf GitHub verfügbar.