Esercitazioni di Calcolo Parallelo e Distribuito

Questo repository contiene le implementazioni in C per il corso di Calcolo Parallelo e Distribuito. Il progetto esplora tecniche di ottimizzazione della memoria e parallelizzazione su architetture MIMD a memoria condivisa (OpenMP) e distribuita (MPI).

📂 Descrizione delle Esercitazioni

1. Parallelismo Dati su Memoria Condivisa (OpenMP)

File: maxsum.c, mainmaxsum.c

• Obiettivo: Calcolo parallelo della formula $R = \max_{i=1..N} \sum_{j=1}^{N} \sqrt{A(i,j)}$.
• Implementazione:
  • Utilizzo di OpenMP per distribuire il carico delle righe della matrice tra i thread.
  • Gestione della race condition sulla variabile del massimo globale tramite la direttiva #pragma omp critical.
  • Analisi dello Speed-up ($S_p = T_1/T_p$) e dell'Efficienza ($E_p = S_p/p$) al variare della dimensione $N$.

2. Equazione di Laplace (MPI)

File: laplace.c, mainlaplace.c

• Obiettivo: Risoluzione iterativa di un'equazione alle derivate parziali su una griglia discretizzata.
• Algoritmo:
  • Aggiornamento basato sui 4 vicini: $B_{i,j} = 0.25 \times (A_{i-1,j} + A_{i+1,j} + A_{i,j-1} + A_{i,j+1})$.
  • Decomposizione del dominio per righe tra i processi MPI (Halo Exchange con prev e next).
• Varianti:
  • Bloccante: Uso di MPI_Send e MPI_Recv.
  • Non Bloccante: Uso di MPI_Isend, MPI_Irecv e MPI_Wait per sovrapporre comunicazione e calcolo.

3. Ottimizzazione Matrice-Matrice (Single Core & OpenMP)

File: matmatthread.c, main.c

• Obiettivo: Ottimizzazione del prodotto $C = A \times B$ riducendo il rapporto $q = N_{mem} / N_{flop}$ per sfruttare la gerarchia di memoria.
• Tecniche:
  • Loop Reordering: Analisi delle permutazioni dei cicli (ijk, ikj, kij, ecc.) per massimizzare la località spaziale.
  • Cache Blocking: Implementazione a blocchi (matmatblock) per mantenere i dati nelle cache L1/L2.
  • Multithreading: Parallelizzazione tramite OpenMP (matmatthread), assegnando blocchi di calcolo distinti ai thread.

4. Moltiplicazione Distribuita Ibrida (MPI + OpenMP)

File: matmatdist.c, mainmatmatdist.c

• Obiettivo: Moltiplicazione di matrici su cluster distribuito.
• Architettura:
  • Livello MPI: Organizzazione dei processi in una griglia cartesiana 2D (MPI_Cart_create). Distribuzione dei blocchi di matrice $A, B, C$.
  • Livello OpenMP: Ogni nodo calcola il prodotto del proprio blocco locale utilizzando la funzione matmatthread (approccio ibrido).
  • Algoritmo: Implementazione ispirata agli algoritmi Cannon e SUMMA per la comunicazione efficiente dei blocchi.

---