Cours 11

Objectifs
• Connaître
Circuits Logiques
ELE1300
La représentation d’une machine à états
algorithmique
• Être capable de
Construire un circuit équivalent à une petite
machine à états algorithmique.
Introduction aux ASM
(Algorithmic State Machine)
JP David
Circuits logiques - JP David
2 avril 2014
ASM
2
Algorithme du PGCD
ASM : Acronyme anglais pour Algorithmic State Machine
Exemple d’algorithme : Trouver le plus grand commun diviseur - PGCD
1. Il s’agit de machines à états finis (MÉF/FSM) avancées
2. Les premiers travaux sur les ASM datent des années 1970 et sont dus à HP
PGCD(A, B)
3. Les ASM traduisent un comportement algorithmique représenté par un diagramme
Tant que (B != 0) {
4. Il fréquent de les considérer comme des FSM contrôlant un système numérique
Temp = B;
Manger
Faim ?
B = A%B;
Oui
A = Temp
Non
}
Boire
Oui
2 avril 2014
Circuits logiques - JP David
Soif ?
Retourner A
Non
3
2 avril 2014
Circuits logiques - JP David
4
Algorithme du PGCD
Algorithme du PGCD
Une affectation
N0
B != 0 ?
Un état
0
PGCD(A, B)
Temp = B;
B = A%B;
A = Temp
A
72
B
30
Temp
30
12
30
12
6
6
12
0
6
N1
0
PGCD(72, 30) = 6
Circuits logiques - JP David
2 avril 2014
B!=0
(Result=A)
Rdy=1
}
Retourner A
A:=INA
B:=INB
Rdy=0
Un test
PGCD(72, 30)
Tant que (B != 0) {
Start
1
Result
INA
INB
start
1
B:=A%B
A:=B
Rdy = 0
Rdy
clk
Une opération
5
2 avril 2014
ASM
Circuits logiques - JP David
6
Le circuit
• Chaque rectangle représente un état
Les (éventuelles) opérations se font durant la période
d’horloge pour que les résultats soient disponibles
avant le flanc montant de l’horloge.
À ce moment, un certain nombre d’affectations “:=“
auront lieu, de manière PARALLÈLE. La machine entre
alors dans un nouvel état.
start
INA
Machine à
états
INB
• Chaque losange représente un test
Éléments de
mémorisation
et traitement
Rdy
Result
clk
C’est lui qui permet de déterminer l’état suivant. Le cas
échéant, la machine peut revenir dans le même état.
2 avril 2014
Circuits logiques - JP David
7
2 avril 2014
Circuits logiques - JP David
8
La machine à états
start
Quelles
Sorties ?
Machine à
états
Les éléments de mémorisation
• Un registre A
Din_A[31..0]
N0
32
Ena_A
N0
0
start
t1
1
32
Dout_A[31..0]
• Un registre B
Start
Din_B[31..0]
N1
N1
32
Ena_B
1
0
t1
B!=0
Signal t1
B
32
t1
Circuits logiques - JP David
2 avril 2014
Dout_B[31..0]
9
2 avril 2014
Les éléments de traitement
32
10
Les éléments de “routage”
• Din_A peut prendre ses données depuis :
• Un circuit de calcul du reste
Rin_A[31..0]
Circuits logiques - JP David
Le port d’entrée INA
La sortie du registre B (Dout_B)
Rin_B[31..0]
1 MUX
2 vers 1
32 bits
Sel_A
• Din_B peut prendre ses données depuis :
32
Le port d’entrée INB
La sortie du modulo (Rout)
Modulo
32
• Rin_A peut prendre ses données depuis :
Rout [31..0]
1 MUX
2 vers 1
32 bits
Sel_B
La sortie du registre A (Dout_A)
• Rin_B peut prendre ses données depuis :
La sortie du registre B (Dout_B)
2 avril 2014
Circuits logiques - JP David
11
2 avril 2014
Circuits logiques - JP David
12
Chemin de données
INA
Sel_A
Sel_B
1
0
Tableau de transition et sorties
1
0
Etat P
start
t1
Next
Ena_A
Ena_B
Sel_A
Sel_B
Rdy
N0
0
X
N0
0
0
X
X
0
N0
1
X
N1
1
1
0
0
0
N1
X
0
N0
0
0
X
X
1
N1
X
1
N1
1
1
1
1
0
INB
Din_A[31..0]
Din_B[31..0]
32
Sel_A
32
Ena_A
Ena_B
Sel_B
32
32
Dout_A[31..0]
Rin_A[31..0]
Ena_A
Dout_B[31..0]
Rin_B[31..0]
32
32
Modulo
Ena_B
Result
32
Rout [31..0]
Circuits logiques - JP David
2 avril 2014
13
Circuit final
Rdy
INA
32
32
32
SelB
1
0
32
D
État
Q
SelA
1
DinA[31..0]
32
DinB[31..0]
D
État
32
t1
DinA[31..0]
32
DinB[31..0]
ena
Registre A
Registre B
32
32
RinA[31..0]
RinB[31..0]
DoutB[31..0]
32
32
RinB[31..0]
Modulo
Modulo
32
32
32
32
Rout [31..0]
Circuits logiques - JP David
15
Rout [31..0]
Result
Result
2 avril 2014
1
DoutA[31..0]
DoutB[31..0]
32
Q
32
0
32
ena
32
RinA[31..0]
SelB
1
0
32
start
Registre B
32
32
32
32
ena
Registre A
DoutA[31..0]
t1
32
32
ena
INB
INA
32
0
32
Rdy
INB
INA
INB
INA
start
14
Contrôle – Chemin de données
INB
SelA
Circuits logiques - JP David
2 avril 2014
2 avril 2014
Circuits logiques - JP David
16
Une forme « standard »
Partie de contrôle
• Attendre que l ’on pousse
sur le bouton
• Chauffer l ’eau
• Attendre qu ’elle soit chaude
• Mettre une dose de café
• Ouvrir la vanne d ’eau
• Attendre que la tasse soit
remplie
• Fermer la vanne
• Arrêter le chauffage de
l ’eau
2 avril 2014
Un circuit « standard »
Partie opérative
Partie de contrôle
Chemin de données
Bouton poussoir
Chauffage de l ’eau
Thermomètre
Ajout de café
Vanne
Circuits logiques - JP David
Niveau d ’eau
CLK
17
2 avril 2014
Circuits logiques - JP David
18

Download Report