A Hybrid Residue Floating Numerical Architecture with Formal Error Bounds for High Throughput FPGA Computation

Dit artikel introduceert de Hybrid Residue Floating Numerical Architecture (HRFNA), een nieuwe numerieke architectuur voor FPGA's die residuele rekenkunde combineert met exponentiële schaling om een hoge doorvoer en energie-efficiëntie te bereiken met formele foutgrenzen, wat aanzienlijke prestatieverbeteringen oplevert ten opzichte van de IEEE 754 FP32-standaard.

De kern

Stel je voor dat je een enorme, super-snelle fabriek bouwt op een chip (een FPGA) om ingewikkelde wiskundige berekeningen te doen. De huidige standaardmethode om deze berekeningen te doen, is als het gebruik van dure, zware vrachtwagens voor elke kleine klus. Deze "vrachtwagens" (de huidige drijvende-kommamethode) zijn heel nauwkeurig, maar ze zijn traag, verbruiken veel brandstof (energie) en nemen veel ruimte in op je fabrieksterrein.

Deze paper introduceert een nieuw systeem, genaamd HRFNA. Laten we dit uitleggen met een paar simpele vergelijkingen.

1. Het Probleem: De Zware Vrachtwagens

Huidige computers gebruiken een methode die lijkt op het schrijven van getallen met een komma (zoals 3,14 of 0,0005). Om dit te doen, moet de computer bij elke berekening:

• De "komma's" op elkaar afstemmen (zoals twee mensen die proberen te praten terwijl ze verschillende talen spreken).
• Controleren of het getal niet te groot of te klein wordt.
• Ronding toepassen (afronden).

Dit is als een vrachtwagen die bij elke stop moet parkeren, de motor uitdoen, de lading controleren en dan pas weer kan rijden. Het kost tijd en energie.

2. De Oplossing: De HRFNA Fabriek

De auteurs van dit paper hebben een nieuw systeem bedacht dat twee slimme ideeën combineert:

Deel A: De "Reste" (Residue) Methode – De Snelle Fietsen
In plaats van één grote vrachtwagen, gebruiken ze een flotterend team van fietsers.

• Stel je voor dat je een enorm getal moet vermenigvuldigen. In plaats van dat één persoon dat doet, splits je het getal op in kleine stukjes (zoals resten van een taart).
• Elke fietser (een kleine rekenunit) doet zijn eigen stukje van de taart zonder te hoeven wachten op de ander. Er is geen "wachtrij" (geen "carry propagation").
• Dit is extreem snel en verbruikt weinig energie, omdat iedereen tegelijkertijd werkt.

Deel B: De "Schaal" (Exponent) – De Regisseur
Het probleem met alleen fietsers is dat je niet weet hoe groot het totale resultaat is. Daarom hebben ze een regisseur toegevoegd.

• Deze regisseur houdt een simpele notitie bij: "We zijn nu 10 keer groter dan gisteren" of "We zijn 100 keer kleiner".
• De regisseur hoeft niet bij elke berekening in te grijpen. Hij kijkt alleen af en toe: "Hebben we de grens bereikt? Moeten we de schaal aanpassen?"
• Als dat nodig is, doet hij een snelle aanpassing (normalisatie). Dit gebeurt maar heel zelden.

3. Hoe het werkt in de praktijk

Stel je een lange rij auto's voor die een tunnel doorrijden (een berekening).

• Oude methode: Elke auto moet bij elke kilometerpaal stoppen, zijn snelheid controleren, de banden checken en dan pas verder. (Traag, veel energie).
• Nieuwe methode (HRFNA): De auto's rijden razendsnel door de tunnel zonder te stoppen. Alleen als ze bijna de muur raken (te groot) of de tunnel uit de mist komen (te klein), stopt één auto even om de regisseur te bellen. De regisseur zegt dan: "Oké, we verplaatsen de hele groep een stukje naar voren/achteren."
• De rest van de auto's rijden gewoon door.

4. Waarom is dit geweldig?

De onderzoekers hebben dit systeem gebouwd op een chip en getest. Het resultaat is verrassend:

• Snelheid: Het is tot 2,4 keer sneller dan de oude methode.
• Energie: Het verbruikt veel minder stroom (tot 50% minder).
• Nauwkeurigheid: Het is net zo nauwkeurig als de oude methode, maar dan zonder de "stop-en-check" kosten.
• Stabiliteit: Zelfs als je heel lang blijft rekenen (zoals bij het voorspellen van weer of het oplossen van complexe formules), blijft het systeem stabiel en maakt het geen fouten die opstapelen.

Samenvatting

De auteurs hebben een manier gevonden om wiskunde op chips te doen die snel is als een fietsrenner (door de "reste-methode") maar slim is als een regisseur (door de schaal-methode).

In plaats van te proberen de perfecte, zware vrachtwagen te bouwen, hebben ze een systeem ontworpen dat de kracht van parallelle fietsers gebruikt, met een slimme regisseur die alleen ingrijpt als het echt nodig is. Dit maakt het perfect voor snelle, energiezuinige toepassingen zoals wetenschappelijke berekeningen, beeldverwerking en AI, zonder dat de nauwkeurigheid verloren gaat.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "A Hybrid Residue–Floating Numerical Architecture with Formal Error Bounds for High-Throughput FPGA Computation" in het Nederlands.

Titel: Een Hybride Restant–Vlottende Numerieke Architectuur met Formele Foutgrenzen voor Hoogdoorvoer FPGA-berekening

1. Het Probleem

Veldprogrammeerbare gate-arrays (FPGA's) zijn essentieel voor het versnellen van numeriek intensieve werklasten in wetenschappelijk rekenen en signaalverwerking. Echter, de implementatie van IEEE-754 zwevendekommabewerkingen op FPGA-fabrics is inherent duur en inefficiënt. Dit komt door:

• Brede datapaden en complexe normalisatie- en afrondingslogica.
• Uitgestelde draagpropagatie (carry propagation), wat de frequentie en het stroomverbruik beperkt.
• Een gebrek aan schaalbaarheid in diep gepipelined ontwerpen.

Bestaande alternatieven hebben ook tekortkomingen:

• Vaste komma (Fixed-point): Beperkt dynamisch bereik, wat problematisch is voor iteratieve algoritmen.
• Logaritmische getalsystemen (LNS): Verminderen vermenigvuldiging tot optelling, maar vereisen dure conversies voor optelling/aftrekking.
• Restantgetalsystemen (RNS): Bieden draagvrije, parallelle bewerkingen, maar lijden onder fundamentele beperkingen bij vergelijking, tekenherkenning, schaling en het representeren van breuken zonder dure reconstructie via de Chinese Reststelling (CRT).

Er ontbreekt een numerieke abstractie die tegelijkertijd draagvrije parallelle bewerkingen, een breed dynamisch bereik, gebonden fouten en hardware-efficiëntie biedt.

2. Methodologie: HRFNA

De auteurs introduceren de Hybrid Residue–Floating Numerical Architecture (HRFNA). Dit is een volledig gespecificeerd numeriek systeem dat de voordelen van restantgetalsystemen combineert met een lichtgewicht exponentiële schaling.

Kernprincipes:

• Scheiding van taken: De integer-waarden worden volledig in het restant-domein verwerkt (draagvrij en parallel), terwijl een globale exponent de schaal (dynamisch bereik) beheert.
• Formele Definitie: Een hybride getal wordt gedefinieerd als een paar $(\mathbf{r}, f)$, waarbij $\mathbf{r}$ een vector van restanten is en $f$ een exponent. De werkelijke waarde is $CRT(\mathbf{r}) \cdot 2^f$.
• Draagvrije Bewerkingen: Vermenigvuldiging en optelling gebeuren volledig parallel in de restantkanalen zonder draagpropagatie.
• Gecontroleerde Normalisatie: Normalisatie en afronding zijn geen per-operatie kosten, maar zeldzame, gestructureerde gebeurtenissen die alleen worden geactiveerd wanneer de magnitude een vooraf gedefinieerde drempel ($\tau$) overschrijdt.
• Foutanalyse: De auteurs leiden expliciete absolute en relatieve foutgrenzen af. Fouten worden uitsluitend geïntroduceerd tijdens de normalisatie, waardoor het systeem deterministisch en analyseerbaar is.
• Hardware-architectuur: De FPGA-implementatie gebruikt diep gepipelined modulaire arithmetiek, een exponent-beheerpad en een gescheiden CRT-gebaseerde normalisatie-engine. Dit zorgt voor een startinterval (initiation interval) van één cyclus in de steady-state.

3. Belangrijkste Bijdragen

1. Formeel Numeriek Model: Een wiskundig onderbouwde definitie van de hybride getalruimte met bewijzen voor correctheid en afleiding van foutgrenzen.
2. Architectuur: Een diep gepipelined FPGA-microarchitectuur die normalisatie ontkoppelt van de kritieke datapad, waardoor de doorvoer niet wordt beïnvloed door reconstructie- overhead.
3. Validatie op Applicatieniveau: Uitgebreide evaluatie op kernwerklasten zoals dot-products, dichte matrixvermenigvuldiging en iteratieve Runge-Kutta ODE-oplossers.
4. Vergelijkende Analyse: Een grondige vergelijking met IEEE-754 FP32, Block Floating-Point (BFP) en eerdere hybride systemen, die aantoont dat HRFNA een nieuw ontwerppunt beslaat.

4. Resultaten

De implementatie op een Xilinx Zynq UltraScale+ ZCU104 toont aanzienlijke verbeteringen ten opzichte van de IEEE-754 FP32-baselines:

• Doorvoer: Tot 2,4x hoger door de eliminatie van per-operatie normalisatie en draagpropagatie.
• Ressourcen: Een reductie van 38–55% in LUT-gebruik (Look-Up Tables).
• Energie-efficiëntie: Tot 1,9x verbetering.
• Numerieke Stabiliteit:
  • HRFNA behoudt een RMS-fout onder de $10^{-6}$ bij vector dot-products, vergelijkbaar met FP32.
  • In tegenstelling tot Block Floating-Point (waar fouten lineair groeien met de vectorlengte), blijft de fout in HRFNA gebonden en stabiel.
  • De Runge-Kutta ODE-oplosser toont stabiel gedrag over $10^6$ iteraties zonder divergentie, wat de geschiktheid voor langdurige iteratieve berekeningen bevestigt.
• Normalisatie-frequentie: Normalisatie vindt slechts zeer zelden plaats (eenmaal per duizenden bewerkingen), waardoor de CRT-reconstructie-overhead effectief wordt geamortiseerd.

5. Betekenis en Conclusie

Deze paper presenteert HRFNA als een praktisch en numeriek principieel alternatief voor conventionele zwevendekommaberekening op FPGA's. Het systeem vult een cruciale kloof in het ontwerplandschap door:

• De hardware-efficiëntie en parallelle aard van RNS te combineren met het dynamische bereik van zwevendekommaberekening.
• Formele foutgaranties te bieden die ontbreken bij veel bestaande hybride systemen.
• Een ontwerp te bieden dat specifiek is geoptimaliseerd voor CAD-gerelateerde en wetenschappelijke werklasten waarbij voorspelbaarheid, efficiëntie en schaalbaarheid centraal staan.

HRFNA is niet bedoeld als een universele vervanging voor IEEE-754, maar als een gespecialiseerde, hoog-efficiënte numerieke abstractie voor FPGA-centric acceleratie, waarbij de trade-off tussen strikte IEEE-compliance en voorspelbare, gebonden fouten met hoge doorvoer wordt gemaakt.