Automatic Parallelization Based on Multi-Dimensional Scheduling
Alain Darte, Frédéric Vivien, Centre National de la Recherche Scientifique (CNRS), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme, Lyon-1 Univ., 69 (France). Lab. de l'Informatique du Parallelisme, Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme · 1994
In the scope of uniform recurrence equations, we study an algorithm first proposed by Karp, Miller and Winograd for detecting cycles of null weight in cyclic graphs. We show how this algorithm can be used for generating multi-dimensional schedules that express all the potential parallelism contained in a computable system of uniform recurrence equations. We then apply this technique to imperative programs based on loop nests and whose dependences are described in the framework (Z; +; \\Gamma; ), the most popular way of describing dependences. We are able to show that our technique is an optimal parallelization technique in the sense that no more parallelism can be detected than provided by our new algorithm.