Embarrassingly parallel: Difference between revisions

Revision as of 23:39, 11 October 2020

Revision as of 20:12, 10 November 2020

Line 1:

[[Parallel computing]], a paradigm in computing which has multiple tasks running simultaneously, might contain what is known as an '''embarrassingly parallel''' workload or problem (also called '''perfectly parallel''', '''delightfully parallel''' or '''pleasingly parallel'''{{citation needed|date=October 2020}}). An embarrassingly parallel task can be considered a trivial case - little or no manipulation is needed to separate the problem into a number of parallel tasks.<ref>{{cite book|last1=Herlihy|first1=Maurice|last2=Shavit|first2=Nir|title=The Art of Multiprocessor Programming, Revised Reprint|date=2012|publisher=Elsevier|isbn=9780123977953|page=14|edition=revised|url=https://books.google.com/books?id=vfvPrSz7R7QC&q=embarrasingly#v=onepage&q=embarrasingly&f=false|accessdate=28 February 2016|quote=Some computational problems are “embarrassingly parallel”: they can easily be divided into components that can be executed concurrently.}}</ref> This is often the case where there is little or no dependency or need for communication between those parallel tasks, or for results between them.<ref name=dbpp>Section 1.4.4 of: {{cite book

|url=http://www.mcs.anl.gov/~itf/dbpp/text/node10.html

|title=Designing and Building Parallel Programs

Line 13:

Thus, these are different from [[distributed computing]] problems that need communication between tasks, especially communication of intermediate results. They are easy to perform on [[server farm]]s which lack the special infrastructure used in a true [[supercomputer]] cluster. They are thus well suited to large, Internet-based distributed platforms such as [[BOINC]], and do not suffer from [[parallel slowdown]]. The opposite of embarrassingly parallel problems are [[inherently serial problem]]s, which cannot be parallelized at all.

A common example of an embarrassingly parallel problem is 3D video rendering handled by a [[graphics processing unit]], where each frame (forward method) or pixel ([[Ray tracing (graphics)|ray tracing]] method) can be handled with no interdependency.<ref name="ChalmersReinhard2011">{{cite book|author1=Alan Chalmers|author2=Erik Reinhard|author3=Tim Davis|title=Practical Parallel Rendering|url=https://books.google.com/books?id=loxhtzzG1FYC&printsec=frontcover#v=onepage&q=%22embarrassingly%20parallel+parallel%22&f=false|date=21 March 2011|publisher=CRC Press|isbn=978-1-4398-6380-0}}</ref> Some forms of [[password cracking]] are another embarrassingly parallel task that is easily distributed on [[central processing unit]]s, [[CPU core]]s, or clusters.

==Etymology==

Line 31:

==Examples==

Some examples of embarrassingly parallel problems include:

* [[Monte Carlo analysis]]<ref name="Kontoghiorghes2005">{{cite book|author=Erricos John Kontoghiorghes|title=Handbook of Parallel Computing and Statistics|url=https://books.google.com/books?id=BnNnKPkFH2kC&printsec=frontcover#v=onepage&q=%22embarrassingly%20parallel+parallel%22&f=false|date=21 December 2005|publisher=CRC Press|isbn=978-1-4200-2868-3}}</ref>

* Distributed relational database queries using [http://www.mysqlperformanceblog.com/2011/05/14/distributed-set-processing-with-shard-query/ distributed set processing].

* [[Numerical integration]]<ref name="Deng2013">{{cite book|author=Yuefan Deng|title=Applied Parallel Computing|url=https://books.google.com/books?id=YS9wvVeWrXgC&printsec=frontcover#v=onepage&q=%22embarrassingly%20parallel+parallel%22&f=false|year=2013|publisher=World Scientific|isbn=978-981-4307-60-4}}</ref>

* Serving static files on a webserver to multiple users at once.{{citation needed|date=June 2019}}

* The [[Mandelbrot set]], [[Perlin noise]] and similar images, where each point is calculated independently.

* [[Rendering (computer graphics)|Rendering]] of [[computer graphics]]. In [[computer animation]], each [[video frame|frame]] or pixel may be rendered independently (see [[parallel rendering]]).

* [[Brute-force search]]es in [[cryptography]].<ref>{{Cite web|url=https://tools.ietf.org/html/rfc7914#page-2|title=The scrypt Password-Based Key Derivation Function|lastlast1=Simon|firstfirst1=Josefsson|last2=Colin|first2=Percival|date=August 2016|website=tools.ietf.org|publisher=|access-date=2016-12-12}}</ref> Notable real-world examples include [[distributed.net]] and [[proof-of-work]] systems used in [[cryptocurrency]].

* [[BLAST]] searches in [[bioinformatics]] for multiple queries (but not for individual large queries).<ref>[http://seqanswers.com/forums/showpost.php?p=21050&postcount=3 SeqAnswers forum]</ref>

* Large scale [[facial recognition system]]s that compare thousands of arbitrary acquired faces (e.g., a security or surveillance video via [[closed-circuit television]]) with similarly large number of previously stored faces (e.g., a ''[[rogues gallery]]'' or similar [[No Fly List|watch list]]).<ref>[http://lbrandy.com/blog/2008/10/how-we-made-our-face-recognizer-25-times-faster/ How we made our face recognizer 25 times faster] (developer blog post)</ref>

* Computer simulations comparing many independent scenarios.

* [[Genetic algorithm]]s.<ref name="TsutsuiCollet2013">{{cite book|author1=Shigeyoshi Tsutsui|author2=Pierre Collet|title=Massively Parallel Evolutionary Computation on GPGPUs|url=https://books.google.com/books?id=Hv68BAAAQBAJ&printsec=frontcover#v=onepage&q=%22embarrassingly%20parallel+parallel%22&f=false|date=5 December 2013|publisher=Springer Science & Business Media|isbn=978-3-642-37959-8}}</ref>

* [[Statistical ensemble (mathematical physics)|Ensemble calculations]] of [[numerical weather prediction]].

* Event simulation and reconstruction in [[particle physics]].

Line 50:

* [[Convolutional neural network]]s running on [[GPU]]s.

* [[Hyperparameter optimization#Grid_search|Hyperparameter grid search]] in machine learning.{{citation needed|date=May 2019}}

* Parallel search in [[constraint programming]]<ref name="HamadiSais2018">{{cite book|author1=Youssef Hamadi|author2=Lakhdar Sais|title=Handbook of Parallel Constraint Reasoning|url=https://books.google.com/books?id=w5JUDwAAQBAJ&printsec=frontcover#v=onepage&q=%22embarrassingly%20parallel+parallel%22&f=false|date=5 April 2018|publisher=Springer|isbn=978-3-319-63516-3}}</ref>

==Implementations==