107
Architektury i algorytmy równoległe.
Komputery równoległe, w odróżnieniu od klasycznego
komputera szeregowego, nie majÄ… jednolitej
architektury.
Projektując algorytm rozwiązujący problem w sposób
równoległy, musimy zawsze odnieść się do konkretnej
architektury komputera równoległego.
1. Architektury równoległe
Komputer równoległy składa się z pewnej ilości (co najmniej
dwóch) procesorów, które prowadzą obliczenia jednocześnie
rozwiÄ…zujÄ…c ten sam problem.
Architekturę komputera równoległego określa się poprzez:
model sterowania,
organizacje przestrzeni adresowej,
rodzaj sieci Å‚Ä…czÄ…cej.
1.1. Modele sterowania
Wyróżniamy dwa modele sterowania procesami w
komputerach równoległych:
- sterowanie procesem przez centralnÄ… jednostkÄ™
sterujÄ…cÄ… komputera (rys. 53a),
- sterowanie procesorami przez lokalne, własne
jednostki sterujące procesorów (rys. 53b).
Centralna jednostka sterujÄ…ca
Procesor p1 Procesor p2 . . . Procesor pn
Sieć łącząca
Rys. 53a.
 108
Procesor p1 Procesor p2 Procesor pn
Jedn. steruj. Jedn. steruj. Jedn. steruj.
. . .
procesora p1 procesora p2 procesora pn
Sieć łącząca
Rys. 53b.
Rys. 53a. przedstawia tzw. architekturÄ™ SIMD (Single
Instruction Stream  Multiple Data Stream). W tej
architekturze wszystkie procesory wykonują jednocześnie ten
sam rozkaz, ale dla różnych zestawów danych.
Przykładem zadania dla takiej architektury może być
mnożenie macierzy A*B. Każdy z procesorów wykonuje w
tym samym czasie mnożenie jednego wiersza macierzy A
przez jednÄ… kolumnÄ™ macierzy B.
Przykładem zadania, które nie może być wykonywane
równolegle w tej architekturze jest jednoczesne wykonywanie
dla różnych zestawów danych { x, y } poniższej instrukcji:
if( x == y )wykonaj instrukcjÄ™ A; else wykonaj instrukcjÄ™ B;
Procesory, które stwierdzą, że x `" y, czekają aż zakończy się
wykonywanie instrukcji A przez procesory dla których x==y i
dopiero w następnym takcie wykonują instrukcję B (w tym
czasie procesory, dla których x == y, czekają aż zakończy się
wykonywanie instrukcji B). Procesory w architekturze SIMD
komunikują się przez sieć łączącą.
W architekturze MIMD (Multiple Instruction Stream 
Multiple Data Stream), rys. 53b, każdy procesor posiada
własną jednostkę sterującą i przechowuje zarówno program,
jak i system operacyjny. W tej architekturze każdy procesor
 109
może wykonywać w danej chwili inną (niż pozostałe
procesory) instrukcję dla właściwych dla tej instrukcji danych.
Rodzaj strumienia danych
Pojedynczy Grupowy
SISD SIMD Pojedynczy Rodzaj strumienia
instrukcji
MISD MIMD Grupowy
Rys. 54. Rodzaje konfiguracji architektur
Architektura SISD (Single Instruction Stream  Single Data
Stream) to architektura konwencjonalnego komputera, w
którym w danej chwili wykonywana jest tylko jedna instrukcja
dla pojedynczego zestawu danych.
Architektura MISD jest niepraktyczna  rzeczywiste
przetwarzanie równoległe może być realizowane jedynie w
architekturach typu SIMD i MIMD.
1.2. Organizacja przestrzeni adresowej
Procesory komputera równoległego mogą komunikować się
między sobą poprzez:
Modyfikację danych umieszczonych we wspólnej,
centralnej przestrzeni adresowej,
Przesyłanie sobie komunikatów.
W pierwszym przypadku mówimy o współdzieleniu
przestrzeni adresowej. Ta organizacja przestrzeni adresowej,
zwana UMA (Uniform Memory Access), musi zapewnić
jednolity dostęp do pamięci centralnej. Oprócz tego każdy
procesor może mieć pamięć lokalną (niedostępną dla innych
procesorów) do przechowywania lokalnych zmiennych.
W organizacji dostępu do pamięci typu NUMA (Non-
Uniform Memory Access) cała pamięć centralna podzielona
 110
jest na części (segmenty) przydzielone poszczególnym
procesorom, przy czym każdy procesor ma możliwość dostępu
do segmentu przydzielonego innym procesorom (!!!).
W organizacji pamięci, opartej na technice przesyłania
komunikatów, każdy procesor ma tylko lokalną pamięć,
niedostępną dla innych procesorów. Poszczególne procesory
komunikują się poprzez przesyłanie sobie danych i sygnałów a
nie poprzez modyfikacje danych we współdzielonych
obszarach pamięci.
1.3. Organizacja sieci Å‚Ä…czÄ…cej
Wyróżniamy dwa rodzaje sieci łączących w komputerze
równoległym:
Sieć statyczna,
Sieć dynamiczna.
Sieć statyczna zapewnia stałe i bezpośrednie połączenia
między procesorami. Sieci statyczne przeznaczone są przede
wszystkim dla komputerów równoległych, opartych na
technice przesyłania komunikatów. Wyróżniamy kilka
topologii sieci statycznej. Przykładowe przedstawia rys. 54.
a) b) c)
Rys. 55. Przykładowe topologie sieci łączących 4 stopnia
Sieć tworząca graf pełny (rys. 55a) zapewnia połączenia
każdego procesora z każdym innym. Jest to bardzo droga sieć,
gdyż ilość połączeń jest proporcjonalna do kwadratu ilości
procesorów. Zapewnia jednak największe bezpieczeństwo.
 111
Sieć typu gwiazda (rys. 55b) zawiera jeden węzeł centralny
(procesor), którego zadaniem jest przesyłanie komunikatów od
z
ródła do wybranego procesora. Wadą tej sieci jest mała
niezawodność.
Sieć typu siatka (rys. 55c) zapewnia bezpośrednie połączenie
tylko z najbliższymi procesorami.
Do obsługiwania komunikacji między procesorami w
architekturach o współdzielonej pamięci budowane są sieci
dynamiczne.
Segment
Segment Segment
pamięci 2
. . .
pamięci 1 pamięci m
Procesor p1
Procesor p2
. . .
Element
przełączający
Procesor pn
Rys. 56. Schemat dynamicznej sieci przełączającej
W sieci, przedstawionej na rys. 56, każdy z n procesorów
może uzyskać dostęp do jednego z m segmentów pamięci za
pomocą przełącznika. Sieć przełączników ma charakter nie
blokujÄ…cych siÄ™ wzajemnie. Rysunek 56 nie jest obrazem
wszystkich sieci dynamicznych. Dziedzina ta aktualnie bardzo
szybko siÄ™ rozwija.
 112
1.4. Architektura PRAM
Jak już zostało wspomniane  nie istnieje uniwersalna
architektura komputera równoległego. Istnieje jednak potrzeba
przyjęcia pewnego wzorca architektury, dla którego
budowane byłyby (zależne przecież od architektury)
algorytmy przetwarzania równoległego. Tę rolę spełnia
architektura PRAM.
Komputer PRAM składa się z n procesorów, z których każdy
ma jednakowy dostęp do wielkiej współdzielonej pamięci.
Procesory mają wspólny zegar (jest to więc komputer
synchroniczny),lecz nie muszą wykonywać w tym samym
cyklu tych samych instrukcji. PRAM jest więc komputerem
równoległym:
- w sensie modelu sterowania: typu MIMD,
- w sensie organizacji przestrzeni adresowej:
typu UMA,
- w sensie modelu sieci Å‚Ä…czÄ…cej;
typu dynamicznego.
Ponieważ PRAM ma współdzieloną pamięć, mogą pojawiać
się konflikty w chwili gdy kilka procesorów będzie próbowało
jednocześnie zapisać, lub odczytać, jakieś wartości w tym
samym miejscu współdzielonej pamięci. Wyróżniono cztery
modele obsługi jednoczesnych prób dostępu do pamięci w
architekturze PRAM:
model EREW (exlusive read  exlusive write)
dopuszcza tylko jeden procesor do tego
samego miejsca pamięci w tym samym czasie,
model ERCW (exlusive read  concurrent
write) dopuszcza wiele jednoczesnych
operacji zapisu i nie dopuszcza wielu jedno-
czesnych operacji odczytu,
 113
model CREW (concurrent read  exlusive
write) dopuszcza wiele jednoczesnych
operacji odczytu i nie dopuszcza wielu jedno-
czesnych operacji zapisu,
model CRCW (concurrent read  concurrent
write) dopuszcza jednoczesnÄ… realizacjÄ™
operacji wielu odczytów i wielu jednoczes-
nych operacji zapisu.
Najczęściej wykorzystywanymi modelami obsługi dostępu
do pamięci są modele CREW oraz CRCW.
Jeśli założymy, że każdy procesor może w jednym kroku nie
tylko wykonać jedną operację z ustalonego zbioru operacji, ale
uaktywnić (powołać) do realizacji inny procesor, to PRAM
może uaktywnić wykładniczą względem rozmiaru zadania
liczbę procesorów, co daje nieprawdopodobną moc
obliczeniowÄ….
2. Algorytmy równoległe
Przykład 1:
Zbudujmy w architekturze PRAM algorytm równoległy,
znajdujący w jednym takcie element największy w
n-elementowej tablicy nie powtarzajÄ…cych siÄ™ liczb
całkowitych A[1& N].
Aby móc jednocześnie porównać elementy tablicy  każdy z
każdym potrzeba n*(n-1)/2 procesorów. Dla tablicy
zawierającej N=4 elementów potrzeba 6 procesorów (rys. 57).
Oznaczmy procesory jako Pij gdzie 1d" i d" j d" N. Wyniki
d" d" d"
d" d" d"
d" d" d"
zapisywać będziemy do zero-jedynkowej tablicy T[1& N]
wypełnionej na początku wartościami 1.
Wynik porównania procesor Pij zapisuje do tablicy T w
następujący sposób:
T[i]=0 gdy A[i] < A[j], T[j]=0 gdy A[i] > A[j]
 114
Na k-tej pozycji tablicy T pozostanie jedynka tylko wtedy,
gdy element A[k] nie przegrał żadnego porównania z innymi
elementami tablicy A.
A
14 8 20 10
P12 P13 P14 P23 P24 P34
T
0 0 1 0
Rys. 57 Realizacja algorytmu z przykładu 1 dla przykładowej
4-elementowej tablicy liczb całkowitych.
Zauważmy, że w tym algorytmie dopuszczony został
jednoczesny odczyt i jednoczesny zapis przez wiele
procesorów. Problem jest więc rozwiązywany w architekturze
CRCW PRAM. Ponadto  że czas znalezienia największego
elementu nie zależy od rozmiaru tablicy A i jest stały.
Dokonuje się to na skutek udziału odpowiednio dużej liczby
procesorów.
2.1. Algorytmy równoległe  podstawy teoretyczne
Uważać będziemy, że algorytm obliczeń równoległych jest
zadany, gdy są określone:
- graf opisujący strukturę obliczeń,
- harmonogram realizacji obliczeń.
 115
Graf struktury obliczeń G=(W,A) jest grafem typu AGS
(acykliczny graf skierowany), gdzie:
W jest zbiorem wierzchołków opisujących operacje na
danych,
A jest zbiorem krawędzi (łuków) grafu.
Harmonogram realizacji obliczeń (który jak każdy
harmonogram odpowiada na pytania: gdzie? kto? kiedy? ) jest
zbiorem trójek
H(G,p)={ ( i Pi t i ): i"
"W \W0 Pi =1& p )
"
"
gdzie:
G jest grafem, dla którego sporządzono harmonogram,
p jest ilością użytych procesorów,
i jest numerem węzła grafu,
Pi jest numerem procesora, użytego w i-tym węz
le
grafu,
t i jest chwilą zakończenia operacji w i-tym węz
le
grafu,
W0 jest zbiorem wierzchołków wejściowych grafu.
Założenia:
1. Wierzchołkom wejściowym W0 nie przyporządkowuje
się żadnych procesów.
2. Czas wykonywania operacji w wierzchołkach wejścio-
wym W0 jest pomijany, w pozostałych wierzchołkach
zajmuje jednÄ… jednostkÄ™ czasu.
3. A
uk ( i , j )"
" A występuje, gdy operacja wykonywana w
"
"
wierzchołku j wykorzystuje bezpośrednio wynik
operacji w wierzchołku i.
4. Dla każdego łuku ( i , j )" A operacja j może być
"
"
"
wykonana dopiero po zakończeniu operacji i.
5. Każdy procesor wykonuje co najwyżej jedną operację w
danej jednostce czasu.
 116
Na ogół można zaproponować dla danego problemu kilka
różnych grafów obliczeniowych, jak również kilka
harmonogramów.
Niech IH(G,p) będzie zbiorem wszystkich możliwych
harmonogramów odpowiadających grafowi G i realizowanych
na komputerze zawierającym p procesorów.
Oznaczmy przez ti(H(G,p)) czas zakończenia operacji w
i-tym wierzchołku grafu G dla harmonogramu H(G,p).
Czas realizacji tego harmonogramu będzie równy
max(ti (H (G, p))
i"W
Def.
Złożonością obliczeniową (w znaczeniu całkowitego czasu
realizacji) algorytmu reprezentowanego przez graf G i
realizowanego za pomocą p procesorów nazywamy wielkość
Tp (G)= minIH max(ti (H (G, p))
H (G, p)" i"W
Tak zdefiniowana złożoność obliczeniowa zależy od postaci
grafu realizującego obliczenia i od ilości użytych procesorów.
Wprowadz
my wielkość
T"(G)=min(Tp (G))
pe"1
Tak zdefiniowana złożoność obliczeniowa zależy już tylko
od użytej postaci grafu obliczeniowego. Wyraża ona
minimalną złożoność obliczeniową przy różnych
harmonogramach i ilości procesorów  w stanie nasycenia
(gdy dalsze zwiększanie ilości procesorów nie zmniejsza już
całkowitego czasu obliczeń).
Dla każdego grafu G istnieje więc taka liczba procesorów
pmax że
" T"(G) = Tp (G)
max
pe"pmax
 117
Tp (G)
Wielkość możemy więc uznać za złożoność
max
obliczeniową algorytmu równoległego z grafem G, gdy
dostępna jest dostatecznie duża liczba procesorów (np. w
architekturze PRAM).
T1(G)
Zauważmy, że jest równe czasowi obliczeń
(złożoności obliczeniowej) algorytmu sekwencyjnego,
realizowanego wg. grafu G na pojedynczym procesorze. Czas
ten będzie równy
T1(G)=card(W \W0)
Def.
Głębokością grafu D(G) typu AGS nazywamy długość
najdłuższej drogi w tym grafie.
Dla algorytmu równoległego o strukturze obliczeniowej
opisanej grafem G zachodzi
T"(G)=D(G)
Przykład 2:
Zbudować algorytm równoległy obliczający dla danych
wartości wejściowych x1 x2 x3 wartość wyrażenia algebra-
icznego
E=(x1+x2)*(x1+x3)
Możliwe są dwie postacie grafów, opisujących strukturę
obliczeń
x1 x2 x3
1 2 3
Warstwa W0
x1 +x2 x2 +x3
4 + 5 +
Graf G1
E
6 *
 118
Dla grafu G1 mamy:
W={1,2,3,4,5,6} W0 ={1,2,3}
A={ (1,4),(2,4), (2,5), (3,5), (4,6), (5,6)}
Wybierzmy jeden procesor, teraz:
H1(G1,1)={(4,1,1), (5,1,2), (6,1,3)}
max(ti (H1(G1,1))=card(W \W0)=3
i"W
Dla dwóch procesorów:
H2(G1,2)={(4,1,1), (5,2,1), (6,1,2)}
max(ti (H2(G1,2))=2
i"W
Dalsze budowanie nowych harmonogramów poprzez
zwiększanie ilości procesorów nie zmniejszy czasu obliczeń,
T"(G1)=D(G1)=T2(G1)=2
czyli
Możliwe jest zbudowanie drugiego grafu w oparciu o
przekształcenie
2
E=(x1+x2)*(x2+x3)=x1 * x2+x2+x1 * x3+x2 * x3
x1 x3
x2
1 3
2
x22 x2*x3
x1*x2 x1*x3
6 *
5 Ń!
Ń!
Ń!
Ń!
4 * 7 *
E1 E2
Graf G2
8 + 9 +
E
10 +
 119
Dla grafu G2 wybierzmy jeden procesor, teraz:
max(ti (H1(G2,1))=card(W \W0)=7
i"W
Dla dwóch procesorów:
H2(G2,2)={(4,1,1), (5,2,1), (6,1,2), (7,2,2), (8,1,3), (9,2,3),
(10,1,4)}
max(ti (H2(G2,2))=4
i"W
Dla czterech procesorów:
H4(G2,4)={(4,1,1), (5,2,1), (6,3,1), (7,4,1), (8,1,2), (9,2,2),
(10,1,3)}
max(ti (H4(G2,2))=3
i"W
Dalsze budowanie nowych harmonogramów poprzez
zwiększanie ilości procesorów nie zmniejszy czasu obliczeń,
T"(G2)=D(G2)=T4(G2)=3
czyli
Przykład nr 2 pokazuje, w jaki sposób o jakości algorytmu
równoległego (jego złożoności obliczeniowej) decyduje wybór
struktury obliczeniowej (grafu). W tym przykładzie lepszym
okazał się graf G1 pozwalający obliczyć wartość wyrażenia w
czasie 2 przy użyciu 2 procesorów.
Wyznaczenie optymalnego grafu należy w ogólnym
przypadku do tzw. zadań trudnych i nie jest wykonywalne w
czasie wielomianowym. Stosunkowo Å‚atwo daje siÄ™ jednak
sformułować dla takich zadań algebry liniowej, jak:
n
"x * yi ,
i
- obliczanie iloczynu skalarnego wektorów
i=1
- mnożenie macierzy C = A * B.
 120
Dla bardziej złożonych zadań obliczeniowych algebry
liniowej i zadań optymalizacyjnych, algorytmy równoległe
bazują na formułach iteracyjnych Jacobiego i Gaussa-Seidla.
Bardzo interesujący jest model obliczeń równoległych oparty
na sieci bramek logicznych.
K o n i e c w y k Å‚ a d u