da4ml: Distributed Arithmetic for Real-time Neural Networks on FPGAs

Dit artikel presenteert `da4ml`, een nieuw algoritme voor FPGA's dat door middel van *distributed arithmetic* de rekenkracht en latentie van neurale netwerken optimaliseert, waardoor ze efficiënter en sneller kunnen worden uitgevoerd met aanzienlijk minder hardwarebronnen.

De kern

Stel je voor dat je een superflitsende chef-kok bent in een restaurant waar de gasten niet wachten op hun eten, maar de bestelling verwachten voordat ze de menukaart hebben dichtgeslagen. Dat is de wereld van de deeltjesversneller bij CERN: er gebeuren miljarden dingen per seconde, en je moet binnen een fractie van een microseconde beslissen: "Is dit een belangrijke ontdekking of gewoon ruis?"

Om die razendsnelle beslissingen te nemen, gebruiken wetenschappers 'hersenen van silicium': FPGA's (een soort digitale bouwdozen die je razendsnel kunt herprogrammeren). In die bouwdozen draaien 'neurale netwerken' (mini-AI'tjes).

Het probleem: De digitale file

Het probleem is dat deze AI-hersenen heel veel rekenwerk moeten doen. Vooral het vermenigvuldigen van grote tabellen met getallen (de zogenaamde Matrix-Vector Multiplicatie) vreet ruimte.

Zie het zo: je hebt een enorme kookopdracht waarbij je voor elke gast 100 ingrediënten moet afwegen. Als je voor elk ingrediënt een aparte weegschaal koopt, is je keuken binnen no-time vol en kun je niet meer bewegen. Je hebt te veel 'hardware' (weegschalen) nodig en de boel loopt vast.

De oplossing: da4ml (De slimme reken-truc)

De onderzoekers hebben een nieuwe methode bedacht genaamd da4ml. In plaats van voor elke berekening een nieuwe, zware rekenmachine (een DSP-chip) te gebruiken, gebruiken ze een slimme wiskundige truc: Distributed Arithmetic.

De metafoor: De slimme kok met een rekenwonder
In plaats van dat de kok voor elke bestelling een nieuwe berekening maakt (bijv. "3 x 7 is 21"), onthoudt hij patronen. Hij ziet dat veel bestellingen dezelfde ingrediënten gebruiken. In plaats van telkens opnieuw te rekenen, zegt hij: "Oh, dat is weer die combinatie van 3 en 7, die ken ik al, dat is gewoon dit patroon."

Hij vervangt zware vermenigvuldigingen door simpele optellingen en verschuivingen. Dat is alsof je niet een hele rekenmachine gebruikt om 10 x 5 uit te rekenen, maar gewoon je vingers gebruikt om 10 + 10 + 10 + 10 + 10 te doen. Dat gaat veel sneller en kost veel minder ruimte in je 'keuken'.

Wat hebben we eraan?

De onderzoekers hebben deze truc in een pakketje gestopt dat ze da4ml noemen. De resultaten zijn indrukwekkend:

1. Minder ruimte nodig: Ze gebruiken tot wel één derde minder ruimte op de chip. Je keuken is dus veel leger en overzichtelijker.
2. Nog sneller: De berekeningen gaan sneller, waardoor de AI nog sneller kan beslissen.
3. Geen extra kosten: De AI blijft even slim en nauwkeurig als voorheen. Er worden geen foutjes gemaakt door de truc te gebruiken.
4. Direct bruikbaar: Het is direct gekoppeld aan hls4ml, een gereedschapskist die al veel door wetenschappers wordt gebruikt.

Kortom...

da4ml is als een slimme assistent die een chaotische keuken verandert in een hyper-efficiënte machine. Hierdoor kunnen wetenschappers bij CERN veel complexere en slimme AI-modellen gebruiken om de geheimen van het universum te ontrafelen, zonder dat hun digitale computers vastlopen of te vol raken.

Technische samenvatting

Technische Samenvatting: da4ml

1. Het Probleem: De Bottleneck in Real-time AI op FPGA's

In toepassingen waar extreem lage latentie vereist is (sub-microseconde), zoals de trigger-systemen van de Large Hadron Collider (LHC) bij CERN, worden neurale netwerken meestal volledig "unrolled" en "pipelined" op FPGA's (Field-Programmable Gate Arrays) geïmplementeerd.

De grootste uitdaging bij deze implementatie is de area utilization (het gebruik van hardware-oppervlakte). De meest rekenintensieve operatie in deze netwerken is de Constant Matrix-Vector Multiplication (CMVM), die plaatsvindt in de dense en convolutionele lagen. Traditionele methoden om dit te optimaliseren zijn ofwel:

• Te traag voor grote matrices: Algoritmen zoals $H_{cmvm}$ hebben een computationele complexiteit van $O(N^3)$, wat het onpraktisch maakt voor grotere neurale netwerken.
• Niet optimaal: Bestaande algoritmen (zoals SCMVM) missen kansen voor optimalisatie omdat ze geen rekening houden met verschillende schalingen (bit-shifts) of tekens (signed digits) in de gewichten.

2. Methodologie: Het da4ml Algoritme

De auteurs stellen da4ml voor, een optimalisatiekader dat gebruikmaakt van Distributed Arithmetic (DA). DA vervangt vermenigvuldigingen door een reeks verschuivingen en optellingen (shift-and-add), wat zeer efficiënt is op FPGA's omdat dit direct in de Look-Up Tables (LUT's) kan worden geïmplementeerd.

Het algoritme werkt via een hybride aanpak in twee fasen:

• Fase 1: Graph-based Decomposition (Grafentheorie):
  Het algoritme behandelt de kolommen van de constante matrix als knopen in een graaf. Door een Minimum Spanning Tree (MST) te berekenen met het algoritme van Prim, wordt de matrix ontbonden in twee submatrices ($M_1$ en $M_2$). Dit legt structurele gelijkenissen tussen verschillende kolommen bloot, waardoor redundante berekeningen op hoog niveau worden verminderd.

• Fase 2: Cost-aware Common Subexpression Elimination (CSE):
  Op de submatrices wordt CSE toegepast om identieke berekeningen te identificeren en te hergebruiken. In tegenstelling tot eerdere methoden is dit proces "cost-aware": het houdt rekening met de bitbreedte en de bit-shifts van de operanden. Hierdoor worden subexpressies die de kleinste impact hebben op de hardware-kosten (zoals het aantal benodigde adders) met voorrang geïmplementeerd.

Het algoritme behoudt de volledige numerieke precisie (geen benadering), wat cruciaal is voor reeds sterk gekwantiseerde netwerken.

3. Belangrijkste Bijdragen

• Nieuw Algoritme: Een hybride algoritme met een asymptotische complexiteit van $O(N^2)$, wat ongeveer vijf ordes van grootte sneller is dan de huidige state-of-the-art ($H_{cmvm}$).
• Open-source Integratie: Het framework is volledig open-source en direct geïntegreerd in de populaire hls4ml bibliotheek. Dit maakt het een "drop-in" oplossing voor de wetenschappelijke gemeenschap.
• RTL Generatie: Naast HLS (High-Level Synthesis) ondersteunt da4ml directe generatie van synthesiseerbare RTL (Verilog/VHDL), wat snellere prototyping mogelijk maakt.

4. Resultaten en Evaluatie

De prestaties zijn getest op zowel synthetische benchmarks als realistische neurale netwerken voor de LHC:

• Efficiëntie: Het algoritme kan het gebruik van on-chip resources (voornamelijk LUT's) met tot wel een derde verminderen.
• DSP-reductie: In veel gevallen worden de Digital Signal Processors (DSP's) volledig geëlimineerd, omdat de berekeningen efficiënt naar de LUT's worden verplaatst.
• Snelheid: De compilatietijd is drastisch verkort. Voor grote netwerken (zoals de particle-based jet tagging netwerken) is de synthesetijd met directe RTL-generatie gereduceerd van ~17 uur (via HLS) naar slechts ~26 minuten.
• Real-world impact: Het heeft succesvol bijgedragen aan de productie-implementatie van de AXOL1TL anomaly detection trigger bij het CMS-experiment van CERN.

5. Betekenis (Significance)

Het werk van Sun et al. overbrugt de kloof tussen theoretische optimalisatie en praktische hardware-implementatie. Door een methode te bieden die zowel sneller is in berekening als efficiënter in hardwaregebruik, stelt da4ml onderzoekers in staat om complexere en nauwkeurigere neurale netwerken te implementeren op de strikte hardware-beperkingen van real-time systemen in de deeltjesfysica en andere edge-computing toepassingen.