Английская Википедия:Embarrassingly parallel
Шаблон:Short description 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 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 volunteer computing 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 video rendering handled by a graphics processing unit, where each frame (forward method) or pixel (ray tracing method) can be handled with no interdependency.[3] Some forms of password cracking are another embarrassingly parallel task that is easily distributed on central processing units, CPU cores, or clusters.
Etymology
"Embarrassingly" is used here to refer to parallelization problems which are "embarrassingly easy".[4] 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."[5] The term is first found in the literature in a 1986 book on multiprocessors by MATLAB's creator Cleve Moler,[6] who claims to have invented the term.[7]
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."[8]
Examples
Some examples of embarrassingly parallel problems include:
- Monte Carlo analysis[9]
- Distributed relational database queries using distributed set processing.
- Numerical integration[10]
- Serving static files on a webserver to multiple users at once.Шаблон:Citation needed
- 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 of computer graphics. In computer animation, each frame or pixel may be rendered independently (see parallel rendering).
- Some brute-force searches in cryptography.[11] Notable real-world examples include distributed.net and proof-of-work systems used in cryptocurrency.
- BLAST searches in bioinformatics with split databases.[12]
- Large scale facial recognition systems 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 watch list).[13]
- Computer simulations comparing many independent scenarios.
- Genetic algorithms.[14]
- 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 number field sieve.
- Tree growth step of the random forest machine learning technique.
- Discrete Fourier transform where each harmonic is independently calculated.
- Convolutional neural networks running on GPUs.
- Hyperparameter grid search in machine learning.Шаблон:Citation needed
- Parallel search in constraint programming[15]
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.[16] Similar R packages include "future", "parallel" and others.
See also
- Amdahl's law defines value P, which would be almost or exactly equal to 1 for embarrassingly parallel problems.
- Map (parallel pattern)
- Multiprocessing
- Massively parallel
- Parallel computing
- Process-oriented programming
- Shared-nothing architecture (SN)
- Symmetric multiprocessing (SMP)
- Connection Machine
- Cellular automaton
- CUDA framework
- Manycore processor
- Vector processor
References
- ↑ Шаблон:Cite book
- ↑ Section 1.4.4 of: Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. Шаблон:ISBN.
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website
- ↑ Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. Шаблон:Isbn.
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ How we made our face recognizer 25 times faster (developer blog post)
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ Simple Network of Workstations (SNOW) package
External links
- Embarrassingly Parallel Computations, Engineering a Beowulf-style Compute Cluster
- "Star-P: High Productivity Parallel Computing"
