DSM-PM2 : une plate-forme portable pour l’implémentation de protocoles de cohérence multithreads

Choix de conception

Mis à part le modèle de cohérence, d’autres facteurs déterminent les performances globales des systèmes à mémoire virtuellement partagée. En particulier, il s’agit de la granularité du partage, des stratégies algorithmiques, ainsi que le mode de gestion de la localisation des données. Granularité du partage La granularité de l’unité de partage détermine la taille des blocs de données manipulés par les protocoles de cohérence. Ce paramètre a un effet important sur l’efficacité globale du système. De manière générale, les systèmes à MVP matérielle utilisent une granularité fine fixée (souvent la taille d’une ligne du cache). Les MVP de niveau logiciel utilisent souvent la page comme unité (fixe) du partage, lorsqu’elles reposent sur le système de mémoire virtuelle. Par contre, quand elles sont implémentées au niveau du langage et utilisent un compilateur spécifique, les MVP logicielles proposent une granularité de taille variable dans l’espace mémoire : la taille de l’objet partagé. Lorsque les applications sont caractérisées par une bonne localité spatiale, l’utilisation d’une granularité large permet parfois de réduire le nombre de messages de communication engendrés par les protocoles de cohérence. En effet, lorsque des objets voisins en mémoire, situés par exemple sur la même page, sont accédés séquentiellement par un processeur, un seul transfert de page suffit pour satisfaire plusieurs accès, par un effet de prefetching. D’autre part, plus l’unité est large, plus elle peut contenir des données partagées et donc plus il est probable que cette page soit demandée plus souvent par différents processeurs sur différents nœuds, même s’ils accèdent à des données différentes (faux partage). Les granularités fines réduisent le risque de faux partage, mais nécessitent plus d’espace mémoire pour les structures de données de gestion, car il y a plus d’unités à gérer. Stratégies algorithmiques d’implémentation : réplication et migration Les algorithmes utilisés pour implémenter les MVP abordent essentiellement deux problématiques : (1) l’allocation et la répartition des données partagées de manière à minimiser le coût des accès ; (2) le maintien d’une vue cohérente des données partagées sur chaque processeur qui y  accède, tout en minimisant le surcoût de cette gestion. Deux techniques sont largement utilisées : la réplication et la migration. La réplication est utilisée pour permettre les accès concurrents de plusieurs nœuds à la même donnée, ou à des données différentes situées dans la même unité de partage. La plupart des systèmes appliquent la réplication en lecture (read-replication), lorsque les lectures concurrentes sont prédominantes, mais cette technique peut également être utilisée pour des accès en écriture (protocoles à écrivains multiples). Dans ce dernier cas, des actions complémentaires sont nécessaires pour assurer la cohérence des différentes copies modifiées de manière concurrente. Alternativement, la migration peut être utilisée pour gérer les accès concurrents en écriture, sans faire recours à la réplication : la donnée migre d’un nœud à l’autre et seul le nœud qui la possède couramment a le droit de la modifier. Suivant le type de réplication utilisé, les algorithmes d’implémentation des MVP se classifient en trois catégories. SRSW (single reader, single writer). Ce type d’algorithme interdit toute réplication. Les accès distants se traduisent alors systématiquement soit par des transferts des valeurs entre les nœuds, soit par des migrations des données. Bien que simples, ces algorithmes ont une efficacité généralement limitée, car aucune parallélisation des accès concurrents aux données sur des nœuds différents n’est possible. MRSW (multiple reader, single writer). Utilisé dans beaucoup de MVP, ce type d’algorithme est basé sur la réplication en lecture et permet à plusieurs nœuds d’accéder en parallèle la même donnée par des accès locaux. Parmi les copies répliquées, une seule est modifiable. Lorsqu’un accès en écriture à cette copie est détecté, le protocole de cohérence doit généralement empêcher les autres copies d’être modifiées (stratégie de type invalidation). MRMW (multiple reader, multiple writer). Lorsque les accès concurrents en écriture sont dominants, on peut permettre également leur parallélisation, en autorisant l’existence de plusieurs copies consultables et modifiables sur des nœuds différents (full-replication). Afin de maintenir la cohérence, les modifications effectuées sont diffusées aux autres copies ou à une copie de référence, dans les algorithmes à référence (en anglais : home-based). Contrairement aux algorithmes MRSW basés sur l’invalidation, on applique généralement ici une stratégie de type mise à jour. Gestion de la localisation et des accès aux données Lorsqu’on accède à une donnée partagée, la MVP doit garantir que cette donnée est à jour, conformément au modèle de cohérence implémenté. Dans le cas des protocoles à écrivain unique (algorithme SRSW ou MRSW), ceci repose sur un mécanisme permettant de localiser le nœud qui détient la copie à jour, pour ensuite transférer cette copie en mémoire locale. Li et Hudak [64] ont proposé plusieurs algorithmes MRSW qui implémentent de tels mécanismes. Dans tous ces algorithmes, la copie à jour est toujours détenue par le nœud (unique à tout moment) qui est autorisé à modifier la donnée. Avant de les discuter, nous devons introduire les notions suivantes : propriétaire : le nœud ayant écrit le dernier sur la page ; gestionnaire : le nœud qui connaît le propriétaire d’une donnée et qui est chargé de gérer les accès en écriture à cette donnée ; ensemble des copies : l’ensemble des nœuds qui possèdent des copies d’une donnée partagée répliquée. Le propriétaire d’une donnée partagée peut être fixe ou dynamique. Dans le premier cas, la donnée est toujours possédée par le même nœud, qui est le seul à pouvoir y accéder en écriture. Tous les autres nœuds doivent négocier avec le propriétaire à chaque fois qu’ils ont besoin de modifier la donnée. C’est une approche coûteuse, qui n’est pas utilisée en pratique. Les implémentations existantes reposent sur des approches à propriété dynamique : le propriétaire d’une donnée peut changer durant l’exécution du programme. Les gestionnaires utilisés dans ce cas sont de deux types : centralisés et distribués. Les gestionnaires distribuées peuvent être fixes ou dynamiques

Performance des MVP : progrès récents et évolutions actuelles

L’idée de construire un espace d’adressage virtuel global sur une architecture de machines faiblement couplées à mémoire distribuée a été proposée il y a une quinzaine d’années [62]. Intéressant pour le programmeur, auquel il offre la possibilité de tirer profit de la puissance de calcul des machines distribuées de manière transparente en proposant un modèle de programmation simple, le concept de MVP s’est heurté dès le début au problème de la performance. Le défi de la plupart des efforts de recherche dans le domaine des MVP a été de proposer des mécanismes permettant d’approcher les performances obtenues en utilisant une programmation par passage explicite de messages. L’efficacité des systèmes à MVP est limitée par plusieurs facteurs. L’utilisation d’une granularité de partage supérieure à la taille des données individuelles (généralement une page) engendre des communications inutiles. Ceci est surtout pénalisant dans les protocoles qui implémentent des modèles de cohérence forte, tels que la cohérence séquentielle, basés sur des algorithmes à écrivain unique (SRSW ou MRSW), car seulement une partie des données situées la même page sont utilisées. D’autre part, les accès concurrents de plusieurs nœuds à des données différentes situées sur la même page créent une situation de faux partage qui déclenche des aller-retours coûteux de la page entre les différents nœuds, en augmentant encore plus le trafic des données. Les déclenchements des défauts de pages à l’intérieur des sections critiques représentent une autre source potentielle d’inefficacité, car ils ont pour effet de dilater les sections critiques et de renforcer les sérialisations. Enfin, les MVP de niveau logiciel souffrent en plus des surcoûts liés aux protocoles, dus à l’exécution des actions de cohérence par les processeurs des nœuds qui doivent interrompre l’exécution des applications pour répondre aux différentes requêtes engendrées par les protocoles. Les efforts qui ont contribué à l’amélioration significative des performances des MVP ont été faits dans plusieurs directions. Une avancée importante est due aux modèles de cohérence faible, et tout particulièrement à la cohérence à la libération, introduite au début des années 1990. L’efficacité a été encore améliorée grâce aux protocoles à écrivains multiples (MRMW) qui ont fourni une solution au problème du faux partage. Les stratégies paresseuses ont ensuite permis de réduire encore plus les communications engendrées par les protocoles, à l’aide de mécanismes plus complexes. Un niveau de performance comparable a été par ailleurs obtenu grâce aux protocoles à référence (home-based), plus simples à mettre en œuvre. D’autres contributions ont visé la classification des schémas d’accès aux données et ont produit des systèmes multiprotocoles, dans lequel le programmeur peut associer des protocoles différents à des données différentes, suivant le type d’accès. Certaines MVP proposent même des protocoles adaptatifs, qui changent dynamiquement de stratégie en fonction du comportement de l’application. Enfin, récemment les MVP intègrent les bénéfices du multithreading, essentiellement pour permettre le recouvrement des communications par des calculs. Dans la suite de cette section, nous allons présenter les progrès récents dans ces différentes directions. 36 CHAPITRE 2. PARALLÉLISME À GRAIN FIN ET MVP Stratégies paresseuses Utilisées par beaucoup de protocoles de cohérence faible, les stratégies paresseuses peuvent concerner plusieurs étapes d’un protocole de cohérence : la propagation des opérations de cohérence aux autres nœuds (par des notifications d’écriture, qui précisent quelles données ont été modifiées), l’application de ces actions sur ces nœuds ; ainsi que la propagation des valeurs des données modifiées. Toutes ces opérations peuvent être effectuées de manière immédiate ou paresseuse et le choix d’une stratégie ou d’une autre peut avoir un impact important sur la performances des protocoles. De manière générale, les approches paresseuses permettent de réduire les communications au prix d’une complexité plus importante des mécanismes sous-jacents mis en œuvre. Propagation de la cohérence. L’implémentation la plus simple du modèle de cohérence à la libération consiste à propager les notifications d’écriture à tous les nœuds qui possèdent des copies des pages modifiées, immédiatement après les opérations release. Une fois envoyées, ces informations deviennent obsolètes et peuvent donc être déchargées de la mémoire. Alternativement, ces notifications peuvent être envoyées plus tard, lors d’un prochain acquire, sélectivement au nœud qui effectue cet acquire (propagation paresseuse). Ceci a deux conséquences. D’une part, les informations surles données modifiées ne peuvent plus être déchargées après le release, car elles pourraient être nécessaires lors d’un prochain acquire. D’autre part, le nœud ayant effectué un release doit fournir au nœud qui effectue un acquire toutes les notifications d’écriture que ce nœud n’a pas encore obtenues, dues éventuellement aux écritures des nœuds tiers. Par conséquent, même les notifications “anciennes” prises en compte localement ne peuvent pas être déchargées (jusqu’à une prochaine synchronisation globale), car d’autres nœuds pourraient encore en avoir besoin. La consommation mémoire exigée est par conséquent importante. De plus, un problème particulièrement difficile auxquel se sont heurtées la plupart des implémentations est celui de la détection du moment où ces notifications peuvent être déchargées en toute sécurité. La mise en œuvre de ce type de protocoles paresseux (illustrée dans TreadMarks [4]) repose sur un protocole d’estampillage permettant d’identifier précisément les notifications d’écriture à envoyer dans chaque cas. Prise en compte des informations de cohérence. Même lorsque les notifications d’écriture sont envoyées immédiatement lors d’un release, les nœuds les ayant reçues peuvent les appliquer tout de suite, ou bien les stocker et les appliquer plus tard, lors d’un prochain acquire. Le cohérence à la libération en mode immédiat correspond à une propagation immédiate lors du release, suivie d’une application immédiate. La propagation immédiate associée à une application paresseuse est utilisée par un autre type d’implémentation (delayed consistency [25]). Un protocole MRMW de ce type est utilisé dans Cashmere [99]. Enfin, la cohérence à la libération en mode paresseux correspond traditionnellement à une propagation paresseuse suivie d’une application immédiate. Les deux sont déclenchées par l’opération acquire qui suit un release. Propagation des données modifiées. Comme les notifications d’écriture, les valeurs des données modifiées peuvent à leur tour être transmises de manière immédiate ou paresseuse. En revanche, l’application de ces modifications sur les nœuds les ayant demandées est toujours immédiate. Dans les protocoles à écrivain unique, il existe toujours une seule instance modifiable de chaque unité de partage (page). Dans le modèle de cohérence à la libération, cette instance (toujours à jour) peut coexister temporairement avec d’autres copies en lecture seule, jusqu’au moment ou les nœuds qui possèdent ces copies se synchronisent avec le propriétaire courant de la page. Lors de la synchronisation, les notifications d’écriture peuvent être transmises de manière immédiate ou paresseuse (cf. ci-dessus), et détermine l’invalidation des copies en lecture seule. Lors d’un accès en écriture à une copie invalidée, toute la page migre vers le nœud ayant généré l’accès. Le problème de la propagation paresseuse des données ne se pose donc pas.

Modèles hiérarchiques et cohérence multi-niveaux

L’intérêt récent pour l’utilisation des plates-formes multi-grappes comme support pour le calcul hautes performances à grande échelle a mis en évidence l’importance de certaines problématiques jusqu’ici souvent négligées dans le domaine des systèmes à mémoire virtuellement partagée, telles que la tolérance aux fautes où l’hétérogéneité des architectures. Par ailleurs, les implémentations des modèles de cohérence classiques visent généralement des architectures “plates”, qui supposent que les coûts des communications sont du même ordre pour toute paire de processeurs sous-jacents. Or, cette hypothèse n’est plus valable dans le cadre d’une architecture multi-grappes : les communications intra-grappes sont généralement plus rapides que les communications inter-grappes. La conception de protocoles de cohérence adaptés à ce type d’architecture est l’une des directions de recherche les plus importantes actuellement dans le domaine des MVP [7, 6]. 2.3.6 Un défi : une plate-forme d’expérimentation pour MVP Lorsqu’on considère l’ensemble des efforts de recherche dans le domaine des systèmes à mémoire virtuellement partagée, un constat s’impose : souvent, afin d’expérimenter un nouveau concept (modèle de cohérence, protocole, stratégie algorithmique, etc.), il a fallu construire un système complet. La plupart des composants du système reposent sur des mécanismes classiques, déjà implémentés précédemment, et seulement peu de composants sont conçus spécifiquement pour illustrer le concept proposé (nouveau modèle de cohérence, etc.). Pourtant, la validation expérimentale du concept n’est possible que si le système complet est fonctionnel. Cette situation a deux conséquences immédiates. Tout d’abord, un investissement important en temps et ressources matérielles et humaines est nécessaire lors de la validation de nouvelles techniques, car cette validation nécessite à chaque fois la mise en œuvre d’un ensemble de mécanismes complexes de base, en plus de l’implémentation de la technique que l’on souhaite illustrer. Ceci a pour effet de rendre difficiles et longues les étapes d’implémentation et validation expérimentale. Une deuxième conséquence est que seule une comparaison des systèmes complets visà-vis d’un ensemble d’applications fixées peut être réalisée. Cette comparaison ne peut pourtant mettre directement en évidence les apports d’une technique ou d’une autre que si les mécanismes de base sous-jacents, qui ne font pas l’objet de la comparaison, sont identiques. Ceci n’arrive pourtant pas souvent, car cette condition est difficile à remplir. Une solution possible à ce problème serait la mise en œuvre d’une plate-forme d’expérimentation pour des systèmes à mémoire virtuellement partagée, qui intègre les composants de base (comme le support des communications, le mécanisme de protection des pages, etc.). L’utilisateur peut alors mettre en œuvre des nouveaux modèles ou protocoles de cohérence par une implémentation plus rapide et plus facile, en utilisant les mêmes mécanismes de base (déjà disponibles) et peut ainsi effectuer des comparaisons concluantes. Cette idée a été exploitée dans une certaine mesure par quelques MVP, mais les choix laissés au programmeur sont souvent limités. Le système TreadMarks [4] a servi de cadre d’implémentation pour plusieurs protocoles de cohérence à la libération en mode paresseux et plusieurs études comparatives ont été publiées. Néanmoins, ces études ont été réalisées par des modifications successives du système par ses concepteurs, car la sélection d’un protocole ou d’un autre n’était pas censée faire partie de l’interface de programmation. Munin [19] laisse plus de liberté au programmeur, en lui permettant de sélectionner lui-même les protocoles implicitement, à travers des annotations, mais les protocoles implémentent unique- 40 CHAPITRE 2. PARALLÉLISME À GRAIN FIN ET MVP ment la cohérence à la libération en mode immédiat. Ni Munin, ni TreadMarks ne sont pas conçus pour fournir une plate-forme d’expérimentation à des concepteurs de nouveaux modèles ou protocoles. Seul le projet CVM [52] a mentionné cet objectif, sans pourtant l’atteindre, car le projet a été arrêté avant que la première version stable soit prête. La conception d’une telle plate-forme est donc restée un objectif important non encore atteint. C’est précisément l’objectif de notre travail.