Algoritmi paralleli e distribuiti
A.A. 2021/2022
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.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
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.
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
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.
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.
Il materiale didattico è reperibile dal sito dell'insegnamento:
https://bpalanoapd.ariel.ctu.unimi.it/v5/home/Default.aspx
Per gli Algoritmi distribuiti il libro di riferimento è: N. Santoro.
Design and Analysis of Distributed Algorithms. Wiley-Interscience, 2006.
Il materiale didattico è reperibile dal sito dell'insegnamento:
https://bpalanoapd.ariel.ctu.unimi.it/v5/home/Default.aspx
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 dell'insegnamento. L'esame non è open book. 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.
Docente/i