Chapitre 4: Arithmétique des ordinateurs

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.

Représentation des nombres en binaire et complément à deux

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 :

• Le bit de poids fort (bit 31) sert de bit de signe : 0 pour les nombres positifs, 1 pour les nombres négatifs.
• Les nombres positifs vont de 0 à 2 147 483 647 (2^31 - 1).
• Les nombres négatifs vont de -1 à -2 147 483 648 (-2^31).

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.

Opérations logiques et arithmétiques en MIPS

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.

Conception de l’Unité Arithmétique et Logique (UAL)

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.

Instruction SLT (Set on Less Than)

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.

Détection de débordement (overflow)

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 :

• On additionne deux nombres positifs et que le résultat est négatif.
• On additionne deux nombres négatifs et que le résultat est positif.

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]

Amélioration des performances : retenue anticipée

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 :

• G = A AND B (génère une retenue)
• P = A XOR B (propage une retenue)

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.

Multiplication binaire

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 :

• Si le bit du multiplicateur est 0, on ajoute 0.
• Si le bit est 1, on ajoute une copie du multiplicande décalée selon la position du bit.

Plusieurs versions matérielles existent pour réaliser la multiplication :

Version 1

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.

Version 2

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.

Version 3

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.

Multiplication signée et algorithme de Booth

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 :

• On effectue des additions ou soustractions du multiplicande selon les transitions dans le multiplicateur.
• Les décalages sont utilisés pour avancer dans le calcul.

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

Division binaire

La division binaire est réalisée de manière similaire à la multiplication, avec plusieurs versions matérielles :

Version 1

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).

Version 2

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.

Version 3

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.

Division signée

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.

Points clés

• La représentation des nombres négatifs utilise le complément à deux, où le bit de poids fort est le bit de signe.
• L’UAL est construite à partir d’unités arithmétiques à 1 bit et réalise addition, soustraction, opérations logiques et comparaison.
• La détection du débordement se fait en comparant les retenues d’entrée et de sortie du bit de poids fort.
• La méthode de retenue anticipée accélère le calcul des additions en calculant les retenues en parallèle.
• La multiplication binaire est réalisée par addition conditionnelle et décalage, avec plusieurs architectures matérielles possibles.
• L’algorithme de Booth optimise la multiplication signée en réduisant le nombre d’opérations.
• La division binaire est similaire à la multiplication, avec plusieurs versions matérielles et un algorithme basé sur la soustraction répétée et le décalage.
• La division signée nécessite un traitement spécial pour gérer les signes du quotient et du reste.