Gian Luca Pozzato & Livio Robaldo
are proud to present…
Bleah! Che schifo…
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Introduzione
 Tra i sistemi distribuiti, i sistemi cluster hanno trovato larga diffusione:
1. Prestazioni buone
2. Architettura ideale per l’esecuzione di applicazioni parallele
3. Costi contenuti
 CLUSTER: sistema distribuito ottenuto collegando fra loro nodi
indipendenti mediante una rete locale
Nodi di tipo “blade”
Nodi indipendenti
Nodi montati su rack
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Introduzione (2)
 L’architettura direct network è molto utilizzata per la costruzione di
sistemi cluster
 Topologia di rete, flow control, switching e routing sono i concetti
fondamentali legati alle direct networks
 La tecnica di switching più utilizzata è il wormhole switching, che offre
le performance migliori
 In questo lavoro presentiamo nel dettaglio le caratteristiche e le
problematiche legate al wormhole switching, oltre ad un’ampia
panoramica sugli algoritmi di routing abbinati a questa tecnica
 Articolo di riferimento: [Mohapatra, 1998]
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
In questa presentazione…
 Introduzione alle diverse tecniche di switching
 Wormhole routing
 Topologie di rete nelle direct networks
 Problema del deadlock e soluzione
 Algoritmi di routing nel wormhole routing
 Conclusioni
 Bibliografia
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Reti multicomputers (direct networks)
Nodo
Nodo
Nodo
Rete locale di interconnessione
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Nodo
Reti multicomputers (direct networks) (2)
Unità
funzionali
…
…
Router
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Canali di output INTERNI
…
…
Canali di input INTERNI
Canali di input
ESTERNI
(canali di input)
Memoria
locale
Processore
Canali di output
ESTERNI
(canali di output)
Reti multicomputers (direct networks) (3)
 I nodi di una direct network comunicano attraverso lo scambio di
messaggi
Un messaggio viene diviso in PACCHETTI
PACCHETTO = la più piccola unità di informazione. Contiene
informazioni di routing e di sequenza
PACCHETTO
informazioni
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Info di
routing
Info di
sequenza
Reti multicomputers (direct networks) (4)
Quando si parla di reti multicomputers è necessario distinguere le
attività di routing, flow control e switching
ROUTING: determina il path che un pacchetto deve percorrere per
raggiungere la destinazione a partire dal nodo sorgente
FLOW CONTROL: riguarda l’allocazione di canali e buffers ad un
pacchetto durante il suo passaggio nel router. In caso di conflitto, la
politica di flow control interviene per stabilire quale pacchetto viene
bloccato a causa dell’indisponibilità di una risorsa (in possesso di un altro
pacchetto)
SWITCHING: è il meccanismo che stabilisce come i dati vengono
rimossi dal canale di input e posti nel canale di output
4 tecniche di switching…
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Circuit switching
 Prima che inizi il trasferimento dei dati viene stabilito un path dedicato
tra la sorgente e la destinazione
 Il path rimane allocato per l’intera trasmissione del pacchetto
 Una volta iniziato il trasferimento dei dati, il messaggio non viene mai
bloccato
 Non è richiesta bufferizzazione dei dati (grazie al path dedicato)
 Pesante overhead: durante la fase di trasferimento dei dati, tutti i
canali sono riservati per l’intero trasferimento del messaggio, con
conseguente degrado delle prestazioni
 Questa tecnica non viene usata nei sistemi multicomputer commerciali
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Packet switching
 Il messaggio viene diviso in pacchetti che sono instradati ognuno sulla
propria strada
 L’intero pacchetto viene memorizzato in ogni nodo intermedio ed
instradato al successivo nodo del path quando:
1. Il canale di output scelto è disponibile
2. Il nodo vicino ha un buffer libero per ricevere il pacchetto
 Ogni pacchetto contiene le informazioni di routing e può selezionare
un percorso piuttosto che un altro in base allo stato di congestione
della rete
 Il canale risulta occupato SOLO in fase di trasferimento di un
pacchetto
 Dato che ciascun pacchetto viene memorizzato in ogni nodo, il tempo
per trasmetterlo dal nodo sorgente al nodo destinazione è
proporzionale al numero di hops nel path; inoltre, è richiesto spazio di
bufferizzazione in ciascun nodo intermedio
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Virtual cut-through switching
 Il pacchetto viene memorizzato nel nodo intermedio solamente se il
successivo canale richiesto è occupato da un altro pacchetto
 Nel caso peggiore (blocco ad ogni nodo intermedio) coincide con il
packet switching
 Poco usata a causa degli eccessivi costi: dato che molti messaggi
potrebbero essere bloccati in un nodo, ogni nodo deve mettere a
disposizione notevoli risorse di bufferizzazione
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Wormhole switching
 E’ una variante del virtual cut-through che consente di superare il problema
della necessità di ampi spazi di bufferizzazione
 Un pacchetto è trasmesso in unità dette flits
 FLIT=la più piccola unità di un messaggio cui viene applicato il controllo di
flusso
 L’header flit contiene tutte le informazioni necessarie per l’esecuzione del
routing, compreso l’indirizzo di destinazione; gli altri flits contengono
soltanto dati
 I flit vengono trasmessi “in fila” in modo canalizzato
 Quando l’header flit viene bloccato, il blocco si propaga a tutti i flit che
seguono, i quali vengono bufferizzati nei nodi intermedi
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Wormhole switching (2)
MESSAGGIO
PACCHETTO
FLITS
D
D
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
D D
D
D
D
D
D H
Routing in sistemi Cluster
Canali fisici di collegamento
Flit
2
3
1
2
3
2
1
3
1
2
3
1
2
3
2
1
3
Buffer
Bufferdi
dioutput
input
NODI del cluster
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
1
2
3
1
2
3
Un flit può avanzare...
Avanti
Savoia!
 Quando risiede in un canale di input
 Quando gli viene allocato un buffer di output
 Quando gli viene allocato il canale fisico
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Wormhole switching: vantaggi e svantaggi
Vantaggi:
 Ogni nodo deve memorizzare un solo flit (anche se alcune implementazioni
richiedono la memorizzazione di flit multipli per migliorare le prestazioni)
 La limitata richiesta di spazio di bufferizzazione rende inferiori costi e
dimensioni del sistema multicomputer.
Svantaggi:
 Il solo header flit conserva le informazioni di routing: se non può avanzare
nella rete, il blocco deve essere propagato a tutto il pacchetto.
 Il deadlock è una conseguenza di questo fatto.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Routing in sistemi Cluster: richiesta dello stesso buffer di output
Flit
2
3
1
2
3
2
1
3
1
2
3
Ops..
3
1
2
1
2
3
3
1
2
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
Flit
2
3
 Un verme passa, l’altro si blocca
 Il blocco si propaga all’indietro a tutti i flit del pacchetto
 Quando il primo verme è passato passa anche l’altro
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
1
2
3
1
2
3
Deadlock
1
2
1
2
3
1
2
3
4
1
2
3
4
5
1
1
4
2
3
5
1
Ah! Il blu ed il verde
vogliono lo stesso buffer
di output. Il verde
continua ed il blu si
blocca
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
1
2
1
2
3
4
E, invece,
il verde non
1
2
3
continua...perchè qui
vuole un buffer in cui
c’è un flit del blu: si
blocca anche lui
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Topologie di rete
 I nodi del cluster sono interconnessi tra loro attraverso una rete.
 I nodi comunicano tra loro attraverso scambio di messaggi che vengono inviati
lungo la rete.
 La scelta della tecnologia e della topologia della rete incide pesantemente
sulle prestazioni del cluster.
Le topologie di rete possono essere classificate in
Direct
Indirect
I nodi sono collegati tra
loro attraverso links point
to point o diretti
I nodi sono collegati tra
loro attraverso degli
switch
Maggiore scalabilità: soluzione più utilizzata
Il wormhole switching viene utilizzato in tutte e due, ma noi vedremo solo
topologie direct
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Topologie di rete (2)
 Le topologie di rete possono essere descritte attraverso un grafo in cui i vertici
sono i nodi del cluster e gli archi sono i canali fisici che li collegano
 n-dimensional mesh: n dimensioni e ki nodi nella dimensione i (i=0, 1, …, n-1)
 k-ary n-cube: k nodi in ciascuna delle n dimensioni, con wraparound connections
ESEMPI
mesh 3D con k=3 in
ciascuna dimensione
5-ary 2-cube (torus)
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Topologie di rete (3)
 Nella realtà, vengono utilizzate soprattutto tre sottoclassi:
 L’hypercube: n-dimensional mesh con k fisso a 2 in ogni dimensione
(es. Intel iPSC/1, nCUBE)
 Il torus: un k-ary n-cube con n fisso a 2 (es. Cray T3D)
 Mesh 2D (es. Intel Paragon)
ESEMPI di hypercube:
2-cube
(n=2)
ESEMPI di mesh 2D:
3-cube
(n=3)
K=4
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
K=8
Topologie di rete (4)
 In generale un n-dimensional mesh è una topologia asimmetrica: nei nodi al
centro della maglia abbiamo una densità di traffico maggiore rispetto a quella
nei nodi sulla periferia.
 Hypercube e torus, invece, sono topologie simmetriche: ogni nodo ha la stessa
connettività con gli altri nodi.
Vediamo l’effetto che questo ha sui parametri di una rete…ricordo che essi sono:
Diametro: lunghezza del più lungo shortest path tra due qualsiasi nodi della rete
Bisection cut: numero di link che deve essere “tagliato” per dividere la rete in due
metà uguali.
Chiaramente…
 Il diametro deve essere minimizzato
 Il bisection cut deve essere massimizzato
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Topologie di rete (5)
Vediamo un confronto…a parità di nodi n, si ha che:
Diametro:
2nx2n 2DMesh >> 2nx2n 2DTorus >> 2nHypercube
Bisection cut:
2nx2n 2DMesh << 2nx2n 2DTorus << 2nHypercube
(2n)
(2n+1)
(22n-1)
Esiste anche una stima del costo della rete: la bisection density, che è data dal
prodotto del bisection cut e della banda del canale.
Sembrerebbe quindi che la topologia hypercube sia una delle più costose…però
bisogna osservare che, essendo l’hypercube una struttura più “fitta” di links, è
necessaria molta meno banda rispetto ad un torus (ed ancora meno rispetto alla
mesh) per ottenere le stesse prestazioni (latenza e throughput). Quindi…
Bandwidth:
2nx2n 2DMesh >> 2nx2n 2DTorus >> 2nHypercube
Morale della favola: a parità di costo, l’hypercube ha un diametro minore
del Torus che ha un diametro minore della mesh. Un diametro minore
significa cammini più corti…e quindi meno latenza e più throughput.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Ah già…dimenticavo…
Cosa sono latenza e throughput?
latenza: tempo che la rete impiega a recapitare un messaggio.
throughput: massimo tasso di messaggi che può essere immesso nella rete
senza che la latenza media cresca (la rete va in saturazione).
Nelle reti cluster, come si è visto, l’unità di trasferimento è il flit; ne consegue che
se Tc (tempo di ciclo) è il tempo che un flit impiega a fare un hop e se D è il numero
di nodi attraversati, la latenza di tutto il pacchetto di dimensione L è…
Tm(L) = Tc x (D + L / W)
Dove W è la dimensione di ogni singolo flit.
Diminuendo il diametro, quindi, diminuiscono i valori D nei trasferimenti di pacchetti
tra i nodi del cluster e, quindi, diminuisce la latenza.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Algoritmi di routing
Un algoritmo di routing, in generale, si può classificare in vari modi…
Source Routing
Distributed Routing
L’intero
Il cammino
cammino
sorgente-destinazione
sorgente-destinazione
viene
èstabilito
stabilitodisul
volta
nodo
in volta
sorgente
dai nodi
prima
intermedi
che il
attraverso
messaggio
cui i il messaggio
sia spedito transita
Deterministici
Adattativi
I messaggi sono sempre instradati
I messaggi sono instradati
lungo uno dei camminiIlpiù
corti trasorgente-destinazione
cammino
Il cammino
sorgente-destinazione
attraversoèqualsiasi cammino
sorgente e destinazione
unico
vieneedstabilito
è determinato
di volta solo
in volta
sulla
daibase
nodi e destinazione
tra
sorgente
degli
intermedi
indirizziedidipende
sorgente
dalle
e destinazione
condizioni
attuali della rete (guasti, traffico, …)
Minimali
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Non minimali
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Deadlock free routing
Sia gli algoritmi deterministici che gli algoritmi adattativi possono essere
Deadlock free
La tecnica solitamente utilizzata per risolvere il problema del deadlock è quella del
Deadlock avoidance
E’ possibile dimostrare che il deadlock non può mai verificarsi se vengono rispettati
i teoremi che ci apprestiamo a vedere (uno per gli algoritmi deterministici e l’altro
per gli adattativi).
Tali teoremi costituiscono delle condizioni necessarie e sufficienti per il deadlock
avoidance.
Teorema:
Condizione necessaria e sufficiente per il deadlock avoidance in algoritmi
deterministici è che il grafo di dipendenza dei canali non abbia cicli.
Questo teorema è solo condizione sufficiente per gli algoritmi adattativi...
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Deadlock free routing (2)
Teorema:
Condizione necessaria e sufficiente per il deadlock avoidance in algoritmi
adattativi è che esista una sub-routing function R1 connessa e priva di cicli
nel suo extended channel dependency graph.
Magari ci vuole qualche definizione...
• Una routing function R:NxNp(C) è una funzione che associa, ad ogni coppia di
nodi (ns, nd)  NxN, l’insieme dei canali p(C) su cui si può spedire un flit da ns per
raggiungere nd.
• Una subrouting function R1 di R è una funzione che implementa un sottoinsieme
delle associazioni di R.
• Una routing\subrouting function R è connessa se per ogni coppia di nodi (ns, nd) si
ha che R(ns, nd) non è vuoto.
• Un extended channel dependency graph della routing function R è un grafo i cui
nodi sono i canali presenti in R ed in cui esiste un arco (ci, cj) se R permette un
cammino tra due nodi che passa per ci e cj (e ci precede cj in tale cammino).
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Un esempio...
Invece che vedere la dimostrazione dei due teoremi [Duato, 1994], vediamo un
esempio del secondo...che è più complicato...
Consideriamo la seguente topologia...
CH0
n0
n1
CA0
CA3
CA1
CH1
CA2
n3
n2
CH2
Un semplice algoritmo che rispetta il secondo teorema:
 Se il nodo corrente ni è uguale al nodo destinazione nj, consuma il messaggio.
 Altrimenti, spedisci il flit sul canale CAi (i  j) o sul canale CHi (j > i)
Tale algoritmo è ovviamente adattativo, perchè, in quasi tutte le
situazioni, ho più di un canale in cui scegliere di spedire il flit.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Un esempio...
Consideriamo ora subrouting function di R, che chiamiamo R1 e che è uguale ad R
eccetto che...
 CA0 non viene utilizzato.
 CA1 e CA2 possono essere usati solo per spedire flits ad una destinazione con
indice più piccolo del nodo corrente.
Il grafo delle dipendenze è...
CH0
CH1
CA3
E’ privo di cicli!!! n0
Per il teorema visto, questo
algoritmo adattativoCA3
non
Da n3 posso raggiungere
CA2
mai
in deadlock
I canali
CHn possono
n0, n1, n2 passando entra
per
CA1
CA1 può raggiungere solo n0
spedire
con
Da n2
possosolo a nodin3
CH1
passandoCH0
soloeda
CA2 e CA3
indicisolo
superiori ad n
raggiungere
CH2
n0 ed n1 passando
per CA3 e CH0
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Topologia
CH0
n1
CA0
CA1
CH1
CA2
n2
CH2
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Wormhole routing deterministico
 Il path è determinato SOLO dalla coppia sorgente-destinazione
 Per ogni coppia sorgente-destinazione, tutti i pacchetti seguono il
medesimo percorso
 Idea di base: il deadlock è prevenuto ordinando i canali che un messaggio
deve attraversare
 Un messaggio percorre i canali in ordine ascendente o discendente,
evitando dei cicli nel grafo delle dipendenze dei canali
 Un esempio di routing deterministico è il dimension-order routing [Dally e
Seitz, 1987]
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing
 Schema di routing deterministico in cui il path selezionato attraversa le
dimensioni della rete in sequenza
 Le dimensioni della rete sono preventivamente organizzate mediante un
ordine monotono x1, x2, …, xn
 Il messaggio compie prima tutti gli spostamenti nella direzione x1, quindi
nella direzione x2,…, fino al raggiungimento della destinazione
 A questo punto, il messaggio attraversa la rete nella successiva
dimensione, fino a che non raggiunge la destinazione
 Il deadlock è scongiurato dal fatto che i messaggi non attraversano MAI la
rete nella direzione inversa dell’ordine di dimensione
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing su hypercube
 I nodi dell’n-cube vengono rappresentati da una stringa binaria di n bit
 L’indirizzo di destinazione viene memorizzato nell’header flit
 Quando un nodo riceve un messaggio esegue l’XOR tra il proprio indirizzo
e l’indirizzo della destinazione:
1. Se è zero, consuma il messaggio
2. Se è diverso da zero, inoltra il messaggio nella dimensione
corrispondente all’uno del risultato più a destra (o più a sinistra)
 Si parla di e-cube routing ed è una tecnica minimale
 Vediamo un esempio…
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing su hypercube (2)
110
010 S
XOR
111
011
010
101
XOR
110
011
001
101
111
011
D
100
000
XOR
010
101
101
001
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
100
101
001
Dimension-order routing su mesh 2D
 Chiamato routing XY, è minimale
 Le due dimensioni della mesh sono etichettate con X e Y
 Un messaggio viene prima inoltrato completamente nella direzione X,
quindi viene inoltrato completamente nella direzione Y
 Nelle mesh multidimensionali si esegue il medesimo algoritmo,
completando il routing in una direzione prima di passare alla successiva (le
dimensioni sono ordinate)
 Questa tecnica è deadlock-free
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing su mesh 2D (2)
17
Possibili
turns
04
Direzione Y
62
30
Direzione X
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing (conclusione)
 Esistono algoritmi di routing minimali per k-ary n-cubes che sfruttano i
canali virtuali [Dally e Seitz, 1987]
 In ogni caso, il dimension-order routing è adatto ad una distribuzione
uniforme del traffico sulla rete (sceglie il cammino minimo per tutto il
messaggio)
 Non sfrutta la possibilità di cammini multipli tra coppie di nodi sorgentedestinazione
 Non è adatto a gestire:
1. Guasti sulla rete
2. Congestione della rete
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Dimension-order routing vs Routing adattativo
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Wormhole routing adattativo
 Gli algoritmi deterministici calcolano uno e un solo cammino tra sorgente e
destinazione
 Per gestire guasti e reagire opportunamente alla congestione della rete è
necessario che gli algoritmi di routing calcolino dei cammini alternativi per i
messaggi
 Gli algoritmi che offrono questa opportunità sono detti ADATTATIVI che si
dividono in:
Totalmente adattativi
Parzialmente adattativi
I messaggi
vengono
instradati
su une
Tutti
i possibili
cammini
tra sorgente
sottoinsieme
dei possibili
cammini
destinazione
sono messi
a tra
sorgente
destinazione dei
disposizione
perel’instradamento
messaggi
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fully-adaptive: algoritmo PFNF
 Vediamo nel dettaglio un altro esempio: l’algoritmo positive-firstnegative-first (PFNF) per mesh bi-dimensionali, illustrato in [Upadhyay et
al., 1997]
 L’algoritmo usa due canali virtuali per ciascun canale fisico
 I messaggi vengono inoltrati nelle due reti virtuali in modo da distribuire
uniformemente il carico ed ottenendo un algoritmo di routing fully-adaptive
 Utilizzando il teorema di Duato si può provare che l’algoritmo PFNF è
deadlock free
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fully-adaptive: algoritmo PFNF (2)
 La rete fisica è logicamente divisa in due reti virtuali: VN1 e VN2
 Due canali virtuali associati al medesimo canale fisico si trovano in reti
virtuali diverse
 La rete virtuale VN1 è gestita mediante le restrizioni dell’algoritmo positive
first
 La rete virtuale VN2 è gestita mediante le restrizioni dell’algoritmo negative
first
 Quando il nodo destinazione si trova nelle direzioni <+x, +y> e <-x, -y>, il
messaggio viene instradato senza restrizioni
 Quando il nodo destinazione si trova nelle direzioni <-x, +y> o <+x, -y>
vengono applicate le restrizioni positive first e negative first
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
…
Fully-adaptive:
VC=Ø algoritmo PFNF (3)
2. Se tutti gli elementi in Routing_tag
≥0 gli elementi in Routing_tag ≤0
1. Se tutti
…
Se Routing_tag[0] >0
Se Routing_tag[0] <0
3c. Se Routing_tag[1] >0
aggiungi
i canali:
Nodo sorgente:
(x0 ,axVC
1)
aggiungi a VC i canali:
…
a VC il canale:
► vcVN1((x0 , x1),(x0 +1, x1)) ► vc aggiungi
((x
,
x
VN1
0 >01),(x0 -1, x1))
3a.
Se
Routing_tag[0]
Nodo destinatario:
(d
,
d
)
►
vc1
((x0 ,lox1restituisce.
),(x0 , x1 +1))
0
1
► vcVN2((x0 , xSE
x1))vi
è►
unvc
solo
canale
in VC,
VN1
d0i +1,
- xi Se
>0
ALLORA
METTI
1),(x
…
((x
,
x
),(x
-1,
x
))
VN2
0
1
0
1
aggiungi
a VC
il canale:
… ne
Se Routing_tag[1]SE
>0 di - xi Altrimenti,
sceglie
uno a random o<0
<0Se
ALLORA
METTI
-1
3b.
Se
Routing_tag[0]
Routing_tag[1]
<0
► vc…
((x
x1)) (=se
VN1
0 , x10),(x0 +1, bias
aggiungi a VC SE
i canali:
impiegando
un
multiplex-turn
di - xi =0
ALLORA
METTI
aggiungi
a VC
il canale:
aggiungi
a
VC
i
canali:
…
1
Routing_tag:
1
► vcVN1((x0 , x1),(x0 ,x1+1))
possibile,
cerca
proseguire
nella
3d.
Se di
Routing_tag[1]
<0 direzione
► vcsi
,x1vc
-1))
VN2((x0 , x1),(x0 -1, x1))
VN1((x0 , x1),(x0►
► vcVN2((x0 , x1),(x0 ,x1+1))
intrapresa,
compiere
turni)
a VC dei
il canale:
…((x0aggiungi
► vcevitando
, xdi
VN2
1),(x0 ,x1-1))
…
► vcVN2((x0 , x1),(x0 , x1 -1))
…
return VC
Routing_function:
VN1:
VN2:
Selection_function(VC):
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fully-adaptive: algoritmo PFNF (4)
 Vediamo un esempio di funzionamento: il mittente del messaggio è (2,2), il
destinatario è (5,0)
(2,2)
(5,0)
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fully adaptive: conclusioni
 La flessibilità garantita dai meccanismi di routing adattativo migliorano le
performance, ma richiedono una crescita della complessità di gestione da
parte dell’hardware, che rallenta notevolmente i router
 E’ stato osservato che gli algoritmi adattativi non migliorano
necessariamente le prestazioni di una rete a bassa dimensione
 Un netto miglioramento si riscontra nelle reti ad alta dimensione, tipo
hypercubes, e nelle reti in cui il traffico non è distribuito uniformemente
 Spesso ci si accontenta di un grado di adattabilità più basso, in cambio di
una gestione più semplice: algoritmi parzialmente adattativi
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Partially adaptive routing
 Glass e Ni hanno proposto il “turn model”, sulla base del quale sono stati
sviluppati diversi algoritmi parzialmente adattativi
 Soffermiamoci ancora sulle mesh 2-D: secondo il modello, ci sono otto
possibili turni
 L’algoritmo xy previene il deadlock impedendo 4 turns:
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Partially adaptive routing (2)
 Per impedire il deadlock è sufficiente impedire 2 soli turni, uno in ciascun
ciclo
 A seconda di quali turns vengono permessi/impediti si ottengono i seguenti
algoritmi parzialmente adattativi:
Algoritmo west-first:
Algoritmo north-last:
Algoritmo negative-first:
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Partially adaptive routing: west-first routing
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Deadlock recovery
 Come discusso, la prevenzione del deadlock richiede l’uso di risorse
aggiuntive ed una gestione impegnativa
 Alcuni studi hanno evidenziato che le situazioni di potenziale deadlock
sono rare nei sistemi multicomputers
 Impiegare risorse aggiuntive per prevenire situazioni rare non è una buona
scelta
 Il deadlock recovery è una buona alternativa alla prevenzione del deadlock
 I messaggi vengono instradati senza restrizioni permettendo la formazione
di cicli
 Un meccanismo di deadlock detection identifica potenziali configurazioni di
deadlock; in tal caso, un opportuno schema di recovery rompe il ciclo
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Deadlock recovery: disha
 Disha è un esempio di strategia di deadlock recovery [Anjan e Pinkston,
1995]
 Il recovery è realizzato mediante un singolo flit buffer presente in ciascun
nodo, chiamato deadlock buffer
 Tale buffer aggiuntivo viene utilizzato soltanto in caso di situazioni di
potenziale deadlock
 Durante il recovery, i deadlock buffers formano una “strada deadlock-free”
 Al formarsi di un ciclo, uno dei messaggi del ciclo viene instradato nella
strada deadlock-free e gli altri messaggi possono procedere
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Deadlock recovery: disha (2)
Viene fissato un time-out di
permanenza di un messaggio in
un nodo. Scaduto il time out, il
messaggio è considerato
“deadlocked”
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fault tolerant wormhole routing
 Nelle reti multicomputers di grandi dimensioni non si può trascurare
l’importanza dei malfunzionamenti dei nodi
 Gli algoritmi di routing dovrebbero garantire che un pacchetto raggiunga la
destinazione, qualora i nodi sorgente e destinazione siano connessi
 In letteratura sono stati presentati diversi algoritmi SPECIFICI che
consentono di reagire ad eventuali guasti nella rete
 Glass e Ni hanno proposto un’estensione dell’algoritmo Negative-first che
lo rendono in grado di reagire ai fallimenti [Glass e Ni, 1993]
 Vengono rilassate le condizioni di non adaptivity: il pacchetto viene fatto
“girare attorno” al faulty node
 Il pacchetto viene scartato qualora sia impossibile instradarlo ulteriormente
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Fault tolerant wormhole routing (2)
 Un altro approccio è quello di [Varavithya et al., 1995]
 Estensione dell’algoritmo PFNF combinando wormhole routing e virtual
cut-through
 Quando un pacchetto incontra un guasto, viene instradato nei cammini
alternativi offerti dall’algoritmo a meno che non si trovi nell’ultima
dimensione
 In tal caso, il messaggio viene completamente bufferizzato in un nodo
adiacente a partire dal quale viene successivamente ritrasmesso
 Questa soluzione offre ottime performance; inoltre, non richiede hardware
aggiuntivo per la gestione dei guasti
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Conclusioni
 Il wormhole routing è la tecnica di switching più usata nei sistemi
multicomputer, ma ci sono diversi problemi aperti
 E’ necessario proseguire lo studio degli algoritmi adattativi (al momento,
non sembrano efficienti al punto di giustificare i costi aggiuntivi)
 Gli algoritmi di routing fault-tolerant sono stati valutati assumendo
fallimenti casuali dei nodi. Sarebbe interessante studiare meccanismi che
permettano di introdurre fallimenti mirati
 Sono necessari algoritmi di routing specifici per certe applicazioni
 Abbiamo presentato algoritmi di routing implementati dall’hardware del
router; tuttavia, per reti con elevate prestazioni ma costi accettabili è
possibile implementare alcune funzionalità via software (schemi di routing
ibrido)
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Bibliografia
Anjan e Pinkston, 1995. K. V. Anjan e T. M. Pinkston. An Efficient, Fully
Adaptive Deadlock Recovery Scheme: DISHA. 22° International
Symposium on Computer Architecture, 201-210, 1995.
Dally e Seitz, 1987. W. J. Dally e C. L. Seitz. Deadlock Free Message
Routing in Multiprocessor Interconnection Networks. IEEE Trans. Comput.,
Vol. 36(5), 547-553, 1987.
Duato, 1994. J. Duato. A necessary and Sufficient Condition for Deadlockfree Adaptive Routing in Wormhole Networks. In Proceedings of the
International Conference on Parallel Processing, Vol. I, 142-149, 1994.
Glass e Ni, 1993. C. J. Glass e L. M. Ni. Fault-tolerant Wormhole Routing
in Meshes. In Proceedings of the International Symposium on FaultTolerant Computing, 240-249, 1993.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing
Bibliografia (2)
Mohapatra, 1998. P. Mohapatra. Wormhole Routing Techniques for
Directly Connected Multicomputer Systems. ACM Computing Surveys, Vol.
30(3), 374-410, 1998.
Ni e McKinley., 1993. L. M. Ni e P. K. McKinley. A Survey of Wormhole
Routing Techniques in Direct Networks. IEEE Computer, Vol. 26(2), 62-76,
1993.
Upadhyay et al., 1997. J. Upadhyay, V. Varavithya e P. Mohapatra. A
Traffic-balanced Adaptive Routing Scheme for two-dimensional Meshes.
IEEE Trans. Comput., Vol. 46(2), 190-197, 1997.
Varavithya et al., 1995. V. Varavithya, J. Upadhyay e P. Mohapatra. An
Efficient Fault-Tolerant Routing Scheme for two-dimensional Meshes. In
Proceedings of the International Conference on High-Performance
Computing, 773-778, 1995.
Gian Luca Pozzato & Livio Robaldo – Wormhole routing