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:
Mirosław Klimek
Grupa I8C1S1
1. Schemat obliczeń równoległych (graf AGS, harmonogram)
Symbol Newtona jest to funkcja dwóch argumentów całkowitych nieujemnych:
, 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.
W zadaniu laboratoryjnym wykorzystam postać iteracyjną symbolu Newtona:
Przykładowy graf AGS dla n=8 i k=3
Opis działania opracowanego przeze mnie algorytmu:
Opiera on się na iteracyjnej postaci dwumianu Newtona. Podajemy 2 zmienne, gdzie zmienna x0 odpowiada n, a zmienna x1 odpowiada k. Następnie jest liczona ich różnica (wierzchołek Z0). Następnie 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: dzielenie, mnożenie, inkrementacja (+1), dekrementacja (-1) oraz odejmowanie.
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:
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:
Operacje jednorodne
Operacje niejednorodne
Liczba procesorów mniejsza od rozmiaru zadania (1) , procesory niejednorodne:
Operacje jednorodne
Operacje niejednorodne
Liczba procesorów równa rozmiarowi zadania (2) , procesory jednorodne:
Operacje jednorodne
Operacje niejednorodne
Liczba procesorów równa rozmiarowi zadania (2) , procesory niejednorodne:
Operacje jednorodne
Operacje niejednorodne
procesorów większa od rozmiaru zadania (4) , procesory jednorodne:
Operacje jednorodne
Operacje niejednorodne
procesorów większa od rozmiaru zadania (4) , procesory niejednorodne:
Operacje jednorodne
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 T1=15 T2=9 T3=8 T4=8 T10=8
Przyspieszenie algorytmów oraz efektywność:
s2= T1/ T2=15/9=1,666 e2=s2/2=1,666/2=0,833
s3= T1/ T3=15/8=1,875 e3=s3/3=1,875/3=0,625
s4= T1/ T4=15/8=1,875 e4=s4/4=1,875/4=0,46875
s10= T1/ T10=15/8=1,875 e10=s10/10=1,875/10=0,1875
WNIOSKI
Złożoność obliczeniowa moje 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 wykonani algorytmu zależy także od tego czy procesory są jednorodne czy nie, 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.
Wyszukiwarka