Algoritmo di Strassen in ambiente GPU-CUDA

Il progetto sviluppato propone una strategia per l'accelerazione del prodotto tra due matrici in ambiente GPGPU. L'algoritmo presente ricorre all'algoritmo di Strassen per ridurre il tempo computazionale dell'algoritmo, studiandone anche le peculiarità. La strategia di parallelizzazione è delegata alla libreria cuBLAS, che svolge le operazioni di addizione e sottrazione matriciale.

Durante la progettazione, è stata ideata in un primo momento un'implementazione in ambiente CPU, per poi "trasporre" la logica in ambiente GPGPU, cercando di mantenere quanto più uniforme possibile i due codici.

Definizione algoritmo di Strassen

Siano date due matrici quadrate

e di dimensioni . Si vuole calcolare la matrice con l'algoritmo di Strassen. L’algoritmo ricava la matrice risultato definendo sette nuove matrici






che riduce, di fatto, la complessità computazionale dell'algoritmo a in quanto da 8 prodotti ne vengono computati "solo" 7. Successivamente si ricombina nella matrice risultato

Il "trucco" dell'algoritmo consiste nell'evitare il prodotto riga per colonna (algoritmo standard del prodotto matriciale) matrici, andando a ridurre il problema fintantoché le sette matrici non siano ricavabili mediante i prodotti numerici

dove in questo caso banale le due matrici di input sono

Siccome l'algoritmo è del tipo divide et impera, si ha un caso banale dove le due matrici e hanno dimensione , mentre il caso ricorsivo è dato da , per cui avviene la decomposizione.

Differenze tra l'algoritmo di Strassen e l'algoritmo standard

Caratteristiche	Naive	Strassen
Complessità di tempo
Approccio algoritmico	Iterativo (o divide et impera)	Divide et impera
Applicazione	Qualsiasi matrice	Matrici quadrate

Sebbene in linea teorica l'algoritmo di Strassen dimostri la non ottimalità dell'algoritmo standard per il prodotto tra due matrici, questo non trova pienamente riscontro in un ambiente computazionale. La creazione delle matrici temporanee

richiede maggiore memoria, oltre al generare maggiore overhead per via dell'allocazione (e deallocazione) di tali matrici.

Nella relazione viene approfondito lo sviluppo di un algoritmo capace di mitigare le problematiche intrinseche dell'algoritmo di Strassen.