UniversityLibHub Documents

Cours de l'Arithmétique des ordinateurs

1/1
100%

Comment les nombres négatifs sont-ils représentés ? Quel est le plus grand nombre qui puisse être représenté par un mot machine ? Que se passe-t-il si une opération génère un nombre plus grand que ce qu'il n'est possible de représenter ? Qu'en est-il des fractions et des nombres réels ? Comment le matériel fait-il réellement pour additionner, soustraire, multiplier ou diviser des nombres le plus rapidement possible ? Le but de ce chapitre est de dévoiler ce mystère Chapitre 4 :Arithmétique des ordinateurs Abdesslem Page : 1 1011 en base 2, représente : ( 1 * 2 3 ) + ( 1 * 2 2 ) + ( 0 * 2 1 ) + ( 1 * 2 0 ) dix = ( 1 *8 ) + ( 1*4 ) + ( 0 * 2 ) + ( 1*1 ) dix = 8 + 4 + 0 + 1 dix = 11 dix Puisqu'un mot MIPS possède 32 bits , le nombre 1101 deux sera représenté comme suit : (32 bits de large ) Le bit du poids faible est le bit le plus à droite. Le bit du poids fort est le bit le plus à gauche. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 Représentation des nombres Abdesslem Page : 2 Représentation distinguant le positif du négatif : Utilisation de 1 bit de signe : ⇒ 0 va avoir une représentation positif et négatif Un nombre ayant deux représentations est plus grave qu’un déséquilibre entre les nombres positifs et les nombres négatifs. Complément à 2 (adopter pour les ordinateurs 32 bits) 0000 0000 0000 0000 0000 0000 0000 0000 deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001 deux = 1 dix 0000 0000 0000 0000 0000 0000 0000 0010 deux = 2 dix .................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110 deux = 2.147.483.646 dix 0111 1111 1111 1111 1111 1111 1111 1111 deux = 2.147.483.647 dix Représentation des nombres Abdesslem Page : 3 0000 0000 0000 0000 0000 0000 0000 0000 deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001 deux = 1 dix 0000 0000 0000 0000 0000 0000 0000 0010 deux = 2 dix .................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110 deux = 2.147.483.646 dix 0111 1111 1111 1111 1111 1111 1111 1111 deux = 2.147.483.647 dix 1000 0000 0000 0000 0000 0000 0000 0000 deux = -2.147.483.648 dix 1000 0000 0000 0000 0000 0000 0000 0001 deux = -2.147.483.647 dix .................................................................................. 1111 1111 1111 1111 1111 1111 1111 1110 deux = -2 dix 1111 1111 1111 1111 1111 1111 1111 1111 deux = -1 dix Représentation des nombres Abdesslem Page : 4 Cette convention s'appelle complément à deux : tout les nombres négatifs ont un 1 comme bit de poids fort. Le matériel n'a donc besoin de tester que ce bit pour déterminer si un nombre est positifs ou non . Ce bit particulier est appelé souvent le bit de signe. Un nombre binaire de 32 bits sera alors représenté comme suit : (x 31 * -2 31 )+ ( x 30 * 2 30 ) + ................+ ( x 1 * 2 1 ) + (x 0 * 2 0 ) x i : signifie : le i ème bit de x x + (-x) = 0 1 seul nombre négatif -2.147.483.648 dix qui n ’a pas de nombre positif correspondant Représentation des nombres Abdesslem Page : 5 Exemple : Prendre l'opposé de 2 dix et ajouter 1 2 dix = 0000 0000 0000 0000 0000 0000 0000 0010 deux Prendre l'opposé de ce nombre en inversant ses bits et en ajoutant 1 donne : 1111 1111 1111 1111 1111 1111 1111 1101 deux + 0000 0000 0000 0000 0000 0000 0000 0001 deux --------------------------------------------------------- = 1111 1111 1111 1111 1111 1111 1111 1110 deux = -2 dix Représentation des nombres Abdesslem Page : 6 Par conséquent : Ä La manière de convertir un nombre binaire représenté avec n bit en un nombre représenté avec plus de n bits: extension signée. Répliqué le bit du signe: (16)bits : 0000 0000 0000 0010 deux 2 dix (32)bits : 0000 0000 0000 0000 0000 0000 0000 0010 deux -2 dix (16) bits : 1111 1111 1111 1110 deux (32) bits : 1111 1111 1111 1111 1111 1111 1111 1110 deux -x = x + 1 Représentation des nombres Abdesslem Page : 7 On peut faire des décalages à droite ou à gauche de tout les bits d'un mots tout en remplissant les bits vidés par des zéro . Exemple : le registre $16 contient 0000 0000 0000 0000 0000 0000 0000 1101deux Une instruction de décalage de 8 bit vers la gauche du contenue du registre $16 va donner comme résultat: 0000 0000 0000 0000 0000 1101 0000 0000 deux Il existe deux instructions pour ce genre d'opération : sll (shift left logical ) Décalage à gauche . srl (shift right logical ) Décalage à droite . Soit l'instruction MIPS suivante sll $10 , $16 , 8 # reg $10 = reg $16 << 8 bits Opérations logiques du MIPS Abdesslem Page : 8 Sll et srl sont deux opérations logiques dans le format de l'instruction en MIPS et du type R , ici la valeur de décalage 8 est mise dans le champs decval , la version en langage machine sera alors : op rs rt rd decval fonct 0 0 16 10 8 0 Opérations logiques du MIPS Abdesslem Page : 9 and $8,$9,$10 # reg $8 = reg $9 ET reg$10 $9 contient : 0000 0000 0000 0000 0000 1101 0000 0000 deux $10 contient : 0000 0000 0000 0000 0011 1100 0000 0000 deux $8 contient 0000 0000 0000 0000 0000 1100 0000 0000 deux or $8,$9,$10 # reg $8 = reg $9 OU reg$10 $8 contient 0000 0000 0000 0000 0011 1101 0000 0000 deux andi $8,$9,100 # reg $8 = reg $9 ET 100 ori $8,$9,100 # reg $8 = reg $9 OU 100 Opérations logiques du MIPS Abdesslem Page : 10 Commencer par les petits éléments pour aboutir a un ensemble plus complexe (du bas en haut) La conception est un processus créative et non une simple méthode Processus de conception Conception CPU – La conception est l’assemblage des différents composants. Datapath Control – Décomposition de haut en bas ALU Regs Shifter d’une fonction complexe (fonctionnement) en fonctions primitives. Nand Gate Abdesslem Page : 11 Top-Down Design Bottom-Up Design Démarche descendante Démarche ascendante Raffinement de chaque constituant Abstraction sur un ensemble de constituants Conception Architecturale Conception Architecturale Conception Logique Conception Logique 10/11/2012 06:36 I. Abdesslem Démarche Démarche de de conception conception Spécification Placement/Routage Silicium - 12 - Exigences : beq, bne, slt, slti, sltu, sltiu addu, subu, addiu: (sans détection de débordement). add, sub, addi: (détection de débordement). add, addu, sub, subu, addi, addiu and, or, andi, ori Conception de l’UAL Abdesslem Page : 13 Format des instructions arithmétiques de MIPS Type-R : Type-I : 31 25 20 15 5 0 op Rs Rt Rd funct op Rs Rt Immed 16 Type op funct ADDI 10 xx ADDIU 11 xx SLTI 12 xx SLTIU 13 xx ANDI 14 xx ORI 15 xx XORI 16 xx LUI 17 xx Type op funct ADD 00 40 ADDU 00 41 SUB 00 42 SUBU 00 43 AND 00 44 OR 00 45 XOR 00 46 NOR 00 47 Type op funct Type op funct SLT 00 52 SLT 00 52 SLTU 00 53 SLTU 00 53 Abdesslem Page : 14 L'Unité Arithmétique et Logique Spécification fonctionnelle Entrées: 2 x 32-bit opérandes A, B, 4-bit pour mode. Sorties: 32-bit résultat S, 1-bit retenu, 1 bit débordement Opérations: add, addu, sub, subu, and, or, xor, nor, slt, sltU Diagramme de bloc : 32 32 CF ZF A OF B UAL m 4 (S-selec (2 bits), Invert, Cin) S 32 Registres temporaires à 32 bits Operations signés : débordement pas de retenu ! Abdesslem Page : 15 Décomposition du diagramme de bloc A 32 B 32 a31 b31a0 b04 ALU31 mco s31 cin ALU0 mco s0 cin M OF ZF 32 S Réalisation de l’UAL de 32 bits en termes de 32 UAL à 1 bit Abdesslem Page : 16 Conception de l’UAL à 1 bit Les opérations logiques : S-select A M ux Result B and or Abdesslem Page : 17 Conception de L’UAL à 1 bit B Cin A 1-bit Full S Adder Cout 0 1 1 1 + 0 0 1 0 1 (0) 0 (1) 0(1) 1 (0) Fonction combinatoire Cin A S B Cout Abdesslem Page : 18 Conception de L’UAL à 1 bit a i bi S-select CarryIn and or Result add M ux 1-bit Full Adder CarryOut Abdesslem Page : 19 Conception de L’UAL à 1 bit A - B = A + (– B) = A + B + 1 Mettre Invert à 1 et mettre CarryIn à 1 invert S-select A B M ux CarryIn and or Result 1-bit add Full Adder CarryOut M ux Abdesslem Page : 20 UAL 32 bits Elle est obtenue en connectant 32 UAL 1 bit les unes aux autres. invert I. Abdesslem Page : 21 Qu’en est t’il pour l’instruction slt ? Qu’en est t’il pour le branchement conditionnelle ? 32 32 CF A OF B UAL m 4 S 32 résultat ZF Exercices Abdesslem Page : 22 L'UAL construite ne réalise pas l'instruction de positionnement si inferieur slt . (slt $1,$2,$3) On rappelle que slt produit 1 dans $1 si $2 < $3 , et 0 sinon. Il faut utiliser l'entrée e3 qui prend la valeur de s31 (bit le plus significatif) du multiplexeur Si s31 = 1 (c-à-d le résultat est négatif) on positionne donc tous les bits de $1 à 0 sauf le bit de poids faible. Page : 23 I. Abdesslem Déroulement de l’instruction Slt L’UAL élémentaire invert CIn S-select Si Bi Mux add Abdesslem Page : 24 2 Ai and or 1-bit Full Adder e3 CO M ux Slt $1,$2,$3 Page : 25 Abdesslem Correction Slt $1,$2,$3 Abdesslem Page : 26 Déroulement de l’instruction Beq et Bne Abdesslem Page : 27 Diagramme de bloc Mode et débordement A 32 B 32 a31 b31 a0 b04 ALU0 co s31 cin ? ALU0 co s0 cin M cin M Produire S-select, Invert, 32 c-in, ... Débordement S Abdesslem Page : 28 Complement Décimale binaire à 2 0 0000 1 0001 2 0010 3 0011 00000 -1 1111 -2 1110 -3 1101 4 0100 5 0101 6 0110 7 0111 -41100 -5 1011 -6 1010 -7 1001 Examples: 7 + 3 = 10 mais ... -8 1000 10 1 1 1 0 1 1 1 71 1 0 0 + 0 0 1 1 3 + 1 0 1 1 1 0 1 0 – 6 0 1 1 1 Abdesslem Page : 29 -4 - 5 = -9 mais ... Overflow Décimale – 4 – 5 7 Détection de Débordement Débordement: le résultat est assez grand ou assez petit pour être représenté. Example: - 8 ≤ 4-bit nombre binaire ≤ 7 Lorsqu’on additionne deux nombres de signes différents Ä Pas de débordement Débordement se présente lorsqu’on additionne : 2 nombres positives et leurs sommes est négative. 2 nombres négatives et leurs somme est positive. si Carry in UAL31 ≠ Carry out UAL31 on peut détecter le overflow. 10 1 1 1 0 1 1 1 71 1 0 0 + 0 0 1 1 3 + 1 0 1 1 1 0 1 0 – 6 0 1 1 1 Abdesslem Page : 30 0 –4 –5 7 Logique de détection de débordement Débordement = CarryIn XOR CarryOut A0 B0 CarryIn0 CarryOut0 A1 B1 1-bit ALU Result0 X Y X XOR Y CarryIn1 0 0 0 0 1 1 1 0 1 CarryOut1 1 1 0 A2 B2 1-bit ALU Result1 CarryIn2 A3 B3 1-bit ALU Result2 CarryIn3 CarryOut3 1-bit ALU Result3 Overflow Abdesslem Page : 31 Amélioration de la performance (méthode de la retenue anticipé) C0 = Cin A B C-out A0 B0 G P S0 0 0 “kill” 0 1 C-in “propage” 1 0 C-in “propage” C1 = G0 + C0 • P0 1 1 1 “génère” A1B1GSP G = A and B génère une retenue P = A xor B propage une retenue C2 = G1 + G0 • P1 + C0 • P0 • P1 A2B2GSP C3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 A3B3 GS P G C4 = . . . P Abdesslem Page : 32 Pour Améliorer le temps de propagation de la retenue è utilisation d’additionneur complet avec propagation et génération de la retenue G0 = A0 and B0 génère une retenue P 0= A0 xor B0 propage une retenue Abdesslem Page : 33 G0 P0 Additionneur complet à 1 bit avec génération et propagation de la retenue C0 S0 A0 B0 Amélioration de la performance (méthode de la retenue anticipé) C LA 4-bit Adder 4-bit Adder 4-bit Adder C0 G0 P0 C1 = G0 + C0 • P0 C2 = G1 + G0 • P1 + C0 • P0 • P1 G P C3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 Abdesslem C4 = . . . Page : 34 Exigences additionnelles (Multiplication) Instruction Example Meaning add add $1,$2,$3 $1 = $2 + $3 subtract sub $1,$2,$3 $1 = $2 – $3 add immediate addi $1,$2,100 $1 = $2 + 100 add unsigned addu $1,$2,$3 $1 = $2 + $3 subtract unsigned subu $1,$2,$3 $1 = $2 – $3 add imm. unsign. addiu $1,$2,100 $1 = $2 + 100 multiply mult $2,$3 Hi, Lo = $2 x $3 multiply unsigned multu$2,$3 Hi, Lo = $2 x $3 divide div $2,$3 Lo = $2 ÷ $3, Hi = $2 mod $3 divide unsigned divu $2,$3 Lo = $2 ÷ $3, Hi = $2 mod $3 Move from Hi mfhi $1 $1 = Hi Move from Lo mflo $1 $1 = Lo Abdesslem Page : 35 Exemple de multiplication (non signée): Multiplicande 1000 Multiplicateur 1001 1000 0000 0000 1000 Produit 01001000 m bits x n bits = m+n bit produit (en ignorant le bit de signe) Multiplication binaire est simple: – 0 => place 0 ( 0 x multiplicande) – 1 => place une copie ( 1 x multiplicande) 4 versions de multiplications (matériel et algorithme): (Multiplication, non signée) Abdesslem Page : 36 0 0 0 0 A 3 A 2 A 1 A 0 A 3 A 2 A 1 A 0 B 1 A 3 A 2 A 1 A 0 B 2 A 3 A 2 A 1 A 0 B 3 Etage P 7 i accumule P 6 P 5 A * P 2 4 i si B P 3 i == 1 P 2 P 1 P 0 • Pour multiplier 32 bit pb. de hardware? B 0 (Multiplication, non signée) Abdesslem Page : 37 Chemin de données multiplication (Version 1) 1 ère proposition : Registre Multiplicande (64-bit), UAL 64-bit, registre produit (64-bit), Registre multiplicateur (32-bit). 0000...00000000 Produit Multiplicande 0000...00001000 Shift Left 64 bits Shift Right 64-bit UAL 32 bits Write Contrôle 64 bits Multiplicateur = chemin de données + contrôle Bit n°0 Abdesslem Multiplicateur 0000..1001 Page : 38 Algorithme de muliplication (Version 1) début Multiplicateur0 = 1 Multiplicateur0 1. Test Multiplicateur0 = 0 1a. Add multiplicande au produit & placer le résultat dans le registre Produit Produit Multiplicateur Multiplicande Shift le registre Multiplicande de 1 bit à gauche. 0000 0000 001 1 0000 0010 0000 0010 0 00 1 1 0000 010 0 0000 0110 00 0 0 2 0000 10 00 Shift le registre Multiplicateur de 1 bit à droite. 0000 0110 000 0 3 0001 0 000 0000 0110 0000 4 0010 0000 32nd Non: < 32 répétitions répétition? Fin Oui: 32 répétitions Abdesslem Page : 39 La moitié (1/2) des bits de la multiplicande était toujours à 0 UAL 64-bit semble lente et peu économique 0 est insérer à gauche de la multiplicande lors du décalage => les bits de poids faible du produit ne peuvent jamais changés une fois qu’ils sont crées. Qu’est ce qui ce passe si on décalais le produit à droite? Observations sur la (Version 1) Abdesslem Page : 40 Registre Multiplicande ( 32 -bit), UAL ( 32 -bit), registre Produit 64-bit, registre Multiplicateur 32-bit. Product Multiplier Shift Right Contrôle Hardware multiplication (Version 2) Multiplicande 32-bit UAL 32 bits Abdesslem Page : 41 32 bits 64 bits Write Shift Right B 0 B 1 B 2 B 3 P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 0 0 0 0 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 Multiplicande ne change pas et le produit se décale à droite Comment Ça marche? Abdesslem Page : 42 début Algorithme de multiplication (Version 2) 0000 0000 001 1 0010 1: 0010 0000 0011 0010 2: 0 001 0 000 0011 0010 3: 0 001 0 000 0 00 1 0010 1: 0 011 0 000 0 001 0010 2: 00 01 10 00 0 001 0010 3: 00 01 10 00 00 0 0 0010 1: 00 01 10 00 00 00 0010 2: 000 0 110 0 00 00 0010 3: 000 0 110 0 000 0 0010 1: 000 0 1100 000 0 0010 2: 0000 0110 000 0 0010 3: 0000 0110 0000 0010 0000 0110 0000 0010 Multiplicateur0 = 1 Multiplicateur0 Test Multiplicateur0 = 0 1a. Add multiplicande à la moitié gauche du produit & place le résultat dans la moitié gauche du registre produit Product Multiplicateur Multiplicand 1 23 32nd répétition? 4 Shift le registre produit à droite de 1 bit. Non: < 32 répétitions Abdesslem Page : 43 Shift le registre multiplicateur à droite de 1 bit. Fin Oui: 32 répétitions Seule la partie gauche du produit est modifiée. (sur 32 bits) Ä Combiner le registre produit et le registre multiplicateur (gagner de l’espace) Registre multiplicande (32-bit), UAL 32 -bit, Registre produit (64-bit) dont 32 registre multiplicateur Multiplicande 32 bits 32-bit UAL Shift Right Produit (Multiplicateur) Contrôle 64 bits Write Observations sur la (Version 2) et hardware de la (Version 3) Abdesslem Page : 44 Algorithme de multiplication (Version 3) début Multiplicande Produit 0010 0000 0011 0010 0010 0011 0001 0001 0010 0011 0001 0001 1000 0010 0000 1100 0010 0000 0110 Produit0 = 1 Produit0 Test Produit0 = 0 1a. Add multiplicande à la moitié gauche du produit & Place le résultat dans la moitié gauche du registre produit2. Shift le regsitre produit à droite de 1 bit. 1 234 32nd répétition? Non: < 32 répétitions Abdesslem Page : 45 Fin Oui: 32 répétitions Observations sur la version 3 de la multiplication 2 étapes pour chaque calcul d'un bit (multiplicateur et produit combinés) Hi/Lo sont les deux demies parties du registre produit gauche et droite MultU, multiplication non signée Comment réaliser la multiplication d’une manière plus vite? Comment on traite la multiplication signée? – Algorithme de Booth est une manière élégante pour la multiplication des nombres signées en utilisant le même matériel utilisée en version 3, de plus on gagne dans certains cycles. Abdesslem Page : 46 Motivation pour l’algorithme de Booth Example 2 x 6 = 0010 x 0110: 0010 x 0110 + 0000 décalage (0 multiplicateur) + 0010 addition (1 multiplicateur) + 0010 addition (1 multiplicateur) + 0000 décalage (0 multipliacteur) ... 00001100 UAL addition ou soustraction peut avoir le même résultat mais de manière différente: 6 = – 2 + 8 0110 = – 00010 + 01000 = 11110 + 01000 For example 0010 x 0 11 0 0000 décalage(0 multiplicateur) – 0010 sub(le premier 1 du multiplicateur) 0000 décalage (les 1 de milieu) + 0010 addition (juste après la liste des 1) 00001100 Abdesslem Page : 47 Algorithme de booth fin d'exécution Milieu 0 1 d’ 1 Execution 1 1 0 Début d'exécution Bit courant Bit à droite Explication Example Op 1 0 début d ’exe. des 1s 000111 10 00 sub 1 1 milieu d ’exe. des 1s 00011 11 000 rien 0 1 fin d ’exe. des 1s 00 01 111000 add 0 0 milieu d ’exe. des 0s 0 00 1111000 rien temps d’exécution est meilleur (décalage est plus rapide que l ’addition) Remplacer la chaîne de 1s dans le multiplicateur par une soustraction lorsqu’on identifie le premier 1et une addition pour le bit juste après le dernier 1 de la chaîne. Abdesslem Page : 48 Exemple (2 x 7), algorithme de Booth Opération Multiplicande Produit suivant? Val. initiale 0010 0000 0111 0 10 -> sub 1a. P = P - m 1110 + 1110 1110 0111 0 dec. P (ext. signée) 1b. 0010 1111 0 011 1 11 -> nop, dec. 0010 1111 10 01 1 11 -> nop, dec. 0010 1111 110 0 1 01 -> add 4a. 0010 + 0010 0001 110 0 1 dec. 4b. 0010 0000 1110 0 fin Abdesslem Page : 49 Exemple (2 x -3), algorithme de Booth Opération Multiplicande Produit suivant? Val. initiale 0010 0000 1101 0 10 -> sub 1a. P = P - m 1110 + 1110 1110 1101 0 dec. P (ext. signée) 1b. 0010 1111 0 110 1 01 -> add + 0010 2a. 0001 0 110 1 dec. P 2b. 0010 0000 10 11 0 10 -> sub + 1110 3a. 0010 1110 10 11 0 dec. 3b. 0010 1111 010 1 1 11 -> nop 4a 1111 010 1 1 dec. 4b. 0010 1111 1010 1 Fin Abdesslem Page : 50 Preuve de l’algorithme de Booth (représentation complément à 2) Soit a: multiplicateur et b: multiplicande, ai: le i eme bit de a. ai ai-1 opération 0 0 Ne rien faire 0 1 Ajout de b 1 0 Soustraire b 1 1 Ne rien faire ai-1-ai 01 -10 Un décalage à gauche de la multiplicande peut être considéré comme une multiplication par une puissance de 2 selonba × ( Booth () = = ab baabaa × - )).2(....)2()2(( 01 - 31 - (...2)() × 31 + + a 10 30 - × × 1 + 30 + + a 0 0 + baa 29 - 30 (2) × × 30 + baa 30 - 31 2) × × 31 Représentation en complément à 2 Abdesslem Page : 51 Observations sur l’algorithme de Booth Problème pour des 1 isolées (addition suivi d’une soustraction) Résolution du pb grâce là la factorisation judicieuse de la représentation en complément à 2 Exercice Algorithme de Booth , réduire le nombre d’op. éviter les op. en présence de 0 et 1. Modifier l’algorithme de Booth pour traiter 3 bits à la fois et calculer la multiplicande 2 bits par 2 bits. Abdesslem Page : 52 Division 1001 Quotient Diviseur 1000 1001010 Dividende –1000 10101 1010 –1000 10 reste (ou modulo résulatat) Le grand nombre a soustraire, création d ’un bit à chaque étape binaire => 1 * diviseur ou 0 * diviseur Dividende = Quotient x Diviseur + Reste => | Dividend | = | Quotient | + | Diviseur | 3 versions de divisions, comme pour la multiplication (plus simple au moins coûteux) Abdesslem Page : 53 Division version 1 du matériel registre Diviseur 64-bit, UAL 64 bit, registre Reste 64 bit, registre Quotient 32 bit. Reste Ecrire Control 64 bits diviseur Décalage à droite 64 bits Décalage à gauche UAL 64-bit Quotient 32 bits Abdesslem Page : 54 Algorithme de division (version 1) début: Placé la dividende dans le reste Sub registre diviseur du register reste et placer le résultat dans le registrer reste . reste ≥ 0 Test Reste < 0 reste 2a. Décalage du 2b. Restaurer la valeur en additionnant le registre quotient registre diviseur au reste et en plaçant la à gauche en somme dans le registre reste. de plus, décalage insérant un 1 du registre quotient en insérant un 0. 3.décalage de 1 bit vers la droite du registre diviseur . n+1 repetition? Fin Non: < n+1 répétitions Oui: n+1 répétitions Abdesslem Page : 55 Exemple de division (7 / 2) Reste Quotient Diviseur 0000 0111 0000 0010 0000 1: 1110 0111 0000 0010 0000 2: 0000 0111 000 0 0010 0000 3: 0000 0111 000 0 0 001 0000 1: 1111 0111 000 0 0 001 0000 2: 0000 0111 00 00 0 001 0000 3: 0000 0111 00 00 00 00 1000 1: 1111 1 111 00 00 00 00 1000 2: 0000 0111 0 000 00 00 1000 3: 0000 0111 0 000 000 0 0100 1: 0000 0001 0 000 000 0 0100 2: 0000 0011 000 1 000 0 0100 3: 0000 0011 0001 0000 0010 1: 0000 0001 000 1 0000 0010 2: 0000 0001 0011 0000 0010 3: 0000 0001 0011 0000 0 001 1 2345 réponse réponse Quotient = 3 Reste = 1 Quotient = 3 Reste = 1 Abdesslem Page : 56 Observations sur la version 1 de la division 1/2 des bits du diviseur sont toujours à 0 => 1/2 des 64-bit de l'addition => 1/2 du diviseur au lieu de décaler le diviseur à droite, on décale le reste à gauche? La première étape, ne peut produire un 1 dans le bit quotient (sinon ça serais plus grand) => décalage avant la soustraction, Gagner une itération. Abdesslem Page : 57 Division version 2 du matériel registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, registre Quotient 32 bit. Abdesslem Reste Diviseur 32-bit ALU 32 bits 64 bits Quotient Shift Left Ecrire 32 bits Shift Left Control Page : 58 Algorithme de division (version 2) début: Placer la dividende dans le registre reste 3.décalage de 1 bit vers la gauche du registre reste 2b. Restaurer la valeur ancienne en additionnant le registre diviseur à la partie gauche du reste et en plaçant la somme dans la partie gauche du registre reste. De plus, décalage du registre quotient en insérant un 0. 2a. Décalage du registre quotient à gauche en insérant un 1 n repetition? Abdesslem Non: < n répétitions Page : 59 Sub registre diviseur de la partie gauche du registre reste et placer le résultat dans la partie gauche du registre reste reste ≥ 0 Test Reste < 0 reste Fin Oui: n répétitions Reste Quotient Diviseur 0000 0111 0000 0010 1: 0000 1110 0000 0010 2: 1111 1110 0000 0010 3: 0000 1110 0000 0010 1: 0001 1100 0000 0010 2: 1111 1100 0000 0010 3: 0001 1100 0000 0010 1: 0011 1000 0000 0010 2: 0001 1000 0000 0010 3: 0001 1000 0001 0010 1: 0011 0000 0001 0010 2: 0001 0000 0001 0010 3: 0001 0000 0011 0010 Abdesslem 1 réponse Quotient = 3 2 Reste = 1 34 Page : 60 Exemple de division (7 / 2) Division version 3 du matériel registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, 0 registre Quotient. Diviseur 32 bits 32-bit UAL “HI” “LO” Shift Left reste (Quotient) Control 64 bits Ecrire Abdesslem Page : 61 Algorithme de division Début: placer la dividende dans la moitié droite reste (version 3) 3b. Restaurer la valeur originale en additionnant le registre diviseur à la moitié gauche du registre reste , et place la somme dans la moitié gauche du registre reste. Décaler le registre reste en insérant un 0. Abdesslem 1.décalage du registre reste à gauche de 1 bit. Soustraire le diviseur de la moitié gauche du registre reste et placer le résultat dans la moitié gauche du registre reste. Reste ≥ 0 Test Reste < 0 Reste 3a. Décalage du registre reste à gauche en insérant un 1 dans le nouveau bit nth Non: < n repetitions répétition? Oui: n répétitions Décalage de la moitié gauche du registre reste à droite de 1 bit. Page : 62 Reste Diviseur 0000 0111 0010 0000 111 0 0010 1: 1111 111 0 0010 2: 0001 11 00 0010 1: 1111 11 00 0010 2: 0011 1 000 0010 1: 0001 1 000 0010 2: 0011 0001 0010 1: 0001 0001 0010 2: 0010 0011 0010 3: 0 001 0011 0010 Abdesslem 1 réponse Quotient = 3 2 Reste = 1 34 Page : 63 Exemple de division (7 / 2) Observations sur la version 3 de la division Même matériel que la multiplication: UAL pour additionner ou soustraire, un registre 64 bit pour décaler à droite ou à gauche. Les registres Hi et Lo de MIPS sont combinés pour être utilisées comme registre 64-bits à la division et à la multiplication. Division signée: faire la division positive, modifier le signe du quotient ou du reste si nécessaire. – Note: la dividende et le reste doivent avoir le même signe. – Note: –7 ÷ 2 = –3, reste = –1 –7 ÷ 2 = –4, reste = +1 (juste en formule mais plus difficile à mettre en œuvre) Abdesslem Page : 64 télécharger gratuitement cours de l'Arithmétique des ordinateurs

Page 1 sur 1Lecteur de document UniversityLib

Cours de l'Arithmétique des ordinateurs

Artificial Intelligence · exam

Voir tous les documents en intelligence artificielle et données

Comment les nombres négatifs sont-ils représentés ? Quel est le plus grand nombre qui puisse être représenté par un mot machine ? Que se passe-t-il si une opération génère un nombre plus grand que ce qu'il n'est possible de représenter ? Qu'en est-il des fractions et des nombres réels ? Comment le matériel fait-il réellement pour additionner, soustraire, multiplier ou diviser des nombres le plus rapidement possible ? Le but de ce chapitre est de dévoiler ce mystère Chapitre 4 :Arithmétique des ordinateurs Abdesslem Page : 1 1011 en base 2, représente : ( 1 * 2 3 ) + ( 1 * 2 2 ) + ( 0 * 2 1 ) + ( 1 * 2 0 ) dix = ( 1 *8 ) + ( 1*4 ) + ( 0 * 2 ) + ( 1*1 ) dix = 8 + 4 + 0 + 1 dix = 11 dix Puisqu'un mot MIPS possède 32 bits , le nombre 1101 deux sera représenté comme suit : (32 bits de large ) Le bit du poids faible est le bit le plus à droite. Le bit du poids fort est le bit le plus à gauche. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 Représentation des nombres Abdesslem Page : 2 Représentation distinguant le positif du négatif : Utilisation de 1 bit de signe : ⇒ 0 va avoir une représentation positif et négatif Un nombre ayant deux représentations est plus grave qu’un déséquilibre entre les nombres positifs et les nombres négatifs. Complément à 2 (adopter pour les ordinateurs 32 bits) 0000 0000 0000 0000 0000 0000 0000 0000 deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001 deux = 1 dix 0000 0000 0000 0000 0000 0000 0000 0010 deux = 2 dix .................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110 deux = 2.147.483.646 dix 0111 1111 1111 1111 1111 1111 1111 1111 deux = 2.147.483.647 dix Représentation des nombres Abdesslem Page : 3 0000 0000 0000 0000 0000 0000 0000 0000 deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001 deux = 1 dix 0000 0000 0000 0000 0000 0000 0000 0010 deux = 2 dix .................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110 deux = 2.147.483.646 dix 0111 1111 1111 1111 1111 1111 1111 1111 deux = 2.147.483.647 dix 1000 0000 0000 0000 0000 0000 0000 0000 deux = -2.147.483.648 dix 1000 0000 0000 0000 0000 0000 0000 0001 deux = -2.147.483.647 dix .................................................................................. 1111 1111 1111 1111 1111 1111 1111 1110 deux = -2 dix 1111 1111 1111 1111 1111 1111 1111 1111 deux = -1 dix Représentation des nombres Abdesslem Page : 4 Cette convention s'appelle complément à deux : tout les nombres négatifs ont un 1 comme bit de poids fort. Le matériel n'a donc besoin de tester que ce bit pour déterminer si un nombre est positifs ou non . Ce bit particulier est appelé souvent le bit de signe. Un nombre binaire de 32 bits sera alors représenté comme suit : (x 31 * -2 31 )+ ( x 30 * 2 30 ) + ................+ ( x 1 * 2 1 ) + (x 0 * 2 0 ) x i : signifie : le i ème bit de x x + (-x) = 0 1 seul nombre négatif -2.147.483.648 dix qui n ’a pas de nombre positif correspondant Représentation des nombres Abdesslem Page : 5 Exemple : Prendre l'opposé de 2 dix et ajouter 1 2 dix = 0000 0000 0000 0000 0000 0000 0000 0010 deux Prendre l'opposé de ce nombre en inversant ses bits et en ajoutant 1 donne : 1111 1111 1111 1111 1111 1111 1111 1101 deux + 0000 0000 0000 0000 0000 0000 0000 0001 deux --------------------------------------------------------- = 1111 1111 1111 1111 1111 1111 1111 1110 deux = -2 dix Représentation des nombres Abdesslem Page : 6 Par conséquent : Ä La manière de convertir un nombre binaire représenté avec n bit en un nombre représenté avec plus de n bits: extension signée. Répliqué le bit du signe: (16)bits : 0000 0000 0000 0010 deux 2 dix (32)bits : 0000 0000 0000 0000 0000 0000 0000 0010 deux -2 dix (16) bits : 1111 1111 1111 1110 deux (32) bits : 1111 1111 1111 1111 1111 1111 1111 1110 deux -x = x + 1 Représentation des nombres Abdesslem Page : 7 On peut faire des décalages à droite ou à gauche de tout les bits d'un mots tout en remplissant les bits vidés par des zéro . Exemple : le registre $16 contient 0000 0000 0000 0000 0000 0000 0000 1101deux Une instruction de décalage de 8 bit vers la gauche du contenue du registre $16 va donner comme résultat: 0000 0000 0000 0000 0000 1101 0000 0000 deux Il existe deux instructions pour ce genre d'opération : sll (shift left logical ) Décalage à gauche . srl (shift right logical ) Décalage à droite . Soit l'instruction MIPS suivante sll $10 , $16 , 8 # reg $10 = reg $16 << 8 bits Opérations logiques du MIPS Abdesslem Page : 8 Sll et srl sont deux opérations logiques dans le format de l'instruction en MIPS et du type R , ici la valeur de décalage 8 est mise dans le champs decval , la version en langage machine sera alors : op rs rt rd decval fonct 0 0 16 10 8 0 Opérations logiques du MIPS Abdesslem Page : 9 and $8,$9,$10 # reg $8 = reg $9 ET reg$10 $9 contient : 0000 0000 0000 0000 0000 1101 0000 0000 deux $10 contient : 0000 0000 0000 0000 0011 1100 0000 0000 deux $8 contient 0000 0000 0000 0000 0000 1100 0000 0000 deux or $8,$9,$10 # reg $8 = reg $9 OU reg$10 $8 contient 0000 0000 0000 0000 0011 1101 0000 0000 deux andi $8,$9,100 # reg $8 = reg $9 ET 100 ori $8,$9,100 # reg $8 = reg $9 OU 100 Opérations logiques du MIPS Abdesslem Page : 10 Commencer par les petits éléments pour aboutir a un ensemble plus complexe (du bas en haut) La conception est un processus créative et non une simple méthode Processus de conception Conception CPU – La conception est l’assemblage des différents composants. Datapath Control – Décomposition de haut en bas ALU Regs Shifter d’une fonction complexe (fonctionnement) en fonctions primitives. Nand Gate Abdesslem Page : 11 Top-Down Design Bottom-Up Design Démarche descendante Démarche ascendante Raffinement de chaque constituant Abstraction sur un ensemble de constituants Conception Architecturale Conception Architecturale Conception Logique Conception Logique 10/11/2012 06:36 I. Abdesslem Démarche Démarche de de conception conception Spécification Placement/Routage Silicium - 12 - Exigences : beq, bne, slt, slti, sltu, sltiu addu, subu, addiu: (sans détection de débordement). add, sub, addi: (détection de débordement). add, addu, sub, subu, addi, addiu and, or, andi, ori Conception de l’UAL Abdesslem Page : 13 Format des instructions arithmétiques de MIPS Type-R : Type-I : 31 25 20 15 5 0 op Rs Rt Rd funct op Rs Rt Immed 16 Type op funct ADDI 10 xx ADDIU 11 xx SLTI 12 xx SLTIU 13 xx ANDI 14 xx ORI 15 xx XORI 16 xx LUI 17 xx Type op funct ADD 00 40 ADDU 00 41 SUB 00 42 SUBU 00 43 AND 00 44 OR 00 45 XOR 00 46 NOR 00 47 Type op funct Type op funct SLT 00 52 SLT 00 52 SLTU 00 53 SLTU 00 53 Abdesslem Page : 14 L'Unité Arithmétique et Logique Spécification fonctionnelle Entrées: 2 x 32-bit opérandes A, B, 4-bit pour mode. Sorties: 32-bit résultat S, 1-bit retenu, 1 bit débordement Opérations: add, addu, sub, subu, and, or, xor, nor, slt, sltU Diagramme de bloc : 32 32 CF ZF A OF B UAL m 4 (S-selec (2 bits), Invert, Cin) S 32 Registres temporaires à 32 bits Operations signés : débordement pas de retenu ! Abdesslem Page : 15 Décomposition du diagramme de bloc A 32 B 32 a31 b31a0 b04 ALU31 mco s31 cin ALU0 mco s0 cin M OF ZF 32 S Réalisation de l’UAL de 32 bits en termes de 32 UAL à 1 bit Abdesslem Page : 16 Conception de l’UAL à 1 bit Les opérations logiques : S-select A M ux Result B and or Abdesslem Page : 17 Conception de L’UAL à 1 bit B Cin A 1-bit Full S Adder Cout 0 1 1 1 + 0 0 1 0 1 (0) 0 (1) 0(1) 1 (0) Fonction combinatoire Cin A S B Cout Abdesslem Page : 18 Conception de L’UAL à 1 bit a i bi S-select CarryIn and or Result add M ux 1-bit Full Adder CarryOut Abdesslem Page : 19 Conception de L’UAL à 1 bit A - B = A + (– B) = A + B + 1 Mettre Invert à 1 et mettre CarryIn à 1 invert S-select A B M ux CarryIn and or Result 1-bit add Full Adder CarryOut M ux Abdesslem Page : 20 UAL 32 bits Elle est obtenue en connectant 32 UAL 1 bit les unes aux autres. invert I. Abdesslem Page : 21 Qu’en est t’il pour l’instruction slt ? Qu’en est t’il pour le branchement conditionnelle ? 32 32 CF A OF B UAL m 4 S 32 résultat ZF Exercices Abdesslem Page : 22 L'UAL construite ne réalise pas l'instruction de positionnement si inferieur slt . (slt $1,$2,$3) On rappelle que slt produit 1 dans $1 si $2 < $3 , et 0 sinon. Il faut utiliser l'entrée e3 qui prend la valeur de s31 (bit le plus significatif) du multiplexeur Si s31 = 1 (c-à-d le résultat est négatif) on positionne donc tous les bits de $1 à 0 sauf le bit de poids faible. Page : 23 I. Abdesslem Déroulement de l’instruction Slt L’UAL élémentaire invert CIn S-select Si Bi Mux add Abdesslem Page : 24 2 Ai and or 1-bit Full Adder e3 CO M ux Slt $1,$2,$3 Page : 25 Abdesslem Correction Slt $1,$2,$3 Abdesslem Page : 26 Déroulement de l’instruction Beq et Bne Abdesslem Page : 27 Diagramme de bloc Mode et débordement A 32 B 32 a31 b31 a0 b04 ALU0 co s31 cin ? ALU0 co s0 cin M cin M Produire S-select, Invert, 32 c-in, ... Débordement S Abdesslem Page : 28 Complement Décimale binaire à 2 0 0000 1 0001 2 0010 3 0011 00000 -1 1111 -2 1110 -3 1101 4 0100 5 0101 6 0110 7 0111 -41100 -5 1011 -6 1010 -7 1001 Examples: 7 + 3 = 10 mais ... -8 1000 10 1 1 1 0 1 1 1 71 1 0 0 + 0 0 1 1 3 + 1 0 1 1 1 0 1 0 – 6 0 1 1 1 Abdesslem Page : 29 -4 - 5 = -9 mais ... Overflow Décimale – 4 – 5 7 Détection de Débordement Débordement: le résultat est assez grand ou assez petit pour être représenté. Example: - 8 ≤ 4-bit nombre binaire ≤ 7 Lorsqu’on additionne deux nombres de signes différents Ä Pas de débordement Débordement se présente lorsqu’on additionne : 2 nombres positives et leurs sommes est négative. 2 nombres négatives et leurs somme est positive. si Carry in UAL31 ≠ Carry out UAL31 on peut détecter le overflow. 10 1 1 1 0 1 1 1 71 1 0 0 + 0 0 1 1 3 + 1 0 1 1 1 0 1 0 – 6 0 1 1 1 Abdesslem Page : 30 0 –4 –5 7 Logique de détection de débordement Débordement = CarryIn XOR CarryOut A0 B0 CarryIn0 CarryOut0 A1 B1 1-bit ALU Result0 X Y X XOR Y CarryIn1 0 0 0 0 1 1 1 0 1 CarryOut1 1 1 0 A2 B2 1-bit ALU Result1 CarryIn2 A3 B3 1-bit ALU Result2 CarryIn3 CarryOut3 1-bit ALU Result3 Overflow Abdesslem Page : 31 Amélioration de la performance (méthode de la retenue anticipé) C0 = Cin A B C-out A0 B0 G P S0 0 0 “kill” 0 1 C-in “propage” 1 0 C-in “propage” C1 = G0 + C0 • P0 1 1 1 “génère” A1B1GSP G = A and B génère une retenue P = A xor B propage une retenue C2 = G1 + G0 • P1 + C0 • P0 • P1 A2B2GSP C3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 A3B3 GS P G C4 = . . . P Abdesslem Page : 32 Pour Améliorer le temps de propagation de la retenue è utilisation d’additionneur complet avec propagation et génération de la retenue G0 = A0 and B0 génère une retenue P 0= A0 xor B0 propage une retenue Abdesslem Page : 33 G0 P0 Additionneur complet à 1 bit avec génération et propagation de la retenue C0 S0 A0 B0 Amélioration de la performance (méthode de la retenue anticipé) C LA 4-bit Adder 4-bit Adder 4-bit Adder C0 G0 P0 C1 = G0 + C0 • P0 C2 = G1 + G0 • P1 + C0 • P0 • P1 G P C3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 Abdesslem C4 = . . . Page : 34 Exigences additionnelles (Multiplication) Instruction Example Meaning add add $1,$2,$3 $1 = $2 + $3 subtract sub $1,$2,$3 $1 = $2 – $3 add immediate addi $1,$2,100 $1 = $2 + 100 add unsigned addu $1,$2,$3 $1 = $2 + $3 subtract unsigned subu $1,$2,$3 $1 = $2 – $3 add imm. unsign. addiu $1,$2,100 $1 = $2 + 100 multiply mult $2,$3 Hi, Lo = $2 x $3 multiply unsigned multu$2,$3 Hi, Lo = $2 x $3 divide div $2,$3 Lo = $2 ÷ $3, Hi = $2 mod $3 divide unsigned divu $2,$3 Lo = $2 ÷ $3, Hi = $2 mod $3 Move from Hi mfhi $1 $1 = Hi Move from Lo mflo $1 $1 = Lo Abdesslem Page : 35 Exemple de multiplication (non signée): Multiplicande 1000 Multiplicateur 1001 1000 0000 0000 1000 Produit 01001000 m bits x n bits = m+n bit produit (en ignorant le bit de signe) Multiplication binaire est simple: – 0 => place 0 ( 0 x multiplicande) – 1 => place une copie ( 1 x multiplicande) 4 versions de multiplications (matériel et algorithme): (Multiplication, non signée) Abdesslem Page : 36 0 0 0 0 A 3 A 2 A 1 A 0 A 3 A 2 A 1 A 0 B 1 A 3 A 2 A 1 A 0 B 2 A 3 A 2 A 1 A 0 B 3 Etage P 7 i accumule P 6 P 5 A * P 2 4 i si B P 3 i == 1 P 2 P 1 P 0 • Pour multiplier 32 bit pb. de hardware? B 0 (Multiplication, non signée) Abdesslem Page : 37 Chemin de données multiplication (Version 1) 1 ère proposition : Registre Multiplicande (64-bit), UAL 64-bit, registre produit (64-bit), Registre multiplicateur (32-bit). 0000...00000000 Produit Multiplicande 0000...00001000 Shift Left 64 bits Shift Right 64-bit UAL 32 bits Write Contrôle 64 bits Multiplicateur = chemin de données + contrôle Bit n°0 Abdesslem Multiplicateur 0000..1001 Page : 38 Algorithme de muliplication (Version 1) début Multiplicateur0 = 1 Multiplicateur0 1. Test Multiplicateur0 = 0 1a. Add multiplicande au produit & placer le résultat dans le registre Produit Produit Multiplicateur Multiplicande Shift le registre Multiplicande de 1 bit à gauche. 0000 0000 001 1 0000 0010 0000 0010 0 00 1 1 0000 010 0 0000 0110 00 0 0 2 0000 10 00 Shift le registre Multiplicateur de 1 bit à droite. 0000 0110 000 0 3 0001 0 000 0000 0110 0000 4 0010 0000 32nd Non: < 32 répétitions répétition? Fin Oui: 32 répétitions Abdesslem Page : 39 La moitié (1/2) des bits de la multiplicande était toujours à 0 UAL 64-bit semble lente et peu économique 0 est insérer à gauche de la multiplicande lors du décalage => les bits de poids faible du produit ne peuvent jamais changés une fois qu’ils sont crées. Qu’est ce qui ce passe si on décalais le produit à droite? Observations sur la (Version 1) Abdesslem Page : 40 Registre Multiplicande ( 32 -bit), UAL ( 32 -bit), registre Produit 64-bit, registre Multiplicateur 32-bit. Product Multiplier Shift Right Contrôle Hardware multiplication (Version 2) Multiplicande 32-bit UAL 32 bits Abdesslem Page : 41 32 bits 64 bits Write Shift Right B 0 B 1 B 2 B 3 P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 0 0 0 0 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 A 0 A 1 A 2 A 3 Multiplicande ne change pas et le produit se décale à droite Comment Ça marche? Abdesslem Page : 42 début Algorithme de multiplication (Version 2) 0000 0000 001 1 0010 1: 0010 0000 0011 0010 2: 0 001 0 000 0011 0010 3: 0 001 0 000 0 00 1 0010 1: 0 011 0 000 0 001 0010 2: 00 01 10 00 0 001 0010 3: 00 01 10 00 00 0 0 0010 1: 00 01 10 00 00 00 0010 2: 000 0 110 0 00 00 0010 3: 000 0 110 0 000 0 0010 1: 000 0 1100 000 0 0010 2: 0000 0110 000 0 0010 3: 0000 0110 0000 0010 0000 0110 0000 0010 Multiplicateur0 = 1 Multiplicateur0 Test Multiplicateur0 = 0 1a. Add multiplicande à la moitié gauche du produit & place le résultat dans la moitié gauche du registre produit Product Multiplicateur Multiplicand 1 23 32nd répétition? 4 Shift le registre produit à droite de 1 bit. Non: < 32 répétitions Abdesslem Page : 43 Shift le registre multiplicateur à droite de 1 bit. Fin Oui: 32 répétitions Seule la partie gauche du produit est modifiée. (sur 32 bits) Ä Combiner le registre produit et le registre multiplicateur (gagner de l’espace) Registre multiplicande (32-bit), UAL 32 -bit, Registre produit (64-bit) dont 32 registre multiplicateur Multiplicande 32 bits 32-bit UAL Shift Right Produit (Multiplicateur) Contrôle 64 bits Write Observations sur la (Version 2) et hardware de la (Version 3) Abdesslem Page : 44 Algorithme de multiplication (Version 3) début Multiplicande Produit 0010 0000 0011 0010 0010 0011 0001 0001 0010 0011 0001 0001 1000 0010 0000 1100 0010 0000 0110 Produit0 = 1 Produit0 Test Produit0 = 0 1a. Add multiplicande à la moitié gauche du produit & Place le résultat dans la moitié gauche du registre produit2. Shift le regsitre produit à droite de 1 bit. 1 234 32nd répétition? Non: < 32 répétitions Abdesslem Page : 45 Fin Oui: 32 répétitions Observations sur la version 3 de la multiplication 2 étapes pour chaque calcul d'un bit (multiplicateur et produit combinés) Hi/Lo sont les deux demies parties du registre produit gauche et droite MultU, multiplication non signée Comment réaliser la multiplication d’une manière plus vite? Comment on traite la multiplication signée? – Algorithme de Booth est une manière élégante pour la multiplication des nombres signées en utilisant le même matériel utilisée en version 3, de plus on gagne dans certains cycles. Abdesslem Page : 46 Motivation pour l’algorithme de Booth Example 2 x 6 = 0010 x 0110: 0010 x 0110 + 0000 décalage (0 multiplicateur) + 0010 addition (1 multiplicateur) + 0010 addition (1 multiplicateur) + 0000 décalage (0 multipliacteur) ... 00001100 UAL addition ou soustraction peut avoir le même résultat mais de manière différente: 6 = – 2 + 8 0110 = – 00010 + 01000 = 11110 + 01000 For example 0010 x 0 11 0 0000 décalage(0 multiplicateur) – 0010 sub(le premier 1 du multiplicateur) 0000 décalage (les 1 de milieu) + 0010 addition (juste après la liste des 1) 00001100 Abdesslem Page : 47 Algorithme de booth fin d'exécution Milieu 0 1 d’ 1 Execution 1 1 0 Début d'exécution Bit courant Bit à droite Explication Example Op 1 0 début d ’exe. des 1s 000111 10 00 sub 1 1 milieu d ’exe. des 1s 00011 11 000 rien 0 1 fin d ’exe. des 1s 00 01 111000 add 0 0 milieu d ’exe. des 0s 0 00 1111000 rien temps d’exécution est meilleur (décalage est plus rapide que l ’addition) Remplacer la chaîne de 1s dans le multiplicateur par une soustraction lorsqu’on identifie le premier 1et une addition pour le bit juste après le dernier 1 de la chaîne. Abdesslem Page : 48 Exemple (2 x 7), algorithme de Booth Opération Multiplicande Produit suivant? Val. initiale 0010 0000 0111 0 10 -> sub 1a. P = P - m 1110 + 1110 1110 0111 0 dec. P (ext. signée) 1b. 0010 1111 0 011 1 11 -> nop, dec. 0010 1111 10 01 1 11 -> nop, dec. 0010 1111 110 0 1 01 -> add 4a. 0010 + 0010 0001 110 0 1 dec. 4b. 0010 0000 1110 0 fin Abdesslem Page : 49 Exemple (2 x -3), algorithme de Booth Opération Multiplicande Produit suivant? Val. initiale 0010 0000 1101 0 10 -> sub 1a. P = P - m 1110 + 1110 1110 1101 0 dec. P (ext. signée) 1b. 0010 1111 0 110 1 01 -> add + 0010 2a. 0001 0 110 1 dec. P 2b. 0010 0000 10 11 0 10 -> sub + 1110 3a. 0010 1110 10 11 0 dec. 3b. 0010 1111 010 1 1 11 -> nop 4a 1111 010 1 1 dec. 4b. 0010 1111 1010 1 Fin Abdesslem Page : 50 Preuve de l’algorithme de Booth (représentation complément à 2) Soit a: multiplicateur et b: multiplicande, ai: le i eme bit de a. ai ai-1 opération 0 0 Ne rien faire 0 1 Ajout de b 1 0 Soustraire b 1 1 Ne rien faire ai-1-ai 01 -10 Un décalage à gauche de la multiplicande peut être considéré comme une multiplication par une puissance de 2 selonba × ( Booth () = = ab baabaa × - )).2(....)2()2(( 01 - 31 - (...2)() × 31 + + a 10 30 - × × 1 + 30 + + a 0 0 + baa 29 - 30 (2) × × 30 + baa 30 - 31 2) × × 31 Représentation en complément à 2 Abdesslem Page : 51 Observations sur l’algorithme de Booth Problème pour des 1 isolées (addition suivi d’une soustraction) Résolution du pb grâce là la factorisation judicieuse de la représentation en complément à 2 Exercice Algorithme de Booth , réduire le nombre d’op. éviter les op. en présence de 0 et 1. Modifier l’algorithme de Booth pour traiter 3 bits à la fois et calculer la multiplicande 2 bits par 2 bits. Abdesslem Page : 52 Division 1001 Quotient Diviseur 1000 1001010 Dividende –1000 10101 1010 –1000 10 reste (ou modulo résulatat) Le grand nombre a soustraire, création d ’un bit à chaque étape binaire => 1 * diviseur ou 0 * diviseur Dividende = Quotient x Diviseur + Reste => | Dividend | = | Quotient | + | Diviseur | 3 versions de divisions, comme pour la multiplication (plus simple au moins coûteux) Abdesslem Page : 53 Division version 1 du matériel registre Diviseur 64-bit, UAL 64 bit, registre Reste 64 bit, registre Quotient 32 bit. Reste Ecrire Control 64 bits diviseur Décalage à droite 64 bits Décalage à gauche UAL 64-bit Quotient 32 bits Abdesslem Page : 54 Algorithme de division (version 1) début: Placé la dividende dans le reste Sub registre diviseur du register reste et placer le résultat dans le registrer reste . reste ≥ 0 Test Reste < 0 reste 2a. Décalage du 2b. Restaurer la valeur en additionnant le registre quotient registre diviseur au reste et en plaçant la à gauche en somme dans le registre reste. de plus, décalage insérant un 1 du registre quotient en insérant un 0. 3.décalage de 1 bit vers la droite du registre diviseur . n+1 repetition? Fin Non: < n+1 répétitions Oui: n+1 répétitions Abdesslem Page : 55 Exemple de division (7 / 2) Reste Quotient Diviseur 0000 0111 0000 0010 0000 1: 1110 0111 0000 0010 0000 2: 0000 0111 000 0 0010 0000 3: 0000 0111 000 0 0 001 0000 1: 1111 0111 000 0 0 001 0000 2: 0000 0111 00 00 0 001 0000 3: 0000 0111 00 00 00 00 1000 1: 1111 1 111 00 00 00 00 1000 2: 0000 0111 0 000 00 00 1000 3: 0000 0111 0 000 000 0 0100 1: 0000 0001 0 000 000 0 0100 2: 0000 0011 000 1 000 0 0100 3: 0000 0011 0001 0000 0010 1: 0000 0001 000 1 0000 0010 2: 0000 0001 0011 0000 0010 3: 0000 0001 0011 0000 0 001 1 2345 réponse réponse Quotient = 3 Reste = 1 Quotient = 3 Reste = 1 Abdesslem Page : 56 Observations sur la version 1 de la division 1/2 des bits du diviseur sont toujours à 0 => 1/2 des 64-bit de l'addition => 1/2 du diviseur au lieu de décaler le diviseur à droite, on décale le reste à gauche? La première étape, ne peut produire un 1 dans le bit quotient (sinon ça serais plus grand) => décalage avant la soustraction, Gagner une itération. Abdesslem Page : 57 Division version 2 du matériel registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, registre Quotient 32 bit. Abdesslem Reste Diviseur 32-bit ALU 32 bits 64 bits Quotient Shift Left Ecrire 32 bits Shift Left Control Page : 58 Algorithme de division (version 2) début: Placer la dividende dans le registre reste 3.décalage de 1 bit vers la gauche du registre reste 2b. Restaurer la valeur ancienne en additionnant le registre diviseur à la partie gauche du reste et en plaçant la somme dans la partie gauche du registre reste. De plus, décalage du registre quotient en insérant un 0. 2a. Décalage du registre quotient à gauche en insérant un 1 n repetition? Abdesslem Non: < n répétitions Page : 59 Sub registre diviseur de la partie gauche du registre reste et placer le résultat dans la partie gauche du registre reste reste ≥ 0 Test Reste < 0 reste Fin Oui: n répétitions Reste Quotient Diviseur 0000 0111 0000 0010 1: 0000 1110 0000 0010 2: 1111 1110 0000 0010 3: 0000 1110 0000 0010 1: 0001 1100 0000 0010 2: 1111 1100 0000 0010 3: 0001 1100 0000 0010 1: 0011 1000 0000 0010 2: 0001 1000 0000 0010 3: 0001 1000 0001 0010 1: 0011 0000 0001 0010 2: 0001 0000 0001 0010 3: 0001 0000 0011 0010 Abdesslem 1 réponse Quotient = 3 2 Reste = 1 34 Page : 60 Exemple de division (7 / 2) Division version 3 du matériel registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, 0 registre Quotient. Diviseur 32 bits 32-bit UAL “HI” “LO” Shift Left reste (Quotient) Control 64 bits Ecrire Abdesslem Page : 61 Algorithme de division Début: placer la dividende dans la moitié droite reste (version 3) 3b. Restaurer la valeur originale en additionnant le registre diviseur à la moitié gauche du registre reste , et place la somme dans la moitié gauche du registre reste. Décaler le registre reste en insérant un 0. Abdesslem 1.décalage du registre reste à gauche de 1 bit. Soustraire le diviseur de la moitié gauche du registre reste et placer le résultat dans la moitié gauche du registre reste. Reste ≥ 0 Test Reste < 0 Reste 3a. Décalage du registre reste à gauche en insérant un 1 dans le nouveau bit nth Non: < n repetitions répétition? Oui: n répétitions Décalage de la moitié gauche du registre reste à droite de 1 bit. Page : 62 Reste Diviseur 0000 0111 0010 0000 111 0 0010 1: 1111 111 0 0010 2: 0001 11 00 0010 1: 1111 11 00 0010 2: 0011 1 000 0010 1: 0001 1 000 0010 2: 0011 0001 0010 1: 0001 0001 0010 2: 0010 0011 0010 3: 0 001 0011 0010 Abdesslem 1 réponse Quotient = 3 2 Reste = 1 34 Page : 63 Exemple de division (7 / 2) Observations sur la version 3 de la division Même matériel que la multiplication: UAL pour additionner ou soustraire, un registre 64 bit pour décaler à droite ou à gauche. Les registres Hi et Lo de MIPS sont combinés pour être utilisées comme registre 64-bits à la division et à la multiplication. Division signée: faire la division positive, modifier le signe du quotient ou du reste si nécessaire. – Note: la dividende et le reste doivent avoir le même signe. – Note: –7 ÷ 2 = –3, reste = –1 –7 ÷ 2 = –4, reste = +1 (juste en formule mais plus difficile à mettre en œuvre) Abdesslem Page : 64 télécharger gratuitement cours de l'Arithmétique des ordinateurs