English version

Problématique

De nos jours, les machines multiprocesseurs ont des niveaux mémoire de plus en plus hiérarchisés: les systèmes Opterons sont en fait des NUMAs, les puces bicore peuvent partager un niveau de cache, on leur adjoint des cartes accélératrices, ... Comment ordonnancer correctement des calculs scientifiques non réguliers sur de telles machines ?! Il n'est plus réaliste de réaliser cet ordonnancement à la main, et l'on recourt à des ordonnanceurs dynamiques, qui permettent d'exploiter ces machines. Pour pouvoir optimiser l'ordonnancement, on utilise de nos jours de plus en plus le paradigme de tâches, auxquelles sont attachées des informations plus ou moins précises de durée, occupation mémoire, priorité, etc.

Publications

Co-encadrant de thèse pour:

Précédemment co-encadrant de thèse pour:

Ordonnancement de tâches sur systèmes hétérogènes, StarPU

Cédric Augonnet, durant sa thèse sous ma co-direction, a élaboré StarPU, un environnement pour ordonnancer des tâches sur des machines hétérogènes. L'idée est d'essayer d'effectuer toutes les optimisations à l'exécution: les transferts de données sont minimisés et effectués à l'avance, recouverts par les calculs, et interagissent avec les décisions d'ordonnancement de tâches. Ces dernières prennent en compte des modèles de performance des tâches, ce qui permet de capturer l'aspect hétérogène de la machine, et même d'en profiter !

StarPU est de plus en plus utilisé pour différents bibliothèques de calcul scientifique telles que l'algèbre linéaire (projet MORSE).

Nous avons étendu le modèle de programmation StarPU à l'exploitation distribuée de clusters à l'aide de MPI, ce qui pose des questions de passage à l'échelle.

Nous avons étendu la gestion des données de StarPU à l'utilisation des disques, permettant ainsi des calculs out of core, ce qui pose des questions d'optimisation des transferts.

La combinaison de StarPU avec Simgrid nous permet de simuler l'exécution, ce qui apporte non seulement un gain de temps pour observer les performances obtenues avec différentes heuristiques d'ordonnancement, mais aussi de modifier les paramètres de l'architectures simulée (bande passante, unités de calcul, ...) ! Plus généralement, avec la modularisation des ordonnanceurs StarPU, cela permet de fournir aux théoriciens une plate-forme pour tester différentes heuristiques sur des applications réelles, tout en évitant toutes les contraintes techniques de l'exécution réelle sur un système de production (fautes matérielles, versions de logiciels changeantes, ...).

Un enregistrement vidéo (26 min.) de ma présentation à la conférence XDC2014 donne un aperçu de ces travaux (transparents):

Une présentation à une classe de CM1 explique la problématique globale de manière très simple.

Publications autour de StarPU

Projets actuels liés à StarPU:

Projets précédents liés à StarPU:

Précédents travaux: modéliser les structures architecturales, hwloc

De mes travaux sur la hiérarchie d'une machine détaillés plus bas, nous avons extrait une brique logicielle, HwLoc, qui s'occupe d'abstraire les détails de détection et représentation de la hiérarchie d'une machine, qui est modélisée sous forme d'un arbre annoté. Les applications de calculs peuvent ainsi facilement, de manière portable, manipuler explicitement des « cœurs », des « sockets », mais aussi considérer la machine comme une hiérarchie générique, sans se soucier des détails architecturaux. Cette brique est désormais utilisée dans toutes les grandes implémentations de l'interface de communication MPI, et dans de nombreux projets de calcul. Elle est ainsi présente dans la majorité des centre de calculs.

Publications autour de hwloc

Précédents travaux: ordonnancement de threads sur systèmes hiérarchiques, Marcel

L'idée de base que j'ai développée durant ma thèse est de fournir aux programmeurs un moyen d'exprimer comment les threads de leurs application sont reliés: des bulles. Une bulle exprime par exemple que certains threads travaillent sur le même jeu de données, qu'ils communiquent souvent ensemble, ... si bien qu'ils devraient être ordonnancés dans le même "coin" de la machine ; ceci de manière hiérarchique.

J'ai développé une API qui permet de manipuler ces bulles avec un haut niveau d'abstraction. Ainsi, on peut expérimenter différents ordonnanceurs de distributions sans avoir à se soucier des détails techniques. On peut réellement se concentrer sur les problèmes algorithmiques.

J'ai développé quelques "ordonnanceurs à bulles" qui manipulent de telles hiérarchies de bulles: étaler la charge de calcul tout en prenant en compte les affinités, gang scheduling, vol de travail. Des stagiaires ont ensuite pu expérimenter d'autres stratégies: privilégier les affinités avant tout, prendre en compte la quantité des données utilisées, leur partage et la fréquence d'accès, ... Tout cela d'une façon qui peut s'adapter automatiquement à n'importe quelle machine hiérarchisée ! La thèse de François Broquedis a alors développé ces ordonnanceurs, en les expérimentant sur des applications OpenMP.

Ma thèse est disponible en PDF.

Ceci est développé au sein de Marcel, la bibliothèque de threads à la fois efficace, portable et flexible du projet PM2.

Publications autour de Marcel

Projets précédents liés à Marcel:

Autres projets