Karp – Flattova metrika - Karp–Flatt metric

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Karp – Flattova metrika je měřítkem paralelizace kódu v paralelní procesor systémy. Tato metrika existuje navíc k Amdahlův zákon a Gustafsonův zákon jako údaj o tom, do jaké míry je konkrétní počítačový kód paralelizován. Navrhli to Alan H. Karp a Horace P. Flatt v roce 1990.

Popis

Vzhledem k tomu, že paralelní výpočet vykazuje zrychlit ${displaystyle psi}$ na ${displaystyle p}$ procesory, kde ${displaystyle p}$ > 1, experimentálně stanoveno sériový zlomek ${displaystyle e}$ je definována jako Karp – Flattova metrika, viz:

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

Čím nižší je hodnota ${displaystyle e}$, tím lepší je paralelizace.

Odůvodnění

Existuje mnoho způsobů, jak měřit výkon a paralelní algoritmus běží na paralelním procesoru. Metrika Karp – Flatt definuje metriku, která odhaluje aspekty výkonu, které nelze snadno rozeznat od jiných metrik. Z toho vyplývá druhová pseudo- „derivace“ Amdahlův zákon, kterou lze napsat jako:

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

Kde:

• ${displaystyle T (p)}$ je celková doba potřebná k provedení kódu v a ${displaystyle p}$-procesorový systém
• ${displaystyle T_ {s}}$ je čas potřebný ke spuštění sériové části kódu
• ${displaystyle T_ {p}}$ je čas potřebný pro spuštění paralelní části kódu v jednom procesoru
• ${displaystyle p}$ je počet procesorů

s výsledkem získaným dosazením ${displaystyle p}$ = 1 viz. ${displaystyle T (1) = T_ {s} + T_ {p}}$, pokud definujeme sériový zlomek ${displaystyle e}$ = ${displaystyle {frac {T_ {s}} {T (1)}}}$ potom lze rovnici přepsat na

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

Z hlediska zrychlit ${displaystyle psi}$ = ${displaystyle {frac {T (1)} {T (p)}}}$ :

${displaystyle {frac {1} {psi}} = e + {frac {1-e} {p}}}$

Při řešení sériového zlomku dostaneme metodu Karp – Flatt, jak je uvedeno výše. Všimněte si, že nejde o „odvození“ od Amdahlova zákona, protože levá strana představuje a metrický spíše než matematicky odvozená veličina. Výše uvedené ošetření pouze ukazuje, že metrika Karp – Flatt je v souladu s Amdahlovým zákonem.

Použití

Zatímco sériový zlomek e je často zmiňován v počítačová věda literatury, byl zřídka používán jako diagnostický nástroj zrychlit a účinnost jsou. Karp a Flatt doufali, že to napraví navržením této metriky. Tato metrika řeší nedostatky jiných zákonů a veličin používaných k měření paralelizace počítačového kódu. Zejména Amdahlův zákon nebere v úvahu vyvažování zátěže problémy, ani to nezabere nad hlavou v úvahu. Použití sériového zlomku jako metriky představuje určité výhody oproti ostatním, zejména s rostoucím počtem procesorů.

U problému pevné velikosti se účinnost paralelního výpočtu obvykle snižuje s rostoucím počtem procesorů. Pomocí sériového zlomku získaného experimentálně pomocí metriky Karp – Flatt můžeme určit, zda je snížení účinnosti způsobeno omezenými příležitostmi paralelismu nebo zvýšením algoritmické nebo architektonické režie.

Reference

• Karp, Alan H. & Flatt, Horace P. (1990). "Měření výkonu paralelního procesoru". Komunikace ACM. 33 (5): 539–543. doi:10.1145/78607.78614.
• Quinn, Michael J. (2004). Paralelní programování v C s MPI a OpenMP. Boston: McGraw-Hill. ISBN  0-07-058201-7.

externí odkazy

• Poznámky k přednášce o metrice Karp – Flatt - Virginia Tech