Unidad 4 - Multiprocesadores - 1ra Parte

Vista previa del material en texto

Multiprocesadores
Unidad 4:
Primera Parte
Ing. Carlos A. Afranllie
Introducción
Los uniprocesadores incorporaron soporte
hardware para explotar los diferentes niveles
de paralelismo y mejorar el rendimiento de
las aplicaciones:
• Paralelismo a nivel de instrucción (ILP)
• Paralelismo a nivel de datos (DLP)
• Paralelismo a nivel de threads (TLP)
Introducción
Los speedups alcanzados en estas aplicaciones no
han sido significativamente grandes, ya sea por
motivos tecnológicos o bien por las necesidades
concretas de las aplicaciones.
Se crean sistemas de computación más grandes
aprovechando la mejora tecnológica y combinando
múltiples uniprocesadores, los cuales pueden
aplicar o no la misma instrucción sobre múltiples
datos.
Introducción
A los sistemas que aplican una misma instrucción a
multiples datos se les llama computadores SIMD y,
en el caso que apliquen diferentes instrucciones a
los datos, reciben el nombre de MIMD.
Las máquinas SIMD dieron respuesta a
aplicaciones científicas y de ingeniería que
realizaban operaciones sobre estructuras muy
regulares, como pueden ser arrays o vectores.
Clasificación
• Arquitecturas paralelas SIMD
o Array processors
o Vector processors
• Multiprocesadores
o UMA
o NUMA 
o COMA 
• Multicomputadores
o MPP
o Clusters computers
Arquitecturas paralelas SIMD
Los computadores paralelos array processors y 
vector processors son los más conocidos. 
• Array Processors: Aplican una misma operación 
(instrucción) sobre una secuencia de datos, ya 
sea teniendo una serie de procesadores o 
unidades funcionales que operan a la vez.
• Vector processors: Una unidad funcional que 
opera secuencialmente sobre una secuencia de 
datos.
Arquitecturas paralelas SIMD
Array processors
• Consisten en un gran número de procesadores 
idénticos que realizan la misma secuencia de 
instrucciones en datos diferentes.
• Cada procesador, en paralelo con el resto de 
procesadores, realiza la misma instrucción sobre 
los datos que le toca procesar. 
• El primer array processor fue el computador 
ILLIAC IV de la Universidad de Illinois.
Array Processors
Arquitectura clásica de un Array Processors
Array Processors
Array Processors con Memoria Compartida
Array Processors
Array Processors con Memoria Distribuída
Arquitecturas paralelas SIMD
Vector processors
• Desde el punto de vista del programador, son lo 
mismo que los computadores array processors.
• El procesamiento de los datos no se hace en 
paralelo. 
• Los datos son procesados por una única unidad 
funcional muy segmentada. 
• La empresa que más vector processors ha 
realizado es Cray Research. 
• La primera máquina fue la Cray-1.
Vector Processors
Diagrama de bloque de un Vector Processors
Vector Processors
Arquitectura de un Vector Processors
Arquitecturas Paralelas MIMD
Computadores MIMD son múltiples procesadores 
que no necesariamente tienen que realizar la 
misma instrucción u operación sobre los datos. 
• Memoria compartida
o Multiprocesadores (fuertemente acoplados)
• Memoria distribuida
o Multicomputadores (débilmente acoplados)
Multiprocesadores
Los multiprocesadores más conocidos 
son los llamados symetric
multiprocessors o SMP, que se 
caracterizan por ser todos los 
procesadores del mismo tipo y poder 
acceder de la misma forma a los 
sistemas de memoria y entrada/salida.
Multiprocesadores
• Los multiprocesadores tienen un espacio virtual 
de direcciones de memoria común. 
• Pueden acceder a cualquier posición de la 
memoria. 
• Se pueden comunicar simplemente a través de 
variables compartidas, facilitando así la 
programación. 
Multiprocesadores
Multiprocesador de memoria compartida sin caché (izquierda) y con caché (derecha).
Multiprocesadores
Clasificación
Las arquitecturas multiprocesador pueden clasificarse 
según la estrategia de distribución de la memoria 
compartida, siempre con un único mapa de memoria:
• UMA (o SMP): Uniform Memory Access (o Symetric
MultiProcessor)
• NUMA: Non Uniform Memory Access
• COMA: Cache Only Memory Architecture
Características:
• Memoria física uniformemente compartida por 
todos los procesadores.
• Cada procesador puede emplear una caché 
privada.
• Todos los procesadores son similares y tienen 
capacidades equivalentes.
UMA (SMP)
Características:
• Todos los procesadores comparten la misma memoria y 
el mismo espacio de direccionamiento de la misma forma 
en que un monoprocesador accede a su memoria.
• Todos los procesadores presentan el mismo tiempo de 
acceso a todas las palabras de memoria.
• Modelo de programación basado en variables 
compartidas, aunque es posible simular paso de mensajes.
UMA (SMP)
Características:
• Mecanismos de sincronización para el acceso a recursos 
comunes.
• Los periféricos se comparten de la misma manera. 
• El principal problema de estos sistemas es la coherencia 
de la memoria cache.
UMA (SMP)
UMA (SMP)
Multiprocesador de memoria compartida a través de un bus
UMA (SMP)
Multiprocesador de memoria compartida a través de un bus
UMA (SMP)
Ejemplo:
Características:
• Tiempo de acceso depende de la ubicación de la palabra 
de memoria. 
• Utiliza (al igual que el SMP) un único espacio de 
direcciones, pero en este caso cada procesador es dueño 
de una parte de la memoria, a la cual puede acceder más 
rápido (memorias locales).
• Utiliza pasaje de mensajes escondido.
NUMA
Características:
• El sistema operativo (más sofisticado) puede ayudar 
mediante migración de páginas.
• El problema de coherencia es más complicado.
• Coherencia caché con directorios distribuidos.
• Sin coherencia de cache, es un multicomputador.
NUMA
NUMA
Multiprocesador NUMA de memoria compartida
NUMA
Ejemplo:
Características:
• Caso especial del NUMA.
• Cada procesador tiene una parte de la memoria principal 
que se convierte en caché.
• El espacio de memoria completo es la suma de las 
caches.
• No existe una jerarquía de memoria en cada procesador.
•Utilizan un mecanismo de directorio distribuido.
COMA
COMA
Ejemplo:
• Basadas en bus (son las más fáciles de 
implementar pero tienen el problema de la 
contención en los accesos a memoria).
• Basadas en una red de interconexión de tipo 
crossbar (evitan la contención, pero son muy 
costosas).
• Basadas en redes multistage (solución 
intermedia, menos contención que las basadas en 
bus, y menos costosas que las crossbar).
Conexiones típicas a memoria
Basadas en bus:
• Formado por un conjunto de conductores para la transacción 
de datos entre procesadores, módulos de memoria, y 
dispositivos periféricos conectados al bus.
• En el bus sólo puede haber una transacción a un tiempo 
entre una fuente (master) y uno o varios destinos (workers).
• En el caso de que varios masters quieran realizar 
transacciones, la lógica de arbitraje del bus debe decidir quien 
será el siguiente que consiga el bus y realice la transacción (se 
les llama buses de contención o buses de tiempo compartido).
Conexiones típicas a memoria
Basadas en bus:
• En la mayoría de los casos se realiza sobre una placa de 
circuito impreso. Las tarjetas con los procesadores, 
memorias, etc. se conectan a este circuito impreso o placa 
madre a través de conectores o cables.
• Bajo costo comparado con otros sistemas de conexión y 
facilidad de diseño.
• Su uso está muy extendido en la industria y existen 
varios estándares del IEEE disponibles.
Conexiones típicas a memoria
Basadas en bus:
• El multiprocesador basado en bus es uno de los sistemas 
multiprocesador más utilizados en computadores de 
prestaciones medias.
• El principal problema es su baja escalabilidad lo que no 
permite tener sistemas con muchos procesadores de forma 
eficiente.
• Dependiendo del ancho de banda del bus y de los requisitos 
de los procesadores que incorpora, un bus puede albergar 
entre 4 y 16 procesadores de forma eficiente.
Conexiones típicas a memoria
Basadas en bus:
• Por encima de estos números máximos, quedependen 
del procesador y el bus, el canal de conexión, en este caso 
el bus, se convierte en el cuello de botella del sistema.
• En sistemas más complejos se sigue utilizando el bus, de 
manera que para aumentar la escalabilidad del sistema se 
disponen varios buses formando una jerarquía, o bien, se 
interconectan varios buses entre sí a través de una red.
Conexiones típicas a memoria
Conexiones típicas a memoria
Multiprocesador de memoria compartida a través de un bus (datos, dirección y control)
Basadas en bus:
Conexiones típicas a memoria
Multiprocesador memoria compartida a través de bus (datos, dirección y control), con caché.
Basadas en bus:
Conexiones típicas a memoria
Una red con bus único (M = Memoria; P = Procesador)
Basadas en bus:
Conexiones típicas a memoria
Redes Híbridas: a) Una red multibus – b) Una jerarquía de dos niveles de buses.
Basadas en bus (híbridas):
Basadas en crossbar:
• El mayor ancho de banda y capacidad de interconexión 
se consigue con la red de barra cruzada.
• Una red de barra cruzada se puede visualizar como una 
red de una sola etapa de conmutación. 
• Los conmutadores de cada cruce dan las conexiones 
dinámicas entre cada par destino-fuente, es decir, cada 
conmutador de cruce puede ofrecer un camino de 
conexión dedicado entre un par.
Conexiones típicas a memoria
Basadas en crossbar:
• En una barra cruzada genérica de conmutadores, 
los elementos V (vertical) y H (horizontal) pueden 
ser indistintamente procesadores, memorias, etc.
• Por ejemplo son típicas las configuraciones de 
procesador con memoria compartida, donde los 
módulos verticales son todo procesadores y los 
horizontales memorias, o al revés.
Conexiones típicas a memoria
Basadas en crossbar:
Conexiones típicas a memoria
Basadas en crossbar:
• Las redes de barras cruzadas (crossbar) permiten que cualquier 
procesador del sistema se conecte con cualquier otro procesador o 
unidad de memoria de tal manera que muchos procesadores 
pueden comunicarse simultáneamente sin contención.
• Es posible establecer una nueva conexión en cualquier momento 
siempre que los puertos de entrada y salida solicitados estén libres.
• Las redes de crossbar se usan en el diseño de multiprocesadores 
de pequeña escala pero alto rendimiento, en el diseño de routers
para redes directas, y como componentes básicos en el diseño de 
redes indirectas de gran escala.
Conexiones típicas a memoria
Basadas en crossbar:
Conexiones típicas a memoria
Multiprocesador de memoria compartida a través de un crossbar, 
enseñando los dos modos en los que se puede encontrar un switch
Basadas en crossbar:
Para una red de barras cruzadas con control distribuido, cada punto 
de conmutación puede estar en uno de los cuatro estados 
siguientes: 
Conexiones típicas a memoria
Basadas en crossbar:
En la figura (a), la entrada de la fila en la que se encuentra el punto 
de conmutación tiene acceso a la correspondiente salida mientras 
que las entradas de las filas superiores que solicitaban la misma 
salida están bloqueadas. 
Conexiones típicas a memoria
Basadas en crossbar:
En la figura (b), a una entrada de una fila superior se le ha permitido 
el acceso a la salida. La entrada de la fila en la que se encuentra el 
punto de conmutación no ha solicitado dicha salida, y puede ser 
propagada a otros conmutadores. 
Conexiones típicas a memoria
Basadas en crossbar:
En la figura (c), una entrada de una fila superior tiene acceso a la 
salida. Sin embargo, la entrada de la columna en la que se encuentra 
en punto de conmutación también ha solicitado esa salida y está 
bloqueada. 
Conexiones típicas a memoria
Basadas en crossbar:
La configuración de la figura (d) sólo es necesaria si el crossbar tiene 
soporte para comunicaciones multicast (uno a muchos).
Conexiones típicas a memoria
Basadas en Multistage (MIN)
• Las MIN (Multistage Interconnection Networks) se han 
utilizado tanto en máquinas MIMD como SIMD. 
• Las redes de interconexión multietapa (MINs) conectan 
dispositivos de entrada a dispositivos de salida a través de un 
conjunto de etapas de conmutadores, donde cada conmutador 
es una red de barra cruzada. 
• El número de etapas y los patrones de conexión entre etapas 
determinan la capacidad de encaminamiento de las redes.
Conexiones típicas a memoria
Basadas en Multistage (MIN)
Red de interconexión multistage genérica de P procesadores de entrada y b bancos de 
memoria de salida.
Conexiones típicas a memoria
Basadas en Multistage (MIN)
• Las MINs fueron inicialmente propuestas por las compañías de 
teléfonos y posteriormente para los procesadores matriciales. En 
estos casos, un controlador central establece el camino entre la 
entrada y la salida. 
• En casos en donde el número de entradas es igual al número de 
salidas, cada entrada puede transmitir de manera síncrona un 
mensaje a una salida, y cada salida recibir un mensaje de 
exactamente una entrada.
• Estas redes pueden configurarse con un número de entradas mayor 
que el número de salidas (concentradores) y viceversa (expansores).
Conexiones típicas a memoria
Basadas en Multistage (MIN)
• La figura muestra una red multietapa generalizada. 
• Un número de axb conmutadores se usa en cada etapa.
• Entre etapas adyacentes se utiliza una red de interconexión fija.
• Los conmutadores pueden ser programados dinámicamente para 
establecer las conexiones deseadas entre las entradas y salidas.
Conexiones típicas a memoria
Clasificación de las Redes MIN
Dependiendo de la disponibilidad de caminos para 
establecer nuevas conexiones, las redes multietapa se han 
dividido tradicionalmente en tres clases:
• Bloqueantes
• No bloqueantes
• Reconfigurables
Conexiones típicas a memoria
Clasificación de las Redes MIN
• Bloqueantes: La conexión entre un par entrada/salida 
libre no siempre es posible debido a conflictos entre las 
conexiones existentes. Típicamente, existe un único 
camino entre cada par entrada/salida, lo que minimiza el 
numero de conmutadores y los estados. A estas redes 
bloqueantes también se les denominan multicamino.
Conexiones típicas a memoria
Clasificación de las Redes MIN
• No bloqueantes: Cualquier puerto de entrada puede 
conectarse a cualquier puerto de salida libre sin afectar a 
las conexiones ya existentes. Las redes no bloqueantes 
tienen la misma funcionalidad que un crossbar. Estar redes 
requieren que existan múltiples caminos entre cada 
entrada y salida, lo que lleva a etapas adicionales.
Conexiones típicas a memoria
Clasificación de las Redes MIN
• Reconfigurables: Cada puerto de entrada puede ser 
conectado a cada puerto de salida. Sin embargo, las 
conexiones existentes pueden requerir de un reajuste en 
sus caminos. Estas redes también necesitan de la 
existencia de múltiples caminos entre cada entrada y 
salida pero el numero de caminos y el costo es menor que 
en el caso de redes no bloqueantes.
Conexiones típicas a memoria
Clasificación de las Redes MIN
Dependiendo del tipo de canales y conmutadores, las 
redes multietapa pueden dividirse en dos clases:
• MINs unidireccionales: Los canales y conmutadores son 
unidireccionales.
• MINs bidireccionales: Los canales y conmutadores son 
bidireccionales. Esto implica que la información se puede 
transmitir simultáneamente en direcciones opuestas entre 
conmutadores vecinos.
Conexiones típicas a memoria
MINs unidireccionales:
• Los bloques básicos de construcción de una red multietapa
unidireccional son los conmutadores unidireccionales.
• Un conmutador axb es un crossbar con a entradas y b salidas.
• Si cada puerto de entrada puede conectarse a exactamente un puerto 
de salida, existirán min{a,b} conexiones simultáneas.
• Si cada puerto de entrada puede conectarse a varios puertos de 
salida, se necesita un diseño más complicado para soportar la 
comunicación multicast (uno a varios).
• En el modo de comunicación broadcast (uno a todos), cada puerto 
puede conectarse a todoslos puertos de salida.
Conexiones típicas a memoria
MINs unidireccionales:
La figura muestra los cuatro posibles estados de un conmutador 2x2. 
Los últimos dos estados se usan para soportar las comunicaciones 
uno a muchos y uno a todos.
Conexiones típicas a memoria
Cuatro posibles estados de un conmutador 2 x 2.
MINs bidireccionales:
• La figura ilustra un conmutador bidireccional en donde cada puerto está asociado a un 
par de canales unidireccionales en direcciones opuestas. Esto implica que la información 
entre conmutadores vecinos puede transmitirse simultáneamente en direcciones 
opuestas. 
• Un conmutador bidireccional soporta tres tipos de conexiones: hacia delante, hacia 
atrás y de vuelta.
• Dado que son posibles la conexiones de vuelta entre puertos del mismo lado del 
conmutador, los caminos tienen diferentes longitudes.
Conexiones típicas a memoria
MINs bidireccionales:
En la figura se muestra una MIN mariposa bidireccional de ocho 
nodos. 
Conexiones típicas a memoria
MINs bidireccionales:
La figura muestra dos caminos alternativos desde el nodo S al nodo D en una 
BMIN mariposa de ocho nodos. Cuando se cruzan las etapas hacia delante, existen 
varios caminos. En cada conmutador se puede seleccionar cualquiera de sus 
puertos de salida.
Conexiones típicas a memoria
Cuando varios procesadores acceden a un dato para 
escritura se nos plantea la pregunta siguiente: ¿en qué 
orden se deben ver estas escrituras por parte del resto de 
procesadores si éstos hacen una lectura de los datos de 
forma paralela?
Hay muchas respuestas posibles, ya que unos accesos se 
pueden adelantar a los otros, siendo el resultado de las 
lecturas impredecible. Todo esto se agrava cuando 
tenemos cachés, ya que entonces es posible que varios 
procesadores tengan copias de lecturas previas.
Consistencia de memoria
• Estos conflictos suceden sólo cuando la memoria 
es compartida. 
• Ante la escritura de un programa paralelo se 
quiere asegurar que una lectura devuelva el valor 
de una determinada escritura. Es decir, establecer 
un orden entre una escritura y una lectura.
• Normalmente se usa alguna forma de evento de 
sincronización para asegurar esta dependencia.
Consistencia de memoria
El acceso a la memoria compartida puede ser visto 
como un contrato entre el hardware y el software 
de memoria. 
Si el software acepta cumplir con ciertas reglas, la 
memoria conviene en entregar ciertos resultados. 
La discusión se centra en la naturaleza de las 
reglas. Estas reglas se denominan “modelos de 
consistencia”.
Consistencia de memoria
Modelo de Consistencia:
Un modelo de consistencia es el conjunto de 
normas que nos indica qué valores deberían ver los 
procesadores en sucesivas lecturas de una o varias 
posiciones de memoria.
“Un modelo de consistencia de memoria 
especifica cómo se resuelven los conflictos de 
acceso a la memoria”.
Consistencia de memoria
Ejemplo 1:
CPU-0 escribe ‘1’ en la posición X de la 
memoria.
luego…
CPU-1 escribe ‘2’ en la posición X.
luego...
CPU-2 lee la posición X y obtiene ‘1’
¿Algo falló? ¡Todo depende de lo que la memoria 
prometió en su contrato!
Consistencia de memoria
Ejemplo 2:
/* El valor inicial de A y flag es 0 */
P1 P2
A=1 while (flag = 0); /* bucle vacío */
flag=1 print A
En particular, estamos suponiendo que la escritura de A es visible para el procesador P2 
antes que la escritura a flag, y que la lectura de flag por P2 que hace que salgamos del 
bucle while se ha completado antes que la lectura de A. 
Esta ordenación entre los accesos de P1 y P2 no está garantizada por la coherencia, que, 
por ejemplo, únicamente requiere que el nuevo valor de A se haga visible al procesador P2, 
no necesariamente antes de que el nuevo valor de flag sea observado.
Consistencia de memoria
Modelos posibles:
A continuación detallaremos algunos de los 
modelos de consistencia conocidos:
• Consistencia estricta
• Consistencia secuencial
Consistencia de memoria
Consistencia estricta: 
"Cualquier lectura de cierta posición de memoria X 
devuelve el valor almacenado por la escritura más 
reciente realizada sobre X"
Hay que hacer notar que este modelo de consistencia no 
se puede implementar en ningún sistema real. 
Efectivamente, como la distancia entre los procesadores y 
la memoria no es nula, la señal que viaja entre el 
procesador que escribe y la memoria sufre un cierto 
retraso.
Consistencia de memoria
Si durante este retraso, en el cual la memoria no tiene 
aún el nuevo dato escrito, otro procesador decide leer, 
no va a leer el valor que se acaba de mandar a la 
memoria, que aún no ha llegado, sino el que hubiera 
anteriormente.
Por lo tanto, la única forma en la que se podría 
implementar este modelo es suponiendo que los datos 
viajan de forma instantánea (velocidad infinita), lo cual 
va en contra de la teoría general de relatividad.
Consistencia estricta
Consistencia secuencial:
En presencia de múltiples solicitudes de lectura y escritura, el 
hardware escoge (de forma no determinista) cierta 
intercalación de todas las solicitudes, pero todas las CPU 
perciben el mismo orden.
Un multiprocesador es secuencialmente consistente si el 
resultado de cualquier ejecución es la misma que si las 
operaciones de todos los procesadores se realizaran en algún 
orden secuencial, y las operaciones de cada procesador 
individual ocurren en esta secuencia en el orden especificado 
por el programa.
Consistencia de memoria
Ejemplo 1:
1. CPU-1 escribe 100 en posición X
2. 1 ns después: CPU-2 escribe 200 en X
3. 1 ns después: CPU-3 y CPU-4 leen dos veces posición X 
CPU 1 2 3 y 4
(X)100 (X)200 lee X, lee X 
(dos veces)
Consistencia secuencial
Secuencias posibles:
E100 E100 E200
E200 L3 = 100 L4 = 200
L3 = 200 E200 E100
L3 = 200 L4 = 200 L3 = 100
L4 = 200 L3 = 200 L4 = 100
L4 = 200 L4 = 200 L3 = 100
CPU 1 2 3 y 4
(X)100 (X)200 lee X, lee X 
(dos veces)
Consistencia secuencial
Secuencias posibles:
E100 E100 E200
E200 L3 = 100 L4 = 200
L3 = 200 E200 E100
L3 = 200 L4 = 200 L3 = 100
L4 = 200 L3 = 200 L4 = 100
L4 = 200 L4 = 200 L3 = 100
Pase lo que pase, una memoria secuencialmente 
consistente nunca permitirá que la CPU-3 obtenga 
(100,200) mientras la CPU-4 obtiene (200,100).
Consistencia de memoria
“No es importante en qué orden se emiten realmente las 
operaciones a la memoria o incluso cuándo se completan, lo 
que importa es que parezcan completarse en un orden que no 
viole la consistencia secuencial”
• Se garantiza que hay un solo ordenamiento global de todas 
las escrituras que todas las CPU ven igual.
• Cuando suceden varias cosas al mismo tiempo, existe un 
orden verdadero en el que ocurren, tal vez determinados por 
los tiempos y la casualidad, pero todos los procesadores 
observan este mismo orden.
Consistencia de memoria
Existen dos restricciones para la implementación de la 
consistencia secuencial. 
• La primera es que las operaciones de memoria de un 
proceso se hagan visibles en el orden del programa.
• El segundo requisito es que las operaciones 
aparezcan atómicas; es decir, que parezca que una 
operación se ha completado con respecto a todos los 
procesos antes que la siguiente operación en el orden 
total haya sido emitida. 
Consistencia de memoria
Condiciones suficientes para preservar la 
consistencia secuencial: 
1. Todo proceso emite las peticiones a la memoria en el orden 
especificado por el programa.
2. Después de emitir una operación de escritura, el proceso que 
la emitió espera ha que se haya realizado la escritura antes de 
emitir su siguiente operación.
3. Después de emitir una operación de lectura, el proceso que la 
emitió espera a que la lectura se haya completado, y también 
espera a que se complete la escritura que generó el valor 
devuelto por la lectura, antes de emitir su siguiente operación. 
Consistenciade memoria
Multiprocesadores
Continuará…