Computer Science – Programming Languages
Scientific paper
2011-09-07
Theory and Practice of Logic Programming, 27th Int'l. Conference on Logic Programming (ICLP'11) Special Issue, volume 11, issu
Computer Science
Programming Languages
Scientific paper
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.
Bone Paul
Schachte Peter
Somogyi Zoltan
No associations
LandOfFree
Estimating the overlap between dependent computations for automatic parallelization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Estimating the overlap between dependent computations for automatic parallelization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating the overlap between dependent computations for automatic parallelization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-306148