Embarrassingly parallel problems
Embarrassingly parallel problems are problems that can be almost trivially divided into independent tasks that can be solved in parallel. In such problems, no or very little synchronization is required between the tasks. Due to negative connotations of “embarrassment”, such problems are also called “pleasingly parallel” or “perfectly parallel”.
Below we give some examples of embarrassingly parallel problems and show how simple parallelization, obtained by applying parallel for-loops, can bring decent speedups in standard multicore desktop machines. However, we also show that improving the algorithms and/or taking the underlying hardware architecture better into account can bring even further speed-ups compared to the naive approach.