Trapně paralelní - Embarrassingly parallel

V paralelních výpočtech je trapně paralelní pracovní zátěž nebo problém (také nazývaný trapně paralelizovatelný , dokonale paralelní , nádherně paralelní nebo příjemně paralelní ), kde je zapotřebí malého nebo žádného úsilí k oddělení problému do několika paralelních úkolů. 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.

Liší se tedy od problémů s distribuovaným výpočtem, které vyžadují komunikaci mezi úkoly, zejména komunikaci průběžných výsledků. Jsou snadno proveditelné na serverových farmách, které postrádají speciální infrastrukturu používanou ve skutečném superpočítačovém klastru. Jsou tedy velmi vhodné pro velké distribuované platformy založené na internetu, jako je BOINC , a netrpí paralelním zpomalením . Opakem trapně paralelních problémů jsou 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é grafickou jednotkou , kde každý snímek (metoda vpřed) nebo pixel ( metoda sledování paprsku ) lze zpracovat bez vzájemné závislosti. Některé formy prolomení hesla jsou dalším trapně paralelním úkolem, který je snadno distribuován na centrálních procesorových jednotkách , jádrech CPU nebo klastrech.

Etymologie

„Trapně“ se zde používá ve stejném smyslu jako ve výrazu „ trapnost bohatství “, což znamená nadbytek - zde se odkazuje na problémy s paralelizací, které jsou „trapně snadné“. Termín 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 metod pokračování polynomiální homotopy .“ Termín je poprvé nalezen v literatuře v knize o multiprocesorech od roku 1986 od tvůrce MATLABu Cleve Molera , který tvrdí, že tento pojem vynalezl.

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

Příklady

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

Implementace

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

Viz také

Reference

  1. ^ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming, Revised Reprint (revised ed.). Elsevier. p. 14. ISBN 9780123977953. Vyvolány 28 February 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álu dne 2011-03-01.
  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 , s.12 . SIAM. ISBN  9780898716733 .
  9. ^ Erricos John Kontoghiorghes (21 prosince 2005). Příručka paralelního výpočtu a statistiky . 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. ^ Josefsson, Simon; Percival, Colin (srpen 2016). Msgstr "Funkce odvození klíče podle hesla" . tools.ietf.org . Citováno 2016-12-12 .
  12. ^ Fórum SeqAnswers
  13. ^ Jak jsme udělali náš nástroj pro rozpoznávání tváře 25krát rychlejší (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