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.
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
cs_pool1 = len_iterable // (n_workers * 4) or 1
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.
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
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
)
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:
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:
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 .
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.