Docente
Beatrice Palano

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

Algoritmi e architetture parallele

Algoritmi e architetture distribuite




Registro del corso
(contenuti del corso lezione per lezione)

  1. Presentazione del corso. Sito del corso, materiali e risorse bibliografiche, modalità d'esame. Chiacchiere introduttive: differenze sostanziali tra algoritmi sequenziali, paralleli e distribuiti. Motivazioni allo studio degli algoritmi paralleli e distribuiti. Esempi di architetture parallele e distribuite. Problematiche che si affrontano nel caso parallelo e distribuito: progettare e valutare gli algoritmi.

  2. Programma del corso. La risorsa tempo, caso sequenziale. Notazioni asintotiche per il tasso di crescita delle funzioni. Classi di problemi risolti efficientemente in tempo sequenziale: P e FP. 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.

  3. Tipi di architetture parallele: a memoria condivisa e distribuita. Il modello PRAM (Parallel RAM), architettura e struttura dei processori. Memoria centrale come canale di comunicazione in tempo O(1). Come programmare una PRAM, PRAM come architettura SIMD contro architetture MIMD. Modelli di PRAM: EREW, CREW, CRCW. Risorse di calcolo: complessità hardware p(n), complessità in tempo T(n,p(n)), definizioni.

  4. Misure per il confronto di algoritmi paralleli con algoritmi sequenziali: speed up e efficienza. Limite inferiore e superiore all'efficienza. Trasformazione di algoritmi paralleli in sequenziali, complessità in tempo risultante, conseguenze sull'efficienza. Efficienza come indicatore della necessità di ridurre l'hardware, principio di Wyllie.

  5. Efficienza come misura monotona decrescente al crescere dei processori. 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).

  6. SOMMATORIA: Valutazione processori/tempo dell'algoritmo generale. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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, ultima posizione, prima posizione. Il problema dell'ordinamento (ranking). Algoritmi basati sui confronti, calcolo del lower bound sul tempo nel caso sequenziale. Algoritmi quadratici, un semplice algoritmo e sua traduzione parallela: counting sort. Analisi della versione parallela di counting sort: processori, tempo e efficienza.

  11. 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. 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à.

  12. La routine bitmerge di ordinamento di sequenze bitoniche. Correttezza di bitmerge per induzione. Dinamica ricorsiva di bitmerge e implementazione parallela EREW. Calcolo del tempo di bitmerge e numero di processori. Il sorting 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. Implementazione parallela EREW, valutazione del tempo, numero di processori e efficienza.

  13. Considerazioni generali sull'esportabilità di buoni algoritmi sequenziali in ambito parallelo e viceversa. Tecnica del circuito euleriano per la gestione parallela di strutture dinamiche (alberi). Nozioni di teoria dei grafi: grafi diretti, circuiti euleriani, grafi euleriani, caratterizzazione di Eulero. Differenza computazionale tra grafi euleriani e hamiltoniani. Definizione di un circuito euleriano su un albero binario, sua realizzazione efficiente come lista euleriana con algoritmi paralleli EREW.

  14. 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, 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. I problemi MAX e ORDINAMENTO su architetture a memoria distribuita. Lower bound sul loro tempo di soluzione in funzione dei parametri di rete.

  15. Ancora sulla struttura delle architetture a memoria distribuita. Algoritmi di ordinamento test and swap oblivious, loro rappresentazione mediante sorting network. Sorting network anche come dispositivo parallelo. Il principio 0-1 (Knuth) nelle sorting network. Dimostrazione e importanza nella progettazione e studio di correttezza degli algoritmi di ordinamento.

  16. 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 dello SWAP nella soluzione del problema di SHUFFLE su array lineari, tempo, processori, efficienza. La routine SEND per trasmissioni a distanza utilizzata per il problema MAX, su array lineari. Tempo, numero di processori e efficienza. Miglioramenti alla soluzione per MAX. Progetto della routine SWAP a distanza, codice e tempo.

  17. La routine MINMAX su processori contigui e a distanza, codice e tempo. Il problema ORDINAMENTO, uso della sorting network 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 a serpente, algoritmi inefficienti. Soluzione ottimale di MAX nativa, processori, tempo. Riduzione dei processori per un algoritmo di efficienza ottima.

  18. Il problema ORDINAMENTO su mesh. L'algoritmo LS3sort, struttura ricorsiva. La procedura LS3merge, specifica con primitive per array lineari e dimostrazione di correttezza grafica tramite il principio 0-1. Valutazione in tempo di LS3merge, equazione di ricorrenza per il tempo di LS3sort, ottimalità, calcolo efficienza.

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

  20. Configurazioni di un sistema distribuito, esecuzione di un protocollo. Stati iniziali e terminali. Formalizzazione della soluzione di un problema: condizione di correttezza e terminazione. Il protocollo Flooding per la soluzione del problema BROADCAST, complessità di messaggi e tempo causale. Lower bound su tempo e messaggi per la soluzione di BROADCAST. Il problema WAKE-UP. Il protocollo WFlood, sua complessità.

  21. 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 DF-Traversal, definizione di stati, messaggi e azioni. Valutazione delle prestazioni di DF-Traversal, upper e lower bound su messaggi e tempo. Possibili miglioramenti, introducendo ulteriori messaggi.

  22. 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.

  23. Il problema ELECTION, definizione e motivazioni: impossibilità di soluzione sotto restrizioni R, banale sotto restrizioni RI. Soluzione sotto restrizioni IR in una topologia ad anello. Due strategie: elezione del minimo, elezione del minimo tra le starting entità. Protocollo All the Way, terminazione e complessità per entrambe le strategie.

  24. I problemi ROUTING e SHORTEST PATH, definizioni e motivazioni. Shortest Path sotto restrizioni IR, definizione della Full Routing Table. Due protocolli diversi: Gossiping e Iterated Construction. Gossiping per la costruzione di MAP(G) per un sistema G e sua complessità di comunicazione. Iterated Construcion per la costruzione della Full Routing Table, idea di correttezza, vantaggi e sua complessità di comunicazione e tempo.




Dispense e testi consigliati

Algoritmi paralleli Algoritmi distribuiti