1. No category

Arquitectura de Computadores:
Práctica de Multiprocesadores
Introducción a OpenMP
Índice
1 Introducción
1.
2. Regiones Paralelas:
3. Distribución del trabajo
4. Gestión de datos
5. Sincronización
6 Funciones
6.
F i
de
d bibli
biblioteca
t
7. Variables del entorno
8. Ejemplo Π
AC : MP: Introd. a OpenMP
2
¿Qué es OpenMP?
API estándar “de facto” para la programación multithread de
sistemas de memoria compartida (C, C++ y Fortran)
Consta de:
●
●
●
Directivas para el compilador
Funciones de librería
Variables de entorno
AC : MP: Introd. a OpenMP
3
Introducción

OpenMP se basa en directivas al compilador (¡el código es
compilable
p
incluso si el compilador
p
no soporta
p
OpenMP!)
p
)

Que se aplican a “bloques estructurados”: una o más
sentencias con un ppunto de entrada y uno de salida

Se apoya en threads, para la paralelización (modelo SPMD)

O MP se bbasa en lla paralelización
OpenMP
l li ió de
d bucles
b l (datos)
(d
)

Mismo código fuente para secuencial y paralelo
Se protege con el preprocesador: #ifdef _OPENMP ….

Los pprototipos
p de funciones y los tipos
p están en el fichero:
#include <omp.h>

¡¡Puede haber interbloqueos
q
y carreras!

También soporta vectorización y coprocesadores
AC : MP: Introd. a OpenMP
4
Modelo de programación de OpenMP



Modelo de paralelismo: Fork-Join
El programa comienza con un solo thread (maestro)
El maestro crea threads según necesidad
AC : MP: Introd. a OpenMP
5
Ejemplo
// Secuencial:
void main()
{
double Res[1000];
for(int i=0;i<1000;i++)
do_huge
g _comp(Res[i]);
p
}


// Paralelo:
void main()
{
double Res[1000];
#pragma omp parallel for
for(int i=0;i<1000;i++)
do_huge
g _comp(Res[i]);
p
}
Similar la versión paralela y la secuencial.
secuencial
Pocos cambios, legible y fácil de mantener
ACAR: Introducción a OpenMP
6
Creación de threads: Regiones Paralelas
Se declaran con la directiva
#
#pragma
omp parallel
ll l [cláusulas]
[ lá l ]
{//código…}

Crea N threads que ejecutan en paralelo el mismo código,
solo cambia su ID.

¡Al final de la región hay una barrera implícita!

El número de threads depende
p
de variables internas
(num_threads, max_threads, dynamic)
o de la cláusula
c usu num
u _t
threads(int)
eads( t)

Si se pone la cláusula if, se paraleliza sólo si se cumple la
condición:…parallel if(N>100)…
AC : MP: Introd. a OpenMP
7
Regiones Paralelas: Ejemplo
#include “omp.h”
omp.h
Funciones de librería
…………
double A[1000];
omp_set_num_threads(4);
#pragma omp parallel
{
int ID = omp_get_thread_num();
omp get thread num();
sumarElemA (ID,A);
}
Cada thread llama a sumarElemA para ID=0 .. 3
Una sola
l copia
i de
d A,
A compartida
id por todos
d los
l threads
h d
AC : MP: Introd. a OpenMP
8
Regiones Paralelas: Ejemplo
#include “omp.h”
omp.h
…………
double A[1000];
cláusula
#pragma omp parallel num
num_threads(4)
threads(4)
{
int ID = omp_get_thread_num();
omp get thread num();
sumarElemA (ID,A);
}
Cada thread llama a sumarElemA para ID=0 .. 3
Una sola
l copia
i de
d A,
A compartida
id por todos
d los
l threads
h d
AC : MP: Introd. a OpenMP
9
Distribución del trabajo: for
Se declara con la directiva
#pragma omp for [cláusulas]
for (;;) {//código…}

Divide las iteraciones de un bucle entre los threads
di
disponibles.
ibl

Al final hay una barrera implícita,
evitable con cláusula nowait

Se puede especificar cómo se reparten las iteraciones entre
los threads:
cláusula schedule
AC : MP: Introd. a OpenMP
10
Distribución del trabajo for: Ejemplo
1. Código
g secuencial
for(i=0;i<N;i++)
{a[i] = a[i] + b[i];}
2.
Región Paralela OpenMP
di ib ió de
distribución
d trabajo
b j
manualmente
(id, i, Nthrds,
istart, iend: son
variables privadas,
¿por qué?
¿p
q
¿deben
¿
serlo?))
#pragma omp parallel
{
int id, i,Nthrds,istart,iend;
id = omp_get_thread_num();
Nthrds =omp
omp_get_num_threads();
get num threads();
istart = id * N / Nthrds;
iend = (id+1) * N / Nthrds;
for(i=istart;i<iend;i++)
(
)
{ a[i] = a[i] + b[i];}
}
3
3.
Región
R
ió Paralela
P l l OpenMP
O MP
y distribución de trabajo
for
#pragma omp parallel
#
#pragma omp for schedule(static)
for(i=0;i<N;i++)
{ a[i]
[i] = a[i]
[i] + b[i]
b[i];}
}
AC : MP: Introd. a OpenMP
11
Distribución del trabajo for: Planificación
Planificación con la cláusula schedule:
#pragma omp for schedule(..)

schedule (static [,chunk])
Asigna bloques fijos de iteraciones de tamaño “chunk” a cada thread

schedule (dynamic [,chunk])
C d thread
Cada
h d coge “chunk”
“ h k” iteraciones
i
i
hasta
h
terminar
i
con todas
d

schedule (guided [,chunk])
● Cada
C d thread
th d coge dinámicamente
di á i
t bloques
bl
de
d iteraciones
it
i
● El bloque inicialmente es grande (nº iteraciones sin asignar
dividido por nº threads) y va bajando hasta tamaño“chunk”

schedule (runtime)
Planificación y tamaño de bloque determinado por la variable de
entorno OMP_SCHEDULE
OMP SCHEDULE
AC : MP: Introd. a OpenMP
12
Planificación: Ejemplo
j p
200 iteraciones en 4 threads
AC : MP: Introd. a OpenMP
13
Distribución del trabajo: sections

Asigna bloques de código a threads.
threads
Ejemplo:
#pragma omp parallel
#pragma omp sections
{
x_calculation();
#pragma omp section
y_calculation();
#pragma omp section
z_calculation();
();
}

Al final hay una barrera (evitable con nowait)
AC : MP: Introd. a OpenMP
14
Gestión de los datos

Modelo de programación de memoria compartida:
●
●


La mayoría de las variables son compartidas por defecto
Las variables globales son compartidas
Pero no todas las variables son compartidas:
●
Al
Algunas
ddeben
b ser específicas
ífi
para cada
d thread
h d
●
Las variables declaradas dentro de una región paralela
●
Las ubicadas en cada pila propia (parámetros y variables
locales) son privadas (cada thread tiene su pila)
Se puede cambiar los ‘atributos’ de las variables heredadas
del maestro mediante cláusulas
AC : MP: Introd. a OpenMP
15
Gestión de los datos

shared: Variable común a todos los threads
Cuidado: puede ser necesario utilizar regiones críticas

private:
i t Cada
C d thread
h d tiene
ti
“su”
“ ” copia
i local.
l l
Sin inicializar y valor indefinido tras la región paralela

firstprivate: Es “private”, pero se inicializa con el valor de
la ‘original’ (variable del maestro)

lastprivate: Es “private”, pero al final se le asigna el valor
que toma en la última iteración o sección

default: shared, private (FORTRAN) o none
AC : MP: Introd. a OpenMP
16
Gestión de los datos

threadprivate: hace una copia de una variable, privada
para cada
d thread.
h d Existe
i a lo
l largo
l
de
d la
l ejecución
j
ió (en
(
secuencial se ve la copia del maestro)

copyin: inicializa las variables threadprivate con el valor de
la del maestro

copyprivate: pasa el valor dado por un thread al resto (se
usa con single)

reduction (op:list): deben ser variables shared
• Hará una copia local y la inicializará según “op”
• Al final las copias locales se reducen a una global
• Operadores: + * - & | ^ && || min max
AC : MP: Introd. a OpenMP
17
Gestión de los datos: Ejemplos
j p
1.
int tmp=0;
#pragma omp parallel private(i) firstprivate(tmp)
{ i = 3 + func(id);
tmp = tmp + 2;}
2. #pragma omp parallel for lastprivate(i)
for (i=0; i<n-1; i++)
a[i] = b[i] + b[i+1
a[i]=b[i]; // caso n-1 fuera bucle
3. double ave=0.0, A[MAX], int i;
#pragma omp parallel for \
schedule
h d l (
(static)reduction(+:ave)
t ti ) d ti (
)
for (i=0; i<MAX; i++)
ave+= A[i];
ave = ave/MAX
/MAX
AC : MP: Introd. a OpenMP
18
Gestión de los datos
1.
2
2.
int counter = 0; // Nº tareas ejecutadas por cada hilo…
#pragma omp threadprivate(counter)
#pragma omp threadprivate(work
threadprivate(work,size)
size)
#pragma omp parallel copyin(size) shared(N)
{
work = build(tol,size+N);
}
3.
#pragma omp parallel for reduction(+:res) lastprivate(Z,i)
for (i=0; i< 1000; i++){
Z = func(I);
res = res + Z;
}
ACAR: Introducción a OpenMP
19
Sincronización

critical [name]: Definición de una región crítica.
Los threads esperan al comienzo de la región crítica hasta que no
haya ningún hilo ejecutando una región crítica con el mismo
nombre.
b Todas
T d las
l que no tienen
ti
nombre,
b se consideran
id
que tienen
ti
un mismo nombre no especificado

Atomic [read|write|update|capture]: Asegura una
actualización atómica. Por defecto update
●
●
●
●
Lectura
L
t
atómica:
tó i v = x;
Escritura atómica: x = expr; //expr no atómica
Actualización atómica: x = x binop expr;
“Captura” atómica: v = x binop= expr; // x atómico
AC : MP: Introd. a OpenMP
20
Sincronización

barrier: Implementa una barrera

ordered: Asegura que las iteraciones se ejecutan en el
mismo orden que en secuencial: ¡¡evítese en lo posible!!

master: Sólo el maestro ejecuta dicho código, los demás se lo
saltan. Sin barrera.

single:
g Un solo thread ejecuta
j
dicho código,
g , tiene una barrera
implícita. Con copyprivate puede hacer visible a los demás
threads los cálculos hechos.
AC : MP: Introd. a OpenMP
21
Sincronización: Ejemplos
1.
#pragma omp parallel for schedule(dynamic) private(a)
for (i=0; i<N; i++){
a = work(i); // en paralelo
#pragma omp ordered
// espera que le toque
printf(“%d\n",
printf(
%d\n , a); //impresión resultados ordenada
}
2. #pragma omp threadprivate(x, y)
void init(float a
a, float b ) { // a y b privados
#pragma omp single copyprivate(a,b,x,y)
scanf("%f %f %f %f", &a, &b, &x, &y);
}
3. #pragma omp critical qlock
enqueue(job);
…
#pragma omp critical qlock
dequeue(job);
AC : MP: Introd. a OpenMP
22
Sincronización
1.
omp_lock_t
_
_ *new_lock()
_
{
omp_lock_t *lock_ptr;
#pragma omp single copyprivate(lock_ptr)
{
lock_ptr = (omp_lock_t *)malloc(sizeof(omp_lock_t));
omp_init_lock( lock_ptr );
} //barrera,
//
todos salen con el cerrojo!!!
return lock_ptr;
}
AC : MP: Introd. a OpenMP
23
Tareas

A partir de OpenMP 3.0
30

Permite definir una “task”: conjunto de código y datos
a ejecutar:
j t
#pragma omp task firstprivate(my_pointer)
(void) do
do_independent_work
independent work (my
(my_pointer);
pointer);

Si hay algún thread disponible se pone a ejecutarla, si
no espera uno libre.

Se espera por ellas en las barreras implícitas y
explícitas
ACAR: Introducción a OpenMP
24
OpenMP 4.0
40


Está disponible OpenMP 4.0 (http://www.openmp.org)
Dos cambios importantes: vectorización y coprocesadores

Vectorización: nuevo #pragma omp simd para vectorizar
bucles. Toma la idea de Intel (icc). Con claúsulas
●

Busca aprovechar las unidades vectoriales: MMX, SSE, AVX,
MIC) Se podrá combinar con regiones paralelas:
MIC).
#pragma omp parallel for simd
Coprocesadores: Se busca aprovechar las GPUs y MICs,
MICs de
gran potencia de cálculo.
●
Se introduce #pragma omp target para indicar el
dispositivo sobre el que se quiere ejecutar
●
Toma la idea de PG, que ya dispone del OpenACC, un
OpenMP de pago para GPUs
ACAR: Introducción a OpenMP
25
Funciones de biblioteca:
Entorno de Ejecución

Gestión de threads
•
•
•
•
•
•

void omp_set_num_threads(int)
int
t omp
o p_get_
get num
u _t
threads(void)
eads( o d)
int omp_get_thread_num(void)
int omp_get_max_threads(void)
_
_
_
void omp_set_dynamic(bool)
bool omp_get_dynamic(void)
Anidamiento del paralelismo
•
•
void omp_set_nested(bool)
omp set nested(bool)
bool omp_get_nested(void)
AC : MP: Introd. a OpenMP
26
Funciones de biblioteca:
Entorno de Ejecución y Cerrojos

Cerrojos
•
•
•
•
•

void
void
void
void
void
oid
omp_init_lock(lock)
omp_destroy_lock(lock)
omp_set_lock(lock)
omp_unset_lock(lock)
omp_test_lock(lock)
omp test lock(lock)
¿En una región paralela?
bool omp_in_parallel(void)
omp in parallel(void)

Número procesadores:
int omp
omp_num_procs(void)
num procs(void)

Tomar tiempos
omp
p_g
get_wtime(), omp
p_g
get_wtick()
AC : MP: Introd. a OpenMP
27
Variables del Entorno del Ejecución

OMP SCHEDULE “schedule[,
OMP_SCHEDULE
schedule[, chunk
chunk_size]
size]”

OMP_NUM_THREADS int_literal // Máximo

OMP_DYNAMIC bool
b l //
//Ajusta
j
el
l número
ú
d
de
hilos en cada región paralela

OMP_NESTED bool

OMP_PROC_BIND bool

OMP_STACKSIZE int [B|K|M|G}

OMP WAIT POLICY passive || active
OMP_WAIT_POLICY

OMP_THREAD_LIMIT int
AC : MP: Introd. a OpenMP
28
Compilación

Incluir el fichero de cabecera: #include <omp.h>
p

Se activa _OPENMP

Compilador de GCC:
gcc -fopenmp
gfortran -fopenmp

Compilador de Intel:
icc -openmp
ifort –openmp
AC : MP: Introd. a OpenMP
29
Ejemplo del cálculo de Pi

Por cálculo númerico:
1
4.0
dx  
2
1 x

0


Se aproxima como:
N
 F ( x )x  
i 0

i
con F(xi) el alto a mitad del
intervalo y x el ancho del
intervalo
AC : MP: Introd. a OpenMP
30
Ejemplo del cálculo de Pi : Secuencial
static long num_steps = 100000;
double step;
void main (){
int i; double x, pi, sum = 0.0;
step = 1.0/(double) num_steps;
_
for (i=0;i< num_steps; i++){
x = (i+0.5)*step;
sum = sum + 4.0/(1.0+x*x);
/
}
pi = step * sum;
}
AC : MP: Introd. a OpenMP
31