``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