Je ne m'attarderai pas sur la présentation du concept de grille. Combien, celle ci est merveilleuse, puissante, complexe et un casse tête pour nos amis chercheurs. A priori, soit parce que vous avez suivi le cours de système distribué avec moi, soit parce que vous savez utiliser google, vous avez déjà une idée de ce qu'est celle ci.
Ce dont je souhaite parler en revanche, est de concept d'ordonnancement dans la grille. Le problème de l’ordonnancement n'est pas nouveau, mais loin d'avoir été résolu. La grille ajoute à ce problème NP-Complet de nouveau enjeux. Les grilles ont des architectures parfois gigantesques, non homogènes et chacun souhaite y soumettre son programme avec ses données spécifiques, ses besoins CPU particuliers, arguant que l’exécution de ce programme est d'une importance capitale. Comment contenter tout le monde dans ce contexte ?
Grâce à l'ordonnancement
Qu'est ce que l'ordonnancement :
- D'abord la recherche de ressources
- Puis la sélection de ressources et leur ordonnancement (selon des critères évoqués plus tard)
- Et enfin la soumission des tâches tel qu'il en a été décidé précédemment.
C'est le second point qui m’intéressera dans ce billet, et en particulier les différents approches d'ordonnancement.
Grid’5000 est une plate-forme expérimentale française pour la recherche sur les systèmes distribués et parallèles. Cette grille est hierarchique et répartie de la façon suivante : 7400 cœurs, 1600 nœuds de calcul, 26 clusters et 11 sites (10 en France et 1 au Luxembourg)
Il utilise un gestionnaire de ressource (batch scheduler) OAR qui gère les grappes de calcul. Il est écrit en scripts PERL articulé autour d’une base SQL. Comment sont ordonnancées les tâches par OAR ?
L'ordonnancement est recalculé à chaque changement important de l’état de la grille. Plusieurs files de tâche, chacune avec une priorité et une politique d'ordonnancement. OAR supporte différentes politiques d'ordonnancement : la fifo, fifo-with first-fit/backfilling, fairsharing et le système de réservation.
FIFO : first in first out
Assez simple à comprendre, malheureusement loin d'être optimal
First fit (back-filling) : Lorsqu'une tâche atteint la première position de la FIFO, l'ordonnanceur crée les réservations pour celui ci sur les processeurs qui seront disponibles. Malheureusement, en attendant que toutes ces réservations soient faites, les ressources ne travaillent pas, or nous souhaitons avoir un cluster aussi occupé que possible. Le backfilling autorise que si une tâche peut être exécutée pendant ce temps intermédiaire, alors, elle le sera.
Fair scheduling : au lieu de répartir les ressources entre des processus, il s'agit de répartir en fonction des utilisateurs (ou groupe d'utilisateur). S'il y a deux utilisateurs (A et B) avec chacun une tâche, chacune des taches recevra 50% des ressources, si A ajoute une autre tâche, cela n'affectera pas B, et les deux processus de A recevront 25% des ressources. Favorise les utilisateurs peu gourmands
Réservation : contraindre la réservation de nœuds pour une période donnée, pratique mais entraîne gaspillage
Est ce que ça marche pour toutes les grilles ?
Non, Grid'5000 est essentiellement homogène, ce qui signifie que faire exécutée une tâche sur une machine plutôt que sur une autre est sans importance. Avec des grilles hétérogènes, ce n'est pas vrai.
Afin de prendre les meilleures décisions, l’ordonnanceur se base sur différents indicateurs qui lui permettent de connaître l’état de la grille à un instant donné : caractéristique CPU, mémoire et réseau d'un site ou encore son chargement à un instant donné. Celui ci doit également connaître les caractéristiques de l'application à envoyer sur la grille et ses besoins. On sait que les ressources exécutent plus ou moins facilement certaines tâches : il faut donc positionner l'application par rapport à d'autres.
Malheureusement, l'ordonnanceur n'a qu'une vision partielle de la grille à un instant donné. Contrairement à un ordonnanceur de Grid'5000, ici, les ressources sont autonomes et ne permettent pas forcément à l'ordonnanceur de la grille (externe , donc) d’accéder à ces informations. La vision de celui ci est donc incomplète et différentes selon les différentes politiques d'accès aux ressources des machines de la grille.
Les applications parallèles sont sensibles à la localisation des données partagées. S'il faut transférer les données d'un site à l'autre sans cesse, les performances s'en ressentiront. Afin de répondre à cette problématique, il est possible de spécifier sur OAR un nombre de cœur/cpu/nœuds nécessaires afin que les ressources puissent être proche afin de travailler plus vite. Possibilité de le préciser : L’option "-l" (minuscule) permet de préciser une liste de propriétés.
Par exemple :
demande de 2 cœurs sur un nœud, peu importe le nœud.
oarsub -I -l /nodes=1/core=2
Cependant, cette solution est loin d'être optimale.
Les solutions proposées par Grid5000 en matière d'ordonnancement sur grille sont assez basiques et connues depuis longtemps dans le monde de l'ordonnancement. Mais le monde de la grille est complexe, et les solutions les plus simples ont le mérite de fonctionner (avec succès pour grid5000). D'autres proposition pour gérer ces questions sont encore à l'étude.
L'idée de ce nouveau paradigme de programmation est d'exprimer au maximum l'utilisation qui sera faite des données. Les tâches sont représentées comme des boites s’échangeant des données. La totalité de la partie calcul est exprimée statiquement par le modèle, et les données sont représentées comme des paramètre ajoutés dynamiquement à l’exécution. Les applications data flow sont représentés comme un graphe orienté.
Plus besoin de découper le code en de multiples tâches à répartir sur la grille, puisque l'écriture et la conception même de l'application à été faite autour de cet objectif. De plus, réfléchir en terme de taches consécutives à effectuer est assez instinctif pour le programmeur en plus d'être un avantage pour les gens du monde de la Grille.
L'ordonnancement statique de telles applications peut offrir un partage tâches sur les ressources intéressant tout en permettant un regroupement géographique des données utilisées au même moment.
Ces applications workflow sont encore aujourd'hui à l'état de recherche en effet, il est difficile de changer de paradigme de programmation aussi facilement. Comment combiner expressivité du modèle, facilité d'approche de celui et efficacité du déploiement de telles applications sur la grille ?
Cependant, un tel modèle offrirait un certain nombre d'avantage, notement celui d'exploiter au maximum le parallélisme des applications. En effet, ce modèle met en évidence l'ordre dans lequel vont s’exécuter les tâches, mais surtout met en évidence le parallélisme de données. Considérons des applications nécessitant une utilisation massive de données,(ce qui est la problématique de nombreux calculs fait dans les grilles), et impliquant des traitement simples sur ceux ci : par exemple le traitement vidéo. L'objectif serait de trouver la meilleure ressource capable d’exécuter une tâche, disons "ajouter 2", et de dédier à cette machine tous les calculs consistant à "ajouter 2".
Si l'ordonnancement statique de telles applications commence à être intéressant, il reste difficile de gérer les passage à l'échelle, et on ne compte pas d’expérience industrielle réussie de grille utilisant le workflow (contrairement à Grid'5000 par exemple). Pire très peu d'applications existent selon le formalisme de workflow ce qui empêche des simulations réaliste en matière d'ordonnancement. D'autre part, si un nœud ne se comporte pas comme prévu, il est difficile de redéployer l'application vers un autre nœud. En conclusion, les application dataflow offrent des possibilités intéressantes dans le domaine de l'ordonnancement statique, et pas seulement dans le domaine des grilles, cependant beaucoup de travail est encore à faire avant de voir apparaître des grilles dataflow dans l'industrie.