Equilibrage de charge et redistribution de données sur plates-formes hétérogènes

In this thesis, we study iterative algorithms onto heterogeneous platforms. These iterative algorithms operate on large data samples (recursive convolution, image processing algorithms, etc.). At each iteration, independent calculations are carried out in parallel, and some communications take place. Note that there is no reason a priori to restrict to a uni-dimensional partitioning of the data, and to map it onto a uni-dimensional ring of processors. But uni-dimensional partitionings are very natural for most applications, and, as will be shown in this thesis, the problem to find the optimal one is already very difficult.After dealing with the problems of mapping and load-balancing onto heterogeneous platforms, we consider the problem of redistributing data onto these platforms, an operation induced by possible variations in the resource performances (CPU speed, communication bandwidth) or in the system/application requirements (completed tasks, new tasks, migrated tasks, etc.).For homogeneous rings the problem has been completely solved. Indeed, we have designed optimal algorithms, and provided formal proofs of correctness, both for unidirectional and bidirectional rings. For heterogeneous rings there remains further research to be conducted. The unidirectional case was easily solved, but the bidirectional case remains open. Still, we have derived an optimal solution for light redistributions, an important case in practice.Dans cette thèse, nous nous sommes intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données (calcul de matrices, traitement d'images, etc.), qui sera réparti sur l'ensemble des processeurs. À chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et nous montrerons que trouver l'optimal est déjà très difficile. Après cette étude sur le placement et l'équilibrage de charge pour plates-formes hétérogènes, nous nous sommes intéressée à la redistribution de données sur ces mêmes plates-formes, lorsque que les caractéristiques de ces dernières changent. En ce qui concerne les anneaux de processeurs homogènes, nous avons totalement résolu le problème : nous avons obtenu des algorithmes optimaux et prouvé leur exactitude dans le cas homogène et dans le cas hétérogène. En ce qui concerne les anneaux hétérogènes, le cas unidirectionnel a été totalement résolu, alors que le cas bidirectionnel reste ouvert. Cependant, sous l'hypothèse de redistribution légère, nous sommes capable de résoudre le problème de manière optimale