Rapports de Recherche

RR-2003-12 : Static load-balancing techniques for iterative computations on heterogeneous clusters

  • This paper is devoted to static load balancing techniques for mapping iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors. At each iteration, independent calculations are carried out in parallel, and some communications take place. The question is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. We establish a complexity result that assesses the difficulty of this problem, and we design practical heuristics that provide efficient distribution schemes.

  • Ce rapport est consacré à l'équilibrage de charge pour algorithmes itératifs sur plateformes hétérogènes. Les données sont réparties sur l'ensemble des ressources. À chaque itération, les calculs indépendants sont transmis en parallèle et les communications ont lieu. Le problème est de déterminer comment partitionner les données et comment les répartir sur les ressources pour que le temps total d'exécution soit minimal. Nous avons démontré un résultat de complexité qui établit la difficulté de ce problème, et nous proposons des heuristiques pratiques qui prouvent l'efficacité de la distribution.

RR-2003-23 : Load-balancing iterative computations in heterogeneous clusters with shared communication links

  • This paper is devoted to mapping iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors, which are arranged along a virtual ring. At each iteration, independent calculations are carried out in parallel, and some communications take place between consecutive processors in the ring. The question is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. One major difficulty is to embed a processor ring into a network that typically is not fully connected, so that some communication links have to be shared by several processor pairs. We establish a complexity result that assesses the difficulty of this problem, and we design a practical heuristic that provides efficient mapping, routing, and data distribution schemes.

  • Ce rapport est consacré à l'application d'algorithmes sur plateformes hétérogènes. Les données sont réparties sur l'ensemble des ressources, qui sont organisées en anneau virtuel. À chaque itération, les calculs indépendants sont tranmis en parallèle et les communications ont lieu entre les ressources consécutives de l'anneau. Le problème est de déterminer comment partitionner les données et comment les répartir pour que le temps total d'exécution soit minimal. Une difficulté majeure est d'inclure un anneau de ressources dans un réseau n'étant pas forcément un graphe complet, de telle sorte que certains liens de communication soient partagés par plusieurs couples de ressources. Nous avons démontré un résultat de complexité qui établit la difficulté de ce problème, et nous proposons une heuristique pratique qui prouve l'efficacité de l'application, du routage et de la distribution de données.

RR-2004-28 : Data redistribution algorithms for heterogeneous processor rings

  • We consider the problem of redistributing data on homogeneous and heterogeneous ring of processors. The problem arises in several applications, each time after that a load-balancing mechanism is invoked (but we do not discuss the load-balancing mechanism itself). We provide algorithms that aim at optimizing the data redistribution, both for uni-directional and bi-directional rings, and we give complete proofs of correctness. One major contribution of the paper is that we are able to prove the optimality of the proposed algorithms in all cases except that of a bi-directional heterogeneous ring, for which the problem remains open.

  • Dans ce rapport, nous nous intéressons au problème de redistribution de données sur des anneaux de processeurs homogènes et hétérogènes. Ce problème surgit dans plusieurs applications, après chaque phase d'équilibrage de charge (nous ne discutons pas ici du mécanisme d'équilibrage de charge lui-même.). Nous proposons des algorithmes qui visent à optimiser la redistribution de données pour des anneaux unidirectionnels et bidirectionnels, et nous donnons toutes les preuves de correction de ces algorithmes. Une des contributions principales de ce rapport est que nous pouvons prouver l'optimialité des algorithmes proposés dans tous les cas, sauf dans le cas d'un anneau hétérogène bidirectionnel, pour lequel le problème reste ouvert.