– Introducción
– Redes basadas en conmutadores
– Redes basadas en encaminadores
– Estrategias de comunicación
– Conflictos en la comunicación
La red de comunicación de los computadores paralelos
? Los sistemas paralelos necesitan un soporte robusto para la comunicación de procesos, sea para acceder a memoria compartida (centralizada, SMP, o distribuida, DSM), o sea para transportar mensajes entre procesos (MPP).
Aunque la red de comunicación es, en teoría, independiente del modelo, se utilizan redes adaptadas a cada modelo.
Introducción
? Los multiprocesadores SMP suelen utilizar un bus para acceder a memoria.
(Gp:) M
(Gp:) P
(Gp:) C
(Gp:) bus
? Aunque el bus es una red sencilla y fácil de gestionar, tiene problemas de escalabilidad:
– no admite más que una comunicación simultánea.
– se satura cuando crece el número de procesadores.
La latencia de los accesos es inde-pendiente de la posición de memoria a la que se accede: todos los datos están a la misma “distancia” (UMA).
Introducción
? Para poder conectar muchos procesadores hay que distribuir la memoria (aunque tal vez sea compartida: DSM).
Hace falta otro tipo de red de comunicación.
? La latencia de los accesos a memoria o de los mensajes no es constante: la comunicación con los procesadores más cercanos será más rápida.
El comportamiento de la red de comunicación es muy importante para minimizar las latencias.
(Gp:) P
(Gp:) C
(Gp:) M
(Gp:) red general
(Gp:) R
Introducción
? Algunas características deseables en las redes de comunicación:
? que la latencia de las comunicaciones sea baja.
? que se permitan muchas comunicaciones simultáneas (es decir, tener un alto throughput).
? que pueda seguir en funcionamiento aunque existan fallos (averías) en la red.
? que sea fácil de construir y ampliar, y que existan algoritmos simples para encontrar los caminos.
Introducción
? La infraestructura de comunicación tiene dos partes:
– el hardware
conexiones, conmutadores, encaminadores de mensajes, interfaces con los procesadores.
– el software
protocolos de comunicación.
Introducción
? La topología representa la forma de la red; es decir, especifica las conexiones entre procesa-dores por medio de un grafo.
? Componentes del grafo:
– nodos: procesadores, o dispositivos especiales para la gestión de mensajes.
– arcos: conexiones entre nodos.
Introducción: topología
? Características topológicas principales:
? Complejidad
– Grado: número de conexiones de los nodos. Si es idéntico en todos, la red es regular.
– Simetría: misma visión de la red desde todos los nodos.
– Escalabilidad: facilidad de ampliación.
? Fiabilidad
– Tolerancia a fallos.
– Conectividad de arcos y nodos: componentes que hay que eliminar para obtener un grafo no conexo.
Introducción: topología
? Tráfico
– Bisección: conexiones que hay que eliminar para dividir el grafo en dos partes iguales.
? Distancias (latencia)
– Distancia media: d = S dij / P(P-1)
– Diámetro: distancia máxima entre dos nodos.
? Características topológicas principales:
Introducción: topología
1. Dinámicas
– redes de conmutadores
– para sistemas SMP (no sólo)
– provienen de la red telefónica
? Dos tipos de redes:
2. Estáticas
– encaminadores de mensajes (routers)
– para sistemas MPP
Introducción: clasificación
? Conmutador: dispositivo que conecta varias entradas y salidas.
E0 ? S0, S1
E1 ? S0, S1
E0 ? S0
E1 ? S1
E0 ? S1
E1 ? S0
(Gp:) grado k=2
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) E0
(Gp:) E1
(Gp:) S0
(Gp:) señales de control
(Gp:) S1
Redes con conmutadores
1. Red Crossbar: todos conectados con todos.
Cada conmutador conecta una fila y una columna.
El coste puede ser muy alto: O(P2)
Redes con conmutadores
2. Redes multietapa
Los conmutadores se organizan en varias etapas, y las conexiones entre distintas etapas se hacen por medio de una “permutación”.
(Gp:) proc.
(Gp:) P0
(Gp:) Pp-1
(Gp:) proc.
(o mem.)
(Gp:) P0
(Gp:) Pp-1
(Gp:) una permutación
Redes con conmutadores
? Ejemplo: red Omega
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) 4
Conexiones entre conmutadores: barajado perfecto (perfect shuffle).
(Gp:) 0
(Gp:) 2
(Gp:) 4
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:)
(Gp:) 0
(Gp:) 2
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 4
Barajado perfecto:
[0, 1, 2, …, P-1] ?
[0, P/2, 1, P/2+1, …, P/2-1, P-1]
logk P etapas
P/k conmutadores por etapa
? en total P/k × logk P conm.
Rotación de un bit:
4 (100) ? 1 (001)
5 (101) ? 3 (011)
Redes Omega
? Red Omega
(Gp:) 0
(Gp:) 2
(Gp:) 4
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:)
(Gp:) 0
(Gp:) 2
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 4
Diámetro: logk P
Distancia med.: logk P
Simétrica (regular)
Grado: 2, 4… (k)
Tolerancia a fallos: baja
Redes Omega
? Encaminamiento en la red Omega (routing)
¿Cómo se escoge el camino para ir de i a j?
1 Bits de la dirección destino
0: salida 0 / 1: salida 1
? 6 (110)
(Gp:) 0
(Gp:) 2
(Gp:) 4
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 0
(Gp:) 2
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 4
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) 0
2 Registro de encaminamiento: i xor j
0: seguir / 1: cruzar
RE = 100 xor 110 = 010
(Gp:) 1
(Gp:) 0
Redes Omega
? Conflictos de salida
La red Omega admite P comunicaciones simultáneas, pero no cualesquiera (red bloqueante).
0 ? 1 y 6 ? 0?
(Gp:) 0
(Gp:) 2
(Gp:) 4
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 0
(Gp:) 2
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 4
– anular
– utilizar búferes
– dividir en dos
Núm. de permutaciones: P!
Se pueden hacer:
2 P/2 log P = P P/2
P=8 ? 10%; P=16 ? 0,02%
Redes Omega
(Gp:) 0
(Gp:) 2
(Gp:) 4
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 0
(Gp:) 2
(Gp:) 6
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 4
? Broadcast
De uno a todos los procesadores
(Gp:) BC
(Gp:) BC
(Gp:) BC
(Gp:) BC
(Gp:) BC
(Gp:) BC
(Gp:) BC
Redes Omega
Red Butterfly
? Otro ejemplo: red Butterfly
Resumen
? La red se forma mediante encaminadores de mensajes (routers).
(Gp:) red de comunicación
(Gp:) procesador/memoria local
(Gp:) router
(Gp:) Gestor de comunicaciones
(Gp:) conexiones de red
Nodo de una red estática: proc./mem. + encaminador.
La distancia entre nodos no es constante.
Redes con encaminadores
Enlaces bidireccionales.
? Un conjunto de puertos de E/S para recibir y enviar paquetes; un conjunto de búferes para almacenar temporalmente los paquetes; y un autómata para procesar paquetes y asignarles una salida.
(Gp:) puertos de entrada
(Gp:) puertos de salida
(Gp:) procesador local
(Gp:) procesador local
(Gp:) enlaces de
comunicación
(Gp:) enlaces de
comunicación
(Gp:) búferes
(Gp:) búferes
(Gp:) func. encam.+ crossbar
Encaminador de mensajes
1 Red crossbar : todos con todos.
Compleja de construir y de coste elevado cuando P es grande.
Además, el grado de los encaminadores (número de conexiones) no es constante: P-1.
Topologías más utilizadas
2 Redes de una dimensión: cadena y anillo.
Grado:
Simetría:
Toler. Fallos:
Diámetro:
Distancia media:
2
2, regular
no
sí
un enlace
dos enlaces
P-1
P/2
P/3 (P grande)
[ (P+1) / 3 ]
P/4 (P grande)
[ P2 / 4(P-1) ]
Topologías más utilizadas
3 Mallas y toros (n dimensiones, k>2 nodos por dim.)
k? P = kn
Enlaces:
Grado:
Simetría:
Toler. Fallos:
Escalabilidad:
n kn-1 (k-1)
n kn
2n
2n, regular
no
sí
alta (n)
más alta (2n)
fácil
fácil
Topologías más utilizadas
3 Mallas y toros (n dimensiones, k>2 nodos por dim.)
Bisección:
Diámetro:
Distancia media:
kn-1
2 kn-1
n (k-1)
n k/2
~ n k/3 (k grande)
~ n k/4 (k grande)
Topologías más utilizadas
4 Hipercubo: caso paticular de una malla de n dimensiones, con sólo dos nodos por dimensión.
(Gp:) (xn-1, xn-2, …, x1, x0) ?
(xn-1, xn-2, …, x1, x0)
(xn-1, xn-2, …, x1, x0)
…
(xn-1, xn-2, …, x1, x0)
(xn-1, xn-2, …, x1, x0)
(Gp:) 0000
(Gp:) 0001
(Gp:) 0100
(Gp:) 1000
(Gp:) 0010
(Gp:) 1111
(Gp:) 0101
(Gp:) 0110
(Gp:) 1100
Enlaces con los nodos cuya dirección se diferencia en un bit.
Topologías más utilizadas
4 Hipercubo: parámetros topológicos
(Gp:) 0000
(Gp:) 0001
(Gp:) 0100
(Gp:) 1000
(Gp:) 0010
(Gp:) 1111
(Gp:) 0101
(Gp:) 0110
(Gp:) 1100
Diámetro:
Dist. med.:
Grado:
Simetría:
T. Fallos: Escal.:
Bisección:
Nodos:
Enlaces:
P = 2n ? n = log2 P
P/2 log2 P
n (log2P, no es constante!)
sí
muy grande
difícil
P/2 (muy grande)
n
~ n/2 (n grande)
Topologías más utilizadas
5 Árboles y árboles densos (fat tree)
(Gp:) fat tree árbol denso
(Gp:) encaminadores
(Gp:) procesadores
(Gp:) árbol binario (k = 2)
Topologías más utilizadas
5 Árboles y árboles densos (fat tree)
fat tree o árbol denso
Diámetro:
Dist. med.:
Grado:
Profund.:
Simetría:
T. Fallos: Escal.:
Bisección:
k (normalmente, 4)
sí
grande
fácil
P/2
2 logk P
~ 2 logk P – 2/(k-1)
(P grande)
logk P
Topologías más utilizadas
Resumen de topologías
? Por ejemplo, P = 4.096 nodos:
(Gp:) 126 42,7
64 32
(Gp:) 45 15,9
24 12
(Gp:) 12 6
12 11,3
(Gp:) D d(med)
2D malla
2D toro
3D malla
3D toro
Hipercubo
Árbol (k = 4)
Resumen de topologías
? El hipercubo tiene parámetros topológicos muy buenos, pero es complejo si el número de procesadores es grande; además, el grado no es constante. Fue la topología de los primeros sistemas MPP (pocos procesadores y la latencia de los mensajes dependiente de la distancia).
? Las mallas y toros 2D y 3D se utilizan mucho en sistemas MPP: son topologías simples con grado bajo. Los parámetros de distancia son mayores, pero cambió la técnica de transmisión de mensajes y la latencia no depende tanto de la distancia.
? Se utilizan también árboles (o similares tipo butterfly, para formar cluster-s, Myrinet), aunque son complejos cuando el número de procesadores es muy grande.
Resumen de topologías
? La red se utiliza para la comunicación entre procesos, permitiendo el envío de mensajes de proceso a proceso.
¿Cómo se envían esos mensajes? ¿Por dónde? ¿Cómo se escoge el camino?…
? Estructura de los mensajes (paquetes)
(Gp:) cabecera
(Gp:) datos
(Gp:) cola
(Gp:) Inf. control
Unidad de información (de flujo): un flit (en general, un byte). Tiempo para transmitir un flit, un “ciclo”.
Comunicación
? Patrones de comunicación
Especifican cuándo y con quién se efectúa la comunicación. Evidentemente, depende de la aplicación.
? Tamaño de los mensajes
En general, hay que transportar mensajes de diversos tamaños.
Los mensajes de control suelen ser pequeños (unos bytes); los de datos, mayores (normalmente divididos en paquetes de tamaño fijo).
Patrones de comunicación
? Algunos patrones de comunicación habituales:
– Aleatorio: la probabilidad de comunicación entre dos nodos es la misma para cualquier par de nodos y uniformemente distribuida en el tiempo.
– Esferas de localidad: hay mayor probabilidad de comunicación con unos nodos que con otros, dependiendo de la distancia (cercanos).
(Gp:) dist.
(Gp:) P. Com.
– Broadcast, multicast, reporting…
– Matriz transpuesta, FFT, perfect shuffle…
Patrones de comunicación
? Construcción del camino
– Conmutación de circuitos (circuit switching)
Antes de enviar el mensaje hay que reservar un camino “privado”, para lo que se envía un mensaje “sonda” hasta el destino.
Tras construir el camino, se transmite todo el mensaje (no se divide en paquetes).
Por ejemplo: red telefónica.
Problemas: hace falta tiempo para generar el camino; y se reservan enlaces de la red, aunque no estén siendo utilizados constantemente.
Construcción del camino
? Construcción del camino
– Conmutación de paquetes (packet switching)
El mensaje se divide en varios paquetes de tamaño fijo. Cada paquete tiene información sobre el destino y va hasta el mismo, encaminador tras encaminador, compitiendo con el resto de los paquetes para la utilización de recursos.
Por ejemplo: servicio de correos.
Problemas: se genera una sobrecarga, porque cada paquete tiene que llevar información de control. Addemás, hay que reconstruir el mensaje en el destino.
Construcción del camino
? Encaminamiento de paquetes (routing)
¿Por dónde van los paquetes desde el origen al destino? ¿Cuál es el camino?
– ¿Cómo indicar el camino a tomar?
registro de encaminamiento, RE (routing record)
– ¿Hay un sólo camino?
caminos de longitud mínima, pero, ¿cuál?
Encaminam. de paquetes
? Encaminamiento de paquetes (routing).
Dos opciones para llegar al destino:
– Indicar en el paquete la dirección absoluta.
La información se procesa en los encaminadores intermedios para escoger la salida (tabla, función…).
– El paquete lleva el registro de encamina-miento que especifica el camino; normalmente, cuántos pasos dar en cada dimensión.
El RE se actualiza en cada encaminador. Se ha llegado al destino cuando todos los componentes del RE son 0.
Encaminam. de paquetes
? Registro de encaminamiento en una malla
X: (xn-1, xn-2, …, x1, x0) ? Y (yn-1, yn-2, …, y1, y0)
Basta con hacer la resta de coordenadas para indicar el número de pasos a dar en cada dimensión.
RE = [yn-1 – xn-1, yn-2 – xn-2, …, y0 – x0]
4 (1,0) ? 15 (3,3) ? RE = [2, 3]
(Gp:) 4 (1,0)
(Gp:) 15 (3,3)
(Gp:) [2,3]
(Gp:) [2,2]
(Gp:) [2,1]
(Gp:) [2,0]
(Gp:) [1,0]
(Gp:) [0,0]
Registro de encaminamiento
? Registro de encaminamiento en un toro
Tras restar las coordenadas, hay que analizar el resultado para escoger el camino más corto en cada anillo:
REi > k/2 ? REi = REi – k
REi < -k/2 ? REi = REi + k
4 (1,0) ? 15 (3,3) RE = [2, 3] ? [2, -1]
(Gp:) 4 (1,0)
(Gp:) 15 (3,3)
En cada dimensión hay dos opciones para ir al destino: hacia “adelante” o hacia “atrás”.
Nunca se recorre más de medio anillo en cada dimensión.
(Gp:) [2,-1]
(Gp:) [2,0]
(Gp:) [1,0]
(Gp:) [0,0]
Registro de encaminamiento
? Registro de encaminamiento en un hipercubo
RE = [i xor j]
2 (0010) ? 12 (1100) RE = [1110]
No hay más que dos nodos en cada dimensión; por lo tanto, sólo se puede dar un paso por dimensión, si las coordenadas de esa dimensión son distintas:
(Gp:) 1001
(Gp:) 1110
(Gp:) 0000
(Gp:) 0001
(Gp:) 0100
(Gp:) 1000
(Gp:) 0010
(Gp:) 1111
(Gp:) 0101
(Gp:) 0110
(Gp:) 1100
(Gp:) 0011
(Gp:) 0111
(Gp:) 1101
(Gp:) [1110]
(Gp:) [1100]
(Gp:) [1000]
(Gp:) [0000]
1010
1011
Registro de encaminamiento
? Estrategias para escoger un camino concreto
El registro de encaminamiento no indica un único camino (en general). ¿Cuál hay que utilizar?
1. Encaminamiento estático
Se utiliza un único camino para ir de X a Y, y siempre el mismo: DOR.
(Gp:) 4 (1,0)
(Gp:) 15 (3,3)
+ Es simple
+ Los paquetes llegan ordenados
– No se aprovechan todas las opciones para seguir adelante
Elección del camino
2. Encaminamiento dinámico
En cada encaminador se escoge el camino en función del estado del sistema (ojo! hay que utilizar información local).
(Gp:) 4 (1,0)
(Gp:) 15 (3,3)
+ Se pueden evitar zonas de mucho tráfico (aprovechando la topología de la red)
– Es más complejo (hay que decidir)
– Los paquetes pueden llegar desordenados
– Pueden ocurrir bloqueos
? Estrategias para escoger un camino concreto
Elección del camino
3. Encaminamiento no mínimo
Hay que utilizar en general caminos de longitud mínima.
En algunos casos puede ser adecuado utilizar caminos más largos para evitar tráfico o superar averías.
? Estrategias para escoger un camino concreto
Elección del camino
? Un paquete contiene L flits (algunos para control y otros para datos).
¿Cómo se transmiten los flits de los paquetes entre encaminadores? ¿Qué hay que hacer con los flits de un paquete que se está transmitiendo?
Dos opciones:
– Store-and-forward
habitual en redes de ordenadores
– Cut-through / Wormhole
la que se utiliza en multicomputadores
Control del flujo
? Store-and-forward
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) Encaminadores intermed.
(Gp:) t
Se transmite el paquete completo (todos los flits) entre encaminadores contiguos.
Durante la transmisión se almacena en un búfer interno.
Tsf ~ L × d
Control del flujo: SF
? Cut-through / Wormhole
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 1
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) Encaminadores intermed.
Tras procesar el primer flit de la cabecera de un paquete, se transmite al siguiente encaminador, sin esperar a la llegada del resto.
Tct/wh ~ L + d
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
La transmision del paquete se “segmenta”.
Control del flujo: CT / WH
? Cut-through / Wormhole
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 4
(Gp:) 2
(Gp:) 3
(Gp:) 1
Diferencia: ¿qué hacer si el flit de cabecera de un paquete no puede continuar?
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
Wormhole
Todos los flits del paquete se paran donde están.
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
No hay que utilizar búferes.
Control del flujo: CT / WH
? Cut-through / Wormhole
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
Cut-through
El primer flit se para, pero el resto continúa y los flits se almacenan en los encaminadores, en búferes.
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
Diferencia: ¿qué hacer si el flit de cabecera de un paquete no puede continuar?
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 2
(Gp:) 4
(Gp:) 3
(Gp:) 1
(Gp:) 2
Control del flujo: CT / WH
? Búferes para paquetes
Los encaminadores de mensajes suelen tener espacio para almacenar paquetes (algunos flits).
SF ? búfer para por lo menos un paquete.
WH ? espacio de memoria para un flit (puerto de entrada).
CT ? solución intermedia; hace falta capacidad para almacenar un paquete o algunos flits.
¿Espacio para muchos paquetes? No
– no tiene que haber muchos paquetes bloqueados.
– el encaminador tiene que ser rápido, es decir, simple.
Conflictos: búferes
? ¿Cómo se estructuran los búferes?
¿Compartidos, o distribuidos?
Compartidos
+ se gestiona mejor el espacio de memoria
– son más complejos, tienen que aceptar varias entradas y salidas
Conflictos: búferes
¿En las entradas o en las salidas?
Salidas
+ los paquetes no se tratan en orden (mejor rendimiento)
– más difíciles de gestionar (entradas múltiples)
? ¿Cómo se estructuran los búferes?
Conflictos: búferes
¿Y si se llenan los búferes?
No debe ser una situación habitual, ya que significa que se ha superado la capacidad de comunicación de la red. Sólo para gestionar momentos de mucho tráfico.
(Gp:) ¿sitio?
(Gp:) sí / no
(Gp:) datos
? ¿Cómo se estructuran los búferes?
Conflictos: búferes
(Gp:) líneas de control
(Gp:) líneas de datos
? La red de comunicación no es más que un recurso para ejecutar programas en paralelo (otra “unidad funcional”), que tiene que ser lo más eficiente posible.
Principales parámetros de calidad:
– Latencia de los paquetes: tiempo necesario para realizar la comunicación.
– Throughput: el nivel de tráfico que puede aceptar / gestionar la red.
Latencia y Throughput
? Algunas definiciones
– Anchura de los enlaces (phit): número de bits que se puede transmitir en paralelo (por ejemplo, 8 bits).
– Ciclo de transmisión: tiempo necesario para transmitir un phit (un ciclo).
– Ancho de banda (bandwidth) de los enlaces, B: cantidad de información transmitible en un segundo.
– Tiempo de encaminamiento (routing time), tr: tiempo para procesar la cabecera de un paquete.
Latencia y Throughput
? Tiempo de comunicación o latencia (sin tráfico)
L: longitud del paquete (en bytes = flits)
d: distancia
– Store-and-forward
Tsf = d × (L/B + tr)
– Cut-through / Wormhole
Tct = d × (1/B + tr) + (L-1)/B
(Gp:) d × L
(Gp:) d + L
Latencia y Throughput
? Ejemplo: P = 1.024, L = 256 bytes, tr = 1 ciclo
(Gp:) hipercubo toro 2D malla 2D
(Gp:) D 10 32 62
d 5 16 22
(Gp:) máx. 2.570 8.224 15.934
med. 1.285 4.112 5.654
(Gp:)
SF
(Gp:) máx. 275 319 379
med. 265 287 299
(Gp:)
CT
Latencia y Throughput
? Teniendo en cuenta el tráfico de la red
(Gp:) Throughput (b/s)
(Gp:) Tráfico (b/s)
(Gp:) Tráfico (b/s)
(Gp:) Latencia (s)
(Gp:) Latencia
a tráfico 0
(Gp:) Tráfico máximo
Latencia y Throughput
? Cut-through versus wormhole
(Gp:) Tráfico (b/s)
(Gp:) Latencia (s)
(Gp:) CT
(Gp:) Throughput (b/s)
(Gp:) Tráfico (b/s)
(Gp:) CT
(Gp:) WH
(Gp:) WH
Latencia y Throughput
? Throughput máximo (tráfico aleatorio)
(Gp:) P/2
(Gp:) P/2
(Gp:) Enlaces de la bisección
P/2 × (NPaq × L) × 1/2 = ABB
NPaq = 4 × ABB / (P × L)
NPaq: número de paquetes de L flits (bytes) que puede inyectar por segundo cada procesador
ABB: ancho de banda de la bisección
(= Bisec × B)
(Gp:) malla 2D toro 2D hiperc. 8D
(Gp:)
(Gp:) bisección
n. max. flit / c.
(Gp:) P = 256
16 32 128
0,25 0,5 2
Latencia y Throughput
(Gp:) NPaq/2
(Gp:) NPaq/2
? Modelo general
Tcom = tini + tflit × L
R = L / Tcom velocidad de transmisión
Rmax = lim R (L?8) velocidad máxima
L1/2 = tini / tflit para obtener la mitad de la veloc. máxima
? Resumen: componentes del tiempo de comunicación
(Gp:) Comunicación entre encaminadores
(Gp:) Proc. paq.
(Gp:) T. espera en búferes
(Gp:) Emisor
(Gp:) Receptor
Latencia y Throughput
? El proceso de comunicación es distribuido, y se ejecuta en paralelo en varios encaminadores de mensajes. Por lo tanto, puede aparecer un problema que ya hemos analizado: el bloqueo (deadlock) (livelock, starvation…).
? Bloqueos: un conjunto de paquetes agota los recursos para seguir adelante (en modo CT, los búferes; en modo WH, los enlaces…), y se queda parado para siempre.
Problemas de la comunic.
m2: 1,3?3,1
(0,0)
(0,3)
(3,0)
(3,3)
m1: 0,1?2,3
m3: 3,2?1,1
m4: 2,1?0,2
? Por ejemplo, en modo WH:
Problemas de la comunic.
? ¿Qué hacer con los bloqueos?
– Utilizar únicamente topologías o estrategias de encaminamiento que no generen bloqueos.
– Aceptar que pueden generarse bloqueos, y, cuando se generan, detectarlos y solucionarlos.
Las opciones más utilizadas son:
Bloqueos: estrategias
(Gp:) m2: 1,3?3,1
(Gp:) (0,0)
(Gp:) (0,3)
(Gp:) (3,0)
(Gp:) (3,3)
(Gp:) m1: 0,1?2,3
(Gp:) m3: 3,2?1,1
(Gp:) m4: 2,1?0,2
1. El encaminamiento estático ayuda
Por ejemplo, si utilizamos el encaminamiento estático DOR, no se generan bloqueos en las mallas.
Bloqueos: estrategias
2. Pero no es suficiente si la propia topología tiene ciclos.
(Gp:)
0
(Gp:)
3
(Gp:)
1
(Gp:)
2
(Gp:) 0?2
(Gp:) 1?3
(Gp:) 2?0
(Gp:) 3?1
Bloqueos: estrategias
(Gp:) B0
(Gp:) B1
(Gp:) B1
(Gp:) B0
3. Canales virtuales
Para no mantener bloqueados los enlaces de los encaminadores, los búferes se dividen en dos (o más) clases.
(Gp:) CV0
(Gp:) CV1
Bloqueos: estrategias
3. Canales virtuales
Doble objetivo:
1 Mejorar la eficiencia: si un paquete no puede seguir, no parar un paquete que viene por detrás y que tiene el camino libre.
2 Evitar las situaciones de deadlock.
Bloqueos: estrategias
3. Canales virtuales
2 Evitar situaciones de deadlock
(Gp:)
0
(Gp:)
3
(Gp:)
1
(Gp:)
2
(Gp:) 1?3
(Gp:) 2?0
(Gp:) 3?1
(Gp:) 0?2
Bloqueos: estrategias
(Gp:) CV1
(Gp:) CV0
? En resumen
Mallas, DOR ? no hay bloqueo
Toros, DOR, 2 canales virtuales ? no hay bloqueo
4. Pero, ¿se puede utilizar el encaminamiento dinámico sin bloqueos?
– mallas virtuales
– giros controlados (turn model)
– caminos seguros
– controlar la inyección de paquetes
Problemas de la comunic.
4a. Mallas virtuales (2D)
– Añadir dos canales virtuales por cada canal físico.
– Clasificar los paquetes en cuatro categorías, en función de las posiciones de los destinos: NE, ES, SW, WN.
– En cada malla virtual los paquetes pueden tomar cualquier camino, ya que no se pueden formar ciclos.
(Gp:) N1
(Gp:) E0
(Gp:) W1
(Gp:) N0
(Gp:) E1
(Gp:) S0
(Gp:) S1
(Gp:) W0
– Generar cuatro mallas virtuales:
NE: N1-E0 ES: E1-S0
SW: S1-W0 WN: W1-N0
Problemas de la comunic.
4b. Turn model (mallas)
– Hay que hacer cuatro giros para formar un ciclo. Cuando se utiliza encaminamiento estático (DOR) dos de ellos están prohibidos.
(Gp:) ?
(Gp:) ?
– Basta con prohibir uno para que no se generen ciclos; p.e, prohibido girar al oeste:
(Gp:) ?
– si no van hacia el oeste, como quieran;
– si no, recorrer inicialmente el camino hacia el oeste.
west-first
Problemas de la comunic.
4c. Caminos seguros (red segura + no segura)
En este caso se acepta que los paquetes se puedan bloquear. Cuando ocurre, se detecta y se soluciona el problema. Por ejemplo, en mallas y los toros:
– 2 canales virtuales (2D), para generar dos redes virtuales.
– Los paquetes se inyectan en una red y se mueven libremente. La otra red se utiliza para moverse en modo seguro (por ejemplo DOR, en una malla 2D).
– Si un paquete se bloquea, se le hace pasar a la red segura, en la que avanzará hasta llegar al destino.
Problemas de la comunic.
4c. Caminos seguros
Ojo: ¿cómo detectar el bloqueo?
Por ejemplo, tras pasar cierto tiempo sin movimiento.
4d. Controlar la inyección de paquetes
Ocurren bloqueos porque se acaban los recursos.
Por lo tanto, los encaminadores rechazarán un paquete si en caso de que lo acepten se llenan los búferes. De esta manera, los recursos no se terminarán nunca (Mare Nostrum).
Problemas de la comunic.
? Ojo: el encaminador tiene que ser simple, para procesar paquetes lo más rápido posible. Por lo tanto, puede que el encaminamiento estático sea suficiente!
? En resumen
– Mallas, DOR ? no hay bloqueo
– Toros, DOR, 2 canales virtuales ? no hay bloqueo
Encaminamiento dinámico:
– En general, 1 canal virtual por dimensión en una malla, y 2 en un toro.
– Otras estrategias.
– Tal vez, topologías que no generan ciclos: árboles!
Problemas de la comunic.
? Otros problemas
Livelock
Los paquetes van adelante y atrás, pero no consiguen llegar al destino.
Pueden aparecer problemas si se desvían paquetes de los caminos mínimos “para no perder tiempo”.
La causa puede estar relacionada con las prioridades.
Starvation
Algunos procesadores no consiguen inyectar sus paquetes en la red porque hay mucho tráfico alrededor.
Problemas de la comunic.
? Recuerda que en el proceso de comunicación toman parte muchos elementos.
(Gp:) red + encaminadores
(Gp:) interfaz + procesador (+SO?)
(Gp:) P1
(Gp:) P2
El proceso más lento de la comunicación acotará la velocidad de comunicación del sistema.
Protocolos de comunicación
? Hemos tenido en cuenta únicamente la transmisión de paquetes. Pero el interfaz “procesador/red” es también muy importante: ¿cómo se inyectan los paquetes en la red? ¿cómo salen?
Hay varios protocolos de comunicación para regular esos procesos:
– El más simple, TCP/IP
– Más eficientes: protocolos de 0 copias
estandares: VIA, Infiniband…
propietario: gm (myrinet)…
Protocolos de comunicación
(Gp:) memoria usuario
(Gp:) memoria usuario
(Gp:) Implementación habitual:
1. TCP / IP
reliable / connection oriented
Protocolo de los primeros clusters (y los de bajo rendimiento).
c. mem. sistema
c. mem. sistema
(Gp:) Int. SO
(Gp:) Int SO
Protocolos de comunicación
Ojo: la sobrecarga debida al sistema operativo y a las copias puede ser muy grande.
sobrecarga del protocolo
tiempo de transmisión
(Gp:) 10 Mb/s
(Gp:) 100 Mb/s
(Gp:) 1 Gb/s
Protocolos de comunicación
2. VIA (virtual interface architecture)
Estándar de comunicación de los principales fabricantes.
No se hacen copias en la memoria del sistema operativo; se trabaja directamente con los encaminadores:
— antes de enviar un mensaje se reserva sitio en la memoria física, en el emisor y en el receptor.
— las operaciones send/receive envían un descriptor a una cola para procesar paquetes.
— podemos esperar a la confirmación, o seguir trabajando.
Son protocolos de bajo nivel, con implementaciones nativas o emuladas.
Protocolos de comunicación
3. InfiniBand (IBA)
Objetivo: infraestructura de comunicaciones de altas prestaciones, basada en conmutadores (intra) y encaminadores (inter), para componer redes SAN (reemplazar el bus compartido).
– Se utilizan adaptadores especiales para conectar nodos: HCA (nodos de computación) o TCA (nodos auxiliares).
– Para conectar nodos de redes locales se utilizan conmutadores y para conectar redes locales entre ellas se utilizan encaminadores.
– Los enlaces son de 2,5 Gb/s de un solo sentido, punto a punto.
Infiniband
4. Myrinet
Infraestructura de comunicación de alto rendimiento (caro).
Enlaces de 10 Gbit/s (full duplex), fibra óptica. Conmutadores en un crossbar (red Clos). Cut-through.
Software propio para gestión de mensajes (GM).
Implementaciones de Gbit ethernet / Via / Infiniband.
Latencias de paquetes pequeños: 1,2 µs (Gigabit, 50 µs)
Throughput máximo 9,6 Gbit/s
Myrinet
Myrinet
Myrinet
Myrinet