#+TITLE : Prise de notes TD 4I100 ARCHI1
La difficulté de la conception de MIPS, c’est de concevoir un jeu d’instructions qui tiennent toutes en 32 bits.
lui R5, 0Il y a plein de possibilités pour initialiser R5 à 0.
Apparemment, lui n’est pas la manière canonique de régler le problème. On préfère les opérations logiques bit par bit.
Xor R5, R5, R5Add R5, R6, R0Or R5, R6, R0La bonne manière :
Ori R5, R0, 0x4567La manière :
Addi R5, R0, 0x4567 Lui R5, 0x4567
Ori R5, R5, 0xABCDCompilation à la main.
OR R9, R4, R0
Boucle: LB R8, 0(R9)
BEQ R8, R0, fin
ADDIU R9, R9, 1
J Boucle
Fin: SUB R2, R9, R4
ADDIU RS,R4,-1
Boucle: ADDIU R2,R2,1
LB R8,0(R2)
BNE R8, R0, Boucle
SUB R2,R2,R4
Recopie de chaîne de caractères.
Solution Agon-Rambosson
OR R8,R5,R0
OR R9,R4,R0
Boucle: LB R10,0(R8)
BEQ R10,R0,fin
SB R10,0(R9)
ADDIU R9,R9,1
ADDIU R8,R8,1
J Boucle
Fin: SB R0,0(R9)
OR R2,R4,R0
On a eu l’idée, probablement un peu difficile à mettre en place pour le moment, d’implémenter un cache dans les registres. Au lieu de charger un octet, on pourrait charger un mot entier, et traiter 8 bits par 8 bits le contenu du registre (un peu sale) : ça permettrait de diviser le nombre d’accès mémoire par 4.
Ecrire la fonction strupper de la bibliothèque standart en assembleur.
On a une condition un peu complexe, qu’on ne pourra pas exprimer en une instruction, et qu’il faudra transformer :
char *strupper (char *str)
{
int i = 0;
while (str[i] != '\0') {
if ((str[i] >= 'a') && (str[i] <= 'z')) {
str[i] = str[i] - 'a' + 'A';
}
i++;
}
}La condition de la ligne 7 du programme doit être traduite en un certain nombre de conditions qui se puissent transcrire en le moins d’instructions asm possible.
En particulier, les seules opérations de comparaison sont slt et ses dérivés : on doit exprimer les conditions sous la forme Reg < Immédiat, ou Reg < Reg.
On a :
(str[i] >= ‘a’) && (str[i] <= ‘z’) = C((str[i] < ‘a’) || (‘z’ < str[i]))
C(A || B) = C(A) && c(B)
On peut donc mettre dans un deux registres le résultat de la comparaison (str[i] < ‘a’) et (‘z’ < str[i]), en faire l’union dans un des deux registres, puis tester pour la différence avec 0 de ce registre : si le registre contient un entier différent de 0, on exécute à partir de l’étiquette endif.
ADDU R2,R0,R4
ADDIU R8,R0,'a'
ADDIU R9,R0,'z'
loop: LB R10,0(R4)
SLT R11,R10,R8
SLT R12,R9,R10
OR R12,R12,R11
BNE R12,R0,endif
ADDIU R10,R10,'A' - 'a'
SB R10,0(R4)
endif: ADDIU R4,R4,1
BNE R10,R0,loop
On se propose d’écrire la fonction suivante en assembleur :
int *addvect(int *a, int *b, int *c, int size)
{
int i = 0;
while (size > 0) {
c[i] = 2 * a[i] + 3 * b[i];
i++;
size--;
}
return c;
}La subtilité ici est de ne pas à se servir de mult, qui est une opération coûteuse.
La solution, c’est le décalage des bits à gauche : on se sert des propriétés du binaire.
Multiplication par 2 : décalage de tous les bits à gauche. Multiplication par 3 : multiplication par 2, puis addition avec l’antécédent.
On a une condition stricte, en revanche : Vu qu’on fait une multiplication par 2 et une par 3, on doit avoir les deux bits du poids fort à 0, sinon le résultat de la multiplication ne se laisse pas écrire dans les 32 bits du registre.
On part du principe que cette condition est remplie.
Voilà notre solution (un certain nombre d’erreurs du tableau ont été corrigées) :
OR R2,R0,R6
loop: BLEZ R7,fin
LW R8,0(R4)
LW R9,0(R5)
SLL R8,R8,1 #R8 contient 2a[i]
SLL R10,R9,1
ADDU R10,R10,R9 #R10 contient 3b[i]
ADDU R10,R10,R8 #R10 contient 2a[i] + 3b[i]
SW R10,0(R6)
ADDIU R6,R6,4
ADDIU R4,R4,4
ADDIU R5,R5,4
ADDIU R7,R7,-1
J loop
fin:
On se gardera les exercices bonus pour la suite.
Conventions utilisées par GNU Compiler Collection, pour MIPS
| R0 | Registre qui vaut toujours 0 |
| R1 | A ne pas utiliser, réservé à l’assembleur. |
| R2 - R3 | Valeur de retour de la fonction appelée (R3 est là pour les retours sur 64 bits) |
| R4 - R7 | Registre pour passer les 4 premiers paramètres de la fonction appelée (les éventuels suivants sont sur la pile) |
| R8 - R15 | Registres de travail non préservés à travers l’appel d’une fonction (flush à l’entrée d’une fonction) |
| R16 - R23 | Registres de travail préservés à travers l’appel d’une fonction |
| R24 - R25 | Comme R8 - R15 |
| R26 - R27 | Ne doivent pas être utilisés par le compilateur |
| R28 | GP (Global pointer : pointeur vers les variables globales) |
| R29 | SP (Stack pointer : pointe sur la pile, là où les données non dynamiques sont stockées et lues) |
| R30 | Comme R16 - R23 |
| R31 | Adresse de retour de la fonction appelante |
La pile grandit vers le bas.
On doit mettre dans la pile les paramètres de la fonction
ADDIU R29,R29,-(n*4)
SW R4,16(R29)
SW R5,12(R29)
SW R6,8(R29)
SW R7,4(R29)
SW R8,0(R29)
JAL @fonction
JAL fait deux choses :
- Met PC + 4 dans R31
- Il change le registre PC vers l’adresse passée en paramètre
On doit faire ça nous même :
- Allouer (1 + nb(R à sauver) + nb(VarLoc)) * 4
- Stocker les Registres à sauver
- Stocker les variables locales
Restitution de la fonction :
- On doit charger les registres qui auraient pu être écrasés, depuis la pile
- On bouge le SP vers le haut, de la même quantité qu’on l’avait baissé avant
- On saute à l’adresse contenue dans R31
On a un problème : le registre R8 ne contient pas de paramètre de la fonction appelée. Il est juste autre part dans la pile, il faut aller le chercher : en fait, on suppose gentiment que toutes une série d’opérations chiantes sont faites pour nous, mais pas toutes non plus : à un moment, on décide qu’on doit faire les opérations faites par le compilateur, à un autre, on décide que ce n’est pas la peine, sans logique apparente.
On a en fait toute une série d’instructions implicites dans les exercices LW pour charger les paramètres depuis la pile (ce qui requiert qu’on connaisse leur adresse) : a priori, le compilateur est capable de les retrouver, c’est lui qui a écrit le code assembleur qui les stockait en un endroit de la pile : il n’est pas compliqué pour lui de se rappeler d’où il les a mis.
On prend un exemple, en supposant gentiment que les paramètres sont déjà dans les bons registres (on va quand même devoir lever cette hypothèse un moment.)
pgcd: ADDIU R29, R29,-4
SW R31,0(R29)
loop: BEQ R4,R5,eloop
SLTU R16,R4,R5
BEQ R16,R0,else
SUB R5,R5,R4
J loop
else: SUB R4,R4,R5
J loop
eloop: OR R2,R4,R0
eplg: LW R31,0(R29)
ADDIU R29,R29,4
JR R31
Mon idée, très verbeuse, linéaire, occupant beaucoup de registres, aimablement corrigée et commentée par mes camarades :
tri:
ADDIU R29,R29,-28
SW R31,16(R29)
OR R8,R0,R0
loop1:
SUB R12,R8,R5
BGEZ R12,eloop1
SLL R15,R8,2
ADD R15,R4,R15
LW R10,0(R15)
ADDI R9,R8,1
loop2:
SUB R13,R9,R5
BGEZ R13,eloop2
SLL R24,R9,2
ADD R24,R4,R24
LW R14,0(R24)
ADDI R9,R9,1
SUB R25,R14,R10
BLEZ R25,loop2
OR R11,R10,R0
OR R10,R14,R0
SW R11,0(R24)
J loop2
eloop2:
SW R10,0(R15)
ADDI R8,R8,1
J loop1
eloop1:
OR R2,R4,R0
eplg:
LW R31,0(R29)
ADDIU R29,R29,4
JR R31
Une autre version, par la prof, de son propre aveu assez sale. Mais utilise moins de registres.
tri:
ADDIU R29,R29,-20
SW R31,16(R29)
OR R2,R4,R0
BEQ R5,R0,end_extloop #On sort si le tableau est de taille 0
SLL R12,R5,2 #Multiplication par 4
ADDU R12,R12,R4 #Adresse fin de tableau
extloop:
LW R8,0(R4) # max=a[i]
ADDIU R9,R4,4 # calcul adresse élément i+1
BEQ R9,R12,end_intloop
intloop:
LW R10,0(R9) # charger a[i+1]
SLTU R11,R8,R10 # max < a[j]
BEQ R11,R0,endif
SW R8,0(R9) # On peut utiliser deux emplacements mémoire et un registre
OR R8,R10,R0
endif:
ADDIU R9,R9,4 # j++
BNE R9,R12,intloop
end_intloop:
SW R8,0(R4)
ADDIU R4,R4,4
BNE R4,R12,extloop
end_extloop:
LW R31,16(R29)
ADDIU R29,R29,20
JR R31
Rappel de pipeline
Partie I (Instruction Fetch) : On va chercher le mot mémoire et on le met dans le registre IR (Instruction Register)
Partie D (Decode) : On découpe l’instruction, on décode les numéros des registres concernés pour les identifier. Le PC est manipulé ici, car on sait où est la prochaine instruction : Soit PC++, soit saut à la bonne instruction.
Partie E (Execute) : On fait les calculs.
Partie M (Memory Access) : Seules les instructions Load et Store vont se servir de cet étage : on accède à la mémoire centrale en lecture et en écriture.
Partie W (Writeback) : A ce moment seulement le résultat éventuel de l’opération est mis dans le registre destination. On peut aussi modifier ici les registres comme R31.
Le fait que les valeurs soient écrites dans le registre seulement à la fin du pipeline pose tout un tas de problème :
loop: LB R9,0(R4)
BEQ R9,R0,end_loop
ADDIU R4,R4,1
ADDIU R2,R2,1
J strlen_loop
Ici, on a un problème :
R9 n’a sa bonne valeur qu’au moment du Writeback de la première instruction, qui arrive bien après le Decode de la deuxième instruction, moment où on a vraiment besoin que sa valeur soit bonne.
La solution naïve, c’est de geler l’instruction : mais si on fait ça, on peut ne pas savoir où on doit aller avant un petit moment, on doit retarder encore la prochaine instruction.
NOP : No operation : une espèce d’opération qui ne fait rien.
On a plusieurs manières de régler ce problème, chacune un peu imparfaite :
- Solution matérielle : bypass, acheminer la solution où on en a besoin dès qu’on peut (coûteux)
- Solution logicielle : réordonner les instructions
- Solution matérielle : Exécution spéculative : on peut commencer à exécuter certaines parties, sans vraiment savoir où on doit aller
Pipeline (plus compliqué à dessiner). On essaie de simplifier les schémas autant qu’il est possible.
On essaie autant qu’il est possible de tout pouvoir dessiner en caractères ASCII.
On utilisera les fonctionnalités des tableaux dans org-mode.
Les étages de pipeline sont dans une colonne chacun. On introduit des colonnes avant et après chaque étage, pour montrer les registres interétages.
Il est compliqué impossible de faire des flèches courbes. Pour cette raison, on notera >- une sortie de registre et -> et une entrée de registre. Si, dans un même étage de pipeline, plusieurs contenus de registre sont tranférés, on codera les flèches avec un chiffre :
>-1
1->
(on comprend bien qu’on doit faire partir une flèche du registre de la première ligne pour aller dans le registre de la deuxième)
Les opérateurs et les multiplexeurs ne sont pas dessinés, ils sont donnés formellement en texte. Par exemple, pour expliquer qu’on a un opérateur d’incrémentation +4 entre le registre PC avant IFC et le registre PC après IFC, on ne peut pas faire un gros rond avec un +4 dedans. On se contentera d’écrire la chose parfaitement lisible suivante :
| IFC | ||
| PC | >-+4-> | PC |
Ca marche aussi avec les multiplexeurs, qui ne font que vérifier des conditions logiques sur des contenus de registre connus de l’étage en question (donc déjà dessinés dans la colonne en question). Pour coder que l’opération du registre PC avant DEC vers le registre PC après RC dépend d’une condition dépendant des opérandes (dans le cas d’une instruction de type branch avec immédiat) on écrira :
BLTZAL (on n’a pas mis qu’on met ):
| DEC | ||
| I_RI | >-2 | |
| 1-> | SOPER_RD | |
| 2-> | TOPER_RD | |
| PC | >- +4 (si 1 >= 2) ou +4 + (2)*4 (si 1 < 2) -> | PC |
| R_V_CPU | >-1 |
C’est un peu plus verbeux, mais encore parfaitement compréhensible (on pourrait raccourcir l’écriture avec un opérateur ternaire).
Les lignes du tableau donnent les registres : on est parfaitement capable de respecter le formalisme Pirouzien qui suppose que le registre à une ligne donnée est toujours bien le même registre. Vu que le nombre de registres dans un pipeline MIPS est fini et potentiellement connu, le nombre de lignes maximum du tableau pourrait théoriquement être ainsi donné.
Le seule vrai problème de ce formalisme est qu’il n’est pas possible d’y faire figurer le déroulement de plusieurs instructions. On est obligé de faire plusieurs tableaux (un schéma détaillé avec plus d’une instruction est illisible de toutes façons).
On dessine l’instruction SLL rd, rs, rt
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RI | >–> | I_RI | |||||||
| 1-> | SOPER_RD | >-1 | ||||||||
| ALU : Shift 2 by 1 -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | >-2 | ||||||||
| -> | DATA_RM | >- | ||||||||
| PC | >-+4-> | PC | >-+4-> | PC | ||||||
| R_V_CPU | >-1,2 | -> | R_V_CPU |
Même question BLTZAL rs, label
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RI | >-2 | ||||||||
| 1-> | SOPER_RD | |||||||||
| -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | |||||||||
| -> | DATA_RM | >- | ||||||||
| PC | >-+4-> | PC | >- +4 (si 1 >= 2) ou +4 + (2)*4 (si 1 < 2) -> | PC | ||||||
| R_V_CPU | >-1 | -> | R_V_CPU$31 | |||||||
| >- +4 (inconditionné) -> | IOPER_RD | >- |
La multiplication par quatre (en fait, toutes les puissances de 2) peut être fait dans l’étage décode.
Une instruction nouvelle, qui n’existe pas dans le MIPS : BEQPI (branch if equal and post increment)
BEQPI RS,RT,label
C’est possible, on peut faire le branchement dans DEC et l’incrémentation se fait dans EXE.
C’est possible, l’incrémentation est inconditionnelle.
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RI | >-3 | ||||||||
| 1-> | SOPER_RD | |||||||||
| -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | >-++ | ||||||||
| -> | DATA_RM | >- | ||||||||
| PC | >-+4-> | PC | >- +4 (si 1 != 2) ou +4 + (3)*4 (si 1 == 2) -> | PC | ||||||
| R_V_CPU | >-1 et 2 | -> | R_V_CPU |
Une instruction nouvelle, qui n’existe pas dans le MIPS : BEQPD (branch if equal and pre decrement)
BEQPD RS,RT,label
Pas possible : la décrémentation devrait être avant le branchement qui est fait dans l’étage DEC, donc dans l’étage DEC aussi, il faudrait y rajouter un additioneur, ce qui allongerait la durée de l’étage et donc de tous les étages.
A dire vrai, possible mais pas worth.
ADD R3,R2,R1 ADD R3,R3,R1
A dire vrai, ces deux opérations sont comprimables en 1 :
ADD R3,R2,R1*2
On peut décaler la broche de R1 vers le poids fort de 1.
Mais là n’est pas la question.
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RI | >- | ||||||||
| 1-> | SOPER_RD | >-1 | ||||||||
| ALU 1+2 -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | >-2 | ||||||||
| -> | DATA_RM | >- | ||||||||
| PC | >-+4-> | PC | >- +4 -> | PC | ||||||
| R_V_CPU | >-1 et 2 | -> | R_V_CPU |
| IFC+1 | DEC+1 | EXE+1 | MEM+1 | WBK+1 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RE | |||||||||
| -> | I_RD | >- | ||||||||
| -> | I_RI | >- | ||||||||
| 1-> | SOPER_RD | >-1 | ||||||||
| ALU 1+2 -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | >-2 | ||||||||
| -> | DATA_RM | >- | ||||||||
| PC | >-+4-> | PC | >- +4 -> | PC | ||||||
| R_V_CPU | >-1 et 2 | -> | R_V_CPU |
L’idée, c’est de récupérer le contenu de RES_RE de l’instant t pour le mettre dans SOPER_RD. En terme de matériel, ça requiert un multiplexeur avec RES_RE et SOPER_RD en entrée et l’additioneur en sortie.
Quelles sont les conditions du mutliplexeurs : on veut comparer RS de l’instruction t et RD de l’instruction t-1.
On devrait avoir la même chose pour l’autre opérande : Un multiplexeur avec RES_RE et TOPER_RD en entrée et l’additioneur en sortie.
Dans ce multiplexeur, on veut comparer RT de l’instruction t et RD de l’instruction t-1.
ADD R0, R2, R11 ADD R3, R0, R11
Ici, on n’est pas censé avoir de problème : on ne peut pas écrire dans R0.
R0 est toujours à jour !!!!!, il ne peut jamais être modifié.
On doit préciser la condition du bypass :
Le bypass est déclenché sssi RS de l’instruction i égale RD de l’instruction i-1 et tous deux sont différents de 0. (on a le même pour le registre RT, on se doute)
LW R3,0(R2) ADD R3,R3,R11
On a R3 disponible et à jour à la fin de l’étage M de l’instruction t. On en a besoin au début de l’étage E de l’instruction t+1.
On va avoir besoin d’une instruction de gel.
On va la dessiner, si on peut. (edit : on peut, une instruction de gel consiste en l’écrasement des valeurs des registres interétage par elles-mêmes)
| IFC | DEC | EXE | MEM | WBK | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RM | |||||||||
| -> | I_RE | >- | ||||||||
| -> | I_RD | >- | ||||||||
| *-> | I_RI | >- | ||||||||
| 1-> | SOPER_RD | >-1 | ||||||||
| ALU 1+2 -> | RES_RE | >- | ||||||||
| 2-> | TOPER_RD | |||||||||
| *-> | DATA_RM | >- | ||||||||
| 3-> | IOPER_RD | >-2 | ||||||||
| PC | >-+4-> | PC | >- +4 -> | PC | ||||||
| R_V_CPU | >-1 et 2 | -> | R_V_CPU |
| IFC+1 | DEC+1 | GEL | EXE +1 | MEM+1 | WBK+1 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| -> | I_RM | |||||||||||
| -> | I_RE | >- | ||||||||||
| -> | I_RD | >–> | I_RD | >- | ||||||||
| -> | I_RI | >- | ||||||||||
| 1-> | SOPER_RD | >–> | SOPER_RD | >-1 | ||||||||
| 1+2-> | RES_RE | >- | RES | |||||||||
| 2-> | TOPER_RD | >–> | TOPER_RD | >-2 | ||||||||
| -> | DATA_RM | >- | ||||||||||
| PC | >-+4-> | PC | >- +4 -> | PC | ||||||||
| R_V_CPU | >-1 et 2 | -> | R_V_CPU |
Le cycle de gel est déclenché sssi (une partie masquée de) I_RD @t == (une partie masquée de) I_RE @t-1
En gros, on compare une partie bien précise de l’instruction stockée dans I_RD avec une partie bien précise de l’instruction stockée dans I_RE (qui concerne donc l’instruction précédente).
Quelle partie bien précise ? On suppose que le matériel sait faire le masque/filtre pour comparer bit à bit. C’est ce qui était entendu par l’expression (une partie masquée de)
addiu $2,$0,4
lui $3,0x00c
add $2,$2,$2
ori $3,$3, 0x4568
lw $2,0($3)
lbu $2,0($2)
ori $2,$2, 0x0001
bltzal $2,suite
addu $0,$0,$0
suite:
jr $31
addu $31,$31,-8
Dépendances :
- La 3 de la 1
- La 4 de la 2
- La 5 de la 4 et de la 3
- La 6 de la 5
- La 7 de la 6
- La 8 de la 7
- La 10 dépend de la 8 (BLTZAL)
- La 11 est exécutée no matter what, malgré le jump (delayed slot)
Schéma simplifié :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ADDIU | I | D | E | M >-2 | W | ||||||||||||||||
| LUI | I | D | E | M >-2 | W | ||||||||||||||||
| ADD | I | D | -> E | M | W | ||||||||||||||||
| ORI | I | D | -> E >-1 | M | W | ||||||||||||||||
| LW | I | D | -> E | M >-1 | W | ||||||||||||||||
| LBU | I | D | O | -> E | M >-1 | W | |||||||||||||||
| ORI | I | O | D | O | -> E >-1 | M | W | ||||||||||||||
| BLTZAL | O | I | O | O | -> D | E >-2 | M >-3 | W | |||||||||||||
| ADDU | I | D | E | M | W | ||||||||||||||||
| JR | I | -> D | E | M | W | ||||||||||||||||
| ADDU | I | -> D | E >-1 | M >-2 | W | ||||||||||||||||
| JK | I | O | -> D | E | M | W | |||||||||||||||
| ADDU | O | I | -> D | E | M | W |
Quel est le CPI de cette série d’instructions ?
D’après Karine, on commence à compter à partir de la sortie de la première instruction considérée (on part du principe que ce qui était avant concernait d’autres instructions, ce qui est vrai) jusqu’à la sortie de la dernière instruction.
#Cycles = 21 - 5 + 1 = 17 #Instruction = 13
CPI = 17/13
On profite de cet exercice pour lister les bypass du pipeline MIPS. On définit l’ordre du bypass comme le nombre d’étages de pipeline que le bypass permet de traverser (ordre 2 : le bypass permet d’obtenir une information située 2 étages plus loin)
Ordre 1 : E@t -> E@t+1
| 1 | 2 | 3 | 4 | 5 | 6 | ||
|---|---|---|---|---|---|---|---|
| ORI R3, R4, 0x0001 | I | D | E >-1 | M | W | ||
| LW R5, 0(R3) | I | D | -> E | M | W |
Ici, le bypass est du côté RS
Pour un bypass nécessaire en RT, on regardera par exemple :
ORI $3,$4,0x0001
ADD $5,$6,$3
Ordre 2 : M@t -> E@t+2
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| LW R3, 0(R5) | I | D | E | M >-2 | W | ||
| NOP | I | D | E | M | W | ||
| ADD R6, R3, R0 | I | D | -> E | M | W |
Pour un bypass nécessaire en RT, on regardera par exemple :
LW $3,0($5)
NOP
ADD $6,$0,$3
Ordre 2 : E@t -> D@t+2
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| ADD R3, R4, R5 | I | D | E >-2 | M | W | ||
| NOP | I | D | E | M | W | ||
| BEQ R3, R7, label | I | -> D | E | M | W |
Pour un bypass nécessaire en RT, on regardera par exemple :
ADD $3,$4,$5
NOP
BEQ $7,$3,label
Ordre 3 : M@t -> D@t+3
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| LW R3, 0(R5) | I | D | E | M >-3 | W | |||
| NOP | I | D | E | M | W | |||
| NOP | I | D | E | M | W | |||
| BEQ R3, R7, label | I | -> D | E | M | W |
Pour un bypass nécessaire en RT, on regardera par exemple :
LW $3,0($5)
NOP
NOP
BEQ $6,$3,label
On a bien vu les 8 (4*2) bypass du pipeline MIPS.
[pour s’entraîner]
Daniela dessine le schéma simplifié du code corrigé non optimisé.
Le code corrigé non optimisé :
loop:
lb $9,0($4)
beq $9,$0,end_loop
nop
addiu $4,$4,1
addiu $2,$2,1
j end_loop
nop
Comment vraiment bien compter le nombre de cycles :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| I | D | E | M | W | ||||||||
| I | O | O | D | E | M | W | ||||||
| I | D | E | M | W | ||||||||
| I | D | E | M | W | ||||||||
| I | D | E | M | W | ||||||||
| I | D | E | M | W | ||||||||
| I | D | E | M | W |
Soit je commence à 6, mais je dois aller jusqu’à 14 compris : 9 Soit je commence à 5, mais je dois aller jusqu’à 13 compris : 9
On a bien CPI = 9/7 et CPIutile = 9/5
Pareil avec les deux autres, à faire pour s’entraîner.
loop:
lb $8,0($4)
slt $9,$8,$11
slt $10,$12,$8
or $10,$10,$9
bne $10,$0,endif
nop
addi $8, $8, 'A' - 'a'
sb $8,0($4)
endif:
addiu $4,$4,1
bne $8,$0,loop
nop
Trouver les dépendances :
RAW de 3 à 2 RAW de 5 à 4 RAW de 6 à 5 RAW de 9 à 8
En fait, il s’agissait de trouver les dépendances, et pas seulement les dépendances qui introduisent des aléas dans le pipeline :
Donc :
RAW de 3 à 2 RAW de 5 à 4 RAW de 6 à 5 RAW de 9 à 8
Mais aussi
RAW de 4 à 2 (sur $8) RAW de 5 à 3 (sur $9)
RAW de 12 à 8 (sur $8) RAW de 2 à 11 (sur $4, si on part du principe que la boucle reprend)
On doit, lors de l’écriture des schémas simplifiés, traiter les différents résultats des flots de contrôle.
Dans notre cas, les instructions 8 et 9 sont exécutées ou non : on fera donc un schéma simplifié dans le cas où elles le sont et où elles ne le sont pas.
Elles le sont :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| I | D | E | M >-1,2 | W | ||||||||||||
| I | D | O | -> E | M >-2 | W | |||||||||||
| I | O | -> D | E >-1 | M | W | |||||||||||
| O | I | D | -> E >-1 | M | W | |||||||||||
| I | O | -> D | E | M | W | |||||||||||
| O | I | D | E | M | W | |||||||||||
| I | D | E >-1 | M >-1 | W | ||||||||||||
| I | D | -> E | M | W | ||||||||||||
| I | D | E | M | W | ||||||||||||
| I | -> D | E | M | W | ||||||||||||
| I | D | E | M | W |
17 - 5 + 1 = 13
Elles ne le sont pas :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| I | D | E | M | W | ||||||||||
| I | D | O | E | M | W | |||||||||
| I | O | D | E | M | W | |||||||||
| O | I | D | E | M | W | |||||||||
| I | O | D | E | M | W | |||||||||
| O | I | D | E | M | W | |||||||||
| I | D | E | M | W | ||||||||||
| I | D | E | M | W | ||||||||||
| I | D | E | M | W |
15 - 5 + 1 = 11 (c’est bien ça, on doit rajouter les bypass)
CPI moyen (#cycles moyen / #instructions_moyen)
(13 * 30% + 11 * 70%) / (11 * 30% + 9 * 70%)
[on fera le calcul si ça nous amuse]
Transformation du code :
_pgcd_loop:
sltu $8,$4,$5
beq $8,$0, _pgcd_else
nop
sub $5,$5,$4
j _pgcd_endif
nop
_pgcd_else:
sub $4,$4,$5
_pgcd_endif:
bne $4,$5, _pgcd_loop
nop
Les dépendances :
RAW de 3 à 2 (pour $8) RAW de 11 à 9 (pour $4) RAW de 11 à 5 (pour $5)
RAW de 2 à 9 (pour $4) (mais conditionnel)
Le schéma simplifié :
[fait au tableau, à refaire pour s’entraîner]
Le calcul du CPI et du CPI utile
[fait au tableau, à refaire pour s’entraîner]
On ne peut pas vraiment optimiser ce code assembleur :
[remettre le code assembleur]
loop:
lbu $8,0($4)
addu $8,$8,$5
lbu $9,0($8)
sb $9,0($4)
addiu $4,$4,1
bne $4,$10,loop
Trouver les dépendances :
RAW de 3 à 2 RAW de 4 à 3 RAW de 5 à 4 RAW de 7 à 6
RAW de 2 à 6 (over the loop)
Schéma simplifié
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| I | D | E | M >-1 | W | |||||||||
| I | D | O | -> E >-1 | M | W | ||||||||
| I | O | D | -> E | M >-1 | W | ||||||||
| O | I | D | O | E | M | W | |||||||
| I | O | D | E >-1 | M | W | ||||||||
| I | O | -> D | E | M | W | ||||||||
| I | D | E | M | W |
Calculer le CPI
Optimisation :
loop:
lbu $8,0($4)
addiu $4,$4,1
addu $8,$8,$5
lbu $9,0($8)
bne $4,$10,loop
sb $9,-1($4)
Le store byte (les instructions store en général) sont les candidats prioritaires à l’inclusion dans le delayed slot.
CPI égale CPI_utile égale 1.
La démarche en général est assez peu systématisée : en gros on dessine les flots de dépendance entre les instructions, et on essaie de panacher pour éloigner les instructions qui crééent des aléas.
On considère un pipeline un peu modifié.
[à refaire]
On part du principe que MEM1 est bien l’étage le plus long. Mettre un bypass devant MEM1 augmente l’étage déjà le plus long, donc augmente la durée du cycle.
loop:
lbu $8,0($4)
addu $8,$8,$5
lbu $9,0($8)
sb $9,0($4)
addiu $4,$4,1
bne $4,$10,loop
nop
nop
[Fait au tableau, à refaire]
13 cycles pour une itération
1024 * 13 * 2 ns = 26624 ns
Le processeur a un bypass en plus de MEM2 fin à MEM1 début, au prix d’un cycle un peu plus long (2,1 ms au lieu de 2 ms)
On va probablement montrer que le bypass ne vaut pas le coup.
[refaire le schéma simplifié]
12 cycles pour une itération
1024 * 12 * 2,1 = 25804 ns
(Ca ne vaut quand même pas le coup)
La seule bonne manière :
- On met le sb dans le dernier nop
- On panache entre les flux de dépendance
loop:
lbu $8,0($4)
addiu $4,$4,1
addu $8,$8,$5
lbu $9,0($8)
bne $4,$10,loop
nop
sb $9,0($4)
Refaire le schéma simplifié :
Pareil pour PROC2, même ordonnancement
On déroule la boucle :
loop:
lbu $8,0($4)
lbu $12,1($4)
addu $8,$8,$5
addu $12,$12,$5
lbu $9,0($8)
lbu $13,0($12)
sb $9,0($4)
sb $13,1($4)
addiu $4,$4,2
bne $4,$10,loop
nop
nop
Optimisation :
loop:
lbu $8,0($4)
lbu $12,1($4)
addiu $4,$4,2
addu $8,$8,$5
addu $12,$12,$5
lbu $9,0($8)
lbu $13,0($12)
bne $4,$10,loop
sb $9,-2($4)
sb $13,-1($4)
Sans avoir besoin de faire le schéma simplifié, on a un CPI de 1.
[La difficulté vient de l’interprétation à donner à la question] [Il fallait comprendre : le compilateur doit-il insérer des delayed slots ?]
Oui, le compilateur va devoir insérer des delayed slots ?
Combien y a-t-il de delayed slot à insérer ? 3
On a des dépendances de données d’ordre 1 à 6. En effet, c’est seulement à partir de l’instruction i+7 qu’on est sûr qu’une opérande sera bien écrite dans le banc de registre avant sa lecture par l’étage DEC.
Par contre, pour les instructions i+1 à i+6 compris.
Ordre par ordre :
Ordre 1 : E2 fin -> E2 début (pas symétrique : 1 seul)
add $5,$5,$6
sw $5,0($4)
On veut l’adresse [réexpliquer]
Bypass sur RT seulement, l’instruction store est asymétrique
Ordre 2 : E2 fin -> E1 début
add $3,$4,$5
nop
add $7,$3,$6
Bypass sur RS et RT, l’instruction add est symétrique
Pas d’autre bypass d’ordre 2
Ordre 3 : M2 -> E2
lw $3,0($5)
nop
nop
sw $3,0($5)
Bypass sur RT, pas symétrique.
Ordre 3 : E2 -> D2
add $3,$4,$5
nop
nop
add $7,$3,$6
Bypass sur RT et RS, donc 2
Ordre 4 : M2 -> E1
lw $4,0($5)
nop
nop
nop
add $6,$4,$7
Bypass sur RT et RS, symétrique (2)
Ordre 4 : E2 -> D1
add $5,$6,$7
nop
nop
nop
bne $5,$8,label
Bypass sur RT et RS, symétrique (2)
Ordre 5 : M1 -> D1 (symétrique)
add $3,$4,$5
nop
nop
nop
nop
bne $3,$6,label
Ordre 5 : M2 -> D2 (symétrique)
lw $3,0($4)
nop
nop
nop
nop
add $7,$3,$5
Ordre 6 : M2 -> D1 (symétrique)
lw $3,0($4)
nop
nop
nop
nop
nop
bne $3,$5,label
16 pipelines [à recompter]
(Il y aurait toujours un exo avec un pipeline stupide : à refaire et à comprendre pour pouvoir refaire sur un pipeline arbitrairement débile)
Instructions qui produisent 1 cycle de gel.
Ordre 1
add $3,$4,$5
add $7,$3,$6
RAW, 1 cycle de gel
Ordre 2
add $3,$4,$5
nop
bne $3,$6,label
RAW, 2 cycles de gel
Ordre 3
On reprend le précédent, ça fait juste un cycle de gel en moins.
add $3,$4,$5
nop
nop
bne $3,$6,label
RAW, 1 cycle de gel
Ordre 4
lw $3,0($4)
nop
nop
nop
bne $3,$6,label
Deux cycles de gel
Ordre 5
La même, enlève un cycle de gel
lw $3,0($4)
nop
nop
nop
nop
bne $3,$6,label
Un cycle de gel
loop:
lw $8,0($4)
bgez $8,endif
nop
nop
nop
sub $8,$0,$8
sw $8,0($4)
endif:
addiu $4,$4,4
bne $4,$9,loop
nop
nop
nop
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| lw | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 >-1 | W | |||||||||||||||||||
| bgez | I1 | I2 | 0 | 0 | 0 | 0 | 0 | -> D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | I1 | 0 | 0 | 0 | 0 | 0 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | 0 | 0 | 0 | 0 | 0 | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | |||||||||||||||||||
| sub | I1 | I2 | D1 | D2 | E1 | E2 >-1 | M1 | M2 | W | |||||||||||||||||||
| sw | I1 | I2 | D1 | D2 | E1 | -> E2 | M1 | M2 | W | |||||||||||||||||||
| addiu | I1 | I2 | D1 | D2 | E1 | E2 >-1 | M1 | M2 | W | |||||||||||||||||||
| bne | I1 | I2 | 0 | 0 | 0 | -> D1 | D2 | E1 | E2 | M1 | M2 | |||||||||||||||||
| nop | I1 | 0 | 0 | 0 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||||
| nop | 0 | 0 | 0 | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||||
| nop | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W |
Cette question suppose quasiment de refaire un schéma simplifié
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| lw | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 >-1 | W | |||||||||||||||||||
| bgez | I1 | I2 | 0 | 0 | 0 | 0 | 0 | -> D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | I1 | 0 | 0 | 0 | 0 | 0 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | 0 | 0 | 0 | 0 | 0 | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||
| nop | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | |||||||||||||||||||
| addiu | I1 | I2 | D1 | D2 | E1 | E2 >-1 | M1 | M2 | W | |||||||||||||||||||
| bne | I1 | I2 | 0 | 0 | 0 | -> D1 | D2 | M1 | M2 | W | ||||||||||||||||||
| nop | I1 | 0 | 0 | 0 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | ||||||||||||||||
| nop | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W | |||||||||||||||||||
| nop | I1 | I2 | D1 | D2 | E1 | E2 | M1 | M2 | W |
Calcul du nombre de cycles en cas de branchement échoué : 20 Calcul du nombre de cycles en cas de branchement réussi : 18 Nombre de cycle moyen : 19
Instructions brutes en cas de branchement échoué : 12 Instructions brutes en cas de branchement réussi : 10 Nombre d’instructions moyen : 11
Instructions utiles en cas de branchement échoué : 6 Instructions utiles en cas de branchement réussi : 4 Nombre d’instructions utiles moyen : 5
CPI moyen = 19 / 11 CPI utile moyen = 19 / 5
[Apparamment, un schéma simplifié ramène 2-3 points]
Optimisation :
loop:
lw $8,0($4)
addiu $4,$4,4
bgez $8,endif
nop
nop
sub $8,$0,$8 # Execution spéculative
sw $8,-4($4)
endif:
bne $4,$9,loop
nop
nop
nop
Cycles si branchement échoue : 15 Cycles si branchement réussit : 13
On a 5 delayed slots.
On a des dépendances d’ordre 1 à 6.
Les différents bypass, ordre par ordre :
Ordre 1 : E2 fin -> E2 début (pas symétrique : 1 seul)
add $5,$5,$6
sw $5,0($4)
On veut l’adresse au début de l’étage M, mais on ne peut la récupérer qu’en E2 au plus tard.
Ordre 2 : E2 fin -> E1 début
add $3,$4,$5
nop
add $7,$3,$6
Bypass sur RS et RT, l’instruction add est symétrique
Ordre 3 : M2 -> E2
lw $3,0($5)
nop
nop
sw $3,0($5)
Bypass sur RT, pas symétrique.
Ordre 3 : E2 -> D2 (ou M1 -> E1)
add $3,$4,$5
nop
nop
add $7,$3,$6
Bypass sur RT et RS, donc 2 (opération add symétrique)
Ordre 4 : M2 -> E1
lw $4,0($5)
nop
nop
nop
add $6,$4,$7
Bypass sur RT et RS, symétrique (2)
Ordre 5 : M2 -> D2 (symétrique)
lw $3,0($4)
nop
nop
nop
nop
add $7,$3,$5
Ordre 6 : M2 -> D1 (symétrique)
lw $3,0($4)
nop
nop
nop
nop
nop
add $3,$3,$5
loop:
lw $8,0($4)
lw $9,0($4)
sub $10,$8,$9
bgez $10, endif
nop
nop
nop
nop
nop
sub $10,$9,$8
endif:
sw $10,0($5)
addu $5,$5,4
addu $4,$4,4
bne $4,$6,loop
nop
nop
nop
nop
nop
schéma simplifié
[à refaire à la maison, pour s’entraîner]
[entraînement]
Optimisation sans déroulage :
loop:
lw $8,0($4)
lw $9,4($4)
addiu $5,$5,4
addiu $4,$4,4
sub $10,$8,$9
bgez $10,endif
nop
nop
nop
nop
nop
sub $10,$9,$8
endif:
bne $4,$6,loop
sw $10,-4($5)
nop
nop
nop
nop
CPI et CPI utile [refaire les calculs]
[la ]
[la deuxième boucle optimisée]
loop:
lw $8,0($4)
lw $9,4($4)
addiu $5,$5,4
addiu $4,$4,4
sub $10,$8,$9
bne $4,$6,loop
slt $11,$10,$0
sub $12,$0,$11
xor $10,$10,$12
add $10,$10,$11
sw $10,-4($5)
Déroulage de boucle. Dans le cas d’un else, il faut faire deux endif dans la boucle déroulée.
Version déroulée
loop:
lw $8,0($4)
lw $9,4($4)
sub $10,$8,$9
bgez $10,endif
nop
nop
nop
nop
nop
sub $10,$9,$8
endif1:
sw $10,0($5)
lw $18,8($4)
sub $19,$9,$18
bgez $19,endif2
nop
nop
nop
nop
nop
sub $19,$18,$9
endif2:
sw $19,4($5)
addiu $5,$5,8
addiu $4,$4,8
bne $4,$6,loop
nop
nop
nop
nop
nop
Version optimisée :
loop:
lw $8,0($4)
lw $9,4($4)
lw $18,8($4)
addiu $5,$5,8
addiu $4,$4,8
sub $10,$8,$9
sub $19,$9,$18
bgez $10,endif1
nop
nop
nop
nop
nop
sub $10,$9,$8
endif1:
bgez $18,endif2
nop
nop
nop
nop
nop
sub $19,$18,$9
endif2:
bne $4,$6,loop
sw $10,-8($5)
sw $19,-4($5)
nop
nop
nop
Calcul du CPI et du CPI utile.
On traite le pipeline logiciel.
Le code, avec le delayed slot :
loop:
lbu $8,0($4)
addu $8,$8,$5
lbu $9,0($8)
sb $9,0($4)
addiu $4,$4,1
bne $4,$10,loop
nop
On distingue le corps de la boucle des instructions de contrôle de la boucle.
Les trois dernières instructions sont les instructions de contrôle de boucle.
On a un cycle de gel entre lbu et addu, et entre lbu et sb.
Les trois étages du pipeline logiciel seront donc les suivants :
- lbu
- addu + lbu
- sb
Réécrivons le code :
loop:
sb $9,-3($4) # E3(i-2)
addu $8,$8,$5 # E2(i-1)
lbu $9,0($8)
lbu $8,-1($4) # E1(i)
bne $4,$10,loop # Suppose une incrémentation du registre $4 dans le prologue
addiu $4,$4,1
On prendra la peine de rajouter le remplissage, le vidage du pipeline.
[On reprendra ça : pipeline logiciel avec flot de contrôle]
Il y a exactement 16 bypass par opérande : les lister est trivial.
Dans quelles situations peut-on avoir un nop* ?
La classe n’a pas aimé mon formalisme. Alors qu’en vrai c’est archi clair.
[à refaire]
[on a fait une espèce de schéma détaillé des registres I_RI (le tampon d’instructions), I_RD, I_RE, I_RM. Pas sûr que ce soit très utile] [Pris en photo, à reregarder]
[ Fait au tableau, à reprendre ]
[ au papier, à reprendre ] [ jusqu’à fin exercice 2 ]
La fréquence du bus est de l’ordre du dixième de la fréquence du processus.
5 à 10 cycles pour que la mémoire trouve la donnée.
Le CPI qui tient compte de ça se calcule de la manière suivante :
CPI_1 = (#cyclesintrinsèques + #cyclessupplémentaireslecture + #cyclessupplémentairesécriture) / (#instructions)
On n’oubliera pas de compter l’instructions fetch dans les lectures.
On tombe sur 12,2 cycles par instructions [refaire le calcul].
C’est lamentable, on va mettre un cache associatif à deux niveaux.
Interlude tampon d’écriture postée (à reprendre).
Après le cache associatif : 2,72
Après le cache de niveau 2 : 1,69
Après le tampon d’écriture postée : 1,39
Première partie, toute nulle.
La partie sur le cache introduit la notion de Pi-bus.
Le bus est pipeliné.
Un cycle d’arbitrage est obligatoire : le contrôleur de bus va choisir le maître qui a le droit d’écrire.
Puis un cycle d’adresse (l’adresse est envoyée par le maître).
Puis un cycle de données (la donnée est récupérée par le maître).
Un cycle pour mettre à jour le cache.
Un cycle pour répondre au processeur.
1 cycle pour détecter le miss : 1 Obtenir le grant : 6 On envoie 16 adresses, plus 1 dernier data : 17 Màj du cache : 1 Réponse processeur : 1
26 cycles par lecture en cas de miss.
Ecriture : Ecrire dans le buffer : 1 Nombre de cycles pour évacuer une écriture : 1 + 6 + 1 + 1 = 9 cycles 1 cycle par écriture si le tampon n’est pas plein. Si le tampon est plein, ça dépend de quand il sera vide : pas déterministe.
96 miss.
On avait 16 cycles par itération.
17,17 cycles par itération à cause des cycles.