Mam openMP i MPI do mojej dyspozycji, i zastanawiałem się, czy ktoś natknął się na równoległą wersję algorytmu wypełniania powodzi (najlepiej w c). Jeśli nie, byłbym zainteresowany szkicami, jak to zrobić paralelizując - czy jest to możliwe, biorąc pod uwagę rekursję?Czy istnieje równoległe wdrożenie wlewu?
Wikipedia ma całkiem niezłe article, jeśli chcesz odświeżyć swoją pamięć na wypełnienia powodziowe.
Wielkie dzięki za pomoc.
Nie ma nic "z natury" rekursywnego w wypełnianiu powodzi, tylko po to, aby wykonać jakąś pracę, potrzebujesz informacji o wcześniej odkrytych "granicznych" komórkach. Jeśli myślisz o tym w ten sposób, oczywiste jest, że paralelizm jest wyjątkowo możliwy: nawet w przypadku pojedynczej kolejki można użyć czterech wątków (po jednym dla każdego kierunku), a jedynie przesunąć ogon kolejki, gdy komórka została zbadana przez każdą z nich. wątek. lub równoważnie, cztery kolejki. myśląc w ten sposób, można sobie nawet wyobrazić podział przestrzeni na wiele kolejek - być może podzielonych przez zakresy współrzędnych.
Jednym z podstawowych problemów jest to, że definicja problemu zwykle zawiera zastrzeżenie, że żadna komórka nigdy nie jest ponownie odwiedzana. oznacza to, że każdy pracownik potrzebuje aktualnej mapy, które komórki zostały uwzględnione (globalnie). Zmienna globalna informacja jest problematyczna, pod względem wydajności, chociaż nie jest trudno wymyślić sposoby ograniczenia konieczności globalnej propagacji aktualizacji ...