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