or wyklad 5 (2)

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

1


OBLICZENIA RÓWNOLEGŁE

Temat 5:

Obliczenia równoległe

w zadaniach optymalizacji

Prowadzący:

dr inż. Zbigniew TARAPATA

pok.225A, tel.: 83-94-13

e-mail:

Zbigniew.Tarapata@wat.edu.pl

http://

tarapata.

tarapata.

strefa

strefa

.pl

.pl

/

/

p_obliczenia_rownolegle

p_obliczenia_rownolegle

/

/














background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

2

OBLICZENIA RÓWNOLEGŁE

W ZADANIACH OPTYMALIZACJI

A) ITERACJA JACOBIEGO

(

)

( )

( )

,...

2

,

1

,

0

,

1

=

=

+

t

t

x

F

t

x

gdzie:

( )

n

E

t

x

dla

,...

2

,

1

,

0

=

t

F

(1)

n

n

E

E

:

lub skalarnie

(

)

( )

( )

( )

( )

(

)

,...

1

,

0

,

,

1

,

,...,

,

1

2

1

=

=

=

+

t

n

i

t

x

t

x

t

x

F

t

x

i

p

n

n

n

i

i

przy czym

( )

1

,

1

,

1

=

<

+

i

p

l

n

n

n

l

l

Zależności komunikacyjne między procesorami opisuje się

tzw.

grafem zależności

(

)

z

z

z

A

W

G

,

=

, gdzie:

{

}

n

W

z

,...,

2

,

1

=

- zbiór wierzchołków równy zbiorowi numerów

składowych wektora

x

;

z

A

- zbiór łuków, taki, że:

( )

{

j

z

z

z

F

W

W

j

i

A

:

,

×

=

zależy od

}

j

i

x

i

,

Graf

z

G stanowi podstawę do sporządzenia grafu AGS.

(1)

Jeżeli F jest odwzorowaniem zwężającym, tzn.

[ ]

1

,

0

q

,

że

( )

( )

y

x

q

y

F

x

F

E

y

x

n

∀ ,

,

to formuła Jacobiego prowadzi

do

uzyskania jedynego punktu stałego,

( )

=

x

F

x

.

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

3

Przykład 5

Niech formuła Jacobiego ma postać:

(

)

( ) ( ) ( )

(

)

(

)

( ) ( )

(

)

(

)

( ) ( ) ( )

(

)

(

)

( ) ( )

(

)

t

x

t

x

F

t

x

t

x

t

x

t

x

F

t

x

t

x

t

x

F

t

x

t

x

t

x

t

x

F

t

x

4

2

4

4

4

3

2

3

3

2

1

2

2

3

2

1

1

1

,

1

,

,

1

,

1

,

,

1

=

+

=

+

=

+

=

+

Graf zależności określimy następująco:

{

}

( ) ( ) ( ) ( ) ( ) ( )

{

}

4

,

2

,

3

,

4

,

3

,

2

,

2

,

1

,

1

,

3

,

1

,

2

,

,

4

,

3

,

2

,

1

=

=

z

z

A

W

Graf AGS

przyjmie postać:

( )

{

}

( ) (

)

(

) ( )

{

}

,...

2

,

1

,

0

,

,

:

1

,

,

,

,...

1

,

0

,

,

1

:

,

=

=

+

=

=

=

=

t

j

i

A

j

i

t

j

t

i

A

t

n

i

t

i

W

z

lub

3

1

4

2

G

Z

1,0

2,0

3,0

4,0

1,1

2,1

3,1

4,1

1,2

2,2

3,2

4,2

AGS

Niech

( )

t

i, - oznacza, że na danych z

iteracji 1

t

wykonana jest

operacja

i

F

, przy czym

( )

0

,

i

oznacza wczytanie wielkości

( )

.

0

i

x

Dla tak skonstruowanego grafu

AGS należy zbudować

harmonogram realizacji obliczeń

dla zadanej liczby

p

procesorów.

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

4

B) ITERACJA GAUSSA-SEIDELA

(

)

( )

( )

( )

( )

( )

(

)

,...

1

,

0

,

1

,

,...,

,

1

2

1

2

1

=

=

=

+

t

n

i

t

x

t

x

t

x

F

t

x

i

p

n

n

n

i

i

i

p

gdzie:

( )

1

,

1

,

1

=

<

+

i

p

l

n

n

n

l

l

{

}

( )

i

n

t

t

i

,p

k

t

t

t

k

k

k

=

=

=

+

gdy

1

,

1

,

Przykład 5 c.d.

Zachowując przyjętą w poprzed-

nim przykładzie kolejność

aktualizacji zmiennych formuła

G-S ma postać:

(

)

( ) ( ) ( )

(

)

,

,

,

1

3

2

1

1

1

t

x

t

x

t

x

F

t

x

=

+

(

)

(

) ( )

(

)

,

,

1

1

2

1

2

2

t

x

t

x

F

t

x

+

=

+

(

)

(

) ( ) ( )

(

)

,

,

,

1

1

4

3

2

3

3

t

x

t

x

t

x

F

t

x

+

=

+

(

)

(

) ( )

(

)

.

,

1

1

4

2

4

4

t

x

t

x

F

t

x

+

=

+

Graf AGS dla

t = 0,1

Przyjmijmy następującą kolejność

aktualizacji:

(

)

( ) ( ) ( )

(

)

,

,

,

1

3

2

1

1

1

t

x

t

x

t

x

F

t

x

=

+

(

)

(

) ( )

(

)

,

,

1

1

2

1

2

2

t

x

t

x

F

t

x

+

=

+

(

)

(

) ( )

(

)

,

,

1

1

4

2

4

4

t

x

t

x

F

t

x

+

=

+

(

)

(

) ( ) (

)

(

)

.

1

,

,

1

1

4

3

2

3

3

+

+

=

+

t

x

t

x

t

x

F

t

x

Graf AGS dla

t = 0,1

1,0

2,0

3,0

4,0

1,1

2,1

3,1

4,1

2

3

=

=

=

p

T

D

1,0

2,0

3,0

4,0

1,1

2,1

3,1

4,1

1

4

=

=

=

p

T

D

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

5

Twierdzenie

Zachodzą 2 równoważne warunki:

1

o

istnieje taka kolejność uaktualniania zmiennych wg formuły G-S,

przy której jedna iteracja G-S wykonuje się w

h

równoległych

krokach.

2

o

istnieje pokolorowanie grafu zależności

z

G , które wykorzystuje

h

kolorów, przy czym dla dowolnego cyklu skierowanego w grafie

z

G nie wszystkie wierzchołki tego cyklu mają ten sam kolor.

Formalnie pokolorowanie spełniające warunki punktu 2

o

twierdzenia

zdefiniujemy jak poniżej.

Oznaczenia:

C - zbiór wszystkich różnych cykli skierowanych w grafie

z

G ;

c

- dowolny cykl skierowany w

z

G ;

( )

( ) ( )

( )

{

} ( )

( )

c

i

c

i

c

i

c

i

c

i

c

W

M

M

=

=

1

2

1

,

,...,

,

zbiór wierzchołków cyklu skierowanego

c

, przy czym

(

)

;

,

;

1

1

1

z

l

l

z

l

M

l

A

i

i

W

i

+

Pokolorowanie K

zdefiniujemy następująco:

K : W

z

→{1,2,...,h}

przy czym zachodzi:

( )

( ) ( )

( )

(

)

( )

(

)

c

i

K

c

i

K

l

l

M

l

c

W

c

i

c

i

C

c

l

l

1

1

1

,

1

+

+

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

6

PROCEDURA POSTĘPOWANIA W CELU USTALENIA

OPTYMALNEJ KOLEJNOŚCI AKTUALIZACJI ZMIENNYCH



1) Kolorujemy graf

z

G , aby spełnić 2

o

.

2) Wybieramy z

z

G podgrafy

z

r

G

w oparciu o wierzchołki

pokolorowane kolorem

r ;

3) Przyporządkowujemy każdemu wierzchołkowi

i

podgrafu

z

r

G

,

h

r

,

1

=

wartość

i

l

równą długości najdłuższej drogi w

z

r

G

z

i

;

4) Porządkujemy wierzchołki grafu

z

G wg wzrastających numerów

kolorów zachowując dla ustalonego koloru kolejność rosnącą

wynikającą z punktu 3).

Przykład 5 c.d.

1) Kolorujemy graf

z

G , zgodnie z ustaloną zasadą:

3

4

2

1

W grafie

z

G

występują 3 różne cykle

skierowane:

a) 1 – 2 – 1

b) 1 – 2 – 3 – 1

c) 1 – 2 – 4 – 3 – 1

Stąd np.:

r = 1 -

2

,

3

,

4

r = 2 -

1

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

7

2)

z

G

1

z

G

2

3)

l

3

= 0 ,

l

4

= 1 ,

l

2

= 2

l

1

= 0

4)

Uporządkowanie wierzchołków grafu

z

G

:

l

i

0 1 2 0

i =

3

-

4

-

2

-

1

3

4

2

1

Podgrafy

r = 1

r = 2

Wobec tego kolejność

uaktualniania zmiennych

jest następująca:

(

)

( ) ( ) ( )

(

)

(

)

( ) ( )

(

)

(

)

( ) ( )

(

)

(

)

( ) (

) (

)

(

)

1

,

1

,

1

,

1

,

1

,

,

1

3

2

1

1

1

2

1

2

2

4

2

4

4

4

3

2

3

3

+

+

=

+

=

+

=

+

=

+

t

x

t

x

t

x

F

t

x

t

x

t

x

F

t

x

t

x

t

x

F

t

x

t

x

t

x

t

x

F

t

x

Graf AGS (dla

t = 0,1)

1,0

2,0

3,0

4,0

1,1

2,1

3,1

4,1

2

2

=

=

=

p

T

D

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

8

Przykład 6

Ustalić optymalną kolejność uaktualniania zmiennych w metodzie

G-S rozwiązywania układu równań liniowych:

Graf

z

G

: AGS:

Wyznaczamy optymalną kolejność uaktualniania zmiennych ze

względu na możliwość zrównoleglenia.

Kolorujemy graf

z

G :

AGS:

- 1,

2

- 3

5

2

5

3

2

2

3

3

1

2

3

1

=

+

=

+

=

x

x

x

x

x

x

x

(

)

( ) ( )

(

)

(

)

(

) ( ) ( )

(

)

(

)

(

) ( )

(

)

t

x

t

x

F

t

x

t

x

t

x

t

x

F

t

x

t

x

t

x

F

t

x

3

2

3

3

3

2

1

2

2

3

1

1

1

,

1

1

,

,

1

1

,

1

+

=

+

+

=

+

=

+

1

3

2

1,0

2,0

3,0

1,1

2,1

3,1

1

3

=

=

p

D

1

3

2

1

1

=

l

0

2

=

l

0

3

=

l

1,0

2,0

3,0

1,1

2

2

=

=

p

D

2,1

3,1

background image

Obliczenia równoległe i rozproszone

dr inż. Zbigniew Tarapata

Temat nr 5: Obliczenia równoległe w zadaniach optymalizacji

9

Ustalamy kolejność uaktualniania

zmiennych:

2

1

3

czyli otrzymujemy:

(

)

( ) ( ) ( )

(

)

(

)

( ) ( )

(

)

(

)

(

) ( )

(

)

t

x

t

x

F

t

x

t

x

t

x

F

t

x

t

x

t

x

t

x

F

t

x

3

2

3

3

3

1

1

1

3

2

1

2

2

,

1

1

,

1

,

,

1

+

=

+

=

+

=

+


Wyszukiwarka

Podobne podstrony:
or wyklad 1 id 339025 Nieznany
or wyklad 4b id 339029 Nieznany
or wykłady1
or wykłady1(1)
or wyklad 2 (2)
or wyklad 4 id 339027 Nieznany
Szkol Or wykład
or wyklad 6 narzedzia srodowisk Nieznany
or wykłady1
or wyklad 4a id 339028 Nieznany
or wyklad 3 id 339026 Nieznany
or wyklad 1 id 339025 Nieznany
or wyklad 4b id 339029 Nieznany

więcej podobnych podstron