aplicaciones científicas de la programación paralela en el...
TRANSCRIPT
Aplicaciones Cientıficas de la Programacion Paralela enel Grupo de Computacion Cientıfica y Programacion
Paralela de la Universidad de Murcia
Domingo Gimenezdis.um.es/~domingo
Grupo de Computacion Cientıfica y Programacion Paralelaluna.inf.um.es/grupo investigacion
Departamento de Informatica y Sistemas, Universidad de Murcia
Universidad de Murcia, 2019
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 1 / 35
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 2 / 35
Aplicaciones en el grupo de CCPP
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 3 / 35
Aplicaciones en el grupo de CCPP
Grupo CCPP
Lıneas de trabajo
AplicacionesEjemplo de Francisco Jose Herrera.Presentacion en pagina del grupo.
Computacion NumericaAlgoritmos Matriciales Paralelos, y Autooptimizacion.Ejemplo de Jesus Camara.
OptimizacionMetaheurısticas paralelas.Ejemplo de Jose Matıas Cutillas.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 4 / 35
Aplicaciones en el grupo de CCPP
Aplicaciones en el grupo de CCPP
luna.inf.um.es/grupo investigacionNumerico Optimizacion
Simulacion climaticaHidrodinamicaElectromagnetismoRepresentacion del terrenoTratamiento de senal acusticaTratamiento de imagenesdocking de moleculasEconometrıaAnalisis envolvente de datosConstantes cineticasConsumo electricidadAnalisis de sedimentosSeries temporalesSistemas multicuerpo
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 5 / 35
Analisis Envolvente de Datos (DEA)
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 6 / 35
Analisis Envolvente de Datos (DEA)
Problema
Analisis de eficiencia de varias unidades de decision (DMU)
Cada unidad k varias entradas x y salidas y
Problema de optimizacion para cada unidad
Disponibles metodos exactos, tipo Branch and Bound, y librerıas(CPLEX)
alto coste de ejecucion
necesidad de paralelismo y metodos aproximados (metaheurısticas)
y operaciones matriciales en la evaluacion de las restricciones ycalculo del fitness
Posibilidad de metodos hıbridos: exactos con metaheurısticas
Martın Gonzalez, Jose J. Lopez-Espın, Juan Aparicio, Domingo Gimenez,Jesus T. Pastor: Using Genetic Algorithms for Maximizing TechnicalEfficiency in Data Envelopment Analysis, The International Conferenceon Computational Science, Reykjavık, Iceland, 1-3 June, 2015
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 7 / 35
Analisis Envolvente de Datos (DEA)
Modelo de Programacion Matematica
max βk − 1m
∑mi=1
t−ikxik
s.t.
βk + 1s
∑sr=1
t+rk
yrk= 1 (c .1)
−βkxik +∑n
j=1 αjkxij + t−ik = 0 ∀i (c .2)
−βkyrk +∑n
j=1 αjkyrj − t+rk = 0 ∀r (c .3)
−∑m
i=1 νikxij +∑s
r=1 µrkyrj + djk = 0 ∀j (c .4)νik ≥ 1 ∀i (c .5)µrk ≥ 1 ∀r (c .6)
djk ≤ Mbjk ∀j (c .7)αjk ≤ M(1− bjk) ∀j (c .8)
bjk = 0, 1 ∀j (c .9)βk ≥ 0 (c .10)t−ik ≥ 0 ∀i (c .11)t+rk ≥ 0 ∀r (c .12)djk ≥ 0 ∀j (c .13)αjk ≥ 0 ∀j (c .14)
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 8 / 35
Analisis Envolvente de Datos (DEA)
Resultados
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 9 / 35
Analisis Envolvente de Datos (DEA)
Combinacion con metodos numericos de optimizacion ehiperheurısticas
Schemes Hyperheuristic Metaheuristic
m = 2, n = 50, s=1 0.393 0.393m = 3, n = 50, s=2 0.576 0.579m = 4, n = 50, s=2 0.606 0.609m = 4, n = 50, s=3 0.518 0.520m = 5, n = 50, s=3 0.488 0.502m = 6, n = 50, s=4 0.455 0.430
Martin Gonzalez-Rodrıguez, Jose-Juan Lopez-Espın, Juan Aparicio,Domingo Gimenez, El-Ghazali Talbi: A parameterized scheme of meta-heuristics with exact methods for determining the Principle of LeastAction in Data Envelopment Analysis. CEC 2017: 588-595
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 10 / 35
Series temporales
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 11 / 35
Series temporales
Series Temporales Multivariantes
Con Big Data, cada vez mas datos de diversidad de campos.
En algunos casos, tienen evolucion temporal: series temporales.
Metodo tradicional de obtencion de modelos por expertos es cada vezde mas difıcil aplicacion.
Series Temporales Multivariantes:Parametros de los que se toman valores pediodicamente,determinar la evolucion temporal de los parametros,el valor de un parametro en un instante puede depender de sus valoresen instantes anteriores y de los de otros parametros.Puede haber parametros externos, que influyen en los internos perono influidos por estos.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 12 / 35
Series temporales
Datos de la serie temporal
d parametros, t instantes de tiempoSerie temporal es Y ∈ Rt×d : y
(1)1 . . . y
(1)d
.... . .
...
y(t)1 . . . y
(t)d
Dependencias temporales con i instantes de tiempo anteriores.
Datos externos al modelo, z , que influyen en los valores de y pero nose ven influenciados: z
(1)1 . . . z
(1)e
.... . .
...
z(t)1 . . . z
(t)e
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 13 / 35
Series temporales
Formulacion matricial
Dependencia de valores de un instante j en funcion de los valores anteriores:
y (j) ≈ y (j−1)A1 + y (j−2)A2 + . . . + y (j−i)Ai + z (j−1)B1 + z (j−2)B2 + . . . + z (j−k)Bk + a
Al , 1 ≤ l ≤ i , de dimension d × d , representa la dependencia de los datos con los valoresde l instantes anteriores;Bl , 1 ≤ l ≤ k, de dimension e × d , dependencias de factores externos.
En forma matricial:
Y (i + 1 : t, :) ≈ Y (i : t − 1, :)A1 + Y (i − 1 : t − 2, :)A2 + . . . + Y (1 : t − i , :)Ai +
Z(i : t − 1, :)B1 + Z(i − 1 : t − 2, :)B2 + . . . + Z(i − k + 1 : t − k, :)Bk + A0 =
[Y (i : t − 1, :)| . . . |Y (1 : t − i , :)|Z(i : t − 1, :)| . . . |Z(i − k + 1 : t − k, :)|1]
A1
...Ai
B1
...Bk
a
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 14 / 35
Series temporales
Problema de mınimos cuadrados
Obtener el modelo consiste en calcular Al , Bl y a que minimizan ladiferencia.
Problema de mınimos cuadrados con matriz de incognitas dedimension (d · i + e · k + 1)× d .
Y es Y (i + 1 : t, :), X la matriz formada por submatrices de Y , Z yel vector 1, y A la formada por las matrices Al , Bl y el vector a:
minA
∣∣∣∣∣∣Y − X A∣∣∣∣∣∣
Tipos:
Sin restricciones en las entradas de las matrices.
Puede que los valores esten en unos ciertos rangos,
o que sean de un conjunto.
Puede que los valores de un parametro no influyan en los de otro.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 15 / 35
Series temporales
Problemas matriciales
Rutinas y librerıas para estos tipos de problemas (Matlab, LAPACK).
Metodos basados en descomposiciones matriciales y metodositerativos.
Iterativos: partir de valores proporcionados por los expertos en elcampo de los datos, o resolver ecuaciones parciales y comenzar labusqueda desde ellas.
Explotacion de la estructura tipo Toeplitz por vectores.
Optimizacion del calculo del fitness (metodos numericos):X ∗ (A+D) = X ∗A+X ∗D, X ∗A precalculado y X ∗D coste lineal.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 16 / 35
Series temporales
Problematica estadıstica
Normalmente se pretende minimizar un estimador estadıstico.
Puede incluir el determinante de la matriz de covarianzas (Akaike).
La solucion del problema de mınimos cuadrados se puede usar comopunto de partida para optimizar el estimador con busqueda local,
o se puede optimizar directamente con el estimador usandometaheurısticas.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 17 / 35
Series temporales
Diversidad de problemas
Identificacion de variables externas.
Determinacion de la amplitud de las dependencias temporales.
Intervalo de realizacion de medias para evitar influencia defluctuaciones.
Variacion del modelo con el tiempo: series temporales de modelos deseries temporales.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 18 / 35
Series temporales
Campos de aplicacion
Datos meteorologicos.
Datos medicos, proyecto de Jose Juan Lopez Espın.
Datos economicos
Por ahora, con datos economicos aproximaciones satisfactorias, con datosmedicos peores predicciones.
Alfonso L. Castano, Javier Cuenca, Jose Matias Cutillas Lozano,Domingo Gimenez, Jose-Juan Lopez-Espın, Alberto Perez-Bernabeu:Parallelism on Hybrid Metaheuristics for Vector Autoregression Models.HPCS 2018: 828-835
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 19 / 35
Determinacion de componentes por analisis de sedimentos
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 20 / 35
Determinacion de componentes por analisis de sedimentos
Problema de determinacion de componentes
Problema del Grupo de Polımeros del Departamento deQuımica-Fısica de la Universidad de Murcia.http://leonardo.inf.um.es/macromol/
Analisis de sedimentacion de una solucion compuesta,a partir de planteamiento deJose Garcıa de la Torre. Analysis of Sedimentation experiments, 2014.
Determinar la concentracion de cada componente en el compuesto.Cada componente dado por su masa, Mk , y coeficiente de friccion, fk .
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 21 / 35
Determinacion de componentes por analisis de sedimentos
Experimento
Se centrifuga el compuesto. Medidas en distintos instantes de tiempo,tj , 1 ≤ j ≤ nt , de una senal optica en posiciones con distancias ri ,1 ≤ i ≤ nr .
La senal es funcion de la posicion y del tiempo: z(r , t).
En instante inicial, con la solucion en reposo, la senal tiene el mismovalor z0 en todas las posiciones r , z(r , 0) = z0.
Solucion con nk componentes, cuya contribucion a la senal es zk , con1 ≤ k ≤ nk .
La senal z es aditiva en los componentes: z =∑nk
k=1 zk .
Cada zk es de la posicion r y el tiempo t.
Para cada componente tenemos el peso molecular, Mk , y elcoeficiente de friccion, fk
y queremos obtener la concentracion del componente en la solucion,yk .
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 22 / 35
Determinacion de componentes por analisis de sedimentos
Determinacion de la senal
Se realizan varios experimentos, 1 ≤ l ≤ nexp
que dependen de parametros experimentales, el , y entre los que estala velocidad de rotacion, ωl .
La senal de un experimento para una posicion y un tiempodeterminado es zexp,l (ri , tj ; el), o simplificando zexp,l (ri , tj),
y se obtiene de forma aditiva a partir de las senales de loscomponentes:
zexp,l (ri , tj ; el) =
nk∑k=1
zk (ri , tj ;Mk , fk , yk ; el)
y como la contribucion a la senal de cada componente es lineal:
zexp,l (ri , tj ; el) =
nk∑k=1
(yk · zk (ri , tj ;Mk , fk ; el))
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 23 / 35
Determinacion de componentes por analisis de sedimentos
Simulacion
Se dispone de procedimientos teoricos con los que estimar los valoresde senal para cada experimento, en cada momento de tiempo y encada posicion, zcal ,l (ri , tj ; el).
Obtener los valores de yk con los que la diferencia entre los zexp,l yzcal ,l se minimicen. Problema de mınimos cuadrados:
42(p) =1
nexp
1
nr
1
nt
nexp∑l=1
nr∑i=1
nt∑j=1
(zexp,l (ri , tj ; el)−
nk∑k=1
yk · zk,cal,l (ri , tj ; el)
)2
Sin conocer los zcal ni los zexp, podemos estudiar metodos dedeterminacion de los yk suponiendo valores de zcal ,l determinados yvalores de yk , se generan con ellos los zexp,l que se obtendrıan, seperturban, y se aplica el metodo de resolucion del problema demınimos cuadrados para determinar cuanto de lejos esta la solucionobtenida con la utilizada en la generacion de los datos experimentales.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 24 / 35
Determinacion de componentes por analisis de sedimentos
Malla de valores
Se considera una distribucion uniforme de los parametros pesomolecular y coeficiente de friccion.
Los M en rango [Mmin,Mmax ], y los de f en [fmin, fmax ].
Se discretizan con nM y nf valores:
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 25 / 35
Determinacion de componentes por analisis de sedimentos
Parametros del problema
Tıpicamente datos de entre 1 y 5 experimentos,
alrededor de 200 posiciones
y 200 instantes de tiempo.
Numero de ecuaciones entre 4 · 104 y 2 · 105.
Si se toman 20 valores de peso molecular y otros 20 para elcoeficiente de friccion, el numero de incognitas es 200.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 26 / 35
Determinacion de componentes por analisis de sedimentos
Refinamiento de la malla
Se puede resolver con esos valores y descartar combinaciones conaportaciones al compuesto muy bajas (valores de yk por debajo de unumbral)y resolver nuevos problemas definiendo mallas mas finas en zonas delmallado donde la aportacion sea mayor:
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 27 / 35
Determinacion de componentes por analisis de sedimentos
Solucion numerica
Se forma la matriz A obtenida con la aplicacion de la ecuacion paralos n = nexp · nr · nt experimentos, posiciones en la celda que rota einstantes de tiempo.
El numero de incognitas es m = nM · nf .
Tenemos A ∈ Rn×m,
y se plantea el problema a optimizar miny ||Ay − b||, con b es elvector de senales obtenidas experimentalmente.
El problema tenemos la restriccion de que0 ≤ yk ≤ 1,∀k / 1 ≤ k ≤ nk , y
∑nkk=1 yk = 1.
Es un problema de mınimos cuadrados no negativos, o NNLS(Non-Negative Least Squares), con variables acotadas y con unarestriccion lineal.
En Matlab esta la rutina lsqlin.
Necesaria realizacion de rutinas paralelas y/o utilizacion de librerıasparalelas
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 28 / 35
Determinacion de componentes por analisis de sedimentos
Aproximacion metaheurıstica
Se buscan valores de yk para el problema de mınimos cuadrados.
Se generan individuos (valores de los yk con∑k
i=1 yk = 1)
la funcion de fitness es la diferencia entre los zexp y los zcal
y se utilizan tecnicas de combinacion y mejora de elementos para irmejorando el conjunto de individuos:Algoritmos Geneticos, Scatter Search, Ascension de colinas, Coloniade hormigas...
Necesaria implementacion de metaheurısticas paralelas y/o utilizacionde librerıas paralelas de optimizacion
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 29 / 35
Sistemas Multicuerpo
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 30 / 35
Sistemas Multicuerpo
Estructura con grupos de ecuaciones
Sistema multicuerpo Plataforma de Stewart
Jose-Carlos Cano, Javier Cuenca, Domingo Gimenez, Mariano Saura-Sanchez, Pablo Segado-Cabezos: A parallel simulator for multibody sys-tems based on group equations. The Journal of Supercomputing 75(3):1368-1381 (2019)
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 31 / 35
Sistemas Multicuerpo
Simulador
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 32 / 35
Sistemas Multicuerpo
Utilizacion del simulador para optimizacion de rutinas de algebralineal en entornos heterogeneos.
Planteamiento de un problema de optimizacion: determinar posicioninicial y parametros de impulso para obtener una trayectoria deseada.El calculo del fitness consiste en simular la trayectoria (metodosnumericos) y comparar con la deseada.
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 33 / 35
Creditos
Contenidos
1 Aplicaciones en el grupo de CCPP
2 Analisis Envolvente de Datos (DEA)
3 Series temporales
4 Determinacion de componentes por analisis de sedimentos
5 Sistemas Multicuerpo
6 Creditos
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 34 / 35
Creditos
En orden de aparicion
Martın Gonzalez, Jose J. Lopez-Espın, Juan Aparicio, Domingo Gimenez, Jesus T. Pastor: Us-ing Genetic Algorithms for Maximizing Technical Efficiency in Data Envelopment Analysis, TheInternational Conference on Computational Science, Reykjavık, Iceland, 1-3 June, 2015
Martin Gonzalez-Rodrıguez, Jose-Juan Lopez-Espın, Juan Aparicio, Domingo Gimenez, El-GhazaliTalbi: A parameterized scheme of metaheuristics with exact methods for determining the Principleof Least Action in Data Envelopment Analysis. CEC 2017: 588-595
Alfonso L. Castano, Javier Cuenca, Jose Matias Cutillas Lozano, Domingo Gimenez, Jose-JuanLopez-Espın, Alberto Perez-Bernabeu: Parallelism on Hybrid Metaheuristics for Vector Autore-gression Models. HPCS 2018: 828-835
Jose Garcıa de la Torre. Analysis of Sedimentation experiments, 2014
Jose-Carlos Cano, Javier Cuenca, Domingo Gimenez, Mariano Saura-Sanchez, Pablo Segado-Cabezos: A parallel simulator for multibody systems based on group equations. The Journal ofSupercomputing 75(3): 1368-1381 (2019)
Informacion adicional en http://dis.um.es/~domingo/:
Metaheurısticas paralelas: optimizacion y aplicaciones, Master de Computacion Paralela yDistribuida, Technical University of Valencia, May 2019
Computacion de altas prestaciones, una herramienta en ayuda de la ciencia, presentationthe festivity of San Alberto, November, 14, 2014
Domingo Gimenez (UMU - CCPP) Aplicaciones de Programacion Paralela UMU, 2019 35 / 35