Bases de datos optimizacion

1

Algoritmos de búsqueda para problemas de optimización discreta
Marcelo Gutiérrez Patzi, Roberto Alejandro Fernández, Felix Tito Herrera, Yohoni Cuenca Sarzuri.
Abstract—el presente trabajo describe el enfoque orientado a las estrategias de búsqueda, pero desde el punto de vista paralelo. Index Terms—estrategias comunicación, nodos, listas. de búsqueda, estrategias de

Aún más si seconsidera el uso de más de 2 procesadores para el mismo árbol se tendrá un desbalance mucho peor. (ver nodos C,D,E,F)

Introduction os algoritmo de búsqueda pueden ser utilizados Lpara resolver problemas de optimización discreta (DOPs), una clase de problemas costosos computacionales con significado teórico e interés practico la búsqueda de algoritmos de resolución DOPs por evaluación son solucionescandidatas desde un conjunto ilimitado para encontrar una que satisfaga un criterio de problema especifico DOPs es también referido para problemas de combinatoria

Se ha podido apreciar que la partición estática no es

conveniente para resolver problemas sobre un árbol no-uniforme por el pobre rendimiento que ofrece. Por lo tanto es necesario balancear el espacio de búsqueda entre losprocesadores de manera dinámica. Sin embargo, la partición dinámica conlleva a una difícil obtención del tamaño de los espacios de búsqueda de manera anticipada. En el balanceo de carga dinámica, cuando un proceso termina su trabajo obtiene trabajo de otro proceso que aún tiene trabajo. Cabe indicar que aunque la distribución dinámica de trabajo genera una sobrecarga en la comunicación entre procesos,mejora el desbalanceo de carga en los mismos.

2

Un esquema general de cómo trabaja la distribución de trabajo dinámica se encuentra en la siguiente figura.

b. Global Round Robin (GRR). En este caso se usa una única variable global llamada ‘target’a la cual todos hacen los ‘request’. Antes de responder un ‘request’ el valor de ‘target’ se incrementa en 1 modulo p (target+1 mod p). Por tantoel procesador solicitante intentar obtener la carga de trabajo del procesador que tiene el ID igual al ‘target’. GRR asegura que las solicitudes de trabajo sean distribuidas igualmente para todos los procesadores. Las desventaja sin embargo de este esquema radica en impedimento de acceder a ‘target’.

Parámetros Importantes de la Búsqueda en Profundidad Paralela (Parallel DFS ó PDFS) En los PDFSDos son las características críticas para determinar su rendimiento: 1. El método de división de trabajo en un procesador 2. El esquema para escoger el asignador (donor) de trabajo cuando un proceso se vuelve a estado pasivo. Para la primera característica se tienen 3 estrategias de balanceo de carga de trabajo: a. Asynchronos Round Robin (ARR). En ARR, cada procesador mantiene una variableobjetivo donde se encuentra la etiqueta (id) del proceso (donor) a quien se debe solicitar la carga de trabajo. Cada vez que se realiza un request al proceso ‘donor’ se incrementa la etiqueta en 1 modulo p (label +1 mod p) Es posible que en cierto momento ambos procesadores soliciten al mismo ‘donor’ la carga de trabajo.

c. Random Polling (RP). Elección Aleatoria de los procesadores a quienessolicitar la carga de trabajo. En este cada procesador tiene la misma probabilidad de ser ‘donor’. Es decir de otorgar carga de trabajo. Marco General para el Análisis de Búsqueda en Profundidad Paralela Desde que la sobrecarga de comunicaciones es la sobrecarga predominante en la Búsqueda en Profundidad Paralela (PDFS). Se debe considerar un método para calcular la sobrecarga en las comunicaciones paracada esquema de balanceo de carga. Detección de la Terminación En el funcionamiento de los PDFS se debe considerar el hecho de que el algoritmo siga en su búsqueda de la solución sin llegar a ningún resultado. Es decir, de alguna manera se debe comunicar a todos los procesos que se ha encontrado la solución buscada. Existen 2 algorimos de Detección de Terminación. Algoritmo de Detección de...