Nicolás Wolovick 20200427
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 - 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
).
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 }
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!
Limitar el no-determinismo de la ejecución concurrente.
Ver
incdec_atomic.c
,
incdec_lock.c
,
incdec_volatile.c
.
¿Porqué no programamos todos en MPI y nos dejamos de molestar?
(no es un chiste: Threads — Threat or Menace?)
.
.
.
.
.
.
.
.
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
.LLVM
un poquito más atrasado que gcc
.
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!
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
#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-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!
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 independientemente si se definieron como:
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 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
Hay 3 constructores: for
, sections
, single
.
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
. Ver openmp_mandel
.
Acá un snapshot de guided
.
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 |