esquemas algor´ıtmicos paralelos: algoritmos en arbol y...

Metodologıa de la Programacion Paralela2015-2016

Facultad Informatica, Universidad de Murcia

Esquemas algorıtmicos paralelos:

Algoritmos en Arbol y GrafoComputacion Pipeline

Domingo Gimenez (Universidad de Murcia) Curso 2015-2016 1 / 22

Sesion 3

Descomposicion del trabajo:Paralelismo de datos.Particionado de datos.Algoritmos relajados.

De paralelismo basado en dependencias de datos:Paralelismo sıncrono.Dependencias en arbol o grafo.Pipeline.

De paralelizacion de esquemas secuenciales:Divide y Venceras.Programacion Dinamica.Recorridos de arboles: Backtracking y Branch and Bound.

De multiples tareas o trabajadores:Bolsa de tareas. Granja de procesos. Maestro-Esclavo.


Contenido

1 Grafos de dependencia

2 Paralelismo en Arbol o Grafo

3 Computacion Pipeline

4 Otros ejemplos y trabajo adicional


Ideas generales

Un Grafo de Dependencias es un grafo dirigido acıclico,

donde los nodos representan tareas,

y una arista de un origen a un destino representa que para poder realizarse la tareadestino tiene que haberse ejecutado la origen.

Los nodos pueden etiquetarse con un valor que representa el coste de la tarea.

Las aristas pueden etiquetarse con valor que representa el coste de lacomunicacion.


Asignacion de tareas

Hay que asignar las tareas a los elementos de proceso.Distintas asignaciones pueden originar tiempos distintos.El problema de la asignacion optima es NP.


Problemas de la asignacion de tareas

Dentro de un elemento de proceso hay que elegir el orden deejecucion de las tareas.

Desbalanceo de la carga : balancear calculo y comunicaciones.

Tiempos de espera : por dependencias entre tareas.

Si granularidad fina muchas tareas, lo que posibilita el balanceopero genera mas comunicaciones.

Si granularidad gruesa menos comunicaciones pero mas difıcil elbalanceo.


Medidas de concurrencia

Maximo grado de concurrencia : mayor numero de tareas que sepueden ejecutar al mismo tiempo.

Camino cr ıtico : camino mas largo desde un nodo de comienzohasta un nodo final.Donde la longitud es la suma los costes de los nodos del camino.

Grado medio de concurrencia : numero medio de tareas que sepodrıan ejecutar en paralelo considerando todas las fases delalgoritmo:

GMC =

∑ni=1 coste (nodoi)

longitud camino critico

En el grafo precedente: MGC = 4, LCC = 13, GMC = 2.


Contenido






Ejemplos en arbolSuma de n numeros:

Suma prefija. Dada secuencia {x0, x1, . . . , xn−1} calcular secuencia{s0, s1, . . . , sn−1} con si =

∑ij=0 xj .

¿Alguno de los vistos?


Ejemplo - suma prefijaCon Paso de Mensajes.

Para cada Pi, i=0,1,...,n-1

desp=1;

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

if(i<n-desp)

enviar x a Pi+desp;

if(i>=desp) {

recibir en y de Pi-desp;

x+=y;

}

desp*=2;

}

¿Como generalizar a n numeros y p elementos de proceso?

¿Como serıa en Memoria Compartida?


Ejemplos de suma - centralizada / distribuida

¿Cual producirıa menos tiempo de ejecucion?

¿Y con la ordenacion por mezcla?

¿Como serıa la ordenacion quicksort?


Grafos con tareas de tipos distintosPor ejemplo la suma de n datos en p procesadores.Suma de todos los elementos de una matriz y obtencion del maximo:

Dada matriz A almacenar en vector x sumando los elementos de lafila, formar la matriz B ordenando las columnas de A y obtener lamultiplicacion Bx.Tenemos bloques de computacion de los vistos antes (suma,ordenacion, multiplicacion...), ¿cual es una forma adecuada dellevarlas a cabo?


Ejemplo - clases de equivalenciaEn una representacion de conjuntos por medio de arboles:

se trata de encontrar el representante de la clase a la que pertenececada nodo.Los arcos indican comunicaciones si estan en distinto procesador.De cada nodo sale como mucho un arco y el patron decomunicaciones es fijo.Funcionamiento:Para cada nodo se lee el valor del padre,si el valor leıdo es igual al que hay en el nodo ese nodose envıa un mensaje de fin al nodo con el que se comunica y acaba.


Contenido






Ideas generalesResolver un problema descomponiendolo en una serie de tareassucesivas:

los datos fluyen por la estructura de los procesadores o hilos.El coste es mayor que el de la tarea mas costosa.Interes cuando:

◮ no hay un unico conjunto de datos a tratar, sino una serie de conjuntosde datos.

◮ no se necesite que una tarea este completamente finalizada paraempezar la siguiente.

Cada tarea puede tener un peso diferente y ser preferible dedicardistinto numero de procesadores a cada tarea:


Ejemplo - divisibilidadDada una lista de numeros primos p0, p1, . . . , pm−1 y una secuencia deenteros a0, a1, . . ., se quiere obtener los enteros que son multiplo de todoslos primos.

Para cada Pi, i=0,...,m-1:

repeat

if(i==0)

leer(a);

else

recibir a de P(i-1);

if(a<0) //condicion de fin

fin=true;

if(fin or (a mod pi==0)) {

if(i!=m-1)

enviar a a P(i+1);

else

salida de a;

until fin;


Ejemplo - sistema triangular de ecuacionesSistema triangular inferior de ecuaciones lineales:

a00x0 = b0

a10x0 + a11x1 = b1

. . .

an−1,0x0 + an−1,1x1 + . . . + an−1,n−1xn−1 = bn−1

Sustituci on progresiva .

Considerando un procesador por fila,pi calcula xi

xi =bi −∑i−1

j=0 aijxj

ajj


Ejemplo - sistema triangular de ecuaciones, MemoriaCompartida

#pragma omp parallel for private(i)

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

resolver(a,b,x,n,i)

resolver(a,b,x,n,i):

suma=0;

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

P(valor[j]);

V(valor[j]);

suma+=a[i,j]*x[j];

}

x[i]=(b[i]-suma)/a[i,i];

V(valor[i]);

valor es un vector de semaforos inicializados a cero.En OpenMP se puede hacer con llaves.


Ejemplo - sistema triangular de ecuaciones, Paso deMensajesEn cada Pi, i=0,1,...,n-1

if(i==0) {

x=b/a[0]; //cada uno tiene un vector con su fila

enviar x a P1;

}

else if(i!=n-1) {

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

recibir x de P(i-1);

enviar x a P(i+1);

suma+=a[j]*x;

}

x=(b-suma)/a[i];

}

else {

for{j=0;j<n-1;j++) {

recibir x de P(n-2);

suma+=a[j]*x;

}

x=(b-suma)/a[n-1];

}

Se han sustituido las llaves por comunicaciones.


Ejemplo - sistema triangular de ecuaciones, costes

Coste secuencial:∑n−1

i=0 (2 + 2i) = n2 + n

Coste paralelo, aproximadamente 5n

Speed-up: n/5

Eficiencia 20%

Y en paso de mensajes hay que anadir coste de comunicaciones.

¿Causa de las bajas prestaciones?¿Como generalizar a tamano de problema y de sistema independientes?


Contenido






Se pueden consultar las secciones correspondientes y sus ejemplosdel capıtulo 6 del libro de Introduccion a la Programacion Paralela yen el Concurso de Programacion Paralela.

◮ Detalles del problema de encontrar las clases de equivalencia (libroIPP).

◮ En el CPP hay pocos ejemplos:

⋆ Los que llevan ordenaciones se podrıan considerar en arbol, perotambien de Divide y Venceras, que veremos la proxima sesion.

⋆ Los A de 2013 y 2015 se pueden pensar como pipeline.

◮ Y pensar como podrıan implementarse los ejemplos vistos en estasesion.

◮ En la sesion de pr acticas se propondran uno o dos problemas paraabordarlos con los paradigmas presentados.


esquemas algor´ıtmicos paralelos: algoritmos en arbol y...

Documents