Using Simulation to Evaluate Scheduling Heuristics for a Class of Applications in Grid Environments
Résumé
Fast networks have made it possible to aggregate distributed CPU, memory, and storage resources into Grids that can deliver considerable performance. However, achieving performance on such systems requires good performance prediction which is usually difficult due to their dynamic and heterogeneous nature. This is especially true for parallel applications whose performance is highly dependent upon the efficient coordination of their constituent components (e.g. computation and data). The goal of the AppLeS project is to develop application-level scheduling agents that provide mechanisms for automatically scheduling individual applications on production heterogeneous systems. AppLeS agents utilize the Network Weather Service (NWS) to monitor and forecast the varying performance of resources potentially usable by their applications. Each AppLeS uses static and dynamic application and system information to select viable resource configurations and evaluate their potential performance. The AppLeS then interacts with the appropriate resource management system to implement the application's network transfers and computational tasks. The next generation of AppLeS agents aims at providing templates that can be used for scheduling classes of structurally similar applications. In this document we introduce a template for scheduling Parameter Sweep applications (application consisting of {\em large} number of independent tasks, with possible input data sharing). We have designed a general scheduling algorithm that can adapt to Grid environments and use a variety of strategies and heuristics to assign tasks and data to resources. In order to evaluate and compare those heuristics we have built a simulator as part of the template. The simulator makes it possible to rapidly conduct large numbers of experiments in a variety of environments. Our starting point was to use widely accepted heuristics that have been proposed in the litterature and venture improvements given our Grid and application model. This document presents the implementation of our simulator and explains how it will be used to obtain new research results in the field of Grid scheduling.
Les réseaux haut débit ont permis de connecter des capacités de calcul et de stockage distribuées en des grilles susceptibles de fournir des puissances de calcul considérables. Cependant, l'utilisation efficace de tels systèmes recquiert de bonnes prédictions des performances des différentes ressources, ce qui est généralement difficile en raison de l'hétérogénéité et du caractère dynamique de ces environnements. Ce constat est tout particulièrement vrai dans le cas d'applications parallèles dont l'efficacité dépend de la bonne coordination de ses différents composants. L'objectif du projet AppLeS est de développer des agents chargés de l'ordonnancement dans des environnement de calculs distribués hétérogènes et spécialisés pour chaque application. Les agents AppLeS utilisent le Network Weather Service (NWS) pour contrôler et prédire les performances des ressources disponibles pour les applications cibles ainsi que leur variations. Chaque agent utilise des informations statiques et dynamiques sur les applications dont il est responsable et sur l'environnement auquel il a accès pour effectuer ses choix. Il peut alors utiliser les systèmes chargés de la gestion de l'environnement pour l'alllocation des fichiers et des calculs aux différentes ressources. La prochaine génération d'agents AppLeS devrait être des modèles, des agents ``types'', dédiés à des classes d'applications structurellement équivalentes. Dans ce document, nous introduisons un modèle d'agent dédié à l'ordonnancement des applications de type Parameter-Sweep (des applications constituées d'un grand nombre de tâches de calcul indépendantes pouvant partager des fichiers d'entrée). Nous avons conçu un algorithme d'ordonnancement général capable de tenir compte des modifications de structure ou de performances de l'environnement et d'utiliser un certain nombre d'heuristiques pour l'allocation des données et des calculs aux différentes ressources. Nous avons développé un simulateur avec lequel l'agent peut interagir pour pouvoir évaluer et comparer ces heuristiques. Ce simulateur nous a permit de réaliser rapidement un grand nombre d'expériences dans un environnement paramétrable à volonté. Notre point de départ à été l'utilisation d'heuristiques tirées de la littérature et de les adapter à notre type d'application. Ce document présente la mise en oeuvre du simulateur et explique comment il va être utilisé pour obtenir de nouveaux résultats concernant l'ordonnancement dans des environnements instables de type grille.
Origine : Fichiers produits par l'(les) auteur(s)