Real-Time Stream Compaction for Sparse Machine Learning on FPGAs

Dit paper presenteert een open-source, FPGA-geoptimaliseerde hiërarchische compressiepijplijn in Chisel die dynamische input-sparsiteit van sensordata verwijdert om de prestaties van Graph Neural Networks voor real-time triggers in deeltjesfysica-experimenten, zoals Belle II, te verbeteren.

De kern

Stel je voor dat je een enorme, drukke treinstation hebt: Belle II. Dit is een gigantisch deeltjesversneller in Japan waar wetenschappers kijken hoe het universum in elkaar zit. Elke seconde komen er duizenden deeltjes binnen, en de sensoren van het station moeten alles opvangen.

Het probleem? De meeste plekken in de trein zijn leeg. Het is alsof je een trein hebt met 1000 zitplaatsen, maar er zitten er maar 5 mensen in. Toch moet de trein (de computer) elke stoel controleren om te zien of er iemand zit. Dat kost enorm veel tijd en energie, en dat kan niet, want de trein moet razendsnel vertrekken voordat de volgende trein aankomt.

Dit artikel beschrijft een slimme oplossing voor dit probleem, speciaal ontworpen voor de FPGA's (de supersnelle computers die in de machine zitten).

Hier is de uitleg in simpele taal:

1. Het Probleem: De "Lege Trein"

In de natuurkunde-experimenten zijn de data vaak heel dun (wetenschappelijk: spars). Dat betekent dat van de duizenden meetpunten er maar een paar daadwerkelijk iets interessants meten.
De huidige computers proberen echter alles tegelijk te verwerken, ook de lege plekken. Het is alsof een postbode elke brievenbus in een stad leegt, ook al zitten er 99% van de dozen leeg. Dat kost te veel tijd.

2. De Oplossing: De "Slimme Sorteerder"

De auteurs hebben een nieuw apparaatje bedacht, een soort slimme sorteerder (in het Engels: Stream Compaction).
Stel je voor dat je duizenden mensen (de data) hebt die door 100 verschillende deuren naar binnen komen. De meeste mensen zijn er niet, dus de deuren staan vaak open zonder iemand.

Deze slimme sorteerder doet het volgende:

• Het filteren: Hij kijkt snel door de 100 deuren en pakt alleen de mensen die écht binnenkomen.
• Het herschikken: Hij duwt die mensen direct door naar een paar andere deuren (bijvoorbeeld 2 of 4), zodat ze daar dicht op elkaar zitten.
• Het resultaat: In plaats van 100 deuren met hier en daar iemand, heb je nu 2 deuren waar een strakke rij mensen staat.

3. Waarom is dit zo belangrijk? (De "GNN")

In het experiment willen ze een heel slimme AI gebruiken (een Grafische Neurale Netwerk of GNN) om te beslissen welke deeltjes interessant zijn. Deze AI is als een super-snel brein, maar hij wordt erg traag als hij eerst alle lege stoelen moet controleren.

Met de "Slimme Sorteerder" krijgt de AI alleen de mensen die er écht zijn.

• Vroeger: De AI moest 1000 stoelen checken (waarvan 995 leeg).
• Nu: De AI checkt direct de 5 mensen die er zijn.

Dit maakt de AI 324 keer sneller in zijn werk! En dat is cruciaal, want in deze experimenten moet de beslissing binnen 0,000004 seconde (4,4 microseconden) zijn genomen. Als het langer duurt, is de trein al vertrokken en is het te laat.

4. Hoe werkt het technisch? (De "Truc")

De wetenschappers hebben dit niet gebouwd met schroeven en bouten, maar met code (in een taal genaamd Chisel). Ze hebben een "machine voor het maken van machines" gemaakt.

• Je kunt instellen hoeveel ingangen je hebt (bijv. 64 of 256) en hoeveel uitgangen je wilt.
• Het apparaatje werkt als een trechter: het vangt de losse druppels water (de data) op en bundelt ze tot een straal die direct de motor (de AI) aandrijft.
• Het is zo snel gebouwd dat het geen tijd kost om te sorteren; het gebeurt bijna tegelijk met het binnenkomen van de data.

5. Het Resultaat

Ze hebben dit apparaatje getest op de grootste computerchip die ze konden vinden (een AMD FPGA).

• Snelheid: Het werkt razendsnel, zonder vertraging.
• Ruimte: Het neemt niet veel ruimte in op de chip (zoals een klein kastje in een grote kamer).
• Toepassing: Het werkt al in het echte experiment bij Belle II.

Kort samengevat:
Deze paper beschrijft hoe ze een "slimme hoeder" hebben gebouwd die de lege plekken in de data weghaalt voordat de computer erbij komt kijken. Hierdoor kan de super-snelle AI van het experiment veel efficiënter werken, waardoor ze meer deeltjes kunnen bestuderen zonder dat het systeem vastloopt. Het is alsof je van een lege trein een volle trein maakt voordat hij de rails oprijdt, zodat de locomotief niet hoeft te wachten.

Technische samenvatting

Probleemstelling

Machine learning-algoritmen, en specifiek Graph Neural Networks (GNN's), worden steeds vaker ingezet in de eerste-triggerniveaus van deeltjesfysica-experimenten. Dit stelt echter hoge eisen aan de hardware, vooral op Field Programmable Gate Arrays (FPGA's). Er zijn drie kritieke uitdagingen:

1. Strakke Latentie-eisen: Triggerbeslissingen moeten deterministisch en binnen een zeer kort tijdsbestek (in de orde van microseconden) worden genomen om bufferoverloop in het data-acquisitiesysteem (DAQ) te voorkomen.
2. Hoge Doorvoer: Systemen moeten miljoenen detector-snapshot per seconde verwerken (bijv. 10 miljoen bij Belle II).
3. Sparsiteit en Complexiteit: De invoerdata van detectoren is vaak zeer spaarzaam (veel nul-waarden), terwijl dynamische GNN's (zoals GraVNet) een rekencomplexiteit van $O(N^2)$ hebben ten opzichte van het aantal invoer-elementen. Het verwerken van alle invoerkanalen, inclusief de lege, leidt tot inefficiënt gebruik van hardwarebronnen en onnodige latentie.

Het huidige probleem is dat er nog geen end-to-end pipelines bestaan die deze spaarzaamheid effectief benutten voor GNN-inferentie in real-time trigger-systemen zonder de prestaties te compromitteren.

Methodologie

De auteurs stellen een concept voor voor latentie-geoptimaliseerde preprocessing van spaarse sensordata. Het doel is om de dynamische invoersparsiteit te verwijderen door data van een groot aantal invoerinterfaces (FIFO's) te herschikken naar een kleiner aantal uitvoerinterfaces, zodat de datastroom "dicht" (dense) wordt voor de machine learning accelerator.

De kern van de oplossing is een hiërarchische sparsiteitscompressie-pijplijn die is geoptimaliseerd voor FPGA's:

• Architectuur: Het systeem bestaat uit een boomtopologie van "stream compaction" modules. Elke cel in de boom comprimeert $2 \cdot N_O$ invoerpoorten naar $N_O$ uitvoerpoorten.
• Werking per cel:
  1. Prefetch: Data-elementen worden geladen in prefetch-registers over een venster van $D$ klokcycli.
  2. Adresgeneratie: Er wordt een bitmask gegenereerd op basis van geldige signalen. Een prefix-sum berekening en twee prioriteitsencoders (daisy-chained) selecteren de adressen van de eerste twee niet-nul data-elementen.
  3. Crossbar-configuratie: Op basis van de berekende adressen wordt een crossbar geconfigureerd om de data-elementen door te sturen naar de juiste uitvoerpoorten.
• Kenmerken: De aanpak garandeert deterministische latentie, zorgt voor 100% gebruik van de pijplijn (stall-free) door een statisch gedefinieerd venster, en behoudt de routeerbaarheid op FPGA's omdat de grootte van de crossbar alleen schaalt met de verhouding van de poorten.

Belangrijkste Bijdragen

1. Open-source Hardware Generator: De auteurs hebben een volledig configureerbare hardware-generator geïmplementeerd in de Chisel-ontwerptaal. Deze genereert AXI-Stream-compatibele modules die backpressure ondersteunen via ready-valid handshakes.
2. Uitgebreide Evaluatie: Er zijn negen verschillende configuraties geëvalueerd met variërende aantallen invoer- ($N_I$) en uitvoerpoorten ($N_O$), waarbij de impact op latentie, doorvoer en resource-gebruik is gekwantificeerd.
3. Real-World Implementatie: Het concept is succesvol geïntegreerd in de GNN-ETM (Graph Neural Network Electromagnetic Calorimeter Trigger Module) binnen het eerste-triggerniveau van het Belle II-detectorexperiment.

Resultaten

De evaluatie is uitgevoerd op een AMD Ultrascale XCVU190 FPGA (gebruikt op de Universal Trigger Board 4 van Belle II) met behulp van AMD Vivado 2024.

• Resource-gebruik: Het aantal Lookup Tables (LUTs) en Registers (FFs) schaalt lineair met het aantal invoerpoorten. Het aantal Configurable Logic Blocks (CLBs) komt overeen met het aantal LUTs, wat wijst op goede routeerbaarheid. Block RAMs en DSP's worden niet gebruikt.
• Frequentie: De systeemfrequentie daalt naarmate het aantal uitvoerpoorten toeneemt (vanwege de grotere crossbar), variërend van ~500 MHz (bij 2 uitvoerpoorten) tot ~277 MHz (bij 8 uitvoerpoorten).
• Performance in Belle II: In de specifieke toepassing voor de Belle II ECL-resultaten wordt een reductie van de rekenlast voor de daaropvolgende GNN-inferentie bereikt met een factor 324 ten opzichte van een naïeve aanpak.
• Latentie: De overhead van de compressie is extreem laag, namelijk minder dan 60 nanoseconden, wat binnen de strenge budgetten van het trigger-systeem valt.

Betekenis

Dit werk bewijst dat sparsiteitsbewuste compressie een cruciale schakel is om efficiënt machine learning op FPGA's mogelijk te maken voor high-throughput, low-latency omgevingen zoals deeltjesfysica-experimenten.

• Het lost het probleem op van het verwerken van spaarse data in dynamische GNN's zonder de harde real-time eisen te schenden.
• Het biedt een schaalbare, open-source oplossing die niet alleen voor Belle II, maar ook voor andere grote wetenschappelijke experimenten kan worden gebruikt.
• De integratie in het Belle II-systeem markeert een belangrijke stap in de overgang van conceptuele studies naar daadwerkelijke implementatie van AI in de eerste-triggerniveaus van collider-experimenten.