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
/
/
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
.
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.
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
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
+
−
≤
≤
∈
∈
≠
∃
∀
+
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
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
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
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
+
=
+
=
+
=
+