OpenMP

Presenter Notes

Resumen

  • Introducción
  • Hello Waldo.
  • Extensiones OpenMP.
  • Bibiliografía.
  • Clase siguiente.

Nicolás Wolovick, $Date: 2012-05-08 14:16:34 -0300 (Tue, 08 May 2012) $, $Revision: 3501 $

Presenter Notes

Introducción

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.

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, mfence, 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 condicionales, barreras: pthread_condwait, pthread_mutex_unlock, etc.
    • Manejo de muy bajo nivel de la memoria.

Presenter Notes

OpenMP

  • Define una API (¿o ABI?) estandar para C, C++, 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.
    • icc >=10.1, OpenMP 2.5; >=11.0, OpenMP 3.0.
    • clang ¿Vendrá en clang-3.1?
    • Situación general: OpenMP compilers.

Presenter Notes

Hello Waldo

Presenter Notes

Mi primer programa

 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 -o parallel-hello
2 $ OMP_NUM_THREADS=5 ./parallel-hello 
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

 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 $ ./parallel-hello-clauses-threads a
2 Thread: 0: Hello Waldo!
3 $ ./parallel-hello-clauses-threads a b
4 Thread: 2: Hello Waldo!
5 Thread: 0: Hello Waldo!
6 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 entre los hilos.
  • Memoria privada 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 data races).

Presenter Notes

Memoria privada y desparramar

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

  • Cada hilo tiene su lugar 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)

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.

Ejemplo

1 unsigned int i = 0;
2 #pragma omp parallel reduction(+:i)
3 {
4     i+=omp_get_thread_num();
5 }
6 printf("%d\n",i);

Presenter Notes

Distribuyendo trabajo en los hilos

Hay 3 constructores: for, sections, single.

Constructores para distribuir trabajo

(LLNL, OpenMP Tutorial)

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 la 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.
  • 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.

Ejemplo

 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.

Ejemplo

 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.

#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 condiciones de carrera 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.

 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 */
 5 unsigned int m[Q] = {0}; /* histograma */
 6 
 7 int main(void)
 8 {
 9     unsigned int i = 0;
10     #pragma omp parallel reduction(+:m)
11     for(i=0; i<N; ++i) {
12         m[a[i]]++;
13     }
14     for(i=0; i<Q; ++i)
15         printf("m[%d]=%d\n",i,m[i]);
16 
17     return 0;
18 }

Intentamos compilarlo.

1 $ gcc -fopenmp parallel-reduction-manual.c -o parallel-reduction-manual
2 parallel-reduction-manual.c: In function ‘main’:
3 parallel-reduction-manual.c:13:32: error: ‘m’ has invalid type for ‘reduction’

No es válido en C/C++. Aunque si vale en Fortran!

Presenter Notes

Ejemplo: reduction a mano

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

  • Paralelismo anidado.
    • Nueva cláusula collapse del constructor de lazos (OpenMP 3.0).
  • Tasks: constructor task, sincronización taskwait (OpenMP 3.0).

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

Bugs comunes en OpenMP.

Implementación de las extensiones OpenMP.

Performance y escalabilidad en OpenMP.

  • Mostrarles intentos de superlinear speedup.

Charla de Daniel Gutson: Optimización mid (Graphite) y backend (ARM).

Presenter Notes