🔢 mathematics

Error Analysis of Matrix Multiplication Emulation Using Ozaki-II Scheme

Dit artikel presenteert een rigoureuze deterministische foutenanalyse van het Ozaki-II-schema voor hoogprecisie matrixvermenigvuldiging, waarbij de nauwkeurigheidsbeperkingen bij brede exponentdistributies worden verduidelijkt en een methode wordt geboden om het benodigde aantal lage-precisie-operaties te schatten om een gewenst precisieniveau te bereiken.

Oorspronkelijke auteurs: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Gepubliceerd 2026-02-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Gigantische Muur Bouwen met Kleine Steentjes

Stel je voor dat je een architect bent die probeert een enorme, ongelooflijk nauwkeurige muur te bouwen (een hoogprecisieberekening) met alleen maar kleine, ruwe steentjes (computers met lage precisie).

Moderne computers, vooral die ontworpen voor Kunstmatige Intelligentie, zijn razendsnel in het verwerken van deze "kleine, ruwe steentjes" (specifiek 8-bit integers). Echter, ze zijn traag of minder efficiënt bij het verwerken van "reusachtige, gladde stenen" (standaard hoogprecisenummers zoals 32-bit of 64-bit floats).

Het Ozaki-II schema is een slimme constructiemethode waarmee je een perfecte hoogprecisiemuur kunt bouwen met alleen die snelle, kleine steentjes. De auteurs van dit paper hebben een blauwdruk (foutanalyse) gemaakt om te bewijzen hoe sterk en nauwkeurig deze muur precies zal zijn, en hoeveel kleine steentjes je nodig hebt om de klus goed te klaren.

Het Probleem: Het "Brede Bereik" Probleem

In eerdere tests werkte deze methode geweldig, maar er was een addertje onder het gras. Als de getallen die je vermenigvuldigde een "breed bereik" hadden (sommigen waren enorm groot, anderen heel klein), ontstonden er soms scheurtjes in de muur. Om dit op te lossen, moest je zóveel kleine steentjes gebruiken dat het proces weer traag werd.

De auteurs wilden weten: Hoeveel steentjes hebben we precies nodig om een perfecte muur te garanderen, ongeacht hoe breed het bereik van de getallen ook is?

De Oplossing: De "Chinese Reststelling" Magische Truc

Om dit op te lossen, gebruikt het Ozaki-II schema een wiskundige magische truc genaamd de Chinese Reststelling (Chinese Remainder Theorem - CRT).

De Analogie: De Geheime Code-kluisjes
Stel je voor dat je het exacte gewicht van een reusachtige olifant wilt weten, maar je weegschaal kan alleen kleine voorwerpen wegen (tot 100 lbs).

Je plaatst de olifant in een kluisje dat alleen het gewicht laat zien mod 7 (de restwaarde bij deling door 7).
Je plaatst hem in een ander kluisje dat het gewicht laat zien mod 11.
Je plaatst hem in een derde die laat zien mod 13.

Hoewel elk kluisje je slechts een klein, verwarrend restgetal geeft, kun je met behulp van de wiskunde het exacte totale gewicht van de olifant reconstrueren als je de restwaarden voor verschillende "moduli" (7, 11, 13, enz.) kent.

Het Ozaki-II schema doet dit met matrices (roosters van getallen):

Slicing (Snijden): Het breekt de grote getallen af in kleinere stukjes die passen in de kleine 8-bit steentjes.
Modulo Rekenen: Het berekent het resultaat met deze kleine stukjes in veel verschillende "kluisjes" (met behulp van verschillende priemgetallen).
Reassemblage (Herassemblage): Het gebruikt de CRT om al die kleine resultaten weer aan elkaar te naaien tot één gigantisch, nauwkeurig antwoord.

Wat dit Paper Eigenlijk Doet: De "Veiligheidsinspecteur"

Hoewel we wisten dat deze methode zou kunnen werken, hadden we geen strikt regelboek dat aangaf hoe goed het in elke situatie zou werken. Dit paper fungeert als de Veiligheidsinspecteur.

De auteurs hebben een deterministische foutanalyse uitgevoerd. Dit betekent dat ze niet simpelweg gokten of willekeurige tests uitvoerden; ze gebruikten strikte wiskunde om een formule op te stellen die de maximale mogelijke "scheur" (fout) in de uiteindelijke muur voorspelt.

Belangrijkste bevindingen van de inspectie:

De Formule: Ze hebben een specifieke vergelijking afgeleid die precies vertelt hoe nauwkeurig het resultaat zal zijn op basis van twee dingen:
1. De "breedte" van de getallen die je vermenigvuldigt (exponentdistributie).
2. Het aantal "kluisjes" (moduli) dat je hebt gebruikt.
De Afweging: Het paper bewijst dat als de getallen zeer "breed" zijn (sommigen enorm groot, anderen heel klein), je simpelweg het aantal kluisjes (moduli) moet verhogen om de fout klein te houden.
Validatie: Ze hebben deze formule getest op een krachtige NVIDIA GPU (een RTX 4090). De werkelijke fouten die ze in de computer zagen, waren altijd kleiner dan de "worst-case" scenario's die door hun formule werden voorspeld. Dit bewijst dat hun veiligheidsblauwdruk accuraat en betrouwbaar is.

Waarom dit Belangrijk is (Volgens het Paper)

Het paper beweert dat deze analyse een fundament is voor automatische afstemming (automatic tuning).

Denk aan een zelfrijdende bouwploeg. Voorheen moest een mens raden hoeveel steentjes er nodig waren. Nu, met deze formule, kan de computer kijken naar de getallen die hij gaat vermenigvuldigen, de "breedte" van de data berekenen en automatisch beslissen: "Oké, voor deze specifieke klus heb ik 15 kluisjes nodig om veilig te zijn. Voor die andere klus heb ik er maar 5 nodig."

Dit stelt de computer in staat om de hoogst mogelijke snelheid te behalen zonder de nauwkeurigheid op te offeren, waardoor wordt gegarandeerd dat de "kleine steentjes"-methode zowel snel als betrouwbaar is voor wetenschappelijke berekeningen.

Samenvatting

Het Doel: Snelle, laag-precisie computerchips gebruiken om langzame, hoog-precisie wiskunde uit te voeren.
De Methode: Een wiskundige truc (CRT) gebruiken om veel kleine, eenvoudige berekeningen samen te voegen tot één groot, nauwkeurig antwoord.
De Bijdrage van het Paper: Het biedt een strikte wiskundige garantie (een foutgrens) die precies vertelt hoe nauwkeurig het resultaat zal zijn en hoeveel kleine berekeningen nodig zijn om een gewenst niveau van precisie te bereiken.
Het Resultaat: De methode is bewezen betrouwbaar en de nieuwe formule stelt computers in staat om hun instellingen automatisch aan te passen voor de beste balans tussen snelheid en nauwkeurigheid.

Technische Samenvatting: Foutanalyse van Matrixvermenigvuldigingsemulatie met behulp van het Ozaki-II-schema

Probleemstelling
Moderne AI-hardware, met name GPU's uitgerust met INT8-matrixengines, biedt een uitzonderlijke doorvoer voor precisiearme rekenkundige operaties, wat aanzienlijk beter presteert dan native single- (FP32) en double-precision (FP64) floating-point operaties. Hoewel emulatiemethoden bestaan om hoog-precisie resultaten te reconstrueren met behulp van sequenties van laag-precisie operaties, is de nauwkeurigheid van deze methoden niet gegarandeerd over alle inputdistributies. Specifiek heeft het Ozaki-II-schema, dat het Chinese Reststelling (CRT) gebruikt om matrixvermenigvuldiging te emuleren, een hoge prestatie aangetoond, maar het ontbreekt aan een rigoureuze deterministische foutanalyse. Eerdere studies merkten op dat de nauwkeurigheid van het schema afneemt wanneer de inputmatrices een brede exponentdistributie bezitten, wat een groot aantal laag-precisie vermenigvuldigingen vereist om de precisie te handhaven. Zonder een theoretische bovengrens is het moeilijk om te bepalen hoeveel moduli vereist zijn om een specifieke nauwkeurigheidsdoelstelling te bereiken.

Methodologie
Het artikel presenteert een rigoureuze deterministische foutanalyse voor het Ozaki-II-schema toegepast op General Matrix-Matrix Multiplication (GEMM) in zowel single (SGEMM) als double (DGEMM) precisie. De methodologie omvat:

Formalisering van het Ozaki-II-schema: De auteurs beschrijven het emulatieproces, dat floating-point matrices $A$ en $B$ omzet in integer matrices $A'$ en $B'$ via diagonale schaling en truncatie. Deze integers worden vervolgens gedecomposeerd modulo onderling relatief priemgetallen $p_\ell$ . De producten worden berekend met INT8 matrixengines, en de resultaten worden gereconstrueerd met behulp van de CRT om een integer benadering van het product te vormen, die tenslotte wordt geschaald naar floating-point formaat.
Afleiding van foutgrenzen: De auteurs deconstrueren de totale fout in drie primaire componenten:
- Truncatiefout: Voortkomend uit de conversie van floating-point inputs naar geschaalde integers.
- Accumulatiefout: Resulterend uit de sommatie van modulaire producten in hoog-precisie floating-point rekenkunde.
- Finale Reductiefout: Voorkomend tijdens de CRT-reconstructie en de schaalveranderingsstappen.
Theoretische Bewijzen: Het artikel levert formele bewijzen voor een reeks lemma's die de uniciteit van de kandidaatsoplossing vaststellen, grenzen aan de truncatie- en accumulatiefouten bepalen, en de geldigheid van de gebruikte afrondingsoperaties bij de reconstructie waarborgen. Deze lemma's culmineren in Stelling 2, die een deterministische bovengrens biedt voor de fout $|AB - C_b|$ , waarbij $C_b$ het berekende resultaat is.
Experimentele Validatie: Numerieke experimenten werden uitgevoerd op een NVIDIA GeForce RTX 4090 GPU. De theoretische foutgrenzen afgeleid uit de analyse werden vergeleken met geobserveerde numerieke fouten voor matrices met variërende dynamische bereiken (gecontroleerd door een parameter $\phi$ ).

Belangrijkste Bijdragen

Rigoureuze Deterministische Foutanalyse: De primaire bijdrage is de afleiding van een deterministische foutgrens (Stelling 2) voor het Ozaki-II-schema. Deze grens relateert de numerieke fout expliciet aan de exponentdistributie van de inputmatrices en het aantal moduli ( $N$ ) dat in de CRT wordt gebruikt.
Verfijnde Grenzen: Het artikel biedt twee vormen van foutschatting: een nauwere grens (Eq. 16) die afhankelijk is van de grootte van het intermediaire integer product $|A'B'|$ , en een conservatievere maar computationeel goedkopere grens (Eq. 20) die deze term vervangt door een constante bovengrens.
Validatie van Nauwkeurigheidsgedrag: De analyse verklaart theoretisch waarom de nauwkeurigheid van het schema afhangt van de exponentdistributie van de inputmatrices en bevestigt dat het verhogen van het aantal moduli de truncatiefout vermindert, waardoor de nauwkeurigheid verbetert.
Bewijs van Correctheid voor Implementatiedetails: De auteurs bewijzen dat specifieke implementatiekeuzes, zoals het gebruik van double-double rekenkunde voor constanten en de specifieke afhandeling van INT8 wrapping, geen onbegrensde fouten introduceren die het eindresultaat in gevaar brengen.

Resultaten

Theoretische vs. Geobserveerde Fout: Numerieke experimenten op de RTX 4090 toonden aan dat de geobserveerde emulatiefouten voor zowel SGEMM als DGEMM consistent begrensd worden door de theoretische schattingen afgeleid uit Stelling 2.
Grens-strakheid (Bound Tightness): De nauwere grens (Eq. 16) bleek de range van geobserveerde fouten nauwkeuriger te vangen dan de conservatieve grens (Eq. 20). De conservatieve grens werd echter als praktisch beschouwd voor robuuste foutschatting, omdat deze enkel steunt op matrix-vector producten in plaats van het potentieel dure $|A'B'|$ te berekenen.
Vergelijking met Native Precisie: De resultaten illustreerden de relatieve nauwkeurigheid van de emulatie vergeleken met native FP32 en FP64 routines, waarmee wordt bevestigd dat het Ozaki-II-schema een hoge precisie kan bereiken wanneer het is geconfigureerd met een gepast aantal moduli.

Significantie
Het artikel stelt dat deze foutanalyse een cruciaal fundament vormt voor de verdere ontwikkeling van het Ozaki-II-schema. Specifiek maakt het de automatische afstemming van nauwkeurigheidsgerelateerde parameters, zoals het aantal moduli, mogelijk op basis van de exponentdistributie van inputmatrices om een gewenst niveau van numerieke nauwkeurigheid te bereiken. Door de relatie tussen inputkenmerken en numerieke betrouwbaarheid te verhelderen, adresseert de analyse de kloof tussen de hoge prestaties van het schema en de variabele nauwkeurigheid, waardoor het levensvatbaarder wordt voor algemeen gebruik in high-precision computing op moderne AI-hardware. De auteurs merken op dat dit analytische kader in de toekomst ook uitgebreid kan worden naar de emulatie van complexe matrixvermenigvuldigingen.