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

11

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ć:

Paweł
źródło
Proszę opisać strukturę komunikacji i związane z nią rozmiary. MPI_ScatterNastępnie MPI_Gathernie zapewniają tak samo jak komunikacja semantyczny MPI_Allgather. Być może występuje nadmiarowość przy wyrażaniu operacji w jakikolwiek sposób?
Jed Brown
Paul, Jed ma rację, miałeś na myśli MPI_Gathernastępujące po nim MPI_Bcast?
Aron Ahmadia
@JedBrown: Dodałem trochę więcej informacji.
Paweł
@AronAhmadia: Nie sądzę, że powinienem używać MPI_Bcast, ponieważ wysyłam część wektora do każdego procesu, a nie cały wektor. Moje uzasadnienie jest takie, że krótsza wiadomość będzie szybsza do wysłania niż większa. Czy to ma sens?
Paweł
Czy macierz jest już rozpowszechniana redundantnie? Czy jest to już uwzględnione? Czy wiele procesów korzysta z tych samych pamięci podręcznych i magistrali pamięci? (Wpłynęłoby to na szybkość rozwiązywania problemów z redundantnymi systemami.) Jak duże / drogie są systemy? Po co rozwiązywać szeregowo?
Jed Brown

Odpowiedzi:

9

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
źródło
To nie jest zły pomysł ... zmierzyć ich czas i ustalić, który z nich jest szybszy.
Paweł
Większość nowoczesnych środowisk HPC optymalizuje wiele połączeń MPI. Czasami prowadzi to do niesamowitych przyspieszeń, innym razem do wyjątkowo nieprzejrzystych zachowań. Bądź ostrożny!
meawoppl
@Jeff: Właśnie zdałem sobie sprawę, że pominąłem jeden ważny szczegół ... Pracuję z klastrem w Texas Advanced Computing Center, gdzie używają sieci topologii grubych drzew. Czy wpłynęłoby to na różnicę w wydajności między podejściami „wszystko zbieraj” i „zbieraj rozgłaszane”?
Paweł
@Paul Topologia nie jest tutaj dominującym czynnikiem, ale tłuste drzewo ma znaczną przepustowość bisekcji, co powinno sprawić, że wszystko to będzie tanie. Jednak zbieranie powinno zawsze być tańsze niż zebranie. W przypadku większych wiadomości może to być współczynnik nie większy niż 2.
Jeff
5

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ć.


źródło
Myślę, że bardziej interesuje mnie przenośność niż optymalizacja, ale zawsze jestem ciekawy, czy istnieje inna implementacja równie przenośna, ale szybsza :)
Paul