El problema de Optimización
Objetivo: min t(s, vap, SP)? vap ? AP
Asignación de procesadores a las necesidades software
Técnicas:
Grafos de precedencia
Optimización analítica
Árboles de asignación
Estrategias heterogéneas (HoHe, HeHo)?
Metaheurísticas
……
9
El problema de Optimización Cuestiones relevantes:
Particionado de datos
Análisis de dependencias
Asignación de recursos
Equilibrado de carga
Hipótesis:
Construcc. sotfware Modelado Autooptimización tº ejecución
Necesidad de establecer una metodología de trabajo
10
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos 11
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos Aplicaciones en esquemas paralelos iterativos 12
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos Aplicaciones en esquemas paralelos iterativos Desarrollo metodologías autoopt. sist. homogéneos 13
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos Aplicaciones en esquemas paralelos iterativos Desarrollo metodologías autoopt. sist. homogéneos Desarrollo metodologías autoopt. sist. heterogéneos 14
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos Aplicaciones en esquemas paralelos iterativos Desarrollo metodologías autoopt. sist. homogéneos Desarrollo metodologías autoopt. sist. heterogéneos Estrategias heterogéneas (HoHe, HeHo)? 15
Metodología Tesis Etapas de la tesis
Construir modelo tº ejecución algoritmos iterativos Aplicaciones en esquemas paralelos iterativos Desarrollo metodologías autoopt. sist. homogéneos Desarrollo metodologías autoopt. sist. heterogéneos Estrategias heterogéneas (HoHe, HeHo)?
Metaheurísticas
16
Metodología de autooptimización 17
Construcción modelo tº ejecución 18
Esquemas iterativos Esquema iterativos usados en multitud de problemas: Progr. Dinámica, Dijkstra, genéticos, sist. ecuaciones …
Ejecución de un conjunto de instrucciones de forma iterativa hasta la condición de fin
Secuenciales Tipos Homogéneos Paralelos Heterogéneos
Caso (Programación Diferentes Prueba dinámica) Esquemas
Diferentes formas de calcular los datos: por filas, columnas, diagonales
19
Programación dinámica Por filas
20
Programación dinámica Por filas
Por columnas
21
Programación dinámica Por filas
Por columnas
Por diagonales
22
Programación dinámica Usados como ejemplos: Problema monedas, Mochila
Definición N: cantidad a devolver n: número tipos de monedas vi: valor de la moneda de tipo i, vi>0 qi: cantidad de monedas de tipo i, qi>0 c[i,j]= mínimo número de monedas para devolver cantidad j usando hasta los i tipos de monedas
c[i,j] = min { c[i-1,j-k*vi]+k}, 1< =i< =n, 1< =j< =N, k=0,..,j/vi
Objetivo: c[n,N]
Ecuación 23
Esquema Secuencial
for i=1 to numero_de_decisiones for j=1 to tamaño_problema obtener la solución óptima con i decisiones y tamaño de problema j endfor endfor
Programación dinámica 24 FILAS
COLUMNAS
Esquema Paralelo (dependencia de datos)?
for i=1 to numero_de_decisiones En Paralelo: for j=1 to tamaño_problema obtener la solución óptima con i decisiones y tamaño de problema j endfor Comunicaciones entre procesos endEnParalelo endfor
Esquemas iterativos 25
AUTOOPTIMIZACIÓN EN SISTEMAS HOMOGÉNEOS 26
Autooptimización en sistemas homogéneos Homogéneos: características similares no exactamente iguales
Relativa facilidad construir modelo tiempo ejecución
Determinar número procesos (p) = procesadores (P)?
Pruebas realizadas sobre diferentes sistemas:
SOLARIS/SUN (SUNEt)? (Un. Murcia)? PenFE (Un. Murcia) HOMOGÉNEOS ORIGIN 2000 (Un. Polit. Cat.) HPC160 (Inter e intranodo)? (Un. Polit. Cart.)?
KIPLING (Univ. Polit. Val.) HETEROGÉNEOS TORC (Univ. Tennessee)?
27
Autooptimización en sistemas homogéneos DEPENDENCIA DE DATOS (VERSIONES A y B) 28
Número procesadores Número procesadores Complejidad Complejidad Tamaño 10.000 Tamaño 50.000 Tamaño 100.000 Tamaño 500.000 Número procesadores Número procesadores Cociente de tiempos de ejecución entre versiones A y B en SUNEt Complejidad Complejidad Autooptimización en sistemas homogéneos 29
Modelo teórico: Ttotal = Tcomputación + Tcomunicación
Coste secuencial:
Coste computacional paralelo (qi grande):
Coste comunicaciones:
Parámetro de complejidad o granularidad para aumentar comput.
Los SP son tc , ts y tw
El único AP es p
(Gp:) Proceso Pp-1
Autooptimización en sistemas homogéneos 30
Diferentes posibilidades estimar parámetros sistema
Diferencias en speed-up Utilidad de sistemas autooptimización
Autooptimización en sistemas homogéneos 31
Tiempos de comunicaciones en SUNEt (izq) y HPC160 (der)? Ratios de tiempos de comunicaciones en SUNEt (izq) y HPC160 (der)? Autooptimización en sistemas homogéneos 32
Comparativa entre el número de procesos con los que se obtiene mejor tiempo de ejecución Autooptimización en sistemas homogéneos 33 El sistema debe decidir cómo ejecutar el algoritmo
Media de los speedups máximos variando tamaño y granularidad Speedup variando procesadores, granularidad y tamaño Autooptimización en sistemas homogéneos 34
Estimación de SP aritméticos: resolviendo un problema reducido
Estimación de SP de comunicac:
Ping-pong (CP1)? Solución de problema reducido variando el número de procesadores (CP2)? Solución de problema reducido variando el número de procesadores y el tamaño del problema (CP3)?
Comparativa del número de procesadores seleccionados con diferentes métodos con respecto al tmb Autooptimización en sistemas homogéneos 35
Cocientes entre tiempos de ejecución obtenido con los diferentes métodos con respecto al tmb Autooptimización en sistemas homogéneos 36
Comparación con usuarios:
Voraz (UV): usa todos los procesadores disponibles Conservador (UC): usa la mitad de los procesadores disponibles Experto (UE): usa un número de procesadores en función del tamaño del problema
Cocientes entre tiempos de ejecución obtenido con los diferentes usuarios con respecto al tmb Autooptimización en sistemas homogéneos 37
Cocientes entre tiempos de ejecución obtenidos con los diferentes usuarios y métodos con respecto al tmb Autooptimización en sistemas homogéneos 38
AUTOOPTIMIZACIÓN EN SISTEMAS HETEROGÉNEOS 39
Autooptimización en sistemas heterogéneos Heterogéneos: agrupar elementos del sistema según características similares no exactamente iguales.
Mayor dificultad construir modelo tiempo ejecución.
Buscar parámetros algorítmicos / min tº ejec
t(s, AP, SP)?
AP= d, p d=(d0,d1,…,dP-1) SP= Más complejos
Construir algoritmos heterogéneos
Diferentes posibilidades Desarrollo métodos (exactos y/o aproximados de mapeo (asignar procesos a procesadores))?
40
Distribución del trabajo y asignación de procesos a procesadores en un esquema de programación dinámica, en algoritmos heterogéneos (HeHo) (a) y homogéneos(HoHe) (b)? Autooptimización en sistemas heterogéneos 41
Autooptimización en sistemas heterogéneos 42 Posibilidades de representación del árbol de asignación:
Árbol de asignación con 2 tipos de procesadores y p procesos
Necesidad de limitar la altura del mismo
Cada nodo lleva asociada 3 cotas: EET, LET, GET.
Uso de técnicas de búsqueda en árboles para optimizar el modelo de tº ejecución
Autooptimización en sistemas heterogéneos 43
Desviación con respecto al tmb obtenido experimentalmente, de los tiempos obtenidos con diferentes métodos y usuarios en una combinación de TORC 1 17P4 + 1 Ath + 1 SPIII + 8 DPIII (a) y 1 Ath + 1 SPIII + 8 DPIII (b)? a) b)? Autooptimización en sistemas heterogéneos 44
Resultados de simulaciones diversas Autooptimización en sistemas heterogéneos 45
METAHEURÍSTICAS EN LA AUTOOPIMIZACIÓN 46
Metaheurísticas en la autooptimización OBJETIVO FINAL min tº ejec
Minimización analítica
Minimización numérica
Métodos exhaustivos
Métodos aproximados
Métodos heurísticos 47
Metaheurísticas en la autooptimización 48 Esquema General de las Metaheurísticas
Inicializar(S)?
while no se cumple CondiciondeFin(S) do
SS = ObtenerSubconjunto(S);
if |SS|>1 then SS1= Combinar(SS); else SS1=SS; end
SS2 = Mejorar(SS1); S = IncluirSoluciones(SS2)? end
Búsqueda Dispersa (particularización)?
Metaheurísticas en la autooptimización Esquema de la tecnica de Búsqueda Dispersa (particularización)?
CrearConjuntoInicial S; GenerarConjuntoReferencia RS;
while Convergencia no alcanzada do
Seleccionar elementos a combinar;
Combinar elementos seleccionados;
Mejorar elementos combinados;
ActualizarConjuntoReferencia RS con los elementos más prometedores y los más dispersos
end? 49
Metaheurísticas en la autooptimización Mapeo como un problema de optimización
Representación y codificación soluciones: (do,d1, …, dP-1)? di = nº procesos asignados al procesador i
Gran cantidad de alternativas a la hora de instanciar el algoritmo:
50
Metaheurísticas en la autooptimización
Comparación entre las posibilidades de opciones de selección e inclusión. Porcentaje en que mejora la búsqueda dispersa respecto al backtracking con poda Tiempos e iteraciones para diferentes métodos de selección e inclusión en el conjunto de referencia 51
Metaheurísticas en la autooptimización Simulaciones para comparar Búsqueda dispersa y backtracking con poda
52
Metaheurísticas en la autooptimización Pruebas en Kipling
53
Metaheurísticas en la autooptimización Relación entre tiempos de decisión y modelado en una simulación concreta 54
CONCLUSIONES Y TRABAJOS FUTUROS 55
Conclusiones y Trabajos Futuros Optimización Autooptimización
tº = f(s,AP,SP)? Hipótesis investigación? + Búsqueda óptimo
Métodos exactos (Búsqueda exhaustiva)?
Alternativas Métodos aproximados
Métodos metaheurísticos
56
Resultados generales en sistemas homogéneos(a), heterogéneos (b) y con el uso de metaheurísticas(c)?
Conclusiones y Trabajos Futuros a) b) 57 a) b) c)?
Conclusiones y Trabajos Futuros 58 Aportaciones
VecPar04. Sistemas homogéneos.
HeteroPar04,Parallel Computing04. Sistemas heterogéneos.
Para06, Maeb07. Metaheurísticas.
Cluster07.
ICCS08.
Journal of Supercomping 09.
Trabajos futuros
Mejorar el modelado el tiempo de ejecución, sobre todo en sistemas heterogéneos
Aplicación en diferentes esquemas algorítmicos (divide & conquer, master – slave, backtracking…)?
Metaheurísticas diversas (tabú, temple simulado, géneticos …
Construcción de un entorno para la prueba y evaluación de metaheurísticas.
| Página siguiente |