ALGORITMI PER IL CALCOLO PARALLELO
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2017/2018
- Docente
- ENRICO CALORE
- Crediti formativi
- 6
- Periodo didattico
- Primo Semestre
- SSD
- MAT/08
Obiettivi formativi
- L'obbiettivo principale del corso consiste nel fornire allo studente le basi della programmazione in ambito parallelo, sia per architetture a memoria distribuita che condivisa.
Le principali conoscenze acquisite saranno:
- caratteristiche delle moderne architetture per il calcolo parallelo;
- metriche per la valutazione delle prestazioni di codici paralleli, sia meediante analisi del sorgente (es. calcolo della metrica CGMA per codici su GPU), che attraverso misure del tempo di calcolo (speedup, efficienza e funzione di Kuck per implementazioni MPI);
- introduzione al paradigma MPI per architetture a memoria distribuita: comunicazioni punto-punto e collettive, direttive di riduzione e sincronizzazione;
- introduzione ad OpenMP ed OpenACC per architetture a memoria condivisa;
- elementi di architettura hardware di una GPU e loro impatto sulle metodologie di programmazione;
- caratteristiche del framework CUDA: tipi di memorie, trasferimento dati tra host e device, gestione dei blocchi di thread e della memoria condivisa;
- utilizzo degli eventi CUDA per la misura del tempo di calcolo e trasfermento dati;
- esempi di implementazione dell'opreazione di riduzione e del prodotto matrice-matrice;
- esempi di utilizzo delle principali librerie di calcolo per l'algebra lineare, fattorizzazioni e problemi agli autovalori: BLAS, ATLAS, LAPACK, MKL e loro implementazioni parallele;
- esempi d'uso di diversi profiler per l'analisi delle performance sia su CPU che GPU;
Le principali abilità saranno:
- Analizzare un algoritmo seriale e individuare una corretta metodologia di suddivisione del carico di lavoro per ottenere un buono speedup;
- Analizzare un algoritmo seriale e individuare una metodologia di accesso ai dati che massimizzi gli accessi a memoria contigui ed allineati.
- Analizzare le performance di un codice quando eseguito su una architettura reale. Prerequisiti
- E’ necessario padroneggiare le seguenti conoscenze fornite dal corso di "Calcolo numerico":
- fattorizzazione QR, fattorizzazione LU e suo utilizzo per la risoluzione di sistemi lineari;
- rappresentazione in virgola mobile, precisione di macchina, aritmetica finita;
Prerequisito consigliato è la familiarità con il linguaggio di programmazione C (definizione di variabili e funzioni, strutture di controllo di flusso, allocazione dinamica della memoria, aritmetica dei puntatori) acquisita con uno dei corsi base di programmazione, per esempio "Programmazione e laboratorio". Contenuti del corso
Introduzione
- Introduzione al calcolo parallelo, architettura di una CPU, costo computazionale, memorizzazione di matrici in C;
- Classificazione di Flynn, misura di prestazioni (speedup, efficienza, funzione di Kuck), codice C per misurare il tempo di calcolo in seriale;
- Esempio: implementazione a blocchi del prodotto matrice matrice;
Utilizzo di MPI
- Introduzione a MPI, script per la compilazione e il lancio di codici paralleli,
comunicazioni punto-punto bloccanti e non bloccanti, definizione di deadlock ed esempio mediante send/receive,
soluzione del deadlock mediante sendreceive, comunicazioni collettive, riduzioni, direttive di sincronizzazione;
- Esempio: implementazione dell'algoritmo mergesort mediante MPI;
- Esempio: implementazione del prodotto matrice-matrice mediante MPI;
Utilizzo di CUDA
- Introduzione a CUDA, descrizione della architettura hardware, librerie di calcolo fornite da NVIDIA:
tipi di memorie sulla scheda e on-chip, gestione dei threads mediante blocchi e griglie, definizione e lancio dei kernel,
thread Warp e divergenza nel flusso di esecuzione, utilizzo degli eventi CUDA;
- Esempio: esecuzione del prodotto matrice-matrice sfruttando la memoria condivisa per blocco;
- Esempio: risolvere i problemi di coalescenza di dati e divergenza dei threads nel caso della operazione di riduzione;
- Esempio: saper individuare pattern di riutilizzo dei dati nel caso del prodotto matrice-vettore;
Approfondimenti:
- cenni ai threads posix, OpenMP, OpenACC; esempi d'uso dei tool gdb, gprof, valgrind;
Esempi di parallelizzazione di comuni algoritmi
- Parallelizzazione della fattorizzazione LU per architetture a memoria distribuita;
- Algoritmo di Cuppen per il calcolo degli autovalori di matrice tridiagonale e sua implementazione (in forma semplficata) in MPI;
- Parallelizzazione del metodo di Neville per la valutazione del polinomio interpolante in CUDA;
- Parallelizzazione del metodo di Gram-Schmidt modificato in CUDA;
- Soluzione di un sistema bordato a blocchi in ambiente MPI;Metodi didattici
- I temi del corso verranno introdotti in aula mediante l'uso di presentazioni, ed esempi pratici condotti sul cluster di Ateneo coka.unife.it.
Gli studenti potranno usufruire del cluster sia durante le lezioni che durante l'anno accademico in corso. Modalità di verifica dell'apprendimento
- Il livello di raggiungimento degli obiettivi formativi indicati in precedenza verrà verificato attraverso una prova d'esame.
Lo studente, all'atto dell'iscrizione all'appello, dovrà inviare via mail sia il codice sorgente riguardante la parallelizzazione di uno degli algoritmi affrontati a lezione, che una breve relazione dove riassume le prestazioni del proprio codice in relazione al numero di processori utilizzati, al variare della dimensione dei dati in input.
Durante l'appello, lo studente dovrà saper ripercorrere le fasi salienti del processo di parallelizzazione che ha affrontato, sottolineando i particolari elementi dell'approccio che ha deciso di sfruttare.
Verranno successivamente sottoposte alcune domante riguardo gli argomenti non trattati direttamente nel progetto.
Il voto finale terrà conto sia delle capacità dimostrate nella fase implementativa del progetto che nella fase di esposizione degli argomenti oggetto delle successive domande. Testi di riferimento
- - Dispense del docente.
- Libro di Testo: V. Kumar, A. Grama, A. Gupta, G. Karypis, Introduction to Parallel Computing: design and analysis of Algorithms, Addison-Wesley, 2003
- Testo per approfondimento: D.P. Bertsekas, J. Tsisiklis, Parallel and Distributed Computation: Numerical Methods, Trentine-Hall, 1989
