Algoritmi paralleli e distribuiti

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Obiettivo dell'insegnamento è la presentazione delle principali nozioni e tecniche che stanno alla base della progettazione di algoritmi paralleli e distribuiti compresa la valutazione delle prestazioni e il confronto con gli algoritmi sequenziali.
Risultati apprendimento attesi
Lo studente dovrà essere in grado di distinguere il mondo parallelo da quello distribuito, applicare tecniche e metodi presentati nell'insegnamento per la progettazione di algoritmi efficienti paralleli e distribuiti. Dovrà inoltre essere in grado di analizzare le risorse di calcolo utilizzate per la valutazione delle prestazioni degli algoritmi e analizzare la correttezza degli stessi.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
Metodi didattici:
Verranno svolte lezioni sincrone (videolezioni) utilizzando la piattaforma Zoom con registrazione completa. Verranno poi rese disponibili le lezioni per consentirne la fruizione in modalità asincrona per gli studenti non presenti in aula.

Il programma e il materiale di riferimento compresa la modalità di verifica dell'apprendimento non subiranno variazioni.
Programma
Algoritmi paralleli e distribuiti, motivazioni. Architetture parallele e distribuite vs. architettura von Neumann. Risorse computazionali nei due contesti.
Algoritmi e architetture parallele:
- Problematiche nel disegno di algoritmi paralleli: sintesi, universalità, valutazione
- Architetture parallele a memoria condivisa e distribuita; la comunicazione nei due contesti
- Architetture a memoria condivisa, Il modello PRAM (Parallel RAM), struttura
- PRAM come architettura SIMD vs. architetture MIMD
- Modelli di PRAM: EREW, CREW, CRCW (common, priority, ... )
- Risorse di calcolo: complessità in numero di processori e tempo
- Confronto con algoritmi sequenziali: speed-up ed efficienza
- Soluzione parallela efficiente su PRAM di alcuni problemi fondamentali
- Calcolo di operazioni binarie associative, il problema SOMMATORIA, struttura ed analisi di un algoritmo parallelo
- Algoritmi paralleli efficienti per: algebra lineare, teoria dei grafi, ottimizzazione,...
- Calcolo di operazioni binarie associative prefisse, il problema SOMME PREFISSE
- Struttura ed analisi dell'algoritmo di Kogge-Stone (pointer doubling)
- Valutazione parallela efficiente di polinomi. Algoritmi di ricerca paralleli
- Il problema dell'ORDINAMENTO (ranking), soluzioni sequenziali efficienti
- Algoritmi di ordinamento paralleli efficienti. L'ordinamento bitonico di Batcher, struttura e analisi dell'algoritmo
- Tecnica del circuito euleriano nel progetto di algoritmi paralleli
- Architetture parallele a memoria distribuita, rete di interconnessione e parametri di valutazione: grado, diametro
e ampiezza di bisezione
- Reti di ordinamento e il principio 0-1 (Knuth)
- Array lineari di processori, struttura, funzionalità e parametri di rete
- Soluzione parallela dei problemi di ORDINAMENTO, calcolo del massimo e SHUFFLE
- Gli algoritmi di ordinamento ODD-EVEN e MERGE-SPLIT, struttura ed analisi
- Mesh di processori, tipologie, struttura, funzionalità e parametri di rete
- Calcolo del massimo su mesh
- L'algoritmo di ordinamento LS3, sruttura ed analisi
Algoritmi e architetture distribuite:
- Modellazione di un'architettura distribuita
- Entita' e canali di comunicazione
- Risorse computazionali, tempo e complessità di messaggi
- Struttura ed analisi di soluzioni distribuite per i problemi fondamentali
- BROADCASTING, lower bound per soluzioni distribuite
- L'algoritmo di flooding
- WAKE-UP, l'algoritmo di wflooding
- ATTRAVERSAMENTO, l'algoritmo depth-first
- SPANNING TREE, l'algoritmo shout e depth-first
- ELECTION, risultati di impossibilità, elezione per minimo
- ROUTING, algoritmi di gossiping
Prerequisiti
Nessuno.
Metodi didattici
Modalità d'erogazione: lezioni frontali, seminari avanzati.
La frequenza alle lezioni è fortemente consigliata.
Materiale di riferimento
Per gli Algoritmi paralleli sono disponibile delle dispense reperibili dal sito dell'insegnamento di Algoritmi Paralleli e Distribuiti.
Per gli Algoritmi distribuiti il libro di riferimento è: N. Santoro.
Design and Analysis of Distributed Algorithms. Wiley-Interscience, 2006.
Modalità di verifica dell’apprendimento e criteri di valutazione
La prova d'esame consiste di uno scritto di circa tre domande/esercizi che coprono gli argomenti del corso. Le domande consistono in: definizioni formali, enunciati di teoremi e costruzioni/dimostrazioni. Gli esercizi verificano la comprensione della materia. La prova d'esame ha durata di circa un'ora e il voto, espresso in trentesimi, viene comunicato direttamente allo studente tramite SIFA.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento
Via Celoria, 18 - stanza: 4011