Sistemas-De-Comunicación-En-Computadores-Paralelos-2.docx

UNIVERSIDAD NACIONAL DEL SANTA E.A.P DE INGENIRIA DE SISTEMAS E INFORMATICA

“UNIVERSIDAD NACIONAL DEL SANTA”FACULTAD DE INGENIERÍA

E.A.P. INGENIERÍA DE SISTEMAS E INFORMÁTICA

ARQUITECTURA DE COMPUTADORASPágina 1

CURSO:

Arquitectura de Computadoras

PROFESOR:

Carlos Guerra Cordero

ALUMNOS:

Gonzales Saavedra Franklin

León Muñoz Eduar

Cierto Córdova Juan

Vásquez Campos Sheyla

CICLO:

VIII

TEMA:

Sistema de comunicación entre computadores paralelos.


INDICE

Introducción…………………………………………………………………………………………..3

Estructura y funcionamiento………………………………………………………………………4

Interconexión de sistemas paralelos…………………………………………………………….5

Los mensajes…………………………………………………………………………………………7

Patrones de comunicación……………………………………………………………………….12

Construcción de caminos………………………………………………………………………...15

Encaminamiento de los mensajes………………………………………………………………17

Control de flujo de información………………………………………………………………….22

Eficiencia de la comunicación……………………………………………………………………28

Problemas de la comunicación…………………………………………………………………..29

Protocolos de comunicación……………………………………………………………………..30

Aplicaciones…………………………………………………………………………………………33

Tendencias en las redes de comunicación…………………………………………………….34

Conclusiones………………………………………………………………………………………..35

INTRODUCCION



La aparición de los ordenadores a mediados de este siglo ha sido sin duda una de las revoluciones más importantes en el campo tecnológico. Tan es así, que se especula con que la aparición de la Informática puede tener un impacto social incluso mayor del que en su día se atribuyó a la revolución Industrial. La historia de los ordenadores apenas tiene 50 años, pero su evolución en este corto período de tiempo ha sido vertiginosa. Conforme el uso de los ordenadores se ha hecho más común en nuestra sociedad, las personas les hemos pedido más y más prestaciones a estos aparatos, al comprobar la ayuda que la Informática presta en la resolución de los mil y un problemas corrientes de cada día. La aparición de los ordenadores personales, en la década de los años '80 ha sido un factor decisivo para favorecer la proliferación del uso de la Informática y ejercer una mayor presión social en el aumento de las prestaciones que desarrollan los ordenadores.

Dicha mejora en prestaciones se abordó en un primer momento apoyándose en diversas innovaciones tecnológicas tales como la integración de circuitos VLSI, el aumento de la frecuencia de reloj en los procesadores, el aumento del tamaño en el bus de control o de datos, etc. Pero estas mejoras tienen un techo impuesto por la naturaleza física de los componentes, lo que hizo que se pensara en otro modo de resolver este problema. Entonces es cuando se dirigió la vista a la arquitectura que presentaban los ordenadores. En la actualidad, los computadores masivamente paralelos con miles de procesadores son considerados como la tecnología mas prometedora para alcanzar una capacidad de procesamiento cercana a los teraflops. Tales computadores de gran escala se organizan como una replicación o aglomeración de unidades funcionales de tratamiento muy parecidas a las que encontramos en una máquina clásica. Cada una de estas unidad es reciben el nombre de nodos. Cada nodo tiene su propio procesador, su memoria local y otros periféricos.

El modo en que los nodos son conectados entre sí varía de unas máquinas a otras. En una máquina con una arquitectura de red directa, cada nodo tiene una conexión punto-a-punto con algún número de otros nodos, llamados nodos vecinos. Las redes directas son en la actualidad una arquitectura muy usada para construir computadores masivamente paralelos debido a que escalan bien, es decir, cuando el número de nodos en la máquina aumenta, también aumenta el ancho de banda de comunicación, el ancho de banda de la memoria y la capacidad de procesamiento de toda la máquina en su conjunto.

Sistems

De Comunicación En Computadores Paralelos: Estructura Y Funcionamiento, Ubicación De La Interfaz. Aplicación.

La red no es sino el soporte físico de la comunicación entre procesadores; por encima de ella, es


MENSAJE


necesario construir la lógica adecuada que permita llevar los mensajes desde el nodo origen al nodo destino. Para analizar el comportamiento de una red de comunicación, además de su topología, es necesario tener en consideración muchas otras cuestiones: ¿cómo se organiza el camino switching strategy)? ¿por dónde se llega al destino (routing algorithm)? ¿hay que usar siempre el mismo camino? ¿Cómo avanzan los mensajes por la red? ¿qué hay que hacer si el camino está ocupado (flow control)? Todas estas decisiones hay que tomarlas teniendo en cuenta que el objetivo debe ser que la latencia de la comunicación sea baja y el throughput de la red alto.

1. Estructura y funcionamiento

Los sistemas o redes de comunicación para computadores se han clasificado atendiendo a diversos criterios, por ejemplo, numero de nodos que interconectan, distancia entre nodos, si se puede utilizar para conectar sistemas autónomos o están implementadas para una arquitectura concreta.Los sistemas de comunicación diseñados o implementados a medida para computadores paralelos concretos, conectan nodos en diferentes niveles del sistema (chip, tarjeta, placa, armario, entre armarios). Algunos pueden llegar a conectar cientos y miles de nodos distribuidos en decenas o cientos de chasis o armarios. Se utilizan en multiprocesadores, multicomputadores y en procesadores matriciales. Se han desarrollado tradicionalmente dentro de la comunidad de diseñadores de arquitecturas de altas presentaciones. Su diseño (especificaciones) o si implementación se ajustan a una arquitectura concreta.Dentro del conjunto de redes o sistemas de comunicación a medida están, por ejemplo, las implementaciones utilizadas en sistemas como Convex Exampler( que implementa SCI), Fire 15k de sun, red de barras cruzadas de 640 x 640 que conecta a 640 nodos[Sato] en el supercomputador Earth Simulator(posición 1 de la lista TOP500 en 2003)Las redes de comunicación que utilizan para comunicar computadores, se pueden clasificar, en función al número de nodos que interconectan y de las distancias entre ellos., en tres grupos:

REDES LAN (Local Area Nextwork):

Conectan cientos de nodos situados a distancias de kilómetros, actualmente decenas de kilómetros. Surgieron dentro del grupo de investigación que desarrollo las estaciones de trabajo. Aparecieron por la necesidad de compartir recursos comunes que resultaban caros, como impresoras y servidores de disco. Las más conocidas son las redes Ethernet. Los conmutadores e interfaces para Ethernet van incorporando características de implementación de redes de altas prestaciones.

REDES LAN (Wide Area Nextwork):

Conectan redes de computadores entre si, lo que supone miles de nodos situados a miles de kilómetros de distancia. Se han desarrollado tradicionalmente dentro de la comunidad de telecomunicaciones. Por ejemplo, la especificación ATM (Asynchronous Transfer Mode), apareció a partir de las actividades de estandarización orientadas al desarrollo de la red de servicios integrados (RDSI, o ISDN, Integrated Services Digital Network).



REDES SAN (System Area Nextwork):

Una red SAN se distingue de otros modos de almacenamiento en red por el modo de acceso a bajo nivel. El tipo de tráfico en una SAN es muy similar al de los discos duros como ATA, SATA y SCSI. Pueden conectar decenas, cientos o miles de nodos situados a decenas o a unos pocos de metros. Son sistemas de comunicación de altas prestaciones, se puede decir que están entre los sistemas de comunicación hechos a medida y las redes LAN.

2. Interconexión de Sistemas Paralelos

La misión de la red en una arquitectura paralela es transferir información desde cualquier fuente a cualquier destino minimizando la latencia y con coste proporcionado.

La red se compone de:

Nodos: es cualquier elemento que se encuentre conectado y comunicado en una red; los dispositivos periféricos que se conectan a una computadora se convierten en nodos si están conectados a la red y pueden compatir sus servicios para ser utilizados por los usuarios, como impresoras, carpetas e información.



Conmutadores o Switch: Los conmutadores controlan el flujo del tráfico de red basándose en la información de la dirección de cada paquete. Un conmutador averigua qué dispositivos están conectados a sus puertos (monitorizando los paquetes que recibe), y envía los paquetes al puerto adecuado solamente. Esta acción permite la comunicación simultánea a través del conmutador, con lo que se mejora el ancho de banda.Esta operación del conmutador reduce la cantidad de tráfico innecesaria que se habría generado si se hubiera enviado la misma información desde cada puerto

Conectores: los conectores son aditamentos con los que los cables se conectan a las tarjetas de red ubicadas en los nodos. La función de los conectores es muy importante, ya que sin ellos es imposible utilizar los cables para conectar un nodo a la red. Cada medio de transmisión tiene sus conectores correspondientes y gracias a ellos se logra recibir o transmitir la información con las características que permiten cables.

La red se caracteriza por su:

Topología: Estructura de la interconexión física. La topología de una red es el arreglo físico o lógico en el cual los dispositivos o nodos de una red (e.g. computadoras, impresoras, servidores, hubs, switches, enrutadores, etc.) se interconectan entre sí sobre un medio de comunicación.

Enrutador: que determina las rutas que los mensajes pueden o deben seguir en el grafo de la red. Un router es un dispositivopara la interconexión de redes informáticas que permite asegurar el enrutamiento de paquetes entre redes o determinar la ruta que debe tomar el paquete de datos.

Estrategia de conmutación: de circuitos o de paquetes. La conmutación de paquetes es un método de envío de datos en una red de computadoras. Un paquete es un grupo de información que consta de dos partes: los datos propiamente dichos y la información de control, que indica la ruta a seguir a lo largo de la red hasta el destino del paquete. Existe un límite superior para el tamaño de los paquetes; si se excede, es necesario dividir el paquete en otros más pequeños. La conmutación de circuitos es un tipo de conexión que realizan los diferentes nodos de una red para lograr un camino apropiado para conectar dos usuarios de una red de telecomunicaciones. A diferencia de lo que ocurre en la conmutación de paquetes, en este tipo de conmutación se establece un canal de comunicaciones dedicado entre dos estaciones. Se reservan recursos de transmisión y de conmutación de la red para su uso exclusivo en el circuito durante la conexión. Ésta es transparente: una vez establecida parece como si los dispositivos estuvieran realmente conectados.

Control de flujo: mecanismos de organización del tráfico. es determinar el orden en el que se ejecutarán las instrucciones en nuestros programas. Si no existiesen las



sentencias de control entonces los programas se ejecutarían de forma secuencial, empezarían por la primera instrucción e irían una a una hasta llegar a la última.

3. Los mensajes

En función de la estructura del sistema paralelo, la información que se intercambia entre los procesadores puede organizarse de formas diversas. Si se utilizan variables compartidas, la comunicación se efectuará mediante operaciones de tipo rd/wr, es decir, pequeños paquetes de control más los datos. Si la comunicación se efectúa mediante paso de mensajes, éstos serán más largos y estructurados. Por otra parte, la longitud máxima de los mensajes que procesa la red suele estar limitada a un valor máximo. Si hay que enviar un mensaje más largo, entonces habrá que dividirlo en varios paquetes o unidades de transmisión de tamaño fijo. En un paquete es habitual distinguir los siguientes campos:

Cabecera: información de control que identifica al paquete, y que incluye, junto a la longitud, tipo, prioridad... del paquete, información sobre la dirección de destino.

Payload o carga de datos: datos a transmitir (contenido del mensaje). Cola: información de control para indicar fin de paquete, códigos de detección de errores

tipo checksum (más común en las redes LAN que en los MPP), etc.

Cola Cabecera

Así pues, tenemos que distinguir la información de control y los datos dentro de un paquete. Si los enlaces entre encaminadores son muy anchos (de muchos bits), los datos y la información de control pueden ir en paralelo. Por ejemplo, en el Cray T3D, los enlaces son de 24 bits, 16 bits para datos y 4


DATOS CONTROLCONTROL


para control (y 4 más para control de flujo). Con los 4 bits de control se indica, por ejemplo, el comienzo y el final de la transmisión de un paquete, etc. En el Cray T3E, en cambio, la información se envía en paquetes tales como los que hemos comentado (se dice que se hace framing).

Toda la información de control que se añade a los paquetes (cabecera, checksum...) supone una sobrecarga en la comunicación y, por tanto, una pérdida de eficiencia, por lo que hay que mantenerla acotada. Por ejemplo, si para mandar 100 bytes de datos hay que enviar un paquete con 128 bytes, entonces sólo aprovecharemos 100 / 128 = 78% del ancho de banda del sistema (para transmitir información útil).

La anchura de los enlaces de red que se utilizan para transmitir la información suele ir desde un bit (transmisión serie, se ha utilizado poco) hasta 16 bits (o más); según los casos, por tanto, puede que se necesite más de un “ciclo de transmisión” para transmitir “la unidad lógica más pequeña” de un paquete. Desde el punto de vista del control, los paquetes se suelen dividir en flits. En este contexto, un flit se define como la cantidad mínima de información con contenido semántico, normalmente la información mínima que se requiere para poder encaminar el paquete. Por ejemplo, si se utiliza transmisión en serie, cuando recibimos el primer bit de un paquete no podemos decir nada sobre dicho paquete; necesitamos más bits para poder saber a dónde va dicho paquete. Por tanto, los mensajes/paquetes se miden en flits. Lo más habitual es que un flit sean 8 o 16 bits, coincidiendo con la anchura de los enlaces que unen los encaminadores de la red. Normalmente, en uno o dos bytes se puede codificar la información necesaria para poder encaminar un paquete. De este modo, un flit se podrá transmitir entre encaminadores en un solo “ciclo”.


Figura N° 1.Computadora T3D MC 256 Figura N° 2.Computadora T3E-900


3.1. Interfaz de Paso de Mensajes(MPI)

MPI ("Message Passing Interface", Interfaz de Paso de Mensajes) es un estándar que define la sintaxis y la semántica de las funciones contenidas en una biblioteca de paso de mensajes diseñada para ser usada en programas que exploten la existencia de múltiples procesadores.El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronización entre procesos y permitir la exclusión mutua, de manera similar a como se hace con los semáforos, monitores, etc.

Figura 3. Interfaz de Paso de Mensajes

Con MPI el número de procesos requeridos se asigna antes de la ejecución del programa, y no se crean procesos adicionales mientras la aplicación se ejecuta. A cada proceso se le asigna una variable que se denomina rank, la cual identifica a cada proceso, en el rango de 0 a p-1, donde p es el número total de procesos. El control de la ejecución del programa se realiza mediante la variable rank; la variable rank permite determinar que proceso ejecuta determinada porción de código. En MPI se define un comunicator como una colección de procesos, los cuales pueden enviar mensajes el uno al otro; el comunicator básico se denomina MPI_COMM_WORLD y se define mediante un macro del lenguaje C. MPI_COMM_WORLD agrupa a todos los procesos activos durante la ejecución de una aplicación. Las llamadas de MPI se dividen en cuatro clases:

Llamadas utilizadas para inicializar, administrar y finalizar comunicaciones.



Llamadas utilizadas para transferir datos entre un par de procesos. Llamadas para transferir datos entre varios procesos. Llamadas utilizadas para crear tipos de datos definidos por el usuario.

a. Llamadas utilizadas para inicializar, administrar y finalizar comunicaciones.

MPI dispone de 4 funciones primordiales que se utilizan en todo programa con MPI. Estas funciones son:

- MPI_Init permite inicializar una sesión MPI. Esta función debe ser utilizada antes de llamar a cualquier otra función de MPI.

- MPI_Finalize permite terminar una sesión MPI. Esta función debe ser la última llamada a MPI que un programa realice. Permite liberar la memoria usada por MPI.

- MPI_Comm_size permite determinar el número total de procesos que pertenecen a un comunicator.

- MPI_Comm_rank permite determinar el identificador (rank) del proceso actual.

b. Llamadas utilizadas para transferir datos entre un par de procesos.

La transferencia de datos entre dos procesos se consigue mediante las llamadas MPI_Send y MPI_Recv. Estas llamadas devuelven un código que indica su éxito o fracaso. MPI_Send permite enviar información desde un proceso a otro. MPI_Recv permite recibir información desde otro proceso. Ambas funciones son bloqueantes, es decir que el proceso que realiza la llamada se bloquea hasta que la operación de comunicación se complete. Las versiones no bloqueantes de MPI_Send y MPI_Recv son MPI_Isend y MPI_Irecv, respectivamente. Estas llamadas inician la operación de transferencia pero su finalización debe ser realizada de forma explícita mediante llamadas como MPI_Test y MPI_Wait. MPI_Wait es una llamada bloqueante y retorna cuando la operación de envío o recepción se completa. MPI_Test permite verificar si la operación de envío o recepción ha finalizado, esta función primero chequea el estado de la operación de envío o recepción y luego retorna.

c. Llamadas para transferir datos entre varios procesos.

MPI posee llamadas para comunicaciones grupales que incluyen operaciones tipo difusión (broadcast), recolección (gather), distribución (scatter) y reducción. Algunas de las funciones que permiten realizar transferencia entre varios procesos se presentan a continuación. MPI_Barrier permite realizar operaciones de sincronización. En estas operaciones no existe



ninguna clase de intercambio de información. Suele emplearse para dar por finalizada una etapa del programa, asegurándose de que todos los procesos han terminado antes de dar comienzo a la siguiente. MPI_Bcast permite a un proceso enviar una copia de sus datos a otros procesos dentro de un grupo definido por un comunicator. MPI_Scatter establece una operación de distribución, en la cual un dato (arreglo de algún tipo de datos) se distribuye en diferentes procesos. MPI_Gather establece una operación de recolección, en la cual los datos son recolectados en un sólo proceso. MPI_Reduce permite que el proceso raíz recolecte datos desde otros procesos en un grupo, y los combine en un solo ítem de datos. Por ejemplo, se podría utilizar una operación reducción, para calcular la suma de los elementos de un arreglo que se distribuyó en algunos procesos.

d. Llamadas utilizadas para crear tipos de datos definidos por el usuario.

Para definir nuevos tipos de datos se puede utilizar la llamada MPI_Type_struct para crear un nuevo tipo o se puede utilizar la llamada MPI_Pack para empaquetar los datos.

CARACTERISTICAS DEL MPI

Estandarización. Portabilidad: multiprocesadores, multicomputadores, redes, heterogéneos, ... Buenas prestaciones. Amplia funcionalidad. Existencia de implementaciones libres (mpich, LAM-MPI, ...)

La especificación detalla las funciones que se pueden utilizar, no el modo como se compilan y lanzan-ejecutan los programas, lo cual puede variar de una implementación a otra. Siguiendo el modelo SPMD, el usuario escribirá su aplicación como un proceso secuencial del que se lanzarán varias instancias que cooperan entre sí.

Los procesos invocan diferentes funciones MPI que permiten

iniciar, gestionar y finalizar procesos MPI comunicar datos entre dos procesos realizar operaciones de comunicación entre grupos de procesos crear tipos arbitrarios de dato

4. Patrones de comunicación

No es posible responder de manera precisa a esa cuestión, ya que las necesidades de comunicación, obviamente, dependen de la aplicación a ejecutar. Sin embargo, podemos aclarar algunos aspectos. Por una parte, hay que tener en cuenta que el esquema de comunicación de una aplicación y el esquema de comunicación en la red son dos cosas diferentes, ya que en medio se encuentra la asignación física de procesos a procesadores. Es decir, si los procesos P1 y P2 tienen



que intercambiar información, no es lo mismo que se asignen a procesadores contiguos en la red que asignarlos a procesadores en dos extremos de la red. Por otra parte, las necesidades de comunicación no suelen ser siempre de todos con todos, sino entre algunos de los procesos. Tenemos por tanto que considerar múltiples aspectos: las necesidades de comunicación de la aplicación, el nivel de paralelismo, el reparto de procesos, etc.

Al esquema de comunicación que hay que ejecutar en la red se le conoce como patrón de comunicación. El patrón de comunicación puede ser espacial o temporal, es decir, puede indicar la distribución espacial de los paquetes (a dónde van) o su distribución en el tiempo (cuándo se transmiten). Analicemos algunos de los casos más típicos.

4.1. Aleatorio

Uno de los patrones que más se utiliza para analizar el comportamiento de las redes es el patrón aleatorio, tanto en el espacio como en el tiempo. La comunicación es aleatoria si la probabilidad de enviar un paquete del nodo i al j, PrCij, es la misma para cualquier par de nodos de la red. En este caso, la distancia media de la comunicación y la de la red (topológica) coinciden. Aunque tal vez no parezca un patrón de comunicación “lógico”, se obtiene de manera sencilla si el propio proceso de reparto de procesos a procesadores es aleatorio, lo cual puede ser útil para utilizar los recursos de la red de manera homogénea.

4.2. Esferas de localidad

La comunicación entre procesos, al igual que ocurre con los accesos a memoria, posee la propiedad de localidad: los procesos se comunican entre sí formando grupos; dentro del grupo, la comunicación es muy habitual, y fuera de él muy escasa. De cara a reducir la latencia de la comunicación, puede ser interesante asignar esos grupos a procesadores cercanos, con lo que la comunicación se limitará dentro de una “esfera”. La probabilidad de comunicación de este tipo de patrones es función, por tanto, de la distancia. En lo que al tiempo se refiere, puede ser aleatoria.

4.3. Broadcast / Multicast / Reporting

Las necesidades de comunicación pueden analizarse en el espacio y en el tiempo. Un tipo habitual de comunicación es la conocida como broadcast (difusión): desde el procesador i se envía un mensaje a todos los procesadores, a la vez. La operación termina cuando todos los nodos han recibido el mensaje. Es una operación muy habitual en muchas situaciones, por ejemplo para sincronizar procesos. Así pues, en un determinado momento se produce un pico de comunicación. El caso de multicast es similar, pero el mensaje no se envía a todos los nodos, sino solamente a un subconjunto de ellos. Existen muchos algoritmos que



implementan estos patrones de manera eficiente (spanning tree...) pero no los vamos a analizar.

El caso conocido como reporting es justamente el contrario: todos los procesadores envían un mensaje al mismo nodo destino, más o menos a la vez. Es un patrón de comunicación que genera muchos problemas, ya que podemos tener niveles elevados de tráfico en las cercanías del nodo destino, que pueden llegar a saturar la capacidad de enlaces y encaminadores. También para este caso existen algoritmos para intentar reducir el problema y efectuar la comunicación de manera eficiente (combining messages).

4.4. Matriz transpuesta, FFT, perfect shuffle.

Algunas aplicaciones de cálculo muy habituales —matriz transpuesta, transformada discreta de Fourier...— suelen generar patrones de comunicación específicos. En estos patrones la comunicación se concentra en momentos determinados, por lo que en esos momentos crecerá la densidad del tráfico de paquetes, puede que se saturen algunas zonas de la red, y, en consecuencia, la latencia de los paquetes será más alta. En todo caso, se trata de momentos concretos de saturación, ya que la red debe ir recuperando su estado normal según va transportando los paquetes a su destino.

Otra característica de la comunicación de una determinada aplicación es el tamaño de los mensajes que genera: grandes, pequeños, de todo tipo. En base a este parámetro suelen distinguirse dos tipos de paralelismo. Por un lado, el paralelismo de grano fino, en el que los mensajes que se intercambian los procesos son cortos (10 - 100 bytes), pero la comunicación es muy frecuente. En el lado opuesto tenemos el paralelismo de grano grueso, con mensajes largos (1 kB - 100 kB) pero mucho menos frecuentes. Por otra parte, junto con los paquetes de datos se van a generar muchos paquetes de control (para mantener la coherencia, para la sincronización...), que, comparados con los de datos, son mucho más cortos.


Broadcast Multicast


En resumen, las aplicaciones paralelas van a generar mensajes de tamaño muy diverso, que habrá que procesar de manera eficiente en todos los casos. Por ello, en algunos sistemas de comunicación se distinguen clases de mensajes (cortos y largos, o de datos y de control) y se tratan de manera diferente; por ejemplo, se da preferencia a los mensajes cortos (de control).

5. Construcción del camino (switching strategy)

El camino que va a "unir" el emisor y el receptor (dos procesadores o un procesador y un módulo de memoria) puede “construirse” de maneras diferentes (que se suelen conocer como técnica de conmutación o switching). Las dos técnicas habituales son:

5.1. Conmutación de circuitos (circuit switching)

Antes de comenzar con la transmisión de datos, se construye (se reserva) un camino físico específico que une emisor y receptor, para lo que se envía un mensaje de control especial, una sonda, que según avanza hacia el destino va reservando los recursos de red que utiliza. Al llegar al destino, se envía una respuesta al nodo origen utilizando el camino que ha “construido” el mensaje sonda. Cuando se recibe este mensaje de confirmación, se procede a enviar los datos por el camino privado establecido entre emisor y receptor.

Reservar el camino requiere cierto tiempo, pero, una vez construido, la transmisión de datos se efectúa sin ninguna limitación, ya que todo el ancho de banda de los enlaces está disponible para nuestro mensaje. Este mecanismo resulta interesante si el tiempo de construcción del camino es mucho menor que el de transmisión de datos (como ocurre, por ejemplo, en el caso de una llamada telefónica).

Cuando se utiliza conmutación de circuitos no es necesario dividir los mensajes en paquetes, ya que no vamos a utilizar nunca búferes intermedios. En todo caso, no hay que olvidar que si los mensajes son muy largos se van a mantener ocupados los enlaces entre encaminadores durante largo tiempo, por lo que la latencia de otros mensajes que querrían utilizar esos recursos puede crecer mucho, lo cual puede no ser aceptable en un entorno de computación paralela. El ejemplo más conocido de este tipo de comunicación es la telefonía. Aunque se ha utilizado en algún multicomputador comercial (por ejemplo, en el iPSC2 de Intel o en Meiko CS-2 y BBN butterfly), no es la alternativa habitual en los sistemas MPP.



5.2. Conmutación de paquetes (packet switching)

Para efectuar la comunicación no se construye un camino, sino que se envían paquetes a la red y éstos van escogiendo el camino adecuado, en función de la dirección de destino (como en el tráfico postal). Ésta es la técnica más habitual para efectuar la comunicación en los sistemas paralelos. Los encaminadores de mensajes de la red reciben los paquetes, procesan la información de control, y los reenvían al siguiente encaminador, hasta llegar así al nodo destino.

La información de control que indica el destino de los paquetes debe ser sencilla de interpretar, ya que no podemos perder mucho tiempo en ese proceso si queremos que la comunicación sea eficiente, es decir, que la latencia de los paquetes sea la menor posible. En el próximo apartado veremos cómo indicar dicha información.

Cuando, por ser grande, un mensaje se divide en varios paquetes se genera una cierta sobrecarga en la comunicación, ya que hay que añadir la información de control en cada paquete. Por ello, salvo que exista otro tipo de razones, no conviene dividir los mensajes en paquetes muy cortos. En general, el tamaño máximo de los paquetes suele estar relacionado con el de los búferes de los encaminadores.



6. Encaminamiento de los mensajes (routing)

Para llegar a su destino, los paquetes deben atravesar la red de comunicación. Pero, ¿cuál es el camino para llegar al destino? Tenemos que resolver dos problemas. Por un lado, cómo indicar la dirección de destino del paquete, y, por otro, qué camino elegir entre los múltiples caminos que enlazan el nodo origen y el destino. En todo caso, y salvo que tuviéramos que resolver algún problema particular, el camino escogido debe ser siempre un camino de distancia mínima (los paquetes nunca se alejan de su destino). Veamos cómo resolver estos problemas.

6.1. El registro de encaminamiento

Cuando se utiliza conmutación de paquetes, el procesador (más exactamente, el interfaz con la red) inyecta los paquetes a transmitir en la red para que éstos lleguen a su destino utilizando por el camino los diferentes recursos de la red (de manera similar a lo que ocurre con el correo habitual). Para llegar desde el nodo origen al destino hay que utilizar la información que lleva el propio paquete. ¿Por dónde avanzar en la red? El proceso de hacer avanzar un paquete en la red se conoce como encaminamiento (routing). El encaminamiento de los paquetes en la red debe ser sencillo. Dos son las opciones más habituales.

En la cabecera del paquete se incluye la dirección de destino; así, en cada encaminador de mensajes intermedio se decidirá por dónde debe avanzar el paquete en función de dicha dirección. Para ello pueden usarse dos técnicas diferentes: (a) utilizar una tabla que indique los puertos de salida adecuados para cada dirección de destino; o (b) efectuar una operación sencilla con la dirección que dé como resultado el puerto de salida.



La cabecera del paquete indica el número de pasos que debe dar el paquete en cada dimensión para llegar al destino, en un campo que se conoce como registro de encaminamiento (routing record). En cada paso se actualiza el registro de encaminamiento (±1), y cuando todos sus elementos valgan 0, el paquete ha llegado a su destino.

De una manera o de otra, la elección del camino debe ser lo más rápida posible, ya que no podemos demorar demasiado tiempo los paquetes en los encaminadores intermedios, so pena de que la latencia de la comunicación crezca mucho. Ya que los registros de encaminamiento son, probablemente, la opción más utilizada, veamos cómo calcular el registro de encaminamiento en las topologías de red que hemos analizado en el apartado anterior.

a) Mallas Los procesadores que forman la malla se suelen identificar según sus coordenadas en la misma

b) Toros El procedimiento es el mismo, pero en este caso hay que tener en cuenta que tenemos un anillo en cada dimensión. Y en un anillo siempre hay dos caminos para ir de un punto a otro: por “delante” o por “detrás”; eso sí, escogiendo siempre el camino mínimo. Por tanto, en un anillo de k nodos no se dan nunca más de d = k/2 pasos en una dirección, ya que siempre es posible efectuar k – d pasos en la dirección contraria, es decir, recorrer una distancia menor. Así pues, el registro de encaminamiento se calcula como en el caso anterior, pero se efectúa luego una fase de corrección para buscar el camino mínimo.

c) Hipercubos. También en este caso el encaminamiento de los paquetes es sencillo. El hipercubo es un cubo binario, es decir, tiene sólo dos nodos en cada dimensión, con etiquetas 1 y 0. La etiqueta de cada nodo es simplemente el conjunto de etiquetas en cada dimensión.

d) Árboles. También en este caso es sencillo el encaminamiento de los paquetes. En primer lugar, habrá que decidir hasta qué nivel del árbol hay que subir (mediante una comparación de las direcciones origen y destino), y, después, por qué rama hay que descender para llegar al destino (normalmente utilizando la dirección destino).

6.2. Elección del camino: estático o adaptativo

Cuando un paquete llega a un encaminador de la red se analiza la cabecera del mismo para saber si va destinado al procesador local o a otro procesador, y para ello se utiliza el registro



de encaminamiento. Cuando todos los campos del registro de encaminamiento son 0, entonces el paquete ha llegado al destino; si no, debe continuar hacia adelante.

Aunque el registro de encaminamiento esté perfectamente definido, el camino entre origen y destino no es único, y, en general, dispondremos de muchas alternativas. Por ejemplo, si hay que dar dos pasos en ambas direcciones de una malla —RE = [2, 2] —, tenemos 6 posibilidades diferentes de recorrer el camino: x-x-y-y, x-y-x-y, x-y-y-x, y-x-x-y, y-x-y-x, y-y-x-x. ¿Qué camino hay que seguir? ¿Hay que seguir siempre el mismo camino?

6.2.1. Encaminamiento estático

Cuando un paquete llega a un encaminador de la red se analiza la cabecera del mismo para saber si va destinado al procesador local o a otro procesador, y para ello se utiliza el registro de encaminamiento. Cuando todos los campos del registro de encaminamiento son 0, entonces el paquete ha llegado al destino; si no, debe continuar hacia adelante.

Aunque el registro de encaminamiento esté perfectamente definido, el camino entre origen y destino no es único, y, en general, dispondremos de muchas alternativas. Por ejemplo, si hay que dar dos pasos en ambas direcciones de una malla —RE = [2, 2] , tenemos 6 posibilidades diferentes de recorrer el camino: x-x-y-y, x-y-x-y, x-y-y-x, y-x-x-y, y-x-y-x, y-y-x-x. ¿Qué camino hay que seguir? ¿Hay que seguir siempre el mismo camino? "primero-X-luego-Y".

Los paquetes avanzan hacia el destino recorriendo primero todo el camino en una dimensión, luego en la siguiente, etc. Por tanto, en el encaminamiento estático sólo se utiliza uno de todos los caminos posibles para ir del nodo i al nodo j.

Dado que se utiliza un sólo camino, se pierde la tolerancia a fallos de bajo nivel; si no se puede avanzar, porque hay una avería, habrá que utilizar algoritmos de otro nivel para que la comunicación se pueda efectuar.

6.2.2. Encaminamiento dinámico o adaptativo

El encaminamiento es dinámico si los paquetes que van de i a j no siguen siempre el mismo camino, sino que escogen el camino más adecuado en función de la situación concreta de la red. El encaminamiento dinámico es más flexible, y permite utilizar caminos en los que la densidad de tráfico sea menor para evitar zonas de la red que estén temporalmente saturadas.



En la siguiente figura se muestran tres opciones (con línea continua la correspondiente al encaminamiento DOR) para poder ir del nodo (1, 0) al nodo (3, 3). En los tres casos el registro de encaminamiento es RE = [2, 3]. Si, por ejemplo, hubiera una congestión de tráfico alrededor del nodo (1, 1), podría ser más adecuado utilizar el camino (b) en lugar del (a). La misma idea se puede aplicar para evitar fallos en la red: aunque se estropee el enlace (1, 2) → (1, 3), todavía tenemos posibilidades de llegar al nodo (3, 3), utilizando, por ejemplo, el camino (c).

Existen muchas maneras diferentes de efectuar la adaptación. Una de las más conocidas es la denominada zigzag: siempre que sea posible, los paquetes no agotan el recorrido en una dimensión, sino que los van intercambiando. De esa manera se consigue mantener hasta el final la posibilidad de utilizar caminos alternativos frente a posibles problemas de tráfico o de fallos en la red. Para el caso de dos dimensiones, un ejemplo de algoritmo simplificado podría ser el siguiente:

si (|REx| > |REy|) entonces Sigue_por_el_eje_X ; X+, X- si_no Sigue_por_el_eje_Y ; Y+, Y-

si (salida_elegida_ocupada) entonces Intenta_la_otra ; si hay alternativa

Aunque el encaminamiento dinámico ofrece ciertas ventajas, hay que valorar, como siempre, los posibles inconvenientes que introduce. A menudo, el encaminamiento dinámico es consecuencia de una apuesta; por ejemplo, si en un momento determinado no se puede utilizar una salida porque está ocupada, se decide avanzar por otro camino. Por desgracia, para tomar esa decisión se utiliza sólo información parcial, basada normalmente en el tráfico local, y no se sabe en qué situación se encuentra el nuevo camino elegido (quizás peor que el rechazado). En todo caso, cuando la red no es simétrica o cuando el tráfico se



reparte de manera no homogénea, es fácil que surjan zonas de alta densidad de tráfico en la red (hot spots), y en esos casos puede resultar efectivo el encaminamiento adaptativo.

Por otra parte, si se divide un mensaje en varios paquetes y éstos utilizan caminos diferentes para llegar al destino, lo más probable es que lleguen en desorden, por lo que habrá que recomponer el mensaje en el destino (y los paquetes deberán incluir más información de control). Además, los encaminadores deberán ser más complejos para poder aplicar encaminamiento adaptativo y, por tanto, el tiempo de procesamiento de los paquetes será mayor. Por último, como analizaremos más adelante, cuando se utiliza encaminamiento adaptativo se pueden producir bloqueos (deadlock) en la red: los paquetes no son capaces de avanzar, porque se impiden avanzar unos a otros. Por tanto, hay que evaluar cuidadosamente el uso de encaminamiento adaptativo.

6.2.3. Encaminamiento no mínimo

Aunque el camino recorrido por los paquetes debiera ser de longitud mínima, en algunos casos puede ser necesario o útil utilizar caminos más largos para llegar a destino, para, por ejemplo, rodear una zona de tráfico denso, o, sobre todo, para evitar zonas con fallos en la red.

Por ejemplo, un paquete va desde el procesador (1, 0) al procesador (3, 2), y cuando está en el encaminador del nodo (1, 2) detecta que no puede avanzar porque el encaminador del nodo (2, 2) no responde (se ha estropeado). En ese caso, tiene la posibilidad de tomar un camino más largo, como el que aparece en la figura, para poder completar la comunicación.

7. Control del flujo de información

Los paquetes avanzan en la red de encaminador a encaminador hasta llegar a su destino. Pero, ¿cómo se efectúa el avance? ¿Qué hay que hacer si los recursos que necesita un paquete para seguir adelante están ocupados? Este tipo de cuestiones se conocen como “control del flujo” de los paquetes.

7.1.1. Avance de los paquetes: SF, WH, CT

¿Cómo se transmite un paquete de encaminador a encaminador? Supongamos que los enlaces de la red son de un byte, con lo que en un “ciclo” de transmisión se pasará un byte entre dos encaminadores. Los paquetes que hay que transmitir van a ser bastante más largos, por lo que necesitaremos varios ciclos de transmisión para pasar todo el paquete



(todos los flits o bytes) de un encaminador al siguiente. Mientras tanto, ¿qué hay que hacer con un paquete que se está recibiendo? Veamos las dos alternativas principales: store-and-forward y wormhole / cut-through.

7.1.2. Store-and-forward (SF)

Store-and-forward es el nombre de la técnica empleada en la primera generación de multicomputadores para pasar los paquetes entre dos encaminadores sucesivos (técnica habitual en las redes LAN y WAN).

En este caso, el encaminador que está recibiendo el paquete no hace nada con el mismo hasta que no lo termina de recibir del todo. A continuación, analiza la cabecera del paquete y decide por dónde debe retransmitirlo. De esa manera, la transmisión de los paquetes se limita siempre a dos encaminadores: el que transmite y el que recibe. Mientras se produce la transmisión, el paquete se guarda en un búfer interno del encaminador (véase la figura siguiente). En primera aproximación, el tiempo de comunicación de un paquete resulta proporcional al tamaño del paquete (L) y a la longitud del camino recorrido (d):

Tsf ~ L × dAsí pues, cuando se duplica la distancia a recorrer, también se duplica la latencia de un paquete.

7.1.3. Wormhole (WH) / Cut-through (CT)

La técnica SF no es muy adecuada para los sistemas MPP, ya que la latencia de la comunicación puede resultar muy elevada (en función de la distancia a recorrer), y la comunicación es crucial en muchas de las aplicaciones que se



ejecutan en paralelo. Por ello, los sistemas paralelos actuales utilizan otra técnica conocida como wormhole (WH) o cut-through (CT).

Cuando un encaminador recibe el primer flit de la cabecera de un paquete (normalmente una parte del registro de encaminamiento) analiza a dónde se dirige. Si debe continuar con su recorrido, entonces se le asigna directamente un puerto de salida y se comienza a retransmitir al siguiente encaminador, sin esperar a recibir todo el paquete; el resto de flits del paquete se enviará tras el primero, por el mismo camino, según vayan llegando. Así, el paquete queda distribuido a lo largo del camino hacia el destino: la comunicación se ha “segmentado”, ya que muchos encaminadores toman parte simultáneamente en la transmisión de un paquete.

Se necesitan d ciclos para que el primer flit de la cabecera del paquete llegue al destino, tras lo cual llegarán, ciclo a ciclo, el resto de flits del paquete. Por tanto, en primera aproximación, la latencia de un paquete en modo WH o CT será proporcional a la suma de L y d. Es decir,

Tct/wh ~ L + dClaramente, la latencia de la comunicación en modo wormhole será menor que en modo store-and-forward, ya que L y d se suman en lugar de multiplicarse: el efecto de la distancia a recorrer en el tiempo de transmisión es mucho menor en modo CT/WH que en modo SF.

La transmisión de un paquete se efectúa de la misma manera en modo wormhole que en modo cut-through, pero si la cabecera de un paquete no puede continuar avanzando, porque la salida que necesita utilizar está ocupada por otro paquete, la respuesta es diferente en ambos casos:

7.1.3.1. Wormhole.



Se detiene la recepción del paquete, y éste queda bloqueado a lo largo de todo el camino que recorre. Cuando se libera el camino de salida, se retoma la transmisión de los flits en todos los encaminadores implicados.

7.1.3.2. Cut-through.

Aunque la cabecera del paquete no pueda avanzar, se siguen recibiendo el resto de los flits del paquete, y se almacenan en un búfer propio del encaminador hasta que el canal de salida que se necesita se libere, en cuyo caso se proseguirá con la transmisión de la cabecera del paquete. De esta manera, el paquete cuya cabecera no puede avanzar no mantiene ocupados tantos recursos de la red, con lo que se producirán muchos menos conflictos con otros paquetes.

Si se utiliza cut-through, es necesario que los encaminadores dispongan de búferes con capacidad para almacenar paquetes de manera



transitoria, hasta que prosigan su camino; si utilizamos wormhole, ese espacio, en principio, no es necesario (bastaría con poder guardar un flit: el que se estáprocesando en ese momento). En muchas máquinas se aplican estrategias intermedias entre WH y CT: no hay capacidad para almacenar un paquete completo, pero pueden guardarse varios flits (por ejemplo, pueden almacenarse 4 flits de un paquete a la espera de que quede libre el puerto de salida).

Analizado desde otro punto de vista, podemos decir que CT representa un compromiso entre WH y SF. Cuando hay poco tráfico en la red, CT se comporta igual que WH: no habrá conflictos en el uso de los recursos y, por tanto, no se almacenan los paquetes en los encaminadores intermedios. En cambio, cuando el tráfico es elevado CT se acerca al comportamiento de SF: los conflictos son muy habituales en los encaminadores de la red, y los mensajes se almacenan casi siempre.

7.1.4. Conflictos en el uso de recursos: los búferes

Los paquetes recorren la red utilizando los enlaces de la misma y los encaminadores de mensajes. La red es por tanto un recurso compartido, que va a ser utilizado simultáneamente por muchos paquetes. ¿Cómo hay que afrontar los conflictos que, inevitablemente, se van a producir al usar esos recursos? Ya hemos comentado en qué difieren CT y WH al tratar los conflictos: el paquete que no puede seguir adelante se almacena temporalmente en el encaminador intermedio, o se deja bloqueado a lo largo de toda la red.

En el caso de CT (y, por definición, de SF) se necesita de un “poco” de memoria para almacenar transitoriamente los paquetes (o algunos flits de un paquete) en los encaminadores, hasta que la salida correspondiente esté libre. Normalmente, los encaminadores no disponen de gran cantidad de memoria para almacenar mensajes, sino que tienen la posibilidad de almacenar unos cuantos bytes o unos cuantos paquetes. Por ejemplo, si los paquetes son de 64 bytes, sería suficiente con una capacidad de 1 o 2 kB (16 o 32 paquetes) por canal; no parece razonable tener una memoria de 1 MB para gestionar un posible bloqueo de 16000 paquetes. Además, el funcionamiento de los encaminadores debe ser eficiente y rápido, con el fin de que la latencia de los paquetes sea lo menor posible, y para ello lo más adecuado es que los encaminadores sean lo más sencillos posibles.

Hay muchas maneras de organizar y gestionar esos búferes (normalmente en forma de cola FIFO), y cada una de ellas tiene sus ventajas e inconvenientes. Además, sea cual sea el número de búferes, siempre es posible que una



aplicación genere un tráfico muy intenso en un momento dado, que sature la capacidad de guardar más paquetes. ¿Qué hacer en esos casos? Analicemos esos problemas uno a uno, aunque sea de manera somera.

7.1.4.1. Estructura de los búferes: compartidos o separados

El espacio de memoria de los encaminadores puede ser compartido, para paquetes que lleguen por cualquier entrada, o puede repartirse a cada entrada, sólo para paquetes que lleguen por cada entrada.

Búferes compartidos búferes repartidos

Si el espacio de memoria es compartido, la capacidad de almacenamiento disponible se utiliza de manera más eficaz, ya que siempre hay sitio para un paquete hasta que se agota toda la memoria del encaminador; sin embargo, si lo repartimos entre los diferentes puertos de entrada del encaminador, puede que se llene una de las colas de entrada y no se pueda admitir más paquetes en esa entrada aunque pudiera quedar sitio libre en otras colas. Pero, por otra parte, la gestión de una memoria común para todas las entradas es más compleja, tanto en la carga de nuevos paquetes como en la salida de los mismos: se necesita una cola multientrada, porque la carga de paquetes (de diferente tamaño) puede ser simultánea durante varios ciclos y desde varios puertos de entrada; también debe ser multisalida, para que un paquete que no puede continuar su viaje no bloquee a otros paquetes que sí podrían continuar. Como siempre, se trata de buscar un compromiso entre eficiencia y complejidad.

En muchos sistemas, los paquetes tienen diferentes niveles de prioridad; por ejemplo, los paquetes de control (en general, paquetes cortos) pueden tener prioridad sobre los paquetes de datos (más largos). En esos casos, los búferes se organizan en varias colas, una por cada clase de paquete.

7.1.4.2. Búferes en las entradas o en las salidas

Los búferes de espera pueden asociarse tanto a los puertos de entrada como a los de salida. Si se colocan en la entrada, los paquetes pasan directamente al búfer de espera si su salida no está disponible o si hay paquetes esperando en los búferes de esa entrada. En cambio, si se colocan en la salida, primeramente se efectúa la operación de asignación de puerto de salida (encaminamiento) y luego se pasa, en su caso, al búfer de espera.



Búferes en las entradas búferes en las salidas

Las ventajas y desventajas parecen claras. La gestión es más sencilla a la entrada, pero su uso no es tan eficiente (el primer paquete de una cola bloquea al resto de los paquetes, aunque éstos tengan camino libre). La gestión de los paquetes es más eficiente si se colocan a la salida, ya que ya se ha efectuado la asignación de salida para cuando se bloquea el paquete, pero su estructura es más compleja, ya que de nuevo deben ser colas multientrada.

8. Eficiencia de la comunicación: latencia y throughput

La red de comunicación, y junto con ella todo el sistema de paso de mensajes, no es sino un intermediario necesario para poder llevar a cabo la comunicación entre procesos. Dado que la comunicación es una parte más del proceso de ejecución en paralelo, el subsistema de comunicación de una máquina MPP debe ser muy eficiente. Dos son los parámetros más habituales para medir la calidad del sistema de comunicación de un computador paralelo: la latencia de los paquetes y el número de paquetes que puede gestionar (throughput). La latencia de un paquete define el tiempo necesario para efectuar la comunicación en la red. El throughput, por su parte, marca el número de paquetes que es capaz de gestionar la red sin saturarse. La red ideal es capaz de gestionar un número muy elevado de paquetes con una latencia muy baja.

Antes de analizar los diferentes parámetros que conforman el tiempo de comunicación, repasemos algunos conceptos:

Anchura de los enlaces: número de bits que puede transmitir simultáneamente el enlace; por ejemplo, 8 bits (en los enlaces serie, un solo bit). En algunos casos, a este parámetro se le conoce también como phit (physical unit).

Ciclo de transmisión: tiempo necesario para transmitir un phit. Si el sistema es síncrono, normalmente un ciclo del reloj correspondiente.



Ancho de banda de los enlaces: cantidad de información que se puede transmitir en un segundo, habitualmente en (Mega) Gigabit/s (109 bit/s). Por ejemplo, enlaces de 10 Gb/s.

Ancho de banda útil: la información a transmitir se estructura en paquetes, y eso significa cierta sobrecarga, ya que además de los datos hay que transmitir información de control (cabecera...). Por ello, para transmitir n bits de datos tenemos que transmitir n + nk bits. El ancho de banda útil se define como n / (n + nk). Es obvio que necesitamos que nk sea lo menor posible.

Tiempo de encaminamiento (routing time, tr): tiempo necesario en cada encaminador para procesar la cabecera del paquete y decidir por dónde debe ir. Sin duda, interesa que este tiempo sea el menor posible

9. Problemas de la comunicación

La función de la red de comunicación es permitir la comunicación entre procesadores gestionando un número alto de paquetes con una latencia baja. En todo caso, lo que sí debe asegurar es que todos los paquetes enviados llegan finalmente a su destino. Por tanto, debemos hacer frente a algunos de los problemas habituales en sistemas distribuidos que ya hemos comentado (por ejemplo en los controladores snoopy): deadlock, livelock y starvation. Analicemos su efecto en un sistema de comunicación.

9.1. Deadlock (interbloqueos)

Tenemos un deadlock de comunicación si un grupo de paquetes se impiden el avance entre ellos y quedan indefinidamente retenidos en la red: m paquetes forman un ciclo y cada uno de ellos impide el avance del siguiente, no llegando nunca a su destino (latencia infinita). No es difícil que se produzca esa situación, en función de cómo se gestionen los paquetes en la red. Veamos un ejemplo (comunicación tipo WH).



Tenemos cuatro paquetes en la red, y los caminos elegidos forman un ciclo cerrado; tal como vemos en la figura anterior, los paquetes se autobloquean y no llegarán nunca al destino fijado.

En todos los casos, las situaciones de interbloqueo aparecen cuando se agotan los recursos de la red: en el caso wormhole, los enlaces, y en el caso cut-through, los búferes. Desde luego, el interbloqueo no aparecería nunca si las colas de búferes para guardar paquetes fueran infinitas, pero eso no es posible, y aunque sean grandes siempre cabe la posibilidad de que se llenen.

El problema del interbloqueo puede aparecer con más facilidad si los caminos que siguen los paquetes no están previamente planificados, es decir, si los caminos se escogen en función de la situación del tráfico en la red (por ejemplo, si se utiliza encaminamiento adaptativo). En caso contrario, si los caminos están prefijados, es más sencillo evitar el problema. Sea como fuere, necesitamos que los procesos de comunicación estén libres de este problema, o sepan cómo resolverlo. Antes de comentar las estrategias principales, conviene recordar que tenemos dos alternativas para hacer frente al problema: (a) no utilizar ningún mecanismo de comunicación que pueda presentar deadlock; y (b) admitir que se pueda producir el bloqueo, y en cambio, detectar si se produce o no, y dar una solución concreta en ese momento.

9.2. Problemas de livelock y starvation

Existe otro tipo de problemas a resolver relacionados con la comunicación en la red, aunque de menor importancia que el que hemos tratado. El problema de livelock aparece en la red si los paquetes se mueven, no están parados, pero nunca consiguen llegar al destino. Por ejemplo, este problema puede aparecer si utilizamos una estrategia de control de flujo que ya hemos citado: si no hay sitio para recibir un paquete se “echa fuera” del encaminador se



desvía de su camino un paquete que hemos recogido antes. A continuación, el paquete que acabamos de desviar vuelve a solicitar sitio en el encaminador, y desviamos al paquete que acabamos de recoger. Es decir, moverse se mueve, pero no van a ninguna parte.

Otro problema que puede aparecer en la gestión de la red de comunicación es el de starvation (hambruna). La red de comunicación y los protocolos correspondientes deben tratar a todos los procesadores de la misma manera. Salvo por cuestiones de prioridades, que tienen que estar bien explícitas, no es de recibo que un procesador siempre pueda inyectar sus mensajes en la red mientras que otro nunca pueda hacerlo. Por ejemplo, si existe una zona de la red en la que se concentra el tráfico (tal vez en el centro de una malla si todos los mensajes van hacia el centro), hay que asegurar que los procesadores de esa zona de la red puedan inyectar sus mensajes y no estén siempre a la espera de encontrar un hueco.

10. Protocolos de comunicación

El proceso completo de paso de información entre dos procesos que se ejecutan en procesadores diferentes, además de la transmisión física en la red de comunicación, implica una serie de procedimientos a ejecutar tanto en el nodo emisor como en el receptor, procedimientos que no podemos desdeñar, ya que bien pudiera ocurrir que la latencia de los mismos llegara a superar a la de la propia transmisión física de los mensajes. Aunque no vamos a efectuar un análisis detallado de los protocolos implicados en esos procesos, vamos a acabar este capítulo haciendo un pequeño resumen de los mismos. Protocolos estándar en el mundo de las redes de computadores, tales como TCP/IP, no resultan adecuados para los sistemas MPP (aunque se usan en clusters de bajo nivel). La implementación habitual de los mismos hace entrar en juego al sistema operativo del nodo emisor, para efectuar una copia del mensaje a transmitir de la memoria de usuario a la del propio sistema operativo. El mismo proceso se repite en el nodo receptor.



El overhead añadido por estas intervenciones del sistema operativo puede ser aceptable si la velocidad de transmisión es baja (100 Mb/s), pero no lo es cuando la velocidad es alta (10 Gb/s).

En los últimos tiempos se han desarrollado protocolos más eficientes para ser usados tanto en sistemas MPP de diseño específico como en clusters de procesadores. El objetivo de estos protocolos es reducir al máximo el coste (tiempo) de generación y recepción de los paquetes que transmite la red, para lo que se eliminan las copias en memoria del S.O. (protocolos de 0 copias) y se gestiona la generación y la recepción de paquetes de manera muy eficiente. Dos de las alternativas más conocidas son VIA (Virtual Interface Architecture) e InfiniBand. Las redes comerciales estándar suelen traer implementados de forma nativa (más rápido) estos protocolos o los soportan mediante emulación (más lento). Además de ello, en otros casos Myrinet, por ejemplo se utilizan protocolos de comunicación propios (GM).

Aunque hay un poco de todo, aparte de las redes de diseño específico (propias de los sistemas MPP de alta gama), las redes más utilizadas en los clusters son Gigabit Ethernet por un lado, barata pero de no muy alto rendimiento (por ejemplo, la latencia de paquetes pequeños con MPI anda en torno a los 50 μs o más), e InfiniBand y Myrinet por otro (más rápidas que la primera, pero también más caras). InfiniBand es una infraestructura y protocolo de comunicaciones de alto rendimiento; la figura representa un nodo general de un sistema paralelo que utiliza InfiniBand.



Los elementos que forman el nodo pueden ser muy variados: en el caso más simple, un solo procesador, y en el más complejo, uno o varios sistemas paralelos (SMP), sitios específicos de entrada/salida o de almacenamiento masivo de datos (RAID), etc. La comunicación entre los elementos que forman el nodo se realiza mediante conmutadores, mientras que la comunicación entre no se realiza mediante encaminadores de mensajes.

Myrinet es otro referente en las redes de alta velocidad. Los nodos se conectan a la red mediante un NIC (network interface card) de diseño específico que ejecutan el protocolo de comunicación (GM); así, el procesador del nodo solamente ejecutará "cálculo", y el de la tarjeta de comunicaciones se encargará de todo lo relacionado con la comunicación (además, el usuario puede programar las funciones de la tarjeta de comunicaciones, para adaptarla a necesidades concretas). En general, los nodos se conectan en una red de Clos (fat tree), tal como la de la figura (64 nodos). Los enlaces son de 10 + 10 Gb/s y la latencia de paquetes pequeños con MPI llega a estar por debajo de los 2 μs

Enlaces para el siguiente nivel del árbol



Red de Clos de 64 nodos (fat tree). Los conmutadores son de 8 + 8 puertos (enlaces bidireccionales).

11. APLICACIONES

• Industriales• Química y bioingeniería.

• Estudio de estructuras moleculares, simulación de reacciones, espectroscopía.• Mecánica Industrial

• Diseño asistido. Modelos de elementos finitos.• Medicina

• Estudio del genoma, medicina farmacéutica, radioterapia.

• Comerciales• Telecomunicaciones

• Análisis de tráfico, desempeño y calidad de servicio• Redes de control inteligentes

• Servicios web.• Buscadores paralelos (metabuscadores).

• Sistemas de tiempo real.• Bases de datos paralelas.• Análisis de datos.

• Data mining.• Análisis de mercado, series temporales, etc

12. Tendencia en las redes de comunicación



La arquitectura de los sistemas paralelos más rápidos ha sufrido importantes cambios en los últimos años. De los 500 computadores más rápidos

• 81% son de tipo cluster • 19% restante son MPP

Las redes más utilizadas son:• Infiniband (42%) • Gigabit/10G Ethernet (41%)• 3,2% redes de diseño específico (proprietary)• 9% de tipo custom.


Tera = 1012 Peta = 1015 Flop/s = operaciones de coma flotante / s *a 1 operación por seg. ≫ 16,3 x 1015 s = 516,5 millones de años = 3,8% de la edad del universo

1993≫2012: La velocidad de cálculo es 270 000 veces mayor (un año de ejecución se ha reducido a 2 minutos); el rendimiento por núcleo es 173 veces mayor, y la máquina tiene 1536 veces más núcleos.


La supercomputadora paralela Sequoia, Blue Gene/Q de IBM.

Arquitectura de Blue Gene/Q



13. CONCLUSIONES

Durante las últimas décadas el desarrollo de las computadoras han venido evolucionando de manera muy rápida, a tal punto que se han venido creando nuevas formas de comunicación, que cada vez son más aceptadas por el mundo actual.

En este trabajo se pudo obtener información sobre las diferentes formas de Redes, entre otros aspectos que en la actualidad son muy utilizados no tan solo en el medio de las computadoras sino en el mundo de las telecomunicaciones que de una forma u otra han facilitado nuestras formas de vida no solamente en el aspecto profesional; facilitándonos nuestros trabajos, sino en el aspecto cultural , ya que gracias a estos podemos enriquecer nuestra cultura permitiéndonos evolucionar cada vez más.

Además de permitir la comunicación no solo desde un mismo salón sino alrededor del mundo, es decir, que no es estrictamente necesario tener dos o más computadoras cercas para comunicarse y acceder a la información que estas posean estas pueden estar en punto distantes el uno del otro y se tiene la misma comunicación y la accesibilidad a la información deseada.

La computación paralela se ha convertido en la corriente principal. Empezamos con una larga serie de conferencias sobre la computación paralela. Parecía que la gente quería saber sobre este tema, pero sobrevino que la computación paralela asusto a la gente.

La más importante razón de peso para rechazar la computación paralela fue que es más fácil y más barato comprar otra máquina, que hacer el mejor de los núcleos del CPU. Esta fue una realidad que impulso la computación de la nube (Cloud Computing).

Los algoritmos y chips DSP son evaluados en MIPS que es la cantidad de instrucciones por constante de tiempo. El aumento del rendimiento por medio de algoritmos significa que usa menos instrucciones o se han agregado más núcleos al CPU. Las PCs también ejecutan algoritmos tales como reconocimiento de rostros, detección de imágenes, filtrado de imágenes, detección de movimiento, y mucho más. La transición desde un único núcleo a multi-núcleo fue rápida y simple.




Documents

Sistemas-De-Comunicación-En-Computadores-Paralelos-2.docx