PDF de programación - Aplicaciones científicas de la computación paralela

Aplicaciones científicas de la computación paralela

Departamento de Informática y Sistemas

Grupo de Computación Científica y Programación Paralela

http://luna.inf.um.es/grupo investigacion

Programación Paralela y Computación de Altas Prestaciones

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

1 / 30

Temas a tratar

1 Computación científica y aplicaciones

2 Aplicaciones en el grupo CCPP

3 Análisis de sedimentos

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

2 / 30

Computación científica y aplicaciones

Temas a tratar

1 Computación científica y aplicaciones

2 Aplicaciones en el grupo CCPP

3 Análisis de sedimentos

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

3 / 30

Computación científica y aplicaciones

Computación Científica

Integración de modelos con técnicas computacionales para solución de
problemas complejos,
con grandes volúmenes de datos (big data) y/o necesidades de
computación (High Performance Computing)

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

4 / 30

Computación científica y aplicaciones

Aplicaciones

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

5 / 30

Computación científica y aplicaciones

... y también

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

6 / 30

Computación científica y aplicaciones

Evolución de aplicaciones en TOP500

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

7 / 30

Computación científica y aplicaciones

Tipos de problemas

De gran desafío
Alto coste computacional θ (an)
problemas NP, optimización combinatoria...

Coste moderado θn3, θn4...

De gran dimensión

pero gran dimensión, por ejemplo n = 1.000.000 (8 Teras)

De tiempo real
Coste bajo pero necesidad de respuesta inmediata
juegos, control, atención médica...

Clima Bio Diseño

Simul

Juego

Imagen

recetas

G. Desafío

G. Dimensión
Tiempo Real

X
X

X
X
X

X
X

X
X

X

X
X

X

X

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

8 / 30

Computación científica y aplicaciones

Problemas de Gran Desafío

Alto coste computacional θ (an)

G. Desafío

G. Dimensión
Tiempo Real

Clima

X
X

Bio
X
X
X

Diseño

Simul

Juego

Imagen

recetas

X
X

X
X

X

X
X

X

X

Problemas NP, optimización combinatoria:
Planificación, Logística,
Asignación de recursos,
Estudio de eficiencia de organizaciones
Biología, Medicina:
Búsquedas en DNA,
Diseño de fármacos
Diseño
Cuando se trata de determinar componentes (ejemplos, filtros de
señal, diseño de puentes con restricciones...)
Recetas?
si varios componentes e intentar combinarlos para satisfacer distintas
restricciones y maximizando algunos aspectos

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

9 / 30

Computación científica y aplicaciones

Problemas de Gran Dimensión

Coste moderado (θ (np)) pero gran tamaño

G. Desafío

G. Dimensión
Tiempo Real

Clima

X
X

Bio
X
X
X

Diseño

Simul

Juego

Imagen

recetas

X
X

X
X

X

X
X

X

X

En algunos casos los problemas de memoria son mayores que los de computación

Clima:
Simulaciones con mallado muy fino
Tiempo cuadrático (superficie) o cúbico (espacio) que aumenta de orden con la
evolución temporal

Bioinformática:
Problemas de búsqueda en cadenas, con bases de datos muy grandes

Diseño y Simulación:
Puede necesitarse mallado muy fino
El coste aumenta por el número de simulaciones a realizar

Imagen:
Generación de imágenes para películas,
muchas imágenes y gran precisión

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

10 / 30

Computación científica y aplicaciones

Problemas de Tiempo Real

Requieren respuesta en un plazo de tiempo “corto”
recetas

Imagen

Diseño

Clima

Simul

Juego

G. Desafío

G. Dimensión
Tiempo Real

X
X

Bio
X
X
X

X
X

X
X

X

X
X

X

X

Clima:
Si la predicción es para el día siguiente

Medicina:
Asistencia inmediata

Simulación:
Si se realiza para controlar un sistema, expansión de un incendio...

Juego e Imagen:
Generación de 24 imágenes por segundo

Recetas:
Si se proporcionan los requerimientos o datos personales en el mismo
momento

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

11 / 30

Computación científica y aplicaciones

Librerías

Pero seguramente habrá disponible para el problema con el que estamos
trabajando librerías paralelas optimizadas:

Álgebra lineal densa: BLAS, LAPACK, MAGMA, PLASMA,
ScaLAPACK, CUBLAS, CULA, ATLAS, GotoBLAS, MKL.
Álgebra lineal dispersa: ARPACK, SPARSE, SPARSE-BLAS,
ITPACK, SVDPACK, SuperLU, Trilinos, PETSc.
Optimización: HeO, ParadisEO, MALLBA, GitHub.
Transformada de Fourier: FFTPACK, P3DFFT, FFTW.
Científicas: MOOSE, COOLFluid, OpenFVM, PyClaw, PetIGA,
ROMS...

Información de librerías en

http://www.netlib.org/liblist.html
http://www.netlib.org/utk/people/JackDongarra/la-sw.html

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

12 / 30

Computación científica y aplicaciones

Librerías - Ventajas

Facilitan el desarrollo de software

El software obtenido es portable

y su eficiencia se basa en la implementación eficiente de las rutinas
básicas.

Multiplicación de matices 1000 × 1000 en sistema con 12 núcleos, tiempo en segundos

núcleos:
BLAS 1
BLAS 2
BLAS 3

1
11.15
0.61
0.14

2
10.66
0.30
0.072

8
10.63
0.099

12
4
10.63
10.64
0.17
0.11
0.044 0.030 0.055

de 0.25 Gflops, con uso de librería 20 Gflops, con paralelismo implícito a 100 Gflops

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

13 / 30

Aplicaciones en el grupo CCPP

Temas a tratar

1 Computación científica y aplicaciones

2 Aplicaciones en el grupo CCPP

3 Análisis de sedimentos

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

14 / 30

Aplicaciones en el grupo CCPP

Miembro del grupo CCPP

Grupo de Computación Científica y Programación Paralela
(http://luna.inf.um.es/grupo investigacion)

Javier Cuenca (DITEC), investigador principal. Optimización de rutinas de álgebra lineal y
aplicaciones en medicina.
José Matías Cutillas (asesor de computación). Optimización de rutinas metaheurísticas y
aplicaciones.
Luis Pedro García (UPCT). Optimización de rutinas de álgebra lineal y sistemas paralelos.
Domingo Giménez (DIS). Rutinas de álgebra lineal y metaheurísticas y aplicaciones.
Jose Juan López Espín (UMH, modelos econométricos y aplicaciones en medicina)

Colaboraciones y estudiantes:

Gregorio Bernabé (DITEC, tratamiento de imágenes médicas)
Murilo do Carmo Boratto (UNAB, aplicaciones en sistemas multicore+multiGPU)
Jesús Cámara (Tesis, optimización de rutinas de álgebra lineal en sistemas híbridos)
José Carlos Cano (TFM, optimización de algoritmos paralelos para análisis cinemático de
sistemas multicuerpo basado en ecuaciones de grupo)
Francisco José Herrera (TFG, optimización de rutinas de álgebra lineal en
multinúcleo+multiGPU)
Baldomero Imbernón (Tesis, UCAM, paralelismo en problemas de docking)

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

15 / 30

Aplicaciones en el grupo CCPP

Un ejemplo - Tesis de Murilo

Modelos Paralelos para la Resolución de

Problemas de Ingeniería Agrícola, tesis de

Murilo do Carmo Boratto, en la UPV

Tres problemas en la zona del Rio S˜ao

Francisco, en Brasil

Representación del relieve

Interpolación de variables meteorológicas

Modelado de corrientes de ríos

Modelos

Mínimos cuadrados
Representación matricial
Ecuaciones diferenciales

Métodos

Algoritmos matriciales
Computación eficiente en sistemas
heterogéneos multicore+multiGPU
Técnicas de autooptimización de
software

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

16 / 30

0 1000 2000 3000 4000 5000 0 1000 2000 3000 4000 5000 0 200 400 600 800 1000 1200zxyz Aplicaciones en el grupo CCPP

Un ejemplo - Análisis envolvente de datos (DEA), UMH

Análisis de eficiencia de varias unidades de decisión (DMU)

Cada unidad k varias entradas x y salidas y

Problema de optimización para cada unidad

Disponibles métodos exactos, tipo Branch and Bound, y librerías
(CPLEX)

alto coste de ejecución

necesidad de paralelismo y métodos aproximados (metaheurísticas)

y operaciones matriciales en la evaluación de las restricciones y
cálculo del fitness

Posibilidad de métodos híbridos: exactos con metaheurísticas

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

17 / 30

Un ejemplo - DEA - Problema de Programación Lineal

Aplicaciones en el grupo CCPP

max βk − 1
s.t.

m

i=1

−
t
ik
xik

m
−βk xik +n
−βk yrk +n
i=1 νik xij +s
−m

s

r =1

t+
βk + 1
= 1
rk
s
yrk
∀i
j=1 αjk xij + t−
ik = 0
rk = 0 ∀r
j=1 αjk yrj − t +
r =1 µrk yrj + djk = 0 ∀j
νik ≥ 1
∀i
∀r
µrk ≥ 1
djk ≤ Mbjk
∀j
αjk ≤ M(1 − bjk )
∀j
∀j
bjk = 0, 1
βk ≥ 0
∀i
ik ≥ 0
t−
∀r
rk ≥ 0
t +
∀j
djk ≥ 0
αjk ≥ 0
∀j

(c.1)
(c.2)
(c.3)
(c.4)
(c.5)
(c.6)
(c.7)
(c.8)
(c.9)
(c.10)
(c.11)
(c.12)
(c.13)
(c.14)

Aplicaciones científicas de la computación paralela

Prog. Paralela y Computación de Altas Prestaciones

18 / 30

Aplicaciones en el grupo CCPP

Un ejemplo - Metaheurísticas parametrizadas (Tesis José
Matías)

El Esquema

Inicializar(S,Par