T.1 Introducción a la Programación Paralela

1.1 Conceptos básicos

¿Qué es la programación paralela?

La programación paralela se encarga de desarrollar programas capaces de realizar muchos cálculos simultáneamente. Estos problemas deben ser capaces de dividirse en subproblemas más pequeños, los cuales se resuelven simultáneamente, suponiendo que disponemos de hardware capaz de desarrollar cálculos en paralelo.

1.2 Evolución del paralelismo

Comienzos

El paralelismo ha estado presente desde los inicios de la computación. En el siglo XX, investigadores de IBM construyeron los primeros ordenadores paralelos comerciales. Sin embargo, la computación paralela se limitó a ciertos entornos científicos, utilizada principalmente para computación de alto rendimiento.

Historia

A principios del siglo XXI, el escalado de frecuencia se encontró con el ‘power wall’. Las empresas empezaron a diseñar procesadores con múltiples núcleos, cada uno capaz de ejecutar secuencias de instrucciones por separado.

1.3 Motivación en programación paralela

Programación

La programación paralela es mucho más compleja que la secuencial, ya que dividir un proceso en múltiples subprocesos puede ser una tarea muy compleja o imposible. Además, la depuración y la validación del código se complican, ya que aparecen nuevas fuentes de errores. Sin embargo, la programación paralela merece la pena por la reducción del tiempo de ejecución que produce.

Eficiencia

El paralelismo y la concurrencia son conceptos muy cercanos. Los programas paralelos usan hardware paralelo para poder ejecutar más rápido, tienen como objetivo mejorar la eficiencia. Por otro lado, los programas concurrentes pueden o no ejecutar varias instancias al mismo tiempo.

1.4 Transición al paralelismo

Antecedentes

Los programadores confiaban en los avances que estaba teniendo el hardware, pero se encontró una barrera de frecuencia en los 8,67 GHz, ya que los procesadores consumían mucha energía y producían mucho calor. La ‘Ley de Moore‘ se sigue cumpliendo hoy día, ya que cada 1,5-2 años se dobla el número de transistores que presenta un procesador. La solución que se encontró fue limitar la frecuencia y aumentar el número de núcleos.

1.5 Computadores paralelos

Actualidad

Hasta que se aplicó el paralelismo a los procesadores comerciales, esta tecnología solo era accesible para grandes organizaciones, era escasa y estaba muy vinculada a la arquitectura. Actualmente, todos los chips son paralelos. Se ha incrementado el mercado de la programación paralela y del uso de Computación de Alto Rendimiento (HPC). Esto ha provocado que aparezcan oportunidades de trabajo para nuevos desarrolladores.

Introducción y tipos

El paralelismo se manifiesta en múltiples niveles de granularidad:

• Nivel Bit: Se procesan múltiples bits en paralelo.
• Nivel de instrucción: Se ejecutan diferentes instrucciones del mismo proceso en paralelo.
• Nivel de tarea: Ejecutar distintas tareas en paralelo.

Podemos encontrar diferentes tipos de hardware paralelo:

• Procesadores multicore
• Multiprocesadores simétricos
• GPUs
• Field-Programmable Gate Arrays (FPGAs)
• Cluster de computadores

1.6 APOD

Conceptos básicos

APOD (Assess, Parallelize, Optimize, Deploy) es una metodología de construcción de aplicaciones paralelas. Está compuesta por 4 etapas: Evaluar, Paralelizar, Optimizar, Desplegar.

Evaluar

Se debe evaluar el código buscando una posible aceleración. Se debe identificar dónde se consume la mayor parte del tiempo y comprobar si es una parte significativa respecto al tiempo total. También se buscan posibles cuellos de botella. Este paso es fundamental en todos los pasos del APOD.

Profiles

Se deben confirmar las hipótesis de evaluación. Se usan conjuntos heterogéneos de datos, al igual que herramientas como gprof en GPU y el API de C para multicore. Se pueden usar temporizadores como (CudaEvent) y Nsight. Aunque el rendimiento se puede ver afectado cuando se ejecuta un profiling.

Escalado

Si 1 core = 10 seg, ¿2 core = 5 seg? Ley de Amdahl: Orientada a corto plazo. Ley de Gustafson: Orientada a largo plazo.

Paralelización

Se debe elegir el lenguaje en el que se va a programar. Esto es importante en base a la plataforma objetivo. Se recomienda el uso de librerías y de compiladores paralelizantes. La paralelización usa el lenguaje nativo de la plataforma objetivo.

Optimizar

Se debe medir el rendimiento de forma precisa. Se deben seguir las prácticas adecuadas: Elección de algoritmos, movimiento de datos, conocimiento del hardware.

Desplegar

No se deben hacer cambios radicales y al codificar se debe estar pensando siempre en los errores.

1.7 Paralelismo en CPU y GPUs

Características

• CPUs, multicore, núcleos complejos: Implantación en ISA x86, Ejecución fuera de orden, Hyperthreading.
• GPUs, núcleos muy simples: Implementación reducida del ISA, Ejecución en orden, Unidad de control compartida.

Las GPUs contienen un gran paralelismo de datos, donde múltiples hilos ejecutan el mismo programa sobre múltiples núcleos.

Diferencias CPU vs GPU

Presentan diferencias de filosofía del diseño. Las CPU están optimizadas para el código secuencial, con mucha memoria caché. Mientras que las GPU están optimizadas para la computación intensiva, presentan un gran número de operaciones aritméticas por segundo, donde un gran número de hilos se ejecutan al mismo tiempo.

• CPU: Diseño orientado a latencia. Cachés muy grandes, aceleran los accesos lentos a memoria principal. Presentan pocas ALUs pero muy potentes.
• GPU: Unidad de control pequeña, Cachés muy pequeños, ALUs con latencias altas, mayor eficiencia energética.

Resumen

Las GPUs están diseñadas para el cálculo intensivo numérico. Las GPUs y las CPUs no son iguales, pero eso no significa que sean incompatibles, de hecho, es usual usar ambas. Una computación híbrida recibe el nombre de ‘CUDA’.

T.2 Conceptos de la Programación Paralela

2.1 Concepto de programación paralela

Conceptos previos

• Proceso: Programa en ejecución. Desde el punto de vista del procesador es el conjunto de instrucciones a ejecutar.
• Hilo: Un proceso está compuesto por uno o más hilos. Estos se dividen el trabajo a realizar por el proceso. El programador es el responsable de crear los hilos y asignarles trabajo.

Definición

• Tradicionalmente: Uso de varios computadores trabajando juntos para resolver una tarea común. Cada computador se encarga de una porción del problema. Estos se pueden comunicar a través de la memoria o de la red de interconexión.
• Actualmente: Uso de varios procesadores trabajando juntos para resolver una tarea común. Estos pueden estar dentro del mismo ordenador, incluso dentro del mismo chip.

2.2 Paralelismo en los computadores monoprocesadores

• Procesador segmentado: Se segmenta el proceso en varias etapas: Carga, decodificación, ejecución, almacenamiento.
• Procesador supersegmentado: Cada una de las etapas se divide a su vez en etapas.
• Procesador superescalar: Lanzar varias instrucciones de forma simultánea.
• Multithreading: Se lanzan varios hilos de manera simultánea.

2.3 Paralelismo en los computadores multiprocesadores

Taxonomía o Clasificación de Flynn

• SISD (Single Instruction, Single Data): Modelo de Von-Neuman. Instrucciones de memoria al elemento de proceso de manera secuencial. Una única unidad de control.
• SIMD (Single Instruction, Multiple Data): La misma instrucción se ejecuta de manera síncrona en todos los elementos. Importante visión para el modelo GPU.
• MIMD (Multiple Instruction, Multiple Data): Instrucciones independientes o la misma ejecutada en diferentes elementos. Modelo ideado para los sistemas tolerantes a fallos.
• MISD (Multiple Instruction, Single Data): Elementos de procesos sin conexión entre sí. No hay colisión en la memoria ni la posibilidad de utilizar cachés entre los elementos de proceso.

Computación heterogénea

Es difícil de clasificar dentro de la taxonomía de Flynn. Presenta un elemento de proceso orientado a latencia y otro orientado a throughput.

2.4 Leyes de Amdahl y Gustafon. Rendimiento

Ley de Amdahl

Esta ley establece un límite superior de ganancia de velocidad. No todas las partes de un programa pueden ser ejecutadas en paralelo. Es una ley bastante pesimista que presenta problemas de tamaño fijo. En esta ley no todo es procesamiento y se requiere gestión de la memoria. Un aumento de los procesadores no implica un mayor rendimiento.

Ley de Gustafson

Es más optimista que la de Amdahl. Presenta un mayor volumen de cálculo donde crece la parte paralela.

Rendimiento de computadores paralelos

Unidades de medida

• MIPS (Millions of Instructions Per Second): Se pueden ejecutar instrucciones distintas. Entre distintos ISA puede haber instrucciones más potentes.
• MFLOPS (Millions of Floating-Point Operations Per Second)

Ciclos por instrucción

Un ciclo de instrucción (CPI) es igual al número de ciclos de reloj consumidos dividido por el número de instrucciones ejecutadas.

Tiempo de ejecución

Equivale al CPI multiplicado por el número de instrucciones multiplicado por (1/f).

SPEED-UP al añadir N procesadores

Equivale al T(1)/T(N).

Eficiencia

Es la ganancia de velocidad obtenida comparada con la ganancia esperada.

2.5 Arquitectura de la GPU

Modelo de hardware de CUDA

La GPU está formada por ‘N’ multiprocesadores, cada uno con ‘M’ cores. Presenta un paralelismo masivo. Computación heterogénea, ya que la GPU complementa a la CPU para la parte más intensiva en datos y operaciones.

Modelo de memoria de CUDA

Cada multiprocesador tiene su banco de registros, la memoria compartida y dos memorias solo de lectura: una de texturas y otra constante. La memoria global es la memoria de vídeo dentro de la tarjeta. Es más lenta que las anteriores, pero presenta una mayor capacidad.

• Memoria de vídeo: Tiene un gran ancho de banda y latencia. Esta no pasa por la memoria caché.
• Memoria compartida: Baja latencia, ancho de banda muy elevado. La controla el programador, ya que puede actuar como caché.
• Memoria de texturas/constantes: Es solo de lectura y pasa por el caché. Es muy rápida y de alta/baja latencia.

2.6 Organización de los computadores paralelos

Memoria distribuida VS Memoria compartida

• Memoria distribuida: Cada procesador tiene su propia memoria. Para intercambiar datos se utiliza paso de mensajes a través de una red de interconexión.
• Memoria compartida: Único espacio de memoria. Todos los procesadores tienen acceso a la memoria a través de una red de interconexión. Esta memoria puede ser física o lógica.

Sistemas de memoria compartida

• UMA (Uniform Memory Access): Cada procesador tiene acceso uniforme a memoria.
• NUMA (Non-Uniform Memory Access): La memoria está físicamente distribuida pero lógicamente unificada. El tiempo de acceso depende de dónde estén alojados los datos.

Sistemas actuales y futuros

• Multicore: Actualmente hay una amplia gama de procesadores para PCs y portátiles que incorporan paralelismo para reducir consumo y aumentar prestaciones.
• Procesadores específicos: GPUs que incorporan ya algunos procesadores.
• Procesamiento cuántico

T.3 Tipos de paralelismo y modelos de programación

3.1 Tipos de paralelismo

Implícito VS Explícito

Algunos paradigmas de programación son más sencillos de programar que otros, pero estos generan código más alejado del hardware (-eficiencia). Distintas aplicaciones pueden presentar diferentes tipos de paralelismo. Los modelos de programación paralela existen como abstracción de las arquitecturas hardware y memoria, no tienen que estar vinculadas a una arquitectura concreta.

• Explícito: El algoritmo debe especificar cómo cooperan los procesadores. La tarea del compilador es sencilla, mientras que la del programador es complicada.
• Implícito: Programación secuencial. El compilador paraleliza transparente al programador. El compilador tiene que analizar y comprender las dependencias para asegurar un correcto y eficiente mapeo. El desarrollo del compilador es costoso y genera un código poco eficiente.

3.2 Paralelismo de datos VS Paralelismo de tareas

Paralelismo de datos

Aplicaciones en las que los datos están sujetos a idéntico procesamiento. Es apropiado para máquinas SIMD o MIMD, ya que: Sincronización global de cada instrucción. Solución: Relajar la ejecución síncrona de instrucciones. SPMD: Cada procesador ejecuta el mismo problema asíncronamente.

Paralelismo de tareas

Se ejecutan simultáneamente diferentes tareas. Son adecuados para MIMD porque requiere múltiples cadenas de instrucciones, ejecuta tareas distintas.

3.3 Comunicación mediante paso de mensajes

Características

• Programa: Colección de procesos con variables privadas y con la posibilidad de enviar y recibir datos mediante paso de mensajes.
• Arquitectura: La ideal es distribuida, aunque también se puede utilizar en arquitecturas de memoria compartida.
• Sintaxis: Suele ser basada en C, pero con extensiones: Paso de mensajes, sincronización de procesos…
• Estándares: MPI

3.4 Memoria compartida

Conceptos previos

• Programa: Colección de procesos.
• Exclusión mutua: Más de un proceso puede acceder al mismo tiempo a la misma zona de memoria.
• Sintaxis: Basada en C con extensiones.
• Estándares: OpenMP

Trabajar con memoria compartida

Primitivas para asignar variables compartidas:

• Dos tipos de variables: Shared y private.

Primitivas para la exclusión mutua y sincronización:

• Sección crítica: Solo se puede ejecutar por un procesador en cierto momento. Se necesitan ‘locks’ para poder garantizar la exclusión mutua.
• Barreras: Cuando los procesos necesitan sincronizarse, se esperan mutuamente en la barrera. Después de la sincronización, todos los procesos continúan con la ejecución.

Primitivas para la creación de procesos (fork + join):

• Llamada al sistema que crea procesos idénticos al padre ‘fork’.
• Cuando los subprocesos terminan se mezclan con ‘join’.
• Al principio se tiene el proceso maestro. Si necesita realizar una tarea en paralelo, crea un número de procesos llamados procesos esclavos. Cuando se completa, los procesos esclavos terminan y devuelven el control al proceso maestro.

3.5 Procesos heterogéneos

Conceptos previos

• Computador heterogéneo: Varios procesadores dentro del mismo computador de distinta naturaleza.
• Cada día es más habitual que los ordenadores presenten un procesador y una tarjeta gráfica.
• La unidad de procesamiento gráfico se está incluyendo dentro del chip.

Trabajando con la heterogeneidad

• Mezclar paralelismo de tareas y datos.
• El lenguaje más utilizado es CUDA de NVIDIA.
  • Dos paradigmas: Secuencial para la CPU y extensiones para controlar la GPU.
  • Problema: Lenguaje propietario, solo para GPUs de NVIDIA.
• Estándar: OpenCL
  • Hecho para ejecutar la misma aplicación en cualquier plataforma.
  • Problema: Desarrollo tedioso y muy general.
• OpenACC: Es una colección de directivas de compilación para especificar bucles y regiones de código que se pueden paralelizar.