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
Crear cuenta
Comentarios de: Esquemas algorítmicos paralelos - Particionado y Paralelismo de Datos - Metodología de la Programación Paralela (0)
No hay comentarios