81668 - ALGORITMI PARALLELI

Conoscenze e abilità da conseguire

Al termine del corso lo studente: - conosce i principali modelli di calcolo parallelo, le tecniche di base per progettare algoritmi paralleli e per calcolarne il costo computazionale; - è in grado di progettare e analizzare algoritmi paralleli per risolvere semplici problemi computazionali; - è in grado di programmare algoritmi paralleli con MPI e OpenMP.

Contenuti

Modelli paralleli sincroni/asincroni, con memoria condivisa/riservata. Algoritmi paralleli per reti a grado limitato. Sistemi sincroni. Tesi della computazione parallela. Reti di interconnessione: mesh, ipercubo, shuffle, butterfly, CCC. Somme prefisse. Mergesort bitonico. Moltiplicazione di matrici. Trasformata di Fourier. Modello VLSI e mesh riconfigurabili. Algoritmi concorrenti. Concorrenza, sezioni critiche, mutua esclusione, primitive di sincronizzazione, stallo. Algoritmi distribuiti. Reti di calcolatori. Messaggi. Topologie di reti: anello, stella, albero, grafo, grafo completo. Mutua esclusione in grafo completo. Elezione del leader in anello. Algoritmo di Gallager-Humblet-Spira per minimo albero di copertura. Algoritmi distribuiti per reti non cablate di calcolatori.

Testi/Bibliografia

A.A. Bertossi, Algoritmi Paralleli: Sincroni, Concorrenti, Distribuiti. Pitagora Editrice, Bologna, 2009.

Metodi didattici

Il corso si svolge nel primo semestre ed è strutturato in lezioni frontali in aula, comprendenti lezioni ed esercitazioni. Vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, vengono presentati i piu' comuni modelli di calcolo parallelo e alcuni problemi computazionali di base. Per tali problemi, sono progettati algoritmi paralleli, evidenziando le tecniche di progettazione e le prestazioni al variare del modello di calcolo parallelo usato.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta finale di 3 ore, durante la quale non è ammesso l'uso di libri, appunti, calcolatrici, supporti elettronici. La prova scritta consiste di 4 quesiti, alcuni dei quali sono esercizi che mirano ad accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi paralleli, mentre altri sono domande aperte che mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso.

Strumenti a supporto della didattica

Videoproiettore.

Orario di ricevimento

Consulta il sito web di Alan Albert Bertossi