Unidad 5 - Multicomputadores

Vista previa del material en texto

Multicomputadores
Unidad 5:
Multicomputadores
Ing. Carlos A. Afranllie
• Multiprocesadores: Cada CPU tiene acceso a toda 
la memoria
o Diferentes tipos de configuraciones de la red 
(bus, conmutadores) para conectar CPUs con 
memorias
• Multicomputadores: Cada CPU tiene acceso 
únicamente a su memoria privada. 
o Diferentes tipos de red para conectar las 
distintas CPUs entre ellas (bus, conmutadores)
Multiprocesadores vs 
Multicomputadores
Multiprocesadores vs 
Multicomputadores
Desventajas de los Multiprocesadores:
1. Son necesarias técnicas de sincronización para 
controlar el acceso a las variables compartidas
2. La contención en la memoria puede reducir 
significativamente la velocidad del sistema.
3. No son fácilmente ampliables para acomodar un 
gran número de procesadores.
Multiprocesadores vs 
Multicomputadores
Multicomputadores
Introducción:
Los multicomputadores surgieron de la necesidad
de poder escalar en número de procesadores sin
un elevadísimo costo económico. Estos consisten
en un conjunto de procesadores y bancos de
memoria que se conectan a través de una red de
interconexión con una determinada topología de
red.
Multicomputadores
Introducción:
• La principal característica de los multicomputadores es
que los procesadores, al más bajo nivel, ya no pueden
compartir datos, sino que lo tienen que hacer por
medio de mensajes.
• Es por eso por lo que en este tipo de sistemas no hay
problemas de coherencia de caché ni de consistencia
de memoria. Aquí, la sincronización se hace explícita
con los mensajes.
Arquitectura básica de un Multicomputador
Multicomputadores
Características:
• Los multicomputadores se caracterizan por tener la 
memoria distribuida.
• Únicamente una memoria local por procesador 
eliminando toda la memoria compartida del sistema. 
• Cada procesador puede acceder a su memoria local, pero 
no a las memorias de otros procesadores.
• El código para cada procesador se carga en la memoria 
local al igual que cualquier dato que sea necesario.
Multicomputadores
Características:
• Los programas todavía están divididos en diferentes partes, 
como en el sistema de memoria compartida, y dichas partes 
todavía se ejecutan concurrentemente por procesadores 
individuales.
• Para acceder a un dato localizado en la memoria de otro 
procesador, éstos se tendrán que comunicar vía mensaje a 
través de la red de interconexión. 
• Los datos no están almacenados globalmente en el sistema; si 
más de un proceso necesita un dato, éste debe duplicarse y ser 
enviado a todos los procesadores peticionarios.
Multicomputadores
Características:
• Esto dificulta notablemente la programación de estos 
sistemas.
• La gran ventaja de que son mucho más económicos de 
montar que los multiprocesadores
• Se pueden construir conectando procesadores de carácter 
general a través de una red de interconexión estándar, sin 
necesidad de ser a medida. 
• Son más escalables.
Multicomputadores
Ventajas:
1. Escala mejor y soporta más nodos.
2. Se eliminan las construcciones de sincronización.
3. No está limitado por el ancho de banda de la memoria, sí por el de 
la red.
4. Puede utilizar redes estáticas no completamente conectadas.
Desventajas:
1. Programación con mensajes explícitos.
2. Tiempo de transición del mensaje.
3. Una copia del SO en cada computadora.
4. Difícil mover procesos entre computadoras.
Multicomputadores
Procesos:
“Un proceso consiste a menudo en un código secuencial, como el que se 
encontraría en una máquina de Von Neumann”
• Cada nodo ejecuta uno o más procesos.
• Se permite el paso de mensajes entre los distintos procesos de un 
procesador mediante el uso de canales internos.
• Los mensajes entre procesos pertenecientes a diferentes procesadores se 
pasan a través de canales externos usando los canales físicos de 
comunicación existentes entre los procesadores.
• El tamaño de un proceso viene determinado por el programador y puede 
describirse por su “granularidad”.
Multicomputadores
Granularidad:
Granularidad = Tiempo de cálculo _
Tiempo de comunicación
• Granularidad gruesa: cada proceso contiene un gran 
número de instrucciones secuenciales que tardan un 
tiempo sustancial en ejecutarse.
• Granularidad fina: un proceso puede tener unas pocas 
instrucciones, incluso una instrucción.
• Granularidad media: la granularidad media describe el 
terreno intermedio entre ambos extremos.
Multicomputadores
Granularidad:
• Al reducirse la granularidad, la sobrecarga de 
comunicación de los procesos suele aumentar. 
• Es particularmente deseable reducir la sobrecarga de 
comunicación debido a que el costo de la misma suele 
ser bastante alto. 
• Por ello, la granularidad empleada en este tipo de 
máquinas suele ser media o gruesa.
Multicomputadores
Redes de Interconexión:
• Las redes de interconexión permiten la comunicación 
de datos entre nodos (procesadores), o entre 
procesadores y memoria.
• Los procesadores y/o los bancos de memoria se 
conectarán a las entradas y salidas de la red de 
interconexión.
• Normalmente, la redes de interconexión están 
formadas por switches y links conectados los unos a 
los otros.
Multicomputadores
Clasificación:
Las redes de interconexión se pueden dividir en static o 
directas, y dynamic o indirectas.
• Directas: Las redes directas son aquellas en las que los 
nodos de procesamiento están conectados punto a punto 
vía links.
• Indirectas: En este caso los procesadores puede que no 
estén conectados punto a punto, y los links pueden 
conectar varios switches de tal forma que se pueda llegar 
a establecer diferentes caminos entre los nodos de 
procesamiento y entre los nodos y los bancos de memoria.
Redes de Interconexión
Redes de Interconexión
Ejemplos de una red de interconexión directa y otra de tipo 
indirecta, ambas formadas por 4 procesadores.
Redes Directas (Redes estáticas basadas en 
encaminador)
• Topologías estrictamente ortogonales
• Malla
o Malla 2-D (Intel Paragon)
o Malla 3-D (MIT J-Machine)
• Toros (n-cubo k-arios)
o Toro 1-D unidireccional o anillo (KSR forst-level ring)
o Toro 2-D bidireccional (Intel/CMU iWarp)
o Toro 2-D bidireccional (Cray T3D, Cray T3E)
• Hipercubo (Intel iPSC, nCUBE)
• Otras topologías directas: Árboles, Ciclos cubo-conectados, Red 
de Bruijn, Grafos en Estrella, etc.
Redes de Interconexión
Redes de Interconexión
Redes de Interconexión
Redes de Interconexión
Redes de Interconexión
Métricas de Análisis de la Red
• Latencia y ancho de banda de la red
• Grado (Fanout o Connectivity) de la red
• Diámetro de la red
• Bisection bandwidth
• Dimensionalidad
Redes de Interconexión
Latencia de la red
• La latencia de la red indica el tiempo que se necesita 
para realizar la comunicación de un solo dato de un 
procesador a otro. 
• La latencia de los mensajes en la red cobra importancia 
en aquellos programas que tienen que realizar un 
elevado número de mensajes pequeños.
Métricas de Análisis de la Red
Latencia de la red
Métricas de Análisis de la Red
Ancho de banda de la red
• El ancho de banda de la red es la cantidad de datos por 
unidad de tiempo que se puede mantener en la 
comunicación de un conjunto de datos. 
• La importancia del ancho de banda de una red es 
mayor en los programas que realizan un elevado 
número de mensajes grandes.
Métricas de Análisis de la Red
Grado (Fanout o Connectivity) de la red
• El número de conexiones en un nodo se llama el grado 
(matemáticamente), fanout o connectivity según los 
ingenieros. 
• El fanout puede indicarnos qué tolerancia a fallos tiene 
el procesador, ya que cuanto mayor sea el grado de un 
nodo más caminos posibles tendremos en el momento 
de enrutar la comunicación.
• Además, tener un grado elevado permite reducir la 
contención de la red en algunos caminos.
Métricas de Análisis de la Red
Diámetro de la red
• El diámetro es la distancia máxima entre dos nodos, 
siendo la distancia entre dos nodos el númerode links 
que tenemos que atravesar para ir de un nodo al otro. 
• El diámetro, por consiguiente, nos da una visión de 
cuánto nos costará el envío de un nodo a otro, ya que 
cada link que pasamos puede significar un pequeño 
coste de comunicación adicional.
Métricas de Análisis de la Red
Bisection bandwidth
• El bisection bandwidth nos da una medida de la cantidad 
de datos que se pueden enviar en las transmisiones sin 
tener contención en la red de interconexión. 
• Para calcular el bisection bandwidth se divide la red de 
interconnexión en dos partes, eliminando el mínimo 
número de links entre ambas partes, de tal forma que las 
dos partes tengan el mismo número de nodos. El número 
de links eliminados, multiplicado por el ancho de banda 
de cada uno de ellos, nos determina el bisection
bandwidth.
Métricas de Análisis de la Red
Bisection bandwidth
Métricas de Análisis de la Red
Dimensionalidad
• La dimensionalidad es la cantidad de opciones que se 
tienen para ir de un nodo a otro.
• Si de un nodo a otro no hay más que una posibilidad 
de camino, entonces se dice que es cero dimensional. 
Sin embargo, si podemos movernos hacia el este o 
hacia el oeste para ir a un determinado nodo, entonces 
diremos que es uno dimensional.
• Si podemos, además, ir hacia el norte o hacia el sur, 
diremos que es dos dimensional.
Métricas de Análisis de la Red
Comunicación
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)? 
Redes de Interconexión
Mensajes
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:
Comunicación
Mensajes
• 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.
Comunicación
Mensajes
• 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).
Comunicación
• Cada mensaje puede dividirse en paquetes de tamaño 
fijo. 
• Estos paquetes son a su vez divididos en unidades de 
control de flujo o flits. Debido a las restricciones de 
anchura del canal, puede ser necesario varios ciclos de 
canal para transferir un único flit.
• Un phit es la unidad de información que puede 
transferirse a través de un canal físico en un único paso o 
ciclo. 
Mensajes
Los flits representan unidades lógicas de información 
en contraposición con los phits que se corresponden 
a cantidades físicas, es decir, número de bits que 
pueden transferirse en paralelo en un único ciclo. 
La figura muestra N paquetes, 6 flits/paquete y 2 
phits/flit.
Mensajes
Construcción del camino
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:
• Conmutación de circuitos (circuit switching)
• Conmutación de paquetes (packet switching)
Comunicación
Conmutación de circuitos
Esta técnica está basada en la telefonía fija.
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.
Esta trama de sondeo del encaminamiento contiene la 
dirección del destino e información de control adicional.
Construcción del camino
Conmutación de paquetes
Para efectuar la comunicación 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
Construcción del camino
Elección del camino
• 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.
• Aunque el registro de encaminamiento esté 
perfectamente definido, el camino entre origen y 
destino no es único, y, en general, dispondremos de 
muchas alternativas.
• ¿Qué camino hay que seguir?¿Hay que seguir siempre 
el mismo camino?
Redes de Interconexión
Encaminamiento estático
• El encaminamiento de los paquetes es estático si 
todos los paquetes que van del nodo i al nodo j 
utilizan siempre el mismo camino, sea cual sea la 
situación de tráfico en la red.
• 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.
Elección del camino
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.
Elección del camino
Encaminamiento dinámico o adaptativo
Elección del camino
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.
Elección del camino
Encaminamiento no mínimo
Elección del camino
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
Redes de Interconexión
Avance de los paquetes: SF, WH, CT
¿Cómo se transmite un paquete de encaminador a encaminador?
Generalmente los paquetes que hay que transmitir van a ser
bastante largos, por lo que se necesitan varios ciclos de
transmisión para pasar todo el paquete (todos los flits o bytes)
de un encaminador al siguiente.
¿Qué hay que hacer con un paquete que se está recibiendo?
Veamos las dos alternativas principales: store-and-forward y
wormhole / cut-through.
Control de flujo de la información
Store-and-forward (SF)
• Es el nombre de la técnica empleada en la primera 
generación de multicomputadores para pasar los paquetes 
entre dos encaminadores sucesivos.
• El encaminador que recibe el paquete no hace nada hasta 
que no lo termina de recibir todo. A continuación, analiza 
la cabeceradel paquete y decide por dónde debe 
retransmitirlo. 
• La transmisión de los paquetes se limita siempre a dos 
encaminadores: el que transmite y el que recibe. 
Control del flujo de la información
Store-and-forward (SF)
Control del flujo de la información
Arquitectura de un encaminador genérico (router)
Control del flujo de la información
Wormhole (WH) / Cut-through (CT)
• Cuando un encaminador recibe el primer flit de la 
cabecera de un paquete 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.
Control del flujo de la información
Wormhole (WH) / Cut-through (CT)
Control del flujo de la información
Wormhole (WH) / Cut-through (CT)
• 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:
Control del flujo de la información
Wormhole (WH)
• 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. 
• El paquete que se ha parado va a mantener ocupados 
muchos recursos de la red, por lo que es posible que 
aumenten los conflictos entre paquetes.
Control del flujo de la información
Wormhole (WH)
Control del flujo de la información
Cut-through (CT)
• 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.
Control del flujo de la información
Cut-through (CT)
Control del flujo de la información
Wormhole (WH) / Cut-through (CT)
• 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).
Control del flujo de la información
Las técnicas de comunicación anteriores fueron descritas 
suponiendo que los mensajes o parte de los mensajes se 
almacenan a la entrada y salida de cada canal físico. Por lo tanto, 
una vez que un mensaje ocupa el buffer asociado a un canal, 
ningún otro mensaje pueda acceder al canal físico, incluso en el 
caso de que el mensaje esté bloqueado.
Sin embargo, un canal físico puede soportar varios canales 
virtuales o lógicos multiplexados sobre el mismo canal físico. Cada 
canal virtual unidireccional se obtiene mediante el manejo 
independiente de un par de buffers de mensajes como se muestra 
en la figura siguiente: 
Control del flujo de la información
Canales Virtuales:
Canales Virtuales:
Control del flujo de la información
Un ejemplo de la reducción del retraso de la cabecera
usando dos canales virtuales por canal físico.
Control del flujo de la información
Canales Virtuales:
Multicomputadores
Fin Unidad 5