Prawo Amdahla

Wzrost szybkości wykonywania się programu przy użyciu wielu procesorów w obliczeniach równoległych jest ograniczany przez sekwencyjny podział programu. Na przykład jeżeli 95% programu może być przetworzone równolegle, wówczas maksymalny wzrost szybkości wykonania programu przy użyciu przetwarzania równoległego może wynieść 20× bez względu na ilość użytych procesorów.

Prawo Amdahla, znane również jako Wywód Amdahla^[1], zostało nazwane od nazwiska twórcy architektur komputerowych Gene Amdahla, i jest używane do znajdowania maksymalnego spodziewanego zwiększenia wydajności całkowitej systemu jeżeli tylko część systemu została ulepszona. Jest ono często używane w przypadku prowadzenia obliczeń równoległych do przewidzenia teoretycznego maksymalnego wzrostu szybkości obliczeń przy użyciu wielu procesorów.

Zwiększenie szybkości wykonywania się programu przy użyciu wielu procesorów w obliczeniach równoległych jest ograniczane przez czas potrzebny do sekwencyjnego dzielenia programu. Na przykład jeżeli program potrzebuje 20 godzin w przypadku obliczeń prowadzonych na procesorze jednordzeniowym i 1 godzina obliczeń nie może zostać przetworzona poprzez obliczenia równoległe, ale pozostałe 19 godzin (95%) obliczeń mogą, wówczas bez względu na to ile procesorów zostanie użytych do przeprowadzenia obliczeń równoległych minimalny czas wykonania programu nie będzie nigdy mniejszy niż ta krytyczna 1 godzina. Tak więc zwiększenie szybkości obliczeń jest ograniczone do 20×, jak przedstawiono na diagramie.

Opis

Prawo Amdahla jest to model zależności pomiędzy oczekiwanym wzrostem szybkości implementacji równoległej algorytmu a algorytmem szeregowym, przy założeniu, że zakres problemu pozostanie taki sam w implementacji równoległej. Na przykład jeżeli z całości rozpatrywanego problemu implementacja równoległa algorytmu może wykonać 12% operacji bezwzględnie szybko (podczas gdy pozostałe 88% operacji nie może być wykonana równolegle), prawo Amdahla stanowi, że maksymalne zwiększenie wydajności wersji równoległej wynosi: ${\displaystyle 1=1/(1-0{,}12)=1{,}136}$ razy szybciej niż implementacja nierównoległa.

Mówiąc bardziej technicznie, prawo to skoncentrowane jest na zwiększeniu wydajności osiągniętej z usprawnienia obliczeń, które wpływają na proporcję ${\displaystyle P}$ tych obliczeń, gdzie usprawnienie ma wzrost szybkości obliczeń ${\displaystyle S.}$ (Na przykład, jeżeli usprawnienie obliczeń dotyczy części stanowiącej 30% wszystkich obliczeń, ${\displaystyle P}$ będzie równe 0,3; jeżeli usprawnienie powoduje, że część, której dotyczy, wykonuje się dwa razy szybciej, wówczas ${\displaystyle S}$ będzie równe 2). Prawo Amdahla stanowi, że całkowity wzrost szybkości po zastosowaniu usprawnienia będzie wynosił:

${\displaystyle {\frac {1}{(1-P)+{\frac {P}{S}}}}.}$

Aby zobaczyć, jak ten wzór został wyprowadzony, załóżmy, że czas wykonania starych obliczeń wynosi 1 jakiejś jednostki czasu. Czas wykonania nowych obliczeń będzie równy czasowi wykonania części bez usprawnień (czyli ${\displaystyle 1-P}$), plus czas, jaki zabierze wykonanie części po zastosowaniu usprawnień. Długość czasu części ulepszonej jest równa czasowi wykonania części usprawnionej, ale przed zastosowaniem ulepszeń, podzielonej przez wzrost szybkości wykonania, co daje w rezultacie czas wykonania części ulepszonej, jako ${\displaystyle P/S.}$ Tak więc finalne zwiększenie szybkości wykonania obliczane jest poprzez podzielenie czasu wykonania części ulepszonej – przed zastosowaniem ulepszenia – przez czas wykonania części ulepszonej – po zastosowaniu ulepszenia – co jest tym, co powyższy wzór czyni.

Kolejny przykład. Mamy zadanie, które zostało podzielone na cztery części: P1 = 11%, P2 = 18%, P3 = 23%, P4 = 48%, co daje w sumie 100%. Teraz określamy, że P1 nie ulegnie przyspieszeniu, wiec S1 = 1 lub 100%, P2 ulegnie przyspieszeniu 5×, więc S2 = 500%, P3 ulegnie przyspieszeniu 20×, więc S3 = 2000%, oraz P4 ulegnie przyspieszeniu 1,6×, więc S4 = 160%. Poprzez użycie tego wzoru P1/S1 + P2/S2 + P3/S3 + P4/S4, znajdujemy, że czas wykonania to

${\displaystyle {\frac {0{,}11}{1}}+{\frac {0{,}18}{5}}+{\frac {0{,}23}{20}}+{\frac {0{,}48}{1{,}6}}=0{,}4575.}$

lub nieco mniej niż ½ niż oryginalny czas wykonania, który jak wiemy jest równy 1. Tak więc całkowity wzrost szybkości wykonania wynosi: ${\displaystyle 1/0{,}4575=2{,}186}$

lub nieco więcej niż dwa razy tyle co oryginalna szybkość wykonania przy użyciu formuły ${\displaystyle (P1/S1+P2/S2+P3/S3+P4/S4)^{-1}.}$ Należy zauważyć, że 20× i 5× przyspieszenia szybkości nie mają większego wpływu na końcowe przyspieszenie całkowite i czas wykonania jeżeli 11% nie ulega przyspieszeniu oraz 48% zostaje przyspieszone o 1,6×.

Zrównoleglanie

W przypadku zrównoleglania, Prawo Amdahla mówi, że jeżeli ${\displaystyle P}$ jest proporcją programu, który może podlegać zrównolegleniu (np. korzyści z wykonywania równoległego) i ${\displaystyle (1-P)}$ jest proporcją części, która nie może zostać zrównoleglona (pozostaje w przetwarzaniu szeregowym), wówczas maksymalne przyspieszenie jakie może być uzyskane przy użyciu ${\displaystyle N}$ procesorów jest równe:

${\displaystyle {\frac {1}{(1-P)+{\frac {P}{N}}}}.}$

Przy granicy, gdzie ${\displaystyle N}$ dąży do nieskończoności, maksymalne przyspieszenie wykonania dąży do ${\displaystyle 1/(1-P).}$ W praktyce stosunek wydajności do ceny spada gwałtownie jeśli ${\displaystyle N}$ zostanie zwiększone nawet jeśli istnieje komponent ${\displaystyle (1-P)}$ o małej wartości.

Na przykład jeżeli ${\displaystyle P}$ jest równe 90%, wówczas ${\displaystyle (1-P)}$ jest równe 10% w takim przypadku wykonanie zadania może zostać przyspieszone maksymalnie 10 razy bez względu na jak duża będzie wartość ${\displaystyle N.}$ Z tego względu przetwarzanie równoległe jest użyteczne albo dla małych ilości procesorów lub zadań o bardzo dużej wartości ${\displaystyle P{:},}$ czyli zadań, które nie stanowią większego problemu przy rozbijaniu ich na zadania cząstkowe do przetwarzania równoległego. Dużą częścią programowania równoległego jest dążenie do zredukowania komponentu ${\displaystyle (1-P)}$ do możliwie najmniejszej wartości.

${\displaystyle P}$ może zostać przewidziane przy użyciu zmierzonego przyspieszenia ${\displaystyle SU}$ na pewnej ilości procesorów ${\displaystyle NP{:}}$

${\displaystyle P_{\text{estimated}}={\frac {{\frac {1}{SU}}-1}{{\frac {1}{NP}}-1}}.}$

${\displaystyle P}$ przewidziane tym sposobem może zostać użyte do przewidzenia wzrostu prędkości działania dla innej liczby procesorów przy użyciu Prawa Amdahla.

Powiązanie z prawem malejących przychodów

Prawo Amdahla w szczególnym przypadku demonstruje działanie prawa malejących przychodów. Jeżeli zostanie dokonany optymalny wybór (w znaczeniu osiągniętego wzrostu prędkości), wówczas wzrost wydajności przy każdej kolejnej optymalizacji będzie mniejszy. Jeżeli jednak zostanie dokonany wybór nieoptymalny to po ulepszeniu go i próbie ulepszania komponentu bardziej zoptymalizowanego można zauważyć w rezultacie wzrost. Przykładowo, jeżeli do wykonania wybrany zostanie element B, a później A to w rezultacie nastąpi wzrost. Jeśli natomiast najpierw do optymalizacji wybrany zostanie element A, a później B w efekcie będzie można zaobserwować zachowanie jak w przypadku prawa malejących przychodów. W skrócie – tylko jeden przypadek (gdzie rozpoczęto od elementu najbardziej zoptymalizowanego) może być odpowiednio wykorzystany do zademonstrowania prawa malejących przychodów. Czasami opłaca się przeprowadzenie usprawnienie systemu w porządku w jakim jest on niezoptymalizowany, uważając jednak na to, iż niektóre usprawnienia mogą okazać się bardziej złożone niż inne i zabierające więcej czasu potrzebnego na znalezienie rozwiązań – pisanie kodu.

Prawo Amdahla reprezentuje prawo malejących przychodów jeśli zostanie wzięte pod uwagę jaki rodzaj rezultatu zostanie otrzymany poprzez dodanie dodatkowych procesorów do maszyny wykonawczej, w przypadku prowadzenia obliczeń o ustalonej wielkości używając wszystkich dostępnych procesorów. Każdy nowy procesor, który zostanie dodany do systemu będzie poszerzał możliwości systemu o coraz mniejszą ilość użytecznej mocy obliczeniowej w porównaniu do poprzedniego dodanego procesora. Za każdym razem gdy liczba procesorów zostanie podwojona współczynnik wzrostu prędkości przetwarzania będzie malał, jako że całkowita przepustowość zmierza ku granicy ${\displaystyle 1/(1-P).}$

Analiza ta pomija potencjalne „wąskie gardła” takie jak przepustowość pamięci, czy przepustowości I/O, jeżeli parametry te nie są skalowane odpowiednio do ilości procesorów; jakkolwiek biorąc pod uwagę tylko takie „wąskie gardła” na ogół pokazują ponadto prawo malejących przychodów tylko poprzez dodawanie kolejnych procesorów.

Przyspieszenie w programach sekwencyjnych

Załóżmy, że zadanie ma dwie niezależne części, A i B. Część B zabiera 25% czasu wszystkich obliczeń. Poprzez duży nakład pracy udało się zoptymalizować tę część dzięki czemu wykonuje się 5 razy szybciej, ale to spowodowało, że całkowity czas wykonania wszystkich obliczeń zmalał nieznacznie. W odróżnieniu część A wymagała mniejszego nakładu pracy w celu uzyskania 2-krotnie krótszego czasu do jej wykonania. W rezultacie pozwoli to na skrócenie całkowitego czasu wykonania w przeciwieństwie do sytuacji kiedy optymalizowana była część B, nawet, pomimo że część B ma wyższą wartość przyspieszenia wykonania (5× wobec 2×).

Maksymalne przyspieszenie wykonania programu sekwencyjnego, w którym pewna część została przyspieszona ${\displaystyle p}$ razy jest ograniczona poprzez nierówność

${\displaystyle {\text{maximum speedup }}\leqslant {\frac {p}{1+f\cdot (p-1)}},}$

gdzie ${\displaystyle f}$ ${\displaystyle (0<f<1)}$ jest częścią czasu (przed ulepszeniem) zużytego w części, która nie była ulepszona. Na przykład (patrz obrazek po prawej):

• Jeżeli część B jest wykonana 5 razy szybciej ${\displaystyle (p=5),}$ ${\displaystyle t_{A}=3,}$ ${\displaystyle t_{B}=1}$ i ${\displaystyle f=t_{A}/(t_{A}+t_{B})=0{,}75,}$ wówczas

  ${\displaystyle {\text{maximum speedup }}\leqslant {\frac {5}{1+0{,}75\cdot (5-1)}}=1{,}25.}$

• Jeżeli część A jest wykonana 2 razy szybciej ${\displaystyle (p=2),}$ ${\displaystyle t_{B}=1,}$ ${\displaystyle t_{A}=3}$ i ${\displaystyle f=t_{B}/(t_{A}+t_{B})=0{,}25,}$ wówczas

  ${\displaystyle {\text{maximum speedup }}\leqslant {\frac {2}{1+0{,}25\cdot (2-1)}}=1{,}60.}$

Tak więc wykonanie części A dwa razy szybciej będzie lepszym rozwiązaniem niż wykonanie części B pięć razy szybciej. Procentowe ulepszenie w prędkości wykonania może być obliczone jako

${\displaystyle {\text{percentage improvement}}=\left(1-{\frac {1}{\text{speedup factor}}}\right)\cdot 100\%.}$

• Ulepszenie części A dwa razy spowoduje ogólne zwiększenie prędkości wykonania programu 1,6 razy, czyli szybciej o 37,5% szybciej niż pierwotnie.
• Jednakże pięciokrotne ulepszenie części B, które wymaga jednak większego nakładu pracy i czasu, spowoduje ogólne zwiększenie prędkości wykonania jedynie 1,25 razy, co daje o 20% szybsze wykonanie.

Zobacz też

• prawo Gustafsona

Przypisy