Performances
Pour les concepteurs et architectes de processeurs, l’amélioration des performances de leurs processeurs ainsi que la diminution de leurs coûts sont des sujets permanents. La diminution de la taille des transistors, l’augmentation de la fréquence de l’horloge système et la largeur du bus µP pour l’accès au code et aux données furent d’un apport majeur à cette amélioration.
Mais existe-t-il d’autres chemins pour réduire le temps d’exécution d’un programme ?
Côté logiciel, le choix des bonnes structures de données et des bons algorithmes pour les manipuler est évidemment déterminant afin de réaliser un programme nécessitant un minimum de ressources matérielles (µP, RAM, Flash, temps) pour remplir le cahier des charges du système. Côté matériel, suffit-il juste de réduire le temps de cycle de l’horloge avec des fréquences plus élevées ou existe-t-il d’autres approches ? Est-il possible de mieux utiliser les ressources internes du µP ?
Pipelining
Afin de réduire encore le temps nécessaire à l’exécution d’un programme, il faut s’intéresser à l’exécution des instructions et regarder les différents blocs de traitement qu’une instruction doit franchir avant d’être complètement exécutée.
Principe
En 1913, Henry Ford inaugura la première chaîne de montage pour des véhicules automobiles. L’objectif était de réduire le temps nécessaire au montage des modèles T de plus 12 heures à 1 heure 30.
En prenant cet exemple, il est intéressant de comparer un montage séquentiel du véhicule avec un montage parallèle (figure Montage séquentiel vs parallèle). Pour l’exemple, le montage du véhicule s’effectue en seulement trois étapes, première étape montage du châssis, deuxième étape montage du toit et troisième étape montage des roues.
Le temps nécessaire pour effectuer chacune de ces étapes est \(T_{e1}\), \(T_{e2}\) et \(T_{e3}\), soit un total \(T_{pv}\) pour la production d’un véhicule. Si l’on produit \(n\) véhicules séquentiellement le temps nécessaire est:
Sachant que la valeur de \(T_e\) correspond au temps de l’étape prenant le plus de temps, alors si la production s’effectue en parallèle, le temps nécessaire pour produire ces \(n\) véhicules est de:
Si le nombre de véhicules produits devient très grand, alors le temps de production des véhicules vaut:
ce qui signifie que chaque \(T_e\) un nouveau véhicule est produit.
Pipeline idéal
D’après l’architecture générale, une instruction s’exécute en trois cycles principaux, lecture (fetch), décodage (decode) et exécution (execute). Ces trois cycles correspondent également aux trois unités de l’architecture des CPU ARMv7. De ce fait, l’exécution d’une instruction devra traverser chacune de ces unités.
Pour appliquer le principe de pipelining à un système électronique et plus particulièrement au CPU du µP, il est nécessaire de découpler les unités de traitement, appelées également étage du pipeline, avec des mémoires tampons (buffer). Ces tampons permettent de rendre les étages indépendants les uns des autres (voir figure ci-dessous). Pour un pipeline idéal, deux étages supplémentaires sont nécessaires, un étage d’accès à la mémoire et un étage de réécriture de la donnée après traitement dans la banque de registres.
Si nous considérons que le temps de traitement de chacun de ces étages prend un cycle d’horloge, alors le temps de traitement d’une instruction prendra cinq cycles d’horloge (comme montré dans la figure ci-dessous). Il est intéressant de noter que dès le 5e cycle tous les étages du pipeline sont actifs.
Si le programme contient un grand nombre d’instructions, alors à chaque cycle d’horloge, une instruction finit son exécution et une nouvelle est chargée. Dans ce cas idéal où le pipeline ne bloque jamais, le nombre de cycles par instruction est égal 1 (CPI = 1.0). Cependant, si des bulles (stall) doivent être introduites, le CPI augmentera, par exemple si le pipeline doit être bloqué durant 1 cycle pour 20% des instructions et de 3 cycles pour 5% des instructions, alors le nouveau CPI sera de 1.35.
L’accès à la mémoire centrale et un exemple typique de blocage du pipeline (figure ci-dessous).
En effet, la latence due un accès à une mémoire volatile de type DRAM placée à l’extérieure de la puce du µP est typiquement 10 à 100 fois plus grand que la période de l’horloge du CPU et de son pipeline. L’utilisation de mémoire cache permet de réduire drastiquement cette latence et d’éviter des blocages.
Aléas du pipeline
Le pipeline permet de lancer à chaque cycle d’horloge l’exécution d’une nouvelle instruction débute alors que d’autres sont encore en cours d’exécution dans le pipeline, c’est-à-dire l’exécution des instructions se chevauche (overlapped). Cependant, il existe une série de cas où l’exécution d’une instruction doit attendre, car elle entre en concurrence avec une instruction déjà en cours d’exécution pour l’accès à une ressource, tels la mémoire ou un registre. Afin garantir une exécution correcte, l’instruction est stoppée dans le pipeline, bloquant par conséquent également l’exécution des instructions qui la suivent. Ces cas sont connus sous le nom d’aléas du pipeline (Pipeline Hazards).
Il existe principalement trois classes d’aléas:
- Aléas structurels (Structural Hazards)
- Aléas de données (Data Hazards)
- Aléas de contrôle (Control Hazards)
Il est généralement possible d’éviter ces aléas en dupliquant les ressources partagées. Néanmoins, cela n’est pas toujours possible, notamment pour des accès à la mémoire. Dans ce cas, des bulles (stall) remplaceront le traitement des instructions dans les étages du pipeline concernés.
Aléas structurels
Ces aléas arrivent lorsque deux instructions dans des étages différents du pipeline requièrent la même ressource matérielle.
Dans l’exemple ci-dessus (figure Aléas structurels), l’exécution de la première
instruction “ldr r1, [r2]” entre en conflit avec le chargement de la quatrième
instruction “sub r2, r2, #1”. En effet, l’étage MEM et l’étage IF sont en
concurrence pour l’accès à la mémoire, la première pour lire une donnée et la
deuxième pour lire l’instruction. Une première solution pour résoudre ce conflit
est d’ajouter un bulle (stall) afin de laisser l’étage MEM s’exécuter. Une
meilleure solution est de mettre en oeuvre l’architecture Harvard séparant le
bus de données du bus des instructions permettant un accès simultané au code et
aux données.
Aléas de données
Ces aléas arrivent lorsqu’une instruction requiert une donnée qui n’est pas complètement traitée par l’exécution d’une instruction précédente encore en cours d’exécution dans le pipeline. Ce problème est la conséquence de l’exécution d’une instruction en plusieurs étapes. En effet, l’évaluation des arguments d’une instruction s’effectue dans les premiers étages du pipeline alors les derniers étages produisent le résultat.
Le code d’exemple ci-dessus (figure Aléas de données) présente trois cas de figure d’aléas de données:
- WAW : Ecriture après écriture (Write After Write)
- WAR : Ecriture après lecture (Write After Read)
- RAW : Lecture après écriture (Read After Write)
L’aléa WAW survient lorsque deux instructions utilisent le même registre
pour stocker (Write) le résultat de leur exécution, dans l’exemple il s’agit
du registre R1. Dans un tel cas, il est essentiel de ne pas changer l’ordre
des instructions afin d’éviter que l’instruction suivante reçoive la mauvaise
valeur. Cet aléa est aussi connu sous le nom de “dépendance de noms” (Name
Dependency).
L’aléa WAR survient lorsque deux instructions utilisent le même registre, la
première instruction en lecture (Read) et la deuxième en écriture (Write).
Dans l’exemple ci-dessus, il s’agit du registre R3 pour la deuxième et
troisième instruction, ainsi que du registre R2 pour la troisième et quatrième
instruction.
Ces dépendances peuvent se résoudre en utilisant d’autres registres encore
libres (voir figure ci-dessous).
L’aléa RAW survient lorsqu’une instruction utilise un registre (Read) dont le contenu est écrit (Write) par l’exécution de l’instruction précédente. La flèche verte (figure ci-dessous) représente ce cas de figure typique lors de traitements de données stockées en mémoire.
Si les données doivent impérativement être communiquées par les registres, il
est absolument indispensable de terminer le traitement de la deuxième
instruction (ADD) avant de pouvoir poursuivre l’exécution de la troisième
instruction (STR).
Ce n’est qu’une fois que l’instruction ADD a traversé l’étage WB, que le
résultat de l’addition sera stocké dans la banque de registres.
Par contre l’instruction STR nécessite ce résultat en entrant dans l’étage
IE. Ceci implique l’ajout de deux bulles (stall).
Est-il possible d’éviter l’ajout de ces bulles (stall). Si oui, que faudrait-il mettre en place ?
La solution à cet aléa réside à l’ajout de logique permettant mettre à
disposition d’un étage précédent du pipeline le résultat d’un étage, ceci sans
passer par la banque de registres (voir figure suivante). Dans l’exemple
ci-dessus, le résultat d’une instruction calculé à l’étage IE est directement
mis à l’entrée de cet étage IE.
Aléas de contrôle
Ces aléas arrivent lorsqu’une instruction de branchement, conditionnelle ou pas,
est exécutée et que le branchement est effectué. Dans le cas où le branchement
est effectif, les instructions suivantes déjà dans le pipeline ne doivent plus
être exécutées (figure ci-dessous). Ces instructions se transforment en
instruction NOP et 2 cycles sont ainsi perdus.
Pour éviter ce problème, différentes stratégies sont imaginables, telle l’évaluation du branchement dans l’étage de décodage, la prédiction des branchements ou l’exécution conditionnelle d’instruction.
Processeur superscalaire
Les processeurs superscalaires disposent d’une unité centrale de traitement (CPU) équipée d’un pipeline capable de traiter simultanément plusieurs instructions (voir figure ci-dessous).
A l’opposé des processeurs scalaires ne pouvant exécuter qu’une seule instruction par étage de leur pipeline, les processeurs superscalaires disposent d’une unité centrale de traitement (CPU) avec de plusieurs unités de traitement dans les différents étages de son pipeline (figure ci-dessous).
Le CPU de ces processeurs est apte à détecter le parallélisme existant entre les instructions d’un programme. Il l’utilise pour exécuter simultanément celles qui peuvent l’être. Cette architecture permet de réduire le temps d’exécution du programme, mais au détriment d’une complexité accrue de son design et d’une plus grande consommation d’énergie.
Profil M
En version ARMv7, il existe actuellement trois variantes de µC basés sur le profil M, les Cortex-M3, M4 et M7. Ces µC sont des processeurs scalaires avec un pipeline de trois étages seulement pour les deux premières variantes et six étages pour la troisième. Vu la faible profondeur du pipeline des deux premières variantes, certains de ses étages nécessitent plus d’un cycle d’horloge pour effectuer le traitement correspondant à l’instruction.
Les µC Cortex-M3 et M4 n’implémentent pas de prédiction de branchement. Les jeux
d’instructions Thumb (figure Thumb Instruction Set Encoding) et Thumb-2 (figure
Thumb-2 Instruction Set Encoding) ne supportent pas d’exécution conditionnelle systématique sur
toutes les instructions. Par contre, ils proposent une instruction IT
(If-Then) permettant d’éviter un branchement conditionnel si une, deux ou
trois instructions doivent s’exécuter en fonction d’un test effectué
préalablement.
