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 x₀ odpowiada n, a zmienna x₁ 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 T₁=15 T₂=9 T₃=8 T₄=8 T₁₀=8

Przyspieszenie algorytmów oraz efektywność:

s₂= T_1/ T₂=15/9=1,666 e₂=s₂/2=1,666/2=0,833

s₃= T_1/ T₃=15/8=1,875 e₃=s₃/3=1,875/3=0,625

s₄= T_1/ T₄=15/8=1,875 e₄=s₄/4=1,875/4=0,46875

s₁₀= T_1/ T₁₀=15/8=1,875 e₁₀=s₁₀/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.

---