Optimisation Mémoire en HPC
Optimisation Mémoire en HPC
Spécialité
Informatique
Je donne toute ma gratitude à ceux qui ont permis la réalisation de ce travail et qui m’ont
guidé tout au long de ces années de thèse. Je remercie tout particulièrement mon encadrant au
CEA, Marc Pérache, pour avoir supervisé mon travail pendant ces années depuis mes débuts en
stage. Merci à lui pour sa disponibilité et pour avoir laissé une part de liberté dans le travail
réalisé. Merci d’avoir supporté la trop grande fougue dont j’ai parfois pu faire preuve sur l’avan-
cée du projet MPC. Je tiens également à remercier mon directeur de thèse, William Jalby, pour
avoir encadré ces travaux à l’UVSQ et de m’avoir fait découvrir les finesses des architectures des
processeurs. Merci à lui de m’avoir acceuilli à mes débuts au laboratoire Exascale.
Ma reconnaissance va aux membres du CEA pour m’avoir accueilli et d’avoir permis la réa-
lisation de cette thèse, notamment Hervé Jourdren, Bruno Scheurer et Pierre Leca. Également
merci aux secrétaires du centre, Stéphanie, Isabelle et Éliane pour leur aide administrative et
leur bonne humeur. Je n’oublie pas non plus Patrick Carribault également membre permanent
de l’équipe MPC et qui a apporté son aide et sa bonne humeur tout au long de cette thèse.
Un grand merci aux doctorants Jean-Baptiste et Jean-Yves pour les discussions à n’en plus fi-
nir et pour leur enthousiasme pour les nouvelles idées geek. Merci à Bertrand et Alexandre pour
les échanges sur la physique qui m’ont fait le plus grand bien. Merci à Julien, mon collègue de bu-
reau, pour sa motivation, son enthousiasme et pour n’avoir jamais oublié de donner son propre
avis lors de nos discussions techniques. Tout autant merci aux doctorants et post-doctorants du
CEA avec qui j’ai partagé de très agréables moments dans nos bâtiments et autour de tables de
repas animées : Marc, François, Emmanuel, Nicolas, Jordan, Jérôme, Antoine, Camille, Emma-
nuelle, Xavier, Thomas. Sans oublier les personnes avec qui j’ai pu travailler à l’UVSQ : Sylvain,
Emmanuel, Cédric, Asma, Augustin, Aurèle et tous ceux dont il serait trop long de donner la
liste complète. Merci à tout ceux précédemment cités qui ont fait parti du projet MPC et avec
qui nous avons longuement échangé autour de ce projet.
Un grand merci à ma famille, notamment mes parents et ma sœur pour leur présence sur le
chemin qui m’a amené jusqu’à cette thèse et pour leur soutien sans faille durant cette période.
Merci à ceux qui ont pris du temps pour relire ce document, dont mon cousin, Roland.
Je tiens enfin à remercier l’ensemble des enseignants qui m’ont permis de concrétiser ce che-
min, notamment à l’université de Savoie et à mes anciens collègues de l’association C-Net sans
qui je ne serais pas où je suis aujourd’hui. Tout autant merci aux amis avec qui j’ai pu partager
mes idées et mes rêves pendant ces années d’études et ceux qui m’ont soutenu pendant ces an-
nées de thèse.
Table des matières
Préambule 15
I Contexte 17
9
TABLE DES MATIÈRES
2 Gestion de la mémoire 41
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Le système d’exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.1 Problématiques du multiprogramme/multiutilisateur . . . . . . . . . . . . 41
2.2.2 Adresses virtuelles, adresses physiques . . . . . . . . . . . . . . . . . . . . 42
2.2.3 Segmentation et pagination . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.4 Notion de processus et threads . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.5 Espace noyau et utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3 Interface avec les applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.1 Les appels systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Fautes de pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4 L’allocateur mémoire (malloc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.2 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.3 Ramasse-miettes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4.4 Problématique d’implémentation . . . . . . . . . . . . . . . . . . . . . . . 50
2.5 Accès à la mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.1 Les caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5.2 MMU et TLB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5.3 Grosses pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5.4 Accès mémoire non uniformes : NUMA . . . . . . . . . . . . . . . . . . . . 54
2.5.5 OS et support NUMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
II Contribution 57
10
TABLE DES MATIÈRES
11
TABLE DES MATIÈRES
7 Conclusion 147
8 Perspectives 151
Bibliographie 155
Annexes 159
12
C File atomique pour l’allocateur 171
TABLE DES MATIÈRES
14
Préambule
Les sciences informatiques sont aujourd’hui devenues un outil essentiel dans le domaine de
la recherche et de l’industrie. Ce domaine apporte en effet un moyen pratique de traiter de
grandes quantités d’informations, que ce soit au travers de la simulation numérique comme ou-
til prédictif ou pour l’analyse de données expérimentales. Au fil des années, les calculateurs mis
en place pour résoudre ces problèmes sont devenus des objets extrêmement complexes offrant
une puissance de calcul toujours croissante. C’est ainsi que l’on a aujourd’hui atteint l’échelle
du pétaflops permettant idéalement d’effectuer 1015 opérations flottantes par secondes. Les nou-
velles ambitions se tournent donc vers le pas suivant : l’exaflop avec 1018 opérations flottantes
par secondes. L’évolution technologique a toutefois effectué un tournant au courant des années
2000. Ces années ont induit des changements en profondeur des architectures faisant apparaître
de nouveaux problèmes qu’il nous faut aujourd’hui prendre en compte.
Dans ce contexte en forte évolution, le choix d’un modèle de programmation exprimant ef-
ficacement le parallélisme devient une question sensible en pleine mutation. À l’heure actuelle,
si la recherche fournit différentes approches, aucune n’a pour l’instant su se présenter comme
LA solution retenue par tous. L’heure est donc au mélange de modèles du fait des choix des
différentes bibliothèques que l’on peut être amené à utiliser. Ces changements doivent éga-
lement cohabiter avec la présence de certains codes historiques (legacy) utilisant d’anciennes
techniques. Le CEA et le laboratoire Exascale Computing Research ont donc investi dans le dé-
veloppement d’un support exécutif (MPC : Multi-Processor Computing) prenant en compte ces
problématiques. Ce support a pour but de faire fonctionner les différents modèles de program-
mation sur une base unifiée permettant leur coopération. Dans ce contexte, nous avons observé
des pertes de performances notables imputables aux mécanismes de gestion de la mémoire.
Nous montrerons ainsi qu’il est possible dans certaines situations d’observer des écarts de per-
formances pouvant dépasser les 50% du temps d’exécution total.
Les problématiques étudiées dans ce document seront donc abordées au travers d’un regard
orienté calcul haute performance (HPC : High Performance Computing). Les points clés concer-
neront donc les aspects massivement multicœurs et de consommation mémoire. Le plan de la
thèse sera donc le suivant.
La première partie de ce document dressera un état des lieux et introduira les concepts fon-
15
Préambule
damentaux attachés au HPC, à son historique et aux méthodes de programmation ayant cours
à l’heure actuelle. Y seront également introduits les points clés attachés aux problématiques de
gestion mémoire sur les architectures modernes notamment au niveau du système d’exploitation
(OS : Operating System).
La deuxième partie décrira les travaux propres à cette thèse. Nous y aborderons dans un
premier temps le problème d’efficacité d’accès aux données. De ce point de vue, les architec-
tures actuelles introduisent en effet des mémoires locales (caches) masquant les latences d’accès
à la mémoire centrale. L’organisation actuelle du matériel est telle que l’OS et l’allocateur mé-
moire peuvent conduire à une perte d’efficacité de ces caches, pénalisant l’accès aux données.
Dans ce sens, nous étudierons les effets d’interférences pouvant survenir entre les politiques
des différents éléments en interaction (caches, OS, allocateur, application). Nous montrerons
notamment qu’une analyse isolée de ces derniers n’est pas suffisante et qu’elle peut induire des
effets néfastes. Le problème sera essentiellement étudié vis-à-vis des mécanismes de pagination
en comparant les politiques de différents OS. Nous mettrons ainsi en évidence le couplage qui
existe entre ces politiques et l’allocateur mémoire en espace utilisateur. Nous discuterons alors
l’intérêt souvent négligé de la politique de pagination de Linux. L’utilisation de grosses pages
sur les architectures modernes peut conduire à des effets similaires, impliquant une nécessité de
prendre en compte ces dernières au sein même de l’allocateur en espace utilisateur.
On abordera dans un deuxième temps l’étude d’un allocateur mémoire parallèle spécifique-
ment conçu pour traiter les problèmes de performances d’allocation rencontrés au niveau des
OS sur les nouvelles architectures. Ce travail prendra comme point focal la problématique des
grosses allocations qui sont habituellement négligées dans la conception des allocateurs et re-
dirigées directement vers l’OS. Or, ces derniers rencontrent des problèmes d’extensibilité sur les
nouvelles architectures. Nous discuterons donc une méthodologie de réutilisation mémoire afin
de limiter les échanges avec le système. À ce titre, nous verrons qu’il est pour l’instant néces-
saire de rechercher un compromis entre consommation mémoire et performance, compromis
que nous nous sommes efforcés de rendre configurable de manière dynamique. Ce travail sera
complété par une prise en compte des architectures à mémoire non uniformes (NUMA : Non
Uniforme Memory Access) par l’organisation structurelle de l’allocateur. L’utilisation conjointe de
ces techniques permet à l’heure actuelle d’obtenir des gains non négligeables (jusqu’à 50%) sur
un code de simulation numérique.
La méthode de recyclage des gros segments discutée précédemment est introduite pour pal-
lier le manque d’extensibilité de certains mécanismes du noyau Linux. Elle a toutefois l’incon-
vénient d’augmenter la consommation mémoire de l’application. Nous aborderons donc dans
un troisième temps une proposition d’extension de la sémantique d’échange avec l’OS permet-
tant des gains substantiels de performance démontrés par notre prototype. Pour ce faire, nous
éliminerons l’obligation d’effectuer de coûteux effacements mémoires lors des fautes de pages
engendrées par les allocations auprès de l’OS. Il est ainsi possible de favoriser les approches
libérant plus régulièrement la mémoire vers l’OS. Comme la consommation mémoire devient
un problème majeur, nous donnerons dans un quatrième temps les résultats obtenus lors d’une
évaluation de la technique KSM (Kernel Samepage Merging) du noyau Linux. Cette dernière per-
met de fusionner les zones mémoire identiques et ainsi d’économiser la fraction de mémoire
associée. Cette extension sera testée avec le maillage d’une simulation numérique afin d’évaluer
sa capacité à réduire son empreinte mémoire.
La dernière partie clôturera ce document avec un bilan des travaux réalisés ainsi que des
perspectives ouvertes par ces derniers.
16
Première partie
Contexte
17
Chapitre 1
1.1 Introduction
Ce chapitre a pour but d’introduire les concepts fondamentaux ayant trait au domaine du
calcul haute performance (HPC), afin de disposer des éléments contextuels des travaux de cette
thèse. La première section rappellera l’historique de mise en place du HPC expliquant l’état
actuel des connaissances dans le domaine. Elle sera suivie de détails sur les méthodes de pro-
grammation des calculateurs actuels, et d’un état de la recherche sur les méthodes envisagées
pour les machines à venir. La mise en place de ces modèles sur les machines complexes actuelles
requiert une construction au-dessus d’un système d’exploitation chargé de gérer et d’abstraire la
ressource matérielle. La dernière partie donnera donc les points nécessaires à la compréhension
de la construction de cette couche logicielle particulière, à laquelle sont associés nos travaux sur
la gestion de la mémoire.
Très vite l’approche s’oriente vers une multiplication des composants en utilisant plusieurs
processeurs partageant une même mémoire dite partagée telle que le Cray-X/MP[ABHS89] de
1982 avec 4 processeurs. Un an plus tard (1985), le Cray-2 fonctionne à 283 Mhz soit 1.7 GFlops
pour 4 Go de mémoire, proche des ordres de grandeur de ce que l’on trouve dans nos téléphones
portables actuels. L’évolution des machines uniques à mémoire partagée se poursuit ainsi jus-
qu’au milieu des années 90 en utilisant jusqu’à 2048 processeurs (Hitachi SR2201)[FYA+ 97].
1. Contrairement aux processeurs dits scalaires, les processeurs vectoriels permettent d’appliquer simultanément
une opération sur un ensemble de valeurs contiguës en mémoire, dit vecteur.
19
Chapitre 1. Introduction au calcul haute performance
Avec un coût croissant de développement, les processeurs spécialisés pour le calcul scien-
tifique commencent à devenir un facteur limitant dans les années 2000. Certains se tournent
alors vers les marchés grands publics pour y trouver des processeurs moins adaptés, mais moins
chers, tels que ceux fabriqués pour les stations de travail plus classiques. Cette évolution pousse
donc à un retour du calcul scalaire, l’utilisation de vecteurs intéressant moins l’industrie du
PC. En terme de calcul scientifique, on observe dans ces années une divergence avec l’appari-
tion des grilles de calcul[FK99]. Cette approche est axée sur des calculs intrinsèquement pa-
rallèles et indépendants, utilisés principalement pour les analyses de données expérimentales,
notamment en physique des particules ou astrophysique. Pour ce type d’usage, chaque machine
traite les données d’une mini-expérience sans dépendance avec les autres. On évite ainsi la
contrainte des communications inter-nœuds qui, devenue inexistante, ne nécessite plus de pla-
cer l’ensemble des nœuds dans le même lieu ni de recourir à l’utilisation de réseaux rapides
onéreux. La communauté scientifique dispose aujourd’hui de projets à l’échelle nationale, tels
que Grid5000[CCD+ 05] ou mondiale avec la grille du CERN (WLCG)[Rob12]. De manière com-
plémentaire, le domaine des supercalculateurs se concentre autour des simulations à grandes
échelles et vise à répartir un calcul unique sur une part importante du supercalculateur. Ce
besoin maintient la nécessité de faire communiquer efficacement un nombre croissant de com-
posants.
Les années 2000 ont ainsi été marquées par la course au pétaflops avec une approche multi-
nœuds, multi-processeurs et multi-cœurs entraînant une envolée du nombre de cœurs. La barre
symbolique est franchie en 2008 par les Américains (DOE/IBM) avec Roadrunner [BDH+ 08] :
1.046 pétaflops pour 129 600 cœurs, dont une part d’accélérateurs de type Cell. Du côté français
(CEA/Bull), c’est Tera 100 qui franchit le pas en 2009 : 1.05 pétaflops pour 138 368 cœurs. La
barre symbolique du million de cœurs est atteinte fin 2012 par la machine Sequoia (DOE/IBM).
Cette évolution continue aujourd’hui avec 3.1 millions de cœurs pour le supercalculateur chinois
Thiane-2 (NUDT), offrant 33.8 pétaflops. La tendance se poursuit ; il nous faut donc appréhen-
der le développement de logiciels devant à l’avenir fonctionner sur des millions de cœurs.
L’histoire du HPC est ponctuée de tests de performances qui permettent de comparer les
capacités de calcul des machines dans le temps. À ce titre, le Linpack [Don88] sert de base au
classement mondial des 500 calculateurs les plus puissants[Top10]. L’évolution de ce classement
est donnée dans la figure 1.1 depuis 1993. On y observe bien une croissance régulière de la
performance des plus gros systèmes, les projections menant à estimer l’arrivée de l’exaflops aux
alentours de 2020.
20
1.3. Évolution actuelle des architectures
Ces concepts s’appliquent à l’exécution des instructions par le processeur, aux transferts mé-
moires ou aux échanges réseau. Idéalement, le débit devrait être favorisé pour maximiser les
performances en effectuant un maximum d’actions en un temps limité. Un programme est tou-
tefois conçu comme une suite d’actions dont certaines dépendent du résultat de la précédente.
Dans un tel contexte, la réduction de la latence est critique car elle contraint la capacité à exé-
21
Chapitre 1. Introduction au calcul haute performance
cuter rapidement l’action suivante, donc le débit d’exécution. L’ augmentation des fréquences
de fonctionnement est par exemple un moyen mécanique de gagner sur les deux postes. Ceci en
réduisant par définition la latence et en augmentant le débit. Nous verrons toutefois qu’elle a
aujourd’hui atteint ses limites au niveau de l’exécution des instructions.
Les échanges entre les composants physiques peuvent toutefois introduire des contraintes sur
ces débits et latences en fonction des capacités des liens utilisés pour les faire communiquer. Les
améliorations basées sur la sémantique d’échange entre composants sont malheureusement sou-
vent contraintes à favoriser l’un des deux points. Nous évoquerons indirectement ce problème
dans les sections qui suivent au vu des architectures exploitées dans les calculateurs actuels.
A 1 B1 C1 D1
A 2 B2 C2 D2
A 3 B3 C3 D3
A 4 B4 C4 D4
Temps
F IGURE 1.2 – Exemple de pipeline d’une instruction pouvant être découpée en 4 sous-étapes
(A,B,C,D). Grâce à cette méthode, il est possible d’exécuter 4 de ces instructions simultanément
sur le même pipeline sans avoir à dupliquer les unités de traitement associées. Le débit est ainsi
augmenté, mais la latence reste la même voir augmente si le découpage entraîne une exécution plus
lente.
22
1.3. Évolution actuelle des architectures
manière statique par le compilateur (architecture dite in-order) ou de manière dynamique par le
processeur (architecture dites out-of-order). Le réordonnancement dynamique des instructions
offre également un moyen efficace de réduire l’impact des latences d’accès à la mémoire. Ceci
en permettant au processeur d’exécuter dans l’intervalle les instructions disposant déjà de leurs
données.
Or, au début des années 2000, ces démarches atteignent leurs limites. Les fréquences se sta-
bilisent aux alentours de 3 GHz comme le montre la figure 1.3. Les raisons tiennent en partie à la
fin d’application de la loi de Dennart[DCK07]. La fin d’application de cette loi entraîne des pro-
blèmes de consommation électrique et de dissipation thermique non compensés par l’évolution
des finesses de gravure. De plus, l’évolution plus lente des technologies de stockage mémoire
creuse le fossé entre la vitesse de traitement d’une donnée et son temps d’accès en mémoire.
Les augmentations de fréquences sont donc rendues moins intéressantes, voir inefficaces. Ce
problème est connu sous le nom de mur de la mémoire depuis sa formalisation en 1995 par
Wulf[WM95]. D’un autre côté, l’exploitation du parallélisme d’instruction se heurte à une pro-
blématique de complexité croissante. Concernant l’allongement des pipelines, on observe ainsi
chez Intel, un pic à 30 niveaux pour les Pentium 4, contre 14 pour les Core 2 Duo qui suivent.
Avec des pipelines très longs, les opérations impliquant une purge de ces derniers deviennent
très pénalisantes avec un temps important de re-remplissage de ce dernier. Le réordonnance-
ment des instructions, lui, se trouve limité par les dépendances entre ces dernières, limitant les
gains au-delà d’un certain seuil.
Evolution du nombre de coeurs par sockets Evolution des fréquences des processeurs
16 10000
#1
14 Moyenne
12 1000
Fréquence en Mhz
Coeurs / sockets
10
8 100
6
4 10
2 Top500
SpecFP/SpecInt
0 1
1990 1995 2000 2005 2010 2015 1990 1995 2000 2005 2010 2015
Année Année
F IGURE 1.3 – Évolution du nombre de cœurs dans les processeurs et des fréquences à partir des
données fournies par Top500[Top10] et Spec[Hen06].
La loi de Moore étant toujours vérifiée, le nombre croissant de transistors est exploité, de-
puis le milieu des années 2000, pour offrir un nombre croissant de cœurs, chacun étant capable
d’exécuter son propre flot d’exécution. On retrouve donc à l’échelle du processeur, l’évolution qui
a eu lieu à l’échelle des calculateurs dans les années 1980. Dès lors, l’augmentation de perfor-
mance des nouveaux processeurs passe par une augmentation du nombre de cœurs, expliquant
l’explosion de leur nombre dans les supercalculateurs modernes. Cette tendance est bien visible
sur le graphique 1.3, mais risque d’être limitée par les phénomènes physiques survenant lorsque
les pistes deviennent trop fines. À long terme, cette approche a donc, elle aussi, de fortes chances
de devenir problématique.
23
Chapitre 1. Introduction au calcul haute performance
L’informatique a été marquée par l’évolution des processeurs au travers de grandes sociétés
telles que IBM, Intel, AMD, Cray et Fujitsu. Toutefois, l’essor du jeu vidéo a permis l’évolution
d’un marché parallèle avec le développement des coprocesseurs graphiques, composants spécia-
lisés dans le traitement d’images et vidéos. Avec le temps, ces composants massivement paral-
lèles, principalement développés par les sociétés Nvidia et ATI/AMD, ont atteint des paramètres
(coûts, performance et consommation énergétique) les rendant attractifs pour le domaine du
HPC. Les constructeurs sont passés des GPU (Graphical Processing Unit) à des conceptions vi-
sant une utilisation plus générique dite GPGPU (General Purpose Graphical Processing Unit). Ces
architectures offrent des possibilités pour le calcul scientifique de par leur conception plus vec-
torielle, dédiée à l’application de traitements sur de grands volumes de données. Les processeurs
conventionnels sont habituellement conçus pour minimiser les latences d’accès aux données et
donc, principalement optimisés pour des codes séquentiels. En comparaison, ces coprocesseurs
sont spécialisés pour maximiser les débits et traitements parallèles au prix de la latence. Cela
suppose des codes massivement parallèles et peu dépendants de la latence pour les exploiter.
Ces approches technologiques ont notamment l’intérêt d’apporter une démarche intéressante
de modèles de programmation (CUDA[Buc07] OpenCL[SGS10] ...) qui forcent le développeur
à exprimer ses traitements sous une forme parallèle. On trouve plusieurs des calculateurs du
TOP500 équipés de ces coprocesseurs (notamment le premier du classement en novembre 2012 :
Titan). Ces approches présentent toutefois une rupture technologique qui nécessite la réécriture
des codes existants. Ceci complique le choix de migration vers cette technologie. Le besoin d’une
présence de processeurs classiques pour les contrôler rend également la prise en main de ces en-
vironnements hybrides d’autant plus délicate.
Les langages tels que CUDA et OpenCL ont toutefois de fortes contraintes qui ne permettent
pas d’exprimer aisément tous les algorithmes actuellement exploités sur processeurs convention-
nels. La migration vers ces architectures doit donc pour l’instant être réfléchie en fonction de la
fraction d’étapes adaptées à ces architectures. Remarquons que les fabricants de GPU tendent
aujourd’hui à complexifier leurs composants pour supporter une sémantique plus vaste et donc,
élargir la gamme de problèmes accessibles au travers de ces outils. À l’opposé, certains proces-
seurs généralistes tendent vers une certaine simplification pour augmenter leurs performances
parallèles et tendent, d’une certaine manière, à se rapprocher des GPGPU. C’est notamment le
cas du nouveau coprocesseur Xeon-Phi, actuellement mis en œuvre par Intel et présent dans les
supercalculateurs Tianhe-2 et Stampede lancés en 2012 et 2013. D’une manière générale, les
algorithmes doivent donc être pensés ou repensés pour prendre en compte des architectures,
qui de toute façon, deviennent massivement parallèles.
Le pétaflops ayant été atteint en 2009, les avancées s’orientent désormais vers l’objectif de
l’exaflops, estimé aux alentours de 2020 si la tendance actuelle se poursuit. Il convient toutefois
de noter que cette évolution présente un certain nombre de défis importants qui nécessitent
des efforts soutenus. Les gains nécessaires ne pourront en effet être apportés par une simple
juxtaposition à l’infinie de composants bien maîtrisés. En effet, si l’on s’en réfère à certaines
études [DBa11], l’exaflops pose de sérieuses questions en ce qui concerne les points listés ici.
24
1.4. Les défis de l’Exaflops
L’exaflops ne pourra pas être atteint en poursuivant une augmentation de ces consomma-
tions, tant pour des raisons financières que pratiques. Il faut pour cela compter sur une multipli-
cation par 1000 des performances pour une augmentation de consommation de quelques unités.
Des limites de l’ordre de 20-30MW[TC12] sont considérées par certains comme un problème
pratique et financier. Il importe donc d’utiliser des composants plus efficaces énergétiquement,
voir des programmes eux-mêmes optimisés pour tenir compte des aspects énergétiques. Cela se
traduit par l’apparition récente d’un nouveau classement, le Green500[SHcF06] prenant pour
critère l’efficacité énergétique des calculateurs.
Sur le plan technique, la dissipation thermique des processeurs est fortement liée à leur
fréquence de fonctionnement. Ce paramètre devient donc un levier important pour la maî-
trise de la consommation. Pour le programmeur, cela signifie une réduction des fréquences de
fonctionnement, donc une nécessité d’exploiter le parallélisme pour maintenir les performances
des programmes existants. Les nouveaux Xeon-Phi d’Intel, utilisent par exemple une fréquence
de 1.6 GHz, bien inférieure aux 3 GHz des Xeon utilisés sur les calculateurs actuels du CEA :
Tera100 et Curie. En compensation, ce coprocesseur offre 60 cœurs capables d’exécuter jus-
qu’à 240 threads contre 8 cœurs et 16 threads (si hyperthreading activé) pour les processeurs de
Tera100 et Curie. Certains voient plus loin et avancent qu’il sera nécessaire dans un futur proche
de désactiver les transistors inutilisés parfois appelés dark silicon[EBSA+ 12].
Les marchés actuels tendent également à favoriser la production d’appareils mobiles aux dé-
pens du PC classique. A moyen/long terme, il est donc probable que les technologies exploitées
en HPC devront s’adapter à cette évolution du marché en réutilisant ses technologies fortement
rentabilisées.
1.4.2 La mémoire
La mémoire est par construction un composant extensif puisque l’augmentation de capacité
est directement reliée au nombre de transistors. Les technologies dites DRAM (Dynamic Random
Access Memory) actuellement employées nécessitent en effet un rafraîchissement[Dre07] régu-
lier de leur contenu et donc, un coût énergétique proportionnel à la capacité de stockage. Ce
facteur devient donc un paramètre d’optimisation de la consommation électrique des calcula-
teurs tendant à limiter l’augmentation de l’espace mémoire des supercalculateurs. De plus, ces
25
Chapitre 1. Introduction au calcul haute performance
mêmes technologies n’évoluent pas à la même cadence que les processeurs. En l’état, l’augmen-
tation du nombre de cœurs va donc avoir tendance à augmenter plus rapidement que la quantité
de mémoire. Ceci, pour des raisons tant énergétiques, que de contrainte de volumes physiques.
Pour le programmeur, cela signifie moins de mémoire par cœur, donc un besoin d’une atten-
tion plus grande sur ces aspects qui s’étaient estompés avec le temps. D’autre part, cela exclut
la possibilité de reposer sur une extensibilité faible 2 stricte pour tirer parti du parallélisme. Le
sous-problème traité par cœur doit en effet se réduire (ou être réorganisé) en proportion de
la mémoire disponible. Les bibliothèques et l’allocateur mémoire lui-même doivent donc être
construits de manière à pouvoir limiter leur empreinte mémoire. Il en résulte un besoin de ré-
évaluer les compromis réalisés dans leur conception. Nous verrons que cela impacte également
les modèles de programmation envisageables pour ces architectures. Remarquons que la mé-
moire totale continuera quant à elle à augmenter, même si ce n’est pas en proportion du nombre
de cœurs. Or, le coût de gestion d’un octet mémoire par l’OS est lui, plus ou moins constant (à
fréquence fixe). Il importe donc de remarquer que la problématique liée aux méthodes de ges-
tion de cette ressource est donc vouée à prendre une importance croissante. Ce point peut donc
devenir un problème majeur pour exploiter le gain de capacité de traitement des processeurs s’il
n’exploite pas les gains de parallélisme.
Le problème sera discuté plus en détail dans la suite, mais le nombre croissant de cœurs
à alimenter en données oblige les architectures à devenir très hiérarchisées pour distribuer les
contentions d’accès à la mémoire. Ce facteur structurel complique le développement des pro-
grammes en introduisant des dépendances sur des paramètres architecturaux en pleine évolu-
tion.
Ce point impacte l’ensemble des codes utilisés, du système d’exploitation aux codes appli-
catifs eux-mêmes. Dans ce contexte, il est nécessaire de revisiter le fonctionnement de certains
aspects systèmes. Nous nous intéresserons donc à la pile de gestion de la mémoire afin de
prendre en compte ces nouvelles contraintes.
1.4.4 Pannes
Une telle augmentation du nombre de cœurs rend difficile le débogage des applications, du
fait de l’interaction d’un nombre trop important de tâches ne pouvant plus être naïvement énu-
mérées de manière lisible par le programmeur. D’autre part, l’utilisateur fait face à un problème
statistique. Considérant une chance de panne fixe pour un composant, il est clair qu’une multi-
plication de ces derniers augmente les chances de pannes de l’un d’entre eux. Ceci vaut pour le
2. L’extensibilité faible est une méthode qui consiste à profiter du supplément de parallélisme pour traiter un
problème plus grand (en proportion du nombre d’unités de traitement supplémentaire).
26
1.5. Environnement de calcul de la thèse
matériel comme pour les logiciels. Les défauts ont donc tendance à produire de plus en plus ra-
pidement un plantage des applications. Il en résulte un besoin de fiabiliser ces composants (tant
logiciels que matériels). Le cas extrême consiste à rendre les programmes tolérant aux pannes.
L’état actuel des connaissances implique toutefois que la panne d’un seul composant (logiciel ou
matériel) a de grandes chances d’entraîner un plantage de l’ensemble du programme.
1.4.5 Entrées/sorties
La problématique liée à l’évolution lente des performances des mémoires vaut également
pour les supports de stockage à long terme (disques durs, bandes...) qui restent très en deçà
des capacités de transfert nécessaires pour alimenter les processeurs actuels. L’utilisation de ces
supports doit donc limiter l’impact sur les performances. On notera que la tolérance aux pannes
est actuellement gérée dans les programmes par le biais des méthodes de reprise sur écriture.
Ces dernières procèdent par écriture régulière de l’ensemble de l’état d’un programme sur un
système de fichier partagé, en général l’ensemble ou une partie de sa mémoire. La reprise peut
alors être réalisée en rechargeant cet état en mémoire. Cette approche a toutefois le défaut de
générer un flux important de données, tant en débit qu’en volume.
1.4.6 Résumé
D’une manière générale, la complexité croissante des architectures dont on dispose est liée
en partie à l’augmentation du nombre de composants, mais aussi à l’application cumulée des
diverses approches historiques. Les architectures récentes exploitent en effets beaucoup de tech-
nologies maîtrisées par le passé (programmation vectorielle, mémoires partagées, mémoires dis-
tribuées...). Les nouvelles difficultés proviennent donc de leur utilisation simultanée à grande
échelle. On remarquera également les contraintes importantes liées à la gestion des données
(stockage et transfert) qui tendent à orienter les développements actuels. Dans ce cadre, cette
thèse s’intéresse aux méthodes de gestion de la ressource mémoire tant que niveau du système
d’exploitation que des bibliothèques système en espace utilisateur. Nous reviendrons plus en dé-
tail sur les points structurels associés à cette problématique dans le chapitre suivant (2).
Cette thèse a été réalisée au centre CEA de Bruyères-le-châtel, site regroupant l’essentiel des
moyens de calcul du CEA, notamment par le biais du centre lui-même (pour les calculs clas-
27
Chapitre 1. Introduction au calcul haute performance
D’autres travaux plus annexes ont également pu avoir lieu sur certains calculateurs proto-
types du CEA offrant de l’ordre de 900 cœurs avec des structures proches des architectures
listées précédemment. Sont également à ajouter les nœuds prototypes mis à disposition par le
projet PerfCloud[Per12]. Ces derniers fournissent des coprocesseurs Intel Xeon-Phi sur lesquels
nous avons pu réaliser quelques évaluations de performance du noyau Linux.
TABLE 1.1 – Structure synthétique des nœuds de calcul utilisés lors des développements de cette
thèse. Sont donnés, par nœud : le nombre de processus, de cœurs total, la structure NUMA et la
mémoire disponible. Tera100 et Curie sont respectivement des calculateurs pétaflopiques classés au
Top500 avec respectivement 1.05 pétaflops (138368 cœurs) et 1.36 pétaflops (77184 cœurs).
Tous ces systèmes sont opérés sous système d’exploitation Linux (Redhat 6, noyau 2.6.32).
Notre étude prendra donc Linux comme OS principal bien que considérant les approches Unix
d’une manière plus générale. En ce qui concerne les parties matérielles, nous nous intéresse-
rons principalement aux architectures de type x86_64 fournies par Intel sous la forme de nœuds
NUMA agrégeant jusqu’à 16 processeurs (nœuds de 128 cœurs) grâce à la technologie d’inter-
connexion BCS (Bull Coherence Switch) développée par Bull.
28
1.7. Modèles de programmation
Données PU PU PU
Données
Données
Données
PU PU PU
PU PU PU
PU PU PU
PU PU PU
F IGURE 1.5 – Illustration des modèles d’exécution établis par la classification de Flynn (schémas
extraits de Wikipedia[wik]).
SIMD (Single Instruction Multiple Data) : L’une des extensions du modèle très présente en
HPC, elle correspond à la notion de calcul vectoriel où une instruction unique est appliquée
à un ensemble contigu de données. Ce modèle permet de réduire le coût de décodage
des instructions à répéter sur des ensembles de données et d’optimiser leurs transferts
mémoires. Il est aujourd’hui concrétisé à grande échelle dans l’architecture des GPU et
sous forme d’extension avec les normes SSE, AVX 4 et équivalents de la famille x86.
MISD (Multiple Instruction Single Data) : Ce modèle n’a pas d’implémentation pratique re-
connue même si certains auteurs[DL95] considèrent que les pipelines peuvent être consi-
dérés comme tel.
MIMD (Multiple Instruction Multiple Data) : Plusieurs instructions sont traitées simultané-
ment, chacune, sur des données différentes. C’est le modèle principal des architectures
modernes. On notera qu’il peut s’appliquer en utilisant des mémoires partagées (SPMD :
Single Program Multiple Data) ou distribuées (MPMD : Multiple Program Multiple Data).
Comme discuté, les calculateurs actuels exploitent un mode hybride en mixant ces deux
approches sous la forme de grappes de nœuds multicœurs.
Compilateur
Modèle de Machine
Langage
programmation opérationnelle
Support
exécutif
F IGURE 1.6 – Illustration de passage du modèle abstrait de programmation à une exécution sur
machine réelle en passant par une expression formalisée du besoin.
4. SSE et AVX sont des normes d’extensions permettant le calcul vectoriel sur les processeurs Intel et AMD pour-
tant centrés sur un fonctionnement scalaire.
29
Chapitre 1. Introduction au calcul haute performance
Il en résulte une forme de compromis impliquant une tendance à limiter l’évolution brutale
des langages. Actuellement, les modèles de programmation des architectures parallèles tendent
donc à se concrétiser sous la forme de bibliothèques de fonctions ou d’extensions de langages
existants. Dans le domaine du HPC, on trouve principalement C, C++ et Fortran. Les modèles
de programmation parallèle tendent donc à se concrétiser autour de ces derniers. Une autre
approche consiste à introduire des directives de compilation, des mots clés ajoutés au langage
permettant d’activer, si supporté, des extensions du compilateur pour que ce dernier modifie
le code source. En C, C++ et Fortran, il s’agit de la notation portée par le mot clé #pragma
qui est ignoré si le compilateur ne supporte pas l’extension associée. Ces formalismes doivent
abstraire le fonctionnement détaillé du matériel, ils reposent donc sur un modèle plus abstrait
de la machine. Nous allons donc voir les deux modèles mémoires dominants exploités en HPC.
F IGURE 1.7 – Illustration de passage du modèle abstrait de programmation à une exécution sur
machine réelle en passant par une expression formalisée du besoin.
Le modèle complémentaire dit à mémoire distribuée tente donc de régler ces problèmes en
distribuant la mémoire entre les unités de traitement. La contention sur le bus est ainsi élimi-
née. Les échanges entre les unités sont toutefois transformés, d’un mode implicite vers un mode
explicite, au travers de la gestion d’un réseau déléguée à l’utilisateur ou aux supports exécutifs.
Ces architectures sont habituellement exploitées sur la base d’échanges de messages : modèle
30
1.7. Modèles de programmation
dit MP (Message Passing) dont nous verrons la concrétisation dans la prochaine section.
Ce point a déjà été abordé précédemment, mais rappelons que les calculateurs actuels mixent
ces deux approches en utilisant des grappes de nœuds multicœurs. Les nœuds sont donc à
programmer sur la base de modèles à mémoire distribuée par échange de messages. Les cœurs
internes aux nœuds sont idéalement à programmer sur la base de modèle à mémoire partagée.
Remarquons toutefois que les modèles à mémoire distribuée représentent une vue plus abstraite,
pouvant tout à fait être exécutée sur des machines à mémoire partagée.
Dans les systèmes d’exploitation modernes, un processus est une instance d’une application
composé : d’un code programme à exécuter et d’un ensemble de ressources en cours d’utili-
sation (mémoire, fichiers, connexions...). Un processus contient au minimum un flux d’exécu-
tion. Chaque processus est isolé et n’utilise que ses propres ressources, sauf demande explicite
d’échanges au travers du système d’exploitation. Cette notion de processus correspond donc bien
à une programmation en mémoire distribuée. En dehors du projet MPC que nous discuterons
plus loin, les implémentations MPI traditionnelles se construisent en établissant une correspon-
dance unique entre tâche et processus.
31
Chapitre 1. Introduction au calcul haute performance
Dans le cadre de la simulation numérique, le modèle MPI est souvent utilisé pour faire de
la décomposition de domaine. Chaque tâche MPI a la charge d’une portion du maillage utilisé
pour le calcul. Les mailles en bordure des domaines voisins doivent être répliquées (mailles
fantômes), car nécessaires aux calculs locaux. MPI est donc utilisé pour synchroniser leurs va-
leurs par échanges de messages, comme cela est visible sur la figure 1.8. Cette approche a pour
contrepartie une surconsommation mémoire induite par la présence des mailles fantômes qui,
dans le cas de simulation 3D, peut devenir non négligeable. Avec le nombre croissant de cœurs,
le modèle MPI, utilisé seul et implémenté à base de processus, pose donc trois problèmes qui
deviennent des facteurs limitant à grande échelle :
Duplication de données : sur une architecture à mémoire partagée, les implémentation MPI à
base de processus imposent la duplication de certaines données (mailles fantômes, tables
de constantes physiques...), qui, sans cela, ne seraient pas nécessaires sur ces architectures.
Cette approche, devient donc limitante dans un contexte où la quantité de mémoire par
cœur tend à la stabilisation, ou réduction.
Communications inter-nœuds : MPI doit établir et maintenir des connexions entre les tâches
qui échangent des données. Cela implique des connexions au niveau du système d’exploi-
tation et la mise en place de tampons mémoires pour les communications. Avec un nombre
croissant de cœurs, le nombre de tampons et de connexions établies par certains schéma
de communications va de manière croissante sur chaque nœud, finissant par poser pro-
blème pour des raisons de consommation mémoire, mais aussi du fait de limites sur le
nombre de connexions autorisées par l’OS et le support matériel des cartes.
Communications intra-nœud : Bien que le modèle MPI fonctionne parfaitement sur les archi-
tectures à mémoire partagée, il importe de noter que le fonctionnement basé sur l’échange
de messages est sous-efficace par rapport à ce que peuvent offrir ces architectures. Ces
échanges nécessitent en effet des recopies de données, qui, sinon, ne seraient pas né-
cessaires. Il existe bien sûr des techniques d’optimisations allant dans ce sens[PCJ09,
BMG07], mais le problème de fond demeure.
32
1.7. Modèles de programmation
Les spinlocks sont construits à l’aide d’instructions atomiques et permettent de protéger des
sections critiques de code constituées de plusieurs instructions. Ils fournissent un méca-
nisme d’attente active, une forte réactivité, mais consomment le temps de calcul au lieu
de le partager. Ils sont disponibles à partir d’interfaces de programmation (API) standard
telles que pthread.
Les mutex sont des verrous logiciels offerts par le système d’exploitation ou certaines biblio-
thèques parallèles. Ces derniers permettent de rendre la main à une autre tâche lorsqu’ils
sont bloqués, en permettant un meilleur partage de la ressource de calcul. La contrepartie
est un coût supérieur et une réactivité moins importante.
Sur les OS de la famille Unix, l’utilisation standardisée des threads repose sur l’interface
pthread définie par la norme POSIX 5 . Cette interface est toutefois destinée à une manipulation
très orientée système, mais, peu adaptée à la parallélisation de simulation numérique, rendant
son utilisation fastidieuse. À l’heure actuelle, on préfère donc utiliser des directives de compi-
lation permettant d’exprimer le parallélisme de manière plus abstraite et déléguer une partie
du travail au compilateur. On trouvera notamment les normes de directives OpenMP et HMPP
comme extension des langages existants C,C++ et Fortran. Ces directives offrent l’avantage
d’introduire simplement la création de threads dans un programme existant et la possibilité de
maintenir le fonctionnement originel du programme si ces dernières sont ignorées. Un exemple
de parallélisation de boucle en OpenMP est donné dans le code 1.1. Ces approches ont l’intérêt
de permettre une transition en s’appliquant sur des codes existants avec un nombre réduit de
changements. La contrepartie est une sémantique restreinte par la nécessité de maintenir un
code fonctionnel lorsque leur interprétation est désactivée.
En pratique, l’utilisation de ces technologies prend pour l’instant la forme d’un duo proces-
seur généraliste associé à un coprocesseur spécialisé nécessitant une programmation hybride
de façon à faire fonctionner chaque portion de code sur l’architecture la plus adaptée. Ce type
d’approche ajoute toutefois la difficulté de gérer explicitement le transfert des données entre
les différents modules de calcul. On trouve pour cela de nombreux travaux de recherche autour
d’environnement d’exécution prenant en charge le besoin d’équilibrage hybride : StarPU[AN09],
5. POSIX : Portable Operating System Interface est une norme visant à standardiser l’interface avec les systèmes
d’exploitation. Elle est reprise par la plupart des Unix.
33
Chapitre 1. Introduction au calcul haute performance
StarSS[ABI+ 09], XKaapi[GFLMR13] ou les études similaires conduites dans le cadre du projet
MPC[JYV12]. Des langages à base de directives sont en cours de mise au point pour générer
des codes GPU à partir de codes existant sur une base de directives de compilations : HMPP et
OpenACC.
1.7.7 Résumé
Nous venons de voir qu’il existait différentes manières d’aborder l’expression du parallélisme
sur les architectures actuelles. Il semble qu’il existe actuellement un certain goût pour une prise
en charge au niveau langage, à base de directives ou d’extension plus profonde de langages
existants. Ces dernières approches permettent une vision plus abstraite et plus simple pour le
programmeur. Remarquons que les approches initiales MPI et pthread tendent ainsi à devenir
les éléments sous-jacents d’approches plus abstraites visant à automatiser l’utilisation de ces ou-
tils. En terme de production, OpenMP devient un standard relativement adopté pour remplacer
l’interface pthread sur les systèmes à mémoire partagée. Toutefois, en mémoire distribuée, MPI
reste pour l’instant, l’outil principal utilisé dans les codes de calculs. L’important ici est de noter
la tendance vers une expression à base de thread qui entraîne les problèmes traités dans cette
thèse.
34
1.7. Modèles de programmation
MPC a également l’originalité de fournir une implémentation MPI basée sur les threads[PCJ09]
au lieu des processus. Il est ainsi possible de faire fonctionner une application préexistante uni-
quement MPI dans un mode multithread par simple recompilation. Ceci permet de réduire cer-
tains problèmes liés aux implémentations MPI à grande échelle (consommation mémoire de
la bibliothèque, nombre de processus à lancer et à connecter, efficacité des communications
intra-nœud). Ceci permet également d’aider la transition de codes existants vers un mode de
programmation hybride MPI+X avec X un modèle de programmation à base de thread. La fi-
gure 1.9 donne un exemple d’exécution dans ce mode couplé à une utilisation d’OpenMP. MPC
fournit dans les grandes lignes :
– Une implémentation de threads utilisateurs qui respecte la topologie physique de la ma-
chine par contrôle de leur placement physique.
– Un support-exécutif MPI basé sur la notion de thread plutôt que processus.
– Un support-exécutif pour OpenMP exploitant les threads utilisateurs de sorte à obtenir un
mélange équilibré avec le support exécutif MPI.
– Un compilateur modifié (GCC) pour le support d’OpenMP et l’exploration d’extensions
telles que la privatisation automatique de variables ou les HLS (Hierachical Local Sto-
rage)[TCP12].
– Un débogueur modifié (GDB) prenant en charge explicitement les threads utilisateurs.
35
Chapitre 1. Introduction au calcul haute performance
Thread sys. Thread sys. Thread sys. Thread sys. Thread sys. Thread sys.
F IGURE 1.9 – MPC exécuté sur un cluster composé de deux nœuds NUMA bicœurs en considérant
une tâche MPI par nœud NUMA et deux threads OpenMP pour chaque tâche MPI. Remarquons
que contrairement à OpenMPI, les deux tâches partagent bien le même espace d’adressage en étant
exécutées dans le même processus.
– Un allocateur mémoire parallèle supportant explicitement les hiérarchies NUMA, qui est
l’objectif de cette thèse.
D’un autre côté, les simulations numériques profitent de l’augmentation de performance pour
exploiter des modèles physiques plus complexes et les coupler. Cela conduit à une complexifica-
tion des codes de simulation : code multi-physiques, multi-matériaux, raffinement de maillages,
couplage de solveurs... Dans l’attente d’obtenir un hypothétique modèle généraliste, on peut se
demander s’il n’est pas intéressant d’explorer une approche à base de langages spécialisés (DSL :
Domain Specific Language), de façon à construire une expression adaptée aux différents types de
problèmes.
La construction d’un DSL passe par la formalisation des concepts nécessaires à la résolution
du problème ou de la classe de problèmes visés. D’une certaine manière, le langage va alors ”ab-
sorber“ l’expérience pratique de ses concepteurs. L’idée n’est pas ici de tomber dans le travers
des systèmes experts, mais d’extraire la notion sémantique importante. On peut ainsi permettre
une meilleure collaboration entre l’humain et la machine, voir également entre les humains. En
suivant cette démarche, chaque équipe ou groupe d’équipes exprime son besoin particulier, avec
les biais que cela implique. Dans un second temps, on peut alors espérer parvenir à extraire les
points communs des différents DSL pour construire des langages plus généraux tenant compte
des différentes problématiques et idées émergentes. Cette construction peut alors se faire de
manière croissante, passant de sous-domaine particulier à des ensembles plus vastes, favorisant
au passage, l’échange de points de vue entre les domaines respectifs. À noter que rien n’interdit
l’empilement de DSL, chacun traitant des problèmes rencontrés aux différents niveaux d’abs-
36
1.9. Le système d’exploitation
traction. Mener cette démarche jusqu’à l’interface d’expression de la physique des simulations
permettrait, certainement de découpler au mieux le travail du physicien et de l’informaticien,
en assurant une interface d’échange saine et clarifiée entre ces domaines. Trouver des langages
se situant à mis-chemin entre ces deux spécialités serait également un moyen de faciliter les
échanges entre les personnes de ces domaines respectifs. Il semble en effet désormais important
de ne pas se limiter aux expertises extrêmes, toujours nécessaires, mais employant des vocabu-
laires trop différents parfois nuisibles aux échanges inter-disciplinaires.
Le grand public a souvent entendu parler des OS historiques : DOS, Windows et Mac OS. Il
est toutefois important de remarquer que le domaine du HPC a lui, une longue tradition d’utili-
sation de la famille Unix, plus industrielle. On y observe également les OS ayant historiquement
mis en place les concepts fondamentaux au cœur de la constitution de ces outils logiciels. Vis-à-
vis des mécanismes de gestion mémoire, on notera la forte influence des OS développés pour le
calculateur Atlas[KELS62] (1962) et le système Multics[BCD69] (1969) dédié aux calculateurs
de Burroughs Corporation.
On remarquera toutefois le tournant observé une fois de plus en 2000, avec l’arrivée de Linux
dans les calculateurs du Top500. Cet OS de type Unix initié par Linus Torvald a été développé
dans le mouvement open source de manière indépendante et est aujourd’hui répandu chez le
public confirmé, dans les serveurs Web, nos téléphones et télévisions. Dans le domaine du HPC,
il équipe plus de 50% des configurations du Top500 depuis 2004 avec un seuil actuel voisin
de 80%. L’utilisation de cet OS offre l’avantage d’un accès pratique à ses sources pour modifi-
cation, ainsi qu’une communauté active et une vaste gamme de logiciels et supports matériels.
Il faut toutefois remarquer qu’il n’est pas développé spécifiquement pour le HPC. Avec l’aug-
mentation massive du nombre de cœurs, certains problèmes sont donc rencontrés de manière
pionnière par ce domaine et nécessitent certains efforts d’amélioration, notamment vis-à-vis des
problèmes dits d’extensibilité sur un nombre de cœurs toujours croissant.
Dans le cadre de cette thèse, nous nous intéressons essentiellement aux problématiques liées
à la gestion de la mémoire, tant au niveau des décisions prises par l’OS que celles prises par les
bibliothèques systèmes servant d’interface entre l’OS et les langages de type C, C++ et Fortran.
Le dernier point est celui qui nous intéresse plus particulièrement dans ce document, essen-
tiellement vis-à-vis de la fonction malloc au cœur des méthodes d’allocation dynamique de ces
37
Chapitre 1. Introduction au calcul haute performance
langages. Avec l’évolution vers le multicœur il devient en effet nécessaire de revisiter les com-
promis des mécanismes exploités par cette fonction. Nous étudierons donc ces points vis-à-vis
des architectures parallèles multicœurs d’aujourd’hui et de l’évolution des modèles de program-
mation utilisés pour les exploiter. Les méthodes de gestion mémoire des OS seront traitées en
détail dans le prochain chapitre.
En complément, nous validerons nos méthodes d’allocation avec un code plus conséquent en
terme de taille et de complexité. Hera[Jou05] est une plateforme de simulation multi-physiques
multi-matériaux opérants sur maillage de type AMR (Adaptive Mesh Refinement). Ce type de
maillage exploite des techniques de raffinement dans les zones du maillage contenant des géo-
métries plus complexes ou ayant des termes aux dérivées élevées. Cette approche permet de
traiter des problèmes plus fins sans payer le prix parfois trop élevé d’un raffinement du maillage
complet. La contrepartie de ces approches est une complexification des méthodes numériques et
une génération d’un nombre plus important d’allocations mémoires. L’application Hera dispose
d’un parallélisme de type MPI. L’utilisation d’un maillage AMR dans ce type de contexte tend
également à complexifier les échanges et générer des problèmes d’équilibrage de charge entre
processus. Ceci fait de cette application un bon cas d’étude en fournissant un cas concret de réso-
lution de problème représentatif des codes de production en complément des micro-benchmarks.
Dans les deux cas, les études en mode multithreads seront réalisées en utilisant le support
exécutif MPC décrit en section 1.7.9. L’exploitation de sa capacité à exécuter chaque tâche MPI
en tant que thread plutôt que processus permet en effet de convertir rapidement des applications
MPI en applications multithreads.
1.11 Conclusion
Nous venons de voir dans ce chapitre que le domaine du HPC a connu une forte évolution
en terme architecturale depuis ses commencements. Au cours des années 2000, les limites tech-
nologiques ont poussé les constructeurs à s’orienter vers une stratégie menant aux calculateurs
massivement parallèles d’aujourd’hui. Les contraintes de conception des calculateurs devant
nous conduire à l’exascale vont poursuivre cette évolution en amplifiant les échelles d’exploita-
tion. Dans ce contexte, les modèles de programmation utilisés et les outils logiciels (OS, biblio-
thèques...) sont mis à rude épreuve et doivent prendre en compte ce nouveau paradigme. Pour
ce faire, il importe d’exploiter des algorithmes passant à l’échelle en terme de performance et de
consommation mémoire.
C’est dans ce cadre que cette thèse s’intéresse au sous-ensemble que constituent les méca-
nismes de gestion de la mémoire tant au niveau de l’OS que de la fonction utilisateur malloc
définit par le langage C. L’étude est notamment conduite pour ré-évaluer le fonctionnement de
ce composant vis-à-vis d’un parallélisme massif à base de threads et des caractéristiques propres
aux simulations numériques. Nous verrons notamment que les simulations tendent à utiliser des
38
1.11. Conclusion
tailles d’allocation qui leur sont propres (grands tableaux). Ce type d’allocation peut nécessiter
un travail autre que les nombreuses allocations de petite taille des applications habituellement
étudiées dans le domaine de la gestion mémoire. Nous discuterons donc largement cette spéci-
ficité.
39
Chapitre 1. Introduction au calcul haute performance
40
Chapitre 2
Gestion de la mémoire
2.1 Introduction
Si un ordinateur est avant tout une machine à calculer, il est important de noter qu’il doit
être alimenté par des données. Ces dernières doivent être identifiables et accessibles efficace-
ment. D’autre part, un ordinateur ne peut stocker qu’une quantité finie de données dans sa
mémoire. Il importe donc de gérer le cycle de vie de ces dernières et leur arrangement dans l’es-
pace de stockage dédié. S’ajoute à cela un besoin de partager la ressource mémoire entre divers
programmes. Dans ce chapitre, nous rappellerons les concepts fondamentaux ayant trait à la
gestion des données par le système d’exploitation, notamment en ce qui concerne la construction
des espaces d’adressage.
Ce chapitre introduira les concepts fondamentaux liés à la gestion de la mémoire dans les
OS modernes. Nous traiterons dans un premier temps de la constitution de l’espace d’adressage
virtuel, de l’isolement des différents composants logiciels et de la méthodologie de partage de
la ressource mémoire. Nous pourrons alors étudier plus en détail l’interface d’échange entre
l’OS et les applications pour permettre d’effectuer des requêtes mémoires. Nous terminerons
enfin par une description des mécanismes mis en œuvre pour distribuer la mémoire au sein
des applications et bibliothèques en espace utilisateur. Après l’introduction des principes de
gestion des données, nous rappellerons dans une dernière section que l’accès aux données peut
être affecté par certaines contraintes sur les processeurs modernes. Nous décrirons donc les
méthodes d’accès à la mémoire pouvant impacter les décisions de l’allocateur. Pour ce faire, nous
aborderons principalement la notion d’associativité des caches du processeur et les mécanismes
de traduction d’adresses. Ces concepts seront essentiels pour comprendre la première partie de
nos travaux.
41
Chapitre 2. Gestion de la mémoire
peut sans difficulté travailler dans un espace d’adressage unique partagé avec le système d’ex-
ploitation, c’est donc la méthode retenue dans les premiers temps. Or, certains systèmes per-
mettent d’exécuter plusieurs programmes simultanément[Tan05, Han73]. Ce type d’exécution
est rendu possible par la présence de plusieurs processeurs/cœurs ou par l’utilisation d’un
mode dit interruptible, exécutant tour à tour chaque programme pendant un laps de temps
déterminé[Lor72, GCO65]. Le système de la machine Atlas[KELS62] offrait par exemple un
mode interruptible. Ces techniques rencontrent toutefois certaines limitations que l’on peut dé-
crire comme suit.
Problème de relocalisation : lorsque les programmes sont compilés, leur code est conçu pour
être chargé à une adresse fixe. Il en va de même pour certains éléments tels que les
constantes, les variables globales, la pile 1 , etc... Si l’on dispose d’un espace d’adressage
unique, relancer plusieurs fois un tel programme est alors impossible sans obtenir une
superposition des bandes d’adresses utilisées par ce dernier. On doit donc recompiler le
programme pour le lancer plusieurs fois, ou passer par la complexité de génération d’un
code relocalisable 2 . Ce problème est déjà présent en 1965 chez IBM[McG65].
Problème de sécurité, robustesse : dans une telle organisation, les programmes ont accès à
toute la mémoire et peuvent donc lire ou corrompre les données d’autres programmes
voir du système d’exploitation lui-même. Ce problème se pose en cas d’attaque de la part
d’un utilisateur malveillant ou d’un bogue entraînant l’utilisation non prévue de zones
mémoires réservées à un autre usage.
Il est possible de traiter le premier problème en modifiant les programmes générés au prix
d’une complexification des compilateurs, éditeurs de lien et lanceurs de programmes. Aujourd’hui,
c’est toutefois une autre approche qui est retenue, réglant le second point du même coup. Elle
est détaillée dans ce qui suit.
Depuis, les architectures modernes disposent toutes d’au moins deux types d’adressage au ni-
veau matériel. L’adressage physique fait correspondre les adresses à la position des données dans
la mémoire centrale. L’adressage virtuel, plus abstrait, fournit des adresses qui n’ont pas de cor-
respondances directes avec la mémoire centrale. L’utilisation d’un système d’adresses virtuelles
offre plusieurs avantages du point de vue de l’OS et des applications.
Efficacité de gestion : Cette approche permet de disposer d’un espace d’adressage couvrant
toute la plage accessible pour une taille d’adresse donnée (32 bits ou 64 bits par exemple).
Ceci offre un espace beaucoup plus grand que l’espace physique qui est naturellement res-
treint à la taille de la mémoire disponible. Disposer de ce grand espace permet de gérer
plus simplement et plus efficacement le placement des différents objets dans la mémoire.
Ce problème est rencontré au quotidien, le rangement d’un grand placard étant habituel-
lement plus aisé qu’un espace réduit.
1. La pile est un espace mémoire utilisé pour stocker les variables locales. Son adresse haute est incrémentée à
chaque appel de fonction de sorte à empiler les variables locales et les dépiler lorsqu’une fonction se termine.
2. Dont les différents éléments peuvent être chargés en mémoire à des adresses non fixées par avance.
42
2.2. Le système d’exploitation
Isolement : Chaque programme peut disposer de son propre espace d’adressage. Il est donc
possible d’assurer qu’aucun processus ne pourra accéder aux données d’un autre de ma-
nière non autorisée. Chaque programme est ainsi isolé du reste du système, ce qui offre un
bon moyen de sécuriser les données de ces derniers et d’isoler le système d’exploitation.
Multi-instances : La question des codes non relocalisables est réglée en permettant l’utilisation
des mêmes adresses virtuelles pour différents programmes, chaque instance travaillant
dans son propre espace. Cela suppose toutefois que les adresses physiques sont associées
à une unique adresse virtuelle, sauf demande explicite (mémoire partagée).
Projection passive : Il est possible de projeter un autre espace de stockage dans la mémoire
(fichier, disque...) en générant des transferts au moment des premiers accès aux données.
Les accès à ces données se font donc de manière transparente au travers de simple accès
mémoire.
Extension de la mémoire : La virtualisation de la mémoire permet de mettre en place faci-
lement un système de pagination disque (swap dans la terminologie Unix) permettant
d’utiliser plus de mémoire physique que disponible. Dans ce cas, une fraction, si possible
rarement utilisée, de la mémoire est copiée sur le disque pour laisser place à une nou-
velle donnée plus utile. Les futurs accès à la donnée déplacée nécessitent alors un échange
(swap) pour être chargés en mémoire avant utilisation. Cette extension se fait toutefois au
prix d’un surcoût lié à la relative lenteur des systèmes de stockages permanents tels que
les disques durs.
Compression mémoire : Dans la même idée que le swap, certains proposent de compresser les
données non utilisées pour économiser de la mémoire[Riz97, YDLC10] sans être pénalisé
par les accès aux disques durs. On notera une certaine activité récente autour de cette
question notamment vis-à-vis des machines virtuelles pour Linux.
Pour la segmentation, l’espace virtuel se définit par assemblage de “segments” décrits comme
des espaces mémoire contigus de tailles variables. Ces segments sont associés à un décalage per-
mettant la correspondance avec les adresses physiques par simple addition à l’adresse virtuelle.
Ils sont donc décrits dans une ou deux tables dont les entrées sont identifiées par le sélecteur
de segment, habituellement défini par un registre. Différents sélecteurs sont généralement dis-
ponibles pour distinguer les différentes parties du programme : code, constantes, pile... Sur les
architectures à faible largeur d’adressage, cette approche a posé de nombreux problèmes du fait
de la nécessité de changer (explicitement) de segment pour accéder à des tableaux de tailles
importantes.
La pagination reprend la notion de segment, mais lui applique une taille fixe. L’espace virtuel
est ainsi découpé en segments de taille prédéfinie, dits pages (généralement 4 Ko). L’espace
mémoire physique est découpé de la même manière de sorte qu’il est possible d’associer une
page virtuelle à une page physique (Figure 2.1). L’association entre ces deux espaces est alors
décrite dans une table maintenue par l’OS. Ce découpage de la mémoire en segments de tailles
fixe permet de faciliter la gestion des allocations mémoires au niveau du système d’exploitation :
43
Chapitre 2. Gestion de la mémoire
1. L’utilisation d’une taille unique (ou ses multiples) réduit les problèmes de fragmentation
de la mémoire, c’est à dire l’introduction de trous non alloués, mais trop petits pour être
utilisés par la suite. Ce problème sera discuté plus en détail dans la suite (section 2.4.2).
2. L’utilisation d’un grand nombre de pages pour décrire l’espace d’adressage permet de
décrire efficacement un espace creux. De cette façon, les pages virtuelles non utilisées
peuvent être libérées afin de réduire la consommation mémoire des programmes, et ce,
même pour celles situées au milieu d’un segment alloué.
3. Les différentes pages voisines n’ayant pas de contraintes de contiguïté, il est possible d’al-
louer efficacement la mémoire en utilisant plus aisément les pages physiques disponibles.
Mémoire virtuelle
F IGURE 2.1 – Pagination de la mémoire pour gérer la traduction des adresses virtuelles.
L’invention du système de pagination est décrite par certains comme l’une des plus belles
ingénieries de l’informatique. Toutefois, sa mise en place effective a longtemps été en but au
problème pratique de construire une manière efficace de traduire les adresses au niveau maté-
riel. Cette nécessité de modifier le matériel a dans un premier temps restreint cette technique à
des études liées aux machines virtuelles pour lesquelles une émulation logicielle pouvait rapide-
ment être mise en place.
F IGURE 2.2 – Structure de la page des tables utilisée par Linux pour les architectures x86_64 extraite
de http ://[Link]/.
Notons que les espaces virtuels actuels couvrent généralement un adressage sur 48 bits, soit
256 To. Les 64 bits d’adresse des processeurs ne sont en effet pas réellement exploitables pour
l’instant, mais laissés pour un usage futur[Int10a]. Stocker la table des pages sur un seul niveau
44
2.2. Le système d’exploitation
nécessiterait 256T o/4Ko = 64Go de mémoire. En pratique, cette dernière prend donc la forme
d’un arbre dont chacun des nœuds occupe la taille d’une page (4Ko). Un exemple est donné
par la figure 2.2 pour Linux sur architecture x86_64. La traduction d’adresse peut ensuite être
effectuée de manière logicielle par l’OS ou matérielle par une unité dédiée, la MMU (Memory
Management Unit).
45
Chapitre 2. Gestion de la mémoire
En plus de décrire l’association des pages virtuelles et physiques, la table des pages définit
les droits d’accès à la mémoire. Le contenu d’une page peut en effet être lu, écrit ou exécuté.
Sur de nombreuses architectures, telles que x86_64, les pages sont également associées à un
niveau de privilège. Ceci permet de projeter l’ensemble de la mémoire utilisée par le noyau dans
l’espace virtuel du processus (en général à la fin). Cet espace est inaccessible en temps normal
par l’utilisateur. Cette astuce utilisée par Linux[BP05] et d’autres OS permet d’éviter d’invalider
certains caches (TLB que nous verrons en section 2.5.2) en changeant de table des pages lors
des appels systèmes. Cela a toutefois conduit à la limitation des 3.5 Go de mémoire adressable
sur architecture 32 bits au lieu des 4 Go attendus. Pour les architectures 64 bits, l’espace est
suffisamment grand pour que cette approche ne pose plus de problème.
46
2.3. Interface avec les applications
Mémoire virtuelle
F IGURE 2.3 – Exemple d’organisation de l’espace virtuel Linux en VMA avec différentes propriétés.
Les zones inter-VMA sont interdites et conduisent immédiatement à un arrêt du processus au travers
du signal faute de segmentation.
utiliserons le terme de zone mémoire dans ce document) auxquels sont associées des informa-
tions (taille, adresse de base, droits, source de donnée...). Un exemple de découpage de l’espace
virtuel en VMA est donné dans la figure 2.3.
Nous l’avons vu, l’espace d’adressage virtuel est beaucoup plus grand que l’espace physique.
Par conséquent, la majeure partie de ce dernier n’est pas associé à une zone mémoire physique.
Lorsqu’un processus accède à ces zones, on dira qu’il y a faute de page. Une interruption est donc
levée pour donner la main au système d’exploitation qui va alors terminer le processus fautif.
Cet arrêt est effectué en envoyant un signal de type faute de segmentation bien connu des déve-
loppeurs C/C++. Ce type d’erreur peut survenir si le processus accède à une zone non associée
à une page physique, ou bien outrepasse les droits d’accès aux données de cette page (lecture,
écriture, exécution ou niveau de privilège).
Cette capacité de notifier l’OS d’un accès à une page est mise à profit pour mettre en place
une politique d’allocation paresseuse. Selon cette approche, les appels de types mmap autorisent
l’utilisation d’un segment mémoire, mais ne lui associent pas immédiatement de mémoire phy-
sique. Le segment est alors dit virtuel. Ces segments provoquent donc une faute de page lors
du premier accès par le processus. À ce moment, l’OS peut alors dynamiquement associer une
page physique à la zone concernée et rendre le contrôle au processus pour qu’il poursuive son
exécution de manière transparente. L’utilisation de la mémoire physique est donc ajustée dyna-
miquement en fonction de l’utilisation réelle par le processus. Cela permet d’éviter un gaspillage
mémoire pouvant survenir avec les applications qui demandent explicitement plus de mémoire
qu’elle n’en utilise réellement.
Cette méthode est particulièrement utile pour les fichiers projetés dans la mémoire par
mmap. De cette manière, ne sont lues et chargées que les parties utiles de ces fichiers. Ceci
est notamment utilisé pour les exécutables et bibliothèques. Ce mécanisme est d’ailleurs la base
même du système de pagination disque survenant en cas de congestion mémoire 4 . Dans ce cas,
une page considérée comme inutile est copiée sur le disque et supprimée de la table des pages.
Lors d’un accès futur, une faute de page sera levée pour demander le rechargement de cette
donnée en mémoire.
4. Lorsque toute la mémoire est utilisée par l’OS et les applications et que des requêtes sont en attente.
47
Chapitre 2. Gestion de la mémoire
2.4.1 Interface
Pour son interface, l’allocateur définit dans le langage C suit une démarche proche de ce que
l’on retrouve au niveau du système pour manipuler les pages, à savoir le nécessaire pour allouer,
redimensionner et libérer des segments mémoires :
malloc : Fonction utilisée pour allouer un nouveau segment mémoire de taille demandée.
calloc : Fonction similaire à malloc, mais assure contrairement à cette dernière que la mémoire
nouvellement allouée est initialisée à 0.
free : Fonction permettant de libérer la mémoire occupée par un segment alloué avec l’une des
autres fonctions.
realloc : Fonction permettant de redimensionner un segment. Cette méthode provoque un
éventuel changement d’adresse du segment si l’espace contiguë suivant est occupé et ne
permet de satisfaire la requête. Le segment sera alloué s’il n’existe pas déjà (adresse nulle),
ou bien libéré pour une taille nulle.
memalign : Fonction similaire à malloc mais permettant de contraindre l’alignement mémoire
du segment.
Dans le langage C++, cette interface est étendue par l’adjonction des mots clés new et delete
se traduisant par un pré- ou post-traitement éventuel aux appels respectifs de malloc et free.
Cet opérateur prend automatiquement en charge la détection de taille du type et l’appel des
constructeurs et destructeurs de l’objet considéré s’il en définit.
Ces fonctions d’allocation de C et C++ sont utilisées pour les allocations dites dynamiques
par opposition aux allocations statiques placées par le compilateur sur la pile. On décidera de
recourir à leur usage dans les cas suivants :
1. La taille de l’allocation n’est pas connue au moment de la compilation, la décision doit
donc être prise au moment de l’exécution. Ce critère est une des raisons principales de
l’approche dynamique.
2. La taille du segment à allouer est trop grande pour tenir dans la pile.
3. Le ou les éléments placés dans le segment alloué doivent survivre après la sortie de la
fonction.
On notera que les langages de plus haut niveau (de type Java, C#...) n’exposent pas cette
distinction au développeur en ne lui fournissant que la sémantique d’allocation dynamique.
2.4.2 Fragmentation
Dans un programme, l’allocateur mémoire est appelé par l’ensemble des fonctions du pro-
gramme ; les requêtes sont donc associées à des tailles potentiellement très variables, dépen-
dantes des objets manipulés par ces dernières. D’autre part, les segments alloués peuvent avoir
des durées de vie très différentes. Ces deux paramètres créent le problème dit de fragmentation,
48
2.4. L’allocateur mémoire (malloc)
1 S1 S2 S3
2 S1 S3
3 S1 S4 S5 S6 S7 S3
4 S1 S5 S6 S3
5 S1 S5 S6 S3 S8
F IGURE 2.4 – Illustration du problème de fragmentation externe en considérant une séquence d’al-
location d’éléments de 256o, 64o et 128o.
correspondant à l’apparition de trous non réutilisables (taille plus petite que les requêtes à venir)
entre segments alloués. Ce problème est très discuté dans la littérature[JW98] et représente l’un
des principaux problèmes de conception des allocateurs mémoires. Ce problème peut s’illustrer
en supposant un schéma d’allocation du type :
1. Allocation de trois segments de 256 octets. Dans un état initial, ils peuvent être alloués de
manière contiguë. Notons-les s1 ,s2 et s3 par adresse croissante.
2. Libération du segment s2 situé au milieu des deux autres.
3. Allocation de 4 segments de 64 octets qui peuvent être placés dans la zone libérée part s2 .
4. Libération des segments de 64 octets 1 et 4.
5. Allocation d’un nouveau segment de 128 octets.
Dans cette configuration, le segment final ne peut être placé dans l’espace laissé libre entre s1
et s3 car cet espace est fragmenté. Le bloc doit donc être alloué après s3 , conduisant à une aug-
mentation de la consommation mémoire. Si toutes les allocations suivantes nécessitent plus que
64 octets, la zone fragmentée entre s1 et s3 ne pourra jamais être réutilisée. La fragmentation
tend donc à dépendre de deux paramètres :
1. Le mélange de blocs de tailles différentes pouvant conduire à un mélange non compact de
l’espace mémoire.
2. Le mélange de blocs ayant des durées de vie différentes peut entraîner la formation de
trous non compatible avec les tailles mémoires requises dans le futur ou rend impossible
la libération des pages associées non totalement utilisées.
La littérature distingue habituellement deux types de fragmentations :
Fragmentation interne : Cette dernière décrit la quantité de mémoire perdue à l’intérieur du
segment alloué. En effet, l’allocateur ajoute généralement des en-têtes de description au
segment et applique certains décalages pour maintenir des alignements compatibles avec
les contraintes de l’architecture. Ces espaces supplémentaires s’ajoutent donc à celui de-
mandé par l’utilisateur. Un bon exemple de fragmentation interne apparaît avec la pagina-
tion : si l’on ne dispose pas d’un allocateur intermédiaire, la demande de 1 Ko conduit à la
réservation pratique de 4 Ko, c’est la fragmentation interne.
Fragmentation externe : On s’intéresse ici à l’espace perdu par le placement des blocs, donc
relié à la présence de trous non réutilisables. En ces termes, la gestion des pages physique
n’est pas impactée par la fragmentation externe, car une seule taille de bloc est utilisée, il
est donc toujours possible de ré-utilisé une page physique libre.
Remarquons que les politiques oscillent souvent entre ces deux types de fragmentation, la ré-
duction de l’une tendant généralement à favoriser l’autre comme c’est par exemple le cas pour
la pagination.
49
Chapitre 2. Gestion de la mémoire
2.4.3 Ramasse-miettes
La gestion de la mémoire est souvent une tâche délicate dans le développement d’un pro-
gramme. La libération des segments alloués est souvent l’objet d’oublis. Ce problème de fuite
mémoire est traité par des outils tels que Valgrind[NS07] et demande des efforts systématiques
de la part des développeurs. Ce problème peut être pour parti réglé avec l’introduction d’un
ramasse-miettes (Garbage Collector), introduit pour le langage récursif LISP dans les années
1950[McC60]. Cette approche vise à libérer automatiquement toute zone mémoire non réfé-
rencée. Remarquons toutefois que le problème subsiste si le développeur oublie de déréférencer
un objet. Il n’est donc résolu que pour les segments orphelins pour lesquels aucun pointeur ne
permet plus d’y accéder.
Ce type d’approche est au centre des langages de plus haut niveau tels que Java, Python,
C#... en leur permettant d’abstraire les problèmes de gestion mémoire. Ces langages basés sur
la notion de référence plutôt que pointeur offrent également la possibilité de déplacer un seg-
ment après son allocation. Ceci lève donc l’une des contraintes principales des allocateurs mé-
moire des langages C,C++ et Fortran. Avec cette liberté, il est en effet possible d’effectuer
une défragmentation régulière de la mémoire. On trouve ainsi une très large littérature dans
ce sens[DP00, BOP03], notamment dans le cadre des architectures parallèles actuelles. Ceci
permet par exemple d’éliminer le problème de fragmentation survenant sur la figure 2.4 de la
section précédente. Cette thèse s’intéresse toutefois aux principaux langages utilisés en HPC (C,
C++ et Fortran), nous ne pourrons donc pas profiter de cette liberté.
Au-delà de la simple notion de gestion mémoire, il est important de remarquer que l’évolu-
tion des processeurs doit satisfaire à de nombreuses contraintes autres que sa seule capacité à
calculer. En terme de performance, la mémoire est actuellement un facteur limitant. Les proces-
seurs se sont donc structurés de manière à compenser ces effets. On obtient ainsi la structure
en cache hiérarchique que l’on observe aujourd’hui. Les systèmes d’exploitation ont également
nécessité certaines adaptations au niveau matériel afin de permettre leur développement. C’est
notamment ce que l’on observe avec l’introduction des mécanismes de pagination au centre
de la gestion de la mémoire de tout système moderne. Cette section dresse un inventaire des
points clés décrivant l’accès physique aux données en considérant les problématiques propres à
la pagination, donc aux traductions d’adresses et aux méthodes de transfert de données entre la
mémoire et les unités de calcul.
50
2.5. Accès à la mémoire
Hiérarchie
La présence de plusieurs cœurs au sein d’un même processeur impacte cette hiérarchie. Les
caches peuvent en effet être locaux ou partagés entre plusieurs cœurs. On trouve en général
des caches locaux pour les premiers niveaux et partagés pour les derniers. La figure 2.5 (a)
donne la structure détaillée d’un processeur Intel Sandy-bridge, typique de ce que l’on observe
sur les processeurs actuellement utilisés par les super-calculateurs. L’impacte de cette hiérarchie
peut être mis en évidence en mesurant le temps d’accès répétés à un segment de taille variable.
Comme le montre la figure 2.5 (b), l’accès aux petits volumes de données se fait d’autant plus
rapidement qu’ils peuvent être contenus dans les caches les plus internes.
Les caches sont des mémoires contenant une copie locale d’information. Leur utilisation se
fait de manière transparente en étant entièrement prise en charge par les mécanismes matériels
du processeur. Les échanges entre la mémoire et le cache se font par lignes de cache, soit des
segments contigus de 64 octets, et ce, même si l’utilisateur n’a demandé qu’une fraction de
cette zone mémoire. Toutefois, le cache est par définition une entité qui ne peut pas contenir
51
Chapitre 2. Gestion de la mémoire
15
10
5
Coeur 0 Coeur 1 Coeur 2 Coeur 3 Coeur 4 Coeur 5
PU 0 PU 2 PU 4 PU 6 PU 8 PU 10
0
PU 1 PU 3 PU 5 PU 7 PU 9 PU 11 4 32 256 12Mo 256Mo
Taille du segment mémoire (Ko)
(a) (b)
F IGURE 2.5 – Exemple de topologie de l’architecture Intel Wesmere utilisée sur les nœuds de la grappe
Cassard. Le schéma (a) donne le rattachement et les tailles des caches privés L1 et L2 des différents
coeurs et le cache L3 partagé à l’ensemble du processeur. Le graphique de droite (b) donne les temps
d’accès par ligne de cache en fonction de la taille du segment lue en boucle.
l’ensemble de la mémoire. Lors d’un accès à une nouvelle donnée, il faut donc évincer une donnée
présente et supposée non utilisée. De plus, à chaque accès, les copies présentes doivent pouvoir
être identifiées pour savoir si la donnée est présente et où. On dispose de trois techniques pour
réaliser cette tâche :
Cache entièrement associatif (fully associative caches) : Dans cette approche, les lignes de
cache peuvent être associées à n’importe quelle adresse, cela suppose que chaque ligne de
cache est associée à un registre mémorisant l’adresse des données qu’elle contient. Lors
d’une requête, il faut effectuer une recherche exhaustive sur tout le cache pour trouver la
ligne correspondante. Cette méthode a donc une complexité proportionnelle à la taille du
cache (complexité en O(s) avec s la taille du cache). Cette technique n’est donc utilisée
que sur les très petits caches (quelques kilo-octets). Elle se limite en général aux caches
de premier niveau et aux TLB (Translation lookaside buffer) que nous décrirons dans la
prochaine section.
Association directe (direct caches) : Chaque adresse est associée à une ligne de cache unique.
La recherche est donc très rapide (complexité en O(1)). L’association est en général dé-
terminée par les bits de poids faible de l’adresse. Ce mode a toutefois le défaut de créer
beaucoup de collisions si les données utilisées sont associées à la même position du cache.
Associatif à N voies (N-way caches) : Il s’agit d’un compromis entre les deux approches précé-
dentes. Les collisions sont réduites en associant chaque adresse à N lignes de cache. Pour
trouver une donnée, on effectue une recherche exhaustive sur au plus N éléments (com-
plexité en O(N )). Les caches processeurs utilisent généralement cette approche pour les
caches de tailles importantes. La figure 2.6 représente l’association des segments mémoires
avec les lignes de cache de cette approche. Remarquons que ce modèle plus général en-
globe les deux précédents en considérant respectivement le cas d’une taille de voie égale
s
à une ligne de cache (N = 64 ) ou une voie unique (N = 1).
On notera à titre de complément qu’il est possible de s’abstraire de ces problèmes si les
caches sont manipulés explicitement. Ces caches sont dits en terminologie anglophone scratch-
pad[BSL+ 02]. Le placement des données est alors défini par l’utilisateur ou plus généralement
le compilateur.
52
2.5. Accès à la mémoire
Mémoire
Cache
Voie 1 Voie 2
F IGURE 2.6 – Exemple d’associativité à 2 voies montrant les points de stockage possible pour les
cellules de couleurs gris clair.
Nous avons vu que la table des pages était constituée d’un arbre. Une traduction nécessite
donc l’accès à plusieurs entrées mémoires ou à un appel logiciel à l’OS, rendant la traduction
coûteuse. Afin de contrebalancer cet effet, les processeurs disposent d’un cache (TLB : Transla-
tion lookaside buffer). Il est ainsi possible de garder en mémoire un nombre réduit de traductions
afin de s’y référer rapidement en cas de réutilisation. Une page contient un nombre important
de données. On peut donc compter sur le fait qu’un accès linéaire ne nécessitera qu’une seule
traduction pour l’ensemble des accès de la page avant de passer à la suivante.
L’existence des TLB a une contrepartie pour l’OS qui doit invalider leur contenu en cas de
modification de la table des pages. Ces invalidations engendrent un surcoût associé à toute mani-
pulation de la table des pages, à la fois pour exécuter l’invalidation elle-même, mais aussi parce
qu’elle nécessite une nouvelle traduction d’adresse de la part de l’application lorsqu’elle reprend
le contrôle. Certains processeurs disposent donc de techniques permettant de n’invalider qu’une
partie des entrées et éviter les invalidations globales utilisées par les premières générations.
53
Chapitre 2. Gestion de la mémoire
20
Cout par accès
15
10
0
0 0.5 1 1.5 2 2.5 3 3.5 4
Mémoire adressée (Mo)
F IGURE 2.7 – Mise en évidence de l’effet des TLB avec leur limite d’adressage à 2 Mo pour les pages
de 4Ko. Le coût relatif aux performances des caches est donné en générant des accès dans ou hors
des caches L1 (32 Ko) et L2 (256 Ko) mais toujours dans le L3 (8 Mo) de l’architecture Nehalem.
Ce problème peut être contourné en utilisant une approche dite NUMA (Non Uniforme Me-
mory Access) dans laquelle les différents processeurs d’une machine disposent d’une mémoire
locale avec un accès rapide. Afin de maintenir un mode mémoire partagée, un mécanisme est
54
2.5. Accès à la mémoire
(a) (b)
F IGURE 2.8 – (a) Exemple de noeud NUMA composé de 4 processeurs avec 4 liens chacun et deux
modules d’entrées/sorties (E/S). (b) Coût effectif du passage par les liens NUMA sur les noeuds 128
coeurs Curie avec leurs 3 niveaux NUMA[VJYA13].
alors mis en place pour accéder automatiquement à une mémoire distante. Ces accès se font en
passant par le processeur propriétaire au travers de liens d’interconnexions (QPI chez Intel, Hy-
perThransport chez AMD). Les accès se séparent donc en deux catégories, locaux et distants. Les
accès distants sont impactés par une latence plus importante. On augmente donc la bande pas-
sante mémoire locale au prix d’une augmentation de la latence des accès distants et du maintien
d’une contention sur ces derniers s’ils sont réalisés en trop grand nombre. Sur ces architectures,
les programmes doivent veiller à accéder autant que possible à des données locales et limiter les
accès distants.
Les nœuds peuvent exploiter différentes topologies structurées en plusieurs niveaux NUMA
(nombre de sauts à faire pour rejoindre une mémoire donnée) en fonction du nombre de liens
offerts par le processeur. La figure 2.8 (a) donne l’exemple d’une topologie à 4 processeurs sem-
blables à ce que l’on trouve sur les nœuds 32 cœurs de Tera 100. Les nœuds 128 cœurs de Curie
et Tera 100 exploitent eux un niveau supplémentaire reliant 4 nœuds de 32 cœurs par la tech-
nologie BCS (Bull Coherence Switch Architecture) développée par Bull. Cette architecture qui
est détaillée en annexe implique 3 niveaux NUMA visibles sur le graphique de bande passante
des nœuds larges de Curie : 2.8 (b).
55
Chapitre 2. Gestion de la mémoire
à l’intérieur de son nœud NUMA d’origine. En cas de besoin de migration du processus sur un
autre nœud NUMA, il est possible de recourir à une migration de la mémoire. Ce support n’est
pas nécessairement optimal dans les OS actuels, mais les informations sont à disposition pour
mettre en place une politique correcte.
2.6 Conclusion
Nous venons de voir que la conception des architectures mémoires actuelles agrégeait de
nombreux concepts pour résoudre le problème du mur de la mémoire et permettre l’implémen-
tation de systèmes d’exploitations fiables et robustes. Dans la suite de ce document, nous allons
montrer que certains de ces points méritent d’être revisités en prenant en compte le nombre
croissant de cœurs des architectures modernes et l’utilisation à grande échelle d’architectures
NUMA. Comme nous venons de le voir, l’OS est l’outil chargé de gérer cette infrastructure, nous
allons donc essentiellement nous intéresser à ce dernier et à sa couche d’interaction (en terme
mémoire) avec le niveau applicatif (malloc).
56
Deuxième partie
Contribution
57
La partie précédente a présenté un rapide historique de l’évolution du matériel utilisé pour le
calcul haute performance. Elle a également introduit les notions structurantes des architectures
modernes et de leur programmation. Cette description s’est terminée par un rappel détaillé des
mécanismes d’accès à la mémoire et de gestion de cette ressource par le système d’exploitation.
Cette seconde partie va se baser sur ces connaissances pour décrire les travaux attachés aux
quatre problématiques majeures abordées durant cette thèse.
Nous donnerons dans un premier temps les résultats obtenus lors de notre étude du com-
portement collaboratif du système de pagination de l’OS et de l’allocateur mémoire en espace
utilisateur, au vu de leur impact sur les performances des caches. Le second chapitre se concen-
trera sur l’allocateur lui même en tâchant de prendre en compte les problématiques de passage à
l’échelle sur architecture NUMA. Ce chapitre donnera une description de l’allocateur conçu dans
le cadre du projet MPC et pointera notamment un problème d’extensibilité de l’implémentation
actuelle des fautes de pages du noyau Linux. Le troisième chapitre se focalisera sur ce problème
et étudiera les mécanismes de fautes de pages de cet OS en proposant une modification de sa sé-
mantique d’échange avec l’espace utilisateur. Nous montrerons qu’il est ainsi possible d’éliminer
les effacements mémoires coûteux imposés par la sémantique standard. Comme la consomma-
tion mémoire constitue actuellement un enjeu, nous terminerons par une analyse du module
noyau KSM (Kernel Samepage Memory) offert par les noyaux Linux récents. Nous décrirons
un test de cette technique sur un maillage de l’application Hera afin de réduire son empreinte
mémoire en fusionnant les pages au contenu identique.
59
60
Chapitre 3
Ce chapitre décrit une étude préliminaire réalisée sur l’interaction, et plus précisément les
interférences, des politiques d’allocation en espace noyau et utilisateur. Ici, nous nous intéres-
serons principalement à la gestion des gros tableaux mémoires et à leur agencement dans les
caches du processeur. Le problème traité peut se découper en deux sous-problèmes : d’un côté,
l’impact de la politique de pagination vis-à-vis des caches, de l’autre, l’impact des choix de l’allo-
cateur sur ces mêmes caches. Ces deux problèmes pris séparément sont très largement discutés
dans la littérature. On ne trouve toutefois que peu de discussions sur l’interaction des politiques
proposées. En ce qui concerne l’allocateur mémoire, les études liées aux caches sont habituel-
lement centrées sur la problématique des petites allocations, négligeant le problème spécifique
des gros segments. Ici, notre contribution sera donc centrée sur l’analyse des interférences po-
tentielles entre les stratégies retenues au niveau de l’OS et celles de l’allocateur mémoire en
espace utilisateur. Cette analyse sera également l’occasion de discuter la politique de pagination
de L INUX sous un angle nouveau, donnant des arguments originaux en faveur de l’approche,
certes améliorable, retenue par cet OS vis-à-vis de sa robustesse aux cas pathologiques.
Dans un premier temps, nous rappellerons les liens connus qui s’établissent entre pagination
et associativité des caches. Nous pourrons alors lister les différentes approches actuelles exploi-
tées par les OS disponibles. Suivra une partie expérimentale permettant de fournir les données
nécessaires à notre étude. Pour cela, nous étudierons les performances de différentes applica-
tions sur plusieurs OS afin de comparer leurs politiques. S’en suivra une analyse détaillée des
différents problèmes répertoriés. Il nous sera alors possible d’extraire de nouvelles recomman-
dations concernant les aspects OS et espace utilisateurs de la gestion mémoire. Nous décrirons
enfin un programme prototype permettant de repérer certains des problèmes de notre inventaire
et une exploration de méthode de résolution pour la partie espace utilisateur.
Une indexation virtuelle est habituellement retenue pour le premier niveau de cache. Ce
dernier ne peut en effet pas se satisfaire de la latence induite par le mécanisme de traduction
61
Chapitre 3. Interférences des mécanismes d’allocations
Adressage virtuel
Adressage physique
?
F IGURE 3.1 – Exemple de conflit de cache lié à un placement non optimal des pages en considérant
un cache associatif à 4 voies indexées physiquement.
d’adresse [LBF92, CD97]. Dans ce cas de figure, la prise en compte de l’associativité du cache
reste de la responsabilité du développeur ou de l’allocateur mémoire. On trouve ainsi nombre
de travaux visant à optimiser le placement des données en espace virtuel vis-à-vis de ce type
de cache : [CHL99, HBHR11]. Dans ce cas, la position pcache d’une donnée dans le cache peut
être modélisée par l’équation 3.1 en considérant S la taille du cache, A son associativité, pvirt.
S
l’adresse virtuelle de la donnée et W = A la taille d’une voie du cache :
À l’opposé, une indexation physique fait intervenir la table des pages dans le processus. En
conséquence, le sous-système mémoire de l’OS devient un paramètre entre l’application et le
cache. L’OS décide en effet de la position physique d’une page virtuelle. Il choisit donc par la
même occasion le placement correspondant dans le cache associatif si ce dernier fournit des
voies plus grandes qu’une page. Considérons B l’adresse physique de la base de la page, U la
taille d’une page et o ≡ pvirt. (mod U ) le décalage dans la page. L’adresse physique pphys. d’une
donnée se définit alors comme pphys. = B +o. La position dans le cache devient donc dépendante
de B :
pcache ≡ pphys. (mod W ) ≡ (B + o) (mod W ) (3.2)
Les voies du cache ont habituellement une taille multiple de la taille de page. On peut donc
définir la couleur c d’une page comme sa position dans un cache indexé physiquement. Cette
couleur dépend uniquement de la table des pages au travers de B :
pcache B (mod W )
c=b c≡b c (3.3)
U U
On notera que dans un cache associatif à A voies, l’utilisation de A + 1 pages de la même cou-
leur génère un conflit ; la dernière page devant occuper l’une des places prises par les A autres
pages. Le problème peut-être illustré en considérant un segment continu en mémoire virtuelle
et couvrant plusieurs pages. Du fait de la pagination, nous avons vu au chapitre 2 que la mé-
moire physique associée n’avait aucune raison d’être contiguë. En considérant un cache A fois
associatif on peut donc se trouver dans la situation décrite par la figure 3.1. Dans cette situa-
tion, l’accès à la dernière page du segment conduira nécessairement à l’éviction d’une des pages
précédemment chargées dans le cache. Les accès successifs à ce segment seront donc pénalisés
par des transferts mémoires, même si ce dernier aurait pu être placé entièrement dans le cache.
Ce problème a été largement étudié et décrit, on pourra par exemple citer [AHH89, KH92,
BKW98] ou certains travaux plus récents avec une reprise d’activité de ce sujet [HK, PTH11,
ADM11]. Il peut-être décrit avec une approche statistique en considérant un choix aléatoire des
pages physiques lors de l’allocation. Un cache associatif offre C = W
U couleurs possibles. Si les
62
3.2. Politiques de pagination
pages sont choisies de manières aléatoires et indépendantes, alors la probabilité d’obtenir une
couleur c est :
1
p= (3.4)
C
Ce problème de tirage aléatoire de N éléments parmi C types d’éléments se résout mathémati-
quement sous la forme d’une loi binomiale donnant une probabilité d’obtenir k éléments d’une
couleur donnée : k (N −k)
N 1 1
P (N,X = k) = 1− (3.5)
k Cmax Cmax
On peut donc évaluer le nombre de fautes de cache en considérant les couleurs présentes en
quantité supérieure aux A voies du cache :
N
X
f (N ) = Cmax (k − A)P (N,k) (3.6)
k=A
Cette description prend en compte la part de faute liée au manque de capacité du cache qui
peut s’exprimer plus simplement en considérant un remplissage idéal :
On peut donc extraire la part de faute induite par la politique de pagination aléatoire comme
étant :
N
X
fpoli. (N ) = Cmax (k − A)P (N,k) − fcapa. (N ) (3.8)
k=A
Cette évaluation théorique est comparée à l’expérience dans la figure 3.2 de la section sui-
vante en considérant un accès linéaire à un tableau mémoire et les paramètres du cache L3 des
processeurs I NTEL N EHALEM, à savoir une associativité de 16 pour une taille de 8 Mo.
63
Chapitre 3. Interférences des mécanismes d’allocations
Comme rappelé dans la section 3.1, ce type de politique génère des conflits de caches direc-
tement imputables à la politique de placement des pages et non à un manque de place dans le
cache. Afin de confirmer ces observations sur les larges caches actuels, nous avons comparé la
politique de Linux à une politique simulée strictement aléatoire et à la prédiction théorique de
la section 3.1. Pour cela, nous avons alloué un segment de taille voulue et effectué une initiali-
sation de son contenu en séquentiel ou parallèle. La table des pages de Linux est alors lue afin
de calculer le nombre de conflits pour un cache de taille et associativité fixées en considérant un
accès linéaire aux données. Cette mesure est finalement comparée à une table aléatoire générée
par nos soins.
−50 −50
0 2 4 6 8 10 12 0 2 4 6 8 10 12
Taille du segment (Mo) Taille du segment (Mo)
(a) (b)
F IGURE 3.2 – Comparaison des conflits de caches provoqués par une table des pages générée par
Linux et une table aléatoire. La simulation considère le cache L3 d’un processeur Nehalem, soit
8Mo partagés en 16 voies. Le graphique rassemble 500 exécutions pour chaque taille mémoire.
Il représente les minimums et maximums de conflits obtenus en fonction de la taille du tableau
considéré. À gauche (a), une mesure séquentielle, à droite (b) en parallèle.
La figure 3.2 montre clairement que Linux réagit d’une manière proche de la méthode aléa-
toire en terme de conflits de cache. Nous confirmons également l’observation de Bahadur[BKW98]
en montrant que la table aléatoire fournit des résultats plus dispersés que la table générée par
Linux. Ce phénomène s’explique par les relations pouvant intervenir entre deux allocations suc-
cessives. Les pages libres sont en effet gérées par un allocateur dit ”buddy allocator“ groupant
les pages contiguës par blocs allant jusqu’à 2 Mo. Les allocations des pages de ces blocs ne véri-
fient donc pas une distribution strictement aléatoire.
On peut également remarquer que les allocations réalisées en parallèle conduisent à une dis-
tribution identique à une table aléatoire. Ceci confirme les observations l’étude de Bahadur sur
des charges de travail plus intensives en allocation mémoire avec notamment des tests utilisant
plusieurs applications. Nos observations ne montrent aucun changement en fonction de la du-
rée de fonctionnement de l’OS. Avec 24Go de mémoire, nous observons strictement les mêmes
effets immédiatement après le démarrage alors que l’OS consomme de l’ordre de 100 Mo de mé-
moire, pouvant laisser espérer moins d’aléas dans la sélection des pages dans un grand espace.
La politique de pagination de Linux peut donc raisonnablement être considérée comme aléatoire
vis-à-vis des caches associatifs.
La figure 3.3 confirme l’impact de cette politique sur les performances en considérant un
64
3.2. Politiques de pagination
2.6
2.2
1.8
1.6
1.4
0 2 4 6 8 10 12
Taille du tempon (Mo)
F IGURE 3.3 – Mesure expérimentale de l’effet de fuite de cache sur les temps d’accès la mémoire. On
considère ici un accès répété et linéaire à un tableau sur un processeur I NTEL N EHALEM avec ou sans
support des grosses pages de Linux (THP : Transparent Huge Pages).
accès séquentiel répété à un tableau sur I NTEL N EHALEM. Sur ce type de processeurs, on note un
début de fuite du cache à partir de 5 Mo (62%) causé par la pagination aléatoire de L INUX. Lors
de l’utilisation de techniques de type cache blocking, le développeur ne doit donc pas oublier que
la politique de pagination de Linux ne permet pas une utilisation complète des caches indexés
physiquement. On remarquera que le développeur ne peut pas facilement compenser cet effet
au niveau espace-utilisateur et devra donc éventuellement considérer un cache plus petit pour
obtenir de bonnes performances.
Ce problème bien que connu est rarement discuté et pris en compte dans les modélisations
concernant les techniques de cache blocking[LRW91]. Il est également courant de présenter
des figures similaires à la figure 3.3 en utilisant des échelles logarithmiques pour les tailles
mémoires. Couplé à un échantillonnage des points de mesure en puissance de deux, ce type
d’approche tend à masquer le problème en occultant la perte des derniers 40% du cache. Il
convient donc d’être prudent lorsque l’on analyse ce type de graphique.
Hashage des adresses virtuelles : Cette méthode consiste généralement à appliquer un mo-
dulo de la taille d’une voie (W ) sur l’adresse virtuelle nécessitant une page physique. Le
65
Chapitre 3. Interférences des mécanismes d’allocations
Les différentes instances (processus) d’un même programme ont tendance à exploiter les
mêmes adresses pour certains éléments du programme (pile, tas, constantes...). Ces der-
niers tendent donc à générer des conflits inter-processus au niveau des caches partagés. Il
est donc possible d’ajouter [KH92] un décalage basé sur l’identifiant du processus (PID)
pour éliminer ces conflits.
Tourniquet : Le système se rappelle de la couleur utilisée lors de la précédente faute de page
et incrémente cette dernière à chaque faute de page. Cette méthode permet d’obtenir une
certaine adaptation en capturant le schéma du premier accès mémoire, supposant donc
que les suivants seront proches de ce dernier.
Équilibré : Le système compte l’utilisation des différentes couleurs et tente d’allouer les moins
utilisées. Dans cette approche, il est aussi possible de prendre en compte le nombre de
pages libres pour chacune des couleurs comme cela est discuté par [KH92]. Cette méthode
est surtout conçue pour mieux s’adapter aux contextes de pénurie mémoire.
Les OS O PEN S OLARIS[MM06] et F REE BSD offrent un support de ces méthodes. Le premier
permet de choisir parmi les deux premiers modes (avec ou sans ajout du PID). Ce choix n’est
toutefois disponible que sur architecture SPARC, le support x86 se limitant au mode de hachage
sans ajout du PID. Le deuxième génère implicitement un support de la méthode de hachage sans
PID de par son implémentation des superpages[NIDC02] discutée dans ce qui suit. Remarquons
l’existence de certains travaux visant à exploiter des informations fournies par le compilateur
[BAM+ 96] ou par des compteurs matériels [SCE99, RLBC94, BLRC94] pour améliorer la poli-
tique de coloration. Ces méthodes ne sont toutefois supportées par aucun OS de production.
Pour résoudre ce problème, certains processeurs offrent la possibilité d’utiliser des pages de
tailles supérieures dites grosses pages. De cette manière, il est possible d’adresser efficacement
un espace plus grand sans augmenter la taille des TLB. Remarquons que, comme cela est rap-
pelé dans [KNTW93], il n’est pas raisonnable d’exploiter ce type de pages de manière générale
pour tout l’OS. Une trop grande taille peut en fait impacter les sous-systèmes entrées/sorties qui
risquent de générer beaucoup plus de trafic de données. Ce type de pagination s’ajoute donc en
complément des pages standard de 4 Ko.
66
3.3. Résultats expérimentaux
Sur les architectures x86_64, il est possible d’utiliser des pages de 2 Mo ou 1 Go[Int10a].
L’implémentation de ce double support présente toutefois quelques difficultés notamment liées
à l’utilisation de deux tailles différentes réintroduisant les problèmes de fragmentation au ni-
veau de la pagination[GH12]. Les méthodes de résolution actuelles dépendent donc fortement
des OS considérés. On trouve chez F REE BSD l’une des méthodes natives les plus abouties dites
superpages[NIDC02]. OpenSolaris offre un support bien intégré, bien que moins avancé par rap-
port à la méthode de F REE BSD. Linux quant à lui, a longtemps maintenu son support sous
une forme très externe au gestionnaire principal, rendant son utilisation difficile et très contrai-
gnante. On trouve toutefois de nombreux travaux ces dernières années visant à améliorer ce
support, avec notamment le travail de Ian Wienand[Wie08, CWHW03] en 2008 ou de K. Yoshii
nommée big memory pour Linux sur Blue Gene[YIN+ 11]. Pour cet OS, on citera entre autre le
travail de Andreas Arcangeli[Arc10] (Transparent Huge Pages) désormais inclu officiellement
dans le noyau de RedHat 6 (2.6.32) et dans les branches officielles depuis la version 2.6.38. On
pourra trouver une étude complémentaire concernant les grosses pages dans domaine du HPC
avec l’étude de Zhang[ZLHM09] ou des propositions intermédiaires facilitant l’intégration aux
OS par Talluri[TH94].
En terme d’associativité, les grosses pages génèrent de par leur définition une forme de
coloration de page similaire à ce qui est obtenu par une méthode de hachage avec un simple
modulo. Les processeurs actuels disposent de caches de l’ordre de 8 Mo pour une associativité
de 16, correspondant à une taille de voie de 512 Ko. Les grosses pages ont une taille supérieure
(2 Mo) et doivent être alignées en mémoire sur leur propre taille. On obtient donc naturellement
un placement en cache qui ne dépend que de la taille d’une voie et de l’adresse virtuelle. Cela
peut se démontrer en reprenant la définition de placement des données en cache (eq. 3.2) en
considérant Uhuge la taille d’une grosse page tel que Uhuge >= W et Uhuge (mod W ) = Bhuge
(mod W ) = 0.
Plus simplement, cela correspond à remarquer qu’une grosse page couvre un nombre entier
de voie. Cette propriété implique une relation directe entre adresse virtuelle et physique en
terme d’associativité. On remarquera de plus que l’aspect attentif aux caches des grosses pages
repose sur leur définition matérielle, non logicielle. Il n’y a donc aucun moyen d’appliquer des
règles de pagination pour modifier leur impact sur l’associativité des caches. Des techniques
telles que l’ajout du PID comme décalage sont donc inapplicables.
3.2.4 Conclusion
Dans cette section, nous avons vu différentes politiques de pagination et leurs interactions
avec les caches associatifs. Sur le plan théorique, Linux semble désavantagé par rapport à
F REE BSD et OpenSolaris qui recourent explicitement à des politiques qui prennent en compte
les caches. Dans ce qui suit, nous allons comparer expérimentalement ces techniques et montrer
que l’approche aléatoire présente tout de même certains intérêts.
67
Chapitre 3. Interférences des mécanismes d’allocations
Dell T5500
Processeur Bi Intel Xeon-E5502 (Nehalem)
Fréquence 2.27 GHz
Cache L3 8 Mo, 16 voies
Cache L2 256 Ko, 8 voies
Cache L1 32 K, 8 voies
Mémoire 24 Go
TABLE 3.1 – Plaftorme de test utilisée pour l’évaluation des politiques de pagination.
Au niveau logiciel, nous avons essayé de fixer au maximum les composants utilisés de ma-
nière à garder autant que possible le noyau comme unique variable. Nous avons donc utilisé
le compilateur GCC-4.4.1 recompilé manuellement sur chaque système. De la même manière,
nous avons fixé les bibliothèques nécessaires aux benchmarks utilisés tels que BINUTILS -2.20,
GMP-5.0.1, MPFR -2.4.2, LIBATLAS -3.8.3 et MPICH 2-1.2.1 P 1. Chacune de ces dépendances est
recompilée si possible avec les mêmes options pour l’ensemble des systèmes testés. Tous les
benchmarks ont ainsi été compilés par les outils précédemment décrits en utilisant les options
de compilation suivantes, nécessaires pour assurer un mode de compilation valide et similaire
sur chacun des trois OS : -m64 -fomit-frame-pointer -O3 -march=core2.
En procédant ainsi, à part pour la LIBC, nous laissons le noyau comme principale variable de
manière à comparer L INUX F EDORA 16 (noyau 2.6.38), O PEN S OLARIS 2009.06 et F REE BSD 8.2,
chacun de ces OS fonctionnant en mode 64 bits. Nous avons également cherché à limiter l’impact
des ordonnanceurs de ces OS en limitant au maximum les processus en fonctionnement pendant
les tests (serveur graphique....). En ce qui concerne les benchmarks, nous avons sélectionné les
NAS[BBB+ 91][JJF+ 99] et EulerMHD, un solveur de magnétohydrodynamique 2D sur maillage
cartésien développé en MPI[DEJ+ 10]. Les sections suivantes donnent donc les résultats obtenus
sur ces applications.
3. Dans ce mode, la mémoire est découpée de sorte qu’une ligne de cache sur deux soit sur un nœud NUMA dif-
férent. Ceci assure donc une distribution statistiquement égale sur chacun des nœuds afin de masquer leur présence.
68
3.3. Résultats expérimentaux
30
20
10
−10
BT CG EP FT IS LU LU−HP MG SP
Benchmark
F IGURE 3.4 – Gains de performances relatifs à Linux obtenus sur la série de benchmarks NAS-SER.
Sur ce graphique, les valeurs positives montrent des gains de performances.
Ces benchmarks ont dans un premier temps été exécutés en mode séquentiel. Les résultats
obtenus et confirmés par plusieurs exécutions (de l’ordre de cinq) sont donnés dans la figure
3.4. Cette dernière représente les gains de performances relativement à Linux avec des pages
standards. On observe une amélioration des performances en faveur de F REE BSD et OpenSolaris
comparé à Linux. Les gains obtenus allant de 7% à 51%. Le benchmark EP est particulièrement
sensible à ces effets avec une amélioration des performances de 51% sur OpenSolaris et 19%
sous F REE BSD. Les benchmarks dont les performances sont réduites sur ces OS ne voient en
comparaison leurs performances diminuer de 5% sous F REE BSD et OpenSolaris.
Le graphique donne également des résultats obtenus avec les Transparent Huge Pages (THP)
disponibles sous Linux. Ces dernières ont été utilisées en activant leur support en mode perma-
nent, impliquant l’usage de grosses pages de manière implicite pour toutes les allocations. La
figure 3.4 montre clairement la corrélation des résultats de cette politique de pagination avec
ceux obtenus sur F REE BSD. On notera toutefois que l’on n’obtient pas strictement la même po-
litique puisqu’elle ne s’applique que pour les segments plus larges qu’une grosse page (2 Mo) et
alignés sur ces dernières. Pour les parties de segment non entièrement couvertes par de telles
pages, Linux maintient sa politique d’allocation aléatoire qui diffère des autres OS. Ceci explique
les différences de résultats observées sur les benchmarks EP et IS.
En ce qui concerne le mode séquentiel, on note une amélioration moyenne des performances
de 7% par rapport aux pages standards de Linux. On montre donc que la politique de Linux
semble pouvoir être améliorée. Comme les NAS sont centrés sur l’utilisation du processeur, nous
pouvons supposer que les écarts observés viennent de l’ordonnanceur ou du système de gestion
mémoire, non du système d’entrées/sorties. Comme nous avons limité l’activité de l’ordonnan-
ceur, nous pouvons raisonnablement supposer que le gestionnaire mémoire est l’une des sources
principales des effets observés. Cette supposition est renfoncée par les corrélations obtenues sur
les résultats avec les grosses pages de Linux.
Par défaut, OpenSolaris n’utilise pas de grosses pages, mais uniquement une politique de
coloration. Comme nous observons aussi des améliorations notables sur cet OS, nous pouvons
admettre que la réduction des TLB n’est pas l’effet dominant dans nos observations. Nous sup-
posons donc que les effets proviennent de l’interaction de la politique de pagination avec les
caches associatifs. Nous verrons dans la suite que cet argument est largement confirmé par les
résultats obtenus avec l’application EulerMHD.
69
Chapitre 3. Interférences des mécanismes d’allocations
La figure 3.5 fournit les résultats obtenus avec les NAS en mode MPI sur 8 processus. Dans
cette configuration, on peut observer une dégradation importante des performances avec des ra-
lentissements de l’ordre de 30%. Ce comportement peut-être également observé avec les classes
S, W et A en activant les grosses pages sous Linux, éliminant une fois de plus les politiques
d’ordonnancement comme paramètre majeur. Les mêmes résultats sont obtenus en utilisant hw-
loc[BCOM+ 10] pour verrouiller les threads et processus sur les coeurs de manière déterministe.
Gain de performance comparé à Linux (%)
F IGURE 3.5 – Gains de performances des NAS-MPI pour 8 processus comparés aux pages standards
de Linux. Les valeurs positives montrent des gains de performances.
Afin d’obtenir une vue plus synthétisée des résultats, on peut grouper les benchmarks et
regarder les impacts extrêmes (amélioration maximum ou dégradation maximum) obtenus en
fonction du nombre de cœurs exploités. Ces résultats sont mis en forme dans la figure 3.6 mon-
trant une corrélation nette entre les différentes politiques de pagination. Avec un nombre crois-
sant de flux d’exécution, on observe que les différents OS tendent à favoriser et à dégrader
les cas pathologiques alors que les gains potentiels tendent à se réduire, principalement en ce
qui concerne les grosses pages. Ce point particulier critiquant l’impact des grosses pages ou de
certains types de coloration sera discuté plus en détail dans la suite à la lumière des résultats
obtenus avec l’application EulerMHD.
Gain max. de perf. comparé à Linux (%)
Gain min. pour NAS−MPI,OMP CLASS=A,B,C Gain max pour NAS−MPI,OMP CLASS=A,B,C
Gain min. de perf. comparé à Linux (%)
0 60
−10 50
−20
40
−30
−40 30
−50
20
−60
−70 10
−80 OpenSolaris 0
−90 FreeBSD 1 2 4 8 16
Linux + THP Nombre de threads/processus
−100
1 2 4 8 16 OpenSolaris Linux + THP
Nombre de threads/processus FreeBSD
(a) (b)
F IGURE 3.6 – Représentation des (a) gains et (b) pertes extrêmes de performances pour l’ensemble
des benchmarks MPI en fonction du nombre de threads/processus utilisés. Ces résultats agrègent les
classes A,B et C. Des valeurs positives impliquent des gains de performances.
70
3.4. Pagination et stratégie de malloc
On remarquera que les effets des grosses pages de Linux sont systématiquement en retrait par
rapport aux résultats des autres OS. Cela s’explique par les effets de seuils liés à leur intégration
partielle dans l’OS et le maintien d’une pagination aléatoire en dessous de ces seuils.
(a) EulerMHD, 1 processus MPI, allocateur de OS (b) EulerMHD, 8 processus MPI, allocateur de l’OS
500 140
450
120
Temps d’exécution (s)
F IGURE 3.7 – Temps d’exécution de l’application EulerMHD sur les différents OS (a) en séquentiel
(b) avec 8 processus MPI.
71
Chapitre 3. Interférences des mécanismes d’allocations
peut trouver des remarques similaires dans les documentations de Nvidia quant à l’utilisation
de certaines mémoires du GPU[RM09] pour l’implémentation de multiplication de matrices. Ces
études travaillent plus généralement sur la notion de tableau en négligeant la présence de l’al-
locateur. Nous allons donc étendre leurs remarques en prenant en compte ce paramètre comme
cela est discuté dans la publication [ADM11] réalisée en parallèle de nos travaux.
Rappelons que pour nos expériences nous avons gardé la LIBC de chacun des systèmes et
donc maintenu leurs allocateurs mémoires (malloc) respectifs. Un simple test prouve que les
alignements mémoires des grands tableaux d’EulerMHD diffèrent d’un OS à l’autre. On pourra
trouver les données en annexe B. On remarque ainsi que sous Linux, les tableaux plus grands
que 128 Ko sont alloués directement par un appel à mmap. Cette méthode implique que chacune
de ces allocations s’aligne sur le début d’une page avec un décalage de 16 octets lié à l’en-tête
ajouté par l’allocateur. Sur F REE BSD, les gros tableaux tendent à être alignés directement sur
les limites des grosses pages (2 Mo)[Eva06]. À l’opposé, OpenSolaris tend à utiliser une distri-
bution, qui dans le cas d’EulerMHD s’avère plus aléatoire selon des multiples de 16 octets.
500
Temps d’exécution (s)
400
300
200
100
0
100 400 800 1000
Taille de problème
Linux
Linux + THP + alignement de 2 Mo
FreeBSD
OpenSolaris
OpenSolaris + décalage
F IGURE 3.8 – Résultats obtenus avec EulerMHD en mode séquentiel en utilisant notre allocateur
simplifié en remplacement de celui de l’OS. Sur les grosses pages Linux, nous avons délibérément
forcé un alignement sur 2 Mo. Sur OpenSolaris, nous avons également testé un mode introduisant
un décalage aléatoire multiple de 4 Ko
La figure 3.8 montre les résultats obtenus avec cet allocateur simplifié. Avec cette méthode,
F REE BSD donne des performances équivalentes à Linux. De manière similaire, le problème peut-
72
3.4. Pagination et stratégie de malloc
être reproduit sous Linux en forçant un alignement sur les grosses pages, problème qui ne se pose
pas sans l’application forcée de cette contrainte. Notre allocateur simplifié génère également le
problème sous OpenSolaris. Toutefois, le problème disparaît si l’on ajoute manuellement un dé-
calage aléatoire multiple de 4 Ko aux adresses générées par ce dernier. Une analyse approfondie
du fonctionnement d’OpenSolaris montre que les requêtes mmap au delà de 1 Mo sont automa-
tiquement alignées sur 2 Mo au lieu des 4 Ko habituellement utilisés sous Linux et F REE BSD.
L’ajout de décalages aléatoires permet donc de réduire l’alignement de 2 Mo à un alignement
de 4 Ko et de corriger le problème. On démontre ainsi l’importance du choix de placement des
segments dans l’espace virtuel. Les NAS utilisent essentiellement des allocutions statiques, cette
méthode ne permet donc pas de mettre en évidence des changements de performance sur ces
derniers.
Mémoire virtuelle
Mémoire physique
F IGURE 3.9 – Exemple de conflit lié à certains alignements en mémoire virtuel en conjonction d’une
politique de coloration régulière sur un cache associatif à 2 voies et un accès à 3 tableaux alignés
sur 2 Mo.
Le problème se pose de la même manière sur une coloration de pages régulière, c’est à dire
produisant un motif répété sur l’ensemble de l’espace virtuel et aboutissant à une relation linéaire
entre les adresses virtuelles et les positions en caches. Ceci explique l’observation du phénomène
sous OpenSolaris. Ce cas de figure est illustré par la figure 3.9 en considérant un cache associatif
à 2 voies. Sous Linux, avec une pagination aléatoire, le déplacement d’un élément de 4 Ko dans
l’espace virtuel ne change statistiquement pas sa position dans le cache. Une page aléatoire est
73
Chapitre 3. Interférences des mécanismes d’allocations
en effet remplacée 4 Ko plus loin par une autre page aléatoire. Dans ce contexte, on comprend
que Linux ne soit pas affecté par le problème observé sur les deux autres OS.
Nous pointons ainsi une limite des techniques de coloration de pages exploitées par F REE BSD
et OpenSolaris. Avec ces colorations que nous dirons régulières, la fonction malloc devient sen-
sible à l’associativité des caches au-delà de la taille standard des pages. Ces décisions peuvent
alors conduire à des interférences avec la politique de l’OS. Nous verrons en section 3.5.3 les
implications sur le design des allocateurs.
Ce phénomène explique les pertes de performances observées sur les NAS parallèles en sec-
tion 3.3.3 l’effet parallèle plus marqué sur EulerMHD. Comme ces derniers utilisent des adresses
statiques, en mode MPI, toutes les instances vont avoir tendance à utiliser les mêmes adresses.
Sur une pagination régulière, on observera l’effet discuté précédemment, augmentant la pres-
sion sur les caches à mesure que l’on augmente le nombre de flux d’exécution. Pour mettre en
évidences les limites du problème, nous étudions ici les performances du code 3.1 en considé-
rant un nombre variable de tableaux et en répétant ces opérations dans différents threads.
Code 3.1– Noyau de calcul utilisé pour l’évaluation des effets d’alignements.
1 # pragma omp parallel
2 {
3 float ** arrays = alloc_arrays () ;
4 float * tb0 = arrays [0];
5 float * tbj ;
6 for ( k = 0 ; k < NB_REPEAT ; ++ k ) {
7 for ( j = 1 ; j < NB_ARRAYS ; ++ j ) {
8 tbj = arrays [ j ];
9 for ( i = 0 ; i < size ; ++ i )
10 tb0 [ i ] += tbj [ i ];
11 }
12 }
13 }
La figure 3.10 donne les résultats de ce benchmark. En fonction de l’alignement des tableaux,
il est possible d’observer des pertes de performance d’un facteur 2 si l’on utilise plus de tableaux
que l’associativité ne le permet. Éliminer le facteur d’alignement permet d’assurer des perfor-
74
3.4. Pagination et stratégie de malloc
Cycles par element pour des pages de 2Mo avec 4 threads OpenMP Accès sequentiels vs. OpenMP sur pages de 2M
utilisation de 8 threads sur 4 cores
5
4.5
Gap des addresse de base des tableaux (Ko)
14
400 4
12
3.5 10
300 3 8
2.5 6
200
2 4
1.5 2
100
1 0
0 10 20 30 40 50 60 70
Nombre de tableaux par thread
0.5
5 10 15 20 Seq. (gap=512k) Seq. (gap=500k)
OMP (gap=512k) OMP (gap=500k)
Nombre de tableaux par thread
(a) (b)
F IGURE 3.10 – Exécution du code 3.1 avec 4 threads sur I NTEL N EHALEM en utilisant des grosses
pages (a). Les tableaux sont dimensionnés pour que les données manipulées par chaque thread
tiennent dans les 32Ko de leur cache L1 respectif. Rappelons que le cache L3 de 8Mo dispose de 16
voies de 512Ko. Le graphique (b) donne une coupe horizontale (gap = 500 Ko et gap = 512 Ko)
pour mieux observer les effets des threads.
mances décentes même en exploitant 64 tableaux, c’est à dire bien plus que l’associativité de
16 du cache L3 du processeur. On montre donc qu’il est possible d’intervenir au niveau de la
politique d’allocation pour prévenir ou limiter l’apparition de ces cas pathologiques.
Du fait du modèle superscalaire 4 utilisée par ces processeurs, l’itération i+1 génère un char-
gement de Y [i] alors que l’opération X[i] de l’itération i est encore dans le pipeline d’exécution.
Si les tableaux X et Y ont les mêmes adresses de base modulo 4Ko, le détecteur de dépendance
considérera qu’il y a conflit et mettra l’instruction en attente. Cela peut être observé avec le
4. Rappelons que les architectures superscalaires peuvent exécuter plusieurs instructions simultanément si elles
utilisent des unités de traitement différentes et qu’il n’y a pas de dépendances entre ces instructions.
75
Chapitre 3. Interférences des mécanismes d’allocations
Evénements LOAD_BLOCK_OVERLAP_STORE
TEmps d’exécution
LOAD_BLOCK_OVERLAP_STORE
12 6e+07
10 5e+07
Cycles par boucle
8 4e+07
6 3e+07
4 2e+07
2 1e+07
0 0
0 5 10 15 20 25 30 35
Décalage
compteur matériel 5 LOAD_BLOCK.OVERLAP_STORE sur Core 2 Duo. Comme cela est montré
sur la figure 3.11, ce type de problème peut conduire à un ralentissement du code d’un facteur
supérieur à 2.
Sur architecture Nehalem et Sandy Bridge, le problème est résolu pour l’exemple précédem-
ment, mais nous observons qu’il reste présent pour des cas plus compliqués avec plusieurs flux
mémoires à problèmes tels que donnés dans le code 3.3.
Code 3.3– Accès plus complexe ayant des problèmes de concurrence lecture/écriture.
1 for ( i = 1 ; i < SIZE ; ++ i ) {
2 X1 [ i ] = Y1 [i -1]
3 X2 [ i ] = Y2 [i -1]
4 }
Sur un cas réel, nous avons observé qu’il était possible d’obtenir des gains de performance
aussi bons en désalignant les tableaux qu’en faisant des optimisations complexes du code. La
table 3.2 donne les mesures effectuées sur Core 2 Duo avec ce code. La version optimisée ma-
nuellement offre une meilleure performance, plus stable en fonction des architectures. Elle a
toutefois nécessité beaucoup plus d’effort et abouti à un code peu lisible non nécessairement
compatible avec une maintenance dans la durée de vie d’un code massif.
Ce problème connu est déjà discuté sur les problèmes de piles [MDHS09], mais nous dé-
montrons ici que les politiques de l’allocateur peuvent conduire au même problème. Ceci est
particulièrement vrai dans le cas où ce dernier tend à aligner les grands tableaux sur les débuts
de pages comme c’est le cas par défaut sur la quasi-totalité des allocateurs utilisant mmap pour
ces segments. La glibc de Linux génère ce type de placement à risque pour tous les tableaux dé-
5. Ces compteurs permettent de suivre certains phénomènes survenant directement à l’intérieur du processeur,
on y accédera par exemple avec l’outil Likwid, VTune ou perf.
76
3.4. Pagination et stratégie de malloc
Originale Optimisée
Allocateur standard 51.0 21.7
Tableaux décalés 21.8 21.3
TABLE 3.2 – Évaluation de performance d’une fonction optimisée et sa version d’origine. Les perfor-
mances sont données avec l’allocateur standard ou en modifiant l’alignement des tableaux utilisés.
Les temps sont donnés en cycles processeurs par itération, les valeurs faibles indiquent donc un gain.
passant 128 Ko. Éviter ce type d’alignement pourrait permettre de maintenir des performances
décentes en limitant l’apparition de ce type de cas pathologiques dépendants de la micro archi-
tecture. Les fonctions d’un programme ne méritent en effet pas nécessairement des corrections
lourdes et risquées au niveau du code des programmes.
Alignements au-delà de 4 Ko
De manière similaire aux tests précédents, nous allouons des tableaux avec des alignements
induisant des effets de résonances et y appliquons des opérations simples pour évaluer les per-
formances d’accès. Pour ce test, nous étudions les alignements au-delà de la taille d’une page,
nous allouons donc des tableaux directement avec mmap pour forcer le placement en mémoire
virtuelle en respectant la distribution suivante :
Avec base_address un point fixe pour l’ensemble des tableaux, array_id un identifiant de tableau
débutant à 0, alignement l’alignement visé (multiple de 4 Ko). Le noyau de calcul est donné par
le code 3.4.
Code 3.4– Noyau utilisé pour tester les TLB avec un nombre variable de trableaux.
1 for ( int i =0; i < SIZE ;++ i )
2 a [ i ] = b [ i ] + c [ i ] + d [ i ]....;
La figure 3.12 est obtenue en échantillonnant les alignements (en mémoire virtuelle) par
puissances de deux au-delà de 4Ko et ce jusqu’à plusieurs Go. Cette figure montre clairement
l’apparition de différents niveaux de performances. On y distingue clairement sur Core 2 Duo
les niveaux à 256 kB et 1 GB ; sur Core i7 : 64 kB, 512 kB et 1 GB. Ici nous ignorons le cas à
32M o pour lequel nous n’avons pour l’instant pas d’explication confirmée. On remarquera que
le problème n’apparaît que dans le cas d’utilisation de plus de 4 tableaux et uniquement pour
les alignements multiples cités précédemment, la structure lissée de la courbe n’apparaît sous
cette forme que parce que notre échantillonnage suit ces multiples par puissance de deux.
77
Chapitre 3. Interférences des mécanismes d’allocations
Utilisation d’alignements identiques sur Core 2 Duo Utilisation d’alignements identiques sur Core i7
2.5 0.8
Temps d’exécution (cycles/boucle)
1.5 0.5
0.4
1 0.3
0.2
0.5
0.1
0 0
100K 1M 10M 100M 1G 10G 100K 1M 10M 100M 1G 10G
Alignement des tableaux en espace virtuel Alignement des tableaux en espace virtuel
(a) (b)
F IGURE 3.12 – Impact de l’alignement relatif des tableaux au-delà d’une page en utilisant le code
3.2 sur C ORE 2 D UO (a) et C ORE I 7 (b).
mer cette hypothèse, nous pouvons explorer les compteurs matériels pour ces différents paliers.
La figure 3.13 donne les résultats de ces expériences sur Core 2 Duo en donnant les écarts entre
une mesure alignée et non alignée. Une valeur non nulle indique donc que nous avons identifié
une source du problème.
Différences d’occurences : aligné − désaligné
600000
400000
200000
−200000
_L
D RE NY LD ST SS T PL PL LL E
SS TO _A S_ S_ MI VIC _RE RE _A OR
MI _ S E S M I S
M I S
LB _
M _E
M D _ R E
I S _C
0_ P SS _ _ T _ 1 O
_L LA MI ES ES _D D_ L1
D L
S_
C
_T
H
ER B_ SS SS ED L1 HI IN
SES O V L M I M I I R _ T S _
MI
S K_ DT B_ B_ ET _IN IN
E
B_ L OC D TL D TL D _R ES _L
L A I N M
DT _B LO _L L2
_
AD M_ L2
LO M E
Compteurs matériels
F IGURE 3.13 – Exécution du benchmark précédent en utilisant les compteurs matériels pour les
alignements relatifs 4kB, 32kB, 512kB et 4GB. Le graphique représente les valeurs des compteurs
soustraites de la part présente pour le cas non aligné.
Pour analyser ces données, rappelons que les architectures Core d’Intel disposent de plu-
sieurs niveaux de TLB décrits dans la table 3.3. Pour nos analyses, nous étudions uniquement
les effets relatifs aux TLB de données (DTLB) et non ceux dédiés aux instructions (ITLB), ces
dernières n’ayant pas de liens étroits avec les allocations dynamiques.
Les données de la figure 3.13 montrent que le niveau à 512Ko sur Core 2 Duo est lié à une
augmentation des fautes de TLB au niveau du DTLB1. En effet, si les tableaux sont distants de
256 Ko (ou multiples), avec une associativité de 4, nos huit tableaux essayent d’utiliser deux fois
78
3.4. Pagination et stratégie de malloc
TABLE 3.3 – Configuration des TLB des architectures C ORE 2 et C ORE I 7. Extrait de la documenta-
tion Intel[Int10a]. Chaque cœur exploite ses propres TLB.
chaque entrée du TLB et génèrent donc des conflits. Même remarque sur Core i7, les niveaux
correspondants à la structure différente des TLB, notamment l’ajout d’un niveau unifié (STLB).
La raison spécifique au problème de DTLB0 à 32k sur Core 2 Duo n’est pas confirmée. Ce der-
nier pourrait s’expliquer si le DTLB0 est directement associatif, mais cette information n’est pas
précisée dans les documents Intel[Int10a, Int10b].
Pour confirmer notre hypothèse, nous pouvons remarquer que si les PDE expliquent les pertes
de performance, alors la position absolue dans l’espace virtuel devient un paramètre important.
Cette position guide en effet la position des entrées en conflits vis-à-vis des limites d’adres-
sage des PDE. Nous pouvons donc revenir au micro benchmark 3.4, y utiliser un alignement de
512Mo et déplacer l’adresse de base du tableau pour balayer une bande d’adresse. Le croisement
des frontières des PDE devrait donc être visible sur les performances. En utilisant 8 tableaux de
4 Ko alignés sur 512 Mo nous couvrons donc un espace 3.5 Go. En fonction de la position relative
aux PDE l’adressage de ces tableaux, l’adressage nécessite un total de 4 ou 5 PDE. Ceci donne
les adresses décrites dans le code 3.5 pour base_address = 4 Go et alignment = 512 Mo.
79
Chapitre 3. Interférences des mécanismes d’allocations
Code 3.5– Positionnement des tableaux pour une mise en évidence de l’impact des PDE.
1 addr_array [0] = base_address = 4 Go
2 addr_array [1] = base_address + 1 * alignment = 4.5 Go
3 addr_array [2] = base_address + 2 * alignment = 5 Go
4 addr_array [3] = base_address + 3 * alignment = 5.5 Go
5 ...
1.8
1.6
1.4
Temps par élément
1.2
0.8
0.6
0.4
0.2
Gap de 512 Mo entre les tableaux
0
4 4.5 5 5.5 6 6.5 7 7.5 8
Adresse de base en Go
F IGURE 3.14 – Déplacement des données dans l’espace virtuel afin de croiser un nombre variable
de frontières des PDE. Le benchmark utilise 8 tableaux de 4 Ko distribués de manière à couvrir une
zone de 3.5 Go de mémoire virtuel en utilisant un gap de 512 Mo. En fonction du placement, ces
segments nécessitent 4 ou 5 PDE pour être adressés.
La figure 3.14 montre le résultat de ce test en déplaçant les données dans l’espace virtuel
pour croiser les limites des PDE. Pour une adresse de base de 4 Go à 4.5 Go l’espace mémoire
utilisé est couvert par 4 PDE. Par contre entre 4.5 et 5Go le recouvrement nécessite une PDE de
plus, donc un coût d’accès supérieur. Ajouter 512 Mo fait revenir à la situation initiale. Les ré-
sultats expérimentaux confirment donc bien que les effets d’alignement au-delà du Go sont liés
au dernier niveau de la table des pages. Rappelons toutefois que ce problème ne se pose qu’en
conjonction de lecture répétée de la table, donc cumulé avec les problèmes précédemment évo-
qués. Ce problème particulier lié à des alignements de l’ordre du Go a donc très peu de chance
de survenir en pratique et peut être ignoré. Il ajoute toutefois un argument visant à considérer
les alignements trop réguliers comme source de problèmes.
80
3.5. Analyse générale et recommandations
locateur. Résumons ici ces derniers avant de poursuivre sur une série de recommandations ap-
plicables à chacun des deux niveaux de gestion de la mémoire (OS et malloc). Ces problèmes
sont essentiellement étudiés en considérant l’utilisation de gros segments mémoires (plusieurs
centaines de Ko). Un tableau récapitulatif pourra être trouvé en annexe B.4.
Fuite de caches : Nous avons dans un premier temps (section 3.1) étudié le problème de la
coloration de pages sur son plan historique. Pour ce faire, nous avons initialement observé
des effets connus de perte d’efficacité du cache liée aux politiques de paginations aléatoires
de la part de l’OS. Nous avons également vu que Linux entrait dans cette catégorie.
Grosses pages : Nous avons ensuite étudié une amélioration potentielle apportée par les grosses
pages (section 3.2.3) et avons montré que ces dernières tendaient à amplifier les effets pé-
nalisants de cas pathologiques. Nous avons notamment montré que dans ce contexte, l’al-
locateur devenait responsable de la prise en compte des caches pour le placement des gros
tableaux. Ce point particulier n’est explicitement traité par aucun des allocateurs actuels.
Avec l’application EulerMHD, nous avons également montré (section 3.3.4) que l’alloca-
teur de F REE BSD appliquait une règle tendant à générer ces cas pathologiques alors même
que cet OS offre un support natif des grosses pages.
Coloration de pages régulière : Au cours de nos analyses, nous avons également montré que
les politiques de coloration de pages proposées par OpenSolaris tendaient à produire les
mêmes effets néfastes que les grosses pages en rendant les décisions de la fonction malloc
sensible aux caches.
Effet des TLB : Sur la fin de notre étude, nous avons (section 3.4.5) également mis en évidences
quelques effets liés à la forme associative des TLB dans le cas ou l’allocateur générerait des
alignements particuliers entre les tableaux qu’il fournit à l’utilisateur.
Effet de la table des pages : En poussant le raffinement, nous montrons également qu’il est
possible d’observer quelques rares effets liés à la structure de la table des pages. Nous
considérons toutefois qu’il est peu probable d’observer ces derniers dans une application
réelle du fait des échelles en jeux (alignement de l’ordre du Go).
De manière générale, nous avons rappelé que les paginations aléatoires de type Linux ré-
duisaient l’efficacité des caches. Toutefois, nous avons montré que les techniques de coloration
de pages actuellement mise en place pour corriger ces effets peuvent s’avérer inefficaces. Cette
inefficacité apparaît parce que ces techniques tendent à générer au niveau de l’OS des motifs
réguliers déléguant la responsabilité d’utilisation des caches à l’espace utilisateur. Ce dernier
point est une bonne chose pour une application optimisée finement par des spécialistes. Il est
toutefois clair qu’elle peut devenir problématique pour le développement d’applications mises
au point par des développeurs moins experts ou dont les priorités ne sont pas orientées sur l’op-
timisation fine dépendante du matériel.
Dans ce contexte, nous pensons qu’il est possible de faire certains efforts au niveau du sys-
tème d’exploitation et de l’allocateur pour limiter les problèmes observés en trouvant un com-
promis entre les méthodes actuellement utilisées. Dans tous les cas, la conception de l’allocateur
doit prendre en compte la politique de pagination sous-jacente et ne peut donc la considérer
comme étant une simple boîte noire.
81
Chapitre 3. Interférences des mécanismes d’allocations
intellectuellement satisfaisante au problème. Au vu de nos résultats, il semble clair que les tech-
niques de coloration actuellement employées génèrent autant de nouveaux problèmes qu’elles
n’en règlent. Cela peut expliquer les avis mitigés observés dans de nombreuses publications trai-
tant de l’implémentation de ces techniques[HK, BKW98] en dehors de certains cas particuliers.
Pour des accès strictement aléatoires, nous pouvons considérer les différentes politiques de
pagination comme équivalentes. En revanche pour des accès plus linéaires, nous pouvons propo-
ser de trouver un meilleur compromis. Une certaine maîtrise du processus d’allocation des pages
est nécessaire pour ne pas aboutir aux défauts d’une pagination aléatoire, néfaste pour des accès
linéaires. Ces techniques de contrôle des pages physiques ne doivent toutefois pas conduire à
l’apparition trop aisée de phénomènes de résonances tels que nous l’avons observé. Pour cela
nous préconisons d’utiliser des méthodes de coloration évitant l’apparition de schémas réguliers
et répétitifs sur l’ensemble de l’espace d’adressage. Ceci est surtout vrai s’ils sont synchrones
avec les frontières des voies du cache. Dans ce sens, afin d’éliminer les effets intra-processus, il
est possible de complexifier les fonctions de hachages comme cela a été fait par l’introduction
du PID pour éliminer les effets inter-processus.
82
3.5. Analyse générale et recommandations
D’une manière générale nous pouvons conseiller d’éviter de produire artificiellement des ali-
gnements sur des ordres trop élevés afin d’éviter de faire apparaître par défaut des résonances
potentielles sur les paginations régulières (grosses pages ou coloration régulière). Ce type de
politique tend malheureusement à être la méthode employée par défaut par certains allocateurs
comme jemalloc[Eva06] de F REE BSD qui tend à forcer l’alignement des grosses allocations sur
2Mo. Nous avons également observé qu’OpenSolaris effectue ce type d’opération au sein même
de la fonction mmap, impliquant ce type de comportement par défaut pour tout allocateur ap-
pelant mmap sans adresses pour l’allocation de gros segments. Sur ce type d’OS, l’allocateur doit
donc prendre en main explicitement ses alignements. Nous pensons que ce type de politique au
niveau de mmap est à prohiber bien que permettant le placement en mémoire d’un plus grand
nombre de grosses pages. Ce problème est à surveiller au niveau de Linux qui tend actuellement
à voir un développement de sa politique de gestion des grosses pages.
D’autre part, si les problèmes étudiés précédemment concernaient principalement les caches
indexés physiquement (L2 et L3), il importe de rappeler que les caches L1 des processeurs
tendent à utiliser un découpage correspondant exactement à la taille d’une page (4Ko). Il
convient donc de noter qu’aligner les grands tableaux en début de page suite à un appel à
mmap peut conduire à une perte d’efficacité de ce cache dès lors que l’application utilise plus
83
Chapitre 3. Interférences des mécanismes d’allocations
de tableaux que l’associativité ne le permet. Ce point est d’autant plus fâcheux qu’un simple
décalage permet comme nous l’avons vu en section 3.4.1 de réduire très largement les pertes de
performances. Ce type d’alignement est toutefois généré par la majorité des allocateurs comme
cela est critiqué dans [ADM11].
3.6.1 Objectifs
Dans ce chapitre, nous avons montré que les paramètres clés des problèmes étudiés étaient
l’adresse de base et le nombre de tableaux utilisés simultanément dans les boucles. Notre outil se
propose donc d’extraire ces paramètres pour chaque fonction d’une application.
Ici, nous ne nous intéressons qu’aux grands segments mémoires, au-delà de 4 Ko. De plus,
ne seront analysés que les segments dynamiques alloués par le biais des fonctions malloc, calloc
et realloc. Notre approche sera basée sur une instrumentation de l’exécutable et une collecte
d’information pendant l’exécution du programme. Afin de ne pas tomber dans des problèmes
de volumes de données, nous limiterons la prise d’information à une forme échantillonnée. Les
entités fondamentales seront constituées des fonctions et des blocs alloués. Nous n’analyserons
donc pas les accès détaillés à l’intérieur des blocs eux-mêmes ou bien la prise en compte de
présence de plusieurs boucles dans une même fonction.
84
3.6. Outil d’analyse
Chaque entrée/sortie de fonction nécessite une remise en place des verrous d’accès aux
tableaux.
Système de liste noire : Avec les points précédents nous générons potentiellement un nombre
trop important de données et d’appels système donc un surcoût d’exécution important
proportionnel au nombre d’entrées/sorties de fonction. Pour simplifier le problème, nous
avons appliqué une méthode d’échantillonnage limitant le nombre d’analyses réalisées
sur une fonction donnée. Une fois ce seuil d’analyse dépassé, la fonction concernée est
placée dans la liste noire et ne nécessitera plus de verrouillage d’accès aux tableaux. Le
programme est donc fortement ralenti lors des premiers appels de fonction puis reprend
une cadence normale d’exécution uniquement impactée par le surcoût d’instrumentation.
Pour être efficace, la liste noire dispose de l’équivalent d’un cache maintenant les dernières
entrées récemment utilisées.
Avec cette approche sélective et une implémentation naïve des fonctions de liste noire, nous
obtenons un surcoût d’un facteur 2 pour de petites exécutions d’EulerMHD. Ce dernier se réduit
toutefois à 30% pour des cas tests de plus grande taille toujours avec EulerMHD. L’approche
retenue à base de signaux de type faute de segmentation implique toutefois que le prototype
n’est pas utilisable en contexte multithread. Les protections des segments sont en effet globales
au processus. Il n’est donc pas possible de maintenir un verrouillage des accès pour un thread
donné. Cette approche nous permet néanmoins de trouver rapidement les fonctions à problème
pour les programmes séquentiels et MPI.
Comme discuté, la méthode précédente n’est pas applicable sous cette forme en context
parallèle. Pour supporter ce type d’application il faudrait recourir à une émulation (par exemple
avec valgrind[NS07]) ou instrumentation des accès (MAQAO[BCRJ+ 10], Pintool[HLC09]). Une
autre possibilité serais d’exploiter certaines propriétés de la segmentation mais elle n’est plus
disponibles sur les architectures intel 64 bits. Dans le cadre de notre étude, nous nous somme
limité au prototype séquentiel.
85
Chapitre 3. Interférences des mécanismes d’allocations
Avec les données collectées, il est possible d’extraire un résumé d’utilisation des tableaux
pour chacune des fonctions. Sur un simple programme test, il est par exemple possible d’obtenir
la sortie du code 3.6. Cette sortie fournit les informations suivantes :
Section ALLOC ligne 1-5 : Liste les allocations effectuées par les différentes fonctions. Chaque
allocation est alors associée à un ID unique utilisé pour suivre son historique et caractérisé
par sa taille. Les nombres entre crochets donnent respectivement les alignements relatifs
aux pages de 4Ko et 2Mo, permettant une analyse rapide des problèmes d’alignement.
Section FREE ligne 6-10 : Donne les points de libérations des tableaux.
Section MEM USAGE ligne 11-24 : Cette section liste les tableaux utilisés par les différentes
fonctions du programme en donnant le nombre d’appels de ces fonctions et le pourcen-
tage de temps consommé par ces dernières. Sont alors listés chacun des tableaux utilisés
identifiés par leur ID et en rappelant leurs paramètres (taille, alignement). Ces informa-
tions sont complétées par le décalage du premier élément utilisé pouvant potentiellement,
permettre une détection de certains problèmes de conflits lecture/écriture décrits en sec-
tion 3.4.4.
On peut alors générer un graphique plaçant les points de chaque fonction dans un repère
construit sur le nombre de tableaux accédés et le temps relatif des fonctions. Il est ainsi possible
de repérer rapidement la présence de zones à problème ayant un impact potentiellement signi-
ficatif sur les performances (nombre de tableaux supérieur à l’associativité avec un temps relatif
important). Sur EulerMHD on constate ainsi aisément la présence d’une fonction exploitant 9
tableaux et occupant plus de 50% du temps d’exécution (figure 3.3.4). Cette visualisation peut
également permettre de retrouver rapidement les fonctions impactées en comparant deux exé-
cutions superposées sur le même graphique, l’une utilisant des alignements standards, l’autre
des alignements aléatoires. Il pourrait bien sûr être envisagé de construire un greffon de ce type
pour Valgrind en bénéficiant des bases fournies par cet outil. L’important dans notre approché
est de profiter des adresses de base et tailles de bloc extraites de l’allocateur mémoire. Ces infor-
mations permettent d’associer une certaine sémantique aux adresses accédées par le programme
en ne pas les considérer comme de simples données éparses.
D’un point de vue pratique, on se heurte toutefois à la difficulté de trouver un moyen simple
et efficace d’associer un tableau à une information extraite d’un profile d’une exécution précé-
dente. Il ne paraît pas raisonnable de remontrer la pile d’appels pour chaque allocation. Nous
avons donc préféré tester diverses heuristiques de génération d’alignements ne nécessitant pas
de profil. À titre de comparaison, sur un programme simple nous avons tout de même mis en
place une méthode basée sur l’ordre d’allocation des tableaux. Cette méthode basique permet
86
3.8. Conclusion
0.1
0.01
0.001
0.0001
0 5 10 15 20 25
Nombre de tableaux utilisés par la fonction
F IGURE 3.15 – Distribution de l’utilisation mémoire des fonctions du programme EulerMHD sur la
base du temps d’exécution relatif des fonctions et du nombre de tableaux manipulés. Remarquons
que la distribution est pour ce programme indépendante de la taille du problème.
ainsi d’évaluer les gains potentiels d’un apport d’information extérieur. L’alignement de l’adresse
de base du tableau est choisi parmi un intervalle de [0, 4Ko[ selon les règles qui suivent :
Aléatoire : Les valeurs sont choisies aléatoirement avec un pas de 16 ou 64 octets.
Incrément : Les valeurs sont choisies selon une méthode tourniquet en incrémentant une va-
riable globale de 16 ou 64 octets.
Groupe : L’algorithme génère des groupes rassemblant les tableaux utilisés simultanément dans
les différentes fonctions comptant pour plus que 1% du temps d’exécution total. Les groupes
ayant des tableaux communs sont fusionnés de sorte à agréger les tableaux en relation
pour le programme dans son ensemble. Chaque groupe est alors associé à un décalage
global et les alignements des tableaux sont répartis de sorte à être dispersés au sein de
l’espace [0, 4Ko[ avec un pas minimum de 16 ou 64 octets.
Les résultats expérimentaux montrent toutefois (figure 3.16) que le choix d’une politique
strictement aléatoire conduit au meilleur gain, obtenant des performances aussi bonnes qu’une
méthode beaucoup plus lourde basée sur l’exploitation de profils. Remarquons qu’empirique-
ment l’utilisation d’une discrétisation par pas de 64o de l’espace des alignements possible semble
apporter les meilleurs résultats. Cette observation est cohérente avec l’utilisation de lignes de
cache de 64 octets par le matériel.
3.8 Conclusion
Dans ce chapitre, nous avons étudié en détail les problèmes d’interférences pouvant surve-
nir entre les politiques de gestion de la mémoire au niveau de l’OS et celles mises en place au
niveau de l’allocateur. Nous avons rappelé le problème de fuite de cache observé sous Linux et
traité par des méthodes de coloration de pages par d’autres OS. Ces approches sont souvent dé-
crites dans les théories des mécanismes de pagination. Nous avons toutefois montré que le choix
87
Chapitre 3. Interférences des mécanismes d’allocations
400
300
Temps (s)
200
100
d’une méthode de coloration n’était pas sans conséquence et que les techniques habituellement
employées impliquaient une prise en compte explicite du problème au niveau de l’allocateur
mémoire en espace utilisateur (malloc).
Nous avons également observé que les allocateurs actuels tendent à prendre des décisions
conduisant par défaut aux pertes de performances observées dans ce chapitre. Il en ressort que
la méthode aléatoire exploitée par Linux évite ce type de problème montrant notamment en
parallèle une plus grande résistance à ces cas pathologiques. Certaines améliorations ont donc
été proposées tant au niveau des politiques de coloration qu’au niveau de l’allocateur, les deux
pouvant être utilisées de manière complémentaire. Remarquons que l’étude [ADM11] décrit le
problème de placement des macros blocs de manière générique, mais ne traite pas de leur inter-
action avec la politique de pagination sous-jacente.
Dans la suite, nous allons discuter les problématiques entourant le développement d’un allo-
cateur parallèle avec support NUMA. Nous nous intéresserons alors aux performances des fautes
de pages pour l’allocation de grands tableaux nécessaires en HPC.
88
Chapitre 4
Dans le chapitre précédent, nous nous sommes attachés à étudier les interactions pouvant
s’établir entre la politique de l’OS et l’allocateur mémoire en terme de choix des adresses. Ici,
nous allons décrire la mise en place d’un allocateur parallèle dans le cadre du projet MPC. Nous
décrirons donc dans un premier temps les contraintes prises en compte et l’état des lieux des
allocateurs disponibles. Une fois de plus nous nous intéresserons principalement à la probléma-
tique de gestion de grands volumes de données, notamment vis-à-vis des performances de leur
allocation par l’OS.
Nous verrons notamment qu’avec un nombre croissant de cœurs, Linux est affecté par un
problème d’extensibilité des performances de ses fautes de pages. Le problème sera traité ici
du point de vue de l’allocateur en visant à réduire l’interaction de ce dernier avec l’OS. Nous
discuterons notamment la possibilité d’établir un compromis entre consommation mémoire et
efficacité d’allocation des grands segments. Pour ce faire, nous considérerons un environnement
dans lequel nous serons amenés à faire plus attention aux problématiques de consommation.
Nous développerons également les points concernant le support des architectures NUMA.
Ces architectures nécessitent une prise en charge explicite par l’allocateur lorsque l’on fonc-
tionne en mode multithread. Nous verrons à cette occasion que MPC nous permet d’exploiter
des informations utiles, non disponibles en temps normal.
À ce titre, de nombreuses stratégies ont été évaluées au fil du temps. On pourra notamment
se référer à une étude bilan réalisée par Wilson en 1995 [WJNB95] pour obtenir une vue des
différentes techniques mises en place dans les allocateurs de l’époque. Cette étude traite notam-
ment le problème de fragmentation mémoire. Willson y décrit le problème sous la forme de trois
niveaux conceptuels. La stratégie tente d’exploiter les régularités du flux de requête. La politique
est un choix de procédure implémentable pour placer les blocs en mémoire. La mécanique est un
89
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
Nous commencerons donc par décrire les besoins particuliers auxquels on s’intéresse afin de
pouvoir construire une stratégie adaptée. Nous étudierons également les différents allocateurs
disponibles allant dans le sens de nos besoins. Nous entrerons finalement dans la description de
nos politiques et mécaniques d’allocation propres.
90
4.3. Aspects génériques des allocateurs
elle-même. Ceci du fait des politiques de pagination paresseuses utilisées par les OS mo-
dernes.
Compromis économie/performances : Nous discuterons la problématique de choix entre une
politique d’économie mémoire et d’orientation vers la performance. Nous discuterons éga-
lement la possibilité de rendre ce choix dynamique afin de s’adapter aux différentes phases
des programmes.
Segments utilisateurs : Nous décrirons la méthode annexe retenue par notre allocateur afin
d’inclure nativement la gestion de segments spécialement préparés par l’utilisateur. Cette
intégration devra, si possible, être intégrée de manière compatible avec les routines d’al-
location standards.
91
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
Une amélioration importante peut s’obtenir en construisant des listes distinctes (ségrégation)
pour différentes tailles de blocs. On obtient alors un algorithme plus proche d’un algorithme
de type best-fit sans avoir le surcoût d’un parcours complet. L’allocateur peut alors fonctionner
en imposant des tailles précises, impliquant toutefois une augmentation de la fragmentation
interne, ou bien, préférer travailler par classes de tailles approximatives.
Les fusions de blocs nécessitent la connaissance de taille des blocs voisins. Ce critère impor-
tant doit être pris en compte dans la construction des métadonnées de l’allocateur de manière à
permettre une implémentation efficace de ces actions. À ce titre, dans le cadre d’une approche
sur base de liste chaînée, l’utilisation d’algorithme first-fit avec un tri par adresse peut permettre
de mettre en commun les métadonnées de fusion et recherche de blocs libres.
Une autre approche introduite par Knuth[Kno65, PN77] dite buddy allocator consiste à n’au-
toriser qu’un nombre réduit de tailles construites sur la base d’une suite numérique. Cette struc-
ture permet des fusions et scissions rapides. On utilise habituellement des puissances de deux
(binary buddies) permettant des calculs rapides sur la base d’opérations binaires. Il est aussi pos-
sible d’utiliser des suites plus complexes (Fibonnacci...). Cette approche permet des algorithmes
performants et réduit la fragmentation externe. Il augmente toutefois significativement la frag-
mentation interne pour les grandes tailles.
La méthode extrême consiste à mettre en place une ségrégation au niveau du stockage lui-
même en interdisant le mélange de blocs de différentes tailles. Différentes régions sont alors
mises en place pour générer un nombre prédéterminé de tailles de blocs. Dans ce cas de figure,
l’allocateur n’effectue que les fusions et découpages par grands ensembles. Cette approche est
retenue dans un certain nombre d’allocateurs récents, dont les trois principaux que nous allons
étudier.
F IGURE 4.1 – Illustration du remplissage rendue obligatoire par la règle d’alignement mémoire. On
suppose ici l’allocation d’un bloc (a) de 4 octets suivi d’une allocation (b) de 8 octets ou plus.
92
4.4. Allocateurs disponibles
vérifie bien lui aussi cet alignement. Le cas est illustré dans la figure 4.1. Certains allocateurs
choisissent donc d’appliquer des politiques de ségrégation pour éviter le mélange des petits blocs
et ainsi permettre de ne pas grossir artificiellement ces derniers. Cela n’a toutefois un intérêt que
pour les blocs entre un et huit octets. Toutes les allocations de taille supérieure doivent forcé-
ment respecter cet alignement. L’utilisation des unités vectorielles (Intel SSE/AVX...) nécessite
aujourd’hui des alignements supérieurs (32 octets pour AVX), nous remarquerons toutefois que
les allocateurs génériques ne prennent pas en charge cette spécificité qui est laissée au soin des
utilisateurs au travers des fonctions de type memalign et posix_memalign.
Cette approche simple à implémenter a toutefois trois effets néfastes. En cas de dépasse-
ment de tableaux, le programme a de fortes chances de corrompre les en-têtes de l’alloca-
teur conduisant à un plantage. Ce type d’erreur est en général difficile à déboguer sans ou-
tils tels que valgrind[NS07] ou des approches par bibliothèques telles que electric-fense ou
similaires[LLC10]. Le second impact est lié à la contrainte d’alignement discutée plus tôt. Les
en-têtes doivent eux aussi satisfaire certains alignements pour être manipulés, en général huit
octets pour les adresses et tailles encodées en 64 bits. Ceci augmente donc la fragmentation
interne pour les petites allocations. Enfin, toujours dans le cas des petites allocations, l’espace
occupé par les en-têtes génère une réduction d’efficacité des caches en occupant une place, qui
idéalement serait utilisée par les données utilisateurs (rappelons que les échanges vers les caches
sont effectués sur la base d’éléments de 64 octets).
(a) (b)
F IGURE 4.2 – Illustration d’exploitation d’en-têtes placés en début de segments. Le segment (a)
illustre un cas de fragmentation interne importante lié aux contraintes d’alignement et occupation
de place de l’en-tête.
Une deuxième école consiste donc à externaliser les en-têtes en fournissant un moyen effi-
cace de retrouver ces derniers à partir de l’identifiant constitué par l’adresse de base du bloc. Ce
type d’allocateur doit toutefois résoudre le problème supplémentaire de gestion de l’espace de
stockages des métadonnées. Nous verrons un exemple avec l’allocateur Jemalloc de FreeBSD.
93
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
contexte, ce domaine a connu une reprise d’activité au milieu des années 2000 avec le dévelop-
pement de nouveaux allocateurs prenant en compte cette problématique.
Afin de familiariser le lecteur avec leurs caractéristiques propres, nous allons décrire ici le
fonctionnement de certains des allocateurs parallèles disponibles que nous utiliserons tout au
long de cette étude. Il s’agit notamment de l’allocateur Dlmalloc/Ptmalloc[Lea, Glo] fourni par
la libc Linux, Jemalloc[Eva06] fournit par FreeBSD, TCMalloc[SG] développé par Google et
Hoard[BMBW00] un allocateur ayant inspiré FreeBSD. Nous discuterons également succincte-
ment un point intéressant de l’allocateur MAMA[KK06]. Notons que nous ne décrirons pas ces
allocateurs dans tous les détails, mais nous focaliserons sur les aspects intéressants pour nos
travaux.
D’un point de vue caractéristique, cet allocateur utilise des listes doublement chaînées pour
gérer les blocs libres. Les métadonnées sont placées en bordure de bloc (début et fin). Ce type
d’approche implique une taille minimale d’allocation de seize octets, les métadonnées occupant
vingt-quatre octets (deux tailles et des bits d’états) pour des adresses en 64 bits. Les blocs libres
sont maintenus dans des listes par groupe de taille dans lesquelles l’algorithme applique une
recherche par meilleure correspondance afin de limiter la fragmentation. Cet allocateur prend
également en compte certaines considérations de localité en testant les blocs proches de l’allo-
cation précédente s’ils répondent à la requête de manière exacte afin de favoriser le voisinage
de blocs ayant des chances d’avoir des durées de vie similaires et accès simultanés.
Les versions séquentielles de l’allocateur utilisent brk pour réserver la mémoire et mmap
pour les segments au-delà d’un certain seuil (en général 128Ko ou 256Ko). L’utilisation de mmap
pour les gros segments permet d’éviter l’apparition de fragmentation externe sur des segments
de grandes tailles. Ces blocs sont libérés avec munumap. Les trous formés restent donc virtuels
et n’ont pas de conséquence sur la consommation de mémoire physique.
4.4.2 Hoard
Hoard[BMBW00] est un allocateur parallèle développé en 2000 par Emeri Berger à la suite
de sa thèse sur les allocateurs mémoires. Dans ses travaux de thèse[Ber02], il s’est surtout
intéressé à la capacité à composer rapidement et efficacement des allocateurs mémoires person-
nalisés pour les applications. Il propose alors des briques (algorithmes) de bases fournies sous
forme de templates C++. Il a ainsi construit un allocateur plus général à partir des observations
obtenues pendant ses travaux.
Cet allocateur apporte certaines notions importantes reprises par l’allocateur Jemalloc de
FreeBSD. On notera essentiellement un fonctionnement à deux niveaux avec des tas locaux et
94
4.4. Allocateurs disponibles
un tas global permettant une meilleure extensibilité. Les échanges entre tas locaux et globaux se
font par “super-blocs”, des segments de grandes tailles qui seront ensuite découpés localement.
Le problème de contention sur le tas global est supposé faible du fait de la taille importante des
super-blocs échangés (de l’ordre du Mo). Concernant le découpage des super-blocs, il introduit
également un principe de ségrégation du contenu des super-blocs en forçant un découpage de
ces derniers en blocs de tailles uniques. Les super-blocs sont échangés avec le tas global s’ils
franchissent un seuil de blocs libres de manière à limiter la surconsommation mémoire des tas
locaux. Les gros segments sont toujours traités directement par appels à mmap/munmap. Bien
qu’intéressant, nous allons voir que la version actuelle de cet allocateur supporte mal la grosse
simulation numérique utilisée pour nos tests.
4.4.3 Jemalloc
Cet allocateur a été implémenté par JASON E VANS pour F REE BSD et N ET BSD, il est aujour-
d’hui intégré par défaut dans F IREFOX et repris par FACEBOOK. Il reprend les grands principes mis
en place dans Hoard : les super-blocs et leur découpage en objets de tailles uniques. J EMALLOC,
découpe ses super-blocs en runs eux-mêmes découpés selon une taille fixe. Lors des allocations,
les run d’une classe de taille donnée sont utilisés jusqu’à leur remplissage total. Puis, un nouveau
run est choisi parmi ceux partiellement vides en suivant des règles de priorité fonction du taux
de remplissage. Cette remarque de la part de l’auteur est intéressante pour assurer une purge
et compacité maximale des super-blocs. Il peut ainsi rendre les pages inutilisées à l’OS. Comme
nous le verrons, cet allocateur est relativement efficace en terme de mémoire avec une bonne
maîtrise de la fragmentation, argument qui a notamment intéressé l’équipe de Firefox.
Sur le plan technique, il est également intéressant d’observer l’utilisation de champs de bits
en début de run pour notifier l’état d’occupation des sous-blocs. Cette approche permet de ne
pas placer d’en-têtes au milieu des blocs alloués tout en garantissant un accès en temps constant
à ces derniers. Cela permet de plus, de se prémunir d’un écrasement des métadonnées en cas
de dépassement. Cette méthode originale est décrite comme rarement utilisée dans l’étude de
Wilson. Les grandes allocations sont indexées par un arbre bicolore en les supposant peu nom-
breuses du fait de leur grande taille (supérieur à 1Mo). Contrairement à Hoard, les super-blocs
sont échangés directement avec l’OS, il n’y a donc pas d’échange direct entre les tas locaux. En
ce qui concerne l’organisation topologique, l’allocateur crée 4P arènes (P le nombre de pro-
cesseurs) et les associent par tourniquet à chaque nouveau thread afin d’obtenir un nombre
constant de threads par tas. Ce problème particulier est tiré de discussion de la part de E. Berger
et J. Bonwick[BMBW00, BA01] dans les années 2000. Le but est de prendre en compte les pro-
grammes créant et détruisant de nombreux threads tout en assurant une répartition homogène
des threads sur les différents tas. Notons que contrairement à Ptmalloc, cette association est fixe.
L’ogranisation générale de Jemalloc est visible sur la figure 4.3 extraite de leur documentation.
On y observe l’utilisation fréquente d’arbres colorés rouge/noir ainsi que la notion de cache lo-
cale à chaque thread similaire à TCMalloc.
Jemalloc tend à avoir une politique de libération agressive en renvoyant régulièrement la mé-
moire vers l’OS. Ce point, couplé à de bonnes heuristiques, lui permet de maintenir une faible
consommation mémoire. Nous verrons toutefois dans la suite que cela donne aussi la limite de
Jemalloc. Cet allocateur utilise des super-blocs de 2 ou 4Mo et force leurs alignements mémoires
sur cette taille. Au vu des discussions de la section 3.5.3, il est clair que ce choix peut poser pro-
blème notamment s’il est appliqué sur grosses pages (cas de FreeBSD). Une correction possible
serait donc d’utiliser des super-blocs de tailles non multiples de la taille des voies du cache, de
ne pas forcer d’alignement particulier ou d’introduire un décalage aléatoire à l’intérieure des
blocs comme discuté en section 3.7.
95
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
4.4.4 TCmalloc
TCMalloc[SG] est un allocateur développé par Google. Cet allocateur reprend principale-
ment la critique sur PTMalloc vis-à-vis du non-échange de blocs entre les différents tas locaux.
Il reprend donc les approches précédentes avec un cache de bloc local et un tas global. Contrai-
rement à jemalloc, TCMalloc génère des purges du cache local au-delà d’une certaine taille, et
compte donc plus fréquemment sur son tas global. Cette approche est certainement intéressante
en cas de flux d’allocation/libération régulier et contrôle mieux la mémoire maintenue dans les
threads. En contrepartie, il semble possible de perdre l’efficacité de l’approche si les libérations
se font par paquets suivis de paquets d’allocations. Dans cette situation, les caches locaux vont
en effets tendre à se vider pour finalement devenir inefficaces lors du flot d’allocations suivant.
Cet allocateur est relativement efficace en terme de performance, nous verrons toutefois que
1. Le drapeau MADV_DONTNEED permet de rendre les pages physiques à l’OS tout en laissant le segment projeté
dans l’espace virtuel.
96
4.5. Impact des allocateurs
cela se fait au prix d’une surconsommation mémoire. L’allocateur montre également ses limites
sur nœud NUMA du fait d’un non-support explicite de ces architectures et de sa méthode de
maintien de la mémoire en espace utilisateur. Des développeurs d’AMD ont effectué quelques
travaux pour intégrer un support explicite des architectures NUMA dans cet allocateur[Kam].
Les sources ne sont toutefois pas disponibles pour test.
4.4.5 MAMA
L’allocateur MAMA[KK06] développé par Cray reprend la discussion sur les allocateurs pa-
rallèles en critiquant les approches précédentes. Ils critiquent la création d’autant de tas que
de threads nourris par un tas centralisé (potentiellement l’OS). Les auteurs partent du principe
que ces approches ne peuvent pas passer à l’échelle au-delà d’un certain seuil. Ils remarquent
en effet que l’augmentation du nombre et du coût des synchronisations sur le tas central im-
pose l’échange de blocs toujours plus gros pour réduire le nombre d’échange. Pour eux, cette
approche induit une augmentation de la mémoire retenue par les tas locaux qui peut à terme
devenir inacceptable.
Les auteurs proposent donc une approche intéressante visant à faire collaborer les différents
threads lors des allocations. Si plusieurs threads sont en attente d’un verrou, alors rien n’inter-
dit que ces derniers ne se mettent d’accord pour que l’un d’entre eux récupère les blocs pour
l’ensemble. Les blocs peuvent ensuite être distribués à tout le monde. Cette approche réduit les
prises de verrous auprès des structures centrales et maintient un certain nombre d’opérations en
cache. Les sources de cet allocateur ne sont pas disponibles, nous n’avons donc pas pu le tester.
Nous discuterons toutefois une intégration potentiellement intéressante de ce type d’approche
au vu de nos travaux dans une partie discussions en fin de chapitre.
L’application Hera est très intensive en terme d’allocation mémoire avec une génération de
l’ordre d’un million d’allocation mémoire pour 5 minutes d’exécution sur 12 threads. Les allo-
cations se répartissent en trois groupes principaux (voir figure 4.4). On observe un groupe de
petites allocations de courtes durées de vies liées à la structure C++ de l’application. S’ajoute
à cela, des allocations et libérations régulières de blocs moyens (de 1 à 4 Mo) liés à la struc-
ture AMR du code, dont certains avec une courte durée de vie. Nous remarquerons également
un grand nombre d’appels à realloc, notamment sous la forme de réallocations croissantes. Ces
dernières tendent à générer une forte fragmentation au niveau de l’allocateur et à poser des
problèmes importants de performances suivant les implémentations retenues. La gestion des
gros blocs à courte durée de vie représente le problème majeur de cette application. Ces blocs
impliquent en effets des échanges systématiques avec l’OS mettant en exergue les limites de
passage à l’échelle de ce dernier, notamment vis-à-vis des fautes de pages.
La table 4.1 donne les performances obtenues avec les différents allocateurs sur 12, 32 et
128 cœurs. On y remarquera l’évolution des tendances. Sur 12 cœurs (calculateur A) TCmal-
loc apporte un léger gain de performance (2 %) alors que jemalloc offre de bonnes perfor-
mances couplées à des gains mémoires importants (2.3 Go économisés sur 3.3 Go utilisés par la
97
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
(a) (b)
F IGURE 4.4 – Distribution en taille et temporelle des allocations mémoires de l’application Hera sur
12 cœurs pour un problème à 1.4 million de mailles. Sont données, en fonction de la taille des blocs :
(a) la répartition temporelle et (b) la durée de vie de ces allocations.
glibc). L’allocateur de la glibc offre des performances similaires et une consommation mémoire
moyenne. On s’intéresse principalement à l’évolution des performances sur 32 et 128 cœurs.
Sur ces architectures on observe une nette dégradation associée à jemalloc et TCmalloc. Le pre-
mier est impacté par une forte augmentation du temps système que l’on impute au nombre trop
important d’échanges avec l’OS. Nous supposerons pour l’instant que la perte de performance
de TCMalloc est pour partie liée à un non-support du NUMA. Nous discuterons et confirmerons
ce point dans la suite. L’allocateur Hoard supporte très mal notre application dans l’ensemble
des configurations testé très probablement à cause d’un support plus faible des appels à realloc,
point sensible de cette application. Certains tests avec cet allocateur conduisent à une explosion
mémoire empêchant la terminaison de la simulation. Nous n’avons donc pas inclus les résultats
partiels obtenus avec cet allocateur.
TABLE 4.1 – Mesure préliminaire des performances de l’application Hera sur différents calculateurs
NUMA en fonction de l’allocateur retenu. Les tests sont effectués dans le mode canonique de MPC,
à savoir, un processus par nœud et un thread par cœur physique. Pour être comparables, les temps
utilisateurs et systèmes sont donnés par thread.
98
4.6. Structure de l’allocateur
Source mémoire
Tas local
(Segment utilisateur)
Chaine d'allocation
F IGURE 4.5 – Schema d’organisation générale de l’allocateur faisant intervenir deux composants
principaux, des sources mémoires et tas locaux assemblés pour former la chaîne complète d’alloca-
tion entre l’OS et l’application.
Cette approche à deux composants permet de redéfinir sa propre source mémoire, il est ainsi
possible de gérer des segments utilisateurs au sein de l’allocateur principal, comme cela sera dis-
cuté en section 4.13. Les tas locaux peuvent fonctionner sans verrous s’ils sont créés par thread,
les contentions se reportant alors sur la source mémoire de manière limitée par la taille impor-
tante des échanges. Remarquons également que les allocations de gros segments (supérieurs à
1Mo) sont transférées directement à la source mémoire.
La séparation par thread a été mise en place afin de permettre la migration des tâches MPI
(de leur mémoire associée) permise par MPC vers des nœuds distants. Ce support des migrations
a toutefois été retiré dans les dernières versions, levant la contrainte pour notre allocateur.
Sans cette dernière, il pourrait être intéressant d’évaluer des méthodes de mise en commun
entre nombres réduits de threads pour limiter la surconsommation engendrée par un trop grand
nombre de tas locaux. Cette remarque est surtout valable si l’on considère le fait que les threads
2. Les TLS : Thread Local Storage sont des variables gérées par le compilateur et permettant d’associer une valeur
dépendant du thread courant.
99
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
utilisateurs de MPC fonctionnent en mode non préemptif. On peut ainsi maintenir des tas locaux
sans verrous si l’on crée un tas local par thread système.
Bloc alloué
Bloc nale
Données utilisateurs (size = 0)
Bloc mémoire alloué
MacroBlocHeader BlocHeader
+ nb_chunk : 64 + size : 56 PaddedBlocHeader
+ * localPool : 64 + magik : 8
+ prevSize : 56 + padding : 56
+ bloc_header : 128 + info :8 info + info :8
+ type :1
+ state :1
+ magik :6
F IGURE 4.6 – Organisation des en-têtes de macro-blocs, blocs alloués et libres. Les tailles des champs
sont données en bits considérant l’architecture x86_64.
Les tas locaux maintiennent des listes doublement chaînées de blocs libres pour différentes
classes de tailles afin de trouver rapidement les blocs adaptés. Ces listes sont ordonnées par
ordre FIFO 3 de manière à réutiliser les blocs les plus anciens. Ceci afin de permettre aux fusions
de libérer des macro-blocs. En cas de scission, le bloc restant est inséré en tête de liste de sorte
à être réutilisé rapidement et favoriser des durées de vie proches pour des blocs voisins. En
ce qui concerne la gestion des blocs libres, ces derniers sont maintenus sous la forme de listes
doublement chaînées en stockant les deux pointeurs à l’intérieur du segment à suivre. Ceci
impose une contrainte interdisant la gestion de blocs de taille utile inférieure à 16 octets sur
architecture 64 bits.
3. FIFO : First In, First Out : système de queue impliquant une réutilisation prioritaire des entrées les plus an-
ciennes.
100
4.6. Structure de l’allocateur
101
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
L’indexation peut se construire sur la base d’arbres binaires équilibrés, comme le fait Jemal-
loc. Remarquons toutefois que la détermination d’appartenance locale ou distante d’un bloc à
libérer nécessite l’accès à cet en tête. Ceci implique donc une lecture de l’index à chaque libé-
ration. L’utilisation d’un arbre pourrait pénaliser les performances s’il devenait trop profond.
Nous avons donc opté pour une structure assurant un accès en temps constant. À la manière
de TCmalloc, l’indexation de nos segments se fera par la création d’une table globale. L’espace
d’adressage est ainsi découpé en segments de 2 Mo associés à des pointeurs vers les en-têtes des
macro-blocs qu’ils couvrent. Cette table est construite en deux niveaux, à la manière de la table
des pages. Le premier niveau adresse des régions, de 1 To. Chaque région est associée à une table
de deuxième niveaux occupant 4 Mo et adressant les sous-segments de 2 Mo.
2Mo
En-tête de macro-bloc
Région : 4 Mo adresse 1 To Macro-bloc 1 (3.5 Mo)
Macro-bloc 2 (2 Mo)
Niveau 0 : 2 Mo Adresse 256 To Espace libre
F IGURE 4.7 – Mécanisme d’indexation en régions des macro-blocs pour retrouver les adresses de
leurs en-têtes. Sont représenté ici l’indexation de macro-blocs de 3.5 Mo et 2 Mo.
Pour des macro-blocs de taille supérieure à 2 Mo, l’unicité des adresses renvoyées par mmap
implique l’unicité des entrées d’index à mettre à jour. Cette structuration impose la contrainte
d’utiliser des macro-blocs d’une taille minimale de 2 Mo afin d’éviter d’avoir plus que deux
macro-blocs à indexer dans la même entrée. De plus, des chevauchements sont possibles si l’on
ne force pas un alignement des tailles et adresses sur 2 Mo. Dans cette situation, nous indexons
systématiquement le bloc ayant l’adresse la plus élevé. Le bloc précédent est nécessairement
enregistré par l’index précédent, une simple comparaison d’adresse permet alors de retrouver
les en-têtes en lisant au plus deux entrées dans la table (code 4.1).
Grâce à ces règles, l’index peut être mis à jour sans prise de verrous, sauf lors des modifica-
tions de la table de niveau 0. Ceci n’est vrai qu’à la condition de ne pas supprimer de régions.
On obtient ici un avantage sur la méthode à base d’arbre qui implique généralement des ver-
rous globaux. Un exemple d’indexation avec chevauchement est donné dans la figure 4.7. Du
fait de l’allocation paresseuse, l’essentiel de cette table reste virtuelle tant que la bande mé-
moire associée n’a pas été utilisée. Remarquons que cette technique peux poser problème si les
mmap successifs vont en adresse croissante sans réutiliser les zones préalablement libérée par
munmap. Ce cas de figure semble se rencontrer par exemple sous Windows.
102
4.6. Structure de l’allocateur
infiniband ou gestionnaires de taches CUDA lors des libérations (munmap) de ces segments.
Ceci est notamment vrai si ces implémentations nécessitent l’utilisation de pages punaisées 4 et
offrent des optimisations à base d’un suivi précis des libérations mémoires.
Lorsque ces libérations surviennent, le bloc est enregistré auprès d’une liste simplement chaî-
née (File de Libération Distante : FLD). Les blocs sont alors libérés en groupe lorsque le thread
propriétaire effectue une opération avec l’allocateur. Cette liste de blocs distants est accédée en
insertion par plusieurs threads et en extraction par un seul. Il est donc possible de la construire
de manière atomique. On peut par exemple reprendre l’algorithme de liste disponible dans la
bibliothèque OpenPA[Ope] initialement tiré du projet MPICH2[BMG06] pour des fils de mes-
sage réseau. Remarquons toutefois que l’extraction n’a pas à se faire élément par élément, nous
modifions donc légèrement l’algorithme pour vider l’ensemble de la liste en un appel. On pourra
trouver en annexe C le détail des modifications apportées sur cette liste que l’on peut dire à
insertion multiple et purge unique.
Au-delà de la suppression des verrous, cette méthode permet de maintenir les structures du
tas local au niveau du cache du thread auquel il est associé. Ce point peut-être particulièrement
important sur les nœuds NUMA ayant de fortes pénalités en cas de déplacement d’un élément
mémoire d’un nœud NUMA à l’autre.
4.6.7 Realloc
La fonction realloc vise à redimensionner un bloc mémoire. L’implémentation naïve consiste
en une nouvelle allocation, une copie des données et libération de l’ancien segment. Cette mé-
thode est toutefois sous-efficace si elle s’applique aux grands segments. Or, nous avons vu en
section 4.5 que l’application Hera utilise un grand nombre de ces appels. Pour notre allocateur,
4. Pages spécialement marquées pour indiquer à l’OS qu’il ne doit pas déplacer leur emplacement physique. Ce
type de page est habituellement utilisé lors de l’emploi des mécanismes dit DMA pour optimiser les échanges avec
les périphériques d’entrées/sorties.
103
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
a≠b
3
4
reg_FLD()
purge_FLD() Distant ?
1
malloc() 0x0A342
2
free()
Thread 1 Thread 2
F IGURE 4.8 – Mécanisme de libération à base de File de Libération Distante (FLD). Un bloc est alloué
par un thread (1) et transmis pour libération à un autre thread (2). La comparaison d’adresse du
tas local avec l’entrée du registre de région permet de distinguer les allocations distantes. Le bloc est
alors enregistré dans la queue distante de manière atomique (3). Le thread d’origine purgera cette
liste de manière atomique lors de la prochaine allocation (4).
nous avons donc pris soin d’optimiser cette fonction. Les réallocations sont donc traitées par
catégorie avec les règles suivantes :
1. Les gros segments sont redimensionnés directement à l’aide de mremap si disponible
comme cela est fait dans d’autres allocateurs. Ceci permet de simplement migrer les pages
dans l’espace virtuel sans effectuer des copies.
2. Pour les blocs standards, un seuil est défini, les redimensionnements décroissants ne gé-
nèrent donc un changement que si la mémoire perdue est supérieure à un seuil définit par
le paramètre SCTK_REALLOC_THRESHOLD.
3. Les autres cas basculent directement sur la méthode allocation/copie/libération. Ceci est
surtout indispensable pour les réallocations distantes qui posent un problème de définition
sémantique quant à l’attente de l’utilisateur en terme de placement (voir section 4.12).
Nous choisirons donc arbitrairement un placement NUMA attaché au thread chargé de la
réallocation pour les petits blocs et un maintien pour les gros blocs.
104
4.7. Réutilisation des gros segments
de mmap. Ces graphiques mettent clairement en évidence l’existence d’une source différente de
surcoût d’allocation. Les petites allocations sont essentiellement impactées par le temps de la
fonction malloc. Les grosses sont majoritairement impactées par les fautes de pages.
(a) (b)
F IGURE 4.9 – Source des différents surcoûts d’allocation en fonction de la taille. L’impact des fautes
de pages est mesuré à partir de la différence de temps entre un premier et un second accès aux
données en ayant vidé les caches entre temps. Les coûts sont donnés par unité de taille (cycles par
octet).
Avec un temps tf de faute de page on montre alors que le surcoût lié à l’OS est au maximum
s
de s = tf ∗ ∆t ∗ c, on a donc un ratio temps effectif sur temps système borné par ∆t = tf ∗ c.
Remarquons toutefois que l’on ne contrôle pas le débit instantané d’allocation (contrairement à
la libération), mais moyen. Or, le débit instantané est celui qui peut avoir une influence sur tf si
l’OS ne passe pas à l’échelle. Nous verrons que c’est malheureusement le cas de Linux. De plus,
on notera que la proposition précédente n’est vérifiée que si l’on est en capacité de réutiliser
100% des pages en attente. Or, du fait de la fragmentation à grande échelle, ce n’est pas le
cas de TCMalloc. Cette approche, bien qu’intéressante, ne permet donc de contrôler les débits
d’allocation que de manière approximative.
105
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
munmap, mremap en ne contraignant pas le placement des blocs à des adresses précises. Le
cache de macro-bloc est contrôlé sur la base de deux paramètres :
Taille maximum de segment : Cette limite permet d’ignorer tous les segments au-delà d’une
certaine taille. Les segments trop grands ont en effet peu de chances d’être facilement
réutilisables tout en générant une surconsommation mémoire importante.
Mémoire maximum : Ce paramètre permet de borner la quantité de mémoire totale que l’on
autorise à maintenir en attente sur chaque nœud NUMA, ceci afin d’éviter tout risque
d’explosion inopiné de la mémoire.
Si une requête est en dessous du seuil de réutilisation, l’algorithme recherche le bloc dispo-
nible ayant la taille la plus proche de la requête. Si la taille ne correspond pas, alors le segment
est redimensionné à l’aide de mremap. Les trois sémantiques de recyclage de blocs de taille in-
adapté sont décrites dans la figure 4.10. Remarquons principalement la présence du dernier cas
qui n’est gérable que sur la base d’un emploi de la sémantique mremap. Cette approche permet
d’assurer la réutilisation de segment même pour des tailles très variables. On assure de la sorte la
propriété de réutilisation à 100%. Ceci peut à permettre à terme d’obtenir un meilleur contrôle
des débits moyens via une méthode basée sur madvise(). Ceci, si l’on dispose d’un OS passant à
l’échelle. D’autre part, notre méthode à l’intérêt est de parvenir de limiter le nombre de fautes de
pages en maintenant un contenu minimal en page physique pour les segments renvoyés même
s’ils ne sont pas entièrement projetés physiquement.
4 Mo 8 Mo
6 Mo 6 Mo
F IGURE 4.10 – Méthode de réutilisation des gros segments à base de mremap pour une requête
de 6 Mo. À gauche un exemple de réutilisation d’un segment plus petit impliquant une fraction
du segment final non paginé. À droite la réutilisation d’un segment trop grand conduisant à une
scission pour réutilisation futur. En bas, un cas nécessitant un déplacement éliminant le problème
de fragmentation puisqu’il est toujours possible de réutiliser les pages du segment.
106
4.8. Remise à zéro pour calloc
réduits. Cette approche d’allocation non totalement physique assure également un minimum de
recyclage de la mémoire. Ceci est bénéfique vis-à-vis des applications demandant plus de mé-
moire que nécessaire et délègue plus de gestion du NUMA à l’OS qui a plus d’information que
l’allocateur.
La fonction appelante de plus haut niveau doit donc prendre en charge elle-même cette
remise à zéro. Elle est en effet la seule à connaître la taille exacte à initialiser en ignorant les
éventuelles fusions/scissions des fonctions sous-jacentes. Elle doit toutefois disposer d’un retour
de ces fonctions pour connaître l’état de pré-initialisation du bloc demandé. La méthode consiste
donc à transmettre un booléen par pointeur dans toute la hiérarchie d’appel tel que cela est fait
dans Jemalloc. La sémantique peut alors être interprétée comme suit :
Pointeur nul ou valeur faut : Aucune remise à zéro n’est attendue, peu importe la méthode
d’allocation. L’utilisation de la modification noyau discutée dans le prochain chapitre (5)
est alors possible.
Valeur vrai : L’appelant a besoin de mémoire remise à zéro. Dans le cas ou les mécanismes de
bas niveaux ne permettraient pas d’obtenir une telle mémoire (recyclage au niveau de la
source mémoire...), le booléen est remis à faut. L’appelant sait ainsi que la mémoire reçue
n’est pas pré-initialisée.
L’approche précédente améliore le procédé, mais ne résout toujours pas le problème, qui du
fait du recyclage des segments tend à demander une remise à zéro systématique de la mémoire
reçu par la fonction calloc. Or, il est à remarquer que les pages non encore accédées (purement
virtuelles) seront automatiquement remises à zéro lors de leur premier accès. On peut donc
proposer d’analyser la projection de la zone mémoire pour déterminer les zones physiquement
107
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
1e+07
1e+06
100000
10000
1000
100
10 100 1000 10000 100000 1e+06
Taille du tempon mémoire (Ko)
F IGURE 4.11 – Évalutation du coût de détection de présence des pages physique en comparaison du
coût de remise à zéro de la mémoire avec ou sans fautes de pages.
présentes. On ne remet alors à zéro que ces dernières. Sous Linux, la requête peut-être faite
via l’appel move_pages utile aux migrations NUMA ou en lisant la table des pages au travers
du fichier /proc/self/pagemap s’il est présent. Le graphique 4.11 montre les surcoûts engendrés
par ces deux méthodes comparés au coût de remise à zéro par memset. On observe clairement
l’intérêt de la méthode avec un surcoût mineur à comparer aux gains potentiels. En considérant
le cas défavorable d’une zone entièrement physique le surcoût ne dépasse pas 5% pour 64 Ko et
1% pour 1 Mo. Cette méthode a été étudiée en cours de rédaction et n’a pas encore été intégrée
dans l’implémentation de l’allocateur faute de temps pour valider sa portabilité. Une alternative
plus portable peut aussi consister à ne pas exploiter le cache de la source mémoire dans le cas
d’allocation nécessitant une remise à zéro.
108
4.11. Aspect NUMA
sance de calcul tend à croître plus vite que les capacités de stockages mémoires. On remarquera
toutefois que les applications n’utilisent pas toujours toute la mémoire du nœud et vont très
souvent faire apparaître des pics de consommation lors de certaines étapes de calcul. Il est donc
intéressant de remarquer que l’on peut dans ces conditions se permettre d’utiliser la mémoire
lorsque disponible pour obtenir de bonnes performances et réduire les performances pour un
mode économique dans le cas contraire.
Ce type d’adaptation dynamique est envisageable dans un contexte HPC où l’utilisateur est
en général seul sur un nœud et vise à exploiter au mieux les ressources. Dans cet objectif, nous
avons construit notre implémentation de façon à offrir les deux politiques extrêmes et pouvoir
contrôler un gradient entre ces dernières à l’aide de paramètres. Pour ce faire, il nous a fallu
obtenir une capacité à économiser au mieux la mémoire au niveau des tas locaux. Ces derniers
renvoient la mémoire de manière agressive vers les sources mémoires. Le contrôle de consom-
mation peut ainsi s’établir à leur niveau en décidant d’y garder ou non les macro-blocs en transit.
Remarquons que la politique est ainsi réversible puisque les macro-blocs en attente peuvent être
libérés brutalement en cas de pic de consommation. Une politique de contrôle au niveau des tas
locaux impliquerait la collaboration de plus de composants et pourrait induire des effets non
réversibles si la méthode impacte les décisions de sélection des blocs.
Comme nous allons le montrer en section 4.14 nous avons ainsi atteint la capacité de passer
d’un profil de type TCMalloc (rapide, mais consommateur) à un profil Jemalloc (plus économe,
mais pénalisé par l’OS). Reste à mettre en place le composant de prise de décision dynamique.
Non implémenté pour l’instant, ce dernier sera discuté en section 4.17.2.
Cette propriété fondamentale n’est toutefois pas vérifiée sur les allocateurs tels que la glibc,
Jemalloc et TCmalloc. Ces allocateurs utilisent en effet une association aléatoire des threads aux
différents tas ou génèrent des échanges non contrôlés entre ces derniers. Dans le cadre de notre
allocateur, l’association d’un tas à chaque thread permet donc d’assurer la propriété de réutili-
sation locale pour les petits blocs. La question se pose toutefois pour les gros segments que l’on
s’efforce de réutiliser. Ces derniers circulent en effet entre les threads au travers de la source
mémoire. Afin d’éviter un mélange indésirable, nous construisons donc une source mémoire par
nœud NUMA.
On remarquera toutefois que les threads ne sont pas nécessairement figés et peuvent migrer
d’un nœud à l’autre sans que l’allocateur n’en soit notifié. Il n’est pas raisonnable (trop coû-
teux) de demander la position du thread à chaque allocation. Nous appliquerons donc différents
niveaux de confiances entre les threads sur la base des règles suivantes :
1. Lors de la première allocation, les positions autorisées pour le thread sont analysées. Si le
thread est fixé sur un nœud NUMA déterminé, alors il est associé à une source mémoire
de confiance pour ce nœud NUMA.
109
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
2. Si le thread n’est pas fixé sur un nœud particulier, il est associé à une source mémoire
générique considérée comme non fiable.
3. En cas de migration du thread, il faut notifier l’allocateur. Ce problème est résolu dans le
cadre de MPC par la gestion de threads utilisateurs dont il est facile de suivre les dépla-
cements explicites. Dans le cas général, il nous faut toutefois compter sur la coopération
de l’utilisateur qui doit appeler une fonction de migration ou surcharger les fonctions de
placement de thread. Certains tel que [DG02] proposent des modifications de l’OS pour
permettre ce type de suivit. Cela rend toutefois la méthode non portable sur les OS conven-
tionnels ne disposant pas de ces mécanismes expérimentaux.
Il est également important de noter que les pages des grands segments sont placées par
l’OS en fonction du premier accès. Ceci pose un problème de confiance sur ces derniers lors
des libérations. Il est en effet possible qu’une partie d’un segment soit sur un nœud NUMA
distant. Il n’est toutefois pas raisonnable de demander le placement de chacune des pages à
chaque libération, on postulera donc un niveau de confiance envers l’utilisateur. Dans le cas où
l’utilisateur voudrait obtenir des segments pour des usages critiques et nécessitant un placement
fiable, nous fournissons en supplément un tas partagé de haute confiance (placement forcé
de manière explicite) pour chaque nœud NUMA disponible. L’utilisateur peut y allouer de la
mémoire en utilisant un appel à sctk_malloc_on_node(). La libération de ces segments se faisant
de manière standard à l’aide de la fonction free.
Remarquons que sur ces architectures, l’utilisation de realloc pose la question de l’attente
de l’utilisateur. Attend-il que le bloc réalloué maintienne l’ancienne association NUMA ou la
nouvelle en fonction du thread demandeur ? Dans notre cas, les réallocations distantes sont
traitées par recopie pour les segments inférieurs au Mo. Les gros blocs sont redimensionnés
par mremap. Cela pose toutefois la question de fiabilité de positionnement NUMA du nouveau
segment s’il est agrandi avec un risque d’association non uniforme pour un nœud donné. Nous
avons vu en section 4.7.2 que nous maintenions un certain taux de pages nouvelles par notre
méthode de réutilisation, nous comptons donc sur cette dernière pour limiter l’impact de ce
problème en libérant tout de même régulièrement une partie de la mémoire.
110
4.14. Méthode d’implémentation
Afin de prendre en compte cette problématique, nous avons construit notre allocateur de
sorte à pouvoir aider à gérer ces segments particuliers. La méthode la plus simple consiste à
construire un tas local sans source mémoire et à y placer le segment mémoire. Les fonctions
d’allocation internes sont alors utilisables comme le montre le code 4.2. Ce support a notamment
été utilisé de manière expérimentale comme base d’implémentation d’un module SHM par un
stagiaire (Antoine Capra) pour les communications entre processus d’un même nœud dans MPC.
Code 4.2– Allocation sur un segment utilisateur via les méthodes d’allocation spécifiques.
1 // preparation du buffer
2 struct alloc_chain chain ;
3 void * buffer = setup_buffer ( SIZE ) ;
4
5 // mise en place de l ’ allocateur
6 user_chain_init (& chain , buffer , SIZE ,
7 CH AI N_F LAG S_ STA ND ALO NE ) ;
8
9 // utilisation de l ’ allocateur
10 void * ptr = chain_alloc (& chain ,32) ;
11 ptr = chain_realloc (& chain ,64) ;
12
13 // liberation par la methode standard
14 free ( ptr ) ;
Remarquons que l’interface standardisée des chaînes d’allocation permet de capturer toutes
les allocations au travers des appels standards de l’allocateur en faisant pointer temporairement
la TLS vers le tas spécialisé. Le code 4.3 montre l’exemple de cette manipulation. Cela permet
également de capturer les opérateurs new et delete du langage C++ ou un ensemble de sous-
fonctions d’une bibliothèque. On peut par exemple isoler un segment de code que l’on sait bogué
pour qu’il ne pollue pas l’allocateur principal.
Code 4.3– Allocation sur un segment utilisateur via les méthodes d’allocation standards.
1 // remplacement de la chaine standard
2 // pour le thread courrant
3 old_chain = set_default_chain (& user_chain ) ;
4
5 // capture
6 MyObject * obj = new MyObject ;
7 fu nc tio nWh ic hUs eM all oc () ;
8
9 // restauration de la chaine d ’ origine
10 default_chain (& old_chain ) ;
11
12 // utilisation de delete
13 delete obj ;
Il est également possible de construire sa propre source mémoire si l’on désire permettre
l’extension automatique de l’espace mémoire du tas. Sans cela, l’allocateur renvoie un code
d’erreur lorsque le segment est épuisé.
111
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
de type développement dirigée par les tests (TDD : Test Driven Developpement[Bec03]) ty-
piques des méthodes agiles. L’allocateur dispose donc d’une base de tests unitaires ayant permis
d’éliminer la majorité des problèmes avant de passer à une phase de test avec des applications
réelles. Cette approche a également permis la modification d’une structure centrale de l’alloca-
teur en vue d’optimisation. Cette modification qui a apporté un gain d’un facteur 2 n’aurait pas
été possible ou très difficile sans tests. Elle impliquait en effet un changement sur une structure
impactant l’ensemble du code. Cette base de 160 tests a également été utile en permettant à un
alternant (Julien Adam) de réaliser en grande partie le portage de l’allocateur sous Windows.
4.15 Évaluation
Dans cette section, nous allons donner une partie des résultats obtenus avec notre alloca-
teur. Ce dernier sera comparé aux allocateurs disponibles discutés en section 4.4. Pour cela,
nous commencerons par observer certains micro-benchmarks validant le comportement du code
et progresserons ensuite avec divers benchmarks pour terminer l’évaluation avec l’application
Hera.
4.15.1 Micro-benchmarks
Le premier micro-benchmark correspond à un accès peu réaliste avec des allocations/libéra-
tion par lot et locales à chaque thread. Les résultats sur les nœuds larges de Curie sont présentés
dans la figure 4.12. Ces résultats montrent que nos performances sur ce type de benchmark
sont proches de TCmalloc pour les grosses allocations. Nos petites allocations sont plus proches
du comportement de la glibc même si en retrait du fait d’un manque d’optimisation de cette
partie en séquentiel. Ceci est notamment dû aux fusions immédiates actuellement utilisées dans
notre allocateur. Notons toutefois que l’écart de performance se gomme avec l’augmentation
du nombre de cœurs. Les allocateurs Hoard et Jemalloc rencontrent de gros problèmes de pas-
sage à l’échelle sur ce benchmark. La Glibc rencontre un problème similaire pour les grosses
allocations.
Temps (s)
8
4
4
2 1
1
0.5 0.25
0.25
0.125 0.0625
1 2 4 8 16 32 64 128 1 2 4 8 16 32 64 128
Threads Threads
(a) (b)
F IGURE 4.12 – Benchmark d’allocations locales de (a) 32 octets ou (b) 128 kilo-octets. Les allo-
cations sont réalisées par lot de 1000 éléments avant libération par le même thread. Lors de ce
benchmark, les threads ont été punaisés avec l’outil likwid-pin[THW10].
112
4.15. Évaluation
nombre variable de threads. Le thread 0 génère des ensembles d’allocations de 32 octets qui
sont transmis aux différents threads pour libération. Les différents allocateurs montrent claire-
ment des comportements divergeant au-delà de 8 cœurs en fonction des algorithmes retenus.
Notre allocateur offre dans ce cas une performance proche de Jemalloc et plus efficace que la
Glibc. Remarquons toutefois l’écart de performance pour le mode séquentiel du fait d’un léger
manque d’optimisation de notre part dans la gestion spécifique des petits blocs qui ne sont pas
l’objectif principal de notre allocateur. Il en résulte une meilleure extensibilité de notre algo-
rithme comparé à l’ensemble des autres allocateurs. Cette dernière s’explique par la prise en
compte explicite de la structure NUMA et l’utilisation des FLD atomiques. Les performances
pourraient certainement être améliorées en reprenant pour partie la notion de cache local ex-
ploité par Jemalloc. On notera que sur ce cas test Hoard multiplie par 10 la consommation des
autres allocateurs pour 128 threads.
Producteur/consommateur en punaisant les threads (32 o) Producteur/consommateur en punaisant les threads (2 Mo)
64 128
glibc glibc
32 jemalloc jemalloc
tcmalloc 64 tcmalloc
16 hoard hoard
mpcalloc 32 mpcalloc
Temps (s)
Temps (s)
8
16
4
8
2
1 4
0.5 2
2 4 8 16 32 64 128 2 4 8 16 32 64 128
Threads Threads
(a) (b)
Temps (s)
8
2
4
1
2
0.5 1
0.25 0.5
0.125 0.25
1 2 4 8 16 32 64 128 1 2 4 8 16 32 64 128
Threads Threads
(a) (b)
F IGURE 4.14 – Benchmark d’allocation t-test1 provenant d’Hoard et Lockless. Le benchmark génère
des allocations de tailles aléatoires bornées par la consigne (a) 64 octets ou (b) 2 Mo. Les blocs sont
ensuite échangés entre les threads.
La figure 4.14 donne un extrait de performance obtenu sur le benchmark t-test1 utilisé par un
certain nombre d’allocateurs, dont Hoard et Lockless[MH]. Ce dernier reprend le cas précédent,
mais en exploitant des blocs de taille aléatoire inférieure à une borne. Notre allocateur fournit
de bonnes performances sur ce benchmark qu’il s’agisse des petites ou grosses allocations. Sur
ce benchmark, notre allocateur offre des performances dans la moyenne pour les petites tailles
113
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
2000
1500
1000
500
0
0 20 40 60 80 100 120 140
Threads
F IGURE 4.15 – Sysbench avec MySQL en fonction de l’allocateur sur les noeuds larges Curie. Lors de
ce benchmark, les threads ont été punaisés avec l’outil likwid-pin.
114
4.15. Évaluation
TABLE 4.2 – Mesure de performance de la simulation numérique Hera avec différents allocateurs sur
les nœuds NUMA disponibles au CEA. Les exécutions sont réalisées dans le mode de fonctionnement
canonique de MPC à savoir un processus par nœud et un thread par cœur physique. Pour être
comparables, les temps utilisateurs et systèmes sont donnés par thread. Ces tables montrent les
gains importants de notre allocateur sur les nœuds NUMA 128 cœurs.
Le mode ECO de notre allocateur montre des consommations mémoires proches des résul-
tats de Jemalloc sur une partie des machines, mais au prix d’un surcoût en temps induit par les
appels trop nombreux à destination de l’OS. En comparant ces résultats au mode UMA, nous
pouvons extraire l’impact de l’interaction avec l’OS. Ce mode apporte une réduction du temps
système non négligeable (facteur 4 à 10) qui se traduit également en gain sur le temps d’exécu-
tion total avec des performances proches (architecture A) ou meilleures que le plus performant
des allocateurs (architectures B et C). Sur 128 cœurs, les gains apportés par ce mode atteignent
20% comparé à la Glibc. On peut alors comparer ces résultats avec l’activation du support NUMA
qui permet de dépasser les performances de tous les allocateurs testés en doublant les perfor-
mances de la glibc sur 128 cœurs. Ces gains sont toutefois obtenus au prix d’une augmentation
de la consommation mémoire d’environ 2 Go.
Avec ces mesures, on montre l’intérêt d’introduire un support explicite des architectures
NUMA au niveau de l’allocateur et de prendre en compte le problème d’échange avec l’OS en
ce qui concerne les allocations de grands segments. On remarque également que nous sommes
parvenus à obtenir une implémentation permettant de passer d’un profile plus économe de
type Jemalloc à un profile plus performant, mais consommateur de mémoire de type TCMalloc.
Ces résultats ouvrent donc la porte à une adaptation dynamique entre ces profils extrêmes en
fonction de la mémoire disponible.
115
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
Nous avons vu avec les résultats précédents qu’il était possible d’améliorer les performances
des allocateurs actuels sur les nœuds NUMA dont nous disposons. Nous avons notamment vu
sur un cas concret de simulation numérique que l’OS pouvait devenir un problème majeur avec
un coût associé à l’OS de 20% du temps total d’exécution. Pour ce type d’application, le contrôle
des échanges avec l’OS devient plus important que l’optimisation propre de la gestion des petits
blocs. À ce titre, nous avons notamment proposé une méthode de réutilisation des gros seg-
ments éliminant les problèmes de fragmentation par utilisation de la fonction mremap comme
élément central de l’approche. L’utilisation de threads sur architecture NUMA nécessite égale-
ment la mise en place d’allocateurs supportant explicitement ces dernières. On notera les efforts
fournis pour maintenir l’utilisation de l’API standard d’allocation afin obtenir le support NUMA
sur la base d’établissement de niveau de confiance envers les différents threads. Toujours pour
les architectures NUMA, nous avons mis en place des procédés éliminant au maximum le besoin
de synchronisation de sorte à obtenir des tas locaux sans verrous. Ne subsistent donc que les
synchronisations nécessaires pour les libérations distantes et l’accès aux sources mémoires com-
munes. Remarquons que cette approche est permise par le mécanisme d’indexation à base de
région lui-même essentiellement sans verrous. Grâce à ce travail, nous avons obtenu des gains
importants sur la grosse simulation numérique Hera avec un double des performances de l’al-
locateur de la glibc. Du fait d’un manque de prise en compte de l’OS et du NUMA, les autres
allocateurs parallèles montrent des performances très dégradées dans ces mêmes conditions.
Dans cette section nous allons discuter certaines améliorations qu’il serait bon d’intégrer et
déduites du recul pris lors de nos travaux sur l’allocateur. Les remarques qui suivent prennent
en compte les problèmes et erreurs rencontrés lors de nos travaux sur l’allocateur.
La version actuelle de notre allocateur mémoire met en place un tas local pour chaque
thread. Cette stratégie peut s’avérer mauvaise pour des programmes très dynamiques en terme
de création de threads. Dans ce contexte, il serait bon de retenir une politique de réutilisation
des tas existants pour limiter leur nombre au lieu de les détruire en même temps que les threads.
Remarquons également que MPC crée autant de threads système que de cœurs puis met
en place des threads utilisateurs à l’intérieur de ces derniers. Dans ce contexte, il peut être
intéressant de créer un tas local par thread système et non utilisateur. Ceci est d’autant plus
intéressant que les threads utilisateurs de MPC sont non interruptibles. Par conséquent, les tas
locaux de cette configuration peuvent être maintenus sans primitive de synchronisation. Il est
donc possible de gagner sur le plan de la consommation mémoire sans perdre sur le plan de la
performance.
116
4.17. Discussion d’améliorations possibles
Nous avons vu avec les résultats précédents que nous avons obtenus un allocateur capable
de reproduire en partie les résultats d’économie mémoire de Jemalloc ou bien un profil plus
gourmand en mémoire évitant les pertes de performances liées à l’OS. Nous avons notamment
pris soin de rendre les décisions de ces profils réversibles. Nous pouvons donc désormais mettre
en place une politique d’adaptation dynamique entre les profils extrêmes en cours d’exécution.
De cette manière, il est possible de s’adapter à la consommation mémoire des différentes phases
de l’application. On remarque en effet que certaines applications tendent à produire des pics
localisés de consommation. Ces pics déterminent les limites de taille de problème exploitable par
le programme. Lors des pics de consommation, il serait donc intéressant de basculer l’allocateur
dans un mode économe pour passer le cas et pouvoir compter sur des gains de performances
pour les étapes moins consommatrices. Au niveau de notre allocateur, un basculement vers le
profil économe peut être réalisé en suivant les étapes :
3. Pour diminuer plus la consommation mémoire, il est aussi possible de parcourir les blocs
libres et rendre au système les pages non utilisées à l’aide d’appels à madvise. Ce traitement
peut se fait au prix d’un surcoût lors du changement de politique.
Cette approche n’a pas encore pu être évaluée d’un point de vue pratique, mais semble tou-
tefois rencontrer deux difficultés qu’il est nécessaire de lever. La première correspond au choix
de la consommation à contrôler : virtuelle ou physique. Dans le cas où l’application ne fait pas
trop d’allocations spéculatives, il n’y a peu de différence, mais les deux peuvent être amenées à
diverger dans le cas contraire. Le contrôle de la mémoire virtuelle peut surestimer la consom-
mation réelle de l’application. Les limites d’exécution sont liées à la mémoire physique, c’est
idéalement cette dernière que l’on doit suivre ou estimer. Le second problème est lié au choix
du seuil limite. Si l’on considère un unique processus sur le nœud, il est possible d’analyser
la mémoire disponible au lancement de l’application et de fonctionner en estimant l’évolution
de cette dernière en fonction des allocations reçue. Afin de s’assurer d’un bon suivi, il serait
certainement important de mettre à jour cette information au-delà d’une certaine quantité de
mémoire échangée avec l’OS. Dans le cadre de notre allocateur, ce suivi doit se faire au niveau
des sources mémoires. Ces dernières étant multiple (une par nœud NUMA) il serait important
de mettre en place un composant central chargé du suivi et interroger périodiquement par les
sources mémoires NUMA.
En pratique il est important de noter que le seuil limite doit être choisi en deçà de la quantité
de mémoire disponible sous peine de trop pénaliser le cache disque qui peut avoir un impact
important si l’application effectue beaucoup d’entrées/sorties. Si l’on souhaite considérer un
environnement multi-processus, il serait important d’utiliser une augmentation de la consigne de
consommation lente et lissée. On peut ainsi espérer permettre aux différents processus d’aboutir
à un état stable, évitant le passage brutal d’un mode (économe ou vitesse) à l’autre de manière
alternative pour chacun. Pour ce faire, on pourrait asservir l’augmentation du seuil de mémoire
maintenu dans les sources mémoires à une fonction dépendante du débit moyen d’échange
mémoire avec l’OS (inspiré du paramètre seuil de TCMalloc) et de la mémoire disponible. La
configuration s’exprimerait alors sous la forme de deux paramètres : le taux minimal de mémoire
devant être laissé libre et un débit maximum d’échange moyen de mémoire avec l’OS. Ces deux
paramètres sont mesurables, le dernier pouvant être estimé par un micro-benchmark en fonction
des limites d’extensibilité de l’OS.
117
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
Lors de notre étude, nous avons choisi de ré-implémenter entièrement un allocateur. Nous
nous sommes toutefois principalement consacrés à la réutilisation des macro-blocs. Avec le re-
cul, il serait peut-être intéressant d’extraire le travail réalisé dans cette partie et le mettre en
place sous la forme d’une surcharge des fonctions mmap/munmap/mremap. Il serait ainsi pos-
sible d’appliquer notre approche de réutilisation sur les divers allocateurs disponibles. Ce choix
n’a pas été fait initialement, car un support explicite du NUMA bien que pris en charge au ni-
veau de nos sources mémoires nécessite l’assurance d’une association fiable de ces dernières
aux différents tas locaux. Nous ne pouvions toutefois pas garantir facilement ce point sur les
allocateurs usuels qui peuvent (jemalloc, TCmalloc et hoard) associer plusieurs threads à un tas,
et ce de manière aléatoire. Lors du retour des blocs (surcharge de munmap) il serait également
indispensable d’utiliser des en-têtes externes pour savoir quel nœud NUMA a alloué le macro-
bloc, les allocateurs usuels pouvant potentiellement avoir fait des échanges entre les tas locaux,
notamment lors de la libération des gros segments réalisés par un appel direct à munmap depuis
le thread de libération. Cette approche mériterait d’être évaluée même si l’on peut s’attendre à
des gains plus limités sur architecture NUMA.
Source NUMA 1
OS Source mémoire Allocateur Appli
standard
Source NUMA 2
mmap/munmap/mremap
Si l’on considère la réalisation de l’idée précédente, on dispose d’un cache mémoire géné-
rique à placer sous un allocateur standard. Partant de cet outil, il serait certainement intéressant
et plus robuste de construire un allocateur en reprenant entièrement Jemalloc. Ce dernier dis-
pose en effet d’une implémentation efficace à faible consommation. L’ajout du cache sous-jacent
permettrait de combler ses lacunes en terme d’appels trop intensifs à l’OS tout en offrant la pos-
sibilité de contrôler efficacement le compromis consommation performance comme nous l’avons
fait dans notre allocateur.
Jemalloc emploie également une politique de maintien des derniers blocs libérés pour une
réutilisation rapide. Ce mécanisme devrait également être modifié pour ne pas maintenir des
blocs provenant d’un thread distant (au sens NUMA) dans un cache local.
118
4.17. Discussion d’améliorations possibles
Pour ne pas trop modifier l’API actuelle, le plus simple serait certainement d’introduire des
pragmas. On pourrait ainsi notifier l’allocateur de l’attente pour l’allocation ou groupe d’alloca-
tions suivant. Cette approche de pré-définition d’intention est la seule valide si l’on considère
le C++ avec son opérateur new qui peut difficilement être étendu en terme de sémantique
par ajout de paramètres. En terme d’information, si l’on considère le maintien d’un allocateur
générique, il serait important de pouvoir distinguer quatre catégories d’allocation :
Locale (local) : C’est la supposition par défaut faite par l’allocateur, à savoir que l’élément al-
loué doit être utilisé par le thread chargé de l’allocation.
Distante (remote) : Le bloc est alloué pour être utilisé sur un autre nœud NUMA dont on
connaît l’ID. Nous fournissons actuellement un tel support au travers de la fonction mal-
loc_on_node().
Motif (map) : Une fonction de placement peut être donnée pour définir un motif de position
de chacune des pages du segment. Plusieurs fonctions élémentaires peuvent alors être
offertes en standard : mode entrelacé, aléatoire et répartition par zones contiguës.
Inconnue (unknown) : L’utilisation n’est pas connue à l’avance, le segment ne peut donc être
placé avec confiance. Idéalement l’allocateur doit laisser la main à l’OS en fournissant
des segments virtuels. À la libération, l’allocateur ne peut garder ces segments dont il ne
connaît pas le placement ou dont il sera trop difficile de trouver une utilisation s’il ne sont
pas uniformes.
Pour des allocateurs spécifiques, il est possible de produire une sémantique plus riche, mais
dans le cadre d’un allocateur généraliste cette dernière doit être limitée, car aucune supposition
ne peut être faite sur l’application. Remarquons que notre implémentation prend en charge
les deux premiers points si l’on considère la politique par défaut et la présence de la fonction
sctk_malloc_on_node(). Pour les deux suivants, il est nécessaire d’ajouter un drapeau sur les
blocs concernés pour les libérer directement vers l’OS, leurs réutilisations étant trop délicates au
sens général. On peut proposer comme exemple de syntaxe C :
Des améliorations sont possibles si l’on obtient un moyen efficace d’obtenir le placement
des pages auprès de l’OS au moment des libérations. Ces informations peuvent aisément être
119
Chapitre 4. Mécanismes d’allocations parallèles et contraintes mémoires
exploitées pour la gestion des petits segments internes aux pages. Dans le cas d’allocateurs
généralistes, ces informations ne pourront toutefois être exploitées que de manière parcellaire
en considérant le placement majoritaire des pages d’un grand segment. Pour ces segments, il est
certainement préférable de se reposer sur l’OS à condition de lever les limitations qui nous ont
obligés à mettre en place du recyclage pour cette catégorie d’allocation.
120
Chapitre 5
Dans la section précédente, nous avons montré que l’application Hera pouvait être largement
pénalisée sur les nœuds à 128 cœurs. Au-delà du non-support NUMA des allocateurs testés, ces
résultats mettent en avant une augmentation du temps système sur les gros nœuds. Nous avons
donc construit une politique d’allocation permettant de limiter les échanges avec l’OS et obtenu
une nette amélioration des performances. Ces gains sont toutefois obtenus au prix d’une aug-
mentation de la consommation mémoire.
Dans ce chapitre, nous allons observer le système lui-même et tenter de comprendre une part
du problème en travaillant directement sur ce dernier. Nous allons notamment nous concentrer
sur le problème de remise à zéro des pages fraîchement allouées qui représentent une part im-
portante des coûts d’allocation. Nous discuterons les problèmes de passage à l’échelle rencontrés
au niveau de l’OS, que nous tenterons dans un premier temps de résoudre par emploi de grosses
pages. Nous montrerons que cette méthode a également ses limites. Nous proposerons donc une
amélioration des performances, basée sur une extension de la sémantique d’échange de mémoire
entre l’OS et les applications et montrerons qu’elle est surtout efficace avec les grosses pages.
121
Chapitre 5. Problématique de remise à zéro de la mémoire
30000
25000
Occurences
20000
15000
10000
5000
0
0 2 4 6 8 10
Temps (Kcycles/4K/Thread)
F IGURE 5.1 – Distribution des temps de fautes de pages sur les nœuds Cassard pour 1 ou 2 threads.
Cette mesure est réalisée sur la base d’une allocation d’un segment de 10Go.
ou deux threads. Les distributions prennent la forme d’une gaussienne associée à une queue se
prolongeant dans les valeurs hautes, liées à l’impact de l’ordonnancement. Cette figure montre
clairement un décalage du pic de la distribution vers les valeurs hautes lorsque le nombre de
threads augmente. On peut ainsi obtenir les courbes de la figure 5.2, donnant l’extensibilité des
fautes de pages sur les nœuds de 128 cœurs de Tera 100 ou sur Xeon Phi. Les mesures sont don-
nées pour des allocations parallèles en mode thread ou processus. Sur Xeon Phi notre méthode de
mesure introduisait un biais trop important, du fait d’un manque d’optimisation de notre code
pour cette architecture. Les résultats de cette architecture sont donc donnés par la méthode de
confirmation à base d’un accès complet par memset. Ceci explique l’absence de barres d’erreurs
sur ce graphique. Les temps sont donnés par page par thread ; on attend donc idéalement un
temps constant.
Sur les nœuds de 128 cœurs, la mesure montre une relative extensibilité pour les processus,
donc pour des approches types MPI. Un léger effet est observable au-delà de 8 cœurs et induit
par la structure NUMA du nœud. À l’opposé, l’utilisation de threads conduit à une augmenta-
tion proportionnelle au nombre de flux utilisés. Ce problème se comprend bien si l’on considère
que la table des pages d’un processus est commune à l’ensemble de ses threads. Toute modifica-
tion de cette dernière nécessite donc, une prise de verrous conduisant au problème observé. Ce
manque d’extensibilité peut devenir bloquant pour toute application ayant tendance en contexte
parallèle à libérer/allouer des segments de grandes tailles comme nous l’avons vu avec l’applica-
tion Hera. Remarquons que les simulations numériques tendent à fonctionner par phase et donc
à grouper les allocations. Ce comportement tend donc à favoriser les contentions sur les alloca-
tions. Ce problème a été étudié en 2011 par l’équipe de Clements Austin[CKZ12] en pointant
les contentions sur ces verrous. Ils ont ainsi proposé une modification des algorithmes du noyau
pour maximiser l’utilisation des RCU[MS98] à la place des verrous conventionnels. Ce type de
verrous permet des accès en lecture sans blocage. Ceci introduit toutefois des contraintes sup-
plémentaires sur les méthodes de mise à jour qui impliquent des restrictions sur les algorithmes
candidats.
122
5.2. Utilisation de grosses pages
Fautes de page sur 128 coeurs Fautes de pages sur Intel Xeon Phi
512 4096
Temps (Kcycles / 4K / Tâche) Threads Threads
64 512
256
32
128
16
64
8 32
4 16
2 8
1 4
1 2 4 8 16 32 64 128 256 1 2 4 8 16 32 64 128 256
Nombre de tâches Nombre de tâche
F IGURE 5.2 – Temps des fautes de pages sur les nœuds larges Tera 100 et sur Xeon Phi. Les barres
d’erreurs donnent les quartiles 50% et 80%.
Sur Xeon Phi, même observation pour les threads. Toutefois, les processus sont cette fois-ci
impactés par le problème. Nous n’avons pour l’instant pas de preuves formelles de la source de
ce nouveau problème. Nous supposons qu’il s’agit d’un problème de contention sur certaines
structures globales du noyau (compteurs, listes...). Sous Linux, la mémoire est découpée en ré-
gions correspondant aux différents nœuds NUMA. Le Xeon Phi n’est pas vu comme NUMA pas
l’OS. La seule région mémoire mise en place est donc accédée par les 240 threads exploitables
contre une limite à 8 pour notre nœud 128 cœurs. On remarquera également que les instruc-
tions atomiques sont plus pénalisantes sur Xeon Phi que sur les processeurs conventionnels. Des
problèmes peuvent donc apparaître sur certains compteurs communs (mémoire consommé par
l’utilisateur...).
En section 2.5.3 nous avons décrit la présence d’un support de grosses pages de 2 Mo dans
les architectures types x86_64. Ces dernières sont habituellement mises en place pour améliorer
les performances des TLB. Ces gains s’obtiennent notamment par une réduction du nombre de
pages nécessaires à l’adressage, par un facteur 512 comparé à une base de 4 Ko. On peut alors
se demander si cette réduction du nombre de pages ne peut pas également réduire la contention
que nous observons sur les fautes de pages de L INUX.
Le graphique 5.3 donne le résultat des mesures obtenues avec l’implémentation THP de
Linux. Les résultats avec grosses pages sont divisés par un facteur 512 pour normaliser ces
derniers sur la base de segment de 4 Ko. Cette normalisation permet ainsi de comparer le coût
relatif aux pages standards de 4 Ko sur une base commune. Sur ce graphique, on remarque une
amélioration des performances séquentielles avec une réduction du coût de 3400 à 2000 cycles,
soit une réduction de 40% que l’on doit comparer au facteur 512 attendu dans l’idéal. Avec 24
threads, les coûts deviennent similaires aux pages standards. On observe de plus, l’apparition du
même problème d’extensibilité avec une dégradation plus rapide des performances. Les grosses
pages apportent donc un léger gain en séquentiel, mais souffrent du même problème que les
pages standards en parallèle sur 24 threads.
123
Chapitre 5. Problématique de remise à zéro de la mémoire
14
Temps (Kcycles / 4K / Thread)
12
10
0
5 10 15 20
Nombre de threads
F IGURE 5.3 – Mesure des temps des fautes de pages en utilisant l’implémentation THP de Linux sur
les nœuds Bi-Westmere du calculateur Cassard. La mesure est effectuée en accédant à un élément de
chacune des pages de 2 Mo. Les temps obtenus sont divisés par 512 pour donner un temps normalisé
par segments de 4 Ko.
124
5.5. Proposition : réutilisation des pages
Utilisateu
Processus 1 Processus 2 Processus 1 Processus 2
F IGURE 5.4 – Principe de réutilisation des pages au niveau noyau permettant d’éliminer le besoin
de remise à zéro du contenu des pages.
en espace utilisateur dans une publication [YBF+ 11] en considérant les ramasses miettes pour
des langages tels que java. Cette étude discute notamment d’un choix de libération différée. Ils
analysent également l’utilisation d’accès mémoires non temporels (non-temporal store) permet-
tant d’outrepasser les caches et de ne pas évincer des données utiles pour la suite. Les auteurs
discutent également une technique employée dans certaines machines virtuelles Java en effec-
tuant des remises à zéro par lots au moment de la libération plutôt que sur le chemin critique
lors de l’allocation.
D’une manière similaire les développeurs de Windows[RS09] ont intégré dans leur noyau
un système permettant d’effectuer la remise à zéro des pages depuis un thread système de faible
priorité. Les listes de pages libres distinguent donc les pages remises à zéro des autres. Cette
approche permet d’éliminer le coût de remise à zéro sur le chemin critique des fautes de pages.
Cette dernière a également l’avantage, en contexte virtualisé, de générer des pages fusionnables.
Ces pages peuvent alors être fusionnées par des techniques de type KSM que nous discuterons
dans le prochain chapitre.
Nous nous sommes donc orientés vers une approche radicalement différente, en partant du
constat que la mémoire est très souvent initialisée juste après son allocation. On note de plus
que la fonction malloc, de par sa définition, ne garantit pas de remise à zéro de la mémoire
allouée. C’est de fait, ce qui arrive lorsqu’elle réutilise des segments mémoires de petite taille.
On se propose donc de supprimer autant que possible le besoin de remise à zéro. Au niveau de
l’OS, ces dernières sont toutefois nécessaires pour interdire toute fuite d’information entre les
125
Chapitre 5. Problématique de remise à zéro de la mémoire
entités en exécution. On remarquera toutefois qu’une page précédemment utilisée par un pro-
cessus, peut sans problème être réutilisée par ce même processus, puisqu’elle ne contient que
des données qui lui sont propres. Comme le montre la figure 5.4, ce fonctionnement peut-être
obtenu en créant un cache de pages en espace noyau et attaché à chaque processus. Les pages
peuvent alors y être capturées lors des libérations (munmap) et réutilisées sans remise à zéro
lors des fautes de pages suivantes.
Sur le principe, cette approche revient à pousser plus loin la réutilisation que nous avions
mis en place au sein de l’allocateur pour les gros segments, mais en descendant le cache au
niveau du noyau. Cette modification apporte deux intérêts majeurs en comparaison du travail
en espace utilisateur :
Maîtrise de la consommation : Nous avons vu que la réutilisation de gros segments au ni-
veau utilisateur pouvait générer une surconsommation dans le cas d’applications allouant
plus de mémoire virtuelle que nécessaire. Avec une approche noyau, ce cas de figure est
automatiquement pris en charge en maintenant l’efficacité du mécanisme d’allocation pa-
resseuse.
Réclamation : La méthode utilisateur tend à augmenter la consommation mémoire de l’appli-
cation par rétention de segments au niveau de l’allocateur. En cas de besoin mémoire de la
part d’autres processus ou de l’OS, il est toutefois impossible ou difficile de réclamer cette
mémoire. Avec l’approche noyau, l’OS peut très facilement réclamer les pages en attentes
dans les caches locaux des processus.
Support NUMA : Au niveau utilisateur, il n’est possible d’effectuer un contrôle NUMA qu’à la
granularité d’un segment et de supposer le placement des pages de ce dernier. Ce problème
est absent du côté noyau avec une gestion qui se place à la granularité de la page. Ce
niveau d’abstraction profite en effet de toutes les informations de placement du thread
générant la faute de page.
Réduction de contention : Cette approche permet de réduire les contentions sur les listes glo-
bales de pages pour un fonctionnement par processus. En mode processus léger, il est par
contre nécessaire de travailler l’implémentation pour ne pas introduire une contention sur
le cache mis en place.
La sémantique POSIX de mmap impose par sa définition le renvoie d’une mémoire initialisée
à zéro, il n’est donc pas possible d’inclure notre approche dans cette interface sans une extension
de sa sémantique. Par défaut, le comportement de mmap est maintenu. Nous avons donc ajouté
un drapeau permettant d’informer mmap que la mémoire allouée n’a pas besoin d’être initia-
lisée. L’expression de cette information par l’appelant permet ainsi de faire cohabiter les deux
126
5.7. Détails d’implémentation
sémantiques. Cette nouvelle expression peut être exploitée dans les fonctions malloc et realloc
qui au contraire de calloc n’ont pas à assurer une mise à zéro de la mémoire.
5.7 Détails d’implémentation
5.7.1 Modification de Linux
On peut dans un premier temps se demander s’il n’est pas possible d’implémenter la modi-
fication proposée sous la forme d’un module noyau. Il convient toutefois de remarquer qu’un
rapide test montre que le coût des fautes de pages est doublé lorsque l’on tente d’exploiter ce
type d’approche. Or, pour les pages standards, nous attendons un gain de l’ordre de 40% cor-
respondant à la fraction de temps associée à la fonction clear_page. Pour les pages standards,
il nous faut donc évaluer l’implémentation au niveau du code noyau principal. Concernant les
grosses pages, il n’est pour l’instant pas possible de les manipuler depuis l’interface offerte aux
modules, il faudrait donc recourir à une approche de type VHP (Virtual Huge Pages) développée
lors du stage de fin d’étude ayant conduit à cette thèse[SM]. Il a donc été décidé de modifier
directement le noyau pour évaluer le réel intérêt de l’approche.
Les modifications ont été réalisées sur les versions 2.6.32 modifiée par Redhat et 2.6.36 offi-
cielle. Au niveau du noyau, nous avons dans un premier temps défini une nouvelle structure de
gestion des pages en attentes. Cette structure est alors injectée dans la structure de description
de l’espace mémoire virtuel de chaque processus (mm_struct). Elle suit ainsi le même cycle de
création/libération que le processus associé. Lors d’un fork, le nouveau processus réinitialise sa
structure de sorte qu’il ne partage aucune page avec le précédent. Les implémentations noyau
des appels madvise et mmap sont alors modifiées pour prendre en compte l’activation du cache
local en fonction du drapeau décrit précédemment (MAP_PAGE_REUSE).
Les modifications délicates sont alors mises en place pour dérouter les chemins d’appels stan-
dards de faute de page et de libération. Lors des fautes de pages, le chemin standard est dérouté
au niveau de la fonction do_anonymous_page dédiée aux fautes de pages anonymes qui nous
intéressent. Si le segment touché dispose du drapeau, une page est cherchée dans le cache local.
Si le cache est vide ou que le drapeau de réutilisation n’est pas actif, le noyau poursuit le chemin
standard et renverra une page remise à zéro comme à l’origine. De manière identique, les grosses
pages sont supportées en modifiant la fonction spécifique do_huge_pmd_anonymous_page.
Les problèmes principaux ont été rencontrés sur le choix du point de capture qui idéale-
ment doit se situer au niveau des fonctions tlb_remove_page ou zap_pte_range. Ce choix s’est
toutefois avéré difficilement praticable du fait de problèmes de cohérence avec les mécanismes
d’invalidation des TLB. La page ne doit en effet pas être enregistrée dans notre cache tant que le
processeur la croit projetée dans l’espace du processus. La version finale modifie donc la fonction
zap_pte_range et zap_huge_pmd pour activer un drapeau sur la page considérée et la marquer en
attente de capture. L’opération de capture prend alors place plus en aval de la pile d’appels au
niveau des fonctions free_hot_cold_page, au point où elle s’insère normalement dans des listes
pour réutilisation rapide dans le noyau d’origine. Cette approche bien qu’élégante n’avait pas
été retenue initialement, car elle consomme un bit de drapeau supplémentaire sur les pages qui
en utilise déjà un grand nombre. Une capture à ce point nécessite également plus d’efforts de
validation en terme de sécurité pour assurer une capture limitée aux pages désirées. Certaines
subtilités sont également à prendre en compte quant à la mise à jour des compteurs d’utilisation
des pages, afin de ne pas aboutir à des valeurs négatives. Ces problématiques techniques ont
occupé l’essentiel du temps de travail sur cette modification.
On remarque qu’en pratique les modifications à l’intérieur du noyau sont relativement limi-
tées avec un différentiel représentant au total 720 lignes dont la moitié sont dédiées à l’implé-
127
Chapitre 5. Problématique de remise à zéro de la mémoire
mentation des fonctions de manipulation de la structure elle-même. Il s’agit donc d’une modifi-
cation qui peut raisonnablement être vérifiée et portée sur les différentes versions du noyau.
Ce point peut être résolu en nettoyant le contenu de la page au moment de la capture pour
les zones sans réutilisation, ou bien, en ne capturant que les pages des zones avec ce support.
Nous avons retenu la dernière méthode dans notre prototype. Il faut toutefois remarquer que
dans ce mode, un logiciel malicieux pourrait faire grossir sans limite le cache en usant de l’appel
madvise pour y libérer les pages, mais ne jamais les ré-utiliser en effectuant plus d’allocations
avec le drapeau activé. Ce problème se résout toutefois de manière automatique, si l’on dispose
d’une intégration dans le système de réclamation de pages, comme discuté dans la suite, ou en
supprimant l’utilisation de madvise pour ce drapeau.
Le choix d’une capture limitée aux zones marquées permet également de n’activer le cache
que lorsqu’il a une réelle utilité. On évite ainsi d’impacter le système dans son fonctionnement
standard.
128
5.8. Résultats expérimentaux
trop, l’OS viendra naturellement ponctionner des pages dans ce dernier, limitant de fait sa taille.
Ceci justifie notre choix de ne pas intégrer de compteurs spécifiques nécessaires à un contrôle
actif. Ce choix est fait dans un contexte HPC, il peut ne pas être valide dans un contexte général
avec divers processus de consommation équivalente en cas de restriction mémoire. Le support
de la réclamation n’est pas indispensable à une première évaluation d’intérêt. Il a donc été laissé
pour travaux futurs bien qu’il a été vérifié qu’une telle modification est possible dans la structure
actuelle de Linux.
Cette intégration a donc été faite dans l’allocateur de MPC développé par nos soins. Nous
avons également modifié Jemalloc qui introduisait déjà nativement la propagation de ce type
d’information. Cet allocateur est un bon candidat expérimental du fait de sa politique agressive
de libération stressant l’OS.
5.8.1 Micro-benchmark
Fautes de pages modifiées sur 1 socket de 6 coeurs Fautes de pages modifiées sur 1 socket de 6 coeurs
12 18
Noyau standard Noyau standard
Temps (Kcycles / 4K / Thread)
11 16
Noyau modifié Noyau modifié
10
14
9
8 12
7 10
6 8
5 6
4
4
3
2 2
1 0
0 2 4 6 8 10 12 0 5 10 15 20 25
Nombre de threads Nombre de threads
Le graphique 5.5 donne les résultats d’application du micro-benchmark précédent sur les
fautes de pages. Les mesures montrent une nette amélioration des performances séquentielles
129
Chapitre 5. Problématique de remise à zéro de la mémoire
avec un temps de faute de page passant de 3400 à 1900 cycles soit un gain de 45% correspon-
dant à l’ordre de grandeur attendu. L’amélioration est également notable en fonctionnant sur
un unique processeur (6 cœurs hyperthreadés, donc 12 processus légers) avec un temps passant
de 8950 à 2900 cycles, soit un gain de 66%. Cette amélioration de passage à l’échelle peut s’ex-
pliquer en considérant une réduction de la saturation des accès mémoires et une réduction de
la taille de la section critique entre les verrous en lecture. Les effets NUMA deviennent toute-
fois dominants, dès lors, que l’on exploite l’ensemble de la machine avec 24 threads. Les gains
se limitent alors à la réduction du coût constant de remise à zéro, soit, 33%. La réduction des
contentions sur les verrous en mode NUMA reste donc un problème prioritaire pour les pages
de 4 Ko.
Les résultats obtenus avec les grosses pages sont fournis dans la figure 5.6. Dans ce mode, les
gains obtenus sur la remise à zéro deviennent prépondérants et permettent d’obtenir une réduc-
tion des coûts par un facteur 57. Le coût relatif est donc ramené à 35 cycles par page équivalente
de 4 Ko. Remarquons que la réduction de bande passante et de taille de la section critique per-
mettent également une nette amélioration de l’extensibilité. Le ralentissement observé lors du
passage de 1 à 24 threads était d’un facteur 3.1, il devient 1.4 avec notre patch.
10
0.1
0.01
5 10 15 20
Nombre de threads
F IGURE 5.6 – Évaluation de l’impact de notre proposition sur micro-benchmark en exploitant des
grosses pages sur les nœuds Cassard.
130
5.8. Résultats expérimentaux
TABLE 5.1 – Mesure avec la version OpenMP du benchmark HydroBench sur les 12 cœurs du cal-
culateur Cassard. La version Perf. (performance) de notre allocateur correspond à l’activation d’un
politique de réutilisation maintenant les gros segments de l’application en espace utilisateur pour
réutilisation rapide.
tableaux.
La table 5.1 montre des gains de 12% sur le temps d’exécution et 37% sur le temps système
en employant notre modification de l’OS (S2,S3). Il est bien sûr possible d’obtenir de meilleurs
gains (44%) en travaillant au niveau de l’allocateur mémoire grâce à une réduction importante
du nombre de fautes (S2,S4). Les grosses pages améliorent par elles-même, les performances
de 12% (S1,G1). Notre modification du noyau apporte, elle, une division par 2.5 du temps
système (G2,G3) rendant le cache en espace utilisateur moins efficace (G3,G4). Des gains plus
importants, jusqu’à 52% sont logiquement obtenus en modifiant les schémas d’allocation au
niveau du code de l’application (S4,S5 et G4,G5). Nous remarquerons toutefois, que ce type
de correction n’est pas forcément possible dans une application plus complexe, limitée par sa
consommation mémoire.
Les résultats obtenus avec notre modification du noyau sont donnés dans la table 5.3 pour
les nœuds Cassard. Les tests sont réalisés avec des versions modifiées des allocateurs Jemalloc
et MPC. Avec les pages standards, la modification du noyau permet d’obtenir un gain global
de performance de 2% (S2,S3 et S4,S5). Le temps système, lui, est impacté par une réduction
de 33%, correspondant aux gains observés sur le micro-benchmark précédent. Sur les grosses
131
Chapitre 5. Problématique de remise à zéro de la mémoire
TABLE 5.2 – Temps d’exécution de l’application Hera sur les nœuds 12 cœurs de Cassard. Les temps
sont donnés par thread.
pages, notre modification induit une amélioration des performances sur le temps total de 30%
et 5% pour les deux allocateurs ayant une faible consommation (H2,H3 et H4,H5). Les temps
systèmes sont eux réduits respectivement d’un facteur 9.7 et 2.4. Dans le cadre de MPC, cette
modification permet de rendre le profil à basse consommation aussi efficace que le mode NUMA
(H1,H3). En d’autres termes, cette modification du noyau permet de compenser le surcoût induit
par les libérations agressives de mémoire.
TABLE 5.3 – Benchmark de notre modification noyau avec l’application Hera sur les noues 12 cœurs
du calculateur Cassard. Hera est exécuté avec 12 processus légers en un seul processus. Les temps
utilisateurs et systèmes sont donnés en secondes par thread.
5.9 Conclusion
Ce chapitre reprend le problème de performance observé sur les architectures parallèles mo-
dernes et s’intéresse aux surcoûts introduits par l’OS lui même. Dans le cadre de cette étude,
nous avons montré que les fautes de pages étaient impactées par un manque de passage à
l’échelle. En complément des travaux d’autres équipes, nous nous sommes intéressés à la frac-
tion de surcoût (40%) induite par les mécanismes de remise à zéro des pages renvoyées par l’OS.
Nous avons vu que certains tentent au niveau allocateur d’optimiser ces remises à zéro en
utilisant des écritures intemporelles. Du côté OS, nous avons rappelé que des OS comme Win-
132
5.9. Conclusion
dows pouvaient déplacer ces dernières afin de les sortir du chemin critique d’allocation. Au
contraire de ces deux méthodes nous avons choisi de chercher à éliminer le besoin de recourir à
ces remises à zéro. On peut ainsi espérer un gain de bande passante, d’utilisation du processeur
et probablement d’énergie. Pour ce faire, il a été remarqué qu’une réutilisation locale au proces-
sus pouvait permettre de maintenir les contraintes de sécurité, tout en éliminant ces nettoyages
mémoires. Ce comportement a été introduit en étendant la sémantique associée à mmap. Nous
permettons ainsi à l’appelant de notifier l’OS du besoin ou non de mémoire pré-initialisé à zéro.
Les micro-benchmarks montrent une amélioration de 40% sur les fautes de pages stan-
dards séquentielles et une amélioration en parallèle en l’absence d’effet NUMA. Les observations
montrent toutefois que ces effets sont à prendre en compte et nécessitent toujours des amélio-
rations au niveau des verrous de l’OS. Les gains observés restent toutefois de l’ordre de 32% sur
24 threads. L’approche retenue a également donné des résultats intéressants et novateurs pour
les grosses pages, proportionnellement plus pénalisées par ces remises à zéro. Grâce à notre
approche, ces dernières peuvent également être utilisées avec la motivation d’augmenter les
performances d’allocation, les gains représentant une réduction des coûts par un facteur 57 en
terme de temps système.
Sur des simulations numériques, cette méthode a montré des améliorations de 1% (Hera)
à 12% (HydroBench) sur les temps d’exécution globaux avec pages standards, mais dans les
deux cas, une réduction de 30% du temps système associé. Les grosses pages modifiées ont
notamment montré leur intérêt sur l’application Hera en permettant une réduction du temps
d’exécution de 30%. Ce gain est comparable à la méthode de rétention mémoire en espace uti-
lisateur. Cette méthode permet donc de compenser les libérations agressives de mémoire.
Ces résultats sont donnés sur un calculateur 12 cœurs moins impactés par l’OS que les nœuds
larges à 128 cœurs. Il faut donc s’interroger sur la projection de des résultats sur ces gros nœuds
qui devrait montrer un plus grand intérêt pour cette technique. Ces tests n’ont pour l’instant pas
pu être réalisés faute d’accès en temps voulu à ce type de machine avec droits administrateurs.
133
Chapitre 5. Problématique de remise à zéro de la mémoire
134
Chapitre 6
6.1 Introduction
De nos jours, la quantité de mémoire disponible n’augmente pas aussi rapidement que le
nombre de cœurs. Il devient donc de plus en plus important de réduire au maximum la consom-
mation mémoire des applications. Les approches décrites précédemment ont eu pour objet prin-
cipal la prise en compte de la problématique de l’allocateur mémoire notamment en terme de
performances. Dans le chapitre précédent, nous avons cherché à améliorer les performances
de l’OS pour permettre une libération plus agressive de la mémoire et ainsi améliorer le ratio
performance/consommation mémoire. En complément, nous allons ici évaluer une technique
actuellement offerte par le noyau Linux pour réduire l’empreinte mémoire des applications.
Dans les simulations, il arrive que certaines données soient dupliquées. Dans un contexte
MPI, c’est par exemple le cas pour les tables de constantes physiques si l’on utilise plusieurs pro-
cessus par nœud. On peut également citer les maillages contenant des données très répétitives
(beaucoup de 0...). Ces problèmes de données dupliquées sont également rencontrés dans le
cadre des offres de serveurs mutualisés. Dans ce cadre, les serveurs doivent offrir une grande
quantité de mémoire pour gérer le fonctionnement simultané des différentes machines virtuelles
(VM). Or, il est fréquent que le même système d’exploitation soit installé sur chacune des VM.
Il en résulte une duplication d’un grand nombre de données en mémoire (codes exécutables,
ressources diverses, images...).
Dans ce contexte, les développeurs de KVM 1 [Hab08] ont mis au point un composant noyau
pour Linux : KSM (Kernel Samepage Merging)[AEW09] dont l’objectif est de fusionner les pages
mémoires ayant des contenus identiques. Il est ainsi possible de réduire la mémoire consommée
par les machines virtuelles gérées par KVM. Ces travaux sont en partie associés, à A. Arcangeli
à qui l’on doit le support actuel des grosses pages dans Linux. Ce module est présent dans la
branche officielle du noyau depuis la version 2.6.32. Des mécanismes similaires (TPS : Transpa-
rent Page Sharing) existent également dans les solutions de virtualisation propriétaires tels que
VMWare[Wal02].
135
Chapitre 6. Étude complémentaire sur le problème de consommation : KSM
nos activités[AEW09]. Leur analyse s’intéresse surtout au problème de duplication des modèles
de détecteurs équivalents aux tables de constantes de nos programmes MPI. Au contraire, nous
évaluerons ici l’application de la méthode sur des données plus dynamiques pour identifier les
redondances au sein du maillage actif. Dans un premier temps, nous rappellerons les principes
de base concernant la gestion des mémoires partagées. Puis nous décrirons le fonctionnement de
KSM. Enfin, nous donnerons quelques résultats obtenus sur l’application Hera en montrant qu’il
est possible avec KSM d’éviter de recourir à de trop coûteuses indirections. Nous exposerons à
l’occasion certaines limites de l’implémentation actuelle de KSM (version datée de début 2011).
Processus 1
F IGURE 6.1 – Exemple de partage de pages physiques entre deux instances d’une application par
le mécanisme de pagination. Ici par exemple, le segment de code de deux instances d’une même
application.
La figure 6.1 illustre un tel partage entre deux processus utilisant le même exécutable. Ce
type de partage reste totalement transparent pour l’application, car géré entièrement par le
matériel et le système d’exploitation. Bien qu’ils reposent sur les mêmes mécanismes, on peut
distinguer deux cas particuliers pour ces partages. Ils correspondent essentiellement à deux
manières d’interagir avec l’OS pour demander leur mise en place :
Mémoire partagée (SHM 2 ) : l’objectif est de partager de manière définitive un segment mé-
moire. Dans ce cas, les modifications apportées par l’un des utilisateurs du segment seront
immédiatement répercutées sur les autres puisque le même segment physique est utilisé.
Cette approche peut, par exemple, être utilisée pour faire communiquer des processus au
sein d’un même nœud.
Copie sur écriture (COW 3 ) : la copie sur écriture a pour but de partager temporairement des
segments mémoires en lecture. Dans ce cas, lors de la première écriture, l’OS va dupliquer
la page afin que la modification n’impacte pas les autres utilisateurs du segment. Ce cas de
figure est illustré sur la figure 6.2. Cette approche est utilisée par le système pour éviter de
dupliquer les codes exécutables et bibliothèques dynamiques. C’est également sur la base
de ce mécanisme que KSM se construit.
136
6.3. Principe de KSM
F IGURE 6.2 – Exemple de copie sur écriture (COW) entre trois processus P1,P2 et P3.
Pour trouver les pages identiques, KSM procède à une comparaison bit à bit du contenu des
pages (avec un memcmp) en faisant une recherche dans un arbre équilibré. Cette méthode est
potentiellement plus coûteuse comparée à l’utilisation d’une méthode de hachage, mais permet
de ne pas entrer en conflit avec un brevet de VMWare et d’éviter tout risque de collision. Lorsque
deux pages similaires sont identifiées, la table des pages est mise à jour pour ne garder qu’une
des deux pages physiques et libérer la seconde. Si par la suite l’application modifie le contenu
de la page, le mécanisme de copie sur écriture va dupliquer automatiquement la page.
4. Le fork est une opération permettant de créer une copie d’un processus. Lors de cette copie, la mémoire des
deux instances est entièrement initialisée en mode copie sur écriture.
137
Chapitre 6. Étude complémentaire sur le problème de consommation : KSM
La contrainte précédente rend délicat le marquage des segments alloués au préalable par la
fonction malloc car leur alignement ne peut être garanti. Il faut donc passer directement par un
appel à mmap, ou disposer d’un allocateur modifié se chargeant lui-même d’effectuer le mar-
quage. La seconde méthode est très certainement préférable, car elle n’impacte pas directement
le code de l’application et maintient l’isolation des responsabilités. Au niveau de l’allocateur,
il suffit d’intercepter les appels à mmap et brk afin de marquer la mémoire allouée. C’est par
exemple trivial avec l’allocateur actuel du framework MPC (patch d’une ligne). En contrepartie,
cette méthode risque de marquer trop d’éléments inintéressants. Nous noterons toutefois que
pour les simulations numériques, la majeure partie de la mémoire et habituellement dédié au
maillage que l’on cherche à réduire dans nos tests.
Nom Signification
run Permets d’activer (1) et désactiver (0) le démon ksmd.
pages_to_scan Nombre de pages à scanner à chaque réveil du démon.
sleep_millisecs Délais entre deux scans.
138
6.4. Test sur Hera
KSM a été testé sur cette application afin d’évaluer les gains qu’il peut apporter en compa-
raison des chunks. Le maillage ayant beaucoup de zones similaires, on peut supposer que KSM
parviendra à fusionner les pages et à compenser la désactivation de ces indirections. Ceci per-
mettrait au code de fonctionner de manière plus efficace, plus propre, tout en réalisant des gains
mémoires.
6.4.2 Résultats
La méthode a été appliquée à Hera en considérant un problème Air-Alu à 6 matériaux en dé-
clarant trois matériaux virtuels pour l’air et pour l’aluminium. Dans un premier temps, les tests
ont été réalisés en fixant l’agressivité de KSM avec pages_to_scan = 2000 et sleep_millisecs =
20. Ces valeurs correspondent plus ou moins au choix optimal pour Hera compte tenu de nos
évaluations de l’espace des paramètres. Sur la figure 6.3 on observe clairement les gains ap-
portés par KSM : 16% lorsque les indirections sont désactivées et 12% lorsqu’elles sont actives.
On remarque également que l’impact sur les performances est négligeable dans ce cas-ci. En
utilisant les 8 threads, on observe des gains mémoires du même ordre. On remarquera que l’on
disposait de 8 hyper-threads sur lesquels KSM pouvait tourner seul.
On remarque sur la figure 6.4 que les gains mémoires ne sont pas immédiats, KSM fusionne
petit à petit le contenu de la mémoire. Il en résulte une limite. En effet, le pic mémoire n’est pas
139
Chapitre 6. Étude complémentaire sur le problème de consommation : KSM
4
120
3
80
2
1 40
0 0
np4 np8 np4 np8
F IGURE 6.3 – Gains observés avec KSM sur une exécution d’Héra utilisant 4 ou 8 processus MPI sur
8 coeurs disponibles avec 2.3 millions de mailles. La mémoire utilisée est donnée sous la forme d’une
moyenne sur l’ensemble de l’exécution.
réduit en proportion du gain moyen. Ici, KSM n’analyse donc pas les pages assez rapidement.
On peut rappeler à l’occasion que KSM ne dispose que d’un unique thread noyau pour scanner la
mémoire, ce qui est très certainement beaucoup trop faible pour réaliser des fusions très agres-
sives avec des applications utilisant plusieurs coeurs.
La figure 6.5 montre un test réalisé avec un problème consommant 14Go de mémoire et
utilisant 8 processus MPI. On observe des gains mémoires moyens plus faibles avec un temps
d’exécution plus impacté, bien que restant très largement inférieur au temps d’exécution obte-
nue en laissant les indirections actives. Le détail est en annexe, mais sur ce test, par moment,
KSM parvient à réduire la consommation mémoire autant que les indirections. Il lui faut toute-
fois du temps et il perd ses gains lors des pics de consommation.
Un de nos tests a été réalisé par erreur en laissant active une option d’instrumentation du
code à la compilation. Hera était donc exécuté avec des performances dégradées. Lors de ce
test, nous avons remarqué que le gain mémoire apporté par KSM était bien plus important que
les cas précédents. La figure 6.6 donne les résultats obtenus lors de ce test. Clairement, sur la
figure 6.6 KSM dispose de plus de temps pour fusionner les pages et permet d’atteindre des
gains mémoires bien plus importants. Cette fois, le pic de consommation est lui aussi diminué.
Un test réalisé en mode séquentiel sur un cas plus petit montre même des gains mémoires supé-
rieurs à ceux obtenus avec les indirections. On est donc a priori limité par le côté non optimal
de l’implémentation actuelle de KSM qui ne fusionne pas les pages assez rapidement.
D’après ces résultats, KSM apporte des gains non négligeables sur l’application Hera. L’implé-
mentation actuelle montre toutefois ses limites avec une cadence de fusion limitée. Mais comme
nous l’avons vu avec la version non optimisée d’Hera, il est probablement possible d’obtenir
des gains supérieurs si KSM pouvait fusionner les pages plus rapidement. Une approche de ce
type représente donc un bon candidat pour éliminer les indirections présentes dans certaines
applications pour peu que KSM soit amélioré.
140
6.5. Limitations de KSM
Consommation mémoire
6000
std, nochunk
ksm, nochunk
std, chunk
5000 ksm, chunk
4000
Mémoire (Go)
3000
2000
1000
0
0 20 40 60 80 100 120 140 160 180 200
Temps (s)
F IGURE 6.4 – Détail de l’utilisation de la mémoire au cours du temps de Hera sur 4 cœurs.
12 500
Mémoire (Go)
10
400
8
300
6
200
4
2 100
0 0
np8 np8
F IGURE 6.5 – Test avec Hera sur un problème occupant 14Go et résolut avec 8 processus MPI avec
les paramètres de KSM pages_to_scan = 200000 et sleep_milliseconds = 100.
alignés sur cette même taille (4Ko en général). Cette limitation n’est pas contournable dans
le cadre de cette approche. Il semble toutefois qu’il soit tout de même possible d’obtenir
des gains avec cette limitation comme le montrent nos résultats.
Démon séquentiel : Le démon ksmd chargé d’analyser les pages périodiquement est actuelle-
ment implémenté de manière séquentielle. Nous avons vu sur Hera que cela représentait
une limite quant à la quantité de fusion que l’on peut attendre de KSM. Sur des nœuds
disposant d’un grand nombre de cœurs il serait certainement très souhaitable de pouvoir
rendre ce démon parallèle.
Support NUMA : Pour l’instant, KSM ne tient absolument pas compte des aspects NUMA. Le
démon va en effet tenter de fusionner toutes les pages même si ces dernières proviennent
de nœuds NUMA distincts. Cela peut être souhaitable en situation de forte consommation
mémoire, mais pas en permanence.
Contrôle de KSM : KSM fonctionne en tâche de fond avec un nombre très restreint de pa-
ramètres. Dans le cadre d’une application, il serait probablement intéressant de pouvoir
141
Chapitre 6. Étude complémentaire sur le problème de consommation : KSM
Mémoire (Go)
Mémoire (Go)
F IGURE 6.6 – Gains observés avec KSM sur une exécution d’Héra utilisant 1 ou 4 processus sur 8
coeurs disponibles. Hera a été compilé par erreur avec l’option -finstrument-function de gcc donc
avec des performances très réduites. À droite, détail temporel de la consommation mémoire du cas
à 4 processus.
interagir avec le démon. Pour demander explicitement l’analyse des pages lors de certaines
phases, par exemple. En cas de pic mémoire, l’application pourrait être prête à céder de
son temps de calcul (via l’allocateur) pour fusionner des pages et ainsi éviter d’enclencher
la pagination disque ou se faire interrompre.
Observable mémoire : L’implémentation actuelle de KSM ne met pas à jour le nombre de pages
physiques enregistrées auprès du processus (RSS : Resident Segment Size). Il n’est donc
pas possible d’observer le taux de fusion en suivant cette observable via ps ou top. Les gains
sont visibles sur la mémoire libre globale du système. La mise à jour de RSS n’étant pas
réalisée, il faudrait s’assurer que les gestionnaires de tâche ne tentent pas tuer l’application
en détectant une utilisation mémoire supérieure à la réalité.
Passage du pic : Nous l’avons vu sur Hera, bien que l’application consomme en moyenne moins
de mémoire, la réduction du pic est moins importante. Les nouvelles allocations ne sont
en effet pas réalisées en mode pré-fusionné. Il faut donc du temps à KSM pour analyser
les pages et les fusionner. Une solution serait de pouvoir notifier KSM pour le réveiller de
manière interactive lorsque l’on arrive à un pic critique ; quitte à ce que l’allocateur fasse
attendre l’application le temps que la mémoire soit fusionnée.
142
6.7. Piste non évaluée : extension de la sémantique de mmap.
6.8 Conclusion
Nous avons vu que KSM proposait un mécanisme actif permettant de fusionner les pages
physiques identiques en mode copie sur écriture. Cette approche à la base développée dans le
cadre de KVM, peut également être appliquée aux applications pour réduire leur empreinte mé-
moire, tout en maintenant des performances décentes. Dans certains cas, KSM peut permettre
d’éliminer les indirections mises en place au niveau logiciel pour réduire la consommation mé-
moire de certaines applications. Au contraire des approches logicielles, KSM a l’avantage de ne
pas dégrader l’optimisation du code par le compilateur et de profiter des mécanismes matériels.
143
Chapitre 6. Étude complémentaire sur le problème de consommation : KSM
Sur Hera, bien que la version actuelle de KSM montre ses limites, nous avons pu observer
des gains mémoires de l’ordre de 15%. Dans un cas, les gains ont pu atteindre 35%, et ce, en
gardant des performances proches du mode sans indirections et sans modifications lourdes de
l’application. La version actuelle de KSM étant séquentielle, les fusions ne sont toutefois pas
assez rapides pour réduire certains pics de consommation.
KSM est actuellement conçu principalement pour les machines virtuelles et pour interagir
le moins possible avec ces dernières. Pour une utilisation plus générale, il serait probablement
intéressant de lever certaines limitations de l’implémentation actuelle, notamment la limite liée
à l’aspect séquentiel du démon ksmd et le non-support des nœuds NUMA. Une collaboration
entre le démon ksmd et l’application via l’allocateur pourrait également être souhaitable pour
un usage en contexte HPC.
144
Troisième partie
Conclusion et perspectives
145
Chapitre 7
Conclusion
Dans ce manuscrit, nous avons dans un premier temps rappelé l’évolution des supercalcula-
teurs massivement parallèles atteignant aujourd’hui l’ordre du million de cœurs. La structuration
de ces calculateurs doit aujourd’hui répondre aux problématiques croissantes de consommation
d’énergie, d’accès à la mémoire et de stockage de l’information (mémoire et systèmes de fi-
chiers). Les solutions actuellement retenues conduisent à la construction d’architectures très
hiérarchiques composées de grappes de nœuds NUMA multicœurs. Ces architectures impliquent
une programmation à mémoire partagée (threads) en plus de l’approche historique à base de
mémoire distribuée (MPI). Dans ce contexte, avec un nombre croissant de threads à exploiter,
le système d’exploitation et les bibliothèques sont soumis à un besoin croissant de support du
parallélisme et de prise en compte de ces hiérarchies.
Nous nous sommes donc intéressés aux problématiques liées à la gestion de la mémoire du
point de vue HPC. L’analyse préliminaire réalisée en début de thèse a ainsi mis en évidence un
problème d’interférence possible entre les différents composants de la chaîne de gestion mé-
moire (caches processeurs, OS, allocateur, application). Cette étude s’est surtout intéressée au
problème de placement des données vis-à-vis des caches en évaluant les politiques de coloration
de pages des OS. À l’opposé du discours conventionnel, nous avons ainsi montré l’intérêt habi-
tuellement négligé d’une politique de coloration aléatoire telle qu’employée dans Linux. Il a été
montré que cette approche offre une plus grande résistance aux cas pathologiques en compa-
raison des méthodes de coloration dites “régulières”. Ces méthodes trop régulières conduisent
à des effets de résonances qui dépendent des décisions de l’allocateur mémoire et du schéma
d’accès à la mémoire par l’application. Les dégradations observées peuvent alors représenter des
facteurs entiers tels que cela a par exemple été observé sur EulerMHD (facteur 3 sur 8 cœurs).
L’augmentation du nombre de cœurs couplée à l’exploitation de caches partagés tendent à aug-
menter l’impact de ce problème. Ces pertes sont à comparer aux gains maximums de 60% sur
les NAS ou aux 5% observés sur Linpack. Il a ainsi été montré que la politique de Linux repré-
sentait un bon choix en évitant ce travers. Cette observation peut être exploitée pour améliorer
les techniques de coloration actuelles afin de supprimer leur aspect trop régulier et bénéficier
des avantages des deux méthodes. Nous avons également montré que ces problèmes touchaient
notablement les grosses pages de 2 Mo du fait de leur définition matérielle. Cette problématique
doit donc être prise en compte au niveau de l’allocateur mémoire en espace utilisateur.
147
Chapitre 7. Conclusion
tés à fournir de bonnes performances sur les nœuds 128 cœurs dont nous disposons désormais.
Les observations montrent des pertes de performances comparées à l’allocateur de la Glibc pou-
vant atteindre 20%. Les problèmes rencontrés tiennent en deux points essentiels : un manque
de prise en compte explicite des aspects NUMA et un trop grand nombre d’échanges avec le
système d’exploitation qui est affecté par des problèmes d’extensibilité. Concernant le second
point, nous avons été amenés à repenser le fonctionnement de l’allocateur avec un effet tampon
pour parer à l’impossibilité de changer rapidement les algorithmes centraux de l’OS. Nous avons
donc étendu le fonctionnement normal de l’allocateur pour les petits segments afin d’obtenir
un recyclage des grands segments (au-delà du mégaoctet). Cette approche demande toutefois
une prise en main spécifique du problème, les méthodes de réutilisation de ces grands segments
devant satisfaire des contraintes différentes des petits segments.
Avec un support du NUMA, nous avons ainsi obtenu sur une simulation numérique consé-
quente, des gains qui peuvent atteindre 50% du temps d’exécution total sur des nœuds 128
cœurs. Ces gains sont toutefois obtenus au prix d’une augmentation de la consommation mé-
moire (de l’ordre de 15%) non nécessairement acceptable pour certaines applications limitées
par la mémoire disponible. Nous avons donc travaillé pour obtenir une méthode supportant une
politique complémentaire économe au sein de la même implémentation. L’activation de ce profil
économe dégrade les performances, mais permet d’obtenir des gains mémoires équivalents à ce
que propose Jemalloc (18% avec Hera sur les nœuds 32 cœurs). L’obtention de cette possibilité
de contrôle ouvre désormais la porte à une migration dynamique d’une politique à l’autre en
fonction des phases de l’application et de la disponibilité de la ressource mémoire. Les concepts
fondamentaux mis en avant dans notre démarche peuvent être résumés comme suit :
Tas locaux et source mémoire : L’allocateur est globalement structuré sur la base de deux
composants principaux. Les tas locaux associés à chaque thread gèrent la réutilisation lo-
cale des petits segments. Ces derniers ont un fonctionnement sans verrous pour optimiser
les performances en contexte parallèle. En complément, les sources mémoires sont char-
gées de fournir des macro-blocs (taille typique de 2 Mo) aux tas locaux.
Contrôle de recyclage : Les tas locaux mettent en place des politiques de retour agressif de la
mémoire vers les sources mémoires. Ceci permet de concentrer la politique de contrôle de
consommation au niveau des sources mémoires. Cette approche implique de fait l’emploi
de décisions réversibles ouvrant la possibilité d’exploitation de choix dynamiques de la
politique à suivre. Ceci limite également la rétention de mémoire au niveau des différents
threads, point qui pourrait éventuellement poser problème.
Ré-utilisation des gros segments : Nous avons discuté l’intérêt d’exploiter une méthodologie
de recyclage des gros segments basé sur la sémantique mremap offerte pas Linux. Il est
ainsi possible d’éliminer les risques de fragmentation de la mémoire à grande échelle pou-
vant intervenir sinon.
Distinction des libérations distantes : Les tas locaux fonctionnent sans verrous, il a donc été
nécessaire de distinguer les libérations locales des libérations distantes afin d’éliminer tous
les conflits potentiels. Cette approche a été mise en place en construisant une file locale
atomique d’accumulation de blocs à libérer. Cette liste est alors vidée par le thread parent
lors des opérations mémoires suivantes.
Source mémoire NUMA : La réutilisation des macro-blocs implique un suivi de leur apparte-
nance NUMA afin d’éviter tout échange involontaire en réponse à une requête d’allocation.
En pratique, il est impossible (ou difficile) d’assurer un contrôle générique pour les threads
non fixé sur un nœud particulier. Nous avons donc mis en place une politique de confiance
isolant les threads “fiables” des threads “non fiable”. Il est ainsi possible de réduire les
risques de pollution mémoire des threads pour lesquels l’utilisateur fait des efforts de sup-
port NUMA.
148
Registre par région : La mise en place d’un registre sous forme de région nous a permis d’ob-
tenir une structure d’indexation des macro-blocs afin d’attacher l’appartenance de ces der-
niers à leur tas de rattachement. Cette approche permet ainsi de distinguer les allocations
locales et distantes. Elle permet également d’étendre la possibilité de mixer différents allo-
cateurs s’intégrant dans les opérations free et realloc standards. Remarquons que la struc-
ture retenue permet un accès essentiellement sans verrous à cet index.
Support de segments utilisateurs : La structure actuelle de l’allocateur permet également de
réutiliser ses composants internes afin de gérer les allocations sur un segment mis en place
par l’utilisateur avec des propriétés particulières (pages punaisées, mémoire partagée...).
Le recyclage de gros segments a été introduit pour compenser une faiblesse de l’OS. Nous
nous sommes donc intéressés à ce problème et avons observé qu’au-delà des problèmes princi-
paux d’extensibilité, 40% du temps des fautes de pages pouvait être consommé par des besoins
de remise à zéro de la mémoire. Nous avons également montré que les grosses pages étaient
affectées par ce problème de manière beaucoup plus importante. Sous Windows, le point d’effa-
cement du contenu des pages est déplacé pour le sortir du chemin critique. Dans ce document,
nous avons proposé de supprimer ce dernier. Les remises à zéro sont toutefois nécessaires pour
des raisons de sécurité. Nous avons donc proposé une modification de la sémantique d’interac-
tion avec mmap permettant une réutilisation locale de la mémoire par l’OS. Cette sémantique
n’impose plus l’effacement des données tout en maintenant le niveau de sécurité initial. Ceci
nous a permis de réduire de 45% les temps de fautes de pages tout en réduisant la consom-
mation de bande passante, cycle processeur et purge des caches. En contexte non NUMA, des
gains de passage a l’échelle ont également été observés. Sur les grosses pages, les gains obtenus
peuvent atteindre un facteur 57 sur micro-benchmarks, ouvrant un nouvel intérêt pour ce type
de pagination. Sur application réelle, nous avons montré sur 12 cœurs qu’il était ainsi possible de
compenser les surcoûts de libération des allocateurs mémoires exploitant des profils économes.
Ces travaux ont fait l’objet d’une publication en 2013[VSW13].
Le dernier point abordé a traité la problématique d’économie de l’espace mémoire par fusion
des pages au contenu identique à l’aide du module KSM (Kernel Samepage Memory) offert par
le noyau Linux. Cette approche a montré un certain intérêt pour la simulation numérique multi-
physiques multi-matériaux testés en réduisant intérêt d’un recourt à un système d’indirections
logicielles. L’implémentation actuelle de ce module montre toutefois certaines limites du fait de
son manque de parallélisme en ne permettant pas de fusionner assez rapidement les pages sur
un grand nombre de cœurs. Le principe général de ce type d’approche reste toutefois intéressant
à reprendre même si l’implémentation du mécanisme nécessite d’être revisitée plus en profon-
deur avec un point de vue HPC.
Pour résumer, tout au long de ce manuscrit, nous nous sommes attachés à étudier les pro-
blèmes de gestion mémoire en considérant le contexte HPC avec le nombre croissant de coeurs
organisés sous forme de hiérarchie NUMA. Au cours de ces analyses, nous avons mis en évidence
quelques points problématiques en terme de performance notamment au niveau de l’interaction
des OS / allocateur mémoire / matériel. Nous avons montré que ces composants doivent être
considérés comme un tout, afin de mettre en cohérence leurs politiques internes, qu’il s’agisse
de la problématique de placement vis-à-vis des caches ou du taux d’échange de mémoire entre
ces deux composants. Nous rappelons que la consommation de la mémoire est actuellement un
problème reprenant de l’importance. Nous avons donc également cherché à trouver un équilibre
entre cette diminution des échanges et le surcoût mémoire que cela engendre dans notre ap-
proche. Dans cette optique il a été montré qu’une meilleure coopération de l’allocateur et de l’OS
pouvait permettre par une extension sémantique d’éliminer les coûteux effacements mémoires
nécessaires à la politique de sécurité de l’OS. Un résumé de la spécificité et de l’orientation gé-
nérale de nos travaux peut être décrit comme une étude de la bonne coopération allocateur /
149
Chapitre 7. Conclusion
Il est reconnu que l’accès à la mémoire est une problématique montante sur les architec-
tures modernes. Les résultats obtenus montrent que les problèmes de gestion du partage de
cette ressource sont également un point important nécessitant d’être ré-investiguer en prenant
en compte l’évolution des architectures et des usages qui en sont faits. Lors de notre étude, nous
avons parfois observé des écarts de performance sous forme de facteurs entiers, pointant des
lacunes qu’il devient important de combler. Les problèmes observés sont en partie induits par
un manque de passage à l’échelle des mécanismes internes à l’OS. On rappelle ainsi que le coût
de gestion de cette mémoire est nécessairement proportionnel à la taille à gérer. Si les méca-
nismes ne sont pas rendus parallèles, la gestion de cet espace grandissant finira nécessairement
par poser un problème majeur. Ajoutons qu’au vu de nos travaux, l’utilisation d’une taille de
page de 4 Ko semble aujourd’hui trop faible au vu des volumes à traiter. À l’opposé, 2 Mo semble
pour l’heure une taille trop importante pour les caches. Un meilleur compromis semble se situer
proche de 64 Ko ou 128 Ko (une fraction des voies du cache pour permettre un certain aléa) si
l’on tient compte de nos résultats couplés à l’étude réalisée lors du stage ayant précédé cette
thèse.
D’une manière plus générale, l’évolution des architectures actuelles représente un défi pour
la pile logicielle existante en nécessitant un besoin de passage à l’échelle toujours plus grand et
la prise en compte de nombreux paramètres. Par ailleurs, l’augmentation de la complexité des
problèmes traités et des volumes de données associés tend à faire croître le nombre de com-
posants logiciels en interaction. Dans un contexte où les architectures évoluent rapidement, il
semble de plus en plus important de garder une capacité d’adaptabilité en limitant les adhé-
rences non réversibles à une architecture propre ou de découpler les parties adhérentes des
parties qui peuvent être abstraites. À ce titre, les méthodes de développement logiciel sont ac-
tuellement soumises à rude épreuve, particulièrement dans le domaine HPC où la performance
reste un point clé, parfois, semble-t-il, mis trop en avant avec une vue à trop court terme. Cet
objectif se réalise alors au détriment d’une capacité de maintenance et d’adaptabilité à long
terme du code et de sa performance. Ceci est particulièrement vrai si les optimisations fines se
font au prix d’une dégradation de la vue d’ensemble. Le point clé n’étant pas d’abandonner la
performance, bien au contraire, mais de lui assurer une expression maintenable.
150
Chapitre 8
Perspectives
Une partie des travaux de cette thèse mettent en lumière les problèmes d’interaction entre
logiciel et structure fine du matériel. Nous avons notamment discuté la problématique des
caches du fait de leur associativité. Ces problèmes délicats à prendre en compte au niveau
logiciel peuvent toutefois conduire à une perte importante de performance. Nous avons ainsi
proposé des pistes d’amélioration des méthodes de coloration de pages, mais n’avons pas en-
core prototypé ces modifications au niveau noyau. Sur ce point particulier, il paraît important de
suivre l’évolution de ces interactions, notamment pour évaluer l’impact de l’arrivée des nouveaux
caches partagés en forme d’anneau tels qu’employés dans le Xeon Phi. Il faudrait en effet véri-
fier si leur implémentation particulière limite ou maintient les problèmes de conflits inter-cœurs
observés dans notre étude pour les grosses pages ou les paginations régulières. Un prototype de
détection de ces cas pathologiques a également été mis au point lors de ces travaux. Ce dernier
ne supportait toutefois pas les applications multithreadées. Il pourrait donc être intéressant de
reprendre les points clés de ce prototype et d’implémenter l’analyse dans un outil tel que Val-
grind.
Au niveau des allocations, nos travaux nous ont permis d’obtenir une méthode offrant des
profils performants ou économes sur une base unique. Il est ainsi possible de reproduire les ex-
trêmes observés au travers des allocateurs Jemalloc et Tcmalloc. À ce titre, il reste désormais à
évaluer l’intérêt d’application d’une politique dynamique s’adaptant aux phases de l’application.
Dans nos travaux, nous avons pour partie laissé de côté la problématique des petites allocations
en les considérant comme suffisamment discutées dans la littérature. L’implémentation de notre
prototype mériterait toutefois d’intégrer un support plus performant reprenant les idées fon-
damentales de Jemalloc pour ces allocations. Comme discuté en fin de section 4.17.4, il serait
certainement intéressant d’évaluer l’application des concepts mis en avant dans cette thèse au
sein de l’implémentation de Jemalloc. Il serait ainsi possible de lui apporter un support NUMA
et les mécanismes de recyclage tout en profitant de sa gestion efficace des allocations petites et
moyennes.
Toujours au niveau de l’allocateur, nous avons également discuté l’intérêt de fournir (par
exemple au travers de directives de type pragma) un supplément d’information à l’allocateur
vis-à-vis des problèmes de projection NUMA. Deux des sémantiques proposées ont été suppor-
tées dans le prototype actuel. Sans ces informations, nous avons montré que certaines ambiguï-
tés pouvaient subsister, notamment au niveau de l’usage de la fonction realloc. Ce point serait
intéressant à lever si les architectures NUMA s’installent de manière durable. Sur le plan to-
pologique, il serait intéressant de choisir le niveau de placement (approche de type HLS) des
composants de l’allocateur (source mémoire, tas local). Ceci peut offrir un levier supplémentaire
pour contrôler le rapport entre contention mémoire et trop grande dissémination des tampons
d’allocations conduisant à une augmentation de la consommation mémoire. Cette remarque est
151
Chapitre 8. Perspectives
notamment liée à la structure non NUMA exposée par les architectures de type Xeon Phi. Avec
un grand nombre de cœurs, il serait en effet intéressant d’utiliser une source mémoire pour x
cœurs et par exemple exploiter un tas local par cœur physique et non thread.
Au niveau OS, l’étude préliminaire sur le problème de remise à zéro des pages a montré un
intérêt certain pour l’approche. Cette dernière reste toutefois à évaluer sur les nœuds 128 cœurs
et sur Xeon Phi afin de confirmer les gains potentiels de cette méthode sur ces architectures. Si
l’intérêt est confirmé, il reste à implémenter l’intégration aux mécanismes de réclamation mé-
moire du noyau et à éventuellement discuter une intégration au noyau officiel. Cette méthode
induit une réduction des transferts mémoires et du nombre d’opérations, elle pourrait donc être
étudiée sur le plan énergétique afin d’évaluer les gains éventuels sur ce plan. Il ne faut toutefois
pas oublier que le problème fondamental d’extensibilité de l’algorithme de gestion de la table
des pages demeure et nécessitera d’être surveillé et probablement corrigé. Toujours vis-à-vis de
l’extensibilité, nous avons vu que les mécanismes KSM du noyau pouvaient très certainement bé-
néficier d’améliorations, voir, d’extensions de la sémantique, pour profiter des informations dont
dispose le programmeur en lui permettant d’établir lui même des segments en copie sur écriture.
Cette thèse s’est focalisée sur les aspects logiciels. Nous pouvons toutefois proposer d’éven-
tuelles idées à étudier au niveau matériel. Sur ce plan, nous ponvons proposer les trois pistes
suivantes. En cas de généralisation de l’emploi des grosses pages, il peut être intéressant d’éva-
luer l’applicabilité du concept de brassage par masque discuté en section 3.5.2. Ceci permettrait
de ne pas trop corréler les décisions de l’allocateur avec les caches. Dans la même orientation,
on pourrait s’interroger sur les méthodes de remise à zéro de la mémoire, par exemple, en délé-
guant ce travail directement à la RAM. Ceci éviterait l’exécution, par le processeur, de transferts
mémoire couteux et peu productifs. Il pourrait en résulter un gain en terme d’énergie bien qu’il
faille régler les problèmes de cohérences. Enfin nous avons discuté (section 2.5.2) la méthode
d’invalidation des TLB sur l’ensemble des coeurs. L’impact de la méthode actuelle sur architec-
ture x86 mériterais certainement d’être ré-étudiée vis à vis du nombre croissant de coeurs.
Pour terminer, nous avons au cours de cette étude observé de nombreux phénomènes com-
plexes liés à la structure du matériel ou de l’OS. À ce titre, les applications doivent adapter
leur code et surtout leurs méthodes d’accès à la mémoire pour tenir compte de ces problèmes.
Il ne semble toutefois pas raisonnable de prendre explicitement en compte ces trop nombreux
paramètres lors de l’écriture d’un code de calcul. Si une méthode d’organisation des données
est implémentée de manière trop statique et trop contrainte par les algorithmes, il semble dif-
ficile d’imaginer que l’on puisse raisonnablement aboutir à un code optimal. Les choix ont en
effet tendance à être mauvais et ne pourront être corrigés s’ils ne sont pas réversibles. D’autre
part, l’incapacité à tester efficacement d’autres organisations des données nuit aux méthodes
de recherche. Ceci conduit à des comparaisons souvent délicates, voire biaisées, des différentes
approches par le nombre de changements trop importants nécessaires à leur mise en place. À
ce titre, il semblerait intéressant d’obtenir une méthodologie d’abstraction entre organisation
mémoire des données et algorithme. Le cas extrême peut consister à évaluer l’intérêt des DSL
pouvant aider à la séparation des problèmes, au moins en phase de prototypage.
152
Bibliographie
153
son, T. A. Lasinski, H. D. Simon, V. Venkatakri-
shnan, and S. K. Weeratunga. The nas parallel
benchmarks. Technical report, 1991.
[BCD69] A. Bensoussan, C. T. Clingen, and R. C. Daley. The
multics virtual memory. In Proceedings of the se-
cond symposium on Operating systems principles,
SOSP ’69, pages 30–42, New York, NY, USA, 1969.
Bibliographie ACM.
[BCOM+ 10] Francois Broquedis, Jérôme Clet-Ortega, Stépha-
nie Moreaud, Nathalie Furmento, Brice Goglin,
Guillaume Mercier, Samuel Thibault, and Ray-
mond Namyst. hwloc : A Generic Framework
for Managing Hardware Affinities in HPC Applica-
[ABHS89] Melvin C. August, Gerald M. Brost, Christopher C. tions. In Proceedings of the 2010 18th Euromicro
Hsiung, and Alan J. Schiffleger. Cray X-MP : The Conference on Parallel, Distributed and Network-
Birth of a Supercomputer. Computer, 22(1) :45– based Processing, PDP ’10, pages 180–186, Wa-
52, jan 1989. shington, DC, USA, 2010. IEEE Computer Society.
[ABI+ 09] Eduard Ayguadé, Rosa M. Badia, Francisco D. [BCRJ+ 10] Denis Barthou, Andres Charif Rubial, William
Igual, Jesús Labarta, Rafael Mayo, and Enrique S. Jalby, Souad Koliai, and Cédric Valensi. Perfor-
Quintana-Ortí. An Extension of the StarSs Pro- mance Tuning of x86 OpenMP Codes with MA-
gramming Model for Platforms with Multiple QAO. In Matthias S. Müller, Michael M. Resch,
GPUs. In Proceedings of the 15th International Alexander Schulz, and Wolfgang E. Nagel, editors,
Euro-Par Conference on Parallel Processing, Euro- Tools for High Performance Computing 2009, pages
Par ’09, pages 851–862, Berlin, Heidelberg, 2009. 95–113. Springer Berlin Heidelberg, 2010.
Springer-Verlag. [BDH+ 08] Kevin J. Barker, Kei Davis, Adolfy Hoisie, Darren J.
Kerbyson, Mike Lang, Scott Pakin, and Jose C.
[ADM11] Yehuda Afek, Dave Dice, and Adam Morrison.
Sancho. Entering the petaflop era : the architec-
Cache index-aware memory allocation. SIGPLAN
ture and performance of Roadrunner. In Procee-
Not., 46(11) :55–64, June 2011.
dings of the 2008 ACM/IEEE conference on Super-
[AEW09] Andrea Arcangeli, Izik Eidus, and Chris Wright. computing, SC ’08, pages 1 :1–1 :11, Piscataway,
Increasing memory density by using KSM. In OLS NJ, USA, 2008. IEEE Press.
’09 : Proceedings of the Linux Symposium, pages
[Bec03] K. Beck. Test Driven Development : By Example.
19–28, July 2009.
Pearson Education, 2003.
[AHH89] A. Agarwal, J. Hennessy, and M. Horowitz. An
[Ber02] Emery David Berger. Memory management for
analytical cache model. ACM Trans. Comput. Syst.,
high-performance applications. PhD thesis, 2002.
7(2) :184–215, May 1989.
AAI3108460.
[Amd67] Gene M. Amdahl. Validity of the single proces- [BGW93] Amnon Barak, Shai Guday, and Richard G. Whee-
sor approach to achieving large scale computing ler. The MOSIX Distributed Operating System :
capabilities. In Proceedings of the April 18-20, Load Balancing for UNIX. Springer-Verlag New
1967, spring joint computer conference, AFIPS ’67 York, Inc., Secaucus, NJ, USA, 1993.
(Spring), pages 483–485, New York, NY, USA,
1967. ACM. [Bha13] Srivatsa S. Bhat. mm : Memory Power Manage-
ment, 2013.
[AN09] Cédric Augonnet and Raymond Namyst. Euro-
Par 2008 Workshops - Parallel Processing. chap- [BKW98] Satyendra Bahadur, Viswanathan Kalyanakrish-
ter A Unified Runtime System for Heteroge- nan, and James Westall. An empirical study of
neous Multi-core Architectures, pages 174–183. the effects of careful page placement in Linux. In
Springer-Verlag, Berlin, Heidelberg, 2009. ACM 36th Southeast Conference, 1998.
[BLRC94] Brian N. Bershad, Dennis Lee, Theodore H. Ro-
[Arc10] Andrea Arcangeli. Transparent Hugepage Sup-
mer, and J. Bradley Chen. Avoiding conflict misses
port, KVM Forum, 2010.
dynamically in large direct-mapped caches. SIG-
[ASBC09] M. Awasthi, K. Sudan, R. Balasubramonian, and PLAN Not., 29(11) :158–170, November 1994.
J. Carter. Dynamic hardware-assisted software-
[BMBW00] Emery D. Berger, Kathryn S. McKinley, Robert D.
controlled page placement to manage capacity
Blumofe, and Paul R. Wilson. Hoard : a scalable
allocation and sharing within large caches. In
memory allocator for multithreaded applications.
HPCA, 2009.
SIGPLAN Not., 35 :117–128, November 2000.
[BA01] Jeff Bonwick and Jonathan Adams. Magazines
[BMG06] Darius Buntinas, Guillaume Mercier, and William
and Vmem : Extending the Slab Allocator to Many
Gropp. Design and Evaluation of Nemesis : a Sca-
CPUs and Arbitrary Resources. In Proceedings of
lable, Low-Latency, Message-Passing Communica-
the General Track : 2002 USENIX Annual Techni-
tion Subsystem. In Proceedings of the Sixth IEEE In-
cal Conference, pages 15–33, Berkeley, CA, USA,
ternational Symposium on Cluster Computing and
2001. USENIX Association.
the Grid, pages 521–530, Singapour, Singapour,
[BAM+ 96] Edouard Bugnion, Jennifer M. Anderson, Todd C. 2006.
Mowry, Mendel Rosenblum, and Monica S. Lam. [BMG07] Darius Buntinas, Guillaume Mercier, and William
Compiler-directed page coloring for multiproces- Gropp. Implementation and evaluation of
sors. SIGOPS Oper. Syst. Rev., 30(5) :244–255, shared-memory communication and synchroni-
September 1996. zation operations in MPICH2 using the Neme-
[BB99] Mark Baker and Rajkumar Buyya. Cluster compu- sis communication subsystem. Parallel Comput.,
ting : the commodity supercomputer. Softw. Pract. 33(9) :634–644, September 2007.
Exper., 29(6) :551–576, May 1999. [BOP03] Katherine Barabash, Yoav Ossia, and Erez Petrank.
[BBB+ 91] D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Brow- Mostly concurrent garbage collection revisited.
ning, R. L. Carter, R. A. Fatoohi, P. O. Frederick- SIGPLAN Not., 38(11) :255–268, October 2003.
155
BIBLIOGRAPHIE
[BP05] Daniel P. Bovet and Marco Cesati Ph. Understan- [DEJ+ 10] Frédéric Duboc, Cédric Enaux, Stéphane Jaouen,
ding the Linux Kernel, Third Edition. O’Reilly Me- Hervé Jourdren, and Marc Wolff. High-order
dia, 3 edition, November 2005. Paperback. dimensionally split Lagrange-remap schemes for
[BSL+ 02] Rajeshwari Banakar, Stefan Steinke, Bo-Sik Lee, compressible hydrodynamics. Comptes Rendus
M. Balakrishnan, and Peter Marwedel. Scratch- Mathematique, 348(1–2) :105 – 110, 2010.
pad memory : design alternative for cache on-chip [Den70] Peter J. Denning. Virtual Memory. ACM Comput.
memory in embedded systems. In Proceedings of Surv., 2(3) :153–189, September 1970.
the tenth international symposium on Hardware/- [DG02] Dave Dice and Alex Garthwaite. Mostly lock-free
software codesign, CODES ’02, pages 73–78, New malloc. In Proceedings of the 3rd international
York, NY, USA, 2002. ACM. symposium on Memory management, ISMM ’02,
[Buc07] Ian Buck. GPU Computing : Programming a Mas- pages 163–174, New York, NY, USA, 2002. ACM.
sively Parallel Processor. In Proceedings of the
[DGR+ 74] R. H. Denard, F. H. Gaensslen, V. L. Rideout,
International Symposium on Code Generation and
E. Bassous, and A. R. Leblanc. Design of ion-
Optimization, CGO ’07, pages 17–, Washington,
implanted MOSFETs with very small physical di-
DC, USA, 2007. IEEE Computer Society.
mensions. IEEE Journal of Solid-state Circuits, 98,
[BZ93] David A. Barrett and Benjamin G. Zorn. Using li- 1974.
fetime predictors to improve memory allocation
[DL95] E.R. Dougherty and P.A. Laplante. Introduction
performance. In Proceedings of the ACM SIG-
to Real-Time Imaging. IEEE Press Understanding
PLAN 1993 conference on Programming language
Science & Technology Series. Wiley, 1995.
design and implementation, PLDI ’93, pages 187–
196, New York, NY, USA, 1993. ACM. [Don88] Jack Dongarra. The LINPACK Benchmark : An
[CCD+ 05] F. Cappello, E. Caron, M. Dayde, F. Desprez, Explanation. In Proceedings of the 1st Interna-
Y. Jegou, P. Primet, E. Jeannot, S. Lanteri, J. Le- tional Conference on Supercomputing, pages 456–
duc, N. Melab, G. Mornet, R. Namyst, B. Quetier, 474, London, UK, UK, 1988. Springer-Verlag.
and O. Richard. Grid’5000 : A Large Scale and [DP00] David Detlefs and Tony Printezis. A Generational
Highly Reconfigurable Grid Experimental Testbed. Mostly-concurrent Garbage Collector. Technical
In Proceedings of the 6th IEEE/ACM International report, Mountain View, CA, USA, 2000.
Workshop on Grid Computing, GRID ’05, pages 99– [Dre07] Ulrich Drepper. What Every Programmer Should
106, Washington, DC, USA, 2005. IEEE Computer Know About Memory, 2007.
Society.
[DSR12] Robert Dobbelin, Thorsten Schutt, and Alexander
[CD97] Michel Cekleov and Michel Dubois. Virtual- Reinefeld. An Analysis of SMP Memory Alloca-
Address Caches Part 1 : Problems and Solutions tors : MapReduce on Large Shared-Memory Sys-
in Uniprocessors. IEEE Micro, 17(5) :64–71, Sep- tems. In Proceedings of the 2012 41st Internatio-
tember 1997. nal Conference on Parallel Processing Workshops,
[CHL99] Trishul M. Chilimbi, Mark D. Hill, and James R. ICPPW ’12, pages 48–54, Washington, DC, USA,
Larus. Cache-conscious structure layout. In Pro- 2012. IEEE Computer Society.
ceedings of the ACM SIGPLAN 1999 conference [dV] Guillaume Colin de Verdière. Hydrobench,
on Programming language design and implemen- https ://[Link]/HydroBench.
tation, PLDI ’99, pages 1–12, New York, NY, USA,
1999. ACM. [EBSA+ 12] Hadi Esmaeilzadeh, Emily Blem, Renée St. Amant,
Karthikeyan Sankaralingam, and Doug Burger.
[CKZ12] Austin T. Clements, M. Frans Kaashoek, and Ni-
Power Limitations and Dark Silicon Challenge the
ckolai Zeldovich. Scalable address spaces using
Future of Multicore. ACM Trans. Comput. Syst.,
RCU balanced trees. In Proceedings of the se-
30(3) :11 :1–11 :27, August 2012.
venteenth international conference on Architectu-
ral Support for Programming Languages and Ope- [EK93] Rüdiger Esser and Renate Knecht. Intel Paragon
rating Systems, ASPLOS XVII (2012), pages 199– XP/S - Architecture and Software Enviroment. In
210, New York, NY, USA, 2012. ACM. Anwendungen, Architekturen, Trends, Seminar, Su-
percomputer ’93, pages 121–141, London, UK,
[CLT] W. Jalby C. Lemuet and S. Touati. Improving
UK, 1993. Springer-Verlag.
Load/Store Queues Usage in Scientific Compu-
ting. In Proceedings ICPP 2004. [EKTB99] Michael Eberl, Wolfgang Karl, Carsten Trinitis,
[CPJ10] Patrick Carribault, Marc Pérache, and Hervé Jour- and Andreas Blaszczyk. Parallel Computing on
dren. Enabling low-overhead hybrid MPI/O- PC Clusters - An Alternative to Supercomputers
penMP parallelism with MPC. In Proceedings of the for Industrial Applications. In Proceedings of the
6th international conference on Beyond Loop Level 6th European PVM/MPI Users’ Group Meeting on
Parallelism in OpenMP : accelerators, Tasking and Recent Advances in Parallel Virtual Machine and
more, IWOMP’10, pages 1–14, Berlin, Heidelberg, Message Passing Interface, pages 493–498, Lon-
2010. Springer-Verlag. don, UK, UK, 1999. Springer-Verlag.
[CWHW03] Matthew Chapman, Ian Wienand, Gernot Heiser, [Eva06] Jason Evans. A Scalable Concurrent malloc(3) Im-
and New South Wales. Itanium Page Tables and plementation for FreeBSD, 2006.
TLB, 2003. [FK99] Ian Foster and Carl Kesselman, editors. The grid :
[DBa11] Jack Dongarra, Pete Beckman, and al. The Inter- blueprint for a new computing infrastructure. Mor-
national Exascale Software Project roadmap. Int. gan Kaufmann Publishers Inc., San Francisco, CA,
J. High Perform. Comput. Appl., 25(1) :3–60, Fe- USA, 1999.
bruary 2011. [Fly66] M. Flynn. Very high-speed computing systems.
[DCK07] Robert H. Dennard, Jin Cai, and Arvind Kumar. Proceedings of the IEEE, 54(12) :1901–1909,
A perspective on today’s scaling challenges and 1966.
possible future directions. Solid-State Electronics, [FM90] Marc Feeley and James S. Miller. A parallel virtual
51(4) :518 – 525, 2007. machine for efficient scheme compilation. In Pro-
[DD68] Robert C. Daley and Jack B. Dennis. Virtual me- ceedings of the 1990 ACM conference on LISP and
mory, processes, and sharing in MULTICS. Com- functional programming, LFP ’90, pages 119–130,
mun. ACM, 11(5) :306–312, May 1968. New York, NY, USA, 1990. ACM.
156
BIBLIOGRAPHIE
[FYA+ 97] Hiroaki Fujii, Yoshiko Yasuda, Hideya Akashi, Ya- [Jou05] Hervé Jourdren. HERA : A Hydrodynamic AMR
suhiro Inagami, Makoto Koga, Osamu Ishihara, Platform for Multi-Physics Simulations. In Tomasz
Masamori Kashiyama, Hideo Wada, and Tsutomu Plewa, Timur Linde, and V. Gregory Weirs, edi-
Sumimoto. Architecture and Performance of the tors, Adaptive Mesh Refinement - Theory and Ap-
Hitachi SR2201 Massively Parallel Processor Sys- plications, volume 41 of Lecture Notes in Compu-
tem. In Proceedings of the 11th International tational Science and Engineering, pages 283–294.
Symposium on Parallel Processing, IPPS ’97, pages Springer Berlin Heidelberg, 2005.
233–241, Washington, DC, USA, 1997. IEEE Com- [JW98] Mark S. Johnstone and Paul R. Wilson. The me-
puter Society. mory fragmentation problem : solved ? In Procee-
[GCO65] E. L. Glaser, J. F. Couleur, and G. A. Oliver. Sys- dings of the 1st international symposium on Me-
tem design of a computer for time sharing ap- mory management, ISMM ’98, pages 26–36, New
plications. In Proceedings of the November 30– York, NY, USA, 1998. ACM.
December 1, 1965, fall joint computer conference,
[JYV12] Albert Cohen Jean-Yves Vet, Patrick Carribault.
part I, AFIPS ’65 (Fall, part I), pages 197–202,
Multigrain Affinity for Heterogeneous Work Stea-
New York, NY, USA, 1965. ACM.
ling, 2012.
[GFLMR13] Thierry Gautier, Joao Vicente Ferreira Lima, Nico-
[Kam] Patryk Kaminski. NUMA aware heap memory ma-
las Maillard, and Bruno Raffin. XKaapi : A Run-
nager (AMD).
time System for Data-Flow Task Programming on
Heterogeneous Architectures. In 27th IEEE Inter- [KELS62] T. Kilburn, D. B G Edwards, M. J. Lanigan,
national Parallel & Distributed Processing Sympo- and F. H. Sumner. One-Level Storage System.
sium (IPDPS), Boston, Massachusetts, États-Unis, Electronic Computers, IRE Transactions on, EC-
May 2013. 11(2) :223–235, 1962.
[GH12] Mel Gorman and Patrick Healy. Performance cha- [KH92] R. E. Kessler and Mark D. Hill. Page placement
racteristics of explicit superpage support. In Pro- algorithms for large real-indexed caches. ACM
ceedings of the 2010 international conference on Trans. Comput. Syst., volume 10 :338–359, No-
Computer Architecture, ISCA’10, pages 293–310, vember 1992.
Berlin, Heidelberg, 2012. Springer-Verlag. [Kje10] Henrik Kjellberg. Partial Array Self-refresh in Li-
[Glo] Wolffram Gloger. PTMalloc : [Link] nux, 2010.
[Link]/en/. [KK06] Simon Kahan and Petr Konecny. "MAMA !" : a me-
[Gor04] Mel Gorman. Understanding the Linux Virtual Me- mory allocator for multithreaded architectures. In
mory Manager. Prentice Hall PTR, Upper Saddle Proceedings of the eleventh ACM SIGPLAN sympo-
River, NJ, USA, 2004. sium on Principles and practice of parallel program-
[Hab08] Irfan Habib. Virtualization with KVM. Linux J., ming, PPoPP ’06, pages 178–186, New York, NY,
2008(166), February 2008. USA, 2006. ACM.
[Han73] Per Brinch Hansen. Operating system principles. [Kle05] Andi Kleen. A NUMA API for LINUX. Technical
Prentice-Hall, Inc., Upper Saddle River, NJ, USA, report, April 2005.
1973. [KLS86] Nancy P. Kronenberg, Henry M. Levy, and
[HBHR11] Jorg Herter, Peter Backes, Florian Haupenthal, William D. Strecker. VAXcluster : a closely-
and Jan Reineke. CAMA : A Predictable Cache- coupled distributed system. ACM Trans. Comput.
Aware Memory Allocator. In Proceedings of the Syst., 4(2) :130–146, May 1986.
2011 23rd Euromicro Conference on Real-Time Sys- [Kno65] Kenneth C. Knowlton. A fast storage allocator.
tems, ECRTS ’11, pages 23–32, Washington, DC, Commun. ACM, 8(10) :623–624, October 1965.
USA, 2011. IEEE Computer Society.
[KNTW93] Yousef A. Khalidi, Michael N. Nelson, Madhusud-
[Hen06] John L. Henning. SPEC CPU2006 benchmark
han Talluri, and Dock Williams. Virtual Memory
descriptions. SIGARCH Comput. Archit. News,
Support for Multiple Pages. Technical report,
34(4) :1–17, September 2006.
Mountain View, CA, USA, 1993.
[HK] Michal Hocko and Tomas Kalibera. Reducing per-
[Kop] Alexey Kopytov. SysBench : a system performance
formance non-determinism via cache-aware page
benchmark.
allocation strategies. In Proceedings of WOSP/SI-
PEW 2010, pages 223–234. [KPH61] T. Kilburn, R. B. Payne, and D. J. Howarth. The
[HLC09] Kim Hazelwood, Greg Lueck, and Robert Cohn. Atlas supervisor. In Proceedings of the December
Scalable Support for Multithreaded Applications 12-14, 1961, eastern joint computer conference :
on Dynamic Binary Instrumentation Systems. In computers - key to total systems control, AFIPS ’61
Proceedings of the 2009 International Symposium (Eastern), pages 279–294, New York, NY, USA,
on Memory Management, ISMM ’09, pages 20–29, 1961. ACM.
New York, NY, USA, 2009. ACM. [KPKZ11] Mahmut Kandemir, Ramya Prabhakar, Mustafa
[HP06] John L. Hennessy and David A. Patterson. Com- Karakoy, and Yuanrui Zhang. Multilayer cache
puter Architecture, Fourth Edition : A Quantitative partitioning for multiprogram workloads. Euro-
Approach. Morgan Kaufmann Publishers Inc., San Par’11, 2011.
Francisco, CA, USA, 2006. [LBF92] William L. Lynch, Brian K. Bray, and M. J. Flynn.
[Int10a] Intel Corporation. Intel
R 64 and IA-32 Architec- The effect of page allocation on caches. In Procee-
tures Software Developer’s Manual Volume 3A : Sys- dings of the 25th annual international symposium
tem Programming Guide, part 1, June 2010. on Microarchitecture, MICRO 25, pages 222–225,
Los Alamitos, CA, USA, 1992. IEEE Computer So-
[Int10b] Intel Corporation. Intel
R 64 and IA-32 Architec-
ciety Press.
tures Software Developer’s Manual Volume 3B : Sys-
tem Programming Guide, Part 2, June 2010. [Lea] Doug Lea. A Memory Allocator.
[JJF+ 99] H. Jin, H. Jin, M. Frumkin, M. Frumkin, J. Yan, [LLC10] Books LLC. Free Memory Management Soft-
and J. Yan. The OpenMP Implementation of NAS ware : Valgrind, Memcached, Mtrace, Leb128,
Parallel Benchmarks and its Performance. Techni- Splint, Duma, Electric Fence, Memory Pool System,
cal report, 1999. Mpatrol, Memwatch. Books Nippan, 2010.
157
BIBLIOGRAPHIE
[Lor72] H. Lorin. Parallelism in Hardware and Software : [PJN08] Marc Pérache, Hervé Jourdren, and Raymond Na-
Real and Apparent Concurrency. Prentice-Hall Se- myst. MPC : A Unified Parallel Runtime for Clus-
ries in Automatic Computation. Pearson Educa- ters of NUMA Machines. In Proceedings of the 14th
tion, Limited, 1972. international Euro-Par conference on Parallel Pro-
[LPMZ11] Song Liu, Karthik Pattabiraman, Thomas Mos- cessing, Euro-Par ’08, pages 78–88, Berlin, Heidel-
cibroda, and Benjamin G. Zorn. Flikker : sa- berg, 2008. Springer-Verlag.
ving DRAM refresh-power through critical data [PN77] James L. Peterson and Theodore A. Norman.
partitioning. SIGARCH Comput. Archit. News, Buddy systems. Commun. ACM, 20(6) :421–431,
39(1) :213–224, March 2011. June 1977.
[LRW91] Monica D. Lam, Edward E. Rothberg, and Mi- [PTH11] Swann Perarnau, Marc Tchiboukdjian, and
chael E. Wolf. The cache performance and opti- Guillaume Huard. Controlling cache utilization
mizations of blocked algorithms. SIGPLAN Not., of HPC applications. In Proceedings of the inter-
26(4) :63–74, April 1991. national conference on Supercomputing, ICS ’11,
pages 295–304, New York, NY, USA, 2011. ACM.
[McC60] John McCarthy. Recursive functions of symbolic
expressions and their computation by machine, [RB03] J. Howker R. Bryant. Linux scalability for large
Part I. Commun. ACM, 3(4) :184–195, April 1960. NUMA systems, 2003.
[McG65] W. C. McGee. On dynamic program relocation. [RF92] B. Ramakrishna Rau and Joseph A. Fisher.
IBM Syst. J., 4(3) :184–199, September 1965. Instruction-Level Parallel Processing : History,
Overview and Perspective, 1992.
[MDHS09] Todd Mytkowicz, Amer Diwan, Matthias Haus-
[Riz97] Luigi Rizzo. A very fast algorithm for RAM com-
wirth, and Peter F. Sweeney. Producing wrong
pression. SIGOPS Oper. Syst. Rev., 31(2) :36–45,
data without doing anything obviously wrong !
April 1997.
ASPLOS, 2009.
[RLBC94] Theodore Romer, Dennis Lee, Brian N. Bershad,
[MH] Rahul Manghwani and Tao He. Scalable Memory and J. Bradley Chen. Dynamic Page Mapping Po-
Allocation. licies for Cache Conflict Resolution on Standard
[MM06] Jim Mauro and Richard McDougall. Solaris In- Hardware. In In 1st USENIX Symposium on Ope-
ternals (2nd Edition). Prentice Hall PTR, Upper rating Systems Design and Implementation (OSDI,
Saddle River, NJ, USA, 2006. pages 255–266, 1994.
[Moo65] G. E. Moore. Cramming More Components onto [RM09] G. Ruetsch and P. Micikevicius. Optimizing matrix
Integrated Circuits. Electronics, 38(8) :114–117, transpose in cuda, 2009.
April 1965. [Rob04] L. Robertson. Anecdotes. Annals of the History of
[Moo75] Gordon E. Moore. Progress in digital integrated Computing, IEEE, 26(4) :71–73, 2004.
electronics. In Electron Devices Meeting, 1975 In- [Rob12] Les Robertson. Computing Services for LHC :
ternational, volume 21, pages 11–13, 1975. From Clusters to Grids. In René Brun, Federico
[MPI94] Forum MPI. MPI : A Message-Passing Interface. Carminati, and Giuliana Galli Carminati, editors,
Technical report, 1994. From the Web to the Grid and Beyond, The Fron-
tiers Collection, pages 69–89. Springer Berlin Hei-
[MS98] PAUL E. MCKENNEY and JOHN D. SLINGWINE. delberg, 2012.
READ-COPY UPDATE : USING EXECUTION HIS-
TORY TO SOLVE CONCURRENCY PROBLEMS. In [RS09] Mark Russinovich and David A. Solomon. Win-
Parallel and Distributed Computing Systems, 1998. dows Internals : Including Windows Server 2008
and Windows Vista, Fifth Edition. Microsoft Press,
[NIDC02] Juan Navarro, Sitaram Iyer, Peter Druschel, and 5th edition, 2009.
Alan Cox. Practical, transparent operating system
[Rus78] Richard M. Russell. The Cray-1 Computer System.
support for superpages. In Proceedings of the 5th
Communications of the ACM, 21(1) :63–72, 1978.
symposium on Operating systems design and im-
http ://[Link]/article/1010112982782683.
plementation, OSDI ’02, pages 89–104, New York,
NY, USA, 2002. ACM. [SCE99] Timothy Sherwood, Brad Calder, and Joel Emer.
Reducing cache misses using hardware and soft-
[NMM+ 07] Aroon Nataraj, Alan Morris, Allen D. Malony, Mat- ware page placement. In Proceedings of the 13th
thew Sottile, and Pete Beckman. The ghost in the international conference on Supercomputing, ICS
machine : observing the effects of kernel opera- ’99, pages 155–164, New York, NY, USA, 1999.
tion on parallel application performance. In Pro- ACM.
ceedings of the 2007 ACM/IEEE conference on Su-
percomputing, SC ’07, pages 29 :1–29 :12, New [SG] Paul Menage Sanjay Ghemawat. TCMalloc :
York, NY, USA, 2007. ACM. Thread-Caching Malloc,
[Link]
[NS07] Nicholas Nethercote and Julian Seward. Val-
grind : a framework for heavyweight dynamic bi- [SGS10] John E. Stone, David Gohara, and Guochun Shi.
nary instrumentation. SIGPLAN Not., 42(6) :89– OpenCL : A Parallel Programming Standard for
100, June 2007. Heterogeneous Computing Systems. IEEE Des.
Test, 12(3) :66–73, May 2010.
[Ope] OpenPA : Open Portable Atomics.
[SHcF06] Sushant Sharma, Chung-Hsing Hsu, and Wu chun
[PCJ09] Marc Pérache, Patrick Carribault, and Hervé Jour- Feng. Making a case for a Green500 list. In
dren. MPC-MPI : An MPI Implementation Redu- IEEE International Parallel and Distributed Proces-
cing the Overall Memory Consumption. In Procee- sing Symposium (IPDPS 2006)/ Workshop on High
dings of the 16th European PVM/MPI Users’ Group Performance - Power Aware Computing, 2006.
Meeting on Recent Advances in Parallel Virtual Ma- [SKR+ 04] Byeong Hag Seong, Donggook Kim, Yangwoo
chine and Message Passing Interface, pages 94– Roh, Kyu Ho Park, and Daeyeon Park. TLB
103, Berlin, Heidelberg, 2009. Springer-Verlag. Update-Hint : A Scalable TLB Consistency Algo-
[Per12] H4H, PERFCLOUD. rithm for Cache-Coherent Non-uniform Memory
http ://[Link]/activites/projetsR_D_H4H_Perfcloud.html,Access Multiprocessors. IEICE Transactions, 87-
2012. D(7) :1682–1692, 2004.
158
BIBLIOGRAPHIE
[SM] Valat S. and Pérache M. Optimisation de l’utili- [VJYA13] Carribault Patrick Vet Jean-Yves and Cohen Al-
sation des caches L2/L3 et meilleure distribution bert. Parallélisme de tâches et localité de don-
des pages : prototypage d’un module noyau Linux. nées dans un contexte multi-modèle de program-
mation pour super-calculateurs hiérarchiques et
[SSC96] L. M. Silva, J. G. Silva, and S. Chapple. Implemen-
hétérogènes, 2013.
ting Distributed Shared Memory on Top of MPI :
The DSMPI Library. In Proceedings of the 4th Euro- [VSW13] Pérache Marc Valat Sébastien and Jalby William.
micro Workshop on Parallel and Distributed Proces- Introducing Kernel-Level Page Reuse for High Per-
sing (PDP ’96), PDP ’96, pages 50–, Washington, formance Computing. MSPC ’13, 2013.
DC, USA, 1996. IEEE Computer Society. [Wal02] Carl A. Waldspurger. Memory resource manage-
[Sun90] V. S. Sunderam. PVM : a framework for parallel ment in VMware ESX server. In Proceedings of the
distributed computing. Concurrency : Pract. Ex- 5th symposium on Operating systems design and
per., 2(4) :315–339, November 1990. implementation, OSDI ’02, pages 181–194, New
York, NY, USA, 2002. ACM.
[SZ98] Matthew L. Seidl and Benjamin G. Zorn. Segre-
[Wie08] Ian Wienand. Transparent Large-Page Support for
gating heap objects by reference behavior and li-
Itanium Linux, 2008.
fetime. In Proceedings of the eighth international
conference on Architectural support for program- [wik] Flynn’s taxonomy.
ming languages and operating systems, ASPLOS [WJNB95] Paul R. Wilson, Mark S. Johnstone, Michael Neely,
VIII, pages 12–23, New York, NY, USA, 1998. and David Boles. Dynamic Storage Allocation :
ACM. A Survey and Critical Review. In Proceedings
[Tan05] Andrew S. Tanenbaum. Structured Computer Or- of the International Workshop on Memory Mana-
ganization (5th Edition). 2005. gement, IWMM ’95, pages 1–116, London, UK,
1995. Springer-Verlag.
[TC12] M. Tolentino and K.W. Cameron. The Optimist, [WM95] Wm. A. Wulf and Sally A. McKee. Hitting the me-
the Pessimist, and the Global Race to Exascale in mory wall : implications of the obvious. SIGARCH
20 Megawatts. Computer, 45(1) :95–97, 2012. Comput. Archit. News, 23(1) :20–24, March 1995.
[TCP12] Marc Tchiboukdjian, Patrick Carribault, and Marc [Wol] Marc Wolff. Analyse mathématique et numérique
Perache. Hierarchical Local Storage : Exploiting du système de la magnétohydrodynamique ré-
Flexible User-Data Sharing Between MPI Tasks. sistive avec termes de champ magnétique auto-
In Proceedings of the 2012 IEEE 26th Internatio- généré.
nal Parallel and Distributed Processing Symposium,
[YBF+ 11] Xi Yang, Stephen M. Blackburn, Daniel Framp-
IPDPS ’12, pages 366–377, Washington, DC, USA,
ton, Jennifer B. Sartor, and Kathryn S. McKinley.
2012. IEEE Computer Society.
Why nothing matters : the impact of zeroing. In
[TH94] Madhusudhan Talluri and Mark D. Hill. Surpas- Proceedings of the 2011 ACM international confe-
sing the TLB performance of superpages with less rence on Object oriented programming systems lan-
operating system support. SIGOPS Oper. Syst. Rev., guages and applications, OOPSLA ’11, pages 307–
28(5) :171–182, November 1994. 324, New York, NY, USA, 2011. ACM.
[Tho80] James E. Thornton. The CDC 6600 Project. [YDLC10] Lei Yang, Robert P. Dick, Haris Lekatsas, and Sri-
2(4) :338–348, October/December 1980. mat Chakradhar. High-performance operating
system controlled online memory compression.
[THW10] Jan Treibig, Georg Hager, and Gerhard Wellein. ACM Trans. Embed. Comput. Syst., 9(4) :30 :1–
LIKWID : A Lightweight Performance-Oriented 30 :28, April 2010.
Tool Suite for x86 Multicore Environments. In
Proceedings of the 2010 39th International Confe- [YIN+ 11] Kazutomo Yoshii, Kamil Iskra, Harish Naik, Pete
rence on Parallel Processing Workshops, ICPPW Beckman, and P. Chris Broekema. Performance
’10, pages 207–216, Washington, DC, USA, 2010. and Scalability Evaluation of ’Big Memory’ on
IEEE Computer Society. Blue Gene Linux. Int. J. High Perform. Comput.
Appl., 25 :148–160, May 2011.
[Top10] Top500. Top 500 Supercomputer Sites.
[ZLHM09] Panyong Zhang, Bo Li, Zhigang Huo, and Dan
http ://[Link]/, 2010.
Meng. Evaluating the Effect of Huge Page on
[VDGR96] Ben Verghese, Scott Devine, Anoop Gupta, and Large Scale Applications. In Proceedings of the
Mendel Rosenblum. Operating system support 2009 IEEE International Conference on Networ-
for improving data locality on CC-NUMA compute king, Architecture, and Storage, NAS ’09, pages
servers. SIGPLAN Not., 31(9) :279–289, Septem- 74–81, Washington, DC, USA, 2009. IEEE Com-
ber 1996. puter Society.
159
BIBLIOGRAPHIE
160
Annexes
161
Annexe A
Cette annexe fournit le détail des architectures tests utilisé pendant cette thèse. Pour ces
travaux, nous rappelons que nous avons essentiellement exploité les nœuds des calculateurs de
classe pétaflopiques Curie et Tera 100. Ces deux calculateurs sont conçus sur la base de nœuds
exploitant respectivement 2 ou 4 processeurs octocœurs Intel. Une fraction de nœuds dits larges
exploitent quant à eux 16 processeurs grâce à la technologie BCS (figure A.1) développée par
Bull et permettant ainsi d’obtenir 128 cœurs en mémoire partagée. Ont également été utilisés
les nœuds d’un petit calculateur d’expérimentation Cassard et une station autonome à base de
processeur Nehalem.
BCS BCS
BCS BCS
F IGURE A.1 – Structure à deux niveaux des nœuds larges 128 cœurs agrégés par la technologie BCS.
163
Chapitre A. Détail structurel des machines tests
Calculateur Curie
Noeuds fin Noeuds large
Performances 1.36 Pflops
Mise en service 2010
Noeuds 5040 90
Processeurs 10080 1440
Coeurs 80640 11520
Processeurs / noeud 2 16
Coeurs / noeud 16 128
Coeurs / CPU 8 8
Mémoire / noeud 64 Go 512 Go
Stokage disque 5 Po
Débit stockage disque 100 Go/s
architecture Intel Sandy Bridge EP Intel Nehalem EX
Processeur Xeon E5-2680 Xeon X7560
Fréquence 2.7 GHz 2.27 GHz
TABLE A.1 – Table d’information détaillée des architectures utilisées lors des tests.
164
Annexe B
Chapitre fournit quelques mesures complémentaires obtenues lors de l’étude des interactions
entre OS, allocateur et caches discutés dans le chapitre 3. Sont essentiellement fourni ici des
résultats obtenus sur un matériel différent : station à base de Core 2 Duo en employant la même
démarche.
OpenSolaris
6 FreeBSD
40
Gain de performance relatif à Linux (%)
20
2
0 0
−2
−20
−4
−40
−6
41
43
43
48 lie M
41
43
43
43
44
44
45
45
45
45
46
46
48
0.
6.
7.
1.
6.
3.
4.
5.
4.
7.
0.
3.
4.
9.
5.
0.
2.
bw
ca
le AD
w d
ga
ze
gr
na
de
so
po
ca
to
lb
sp
rf
s
ct
av
em
m
ilc
nt
om
u
h
m
al
vr
us
cu
sm
le
in
o
3
es
II
es
ay
sF
ac
lix
x
x3
p
s
D
s
TD
Benchmark
F IGURE B.1 – Gains de temps relatifs à Linux pour les benchmarks de SpecFP2006 en mode base-ref.
Plus grand est meilleur.
165
Chapitre B. Complémenté sur l’interférence des mécanismes d’allocations
Ici les résultats sont très inégaux entre les différents benchmarks, [Link] sort du lot
avec un comportement proche de celui obtenu pour le programme MHD étudié en section 3.3.4.
Sous OpenSolaris, les gains et pertes se compensent pour donner en moyenne un gain de 1%,
contre −3.4% sous FreeBSD. En ne tenant pas compte des benchmarks bwaves et bwrf les deux
moyennes deviennent quasi nulles. Certains benchmarks montrent toutefois des écarts allant de
2% à 10%.
B.2 Linpack
Des tests ont été réalisés sur le Linpack en faisant varier les paramètres N (taille du pro-
blème) et Bs (la taille des blocs). Les valeurs utilisées sont données dans le tableau B.1.
TABLE B.1 – Valeurs de certains des paramètres utilisés pour configurer le Linpack. Toutes les com-
binaisons ont été testées.
La figure B.2 donne les gains obtenus en comparant les performances maximums obtenues
sur chaque OS pour les différentes tailles de problèmes. On y remarque des gains presque systé-
matiques de 0.5% à 2% sous FreeBSD et OpenSolaris.
1
0.5 0.5
0
0
−0.5
−1 −0.5
−1.5
−1
−2
−2.5 −1.5
1000 2000 3000 6000 10240 17920 19328 1000 2000 3000 6000 10240 17920 19328
Taille de problème Taille de problème
F IGURE B.2 – Gains de performances relatifs à Linux en gardant la taille de bloc (Bs) donnant la
meilleure performance sous Linux pour chaque taille de problème (N) ; voir table B.2. Plus grand
est meilleur.
TABLE B.2 – Tailles de bloc (Bs) retenues pour avoir donné les meilleures performances sous Linux,
pour chaque taille de problème (N). À part pour N=3000 avec 2 processus, le maximum est atteint
avec le même Bs sur tous les systèmes testés.
Les écarts étant relativement faibles, de multiples exécutions ont été réalisées pour chacune
des tailles en choisissant le paramètre Bs ayant donné la meilleure performance sous Linux
(table B.2). On obtient ainsi pour chaque taille une distribution des performances qui nous
166
B.2. Linpack
informe sur la stabilité de la mesure. La figure B.3 donne quelques exemples de distributions
obtenues. Les gains moyens obtenus par cette méthode sont résumés dans la figure B.4.
Nombre d’occurences
120
80
100
80 60
60
40
40
20
20
0 0
4.3 4.35 4.4 4.45 4.5 4.55 4.6 6 6.2 6.4 6.6 6.8 7
GFlops GFlops
8 Nombre d’occurences 14
12
6 10
8
4
6
4
2
2
0 0
5.5 5.51 5.52 5.53 5.54 5.55 5.56 5.57 10.22 10.24 10.26 10.28 10.3 10.32 10.34 10.36 10.38
GFlops GFlops
F IGURE B.3 – Distribution des mesures de performances pour les problèmes de tailles 2000 et 17920.
Attention, les échelles ne commencent pas à 0.
1.5 1
1 0.5
0.5 0
0 −0.5
−0.5 −1
1000 2000 3000 6000 10240 17920 19328 1000 2000 3000 17920 19328
Taille de problème Taille de problème
F IGURE B.4 – Gains de performances relatifs à Linux en utilisant les moyennes des distributions
obtenues en figure B.3, toujours pour les couples {N, Bs} listés en table B.2. Plus grand est meilleur.
On confirme donc bien l’observation de gains allant de 0.5% à 2% sous FreeBSD et OpenSo-
laris. Remarquons que ces résultats sont compatibles avec les observations faites par l’étude de
167
Chapitre B. Complémenté sur l’interférence des mécanismes d’allocations
Zang en 2009[ZLHM09].
Linux :
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
Alignements : 16, 16, 16, 16 16, 16, 16, 16
...
OpenSolaris :
Alignements : 16, 0, 48, 32 16, 0, 48, 32
Alignements : 16, 0, 48, 32 16, 0, 48, 32
Alignements : 48, 32, 16, 0 48, 32, 16, 0
Alignements : 16, 0, 48, 32 16, 0, 48, 32
Alignements : 48, 16, 48, 16 48, 16, 48, 16
Alignements : 16, 48, 16, 48 16, 48, 16, 48
Alignements : 16, 48, 16, 48 16, 48, 16, 48
Alignements : 48, 16, 48, 16 48, 16, 48, 16
...
FreeBSD :
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
Alignements : 0, 0, 0, 0 0, 0, 0, 0
...
168
B.4. Résumé des effets d’alignements
TABLE B.3 – Identification des paramètres impliqués dans les problèmes d’alignement mémoire.
TABLE B.4 – Liste des solutions envisageables pour résoudre les différents problèmes listés dans la
table B.5. Les solutions sont détaillées dans la section 3.5.
169
Impacte Nom Alignement OMP OS Pages Condition Solutions Probabilité
Fuite dernier niveau de cache - - Oui 4kB – Utilisation de l’ensemble du dernier cache. color, nrco- Elevé : Linux,
LL lor, huge ou Faible : SunOS
smcache
Oui 4 Ko – SBA aligné relativement à LLSS 16bp, 4kp, nr- Élevé : SunOS,
OpenMP sur coloration régulière LLSS Oui
– N BS > LLASSO color, nrsplit ou Null : Linux
– N BT H <= CP U T H chnbs
Non >= LLSS 16bp, 4kp, nrs- Moyen
plit ou chnbs
Oui 4 Ko 16bp, 4kp, nrco- Élevé : SunOS,
L1 ? ,LL Pagination régulière LLSS, L1SS ? Non – N BS > LLASSO lor ou chnbs Null : Linux
Non >= LLSS – SBA aligné sur LLSS (ou à L1SS ?) 16bp, 4kp ou Moyen
170
chnbs
– Utilisation d’accès de type a[i] = b[i-1].
L1 Conflits Load/Store 4 Ko Non Non ??? 16bp ou chacc Élevé
– Tableaux alignés sur 4 Ko.
– N BS > T LBASSO
– BSA aligné sur T LBSASIZE
TLB, L1 Limite des PDE PDEASIZE Non Non 4 Ko 16bp, 4kp ou Faible
– BSA distants de plus que
chnbs
P DEASIZE/N BS
– BSA aligné sur T LBSASIZE
hline TLB Limit d’associativité du DTLB T LBSASIZE Non Non 4 Ko 16bp, 4kp ou Moyen
– N BS > T LBASSO
chnbs
Chapitre B. Complémenté sur l’interférence des mécanismes d’allocations
TABLE B.5 – Résumé des impacts de performance d’accès induit par les politiques d’allocation.
Annexe C
Dans le cadre du développement de notre allocateur, nous avons eu besoin d’une file ato-
mique ayant des propriétés d’accès synchronisés en considérant les contraintes d’insertion mul-
tiples et de purge par un thread unique. Pour ce faire nous avons repris l’implémentation de
queue atomique fournie par la bibliothèque OpenPA et utilisée pour les échanges de message en
mémoire partagé de Mpich2. Cette structure à toutefois l’inconvénient de considérer la récupé-
ration des éléments un a un. Dans le cadre des libérations distantes de notre allocation, nous
considérons plutôt le cas d’une purge de l’ensemble de la liste en une opération. La liste a donc
été modifiée de sorte que l’opération de récupération renvoie l’ensemble du contenu de la liste.
171
Chapitre C. File atomique pour l’allocateur
172
85 s c t k _ m p s c f _ q u e u e _ w a i t _ u n t i l _ e n d _ i s ( head , tail ) ;
86 }
87
88 /* now we can return */
89 return head ;
90 }
173