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:

[e-mail]

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ę