Algorytm równoległy - analiza

Analiza algorytmu pomaga nam określić, czy algorytm jest przydatny, czy nie. Ogólnie algorytm jest analizowany na podstawie czasu jego wykonania(Time Complexity) i ilość miejsca (Space Complexity) to wymaga.

Ponieważ dysponujemy zaawansowanymi urządzeniami pamięci dostępnymi po rozsądnych kosztach, przestrzeń dyskowa nie jest już problemem. Stąd złożoność przestrzeni nie ma tak dużego znaczenia.

Algorytmy równoległe mają na celu poprawę szybkości obliczeń komputera. Aby przeanalizować algorytm równoległy, zwykle rozważamy następujące parametry -

Złożoność czasowa (czas wykonania),
Łączna liczba używanych procesorów i
Całkowity koszt.

Złożoność czasowa

Głównym powodem opracowania równoległych algorytmów było skrócenie czasu obliczeń algorytmu. Dlatego ocena czasu wykonania algorytmu jest niezwykle ważna w analizie jego wydajności.

Czas wykonania jest mierzony na podstawie czasu potrzebnego algorytmowi do rozwiązania problemu. Całkowity czas wykonania jest obliczany od momentu rozpoczęcia wykonywania algorytmu do momentu jego zatrzymania. Jeżeli wszystkie procesory nie rozpoczynają lub nie kończą wykonywania w tym samym czasie, to łączny czas wykonywania algorytmu jest momentem rozpoczęcia wykonywania przez pierwszy procesor do momentu, w którym ostatni procesor przestał wykonywać swoje wykonanie.

Złożoność czasową algorytmu można podzielić na trzy kategorie:

Worst-case complexity - Gdy ilość czasu wymagana przez algorytm dla danego wejścia wynosi maximum.
Average-case complexity - Gdy ilość czasu wymagana przez algorytm dla danego wejścia wynosi average.
Best-case complexity - Gdy ilość czasu wymagana przez algorytm dla danego wejścia wynosi minimum.

Analiza asymptotyczna

Złożoność lub wydajność algorytmu to liczba kroków wykonywanych przez algorytm w celu uzyskania pożądanego wyniku. Analiza asymptotyczna jest wykonywana w celu obliczenia złożoności algorytmu w analizie teoretycznej. W analizie asymptotycznej do obliczenia funkcji złożoności algorytmu stosuje się dużą długość danych wejściowych.

Note - Asymptoticjest stanem, w którym linia ma tendencję do stykania się z krzywą, ale się one nie przecinają. Tutaj linia i krzywa są względem siebie asymptotyczne.

Notacja asymptotyczna jest najłatwiejszym sposobem opisania najszybszego i najwolniejszego możliwego czasu wykonania algorytmu wykorzystującego wysokie i niskie ograniczenia szybkości. W tym celu używamy następujących oznaczeń -

Notacja Big O.
Notacja Omega
Notacja theta

Notacja Big O.

W matematyce notacja Big O jest używana do reprezentowania asymptotycznych cech funkcji. Reprezentuje zachowanie funkcji dla dużych danych wejściowych w prostej i dokładnej metodzie. Jest to metoda reprezentacji górnej granicy czasu wykonania algorytmu. Reprezentuje najdłuższy czas, jaki może zająć algorytm, aby zakończyć swoje wykonanie. Funkcja -

f (n) = O (g (n))

jeśli istnieją stałe dodatnie c i n₀ takie że f(n) ≤ c * g(n) dla wszystkich n gdzie n ≥ n₀.

Notacja Omega

Notacja Omega to metoda reprezentacji dolnej granicy czasu wykonania algorytmu. Funkcja -

f (n) = Ω (g (n))

jeśli istnieją stałe dodatnie c i n₀ takie że f(n) ≥ c * g(n) dla wszystkich n gdzie n ≥ n₀.

Notacja Theta

Notacja theta to metoda reprezentacji zarówno dolnej, jak i górnej granicy czasu wykonania algorytmu. Funkcja -

f (n) = θ (g (n))

jeśli istnieją stałe dodatnie c₁, c₂, i n₀ takie, że c1 * g (n) ≤ f (n) ≤ c2 * g (n) dla wszystkich n gdzie n ≥ n₀.

Przyspieszenie algorytmu

Wydajność algorytmu równoległego jest określana przez obliczenie jego speedup. Przyspieszenie jest definiowane jako stosunek czasu wykonania najgorszego przypadku najszybszego znanego algorytmu sekwencyjnego dla danego problemu do czasu wykonania najgorszego przypadku algorytmu równoległego.

speedup =

Czas wykonania najgorszego przypadku najszybszej znanej sekwencji dla określonego problemu / Czas wykonania najgorszego przypadku algorytmu równoległego

Liczba używanych procesorów

Liczba zastosowanych procesorów jest ważnym czynnikiem w analizie wydajności algorytmu równoległego. Oblicza się koszt zakupu, utrzymania i eksploatacji komputerów. Im większa liczba procesorów wykorzystywanych przez algorytm do rozwiązania problemu, tym kosztowniejszy staje się uzyskany wynik.