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