Trápně paralelní - Embarrassingly parallel

Paralelní výpočty, paradigma ve výpočetní technice, která má spuštěných více úloh současně, může obsahovat to, co je známé jako trapně paralelní pracovní zátěž nebo problém (nazývaný také dokonale paralelní, nádherně paralelní nebo příjemně paralelní[Citace je zapotřebí ]). Trápně paralelní úkol lze považovat za triviální případ - k rozdělení problému do několika paralelních úkolů je potřeba malá nebo žádná manipulace.[1] To je často případ, kdy existuje malá nebo žádná závislost nebo potřeba komunikace mezi těmito paralelními úkoly nebo výsledků mezi nimi.[2]

Tím se liší od distribuované výpočty problémy, které vyžadují komunikaci mezi úkoly, zejména komunikace průběžných výsledků. Jsou snadno proveditelné serverové farmy kterým chybí speciální infrastruktura použitá ve skutečném superpočítač shluk. Jsou tedy velmi vhodné pro velké distribuované platformy založené na internetu, jako je BOINC a netrpí tím paralelní zpomalení. Opakem trapně paralelních problémů je neodmyslitelně sériové problémy, které nelze vůbec paralelizovat.

Běžným příkladem trapně paralelního problému je vykreslování 3D videa zpracované a grafická jednotka, kde každý snímek (metoda vpřed) nebo pixel (sledování paprsku metoda) lze zpracovat bez vzájemné závislosti.[3] Některé formy prolomení hesla jsou dalším trapně paralelním úkolem, na který se snadno distribuuje centrální procesorové jednotky, Jádra CPU nebo shluky.

Etymologie

„Trapně“ se zde používá ve stejném smyslu jako ve výrazu „an.“ rozpaky bohatství “, což znamená nadbytek - zde se odkazuje na problémy s paralelizací, které jsou„ trapně snadné “.[4] Tento výraz může také znamenat rozpaky ze strany vývojářů nebo překladačů: „Protože tolik důležitých problémů zůstává nevyřešeno hlavně kvůli jejich vnitřní výpočetní složitosti, bylo by trapné nevyvíjet paralelní implementace polynomu homotopy metody pokračování. “[5] Termín je poprvé nalezen v literatuře v knize o multiprocesorech od roku 1986 MATLAB tvůrce Cleve Moler,[6] kdo tvrdí, že tento pojem vynalezl.[7]

Alternativní termín, příjemně paralelní, získal určité využití, snad proto, aby se vyhnul negativním konotacím rozpaků ve prospěch pozitivní reflexe paralelizovatelnosti problémů: „Samozřejmě v těchto programech není vůbec nic trapného.“[8]

Příklady

Mezi příklady trapně paralelních problémů patří:

Implementace

  • v R (programovací jazyk) - Balíček SNOW (Simple Network of Workstations) implementuje jednoduchý mechanismus pro použití sady pracovních stanic nebo Klastr Beowulf pro trapně paralelní výpočty.[16]

Viz také

Reference

  1. ^ Herlihy, Maurice; Shavit, Nir (2012). Umění víceprocesorového programování, revidovaný dotisk (přepracované vydání). Elsevier. str. 14. ISBN  9780123977953. Citováno 28. února 2016. Některé výpočtové problémy jsou „trapně paralelní“: lze je snadno rozdělit na komponenty, které lze provádět současně.
  2. ^ Oddíl 1.4.4: Foster, Ian (1995). Navrhování a budování paralelních programů. Addison – Wesley. ISBN  9780201575941. Archivovány od originál dne 01.03.2011.
  3. ^ Alan Chalmers; Erik Reinhard; Tim Davis (21. března 2011). Praktické paralelní vykreslování. CRC Press. ISBN  978-1-4398-6380-0.
  4. ^ Matloff, Norman (2011). Umění programování R: Prohlídka statistického softwarového designu, str. 347. Žádný škrob. ISBN  9781593274108.
  5. ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). Parallel Homotopy Algorithms to Solve Polynomial Systems. Sborník ICMS. Přednášky z informatiky. 4151. str. 225–234. doi:10.1007/11832225_22. ISBN  978-3-540-38084-9.
  6. ^ Moler, Cleve (1986). Heath, Michael T. (ed.). Maticový výpočet na multiprocesorech s distribuovanou pamětí. Hypercube multiprocesory. Společnost pro průmyslovou a aplikovanou matematiku, Philadelphia. ISBN  978-0898712094.
  7. ^ Hypercube Intel část 2 byla znovu zveřejněna na blogu Cleve's Corner na webu The MathWorks
  8. ^ Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, str.12. SIAM. ISBN  9780898716733.
  9. ^ Erricos John Kontoghiorghes (21. prosince 2005). Příručka pro paralelní výpočet a statistiku. CRC Press. ISBN  978-1-4200-2868-3.
  10. ^ Yuefan Deng (2013). Aplikované paralelní výpočty. World Scientific. ISBN  978-981-4307-60-4.
  11. ^ Simon, Josefsson; Colin, Percival (srpen 2016). "Funkce scrypt odvození klíče na základě hesla". tools.ietf.org. Citováno 2016-12-12.
  12. ^ Fórum SeqAnswers
  13. ^ Jak jsme 25krát rychlejší rozpoznávání obličeje (příspěvek na blogu vývojáře)
  14. ^ Shigeyoshi Tsutsui; Pierre Collet (5. prosince 2013). Masivně paralelní evoluční výpočet na GPGPU. Springer Science & Business Media. ISBN  978-3-642-37959-8.
  15. ^ Youssef Hamadi; Lakhdar Sais (5. dubna 2018). Příručka uvažování o paralelním omezení. Springer. ISBN  978-3-319-63516-3.
  16. ^ Balíček Simple Network of Workstations (SNOW)

externí odkazy