Download x - CC301: Algoritmos Paralelos

Algoritmos de búsqueda para problemas de
optimización discreta
Algoritmos Paralelos
Glen Rodriguez R. (basado en Kumar)
Contenido
• Problemas de Optimización discreta
• Algoritmos de búsqueda secuencial
• Factor de overhead
• Algoritmos paralelos para búsqueda “primero en
profundidad”
• Algoritmos paralelos para búsqueda “primero el mejor”
Problemas de Optimización discreta
• Son una clase de problemas a computacionalmente
costosos que son objeto de interés tanto teórico como
práctico. Muchos de estos problemas son NPcompletos.
• Un tipo se solución es usar algoritmos de búsqueda, que
buscan el espacio de las posibles soluciones sujetas a
restricciones.
Definiciones
• Un problema de optimización discreta se puede
expresar como una tupla (S, f).
• S es un conjunto de soluciones (finito o infinito contable)
• f es una función de costo que mapea cada elemento de
S en el conjunto de los números reales R.
• Se desea encontrar una solución factible xopt, tal que
f(xopt) ≤ f(x) para todo x  S.
• Uso práctico: diseño de circuitos impresos tipo VLSI
layouts, planeamiento del movimiento de unrobot,
generación de casos de prueba en Ing. de software,
ubicación de fábricas o almacenes.
Ejemplo: programación lineal entera 0/1
• Dados: una matriz m×n llamada A, un vector m×1 llamado
b, y un vector n×1 llamado c.
• Hallar un vector n×1 vector
pueden ser 0 ó 1.
cuyos elementos solo
• Dicho vector debe satisfacer la restricción
y debe minimizar la función
• Relacionado con otro problemas como el “problema de la
mochila”
Ejemplo: puzzle con mínimos movimientos
16-puzzle
Un caso de problema 8-puzzle : (a) configuración inicial; (b)
configuración final; y (c) secuencia de movimientos posible
que lleva de la configuración inicial a la final.
Conceptos básicos de optimización discreta
• El espacio factible S es enorme.
• El problema puede ser reformulado como un problema de
encontrar la ruta de costo mínimo en un grafo que va de un
nodo inicial designado a uno de varios posibles nodos
objetivo.
• Cada elemento x de S puede ser visto como una de las
rutas.
• A ese grafo se le llama estado de espacios.
Conceptos básicos de optimización discreta
• Con frecuencia, es posible estimar el costo para alcanzar el
estado objetivo desde un estado intermedio  estimado
heurístico.
• Cálculo exacto vs. sub-estimación (admisible)
• Cálculo exacto : divide y vencerás.
Ejemplo de heurística
• Asumir que cada posición del grid del 8-puzzle se
representa por un par ordenado.
• La distancia entre (i,j) y (k,l) se define como |i - k| + |j - l|.
Distancia Manhattan.
• La suma de las distancias Manhattan entre las posiciones
iniciales y finales es una heurística admisible.
Y aquí que pinta el paralelismo?
• Muchos problemas son NP-hard. ¿Ayudaría paralelizar?
• En muchos casos, el tiempo de ejecución promedio o el de
casos de la vida real son polinomiales.
• Caso contrario, soluciones suboptimas en tiempo polinomial.
• Otros problemas no tienen tantas soluciones por chequear,
pero las necesitan muy rápido.
• En otros problemaas, se desea el xopt , o algo muy cercano,
sin importar el tiempo de procesamiento.
Algoritmos secuenciales de búsqueda
• El espacio de búsqueda: árbol o grafo?
• Programación Lineal entera 0/1: árbol
• 8-puzzle: grafo.
• Ojo: un grafo puede “explotarse” en un árbol.
• Pros y contras de cada uno?.
Explotando o desdoblando árboles
Algoritmos para búsqueda “primero en
profundidad”
• Se aplica a árboles.
• Primero se expande el nodo inicial y se generan sus
sucesores. En cada paso subsecuente, se expande uno de
los nodos más recientemente generados.
• Si no hay éxito, se hace “backtrack” o sea se retrocede al
nodo padre y se explora otro nodo hijo.
• Es recomendable ordenar los nodos basados en la
probabilidad de llegar a la solución desde cada nodo 
búsqueda dirigida.
• Ventaja del “primero en profundidad” : uso lineal de la
memoria respecto a la profundidad del árbol.
Algoritmos para búsqueda “primero en
profundidad”
Estados resultantes de procesar los 3 primeros pasos de la búsqueda
“primero en profundidad” aplicados al 8-puzzle.
Backtracking simple
• Se realiza la búsqueda hasta encontrar la primera
solución factible y allí termina.
• No hay garantía de hallar la solución óptima.
• No se usa información heurística para ordenar nodos.
• Backtracking ordenado si usa uses heurísticas para
ordenar nodos.
Branch-and-Bound
• Es un tipo de búsqueda “primero en profundidad”
orientado a encontrar la mejor solución. Cada vez que
se encuentra una mejor solución, el algoritmo actualiza
la solución y su función de costo.
• Evita explorar caminos que garantizan que no habrá
mejoras.
• Al terminar la búsqueda queda la mejor solución global
(solución óptima).
Busca iterativa profundizadora
• Qué pasa si la solución es la
marcada en rojo?
• El backtracking simple tardaría
mucho en llegar allí.
• La iteración profundizadora
establece un límite en la
profundidad de la búsqueda (se
sigue trabajando con “primero en
profundidad”).
• Si no se encuentra solución, el
límite de profundidad de
incrementa y se repite el proceso.
…
…
…
Iterativa profundizadora A* (IDA*)
• Usa un límite en el costo de la ruta en vez de la
profundidad.
• IDA* define una función del nodo x en el espacio de
búsqueda como l(x) = g(x) + h(x). Donde g(x) es el costo
de llegar al nodo, y h(x) es un estimado heurístico del
costo de llegar desde el nodo a la solución.
• Luego de cada paso fallido, el límite de costo es
incrementado al del nodo que excedió el límite anterior
de costo por la menor cantidad.
• Si la heurística h es admisible, IDA* llega a obtener la
solución óptima.
Estructuras de datos y necesidades de memoria
• Las estructuras dependen si uso un algoritmo iterativo o
uno recursivo. Las necesidades de memoria no.
• En el iterativo: en cada paso de la B.P.P., se deben poder
saber en que alternativa me quede en cada nivel y/o
cuáles me faltan.
• Si m = memoria necesitada para guardar un estado, y d =
máxima profundidad la memoria total requerida es
O(md).
• Para un B.P.P. paralelo el árbol puede ser representado
como un stack.
• Ese stack ocupa memoria linealmente proporcional a la
profundidad del árbol.
Estructuras de datos y necesidades de memoria
Algoritmos de búsqueda “primero el mejor”
• B.P.M. usan una heurística para guiar la búsqueda.
• La principal estructura de datos es una lista, llamada “lista
abierta”, que guarda los nodos no explorados ordenados por
la estimación heurística de c/u.
• Se escoge el mejor nodo de la lista, se expande, y sus hijos
se insertan según el orden heurístico.
• Si la heurística es admisible, B.P.M hallará la solución
óptima.
Algoritmos de búsqueda “primero el mejor”
• Si aplico B.P.M. a grafos, debo modificarlo para tomar en
cuenta que puedan haber muchos caminos para llegar al
mismo nodo.
• Una lista cerrada guarda todos los nodos que ya se han
visitado.
• Si existe un nuevo nodo expandido en la lista cerrada o
abierta, con mejor valor heurístico, no se debe insertar el
nodo en la lista abierta.
Algoritmo A*
• Un tipo de B.P.M. que usa heurísticas admisibles.
• Defino una función l(x) para cada nodo x con l(x)= g(x) +
h(x).
• Donde g(x)= costos de llegar a x, y h(x) es un estimado
heurístico admisible del costo de ir de x a la solución.
• Se ordena a la lista abierta respecto a l(x).
Consumo de memoria: exponencial en función a la
profundidad!
Ejemplo
Factor de overhead
• El trabajo hecho por las búsquedas secuenciales muchas
veces es diferente del trabajo de las paralelas.
• Si W es el trabajo serial y WP el paralelo, el factor de
overhead s = WP/W.
• La cota superior del speed-up es p×(W/WP).
Retos de la B.P.P. paralela
• El cómputo es dinámico y no estructurado.
– Por qué?
• Cómo descompongo el espacio de búsqueda?
– Si no es perfecta, el factor de overhead > 1
• Como mapear?
– Se puede balancear la carga?
B.P.P. paralela
• Descomposición  una parte del espacio de búsqueda
a cada procesador.
• Varios sub-árboles pueden buscarse a la vez.
• Pero los sub-árboles pueden ser de diferente tamaño 
paralelismo no balanceado.
• Y como estimo A PRIORI el tamaño de un sub-árbol.
• Necesito balance de carga dinámico.
B.P.P. paralela
Balance de carga dinámico en B.P.P.
• Cuando un procesador se queda sin trabajo, se le asigna
trabajo de otro procesador.
• Implementación difiere en Message Passing vs. Shared
Memory.
• Cuando un procesador obtiene la solución, todos los
procesadores terminan.
• Se usan stacks independientes por procesador .
• El nodo o nodos inciales se asignan a un solo
procesador.
Balance de carga dinámico en B.P.P.
Esquema general
Esquemas de balance de carga
• A quién se le solicita trabajo?  quiero distribución
pareja GLOBAL.
• Round robin asíncrono: contador independiente por
procesador que hace request tipo round-robin.
• Round robin global: contador único global, cada
procesador usa ese contador global para sus requests.
• Polling aleatorio: un procesador escoge al azar a otro
procesador para pedirle el trabajo.
Analizando balance de carga en B.P.P
• Asumamos que el tiempo de procesamiento tiene relación
directa con la cantidad de request mínimo para que cada
procesador reciba por lo menos un request de otro
procesador.
• En round robin asíncrono, esa cantidad de request es O(p2)
en el peor caso.
• Para Round Robin global es O(p)
• Para Polling aleatorio: el peor caso no tiene cota superior.
Analizando balance de carga en B.P.P
• Entonces, casos promedios:
• En round robin asíncrono, el proceso total es O(p2 log p).
Hace muchas llamadas o request.
• Para Round Robin global, el proceso total es O(p2 log p).
Hace pocos request, pero el procesador que tiene el
contador global es cuello de botella.
• Para Polling aleatorio, el proceso total es O(p log2 p).
Hace más llamadas que r.r.global pero menos que
r.r.asíncrono, y no hay cuellos de botella.
Caso experimental: problema SAT
p (num.procesadores)
Speed-ups de B.P.P paralela usando esquemas RRA (ARR), RRG
(GRR) y RP (PA)
B.P.P paralela tipo Branch-and-Bound
• Se parecen a B.P.P.
• Cada procesador tiene una copia de la mejor solución
hasta el momento. Sirve como límite local.
• Si un procesador encuentra otra solución, la compara
con la mejor actual. Si el costo es mejor, se vuelve la
nueva mejor actual y se envía a todos los demás
procesadores.
• “Mejores soluciones” detectadas a la vez en más de 1
procesador: la solución final no se altera, solo se afecta
la rapidez de cómputo.
IDA* paralelo
Hay dos algoritmos
• Límite común en costo : y luego se usa B.P.P paralela
sujeta a ese límite en cada procesador. Poco escalable
si el límite común es bajo.
• Límite variable en costo: complicado y sujeto a
verificación.
B.P.M. paralela
• Estructura clave: lista abierta (implementada como una
cola con prioridad).
• Cada procesador invoca al cierre de exclusión mutua
de la cola, saca el mejor nodo, luego desbloquea la
cola.
• Se generan los hijos del nodo, se estiman sus
funciones heurísticas, y se insertan dichos hijos a la
lista abierta, previo cierre.
• Como p procesadores expanden p nodos en paralelo,
el ordende trabajo de este algoritmo paralelo sería
diferente al de su versión secuencial.
B.P.M. paralela
B.P.M. paralela
• La lista abierta es cuello de botella (por contención)
• Sea texp = tiempo promedio para expander un nodo, y
taccess = tiempo promedio para accesar la lista abierta para
buscar siguiente nodo a expandir, n= número de nodos del
árbol o grafo.
• El tiempo secuencial = n(taccess+ texp).
• El tiempo paralelo no puede bajar de ntaccess.
• La cota superior del speed-up es (taccess+ texp)/taccess
B.P.M. paralela
• Evitemos la contención usando varias listas abiertas.
• Al inicio el espacio de búsqueda se divide
equitativamente entre estas listas abiertas.
• Se puede leer de más de una lista a la vez.
• Como el valor heurístico de los nodos explotados puede
divergir de una lista a otra, cada cierto tiempo debemos
rebalancear las listas, emparejando la calidad de los
nodos.
B.P.M. paralela
Ejemplo de rebalanceo usando comunicación en anillo
B.P.M. paralela
Ejemplo de rebalanceo usando comunicación en pizarra
B.P.M. paralela para grafos
• Recuerden: hay lista cerrada, donde debe hacerse una
búsqueda con clave=estado.
• Se usan hash.
• Hashing se puede paralelizar usando 2 funciones: una hashea
cada nodo a un processor, y la otra hashea dentro del
procesador.
• Además se pueden usar muchas listas abiertas.
• Si un nodo no existe en una lista cerrada, es insertado en la lista
abierta del destino de la primera función de hash.
• Por la naturaleza del hash, lo más probable es que cada lista
abierta tenga más o menos la misma calidad de nodos.
Resumen
Naturaleza del
espacio de
búsqueda
Memoria
requerida
Heurística
Calidad de la
solución
BPP simple
(backtracking)
Árbol
Lineal en
profundidad
No usa
Cualquiera
factible
BPP dirigida
(ordenada)
Árbol
Lineal en
profundidad
Local
Cualquiera
factible
BPP Branch
and Bound
Árbol
Lineal en
profundidad
Semi global
Óptima
IDA*
Árbol
Lineal en
profundidad
Semi global
Óptima
BPM , A*
Árbol o grafo
Exponencial
Global
Óptima