Jak porównuje się koszt obliczeniowy operacji mpi_allgather z operacją gromadzenia / rozpraszania?

Pracuję nad problemem, który można zrównoleglić za pomocą pojedynczej operacji mpi_allgather lub jednej operacji mpi_scatter i jednej operacji mpi_gather. Te operacje są wywoływane w pętli while, więc mogą być wywoływane wiele razy.

W implementacji ze schematem MPI_allgather zbieram wektor rozproszony dla wszystkich procesów w celu zduplikowanego rozwiązywania macierzy. W drugiej implementacji zbieram wektor rozproszony na jednym procesorze (węzeł główny), rozwiązuję układ liniowy na tym procesorze, a następnie rozpraszam wektor rozwiązania z powrotem na wszystkie procesy.

Jestem ciekawy, czy koszt operacji zbierania jest znacznie wyższy niż suma operacji rozproszenia i zbierania. Czy długość wiadomości odgrywa istotną rolę w jej złożoności? Czy różni się między implementacjami MPI?

Edytować:

Po pierwsze, dokładna odpowiedź zależy od: (1) użycia, tj. Argumentów wejściowych funkcji, (2) jakości i szczegółów implementacji MPI oraz (3) używanego sprzętu. Często (2) i (3) są powiązane, na przykład gdy dostawca sprzętu optymalizuje MPI dla swojej sieci.

Ogólnie rzecz biorąc, łączenie kolektywów MPI jest lepsze w przypadku mniejszych wiadomości, ponieważ koszty początkowe mogą być niepraktyczne, a synchronizacja związana z blokowaniem kolektywów powinna być zminimalizowana, jeśli występuje różnica w czasie obliczeń między rozmowami. W przypadku większych wiadomości celem powinno być zminimalizowanie ilości wysyłanych danych.

Na przykład, teoretycznie, MPI_Reduce_scatter_blockpowinno być lepsze niż MPI_Reducepóźniej MPI_Scatter, chociaż pierwsze jest często wdrażane w odniesieniu do drugiego, tak że nie ma realnej korzyści. Istnieje korelacja między jakością implementacji a częstotliwością użycia w większości implementacji MPI, a dostawcy oczywiście optymalizują te funkcje, dla których jest to wymagane w umowie maszynowej.

Z drugiej strony, jeśli ktoś jest na Blue Gene, robiąc MPI_Reduce_scatter_blockprzy użyciu MPI_Allreduce, których nie więcej niż komunikację MPI_Reducei MPI_Scatterpołączony jest rzeczywiście trochę szybciej. To jest coś, co niedawno odkryłem i jest to interesujące naruszenie zasady samoreformacji wydajności w MPI (zasada ta jest opisana bardziej szczegółowo w „Samowystarczalnych wytycznych dotyczących wydajności MPI” ).

W szczególnym przypadku scatter + gromadzenie kontra zbieranie weź pod uwagę, że w pierwszym przypadku wszystkie dane muszą przechodzić do i z jednego procesu, co czyni z niego wąskie gardło, podczas gdy w przypadku zbierania danych dane mogą wpływać i wychodzić ze wszystkich szeregów natychmiast , ponieważ wszystkie stopnie mają pewne dane do wysłania do wszystkich innych stopni. Jednak wysyłanie danych ze wszystkich węzłów jednocześnie niekoniecznie jest dobrym pomysłem w niektórych sieciach.

Wreszcie najlepszym sposobem na udzielenie odpowiedzi na to pytanie jest wykonanie następujących czynności w kodzie i udzielenie odpowiedzi na pytanie eksperymentalnie.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

Jeszcze lepszą opcją jest, aby Twój kod mierzył go eksperymentalnie podczas pierwszych dwóch iteracji, a następnie użyj tej, która jest szybsza dla pozostałych iteracji:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}

Jeff ma całkowitą rację, jeśli chodzi o jedyny sposób, aby upewnić się, że jest to pomiar - w końcu jesteśmy naukowcami, i to jest pytanie empiryczne - i daje doskonałą poradę, jak wprowadzić takie pomiary. Pozwólcie, że przedstawię teraz przeciwny (a może uzupełniający) pogląd.

Należy wprowadzić rozróżnienie między pisaniem powszechnie używanego kodu a dostosowaniem go do określonego celu. Ogólnie rzecz biorąc, robimy pierwszy - budujemy nasz kod, aby: a) można go używać na wielu różnych platformach, i b) kod można aktualizować i rozszerzać w nadchodzących latach. Ale czasami robimy coś innego - mamy roczną alokację na jakąś dużą maszynę i zwiększamy do pewnego wymaganego zestawu dużych symulacji i potrzebujemy pewnego poziomu wydajności, aby wykonać to, czego potrzebowaliśmy podczas czas przyznanego przydziału.

Kiedy piszemy kod, uczynienie go powszechnie użytecznym i łatwym w utrzymaniu jest o wiele ważniejsze niż zmniejszenie o kilka procent czasu wykonywania na konkretnej maszynie. W takim przypadku właściwą rzeczą jest prawie zawsze stosowanie procedury, która najlepiej opisuje to, co chcesz zrobić - jest to na ogół najbardziej specyficzne połączenie, jakie możesz wykonać, i robi to, co chcesz. Na przykład, jeśli prosty zbieracz lub zbieracz robi wszystko, co chcesz, powinieneś tego użyć zamiast wybierać własne operacje rozproszenia / sortowania. Powody są następujące:

• Kod teraz wyraźniej reprezentuje to, co próbujesz zrobić, dzięki czemu jest bardziej zrozumiały dla następnej osoby, która przyjdzie do Twojego kodu w następnym roku, nie mając pojęcia, co powinien zrobić kod (ta osoba może być tobą);
• Optymalizacje są dostępne na poziomie MPI dla tego bardziej konkretnego przypadku, którego nie ma w bardziej ogólnym przypadku, więc biblioteka MPI może ci pomóc; i
• Próba wyrzucenia własnego prawdopodobnie przyniesie odwrót; nawet jeśli działa lepiej na komputerze X z implementacją MPI Y.ZZ, może również działać znacznie gorzej po przejściu na inną maszynę lub aktualizacji implementacji MPI.

W tym dość powszechnym przypadku, jeśli okaże się, że jakiś kolektyw MPI działa nieuzasadnio wolno na twoim komputerze, najlepiej złożyć raport o błędzie u dostawcy MPI; nie chcesz komplikować własnego oprogramowania próbującego obejść kod aplikacji, co powinno zostać naprawione na poziomie biblioteki MPI.

Jednakże . Jeśli pracujesz w trybie „strojenia” - masz działający kod, musisz szybko uruchomić bardzo duże skale (np. Roczna alokacja) i profilujesz swój kod i odkryłem, że ta konkretna część twojego kodu jest wąskim gardłem, wtedy sensowne jest rozpoczęcie wykonywania tych bardzo specyficznych zmian. Mamy nadzieję, że nie będą to długoterminowe części kodu - najlepiej, że zmiany te pozostaną w określonej gałęzi repozytorium dla konkretnego projektu - ale być może będziesz musiał je wykonać. W takim przypadku kodowanie dwóch różnych podejść rozróżnianych przez dyrektywy preprocesora lub podejście „autotuning” dla określonego wzorca komunikacji - może mieć sens.

Więc nie zgadzam się z Jeffem, chcę tylko dodać kontekst, kiedy powinieneś być wystarczająco zainteresowany takimi względnymi pytaniami dotyczącymi wydajności, aby zmodyfikować kod, aby sobie z tym poradzić.