Embarrassingly Parallel

What is Embarrassingly Parallel?

A computing task is said to be embarrassingly parallel when it can be naturally and easily divided into several different processing tasks that are performed in parallel with little or no dependency or communication.

Understanding Embarrassingly Parallel

In parallel computing, where multiple tasks are run at the same time, there may be some problems or workloads that are embarrassingly parallel.

Ideally, the term ‘embarrassingly’ in the etymology has nothing to do with any kind of embarrassment.

It, in fact, refers to ‘overabundance’ of the parallelization problems, which are, however, ‘embarrassingly easy.’

Typically, in parallel computing, an embarrassingly parallel problem or workload refers to the one that can be separated into a number of parallel tasks with very little or no effort.

This is the case often when there is very little or no need for or dependency on any sort of communication between the parallel tasks as well as the results obtained from them.

Embarrassingly parallel is also known by different other terms and phrases such as:

Embarrassingly parallelizable
Delightfully parallel
Perfectly parallel or
Pleasingly parallel.

Ideally, it refers to a different form of distributed computing problems since they do not need any communications between the different tasks or even with the intermediate results.

3D image processing, such as ray tracing and ray casting of images, is the most common example of an embarrassingly parallel computing task.

In this case, there are different sections of one single image that are computed separately without needing any interaction with the others involved.

A proper breakdown of the process will make things very clear to you.

The image is broken down into different sections or chunks
Each section is allocated to independent processors such as the Compute Unified Device Architecture or CUDA cores on an Nvidia graphics card for parallel processing
Each of these CUDA cores processes the specific section assigned to it separately but at the same time while others are worked on by the other cores, which greatly speeds up the process and
When the processing is complete, all of the chunks are joined together to create the final image that is to be rendered by the Graphics Processing Unit.

These tasks are very easy to perform, especially on a server farm that does not have the special infrastructure used in a real supercomputer cluster.

Embarrassingly Parallel Algorithms

Embarrassingly parallel algorithms, irrespective of the nomenclature, can be either sequential algorithm or parallel algorithm in nature.

It is for this reason that they are so useful for large, distributed platforms based on the internet and are not subject to the customary parallel slowdown effects.

Embarrassingly parallel algorithms, also known as naturally parallel algorithms, have the following features:

They are probably the simplest of all types
They need almost no communication among the processes
Respective computations can be carried out by each process and
It sometimes needs some initial data partitioning or collecting the end results.

In an ideal case scenario, in these algorithms the calculation of the tasks or sub-solutions is totally independent due to specific reasons such as:

All are defined before the beginning of the computation and
All are stored in separate memory locations.

These computations become almost embarrassingly parallel if they need some initial or final communication.

On the other hand, in a hybrid or a variable scenario, these solutions or tasks are collected in a shared data structure and also need some coordination in the end.

However, in a non-obvious termination condition, it may need some intermediate coordination while something is found.

Keeping track of the pool of tasks needs some additional overhead because all sub-problems are not known at the beginning.

The algorithms of Monte Carlo simulations are a bit different. They approximate a function by means of random selections in computations.

And, in the case of the pseudorandom numbers, there are different techniques that are followed according to the set of rules such as:

Sequential – Here, one process generates the pseudorandom numbers and sends them to the other processes that require them and
Embarrassingly parallel – Here, a separate pseudo random number generator is used for each process that uses a different seed.

There is also another specific technique followed in which the linear generator is converted so that each process produces only its share of random numbers. This makes controlling them much easier, but it needs more communication.

Embarrassingly Parallel Examples

One of the most common examples of embarrassingly parallel computing is 3D video or image rendering. It is done by the Graphics Processing Unit with no interdependency and by two methods, namely the forward method and the ray tracing method.

Another good example is a few types of password cracking that are distributed easily among the CPU cores or clusters.

Some other implementations and examples of embarrassingly parallel computing, both classic and otherwise, are:

In several R programming language packages and the SNOW or Simple Network of Workstations package which uses a cluster of workstations using a simple mechanism for embarrassingly parallel computations
In genetic programming, where algorithms are created as a set by mutating and combining earlier generations
In the Mandelbrot set, which is a fractal where individual points are computed separately
In Monte Carlo algorithms and simulations wherein a large amount of diverse computational tasks are executed by sampling separate elements in a pseudorandom manner
In Discrete Fourier Transform or DFT, which deals with samples of a signal or a function that are evenly spaced and used commonly in DSP or Digital Signal Processors
In facial recognition systems to compare a large number of images of faces that are arbitrarily acquired through CCTV surveillance and other means with an equally large number of images of faces stored in a watch list
For bulk processing of unrelated files but are of the same nature in general such as conversion and resizing of photo gallery and
In brute-force cryptographic problems which deal with several similar computations such as POW or Proof of Work algorithms.

Some classic examples of embarrassingly parallel computing are:

In protein folding software
In Search for Extra Terrestrial Intelligence or SETI projects
In computation pseudorandom numbers of all subsets of different generations
In distributed relational database queries
In numerical integration
For providing static files on a web server to several users at the same time
In computer animation
For BLAST searches in split databases in bioinformatics
For comparing different computer simulations involving separate scenarios
For genetic algorithms
For numerical weather forecasts and ensemble calculations
For reconstructing and simulation of events in particle physics
In marching squares algorithm
In quadratic and number field sieving
In random forest machine learning involving growth of trees
In Graphics Processing Units or GPUs running on convolutional neural networks
In machine learning for hyperparameter grid search and
In constraint programming.

Embarrassingly Parallel vs Parallel

Embarrassingly parallel computing takes relatively less time than simple parallel computing
Parallel computing is more beneficial when repetitive processes needs longer time to execute as opposed to embarrassingly parallel computing which is pretty quick and
In embarrassingly parallel computing a task is divided among multiple cores, while in parallel computing a task can be completed within a single core with multiple threads.

Conclusion

Embarrassingly parallel computing is very important to expedite the process of computing different problems.

Now, after reading this article, you know that it is the process by which a specific task is easily and naturally divided and assigned to different cores for processing and has nothing ‘embarrassing’ in it as such.