Prawo Gustafsona

Prawo Gustafsona (znane także jako prawo Gustafsona-Barsisa) – prawo 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$ – liczba procesorów,

$S$ – przyspieszenie,

$\alpha$ – część 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 uwagę 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 koncepcję 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.

Interpretacja 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$ – część sekwencyjna,

$b$ – część równoległa, 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 80 km i spędził godzinę, pokonując połowę trasy z prędkością 40 km/h. Niezależnie jak szybko będzie jechał przez następną godzinę, jest niemożliwe aby osiągnął średnią prędkość 120 km/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ą 80 km/h.

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

• Przypuśćmy, że samochód podróżował przez pewien czas z prędkością mniejszą niż 120 km/h. Dając mu wystarczającą ilość czasu i zwiększając długość trasy, średnia prędkość samochodu może zawsze osiągnąć 120 km/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ą 40 km/h, może osiągnąć to jadąc z prędkością 160 km/h przez następne dwie godziny lub 200 km/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ące klastrów lub rozproszonych systemów obliczeniowych takich jak HTCondor.

Zobacz też

• inżynieria komputerowa
• prawo Amdahla

Linki zewnętrzne

• Reevaluating Amdahl’s Law. scl.ameslab.gov. [zarchiwizowane z tego adresu (2012-06-23)]. – dokument w którym John Gustafson po raz pierwszy opisał swoje prawo. Oryginalnie opublikowano w „Communications of the ACM” 31(5), 1988. s. 532–533
• Lawrence Snyder, Type Architectures, Shared Memory, and The Corrolary of Modest Potential.