Localité des données et Politiques de Placement

Localité des données et Politiques de Placement

Paradigmes architecturaux des plateformes Multic÷urs-UMA/NUMA

Depuis son invention en 1969 et sa première commercialisation en 1971, le microprocesseur a suivi une évolution phénoménale en doublant sa capacité de traitement tous les deux ans comme il a prédit le cofondateur d’Intel Mr G. Moore dans son article de 1965 que le nombre des transistors sur les puces semi-conducteurs va doubler chaque 18 mois. Ce nombre est déterminé par l’évolution de la nesse de gravure dont la diminution permet d’augmenter ce nombre par puce et aussi sa fréquence [Moo+65]. Durant cette évolution, les processeurs ont connu une succession de transformation dans ses versions (single cycle processor, Pipelined , Deep-Pilepline, Superscalar, Out-of Order) [HP17]. 5 Jusqu’au début des années deux mille, Les performances des processeurs construits sur le modèle de von Neumann ont continué d’augmenter de façon exponentielle. Au cours des années, les processeurs sont devenus de plus en plus petits. Cette diminution aecte directement, en termes de fréquence, leurs performances. Ces dernières années, Cette augmentation amorce un fort ralentissement (Table 2.1 donne la tendance de l’augmentation de la puissance par date). Les contraintes qui ont freiné cette évolution sont exprimées par le terme « Patter-son three walls » [Berkeley’s David Patterson succinctly summarized INTEL’s problem in « Patterson’s Three Walls » : Power Wall + Memory Wall + ILP Wall = Brick Wall][Fisveb] qui désigne les barrières (murs) confrontés par les méthodes et les technologies utilisées dans le processus de fabrication des processeurs. Alors elles ont atteint leurs limites. Les trois mur/barrières de Patterson sont : 2.1.1 Puissance La diminution de nesse de gravure a permis de mettre plus de transistors par la même puce qui ont besoin de plus de puissance qui va entrainer une consommation électrique et une dissipation thermique importantes. Ce processus (nesse de gravure) a une limite physique que toute technologie utilisée pour cette opération est incapable d’aller au delà de cette limite. En eet, il se heurt à des phénomènes physiques limitant les performances. La table 2.2 donne la tendance de la nesse de gravure par date depuis 1978 jusqu’à 2015 et les prévisions pour l’année 2021 et 2028 (qui sera la n du processus de la diminution de la taille physique de la grille des transistors à 5nm [Gue16]). Donc, l’augmentation de la fréquence, pour permettre celle des performances, a atteint ses limites. Ces dernières sont proportionnelles au produit du nombre de transistors par la fréquence d’horloge. En eet, un transistor consomme et dissipe à chaque changement d’état. Donc, plus il y a de transistors, plus il y a de consommation électrique et de dissipation thermique. Ce phénomène est amplié par la fréquence d’horloge qui va augmenter la fréquence des changements d’état et donc la consommation et la dissipation. La consommation électrique et la dissipation thermique ont aujourd’hui atteint des seuils critiques avec certains processeurs ayant une consommation de plus de 100W et nécessitant d’imposants systèmes de refroidissement. Donc, Nous ne pouvons plus augmenter la fréquence des processeurs avec la conception actuelle des transistors. La gure 2.1 donne l’évolution des fréquences maximales des processeurs durant ces derniers 40 ans

Caches

Tous les processeurs modernes sont équipés d’une mémoire de petite capacité (allant de quelques Ko à quelques Mo) mais très rapide (0.5-2.5 ns comparé au DRAM 50-70ns ) appelée cache SRAM qui stockent des données (une partie des données de la mémoire) sur 9 lesquelles le processeur travaille temporairement et qui masquent la latence d’accès à la mémoire principale lente. L’emplacement physique de la mémoire cache est très proche des c÷urs an de réduire les coûts de communication. Dans une conguration typique, un CPU comprend plusieurs caches, formant une hiérarchie de cache Les caches peuvent être une autre ressource partagée sur les processeurs. Le cache de premier L1 est local pour chaque c÷ur de petite taille, comprise entre 8 et 128 kilo-octets, mais assez rapide. Le cache du deuxième niveau L2 peut être local pour chaque c÷ur ou partagé entre les c÷urs moins rapide que L1 et mais de taille supérieure, L1 et L2 sont partagés entre les threads matériels. Le cache de troisième niveau L3, cependant, est partagé entre tous les c÷urs du processeur de grande taille mais lent Les caches stockent les blocs de données des niveaux supérieur sous la forme de lignes de cache = bloc : un bloc contigu d’octets. La taille est xe, dépend de l’architecture, typiquement elles sont de 32 octets sur certains processeurs de l’architecture ARM [Lim07], ou 64 octets sur les processeurs x86 de l’architecture Netburst d’Intel Grace à un contrôleur de cache séparé, le contrôle du cache est découplé du processeur et exécuté par ce dernier. Pendant l’exécution du programme, le processeur spécie les adresses mémoire (indépendamment de l’organisation du système de mémoire, sans connaître l’architecture) à lire ou à écrire comme données par les opérations de chargement/stockage. il les transmet à ce système et attend que les valeurs correspondantes soient renvoyées ou écrites. Après avoir reçu une requête d’accès mémoire du processeur, le contrôleur de cache vérie si l’adresse mémoire spéciée correspond à une ligne de cache qui est actuellement stockée dans le cache. Si c’est le cas, une mise en cache cache-hit se produit et la donnée demandée est transmise au processeur à partir du cache. Sinon un cache manqué cache-miss se produit et la ligne de cache est d’abord copiée de la mémoire dans le cache (un bloc de mémoire entier est amené dans le cache, dit un remplacement cache) avant que la donnée demandée ne soit délivrée au processeur. Le temps de retard correspondant est appelé pénalité du cache-miss. Étant donné que le temps d’accès à la mémoire est signicativement plus grand que le temps d’accès au cache, un cache-miss entraîne un retard de remise d’opérande au processeur. Par conséquent, il est souhaitable de réduire autant que possible le nombre des cache-miss. Le temps d’accès d’un cache dépend de sa taille, la taille du bloc-cache et sa méthode d’adressage, Toutefois, l’utilisation d’un cache plus grand entraîne un plus petit nombre de remplacements par rapport un cache plus petit, car davantage de blocs de cache peuvent être conservés dans le cache. L’utilisation de blocs plus grands réduit le nombre de blocs qui s’intègrent dans le cache lors de l’utilisation de la même taille de cache. Par conséquent, les blocs ont tendance à être remplacés plus tôt par rapport aux blocs plus petits. Étant donné que le cache est nettement plus petit que la mémoire principale, tous les blocs de mémoire ne peuvent pas être stockés dans le cache en même temps. Par conséquent, un algorithme d’association doit être utilisé pour dénir la relation entre les blocs cache/mémoire (BC/BM) et détermine comment un bloc stocké est localisé et extrait du cache. Pour l’association, l’accès associatif clé(tag)/valeur(contenu du BM) sera utilisé pour déterminer pour un bloc-mémoire les positions des blocs-cache ou il peut être stocké/sa position dans le cache pour une mise à jour ou une lecture, s’il est déjà 10 chargé dans le cache. [HRR07

Table des matières

1 Introduction 1
1.1 Problématique et motivation
1.2 Objectifs de la thèse .
1.3 Contributions
1.4 Plan et Organisation de la thèse
1.5 Production scienti_que .
2 Paradigmes architecturaux des plateformes Multic÷urs-UMA/NUMA
2.1 Processeurs monoc÷ur .
2.1.1 Puissance
2.1.2 Mémoire
2.1.3 Pipeline ILP( Instruction Level Parallelism)
2.2 Processeurs Multic÷urs (Multicore)
2.2.1 Contrôleur de mémoire intégré .
2.2.2 Hiérarchie de la mémoire [TG13]
2.2.3 Caches
2.2.4 Cohérence de Cache .
2.3 Systèmes SMP/UMA (uniform memory access) .
2.3.1 Mesure de l’accélération (speedup γ)
2.3.2 Passage à l’échelle (scalability ζ)
2.4 Systèmes NUMA Non Uniform memory Access
2.4.1 Architecture NUMA .
2.4.2 Caractéristiques NUMA
2.5 Localité des données et Politiques de Placement
2.5.1 Principe de la localité
2.5.2 Politiques de Placement
2.5.3 Attâchement d’un Thread (Thread Binding)
2.6 Conclusion
3 Graphes de tâches
3.1 Application parallèle décrite par DAG .
3.1.1 Graphe de tâches
3.2 Modèle DAG
3.2.1 Concepts et dé_nitions .
3.2.2 Exécution d’un DAG
3.3 Modèle d’ordonnancement
3.3.1 Modèle Just-in-Time JIT
3.3.2 Horizon d’exécution pour les multicoeurs [Pla15] .
3.3.3 Ordonnancement par liste
3.3.4 Par clustering
3.3.5 Duplication des tâches
3.3.6 Basés les Metaheuristiques
3.4 Conclusion .
4 Etat de l’art de l’ordonnancement et le placement sur MC-NUMA 41
4.1 Caractéristiques des approches .
4.1.1 Caractéristiques principales .
4.1.2 Caractéristiques du placement de données
4.1.3 Caractéristiques des mécanismes d’ordonnancement .
4.2 Ordonnancement des tâches .
4.2.1 Principe de la réutilisation de l’ordonnancement
4.2.2 Ordonnancement du parallélisme non structuré
4.3 Placement des données .
4.3.1 A_nity on touch AoT
4.3.2 CARREFOUR
4.3.3 Interface memory a_nity MAI .
4.3.4 MINAS
4.3.5 Placement de pages orienté feedback FBoPP
4.4 Ordonnancement et placement combinés .
4.4.1 FORESTGOMP
4.4.2 LAWS
4.5 Stratégies d’équilibrage de charge dans NUMA
4.5.1 Partage du travail
4.5.2 Vol de travail (Work stealing) .
4.6 Conclusion
5 Horizon d’exécution étendu et Vol de travail adaptatif 62
5.1 Schémas des stratégies d’ordonnancement et placement
5.2 Ordonnancement et placement des tâches indépendantes .
5.2.1 Combinaison des politiques d’ordonnancement/placement classiques 65
5.2.2 Politiques d’ordonnancement classique
5.2.3 Politiques de placement classique
5.3 Ordonnancement et placement d’un graphe de tâches .
5.3.1 Heuristique Horizon d’exécution Etendu X-VHFU
5.4 Equilibrage de charge
5.4.1 Vol de travail basé sur distance et adaptatif
5.5 Conclusion
6 Simulation et Analyse des résultats
6.1 Simulateur NUMA (HLSMN) .
6.1.1 Etat de l’art des simulateurs Multicoeurs NUMA
6.1.2 Architecture et Conception du simulateur HLSMN
6.2 Expérimentation tâches indépendantes
6.2.1 Con_guration de la simulation
6.2.2 Expérimentation des scénarios .
6.2.3 Analyse des Résultats
6.3 Expérimentation tâches dépendantes DAG
6.3.1 Con_guration de la simulation .
6.3.2 Expérimentation des scénarios
6.3.3 Analyse des Résultats
6.4 Expérimentation Equilibrage de charge
6.4.1 Con_guration de la simulation
6.4.2 Expérimentation des scénarios
6.4.3 Analyse des Résultats
6.5 Conclusion
7 Conclusion et perspectives
7.1 Résultats
7.2 Limites
7.3 Perspectives
References

Télécharger le rapport complet