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

Vývoj, implementace a testování metod pro paralelní řešení výpočetně náročných úloh

SP2012/187

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

01. 01. 2012 - 31. 12. 2012

1. Úvod Předkládaný projekt navazuje na výsledky řešení projektu SGS s názvem Paralelní zpracování výpočetně náročných inženýrských úloh (2009-2011), 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 mechaniky, akustiky, elektromagnetismu, molekulových simulací, diskrétní matematiky a analýzy obrazu. Nový projekt bude pokračovat ve vývoji efektivních algoritmů, jejich masivně paralelní implementaci a testování. Navíc se rozšíří oblasti aplikovatelnosti na environmentální vědy, konkrétně povodně a šíření znečištění. Dojde k posílení zapojení členů týmu do řešení mezinárodních projektů PRACE-1IP a PRACE-2IP, k 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ů, 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 OOSol, MatSol 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 TEAR-0 superpočítačových systémech. • Aplikování vyvinutých metod na vybrané úlohy z environmentálních věd, mechaniky, fyziky, chemie, diskrétní matematiky a informatiky. 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 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Š, MS kraje a mezinárodních projektů PRACE 1IP, PRACE 2IP 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ů řešitelského týmu v RIV 2011: 2043 bodů • Podíl pracovníků s podstatným výkonem v RIV 2011 na řešení projektu: 8 členů (19%) týmu má více než 50 bodů v RIV 2011 • 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 2011: 650Kč/bod • Výkon ve VaV řešitelského týmu v roce 2011: 297 bodů (pouze impaktované publikace na WOS) Členové týmu se podíleli v posledních 3 letech na více než 20 impaktovaných publikacích a 8 projektech GAČR, 2 grantech AVČR, projektu MS kraje Floreon+, Výzkumném záměru a 3 mezinárodních projektech PRACE 1IP, PRACE 2IP a ESF OPTPDE. Vybrané publikace členů týmu s impakt faktorem za rok 2011 z tematiky projektu: 1. Tomáš Brzobohatý; Zdeněk Dostál; Tomáš Kozubek; Petr Kovář; Alexandros Markopoulos. Cholesky decomposition with fixing nodes to stable computation of a generalized inverse of the stiffness matrix of a floating structure, INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2. Marie Sadowská; Zdeněk Dostál; Tomáš Kozubek; Alexandros Markopoulos; Jiří Bouchala. Scalable total BETI based solver for 3D multibody frictionless contact problems in mechanical engineering, ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS 3. Zdeněk Dostál; Marta Domoradová; Marie Sadowská. Superrelaxation and the rate of convergence in minimizing quadratic functions subject to bound constraints, COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. 4. Zdeněk Dostál; Tomáš Kozubek; Alexandros Markopoulos; Martin Menšík. Cholesky decomposition of a positive semidefinite matrix with known kernel, APPLIED MATHEMATICS AND COMPUTATION. 5. Dalibor Fronček; Petr Kovář; Michael Kubesa. Factorizations of Complete Graphs into Trees with at most Four Non-Leave Vertices, GRAPHS AND COMBINATORICS. 6. Daniel Jandačka; Petr Beremlijski. Determination of Strength Exercise Intensities Based on the Load-Power-Velocity Relationship, JOURNAL OF HUMAN KINETICS. 7. Dalibor Lukáš; Kamil Postava; O. Životský. A Shape Optimization Method for Nonlinear Axisymmetric Magnetostatics Using a Coupling of Finite and Boundary Elements, Mathematics and Computers in Simulation. 8. Petr Kovář; Michael Kubesa; M. Meszka. Factorizations of complete graphs into brooms, Discrete Mathematics. 9. Zdeněk Dostál; Tomáš Kozubek; Tomáš Brzobohatý; Alexandros Markopoulos; Vít Vondrák; Petr Horyl. Theoretically supported scalable TFETI algorithm for the solution of multibody 3D contact problems with fiction, Computer Methods in Applied Mechanics and Engineering. 10. Radek Kučera; Tomáš Kozubek; Alexandros Markopoulos; J. Machalová. On the Moore-Penrose inverse in solving saddle-point systems with singular diagonal blocks. Numerical Linear Algebra with Applications. 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, Pavla Kabelíková, Tomáš Kocyan, Martin Menšík, Aleš Ronovský, Martin Hasal, Matyáš Theuer, Artur Iwan) Ř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. 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. 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, Ondřej Zjevík, Rajko Ćosić, Petr Ehler, Pavla Jirůtková, Petr Haškovec) Při zkoumání a návrhu mechanických vlastností součástí systému je výhodné použít metod matematického modelování, zejména pro jejich nižší časovou i finanční náročnost oproti metodě „vyrob/naměř“. Aby numerické řešení matematického modelu bylo dostatečně přesné, je nutno počítat na dostatečně husté síti, což vede k řešení rozsáhlých soustav rovnic. Jednou z efektivních možností řešení těchto úloh je paralelizace řešení prostřednictvím např. FETI metody rozložení oblastí. Tato metoda umožňuje nasazení inženýrských úloh na výpočetní klastry a jejich masivní paralelizaci a je dlouhodobě vyvíjena na Katedře aplikované matematiky FEI. Výzkum zaměříme na kontaktní úlohy mechaniky, jež jsou intenzivně zkoumanou, přesto stále velmi náročnou oblastí. Budeme se věnovat zefektivnění vyhledávání kontaktních zón, aproximaci kontaktních podmínek pomocí mortarů a vývoji předpodmínění, které je pro rozsáhlé kontaktní úlohy nezbytné. Dále rozšíříme funkcionalitu a aplikovatelnost knihoven MatSol a OOSol na další proprietální problémy z CFD, vedení tepla, akustiky a na sdružené multifyzikální inženýrské úlohy. Dále se zaměříme na úlohy tvarové optimalizace s kontakty, které představují výpočetně velmi náročné problémy složené ze dvou částí. První z nich je samotná úloha tvarové optimalizace, kterou je třeba vhodně zformulovat, zvolit vhodnou (hladkou/nehladkou) metodu pro její řešení a navrhnout tzv. citlivostní analýzu, kterou potřebujeme pro iterační řešení dané úlohy. Druhou částí je efektivní řešení stavové úlohy pro každý aktuální navržený tvar součásti s odpovídající modifikací diskretizační sítě. Zde s výhodou využijeme k diskretizaci úlohy metodu hraničních prvků (BEM), u níž stačí generovat síť pouze na hranici oblasti. Současně provedeme implementaci rychlých BEM řešičů založených na ACA a Fast Multipole metodách do MatSolu a otestujeme na vybraných inženýrských benchmarcích. Rovněž rozšíříme funkcionalitu MatSolu o řešiče úloh tvarové optimalizace typu minimax (minimalizovat maximum zvolené veličiny, např. deformace, napětí). Tým 3. Řešení výpočetně náročných úloh ve fyzice a chemii (Řešitelský tým: Dalibor Lukáš, Marie Sadowská, Lukáš Mocek, Vojtěch Sokol, Martin Kramář, Martin Stachoň, Jan Zapletal, Lukáš Malý, Robert Skopal) Cílem výzkumu je vyvinout paralelní metody výpočtu šíření akustických a elektromagnetických vln a aplikovat je např. na odhlučnění železničních kol nebo na vývoj nových materiálů pro integrovanou optiku. Úlohy jsou formulovány na neomezených oblastech a přirozeně vedou na použití metody hraničních prvků. Výsledné soustavy se zřeďují tzv. hierarchickým clusterováním a výpočet, např. neúplným LU-rozkladem, lze dobře paralelizovat. Paralelizace je potřebná zejména pro vysoké kmitočty záření, kde narůstá počet neznámých, a požadavky na celkovou paměť jsou v desítkách GB. Podobné algoritmy lze využít i pro výpočty molekulárně-dynamických systémů, kde masivní paralelizace je již nezbytná i pro relativně malé systémy o tisících molekulách. Přidělené prostředky umožní rozšířit oblasti výzkumu a možnosti spolupráce. Vyvinuté metody budou průběžně testovány na aplikacích ve spolupráci s týmem Doc. R. Kaluse, Prof. Pištory, Doc. Postavy a Prof. Čapkové z CE IT4Innovations. V rámci předchozího projektu SGS byla vyvinuta paralelní implementace metody hraničních prvků na paralelním počítači se sdílenou pamětí. Numerické výpočty vykazují škálovatelnost, která byla testována na úloze akustiky. Pomocí faktorizace grafů se podařilo Petru a Tereze Kovářovým navrhnout pro jisté počty procesorů optimální rozdělení mimodiagonálních bloků husté matice na podprocesory. Dále byly implementovány primární metody rozložení oblasti pro Laplaceovu úlohu ve 2 dimenzích, kde jsme numericky analyzovali nepřesnost předpodmínění lokálních úloh i Schurova doplňku na rozhraní. Konečně jsme implementovali paralelní program pro částicové a molekulové simulace založené na Newtonově mechanice tuhých těles formulované pomocí kvaternionů. V novém projektu bude implementována paralelní BEM na klastry s distribuovanou pamětí a s vyvažováním zatížení procesorů pomocí rozkladů grafů navržených Petrem a Terezou Kovářovými. V primárních metodách rozložení oblasti použijeme předpodmínění Schurova doplňku metodou hraničních prvků a otestujeme nepřesné řešení lokálních úloh. Vyvinutá paralelní knihovna pro molekulovou dynamiku bude aplikována na srážkovou dynamiku klastrů plynů. Konečně ve spolupráci se skupinou prof. Pištory a doc. Postavy zformulujeme úlohu tvarové optimalizace pro návrh optického nanokompozitu, který bude mít záporný efektivní index lomu. Tuto úlohu chceme řešit pomocí našeho softwaru pro Helmholtzovy rovnice, který doplníme o periodickou okrajovou podmínku. 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, Martin Čermák, Rostislav Hrtus, Michal Merta, Alena Vašatová, Adam Silber, Václav Sitta) Výzkum bude zaměřen na optimalizaci rozdělení bloků paměti pro paralelní výpočty na superpočítači se sdílenou pamětí. Práci můžeme rozdělit 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 designů, seskupitelných designů) a teorie čísel (systémy dokonalých rozdílů). Ukazuje se, že pro některé vybrané řády blokových matic je nalezení optimálního řešení možno přeformulovat jako úlohu teorie čísel a pro další řády využít rozkladů grafů. Tyto řády však obvykle neodpovídají počtu jader ve výpočetních klastrech a proto pro optimální využití architektury superpočítačů, je nutno hledat řešení i pro jiné řády. Využití známých metod je možné jen v omezené míře a pro konstrukci rozkladu bude nutno hledat metody nové. 2) Aplikační část, kdy pro malé řády a dílčí úlohy rozkladů budeme využívat paralelní modifikaci DLX algoritmu, který byl vyvíjen v rámci předchozího projektu SGS. Rozklady kompletních grafů patří mezi klasická témata teorie grafů a teorie designů. Ukazuje se, že rozsah aplikací metod i výsledků významně překračuje doménu základního výzkumu. Designy a zejména seskupitelné designy nacházejí uplatnění při plánování statistických experimentů. Rozklady kompletních grafů je možno přímo využít pro řadu "plánovacích úloh", kdy je třeba všechny možnosti rozdělit do skupin s řadou omezujících požadavků. Mezi nejznámější témata patří losování sportovních turnajů, ukládání dat na disková pole typu RAID. Každá ze zmíněných úloh má specifické omezující podmínky a často lze výsledky jedné metody použít jen v omezené míře pro jiný typ úlohy. 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 jinak než 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 blokových matic i velkých řádů. V první fázi výzkumu se zaměříme na teoretický přístup, kdy bude daná praktická úloha optimálního rozložení blokové matice pro paralelní výpočet přeformulována jako a) úloha rozkladů grafů na husté podgrafy, b) pro některé řády jako úloha nalezení systému dokonalých rozdílů a konečně c) jako úloha existence designu. Varianty b) a c) jsou použitelné jen v omezené míře, neboť praktická motivace nevyžaduje existenci isomorfních rozkladů, což je naopak základní požadavek pro systémy dokonalých rozdílů nebo existence seskupitelných designů. V další fázi (a v omezené míře již současně s první fází) bude možno implementovat obecnější generátor vstupních dat pro paralelní DLX algoritmus. Na základě získaných výsledků připravíme optimální rozložení blokové matice pro paralelní výpočet pro vhodné řády blokových matic (řády blízké hodnotám 64 až 128). Dalším výstupem budou jak příspěvky na konferencích, tak i časopisecké publikace. V neposlední řadě dojde k dalšímu rozvoji paralelní implementace DLX algoritmu, kterou na Katedře aplikované matematiky rozvíjíme. Dosažené výsledky bude možné také s výhodou použít i pro efektivní paralelní implementaci některých vyvíjených algoritmů v ostatních týmech.

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
doc. Ing. Martin Čermák, Ph.D.
Ing. Lukáš Mocek
Ing. Petr Kotas
Ing. Vojtěch Sokol
Ing. Martin Menšík
Ing. Martin Kramář
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
Bc. Ondřej Zjevík
Ing. Rajko Ćosić
Ing. Lukáš Malý
Artur Iwan
Ing. Robert Skopal
Ing. Pavla Jirůtková
Bc. Petr Ehler
Bc. Petr Haškovec
Mgr. Václav Sitta

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 MatSol a OOSol, vytvoření nových knihoven pro řešení specifických problémů, posílení zapojení se do řešení mezinárodního projektů PRACE-1IP (2010-2012) a PRACE-2IP (2011-2013) a nově zapojení se do projektu PRACE-3IP (2012-2014).

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.
• Paralelizace algoritmů pro výpočet šíření znečištění ovzduší.
• Využití stochastických modelů 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
• Rozšíření funkcionality a aplikovatelnosti knihoven MatSol a OOSol (CFD, vedení tepla, akustika, multifyzikální úlohy).
• Implementace rychlých BEM řešičů založených na ACA a Fast Multipole metodách do MatSolu a jejich testování.
• Zefektivnění vyhledávání kontaktů v MatSolu a využití mortarové aproximace kontaktních podmínek.
• Pokračování ve vývoji škálovatelných řešičů založených na metodě rozložení oblasti.

Tým 3. Řešení výpočetně náročných úloh ve fyzice a chemii
• Implementace paralelní BEM metody na klastry s distribuovanou pamětí pomocí rozkladu grafů.
• Implementace a testování primární metody rozložení oblasti s předpodmíněním Schurova doplňku metodou hraničních prvků.
• Použití vyvíjeného paralelního software na molekulovou dynamiku plynů.
• Formulace úlohy tvarové optimalizace nanokompozitu.

Tým 4. Řešení výpočetně náročných úloh v diskrétní matematice a informatice
• Optimalizace rozdělení mimodiagonálních bloků blokových matic za účelem zefektivnění paralelní implementace numerických výpočtů.
• Rozšíření implementace paralelní verze algoritmu DLX na jiné faktory než kostry.
• Automatická detekce automorfismu vybraných tříd obecných grafů.
• Využití implementovaného algoritmu pro nalezení rozkladů kompletních grafů na husté podgrafy.