TEORETYCZNE
PODSTAWY
INFORMATYKI
Prowadzący:
ppor. mgr inż. Mariusz
CHMIELEWSKI
e-mail:
mchmiel@isi.wat.waw.pl
Temat 6:
Temat 6:
Modele obliczeń równoległych.
Modele obliczeń równoległych.
Architektury równoległe.
Architektury równoległe.
TEORETYCZNE
PODSTAWY
INFORMATYKI
Prowadzący:
ppor. mgr inż. Mariusz
CHMIELEWSKI
e-mail:
mchmiel@isi.wat.waw.pl
Temat 6:
Temat 6:
Modele obliczeń równoległych.
Modele obliczeń równoległych.
Architektury równoległe.
Architektury równoległe.
2
ppor. mgr inż. Mariusz CHMIELEWSKI
Metody zwiększania efektywności
algorytmów
metody zwiększania efektywności
metody zwiększania efektywności
algorytmów
algorytmów
:
zaprojektowanie algorytmu poprzez stosowanie
odpowiednich:
-
struktur danych
(listy, drzewa, kolejki, itp.),
-
technik projektowania algorytmów
(np. dziel i
zwyciężaj, programowanie dynamiczne,
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.);
3
ppor. mgr inż. Mariusz CHMIELEWSKI
wykorzystanie odpowiednich struktur danych
Przykład (sortowanie, n – rozmiar tablicy)
Umiejętne projektowanie
algorytmów
Nazwa algorytmu
Złożoność
Uwagi
- przez proste wstawianie
- bąbelkowe
W
(n) = (n
2
)
-
- działa „w miejscu” (tzn.
tylko stała liczba elementów
tablicy jest przechowywana
poza tablicą podczas
działania algorytmu)
-
- dla małych tablic
przez scalanie
W
(n) = (n log n)
-
- nie działa w miejscu
-
- oparty o technikę „dziel i
zwyciężaj”
przez kopcowanie
(heapsort)
W
(n) = O(n log n)
-
- wykorzystywane są kopce
binarne
szybkie (quicksort)
W
(n) = (n
2
)
A
(n) = (n log n)
-
- działa „w miejscu”
-
- dla dużych tablic
-
- oparty o technikę „dziel i
zwyciężaj”
4
ppor. mgr inż. Mariusz CHMIELEWSKI
Wykorzystanie wielu procesorów = zrównoleglanie
Sortowanie bąbelkowe
– wykorzystując N/2 (=4) procesorów
przyspieszamy porównywanie parami elementów tablicy
Umiejętne projektowanie
algorytmów
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
5
ppor. mgr inż. Mariusz CHMIELEWSKI
Umiejętne projektowanie
algorytmów,
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
6
ppor. mgr inż. Mariusz CHMIELEWSKI
Umiejętne projektowanie
algorytmów
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ównole
gły
O(N
2
)
O(N)
7
ppor. mgr inż. Mariusz CHMIELEWSKI
Algorytmy i systemy równoległe
ISTOTA zrównoleglenia rozwiązywania
problemu:
Podział zadania na mniejsze części;
Wyznaczenie rozwiązania składowych
problemów na wielu procesorach
Koordynacja zadań cząstkowych i
przekazanie ich wyników do zadania
nadrzędnego (koordynującego).
8
ppor. mgr inż. Mariusz CHMIELEWSKI
CPU
Pamięć
Interfejs
sieciowy
Struktura systemu obliczeń
równoległych
9
ppor. mgr inż. Mariusz CHMIELEWSKI
Algorytmy i systemy równoległe -
własności
Korzystanie z systemów obliczeń równoległych nie
nie
wyprowadza nas poza klasyfikację opartą na
wyprowadza nas poza klasyfikację opartą na
złożoności obliczeniowej
złożoności obliczeniowej
dla obliczeń
sekwencyjnych.
Użycie
Użycie
wielu procesorów
wielu procesorów
przyspiesza (nie zawsze)
rozwiązywanie problemów lecz nie zmienia
nie zmienia
przynależności do klasy złożoności obliczeniowej
przynależności do klasy złożoności obliczeniowej
.
Jakich korzyści dostarcza zrównoleglenie obliczeń
Jakich korzyści dostarcza zró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.
10
ppor. mgr inż. Mariusz CHMIELEWSKI
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
11
ppor. mgr inż. Mariusz CHMIELEWSKI
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).
12
ppor. mgr inż. Mariusz CHMIELEWSKI
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
.
13
ppor. mgr inż. Mariusz CHMIELEWSKI
Algorytmy i systemy równoległe –
Równoległość, a rozproszoność
Rodzaj
Cechy
systemu
charakteryst.
Syst. oblicz.
Syst. oblicz.
równoległych
równoległych
Syst. oblicz.
Syst. oblicz.
rozproszonych
rozproszonych
Odległości między
Odległości między
procesorami
procesorami
małe
Zazwyczaj
duże
Struktura połączeń
Struktura połączeń
Nie ulega
zmianom w
czasie
Może ulegać
zmianom w
czasie
Niezawodność
Niezawodność
polączeń
polączeń
duża
mała
Opóźnienia
Opóźnienia
komunikacyjne
komunikacyjne
Pomijalnie małe
Zazwyczaj nie
do pominięcia
Ingerencja
Ingerencja
sterowania
sterowania
centralnego
centralnego
duża
mała
14
ppor. mgr inż. Mariusz CHMIELEWSKI
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.
15
ppor. mgr inż. Mariusz CHMIELEWSKI
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ęć.
16
ppor. mgr inż. Mariusz CHMIELEWSKI
)
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.
17
ppor. mgr inż. Mariusz CHMIELEWSKI
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”
18
ppor. mgr inż. Mariusz CHMIELEWSKI
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,410
9
FLOPS)
- moc Deep Blue z 1997 r.: 10 G FLOPS.
Algorytmy i systemy równoległe –
Przykłady zastosowań
19
ppor. mgr inż. Mariusz CHMIELEWSKI
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ń
20
ppor. mgr inż. Mariusz CHMIELEWSKI
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ń
21
ppor. mgr inż. Mariusz CHMIELEWSKI
Najszybszy obecnie system na świecie
(od 2002 roku):
japoński Earth Simulator
(do symulacji złożonych zjawisk
geologicznych i pogodowych),
moc: 40 T FLOPS,
koszt: 350 mln $.
Program „Blue Gene” firmy IBM
: w 2005
r. ma powstać (na bazie RS/6 000)
maszyna o wydajności 1 P FLOPS
(10
15
FLOPS) do analizy genomu ludzkiego
).
) Źródło: http://www.top500.org.
Algorytmy i systemy równoległe –
Przykłady zastosowań
22
ppor. mgr inż. Mariusz CHMIELEWSKI
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
23
ppor. mgr inż. Mariusz CHMIELEWSKI
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
24
ppor. mgr inż. Mariusz CHMIELEWSKI
Podstawowe pojęcia z teorii
obliczeń równoległych
Przykład 2
(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.
25
ppor. mgr inż. Mariusz CHMIELEWSKI
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 2
(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
26
ppor. mgr inż. Mariusz CHMIELEWSKI
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
\
27
ppor. mgr inż. Mariusz CHMIELEWSKI
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
t
t
j
i
P
P
Podstawowe pojęcia z teorii
obliczeń równoległych
A
j
i
,
1
i
j
t
t
28
ppor. mgr inż. Mariusz CHMIELEWSKI
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
29
ppor. mgr inż. Mariusz CHMIELEWSKI
Złożonością obliczeniową
algorytmu A
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 A;
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
30
ppor. mgr inż. Mariusz CHMIELEWSKI
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
31
ppor. mgr inż. Mariusz CHMIELEWSKI
T
w
ie
rd
z
e
n
ie
W
ie
lk
o
ś
ć
T
je
s
t ró
w
n
a
g
łę
b
o
k
o
ś
c
i
D
g
ra
fu
A
G
S
.
T
T
T
p
1
,
1
p
T w ierdzen ie
N iech d la p ew n ego w ier zch ołk a w y jściow ego j istn ieje d r oga z
k ażd ego w ier zch ołk a w ejściow ego.
N iech
\
0
W
W
i
zach od zi:
2
)
(
i
S
w
gd zie
|
}
)
,
(
:
{
|
)
(
A
i
j
W
j
i
S
w
- stop ień w ew n ętr zn y w ier zch ołk a i.
W ów czas zach od zi:
|
|
log
0
2
W
T
Podstawowe pojęcia z teorii
obliczeń równoległych
32
ppor. mgr inż. Mariusz CHMIELEWSKI
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
33
ppor. mgr inż. Mariusz CHMIELEWSKI
T
w
ie
r
d
z
e
n
ie
D
la
k
a
ż
d
e
g
o
1
p za
c
h
o
d
z
i:
p
T
T
T
p
1
Podstawowe pojęcia z teorii
obliczeń równoległych
D o w ó d :
R o z p a tr z m y h a r m o n o g r a m
H
, k tó r eg o r ea liz a cj a tr w a
T
, tz n .
o p ty m a ln y h a r m o n o g r a m r ea liz a cj i o b lic z eń d la z a d a n eg o g r a fu G ,
g d y d o sta tecz n ie d u ż a lic z b a p r o c eso r ó w j est d o stęp n a .
D la d o d a tn iej licz b y ca łk o w itej k w y k o r z y stu j ą c h a r m o n o g r a m
H
w p r o w a d ź m y z b ió r :
}
:
{
k
t
W
i
A
i
k
34
ppor. mgr inż. Mariusz CHMIELEWSKI
Dowód, c.d.
Z b u d u j e m y e ta p o w o d la te g o s a m e g o g r a f u G h a r m o n o g r a m
p
H
, k tó r y
w y k o r z y s tu j e ty lk o p p r o c e so r ó w .
W k - ty m e ta p ie te g o n o w e g o h a r m o n o g r a m u w y k o n a m y o p e r a c j e , k tó r e
w h a r m o n o g r a m ie
H
z a k o ń c z y ły s ię d o k ła d n ie w c h w ili k - te j .
P o n ie w a ż ty lk o p p r o c e so r ó w j e st d o s tę p n y c h , k - ty e ta p b ę d z ie z r e a liz o w a n y
w c z a s ie
p
A
k
|
|
j e d n o s te k c z a s u .
C z a s T
p
n ie m o ż e b y ć w ię k s z y n iż c z a s w y m a g a n y d o z r e a liz o w a n ia
h a r m o n o g r a m u
p
H
.
S tą d :
T
p
T
p
A
p
A
T
T
k
k
T
k
k
p
1
1
1
1
|
|
|
|
g d z ie
|
\
|
|
|
0
1
1
W
W
A
T
T
k
k
c .n .d .
Podstawowe pojęcia z teorii
obliczeń równoległych
35
ppor. mgr inż. Mariusz CHMIELEWSKI
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
36
ppor. mgr inż. Mariusz CHMIELEWSKI
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
37
ppor. mgr inż. Mariusz CHMIELEWSKI
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
38
ppor. mgr inż. Mariusz CHMIELEWSKI
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
39
ppor. mgr inż. Mariusz CHMIELEWSKI
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