Analýza paralelních algoritmů - Analysis of parallel algorithms

Tento článek pojednává o analýza z paralelní algoritmy. Stejně jako v analýze „obyčejných“, sekvenčních, algoritmů, je typicky zájem o člověka asymptotické hranice spotřeby zdrojů (hlavně času stráveného výpočtem), ale analýza se provádí v přítomnosti více procesorových jednotek, které spolupracují na provádění výpočtů. Lze tedy určit nejen to, kolik „kroků“ výpočet trvá, ale také to, jak rychlejší bude, když se zvýší počet procesorů. Přístup k analýze funguje tak, že se nejprve potlačí (nebo abstrahuje) počet procesorů. Následující odstavec na pozadí vysvětluje, jak se poprvé objevila abstrakce počtu procesorů.

Shiloach a Vishkin původně zavedli takzvaný rámec pracovní doby (WT) (někdy nazývaný pracovní hloubka nebo pracovní rozpětí). [1]pro konceptualizaci a popis paralelních algoritmů. V rámci WT je nejprve popsán paralelní algoritmus z hlediska paralelních kol. Pro každé kolo jsou charakterizovány operace, které mají být provedeny, ale lze potlačit několik problémů. Například nemusí být jasný počet operací v každém kole, nemusí být zmíněny procesory a nemusí být účtovány žádné informace, které mohou pomoci při přiřazení procesorů k úlohám. Zadruhé jsou poskytovány potlačené informace. Zahrnutí potlačené informace je ve skutečnosti vedeno důkazem plánovací věty kvůli Brentovi,[2] což je vysvětleno dále v tomto článku. Rámec WT je užitečný, protože i když může značně zjednodušit počáteční popis paralelního algoritmu, vložení podrobností potlačených tímto počátečním popisem není často příliš obtížné. Například rámec WT byl přijat jako základní rámec prezentace v knihách o paralelních algoritmech (pro Paralelní stroj s náhodným přístupem PRAM model) [3]a ,[4] stejně jako v poznámkách ke třídě.[5] Níže uvedený přehled vysvětluje, jak lze rámec WT použít k analýze obecnějších paralelních algoritmů, i když jejich popis není v rámci WT framework k dispozici.

Přehled

Předpokládejme, že výpočty jsou prováděny na počítači, který má str procesory. Nechat Tstr označuje čas, který vyprší mezi začátkem výpočtu a jeho koncem. Analýza výpočtů provozní doba zaměřuje se na následující pojmy:

  • The práce výpočtu provedeného str processors je celkový počet primitivních operací, které procesory provádějí.[6] Ignorování režie komunikace ze synchronizace procesorů, to se rovná času použitému ke spuštění výpočtu na jednom procesoru, označeném T1.
  • The hloubka nebo rozpětí je délka nejdelší série operací, které musí být provedeny postupně kvůli datové závislosti (dále jen kritická cesta). Hloubku lze také nazvat délka kritické cesty výpočtu.[7] Minimalizace hloubky / rozpětí je důležitá při navrhování paralelních algoritmů, protože hloubka / rozpětí určuje nejkratší možnou dobu provedení.[8] Alternativně lze rozpětí definovat jako čas T∞ strávené výpočty pomocí idealizovaného stroje s nekonečným počtem procesorů.[9]
  • The náklady výpočtu je množství pTstr. To vyjadřuje celkovou dobu strávenou všemi procesory výpočtem i čekáním.[6]

Několik užitečných výsledků vyplývá z definic práce, rozpětí a nákladů:

  • Pracovní právo. Cena je vždy přinejmenším práce: pTstr ≥ T1. To vyplývá ze skutečnosti, že str procesory mohou pracovat maximálně str paralelní operace.[6][9]
  • Rozpětí zákona. Konečné číslo str procesorů nemůže překonat nekonečné množství, takže Tstr ≥ T∞.[9]

Pomocí těchto definic a zákonů lze uvést následující měřítka výkonu:

  • Zrychlit je nárůst rychlosti dosažený paralelním spuštěním ve srovnání se sekvenčním spuštěním: Sstr = T1 ∕ Tstr. Když je zrychlení Ω (n) pro velikost vstupu n (použitím velká O notace ), zrychlení je lineární, což je u jednoduchých modelů výpočtu optimální, protože to naznačuje pracovní zákon T1 ∕ Tstr ≤ str (superlineární zrychlení v praxi může nastat kvůli hierarchie paměti účinky). Situace T1 ∕ Tstr = str se nazývá perfektní lineární zrychlení.[9] Algoritmus, který vykazuje lineární zrychlení, se říká škálovatelné.[6]
  • Účinnost je zrychlení na procesor, Sstr ∕ str.[6]
  • Rovnoběžnost je poměr T1 ∕ T∞. Představuje maximální možné zrychlení na libovolném počtu procesorů. Podle zákona o rozpětí omezuje paralelismus zrychlení: pokud str > T1 ∕ T∞, pak:

.[9]

  • The ochablost je T1 ∕ (pT∞). Povolná vůle menší než jedna znamená (podle zákona o rozpětí), že je nemožné dokonalé lineární zrychlení str procesory.[9]

Provádění na omezeném počtu procesorů

Analýza paralelních algoritmů se obvykle provádí za předpokladu, že je k dispozici neomezený počet procesorů. To je nereálné, ale není to problém, protože jakýkoli výpočet, který může běžet paralelně N procesory lze spustit na str < N procesory tím, že umožní každému procesoru vykonávat více pracovních jednotek. Výsledek s názvem Brentův zákon uvádí, že lze takovou „simulaci“ provést včas Tstr, ohraničený[10]

nebo, méně přesně,[6]

Alternativní prohlášení o mezích zákona Tstr nad a pod podle

.

ukazující, že rozpětí (hloubka) T∞ a práce T1 společně poskytují rozumné meze pro výpočetní čas.[2]

Reference

  1. ^ Shiloach, Yossi; Vishkin, Uzi (1982). „An Ó(n2 logn) paralelní algoritmus maximálního toku ". Journal of Algorithms. 3 (2): 128–146. doi:10.1016 / 0196-6774 (82) 90013-X.
  2. ^ A b Brent, Richard P. (1974-04-01). "Paralelní vyhodnocení obecných aritmetických výrazů". Deník ACM. 21 (2): 201–206. CiteSeerX  10.1.1.100.9361. doi:10.1145/321812.321815. ISSN  0004-5411. S2CID  16416106.
  3. ^ JaJa, Joseph (1992). Úvod do paralelních algoritmů. Addison-Wesley. ISBN  978-0-201-54856-3.
  4. ^ Keller, Jorg; Kessler, Cristoph W .; Traeff, Jesper L. (2001). Praktické programování PRAM. Wiley-Interscience. ISBN  978-0-471-35351-5.
  5. ^ Vishkin, Uzi (2009). Paralelní myšlení: Některé základní datově paralelní algoritmy a techniky, 104 stran (PDF). Poznámky ke kurzům o paralelních algoritmech vyučovaných od roku 1992 na University of Maryland, College Park, Tel Aviv University a Technion.
  6. ^ A b C d E F Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Paralelní algoritmy. CRC Press. str. 10. CiteSeerX  10.1.1.466.8142.
  7. ^ Blelloch, Guy (1996). „Programování paralelních algoritmů“ (PDF). Komunikace ACM. 39 (3): 85–97. CiteSeerX  10.1.1.141.5884. doi:10.1145/227234.227246. S2CID  12118850.
  8. ^ Michael McCool; James Reinders; Arch Robison (2013). Strukturované paralelní programování: vzory pro efektivní výpočet. Elsevier. s. 4–5.
  9. ^ A b C d E F Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Úvod do algoritmů (3. vyd.). MIT Press a McGraw-Hill. str. 779–784. ISBN  0-262-03384-4.
  10. ^ Gustafson, John L. (2011). „Brentova věta“. Encyclopedia of Parallel Computing. str. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN  978-0-387-09765-7.