PDF de programación - Esquemas algorítmicos paralelos: Algoritmos en Arbol y Grafo - Computacion Pipeline - Metodología de la Programación Paralela

Metodología de la Programación Paralela

2015-2016

Facultad Informática, Universidad de Murcia

Esquemas algorítmicos paralelos:

Algoritmos en Árbol y Grafo

Computación Pipeline

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

1 / 22

Sesión 3

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

2 / 22

Contenido

1 Grafos de dependencia

2 Paralelismo en Árbol o Grafo

3 Computación Pipeline

4 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

3 / 22

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 tarea
destino 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 la
comunicación.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

4 / 22

Asignación de tareas

Hay que asignar las tareas a los elementos de proceso.
Distintas asignaciones pueden originar tiempos distintos.
El problema de la asignación óptima es NP.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

5 / 22

Problemas de la asignación de tareas

Dentro de un elemento de proceso hay que elegir el orden de
ejecución de las tareas.
Desbalanceo de la carga: balancear cálculo y comunicaciones.
Tiempos de espera: por dependencias entre tareas.
Si granularidad fina muchas tareas, lo que posibilita el balanceo
pero genera más comunicaciones.
Si granularidad gruesa menos comunicaciones pero más difícil el
balanceo.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

6 / 22

Medidas de concurrencia

Máximo grado de concurrencia: mayor número de tareas que se
pueden ejecutar al mismo tiempo.
Camino crítico: camino más largo desde un nodo de comienzo
hasta un nodo final.
Donde la longitud es la suma los costes de los nodos del camino.
Grado medio de concurrencia: número medio de tareas que se
podrían ejecutar en paralelo considerando todas las fases del
algoritmo:

GMC =

Pn

i=1 coste(nodoi)

longitud camino critico

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

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

7 / 22

Contenido

1 Grafos de dependencia

2 Paralelismo en Árbol o Grafo

3 Computación Pipeline

4 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

8 / 22

Ejemplos en árbol

Suma de n números:

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

j=0 xj.

¿Alguno de los vistos?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

9 / 22

Ejemplo - suma prefija
Con 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;

}

¿Cómo generalizar a n números y p elementos de proceso?
¿Cómo sería en Memoria Compartida?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

10 / 22

Ejemplos de suma - centralizada / distribuida

¿Cuál produciría menos tiempo de ejecución?

¿Y con la ordenación por mezcla?

¿Cómo sería la ordenación quicksort?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

11 / 22

Grafos con tareas de tipos distintos

Por ejemplo la suma de n datos en p procesadores.
Suma de todos los elementos de una matriz y obtención del máximo:

Dada matriz A almacenar en vector x sumando los elementos de la
fila, formar la matriz B ordenando las columnas de A y obtener la
multiplicación Bx.
Tenemos bloques de computación de los vistos antes (suma,
ordenación, multiplicación...), ¿cuál es una forma adecuada de
llevarlas a cabo?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

12 / 22

Ejemplo - clases de equivalencia

En una representación de conjuntos por medio de árboles:

se trata de encontrar el representante de la clase a la que pertenece
cada nodo.
Los arcos indican comunicaciones si están en distinto procesador.
De cada nodo sale como mucho un arco y el patrón de
comunicaciones 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 nodo
se envía un mensaje de fin al nodo con el que se comunica y acaba.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

13 / 22

Contenido

1 Grafos de dependencia

2 Paralelismo en Árbol o Grafo

3 Computación Pipeline

4 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

14 / 22

Ideas generales

Resolver un problema descomponiéndolo en una serie de tareas
sucesivas:

los datos fluyen por la estructura de los procesadores o hilos.
El coste es mayor que el de la tarea más costosa.
Interés cuando:

◮ no hay un único conjunto de datos a tratar, sino una serie de conjuntos

de datos.

◮ no se necesite que una tarea esté completamente finalizada para

empezar la siguiente.

Cada tarea puede tener un peso diferente y ser preferible dedicar
distinto número de procesadores a cada tarea:

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

15 / 22

Ejemplo - divisibilidad
Dada una lista de números primos p0, p1, . . . , pm−1 y una secuencia de
enteros a0, a1, . . ., se quiere obtener los enteros que son múltiplo de todos
los 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;

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

16 / 22

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

a00x0
a10x0 + a11x1

. . .

= b0
= b1

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

Sustituci ón progresiva.

Considerando un procesador por fila,
pi calcula xi

xi =

bi − Pi−1
j=0 aijxj
ajj

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

17 / 22

Ejemplo - sistema triangular de ecuaciones, Memoria
Compartida

#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 semáforos inicializados a cero.
En OpenMP se puede hacer con llaves.
Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

18 / 22

Ejemplo - sistema triangular de ecuaciones, Paso de
Mensajes

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

if(i==0) {

x=b/a[0];
enviar x a P1;

//cada uno tiene un vector con su fila

}
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.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

19 / 22

Ejemplo - sistema triangular de ecuaciones, costes

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

Coste secuencial: Pn−1
Coste paralelo, aproximadamente 5n
Speed-up: n/5
Eficiencia 20%

Y en paso de mensajes hay que añadir coste de comunicaciones.

¿Causa de las bajas prestaciones?
¿Cómo generalizar a tamaño de problema y de sistema independientes?

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

20 / 22

Contenido

1 Grafos de dependencia

2 Paralelismo en Árbol o Grafo

3 Computación Pipeline

4 Otros ejemplos y trabajo adicional

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

21 / 22

Se pueden consultar las secciones correspondientes y sus ejemplos
del capítulo 6 del libro de Introducción a la Programación Paralela y
en el Concurso de Programación Paralela.

◮ Detalles del problema de encontrar las clases de equivalencia (libro

IPP).

◮ En el CPP hay pocos ejemplos:

⋆ Los que llevan ordenaciones se podrían considerar en árbol, pero

también de Divide y Vencerás, que veremos la próxima sesión.

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

◮ Y pensar cómo podrían implementarse los ejemplos vistos en esta

sesión.

◮ En la sesión de prácticas se propondrán uno o dos problemas para

abordarlos con los paradigmas presentados.

Domingo Giménez (Universidad de Murcia)

Curso 2015-2016

22 / 22