Miara Karpa-Flatta

Miara Karpa-Flatta – miara 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

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

Istnieje wiele sposobów na zmierzenie wydajności algorytmu równoległego (parallel algorithm) wykonują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)$ – całkowity czas wykonania się kodu na $p$-procesorowym systemie,

$T_{s}$ – czas wykonywania się szeregowej części kodu,

$T_{p}$ – czas wykonywania się równoległej części kodu na jednym procesorze,

$p$ – liczba procesorów.

Wynik otrzymywany jest poprzez dzielenie $p=1,$ mianowicie $T(1)=T_{s}+T_{p},$ jeśli zdefiniujemy szeregową frakcję $e={\frac {T_{s}}{T(1)}},$ wówczas 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

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 zależnościami overhead.

Przypisy

• 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

• Lecture Notes on Karp-Flatt metric – Virginia Tech