View
4
Download
0
Category
Preview:
Citation preview
ALGORITMOS MASIVAMENTE
PARALELIZADOS DE LA
MMC
ISMAEL HERRERA REVILLA UNAM
RECONOCIMIENTOS
• Una parte significativa de los trabajos aquí
reportados han sido desarrollados como parte
de las tesis doctorales del Dr. Antonio Carrillo y
del candidato a doctor Alberto Rosas
• Agradezco también la colaboración del Dr. Luis
Miguel de la Cruz en algunos aspectos
• Finalmente, el apoyo de los Dres. Guillermo
Hernández y Norberto Vera
2
A.
INTRODUCCIÓN
2
PREÁMBULO
Los modelos matemáticos de muchos sistemas de interés, que
incluyen sistemas macroscópicos muy importantes de la ingeniería y la ciencia, son una gran variedad de sistemas de ecuaciones diferenciales parciales (EDPs) cuyos métodos de solución se basan en el procesamiento computacional de sistemas algebraicos de gran escala
4
COMPUTACIÓN EN PARALELO
• Las computadoras en paralelo disponibles hoy en día,
son un recurso invaluable para el progreso y aplicación
de los métodos de solución de las EDPs. Su uso eficiente
necesita códigos con un alto grado de paralelización
• Las dificultades principales para la aplicación del
cómputo en paralelo se deben a la necesidad de
coordinar multitud de procesadores que ejecutan tareas
diferentes y de transmitir información entre ellos
PARADIGMA
DE LA PROGRAMACIÓN EN PARALELO
•Estas dificultades desaparecen cuando cada uno de los
procesadores puede ejecutar sus tareas de manera
independiente
•Desarrollar códigos que ejecuten la tarea global,
asignándole a cada procesador tareas que sean
independientes
7
i
DESCOMPOSICIÓN DE DOMINIO
PARADIGMA DE LOS MÉTODOS
DESCOMPOSICIÓN DE DOMINIO
Obtener la solución global a través de
resolver problemas locales,
exclusivamente
NON-OVERLAPPING DDMs
•They are the most effective procedures for applying parallel computing to the solution of partial differential equations
• Non-overlapping DDMs permit better uncoupling of ‘local’ problems
•However, even in non-overlapping DDMs, the set of nodes used are over-lapping
10
11
12
13
GOAL OF THE LINE OF
RESEARCH HERE PRESENTED
•Develop a general discretization method, applicable to any BVP, using systems of non-overlapping nodes
• Develop domain decomposition algorithms for numerical formulations obtained applying such discretization methods
•Test the degree of parallelization that can be obtained using numerical formulations so obtained
DESCRIPCIÓN DE LA PLÁTICA •Voy a presentar una manera, que hemos introducido en la literatura internacional, de discretizar cualquier ecuación diferencial parcial, o sistema de tales ecuaciones, en un sistema de nodos sin traslape • Voy a desarrollar algoritmos DDM utilizando esa forma de discretizar • Explicaré brevemente, cómo utilizándolos se alcanza el paradigma de los DDM • Mostraré algunos resultados numéricos
B.
MÉTODO GENERAL DE
DISCRETIZACIÓN SIN
TRASLAPE
2
MODELO MATEMÁTICO
17
u fL
18
MODELO NUMÉRICO
CON TRASLAPE
MU g
19
SE INTRODUCE MALLA GRUESA
20
21
SE INTRODUCE
CONJUNTO DE NODOS
SIN TRASLAPE
22
23
FORMULACIÓN SIN TRASLAPE
24
0aAu f and ju
ALGUNOS DETALLES
25
VECTORES DERIVADOS
26
LOS VECTORES CONTINUOS
Y
LOS DE PROMEDIO CERO
27
1
es ' , cuando , es independiente de
es de ' : , 0
Los subespacios de vectores continuos y de promedio cero
son complementos ortogonales
E
u continuo' u p
u promedio cero' u p
28
29
La matriz es la proyección en el
subespacio continuo
La matriz es la proyección en el
subespacio de promedio cero
a
j
LAS MATRICES Y a j
DEFINICIÓN DE LA MATRIZ
30
1
E
A A
, , , , , ,pqp q p qA A with A M
,
pq
pq pq
MM M with M
s p q
C.
FORMULACIÓN DE SCHUR
y
ALGORITMOS DVS
2
32
NODOS INTERIORES: ; NODOS DE INTERFASE: ;
NODOS ; NODOS
NODOS : LOS QUE NO SON PRIMALE
S
PRIMALES DUALES
DUALES
FORMULACIÓN DE SCHUR
33
0aSu f and ju
1
S A A A A
ALGORITMOS DVS
34
1
INFORMACION BUSCADA
PRIMAL 1
PRIMAL 2
DUAL 1
DUAL 2
u
S aSu
jSu
Su
v
SUBESPACIOS DE VECTORES DUALES
35
11 12; W jW W aW
1 1
21 22; W S aSW W S jSW
1 1
31 32; W SaS W W S jS W
ALGORITMOS PRIMALES
36
12u W
1S aS
21W 12W
a
Algoritmo DVS PRIMAL # 1
22v W
j
11W 22W
1S jS
Algoritmo DVS PRIMAL # 2
ALGORITMOS DUALES
37
11W
1S jS
32W 11W
j
Algoritmo DVS DUAL # 1
31W
a
12W 31W
1SaS
Algoritmo DVS DUAL # 2
RESUMEN
Todos los algoritmos de descomposición
de dominio precondicionados consisten
de la aplicación de dos proyecciones
sucesivas, la primera proyecta un
elemento del subespacio donde se
encuentra la información buscada a otro
subespacio y la segunda lo regresa a ese
mismo subespacio. Estas acciones se
ilustran en las figuras siguientes
38
ALGORITMOS PRIMALES
39 u
11W jW
12W aW
1
21W S aSW
1
22W S jSW
1S aS
1S jS
a
j
v vj
1vS jS j
1S aSu
1aS aSu
ALGORITMOS DUALES
40
11W jW
12W aW
1
31W SaS W
1
32W S jS W
1SaS
a
1S jS
j
1S jS
1jS jS
1SaS a
D. CÓMO
ALCANZAR LOS PARADIGMAS
DE LOS DDM
2
EXPRESIONES MATRICIALES
42
1 1
1 1 1
PRIMAL ES
0
0
aS aSu aS f and ju
S jS j S jS jS f and aS
v v
1 1
1 1 1
DUAL E S
0
0
jS jS jS jS f and a
SaS a SaS f and jS
43
1
S A A A A
1
A A A A A
~10A w A A w , j
v v
1
A w
v
APLICACIÓN DE S
44
1
CÁLCULO DE LA ACCIÓN DE A
11
1
E
A A
45
and rW W
1 1S A
1 11 1
1
1 1 1 1
A AA AA
A A A A
1APLICACIÓN DE S
1 1 1S w A w A w
46
1A w
v
1 1
1
E
A A
1
0t
A w A A w , j
v v
1APLICACIÓN DE A
1
A w A
v v
47
APLICACIÓN DE Y a j
jw w aw
CONCLUSIONES
• Las computadoras en paralelo disponibles hoy en día,
son un recurso invaluable para el progreso y aplicación
de la modelación matemática y computacional. Su uso
eficiente necesita códigos con un alto grado de
paralelización
• Los modelos matemáticos de los sistemas
macroscópicos de la ciencia y la ingeniería son
sistemas de ecuaciones diferenciales parciales (EDPs)
• Los resultados presentados en esta plática indican que,
para la solución de las EDPs, los códigos más
eficientes son los que se desarrollan utilizando el
método de discretización DVS, introducido en el
ámbito mundial por el IGF 48
EL FUTURO
• Desarrollar códigos muy eficientes,
paralelizados masivamente
• Aplicarlos a problemas específicos
importantes
• Probar fehacientemente la superioridad de
nuestros métodos
• Darles difusión internacional para que el
IGF y la UNAM reciban el reconocimiento
que merecen por estos logros
49
Recommended