Problems Embarrassingly Parallel?

Question

I was looking for problems called "embarrassingly parallel", which are problems that there are no dependencies between tasks, which can be divided in parallel.

Could you give me some suggestion of some algorithm?

Answer 1

Image rendering

An algorithm of this kind is the rendering of three-dimensional scenes, in which each pixel is rendered completely without relying on any other pixel rendering.

That’s why today’s Gpus increasingly expand the number of processors called shaders, which are responsible for calculating the final color of each pixel, independently of each other.

An important mention in this set is the Perlin noise (Perlin Noise), which is used to generate pseudo-random noise.

Physical simulations with particles

Another example is physical simulations, in which each particle has its characteristics changed taking into account the previous state of the simulation. That is, at each step, the particles do not interact with each other, but with the particles of the previous stage.

Also because of this, many games use the GPU to make physical simulations with a much larger number of particles, obviously the GPU has to support this.

Problems that don’t completely parallelize

Problems in the "Divide to Conquer" category are not so parallelizable for small trees. But as the information set grows, the solution becomes more and more parallelizable.

Examples:

• add all the numbers of a giant list... you can subdivide the problem by dividing the giant list into smaller lists and delegate the partial solution to different processors.

• search all the alternatives in a chess game (you will have to define the maximum depth of the search, because it is impossible to calculate all... the number of alternatives is absurdly large)

Answer 2

Some classic problems of relatively simple and good parallelizing algorithms are:

Calculation of Pi using the Monte Carlo Method

Consider the following image with a square and a circle whose diameter is the same as the square side.

Now imagine that the circle is a target. You will throw darts randomly inside the square.

Now consider the formula below:

This means that if you take the amount of darts you hit inside the circle, divide by the amount you hit outside the circle and multiply by four, you get an approximate pi value.

The theory says that the approach improves according to the number of darts thrown. Thus, a parallel program can "throw darts" randomly into the square and account for the amount of darts inside and outside the circle. At the end, just add the results and apply in the formula.

Integral approach by trapezoidal rule

You want the approximate value of the integral of a function f(x) in the intervening period of a to b.

A very simple (and inaccurate) way to solve this is to calculate the integral of a linear function that passes through the points f(a) and f(b).

Take the example:

In blue you have the real function and in red the linear function used to calculate the approximation.

Well, a linear function will result in a bad approximation. However, we increase the number of points of the approximation function, the result will be more accurate, right? The more points we calculate, the better.

So we can use a parallel program and split the interval [a, b] by the number of threads or processes and each calculates the partial full of that part.

In the end, just add up the results.