Miara Karpa-Flatta 📖 Wikipedia

Ten artykuł należy dopracować:

→ poprawić tłumaczenie fragmentów tekstu/pojęć (uwaga! nie należy używać automatycznych translatorów bez sprawdzenia uzyskanego dzięki nim tłumaczenia),
artykuł zawiera linki wewnętrzne do pojęć w języku angielskim.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.

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

${\displaystyle e={\frac {{\frac {1}{\psi }}-{\frac {1}{p}}}{1-{\frac {1}{p}}}}.}$

Im mniejsza wartość ${\displaystyle e}$ tym lepsza współbieżność (zrównoleglenie).

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:

${\displaystyle T(p)=T_{s}+{\frac {T_{p}}{p}},}$

gdzie:

${\displaystyle T(p)}$ – całkowity czas wykonania się kodu na ${\displaystyle p}$-procesorowym systemie,

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

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

${\displaystyle p}$ – liczba procesorów.

Wynik otrzymywany jest poprzez dzielenie ${\displaystyle p=1,}$ mianowicie ${\displaystyle T(1)=T_{s}+T_{p},}$ jeśli zdefiniujemy szeregową frakcję ${\displaystyle e={\frac {T_{s}}{T(1)}},}$ wówczas równanie można zapisać jako:

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

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

${\displaystyle {\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.

Podczas gdy szeregowa frakcja ${\displaystyle 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.

• 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.

• Lecture Notes on Karp-Flatt metric – Virginia Tech