Czy dzisiejsze masywne równoległe jednostki przetwarzania są w stanie efektywnie uruchamiać automaty komórkowe?

Zastanawiam się, czy obecnie masowo równoległe jednostki obliczeniowe dostępne w kartach graficznych ( na przykład programowalne w OpenCL ) są wystarczająco dobre, aby skutecznie symulować automaty komórkowe 1D (a może automaty komórkowe 2D?).

Jeśli wybierzemy dowolną skończoną siatkę, która mieści się w pamięci układu, czy możemy oczekiwać, że jedno przejście zdefiniowanego na tej siatce automatu komórkowego będzie obliczane w (quasi) stałym czasie?

Zakładam, że automaty komórkowe 2D wymagałyby większej przepustowości do komunikacji między różnymi częściami układów niż automaty 1D.

Byłbym zainteresowany tym samym pytaniem w przypadku programowania FPGA lub niestandardowych układów.

Doskonałe pytanie. Uważam, że odpowiedź brzmi tak.

Ewolucja automatu komórkowego jest zasadniczo równoważna z wykonaniem obliczeń matrycowych. Na niektórych siatkach 1D, 2D lub 3D kolejne wartości punktów (lub komórek) są obliczane na podstawie ostatniej wartości sąsiedztwa punktu. W prostym 1D CA to sąsiedztwo może być komórką i dwiema komórkami po lewej i prawej stronie. Istnieje wiele przykładów obliczeń wzorników wykonywanych na GPU; Pakiet testowy SHOC firmy ORNL dla OpenCL / CUDA zawiera na przykład szablon 2D.

Podstawową ideą jest, aby każdy wątek otrzymał lokalną kopię sąsiedztwa dla kilku punktów, a następnie obliczał kolejne wartości dla punktów określonych przez to sąsiedztwo. Odpowiednio wykorzystując hierarchię pamięci np. W CUDA (rejestry, współużytkowane, stałe, tekstury i pamięci globalne) oraz model przetwarzania SIMT (np. Odpowiednio obliczając funkcję przejścia bez wprowadzania nadmiernej rozbieżności wypaczenia), można osiągnąć dobrą wydajność.

Ta odpowiedź byłaby o wiele lepsza, gdybym dał przykład, ale jestem teraz zbyt zajęty, aby napisać jakikolwiek kod ... Ale teoretycznie myślę, że powinna być wykonalna efektywna symulacja CA na GPU poprzez modelowanie ich według szablonu obliczenia. Jednak wiele rozważań należy poświęcić na napisanie dobrego obliczenia szablonowego dla GPU.

Cokolwiek zrobisz, obliczenie następnego stanu dla automatu komórkowego wymaga tyle obliczeń, ile jest komórek w automacie. Zatem, aby uzyskać stały czas, potrzebujesz tyle rdzeni obliczeniowych, ile jest komórek.

Ich liczba w GPU wynosi obecnie najwyżej kilka tysięcy, podczas gdy obliczenie następnego stanu jest tak proste, że spodziewam się, że wynik będzie związany z IO, tj. Możesz uzyskać bardzo dobre przybliżenie czasu potrzebnego po prostu biorąc pod uwagę potrzebny jest ruch danych (a jeśli nie jest to dobre przybliżenie, albo implementacja jest nieefektywna, albo architektura nie jest odpowiednia, ale byłoby to bardzo zaskakujące).

W przypadku FPGA pytanie jest trudniejsze i prawdopodobnie będzie zależeć od dostępnej kombinacji pamięci i jednostek obliczeniowych. Jeśli nie jestem zbyt daleko, nie będziesz mieć wystarczającej ilości pamięci, aby wszystkie jednostki były zajęte, a jeśli polegasz na pamięci zewnętrznej, jesteś na tym samym miejscu co GPU, przepustowość pamięci będzie czynnikiem ograniczającym, a ja nie zdziw się, jeśli wniosek będzie taki, że nie ma przewagi nad GPU. (Pamiętaj, że chociaż pracowałem z FPGA, to było lata temu, teraz mogą istnieć modele FPGA z odpowiednim miksem).

ASIC oferuje większą elastyczność. Możesz łatwo mieć implementację skurczową (ale przy dwukierunkowym przepływie danych, niektóre skurczowe są zwykle ograniczone do jednokierunkowego przepływu danych), każda fizyczna komórka jest jedna logiczna: bit pamięci i logika potrzebna do obliczenia jej następnego stanu i jest ułożona tak że to fizyczny sąsiad jest logiczny. Jesteście oczywiście w stałym świecie. W zależności od tego, jakie masz twarde makra, lepiej być nieco mniej oczywistym i mieć fizyczne komórki, które przegrupowują kilka logicznych. Celem jest maksymalizacja tego, co dzieje się w jednym układzie, innymi słowy, aby zminimalizować komunikację z zewnętrznym układem, gdy tylko potrzeby w zakresie komunikacji będą proporcjonalne do liczby komórek, nastąpi ograniczenie przepustowości. Tak, oznacza to, że jeśli musisz spojrzeć na wszystkie komórki dla każdego kroku, prawdopodobnie nie jesteś dużo lepszy niż z GPU. (Pełne niestandardowe zapewniałoby tylko lepszą integrację, tj. Więcej komórek na chip).

Podsumowanie: - jeśli chcesz spojrzeć na wszystkie stany pośrednie, GPU jest najbardziej skutecznym podejściem - jeśli nie, potrzebujesz głośności, aby uzasadnić, że ASIC ma coś lepszego, FPGA prawdopodobnie nie zapewni wystarczającej przewagi, jeśli masz jakieś.

Zastanawiam się, czy masowo równoległe jednostki obliczeniowe dostępne obecnie w kartach graficznych są wystarczająco dobre, aby skutecznie symulować automaty komórkowe 1D (a może automaty komórkowe 2D?).

ogólnie mówiąc, tak, obliczenia na GPU to najlepsza alternatywa dla standardowego sprzętu dostępna dla wszystkich.

Bardziej szczegółowo; teoretycznie, zgodnie z modelem PRAM, koszt za krok czasowy rzeczywiście wynosi , już o tym wiesz. Jednak GPU różni się nieco od PRAM, ponieważ dostęp do pamięci kosztuje więcej i jest podzielony na różne hierarchie (należy rozważyć model PMH dla dokładniejszej analizy teoretycznej). Ponadto wątki działają w grupach lub wypaczeniach , są to obliczenia blokujące, które postępują w sposób SIMD. Model programowania GPU działa z koncepcją grid (CUDA) lub przestrzeni roboczejn ≤ P n P O ( 1 $O(1)$(OpenCL), który jest praktycznie mapowaniem 1-do-1 w przestrzeni obliczeniowej automatów komórkowych. Jest to kluczowa funkcja pozwalająca zidentyfikować i zrozumieć, że procesory graficzne są przyjazne dla urzędów certyfikacji. Szczegóły techniczne: jeśli rozbieżność wypaczenia jest traktowana poprawnie (zastępując warunek if-else zamkniętymi wyrażeniami matematycznymi), dostępy do pamięci są łączone i ( liczba komórek i liczba procesorów), to można powiedzieć, że obliczenia złożoność jest rodzajem .$n \le P$$n$$P$$O(1)$

po stronie FPGA i ASIC wiem, że prowadzone są badania nad budowaniem fizycznego CA jako siatki bramek logicznych ze stanami, wszystkie połączone przez sąsiadów; tj . macierze skurczowe . Chodzi o to, aby nie używać już pamięci globalnej, ale polegać na stanach każdego węzła w siatce. Maszyna tego typu byłaby rewolucyjna, ponieważ odtąd moglibyśmy przestać mówić o komputerze symulującym urząd certyfikacji i zacząć mówić o urzędzie certyfikacji działającym jako komputer (niektóre urzędy są w pełni gotowe).