Ordonnancement multicœur soucieux des caches et équilibrage de charge

L'ordonnancement multicœur soucieux des caches et équilibrage de charge, composante d'un système d'exploitation, consiste à partager l'activité du microprocesseur multi-cœur d'un ordinateur entre les programmes en cours d'exécution pour en optimiser la performance. Pour réaliser cette parallélisation, un ordonnanceur répartit les processus sur les cœurs disponibles, en prenant notamment en compte les mémoires caches.

Problème vignette|Architecture avec mémoire centrale partagée et les mémoires caches propres à chaque processeur. Avant le lancement d'un programme, il faut tenir compte de la façon dont il sera exécuté, comment seront répartis les processus chargés de son exécution. Cela permet de réduire le temps nécessaire à l'ordinateur pour effectuer toutes les opérations. Il s'agit de présenter les politiques d'ordonnancement qui existent sur les architectures multi-cœur pour minimiser le temps d'exécution d'un programme.

Les architectures multicœurs partagent, via un unique bus, les multiples accès simultanés que leurs cœurs réclament à la mémoire centrale. Afin de contourner autant que possible ce goulot d'étranglement, elles incluent différents niveaux de mémoires caches. Chaque cœur se voit doté d'un premier niveau de cache, qui lui est dédié. À l'autre extrémité, à proximité du bus d'accès à la mémoire centrale, un cache commun fédère l'ensemble des requêtes d'accès à des données que les caches inférieurs n'ont su servir. Comme les caches spécifiquement associés à un cœur mémorisent les transformations opérées sur les données, un système de maintien de la cohérence des données est mis en place entre eux. Lorsqu'un cœur accède à une donnée stockée dans le cache associé à un autre cœur, cette donnée est transférée jusqu'au cache associé au cœur qui en a demandé l'accès.

Aussi, les performances d'une architecture multicœur, c'est-à-dire le temps pris pour l'exécution d'un ensemble de programmes (processus), sont fortement corrélées à la répartition de ces exécutions sur les différents cœurs. En effet, l'exécution en parallèle de programmes manipulant un ensemble de données communes cause des problèmes de contention entre les données auxquelles ils accèdent. Lorsque deux cœurs exécutent des accès simultanés à une donnée partagée, leurs performances sont notablement réduites, à cause des défauts de cache à répétition qui permettent de maintenir la cohérence des données manipulées.

Les algorithmes d'ordonnancement chargés de la répartition des processus sur les cœurs doivent chercher à minimiser ces interférences entre les processus dont ils planifient l'exécution simultanée (sur des cœurs différents). Pour cela, ils doivent notamment éviter la planification de tâches partageant des données sur des cœurs différents. Toutefois, ils doivent aussi garantir l'équité entre l'exécution de tous les programmes. La recherche de compromis entre les performances et l'équité est à la source de développements algorithmiques spécifiques.

Architecture multicœurs Pour exploiter tout le potentiel des architectures multicœurs, les programmeurs doivent paralléliser les opérations de toutes les sections de leurs applications dès la phase de développement. Ainsi, ils sont capables de réduire les accès à la mémoire générale de la machine qui sont très coûteux en temps, en privilégiant l'utilisation des caches. Il ne suffit plus d'aborder le problème avec un parallélisme naïf, c'est-à-dire sans que le programmeur ne pense au préalable à comment et où doivent être effectuées les opérations, en utilisant simplement l'ordonnanceur « classique » fourni par le système..

Afin d'obtenir les meilleures performances sur une architecture donnée, les programmeurs forcent souvent le placement des données en fonction de l'architecture sur laquelle ils s'appuient. De cette manière, ils permettent aux données liées les unes avec les autres, qui possèdent une certaine affinité, d'être proches en mémoire les unes des autres. C'est une technique adaptée, mais mise en place manuellement pour satisfaire les conditions uniquement dans ce cas, mais qui n'est pas appropriée pour d'autres architectures. Elle présente un inconvénient majeur : les performances sont fortement dépendantes de l'architecture. Dans ces conditions, la politique d'ordonnancement n'est pas du tout portable.

Technique d'ordonnancement L'objectif d'un ordonnanceur est de répartir au mieux les traitements sur les processeurs et d'y accorder les laps de temps nécessaires pour réaliser en temps limité toutes les opérations des programmes. Il ne suffit donc pas seulement d'organiser les traitements entre les cœurs mais aussi de minimiser le temps d'exécution de ces traitements. La répartition des calculs vise à ce qu'ils respectent cet objectif et à réaliser l'ordonnanceur le plus adapté.

Les ordonnanceurs généralistes, c'est-à-dire qui pourraient s'adapter à tout type d'architecture, sont figés. Ils ne s'adaptent pas dynamiquement aux comportements des processeurs et à la charge qu'ils supportent pendant l'exécution du programme. C'est notamment le cas du , qui se charge de répartir les processus selon la politique suivante : quand un processeur devient inactif, l'ordonnanceur choisit de lui attribuer, en prenant en compte les affinités avec le processus que le processeur a précédemment exécuté, un processus dans la liste globale des processus qu'il reste à exécuter.. Cependant, il ne tient pas compte des partages de données entre les processus qui sont situés sur plusieurs cœurs. Cela explique qu'il n'obtienne pas de bonnes performances, car certaines applications sont imprévisibles, c'est-à-dire qu'il n'est pas possible de répartir efficacement les processus avant le début de l'exécution. En effet, il est impossible d'imaginer, avant exécution du programme, la meilleure politique pour répartir les différents processus entre les cœurs.

Se fier à ce genre d'ordonnanceurs peut donc poser d'importants problèmes, notamment concernant l'équilibrage de charge, car ils ne prennent pas en compte la charge de travail donné à un processeur, ils se contentent de placer les processus. Il est donc nécessaire de disposer d'ordonnanceurs capables de modifier leur politique, pendant et en fonction de l'exécution du programme, afin de résoudre ces problèmes. Si le programmeur connaît une politique d'ordonnancement efficace, il peut l'intégrer à son programme, grâce à des outils qui permettent de préciser comment, quand et où doivent être exécutées les diverses opérations du programme. C'est le cas d'OpenMP, une interface de programmation pour le calcul parallèle sur architecture à mémoire partagée supportée sur de nombreuses plateformes. Parmi ces environnements figurent les systèmes d'exploitation Unix, Linux et Windows, ainsi que les langages de programmation C, C++ et Fortran.

Localité des informations en mémoire Le placement des données est l'un des principaux facteurs en ce qui concerne les performances d'exécution d'un programme. En effet, un cœur accède beaucoup plus rapidement à un banc mémoire local (mémoire cache propre à chaque cœur) qu'aux autres bancs de l'ordinateur. Le rapport du coût d'accès à la mémoire distante via la mémoire locale est appelé rapport NUMA. Plus ce rapport est élevé, plus le coût d'accès à la mémoire des autres nœuds est important. Il varie généralement entre 1,2 et 3 selon les architectures.. Cela prouve que cet aspect du problème est loin d'être négligeable.

Si 2 processus auront besoin d'accéder aux mêmes informations, le programmeur peut fournir des informations concernant ces affinités entre les différents processus. C'est aussi le cas du compilateur qui peut détecter des relations que le programmeur n'avait pas décelé.. Les processus qui ont besoin des mêmes données devraient être placées sur un même cœur pour obtenir de bonnes performances. De cette façon, il y a moins d'accès mémoire distants au profit des accès au cache. Ceci permet d'améliorer les performances d'exécution du programme car les accès distants sont beaucoup plus couteux que les accès au cache.

Répartir les données en fonction des processus qui y accèdent n'est pas suffisant pour garantir de bonnes performances. Il faut connaître précisément la composition de l'architecture car elle influe directement sur le placement des données, par exemple en cas de cache partagé.. De plus, les nouveaux processus créés doivent être répartis en priorité selon les données dont ils ont besoin. De cette façon, ils peuvent s'exécuter plus rapidement car les temps d'accès à la mémoire sont plus courts.

Problèmes liés aux caches et à l'équilibrage de charge Il faut correctement répartir les processus et les données pour profiter au maximum des capacités des caches et éviter au maximum les accès à la mémoire générale de la machine.

Le but de toute technique d’équilibrage de charge est d’optimiser l’utilisation des processeurs en spécifiant la localité des traitements en minimisant le temps d'exécution des processus. Ce qui revient à maintenir une charge équivalente sur l’ensemble des processeurs. Il est également intéressant, pour traiter une opération réalisée par plusieurs processus simultanément, de mettre une barrière de synchronisation qui permet de s’assurer que les processus concernés ont tous terminé la première partie d’un calcul avant d’entamer la seconde..

BubbleSched et OpenMP Présentation L'extension de langage OpenMP permet au programmeur d'ajouter des directives de compilation parallèles au programme. De cette façon, il peut tenter de contrôler le parallélisme de l'exécution.

La plate-forme MARCEL BubbleSched permet de décrire dynamiquement la structure hiérarchique des calculs et de définir simplement des ordonnanceurs efficaces et portables.

L'utilisation conjointe de OpenMP et BubbleSched facilite le dialogue entre l’application et l’ordonnanceur afin de structurer l’exécution des programmes parallèles. C'est pour cette raison que FORESTGOMP une extension d'OpenMP, a été créée. Elle permet de s’appuyer sur la bibliothèque MARCEL BubbleSched, grâce à la bibliothèque libgomp, l'implementation GNU d'OpenMP. Cette nouvelle implémentation permet de remplacer les appels à la bibliothèque PTHREAD (la bibliothèque standard POSIX de gestion des threads) par leurs équivalents MARCEL.

Principes utilisés par les différentes bibliothèques de BubbleSched et OpenMP vignette|Principe de Bubblesched. Les cercles représentant les bulles et les vagues sont des threads de calculs qui ne peuvent être eux-mêmes découpés en sous-bulles. Les relations entre les processus d’une application sont représentées par des ensembles récursifs appelés bulles. Ces bulles sont elles-mêmes regroupées, par paire, avec un processus de communication dans une plus grande bulle. De cette façon, il est possible d'exprimer des relations telles que le partage de données et la participation à des opérations collectives. Ainsi, les opérations qui nécessitent le partage de données seront regroupées sur une même bulle. Chaque bulle pouvant elle-même contenir directement les processus ou d'autres bulles. Les algorithmes de type « Diviser pour régner », qui correspondent à répartir la charge de travail à effectuer sur les différents cœurs pour obtenir de meilleures performances, engendrent naturellement de nombreuses bulles de manière récursive. Il s’agit alors de les répartir au mieux en respectant les différentes relations qui existent entre les processus. Cela permet de paralléliser fortement les tâches que le programme doit exécuter.

Les machines hiérarchiques sont modélisées avec une hiérarchie de listes de processus. Chaque élément de chaque niveau de la machine est représenté par une liste de processus : la machine en elle-même, chaque nœud NUMA, chaque processeur, chaque cœur....