Embarrassingly Parallel

``Embarassingly Parallel'' means that it is easy to get arbitrarily large SpeedUp by suitable ParTition strategy or by making the problem sufficiently large.

Now, if your goal is achieving high performance and large SpeedUp, you -want- your problem to be embarrassingly parallel. If it is not embarassingly parallel, you would be well-advised to put some effort into transforming it into a related problem that is embarrassingly parallel, or approximating the original difficult problem by an embarrassingly parallel surrogate. Or perhaps you can subdivide the original problem into an embarrassingly parallel common case and a difficult (read ``slow'') less-common fallback.

This latter approach often allows ParTition to be used to good effect.

See also MassivelyParallel ParalleliZation