MetaSimGrid : Towards realistic scheduling simulation of distributed applications

Most scheduling problems are already hard on homogeneous platforms, they become quite intractable in an heterogeneous framework such as a metacomputing grid. In the best cases, a guaranteed heuristic can be found, but most of the time, it is not possible. Real experiments or simulations are often involved to test or to compare heuristics. However, on a distributed heterogeneous platform, such experiments are technically difficult to drive, because of the genuine instability of the platform. It is almost impossible to guarantee that a platform which is not dedicated to the experiment, will remain exactly the same between two tests, thereby forbidding any meaningful comparison. Simulations are then used to replace real experiments, so as to ensure the reproducibility of measured data. A key issue is the possibility to run the simulations against a realistic environment. The main idea of trace-based simulation is to record the platform parameters today, and to simulate the algorithms tomorrow, against the recorded data: even though it is not the current load of the platform, it is realistic, because it represents a fair summary of what happened previously. A good example of a trace-based simulation tool is \textscSimGrid, a toolkit providing a set of core abstractions and functionalities that can be used to easily build simulators for specific application domains and/or computing environment topologies. Nevertheless, \textscSimGrid lacks a number of convenient features to craft simulations of a distributed application where scheduling decisions are not taken by a single process. Furthermore, modeling a complex platform by hand is fastidious for a few hosts and is almost impossible for a real grid. This report is a survey on simulation for scheduling evaluation purposes and present \textscMetaSimGrid, a simulator built on top of \textscSimGrid.Alors que la plupart des problèmes d’ordonnancement sont déjà difficiles sur une plateforme de calcul homogène, ils deviennent carrément insolubles dans un cadre hétérogène tel qu'une grille de metacomputing. Dans le meilleur des cas, on peut arriver à trouver une heuristique garantie, mais la plupart du temps ce n'est même pas possible. on a donc souvent recours à des expériences grandeur nature ou à des simulations pour pouvoir comparer deux heuristiques. Cependant, dans le cas d'une plateforme de calcul hétérogène et distribuée, de telles expériences sont très délicates à mener en raison de l'instabilité latente de telles plateformes. Il est en effet impossible de garantir l'état qu'une plateforme de calcul qui n'est pas entièrement dédiée à l’expérimentation, va rester le même entre deux expériences, ce qui empêche donc toute comparaisons rigoureuses;On utilise donc des simulations afin d 'assurer la reproductibilité des expériences. Une des difficultés majeures est d'arriver à simuler un environnement réaliste. une approche efficace consiste à effectuer des simulations utilisant des traces, c'est -à-dire utilisant des enregistrements de différents paramètres de la plateforme pour obtenir un comportement réaliste. SIMGRID est un bon exemple d'outil de simulation utilisant des traces. Cette bibliothèque fournit un ensemble de fonctions et d'abstractions de bas niveaux permettant de construire facilement un simulateur pour un domaine particulier d’applications et/ou des topologies particulières de plateformes de calcul. Néanmoins, SIMGRID souffre d'un certain nombre de lacunes, notamment en ce qui concerne la simulation d'une application distribuée où les décisions ordonnancement ne sont pas prises par une seule entité. De plus, si la modélisation d'une plateforme réaliste est déjà fastidieuse pour quelques machines, elle s'avère impossible quand le nombre de processeurs devient important. Ce rapport présente donc une étude sur la simulation ayant pour objectif l'évaluation d'heuristiques d’ordonnancement et présente METASIMGRID, un simulateur construit au dessus de SIMGRI