1 ZŁOŻONOŚĆ ALGORYTMÓW RÓWNOLEGŁYCH

2 T - czas wykonania programu równoległegoto czas od momentu gdy pierwszy procesor rozpoczyna wykonanie programu do momentu gdy ostatni procesor zakończy wykonywanie programu T = f ( N, P, U, ....) N - rozmiar problemu P - liczba procesorów U - liczba procesów ( zadań )

3 T = Dwa sposoby definiowania T : (1) T = Tjcomp + Tjcomm + Tjidle(2) T = ( Tcomp + Tcomm + Tidle ) /P (**) T =

4 Tcomm = Tsend + Trecv = TmsgTmsg = ts + tw * L

5 ..... Tmsg= ts + (mtw + tk) * d Tmsg = ts + mtw * dPodstawowe operacje komunikacyjne i ich złożoność na różnych architekturach 1 2 ..... d P' P'' Oznaczenia : m rozmiar wiadomości d długość drogi tk czas przesłania nagłówka wiadomości m tw czas przesłania reszty wiadomości ts czas startu dla jednego "odcinka" Tmsg= ts + (mtw + tk) * d Tmsg = ts + mtw * d

6 Procesy tworzą pierścień (ring) d  P/2P - liczba procesów Procesy tworzą pierścień (ring) d  P/2 Tmsg = ts + tw*m*P/2 Procesy tworzą siatkę dwuwymiarową (mesh) d  2 * P/2  Tmsg = ts + 2 * tw*m* P /2 Procesy tworzą kostkę (hypercube) d  logP Tmsg = ts + tw*m* logP

7 TS - złożoność czasowa najszybszego algorytmu sekwencyjnegoPrzyśpieszenie S = TS/ TP TS - złożoność czasowa najszybszego algorytmu sekwencyjnego TP złożoność czasowa algorytmu równoległego

8 Przykład : DOD Dane : N procesorów (kostka), Pi posiada jedną liczbę rzeczywistą Xi Wynik : X XN w P0 TS(DOD) = ( N ) TP(DOD) = ( logN ) S(DOD) =  ( N/logN ) Uwagi: S  p p - liczba procesorów S = p idealny równoległy komputer może...

9 Efektywność E = S/p Przykład : Uwagi : E = 1 w idealnym systemieE(DOD) =  ( 1/logN ) Uwagi : E = w idealnym systemie 0 < E < 1 E = TS / (p*TP)

10 Koszt Kpar = TP * p Równoległy algorytm jest optymalny ze względu na koszt jeśli jego Kpar jest proporcjonalny do TS E = (1) dla optymalnych systemów Kpar(DOD) = ( NlogN ) Stąd algorytm nie jest optymalny ze względu na koszt.