Extreme parallelism (extremely parallel task, English embarrassingly parallel ) is a type of tasks in parallel computing systems, for which it is not necessary to exert great efforts when dividing into several separate parallel tasks (parallelization). Most often, there is no dependence (or connection) between these parallel tasks, that is, their results do not affect each other. [one]
Extremely parallel tasks practically do not require coordination between the results of individual steps, which distinguishes them from distributed computing tasks that require the connection of intermediate results. Parallel tasks are easy to execute on server farms (server clusters), they are well suited for large distributed platforms on the Internet, such as BOINC .
A typical example of an extremely parallel task is the work of the graphic processor (GPU) when calculating 3D projections , when each pixel on the screen can be calculated independently.
Content
Examples
Some examples of extremely parallel tasks:
- Serving static files on a web server .
- Calculation of elements of the Mandelbrot set and other fractals , when each point can be calculated independently.
- Rendering in computer graphics . In ray tracing, each pixel can be worked out independently. In computer animation, each frame can be processed independently.
- Full search or βsearches of brute forceβ - search in cryptography by sequential search of possible combinations. A prime example is the distributed.net network.
- BLAST searches in bioinformatics .
- Large-scale face recognition systems that compare thousands of input images (for example, face images from security systems or video surveillance systems) with a large number of stored images of certain individuals (for example, portraits of criminals).
- Computer simulations comparing many independent scenarios such as climate models.
- Genetic algorithms and other heuristic algorithms .
- Statistical ensemble with numerical weather forecast .
- Modeling and reconstruction of events in elementary particle physics .
- The stage of collecting relations in the variation of multiple polynomials of the quadratic sieve method is an algorithm in factorization of integers (MPQS).
- When generating Bitcoin, hashing for the same block, but with different overhead information in the header, can be performed in parallel.
Implementations
- In the R programming language, the Snow package (Simple Network of Workstations) implements a simple mechanism for using a collection of workstations or a Beowulf cluster for extremely parallel computing.
See also
- Amdahl's Law
- Mapreduce
Notes
Links
- Embarrassingly parallel , parallel algorithms
- Embarrassingly Parallel Computations , Engineering a Beowulf-style Compute Cluster
- Star-P: High Productivity Parallel Computing