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

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

SP2014/204

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

01. 01. 2014 - 31. 12. 2014

1. Úvod Předkládaný projekt navazuje na výsledky řešení projektu SGS s názvem Paralelní řešení výpočetně náročných úloh z roku 2013, jehož cílem bylo vyvinout, implementovat, testovat a optimalizovat nové paralelní algoritmy na řešení náročný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. Předkládaný projekt bude pokračovat v optimalizaci stávajících kódů a ve vývoji nových efektivních algoritmů ve zmíněných oblastech, jejich masivně paralelní implementaci a testování na TIER-1 a TIER-0 systémech. Členové týmu se budou rovněž podílet na řešení úkolů aktuálně běžících mezinárodních projektů PRACE-2IP, PRACE-3IP, EXA2CT a HARPA, přispějí 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 výpočetních metod pro řešení problémů z oblasti environmentálních věd, dopravní telematiky, mechaniky, fyziky, chemie, diskrétní matematiky a informatiky, které jsou v současné době díky svému rozsahu, složitosti, nehladkosti nebo nelinearitě neřešitelné na běžných pracovních stanicích. • Paralelní implementace vyvinutých algoritmů do knihoven FLLOP, MatSol, MULTIDYN, knihovny BEM4I ř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 a centra IT4Innovations. • Aktualizace existujících rozhraní k vybraným open sourceovým kódům, případně vytvoření nových 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. • Řešení úkolů a aktivit mezinárodních projektů PRACE-2IP, PRACE-3IP a nově EXA2CT a HARPA zaměřených na HPC. 3. Historie týmu Předkladatel je od roku 2013 profesorem 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ž 25 impaktovaných publikací, hlavním řešitelem za VŠB-TUO mezinárodního projektu EXA2CT (2013-2016) zaměřeného na vývoj exascale algoritmů a pokročilých technik a národního projektu OPVK SPOMECH (2011-2014) zaměřeného na spolehlivé řešení nelineárních úloh mechaniky. Dále je řešitelem nebo členem řešitelských týmů celé řady domácích projektů GAČR, AVČR, MŠMT, MS kraje a mezinárodních projektů PRACE 1IP (2010-2013), PRACE 2IP (2011-2014), 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 13 zaměstnanců a 29 studentů katedry aplikované matematiky. • 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 9 projektech GAČR, 2 grantech AVČR, projektu MS kraje Floreon+, Výzkumném záměru, několika spoluprací s průmyslem a 6 mezinárodních projektech PRACE 1IP, PRACE 2IP, PRACE 3IP, EXA2CT, HARPA a ESF OPTPDE. Vybrané publikace (pouze publikované) členů týmu s impakt faktorem za rok 2013 z tématiky projektu: 1. Marek Lampart; Jaroslav Zapoměl Dynamics of the electromechanical system with impact element Journal of Sound and Vibration 1.558 2. Jiří Bouchala; Zdeněk Dostál; Petr Vodstrčil Separable Spherical Constraints and the Decrease of a Quadratic Function in the Gradient Projection Step JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1.062 3. Tomáš Kozubek; Vít Vondrák; Martin Menšík; David Horák; Zdeněk Dostál; Václav Hapla; Pavla Hrušková; Martin Čermák Total FETI domain decomposition method and its massively parallel implementation ADVANCES IN ENGINEERING SOFTWARE 1.22 4. Radek Kučera; Tomáš Kozubek; Alexandros Markopoulos On large-scale generalized inverses in solving two-by-two block linear systems LINEAR ALGEBRA AND ITS APPLICATIONS 0.968 5. Sylwia Cichacz; Dalibor Froncek; Petr Kovář Decomposition of complete bipartite graphs into generalized prisms EUROPEAN JOURNAL OF COMBINATORICS 0.677 6. Francisco Balibrea; Juan L.G. Guirao; Marek Lampart A note on the definition of alpha limit set Applied Mathematics and Information Sciences 0.731 7. J. L. García Guirao; Marek Lampart; Guo Hua Zhang On the dynamics of a 4d local Cournot model Applied Mathematics and Information Sciences 0.731 8. Separable Spherical Constraints and the Decrease of a Quadratic Function in the Gradient Projection Step Jiří Bouchala; Zdeněk Dostál; Petr Vodstrčil JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1.062 Dalších 5 publikací je akceptovaných a několik dalších je v přípravě. 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 a dopravní telematice (Řešitelský tým: Vít Vondrák, Aleš Ronovský, Petr Kotas, Martin Hasal, Tomáš Režnar, Radek Tomis, Milan Jaroš, Václav Ryška, Erika Straková) Ř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ů. Jedním ze zásadních předpokladů řešení těchto úloh je vytvoření výpočetní sítě, která díky své rozsáhlosti mnohdy nemůže být generována na jednom počítači. Důvodem jsou enormní paměťové požadavky i výpočetní síla. Jako přirozené se proto jeví použití paralelizace této úlohy pomocí metod doménové dekompozice a její následné nasazení na masivně paralelních počítačích. Za tímto účelem budou vytvořeny nové nástroje pro generování velmi rozsáhlých sítí z dostupných digitálních modelů terénu za využití open sourceových balíků jako jsou PT-SCOTCH, Parmetis apod. Hlavním cílem je vytvoření plně automatizovaného systému paralelního generování výpočetních sítí, který by mohl být testován například v prostředí systému FLOREON+. Následným krokem je nasazení numerických modelů pro řešení 2D rozlivů řek při povodňových situacích a numerických modelů pro výpočet znečištění ovzduší. Stejně jako generování výpočetních sítí i vlastní řešení vyžaduje masivní paralelizaci a využití velmi výkonných paralelních počítačů. Za tímto účelem se plánuje využití open-sourceových paralelních kódů jako je OpenFoam, TELEMAC nebo Code_Saturne. Kromě problematiky modelování v environmentálních vědách se výzkumný tým rozšíří i o studenty, kteří se budou věnovat vybraným problémům dopravní telematiky. Modelování dopravní dostupnosti, vyhledávání tras a predikce dopravních situací jsou jevy, které logicky navazují na krizové jevy jako jsou povodně či omezení dopravy v důsledku smogových situací, či ekologických havárií. Výstupy těchto dopravních modelů musí být dostupné téměř v reálném čase a proto je nezbytné tyto modely urychlovat. Jako přirozený nástroj se opět jeví paralelizace modelů. Cílem této části výzkumného týmu proto bude analýza vybraných dopravních modelů za účelem jejich paralelizace a jejich nasazení na řešení reálných problémů na paralelních výpočetních prostředcích. Výše zmíněné problémy musí obvykle zajišťovat výstupy s vysokou spolehlivostí a dostupností. Právě touto problematikou se zabývá projekt EU FP7 s názvem HARPA (Harnessing Performance Availibility). Z tohoto důvodu se předpokládá zapojení členů týmu do řešení cílů tohoto projektu. Tým 2. Řešení výpočetně náročných úloh v mechanice (Řešitelský tým: Zdeněk Dostál, Oldřich Vlach, Petr Vodstrčil, Marek Lampart, Petr Beremlijski, David Horák, Lukáš Pospíšil, Kristina Motyčková, Václav Hapla, Matyáš Theuer, Pavla Jirůtková, Petr Haškovec, Michaela Bailová, Martin Mrovec, Josef Raška, Tom Raiman) Tým bude pokračovat v započaté práci v oblasti masivní paralelizace řešičů lineárních a kontaktních úloh. Cílem je otestovat stávající implementace metod rozložení oblasti zejména FETI typu a tím rozšířit vlastní vyvíjenou knihovnu FLLOP. Za účelem benchmarkingu na masivně paralelních úlohách je naplánována implementace generátoru obrovských úloh umožňující rychlé generování úloh na statisících jader mající primární dimenzi přesahující miliardu neznámých. V paralelizaci TFETI metody byly identifikovány bottlenecky, jakým je např. řešení hrubého problému, jejichž podíl na celkovém výpočetním čase významně roste s rostoucím počtem výpočetních jader a pro desetitisíce jader se tyto problémy stávají vážnou překážkou. Řešení vidíme v hybridní verzi TFETI (HTFETI), která zefektivňuje právě řešení tohoto hrubého problému tím, že používá TFETI metodu víceúrovňově - vytváří clustery podoblastí a na následné hrubé problémy podstatně menší dimenze opět používá TFETI. Dalším krokem ke zrychlení paralelní implementace je využití communication hiding/avoiding technik. V předchozím projektu bylo dokončeno sestavování 3D kontaktních podmínek pomocí mortarů a v navazujícím projektu se plánuje práce na matematickém modelu a implementaci úloh termoelasticity. Současně začínáme s paralelní C++ implementací sestavování matic pro úlohy mechaniky a kontaktu. Zde se úspěšně podílíme na vývoji paralelního algoritmu pro fast marching, byla vyvinuta knihovna pro paralelní level set a fast marching metody, která byla propojena s knihovnou UG ve Švýcarsku pro simulaci kontaktu. Rovněž budou rozšířeny řešiče ve FLOPPu o semihladké Newtonovy metody. V úlohách tvarové optimalizace se zaměříme na úlohy s realističtějšími modely tření - Trescovo a Coulombovo tření s koeficientem tření závislým na řešení, což obnáší vyvinout citlivostní analýzu reflektující tyto modely. Pro řešení těchto úloh, které vedou obecně na minimalizaci nediferencovatelné funkce, je třeba použít vhodné algoritmy. K tomuto účelu chceme implementovat metodu r-sečen a ověřit, zda tato metoda dokáže nahradit běžně užívanou bundle metodu. V předchozí fázi byl vypracován návrh modifikace optimálního algoritmu kvadratického programování MPRGP pro úlohy s positivně semidefinitním hessiánem vzhledem k množině popsané pomocí lineárních omezení. Testování proběhlo na úloze dynamiky tuhých těles pomocí sekvenční implementace v jazyce C. V další fázi bude tento algoritmus paralelizován pomocí knihovny MPI. Rovněž se bude pokračovat v kvantifikaci dynamických vlastností diskrétních systémů pomocí Lyapunovových exponentů a členové týmu budou zapojeni do plnění milníků mezinárodních projektů PRACE-2IP, PRACE-3IP a 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, Martin Stachoň, Jan Zapletal, Lukáš Malý, Michal Kravčenko, Rajko Ćosić, Robert Skopal, Lenka Vozárová) Hlavní oblastí 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. Na vývoji BEM pro vlnové rovnice spolupracujeme s Dr. Veitem z Chicaga (dříve 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 a – díky spolupráci se skupinou doc. Kováře zabývající se teorií grafů - distribuovanou pamětí. V roce 2013 byl zaslán článek do časopisu s IF. Teorie grafů dává optimální distribuci paměti pouze pro jisté počty procesů. V roce 2014 metodu rozšíříme na obecný počet procesů. Rovněž jsme v rámci nové knihovny BEM4I nahradili stávající zřeďovací techniku Adaptive Cross Approximation (ACA) za paměťově šetrnější Fast Multipole Method (FMM). Knihovna využívá též OpenMP a vektorizaci výpočtu, což urychlilo stávající kód na uzlu ANSELMu až 64-krát. Další oblast našeho zájmu jsou metody konečných prvků pro elastické vlnové rovnice na tenkostěnných strukturách. Metody budeme aplikovat ve spolupráci s firmou Honeywell (Brno) na úlohy identifikace trhlin na komponentech letadla. Ukazuje se, že pro vyšší frekvence vln je nutné použít konečné prvky vyššího řádu. Vhodná metoda pro tento účel byla navržena ve skupině prof. Schoeberla (TU Vídeň) a implementována v jeho open-source kódu Netgen/NgSolve. S Prof. Schoeberlem na toto téma budeme v roce 2014 spolupracovat. Systematicky studujeme teorii metod rozložení oblasti, což v roce 2013 vyústilo k nové analýze metody ve 2d a k zaslání článku do časopisu s IF. Metody rozložení oblasti kombinujeme s metodou hraničních prvků. V následujícím roce metodu implementujeme v MPI-C++ a otestujeme na ANSELMu. Ukazuje se, že 2d metoda bude použitelná i pro účely modelování tenkostěnných struktur, viz předchozí odstavec. Rovněž jsme ve spolupráci se skupinou doc. Kováře našli další použití teorie grafů, které dovoluje optimálně přidělit hranové úlohy subdoménám. V rámci spolupráce s Honeywell na úloze identifikace trhlin se ukázalo nezbytné modelovat piezoelektrické aktuátory a senzory. Navrhli jsme FEB-BEM pro piezoelektřinu a implementovali ji v Matlabu. To vede na 3x3 sedlo-bodovou strukturu matice. V další fázi se budeme zabývat teorií sedlo-bodových úloh, stabilních diskretizací a předpodmíněním jejich více-úrovňových variant. 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á, Rostislav Hrtus, Alena Vašatová, Adam Silber, Matěj Krbeček, Vojtěch Zicha) Výzkum bude v další fázi zaměřen na optimalizaci rozdělení zátěže při paralelizaci výpočtů na hranicích oblastí. A na hledání paralelní implementace. Práce je rozdělena do tří oblastí: 1) Teoretická část využívající metod teorie grafů (orientovaný rovinný graf, případně grafy odpovídající 3D modelům), jedná se zejména o minimalizaci nejvyššího odchozího stupně v orientaci jednoduchého grafu. Zatímco pro řešení úlohy v 2D je teoretický výsledek znám, tak pro obecný graf se jedná o úlohu obtížnější a místo je jak pro heuristické přístupy, tak pro hledání obecných horních odhadů mezí. Pokusíme se najít konstruktivní (nejen existenční) důkazy, které by vedly k algoritmickému řešení úlohy. 2) Druhou oblastí zůstává hledání rozkladů užitím výpočetní techniky. S využitím paralelní modifikace DLX algoritmu, který byl vyvíjen v rámci předchozích projektů SGS, se podařilo klasifikovat některé grafy na 12 vrcholech. Podařilo se najít příslušné rozklady. Nadále musí výzkum teoretický a empirický s využitím hrubé výpočetní síly jít ruku v ruce, neboť již pro grafy s řádově 12 vrcholy se jedná o úlohu extrémně paměťově (10 až 200GB) i výpočetně náročnou. V minulém období se dařilo nacházet rozklady na husté, nikoliv nutně kompletní podgrafy. V dalším bychom se pokusili hledat rozklady na husté a ne nutně isomorfní podgrafy. 3) Třetí oblastí se nově stane výzkum v oblasti ohodnocení grafů, kde bychom rádi převedli stávající sekvenční algoritmy pro hledání předepsaných typů ohodnocení (obvykle bijekcí mezi množinou všech n vrcholů grafu a množinou 1,2,...,n s předepsanými podmínkami u vrcholů) pro spuštění na paralelním výpočetním clusteru. Nalezené grafy pak slouží jako základní konstruktivní příklady v obecných induktivních konstrukcích grafů s předepsaným ohodnocením, což je jeden z dlouhodobých výzkumných směrů na katedře.

prof. RNDr. Marek Lampart, Ph.D.
doc. Ing. Petr Beremlijski, Ph.D.
Ing. Oldřich Vlach, Ph.D.
doc. Mgr. Petr Vodstrčil, 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.
Ing. Petr Kotas
prof. Ing. Tomáš Kozubek, Ph.D.
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. Radek Tomis
Ing. Rajko Ćosić
Ing. Lukáš Malý
Ing. Tomáš Režnar
Ing. Václav Ryška
Ing. Milan Jaroš, Ph.D.
Ing. Robert Skopal
Ing. Matěj Krbeček
Ing. Pavla Jirůtková
Ing. Michaela Bailová, Ph.D.
Ing. Martin Mrovec
Ing. Tom Raiman
Ing. Erika Viščorová
Bc. Petr Haškovec
Bc. Josef Raška
Vojtěch Zicha
Ing. Lenka Vozárová

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 BEM4I řešičů, vytvoření nových knihoven pro řešení specifických problémů, plnění milníků mezinárodních projektů PRACE-2IP, PRACE-3IP, EXA2CT a HARPA.

Tým 1. Řešení výpočetně náročných úloh v environmentálních vědách a dopravní telematice
• Efektivní výpočet záplavových jezer.
• Paralelní algoritmy pro výpočet šíření znečištění ovzduší.
• Efektivní algoritmy v dopravní telematice.

Tým 2. Řešení výpočetně náročných úloh v mechanice
• Implementace nových generátorů obrovských lineárních a kontaktních úloh.
• Implementace hybridního TFETI (HTFETI) do knihovny FLLOP a napojení knihovny FLLOP na softwareové balíky Sifel a PMD.
• Optimalizace iteračních řešičů (CG, DCG) s využitím „communication hidden“ nebo „communication avoiding“ strategie.
• Dokončení termoelasticity s kontaktem a třením.
• Implementace a benchmarky pro metodu r-sečen v úlohách optimalizace.
• Dvoudimenzionální případ diskrétního modelu dravec-kořist ve výpočtu Lyapunova koeficientu.

Tým 3. Řešení výpočetně náročných úloh ve fyzice a chemii
• Vývoj knihovny BEM4I.
• Testování paralelní škálovatelnosti na inženýrských úlohách.
• FEM pro šíření vln na tenkostěnných strukturách.
• Testování paralelní škálovatelnosti primární DDM v kombinaci s BEM.
• Stabilní diskretizace a předpodmínění sedlo-bodových formulací piezoelektřiny.

Tým 4. Řešení výpočetně náročných úloh v diskrétní matematice a informatice
• Teoretické (co nejmenší) horní odhady minimálního odchozího stupně v orientaci grafu, který modeluje oblasti sítě při paralelním numerickém řešení úloh.
• Konkrétní rozklady kompletních grafů na husté podgrafy vhodné pro paralelizaci výpočtu na clusteru ANSELM (s počtem jader=vrcholů blízkým násobkům 16).
• Návrh paralelního kódu pro hledání různých typů bijektivních ohodnocení s předepsanými podmínkami.