Download PARTE II: ALGORÍTMICA Tema 4. Divide y vencerás.

Computación de Altas Prestaciones
Modelos de programación paralela
Paradigmas de programación paralela
Tipos de paralelismo
Las variaciones entre los paradigmas están motivadas por varios factores:
• Diferencia de esfuerzo invertido en escribir programas paralelos. Algunos lenguajes requieren menos esfuerzo para el programador, mientras que otros requieren menos trabajo pero generan un código menos eficiente.
• Un determinado paradigma de programación puede ser más eficiente que otros al programar sobre determinadas arquitecturas paralelas.
• Distintas aplicaciones tienen diferentes tipos de paralelismo y por tanto se han desarrollado diferentes lenguajes de programación para explotarlos.
Paralelismo implícito/explícito
• Explícito : algoritmo paralelo debe especificar – El explícitamente cómo cooperan los procesadores para resolver un problema específico.
– La tarea del compilador es sencilla, en cambio la del programador es bastante difícil.
• Implícito:
– Se usa un lenguaje de programación secuencial y el compilador inserta las instrucciones necesarias para ejecutar el programa en un computador paralelo.
– El compilador tiene que analizar y comprender las dependencias para asegurar un mapeo eficiente en el computador paralelo.
Paso de mensajes/espacio de direcciones
compartido
Espacio de direcciones compartido:
• Los programadores ven el programa como una colección de procesos accediendo a una zona central de variables compartidas.
• Más de un proceso podría acceder a la misma zona compartida en el mismo instante produciendo resultados impredecibles. Los lenguajes proporcionan primitivas para resolver estos problemas de exclusión mutua.
Paso de mensajes/espacio de direcciones
compartido
Paso de mensajes: • Los programadores ven su programa como una colección de procesos con variables locales privadas y la posibilidad de enviar y recibir datos mediante paso de mensajes.
• Los computadores de espacio de direcciones compartido también se pueden programar usando el paradigma de paso de mensajes.
Paso de mensajes/espacio de direcciones
compartido
• Muchos lenguajes de programación para memoria compartida o paso de mensajes son básicamente lenguajes secuenciales aumentados mediante un conjunto de llamadas de sistema especiales. Estas llamadas producen primitivas de bajo nivel para el paso de mensajes, sincronización de procesos, exclusión mutua, etc. • Hay librerías como PVM, MPI, OpenMP, con primitivas independientes del computador.
Paralelismo de datos/de control
Paralelismo de datos:
• Aplicaciones en las que los datos están sujetos a idéntico procesamiento. • Es más apropiado para ejecutar en máquinas SIMD. • También se pueden ejecutar en computadores MIMD. Se requiere sincronización global después de cada instrucción, lo que resulta en un código ineficiente. Solución: relajar la ejecución síncrona de las instrucciones. Modelo SPMD. Cada procesador ejecuta el mismo programa asíncronamente. • Los lenguajes de paralelismo de datos ofrecen construcciones de alto nivel para compartir información y manejar concurrencia. Programas más fáciles de escribir y comprender. Aunque el código generado por estas construcciones no es tan eficiente como el obtenido usando primitivas de bajo nivel.
Paralelismo de datos/de control
Paralelismo de control:
• Ejecución simultánea de cadenas de instrucciones diferentes. Las instrucciones se pueden aplicar sobre la misma cadena de datos aunque normalmente se aplican a cadenas de datos diferentes.
• Adecuados para mapear en MIMD ya que el paralelismo de control requiere múltiples cadenas de instrucciones.
Compiladores paralelizantes
• Programa secuencial. El compilador se encarga de paralelizarlo.
• Normalmente en sistemas de memoria compartida.
• Paralelizan bucles: dividen el trabajo en los bucles entre los distintos procesadores
• Si puede haber dependencia de datos no paraleliza:
para i=1 to n
a[i]=b[i]+a[i­1]
finpara
• Se puede forzar la paralelización con opciones de compilación, o con directivas (OpenMP).
• Generan ficheros con información de bucles paralelizados y no paralelizados, y el motivo.
Lenguajes paralelos de alto nivel
• Primitivas que debería contener un lenguaje paralelo:
– Paralelización de bucles,
– Pipeline,
– Crear grupo de procesos, …
• Asociar a cada constructor (esqueleto) una función de coste.
• Mapeo de los procesos generados en función de la función de coste.
• Ejemplo mpC
Librerías para campos específicos de trabajo
• Desarrollar librerías para campos donde más se usa la computación paralela, con capacidades de autooptimización: el usuario llama a la rutina y ésta decide cuántos y qué procesadores usar, la distribución de datos, …
• Álgebra lineal, transformada rápida de Fourier, …