Mam kolekcję modeli obliczeniowych, które można opisać jako asynchroniczne automaty komórkowe. Modele te przypominają model Isinga, ale są nieco bardziej skomplikowane. Wydaje się, że takie modele skorzystałyby na GPU, a nie na CPU. Niestety równoległość takiego modelu nie jest łatwa i wcale nie jest dla mnie jasne, jak sobie z tym poradzić. Wiem, że istnieje literatura na ten temat, ale wszystko to wydaje się być skierowane do zapalonych informatyków, którzy są zainteresowani szczegółami złożoności algorytmicznej, a nie do kogoś takiego jak ja, który chce tylko opisu czegoś, co mogę zaimplementować, i w konsekwencji uważam, że jest to raczej nieprzeniknione.
Dla jasności nie szukam optymalnego algorytmu, a nie czegoś, co mogę szybko zaimplementować w CUDA, co może znacznie przyspieszyć moją implementację procesora. W tym projekcie czas programisty jest znacznie bardziej ograniczającym czynnikiem niż czas komputerowy.
Powinienem również wyjaśnić, że asynchroniczny automat komórkowy jest czymś innym niż synchroniczny, a techniki równoległego synchronicznego CA (takie jak życie Conwaya) nie mogą być łatwo dostosowane do tego problemu. Różnica polega na tym, że synchroniczny urząd certyfikacji aktualizuje każdą komórkę jednocześnie na każdym etapie, podczas gdy asynchroniczny aktualizuje losowo wybrany region lokalny na każdym etapie, jak opisano poniżej.
Modele, które chcę zrównoleglać, są zaimplementowane w sieci (zwykle heksagonalnej) składającej się z ~ 100000 komórek (choć chciałbym użyć ich więcej), a niesparalizowany algorytm ich uruchamiania wygląda następująco:
Wybierz losowo sąsiednią parę komórek
Oblicz funkcję „energii” na podstawie lokalnego sąsiedztwa otaczającego te komórki
Z prawdopodobieństwem zależnym od (z parametrem a) albo zamień stany dwóch komórek, albo nic nie rób. β
Powtórz powyższe kroki w nieskończoność.
Istnieją również pewne komplikacje związane z warunkami brzegowymi, ale wyobrażam sobie, że nie będą one stanowić dużego problemu dla równoległości.
Warto wspomnieć, że interesuje mnie przejściowa dynamika tych układów, a nie tylko stan równowagi, więc potrzebuję czegoś, co ma równoważną dynamikę do powyższych, a nie tylko czegoś, co zbliży się do tego samego rozkładu równowagi. (Więc odmiany algorytmu szachownicy nie są tym, czego szukam.)
Główną trudnością w równoległości powyższego algorytmu są kolizje. Ponieważ wszystkie obliczenia zależą tylko od lokalnego regionu sieci, wiele witryn sieci może być aktualizowanych równolegle, o ile ich sąsiedztwo się nie nakłada. Pytanie brzmi, jak uniknąć takiego nakładania się. Mogę wymyślić kilka sposobów, ale nie wiem, który z nich najlepiej wdrożyć. Są to:
Użyj procesora, aby wygenerować listę losowych witryn sieci i sprawdzić kolizje. Gdy liczba miejsc siatki jest równa liczbie procesorów GPU lub w przypadku wykrycia kolizji, wyślij każdy zestaw współrzędnych do jednostki GPU, aby zaktualizować odpowiednie miejsce sieci. Byłoby to łatwe do wdrożenia, ale prawdopodobnie nie dałoby większego przyspieszenia, ponieważ sprawdzanie kolizji na CPU prawdopodobnie nie byłoby o wiele tańsze niż wykonanie całej aktualizacji na CPU.
Podziel sieć na regiony (po jednej na jednostkę GPU) i niech jedna jednostka GPU odpowiada za losowy wybór i aktualizację komórek siatki w swoim regionie. Istnieje jednak wiele problemów z tym pomysłem, których nie umiem rozwiązać, najbardziej oczywistym jest to, co dokładnie powinno się zdarzyć, gdy jednostka wybierze dzielnicę pokrywającą się z krawędzią swojego regionu.
Przybliż system w następujący sposób: pozwól, aby czas przebiegał w dyskretnych krokach. Podziel sieć na innązestaw regionów na każdym etapie za każdym razem zgodnie z pewnym wstępnie zdefiniowanym schematem, a każda jednostka GPU losowo wybiera i aktualizuje parę komórek siatki, których sąsiedztwo nie zachodzi na granicę regionu. Ponieważ granice zmieniają się za każdym razem, ograniczenie to może nie wpływać zbytnio na dynamikę, o ile regiony są stosunkowo duże. Wydaje się to łatwe do wdrożenia i prawdopodobnie szybkie, ale nie wiem, jak dobrze będzie to przybliżać dynamikę, ani jaki jest najlepszy schemat wyboru granic regionu na każdym kroku. Znalazłem kilka odniesień do „blokowo-synchronicznych automatów komórkowych”, które mogą, ale nie muszą być takie same jak ten pomysł. (Nie wiem, ponieważ wydaje się, że wszystkie opisy metody są albo w języku rosyjskim, albo w źródłach, do których nie mam dostępu.)
Moje konkretne pytania są następujące:
Czy którykolwiek z powyższych algorytmów jest rozsądnym sposobem podejścia do równoległości GPU asynchronicznego modelu CA?
Czy jest lepszy sposób?
Czy istnieje kod biblioteki dla tego typu problemu?
Gdzie mogę znaleźć jasny anglojęzyczny opis metody „blokowo-synchronicznej”?
Postęp
Wydaje mi się, że wpadłem na pomysł równoległego asynchronicznego urzędu certyfikacji, który może być odpowiedni. Algorytm przedstawiony poniżej dotyczy normalnego asynchronicznego urzędu certyfikacji, który aktualizuje tylko jedną komórkę na raz, a nie sąsiednią parę komórek, tak jak moja. Istnieją pewne problemy z ogólnym uogólnieniem tego przypadku, ale myślę, że mam pomysł, jak je rozwiązać. Jednak nie jestem pewien, ile korzyści z prędkości przyniesie, z powodów omówionych poniżej.
Chodzi o to, aby zastąpić asynchroniczny CA (odtąd ACA) stochastycznym synchronicznym CA (SCA), który zachowuje się równorzędnie. Aby to zrobić, najpierw wyobrażamy sobie, że ACA jest procesem Poissona. Oznacza to, że czas płynie w sposób ciągły, a każda komórka jako stałe prawdopodobieństwo wykonania funkcji aktualizacji na jednostkę czasu, niezależnie od innych komórek.
Konstruujemy SCA, którego komórki przechowują dwie rzeczy: stan komórki (tj. Dane, które będą przechowywane w każdej komórce w implementacji sekwencyjnej) oraz liczbę zmiennoprzecinkową reprezentującą (ciągły ) godzina, o której nastąpi kolejna aktualizacja. Ten ciągły czas nie odpowiada etapom aktualizacji SCA. Odniosę się do tego drugiego jako do „czasu logicznego”. Wartości czasu są inicjowane losowo zgodnie z rozkładem wykładniczym: . (Gdzie jest parametrem, którego wartość można wybrać dowolnie.) t i j t i j ( 0 ) ∼ Exp ( λ ) λ
Na każdym logicznym etapie czasu komórki SCA są aktualizowane w następujący sposób:
Jeśli dla dowolnego sąsiedztwie , czas , nie rób nic.i , j t k l < t i j
W przeciwnym razie (1) zaktualizuj stan zgodnie ze stanami sąsiednich komórek, stosując tę samą regułę, co oryginalny ACA; i (2) wygeneruj losową wartość nazwa i zaktualizuj do . X k l Δ t ∼ Exp ( λ ) t i j t i j + Δ t
Wierzę, że to gwarantuje, że komórki zostaną zaktualizowane w kolejności, którą można „zdekodować”, aby odpowiadały pierwotnemu ACA, unikając kolizji i umożliwiając równoległą aktualizację niektórych komórek. Jednak ze względu na pierwszy punkt powyżej oznacza to, że większość procesorów GPU będzie w większości bezczynna na każdym kroku SCA, co jest mniej niż idealne.
Muszę się zastanowić, czy wydajność tego algorytmu można poprawić, i jak rozszerzyć ten algorytm, aby poradził sobie z przypadkiem, gdy wiele komórek jest aktualizowanych jednocześnie w ACA. Wygląda jednak obiecująco, więc pomyślałem, że opisałbym to tutaj na wypadek, gdyby ktokolwiek (a) wiedział o czymś podobnym w literaturze lub (b) mógł zaoferować wgląd w pozostałe kwestie.
exp()), więc nie sądzę, że rozłożenie go na wiele wątków ma sens. Myślę, że lepiej (i dla mnie łatwiej) jest spróbować zaktualizować wiele par równolegle, z jedną parą na wątek.