Embarrassingly parallel

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In parallel computing, an embarrassingly parallel workload or problem (also called perfectly parallel or pleasingly parallel) is one where little or no effort is needed to separate the problem into a number of parallel tasks.[1] 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.[2]

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 farms 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 problems, which cannot be parallelized at all.

A common example of an embarrassingly parallel problem is 3d rendering handled by a graphics processing unit, where many vertices and pixels may be handled with no interdependency.

Etymology of the term[edit]

The genesis of the phrase "embarrassingly parallel" can be understood in the same context as 'embarras de richesses' in French, meaning too rich. It is a comment on the ease of parallelizing such applications, and that it would be embarrassing for the programmer or compiler to not take advantage of such an obvious opportunity to improve performance. "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."[3] Contrastingly, the term may refer to parallelizing which is, "embarrassingly easy".[4] It is first found in the literature in a 1986 book on multiprocessors by MATLAB's co-founder Cleve Moler.[5] Moler claims to have invented this term.[6]

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."[7]

Examples[edit]

Some examples of embarrassingly parallel problems include:

Implementations[edit]

See also[edit]

References[edit]

  1. ^ 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. 
  2. ^ Section 1.4.4 of: Foster, Ian (1995). "Designing and Building Parallel Programs". Addison–Wesley (ISBN 9780201575941). Archived from the original on 2011-02-21. 
  3. ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). "Parallel Homotopy Algorithms to Solve Polynomial Systems". Proceedings of ICMS 2006. 
  4. ^ Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. ISBN 9781593274108.
  5. ^ Moler, Cleve (1986). Heath, Michael T., ed. "Matrix Computation on Distributed Memory Multiprocessors". Hypercube Multiprocessors (Society for Industrial and Applied Mathematics, Philadelphia). ISBN 0898712092. 
  6. ^ The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website
  7. ^ Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. ISBN 9780898716733.
  8. ^ SeqAnswers forum
  9. ^ How we made our face recognizer 25 times faster (developer blog post)
  10. ^ Simple Network of Workstations (SNOW) package

External links[edit]