Streszczenie - Daragan Taras Gennadievich - Optymalizacja operacji komunikacyjnych sterowania wysokością tonu w równoległych algorytmach symulacyjnych

1. 1 OGÓLNY OPIS PRACY 1.1 Znaczenie tematu
2. 1.2 Połączenie pracy z programami naukowymi, planami, tematami
3. 1.3 Ustalenie problemu badawczego
4. 2 ANALITYCZNE BADANIE NA BADANIACH
5. 2.2 Przegląd źródeł krajowych
6. 3 METODY BLOKU DO ROZWIĄZANIA SODA
7. 3.2 Kanoniczne schematy kolokacji wielostopniowych metod blokowych
8. WNIOSEK
9. WYKAZ UŻYWANEJ LITERATURY

1 OGÓLNY OPIS PRACY

1.1 Znaczenie tematu

Obecnie jedną z najbardziej popularnych i skutecznych metod badania złożonych systemów dynamicznych jest modelowanie komputerowe, które charakteryzuje szerokie zastosowanie równoległych systemów obliczeniowych o różnych architekturach, tworzenie matematycznych metod organizowania obliczeń równoległych, rozwój równoległych metod i algorytmów do rozwiązywania różnych klas problemów, opracowywanie metod i oprogramowania środki do automatycznej równoległości programu dla systemów wieloprocesorowych. Największe zapotrzebowanie na skuteczne metody równoległe powstaje podczas modelowania obiektów dynamicznych o skupionych parametrach, które są opisane przez układy równań różniczkowych zwyczajnych.

W prawdziwym życiu potrzeba przetwarzania równoległego wynika z postępu potrzeby (złożoności) obliczania prędkości istniejących systemów komputerowych w celu rozwiązywania problemów w takich obszarach jak:

• modelowanie klimatu;
• inżynieria genetyczna;
• projektowanie układów scalonych;
• analiza zanieczyszczenia środowiska;
• wirtualny projekt;
• tworzenie leków itp.

Ponieważ zadania te, a są to głównie zadania na dużą skalę, nakładają zwiększone i specyficzne wymagania dotyczące wydajności przetwarzania informacji, istnieje potrzeba wydajnej strukturalnej i algorytmicznej implementacji obliczeń równoległych. Uzyskanie rozwiązania wymaganej kolejności dokładności metodami numerycznymi może wymagać znacznej liczby iteracji. Dlatego wśród najważniejszych prac nad rozwojem teorii modelowania matematycznego i komputerowego warto podkreślić równoległość obliczeń, tworzenie nowych metod obliczeniowych i algorytmów mających na celu efektywne wykorzystanie w systemach wieloprocesorowych.

Pomimo wyników szeroko zakrojonych badań w dziedzinie obliczeń równoległych, praca w tym kierunku nie traci na znaczeniu i wymaga dalszego rozwoju ze względu na masowy rozkład komputerów równoległych.

Tak jak poprzednio, główną przeszkodą we wdrażaniu prawie wszystkich systemów równoległych jest brak skutecznych stosowanych metod równoległych. Powyższe problemy decydują o kierunku pracy magisterskiej, poświęconej aktualnym zagadnieniom efektywnej organizacji strukturalnej i algorytmicznej obliczeń równoległych, opracowaniu i uzasadnieniu metod rozwiązywania szerokiej klasy problemów dynamicznych z parametrami skupionymi. Znaczenie pracy wynika z powszechnego wprowadzenia komputerów równoległych o wysokiej wydajności w przedsiębiorstwach i organizacjach na Ukrainie.

1.2 Połączenie pracy z programami naukowymi, planami, tematami

Główne badania na temat pracy magisterskiej przeprowadzono w Departamencie PMI Państwowej Wyższej Szkoły w DonNTU w ramach badań nad budżetowymi tematami badań podstawowych, zatwierdzonymi przez MES Ukrainy: D-15-02 „Metody algorytmiczne dla zwiększenia wydajności równoległych systemów komputerowych w rozwiązywaniu problemów dynamicznych”.

Badania nad tematem pracy prowadzone są również przez międzynarodową organizację World Scientific and Engineering Academy and Society w ramach międzynarodowej konferencji International Conference on Applied, Numerical and Computational Mathematics.

1.3 Ustalenie problemu badawczego

Celem pracy jest zbadanie i opracowanie algorytmów sterowania krokiem i kolejnością integracji podczas rozwiązywania sztywnych systemów opartych na równoległych metodach kolokacji z generowaniem współczynników metody o określonej kolejności dokładności w celu uzyskania maksymalnej rzeczywistej wydajności.

Aby osiągnąć ten cel, konieczne jest rozwiązanie następujących głównych zadań:

• analiza istniejących metod i algorytmów do równoległej symulacji wysokowymiarowych systemów dynamicznych w celu zidentyfikowania nowych podejść do poprawy wydajności ich wdrażania;
• teoretyczne uzasadnienie podejść do optymalizacji operacji komunikacyjnych sterowania pitch w równoległych algorytmach symulacyjnych;
• restrukturyzacja znanych algorytmów sekwencyjnych dla numerycznego rozwiązania układów równań różniczkowych zwyczajnych;
• badanie możliwości i cech odbicia zrestrukturyzowanych algorytmów na równoległych systemach obliczeniowych SIMD (pojedyncza instrukcja wielu danych) i MIMD (wielokrotna instrukcja wielu danych) typów o różnych charakterystykach topologicznych, typy pamięci w celu uzyskania maksymalnej rzeczywistej wydajności;
• opracowanie algorytmów sterowania dla kroku i kolejności integracji podczas rozwiązywania sztywnych systemów opartych na równoległych metodach kolokacji z generowaniem współczynników metody o określonej kolejności dokładności.

Przedmiotem badań są procesy operacji komunikacyjnych kontrolujących krok i kolejność integracji w rozwiązywaniu trudnych problemów w równoległych algorytmach symulacyjnych w systemach komputerowych o podstawowych charakterystykach topologicznych.

Przedmiotem badań są równoległe metody numeryczne do rozwiązywania problemów dynamicznych z parametrami skupionymi dla układów równań różniczkowych zwyczajnych, które zapewniają wzrost wydajności wieloprocesorowych systemów obliczeniowych.

Metody badawcze. Rozwiązanie problemów sformułowanych w pracy magisterskiej opiera się na podstawowych zasadach teorii równań różniczkowych zwyczajnych, teorii systemów obliczeniowych i obliczeń równoległych, a także teorii grafów. Implementacja oprogramowania opiera się na wykorzystaniu technologii obliczeniowych, a mianowicie: programowania obiektowego, standardu OpenMP i biblioteki przesyłania komunikatów MPI. Aby zweryfikować wyniki, dobrze znane dokładne rozwiązania są używane jako referencyjne, aw przypadku ich braku stosowane są rozwiązania uzyskane znanymi metodami o porównywalnej dokładności.

Nowość naukowa jest następująca:

• nowe podejścia do optymalizacji operacji komunikacyjnych sterowania pitch w równoległych algorytmach symulacyjnych;
• równoległe algorytmy sterowania krokowego do rozwiązywania twardych systemów w oparciu o równoległe zagnieżdżone metody fazowane.

Wartość praktyczna polega na zwiększeniu efektywności wykorzystania równoległych systemów obliczeniowych przy rozwiązywaniu problemów dynamicznych o dużych wymiarach z parametrami skupionymi. Oczekiwane algorytmy sterowania wysokością i integracją podczas rozwiązywania twardych systemów z generowaniem współczynników o określonej kolejności dokładności przyspieszą rozwiązanie trudnych problemów z lokalną kontrolą błędów na równoległych systemach obliczeniowych SIMD (pojedyncze instrukcje wielu danych) i typy MIMD (wiele instrukcji wielu danych) [ 18 ] o różnych charakterystykach topologicznych, typach pamięci. Oczekuje się, że opracowane metody minimalizują zasoby obliczeniowe przy rozwiązywaniu układów równań różniczkowych.

2 ANALITYCZNE BADANIE NA BADANIACH

2.1 Przegląd źródeł międzynarodowych

W [ 1 ] Autorzy badania zaproponowali równoległy algorytm do rozwiązywania dużych systemów ODE opartych na 2-punktowej metodzie blokowej, która wykazała wyższość równoległości w całym systemie przy stosowaniu problemów o dużej skali. Wyniki liczbowe pokazują, że prędkość wzrasta wraz ze wzrostem wielkości zadania.

W [ 2 ] opisuje autora skonstruowane implicite schematy ekstrapolacji oparte na symetrycznych metodach E z wyższymi pochodnymi, zbieżnymi z kolejnością 4, 6 lub 8, dla numerycznego rozwiązania równań różniczkowych zwyczajnych, które pozwalają znaleźć numeryczne rozwiązanie równań różniczkowych z określoną dokładnością iw krótkim czasie.

W artykule [ 3 ] opisuje zastosowanie podejścia kolokacji do uzyskiwania formuł niejawnych, liniowych, n-stopniowych metod blokowych k-punktów. Proponowana metoda blokowa określa metodę dziewiątego rzędu dokładności, jest A (α) -stabilna, α = 72,760.

2.2 Przegląd źródeł krajowych

Główne prace naukowe i artykuły mistrzów i nauczycieli DonNTU:

W pracach [ 4-5 ] opisuje nowe podejścia do rozwiązania problemu równoległej kontroli dokładności integracji w oparciu o zmianę długości kroku. Proponowane podejścia opierają się na zastosowaniu wieloetapowych metod blokowych kolokacji wielopunktowej o zmiennych wymiarach bloków odniesienia i bloków obliczeniowych z nierównomiernym rozmieszczeniem węzłów połączonych ze sobą przez niektóre współczynniki proporcjonalności.

W pracach [ 6-7 ] istnieją równoległe algorytmy sterowania dla etapu integracji do rozwiązywania sztywnych systemów opartych na jednokrokowych i wieloetapowych metodach kolokacji z wyższymi pochodnymi. W opracowanych algorytmach błędy lokalne są określane i porównywane we wszystkich punktach kolokacji bloku. Uzyskane charakterystyki równoległości świadczą o wysokich prędkościach opracowanych metod i możliwości uzyskania rozwiązania z określoną dokładnością.

W pracy badawczej [ 8 ] szczegółowo opisał wzrost wydajności modelowania przy użyciu komputerów równoległych poprzez zmniejszenie liczby wymian przy jednoczesnej numerycznej implementacji rozwiązania problemu Cauchy'ego do stosowania metod ekstrapolacji z kontrolą etapu integracji. Analizując wyniki eksperymentu, można zauważyć, że największe przyspieszenie wynikające z zastosowania predykcji fragmentacji kroku spada na obszar, w którym wydajność podstawowego algorytmu gwałtownie spada, a użycie dodatkowych węzłów obliczeniowych nie skraca czasu wykonywania programu.

W [ 10 ] przeprowadzono badanie schematów ekstrapolacji równoległej z automatyczną kontrolą stopnia i kolejności integracji, w wyniku czego dzięki zaproponowanym metodom udało się uzyskać przyspieszenie numerycznego rozwiązania wielowymiarowych problemów Cauchy'ego w oparciu o równoległe metody numeryczne o wysokiej precyzji przy 9 węzłach 4,5 razy.

3 METODY BLOKU DO ROZWIĄZANIA SODA

3.1 Metody integracji bloków

Główna idea [ 6 ], na której opiera się konstrukcja metod blokowych do rozwiązywania SODA na komputerach równoległych, polega na jednoczesnym uzyskiwaniu aproksymacji dokładnego rozwiązania w równoodległych punktach bloku [ 9 ]. Jednakże, jeśli mówimy o numerycznej integracji sztywnych równań różniczkowych, konieczna staje się zmiana kroku integracji, którego nie można zapewnić wewnątrz jednostki. Z jednej strony jest to wada metody, ale z drugiej strony, ponieważ punkty wewnątrz bloku są rozmieszczone regularnie (rys. 3.1), możliwe jest określenie i porównanie lokalnych błędów we wszystkich punktach bloku [ 7 ]. Jest to główna różnica między metodami blokowymi a metodami etapowymi, w których etapy z reguły nie pokrywają się, a porównanie przeprowadza się tylko w jednym końcowym punkcie projektu. Nie jest też szczególnie atrakcyjne stosowanie metod etapowych w komputerach z rozproszoną pamięcią o drobnoziarnistej równoległości.

Rysunek 3.1 - Szablon schematu obliczania metody blokowania

Algorytmy kontroli wysokości bazują na zastosowaniu jednoetapowego i wieloetapowego metody blokowania kolokacji [ 21 ]. Równoległe zliczanie odbywa się w ciągu jednego cyklu dla wszystkich punktów bloków o wymiarach s i + 1. Dwa wątki obliczeń przechodzą niezależnie, a potrzeba wymiany pojawia się dopiero po uzyskaniu ostatecznych wyników dla obu bloków punktów obliczeniowych.

3.2 Kanoniczne schematy kolokacji wielostopniowych metod blokowych

Metody kolokacji są oparte na wielomianach interpolacyjnych, których stopnie pokrywają się z liczbą punktów kolokacji [ 4 ], a wartości wielomianów w tych punktach pokrywają się z prawymi stronami równania różniczkowego w obliczonych punktach. Wykorzystanie zbioru punktów jednolitej siatki jako punktów kolokacji (rys. 3.2)

kanoniczna forma wielostopniowych metod blokowych kolokacji z liczbą punktów kontrolnych m i liczbą punktów obliczeniowych s [6, 13] jest reprezentowana jako

(1)

gdzie są przybliżone wartości rozwiązania problemu Cauchy'ego w punktach, i = 0,1, ... s,

τ to etap integracji,

- prawa strona równania w odpowiednich punktach j = (m-1), (m-2), ..., 0,1, ... s,

- współczynniki schematu projektowego.

Rysunek 3.2 - Schemat ustalania punktów odniesienia i punktów obliczeniowych

Aby rozróżnić obliczone i pożądane punkty, wprowadza się odpowiednie oznaczenia i są one przedstawione w postaci wektorów:

- wektor zliczonych punktów;

- wektor poszukiwanych punktów;

s, odpowiednio, prawa strona równania problemu Cauchy'ego w znanych i poszukiwanych punktach.

Oznaczono dodatkowo, że rozwiązanie w punkcie jest wektorem jednostkowym wymiaru s. Następnie w postaci wektorowej układ równań (1) ma postać

(2)

Aby rozpocząć obliczenia, należy wprowadzić zestaw wartości odniesienia, które można określić metodą jednoetapową, zapewniając wymaganą dokładność obliczeń

(3)

Następnie poszukiwanie rozwiązania numerycznego można zredukować do rozwiązania na każdym etapie nieliniowego układu równań (2), z sekwencyjnym określaniem wektorów U_1, U_2, .... Należy zauważyć, że każde równanie w (1) zawiera nieznane współczynniki m + s.

które można określić na podstawie warunków aproksymacji lub metodą interpolacji integro [ 22 ].

W pracach [ 11-12 ] stabilność tych metod została udowodniona na podstawie danych początkowych iz prawej strony, a dla nich również określono maksymalną kolejność aproksymacji, która jest wartością m + s. Po określeniu nieznanych współczynników i utworzeniu macierzy A i B z odpowiednimi wymiarami sxm i sxs, obliczenia metodą wielostopniowego bloku, przedstawione w postaci układu równań nieliniowych (1), są zredukowane do następującego procesu iteracyjnego

(4)

Przed rozpoczęciem rozwiązywania systemu (4) wartości wektora U0 (3) są określane w punktach odniesienia bloku początkowego. Obliczanie przybliżonych wartości rozwiązania problemu Cauchy'ego w każdym kolejnym bloku obliczeniowym jest wykonywane iteracyjnie (4). Wyznaczanie wartości początkowych w bloku obliczeniowym odbywa się na podstawie wielostopniowej metody Adamsa, która pozwala na zwiększenie dokładności wstępnego przybliżenia.

WNIOSEK

Analiza istniejących opracowań i publikacji [ 14-17 ] wskazuje, że prawie wszystkie obecnie znane metody numeryczne z automatycznym wyborem etapu integracji są oparte na obliczeniu głównego terminu błędu lokalnego i późniejszym wyborze tego rozmiaru dla następnego kroku, który jest maksymalny dla danej granicy dokładności lokalnej. Ale jednocześnie istnieje potrzeba powtarzania obliczeń w każdym punkcie, co prowadzi do znacznego wzrostu kosztów obliczeniowych. Aby rozwiązać ten problem, ma on stworzyć nowe metody blokowe do rozwiązywania układów równań różniczkowych zwyczajnych, które początkowo koncentrują się na architekturze równoległej.

Dalszy rozwój algorytmów sterowania dla kolejności kroków i integracji w rozwiązywaniu sztywnych systemów z generowaniem współczynników o określonej kolejności dokładności, w oparciu o zastosowanie jednoetapowego i wielostopniowego bloku kolokacji.

W momencie pisania tego tekstu praca magisterska nie jest jeszcze zakończona. Ostateczne zakończenie: kwiecień 2017 r. Pełny tekst pracy i materiałów na ten temat można uzyskać od autora lub jego menedżera po określonym terminie.

WYKAZ UŻYWANEJ LITERATURY

1. ODI używające MPI / [zasób elektroniczny]. - Dostęp do trybu: http://www.wseas.us/e-library/conferences/2010/Corfu/ASM/ASM-04.pdf
2. Na automatycznej kontroli długości w kierunku w jednym postępowaniu metodach kolokacji z wyższymi pochodnymi // G. Yu. Kulikov, E. Yu. Khrustaleva [zasób elektroniczny]. - Dostęp do trybu: http://www.mathnet.ru/links/3ef4bb6e9ad29c4663102b4aa12b5219/zvmmf4891.pdf
3. DA Tursunov. Budowanie jednoetapowej dziewięciopunktowej metody blokowej do sztywnych układów równań różniczkowych zwyczajnych // Tursunov D.A. [zasób elektroniczny]. - Dostęp do trybu: http://cyberleninka.ru/article/n/postroenie-odnoshagovogo-devyatitochechnogo-blochnogo-metoda-dlya-resheniya-zhestkih-sistem-obyknovennyh-differentsialnyh-uravneniy
4. Dmitrieva OA Równoległa precyzyjna kontrola na podstawie zmian wymiaru bloku // OA Dmitriev [zasób elektroniczny]. - Dostęp do trybu: http://irbis-nbuv.gov.ua
5. Dmitrieva OA Metody blokowania kolokacji z kontrolą na etapie // OA Dmitriev [zasób elektroniczny]. - Dostęp do trybu: http://www.hups.mil.gov.ua/periodic-app/article/12220/soi_2015_5_20.pdf
6. Metoda blokowania kolokacji // OA Dmitriev [Zasób elektroniczny]. - Dostęp do trybu: http://www.khai.edu/csp/nauchportal/Arhiv/REKS/2014/REKS514/Dmitriev.pdf
7. Dmitrieva OA Wysokowydajny algorytm sterowania krokowego na równoległych metodach blokowania kolokacji // OA Dmitriev [zasób elektroniczny]. - Dostęp do trybu: http://dspace.nbuv.gov.ua/xmlui/bitstream/handle/123456789/57699/7-Dmitrieva.pdf?sequence=1
8. Dmitriyeva OA Optymalizacja operacji komunikacyjnych za pomocą Croc Kerwanniana w równoległych algorytmach ekstrapolarnych // OA Dmitriyev [zasób elektroniczny]. - Dostęp do trybu: http://irbis-nbuv.gov.ua
9. Dmitriva OA Parallel ізниціві metodi raz'yaznya zadachi Kosh. - Donieck: DonNTU, 2011. - 256 p.
10. Kulakov VV Poprawa skuteczności rozwiązywania wielowymiarowych problemów Cauchy'ego w oparciu o równoległe metody numeryczne o wysokiej precyzji // V.V. Kułakow [zasób elektroniczny]. - Dostęp do trybu: http://masters.donntu.org/2013/fknt/kulakov/diss/index.htm
11. Dmitrieva, O. A. Rozwój i uzasadnienie stabilności równoległych metod modelowania systemów dynamicznych z wprowadzeniem kolokacji [Text] / O. A. Dmitrieva // Artificial Intelligence. - 2014. - № 3 (61). - str. 488–494.
12. Dmitriva, O. A Równoległe modelowanie obiektów dynamicznych według parametrów koncentracji [Tekst] // O. A Dmitriva. - Charków: „Knowlej”. - 2014 r. - 336 p.
13. Verzhbitsky V.M. Podstawy metod numerycznych. M.: Wyżej. Szkoła, 2005. - 848 p.
14. Hayrer E. Rozwiązanie równań różniczkowych zwyczajnych. Nierówne problemy // E. Heirer, S. Nersett, G. Vanner: Trans. z angielskiego - M.: Mir, 1990. - 512s.
15. Projektowanie architektury komputera równoległego // [zasób elektroniczny]. - Dostęp do trybu: http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=328
16. Równoległe formuły różnicowania wstecznego do rozwiązywania równań różniczkowych zwyczajnych // [zasób elektroniczny]. - Dostęp do trybu: http://waset.org/publications/7693/parallel-block-backward-differeniation-formulas-for-solving-ordinary-differential-equations
17. Równoległe programy do numerycznego rozwiązania problemów Kosha: monografie // L.P. Feldman, I.A. Nazarow. - Donieck: DVNZ DonNTU, 2011. - 185 str.: Л.
18. Voevodin V.V. Metody opisywania i klasyfikowania systemów komputerowych. Moskwa: MGU, Izd-vl, 1994. - 79 p.
19. Gergel V.P. Teoria i praktyka obliczeń równoległych. Intuit; Binom. LZ., 2007. - 423 s.
20. Kumar V., Grama A., Gupta A., Karypis G. Wprowadzenie do obliczeń równoległych. - The Benjamin / Cummings Publishing Company, Inc., 1994
21. Liczba metod różnicowania wywołań różnicowych w EOM // [zasób elektroniczny]. - Tryb dostępu: http://posibnyky.vntu.edu.ua/met/lek9.htm
22. Feldman L.P. Równoległe metody kolokacji do rozwiązywania problemu Cauchy'ego dla równań różniczkowych zwyczajnych // L.P. Feldman [zasób elektroniczny]. - Dostęp do trybu: http://masters.donntu.org/2008/fvti/zavalkin/library/feldman1/default.htm