Ordonnancement en régime permanent sur plates-formes hétérogènes

This thesis mainly deals with the mapping and the scheduling of applications on large heteroge- neous platforms. As the general scheduling problem is untractable, we consider two relaxations which apply to specific problems. Divisible load scheduling: Divisible loads are perfectly parallel applications, which can be split into chunks of arbitrary sizes to be distributed to many workers. We focus our attention on scheduling several divisible loads with different characteristics on linear networks of processors, in order to minimize the total processing time. This distribution may be done using several installments. Given a number of installments, we expose an algorithm giving an optimal dis- tribution of loads on processors, and we compare it to a pre-existing solution. Moreover, we show that any optimal distribution uses an infinite number of installments, leading to unfeasible solutions. This results also holds true for star-shaped platforms. Steady-state scheduling: In the second part, we discuss the issue of scheduling many copies of a given application, which is represented by a complex task graph. Instead of minimizing the completion time, we concentrate on the heart of the schedule and we try to maximize the throughput of the whole platform, without considering the start nor the end of our schedules. In this part, we first study the scheduling of complex but static applications, made of acyclic task graphs, on general heterogeneous platforms. To preserve a simple deployment of the application, produced schedules are made of a single allocation. Due to the NP-completeness of the problem, we not only provide an optimal solution, but also several heuristics returning efficient schedules. We compare our solutions to classical scheduling algorithms such as HEFT. In a second step, we focus on a collection of simpler but dynamic applications to schedule on fully heterogeneous master-workers platforms: the characteristics of their instances are varying. Designing static schedules taking care of this dynamicity is difficult, even in case of simple bag- of-tasks applications. Assuming that these variations are represented by random variables, we provide an ε-approximation in clairvoyant context and efficient heuristics for both the semi- clairvoyant and non-clairvoyant cases. We present many simulations to assess their qualities compared to the Round-Robin or the On-Demand policies. In a third step, we deal with pipeline applications, of which several tasks are replicated on different processors to increase the global throughput. In this case, even if instances are dis- tributed in a simple Round-Robin fashion and if the mapping is completely specified, computing the throughput of the platform is difficult. We expose a model based on Timed Petri Nets to compute them; we also prove that the throughput can be computed in polynomial time for the Strict One-Port communication model. Finally, steady-state techniques are effectively used to schedule complex task graph on a hetero- geneous multi-core processor, the IBM Cell. We present a theoretical model of this processor and an efficient algorithm to schedule many instances of complex task graphs. An complete implementation of this algorithm shows strong performances, while actual throughputs are very close to those predicted by our solution.Les travaux présentés dans cette thèse portent sur l'ordonnancement d'applications sur des plate- formes hétérogènes à grande échelle. Dans la mesure où le problème général est trop complexe pour être résolu de façon exacte, nous considérons deux relaxations. Tâches divisibles : La première partie est consacrée aux tâches divisibles, qui sont des appli- cations parfaitement parallèles et pouvant être arbitrairement subdivisées pour être réparties sur de nombreux processeurs. Nous cherchons à minimiser le temps de travail total lors de l'exécution de plusieurs applications aux caractéristiques différentes sur un réseau linéaire de processeurs, sachant que les données peuvent être distribuées en plusieurs tournées. Le nombre de ces tour- nées étant fixé, nous décrivons un algorithme optimal pour déterminer précisément ces tournées, et nous montrons que toute solution optimale requiert un nombre infini de tournées, résultat restant vrai sur des plate-formes non plus linéaires mais en étoile. Nous comparons également notre méthode à des méthodes déjà existantes. Ordonnancement en régime permanent : La seconde partie s'attache à l'ordonnancement de nombreuses copies du même graphe de tâches représentant une application donnée. Au lieu de chercher à minimiser le temps de travail total, nous optimisons uniquement le cœur de l'or- donnancement. Tout d'abord, nous étudions des ordonnancements cycliques de ces applications sur des plate-formes hétérogènes, basés sur une seule allocation pour faciliter leur utilisation. Ce problème étant NP-complet, nous donnons non seulement un algorithme optimal, mais éga- lement différentes heuristiques permettant d'obtenir rapidement des ordonnancements efficaces. Nous les comparons à ces méthodes classiques d'ordonnancement, telles que HEFT. Dans un second temps, nous étudions des applications plus simples, faites de nombreuses tâches indépendantes, que l'on veut exécuter sur une plate-forme en étoile. Les caractéristiques de ces tâches variant, nous supposons qu'elles peuvent être modélisées par des variables aléatoires. Cela nous permet de proposer une ε-approximation dans un cadre clairvoyant, alors que l'ordonnan- ceur dispose de toutes les informations nécessaires. Nous exposons également des heuristiques dans un cadre non-clairvoyant. Ces différentes méthodes montrent que malgré la dynamicité des tâches, il reste intéressant d'utiliser un ordonnancement statique et non des stratégies plus dynamiques comme On-Demand. Nous nous intéressons ensuite à des applications, dont plusieurs tâches sont répliquées sur plu- sieurs processeurs de la plate-forme de calcul afin d'améliorer le débit total. Dans ce cas, même si les différentes instances sont distribuées aux processeurs tour à tour, le calcul du débit est difficile. Modélisant le problème par des réseaux de Petri temporisés, nous montrons comment le calculer, prouvant également que ce calcul peut être fait en temps polynomial avec le modèle Strict One-Port. Enfin, le dernier chapitre est consacré à l'application de ces techniques à un processeur multi- cœur hétérogène, le Cell d'IBM. Nous présentons donc un modèle théorique de ce processeur ainsi qu'un algorithme d'ordonnancement adapté. Une implémentation réelle de cet ordonnanceur a été effectuée, permettant d'obtenir des débits intéressants tout en simplifiant l'utilisation de ce processeur et validant notre modèle théorique