Loop Partitioning versus Tiling for Cache-based Multiprocessors.

In this paper, an efficient algorithm to implement loop partitioning is introduced and evaluated. We improve recent results of Agarwal, Kranz and Natarajan in several directions. We give a more accurate estimation of the cumulative footprint, and we derive a much more powerful algorithm to determine the optimal tile shape. We illustrate the superiority of our algorithm on the same examples as those of Agarwal, Kranz and Natarajan to ensure the fairness of the comparisons.Nous présentons dans ce papier une heuristique efficace permettant de faire de la distribution de boucles. Nous appuyons notre travail sur un papier récent de Agarwal, Kranz et Natarajan que nous améliorons dans de nombreuses directions. Plus précisement, nous proposons une estimation des empreintes cumulées de tuiles plus précise ; nous proposons une heuristique puissante permettant de minimiser cette empreinte cumulée ; enfin, nous montrons la superiorité de notre algorithme en l'appliquant aux exemples donnés par Agarwal, Kranz et Natarajan, afin d'assurer l' équité de notre comparaison