Architetture distribuite per il Cloud (Sistemi P2P)

Parametri dell'algoritmo parallelo

Esistono diversi parametri:

• Lo speedup ci dice quanto è migliorato il nostro algoritmo rispetto al sequenziale. Lo speedup minore è pari a 1, (posso spegnere i P -1 processori eseguendo tutto con 1 processore) per potere eseguire l'algoritmo in sequenziale. Non posso migliorare più di P altrimenti è possibile migliorare l'algoritmo sequenziale simulando l'algoritmo parallelo con 1 solo processore, se per ipotesi avessi questo algoritmo sequenziale che esegue l'algoritmo parallelo con 1 solo processore, ogni step dell'algoritmo parallelo paga N step sequenziali, quindi il nuovo algoritmo parallelo impiegherà N*P, allora succede che questo nuovo algoritmo parallelo è più veloce di quello che è considerato il miglior algoritmo sequenziale, assurdo.
• Per work possiamo intenderlo come il tempo impiegato dal numero di processori, se voglio misurarlo in maniera effettiva devo misurare i lavori dei singoli processori.

E sommarli. Se non posso sfruttare questa tecnica, perché gli altri processori sono bloccati allora moltiplico il tempo2 per il numero di processori usati T*P. Nel nostro caso il lavoro è N perché abbiamo usato N istanti di tempo con N processori.

Efficienza rapporto tra il miglior algoritmo sequenziale e il lavoro, oppure rapporto fra speed up e numero di processori, l'efficienza è molto utile perché è indipendente dal numero di processori utilizzati. L'intervallo considerato è un valore che va da 1/P a 1.

Considerazioni: è importante osservare che spesso l'efficienza è data dalla taglia del problema. Capita che per diverse taglie devo usare algoritmi differenti, sullo stesso problema. Il lavoro non dice tutto, bisogna considerare l'istanza o il numero di istanze per capire quale strategia usare.

2.1.2. Ordinare N numeri con meno di N processori

Ogni processore simula quello che facevano N/P processori di

un array lungo N. conviene emulare processori consecutivi.
2.2. Il Sorting nel modello a bit
2.2.1. Modello lineare
  Supponiamo che ogni processore è in grado di processare solo un numero costante di bit per volta.
  Misuriamo il tempo in bit step.
  Esempio confrontiamo due stringe:
    È possibile usare un array lineare dove ogni processore confronta una coppia di bit. In questo caso richiede O(k) passi.
  Possiamo farlo in tempo minore, confrontando 2 stringe a k bit.
2.2.2. Due stringhe k bit con array lineare e un albero binario a k foglie
  Di solito propagano l'input dall'alto che ha più priorità, i nodi interni dell'albero propagano sempre quello che viene dall'alto tranne nel caso in cui ci sia un uguale in alto, in quel caso propaga dal basso.
  In particolare usando l'albero completo è possibile notificare a tutti i processori quale è la stringa che rappresenta il numero più grande in 2 log k passi O(log k).
  Questo ci

Permette di costruire una rete di ordinamento nel modello a bit. Basta sostituire ogni processore nel modello a word con un albero binario completo a k foglie. Questa rete richiede (2N-1)2logk bit step per completare la fase 1 del sorting, si può fare di meglio con la comparazione lineare, ma utilizzare l'array per la comparazione con un approccio a pipeline in modo da massimizzare l'utilizzo dei processori.

Algoritmo di ordinamento d'array non è molto efficiente, non possiamo ottenere di meglio con questa architettura ad array o sulla matrice.

Considerazioni: L'ordinamento su array non è molto efficiente (speedup log P invece dovrebbe variare tra 1 e P), e non è possibile fare meglio, se si considera l'architettura ad array, con altre architetture invece possiamo fare meglio. Esistono dei limiti legati all'architettura di array/matrice, che ci dice che non possiamo avere di meglio. Questi sono limiti sulle architetture.

2.3. Lower

BoundsL'esistenza di questi limiti ci dice che abbiamo ottenuto il meglio. I modi di analizzare le caratteristiche di una rete:

• input/output bandwidth misurano la capacità della rete in ingresso (dati di input) e in uscita (output) Ω
• Esempi: per l'array solo per l'input impieghiamo (N) nel processore più a sinistra che matcha con il nostro upper bound quindi non si può fare meglio che il modello a word; Ω per la matrice invece ha k input per i k processori a sinistra anch'essa (N) però non matcha con l'upper bound che è N+k quindi non possiamo dire che è ottimale
• Bisezione di una rete è il minimo numero di archi che devono essere rimossi per disconnettere la rete in due metà con lo stesso numero di processori (+/-1 in caso è dispari), serve perché alcuni algoritmi partono da una configurazione e terminano con una configurazione diversa e può accadere che i dati in una

metà della rete debbano essere trasferiti nell'altra metà e viceversa, la bisezione è come un collo di bottiglia per quest'operazione. Esempi: nel caso dell'array la bisezione è (1) di nuovo l'ottimo, nel caso della matrice è min(k, N) oppure min(k, N)+1 se max(k, N) è dispari, nell'esempio è quindi (N). Diametro di una rete è la massima distanza tra ogni coppia di processori. La distanza fra due processori è la lunghezza della minima path che li contiene entrambi. Esempi: diametro nel caso dell'array è N-1, e nella matrice kxN un diametro di N+k-2. Avremo un lower bound per l'array di (N) e per la matrice (N+k) quindi entrambi ottimali. 3. Architetture 3.1. Ipercubo r r-1 Un Ipercubo è una rete di r dimensioni con 2 nodi e rx2 archi, ogni nodo etichettato con r bit. Due nodi sono connessi se le loro etichette differiscono di un solo bit. Archi di

livello 1 sono quelli che ci permettono di far cambiare il primo bit, mentre archi di livello 2 sono quelli che sono in grado di far cambiare il secondo bit e così via, cioè un arco di dimensione k è un arco che connette due nodi che differiscono nel k-esimo bit.

Il grado di ogni nodo è r = logN.

Bisezione (N/2) basta eliminare tutti gli archi lungo una generica dimensione k (togliamo un livello di archi).

Diametro r = logN (i passi che occorrono per cambiare i bit, meccanismo di routing per arrivare a destinazione). Immaginiamo il caso peggiore con tutti i bit diversi, riusciamo comunque a raggiungerlo in r passi, si confronta un bit per volta del vicino e si va a quello che mi avvicina a diventare il nodo obiettivo.

Simmetria appare come un dado ed è possibile ruotarlo su se stesso, e quindi ridefinire le etichette dei nodi, ad esempio ridefinire l'etichetta u nell'etichetta u' significa ridefinire tutte le etichette dei nodi (è possibile ridefinire anche).

Gli archi). Per capire l'etichetta del nodo ruotato:

Immersione di un architettura in un'altra:

È una funzione che mappa i nodi di un architettura (ospite) nei nodi dell'altra (ospitante) (il che vuol dire che un architettura è potente almeno quanto l'altra architettura).

Ad esempio è possibile mappare un array in un Ipercubo. Ma ci sono dei problemi alcuni processori che sono connessi nell'array che non sono connessi nell'Ipercubo (e quindi più costosi in termini di passi per arrivarci). Inoltre gli archi in grigio sono archi usati nell'ipercubo ma non nell'array.

Ci sono dei parametri per valutare la qualità dell'immersione di un architettura in un'altra:

• dilatazione di un arco (dell'architettura ospite) è la lunghezza delle path che simula un arco sulla architettura ospitante. La dilatazione di una immersione è la massima dilatazione su tutti gli archi dell'architettura ospite.

(sicapisce da quanti bit differiscono tra i nodi)

• Congestione di un arco (dell'architettura ospitante) è il numero delle path dell'architettura ospitante che utilizzano tale arco per simulare più archi dell'architettura ospite. La congestione di una immersione è la massima congestione su tutti gli archi dell'architettura ospitante. (quante volte uso un arco all'interno di una architettura, e vedo quale arco è usato di più, non si riesce a scendere sotto 2)
• Espansione è il rapporto tra il numero di nodi dell'architettura ospitante e dei nodi dell'architettura ospite. Cioè se N è il numero di nodi dell'architettura ospite (array) e N numero di nodi dell'architettura ospitante (Ipercubo) di solito avremo N / N ≈ 2 cioè circa il doppio dei nodi (N = 2^n, N = 2^m+1, N = 2^12+1, N = 2^8) nell'esempio i nodi sono 8 e 8 quindi l'espansione è 1.2
• Carico (introdotto ma

mai usato perché in alcuni casi prende 2 o più nodi dell'architettura ospite e li mette in un solo nodo di un'architettura ospitante): il numero massimo di processori dell'architettura ospite che vengono simulati da un solo processore dell'architettura ospitante. Dilatazione nel nostro esempio è 3 quindi l'immersione non è ottima. Possiamo mappare l'array nell'Ipercubo con parametri nettamente migliori usando un'assegnazione diversa di nodi ospiti nell'architettura ospitante. Codice Gray La codifica di due interi consecutivi differisce di un solo bit. Immergendo l'array nell'Ipercubo con il codice gray otteniamo parametri nettamente migliori, tutti i parametri uguali a 1. Possiamo dire che l'Ipercubo è potente almeno quanto l'array. Proprietà che vale non solo per l'array ma anche per la matrice: Considerazioni L'Ipercubo offre una potenza computazionale almeno uguale alle

Reti classiche ma ha come svantaggio il grado non costante (un processore di un Ipercubo con 8 nodi ha 3 vicini, mentre un processore di un Ipercubo con 1024 nodi ha 10 vicini). Per avere un grado costante sono state definite delle altre architetture chiamate varianti dell'Ipercubo: Butterfly, Wrapped butterfly, Rete di Benes, CCC (cube connected cycles), Shuffle exchange, De Bruijin graph.

3.2. Butterfly

• Ipercubo con nodi = N = 2^r, archi = r x 2, bisezione = N/2 e diametro = log N
• Butterfly (r dimensioni) 2 righe e r+1 colonne
• Ogni nodo è una coppia (riga, colonna), 2 nodi sono connessi se fanno parte di due colonne consecutive e se stanno sulla stessa riga (arco diretto) oppure differiscono esattamente nell'i-esimo bit (arco incrociato)
• Nodi = righe x colonne, Archi = r x 2 = r (perché l'ultima colonna non ha archi)