Static Load Balancing Applied to Time Dependent Mechanical Problems

Popis problému a motivace Realizace Výsledky ˇ Záver

Static Load Balancing Applied to Time Dependent Mechanical Problems O. Medek1 , J. Kruis2 , Z. Bittnar2 , P. Tvrdík1 1 Katedra poˇ cítaˇcu˚ ˇ Ceské vysoké uˇcení technické, Praha 2 Katedra stavební mechaniky ˇ Ceské vysoké uˇcení technické, Praha

Semináˇr numerické analýzy 2005


Obsah 1

Popis problému a motivace ˇ Casov eˇ závislé mechanické problémy Paralelizace ˇrešení systému lineárních rovnic Problém vyváženosti výpoˇctu Vyvažování pomocí Quality Balancing heuristiky

2

Realizace ˇ Doménová dekompozice delením grafu Quality Balancing heuristika

3

Výsledky

4

ˇ Záver


ˇ Casov eˇ závislé mechanické problémy Paralelizace ˇrešení SLR Problém vyváženosti výpoˇctu Vyvažování pomocí Quality Balancing heuristiky

Obsah 1


2


3

Výsledky

4

ˇ Záver



ˇ Casov eˇ závislé mechanické problémy

Závislost na cˇ ase.




Závislost na cˇ ase. Zanedbatelné inerciální síly.




Závislost na cˇ ase. Zanedbatelné inerciální síly. Pˇr.: analýza reaktorové tlakové nádoby v jaderných elektrárnách.



ˇ Rešení cˇ asoveˇ závislý mechanických problému˚

Prostorová diskretizace: metoda koneˇcných prvku˚ (MKP).




Prostorová diskretizace: metoda koneˇcných prvku˚ (MKP). ˇ Casová diskretizace: metoda koneˇcných diferencí + linearizace (Newtonov-Raphsonovou metodou) ⇒ iterace.




Prostorová diskretizace: metoda koneˇcných prvku˚ (MKP). ˇ Casová diskretizace: metoda koneˇcných diferencí + linearizace (Newtonov-Raphsonovou metodou) ⇒ iterace. V každé iteraci se ˇreší systém lineárních rovnic (SLR) Ax = b.




Prostorová diskretizace: metoda koneˇcných prvku˚ (MKP). ˇ Casová diskretizace: metoda koneˇcných diferencí + linearizace (Newtonov-Raphsonovou metodou) ⇒ iterace. V každé iteraci se ˇreší systém lineárních rovnic (SLR) Ax = b. Tyto SLR mají shodnou strukturu.




Prostorová diskretizace: metoda koneˇcných prvku˚ (MKP). ˇ Casová diskretizace: metoda koneˇcných diferencí + linearizace (Newtonov-Raphsonovou metodou) ⇒ iterace. V každé iteraci se ˇreší systém lineárních rovnic (SLR) Ax = b. Tyto SLR mají shodnou strukturu. Dále pˇredpokládáme úlohy se symetrickými, pozitivneˇ definitními ˇrídkými a velkými SLR.



Obsah 1


2


3

Výsledky

4

ˇ Záver



Paralelizace ˇrešení systému lineárních rovnic ˇ u˚ Metoda Schurových doplnk

1

Doménová dekompozice (DD).




1


2

ˇ Pˇreˇcíslování promenných.




1


2

ˇ Pˇreˇcíslování promenných. Sestavení podmatic.

3




1


2

ˇ Pˇreˇcíslování promenných. Sestavení podmatic. ˇ Cásteˇ cná faktorizace podmatic (výpoˇcet Schurových ˇ u). doplnk ˚

3 4




1


2

ˇ Pˇreˇcíslování promenných. Sestavení podmatic. ˇ Cásteˇ cná faktorizace podmatic (výpoˇcet Schurových ˇ u). doplnk ˚ ˇ Rešení redukovaného systému.

3 4

5




1


2

ˇ Pˇreˇcíslování promenných. Sestavení podmatic. ˇ Cásteˇ cná faktorizace podmatic (výpoˇcet Schurových ˇ u). doplnk ˚ ˇ Rešení redukovaného systému.

3 4

5 6

ˇ substituce na podmaticích. Zpetná



Doménová dekompozice (DD)

A B1

C1

C2

B2

C T1

C T2

B3

C3

C T3

R

ˇ Blokove–šípový tvar.




A B1

B2

C T1

C T2

C1

ˇ Blokove–šípový tvar.

C2

R je matice redukovaného problému.

B3

C3

C T3

R




A B1

C1

C2

B2

C T1

C T2

B3

C3

C T3

R

ˇ Blokove–šípový tvar. R je matice redukovaného problému. ˇ Rád vnitˇrních Bk zhruba stejný.




A B1

C1

C2

B2

C T1

C T2

B3

C3

C T3

R

ˇ Blokove–šípový tvar. R je matice redukovaného problému. ˇ Rád vnitˇrních Bk zhruba stejný. Šíˇrka hraniˇcních Ck a R je minimalizována.




A B1

B2

C T1

C T2

C1

Ak je podmatice vytvoˇrená na procesoru k .

C2

Ak

B3

C3

C T3

R

Bk

Ck

C Tk

R



ˇ Zápis blokove–šípový tvaru SLR

B1 x1 + C1 xR = b1 B2 x2 + C2 xR = b3 B3 x3 + C3 xR = b3 C1T x1

+

C1T x2

+ C1T x3 + RxR = bR





+

C1T x2

+ C1T x3 + RxR = bR

ˇ xk vnitˇrní promenné (x1 , x2 , x3 ).





+

C1T x2

+ C1T x3 + RxR = bR

ˇ xk vnitˇrní promenné (x1 , x2 , x3 ). ˇ xR hraniˇcní promenné.



ˇ Cásteˇ cná faktorizace podmatic

Ak Eliminují se pouze vnitˇrní ˇ promenné xk .

Bk

Ck

C kT

R





Bk

Ck

C Tk

R

Podmatice Ak jsou ˇrídké.





Bk

Ck

C Tk

R

Podmatice Ak jsou rˇídké. ˇ Cásteˇ cná faktorizace se provádí obálkovou (skyline) metodou.



Obálková metoda

Ak

Obálka = “množina prvku˚ okolo hlavní diagonály”. Mimo obálku jsou jen 0.

Bk

Ck

C Tk

R



Obálková metoda

Ak Bk

Ck

C Tk

R

Obálka = “množina prvku˚ okolo hlavní diagonály”. Mimo obálku jsou jen 0. ˇ Cásteˇ cná faktorizace se provádí pouze uvnitˇr obálky.



Obálková metoda

Ak Bk

Ck

C Tk

R

Obálka = “množina prvku˚ okolo hlavní diagonály”. Mimo obálku jsou jen 0. ˇ Cásteˇ cná faktorizace se provádí pouze uvnitˇr obálky. ˇ jsou pouze prvky uvnitˇr obálky. V pameti



Obálková metoda

Ak Bk C Tk

Ck

Obálka = “množina prvku˚ okolo hlavní diagonály”. Mimo obálku jsou jen 0. ˇ Cásteˇ cná faktorizace se provádí pouze uvnitˇr obálky. ˇ jsou pouze prvky uvnitˇr obálky. V pameti ˇ Pˇreˇcíslování promenných → minimalizace obálky.

R



Obálková metoda

Ak Bk C Tk

Ck

Obálka = “množina prvku˚ okolo hlavní diagonály”. Mimo obálku jsou jen 0. ˇ Cásteˇ cná faktorizace se provádí pouze uvnitˇr obálky. ˇ jsou pouze prvky uvnitˇr obálky. V pameti ˇ Pˇreˇcíslování promenných → minimalizace obálky.

R

Pˇreˇcíslování: hraniˇcní Sloanuv ˚ algoritmus.



Pˇríklad obálky

1 2 3 4 5 6 7 8 9

• • • 0 0 0 • • 0

• • • • 0 0 0 0

• • 0 • • • 0

• 0 0 0 • •

• • 0 0 0

• • • 0 • • 0 0 • •

•: diagonální prvek. 0: nula mimo obálku. • 0 : nuly a nenulové prvky uvnitˇr obálky. ˇ 1 – 6: vnitˇrní promenné. ˇ 7 – 9: hraniˇcní promenné.



Obsah 1


2


3

Výsledky

4

ˇ Záver



Problém vyváženosti výpoˇctu

ˇ na podmatice Ak zhruba stejného ˇrádu. DD delí




ˇ na podmatice Ak zhruba stejného ˇrádu. DD delí Doba cˇ ásteˇcné faktorizace závisí na velikosti obálky. V praxi se doby cˇ ásteˇcných faktorizací podmatic mohou lišit (až 2,5–krát).




ˇ na podmatice Ak zhruba stejného ˇrádu. DD delí Doba cˇ ásteˇcné faktorizace závisí na velikosti obálky. V praxi se doby cˇ ásteˇcných faktorizací podmatic mohou lišit (až 2,5–krát). ˇ (menšuje) velikost obálky až po Navíc pˇreˇcíslování mení DD.




ˇ na podmatice Ak zhruba stejného ˇrádu. DD delí Doba cˇ ásteˇcné faktorizace závisí na velikosti obálky. V praxi se doby cˇ ásteˇcných faktorizací podmatic mohou lišit (až 2,5–krát). ˇ (menšuje) velikost obálky až po Navíc pˇreˇcíslování mení DD.

J AK

ˇ ˇ ˇ VYVÁŽENOU DEKOMPOZICI ? UD ELAT VÝPO CETN E



Obsah 1


2


3

Výsledky

4

ˇ Záver


Spojení DD a pˇreˇcíslování

1. Doménová dekompozice 2. Pˇreˇcíslování










Quality Balancing heuristika

Domenova dekompozice

Precislovani

Odhad slozitosti cast.faktorizace

Odhadnuta slozitost



Quality Balancing heuristika Quality = míra, která se vyvažuje: ˇ pamet’ové nároky, výpoˇcetní složitost.




Prezentováno na EUROPAR’04 a PDCN’05 na jednoduchých úlohách mechaniky.




Prezentováno na EUROPAR’04 a PDCN’05 na jednoduchých úlohách mechaniky. Vyvážený výpoˇcet trvá kratší dobu.




Prezentováno na EUROPAR’04 a PDCN’05 na jednoduchých úlohách mechaniky. Vyvážený výpoˇcet trvá kratší dobu. Ale QB je znaˇcneˇ pomalejší nežli klasická DD.




Prezentováno na EUROPAR’04 a PDCN’05 na jednoduchých úlohách mechaniky. Vyvážený výpoˇcet trvá kratší dobu. Ale QB je znaˇcneˇ pomalejší nežli klasická DD. ˇ ˇ ren na vyvažování výpoˇcetní Tento pˇríspevek je zameˇ složitosti ˇrešení cˇ asoveˇ závislých mechanických problému, ˚ kde se projeví výhody QB.


ˇ DD delením grafu Quality Balancing heuristika

Obsah 1


2


3

Výsledky

4

ˇ Záver



Sít’ koneˇcných prvku˚ (KP) 1 5 9

a d g

6 10

4

3

2 b e h

7 11

c f

8 12

i

13 16 14 15 Elementy (koneˇcné prvky) a . . . i. Uzly 1 . . . 16. ˇ Každý uzel obsahuje stupneˇ volnosti (SV, promenné).



Duální graf

1 5 9

Sít’ KP reprezentovaná duálním grafem GD . 4 3 2

a d

6 10

g 13

b e

7 11

h 14

c f

b

d

e

g

h

c

8 f

12

i 15

a

16

i



Uzlový graf Sít’ KP reprezentovaná uzlovým grafem GN . 1 4 3 2 2 3

1 5 9

a d

6 10

b e

7 11

c f

8

5

12

9

6

13

h 14

8 12

10 g

7

4

11

i 15

16

13

14

15

16



ˇ DD delením grafu

ˇ DD se provádí pomocí delení GD hranovým rˇezem ˇ ˇ c METIS). (víceúrovnový deliˇ




ˇ DD se provádí pomocí delení GD hranovým rˇezem ˇ ˇ c METIS). (víceúrovnový deliˇ ˇ ⇒ Rozdelení síteˇ KP na podsíteˇ KP.




ˇ DD se provádí pomocí delení GD hranovým rˇezem ˇ ˇ c METIS). (víceúrovnový deliˇ ˇ ⇒ Rozdelení síteˇ KP na podsíteˇ KP. ˇ ⇒ Rozdelení GN vrcholovým rˇezem.




ˇ DD se provádí pomocí delení GD hranovým rˇezem ˇ ˇ c METIS). (víceúrovnový deliˇ ˇ ⇒ Rozdelení síteˇ KP na podsíteˇ KP. ˇ ⇒ Rozdelení GN vrcholovým rˇezem. ⇒ Dekompozice A na podmatice Ak .




ˇ DD se provádí pomocí delení GD hranovým rˇezem ˇ ˇ c METIS). (víceúrovnový deliˇ ˇ ⇒ Rozdelení síteˇ KP na podsíteˇ KP. ˇ ⇒ Rozdelení GN vrcholovým rˇezem. ⇒ Dekompozice A na podmatice Ak . ˇ ⇒ Uzly (promenné) patˇrící k více než jedné podsíti (podmatici) jsou hraniˇcní; ostatní jsou vnitˇrní.



ˇ DD delením grafu (obrázek) 1 a

b

c

d

e

f

g

h i Rozdeleny GD

Podsite KP vnitrni uzly hranicni uzly

Rozdeleny GN

vnitrni vrcholy

2

3

3

4

5 a6 b 7 7 c 8 d e 10 11 f 12 9 g 10 11 h i 13

14

14 15

16

1

2

3

3

4

5

6

7

7

8

10 11

12

14 15

16

9 10 11

hranicni vrcholy 13 14



ˇ ˇ Víceúrovnové delení grafu GD0

GD1

GD1

GD2

GD2 GD3

GD3 GD4

Pocatecni rozdeleni

Zjemnovani a vylepsovaci heuristika

Zhrubovani

GD0



Vylepšovací heuristika

Pˇresouvá supervrcholy (množiny vrcholu) ˚ mezi podgrafy.




Pˇresouvá supervrcholy (množiny vrcholu) ˚ mezi podgrafy. Vyvažuje poˇcet vrcholu˚ v podgrafech a zmenšuje hranový ˇrez.




Pˇresouvá supervrcholy (množiny vrcholu) ˚ mezi podgrafy. Vyvažuje poˇcet vrcholu˚ v podgrafech a zmenšuje hranový ˇrez. ˇ ˇ Nejvíce ze všech fází ovlivnuje výsledné delení.



Obsah 1


2


3

Výsledky

4

ˇ Záver



QB heuristika

Rozšiˇruje a modifikuje vylepšovací heuristiku.



QB heuristika

Rozšiˇruje a modifikuje vylepšovací heuristiku. ˇ Pro každý podgraf spoˇcte odhad výpoˇcetní záteže (#FLOPs) cˇ ásteˇcné faktorizace pˇríslušné podmatice.



QB heuristika

Rozšiˇruje a modifikuje vylepšovací heuristiku. ˇ Pro každý podgraf spoˇcte odhad výpoˇcetní záteže (#FLOPs) cˇ ásteˇcné faktorizace pˇríslušné podmatice. ˇ a zmenšuje hranový Vyvažuje odhady výpoˇcetních záteží rˇez.



QB heuristika (obrázek) Tok dat Zavislost

Zlepsovaci heuristika Podgraf zhrubleho

Dualni graf

Projekce na GD Podgraf

Sit KP

Ohodnoceny uzlovy graf

GD

GD

Projekce na GN

Precislovani

Odhad slozitosti

Odhadnuta slozitost


Obsah 1


2


3

Výsledky

4

ˇ Záver


Testování

Testováno na výpoˇctech stárnutí reaktorové nádoby.


Testování

Testováno na výpoˇctech stárnutí reaktorové nádoby. Pouze pro 130 cˇ asových kroku. ˚ (V praxi je jich potˇreba 13000).


Testování

Testováno na výpoˇctech stárnutí reaktorové nádoby. Pouze pro 130 cˇ asových kroku. ˚ (V praxi je jich potˇreba 13000). Dekompozice na 4, 6, 8 a 10 domén, nejprve METISem, pak QB.


Testování

Testováno na výpoˇctech stárnutí reaktorové nádoby. Pouze pro 130 cˇ asových kroku. ˚ (V praxi je jich potˇreba 13000). Dekompozice na 4, 6, 8 a 10 domén, nejprve METISem, pak QB. Testováno na Linuxovém clusteru. Každý stroj: Pentium 4, ˇ 3,2 GHz, 3GB pameti.


Testování

Testováno na výpoˇctech stárnutí reaktorové nádoby. Pouze pro 130 cˇ asových kroku. ˚ (V praxi je jich potˇreba 13000). Dekompozice na 4, 6, 8 a 10 domén, nejprve METISem, pak QB. Testováno na Linuxovém clusteru. Každý stroj: Pentium 4, ˇ 3,2 GHz, 3GB pameti. ˇ c SIFEL http://cml.fsv.cvut.cz/~sifel/, Rešiˇ zkompilován gcc s optimalizací -O3.


Popis testovacích problému˚

ˇ u. Diskretizace reaktorové nádoby pomocí cˇ tyˇrsten ˚ 2 Síteˇ KP ruzné ˚ jemnosti: creep15 a creep10.

#elementu˚ #uzlu˚ #SV

creep15 47090 13529 3

creep10 152464 38235 3


Vyvazeni vypoctu METIS QB

4 4

6 6

8 8

100

150

vyvazeni 200

250 [%]

Vyvážení výpoˇctu

creep15

creep10

10 10


Výsledné zrychlení ˇ TM (TQB ) doba 130 cˇ asových kroku˚ [sec] po delení METISem (QB). ˇ ∆ úspora cˇ asu výpoˇctu po delení QB [%]. ˇ tQB doba behu QB [sec]. #domén 4 6 8 10

TM 2432 2543 847 844

creep15 TQB ∆ 2294 6 1097 57 711 16 567 33

tQB 10 6 7 7

TM 21256 11607 7710 5550

creep10 TQB ∆ 20743 2 10264 12 6255 19 4084 26

tQB 56 49 49 46


Obsah 1


2


3

Výsledky

4

ˇ Záver


ˇ Záver QB heuristika: a) vyvažuje paralelní výpoˇcet,


ˇ Záver QB heuristika: a) vyvažuje paralelní výpoˇcet, b) zkracuje dobu ˇrešení,


ˇ Záver QB heuristika: a) vyvažuje paralelní výpoˇcet, b) zkracuje dobu ˇrešení, c) prodlužuje dobu dekompozice,



⇒ je vhodná pro dekompozici cˇ asoveˇ závislých mechanických problému. ˚



⇒ je vhodná pro dekompozici cˇ asoveˇ závislých mechanických problému. ˚ Další výzkum testování na dalších úlohách.



⇒ je vhodná pro dekompozici cˇ asoveˇ závislých mechanických problému. ˚ Další výzkum testování na dalších úlohách. ˇ testování na vetším poˇctu procesoru. ˚

Static Load Balancing Applied to Time Dependent Mechanical Problems

Recommend Documents