ORGANIZACIÓN DE COMPUTADORAS DRA. LETICIA FLORES PULIDO

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes para Multicomputadoras  El propósito de la red de interconexión, es proporcionar un ruta física de para envío de mensajes de una computadora a otra  Se manejan entonces:  ANCHO DE BANDA: número de bits que pueden ser transmitidos en una unidad de tiempo  LATENCIA DE LA RED: tiempo para hacer que un mensaje se transfiera por la red  LATENCIA DE COMUNICACIÓN: tiempo total para enviar el mensaje, incluyendo la sobrecarga de software y los retrasos de la intrefaz

2

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes para Multicomputadoras  LATENCIA DEL MENSAJE: el tiempo para enviar un mensaje de longitud cero, el cual es esencialmente la sobrecarga de software y hardware en enviar un mensaje (al encontrar una ruta, al cifrar, al decodificar, etc) además debe ser agregado el tiempo actual de envío de datos a lo largo de la ruta de interconexión.  NÚMERO DE RUTAS FÍSICAS: también es importante considerarlas como en el caso de dos nodos, lo cual puede implicar mas de dos rutas y que puede implicar un retraso en el mensaje

3

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes para Multicomputadoras  DIÁMETRO: Es el mínimo número de links entre dos nodos lejanos dentro de la red. Solamente las rutas más cortas son consideradas  ANCHO DE BISECCIÓN: De la red, es el número mínimo de cableado o rutas en que debe ser dividida la red en dos partes iguales

4

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes para Multicomputadoras  Existen varias maneras en que se pueden interconectar las computadoras para formar un sistema de multicomputadoras  Para un sistema pequeño, se puede considerar todas las computadoras entre si, por medio de cables  Con c computadoras, existen c(c-1)/2 cables a conectar  Pero esto aplica obviamente a sistemas pequeños

5

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes para Multicomputadoras  Por razones de practicidad y de consideraciones ingenieriles, esto es obviamente impráctico conforme c aumenta.  Es necesario entonces revisar las posibilidades de interconexión  Existen dos redes con interconexiones directas pero restringidas y que han sido utilizadas ampliamente en el campo: Red Mezclada y Red de Hipercubo

6

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

procesador

Red Mezclada  Un arreglo bidimensional es creado  Cada nodo está dentro de dicho arreglo bidimensional  Cada nodo se conecta a 4 de sus vecinos más cercanos

7

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Red Mezclada  El Diámetro de una red de este tipo es: 2(√ p -1)  Su expansión es relativamente sencilla  También puede haber variaciones con arreglos tridimensionales  Son convenientes para problemas ingenieriles, especialmente si los puntos de solución se dan en dos o tres dimensiones

8

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Red Mezclada  EJEMPLOS:  La computadora delta de Intel Touchstone (1991)  La máquina J (MIT) en 1991 con arreglo tridimensional  Una supercomputadora de RED 1997 Creada en el departamento de aceleración de energía estratégica  Que consiste en 9,472 Pentium II Xeon y utiliza una red mezclada de 38X32X2 para el envío de mensajes interconectados (en casos de memoria compartida) 9

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

Redes de Hipercubo:  Una red de hipercubo binaria tiene conexiones hacia las d-dimensiones o los d-vecinos de la red  Por ejemplo: En un hipercubo de d-dimensiones, se realizan conexiones en X, YyZ

111

110 100

101

011 010 000

001

10

Redes de Hipercubo:  A cada node se le asigna un dirección binaria de ddigitos  Cada bit es asociado a una dimensión  Los nodos dentro de un hipercubo tridimensional, tiene una dirección de 3 bits  En este ejemplo los nodos se conectan con aquellos cuyas direcciones solo difieren en un bit

Redes de Hipercubo:  Por ejemplo:  En un cubo con 5 dimensiones, el nodo 11101 conecta con los nodos 11100, 11111, 11001, 10101 y 01101  Una ventaja del hipercubo es que el diámetro de la red está dado por log2p para un hipercubo de p-nodos, el cual es razonablemente (bajo) con crecimiento p

Redes de Hipercubo: 0111

0110

1111

1110

0101 1100

0100

1101

1011

0011 1010

0010 0000

0001

1000

1001

Redes de Hipercubo:  Un aspecto conveniente en esta configuración, es el hecho de la existencia de una mínima distanci para un algoritmo libre de abrazos mortales (deadlocks)  Descripción del Algoritmo: 1. Supongamos que ruteamos un mensaje a partir de un nodo X con una dirección nodal de: X = x x ...x x n"1 n"2

2. Hacia un nodo destino, con la dirección nodal:

Y = y n"1 y n"2 ...y1 y 0 !

!

1 0

Redes de Hipercubo: 3. Cada bit de Y que difiere del identificador de X indica una dimensión de la ruta que puede tomar y puede encontrarse al realizar un OR-exclusivo Z =X ⊕ Y el cual opera directamente en pares de bits 4. Las dimensiones a utilizar dentro de dicha ruta están dadas por aquellos bits de Z que son 1’s. 5. Esto se ejecuta para cada nodo dentro de dicha ruta.

Redes de Hipercubo:  Por Ejemplo:  La ruta desde el nodo 13 (001101) hacia el nodo 42(101010) dentro de un cubo 6-dimensional podría ser:  Hacia el nodo 45 (101101)  Luego hacia el nodo 41 (101001)  De ahí al nodo 43 (101011)  Finalmente para llegar al nodo 42 (101010)

Redes de Hipercubo:  Este algoritmo de ruteo para el Hipercubo se le llama Algoritmo de Ruteo e-cubo, o algoritmo de ruteo de izquierda a derecha.  En la malla de hipercubo se tiene un ancho de bisección de 8 nodos  Una red de hiercubos se construyó por primera vez en el Tecnológico de California llamado el Cubo Cósmico en los 80’s y publicado en 1985 por Seitz como debut y despedida de dicho enfoque