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

Each language version is independently generated for its own context, not a direct translation.

De "Vierkant-Revolutie": Hoe je Rekenen Makkelijker en Goedkoper Maakt

Stel je voor dat je een enorme hoeveelheid rekenwerk moet doen, bijvoorbeeld om een AI (kunstmatige intelligentie) te laten leren of om een foto te verwerken. De basis van al dit werk is het vermenigvuldigen van getallen. In de wereld van computerchips is vermenigvuldigen echter een "zware jongen". Het is als het bouwen van een enorme, complexe fabriek die veel ruimte inneemt en veel stroom verbruikt.

Deze paper, geschreven door Vincenzo Liguori, introduceert een slimme truc: waarom zou je een zware fabriek bouwen als je een simpele, goedkope machine kunt gebruiken die bijna hetzelfde doet?

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het Grote Geheim: Vermenigvuldigen is een "Vierkant"

In de wiskunde weten we dat vermenigvuldigen ( $a \times b$ ) lastig is om te doen in hardware. Maar er is een wiskundige formule die zegt: "Als je twee getallen optelt en het resultaat kwadrateert (vermenigvuldigt met zichzelf), en daar de kwadraten van de losse getallen van aftrekt, krijg je precies het product."

Dit klinkt ingewikkeld, maar denk aan het volgende:

Vermenigvuldigen is alsof je een ingewikkeld puzzelstukje moet snijden uit een blok marmer. Dat kost veel tijd en energie.
Kwadrateren (Vierkantsverheffen) is alsof je datzelfde blok marmer in een vorm giet die al precies de juiste maat heeft. Het is veel sneller en goedkoper.

De auteur zegt: "Laten we stoppen met het snijden van het marmer (vermenigvuldigen) en in plaats daarvan de gietvorm gebruiken (kwadrateren)."

2. De Magie van de "Deelrekening"

Wanneer je een hele matrix (een groot rooster met getallen) vermenigvuldigt, moet je duizenden keer vermenigvuldigen. De paper stelt voor om dit te vervangen door kwadrateren.

De Truc: In plaats van $A \times B$ te berekenen, bereken je $(A+B)^2$ , trek je $A^2$ en $B^2$ af, en deel je door 2.
Het Voordeel: Een kwadraat-machine (een circuit dat een getal met zichzelf vermenigvuldigt) is ongeveer de helft zo groot en verbruikt de helft minder stroom dan een gewone vermenigvuldiger.

Het is alsof je in plaats van een dure, zware vrachtwagen (de vermenigvuldiger) een lichte, snelle scooter (de kwadraat-machine) gebruikt om dezelfde boodschappen te doen. Je moet misschien twee keer heen en weer rijden (extra stappen), maar omdat de scooter zo veel lichter is, bespaar je toch enorm veel benzine en ruimte in je garage.

3. Van Simpel naar Compleks: De "Drie-Square" Truc

De paper gaat nog verder. Wat als je met complexe getallen werkt (zoals in signaalverwerking of DFT)? Normaal heb je daar 4 vermenigvuldigingen voor nodig.

De Oude Weg: 4 zware vrachtwagens.
De Nieuwe Weg (4 squares): 4 scooter-varianten.
De Super-Truc (3 squares): De auteur toont aan dat je dit zelfs kunt doen met slechts 3 kwadraten per complexe vermenigvuldiging.

Dit is als het vinden van een nog slimmere route waar je maar 3 keer hoeft te stoppen in plaats van 4. Voor grote matrices (zoals die in AI) is het verschil in ruimte en energie enorm.

4. Hoe ziet dit eruit in de praktijk? (De Architectuur)

De paper beschrijft hoe je dit in chips bouwt:

Systolische Arrays: Denk hieraan als een productielijn in een fabriek. In plaats van dat elk station een zware vermenigvuldiger heeft, heeft elk station nu een snelle kwadraat-machine. De getallen "stroomt" door de lijn, worden gekwadrateerd, en aan het einde worden de losse stukjes (de extra aftrekkingen) erbij geteld.
Tensor Cores: Dit zijn de krachtige rekenmotoren in moderne videokaarten. De paper stelt voor om deze motoren te herschikken zodat ze in plaats van vermenigvuldigen, vooral kwadrateren.

5. Waarom is dit belangrijk voor jou?

Je merkt dit misschien niet direct, maar dit soort optimalisaties heeft grote gevolgen:

Minder Stroom: Je telefoon of laptop wordt minder warm en de batterij gaat langer mee.
Snellere AI: Omdat de chips kleiner en efficiënter zijn, kun je er meer van op een chip zetten. Dat betekent dat AI-apps sneller werken.
Kleinere Chips: De fabrikanten hoeven minder "ruimte" op de chip te gebruiken voor rekenwerk, waardoor ze goedkopere of krachtigere apparaten kunnen maken.

Samenvatting in één zin

Deze paper is een blauwdruk voor het vervangen van zware, energievretende vermenigvuldigers in computerchips door lichtere, snellere kwadraat-machines, waardoor we AI en signaalverwerking veel efficiënter en goedkoper kunnen maken.

Het is alsof we in plaats van met een hamer en beitel (vermenigvuldigen) te werken, een 3D-printer (kwadrateren) gebruiken om dezelfde vormen te maken: het resultaat is hetzelfde, maar het proces is veel slimmer en zuiniger.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplication and Convolutions" van Vincenzo Liguori, geschreven in het Nederlands.

1. Het Probleem

Matrixvermenigvuldigingen, convoluties en lineaire transformaties zijn fundamentele bewerkingen in kunstmatige intelligentie (AI), digitale signaalverwerking (DSP) en vele andere toepassingen. De implementatie van deze bewerkingen vereist doorgaans een groot aantal vermenigvuldigingen.

Hardwarekosten: Een vermenigvuldigingscircuit (multiplier) voor $n$ -bits data vereist aanzienlijk meer transistors (poortaantal) dan een kwadrateringscircuit (squaring circuit). Een kwadrateringscircuit vereist ongeveer de helft van het poortaantal van een equivalente $n \times n$ -multiplier.
Efficiëntie: Het verminderen van het aantal vermenigvuldigingen in hardware-architecturen (zoals systolische arrays en tensor cores) kan leiden tot aanzienlijke besparingen in chipoppervlak, energieverbruik en kosten, zonder de functionaliteit te verliezen.

2. Methodologie

De kern van de paper is een wiskundige herschrijving van vermenigvuldigingen in termen van kwadraten, gebaseerd op de algebraïsche identiteiten:

$(a+b)^2 = a^2 + b^2 + 2ab \Rightarrow ab = \frac{1}{2}((a+b)^2 - a^2 - b^2)$
$(a-b)^2 = a^2 + b^2 - 2ab \Rightarrow -ab = \frac{1}{2}((a-b)^2 - a^2 - b^2)$

Algoritme en Strategie:

Vervanging: In plaats van $a \times b$ direct te berekenen, wordt de som $(a+b)$ gekwadrateerd, waarna de individuele kwadraten ( $a^2$ en $b^2$ ) worden afgetrokken. Het resultaat wordt gedeeld door 2.
Herbruikbaarheid: Bij matrixvermenigvuldigingen en convoluties hangen de termen $a^2$ en $b^2$ vaak alleen af van de rij- of kolomindex. Deze kunnen vooraf worden berekend of tijdens de verwerking worden hergebruikt, waardoor ze geen extra "kostbare" berekening per element vereisen.
Complexiteit: Voor complexe getallen worden standaard methoden (zoals de Gaussische methode met 3 reële vermenigvuldigingen) aangepast en vervolgens vervangen door kwadraten.

3. Belangrijkste Bijdragen

A. Reële Matrixvermenigvuldiging

Methode: Elke vermenigvuldiging $a_{ik} \cdot b_{kj}$ wordt vervangen door $\frac{1}{2}((a_{ik}+b_{kj})^2 - a_{ik}^2 - b_{kj}^2)$ .
Optimalisatie: De termen $a_{ik}^2$ en $b_{kj}^2$ worden samengevat tot $S_{ai}$ en $S_{bj}$ , die per rij/kolom worden berekend en hergebruikt voor alle elementen in die rij/kolom.
Resultaat: Voor een matrix van grootte $M \times N \times P$ is het totale aantal kwadraten $MNP + MN + NP$ . De ratio tussen kwadraten en oorspronkelijke vermenigvuldigingen is $1 + \frac{1}{P} + \frac{1}{M}$. Voor grote matrices nadert deze ratio 1.

B. Complexe Matrixvermenigvuldiging

De paper presenteert twee benaderingen voor complexe getallen:

4 Kwadraten-methode: Gebaseerd op het splitsen van reële en imaginaire delen. Dit vereist asymptotisch 4 kwadraten per complexe vermenigvuldiging.
3 Kwadraten-methode: Een geoptimaliseerde variant die de algebraïsche structuur van complexe vermenigvuldiging (gebaseerd op 3 reële vermenigvuldigingen) gebruikt en deze omzet in kwadraten.
- Formule: $(a+bi)(c+di)$ wordt herschreven zodat er slechts 3 kwadraten nodig zijn die van beide indices afhangen.
- Resultaat: De ratio nadert 3 kwadraten per complexe vermenigvuldiging voor grote matrices.

C. Toepassingen op Andere Operaties

De techniek wordt uitgebreid naar:

Lineaire Transformaties (bijv. DCT, DFT): Waarbij coëfficiënten vaak constant zijn, waardoor de vooraf berekende kwadraten-termen ( $S_w$ ) kunnen worden voorgeprogrammeerd.
Convoluties en Correlaties: Zowel 1D als 2D convoluties. De kernel-weights kunnen als constant worden beschouwd, waardoor de overhead van het berekenen van de som van kwadraten over duizenden samples wordt gespreid.

D. Hardware-architecturen

De paper beschrijft concrete hardware-implementaties:

Gedeeltelijke Vermenigvuldigers (Partial Multipliers): Vervanging van standaard MAC's (Multiply-Accumulate) door een eenheid die sommen kwadrateert en correcte termen optelt/aftrekt.
Systolische Arrays: Aangepaste verwerkingselementen (PE's) die $S_a$ en $S_b$ termen in de stroom van data integreren.
Tensor Cores: Aangepaste architecturen voor AI-chips die de initiële accumulator-waarden instellen op basis van de vooraf berekende kwadraten ( $S_a + S_b$ ) en vervolgens de "gedeeltelijke producten" accumuleren.

4. Resultaten en Analyse

Resource Besparing: Omdat een kwadrateringscircuit ongeveer 50% minder poorten vereist dan een multiplier, leidt de vervanging van vermenigvuldigingen door kwadraten tot een aanzienlijke reductie in het totale poortaantal van de chip.
Asymptotische Efficiëntie:
- Reële vermenigvuldiging: 1 vermenigvuldiging $\approx$ 1 kwadraat (voor grote matrices).
- Complexe vermenigvuldiging: 1 vermenigvuldiging $\approx$ 3 kwadraten (in plaats van de gebruikelijke 4 of meer bij directe implementatie).
Schaling: De extra kosten voor het berekenen van de "correctie-termen" (de som van de kwadraten van de individuele elementen) zijn verwaarloosbaar bij grote matrices of bij het verwerken van grote datasets (zoals in AI-inferentie).

5. Significantie

De paper biedt een fundamentele doorbraak in de efficiëntie van digitale signaalverwerking en AI-hardware:

Kostenreductie: Het mogelijk maken van goedkopere en energiezuiniger hardware voor AI-modellen en DSP-toepassingen door het gebruik van minder complexe circuits.
Architectonische Flexibiliteit: De methode is generiek en toepasbaar op bestaande architecturen (systolische arrays, tensor cores, FIR/IIR filters) met minimale aanpassingen.
Toekomstperspectief: De techniek is ook relevant voor benaderende berekeningen (approximate computing), waarbij kwadrateringsfuncties nog efficiënter kunnen worden geïmplementeerd.

Kortom, het artikel bewijst dat het mogelijk is om de dominante vermenigvuldiging in rekenintensieve taken te vervangen door kwadratering, wat leidt tot aanzienlijke besparingen in hardware-oppervlak en stroomverbruik, zonder in te leveren op de nauwkeurigheid van de berekeningen.