Actualizado el 21 de Noviembre del 2020 (Publicado el 27 de Mayo del 2018)
1.353 visualizaciones desde el 27 de Mayo del 2018
1,0 MB
37 paginas
Creado hace 9a (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
Comentarios de: Paralelización de problemas de recorrido de arboles - Trabajadores replicados y esquema maestro esclavo (0)
No hay comentarios