Relation entre l’ordonnancement des instructions et l’allocation des registres

Processeurs ARM

De nos jours, les processeurs ARM dominent largement le marché de l’électronique embarquée. En 2014, on a dénombré 12 milliards de puces en circulation qui utilisent la propriété intellectuelle ARM (Vijay & Bansode, 2015). L’adoption à grande échelle des processeurs ARM a été favorisée par la simplicité de leur architecture, leurs performances et leur grande efficacité énergétique. Les noyaux ARM se distinguent de la concurrence par leur modèle de mise en marché. Ces noyaux sont vendus sous la forme de propriété intellectuelle aux grands manufacturiers (Samsung, Texas Instrument, etc.). Ces derniers les intègrent avec d’autres périphériques, dans le cadre d’une implémentation spécifique, pour produire des microcontrôleurs, des processeurs ou des SoC (System On Chip). Ces circuits sont produits à grande échelle, par la suite, dans un laboratoire de semi-conducteurs. Les noyaux ARM implémentent un jeu d’instructions RISC (Reduced Instruction Set Computing) où la plupart des instructions s’exécutent en un cycle d’horloge. Les instructions faisant partie du ARM ISA (Instruction set architecture) offrent, pour la plupart, des caractéristiques intéressantes comme les décalages intégrés ou l’exécution conditionnelle. L’architecture RISC impose la manipulation de la mémoire par le biais des registres. Les noyaux ARM permettent des accès multiples à la mémoire à travers les instructions LDM (Load Multiple), STM (Store Multiple) et leurs variantes.

Ces instructions permettent l’échange simultané de plusieurs valeurs avec la mémoire selon la largeur du bus reliant cette dernière au processeur. Les processeurs ARM possèdent différents modes d’opérations et ces modes se qualifient de « privilégiés » s’ils s’exécutent avec des mécanismes de protection. Les modes privilégiés, comme les modes superviseur et système, permettent l’exécution protégée des processus critiques du système d’exploitation, tandis que les modes FIQ (Fast Interrupt Request) et IRQ (Interrupt Request) permettent la gestion des interruptions. Le mode utilisateur, qui permet l’exécution de la majorité des applications, est un mode non privilégié. En mode utilisateur, un noyau ARM dispose de 16 registres dont 13, à usage général ainsi qu’un registre de contrôle et d’état CPSR (Current Program Status Register). Le tableau 1.1. montre les fonctions des registres. Ces registres de 32 bits peuvent contenir des données 8, 16, ou 32 bits selon la nature de la donnée. Dans le cas d’un registre contenant plusieurs données, ces dernières sont manipulées à l’aide d’un suffixe ajouté à l’instruction. Le registre CPSR permet d’activer les différents modes d’opération ainsi que certaines extensions architecturales, telles qu’illustrées à la figure 1.1 (Vijay & Bansode, 2015). Ce registre contient surtout les bits d’état qui maintiennent les drapeaux conditionnels d’égalité, de signe, de dépassement et de retenue. Les instructions conditionnelles sont exécutées selon la valeur de ces bits.

Premiers designs des processeurs asynchrones

La première implémentation notable d’un processeur asynchrone a été introduite par Martin (1989) dans un projet de l’Institut Caltech (California Institute of Technology). Ce processeur dispose d’un bus de données d’une largeur de 16 bits et effectue les différentes opérations de traitement d’un processeur RISC standard. Ces opérations sont les calculs arithmétiques et logiques sur des entiers, les accès à la mémoire (écriture et lecture) et les branchements. La synchronisation des différents éléments est basée sur un établissement de liaison (Handshake). Cette approche a démontré la possibilité d’implémenter un processeur fonctionnel ne disposant pas de distribution d’horloge et a permis d’atteindre une performance estimée à 15 MIPS en technologie 2μm. L’approche, décrite par Cho et al. (1992), introduit un processeur 32 bits entièrement asynchrone. Le FAM (Fully Asynchronous Microprocessor) implémente une architecture endochrone à 18 instructions utilisant 32 registres. Cette architecture possède un pipeline à quatre étages : acquisition de l’instruction, communication avec la mémoire externe, décodage de l’instruction et finalement l’étage d’exécution (permettant aussi d’écrire le résultat dans le fichier des registres). Un établissement de liaison à 4 phases se fait entre les étages adjacents du pipeline, pour synchroniser le transfert des données entre ces derniers. Ce modèle de communication est illustré à la figure 1.2. Dans ce modèle, le bloc 1 envoie une requête (Rin) au module de communication pour l’informer que les données sont prêtes. Le module de communication déclenche, dès lors, la bascule qui mémorise les données transmises par le bloc 1 à l’aide d’une communication bidirectionnelle (Lin et Lack) et notifie le bloc 2 de cette requête avec le signal Rout . Ce dernier transmet sa confirmation au bloc 1 par l’entremise du module de communication (Ain et Aout ). Le transfert des données se déclenche et le bloc 1 envoie une requête de terminaison.

Dès lors que le bloc 2 reçoit l’ensemble des données, il confirme la terminaison. À la réception de cette dernière Brunvand (1993), chercheur à l’université de l’Utah, a développé un processeur asynchrone dénommé NSR (Nonsynchronous Risc). Le NSR est un processeur 16 bits qui implémente 16 instructions comprenant des opérations logiques et arithmétiques, des accès mémoire et des branchements. Ce processeur est un amalgame de plusieurs blocs endochrones qui sont synchronisés grâce à un établissement de liaison à deux phases. Chaque bloc représente une étape du pipeline. L’utilisation de ces blocs dépend de l’instruction, de manière à ce que chaque instruction utilise uniquement les blocs dont elle a besoin. La figure 1.3 (Werner & Akella, 1997), offre un aperçu, à haut niveau, de cette architecture. Le NSR a été implémenté sur FPGA et a permis d’obtenir une performance de 1.3 MIPS (million d’instructions par seconde).

Du fait de son implémentation sur FPGA, les performances du NSR sont difficiles à comparer avec celles des autres processeurs, car les FPGA sont plus lents que les circuits ASIC (Application Specific Integrated Circuit) (Werner & Akella, 1997). L’architecture STRIP (A self timed RISC processor), publiée par Dean (1992), est un exemple de processeur endochrone possédant un système de synchronisation particulier. Alors que la majorité des processeurs asynchrones utilisent un système d’établissement de liaison pour coordonner les tâches de traitement, le STRIP utilise un système d’horloge dynamique. Ce système repose sur des cellules de repérage qui déterminent le temps de propagation critique du chemin logique utilisé pour générer un signal d’horloge ayant une période adéquate. Ce système est présenté à la figure 1.4 (Werner & Akella, 1997). En résumé, cette architecture est synchrone avec une horloge qui s’adapte ce qui permet d’imposer un temps d’exécution selon la charge du traitement requis. Ceci est particulièrement utile dans le cas où une étape de calcul ne nécessite pas d’accès à la mémoire. La période d’horloge dans ce cas-ci sera considérablement réduite, car elle ne prendra pas en compte le chemin logique de la transaction avec la mémoire. La performance moyenne de ce design est de 62.5 MIPS sur une technologie 2-μm CMOS.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION
CHAPITRE 1 ARCHITECTURE ASYNCHRONE ET ARM
1.1 Processeurs ARM
1.2 Historique des processeurs asynchrones
1.2.1 Premiers designs des processeurs asynchrones
1.2.2 ARM asynchrone
1.3 Architecture de l’AnARM
1.3.1 Présentation générale de l’AnARM
1.3.2 Synchronisation intra modulaire
1.3.3 Synchronisation inter modulaire
1.4 Conclusion
CHAPITRE 2 ORDONNANCEMENT DES INSTRUCTIONS
2.1 Cadre théorique
2.1.1 Ordonnancement des instructions
2.1.1.1 Dépendances de données
2.1.1.2 Disponibilité des ressources
2.1.1.3 Graphe de flot de données
2.1.1.4 Définition du problème d’ordonnancement des instructions
2.1.2 Allocation des registres
2.1.2.1 Intervalle de vie d’une variable et graphe d’interférences
2.1.2.2 Relation entre l’ordonnancement des instructions et l’allocation des registres
2.2 Techniques existantes d’ordonnancement des instructions
2.2.1 Ordonnancement de liste
2.2.2 Méthodes combinatoires
2.2.3 Ordonnancement pour architectures asynchrones
2.3 Conclusion
CHAPITRE 3 STRATÉGIE D’ORDONNANCEMENT POUR L’ANARM
3.1 Modélisation
3.1.1 Modélisation temporelle
3.1.2 Modélisation spatiale
3.2 Algorithme d’ordonnancement pour l’AnARM
3.2.1 Stratégie d’ordonnancement
3.2.2 Description de l’algorithme d’ordonnancement proposé
3.3 Conclusion
CHAPITRE 4 ÉVALUATION DE L’APPROCHE PROPOSÉE
4.1 Environnement d’implémentation
4.1.1 Ordonnancement des instructions dans LLVM
4.1.2 Implémentation de l’approche d’ordonnancement
4.2 Évaluation de l’approche d’ordonnancement
4.2.1 Environnement expérimental
4.2.2 Choix des paramètres de priorité
4.2.3 Évaluation de l’approche au niveau d’optimisation minimal
4.2.4 Évaluation de l’approche au niveau d’optimisation maximal
4.3 Conclusion
CONCLUSION ET RECOMMANDATIONS
ANNEXE I CODE SOURCE DE L’APPROCHE D’ORDONNANCEMENT
ANNEXE II CODE SOURCE DES PROGRAMMES TÉSTÉS
BIBLIOGRAPHIE