1 Ejemplos openMP

2 Hello World #include #include int main (int argc, char *argv[]) { int p,th_id; p=omp_get_num_procs(); omp_set_num_threads(p); #pragma omp parallel private(th_id); { th_id = omp_get_thread_num(); printf("Hello World from thread %d\n", th_id); } return 0;

3 El algoritmo de Floyd paralelizadofor (k= 0;k #pragma omp parallel for private(j) for (i =0;i< n;i++) for (j= 0;j a[i,j]  min (a[i,j], a[i,k] + a[k,j]) Mejor paralelizar el segundo bucle en vez del tercero para evitar el costo de “fork join” repetido

4 Aproximar π mediante la “regla de rectangulos”#include #include #include #include int main (int argc, char *argv[]) { double area,x; int i,n; area = 0.0; printf("n="); scanf("%d",&n); #pragma omp parallel for private(x) reduction(+:area); for (i=0;i x=(i+0.5)/n; area += 4.0/(1.0+x*x); } printf("pi = %lf\n", area/n); return 0;

5 Aproximar pi por el método Monte Carlo#include #include int main(int argc,char *argv[]) { int count; int i; int local_count; int samples; int t; int tid; double x,y; unsigned short xi[3]; samples=atoi(argv[1]); omp_set_num_threads(atoi(argv[2])); count=0;

6 Método Monte Carlo (cont)#pragma omp parallel private(xi,t,i,x,y,local_count); { local_count=0; xi[0]=atoi(argv[3]); xi[1]=atoi(argv[4]); xi[2]=tid=omp_get_thread_num(); t = omp_get_num_threads(); for (i=tid;i x=erand48(xi); y=erand48(xi); if(x*x + y*y <= 1.0) local_count +=1; } #pragma omp critical count += local_count; printf("Estimate of pi: %7.5f\n",4.0*count/samples);

7 La multiplicación matríz-vectorPara computar y = Ax = [aij]x donde A es m X n y x es n X 1: for (i=0;i y[i] = 0; for (j=0;j y[i] = y[i] + A[i][j] * x[j]; } f

8 Paralelizar el bucle exterior#pragma omp parallel for private(j) for (i=0;i y[i] = 0; for (j=0;j y[i] = y[i] + A[i][j] * x[j]; } f

9 Paralelizar el bucle interiorfor (i=0;i tmp = 0.0; #pragma omp parallel for reduction(+:tmp) for (j=0;j tmp = tmp + A[i][j] * x[j]; y[i]=tmp; } f

10 Matrices Esparcidas Una matríz es esparcida si la mayoria de sus elementos son iguales a cero. Los algoritmos ordinarios aplicados a matrices esparicidas, no son lo mas eficientes pues ocupan mucho espacio y gastan operaciones de mas.

11 “Compressed Sparse Row Format” (CSR)El format de fila esparcida comprimida consiste de: (1) Un arreglo, vals, de los elementos no cero de tamaño nz, donde nz es el número de elementos no cero. (2) Un arreglo, cols, de tamaño nz de los números de columna en las cuales cada elemento de vals aparece. (3) Un arreglo, filas, de tamaño n+1 donde los elementos de la fila i se encuentran en las posiciones fila[i], fila[i]+1,…, fila[i+1]-1 del arreglo vals y fila[n] contains nz.

12 La multiplicación de una matriz nXn en el formato CSR por un vectorfor(i=0;i { y[i]=0; for(k=filas[i];k {j=cols[k]; y[i] += vals[k]*x[j]; }

13 Paralelizar el bucle exterior#pragma omp parallel for private(j,k) for(i=0;i { y[i]=0; for(k=filas[i];k {j=cols[k]; y[i] += vals[k]*x[j]; }

14 Paralelizar el bucle interiorfor(i=0;i { y[i]=0; #pragma omp parallel for reduction(+:y[i]) for(k=filas[i];k {j=cols[k]; y[i] += vals[k]*x[j]; }

15 Experimentos (1) Investigar el speedup para las dos versiones anteriores usando matrices aleatorias. Vease sparsematvec.c (2) Investigar el speedup en el caso de matrices donde la cantidad de elementos no cero varia mucho de una fila a otra. (Podria atrasar la ejecutación (“load imbalance”).

16 Se podria probar “scheduling”Por ejemplo: #pragma omp parallel for private(j,k) schedule(guided,4) for(i=0;i { y[i]=0; for(k=filas[i];k {j=cols[k]; y[i] += vals[k]*x[j]; }

17 Otras posibilidades schedule(dynamic) iteraciones se asignan dinamícamente una a la vez a los hilos Schedule(dynamic,C) C iteraciones se asignan dinamícamente as los hijos

18 Un Programa openMP para Resolver el Problema de Satisfacer un Circuito

19 NOT Gate 4–19

20 AND Gate 4–20

21 OR Gate 4–21

22 Circuitos Lógicos Los gates se combinan en circuitos usando la salida de un gate como la entrada de otra.

23 Determinar cuantas combinaciones de entradas satisfacen el circuito

24 Satisfacer un Circuito en openMP#include #include #include #include //int check_circuit(int,int); int main (int argc, char *argv[]) { int global_solutions; int i; int id; int hilos; int solutions; int lo,hi; int N=65536; int check_circuit(int,int); //hilos=omp_get_num_threads( ); global_solutions = 0;

25 Satisfacer un Circuito (cont)#pragma omp parallel private(lo,hi,id,i,solutions) reduction(+:global_solutions) { hilos=omp_get_num_threads( ); id = omp_get_thread_num( ); lo = id*N/hilos; hi = (id+1)*N/hilos; solutions=0; for (i=lo;i solutions += check_circuit(id,i); global_solutions += solutions; } printf("El numero de soluciones es %d\n",global_solutions); return 0;

26 check_circuit /* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */#define EXTRACT_BIT(n,i) ((n&(1< void check_circuit (int id, int z) { int v[16]; /* Each element is a bit of z */ int i; for (i = 0; i < 16; i++) v[i] = EXTRACT_BIT(z,i); if ((v[0] || v[1]) && (!v[1] || !v[3]) && (v[2] || v[3]) && (!v[3] || !v[4]) && (v[4] || !v[5]) && (v[5] || !v[6]) && (v[5] || v[6]) && (v[6] || !v[15]) && (v[7] || !v[8]) && (!v[7] || !v[13]) && (v[8] || v[9]) && (v[8] || !v[9]) && (!v[9] || !v[10]) && (v[9] || v[11]) && (v[10] || v[11]) && (v[12] || v[13]) && (v[13] || !v[14]) && (v[14] || v[15])) { printf ("%d) %d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n", id, v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9], v[10],v[11],v[12],v[13],v[14],v[15]); fflush (stdout); }

27 Otra solucion utilizando un bucle for paralelo#include #include #include #include //int check_circuit(int,int); int main (int argc, char *argv[]) { int global_solutions; int i; int id; int hilos; int solutions; int lo,hi; int N=65536; int check_circuit(int,int); //hilos=omp_get_num_threads( ); #pragma omp parallel for reduction(+:global_solutions) for (i=0;i global_solutions += check_circuit(id,i); //global_solutions += solutions; printf("El numero de soluciones es %d\n",global_solutions); return 0; }