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 anterior | Volver al principio del trabajo | Página siguiente |