1. No category

Metodologı́a de la Programación Paralela
2015-2016
Facultad Informática, Universidad de Murcia
Esquemas algorı́tmicos paralelos:
Paralelización de problemas
de recorrido de árboles
Trabajadores replicados y
esquema maestro esclavo
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
1 / 35
Sesión 4
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 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
3 / 35
Árboles de soluciones
Problemas de búsqueda en un espacio de posibles soluciones.
Problemas de distintos tipos: búsqueda de una única solución, de
todas las soluciones, de la solución óptima, etc.
Esquemas tı́picos de recorrido del árbol: Backtracking, Branch and
Bound, etc.
Se descompone el espacio de búsqueda en subespacios más
pequeños y se asignan a distintos componentes computacionales
(hilos, procesos).
La generación de subproblemas puede ser estática o dinámica: todas
las tareas se generan inicialmente, o se generan nuevas tareas
durante el recorrido del árbol.
La asignación de tareas puede ser estática o dinámica: se decide
inicialmente qué subproblemas resuelve cada elemento de proceso,
o se asigna trabajo según la velocidad de cada elemento de proceso.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
4 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (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 ,
P
se quiere encontrar un subconjunto S ⊆ C tal que si ∈S si = V .
Representación de soluciones:
n-tupla X de valores 0 o 1, con ai ∈ S sı́ y sólo sı́ xi = 1.
Árbol de soluciones:
Árbol 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ón los nodos terminales en los que
Domingo Giménez (Universidad de Murcia)
Pn−1
i =0
xi ai = V .
Curso 2015-2016
6 / 35
Backtracking - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
7 / 35
Backtracking - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
8 / 35
Backtracking - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
9 / 35
Backtracking - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
10 / 35
Backtracking - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
11 / 35
Backtracking paralelo
Generación secuencial inicial de un número fijo de tareas.
Distribución de tareas:
◮
◮
Estática. Balancear la distribución.
Si se sabe el coste de cada tarea se puede calcular distribución óptima
(problema NP).
Si no se sabe, se pueden generar más tareas que procesos y
asignarlas aleatoriamente o cı́clicamente.
Dinámica. Más difı́cil la gestión.
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ón por comunicaciones.
Generación dinámica de tareas: se generan tareas y al tratarlas se
generan nuevas tareas.
Coste de gestión de la bolsa de tareas.
La granularidad de las tareas debe ser alta.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
12 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
13 / 35
Branch and Bound - ideas generales
En problemas de búsqueda en un espacio de soluciones.
Normalmente problemas de optimización.
Se trata de obtener la solución óptima 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ón del beneficio (coste) de la solución
óptima a partir de él.
Ramificación:
Los nodos de la LNV se van extrayendo con un criterio que puede
estar basado en la estimación del beneficio.
Poda:
Un nodo se poda si su Cota Superior es menor que la mayor Cota
Inferior de los nodos generados.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
14 / 35
Branch and Bound - paralelismo
1
Búsqueda paralela usando diferentes algoritmos en diferentes
procesos: diferentes formas de calcular las cotas y la estimación del
beneficio, y distintos criterios de selección.
Se repiten nodos pero hay pocas comunicaciones.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
15 / 35
Branch and Bound - paralelismo
1
2
Búsqueda paralela usando diferentes algoritmos en diferentes
procesos: diferentes formas de calcular las cotas y la estimación del
beneficio, y distintos criterios de selección.
Se repiten nodos pero hay pocas comunicaciones.
Expansión en paralelo de cada nodo.
Se necesita que la expansión de cada nodo sea costosa: gran
número de hijos, alto coste de los cálculos de cada hijo.
Gestión de la lista de nodos vivos centralizada ⇒ muchas
comunicaciones.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
15 / 35
Branch and Bound - paralelismo
1
2
3
Búsqueda paralela usando diferentes algoritmos en diferentes
procesos: diferentes formas de calcular las cotas y la estimación del
beneficio, y distintos criterios de selección.
Se repiten nodos pero hay pocas comunicaciones.
Expansión en paralelo de cada nodo.
Se necesita que la expansión de cada nodo sea costosa: gran
número de hijos, alto coste de los cálculos de cada hijo.
Gestión de la lista de nodos vivos centralizada ⇒ muchas
comunicaciones.
Evaluación paralela de subproblemas:
Se asignan a cada proceso varios nodos de la LNV.
Posibilidades de distribución:
Estática: pocas comunicaciones, se pueden difundir las cotas para
podar; la asignación de los nodos puede ser balanceada o
ponderada.
Dinámica con bolsa de tareas: más comunicaciones. La
actualización de la bolsa puede ser inmediata o pospuesta.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
15 / 35
Branch and Bound - Subconjunto que suma una cantidad
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
16 / 35
Branch and Bound - comunicación de las cotas
Comunicar las cotas puede contribuir a podar más, pero conlleva
comunicaciones.
¿Cuándo y cómo comunicarlas?
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
17 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (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ón de las tareas a realizar: Bolsa
de tareas.
Y la gestión 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énez (Universidad de Murcia)
Curso 2015-2016
19 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (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ón cuando la bolsa está vacı́a y todos los
trabajadores han acabado (problema de detección de terminación).
Útil en problemas combinatorios: búsqueda en árbol.
La asignación dinámica de trabajos se hace para balancear la
computación.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
21 / 35
Bolsa de tareas
Bolsa de tareas: conjunto de descriptores de tareas; cada descriptor
especifica una computación.
En Memoria Compartida:
una estructura centralizada de la que los trabajadores toman trabajos
y posiblemente depositan otros nuevos. Acceso en exclusión mutua.
En Paso de Mensajes:
la estructura está en la memoria de uno o varios procesos,
la petición y depósito de tareas conllevan comunicación.
Tener en cuenta:
◮
◮
◮
Contención:
Por ser la bolsa de tareas centralizada.
Cuantos más procesadores mayor contención.
Balanceo:
Si se descentraliza la bolsa hay mayor desbalanceo y menor
contención
⇒ compromiso entre contención y balanceo.
Terminación:
El test de terminación es global ⇒ sincronización.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
22 / 35
Ejemplo - Algoritmo de Dijkstra de camino más 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
0
0
0
0
0
∞
∞
4
4
4
4
4
8
7
7
7
7
∞
∞
5
5
5
5
∞
∞
∞
15
12
12
¿Cómo paralelizar?:
Pasos independientemente: Paralelización Sı́ncrona.
Procesos tomando elementos de la cola, pero genera nuevos elementos para la cola y
modifica el vector de distancias ⇒ regiones crı́ticas, que limitan el paralelismo.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
23 / 35
Esquema de trabajadores replicados con bolsa de tareas
en OpenMP
inicializar bolsa de tareas;
inicializar tareas ;
omp set num threads(trabajadores );
acabados = trabajadores ;
#pragma omp parallel private(fin,n)
{
fin=FALSO;
Mientras no fin hacer
#pragma omp critical
{
Si tareas = 0 y acabados = trabajadores entonces
fin=VERDADERO;
sino Si tareas , 0 entonces
acabados = acabados − 1;
tareas = tareas − 1;
tomar tarea de la bolsa;
finsi
}
Si tomada tarea entonces
resolver tarea y generar n nuevas tareas;
#pragma omp critical
{
tareas = tareas + n;
acabados = acabados + 1;
insertar las n tareas en la bolsa;
}
finsi
finmientras
}
Domingo Giménez (Universidad de Murcia)
bolsa de tareas y variables tareas y
acabados son globales.
Inicialmente 1 tarea y todos los
trabajadores inactivos
(acabados = trabajadores ).
Los hilos trabajan mientras queden
tareas u otros hilos trabajando
(pueden generar nuevas taareas).
No es necesario un Maestro. Todos
los hilos hacen el mismo trabajo.
Es necesario acceder en exclusión
mutua a las variables compartidas.
Curso 2015-2016
24 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
25 / 35
Maestro-Esclavo - esquema centralizado
Comunicaciones entre el maestro y los esclavos.
El maestro conoce la condición de fin y la comunica a los esclavos.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
26 / 35
Esquema Maestro-Esclavo con número fijo de trabajos y
distribución dinámica de trabajo
// Se dispone de p procesos esclavos
// y de t tareas
Si proceso maestro entonces
asignar un trabajo a cada esclavo;
t = t − p;
Mientras t,0 hacer
Recibe(resultado );
Envia(trabajo , esclavo del que ha recibido );
t = t − 1;
finmientras
Mientras p,0 hacer
Recibe(resultado );
Envia(marca de fin, esclavo del que ha recibido );
p = p − 1;
finmientras
sino
Recibe(trabajo , maestro );
resolver trabajo ;
Envia(resultado , maestro );
Recibe(trabajo o marca de fin, maestro );
Mientras no recibida marca de fin hacer
resolver trabajo ;
Envia(resultado , maestro );
Recibe(trabajo o marca de fin, maestro );
finmientras
finsi
Domingo Giménez (Universidad de Murcia)
Suponemos que inicialmente hay
tareas para todos los esclavos.
El Maestro recibe resultados y envı́a
nuevos trabajos.
Cuando no le quedan más trabajos
manda señales de fin a todos los
esclavos.
Los Esclavos reciben tareas,
las resuelven,
mandan el resultado
y reciben nuevas tareas,
hasta que reciben la señal de fin.
Curso 2015-2016
27 / 35
Esquema Maestro-Esclavo con generación de nuevos
trabajos por los esclavos
Si proceso maestro entonces
generar tareas iniciales; asignar un trabajo a cada esclavo;
// solicitudes representa el número de solicitudes de trabajo que ha recibido el maestro y que no ha atendido
solicitudes = 0;
Mientras solicitudes,p hacer
Recibe(resultado trabajos o solicitud );
Si recibidos trabajos entonces
incluir trabajos en la bolsa;
Para cada esclavo esperando hacer
Si trabajo disponible entonces
Envia(trabajo , esclavo ); solicitudes = solicitudes − 1;
finsi
finpara
finsi
Si recibida solicitud entonces
solicitudes = solicitudes + 1;
Si trabajo disponible entonces
Envia(trabajo , esclavo del que ha recibido );
finsi
finsi
finmientras
enviar señal de fin a todos los esclavos;
sino
Recibe(trabajo , maestro ); resolver trabajo ;
Envia(resultado y trabajos , maestro );
Recibe(trabajo o marca de fin, maestro );
Mientras no recibida marca de fin hacer
resolver trabajo ; Envia(resultado y trabajos , maestro );
Recibe(trabajo o marca de fin, maestro );
finmientras
finsi
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
28 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
29 / 35
Problemas del esquema de bolsa de tareas centralizado
La bolsa de tareas puede convertirse en un cuello de botella: muchas
comunicaciones entre el Maestro y los Esclavos.
Se puede intentar mejorar:
◮
◮
◮
◮
Aumentando la granularidad de las tareas: asignar varias tareas a la
vez. Pero esto puede empeorar el balanceo.
Quedándose los esclavos con tareas que han generado.
Haciendo petición anticipada de tareas.
Con una jerarqı́a de maestros. Dificulta la detección de fin.
Se puede intentar solventar el problema descentralizando la bolsa de
tareas.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
30 / 35
Bolsa de tareas descentralizada
Mucho más compleja de gestionar.
¿A quién se hacen las peticiones?
¿Cómo se sabe que no quedan tareas por resolver?
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
31 / 35
Solicitud cı́clica de trabajo
Los procesos solicitan trabajos cı́clicamente.
¿Cuándo se acaba?
Puede pasar que pida a todos y ninguno tenga trabajo,
pero que mientras estaba haciendo las peticiones otro proceso que ya
habı́a evaluado genere nuevos trabajos.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
32 / 35
Algoritmo de Dijkstra de detección de fin
Al hacer la petición se manda un testigo Blanco.
Si por el camino pasa por un proceso que mandó trabajo a otro el testigo
pasa a Negro.
Si vuelve el testigo Blanco se acaba.
Si vuelve Negro puede volver a pedir.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
33 / 35
Contenido
1
Recorrido de árboles
Backtracking
Branch and Bound
2
Trabajadores replicados
Bolsa de tareas
Maestro-Esclavo
Esquemas descentralizados
3
Prácticas
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
34 / 35
Más ejemplos en el capı́tulo 6 del libro de Introducción a la
Programación Paralela.
Hay un ejemplo del Problema de las reinas con esquema
maestro-esclavo con generación de nuevas configuraciones.
También ejemplos de Backtracking en el Concurso de Programación
Paralela:
2011, problema E.
2012, problema D.
2013, problemas F y G. El mismo con Memoria Compartida y Paso
de Mensajes.
2014, problemas F y G. El mismo con Memoria Compartida y Paso
de Mensajes.
En la práctica se pedirá la implementación de alguno de ellos en
OpenMP y MPI, puede que pidiendo una implementación concreta
(maestro-esclavo, bolsa centralizada, asignación estática o
dinámica...) o bien seleccionando el alumno la técnica a usar.
Domingo Giménez (Universidad de Murcia)
Curso 2015-2016
35 / 35