paralelismo avanzado Flashcards
Taxonom´ıa de Flynn
forma de categorizar las arquitecturas
paralelas la cual define cuatro categor´ıas de
paralelismo seg´un si se utiliza uno o m´ultiples streams de instrucciones (i.e. programas) y uno o
m´ultiples streams de datos.
SISD, paralelismo
dentro de un procesador sobre un programa, MIMD, paralelismo de m´ultiples procesadores
sobre m´ultiples programas, y SIMD, paralelismo que puede ser en uno o m´ultiples procesadores,
y que realiza un mismo procesamiento sobre un conjunto de datos
Paralelismo SISD
- Un procesador que permite obtener, decodificar y ejecutar m´ultiples instrucciones al mismo
tiempo se conoce como multiple-issue.
tipo de tecnicas de multiple issue
Las t´ecnicas est´aticas se basan en que el
compilador sea capaz de agrupar los conjuntos de instrucciones paralelizables y envi´arselas en conjunto
al procesador.
Las t´ecnicas din´amicas se basan en que el procesador sea capaz de determinar
en tiempo de ejecuci´on que instrucciones paralelizar, pudiendo despachar instrucciones a distintas
unidades de ejecuci´on din´amicamente
Arquitectura Superescalar.
t´ecnicas din´amicas. En este tipo de arquitecturas, antes de cada unidad de ejecuci´on se agrega una estaci´on de
reserva o reservation station la cual ser´a encargada de ir almacenando los operandos necesarios
para una determinada operaci´on, reserv´andolos hasta que est´en todos y solo en ese momento se
enviar´an a la unidad de ejecuci´on. Luego de que se ejecute la operaci´on, el resultado se almacena
temporalmente en una commit unit (tambi´en llamada reorder buffer) la cual se encargar´a de enviar
los datos a memoria o a los registros s´olo cuando haya seguridad de que no h´abr´an problemas
de dependencia de datos
very long instruction word
t´ecnicas est´aticas, la m´as utilizada se conoce como Very Long Instruction
Word (VLIW), la cual consiste en que el compilador agrupe un paquete o bundle de instrucciones
juntas, las cuales pueden ejecutarse en paralelo, y env´ıe al procesador este bundle como una
✭✭instrucci´on muy larga✮✮ que el procesador directamente envi´e a distintas unidades de ejecuci´on en
paralelo. Para lograr esto, el compilador puede implementar t´ecnicas de code motion, es decir,
reordenar el c´odigo de manera de permitir paralelizar instrucciones que no tienen dependencia de
datos, pero sin perder la l´ogica original del algoritmo
Instruction Level Parallelism (ILP)
mide a nivel de
las instrucciones del programa que tan paralelizable es un cierto c´odigo. La idea de esta m´etrica
es determinar que tanto m´as r´apido se puede ejecutar un c´odigo si se pudiera paralelizar lo m´as
posible.
Paralelismo MIMD
trabajar con m´ultiples procesadores simples, repartiendo el procesamiento
de m´ultiples programas independientes entre ´estos, lo que se conoce como un sistema multiprocesador.
ventajas y desventajas SISD
procesador logra mejoras de desempe˜no, tiene el costo
asociado de aumentar la complejidad del procesador, lo que tambi´en repercute en el consumo de
energ´ıa de ´este
tipos de multiprocesador
multiprocesador por paso de mensaje y
multiprocesador de memoria compartida.
-En un multiprocesador por paso de mensaje, cada
procesador tiene una memoria y espacio de direccionamiento propio, y la comunicaci´on con los
dem´as procesadores se realiza a trav´es de alg´un sistema de red que los interconecte
-multiprocesadores de memoria compartida se caracterizan
por tener un nivel de memoria compartida entre los distintos procesadores (figura 11). Debido
a esto es m´as simple compartir informaci´on entre los distintos procesadores, ya que no se requiere
estar envi´andola a trav´es de la red, pero se generan problemas de sincronizaci´on, ya que se debe
evitar que ambos procesadores modifiquen un mismo dato de memoria al mismo tiempo
problema posible de multiprocesador de memoria compartida
a sincronizaci´on de dos procesadores ocurre por el hecho de que a
pesar de tener un nivel de memoria compartida, es probable que cada procesador tenga un cach´e no
compartido (figura 12), lo que puede generar problemas de coherencia de cach´e, ya que si un
procesador escribe un valor en su cach´e y esto no se le notifica al otro procesador, la informaci´on
sobre una misma variable puede quedar almacenada de manera inconsistente en el sistema.
metodo MSI multiprocesador memoria compartida
Un mecanismo para solucionar los problemas de coherencia de cach´e es el protocolo MSI. En
este sistema, cada bloque puede estar en uno de cuatro estados:
Modified: bloque distinto de memoria principal y no existe en otras caches.
Shared: bloque coincide con memoria principal y puede estar presente en otras caches.
Invalid: datos no son v´alidos
pasos metoo msi multiprocesador de memoria compartida
En un comienzo todos los bloques comienzan en estado Invalid.
Si un procesador realiza una lectura de un valor de memoria, y lo almacena en su cach´e, ese
bloque pasa a estar en estado Shared en el cach´e de ese procesador.
Luego de esto pueden ocurrir distintas alternativas:
• Si el mismo procesador escribe en ese bloque de cach´e, el estado del bloque pasa a
Modified.
• Si el segundo procesador lee esa direcci´on de memoria y lo almacena en su cach´e, ese
bloque pasa a estar en estado Shared en la cach´e del segundo procesador.
En caso de que el estado de bloque qued´o en Modified, si ahora el segundo procesador intenta
leer esa direcci´on de memoria, ocurrir´a un problema de coherencia. Para evitar esto,
el controlador de la cach´e con el bloque Modified, debe encargarse de hacer bus snooping,
es decir ✭✭espiar✮✮ el bus de direcciones, para determinar si hubo un acceso a la direcci´on de
memoria asociada al bloque Modified. En caso de detectar un acceso, el controlador le env´ıa
una se˜nal a la segunda cach´e, indicando que el segundo procesador debe esperar (stall), por
que si lee ahora habr´a problema de inconsistencia. En ese momento el controlador de la primera
cach´e pasa a escribir el bloque en la memoria principal compartida, para que cuando
el segundo procesador reintente el acceso, ahora el bloque ya no est´e modificado, sino que se
haya cambiado a estado Exclusive y no haya problemas de coherencia.
arquitectura multicore
arquitectura particular de multiprocesadores son las arquitecturas multicore, las cuales no
corresponde a un tipo de multiprocesador, sino a una tecnolog´ıa en la cual los distintos procesadores
del sistema est´an incorporados en el mismo chip. El gran atractivo de estas arquitecturas es que al
estar en el mismo chip la comunicaci´on entre los procesadores ser´a mucho m´as r´apida.
Paralelismo SIMD Single
Instruction Multiple Data
en muchas circunstancias se requiere
ejecutar la misma operaci´on sobre distintos datos, por lo que es posible implementar naturalmente
cierto grado de paralelismo en estos casos. Este paralelismo es particularmente importante para el
procesamiento de operaciones vectoriales, que por su naturaleza suelen requerir operaciones de tipo
SIMD: sumar un vector con otro, por ejemplo, corresponde a sumar (una instrucci´on) los distintos
pares de componentes de ambos vectores (m´ultiples datos)
