The computational problem should be able to:
Be broken apart into discrete pieces of work that can be solved simultaneously;
Execute multiple program instructions at any moment in time;
Be solved in less time with multiple compute resources than with a single compute resource.
The compute resources are typically:
A single computer with multiple processors/cores
An arbitrary number of such computers connected by a network