Jak poradzić sobie z brakiem asocjatywności liczbowej w celu redukcji równoległej?

Równoległa redukcja zakłada, że ​​odpowiednia operacja jest asocjacyjna. Założenie to jest naruszone przy dodawaniu liczb zmiennoprzecinkowych. Możesz zapytać, dlaczego mi na tym zależy. Cóż, sprawia, że ​​wyniki są mniej powtarzalne. I staje się gorzej, gdy symulowane wyżarzanie jest używane do optymalizacji (lub dopasowania parametrów) w stosunku do podprogramów, dających takie niepowtarzalne wyniki.

Jakie są typowe sposoby radzenia sobie z tym problemem? Co można powiedzieć o następujących strategiach?

• Nie przejmuj się odtwarzalnością.
• Nie używaj redukcji równoległej z liczbami zmiennoprzecinkowymi i dodawaniem.
• Twórz pakiety robocze o odpowiednich rozmiarach w powtarzalny sposób i ręcznie dokonaj ostatecznej redukcji.
• Dodaj większą precyzję (ale nie wszystkie kompilatory oferują zmiennoprzecinkowe typy o wyższej precyzji).

Redukcja wprowadzona przy użyciu MPI_Allreduce() jest odtwarzalna, o ile używasz tej samej liczby procesorów, pod warunkiem, że implementacja przestrzega następującej uwagi w sekcji 5.9.1 standardu MPI-2.2.

Porady dla realizatorów . Zdecydowanie zaleca MPI_REDUCEsię implementację, aby uzyskać ten sam wynik za każdym razem, gdy funkcja jest stosowana do tych samych argumentów, pojawiających się w tej samej kolejności. Należy pamiętać, że może to uniemożliwić optymalizacje wykorzystujące fizyczną lokalizację procesorów. ( Koniec porady dla wdrażających .)

Jeśli chcesz zagwarantować odtwarzalność za wszelką cenę, możesz postępować zgodnie z wytycznymi w następnym akapicie:

Porady dla użytkowników . Niektóre aplikacje mogą nie być w stanie zignorować niesocjacyjnego charakteru operacji zmiennoprzecinkowych lub mogą wykorzystywać operacje zdefiniowane przez użytkownika (patrz rozdział 5.9.5), które wymagają specjalnego polecenia redukcji i nie mogą być traktowane jako asocjacyjne. Takie aplikacje powinny wyraźnie egzekwować kolejność oceny. Na przykład w przypadku operacji wymagających ścisłej kolejności oceny od lewej do prawej (lub od prawej do lewej) można to zrobić poprzez zebranie wszystkich operandów w jednym procesie (np. Za pomocą MPI_GATHER), stosując operację redukcji w pożądanej kolejności (np. z MPI_REDUCE_LOCAL) i, jeśli to konieczne, transmituj lub rozpraszaj wynik do innych procesów (np. z MPI_BCAST). ( Koniec porady dla użytkowników ).

W szerszym schemacie rzeczy wydajne algorytmy dla większości aplikacji wykorzystują lokalizację. Ponieważ algorytm jest naprawdę inny, gdy działa na innej liczbie procesów, po prostu nie jest praktyczne dokładne odtwarzanie wyników, gdy jest uruchamiany na innej liczbie procesów. Możliwym wyjątkiem jest układ wielosieciowy z tłumionym wygładzaczem Jacobiego lub wielomianowy (np. Czebiszew), w którym możliwe jest bardzo dobre działanie tej prostej metody.

Przy tej samej liczbie procesów często korzystne jest przetwarzanie wiadomości w kolejności ich odbierania (np. Za pomocą MPI_Waitany() ), co wprowadza niedeterminizm. W takich przypadkach można zaimplementować dwa warianty: szybki, który odbiera w dowolnej kolejności, i „debugujący”, który odbiera w kolejności statycznej. Wymaga to napisania wszystkich bazowych bibliotek, aby oferowały takie zachowanie.

W celu debugowania w niektórych przypadkach można wyodrębnić część obliczeń, która nie zapewnia tego powtarzalnego zachowania, i wykonać ją nadmiarowo. W zależności od sposobu zaprojektowania komponentów zmiana ta może być niewielką ilością kodu lub być bardzo uciążliwa.

W większości odpowiadam na odpowiedź Jeda. Istnieje jednak inne wyjście: biorąc pod uwagę rozmiar normalnych liczb zmiennoprzecinkowych, możesz zapisać każdą liczbę w około 4000 bitowej liczbie stałoprzecinkowej. Jeśli więc zredukujesz liczbę zmiennoprzecinkową w ten sposób osadzoną, otrzymasz dokładne obliczenie, bez względu na skojarzenie. (Przepraszam, nie mam odniesienia do tego, kto wpadł na ten pomysł).

Możesz zaimplementować stabilny numerycznie algorytm redukcji w MPI tak samo, jak w przypadku szeregowym. Oczywiście może wystąpić hit wydajności. Jeśli możesz sobie pozwolić na replikację wektora, po prostu użyj MPI_Gather i wykonaj liczbowo stabilną redukcję numeru seryjnego w katalogu głównym. W niektórych przypadkach wydajność może nie być wielkim problemem.

Innym rozwiązaniem jest użycie szerokich akumulatorów, jak opisano tutaj . Możesz to zrobić z MPI jako redukcją definiowaną przez użytkownika, chociaż zużyje on znacznie większą przepustowość.

Kompromisem dla powyższego jest użycie sumowania kompensowanego. Szczegółowe informacje można znaleźć w odnośnikach „Podsumowanie Kahana”. „ Dokładność i stabilność algorytmów numerycznych ” Highama jest doskonałym źródłem na ten temat.

Aby rozwiązać ten problem w kontekście wątków w systemie pamięci współdzielonej, napisałem tę stronę, która wyjaśnia, co robimy w transakcji. II: http://dealii.org/developer/doxygen/deal.II/group__threads.html #MTWorkStream

Chciałbym zauważyć, że zamiast używać arytmetyki o wyższej precyzji do dodawania, istnieje możliwość zastosowania sumowania kompensowanego (patrz [1]). Może to zwiększyć dokładność sumowania bez konieczności uciekania się do większych typów danych.

[1] Higham, NJ Dokładność sumowania zmiennoprzecinkowego. SIAM Journal on Scientific Computing 14, 783–799 (1993).