Sincronización de los threads y tareas (OpenMP)

OpenMP proporciona los mecanismos de sincronización más habituales: exclusión mutua y sincronización por eventos.
Sincronización de threads

1. Secciones Críticas
Define un trozo de código que no puede ser ejecutado por más de un thread a la vez.

OpenMP ofrece varias alternativas para la ejecución en exclusión mutua de secciones críticas. Las dos opciones principales son: critical y atomic.
Exclusión mútua (SC)

? Directiva critical

Define una única sección crítica para todo el programa, dado que no utiliza variables de lock.
#pragma omp parallel firstprivate(MAXL)
{
…
#pragma omp for
for (i=0; iMAXL) MAXL = A[i];
}
#pragma omp critical
{ if (MAXL>MAX) MAX = MAXL; }
…
}
OJO: la sección crítica debe ser lo “menor” posible!
Exclusión mútua

? Secciones críticas “específicas” (named)
#pragma omp parallel for
for (i=0; iMAX)
#pragma omp critical(M1)
{ if (A[i]>MAX) MAX = A[i]; }

if (A[i] Ejemplo
#pragma omp parallel private(nire_it)
{
omp_set_lock(&C1);
mi_it = i;
i = i + 1;
omp_unset_lock(&C1);

while (mi_it Ejemplo

/* productor */
…
dat = …;
flag = 1;
…
? Sincronización punto a punto
La sincronización entre procesos puede hacerse mediante flags (memoria común), siguiendo un modelo de tipo productor / consumidor.
/* consumidor */
…
while (flag==0) { };
… = dat;
…
Eventos (flags)

Sin embargo, sabemos que el código anterior puede no funcionar correctamente en un sistema paralelo, dependiendo del modelo de consistencia de la máquina.

Tal vez sea necesario desactivar las optimizaciones del compilador antes del acceso a las variables de sincronización.
Eventos (flags)

Para asegurar que el modelo de consistencia aplicado es el secuencial, OpenMP ofrece como alternativa la directiva:
#pragma omp flush(X)
que marca puntos de consistencia en la visión de la memoria (fence).
/* productor */
…
dat = …;
#pragma omp flush(dat)
flag = 1;
#pragma omp flush(flag)
…
/* consumidor */
…
while (flag==0)
{ #pragma omp flush(flag) };
#pragma omp flush(dat)
… = dat;
…
Eventos (flags)

El modelo de consistencia de OpenMP implica tener que realizar una operación de flush tras escribir y antes de leer cualquier variable compartida.
volatile int dat, flag;
…

/* productor */
…
dat = …;
flag = 1;
…
volatile int dat, flag;
…

/* consumidor */
…
while (flag==0) {};
… = dat;
…
En C se puede conseguir esto declarando las variables de tipo volatile.
Eventos (flags)

4. Secciones “ordenadas”

#pragma omp ordered

Junto con la cláusula ordered, impone el orden secuencial original en la ejecución de una parte de código de un for paralelo.
#pragma omp paralell for ordered
for (i=0; i Ejemplo 1: lista ligada
…
while (puntero)
{
(void) ejecutar_tarea(puntero);
puntero = puntero->sig;
}
…
Sin la directiva task, habría que contar el número de iteraciones previamente para transformar el while en un for.
Tareas

puntero = cabecera;
#pragma omp parallel
{
#pragma omp single nowait
{
while(puntero) {
#pragma omp task firstprivate(puntero)
{
(void) ejecutar_tarea(puntero);
}
puntero = puntero->sig ;
}
}
}
Tareas
> Ejemplo 1: lista ligada – openmp

long fibonacci(int n)
{ // f(0)=f(1)=1, f(n) = f(n-1) + f(n-2)

long f1, f2, fn;

if ( n == 0 || n == 1 ) return(n);

f1 = fibonacci(n-1);
f2 = fibonacci(n-2);

fn = f1 + f2;

return(fn);
}
Tareas
> Ejemplo 2: fibonacci

long fibonacci(int n)
{
long f1, f2, fn;

if ( n == 0 || n == 1 ) return(n);

#pragma omp task shared(f1)
{f1 = fibonacci(n-1);}

#pragma omp task shared(f2)
{f2 = fibonacci(n-2);}

#pragma omp taskwait

fn = f1 + f2;

return(fn);
}
Tareas
> Ejemplo 2: fibonacci – openmp

#pragma omp parallel shared(nth)
{
#pragma omp single nowait
{
result = fibonacci(n);
}
}
Posibilidad de aplicar recursividad paralela a partir de un tamaño mínimo de cálculo?
Tareas
> Ejemplo 2: fibonacci – openmp

? Un par de funciones para “medir tiempos”

? omp_get_wtime();

t1 = omp_get_wtime();
…
t2 = omp_get_wtime();
tiempo = t2 – t1;

? omp_get_wtick(); precisión del reloj
Otras cuestiones

? Programar aplicaciones SMP resulta “más sencillo” que repartir datos por diferentes procesadores y comunicarse por paso de mensajes.

Pero el uso de variables compartidas por varios threads puede llevar a errores no previstos si no se analiza detenidamente su comportamiento.

Algunos errores típicos pueden producir carreras (races) en los resultados o dejar bloqueada la ejecución (deadlock).
Otras cuestiones

? Carreras
Definimos una carrera (race) como la consecución de resultados inesperados e irreproducibles debido a problemas en el acceso y sincronización de variables compartidas.
#pragma omp parallel sections
{
#pragma omp section
A = B + C;

#pragma omp section
B = A + C;

#pragma omp section
C = B + A;
}
!?
Otras cuestiones: carreras

CONT = 0;
#pragma omp parallel sections
{ #pragma omp section
A = B + C;
#pragma omp flush (A)
CONT = 1;
#pragma omp flush (CONT)
#pragma omp section
{ while (CONT<1)
{ #pragma omp flush (CONT) }
B = A + C;
#pragma omp flush (B)
CONT = 2;
#pragma omp flush (CONT)
}
#pragma omp section
{ while (CONT<2)
{ #pragma omp flush (CONT) }
C = B + A;
}
}
el contador permite la sincronización entre las secciones (eventos)
las operaciones de flush aseguran la consistencia de la memoria.
Otras cuestiones: carreras

#pragma omp parallel private(tid, X)
{
tid = omp_get_thread_num();

#pragma omp for reduction(+:total) nowait
for (i=0; i0) omp_unset_lock(&C1);
else
{
…
}

…

(región paralela con secciones)

…
#pragma omp section
{ omp_set_lock(&C1);
A = A + func1();
omp_set_lock(&C2);
B = B * A;
omp_unset_lock(&C2);
omp_unset_lock(&C1);
}

#pragma omp section
{ omp_set_lock(&C2);
B = B + func2();
omp_set_lock(&C1);
A = A * B;
omp_unset_lock(&C1);
omp_unset_lock(&C2);
}
…
Otras cuestiones: deadlock

? Recomendaciones:
? prestar atención al ámbito de las variables: shared, private, etc.

? utilizar con cuidado las funciones de sincronización.

? disponer de una versión equivalente secuencial para comparar resultados (serán siempre iguales?).
Otras cuestiones: deadlock

? Llamadas en paralelo a funciones de librería
¿habrá problemas con la activación simultánea de más de una instancia de dichas funciones?

Una librería es thread-safe (re-entrante) si lo anterior no es un problema. Si no es así, habría que utilizar una secuencia tipo:

LOCK / CALL / UNLOCK
Otras cuestiones

? Speed-up
El objetivo de programar una aplicación en un sistema paralelo es:
– ejecutar el problema más rápido.
– ejecutar un problema de mayor tamaño.

En ambos casos hay que tener en cuenta el overhead añadido al paralelizar el código.
Otras cuestiones: speed-up

? Escribir programas paralelos OpenMP es fácil… y también lo es escribir programas de bajo rendimiento.

? Principales fuentes de pérdida de eficiencia

? el algoritmo en ejecución: Amdahl // desequilibrio de carga
? sincronización: grano muy fino
? comunicación: acceso a variables shared, cache (fallos, falsa compartición…)

? implementación de OpenMP / S.O.
Limitaciones al rendimiento

? Ejemplos de mejora de la eficiencia:
#pragma omp parallel for
for (i=0;i