Jo el Gay - lri.frjgay/enseignement/Archi/Archi_slides_part1.pdf · egal a la retenue. Facile a tester. Jo el Gay APP3 - Architecture des ordinateurs Ann ee 2018 2019. Repr esentation

Architecture des ordinateurs

Joel Gay

APP3 - Polytech Paris Sud

Annee 2018− 2019

Joel Gay APP3 - Architecture des ordinateurs Annee 2018 − 2019

Representation de l’information

Plan

1 Representation de l’information

2 Architecture logicielle

3 Micro-architecture

4 Hierarchie memoire


Representation de l’information Introduction

Plan

1 Representation de l’informationIntroductionRepresentation des caracteresRepresentation des entiersRepresentation des reels



Les niveaux d’un systeme informatique

Programmable

Non programmable

Langage machine

Langage Haut niveau

Application

Microarchitecture

Circuits

Programmation

Compilation

Execution



L’information - definitionAnalogique : grandeur continueNumerique : connaissance d’un etats parmi un nombre fini possible

Amplitude

Temps

100

110

111

110

011

001

000 001

101



L’information - definition

Support : la tension, grandeur physique continue

Echantillonnage en fonction du temps : frequence

Seuil de tolerance

V

Tempst1 t2 t3

Etat haut

Etat bas



Quantite d’informations

1 bit : quantite d’information liee a la connaissance d’un etat parmi 2⇒ codage par 0 et 1

Avec n bits, on peut coder 2n etats, donc la quantite d’information

contenue dans la connaissance d’un etat parmi N est

dlog2(N)e bits

Exemple de codage sur 2 bits :

− France : 00

− GB : 01

− Italie : 10

− Espagne : 11



Ordre de grandeurs

Kilo 210 103

Mega 220 106

Giga 230 109

Tera 240 1012

Peta 250 1015

N.B. 210 = 1024.



Quelles informations coder ?

Tous les processeurs :I Nombres

F Entiers naturels et relatifsF Reels

I CaracteresI Instructions

Certains processeurs representent et traitent les vecteurs d’entiers etde reels : on parle de processeurs vectoriels.



Quel type de codage ?

Le codage doit permettre de realiser des operateurs materielsfonctionnels et rapides

Operateur materiel = circuit electronique non programmable.Exemple : un additionneur :

code de 1 code de 2

Additionneur

code de 3



Quel type de codage ?

Les operateurs sont sur un nombre fixe de bits

− caracteristique du processeur et de la technologie des Circuits Integres

− typiquement 32 ou 64 bits

code de 1 code de 2

Additionneur

code de 3

. . . . . .

. . .



Notations humaines

Binaire : 0010110 = 0b0010110 = (0010110)2

Peu pratique pour le traitement manuel

Hexadecimal : en base 16 : un digit pour 4 bits.Ex : 0xAC ; 31 = 16 + 15 = 0x1F.

Decimal binaire Hexa Decimal binaire Hexa

0 0000 0 8 1000 8

1 0001 0 9 1001 9

2 0010 0 10 1010 A

3 0011 0 11 1011 B

4 0100 0 12 1100 C

5 0101 0 13 1101 D

6 0110 0 14 1110 E

7 0111 0 15 1111 F

N.B. Ce ne sont que des notations : on peut melanger les systemesd’ecritures mais attention aux confusions.


Representation de l’information Representation des caracteres

Plan




Codage des caracteres

ASCII (American Standard Code for Information Interchange) :7 bits + 1 bit de pariteCaracteres alphanumeriques latins non accentues + caracteresspeciaux

Latin -1 : 8 bits, standard ISO 8859-1. Caracteresalphanumeriques latins accentues

Unicode : 16 bits, caracteres d ’alphabets varies



Codage ASCII

Decimal Hex Char Decimal Hex Char Decimal Hex Char Decimal Hex Char


Representation de l’information Representation des entiers

Plan




Codage des entiers naturels

Sur n bits, ecriture en base 2 de N :

N =n−1∑i=0

xi2i .

Exemple : 10100101

Sur n bits, les nombres representables sont

[0, 2n − 1]

Exemple sur 8 bits : [0, 255]



Passage decimal ↔ binaire

Passage binaire → decimal :

(10100011)2 = 1︸︷︷︸27

0︸︷︷︸26

1︸︷︷︸25

0︸︷︷︸24

0︸︷︷︸23

0︸︷︷︸22

1︸︷︷︸21

1︸︷︷︸20

= 27+25+21+20 = 163.

Passage decimal → binaire : directement ou par divisioneuclidienne successive :

163 = 2 · 81 + 181 = 2 · 40 + 140 = 2 · 20 + 020 = 2 · 10 + 010 = 2 · 5 + 0

5 = 2 · 2 + 12 = 2 · 1 + 01 = 2 · 0 + 1

Lecture ensens inverse



L’additionneur

Additionneur : circuit materiel qui effectue l’addition naıve desentiers naturels sur n bits et tronque eventuellement la retenue.

a b

Additionneur

r

c

n n

n

1

Operation additionnage notee #a, b operandes; r resultat ; c retenue (carry)

a b r c

0 0 0 0

0 1 1 0

1 0 1 0

1 1 1 1

Additionneur 1 bit.



L’additionneur

Le resultat du calcul dans l’additionneur peut etre faux :probleme de retenue

Sur 3 bits :

001 # 001 = 010 Correct : 1 + 1 = 2001 # 111 = 000 Faux : 1 + 7 6= 0

# est l’addition modulo 2n



Codage des entiers relatifsDefinition :

Codage en complement a 2 sur n bitsI Si N ≥ 0, N est code comme un entier naturelI Si N < 0, N est code par la representation en naturel de 2n + N

Nombres representables :

[−2n−1, 2n−1 − 1].Exemple :

Nombre Code0 0001 0012 0103 011−1 De 8− 1 = 7, soit 111−2 De 8− 2 = 6, soit 110−3 De 8− 3 = 5, soit 101−4 De 8− 4 = 4, soit 100

010 2

001

1000

0

111

−1

110−2

101

−3100

−4

011

3



Proprietes du codage en complement a 2

Le bit de poids fort :I des positifs est 0I des negatifs est 1

La representation de −1 est le mot ou tous les bits sont a 1 : 0xFF(8bits), 0xFFFF (16bits) etc.

L’oppose d’un relatif s’obtient en complementant bit a bit et enajoutant 1.Exemples : 2 est code par 010 sur 3 bits. Comment coder −2 ?Complement bit a bit : 101On ajoute 1 : −2 est donc code sur 3 bits par 110.Dans l’autre sens, faire les memes operations : 110→ 001→ 010.

Le codage de −2n−1 est 1 suivi de n − 1 zeros. En effet :

10000000complement−−−−−−−→ 01111111

+1−−→ 10000000.



Extension de signe

Soit un relatif represente en complement a 2 sur n bits.Sa representation en complement a 2 sur m > n bits s’obtient enrepliquant le bit de poids fort sur les bits manquants.

5 s’ecrit 0b0101 sur 4 bits, et −5 s’ecrit 0b1011. On etend a 8 ou 16 bits :

∗ 5 est represente sur 8 bits par 0b00000101

∗ 5 est represente sur 16 bits par 0b0000000000000101

∗ −5 est represente sur 8 bits par 0b11111011

∗ −5 est represente sur 16 bits par 0b1111111111111011

Notation: ESm(Immn)



Operations arithmetiques

Le circuit additionneur peut effectuer aussi l’addition des relatifs s’ilssont codes en complement a 2 : 1 seul et meme circuit

code de 1 code de 2

Additionneur

code de 3

code de 1 code de −2

Additionneur

code de −1



Additions des relatifs

Le resultat du calcul dans l’additionneur peut etre faux : overflow

Sur 3 bits :

001 # 001 = 010 correct : 1 + 1 = 2001 # 110 = 111 correct : 1 + (−2) = −1111 # 111 = 110 correct : −1 + −1 = −2011 # 001 = 100 faux : 3 + 1 n’est pas codable110 # 101 = 011 faux : −2 + (−3) n’est pas codable

Attention : retenue 6= overflow.



Addition des relatifs

On demontre :

L’additionnage des codes de deux relatifs N et M est egal aN + M si et seulement si N + M est codable.

L’additionneur est aussi satisfaisant que possible.

L’additionnage des codes de deux relatifs N et M est egal aN + M si et seulement si :

I N et M sont de signes contraires.I Ou bien N et M sont de meme signe, et le bit de signe du resultat est

egal a la retenue.

Facile a tester.



Conclusion

Avec les codages choisis, l’additionneur effectue l’addition desnaturels et des relatifs aussi bien que possible : tout resultatrepresentable est correctement calcule.Mais le resultat peut etre faux s’il n’appartient pas a l’ensembled’entiers representables.

I Analyser l’application et le programme pour garantir que leresultat reste codable.

I Si ce n’est pas possible, specifier le comportement sur overflowet utiliser les ressources de l’environnement pour le detecter etrealiser l’action specifiee.


Representation de l’information Representation des reels

Plan




Codage des reels

Problemes :I Arrondir.I Representer equitablement des nombres tres grands et tres petits.

Principe : representation normalisee par mantisse etexposant, avec un choix judicieux des valeurs del’exposant.



Codage IEEE 754 simple precision

s E f

1 8 23

31 30 23 22 0

E = interpretation en naturel.Pour E 6= 0 et E 6= 255, la valeur codee est :

(−1)s · 2E−127 · 1, f

ou 1, f doit etre interprete en base 2.Soit e = E − 127. Alors −127 ≤ e ≤ 128.



Codage IEEE 754 simple precision - decodage

1 100 1000 1 001 0000 0000 0000 0000 0000

1 8 23

31 30 23 22 0

Que represente 0xC8900000 = 0b 1100 1000 10010 . . . 0 ?s = 1 ; E = 10010001 = 145 donc e = 18 ;f = 0010 . . . 0 donc m = (1, f )2 = (1, 001)2 = 1 + 2−3 ;Le nombre code est −218(1 + 2−3).



Codage IEEE 754 simple precision - codage

Codage de 2, 52, 5 = 5× 2−1 = 1012 × 2−1 = 1, 012 × 21

E = 127 + 1 = 128 ; f = 01codage : 010000000010 . . . 0 = 0x40200000

Codage de 0, 750, 75 = 3× 2−2 = (2 + 1)× 2−2 = (1 + 2−1)× 2−1 = 1, 12 × 2−1

E = 127− 1 = 126 ; f = 1codage : 00111111010 . . . 0 = 0x3F400000



Codage IEEE 754 simple precision

Les cas exceptionnels

s E f

1 8 23

31 30 23 22 0

Nom E f valeurDenormalise 0 non 0 (−1)s · 2−127 · 0, fZero 0 0 0

Infini 255 0 (−1)s · ∞NaN 255 non 0 Not a number



L’addition des flottants

Idee de base : se ramener a la meme puissance de 2 puis sommer enfaisant les arrondis necessaires.

1. Comparaison des exposants2, 5 = 1, 012 × 21

0, 75 = 1, 12 × 2−1

2. Decalage a droite de la Difference de 2mantisse du plus petit nombre 0, 75 = 0, 0112 × 21

3. Somme des mantisses 1, 012 + 0, 0112 = 1, 1012

4. Normalisation du resultat Normalise

5. Traitement cas exceptionnels Non

Resultat : 1, 1012 × 21 = 3, 25.




1. Comparaison des exposants2, 5 = 1, 012 × 21

3, 25 = 1, 1012 × 21

2. Decalage a droite de la Difference de 0mantisse du plus petit nombre


4. Normalisation du resultat 10, 1112 × 21 = 1, 01112 × 22

5. Traitement cas exceptionnels Non

Resultat : 1, 01112 × 22 = 5, 75.




1. Comparaison des exposants230 = 1, 02 × 230

3, 25 = 1, 1012 × 21

2. Decalage a droite de la Difference de 29mantisse du plus petit nombre Mantisse mise a 0


4. Normalisation du resultat Normalise

5. Traitement cas exceptionnels Arrondi

Resultat : 230.



Erreurs d’arrondi

Le resultat d’une addition est souvent faux.Mais le standard impose que le resultat soit le resultat exactarrondi, avec des choix possibles :

I Au plus pres / Valeur Inferieure / Valeur superieureI Mais 230 + 3, 25 a pour resultat 230.

Realise avec 3 bits supplementaires seulement.

L’addition n’est plus associative :

(−230 + 230) + 3, 25 = 3, 25

−230 + (230 + 3, 25) = 0

Le traitement des erreurs d’arrondi dans les methodes numeriquesest une composante essentielle de l’informatique numerique

I Methodes mathematiques.I Tres bien connu pour l’algebre lineaire et encapsule dans des

bibliotheques dont l’utilisation est imperative.I Beaucoup moins bien en simulation.



Un bug a $7 milliards : Ariane V

39 seconds: self-destruct, triggered automatically because aerodynamic forces wereripping the boosters from the rocket.

Just before: This disintegration had begun an instant before, when the spacecraftswerved off course under the pressure of the three powerful nozzles in its boostersand main engine. The rocket was making an abrupt course correction that was notneeded, compensating for a wrong turn that had not taken place.

Steering was controlled by the on-board computer, which mistakenly thought therocket needed a course change because of numbers coming from the inertialguidance system. That device uses gyroscopes and accelerometers to track motion.The numbers looked like flight data – bizarre and impossible flight data – but wereactually a diagnostic error message. The guidance system had in fact shut down.

36.7 seconds after launch: shutdown of the guidance system when trying toconvert the sideways velocity of the rocket from a 64-bit floating point format to a16-bit integer. The number was too big, and an overflow error resulted. When theguidance system shut down, it passed control to an identical, redundant unit,which was there to provide backup in case of just such a failure. But the secondunit had failed in the identical manner a few milliseconds before. And why not? Itwas running the same software.



Arithmetique des cas exceptionnels

Arithmetique etendueI Infini : trop grand, regles classiquesI NaN : not a number, operation hors de l’ensemble de definition. NaN

est absorbant.

Denormalise simple precisionI Motivation :

la difference de deux nombres representables peut ne pas l’etre.1, 11 . . . 12 × 2−126 − 1, 10 . . . 02 × 2−126 = 0, 0 . . . 01× 2−126 = 2−149

n’est pas representable. Donc les tests x == y (comparaison des bits)et x − y = 0 ne seraient pas equivalents.

I Evidemment, le meme probleme existe pour la difference de deuxdenormalises.



Traitement des cas exceptionnels

Comportements souhaitablesI Arret immediat :

x/(1 + x2) pour x = 265 produit x2 =∞, resultat 0 alors que le resultat est

de l’ordre de 1/x , donc representable. Pas d’interet a continuer le calcul.I Aucune action

Arrondi presque toujoursDenormalise si pas de soustraction problematique

I Traitement par l’applicationMethodes d’exploration : la valeur peut tomber en dehors de l’ensemble dedefinition

Support au niveau de la normeI Fonctionnement par defaut : continuer dans l’arithmetique etendueI Enregistrement des evenements anormaux dans des drapeauxI Fortement conseille : gestionnaire d’exception

F Traitement par le logiciel de baseF Souvent arret immediat



Evenements anormaux - drapeaux

Drapeau Condition ResultatUnderflow Nb trop petit 0, xmin, nombre

denormaliseOverflow Nb trop grand ±∞, xmaxDivision by 0 Division par 0 ±∞Invalid operation Resultat NaN avec NaN

operandes non NaN :0/0, ∞/∞, ∞−∞,0×∞, parfois 1∞

Inexact Arrondi Resultat arrondi


Architecture logicielle

Plan

1 Representation de l’information

2 Architecture logicielle

3 Micro-architecture

4 Hierarchie memoire


Architecture logicielle Modele de Von-Neumann

Plan

2 Architecture logicielleModele de Von-NeumannFormat des instructionsInstructions arithmetiquesInstructions d’acces memoireInstructions de controleProcedures



Modele d’ordinateur de Von Neumann

Memoire

UAL

Unite de controle

Accumulateur

Processeur (CPU)

Sorties

Entrees



Modele d’ordinateur de Von Neumann

Memoire = Instruction et donnees

Processeur :I Tant que true faireI Lire instruction : RI ← Mem[PC] ; PC ← PC+1I Executer instruction : suite d’actions dependant de l’instruction

CPU

RI

PC = x

Memoire

Inst J + 1Inst J x

x + 1

Donnees

Addresses

RI : Registre d’instructions



Les niveaux d’un systeme informatique

Programmable

Non programmable

Langage machine

Langage Haut niveau

Application

Microarchitecture

Circuits

Programmation

Compilation

Execution



Architecture logicielle

On considere le processeur tel que le voit lecompilateur, ou un programmeur d’applicationsspecifiques bas niveau : interface de programmation

Utilisation d’un langage-machine = jeu d’instructions= ”assembleur”

Dans toute la suite, on considere un sous-ensemble dujeu d’instructions MIPS.



Le processeur : partie operative

Calcul uniquement sur lesregistres

Architecture materielle RISC(Reduced Instruction SetComputer)

Registres : Organes destockage a l’interieur duprocesseur (accumulateur).Chacun contient 1 mot.

UAL : operationsadditionnage, soustraction,division et multiplication parpuissances de 2 etc.

UAL

...

R31

R0

Memoire

RI

PC



Caracteristiques elementaires du CPU

Largeur du chemin dedonnees = taille de l’UAL :32 ou 64 bits. 32 bit pourMIPS.

R0 toujours 0 pour MIPS

Chaque registre a la memetaille que le chemin dedonnees.

3232 32

UAL

...

R31

R0



Caracteristiques elementaires de la memoire

Tableau de mots de largeur fixe p. Pournous par octets (p=8).

Accessible chacun par leur adresse

Taille = nombre de mots memoire n.n

p



Un exempleInstruction d’affectation LHN (Langage Haut Niveau) :

int A, B, C ;

A = B + C ;

Comment sont stockees les variables A, B et C ?Comment effectuer le calcul ?

Charger B depuis la memoire vers le CPULOAD R1, ”adresse de B”Charger C depuis la memoire vers le CPULOAD R2, ”adresse de C”Effectuer : R3 ← R1 + R2ADD R3, R2, R1Stocker le resultat en memoireSTORE R3, ”adresse de A”

UAL

R1

R2

R3

Memoire



Langages de haut niveau

Structures de donnees : Scalaires, Tableaux, Listes,Produits, etc.

Affectations : A = B + C + D

ControleI Sequence : Instruction1 ; Instruction2I ConditionnellesI BouclesI Appels de procedures et fonctions



Types de donnees

Un type decrit en general : encombrement memoire etles operateurs admissibles

Ici les operateurs sont materiels, donc les types sont :I Entiers signes et non signes : taille du chemin de donneesI Flottants : 32 ou 64 bits


Architecture logicielle Format des instructions

Plan




Format des instructions

Qu’est-ce qu’une instruction ?

Chaıne de bits respectant un format

CODOP Rs Rt Rd Shamt funct

6 5 5 5 5 6

000000 00001 00010 00011 00000 100000

⇒ 0x00221420

31 26 25 21 20 16 15 11 10 6 5 0

Version lisible par un humain, assembleur

ADD R3, R1, R2



Formats MIPS

Registre-Registre

CODOP Rs Rt Rd Shamt funct

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

Registre-Immediat

CODOP Rs Rt Immediat

6 5 5 16

31 26 25 21 20 16 15 0

Sauts

CODOP Immediat

5 27

31 27 26 0



Operandes

2 operandes d’entree et 1 resultat = 3 operandes a decrire dansl’instruction

Modes d’acces (d’adressage) a un operandeI Registre

F L’operande est dans un registreF Le registre est decrit par son numero, sur 5 bits

I ImmediatF L’operande est dans l’instruction, sur les 16 bits de poids faibleF Problematique, voir plus loin

I Le resultat est toujours en registre !

Format R-R : tous les operandes en registre

Format R-I : un des operandes source est un immediat



Quelques instructions MIPS (1)

31 26 25 21 20 16 15 11 10 6 5 0 R[$x]&indicates&the&register&with&address&xopcode rs rt rd shamt funct R-type BMEM&indicates&a&byte&aligned&access&to&memory opcode rs rt I-type HMEM&indicates&a&half&word&aligned&access&to&memoryopcode J-type WMEM&indicates&a&word&aligned&access&to&memory

Name Mnemonic RTL Description

100000 base dest Load Byte LB rt,offset(rs) R[$rt] = SignEXT(BMEM[(R[$rs]+ SignEXT(imm))[31:0]])

100001 base dest Load Halfword LH rt,offset(rs) R[$rt] = SignEXT(HMEM[(R[$rs]+ SignEXT(imm))[31:1]])

100011 base dest Load Word LW rt,offset(rs) R[$rt] = WMEM[(R[$rs]+ SignEXT(imm))[31:2]]

100100 base dest Load Byte Unsigned LBU rt,offset(rs) R[$rt] = ZeroEXT(BMEM[(R[$rs]+ SignEXT(imm))[31:0]])

100101 base dest Load Halfword Unsigned LHU rt,offset(rs) R[$rt] = ZeroEXT(HMEM[(R[$rs]+ SignEXT(imm))[31:1]])

101000 base dest Store Byte SB rt,offset(rs) BMEM[(R[$rs]+SignEXT(imm))[31:0]] = R[$rt][7:0]

101001 base dest Store Halfword SH rt,offset(rs) HMEM[(R[$rs]+SignEXT(imm))[31:1]] = R[$rt][15:0]

101011 base dest Store Word SW rt,offset(rs) WMEM[(R[$rs]+SignEXT(imm))[31:2]] = R[$rt]

Name Mnemonic RTL Description

000000 000000 src dest shamt 000000 Shift Left Logical SLL rd, rt, shamt R[$rd] = R[$rt] << shamt

000000 000000 src dest shamt 000010 Shift Right Logical SRL rd, rt, shamt R[$rd] = R[$rt] >> shamt

000000 000000 src dest shamt 000011 Shift Right Arithmetic SRA rd, rt, shamt R[$rd] = R[$rt] >>> shamt

000000 src1 src2 dest 000000 100000 Add (with overflow) ADD rd, rs, rt R[$rd] = R[$rs] + R[$rt]

000000 src1 src2 dest 000000 100001 Add Unsig. (no overflow) ADDU rd, rs, rt R[$rd] = R[$rs] + R[$rt]

000000 src1 src2 dest 000000 100010 Subtract SUB rd, rs, rt R[$rd] = R[$rs] - R[$rt]

000000 src1 src2 dest 000000 100011 Subtract Unsigned SUBU rd, rs, rt R[$rd] = R[$rs] - R[$rt]

000000 src1 src2 dest 000000 100100 And AND rd, rs, rt R[$rd] = R[$rs] & R[$rt]

000000 src1 src2 dest 000000 100101 Or OR rd, rs, rt R[$rd] = R[$rs] | R[$rt]

000000 src1 src2 dest 000000 100110 Xor XOR rd, rs, rt R[$rd] = R[$rs] ^ R[$rt]

000000 src1 src2 dest 000000 100111 Nor NOR rd, rs, rt R[$rd] = ~R[$rs] & ~R[$rt]

000000 src1 src2 dest 000000 101010 Set Less Than SLT rd, rs, rt R[$rd] = R[$rs] < R[$rt]

000000 src1 src2 dest 000000 101011 Set Less Than Unsig. SLTU rd, rs, rt R[$rd] = R[$rs] < R[$rt]

signed offset

signed offset

MIPS Reference Sheet

R-Type Computational Instructions

Load and Store Instructions

signed offset

signed offset

immediatetarget

signed offset

signed offset

signed offset

signed offset



Quelques instructions MIPS (2)

31 26 25 21 20 16 15 11 10 6 5 0 R[$x]&indicates&the&register&with&address&xopcode rs rt rd shamt funct R-type BMEM&indicates&a&byte&aligned&access&to&memory opcode rs rt I-type HMEM&indicates&a&half&word&aligned&access&to&memoryopcode J-type WMEM&indicates&a&word&aligned&access&to&memory

Name Mnemonic RTL$Description

001001 src dest Add Imm. Unsigned ADDIU rt, rs, signed-imm. R[$rt] = R[$rs] + SignEXT(imm)

001010 src dest Set Less Than Imm. SLTI rt, rs, signed-imm. R[$rt] = R[$rs] < SignEXT(imm)

001011 src dest Set Less Than Imm. Unsig. SLTIU rt, rs, signed-imm. R[$rt] = R[$rs] < SignEXT(imm)

001100 src dest And Immediate ANDI rt, rs, zero-ext-imm. R[$rt] = R[$rs] & ZeroEXT(imm)

001101 src dest Or Immediate ORI rt, rs, zero-ext-imm. R[$rt] = R[$rs] | ZeroEXT(imm)

001110 src dest Xor Immediate XORI rt, rs, zero-ext-imm. R[$rt] = R[$rs] ^ ZeroEXT(imm)

001111 00000 dest Load Upper Imm. LUI rt, zero-ext-imm. R[$rt] = {imm, 0x0000}

Jump and Branch Instructions Name Mnemonic RTL$Description

000010 Jump J target PC = {PC[31:28], target, 00}

000011 Jump and Link JAL target R[31] = PC + 8;PC = {PC[31:28], target, 00}

000000 src 00000 00000 00000 001000 Jump Register JR rs PC = R[$rs]

000000 src 00000 dest 00000 001001 Jump and Link Register JALR rd, rs R[$rd] = PC + 8;PC = R[$rs]

000100 src1 src2 Branch On Equal BEQ rs, rt, offset PC = PC + 4 + (R[$rs] == R[$rt] ? SignEXT(imm) << 2 : 0)

000101 src1 src2 Branch On Not Equal BNE rs, rt, offset PC = PC + 4 + (R[$rs] != R[$rt] ? SignEXT(imm) << 2 : 0)

000110 src 00000 Branch On Less Than or Equal to Zero

BLEZ rs, offset PC = PC + 4 + (R[$rs] <= 0 ? SignEXT(imm) << 2 : 0)

000111 src 00000 Branch on Greater than Zero BGTZ rs, offset PC = PC + 4 + (R[$rs] > 0 ? SignEXT(imm) << 2 : 0)

000001 src 00000 Branch on Less Than Zero BLTZ rs, offset PC = PC + 4 + (R[$rs] < 0 ? SignEXT(imm) << 2 : 0)

000001 src 00001Branch on Greater than or Equal to Zero

BGEZ rs, offset PC = PC + 4 + (R[$rs] >= 0 ? SignEXT(imm) << 2 : 0)

Name Mnemonic RTL$DescriptionBranch Less Than BLT rs, rt, label if(R[$rs]<R[$rt]) PC = Label

Branch Greater Than BGT rs, rt, label if(R[$rs]>R[$rt]) PC = Label

Branch Less Than or Equal BLE rs, rt, label if(R[$rs]<=R[$rt]) PC = Label

Branch Greater Than or Equal BGE rs, rt, label if(R[$rs]>=R[$rt]) PC = Label

Load Immediate li rd, immediate R[$rd] = immediate

Move move rd, rs R[$rd] = R[$rs]

These are simple assembly language instructions that do not have adirect machine language equivalent. During assembly, the assembler

translates each psedudoinstruction into one or more machine languageinstructions.

target

target

signed offset

signed offset

signed offset

signed offset

signed offset

signed immediate

signed immediate

signed immediate

I-Type Computational Instructions

Pseudoinstruction Set

MIPS Reference Sheet

immediatetarget

signed offset

zero-ext. immediate

zero-ext. immediate

zero-ext. immediate

zero-ext. immediate


Architecture logicielle Instructions arithmetiques

Plan




Instructions arithmetiques et logiques

ArithmetiquesI ADD, SUB et variantes : addition, soustraction

LogiquesI AND, OR, XOR et variantes : operations logiques bit a bit

ExemplesI Etat initial R1 = 0x00001000, R2 = 0xEF125634I ADD R3, R2, R1 : R3← 0xEF126634I AND R3, R2, R1 : R3← 0x00001000



Instructions d’addition (1)

ADD

000000 Rs Rt Rd 00000 100000

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-RI Syntaxe ADD Rd, Rs, RtI Effet Rd ← Rs + Rt si resultat representable en interpretation en

relatifs, trap on overflow sinon.I Exemple : ADD R3, R1, R2

F Initialement R1= 0x00000000 et R2 =0x12345678F code 0b000000 00001 00010 00011 00000 100000 = 0x00221820F si initialement R1 = 0x00000001, effet R3 = 0x12345679F si initialement R1 = 0x70000000, effet R3 inchange et exception




ADDU

000000 Rs Rt Rd 00000 100001

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-RI Syntaxe ADDU Rd, Rs, RtI Effet Rd ← Rs + Rt au sens additionnageI Exemple : ADDU R3, R1, R2

F Initialement R1= 0x00000000 et R2 =0x12345678F code 0b000000 00001 00010 00011 00000 100001 = 0x00221821F si initialement R1 = 0x00000001, effet R3 = 0x12345679F si initialement R1 = 0x70000000, effet R3 = 0x82345679




ADDI

001000 Rs Rt Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe ADDI Rt, Rs, Imm16

I Effet Rt ← Rs + ES32(Imm16) si resultat representable eninterpretation en relatifs, trap on overflow sinon.

I Exemples. Initialement R2= 0x00000000 et R1 = 0x12345678F ADDI R2, R1, 9

Code 0b001000 00001 00010 0. . . 01001 = 0x20220009Resultat R2 = 0x12345681

F ADDI R2, R1, -1Code 0b001000 00001 000010 1. . . 1 = 0x2022FFFFResultat R2 = 0x12345677




ADDIU


6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe ADDI Rt, Rs, Imm16

I Effet Rd ← Rs + ES32(Imm16) au sens additionnageI Exemples.

F Initialement R1 = 0x7FFFFFFFADDI R2, R1, 1 : Resultat R2 = 0x80000000

F Initialement R1 = 0xFFFFFFFFADDI R2, R1, 9 : Resultat R2 = 0x00000008

F Initialement R1 = 0x80000000ADDI R2, R1, -1 : Resultat R2 = 0x7FFFFFFF



Instruction addition Registre-Immediat

Application : compiler l’evaluation des expressionscontenant des constantes

Y = X + 12

Se compile en

< charger X dans R1 >

ADDI (ou ADDIU) R2, R1, 12

< ranger R2 dans Y >

Mais comment compiler Y = X + 0x12345678 ?



Instruction LUI

LUI

001111 00000 Rt Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe LUI Rt, Imm16

I Effet Rt ← Imm16 || 0x0000I Exemple LUI R1, 0x1234. Effet : R1 = 0x12340000.I Usage

F Compiler les expressions faisant intervenir des constantes entieres surplus de 16 bits, par exemple Y= X + 0x12345678.

F En langage assembleur, on utilise la pseudo-instruction LI, qui estimplementee a partir de LUI (voir TD). On ne peut pas avoir 32 bitsdans une instruction 32 bits !



Instructions logiques (1)

AND

000000 Rs Rt Rd 00000 100100

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-RI Syntaxe AND Rd, Rt, RsI Effet Rd ← Rs AND Rt au sens bit-a-bitI Exemple. Initialement R1 =0x12345678 et R3= 0x00000000

F si R2 = 0x00000041, effet R3 = 00000040



Instructions logiques (2)

ANDI


6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe ANDI Rt, Rs, Imm16

I Effet Rt ← Rs AND EZ32(Imm16) au sens bit-a-bitI Exemple. Initialement R1 =0x12345678 et R2= 0x00000000

F ANDI R2, R1, 0x0041 effet R2 = 0x00000040F ANDI R2, R1, 0xFF41 effet R2 = 0x00005640

Autres instructions logiques (OR, ORI, NOR, NOT, XOR, XORI)dans la feuille MIPS de reference.



Instructions de decalage (1)

SLL : Shift Left Logical

000000 00000 Rt Rd Imm5 000000

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-R, bits 21-25 non significatifs (0)I Syntaxe SLL Rd, Rt, Imm5

I Effet Rd ← Rt decale a gauche de Imm5 interprete en non signe.NB: C’est donc la multiplication non signee par 2Imm5 si le resultat estrepresentable

I Exemple : SLL R2, R1, 8F Initial R1 = 0x00070000F Resultat R2 = 0x07000000



Instructions de decalage (2)

SRL : Shift Right LogicalI Syntaxe SRL Rd, Rt, Imm5

I Effet Rd ← Rt decale a droite de Imm5, avec extension a zeroNB: Division en entiers naturels par 2Imm5 si representable.

SRA : Shift Right ArithmeticI Syntaxe SRL Rd, Rt, Imm5

I Effet Rd ← Rt decale a droite de Imm5, avec extension de signe

ExemplesI SRL R2, R1, 12 avec R1=0xFFFFFFFF, resultat R2 = 0x000FFFFFI SRA R2, R1, 12 avec R1=0xFFFFFFFF, resultat R2 = 0xFFFFFFFF



Calculs de conditionsSLT

000000 Rs Rt Rd 00000 101010

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-RI Syntaxe SLT Rd, Rs, RtI Effet Si Rs < Rt en signe, Rd ← 1, sinon Rd ← 0.

SLTI


6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe SLTI Rt, Rs, Imm16

I Effet si Rs < ES32(Imm16) en signe, Rd ← 1, sinon Rd ← 0.

SLTU, SLTIU : comparaison non signee



Instructions conditionnelles

Limites a des MOV :I MOVN

F Syntaxe MOVN Rd, Rs, RtF Effet si Rt 6= 0, Rd ← Rs

I MOVZF Syntaxe MOVZ Rd, Rs, RtF Effet si Rt = 0, Rd ← Rs

Exemple de programme :

Min Signe (R8, R9)

SLT R1, R8, R9

MOVN R9, R8, R1



A retenir sur “l’assembleur”

On a vu les instructions sous representation alphanumerique duformat, pour la commodite de l’interaction homme-machine.Exemple : ADD R1, R2, R3.On peut trouver de telles instructions :

I En programmation directe (cf. TP)I Comme resultat de la compilation (sous Unix, Option -S)

On a vu comment coder les instructions (codage) : del’alphanumerique vers le binaire.


Architecture logicielle Instructions d’acces memoire

Plan




Instruction d’acces memoire

Chargement : de la memoire vers le processeur

Rangement : du processeur vers la memoire

MIPS : uniquement format R-I

Point delicat : la memoire est organisee par octets,mais le chemin de donnees est 32 bits.



Representation des variables en memoire

Dans quel ordre placer les variables multi-octets ?

int x = 0x12345678 ;

Memoire organisee en big endian

78563412

0x000010030x000010020x000010010x00001000

Memoire organisee en little endian

12345678

0x000010030x000010020x000010010x00001000

On se met en cadre big endian pour la suite.



Chargement

LW : Load Word

100011 base Rt Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Syntaxe LW Rt, Imm16 (base)I Effet Rt ← Mem32 [base + ES(Imm16)]I L’immediat est appele parfois offset :

decalage.I NB: attention aux questions d’alignement, ici

multiple de 4 (voir + loin)I Exemples

LW R2, 0(R1) R2 ← 0x12345678LW R2, 4(R1) R2 ← 0xABCDEF09

09

EF

CD

AB

78

56

34

12

1007

1006

1005

1004

1003

1002

1001

1000

R1 = 0x00001000

Etat initial



Rangement

SW : Store Word

101011 base Rt Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Syntaxe SW Rt, Imm16 (base)I Effet Mem32 [base + ES(Imm16)] ← RtI NB: attention aux questions d’alignementI Exemple :

09

EF

CD

AB

78

56

34

12

1007

1006

1005

1004

1003

1002

1001

1000

R1 = 0x00001000 et R2 = 0xEF125634

Etat initial

09

EF

CD

AB

34

56

12

EF

1007

1006

1005

1004

1003

1002

1001

1000

SW R2, 0(R1)Effet des instructions




Les types elementaires des LHN correspondent a un nombreprecis d’octets :

Caracteres char 1Entiers courts short 2Entiers int 4Flottants simple precision float 4Flottants double precision double 8

Alignement : a la compilation, les variables sont alignees sur leursfrontieres naturelles = adresses multiples de leurs tailles.

Instructions Nom Multiple deSB, LB Byte 1SH, LH Half-word 2SW, LW Word 4




Tableaux : stockes sequentiellement a partir de l’adresse dupremier element

Adresse(tab[i]) = Adresse(tab[0]) + i * sizeof(element tableau)

Programme en C : echange

int v[N], k, temp ;

temp = v[k] ;

v[k] = v[k+1] ;

v[k+1] = temp ;

Assembleur

Initialement, R1 = v[0], R2 = kSLL R2, R2, 2 ; k ← k*4ADD R2, R2, R1 ; R2 ← v[k]LW R3, 0(R2) ; temp = R3 ← v[k]LW R4, 4(R2) ; R4 ← v[k+1]SW R4, 0(R2) ; v[k] ← R4SW R3, 4(R2) ; v[k+1] ← temp


Architecture logicielle Instructions de controle

Plan




Instructions de branchement

Comment realiser les ruptures de sequence ?

Branchements : deplacement relatif

PC ← PC + depct

Sauts

PC ← adresseNB :

I PC pointe l’instruction qui suit le branchementI Les instructions occupent 4 octets et sont aligneesI En MIPS vrai, l’instruction qui suit le branchement ou le saut (delay

slot) est executee. Le cours et les TD ne sont pas conformes au MIPSsur ce point.



Instructions de branchement (1)

BLEZ

000110 Rs 00000 Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe BLEZ Rs, Imm16

I Effet Si Rs ≤ 0, PC ← PC + ES(Imm16 || 0b00)I Exemples

F BLEZ R0, Imm16 est un branchement inconditionnel BA (Branch At).Pour les exercices papier, on peut utiliser la fausse pseudo-instructionBA

F SI BLEZ est a l’adresse 0x10000000, BLEZ R0, 16 branche a l’adresse0x10000040.



Instructions de branchement (2)

BGEZ

000001 Rs 00001 Immediat

6 5 5 16

31 26 25 21 20 16 15 0

I Format R-II Syntaxe BGEZ Rs, Imm16

I Effet Si Rs ≥ 0, PC ← PC + ES(Imm16 || 0b00)



Compilation des conditionnelles

LHN :

Si condition

alors

Bloc1

sinon

Bloc2

Assembleur :

Bcond vraiInstructions du bloc 2BA lsuite

vrai: Instructions du bloc 1suite: . . .

Exemple : placer dans R1 la valeur absolue de R2

Version litterale

BGEZ R2, pos ; R2 ≥ 0 ?NEGU R1, R2 ; R1 = −R2B suite

Pos: MOV R1, R2 ; R1 ← R2Suite: . . .

Version optimisee

MOV R1, R2 ; R1 = R2 ?BGEZ R1, suiteNEGU R1, R1

Suite: . . .



Conditionnelles

Rappel : Instructions conditionnelles :I MOVN

F Syntaxe MOVN Rd, Rs, RtF Effet si Rt 6= 0 Rd ← Rs

I MOVZF Syntaxe MOVZ Rd, Rs, RtF Effet si Rt = 0 Rd ← Rs

Utilisation des instructions conditionnelles : eviter les branchements.

Exemple : placer dans R1 la valeur absolue de R2

Version optimisee

MOV R1, R2BGEZ R1, suiteNEGU R1, R1

Suite: . . .

Version sans branchements

NEGU R1, R2 ; R1 = −R2SLT R3, R1, R0 ; R3 = (R1 < 0)MOVN R1, R2, R3 ; si (R1 < 0) corriger



Boucles : principes generaux

Tant que : un branchement conditionnel + un branchementinconditionnel

Boucle: bcht cond fausse Suitecorps bouclebcht incond Boucle

Suite:

for, repetition : un seul branchement, conditionnel

Boucle: corps bouclebcht cond vraie Boucle



Boucles : exemple (1)

int a[100], b[100];

for (i=0; i < 100; i++) a[i] = b[i] +10 ;

Initialement : R4 = b[0] et R5 = a[0]

ADDI R6,R5,400 ; R6 ← premiere adresse invalideloop: LW R7,0(R5) ; R7 ← b[i]

ADDI R7,R7,10 ; R7 ← b[i]+10SW R7,0(R4) ; a[i] ← R7ADDI R5,R5,4 ; i++ pour bADDI R4,R4,4 ; i++ pour aBNE R5,R6,loop ; branche si i < n




char a[100], b[100];

for (i=0; i < 100; i++) a[i] = b[i] +10 ;


ADDI R6,R5,100 ; R6 ← premiere adresse invalideloop: LB R7,0(R5) ; R7 ← b[i]

ADDI R7,R7,10 ; R7 ← b[i]+10SB R7,0(R4) ; a[i] ← R7ADDI R5,R5,1 ; i++ pour bADDI R4,R4,1 ; i++ pour aBNE R5,R6,loop ; branche si i < n




int a[100], b[100];

for (i=0; i < 99; i++) a[i+1] = b[i] +10 ;


ADDI R6,R5,396 ; R6 ← premiere adresse invalideloop: LW R7,0(R5) ; R7 ← b[i]

ADDI R7,R7,10 ; R7 ← b[i]+10SW R7,4(R4) ; a[i] ← R7ADDI R5,R5,4 ; i++ pour bADDI R4,R4,4 ; i++ pour aBNE R5,R6,loop ; branche si i < n


Architecture logicielle Procedures

Plan




Procedures

Appel et retour de procedureLa procedure peut etre a une adresse eloignee

L’appelante connaıt l’adresse de l’appelee, mais le contraire n’estpas vrai

Il faut assurer la sauvegarde de l’adresse de retour

Inst. suivante

Inst. d’appel

retour

Inst. 1

Memoire

AppeleeAppelante

PC



Support pour l’appel et le retour de procedureJAL : Jump and Link

000011 Immediat

6 26

31 26 25 0

I Format Sauts (J)I Syntaxe JAL Imm26.I Effet R31 ← PC + 4 ; PC ← PC31:28 || Imm26 || 0b00.

JR : Jump Register

000000 Rs 00000 00000 hint 001000

6 5 5 5 5 6

31 26 25 21 20 16 15 11 10 6 5 0

I Format R-RI Syntaxe JR RsI Effet PC ← RsI Usage typique : JR R31



Pile d’execution

Appels de procedures imbriques : conserverl’adresse de retour

Les procedures peuvent modifier certainsregistres

Conventions logicielles sur :I Le stockage en memoire de l’adresse de

retour et des parametresI Le registre pointeur de pile : R29I l’usage des registres :

F R8-R15 et R25-R26 ne sont passauvegardes par l’appelee

F R16-R23 doivent etre sauvegardes.F R4-R7 passage des parametres, R2 valeur

de retour

Pile

prec

eden

teP

ileco

ura

nte

arguments registre pourune future pile (R4-R7)

autres arguments pourfuture pile si besoin

sauvegarde registres

adresse retour

variables locales


Documents

Jo el Gay - lri.frjgay/enseignement/Archi/Archi_slides_part1.pdf · egal a la retenue. Facile a tester. Jo el Gay APP3 - Architecture des ordinateurs Ann ee 2018 2019. Repr esentation