Soutenance mémoire
Architecture d’un ordinateur
Un ordinateur est une machine capable d’exécuter de manière contrôlée une séquence d’instructions traitant des données, le tout stocké dans une mémoire, en interagissant avec son environnement. Il est à minima composé d’une Unité de Contrôle (UC) ou Control Unit (CU) en anglais, d’une Unité Arithmétique et Logique (UAL) ou Arithmetic Logic Unit (ALU) en anglais, d’une mémoire et d’entrées/sorties. On parle d’architecture de von Neumann [1945]. L’UC orchestre le fonctionnement des autres composants de l’ordinateur. L’UAL effectue les traitements indiqués par les instructions sur les données qui lui sont fournies. L’UC et l’UAL forment l’Unité Centrale de Traitement (UCT) ou Central Processing Unit (CPU) en anglais. La mémoire stocke les instructions et les données. Finalement, le périphérique d’entrées/sorties permet à l’ordinateur de communiquer avec son environnement. Si nous regardons de plus près le fonctionnement de l’UCT, l’exécution d’une instruction peut être décomposée en plusieurs étapes. L’instruction est tout d’abord chargée depuis la mémoire, puis décodée pour connaitre le traitement à effectuer et les données concernées. Il faut ensuite charger ces données, les traiter, puis potentiellement écrire le résultat du traitement en mémoire. Ces différentes étapes sont effectuées par différentes parties de l’UCT, celles-ci ne sont donc pas utilisées en permanence mais à tour de rôle. C’est pour améliorer cette utilisation qu’ont été proposées les premières UCT pipelinées. Dans ce type d’architecture, l’UCT n’attend pas que l’exécution d’une instruction soit terminée pour commencer le traitement de la suivante. Une étape de l’exécution d’une instruction peut commencer dés que cette étape est terminée pour l’instruction précédente. Chaque étape d’exécution constitue alors un étage du pipeline du processeur. Cela permet d’augmenter la fréquence d’horloge du processeur, un cycle ne correspond plus au temps de traitement d’une instruction complète mais au temps maximum de traitement d’un étage du pipeline. Le nombre d’étages du pipeline peut varier, allant des 3 étages du premier processeur pipeliné, le Stretch d’IBM [Bloch, 1959], jusqu’aux 31 étages de certains Pentium 4 d’Intel [Jagannathan et al., 2005]. Cependant, les processeurs actuels sont revenus à des pipelines de taille intermédiaire et utilisent majoritairement des pipelines allant de 14 à 20 étages.
Parallélisme d’instruction
Comme nous l’avons vu dans la sous-section 2.2.1, le flot d’exécution d’un processeur peut être découpé en plusieurs étages pour former un pipeline. Or, il existe des contraintes sur les interactions entre les différents étages du pipeline : on parle d’aléas. Il existe trois types d’aléas : structurels, de données et de contrôle. Un aléa structurel correspond à l’utilisation d’un même composant matériel par plusieurs étages du pipeline. L’exemple le plus simple est l’accès simultané par deux étages différents aux instructions et aux données contenues en mémoire. Cet aléa peut être résolu par l’utilisation de deux mémoires caches séparées, une pour les instructions et une pour les données. Un aléa de données correspond à l’utilisation d’une même donnée par plusieurs étages du pipeline. Cet aléa peut-être réglé de plusieurs manières, la manière la plus simple étant de retarder le lancement de la deuxième instruction jusqu’à la fin de la première. Cependant de meilleures solutions existent : il est par exemple possible d’exécuter les instructions dans un ordre différent de celui décidé par le programmeur lors de l’écriture du code. Cela permet d’exécuter effectivement une instruction par cycle en insérant des instructions indépendantes entres deux instructions présentant des dépendances entre elles. On parle alors d’exécution dans le désordre [Tomasulo, 1967]. Finalement, les aléas de contrôle correspondent aux instructions de branchement conditionnelles utilisées pour implémenter les boucles et les tests. Or le choix de l’instruction à exécuter après une instruction de branchement conditionnel dépend directement du résultat de cette dernière. Si le branchement est pris, il ne faut pas exécuter l’instruction se trouvant à l’adresse suivante mais celle qui se trouve à l’adresse spécifiée par le branchement. Ceci implique de devoir soit attendre la fin de l’instruction de branchement pour lancer la suivante, soit de pouvoir annuler l’exécution de l’instruction suivante si le branchement est pris. C’est pour s’affranchir de cette contrainte que les prédicteurs de branchement ont été proposés. Cette solution part du constat que le résultat d’un branchement donné a de fortes chances d’être plusieurs fois de suite le même. Au regard de ces différents aléas, il est possible de séparer le flot d’instructions exécutées par le processeur en deux catégories. D’une part, les instructions pouvant introduire des aléas dans le pipeline : ces instructions doivent être exécutées avec un certain délai d’attente entre chacune et dans un ordre précis. D’autre part, les instructions qui ne présentent pas de dépendances entre elles : ces instructions peuvent donc être lancées dans le pipeline au rythme d’une par cycle, potentiellement dans un ordre différent de celui du code de départ et même en parallèle. L’exécution dans le désordre et la prédiction de branchement permettent de maintenir une utilisation optimale du pipeline. Ils peuvent être couplés à une autre méthode d’amélioration des performances : l’utilisation de plusieurs pipelines en parallèle. On parle alors de processeur superscalaire. Ces trois techniques sont alors complémentaires. D’une part, l’exécution dans le désordre et la prédiction de branchement permettent l’utilisation optimale des pipelines d’un processeur superscalaire. D’autre part, l’utilisation de plusieurs pipelines permet de tirer pleinement partie des deux autres méthodes capables de fournir plus d’une instruction par cycle. Il devient alors possible d’exécuter réellement plusieurs instructions par cycle. On parle alors de parallélisme d’instruction ou Instruction Level Parallelism (ILP).
Classification par domaine applicatif
Il est possible d’évaluer le degré de parallélisme d’une application de deux manières : soit par rapport à son speedup théorique, soit par rapport à son TLP effectif. Dans les deux cas, la valeur est obtenue en supposant un nombre de cœurs/processeurs suffisamment grand pour que ce soit le logiciel qui limite le parallélisme et non le matériel. Le speedup théorique d’une application correspond à la diminution maximale de son temps d’exécution. Le TLP effectif correspond au nombre maximal de tâches d’une même application pouvant s’exécuter simultanément. Applications bureautiques Nous rangeons dans cette catégorie les applications telles que la compression de fichier, la compilation, les suites bureautiques ou les navigateurs internet. D’après Wang et al. [2009], les applications telles que la compression ou la compilation ont un speedup théorique maximal de ×1, 4. De plus, il est possible d’obtenir 80 % de cette valeur théorique maximale avec 2 cœurs. D’après Blake et al. [2010], le TLP effectif des applications telles que les suites bureautiques est de 1,2 alors que celui des navigateurs internet est de 2,0. Dans les deux cas, il ressort donc que les applications de bureautique n’exploitent pas un grand nombre de cœurs et ne semblent même pas en avoir besoin, tel qu’elles sont programmées actuellement. Cependant, même si ces valeurs sont assez basses, ces applications peuvent être plusieurs à s’exécuter en même temps. Applications multimédia Nous rangeons dans cette catégorie les applications de traitement et de compression d’image, de son ou de vidéo ainsi que les jeux vidéo. D’après Wang et al. [2009], le speedup théorique maximal de ce type d’application est de ×3, 3. Il est possible d’atteindre 60 % de ce speedup avec 2 cœurs et 80 % avec 8 cœurs. D’après Blake et al. [2010], le TLP effectif est de l’ordre de 2,9 pour ce type d’application. Tout comme pour les applications bureautiques, les applications de type multimedia peuvent être plusieurs à s’exécuter en même temps sur une machine. Il peut donc y avoir un TLP au niveau application sur la machine auquel il faut ajouter un TLP au niveau thread au sein de chaque application. Applications HPC Pour caractériser les applications de type HPC nous avons retenu les benchmarks tels que SPLASH [Woo et al., 1995] et PARSEC [Bienia et al.,2008]. D’après Woo et al. [1995], le speedup moyen atteignable pour les applications de SPLASH est de ×50 sur une machine à 64 processeurs. La pente de la courbe représentant le speedup en fonction du nombre de processeurs ne change quasiment pas entre 32 et 64 processeurs pour 7 applications sur 12. D’après Bienia et al. [2008], le speedup moyen atteignable pour les applications de PARSEC est de ×14 sur une machine à 16 cœurs. Tout comme pour SPLASH, et même si le nombre de cœurs est moindre, la pente de la courbe représentant le speedup en fonction du nombre de cœurs ne change quasiment pas entre 8 et 16 cœurs pour 9 applications sur 12. Ainsi ces deux benchmark montrent que les applications de type HPC peuvent tirer parti d’architectures à 64 cœurs et laissent à penser qu’il serait possible d’exploiter un encore plus grand nombre de cœurs. De plus, si les benchmark SPLASH et PARSEC ont été développés dans le but d’évaluer les architectures à mémoire partagée cohérente, ce n’est pas le seul modèle de CMP possible. Il est tout à fait possible d’envisager les architectures CMP fonctionnant par passage de messages. De telles architectures pourraient alors exécuter des applications de calculs scientifiques capables de tirer parti de plusieurs milliers de cœurs [Raponi et al., 2011] Analyse Suivant cette classification, il apparait qu’en fonction du domaine considéré, les applications peuvent ou non exploiter un grand nombre de cœurs. Ainsi les applications bureautiques peuvent se contenter de deux cœurs et les applications multimédia de huit cœurs. Cependant, ces applications peuvent être plusieurs à s’exécuter sur une même machine, augmentant ainsi le nombre de cœurs utilisés à quelques dizaines. De plus, le dernier domaine applicatif, le HPC, peut tirer parti de machines ayant une centaine de cœurs ou plus. Il apparait donc que le développement de CMP à plusieurs dizaines ou même centaines de cœurs peut être justifié par l’utilisation effective d’autant de cœurs par les applications exécutées.
Architectures multi-cœurs par conception
Si l’assemblage de processeurs mono-cœurs permet de développer rapidement une puce multi-cœur, le résultat est aussi plus proche d’une solution multi-processeur que d’un réel CMP. Ainsi, dans les puces multi-cœurs conçues comme telles, les communications passent soit par un médium de communication interne, soit par des caches partagés. IBM POWER4 En 2001, le premier processeur multi-cœur est lancé par IBM, le POWER4 [Tendler et al., 2002]. Il possède deux cœurs ayant chacun un cache instruction et un cache donnée. Ces deux cœurs partagent un cache L2 auquel ils sont reliés par un crossbar. Il possède aussi un contrôleur de cache lui permettant d’accéder via un bus à un cache L3 situé en dehors de la puce. La cohérence du POWER est assurée par snooping. SUN UltraSPARC T1 (Niagara) En 2005, SUN lance un processeur à huit cœurs, l’UltraSPARC T1 [Kongetira et al., 2005]. Contrairement à son prédécesseur, l’UltraSPARC IV, le deuxième niveau de cache se trouve ici intégralement sur la puce. Le processeur possède quatre bancs de cache L2 accessibles par tous les cœurs grâce à un crossbar. La gestion de la cohérence est assurée par le cache L2 et repose sur un protocole à base de répertoire. Intel Core En 2006, Intel lance plusieurs processeurs basés sur la microarchitecture Core [Doweck, 2006]. Contrairement au Pentium D, les cœurs situés sur une même puce peuvent maintenant communiquer sans passer par le bus système. Pour ce faire, les différents cœurs du CMP partagent un cache L2 unifié.
L’augmentation du nombre de cœurs
Si les premiers CMP n’étaient constitués que de deux cœurs, ce nombre a augmenté avec les architectures suivantes. De plus, cette augmentation du nombre de cœurs s’est accompagnée d’une augmentation du nombre de niveaux de cache. L’utilisation de plusieurs niveaux de cache permet alors de faciliter les communications entre les cœurs et de partager plus efficacement les données. Intel Haswell En 2013, Intel lance Haswell, la quatrième génération de microarchitecture Core [Hammarlund et al., 2014]. Les processeurs utilisant cette microarchitecture peuvent posséder de 2 à 22 cœurs. Chaque cœur possède maintenant des caches L1 et L2 privés alors que le cache L3 est partagé par tous les cœurs de la puce. Les caches L3 sont reliés entre eux par un anneau permettant aux différents cœurs du CMP de communiquer entre eux. Comme pour les générations précédentes de CMP Intel, la cohérence mémoire fonctionne par snooping. Oracle UltraSPARC T5 En 2013, Oracle lance un processeur à seize cœurs, l’UltraSPARC T5 [Feehrer et al., 2013]. Chaque cœur possède un cache L1 instruction et un cache L1 données ainsi qu’un cache L2. De plus, la puce possède un cache L3 partagé par tous les cœurs. Les communications entre le cache L3 et les cœurs passent par un crossbar. Comme pour l’UltraSPARC, la gestion de la cohérence est assurée par un mécanisme de répertoire mis en place dans les caches L1 et L2. IBM POWER8 Depuis le POWER4, les processeurs IBM ont continué d’évoluer pour arriver à la génération actuelle, le POWER [Starke et al., 2015]. Il possède 12 cœurs ayant chacun un cache L1 pour les instructions et un pour les données ainsi qu’un cache L2. Contrairement au POWER4, le cache L3 est maintenant intégré sur le CMP. De plus, le POWER8 introduit un niveau supplémentaire de cache L4 situé sur une puce dédiée qui est chargée de gérer les communications avec la mémoire vive. Les communications à l’intérieur du CMP utilisent huit bus. Pour limiter le trafic généré par la cohérence, le POWER utilise un protocole hybride basé à la fois sur des répertoires et du snooping.
Les premiers NoC filaires
Dans cette sous-section, nous présentons différents NoC de type grille 2D et leurs particularités. Ils correspondent pour la plupart aux NoC utilisés dans les manycœurs présentés dans la sous-section précédente. SPIN et DSPIN Le réseau Scalable Programmable Integrated Network (SPIN) a été proposé par Guerrier et Greiner [2000] car, comme nous l’avons vu dans la section précédente, les bus ne passent pas à l’échelle. SPIN repose sur un réseau de routeurs par commutation de paquet permettant chacun de relier cinq éléments. La connexion avec chaque élément repose sur une FIFO de réception et une FIFO d’émission. Ces routeurs ne permettent pas uniquement de réaliser des topologies de type grille 2D, ils ont par exemple été utilisés pour mettre en place un FatTree [Adriahantenaina et al., 2003]. Finalement, Miro-Panades et al. [2006] ont proposé une amélioration appelée Distributed SPIN (DSPIN). Elle a été développée pour créer des System on Chip (SoC) découpés en tuiles et organisés en grille 2D. Elle permet aussi de répondre au problème de la distribution des horloges en autorisant le déphasage des horloges des tuiles entre elles. Pour ce faire, le routeur est éclaté sur les quatre bords de la tuile de façon à ce que les FIFO de deux routeurs adjacents puissent être bi-synchrones. Ainsi, les fils les plus longs ne sont plus entre deux tuiles mais à l’intérieur d’une tuile. iMesh Le NoC utilisé dans le CMP Tile64 est décrit par Wentzlaff et al. [2007]. Ce réseau présente la particularité d’être composé de cinq grilles dont une fonctionne par commutation de circuit alors que les autres fonctionnent par commutation de paquet. Tout comme la version non-distribuée de SPIN, le transfert des messages entre les différents ports du routeur est géré par un crossbar central. ANOC Le réseau Asynchronous Network On Chip (ANOC) a été proposé par Thonnart et al. [2010] et est utilisé dans le CMP Platform2012. Tout comme DSPIN, le but de ce NoC est de permettre l’implémentation de SoC respectant le paradigme Globally Asynchronous Locally Synchronous (GALS). Pour ce faire, le NoC repose sur trois composants : les routeurs, les liaisons et les interfaces GALS. Les routeurs possèdent cinq ports d’entrées/sorties et supportent deux canaux virtuels. Les liaisons entre les routeurs utilisent des répétiteurs pour supporter l’allongement des fils et sont asynchrones. Finalement, les interfaces GALS permettent à la fois de gérer la différence entre l’horloge du NoC et l’horloge locale, mais aussi de générer cette dernière. Alors que DSPIN permet la gestion d’horloges locales déphasées, ANOC permet de gérer différents domaines d’horloges. Mesh du SCC Le réseau utilisé par le SCC d’Intel a été proposé par Salihundam et al. [2011]. Il repose sur un réseau de routeurs utilisant des jetons pour favoriser alternativement certains chemins à travers le NoC. De plus, l’une des principales préoccupations ayant mené au développement de ce NoC est la consommation énergétique. Dans ce but, le SoC est découpé en plusieurs zones pouvant fonctionner à différentes tensions.
|
Table des matières
1 Préambule
1.1 Introduction
1.2 Plan de la thèse
2 Contexte et problématique
2.1 Introduction
2.2 Les besoins applicatifs
2.2.1 Architecture d’un ordinateur
2.2.2 Les différents niveaux de parallélisme
2.2.3 Les différentes classes d’applications
2.2.4 Conclusion
2.3 Les multi-cœurs
2.3.1 Architectures existantes
2.3.2 Médiums de communication utilisés
2.3.3 Limitations
2.4 Les many-cœurs
2.4.1 Les architectures many-cœurs existantes
2.4.2 Les premiers NoC filaires
2.4.3 Limitations
2.5 Conclusion et problématique
3 État de l’art
3.1 Introduction
3.2 Améliorations de la bande-passante et de la latence
3.2.1 Approches filaires 2D
3.2.2 La 3D
3.2.3 L’optique
3.2.4 La Radio Fréquence
3.2.5 Synthèse
3.3 Support du multicast et du broadcast
3.3.1 NoC filaires
3.3.2 NoC optiques
3.3.3 NoC RF
3.3.4 Synthèse
3.4 Reconfiguration dynamique
3.4.1 NoC filaires
3.4.2 NoC optiques
3.4.3 NoC RF
3.4.4 Synthèse
3.5 Conclusion
4 Architecture WiNoCoD
4.1 Introduction
4.2 Principes de l’architecture
4.2.1 Un réseau RF reconfigurable dynamiquement
4.2.2 Un réseau hiérarchique
4.2.3 L’OFDMA
4.2.4 L’algorithme d’allocation dynamique distribué
4.2.5 Le broadcast
4.3 La hiérarchie de WiNoCoD
4.3.1 Tuiles
4.3.2 Grappes
4.3.3 CMP
4.4 Le NoC RF
4.4.1 L’architecture de l’interface RF
4.4.2 Description détaillée des composants
4.4.3 L’algorithme d’allocation dynamique
4.4.4 Le contrôleur RF : support matériel de l’allocation dynamique
4.5 Conclusion
5 Modélisation SystemC de l’architecture
5.1 Introduction
5.2 Outils de modélisation
5.2.1 SystemC
5.2.2 SoClib
5.3 Modélisation de l’architecture
5.3.1 Le routeur 3D
5.3.2 L’arbitre
5.3.3 Le codeur
5.3.4 Le placeur
5.3.5 Le guide d’ondes numérique
5.3.6 Le multiplexeur
5.3.7 Le décodeur
5.3.8 Le routeur RF
5.3.9 Le contrôleur RF
5.4 Conclusion
6 Expérimentations et résultats
6.1 Introduction
6.2 Évaluation des performances intrinsèques
6.2.1 Protocole expérimental
6.2.2 Résultats
6.2.3 Analyse
6.3 Évaluation technologique
6.3.1 Protocole expérimental
6.3.2 Résultats
6.3.3 Analyse
6.4 Évaluation via un trafic réel
6.4.1 Protocole expérimental
6.4.2 Résultats
6.4.3 Analyse
6.5 Évaluation via un trafic synthétique
6.5.1 Protocole expérimental
6.5.2 Résultats
6.5.3 Analyse
6.6 Conclusion
7 Conclusion et perspectives
7.1 Conclusion
7.2 Perspectives
7.2.1 Court terme
7.2.2 Moyen terme
7.2.3 Long terme
Liste des publications
Bibliographie
Glossaire
Télécharger le rapport complet
