Efficient, non obstructive scheduling on computing grids using virtual execution environments - PASTEL - Thèses en ligne de ParisTech Access content directly
Theses Year : 2010

Efficient, non obstructive scheduling on computing grids using virtual execution environments

Allocation efficace et non contraignante des ressources de grilles de calcul à l'aide d'environnements virtuels

Abstract

In the last decade, computing grids have brought together storage and servers located across multiple institutions to support large-scale scientific applications. By analogy with power grids, the original idea is to provide with seamless computing power anyone who plugs in. However, as applications increase in demand and multiply, the efficiency of the underlying resource allocation mechanisms deserves attention. This thesis presents the following contributions. - We identify resource allocation patterns in grids and we compare them to resource allocation patterns on single clusters. - We identify a common pattern (Late Binding) in the way that several applications have recently bypassed the mainstream grid mechanism (Metascheduling) in order to take more control for better perceived performance. - We propose a new pattern (Symmetric Mapping) that achieves separation of control between multiple participants in resource allocation. - We propose a new formal model to specify resource allocation strategies. This model allows to represent dynamic scheduling under multiple constraints and objectives. - We transpose the problem of Multiple Administrative Domains (MADs) from the area of fault tolerance to the area of distributed computing; we identify it as distinctive of grids among other computing systems; and we identify Symmetric Mapping as a solution. - We propose an implementation of Symmetric Mapping based on virtual machines. As part of the implementation, we propose a system that deploys and manages multiple virtual machines based on declarative descriptions. - We propose a system that detects service termination and resumes discontinued services on newly elected servers, in order to maintain an implementation of Symmetric Mapping, or any system that requires permanent services on transient servers. - We propose a new method to analyze tasks and predict cache performance on various servers, in order to dynamically match tasks to adequate heterogeneous computing resources such as obtained on a grid. The method relies on fitting memory access patterns with well known probability distributions. The task signature is reduced to constant size and prediction is reduced to constant time. - We propose the first evaluation of cache thrashing, in order to make realistic performance predictions for time-shared CPUs. The analysis is based on a new Markov model of LRU caches. It yields a lower and a higher bound of the cache miss ratio in presence of competing processes.
Dans la dernière décennie, les grilles de calcul ont permis de réunir des ressources de stockage et de calcul de multiples institutions pour pourvoir à des applications scientifiques de grande ampleur. Par analogie aux grilles électriques, l'idée d'origine est de fournir de manière transparente de la capacité de calcul selon les besoins. Cependant, alors que les applications se multiplient, l'efficacité des mécanismes sous-jacents d'allocation de ressources mérite l'attention. Cette thèse présente les contributions suivantes. - Identification des patterns d'allocation de ressource, et comment ils ont évolué depuis les clusters isolés jusqu'aux grilles qui s'étendent sur plusieurs institutions autonomes. - Identification d'un pattern commun (Late Binding) dans la façon dont plusieurs applications contournent depuis peu le méccanisme habituel (Meta-scheduling) dans le but d'obtenir une mainmise accrue sur l'allocation de ressources et de palier à certains manques d'efficacité. - Proposition d'un nouveau pattern (Symmetric Mapping) qui permet d'obtenir la séparation du contrôle entre les fournisseurs et utilisateurs de ressources. - Proposition d'un nouveau modèle pour spécifier des stratégies d'allocation de ressource. Ce modèle permet de représenter l'allocation dynamique, ainsi que de multiples contraintes et objectifs. - Transposition du problème des Domaines Administratifs Multiples (MADs) du domaine de la tolérance aux fautes à celui du calcul distribué. Identification du problème MAD comme problème distinctif des grilles parmi les systèmes de calcul distribué. Identification de Symmetric Mapping comme une solution. - Proposition d'une implémentation de Symmetric Mapping basée sur les machines virtuelles, et dont l'un des éléments déploie et contrôle des multiples machines virtuelles à partir de descriptions déclaratives. - Proposition d'un système qui détecte la terminaison d'un service et relance tout service interrompu sur un serveur nouvellement sélectionné, afin de maintenir une implémentation de Symmetric Mapping, ou tout système qui nécessite des services permanents sur des serveurs transitoires. - Proposition d'une nouvelle méthode pour l'analyse des tâches et la prédiction de performance afin d'associer de manière dynamique des tâches aux serveurs adéquats. La méthode s'appuie sur l'estimation de patterns d'accès mémoire par des distributions de probabilité connues. La signature des tâches est réduite à une taille constante et la prédiction est effectuée en temps constant. - Proposition de la première évaluation du cache thrashing, afin de permettre des prédictions de performance réalistes pour les CPUs partagés par plusieurs processus. L'analyse est basée sur un nouveau modèle de Markov des caches LRU. Elle donne une borne supérieure et une borne inférieure de la proportion de fautes de caches en présence de processus concurrents.
Fichier principal
Vignette du fichier
these_Grehant.pdf (10.86 Mo) Télécharger le fichier
Loading...

Dates and versions

pastel-00569373 , version 1 (24-02-2011)

Identifiers

  • HAL Id : pastel-00569373 , version 1

Cite

Grehant Xavier. Efficient, non obstructive scheduling on computing grids using virtual execution environments. Performance [cs.PF]. Télécom ParisTech, 2010. English. ⟨NNT : ⟩. ⟨pastel-00569373⟩
213 View
796 Download

Share

Gmail Facebook Twitter LinkedIn More