Tiling for Heterogeneous Computing Platforms.

In the framework of fully permutable loops, tiling has been extensively studied as a source-to-source program transformation. However, little work has been devoted to the mapping and scheduling of the tiles on physical processors. Moreover, targeting heterogeneous computing platforms has, to the best of our knowledge, never been considered. In this paper we extend tiling techniques to the context of limited computational resources with different-speed processors. In particular, we present efficient scheduling and mapping strategies that are asymptotically optimal. The practical usefulness of these strategies is fully demonstrated by MPI experiments on a heterogeneous network of workstations.Dans le cadre des boucles totalement permutables, le partitionnement a été intensivement étudié en tant que transformation de programme. Cependant, très peu de travaux ont concerné l'ordonnancement et l'allocation des tuiles sur les processeurs physiques, et aucun, à notre connaissance, n'a considéré un ensemble de processeurs hétérogène. Dans ce rapport, nous étendons les techniques de partitionnement au cadre des ressources bornées et des processeurs de vitesses diffé rentes. En particulier, nous présentons des stratégies d'ordonnancement et d'allocation asymptotiquement optimales. Nous démontrons l'intérêt pratique de ces stratégies par des expérimentations avec MPI sur un réseau hétérogène de stations de travail