Ordonnancement et réplication de données bioinformatiques dans un contexte de grille de calcul
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
In this thesis, we focus on the specific context of a set of bioinformatic applications. Those applications have the particularity to use wellknown read-only databanks and a computation cost linear with the size of data. The other point is that the use of application and data is always the same. Within this context, we have developped an algorithm (Scheduling and Replication Algorithm, SRA) that combines data management and scheduling using steady-state approach. Using a model of the platform, the number of requests as well as their distribution, the number and size of databanks, we define a linear program to satisfy ball the constraints at every level of the platform in steady-state. The solution of this linear program will give us a placement for the databanks on the servers as well as providing, for each kind of job, the server on which they should be executed. With the OptorSim grid simulator, that we have merely improved, we have show good result when storage space or network bandwidth between grid nodes are critical resources. Then, we have design a set of heuristics that aims to adapt the scheduling and data placement when data use changes. These heuristics have also been tested with our version of OptorSim. The conclusion of these simulations is that, in most cases, our algorithm is able to keep an almost optimal use of computation resources even if usage scheme used for initial data placement are very different of the request that are really submitted. Finally, we have implemented a prototype of our static solution inside the DIET grid middleware. This prototype has been deployed on the Grid'5000 platform. The run of experiments in these real conditions has validated results of our simulations.
Abstract FR:
Au cours de cette thèse, nous nous sommes placés dans le contexte bien > particulier d'une catégorie d'applications bioinformatiques dont les > caractéristiques sont d'utiliser des banques de données de références en > lecture seule et d'avoir un coût en temps de calcul affine en la taille des > données. Une autre caractéristique concernant l'utilisation de ces > applications est que leur schéma d'utilisation reste constant dans le > temps. Dans ce cadre, nous avons défini un algorithme basé sur un programme > linéaire permettant de calculer un ordonnancement et un placement statique > des données optimisant le rendement d'une plate-forme de type grille de > calcul. Grâce au simulateur Optorsim que nous avons largement modifié, nous > avons montré les bons résultats de notre algorithme lorsque l'espace de > stockage sur les noeuds de calcul ou le débit du réseau connectant les > différents sites sont des points critiques. > Nous avons ensuite établi un ensemble d'heuristiques dont le but est de > palier à d'éventuels changements dans les schémas d'utilisation des banques > de données. Là encore, nous avons utilisé Optorsim pour montrer et > comprendre l'impact de ces différentes heuristiques. Il en découle que dans > la plupart des cas, nous sommes en mesure de conserver une utilisation > presque optimale de la plate-forme, même lorsque les requêtes qui arrivent > sont très différentes du schéma d'utilisation utilisé pour le placement > initial. Enfin, nous avons réalisé un prototype du système basé sur > l'ordonnancement et le placement statique au sein de l'intergiciel de > grille DIET. Ce prototype, déployé sur un ensemble de noeuds de la > plate-forme Grid 5000, nous a permis de montrer l'efficacité de notre > méthode dans un environnement réel.