Nouvelles approches pour lordonnancement dapplications parallèles sous contraintes de déploiement denvironnements sur grappe.Report as inadecuate




Nouvelles approches pour lordonnancement dapplications parallèles sous contraintes de déploiement denvironnements sur grappe. - Download this document for free, or read online. Document in PDF available to download.

1 LIG Laboratoire d-Informatique de Grenoble - ADELE LIG - Laboratoire d-Informatique de Grenoble

Abstract : This thesis considers the \textit{Clusters} in Grid-5000 French Project for the grids. Grid-5000 is an experimental platform which makes possible for researchers to submit their programs associating them with an excution environment. Usually, the deployment process on nodes has some problems. One of them is the failure of the machines because the excessive boot of the deployment phases can cause their endomagement. Thus, we consider the bicriteria scheduling problem to solve the scheduling problem with deployment on cluster. The first criteria to minimize is the number of deployments of all machines. The second one is to minimize the makespan. We define an algorithm -Groups List Scheduling- denoted by GLS, based on a bujet approach with relaxation of the optimality constraints. Using this approach, we define a alpha, beta-budget-relaxed-approximate solution for the bicriteria optimisation problem. When we consider the bicriteria scheduling problem with deployment, the GLS algorithm gives a 4,2-budget-relaxe-approximate solution. We have defined a polynomial algorithm that allows the construction of a 4+epsilon,2-approximate Pareto curve from the results obtained by the GLS algoritm. In the next step we consider the bicriteria scheduling problem with deployment, using the Pareto curve approach. We define a plynomial algorithm which builds, from GLS algorithm, a 4+epsilon,2-approximate Pareto curve solutions. An experimental analysis gives the performance of the GLS algorithm and allows us to validate the approximation ratios.

Résumé : Cette thèse s-inscrit dans le cadre des grappes dans le projet Grid-5000 Projet Français pour les grilles. Grid-5000 est une plate-forme expérimentale qui offre la possibilité aux chercheurs de soumettre aux gestionnaires de ressource des programmes travaux et d-associer pour chaque requête un environnement. Une grappe est un ensemble de noeuds de calcul, connectés entre eux via un réseau dédié. Le processus de déploiement d-environnement sur les noeuds de calcul n-est pas sans conséquence. Un des problèmes que l-on rencontre est la défaillance des machines. Le démarrage excessif lors de de la phase déploiement peut causer un endomagement de celles-ci. Nous avons ainsi modélisé ce problème sous forme d-un problème d-ordonnancement bicritère. Le premier critère à minimiser comptabilise pour chaque machine processeur le nombre de déploiements effectués. Il permet ainsi permet de définir le nombre total de déploiements sur toutes les machines. Nous avons également considéré un second critère à minimiser, le makespan. Nous avons défini un algorithme Groups List Scheduling, basé sur une approche budget, avec un relâchement des contraintes d-optimalité. Cette approche nous a permis de définir une solution alpha, beta-budget-relaxée-approchée pour un problème d-optimisation bicritère. Dans le cadre du problème d-ordonnancement bicritère avec déploiement, l-algorithme GLS donne ainsi une solution 4,2-budget-approchée-relaxée. Nous avons ensuite abordé ce problème d-ordonnancement bicritère avec déploiement en utilisant l-approche «courbe de Pareto». Nous avons défini un algorithme polynômial, qui permet de construire une courbe de Pareto 4+epsilon, 2-approchée, à partir des solutions fournies par l-algorithme GLS. Une analyse expérimentale nous a permis d-évaluer les performances de l-algorithme GLS et de valider ainsi les rapports

Mots-clés : Ordonnancement optimisation multicritère déploiement Grid-5000?????





Author: Feryal-Kamila Moulaï -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents