Docenti

Beatrice Palano       Carlo Mereghetti


UNA VELOCISSIMA PRESENTAZIONE
DEL CORSO DI ALGORITMI PARALLELI E DISTRIBUITI




Programma del corso


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

Algoritmi e architetture distribuite





Registro del corso
(contenuti del corso lezione per lezione)

  1. Presentazione del corso, scopi, contenuti. Architetture parallele e distribuite e relativi algoritmi: caratteristiche salienti, storia, motivazioni, risorse computazionali, problemi paradigmatici. Sito del corso, materiali e risorse bibliografiche, modalità d'esame.

  2. Richiami di teoria della complessità sequenziale. Modello di calcolo, risorse di calcolo, loro valutazione. La macchina di Turing deterministica (DTM). Definizione formale, mossa, definizione di computazione, linguaggio accettato. Esempi: il linguaggio dei numeri pari, progettazione di una DTM accettante.

  3. Programmazione di una DTM, utilizzo di pseudo-codice, risultati di conversione. Problemi di decisione e loro soluzione mediante DTM, esempi: test di parità. Funzione calcolata da una DTM e soluzione di problemi generici, esempi. DTM come computer general purpose. Risorse computazionali. Tempo di calcolo su istanza e complessità in tempo (worst case). Esempi di problemi e valutazione della complessità in tempo di algoritmi risolutivi. Importanza teorica e pratica della complessità in tempo worst case. Notazioni asintotiche per il tasso di crescita delle funzioni.

  4. Accuratezza della misurazione della complessità in tempo: il caso delle palindrome e del fattoriale. Complessità asintotiche notevoli. Il concetto di efficienza sequenziale in tempo come polinomiale. Classi di problemi risolti efficientemente in tempo: P e FP. Importanza teorica e pratica del concetto di efficienza come tempo polinomiale, esempi: il test di primalità, confronto algoritmo deterministico e randomizzato. Spazio, spazio di calcolo su istanza e complessità in spazio (worst case). Aggiunta di nastri in sola lettura e scrittura al modello delle DTM per una valutazione più fedele dello spazio di lavoro. Trade-off spazio/tempo nella soluzione di problemi, il caso delle palindrome. Classi di problemi risolti efficientemente in spazio: L e FL.

  5. Algoritmi Paralleli, motivazioni per il calcolo parallelo. Architettura parallela. Problemi nel disegno di algoritmi paralleli: 1) Sintesi: servono nuovi strumenti rispetto al caso sequenziale 2) Valutazione: risorse tempo, numero di processori e efficienza per un confronto col sequenziale 3) Universalità: la questione NC = P. Architetture parallele a memoria condivisa e distribuita, pregi e difetti. Problema della comunicazione nei due tipi di architetture parallele.

  6. Il modello PRAM (Parallel RAM), architettura e struttura dei processori. Memoria centrale come canale di comunicazione in tempo O(1). Funzionamento di un programma per PRAM, PRAM come architettura SIMD contro architetture MIMD, definizioni. Modelli di PRAM: EREW, CREW, CRCW. Risorse di calcolo: complessità hardware p(n), complessità in tempo T(n,p(n)), definizioni. Misure per il confronto con algoritmi sequenziali: speed up e efficienza. Significato delle due misure e obbiettivi degli algoritmi paralleli (minimizzazione di tempo e processori, esempi). Limite inferiore e superiore all'efficienza. Trasformazione di algoritmi paralleli in sequenziali, complessità in tempo risultante, conseguenze sull'efficienza.

  7. Efficienza come indicatore della riduzione di hardware, principio di Wyllie. Efficienza come misura monotona decrescente. Il problema della SOMMATORIA, complessità sequenziale. Progetto e valutazione di un primo algoritmo parallelo di scarsa efficienza. Realizzazione dell'algoritmo per SOMMATORIA su PRAM. Verifica di fattibilità (algoritmo EREW) e correttezza (per induzione). Estensione dell'algoritmo per SOMMATORIA ad un numero generico di input e valutazione processori/tempo dell'algoritmo generale.

  8. SOMMATORIA: Efficienza tendente a zero, esigenza di ridurre il numero di processori (applicazione del principio di Wyllie). Algoritmo finale efficiente. Algoritmi paralleli efficienti per l'iterazione di operazioni associative: prodotto, and, or, xor, concatenazione, max, min. And/Or/Max/Min in tempo costante su CRCW. Algoritmi paralleli EREW e CREW per operazioni in algebra lineare, loro costruzione modulare a partire da SOMMATORIA: prodotto interno, matrice vettore, matrice matrice. Il problema delle SOMME PREFISSE, importanza, generalizzazioni, applicazioni. Algoritmo sequenziale, un primo algoritmo parallelo CREW col modulo SOMMATORIA. Valutazione tempo e processori, necessità di miglioramento.

  9. Algoritmo parallelo di Kogge-Stone per SOMME PREFISSE, pointer doubling, idea ed esempi. Dettagli dell'algoritmo di Kogge-Stone e stesura del codice. Dimostrazione di consistenza (funziona su EREW PRAM) e correttezza per induzione. Valutazione processori/tempo/efficienza dell'algoritmo di Kogge-Stone, possibile miglioramento ottimale.

  10. Il problema della valutazione parallela di polinomi, schema modulare di un possibile algoritmo. Routine parallela di replica di informazione su CREW e EREW, valutazione delle prestazioni. Algoritmo parallelo EREW ottimo per la valutazione di polinomi. Query parallele, il problema della ricerca di un elemento. Soluzioni modulari efficienti per architetture CRCW, CREW, EREW. Problemi connessi al problema di ricerca: conteggio occorrenze, prima posizione, ultima posizione.

  11. Il problema dell'ordinamento (ranking). Categorie di algoritmi, ordinamento per confronti nel caso sequenziale. Calcolo del lower bound sul tempo e algoritmi ottimi. Cenno alla complessità di ordinamenti non basati sui confronti. Algoritmi quadratici, un semplice algoritmo e sua traduzione parallela: counting sort. Analisi della versione parallela di counting sort. Dalla versione CREW alla versione EREW, processori, tempo e efficienza.

  12. Ricerca di un miglioramento delle prestazioni traendo ispirazione dall'algoritmo ottimale mergesort. Richiamo della tecnica "Divide et impera" in mergesort e analisi della complessità in tempo con equazione di ricorrenza. Versione parallela di mergesort bottom-up, valutazione di efficienza. Il problema dell'inerente sequenzialità della routine merge. Merge come semplice concatenazione. Definizione delle operazioni REV e MINMAX su sequenze e relative implementazioni parallele. Definizione di sequenza unimodale e bitonica, esempi. Forme grafiche delle sequenze, loro proprietà.

  13. Discesa ricorsiva su sequenze bitoniche e fusione come semplice concatenazione. La routine bitmerge di ordinamento di sequenze bitoniche. Correttezza di bitmerge per induzione. Dinamica ricorsiva di bitmerge e implementazione parallela. Valutazione EREW e numero processori. Calcolo del tempo di bitmerge parallela dalla dinamica ricorsiva e mediante equazione di ricorrenza. Il sorting Bitonico di Batcher: bitsort come mergesort con bitmerge invece di merge e uso di REV per mantenere la bitonicità. Correttezza di bitsort per induzione. Dinamica ricorsiva di bitsort (fase di suddivisione e fase di ricomposizione). Implementazione parallela EREW e numero di processori. Valutazione del tempo direttamente e da equazione di ricorrenza. Considerazioni generali sull'esportabilità di buoni algoritmi sequenziali in ambito parallelo e viceversa.

  14. Tecnica del circuito euleriano per la gestione parallela di strutture dinamiche (alberi). Nozioni di teoria dei grafi: circuiti euleriani, grafi euleriani (diretti e non diretti), caratterizzazione di Eulero. Differenza computazionale tra grafi euleriani e hamiltoniani. Definizione di un circuito euleriano su un albero binario, sua realizzazione EREW efficiente come lista euleriana con algoritmi paralleli.

  15. Utilizzo della rappresentazione a lista di alberi con la routine di Kogge-Stone nella soluzione parallela efficiente di alcuni problemi su alberi: visita in preordine, calcolo della profondità dei nodi. Riassunto sull'importanza del modello PRAM. Interesse non solo teorico del modello PRAM: i processori multicore, motivazioni per la loro introduzione. Introduzione alle architetture parallele a memoria distribuita, caratteristiche principali, funzionalità dei processori e rete di interconnessione. Parametri di una rete di interconnessione: grado, diametro, ampiezza di bisezione, loro significato. I problemi MAX e ORDINAMENTO su architetture a memoria distribuita. Lower bound sul loro tempo di soluzione in funzione, rispettivamente, del diametro e dell'ampiezza di bisezione.

  16. Ancora sulla struttura delle architetture a memoria distribuita. Algoritmi di ordinamento test and swap, loro rappresentazione mediante sorting network. Sorting network anche come dispositivo parallelo. Il principio 0-1 (Knuth) negli algoritmi di ordinamento test and swap e nelle sorting network. Dimostrazione e importanza nella progettazione e studio di correttezza degli algoritmi di ordinamento. Array lineari di processori: struttura, funzionalità e parametri di rete. Lower bound sui tempi di soluzione di MAX e ORDINAMENTO. La primitiva SWAP, codice e tempo. Utilizzo della routine SWAP nella soluzione del problema di SHUFFLE su array lineari, tempo, numero di processori e confronti con gli algoritmi sequenziali.

  17. La routine SEND per trasmissioni a distanza. Il problema MAX, mapping della soluzione PRAM su array lineari. Tempo, numero di processori e confronti col caso sequenziale. Miglioramenti alla soluzione per MAX. Progetto della routinne SWAP a distanza, codice e tempo. La routine MINMAX su processori contigui e a distanza, codice e tempo.

  18. Il problma ORDINAMENTO, uso delle sorting network per la progettazione ed analisi di ODD-EVEN. Dimostrazione di correttezza col principio 0-1. Implementazione di ODD_EVEN su array lineari, codice, tempo e processori. Tentativo di miglioramento con riduzione dei processori, l'algoritmo MERGE-SPLIT su array lineari. Considerazioni sui limiti della geometria di rete. L'architettura mesh, struttura e funzionalità della mesh quadrata. Parametri di rete e lower bound in tempo per la soluzione di MAX e ORDINAMENTO su mesh. Uso banale di una mesh come array lineare, algoritmi inefficienti per i due problemi. Soluzione ottimale di MAX nativa, processori, tempo. Riduzione dei processori per un algoritmo di efficienza ottima.

  19. Il problema ORDINAMENTO su mesh. L'algoritmo LS3sort, struttura ricorsiva. La procedura LS3merge, specifica con primitive per array lineari e dimostrazione di correttezza tramite il principio 0-1. Valutazione in tempo di LS3merge, equazione di ricorrenza per il tempo di LS3sort, ottimalità. Cenni ad algoritmi di efficienza ottima su mesh (bitonic sort).

  20. Algoritmi distribuiti. Ambiente di calcolo distribuito: entità e link. Funzionalità delle entità. Eventi, azioni e regole. Comportamento del sistema, comportamento omogeneo. Comunicazione e parametri di rete. Assiomi e restrizioni. Misure di complessità. Concetto di configurazione. Definizione di problema. Il primo problema: BROADCAST.

  21. Ancora su configurazioni di un sistema distribuito, esecuzione di un protocollo. Stati iniziali e terminali. Formalizzazione della soluzione ad un problema: condizione di correttezza e terminazione. Il protocollo Flooding per la soluzione del problema BROADCAST, complessità di messaggi e tempo ideale. Lower bound su tempo e messaggi per la soluzione di BROADCAST. Il problema WAKE-UP e il protocollo WFlood, sua complessità e lower bound per il problema.

  22. Il problema TRAVERSAL, applicazioni nella gestione di risorse condivise. L'approccio Depth-First, richiami. L'implementazione della strategia Depth-First in ambiente distribuito, il protocollo DFT, definizione di stati, messaggi e azioni. Valutazione delle prestazioni di DFT, upper e lower bound su messaggi e tempo. Cenno a possibili miglioramenti.

  23. Il problema SPANNING TREE, definizione e motivazioni: ottimizzazione dei messaggi per la soluzione di diversi problemi. Soluzione distribuita a SPANNING TREE con un unico iniziatore. Il protocollo Shout, schema Flooding+Reply, esempio di esecuzione. Codice di Shout. Correttezza del protocollo, misure di complessità: messaggi e tempo. Miglioramento di Shout: Shout+, complessità di messaggi. Cenni ad altri protocolli di soluzione per SPANNING TREE.

  24. Presentazione e discussione di varie tematiche avanzate su algoritmi paralleli e distribuiti. Pianificazione degli approfondamenti e seminari finali.





Dispense e testi consigliati

Algoritmi paralleli Algoritmi distribuiti




Ricevimento studenti

Su appuntamento (preavvisare via mail)
Uffici S203, S241

Via Comelico 39, MI






 
Avvisi per gli studenti  

Per poter sostenere l'esame di Algoritmi Paralleli e Distribuiti è necessario iscriversi tramite Sifa.


Gli studenti che NON hanno seguito il corso devono contattare i docenti per concordare le modalità d'esame.

I CORSI DI
ALGORITMI PARALLELI E DISTRIBUITI e INFORMATICA TEORICA
SONO FRUIBILI ANCHE DAGLI STUDENTI DELLA TRIENNALE
A PATTO CHE VENGANO INSERITI NEL PIANO DI STUDI
TRA I CREDITI LIBERI






Orario delle lezioni 2017
Giorno
Ore
Aula
mercoledì
11:30 - 13:30
Aula Alfa (via Comelico 39)
venerdì
11:30 - 13:30
Aula Sigma (via Comelico 39)








Appelli esame 2017/18
Mese
Giorno
Gennaio
24
Febbraio
14
Giugno
19
Luglio
4
Luglio
18
Settembre
18
Gennaio 2018
23