Studentská grantová soutěž - předchozí roky

Paralelní řešení výpočetně náročných úloh

SP2013/191

Kozubek Tomáš prof. Ing., Ph.D.

01. 01. 2013 - 31. 12. 2013

1. Úvod Předkládaný projekt navazuje na výsledky řešení projektu SGS s názvem Vývoj, implementace a testování metod pro paralelní řešení výpočetně náročných úloh z roku 2012, jehož cílem bylo nasazení a masivní testování vyvinutých paralelních algoritmů na řešení rozsáhlých inženýrských úloh z oblasti environmentálních věd (povodně, šíření znečištění), mechaniky, fyziky, chemie, diskrétní matematiky a informatiky. Nový projekt bude pokračovat ve vývoji efektivních algoritmů ve zmíněných oblastech, jejich masivně paralelní implementaci a testování na TIER-1 a TIER-0 systémech. Dojde k posílení zapojení členů týmu do řešení mezinárodních projektů PRACE-2IP a PRACE-3IP, k dalšímu rozšíření mezinárodní spolupráce a k navýšení kvality a počtu výstupů projektu. Veškeré činnosti budou synchronizovány s podobnými činnostmi týmů CE IT4Innovations. 2. Cíle projektu • Navázání na výsledky předchozího projektu SGS a pokračování v dalším zefektivňování a vývoji matematických metod pro řešení problémů z oblasti environmentálních věd, mechaniky, fyziky, chemie, diskrétní matematiky a informatiky, které jsou v současné době díky svému rozsahu, složitosti, nehladkosti nebo nelinearitě na hranici řešitelnosti. • Paralelní implementace vyvinutých algoritmů do knihoven FLLOP, MatSol, MULTIDYN, knihovny FastBEM řešičů a některých nových knihoven vzniklých při řešení dílčích proprietálních problémů. • Masivní testování na TIER-1 a TIER-0 superpočítačových systémech infrastruktury PRACE. • Vytvoření rozhraní k vybraným open sourceovým kódům jako jsou ELMER vyvíjený v CSC Helsinki, CODE_ASTER vyvíjený v EDF France a další za účelem jak akademického tak i průmyslového využití námi vyvíjených algoritmů. • Aplikování vyvinutých metod na vybrané úlohy z environmentálních věd, mechaniky, fyziky, chemie, diskrétní matematiky a informatiky. • Posílení zapojení se do řešení mezinárodního projektů PRACE-2IP (2011-2013) a PRACE-3IP (2012-2014) a nově zapojení se do projektů FP7 EXA2CT a HARPA. 3. Historie týmu Předkladatel je od roku 2007 docentem na Katedře aplikované matematiky FEI a od roku 2011 vedoucím výzkumného programu Knihovny pro paralelní výpočty CE IT4Innovations. Taktéž je autorem více než 20 impaktovaných publikací, řešitelem projektu OPVK SPOMECH (2011-2014) a spoluřešitelem celé řady domácích projektů GAČR, AVČR, MŠMT, MS kraje a mezinárodních projektů PRACE 1IP (2010-2012), PRACE 2IP (2011-2013), PRACE 3IP (2012-2014) a ESF OPTPDE. Kvalita řešitelského týmu: • Řešitelský tým je složen ze 42 členů, z toho 14 zaměstnanců a 27 studentů katedry aplikované matematiky a 1 student katedry informatiky. • Počet bodů (rozpočítaných vzhledem ke spoluautorům) řešitelského týmu v RIV 2012: 1300 bodů • Podíl pracovníků s podstatným výkonem v RIV 2012 na řešení projektu: 9 členů (21%) týmu má více než 40 bodů v RIV 2012 • Poměr cena/výkon projektu, kde cena je tvořena náklady projektu, výkon je součet bodů klíčových osob řešitelského týmu v RIV 2012: 968Kč/bod • Výkon ve VaV řešitelského týmu v roce 2012: 240 bodů (pouze impaktované publikace na WOS) Členové týmu se podíleli v posledních 3 letech na více než 25 impaktovaných publikacích a 8 projektech GAČR, 2 grantech AVČR, projektu MS kraje Floreon+, Výzkumném záměru a 4 mezinárodních projektech PRACE 1IP, PRACE 2IP, PRACE 3IP a ESF OPTPDE. Vybrané publikace (publikované a akceptované) členů týmu s impakt faktorem za rok 2012 z tematiky projektu: 1. Balibrea, F.; Dvorníková, G.; Lampart, M.; Oprocha, P. On negative limit sets for one-dimensional dynamics, NONLINEAR ANALYSIS: THEORY, METHODS & APPLICATIONS 75 (6), pp. 3262–3267, 2012. 2. Lampart, M. Stability of the Cournot equilibrium for a Cournot oligopoly model with n competitors, CHAOS, SOLITONS & FRACTALS 45 (9-10), pp. 1081-1085, 2012. 3. R. Kucera, T. Kozubek, A. Markopoulos, On large-scale generalized inverses in solving two-by-two block linear systems, Linear Algebra and its Applications, 2012, accepted. 4. Z. Dostál, T. Kozubek, T. Brzobohatý, A. Markopoulos, O. Vlach, Scalable TFETI with optional preconditioning by conjugate projector for transient frictionless contact problems of elasticity, Comput. Methods Appl. Mech. Engrg., 2012. 5. DOSTAL, Z., KOZUBEK, T.: An optimal algorithm and superrelaxation for minimization of a quadratic function subject to separable convex constraints with applications. Mathematical Programming, 2012. 6. Kucera, R.; Kozubek, T.; Markopoulos, A.; Machalova, J. On the Moore-Penrose inverse in solving saddle-point systems with singular diagonal blocks, NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 19(4), pp. 677-699, 2012. 7. Dostal, Z.; Kozubek, T.; Markopoulos, A.; Brzobohaty, T.; Vondrak, V.; Horyl, P. A theoretically supported scalable TFETI algorithm for the solution of multibody 3D contact problems with friction, COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING, Volume: 205 Special Issue: SI, Pages: 110-120, DOI: 10.1016/j.cma.2011.02.015, 2012, IF 2.651. 8. Kozubek, T.; Vondrák, V.; Menšík, M.; Horák, D.; Dostál, Z.; Hapla, V., Kabelíková, P., Čermák, M. Total FETI domain decomposition method and its massively parallel implementation, (accepted in ADVANCES IN ENGINEERING SOFTWARE) 9. Fabián, T.; Gaura, J.; Kotas, P. Iris localisation and extraction algorithm from an eye image, INTERNATIONAL JOURNAL OF SIGNAL AND IMAGING SYSTEMS ENGINEERING 5(2), pp. 69-77, 2012. 10. D. Lukáš, K. Postava, O. Životský, A Shape Optimization Method for Nonlinear Axisymmetric Magnetostatics Using a Coupling of Finite and Boundary Elements, Mathematics and Computers in Simulation (IF 0.738), vol. 82, nr. 10, pp. 1721-1731, 2012. 11. K. Postava, J. Hamrle, J. Hamrlová, O. Životský, J. Pištora, D. Lukáš, Depth and material sensitivity in magneto-optic nanostructures, International Journal of Nanotechnology (IF 1.013), vol. 9, nr. 8-9, pp. 784-808, 2012. 12. Kovář, P.; Kubesa, M.; Meszka, M.: Factorizations of complete graphs into brooms. In Discrete Mathematics, 312, 1084-1093 (2012) 13. Ahmad, A.; Ali, K.; Baca, M.; Kovar, P; Semanicova-Fenovcikova, A.: Vertex-antimagic Labelings of Regular Graphs, ACTA MATHEMATICA SINICA-ENGLISH SERIES, 28, 865-1874 2012. 14. Cichacz, S.; Froncek, D.; Kovar, P.: Decomposition of complete bipartite graphs into generalized prisms (accepted in EUROPEAN JOURNAL OF COMBINATORICS) 15. Bača, M; Kovář, P.; Semaničová–Feňovčíková, A.; Zlámalová, J.: Vertex-Antimagic Labelings of Wheels and Related Graphs, (accepted in Discrete Mathematics) 4. Popis řešení a výstupy projektu Tým 1. Řešení výpočetně náročných úloh v environmentálních vědách (Řešitelský tým: Vít Vondrák, Petr Kotas, Pavla Kabelíková, Tomáš Kocyan, Martin Menšík, Aleš Ronovský, Martin Hasal, Artur Iwan, Václav Ryška) Řešení matematických modelů v environmentálních vědách patří mezi výpočetně nejnáročnější matematické úlohy. Náročnost je dána jak složitostí matematických modelů popisujících velmi složité jevy, tak rozsáhlostí numerických modelů v důsledku velmi podrobné jak prostorové tak i časové diskretizace. Do výpočetní náročnosti dále nemalou měrou přispívají i neurčitosti a nejistoty ve vstupních datech a parametrech matematických modelů. Řešení těchto úloh klasickými postupy s využitím standardních výpočetních prostředků je však časově natolik náročné, že jejich výstupy jsou mnohdy nepoužitelné vzhledem k jejich časové neaktuálnosti. Typicky se nutnost aktuálnosti simulací vyskytuje v oblasti hydrologie při předpovědi povodní nebo v případě úniku škodlivin při ekologických haváriích. V oblasti hydrologie se proto výzkumný tým zaměří na vývoj a implementaci efektivních algoritmů pro výpočet záplavových jezer ve 2D a nové efektivní metody pro řešení proudění v horninách. Standardní algoritmy totiž pro řešení této úlohy vyžadují řádově hodiny, což činí výsledky těchto simulací pro operativní předpověď nepoužitelnými. Nutností je tedy využití nových efektivních algoritmů vykazujících paralelní škálovatelnost a jejich následná implementace na výpočetní klastry. Výsledkem by mělo být zkrácení výpočetních časů řádově z hodin na desítky minut či minuty a otestování implementovaných algoritmů na reálných situacích. Další významnou aplikací s potřebou včasných výstupů simulací je modelování šíření škodlivin v ovzduší. Tyto modely dynamiky plynů vyžadují velmi rozsáhlou prostorovou diskretizaci, což vede k výpočetně velmi náročným úlohám. Výzkumný tým se proto bude zabývat vývojem a nasazením paralelních algoritmů pro řešení těchto úloh založených na doménové dekompozici. Cílem je dosažení významné míry paralelní škálovatelnosti implementovaných algoritmů pro stovky až tisíce procesorových jader. Vstupní data a parametry modelů v přírodních vědách jsou typicky zatíženy neurčitostmi a nejistotami. Mnohdy se parametry těchto modelů v čase mění nebo nejsou známy vůbec, což má za následek značné nepřesnosti ve výstupech modelů. Vhodnou cestou zpřesňování těchto dat je inverzní modelování. Na základě známých výsledků je možné identifikovat jednotlivé parametry modelů nebo určovat parametry vstupních dat. Tyto inverzní úlohy jsou však výpočetně řádově náročnější než přímé úlohy, neboť vyžadují opakované řešení původního modelu. Obvykle tyto úlohy vykazují dobrou paralelní škálovatelnost, a proto se jeví jako řešení jejich paralelní implementace. Výzkumný tým se proto zaměří na paralelní implementaci metod inverzního modelování v oblasti srážkoodtokových modelů v hydrologii. Výstupem bude identifikace parametrů hydrologických schematizací a lokalizace srážek. Implementované metody budou testovány na reálných srážkoodtokových situacích. Předpokládá se nově zapojení členů týmu do projektu FP7 HARPA. Tým 2. Řešení výpočetně náročných úloh v mechanice (Řešitelský tým: Zdeněk Dostál, Petr Vodstrčil, Marek Lampart, Oldřich Vlach, Petr Beremlijski, David Horák, Petr Kotas, Lukáš Pospíšil, Kristina Rádková, Václav Hapla, Matyáš Theuer, Ondřej Zjevík, Rajko Ćosić, Petr Ehler, Pavla Jirůtková, Petr Haškovec, Michaela Bailová, Martin Mrovec, Josef Raška) Při modelování úloh mechaniky je často nutno počítat na dostatečnou přesnost, což znamená počítat na dostatečně husté síti. Zvyšuje se tak počet neznámých v úloze, která vede k řešení rozsáhlých soustav rovnic v řádech milionů až miliard. Je běžné, že se takováto matice soustavy, případně její dekompozice, nevlezou do paměti počítače, což je jeden z důvodů, proč nelze rovnou použít přímých řešičů. Iterační metody na druhé straně mají problémy s robustností výpočtu v případě špatně podmíněné matice soustavy. Kombinací obou přístupů jsou například tzv. FETI metody rozložení oblastí, které jsou navíc masivně paralelizovatelné. FETI metody jsou dlouhodobě zkoumány a vyvíjeny na Katedře aplikované matematiky a jsou součástí knihoven MatSol (nad Matlabem) a FLLOP (nad PETSci). V uplynulém roce jsme získali výrazné zkušenosti s výpočty na TIER-1 a TIER-0 systémech infrastruktury PRACE (HECTOR na EPCC Edinburk, VUORI na CSC Helsinki, CURIE ve Francii a další). Současný výzkum je zaměřen na kontaktní úlohy mechaniky, jež jsou intenzivně zkoumanou, přesto stále velmi náročnou oblastí. V roce 2013 bude dokončena implementace aproximace kontaktních podmínek pomocí mortarů ve 3D, začneme modelovat vznik tepla při kontaktu se třením a budeme pokračovat ve tvarové optimalizaci s kontakty a s řešením dynamických úloh. Poměrně novou a slibnou tématikou je formulace kontaktních podmínek pomocí level set funkcí, ve které chceme rozvíjet nově nabyté zkušenosti. Jeden z nejvýznamnějších nástrojů pro odhalování dynamických vlastností modelů je tzv. Lyapunovův exponent, který pokud je záporný, dokazuje periodicitu daného modelu, je-li nulový, pak dochází k bifurkaci a konečně je-li kladný, model vykazuje chaotické chování. V současné době existují, a jsou vyvíjeny, celé řady přístupů a algoritmů pro výpočet Lyapunovových exponentů a to jak pro jedno-dimenzionální tak pro více-dimenzionální modely. V příštím roce bude pozornost soustředěna na dvoudimenzionální případ diskrétního modelu dravec-kořist. Proběhne aplikování vyvinutých metod na vybrané úlohy z environmentálních věd, mechaniky, fyziky, chemie, diskrétní matematiky a informatiky. Současně bude vytvořeno rozhraní k vybraným open sourceovým kódům jako jsou ELMER vyvíjený v CSC Helsinki, CODE_ASTER vyvíjený v EDF France, CODE_SATURN vyvíjeny v STFC Daresbury laboratory a další, za účelem nejen akademického, ale i průmyslového využití námi vyvíjených algoritmů. Předpokládá se spolupráce na řešení mezinárodních projektů PRACE-2IP (2011-2013) a PRACE-3IP (2012-2014) a nově zapojení členů týmu do projektu FP7 EXA2CT. Tým 3. Řešení výpočetně náročných úloh ve fyzice a chemii (Řešitelský tým: Dalibor Lukáš, Michal Merta, Marie Sadowská, Martin Stachoň, Jan Zapletal, Lukáš Malý, Robert Skopal) Cílem výzkumu je pokračovat ve vývoji paralelních metod hraničních prvků (BEM) pro šíření akustických, mechanických a elektromagnetických vln a aplikovat je v rámci nového prestižního projektu TAČR s firmou Honeywell na úlohy identifikace trhlin na komponentech letadla. Na vývoji BEM pro vlnové rovnice nově spolupracujeme s Dr. Veitem z ETH Curych. Výhodou BEM je, že diskretizuje pouze hranici oblasti. Výsledné matice soustavy jsou husté a dále se hierarchicky zřeďují, tzv. fast BEM. V rámci předchozího projektu SGS byla vyvinuta paralelní implementace fast BEM na počítačích se sdílenou pamětí. V dalším roce řešení projektu jsme díky netriviálním výsledkům Petra a Terezy Kovářových v teorii grafů vyvinuli paralelní implementaci i pro počítače s distribuovanou pamětí. Impaktovaný článek je před odesláním. Numerické výpočty vykazují optimální časovou škálovatelnost tak, že jsme schopni sestavovat 3d fast BEM matice až do 3 milionů elementů na 133 jádrech. Odpovídající objemová (např. FEM) úloha by vedla na miliardu neznámých. V další fázi zlepšíme i paměťovou škálovatelnost tím, že nahradíme zřeďovací techniku Adaptive Cross Approximation (ACA) za paměťově šetrnější Fast Multipole Method (FMM) a implementujeme předpodmínění soustav. Výsledkem bude impaktovaný článek, který prokáže efektivitu metody na řešení náročných inženýrských úloh. Další oblastí našeho zájmu je systematické studium teorie metod rozložení oblasti založených na metodě konečných prvků a vývoj příbuzných metod založených na BEM. Nastudovali jsme teorii 2d metod, která předpokládá dekompozici oblastí do trojúhelníků, což je velmi vzdáleno praktickým dekompozicím generovanými např. knihovnou Metis. V následující fázi projektu 2d teorii rozšíříme na polygonální subdomény, kde se harmonické bázové funkce konstruují pomocí BEM. Výsledkem bude impaktovaný článek. Tým 4. Řešení výpočetně náročných úloh v diskrétní matematice a informatice (Řešitelský tým: Petr Kovář, Tereza Kovářová, Michael Kubesa, Rostislav Hrtus, Alena Vašatová, Adam Silber, Václav Sitta, Martin Kovář) Výzkum bude v další fázi zaměřen na optimalizaci rozdělení bloků paměti pro paralelní výpočty na superpočítači bez sdílené paměti. Práce je rozdělena do dvou oblastí: 1) Teoretická část využívající známých metod teorie grafů (cyklická ohodnocení grafů, rozklady grafů, nafukování grafů), teorie designů (známe konstrukce speciálních typů designů) a teorie čísel (systémy dokonalých rozdílů). Zatímco v předchozí fázi se úspěšně podařilo aplikovat známé výsledky pro přesné konstrukce pro vybrané řády, nyní se pokusíme zobecnit konstrukce i pro další řády za současné relaxace některých omezujících podmínek. Budeme se věnovat téměř vyváženým rozkladům, kdy se jednotlivé rozkládací grafy liší v počtu hran nejvýše o 1. Toto zobecnění dobře odpovídá praktické motivaci úlohy a současně přináší nové poznatky v oblasti teorie designů. 2) Druhou oblastí je hledání rozkladů užitím výpočetní techniky. Budeme využívat paralelní modifikaci DLX algoritmu, který byl vyvíjen v rámci předchozího projektu SGS. Je nutno zdůraznit, že aplikační část výzkumu musí jít ruku v ruce s teoretickým přístupem, neboť již pro velmi malé počty jader výpočetního klastru (řádově 20, 24 jader) není možné najít optimální řešení rozkladu ani hrubou silou (prozkoumáním všech možností), neboť počet vyšetřovaných variant se pohybuje v řádech 10^20 a větších a objem zkoumaných dat se pohybuje ve stovkách GB. Avšak kombinace teoretického přístupu (kdy zredukujeme nebo rozložíme velkou úlohu na několik menších úloh) a výpočetního přístupu (kdy strojově vyřešíme dílčí nebo zredukované úlohy) umožňuje najít řešení pro konkrétní případy. Zaměříme se na hledání rozkladů v případě, kdy rozkládající grafy jsou husté, ne však nutně isomorfní, ani se stejným počtem hran.

prof. RNDr. Marek Lampart, Ph.D.
Ing. Marie Sadowská, Ph.D.
doc. Ing. Petr Beremlijski, Ph.D.
Ing. Oldřich Vlach, Ph.D.
doc. Mgr. Petr Vodstrčil, Ph.D.
Ing. Pavla Hrušková, Ph.D.
doc. Ing. Dalibor Lukáš, Ph.D.
doc. Ing. David Horák, Ph.D.
prof. RNDr. Zdeněk Dostál, DSc.
RNDr. Michael Kubesa, Ph.D.
doc. Mgr. Vít Vondrák, Ph.D.
Mgr. Tereza Kovářová, Ph.D.
prof. Ing. Tomáš Kozubek, Ph.D.
doc. Mgr. Petr Kovář, Ph.D.
prof. Ing. Tomáš Kozubek, Ph.D.
Ing. Tomáš Kocyan
Ing. Petr Kotas
Ing. Martin Menšík
Ing. Rostislav Hrtus, Ph.D.
Ing. Lukáš Pospíšil, Ph.D.
Ing. Martin Stachoň
Ing. Václav Hapla, Ph.D.
Ing. Aleš Ronovský
Mgr. Kristina Motyčková, Ph.D.
Ing. Michal Merta, Ph.D.
Ing. Jan Zapletal, Ph.D.
Ing. Alena Ješko, Ph.D.
Ing. Martin Hasal, Ph.D.
Ing. Adam Silber
Ing. Matyáš Theuer
Ing. Rajko Ćosić
Ing. Lukáš Malý
Artur Iwan
Ing. Václav Ryška
Ing. Robert Skopal
Ing. Pavla Jirůtková
Ing. Michaela Bailová, Ph.D.
Ing. Martin Mrovec
Bc. Petr Ehler
Bc. Petr Haškovec
Mgr. Václav Sitta
Bc. Josef Raška
Bc. Martin Kovář

Obecné výstupy
10 impaktovaných publikací, články ve sbornících mezinárodních i tuzemských konferencí, 2 grantové přihlášky, další rozšíření funkcionality a aplikovatelnosti paralelních knihoven FLLOP, MatSol, MULTYDIN a knihovny FastBEM řešičů, vytvoření nových knihoven pro řešení specifických problémů, posílení zapojení se do řešení mezinárodního projektů PRACE-2IP (2011-2013) a PRACE-3IP (2012-2014) a nově zapojení členů týmu do projektu FP7 EXA2CT a HARPA.

Tým 1. Řešení výpočetně náročných úloh v environmentálních vědách
• Efektivní výpočet záplavových jezer.
• Paralelní algoritmy pro výpočet šíření znečištění ovzduší.
• Spolehlivostní modelování v hydrologii.
• Řešení inverzních úloh a jejich paralelní implementace.
Tým 2. Řešení výpočetně náročných úloh v mechanice
• Paralelní vyhledávání kontaktů a dokončení mortarů pro 3D úlohy.
• Termomechanické vlastnosti kontaktu se třením.
• Dvoudimenzionální případ diskrétního modelu dravec-kořist ve výpočtu Lapunova koeficientu.
• Paralelní řešení úlohy tvarové optimalizace pro 3D kontaktní úlohu s Coulombovým třením.
• Rozšiřování (o časově závislé úlohy, plasticitu) a zefektivňování (různé architektury) knihovny FLLOP, vytvoření interface s balíky Elmer a Code_Aster.
• Vývoj nových spádových metod, zkoumání jejich konvergence.
Tým 3. Řešení výpočetně náročných úloh ve fyzice a chemii
• Vývoj knihovny pro paralelní fast multipole BEM.
• Testování knihovny na inženýrských úlohách (článek Lukáš, Merta, Kovář).
• BEM pro hrubou úlohu v 2d metodách rozložení oblasti (článek Lukáš, Malý, Bouchala, Vodstrčil).
• BEM pro vlnovou rovnici (TAČR s Honeywell, spolupráce s ETH Curych).

Tým 4. Řešení výpočetně náročných úloh v diskrétní matematice a informatice
• Návrhy rozkladů grafů pro řády vhodné pro paralelní implementaci BEM.
• Teoreticky stanovené nutné podmínky rozkladů za případného zohlednění dalších omezujících podmínek, které vyplývají z praktické motivace (optimální rozložení zátěže pro jednotlivá jádra).