Inter-PE network

I PE devono essere collegati attraverso opportune reti di interconnessione in modo da consentirne la comunicazione. Le reti possono essere:

• Statiche: se coppie di nodi hanno collegamenti stabiliti a priori. Ad esempio grafo completo.
• Dinamiche: se coppie di nodi hanno collegamenti variabili. Ad esempio Bus, Ethernet, Rete telefonica…

Nelle inter-PE net è obbligatorio l’utilizzo di reti statiche che non richiedono tempi di setup e di rilascio. I parametri fondamentali da tenere sotto controllo sono:

• C: numero di canali per nodo. Questo numero deve essere piccolo ma è bene che resti costante al variare del numero dei nodi n.
• D: diametro della rete. Massimo percorso minimo fra coppie di nodi. Misura il caso pessimo in una situazione di scorretta allocazione dei dati nei PE della macchina SIMD. Più è piccolo il diametro della inter-PE net, meno critica è l’allocazione.
• B: banda passante aggregata. Misura quanti bit al secondo il sistema nel suo complesso è in grado di trasportare. In sostanza misura le potenzialità teoriche della rete. Più la banda passante è grande più efficiente sarà la rete. Inoltre è opportuno che tale banda cresca con il numero di nodi. Si può avere una crescita lineare con n (che a lungo andare con n grande, creerà dei problemi) o una crescita più che lineare con n che è la soluzione migliore per l’approccio SIMD.
• P: politica di routing. Per macchine SIMD la politica di routing deve essere snella in modo da avere hardware semplice e, di conseguenza, veloce.

• C = 2
• D = n – 1
• B = (n – 2)
• P: politica di routing basata sull’ordinamento dei nodi.

• C = 2
• D =

→ n – 1 (se l’anello è monodirezionale).

→ (n – 1)/2 (se l’anello è bidirezionale).

• B = n
• P:

→ Se l’anello è monodirezionale si ha un routing semplice è praticamente identico a quello del linear array.

→ Se l’anello è bidirezionale la politica di routing si complica, ma il guadagno sul diametro è talmente

basso che non è consigliabile un anello bidirezionale.

Si collegano i nodi anche agli adiacenti degli adiacenti o a quelli di tre posti oltre...

• C = 4
• D ≈ n/4
• B ≈ 2n
• P: la politica di routing inizia a complicarsi leggermente. Bisogna valutare se conviene viaggiare via corda o via circonferenza in base a calcoli sui nodi adiacenti.

Per le reti 2D-Mesh si deve sfruttare al massimo la bidemnsionalità della struttura. Si devono cioè creare reti quadrate.

• C = 4
• D ≈ 2√(n)
• B ≈ 2n
• P: i nodi sono etichettati da due valori (senza salti). Si utilizzano tecniche di NEWS Grid (dove NEWS sta per North East South West).

C = 4

D ≈ √(n)

B ≈ 2n

P: la politica di routing con reti 2D-Torus si complica per via della circolarità della struttura.

3D-Mesh e 3D-Torus

Hanno caratteristiche strutturali del tutto simili alle reti 2D. I parametri delle 3D sono:

• C = 6
• D ≈ O( ³√(n) )
• B ≈ 6n
• P: valgono le considerazioni fatte per le 2D-Mesh e le 2D-Torus, aggiungendo una dimenzione.

Si assuma un cubo “d-dimensionale”:

• C = d.

Non avere C costante complica la costruzione della rete anche se d non è mai molto elevato visto che d=log₂n (in quanto n=2d). Ad esempio per 65.536 nodi (cioè 64K nodi) si ha un valore d pari a 16. Se si decide di utilizzare una rete a ipercubo, si deve stimare a priori un numero di nodi che costituira l’upper bound (cioè il limite superiore) di nodi della rete.

• D = d
• B = ½ n log2n.

Si ha la crescita più che lineare che si cercava fra le caratteristiche che doveva avere una inter-PE net.

• P: visto che si ha una distanza di Hamming fra vertici adiacenti, per sapere quanti salti si devono fare per raggiungere il destinatario, si deve calcolare la distanza di Hamming fra mittente e destinatario. Inoltre controllando che bit varia si riesce a capire in che direzione muoversi all’interno dell’ipercubo. La politica di routing consiste quindi in un semplice confronto bit a bit.

• C = 3
• D = 2 log₂n (dove log₂n è il numero di livelli dell’albero)
• B: cresce linearmente con n.
• P: la politica di routing è un po’ più complessa di quella pensata per le reti a ipercubo. Occorre una particolare etichettatura o la conoscenza del numero dei nodi da propagare ad ogni nodo.

La rete ad albero ha due grossi problemi:

• La radice dell’albero è un collo di bottiglia in quanto molte comunicazioni passeranno in media dal nodo radice. Per risolvere questo problema si usano i cosiddetti “Fat-Tree” nei quali la banda aumenta al decrescere del livello dell’albero (al livello radice si avrà una banda maggiore).
• La struttura ad albero non è omogenea, si ha una gerarchia intrinseca. Bisogna scegliere attentamente i programmi da mappare su una struttura del genere in quanto è facile utilizzare programmi gerarchici su reti omogenee ma non vale il viceversa.