Architecture de Von Neumann

I/ Addition

1) Ou exclusif

Voici la table de vérité de (a ∧ ¬b) ∨ (¬a ∧ b) (on rappelle que 0 représente le faux et 1 représente le vrai)) :

L'opération ainsi réalisée est appelée ou exclusif et notée xor ou ⊕ : elle ne renvoie la valeur 1 que lorsque a≠b. Elle est à la base de l'addition binaire.

2) Additionneur un bit

Voici une table d'addition de deux nombres a et b à un bit chacun :

On constate que le chiffre des unités se calcule par un ou exclusif entre a et b, et que le chiffre des deuxaines (ou retenue engendrée) se calcule par un et entre a et b. On a là, la base d'un additionneur de deux nombres binaires avec génération d'une retenue.

Pour additionner a et b avec une éventuelle retenue c, si on note r la retenue engendrée par a+b (chiffre des deuxaines) et s le chiffre des unités de a+b (s==a⊕b) alors on entre s et c dans une autre porte ou exclusif (a⊕b⊕c==(a⊕b)⊕c=s⊕c). Et pour savoir si une retenue est engendrée, on peut faire (a∧b)∨(b∧c)∨(a∧c) comme le montre la table de vérité de cette expression :

Théorème (Shannon 1937) : on peut construire un additionneur binaire un bit avec retenue, uniquement en câblant des portes non, et et ou.

3) Additionneur 8 bits

Pour obtenir un additionneur 8 bits (additionneur d'octets), il suffit de brancher en cascade des additionneurs 1 bit avec retenue. Par exemple si deux registres A et B d'un octet chacun contiennent respectivement les nombres 86 (01010110 en binaire) et 61 (00111101) alors avant l'addition, on a :

Ensuite,

1. l'additionneur des deux chiffres des unités calcule 0+1=1 sans retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R							0
   S								1

2. l'additionneur des trois chiffres des deuxaines calcule 1+0+0=1 sans retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R						0	0
   S							1	1

3. l'additionneur des trois chiffres des quatraines calcule 1+1+0=0 avec retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R					1	0	0
   S						0	1	1

4. l'additionneur des trois chiffres des huitaines calcule 0+1+1=0 avec retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R				1	1	0	0
   S					0	0	1	1

5. l'additionneur des trois chiffres des seizaines calcule 1+1+1=1 avec retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R			1	1	1	0	0
   S				1	0	0	1	1

6. l'additionneur des trois chiffres des trente-deuxaines calcule 0+1+1=0 avec retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R		1	1	1	1	0	0
   S			0	1	0	0	1	1

7. l'additionneur des trois chiffres des soixante-quatraines calcule 1+0+1=0 avec retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	1	1	1	1	1	0	0
   S		0	0	1	0	0	1	1

8. l'additionneur des trois chiffres des cent-vingt-huitaines calcule 0+0+1=1 sans retenue

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	1	1	1	1	1	0	0
   S	1	0	0	1	0	0	1	1

La somme de 86 et 61 est, en binaire, 10010011 soit 147.

En réalité, les additionneurs 1 bit fonctionnent tous en même temps, et les délais successifs aboutissent (assez rapidement) à la stabilisation des retenues.

1. Au début il n'y a pas de retenue :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	0	0	0	1	0	1	0	0
   S	0	1	1	0	1	0	1	1

2. Avec les retenues l'addition se refait :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	0	0	1	0	1	0	0	0
   S	0	1	1	1	1	1	1	1

3. Puis une nouvelle stabilisation :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	0	0	1	1	1	0	0	0
   S	0	1	0	0	0	0	1	1

4. Encore une stabilisation :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	0	1	1	1	1	0	0	0
   S	0	1	0	1	0	0	1	1

5. Une autre :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	1	1	1	1	1	0	0	0
   S	0	0	0	1	0	0	1	1

6. Et une dernière :

   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1
   R	1	1	1	1	1	0	0	0
   S	1	0	0	1	0	0	1	1

4) En assembleur

Un additionneur de ce genre est présent (entre autres) dans l'ALU du microprocesseur Z80 (en bas à droite) :

Supposons qu'à l'adresse 42 de la mémoire, soit stocké le nombre 128, et que le registre PC contienne justement le nombre 42 :

Alors, au cours d'un cycle de calcul du CPU,

1. le contenu du registre PC est placé sur le bus d'adresse, déclenchant ainsi un cycle de lecture,
2. L'octet stocké à l'adresse 42 est lu : il s'agit de 128 (80 en hexadécimal ou 10000000 en binaire)
3. Cet octet est transféré dans le registre d'instructions I qui contient alors 10000000
4. Le contenu de PC est incrémenté (c'est-à-dire que 1 lui est additionné) :

   PC	0	0	1	0	1	0	1	1
   A	0	1	0	1	0	1	1	0
   B	0	0	1	1	1	1	0	1

5. Le mot 10000000 qui est dans I est décodé par la logique de décodage : le 10000 veut dire additionner à A et le 000 qui suit signifie que c'est B qui doit être additionné à A.
6. Donc c'est le circuit additionneur de l'ALU qui est activé, on voit que A est déjà branché à l'une des entrées ACU de l'additionneur, et B est, via un multiplexeur MUX, envoyé sur le bus interne et de là, à l'autre entrée TEMP.
7. L'additionneur effectue l'addition et renvoie le résultat 147 (soit 10010011) dans le registre A :

   PC	0	0	1	0	1	0	1	1
   A	1	0	0	1	0	0	1	1
   B	0	0	1	1	1	1	0	1

8. Le registre d'état est mis à jour selon le résultat du calcul. En particulier, son bit C (carry veut dire retenue) aurait été positionné s'il y avait eu une retenue de poids 256 à la fin de l'addition.

En assembleur Z80, l'octet 10000000 est traduit par ADD A, B.

II/ Décalage

1) Doublement

En binaire, pour doubler un registre, il suffit de décaler vers la gauche tous ses chiffres, en insérant un 0 à droite du registre. Par exemple si un registre contient le nombre 13

après décalage vers la gauche, il contient

soit 26 qui est le double de 13. Le bit le plus à gauche, qui est sorti du registre lors du décalage, est stocké comme flag de dépassement : il était nul donc il n'y a pas eu de dépassement de capacité.

Par exemple si, à l'adresse 43 de la mémoire, est stocké l'octet 00100000 soit SLA B (00100 codant SLA et comme déjà vu, 000 désignant le registre B), le prochain cycle d'exécution passe de

à

Il est bien plus rapide de faire un doublement par décalage, que d'additionner un registre avec lui-même.

2) Division par 2

Pour diviser un registre par 2, on effectue un décalage vers la droite. Le bit des unités est perdu, mais dans le Z80 il est stocké comme retenue.

Par exemple si à l'adresse 44 est stocké l'octet codant SRA A (soit 00101111 qui se décompose en 00101 pour SRA et 111 pour le registre A, un cycle machine passe de

à

avec un 1 dans le bit C de retenue. 73 est bien la moitié de 147 mais avec un reste de 1.

En résumé, le contenu de mémoire suivant

signifie, pour le Z80,

ADD A, B
SLA B
SRA A

III/ Multiplication

Il est possible de réaliser des circuits logiques combinatoires pour faire un multiplicateur, mais sur le Z80 on programme la multiplication en assembleur. Par exemple si on veut multiplier 13 par 11 en binaire :

    1101
×   1011
--------
    1101
   1101
 1101
--------
10001111

on voit qu'on obtient les termes à additionner (avec un additionneur binaire) par décalage du multiplicande, et on n'additionne les termes que si le bit correspondant du multiplicateur est égal à 1. Or celui-ci peut s'obtenir par SRA en regardant le bit C de retenue.

1) Programme assembleur

On suppose qu'au début

• A (produit) contient 0
• B contient 13 (multiplicande)
• C contient 11 (multiplicateur)
• D contient 4 (nombre de chiffres du multiplicateur)

Alors on utilise le programme en assembleur suivant :

label retour
SRA C
JP NC, suite
ADD A, B
label suite
SLA B
DEC D
JP NZ, retour
HALT

2) Déroulé

• La première instruction est SRA C. Elle donne

  A	0	0	0	0	0	0	0	0
  B	0	0	0	0	1	1	0	1
  C	0	0	0	0	0	1	0	1
  D	0	0	0	0	0	1	0	0

  et comme le registre C (à ne pas confondre avec le bit C) se terminait par un 1, ce 1 a été placé dans le bit C.
• La condition NC (not carry) n'est donc pas satisfaite, donc l'instruction de saut conditionnel JP NC, suite n'est pas exécutée.
• Le Z80 exécute ensuite ADD A, B. Cela donne

  A	0	0	0	0	1	1	0	1
  B	0	0	0	0	1	1	0	1
  C	0	0	0	0	0	1	0	1
  D	0	0	0	0	0	1	0	0

• Ensuite SLA B donne

  A	0	0	0	0	1	1	0	1
  B	0	0	0	1	1	0	1	0
  C	0	0	0	0	0	1	0	1
  D	0	0	0	0	0	1	0	0

• Ensuite DEC D (décrementer D, soit lui soustraire 1) donne

  A	0	0	0	0	1	1	0	1
  B	0	0	0	1	1	0	1	0
  C	0	0	0	0	0	1	0	1
  D	0	0	0	0	0	0	1	1

  Le bit Z n'est pas positionné puisque 3 est non nul.
• La condition NZ (not sero) est donc vérifiée, donc l'instruction JP NZ, retour est exécutée. Elle a pour effet d'écraser l'ancienne valeur de PC et la remplacer par l'adresse du label retour.
• On revient donc à SRA C qui donne

  A	0	0	0	0	1	1	0	1
  B	0	0	0	1	1	0	1	0
  C	0	0	0	0	0	0	1	0
  D	0	0	0	0	0	0	1	1

  avec un 1 dans le bit C.
• Comme il y a une retenue on passe à ADD A, B qui donne

  A	0	0	1	0	0	1	1	1
  B	0	0	0	1	1	0	1	0
  C	0	0	0	0	0	0	1	0
  D	0	0	0	0	0	0	1	1

  avec un 1 dans le bit C.
• Ensuite on passe à SLA B qui donne

  A	0	0	1	0	0	1	1	1
  B	0	0	1	1	0	1	0	0
  C	0	0	0	0	0	0	1	0
  D	0	0	0	0	0	0	1	1

• Ensuite on passe à DEC D qui donne

  A	0	0	1	0	0	1	1	1
  B	0	0	1	1	0	1	0	0
  C	0	0	0	0	0	0	1	0
  D	0	0	0	0	0	0	1	0

  avec 0 dans le bit Z puisque 2 est non nul.
• La condition NZ est donc vérifiée et l'adresse du label retour est chargée dans PC.
• Le Z80 exécute à nouveau SRA C qui donne

  A	0	0	1	0	0	1	1	1
  B	0	0	1	1	0	1	0	0
  C	0	0	0	0	0	0	0	1
  D	0	0	0	0	0	0	1	0

  avec 0 dans le bit C puisque C finissait par un 0.
• La condition NC est donc vérifiée et on charge dans PC l'adresse du label suite
• On passe directement à SLA B qui donne

  A	0	0	1	0	0	1	1	1
  B	0	1	1	0	1	0	0	0
  C	0	0	0	0	0	0	0	1
  D	0	0	0	0	0	0	1	0

• puis à DEC D qui donne

  A	0	0	1	0	0	1	1	1
  B	0	1	1	0	1	0	0	0
  C	0	0	0	0	0	0	0	1
  D	0	0	0	0	0	0	0	1

• Comme 1 n'est pas nul, la condition NZ est vérifiée, donc on charge dans PC l'adresse du label retour.
• Le Z80 exécute SRA C qui donne

  A	0	0	1	0	0	1	1	1
  B	0	1	1	0	1	0	0	0
  C	0	0	0	0	0	0	0	0
  D	0	0	0	0	0	0	0	1

  avec le 1 de fin du registre C stocké dans le bit C. La condition NC est donc fausse.
• Le Z80 exécute ADD A, B qui donne

  A	1	0	0	0	1	1	1	1
  B	0	1	1	0	1	0	0	0
  C	0	0	0	0	0	0	0	0
  D	0	0	0	0	0	0	0	1

• Le Z80 exécute SLA B qui donne

  A	1	0	0	0	1	1	1	1
  B	1	1	0	1	0	0	0	0
  C	0	0	0	0	0	0	0	0
  D	0	0	0	0	0	0	0	1

• Le Z80 exécute DEC D qui donne

  A	1	0	0	0	1	1	1	1
  B	1	1	0	1	0	0	0	0
  C	0	0	0	0	0	0	0	0
  D	0	0	0	0	0	0	0	0

  donc le bit Z est positionné puisque maintenant D==0.
• La condition NZ n'est plus vérifiée donc il n'y a plus de chargement de l'adresse de retour dans PC : on passe à l'instruction suivante qui est HALT et le programme s'arrête.

À la fin du programme, le registre A contient 10001111 soit le nombre 143 qui est bien le produit de 13 par 11.

3) Histoire

Cet algorithme a été proposé par Von Neumann en 1946, pour les plans du premier ordinateur américain, mais il est équivalent à un algorithme connu des égyptiens.