🔢 mathematics

Error Analysis of Matrix Multiplication Emulation Using Ozaki-II Scheme

Diese Arbeit präsentiert eine rigorose deterministische Fehleranalyse des Ozaki-II-Schemas für hochpräzise Matrixmultiplikation, klärt dessen Genauigkeitsbeschränkungen unter weiten Exponentenverteilungen auf und stellt eine Methode bereit, um die notwendige Anzahl an Niedrigpräzisionsoperationen zur Erreichung eines gewünschten Präzisionsniveaus abzuschätzen.

Ursprüngliche Autoren: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Veröffentlicht 2026-02-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Eine riesige Wand mit winzigen Ziegeln bauen

Stellen Sie sich vor, Sie sind ein Architekt, der versucht, eine massive, unglaublich präzise Wand (eine hochpräzise Berechnung) zu bauen, und dabei nur winzige, grobe Ziegel (Computerchips mit geringer Präzision) verwendet.

Moderne Computer, insbesondere solche, die für Künstliche Intelligenz entwickelt wurden, sind unglaublich schnell im Umgang mit diesen „winzigen, groben Ziegeln“ (speziell 8-Bit-Ganzzahlen). Sie sind jedoch langsam oder weniger effizient beim Umgang mit „riesigen, glatten Ziegeln“ (Standard-Hochpräzisionszahlen wie 32-Bit- oder 64-Bit-Fließkommazahlen).

Das Ozaki-II-Schema ist eine clevere Konstruktionsmethode, die es Ihnen ermöglicht, eine perfekte Hochpräzisionswand nur mit diesen schnellen, winzigen Ziegeln zu bauen. Die Autoren dieser Arbeit haben einen Bauplan (Fehleranalyse) erstellt, um zu beweisen, wie stark und genau diese Wand sein wird und wie viele winzige Ziegel Sie benötigen, um die Aufgabe korrekt zu erledigen.

Das Problem: Das Problem des „weiten Bereichs“

In früheren Tests funktionierte diese Methode hervorragend, aber es gab einen Haken. Wenn die Zahlen, die Sie multiplizierten, einen „weiten Bereich“ hatten (einige waren riesig, andere winzig klein), bekam die Wand manchmal Risse. Um dies zu beheben, musste man so viele winzige Ziegel verwenden, dass der Prozess wieder langsam wurde.

Die Autoren wollten wissen: Wie viele Ziegel benötigen wir genau, um eine perfekte Wand zu garantieren, egal wie weit der Bereich der Zahlen ist?

Die Lösung: Der „Chinesische Restsatz“-Zaubertrick

Um dies zu lösen, nutzt das Ozaki-II-Schema einen mathematischen Zaubertrick namens Chinesischer Restsatz (Chinese Remainder Theorem, CRT).

Die Analogie: Die geheimen Code-Schließfächer
Stellen Sie sich vor, Sie möchten das exakte Gewicht eines riesigen Elefanten wissen, aber Ihre Waage kann nur kleine Gegenstände wiegen (bis zu 100 Pfund).

Sie legen den Elefanten in ein Schließfach, das nur das Gewicht mod 7 anzeigt (den Rest bei der Division durch 7).
Sie legen ihn in ein zweites Schließfach, das das Gewicht mod 11 anzeigt.
Sie legen ihn in ein drittes, das mod 13 anzeigt.

Obwohl jedes Schließfach nur einen winzigen, verwirrenden Rest liefert, können Sie das exakte Gesamtgewicht des Elefanten mathematisch rekonstruieren, wenn Sie die Reste für mehrere verschiedene „Moduli“ (7, 11, 13 usw.) kennen.

Das Ozaki-II-Schema macht dies mit Matrizen (Zahlenrastern):

Zerlegung (Slicing): Es zerlegt die großen Zahlen in kleinere Stücke, die in die winzigen 8-Bit-Ziegel passen.
Modulo-Mathematik: Es berechnet das Ergebnis mithilfe dieser kleinen Stücke in vielen verschiedenen „Schließfächern“ (unter Verwendung verschiedener Primzahlen).
Rekonstruktion (Reassembly): Es verwendet den CRT, um all diese kleinen Ergebnisse wieder zu einer einzigen, riesigen, präzisen Antwort zusammenzufügen.

Was dieses Papier tatsächlich tut: Der „Sicherheitsinspektor“

Obwohl wir wussten, dass diese Methode funktionieren könnte, fehlte uns ein strenges Regelwerk darüber, wie gut sie in jeder Situation funktionieren würde. Dieses Papier fungiert als der Sicherheitsinspektor.

Die Autoren haben eine deterministische Fehleranalyse durchgeführt. Das bedeutet, sie haben nicht einfach nur geraten oder zufällige Tests durchgeführt; sie haben strenge Mathematik angewandt, um eine Formel aufzustellen, die den maximal möglichen „Riss“ (Fehler) in der finalen Wand vorhersagt.

Wichtigste Erkenntnisse der Inspektion:

Die Formel: Sie haben eine spezifische Gleichung hergeleitet, die Ihnen genau sagt, wie präzise das Ergebnis sein wird, basierend auf zwei Dingen:
1. Der „Breite“ der Zahlen, die Sie multiplizieren (Exponentendistribution).
2. Der Anzahl der „Schließfächer“ (Moduli), die Sie verwendet haben.
Der Kompromiss (Trade-off): Das Papier beweist, dass wenn die Zahlen sehr „weit“ sind (einige riesig, andere winzig), Sie einfach die Anzahl der Schließfächer (Moduli) erhöhen müssen, um den Fehler klein zu halten.
Validierung: Sie haben diese Formel auf einer leistungsstarken NVIDIA GPU (einer RTX 4090) getestet. Die tatsächlichen Fehler, die sie im Computer beobachteten, waren immer kleiner als die „Worst-Case“-Werte, die von ihrer Formel vorhergesagt wurden. Dies beweist, dass ihr Sicherheits-Bauplan genau und zuverlässig ist.

Warum das wichtig ist (laut dem Papier)

Das Papier behauptet, dass diese Analyse eine Grundlage für die automatische Abstimmung (Automatic Tuning) ist.

Denken Sie an eine selbstfahrende Baustelle. Früher musste ein Mensch raten, wie viele Ziegel verwendet werden müssen. Jetzt kann der Computer mit dieser Formel die Zahlen, die er gleich multiplizieren wird, betrachten, die „Breite“ der Daten berechnen und automatisch entscheiden: „Okay, für diesen speziellen Job brauche ich 15 Schließfächer, um sicher zu sein. Für den anderen Job brauche ich nur 5.“

Dies ermöglicht es dem Computer, die höchstmögliche Geschwindigkeit zu erreichen, ohne die Genauigkeit zu opfern, und stellt sicher, dass die „winzige Ziegel“-Methode sowohl schnell als auch vertrauenswürdig für das wissenschaftliche Rechnen ist.

Zusammenfassung

Das Ziel: Schnelle Computerchips mit geringer Präzision nutzen, um langsame, hochpräzise Mathematik zu betreiben.
Die Methode: Ein mathematischer Trick (CRT), um viele kleine, einfache Berechnungen zu einer einzigen großen, präzisen Berechnung zusammenzufügen.
Der Beitrag des Papiers: Es liefert eine strikte mathematische Garantie (eine Fehlerschranke), die genau angibt, wie präzise das Ergebnis sein wird und wie viele kleine Berechnungen nötig sind, um ein gewünschtes Maß an Präzision zu erreichen.
Das Ergebnis: Die Methode wurde als zuverlässig bewiesen, und die neue Formel ermöglicht es Computern, ihre Einstellungen automatisch anzupassen, um das beste Gleichgewicht zwischen Geschwindigkeit und Genauigkeit zu finden.

Technische Zusammenfassung: Fehleranalyse der Matrixmultiplikations-Emulation mittels des Ozaki-II-Schemas

Problemstellung
Moderne KI-Hardware, insbesondere GPUs, die mit INT8-Matrix-Engines ausgestattet sind, bietet einen außergewöhnlichen Durchsatz für niederpräzise Arithmetik und übertrifft damit die nativen Single- (FP32) und Double-Precision- (FP64) Gleitkommaoperationen signifikant. Während jedoch klassische Hochleistungsrechnen-Anwendungen (HPC) und viele Machine-Learning-Workloads die numerische Zuverlässigkeit höherer Präzision erfordern, existieren Emulationsmethoden, um hochpräzise Ergebnisse durch Sequenzen von niederpräzisen Operationen zu rekonstruieren. Die Genauigkeit dieser Methoden ist jedoch nicht über alle Eingangsverteilungen hinweg garantiert. Speziell das Ozaki-II-Schema, welches den Chinesischen Restsatz (CRT) zur Emulation der Matrixmultiplikation nutzt, hat eine hohe Performance demonstriert, aber es mangelt ihm an einer rigorosen deterministischen Fehleranalyse. Vorherige Studien stellten fest, dass die Genauigkeit des Schemas abnimmt, wenn die Eingangsmatrizen eine weite Exponentenverteilung aufweisen, was eine große Anzahl von niederpräzisen Multiplikationen erfordert, um die Präzision aufrechtzuerhalten. Ohne eine theoretische Schranke ist es schwierig, die Anzahl der benötigten Moduli zu bestimmen, um ein spezifisches Genauigkeitsziel zu erreichen.

Methodik
Die Arbeit präsentiert eine rigorose deterministische Fehleranalyse für das Ozaki-II-Schema angewandt auf General Matrix-Matrix Multiplication (GEMM) sowohl in Single- (SGEMM) als auch in Double-Präzision (DGEMM). Die Methodik umfasst:

Formalisierung des Ozaki-II-Schemas: Die Autoren detaillieren den Emulationsprozess, der die Gleitkomma-Matrizen $A$ und $B$ via diagonaler Skalierung und Trunkierung in Ganzzahlmatrizen $A'$ und $B'$ umwandelt. Diese Ganzzahlen werden dann modulo paarweise teilerfremder Ganzzahlen $p_\ell$ zerlegt. Die Produkte werden unter Verwendung von INT8-Matrix-Engines berechnet, und die Ergebnisse werden mittels des CRT rekonstruiert, um eine Ganzzahl-Approximation des Produkts zu bilden, welche schließlich in das Gleitkommaformat reskaliert wird.
Ableitung von Fehlerschranken: Die Autoren zerlegen den Gesamtfehler in drei primäre Komponenten:
- Trunkierungsfehler (Abschneidefehler): Resultierend aus der Konvertierung von Gleitkomma-Eingängen in skalierte Ganzzahlen.
- Akkumulationsfehler: Resultierend aus der Summation modularer Produkte in hochpräziser Gleitkomma-Arithmetik.
- Finaler Reduktionsfehler: Auftretend während der CRT-Rekonstruktion und der Reskalierungsschritte.
Theoretische Beweise: Das Paper liefert formale Beweise für eine Reihe von Lemmata, die die Eindeutigkeit der Kandidatenlösung, Schranken für Trunkierungs- und Akkumulationsfehler sowie die Gültigkeit der verwendeten Rundungsoperationen bei der Rekonstruktion etablieren. Diese Lemmata kulminieren in Theorem 2, welches eine deterministische obere Schranke für den Fehler $|AB - C_b|$ liefert, wobei $C_b$ das berechnete Ergebnis darstellt.
Experimentelle Validierung: Numerische Experimente wurden auf einer NVIDIA GeForce RTX 4090 GPU durchgeführt. Die abgeleiteten theoretischen Fehlerschranken wurden gegen beobachtete numerische Fehler für Matrizen mit variierenden Dynamikbereichen (gesteuert durch einen Parameter $\phi$ ) verglichen.

Zentrale Beiträge

Rigorose deterministische Fehleranalyse: Der primäre Beitrag ist die Ableitung einer deterministischen Fehlerschranke (Theorem 2) für das Ozaki-II-Schema. Diese Schranke setzt den numerischen Fehler explizit in Beziehung zur Exponentenverteilung der Eingangsmatrizen und der Anzahl der verwendeten Moduli ( $N$ ) im CRT.
Verfeinerte Schranken: Das Paper bietet zwei Formen der Fehlerschätzung an: eine engere Schranke (Eq. 16), die vom Betrag des intermediären Ganzzahlprodukts $|A'B'|$ abhängt, und eine konservativere, aber rechentechnisch günstigere Schranke (Eq. 20), die diesen Term durch eine konstante obere Schranke ersetzt.
Validierung des Genauigkeitsverhaltens: Die Analyse erklärt theoretisch, warum die Genauigkeit des Schemas von der Exponentenverteilung der Eingangsmatrizen abhängt, und bestätigt, dass eine Erhöhung der Anzahl der Moduli den Trunkierungsfehler reduziert und somit die Genauigkeit verbessert.
Nachweis der Korrektheit von Implementierungsdetails: Die Autoren beweisen, dass spezifische Implementierungswahlen, wie die Verwendung von Double-Double-Arithmetik für Konstanten und der spezifische Umgang mit INT8-Wrapping, keine unbeschränkten Fehler einführen, die das Endergebnis gefährden würden.

Ergebnisse

Theoretischer vs. beobachteter Fehler: Numerische Experimente auf der RTX 4090 zeigten, dass die beobachteten Emulationsfehler für sowohl SGEMM als auch DGEMM konsistent durch die in Theorem 2 abgeleiteten theoretischen Schätzungen begrenzt sind.
Schrankengüte: Die engere Schranke (Eq. 16) erwies sich als genauer bei der Erfassung der beobachteten Fehlerbereiche im Vergleich zur konservativen Schranke (Eq. 20). Dennoch wurde gezeigt, dass die konservative Schranke für eine robuste Fehlerschätzung praktikabel ist, da sie nur auf Matrix-Vektor-Produkten basiert, statt auf dem potenziell rechenintensiven $|A'B'|$ .
Vergleich mit nativer Präzision: Die Ergebnisse illustrierten die relative Genauigkeit der Emulation im Vergleich zu nativen FP32- und FP64-Routinen und bestätigten, dass das Ozaki-II-Schema bei entsprechender Konfiguration der Anzahl der Moduli eine hohe Präzision erreichen kann.

Bedeutung
Das Paper behauptet, dass diese Fehleranalyse eine kritische Grundlage für die zukünftige Entwicklung des Ozaki-II-Schemas bildet. Insbesondere ermöglicht sie die automatische Abstimmung von genauigkeitsbezogenen Parametern, wie etwa der Anzahl der Moduli, basierend auf der Exponentenverteilung der Eingangsmatrizen, um ein gewünschtes Maß an numerischer Genauigkeit zu erreichen. Durch die Klärung des Zusammenhangs zwischen Eingangscharakteristika und numerischer Zuverlässigkeit adressiert die Analyse die Lücke zwischen der hohen Performance des Schemas und seiner variablen Genauigkeit, was es für das allgemeine Hochpräzisionsrechnen auf moderner KI-Hardware praktikabler macht. Die Autoren merken an, dass dieser analytische Rahmen in zukünftiger Arbeit auch auf die Emulation komplexwertiger Matrixmultiplikationen erweitert werden könnte.