1 Estrategias de Conmutación Conmutación de Circuito w Se establece un camino completo entre origen y destino, transfiriéndose a continuación los datos (libre de conflicto y con baja latencia), liberán- dose el camino finalmente. w Es adecuada cuando el tiempo de establecimiento del circuito es mucho menor que el tiempo de transmisión (mensajes largos) w Como todo el camino origen-destino está reservado, el ancho de banda se ve afectado negativamente, pero la latencia se minimiza. Conmutación de Paquetes w La información se agrupa en pequeños paquetes, que compiten indivi- dualmente por el acceso al camino entre origen y destino. w Los nodos/conmutadores deben incluir buffers para almacenar los pa- quetes en tránsito. w El ancho de banda es superior que en la conmutación de circuito, pero la latencia se ve afectada negativamente.

2 Conmutación de Paquetes Store-and-Forward w Cada paquete (o mensaje completo) contiene información completa so- bre su ruta (cabecera) y es transferido/almacenado en cada nodo inter- medio de su camino origen-destino. w Se necesitan buffers en cada nodo para almacenar paquetes (mensajes) completos. w Utilizado en las primeras generaciones de multicomputadores. Cut-Through w Cada paquete (mensaje) es descompuesto en flits (flow-control digits), con información de ruta (cabecera) sólo en el primero de ellos. w El primer flit establece el camino transitado de nodo a nodo, mientras que el resto de los flits siguen la misma ruta y en el mismo orden (seg- mentación de la transmisión). w Si una conexión bloquea el primer flit, el resto siguen el camino preesta- blecido, almacenándose todos ellos en el nodo bloqueado.

3 Conmutación de Paquetes Wormhole: w Variante del cut-through que minimiza el tamaño de los buffers en los nodos (sólo deben almacenar un único flit) w Cuando el flit de cabecera se bloquea, el resto de los flits perma- necen almacenados en los buffers de los nodos previos. w Este esquema puede dar lugar a interbloqueos (deadlock)

4 Comparación N1 N2 N3 N4 Time N1 N2 N3 N4 Time T SF L/W Data header packet D T WH L/W D a) Store-and-forward routingb) Wormhole routing Latencia: Store-and-Forward: t comm = t s + (mt w + t h ) l ≈ t s + mt w l Wormhole: t comm = t s + t h l + mt w ≈ t s + mt w m: tamaño del mensaje (palabras)l: longitud del camino t s : tiempo de confección del mensaje (startup)t h : tiempo de tránsito entre dos nodos t w : tiempo de tránsito por palabra y conexión vecinos

5 Interbloqueos (Deadlock) Interbloqueo circular D D D D D Packet Buffer C C C C C Packet Buffer A A A A A Packet Buffer B B B B B Packet Buffer Node C Node DNode A Node B (a) Buffer deadlock among four nodes with store-and-forward routing. Node A Node D Node B Node C Router A Message 4 Message 3 Router D Message 2 Router CMessage 1Flit buffer ( b) Channel deadlock among four nodes with wormhole routing; shaded boxes are flit buffers. m4 m3 m2 m1

6 Resolución:  Uso de canales virtuales (multiplexación en tiempo de las conexiones físicas, situando varios buffers en cada nodo)  Uso de técnicas adecuadas para establecer el encamina- miento de los mensajes (ej.: E-cube en hipercubos y enca- minamiento XY en mallas) Interbloqueos (Deadlock)

7 Redes de Conexión Dinámicas: Bloqueos Diferenciación entre canales físicos y virtuales: Physical Channel Flit buffers in source node Flit buffers in destination node Four virtual channels sharing a physical channel with time-multiplexing on a flit-by-flit basis Pueden existir varios canales virtuales por cada canal físico, con multiple- xación en el tiempo flit a flit.

8 Redes de Conexión Dinámicas: Bloqueos Los canales virtuales permiten resolver situaciones de bloqueo. AD BC AD BC (a) Channel deadlock(b) Channel-dependence graph containing a cycle (c) Adding two virtual channels (V 3, V 4 )(d) A modified channel-dependence graph using the virtual channels. Deadlock avoidance using virtual channels to convert a cycle to a spiral on a channel-dependence graph C4C4 C2C2 C3C3 C1C1 C4C4 C2C2 C3C3 C1C1 V3V3 V4V4 C2C2 C4C4 C3C3 C1C1 C2C2 V3V3 C3C3 C1C1 V4V4 C4C4

9 Encaminamiento de mensajes Estrategias de control de flujo: Resolución de una colisión entre paquetes Están presentes tres elementos en el envío de un mensaje (wormhole): 1) El nodo emisor contiene el flit a emitir en un buffer 2) El canal de conexión se aloca 3) El nodo receptor cuenta con un buffer donde aceptar el flit

10 Encaminamiento de mensajes Cuando dos paquetes llegan simultáneamente a un nodo hay que arbritar: 1) A qué paquete se le aloca el canal 2) Qué hacer con el paquete al que se le niega el acceso X Packet buffer Packet 1 flit buffer channel Outgoing Packet 2 (a) Buffering in virtual cut-through routing(b) Blocking flow control Gate Packet 2 Control Packet 1 Packet 2 Packet 1 (c) Discard and retransmission(d) Detour after being blocked Packet 2 Detour channel Packet 1 Outgoing channel Flow control methods for resolving a collision between two packets requesting the same outgoing channel (packet 1 being allocated the channel and packet 2 being denied)

11 Encaminamiento de mensajes Estrategias para la selección de las conexiones (caminos) para el Tránsito de los mensajes a través de la red. Tipos: Encaminamiento Determinístico: El camino depende solo del nodo origen y destino, y no de las condiciones de tráfico de la red. Encaminamiento Adaptivo: El camino depende de los nodos origen y destino y de las condiciones de la red.

12 Encaminamiento Determinístico XY en una Malla 2D 3,74,75,76,77,7 0,61,62,63,64,65,66,67,6 0,51,52,53,54,55,56,57,5 0,41,42,43,44,45,46,47,4 0,31,32,33,34,35,36,37,3 0,21,22,23,24,25,26,27,2 0,11,12,13,14,15,16,17,1 0,01,02,03,04,05,06,07,0 Encaminamiento dimensional libre de interbloqueos Four (Source; destination) pairs: (2,1,7,6) (0,7; 4,2) (5,4; 2,0) (6,3; 1,5) x y i,j 0,71,72,7 N E S W

13 Patrones de Comunicación Son posibles cuatro patrones de comunicaciones: 1.- Unicast uno a uno: Patrón de comunicaciones en que un procesador manda un mensaje a otro. 2.- Multicast: Un procesador fuente manda un mismo mensaje a múltiple destinos. 3.- Broadcast: Un procesador fuente manda el mismo mensaje a TODOS los procesadores restantes. 4.- Conference: Comunicaciones de todos con todos.

14 Encaminamiento Adaptativo en mallas Objetivo: Impedir interbloqueos, así como maximizar los recursos de forma global. En general suele implicar consideraciones tanto sobre el diseño de los bufferes de los routeres, como sobre la decisión a tomar frente a paquetes en espera, los mecanismos alternativos de encaminamiento, o, finalmente, el uso de canales virtuales. 02 01 00 12 11 10 22 21 20 02 01 00 12 11 10 22 21 20 (a) Original mesh without virtual channel (b) Two pair of virtual channels in Y-dimension (c) For a westbound message (d) For an eastbound message Adaptive X-Y routing using virtual channels to avoid deadlock; only westbound and eastbound Traffic are deadlock-free. (Courtesy of Lionel Ni, 1991) 02 01 00 12 11 10 22 21 20 02 01 00 12 11 10 22 21 20

15 Encaminamiento Uno-a-Muchos (Multicast) en Mallas D3D2 D1S D3D2 D4 D1SD5 D3D2 D4 D1SD5 3243 2132 1S21 (a) Five unicast with traffic = 13 (b) A multicast pattern with traffic and distance = 4 = 7 and distance = 4 (c)Another multicast patter with (d) Broadcast to all nodes via a tree traffic = 6 and distance = 5 (numbers in nodes correspond to levels of the tree) D4 D5

16 (a): Uno-a-muchos mediante transferencias punto-a-punto (b): Uno-a-muchos mediante replicación de paquetes en nodos intermedios (adecuado para redes store-and-forward) (c): Uno-a-muchos lineal (adecuado para redes wormhole (d): Radiación en árbol. Encaminamiento Uno-a-Muchos (Multicast) en Mallas

17 Encaminamiento Uno-a-Muchos (Multicast) en Hipercubos 0011 0001 0011 0001 0011 0001 1011 1001 01110110 0010 0100 0000 0101 11101111 1101 1100 1000 01110110 0010 0101 0000 0100 (a) Broadcast tree for a 4-cube rooted at node 0000 (b) A multicast tree from node 0101 to seven destination nodes 1100,0111,1010,1110,1011,1000 and 0010

18 (a): Radiación en árbol (orden decreciente de la dimensión) (b): Uno-a-muchos en árbol avaro (greedy) (se manda el paquete a lo largo de la dimensión que permita alcanzar el mayor número de destinos pendientes. Encaminamiento Uno-a-Muchos (Multicast) en Hipercubos

19 Conmutación de Paquetes Store-and-Forward Cada paquete (o mensaje completo) contiene información completa sobre su ruta (cabecera) y es transferido/almacenado en cada nodo intermedio de su camino origen-destino. Se necesitan buffers en cada nodo para almacenar paquetes (mensajes) completos Utilizado en las primeras generaciones de multicomputadores Cut-Through Cada paquete (mensaje) es descompuesto en flits (flow-control digits), con información de ruta (cabecera) sólo en el primero de ellos. El primer flit establece el camino transitado de nodo a nodo, mientras que el resto de los flits siguen la misma ruta y en el mismo orden (segmentación de la transmisión) Si una conexión bloquea el primer flit, el resto siguen el camino preestablecido almacenándose todos ellos en el nodo bloqueado.

20 Conmutación de Paquetes Wormhole: Variante del cut-through que minimiza el tamaño de los buffers en los nodos (sólo deben almacenar un único flit) Cuando el flit de cabecera se bloquea, el resto de los flits perma- necen almacenados en los buffers de los nodos previos. Este esquema puede dar lugar a interbloqueos (deadlock)

21 Encaminamiento Determinístico en la Red Omega Se define un “barajamiento perfecto” como la función  que mapea Enteros entre o y N-1 en sí mismos definida como  (x d-1 x d-2 … x 0 ) = x d-2 … x 0 x d-1 donde x d-1 x d-2... x 0 es la representación binaria de x Definimos también un mapa de cambios  como  (x d-1 x d-2 … x 0 ) = x d-1 x d-2 … x 0 * donde el asterisco denota complemento binario Finalmente, definimos una red de cambios por barajamiento como aquella que contiene N nodos x d-1 x d-2 … x 0, donde el nodo x está conectado al nodo y si y =  (x), x =  (y), o y =  (x)

22 Redes de Conexión Dinámicas Bus Compartido P2P2 PnPn C1C1 C2C2 CnCn M1M1 M2M2 MmMm I/O Subsystem P1P1 Secondary Storage (Disks, Tape Units) …. Proccesors Caches Bus Main Memory Colección de cables para la transferencia de datos multiplexados en el tiempo (tiempo compartido) Su coste es muy reducido pero su ancho de banda es bajo (escalabilidad limitada) Ampliamente utilizado cuando el número de nodos es reducido Ejemplos: - VME, IEEE Multibus II, IEEE Futurebus+, Encore Ultramax (1987; bus jerárquico), Sequent Symmetry, SGI Challenge (1993)

23 Redes de Conexión Dinámicas Barras Cruzadas (Crossbar) PE222 PE221 PE220 PE219 PE001 CP002 CP001 On Off......... Transmit Receive (b) The interprocessor crossbar network built in the Fujitsu VPP500 vector parallel processor (1992) P1P1 P2P2 P 16 M1M1 M2M2 M 16........... (a) Interprocessor-memory cross- bar network built in the C.mmp multiprocessor at Carnegie- Mellon University (1972)

24 Red con máximo ancho de banda y capacidad de interconexión, pero poco escalable y muy costosa. Puede considerarse como una red dinámica de una sola etapa, donde cada punto de cruce es un conmutador que puede estar abierto o cerrado. Ejemplos: - C.mmp (1972; barras cruzadas entre procesadores y memorias), Fujitsu VPP500 (1992; barras cruzadas entre nodos procesador- memoria)

25 Redes de Conexión Dinámicas Redes Dinámicas Multietapa

26 Varias etapas de conmutadores (proyecciones uno-a-uno y uno-a-muchos) y conexiones fijas. Redes con características intermedias entre buses y barras cruzadas Number of processors Cost Bus MultistageCrossbar Number of processorsPerformance Bus Multistage Crossbar

27 Redes de Conexión Dinámicas Red Omega Procesadores (izq.) Memorias (der.) Conexiones inter-etapa: barajamiento perfecto Ejemplos: - NYU Ultracomputer (1983), IBM RP3 (1985), Illinois Cedar (1987), IBM SP1/2 (1993/4) (e) A 16 x 16 Omega network

28 Redes de Conexión Dinámicas Red Benes Es una red no-bloqueante reorganizable, eliminando la posibilidad de interbloqueo entre caminos diferentes (permite varios caminos diferentes entre cada par entrada- salida) Se comporta como una red no-bloqueante pura (como las barras cruzadas) si se espe- cifican de antemano todos los caminos entrada-salida deseados (precomputación es- tática del encaminamiento) El inconveniente es mayor coste y latencia que su equivalente red Omega (es adecua- da, por tanto, la conmutación de circuito) Ejemplo: GF11 (576 nodos)

29 Redes de Conexión Dinámicas Red Banyan Ejemplo de red con diferente número de entradas y salidas Esta red permite un único camino entre cada para entrada-salida, como la red Omega Ejemplo: TRAC

30 Características de las Redes de Conexión Dinámicas