TEORETYCZNE

PODSTAWY

INFORMATYKI

Prowadzący:

ppor. mgr inż. Mariusz

CHMIELEWSKI

e-mail:

[e-mail]

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,410

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