DZIEKAN i RADA WYDZIAŁU INFORMATYKI, ELEKTRONIKI I TELEKOMUNIKACJI AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE |
|
---|---|
zapraszają na publiczną dyskusję nad rozprawą doktorską mgr inż. Piotr Gurgula |
|
LINEAR COMPUTATIONAL COST SOLVERS FOR ADAPTIVE SIMULATIONS | |
Termin: | 31 października roku 2014 o godz. 11:00 |
Miejsce: | Sala 1.36, ul. Kawiory 21, 30-059 Kraków, pawilon D-17 |
PROMOTOR: | dr hab. Maciej Paszyński, prof. nadzw. AGH, Akademia Górniczo-Hutnicza w Krakowie |
RECENZENCI: | Prof. dr hab. inż. Tadeusz Burczyński, Instytut Podstawowych Problemów Techniki PAN |
Prof. dr hab. Mariusz Flasiński, Uniwersytet Jagielloński | |
Prof. dr hab. inż. Witold Dzwinel, Akademia Górniczo-Hutnicza w Krakowie | |
Z rozprawą doktorską i opiniami recenzentów można się zapoznać w Czytelni Biblioteki Głównej AGH, al. Mickiewicza 30 |
mgr inż. Piotr Gurgul
Promotor: dr hab. Maciej Paszyński, prof. nadzw. AGH Dyscyplina: Informatyka
Liczne, a zarazem ważne i trudne problemy inżynierskie wymagają uzyskania przybliżonego rozwiązania pewnego równania różniczkowego cząstkowego. Zważywszy na fakt, iż rozważane problemy generują często miliony niewiadomych, rozwiązanie takiego równania jest zwykle zadaniem wymagającym znacznej mocy obliczeniowej. W rezultacie, algorytmy o niskiej złożoności obliczeniowej są w tej dziedzinie co najmniej tak potrzebne, jak wydajny sprzęt. Używanie metod zapewniających wykładniczy spadek błędu, takich jak hp-adaptacyjna Metoda Elementów Skończonych pozwala w znacznym stopniu ograniczyć liczbę niewiadomych. Najczęstszym przypadkiem wykorzystania algorytmów adaptacyjnych są problemy zawierające jedną lub więcej osobliwości. Kolejny obszar badań w zakresie Metody Elementów Skończonych obejmuje prace nad ulepszeniem działania solwera rozwiązującego wygenerowany układ równań liniowych. Klasyczne solwery dostępne w środowisku naukowym i komercyjnym posiadają złożoność obliczeniową O(N3/2) dla problemów 2D oraz O(N2) dla problemów 3D, w przypadku stosowania siatek jednorodnych. N oznacza tu liczbę stopni swobody (niewiadomych). Stosowanie adaptacyjnej metody elementów skończonych pozwala znacznie zredukować czas obliczeń solwerów dokładnych. Zdefiniowanie, w oparciu o formalizm gramatyk grafowych, nowego solwera dla problemów adaptacyjnych, wykorzystującego wiedzę o strukturze siatki i gwarantującego w ten sposób złożoność obliczeniową O(N) zarówno dla dwóch, jak i trzech wymiarów pozwoliłoby na kilkukrotne przyspieszenie obliczeń względem dotychczas stosowanych metod. Wyodrębnienie niepodzielnych zadań pod postacią produkcji byłoby również niezwykle przydatne przy opracowaniu wydajnej wersji równoległej solwera. Obiecujący kierunek dalszych badań naukowych będą zapewne stanowić prace nad wykorzystaniem nowoczesnych architektur komputerowych takich jak procesory graficzne.
– Teza rozprawy:– Jako tezę niniejszej rozprawy doktorskiej autor przedstawia następujące twierdzenie:
Istnieje formalizm oparty o gramatyki hipergrafowe, za którego pomocą można opisać dokładny solwer wielofrontalny dla dwu- i trójwymiarowych problemów obliczeniowych z osobliwościami punktowymi, w formie przekształceń zwanych dalej produkcjami, które w prosty sposób pozwalają ustalić porządek wykonania tychże zadań, który gwarantuje liniowy koszt obliczeniowy w wypadku wykonania sekwencyjnego oraz logarytmiczny czas obliczeniowy w wyniku wykonania równoległego.
Niniejsza praca prezentuje nowy formalizm matematyczny, który za pomocą gramatyk hipergrafowych steruje wykonaniem adaptacyjnej Metody Elementów Skończonych dla siatek z osobliwościami punktowymi o dowolnym poziomie zagęszczenia siatki w stronę osobliwości. Rozprawa pokazuje, w jaki sposób wykorzystać szczególną dla problemów z osobliwościami punktowymi strukturę siatki, celem zmniejszenia złożoności obliczeniowej o cały rząd wielkości. Ponadto, zamodelowanie gramatykami hipergrafowymi solwera wielofrontalnego wspomaga wydajne zrównoleglenie, co skutkuje dodatkowym wzrostem wydajności. Modele hipergrafowe zostały w niniejszej rozprawie stworzone zarówno dla sekwencyjnej, jak i równoległej wersji solwera, w dwu i trzech wymiarach. Również proces generacji siatki został opisany produkcjami grafowymi. Dla obu wariantów rozwiązania zostały oszacowane teoretyczne koszta wykonania oraz zużycie pamięci. Modele teoretyczne zostały zaimplementowane na CPU i GPU, a wydajność implementacji porównana z wiodącym obecnie solwerem MUMPS (MUltifrontal Massively Parallel sparse direct Solver). Pomiary wydajności zostały zebrane dla problemów dwu- i trójwymiarowych, z jedną lub wieloma osobliwościami punktowymi oraz dla kilku różnych stopni aproksymacji wielomianowej. Rezultaty te zostały również porównane z oszacowaniami teoretycznymi.
Ważniejsze publikacje doktoranta: