PDF de programación - Esquemas algorítmicos paralelos - Particionado y Paralelismo de Datos - Metodología de la Programación Paralela

Imágen de pdf Esquemas algorítmicos paralelos - Particionado y Paralelismo de Datos - Metodología de la Programación Paralela

Esquemas algorítmicos paralelos - Particionado y Paralelismo de Datos - Metodología de la Programación Paralelagráfica de visualizaciones

Publicado el 27 de Mayo del 2018
775 visualizaciones desde el 27 de Mayo del 2018
524,0 KB
48 paginas
Creado hace 8a (19/10/2015)
Metodología de la Programación Paralela

2015-2016

Facultad Informática, Universidad de Murcia

Esquemas algorítmicos
paralelos - Particionado y

Paralelismo de Datos

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

1 / 31

Contenido

1 Esquemas algorítmicos paralelos

2 Paralelismo de datos

3 Particionado de datos

4 Esquemas de descomposición de datos

5 Trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

2 / 31

Contenido

1 Esquemas algorítmicos paralelos

2 Paralelismo de datos

3 Particionado de datos

4 Esquemas de descomposición de datos

5 Trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

3 / 31

Tipos de esquemas
Podemos considerar esquemas de distintos tipos:

Descomposición del trabajo:
Paralelismo de datos.
Particionado de datos.
Algoritmos relajados.
De paralelismo basado en dependencias de datos:
Paralelismo síncrono.
Dependencias en árbol o grafo.
Pipeline.
De paralelización de esquemas secuenciales:
Divide y Vencerás.
Programación Dinámica.
Recorridos de árboles: Backtracking y Branch and Bound.
De múltiples tareas o trabajadores:
Bolsa de tareas.
Granja de procesos.
Maestro-Esclavo.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

4 / 31

Sesiones
Los agruparemos en 5 sesiones de teoría y las correspondientes de
prácticas:

Descomposición del trabajo:
Paralelismo de datos.
Particionado de datos.
Algoritmos relajados.
De paralelismo basado en dependencias de datos:
Paralelismo síncrono.
Dependencias en árbol o grafo.
Pipeline.
De paralelización de esquemas secuenciales:
Divide y Vencerás.
Programación Dinámica.
Recorridos de árboles: Backtracking y Branch and Bound.
De múltiples tareas o trabajadores:
Bolsa de tareas. Granja de procesos. Maestro-Esclavo.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

5 / 31

Metodología

En clase de teoría se verán las ideas generales de cada paradigma
se discutirán sobre ejemplos básicos.
En las sesiones de prácticas se propondrá la resolución de algún
problema usando esos paradigmas.
Los problemas a usar en prácticas serán principalmente de los
analizados en teoría y del Concurso de Programación Paralela.
Los paradigmas no son disjuntos, por lo que se puede ver un
mismo problema con distintos paradigmas.
Otras referencias, con ejemplos e implementaciones:
Almeida, Giménez, Mantas, Vidal: Introducción a la Programación
Paralela, Paraninfo. 2008. Capítulo 6.
Wilkinson, Allen: Techniques and Applications Using Networked
Workstations and Parallel Computers, Prentice-Hall, 2004.
Quinn: Parallel Programming in C with MPI and OpenMP,
McGraw-Hill, 2003.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

6 / 31

Contenido

1 Esquemas algorítmicos paralelos

2 Paralelismo de datos

3 Particionado de datos

4 Esquemas de descomposición de datos

5 Trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

7 / 31

Ideas generales

Muchos datos tratados de una forma igual o similar (también
apropiado para GPU)
Típicamente algoritmos numéricos
Datos en arrays o vectores

◮ Posible procesamiento vectorial
◮ Paralelismo asignando partes distintas del array a distintos elementos

de proceso

Memoria Compartida (Paralelismo de datos):

◮ Distribución del trabajo entre los hilos
◮ Paralelización automática o implícita

Memoria Distribuida (Particionado de datos):

◮ Distribución de los datos a los procesos
◮ Paralelización explícita

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

8 / 31

Ejemplos

¿Alguno de los ejemplos vistos hasta ahora es de paralelismo de
datos?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

9 / 31

Ejemplos

¿Alguno de los ejemplos vistos hasta ahora es de paralelismo de
datos?
Claramente la multiplicación de matrices
¿Características?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

9 / 31

Ejemplos

¿Alguno de los ejemplos vistos hasta ahora es de paralelismo de
datos?
Claramente la multiplicación de matrices
¿Características?
¿Y la ordenación?
¿Cómo se podría hacer con palalelismo de datos?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

9 / 31

Ejemplo - Suma de n datos

Esquema secuencial:

s=0;
for (i=0;i<n;i++)

s=s+a[i];

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 31

Ejemplo - Suma de n datos

Esquema secuencial:

s=0;
for (i=0;i<n;i++)

s=s+a[i];

Paralelización automática: con opción de compilación si no hay
dependencia de datos o el compilador detecta que se puede resolver.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 31

Ejemplo - Suma de n datos

Esquema secuencial:

s=0;
for (i=0;i<n;i++)

s=s+a[i];

Paralelización automática: con opción de compilación si no hay
dependencia de datos o el compilador detecta que se puede resolver.
Con pragma:

s=0;
#pragma omp parallel for private(i) reduction(+:s)
for (i=0;i<n;i++)

s=s+a[i];

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 31

Ejemplo - Suma de n datos

Esquema secuencial:

s=0;
for (i=0;i<n;i++)

s=s+a[i];

Paralelización automática: con opción de compilación si no hay
dependencia de datos o el compilador detecta que se puede resolver.
Con pragma:

s=0;
#pragma omp parallel for private(i) reduction(+:s)
for (i=0;i<n;i++)

s=s+a[i];

Distintas posibilidades de asignación de los datos a los procesadores,
con cláusula schedule: bloques contiguos, cíclica, dinámica.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 31

Ejemplo - Suma de n datos

Esquema secuencial:

s=0;
for (i=0;i<n;i++)

s=s+a[i];

Paralelización automática: con opción de compilación si no hay
dependencia de datos o el compilador detecta que se puede resolver.
Con pragma:

s=0;
#pragma omp parallel for private(i) reduction(+:s)
for (i=0;i<n;i++)

s=s+a[i];

Distintas posibilidades de asignación de los datos a los procesadores,
con cláusula schedule: bloques contiguos, cíclica, dinámica.
¿Cuál es la mejor manera de ejecutarlo? ¿Merece la pena
paralelizar?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 31

Ejemplo - Suma de n datos, con paralelismo explícito

#pragma omp parallel for private(s)
for(i=0;i<p;i++)

sumaparcial(&a[(i*n)/p],n,p);

if(nodo==0)

s=sumatotal(a,n,p);

sumaparcial(a,n,p):

s=0;
for(j=0;j<n/p;j++)

s=s+a[j];

a[0]=s;

sumatotal(a,n,p):

s=0;
for(j=0;j<p;j+=n/p)

s=s+a[j];

return s;

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

11 / 31

Ejemplo - Suma de n datos, con paralelismo explícito

#pragma omp parallel for private(s)
for(i=0;i<p;i++)

sumaparcial(&a[(i*n)/p],n,p);

if(nodo==0)

s=sumatotal(a,n,p);

sumaparcial(a,n,p):

s=0;
for(j=0;j<n/p;j++)

s=s+a[j];

a[0]=s;

sumatotal(a,n,p):

s=0;
for(j=0;j<p;j+=n/p)

s=s+a[j];

return s;

¿Merece la pena paralelizar sumatotal?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

11 / 31

Ejemplo - Ordenación por rango

Se cuenta para cada elemento cuantos hay mayores que él (su
rango), y a continuación se sitúa en la posición dada por su rango.

#pragma omp parallel for private(i,j)
for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(a[i]>a[j])

r[i]+=1;

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

12 / 31

Ejemplo - Ordenación por rango

Se cuenta para cada elemento cuantos hay mayores que él (su
rango), y a continuación se sitúa en la posición dada por su rango.

#pragma omp parallel for private(i,j)
for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(a[i]>a[j])

r[i]+=1;

Problemas:
¿Se hace trabajo de más?
¿Cómo situarlos en su posición?
¿Qué pasa si dos datos son iguales?
¿Se pueden colapsar los dos bucles?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

12 / 31

Ejemplo - Ordenación por rango, con paralelismo
explícito
Se hace asignación del trabajo entre los hilos:

#pragma omp parallel for

for(i=0;i<p;i++)

calcularrango(a,n,i,p);

calcularrango(a,n,i,p):

for(j=(i*n)/p;j<((i+1)*n)/p;j++)

for(k=0;k<n;k++)

if(a[j]>a[k])

r[j]+=1;

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

13 / 31

Ejemplo - Multiplicación de matrices

Con paralelismo implícito:

#pragma parallel for private(i,j,k)
for(i=0;i<n;i++)

for(j=0;j<n;j++) {

c[i,j]=0;
for(k=0;k<n;k++)

c[i,j]=c[i,j]+a[i,k]*b[k,j];

}

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

14 / 31

Ejemplo - Multiplicación de matrices

Con paralelismo implícito:

#pragma parallel for private(i,j,k)
for(i=0;i<n;i++)

for(j=0;j<n;j++) {

c[i,j]=0;
for(k=0;k<n;k++)

c[i,j]=c[i,j]+a[i,k]*b[k,j];

}

¿Por qué en los ejemplos usábamos arrays unidimensionales y una
variable s para acumular el producto escalar?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

14 / 31

Ejemplo - Multiplicación de matrices

Con paralelismo implícito:

#pragma parallel for private(i,j,k)
for(i=0;i<n;i++)

for(j=0;j<n;j++) {

c[i,j]=0;
for(k=0;k<n;k++)

c[i,j]=c[i,j]+a[i,k]*b[k,j];

}

¿Por qué en los ejemplos usábamos arrays unidimensionales y una
variable s para acumular el producto escalar?
Se pueden mejorar las prestaciones con algoritmos por bloques,
vectorización, reordenación de bucles...

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

14 / 31

Ejemplo - Multiplicación de matrices, con paralelismo
explícito

#pragma omp parallel for private(i)
for(i=0;i<p;i++)

multiplicar(c,a,b,i)

multiplicar(c,a,b,i):

for(j=(i*n)/p;j<((i+1)*n)/p;j++)

for(k=0;k<n;k++) {

c[j,k]=0;
for(l=0;l<n;l++)

c[j,k]=c[j,k]+a[j,l]*b[l,k];

}

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

15 / 31

Otros ejemplos

Producto escalar de dos vectores x e y de tamaño n:
Similar a la suma de n datos.
Asignación de bloques de tamaño n
p de x e y a los p hilos.
Suma (secuencial o paralela) de los productos parciales.
Producto matriz-vector:
Dos bucles, paralelización del más externo.
Posible trabajo por bloques.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

16 / 31
  • Links de descarga
http://lwp-l.com/pdf11353

Comentarios de: Esquemas algorítmicos paralelos - Particionado y Paralelismo de Datos - Metodología de la Programación Paralela (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad