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

Paralelní zpracování výpočetně náročných inženýrských úloh - etapa II

SP/2010173

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

01. 01. 2010 - 31. 12. 2010

1. Úvod Předkládaný projekt navazuje na dílčí výsledky řešení stejnojmenného víceletého projektu IGS, který byl zahájen v loňském roce 2009. V jeho druhé etapě chceme dokončit, příp. dále rozšířit stávající výstupy, dále zefektivnit implementované metody a začít s jejich testováním. Právě masivní testování a nasazení vyvinutých paralelních algoritmů na řešení rozsáhlých inženýrských úloh je hlavním cílem celého projektu, který by měl být plně dosažen v jeho poslední III. etapě. 2. Cíle projektu Navázat na výsledky předchozí etapy a pokračovat v rozvoji efektivních matematických metod pro řešení problémů, které jsou v současné době díky svému rozsahu, nehladkosti nebo nelinearitě na hranici řešitelnosti. Následně bude provedeno jejich zapojení do řešení vybraných komplexních vědeckých a inženýrských problémů v mechanice, akustice, molekulární dynamice, elektromagnetismu, analýze obrazu a v dalších oblastech. Předkládaný projekt se zaměřuje na vývoj paralelních algoritmů pro výpočetně náročné úlohy a jejich aplikace. V rámci této etapy budou dokončeny a dále rozšířeny vyvíjené paralelní algoritmy a doimplementovány stávající algoritmy, které jsou zatím dostupné pouze v sekvenční verzi. Algoritmy a struktury budou implementovány do knihoven, které budou rozšiřovat některé stávající jako je PetSc., OOSol, MatSol, nebo vzniknou jako zcela nové řešení některých proprietálních problémů. 3. Historie týmu Předkladatel je autorem 14 impaktovaných publikací a spoluřešitelem celé řady projektů GAČR, AVČR, MŠ a MS kraje. Od roku 2007 docent na VŠB-TU, název habilitační práce: "Aplikace metody fiktivních oblastí a waveletů na řešení parciálních diferenciálních rovnic". Účastníci týmu se podíleli v posledních 3 letech na více než 15 impaktovaných publikacích a 6 projektech GAČR, 2 grantech AVČR, projektu MS kraje Floreon+ a Výzkumném záměru. 4. Výstupy předchozí etapy Granty V roce 2009 bylo zahájeno řešení projektu GAČR řešitele Ing. Davida Horáka, Ph.D. Jeden grant se připravuje k podání v březnu 2010 u GAČR. Impaktované publikace za I. etapu řešení (pouze vyšlé a přijaté v roce 2009) 1. BEREMLIJSKI, P., HASLINGER, J., KOČVARA, M., KUČERA, R., OUTRATA, J. Shape Optimization in Three-Dimensional Contact Problems with Coulomb Friction. SIAM Journal on Optimization, 2009, 20(2009): 1, 416-444. 2. BOUCHALA, J., DOSTÁL, Z., SADOWSKÁ, M. Scalable Total BETI Based Algorithm for 3D Coercive Contact Problems of Linear Elastostatics. Computing, 2009, 85, pp. 189-217, 1007/s00607-009-0044-9. 3. DOSTÁL, Z., KOZUBEK, T., VONDRÁK, V., BRZOBOHATÝ, T., MARKOPOULOS, A. Scalable TFETI algorithm for the solution of coercive multibody contact problems of elasticity. Accepted in International Journal for Numerical Methods in Engineering, 2009, IF 2.229. 4. HASLINGER, J., ITO, K., KOZUBEK, T., KUNISCH, K. and PEICHL, G. On the shape derivative for problems of Bernoulli type, Interfaces and free boundaries 11, 2 (2009), pp. 317-330, IF 0.955. 5. HASLINGER, J., KOZUBEK, T. and KUČERA, R. Fictitious domain formulations of unilateral problems: analysis and algorithms, Computing 84 (2009), pp. 69-96, IF 1.0. 6. HORÁK, D., DOSTÁL, Z., STEFANICA, A. A scalable FETI-DP algorithm with non-penetration mortar conditions on contact interface, Journal of Computational and Applied Mathematics, Volume 231 , Issue 2, 2009, pages 577-591, ISSN:0377-0427. 7. KOVÁŘ, P., FEŇOVČÍKOVÁ A., BAČA, M., SHAFIQ, M.K. On Super $(a,1)$-Edge-Antimagic Total Labelings of Regular Graphs. Discrete Mathematics, 2009 (přijato) 8. KOVÁŘ, P., FRONČEK, D., KUBESA, M. Decomposition of complete graphs into C_m[2]. Discrete mathematics, 2009 (přijato) 9. LUKÁŠ, D., POSTAVA, K., ŽIVOTSKÝ, O. Optimization of Electromagnet for High-Field Polar Magneto-Optical Microscopy, 3 pp., Journal of Magnetism and Magnetic Materials (IF 1.283). V tisku. 10. LUKÁŠ, D., POSTAVA, K., ŽIVOTSKÝ, O. A Shape Optimization Method for Nonlinear Axisymmetric Magnetostatics Using a Coupling of Finite and Boundary Elements, 16 pp., Mathematics and Computers in Simulation (IF 0.93) (přijato). Pozn. Dalších 6 impaktovaných publikací v přípravě. Implementované paralelní knihovny MatSol: K paralelizaci knihovny MatSol byl použit Matlab Distributed Computing Engine firmy Mathworks a Parallel Toolbox. Konkrétně bylo paralelizováno vyskládávání matic, jejich faktorizace, násobící procedury a výpočty postprocessingu. Díky tomu jsme schopni řešit inženýrské úlohy o miliónech stupních volnosti. OOSol: Byly navrženy a implementovány blokové a distribuované matice na bázi MPI, včetně jejich základních BLAS routin. V implementační fázi je i alternativní technologie pro distribuované blokové matice založená na technologii CORBA. 5. Popis řešení a výstupy II. etapy Tým 1. Distribuované datové struktury a paralelní algoritmy (Řešitelský tým: Doc. Mgr. Vít Vondrák, Ph.D., Ing. David Horák, Ph.D., Bc. Martin Stachoň, Bc. Jakub Dostál, Bc. Lukáš Vojáček, Bc. Michal Merta, Bc. Jan Zapletal, Bc. Václav Hapla) Řešení mnoha technických problémů je redukováno na řešení soustav lineárních rovnic se speciální maticí velké dimenze. Náročnost řešení rozsáhlých soustav byla podnětem pro vývoj efektivních algoritmů. Jedna z úspěšných tříd metod je založena na principu “rozděl a panuj”, spočívající v rozložení oblasti na jednoduché podoblasti, definici rozšířených okrajových úloh a iteračního procesu pro tvorbu řešení z řešení problémů lokálních. Tyto metody mohou být velmi efektivně implementovány pro použití na masivně paralelních počítačích. K tomu potřebují ale řadu podpůrných nástrojů, jejichž vývoj je hlavním cílem této části projektu. Hlavní cíle jsou tedy následující: návrh a implementace vhodných distribuovaných datových struktur, zejména matic a vektorů vhodných formátů. Dále vytvoření vhodného rozhraní pro paralelní komunikaci, což obnáší zejména inicializaci paralelního prostředí, distribuci dat na jednotlivé procesory a paralelní implementace řešičů s použitím C++ knihovny OOSol (sekvenční software vyvíjený na naší katedře) a PETSc (sada procedur z Argonne National Laboratory) včetně systematického ověření škálovatelnosti FETI řešičů kontaktních úloh a to nejen modelových. V předchozí etapě se podařilo splnit nejdůležitější cíl, kterým byl návrh a implementace distribuovaných datových struktur na výpočetní cluster prostřednictvím technologie MPI. Prozatím však byly implementovány pouze nejzákladnější BLAS routiny pro distribuované matice. Náplní druhé etapy pro rok 2010 je tedy doplnění všech BLAS routin tak, jak je známe z jejich sekvenčních verzí a nasazení těchto distribuovaných matic do složitějších algoritmů. Řešitelský tým proto čeká nesnadná úloha, kterou je testování dosud implementovaných sekvenčních verzí algoritmů v paralelním prostředí a jejich případná adaptace pro řešení na paralelních počítačích. Výsledkem by tak měla být funkční knihovna paralelních algoritmů, které tak budou k dispozici ostatním výzkumným týmům. Tým 2. Úlohy výpočetní mechaniky (Řešitelský tým: Ing. Oldřich Vlach, Ph.D., Ing. Marie Sadowská, Ph.D., Ing. Petr Beremlijski, Ph.D., Doc. RNDr. Jiří Bouchala, Ph.D., Mgr. Petr Vodstrčil, Ph.D., Ing. Lukáš Mocek) Při zkoumání a návrhu mechanických vlastností objektů je výhodné použít metod matematického modelování, zejména pro jejich nižší 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. Tady se uplatňuje přístup paralelního počítání, které řešení výrazně urychluje. V této sekci se chceme zaměřit na následující třídy problémů: Kontaktní úlohy jsou intenzivně zkoumanou, přesto náročnou oblastí. My se chceme zaměřit na paralelizaci vyhledávání oblasti kontaktu a aplikaci předpodmínění, které je pro kontaktní problémy významné. Úlohy tvarové optimalizace s kontakty představují výpočetně náročné problémy, které se skládají ze dvou obtížných problémů. Prvním z nich je samotná úloha tvarové optimalizace, kterou je třeba vhodně formulovat, dále 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. Druhým problémem je efektivní řešení stavové úlohy pro každý aktuální navržený tvar a odpovídající diskretizační síť, kterou lze zredukovat na jednoduchou a rychlou diskretizaci hranice oblasti pomocí hraničních prvků. Matematická teorie homogenizace představuje důležitý aparát při modelování kompozitních materiálů (materiál ze dvou nebo více substancí s rozdílnými vlastnostmi, které dohromady dávají výslednému výrobku nové vlastnosti, které nemá sama o sobě žádná z jeho součástí). Princip teorie homogenizace spočívá v tom, že hledáme homogenní materiál, který bude vykazovat stejné vlastnosti jako nehomogenní kompozitní materiál. Hledání tohoto homogenního materiálu však vůbec není jednoduché a není možné jej nalézt analyticky. Proto je potřeba přistoupit k numerickým metodám, díky kterým je možné charakterizovat zhomogenizovaný materiál s libovolnou předem danou přesností. V předchozí etapě jsme se zabývali řešením úloh 3D tvarové optimalizace, kdy k numerické realizaci stavové úlohy je použita diskretizace pomocí metody hraničních prvků. Byla implementována citlivostní analýza, tj. výpočet libovolného Clarkeova subgradientu z Clarkeova zobecněného gradientu pro libovolný řídící vektor popisující kontaktní hranici. Dále byla nastudována a implementována metoda Fast Multipole pro 2D okrajové úlohy s Laplaceovým operátorem v Matlabu. Taktéž byla analyzována situace s homogenizacemi v 1D, aplikována metoda asymptotické expanze a provedeny numerické experimenty v 1D a 2D pro “sendvičové” materiály. Bylo otestováno předpodmínění algoritmů pro řešení kontaktních úloh a analyzovány možnosti paralelního vyhledávání kontaktních párů. Ve druhé etapě bude sepsán popularizační článek o homogenizaci v 1D a provedeny numerické experimenty ve více dimenzích. Bude se pokračovat v řešení úloh tvarové optimalizace pro 3D kontaktní úlohu diskretizovanou metodou hraničních prvků a doimplementuje se semianalytická citlivostní analýza na místo konečných diferencí. Dále budou implementovány algoritmy pro nehladkou optimalizaci do knihovny MatSol a aplikovány na inženýrské úlohy tvarové optimalizace. Konečně, nastudování a implementace Fast Multipole metody pro 3D a implementace paralelního vyhledávání kontaktních párů do knihovny MatSol. Tým 3. Paralelní výpočty v akustice, elektromagnetickém záření a molekulární dynamice (Řešitelský tým: Ing. Dalibor Lukáš, Ph.D., Ing. Martin Kramář, Ing. Vojtěch Sokol, Bc. Kateřina Janurová, Ing. Martin Menšík, Bc. Lukáš Pospíšil) 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 nám umožní proniknout do nové oblasti, na což chceme navázat buď start-up grantem v rámci projektu IT4, nebo navazujícím projektem GA ČR. Vyvinuté metody budou průběžně testovány na aplikacích ve spolupráci s týmem Prof. Pištory a Doc. Postavy z Institutu fyziky a Prof. Čapkové z Centra nanotechnologií. V uplynulé etapě bylo provedeno párování FEM-BEM pro nelineární rotačně-symetrickou magnetostatiku a tvarová optimalizace ve spolupráci s doc. Postavou z Katedry fyziky. Byla implementována a odzkoušena nová a nejrychlejší známá metoda hraničních prvků pro Helmholtze. Taktéž byla otestována stabilizace GMRES pro BEM v akustice a provedeno modelování 2D elektrostatického pole chirurgického nástroje ve spolupráci s Ing. Penhakerem, Ph.D. (Katedra měření, VŠB) a MUDr. Vávrou, Ph.D. (chirurgie, FNO). V následující etapě budou řešeny benchmarky, nastudováno „density functional theory“, provedena analýza finitních řešičů vlastních čísel, aplikace na molekulu vodíku a srovnání s analytickým řešením. Otestuje se kombinace Multigrid-SMALE-FETI pro 3D magnetostatiku a provede se paralelní implementace v C++. Dále bude implementována a otestována homogenizace pro Helmholtzovu rovnici, aplikace na fotonické krystaly ve spolupráci s Doc. Postavou z Katedry fyziky, VŠB-TU Ostrava. Tým 4. Implementace metod diskrétní matematiky (Řešitelský tým: Mgr. Petr Kovář, Ph.D., Ing. Pavla Kabelíková, Ing. Martin Čermák, Bc. Rostislav Hrtus, Adam Silber) Výzkum v oblasti teorie grafů bude rozvržen do dvou částí. První z nich se bude zabývat paralelní implementaci úlohy nalezení rozkladu dané množiny A v systému jejich podmnožin S (DLX algoritmus). Jedná se o obecný přístup, který bude využit v další fázi při hledání základních grafů ("startérů" indukčních konstrukcí). Podobný přístup jsme využili v několika impaktovaných publikacích v posledních dvou letech, avšak jen v omezené míře kvůli extrémní početní náročnosti. Druhá část výzkumu se bude věnovat využití Perronova vektoru pro automatické rozdělení velkých úloh, které se objevují při řešení technických problémů ostatních částí tohoto projektu. Hlavním cílem je rozložení rozsáhlé úlohy na menší podúlohy, tak aby výpočetní náročnost těchto podúloh byla přibližně srovnatelná. Tímto se zajišťuje „load balancing“ použitého paralelního počítače při řešení těchto náročných úloh. V současnosti se totiž ukazuje, že největší ztráty v efektivní implementaci paralelního řešení jsou způsobeny právě nevyrovnaností jednotlivých paralelních procesů. V předchozí etapě byl nastudován DLX algoritmus a známé metody implementace. Byla implementována sekvenční verze ve třech variantách. Algoritmus je připraven pro řešení problému faktorizace kompletního grafu daného řádu na isomorfní kostry. Navíc byl navržen postup, který umožní automatické generování vstupního souboru dat se zohledněním automorfismu faktorizujících stromů. Současně byla nastudována problematika využití vlastních čísel a vektorů matic grafu. Byly formulovány různé hypotézy týkající se využití pro stabilizaci numerického výpočtu řešení soustav lineárních rovnic a byla rozpracována algebraická důkazová technika. Zkoumány byly jak matice sousednosti, tak i Laplaceova matice s Dirichletovými nebo Neumannovými okrajovými podmínkami. Náplní druhé etapy tedy bude paralelizace vyvíjených algoritmů, implementace algoritmu, který umožní automatické generování vstupního souboru dat se zohledněním automorfismu faktorizujících stromů. Pokračování v analýze stabilizace numerického výpočtu vhodným výběrem vrcholů grafu, dokončení důkazů. Tým 5. Variační metody v analýze obrazu (Řešitelský tým: Ing. Tomáš Fabián, Ing. Jan Gaura, Ing. Michal Krumnikl, Bc. Petr Kotas, Alena Vašatová) S narůstajícím výkonem dnešních procesorů se stává využití variačních metod v analýze obrazu zajímavé nejen z teoretického pohledu, ale i prakticky nasaditelné v reálných aplikacích. Jako velice perspektivní oblastí se jeví využití variačních metod pro úlohy segmentace obrazu a optického toku. Vzhledem k výpočetní náročnosti obou problémů bude jedním z cílů vytvořit paralelní implementace vybraných algoritmů. V další části se pak budeme zabývat vývojem upravených variačních formulací, které budou přizpůsobeny aktuálnímu zadaní. V předchozí etapě se tým zaměřil na problém lokalizace duhovek u sady testovacích obrázků. Byl sestaven a implementován algoritmus jejich lokalizace s využitím technologií zaměřených na masivní paralelismus a digitální zpracování obrazu. Zejména se jedná o implementaci prototypové aplikace s využitím optimalizované knihovny OpenCV určené k podpoře vývoje systémů počítačového vidění. V této etapě bude dokončen algoritmus lokalizace duhovky a provedena implementace s využitím vícejádrových procesorů případně grafických karet. Funkčnost bude otestována na sadě duhovek a provedena další optimalizace výkonu s využitím jazyka OpenCL.

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. Jiří Bouchala, Ph.D.
doc. Mgr. Vít Vondrák, Ph.D.
doc. Mgr. Petr Kovář, Ph.D.
Mgr. Ing. Michal Krumnikl, Ph.D.
doc. Ing. Martin Čermák, Ph.D.
Ing. Tomáš Fabián, Ph.D.
Ing. Jan Gaura, 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. Lukáš Vojáček, Ph.D.
Ing. Kateřina Martinovičová, Ph.D.
Ing. Václav Hapla, Ph.D.
Ing. Michal Merta, Ph.D.
Ing. Jan Zapletal, Ph.D.
Ing. Alena Ješko, Ph.D.
Ing. Adam Silber
Bc. Jakub Dostál
prof. Ing. Tomáš Kozubek, Ph.D.

Obecné výstupy
5 impaktovaných publikací, prezentace na mezinárodních i tuzemských konferencích, 1 grantová přihláška, rozšíření možností paralelních knihoven MatSol a OOSol.

Tým 1. Distribuované datové struktury a paralelní algoritmy
• Dokončení vhodného rozhraní pro paralelní komunikaci v OOSolu, což obnáší zejména inicializaci paralelního prostředí, distribuci dat na jednotlivé procesory a paralelní implementace řešičů.
• Doplnění distribuovaných datových struktur o paralelní verze BLAS routin a adaptace sekvenčních algoritmů na tyto distribuované struktury a jejich nasazení na paralelních počítačích
• Ověření škálovatelnosti FETI řešičů kontaktních úloh a to nejen modelových.
• Výstupem bude komplexní knihovna distribuovaných datových struktur a paralelních algoritmů v prostředí OOSol, popř. PETSc.

Tým 2. Úlohy výpočetní mechaniky
• Sepsání popularizačního článku o homogenizaci v 1D. Provedení numerických experimentů ve více dimenzích.
• Pokračování v řešení úloh tvarové optimalizace pro 3D kontaktní úlohu diskretizovanou metodou hraničních prvků. Implementace semianalytické citlivostní analýzy na místo konečných diferencí.
• Implementace algoritmů pro nehladkou optimalizaci a jejich aplikace v tvarové optimalizaci.
• Nastudování a implementace Fast Multipole metody pro 3D.

Tým 3. Paralelní výpočty v akustice, elektromagnetickém záření a molekulární dynamice
• Molekulární simulace: benchmarky, studium density functional theory, finitní řešiče vlastních čísel, aplikace na molekulu vodíku a srovnání s analytickým řešením.
• Kombinace Multigrid-SMALE-FETI pro 3D magnetostatiku, paralelní implementace v C++.
• Homogenizace pro Helmholtzovu rovnici, fotonické krystaly ve spolupráci s Doc. Postavou z Katedry fyziky, VŠB-TU Ostrava.


Tým 4. Implementace metod diskrétní matematiky
• Paralelizace vyvíjených algoritmů.
• Implementace algoritmu, který umožní automatické generování vstupního souboru dat se zohledněním automorfismu faktorizujících stromů.
• Pokračování v analýze stabilizace numerického výpočtu vhodným výběrem vrcholů grafu, dokončení důkazů.

Tým 5. Variační metody v analýze obrazu
• Dokončení algoritmu lokalizace duhovky.
• Implementace s využitím vícejádrových procesorů případně grafických karet.
• Otestování funkčnosti na sadě duhovek a další optimalizace výkonu s využitím jazyka OpenCL.