Algoritmi paralleli e distribuiti
A.A. 2025/2026
Learning objectives
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.
Expected learning outcomes
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 quadrimestre
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.
Course syllabus and organization
Edizione unica
Responsabile
Periodo
Primo quadrimestre
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://myariel.unimi.it/course/view.php?id=7697
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://myariel.unimi.it/course/view.php?id=7697
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 di: definizioni formali, enunciati di teoremi e costruzioni/dimostrazioni. Gli esercizi verificano l'aspetto applicativo della materia mentre le domande aperte verificano la capacità di ragionamento sugli argomenti presentati a lezione.
La prova d'esame ha durata di circa un'ora e mezza e il voto è espresso in trentesimi. Un voto compreso tra 18 e 24 indica una conoscenza sufficiente a esporre gli argomenti mediante l'uso di un appropriato formalismo, un voto compreso tra 25 e 30 evidenzia anche la capacità di dimostrare e/o applicare enunciati di teoremi. Il voto viene comunicato direttamente allo studente tramite SIFA.
La prova d'esame ha durata di circa un'ora e mezza e il voto è espresso in trentesimi. Un voto compreso tra 18 e 24 indica una conoscenza sufficiente a esporre gli argomenti mediante l'uso di un appropriato formalismo, un voto compreso tra 25 e 30 evidenzia anche la capacità di dimostrare e/o applicare enunciati di teoremi. Il voto viene comunicato direttamente allo studente tramite SIFA.
Professor(s)