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

Imágen de pdf Paralelización de problemas de recorrido de arboles - Trabajadores replicados y esquema maestro esclavo

Paralelización de problemas de recorrido de arboles - Trabajadores replicados y esquema maestro esclavográfica de visualizaciones

Actualizado el 21 de Noviembre del 2020 (Publicado el 27 de Mayo del 2018)
629 visualizaciones desde el 27 de Mayo del 2018
1,0 MB
37 paginas
Creado hace 5a (12/11/2015)
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
  • Links de descarga
http://lwp-l.com/pdf11357

Comentarios de: Paralelización de problemas de recorrido de arboles - Trabajadores replicados y esquema maestro esclavo (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad