Anno Accademico 2018/2019
- Docente: Alan Albert Bertossi
- Crediti formativi: 6
- SSD: INF/01
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea Magistrale in Informatica (cod. 8028)
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