Parallel Computing (9 CFU, primo semestre)

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, e in generale possedere una certa conoscenza del settore del calcolo ad alte prestazioni, considerato anche l'odierna importanza dell'elaborazione di dati di grandi dimensioni ed alta dimensionalita'.

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

  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', scopi di un calcolatore parallelo. Limiti dei calcolatori paralleli: legge di Amdahl, ritardi di comunicazione. Calcolatori MIMD a memoria comune, a memoria distribuita con spazio di indirizzamento comune, a memoria distribuita e scambio di messaggi.
  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 MIMD a spazio di indirizzamento comune:
    Comunicazione e sincronizzazione. Implementazione di lock/unlock e barrier synchronization su spazio di indirizzamento comune, discussione delle loro prestazioni.
  9. Calcolatori MIMD a memoria distribuita con spazio di indirizzamento comune:
    Struttura a grandi linee. Protocolli di coerenza di cache basati su directory (cenno).
  10. Modelli di consistenza della memoria principale. Modelli di consistenza debole e loro vantaggi in termini di prestazioni.
  11. Programmazione parallela ad alto livello su calcolatori MIMD a spazio di indirizzamento comune: le direttive OpenMP. Esercitazioni pratiche con OpenMP.
  12. 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.
  13. Programmazione parallela a scambio di messaggi: il paradigma SPMD, lo standard Message Passing Interface (MPI). Esercitazioni pratiche con MPI.
  14. 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.
  15. Calcolatori paralleli SIMD: processori vettoriali. I discendenti moderni dei calcolatori SIMD: le GPU. Programmazione GPU con OpenCL. Esercitazioni pratiche con OpenCL.
  16. I/O parallelo e MPI-I/O (cenni).

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

John Hennessy, David Patterson: Computer architecture: a quantitative approach (fifth edition), Morgan Kaufmann.
Acquistabile a modico prezzo (meno di 30 euro) qui

Esiste anche la traduzione in italiano (ma dell'edizione piu' vecchia):
John Hennessy, David Patterson: Architettura degli elaboratori, Apogeo.

Qui la versione online del libro di Jan Foster: Designing and Building Parallel Programs, Addison Wesley.

Il materiale didattico presente sul modulo Aulaweb integra, ma non sostituisce, il libro di testo.

Prerequisiti

Elementi di base di Architettura dei Calcolatori e di Programmazione.
Ultimo Aggiornamento: Aprile 2017