OpenMP 1

Presenter Notes

Resumen:

La abstracción proceso.
OpenMP.

Nicolás Wolovick 20160426

Presenter Notes

Procesos

Presenter Notes

Proceso

Abstracción de un µP.

CPU.
Memoria.

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.

Relación entre procesos y µP

Antes: m procesos, 1 µP.
Ahora: m procesos, n procesadores.

Importancia

¿Cómo aseguro que 1 proceso vaya a 1 µP?

Me puedo mandar mocos grandes.
Hay que saber manejar bien los resouce managers como SLURM.

Presenter Notes

¿Cómo se crean procesos? `fork()`

How fork operates

Cada proceso tiene una memoria (virtual) disjunta.

Está bárbaro para parameter sweeping.
¿Cómo hago para que varios µP trabajen sobre los mismos datos compartidos?

Presenter Notes

LWP o Hilos

Creating a thread

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).

Presenter Notes

Un programa usando hilos (`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 }

Presenter Notes

Varias cosas

Públicas y privadas (globales y locales)

Globales: x.
Locales: d.

Hay 1 copia de x y 2 copias de d.

¿Qué hace este programa?

La teoría dice que no tiene que fallar.
La práctica dice otra cosa.

Atomicidad

Fundamental en concurrencia.
La corrección del código paralelo es un dolor de cabeza (race-conditions).

¿Tengo que hacer este lío para usar multicore?

¡OpenMP al rescate!

Presenter Notes

La multiprogramación es un lío

Código sintácticamente secuencial pero de semántica paralela.
Localidad de las variables.
Race-conditions.

¿Porqué no programamos todos en MPI y nos dejamos de molestar?
(no es un chiste: Threads — Threat or Menace?)

Presenter Notes

OpenMP

Presenter Notes

Multicomputadoras

Computadoras de memoria compartida y distribuida

(Using OpenMP, fig-1.2)

Presenter Notes

El Modelo fork-join

OpenMP Fork Join

(Using OpenMP, fig-2.1)

Presenter Notes

Como programar una multicomputadora

Hay dos estandar de-facto para programación paralela (memoria compartida):

PThreads y OpenMP.

Ambos utilizan el modelo fork-join.

Un hilo maestro lanza (fork) los hilos.
Cada hilo ejecuta el mismo código.
- Un identificador de hilo tid, los diferencia.
Utilizan memoria compartida.
- Para comunicarse.
- Para tener datos locales thread private.
Utilizan instrucciones especiales y memoria compartida para sincronización.
- xchg, cmpxchg, etc.
Todos los hilos se juntan (join) en el maestro.

Presenter Notes

PThreads

Biblioteca estándar en *NIX modernos (aka POSIX circa 1995).
- Multi plataforma (ubuicuo).
- Multi lenguaje (bindings para cualquier cosa).
Control fino y explícito del paralelismo.
- Creación, destrucción, espera: pthread_create, pthread_cancel, pthread_join.
- Locks, semáforos, variables de condición, barreras: pthread_condwait, pthread_mutex_unlock, etc.
- Manejo de la memoria de muy bajo nivel.

Presenter Notes

OpenMP

Define una API (¿o ABI?) estandar para C, C++ y Fortran.
Existe un consorcio que regula el estándar (Architecture Review Board - ARB):
- Grandes jugadores: AMD, Intel, NVidia, Cray, Microsoft, Fujitsu, ...
Intenta ocultar la complejidad del modelo fork-join a través de:
- Decoraciones en el código fuente: #pragma omp parallel.
- Llamandos a bibliotecas: omp_get_thread_num().
- Planificación dinámica: schedule(dynamic).
- Configuración run-time: OMP_NUM_THREADS.
Soportado por varios compiladores:
- 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, ...
- Situación general: OpenMP compilers.

Presenter Notes

OpenMP ≥4.0

Tasks (paralelismo dinámico).
SIMD.
Aceleradoras.

¡Debería haber dado #pragma omp simd!

Presenter Notes

Hello Waldo

Presenter Notes

Mi primer programa

`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 }

Compilación, no-determinismo y configuración run-time

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!

Presenter Notes

Por dentro

 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

Arma la función para que ejecuten todos los hilos.
Fork y luego join de los hilos.

Presenter Notes

Extensiones OpenMP

Presenter Notes

Constructor de paralelización

#pragma omp parallel
{ structured block }

Lanza ejecución paralela, junta los hilos.

Cláusulas

Manejo de hilos.
Manejo de datos compartidos.

Cláusulas de manejo de hilos

num_threads(integer-expression): define cuantos hilos lanza.
if(scalar-expression): lanza los hilos si la expresión es distinta de 0.

Presenter Notes

Ejemplos de cláusulas de manejo de hilos

`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!

Presenter Notes

Cláusulas para datos compartidos

El problema es: ¿Qué hago con la memoria respecto a los hilos?

Memoria compartida (global scope) entre los hilos.
Memoria privada (local scope) de cada hilo.

Y en el caso de la memoria privada.

¿Cómo distribuyo la información en el fork? y,
¿Cómo la junto en el join?

Presenter Notes

Memoria compartida

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).

Presenter Notes

Memoria privada y desparramar

#pragma omp parallel private(i,j,k,l)

Cada hilo tiene su juego de variables en la memoria.
El valor es indeterminado al iniciar y al terminar.

Copiando desde el hilo maestro

#pragma omp parallel firstprivate(i,j)

Copiando desde el hilo maestro a variables persistentes de hilos (`threadprivate`)

#pragma omp parallel copyin(p,q)

.
.

variables threadprivate : persisten a través de regiones paralelas.

Presenter Notes

Memoria privada y juntar

Reducciones

#pragma omp parallel reduction(+:i)

Crea una variable privada por hilo.
Realiza el fork y ejecuta los hilos.
En el join sumariza con el operador todas las variables privadas en una sola que se copia al master.

`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

Presenter Notes

Distribuyendo trabajo en los hilos

Hay 3 constructores: for, sections, single.

Constructores para distribuir trabajo

(LLNL, OpenMP Tutorial)

Siempre dentro de un constructor parallel.

Presenter Notes

Constructor de lazos

#pragma omp for

Inmediatamente sucedido por un for con varias restricciones de sintaxis.
for(init; var relop bound; incr)

Ejemplo

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.

Semántica

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)

Presenter Notes

Política de planificación

schedule(kind[, chunksize])

Donde kind:

static: tamaño fijo de pedazo (chunk) se asigna round-robin a los hilos.
El último pedazo puede ser más chico (resto de la división).
Si no se especifica el pedazo, el rango se divide en partes iguales.
dynamic: threadpool de pedazos de tamaño fijo.
Los hilos van tomando pedazos en orden arbitrario hasta que no hay más pedazos.
El valor por defecto del pedazo es 1.
guided: threadpool de pedazos de tamaño decreciente. El tamaño de los bloques van decreciendo en cada iteración según:
number_of_iterations_remaining / number_of_threads.
El tamaño del pedazo indica el tamaño mínimo.
El valor por defecto del pedazo es 1.
auto: el compilador y/o el runtime lo definen.
runtime: controlado por la variable de entorno OMP_SCHEDULE.

Presenter Notes

Política de planificación, gráfico

Ilustración de las planificaciones

(Using OpenMP, fig-4.44)

Presenter Notes

Política de planificación, ejemplo

Ver openmp_mandel. Acá un snapshot de guided.

openmp-mandel guided ordered

(Joel Yliluoma, Guide into OpenMP)

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.

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

(LLNL, OpenMP Tutorial)

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

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

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);

Presenter Notes

Ejemplo: `reduction` a mano

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]; /* 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!

Presenter Notes

`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 }

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.

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

Bibliografía

Presenter Notes

Bibliografía

Charles Severance, Kevin Dowd, "High Performance Computing", Connexions, 2010, CC3.0.
Barbara Chapman, Gabriele Jost y Ruud van der Pas, Using OpenMP, Portable Shared Memory Parallel Programming, MIT Press, 2007.
Michael Süß and Claudia Leopold, Common Mistakes in OpenMP and How To Avoid Them, 2006.
Blaise Barney, OpenMP Tutorial, LLNL, 2012.
Joel Yliluoma, Guide into OpenMP: Easy multithreading programming for C++, 2008.
Keld Helsgaun, How to Get Good Performance by Using OpenMP, 2010.

Presenter Notes

La clase que viene

OpenMP cont'd.

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

Relación entre procesos y µP

Importancia

Públicas y privadas (globales y locales)

¿Qué hace este programa?

Atomicidad

¿Tengo que hacer este lío para usar multicore?

parallel-hello.c

Compilación, no-determinismo y configuración run-time

Cláusulas

Cláusulas de manejo de hilos

parallel-hello-clauses-threads.c

Copiando desde el hilo maestro

Copiando desde el hilo maestro a variables persistentes de hilos (threadprivate)

Reducciones

parallel-reduction.c

Ejemplo

Semántica

Compartir datos

Sincronización

parallel-ordered.c

parallel-sections.c

Cláusulas

Barreras

Secuencial

parallel-reduction-array.c

Flush

Paralelismo anidado

Consejos

Table of Contents

Help

`parallel-hello.c`

`parallel-hello-clauses-threads.c`

Copiando desde el hilo maestro a variables persistentes de hilos (`threadprivate`)

`parallel-reduction.c`

`parallel-ordered.c`

`parallel-sections.c`

`parallel-reduction-array.c`