Fundamentos y Evolución de la Programación Paralela

Conceptos Básicos

¿Qué es la Programación Paralela?

Se encarga de desarrollar programas capaces de realizar muchos cálculos simultáneos. Estos problemas deben ser capaces de dividirse en subproblemas más pequeños, los cuales se deben resolver simultáneamente, suponiendo que disponemos de hardware capaz de realizar cálculos en paralelo.

Evolución del Paralelismo

Comienzos

Ha estado presente desde el primer día. En el S.XX, investigadores de IBM construyen los primeros ordenadores paralelos comerciales. La computación paralela se limitó a ciertos entornos científicos, utilizada para computación de alto rendimiento.

Historia

A principios del S.XXI, el escalado de frecuencia se encuentra 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.

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 también, ya que aparecen nuevas fuentes de errores. 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, y tienen como objetivo mejorar la eficiencia. Por otro lado, los programas concurrentes pueden o no ejecutar varias instancias al mismo tiempo.

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 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.

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)
• Clusters de computadores

Metodología APOD

Conceptos Básicos de APOD

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

Evaluar (Assess)

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 CPU/GPU y la 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 cores = 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 paralelizados. La paralelización usa el lenguaje nativo de la plataforma objetivo.

Optimizar (Optimize)

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 (Deploy)

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

Paralelismo en CPU y GPU

Características

• CPUs (Multicore, Núcleos complejos):
  • Implementació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 CPUs están optimizadas para el código secuencial, con mucha memoria caché. Mientras que las GPUs 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