Grid felhasználás: alkalmazott matematika

Grid felhasználás: alkalmazott matematika Konvex testek egyensúlyi osztályozása a Saleve keretrendszerrel

Kápolnai Richárd1 Domokos Gábor2 Szabó Tímea2 1 BME

Irányítástechnika és Informatika Tanszék [email protected] 2 BME Szilárdságtani és Tartószerkezeti Tanszék

e-Science Cafè, 2011. november 14.

Verzió: $Id: scicafe.tex 273 2011-11-14 10:45:12Z richard $

Egyensúlyi pontok Konvex, homogén test felszínén távolság a tkp-tól: R(θ, ϕ) Egyensúlyi pontok az R szélsőértékei (minimum, maximum és nyereg) S R

U R

H

π π/2 0

0 π/4

θ

ϕ

-π/2

π/2 3π/4 π -π

Elforgatott ellipszoid magasságfüggvénye Kápolnai Richárd (BME)

Grid felhasználás: alkalmazott matematika

e-Science Cafè, 2011.11.14.

2 / 17

Ellipszoid magasságfüggvénye és gradiensmezője 3

π

2.8 2.6 π/2 2.4

ϕ

2.2 0

2 1.8 1.6

-π/2 1.4 1.2 -π

1 0

Kápolnai Richárd (BME)

π/4

π/2

3π/4

Grid felhasználás: θalkalmazott matematika

π e-Science Cafè, 2011.11.14.

3 / 17

Egyensúlyi osztályok (S, U): a test egyensúlyi osztálya, pl. a kocka: (6,8) S

(1,1)

U

1

2

3

4

5

6

7

8

…

1 2 3 4

(1,2)

5 6 7 8 …

Domokos Gábor – Várkonyi Péter, 2006. Kápolnai Richárd (BME)



4 / 17

Minden osztályban van valamilyen test S

U

1

2

3

4

5

6

7

8

…

1 2 3 4 5 6 7 8 Kápolnai Richárd (BME)



5 / 17

Az egyensúlyi gráf Finomabb felosztás: izolált pályák (U −→ H és H −→ S) egy négyszögelt gráfot határoznak meg 4

3 2.8

3

2.6 2 2.4 1

2.2

0

2 1.8

-1

1.6 -2 1.4 -3

-4 -0.5

1.2

0

0.5

1

1.5

2

2.5

3

3.5

1

Az R függvény Morse–Smalekomplexének gráfja Kápolnai Richárd (BME)



6 / 17

Futási eredmények – alosztályok felsorolása S + U ≤ 10-ig Hányféle topológia lehetséges egy (S, U) egyensúlyi osztályon belül? n = S + U a csúcsok száma: 3

4

5

6

7

8

9

10

U\S 1 2 3 4 5 6 7 8 9

1 1 1 1 2 3 6 12 27 65

2 1 2 5 13 35 104 315 1021

3 1 5 20 83 340 1401 5809


4 2 13 83 504 2843 15578

5 3 35 340 2843 21420

6 6 104 1401 15578


7 12 315 5809

8 27 1021

9 65


7 / 17

Felsorolás hatékonysága

Jelölje S az összes egyensúlyi gráf halmazát n 3 4 5 6 7 8 9 10

feldolgozási idő 0 0 0 0 6 sec 10 perc 20 óra 81 nap


vizsgált lehetőségek 2 14 291 14 468 1,1 · 106 1,1 · 108 1,2 · 1010 1,4 · 1012

|S| 2 4 14 52 248 1 416 9 172 66 366



8 / 17

Gráfok párhuzamos generálása ismétlés nélkül G0

G1

G4

G2

G5

G6

G3

G7

G8

G9

Csak a fekete élek mentén generálunk (legjobb redukció)




9 / 17


G1

G4

G2

G5

G6

G3

G7

G8

G9

Csak a fekete élek mentén generálunk (legjobb redukció) Itt 6 független job indítható Kápolnai Richárd (BME)



9 / 17


G1

G4

G2

G5

G6

G3

G7

G8

G9

Csak a fekete élek mentén generálunk (legjobb redukció) Itt 6 független job indítható Függetlenül generálják a megoldásokat (Brinkmann – McKay, 2007) Kápolnai Richárd (BME)



9 / 17

Egyenletes feldarabolás a Saleve alkalmazáshoz G0

G1

G4

G2

G5

G6

G

G3

G7

G8

G9

G

Nem tudjuk előre az egyes darabok számításigényét Kápolnai Richárd (BME)



10 / 17


G1

G4

G2

G5

G6

G

G3

G7

G8

G9

G

Nem tudjuk előre az egyes darabok számításigényét Iteratív darabolás: bizonyos részeket manuálisan továbbdarabolunk Kápolnai Richárd (BME)



10 / 17


G1

G4

G2

G5

G6

G

G3

G7

G8

G9

G

Nem tudjuk előre az egyes darabok számításigényét Iteratív darabolás: bizonyos részeket manuálisan továbbdarabolunk Kápolnai Richárd (BME)



10 / 17

Gridalkalmazás fejlesztése a Saleve keretrendszerben Példa: függvény integrálása [0, 1]-en: kis módosítás a forráskódon

Eredeti forráskód

Saleve kliens: majdnem ugyanaz,

int main(int ac, char *av[]) { double result = integrate("0.0", "1.0"); printf("%lf\n", result); }

int saleve_main(int argc, char *argv[]) { double subresult = integrate(argv[1], argv[2]); printf("%lf", subresult); }

Az alkalmazás lényegi részén (integrate) nem kell változtatni

kiegészítve a paramétertér felosztásával, összegzésével: void saleve_span() { saleve_addInstance("0.0 saleve_addInstance("0.1 ...

0.1"); 0.2");

Automatikus: (többdimenziós) paramétertartomány feldarabolása, grides job futtatása minden darabhoz C/C++ támogatás, „becsomagolható” bármilyen konzolos alkalmazás (Java, Matlab, Python, Fortran, . . . ) Kápolnai Richárd (BME)



11 / 17

Saleve: transzparens működés A kliens elküldi önmagát és a feladatot: 1

2

A szerver jobokat küld a gridbe

tux@linux#

A kliens összegzi a részeredményeket 4

A visszatérő részeredményeket a szerver továbbítja a kliensnek 3

P

5 7

9

tux@linux#

4


=

tux@linux#

25 Grid felhasználás: alkalmazott matematika

7

5 9 4


12 / 17

Saleve gridalkalmazás hatékonysága Feldolgozási idők:

Sorbanállás + feldolgozás:

n = 10 pontszámra 1076 job, összesen 1923 cpu óra (80 nap) A kezdeti paramétertartomány az n = 8 méretű T -gráfok 1. iteráció: 1000 job, 2. iteráció: 4 job továbbdarabolva Ideális párhuzamosításban minden job kb. 2 órás lenne Volt 11 órás job is, így kb. 6-szoros futási idő (vö. 80 nappal) Hosszú várakozási sorok automatikus kezelése Kápolnai Richárd (BME)



13 / 17

Vannak-e a Gömböc mellett más ősök? n < 8-ig minden gráf előállítható a Gömböcből, ahol n = S + U. A programmal generált gráfokra ellenőrizhető: n 4 5 6 7 8 9 10

mindkettő 2 6 32 172


csak C1 1 2 4 10

csak C2 1 6 16 66

egyik sem -



14 / 17


mindkettő 2 6 32 172

csak C1 1 2 4 10

csak C2 1 6 16 66

egyik sem -

Léteznek-e egyéb ősök? Létezik-e hozzájuk fizikai test? Hogyan képzeljük el őket?




14 / 17


mindkettő 2 6 32 172 1071 7370 55766

csak C1 1 2 4 10 33 114 474

csak C2 1 6 16 66 311 1688 10125

egyik sem 1 1

Léteznek-e egyéb ősök? Létezik-e hozzájuk fizikai test? Hogyan képzeljük el őket? n ≥ 8 esetén vannak más ősök!




14 / 17

Minimálpoliéderek

Ős: semmiből sem származtatható




15 / 17

Minimálpoliéderek

Ős: semmiből sem származtatható Példa: szabályos poliéderek, gúla, . . .




15 / 17

Minimálpoliéderek

Ős: semmiből sem származtatható Példa: szabályos poliéderek, gúla, . . . Meghatároztunk egy olyan test-kategóriát, mely nem származtatható a Gömböcből.




15 / 17

Ős megállapítása Egy gráfot általában többféleképpen lehet generálni egy ősből, az ős egyértelműen megállapítható Kb. 100 bescannelt kavicsnak megállapítottuk az ősét

Scannelt kavics pályái, ábra: GTT és SZT (Sípos András–Szabó Tímea)




16 / 17

Köszönöm szépen a figyelmet! Saleve keretrendszer http://cern.ch/saleve/ Hungrid Virtuális Szervezet http://grid.kfki.hu/hungrid/ G. Brinkmann – B. D. McKay, Fast generation of planar graphs, MATCH Comm., (2007) 58 G. Domokos – P. Várkonyi, Static equilibria of rigid bodies: dice, pebbles and the Poincaré–Hopf theorem, J Nonlinear Sci, (2006) 16 P. Dóbé – R. Kápolnai – A. Sipos – I. Szeberényi, Applying the improved Saleve framework for modeling abrasion of pebbles, in LSSC, vol. 5910 of LNCS, 2010 R. Kápolnai – G. Domokos, Inductive generation of convex bodies, in The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 170–178, 2011

Grid felhasználás: alkalmazott matematika

Recommend Documents