Architecture Logicielle et matérielle - laure.gonnord.orglaure.gonnord.org/pro/teaching/Archi1415_L2/Cours03_alu_circuits... · Au niveau physique, la mémoire ne supporte que des

Architecture Logicielle et matérielleCours 3 : unité arithmétique et logique

D’après les transparents de N. Louvet (univ Lyon1)

Laure Gonnordhttp://laure.gonnord.org/pro/teaching/

[email protected]

Licence d’info - Université Lyon 1 - FST

http://laure.gonnord.org/pro/teaching/

[email protected]

Plan

1 Retour sur le Modèle de Van NeumanMémoire centraleUnité centrale de traitement

2 Circuits logiques combinatoiresFonctions BooléennesCircuits logiques combinatoires

3 Construisons une ALU !Choix des opérations, choix des sortiesOpérations

Laure Gonnord (L2/FST/Univ Lyon1) ArchiL2 (LIF6) Cours 3 : Construction de l’ALU 2014 � 2 / 53 �

Retour sur le Modèle de Van Neuman


2 Circuits logiques combinatoires

3 Construisons une ALU !


Retour sur le Modèle de Van Neuman

Composition d’un ordinateur dans le modèle

une mémoire centrale, qui contient le programme et lesdonnées ;

une unité centrale de traitement (UCT), qui exécute unprogramme contenu en mémoire centrale ;

une (ou plusieurs) unité(s) d’entrée-sortie permettantl’échange d’informations avec l’environnement de l’UCT.

Un système d’interconnexion permet l’interaction entre cesunités.

Unité

centrale de

traitement

Mémoire centraleUnité

d’entrée/sortie


Retour sur le Modèle de Van Neuman Mémoire centrale






Mémoire centrale

La mémoire centrale contient deux types d’informations :

les instructions de différents programmes ;

les données traitées lors de l’exécution de cesprogrammes.

L’unité d’information élémentaire est le bit, chaque bit pouvantvaloir 0 ou 1. Un mot est une suite de bits, de longueur a prioriquelconque.

Au niveau physique, la mémoire ne supporte que des bits : lesdonnées et les instructions sont stockées sous forme de mots.

Ex (déjà vu !) : dans le code ASCII (American Standard Codefor Information Interchange), le caractère Y est codé 1011001.



Mémoire centrale

Caractéristiques de la mémoire centrale :

mémoire vive : infos écrites/lues par l’UCT sont perdueslors de la mise hors tension de l’ordinateur.

mémoire RAM (Random Access Memory) : cases àadresse unique, écrite/lue en temps constant

I l’UCT peut lire et écrire n’importe où dans la mémoire (àn’importe quelle adresse), dans un ordre quelconque.



Mémoires, adresses 1/2

La taille d’une case mémoire peut par exemple être de 8 bits(1B). C’est alors la plus petite unité adressable.

Chaque case mémoire possède un indice permettant del’identifier de manière unique, appelé adresse :

n cases mémoires : adresses 0 à n− 1

adresses codées en binaire : si m bits, 2m adressespossibles.

I Abstraction mémoire comme un tableau. Notation : mem[a]=case mémoire d’adresse a.



Mémoires, adresses 2/2Trois organisations possibles d’une mémoire de « 64 bits » :

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

154 bits

0

1

2

3

4

5

6

7

0

1

2

3

8 bits

16 bits

(a) (b) (c)

(a) : adresse codee sur 4 bits, car 24 = 16 adresses.

(b) : adresse codee sur 3 bits, car 23 = 8 adresses.

(c) : adresse codee sur 2 bits, car 22 = 4 adresses.



Note importante

ImportantLa mémoire stocke les données et les programmes.

Pour l’instant, on laisse de côté le stockage des programmes(suite d’instructions).


Retour sur le Modèle de Van Neuman Unité centrale de traitement






Unité centrale de traitement (UCT)Deux unités fonctionnelles :

L’unité de contrôle (UC) : gestion de l’exécution desinstructions.

L’unité arithmétique et logique (UAL, ou ALU) : effectueles opérations de traitement des données.

Unité de calculUnité de contrôle

Mémoire centrale

Unité centrale de traitement

Sorties

Entrées



Dans la suitePlan d’attaque :

Laissons temporairement de côté l’unité de contrôle.

Construisons l’ALU.

I Un petit détour par les circuits logiques de base.

CC by SA Rizo/Wikipedia


Circuits logiques combinatoires

1 Retour sur le Modèle de Van Neuman


3 Construisons une ALU !



Formule logique, circuit logique

Informations binaires :

bit 0 assimilé à false, 0

bit 1 assimilé à true, 1.

I Bits = valeurs de vérité. Opération sur les bits = formulesBooléennes/ circuits logiques.



Circuits logiques

On distingue deux types de circuits logiques :

circuits combinatoires : les signaux de sortie nedépendent que des signaux d’entrées du circuit à l’instantconsidéré.Ex : la plupart des circuits pour l’addition de nombresbinaires.

Les circuits séquentiels : propriétés de mémorisation, lessignaux de sortie dépendent des signaux d’entrées ducircuit à l’instant considéré, mais aussi de l’état du circuit.Ex : mémoires, registres, unité de commande. . .

I Circuits combinatoires pour l’ALU.


Circuits logiques combinatoires Fonctions Booléennes






Fonctions Booléennes/logiques - Objectif

On va écrire des fonctions avec des entrées booléennes, et dessorties Booléennes, i.e. à variables dans B = 0, 1 :

on se munit d’opérations de base : ou, et, non (qui ontquelques propriétés “classiques”).

on construit avec ces opérations de base des expressionsbooléennes.

Au passage(B,NOT,AND,OR) avec leurs propriétés “classiques” formentl’algèbre de Boole.



Table des opérations de base

Si a et b sont deux variables booléennes, on notera parcommodité :

NOT(a) = a, AND(a, b) = ab, OR(a, b) = a+ b.

a b a ab a+ b

0 0

0 1

1 0

1 1



Propriétés des opérations de base

Il est interdit d’apprendre ces propriétés par cœur• éléments neutres : a+ 0 = a, a·1 = a

• éléments absorbants : a+ 1 = 1, a·0 = 0

• idempotance : a+ a = a, a·a = a

• tautologie/antilogie a+ a = 1, a·a = 0

• commutativité : a+ b = b+ a, ab = ba

• distributivité : a+ (bc) = (a+ b)(a+ c), a(b+ c) = ab+ ac

• associativité : a+ (b+ c) = (a+ b) + c = a+ b+ c,

a(bc) = (ab)c = abc

• lois de Morgan : ab = a+ b,

a+ b = a·b

• autres relations : a+ (ab) = a, a+ (ab) = a+ b,

a(a+ b) = a, (a+ b)(a+ b) = a



Expressions booléennes, fonction booléenne

ab+ cb

Vocabulaire :

a, b, c, d sont des variables booléennes.

a, b, b, b sont les litteraux

Implicitement, cette expression représente la fonction

B4 → B, (a, b, c, d) 7→ ab+ cb



Expressions booléennes, fonction booléenne

Une fonction booléenne peut aussi être définie à l’aide d’unetable de vérité :Ex : On considère la fonction f : B2 → B définie par la table devérité suivante :

a b f(a, b)

0 0 1

0 1 0

1 0 0

1 1 0

I f(a, b) = ab est une expression booléenne représentant lafonction f .



Unicité de la représentation

Il n’y a pas unicité de la représentation d’une fonction par uneexpression. . .Ex : si f(a, b) = ab, alors on a aussi f(a, b) = a+ b.

On distingue donc deux formes normales :

La forme normale disjonctive : disjonction de conjonctionsde littéraux.Ex : abc+ ab+ ab.

La forme normale conjonctive : conjonction de disjonctionsde littéraux.Ex : (a+ b+ c)·(a+ b+ c)·(a+ b+ c).

I Unicité de la représentation.



Rappels (cf LIF3, . . . )

AlgoPour mettre une formule en FND ou FNC, on peut bidouiller laformule ou alors utiliser la table de vérité.

I Laissé au lecteur (voir TD)



D’autres fonctions utiles : XOR

XOR(a, b) = a⊕ b :a⊕ b = 1 ssi une seule des deux variables a et b a la valeur 1 :

a b a⊕ b

0 0 0

0 1 1

1 0 1

1 1 0

Le XOR peut s’exprimer à l’aide de AND, ORet NOT :

a⊕ b = (a+ b)ab = (a+ b)(a+ b) = ab+ ab.

L’opérateur XOR est commutatif et associatif.



D’autres fonctions utiles : NAND NOR

a b ab a+ b

0 0 1 1

0 1 1 0

1 0 1 0

1 1 0 0

NAND(a, b) = ab = a+ b.

NOR(a, b) = a+ b = ab.


Circuits logiques combinatoires Circuits logiques combinatoires







Un signal logique est un dispositif physique pouvanttransmettre une valeur de vérité d’un endroit à un autre (doncaussi un bit), et sera représenté par un trait.

Vu de l’extérieur, un circuit logique présente des signauxd’entrée et de de sortie : chaque signal de sortie est unefonction logique des signaux d’entrée.



Portes

Les portes logiques sont les briques de base pour laréalisation de circuits logiques plus complexes :

XOR

NAND

NOR

NOT

AND

OR a+ bab

ab

ab

aaab

ab

ab

a+ b

ab

a⊕ b



Cicruit combinatoire bien formé

Un circuit combinatoire bien formé (CCBF) peut être formé :

par une porte de base,

par un fil,

par la juxtaposition de deux CCBFs posés l’un à côté del’autre,

en connectant les sorties d’un CCBF aux entrées d’unautre CCBF,

en connectant entre elles deux entrées d’un CCBF.



Circuit bien formé

On obtient un graphe sans cycle sur les portes de bases. Ons’interdit :

de faire des cycles, car cela permettrait des situations maldéfinies, e.g.,

0 1

1 0

1

0 1

0

de connecter des sorties entre elles (si une sortie est 1 etl’autre 0 ?)



Exemple

Réalisation des portes NOT, AND et OR à l’aide de portesNAND et de portes NOR.

a = a+ 0,

ab = a+ b = a+ 0 + b+ 0,

a+ b = a+ b = a+ b+ 0.

a = a·1,

ab = ab = ab·1,

a+ b = ab = (a·1)(b·1).

I le dessin des circuits est laissé au lecteur.



Exemple en LOGISIM

Il existe des simulateurs de circuits logiques. Nous allonsutiliser LOGISIM :

http://www.cburch.com/logisim/

I Démo !


http://www.cburch.com/logisim/

Construisons une ALU !

1 Retour sur le Modèle de Van Neuman

2 Circuits logiques combinatoires



Construisons une ALU !

ALU - spécification

Nous voulons réaliser un circuit selon la spécification suivante :

selon un signal de contrôle, une opération est réalisée.

3 opérations : addition, soustraction, test d’égalité

Ceci est une simplification, une vraie ALU possède bien plusd’opérations

Constructions de circuitsLa méthode de construction de ces circuits est à connaître, pasle résultat !


Construisons une ALU ! Choix des opérations, choix des sorties






Décodeur

Un décodeur n vers 2n est un circuit qui présente :

n entrées ei, qui forment l’entier (en−1 . . . e0)2 ;

2n sorties si, indicées de 0 à 2n − 1.

Lorsque les lignes d’entrée forment un entier (en−1 . . . e0)2, laseule ligne de sortie active est la ligne s(en−1...e0)2 .I Démo LOGISIM.



Décodeur : construire un décodeur 3 vers 8

à vous !



Décodeur suite

Décodeur 3 vers 8 :

s7

s0

s1

s2

s3

s4

s5

s6

e0e1e2e2 e1 e0

s7

s6

s5

s4

s3

s2

s1

s0

Decodeur3 vers 8



Multiplexeur

Un multiplexeur 2n vers 1 est un circuit qui présente :

2n entrées ei indicées de 0 à 2n − 1 ;

n lignes de sélection, qui forment l’entier (cn−1 . . . c0)2 ;

1 sortie s.

Lorsque les lignes de sélection forment un entier (cn−1 . . . c0)2,

s = e(cn−1...c0)2 .

Une des entrées est sélectionnée. (démo LOGISIM)



Multiplexeur (suite) - exemple 2 vers 1

Mux01c0

e1 e0

s

s

e1 e0

c0



Multiplexeur (suite) - exemple 8 vers 1Ex : Multiplexeur 8 vers 1.

e0e1e2e3e4e5e6e7e0e1e2e3e4e5e6e7

c0c1c2c0c1c2

Decodeur3 vers 8

7

6

5

4

3

2

1

0

ss

Multiplexeur8 vers 1



Multiplexeur (suite)

Un multiplexeur k·2n vers k est un circuit qui présente :

k·2n entrées ;

n lignes de sélection ;

k signaux de sortie.

Un tel multiplexeur sélectionne k signaux parmi les k·2n

signaux d’entrée.



Multiplexeur (suite) - ex 16 vers 8

a

b

8

8

8 s

Mux.16 vers 8

c

1

Exercice : comment réaliser un mux. 8 vers 4 avec des mux. 2vers 1 ?


Construisons une ALU ! Opérations






Additionneur - half adder

Pour la conception d’additionneurs, une brique qui peut êtreutilisée est le demi-additionneur ou half adder :

entrées : deux bits à sommer a et b ;

sorties : un bit de somme s et un bit de retenue sortante rs.

a b s rs

0 0

0 1

1 0

1 1

On constate que

s = . . . et rs = . . .



Half-adder, dessin !On en déduit le circuit suivant à remplir :

half

adder

(HA)

a b

s

a b

s

rsrs

Warning ! Un demi-additionneur ne peut pas prendre encompte de retenue entrante. . .



Full adder

entrées : deux bits à sommer a et b, et un bit de retenueentrante re ;

sorties : un bit de somme s et un bit de retenue sortante rs.

a b re s rs

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1



Full adder, le circuitOn constate que

s = a(b⊕ re) + a(b⊕ re) = a⊕ (b⊕ re) = a⊕ b⊕ re et

rs = abre + abre + abre + abre

= (ab+ ab)re + ab(re + re) = (a⊕ b)re + ab.

On déduit des expressions précédentes le circuit d’unadditionneur 1 bit complet ou (full adder) :

adder

full

(FA)

a b

s

rs

HA

HA

a b

s

re

rs re

a b

s

rs

re



k-bits AdditionneursOn peut enchaîner k full adders de manière à obtenir unadditionneur de deux entiers naturels de k bits.

FA FA FA FA rs re

s0s1s2s3

add4rs re

s0s1s2s3

b3 a3 b2 a2 b1 a1 b0 a0b3 a3 b2 b1a2 a1 b0 a0

On peut répéter la manœuvre pour obtenir un additionneur8 bits :

add4

4

4 4

add4rs

b7...4

4

4 4

s7...4

re

s3...0

a3...0a7...4 b3...0

I on propage la retenue comme “à la main”.Laure Gonnord (L2/FST/Univ Lyon1) ArchiL2 (LIF6) Cours 3 : Construction de l’ALU 2014 � 50 / 53 �


Soustraction

Pb : Réaliser la soustraction de deux entiers encodés encomplément à deux sur 8 bits

a− b = a+ (−b) = a+ compl(b)− 1

I Voir en TD la construction du soustracteur-additionneur.



Test d’égalité - ALU

À ce stade :

On peut déduire de la soustraction le test d’égalité.

On peut avec un multiplexeur choisir quelle opérationchoisir selon un code fixé à l’avance.

I Cf TD/TP



Conclusion

Unité

d’Entrées/Sorties

Mémoire centrale

Unité centrale de traitement

Unité de contrôle

et Logique

Unité Arithmétique

On a construit l’ALU en utilisant des circuits combinatoires.


Documents

Architecture Logicielle et matérielle - laure.gonnord.orglaure.gonnord.org/pro/teaching/Archi1415_L2/Cours03_alu_circuits... · Au niveau physique, la mémoire ne supporte que des