Nicolás Wolovick 20180508
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);
reduction
de un arregloEste 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 }
reduction
de un arreglo, peerooooIntentamos 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
||-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.
||-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 $ 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
Ejercicio para el lector.
#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<<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
Genera 256 tasks de 2²⁰ elementos cada uno
simd
: 0.056Task
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
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 |