Soutenance mémoire
DE nos jours, la majeure partie des systèmes informatiques disposent de plusieurs unités de calcul de mêmes fréquences, qu’il s’agisse de superordinateurs, d’ordinateurs de bureau, d’ordinateurs portables ou de systèmes embarqués. Ces systèmes sont alors dits « à multitraitement symétrique », ou simplement SMP (pour « Symmetric MultiProcessing »). Contrairement à l’augmentation en fréquence des cœurs de calcul, cette évolution des systèmes ne peut se faire de façon transparente pour les applications. En effet, l’utilisation efficace de ces architectures passe par une parallélisation des applications. Pour que cette parallélisation soit efficace, il est nécessaire de bien prendre en compte les spécificités matérielles de ces systèmes. Connaître ces spécificités est également nécessaire pour comprendre certaines répercussions sur les performances des programmes, tel le coût important d’une section critique lorsqu’elle est exécutée sur plusieurs unités de calcul [LDT`].
Il existe cependant plusieurs familles de systèmes SMP, chacune ayant ses propres particularités. Il faut donc connaître les particularités de tous ces systèmes pour obtenir de bonnes performances sur chacun d’eux. Pour simplifier la parallélisation d’applications, cette thèse propose donc deux contributions permettant de paralléliser une application de façon efficace sans nécessiter de connaissances étendues sur les systèmes SMP.
Caches matériels
Les accès à la mémoire font partie des instructions les plus fréquemment utilisées dans tous les programmes. Or, ces instruction d’accès à la mémoire ont un coût élevé en nombre de cycles processeur. Sans précaution particulière, de nombreux cycles seraient perdus à chaque accès à la mémoire, réduisant d’autant l’efficacité globale du système. L’utilisation de caches matériels permet de réduire de manière drastique l’impact des accès à la mémoire. Cependant, l’accès à la mémoire doit suivre certaines contraintes pour obtenir les meilleures performances possibles des caches matériel. Cette section présente l’origine et le fonctionnement des caches matériels, ainsi que les contraintes qui y sont associées.
Idée générale
Dans un ordinateur, la mémoire centrale et le processeur opèrent à des fréquences différentes : le processeur opère à une fréquence significativement plus élevée que celle de la mémoire. De plus, les mémoires centrales de type DRAM qui se trouvent dans les ordinateurs actuels possèdent de nombreuses limitations physiques qui mènent à des cycles mémoire non utilisés pour transmettre des données . En conséquence, une instruction d’accès mémoire nécessite de nombreux cycles processeur pour s’exécuter. Pour atténuer ce problème, des mémoires plus petites que la mémoire centrale mais d’accès plus rapide sont disposées entre elle et le processeur. Ces mémoires sont généralement désignées sous le nom de caches matériels. En dehors des zones mémoire qui servent à communiquer avec les périphériques, toute donnée lu ou écrite en mémoire passe par le cache matériel. Ainsi, lorsqu’une donnée doit être lue en mémoire, celle-ci est d’abord cherchée dans le cache matériel. Si celle-ci n’y est pas présente, le cache matériel lit la donnée depuis la mémoire centrale puis la renvoie au processeur : ce scénario se nomme un défaut de cache. De la même manière, une donnée à écrire est d’abord stockée dans le cache matériel puis celui-ci propage l’écriture en mémoire centrale. L’idée derrière ce dispositif est d’éviter un accès à la mémoire en cas d’utilisation ultérieure d’une donnée.
Le concept de cache matériel repose sur l’hypothèse que l’accès aux données vérifie le principe dit de localité. Deux types de localité existent :
— localité temporelle ;
— localité spatiale.
Localité temporelle
La localité temporelle est le principe selon lequel les données sont souvent accédées plusieurs fois, et cela dans un court laps de temps. En effet, leur utilité dépend entièrement de la probabilité de présence des données dans le cache. Cette probabilité est d’autant plus grande que le temps séparant deux accès à une même donnée est court. Une caractéristique essentielle d’un cache est qu’il a une capacité bien plus petite que la mémoire principale : si la capacité des deux mémoires était du même ordre de grandeur, c’est dans la mémoire la plus rapide d’accès que les données seraient stockées. Une conséquence de la différence de taille est qu’il est possible pour la mémoire principale de contenir plus de données que le cache ne le peut. Une donnée d peut donc être accédée mais le cache être déjà rempli d’autres données. Lorsque cela se produit, une donnée doit être retirée du cache afin de libérer de la place pour stocker la donnée d – on parle alors d’éviction de donnée. Un nouvel accès à la donnée ainsi évincée occasionne alors un défaut de cache : la donnée doit être copiée depuis la mémoire à nouveau. C’est pour cette raison qu’un cache repose sur la brièveté du laps de temps qui sépare les différents accès aux données. Plus le temps entre deux accès à une donnée d est grand, plus le nombre de données différentes qui peuvent être accédé pendant cet intervalle est important. Or si ce nombre est trop grand, la donnée d sera alors évincée et l’accès suivant occasionnera un nouveau défaut de cache. Pour que le cache permette effectivement de réduire le nombre de défaut de cache, il est donc nécessaire que le temps entre les accès successifs aux données soit court.
Localité spatiale
La localité spatiale est le principe selon lequel des données proches l’une de l’autre en mémoire sont accédées dans un intervalle de temps court. Lorsque ce principe est vérifié, il devient avantageux de copier simultanément dans le cache les données contiguës en mémoire. En effet, le coût d’une copie n’est souvent pas linéaire vis à vis du nombre de données copiées, c’est à dire qu’il est souvent plus rapide de copier plusieurs données en une fois que de les copier une par une. C’est le cas notamment de la mémoire de type DRAM utilisée dans les mémoires centrales aujourd’hui. Il est donc intéressant de copier simultanément dans le cache – et donc à moindre coût – les données contiguës en mémoire, sachant qu’il existe une forte probabilité que celles-ci soient accédées par la suite. Ce principe se vérifie également pour d’autres types de cache, tel le cache des pages où un bloc entier est lu depuis le disque lorsqu’une donnée est accédée. Les caches matériels requiert par contre une localité spatiale plus forte pour être efficace, la quantité de données pouvant être transférées ensembles étant plus petite. La localité temporelle et la localité spatiale ont toutes deux leur origine dans les modèles habituels de programmation. La localité temporelle provient ainsi de l’utilisation de boucles dans les langages de programmation. L’exécution d’une boucle amène en effet à accéder en lecture ou écriture des données de façon répétée dans un court laps de temps, rendant les caches matériels utiles. De même, le principe de localité spatiale s’explique par l’existence de structures, d’objets et de tableaux. Ces structures de données ont pour point commun de grouper de façon contiguë en mémoire des données ayant un lien logique entre elles. Ces données sont alors souvent accédées ensemble, notamment au sein de boucles dans le cas des tableaux, créant ainsi la localité spatiale.
Paramètres de performance des caches matériels
Si les principes de localité temporelle et spatiale sont essentiels à l’efficacité des caches matériels, il existe en pratique, de nombreux autres paramètres influençant leur efficacité. De fait, il n’est pas possible d’obtenir de bonnes performances sans en tenir compte. Cette sous-section a donc pour but de décrire chacun de ces paramètres.
Lignes de cache
La propriété de localité spatiale est un des éléments majeur de la performance des caches matériels. Elle permet d’améliorer leurs performances en copiant simultanément des données contiguës en mémoire. Cependant, l’efficacité de ce mécanisme dépend pour beaucoup du placement des données dans la mémoire. En effet, pour des raisons de simplicité d’implémentation, la mémoire centrale ainsi que le cache matériel ne permettent pas de copier n’importe quelle séquence de données mais seulement les séquences dont la première donnée a une adresse multiple d’une puissance de deux donnée. Il n’est donc pas possible de récupérer systématiquement dans le cache une donnée et les n suivantes. La mémoire centrale est virtuellement découpée en segments, appelés lignes de caches, dont la taille correspond à la quantité de données copiées simultanément depuis la mémoire vers un cache matériel. L’expression « ligne de cache » désigne ainsi un ensemble de données et par extension la taille de cet ensemble.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 Contributions
1.3 Plan de la thèse
2 Architectures multi-cœurs
2.1 Caches matériels
2.1.1 Idée générale
2.1.2 Paramètres de performance des caches matériels
2.2 Architectures mémoire des systèmes SMP
2.2.1 Architecture multi-processeurs
2.2.2 Architecture multi-cœurs
2.2.3 Architecture NUMA
2.3 Système de cohérence de la mémoire
2.3.1 Origine des incohérences mémoire
2.3.2 Solutions pour le maintien de la cohérence
2.3.3 Fonctionnement du système de cohérence des caches
2.3.4 Conséquences pour les performances
2.3.5 Impact des protocoles de cohérence mémoire sur les performances
2.4 Conclusion
3 Algorithme de communication inter-cœurs BatchQueue
3.1 État de l’art des algorithmes de communication inter-cœurs
3.1.1 Primitives de communication des systèmes d’exploitation
3.1.2 File sans verrou à accès simultané de Lamport
3.1.3 Solutions optimisées pour les architectures multi-cœurs
3.2 Communication inter-cœurs rapide avec BatchQueue
3.2.1 Principe
3.2.2 Algorithme
3.2.3 Gestion du préchargement
3.3 Mesures de performance des algorithmes de communication
3.3.1 Conditions expérimentales
3.3.2 Ordre de grandeur des algorithmes de communication inter-cœurs
3.3.3 comparaison des algorithmes de communication optimisés pour le multicœurs
3.3.4 Paramètres des algorithmes de communication
3.3.5 Influence du partage de cache
3.4 Conclusion
4 Parallélisme de flux optimisé avec BatchQueue
4.1 Paradigmes de programmation parallèle
4.1.1 Parallélisme de données
4.1.2 Parallélisme de tâche
4.1.3 Parallélisme de flux
4.2 Implémentation
4.2.1 Adaptation à l’interface de communication de l’extension de calcul par
flux pour OpenMP
4.2.2 Interchangeabilité des algorithmes de communication
4.3 Évaluation préliminaire
4.4 Performances appliquées
4.4.1 FMradio : une synchronisation excessive
4.4.2 Décodage par treillis : jusqu’à 200% d’amélioration
4.4.3 Modèle de code : accélération multipliée par 2
5 Conclusion
Télécharger le rapport complet
