OpenMP 2

Presenter Notes

Resumen:

  • Seguimos con OpenMP.

Nicolás Wolovick 20180508

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

reduction de un arreglo

Este programa muy sencillo y útil parallel-reduction-array.c

 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 }

Presenter Notes

reduction de un arreglo, peeroooo

Intentamos compilarlo con un gcc viejo.

1 $ gcc-5 -fopenmp parallel-reduction-array.c && perf stat -d ./a.out
2 parallel-reduction-array.c:13:36: error: user defined reduction not found for ‘m’
3 #pragma omp parallel for reduction(+:m)
4                                     ^

No es válido en C/C++ viejo, aunque si vale en Fortran! Por suerte ...

 1 $ gcc-8 -O2 -fopenmp parallel-reduction-array.c && perf stat -d ./a.out
 2 m[0]=268435451
 3 m[1]=1
 4 ...
 5 m[5]=1
 6 m[6]=0
 7 Performance counter stats for './a.out':
 8     828.136696      task-clock (msec)         #    1.644 CPUs utilized          
 9            229      context-switches          #    0.277 K/sec                  
10              0      cpu-migrations            #    0.000 K/sec                  
11         16,458      page-faults               #    0.020 M/sec                  
12  2,191,327,387      cycles                    #    2.646 GHz                      (48.38%)
13  1,640,350,632      instructions              #    0.75  insn per cycle           (74.26%)
14    324,315,970      branches                  #  391.621 M/sec                    (76.48%)
15        420,968      branch-misses             #    0.13% of all branches          (75.14%)
16    0.503626438 seconds time elapsed

Presenter Notes

||-reduction-manual-naive.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 
10 int main(void)
11 {
12     unsigned int i = 0;
13     #pragma omp parallel shared(a,m)
14     {
15         #pragma omp for
16         for(i=0; i<N; ++i)
17             //#pragma omp critical
18             #pragma omp atomic
19             m[a[i]]++;
20     }
21     for(i=0; i<Q; ++i)
22         printf("m[%d]=%d\n",i,m[i]);
23 
24     return 0;
25 }

Peformance en la misma máquina: atomic 4.5s, critical 15s.

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

Ejecutamos versión manual

 1 $ gcc-8 -O2 -fopenmp parallel-reduction-array-manual.c && perf stat ./a.out
 2 m[0]=268435451
 3 m[1]=1
 4 m[2]=1
 5 m[3]=1
 6 m[4]=1
 7 m[5]=1
 8 m[6]=0
 9 
10 Performance counter stats for './a.out':
11 
12     815.945283      task-clock (msec)         #    1.803 CPUs utilized          
13            178      context-switches          #    0.218 K/sec                  
14              0      cpu-migrations            #    0.000 K/sec                  
15         16,458      page-faults               #    0.020 M/sec                  
16  2,148,344,218      cycles                    #    2.633 GHz                      (50.07%)
17  1,653,189,150      instructions              #    0.77  insn per cycle           (75.13%)
18    322,194,708      branches                  #  394.873 M/sec                    (75.10%)
19        373,786      branch-misses             #    0.12% of all branches          (74.82%)
20 
21    0.452670168 seconds time elapsed

Presenter Notes

False sharing version

Ejercicio para el lector.

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

 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 spawing 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<<28)
 6 #define THRESHOLD (1<<20)
 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-8 -fopenmp -O1 -ftree-vectorize -ffast-math parallel-task-sum.c && perf stat -d ./a.out

Presenter Notes

Task-based suma de 2²⁸ elementos

Genera 256 tasks de 2²⁰ elementos cada uno

Comparación de eficiencia

  • 256 tasks: 0.082
  • Autoparalelización: 0.059
  • OpenMP con cláusula simd: 0.056

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

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

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

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • OpenMP cont'd.

Presenter Notes