Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon
•
1 like•373 views
Tézisjavaslat védés prezentáció Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon
Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon
- 1. Gazdasági alkalmazások párhuzamos architektúrákon Budapes( Corvinus Egyetem, Gazdaságinforma(ka Doktori Iskola 2014. július 1. PhD disszertáció-‐tervezet védés Mohácsi László Témavezetők: Dr. Abaffy József és Dr. Kovács Erzsébet
- 2. A dolgozat részei I. Gazdasági számítások párhuzamos architektúrákon II. Lineáris egyenletrendszerek megoldása ABS-‐ módszerrel III. Egy O*(n4) algoritmus párhuzamos architektúrán konvex testek térfogatának kiszámítására IV. A nyugdíj-‐előreszámítás támogatása mikroszimulációs eljárással Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 1/25
- 3. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 2/25 I. Gazdasági számítások párhuzamos architektúrákon ‒ Architektúrák bemutatása. ‒ A párhuzamosításra nincs általános módszer. ‒ Gyakran az algoritmus működésén is változtatni kell. ‒ A helyesség nem mindig ellenőrizhető.
- 4. NVIDIA GeForce GTX570 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 3/25 Grafikus processzorok - CUDA
- 5. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 4/25 Grafikus processzorok - CUDA
- 6. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 4/25 Grafikus processzorok - CUDA
- 7. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 4/25 Grafikus processzorok - CUDA
- 8. A dolgozat részei I. Gazdasági számítások párhuzamos architektúrákon II. Lineáris egyenletrendszerek megoldása ABS-‐ módszerrel III. Egy O*(n4) algoritmus párhuzamos architektúrán konvex testek térfogatának kiszámítására IV. A nyugdíj-‐előreszámítás támogatása mikroszimulációs eljárással Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 5/25
- 9. II. Lineáris egyenletrendszerek megoldása ABS-módszerrel ‒ Első verzióját Dr. Abaffy József publikálta. ‒ A kutatáshoz csatlakoztak Charles G. Broyden és Emilio Spedicato. ‒ A részeredmények tárolásához mindössze egy mátrixot használ. ‒ Stabilabb, mint a módosítoa Gram-‐Smidth eljárás. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 6/25
- 10. ABS módszer CUDA architektúrán Lineáris egyenletrendszerek megoldása ABS- módszerrel Ismeretlenek száma Futásidő Hiba 2 6 ms ≈0 4 8 ms 7.81597·∙10 -‐14 8 10 ms 2.13163·∙10 -‐14 16 16 ms 1.00364·∙10 -‐13 32 24 ms 1.82077·∙10 -‐13 64 46 ms 7.43805·∙10 -‐12 128 100 ms 6.81943·∙10 -‐12 256 245 ms 7.41984·∙10 -‐12 512 886 ms 4.81473·∙10 -‐11 1024 3.2 sec 1.89602·∙10 -‐11 2048 14.7 sec 8.06466·∙10 -‐12 4096 105.9 sec 1.29308·∙10 -‐13 8192 23 min 2.35101·∙10 -‐12 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 7/25
- 11. Az ABS algoritmussal kapcsolatban elért eredmények ‒ Lehetővé vált a hibaterjedés empirikus vizsgálata. ‒ A módosítoa Huang algoritmus stabil -‐ Gá( Ajla dolgozatában állítoa stabilitás alátámasztása. ‒ Alacsony memóriaigénye miaa különösen alkalmas GPU-‐n történő fuaatásra. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 8/25
- 12. A dolgozat részei I. Gazdasági számítások párhuzamos architektúrákon II. Lineáris egyenletrendszerek megoldása ABS-‐ módszerrel III. Egy O*(n4) algoritmus párhuzamos architektúrán konvex testek térfogatának kiszámítására IV. A nyugdíj-‐előreszámítás támogatása mikroszimulációs eljárással Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 9/25
- 13. Konvex testek térfogatának kiszámítása ‒ A térfogat kiszámolására nem létezik polinomiális idejű megoldás. ‒ Sta(sz(kai módszereken alapuló térfogatbecslő eljárások polinomiális időben adnak becslést. ‒ Nagy számításigény. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 10/25
- 14. Térfogatszámító algoritmusok számításigénye Dyer-‐Frieze-‐Kannan 1989 𝑂↑∗ ( 𝑛↑27 ) Lovász-‐Simonovits 1990 𝑂↑∗ ( 𝑛↑16 ) Applegate-‐Kannan 1990 𝑂↑∗ ( 𝑛↑10 ) Lovász 1991 𝑂↑∗ ( 𝑛↑10 ) Dyer-‐Frieze 1991 𝑂↑∗ ( 𝑛↑8 ) Lovász-‐Simonovits 1992,93 𝑂↑∗ ( 𝑛↑7 ) Kannan-‐Lovász-‐Simonovits 1997 𝑂↑∗ ( 𝑛↑5 ) Lovász 1999 Kannan-‐Lovász 1999 Lovász-‐Vempala 2002 A.Kalai-‐Lovász-‐Vempala 2003 𝑂↑∗ ( 𝑛↑4 ) Deák 2012 Program *Forrás: hap://www.cs.elte.hu/~lovasz/presenta(ons.html Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 11/25
- 15. „Determinisztikus” térfogatok kiszámítása 𝐾↓0 = 𝐵↓0 𝐾↓1 𝐾↓2 𝐾↓3 𝐾↓𝑚 = 𝐾 𝐵↓0 𝐵↓1 𝐵↓2 𝐵↓3 𝐵↓𝑚 𝑣𝑜𝑙(𝐾)= 𝑣𝑜𝑙( 𝐾↓0 ) 𝑣 𝑜𝑙( 𝐾↓1 )/𝑣𝑜𝑙( 𝐾↓0 ) ⋯ 𝑣 𝑜𝑙( 𝐾↓𝑚 ⋯ Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 14/
- 16. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 17. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 18. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/
- 19. 𝑓(𝑥)= 𝑒↑ 𝑎↓1 𝑥↓0 𝑎↓1 =3.514719 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 20. 𝑓(𝑥)= 𝑒↑ 𝑎↓2 𝑥↓0 𝑎↓2 =1.029437 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 21. 𝑓(𝑥)= 𝑒↑ 𝑎↓3 𝑥↓0 𝑎↓3 =0.301515 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 22. 𝑓(𝑥)= 𝑒↑ 𝑎↓4 𝑥↓0 𝑎↓4 =0.088312 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 23. 𝑓(𝑥)= 𝑒↑ 𝑎↓5 𝑥↓0 𝑎↓5 =0.025866 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 24. 𝑓(𝑥)= 𝑒↑ 𝑎↓6 𝑥↓0 𝑎↓6 =0.007576 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 25. 𝑓(𝑥)= 𝑒↑ 𝑎↓7 𝑥↓0 𝑎↓7 =0.002219 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 26. 𝑓(𝑥)= 𝑒↑ 𝑎↓8 𝑥↓0 𝑎↓8 =0.000650 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 27. 𝑓(𝑥)= 𝑒↑ 𝑎↓9 𝑥↓0 𝑎↓9 =0.000190 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 28. 𝑓(𝑥)= 𝑒↑ 𝑎↓10 𝑥↓0 𝑎↓10 =0.000056 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 29. 𝑓(𝑥)= 𝑒↑ 𝑎↓11 𝑥↓0 𝑎↓11 =0.000016 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 30. 𝑓(𝑥)= 𝑒↑ 𝑎↓12 𝑥↓0 𝑎↓12 =0.000005 Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 12/25
- 31. Futási eredmények vizualizációja „Falnak ütköző” pontok elhelyezkedése térben a ceruza felületén a 2. fázis végén Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 13/25
- 32. A térfogatszámítással kapcsolatban elért eredmények ‒ Vizsgálhatóvá vált a Lovász-‐Vempala algoritmus viselkedése. ‒ Több pont-‐szál használata hozzájárul a generált pontok függetlenségének biztosításához. ‒ Pontok terjedésének vizualizációja. ‒ A bevezetea varianciacsökkentő eljárások nem váltoaák be a reményeket. ‒ A dupla-‐pontosságú számábrázolás hibájából fakadóan 20 dimenziónál korlát. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 14/25
- 33. A dolgozat részei I. Gazdasági számítások párhuzamos architektúrákon II. Lineáris egyenletrendszerek megoldása ABS-‐ módszerrel III. Egy O*(n4) algoritmus párhuzamos architektúrán konvex testek térfogatának kiszámítására IV. A nyugdíj-‐előreszámítás támogatása mikroszimulációs eljárással Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 15/25
- 34. IV. A nyugdíj-előreszámítás támogatása mikroszimulációs eljárással ‒ A cél egy mikroszimulációs keretrendszer létrehozása. ‒ Az egyedek sorsát egyesével köve(. ‒ Csak súlyozatlan kiinduló állomány használható. ‒ Évenként és egyedenként végrehajtoa szimulációs lepések. ‒ Nagy számításigény. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 16/25
- 35. 10 millió személy adata 2004-‐ ben Kiinduló állomány Szimulációs lépés szem. évek Szimuláció n millió személy adata 2054-‐ben Továbbvezetea állomány Élő Nyugdíjas gyermek Összesítés Lélekszám, nyugdíjasok, gyermekek száma 2054-‐ ben. Eredmény A mikroszimulációs módszertan Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 17/25
- 36. 0% 10% 20% 30% 40% 50% 60% 70% 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 1950 1960 1970 1980 1990 2000 2009 Halandósági táblák Férfiak halálozási valószínűsége korévenként. „A” változat Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 20/
- 37. 1950 1956 1962 1968 1974 1980 1986 1992 1998 2004 0% 10% 20% 30% 40% 50% 60% 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 0%-‐10% 10%-‐20% 20%-‐30% 30%-‐40% 40%-‐50% 50%-‐60% Férfiak halálozási valószínűsége korévenként. Halandósági táblák Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 18/25
- 38. Halandósági táblák Életkilátások alakulása korévenként 1950-‐hez képest. 1950 1956 1962 1968 1974 1980 1986 1992 1998 2004 -‐15,0% -‐10,0% -‐5,0% 0,0% 5,0% 10,0% 15,0% 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 -‐15,0%-‐-‐10,0% -‐10,0%-‐-‐5,0% -‐5,0%-‐0,0% 0,0%-‐5,0% 5,0%-‐10,0% 10,0%-‐15,0% Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 20/
- 39. Szimulációs keretrendszer CSV fájl Kiinduló adatállomány Metaadatok Mezőleírások Nómenklatúrák Paramétertáblázato k Adatszerkezetek Táblázatok Szimulációs program C# forráskódja Mikromodulok Fuaató modul CSV fájl Továbbvezetea adatállomány Lekérdező modul Eredménylisták A keretrendszer folyamatábrája Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 19/25
- 40. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 20/25
- 41. A nyugdíj-előreszámítással kapcsolatban megfogalmazott eredményeim ‒ Használható keretrendszer a modellező közgazdászok számára. ‒ 50 éves előrejelzés 2 percre leszorítható. ‒ A keretrendszer a nyugdíjrendszerekhez kapcsolódó más tényezők számításaira is alkalmazható. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 21/25
- 42. Fejlesztési tervek és irányok ‒ Próbatestnek szimplex tetszőleges dimenzióban. ‒ A 20 dimenziós korlát átlépéséhez a PLVDM algoritmust áyrása klaszterre. ‒ A szimulációs keretrendszer fuaatása klaszteren. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 22/25
- 43. Publikációk Csetényi Arthur – Mohácsi László – Váraljai László (2007): Szo{verfejlesztés. HEFOP, Debrecen. Mohácsi László – Rétallér Orsolya (2013): A mechanical approach of mul(variate density func(on approxima(on. Proceedings of the Interna(onal Conference on Modeling and Applied Simula(on, 179-‐184. Forgács Ajla – Mohácsi László (2014): Gazdasági számítások párhuzamos architektúrákon. GIKOF Journal, 6-‐14. Mohácsi László – Deák István (2014): A parallel implementa(on of an O*(n4) volume algorithm. Central European Journal of Opera(ons Research, elfogadva 2014. június 23-‐án Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 23/25
- 44. Konferenciák, előadások Egy térfogat kiszámítási algoritmus párhuzamos architektúrán. XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-‐13. Gazdasági számítások párhuzamos számítógépeken. OGOK’2013 Országos Gazdaságinforma(kai Konferencia, Győr, 2013. november 8-‐9. A halandóság becslése mikroszimulációval. Tanszéki szeminárium, Operációkutatás Tanszék, 2014. március 4. Mohácsi László: Gazdasági alkalmazások párhuzamos architektúrákon 24/25
- 45. "Programming is the art of telling another human what one wants the computer to do." hap://web.uni-‐corvinus.hu/~lmohacs/thesis/ Donald Knuth
- 46. Irodalom • Abaffy, J. (1979): A lineáris egyenletrendszerek általános megoldásának egy direkt módszerosztálya. Alkalmazoa Matema(kai Lapok, 5, 223-‐240 • Gá(, A. (2013): Automa(c roundoff error analysis of numerical algorithms. Ph.D thesis, Applied Informa(cs Doctoral School, Óbuda University • Lovász, L./Deák, I. (2012): Computa(onal results of an O(n4) volume algorithm. European Journal of Opera(onal Research, 216, 152-‐161 • Csicsman, J./Fényes, C. (2003): A Mikroszimulációs Szolgáltató Rendszer fejlesztése. Alma Mater sorozat -‐ Üzlet, folyamat, monitoring • Hablicsek, L. (2007): Társadalmi-‐demográfiai előreszámítások a nyugdíjrendszer átalakításának modellezéséhez, Jelentés a Nyugdíj és Időskor Kerekasztal számára • Kovács, E. (2010): A nyugdíjreform demográfiai korlátai. Hitelintéze( Szemle, 2,128-‐149
- 48. ABS módszer CUDA architektúrán Lineáris egyenletrendszerek megoldása ABS- módszerrel Ismeretlenek száma Futásidő Hiba 2 6 ms ≈0 4 8 ms 7.81597·∙10 -‐14 8 10 ms 2.13163·∙10 -‐14 16 16 ms 1.00364·∙10 -‐13 32 24 ms 1.82077·∙10 -‐13 64 46 ms 7.43805·∙10 -‐12 128 100 ms 6.81943·∙10 -‐12 256 245 ms 7.41984·∙10 -‐12 512 886 ms 4.81473·∙10 -‐11 1024 3.2 sec 1.89602·∙10 -‐11 2048 14.7 sec 8.06466·∙10 -‐12 4096 105.9 sec 1.29308·∙10 -‐13 8192 23 min 2.35101·∙10 -‐12