Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.
Gdy procesorów będzie N, czas wykonywania kodu sekwencyjnego nie zmieni się, natomiast czas wykonania kodu „równoległego” zmniejszy się N-krotnie, co schematycznie zilustrowano na rysunku 8.41. Uzyskamy tym samym przyspieszenie wynoszące:
T + T
s
r
η =
T
T
r
+
s
N
Oznaczmy przez f „stopień sekwencyjności” programu, a przez T łączny czas jego wykonywania:
T
T = T +
s
Tr
f
s
= T
Mamy wówczas:
T
T
1
N
η =
=
=
=
T
T
−1
1−
r
( f )
f
Nf +1− f
T +
Tf +
f +
s
N
N
N
i ostatecznie:
N
η = 1+( N − )1 f
Dla f = 0 otrzymujemy przyspieszenie liniowe (η = N), dla f > 0 przyspieszenie jest z konieczności mniejsze od liniowego. Dla programu ściśle sekwencyjnego ( f = 1) przyspieszenie jest w ogóle niemożliwe (η = 1).
8.4. WIELOKOMPUTERY PRZEKAZUJĄCE KOMUNIKATY
693
RYSUNEK 8.41.
Przyspieszenie
programu
równoległego
w zależności
od stopnia jego
sekwencyjności
Ograniczenie wyrażone przez prawo Amdahla nie jest jedyną przyczyną prak-
tycznej nieosiągalności maksymalnego przyspieszenia. Oprócz innych tak oczywi-
stych przyczyn jak niezerowa wartość opóźnień i skończona wartość pasma transmisji dużą rolę grają ograniczenia wynikające ze sposobu tworzenia programów. Rzadko
który program napisany jest w ten sposób, że w nieskończoność sięgać może po ko-
lejne procesory, jeśli tylko są dostępne. Graniczna wartość liczby używanych procesorów wynikać może na przykład z rozmiaru zadeklarowanych struktur danych, lecz
tkwi ona organicznie w wielu wykorzystywanych algorytmach: przykładowo, poszu-
kiwanie wartości maksymalnej n liczb bądź obliczanie iloczynu skalarnego dwóch wektorów n-elementowych nie daje się podzielić na więcej niż n równoległych obliczeń i zwiększanie liczby procesorów ponad tę granicę jest z punktu widzenia takich programów mało interesujące. Co do samych algorytmów, często bywa tak, że najbardziej optymalny (pod względem złożoności obliczeniowej) algorytm rozwiązujący dany problem w ogóle nie poddaje się zrównolegleniu, daje się natomiast zrównole-glić inny algorytm dla tego problemu, lecz o znacznie większej złożoności. W efekcie zysk wynikający ze zrównoleglenia osłabiany jest konsekwencjami użycia subopty-malnego algorytmu. Można mówić o szczęściu, gdy dany program wolny jest od tego
rodzaju ograniczeń algorytmicznych i udaje się uzyskać jego n-krotne przyspieszenie przez zastosowanie 2 n czy 3 n procesorów. W końcu procesory są tanie, a poza tym —
ile firm tak naprawdę uzyskuje 100-procentową efektywność w swej działalności
biznesowej?
Uzyskiwanie dużej wydajności
Oczywistym zabiegiem mogącym zwiększyć wydajność systemu komputerowego jest
zwiększenie liczby wchodzących w skład niego procesorów. Zabieg ten okaże się
jednak skuteczny tylko wówczas, gdy zwiększanie liczby procesorów nie będzie
prowadzić do powstawania różnego rodzaju wąskich gardeł. System, w którym zasada i „dołożenie” nowych procesorów faktycznie skutkuje większą wydajnością, nazywamy systemem skalowalnym.
By lepiej zrozumieć niektóre implikacje skalowalności, rozpatrzmy najpierw zestaw czterech procesorów połączonych wspólną magistralą, jak na rysunku 8.42 (a). Wyobraźmy sobie, że w zamiarze zwiększenia wydajności systemu dołączono do wspo-
mnianej magistrali kolejnych 12 procesorów, co zilustrowano w części (b) rysunku.
694
ROZDZIAŁ 8. z ARCHITEKTURY KOMPUTERÓW RÓWNOLEGŁYCH
RYSUNEK 8.42. Przykładowe konfiguracje w kontekście skalowalności: (a) 4 procesory połączone wspólną magistralą; (b) 16 procesorów połączonych wspólną magistralą;
(c) 4 procesory połączone w kratę; (d) 16 procesorów połączonych w kratę
Jeśli przepustowość magistrali równa była b, to zwiększając liczbę procesorów z 4 do 16, powodujemy jednocześnie zredukowanie przypadającego na jeden procesor pasma
b
b
z
do
. System wielu procesorów połączonych jedną magistralą nie jest więc
4
16
skalowalny.
Przeprowadźmy analogiczne rozważania w odniesieniu do czterech procesorów
połączonych w kratę, jak w części (c) rysunku 8.42. Zwiększanie liczby procesorów powoduje jednocześnie dodawanie nowych łączy, dzięki czemu skalowanie systemu
nie powoduje spadku zagregowanej przepustowości, jak to miało miejsce w przypad-
ku pojedynczej magistrali. Wręcz przeciwnie: średnia liczba łączy przypadających na jeden procesor zwiększa się z 1 (4 łącza, 4 procesory) do 1,5 (24 łącza, 16 procesorów), a więc dołączenie nowych procesorów powoduje zwiększenie przepustowości
zagregowanej.
Przepustowość nie jest jednak jedynym kryterium wydajności, równie istotne jest
bowiem opóźnienie, ściśle związane ze średnicą sieci. Dołączanie nowych procesorów do magistrali nie zwiększa tej średnicy i opóźnienie sygnału wysyłanego na „pustą”
magistralę jest od liczby procesorów niezależne. Średnica sieci o topologii kraty i rozmiarze n × n węzłów równa jest 2( n–1), a więc opóźnienie (w najgorszym przypadku) zwiększa się w przybliżeniu proporcjonalnie do pierwiastka kwadratowego
z liczby węzłów (procesorów). Dla 400 połączonych w kratę procesorów średnica
sieci równa jest 38, zaś dla 1600 procesorów równa jest już 78; czterokrotne zwiększenie liczby procesorów powoduje dwukrotne (w przybliżeniu) zwiększenie średniego opóźnienia.
W idealnym przypadku skalowalny system powinien charakteryzować się jedna-