95.157.5.206: /* Examples */Monte Carlo Analysis is not a commonly used term. The main page on this topic has the Title Monte Carlo Method.

2025-03-29T22:35:06Z

Examples: Monte Carlo Analysis is not a commonly used term. The main page on this topic has the Title Monte Carlo Method.

New page

{{Short description|Parallel computing, a problem which is able to be trivially divided into parallelized tasks}}
In [[parallel computing]], an '''embarrassingly parallel''' workload or problem (also called '''embarrassingly parallelizable''', '''perfectly parallel''', '''delightfully parallel''' or '''pleasingly parallel''') is one where little or no effort is needed to split 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|access-date=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 due to minimal or no dependency upon communication between the 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
|author=Foster, Ian
|publisher=Addison–Wesley
|archive-url=https://web.archive.org/web/20110301095228/http://www.mcs.anl.gov/~itf/dbpp/text/node10.html
|archive-date=2011-03-01
|year=1995
|url-status=dead
|isbn=9780201575941
}}</ref>

These differ from [[distributed computing]] problems, which need communication between tasks, especially communication of intermediate results. They are easier to perform on [[server farm]]s which lack the special infrastructure used in a true [[supercomputer]] cluster. They are well-suited to large, Internet-based [[volunteer computing]] platforms such as [[BOINC]], and suffer less 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&q=%22embarrassingly+parallel%22|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==
"Embarrassingly" is used here to refer to parallelization problems which are "embarrassingly easy".<ref>Matloff, Norman (2011). ''The Art of R Programming: A Tour of Statistical Software Design'', p.347. No Starch. {{ISBN|9781593274108}}.</ref> The term may imply embarrassment on the part of developers or compilers: "Because so many important problems remain unsolved mainly due to their intrinsic computational complexity, it would be embarrassing not to develop parallel implementations of polynomial [[homotopy]] continuation methods."<ref>{{cite book|last1=Leykin|first1=Anton|last2=Verschelde|first2=Jan|last3=Zhuang|first3=Yan|title=Mathematical Software - ICMS 2006 |chapter=Parallel Homotopy Algorithms to Solve Polynomial Systems |year=2006 |volume=4151|pages=225–234|doi=10.1007/11832225_22|series=Lecture Notes in Computer Science|isbn=978-3-540-38084-9}}</ref> The term is first found in the literature in a 1986 book on multiprocessors by [[MATLAB]]'s creator [[Cleve Moler]],<ref name=hcmp>{{cite book
| contribution = Matrix Computation on Distributed Memory Multiprocessors
| author = Moler, Cleve
| publisher = Society for Industrial and Applied Mathematics, Philadelphia
| title = Hypercube Multiprocessors
| editor-last = Heath
| editor-first = Michael T.
| year = 1986
| isbn = 978-0898712094
}}</ref> who claims to have invented the term.<ref>[http://blogs.mathworks.com/cleve/2013/11/12/the-intel-hypercube-part-2-reposted/#096367ea-045e-4f28-8fa2-9f7db8fb7b01 The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website]</ref>

An alternative term, ''pleasingly parallel'', has gained some use, perhaps to avoid the negative connotations of embarrassment in favor of a positive reflection on the parallelizability of the problems: "Of course, there is nothing embarrassing about these programs at all."<ref>Kepner, Jeremy (2009). ''Parallel MATLAB for Multicore and Multinode Computers'', p.12. SIAM. {{isbn|9780898716733}}.</ref>

==Examples==
A trivial example involves serving static data. It would take very little effort to have many processing units produce the same set of bits. Indeed, the famous [["Hello, World!" program|Hello World]] problem could easily be parallelized with few programming considerations or computational costs.

Some examples of embarrassingly parallel problems include:
* [[Monte Carlo method]]<ref name="Kontoghiorghes2005">{{cite book|author=Erricos John Kontoghiorghes|title=Handbook of Parallel Computing and Statistics|url=https://books.google.com/books?id=BnNnKPkFH2kC&q=%22embarrassingly+parallel%22|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&q=%22embarrassingly+parallel%22|year=2013|publisher=World Scientific|isbn=978-981-4307-60-4}}</ref>
* Bulk processing of unrelated files of similar nature in general, such as photo gallery resizing and conversion.
* 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 {{xref|(see: [[Parallel rendering]])}}.
* Some [[brute-force search]]es in [[cryptography]].<ref>{{Cite journal|url=https://tools.ietf.org/html/rfc7914#page-2|title=The scrypt Password-Based Key Derivation Function|first1=Simon|last1=Josefsson|first2=Colin|last2=Percival|author-link2=Colin Percival|date=August 2016|website=tools.ietf.org|doi=10.17487/RFC7914 |access-date=2016-12-12}}</ref> Notable real-world examples include [[distributed.net]] and [[proof-of-work]] systems used in [[cryptocurrency]].
* [[BLAST (biotechnology)|BLAST]] searches in [[bioinformatics]] with split databases.<ref>{{cite journal |last1=Mathog |first1=DR |title=Parallel BLAST on split databases. |journal=Bioinformatics |date=22 September 2003 |volume=19 |issue=14 |pages=1865–6 |doi=10.1093/bioinformatics/btg250 |pmid=14512366|doi-access=free }}</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&q=%22embarrassingly+parallel%22|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]].
* The [[marching squares]] algorithm.
* Sieving step of the [[quadratic sieve]] and the [[General number field sieve|number field sieve]].
* Tree growth step of the [[random forest]] machine learning technique.
* [[Discrete Fourier transform]] where each harmonic is independently calculated.
* [[Convolutional neural network]]s running on [[GPU]]s.
* 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&q=%22embarrassingly+parallel%22|date=5 April 2018|publisher=Springer|isbn=978-3-319-63516-3}}</ref>

==Implementations==
* In [[R (programming language)]] – The Simple Network of Workstations (SNOW) package implements a simple mechanism for using a set of workstations or a [[Beowulf cluster]] for embarrassingly parallel computations.<ref>[http://www.stat.uiowa.edu/~luke/R/cluster/cluster.html Simple Network of Workstations (SNOW) package]</ref> Similar R packages include "future", "parallel" and others.

==See also==
*[[Amdahl's law]] defines value ''[[Amdahl's law#Parallelization|P]]'', which would be almost or exactly equal to 1 for embarrassingly parallel problems.
*[[Cellular automaton]]
*[[Connection Machine]]
*[[CUDA|CUDA framework]]
*[[Manycore processor]]
*[[Map (parallel pattern)]]
*[[Massively parallel]]
*[[Multiprocessing]]
*[[Parallel computing]]
*[[Process-oriented programming]]
*[[Shared-nothing architecture]] (SN)
*[[Symmetric multiprocessing]] (SMP)
*[[Vector processor]]

==References==
<references/>

==External links==
{{Wiktionary}}

*[http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/beowulf_book/node30.html Embarrassingly Parallel Computations], Engineering a Beowulf-style Compute Cluster
*"[http://www.cs.ucsb.edu/~gilbert/reports/hpec04.pdf Star-P: High Productivity Parallel Computing]"

{{Parallel computing}}

[[Category:Applications of distributed computing]]
[[Category:Distributed computing problems]]
[[Category:Parallel computing]]

Embarrassingly parallel - Revision history

95.157.5.206: /* Examples */Monte Carlo Analysis is not a commonly used term. The main page on this topic has the Title Monte Carlo Method.