Scheduling reductions

X Redon, P Feautrier - Proceedings of the 8th international conference …, 1994 - dl.acm.org
X Redon, P Feautrier
Proceedings of the 8th international conference on Supercomputing, 1994dl.acm.org
In order to detect more parallelism in scientific programs, one may extract a parallelism
relative to reductions. This paper presents such a method which schedules programs with
explicit computations of reductions. We describe the way the reductions are expressed in
our input language (which is in fact the output language of the reductions detector presented
in [RF93]). We also give a brief summary of scheduling techniques. In order to simplify the
scheduling we suppose that the target parallel computer has an infinite number of …
In order to detect more parallelism in scientific programs, one may extract a parallelism relative to reductions. This paper presents such a method which schedules programs with explicit computations of reductions. We describe the way the reductions are expressed in our input language (which is in fact the output language of the reductions detector presented in [RF93]). We also give a brief summary of scheduling techniques. In order to simplify the scheduling we suppose that the target parallel computer has an infinite number of processors with infinite fan-in. We show that a schedule computed with this model can be adapted to work on real parallel machines. Then we present a scheduling method based on the algorithms from [Fea92a, Fea92b] which works in presence of reductions. This method is applied on an example. Lastly, we show that side-effects of reductions scheduling are the simplification of the scheduling process and the improvement of the computed schedules.
ACM Digital Library