Théorie et pratique de l'ordonnancement d'applications sur les systèmes distribués

L'émergence de nouveaux supports d'exécution tels que les grilles de calcul et les clusters de PCs a démocratisé le calcul haute performance. Un mécanisme efficace de gestion des ressources est indispensable pour obtenir de bonnes performances sur ce type de machines. La littérature contient quantité de travaux théoriques sur ce domaine, en particulier un certain nombre de modèles et d'algorithmes, mais il n'y a pas de consensus clair sur un moyen universel de gérer ces ressources. De plus, les modèles théoriques sont souvent très simplifiés par rapport aux réalités pratiques de tels systèmes ; et les algorithmes proposés sont généralement très sophistiqués, leurs temps de calcul élevés et la difficulté de leur implémentation sont alors un frein à leur utilisation pratique.

Réciproquement, plusieurs logiciels spécialisés dans la gestion de ces ressources ont été développés et sont largement utilisés. Ils offrent souvent des fonctionnalités évoluées pour permettre aux utilisateurs d'accéder aux ressources de façon pratique pour eux. Cependant, ils intègrent peu les travaux théoriques de la communauté de l'ordonnancement, qui sont trop complexes et trop peu connus des développeurs de tels systèmes. Les algorithmes mis en œuvre sont ainsi toujours de simples heuristiques gloutonnes, sans réels fondements théoriques.

Dans ma thèse, je me suis attaché à explorer ces deux facettes de la gestion de ressources, analyse théorique et mise en œuvre pratique, en insistant sur les possibilités d'interactions et de connexions entre les deux communautés.

Approche théorique

D'un point de vue théorique, je me suis intéressé au modèle des Tâches Parallèles, qui se place à une granularité appropriée par rapport à la pratique dans les logiciels de gestion de ressources. Dans ce modèle, on considère un ensemble de travaux indépendants à effectuer, chacun pouvant nécessiter plusieurs nœuds de la plate-forme. Ces tâches sont rigides si le nombre de nœuds nécessaires est fixé par l'utilisateur au moment de la soumission, ou modelables si ce nombre est choisi par le système au moment d'exécuter chaque tâche.

Dans le cadre des tâches modelables, j'ai conçu un algorithme d'ordonnancement avec une garantie de performance sur deux critères simultanément, le makespan et le temps de complétion moyen, qui expriment deux attentes souvent contradictoires des utilisateurs de tels systèmes. Cet algorithme est basé sur une structure originale en lots de tailles croissantes, et a une garantie de performance au pire cas de 6 sur chacun des deux critères ; une version randomisée permet d'obtenir des espérances de garantie de l'ordre de 4, ce qui améliore la meilleure garantie connue auparavant pour le seul critère du temps de complétion moyen.

Cet algorithme, bien qu'ayant une complexité théorique polynomiale, est trop sophistiqué et a un temps de calcul trop long pour être intégré tel quel dans un système de gestion de ressources. J'ai donc dérivé une version simplifiée de cet algorithme dans laquelle la structure en lots est conservée, mais la procédure de sélection des tâches est plus directe. Cette heuristique n'apporte aucune performance de garantie, mais une campagne de tests par simulation a montré qu'elle avait en moyenne des performances proches d'une borne inférieure pour chacun des critères.

Approche pratique

Pour continuer la validation de cette heuristique, je l'ai implémentée dans l'environnement de OAR, un système de gestion de ressources développé au laboratoire ID. Cette implémentation a soulevé de nombreux problèmes, car le modèle d'applications de OAR est plus riche que le modèle théorique que nous avons étudié. Cependant, faire l'étude théorique complète aurait été impossible dans un modèle aussi complexe. Cette implémentation a été validée en rejouant les traces d'exécution de clusters locaux. Il est maintenant prévu de l'utiliser en vraie grandeur.

Parmi les problèmes rencontrés lors de l'implémentation, la présence de réservations comme contraintes pour l'ordonnancement est apparue comme un problème important et difficile à gérer. Je suis donc revenu sur le modèle théorique pour le prendre en compte. J'ai ainsi pu obtenir quelques premiers résultats théoriques de complexité et de garanties de performance pour des algorithmes de liste.

Projet de recherche

Pour aller plus loin dans cette ligne de recherche, je suis intéressé pour continuer les recherches théoriques sur les réservations, afin de les intégrer à terme à l'implémentation pratique. De plus, OAR est actuellement en évolution, et il serait intéressant d'étudier les changements théoriques qu'amènent la nouvelle version.

Je suis également intéressé pour considérer des architectures plus complexes de type grilles de calcul, avec éventuellement des modèles d'applications plus simples, comme les tâches divisibles, qui sont une façon intéressante de modéliser les applications multi-paramétrique. Dans cette optique, et même de façon plus générale, il me semble important d'étudier d'autres critères, plus adaptés à des environnements interactifs (comme par exemple le stretch ou le flot).