Unidad 1 - Paralelismo y Arquitecturas Paralelas

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Paralelismo y 
Arquitecturas
Paralelas
Unidad 1
Carreras:
• Lic. en Sistemas
• Ing. Informática
Ing. Carlos A. Afranllie
Paralelismo
¿Qué es Paralelismo?:
“Una estrategia para ejecutar grandes tareas complejas, de forma 
más rápida”.
Una tarea grande puede ser ejecutada serialmente (un paso seguido 
de otro) o puede descomponerse en tareas más pequeñas para ser 
ejecutadas simultáneamente, es decir, en paralelo. El paralelismo es 
hecho:
• Descomponiendo las tareas en tareas más pequeñas
• Asignando las tareas más pequeñas a múltiples trabajadores 
para trabajar simultáneamente 
• Coordinando los trabajadores
Paralelismo
Paralelismo
Paralelismo
Paralelismo
Paralelismo Distribuido
Paralelismo Distribuido
Paralelismo Distribuido
Paralelismo
¿Por qué Paralelizar?:
Existen diferentes clases de problemas que requieren un 
procesamiento más rápido:
• Problemas de simulación y modelaje: 
o Basados en aproximaciones sucesivas 
o Más cálculo, más precisión 
• Problemas dependientes de los cálculos y manipulación de 
grandes cantidades de datos:
o Procesamiento de señal e imágenes 
o Renderingde imágenes 
o Base de datos 
Paralelismo
¿Por qué Paralelizar?:
Paralelismo
¿Por qué Paralelizar?:
• El desempeño de las computadoras determina la clase 
de problemas que se pueden resolver. 
• Existen problemas tan complejos, que su solución 
podría tomar muchos años.
• Algunas áreas con fuerte demanda por la computación 
de alto desempeño son: química molecular (industria 
farmacéutica), astrofísica, biología genética, predicción 
del tiempo, modelos ambientales, etc…
Paralelismo
Definiciones Básicas:
• El paralelismo esta implícito en la mayoría de 
los procesadores modernos y los sistemas 
operativos.
• En otras palabras, toda computadora moderna 
tiene algún grado de paralelismo, pero no toda 
computadora la llamamos computadora 
paralela porque la concurrencia en estas 
maquinas está oculta al programador.
Paralelismo
Definiciones Básicas:
• Procesamiento paralelo
Es el procesamiento de información que enfatiza el 
manejo concurrente de conjuntos de datos por 
varios procesadores con el objetivo de resolver un 
solo problema.
•Computadora paralela
Es una computadora formada por varios procesadores 
capaz de realizar procesamiento paralelo.
Paralelismo
Fuentes de Paralelismo:
• Todas las aplicaciones no presentan el mismo perfil de cara al 
paralelismo.
• Es necesario considerar el factor cualitativo: ¿Qué manera se 
utiliza para explotar el paralelismo?
• Cada técnica de explotación del paralelismo se denomina 
fuente, estas son:
o Paralelismo de Control.
o Paralelismo de Datos.
o Paralelismo de Flujo.
Fuentes de Paralelismo
Paralelismo de Control:
• Constatación natural: en una aplicación existen acciones que 
podemos hacer simultáneamente.
• Las acciones pueden ejecutarse de manera más o menos 
independiente sobre unos recursos de cálculos.
• Caso ideal: N acciones independientes se ejecutarán N veces más 
rápido sobre N elementos de proceso que sobre uno solo.
• Caso Real: acciones dependientes. Existen dos clases de 
dependencia:
o Dependencia de Control de Secuencia.
o Dependencia de Control de Comunicación.
Paralelismo de Control
Paralelismo de Control
Figura 2: Ejemplo de paralelismo de control
Fuentes de Paralelismo
Paralelismo de Datos:
• Constatación natural: ciertas aplicaciones trabajan con estructuras de datos 
muy regulares (vectores, matrices) repitiendo una misma acción sobre cada 
elemento de la estructura.
• Los recursos de cálculo se asocian a los datos.
• Centralización de control.
• Limitaciones:
o Necesidad de dividir datos vectoriales para adecuarlos al tamaño 
soportado por la máquina.
o La existencia de datos escalares que limitan el rendimiento.
o La existencia de operaciones de difusión (un escalar se reproduce varias 
veces convirtiéndose en un vector) y β-reducciones que no son 
paralelas.
Paralelismo de Datos
Paralelismo de Datos
Figura 4: Ejemplo de aplicación del paralelismo de datos a un bucle
Fuentes de Paralelismo
Paralelismo de Flujo:
• Constatación natural: ciertas aplicaciones funcionan en modo cadena: 
flujo de datos (semejantes) ⇒ sucesión de operaciones en cascada.
• Los resultados de las acciones efectuadas en el instante t pasan en el 
instante t + 1 al PE siguiente.
• Segmentación o pipeline.
• El flujo de datos puede provenir de dos fuentes:
o Datos de tipo vectorial ubicados en memoria.
o Datos de tipo escalar provenientes de un dispositivo de entrada.
• Ganancia obtenida ⇒ Núm. de etapas (núm. de PE).
Paralelismo de Datos
Fuentes de Paralelismo
Segmentación (Pipelining):
La segmentación consiste en dividir la ejecución de una tarea en 
etapas. De esta manera, una tarea se completa cuando se han 
realizado todas las etapas en las que se subdivide de manera 
ordenada.
Cauce segmentado en el montaje de automóviles
Fuentes de Paralelismo
Segmentación (Pipelining):
• El pipelining es una técnica que permite aumentar el grado 
de concurrencia de un algoritmo.
• Un algoritmo pipelined se divide en un número de pasos, 
llamados Pipe Stages o segmentos (segmentación). Cada 
segmento trabaja a máxima velocidad en su etapa.
• La salida de un segmento corresponde a la entrada de otro 
segmento. Si todos los segmentos trabajan a la misma 
velocidad el ancho de banda del pipeline completo, es igual al 
ancho de banda de un segmento cuando el pipe está lleno.
Segmentación
Ejemplo:
• Cuatro mujeres que trabajan en una lavandería tienen ropa sucia para 
lavar.
• Deben realizar tres tareas: lavar, secar y planchar.
• Sólo existen una máquina de lavar, una de secar y una de planchar.
• El lavado demora 30 minutos, el secado 40 minutos y el planchado 20 
minutos.
• El lavado secuencial demora 6 horas.
• El lavado pipeline demora 3.5 horas.
Segmentación
Segmentación
Segmentación
Riesgos de la Segmentación:
• Riesgos por dependencia de datos: Se debe a que una 
instrucción depende del resultado de otra previa que todavía se 
encuentra en el cauce.
• Riesgos estructurales: Significa que el hardware no puede 
soportar la combinación de instrucciones que se quieren 
ejecutar en el mismo ciclo, por ejemplo dos instrucciones 
accediendo a la memoria.
• Riesgos de control: Se debe a la necesidad de tomar una 
decisión basada en los resultados de una instrucción mientras 
las otras se están ejecutando, por ejemplo un salto condicional.
Arquitecturas Paralelas
Arquitecturas Paralelas
Arquitecturas Paralelas
Clasificación de Flynn
Clasificación de Flynn
SISD (Single Instruction Single Data):
• Concepto serie de la arquitectura de Von Neumann, 
en un único procesador en cualquier momento solo se 
ejecuta una única instrucción.
• Posee el registro simple de contador de programa.
• Prácticamente hoy en día no se fabrican 
computadores puramente SISD, ya que la mayoría de 
los procesadores modernos incorporan algún tipo de 
paralelismo como la segmentación de instrucciones.
SISD
Clasificación de Flynn
MISD (Multiple Instruction Single Data):
• Varias instrucciones actúan sobre el mismo y único 
conjunto de datos.
• Se pueden tomar dos interpretaciones:
o Unidades diferentes reciben instrucciones distintas 
que operan sobre los mismos datos. Impracticable 
y no existen ejemplos con este modelo.
o Un mismo flujo de datos fluye a través de 
numerosas unidades de procesamiento (Arrays
Sistólicos, Procesadores Vectoriales).
MISD
Clasificación de Flynn
SIMD (Single Instruction Multiple Data):
• Una única instrucción es aplicada sobre diferentes datos al 
mismo tiempo (sincronismo).
• Poseen una única unidad de control.
• Soportan procesamiento Vectorial.
• Procesadores matriciales.
• Útil en aplicaciones uniformes. (Procesamiento de 
Imágenes, Multimedia, Aplicaciones Numéricas)
SIMD
Clasificación de Flynn
MIMD (Multiple Instruction Multiple Data):
• Son máquinas que poseen varios procesadores en las 
cuales
se pueden realizar múltiples instrucciones sobre 
datos diferentes de forma simultánea.
• Más Complejas, mayor eficiencia en ejecución 
concurrente.
• Se pueden ejecutar varios programas a la vez.
• Los procesadores pueden trabajar de forma semi-
autónoma (asíncronos).
MIMD
Clasificación de Flynn
Clasificación de Flynn de las arquitecturas de computadores. (UC=Unidad de Control, UP=Unidad de Procesamiento,
UM=Unidad de Memoria, EP=Elemento de Proceso, ML=Memoria Local, FI=Flujo de Instrucciones, FD=Flujo de datos.)
Otra Clasificación
Taxonomía de Tanenbaum
MIMD
Multiprocesadores:
• Conjunto de procesadores interconectados que 
pueden compartir un mismo sistema de memoria.
• Conocidos también como Sistemas de Memoria 
Compartida.
• Los procesadores se pueden configurar para que 
cada uno ejecute una parte de un programa o 
varios programas al mismo tiempo.
MIMD
UMA (Uniform Memory Access):
• La memoria física está uniformemente compartida por todos los 
procesadores.
• Cada procesador puede tener su caché privada, y los periféricos 
también son compartidos de alguna manera.
• Sistemas fuertemente acoplados.
• Multiprocesador simétrico y asimétrico.
• CC-UMA (Cache-Coherent Uniform Memory Access).
MIMD
MIMD
NUMA (Non-Uniform Memory Access):
• El tiempo de acceso a memoria varía según el lugar donde se encuentre 
localizado el acceso.
• Toda la memoria es compartida pero local a cada módulo procesador.
o Ventaja: Más rápido acceso a memoria local.
o Desventaja: Acceso a memoria no local más lento.
• Se busca que los accesos sean lo más locales posibles.
• Se puede añadir al sistema una memoria de acceso global.
• CC-NUMA: memoria compartida distribuida y directorios de caché.
MIMD
MIMD
COMA (Cache Only Memory Access):
• Sólo usa caché como memoria.
• Este modelo es un caso especial de NUMA: las memorias 
distribuidas se convierten en caché.
• Todas las cachés usan un mismo espacio global de direcciones.
• El acceso a las demás cachés se realiza a través de los directorios 
distribuidos de las cachés.
• La ubicación inicial de los datos no es relevante.
MIMD
MIMD
Multicomputadores:
• Se puede ver como un computador paralelo en el cual cada 
procesador tiene su propia memoria local.
• La memoria del sistema se encuentra distribuida entre todos los 
procesadores.
• Cada procesador sólo puede direccionar su memoria local.
• Para el acceso a otras memorias, el procesador debe hacerlo por 
paso de mensajes.
• La transferencia de datos se realiza a través de la red de 
interconexión.
• Llamados también Sistemas distribuidos o Sistemas débilmente 
acoplados.
MIMD
Máquinas de Flujo de datos:
• Hay dos maneras de procesar la información:
o Mediante la ejecución en serie de una lista de 
comandos: Arquitectura de Von Neumann.
o Mediante la ejecución de un comando demandado 
por los datos disponibles.
• Las instrucciones se ejecutan en el momento que 
tienen los datos necesarios para hacerlo.
MIMD
Máquinas de Flujo de datos:
• Se evita la ejecución de instrucciones basadas 
en contador de programa.
• Las instrucciones en un flujo de datos son 
puramente autocontenidas.
• La ejecución de una instrucción no afecta a 
otras que estén listas para ejecutarse.
MIMD
MIMD
Procesadores Matriciales:
• Consiste en un conjunto de elementos de proceso y un 
procesador escalar que operan bajo una unidad de control.
• La instrucción que ejecutan los nodos procesadores es la misma 
simultáneamente.
• Los datos serán los de cada procesador.
• Se requiere un único programa para controlar todas las 
unidades de proceso.
• Paralelización de los datos de un problema.
• Tipos de datos altamente particionables: Vectores y Matrices.
MIMD
Procesadores Vectoriales y Arrays Sistólicos:
• Procesadores Vectoriales:
o Ejecuta de forma segmentada instrucciones sobre vectores.
• Arrays Sistólicos:
o Gran número de elementos de proceso EPs idéenticos con 
una limitada memoria local.
o Los EPs están en forma de matriz (arrays). Sólo están 
permitidas las conexiones con los EPs vecinos.
o Los datos fluyen de unos EPs a sus vecinos a cada ciclo de 
reloj. Durante este ciclo de reloj los EPs realizan una 
operación sencilla.
MIMD
Arquitecturas Híbridas:
• El mayor beneficio en paralelismo se consigue con 
la paralelización de datos.
• En algunos casos la paralelización de datos no se 
puede conseguir en su totalidad, y es necesario 
utilizar además de éste, el paralelismo de control.
• Procesadores con características MIMD y SIMD (o 
MISD).
MIMD
Arquitecturas Específicas:
• Llevan consigo la elaboración de circuitos integrados 
específicos.
• Las ANN (Artificial Neuronal Network):
• Elevado número de EP simples que se ejecutan en paralelo.
• Se utiliza para resolver problemas que pueden ser sencillos 
para los humanos pero para una máquina no: comprensión de 
lenguaje.
• Aprende a la fuerza de aplicarle patrones de comportamiento.
Noviembre 2012
Titan (Laboratorio Nacional de Oak Ridge, China).
Un sistema de procesador 560,640 con un rendimiento Linpack de
17,6 petaflop/s.
Es un sistema Cray XK7 que se basa en una combinación de GPU y
CPU tradicionales para convertirlo en el superordenador más potente
del mundo.
Cada uno de los 18,688 nodos de Titan contiene una GPU NVIDIA
Tesla K20 junto con un procesador de CPU AMD Opteron 6274 de 16
núcleos, lo que le da al sistema un rendimiento máximo de más de 27
petaflops.
Titán también tiene más de 700 terabytes de memoria.
Junio 2013 – Noviembre 2015
Tianhe-2 (Universidad Nacional de Tecnología de Defensa de China).
Rendimiento de 33,86 petaflop/s (cuatrillones de cálculos por
segundo) en el punto de referencia Linpack.
16.000 nodos informáticos, cada uno compuesto por dos procesadores
Intel Ivy Bridge Xeon y tres chips Xeon Phi, representa la instalación
más grande del mundo de chips Ivy Bridge y Xeon Phi, con un total de
3.120.000 núcleos.
Cada uno de los 16.000 nodos posee 88 gigabytes de memoria (64
utilizados por los procesadores Ivy Bridge y 8 gigabytes para cada uno
de los procesadores Xeon Phi).
La CPU total más la memoria del coprocesador es de 1375 TiB
(aproximadamente 1,34 PiB).
Junio 2016 – Noviembre 2017
TaihuLight (Centro Nacional de Investigación de Ingeniería y
Tecnología Informática Paralela, China).
93 petaflops representan un respetable 74 por ciento de rendimiento
del máximo rendimiento.
125 petaflops pico en toda la máquina
40.960 nodos
Más de 10 millones de núcleos
Junio 2018 – Noviembre 2019
Summit (IBM, Laboratorio Nacional Oak Ridge (ORNL) del
Departamento de Energía (DOE), EEUU)
Rendimiento de 122,3 petaflops en High Performance Linpack (HPL)
4356 nodos, cada uno equipado con dos CPU Power9 de 22 núcleos y
seis GPU NVIDIA Tesla V100.
La memoria alcanza los 2.736 TB.
Los nodos están conectados entre sí con una red EDR InfiniBand de
doble carril Mellanox.
Junio 2020
Fugaku (Japón), funciona con el SoC A64FX de 48 núcleos de Fujitsu,
convirtiéndose en el primer sistema número uno en la lista que
funciona con procesadores ARM.
Sus 415 petaflops la hacen 2,8 veces más rápida que Summit.
Pico teórico de 513.855 TFlop/s.
7.299.072 núcleos y utiliza procesadores A64FX 48C a 2.2GHz.
La memoria es de 4.752 TB.