  Researchers working on the automatic parallelization of programs have long
known that too much parallelism can be even worse for performance than too
little, because spawning a task to be run on another CPU incurs overheads.
Autoparallelizing compilers have therefore long tried to use granularity
analysis to ensure that they only spawn off computations whose cost will
probably exceed the spawn-off cost by a comfortable margin. However, this is
not enough to yield good results, because data dependencies may \emph{also}
limit the usefulness of running computations in parallel. If one computation
blocks almost immediately and can resume only after another has completed its
work, then the cost of parallelization again exceeds the benefit.
  We present a set of algorithms for recognizing places in a program where it
is worthwhile to execute two or more computations in parallel that pay
attention to the second of these issues as well as the first. Our system uses
profiling information to compute the times at which a procedure call consumes
the values of its input arguments and the times at which it produces the values
of its output arguments. Given two calls that may be executed in parallel, our
system uses the times of production and consumption of the variables they share
to determine how much their executions would overlap if they were run in
parallel, and therefore whether executing them in parallel is a good idea or
not.
  We have implemented this technique for Mercury in the form of a tool that
uses profiling data to generate recommendations about what to parallelize, for
the Mercury compiler to apply on the next compilation of the program. We
present preliminary results that show that this technique can yield useful
parallelization speedups, while requiring nothing more from the programmer than
representative input data for the profiling run.
