PDF de programación - Redes de Interconexión - TOPOLOGÍAS

Redes de Interconexión

José M. Cámara

([email protected])

v. 1.0

Redes de interconexión

• Estáticas o directas: formadas por enlaces

permanentes, punto a punto, entre los
diferentes nodos de la red.

• Dinámicas o indirectas: formadas por

enlaces no permanentes que se reconfiguran
en función de la demanda.

CONCEPTOS

• Número de nodos de la red
• Grado: número de enlaces por nodo
• Diámetro: máxima distancia mínima entre

dos nodos

• Ancho de bisección: número mínimo de

enlaces rotos al dividir la red en dos partes
iguales

• Coste: número de enlaces de la red

Coste del mensaje

• Tiempo de procesamiento: en el nodo fuente y destino. Es el tiempo

que se tarda en procesar un mensaje de salida y en recoger un mensaje
de entrada.

• Retardo de propagación: es el tiempo que tarda en desplazarse de un

nodo a otro la cabecera del mensaje

• Tiempo de transmisión: determinado por el ancho de banda del canal.
• Tiempo de almacenamiento: en buffers intermedios (si no hay flits)
• Grado de solapamiento (si hay flits)
• Tiempo de contención: por falta de disponibilidad de recursos
• Latencia: tiempo que invierte un paquete (mensaje) en trasladarse del

nodo fuente al destino.

• Throughput: capacidad del procesamiento del la red paquetes

(mensajes) por unidad de tiempo.

TOPOLOGÍAS ESTÁTICAS

Array lineal

ARRAY LINEAL

Grado=1 en los extremos

Grado=2 en el resto

ARRAY LINEAL

Diámetro = N-1= Coste

1

2

1

2

N-1

N

ARRAY LINEAL

Ancho de bisección=1

TOPOLOGÍAS ESTÁTICAS

Anillo

ANILLO

Grado=2 en todos los nodos

ANILLO

Diámetro = int (N/2)
Diámetro con enlaces unidireccionales = N-1

2

3

4

4

3

2

1

1

Coste = N

ANILLO

B= 2

TOPOLOGÍAS ESTÁTICAS
Anillo cordal de grado 4

TOPOLOGÍAS ESTÁTICAS
Barrell shifter de 8 nodos

BARRELL SHIFTER
NB

=

2 N
+−

N 2=

n

)1

−

G

= n

2 −

nNNC
(
=

+

2
2=D

2
1

TOPOLOGÍAS ESTÁTICAS

Árbol

ÁRBOL

1=B

1

2 −

= n
N
3=G

= n
D
= NC

)1
(2 −
1−

ÁRBOL GRUESO
D
= n
2 −
= n
=
12 −

GB =

2

= n
)1
(2 −
n
12)1
−
n
(
⋅−

C

1

N
G

TOPOLOGÍAS ESTÁTICAS

Estrella

ESTRELLA

G=1

B=1

C=N-1

D=2

TOPOLOGÍAS ESTÁTICAS

Malla

MALLA

)1

=

ndN =
dnD
= ndB
dnC
⋅=
G 2=
n

( −
1−

(

n

()1
− d

−

)1

TOPOLOGÍAS ESTÁTICAS

Toro

TORO

)2

ndN =
nD
⋅=
B
=
C =
G 2=

(
int d
nd
1
2 −
nnd
n

TOPOLOGÍAS ESTÁTICAS

Malla
Iliac

TOPOLOGÍAS ESTÁTICAS

Hiper-
cubo

Hiper-cubo

= n
12 −
B
nC
⋅=

n
12 −

n
N 2=
nG =
nD =

TOPOLOGÍAS ESTÁTICAS

CCC

Ciclos conectados en cubo
2⋅=
n

n

nN
D 2=
3=G
= n
12 −
B
n
123
−
n
C
=
⋅

Topologías Dinámicas

• Bloqueantes/No bloqueantes: una vez

establecida una determinada configuración,
en las redes bloqueantes habrá ciertas
posibilidades de conexión que queden
bloqueadas.

• Monoetapa/Multietapa: en función del

número de etapas de conmutación que se
deban atravesar para llegar a destino.

TOPOLOGÍAS DINÁMICAS

Bus

TOPOLOGÍAS DINÁMICAS

Crossbar

CROSSBAR: SWITCH POINT

Módulo de memoria compartida



W
R

/

Mux. de
control

Mux. de
datos



W
R

/



W
R

/



W
R

/


.
l
e
S

Arbitraje

Mux. de
direcciones


.
t
e
P


.
t
e
P

A
c
e
p
.


A
c
e
p
.



.
t
e
P

A
c
e
p
.


TOPOLOGÍAS DINÁMICAS

Red Omega

RED OMEGA: CONTACTO

E1

E2

SEL

S1

S2

RED OMEGA: CONTACTO

E1

E2

0

S1

S2

RED OMEGA: CONTACTO

E1

E2

1

S1

S2

RED OMEGA: RUTADO

Etapa 0

Etapa 1

Etapa 2

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

RED OMEGA: RUTADO

Etapa 0

Etapa 1

Etapa 2

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

RED OMEGA: RUTADO

Etapa 0

Etapa 1

Etapa 2

100

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

RED OMEGA: RUTADO

Etapa 0

Etapa 1

Etapa 2

100

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

RED OMEGA: RUTADO

Etapa 0
Etapa 0

Etapa 1
Etapa 1

Etapa 2
Etapa 2

000
000

001
001

010
010

011
011

100
100

101
101

110
110

111
111

100
100

000
000

001
001

010
010

011
011

100
100

101
101

110
110

111
111

TOPOLOGÍAS DINÁMICAS

Mariposa

4x4

4x4

4x4

4x4

4x4

4x4

4x4

4x4

MARIPOSA: RUTADO

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

4x4

4x4

4x4

4x4

4x4

4x4

4x4

4x4

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

MARIPOSA: RUTADO

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

1001

4x4

4x4

4x4

4x4

4x4

4x4

4x4

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

MARIPOSA: RUTADO

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

4x4

4x4

4x4

4x4

4x4

4x4

1001

4x4

0000
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111

Árbol grueso conmutado

Switches
Nivel 2

Switches
Nivel 1

Nodos

Hipercubo conmutado

Encaminadores modernos
• Disponen de 3 elementos principales:

– Colas de almacenamiento:

• De inyección: permiten al nodo local colocar

paquetes en la red.

• De tránsito: almacenan paquetes que no tienen

origen ni destino en el nodo local.

• De consumo: entregan paquetes al nodo local.

– Interconexión (crossbar limitado).
– Árbitro: toma las sobre encaminamiento y

resolución de conflictos.

Encaminadores modernos - colas

Lógica de
canal oeste

Lógica de
canal norte

Lógica de
canal sur

Lógica de
canal este

Encaminadores modernos - colas

Su espacio de almacenamiento se
establece en función del mecanismo
de control de flujo:

Store & forward: paquetes.
Wormhole: flits.
Virtual cut through: paquetes.

Se trata por defecto de colas FIFO ->
problemas de bloqueo de cabeza de
línea (HLB). Si la unidad de cabeza
no puede ser atendida, las siguientes
quedan bloqueadas aunque no entren
en conflicto.

Hay tantas colas de tránsito como
canales virtuales.

HLB
El coche rojo podría girar pero está bloqueado por el blanco.
El semáforo impide al blanco avanzar recto.

Google Earth

Encaminadores modernos -

arbitraje

• Selección: criterio empleado por el árbitro para seleccionar

el puerto de salida de entre los que permitan avanzar a un
paquete cumpliendo con su protocolo de encaminamiento.
Si el encaminamiento es estático, no existe política de
selección posible.

• Arbitraje: criterio empleado por el árbitro para asignar un
determinado puerto de salida entre varias colas de entrada
que compiten por él.

• Objetivo: combinar la eficiencia con la ausencia de

problemas fatales; típicamente la inanición.


Encaminadores modernos –

arbitraje

Encaminadores modernos –

arbitraje – políticas de selección
• Aleatoria: se asigna una salida al azar de entre las

posibles.

• Cola más corta: se elige el puerto de salida con

más espacio en la cola de entrada del nodo
destino.

• Smart: se realizan sucesivos intentos. Tiene
sentido si el encaminamiento es adaptativo.
Primero se intenta continuar por el mismo canal de
entrada; si no está disponible, se solicita cambiar
de dirección.

Encaminadores modernos –

arbitraje – políticas de arbitraje
• Aleatoria: se da servicio a uno de los

competidores seleccionado al azar.

• Roundrobin: se sigue una lista ordenada

para dar servicio a todos.

• Más antiguo: se da servicio al que más

tiempo lleve en espera.

• Cola más larga: se da servicio al canal que

mantenga la cola más larga.

Referencias

• W. J. Dally & B. Towles. Principles and Practices of
Interconnection Networks. Morgan Kaufmann, 2004.

• José Miguel Alonso. Redes de interconexión para sistemas

masivamente paralelos. Informe de investigación EHU-
KAT-IK-05-04.