Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Embarrassingly parallel
open-in-new
<h2 id="etymology">Etymology</h2> <p>"Embarrassingly" is used here to refer to parallelization problems which are "embarrassingly easy".<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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 <a href="/facts/Homotopy/1nWrPxdj">homotopy</a> continuation methods."<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> The term is first found in the literature in a 1986 book on multiprocessors by <a href="/facts/MATLAB/qPjLISCk">MATLAB</a>'s creator <a href="/facts/Cleve_Moler/o0wxumjp">Cleve Moler</a>,<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> who claims to have invented the term.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>An alternative term, <i>pleasingly parallel</i>, 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."<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="examples">Examples</h2> <p>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 <a href="/facts/%2522Hello%2c_World!%2522_program/vLn0jLlL">Hello World</a> problem could easily be parallelized with few programming considerations or computational costs. </p><p>Some examples of embarrassingly parallel problems include: </p> <ul><li><a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo method</a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>Distributed relational database queries using <a href="http://www.mysqlperformanceblog.com/2011/05/14/distributed-set-processing-with-shard-query/">distributed set processing</a>.</li> <li><a href="/facts/Numerical_integration/MwJnvcDV">Numerical integration</a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li> <li>Bulk processing of unrelated files of similar nature in general, such as photo gallery resizing and conversion.</li> <li>The <a href="/facts/Mandelbrot_set/2NVUgrVG">Mandelbrot set</a>, <a href="/facts/Perlin_noise/Eg48246G">Perlin noise</a> and similar images, where each point is calculated independently.</li> <li><a href="/facts/Rendering_(computer_graphics)/YYxfnmAq">Rendering</a> of <a href="/facts/Computer_graphics/lapBE8wv">computer graphics</a>. In <a href="/facts/Computer_animation/rPW63nm0">computer animation</a>, each <a href="/facts/Video_frame/27Uqo8WN">frame</a> or pixel may be rendered independently (see: <a href="/facts/Parallel_rendering/0wMWTncz">Parallel rendering</a>).</li> <li>Some <a href="/facts/Brute-force_search/YU2fzBIt">brute-force searches</a> in <a href="/facts/Cryptography/e94PEVau">cryptography</a>.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> Notable real-world examples include <a href="/facts/Distributed.net/xajY2Ff7">distributed.net</a> and <a href="/facts/Proof-of-work/GKI1LcQU">proof-of-work</a> systems used in <a href="/facts/Cryptocurrency/Rg6JAS8y">cryptocurrency</a>.</li> <li><a href="/facts/BLAST_(biotechnology)/uWufGxFH">BLAST</a> searches in <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a> with split databases.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li>Large scale <a href="/facts/Facial_recognition_system/mtVxaDln">facial recognition systems</a> that compare thousands of arbitrary acquired faces (e.g., a security or surveillance video via <a href="/facts/Closed-circuit_television/1JCtvSmx">closed-circuit television</a>) with similarly large number of previously stored faces (e.g., a <i><a href="/facts/Rogues_gallery/bxAT2LCf">rogues gallery</a></i> or similar <a href="/facts/No_Fly_List/hCdnt5Cc">watch list</a>).<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li>Computer simulations comparing many independent scenarios.</li> <li><a href="/facts/Genetic_algorithm/WP2AFWuW">Genetic algorithms</a>.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li> <li><a href="/facts/Statistical_ensemble_(mathematical_physics)/Nsxv4FAI">Ensemble calculations</a> of <a href="/facts/Numerical_weather_prediction/TXdbEfE4">numerical weather prediction</a>.</li> <li>Event simulation and reconstruction in <a href="/facts/Particle_physics/YgIuyj2t">particle physics</a>.</li> <li>The <a href="/facts/Marching_squares/JdlWLo2l">marching squares</a> algorithm.</li> <li>Sieving step of the <a href="/facts/Quadratic_sieve/xDrfU9xl">quadratic sieve</a> and the <a href="/facts/General_number_field_sieve/elC06ARC">number field sieve</a>.</li> <li>Tree growth step of the <a href="/facts/Random_forest/Ff1ppJEQ">random forest</a> machine learning technique.</li> <li><a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">Discrete Fourier transform</a> where each harmonic is independently calculated.</li> <li><a href="/facts/Convolutional_neural_network/kHEdnmGU">Convolutional neural networks</a> running on <a href="/facts/GPU/PTK1RQVp">GPUs</a>.</li> <li>Parallel search in <a href="/facts/Constraint_programming/rgkCK5bD">constraint programming</a><a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></li></ul> <h2 id="implementations">Implementations</h2> <ul><li>In <a href="/facts/R_(programming_language)/LSrkr8K8">R (programming language)</a> – The Simple Network of Workstations (SNOW) package implements a simple mechanism for using a set of workstations or a <a href="/facts/Beowulf_cluster/umsNXl3k">Beowulf cluster</a> for embarrassingly parallel computations.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> Similar R packages include "future", "parallel" and others.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Amdahl%2527s_law/ChdYzFx3">Amdahl's law</a> defines value <i><a href="/facts/Amdahl%2527s_law/ChdYzFx3">P</a></i>, which would be almost or exactly equal to 1 for embarrassingly parallel problems.</li> <li><a href="/facts/Cellular_automaton/6gfkjKAW">Cellular automaton</a></li> <li><a href="/facts/Connection_Machine/wxUPNe4r">Connection Machine</a></li> <li><a href="/facts/CUDA/fvPpolot">CUDA framework</a></li> <li><a href="/facts/Manycore_processor/ozoxeNzT">Manycore processor</a></li> <li><a href="/facts/Map_(parallel_pattern)/ePJMadFT">Map (parallel pattern)</a></li> <li><a href="/facts/Massively_parallel/dX7W2Nxs">Massively parallel</a></li> <li><a href="/facts/Multiprocessing/aDCfehDQ">Multiprocessing</a></li> <li><a href="/facts/Parallel_computing/nQzcpzQt">Parallel computing</a></li> <li><a href="/facts/Process-oriented_programming/Qfy1b174">Process-oriented programming</a></li> <li><a href="/facts/Shared-nothing_architecture/EXvXTQ6E">Shared-nothing architecture</a> (SN)</li> <li><a href="/facts/Symmetric_multiprocessing/T9CahUsN">Symmetric multiprocessing</a> (SMP)</li> <li><a href="/facts/Vector_processor/nYAsIKT0">Vector processor</a></li></ul> <h2 id="external-links">External links</h2> Look up <i>embarrassingly parallel</i> in Wiktionary, the free dictionary. <ul><li><a href="http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/beowulf_book/node30.html">Embarrassingly Parallel Computations</a>, Engineering a Beowulf-style Compute Cluster</li> <li>"<a href="http://www.cs.ucsb.edu/~gilbert/reports/hpec04.pdf">Star-P: High Productivity Parallel Computing</a>"</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming, Revised Reprint (revised ed.). Elsevier. p. 14. ISBN 9780123977953. Retrieved 28 February 2016. Some computational problems are "embarrassingly parallel": they can easily be divided into components that can be executed concurrently. <a href="9780123977953" target="_blank">9780123977953</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Section 1.4.4 of: Foster, Ian (1995). Designing and Building Parallel Programs. Addison–Wesley. ISBN 9780201575941. Archived from the original on 2011-03-01. <a href="9780201575941" target="_blank">9780201575941</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Alan Chalmers; Erik Reinhard; Tim Davis (21 March 2011). Practical Parallel Rendering. CRC Press. ISBN 978-1-4398-6380-0. <a href="978-1-4398-6380-0" target="_blank">978-1-4398-6380-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. ISBN 9781593274108. <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). "Parallel Homotopy Algorithms to Solve Polynomial Systems". Mathematical Software - ICMS 2006. Lecture Notes in Computer Science. Vol. 4151. pp. 225–234. doi:10.1007/11832225_22. ISBN 978-3-540-38084-9. <a href="978-3-540-38084-9" target="_blank">978-3-540-38084-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Moler, Cleve (1986). "Matrix Computation on Distributed Memory Multiprocessors". In Heath, Michael T. (ed.). Hypercube Multiprocessors. Society for Industrial and Applied Mathematics, Philadelphia. ISBN 978-0898712094. <a href="978-0898712094" target="_blank">978-0898712094</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website <a href="http://blogs.mathworks.com/cleve/2013/11/12/the-intel-hypercube-part-2-reposted/#096367ea-045e-4f28-8fa2-9f7db8fb7b01" target="_blank">http://blogs.mathworks.com/cleve/2013/11/12/the-intel-hypercube-part-2-reposted/#096367ea-045e-4f28-8fa2-9f7db8fb7b01</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. ISBN 9780898716733. <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Erricos John Kontoghiorghes (21 December 2005). Handbook of Parallel Computing and Statistics. CRC Press. ISBN 978-1-4200-2868-3. <a href="978-1-4200-2868-3" target="_blank">978-1-4200-2868-3</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Yuefan Deng (2013). Applied Parallel Computing. World Scientific. ISBN 978-981-4307-60-4. <a href="978-981-4307-60-4" target="_blank">978-981-4307-60-4</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Josefsson, Simon; Percival, Colin (August 2016). "The scrypt Password-Based Key Derivation Function". tools.ietf.org. doi:10.17487/RFC7914. Retrieved 2016-12-12. <a href="/wiki/Colin_Percival" target="_blank">/wiki/Colin_Percival</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Mathog, DR (22 September 2003). "Parallel BLAST on split databases". Bioinformatics. 19 (14): 1865–6. doi:10.1093/bioinformatics/btg250. PMID 14512366. <a href="https://doi.org/10.1093%2Fbioinformatics%2Fbtg250" target="_blank">https://doi.org/10.1093%2Fbioinformatics%2Fbtg250</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>How we made our face recognizer 25 times faster (developer blog post) <a href="http://lbrandy.com/blog/2008/10/how-we-made-our-face-recognizer-25-times-faster/" target="_blank">http://lbrandy.com/blog/2008/10/how-we-made-our-face-recognizer-25-times-faster/</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Shigeyoshi Tsutsui; Pierre Collet (5 December 2013). Massively Parallel Evolutionary Computation on GPGPUs. Springer Science & Business Media. ISBN 978-3-642-37959-8. <a href="978-3-642-37959-8" target="_blank">978-3-642-37959-8</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Youssef Hamadi; Lakhdar Sais (5 April 2018). Handbook of Parallel Constraint Reasoning. Springer. ISBN 978-3-319-63516-3. <a href="978-3-319-63516-3" target="_blank">978-3-319-63516-3</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Simple Network of Workstations (SNOW) package <a href="http://www.stat.uiowa.edu/~luke/R/cluster/cluster.html" target="_blank">http://www.stat.uiowa.edu/~luke/R/cluster/cluster.html</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> </ol>