Wieloprocesorowość w Pythonie: zrozumienie logiki stojącej za `chunksize`

Question 1

Jakie czynniki decydują o optymalnym chunksizeargumencie do takich metod multiprocessing.Pool.map()? .map()Sposób wydaje się użycie dowolnego heurystyczne do domyślnej chunksize (jak opisano poniżej); co motywuje ten wybór i czy istnieje bardziej przemyślane podejście oparte na jakiejś konkretnej sytuacji / konfiguracji?

Przykład - powiedz, że jestem:

Przechodząc iterabledo .map()tego ma ~ 15 milionów elementów;
Praca na maszynie z 24 rdzeniami i używanie domyślnego processes = os.cpu_count()w ramach multiprocessing.Pool().

Moje naiwne myślenie to dać każdemu z 24 pracowników równej wielkości porcję, czyli 15_000_000 / 24625 000. Duże kawałki powinny zmniejszyć obroty / koszty ogólne przy pełnym wykorzystaniu wszystkich pracowników. Wydaje się jednak, że brakuje w tym pewnych potencjalnych wad dostarczania dużych partii każdemu pracownikowi. Czy to niekompletny obraz i czego mi brakuje?

Część mojego pytania wynika z domyślnej logiki dla if chunksize=None: both .map()i .starmap()call .map_async(), która wygląda tak:

def _map_async(self, func, iterable, mapper, chunksize=None, callback=None,
               error_callback=None):
    # ... (materialize `iterable` to list if it's an iterator)
    if chunksize is None:
        chunksize, extra = divmod(len(iterable), len(self._pool) * 4)  # ????
        if extra:
            chunksize += 1
    if len(iterable) == 0:
        chunksize = 0

Jaka jest logika divmod(len(iterable), len(self._pool) * 4)? Oznacza to, że rozmiar fragmentu będzie bliżej 15_000_000 / (24 * 4) == 156_250. Jaki jest zamiar pomnożenia len(self._pool)przez 4?

To sprawia, że wynikowy rozmiar fragmentu jest o współczynnik 4 mniejszy niż moja „naiwna logika” z góry, która polega po prostu na podzieleniu długości iteracji przez liczbę pracowników pool._pool.

Na koniec jest też ten fragment z dokumentacji Pythona, .imap()który dodatkowo napędza moją ciekawość:

chunksizeArgument jest taka sama jak ta wykorzystywana przez map() metody. W przypadku bardzo długich iteracji użycie dużej wartości for chunksizemoże sprawić, że zadanie zostanie ukończone znacznie szybciej niż użycie domyślnej wartości 1.

_{Powiązana odpowiedź, która jest pomocna, ale nieco zbyt ogólnikowa : Wieloprocesorowość w Pythonie: dlaczego duże porcje są wolniejsze? .}

Question 2

Krótka odpowiedź

Algorytm wielkości kawałków puli to heurystyka. Zapewnia proste rozwiązanie wszystkich możliwych do wyobrażenia scenariuszy problemów, które próbujesz upchnąć w metodach Pool. W konsekwencji nie można go zoptymalizować pod kątem żadnego konkretnego scenariusza.

Algorytm arbitralnie dzieli iterowalność na około cztery razy więcej fragmentów niż podejście naiwne. Więcej fragmentów oznacza większe obciążenie, ale większą elastyczność planowania. Jak ta odpowiedź pokaże, prowadzi to średnio do wyższego wykorzystania pracowników, ale bez gwarancji krótszego całkowitego czasu obliczeń dla każdego przypadku.

„Miło jest wiedzieć”, możesz pomyśleć, „ale w jaki sposób znajomość tego pomoże mi w rozwiązaniu moich konkretnych problemów z wieloprocesorowością?” Tak nie jest. Bardziej uczciwa krótka odpowiedź brzmi: „nie ma krótkiej odpowiedzi”, „przetwarzanie wieloprocesowe jest złożone” i „to zależy”. Obserwowany objaw może mieć różne źródła, nawet w przypadku podobnych scenariuszy.

Ta odpowiedź ma na celu przedstawienie podstawowych pojęć, które pomogą Ci uzyskać jaśniejszy obraz czarnej skrzynki planowania Pool. Próbuje również udostępnić kilka podstawowych narzędzi do rozpoznawania i unikania potencjalnych klifów, o ile są one związane z rozmiarem fragmentów.

Spis treści

Część I.

Definicje
Cele zrównoleglenia
Scenariusze równoległości
Ryzyko wielkości kawałka> 1
Algorytm wielkości części puli
Kwantyfikacja wydajności algorytmu

6.1 Modele

6.2 Harmonogram równoległy

6.3 Wydajność

6.3.1 Absolute Distribution Efficiency (ADE)

6.3.2 Względna efektywność dystrybucji (RDE)

część druga

Algorytm naiwny kontra pulę
Sprawdzenie autentyczności
Wniosek

Najpierw należy wyjaśnić kilka ważnych terminów.

1. Definicje

Kawałek

Fragment w tym miejscu jest udziałem iterableargumentu określonego w wywołaniu metody puli. W jaki sposób obliczana jest wielkość kawałka i jakie może to mieć skutki, jest tematem tej odpowiedzi.

Zadanie

Fizyczną reprezentację zadania w procesie roboczym pod względem danych można zobaczyć na poniższym rysunku.

Na rysunku pokazano przykładowe wywołanie pool.map(), wyświetlane wzdłuż linii kodu, pobranego z multiprocessing.pool.workerfunkcji, w której zadanie odczytane z pliku inqueuezostaje rozpakowane. workerjest podstawową funkcją główną w procesie MainThreadroboczym puli. func-Argument określone w basenie metodą będzie pasował tylko func-variable wewnątrz worker-function dla metod pojedynczych połączeń, jak apply_asynci dla imapz chunksize=1. Dla pozostałych metod-puli z chunksize-parametrem funkcja-przetwarzania funcbędzie funkcją-mapującą ( mapstarlub starmapstar). Ta funkcja odwzorowuje określony przez użytkownika funcparametr na każdym elemencie przesyłanego fragmentu iterowalnego (-> "map-task"). Czas, jaki to zajmuje, określa zadanierównież jako jednostka pracy .

Taskel

Podczas gdy użycie słowa „zadanie” dla całego przetwarzania jednej porcji jest dopasowywane przez kod wewnątrz multiprocessing.pool, nie ma wskazania, w jaki sposób pojedyncze wywołanie określonego przez użytkownika func, z jednym elementem porcji jako argumentem, powinno być o którym mowa. Aby uniknąć nieporozumień pojawiających się od nazywania konfliktów (myśleć maxtasksperchild-parameter dla puli za __init__-method), to odpowiedź będzie odnosić się do pojedynczych jednostek prac w ramach zadania jako taskel .

Taskel (od zadania + el ement) jest najmniejszą jednostką pracy w zadaniu . Jest to pojedyncze wykonanie funkcji określonej funcparametrem Pool-method, wywoływane z argumentami uzyskanymi z pojedynczego elementu przesyłanego fragmentu . Zadanie składa się z chunksize taskels .

Narzut równoległości (PO)

PO składa się z wewnętrznego narzutu Pythona i narzutu komunikacji między procesami (IPC). Narzut na zadanie w Pythonie obejmuje kod potrzebny do pakowania i rozpakowywania zadań oraz ich wyników. IPC-overhead wiąże się z konieczną synchronizacją wątków i kopiowaniem danych między różnymi przestrzeniami adresowymi (potrzebne są dwa kroki kopiowania: rodzic -> kolejka -> dziecko). Wielkość narzutu IPC zależy od systemu operacyjnego, sprzętu i rozmiaru danych, co utrudnia uogólnienia dotyczące wpływu.

2. Cele zrównoleglenia

Podczas korzystania z przetwarzania wieloprocesowego naszym ogólnym celem (oczywiście) jest zminimalizowanie całkowitego czasu przetwarzania wszystkich zadań. Aby osiągnąć ten ogólny cel, naszym celem technicznym musi być optymalizacja wykorzystania zasobów sprzętowych .

Niektóre ważne cele cząstkowe umożliwiające osiągnięcie celu technicznego to:

zminimalizować narzut związany z równoległością (najbardziej znany, ale nie sam: IPC )
wysokie wykorzystanie wszystkich rdzeni procesora
utrzymywanie ograniczonego użycia pamięci, aby zapobiec nadmiernemu stronicowaniu ( koszowaniu ) systemu operacyjnego

Na początku zadania muszą być wystarczająco ciężkie obliczeniowo (intensywne), aby odzyskać PO musimy zapłacić za zrównoleglenie. Trafność PO maleje wraz ze wzrostem bezwzględnego czasu obliczeń na zadanie. Lub, mówiąc na odwrót, im większy bezwzględny czas obliczeń na zadanie dla danego problemu, tym mniej istotna jest potrzeba zmniejszenia PO. Jeśli twoje obliczenia zajmą kilka godzin na zadanie, narzut IPC będzie znikomy w porównaniu. Głównym problemem jest tutaj zapobieganie bezczynnym procesom roboczym po rozproszeniu wszystkich zadań. Utrzymując wszystkie rdzenie obciążone, równolegle robimy tak dużo, jak to możliwe.

3. Scenariusze równoległości

Jakie czynniki określają optymalny argument wielkości chunksize dla metod takich jak multiprocessing.Pool.map ()

Głównym pytanym czynnikiem jest to, ile czasu obliczeń może się różnić w naszych pojedynczych zadaniach. Aby to nazwać, wybór optymalnego rozmiaru fragmentu jest określany przez współczynnik zmienności ( CV ) dla czasów obliczeń na zadanie.

Dwa skrajne scenariusze w skali, wynikające z zakresu tej zmienności, to:

Wszystkie zadania potrzebują dokładnie tego samego czasu obliczeń.
Zakończenie zadania może zająć kilka sekund lub dni.

Aby lepiej zapamiętać, będę odnosił się do tych scenariuszy jako:

Gęsty scenariusz
Szeroki scenariusz

Gęsty scenariusz

W gęstym scenariuszu pożądane byłoby rozprowadzenie wszystkich zadań jednocześnie, aby zminimalizować niezbędne IPC i przełączanie kontekstów. Oznacza to, że chcemy tworzyć tylko tyle fragmentów, ile jest procesów roboczych. Jak już wspomniano powyżej, waga PO rośnie wraz z krótszymi czasami obliczeń na Taskel.

Aby zapewnić maksymalną przepustowość, chcemy również, aby wszystkie procesy robocze były zajęte do czasu przetworzenia wszystkich zadań (bez bezczynnych pracowników). W tym celu rozproszone fragmenty powinny być równej wielkości lub zbliżone.

Szeroki scenariusz

Najlepszym przykładem dla szerokiego scenariusza byłby problem optymalizacji, w którym wyniki albo szybko się zbiegają, albo obliczenia mogą zająć godziny, jeśli nie dni. Zwykle nie jest przewidywalne, jaką mieszankę „lekkich zadań” i „ciężkich zadań” będzie zawierało zadanie w takim przypadku, dlatego nie zaleca się rozdzielania zbyt wielu zadań jednocześnie w zestawie zadań. Dystrybucja mniejszej liczby zadań na raz niż to możliwe oznacza zwiększenie elastyczności planowania. Jest to potrzebne, aby osiągnąć nasz cel cząstkowy, jakim jest wysokie wykorzystanie wszystkich rdzeni.

Gdyby Poolmetody były domyślnie całkowicie zoptymalizowane pod kątem scenariusza zagęszczonego, w coraz większym stopniu tworzyłyby nieoptymalne czasy dla każdego problemu znajdującego się bliżej scenariusza szerokiego.

4. Ryzyko wielkości kawałka> 1

Rozważmy ten uproszczony przykład pseudokodu, przedstawiający literaturę Wide Scenario , którą chcemy przekazać do metody puli:

good_luck_iterable = [60, 60, 86400, 60, 86400, 60, 60, 84600]

Zamiast rzeczywistych wartości udajemy, że widzimy potrzebny czas obliczeń w sekundach, dla uproszczenia tylko 1 minuta lub 1 dzień. Zakładamy, że pula ma cztery procesy robocze (na czterech rdzeniach) i chunksizejest ustawiona na 2. Ponieważ kolejność zostanie zachowana, fragmenty wysłane do pracowników będą następujące:

[(60, 60), (86400, 60), (86400, 60), (60, 84600)]

Ponieważ mamy wystarczającą liczbę pracowników, a czas obliczeń jest wystarczająco długi, możemy powiedzieć, że każdy proces roboczy otrzyma kawałek do pracy. (Nie musi to mieć miejsca w przypadku szybkiego wykonywania zadań). Dalej możemy powiedzieć, że całe przetwarzanie zajmie około 86400 + 60 sekund, ponieważ jest to najwyższy całkowity czas obliczeniowy dla fragmentu w tym sztucznym scenariuszu, a fragmenty rozprowadzamy tylko raz.

Rozważmy teraz tę iterowalną, która ma tylko jeden element zmieniający swoją pozycję w porównaniu z poprzednią iterowalną:

bad_luck_iterable = [60, 60, 86400, 86400, 60, 60, 60, 84600]

... i odpowiednie fragmenty:

[(60, 60), (86400, 86400), (60, 60), (60, 84600)]

Po prostu pech z sortowaniem naszego iterowalnego prawie dwukrotnie (86400 + 86400) naszego całkowitego czasu przetwarzania! Pracownik pobierający błędną (86400, 86400) porcję blokuje drugi ciężki Taskel w swoim zadaniu przed przekazaniem go jednemu z bezczynnych pracowników, którzy już skończyli (60, 60) porcje. Oczywiście nie ryzykowalibyśmy tak nieprzyjemnego wyniku, gdybyśmy byli nastawieni chunksize=1.

To jest ryzyko większych kawałków. Przy większych porcjach handlujemy elastycznością planowania przy mniejszych kosztach, aw przypadkach takich jak powyżej to zła umowa.

Jak zobaczymy w rozdziale 6. Ilościowe określanie wydajności algorytmu , większe fragmenty mogą również prowadzić do nieoptymalnych wyników dla scenariuszy zagęszczonych .

5. Algorytm wielkości części puli

Poniżej znajdziesz nieco zmodyfikowaną wersję algorytmu wewnątrz kodu źródłowego. Jak widać, odciąłem dolną część i zawinąłem ją w funkcję do obliczania chunksizeargumentu na zewnątrz. Zastąpiłem 4też factorparametrem i zleciłem len()wywołania.

# mp_utils.py

def calc_chunksize(n_workers, len_iterable, factor=4):
    """Calculate chunksize argument for Pool-methods.

    Resembles source-code within `multiprocessing.pool.Pool._map_async`.
    """
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    return chunksize

Aby upewnić się, że wszyscy jesteśmy na tej samej stronie, oto co divmodrobi:

divmod(x, y)jest funkcją wbudowaną, która zwraca (x//y, x%y). x // yjest dzieleniem piętra, zwracającym zaokrąglony w dół iloraz z x / y, natomiast x % yjest operacją modulo zwracającą resztę z x / y. Stąd np . divmod(10, 3)Powroty (3, 1).

Teraz, jeśli spojrzeć chunksize, extra = divmod(len_iterable, n_workers * 4), można zauważyć n_workerstutaj jest dzielnik yw x / yi mnożenie przez 4, bez dalszej regulacji poprzez if extra: chunksize +=1później, prowadzi do początkowego chunksize co najmniej cztery razy mniejsze (o len_iterable >= n_workers * 4) niż byłoby inaczej.

Aby zobaczyć efekt mnożenia przez 4wynik pośredniego rozmiaru fragmentu, rozważ następującą funkcję:

def compare_chunksizes(len_iterable, n_workers=4):
    """Calculate naive chunksize, Pool's stage-1 chunksize and the chunksize
    for Pool's complete algorithm. Return chunksizes and the real factors by
    which naive chunksizes are bigger.
    """
    cs_naive = len_iterable // n_workers or 1  # naive approach
    cs_pool1 = len_iterable // (n_workers * 4) or 1  # incomplete pool algo.
    cs_pool2 = calc_chunksize(n_workers, len_iterable)

    real_factor_pool1 = cs_naive / cs_pool1
    real_factor_pool2 = cs_naive / cs_pool2

    return cs_naive, cs_pool1, cs_pool2, real_factor_pool1, real_factor_pool2

Powyższa funkcja oblicza naiwny rozmiar chunksize ( cs_naive) i rozmiar chunksize pierwszego kroku algorytmu chunksize-Algorytm puli ( cs_pool1), a także rozmiar części dla całego algorytmu Pool ( cs_pool2). Następnie oblicza rzeczywiste współczynniki rf_pool1 = cs_naive / cs_pool1 i rf_pool2 = cs_naive / cs_pool2, które mówią nam, ile razy obliczone naiwnie rozmiary fragmentów są większe niż wewnętrzne wersje Puli.

Poniżej widać dwie figury utworzone na podstawie danych wyjściowych z tej funkcji. Rysunek po lewej stronie pokazuje tylko rozmiary fragmentów n_workers=4aż do iterowalnej długości 500. Prawa rysunek przedstawia wartości rf_pool1. W przypadku długości iterowalnej 16rzeczywistym współczynnikiem staje się >=4(for len_iterable >= n_workers * 4), a jego maksymalna wartość dotyczy 7długości iterowalnych 28-31. To ogromne odchylenie od pierwotnego czynnika, 4do którego algorytm zbiega się w przypadku dłuższych iteracji. „Dłuższy” jest tutaj względny i zależy od liczby określonych pracowników.

Pamiętaj, że rozmiar fragmentu cs_pool1nadal nie ma korekty -dostosowania extrado reszty z divmodzawartej w cs_pool2całym algorytmie.

Algorytm kontynuuje:

if extra:
    chunksize += 1

Teraz w przypadkach, tam jest przypomnieniem (an extraz divmod-operation), zwiększając chunksize o 1 oczywiście nie może wypracować dla każdego zadania. Przecież gdyby tak się stało, nie byłoby żadnej reszty.

Jak widać na poniższych rysunkach, „ dodatkowe traktowanie ” skutkuje tym, że rzeczywisty czynnik na rf_pool2razie zbiega się w kierunku 4od dołu, 4 a odchylenie jest nieco łagodniejsze. Odchylenie standardowe dla n_workers=4i len_iterable=500spada od 0.5233za rf_pool1do 0.4115na rf_pool2.

Ostatecznie zwiększenie chunksizeo 1 skutkuje tym, że ostatnie przesłane zadanie ma rozmiar len_iterable % chunksize or chunksize.

Bardziej interesujący i jak zobaczymy później, bardziej konsekwentny efekt dodatkowego traktowania można jednak zaobserwować dla liczby wygenerowanych fragmentów ( n_chunks). W przypadku dostatecznie długich iterowalnych algorytm n_pool2wielkości fragmentów puli ( na poniższym rysunku) ustabilizuje liczbę fragmentów na poziomie n_chunks == n_workers * 4. W przeciwieństwie do tego, naiwne algorytm (po początkowym beknięciem) prowadzi na przemian n_chunks == n_workersi n_chunks == n_workers + 1w długości iterowalny wzrasta.

Poniżej znajdziesz dwie ulepszone funkcje informacyjne dla Pool's i naiwnego algorytmu chunksize. Dane wyjściowe tych funkcji będą potrzebne w następnym rozdziale.

# mp_utils.py

from collections import namedtuple


Chunkinfo = namedtuple(
    'Chunkinfo', ['n_workers', 'len_iterable', 'n_chunks',
                  'chunksize', 'last_chunk']
)

def calc_chunksize_info(n_workers, len_iterable, factor=4):
    """Calculate chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    # `+ (len_iterable % chunksize > 0)` exploits that `True == 1`
    n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
    # exploit `0 == False`
    last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

Nie daj się zmylić prawdopodobnie nieoczekiwanym wyglądem calc_naive_chunksize_info. Wartość extrafrom divmodnie jest używana do obliczania rozmiaru fragmentu.

def calc_naive_chunksize_info(n_workers, len_iterable):
    """Calculate naive chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers)
    if chunksize == 0:
        chunksize = 1
        n_chunks = extra
        last_chunk = chunksize
    else:
        n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
        last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

6. Kwantyfikacja wydajności algorytmu

Teraz, po tym jak zobaczyliśmy, jak wynik Poolalgorytmu chunksize wygląda inaczej w porównaniu z wyjściem z naiwnego algorytmu ...

Jak sprawdzić, czy podejście Pool rzeczywiście coś poprawia ?
I co dokładnie to może coś być?

Jak pokazano w poprzednim rozdziale, w przypadku dłuższych iteracji (większej liczby zadań), algorytm wielkości kawałków puli w przybliżeniu dzieli iterowalność na cztery razy więcej fragmentów niż metoda naiwna. Mniejsze fragmenty oznaczają więcej zadań, a więcej zadań oznacza więcej narzutów związanych z równoległością (PO) , kosztem, który należy porównać z korzyściami wynikającymi ze zwiększonej elastyczności planowania (przypomnij sobie „Ryzyko rozmiaru fragmentów> 1” ).

Z raczej oczywistych powodów podstawowy algorytm chunksize-puli nie może ważyć elastyczności planowania względem zamówienia zakupu . Koszty IPC zależą od systemu operacyjnego, sprzętu i rozmiaru danych. Algorytm nie może wiedzieć, na jakim sprzęcie uruchamiamy nasz kod, ani nie ma pojęcia, ile czasu zajmie ukończenie zadania. Jest to heurystyka zapewniająca podstawową funkcjonalność dla wszystkich możliwych scenariuszy. Oznacza to, że nie można go zoptymalizować pod kątem żadnego konkretnego scenariusza. Jak wspomniano wcześniej, PO również staje się coraz mniejszym problemem wraz ze wzrostem czasu obliczeń na zadanie (korelacja ujemna).

Kiedy przypomnisz sobie cele równoległości z rozdziału 2, jednym z punktów było:

wysokie wykorzystanie wszystkich rdzeni procesora

Wspomnianym wcześniej czymś , co algorytm chunksize-algorytmu puli może próbować ulepszyć, jest minimalizacja bezczynnych procesów roboczych , odpowiednio wykorzystanie rdzeni procesora .

Powtarzające się pytanie na temat SO dotyczące SO multiprocessing.Pooljest zadawane przez ludzi zastanawiających się nad nieużywanymi rdzeniami / bezczynnymi procesami roboczymi w sytuacjach, w których można oczekiwać, że wszystkie procesy robocze są zajęte. Chociaż może to mieć wiele powodów, bezczynne procesy robocze pod koniec obliczenia są obserwacją, której często możemy dokonać, nawet w przypadku scenariuszy zagęszczonych (równe czasy obliczeń na zadanie) w przypadkach, gdy liczba pracowników nie jest dzielnikiem liczby z kawałków ( n_chunks % n_workers > 0).

Teraz pytanie brzmi:

Jak praktycznie możemy przełożyć nasze rozumienie chunksizes na coś, co pozwoli nam wyjaśnić obserwowane wykorzystanie pracowników, a nawet porównać skuteczność różnych algorytmów w tym zakresie?

6.1 Modele

Aby uzyskać głębszy wgląd tutaj, potrzebujemy formy abstrakcji równoległych obliczeń, która upraszcza zbyt złożoną rzeczywistość do możliwego do zarządzania stopnia złożoności, zachowując jednocześnie znaczenie w określonych granicach. Taka abstrakcja nazywana jest modelem . Implementacja takiego „ modelu równoległości” (PM) generuje metadane (znaczniki czasu) odwzorowane na mapie roboczej, tak jak zrobiłyby to rzeczywiste obliczenia, gdyby dane były gromadzone. Metadane wygenerowane przez model pozwalają przewidywać metryki obliczeń równoległych pod pewnymi ograniczeniami.

Jednym z dwóch podmodeli w ramach zdefiniowanego tutaj PM jest Model Dystrybucji (DM) . DM wyjaśnia jak atomowy jednostki pracy (taskels) są rozmieszczone równolegle pracowników i czasie , gdy nie ma innych czynników niż odpowiednia chunksize algorytm, liczba pracowników, the-iterable wejściowego (liczba taskels) oraz czas ich trwania obliczeń jest uważany . Oznacza to, że nie obejmuje żadnych kosztów ogólnych .

W celu uzyskania pełnego PM , DM jest rozszerzany o model narzutów (OM) , reprezentujący różne formy narzutów równoległych (PO) . Taki model musi być skalibrowany indywidualnie dla każdego węzła (zależności sprzętowe, OS). Jak wiele form napowietrznych są reprezentowane w OM pozostaje otwarte i tak wielu OMs o różnym stopniu złożoności może istnieć. O tym, jaki poziom dokładności potrzebuje zaimplementowana OM, decyduje całkowita waga PO dla konkretnego obliczenia. Krótsze zadania prowadzą do większej wagi PO , co z kolei wymaga bardziej precyzyjnego OMgdybyśmy próbowali przewidzieć wydajność równoległości (PE) .

6.2 Harmonogram równoległy (PS)

Równoległe harmonogram jest dwuwymiarową reprezentacją równoległych obliczeniach, gdzie oś x reprezentuje czas, a oś y przedstawia basen pracowników równoległych. Liczba pracowników i całkowity czas obliczeń oznaczają zasięg prostokąta, w którym są rysowane mniejsze prostokąty. Te mniejsze prostokąty reprezentują atomowe jednostki pracy (taskels).

Poniżej znajduje się wizualizacja PS narysowana z danymi z algorytmu chunksize DM of Pool dla scenariusza gęstego .

Oś X jest podzielona na równe jednostki czasu, gdzie każda jednostka oznacza czas obliczeń wymagany przez zadanie.
Oś Y jest podzielona na liczbę procesów roboczych używanych przez pulę.
W tym miejscu pasek zadań jest wyświetlany jako najmniejszy prostokąt w kolorze cyjan, umieszczony na osi czasu (harmonogramie) anonimowego procesu roboczego.
Zadanie to jeden lub wiele zadań na osi czasu pracownika, które są stale podświetlane tym samym odcieniem.
Jednostki czasu biegu jałowego są reprezentowane przez kafelki w kolorze czerwonym.
Harmonogram równoległy jest podzielony na sekcje. Ostatnia sekcja to sekcja ogonowa.

Nazwy skomponowanych części można zobaczyć na poniższym obrazku.

W kompletnym PM zawierającym OM , Idling Share nie ogranicza się do ogona, ale obejmuje również przestrzeń między zadaniami, a nawet między zespołami zadań.

6.3 Wydajność

Przedstawione powyżej modele pozwalają na ilościowe określenie stopnia wykorzystania pracowników. Możemy wyróżnić:

Distribution Efficiency (DE) - obliczana za pomocą DM (lub uproszczonej metody dla Scenariusza Gęste ).
Wydajność równoległości (PE) - obliczana za pomocą skalibrowanego PM (predykcja) lub obliczana na podstawie metadanych rzeczywistych obliczeń.

Należy zauważyć, że obliczone wydajności nie korelują automatycznie z szybszymi ogólnymi obliczeniami dla danego problemu z równoległością. Wykorzystanie pracownika w tym kontekście rozróżnia jedynie między pracownikiem mającym rozpoczęty, ale niedokończony Taskel a pracownikiem nieposiadającym takiego „otwartego” zadania. Oznacza to, że ewentualna praca na biegu jałowym w czasie zadania nie jest rejestrowana.

Wszystkie wyżej wymienione wydajności uzyskuje się w zasadzie przez obliczenie ilorazu podziału Busy Share / Parallel Schedule . Różnica między DE i PE polega na tym, że zajęty udział zajmuje mniejszą część ogólnego harmonogramu równoległego dla wydłużonego narzutu PM .

Ta odpowiedź będzie dalej omawiać tylko prostą metodę obliczania DE dla gęstego scenariusza. Jest to wystarczające, aby porównać różne algorytmy wielkości fragmentów, ponieważ ...

... DM jest częścią PM , która zmienia się wraz z różnymi zastosowanymi algorytmami rozmiaru fragmentu.
... Gęsty Scenariusz z równymi czasami trwania obliczeń na zadanie przedstawia „stan stabilny”, w którym te przedziały czasowe wypadają z równania. Każdy inny scenariusz prowadziłby po prostu do losowych wyników, ponieważ kolejność zadań miałaby znaczenie.

6.3.1 Absolute Distribution Efficiency (ADE)

Tę podstawową efektywność można ogólnie obliczyć, dzieląc zajęty udział przez cały potencjał harmonogramu równoległego :

Absolute Distribution Efficiency (ADE) = Busy Share / Parallel Schedule

W przypadku scenariusza zagęszczonego uproszczony kod obliczeniowy wygląda następująco:

# mp_utils.py

def calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Absolute Distribution Efficiency (ADE).

    `len_iterable` is not used, but contained to keep a consistent signature
    with `calc_rde`.
    """
    if n_workers == 1:
        return 1

    potential = (
        ((n_chunks // n_workers + (n_chunks % n_workers > 1)) * chunksize)
        + (n_chunks % n_workers == 1) * last_chunk
    ) * n_workers

    n_full_chunks = n_chunks - (chunksize > last_chunk)
    taskels_in_regular_chunks = n_full_chunks * chunksize
    real = taskels_in_regular_chunks + (chunksize > last_chunk) * last_chunk
    ade = real / potential

    return ade

Jeśli nie ma na biegu jałowym Share , Busy akcji będzie równa do Parallel Harmonogram , stąd otrzymujemy ADE 100%. W naszym uproszczonym modelu jest to scenariusz, w którym wszystkie dostępne procesy będą zajęte przez cały czas potrzebny do przetworzenia wszystkich zadań. Innymi słowy, cała praca jest efektywnie równoległa do 100 procent.

Ale dlaczego ciągle odnoszę się do PE jako absolutnego PE ?

Aby to zrozumieć, musimy wziąć pod uwagę możliwy przypadek chunksize (cs), który zapewnia maksymalną elastyczność planowania (również liczbę górali, jaka może być. Zbieg okoliczności?):

__________________________________ ~ JEDEN ~ __________________________________

Jeśli na przykład mamy cztery procesy robocze i 37 zadań, będą bezczynni pracownicy nawet z chunksize=1, tylko dlatego, że n_workers=4nie jest dzielnikiem 37. Pozostała część z dzielenia 37/4 wynosi 1. Ten pojedynczy pozostały Taskel będzie musiał być przetwarzane przez jednego pracownika, podczas gdy pozostałe trzy są na biegu jałowym.

Podobnie, nadal będzie jeden bezczynny pracownik z 39 zadaniami, jak widać na poniższym obrazku.

Porównując górny harmonogram równoległy dla chunksize=1z wersją poniżej dla chunksize=3, zauważysz, że górny harmonogram równoległy jest mniejszy, a oś czasu na osi x krótsza. Powinno stać się teraz oczywiste, jak większe fragmenty nieoczekiwanie mogą również prowadzić do zwiększenia ogólnego czasu obliczeń, nawet w przypadku scenariuszy gęstych .

Ale dlaczego nie wykorzystać po prostu długości osi X do obliczeń wydajności?

Ponieważ narzut nie jest zawarty w tym modelu. Będzie różna dla obu rozmiarów fragmentów, stąd oś X nie jest bezpośrednio porównywalna. Narzut może nadal prowadzić do dłuższego całkowitego czasu obliczeń, jak pokazano w przypadku 2 na poniższym rysunku.

6.3.2 Względna efektywność dystrybucji (RDE)

Wartość ADE nie zawiera informacji, jeśli możliwa jest lepsza dystrybucja zadań z wielkością fragmentu ustawioną na 1. Lepiej tutaj nadal oznacza mniejszy udział na biegu jałowym .

Aby uzyskać wartość DE skorygowaną o maksymalny możliwy DE , musimy podzielić rozważane ADE przez ADE , dla którego otrzymujemy chunksize=1.

Względna efektywność dystrybucji (RDE) = ADE_cs_x / ADE_cs_1

Oto jak to wygląda w kodzie:

# mp_utils.py

def calc_rde(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Relative Distribution Efficiency (RDE)."""
    ade_cs1 = calc_ade(
        n_workers, len_iterable, n_chunks=len_iterable,
        chunksize=1, last_chunk=1
    )
    ade = calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk)
    rde = ade / ade_cs1

    return rde

RDE , jak tu zdefiniowano, jest w istocie opowieścią o ogonie równoległego harmonogramu . Na RDE wpływa maksymalny efektywny rozmiar kawałka znajdujący się w ogonie. (Ten ogon może mieć długość w osi X chunksizelub last_chunk.) To powoduje, że RDE naturalnie zbiega się do 100% (równo) dla wszelkiego rodzaju "ogonów", jak pokazano na poniższym rysunku.

Niski RDE ...

to mocna wskazówka dotycząca potencjału optymalizacji.
naturalnie staje się mniej prawdopodobne w przypadku dłuższych iteracji, ponieważ względna część końcowa ogólnego harmonogramu równoległego kurczy się.

Proszę znaleźć część II tej odpowiedzi tutaj .

Question 3

O tej odpowiedzi

Ta odpowiedź jest częścią II zaakceptowanej odpowiedzi powyżej .

7. Algorytm naiwny a algorytm wielkości puli

Zanim przejdziemy do szczegółów, rozważ dwa poniższe gify. Dla zakresu różnych iterabledługości pokazują, w jaki sposób dwa porównywane algorytmy dzielą przekazany fragment iterable(do tego czasu będzie to sekwencja) i jak mogą być rozdzielane wynikowe zadania. Kolejność pracowników jest losowa, a liczba rozdzielonych zadań na pracownika w rzeczywistości może różnić się od przedstawionych na tych obrazach dla lekkich zadań i / lub zestawów zadań w szerokim scenariuszu. Jak wspomniano wcześniej, nie uwzględniono tutaj również kosztów ogólnych. Jednak dla wystarczająco ciężkich zadań w gęstym scenariuszu z pomijalnymi rozmiarami przesyłanych danych, rzeczywiste obliczenia rysują bardzo podobny obraz.

cs_4_50

cs_200_250

Jak pokazano w rozdziale „ 5. Algorytm wielkości części puli ”, dzięki algorytmowi wielkości części puli liczba fragmentów ustabilizuje się n_chunks == n_workers * 4dla dostatecznie dużych elementów iteracyjnych, przy jednoczesnym przełączaniu między n_chunks == n_workersi n_chunks == n_workers + 1przy podejściu naiwnym. Dla algorytmu naiwnego Dotyczy: Bo n_chunks % n_workers == 1jest Trueza n_chunks == n_workers + 1nowy odcinek zostanie utworzony gdzie będzie zatrudniony tylko jeden pracownik.

Naiwny algorytm wielkości fragmentów:

Możesz pomyśleć, że utworzyłeś zadania dla tej samej liczby pracowników, ale będzie to prawdą tylko w przypadkach, w których nie ma reszty dla len_iterable / n_workers. Jeśli nie jest przypomnieniem, że będzie nowy odcinek z jednym tylko zadaniem dla pojedynczego pracownika. W tym momencie Twoje obliczenia nie będą już równoległe.

Poniżej widzisz rysunek podobny do pokazanego w rozdziale 5, ale wyświetlający liczbę sekcji zamiast liczby fragmentów. Dla pełnego algorytmu wielkości chunksize puli ( n_pool2) n_sectionsustabilizuje się na niesławnym, zakodowanym na stałe współczynniku 4. Dla naiwnego algorytmu, n_sectionsbędzie zmieniał się od jednego do dwóch.

W przypadku algorytmu wielkości kawałków puli stabilizacja n_chunks = n_workers * 4przez wspomnianą wcześniej dodatkową obróbkę zapobiega tworzeniu nowej sekcji w tym miejscu i ogranicza udział bezczynności do jednego pracownika przez wystarczająco długi czas iterowalny. Co więcej, algorytm będzie nadal zmniejszał relatywny rozmiar udziału na biegu jałowym , co prowadzi do zbliżenia wartości RDE do 100%.

„Długa na tyle” za n_workers=4to len_iterable=210na przykład. W przypadku iterowalnych równych lub większych niż to, udział na biegu jałowym będzie ograniczony do jednego pracownika, cecha pierwotnie utracona z powodu 4-mnożenia w algorytmie rozmiaru fragmentu.

Naiwny algorytm wielkości kawałków również zbliża się do 100%, ale robi to wolniej. Efekt zbieżności zależy wyłącznie od tego, że względna część ogona kurczy się w przypadkach, gdy będą dwie sekcje. Ten ogon z tylko jednym zatrudnionym pracownikiem jest ograniczony do długości osi X n_workers - 1, możliwej maksymalnej pozostałej części len_iterable / n_workers.

Czym różnią się rzeczywiste wartości RDE dla algorytmu naiwnego i algorytmu chunksize?

Poniżej znajdują się dwie mapy cieplne pokazujące wartości RDE dla wszystkich iterowalnych długości do 5000, dla wszystkich liczb pracowników od 2 do 100. Skala kolorów wynosi od 0,5 do 1 (50% -100%). Zauważysz znacznie więcej ciemnych obszarów (niższe wartości RDE) dla naiwnego algorytmu na lewej mapie cieplnej. W przeciwieństwie do tego algorytm wielkości kawałków Puli po prawej stronie rysuje znacznie bardziej słoneczny obraz.

Ukośny gradient ciemnych lewych dolnych rogów w porównaniu z prawymi górnymi jasnymi rogami ponownie pokazuje zależność od liczby pracowników w przypadku tego, co można nazwać „długim iterowalnym”.

Jak źle może się to stać z każdym algorytmem?

Z algorytmem chunksize puli wartość RDE 81,25% jest najniższą wartością dla zakresu pracowników i iterowalnych długości określonych powyżej:

Z naiwnym algorytmem wielkości fragmentów sytuacja może się znacznie pogorszyć. Najniższe obliczone RDE to 50,72%. W tym przypadku przez prawie połowę czasu obliczeń działa tylko jeden pracownik! Uważajcie więc, dumni właściciele Knights Landing . ;)

8. Sprawdzenie rzeczywistości

W poprzednich rozdziałach rozważaliśmy uproszczony model czysto matematycznego problemu dystrybucji, pozbawiony drobiazgowych szczegółów, które sprawiają, że przetwarzanie wieloprocesowe jest tak drażliwym tematem. Aby lepiej zrozumieć, jak daleko Distribution modelu (DM) sam może przyczynić się do wyjaśnienia obserwowanego wykorzystanie pracowników w rzeczywistości, będziemy teraz podjąć pewne spojrzenia na Parallel wykazach sporządzonych przez rzeczywistych obliczeniach.

Ustawiać

Poniższe wykresy dotyczą równoległych wykonań prostej, powiązanej z procesorem funkcji fikcyjnej, która jest wywoływana z różnymi argumentami, dzięki czemu możemy obserwować, jak narysowany harmonogram równoległy zmienia się w zależności od wartości wejściowych. „Praca” w ramach tej funkcji składa się tylko z iteracji po obiekcie zakresu. To już wystarczy, aby rdzeń był zajęty, ponieważ przekazujemy ogromne liczby. Opcjonalnie funkcja pobiera dodatkowe, unikalne dla zadań, dataktóre są po prostu zwracane niezmienione. Ponieważ każdy z zadań obejmuje dokładnie taką samą ilość pracy, nadal mamy tutaj do czynienia z gęstym scenariuszem.

Funkcja jest ozdobiona opakowaniem pobierającym znaczniki czasu o rozdzielczości ns (Python 3.7+). Znaczniki czasu są używane do obliczania przedziału czasu zadania, a tym samym umożliwiają rysowanie empirycznego harmonogramu równoległego.

@stamp_taskel
def busy_foo(i, it, data=None):
    """Dummy function for CPU-bound work."""
    for _ in range(int(it)):
        pass
    return i, data


def stamp_taskel(func):
    """Decorator for taking timestamps on start and end of decorated
    function execution.
    """
    @wraps(func)
    def wrapper(*args, **kwargs):
        start_time = time_ns()
        result = func(*args, **kwargs)
        end_time = time_ns()
        return (current_process().name, (start_time, end_time)), result
    return wrapper

Metoda Starmap Pool jest również udekorowana w taki sposób, że tylko samo wywołanie gwiezdnej gwiazdy jest mierzone w czasie. „Początek” i „koniec” tego wezwania określają minimum i maksimum na osi x utworzonego harmonogramu równoległego.

Będziemy obserwować obliczenia 40 zadań na czterech procesach roboczych na maszynie o następujących specyfikacjach: Python 3.7.1, Ubuntu 18.04.2, procesor Intel® Core ™ i7-2600K @ 3,40 GHz × 8

Wartości wejściowe, które będą się zmieniać, to liczba iteracji w pętli for (30k, 30M, 600M) oraz dodatkowo wielkość wysyłanych danych (na taskel, numpy-ndarray: 0 MiB, 50 MiB).

...
N_WORKERS = 4
LEN_ITERABLE = 40
ITERATIONS = 30e3  # 30e6, 600e6
DATA_MiB = 0  # 50

iterable = [
    # extra created data per taskel
    (i, ITERATIONS, np.arange(int(DATA_MiB * 2**20 / 8)))  # taskel args
    for i in range(LEN_ITERABLE)
]


with Pool(N_WORKERS) as pool:
    results = pool.starmap(busy_foo, iterable)

Pokazane poniżej przebiegi zostały starannie dobrane tak, aby miały taką samą kolejność fragmentów, dzięki czemu można lepiej dostrzec różnice w porównaniu z harmonogramem równoległym z modelu dystrybucji, ale nie zapominaj, że kolejność, w której pracownicy wykonują swoje zadania, jest niedeterministyczna.

DM Prediction

Powtarzając, model dystrybucji „przewiduje” równoległy harmonogram, jak widzieliśmy już wcześniej w rozdziale 6.2:

Pierwsze uruchomienie: 30 tys. Iteracji i 0 MiB danych na zadanie

Nasz pierwszy bieg tutaj jest bardzo krótki, zestawy zadań są bardzo „lekkie”. Całe połączenie pool.starmap()trwało łącznie tylko 14,5 ms. Zauważysz, że w przeciwieństwie do DM , praca na biegu jałowym nie ogranicza się do sekcji ogonowej, ale ma również miejsce między zadaniami, a nawet między zadaniami. Dzieje się tak, ponieważ nasz prawdziwy harmonogram obejmuje oczywiście wszystkie rodzaje kosztów ogólnych. Bezczynność tutaj oznacza po prostu wszystko poza zadaniami. Ewentualne rzeczywiste bezczynność podczas zadania nie jest uchwycone, jak już wspomniano wcześniej.

Dalej widać, że nie wszyscy pracownicy wykonują swoje zadania w tym samym czasie. Wynika to z faktu, że wszyscy pracownicy są karmieni wspólnym plikiem inqueuei tylko jeden pracownik może z niego odczytywać naraz. To samo dotyczy outqueue. Może to powodować większe zamieszanie, gdy tylko będziesz przesyłać dane o innych niż marginalne rozmiary, co zobaczymy później.

Ponadto widać, że pomimo faktu, że każdy element zadań obejmuje taką samą ilość pracy, rzeczywisty mierzony okres czasu dla zadania jest bardzo zróżnicowany. Zadania przydzielone do pracownika 3 i pracownika 4 wymagają więcej czasu niż te, które zostały przetworzone przez pierwszych dwóch pracowników. Podejrzewam, że w tym przebiegu jest to spowodowane tym, że turbo doładowanie nie było już dostępne w rdzeniach dla pracownika-3/4 w tym momencie, więc przetwarzali swoje zadania z niższą częstotliwością zegara.

Całe obliczenia są tak lekkie, że czynniki chaosu wprowadzone przez sprzęt lub system operacyjny mogą drastycznie wypaczyć PS . Obliczenie jest „liściem na wietrze”, a prognoza DM ma niewielkie znaczenie, nawet dla teoretycznie pasującego scenariusza.

2nd RUN: 30 mln iteracji i 0 MiB danych na zadanie

Zwiększenie liczby iteracji w pętli for z 30 000 do 30 milionów daje w rezultacie rzeczywisty harmonogram równoległy, który jest bliski idealnego dopasowania z przewidywanym na podstawie danych dostarczonych przez DM , hurra! Obliczenia za taskel jest teraz wystarczająco ciężki do marginalizacji części biegu jałowego na początku i pomiędzy nimi, pozwalając tylko wielkie biegu jałowym Podziel widoczne której DM przewidzieć.

Trzeci RUN: 30 mln iteracji i 50 MB danych na zadanie

Utrzymanie 30M iteracji, ale dodatkowo wysyłanie 50 MB na zadanie w tę iz powrotem, ponownie wypacza obraz. Tutaj efekt kolejkowania jest dobrze widoczny. Pracownik-4 musi czekać dłużej na swoje drugie zadanie niż Robotnik-1. Teraz wyobraź sobie ten harmonogram z 70 pracownikami!

W przypadku, gdy zestawy zadań są obliczeniowo bardzo lekkie, ale zapewniają znaczną ilość danych jako ładunek, wąskie gardło pojedynczej współużytkowanej kolejki może uniemożliwić jakąkolwiek dodatkową korzyść z dodawania większej liczby pracowników do puli, nawet jeśli są one obsługiwane przez fizyczne rdzenie. W takim przypadku Pracownik-1 mógłby wykonać swoje pierwsze zadanie i oczekiwać na nowe, jeszcze zanim Robotnik-40 otrzyma swoje pierwsze zadanie.

Powinno teraz stać się oczywiste, dlaczego czasy obliczeń Poolnie zawsze zmniejszają się liniowo wraz z liczbą pracowników. Wysyłanie stosunkowo dużych ilości danych może prowadzić do scenariuszy, w których większość czasu spędza się na oczekiwaniu na skopiowanie danych do przestrzeni adresowej pracownika i tylko jeden pracownik może być zasilany naraz.

4. RUN: 600 mln iteracji i 50 MB danych na zadanie

Tutaj ponownie wysyłamy 50 MiB, ale zwiększamy liczbę iteracji z 30M do 600M, co daje całkowity czas obliczeń z 10 s do 152 s. Ponownie narysowany harmonogram równoległy jest bliski idealnego dopasowania do przewidywanego, a koszty związane z kopiowaniem danych są marginalizowane.

9. Wniosek

Omówione mnożenie przez 4zwiększa elastyczność planowania, ale także wykorzystuje nierówności w rozkładach zadań. Bez tego mnożenia udział bezczynny byłby ograniczony do jednego pracownika, nawet w przypadku krótkich iteracji (w przypadku DM ze scenariuszem zagęszczonym). Algorytm wielkości kawałka puli wymaga, aby iterowalne dane wejściowe miały określony rozmiar, aby odzyskać tę cechę.

Miejmy nadzieję, że ta odpowiedź pokazała, że algorytm wielkości kawałków puli prowadzi do lepszego średnio lepszego wykorzystania rdzenia w porównaniu z naiwnym podejściem, przynajmniej dla przeciętnego przypadku i tak długo, jak nie jest brane pod uwagę. Naiwny algorytm może mieć tutaj wydajność dystrybucji (DE) tak niską, jak ~ 51%, podczas gdy algorytm rozmiaru częściowego Puli ma niski poziom ~ 81%. DE nie obejmuje jednak narzutu równoległego (PO), jak IPC. Rozdział 8 pokazał, że DE nadal może mieć wielką moc predykcyjną w przypadku gęstego scenariusza ze zmarginalizowanym narzutem.

Pomimo faktu, że algorytm wielkości kawałków Puli osiąga wyższy DE w porównaniu z naiwnym podejściem, nie zapewnia optymalnych rozkładów zadań dla każdej konstelacji wejściowej. Chociaż prosty statyczny algorytm porcjowania nie może zoptymalizować (w tym narzutów) wydajności równoległości (PE), nie ma nieodłącznego powodu, dla którego nie zawsze mógłby zapewnić względną wydajność dystrybucji (RDE) na poziomie 100%, to znaczy, że ten sam DE co z chunksize=1. Prosty algorytm wielkości kawałków składa się tylko z podstawowej matematyki i może w dowolny sposób „pokroić ciasto”.

W przeciwieństwie do implementacji algorytmu „porcjowania równych rozmiarów”, algorytm „porcjowania równych rozmiarów”, algorytm „porcjowania równych rozmiarów” zapewniłby RDE 100% dla każdej kombinacji len_iterable/ n_workers. Algorytm dzielenia równych rozmiarów byłby nieco bardziej skomplikowany do zaimplementowania w źródle puli, ale można go modulować na podstawie istniejącego algorytmu, po prostu pakując zadania na zewnątrz (utworzę łącze z tego miejsca na wypadek, gdybym upuścił Q / A na jak to zrobić).

Question 4

Myślę, że brakuje ci tego, że twoje naiwne szacunki zakładają, że każda jednostka pracy zajmuje tyle samo czasu, w którym to przypadku twoja strategia byłaby najlepsza. Ale jeśli niektóre zadania zakończą się wcześniej niż inne, niektóre rdzenie mogą stać się bezczynne w oczekiwaniu na zakończenie wolnych zadań.

Tak więc, dzieląc kawałki na 4 razy więcej kawałków, a następnie, jeśli jeden fragment zostanie ukończony wcześniej, rdzeń może rozpocząć następny fragment (podczas gdy inne rdzenie nadal pracują nad swoim wolniejszym kawałkiem).

Nie wiem, dlaczego dokładnie wybrali współczynnik 4, ale byłby to kompromis między zminimalizowaniem narzutu kodu mapy (który chce największej możliwej części) a równoważeniem fragmentów zajmujących różną ilość czasu (który chce najmniejszej możliwej części ).

Answer 1

Jakie czynniki decydują o optymalnym chunksizeargumencie do takich metod multiprocessing.Pool.map()? .map()Sposób wydaje się użycie dowolnego heurystyczne do domyślnej chunksize (jak opisano poniżej); co motywuje ten wybór i czy istnieje bardziej przemyślane podejście oparte na jakiejś konkretnej sytuacji / konfiguracji?

Przykład - powiedz, że jestem:

Przechodząc iterabledo .map()tego ma ~ 15 milionów elementów;
Praca na maszynie z 24 rdzeniami i używanie domyślnego processes = os.cpu_count()w ramach multiprocessing.Pool().

Moje naiwne myślenie to dać każdemu z 24 pracowników równej wielkości porcję, czyli 15_000_000 / 24625 000. Duże kawałki powinny zmniejszyć obroty / koszty ogólne przy pełnym wykorzystaniu wszystkich pracowników. Wydaje się jednak, że brakuje w tym pewnych potencjalnych wad dostarczania dużych partii każdemu pracownikowi. Czy to niekompletny obraz i czego mi brakuje?

Część mojego pytania wynika z domyślnej logiki dla if chunksize=None: both .map()i .starmap()call .map_async(), która wygląda tak:

def _map_async(self, func, iterable, mapper, chunksize=None, callback=None,
               error_callback=None):
    # ... (materialize `iterable` to list if it's an iterator)
    if chunksize is None:
        chunksize, extra = divmod(len(iterable), len(self._pool) * 4)  # ????
        if extra:
            chunksize += 1
    if len(iterable) == 0:
        chunksize = 0

Jaka jest logika divmod(len(iterable), len(self._pool) * 4)? Oznacza to, że rozmiar fragmentu będzie bliżej 15_000_000 / (24 * 4) == 156_250. Jaki jest zamiar pomnożenia len(self._pool)przez 4?

To sprawia, że wynikowy rozmiar fragmentu jest o współczynnik 4 mniejszy niż moja „naiwna logika” z góry, która polega po prostu na podzieleniu długości iteracji przez liczbę pracowników pool._pool.

Na koniec jest też ten fragment z dokumentacji Pythona, .imap()który dodatkowo napędza moją ciekawość:

chunksizeArgument jest taka sama jak ta wykorzystywana przez map() metody. W przypadku bardzo długich iteracji użycie dużej wartości for chunksizemoże sprawić, że zadanie zostanie ukończone znacznie szybciej niż użycie domyślnej wartości 1.

_{Powiązana odpowiedź, która jest pomocna, ale nieco zbyt ogólnikowa : Wieloprocesorowość w Pythonie: dlaczego duże porcje są wolniejsze? .}

Answer 2

1

4Jest arbitralne, a całe obliczanie rozmiaru części jest heurystyczne. Istotnym czynnikiem jest to, jak bardzo może się różnić rzeczywisty czas przetwarzania. Trochę więcej na ten temat tutaj, dopóki nie będę miał czasu na odpowiedź, jeśli nadal będzie potrzebna.

Darkonaut

Answer 3

Czy sprawdziłeś to pytanie ?

Andrew Naguib,

Answer 4

1

Dzięki @AndrewNaguib, tak naprawdę jakoś nie natknąłem się na to

Brad Solomon,

Answer 5

1

Chciałem tylko powiedzieć: nie zapomniałem tego pytania. W rzeczywistości pracuję nad kanoniczną odpowiedzią wymiarów biblijnych (wiele przydatnych fragmentów kodu i fantazyjnych grafik) od dnia, w którym zapytałeś. Nagroda wciąż nadeszła o 1-2 tygodnie za wcześnie, aby to wszystko zakończyć, ale jestem pewien, że będę w stanie upuścić coś wystarczająco blisko przed upływem terminu.

Darkonaut

Answer 6

@BradSolomon Zapraszamy :). Czy to jednak odpowiada na twoje pytanie?

Andrew Naguib,

Answer 7

Krótka odpowiedź

Algorytm wielkości kawałków puli to heurystyka. Zapewnia proste rozwiązanie wszystkich możliwych do wyobrażenia scenariuszy problemów, które próbujesz upchnąć w metodach Pool. W konsekwencji nie można go zoptymalizować pod kątem żadnego konkretnego scenariusza.

Algorytm arbitralnie dzieli iterowalność na około cztery razy więcej fragmentów niż podejście naiwne. Więcej fragmentów oznacza większe obciążenie, ale większą elastyczność planowania. Jak ta odpowiedź pokaże, prowadzi to średnio do wyższego wykorzystania pracowników, ale bez gwarancji krótszego całkowitego czasu obliczeń dla każdego przypadku.

„Miło jest wiedzieć”, możesz pomyśleć, „ale w jaki sposób znajomość tego pomoże mi w rozwiązaniu moich konkretnych problemów z wieloprocesorowością?” Tak nie jest. Bardziej uczciwa krótka odpowiedź brzmi: „nie ma krótkiej odpowiedzi”, „przetwarzanie wieloprocesowe jest złożone” i „to zależy”. Obserwowany objaw może mieć różne źródła, nawet w przypadku podobnych scenariuszy.

Ta odpowiedź ma na celu przedstawienie podstawowych pojęć, które pomogą Ci uzyskać jaśniejszy obraz czarnej skrzynki planowania Pool. Próbuje również udostępnić kilka podstawowych narzędzi do rozpoznawania i unikania potencjalnych klifów, o ile są one związane z rozmiarem fragmentów.

Spis treści

Część I.

Definicje
Cele zrównoleglenia
Scenariusze równoległości
Ryzyko wielkości kawałka> 1
Algorytm wielkości części puli
Kwantyfikacja wydajności algorytmu

6.1 Modele

6.2 Harmonogram równoległy

6.3 Wydajność

6.3.1 Absolute Distribution Efficiency (ADE)

6.3.2 Względna efektywność dystrybucji (RDE)

część druga

Algorytm naiwny kontra pulę
Sprawdzenie autentyczności
Wniosek

Najpierw należy wyjaśnić kilka ważnych terminów.

1. Definicje

Kawałek

Fragment w tym miejscu jest udziałem iterableargumentu określonego w wywołaniu metody puli. W jaki sposób obliczana jest wielkość kawałka i jakie może to mieć skutki, jest tematem tej odpowiedzi.

Zadanie

Fizyczną reprezentację zadania w procesie roboczym pod względem danych można zobaczyć na poniższym rysunku.

Na rysunku pokazano przykładowe wywołanie pool.map(), wyświetlane wzdłuż linii kodu, pobranego z multiprocessing.pool.workerfunkcji, w której zadanie odczytane z pliku inqueuezostaje rozpakowane. workerjest podstawową funkcją główną w procesie MainThreadroboczym puli. func-Argument określone w basenie metodą będzie pasował tylko func-variable wewnątrz worker-function dla metod pojedynczych połączeń, jak apply_asynci dla imapz chunksize=1. Dla pozostałych metod-puli z chunksize-parametrem funkcja-przetwarzania funcbędzie funkcją-mapującą ( mapstarlub starmapstar). Ta funkcja odwzorowuje określony przez użytkownika funcparametr na każdym elemencie przesyłanego fragmentu iterowalnego (-> "map-task"). Czas, jaki to zajmuje, określa zadanierównież jako jednostka pracy .

Taskel

Podczas gdy użycie słowa „zadanie” dla całego przetwarzania jednej porcji jest dopasowywane przez kod wewnątrz multiprocessing.pool, nie ma wskazania, w jaki sposób pojedyncze wywołanie określonego przez użytkownika func, z jednym elementem porcji jako argumentem, powinno być o którym mowa. Aby uniknąć nieporozumień pojawiających się od nazywania konfliktów (myśleć maxtasksperchild-parameter dla puli za __init__-method), to odpowiedź będzie odnosić się do pojedynczych jednostek prac w ramach zadania jako taskel .

Taskel (od zadania + el ement) jest najmniejszą jednostką pracy w zadaniu . Jest to pojedyncze wykonanie funkcji określonej funcparametrem Pool-method, wywoływane z argumentami uzyskanymi z pojedynczego elementu przesyłanego fragmentu . Zadanie składa się z chunksize taskels .

Narzut równoległości (PO)

PO składa się z wewnętrznego narzutu Pythona i narzutu komunikacji między procesami (IPC). Narzut na zadanie w Pythonie obejmuje kod potrzebny do pakowania i rozpakowywania zadań oraz ich wyników. IPC-overhead wiąże się z konieczną synchronizacją wątków i kopiowaniem danych między różnymi przestrzeniami adresowymi (potrzebne są dwa kroki kopiowania: rodzic -> kolejka -> dziecko). Wielkość narzutu IPC zależy od systemu operacyjnego, sprzętu i rozmiaru danych, co utrudnia uogólnienia dotyczące wpływu.

2. Cele zrównoleglenia

Podczas korzystania z przetwarzania wieloprocesowego naszym ogólnym celem (oczywiście) jest zminimalizowanie całkowitego czasu przetwarzania wszystkich zadań. Aby osiągnąć ten ogólny cel, naszym celem technicznym musi być optymalizacja wykorzystania zasobów sprzętowych .

Niektóre ważne cele cząstkowe umożliwiające osiągnięcie celu technicznego to:

zminimalizować narzut związany z równoległością (najbardziej znany, ale nie sam: IPC )
wysokie wykorzystanie wszystkich rdzeni procesora
utrzymywanie ograniczonego użycia pamięci, aby zapobiec nadmiernemu stronicowaniu ( koszowaniu ) systemu operacyjnego

Na początku zadania muszą być wystarczająco ciężkie obliczeniowo (intensywne), aby odzyskać PO musimy zapłacić za zrównoleglenie. Trafność PO maleje wraz ze wzrostem bezwzględnego czasu obliczeń na zadanie. Lub, mówiąc na odwrót, im większy bezwzględny czas obliczeń na zadanie dla danego problemu, tym mniej istotna jest potrzeba zmniejszenia PO. Jeśli twoje obliczenia zajmą kilka godzin na zadanie, narzut IPC będzie znikomy w porównaniu. Głównym problemem jest tutaj zapobieganie bezczynnym procesom roboczym po rozproszeniu wszystkich zadań. Utrzymując wszystkie rdzenie obciążone, równolegle robimy tak dużo, jak to możliwe.

3. Scenariusze równoległości

Jakie czynniki określają optymalny argument wielkości chunksize dla metod takich jak multiprocessing.Pool.map ()

Głównym pytanym czynnikiem jest to, ile czasu obliczeń może się różnić w naszych pojedynczych zadaniach. Aby to nazwać, wybór optymalnego rozmiaru fragmentu jest określany przez współczynnik zmienności ( CV ) dla czasów obliczeń na zadanie.

Dwa skrajne scenariusze w skali, wynikające z zakresu tej zmienności, to:

Wszystkie zadania potrzebują dokładnie tego samego czasu obliczeń.
Zakończenie zadania może zająć kilka sekund lub dni.

Aby lepiej zapamiętać, będę odnosił się do tych scenariuszy jako:

Gęsty scenariusz
Szeroki scenariusz

Gęsty scenariusz

W gęstym scenariuszu pożądane byłoby rozprowadzenie wszystkich zadań jednocześnie, aby zminimalizować niezbędne IPC i przełączanie kontekstów. Oznacza to, że chcemy tworzyć tylko tyle fragmentów, ile jest procesów roboczych. Jak już wspomniano powyżej, waga PO rośnie wraz z krótszymi czasami obliczeń na Taskel.

Aby zapewnić maksymalną przepustowość, chcemy również, aby wszystkie procesy robocze były zajęte do czasu przetworzenia wszystkich zadań (bez bezczynnych pracowników). W tym celu rozproszone fragmenty powinny być równej wielkości lub zbliżone.

Szeroki scenariusz

Najlepszym przykładem dla szerokiego scenariusza byłby problem optymalizacji, w którym wyniki albo szybko się zbiegają, albo obliczenia mogą zająć godziny, jeśli nie dni. Zwykle nie jest przewidywalne, jaką mieszankę „lekkich zadań” i „ciężkich zadań” będzie zawierało zadanie w takim przypadku, dlatego nie zaleca się rozdzielania zbyt wielu zadań jednocześnie w zestawie zadań. Dystrybucja mniejszej liczby zadań na raz niż to możliwe oznacza zwiększenie elastyczności planowania. Jest to potrzebne, aby osiągnąć nasz cel cząstkowy, jakim jest wysokie wykorzystanie wszystkich rdzeni.

Gdyby Poolmetody były domyślnie całkowicie zoptymalizowane pod kątem scenariusza zagęszczonego, w coraz większym stopniu tworzyłyby nieoptymalne czasy dla każdego problemu znajdującego się bliżej scenariusza szerokiego.

4. Ryzyko wielkości kawałka> 1

Rozważmy ten uproszczony przykład pseudokodu, przedstawiający literaturę Wide Scenario , którą chcemy przekazać do metody puli:

good_luck_iterable = [60, 60, 86400, 60, 86400, 60, 60, 84600]

Zamiast rzeczywistych wartości udajemy, że widzimy potrzebny czas obliczeń w sekundach, dla uproszczenia tylko 1 minuta lub 1 dzień. Zakładamy, że pula ma cztery procesy robocze (na czterech rdzeniach) i chunksizejest ustawiona na 2. Ponieważ kolejność zostanie zachowana, fragmenty wysłane do pracowników będą następujące:

[(60, 60), (86400, 60), (86400, 60), (60, 84600)]

Ponieważ mamy wystarczającą liczbę pracowników, a czas obliczeń jest wystarczająco długi, możemy powiedzieć, że każdy proces roboczy otrzyma kawałek do pracy. (Nie musi to mieć miejsca w przypadku szybkiego wykonywania zadań). Dalej możemy powiedzieć, że całe przetwarzanie zajmie około 86400 + 60 sekund, ponieważ jest to najwyższy całkowity czas obliczeniowy dla fragmentu w tym sztucznym scenariuszu, a fragmenty rozprowadzamy tylko raz.

Rozważmy teraz tę iterowalną, która ma tylko jeden element zmieniający swoją pozycję w porównaniu z poprzednią iterowalną:

bad_luck_iterable = [60, 60, 86400, 86400, 60, 60, 60, 84600]

... i odpowiednie fragmenty:

[(60, 60), (86400, 86400), (60, 60), (60, 84600)]

Po prostu pech z sortowaniem naszego iterowalnego prawie dwukrotnie (86400 + 86400) naszego całkowitego czasu przetwarzania! Pracownik pobierający błędną (86400, 86400) porcję blokuje drugi ciężki Taskel w swoim zadaniu przed przekazaniem go jednemu z bezczynnych pracowników, którzy już skończyli (60, 60) porcje. Oczywiście nie ryzykowalibyśmy tak nieprzyjemnego wyniku, gdybyśmy byli nastawieni chunksize=1.

To jest ryzyko większych kawałków. Przy większych porcjach handlujemy elastycznością planowania przy mniejszych kosztach, aw przypadkach takich jak powyżej to zła umowa.

Jak zobaczymy w rozdziale 6. Ilościowe określanie wydajności algorytmu , większe fragmenty mogą również prowadzić do nieoptymalnych wyników dla scenariuszy zagęszczonych .

5. Algorytm wielkości części puli

Poniżej znajdziesz nieco zmodyfikowaną wersję algorytmu wewnątrz kodu źródłowego. Jak widać, odciąłem dolną część i zawinąłem ją w funkcję do obliczania chunksizeargumentu na zewnątrz. Zastąpiłem 4też factorparametrem i zleciłem len()wywołania.

# mp_utils.py

def calc_chunksize(n_workers, len_iterable, factor=4):
    """Calculate chunksize argument for Pool-methods.

    Resembles source-code within `multiprocessing.pool.Pool._map_async`.
    """
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    return chunksize

Aby upewnić się, że wszyscy jesteśmy na tej samej stronie, oto co divmodrobi:

divmod(x, y)jest funkcją wbudowaną, która zwraca (x//y, x%y). x // yjest dzieleniem piętra, zwracającym zaokrąglony w dół iloraz z x / y, natomiast x % yjest operacją modulo zwracającą resztę z x / y. Stąd np . divmod(10, 3)Powroty (3, 1).

Teraz, jeśli spojrzeć chunksize, extra = divmod(len_iterable, n_workers * 4), można zauważyć n_workerstutaj jest dzielnik yw x / yi mnożenie przez 4, bez dalszej regulacji poprzez if extra: chunksize +=1później, prowadzi do początkowego chunksize co najmniej cztery razy mniejsze (o len_iterable >= n_workers * 4) niż byłoby inaczej.

Aby zobaczyć efekt mnożenia przez 4wynik pośredniego rozmiaru fragmentu, rozważ następującą funkcję:

def compare_chunksizes(len_iterable, n_workers=4):
    """Calculate naive chunksize, Pool's stage-1 chunksize and the chunksize
    for Pool's complete algorithm. Return chunksizes and the real factors by
    which naive chunksizes are bigger.
    """
    cs_naive = len_iterable // n_workers or 1  # naive approach
    cs_pool1 = len_iterable // (n_workers * 4) or 1  # incomplete pool algo.
    cs_pool2 = calc_chunksize(n_workers, len_iterable)

    real_factor_pool1 = cs_naive / cs_pool1
    real_factor_pool2 = cs_naive / cs_pool2

    return cs_naive, cs_pool1, cs_pool2, real_factor_pool1, real_factor_pool2

Powyższa funkcja oblicza naiwny rozmiar chunksize ( cs_naive) i rozmiar chunksize pierwszego kroku algorytmu chunksize-Algorytm puli ( cs_pool1), a także rozmiar części dla całego algorytmu Pool ( cs_pool2). Następnie oblicza rzeczywiste współczynniki rf_pool1 = cs_naive / cs_pool1 i rf_pool2 = cs_naive / cs_pool2, które mówią nam, ile razy obliczone naiwnie rozmiary fragmentów są większe niż wewnętrzne wersje Puli.

Poniżej widać dwie figury utworzone na podstawie danych wyjściowych z tej funkcji. Rysunek po lewej stronie pokazuje tylko rozmiary fragmentów n_workers=4aż do iterowalnej długości 500. Prawa rysunek przedstawia wartości rf_pool1. W przypadku długości iterowalnej 16rzeczywistym współczynnikiem staje się >=4(for len_iterable >= n_workers * 4), a jego maksymalna wartość dotyczy 7długości iterowalnych 28-31. To ogromne odchylenie od pierwotnego czynnika, 4do którego algorytm zbiega się w przypadku dłuższych iteracji. „Dłuższy” jest tutaj względny i zależy od liczby określonych pracowników.

Pamiętaj, że rozmiar fragmentu cs_pool1nadal nie ma korekty -dostosowania extrado reszty z divmodzawartej w cs_pool2całym algorytmie.

Algorytm kontynuuje:

if extra:
    chunksize += 1

Teraz w przypadkach, tam jest przypomnieniem (an extraz divmod-operation), zwiększając chunksize o 1 oczywiście nie może wypracować dla każdego zadania. Przecież gdyby tak się stało, nie byłoby żadnej reszty.

Jak widać na poniższych rysunkach, „ dodatkowe traktowanie ” skutkuje tym, że rzeczywisty czynnik na rf_pool2razie zbiega się w kierunku 4od dołu, 4 a odchylenie jest nieco łagodniejsze. Odchylenie standardowe dla n_workers=4i len_iterable=500spada od 0.5233za rf_pool1do 0.4115na rf_pool2.

Ostatecznie zwiększenie chunksizeo 1 skutkuje tym, że ostatnie przesłane zadanie ma rozmiar len_iterable % chunksize or chunksize.

Bardziej interesujący i jak zobaczymy później, bardziej konsekwentny efekt dodatkowego traktowania można jednak zaobserwować dla liczby wygenerowanych fragmentów ( n_chunks). W przypadku dostatecznie długich iterowalnych algorytm n_pool2wielkości fragmentów puli ( na poniższym rysunku) ustabilizuje liczbę fragmentów na poziomie n_chunks == n_workers * 4. W przeciwieństwie do tego, naiwne algorytm (po początkowym beknięciem) prowadzi na przemian n_chunks == n_workersi n_chunks == n_workers + 1w długości iterowalny wzrasta.

Poniżej znajdziesz dwie ulepszone funkcje informacyjne dla Pool's i naiwnego algorytmu chunksize. Dane wyjściowe tych funkcji będą potrzebne w następnym rozdziale.

# mp_utils.py

from collections import namedtuple


Chunkinfo = namedtuple(
    'Chunkinfo', ['n_workers', 'len_iterable', 'n_chunks',
                  'chunksize', 'last_chunk']
)

def calc_chunksize_info(n_workers, len_iterable, factor=4):
    """Calculate chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    # `+ (len_iterable % chunksize > 0)` exploits that `True == 1`
    n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
    # exploit `0 == False`
    last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

Nie daj się zmylić prawdopodobnie nieoczekiwanym wyglądem calc_naive_chunksize_info. Wartość extrafrom divmodnie jest używana do obliczania rozmiaru fragmentu.

def calc_naive_chunksize_info(n_workers, len_iterable):
    """Calculate naive chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers)
    if chunksize == 0:
        chunksize = 1
        n_chunks = extra
        last_chunk = chunksize
    else:
        n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
        last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

6. Kwantyfikacja wydajności algorytmu

Teraz, po tym jak zobaczyliśmy, jak wynik Poolalgorytmu chunksize wygląda inaczej w porównaniu z wyjściem z naiwnego algorytmu ...

Jak sprawdzić, czy podejście Pool rzeczywiście coś poprawia ?
I co dokładnie to może coś być?

Jak pokazano w poprzednim rozdziale, w przypadku dłuższych iteracji (większej liczby zadań), algorytm wielkości kawałków puli w przybliżeniu dzieli iterowalność na cztery razy więcej fragmentów niż metoda naiwna. Mniejsze fragmenty oznaczają więcej zadań, a więcej zadań oznacza więcej narzutów związanych z równoległością (PO) , kosztem, który należy porównać z korzyściami wynikającymi ze zwiększonej elastyczności planowania (przypomnij sobie „Ryzyko rozmiaru fragmentów> 1” ).

Z raczej oczywistych powodów podstawowy algorytm chunksize-puli nie może ważyć elastyczności planowania względem zamówienia zakupu . Koszty IPC zależą od systemu operacyjnego, sprzętu i rozmiaru danych. Algorytm nie może wiedzieć, na jakim sprzęcie uruchamiamy nasz kod, ani nie ma pojęcia, ile czasu zajmie ukończenie zadania. Jest to heurystyka zapewniająca podstawową funkcjonalność dla wszystkich możliwych scenariuszy. Oznacza to, że nie można go zoptymalizować pod kątem żadnego konkretnego scenariusza. Jak wspomniano wcześniej, PO również staje się coraz mniejszym problemem wraz ze wzrostem czasu obliczeń na zadanie (korelacja ujemna).

Kiedy przypomnisz sobie cele równoległości z rozdziału 2, jednym z punktów było:

wysokie wykorzystanie wszystkich rdzeni procesora

Wspomnianym wcześniej czymś , co algorytm chunksize-algorytmu puli może próbować ulepszyć, jest minimalizacja bezczynnych procesów roboczych , odpowiednio wykorzystanie rdzeni procesora .

Powtarzające się pytanie na temat SO dotyczące SO multiprocessing.Pooljest zadawane przez ludzi zastanawiających się nad nieużywanymi rdzeniami / bezczynnymi procesami roboczymi w sytuacjach, w których można oczekiwać, że wszystkie procesy robocze są zajęte. Chociaż może to mieć wiele powodów, bezczynne procesy robocze pod koniec obliczenia są obserwacją, której często możemy dokonać, nawet w przypadku scenariuszy zagęszczonych (równe czasy obliczeń na zadanie) w przypadkach, gdy liczba pracowników nie jest dzielnikiem liczby z kawałków ( n_chunks % n_workers > 0).

Teraz pytanie brzmi:

Jak praktycznie możemy przełożyć nasze rozumienie chunksizes na coś, co pozwoli nam wyjaśnić obserwowane wykorzystanie pracowników, a nawet porównać skuteczność różnych algorytmów w tym zakresie?

6.1 Modele

Aby uzyskać głębszy wgląd tutaj, potrzebujemy formy abstrakcji równoległych obliczeń, która upraszcza zbyt złożoną rzeczywistość do możliwego do zarządzania stopnia złożoności, zachowując jednocześnie znaczenie w określonych granicach. Taka abstrakcja nazywana jest modelem . Implementacja takiego „ modelu równoległości” (PM) generuje metadane (znaczniki czasu) odwzorowane na mapie roboczej, tak jak zrobiłyby to rzeczywiste obliczenia, gdyby dane były gromadzone. Metadane wygenerowane przez model pozwalają przewidywać metryki obliczeń równoległych pod pewnymi ograniczeniami.

Jednym z dwóch podmodeli w ramach zdefiniowanego tutaj PM jest Model Dystrybucji (DM) . DM wyjaśnia jak atomowy jednostki pracy (taskels) są rozmieszczone równolegle pracowników i czasie , gdy nie ma innych czynników niż odpowiednia chunksize algorytm, liczba pracowników, the-iterable wejściowego (liczba taskels) oraz czas ich trwania obliczeń jest uważany . Oznacza to, że nie obejmuje żadnych kosztów ogólnych .

W celu uzyskania pełnego PM , DM jest rozszerzany o model narzutów (OM) , reprezentujący różne formy narzutów równoległych (PO) . Taki model musi być skalibrowany indywidualnie dla każdego węzła (zależności sprzętowe, OS). Jak wiele form napowietrznych są reprezentowane w OM pozostaje otwarte i tak wielu OMs o różnym stopniu złożoności może istnieć. O tym, jaki poziom dokładności potrzebuje zaimplementowana OM, decyduje całkowita waga PO dla konkretnego obliczenia. Krótsze zadania prowadzą do większej wagi PO , co z kolei wymaga bardziej precyzyjnego OMgdybyśmy próbowali przewidzieć wydajność równoległości (PE) .

6.2 Harmonogram równoległy (PS)

Równoległe harmonogram jest dwuwymiarową reprezentacją równoległych obliczeniach, gdzie oś x reprezentuje czas, a oś y przedstawia basen pracowników równoległych. Liczba pracowników i całkowity czas obliczeń oznaczają zasięg prostokąta, w którym są rysowane mniejsze prostokąty. Te mniejsze prostokąty reprezentują atomowe jednostki pracy (taskels).

Poniżej znajduje się wizualizacja PS narysowana z danymi z algorytmu chunksize DM of Pool dla scenariusza gęstego .

Oś X jest podzielona na równe jednostki czasu, gdzie każda jednostka oznacza czas obliczeń wymagany przez zadanie.
Oś Y jest podzielona na liczbę procesów roboczych używanych przez pulę.
W tym miejscu pasek zadań jest wyświetlany jako najmniejszy prostokąt w kolorze cyjan, umieszczony na osi czasu (harmonogramie) anonimowego procesu roboczego.
Zadanie to jeden lub wiele zadań na osi czasu pracownika, które są stale podświetlane tym samym odcieniem.
Jednostki czasu biegu jałowego są reprezentowane przez kafelki w kolorze czerwonym.
Harmonogram równoległy jest podzielony na sekcje. Ostatnia sekcja to sekcja ogonowa.

Nazwy skomponowanych części można zobaczyć na poniższym obrazku.

W kompletnym PM zawierającym OM , Idling Share nie ogranicza się do ogona, ale obejmuje również przestrzeń między zadaniami, a nawet między zespołami zadań.

6.3 Wydajność

Przedstawione powyżej modele pozwalają na ilościowe określenie stopnia wykorzystania pracowników. Możemy wyróżnić:

Distribution Efficiency (DE) - obliczana za pomocą DM (lub uproszczonej metody dla Scenariusza Gęste ).
Wydajność równoległości (PE) - obliczana za pomocą skalibrowanego PM (predykcja) lub obliczana na podstawie metadanych rzeczywistych obliczeń.

Należy zauważyć, że obliczone wydajności nie korelują automatycznie z szybszymi ogólnymi obliczeniami dla danego problemu z równoległością. Wykorzystanie pracownika w tym kontekście rozróżnia jedynie między pracownikiem mającym rozpoczęty, ale niedokończony Taskel a pracownikiem nieposiadającym takiego „otwartego” zadania. Oznacza to, że ewentualna praca na biegu jałowym w czasie zadania nie jest rejestrowana.

Wszystkie wyżej wymienione wydajności uzyskuje się w zasadzie przez obliczenie ilorazu podziału Busy Share / Parallel Schedule . Różnica między DE i PE polega na tym, że zajęty udział zajmuje mniejszą część ogólnego harmonogramu równoległego dla wydłużonego narzutu PM .

Ta odpowiedź będzie dalej omawiać tylko prostą metodę obliczania DE dla gęstego scenariusza. Jest to wystarczające, aby porównać różne algorytmy wielkości fragmentów, ponieważ ...

... DM jest częścią PM , która zmienia się wraz z różnymi zastosowanymi algorytmami rozmiaru fragmentu.
... Gęsty Scenariusz z równymi czasami trwania obliczeń na zadanie przedstawia „stan stabilny”, w którym te przedziały czasowe wypadają z równania. Każdy inny scenariusz prowadziłby po prostu do losowych wyników, ponieważ kolejność zadań miałaby znaczenie.

6.3.1 Absolute Distribution Efficiency (ADE)

Tę podstawową efektywność można ogólnie obliczyć, dzieląc zajęty udział przez cały potencjał harmonogramu równoległego :

Absolute Distribution Efficiency (ADE) = Busy Share / Parallel Schedule

W przypadku scenariusza zagęszczonego uproszczony kod obliczeniowy wygląda następująco:

# mp_utils.py

def calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Absolute Distribution Efficiency (ADE).

    `len_iterable` is not used, but contained to keep a consistent signature
    with `calc_rde`.
    """
    if n_workers == 1:
        return 1

    potential = (
        ((n_chunks // n_workers + (n_chunks % n_workers > 1)) * chunksize)
        + (n_chunks % n_workers == 1) * last_chunk
    ) * n_workers

    n_full_chunks = n_chunks - (chunksize > last_chunk)
    taskels_in_regular_chunks = n_full_chunks * chunksize
    real = taskels_in_regular_chunks + (chunksize > last_chunk) * last_chunk
    ade = real / potential

    return ade

Jeśli nie ma na biegu jałowym Share , Busy akcji będzie równa do Parallel Harmonogram , stąd otrzymujemy ADE 100%. W naszym uproszczonym modelu jest to scenariusz, w którym wszystkie dostępne procesy będą zajęte przez cały czas potrzebny do przetworzenia wszystkich zadań. Innymi słowy, cała praca jest efektywnie równoległa do 100 procent.

Ale dlaczego ciągle odnoszę się do PE jako absolutnego PE ?

Aby to zrozumieć, musimy wziąć pod uwagę możliwy przypadek chunksize (cs), który zapewnia maksymalną elastyczność planowania (również liczbę górali, jaka może być. Zbieg okoliczności?):

__________________________________ ~ JEDEN ~ __________________________________

Jeśli na przykład mamy cztery procesy robocze i 37 zadań, będą bezczynni pracownicy nawet z chunksize=1, tylko dlatego, że n_workers=4nie jest dzielnikiem 37. Pozostała część z dzielenia 37/4 wynosi 1. Ten pojedynczy pozostały Taskel będzie musiał być przetwarzane przez jednego pracownika, podczas gdy pozostałe trzy są na biegu jałowym.

Podobnie, nadal będzie jeden bezczynny pracownik z 39 zadaniami, jak widać na poniższym obrazku.

Porównując górny harmonogram równoległy dla chunksize=1z wersją poniżej dla chunksize=3, zauważysz, że górny harmonogram równoległy jest mniejszy, a oś czasu na osi x krótsza. Powinno stać się teraz oczywiste, jak większe fragmenty nieoczekiwanie mogą również prowadzić do zwiększenia ogólnego czasu obliczeń, nawet w przypadku scenariuszy gęstych .

Ale dlaczego nie wykorzystać po prostu długości osi X do obliczeń wydajności?

Ponieważ narzut nie jest zawarty w tym modelu. Będzie różna dla obu rozmiarów fragmentów, stąd oś X nie jest bezpośrednio porównywalna. Narzut może nadal prowadzić do dłuższego całkowitego czasu obliczeń, jak pokazano w przypadku 2 na poniższym rysunku.

6.3.2 Względna efektywność dystrybucji (RDE)

Wartość ADE nie zawiera informacji, jeśli możliwa jest lepsza dystrybucja zadań z wielkością fragmentu ustawioną na 1. Lepiej tutaj nadal oznacza mniejszy udział na biegu jałowym .

Aby uzyskać wartość DE skorygowaną o maksymalny możliwy DE , musimy podzielić rozważane ADE przez ADE , dla którego otrzymujemy chunksize=1.

Względna efektywność dystrybucji (RDE) = ADE_cs_x / ADE_cs_1

Oto jak to wygląda w kodzie:

# mp_utils.py

def calc_rde(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Relative Distribution Efficiency (RDE)."""
    ade_cs1 = calc_ade(
        n_workers, len_iterable, n_chunks=len_iterable,
        chunksize=1, last_chunk=1
    )
    ade = calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk)
    rde = ade / ade_cs1

    return rde

RDE , jak tu zdefiniowano, jest w istocie opowieścią o ogonie równoległego harmonogramu . Na RDE wpływa maksymalny efektywny rozmiar kawałka znajdujący się w ogonie. (Ten ogon może mieć długość w osi X chunksizelub last_chunk.) To powoduje, że RDE naturalnie zbiega się do 100% (równo) dla wszelkiego rodzaju "ogonów", jak pokazano na poniższym rysunku.

Niski RDE ...

to mocna wskazówka dotycząca potencjału optymalizacji.
naturalnie staje się mniej prawdopodobne w przypadku dłuższych iteracji, ponieważ względna część końcowa ogólnego harmonogramu równoległego kurczy się.

Proszę znaleźć część II tej odpowiedzi tutaj .

Answer 8

51

Jedna z najbardziej epickich odpowiedzi, jakie widziałem w SO.

Christian Long

Answer 9

4

Och, to była twoja krótka odpowiedź: P

d_kennetz

Answer 10

1

Ale forreal… to doskonała odpowiedź. Zagrałem pytanie w przyszłych przypadkach, w których chcę to lepiej zrozumieć. Przeglądanie go już wiele mnie nauczyło! Dzięki

d_kennetz,

Answer 11

2

@ L.Iridium Nie ma za co! Tam, gdzie było to możliwe, korzystałem z matplotlib , a poza tym ... LibreOffice calc + Pinta (podstawowa edycja obrazu). Tak, wiem ... ale jakoś to działa. ;)

Darkonaut

Answer 12

2

Pierwsza odpowiedź ze spisem treści wyświetlanym w SO.

tly_alex

Answer 13

O tej odpowiedzi

Ta odpowiedź jest częścią II zaakceptowanej odpowiedzi powyżej .

7. Algorytm naiwny a algorytm wielkości puli

Zanim przejdziemy do szczegółów, rozważ dwa poniższe gify. Dla zakresu różnych iterabledługości pokazują, w jaki sposób dwa porównywane algorytmy dzielą przekazany fragment iterable(do tego czasu będzie to sekwencja) i jak mogą być rozdzielane wynikowe zadania. Kolejność pracowników jest losowa, a liczba rozdzielonych zadań na pracownika w rzeczywistości może różnić się od przedstawionych na tych obrazach dla lekkich zadań i / lub zestawów zadań w szerokim scenariuszu. Jak wspomniano wcześniej, nie uwzględniono tutaj również kosztów ogólnych. Jednak dla wystarczająco ciężkich zadań w gęstym scenariuszu z pomijalnymi rozmiarami przesyłanych danych, rzeczywiste obliczenia rysują bardzo podobny obraz.

cs_4_50

cs_200_250

Jak pokazano w rozdziale „ 5. Algorytm wielkości części puli ”, dzięki algorytmowi wielkości części puli liczba fragmentów ustabilizuje się n_chunks == n_workers * 4dla dostatecznie dużych elementów iteracyjnych, przy jednoczesnym przełączaniu między n_chunks == n_workersi n_chunks == n_workers + 1przy podejściu naiwnym. Dla algorytmu naiwnego Dotyczy: Bo n_chunks % n_workers == 1jest Trueza n_chunks == n_workers + 1nowy odcinek zostanie utworzony gdzie będzie zatrudniony tylko jeden pracownik.

Naiwny algorytm wielkości fragmentów:

Możesz pomyśleć, że utworzyłeś zadania dla tej samej liczby pracowników, ale będzie to prawdą tylko w przypadkach, w których nie ma reszty dla len_iterable / n_workers. Jeśli nie jest przypomnieniem, że będzie nowy odcinek z jednym tylko zadaniem dla pojedynczego pracownika. W tym momencie Twoje obliczenia nie będą już równoległe.

Poniżej widzisz rysunek podobny do pokazanego w rozdziale 5, ale wyświetlający liczbę sekcji zamiast liczby fragmentów. Dla pełnego algorytmu wielkości chunksize puli ( n_pool2) n_sectionsustabilizuje się na niesławnym, zakodowanym na stałe współczynniku 4. Dla naiwnego algorytmu, n_sectionsbędzie zmieniał się od jednego do dwóch.

W przypadku algorytmu wielkości kawałków puli stabilizacja n_chunks = n_workers * 4przez wspomnianą wcześniej dodatkową obróbkę zapobiega tworzeniu nowej sekcji w tym miejscu i ogranicza udział bezczynności do jednego pracownika przez wystarczająco długi czas iterowalny. Co więcej, algorytm będzie nadal zmniejszał relatywny rozmiar udziału na biegu jałowym , co prowadzi do zbliżenia wartości RDE do 100%.

„Długa na tyle” za n_workers=4to len_iterable=210na przykład. W przypadku iterowalnych równych lub większych niż to, udział na biegu jałowym będzie ograniczony do jednego pracownika, cecha pierwotnie utracona z powodu 4-mnożenia w algorytmie rozmiaru fragmentu.

Naiwny algorytm wielkości kawałków również zbliża się do 100%, ale robi to wolniej. Efekt zbieżności zależy wyłącznie od tego, że względna część ogona kurczy się w przypadkach, gdy będą dwie sekcje. Ten ogon z tylko jednym zatrudnionym pracownikiem jest ograniczony do długości osi X n_workers - 1, możliwej maksymalnej pozostałej części len_iterable / n_workers.

Czym różnią się rzeczywiste wartości RDE dla algorytmu naiwnego i algorytmu chunksize?

Poniżej znajdują się dwie mapy cieplne pokazujące wartości RDE dla wszystkich iterowalnych długości do 5000, dla wszystkich liczb pracowników od 2 do 100. Skala kolorów wynosi od 0,5 do 1 (50% -100%). Zauważysz znacznie więcej ciemnych obszarów (niższe wartości RDE) dla naiwnego algorytmu na lewej mapie cieplnej. W przeciwieństwie do tego algorytm wielkości kawałków Puli po prawej stronie rysuje znacznie bardziej słoneczny obraz.

Ukośny gradient ciemnych lewych dolnych rogów w porównaniu z prawymi górnymi jasnymi rogami ponownie pokazuje zależność od liczby pracowników w przypadku tego, co można nazwać „długim iterowalnym”.

Jak źle może się to stać z każdym algorytmem?

Z algorytmem chunksize puli wartość RDE 81,25% jest najniższą wartością dla zakresu pracowników i iterowalnych długości określonych powyżej:

Z naiwnym algorytmem wielkości fragmentów sytuacja może się znacznie pogorszyć. Najniższe obliczone RDE to 50,72%. W tym przypadku przez prawie połowę czasu obliczeń działa tylko jeden pracownik! Uważajcie więc, dumni właściciele Knights Landing . ;)

8. Sprawdzenie rzeczywistości

W poprzednich rozdziałach rozważaliśmy uproszczony model czysto matematycznego problemu dystrybucji, pozbawiony drobiazgowych szczegółów, które sprawiają, że przetwarzanie wieloprocesowe jest tak drażliwym tematem. Aby lepiej zrozumieć, jak daleko Distribution modelu (DM) sam może przyczynić się do wyjaśnienia obserwowanego wykorzystanie pracowników w rzeczywistości, będziemy teraz podjąć pewne spojrzenia na Parallel wykazach sporządzonych przez rzeczywistych obliczeniach.

Ustawiać

Poniższe wykresy dotyczą równoległych wykonań prostej, powiązanej z procesorem funkcji fikcyjnej, która jest wywoływana z różnymi argumentami, dzięki czemu możemy obserwować, jak narysowany harmonogram równoległy zmienia się w zależności od wartości wejściowych. „Praca” w ramach tej funkcji składa się tylko z iteracji po obiekcie zakresu. To już wystarczy, aby rdzeń był zajęty, ponieważ przekazujemy ogromne liczby. Opcjonalnie funkcja pobiera dodatkowe, unikalne dla zadań, dataktóre są po prostu zwracane niezmienione. Ponieważ każdy z zadań obejmuje dokładnie taką samą ilość pracy, nadal mamy tutaj do czynienia z gęstym scenariuszem.

Funkcja jest ozdobiona opakowaniem pobierającym znaczniki czasu o rozdzielczości ns (Python 3.7+). Znaczniki czasu są używane do obliczania przedziału czasu zadania, a tym samym umożliwiają rysowanie empirycznego harmonogramu równoległego.

@stamp_taskel
def busy_foo(i, it, data=None):
    """Dummy function for CPU-bound work."""
    for _ in range(int(it)):
        pass
    return i, data


def stamp_taskel(func):
    """Decorator for taking timestamps on start and end of decorated
    function execution.
    """
    @wraps(func)
    def wrapper(*args, **kwargs):
        start_time = time_ns()
        result = func(*args, **kwargs)
        end_time = time_ns()
        return (current_process().name, (start_time, end_time)), result
    return wrapper

Metoda Starmap Pool jest również udekorowana w taki sposób, że tylko samo wywołanie gwiezdnej gwiazdy jest mierzone w czasie. „Początek” i „koniec” tego wezwania określają minimum i maksimum na osi x utworzonego harmonogramu równoległego.

Będziemy obserwować obliczenia 40 zadań na czterech procesach roboczych na maszynie o następujących specyfikacjach: Python 3.7.1, Ubuntu 18.04.2, procesor Intel® Core ™ i7-2600K @ 3,40 GHz × 8

Wartości wejściowe, które będą się zmieniać, to liczba iteracji w pętli for (30k, 30M, 600M) oraz dodatkowo wielkość wysyłanych danych (na taskel, numpy-ndarray: 0 MiB, 50 MiB).

...
N_WORKERS = 4
LEN_ITERABLE = 40
ITERATIONS = 30e3  # 30e6, 600e6
DATA_MiB = 0  # 50

iterable = [
    # extra created data per taskel
    (i, ITERATIONS, np.arange(int(DATA_MiB * 2**20 / 8)))  # taskel args
    for i in range(LEN_ITERABLE)
]


with Pool(N_WORKERS) as pool:
    results = pool.starmap(busy_foo, iterable)

Pokazane poniżej przebiegi zostały starannie dobrane tak, aby miały taką samą kolejność fragmentów, dzięki czemu można lepiej dostrzec różnice w porównaniu z harmonogramem równoległym z modelu dystrybucji, ale nie zapominaj, że kolejność, w której pracownicy wykonują swoje zadania, jest niedeterministyczna.

DM Prediction

Powtarzając, model dystrybucji „przewiduje” równoległy harmonogram, jak widzieliśmy już wcześniej w rozdziale 6.2:

Pierwsze uruchomienie: 30 tys. Iteracji i 0 MiB danych na zadanie

Nasz pierwszy bieg tutaj jest bardzo krótki, zestawy zadań są bardzo „lekkie”. Całe połączenie pool.starmap()trwało łącznie tylko 14,5 ms. Zauważysz, że w przeciwieństwie do DM , praca na biegu jałowym nie ogranicza się do sekcji ogonowej, ale ma również miejsce między zadaniami, a nawet między zadaniami. Dzieje się tak, ponieważ nasz prawdziwy harmonogram obejmuje oczywiście wszystkie rodzaje kosztów ogólnych. Bezczynność tutaj oznacza po prostu wszystko poza zadaniami. Ewentualne rzeczywiste bezczynność podczas zadania nie jest uchwycone, jak już wspomniano wcześniej.

Dalej widać, że nie wszyscy pracownicy wykonują swoje zadania w tym samym czasie. Wynika to z faktu, że wszyscy pracownicy są karmieni wspólnym plikiem inqueuei tylko jeden pracownik może z niego odczytywać naraz. To samo dotyczy outqueue. Może to powodować większe zamieszanie, gdy tylko będziesz przesyłać dane o innych niż marginalne rozmiary, co zobaczymy później.

Ponadto widać, że pomimo faktu, że każdy element zadań obejmuje taką samą ilość pracy, rzeczywisty mierzony okres czasu dla zadania jest bardzo zróżnicowany. Zadania przydzielone do pracownika 3 i pracownika 4 wymagają więcej czasu niż te, które zostały przetworzone przez pierwszych dwóch pracowników. Podejrzewam, że w tym przebiegu jest to spowodowane tym, że turbo doładowanie nie było już dostępne w rdzeniach dla pracownika-3/4 w tym momencie, więc przetwarzali swoje zadania z niższą częstotliwością zegara.

Całe obliczenia są tak lekkie, że czynniki chaosu wprowadzone przez sprzęt lub system operacyjny mogą drastycznie wypaczyć PS . Obliczenie jest „liściem na wietrze”, a prognoza DM ma niewielkie znaczenie, nawet dla teoretycznie pasującego scenariusza.

2nd RUN: 30 mln iteracji i 0 MiB danych na zadanie

Zwiększenie liczby iteracji w pętli for z 30 000 do 30 milionów daje w rezultacie rzeczywisty harmonogram równoległy, który jest bliski idealnego dopasowania z przewidywanym na podstawie danych dostarczonych przez DM , hurra! Obliczenia za taskel jest teraz wystarczająco ciężki do marginalizacji części biegu jałowego na początku i pomiędzy nimi, pozwalając tylko wielkie biegu jałowym Podziel widoczne której DM przewidzieć.

Trzeci RUN: 30 mln iteracji i 50 MB danych na zadanie

Utrzymanie 30M iteracji, ale dodatkowo wysyłanie 50 MB na zadanie w tę iz powrotem, ponownie wypacza obraz. Tutaj efekt kolejkowania jest dobrze widoczny. Pracownik-4 musi czekać dłużej na swoje drugie zadanie niż Robotnik-1. Teraz wyobraź sobie ten harmonogram z 70 pracownikami!

W przypadku, gdy zestawy zadań są obliczeniowo bardzo lekkie, ale zapewniają znaczną ilość danych jako ładunek, wąskie gardło pojedynczej współużytkowanej kolejki może uniemożliwić jakąkolwiek dodatkową korzyść z dodawania większej liczby pracowników do puli, nawet jeśli są one obsługiwane przez fizyczne rdzenie. W takim przypadku Pracownik-1 mógłby wykonać swoje pierwsze zadanie i oczekiwać na nowe, jeszcze zanim Robotnik-40 otrzyma swoje pierwsze zadanie.

Powinno teraz stać się oczywiste, dlaczego czasy obliczeń Poolnie zawsze zmniejszają się liniowo wraz z liczbą pracowników. Wysyłanie stosunkowo dużych ilości danych może prowadzić do scenariuszy, w których większość czasu spędza się na oczekiwaniu na skopiowanie danych do przestrzeni adresowej pracownika i tylko jeden pracownik może być zasilany naraz.

4. RUN: 600 mln iteracji i 50 MB danych na zadanie

Tutaj ponownie wysyłamy 50 MiB, ale zwiększamy liczbę iteracji z 30M do 600M, co daje całkowity czas obliczeń z 10 s do 152 s. Ponownie narysowany harmonogram równoległy jest bliski idealnego dopasowania do przewidywanego, a koszty związane z kopiowaniem danych są marginalizowane.

9. Wniosek

Omówione mnożenie przez 4zwiększa elastyczność planowania, ale także wykorzystuje nierówności w rozkładach zadań. Bez tego mnożenia udział bezczynny byłby ograniczony do jednego pracownika, nawet w przypadku krótkich iteracji (w przypadku DM ze scenariuszem zagęszczonym). Algorytm wielkości kawałka puli wymaga, aby iterowalne dane wejściowe miały określony rozmiar, aby odzyskać tę cechę.

Miejmy nadzieję, że ta odpowiedź pokazała, że algorytm wielkości kawałków puli prowadzi do lepszego średnio lepszego wykorzystania rdzenia w porównaniu z naiwnym podejściem, przynajmniej dla przeciętnego przypadku i tak długo, jak nie jest brane pod uwagę. Naiwny algorytm może mieć tutaj wydajność dystrybucji (DE) tak niską, jak ~ 51%, podczas gdy algorytm rozmiaru częściowego Puli ma niski poziom ~ 81%. DE nie obejmuje jednak narzutu równoległego (PO), jak IPC. Rozdział 8 pokazał, że DE nadal może mieć wielką moc predykcyjną w przypadku gęstego scenariusza ze zmarginalizowanym narzutem.

Pomimo faktu, że algorytm wielkości kawałków Puli osiąga wyższy DE w porównaniu z naiwnym podejściem, nie zapewnia optymalnych rozkładów zadań dla każdej konstelacji wejściowej. Chociaż prosty statyczny algorytm porcjowania nie może zoptymalizować (w tym narzutów) wydajności równoległości (PE), nie ma nieodłącznego powodu, dla którego nie zawsze mógłby zapewnić względną wydajność dystrybucji (RDE) na poziomie 100%, to znaczy, że ten sam DE co z chunksize=1. Prosty algorytm wielkości kawałków składa się tylko z podstawowej matematyki i może w dowolny sposób „pokroić ciasto”.

W przeciwieństwie do implementacji algorytmu „porcjowania równych rozmiarów”, algorytm „porcjowania równych rozmiarów”, algorytm „porcjowania równych rozmiarów” zapewniłby RDE 100% dla każdej kombinacji len_iterable/ n_workers. Algorytm dzielenia równych rozmiarów byłby nieco bardziej skomplikowany do zaimplementowania w źródle puli, ale można go modulować na podstawie istniejącego algorytmu, po prostu pakując zadania na zewnątrz (utworzę łącze z tego miejsca na wypadek, gdybym upuścił Q / A na jak to zrobić).

Answer 14

Myślę, że brakuje ci tego, że twoje naiwne szacunki zakładają, że każda jednostka pracy zajmuje tyle samo czasu, w którym to przypadku twoja strategia byłaby najlepsza. Ale jeśli niektóre zadania zakończą się wcześniej niż inne, niektóre rdzenie mogą stać się bezczynne w oczekiwaniu na zakończenie wolnych zadań.

Tak więc, dzieląc kawałki na 4 razy więcej kawałków, a następnie, jeśli jeden fragment zostanie ukończony wcześniej, rdzeń może rozpocząć następny fragment (podczas gdy inne rdzenie nadal pracują nad swoim wolniejszym kawałkiem).

Nie wiem, dlaczego dokładnie wybrali współczynnik 4, ale byłby to kompromis między zminimalizowaniem narzutu kodu mapy (który chce największej możliwej części) a równoważeniem fragmentów zajmujących różną ilość czasu (który chce najmniejszej możliwej części ).

Wieloprocesorowość w Pythonie: zrozumienie logiki stojącej za `chunksize`

Odpowiedzi:

Krótka odpowiedź

1. Definicje

2. Cele zrównoleglenia

3. Scenariusze równoległości

Gęsty scenariusz

Szeroki scenariusz

4. Ryzyko wielkości kawałka> 1

5. Algorytm wielkości części puli

6. Kwantyfikacja wydajności algorytmu

6.1 Modele

6.2 Harmonogram równoległy (PS)

6.3 Wydajność

6.3.1 Absolute Distribution Efficiency (ADE)

6.3.2 Względna efektywność dystrybucji (RDE)

7. Algorytm naiwny a algorytm wielkości puli

8. Sprawdzenie rzeczywistości

Ustawiać

DM Prediction

Pierwsze uruchomienie: 30 tys. Iteracji i 0 MiB danych na zadanie

2nd RUN: 30 mln iteracji i 0 MiB danych na zadanie

Trzeci RUN: 30 mln iteracji i 50 MB danych na zadanie

4. RUN: 600 mln iteracji i 50 MB danych na zadanie

9. Wniosek