PDF de programación - Divide y Vencerás - Programación Dinámica - Metodología de la Programación Paralela

Metodología de la Programación Paralela

Facultad Informática, Universidad de Murcia

Esquemas algorítmicos paralelos:
Divide y Vencerás

Programación Dinámica

Domingo Giménez (Universidad de Murcia)

1 / 24

Sesión 4

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)

2 / 24

Contenido

1 Divide y Vencerás

2 Programación Dinámica

3 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

3 / 24

Ideas generales de Divide y Vencerás

Dividir un problema p en subproblemas p1, p2, . . . , pn.
Resolver los subproblemas pi obteniendo subsoluciones si.
Combinar las soluciones parciales s1, s2, . . . , sn para obtener la
solución global de p.
El éxito del método depende de que se pueda hacer la división y la
combinación de forma eficiente.

Es el esquema más adecuado para paralelizar.
Se puede considerar que todos los programas paralelos siguen este
esquema.

Domingo Giménez (Universidad de Murcia)

4 / 24

Paralelismo en Divide y Vencerás

La solución de los subproblemas si se puede hacer en paralelo.
La división debe producir subproblemas de coste balanceado.
La división y la combinación implican comunicaciones y
sincronización.
Si consideramos un árbol de llamadas recursivas, el Grafo de
Dependencias viene determinado por el árbol, y podemos considerar
que seguimos el paradigma de programación paralela en árbol.
Ordenación por mezcla ¿árbol o no árbol?

Domingo Giménez (Universidad de Murcia)

5 / 24

Ejemplo - Ordenación por Mezcla, Memoria Compartida

#pragma omp parallel for private(i)

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

ordenarsimple(i,a);

//cada hilo ordena un trozo

proc=p/2;
for(i=1;i<log p;i++) {

//numero de hilos que intervienen en la mezcla

#pragma omp parallel for private(j)

for(j=0,j<proc;j++)

mezclar(i,n/proc,a);

proc=proc/2;

}
mezclasimple(0,n,a);

mezclar(i,l,a):

mezclasimple(i*l,(i+1)*l-1,a);

No hay recursión, sino que se divide en función del número de procesadores.
¿Cómo podría ser con recursión?
¿Cuál es el coste de la mezcla? ¿y del algoritmo completo?
¿Cómo se puede hacer la mezcla de otra forma?

Domingo Giménez (Universidad de Murcia)

6 / 24

Ejemplo - Ordenación por Mezcla, Paso de Mensajes

Envio de n/p datos a cada proceso
En cada Pi, i=0,1,...,p-1:

//distintas posibilidades

//cada proceso con a local

ordenar(0,n/p-1,a);
activo=1;
desp=2;
for(j=1;j<=log p;j++)

if(activo==1) {

if(i mod desp==0) {

recibir en b (n/p)*(desp/2) datos de Pi+desp/2;
mezclar a y b en a;

} else {

enviar (n/p)*(desp/2) datos de a a Pi-desp/2;
activo=0;

}
desp=desp*2;

}

¿Cómo se hace el envío inicial? ¿Qué coste tiene?
¿Qué memoria necesita cada proceso?
¿Cuál es el coste de la mezcla? ¿y del algoritmo completo?
¿Cómo se puede hacer la mezcla de otra forma?

Domingo Giménez (Universidad de Murcia)

7 / 24

Ejemplo - Ordenación Rápida
Secuencial:

ordenar(p,q,a):

if(q-p>base) {

m=particionar(p,q,a);
ordenar(p,m,a);
ordenar(m+1,q,a);

} else

ordenarbasico(p,q,a);

Problemas para el paralelismo:

Domingo Giménez (Universidad de Murcia)

8 / 24

Ejemplo - Ordenación Rápida
Secuencial:

ordenar(p,q,a):

if(q-p>base) {

m=particionar(p,q,a);
ordenar(p,m,a);
ordenar(m+1,q,a);

} else

ordenarbasico(p,q,a);

Problemas para el paralelismo:

¿Cuál es el caso más desfavorable?

Domingo Giménez (Universidad de Murcia)

8 / 24

Ejemplo - Ordenación Rápida
Secuencial:

ordenar(p,q,a):

if(q-p>base) {

m=particionar(p,q,a);
ordenar(p,m,a);
ordenar(m+1,q,a);

} else

ordenarbasico(p,q,a);

Problemas para el paralelismo:

¿Cuál es el caso más desfavorable?
¿Cómo se balancea el trabajo?

Domingo Giménez (Universidad de Murcia)

8 / 24

Ejemplo - Ordenación Rápida
Secuencial:

ordenar(p,q,a):

if(q-p>base) {

m=particionar(p,q,a);
ordenar(p,m,a);
ordenar(m+1,q,a);

} else

ordenarbasico(p,q,a);

Problemas para el paralelismo:

¿Cuál es el caso más desfavorable?
¿Cómo se balancea el trabajo?
¿Cómo se sabe el tamaño local de datos?

Domingo Giménez (Universidad de Murcia)

8 / 24

Ejemplo - Ordenación Rápida
Secuencial:

ordenar(p,q,a):

if(q-p>base) {

m=particionar(p,q,a);
ordenar(p,m,a);
ordenar(m+1,q,a);

} else

ordenarbasico(p,q,a);

Problemas para el paralelismo:

¿Cuál es el caso más desfavorable?
¿Cómo se balancea el trabajo?
¿Cómo se sabe el tamaño local de datos?
¿Cómo se sabe el tamaño de los envíos?

Domingo Giménez (Universidad de Murcia)

8 / 24

Ejemplo - Ordenación Rápida, Memoria Compartida

m[0]=0;
m[1..p]=n-1;
m[p/2]=particionar(0,n-1,a);
proc=2;
for(i=1;i<log p;i++) {
#pragma omp parallel for private(j)

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

m[p/(2*proc)+j*p/proc]=particionar(m[j*p/proc],m[(j+1)*p/proc],a);

proc=2*proc;

}
#pragma omp parallel for private(i)

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

ordenar(m[i],m[i+1],a);

Domingo Giménez (Universidad de Murcia)

9 / 24

Ejemplo - Ordenación Rápida, Memoria Compartida

m[0]=0;
m[1..p]=n-1;
m[p/2]=particionar(0,n-1,a);
proc=2;
for(i=1;i<log p;i++) {
#pragma omp parallel for private(j)

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

m[p/(2*proc)+j*p/proc]=particionar(m[j*p/proc],m[(j+1)*p/proc],a);

proc=2*proc;

}
#pragma omp parallel for private(i)

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

ordenar(m[i],m[i+1],a);

¿Qué coste tiene?

Domingo Giménez (Universidad de Murcia)

9 / 24

Ejemplo - Ordenación Rápida, Memoria Compartida

m[0]=0;
m[1..p]=n-1;
m[p/2]=particionar(0,n-1,a);
proc=2;
for(i=1;i<log p;i++) {
#pragma omp parallel for private(j)

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

m[p/(2*proc)+j*p/proc]=particionar(m[j*p/proc],m[(j+1)*p/proc],a);

proc=2*proc;

}
#pragma omp parallel for private(i)

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

ordenar(m[i],m[i+1],a);

¿Qué coste tiene?
¿Cómo se puede dividir el trabajo de otra manera?

Domingo Giménez (Universidad de Murcia)

9 / 24

Ejemplo - Ordenación Rápida, Memoria Compartida

m[0]=0;
m[1..p]=n-1;
m[p/2]=particionar(0,n-1,a);
proc=2;
for(i=1;i<log p;i++) {
#pragma omp parallel for private(j)

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

m[p/(2*proc)+j*p/proc]=particionar(m[j*p/proc],m[(j+1)*p/proc],a);

proc=2*proc;

}
#pragma omp parallel for private(i)

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

ordenar(m[i],m[i+1],a);

¿Qué coste tiene?
¿Cómo se puede dividir el trabajo de otra manera?
¿Cómo se puede hacer una división balanceada?

Domingo Giménez (Universidad de Murcia)

9 / 24

Ejemplo - Ordenación Rápida, Paso de Mensajes

En cada Pi, i=0,1,...,p-1
m1=n-1; desp=p ; activo=0;
if(i mod (desp/2)==0)

activo=1;

for(j=1;j<=log p;j++) {

if(activo==1)

if(i mod desp==0) {

m=particionar(0,m1,a);
enviar m1-m+1 y a[m+1],...,a[m1] a Pi+desp/2;
m1=m;

} else {

recibir en l y a de Pi-desp/2;
m1=l-1;
m=particionar(0,m1,a);
enviar m1-m+1 y a[m+1],...,a[m1] a Pi+desp/2;
m1=m;

}
desp=desp/2;
if(i mod (desp/2)==0)

activo=1;

ordenar(a); acumular sobre P0;

¿Qué problemas de implementación tenemos?

Domingo Giménez (Universidad de Murcia)

10 / 24

Descomposición recursiva

Se divide un problema en subproblemas completamente
independientes, que se pueden dividir recursivamente en otros
subproblemas.
Es un esquema divide y vencerás, pero no sabemos los
subproblemas a los que puede dar lugar.
Ejemplo: en la ordenación rápida puede que la parte izquierda o
derecha tenga cero o un elemento, y no hace falta llamar
recursivamente con ella.
Tiene que haber un criterio para decidir si se realiza la llamada.
En Memoria Compartida se puede hacer con tareas.
En Memoria Distribuida se generan tareas que hay que gestionar
cómo asignar a los procesos (técnica de bolsa de tareas).

Domingo Giménez (Universidad de Murcia)

11 / 24

Descomposición recursiva - Aproximación recursivo de
integral

El número de intervalos de integración no es fijo.
Cada intervalo se divide en dos subintervalos.
Se sigue dividiendo un intervalo cuando el área de su trapecio se
diferencia con una cierta tolerancia del área de sus dos subtrapecios.

Domingo Giménez (Universidad de Murcia)

12 / 24

Ejemplos numéricos

Multiplicación de enteros largos.
Método de Karatsuba y Ofman.

Multiplicación rápida de matrices.
Método de Strassen.

uv = 102Swy+10S((w−x)(z−y)+wy+xz)+xz

P = (A11 + A22) (B11 + B22)
Q = (A12 + A22) B11
R = A11 (B12 − B22)
S = A22 (B21 − B11)
T = (A11 + A12) B22
U = (A21 − A11) (B11 + B12)
V = (A12 − A22) (B21 + B22)
C11 = P + S − T + U
C12 = R + T
C21 = Q + S
C22 = P + R − Q + U

¿Cuántas tareas generar y cómo asignarlas a los procesos?

Domingo Giménez (Universidad de Murcia)

13 / 24

Contenido

1 Divide y Vencerás

2 Programación Dinámica

3 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

14 / 24

Ideas generales de la Programación Dinámica

Para resolver problemas de optimización.
Obteniendo soluciones de subproblemas de menor a mayor tamaño
hasta llegar al tamaño deseado.
Las soluciones parciales se pueden guardar en un array
construyendo el array de la primera fila hasta la última, usándose
para cada fila los valores de las anteriores.

Domingo Giménez (Universidad de Murcia)

15 / 24

Ideas generales de la Programación Dinámica

Memoria Compartida:
En cada fila intervienen los procesadores obteniendo cada uno
valores de distintos tamaños, basándose en la fila anterior para leer.
No hay problema de coherencia,
pero se necesita sincronización entre los pasos sucesivos (uno por
fila), lo que se puede ver como Paralelismo Síncrono.
Paso de Mensajes:
Un proceso puede necesitar datos almacenados en otro.
Las flechas que cruzan de un proceso a otro determinan
comunicaciones.

Domingo Giménez (Universidad de Murcia)

16 / 24

Ejemplo - Problema de la Mochila 0/1