Prawo Gustafsona

Prawo Gustafsona (znane także jako prawo Gustafsona-Barsisa) jest prawem w inżynierii komputerowej, które stanowi, że każdy wystarczająco duży problem może być efektywnie zrównoleglony. Prawo Gustafsona jest ściśle związane z prawem Amdahla, które określa limit przyspieszenia spowodowanego zrównolegleniem. Zostało po raz pierwszy sformułowane przez J. Gustafsona w 1988 roku.

$S(P)=P-\alpha \cdot (P-1)$.

gdzie P jest liczbą procesorów, S jest przyspieszeniem a $\alpha$ częścią procesu której nie da się zrównoleglić.

Prawo Gustafsona odnosi się do wad prawa Amdahla, które nie jest skalowalne do tego stopnia, aby brać pod uwage dostępność mocy obliczeniowej przy rozrastaniu się maszyny. Usuwa problem ustalonego rozmiaru problemu lub ustalonego ładowania obliczeń na równoległych procesorach: zamiast tego, proponuje koncepcje ustalonego czasu, która prowadzi do skalowanego przyspieszenia.

Prawo Amdahla bazuje na ustalonym obciążeniu roboczym lub znanym rozmiarze problemu. Wynika z tego, że sekwencyjna część programu nie zmienia się wraz z rozmiarem maszyny (np. liczba procesorów), natomiast zrównoleglona część jest równomiernie rozdzielona na n procesorów.

Efektem prawa jest przesunięcie w rozwoju tworzenia zrównoleglających kompilatorów i redukcja szeregowych części rozwiązań w celu poprawy wydajności systemów równoległych.

Implementacja prawa Gustafsona

Niech n będzie miarą rozmiaru problemu.

Przetwarzanie programu na równoległym komputerze zostaje zdekomponowane do:

$a(n)+b(n)=1$

gdzie a jest częścią sekwencyjną a b częścią równoległą, na razie ignorując narzut.

Na sekwencyjnym komputerze, odpowiedni czas przedstawia się jako $a(n)+p\cdot b(n)$ gdzie p jest liczbą procesorów w przypadku zrównoleglenia.

W takim przypadku przyspieszenie wynosi:

$(a(n)+p\cdot {}b(n))$ (zrównoleglenie, odpowiednie dla sekwencyjnego $a(n)+b(n)=1$)

a więc

$S=a(n)+p\cdot {}(1-a(n))$

gdzie $a(n)$ jest funkcją szeregującą.

Zakładając że funkcja szeregująca $a(n)$ zmniejsza się wraz z rozmiarem problemu n, przyspieszenie zmierza do p jako że n zmierza do nieskończoności, jak zamierzono.

W związku z tym, prawo Gustafsona próbuje ratować przetwarzanie równoległe przed efektem prawa Amdahla.

Prawo Gustafsona utrzymuje, że nawet użycie masowych równoległych systemów komputerowych, nie wpływa na szeregową część programu, której czas wykonania jest stały. Tak więc, hipoteza zawarta w prawie Amdahla wynika z pomysłu, że wpływ części szeregowej rośnie wraz ze wzrostem liczby procesorów.

Metafora kierowcy

Prawo Amdahla (w przybliżeniu) proponuje:

• Przypuśćmy, że samochód podróżuje między dwoma miastami odległymi od siebie 80km i spędził godzinę, pokonując połowę trasy z prędkością 40km/h. Niezależnie jak szybko będzie jechał przez następną godzinę, jest niemożliwe aby osiągnął średnią prędkość 120km/h przed dotarciem do drugiego miasta. Ze względu na fakt, że do tej pory jechał godzinę i ma za sobą 40 kilometrów, jadąc nieskończenie szybko, może osiągnąć maksymalną prędkość równą 80km/h.

Prawo Gustafsona (w przybliżeniu) stanowi że:

• Przypuśćmy, że samochód podróżował przez pewien czas z prędkością mniejszą niż 120km/h. Dając mu wystarczającą ilość czasu i zwiększając długość trasy, średnia prędkość samochodu może zawsze osiągnąć 120km/h, niezależnie jak długo i jak wolno podróżował do tej pory. Na przykład, jeśli samochód spędził godzinę, jadąc z prędkością 40km/h, może osiągnąć to jadąc z prędkością 160km/h przez następne dwie godziny lub 200km/h przez godzinę itd.

Ograniczenia

Niektóre problemy nie posiadają zasadniczo większych zbiorów danych. Na przykład, przetwarzanie jednego punktu danych na jednego mieszkańca świata, zwiększa się tylko o mały procent rocznie.

Nieliniowe algorytmy mogą sprawiać trudność w korzystaniu z zalet równoległości ukazanych przez prawo Gustafsona. Snyder wykazał że algorytmy o złożoności obliczeniowej O(N³) przy podwojeniu współbieżności osiągają tylko 9% wzrostu w rozmiarze problemu. Tak więc, podczas gdy możliwe jest duże wykorzystanie współbieżności, może to przynieść jedynie niewielkie korzyści, nad oryginalnym, mniej współbieżnym rozwiązaniem -- jednak w praktyce występują masowe usprawnienia, szczególnie używając klastrów lub rozproszonych systemów obliczeniowych takich jak Condor.

Zobacz też

• inżynieria komputerowa
• prawo Amdahla

Linki zewnętrzne

• Reevaluating Amdahl's Law - dokument w którym John Gustafson po raz pierwszy opisał swoje prawo. Oryginalnie opublikowano w Communications of the ACM 31(5), 1988. pp. 532-533
• [1] -- Lawrence Snyder, "Type Architectures, Shared Memory, and The Corrolary of Modest Potential"