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

L'ordonnancement multicœur soucieux des caches et équilibrage de charge est une problématique importante dans la conception des systèmes d'exploitation destinés à gérer des microprocesseurs multi-cœurs. L'évolution des matériels depuis des microprocesseurs uniques vers des architectures pouvant exécuter simultanément plusieurs logiciels permet d'améliorer les performances d'exécution des programmes en parallélisant leur exécution.

Au sein d'un système d'exploitation, l'ordonnanceur a la charge de partager l'activité de la machine entre les différents programmes en cours d'exécution. Sur un matériel multicœur, l'ordonnanceur a la responsabilité de répartir les différents processus sur les différents cœurs disponibles. Les ordonnanceurs doivent prendre en compte les mémoires caches pour ne pas dégrader les performances globales du système tout en répartissant au mieux l'exécution des programmes sur les différents microprocesseurs.

Problématique

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 différentes politiques d'ordonnancement qui existent sur les architectures multicœ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 spécifiquement dédié. A 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 ces différents caches. 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 génère 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 différents 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 penser à 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 couteux en termes de 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 pense au préalable à comment et où doivent être effectuées les opérations, en utilisant simplement l'ordonnanceur "classique" fournit par le système^[1].

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^[2]. De cette façon, 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 bricolée manuellement pour satisfaire les conditions dans ce cas uniquement, mais qui n'est pas appropriée pour d'autres architectures. Ce qui présente un inconvénient majeur : les performances sont fortement dépendantes de l'architecture. Donc, 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. Il faut donc être vigilants à la répartition des calculs pour 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 le cas du Self-Scheduling^[3] 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, il n'est pas possible de répartir efficacement pour les performances les processus avant le début de l'exécution. En effet, il est impossible d'imaginer avant l'exécution 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, incluant Unix et Windows, pour 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^[4]. Ce qui prouve bien 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é^[5]. 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é^[6]. 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^[7].

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^[8]

Principes utilisés par les différentes librairies de BubbleSched et OpenMP

Principe de Bubblesched. Les cercles représent 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^[2].

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^[9]...

Les bulles ont également un ensemble d’attributs choisis par les programmeurs pour donner des informations sur l’ensemble des processus qu'elles contiennent telles que le degré de priorité, la politique d’ordonnancement à lui appliquer, un compteur pour le nombre total de processus qui seront créés ou encore le nombre de processus actifs à un instant t^[10]. Le degré de priorité d'une bulle détermine l'ordre dans lequel les processus seront exécutés. Lorsqu’un processeur, en devenant inactif, cherche une tâche à exécuter, il parcourt les différentes listes qui le couvrent, des plus locales (du niveau le plus bas) aux plus globales, jusqu'à la machine elle-même. Il cherche la tâche de priorité maximale. Il devra alors exécuter cette tâche, même si d’autres tâches, plus locales et moins prioritaires existent. Cela permet par exemple aux processus de communication d’être exécutés dès que possible.

Par défaut, les bulles sont placées au démarrage sur la liste de la machine entière^[11]. Une telle répartition permet d’utiliser tous les processeurs de la machine, puisque tous ont l’opportunité d’exécuter les processus (dans l'ordre des degrés de priorité). Cependant, les performances ne sont pas bonnes puisque les affinités entre processus pour le partage d'informations, et entre processus et cœur (par rapport aux données présentes dans le cache) ne sont pas prises en compte puisqu’aucune relation n'est définie.

Ordonnanceur

Pendant l’exécution d'un programme, l'ordonnanceur dispose d’informations sur l'architecture de la machine sur laquelle il travaille, depuis l’organisation des bancs mémoire pour les machines de type NUMA jusqu’à la répartition des mémoires caches. Il dispose aussi de compteurs de performances pour savoir si l’application s’exécute correctement. Le nombre de défauts de cache, c'est-à-dire l'accès à une donnée non encore présente dans la mémoire cache du processeur, et d’instructions par cycle (IPC) permettent également de mesurer la concurrence au sein des processeurs. Le compilateur peut aussi fournir des indications sur le comportement de l’application. En analysant toutes ces informations, il est possible de déterminer la meilleure répartition des processus pour maximiser les performances^[12]

Ecrire un ordonnanceur qui s'adapte à BubbleSched se résume à écrire des fonctions clés appelées à certains moments de l’exécution d’un programme^[13]. Une de ces fonctions sera par exemple appelée afin de répartir les processus et les bulles sur les différentes listes au démarrage de l'exécution. Une autre permettra de rééquilibrer la charge lorsqu’un processeur deviendra inactif.

Il existe différentes politiques d'ordonnancement comme le "vol de travail" ou la répartition "par gang".

• Le "vol de travail^[14]" :

Il consiste à trouver des processus à exécuter par un processeur lorsqu'il est inactif. De cette façon, un processeur "vole" le travail car ce travail était préalablement destiné à un autre. Il faut pour cela ajouter des relations père/fils entre les listes de processus, c'est-à-dire connaître pour une liste donnée, celle qui l'a engendrée et celles qu'elle engendrera. L'ordonnanceur cherche d'abord localement puis plus globalement, jusqu’à trouver du travail. Savoir quel "vol" effectuer est un problème algorithmique non trivial : seule une partie de la hiérarchie de bulles devrait être tirée vers le processeur inactif pour que l'ordonnancement soit vraiment efficace. Dans le cas contraire, les charges sur les processeurs ne seraient plus équilibrées.

• Les "gangs^[15]" :

John OUSTERHOUT propose de regrouper les processus et les données, par affinités, sous forme de gangs et de placer, non plus des processus sur des processeurs, mais des gangs sur des machines^[16]. Une machine est symbolisée par une liste de processus pouvant être exécutés sur n'importe quel processeur. Pour réaliser un gang-scheduler, on associe une bulle à chaque gang, et on laisse tourner un démon qui met de côté toutes les bulles (c'est-à-dire les gangs) sauf une, qu’il laisse sur la liste principale, la machine, pendant un certain laps de temps, avant de recommencer pour placer une autre bulle. De cette façon, comme les bulles contiennent déjà les relations d'affinités, les processus qui s'exécutent pendant ce laps de temps, font bien référence aux mêmes informations.

Les programmeurs peuvent même combiner les types d'ordonnanceurs, vol et gang, présentés ci-dessus^[12] pour une même exécution.

Performances

Les défauts de cache et le facteur NUMA (rapport entre les temps d’accès à la mémoire générale de la machine et les accès locaux aux caches) influent tellement, avec l'évolution des architectures, sur les performances des exécutions qu'il est presque aussi important de paralléliser le programme que de répondre à ces deux problèmes^[17].

Concernant l'allocation d'objets, la bibliothèque MARCEL utilise un « cache » de piles d'exécution^[18], pour éviter d'encombrer le système à chaque création d'un processus. A la création de la bibliothèque, ce cache était partagé, ce qui pose des problèmes lorsqu'il est sollicité par plusieurs processeurs simultanément. Dans ce cas, lorsque plusieurs processeurs créent des processus grâce au cache général, le temps de création concurrente de nombreux processus explose avec le nombre de processeurs^[19]. Cependant, si un cache est créé pour chaque processeur, les temps nécessaires à la création des processus sont constants. Il y a tout de fois un inconvénient à cette pratique. Si un processeur crée de nombreux processus, qui seront répartis sur les autres processeurs de la machine, le cache du premier processeur sera vide et les autres caches, au contraire, se rempliront.

De plus, la création et la destruction d'une bulle n'entraine pas une perte significative des performances par rapport à la création et la destruction du processus seul. En effet, les temps d'exécution pour ces deux opérations varient de 3,3μs à 3,7μs^[20].

Améliorations de BubbleSched

MaGOMP

MaGOMP^[21] est une extension de GOMP (GNU openMP compiler). C'est une partie de GOMP qui utilise la librairie Marcel (celle dans laquelle BubbleSched est implémenté). MaGOMP permet d'organiser les threads par équipes, avec pour chaque équipe, un maitre d'équipe. C'est ce maitre d'équipe de la bulle (l'équipe) qui va répartir le travail entre tous les équipiers. Une fois que tous les équipiers ont terminé leur travail, ils se terminent et le maitre d'équipe détruit la bulle avant de rejoindre le thread qui l'a lancé.

Burst

Burst^[22] est un ordonnanceur à bulles. Il utilise une stratégie de répartition basique pour laquelle l’application indique, en même temps qu’elle crée des bulles, à quels niveaux celles-ci doivent éclater. Les bulles et threads sont alors répartis sur la machine de manière opportuniste en faisant éclater les bulles aux niveaux indiqués. Lorsque celui-ci trouve une bulle, au lieu de la parcourir pour trouver un thread à exécuter (le comportement par défaut), l’algorithme Burst fait descendre cette bulle vers le processeur courant jusqu’à une liste d’un niveau au moins aussi profond que celui attribué à cette bulle par le programmeur d’application. Une fois déplacée sur cette liste, la bulle est « éclatée », c’est-à-dire que son contenu (threads et sous-bulles) est libéré sur la liste. L’algorithme de base peut alors reprendre pour découvrir ce contenu. Dans le cas de threads, il peut alors les exécuter. Dans le cas de sous-bulles, la méthode sched sera de nouveau appelée pour faire descendre une des sous-bulles encore plus bas vers le processeur courant.

Spread

L’ordonnanceur Spread^[22] utilise un algorithme plus évolué pour distribuer bulles et threads sur la machine en prenant en compte une notion de charge fournie par exemple par l’application. Il met en œuvre une généralisation de l’algorithme glouton classique utilisé pour résoudre le problème de Bin Packing, la différence étant qu’ici le but n’est pas simplement de répartir des objets dans les conteneurs, mais de répartir une arborescence d’objets (la hiérarchie de bulles et de threads) sur une arborescence de conteneurs (la hiérarchie de listes de threads). La difficulté est de choisir le moment et la bulle à percer. La tactique est simple : on privilégie l’équilibrage de charge. Cette tactique pourrait être affinée par des heuristiques qui décideraient de manière plus adaptée quelles bulles éclater en fonction de la finesse de charge que leur contenu pourrait apporter.

MemAware

MemAware^[22] permet un ordonnancement dirigé par la mémoire. Le principe est de créer un tas pour chaque thread et chaque bulle. Lorsque l’application effectue une allocation de données, elle indique quels threads accéderont le plus à ces données. Elle peut également indiquer une fréquence d’accès aux données. L’allocation est alors effectuée dans le tas correspondant au thread ou à la bulle indiquée.

Ceci permet ainsi d’avoir à tout moment une connaissance hiérarchisée des affinités entre threads, données et nœuds NUMA.

Affinity

Affinity^[23] est un ordonnanceur à bulles qui respecte les relations d’affinité entre threads issus des mêmes sections parallèles Il soutient le fait que les threads et sous-bulles d'une même bulle dispose d'un certain niveau d'affinité, puisqu'ils partagent par exemple, des données communes. Il ordonne donc les membres d’une même bulle sur un même processeur, quitte à engendrer des déséquilibres de charge provoquant une redistribution locale de temps à autre.

Cette solution dispose de deux algorithmes principaux, l’un pour effectuer une distribution des groupes d’entités sur une architecture hiérarchique, l’autre pour rééquilibrer cette répartition dynamiquement.

Il est parfois nécessaire d’éclater les bulles (extraire le contenu d’une bulle pour augmenter le nombre d’entités ordonnançables), pour occuper un nombre plus important de processeurs. Les entités d’une bulle éclatée sur le niveau modélisant la machine tout entière peuvent être exécutées par n’importe quels processeurs, qu’ils soient sur le même banc NUMA ou non.. C’est pourquoi Affinity retarde au maximum l’éclatement des bulles, afin de maximiser la localité entre entités extraites.

STREAM

STREAM^[24] est un benchmark synthétique développé en C, parallélisé en OpenMP, qui mesure la bande passante mémoire soutenue de la machine et le taux de calcul correspondant en effectuant des opérations simples sur des vecteurs d’entiers. Ces derniers sont suffisamment grands pour ne pas tenir dans le cache et sont initialisés en parallèle pour garantir à chaque thread la localité de ses données.

Le support exécutif ForestGOMP obtient au contraire des performances stables. En effet, en l’absence d’informations d’affinité mémoire, l’ordonnanceur Cache s’occupe seul de la répartition des threads et leur attribue à chacun un cœur dédié.

Twisted-STREAM

Twisted-STREAM^[25] est un benchmark développé conjointement avec STREAM. Il est destiné à compliquer le motif d'accès mémoire.

Il permet une répartition assurant la suppression totale des accès distants en ayant migré le moins de données possible. Le surcoût de cette approche est inférieur à celui engendré par la migration classique qui provoque la migration du double de données, tout en obtenant les meilleures performances quand la charge de travail par thread augmente.

Alternatives à BubbleSched

Matériel

L'enjeu principal pour le gain de puissance tend vers une utilisation plus intelligente et mieux gérée des processeurs multicœurs, les constructeurs adaptent le matériel dans ce sens.

Ainsi, SUN commercialise des puces capables d’exécuter simultanément 32 threads sur 8 cœurs et IBM en est à 4 threads sur 2 cœurs^[26]. De leur côté AMD et INTEL ont planifié la production de puces 4 cœurs et réfléchissent même à l’intégration d’une centaine de cœurs sur une seule puce.

ELITE

Le projet ELITE^[26] fournit comme BubbleSched implémentation d’une plate-forme d’ordonnancement de niveau utilisateur qui prend en compte les affinités entre threads, cache et données.

NewMadeleine

Contrairement aux bibliothèques de communication classiques, NEWMADELEINE^[27] applique dynamiquement des stratégies d’ordonnancement et d’optimisation.Différentes stratégies d’optimisation (agrégation de messages, répartition des messages sur plusieurs réseaux, etc.) sont définies et peuvent agir en fonction de l’état des cartes réseaux.

NEWMADELEINE base son activité sur celle des cartes réseaux : lorsque ces dernières sont occupées à transmettre des données, les messages déposés par l’application sont accumulés. Lorsque les cartes réseaux sont inutilisées, NEWMADELEINE invoque une stratégie d’optimisation et génère un paquet à transmettre par le réseau. NEWMADELEINE profite donc des moments pendant lesquels les cartes réseau sont occupées pour accumuler des messages de l’application et ainsi avoir un large choix d’optimisations.

Afin de gérer les interactions entre NEWMADELEINE et MARCEL, PIOMAN^[27], un gestionnaire d’entrées/sorties, prend en charge les problèmes de multi-threading pour la bibliothèque de communication. Ainsi, NEWMADELEINE peut concentrer ses efforts sur la gestion et l’optimisation des requêtes réseau et le code n’est pas complexifié par une gestion de la progression des communications ou par la parallélisation des traitements.

Pour cela, MARCEL donne la main fréquemment à PIOMAN, de telle sorte que les tâches (détection des événements ou tâche soumise par la bibliothèque de communication) puissent être exécutées. Des appels à PIOMAN sont insérés à certains points-clés de l’ordonnancement : dans la boucle idle afin que PIOMAN puisse exploiter les processeurs inutilisés, lors des changements de contexte et dans le code traitant les signaux d’horloge.

Perspectives

Fonctions dans le développement des programmes

A plus long terme, l’objectif^[28] est de fournir à l’application des moyens d’expression suffisamment puissants et portables pour permettre un ordonnancement s’approchant de l'ordonnancement optimal. Il serait par ailleurs utile de fournir à l’application des fonctions d’allocation mémoire plus expressives : préciser par exemple quelles tâches (ou tâches d’une bulle) utiliseront la zone allouée.

Ordonnanceur générique

Un ordonnanceur générique pourrait être développé^[29] ; celui-ci prendrait en compte autant d’informations qu’il est possible de collecter auprès du matériel, du compilateur et du programmeur. L’intégration au sein du noyau LINUX pourrait même être envisagée, puisqu’une hiérarchie naturelle de bulles existe déjà au travers des notions de threads, processus, jobs, sessions et utilisateurs.

Lier les compteurs de performances

Il serait possible d’utiliser les compteurs de performances^[30] intégrés aux processeurs pour obtenir des informations sur la qualité de l’exécution actuelle de l’application.

Un ordonnanceur à bulles pourrait ainsi par exemple détecter un taux anormal de défauts de cache, et décider alors de distribuer les threads en cours d’exécution sur un plus grand nombre de processeurs, pour que ces threads ne se gênent pas mutuellement dans des caches partagés.

Gérer les placements mémoires

Dans le cadre de l’ANR NUMASIS^[24], des travaux préliminaires ont montré que l’utilisation conjointe de BubbleSched et d’une bibliothèque de gestion mémoire orientée NUMA permet de diriger dynamiquement placement mémoire et ordonnancement de thread. L’intégration de telles fonctionnalités permettront d’améliorer Affinity afin de décider de la migration de certaines pages mémoires lors d’un vol de travail.

Ensuite, afin de privilégier l’intégrité des bulles partageant effectivement des données, il serait judicieux de mettre en œuvre des techniques d’analyse statique à la compilation et statistique à l’exécution. Une extension envisageable au langage OpenMP pourrait permettre au programmeur de sélectionner la stratégie d’ordonnancement optimal à chaque section et ensemble de tâches parallèles du programme considéré.

Notes et références

Références

1. ↑ François broquedis 2008, p. 1.
2. ↑ ^{a et b} Samuel Thibault 2006, p. 1.
3. ↑ Samuel Thibault 2005, p. 2.
4. ↑ François Broquedis 2009, p. 2.
5. ↑ G. Mercier 2009, p. 2.
6. ↑ F. Broquedis 2009, p. 2.
7. ↑ Samuel Thibault 2005, p. 4.
8. ↑ François Broquedis 2008, p. 3.
9. ↑ François Broquedis, Brice Goglin, Raymond Namyst, Pierre-Andre Wacrenier 2008, p. 4.
10. ↑ Samuel Thibault 2006, p. 3.
11. ↑ Samuel Thibault 2006, p. 4.
12. ↑ ^{a et b} Samuel Thibault 2006, p. 2.
13. ↑ François Broquedis 2008, p. 3.
14. ↑ Samuel Thibault 2006, p. 6.
15. ↑ Samuel Thibault 2006, p. 5.
16. ↑ John Ousterhout 1982, p. 1.
17. ↑ F. Broquedis 2007, p. 1.
18. ↑ Samuel Thibault 2007, p. 75.
19. ↑ Samuel Thibault 2007, p. 76.
20. ↑ Samuel Thibault 2005, p. 8.
21. ↑ Franc ̧ois Broquedis, Brice Goglin, Raymond Namyst, Pierre-Andre Wacrenier 2007, p. 3.
22. ↑ ^{a, b et c} Samuel Thibault 2007
23. ↑ François Broquedis, François Diakhaté, Samuel Thibault, Olivier Aumage, Raymond Namyst, and Pierre-André Wacrenier 2008, p. 4.
24. ↑ ^{a et b} F. Broquedis 2008.
25. ↑ F. Broquedis 2009.
26. ↑ ^{a et b} Samuel Thibault 2006
27. ↑ ^{a et b} F. Trahay 2009.
28. ↑ S. Thibault 2005.
29. ↑ S. Thibault 2005.
30. ↑ S. Thibault 2007.

Bibliographie

• S. Thibault, « Un ordonnanceur flexible pour machines multiprocesseurs hiérarchiques », dans Sujet de thèse, avril 2005 
• S. Thibault, « BubbleSched : construire son propre ordonnanceur de threads pour machines multiprocesseurs hiérarchiques », dans Rencontres Francophones du Parallélisme (RenPar), SympA, CFSE, octobre 2006 
• (en) F. Broquedis, B. Goglin, R. Namyst et P-A. Wacrenier, « An Efficient OpenMP Runtime System for Hierarchical Architectures », dans Rapport INRIA, juin 2007 
• S. Thibault, « Ordonnancement de processus légers sur architectures multiprocesseurs hiérarchiques : BubbleSched, une approche exploitant la structure du parallélisme des applications », dans Sujet de thèse, décembre 2007 
• F. Broquedis, « Exécution structurée d’applications OpenMP à grain fin sur architectures multicoeurs », dans Rencontres Francophones du Parallélisme (RenPar)’18/SympA’2008/CFSE’6, février 2008 
• (en) F. Broquedis, F. Diakhaté, S. Thibault, O. Aumage et P-A. Wacrenier, « Scheduling Dynamic OpenMP Applications over Multicore Architectures », dans International Workshop on OpenMP, octobre 2008 
• (en) F. Broquedis, N. Furmento, B. Goglin, R. Namyst et P-A. Wacrenier, « Dynamic Task and Data Placement over NUMA Architectures : an OpenMP Runtime Perspective », dans International Workshop on OpenMP (IWOMP), mars 2009 
• (en) F. Trahay, E. Brunet et A. Denis, « An analysis of the impact of multi-threading on communication performance », dans Communication Architecture for Clusters, mai 2009 
• F. Broquedis, « Ordonnancement de threads OpenMP et placement de données coordonnés sur architectures hiérarchiques », dans Rencontres Francophones du Parallélisme (RenPar), octobre 2009 
• (en) G. Mercier et J. Clet-Ortega, « Towards an Efficient Process Placement Policy for MPI Applications in Multicore Environments », dans Europvm/mpi 2009, Espoo : Finland, novembre 2009 
• F. Trahay, « De l’interaction des communications et de l’ordonnancement de threads au sein des grappes de machines multi-cœurs », dans sujet de thèse, novembre 2009 
• (en) F. Broquedis, O. Aumage, B. Goglin, S. Thibault, P-A. Wacrenier et R. Namyst, « Structuring the execution of OpenMP applications for multicore architectures », dans International Parallel and Distributed Symposium (IPDPS 2010), janvier 2010 
• (en) J. Ousterhout, « Scheduling techniques for Concurrent Systems », dans université de Berkeley (Californie), août 1982 

Articles connexes

• Théorie de l'ordonnancement
• Ordonnancement de tâches informatiques