Algoritmi Paralleli e Distribuiti (a.a. 2008/09)

Sistemi concorrenti: Computazione parallela, computazione distribuita. Differenza fra sistema concorrente e sistema sequenziale. Differenze fra Sistema Distribuito e Sistema Parallelo. Classificazione di Flynn delle macchine parallele. Macchine SIMD a reti di interconnessione: vettore, matrice, albero, cubo. Definizione di Sistema Distribuito. Sistemi sincroni e asincroni.

Algoritmi concorrenti: Definizione di Algoritmo Parallelo. Definizione di Algoritmo distribuito. Complessità parallela: tempo, costo, speed-up ed efficienza. Misure di complessità legate alla tecnologia*. Complessità distribuita: tempo e messaggi. La tesi della computazione parallela*. La classe NC*.

Il modello PRAM: Modelli a lettura e scrittura esclusiva e/o concorrente. Simulazione della lettura e della scrittura concorrente. Ricerca di un elemento in un vettore su PRAM CREW/EREW e delle radici in una foresta su PRAM CREW. Calcolo del massimo in un vettore su PRAM CRCW. Calcolo della somma di n elementi su PRAM EREW, mesh, albero binario e ipercubo.

La trasmissione dell'informazione: Broadcast su PRAM EREW. Broadcast su rete a vettore, su albero binario, mesh e ipercubo. Broadcast in un sistema distribuito ad anello. Broadcast con eco su rete qualsiasi. Il problema del caricamento dei dati su rete a vettore, su albero binario e su mesh. Caricamento di valori distinti su un ipercubo: distanza di Hamming, codice di Gray, codifica e decodifica per numeri di d bits, verifica della correttezza della codifica.

La trasportabilità degli algoritmi: Trasportabilità fra PRAM con diverso numero di processori. Reti combinatorie: fan in e fan out. Teorema di Brent. Somme Prefisse su PRAM, su albero binario e su mesh. Simulazione di sistemi asincroni su sistemi sincroni: il sincronizzatore.

Tecniche parallele di base: Iterazione della prima metà; ricerca del minimo su PRAM-EREW. Tecnica del salto del puntatore: calcolo del rango in una lista. La tecnica del Tour di Eulero (TDE). Come costruire il TDE. Ordinamento dei vertici di un albero rispetto alla radice. Numerazione in preordine e postordine. Calcolo in un albero dei livelli e dei discendenti di ogni nodo. Introduzione degli operatori left e right per calcolare la numerazione in modo simmetrico e il minimo antecedente comune. Accelerated Cascading: somme, somme prefisse e somme con numero di processori p < n.

Il problema dell'elezione del leader: Elezione del leader in reti ad anello sincrone e asincrone. Impossibilità di eleggere un leader in processi anonimi. Elezione del leader in reti qualunque*.

Algoritmi paralleli su grafi: Partizione degli spigoli di un grafo in cammini semplici. Contrazione e decontrazione di alberi binari tramite l'operazione di Rake. Trasformazione di alberi qualsiasi in alberi binari 0/2. Valutazione di espressioni tramite contrazione di alberi. Calcolo del minimo, sia parziale che globale, in un albero binario 0/2*.

Minimo albero ricoprente: Unicità del minimo albero ricoprente. Proprietà del minimo albero ricoprente. Algoritmo di Sollin per il calcolo del minimo albero ricoprente in sistemi concorrenti. Differenza fra meganodi e frammenti. Algoritmo parallelo per il calcolo dell'albero ricoprente di costo minimo. Calcolo del minimo albero ricoprente in un sistema distribuito: come limitare il tempo e il numero di messaggi trasferiti.

Ordinamento nel Parallelo: Ordinamento per inserzione tramite circuiti di comparatori. Monotonicità e principio 0/1. Sequenze bitoniche e pulite. Circuiti di fusione e di ordinamento. Algoritmo di ordinamento pari/dispari su PRAM EREW e ordinamento in tempo parallelo costante su PRAM CRCW. Ricerca di un elemento su un vettore ordinato. Calcolo del rango fra due vettori. Algoritmo parallelo di ordinamento per fusione tramite rango. Cenni sull'algoritmo di Cole per l'ordinamento in tempo O(log n) su PRAM-CREW.

Gli argomenti contrassegnati con * sono facoltativi.

Riferimenti bibliografici

• [A89] Akl S.G., The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989.
• [AW00] Attiya H.,Welch J., Distributed Computing: Fundamentals, Simulations and Advanced Topics, McGraw-Hill, 2000.
• [CLR90] Cormen T.H., Leiserson C.E., Rivest R.L.: Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.
• [B96] Barbosa V.C., An Introduction to Distributed Algorithms, MIT Press, 1996.
• [J92] Jaja J., An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• [JS04] Johnsonbaugh R. e Schaefer M., Algorithms, Pearson Education International, 2004.
• [L96] Lynch N.A., Distributed Algorithms, Morgan Kaufmann, 1996.
• [T00] Tel G., Introduction to Distributed Algorithms, Cambridge University Press, 2000.