arquitecturas paralelas if - ehu arquitecturas paralelas 6. la red de comunicación de los...
Post on 28-Jan-2016
246 Views
Preview:
TRANSCRIPT
Arquitecturas Paralelas IF - EHU
Arquitecturas Paralelas
6. La red de comunicación de los computadores paralelos. Comunicación mediante paso de mensajes.
- Introducción
- Redes basadas en conmutadores- Redes basadas en encaminadores- Estrategias de comunicación- Conflictos en la comunicación
Arquitecturas ParalelasIF - EHU
2RC-PM
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
Arquitecturas ParalelasIF - EHU
3RC-PM
Los multiprocesadores SMP suelen utilizar un bus para acceder a memoria.
M
P
C
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
Arquitecturas ParalelasIF - EHU
4RC-PM
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.
P
C
M
red general
R
Introducción
Arquitecturas ParalelasIF - EHU
5RC-PM
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
Arquitecturas ParalelasIF - EHU
6RC-PM
La infraestructura de comunicación tiene dos partes:
- el hardwareconexiones, conmutadores, encaminadores de mensajes, interfaces con los procesadores.
- el softwareprotocolos de comunicación.
Introducción
Arquitecturas ParalelasIF - EHU
7RC-PM
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
Arquitecturas ParalelasIF - EHU
8RC-PM
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
Arquitecturas ParalelasIF - EHU
9RC-PM
Tráfico- Bisección: conexiones que hay que eliminar para dividir el grafo en dos partes iguales.
Distancias (latencia)- Distancia media: d = Σ dij / P(P-1)
- Diámetro: distancia máxima entre dos nodos.
Características topológicas principales:
Introducción: topología
Arquitecturas ParalelasIF - EHU
10RC-PM
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
Arquitecturas ParalelasIF - EHU
11RC-PM
Conmutador: dispositivo que conecta varias entradas y salidas.
E0 → S0, S1
E1 → S0, S1
E0 → S0E1 → S1
E0 → S1E1 → S0
grado k=2
0
1
0
1
E0E1
S0
señales de señales de controlcontrol
S1
Redes con conmutadores
Arquitecturas ParalelasIF - EHU
12RC-PM
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
Arquitecturas ParalelasIF - EHU
13RC-PM
2. Redes multietapa
Los conmutadores se organizan en varias etapas, y las conexiones entre distintas etapas se hacen por medio de una “permutación”.
proc.
P0
Pp-1
proc.(o mem.)
P0
Pp-1
una permutación
Redes con conmutadores
Arquitecturas ParalelasIF - EHU
14RC-PM
Ejemplo: red Omega
0
1
2
3
5
6
7
4
Conexiones entre conmutadores: barajado perfecto (perfect shuffle).
0
2
4
6
1
3
5
7
0
2
6
1
3
5
7
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
Arquitecturas ParalelasIF - EHU
15RC-PM
Red Omega
0
2
4
6
1
3
5
7
0
2
6
1
3
5
7
4
Diámetro: logk P
Distancia med.: logk P
Simétrica (regular)Grado: 2, 4... (k)Tolerancia a fallos: baja
Redes Omega
Arquitecturas ParalelasIF - EHU
16RC-PM
Encaminamiento en la red Omega (routing)¿Cómo se escoge el camino para ir de i a j? 1 Bits de la dirección
destino0: salida 0 / 1: salida 1
→ 6 (110)
0
2
4
6
1
3
5
7
0
2
6
1
3
5
7
4
10
10
2 Registro de encaminamiento: i xor j0: seguir / 1: cruzar
RE = 100 xor 110 = 010
1
0
Redes Omega
Arquitecturas ParalelasIF - EHU
17RC-PM
Conflictos de salidaLa red Omega admite P comunicaciones simultáneas, pero no cualesquiera (red bloqueante).
0 → 1 y 6 → 0?0
2
4
6
1
3
5
7
0
2
6
1
3
5
7
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
Arquitecturas ParalelasIF - EHU
18RC-PM
0
2
4
6
1
3
5
7
0
2
6
1
3
5
7
4
BroadcastDe uno a todos los procesadores
BC
BC
BC
BC
BC
BC
BC
Redes Omega
Arquitecturas ParalelasIF - EHU
19RC-PM Red Butterfly
Otro ejemplo: red Butterfly
Arquitecturas ParalelasIF - EHU
20RC-PM
bus Omega Crossbar
Latencia constante O(logkP) constante
Ancho de banda por procesador
O(w/P)→O(w) O(w)→O(w × P) O(w × P)
Complejidad de cableado
O(w) O(w × P × logkP) O(w × P2)
Complejidad de conmutación
O(P) O(P/k × logkP) O(P2)
Capacidad de comunicación
de uno en unoalgunas
permutaciones broadcast
todas las permutaciones
Resumen
Arquitecturas ParalelasIF - EHU
21RC-PM
La red se forma mediante encaminadores de mensajes (routers).
red de comunicación
procesador/memoria local
router
Gestor de comunicacione
s
conexiones de red
Nodo de una red estática: proc./mem. + encaminador. La distancia entre nodos no es constante.
Redes con encaminadores
Enlaces bidireccionales.
Arquitecturas ParalelasIF - EHU
22RC-PM
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.
puertos de entrada puertos de salida
procesador localprocesador local
enlaces decomunicación
enlaces decomunicación
búfe
res
búfe
res
fun
c.
en
cam
.+
cro
ssb
ar
Encaminador de mensajes
Arquitecturas ParalelasIF - EHU
23RC-PM
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
Arquitecturas ParalelasIF - EHU
24RC-PM
2 Redes de una dimensión: cadena y anillo.
Grado:Simetría:
Toler. Fallos:
Diámetro: Distancia media:
2 2, regularno síun enlace dos enlaces
P-1 P/2P/3 (P grande)
[ (P+1) / 3 ]
P/4 (P grande)
[ P2 / 4(P-1) ]
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
25RC-PM
3 Mallas y toros (n dimensiones, k>2 nodos por dim.)
k→ P = kn
Enlaces:Grado:
Simetría:Toler. Fallos: Escalabilida
d:
n kn-1 (k-1) n kn
2n 2n, regularno síalta (n) más alta (2n)fácil fácil
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
26RC-PM
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
Arquitecturas ParalelasIF - EHU
27RC-PM
4 Hipercubo: caso paticular de una malla de n dimensiones, con sólo dos nodos por dimensión.
(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)
0000 0001 0100
1000
0010
1111
0101
0110
1100
Enlaces con los nodos cuya dirección se diferencia en un bit.
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
28RC-PM
4 Hipercubo: parámetros topológicos
0000 0001 0100
1000
0010
1111
0101
0110
1100
Diámetro: Dist. med.:
Grado:Simetría:T. Fallos: Escal.:Bisección:
Nodos: Enlaces:
P = 2n → n = log2 PP/2 log2 P
n (log2P, no es constante!)símuy grandedifícilP/2 (muy grande)
n~ n/2 (n grande)
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
29RC-PM
5 Árboles y árboles densos (fat tree)
fat tree árbol denso
encaminadores
procesadores
árbol binario (k = 2)
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
30RC-PM
5 Árboles y árboles densos (fat tree)
fat tree o árbol densoDiámetro: Dist. med.:
Grado:Profund.:Simetría:T. Fallos: Escal.:Bisección:
k (normalmente, 4)sígrandefácilP/2
2 logk P~ 2 logk P – 2/(k-1)(P grande)
logk P
Topologías más utilizadas
Arquitecturas ParalelasIF - EHU
31RC-PM
parámetros topológicos (P par, grande)
Proc. Grado Simetr. Enlaces d (med) Dmax Bisec.Arco-con.
Crossbar P P-1 si P (P-1) 1 1 P2/4 P-1
Omega[conm.] P k si
P(logkP+1)[P/k logkP]
logkP logkP - -
Malla (n / k>2)
P = kn 2n no n kn-1 (k-1) ~ n k/3 n (k-1) kn-1 n
Toro P = kn 2n si nP ~ n k/4 n k/2 2 kn-1 2n
Hipercubo P = 2n n(log P)
si P/2 logP ~ n/2 n P/2 n
Árbol(fat tree)
P k si P (logkP)~ 2 logkP
-2/(k-1)
2 logkP P/2 1
Resumen de topologías
Arquitecturas ParalelasIF - EHU
32RC-PM
Por ejemplo, P = 4.096 nodos:
126 42,764 32
45 15,924 12
12 6
12 11,3
D d(med)
2D malla2D toro
3D malla3D toro
Hipercubo
Árbol (k = 4)
Resumen de topologías
Arquitecturas ParalelasIF - EHU
33RC-PM
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
Arquitecturas ParalelasIF - EHU
34RC-PM
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)
cabeceradatoscola
Inf. control
Unidad de información (de flujo): un flit (en general, un byte). Tiempo para transmitir un flit, un “ciclo”.
Comunicación
Arquitecturas ParalelasIF - EHU
35RC-PM
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
Arquitecturas ParalelasIF - EHU
36RC-PM
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).
dist.
P. Com.
- Broadcast, multicast, reporting...
- Matriz transpuesta, FFT, perfect shuffle...
Patrones de comunicación
Arquitecturas ParalelasIF - EHU
37RC-PM
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
Arquitecturas ParalelasIF - EHU
38RC-PM
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
Arquitecturas ParalelasIF - EHU
39RC-PM
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
Arquitecturas ParalelasIF - EHU
40RC-PM
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
Arquitecturas ParalelasIF - EHU
41RC-PM
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]
4 (1,0)
15 (3,3)
[2,3] [2,2] [2,1] [2,0]
[1,0]
[0,0]
Registro de encaminamiento
Arquitecturas ParalelasIF - EHU
42RC-PM
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 + k4 (1,0) → 15 (3,3) RE = [2, 3] → [2, -
1]
4 (1,0)
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.
[2,-1] [2,0]
[1,0]
[0,0]
Registro de encaminamiento
Arquitecturas ParalelasIF - EHU
43RC-PM
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:
1001
1110
0000 0001 0100
1000
0010
1111
0101
0110
1100
0011 0111
1101
[1110]
[1100]
[1000]
[0000]
1010 1011
Registro de encaminamiento
Arquitecturas ParalelasIF - EHU
44RC-PM
Estrategias para escoger un camino concretoEl registro de encaminamiento no indica un único camino (en general). ¿Cuál hay que utilizar? 1. Encaminamiento estáticoSe utiliza un único camino para ir de X a Y, y siempre el mismo: DOR.
4 (1,0)
15 (3,3)
+ Es simple+ Los paquetes llegan
ordenados - No se aprovechan todas las
opciones para seguir adelante
Elección del camino
Arquitecturas ParalelasIF - EHU
45RC-PM
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).
4 (1,0)
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
Arquitecturas ParalelasIF - EHU
46RC-PM
3. Encaminamiento no mínimoHay 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
Arquitecturas ParalelasIF - EHU
47RC-PM
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-forwardhabitual en redes de ordenadores
- Cut-through / Wormholela que se utiliza en
multicomputadores
Control del flujo
Arquitecturas ParalelasIF - EHU
48RC-PM
Store-and-forward
1234
234 1
34 12
4 123
1234
234 1
34 12
4 123
1234
234 1
34 12
4 123
1234
Encaminadores intermed.
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
Arquitecturas ParalelasIF - EHU
49RC-PM
Cut-through / Wormhole
1234
234 1
4 23 1
1234
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
124 3
4 123
34 12
La transmision del paquete se “segmenta”.
Control del flujo: CT / WH
Arquitecturas ParalelasIF - EHU
50RC-PM
Cut-through / Wormhole
1234
4 23 1
Diferencia: ¿qué hacer si el flit de cabecera de un paquete no puede continuar?
124 3
4 123
Wormhole
Todos los flits del paquete se paran donde están.
34 12
234 1
1234
34 12
34 12
No hay que utilizar búferes.
Control del flujo: CT / WH
Arquitecturas ParalelasIF - EHU
51RC-PM
Cut-through / Wormhole
1234
4 123
Cut-through
El primer flit se para, pero el resto continúa y los flits se almacenan en los encaminadores, en búferes.
4 123
1234
1234
Diferencia: ¿qué hacer si el flit de cabecera de un paquete no puede continuar?
234 1
1234
34 12
4 3 12
Control del flujo: CT / WH
Arquitecturas ParalelasIF - EHU
52RC-PM
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
Arquitecturas ParalelasIF - EHU
53RC-PM
¿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
Arquitecturas ParalelasIF - EHU
54RC-PM
¿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
Arquitecturas ParalelasIF - EHU
55RC-PM
¿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.
¿sitio?
sí / no
datos
¿Cómo se estructuran los búferes?
Conflictos: búferes
líneas de control
líneas de datos
Arquitecturas ParalelasIF - EHU
56RC-PM
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
Arquitecturas ParalelasIF - EHU
57RC-PM
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
Arquitecturas ParalelasIF - EHU
58RC-PM
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
d × L
d + L
Latencia y Throughput
Arquitecturas ParalelasIF - EHU
59RC-PM
Ejemplo: P = 1.024, L = 256 bytes, tr = 1 ciclo
hipercubo toro 2D malla
2D D 10 32 62 d 5 16 22
máx. 2.570 8.224 15.934 med. 1.285 4.112 5.654
SF
máx. 275 319 379 med. 265 287 299CT
Latencia y Throughput
Arquitecturas ParalelasIF - EHU
60RC-PM
Teniendo en cuenta el tráfico de la red
Throughput (b/s)
Tráfico (b/s) Tráfico (b/s)
Latencia (s)
Latencia a tráfico 0
Tráfico máximo
Latencia y Throughput
Arquitecturas ParalelasIF - EHU
61RC-PM
Cut-through versus wormhole
Tráfico (b/s)
Latencia (s)
CT
Throughput (b/s)
Tráfico (b/s)
CT
WH
WH
Latencia y Throughput
Arquitecturas ParalelasIF - EHU
62RC-PM
Throughput máximo (tráfico aleatorio)
P/2 P/2
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)
malla 2D toro 2D hiperc. 8Dbisección
n. max. flit / c.
P = 256
16 32 1280,25 0,5 2
Latencia y Throughput
NPaq/2NPaq/2
Arquitecturas ParalelasIF - EHU
63RC-PM
Modelo general
Tcom = tini + tflit × L
R = L / Tcom velocidad de transmisión
Rmax = lim R (L→∞) velocidad máxima
L1/2 = tini / tflit para obtener la mitad de la veloc. máxima
Resumen: componentes del tiempo de comunicación
Comunicación entre
encaminadoresProc. paq. T. espera
en búferesEmisor
Receptor
Latencia y Throughput
Arquitecturas ParalelasIF - EHU
64RC-PM
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.
Arquitecturas ParalelasIF - EHU
65RC-PM
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.
Arquitecturas ParalelasIF - EHU
66RC-PM
¿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
Arquitecturas ParalelasIF - EHU
67RC-PM
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
1. El encaminamiento estático ayudaPor ejemplo, si utilizamos el encaminamiento estático DOR, no se generan bloqueos en las mallas.
Bloqueos: estrategias
Arquitecturas ParalelasIF - EHU
68RC-PM
2. Pero no es suficiente si la propia topología tiene ciclos.
0
3
1
2
0→2 1→3
2→03→1
Bloqueos: estrategias
Arquitecturas ParalelasIF - EHU
69RC-PM
B0
B1 B1
B0
3. Canales virtuales
Para no mantener bloqueados los enlaces de los encaminadores, los búferes se dividen en dos (o más) clases.
CV0
CV1
Bloqueos: estrategias
Arquitecturas ParalelasIF - EHU
70RC-PM
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
Arquitecturas ParalelasIF - EHU
71RC-PM
3. Canales virtuales
2 Evitar situaciones de deadlock
0
3
1
2
1→3
2→03→1
0→2
Bloqueos: estrategias
CV1
CV0
Arquitecturas ParalelasIF - EHU
72RC-PM
En resumenMallas, 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.
Arquitecturas ParalelasIF - EHU
73RC-PM
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.
N1
E0W1
N0
E1
S0S1
W0
- Generar cuatro mallas virtuales:
NE: N1-E0 ES: E1-S0
SW: S1-W0 WN: W1-N0
Problemas de la comunic.
Arquitecturas ParalelasIF - EHU
74RC-PM
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.
- Basta con prohibir uno para que no se generen ciclos; p.e, prohibido girar al oeste:
- si no van hacia el oeste, como quieran;
- si no, recorrer inicialmente el camino hacia el oeste.
west-first
Problemas de la comunic.
Arquitecturas ParalelasIF - EHU
75RC-PM
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.
Arquitecturas ParalelasIF - EHU
76RC-PM
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.
Arquitecturas ParalelasIF - EHU
77RC-PM
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.
Arquitecturas ParalelasIF - EHU
78RC-PM
Otros problemas
LivelockLos 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.
StarvationAlgunos procesadores no consiguen inyectar sus paquetes en la red porque hay mucho tráfico alrededor.
Problemas de la comunic.
Arquitecturas ParalelasIF - EHU
79RC-PM
Recuerda que en el proceso de comunicación toman parte muchos elementos.
red + encaminadores
interfaz + procesador (+SO?)
P1 P2
El proceso más lento de la comunicación acotará la velocidad de comunicación del sistema.
Protocolos de comunicación
Arquitecturas ParalelasIF - EHU
80RC-PM
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 copiasestandares: VIA, Infiniband...propietario: gm (myrinet)...
Protocolos de comunicación
Arquitecturas ParalelasIF - EHU
81RC-PM
memoria
usuario
memoria
usuario
Implementación habitual:
1. TCP / IPreliable / connection orientedProtocolo de los primeros clusters (y los de bajo rendimiento).
c. mem. sistema
c. mem. sistema
Int. SO Int SO
Protocolos de comunicación
Arquitecturas ParalelasIF - EHU
82RC-PM
Ojo: la sobrecarga debida al sistema operativo y a las copias puede ser muy grande.
sobrecarga del protocolotiempo de transmisión
10 Mb/s 100 Mb/s 1 Gb/s
Protocolos de comunicación
Arquitecturas ParalelasIF - EHU
83RC-PM
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
Arquitecturas ParalelasIF - EHU
84RC-PM
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
Arquitecturas ParalelasIF - EHU
85RC-PM
Arquitecturas ParalelasIF - EHU
86RC-PM
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
Arquitecturas ParalelasIF - EHU
87RC-PM Myrinet
Arquitecturas ParalelasIF - EHU
88RC-PM Myrinet
Arquitecturas ParalelasIF - EHU
89RC-PM Myrinet
any questions?please, d’ont forget exercices!
Arkitektura Paraleloak IF - EHU
RC-PM | Protocolos de comunicación
OJO: si se utilizan PCs para crear un cluster, la conexión entre la red y los nodos se hará mediante el bus PCI.¡Puede que sea ese bus el que limite la velocidad de la comunicación, y no los componentes de la red!
PCI → 32 bits / 33 MHz -- 64 bits / 66 MHz
110 - 480 MB/sPCI-X → 1 GB/s (2.0 → 4 GB/s)
PCI Express → 200 MB/s por canal (× 32 → 6,4 GB/s)
top related