OpenMP 2

Presenter Notes

Resumen:

  • Seguimos con OpenMP.

Nicolás Wolovick 20200504

Presenter Notes

Cláusulas del constructor de lazos

Compartir datos

  • shared y private: como en parallel
    • La variable del for se declara private de manera implícita
  • firstprivate, copyin: idem
  • reduction: idem. Muy usado en este constructor
  • lastprivate: el último valor que toma la variable según el orden del loop se copia al master
    Otra forma de juntar datos
    Notar que requiere de un órden definido por el constructor, por eso parallel no la admite

Sincronización

  • nowait: elimina la barrera final de for

Presenter Notes

Cláusula de ejecución ordenada

  • ordered solo declara que puede existir un bloque ordered
  • El bloque ordered se ejecuta de manera secuencial
  • mientras que el resto es en paralelo

parallel-ordered.c

 1 unsigned int i = 0, tid = 0;
 2 #pragma omp parallel for ordered private(tid)
 3 for(i=0; i<8; ++i) {
 4     tid = omp_get_thread_num();
 5     printf("Unordered %d %d\n", tid, i);
 6     #pragma omp ordered
 7     {
 8     printf("Ordered %d %d\n", tid, i);
 9     }
10 }

Uso típico: procesamiento en paralelo de datos, escritura ordenada en un archivo.

Presenter Notes

Constructor de secciones

Hace el fork de hilos y ejecuta una sección distinta de código en cada uno.
No necesariamente hay una relación 1-a-1 entre secciones e hilos.

parallel-sections.c

 1 #pragma omp parallel sections num_threads(4)
 2 {
 3     #pragma omp section
 4     {
 5     printf("1st lexical section, tid %d\n", omp_get_thread_num());
 6     }
 7     #pragma omp section
 8     {
 9     printf("2nd lexical section, tid %d\n", omp_get_thread_num());
10     }
11 }

Corrida

1 $ ./parallel-sections 
2 1st lexical section, tid 2
3 2nd lexical section, tid 1
4 $ ./parallel-sections 
5 1st lexical section, tid 1
6 2nd lexical section, tid 0

Uso típico: ejecución de funciones en paralelo (function parallelism).

Presenter Notes

Constructor de secciones, cláusulas

  • private
  • shared
  • firstprivate
  • lastprivate: el órden es el dado por las secciones dentro del código fuente
  • reduction
  • nowait

Ya conocemos su semántica.

Presenter Notes

Constructor single

Ejecuta el bloque estructurado con un solo hilo.
El resto de los hilos del team, espera hasta que termine la ejecución secuencial.

Es como un join-single-fork, pero no paga el costo de estas llamadas
(mhhh dijo la mudita, dudo que esto sea más costoso).

#pragma omp single
{ structured block }

Cláusulas

  • private
  • firstprivate
  • copyprivate: difunde el valor de salida de una variable privada al bloque a todos los hilos del team

Presenter Notes

Constructor master

#pragma omp master
{ structured block }

Variación de single:

  • El bloque estructurado lo ejecuta solo el hilo maestro.
  • No incluye la barrera final implícita.

Presenter Notes

Cláusulas válidas para constructores

Clauses / Directives Summary

Presenter Notes

Constructores de sincronización

Barreras

#pragma omp barrier

Separa fases de computación.

Secuencial

#pragma omp ordered
{ structured block }

¡Ya visto!

Presenter Notes

Sincronización: Sección Crítica

#pragma omp critical [(global_name)]
{ structured block }

El bloque lo ejecuta en exclusión mutua respecto a todas las secciones críticas con el mismo nombre global.

Cuidado con el nombre global, sino pueden aparecer:

  • Errores por race-conditions al sincronizar sobre diferentes nombres, ó
  • Esperas innecesarias.
    • Por ejemplo si todos usan #pragma omp critical sin nombre.

Presenter Notes

Sentencias atómicas

#pragma omp atomic
statement

Intenta compilar la sentencia a una instrucción atómica de la arquitectura.

Hay muchísimas restricciones sintácticas, pero cuando aplican se da una gran ganancia de performance.

Ejemplo típico:

1 #pragma omp atomic
2 ++a;

o éste, donde func no se protege. El read-modify-write luego de la llamada si es atómico.

1 #pragma omp atomic
2 a *= func(b);

Presenter Notes

Ejemplo: Histograma

Presenter Notes

Especificación e implementación sec.

Histograma del vector A[N] en el vector M[Q].

Cuantas instancias de {0..Q-1} en A[N].

M[i] = (\sum j: 0<=j<N: A[j]=i)

(una) Implementación secuencial

1 int main(void) {
2     unsigned int i = 0;
3     for(i=0; i<N; ++i)
4         m[a[i]]++;
5     for(i=0; i<Q; ++i)
6         printf("m[%d]=%d\n",i,m[i]);
7 
8     return 0;
9 }

Notar el m[a[i]] = m[a[i]] + 1 que es un gather en términos de vectorización.

Presenter Notes

Versión incorrecta

 1 #define Q 7 /* discretización del histograma */
 2 #define N (1<<28) /* largo del vector */
 3 
 4 unsigned int a[N] = {1,2,3,4,5}; /* vector de muestras en el rango [0,Q) */
 5 unsigned int m[Q] = {0}; /* histograma */
 6 
 7 int main(void) {
 8     unsigned int i = 0;
 9     #pragma omp parallel for shared(a,m)
10     for(i=0; i<N; ++i)
11         m[a[i]]++;
12     for(i=0; i<Q; ++i)
13         printf("m[%d]=%d\n",i,m[i]);
14 
15     return 0;
16 }

Race condition de todos los hilos sobre el read-modify-write del M.
Cada ejecución da diferente.

Solución: hacerlo atómico.

Notar todo lo que tarda en compilar porque tiene que meter en .data el a[2²⁸] por que no está inicializado en 0.

Presenter Notes

Versión critical, atomic

 1 #define Q 7 /* discretización del histograma */
 2 #define N (1<<28) /* largo del vector */
 3 
 4 unsigned int a[N] = {1,2,3,4,5}; /* vector de muestras en el rango [0,Q) */
 5 unsigned int m[Q] = {0}; /* histograma */
 6 
 7 int main(void) {
 8     unsigned int i = 0;
 9     #pragma omp parallel for shared(a,m)
10     for(i=0; i<N; ++i)
11         //#pragma omp atomic
12         #pragma omp critical
13         m[a[i]]++;
14     for(i=0; i<Q; ++i)
15         printf("m[%d]=%d\n",i,m[i]);
16 
17     return 0;
18 }
  • critical es tremendamente lento. ¡Secuencializa todo!
  • atomic compila, pero genera código incorrecto por esta asignación compleja m[a[i]] = m[a[i]]+1.
  • Peformance en la misma máquina: atomic 4.5s, critical 15s.

Presenter Notes

Idea

Tener un M global donde se resume todo, y además un M local donde actua cada hilo de manera independiente.

El viejo truco de las Ciencias de la Computación:

Memory-speed trade off

Presenter Notes

||-reduction-manual.c

 1 #include <stdio.h>
 2 #include <omp.h>
 3 
 4 #define Q 7 /* discretización del histograma */
 5 #define N (1<<28) /* largo del vector */
 6 
 7 unsigned int a[N] = {1,2,3,4,5}; /* vector de muestras */
 8 unsigned int m[Q] = {0}; /* histograma */
 9 unsigned int mp[Q] = {0}; /* histograma per-thread*/
10 
11 int main(void) {
12     unsigned int i = 0;
13     #pragma omp parallel firstprivate(mp) shared(a,m)
14     {
15         #pragma omp for
16         for(i=0; i<N; ++i)
17             mp[a[i]]++;
18 
19         for(i=0; i<Q; ++i) {
20             #pragma omp atomic
21             m[i] += mp[i];
22         }
23     }
24     for(i=0; i<Q; ++i)
25         printf("m[%d]=%d\n",i,m[i]);
26 
27     return 0;
28 }

Muy interesante como mezcla scope de variables en el mismo código CONFUNDE.

Presenter Notes

Zoom-in de la parte paralela

 1 unsigned int i = 0;
 2 #pragma omp parallel firstprivate(mp) shared(a,m)
 3 {
 4     #pragma omp for
 5     for(i=0; i<N; ++i)
 6         mp[a[i]]++;
 7 
 8     for(i=0; i<Q; ++i) {
 9         #pragma omp atomic
10         m[i] += mp[i];
11     }
12 }
13 for(i=0; i<Q; ++i)
14     printf("m[%d]=%d\n",i,m[i]);

Tres (3) for sintácticamente iguales, tres semánticas de ejecución DISTINTAS.

  1. Distribución de trabajo entre hilos.
  2. Todos los hilos ejecutan el mismo lazo
  3. Ejecución secuencial luego del join de hilos.

Presenter Notes

Race condition!

 1 $ gcc-10 -O2 -fopenmp parallel-reduction-array-manual.c 
 2 $ perf stat -r 16 ./a.out 
 3 m[0]=268435451
 4 m[1]=1
 5 m[2]=1
 6 m[3]=1
 7 m[4]=1
 8 m[5]=1
 9 m[6]=0
10 ...
11 m[1]=0
12 m[2]=0
13 m[3]=1
14 m[4]=1
15 m[5]=1
16 m[6]=0
17 ...
18 m[0]=268435451
19 m[1]=2
20 m[2]=1
21 m[3]=1
22 m[4]=1
23 m[5]=2
24 m[6]=0

Presenter Notes

Caos

Sutilezas de OpenMP. Todo es tan, pero tan frágil.
Para Charlie:

Presenter Notes

Sutilezas de OpenMP

 1 unsigned int i = 0;
 2 #pragma omp parallel firstprivate(mp) shared(a,m)
 3 {
 4     #pragma omp for
 5     for(i=0; i<N; ++i)
 6         mp[a[i]]++;
 7     for(i=0; i<Q; ++i) {
 8         #pragma omp atomic
 9         m[i] += mp[i];
10     }
11 }

En el segundo for la variable i de lazo es ¿privada o compartida? Debería ser privada, pero es compartida. JUAAAA!
Confunde que el primer for la declara como privada, pero solo en el scope de ese for.

Presenter Notes

Solución

Agregar private(i).

 1 unsigned int i = 0;
 2 #pragma omp parallel firstprivate(mp) private(i) shared(a,m)
 3 {
 4     #pragma omp for
 5     for(i=0; i<N; ++i)
 6         mp[a[i]]++;
 7     for(i=0; i<Q; ++i) {
 8         #pragma omp atomic
 9         m[i] += mp[i];
10     }
11 }

Probamos 1024 veces a ver si tira diferencias

1 $ ./a.out > base.out; for i in {0..1023}; do ./a.out | diff base.out -; done
2 $

Parece correcto.

Consejo: usar default(none) asi nos fuerza a declarar todas las variables.

Presenter Notes

reduction de un arreglo

La papa, que el compilador se arregle:

 1 #define Q 7 /* discretización del histograma */
 2 #define N (1<<28) /* largo del vector */
 3 
 4 unsigned int a[N] = {1,2,3,4,5}; /* vector de muestras en el rango [0,Q) */
 5 unsigned int m[Q] = {0}; /* histograma */
 6 
 7 int main(void) {
 8     unsigned int i = 0;
 9     #pragma omp parallel for reduction(+:m)
10     for(i=0; i<N; ++i)
11         m[a[i]]++;
12     for(i=0; i<Q; ++i)
13         printf("m[%d]=%d\n",i,m[i]);
14 
15     return 0;
16 }

Lo que hace OpenMP es complejo y a la vez, correcto.
Aplauso, medalla y beso.

Presenter Notes

Threadprivate

#pragma omp threadprivate(list)

Declaración de variables persistentes en cada hilo.

Apareado con copyin para inicializar valores.

Flush

#pragma omp flush [(list)]

Atacar el problema de consistencia, es decir cuando los otros procesadores ven las escrituras.

Hay flushes implícitos:

  • Todas las barreras implícitas y explícitas.
  • Entrar y salir de una región critical.
  • Entrar y salir de las rutinas de locking.
    • Si, hay locking explícito.
    • omp_init_lock, omp_destroy_lock, omp_set_lock, omp_unset_lock y omp_test_lock.

Presenter Notes

Algunas cosas más (OpenMP 3.0)

Paralelismo anidado

Fusionar lazos para generar más trabajo lineal para dividir en el team.

1 #pragma omp for collapse(2)
2     for (i = 0; i < N; i++)
3         for (j = 0; j < M; j++)
4             for (k = 0; k < K; k++)
5                 foo(i, j, k);

Presenter Notes

Tasks (OpenMP 3.0)

División en tareas no-estructuradas #pragma omp task.

  • Lazos que no tienen cota (conocida).
  • Algoritmos recursivos.

Paralelismo en estructuras de datos no-regulares.

  • Listas, árboles, grafos, octrees, ...
  • Mallas irregulares (AMR).

Es trabajo asíncrono.

  • Puede ser ejecutado ya, luego o más tarde.
  • Puede cambiar de hilo de ejecución untied.

Se puede sincronizar: #pragma omp taskwait

Presenter Notes

Ejemplo clásico, que no sirve para nada

 1 int fib(int n) {
 2     int i, j;
 3     if (n < 2)
 4         return n;
 5     #pragma omp task shared(i)
 6     i = fib(n - 1);
 7     #pragma omp task shared(j)
 8     j = fib(n - 2);
 9     #pragma omp taskwait
10     return i + j;
11 }
  • Paralelismo de grano fino.
  • Te mata el overhead (probar sin -fopenmp)

Consejos

  • En algoritmos no-regulares, es muy útil.
  • Manejar el spawning de tasks para que no sean ni tantos ni tan pocos.
  • Usar cláusula if para cortar la creación de tareas por abajo de un umbral.

Presenter Notes

Tasks es la posta

Dividir en tareas de un tamaño razonable:

  • Paralelismo dinámico, en runtime.
  • Se pueden alimentar muchos procesadores fácilmente.
  • Evitamos problemas de load balancing.

Presenter Notes

Ejemplo, suma task-based

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <omp.h>
 4 
 5 #define N (1<<30)
 6 #define THRESHOLD (1<<22)
 7 float a[N];
 8 
 9 float sum(float * const restrict ptr, const size_t n) {
10     float s0 = 0.0f, s1 = 0.0f;
11     if (n<THRESHOLD) {
12         float s = 0.0f;
13         // please vectorize, unroll this
14         for (size_t i=0; i<n; ++i)
15             s += ptr[i];
16         return s;
17     }
18     #pragma omp task shared(s0)
19     s0 = sum(ptr, n/2);
20     #pragma omp task shared(s1)
21     s1 = sum(ptr+n/2, n/2);
22     #pragma omp taskwait
23     return s0+s1;
24 }
25 
26 int main(int argc, char **argv)
27 {
28     #pragma omp parallel
29     {
30     #pragma omp single
31     printf("%d\n", sum(a,N)); // Lost Ina Seaof Parentheses
32     }
33 }
34 
35 // gcc-10 -fopenmp -O1 -ftree-vectorize -ffast-math parallel-task-sum.c && perf stat -r 16 ./a.out

Presenter Notes

Task-based suma de 2³⁰ elementos

Genera 256 tasks de 2²² elementos cada uno

Comparación de eficiencia

Task
gcc-10 -fopenmp -O1 -ftree-vectorize -ffast-math sum-task.c && perf stat -r 16 ./a.out

OpenMP SIMD
gcc-10 -O1 -ffast-math -fopenmp sum-omp.c && perf stat -r 16 ./a.out

Autopar
gcc-10 -O1 -ftree-vectorize -ffast-math -ftree-parallelize-loops=28 sum.c && perf stat -r 16 ./a.out

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • OpenMP affinity, o como mapear bien los hilos para que estén cerca de la memoria.

Presenter Notes