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

Questo articolo dimostra che è possibile sostituire asintoticamente ogni moltiplicazione reale con un singolo quadrato e ogni moltiplicazione complessa con tre quadrati nelle moltiplicazioni di matrici e nelle convoluzioni, ottenendo così significativi risparmi di risorse hardware grazie alla minore complessità dei circuiti di elevamento al quadrato rispetto ai moltiplicatori.

L'essenziale

Ecco una spiegazione semplice e creativa del paper, pensata per chiunque, anche senza un background tecnico.

Il Titolo: "Giusto e Quadrato" (Fair and Square)

Immagina di dover costruire un muro enorme. Per farlo, hai bisogno di calcolare milioni di volte quanto pesa un mattello moltiplicato per un altro. Normalmente, per fare questo calcolo, usi una "macchina moltiplicatrice" complessa, costosa e che consuma molta energia.

Questo articolo di Vincenzo Liguori propone un trucco geniale: perché usare una macchina complessa se puoi usare una macchina più semplice?

L'idea è sostituire la moltiplicazione (che è difficile e costosa) con il quadrato (che è più facile e costa la metà).

---

1. Il Trucco Matematico: La Magia del Quadrato

Immagina di avere due numeri, A e B, e vuoi sapere quanto fanno moltiplicati tra loro ($A \times B$).
Invece di usare la moltiplicazione diretta, il paper ci dice: "Ehi, guarda qui!".

C'è una regola matematica antica:

Se prendi la somma di due numeri e la elevi al quadrato, ottieni: il quadrato del primo + il quadrato del secondo + due volte il prodotto.

In parole povere:
$$(A + B)^2 = A^2 + B^2 + 2 \times (A \times B)$$

Se vuoi trovare solo il prodotto ($A \times B$), puoi riorganizzare la formula:
$$A \times B = \frac{(A+B)^2 - A^2 - B^2}{2}$$

L'analogia:
Immagina di voler sapere quanto pesa un pacchetto misto (A e B insieme).

1. Pesare il pacchetto misto e fare il quadrato del peso è facile (è come schiacciare un palloncino: costa poco sforzo).
2. Pesare A da solo e B da solo e fare i loro quadrati è ancora più facile.
3. Sottraendo i pesi singoli dal peso misto, scopri quanto pesa la loro "interazione" (la moltiplicazione).

Il punto chiave è che fare un quadrato (elevare al quadrato) in un chip di computer richiede circa la metà dei transistor (i mattoncini della logica) rispetto a fare una moltiplicazione. È come passare da un camioncino pesante a una bicicletta per lo stesso viaggio: risparmi spazio e benzina (energia).

---

2. Dove si usa questo trucco?

Il paper dice che questo trucco funziona ovunque ci siano calcoli massicci, come:

• Intelligenza Artificiale (AI): Quando un computer "pensa" e riconosce un volto, sta facendo miliardi di moltiplicazioni tra numeri.
• Convoluzioni: Come quando un filtro foto sfoca un'immagine o quando un radar vede un aereo.
• Trasformate: Come quando trasformi un suono in una nota musicale (DFT).

In tutti questi casi, invece di usare le "macchine moltiplicatrici" (MAC), il paper propone di usare "macchine parziali" basate sui quadrati.

---

3. Come funziona nella pratica? (L'Analogia della Fabbrica)

Immagina una catena di montaggio (chiamata Systolic Array nel paper) dove i pezzi scorrono e vengono assemblati.

• Il metodo vecchio: Ogni pezzo passa davanti a un operaio che usa un martello pesante (il moltiplicatore) per unire due pezzi. È lento e stanca l'operaio.
• Il metodo nuovo (Square-based): Ogni pezzo passa davanti a un operaio che usa un timbro leggero (il quadratore).
  • Prima di iniziare, l'operaio calcola velocemente il "peso" dei pezzi singoli (i quadrati dei numeri).
  • Poi, quando i pezzi arrivano, li somma, li "timbra" (quadratura) e sottrae i pesi calcolati prima.
  • Alla fine, ottieni lo stesso risultato, ma hai usato un attrezzo più leggero e veloce.

Il vantaggio: Poiché il timbro (il circuito di quadratura) è la metà del martello (il moltiplicatore), puoi mettere il doppio degli operai nello stesso spazio, o usare la metà dell'energia.

---

4. E i numeri complessi? (Il trucco dei 3 quadrati)

Fino a qui abbiamo parlato di numeri normali (reali). Ma nell'AI e nelle telecomunicazioni si usano spesso numeri "complessi" (che hanno una parte reale e una immaginaria, come coordinate su una mappa 3D).

Moltiplicare due numeri complessi di solito richiede 4 moltiplicazioni reali.
Il paper mostra due modi per fare questo trucco:

1. Metodo classico: Sostituisci le 4 moltiplicazioni con 4 quadrati.
2. Metodo avanzato (Il "Super Trucco"): Usando un'altra formula matematica (quella di Gauss), puoi fare la stessa cosa con solo 3 quadrati.

L'analogia:
Immagina di dover cucire una giacca complessa.

• Il metodo vecchio ti chiede 4 ago e fili diversi.
• Il metodo nuovo ti dice: "Non serve! Con 3 ago e fili, se li usi in un ordine specifico, ottieni lo stesso risultato".

Questo è fondamentale perché ridurre da 4 a 3 operazioni significa un risparmio enorme quando si fanno miliardi di calcoli al secondo.

---

5. Perché dovremmo preoccuparcene?

Oggi i nostri telefoni e i server AI consumano molta energia e si scaldano. Questo perché i chip devono fare miliardi di moltiplicazioni al secondo.

Se riusciamo a sostituire ogni moltiplicazione con un quadrato (che costa la metà):

• Risparmio di spazio: I chip possono essere più piccoli.
• Risparmio di energia: I dispositivi durano di più a batteria e si scaldano meno.
• Velocità: Si possono fare più calcoli nello stesso tempo.

In sintesi

Il paper è come se un ingegnere dicesse:

"Smettetela di usare il martello per ogni chiodo! Se usate il trucco del quadrato, potete usare un cacciavite leggero. Funziona per costruire muri (matrici), per filtrare immagini (convoluzioni) e per tradurre suoni (trasformate). E se i numeri sono complicati, basta usare il cacciavite tre volte invece di quattro."

È un modo per rendere l'Intelligenza Artificiale e i calcoli scientifici più efficienti, economici e veloci, semplicemente cambiando il modo in cui pensiamo alla matematica di base.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Fair and Square" di Vincenzo Liguori, redatta in italiano.

Titolo

Fair and Square: Sostituzione di una moltiplicazione reale con un singolo quadrato e di una moltiplicazione complessa con tre quadrati nelle moltiplicazioni di matrici e nelle convoluzioni.

1. Il Problema

Le operazioni di moltiplicazione di matrici e convoluzioni sono fondamentali in campi come l'Intelligenza Artificiale (AI), l'elaborazione digitale dei segnali (DSP) e molte altre applicazioni. Tuttavia, l'implementazione hardware di queste operazioni richiede un numero elevato di moltiplicazioni, che sono circuiti complessi e costosi in termini di risorse (gate count) e potenza.
In particolare, un circuito di moltiplicazione a $n$ bit richiede circa il doppio dei gate rispetto a un circuito di elevamento al quadrato (squaring) dello stesso numero di bit. L'obiettivo del paper è ridurre drasticamente il consumo di risorse hardware sostituendo le moltiplicazioni con operazioni di elevamento al quadrato, che sono intrinsecamente più efficienti.

2. Metodologia

Il nucleo della metodologia si basa sull'identità algebrica fondamentale che permette di esprimere il prodotto di due numeri in termini di somme e differenze elevate al quadrato:
$$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)$$

L'autore applica questa trasformazione a diverse operazioni matematiche, sfruttando la possibilità di pre-calcolare o riutilizzare i termini che dipendono solo da un indice (ad esempio, la somma dei quadrati delle righe o delle colonne di una matrice).

Casi Analizzati:

1. Moltiplicazione di Matrici Reali:

   • La moltiplicazione standard $C_{ij} = \sum A_{ik} B_{kj}$ viene trasformata in una somma di quadrati di somme.
   • I termini $A_{ik}^2$ e $B_{kj}^2$ dipendono rispettivamente solo dall'indice $i$ o $j$. Possono essere calcolati una volta sola e riutilizzati per tutti gli elementi della matrice risultato.
   • Risultato: Per matrici di grandi dimensioni ($M, P \to \infty$), il rapporto tra operazioni di quadrato e moltiplicazioni tende a 1:1.

2. Trasformate Lineari e Convoluzioni (Reali):

   • Applicando la stessa logica a trasformate (es. DCT) e filtri FIR, si sostituiscono i moltiplicatori con "moltiplicatori parziali" basati su quadrati.
   • Se i coefficienti sono costanti, i termini di correzione possono essere pre-calcolati.

3. Moltiplicazione di Matrici Complesse:

   • Approccio a 4 quadrati: Sostituendo le parti reale e immaginaria separatamente con le identità sopra citate, si ottiene un rapporto asintotico di 4 quadrati per moltiplicazione complessa.
   • Approccio a 3 quadrati (Ottimizzato): Utilizzando una riformulazione della moltiplicazione complessa (simile all'algoritmo di Gauss per i numeri complessi che riduce da 4 a 3 moltiplicazioni reali, ma adattata ai quadrati), l'autore dimostra che è possibile raggiungere un rapporto asintotico di 3 quadrati per moltiplicazione complessa.
     • La formula chiave sfrutta la condivisione di termini comuni tra la parte reale e immaginaria, riducendo il numero totale di operazioni di quadrato necessarie.

3. Contributi Chiave

• Riduzione Asintotica delle Risorse: Dimostrazione che è possibile sostituire ogni moltiplicazione reale con un'operazione di quadrato e ogni moltiplicazione complessa con 3 (o 4) operazioni di quadrato, sfruttando il fatto che un circuito di quadrato richiede circa la metà dei gate di un moltiplicatore.
• Nuove Architetture Hardware: Proposta di diverse implementazioni hardware per sfruttare questa tecnica:
  • Array Systolic basati su Quadrati: Modifica dei Process Element (PE) per includere accumulatori di "moltiplicazione parziale" e l'iniezione dei termini di correzione ($S_a, S_b$).
  • Tensor Core: Adattamento dei Tensor Core esistenti per inizializzare gli accumulatori con i termini di correzione pre-calcolati invece di azzerarli.
  • Architetture per Convoluzioni: Modifiche ai filtri FIR/IIR e alle convoluzioni 2D per gestire i termini comuni ($x^2$) e i termini di kernel pre-calcolati.
• Generalizzazione: La tecnica è applicabile non solo alle moltiplicazioni di matrici, ma anche a prodotti scalari, trasformate lineari (DFT, DCT) e convoluzioni, sia in dominio reale che complesso.

4. Risultati e Analisi

• Efficienza dei Gate: Poiché un moltiplicatore $N \times N$ ha una complessità di gate significativamente superiore a un elevatore al quadrato $N$, la sostituzione porta a una riduzione significativa dell'area del chip e del consumo energetico.
• Rapporto Operativo:
  • Per matrici reali grandi, il costo è quasi equivalente a una sola operazione di quadrato per moltiplicazione.
  • Per matrici complesse, l'approccio a 3 quadrati riduce il costo operativo rispetto all'approccio standard a 4 quadrati, avvicinandosi ulteriormente all'efficienza delle moltiplicazioni reali.
• Scalabilità: Il metodo è particolarmente vantaggioso per matrici di grandi dimensioni (tipiche nell'AI moderna), dove i termini di overhead per il calcolo dei quadrati pre-calcolati ($S_a, S_b$) diventano trascurabili rispetto al totale delle operazioni.

5. Significato e Impatto

Il lavoro di Liguori offre un approccio innovativo per l'ottimizzazione hardware delle operazioni fondamentali dell'AI e del DSP.

• Impatto sull'Hardware: La possibilità di sostituire moltiplicatori complessi con circuiti di quadrato più semplici e compatti permette di progettare acceleratori (come GPU, TPU o ASIC dedicati) più efficienti dal punto di vista energetico e con una maggiore densità di calcolo.
• Flessibilità: La metodologia è indipendente dall'implementazione specifica del circuito di quadrato (può essere esatta o approssimata), rendendola adattabile a diverse tecnologie di processo.
• Rilevanza per l'AI: Data la natura ubiqua delle moltiplicazioni di matrici nel deep learning, questa tecnica potrebbe portare a un'accelerazione significativa delle inferenze e dell'addestramento, riducendo al contempo i costi energetici e l'impronta hardware.

In sintesi, il paper dimostra che sfruttando le proprietà algebriche dei quadrati e una gestione intelligente dei termini ricorrenti, è possibile ridefinire l'architettura dei calcoli numerici per ottenere guadagni sostanziali in termini di efficienza hardware.