Algoritmi paralleli e distribuiti

A.A. 2016/2017
Insegnamento per
6
Crediti massimi
48
Ore totali
Lingua
Italiano
Obiettivi formativi
Obiettivo del corso è la presentazione delle principali nozioni e tecniche che stanno alla base della progettazione di algoritmi paralleli e distribuiti

Struttura insegnamento e programma

Edizione attiva
Responsabile
STUDENTI FREQUENTANTI
Informazioni sul programma
Algoritmi paralleli e distribuiti, motivazioni
Architetture parallele e distribuite vs. architettura von Neumann
Risorse computazionali nei due contesti
Richiami di teoria della complessità sequenziale
Le risorse tempo e spazio sequenziali, concetto di efficienza

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
- L'architettura ipercubo, tipologie, struttura, funzionalità e parametri di rete
- Soluzione parallela del calcolo del massimo e ORDINAMENTO su ipercubo
- Cenni ad altre architetture parallele a memoria distribuita

Algoritmi e architetture distribuite
- Modellazione di un'architettura distribuita
- Entità 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
- Soluzioni distribuite su architetture particolari
Propedeuticità
Nessuna
Prerequisiti e modalità di esame
Modalità d'esame frequentanti: l'esame consiste nella presentazione di un seminario su argomenti avanzati concordati tra docente e studente.
Metodi didattici
Modalità d'erogazione: lezioni frontali, seminari avanzati.
Modalità di frequenza: frequenza fortemente consigliata.
STUDENTI NON FREQUENTANTI
Prerequisiti e modalità di esame
Modalità d'esame non frequentanti: l'esame consiste in un colloquio orale atto a verificare le conoscenze di base presentate al corso.
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
su appuntamento via mail
Sala Dottorato, V piano (edificio Lita), Dip. Fisica, via Celoria 16
Ricevimento:
Su appuntamento da concordare via email.
Via Celoria, 18 - stanza: 4011