OBLICZENIA RÓWNOLEGŁE
I ROZPROSZONE
Temat 2:
Projektowanie algorytmów równoległych -
wprowadzenie
Prowadzący:
dr inż. Zbigniew TARAPATA
pok.225, 306, tel.: 83-95-04
e-mail:
Zbigniew.Tarapata@wat.edu.pl
http://
tarapata.
tarapata.
strefa
strefa
.pl
.pl
/
/
p_obliczenia_rownolegle_i_rozproszone
p_obliczenia_rownolegle_i_rozproszone
/
/
2
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Plan wykładu
Algorytmy i systemy równoległe –
wprowadzenie;
Algorytmy i systemy równoległe – własności;
Algorytmy i systemy równoległe –
równoległość a
współbieżność, równoległość a rozproszoność;
Podstawowe pojęcia z teorii obliczeń
równoległych – graf AGS jako reprezentacja algorytmu
równoległego;
Podstawowe pojęcia z teorii obliczeń
równoległych – miary efektywności algorytmu
równoległego;
3
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Metody zwiększania efektywności algorytmów -
przypomnienie
Wyróżniamy dwie zasadnicze
metody zwi
metody zwi
ę
ę
kszania
kszania
efektywno
efektywno
ś
ś
ci algorytm
ci algorytm
ó
ó
w
w
:
umiejętne zaprojektowanie algorytmu poprzez
stosowanie odpowiednich :
-
struktur danych
(listy, drzewa, kolejki, itp.),
-
technik projektowania algorytmów
(np. dziel i
zwyciężaj,
zrównoleglanie
, derekursywacja,
itp.);
optymalizacja kodu programu realizującego
algorytm
(zmniejszanie liczby pętli, zastępowanie operacji
arytmetycznych, eliminowanie zmiennych indeksowanych,
umieszczanie wartownika na końcu tablicy, przekazywanie parametrów
funkcji przez wskaźniki, itp.);
4
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Przykład (sortowanie, n – rozmiar tablicy)
Umiejętne projektowanie algorytmów, przykład 1
-
wykorzystanie odpowiednich struktur danych
-
- wykorzystywane są kopce
binarne
W
α
(n) = O(n log n)
przez kopcowanie
(heapsort)
-
- działa „w miejscu”
-
- dla dużych tablic
-
- oparty o technikę „dziel i
zwyciężaj”
W
α
(n) =
Θ(n
2
)
A
α
(n) =
Θ(n log n)
szybkie (quicksort)
-
- nie działa w miejscu
-
- oparty o technikę „dziel i
zwyciężaj”
W
α
(n) =
Θ(n log n)
przez scalanie
-
- działa „w miejscu” (tzn. tylko
stała liczba elementów tablicy jest
przechowywana poza tablicą
podczas działania algorytmu)
-
- dla małych tablic
W
α
(n) =
Θ(n
2
)
- przez proste
wstawianie
- bąbelkowe
Uwagi
Złożoność
Nazwa algorytmu
α
5
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Sortowanie bąbelkowe
– wykorzystując N/2 (=4)
procesorów przyspieszamy porównywanie
parami elementów tablicy
Umiejętne projektowanie algorytmów, przykład 2
-
wykorzystanie wielu procesorów = zrównoleglanie
93
87
74
65
57
45
33
27
93
87
74
65
57
45
33
27
1
93
87
74
65
57
45
33
27
2
6
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Umiejętne projektowanie algorytmów, przykład 2,
c.d.
-
wykorzystanie wielu procesorów = zrównoleglanie
93
87
74
65
57
45
33
27
3
93
87
74
65
57
45
33
27
4
93
87
74
65
57
45
33
27
5
93
87
74
65
57
45
33
27
6
93
87
74
65
57
45
33
27
7
93
87
74
65
57
45
33
27
8
7
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Umiejętne projektowanie algorytmów, przykład 2,
c.d.
-
wykorzystanie wielu procesorów = zrównoleglanie
WNIOSKI
Sekwencyjny algorytm sortowania bąbelkowego
tablicy N-elementowej potrzebuje w najgorszym
przypadku N
2
czasu.
Równoległy algorytm sortowania bąbelkowego
tablicy N-elementowej potrzebuje w najgorszym
przypadku N czasu
(pomijamy aspekty komunikacyjne między procesorami).
Sortowanie
bąbelkowe –
alg. sekwencyjny
Alg.
równoległy
O(N
2
)
O(N)
8
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe - wprowadzenie
CZAS NA BLIŻSZE PRZYJRZENIE SIĘ ALGORYTMOM
RÓWNOLEGŁYM ☺
Używamy wielu procesorów do rozwiązania
pojedynczego zadania (ang. task).
ISTOTA:
Dzielimy zadanie na mniejsze „kawałki”;
Wykonujemy obliczenia na wielu
procesorach (np. każdy „kawałek”
obliczany jest na oddzielnym procesorze);
Koordynujemy zadania cząstkowe i ich
wyniki przekazujemy do zadania
nadrzędnego (koordynującego).
9
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
1
2
3
4
1
2
3
4
Procesory
Zadania
Algorytmy i systemy równoległe - wprowadzenie,
c.d.
10
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
CPU
Pamięć
Interfejs
sieciowy
Algorytmy i systemy równoległe – wprowadzenie,
c.d. - struktura systemu obliczeń równoległych
11
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe - własności
Korzystanie z systemów obliczeń równoległych
nie
nie
wyprowadza nas poza klasyfikacj
wyprowadza nas poza klasyfikacj
ę
ę
opart
opart
ą
ą
na
na
z
z
ł
ł
o
o
ż
ż
ono
ono
ś
ś
ci obliczeniowej
ci obliczeniowej
dla obliczeń
sekwencyjnych.
U
U
ż
ż
ywanie wielu procesor
ywanie wielu procesor
ó
ó
w
w
przyspiesza (czasami ☺)
rozwiązywanie problemów lecz
nie zmienia
nie zmienia
ich
przynale
przynale
ż
ż
no
no
ś
ś
ci do klasy z
ci do klasy z
ł
ł
o
o
ż
ż
ono
ono
ś
ś
ci obliczeniowej
ci obliczeniowej
.
Jakich korzy
Jakich korzy
ś
ś
ci dostarcza zr
ci dostarcza zr
ó
ó
wnoleglenie oblicze
wnoleglenie oblicze
ń
ń
?
Mając algorytm działający w czasie O(N logN)
i log N procesorów, algorytm równoległy
będzie potrzebował
co najmniej
O(N) czasu.
Mając algorytm działający w czasie O(N
3
) i N
procesorów, algorytm równoległy będzie
potrzebował
co najmniej
O(N
2
) czasu.
12
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Liczba procesorów jest ograniczona
sprzętowo
;
Zazwyczaj liczba procesorów jest potęgą
2;
Wpływ dodawania nowych procesorów:
Program na jednym procesorze
Uruchamia się w czasie X;
Dodając dodatkowy procesor
Uruchamia się w czasie
nie mniejszym niż
X/2;
W praktyce: w czasie X/2 +
ε z powodu
„kosztów zrównoleglenia”
W skrajnych przypadkach, dodanie procesorów
może nie pomóc, a wręcz spowolnić działanie
programu !!!
Algorytmy i systemy równoległe – własności
Liczba procesorów
13
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe – własności
Koszty zrównoleglenia obliczeń
Zrównoleglenie
niesie za sobą pewne koszty
.
Procesory muszą być
sterowane i
koordynowane.
Musimy wskazać każdemu procesorowi, co w
każdej chwili ma robić; to wymaga
dodatkowego
wysiłku
(czasu, kosztu, itp.)
.
Często program musi być napisany w
specjalnym języku programowania
dla
systemów równoległych (np. w języku Modest).
Często program równoległy (np. z 2
K
procesorami) nie będzie pracował na innym
komputerze (np. z 2
L
procesorami).
14
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe –
Równoległość, a współbieżność
Współbieżność
polega na
wykonywaniu wielu zadań w tym
samym czasie, niezależnie od liczby
użytych procesorów.
Zrównoleglenie
polega na
wykonywaniu tego samego zadania
na wielu procesorach
.
15
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe –
Równoległość, a rozproszoność
Zazwyczaj nie do
pominięcia
Pomijalnie małe
Op
Op
ó
ó
ź
ź
nienia
nienia
komunikacyjne
komunikacyjne
mała
duża
Ingerencja sterowania
Ingerencja sterowania
centralnego
centralnego
mała
duża
Niezawodno
Niezawodno
ść
ść
pol
pol
ą
ą
cze
cze
ń
ń
Może ulegać
zmianom w czasie
Nie ulega zmianom
w czasie
Struktura po
Struktura po
łą
łą
cze
cze
ń
ń
Zazwyczaj duże
małe
Odleg
Odleg
ł
ł
o
o
ś
ś
ci mi
ci mi
ę
ę
dzy
dzy
procesorami
procesorami
Syst
Syst
. oblicz.
. oblicz.
rozproszonych
rozproszonych
Syst
Syst
. oblicz.
. oblicz.
r
r
ó
ó
wnoleg
wnoleg
ł
ł
ych
ych
Rodzaj
Cechy
systemu
charakteryst.
16
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe –
Podstawowe kryteria podziału systemów równoległych
Liczba i rodzaj procesorów:
- tysiące procesorów;
- do 10-ciu procesorów;
Obecność sterowania centralnego:
- duża ingerencja systemu w pracę procesorów
(system decyduje co każdy procesor ma
wykonywać w każdej chwili);
- mała ingerencja systemu w pracę procesorów;
Obecność synchronizacji obliczeń:
- systemy synchroniczne;
- systemy asynchroniczne.
17
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe –
Podstawowe kryteria podziału systemów równoległych, c.d.
Wymiana informacji między procesorami
(komunikacja poprzez sieć połączeń –
wybór
struktury połączeń jest zadaniem projektowym
):
- podział wspólnej pamięci między procesory oraz
obecność systemu przełączającego;
- każdy procesor ma własną pamięć.
18
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
*)
S – Single,
M – Multiple,
I – Instruction,
D – Data.
Rodzaj strumienia danych
*)
pojedynczy grupowy
pojedynczy
SISD
SIMD
Rodzaj
strumienia
instrukcji
grupowy
MISD
MIMD
Algorytmy i systemy równoległe –
Podstawowe kryteria podziału systemów równoległych, c.d.
19
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytmy i systemy równoległe –
Podział komputerów typu MIMD
Sposób komunikacji poprzez
Wspólne
zmienne
Przesyłanie
komunikatów
globalna
GMSV
„Shared Memory”
GMMP
Sposób
organizacji
pamięci
rozproszona
DMSV
„Hybrid”
DMMP
„Message passing”
20
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Intel ASCI Red
(Accelerated Strategic
Computing Initiative) – 1996-2010 r., do
modelowania zjawisk związanych
z zastosowaniem broni jądrowej
(9632 procesory P II Xeon 333 MHz,
moc: 2,3 T FLOPS
*)
;
rozwiązanie układu 215 000 równań liniowych
zajęło 100 min., ale użyto procesorów 200 MHz
×
7 000);
*)
dla porównania:
- procesor PENTIUM-IV 1 GHz ma moc
∼1,4 G FLOPS (1,4⋅10
9
FLOPS)
- moc Deep Blue z 1997 r.:
∼ 10 G FLOPS.
Algorytmy i systemy równoległe –
Przykłady zastosowań
21
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
IBM SP ASCI Blue Pacific
(Lawrence Livermore
National Laboratory) –system RS/6 000, 4
× 1464
Power PC 332 MHz,
moc: 2,1 T FLOPS
RAM: 2,6 TB,
koszt: 94 mln $,
powierzchnia: 740 m
2
,
Algorytmy i systemy równoległe –
Przykłady zastosowań
22
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
IBM ASCI White
: 8192 procesory IBM Power3-III
375 MHz,
moc: 10 T FLOPS,
RAM: 6TB (pamięć zewnętrzna: 160 TB),
koszt: 100 mln $,
powierzchnia: ok. 1000m
2
,
waga: 106 ton,
pobierany prąd: 1.2 MW
Ciekawostka nr 1:
wierne zasymulowanie wybuchu jądrowego
zajmuje ASCI White miesiąc !!!
Dla porównania Cray z 1995 roku liczyłby to
samo przez 60 tys. lat!!
Algorytmy i systemy równoległe –
Przykłady zastosowań
23
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Najszybszy do niedawna system na świecie (od 2002r.-
do2007r.):
japoński Earth Simulator
(do symulacji
złożonych zjawisk geologicznych i pogodowych),
moc: 40 T FLOPS,
koszt: 350 mln $.
W ramach programu „Blue Gene” firmy IBM
:
powstał w 2007 r. (na bazie 212992 x PowerPC 440
770MHz);
73728 GB pamięci;
maszyna o wydajności 0,5 PFLOPS (0,5*10
15
FLOPS) do
analizy genomu ludzkiego
*)
.
*)
Źródło: http://www.top500.org.
Algorytmy i systemy równoległe –
Przykłady zastosowań
24
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Najszybszy obecnie system na świecie (11.2008):
Roadrunner
Roadrunner
BladeCenter
BladeCenter
QS22
QS22
Cluster
Cluster
,
Miejsce: DOE/NNSA/LANL (Los Alamos, USA);
129600 x PowerXCell 8i 3.2 Ghz, OS Linux;
moc: 1,1 PFLOPS (10
15
FLOPS) !!!!!!!
Najszybszy w Polsce system (łącznie z Polski 6 na liście top500,
11.2008):
Galera ACTION Cluster Xeon E5345 Infiniband (67 miejsce.
11.2008);
Politechnika Gdańska;
Pamięć: 5376 GB;
Procesory: 5336 x Intel EM64T Xeon 53xx (Clovertown) 2333
MHz (9.332 GFlops);
OS: Linux;
Moc: 38 GFLOPs;
*)
*)
Źródło: http://www.top500.org
Algorytmy i systemy równoległe –
Przykłady zastosowań
25
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład
(problem doboru topologii sieci komunikacyjnej)
Topologie połączeń MIMD: a) pierścień b) siatka c) drzewo d) hipersześcian
26
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład
(problem doboru topologii sieci komunikacyjnej), c.d.
Łączność (długość najkrótszej z dróg między dowolną parą wierzchołków)
w warunkach najgorszego przypadku
16 skoków
254 skoki
16384
11 skoków
126 skoków
2048
10 skoków
62 skoki
1024
8 skoków
30 skoków
256
4 skoki
6 skoków
16
Hipersześcian
Siatka
Liczba węzłów
27
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład
(problem doboru topologii sieci komunikacyjnej), c.d.
Chcemy dodać do siebie 8 liczb x
1
, x
2
,...,x
8
.
(a)
(b)
Dwie możliwe topologie sieci komunikacyjnej: (a) i (b)
x
1
+x
2
x
3
+x
4
x
5
+x
6
x
7
+x
8
Porównanie topologii (a) i (b):
•Dla topologii
(a) uszkodzenie tylko jednego wierzchołka
(procesora) może spowodować, że
cała sieć
„rozpadnie się”
na dwie części nie mogące komunikować się między sobą.
Graf
z rysunku (b) może działać dalej nawet jeśli dwa procesory są uszkodzone
;
•Największa odległość między parą wierzchołków (mierzona za pomocą liczby krawędzi w drodze je
łączącej) w grafie (a) wynosi 4 (dla dwóch wierzchołków) podczas, gdy w grafie (b) ta odległość wynosi 3.
28
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Zanurzenie sieci (a) w sieć (b).
Wierzchołki g, s, d są obrazami, odpowiednio,
wierzchołków górnego, środkowych i dolnych
grafu.
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład
(problem doboru topologii sieci komunikacyjnej), c.d.
g
s
d
d
s
d
d
x
1
+x
2
x
3
+x
4
x
5
+x
6
x
7
+x
8
29
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
AGS
- acykliczny graf skierowany G,
W - zbiór wierzchołków oznaczających
operacje wykonywane na danych,
A - zbiór łuków oznaczających zależności
między danymi,
Głębokością D
grafu AGS nazywamy
długość najdłuższej drogi w G.
A
W
G
,
=
∈
=
i
olku
w wierzch
operacji
wynik
e
ykorzystuj
w
j
ku
wierzchol
operacja w
:
)
,
(
2
W
j
i
A
30
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
p – potęgowanie
* – mnożenie
+ – dodawanie
Weźmy zadanie obliczeniowe:
Przykładowy graf AGS:
( )
3
3
2
2
1
2
1
x
x
x
x
x
x
f
⋅
+
⋅
+
=
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład 1
1
2
3
4
5
6
7
8
9
10
31
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Przyjmijmy oznaczenia:
x
i
- wynik operacji wykonywanej w wierzchołku
i grafu AGS;
f
i
- operacja związana z wierzchołkiem i;
P
i
- numer procesora przyporządkowanego do
wykonywania operacji w i-tym wierzchołku,
(W
0
- zbiór wierzchołków wejściowych);
t
i
- chwila zakończenia operacji w i-tym
wierzchołku.
o
W
W
i
\
∈
32
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Założenia:
wierzchołkom wejściowym nie są
przyporządkowane żadne procesory;
chwila t
i
zakończenia operacji w każdym
wierzchołku wejściowym jest równa 0;
każdy procesor wykonuje co najwyżej jedną
operację w danej chwili, tzn. jeżeli ,
oraz ,
to ;
jeżeli
, to
co oznacza, że
operacja związana z wierzchołkiem j może być
wykonana dopiero po wykonaniu operacji
związanej z i-tym wierzchołkiem.
o
W
W
j
i
\
,
∈
j
i
≠
j
i
P
P
≠
Podstawowe pojęcia z teorii obliczeń równoległych
( )
A
j
i
∈
,
1
+
≥
i
j
t
t
i
j
t
t
=
33
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Algorytm obliczeń równoległych jest zadany, gdy:
1
o
zadany jest graf AGS;
2
o
zadany jest harmonogram
,
( )
G
H
( ) (
)
{
}
o
i
i
W
i
t
P
i
G
H
≠
=
:
,
,
Podstawowe pojęcia z teorii obliczeń równoległych
Dysponując np. dwoma
procesorami jeden z możliwych
harmonogramów może wyglądać
następująco:
(
) (
) (
) (
)
(
) (
) (
)
=
4
,
1
,
10
,
3
,
2
,
9
,
3
,
1
,
8
,
2
,
2
,
7
,
2
,
1
,
6
,
1
,
2
,
5
,
1
,
1
,
4
)
(G
H
34
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Złożonością
obliczeniową
algorytmu
Alg
reprezentowanego przez
AGS
i wykorzystującego p procesorów nazywamy
wielkość:
gdzie:
- czas realizacji harmonogramu H.
H – zbiór wszystkich harmonogramów realizujących
rozpatrywany algorytm równoległy Alg;
( )
H
t
T
i
W
i
H
p
∈
∈
=
max
min
H
( )
H
t
i
W
i
∈
max
Podstawowe pojęcia z teorii obliczeń równoległych
35
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Zdefiniujmy wielkość:
T
p
jest nierosnącą funkcją i ograniczoną od dołu
przez 0.
Istnieje taka liczba procesorów p
*
, że dla każdego
, zachodzi
:
-
złożoność obliczeniowa algorytmu reprezentowanego
przez G, gdy dostatecznie duża liczba procesorów jest
dostępna;
T
1
- złożoność obliczeniowa (czas) odpowiadająca
algorytmowi sekwencyjnemu na jednym procesorze, przy
czym
.
Podstawowe pojęcia z teorii obliczeń równoległych
p
p
T
T
1
min
≥
∞
=
*
p
p
≥
∞
= T
T
p
∞
T
o
W
W
T
\
1
=
36
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Twierdzenie
• Wielkość
∞
T
jest równa głębokości
D
grafu AGS.
•
∞
≥
≥
T
T
T
p
1
,
1
≥
∀ p
Twierdzenie
Niech dla pewnego wierzchołka wyjściowego j istnieje droga z
każdego wierzchołka wejściowego.
Niech
\
0
W
W
i
∈
∀
zachodzi:
2
)
(
≤
i
S
w
gdzie
|
}
)
,
(
:
{
|
)
(
A
i
j
W
j
i
S
w
∈
∈
=
- stopień wewnętrzny wierzchołka i.
Wówczas zachodzi:
|
|
log
0
2
W
T
≥
∞
Podstawowe pojęcia z teorii obliczeń równoległych
37
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Wnioski:
Dla operacji arytmetycznych założenie, że
jest naturalne i dotyczy fizycznej
realizowalności operacji.
Głębokość AGS jest nie mniejsza niż logarytm
przy podstawie 2 z liczby wierzchołków
wejściowych w AGS.
2
)
(
≤
i
S
w
Podstawowe pojęcia z teorii obliczeń równoległych
38
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Twierdzenie
Dla każdego
1
≥
p
zachodzi:
p
T
T
T
p
1
+
≤
∞
Podstawowe pojęcia z teorii obliczeń równoległych
Dowód:
Rozpatrzmy
harmonogram
∞
H
, którego realizacja trwa
∞
T
, tzn.
optymalny harmonogram realizacji obliczeń dla zadanego grafu G,
gdy dostatecznie duża liczba procesorów jest dostępna.
Dla dodatniej liczby całkowitej k wykorzystując harmonogram
∞
H
wprowadźmy zbiór:
}
:
{
k
t
W
i
A
i
k
=
∈
=
39
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Dowód, c.d.
Zbudujemy etapowo dla tego samego grafu G harmonogram
p
H
, który
wykorzystuje tylko p procesorów.
W k-tym etapie tego nowego harmonogramu wykonamy operacje, które
w harmonogramie
∞
H
zakończyły się dokładnie w chwili k-tej.
Ponieważ tylko p procesorów jest dostępnych, k-ty etap będzie zrealizowany
w czasie
p
A
k
|
|
jednostek czasu.
Czas T
p
nie może być większy niż czas wymagany do zrealizowania
harmonogramu
p
H
.
Stąd:
∞
=
=
+
=
+
<
≤
∑
∑
∞
∞
T
p
T
p
A
p
A
T
T
k
k
T
k
k
p
1
1
1
1
|
|
|
|
gdzie
|
\
|
|
|
0
1
1
W
W
A
T
T
k
k
∑
∞
=
=
=
c.n.d.
Podstawowe pojęcia z teorii obliczeń równoległych
40
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład (dwie alternatywne reprezentacje AGS dla zadania)
Rozpatrzmy
zadanie:
(
) (
)
3
2
2
1
x
x
x
x
x
+
⋅
+
=
*
*
+
*
p
+
+
1
x
2
x
3
x
2
1
x
x
⋅
2
2
x
3
2
x
x
⋅
3
1
x
x
⋅
2
2
2
1
x
x
x
+
⋅
3
2
3
1
x
x
x
x
⋅
+
⋅
(
)(
)
3
2
2
1
x
x
x
x
x
+
+
=
4
*
3
7
1
=
=
=
∞
=
p
D
T
T
AGS 1
+
+
*
1
x
2
x
3
x
2
1
x
x
+
3
2
x
x
+
(
)(
)
3
2
2
1
x
x
x
x
x
+
+
=
2
2
3
1
=
=
=
=
∗
∞
p
D
T
T
AGS 2
WNIOSEK:
Dla tego samego
problemu może
istnieć wiele
reprezentacji w
postaci AGS
różniących się
wartościami
oraz
p*.
∞
T
41
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Podstawowe pojęcia z teorii obliczeń równoległych
Niech G oznacza zbiór wszystkich możliwych
AGS-ów dla ustalonego problemu i ustalonej
liczby procesorów.
Wielkość
nazywamy
złożonością problemu
,
nazywamy
złożonością algorytmu równoległego
przy p procesorach
, a G* nazywamy
optymalnym grafem
reprezentującym algorytm
rozwiązania danego problemu przy ustalonej
liczbie p procesorów.
( )
( )
G
T
G
T
T
p
G
p
p
G
min
∈
∗
∗
=
=
( )
G
T
T
p
p
=
42
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Przyspieszeniem
algorytmu równoległego nazywamy liczbę
a
efektywnością
algorytmu równoległego liczbę
gdzie:
T
*
(n) – złożoność najlepszego sekwencyjnego algorytmu
na jednym procesorze (jeśli mamy AGS, to T
*
(n) = T
1
(n));
T
p
(n) – złożoność algorytmu rozwiązywania problemu
o rozmiarze n na p procesorach.
( )
( )
( )
p
n
T
n
T
n
S
p
p
≤
=
∗
( )
( )
( )
( )
1
≤
⋅
=
=
∗
n
T
p
n
T
p
n
S
n
E
p
p
p
Podstawowe pojęcia z teorii obliczeń równoległych
43
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Zadanie obliczeniowe ma posta
Zadanie obliczeniowe ma posta
ć
ć
:
:
Przy użyciu n
procesorów zadanie to można
rozwiązać w czasie
dwuetapowo
.
W
pierwszym etapie
każdy i-ty procesor oblicza
wartość
, a następnie
w drugim etapie
dodaje
n uzyskanych liczb w czasie
.
Najlepszy algorytm dla jednego procesora wymaga
czasu
.
Stąd przyspieszenie
i efektywność dla n procesorów:
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład
ℜ
∈
⋅
=
∑
=
i
i
i
n
i
i
y
x
y
x
a
,
,
1
( )
1
log
+
=
n
n
T
n
i
i
y
x
⋅
n
log
( )
1
2
−
=
∗
n
n
T
( )
1
log
1
2
+
−
=
n
n
n
S
n
( )
(
)
1
log
1
2
+
−
=
n
n
n
n
E
n
44
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
np. dla n=3, mamy następujący AGS
Podstawowe pojęcia z teorii obliczeń równoległych
Przykład, c.d.
*
*
*
+
+
1
2
3
4
5
6
7
8
9
10
11
1
x
1
y
2
x
2
y
3
x
3
y
1
1
y
x
⋅
2
2
y
x
⋅
3
3
y
x
⋅
2
2
1
1
y
x
y
x
+
3
3
2
2
1
1
y
x
y
x
y
x
+
+
H*(G)={(7,1,1),(8,2,1),(9,3,1),(10,1,2),(11,1,3)}
55
,
0
3
3
5
67
,
1
3
5
1
3
log
3
5
\
3
3
3
3
3
3
1
=
⋅
=
⋅
=
=
=
=
+
=
=
=
=
=
=
=
∗
∗
∗
∞
T
n
T
E
T
T
S
T
W
W
T
T
D
T
o
( )
( )
(
)
3
max
min
3
=
=
∈
∈
G
H
t
T
i
W
i
H
G
H
45
Z.Tarapata, Obliczenia równoległe i rozproszone, wykład nr 2,
http://tarapata.strefa.pl/p_obliczenia_rownolegle_i_rozproszone/
Dziękuję za uwagę