2. computo en paralelo con openmp

Cmputo en paralelo con OpenMP

MSc Miguel [email protected]

http://www.cimat.mx/~miguelvargas

17/08/11 1/26

Contenido

Contenido

Cmputo en paraleloOperaciones matemticas en paraleloEl esquema OpenMPProgramacin con multi-hilos (multi-threads)Prdida de eficiencia con el aumento de procesadoresPreguntas?Para saber ms...

17/08/11 2/26

Cmputo en paralelo

Cmputo en paralelo

La evolucin de la velocidad de los procesadores

1970 1975 1980 1985 1990 1995 2000 2005 20100E+0

1E+10

2E+10

3E+10

4E+10

5E+10

6E+10

7E+10

8E+10

Inte

l 400

4(9

2K ip

s)

Inte

l 808

0(5

00K

ips)

Mot

orol

a 68

000

(1M

ips)

Inte

l 80x

286

(4M

ips)

Inte

l 80x

386

(11M

ips)

Mot

orol

a 68

040

(44M

ips)

Inte

l 80x

486

(54M

ips)

Mot

orol

a 68

060

(88M

ips)

Inte

l Pen

tium

Pro

(541

M ip

s)

Inte

l Pen

tium

III(1

.4G

ips)

AM

D A

thlo

n XP

(5.9

G ip

s)In

tel P

entiu

m IV

(9.7

G ip

s)

Play

Stat

ion

3 Ce

ll(1

0G ip

s)In

tel C

ore

2(4

9G ip

s)In

tel C

ore

i7(7

6G ip

s)A

MD

Phen

om II

X4(4

3G ip

s)

Nm

ero

de in

stru

ccio

nes

por s

egun

do

procesadoresmulti-core

Tenemos ahora que desarrollar nuevos esquemas para disear algoritmos

17/08/11 3/26

Cmputo en paralelo

Algoritmoen

serie

Algoritmoen

paralelo

La meta es reducir tiempo necesario para realizar una secuencia de instrucciones.

La buena noticia: Hacer programas en paralelo con OpenMP es muy sencillo.

La mala noticia: Hacer programas en paralelo eficientes requiere un esfuerzo extra.

17/08/11 4/26

Operaciones matemticas en paralelo


Fcilmente paralelizables

Esto significa que pueden separarse en varias sub-operaciones que puede realizarse de forma independiente. Por ejemplo, el la suma de dos vectores x, y para producir otro vector c,

ci=x i yi, i=1, , N.En este caso las N sumas pueden realizarse simultneamente, asignando una a cada procesador. Lo que hay que resaltar es que no hay dependencia entre los diferentes pares de datos, tenemos entonces el paralelismo ms eficiente.

No tan fciles de paralelizar

Por ejemplo el producto punto x , y

a=i=1

N

xi yi,

donde a es un escalar, una primera aproximacin sera verlo como una secuencia de sumas de productos que requieren irse acumulando, al verlo as no es una operacin paralelizable.Sin embargo, podemos reorganizar el proceso como se muestra en la figura:

17/08/11 5/26


a=i=1

N

xi yi

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x7 y7 x8 y8 xn yn...x9 y9

+

+

a

+ + +

+ +

...

x9 y9

+ ...

En este caso se tiene una paralelizacin eficiente de la multiplicacin de las entradas de los vectores, despus se va reduciendo la eficiencia. Muchos algoritmos seriales requieren, para ser paralelizados, de re-ordenar las operaciones con una estrategia de divide y vencers, como en el caso del producto punto.

17/08/11 6/26


Usualmente se tendrn memos procesadores que el tamao del vector, por lo que se asignan varias operaciones de un grupo a cada procesador, las cuales se ejecutarn en secuencia, lo que limita la eficiencia del paralelismo.

a=i=1

N

xi yi

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x7 y7 x8 y8 xn yn...x9 y9

+ +

+

a

...

17/08/11 7/26

El esquema OpenMP

El esquema OpenMP

Sirve para paralelizar programas en C, C++ o Fortran en computadoras multi-core o multi- thread.Busca que escribir cdigo en paralelo sea sencillo.Es un esquema de paralelizacin con memoria compartida (todos los procesadores accesan a la misma memoria).Su funcionamiento interno es con threads, en el caso de sistemas POSIX se utiliza la librera de POSIX-Threads (libpthread).

Algunos compiladores que soportan este esquema: GNU Compiler Collection GCC (versin >= 4.3.2) Intel Compiler Suite (version >= 10.1) Microsoft Visual Studio 2008 (Professional) Microsoft Visual Studio 2008 (Express) + Windows SDK for Windows Server 2008

La lista completa: http://openmp.org/wp/openmp-compilers

17/08/11 8/26

Programacin con multi-hilos (multi-threads)

Programacin con multi-hilos (multi- threads)

A la ejecucin secuencial de una conjunto de instrucciones se le conoce como un hilo de procesamiento o thread.

1 thread

3 threads

1 thread

3 threads

1 thread

17/08/11 9/26


En las computadoras multi-core logra la mejor eficiencia cuando cada CPU ejecuta slo un thread.

Core 1Core 2Core 3

Core n

Core 4Threadactivo

Threadinactivo

Procesamientoserial

Procesamientoparalelo

SincronizacinCreacin delos threads

t

Dentro de un programa, cada thread posee sus propios registros de control y su propio stack de datos, mientas que comparte el uso de la memorias del montculo (heap) y data con los dems threads del programa.

17/08/11 10/26


Un programa simple con OpenMP

Comencemos con la paralelizacin de la suma de dos vectores:

void Suma(double* a, double* b, double* c, int size){

for (int i = 0; i < size; ++i){

c[i] = a[i] + b[i];}

}

La paralelizacin sera...

17/08/11 11/26


...la paralelizacin sera:


#pragma omp parallel forfor (int i = 0; i < size; ++i){

c[i] = a[i] + b[i];}

}

Para compilar con GCC es necesario agregar:gcc -o programa -fopenmp main.c

En Visual C++ hay una opcin en las preferencias del proyecto para activar OpenMP.

17/08/11 12/26


Cmo funciona?

Supongamos que size = 30, si la computadora tiene 3 procesadores, el cdigo se ejecutara como:


#pragma omp parallel forfor (int i = 0; i < 10; ++i) for (int i = 10; i < 20; ++i) for (int i = 20; i < 30; ++i){ { {

c[i] = a[i] + b[i]; c[i] = a[i] + b[i]; c[i] = a[i] + b[i];} } }

}

Cmo se define el nmero de procesadores/threads a utilizar?- Por default el nmero de threads es igual al nmero de cores en la computadora.- Se puede establecer por medio de variables de ambiente- Se puede definir en el cdigo en run-time.

17/08/11 13/26


Establecer nmero de threads con variables de ambiente

Se hace a travs de la variable de ambiente OMP_NUM_THREADS

En Linux/Unix (Bash):export OMP_NUM_THREADS=3programa

En Windows:set OMP_NUM_THREADS=3programa.exe

17/08/11 14/26


Establecer nmero de threads con cdigo

Es necesario incluir el header omp.h, el cual incluye varias funciones para el control de threads.

#include

int threads = 3;


omp_set_num_threads(threads);

#pragma omp parallel forfor (int i = 0; i < size; ++i) {

c[i] = a[i] + b[i];}

}omp_set_num_threads( ) permite establecer el nmero de threads a utilizar en el futuro.

17/08/11 15/26


Reducciones

El ejemplo que mostraremos es el producto punto:double ProductoPunto(double* a, double* b, int size){

double c = 0;for (int i = 0; i < size; ++i)

c += a[i]*b[i];return c;

}Su paralelizacin sera:double ProductoPunto(double* a, double* b, int size){

double c = 0;#pragma omp parallel for reduction(+:c)for (int i = 0; i < size; ++i)

c += a[i]*b[i];return c;

}

17/08/11 16/26


Paralelizar bloques de cdigo

Adems de paralelizar ciclos, es posible paralelizar bloques

#pragma omp parallel{

// ... codigo a ejecutar en paralelo...int thread = omp_get_thread_num();

}

omp_get_thread_num regresa el nmero de thread actual.

17/08/11 17/26


Paralelizar secciones de cdigo

Se puede hacer que varias secciones de cdigo se ejecuten de forma simultnea

int threads = 2;#pragma omp parallel sections num_threads(threads){

#pragma omp section{

// ... algo de codigo}#pragma omp section{

// ... otro codigo}

}

Con num_threads( ) podemos especificar cuantos threads/cores se utilizarn. En este caso uno por cada seccin.

17/08/11 18/26


Variables private and shared

En el ejemplo del producto punto:double ProductoPunto(double* a, double* b, int size){

double c = 0;#pragma omp parallel for reduction(+:c)for (int i = 0; i < size; ++i){

c += a[i]*b[i];}return c;

}OpenMP hace considera a y b como variables compartidas (shared), es decir, todos los threads las pueden accesar y modificar.Para las variables del ciclo i y de la reduccin c, OpenMP hace un copias de las variables al stack de cada thread, con lo cual se convierten a privadas (private). Al terminar se sumarn las c de cada thread en la variable c que ahora se considerar shared.Adems, todas las variables declaradas dentro del bloque parallel sern privadas.

17/08/11 19/26


Tambin es posible decidir de forma explcita que variables queremos que tengan un comportamiento privado o shared.El siguiente ejemplo muestra como:

int i[10];int j = 5;float* a;float* b;#pragma omp parallel private(i) firstprivate(j) shared(a,b){

int k;// ... codigo ...

}

En este caso, tanto i, j y k sern privadas y a y b sern compartidas.

firstprivate indica que el valor de j se inicializar con el valor que tena antes del bloque parallel.

17/08/11 20/26


Schedule

Por default, al paralelizar un ciclo el nmero de iteraciones se divide por igual entre cada thread. Sin embargo, esto no es eficiente si las iteraciones tardan tiempos diferentes en ejecutarse.Es posible hacer entonces reajustar la distribucin de iteraciones de forma dinmica, esto se hace con schedule.

#pragma omp parallel for schedule(type[, chunk_size])for (int i = 0; i < size; ++i){

c[i] = a[i] + b[i];}

Los tipos de schedule son:static Las iteraciones se dividen en chunks de un tamao definido.dynamic Cada thread ejecuta un chunk de iteraciones y al terminar su parte busca otro chunk para procesar.guided Cada thread ejecuta un chunk de iteraciones y al terminar su parte busca otro chunk para procesar. El tamao del chunk vara, siendo grande al iniciar y ste se va reduciendo.auto La decicin del tipo de schedule es decidido por el compilador/sistema operativo.runtime El schedule y el tamao del chunk son tomados de la variable sched-var ICV.

17/08/11 21/26


Otro ejemplo

Ahora veamos la multiplicacin matriz-vector:

void Mult(double* A, double* x, double* y, int rows, int cols){

#pragma omp parallel forfor (int i = 0; i < rows; ++i){

double sum = 0;for (int k = 0; k < cols; ++k){

sum += A[i*cols + k]*x[k];}y[i] = sum;

}}Hay que notar que las operaciones no se interfieren, dado que cada iteracin slo escribe en el elemento y[i].

17/08/11 22/26


Secciones crticas

#pragma omp parallel forfor (int i = 0; i < 10; ++i){

...#pragma omp critical{

fwrite(file, %i\n, i);}

}

La ejecuccin dentro de un rea crtica se restringe a un solo thread a la vez.

17/08/11 23/26

Prdida de eficiencia con el aumento de procesadores


Ejemplo de un programa trabajando en una computadora con 16 procesadores/threads

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160.00

5.00

10.00

15.00

20.00

25.00

Tiempo real [m]Tiempo ideal [m]

Procesadores

Tiem

po [m

]

Sea t 1 el tiempo real que tard el resolverse un problema con un core, n el nmero de procesadores utilizado, el tiempo ideal de ejecucin lo podemos definir como

in=t1n .

17/08/11 24/26


Podemos dar una medida de eficiencia E de un algoritmo

E=int n=

t 1nt n

.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160.00

0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00

Procesadores

Efic

ienc

ia

17/08/11 25/26

Preguntas?

Preguntas?

[email protected]://www.cimat.mx/~miguelvargas

Bibliografa:

[Chap08] B. Chapman, G. Jost, R. van der Pas. Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press, 2008.

17/08/11 26/26

ContenidoCmputo en paraleloOperaciones matemticas en paraleloFcilmente paralelizablesNo tan fciles de paralelizar

El esquema OpenMPProgramacin con multi-hilos (multithreads)Un programa simple con OpenMPCmo funciona?Establecer nmero de threads con variables de ambienteEstablecer nmero de threads con cdigoReduccionesParalelizar bloques de cdigoParalelizar secciones de cdigoVariables private and sharedScheduleOtro ejemploSecciones crticas

Prdida de eficiencia con el aumento de procesadoresPreguntas?Bibliografa:

2. computo en paralelo con openmp

Documents