Nicolás Wolovick 20200504
shared
y private
: como en parallel
for
se declara private
de manera implícitafirstprivate
, copyin
: idemreduction
: idem. Muy usado en este constructorlastprivate
: el último valor que toma la variable según el orden del loop se copia al masterparallel
no la admitenowait
: elimina la barrera final de for
ordered
solo declara que puede existir un bloque ordered
ordered
se ejecuta de manera secuencialparallel-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.
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).
private
shared
firstprivate
lastprivate
: el órden es el dado por las secciones dentro del código fuentereduction
nowait
Ya conocemos su semántica.
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 }
private
firstprivate
copyprivate
: difunde el valor de salida de una variable privada al bloque a todos los hilos del teammaster
#pragma omp master
{ structured block }
Variación de single
:
#pragma omp barrier
Separa fases de computación.
#pragma omp ordered
{ structured block }
¡Ya visto!
#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:
#pragma omp critical
sin nombre.#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);
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)
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.
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
.
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
.atomic
4.5s, critical
15s.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
||-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.
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 $ 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
Sutilezas de OpenMP. Todo es tan, pero tan frágil.
Para Charlie:
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
.
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.
reduction
de un arregloLa 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.
#pragma omp threadprivate(list)
Declaración de variables persistentes en cada hilo.
Apareado con copyin
para inicializar valores.
#pragma omp flush [(list)]
Atacar el problema de consistencia, es decir cuando los otros procesadores ven las escrituras.
Hay flushes implícitos:
critical
.omp_init_lock
, omp_destroy_lock
, omp_set_lock
, omp_unset_lock
y omp_test_lock
.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);
División en tareas no-estructuradas #pragma omp task
.
Paralelismo en estructuras de datos no-regulares.
Es trabajo asíncrono.
untied
.Se puede sincronizar: #pragma omp taskwait
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 }
-fopenmp
)if
para cortar la creación de tareas por abajo de un umbral.Dividir en tareas de un tamaño razonable:
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
Genera 256 tasks de 2²² elementos cada uno
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
Table of Contents | t |
---|---|
Exposé | ESC |
Full screen slides | e |
Presenter View | p |
Source Files | s |
Slide Numbers | n |
Toggle screen blanking | b |
Show/hide slide context | c |
Notes | 2 |
Help | h |