728 x 90

Problemy obliczeń masowo równoległych

Problemy obliczeń masowo równoległych

W masowo równoległych obliczeniach pojawiają się pewne problemy z którymi nie mamy do czynienia w przypadku obliczeń sekwencyjnych. Rozważmy następująca sytuację, mamy n obiektów poruszających się w przestrzeni dwuwymiarowej. Obiekty w żaden sposób nie mogą na siebie wpływać i wchodzić w interakcje, więc każdy porusza się niezależnie od pozostałych. Załóżmy, że chcemy dokonać komputerowej symulacji takiego układu. Pierwszym aspektem, który musimy rozważyć jest nasze podejście do czasu. W rzeczywistym świecie czas jest ciągły, procesy zachodzą cały czas. Nie jest to jednak wygodny sposób przeprowadzania obliczeń komputerowych, dlatego często czas traktuje się jako wartość dyskretną. Obliczenia wykonuje się w kolejnych krokach czasowych symulacji, aż nie uzyskamy zadanego czasu symulacji. Jeśli krok czasowy jest dostatecznie mały (może mieć na przykład wartość w femtosekundach) takie uproszczenie nie odbiega za bardzo od rzeczywistości. Symulacje z takim podejściem do czasu określa się jako dyskretne.

Załóżmy, że chcemy przeprowadzić symulację naszego układu używając jednego węzła (np. procesora), czyli w sposób sekwencyjny. Wówczas nasz kod będzie mieć formę dwóch zagnieżdżonych pętli, jedna będzie przebiegać po ilości kroków czasowych, druga po ilości obiektów. Załóżmy następnie, że mamy n węzłów, które możemy użyć w naszej symulacji. Wówczas każdy węzeł może dokonać symulacji ruchu jednego obiektu. Patrząc na kod będziemy mieć tylko jedną pętlę po ilości kroków czasowych. Mamy więc bardzo duży zysk w czasie obliczeń.

Przedstawiony układ nie jest jednak zbyt realistyczny. W rzeczywistości obiekty mogą ze sobą oddziaływać. Załóżmy więc, że nasze obiekty, jeśli znajdą się w pewnej odległości, odpychają się. Można je sobie wyobrazić na przykład jako dodatnio naładowane cząsteczki. Wówczas nasza symulacje nie będzie już tak prosta. Aby obliczyć kolejną pozycję obiektu, każdy węzeł będzie musiał wziąć pod uwagę pozycję innych obiektów, aby wyznaczyć te z którymi on oddziałuje i uwzględnić to w swoich obliczeniach. Przez to po obliczeniu pozycji swojego obiektu w danym kroku czasowym, węzeł będzie musiał poczekać, aż pozostałe zakończą swoje obliczenia dla tego kroku czasowego, aby mieć pewność, że użyje aktualnych pozycji innych obiektów w kolejnym kroku czasowym. Takie postępowanie nazywa się synchronizacją. Synchronizacja wprowadza jednak opóźnienia, czas obliczeń wydłuża się w stosunku do przypadku, kiedy węzły nie musiały na siebie czekać, ponieważ dodaje się do niego czas czekania. W masowo równoległych obliczeniach na tysiącach czy nawet milionach węzłów są to już znaczne wartości.

Co możemy zrobić w takiej sytuacji? A gdyby tak pominąć synchronizację, pozwolić węzłom wykonywać swoje obliczenia, mając nadzieję, że dane na których są one przeprowadzane są już aktualne. W przypadku, kiedy okaże się, że naruszona została zależność danych, czyli do obliczeń użyto niewłaściwych wartości, wówczas wycofać przeprowadzone od tamtej pory obliczenia. Podejście takie nazywa się optymistycznym. Przeciwnym do niego jest podejście konserwatywne, podejście optymistyczne daje jednak zazwyczaj lepszy wyniki – krótsze czasy symulacji. Wymaga ono jednak odwracania obliczeń, co przez długi czas stanowiło problem. Aktualnie, dzięki algorytmowi Time Wrap oraz narzędziu Backstroke metoda ta jest bardzo wydajna i uzyskuje bardzo dobre wyniki w benchmarkach.

Algorytm Time Warp to algorytm optymistycznej, równoległej i dyskretnej symulacji zdarzeń. W algorytmie używane są następujące elementy:

  • obiekty, które reprezentują rzeczywiste, symulowane obiekty
  • zdarzenia, które oznaczają egzekucję metody obiektu w danym czasie symulacji
  • lokalny czas wirtualny (LVT) – każdy obiekt posiada własny LVT, który określa czas symulacji do którego dotarł obiekt
  • wiadomości – obiekty przesyłają między sobą wiadomości, które zawierają zdarzenia, czyli jaka akcja ma być wykonana wraz z momentem, czasem w którym powinna ona być wykonana. O wiadomościach więcej poniżej.
  • dwie kolejki wiadomości – wejściową i wyjściową, wejściowa zawiera wiadomości otrzymane przez obiekt, wyjściowa wiadomości jakie obiekt wysłał. Wiadomości posortowane są według czasu w nich zawartego.

Wiadomości mają dwa typy: pozytywne i negatywne wiadomości. Jedyną różnicą między nimi jest znak, pozostałe informacje w wiadomości są takie same. Negatywna wiadomość jest antywiadomością dla pozytywnej wiadomości i odwrotnie. Otrzymanie pozytywnej wiadomości oznacza, że dane zdarzenie ma być wykonane. Otrzymanie negatywnej oznacza, że odpowiadająca jej pozytywna wiadomość powinna być anulowana, że została ona wysłana z naruszeniem integralności danych i jeśli zdarzenie w niej zawarte zostało już wykonane to powinno być ono wycofane.

Jak działa algorytm? Obiekty wykonują kolejne zdarzenia zawarte w wiadomościach z kolejki wejściowej. W ten sposób ich LVT posuwają się do przodu, np. jeśli obiekt ma właśnie wykonać zdarzenia z wiadomości oznaczonej czasem symulacji 100 to znaczy, że LVT tego obiektu jest 100. Jeśli obiekt wysyła jakieś wiadomości to ich kopie trafiają do jego kolejki wyjściowej. Gdy obiekt otrzyma nową pozytywną wiadomość z czasem symulacji większym niż jego aktualne LVT to wiadomość po prostu umieszczana jest we właściwym miejscu w kolejce wejściowej (czyli w części kolejki jeszcze nie przetworzonej przez obiekt, kolejka posortowana jest według czasu symulacji) i gdy obiekt dojdzie do jej czasu symulacji to zawarte w niej zdarzenie zostanie wykonane. Jeśli obiekt otrzyma negatywną wiadomość z czasem symulacji większym niż jego LVT to również umieszcza ją w swojej kolejce wejściowej w odpowiednim miejscu w nieprzetworzonej części. Jeśli w kolejce tej znajduje się już pozytywna wiadomość odpowiadająca otrzymanej antywiadomości to obie one się znoszą i są usuwane z kolejki. Jeśli pozytywnej wiadomości w kolejce jeszcze nie ma negatywna wiadomość po prostu „czeka” na nadejście jej pozytywnej odpowiedniczki, bo wiadomo, że taka przybędzie, aby obie mogły zostać usunięte. W takiej sytuacji obiekt pomija negatywną wiadomość przy przetwarzaniu kolejki, jeśli dojdzie do tego miejsca i przesuwa się do następnej wiadomości.

Ciekawsza sytuacja ma miejsce, kiedy obiekt otrzyma wiadomość (pozytywną lub negatywną) z czasem symulacji mniejszym niż jego LVT – czyli z czasem z „przeszłości” obiektu. Co oznacza taka sytuacja? W przypadku wiadomości pozytywnej znaczy to, że obiekt pominął pewną operację, którą powinien wykonać w przeszłości. Obliczenia, które zaszły potem mogą być niewłaściwe, ze względu na pominiętą operację, przez co powinny być wycofane, aż do momentu kiedy LVT osiągnie wartość w otrzymanej wiadomości. Dla wszystkich wiadomości, które zostały wysłane w tym czasie trzeba również wysłać wiadomości negatywne, aby inne obiekty mogły wycofać swoje obliczenia, które być może były wykonane ze złymi danymi – można to zrobić używając kolejki wyjściowej. LVT obiektu zmniejsza się na wartość zawartą w otrzymanej wiadomości i kolejne zdarzenia z kolejki wejściowej są przetwarzane.

Gdy obiekt otrzyma wiadomość negatywną z czasem symulacji mniejszym niż jego LVT znaczy to, że wykonał on już w przeszłości obliczenie z błędnymi danymi. Błędna była operacja opisana przez pozytywny odpowiednik otrzymanej, negatywnej wiadomości. Obiekt musi więc wycofać wszystkie obliczenia, które zaszły od tego momentu, włącznie z błędną operacją, która to zostaje całkowicie usunięta z kolejki wejściowej. Towarzyszy temu, tak jak wyżej, wysłanie negatywnych wiadomości odpowiadających wiadomościom wysłanym w czasie wycofywanych obliczeń. LVT obiektu się zmniejsza i znowu przystępuje on do przetwarzania zdarzeń z kolejki wejściowej.

Algorytm Time Warp opisuje więc ogólną ideę działania podczas optymistycznych masowo równoległych symulacji, ze szczególnym naciskiem na komunikację między obiektami. Wymaga on jednak możliwości wycofywania obliczeń. W sytuacji wycofywania obliczeń, obiekt musi nie tylko wysłać negatywne wiadomości, ale również wykonać obliczenie odwrotne do tych które chce wycofać. Przez długi czas właśnie to odwracanie obliczeń było przeszkodą i przyczyną małej popularności algorytmu. Problem rozwiązuje narzędzie Backstroke.

Backstroke umożliwia generowanie odwracalnego kodu C++ dla prawie każdego wejściowego kodu C++. Działa on na zasadzie „do przodu-do tyłu-zatwierdzenie” (forward-backward-commit). Oznacza to, że obliczenia mogą być swobodnie wykonywane i odwracane, aż do momentu kiedy nastąpi ich zatwierdzenie, wówczas odwrócenie nie jest już możliwe.

Jak działa Backstroke? Narzędzie działa na zasadzie zapisywania dodatkowych informacji, a dokładniej stanu obiektu, aby w razie potrzeby poprzedni, zapisany stan mógł być odtworzony. Dokładne obliczenia odwrotne nie są więc wykonywane, cofa się jedynie ich efekt poprzez przywrócenie sytuacji jaka miała miejsce przed ich wykonaniem. Wbrew temu co by się mogło wydawać, zapis takiego stanu wcale nie musi być skompilowany. Po chwili zastanowienia można dojść do wniosku, że zapamiętać trzeba tylko informacje dotyczące operacji powodujących zmiany w pamięci, a więc: przypisania (wszystkie w C++, między innymi ++, –, += itd.), alokacja i zwolnienie pamięci. Kod generowany przez Backstroke jest bardzo podobny do wejściowego. Dodane zostają do niego jedynie wywołania metod z bibliotek Backstroke, przy każdym przypisaniu, przydzieleniu i zwolnieniu pamięci.

W przypadku przypisania wystarczy zapamiętać adres zmiennej, której wartość się zmienia oraz jej starą wartość. Te dane wystarczą już, aby wycofać operację przypisania. W przypadku alokacji pamięci należy zachować adres początku przydzielanej pamięci oraz jej wielkość. To również są już dostateczne informacje, aby wycofać przydzielenie pamięci, czyli ją zwolnić. Najbardziej problematyczne jest zwolnienie pamięci. Jest to jedyna operacja, której nie można cofnąć, ponieważ gdy pamięć zostanie zwolniona nie można już do niej wrócić. Dlatego też należy wstrzymać operację zwalniania pamięci, a jedynie zachować o niej informację. W momencie cofania na podstawie zachowanej informacji wiadomo jaki obszar pamięci należy „przywrócić”. Rzeczywiste zwolnienie pamięci zachodzi dopiero w momencie zatwierdzenia (commit).

Zapisywanie dodatkowych informacji niesie ze sobą jednak pewne niebezpieczeństwo – ryzyko przepełnienia pamięci zapisanym stanami. Dlatego wprowadzono zatwierdzanie – podczas zatwierdzania obliczeń dodatkowe, zapisane informacje są usuwane. Obliczenia mogą być zatwierdzone tylko jeśli ma się pewność, że nie zostaną one już cofnięte. Kiedy taka sytuacja ma miejsce? Ogólnie można przyjąć, że cofnięte nie zostaną obliczenia z czasem symulacji mniejszym niż najmniejszy z LVT obiektów. Żaden z obiektów nie „zagląda” w swoje przeszłe obliczenia bez powodu. Robi to jedynie jeśli otrzyma wiadomość z czasem symulacji mniejszym niż jego LVT. Więc jeśli uwzględnić najmniejszy z LVT wraz z ewentualnym czasem potrzebnym do przekazania wiadomości mamy pewność, że wszystkie zdarzenia, które zaszły wcześniej nie mogą być już cofnięte. Te są więc zatwierdzane, a zapisane dla nich stany zostają zapomniane – w ten sposób pamięć jest zwalniana i nie ma problemu z jej przepełnieniem.

Backstroke jest to narzędzie uniwersalne i automatyczne, więc można się spodziewać, że niekoniecznie najbardziej wydaje. Badania pokazują, że bardziej wydajnie działa napisany ręcznie kod odwrotny. Wymaga to jednak czasu na jego napisanie, a testy pokazują, że o ile odwracanie obliczeń stanowi nie więcej niż 25% czasu obliczeń to użycie Backstroke jest opłacalne. W takiej sytuacji kod odwracalny nie musi być aż tak szybki. Poza tym, napisać kod odwracalny należałoby również dla wszystkich używanych bibliotek, jak np. standardowych biblioteki języka C++. A to może być już pracą ponad siły.

W artykule tym opisano jak poradzić sobie z masowo równoległymi symulacjami przy użyciu strategii optymistycznej, która to wymaga odwracania obliczeń. Backstroke może być znaleziony pod adresem: https://github.com/LLNL/backstroke. Współdziała on z symulatorem ROSE dostępnym na www.rosecompiler.org.

Powyższy tekst powstał na podstawie wykładu „Incremental State Saving for Optimistic Parallel Discrete Event Simulation”, autor: Markus Schordan.

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły