# Embarrassingly parallel > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Embarrassingly_parallel > Markdown URL: https://mediated.wiki/source/Embarrassingly_parallel.md > Source: https://en.wikipedia.org/wiki/Embarrassingly_parallel > Source revision: 1338671164 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Problem easily dividable into parallel tasks}} In [parallel computing](/source/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.{{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.}} This is due to minimal or no dependency upon communication between the parallel tasks, or for results between them.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 }} These differ from [distributed computing](/source/distributed_computing) problems, which need communication between tasks, especially communication of intermediate results. They are easier to perform on [server farm](/source/server_farm)s which lack the special infrastructure used in a true [supercomputer](/source/supercomputer) cluster. They are well-suited to large, Internet-based [volunteer computing](/source/volunteer_computing) platforms such as [BOINC](/source/BOINC), and suffer less from [parallel slowdown](/source/parallel_slowdown). The opposite of embarrassingly parallel problems are [inherently serial problem](/source/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](/source/graphics_processing_unit), where each frame (forward method) or pixel ([ray tracing](/source/Ray_tracing_(graphics)) method) can be handled with no interdependency.{{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}} Some forms of [password cracking](/source/password_cracking) are another embarrassingly parallel task that is easily distributed on [central processing unit](/source/central_processing_unit)s, [CPU core](/source/CPU_core)s, or clusters. ==Etymology== "Embarrassingly" is used here to refer to parallelization problems which are "embarrassingly easy".Matloff, Norman (2011). ''The Art of R Programming: A Tour of Statistical Software Design'', p.347. No Starch. {{ISBN|9781593274108}}. 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](/source/homotopy) continuation methods."{{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}} The term is first found in the literature in a 1986 book on multiprocessors by [MATLAB](/source/MATLAB)'s creator [Cleve Moler](/source/Cleve_Moler),{{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 }} who claims to have invented the term.[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] 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."Kepner, Jeremy (2009). ''Parallel MATLAB for Multicore and Multinode Computers'', p.12. SIAM. {{isbn|9780898716733}}. ==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](/source/%22Hello%2C_World!%22_program) problem could easily be parallelized with few programming considerations or computational costs. Some examples of embarrassingly parallel problems include: * [Monte Carlo method](/source/Monte_Carlo_method){{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}} * Distributed relational database queries using [http://www.mysqlperformanceblog.com/2011/05/14/distributed-set-processing-with-shard-query/ distributed set processing]. * [Numerical integration](/source/Numerical_integration){{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}} * Bulk processing of unrelated files of similar nature in general, such as photo gallery resizing and conversion. * The [Mandelbrot set](/source/Mandelbrot_set), [Perlin noise](/source/Perlin_noise) and similar images, where each point is calculated independently. * [Rendering](/source/Rendering_(computer_graphics)) of [computer graphics](/source/computer_graphics). In [computer animation](/source/computer_animation), each [frame](/source/video_frame) or pixel may be rendered independently {{xref|(see: [Parallel rendering](/source/Parallel_rendering))}}. * Some [brute-force search](/source/brute-force_search)es in [cryptography](/source/cryptography).{{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}} Notable real-world examples include [distributed.net](/source/distributed.net) and [proof-of-work](/source/proof-of-work) systems used in [cryptocurrency](/source/cryptocurrency). * [BLAST](/source/BLAST_(biotechnology)) searches in [bioinformatics](/source/bioinformatics) with split databases.{{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 }} * Large scale [facial recognition system](/source/facial_recognition_system)s that compare thousands of arbitrary acquired faces (e.g., a security or surveillance video via [closed-circuit television](/source/closed-circuit_television)) with similarly large number of previously stored faces (e.g., a ''[rogues gallery](/source/rogues_gallery)'' or similar [watch list](/source/No_Fly_List)).[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) * Computer simulations comparing many independent scenarios. * [Genetic algorithm](/source/Genetic_algorithm)s.{{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}} * [Ensemble calculations](/source/Statistical_ensemble_(mathematical_physics)) of [numerical weather prediction](/source/numerical_weather_prediction). * Event simulation and reconstruction in [particle physics](/source/particle_physics). * The [marching squares](/source/marching_squares) algorithm. * Sieving step of the [quadratic sieve](/source/quadratic_sieve) and the [number field sieve](/source/General_number_field_sieve). * Tree growth step of the [random forest](/source/random_forest) machine learning technique. * [Discrete Fourier transform](/source/Discrete_Fourier_transform) where each harmonic is independently calculated. * [Convolutional neural network](/source/Convolutional_neural_network)s running on [GPU](/source/GPU)s. * Parallel search in [constraint programming](/source/constraint_programming){{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}} ==Implementations== * In [R (programming language)](/source/R_(programming_language)) – The Simple Network of Workstations (SNOW) package implements a simple mechanism for using a set of workstations or a [Beowulf cluster](/source/Beowulf_cluster) for embarrassingly parallel computations.[http://www.stat.uiowa.edu/~luke/R/cluster/cluster.html Simple Network of Workstations (SNOW) package] Similar R packages include "future", "parallel" and others. ==See also== *[Amdahl's law](/source/Amdahl's_law) defines value ''[P](/source/Amdahl's_law)'', which would be almost or exactly equal to 1 for embarrassingly parallel problems. *[Cellular automaton](/source/Cellular_automaton) *[Connection Machine](/source/Connection_Machine) *[CUDA framework](/source/CUDA) *[Manycore processor](/source/Manycore_processor) *[Map (parallel pattern)](/source/Map_(parallel_pattern)) *[Massively parallel](/source/Massively_parallel) *[Multiprocessing](/source/Multiprocessing) *[Parallel computing](/source/Parallel_computing) *[Process-oriented programming](/source/Process-oriented_programming) *[Shared-nothing architecture](/source/Shared-nothing_architecture) (SN) *[Symmetric multiprocessing](/source/Symmetric_multiprocessing) (SMP) *[Vector processor](/source/Vector_processor) ==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 --- Adapted from the Wikipedia article [Embarrassingly parallel](https://en.wikipedia.org/wiki/Embarrassingly_parallel) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Embarrassingly_parallel?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.