PDF de programación - Paralelización de problemas de recorrido de arboles - Trabajadores replicados y esquema maestro esclavo

Metodolog´ıa de la Programaci´on Paralela

2015-2016

Facultad Inform´atica, Universidad de Murcia

Esquemas algor´ıtmicos paralelos:

Paralelizaci´on de problemas

de recorrido de ´arboles
Trabajadores replicados y
esquema maestro esclavo

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

1 / 35

Sesi´on 4

Descomposici´on 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 paralelizaci´on de esquemas secuenciales:
Divide y Vencer´as.
Programaci´on Din´amica.
Recorridos de ´arboles: Backtracking y Branch and Bound.
De m´ultiples tareas o trabajadores:
Bolsa de tareas. Granja de procesos. Maestro-Esclavo.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

2 / 35

Contenido

1 Recorrido de ´arboles

Backtracking
Branch and Bound

2 Trabajadores replicados

Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados

3 Pr´acticas

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

3 / 35

´Arboles de soluciones

Problemas de b´usqueda en un espacio de posibles soluciones.
Problemas de distintos tipos: b´usqueda de una ´unica soluci´on, de
todas las soluciones, de la soluci´on ´optima, etc.
Esquemas t´ıpicos de recorrido del ´arbol: Backtracking, Branch and
Bound, etc.
Se descompone el espacio de b´usqueda en subespacios m´as
peque˜nos y se asignan a distintos componentes computacionales
(hilos, procesos).
La generaci´on de subproblemas puede ser est´atica o din´amica: todas
las tareas se generan inicialmente, o se generan nuevas tareas
durante el recorrido del ´arbol.
La asignaci´on de tareas puede ser est´atica o din´amica: se decide
inicialmente qu´e subproblemas resuelve cada elemento de proceso,
o se asigna trabajo seg´un la velocidad de cada elemento de proceso.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

4 / 35

Contenido

1 Recorrido de ´arboles

Backtracking
Branch and Bound

2 Trabajadores replicados

Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados

3 Pr´acticas

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

5 / 35

Ejemplo - Subconjunto que suma una cantidad

Problema:
Dado un conjunto de n enteros, C = {a0 , a1 , . . . , an−1}, y un entero V,
se quiere encontrar un subconjunto S ⊆ C tal que Psi∈S si = V.
Representaci´on de soluciones:
n-tupla X de valores 0 o 1, con ai ∈ S s´ı y s´olo s´ı xi = 1.
´Arbol de soluciones:
´Arbol binario. Cada nivel representa un elemento de C, y cada nodo
tiene dos hijos que corresponden a los valores xi = 0 y xi = 1.
Son soluci´on los nodos terminales en los que Pn−1

i=0 xiai = V.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

6 / 35

Backtracking - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

7 / 35

Backtracking - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

8 / 35

Backtracking - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

9 / 35

Backtracking - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

10 / 35

Backtracking - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

11 / 35

Backtracking paralelo

Generaci´on secuencial inicial de un n´umero fijo de tareas.
Distribuci´on de tareas:

◮ Est´atica. Balancear la distribuci´on.

Si se sabe el coste de cada tarea se puede calcular distribuci´on ´optima
(problema NP).
Si no se sabe, se pueden generar m´as tareas que procesos y
asignarlas aleatoriamente o c´ıclicamente.

◮ Din´amica. M´as dif´ıcil la gesti´on.

Memoria Compartida, acceso en exclusiva a descriptores de las
tareas.
Paso de Mensajes, proceso que gestiona la bolsa de tareas (Maestro),
y coste alto de la gesti´on por comunicaciones.

Generaci´on din´amica de tareas: se generan tareas y al tratarlas se
generan nuevas tareas.
Coste de gesti´on de la bolsa de tareas.
La granularidad de las tareas debe ser alta.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

12 / 35

Contenido

1 Recorrido de ´arboles

Backtracking
Branch and Bound

2 Trabajadores replicados

Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados

3 Pr´acticas

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

13 / 35

Branch and Bound - ideas generales

En problemas de b´usqueda en un espacio de soluciones.
Normalmente problemas de optimizaci´on.
Se trata de obtener la soluci´on ´optima explorando la menor cantidad
posible de nodos.
Se mantiene una Lista de Nodos Vivos. Se van extrayendo nodos de
la LNV y se generan sus hijos. Para cada nodo se generan cota
inferior, cota superior y estimaci´on del beneficio (coste) de la soluci´on
´optima a partir de ´el.
Ramificaci´on:
Los nodos de la LNV se van extrayendo con un criterio que puede
estar basado en la estimaci´on del beneficio.
Poda:
Un nodo se poda si su Cota Superior es menor que la mayor Cota
Inferior de los nodos generados.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

14 / 35

Branch and Bound - paralelismo

1 B´usqueda paralela usando diferentes algoritmos en diferentes

procesos: diferentes formas de calcular las cotas y la estimaci´on del
beneficio, y distintos criterios de selecci´on.
Se repiten nodos pero hay pocas comunicaciones.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

15 / 35

Branch and Bound - paralelismo

1 B´usqueda paralela usando diferentes algoritmos en diferentes

procesos: diferentes formas de calcular las cotas y la estimaci´on del
beneficio, y distintos criterios de selecci´on.
Se repiten nodos pero hay pocas comunicaciones.

2 Expansi´on en paralelo de cada nodo.

Se necesita que la expansi´on de cada nodo sea costosa: gran
n´umero de hijos, alto coste de los c´alculos de cada hijo.
Gesti´on de la lista de nodos vivos centralizada ⇒ muchas
comunicaciones.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

15 / 35

Branch and Bound - paralelismo

1 B´usqueda paralela usando diferentes algoritmos en diferentes

procesos: diferentes formas de calcular las cotas y la estimaci´on del
beneficio, y distintos criterios de selecci´on.
Se repiten nodos pero hay pocas comunicaciones.

2 Expansi´on en paralelo de cada nodo.

Se necesita que la expansi´on de cada nodo sea costosa: gran
n´umero de hijos, alto coste de los c´alculos de cada hijo.
Gesti´on de la lista de nodos vivos centralizada ⇒ muchas
comunicaciones.

3 Evaluaci´on paralela de subproblemas:

Se asignan a cada proceso varios nodos de la LNV.
Posibilidades de distribuci´on:
Est´atica: pocas comunicaciones, se pueden difundir las cotas para
podar; la asignaci´on de los nodos puede ser balanceada o
ponderada.
Din´amica con bolsa de tareas: m´as comunicaciones. La
actualizaci´on de la bolsa puede ser inmediata o pospuesta.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

15 / 35

Branch and Bound - Subconjunto que suma una cantidad

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

16 / 35

Branch and Bound - comunicaci´on de las cotas
Comunicar las cotas puede contribuir a podar m´as, pero conlleva
comunicaciones.
¿Cu´ando y c´omo comunicarlas?

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

17 / 35

Contenido

1 Recorrido de ´arboles

Backtracking
Branch and Bound

2 Trabajadores replicados

Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados

3 Pr´acticas

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

18 / 35

Conceptos generales

Una serie de elementos de proceso que constituyen una Granja de
procesos y que pueden ser del mismo tipo (Trabajadores replicados).
Normalmente trabajan resolviendo tareas que se encuentran en una
estructura que contiene la definici´on de las tareas a realizar: Bolsa
de tareas.
Y la gesti´on de la bolsa la hace un proceso distinguido (Maestro), que
atiende las peticiones y los env´ıos de otros procesos (Esclavos).
Se tiene as´ı el paradigma Maestro-Esclavo.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

19 / 35

Contenido

1 Recorrido de ´arboles

Backtracking
Branch and Bound

2 Trabajadores replicados

Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados

3 Pr´acticas

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

20 / 35

Trabajadores replicados

Se mantiene una bolsa central de tareas.
Los trabajadores:

◮ Toman tareas de la bolsa.
◮ Posiblemente generan otras nuevas.

Acaba la computaci´on cuando la bolsa est´a vac´ıa y todos los
trabajadores han acabado (problema de detecci´on de terminaci´on).
´Util en problemas combinatorios: b´usqueda en ´arbol.
La asignaci´on din´amica de trabajos se hace para balancear la
computaci´on.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

21 / 35

Bolsa de tareas

Bolsa de tareas: conjunto de descriptores de tareas; cada descriptor
especifica una computaci´on.
En Memoria Compartida:
una estructura centralizada de la que los trabajadores toman trabajos
y posiblemente depositan otros nuevos. Acceso en exclusi´on mutua.
En Paso de Mensajes:
la estructura est´a en la memoria de uno o varios procesos,
la petici´on y dep´osito de tareas conllevan comunicaci´on.
Tener en cuenta:
◮ Contenci´on:

Por ser la bolsa de tareas centralizada.
Cuantos m´as procesadores mayor contenci´on.

◮ Balanceo:

Si se descentraliza la bolsa hay mayor desbalanceo y menor
contenci´on
⇒ compromiso entre contenci´on y balanceo.

◮ Terminaci´on:

El test de terminaci´on es global ⇒ sincronizaci´on.

Domingo Gim´enez (Universidad de Murcia)

Curso 2015-2016

22 / 35

Ejemplo - Algoritmo de Dijkstra de camino m´as corto
Grafo con matriz de adyacencia

Pasos del algoritmo:

paso
inicial
1
2
3
4
5

cola
1
2,3
4,3
3,5
5
∅

distancias

0 ∞ ∞ ∞ ∞
8 ∞ ∞
0
0
7
5 ∞
15
5
7
0
12
5
7
0
0
7
5
12

4
4
4
4
4

¿C´omo paralelizar?:
Pasos independientemente: Paralelizaci´on S´ıncrona.
Procesos tomando elementos de la cola, pero genera