Miara Karpa-Flatta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Miara Karpa-Flatta jest miarą równoległości (parallelization) kodu w systemach z procesorami równoległymi. Miara ta istnieje jako dodatek do Prawa Amdahla oraz Prawa Gustafsona jako wskazówka w jakim stopniu dany program komputerowy jest zrównoleglony. Została ona zaproponowana przez Alana H. Karpa and Horace`a P. Flatta w 1990 roku.

Opis[edytuj | edytuj kod]

Biorąc pod uwagę obliczenia wykazujące przyspieszenie (speedup) \psi na p procesorach, gdzie p > 1, na drodze eksperymentu określono frakcję szeregową (serial fraction) e definiuje się jako miarę Karpa-Flatta, mianowicie:

e = \frac{\frac{1}{\psi}-\frac{1}{p}}{1-\frac{1}{p}}

Im mniejsza wartość e tym lepsza współbieżność (zrównoleglenie).

Uzasadnienie[edytuj | edytuj kod]

Istnieje wiele sposobów na zmierzenie wydajności algorytmu równoległego (parallel algorithm) wykonywującego się na procesorze równoległym. Miara Karpa-Flatta definiuje miarę, która ujawnia aspekty wydajnościowe, które nie są zbyt łatwo dostrzegalne w innych miarach. Pseudo-"wyprowadzenie" wynika z Prawa Amdahla, co można zapisać jako:

T(p) = T_s + \frac{T_p}{p}

Gdzie:

  • T(p) jest całkowitym czasem wykonania się kodu na p-procesorowym systemie
  • T_s jest to czas wykonywania się szeregowej części kodu
  • T_p jest to czas wykonywania się równoległej części kodu na jednym procesorze
  • p jest liczba procesorów

wynik otrzymywany jest poprzez dzielenie p = 1 mianowicie T(1) = T_s + T_p, jeśli zdefinujemy szeregową frakcję e = \frac{T_s}{T(1)} wółczas równanie można zapisać jako:

T(p) = T(1) e + \frac{T(1) (1-e)}{p}

In terms of the speedup \psi = \frac{T(1)}{T(p)} :

\frac{1}{\psi} = e + \frac{1-e}{p}

Rozwiązując frakcję szeregową otrzymujemy miarę Karpa-Flatta jak wyżej. Należy zaznaczyć, że to nie pochodzi z Prawa Amdahla jako, że lewa strona reprezentuje miarę (metric), a nie matematycznie obliczoną ilość. Powyższe działania pokazują, że miara Karpa-Flatta jest zgodna z Prawem Amdahla.

Użycie[edytuj | edytuj kod]

Podczas gdy szeregowa frakcja e jest często opisywana w literaturze informatycznej, jest rzadko używana jako narzędzie diagnostyczne do sprawdzania wzrostu wydajności (speedup) oraz efektywności algorytmów (efficiency). Karp and Flatt mieli nadzieję to zmienić proponując tą miarę. Wskaźnik ten odnosi się do niedoskonałości innych praw i ilości używanych do pomiaru zrównoleglenia kodu programu komputerowego. W szczególności Prawo Amdahla nie bierze pod uwagę problemów związanych z rozłożeniem obciążenia obliczeniowego (load balancing) ani z zależnościami dotyczącymi overhead. Wykorzystanie frakcji szeregowej pozwoliło na zdobycie przewagi nad innymi miarami, w szczególności jako że liczba procesorów wzrasta.

Jeśli chodzi o problem stałego rozmiaru, efektywność zazwyczaj spadała wraz ze wzrostem liczby procesorów. Dzięki użyciu szeregowej frakcji uzyskanej metodami doświadczalnymi przy użyciu miary Karpa-Flatta, można stwierdzić czy spadek wydajności jest wynikiem ograniczonych możliwości związanych z przetwarzaniem równoległym lub wzrost wydajności związany z zastosowanymi algorytmicznymi lub architekturalnymi zaleznosciami overhead.

Przypisy[edytuj | edytuj kod]

  • Quinn Michael J, Parallel Programming in C with MPI and OpenMP McGraw-Hill Inc. 2004. ISBN 0-07-058201-7
  • Karp Alan H. and Flatt Horace P. Measuring Parallel Processor Performance, Communication of the ACM Volume 33 Number 5, May 1990

Linki zewnętrzne[edytuj | edytuj kod]