Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplication and Convolutions

Diese Arbeit zeigt, dass sich bei Matrixmultiplikationen und Faltungen asymptotisch jede reelle Multiplikation durch eine einzige Quadrierung und jede komplexe Multiplikation durch drei Quadrierungen ersetzen lässt, was aufgrund des geringeren Hardwareaufwands für Quadrierer zu erheblichen Ressourcenreduktionen führt.

Das Wesentliche

Hier ist eine einfache Erklärung der wissenschaftlichen Arbeit von Vincenzo Liguori, verpackt in eine Geschichte mit alltäglichen Vergleichen.

Das große Problem: Die teuren Multiplizierer

Stellen Sie sich vor, Sie sind ein Koch in einer riesigen Küche (einem Computer-Chip), der Millionen von Rezepten gleichzeitig zubereiten muss. Die wichtigste Aufgabe dabei ist das Mischen von Zutaten. In der digitalen Welt nennt man das „Multiplizieren".

Normalerweise ist ein Multiplikator (die Maschine, die Zahlen multipliziert) wie ein schwerer, komplexer und teurer Industriemixer. Er braucht viel Platz auf der Arbeitsplatte (Chipfläche) und verbraucht viel Strom. Wenn Sie Tausende von Rezepten (z. B. für künstliche Intelligenz oder Bildverarbeitung) kochen müssen, werden diese Mixer zum Flaschenhals. Sie sind langsam, teuer und machen die Küche überfüllt.

Die geniale Lösung: Der einfache „Quadrat-Ofen"

Der Autor der Arbeit hat eine clevere Idee: Warum nutzen wir nicht einen viel einfacheren, günstigeren Ofen, der nur Quadrate berechnet?

Ein Quadrat zu berechnen (also eine Zahl mit sich selbst zu multiplizieren, z. B. $5 \times 5$) ist für einen Computer viel einfacher als zwei unterschiedliche Zahlen zu multiplizieren.

• Der Mixer (Multiplikator): Braucht viele Bauteile, ist schwer und teuer.
• Der Ofen (Quadrat-Rechner): Braucht nur die Hälfte der Bauteile, ist klein und spart enorm viel Strom.

Die Frage war: Können wir unsere komplexen Rezepte so umschreiben, dass wir statt des teuren Mixers nur den billigen Ofen benutzen?

Der Trick: Die „Zerlegungs-Formel"

Liguori zeigt, dass man jede Multiplikation ($a \times b$) in eine Formel umwandeln kann, die nur Quadrate nutzt. Es ist wie ein mathematischer Zaubertrick:

Statt $a$ und $b$ direkt zu mischen, tun wir folgendes:

1. Wir addieren sie ($a+b$) und machen ein Quadrat daraus.
2. Wir machen ein Quadrat aus $a$ allein.
3. Wir machen ein Quadrat aus $b$ allein.
4. Wir subtrahieren die Einzelergebnisse vom Summenergebnis.

Die Analogie:
Stellen Sie sich vor, Sie wollen wissen, wie viel Fläche zwei verschiedene Teppiche zusammen haben, wenn sie nebeneinander liegen.

• Der alte Weg: Messen Sie Teppich A, messen Sie Teppich B, multiplizieren Sie die Maße.
• Der neue Weg: Legen Sie beide Teppiche zusammen zu einem großen Quadrat, messen Sie das große Quadrat. Dann messen Sie die einzelnen Teppiche nochmal als Quadrate. Die Differenz gibt Ihnen die gesuchte Information.

Das klingt erst einmal komplizierter (man muss mehr messen), aber da das „Messen als Quadrat" (der Ofen) so viel billiger und schneller ist als das „Mischen" (der Mixer), gewinnt man am Ende enorm.

Anwendung in der Praxis

Die Arbeit zeigt, wie man diesen Trick überall anwendet:

1. Matrix-Multiplikation (Das große Kochen):
   Wenn Computer riesige Datenblöcke (Matrizen) verarbeiten, müssen sie Millionen von Multiplikationen durchführen.

   • Früher: 1000 teure Mixer.
   • Jetzt: Man nutzt den Trick. Man braucht fast genauso viele Quadrate wie vorher Multiplikationen, aber da die Quadrate so billig sind, spart man massiv Platz und Energie.
   • Besonderheit: Bei großen Datenmengen kann man einige der Quadrate im Voraus berechnen (wie eine vorbereitete Soße), was den Prozess noch schneller macht.

2. Komplexe Zahlen (Das Kochen mit zwei Farben):
   Manchmal müssen wir mit komplexen Zahlen rechnen (Realteil + Imaginärteil). Das ist wie Kochen mit zwei verschiedenen Farben von Teig, die nicht vermischt werden dürfen.

   • Früher: Man brauchte 4 Mixer für eine komplexe Aufgabe.
   • Neu (Variante 1): Man braucht 4 billige Öfen.
   • Neu (Variante 2 - Der Super-Trick): Mit einer noch clevereren Umstellung reicht es, nur 3 Öfen zu benutzen, um die Arbeit eines komplexen Mixers zu erledigen.

3. Hardware-Architekturen (Die neue Küche):
   Der Autor beschreibt, wie man diese neuen Öfen in die Hardware einbaut:

   • Systolische Arrays: Stellen Sie sich eine Fließbandküche vor, wo Zutaten von Hand zu Hand weitergegeben werden. Statt dass jeder Handwerker einen Mixer hat, hat jeder nur einen Ofen.
   • Tensor Cores: Das sind die Hochleistungs-Kochstationen in modernen Grafikkarten (GPUs). Wenn man diese mit „Ofen-Technik" statt „Mixer-Technik" baut, werden sie kleiner, schneller und verbrauchen weniger Strom.

Warum ist das wichtig?

Heute laufen unsere Smartphones, KI-Modelle und Autonomes Fahren auf riesigen Datenmengen. Diese Daten müssen ständig multipliziert werden.

• Platz: Da ein Quadrat-Rechner nur halb so viele Transistoren (Bauteile) braucht wie ein Multiplikator, passt mehr Leistung auf den gleichen Chip.
• Energie: Weniger Bauteile bedeuten weniger Stromverbrauch. Das ist entscheidend für Akkulaufzeiten in Handys und für die riesigen Rechenzentren, die KI betreiben.
• Geschwindigkeit: Einfachere Schaltungen können oft schneller arbeiten.

Fazit

Vincenzo Liguori hat im Grunde gesagt: „Warum bauen wir teure, schwere Lastwagen, wenn wir mit kleinen, schnellen Motorrädern das gleiche Ziel erreichen können, wenn wir nur die Route ein bisschen cleverer planen?"

Indem wir die mathematische Route ändern (von Multiplikation zu Quadrieren), können wir die Hardware revolutionieren. Wir ersetzen schwere, teure Multiplizierer durch leichte, günstige Quadrat-Rechner. Das Ergebnis: Schnellere, sparsamere und leistungsfähigere Computer für die Zukunft.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Fair and Square" von Vincenzo Liguori auf Deutsch:

Titel

Fair and Square: Ersetzen einer realen Multiplikation durch eine einzelne Quadrierung und einer komplexen Multiplikation durch drei Quadrierungen bei Matrixmultiplikation und Faltungen

1. Problemstellung

Matrixmultiplikationen, Faltungen (Convolutions) und lineare Transformationen sind fundamentale Operationen in Bereichen wie Künstlicher Intelligenz (KI), Digitaler Signalverarbeitung (DSP) und vielen anderen Anwendungen. Diese Operationen erfordern eine immense Anzahl von Multiplikationen.

• Herausforderung: Multiplizierer (Multiplier) sind in digitalen Schaltungen (Hardware) ressourcenintensiv. Ein $n$-Bit-Multiplizierer benötigt etwa doppelt so viele Gatter wie ein $n$-Bit-Quadrierer (Squaring Circuit).
• Ziel: Die Reduzierung des Hardware-Aufwands (Fläche und Leistungsaufnahme) durch die Ersetzung von Multiplikationen durch effizientere Quadrierungsoperationen, ohne die mathematische Korrektheit zu verlieren.

2. Methodik

Der Kern der vorgestellten Methode basiert auf der algebraischen Identität, die eine Multiplikation durch Quadrierungen ausdrückt.

Grundlegende Mechanismen:
Aus den binomischen Formeln $(a+b)^2 = a^2 + b^2 + 2ab$ und $(a-b)^2 = a^2 + b^2 - 2ab$ lässt sich das Produkt $ab$ wie folgt ableiten:
$$ab = \frac{1}{2} \left( (a+b)^2 - a^2 - b^2 \right)$$
$$-ab = \frac{1}{2} \left( (a-b)^2 - a^2 - b^2 \right)$$

Anwendung auf verschiedene Operationen:

1. Reale Matrixmultiplikation:

   • Das Produkt $c_{ij} = \sum a_{ik} b_{kj}$ wird umgeformt.
   • Der Term $(a_{ik} + b_{kj})^2$ wird als „partielle Multiplikation" berechnet.
   • Die Terme $a_{ik}^2$ und $b_{kj}^2$ sind unabhängig von der Summationsindex-Kombination und können separat berechnet und wiederverwendet werden (z. B. als Summe der Quadrate der Zeilen von A und Spalten von B).
   • Ergebnis: Für große Matrizen ($M, P \to \infty$) nähert sich das Verhältnis von Quadrierungen zu Multiplikationen dem Wert 1:1 an.

2. Komplexe Matrixmultiplikation (Ansatz 1: 4 Quadrierungen):

   • Durch Aufteilung in Real- und Imaginärteil und Anwendung der obigen Formeln auf die vier entstehenden Produkte werden 4 Quadrierungen pro komplexer Multiplikation benötigt.
   • Das asymptotische Verhältnis beträgt 4:1.

3. Komplexe Matrixmultiplikation (Ansatz 2: 3 Quadrierungen):

   • Durch eine geschickte Umformung der komplexen Multiplikation (ähnlich dem Algorithmus von Gauss oder Karatsuba, aber für Quadrierungen optimiert) können die Produkte so umgestellt werden, dass ein gemeinsamer Term $(c+a+b)^2$ genutzt wird.
   • Dies reduziert den Bedarf auf 3 Quadrierungen pro komplexer Multiplikation.
   • Das asymptotische Verhältnis beträgt 3:1.

4. Faltungen und Lineare Transformationen:

   • Die gleichen Prinzipien werden auf Faltungen (Convolution/Correlation) und lineare Transformationen (z. B. DFT) angewendet.
   • Da Kernel-Gewichte oft konstant sind, können die Summen ihrer Quadrate ($S_w$) vorab berechnet werden, was den Overhead weiter minimiert.

3. Hardware-Architekturen

Das Paper beschreibt mehrere Architekturen, die diese mathematischen Umformungen in Hardware umsetzen:

• Partielle Multiplizierer-Akkumulatoren (Partial Multiplier Accumulators): Ersetzen herkömmliche MAC-Einheiten (Multiply-Accumulate). Statt $a \times b$ wird $(a+b)^2$ berechnet, und die Korrekturterme werden hinzugefügt/subtrahiert.
• Systolische Arrays: Die Processing Elements (PEs) werden modifiziert, um Quadrierer statt Multiplizierer zu nutzen. Zusätzliche Eingänge ermöglichen das Einbringen der vorberechneten Korrekturterme ($S_a, S_b$).
• Tensor Cores: Die Architektur wird angepasst, um entweder auf MACs oder auf den neuen „Partial Multiplication"-Basis zu arbeiten. Bei komplexen Daten werden CPMs (Complex Partial Multipliers) oder CPM3s (mit 3 Quadrierungen) verwendet.
• Faltungs-Engines: Ähnliche Anpassungen für FIR- und IIR-Filter, wobei der gemeinsame Term $x^2$ nur einmal berechnet und von allen Pfaden subtrahiert wird.

4. Wichtige Ergebnisse

• Ressourceneffizienz: Da ein Quadrierer etwa die Hälfte der Gatter eines Multiplizierers benötigt, führt der Austausch zu einer signifikanten Reduktion der Chipfläche und des Stromverbrauchs.
• Asymptotische Effizienz:
  • Reale Operationen: 1 Quadrierung pro Multiplikation.
  • Komplexe Operationen: 3 Quadrierungen pro komplexer Multiplikation (im Vergleich zu den üblichen 4 Multiplikationen oder 3 Multiplikationen bei klassischen Optimierungen).
• Skalierbarkeit: Der Overhead durch die zusätzlichen Korrekturterme (Summen von Quadraten) wird bei großen Matrizen oder langen Faltungsfiltern vernachlässigbar, da diese Terme wiederverwendet werden.
• Flexibilität: Die Methode ist unabhängig von der spezifischen Implementierung des Quadrierers und kann auch für approximative Quadrierungen genutzt werden.

5. Bedeutung und Fazit

Die Arbeit zeigt einen fundamentalen Paradigmenwechsel in der Hardware-Implementierung arithmetischer Operationen auf. Anstatt Multiplizierer zu optimieren, ersetzt sie diese durch Quadrierer, die hardware-technisch günstiger sind.

• Für KI und DSP: Dies ermöglicht effizientere Beschleuniger (z. B. in TPUs oder spezialisierten ASICs) mit geringerem Energieverbrauch und kleinerer Fläche, was besonders für Edge-Computing und mobile Geräte entscheidend ist.
• Mathematische Eleganz: Die Arbeit demonstriert, wie klassische algebraische Identitäten genutzt werden können, um die Komplexität von Hardware-Designs zu reduzieren, ohne die Genauigkeit der Ergebnisse zu beeinträchtigen (bis auf den Skalierungsfaktor 2, der durch einen einfachen Bit-Shift korrigiert wird).

Zusammenfassend bietet das Paper einen praktikablen Weg, die Kosten für rechenintensive Operationen in der digitalen Signalverarbeitung drastisch zu senken, indem es die „teure" Multiplikation durch die „günstige" Quadrierung ersetzt.