Chapitre 4 :Arithmétique des ordinateurs
· 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
I. Abdesslem
Page : 1
Représentation des nombres
1011 en base 2, représente :
( 1 * 23) + ( 1 * 22) + ( 0 * 21) + ( 1 * 20)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 1101deux sera représenté comme suit : (32 bits de large )
(cid:127)Le bit du poids faible est le bit le plus à droite.
(cid:127)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
I. Abdesslem
Page : 2
Représentation des nombres
Représentation distinguant le positif du négatif :
(cid:127)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.
(cid:127)Complément à 2 (adopter pour les ordinateurs 32 bits)
0000 0000 0000 0000 0000 0000 0000 0000deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001deux = 1dix 0000 0000 0000 0000 0000 0000 0000 0010deux = 2dix
.................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110deux = 2.147.483.646dix 0111 1111 1111 1111 1111 1111 1111 1111deux = 2.147.483.647dix
I. Abdesslem
Page : 3
Représentation des nombres
0000 0000 0000 0000 0000 0000 0000 0000deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001deux = 1dix 0000 0000 0000 0000 0000 0000 0000 0010deux = 2dix
.................................................................................. 0111 1111 1111 1111 1111 1111 1111 1110deux = 2.147.483.646dix 0111 1111 1111 1111 1111 1111 1111 1111deux = 2.147.483.647dix 1000 0000 0000 0000 0000 0000 0000 0000deux = -2.147.483.648 dix 1000 0000 0000 0000 0000 0000 0000 0001deux = -2.147.483.647 dix
.................................................................................. 1111 1111 1111 1111 1111 1111 1111 1110deux = -2 dix 1111 1111 1111 1111 1111 1111 1111 1111deux = -1 dix
I. Abdesslem
Page : 4
Représentation des nombres
(cid:127) Cette convention s'appelle complément à deux : tout les nombres négatifs ont un 1 comme bit de poids fort.
(cid:127) Le matériel n'a donc besoin de tester que ce bit pour déterminer si un nombre est positifs ou non .
(cid:127) Ce bit particulier est appelé souvent le bit de signe.
(cid:127) Un nombre binaire de 32 bits sera alors représenté comme suit :
(x31 * -231)+ ( x30 * 2 30 ) + ................+ ( x1 * 2 1 ) + (x0 * 20)
xi : signifie : le ième bit de x
(cid:127) x + (-x) = 0
(cid:127) 1 seul nombre négatif -2.147.483.648 dix qui n ’a pas de nombre positif correspondant
I. Abdesslem
Page : 5
Représentation des nombres
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
I. Abdesslem
Page : 6
Représentation des nombres
Par conséquent :
(cid:127) -x = x + 1
Ä 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:
2 dix
-2 dix
(16)bits : 0000 0000 0000 0010 deux
(32)bits : 0000 0000 0000 0000 0000 0000 0000 0010 deux
(16) bits : 1111 1111 1111 1110 deux
(32) bits : 1111 1111 1111 1111 1111 1111 1111 1110 deux
I. Abdesslem
Page : 7
Opérations logiques du MIPS
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
I. Abdesslem
Page : 8
Opérations logiques du MIPS
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
0
rs
0
rt
16
rd
10
decval
8
fonct
0
I. Abdesslem
Page : 9
Opérations logiques du MIPS
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
I. Abdesslem
Page : 10
Processus de conception
Conception – La conception est l’assemblage des différents composants. – Décomposition de haut en bas
d’une fonction complexe (fonctionnement) en fonctions primitives.
Commencer par les petits éléments pour aboutir a un ensemble plus complexe (du bas en haut)
CPU
Datapath
Control
ALU
Regs
Shifter
Nand Gate
La conception est un processus créative et non une simple méthode
I. Abdesslem
Page : 11
Démarche de conception Démarche de conception
Top-Down Design
Bottom-Up Design
Démarche descendante
Raffinement de chaque constituant
Spécification
Conception Architecturale
Conception Logique
Placement/Routage
Silicium
Démarche ascendante
Abstraction sur un ensemble de constituants
10/11/2012 06:36
- 12 -
I. Abdesslem
Conception de l’UAL
Exigences :
add, addu, sub, subu, addi, addiu
and, or, andi, ori
beq, bne, slt, slti, sltu, sltiu
addu, subu, addiu: (sans détection de débordement).
add, sub, addi: (détection de débordement).
I. Abdesslem
Page : 13
Format des instructions arithmétiques de MIPS
31
25
20
15
Type-R :
Type-I :
op
op
Rd
Rs
Rs
Rt
Rt
Immed 16
5
0
funct
Type
SLT
op
00
SLTU 00
funct
52
53
Type
ADDI
op
10
ADDIU 11
SLTI
12
SLTIU 13
ANDI
ORI
XORI
LUI
14
15
16
17
funct
Type
op
funct
xx
xx
xx
xx
xx
xx
xx
xx
ADD 00
ADDU 00
SUB
00
SUBU 00
AND 00
OR
00
XOR 00
NOR 00
40
41
42
43
44
45
46
47
I. 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: Opérations:
32-bit résultat S, 1-bit retenu, 1 bit débordement
add, addu, sub, subu, and, or, xor, nor, slt, sltU
Diagramme de bloc :
32
A
ZF CF OF
32
B
m
UAL
S
32
Registres temporaires à 32 bits
4 (S-selec (2 bits), Invert, Cin)
Operations signés : débordement pas de retenu !
I. Abdesslem
Page : 15
Décomposition du diagramme de bloc
A
32
B
32
a31
ALU31 co
s31
b31 m
cin
a0
ALU0 co
s0
b0 m
cin
4
M
OF
ZF
32
S
Réalisation de l’UAL de 32 bits en termes de 32 UAL à 1 bit
I. Abdesslem
Page : 16
Conception de l’UAL à 1 bit
Les opérations logiques :
S-select
and
M u x
or
Result
A
B
I. Abdesslem
Page : 17
Conception de L’UAL à 1 bit
Cin
1-bit Full Adder
S
Cout
Publicité
A B
A
B
0
0
1
0
1
1
1
0
+
1 (0)
0 (1)
0(1)
1 (0)
Fonction combinatoire
Cin
S
Cout
I. Abdesslem
Page : 18
Conception de L’UAL à 1 bit
ai
bi
CarryIn
S-select
Result
M u x
and
or
add
1-bit Full Adder
CarryOut
I. Abdesslem
Page : 19
Conception de L’UAL à 1 bit
(cid:127) A - B = A + (– B) = A + B + 1 Mettre Invert à 1 et mettre CarryIn à 1
invert
CarryIn
S-select
A
B
and
or
add
Result
M u x
1-bit Full Adder
M u x
CarryOut
I. Abdesslem
Page : 20
UAL 32 bits
(cid:127) Elle est obtenue en connectant 32 UAL 1 bit
les unes aux autres.
invert
I. Abdesslem
Page : 21
Exercices
Qu’en est t’il pour l’instruction slt ? Qu’en est t’il pour le branchement conditionnelle ?
32
32
4
m
B
ZF
A
CF OF
UAL
S
32
résultat
I. Abdesslem
Page : 22
Déroulement de l’instruction Slt
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.
I. Abdesslem
Page : 23
L’UAL élémentaire
invert
CIn
S-select 2
and
or
M u x
Si
M u x
1-bit Full Adder
add
e3
CO
Ai
Bi
I. Abdesslem
Page : 24
Slt $1,$2,$3
I. Abdesslem
Page : 25
Correction
Slt $1,$2,$3
I. Abdesslem
Page : 26
Déroulement de l’instruction Beq et Bne
I. Abdesslem
Page : 27
Diagramme de bloc
Mode et débordement
A
32
B
32
a31 b31
ALU0 co
s31
cin
?
a0
b0
ALU0 co
s0
cin
Débordement
S
32
4
M
Produire S-select, Invert, c-in, …
I. Abdesslem
Page : 28
Overflow
Décimale
Décimale 0 1 2 3 4 5 6 7
binaire 0000 0001 0010 0011 0100 0101 0110 0111 Examples: 7 + 3 = 10 mais ... - 4 - 5 = - 9 mais ...
0
+
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
7 3
– 6
0 -1 -2 -3 -4 -5 -6 -7 -8
1
+
Complement à 2 0000 1111 1110 1101 1100 1011 1010 1001 1000
1
1
0
1
0
1
0
1
1
0
1
1
– 4 – 5
7
I. Abdesslem
Page : 29
Détection de Débordement
(cid:127) Débordement: le résultat est assez grand ou assez petit pour être représenté.
Example: - 8 £ 4-bit nombre binaire £ 7
(cid:127) Lorsqu’on additionne deux nombres de signes différents
Ä Pas de débordement
(cid:127) Débordement se présente lorsqu’on additionne :
(cid:127)2 nombres positives et leurs sommes est négative.
(cid:127)2 nombres négatives et leurs somme est positive.
(cid:127) si Carry in UAL31 ¹ Carry out UAL31 on peut détecter le overflow.
0
+
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
7 3
– 6
1
+
0
1
1
0
1
0
1
0
1
1
0
1
1
–4 –5
7
I. Abdesslem
Page : 30
Logique de détection de débordement
(cid:127) Débordement = CarryIn[N - 1] XOR CarryOut[N - 1]
CarryIn0
A0
B0
A1
B1
A2
B2
A3
B3
1-bit ALU
Result0
CarryIn1
CarryOut0
1-bit ALU
Result1
CarryIn2
CarryOut1
1-bit ALU
CarryIn3
1-bit ALU
Result2
Result3
CarryOut3
I. Abdesslem
X
0 0 1 1
Y
0 1 0 1
X XOR Y
0 1 1 0
Overflow
Page : 31
Amélioration de la performance (méthode de la retenue anticipé)
C0 = Cin
S
S
S
S
G P
G P
G P
G P
A0
B0
A1
B1
A2
B2
A3
B3
C1 = G0 + C0 · P0
A B 0 0 1 0 0 1 1 1
C-out 0 “kill” C-in “propage” C-in “propage” “génère” 1
G = A and B génère une retenue P = A xor B propage une retenue
C2 = G1 + G0 · P1 + C0 · P0 · P1
C3 = G2 + G1 · P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2
G P
C4 = . . .
I. Abdesslem
Publicité
Page : 32
Additionneur complet à 1 bit avec génération et propagation de la retenue
Pour Améliorer le temps de propagation de la retenue è utilisation d’additionneur complet avec propagation et génération de la retenue
A0 B0
C0
S0
G0 = A0 and B0 génère une retenue P 0= A0 xor B0 propage une retenue
G0
P0
I. Abdesslem
Page : 33
Amélioration de la performance (méthode de la retenue anticipé)
C L A
4-bit Adder
4-bit Adder
4-bit Adder
C0
G0 P0 C1 = G0 + C0 · P0
C2 = G1 + G0 · P1 + C0 · P0 · P1
C3 = G2 + G1 · P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2
G P
I. Abdesslem
C4 = . . .
Page : 34
Exigences additionnelles (Multiplication)
Instruction add subtract add immediate add unsigned subtract unsigned add imm. unsign.
Example add $1,$2,$3 sub $1,$2,$3 addi $1,$2,100 addu $1,$2,$3 subu $1,$2,$3 addiu $1,$2,100 $1 = $2 + 100
Meaning $1 = $2 + $3 $1 = $2 – $3 $1 = $2 + 100 $1 = $2 + $3 $1 = $2 – $3
multiply mult $2,$3 multiply unsigned multu$2,$3 divide
div $2,$3
divide unsigned
divu $2,$3
Move from Hi Move from Lo
mfhi $1 mflo $1
Hi, Lo = $2 x $3 Hi, Lo = $2 x $3 Lo = $2 ÷ $3, Hi = $2 mod $3 Lo = $2 ÷ $3, Hi = $2 mod $3 $1 = Hi $1 = Lo
I. Abdesslem
Page : 35
(Multiplication, non signée)
(cid:127) Exemple de multiplication (non signée):
Multiplicande
Multiplicateur
Produit
1000 1001 1000
0000
0000
1000 01001000
(cid:127) m bits x n bits = m+n bit produit (en ignorant le bit de signe) (cid:127) Multiplication binaire est simple:
– 0 => place 0 – 1 => place une copie
( 0 x multiplicande) ( 1 x multiplicande)
(cid:127) 4 versions de multiplications (matériel et algorithme):
I. Abdesslem
Page : 36
(Multiplication, non signée)
0
0
0
0
A3
A2
A1
A0
A3
A2
A1
A0
A3
A2
A1
A0
A3
A2
A1
A0
B0
B1
B2
B3
P7
P6
P5
P4
P3
(cid:127) Etage i accumule A * 2 i si Bi == 1 (cid:127) Pour multiplier 32 bit pb. de hardware?
P2
P1
P0
I. 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).
Multiplicande
0000…00001000
64 bits
64-bit UAL
Shift Left
Multiplicateur
Bit n°0
0000..1001
Shift Right
32 bits
0000…00000000
Produit
64 bits
Write
Contrôle
Multiplicateur = chemin de données + contrôle
I. Abdesslem
Page : 38
Algorithme de muliplication (Version 1)
début
Multiplicateur0 = 1
1. Test Multiplicateur0
Multiplicateur0 = 0
1a. Add multiplicande au produit & placer le résultat dans le registre Produit
(cid:127) Produit
0000 0000 (cid:127) 0000 0010 (cid:127) 0000 0110 (cid:127) 0000 0110 (cid:127) 0000 0110
Multiplicateur Multiplicande 0011 0001 0000 0000 0000
0000 0010 0000 0100 0000 1000 0001 0000 0010 0000
1 2 3 4
I. Abdesslem
2. Shift le registre Multiplicande de 1 bit à gauche.
3. Shift le registre Multiplicateur de 1 bit à droite.
32nd répétition?
Non: < 32 répétitions
Oui: 32 répétitions
Fin
Page : 39
Observations sur la (Version 1)
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?
I. Abdesslem
Page : 40
Hardware multiplication (Version 2)
(cid:127) Registre Multiplicande (32-bit), UAL (32 -bit), registre
Produit 64-bit, registre Multiplicateur 32-bit.
Multiplicande
32 bits
32-bit UAL
Product
Shift Right
Multiplier
32 bits
Shift Right
Contrôle
64 bits
Write
I. Abdesslem
Page : 41
Comment Ça marche?
0
0
0
0
A3
A2
A1
A0
A3
A2
A1
A0
A3
A2
A1
A0
A3
A2
A1
A0
B0
B1
B2
B3
P4 (cid:127) Multiplicande ne change pas et le produit se décale à droite
P7
P3
P2
P0
P5
P6
P1
I. Abdesslem
Page : 42
Algorithme de multiplication (Version 2)
début
Multiplicateur0 = 1
1. Test Multiplicateur0
Multiplicateur0 = 0
1a. Add multiplicande à la moitié gauche du produit & place le résultat dans la moitié gauche du registre produit
1
Product Multiplicateur Multiplicand 0000 0000 0011 1: 0010 0000 0011 2: 0001 0000 0011 3: 0001 0000 0001 1: 0011 0000 0001 0001 2: 0001 1000 0000 3: 0001 1000 0000 1: 0001 1000 0000 2: 0000 1100 0000 3: 0000 1100 0000 1: 0000 1100 0000 2: 0000 0110 0000 3: 0000 0110
0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010
3
4
2
0000 0110
0000
0010
I. Abdesslem
2. Shift le registre produit à droite de 1 bit.
3. Shift le registre multiplicateur à droite de 1 bit.
32nd répétition?
Non: < 32 répétitions
Oui: 32 répétitions
Fin
Page : 43
Observations sur la (Version 2) et hardware de la (Version 3)
(cid:127) Seule la partie gauche du produit est modifiée. (sur 32 bits)
Ä Combiner le registre produit et le registre multiplicateur (gagner de l’espace)
(cid:127) 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
I. Abdesslem
Page : 44
Algorithme de multiplication (Version 3)
début
Produit0 = 1
1. Test
Produit0
Produit0 = 0
1a. Add multiplicande à la moitié gauche du produit & Place le résultat dans la moitié gauche du registre produit
Multiplicande
0010 0010
0010
0010 0010
1
2 3 4
Produit 0000 0011 0010 0011 0001 0001 0011 0001 0001 1000 0000 1100 0000 0110
2. Shift le regsitre produit à droite de 1 bit.
32nd répétition?
Non: < 32 répétitions
Oui: 32 répétitions
Fin
I. Abdesslem
Page : 45
Observations sur la version 3 de la multiplication
(cid:127) 2 étapes pour chaque calcul d'un bit (multiplicateur et produit
combinés)
(cid:127) Hi/Lo sont les deux demies parties du registre produit gauche
et droite
(cid:127) MultU, multiplication non signée (cid:127) Comment réaliser la multiplication d’une manière plus vite? (cid:127) 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.
I. Abdesslem
Page : 46
Motivation pour l’algorithme de Booth
(cid:127) Example 2 x 6 = 0010 x 0110:
0010 0110 x 0000 décalage (0 multiplicateur) + + 0010 addition (1 multiplicateur) + 0010 addition (1 multiplicateur) + 0000 décalage (0 multipliacteur)
…00001100
(cid:127) UAL addition ou soustraction peut avoir le même résultat mais de manière différente:
(cid:127) 6 (cid:127) For example
= – 2 + 8
0110 = – 00010 + 01000 = 11110 + 01000
x
–
0010 0110 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
I. Abdesslem
Page : 47
Algorithme de booth
fin d'exécution
Milieu d’ Execution 0 1 1 1 1 0
Début d'exécution
Bit courant Bit à droite
1 1 0 0
0 1 1 0
Explication début d ’exe. des 1s milieu d ’exe. des 1s fin d ’exe. des 1s milieu d ’exe. des 0s
Example 0001111000 0001111000 0001111000 0001111000
Op sub rien add rien
temps d’exécution est meilleur (décalage est plus rapide que l ’addition)
(cid:127) 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.
Publicité
I. Abdesslem
Page : 48
Exemple (2 x 7), algorithme de Booth
Opération
Multiplicande
Produit
suivant?
0. Val. initiale 0010
0000 0111 0
10 -> sub
1a. P = P - m
1110 + 1110
1b.
2.
3.
4a.
4b.
0010
0010
0010
1110 0111 0
dec. P (ext. signée)
1111 0011 1
11 -> nop, dec.
1111 1001 1
11 -> nop, dec.
1111 1100 1
01 -> add
0010 + 0010
0001 1100 1
0010
0000 1110 0
dec.
fin
I. Abdesslem
Page : 49
Exemple (2 x -3), algorithme de Booth
Opération
Multiplicande
Produit
0. Val. initiale 0010 1a. P = P - m 1110 + 1110
0000 1101 0
1110 1101 0
suivant?
10 -> sub
dec. P (ext. signée)
01 -> add
0010
0010
0010
1111 0110 1
+ 0010
0001 0110 1 dec. P
0000 1011 0
+ 1110
10 -> sub
1110 1011 0
dec.
0010 1111 0101 1 11 -> nop
0010
I. Abdesslem
1111 0101 1
1111 1010 1
dec.
Fin
Page : 50
1b.
2a.
2b.
3a.
3b.
4a
4b.
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
ai-1-ai
0 0 1 1
0 1 0 1
Ne rien faire Ajout de b Soustraire b Ne rien faire
0 1 -1 0
Un décalage à gauche de la multiplicande peut être considéré comme une multiplication par une puissance de 2
ba selon ( ´
Booth
baaba a a b a a ) ( 2 2 ) ( ) ... ( () 30 = +´- ++´´- - +´´ 1 30 30 0 0 1 29 1 - 31 30 0 ab a a ( )2( )2( )).2( .... - + ++ ´= 30 0
31
-
a b ) 2 31 ´´ 31
Représentation en complément à 2
I. Abdesslem
Page : 51
Observations sur l’algorithme de Booth
(cid:127)Problème pour des 1 isolées (addition suivi d’une soustraction)
(cid:127)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.
I. Abdesslem
Page : 52
Division
Diviseur 1000 1001010
1001
Quotient Dividende
–1000
10 101 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)
I. Abdesslem
Page : 53
Division version 1 du matériel
(cid:127) registre Diviseur 64-bit, UAL 64 bit, registre
Reste 64 bit, registre Quotient 32 bit.
diviseur
64 bits
Décalage à droite
Décalage à gauche
Quotient
32 bits
Ecrire
Control
UAL 64-bit
Reste
64 bits
I. Abdesslem
Page : 54
Algorithme de division (version 1)
début: Placé la dividende dans le reste
1. Sub registre diviseur du register reste et placer le résultat dans le registrer reste .
reste ³ 0
Reste < 0
Test reste
2a. Décalage du registre quotient à gauche en insérant un 1
2b. Restaurer la valeur en additionnant le registre diviseur au reste et en plaçant la somme dans le registre reste. de plus, décalage du registre quotient en insérant un 0.
3.décalage de 1 bit vers la droite du registre diviseur .
n+1 repetition?
Non: < n+1 répétitions
Oui: n+1 répétitions
Fin
I. Abdesslem
Page : 55
Exemple de division (7 / 2)
Reste 0000 0111 1110 0111 0000 0111 0000 0111 1111 0111 0000 0111 0000 0111 1111 1111 0000 0111 0000 0111 0000 0001 0000 0011 0000 0011 0000 0001 0000 0001 0000 0001
Quotient 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0001 0001 0011 0011
1: 2: 3: 1: 2: 3: 1: 2: 3: 1: 2: 3: 1: 2: 3:
Diviseur 0010 0000 0010 0000 0010 0000 0001 0000 0001 0000 0001 0000 0000 1000 0000 1000 0000 1000 0000 0100 0000 0100 0000 0100 0000 0010 0000 0010 0000 0010 0000 0001
1
2
3
4
5
réponse
Quotient = 3 Reste = 1
I. Abdesslem
Page : 56
Observations sur la version 1 de la division
(cid:127) 1/2 des bits du diviseur sont toujours à 0
=> 1/2 des 64-bit de l'addition => 1/2 du diviseur
(cid:127) au lieu de décaler le diviseur à droite, on décale le reste à
gauche?
(cid:127) 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.
I. Abdesslem
Page : 57
Division version 2 du matériel
(cid:127) registre Diviseur 32-bit, UAL 32 bit, registre
Reste 64 bit, registre Quotient 32 bit.
Diviseur
32 bits
32-bit ALU
Reste
Quotient
Shift Left
32 bits
Shift Left
Control
64 bits
Ecrire
I. Abdesslem
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
1. Sub registre diviseur de la partie gauche du registre reste et placer le résultat dans la partie gauche du registre reste
reste ³ 0
Reste < 0
Test reste
2a. Décalage du registre quotient à gauche en insérant un 1
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.
n repetition?
Non: < n répétitions
Oui: n répétitions
Fin
I. Abdesslem
Page : 59
Exemple de division (7 / 2)
Reste
Quotient
Diviseur
0000 0111 0000 1110 1111 1110 0000 1110 0001 1100 1111 1100 0001 1100 0011 1000 0001 1000 0001 1000 0011 0000 0001 0000 0001 0000
1: 2: 3: 1: 2: 3: 1: 2: 3: 1: 2: 3:
0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0001 0001 0011
0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010
1
2
3
4
réponse
Quotient = 3 Reste = 1
I. Abdesslem
Page : 60
Division version 3 du matériel
(cid:127) registre Diviseur 32-bit, UAL 32 bit, registre
Reste 64 bit, 0 registre Quotient.
Diviseur
32 bits
32-bit UAL
“HI”
reste
“LO”
Shift Left
(Quotient)
64 bits
Ecrire
Control
I. Abdesslem
Page : 61
Algorithme de division (version 3)
Début: placer la dividende dans la moitié droite reste
1.décalage du registre reste à gauche de 1 bit.
2. 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
Reste < 0
3a. Décalage du registre reste à gauche en insérant un 1 dans le nouveau bit
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.
nth répétition?
Non: < n repetitions
Oui: n répétitions
Décalage de la moitié gauche du registre reste à droite de 1 bit.
I. Abdesslem
Page : 62
Exemple de division (7 / 2)
Reste 0000 0111 0000 1110
1111 1110 0001 1100
1111 1100 0011 1000 0001 1000 0011 0001
0001 0001 0010 0011
1: 2:
1: 2: 1: 2:
1: 2:
3:
0001 0011
Diviseur 0010 0010
1
2
3
4
0010 0010
0010 0010 0010 0010
0010 0010
0010
réponse
Quotient = 3 Reste = 1
I. Abdesslem
Page : 63
Observations sur la version 3 de la division
(cid:127) Même matériel que la multiplication: UAL pour additionner ou soustraire, un registre 64 bit pour décaler à droite ou à gauche.
(cid:127) Les registres Hi et Lo de MIPS sont combinés pour être utilisées comme registre 64-bits à la division et à la multiplication.
(cid:127) 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:
(cid:127) –7 ÷ 2 = –3, reste = –1 (cid:127) –7 ÷ 2 = –4, reste = +1 (juste en formule mais plus
difficile à mettre en œuvre)
I. Abdesslem
Page : 64