Parallel Computing (9 CFU, primo semestre)

• Docente: dott. Giuseppe Ciaccio
• Informazioni generali:
  • Obbiettivi
  • Programma
  • Modalita' di esame
  • Testi di Riferimento
  • Prerequisiti
  • Sillabo (argomenti svolti nell'anno accademico corrente)
• Materiale didattico in linea

Obbiettivi

Il modello tradizionale di calcolatore sequenziale rimane ormai confinato ad ambiti applicativi in cui sono richieste basse capacita' di elaborazione di informazione (controllo di apparati industriali, telefoni cellulari, netbook). In tutti gli altri casi, invece, vengono utilizzati sistemi che impiegano piu' unita' di calcolo simultaneamente. Tali calcolatori paralleli richiedono specifiche tecniche di programmazione, al fine di esplicare maggiori capacita' di elaborazione attraverso il controllo (esplicito o implicito) della cooperazione tra le varie unita' di calcolo.

Per un esperto in Informatica e' dunque importante conoscere i vari tipi di architetture parallele oggi disponibili ed essere in grado di programmare calcolatori paralleli.

Obbiettivo di questo corso e' di fornire conoscenze di base sull'architettura dei sistemi di elaborazione paralleli, insieme a un minimo di capacita' di programmazione indispensabili per utilizzare sistemi di questo tipo. Per quanto riguarda la parte di programmazione, questa riguarda in special modo la programmazione parallela a scambio di messaggi utilizzando lo standard MPI su una piattaforma di tipo cluster, ma viene anche esaminato un paradigma a memoria condivisa basato sulle direttive OpenMP. Viene inoltre presentata una architettura di calcolo parallelo di tipo GPU con alcuni esempi di programmazione. Viene infine affrontato, in maniera introduttiva, il problema dell'I/O parallelo.

Programma

Alcuni degli argomenti sotto elencati potrebbero non essere stati svolti in questo anno accademico e dunque non essere richiesti per superare l'esame. Prima di sostenere l'esame, consulta il sillabo degli argomenti svolti nell'anno accademico corrente.

1. Prestazioni di un calcolatore:
   Indici di prestazione diretti e inversi, assoluti e relativi. Benchmarks.
2. Architettura dei processori pipeline:
   Prestazioni dei sistemi pipeline e loro valutazione analitica. Struttura di un processore pipeline. Conflitti (strutturali, sui dati, sul controllo) e loro impatto sulle prestazioni. Riduzione dei conflitti e/o del loro effetto sulle prestazioni: tecniche hardware. Il parallelismo a livello istruzioni nei programmi. Come sfruttare meglio il parallelismo a livello istruzioni quando si usano processori pipeline: loop unrolling, ridenominazione registri, riordino delle istruzioni.
3. Processori pipeline avanzati:
   Schedulazione dinamica delle istruzioni: architettura di Tomasulo.
   Predizione dei salti (``branch prediction''): tecniche principali.
   Esecuzione speculativa delle istruzioni.
4. Cenni sui processori superscalari:
   Processori ad avvio multiplo. Schedulazione istruzioni su processori ad avvio multiplo. Processori VLIW.
5. Memoria cache e prestazioni dei calcolatori:
   Tecniche hardware per ridurre la penalita' di cache miss. Tecniche hardware e software per ridurre la frequenza di cache miss. Tecniche hardware per nascondere l'impatto dei cache miss.
6. Calcolatori multiprocessore MIMD:
   Generalita': MIMD a memoria comune, MIMD a memoria distribuita con spazio di indirizzamento comune, MIMD a memoria distribuita e scambio di messaggi. Scopi di un calcolatore MIMD. Limiti dei calcolatori MIMD: legge di Amdahl, ritardi di comunicazione.
7. Calcolatori MIMD a memoria comune:
   Struttura a grandi linee. Riduzione dei conflitti di accesso alla memoria. Coerenza di cache: protocolli basati su ``snooping''.
8. Cooperazione tra processi su calcolatori a spazio di indirizzamento comune:
   Cooperazione e sincronizzazione. Implementazione di lock/unlock e barrier synchronization su spazio di indirizzamento comune, discussione delle loro prestazioni.
9. Modelli di consistenza della memoria principale. Modelli di consistenza debole e loro vantaggi in termini di prestazioni.
10. Programmazione parallela ad alto livello su calcolatori a spazio di indirizzamento comune: le direttive OpenMP.
11. Calcolatori MIMD a memoria distribuita e scambio di messaggi:
    Struttura a grandi linee. Cooperazione tra processi: funzioni di comunicazione basate sullo scambio di messaggi. Funzioni di comunicazione bloccanti vs. non bloccanti, punto-punto vs. collettive, cenni sulla loro implementazione. Funzioni non bloccanti e riordino di istruzioni. Programmazione parallela a scambio di messaggi: il paradigma SPMD. MPI, uno standard per la programmazione parallela a scambio di messaggi. Esercitazioni pratiche sulla programmazione parallela mediante la libreria MPI.
12. Il concetto di ``bilanciamento del carico'' e il suo impatto sulle prestazioni.
    Tecniche per il bilanciamento dinamico del carico (cenni). Sistemi paralleli di tipo ``farm'' e loro valutazione analitica.
13. Cenni sulle reti di interconnessione per calcolatori multiprocessore:
    Tassonomia. Indirizzamento, instradamento, propagazione dei messaggi (store-and-forward, virtual cut-through, ``wormhole''). Prestazioni di comunicazione. Caratteristiche delle principali reti di interconnessione (diametro, throughput di bisezione, complessita' realizzativa, espandibilita').
14. Calcolatori paralleli SIMD: processori vettoriali. I discendenti moderni dei calcolatori SIMD: le GPU. Programmazione GPU con OpenCL.
15. Cenni su I/O parallelo e MPI-I/O

Modalita' di esame

L'esame consiste di una prova orale. La valutazione terra' conto anche del lavoro svolto in occasione delle esercitazioni pratiche. Per coloro che non partecipano alle esercitazioni, e' prevista una prova pratica in laboratorio riguardante la programmazione parallela utilizzando uno dei paradigmi di programmazione esaminati durante il corso.

Testi di Riferimento

Prerequisiti

Sillabo (2011)

Ultimo Aggiornamento: Febbraio 2012