WOJSKOWA AKADEMIA TECHNICZNA
IM. JAROSŁAWA DĄBROWSKIEGO
W WARSZAWIE
OBLICZENIA RÓWNOLEGŁE I ROZPROSZONE
TEMAT: Obliczanie wartości symbolu Newtona
Prowadzący:
mgr inż. Adam Misztak
Wykonawcy:
Błażej Bubrowiecki
Grupa I8C1S1
WOJSKOWA AKADEMIA TECHNICZNA
IM. JAROSŁAWA DĄBROWSKIEGO
W WARSZAWIE
OBLICZENIA RÓWNOLEGŁE I ROZPROSZONE
TEMAT: Obliczanie wartości symbolu Newtona
Prowadzący:
mgr inż. Adam Misztak
Wykonawcy:
Błażej Bubrowiecki
Grupa I8C1S1
1. Schemat obliczeń równoległych (graf AGS, harmonogram)
Symbol Newtona jest to funkcja dwóch argumentów całkowitych nieujemnych:
!
!*
!
k
k
n
n
k
n
,
gdzie n>k
Symbol Newtona pojawia się także w wzorze na dwumian Newtona, gdzie jest
współczynnikiem w k-tym wyrazie rozwinięcia n-tej potęgi sumy dwóch składników.
Postać iteracyjna symbolu Newtona, którą wykorzystam w zadaniu wygląda następująco:
k
k
n
n
k
n
k
k
n
n
k
n
*
)
1
(
*
...
*
3
*
2
*
1
*
)
1
(
*
...
*
)
1
(
!
)!*
(
!
Rys.1. Graf AGS dla n=7 i k=3.
Rys.2. Histogram.
Opis działania algorytmu:
Algorytm opiera on się na iteracyjnej postaci dwumianu Newtona. Na wejścia podajemy 2
zmienne, zmienna x
0
odpowiada n, a zmienna x
1
odpowiada k. Następnie oblczamy ich
różnicę (wierzchołek Z0). Po czym dla wartości (n-k) jest liczony iloczyn kolejnych liczb
naturalnych od (n-k+1) do n poprzez zwiększanie wartości (n-k) oraz przemnażanie z
wartością uzyskaną w poprzednim kroku. Podobnej operacji dokonujemy dla k tylko, że w
tym przypadku wartość wejściową zmniejszamy aż uzyskamy iloczyn kolejnych liczb
naturalnych od 1 do k (czyli uzyskamy silnie dla k). Na końcu uzyskane obliczenia cząstkowe
są dzielone, zgodnie ze wzorem na dwumian Newtona.
Występują 4 podstawowe działania: odejmowanie, mnożenie, inkrementacja (+1),
dekrementacja (-1) oraz dzielenie.
2. Oszacowanie teoretycznej złożoności obliczeniowej problemu.
Wpływ na złożoność obliczeniową mojego algorytmu ma początkowa wartość k. Ona
decyduje o głębokości grafu AGS. Wynika to z tego, że obliczenia nie są zależne od samego
n, ale od różnicy (n-k). Dla ustalonego k liczba działań, które należy wykonać żeby obliczyć
licznik dwumianu wynosi 2*(k-1)+1, a mianownik 2*(k-1). Całkowita złożoność
zaproponowanego algorytmy jako funkcję rozmiaru zadania (od wartości n i k) wynosi:
2
*
4
1
)
1
(
*
2
1
)
1
(
*
2
)
(
)
,
(
k
k
k
k
T
k
n
T
Nie udało mi się znaleźć zależności miedzy liczba procesorów, a złożonością obliczeniową,
zarówno dla procesorów pracujących z opóźnieniem jak i bez nich.
3.Symulacja obliczeń równoległych.
Liczba procesorów mniejsza od rozmiaru zadania (1) , procesory jednorodne:
Rys.3. Operacje jednorodne
Rys.4. Operacje niejednorodne.
Liczba procesorów mniejsza od rozmiaru zadania (1) , procesory niejednorodne:
Rys.5. Operacje jednorodne.
Rys.6. Operacje niejednorodne.
Liczba procesorów równa rozmiarowi zadania (2) , procesory jednorodne:
Rys.7. Operacje jednorodne.
Rys.8. Operacje niejednorodne.
Liczba procesorów równa rozmiarowi zadania (2) , procesory niejednorodne:
Rys.9. Operacje jednorodne.
Rys.10. Operacje niejednorodne.
procesorów większa od rozmiaru zadania (4) , procesory jednorodne:
Rys.11. Operacje jednorodne.
Rys.12. Operacje niejednorodne.
procesorów większa od rozmiaru zadania (4) , procesory niejednorodne:
Rys.13. Operacje jednorodne.
Rys.14. Operacje niejednorodne.
4.Wartości charakterystyk oraz porównanie wyników.
Optymalna liczba procesorów to: p*=3
Złożoność obliczeniowa dla T
∞
=8
Optymalna liczba procesorów dla rozmiaru danych 2 wynosi:
p*=3 T
1
=15
T
2
=9 T
3
=8 T
4
=8 T
10
=8
Przyspieszenie algorytmów oraz efektywność:
s
2
= T
1/
T
2
=15/9=1,666
e
2
=s
2
/2=1,666/2=0,833
s
3
= T
1/
T
3
=15/8=1,875
e
3
=s
3
/3=1,875/3=0,625
s
4
= T
1/
T
4
=15/8=1,875
e
4
=s
4
/4=1,875/4=0,46875
s
10
= T
1/
T
10
=15/8=1,875
e
10
=s
10
/10=1,875/10=0,1875
Zależność złożoności algorytmu od liczby
procesorów
15
9
8
8
8
0
5
10
15
20
1
2
3
4
10
liczba procesorów
Tp
Zależność przyspeszenia algorytmu od liczby
procesorów
1
1,666
1,875
1,875
1,875
0
0,5
1
1,5
2
1
2
3
4
10
liczba procesorów
Sp
Zalezność efektywności algorytmu od liczby procesorów
1
0,833
0,625
0,46875
0,1875
0
0,2
0,4
0,6
0,8
1
1,2
1
2
3
4
10
liczba procesorów
Ep
5.WNIOSKI
Złożoność obliczeniowa stworzonego algorytmu jest zależna od rozmiaru danej
k, gdyż ona decyduje o ilości obliczeń. Optymalna liczba procesorów wynosi 3, i dla
mojego rozmiaru danych taka właśnie była. Dla jednego procesora algorytm dla
przyjętego rozmiaru danych wykonywał się 15 jednostek czasu. Po zwiększeniu ich
liczby do 2 czas wykonania spadł do 9 jednostek. Gdy przekroczyłem liczbę 3
procesorów to czas wykonani ustabilizował się na poziomie 8 jednostek czasu, i był
taki sam zarówno dla 4 procesorów jak i 10. Zwiększanie liczby kolejnych procesorów
nie wpłynie na czas wykonania zadania, ponieważ pozostałe procesory będą nie
używane.
Czas wykonania algorytmu zależy także od tego czy procesory są jednorodne
czy niejednorodne, od długości wykonania poszczególnych operacji oraz od tego czy
występują opóźnienia w przesyłaniu wewnątrz jak i pomiędzy procesorami. Może
dojść do sytuacji, że opóźnienia będą tak duże w przesyłaniu danych, że zadanie
wykonane na jednym procesorze wykona się szybciej niż zadania zlecone do
wykonania na kilku maszynach.