Chapitre 4: Arithmétique des ordinateurs
Chapitre 4: Arithmétique des ordinateurs
Computer Architecture · notes
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce chapitre traite de l'arithmétique des ordinateurs, en expliquant comment les nombres sont représentés en binaire, comment les opérations arithmétiques sont réalisées au niveau matériel, et comment les problèmes liés aux nombres négatifs, au dépassement de capacité et aux opérations sur les nombres entiers sont gérés. Il s'inscrit dans un cours d'architecture des ordinateurs ou de systèmes numériques, visant à comprendre le fonctionnement interne des processeurs, notamment le jeu d'instructions MIPS.
Un nombre binaire est une suite de bits, chaque bit ayant une valeur pondérée selon sa position. Par exemple, le nombre binaire 1011 représente en base dix :
(1 × 2^3) + (0 × 2^2) + (1 × 2^1) + (1 × 2^0) = 8 + 0 + 2 + 1 = 11
Dans une architecture MIPS, un mot machine est constitué de 32 bits. Le bit de poids faible est le bit le plus à droite, tandis que le bit de poids fort est le plus à gauche.
Pour représenter les nombres négatifs, on utilise la convention du complément à deux. Cette méthode évite d'avoir deux représentations pour zéro et facilite les opérations arithmétiques. Dans cette représentation :
Un nombre binaire x de 32 bits est donc interprété comme :
(x31 × -2^31) + (x30 × 2^30) + ... + (x1 × 2^1) + (x0 × 2^0)
Pour obtenir l'opposé d'un nombre, on inverse tous ses bits puis on ajoute 1. Par exemple, pour -2 :
2 dix = 0000 0000 0000 0000 0000 0000 0000 0010 (binaire) Inverse des bits = 1111 1111 1111 1111 1111 1111 1111 1101 Ajouter 1 = 1111 1111 1111 1111 1111 1111 1111 1110 = -2 dix
Cette méthode est appelée extension signée lorsqu'on convertit un nombre binaire de n bits en un nombre de plus de n bits en répliquant le bit de signe.
Les instructions MIPS permettent de manipuler les bits par décalage logique à gauche (sll) ou à droite (srl), en remplissant les bits libérés par des zéros. Par exemple, décaler de 8 bits vers la gauche le contenu du registre $16 contenant 0000...1101 donne :
0000 0000 0000 0000 0000 1101 0000 0000
Les instructions and, or, andi, ori permettent respectivement des opérations ET et OU entre registres ou entre registre et valeur immédiate.
L’UAL est le composant central du processeur qui réalise les opérations arithmétiques et logiques. Elle prend en entrée deux opérandes de 32 bits, un code de contrôle de 4 bits indiquant l’opération à effectuer, et produit un résultat de 32 bits ainsi que des indicateurs comme le bit de retenue, le bit de débordement et le bit zéro.
L’UAL est construite à partir de 32 unités arithmétiques élémentaires à 1 bit connectées en série. Chaque unité à 1 bit réalise des opérations logiques (and, or) et arithmétiques (addition complète à 1 bit).
Pour la soustraction, on utilise la relation :
A - B = A + (–B) = A + B̅ + 1
où B̅ est l’inverse bit à bit de B. Le signal d'inversion et la retenue d'entrée (CarryIn) sont utilisés pour activer cette opération.
L’instruction slt ($1, $2, $3) positionne le registre $1 à 1 si $2 < $3, sinon à 0. L’UAL ne réalise pas directement cette instruction. On utilise le bit de poids fort (s31) du résultat du calcul $2 - $3. Si ce bit est 1 (résultat négatif), on place 1 dans le bit de poids faible du registre destination et 0 dans les autres.
Le débordement se produit lorsque le résultat d’une opération dépasse la capacité de représentation. Il n’y a pas de débordement lorsqu’on additionne deux nombres de signes différents. En revanche, il y a débordement si :
La détection s’effectue en comparant le CarryIn et le CarryOut du bit de poids fort (bit 31) :
Débordement = CarryIn[31] XOR CarryOut[31]
Pour accélérer le calcul de la retenue dans l’addition, on utilise la méthode de la retenue anticipée. On définit :
Les retenues intermédiaires sont calculées par :
C1 = G0 + C0 · P0
C2 = G1 + G0 · P1 + C0 · P0 · P1
C3 = G2 + G1 · P2 + G0 · P1 · P2 + C0 · P0 · P1 · P2
Cette méthode permet de réduire le temps de propagation de la retenue lors de l’addition.
La multiplication binaire non signée entre un multiplicande de m bits et un multiplicateur de n bits produit un résultat de m + n bits. La multiplication binaire est simple :
Plusieurs versions matérielles existent pour réaliser la multiplication :
Elle utilise un registre multiplicande de 64 bits, une UAL 64 bits, un registre produit de 64 bits et un registre multiplicateur de 32 bits. L’algorithme consiste à tester le bit de poids faible du multiplicateur, ajouter le multiplicande au produit si ce bit est 1, puis décaler le multiplicande à gauche et le multiplicateur à droite, répété 32 fois.
Cette version est peu économique en matériel et lente car la moitié des bits du multiplicande sont souvent à zéro.
Le multiplicande reste fixe sur 32 bits, l’UAL est de 32 bits, le produit est un registre de 64 bits, et le multiplicateur est un registre de 32 bits. Le produit est décalé à droite à chaque étape. L’algorithme ajoute le multiplicande à la moitié gauche du produit si le bit de poids faible du multiplicateur est 1, puis décale le produit et le multiplicateur à droite. Cette version économise de l’espace et améliore la gestion des bits.
Le registre produit combine le produit et le multiplicateur sur 64 bits. L’algorithme est similaire à la version 2 mais utilise un seul registre pour le produit et le multiplicateur, ce qui simplifie le matériel.
L’algorithme de Booth est une méthode efficace pour multiplier des nombres signés en complément à deux. Il réduit le nombre d’opérations en remplaçant les chaînes de 1 dans le multiplicateur par une soustraction au début de la chaîne et une addition juste après la fin de cette chaîne. Cela permet d’optimiser le temps d’exécution en privilégiant les décalages, plus rapides que les additions.
Par exemple, pour multiplier 2 par 6 :
L’algorithme repose sur l’analyse des bits consécutifs du multiplicateur et applique les règles suivantes :
| ai-1 | ai | Opération |
|---|---|---|
| 0 | 0 | Ne rien faire |
| 0 | 1 | Ajouter le multiplicande |
| 1 | 0 | Soustraire le multiplicande |
| 1 | 1 | Ne rien faire |
La division binaire est réalisée de manière similaire à la multiplication, avec plusieurs versions matérielles :
Utilise un registre diviseur de 64 bits, une UAL 64 bits, un registre reste de 64 bits et un registre quotient de 32 bits. L’algorithme commence par placer le dividende dans le registre reste, puis soustrait le diviseur du reste. Si le reste est positif, un 1 est inséré dans le quotient, sinon la valeur est restaurée et un 0 est inséré. Le diviseur est décalé à droite à chaque étape. Ce processus est répété n+1 fois (n étant la taille en bits).
Le diviseur est de 32 bits, l’UAL de 32 bits, le reste de 64 bits, et le quotient de 32 bits. Le registre reste est décalé à gauche à chaque étape. La soustraction est effectuée sur la moitié gauche du reste. Si le reste est négatif, la valeur est restaurée et un 0 est inséré dans le quotient, sinon un 1 est inséré. Ce processus est répété n fois.
Le matériel est similaire à celui de la multiplication, avec un registre reste de 64 bits divisé en deux parties (Hi et Lo), un registre diviseur de 32 bits et une UAL de 32 bits. L’algorithme place le dividende dans la moitié droite du registre reste, décale le registre reste à gauche, soustrait le diviseur de la moitié gauche du reste, puis ajuste le quotient en fonction du signe du reste.
Pour la division signée, on effectue la division sur les valeurs absolues, puis on ajuste le signe du quotient et du reste selon les signes initiaux du dividende et du diviseur. Le dividende et le reste doivent avoir le même signe.