Nicolás Wolovick 20160426
Abstracción de un µP.
El gran truco de la X1 y IBM/360.
Abstracción básica para los time-sharing systems.
Se puede hacer hasta en un 6502 con FUZIX.
Antes: m procesos, 1 µP.
Ahora: m procesos, n procesadores.
¿Cómo aseguro que 1 proceso vaya a 1 µP?
fork()
Cada proceso tiene una memoria (virtual) disjunta.
Virtualiza menos cosas que un proceso, por eso es un LightWeight Process.
(no le digan a nadie, es solo una implementación para que funcione más rápido)
Privado: µP (registros, PSW, IP), stack (pila de llamadas, variables automáticas).
Compartido: variables globales, variables estáticas, memoria dinámica (malloc
).
pthreads
) 1 #include <stdio.h>
2 #include <assert.h>
3 #include <pthread.h>
4
5 int x = 0; // variable global y compartida
6
7 void *IncDec(void *arg) {
8 int d = 1; // variable local
9 while(1) {
10 x = x+d;
11 x = x-d;
12 }
13 }
14
15 int main(void) {
16 pthread_t t0id,t1id;
17 pthread_create(&t0id, NULL, IncDec, NULL);
18 pthread_create(&t1id, NULL, IncDec, NULL);
19 /* sonda que comprueba el Invariante */
20 while(1) {
21 assert(0<=x && x<=2); /* Inv: 0<=x<=2 */
22 printf("%2d", x);
23 }
24 }
Globales: x
.
Locales: d
.
Hay 1 copia de x
y 2 copias de d
.
La teoría dice que no tiene que fallar.
La práctica dice otra cosa.
Fundamental en concurrencia.
La corrección del código paralelo es un dolor de cabeza (race-conditions).
¡OpenMP al rescate!
¿Porqué no programamos todos en MPI y nos dejamos de molestar?
(no es un chiste: Threads — Threat or Menace?)
(Using OpenMP, fig-1.2)
(Using OpenMP, fig-2.1)
Hay dos estandar de-facto para programación paralela (memoria compartida):
PThreads y OpenMP.
Ambos utilizan el modelo fork-join.
tid
, los diferencia.xchg
, cmpxchg
, etc.pthread_create
, pthread_cancel
, pthread_join
.pthread_condwait
, pthread_mutex_unlock
, etc.#pragma omp parallel
.omp_get_thread_num()
.schedule(dynamic)
.OMP_NUM_THREADS
.gcc
≥4.2 OpenMP 2.5, ≥4.4 OpenMP 3.0, ≥4.7 OpenMP 3.1, ...icc
≥10.1 OpenMP 2.5, ≥11.0 OpenMP 3.0, ...clang
>=3.2 OpenMP 3.1, ...¡Debería haber dado #pragma omp simd
!
parallel-hello.c
1 #include <stdio.h>
2 #include <omp.h>
3
4 int main(void)
5 {
6 #pragma omp parallel
7 {
8 printf("Thread %d: Hello Waldo!\n", omp_get_thread_num());
9 }
10
11 return 0;
12 }
1 $ gcc -fopenmp parallel-hello.c
2 $ OMP_NUM_THREADS=5 ./a.out
3 Thread 0: Hello Waldo!
4 Thread 4: Hello Waldo!
5 Thread 3: Hello Waldo!
6 Thread 2: Hello Waldo!
7 Thread 1: Hello Waldo!
1 main:
2 .LFB0:
3 ...
4 movl $0, %edx
5 movl $0, %esi
6 movl $main._omp_fn.0, %edi
7 call GOMP_parallel_start
8 movl $0, %edi
9 call main._omp_fn.0
10 call GOMP_parallel_end
11 movl $0, %eax
12 ret
13 ...
14 main._omp_fn.0:
15 .LFB1:
16 ...
17 call omp_get_thread_num
18 movl %eax, %edx
19 movl $.LC0, %eax
20 movl %edx, %esi
21 movq %rax, %rdi
22 movl $0, %eax
23 call printf
24 ret
#pragma omp parallel
{ structured block }
Lanza ejecución paralela, junta los hilos.
num_threads(
integer-expression)
: define cuantos hilos lanza.if(
scalar-expression)
: lanza los hilos si la expresión es distinta de 0
.parallel-hello-clauses-threads.c
1 #include <stdio.h>
2 #include <omp.h>
3
4 int main(int argc, char **argv)
5 {
6 #pragma omp parallel num_threads(argc) if(2<argc)
7 {
8 printf("Thread: %d: Hello Waldo!\n", omp_get_thread_num());
9 }
10
11 return 0;
12 }
El if
es muy útil para no paralelizar cuando el tamaño del problema no lo justifica.
1 $ gcc -fopenmp parallel-hello-clauses-threads.c
2 $ ./parallel-hello-clauses-threads a
3 Thread: 0: Hello Waldo!
4 $ ./parallel-hello-clauses-threads a b
5 Thread: 2: Hello Waldo!
6 Thread: 0: Hello Waldo!
7 Thread: 1: Hello Waldo!
El problema es: ¿Qué hago con la memoria respecto a los hilos?
Y en el caso de la memoria privada.
1 int a, *b, c;
2 double d;
3 d=malloc(1<<20);
4 #pragma omp parallel shared(a,b,c,d)
Todos los hilos ven la misma memoria ya sea automática (stack variables) o
manual (globals y heap).
Usualmente hay que sincronizar los accesos a memoria compartida para limitar el no-determinismo a interleavings permitidos (aka, evitar race conditions).
#pragma omp parallel private(i,j,k,l)
#pragma omp parallel firstprivate(i,j)
threadprivate
)#pragma omp parallel copyin(p,q)
.
.
variables threadprivate : persisten a través de regiones paralelas.
#pragma omp parallel reduction(+:i)
parallel-reduction.c
1 unsigned int i = 0;
2 #pragma omp parallel reduction(+:i)
3 {
4 i+=omp_get_thread_num();
5 }
6 printf("%d\n",i);
Ejecutamos
1 $ gcc -fopenmp parallel-reduction.c && OMP_NUM_THREADS=4 ./a.out
2 6
3 $ gcc -fopenmp parallel-reduction.c && OMP_NUM_THREADS=4 ./a.out
4 6
Hay 3 constructores: for
, sections
, single
.
(LLNL, OpenMP Tutorial)
Siempre dentro de un constructor parallel
.
#pragma omp for
Inmediatamente sucedido por un for
con varias restricciones de sintaxis.
for(init; var relop bound; incr)
1 unsigned int i = 0;
2 #pragma omp parallel
3 {
4 #pragma omp for
5 for(i=0; i<200; ++i) {
6 a[i]*=a[i];
7 }
8 }
Se pueden colapsar y poner directamente #pragma omp parallel for
.
Dividir el rango del for
según una política de planificación.
En este caso de planificación estática por defecto, para 2 hilos tenemos:
hilo 0: i∈[0,100)
hilo 1: i∈[100,200)
schedule(kind[, chunksize])
Donde kind
:
static
: tamaño fijo de pedazo (chunk) se asigna round-robin a los hilos.dynamic
: threadpool de pedazos de tamaño fijo.1
.guided
: threadpool de pedazos de tamaño decreciente.
El tamaño de los bloques van decreciendo en cada iteración según:1
.auto
: el compilador y/o el runtime lo definen.runtime
: controlado por la variable de entorno OMP_SCHEDULE
. (Using OpenMP, fig-4.44)
Ver openmp_mandel
.
Acá un snapshot de guided
.
(Joel Yliluoma, Guide into OpenMP)
shared
y private
: como en parallel
.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.parallel
no la admite.nowait
: elimina la barrera final de for
.ordered
solo declara que puede existir un bloque ordered
.ordered
se ejecuta de manera secuencial,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.
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.
private
.shared
.firstprivate
.lastprivate
: el órden es el dado por las secciones dentro del código fuente.reduction
.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 team.master
#pragma omp master
{ structured block }
Variación de single
:
(LLNL, OpenMP Tutorial)
#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
Escencialmente 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 proteje. El read-modify-write luego de la llamada si es atómico.
1 #pragma omp atomic
2 a *= func(b);
reduction
a manoEste 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]; /* 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 }
Intentamos compilarlo.
1 $ gcc -fopenmp parallel-reduction-array.c && ./a.out
2 parallel-reduction-array.c: In function ‘main’:
3 parallel-reduction-array.c:13:36: error: user defined reduction not found for ‘m’
4 #pragma omp parallel for reduction(+:m)
5 ^
No es válido en C/C++. Aunque si vale en Fortran!
parallel-reduction-manual.c
1 #include <stdio.h>
2 #include <omp.h>
3
4 #define Q 7 /* discretización del histograma */
5 #define N (1<<26) /* largo del vector */
6
7 unsigned int a[N]; /* 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 a[i] = i%Q;
18
19 #pragma omp for
20 for(i=0; i<N; ++i)
21 mp[a[i]]++;
22
23 for(i=0; i<Q; ++i) {
24 #pragma omp atomic
25 m[i] += mp[i];
26 }
27 }
28 for(i=0; i<Q; ++i)
29 printf("m[%d]=%d\n",i,m[i]);
30
31 return 0;
32 }
#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 }
if
para cortar la creación de tareas por abajo de un umbral.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 |