OpenMP 1

Presenter Notes

Resumen:

  • La abstracción proceso.
  • OpenMP.

Nicolás Wolovick 20200427

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 - LWP.
(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 compartida en el .data
 6 
 7 void *IncDec(void *arg) {
 8     int d = 1; // variable local en el stack o registros
 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

Soluciones a las race conditions

Limitar el no-determinismo de la ejecución concurrente.

Primitivas de sincronización

  • Sumas atómicas.
  • Mutex.
  • Semáforos.
  • Variables de condición.

Ver
incdec_atomic.c,
incdec_lock.c,
incdec_volatile.c.

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

.

.

.

.

.

.

.

.

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.

Presenter Notes

Compiladores que lo soportan

LLVM un poquito más atrasado que gcc.

Presenter Notes

OpenMP ≥4.0

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

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, configuración run-time y modelo abstracto de ejecución

1 $ gcc-10 -fopenmp parallel-hello.c && OMP_NUM_THREADS=5 ./a.out
2 Thread 0: Hello Waldo!
3 Thread 4: Hello Waldo!
4 Thread 3: Hello Waldo!
5 Thread 2: Hello Waldo!
6 Thread 1: Hello Waldo!

Presenter Notes

Por dentro

1 clang-9 -S -O1 -fopenmp parallel-hello.c

Miramos el assembler

 1 main:
 2     pushq   %rax
 3     movl    $.L__unnamed_1, %edi
 4     movl    $.omp_outlined., %edx
 5     xorl    %esi, %esi
 6     xorl    %eax, %eax
 7     callq   __kmpc_fork_call
 8     xorl    %eax, %eax
 9     popq    %rcx
10     retq
11 .omp_outlined.:
12     pushq   %rax
13     callq   omp_get_thread_num
14     movl    $.L.str, %edi
15     movl    %eax, %esi
16     xorl    %eax, %eax
17     popq    %rcx
18     jmp printf
  • 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-10 -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 independientemente si se definieron como:

  • automática (stack variables).
  • 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 / registros.
  • 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 resume 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 128 veces y nos fijamos si cambia.

1 $ gcc-10 -fopenmp parallel-reduction.c && for i in {0..127}; do OMP_NUM_THREADS=4 ./a.out; done | sort | uniq -c
2     128 6

Presenter Notes

Distribuyendo trabajo en los hilos

Hay 3 constructores: for, sections, single.

Constructores para distribuir trabajo

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

Esquemas más claros

Presenter Notes

Política de planificación, ejemplo

Ver openmp_mandel. Acá un snapshot de guided.

openmp-mandel guided ordered

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • OpenMP cont'd.

Presenter Notes