Département IF / Architecture Matérielle

Architecture des Circuits : Cahierd’Exercices

Table des matières

Table des matières 1

1 Représentation des nombres et arithmétique entière 31 Entiers représentables et ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . 32 Nombres entiers relatifs, codage en complément à 2 . . . . . . . . . . . . . . . . . . . . . 33 Operations en complément à deux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.1 Addition et calcul de l’opposé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.2 Extension de signe en complément à 2 . . . . . . . . . . . . . . . . . . . . . . . . 43.3 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Calcul booléen 51 Calcul booléen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Expression algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Circuits logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Multiplexeur et démultiplexeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Circuits combinatoires 71 Prise en main de Logisim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Additionneur 1 bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Additionneur 8 bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Additionneur / Soustracteur 8 bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Registres et mémoires 101 Registres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1 Latch et flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2 Flip-flop avec reset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Registre à commande de chargement . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Registre à n bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 Un petit compteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Mémoires adressables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1 Observation du comportement d’une mémoire . . . . . . . . . . . . . . . . . . . . 112.2 Réalisation d’un démux 1 vers 8 de 1 bit . . . . . . . . . . . . . . . . . . . . . . . 112.3 Réalisation d’un mux 8 vers 1 de 8 bits . . . . . . . . . . . . . . . . . . . . . . . . 122.4 Construction d’une mémoire de 8 mots de 8 bits . . . . . . . . . . . . . . . . . . . 12

1

5 Automates 131 Sur papier ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3 Protocole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.4 Chemin de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.5 Automate de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.6 “Exécution” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 En Logisim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1 Construction de l’automate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Construction du diviseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Simulez et corrigez votre chronogramme si besoin . . . . . . . . . . . . . . . . . . 19

6 Un embryon de machine de von Neumann 201 Le modèle de von Neumann : processeur et mémoire . . . . . . . . . . . . . . . . . . . . 202 Un processeur qui parcourt la mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Les branchements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2

Chapitre 1

Représentation des nombres etarithmétique entière

1 Entiers représentables et ordres de grandeur

QUESTION 1 I Quels sont les plus grands nombres codables en base 2 sur les tailles suivantes. Ondemande une valeur exprimée en décimal.

1 bit (valeur exacte)

4 bits (valeur exacte)

8 bits (valeur exacte)

1 byte (valeur exacte)

2 bytes (valeur exacte)

4 bytes (valeur approchée)

8 bytes (valeur approchée)

QUESTION 2 I Pour chacune des paires de valeurs ci-dessous, laquelle est la plus grande ?

1033 et 280

1010 et 235

2 Nombres entiers relatifs, codage en complément à 2

QUESTION 3 I Écrire la table des correspondances binaire↔décimal pour tous les nombres entiers signéscodés sur trois bits en complément à deux.

QUESTION 4 I Comment pouvez-vous savoir si l’entier, codé en complément-à-deux sur 16 bits,

1010 1110 1010 1111

est positif ou négatif ? Quelle est sa valeur ? Donnez le code binaire de son opposé.

QUESTION 5 I Donner la représentation binaire, en complément à 2 sur huit bits, des nombres suivants(tous négatifs) :

−1110

−2210

−4410

−4710

−12510

QUESTION 6 I Convertir en base 10 les nombres suivants codés en complément à deux :

11111111

3

01001111

10011111

111. . . 111110

QUESTION 7 I En utilisant la technique décrite dans le poly, convertissez (11011)2 puis (56)9 en décimal.

QUESTION 8 I Utilisez la méthode à base de divisions euclidiennes décrite dans le poly pour convertirn = (414)10 en binaire, puis (3452)10 en base 8.

QUESTION 9 I Entre les bases 2, 8 et 16, des méthodes plus directes peuvent être utilisées : par exemple,tout chiffre octal est représenté par un entier sur trois bits, et tout entier sur trois bits est représenté par unchiffre octal. Justifiez cette méthode de convertion entre les bases 2 et 8. Convertissez (34521)8 en base 2puis 16.

3 Operations en complément à deux

3.1 Addition et calcul de l’opposé

QUESTION 10 I Posez, en complément à deux sur 8 bits, les additions suivantes : (10001010)2 +(00001011)2, (10001010)2 + (10001011)2, (01001010)2 + (11001010)2.

QUESTION 11 I Calculez l’opposé de (10001010)2 en complément à 2 sur 8 bits, et vérifiez que votrerésultat est correct.

QUESTION 12 I En complément à 2 sur p bits, quel est le seul cas produisant un dépassement de capacitépour le calcul de l’opposé ?

QUESTION 13 I Calculez en binaire la soustraction 11012 − 01102

— en utilisant un algorithme qui ressemble à l’algorithme de soustraction décimal (facultatif)

— en utilisant le complément à 2. Rappel : on écrira

11012 − 01102 ≡ 11012 − 01102 + 100002 ≡ 11012 + 11112 − 01102 + 1

Interprétez 11012, 01102 et votre résultat comme des entiers naturels, et vérifiez votre calcul.Si les trois nombres sont interprétés comme des entiers relatifs, que pouvez vous dire ?

3.2 Extension de signe en complément à 2

QUESTION 14 I Comment sont représentés (34)10 et (−42)10 en complément à 2 sur 8 bits (complément à28) ?

QUESTION 15 I Comment sont représentés (34)10 et (−42)10 en complément à 2 sur 12 bits (complémentà 212) ?

3.3 Multiplication

QUESTION 16 I Effectuer – en binaire – les opérations suivantes :

111111112 × 12

111111112 × 102

111111112 × 1002

110100112 × 10012

110100112 × 1101012 (facultatif)

111111112 × 111111112 (facultatif)

Comparez la taille du résultat par rapport à la taille des opérandes. Quelle règle générale peut-on endéduire ?

QUESTION 17 I Donner la représentation en hexadécimal de quelques nombres utilisés dans les exercicesprécédents. Comment procédez-vous et pourquoi ? Quel est l’intérêt du codage hexadécimal ?

4

Chapitre 2

Calcul booléen

Dans ce TD, on s’intéresse tout d’abord au calcul booléen dans l’exercice 1, puis dans les exercices suivantsà l’équivalence expression booléenne↔ table de vérité↔ circuit combinatoire. Le dernier exercice détaillenotamment la construction d’un multiplexeur et d’un démultiplexeur.

1 Calcul booléen

QUESTION 1 I Rappeler la règle de De Morgan sous ses deux formes.

QUESTION 2 I Prouver les équivalences suivantes :

(1) a.b + a.b = b (2) a + a.b = a

(3) a + a.b = a + b (4) a.b + a.c = a.b + a.c + b.c

QUESTION 3 I Simplifier les expressions suivantes, notamment grâce au théorème de De Morgan :

s1 = (x + y )(x + z)(y + z)

s2 = x .y + yz + (x + z)(y + xz)

s3 = y (x + z) + x(y + z) + (y + z)(xy + x(y + z) )

2 Expression algébrique

QUESTION 4 I Donner une expression booléenne de la fonction f (x , y , z) qui vaut 1 si et seulement si lamajorité de ses trois arguments vaut 1.

QUESTION 5 I Donner (sans chercher à la simplifier) une expression booléenne de la fonction g(a, b, c)définie par la table de vérité suivante :

a b c s0 0 0 10 0 1 00 1 0 10 1 1 11 0 0 11 0 1 01 1 0 11 1 1 1

5

3 Circuits logiques

QUESTION 6 I Donner une expression algébrique des sorties s1 et s2. Établir la table de vérité. La fonctioncalculée par ce circuit vous est-elle familière ?

a

b

s2 s1

QUESTION 7 I Dessiner un circuit logique pour chacune des fonctions f et g de l’exercice précédent enutilisant uniquement des portes logiques (et, ou, non, xor, nand, nor)

4 Multiplexeur et démultiplexeur

On rappelle ci-dessous le symbole générique d’un multiplexeur à N entrées.

y

s

x0

x1

xN−1|x|

|y|

|s|

Intuitivement parlant, ce composant «recopie» l’une de ses entrées, xi , sur sa sortie y . On choisit la valeurde i en positionnant l’entrée de sélection (notée s sur le symbole). Ainsi, si cette entrée de sélectionest codée sur |s| bits, elle permet de sélectionner parmi N = 2|s| entrées différentes. Par ailleurs, unmultiplexeur peut être conçu pour travailler avec des données composées de plusieurs bits ; dans ce cas-là,la largeur |y | de la sortie sera la même que la largeur |x | des entrées.

QUESTION 8 I Écrire la table de vérité complète d’un multiplexeur à 2 entrées de 1 bit chacune (on parleaussi de «multiplexeur 2-vers-1 à 1 bit»).

QUESTION 9 I Donner une expression booléenne de la fonction réalisée par ce multiplexeur, et dessiner lecircuit logique correspondant.

QUESTION 10 I On s’intéresse maintenant à un multiplexeur à 4 entrées de 1 bits (on parle aussi de«multiplexeur 4-vers-1 à 1 bits»). Proposer une implémentation de ce circuit à l’aide de quelques instancesdu multiplexeur 2 vers 1 construit dans la question précédente. Dessiner le circuit logique correspondant.

QUESTION 11 I Dessiner un circuit logique équivalent à un démultiplexeur 1-vers-4 à 1 bit.

6

Chapitre 3

Circuits combinatoires

1 Prise en main de Logisim

Logisim est installé sur les machines du département IF, ici :

/opt/logisim-2.7

Il a été développé en java et se lance en tapant, depuis une ligne de commande shell :

java -jar /opt/logisim-2.7/logisim-generic-2.7.1.jar

Le logiciel est disponible gratuitement depuis http://www.cburch.com/logisim/.

QUESTION 1 I Afin de vous permettre de prendre en main l’outil, suivez le tutoriel suivant, qui vous faitcréer un circuit réalisant la fonction xor :

http://www.cburch.com/logisim/docs/2.7/en/html/guide/tutorial/index.html

2 Additionneur 1 bit

Dans Logisim, créez un nouveau projet. Vous y créerez tous les circuits demandés dans les différentesséances de TP.

QUESTION 2 I Votre premier circuit dans ce projet réalisera l’addition 1 bit. Ce circuit possède 3 entrées a,b et c_in représentant respectivement les deux valeurs à additionner et la retenue entrante de l’addition. Ilpossède 1 sortie s dénotant la valeur de la somme ainsi que 1 sortie c_out dénotant la valeur de la retenuede sortie.On vous rappelle la définition de s et c_out :

s = (a xor b) xor c_in

c_out = (a and b) or (a and c_in) or (b and c_in)

Attention à ce que la simulation soit bien activée ! Dans le menu “Simulate”, choisissez “Simulationenabled” !Vous aurez remarqué que, par défaut, les portes de votre circuit ont plus d’entrées que ce que vous utilisez.Logisim permet de changer ces paramètres dans le "cadre des attributs", en bas à gauche de la fenêtre.Ce cadre permet notamment de nommer les entrées (attribut "label") de changer l’orientation des portes(attribut "facing") et leur nombre d’entrées (attribut "number of inputs").Au delà de l’exécution pas-à-pas, dirigée par le changement des valeurs d’entrées du circuit, que vous avezutilisée dans le tutoriel ci-dessus, Logisim offre un certain nombre d’outils pour valider le comportement devos petites créations. Ceux-ci sont accessibles par 1 Project > Analyze Circuit.Logisim vous propose notamment, pour le circuit en cours d’édition :

— La liste de ses entrées et sorties ;

— Sa table de vérité ;

— Une version textuelle de l’expression booléenne réalisée pour chacune des sorties.

1. voir http://www.cburch.com/logisim/docs/2.7/en/html/guide/analyze/index.html

7

3 Additionneur 8 bits

Pour construire un additionneur 8 bits, vous n’allez pas ( !) copier-coller 8 fois les portes que vous venezd’utiliser pour l’additionneur 1 bit. Plutôt, vous allez encapsuler votre additionneur 1 bit dans un composantque vous pourrez ensuite réutiliser 8 fois pour obtenir l’additionneur 8 bits.

QUESTION 3 I Commencez par suivre le tutoriel mis en place par les auteurs de Logisim, ici :

http://www.cburch.com/logisim/docs/2.7/en/html/guide/subcirc/index.html

Concentrez-vous sur les parties intitulées Creating circuits, Using subcircuits ainsi que Editing subcir-cuit appearance. Dans cette dernière section, vous apprendrez à modifier la forme des composants quevous créez et surtout à nommer les ports d’entrée/sortie de vos composants.Nommez les ports de votre additionneur, par exemple a, b et c_in pour les entrées et s et c_out.Changez ensuite le nom de votre circuit (jusqu’ici main) pour, par exemple, add1bit.Enfin, créez un nouveau circuit dans le même projet en utilisant la petite croix verte ici :

Changez son nom pour add8bits.

QUESTION 4 ICréez maintenant votre additionneur 8 bits en utilisant l’additionneur 1 bit de la section précédente.Pour le tester, vous pouvez vous servir de “pin ports” d’entrée/sortie d’une taille plus grande que celle pardéfaut (1 bit). Pour cela, sélectionnez l’outil “pin port” depuis la barre d’outils. Puis, dans l’encart en bas àgauche de la fenêtre “Tool : Pin” sélectionnez 8 pour le champ “data bits” (voir figure ci-dessous).

Pour pouvoir connecter ces ports à vos composants, vous utiliserez des “Splitter” qui vous permettront deregrouper des fils. Encore une fois, aidez-vous de la documentation en ligne :

http://www.cburch.com/logisim/docs/2.7/en/html/guide/bundles/splitting.html

Testez votre circuit en réalisant plusieurs additions. Vous prendrez bien garde à l’initialisation de la retenueentrante de votre additionneur.

8

4 Additionneur / Soustracteur 8 bits

Comme brillamment décrit dans le poly du cours, on peut profiter de la circuiterie de l’additionneur pour créerun circuit additionneur/soustracteur. Les modifications nécessaires se basent sur le calcul du complémentbinaire d’un deux des chiffres paramètres de la soustraction. Pour deux entiers dont on veut calculer ladifférence A-B, on calcule le complément du second, B, chaque bit de B étant défini par la négation du bitcorrespondant dans B. Puis, on calcule l’addition A+B+1.Pour réaliser cela à partir de votre additionneur 8 bits, vous utiliserez la retenue entrante, qui permettramaintenant de décider si on souhaite une addition (elle vaut alors 0) ou une soustraction (elle vaut alors 1).Cette entrée conditionne la complémentation de la deuxième entrée de l’opération, ainsi que la valeur desa retenue d’entrée. Le choix entre B et B se fait à l’aide d’un xor pour chaque bit de B, prenant commepremière entrée B et comme seconde entrée la retenue entrante de votre opération.

QUESTION 5 I Réalisez un additionneur / soustracteur 8 bits en suivant les indications précédentes.

Pour rendre votre circuit plus lisible, on vous encourage à encapsuler les 8 xor dans un composant dédié.

9

Chapitre 4

Registres et mémoires

Jusqu’à présent on s’est contenté de décrire des circuits combinatoires : la valeur des sorties de votreadditionneur à un instant donné t ne dépend pas du passé, mais uniquement de la valeur de ses entrées àcet instant précis.

C’est très bien, mais on ne va pas aller très loin avec ça. Très vite, on va vouloir faire des calculs qui vontnécessiter plusieurs opérations successives : à chaque étape, une opération combinatoire produira unrésultat temporaire qui sera une opérande d’une opération à l’étape suivante. Ces étapes sont les fameuxinstants successifs de l’exécution de notre programme et de tels circuits sont appelés circuits séquentielset seront abordés plus en détails dans les chapitres 5 et 6.

Pour pouvoir construire de tels circuits, il va nous falloir des petits circuits pour mémoriser des valeurs, d’uninstant sur l’autre. Vous allez maintenant découvrir comment on construit de tels composants qu’on nommeregistres, en partant d’éléments simples appelés verrous (en anglais latch), eux-mêmes construits à partirde portes logiques. Ce chapitre aborde la construction de ces éléments.

1 Registres

NB : Créez chacun des circuits demandés séparément dans Logisim, notamment pour pouvoir facilement yrevenir plus tard.

1.1 Latch et flip-flop

QUESTION 6 I Construisez un verrou (latch ainsi qu’un registre 1 bit (flip-flop) dans Logisim.Dans le poly du cours (chapitre 4.2) ainsi que dans les transparents, vous trouverez une description de cesdeux composants. Vous trouverez le mux dans la bibliothèque de portes de Logisim.

QUESTION 7 I Remplissez le chronogramme suivant pour vous assurer que vous comprenez le comporte-ment du flip-flop.

out

clock

in

1.2 Flip-flop avec reset

QUESTION 8 I Complétez votre flip-flop afin de permettre sa remise à zéro.

Pour cela, créez un nouveau circuit qui utilise votre flip-flop précédent et possède une entrée supplémentairereset.

10

1.3 Registre à commande de chargement

QUESTION 9 I Ajoutez une commande de chargement à votre registre.

Pour cela, encapsulez votre flip-flop à reset, et étendez-le une entrée supplémentaire enable : la valeur duregistre n’est modifiée pour prendre la valeur d’entrée que si enable est vrai. Sinon, la sortie conserve savaleur actuelle.

Remarque : Vous venez de construire un registre complet à 1 bit, qui vous permet de conserver uneinformation sur plusieurs cycles d’exécution et de changer cette information à la demande, grâce à lacommande enable.

1.4 Registre à n bits

On ne sait pour l’instant que mémoriser 1 bit. Pour aller plus loin, il va nous falloir de quoi mémoriserdes paquets de bits. En pratique, la taille des registres est très liée à d’autres éléments de l’architectureconcernée : taille des bus, taille de la mémoire. Pour ce TP, nous nous arrêterons à des registres 8 bits.Contrairement aux différents verrous et flip-flop que nous avons construits jusque-là, la complexité ne sesitue pas dans le comportement temporel mais dans le nombre des boîtes et des connexions constituant lecircuit.

QUESTION 10 I Construisez un registre 8 bits en collant côte-à-côte 8 registres 1 bit. Veillez à la synchro-nisation de l’ensemble.

1.5 Un petit compteur

Nous allons maintenant concevoir un circuit qui va nous permettre de compter. La valeur du compteur seraenregistrée dans un registre 8 bits. Nous compterons donc de la valeur 0 à la valeur 28 − 1.

QUESTION 11 I Construisez ce compteur en utilisant le registre que vous venez de construire ainsi quel’additionneur 8 bits réalisé plus tôt (voir section 3).

Parce que c’est trop beau, vous pouvez maintenant lancer une simulation en choisissant tick enabled dansle menu Simulate. Vous pouvez même régler la fréquence assez haut pour vérifier rapidement que votrecompteur se comporte “bien comme il faut” lorsqu’il atteint la borne sup.

2 Mémoires adressablesLorsqu’on veut stocker beaucoup de données en même temps, utiliser des registres indépendants impliqueune trop grande complexité d’interconnexion (i.e. il y a trop de filasse). On invente alors (tadam) desmémoires adressables.Dans cette partie, vous allez implémenter une telle mémoire adressable. Elle sera petite (8 mots de 8 bits),mais vous constaterez également qu’étendre ce composant à des capacités plus grandes est simple.

2.1 Observation du comportement d’une mémoire

A la fin de la séance, vous aurez construit une mémoire adressable de 8 mots de 8 bits. Ce composant estpar ailleurs déjà implémenté dans Logisim.

QUESTION 12 I Testez une RAM de cette taille, en suivant le tutorial sur le site de Logisim :

http://www.cburch.com/logisim/docs/2.3.0/libs/mem/ram.html

Choisissez une RAM de type Separate load and store ports : c’est celle-là que vous allez construire dans lasuite du TP.

2.2 Réalisation d’un démux 1 vers 8 de 1 bit

Un dé-multiplexeur est un composant qui réalise un aiguillage. On se donne 1 entrée de données, k=dlog2neentrées de sélection et n sorties de données. À l’intérieur, il faut trouver la bonne combinaison de porteslogiques ....

QUESTION 13 I Réalisez un démultiplexeur 1 vers 8 à 1 bits.

11

2.3 Réalisation d’un mux 8 vers 1 de 8 bits

Cet aiguillage se fait aussi dans l’autre sens, pour pouvoir envoyer une des n entrées vers l’unique sortie.

QUESTION 14 I Réalisez ce composant multiplexeur n vers 1, avec n=8, pour des entrées booléennes (1bit chacune) et une sortie booléenne.

Remarquez que ces circuits ont déjà été abordés sur papier.

Cet aiguillage manipule des fils (entrées et sortie) de taille 1, on parle de multiplexeur 8 vers 1 à 1 bit.On peut le généraliser pour que les informations à sélectionner soient de taille quelconque. Ça se fait demanière hiérarchique, par exemple en encapsulant des multiplexeurs de m bits pour faire un multiplexeurde 2m bits.

QUESTION 15 I Réalisez un multiplexeur 8 vers 1 à 2 bits. Puis à 4 bits, puis à 8 bits.

2.4 Construction d’une mémoire de 8 mots de 8 bits

QUESTION 16 I Concevez maintenant une mémoire de 8 mots de 8 bits.

Vous avez tous les composants nécessaires. Elle sera d’une taille considérable : 64 bits en tout (8 octets) !Pour vous aider un peu, elle aura les entrées suivantes :

— une entrée d’adresse A.

— un entrée de données DI (pour Data In).

— une entrée de contrôle WE (pour Write Enable) qui permet de décider quand on veut écrire la donnéeprésente sur le bus DI à l’adresse A.

— une entrée reset, pour réinitialiser la mémoire.

— une entrée clk, pour piloter la mise a jour de la mémoire.

Votre mémoire aura aussi une sortie de données DO (pour Data Out) sur laquelle on peut lire la valeurcontenue à l’adresse A.

12

Chapitre 5

Automates

Dans ce chapitre, vous allez construire une implémentation matérielle d’un algorithme, sous la forme d’uncircuit séquentiel complexe avec séparation de la partie contrôle (automate à nombre fini d’états) et de lapartie données (chemin de données). Pour gagner du temps, la partie données du circuit vous est fourniedans le sujet ; votre travail consistera à implémenter l’automate de contrôle, et à exécuter le circuit pas àpas pour bien en comprendre le fonctionnement.

On veut construire un diviseur, c’est à dire, un composant qui calcule le quotient Q de la division entièred’un nombre positif ou nul N par un autre nombre positif P.

1 Sur papier !

1.1 Algorithme

Afin de simplifier l’exercice, on va adopter un algorithme itératif simpliste, qui procède par additionssuccessives en calculant p, p + p, p + p + p, p + p + p + p, et ainsi de suite jusqu’à dépasser N. Quandla somme partielle dépasse N, alors le résultat de la division est le nombre de fois qu’on a pu ajouter p àlui-même.L’algorithme utilise deux variables auxiliaires, x pour la somme partielle, et q pour le quotient partiel. Lorsquex + p dépasse n, alors on a terminé, et q est le résultat recherché.

n := entrée Np := entrée Px := 0q := 0tant que x+p 6 n

x := x+pq := q+1

fin tant quesortie Q := q

1.2 Interface

P Q

go ok

8 8

N8

FIGURE 5.1 – L’interface de notre circuit avec son environnement

13

On suppose que les nombres N et P sont tous les deux positifs, et sont codés en binaire sur 8 bits. Lesignal d’entrée go ordonne au composant de se mettre à travailler, et le signal de sortie ok permet aucomposant de signaler qu’il a terminé son calcul.

1.3 Protocole

Le protocole de communication avec notre diviseur est illustré dans le chronogramme ci-dessous, etexpliqué dans le texte qui suit.

CK

go

Q

ok

temps

N 42

6

t1 t2 t3

P 7

Pour demander une division, le client doit écrire N et P sur les entrées correspondantes, positionner goà 1 et attendre le prochain top d’horloge (instant t1 sur le chronogramme). Le circuit mémorise alors cesentrées dans ses variables n et p, puis il déroule l’algorithme ci-dessus.

Lorsqu’il a terminé son calcul, le circuit positionne sa sortie ok à 1 (instant t2) pour indiquer au clientqu’il peut lire le résultat sur la sortie Q (d’autres valeurs intermédiaires ont peut-être été visibles sur Qentre-temps, mais elles ne sont pas significatives tant que ok n’est pas à 1).

Le circuit garde ok à 1 jusqu’à ce que le signal go soit retombé à zéro. La sortie Q est valide pendant cetemps-là. Lorsque go est de nouveau à zéro (instant t3) le circuit retourne dans son état initial et attendune nouvelle commande. (Bien sûr le circuit ne réagit pas immédiatement lorsque go passe à zéro, maisseulement lors du top d’horloge suivant)

Note : Même si le client ne maintient pas go à 1 pendant tout le calcul, et que go est déjà à zéro au momentde t2, notre circuit garde sa sortie valide pendant au moins un cycle d’horloge. Autrement dit, il y a toujoursau moins un cycle d’écart entre les instants t2 et t3, comme illustré sur le chronogramme ci-dessous :

CK

go

Q

ok

temps

N 10

2

t1 t2 t3

P 4

En résumé, on peut considérer que notre circuit implémente l’algorithme ci-dessous :

14

pour toujours faireattendre que go = 1n := entrée Np := entrée Px := 0q := 0tant que x+p 6 n

x := x+pq := q+1

fin tant que

sortie ok := 1sortie Q := qattendre que go = 0sortie ok := 0

fin tant que

1.4 Chemin de données

Pour construire un tel circuit, on va essayer de séparer proprement le contrôle des données, comme sur leschéma page suivante. La partie données vous est fournie : des registres pour les différentes variables, etdes circuits combinatoires pour les calculs. Attention, tous les registres sont synchrones, comme dans lepoly. Au moment du top d’horloge :

— si reset est vrai, le registre passe à zéro

— sinon, si load est vrai, le registre mémorise la valeur de D

— sinon, il garde sa valeur précédente.

Pour la partie contrôle, ce sera à vous de l’implémenter, mais les signaux de commande (loadN, loadX, ...resetQ) et de compte-rendu (pp) vous sont donnés. À défaut d’un meilleur nom, on appelle pp (pour «pluspetit») le signal transmis par le comparateur à destination de l’automate.

1.5 Automate de contrôle

QUESTION 1 I Proposez, sous la forme d’un diagramme états-transitions, un automate capable de piloterce chemin de données. Il s’agira d’un automate de Moore, donc vous indiquerez :

— sur chaque transition, le symbole d’entrée attendu,

— sur chaque état, le symbole de sortie émis.

QUESTION 2 I Dessinez le circuit correspondant sous formes de trois boites : un registre d’état, une boiteappelée “fonction de transition”, et une boite appelée “fonction de sortie”.C’est là qu’on remarque qu’il y a une entrée reset sur la figure 5.2 qui n’était pas sur la figure 1.2. C’estqu’elle est spéciale : à quoi correspond-elle sur votre dessin de patates ?

QUESTION 3 I Donnez les tables de vérité de la fonction de transition et de la fonction de sortie.

1.6 “Exécution”

QUESTION 4 I Complétez le chronogramme page 18, jusqu’à la fin de la division.

Les premières lignes représentent les données aux entrées et aux sorties du circuit. La ligne verticalepointillée repère le top d’horloge où l’algorithme démarre. Après cet instant, les entrées N et P ne sont plusutiles, leur valeur n’est donc pas importante. Pour le signal go, vous pouvez supposer que le client gardego à 1 jusqu’au bout de l’opération, ou qu’il le remet à zéro plus tôt.

Les lignes suivantes représentent les valeurs des registres du chemin de données. Leur valeur initiale estinconnue (notée « ? » sur le chronogramme).

15

D Q

L

8

registre Q

LoadQ

CK

D Q

L

8

registre P

LoadP

CK

D Q

L

8

registre X

LoadX

CK

D Q

L

8

registre N

LoadN

CK

Contrôle

A

BA6B ?

go

CK

ok

+

+1

8

8

8

8

RResetX

RResetQ

Q

N

P

CK

LoadNLoadXResetXLoadPLoadQResetQ

pp

go ok

reset reset

FIGURE 5.2 – Le circuit du diviseur

16

Les deux lignes suivantes représentent l’état courant de l’automate de contrôle, noté s et l’état suivantcalculé par la fonction de transition, noté s′.

Les dernières lignes représentent les signaux de contrôle de de compte-rendu échangés entre la partiecontrôle et le chemin de données.

17

CK

entréeN

entréePgook

sortieQ

registreN

registreP

registreQ

registreX

LoadN

LoadX

ResetX

LoadP

LoadQ

ResetQ pp

étatcourants

étatsuivants ′

125?????

18

2 En Logisim

Dans cette partie, vous allez réaliser votre diviseur dans Logisim, comme un assemblage de portesélémentaires pour concevoir l’automate, puis d’un assemblage de composants plus gros que vous avezdéjà conçu précédemment, puis le diviseur dans son ensemble.

2.1 Construction de l’automate

On va commencer par construire le circuit implémentant le comportement de l’automate construit à lasection 1.5 en s’attaquant d’abord à la fonction de transition puis à sa fonction de sortie.

2.1.1 Fonction de transition

La fonction de transition prend pour entrée l’état courant s et les signaux go et pp. Elle produit l’état suivants′. Si vous avez construit un automate avec 4 états, s′ est codé sur 2 bits. La fonction de transition a doncdeux bits en sorties, il vous faudra donc construire 2 équations.

QUESTION 5 I A partir des tables de vérités construites à la section 1.5, donner les équations booléennespour s′ en fonction de s.

QUESTION 6 I A partir des équations booléennes, construisez le circuit correspondant.

2.1.2 Fonction de sortie

QUESTION 7 I Procédez de la même façon (équations booléennes puis circuits) pour les sorties de votreautomates, à savoir : loadN, loadP, loadX , resetX , loadQ, resetQ et ok .

2.2 Construction du diviseur

2.2.1 Il manque encore ...

Vous avez maintenant à votre disposition presque tous les composants nécessaires à la construction dudiviseur : votre automate, des registres, des additionneurs. Il vous manque encore un comparateur quivous permettent de réaliser la boite A ≤ B?.

QUESTION 8 I Implémentez ce comparateur.

2.2.2 “Et Voilà”

Il n’y a plus qu’à assembler tout ce beau monde pour reproduire à l’identique la figure 5.2. C’est tellementgratifiant de voir son diviseur fonctionner :)

2.3 Simulez et corrigez votre chronogramme si besoin

19

Chapitre 6

Un embryon de machine de von Neumann

Dans ce TP vous allez construire en logisim un petit processeur 8-bits : il implémentera le modèle de vonNeumann avec un nombre très réduit d’instructions. On suivra la même démarche que pour le diviseur duchapitre précédent.En principe on ne vous demande dans cette partie que des choses que vous avez faites pour le TP sur lediviseur, mais en plus simple.

1 Le modèle de von Neumann : processeur et mémoire

QUESTION 1 I Retrouvez le dessin du modèle de von Neumann dans les transparents du cours. Redonnezla définition du cycle de von Neumann.

On vous fournit (sur Moodle) un composant “CPU” qui n’est pas fini.

QUESTION 2 I Posez à côté une mémoire ROM dimensionnée comme il faut. Les premières cases decette ROM devront contenir les valeurs 00 7F 05 00 00 00 7F 01 00. Reliez-la au CPU.

A ce stade, le circuit que vous avez construit n’est pas fonctionnel car on a largement saboté le CPU, mêmepour une fonctionnalité minimale. Ouvrez-le.Notez la présence de deux registres qui nous intéresseront particulièrement :

— PC qui contiendra, à chaque instant, l’adresse d’une instruction à traiter.

— IR qui contiendra, à chaque instant, l’instruction en cours de traitement.

QUESTION 3 I Complétez ce circuit pour que le CPU lise l’instruction rangée à l’adresse mémoire donnéepar le PC, et la range dans IR.

2 Un processeur qui parcourt la mémoire

Le processeur contient donc deux registres internes de 8 bits, PC et IR, avec PC initialisé à 0. Le cycle devon Neumann que nous allons implémenter consiste à :

1. recopier dans IR le contenu de la case mémoire d’adresse PC, et ajouter 1 au PC

2. interpréter IR comme une instruction, puis exécuter celle-ci

3. recommencer

QUESTION 4 I Complétez le CPU pour qu’il implémente l’étape 1 du cycle de von Neumann (et l’étape 3bien sûr).

QUESTION 5 I Dessinez le diagramme état-transitions de l’automate ainsi obtenu. Il est très très simple.

Pour le moment, notre processeur sait pas passer à l’étape 2. Pour cela, il va nous falloir un automate unpeu moins simple. C’est ce que vous allez faire dans les questions suivantes, en partant de l’implémentationà trous qui vous est fournie. Ouvrez le circuit FSM et constatez qu’il implémente exactement l’automate dela question précédente.

20

QUESTION 6 I Modifiez votre CPU pour qu’il soit commandé par cet automate de contrôle.

Reprenez maintenant les transparents du cours “Towards Von Neuman” à la page 25 “Executing programs -The Von Neuman Cycle - 2”. Vous êtes en train d’implémenter un automate comparable à celui présentédans ce transparent. Dans les questions qui suivent vous allez petit à petit vous rapprocher de celui-ci.

QUESTION 7 I Dessinez un diagramme états-transitions à deux états qui implémente le cycle entier.Attention pour l’instant on ne fait toujours rien à l’étape 2, mais on va quand même la prévoir dansl’automate de commande.Placez les signaux loadIR et loadPC sur votre diagramme, et faites valider par un enseignant.

QUESTION 8 I Implémentez cet automate dans votre FSM.Contrairement à ce que vous avez fait dans le TP précédent sur le diviseur, on vous encourage ici à choisirpour les états un codage 1-parmi-n (aussi connu comme “patate chaude” ou one-hot encoding : chaqueétat est encodé par un bit. voir https://en.wikipedia.org/wiki/One-hot). Cela vous facilitera la tâchepour implémenter la fonction de transition et la fonction de sortie, et surtout cela vous permettra de faireévoluer votre machine sans tout casser à chaque fois...

3 Les branchements

On va maintenant commencer à s’intéresser à la seconde étape du cycle, avec pour le moment une seule ins-truction possible, le saut inconditionnel (aussi appelé goto, branch, ou jump). Cette instruction sera codéesur deux octets 7F XY où XY est l’adresse de destination du saut.

Autrement dit, à l’étape 2 (decode), on va maintenant tester si l’instruction courante est 7F, puis :

— si c’est le cas, alors on va lire le contenu de la case mémoire qui suit immédiatement l’octet 7F (i.e. lacase mémoire d’adresse PC puisque PC a déjà été incrémenté à l’étape 1) et on range ce contenudans PC.

— dans tous les autres cas, on ne fait rien (puisque pour le moment nous n’avons qu’une seuleinstruction).

Par exemple, si les premières cases de la mémoire contiennent les valeurs 00 7F 05 00 00 00 7F 01 00 ...alors le registre PC va passer successivement par les valeurs 0, 1, 2, 5, 6, 7, 1, 2, 5, 6 ...

QUESTION 9 I Avant de passer à la suite, vérifiez que vous comprenez l’exemple ci-dessus.

QUESTION 10 I En vous inspirant des transparents de cours, faites une nouvelle version de votre dia-gramme état-transitions, avec maintenant un état supplémentaire «executeBranch». Faites valider parun enseignant, puis implémentez ces modifications (vous aurez à changer FSM et CPU) et testez votreprocesseur sur le programme d’exemple.

Vous allez maintenant rajouter une seconde instruction : le saut relatif (relative jump). Au lieu de donnerl’adresse de destination de façon absolue, cette instruction indique la distance relative entre l’emplacementcourant et la destination souhaitée. Un saut relatif sera codé sur un seul octet de la forme 1xxN NNNN oùles cinq bits de poids faible (les NNNNN) indiquent la distance relative (offset) en complément à deux.

Autrement dit, si le bit 7 du mot d’instruction vaut 1, alors il vous faudra : extraire l’offset du mot d’instruction,étendre son signe pour obtenir une valeur en complément à 2 sur 8 bits, et enfin ajouter cette valeur au PC.

Pour des raisons de simplicité, on va considérer que l’offset s’interprète relativement à la case qui suitimmédiatement l’instruction de saut et non pas à l’instruction de saut elle-même. Ainsi, l’instruction 80 estun NOP et non pas une boucle infinie.

QUESTION 11 I Avant de passer à la suite, vérifiez que vous avez compris la spécification en exécutant,sur papier, le programme suivant : 80 86 00 00 00 00 00 00 98 00 ...

QUESTION 12 I Modifiez votre automate, puis rajoutez dans votre processeur le support de cette nouvelleinstruction.

21