#+TITLE : Prise de notes CM 4I100 ARCHI1
Pirouz Bazargan-Sabet ([email protected]) partagé avec : Karine Heydemann ([email protected])
4I100
1 cours par semaine
1 TD de 4h (pas de machine)
3 parties distinctes :
- Processeurs
- Optimisation de code (Karine)
- Mémoire (organisation matérielle)
Deux examens répartis :
Examen réparti 1 (40%) : Processeurs et début de optimisation de code Examen réparti 2 (60%) : Tout
Droit à tous les documents sous forme imprimée.
Pas de questions de cours ni de TD. On demande d’aller au-delà.
Annales disponibles, sans les corrigés.
UE réputée difficile, réputation imméritée. Moyenne des examens est autour de 8,5. 30% seulement réussissent en validation simple. SESI obligatoire, SAR, RES, SFPN sont présents.
Support de cours apparemment compilé par les étudiants de ALIAS.
Hennessey-Patterson, Computer architecture Il faut faire les annales, la structure des examens est très classique.
Le partiel portera sur les cours jusqu’au 4 compris.
https://www-soc.lip6.fr/trac/sesi-m1archi/wiki
Architecture et réalisation sont indépendants.
Qui est l’utilisateur dans le cas d’un processeur ? [les processus, pas vraiment l’utilisateur de la machine]
On doit être capable de concevoir les processeurs à la fin de l’UE.
Dans le cas des processeurs RISC, on ne peut pas parler d’architecture sans parler de réalisation (enfreinte de la règle plus haut).
Architecture représente 4 points (ce qu’un programmeur doit savoir du processeur pour écrire un programme en assembleur) :
- Registres visibles du logiciel
- Jeu d’instruction du processeur
- Comment le processeur voit la mémoire (l’abstraction de la mémoire vue du processeur)
- Mécanismes d’interruptions et reset
On va étudier le processeur MIPS-32.
Rupture de l’année 1980 (MIPS-32 et RISC 1) : conçues à Stanford et Berkeley respectivement.
Avant 1980 : Complex Instruction Set Computer (CISC) Après 1980 : Reduced Instruction Set Computer (RISC)
Il y a 32 registres entiers visibles dans le MIPS-32 R0 à R31.
Chaque registre peut contenir 32 bits.
Aucune différence de permission entre ces registres, sauf R0 et R31.
R0 est le Trash Register → pas vraiment un registre, c’est la constante 0. Il n’est pas modifiable
R31 est le Link Register. Permet d’enregistrer une adresse, l’adresse de retour de la fonction. On peut écrire dessus, même si c’est imprudent.
Ces registres sont indexés
Deux registres nommés LO et HI (32 bits chacun), utilisés seulement pour l’opération * et /.
Le résultat d’une multiplication de deux entiers écrits sur 32 bits doit pouvoir s’écrire sur 64 bits maximum (preuve à refaire). Les deux registres mis bout-à-bout (HI puis LO) donnent le résultat.
Le résultat d’une division de deux entiers écrits sur 32 bits doit pouvoir s’écrire sur 32 : HI le reste, LO le quotient.
Coprocesseur 0 gère le système d’exploitation. A besoin pour cela d’un certain nombre de registres (tous en 32 bits) qui lui sont réservées : STATUS : Quelle est le mode de fonctionnement du processeur (USER ou KERNEL) CAUSE : enregistre la cause de l’interruption ou de l’exception EPC (EXCEPTION PROGRAM COUNTER) : adresse de l’instruction fautive EBASE : Adresse du système d’exploitation dans la mémoire BADVADDR : L’adresse (virtuelle) à laquelle le processeur voulait accéder avant erreur. Ne correspond pas forcément à une adresse physique de la machine.
add R3, R4, R5Ici, l’instruction donne : “écrit dans R3 (la cible) la somme de R4 et R5”.
Dans le cas de RISC :
Toutes les instructions font la même taille : de cette manière, je sais où elles commencent et où elles s’arrêtent.
On a trois formats dans un processeur MIPS-32 :
Dans un format régulier (R), on a :
- Un opcode : Code de l’opération qu’on veut faire, codée sur 6 bits, donc 2^6 opérations différentes (= 64). Innovation de RISC : permettre moins d’opérations.
- Le numéro du registre source Rs
- Le numéro du registre source Rs
- Le numéro du registre source Rs
- Le décalage éventuel
- Func, un complément du opcode
| Opcode | R_s | R_t | R_d | Shift Amount | Func |
| 6 | 5 | 5 | 5 | 5 | 6 |
Shift amount n’est utilisé que pour les instructions de décalage.
Autre format, le format I (immédiat), pour les opérations avec des constantes :
| Opcode | R_s | R_t ou R_d | Const |
| 6 | 5 | 5 | 16 |
La constante est donc au maximum 2^16. Pour manipuler des plus grosses constantes, il faudra plusieurs instructions.
Autre format, le format J (jump), pour les sauts :
| Opcode | Const |
| 6 | 26 |
La constante donne l’adresse vers laquelle on veut sauter. Ce processeur peut donc gérer 2^26 octets (64 Mo environ)
L’opcode est toujours au même endroit, parce que c’est ce qu’il faut pour déterminer quel est le format utilisé.
Le opcode 000000 (et 000001 apparemment) disent qu'on est sur un format R.
Quatre catégories d’instruction :
- Instructions de calcul (arithmétiques et logiques)
- Instructions d’accès à la mémoire
- Instructions de contrôle (sauts ou branchements)
- Instructions dites système
Add Rd, Rs, RtSi le résultat de l’opération ne peut pas s’écrire sur 32 bits (33 maximum en cas d’addition de deux nombres sur 32 bits) erreur d’overflow.
Addu Rd, Rs, RtMême chose sans erreur d’overflow
Soustraction
Même sans erreur d’overflow
Addi Rd, Rd, IAddition du contenu d’un registre et d’une constante.
La même sans erreur d’overflow.
Problème : On additione un entier sur 32 bits (le contenu d’un des 30 registres) et un entier sur 16 bits (les 16 derniers bits du mot).
Pour que cette opération soit valable, on doit convertir ce nombre écrit sur 16 bits en un nombre écrit en 32 (pas l’inverse, le registre qui doit accueillir le résultat étant grand de 32 bits)
Un certain nombre de choses sur lesquelles Pirouz “Ferrari” Bazargan est passé un peu vite.
Donc, si on veut écrire des nombres naturels, sans signe, on utilise le premier vecteur, si on veut écrire des nombres relatifs, on utilise le deuxième.
Donc, un même nombre en binaire : 1001, ne s'interprète pas de la même manière selon qu'on décide que c'est un entier naturel et un relatif : Si c'est un naturel : 9 Si c'est un relatif : -7
On appelle les nombres dans Z les nombres arithmétiques, et les nombres de N de nombres logiques. (Jargon des architectes de processeur)
Puisque l’immédiat appartient à Z, on a pas besoin d’une instruction subi ou subiu (il suffit d’utiliser addi ou addiu avec un entier négatif).
sll Rd, Rt, ShamSham = Shift amount
Sham est codé sur 5 bits (on n’a que 32 registres). On peut donc se permettre de mettre cette instruction dans R.
Remarquez le Rt en lieu du Rs : on décale le deuxième registre source (pas de premier).
Cette opération met le contenu de Rt à gauche de Rd (les bits à gauche, autrement dit le poids fort). (Revient à multiplier par une puissance de 2 la partie de Rt qui n’est pas “écrasée”, on décale les bits à gauche).
Dans le poids faible, on met des 0 : multiplication.
srl Rd, Rt, ShamSham = Shift amount
Sham est codé sur 5 bits. On peut donc se permettre de mettre cette instruction dans R.
Remarquez le Rt en lieu du Rs : on décale le deuxième registre source (pas de premier).
Cette opération met le contenu de Rt à droite de Rd (les bits à droite, autrement dit le poids faible).
Dans le poids fort, on complète avec des 0 : nombre logique.
srl Rd, Rt, ShamPareil, avec des nombres arithmétiques (on étend le bit du poids fort si besoin est), et on complète avec des 0 à droite (multiplication par une puissance de 2).
sra Rd, Rt, ShamPareil, avec nombres arithmétiques (on décale à droite de Sham octets), et on complète à gauche en étendant le bit du poids fort.
Prend trois registres Rd, Rs, Rt, et inscrit dans Rd le résultat de l’opération bit à bit OR, AND, XOR ou NOR (tous les 32 couples de bits sont interprétés et mis dans le bit correspondant du registre destination).
OR : On met 1 sssi au moins une des deux sources a 1 AND : On met 1 sssi les deux sources ont 1 XOR : On met 1 sssi exactement une source a 1 NOR : On met 1 sssi exactement zéro source a 1
Même chose que la série précédente, avec un immédiat I
I est ici interprété comme un entier naturel (opération logique), il est donc étendu par zéro à 32 bits avant la comparaison.
The AND, OR, and XOR instructions can alternatively source one of the operands from a 16-bit immediate (which is zero-extended to 32 bits).
On a pas Nori :
La manière dont les architectes choisissent les opérations à inclure dans le jeu d’instruction dépendent du marché, des utilisateurs potentiels. On fait des benchmark, on obtient une table des instructions du processeur utilisées, et leur poids.
Ici, Nori a dû être considéré pas assez important. De surcroît, c’est une opération de format I, et les places sont très chères (plus que dans R : Nor a été pris).
Si on part du principe qu’on peut réinterpréter une opération inexistante en N opérations existantes, on peut sacrifier cette opération à condition qu’elle soit peu utilisée.
lui Rd, ILoad upper immediate
Prend les 16 bits de I et les enregistre à gauche (poids fort) et on complète à droite (poids faible) avec des 0.
slt Rd, Rs, RtSet on less than
Met 1 dans Rd sssi Rs < Rt (strictement), 0 sinon. Le contenu de Rs et Rt sont interprétés comme des entiers signés.
sltu Rd, Rs, RtSet on less than unsigned
Met 1 dans Rd sssi Rs < Rt (strictement), 0 sinon.
Le contenu de Rs et Rt sont interprétés comme des entiers non signés.
stli Rd, Rs, ISet on less than immediate
Met 1 dans Rd sssi Rs < I (strictement), 0 sinon.
Le contenu de Rs et I sont interprétés comme des entiers signés.
stliu Rd, Rs, ISet on less than immediate unsigned
Met 1 dans Rd sssi Rs < I (strictement), 0 sinon.
Le contenu de Rs et I sont interprétés comme des entiers non signés.
The variants of these instructions that are suffixed with “unsigned” interpret the operands as unsigned integers (even those that source an operand from the sign-extended 16-bit immediate).
Processeur MIPS est 32 bits, donc les adresses mémoire sont sur 32 bits.
1 adresse représente 1 octet.
On peut donc avoir 2^32 octets de mémoire, soit à peu près 4 Go.
2G (de l’espace d’adressage) sont réservés au système d’exploitation. Grâce au registre STATUS, on sait si le truc qui essaie d’accéder à la zone noyau de l’espace d’adressage est le noyau ou un utilisateur.
Important : Il est ici question d’espace d’adressage !!!! Pas de mémoire physique. À un espace d’adressage de 4Go peut ne pas correspondre la même mémoire physique.
On peut lire ou écrire :
- octet
- Demi-mot (2 octets)
- Mot entier (4 octets)
Les données sont cadrées à droite (convention). On met un octet dans le poids faible du registre (l’octet à droite).
Quand tu copies vers la mémoire depuis un registre, dans quel sens : poids faible en haut (adresse plus petite) ou en bas (adresse plus grande) ?
Deux conventions :
- Little-endian (petit-boutiste) : Adresse la plus petite reçoit le poids fiable, la fin du mot
- Big-endian (gros-boutiste) : Adresse la plus grande reçoit le poids faible, la fin du mot
On ne peut lire que des adresses qui sont des multiples de la taille de l’objet.
L’adresse d’un octet est multiple de 1 L’adresse d’un demi-mot est multiple de 2 L’adresse d’un mot est multiple de 4
Lw Rd, I(Rs)Lit 4 octets (load word) de mémoire à l’adresse Rs + I, enregistrés dans le registre Rd.
Sw Rt, I(Rs)Store Word
Stocke 4 octets du registre Rt à l’adresse mémoire Rs + I.
LH Rd, I(Rs)Lit 2 octets (load half-word) de mémoire à l’adresse Rs + I, enregistrés dans le registre Rd. Serré à droite dans ce registre donc (convention de cadrage à droite).
Cette opération considère des entiers relatifs : on étend donc à gauche avec le signe.
LHU Rd, I(Rs)Lit 2 octets (load half-word) de mémoire à l’adresse Rs + I, enregistrés dans le registre Rd. Serré à droite dans ce registre donc (convention de cadrage à droite).
Cette opération considère des entiers naturels : on étend donc à gauche avec des zéros.
SH Rt, I(Rs)Store Half Word
Stocke 2 octets du registre Rt (les deux octets de droite, on suppose : convention) à l’adresse mémoire Rs + I.
LB Rd, I(Rs)Load Byte
Lit 1 octet de mémoire à l’adresse Rs + I, enregistrés dans le registre Rd. Serré à droite dans ce registre donc (convention de cadrage à droite).
Cette opération considère des entiers relatifs : on étend donc à gauche avec le signe.
LBU Rd, I(Rs)Load Byte Unsigned
Lit 1 octet de mémoire à l’adresse Rs + I, enregistrés dans le registre Rd. Serré à droite dans ce registre donc (convention de cadrage à droite).
Cette opération considère des entiers naturels : on étend donc à gauche avec des zéros.
SB Rt, I(Rs)Store Byte
Stocke 1 octet du registre Rt (l’octet de droite, on suppose) à l’adresse mémoire Rs + I.
Branch if equal : Saute vers l’adresse “Label” si Rt à Rs
C’est l’assembleur qui traduit Label vers une adresse.
Beq Rs, Rt, LabelLabel est remplacé par un immédiat.
Si Rs != Rt, on continue à l’addresse suivante (@cible = @seq) Si Rs = Rt, on (@cible = @Bt + 4 + I*4)
(Pourquoi +4 : On pense que c’est pour éviter une boucle infinie si I est donné à 0. On pourrait toujours donner I = -1, mais il faudrait le vouloir)
Branch if ne
Bne Rs, Rt, LabelBranch if less than 0 (strict)
Compare Rs à 0 (pas besoin de Rt)
BlTZ Rs, LabelBranch if less than 0 (large)
BleZ Rs, LabelBranch if greater than 0 (strict)
BgTZ Rs, LabelBranch if greater than 0 (large)
BgeZ Rs, LabelJ labelBranchement inconditionnel, soit saut.
Problème : On a que 26 bits pour mettre l’adresse vers laquelle on doit sauter.
On met :
- Les 4 (premiers) bits de l’adresse actuelle
- Les 26 bits du label
- 2 bits 00 au poids faible (en effet, si on saute vers un mot, l’adresse doit être multiple de 4. Et on sait qu’on saute vers un mot, puisqu’on saute vers une instruction.)
(On se rappellera de l’aparté plus haut : A partir de cet aparté, on peut déduire trivialement que si un nombre non-nul écrit en binaire a ses n derniers chiffres égaux à 0, alors il est divisible par 2^n)
La partie variable de l’adresse de destination est de l’ordre de 2^28, pas de 2^32 (les 4 premiers bits fixes égaux aux 4 premiers bits de l’adresse actuelle). On ne peut sauter que dans un bloc (256 Mo) au lieu de pouvoir sauter dans l’espace d’adressage complet de ≈ 4 Go
Saute à l’adresse contenue dans un registre Rs.
Jr RsJump and link. On ne pert pas l’endroit d’où on a sauté.
L’adresse de retour (l’adresse d’où on est parti + 4) est stockée dans R31.
Jal LabelJump and link, mais avec un registre Rs
Jalr RsCISC vs RISC
CISC pensait que ces capacités supplémentaires serviront à faire des instructions de plus en plus complexes. Le but était de faire tendre l’assembleur CISC vers la complexité des langages de haut niveau. Le but était de réduire le gap sémantique entre les langages de haut niveau et l’assembleur CISC.
L’idée était que plus le langage assembleur est fort, plus il est facile d’exprimer des algorithmes complexes en un nombre réduit d’instructions processeur.
Le processeur IBM 370, datant de 1978, est l'exemple canonique du processeur CISC. Incluait une instruction strcmp (comparaison de chaîne de caractères). Le processeur VAX (Virtual architecture extension) Digital (les inventeurs de la mémoire virtuelle). Dans le processeur VAX, on pouvait faire des additions avec des opérandes en mémoire (pas forcément dans les registres), avec le supplément d'instructions que ça supposait. Chaque processeur était conçu pour un type d'application particulier.
L’intuition de RISC, c’est exactement le contraire. Il faut réduire les instructions, rapprocher l’assembleur du matériel.
Soit l’instruction C suivante :
a = b + c;Les traductions en :
| VAX | Mips |
| ADD @a, @b, @c | LW R4, @b |
| LW R5, @c | |
| ADD R6, R4, R5 | |
| SW R6, @a |
Si on retient comme critère le nombre d’instructions, VAX est objectivement mieux.
Il y a d’autres critères :
- L’encombrement mémoire (quel espace occupe le programme en mémoire avant d’être exécuté) : VAX est meilleur uniquement si la mémoire est chère.
- Facilité d’écrire les programmes : VAX est meilleur uniquement si on doit écrire en assembleur à la main.
- Time-to-market : on veut un processeur facile à faire, pour réduire le TTM (TTM du RISC = moins d’un an alors que TTM du CISC = 4 ans).
On peut choisir de faciliter la vie des gens qui fabriquent le matériel ou ceux qui écrivent les programmes en assembleur. Si les deuxièmes disparaissent, on a plus besoin de choisir.
Le vrai sens des processeurs RISC, c’est Reject Important Stuff into the Compiler. C’était pensé comme une insulte de la part de CISC (dans un long papier du début des années 80), mais c’est en fait exactement l’idée, assumée par RISC : la production de l’assembleur est trop compliqué pour être laissé à des humains, ce sont les compilateurs qui doivent s’en occuper.
La conséquence logique de ça est donnée par une citation bien plus tardive (années 2000-2010) de Linus Torvalds :
Une architecture n’existe pas s’il n’existe pas de compilateur C vers cette architecture.
Linus Torvalds
La performance dépend de deux facteurs.
- La fréquence du processeur (F : Fréquence)
- Le nombre de cycles de la totalité des instructions à exécuter (CPI : Cycle Par Instruction), cappé à 1 bien entendu.
La performance est donc donnée par
Pour se donner un objectif maximal sur la deuxième composante, il faut et il suffit d’atteindre ou de tendre vers CPI = 1. On prend chacune des instructions, et on regarde ce qu’on doit mettre dans le processeur pour qu’elle soit exécutable en un seul cycle (si possible).
Voilà les contraintes sur la réalisation
| ADD Rd, Rs, Rt | LW Rd, I(Rs) | SW | JR | |||
|---|---|---|---|---|---|---|
| D | Lire instruction en mémoire | V | V | V | V | |
| D | Décoder opcode | V | V | V | V | |
| D | D | Lire les opérandes | V | V | V | V |
| D | Operation | V | V | V | ||
| D | Accès mémoire | V | V | |||
| X | Sauvegarde du résultat | V | V | |||
| X | Adresse instruction suivante | V | V | V | V |
Le matériel est défini par la colonne de gauche : Ce que le matériel doit posséder pour pouvoir exécuter toutes les instructions possibles dans le jeu.
On doit maintenant regarder quelle opération dépend de quelle opération : graphe de dépendance.
Sauvegarde du résultat dépend de l’accès mémoire, qui lui même dépend de l’opération (quelle opération), qui lui-même dépend de l’opérande, qui dépend de quelle instruction on est en train d’exécuter, donc du décodage, qui dépend du chargement de l’instruction en mémoire.
Adresse de l’instruction suivante dépend de la lecture des opérandes.
La réalisation est en fait très simple : il faut et il suffit de construire une réalisation qui respecte les dépendances :
On parle bien d’une boucle de conception : on ne part pas des instructions pour faire la réalisation, mais pas complètement l’inverse non plus.
On a bien CPI = 1, par construction (le CPI est défini comme le temps qu’il faut pour traverser le matériel qui est les opérations)
Comment on fait pour augmenter la fréquence à CPI défini et fixe ?
Notion de pipeline : au fond, chacun des ports du matériel peut être occupé au même moment. Si on met des registres entre les opérations atomiques, on augmente la fréquence. Il faut foutre des registres partout. Plus on découpe, plus on augmente la fréquence.
Le découpage en étage de pipeline n’a rien à voir avec les opérations : on n’est pas limité aux opérations, on peut couper en plein de portes, ou d’étage de pipeline.
La période d’horloge est défini comme l’opération la plus grande. Il faut couper de manière équilibrée.
Les architectes du MIPS ont défini le pipeline comme ceci :
| ADD Rd, Rs, Rt | LW Rd, I(Rs) | SW | JR | Etage de pipeline | |||
|---|---|---|---|---|---|---|---|
| D | Lire instruction en mémoire | V | V | V | V | IFC : Instruction fetch | |
| D | Décoder opcode | V | V | V | V | DEC : Decode | |
| D | D | Lire les opérandes | V | V | V | V | DEC |
| D | Operation | V | V | V | EXE : Execute | ||
| D | Accès mémoire | V | V | MEM : Memory access | |||
| X | Sauvegarde du résultat | V | V | WBK : Writeback | |||
| X | Adresse instruction suivante | V | V | V | V |
Pipeline :
| I | D | E | M | W | |||||
| I + 1 | D + 1 | E + 1 | M + 1 | W + 1 | |||||
| I + 2 | D + 2 | E + 2 | M + 2 | W + 2 | |||||
| I + 3 | D + 3 | E + 3 | M + 3 | W + 3 | |||||
| I + 4 | D + 4 | E + 4 | M + 4 | W + 4 | |||||
| I + 5 | D + 5 | E + 5 | M + 5 | W + 5 |
Temps en abscisses (chaque trait est un front d’horloge : montant plus descendant)
Si ça correspond à peu près aux opérations, c’est par hasard : il se trouve que les étages étaient équilibrés de cette manière.
Le cycle d’instruction, c’est le temps qu’il faut pour injecter une nouvelle instruction (elle a été multipliée par 5 par notre amélioration) La latence, c’est le temps que l’instruction met à se terminer (elle n’a pas changé, au moins pour la première opération)
On connaît l’adresse de l’instruction qui suit après D, mais on en a besoin avant ! En fait, l’adresse de l’instruction qui suit est l’adresse de l’instruction i + 2. L’adresse de l’instruction i + 1 est connue dès la fin de l’étage D de l’instruction n - 1.
Toutes les instructions passent par le même schéma d’exécution, qu’on ne rappellera pas ici.
C’est à la condition d’existence d’un schéma unique qu’on peut définir l’optimisation pipeline.
Règles du pipeline (rappels) :
- Les étages doivent être équilibrés : temps de propagation dans chaque étage doit être à peu près le même.
- Les étages doivent être séparés par des registres : les étages doivent être compartimentés.
- Un matéériel quelconque doit appartenir à un étage unique (tous les étages sont en train de travailler à chaque instant : un matériel ne peut pas faire deux choses à la fois)
Prenons une instruction simple, et regardons comment elle se comporte dans le pipeline : schéma détaillé, qui montre exactement ce qui se passe dans chaque étage quand j’exécute une instruction.
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RM | >- | ||||||||
| -> | I_RE | >- | ||||||||
| -> | I_RD | >- | ||||||||
| -> | I_RI | >- | ||||||||
| -> | R Soper | >-1 | ||||||||
| 1+2 -> | RES_RE | >- | ||||||||
| -> | R Toper | >-2 | ||||||||
| R Ioper | ||||||||||
| 32 R du CPU | >- | -> | 32 R du CPU | |||||||
| -> | DATA_RM | |||||||||
| R @instr | >- | R @instruction | >-+4-> | R @instr | ||||||
| >-IMEM-> | ||||||||||
| >-DMEM-> |
Chaque trait représente un front d’horloge (montant, le trait descendant est au milieu de deux traits).
Ce genre de schéma permet de s’assurer que deux registres ne soient pas utilisés à deux moments différents.
On a deux matériels combinatoires (le truc dans EXE, et le +4 dans DEC) seulement, mais plein de registres. 70 % de la surface d’un processeur pipeline typique est consacrée aux registres.
Tous les registres sont suffixés par l’étage auquel ils appartiennent (un registre appartient à l’étage qui écrit dedans).
Le principe de ce schéma, c’est de lister le matériel nécessaire à faire une opération (ici, on a seulement dessiné pour ADD et LW). En calquant les contraintes pour toutes les instructions, on obtient le schéma complet du matériel : métier de galérien. (et on parle de RISC, pas de CISC)
La même chose, pour BEQ :
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RI | >- | ||||||||
| -> | R Soper | |||||||||
| 1=2 | ||||||||||
| -> | R Toper | |||||||||
| 32 R du CPU | >-1,2 | |||||||||
| R @instr | >- | R @instruction | >-+4 -> | R @instr | ||||||
| >-+I*4 -> | ||||||||||
| >-IMEM-> | ||||||||||
Pour multiplier par une puissance de 2 (a + 2 * b), on peut se contenter de décaler la nappe de l’opérande b vers le poids fort de log_2(facteur)
La technique de calculer +(immédiat * 4) et +4 ne marche que si on sait que l’instruction précédente a bien demandé +4 : on n’a aucun moyen de s’en assurer, ce sera au compilateur de le faire : REJECT IMPORTANT STUFF into COMPILER.
On a un autre problème : au moment ou on a décidé qu’on devait aller ailleurs, l’instruction séquentielle est déjà chargée en registre. Comment on fait :
- On implémente une solution kill, mais ça coûte du matériel.
- On ne s’en occupe pas
L’instruction de branchement est retardée (Delayed Slot) : l’instruction séquentielle sera exécutée quoiqu’il arrive, ce qui n’est pas ce qu’on veut.
Une solution, c’est de mettre une opération NOP : certains compilateurs font ça. Ou alors on trouve une chose utile à faire : on réarrange l’ordre des opérations : réordonnancement.
Deux contraintes pèsent sur le compilateur :
- L’instruction avant un branchement doit être séquentielle
- Il faut, autant qu’il est possible, mettre une opération utile dans l’opération qui suit le branchement.
gcc peut se voir demander plusieurs effort d’optimisation (-O). Mais même dans le cas où on lui demande de chercher partout, il n’est pas toujours capable de mettre qqch (25% du temps, il ne peut rien mettre)
Ici, le delayed slot est de 1 : on n’imagine même pas si c’est plus de 1. L’effort demandé au compilateur est encore pire (et impossible à fournir) : pour cette raison, les concepteurs du RISC tenaient à ce que l’adresse de l’instruction à exécuter ensuite soit calculée le plus tôt possible.
On a un autre problème : un moment où une instruction doit consommer une valeur, elle peut ne pas encore avoir été calculée.
On a un délai nécessaire de 3 : c’est au compilateur de s’assurer de ça, sur n’importe quelle fenêtre de 4 instructions : toutes les instructions dans n’importe laquelle de ces fenêtres de 4 instructions doivent être indépendantes deux à deux.
Et ça le compilateur ne peut pas bien le faire.
On va quand même modifier le matériel.
Une idée, c’est de pouvoir bloquer une instruction en cours : injecter des cycles de gel (stall cycle) : pas mieux que la technique des NOP.
ADD $3,$4,$5
ADD $6,$7,$3
Dans cet exemple-là, ce n’est pas exactement de $3 dont on a besoin, mais du résultat de la somme $4+$5, qui est connue 2 cycles avant $3 (à la fin de EXE).
De la même manière, on a vraiment besoin de cette valeur au début de EXE, pas au début de DEC : il suffit de récupérer le contenu de RES_RE et le passer en deuxième opérande de l’opération +.
Donc en fait, le truc dont on a besoin ($4+$5) est disponible pile au moment où on en a besoin (au début de mon EXE, soit à la fin du EXE de mon t-1).
Soit en fait : (même si cette instruction n’existe pas, RES_RE n’étant pas un registre visible du processeur)
ADD $3,$4,$5
ADD $6,$7,$RES_RE
Cette technique s’appelle bypass.
Entre quelle zones peut-on/doit-on mettre des bypass ?
- E@t -> E@t+1
- M@t -> E@t+2
- E@t -> D@t+2
- M@t -> D@t+3
(* 2, car on a deux opérandes)
Idéalement, on aurait une instruction terminée à chaque cycle, soit un CPI de 1.
On distingue trois cas de dépendances de données :
- La dépendance RAW : Read after Write (on écrit ça i1 →RAW i2). Signifie que i1 écrit dans un registre et que i2 lit dans ce registre. Utilisation d’un résultat précédent.
- La dépendance WAW : Write after Write (on écrit ça i1 →WAW i2). Signifie que i1 écrit dans un registre et que i2 écrit dans ce même registre. Réutilisation d’un registre.
- La dépendance WAR : Write after Read (on écrit ça i1 →WAR i2). Signifie que i1 lit dans un registre et que i2 écrit dans ce registre. Réutilisation d’un registre.
Par exemple :
- WAW. L’écriture dans un registre est considérée finie à la fin de l’étage WBK. L’écriture suivante dans le même registre par n’importe quelle instruction future se fera forcément après (à la fin de l’étage WBK de l’instruction en question) :
| IFC | DEC | EXE | MEM | WBK (ici) | |
| IFC | DEC | EXE | MEM | WBK (ici) |
Pas de problème : et à plus forte raison si on considère une instruction située encore plus loin.
- WAR. La lecture des registres opérandes du banc de registre se fait dans l’étage DEC. L’écriture dans un de ces deux registres opérandes du banc de registre par n’importe quelle instruction future se fera forcément après (à la fin de l’étage WBK de l’instruction en question) :
| IFC | DEC (ici) | EXE | MEM | WBK | |
| IFC | DEC | EXE | MEM | WBK (ici) |
Pas de problème : et à plus forte raison si on considère une instruction située encore plus loin.
Par contre, les problèmes d’aléa dans le pipeline arrivent avec la dépendance de données RAW :
On a besoin de lire les registres opérandes du banc de registre au début de l’étage DEC. Or, si l’écriture dans ces registres se fait au WBK de l’instruction précédente, par exemple, ce ne sera pas prêt à temps :
| IFC | DEC | EXE | MEM | WBK (ici) | |
| IFC | (ici) DEC | EXE | MEM | WBK |
Dans l’exemple donné, on a besoin de ce que WBK de l’instruction d’avant produit trois cycles avant qu’il soit effectivement produit.
Il faut trouver une manière d’accélérer la transmission des résultats aux opérandes !
Notion de bypass
On a un nombre limité d’opérations dans le MIPS, regardons chaque opération distinctement :
ALU (Arithmetic and Logical Unit) :
ADD $2, $4, $3
ADDI $5, $2, 10
Dans notre exemple, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage EXE, et on en a besoin au début de l’étage EXE de la seconde instruction (soit au même moment). Un bypass de EXE fin à EXE début règle le problème, et permet d’éviter le cycle de gel :
| IFC | DEC | EXE >-1 | MEM | WBK | |
| IFC | DEC | -> EXE | MEM | WBK |
LOAD :
LW $2, 0($4)
ADDI $5, $2, 10
Dans notre exemple, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage MEM, et on en a besoin au début de l’étage EXE de la seconde instruction (soit un cycle avant). Un bypass de MEM fin à EXE début diminue le problème, et permet de n’avoir à mettre qu’un cycle de gel :
| IFC | DEC | EXE | MEM >-1 | WBK | ||
| IFC | DEC | O | -> EXE | MEM | WBK |
BRANCH :
ADD $2, $4, $3
BEQ $5, $2, loop
Dans notre exemple, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage EXE, et on en a besoin au début de l’étage DEC de la seconde instruction (soit un cycle avant). Un bypass de EXE fin à DEC début diminue le problème, et permet de n’avoir à mettre qu’un cycle de gel :
| IFC | DEC | EXE >-1 | MEM | WBK | ||
| IFC | O | -> DEC | EXE | MEM | WBK |
Deuxième exemple :
LW $2, 0($3)
BEQ $5, $2, loop
Dans notre exemple, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage MEM, et on en a besoin au début de l’étage DEC de la seconde instruction (soit deux cycles avant). Un bypass de MEM fin à DEC début diminue le problème, et permet de n’avoir à mettre que deux cycles de gel :
| IFC | DEC | EXE | MEM >-1 | WBK | |||
| IFC | O | O | -> DEC | EXE | MEM | WBK |
STORE :
ADDI $2, $3, 1
SW $2, 0($4)
Dans notre exemple, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage EXE, et on en a besoin au début de l’étage MEM de l’instruction suivante. On pourrait aussi envisager d’en avoir besoin au début de l’étage EXE de l’instruction suivante :
En effet, les opérations de type STORE consomment l’opérande RS (ici, $4) en EXE (pour calculer l’adresse à laquelle enregistrer), et l’opérande RT (ici $2) en MEM.
On a déjà un bypass de EXE fin à EXE début, donc le cas 2 est réglé.
Pour le cas 1, va-t-on mettre un bypass de EXE fin à MEM début ? Non, pour deux raisons :
- C’est déjà le chemin naturel des données (une donnée passe de EXE fin à MEM début sans avoir besoin de quelque bypass) dans notre cas
- Raison plus générale : MEM est un étage critique (la criticité des étages, en décroissant : MEM, IF, DEC, EXE). On ne peut pas se permettre d’allonger encore la durée de l’étage MEM en y introduisant un bypass en entrée qui supposerait un multiplexeur et le matériel logique qui permettrait de le contrôler.
Pour cette raison, on ne met pas de bypass entrant en MEM : on préfèrera mettre un bypass entrant en EXE, même pour récupérer des données qui ne seront utilisées qu’en MEM.
Dans notre cas, ça n’induit pas de cycle de gel (on est dans le cas d’un bypass EXE fin vers EXE début, vu plus haut).
Mais, si on imagine un autre cas :
LW $2, 0($3)
SW $2, 0($4)
Dans ce cas, on a effectivement produit le résultat de l’opération de la première instruction à la fin de l’étage MEM, et on en a besoin au début de l’étage MEM de la seconde instruction. On pourrait imaginer un bypass qui irait de MEM fin à MEM début, qui permettrait de ne pas avoir à introduire un cycle de gel.
Mais, PAS DE BYPASS ENTRANT EN MEM, pour toutes les raisons données. On doit donc récupérer le résultat de l’opération LW (ici le contenu du registre $2) au début de l’étage EXE.
On se servira donc du bypass déjà vu : MEM fin -> EXE début, ce qui implique un cycle de gel.
Ce qui signifie qu’à un moment, les concepteurs du MIPS ont dû préférer introduire un cycle de gel plutôt que de payer un temps supplémentaire à l’étage MEM. En effet, MEM étant l’étage le plus gourmand en temps, ça aurait augmenté la durée du cycle pour toutes les instructions exécutées par ce processeur.
Prenons l’exemple d’un code C simple :
int a[size];
for (i = 0; i != size; ++i) a[i] = 2*a[i];En code ASM MIPS compilé, ça donne ça :
OR $0, $0, $0
# i dans R8
# size dans R6, a dans R5
XOR $8, $8, $8
BEQ $6, $0, suite
SLL $9, $6, 2 #multiplication par 4
ADD $9, $9, $5
loop:
LW $4, 0($5)
SLL $7, $4, 1 #multiplication par 2
SW $7, 0($5)
ADDIU $5, $5, 4
BNE $9, $5, loop
suite:
Ce code tel quel ne respecte pas notre sémantique dans le MIPS 32, à cause du pipeline.
On doit déjà introduire des delayed slot derrière les branchements :
OR $0, $0, $0
# i dans R8
# size dans R6, a dans R5
XOR $8, $8, $8
BEQ $6, $0, suite
OR $0, $0, $0
SLL $9, $6, 2 #multiplication par 4
ADD $9, $9, $5
loop:
LW $4, 0($5)
SLL $7, $4, 1 #multiplication par 2
SW $7, 0($5)
ADDIU $5, $5, 4
BNE $9, $5, loop
OR $0, $0, $0
suite:
On doit maintenant faire l’analyse de la performance de ce code assembleur. On se propose de faire le schéma simplifié, de manière à repérer les cycles de gel.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| XOR | IFC | DEC | EXE | MEM | WBK | ||||||||||||
| BEQ | IFC | DEC | EXE | MEM | WBK | ||||||||||||
| NOP | IFC | DEC | EXE | MEM | WBK | ||||||||||||
| SLL | IFC | DEC | EXE >-1 | MEM | WBK | ||||||||||||
| ADD | IFC | DEC | -> EXE | MEM | WBK | ||||||||||||
| LW | IFC | DEC | EXE | MEM >-1 | WBK | ||||||||||||
| SLL | IFC | DEC | GEL | -> EXE >-1 | MEM | WBK | |||||||||||
| SW | IFC | GEL | DEC | -> EXE | MEM | WBK | |||||||||||
| ADDIU | GEL | IFC | DEC | EXE >-1 | MEM | WBK | |||||||||||
| BNE | IFC | GEL | -> DEC | EXE | MEM | WBK | |||||||||||
| NOP | IFC | DEC | EXE | MEM | WBK |
Le CPI de cette suite d’instructions :
#Cycles = 17 - 5 = 12 #Instructions = 11 #Instructions_utiles = 9
CPI = 12/11 CPIutile = 12/9
2 cycles de gel. On peut sûrement faire mieux en changeant l’ordre des instructions (en veillant toutefois à ne pas changer la sémantique du programme).
Dans notre exemple, à quoi cette optimisation pourrait-elle ressembler ?
On décide de ne considérer que la boucle :
loop:
LW $4, 0($5)
SLL $7, $4, 1 #multiplication par 2
SW $7, 0($5)
ADDIU $5, $5, 4
BNE $9, $5, loop
OR $0, $0, $0
On rappelle :
- Un cycle de gel entre le LW et le SLL
- Un cycle de gel entre le ADDIU et le BNE
- Un NOP après le BNE, inutile
Le ADDIU incrémente $5 d’un pas constant : on peut faire remonter ADDIU avant SW sssi on corrige la modification qu’on fait sur $5 par l’offset de SW (-4 au lieu de 0).
Le ADDIU peut donc être remonté à la deuxième position, ce qui fait d’une pierre deux coups :
- On supprime le cycle de gel de SLL.
- On supprime le cycle de gel de BNE.
loop:
lw $4, 0($5)
addiu $5, $5, 4
sll $7, $4, 1 #multiplication par 2
sw $7, -4($5)
bne $9, $5, loop
or $0, $0, $0
On respecte bien toutes les dépendances.
On peut maintenant mettre SW à la place du NOP, ce qui supprime l’instruction NOP :
loop:
lw $4, 0($5)
addiu $5, $5, 4
sll $7, $4, 1 #multiplication par 2
bne $9, $5, loop
sw $7, -4($5)
On a bien 0 cycles de gel et 0 instructions NOP.
Dans ce cycle de boucle en assembleur MIPS, on a deux instructions qui gèrent la boucle, et 3 instructions pour le corps. On a potentiellement moyen d’améliorer tout ça.
Mécaniquement, dérouler une boucle permet de diluer le coût de la gestion de la boucle (le coût en instructions assembleur d’une gestion de la boucle est constante), mais a aussi un autre avantage : le corps de la boucle devenant plus gros, on a plus d’opportunités de réordonnancement.
Les problèmes liés au déroulage de boucle sont les suivants :
- Le segment de texte des processus va exploser. Pas un problème en soi (la mémoire ne coûte plus rien), mais peut devenir un problème pour le cache d’instructions (le IFC ne coûteront plus 0, il faudra faire des accès mémoire plus souvent que jamais : pourvu qu’on ne soit pas un prolo en cache, dans les processeurs modernes pour les codes pas trop gros, on peut quand même partir du principe qu’une grosse partie voir tout le texte du programme tient dans le cache : les IFC coûtent donc 0. Si on déroule le code, c’est moins possible)
- Le renommage des registres peut poser problème : si on regarde notre boucle déroulée, on a eu besoin de plus de registres différents. On n’a qu’un certain nombre de registres disponible.
Mais dans les faits, les compilateurs abusent du déroulement de boucle, surtout quand la taille de la boucle est statique : ne permet pas d’économiser des accès mémoire en écriture, ni même de les bien grouper (on n’a qu’un nombre limité de registres), suppose une légère augmentation des défauts de cache instruction, mais permet de virtuellement supprimer le coût des gestions de boucle (qui est somme toute minime, rappelons-le)
Essayons de dérouler la boucle :
à haut niveau :
for (i = 0; i + 1 < N; i+=2) {
tab[i] = tab[i] * 2;
tab[i+1] = tab[i+1] * 2;
}
for (; i < N; i++) {
tab[i] = tab[i] * 2;
}à bas niveau (en repartant de la boucle non encore optimisée) :
loop:
lw $4, 0($5)
sll $7, $4, 1 #multiplication par 2
sw $7, 0($5)
lw $14, 4($5)
sll $17, $14, 1
sw $17, 4($5)
addiu $5, $5, 4
bne $9, $5, loop
or $0, $0, $0
Dans notre cas, on a seulement 2 instructions de gestion de boucle (on ne compte pas le NOP qui sera supprimé dans la suite) pour 6 et non plus 3 instructions de corps.
Dans cette version non encore optimisée, on a en revanche 3 cycles de gel et 1 instruction NOP.
De la même manière qu’avant, on peut supprimer les cycles et le NOP en réordonnançant. Sauf que cette fois, on a plus d’ordonnancement possibles, puisque le corps de la boucle est plus grand.
On doit prendre bien garde à respecter les dépendances :
loop:
lw $4, 0($5)
lw $14, 4($5)
sll $7, $4, 1 #multiplication par 2
sll $17, $14, 1
addiu $5, $5, 8
sw $7, -8($5)
bne $9, $5, loop
sw $17, -4($5)
On a bien 0 cycles de gel, et 0 instructions NOP.
On a 6 instructions de corps et 2 instructions de gestion de boucle : meilleur rapport.
Toutes ces techniques font bien mal à la tête ! On doit se donner un certain nombre d’outils théoriques qui permettront de formaliser correctement les possibilités d’optimisation, de manière à en évaluer leurs bénéfices et leur possibilité. (si on fait ça correctement, on pourra implémenter ces formalismes dans le compilateur, pour qu’il fasse les optimisations à notre place)
Si on prend un exemple un peu plus complexe :
loop:
lw $8, 0($5)
bgez $8, endif
nop
sub $9, $0, $8
sw $9, 0($5)
endif:
addiu $5, $5, 4
bne $7, $5, loop
nop
Dans notre cas, on a un branchement dans la boucle à l’instruction bgez (cas fréquent, traduit un simple if).
Quels problèmes pour l’ordonnancement et pour le déroulage de boucle ?
Il faut un des outils théoriques qui permettent de systématiser les réponses à cette question.
Si on reprend notre exemple :
#BB1
loop:
lw $8, 0($5)
bgez $8, endif
nop
#BB2
sub $9, $0, $8
sw $9, 0($5)
#BB3
endif:
addiu $5, $5, 4
bne $7, $5, loop
nop
L’ordonnancement doit prendre bien garde au flot de contrôle : on ne peut pas forcément bouger une instruction d’un bloc de base à un autre.
En revanche :
Dans le cas où on a plusieurs blocs de base, on doit faire plus attention aux arcs.
| BB1 | >-1 |
|---|---|
| V | |
| BB2 | |
| V | |
| BB3 | <-1 |
Dans notre exemple :
- BB1 et BB3 sont toujours exécutés : on peut bouger des instructions de BB1 vers BB3 et vice versa, pourvu qu’on respecte les dépendances.
- BB2 n’est pas forcément exécuté : on ne peut pas mettre une instruction de BB1 dans BB2, ni remonter une instruction de BB3 de BB2
- On peut bouger des instructions dans BB2 (suit de la définition du bloc de base), et on peut éventuellement descendre des instructions de BB2 vers BB3, si on ne change pas la sémantique d’une itération.
Et comment fait-on quand on veut dérouler la boucle ?
#BB1
loop:
lw $8, 0($5)
bgez $8, endif
nop
#BB2
sub $9, $0, $8
sw $9, 0($5)
#BB1'
lw $18, 4($5)
bgez $18, endif
nop
#BB2'
sub $19, $0, $8
sw $9, 4($5)
#BB3
endif:
addiu $5, $5, 4
bne $7, $5, loop
nop
On a bien réécrit les blocs de contrôle.
On redessine le graphe :
| BB1 | >-1,2 |
|---|---|
| V | |
| BB2 | |
| V | |
| BB1’ | <-2, >-3 |
| V | |
| BB2’ | |
| V | |
| BB3 | <-1,3 |
On ne sépare pas un branchement interne de ses blocs successeurs.
On doit aussi faire attention à une dernière chose :
- Les instructions du corps de la boucle doivent être indépendantes les unes des autres, maintenant que leur indépendance n’est plus garantie par la boucle elle-même.
- On doit faire particulièrement aux modifications en avance.
En fait, le déroulage de boucle généralise la notion de “pipeline” : on traite des instructions de corps boucle à la pipeline : le traitement de la prochaine instruction de corps de boucle n’attend pas la prochaine itération de la boucle pour s’exécuter.
Quelques rappels avant de voir la prochaine grande innovation des processeurs.
On a fondamentalement deux manières d’augmenter la performance, c’est d’augmenter la fréquence ou de diminuer le CPI.
L’idée du pipeline suit de la volonté d’augmenter la fréquence des processeurs. Les adaptations qu’on a vu en terme de bypass sont là pour préserver un CPI proche de 1.
On peut augmenter le fréquence, donc la performance en multipliant les étages de pipeline.
C’est l’invention du superpipeline.
Mais comme on l’a vu avec le résultat plus haut, plus le pipeline est profond, plus on augmente le problème de la dépendance des données (celui-ci augmente linéairement en N le nombre d’étages du pipeline).
Augmenter le nombre de bypass n’est pas une solution miracle, car les bypass supposent un multiplexeur pour l’étage qui a le bypass en entrée, ce qui va avoir tendance à augmenter la durée du cycle, donc baisser la fréquence.
Autre problème, on augmente la quantité de delayed slots (CPI/CPI utile augmente) : si on dit que le décodage de l’adresse suivante se fait à la fin de l’étage N, on a N-1 delayed slots. (Déjà moins grave : on peut quand même partir du principe que l’étage DEC restera quoi qu’il en soit très près du début).
Si on interdit à l’utilisateur, donc au compilateur, de produire des branchements (pas de if ni de while autorisé), alors on peut se permettre de créer des processeurs avec beaucoup beaucoup d’étages de pipeline, qui seront efficaces pour le traitement des données peu dépendantes les unes des autres (typiquement, le calcul matriciel).
Le supercalculateur CRAY-2, de la fin des années 80 (1985).
On voit que les manières d’augmenter la fréquence en augmentant le nombre d’étages de pipeline posent presque autant de problème qu’elles en résolvent, et que les problèmes posés par cette solution n’augmentent pas de manière linéaire : à titre d’exemple, si un compilateur est assez capable de trouver une instruction à caser dans le delayed slot unique (75% du temps), ça devient beaucoup plus difficile avec 2 delayed slots (5%) et encore davantage avec 3 (0%).
Comment régler le problème donc ? Si on veut pouvoir continuer à augmenter la performance, mais que l’augmentation artificielle de la fréquence par le pipeline n’est pas assez rentable, il faut diminuer le CPI en dessous de ce qui était jusque là sa limite théorique : 1.
Autrement dit, il faut exécuter plusieurs instructions par cycle : invention des processus superscalaires, qui ont commencé à dominer dans les années 90. Les processeurs utilisés dans les machines modernes sont des processus superscalaires un peu particuliers (on le verra plus tard).
L’idée d’avoir plusieurs pipeline n’est pas spécifique aux processeurs superscalaires. On sait que certaines opérations sont plus longues que d’autres : certains opérateurs comme l’addition, le shift, la comparaison bit à bit ont un temps de calcul logarithmique en le nombre de bits sur lequel ils sont appliqués, et certains autres (comme la multiplication) ne le sont pas du tout.
La manière naïve de faire une multiplication de deux nombres écrits sur 32 bits chacun est la manière de multiplier qu’on a appris à l’école : on fait les multiplications chiffre par chiffre (ici, bit à bit), puis on additionne le résultat des multiplications. On a au maximum 31 additions.
Un certain nombre d’algorithmes plus intelligents arrivent à faire ces multiplications en 3 additions plutôt qu’en 31. La multiplication reste quand même trois fois plus longue qu’une opération faite par l’unité logique et arithmétique.
On peut donc caser la multiplication à la places des 3 derniers étages du pipeline, en parallèle de ceux-ci.
De la même manière que pour traiter la multiplication, on pourrait parfaitement doubler le pipeline d’exécution (E, M et W) pour en faire deux pipelines indépendants.
Le cycle D devra donc décoder deux instructions à la fois.
Le cycle I doit maintenant alimenter le cycle decode avec deux instructions
La mémoire doit donc être capable de donner non pas 1, mais 2 instructions à la fois.
On rappelle que les instructions doivent être alignées, autrement dit que leurs adresses en octets doivent être divisibles par la taille en octets du mot d’instruction mémoire.
Ce qui suppose plusieurs choses :
- La largeur du bus CPU-mémoire centrale doit être doublée.
- Si on ne tient pas à mettre deux accès mémoire indépendants (ce qui coûte très cher), alors on doit demander au processeur de fetch deux mots d’instruction contigus d’un coup (les deux instructions pourront passer par le bus, mais ce sera toujours un seul bus, avec un seul contrôleur mémoire). Or, les mots d’instruction doivent être alignés (Adresses en octets divisibles par la taille du mot mémoire). L’adresse des couples d’instruction qu’on va demander à chercher devra donc être divisible par le double de la taille du mot mémoire. Si on veut que cette condition soit toujours respectée, on doit forcément :
– Chercher toujours 2 mots d’instruction d’un coup – Ne jamais aller rechercher un mot d’instruction qu’on a déjà cherché avant (parmi les N qu’on va chercher) (donc ne jamais discard un mot d’instruction, à moins d’être sûr de ne point avoir envie de l’exécuter)
Or, si les deux instructions passées chacune dans un des deux pipeline parallèle, il est parfaitement possible de ne pas pouvoir en exécuter une des deux (problème de dépendance). Or, d’après ce qu’on vient d’établir, on ne peut pas juste discard une instruction simplement parce qu’on ne peut pas l’exécuter : il faut être sûr de ne pas avoir envie du tout de l’exécuter, en raison par exemple d’un branchement conditionné ou non. Si on ne peut pas discard, il faut garder cette instruction non exécutée qqpart.
Cet endroit, c’est le tampon d’instructions (instruction buffer).
En fait, quand le matériel de l’étage IFC cherche deux mots d’instruction dans la mémoire, il place des deux mots d’instruction dans le tampon d’instruction, tampon dans lequel le matériel de l’étage DEC vient puiser une ou deux instructions (selon s’il peut en exécuter une ou deux).
C’est la raison pour laquelle le tampon d’instruction peut tenir 4 instructions dans un processeur superscalaire à deux pipelines.
Rappels sur les bypass existant :
- E fin vers E début
- M fin vers E début
- E fin vers D début
- M fin vers D début
Donc 4 bypass par opérande sur un pipeline simple.
Si on imagine un superscalaire à deux pipelines, on doit potentiellement avoir deux 4^2 pipelines :
- Les 4 bypass de pipeline 1 vers pipeline 1
- Les 4 bypass de pipeline 1 vers pipeline 2
- Les 4 bypass de pipeline 2 vers pipeline 2
- Les 4 bypass de pipeline 2 vers pipeline 1
Dans le cas d’un processus superscalaire à deux pipelines, on a donc 16 bypass par opérande, donc 32 en tout.
Prenons un exemple au tableau, reproduit ici :
for:
lw $6,0($4)
sll $6,$6,1
sw $6,0($4)
addiu $4,$4,4
bne $4,$9,for
nop
Faisons passer cette suite d’instructions dans un superscalaire à 2 pipelines, en faisant apparaître le contenu du tampon d’instructions.
| IB@endI | Inst | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| lw | E | M | W | |||||||||||
| lw,sll | I | D | ||||||||||||
| nop* | E | M | W | |||||||||||
| sll | 0 | E | M | W | ||||||||||
| sll,sw | I | D | ||||||||||||
| addiu | nop* | 0 | E | M | W | |||||||||
| sw | E | M | W | |||||||||||
| sw,addiu | I | 0 | D | |||||||||||
| bne,nop | addiu | E | M | W | ||||||||||
| bne | E | M | W | |||||||||||
| bne,nop | 0 | I | 0 | D | ||||||||||
| x,y | nop | E | M | W | ||||||||||
| nop* | E | M | W | |||||||||||
| x,y | I | D | ||||||||||||
| x1,y1 | nop* | E | M | W | ||||||||||
| lw,sll | I | |||||||||||||
Le calcul du CPI et du CPI utile :
Dans notre exemple, la première instruction effective qui ne fait pas partie de notre segment étudié (une itération particulière de la boucle) rentre dans le pipeline au cycle 8. La première instruction de notre segment rentre dans le pipeline au cycle 1. On a donc bien 7 cycles.
On compte 6 instructions (attention, les nop* ne sont pas des instructions, mais des opérations, et ne comptent donc pas dans ce total), dont 5 utiles. Le CPI est donc de 7/6 et le CPI utile de 7/5. Ce n’est pas beaucoup mieux qu’un processeur pipeliné classique : ce processeur est particulièrement sensible aux branchements, comme on va le voir.
Les opérations à mettre dans les différents pipelines ne sont en fait connues qu’à la fin de l’étage decode. Le matériel de l’étage decode regarde les deux premières instructions du tampon d’instruction, décide s’il peut mettre les deux dans le pipeline. S’il ne peut pas, il ne met que la première, et il met une opération nop* dans le deuxième pipeline parallèle.
Dans le cas spécifique d’un branchement, les 4 instructions du tampon d’instructions ne sont potentiellement plus les bonnes (décidé à la fin de l’étage decode de l’instruction de branchement). Il faut flush le tampon d’instructions. Or on sait que le tampon d’instructions doit être flush quand celui-ci est déjà plein de 4 instructions qu’on ne veut pas exécuter. C’est donc à l’instruction d’après seulement que des instructions à exécuter rentrent effectivement dans le tampon d’instruction.
On a donc, après un branchement réussi (si le branchement échoue, les instructions séquentielles sont valables), toujours une instruction inutile.
Ce type de processeur étant particulièrement sensible aux branchements (flush du tampon d’instruction obligatoire en cas de branchement réussi), on a intérêt à dérouler les boucles.
Réessayons avec deux itérations d’un coup.
for:
lw $8,0($4)
lw $10,4($4)
addiu $4,$4,8
sll $8,$8,1
sll $10,$10,1
sw $8,-8($4)
bne $4,$5,for
sw $10,-4($4)
Cet exemple est déjà optimisé : on s’est permis de réordonnancer :
| IB@endI | Inst | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| lw | E | M | W | |||||||||||
| lw,lw | I | D | ||||||||||||
| lw | E | M | W | |||||||||||
| addiu | E | M | W | |||||||||||
| addiu | I | D | ||||||||||||
| sll | sll | 0 | E | M | W | |||||||||
| sll | E | M | W | |||||||||||
| sll | I | D | ||||||||||||
| sw | nop* | E | M | W | ||||||||||
| sw | E | M | W | |||||||||||
| sw,bne | I | D | ||||||||||||
| sw | bne | E | M | W | ||||||||||
| sw | E | M | W | |||||||||||
| sw | I | D | ||||||||||||
| x,y | nop* | E | M | W | ||||||||||
| nop* | E | M | W | |||||||||||
| I | D | |||||||||||||
| nop* | E | M | W | |||||||||||
| lw,lw | I | |||||||||||||
Calcul du CPI et du CPI utile :
Nombre de cycles pour le segment concerné : La première instruction effective après notre segment rentre dans le pipeline au cycle 7 La première instruction effective de notre segment rentre dans le pipeline au cycle 1
Notre segment prend donc 6 cycles pour s’exécuter. On a 8 instructions, dont 8 instructions utiles, le CPI égale donc le CPI utile égale 0.75
[Vérifions quand même cette histoire de comptage des nop*]
On voit que le déroulage de boucle, parce qu’il permet de rendre le coût fixe d’une instruction perdue après les branchements réussis petit devant le coût total de la boucle déroulée, permet de bien exploiter les possibilités du superscalaire.
D’un autre côté, ce déroulage est nécessaire : avec la possibilité de faire passer deux instructions d’un coup dans le pipeline, les instructions se “rapprochent” les unes des autres, rendant les problèmes de dépendance plus aigus.
Un autre problème survient avec l’étage M : autant dans l’étage I, vu qu’on savait qu’on allait chercher N mots d’instructions contigus d’un coup, on pouvait se contenter de simplement élargir la nappe de fils qui devaient aller chercher les instructions, sans avoir besoin d’augmenter le nombre de contrôleurs mémoire.
Mais en ce qui concerne les lectures et les écritures dans la mémoire faites à l’étage M, on n’a aucune garantie que 2 écritures simultanées se fassent dans des octets/demi-mots/mots contigus (ni même que les écritures soient de la même taille, à dire vrai). On a donc deux solutions :
- Interdire deux écritures/lectures mémoire simultanées, ce qui implique soit d’arranger les instructions d’accès mémoire de manière à ce qu’elles ne soient pas dans le même N-uplet de mots d’instructions (de plus en plus complexe avec N augmentant), soit d’introduire des cycles de gel (jusqu’à N-1 dans le pire des cas), ce qui diminue grandement l’intérêt du superscalaire.
- Ajouter N contrôleurs à la mémoire de données, ce qui coûte extrêmement cher.
Suite du premier cours de Karine : Rappels de déroulage de boucle, et introduction au pipeline logiciel.
Prenons une boucle simple :
loop:
lw $4,0($5)
sll $7,$4,1
sw $7,0($5)
addiu $5,$5,4
bne $5,$9,loop
nop
Cette boucle lit 4 octets de mémoire dans un de ses registres, multiplie la quantité lue par deux, et réécrit le quantité modifiée à la même adresse.
Il incrémente ensuite l’adresse de 4 octets, vérifie qu’on n’est pas past-the-end dans la boucle, et reprend son exécution au début de celle-ci.
Dans cette boucle, le premier bloc de trois instructions constitue véritablement le corps de la boucle. Appelons-les i1, i2 et i3.
Les dépendances dans le corps de la boucle sont les suivantes :
- RAW de i2 vers i1, pour $4
- RAW de i3 vers i2, pour $7
Si on considère la prochaine itération de la boucle, on a aussi :
- WAR de i1(i+1) vers i2(i), pour $4
- WAR de i2(i+1) vers i3(i), pour $7
Ce sont les seules quatre dépendances qui concernent le corps de la boucle. Quand on arrange les instructions entre elles sur plusieurs itérations, on doit seulement prendre garde à garder les ordres suivants si on veut garder la sémantique en général :
- i1(i) -> i2(i)
- i2(i) -> i3(i)
- i2(i) -> i1(i+1)
- i3(i) -> i2(i+1)
Le déroulage de boucle suppose le renommage de certains registres. Si on y pense bien, les dépendances WAR peuvent assez facilement être supprimées en se contentant d’écrire dans un autre registre que celui dans lequel on lisait avant. C’est le principe du déroulage de boucle qu’on a vu il y a deux semaines.
Sans renommer de registres, et donc en respectant les dépendances WAR (les deux dernières de notre liste), on peut quand même dérouler la boucle.
Sur 5 itérations, (i = 0; i < 5; ++i), ça donne :
i1(0) i2(0) i1(1)
i3(0) i2(1) i1(2)
i3(1) i2(2) i1(3)
i3(2) i2(3) i1(4)
i3(3) i2(4) i1(4)
Pour les trois blocs non-extrêmes, on s’aperçoit qu’on a le même motif :
i3(i-2) i2(i-1) i1(i)
Puisque le motif est constant, on peut simplement reformer une nouvelle boucle !
Cette idée suppose en revanche une hypothèse très forte : les itérations doivent être indépendantes. L’opération d’intérêt (ici, la multiplication par une constante) ne doit pas dépendre des valeurs des itérations précédentes et suivantes. Par exemple, une moyenne mobile du style a[i] = 0.25a[i-1] + 0.5a[i] + 0.25a[i+1] ne fonctionnera pas bien.
Admettons qu’on puisse découper l’exécution en N étapes. On peut commencer l’étape M de l’itération i quand l’itération i-1 l’a terminée. Mais il faut aussi que les ressources nécessaires à l’étape M (les registres utilisés) aient été libérés : sinon, on écrase des valeurs pour l’itération i-1. En fait, il faut que les valeurs que l’itération i-1 a mis dans ces registres de fin d’étape M aient été traitées ou copiées ailleurs. Autrement dit, il faut que l’itération i-1 ait fini l’étape M+1.
On peut donc lancer l’étape M de l’itération i juste après l’étape M+1 de l’itération i-1 :
On voit qu’on a un motif qui se répète, comme dans notre exemple plus haut.
Le motif est le suivant :
E6(i-5) E5(i-4) E4(i-3) E3(i-2) E2(i-1) E1(i)
La boucle ordonnance une étape de N itérations successives (N étant le nombre d’étapes du pipeline logiciel).
Pour le début et la fin, on doit quand même remplir et vider le pipeline.
Prenons une boucle.
On a l’adresse mémoire a + i dans $6, et l’adresse mémoire a + N (past the end) en $10.
loop:
lw $4,0($6)
sll $5,$4,1
sw $5,0($6)
addiu $6,$6,4
bne $10;$6,loop
Première étape : Déterminons dans la boucle ce qui fait partie du corps, et ce qui fait partie du contrôle de boucle en lui-même.
Le corps de la boucle consiste en les trois premières instructions, le contrôle en les deux dernières.
Analysons ensuite les dépendances (dépendantes de l’architecture) dans le corps de la boucle, et par rapport à la prochaine itération. (on suppose ici un MIPS à 5 étages)
- RAW de i2 vers i1 pour $4
- RAW de i3 vers i2 pour $5
- WAR de i1(i+1) vers i2(i) pour $4
- WAR de i2(i+1) vers i3(i) pour $5
Cycles perdus (dépend aussi de l’architecture, on continue à supposer un MIPS à 5 étages) :
- 1 cycle de gel entre i1 et i2 (on doit attendre la fin de M de i1 pour commencer E de i2)
C’est tout !
On coupe ensuite où il y a des cycles de gel, des dépendances, des limitations de performance. Dans notre cas, on va découper partout dans le corps de la boucle.
E1 : lw $4,0($6) E2 : sll $5,$4,1 E3 : sw $5,0($6)
Le corps de la nouvelle boucle sera constitué de :
E3(i-2) : sw $5,?($6) E2(i-1) : sll $5,$4,1 E1(i) : lw $4, ?($6)
On a besoin de modifier les adresses de lecture et d’écriture pour tenir compte du fait qu’on manipule plusieurs itérations de la boucle originale d’un coup.
Les instructions de contrôle de la boucle sont quand même exécutées à chaque itération, en particulier l’incrémentation de 4 de l’adresse.
Le corps de la nouvelle boucle, avec les adresses corrigées, sera donc :
E3(i-2) : sw $5,-8($6) E2(i-1) : sll $5,$4,1 E1(i) : lw $4,0($6)
On met la gestion de boucle, autant entre les itérations, qu’au début et à la fin de celles-ci.
On doit s’arrêter au bon moment : on ne doit pas faire de lecture d’adresses past the end.
La nouvelle boucle se fait sur la range suivante : (i = 2; i < N; ++i) (ou alors (i = 0 ; i < N-2; ++i), comme vous voulez, la variable d’itération est muette)
On doit donc ajouter au début : E1(0), E2(0), E1(1)
Et à la fin : E3(N-2), E2(N-1), E3(N-1)
Ce qui donne, en brut non optimisé :
remplissage:
lw $4,0($6) # Le remplissage du pipeline logiciel
sll $5,$4,1
lw $4,4($6)
addiu $6,$6,8 # On commence la boucle à i = 2
loop:
sw $5,-8($6)
sll $5,$4,1
lw $4,0($6)
addiu $6,$6,4
bne $6,$10,loop
nop
vidage:
sw $5,-8($6) # Le vidage du pipeline logiciel
sll $5,$4,1
sw $5,-4($6)
On a :
- 1 cycle de gel entre lw et sll, lignes 2 et 3
- 1 cycle de gel entre addiu et bne, lignes 12 et 13
- Un nop après bne, ligne 14
Optimisation :
- On peut faire remonter le addiu de la ligne 6, qui fait l’initialisation de la bonne adresse avant le début de la boucle du pipeline logiciel, entre le lw et le sll des lignes 2 à 3. Attention, cette opération requiert de changer l’immédiat de l’opération lw de la ligne de 4, de 4 à -4.
On se débarasse d’un cycle de gel.
- On peut faire passer le lw de la ligne 9 à la place du nop de la ligne 13. Attention, cette opération requiert de changer l’immédiat de l’opération lw de 0 à -4.
On se débarasse ainsi de l’opération nop
- On peut remonter l’instruction addiu ou bien entre sw et sll, ou bien même avant sw. Si on choisit cette deuxième manière, on doit changer l’immédiat de la l’opération sw, qui doit passer de -8 à -12.
De cette manière, on supprime le cycle de gel entre addiu et bne.
Ce qui donne :
remplissage:
lw $4,0($6) # Le remplissage du pipeline logiciel
addiu $6,$6,8 # On commence la boucle à i = 2
sll $5,$4,1
lw $4,-4($6)
loop:
sw $5,-8($6)
addiu $6,$6,4
sll $5,$4,1
bne $6,$10,loop
lw $4,-4($6)
vidage:
sw $5,-8($6) # Le vidage du pipeline logiciel
sll $5,$4,1
sw $5,-4($6)
De cette manière, sur le corps de la boucle (label “loop”), on a un CPI égale au CPI utile, égale à 1.
loop:
lw $4,0($6)
sll $5,$4,1 # val * 2
add $5,$5,$4 # val = val * 2 + val, soit val * 3
sw $5,0($6)
addiu $6,$6,4 # Contrôle de boucle
bne $10,$6,loop
nop
Analyse du corps :
- RAW de sll à lw, pour $4 (1 cycle de gel)
- RAW de add à sll pour $5
- RAW de sw à add pour $5
Plus le cycle de gel entre addiu et bne, qui ne concerne pas le corps mais le contrôle.
On se propose de simplement découper le corps en 4 étapes.
La boucle pipelinée, avec son remplissage, et son vidage, mais brute :
remplissage:
lw $4,0($6)
sll $4,$4,1
add $5,$5,$4
lw $4,4($6)
sll $4,$4,1
lw $4,8($6)
addiu $6,$6,12 # On initialise i à 3
loop:
sw $5,-12($6)
add $5,$5,$4 # Erreur ici : On est en train d'ajouter a[i-1] à 2a[i]
sll $4,$4,1
lw $4,0($6)
addiu $6,$6,4
bne $6,$10,loop
nop
vidage:
sw $5,-12($6) # E4(N-3)
add $5,$5,$4 # E3(N-2)
sw $5,-8($6) # E4(N-2)
sll $4,$4,1 # E2(N-1)
add $5,$5,$4 # E3(N-1)
sw $5,-4($6) # E4(N-1)
On voit tout de suite que la boucle est vérolée :
On ajoute a[i-1] à 2a[i] dans le registre $5, alors qu’on veut ajouter a[i] à 2a[i].
E1 produit $4 utilisé en E2 et E3 E2 produit $5 utilisé en E3 E3 utilise $5 et $4 et produit $5 pour E4
Le problème vient de ce qu’un étage produit des registres pour plusieurs autres étages à la fois, et donc de ce qu’un étage utilise un registre qui doit être utilisé par un autre. Certains registres sont écrasés avant d’être utilisés par tous les étages qui voulaient s’en servir.
On va donc rectifier notre boucle, en allant de E1 vers E4 (donc du bas vers le haut) :
remplissage:
lw $4,0($6) # E1(0)
sll $5,$4,1 # E2(0)
ori $9,$4,0
lw $4,4($6) # E1(1)
add $7,$5,$9 # E3(0)
sll $5,$4,1 # E2(1)
ori $9,$4,0
lw $4,8($6) # E1(2)
addiu $6,$6,12 # On initialise i à 3
loop:
sw $7,-12($6)
add $7,$5,$9
ori $9,$4,0
sll $5,$4,1
lw $4,0($6)
addiu $6,$6,4
bne $6,$10,loop
nop
vidage:
sw $7,-12($6) # E4(N-3)
add $7,$5,$9 # E3(N-2)
ori $9,$4,0 # E2(N-1)
sll $5,$4,1
sw $7,-8($6) # E4(N-2)
add $7,$5,$9 # E3(N-1)
sw $7,-4($6) # E4(N-1)
On a du rajouter une instruction de transmission pure. On renomme le remplissage et le vidage du pipeline exactement comme on a renommé le corps de la boucle pipelinée.
On pourrait s’amuser à optimiser cette série d’instructions, mais ce n’est pas l’objet ici.
Les choses se compliquent encore quand on rajoute des dépendances de contrôle dans la boucle à dérouler.
Deux exemples :
loop:
lw $3,0($4)
bgez $3,suite
nop
sub $3,$0,$3
sw $3,0($4)
suite:
addiu $4,$4,4
bne $4,$10,loop
nop
loop:
lw $3,0($4)
bgez $3,else
nop
addi $3,$3,-1
j suite
else:
addi $3,$3,1
suite:
sw $3,0($4)
addiu $4,$4,4
bne $4,$10,loop
nop
On s’entraîne à définir les blocs de base des deux exemples précédents.
Exemple 1 :
- 1 en-tête avant lw (début)
- 1 en-tête après nop (post-branchement)
- 1 en-tête avant addiu (cible d’un branchement)
Exemple 2 :
- 1 en-tête avant lw (début)
- 1 en-tête après nop (post-branchement)
- 1 en-tête avant le deuxième addi (cible d’un branchement)
- 1 en-tête avant sw (cible d’un branchement)
A partir de ces blocs de base, on peut dessiner le diagramme de flot de contrôle :
Diagramme de flot de contrôle 1
Où peut-on couper l’itération ?
Donc, on ne pourra couper que de cette manière-là (on ne pourra pas découper dans les carrés en pointillé, mais uniquement entre le contenu du carré d’une part, et qqch en dehors de celui-ci, d’autre part) :
Diagramme de flot de contrôle découpé
Pour résumer, quand on veut optimiser une boucle, on peut appliquer le principe du pipeline logiciel, qui fonctionne selon la même idée que le pipeline matériel : on n’a pas besoin d’attendre qu’une instruction soit terminée pour lancer la suivante. Les mêmes contraintes cependant doivent être respectées.
Le principal intérêt est qu’on renomme moins de registres que le simple déroulage de boucle, qu’on se débarrasse des dépendances RAW, et donc des cycles de gel qui s’ensuivent, au prix minime de davantage de dépendances WAR, et aussi et surtout qu’on recomprime la taille du segment de texte du processus, ce qui est excellent pour la performance du cache.
Les règles à retenir :
On ne considère que le corps de la boucle, pas les instructions de contrôle de la boucle.
On ne sépare jamais les instructions dépendantes d’un branchement de ce branchement dont elles dépendent.
On coupe là où il y a des pertes de performance liées à des dépendances RAW et des cycles de gel.
On vérifie que, comme dans le pipeline matériel :
- Chaque étage produit dans un registre différent
- Chaque étage consomme exactement du registre produit par l’étage d’avant, et produit exactement dans un unique registre, consommé uniquement par l’étage d’après : si besoin, on rajoute des instructions de transfert dans un registre libre à l’intérieur de l’étape.
Pour que cette condition soit respectée, on peut aussi revoir le découpage : dans notre exemple plus haut, laisser :
sll $5,$4,1
add $5,$5,$4
ensemble dans un même étage permet de respecter automatiquement la condition. Cet étage est une boîte noire, qui ne lit qu’un seul registre, $4, et qui n’en produit qu’un seul, $5, le second étant le triple du premier.
En plus, dans ce cas, on n’avait même pas de cycle de gel qui justifiât un découpage.
Découper entre ces deux instructions nous a forcé à rajouter une instruction de copie de registre, ce qui est dommageable pour les performances. Si on ne coupait pas, on se trouvait avec une boucle de pipeline plus courte d’une instruction, sans davantage de cycles de gel ou de nop.
Le pipeline logiciel, contrairement au pipeline matériel, est flexible sur le nombre d’étages en lequel il est découpé. Autant on ne peut pas redécouper un pipeline MIPS à la volée quand ça nous arrange, selon les instructions du moment, autant on peut le faire avec un pipeline logiciel, pourvu que les conditions mentionnées plus haut soient respectées. Utilisons cette flexibilité à notre avantage, soyons économes sur les découpages là où nous pouvons nous le permettre.
Ce cours commence la partie sur la hiérarchie mémoire qui durera jusqu’à la fin du cours.
Les deux composants essentiels d’un ordinateur sont le processeur central et la mémoire centrale.
Au fur et à mesure qu’on rend les processeurs de plus en plus puissants avec les innovations qu’on a vu pendant la première partie les contraintes posées par le processeur sur la mémoire sont de plus en plus fortes.
Les contraintes posées par le processeur sur la mémoire :
- 1 ou 2 accès par cycle
- temps de cycle de la mémoire = temps de cycle du processeur
- On veut un espace d’adressage de 4Go * le nombre de processus dans la machine (mémoire large)
- Coût raisonnable
Il n’existe pas, à ce jour, de mémoire qui respecte ces quatre conditions à la fois. On peut en revanche concevoir plusieurs types de mémoire qui respectent chacun un sous-ensemble de ces contraintes.
La mémoire statique respecte la première et la deuxième condition : elle est d’accès très rapide.
Ce matériel est fabriqué en silicium. Il ressemble un peu aux registres du processeur, il est d’ailleurs fabriqué avec les mêmes technologies.
Par contre, coûte cher : 6 transistors par bit.
Si on essaie de faire une mémoire pas chère avec cette technologie, on a à peine quelque Ko à quelques Mo.
Un autre mémoire, c’est la mémoire dynamique : 3-10 cycles par accès.
Silicium aussi. On peut avoir quelques Mo à quelques Go à un prix raisonnable.
Le disque dur : pour un prix raisonnable, de quelques Go à plusieurs To.
Pas du silicium, du matériel métallique magnétique.
Accès mécanique. Quelques ms d’accès (10ms, soit 10 millions de cycles)
Pour un prix raisonnable, quelques To à plusieurs Po. 10 minutes d’accès : accès séquentiel, il faut mettre la bobine au bon endroit avant d’accéder aux données. Encore moins cher : plastique
On le voit immédiatement, aucun de ces quatre matériels ne respecte les quatre contraintes qu’on a énoncé plus haut. Par contre, chacune d’entre-elle en respecte un sous-ensemble.
La solution intuitive est de mélanger les différents types de mémoire. Le processeur est censé s’adresser successivement aux différentes mémoires, de la plus rapide à la moins rapide.
On suppose une mémoire statique avec temps d’accès d’un cycle, de 4 Ko, une mémoire dynamique qui demande 10 cycles pour un accès, et propose 4 Mo, et un disque dur qui réclame 1 million de cycles par accès, et propose 4 Go.
Si on suppose que les processeur demande à accéder à une adresse choisie selon une loi uniforme sur [0, 4*10^9], alors l’espérance du nombre de cycles pour un accès mémoire sera en fait très proche de 10^6.
Le calcul exact est donné par E = 1 * (10^-6) + 10 * (10^-3 - 10^-6) + 10^6 * (1 - 10^-3).
Bien heureusement, le processeur ne demande pas d’accéder à des adresses choisies selon une loi uniforme sur la totalité de l’espace d’adressage donné par le disque dur. On peut en fait supposer deux propriétés sympathiques, et ce de manière assez universelle en le type du programme :
- La localité spatiale : les adresses demandées dans un programme sont proches les unes des autres : les instructions sont placées de manière séquentielle dans des boucles ou des fonctions, les données sont placées sur une pile, ou avec un peu de chance en tous cas de manière contigüe.
- La localité temporelle : la probabilité d’accéder à une adresse proche de la dernière adresse accédée est plus élevée que la probabilité d’accéder à une adresse proche d’une adresse accédée il y a 10000 cycles.
Ces deux propriétés doivent être exploitées, si on veut pouvoir avoir besoin de moins d’un million de cycles en moyenne pour accéder à un octet : l’idée est de ramener plus que la donnée d’intérêt des mémoires lentes au mémoire rapides, de ramener un bloc mémoire autour de cette donnée. Ce bloc fait en général quelques dizaines d’octets (32, 64, 128).
On peut exploiter ça en ramenant plus que les données d’intérêt dans les mémoires plus rapides : on ramène un bloc mémoire (quelques dizaines d’octets : 32, 64, 128).
A partir de maintenant, la première mémoire statique sera appelée cache, la deuxième mémoire dynamique sera appelée RAM, ou mémoire centrale, ou mémoire primaire, le disque dur sera la mémoire secondaire. On oublie la mémoire magnétique pour le moment, elle n’est pas utilisée dans les ordinateurs habituels.
Le processeur est censé demander d’abord au cache si un octet ou un mot s’y trouve. Si l’octet ou le mot ne s’y trouve pas, le bloc entier est alors ramené de la mémoire centrale vers le cache.
Le temps que cela prend se calcule de la manière suivante :
On part du principe qu’on a des blocs de 32 octets, et que la largeur du bus est d’un mot mémoire. Ramener les 8 mots mémoire (on est dans une architecture 32 bits) de la mémoire vers le cache prend donc 80 cycles.
Si on part du principe que le cache miss a une probabilité de 0.1, alors l’espérance du temps d’accès à l’octet ou au mot mémoire est donnée par : E = 0.9 * 1 + 0.1 * 10 * 8 = 8.9
C’est assurément mieux que 1 million, mais c’est encore trop, d’autant plus qu’on a fait une hypothèse assez généreuse sur la proba du cache miss.
En élargissant la nappe de fils de la mémoire vers le cache, on réduit énormément le nombre de cycles. Coûte cher, mais très efficace.
Analysons plus précisément les 10 cycles nécessaire pour l’accès à la mémoire : en fait, une partie de ces 10 cycles est due :
- Au décodage de l’adresse
- À l’attente pour l’accès au bus système
Donc, indépendemment de la quantité de données qu’on va chercher, on doit toujours payer un temps forfaitaire pour le décodage de l’adresse plus l’accès au bus.
Le temps d’accès total est donc donné par :
T = A + B * (Taille bloc en mots / Taille bus en mots)
Avec A qui désigne le forfait, et B le coût du transfert d’un mot mémoire.
En général, pour des raisons qu’on ne rappellera pas ici, A domine très largement B. C’est précisément le fait que le forfait est très cher devant le coût du transfert que les transferts en gros, et donc les tampons et les caches, sont beaucoup beaucoup plus efficace que les transferts au détail.
Si on suppose dans notre exemple que A = 9 et B = 1, et si on suppose toujours les mêmes probabilités de cache miss et de cache hit, et si on suppose encore que la taille du bus est de 4 octets, de même que la taille du bloc est de 32, alors le temps espéré d’accès à l’octet ou au mot d’intérêt est donné par : E = 0.9 * 1 + 0.1 * (9 + 1 * 8) = 0.9 + 0.9 + 0.8 = 2.6
Ce qui est beaucoup mieux : 2.6 cycles en moyenne pour accéder à un mot, en supposant une proba de miss de 0.1, c’est tout-à-fait acceptable.
Le cache et la mémoire sont organisés en blocs, pas en mots.
Comment sont organisées les données dans le cache et la mémoire centrale ?
On dit que la mémoire est divisée en blocs, et que le cache est divisé en blocs, ou plutôt en emplacements qui permettent d’accueillir des blocs. Bien entendu, les blocs de la mémoire centrale font la même taille que les blocs, ou emplacements de blocs, du cache.
Dans la suite, on nommera blocs des blocs de la mémoire centrale et emplacements les emplacements de blocs dans le cache. On a bien entendu bien plus de blocs que d’emplacements.
On distingue trois types de cache quand à la correspondance entre les blocs et les emplacements :
- Direct mapping (chaque numéro de bloc peut atterrir à un et un seul emplacement)
- Set associative (chaque numéro de bloc peut atterrir dans un ensemble d’emplacements)
- Full associative (chaque numéro de bloc peut atterrir où il veut)
On voit immédiatement que le dernier des trois types est le meilleur, il nous laisse la plus grande liberté dans les blocs qu’on pourra effectivement avoir dans le cache à un moment arbitraire. C’est aussi potentiellement le plus coûteux en matériel et en overhead.
Correspondance la plus simple.
Dans la mesure où on a bien plus de blocs que d’emplacements, on doit partitionner l’ensemble des blocs d’une certaine manière à pouvoir à chaque partition associer un emplacement dans lequel tous les blocs de la partition iront se loger.
La partition la plus intelligente, si on se rappelle les propriétés de localité spatiale et temporelle des programmes, c’est la partition telle que la distance minimale entre deux blocs devant se loger dans un même emplacement soit maximale égale à la taille du cache en nombre d’emplacements.
En effet : on voudrait que si un bloc n doit se loger dans un emplacement m, les blocs n+1 et n-1 puissent chacun se loger dans deux emplacements distincts deux à deux et différents de m. Sinon, il ne sera pas possible d’avoir à la fois les blocs n-1, n, n+1 dans le cache, ce qui est une source sûre de gâchis étant donné les propriétés de localité spatiale et temporelles des programmes. Ce raisonnement reste valable tant qu’il reste des emplacements dans le cache.
A quoi ressemble le cache direct mapping du point de vue matériel ?
On part toujours du principe que les blocs font 32 octets, et que la taille du mot mémoire est de 32 bits.
Etant donné ce matériel, à quoi ressemble une adresse mémoire pour les différents composants. On sait déjà que l’adresse s’écrit sur 32 bits.
Pour la mémoire principale, les 5 bits de poids faible vont désigner le décalage en octets depuis le début du bloc (car les blocs font 32 octets). Les bits de poids fort donnent le numéro du bloc. Si on admet une taille de bloc à 64 (respectivement 128 octets), on devra attribuer les 6 (respectivement 7) octets de poids faible au décalage depuis le début du bloc. Mais puisqu’il y aura 2 (respectivement 4) fois moins de blocs (on a toujours au maximum 2^32 adresses), on pourra quand même nommer toutes les octets.
Pour le cache, c’est un peu plus compliqué : les 5 bits de poids faible vont toujours désigner le décalage en octets par rapport au début du bloc, mais les bits de poids fort seront séparés en les bits qui serviront à donner le numéro de l’emplacement, et en les bits qui serviront à donner l’étiquette du bloc dans l’emplacement. Si on admet que le nombre d’emplacements dans un cache est une puissance de 2 (et ça doit être le cas, sinon c’est du gâchis de bits), alors le nombre total de bits utilisés pour écrire le numéro de l’emplacement est donné par log_2(nombre d’emplacements), qui est une quantité entière.
L’étiquette du bloc est donc un nombre écrit sur (taille du mot mémoire) - log_2(nombre d’emplacements du cache) - log_2(taille du bloc en octets) bits.
Le cache est séparé en deux parties, la partie directory qui stocke les étiquettes des blocs et la partie data, qui stocke les données des blocs. Chaque partie a donc le même nombre d’emplacements, le nombre d’emplacements du cache donné plus haut.
Dans la partie directory du cache, on a un bit de présence pour chaque emplacement, qui dit si l’emplacement contient ou non un bloc.
Quand le processeur central demande une adresse, celle-ci est formatée de la même manière que pour le cache : en effet, le processeur ne parle qu’à son cache pour le moment. Le fait que la notion d’étiquette ou d’emplacement, ou de bloc, ou de décalage par rapport au bloc n’aient pas de sens pour le processeur n’est pas un problème ici : il se trouve simplement que l’adresse demandée par le processeur à son cache se conforme au formatage donné plus haut pour le cache. Le contrôleur du cache compare les (taille du mot mémoire) - log_2(nombre d’emplacements du cache) - log_2(taille du bloc en octets) (soit ici 24) bits de poids fort de l’adresse envoyée par le processeur aux 24 bits stockés dans la partie directory de l’emplacement donné par les bits 24 à 26 (dans notre exemple à 8 emplacements) de l’adresse envoyée par le processeur. Si ces 24 bits-ci sont les mêmes que ces 24 bits-là, et que le bit de présence idoine est à 1, alors on sait que le contenu de l’emplacement est valable.
Dans ce cas, le cache envoie les données au processeur. Quand une au moins de ces conditions n’est pas respectée, soit le bit de présence idoine à 0, soit une non-correspondance entre les 24 bits de poids fort de l’adresse envoyée par le processeur, et les 24 bits stockés dans l’emplacement idoine de la partie directory du cache, que se passe-t-il ?
Les données sont quand même envoyée, mais par un autre fil est envoyé un bit de “miss” qui est mis a 1 quand une de ces conditions n’est pas respectée : ce bit de miss dit simplement au processeur de ne pas tenir compte des données envoyée.
Cette mise en place, qui semble contre-intuitive (pourquoi ne pas simplement conditionner l’envoi des données à leur validité ?), est en fait la moins coûteuse en matériel : on envoie les données sans se poser de question, et au prix seulement d’un comparateur et d’une porte logique NAND, on indique si les données sont valables. Ce coût de la validation est constant en la quantité de données effectivement envoyées au processeur, et promet donc de bien passer à l’échelle.
Suite de l’organisation du système mémoire.
On a vu dans la séance précédente la logique et l’implémentation matérielle du cache. On a vu en particulier que le cache n’avait pas tout le temps la donnée demandée, ce qui occasionnait un miss. Se renseigner sur la fréquence de ce phénomène est la première étape pour essayer de l’amoindrir.
Pour les instructions, le taux de miss couramment retenu est autour de 2 à 5%. Pour les données, le taux de miss couramment retenu est autour de 5 à 10%.
Ces valeurs n’ont bien évidemment de sens que pour un rapport de taille bien particulier entre le cache et la mémoire centrale. Plus généralement, entre l’espace des instructions ou données que les instructions sont susceptibles de demander et l’espace dans lequel ces instructions ou données occasionnent un hit.
On a ici un rapport de 1/1000 entre le cache et la mémoire.
On a vu la semaine dernière le cache par direct mapping, voyons maintenant le cache set associative.
Auparavant, un bloc de la mémoire centrale ne pouvait aller que dans un emplacement bien précis (mapping direct).
On décide maintenant de permettre à un bloc de la mémoire centrale d’aller dans l’un de plusieurs emplacements bien définis.
À titre d’exemple, si on fait l’hypothèse qu’on a un cache à 8 emplacements, on créé 4 ensembles de deux emplacements chacun.
Chaque bloc peut atterrir non plus dans un emplacement, mais dans n’importe lequel des deux emplacements du même ensemble.
Les adresses de la mémoire centrale sont donc maintenant distribuées dans des ensembles plus que des emplacements. Auparavant, selon les principes de localité spatiale et temporelle, la partition optimale était celle qui garantissait une distance en adresse minimale entre deux blocs devant aller dans le même emplacement la plus grande possible. Cette contrainte était saturée en mettant cette distance constante identique à la taille du cache en emplacements, très simplement en associant le bloc n à l’emplacement avec lequel il est congruent modulo la taille du cache en emplacements.
Maintenant, on peut se permettre d’utiliser le même principe, sauf qu’on doit associer le bloc n à l’ensemble avec lequel il est congruent modulo la taille du cache en ensembles.
À taille constante entre nos deux exemple, puisque la taille du cache en ensembles est inférieure à la taille du cache en emplacements (sinon, c’est juste du direct mapping), la distance minimale entre deux blocs qui vont dans le même ensemble est divisée d’un rapport égal au nombre d’emplacements par ensemble.
On doit maintenant changer la manière dont les adresses sont écrites.
Pour le cache, elle sera donc maintenant formatée comme suit :
- Toujours l’ offset depuis le début du bloc (écrit sur log_2(nombre d’octets du bloc) bits)
- Un numéro d’ensemble et non plus un numéro d’emplacement (écrit sur log_2(nombre d’ensembles du cache) bits) (maintenant moins long de log_2 le nombre d’emplacements par ensemble)
- Tag (les bits de poids fort) (maintenant plus long de log_2 le nombre d’emplacements par ensemble)
Puisque maintenant le cache a un peu de choix sur l’emplacement dans lequel il écrit, on vient d’introduire la nécessité d’une stratégie de remplacement.
le but final : on veut se débarasser du bloc tel que pour une suite arbitraire d’opérations du processeur, le taux de cache miss soit le plus bas possible. (merci capitaine évident)
La stratégie FIFO : on vire le plus ancien. La stratégie LIFO : on vire le plus nouveau. La stratégie LRU : on vire celui qui a été accédé pour la dernière fois il y a plus longtemps.
La dernière stratégie est basée sur la localité temporelle.
L’adresse à laquelle le processeur va demander à accéder peut être modélisé par une variable aléatoire.
Le support de cette variable aléatoire est l’ensemble des adresses de la mémoire, gentiment indexées de 0 à N.
On suppose par hypothèse que la fonction de densité de probabilité de (X = x) (X la VAR, x l’index de la mémoire) est constante égale à 1/N.
Autrement dit, a priori, le processeur accède à toutes les adresses de manière équiprobable.
Maintenant, on peut considérer non plus une probabilité naïve, mais une probabilité conditionnelle.
La fonction de densité de probabilité de (X_t = x) conditionnée à (Xt-1 = x_0) sera une espèce de pointe légèrement dissymétrique à droite (pourquoi ? Exercice pour le lecteur…) centrée autour de x_0.
La fonction de densité de probabilité de (X_t = x) conditionnée à (Xt-10 = x_0) sera une espèce de montagne légèrement dissymétrique à droite (pourquoi ? Exercice pour le lecteur…) centrée autour de x_0.
La fonction de densité de probabilité de (X_t = x) conditionnée à (Xt-100 = x_0) sera une espèce de colline légèrement dissymétrique à droite (pourquoi ? Exercice pour le lecteur…) centrée autour de x_0.
La fonction de densité de probabilité de (X_t = x) conditionnée à (Xt-1000000 = x_0) sera probablement indistinguable de la probabilité a priori.
Maintenant, faisons figurer toutes ces courbes sur le même graphique : en abscisses les x les index d’adresses, en ordonnées la probabilité que X_t soit égale à x.
Ce dessin illustrera à la fois la notion de localité spatiale et de localité temporelle :
- La forme de la courbe, c’est la localité spatiale : on a plus de chance, si on a accédé à l’instruction précédente à x_0, que l’adresse à laquelle on va accéder maintenant soit proche de x_0, plutôt qu’elle en soit éloignée.
- La dégradation successive des courbes et son retour vers une droite, c’est la localité temporelle. Selon la proximité dans le temps avec laquelle on a accédé à x_0, on a plus ou moins de chance d’y accéder à nouveau maintenant.
Puisqu’on peut avoir deux emplacements par ensemble, le matériel change.
On a besoin de deux mémoires directory et de deux mémoires data.
Maintenant, quand on cherche une adresse, et qu’on sait donc qu’on doit la demander à un ensemble bien précis (il suffit de regarder l’adresse à un endroit bien précis), il faut maintenant vérifier tous les emplacements de cet ensemble (plus unique maintenant) : soit comparer bit à bit le tag de l’adresse avec le tag de l’emplacement correspondant à l’ensemble de l’adresse, dans chaque mémoire directory.
En fait, une mémoire directory stockera la moitié de chacun des ensembles du cache. (de même pour la mémoire data)
On aura donc autant de comparaisons qu’il y a d’emplacements dans chaque ensemble (autrement appelé le degré d’associativité).
Un cache set associative est donc un peu plus lent qu’un cache direct mapping. Il compense cette lenteur relative par une diminution CETERIS PARIBUS du taux de miss.
L’implémentation du LRU en matériel est en revanche beaucoup plus coûteuse.
Soit une degré d’associativité n.
Dans un ensemble, on doit stocker l’index de l’accession sur log_2(n) bits. Vu qu’on a n emplacements par ensemble, on doit avoir de quoi stocker n*log_2(n) bits.
À chaque accès mémoire, on doit mettre à jour ces n tableaux de log_2(n) bits.
On doit, en cas d’éviction, chercher l’index le plus élevé.
Tout ça est impossible à implémenter en matériel, surtout si on veut que ça prenne genre un ou deux cycles.
On utilise le principe du LRU simplifié, ou pseudo-LRU, ou plru, qui vient en deux types, le tree-pLRU et le bit-pLRU.
Pirouz n’a expliqué que le bit-pLRU en cours. On inclut ici le texte d’une réponse stackoverflow. La réponse est de Alain Mérigot, professeur à Paris-Sud (les droits de reproduction de cette réponse peuvent être réservés, et devront toujours mentionner l’auteur original) :
Least recently used means the line with the oldest access time. But keeping track of accesses to always know which one is the oldest may be complex in a cache context. Storing the access order for every block would require at least ceil(log2(n!)) bits, or, most probably, n×log2n bits which is close for n small and much simpler to manage. Whenever a memory reference is accessed, it must be removed from the order list, put at the top and the rest of the list updated. This may be complex to do in one cycle.
This is the reason why pseudo-LRU methods have been developed. They guaranty that an “ancient” line will be ejected, but not that the most ancient will be.
Consider an example for the bit-LRU of your question. We assume that the initial set state is the following.
line status real order (index) (MRU) 0 0 3 LRU 1 1 0 MRU 2 1 1 3 0 2 The real order is not stored, but we will use it to understand the behavior of the algorithm (smallest is youngest).
Now, assume we access existing line 0. Status becomes
line status real order (index) (MRU) 0 1 0 MRU 1 1 1 2 1 2 3 0 3 LRU Assume this is followed by a miss, so we apply the method and replace line 3:
Whenever the last remaining 0 bit of a set’s status bits is set to 1, all other bits are reset to 0. line status real order (index) (MRU) 0 0 1 1 0 2 2 0 3 LRU 3 1 0 MRU So the algorithm has properly ejected LRU (line 3).
Assume that there is another miss. The algorithm states :
At cache misses, the line with lowest index whose MRU-bit is 0 is replaced. So line 0 will be replaced. But it is not LRU which is line 2. It is even the “youngest” in the ancient lines. But is has the lowest index. To eject another better line would require additional information on the access times. Maybe some randomness in the ejection could be simply added. But finding the real LRU is more complex.
Note that there are better ways to have a pseudo LRU. Tree-LRU for instance is much better, but it still does not guaranty that the real LRU will be used. For practical applications, pLRU gives a miss rate similar to real LRU, while being much simpler.
But even real LRU may not always be the best policy and if a line has been accessed frequently it is likely that it will continue to be accessed, and it should probably not be replaced even if it is LRU. So the most efficient methods extend pLRU by keeping track of the number of accesses and by considering differently lines that are have been accessed only once and lines that have been accessed twice or more. This way, whenever a line has to be ejected, lines that have been accessed only once are preferred.
Bien entendu, des fois, on se trouve à évincer une ligne (comme on appelle aussi un bloc apparemment) qui n’est pas la ligne LRU. Mais on n’a besoin que de n bits de stockage, et on a un bit à flip pour chaque accès, et ce indépendemment de n.
Bien évidemment, de temps en temps, on doit aussi flip tous les bits sauf 1. Pirouz avait une autre version, qui consiste à noter la valeur du bit MRU, et à plutôt flip ce bit-là.
Ca requiert un bit à stocker en plus, un peu plus de matériel pour aller chercher la valeur de ce bit pour savoir dans quel sens flip les bits, mais ça doit être un peu plus rapide.
Cette méthode donne des résultats très corrects
L’autre technique est un peu plus complexe et un peu plus coûteuse en matériel, et prend un peu plus de temps.
On se réfèrera à l’article wikipedia :
The algorithm works as follows: consider a binary search tree for the items in question. Each node of the tree has a one-bit flag denoting “go left to find a pseudo-LRU element” or “go right to find a pseudo-LRU element”. To find a pseudo-LRU element, traverse the tree according to the values of the flags. To update the tree with an access to an item N, traverse the tree to find N and, during the traversal, set the node flags to denote the direction that is opposite to the direction taken.
Dans ce cas, on a besoin de 2n-1 bits de stockage pour un degré d’associativité n.
On a besoin de log_2(n) “traversements” par accès mémoire.
Donc ça coûte plus de matériel, c’est un peu plus long, mais le taux de cache miss est apparemment bien meilleur, d’après l’ami Alain Mérigot toujours.
On l’a donc vu, le set associative introduit un certain nombre de problèmes assez difficilement solvables pour passer à l’échelle. C’est un cas conceptuel important, parce que c’est la cas général : le direct mapping est en fait un set associative avec un degré d’associativité égal à 1, et le full associative est en fait un set associative avec un degré d’associativité égal à la taille du cache.
Dans les faits, on a du mal, pour toutes les raisons énoncées plus haut, à dépasser un degré d’associativité de 8 ou 16, même sur les machines modernes.
Les miss s’expliquent de trois manières :
- Miss compulsif : miss qui vient simplement du premier accès à un bloc.
- Miss de conflit : plusieurs blocs se battent pour le même emplacement.
- Miss de capacité : tout le monde se bat pour la totalité des emplacements.
Il y a en fait trois solutions orthogonales à chacun de ces problèmes :
- Miss compulsif : augmenter la taille des blocs (ou prendre plusieurs blocs, c’est la même chose)
- Miss de conflit : augmenter le degré d’associativité
- Miss de capacité : augmenter la taille du cache
Pour le moment, on n’a considéré que la lecture dans le cache.
Avec les écritures arrivent les problèmes de cohérence mémoire.
Considérons une situation avec plusieurs processeurs, chacun avec son propre cache.
Il existe une solution qui, par construction, respecte la cohérence : l’écriture Write Through. Quand on modifie une donnée de la mémoire, on accède directement à la mémoire primaire, on modifie, et on modifie en passant les valeurs de la donnée dans le cache.
Cohérence est respectée, et principe simple. Inconvénient est que chaque écriture requiert d’accéder au bus.
Deuxième stratégie possible : Write back : On oublie la mémoire primaire, on se contente de modifier la valeur dans le cache. Et on sauvegarde les modifications dans la mémoire centrale au moment où on s’apprête à supprimer.
Accès en écriture sont très rapide. Mais la cohérence mémoire n’est plus assurée. (marche probablement quand même quand on a un seul processeur).
Mais un remplacement demande un transfert de deux blocs : on amène l’ancien bloc en mémoire centrale, et on ramène le nouveau en cache.
Retour sur les stratégies d’écriture :
Deux types de cache :
- Write-through : l’écriture se fait à travers le cache vers la mémoire primaire (si le bloc qu’on veut écrire est présent, on écrit dans le cache en passant) : assure par construction la cohérence de mémoire, même si on admet plusieurs niveaux de cache et de mémoire. Le gros inconvénient c’est que chaque écriture se traduit par un accès au bus.
- Write-back : Consiste à ne pas se préoccuper de ce qui se passe en mémoire, et écrire uniquement dans le cache, et la version dans la mémoire primaire n’est pas mise à jour. On accède peu au bus, seulement quand on remplace le bloc (suppose la présence d’un bit “dirty”). Néanmoins, il faut un mécanisme supplémentaire pour assurer la cohérence.
Pourquoi pas plus de bus : consiste simplement à repousser le problème au niveau des périphériques.
Améliorons les performances de write-through :
1ère idée : mettre une boîte aux lettres dans le cache : le tampon d’écriture postée
Le nombre de places dans le tampon d’écritures postées est limité : si on veut lire un bloc, on doit d’abord vérifier si le bloc qu’on veut lire n’est pas dans le tampon d’écriture postée, déjà modifié par une écriture préalable. Il faut donc faire des comparaisons, qui coûtent cher. Donc le nombre de comparaisons doit être limité. Il n’y a que quelques places (1, 2, 4 ou 8) dans le tampon d’écritures postées.
Pour que le processeur ne soit jamais bloqué par les écritures, il faut et il suffit que le débit des store soit inférieur ou égal au débit d’évacuation des écritures du tampon d’écritures postées.
Si on dépasse, des cycles de gel vont être introduits de manière à ralentir le programme, de manière à ralentir le débit des store, qui va coïncider avec le débit d’évacuation.
Cette règle est fixe et doit être maintenue : si on ne la respecte pas, on finira forcément par devoir ralentir le programme. La taille du tampon d’écriture postée n’a d’influence que sur le moment où on va effectivement devoir faire le ralentissement.
Amélioration se voit du point de vue du processeur (pas du bus, le bus reçoit toujours autant de requêtes).
Améliorons Write-Back :
Le coût du miss augmente : je dois d’abord répercuter le bloc du cache dirty dans la mémoire centrale, puis ramener le bloc d’intérêt.
A>>B signifie 1 à 10 ou 1 à 100 (donc on doit quand même essayer de limiter les transferts)
Si on a un bit dirty, on peut effectivement limiter la quantité de transferts sur le bus en les conditionnant à ce que le bit est à 1.
Donc on a deux types de miss : le miss clean, qui coûte un transfert de bloc, et le miss dirty, qui en coûte deux.
Dans quel cas on préfère le premier ou le deuxième cas :
Les critères :
- La distribution temporelle des écritures
- La distribution spatiale des écritures
Les applications très localisées sont meilleures avec WB, les très délocalisées avec WT.
Que faire en cas de miss sur écriture :
Dans le cas du cache WT : si on a choisi WT, c’est que les écritures sont distribuées : pas le coup d’amener le bloc. Dans le cas du cache WB : si on a choisi WB, c’est que les écritures sont localisées : vaut le coup de ramener le bloc.
En fait, c’est la localisation qui détermine ET le type de cache d’écriture ET la présence ou non de miss sur écriture.
Problème avec deux processeurs :
On va avoir des problèmes de cohérence avec WB.
Un problème de cohérence en validité itérative [reprendre l’exemple]
On peut rajouter snoopy : il observe le bus.
Il faut informer la mémoire de ce que le bloc qu’elle tient est obsolète. Mais ça, ça coûte une transaction sur le bus. Mais si on écrit sur le même bloc, plus la peine de l’invalider.
Si la bit dirty est à 0 et que je fais une écriture sur le bloc, je dois envoyer invalidation.
Si la bit dirty est à 1 et que je fais une écriture sur le bloc, je n’ai pas besoin d’envoyer invalidation.
Suppose d’ajouter un directory à la mémoire centrale.
Snoopy intervient quand il voit qu’un autre processeur voit ses requêtes rejetées pour cause d’invalidation : c’est moi qui détiens la dernière version de la donnée.
Il lance une transaction de mise à jour de la mémoire. Le bit dirty repasse à 0 et le bit invalidate de la mémoire centrale repasse à 0.
Snoopy est aussi chargé d’invalider sa copie locale de la donnée si il voit une instruction d’invalidation passer dans le bus : c’est le bit de présence qui va passer à 0.
En gros, on parle de l’implémentation en matériel d’un mutex flexible.
Il faut aussi un snoopy dans le cas du WT.
On peut aussi interdire de cacher certains blocs : très simple mais très coûteux.
Les lock se servent de ce dispositif.
Est-ce qu’on a un cache unifié pour les instructions et les données, ou au contraire on a des caches séparés pour les instructions et les données ?
Spontanément, on préfèrerait avoir deux caches séparés : beaucoup plus simple à mettre en place.
Les caches séparés font perdre potentiellement de la place.
Dernier cours sur la hiérarche mémoire.
Liaison entre la mémoire primaire et la mémoire secondaire.
Cache : 1 cycle par accès, quelques Ko à Mo. Taux de miss (cache instructions : 2-3-5 % et cache de données : 5-10 %)
Mémoire centrale : 10 cycles par accès (en vrai un peu plus, genre 40), quelques Mo à Go. Taux de miss (10^-6)
Mémoire secondaire : 10 millions de cycles par accès, quelques Go à quelques To (physique mécanique).
Comment fonctionne la liaison entre la mémoire primaire et la mémoire secondaire.
De la même manière que la liasion entre le cache et la mémoire primaire. La mémoire primaire est un cache de la mémoire secondaire.
On doit absolument avoir un taux de miss TRÈS TRÈS TRÈS faible (de l’ordre de 10^-6, 10^-5). [reprendre la démonstration]
Comment arriver à cet objectif ? On n’a que la localité spatiale et temporelle.
Localité spatiale, pour être utilisée à son plein potentiel, suppose de prendre des gros blocs (unix standart : 4Ko, linux variable de 4Ko - 1Mo : on appelle ça une page).
Localité temporelle, pour être utilisée à son plein potentiel, suppose d’augmenter l’associativité : il faut faire un cache full associative.
On est obligé d’utiliser WB.
Puisqu’on a full associative, quand le processeur demande qqch à la mémoire centrale.
Adresse :
Bits de poids faible donnent le déplacement dans la page.
Bits de poids fort donnent l’étiquette : on n’a pas besoin de nommer un ensemble (on a un seul ensemble). Cet étiquette est l’adresse virtuelle.
L’emplacement physique dans la mémoire centrale donne l’adresse physique.
N’importe quel adresse virtuelle peut aller dans n’importe quelle adresse physique. La correspondance ne peut pas être donnée par un algorithme.
Problème de table associative. On ne va pas s’amuser à scanner toute la mémoire : on doit stocker ces informations quelque part : c’est la table des pages.
La table des pages est une espèce de directory de la mémoire.
Le nombre de cases dans la table des pages est le nombre de pages virtuelles (soit 1 Mpage dans notre exemple).
La largeur de la table des pages est de 32 bits (recalculer). (bit de présence, bit dirty, etc…)
Donc la taille de la table des pages est de 4Mo, soit la taille de la mémoire centrale dans notre exemple. C’est nul.
Mais en fait, seule une toute petite proportion des pages dans la table des pages a un bit de présence non 0 (parce qu’il y a très peu de place dans la mémoire centrale).
On dit que la table est éparse (sparse).
On peut donc facilement se permettre de créer une table hiérarchique. Chaque entrée dans la table des pages maître représentera une quantité fixée de pages virtuelles. Si toutes les pages d’un “paquet” ne sont pas dans la mémoire centrale, et ont donc un bit de présence à 0, nul besoin de les représenter.
La table maître est en fait une table de pointeurs vers un certain ensemble de sous-tables, qui ne sont effectivement représentées que si elles ont de l’information (soit quand au moins un des bits de présence est à 1).
Cette quantité de 1024 pas forcément fixée. Plus il y a de niveaux d’indirection, plus on peut se permettre d’avoir une quantité faible, ce qui permettra de bien compacter l’espace que prendra la table des pages.
La taille de la table des pages dépend fondamentalement de la taille de la mémoire secondaire (la taille de l’espace d’adressage en fait), et non pas de la taille de la mémoire primaire, ce qui est fondamentalement débile.
On pourrait faire l’inverse : on ne stocke que des pages physiques dans la table, et dans chaque champ se trouve l’addresse de la page virtuelle que cette page physique représente.
La taille de la table des pages dépend maintenant de la taille de la mémoire primaire et non plus de la taille de l’espace d’adressage.
On a besoin d’une seule table pour l’ensemble des processus de la machine.
Cette table contient donc deux informations : le numéro de page virtuelle, et un identifiant du processus.
Inventé par IBM : AIX.
Maintenant, il faut quand même parcourir cette table à la recherche du bon index :
for (i = 0; i < n; i++)
if ((TPI[i].PV == #PV) && (TPI[i].pid == pid))
break;La bonne manière, c’est la table de hachage. (on va en plus se permettre de cacher les correspondances)
Les adresses du cache sont des adresses physiques. Les adresses de la mémoire centrale sont aussi des adresses phyiques. Les adresses de la mémoire secondaire sont des adresses virtuelles. Mais le processeur créé des adresses virtuelles !
Il faut que ces adresses virtuelles soient traduites en adresses physiques, faute de quoi le processeur ne pourrait accéder à son cache.
Ces traductions doivent être faites très vite. Or, s’il faut accéder à la table des pages dans la mémoire centrale, ça ne peut pas être fait en un cycle. En fait, il y a un cache dans le processeur qui garde les correspondances : le TLB, pour translation lookaside buffer. Ce cache fonctionne aussi selon le principe de la localité spatiale et la localité temporelle (contient 8, 16, 32 entrées).
Le scénario complet :
Mon processeur créé une adresse virtuelle. De cette addresse, j’enlève les bits de poids faible qui correspondent au déplacement dans la page, pour ne garder que le numéro de page virtuelle. Je donne ce numéro à mon TLB, si tout se passe bien, il me rend un numéro de page physique, je demande la page à mon cache (ou plutôt à la partie de la page qui m’intéresse qui est le bloc), et on a hit ou miss, la suite de l’histoire est connue…
Le scénario moins sympa :
Mon processeur créé une adresse virtuelle. De cette addresse, j’enlève les bits de poids faible qui correspondent au déplacement dans la page, pour ne garder que le numéro de page virtuelle. Je donne ce numéro à mon TLB, et là j’ai un miss. Il faut appliquer l’algorithme de traduction, et donc parcourir la table des pages. Je récupère donc cette adresse physique (si elle est là, bien entendu), que j’enregistre au passage dans mon TLB.
Le processus de traduction à partir du TLB prend quelques centaines de cycles.
Le scénario encore moins sympa :
Mon processeur créé une adresse virtuelle. De cette addresse, j’enlève les bits de poids faible qui correspondent au déplacement dans la page, pour ne garder que le numéro de page virtuelle. Je donne ce numéro à mon TLB, et là j’ai un miss. Il faut appliquer l’algorithme de traduction, et donc parcourir la table des pages. Il se trouve que cette page n’est pas dans la mémoire centrale (défaut de page). Il faut donc aller la chercher dans la mémoire secondaire, la ramener en mémoire centrale (évincer si besoin est). On met à jour la table des pages (très important).
(ça suppose que j’ai toujours l’adresse physique de la table des pages) Il y a donc un registre qui stocke cette adresse physique constante.
Ce cache doit être implémenté en logiciel (cf. NOYAU)
Support de cours :