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.
Les différents niveaux de parallélisme
Parallélisme d’instruction
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).
Parallélisme de tâche
L’utilisation des pipelines permet d’augmenter la fréquence de fonctionnement d’un processeur. L’utilisation de techniques telles que l’exécution dans le désordre et la prédiction de branchement permet au pipeline d’approcher un fonctionnement idéal d’une instruction chargée par cycle. L’utilisation de processeurs superscalaires permet d’améliorer encore les performances et de charger plusieurs instructions par cycle. Cependant ces techniques présentent certaines limites. D’une part, ces méthodes ont un coût matériel important. Par exemple, plus le nombre de pipelines d’un processeur superscalaire augmente, plus le module d’exécution dans le désordre doit être efficace, devenant de plus en plus complexe. D’autre part, le code exécuté impose lui-même certaines limitations. Il présente toujours un caractère séquentiel plus ou moins important et certaines instructions doivent impérativement être exécutées l’une après l’autre dans un ordre précis.
Les différentes classes d’applications
Avant de décrire plus en détail l’architecture des différents CMP, il est nécessaire de caractériser les applications qu’ils exécutent. La première approche retenue est de diviser ces applications en trois catégories [Wang et al., 2009]. Les applications de bureautique, les applications multimédia et les applications de calcul scientifique ou High Performance Computing (HPC). La deuxième approche retenue est de suivre la classification proposée par Asanovi´c et al. [2006], les « nains de Berkeley ». Les applications sont alors classées selon les caractéristiques de l’algorithme utilisé, en terme de calculs et de communications.
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.
|
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
6 Expérimentations et résultats
7 Conclusion
Télécharger le rapport complet
