Embarrassingly Parallel Algorithms

• Sometimes called naturally parallel algorithms.
• Simplest type of parallel algorithms requiring almost no communication between the processes.
• Each process can perform their own computations without any need for communication with the others.
• They may require some initial partition of the data or collecting the results in the end, but not always.

Pseudo Random Numbers

Technique 1. One process can generate the pseudo-random numbers and send to other processes that need the random numbers. This is sequential.

Technique 2. Use a separate pseudo-random number generator on each process. Each process must use a different seed. This is embarrassingly parallel. The choice of seeds used at each process is important. Simply using the process id or time of the day can yield to bad distributions. One can use the /dev/random device driver in Linux to get good seeds.

Technique 3. Convert the linear generator such that each process only produces its share of random numbers. It is easier to control but requires more communication.

An Example
y₀ = s;
y_i+1 = a y_i + c
We can convert it to a dependency on a number several positions back.
y_i+k = a^k+1 y_i + (a^k + ... + a² + a + 1) c