Teoretyczne podst inform cz V

[ Pobierz całość w formacie PDF ]
51
Architektury i algorytmy rwnolegþe
€
Komputery rwnolegþe, w odrŇnieniu od klasycznego
komputera szeregowego, nie majĢ jednolitej
architektury.
€
ProjektujĢc algorytm rozwiĢzujĢcy problem w sposb
rwnolegþy, musimy zawsze odnieĻę siħ do konkretnej
architektury komputera rwnolegþego.
1. Architektury rwnolegþe
Komputer rwnolegþy skþada siħ z pewnej iloĻci (co najmniej
dwch) procesorw, ktre prowadzĢ obliczenia jednoczeĻnie
rozwiĢzujĢc ten sam problem.
Architekturħ komputera rwnolegþ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 rwnolegþych:
- sterowanie procesem przez centralnĢ jednostkħ
sterujĢcĢ komputera (rys. 1a),
-
sterowanie procesorami przez lokalne, wþasne
jednostki sterujĢce procesorw (rys. 1b).
Centralna jednostka sterujĢca
. . .
Procesor p
n
Sieę þĢczĢca
Rys. 1a.
Procesor p
1
Procesor p
2
52
Procesor p
1
Jedn. steruj.
procesora p
1
Procesor p
2
Jedn. steruj.
procesora p
2
Procesor p
n
Jedn. steruj.
procesora p
n
Sieę þĢczĢca
Rys. 1b.
Rys. 1a. przedstawia tzw. (Single
Instruction Stream Î Multiple Data Stream). W tej
architekturze wszystkie procesory wykonujĢ jednoczeĻnie ten
sam rozkaz, ale dla rŇnych zestaww danych.
Przykþadem zadania dla takiej architektury moŇe byę
mnoŇenie macierzy A*B. KaŇdy z procesorw wykonuje w
tym samym czasie mnoŇenie jednego wiersza macierzy A
przez jednĢ kolumnħ macierzy B.
Przykþadem zadania, ktre nie moŇe byę wykonywane
rwnolegle w tej architekturze jest jednoczesne wykonywanie
dla rŇnych zestaww danych { x, y } poniŇszej instrukcji:
if( x == y )wykonaj instrukcjħ A; else wykonaj instrukcjħ B;
Procesory, ktre stwierdzĢ, Ňe x
y, czekajĢ aŇ zakoıczy siħ
wykonywanie instrukcji A przez procesory dla ktrych x==y i
dopiero w nastħpnym takcie wykonujĢ instrukcjħ B (w tym
czasie procesory, dla ktrych x == y, czekajĢ aŇ zakoıczy siħ
wykonywanie instrukcji B). Procesory w architekturze SIMD
komunikujĢ siħ przez sieę þĢczĢcĢ.
W architekturze (Multiple Instruction Stream Î
Multiple Data Stream), rys. 1b, kaŇdy procesor posiada wþasnĢ
jednostkħ sterujĢcĢ i przechowuje zarwno program, jak i
system operacyjny. W tej architekturze kaŇdy procesor moŇe
. . .
53
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
MISD MIMD Grupowy
Rodzaj strumienia
instrukcji
Rys. 2. Rodzaje konfiguracji architektur
A (Single Instruction Stream Î Single Data
Stream) to architektura konwencjonalnego komputera, w
ktrym w danej chwili wykonywana jest tylko jedna instrukcja
dla pojedynczego zestawu danych.
Architektura jest niepraktyczna Î rzeczywiste
przetwarzanie rwnolegþe moŇe byę realizowane jedynie w
architekturach typu i.
1.2. Organizacja przestrzeni adresowej
Procesory komputera rwnolegþego mogĢ komunikowaę siħ
miħdzy sobĢ poprzez:
€
Modyfikacjħ danych umieszczonych we wsplnej,
centralnej przestrzeni adresowej,
€
Przesyþanie sobie komunikatw.
W pierwszym przypadku mwimy o
o. Ta organizacja przestrzeni adresowej
zwana jest (Uniform Memory Access), czyli musi
zapewnię jednolity dostħp do pamiħci centralnej. Oprcz tego
kaŇdy procesor moŇe mieę pamiħę lokalnĢ (niedostħpnĢ dla
innych procesorw) do przechowywania lokalnych
zmiennych.
54
W organizacji dostħpu do pamiħci typu (Non-
Uniform Memory Access) caþa pamiħę centralna podzielona
jest na czħĻci (segmenty) przydzielone poszczeglnym
procesorom, przy czym kaŇdy procesor ma moŇliwoĻę dostħpu
do segmentu przydzielonego innym procesorom (!!!).
W organizacji pamiħci, opartej na
o, kaŇdy procesor ma tylko lokalnĢ pamiħę,
niedostħpnĢ dla innych procesorw. Poszczeglne 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
rwnolegþym:
€
Sieę statyczna,
€
Sieę dynamiczna.
zapewnia staþe i bezpoĻrednie poþĢczenia
miħdzy procesorami. Sieci statyczne przeznaczone sĢ przede
wszystkim dla komputerw rwnolegþych, opartych na
technice przesyþania komunikatw. WyrŇniamy kilka
topologii sieci statycznej. Przykþadowe przedstawia rys. 3.
a) b) c)
Rys. 3. Przykþadowe topologie sieci þĢczĢcych 4 stopnia
Sieę tworzĢca graf peþny (rys. 3a) zapewnia poþĢczenia
kaŇdego procesora z kaŇdym innym. Jest to bardzo droga sieę,
 55
gdyŇ iloĻę poþĢczeı jest proporcjonalna do kwadratu iloĻci
procesorw. Zapewnia jednak najwiħksze bezpieczeıstwo.
Sieę typu gwiazda (rys. 3b) zawiera jeden wħzeþ centralny
(procesor), ktrego zadaniem jest przesyþanie komunikatw od
Ņrdþa do wybranego procesora. WadĢ tej sieci jest maþa
niezawodnoĻę.
Sieę typu siatka (rys. 3c) 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
pamiħci 1
Segment
pamiħci 2
Segment
pamiħci m
Procesor p
1
Procesor p
2
. . .
Element
przeþĢczajĢcy
Rys. 4. Schemat dynamicznej sieci przeþĢczajĢcej
W sieci, przedstawionej na rys. 4, kaŇdy z n procesorw
moŇe uzyskaę dostħp do jednego z m segmentw pamiħci za
pomocĢ przeþĢcznika. Sieę przeþĢcznikw ma charakter nie
blokujĢcych siħ wzajemnie. Rysunek 4 nie jest obrazem
wszystkich sieci dynamicznych. Dziedzina ta aktualnie bardzo
szybko siħ rozwija.
Procesor p
n
[ Pobierz całość w formacie PDF ]