PDF de programación - Programación de Memoria Compartida - OpenMP - Metodología de la Programación Paralela

Metodología de la Programación Paralela

2015-2016

Facultad Informática, Universidad de Murcia

Programación de Memoria

Compartida - OpenMP

Contenido

1 Tipos de paralelismo

2 OpenMP

Ejemplo básico
Directivas
Cláusulas de alcance de datos
Funciones
Variables de entorno
Tareas
... y más

Tipos de paralelismo

Diferencia en paradigmas de programación paralela

Diferencia de esfuerzo en escribir programas.
Algunos lenguajes menos esfuerzo para el programador.
Otros requieren menos trabajo pero generan un código
menos eficiente.
Un determinado paradigma puede ser más eficiente que otro
al programar sobre determinadas arquitecturas paralelas.
Distintas aplicaciones tienen diferentes tipos de paralelismo.

Tipos de paralelismo

Paralelismo implícito / explícito

Explícito:

El algoritmo paralelo debe especificar cómo cooperan los
elementos de proceso.
La tarea del compilador es sencilla. La del programador es
difícil.
Implícito:

Lenguaje de programación secuencial y el compilador inserta
las instrucciones necesarias para ejecutar el programa en un
sistema paralelo.
El compilador tiene que analizar y comprender las
dependencias para asegurar un mapeo eficiente.

Tipos de paralelismo

Espacio de direcciones compartido / Paso de Mensajes

Memoria Compartida

El programa se ve 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 (secciones críticas, constructores secuenciales, llaves,
semáforos...)

Paso de Mensajes

El programa es 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.

Tipos de paralelismo

Lenguajes de programación paralela

Normalmente lenguajes secuenciales aumentados mediante
un conjunto de llamadas de sistema.
Las llamadas producen primitivas de bajo nivel para el paso
de mensajes, sincronización, exclusión mutua, etc.
Problema de portabilidad entre arquitecturas.
Entornos con primitivas independientes del computador
ofrecen portabilidad.

Tipos de paralelismo

Paralelismo de control

Ejecución simultánea de cadenas de instrucciones diferentes.
Las instrucciones se pueden aplicar sobre la misma cadena
de datos, pero normalmente se aplican a cadenas de datos
diferentes.
Adecuados para MIMD ya que requiere múltiples cadenas de
instrucciones.

Tipos de paralelismo

Paralelismo de datos

Aplicaciones en las que los datos están sujetos a idéntico
procesamiento.
Apropiado para máquinas SIMD.
Se pueden ejecutar en computadores MIMD, con
sincronización global después de cada instrucción ⇒
ineficiente.
Relajar la ejecución síncrona de las instrucciones:
Modelo SPMD (Single Program Multiple Data): cada
elemento de proceso ejecuta el mismo programa
asíncronamente.

Tipos de paralelismo

Memoria Compartida: compartición de variables

Primitivas para asignar variables compartidas.
Existen dos tipos de variables: compartidas (shared) y
locales (private).
Primitivas para la exclusión mutua:

Una secci ón crítica tiene código que ejecuta un único
elemento de proceso en un momento determinado.
Los lenguajes proporcionan llaves (locks) para programar la
exclusión mutua en secciones críticas.

Sincronización:
Sincronización de barreras se usa para sincronizar todos los
elementos de proceso.
Cada proceso espera en la barrera a los otros procesos.
Después de la sincronización todos los procesos continúan
su ejecución.

Tipos de paralelismo

Memoria Compartida: creación de procesos

Con una llamada al sistema se crean procesos idénticos al
padre.
Estos procesos comparten las variables declaradas
“compartidas” por el padre.
En algunos entornos esta operación se llama fork.
Cuando los subprocesos terminan, se mezclan con otra
primitiva, normalmente llamada join.
Al principio de la ejecución, podemos tener un solo proceso
(maestro).
Cuando el maestro necesita hacer una tarea en paralelo, crea
procesos esclavos.
Cuando la tarea se completa, los esclavos terminan y
devuelven el control al maestro.

Tipos de paralelismo

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 elementos de
proceso.
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.
Generan ficheros con información de bucles paralelizados y no paralelizados y el
motivo.

OpenMP

Ideas generales

Modelo de programación fork-join,
con generación de múltiples
threads.
Inicialmente se ejecuta un thread
hasta que aparece el primer
constructor paralelo,
se crean threads esclavos y el que
los pone en marcha es el maestro.
Al final del constructor se
sincronizan los threads y continúa
la ejecución el maestro.

maestroesclavosconstructorjoinOpenMP

Ejemplo básico

Hello world (codigo3-11.c)

#include <omp.h>
int main()

{

int iam = 0, np = 1;

#pragma omp parallel private(iam,np)

{

#if defined (_OPENMP)

np = omp_get_num_threads();
iam = omp_get_thread_num();

#endif

printf("Hello from thread %d out of %d \n", iam, np);

}

}

OpenMP

Ejemplo básico

Compilación y ejecución

Compilación con un compilador C/C++ y la opción de
OpenMP:

$gcc -O3 programa.c -fopenmp

$icc -O3 programa.c -openmp

Una vez compilado se ejecuta como cualquier otro programa.
¿Cuántos threads se ponen en marcha?
Por defecto el número de cores.
Se puede cambiar con variable de entorno o funci ón de
librería.

OpenMP

Directivas

Forma general

#pragma omp nombre-directiva [clausulas]

OpenMP

Directivas

Constructor parallel (codigo3-12.c)

#pragma omp parallel [clausulas]

bloque

Se crea un grupo de threads. El que los pone en marcha actúa de maestro.
Con cláusula if se evalúa su expresión y si da valor distinto de cero se
crean los threads, si es cero se hace en secuencial.
El número de threads a crear se obtiene por variables de entorno o
llamadas a librería.
Hay barrera implícita al final de la región.
Cuando dentro de una región hay otro constructor paralelo (anidamiento)
cada esclavo crea otro grupo de threads esclavos de los que es el maestro.
Cláusulas (private, firstprivate, default, shared, copyin y
reduction) para indicar la forma en que se accede a las variables.

OpenMP

Directivas

Constructor for (codigo3-13.c)

#pragma omp for [clausulas]

bloque for

Las iteraciones se ejecutan en paralelo por threads que ya existen.
La parte de inicialización del for debe ser una asignación.
La parte de incremento debe ser una suma o resta.
La parte de evaluación es la comparación de una variable entera sin signo
con un valor, utilizando un comparador mayor o menor (puede incluir igual).
Los valores que aparecen en las tres partes del for deben ser enteros.
Hay barrera al final a no ser que se utilice la cláusula nowait.
Cláusulas (private, firstprivate, lastprivate y reduction) para
indicar la forma en que se accede a las variables.

OpenMP

Directivas

Constructor for - schedule

Una cláusula schedule indica la forma como se dividen las
iteraciones del for entre los threads:

schedule(static,tamaño) las iteraciones se dividen según el
tamaño, y la asignación se hace estáticamente a los threads.
Si no se indica el tamaño se divide por igual entre los threads.

schedule(dynamic,tamaño) las iteraciones se dividen según el
tamaño y se asignan a los threads dinámicamente cuando van
acabando su trabajo.

schedule(guided,tamaño) las iteraciones se asignan
dinámicamente a los threads pero con tamaños decrecientes.

schedule(runtime) deja la decisión para el tiempo de ejecución, y
se obtienen de la variable de entorno OMP SCHEDULE.

Se puede experimentar con modificaciones de ejemplo for.c

OpenMP

Directivas

Constructor sections (codigo3-14.c)

#pragma omp sections [clausulas]

{

}

[#pragma omp section]

bloque

[#pragma omp section

bloque
...

]

Cada sección se ejecuta por un thread.
Hay barrera al final a no ser que se utilice la cláusula nowait.
Cláusulas (private, firstprivate, lastprivate y reduction) para
indicar la forma en que se accede a las variables.

Se puede experimentar con modificaciones de ejemplo sections.c

OpenMP

Directivas

Constructores combinados

Forma abreviada de directiva parallel con una única directiva
for o sections, de las que admite sus cláusulas menos la
nowait.

#pragma omp parallel for [clausulas]

bucle for

#pragma omp parallel sections [clausulas]

OpenMP

Directivas

Constructores de ejecución secuencial

#pragma omp single [clausulas]

bloque

El bloque se ejecuta por un único thread. No tiene que ser el maestro.
Hay barrera al final a no ser que se utilice la cláusula nowait.

#pragma omp master

bloque

El bloque lo ejecuta el thread maestro.
No hay sincronización al entrar ni salir.

#pragma omp ordered

bloque

El bloque se ejecuta en el orden en que se ejecutaría en secuencial.

Ejemplos ejemplo single.c, ejemplo master.c y ejemplo ordered.c

OpenMP

Directivas

Constructores de sincronización

#pragma omp critical [nombre]

bloque

Asegura exclusión mutua en la ejecución del bloque.
El nombre se puede usar para identificar secciones críticas distintas.

Ejemplos codigo3-17.c y ejemplo critical.c

#pragma omp barrier
Sincroniza todos los threads en el equipo.

Ejemplo ejemplo barrier.c

#pragma omp atomic

expresion

La expresión debe ser x binop = exp, x + +, + + x, x − − o − − x, donde x
es una expresión con valor escalar, y binop es un operador binario.
Asegura la ejecución de la expresión de forma atóm