Mapping pipeline skeletons onto heterogeneous platforms

Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous --nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer's task, but it also provides additional information which can help realize an efficient mapping of the application. In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms: fully homogeneous platforms with identical processors and interconnection links; communication homogeneous platforms, with identical links but different speed processors; and finally, heterogeneous platforms. We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for two different mapping policies: a mapping can be either one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages). We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on communication homogeneous platforms.L’ordonnancement d’applications sur des plates-formes parallèles est un problèmedifficile, et ce d’autant plus si ces plates-formes sont hétérogènes. Une approche de haut niveau à la programmation parallèle, à base de squelettes algorithmiques, permet tout à la fois de faciliter la tâche du développeur, et d’acquérir des informations structurelles supplémentaires sur l’application, qui permettront d’obtenir un meilleur résultat.Dans ce rapport, on discute l’ordonnancement d’applications sous forme du squelette pipeline sur différent types de plateformes: les plateformes totalement homogènes(processeurs et liens de communication identiques), les plateformes à communications homogènes mais avec des vitesses de processeurs différentes, et les plateformes totalement hétérogènes. On suppose qu’une étape de pipeline doit être placée sur un unique processeur, et on établit de nouveaux résultats de complexité pour différentes stratégies d’allocation: on peut imposer qu’au plus une étape de pipeline soit allouée à chaque processeur, ou bien allouer un intervalle d’étapes consécutives aux processeurs.Une troisième politique ne fixe aucune contrainte d’allocation.Nous donnons de nombreuses heuristiques polynomiales efficaces pour la combinaison stratégie/plate-forme la plus importante, à savoir le placement par intervalle sur plateformes à communications homogènes. Ces heuristiques sont comparées au résultat optimal obtenu par une formulation du problème sous forme de programme linéaire, pour de petites instances du problème