L 9 – 1/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Architettura degli Elaboratori e delle Reti
Lezione 9
Flip-flop, registri,
la macchina a stati finiti
Proff. A. Borghese, F. Pedersini
Dipartimento di Scienze dell’Informazione
Università degli Studi di Milano
L 9 – 2/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Sommario
!Bistabili DT edge- sensitive: Flip-Flop
!Registri e Register-File
!Circuiti sequenziali (macchine a stati finiti)
L 9 – 3/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Sincronizzazione
! I “cancelli” devono disaccoppiare i diversi sottosistemi logici
" “raccogliere” i segnali, senza farli passare, e “rilanciarli” ad un determinatoistante
" Cancello doppio: ingresso e uscita
" Mai aperti contemporaneamente
L 9 – 4/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
! I latch sono dispositivi trasparenti:
" Per tutto il tempo in cui il clock è attivo (alto), il valore di D vieneriportato in uscita:
Q = D : uscita collegata all’ingresso
! A noi interessa memorizzare l’informazione in undeterminato istante
Latch: Bistabili level-sensitive
!
"#$
%
%
if CLK = 1
then Q*=D
else Q*=Q
L 9 – 5/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Problemi con i latch sincroni
! Registro a scorrimento (shift register)
" Un unico ingresso I e un’unica uscita U
" In presenza di segnale attivo (clock alto), il contenuto deve esserespostato verso destra di una posizione
! Realizzazione mediante bistabili LATCH:
" Funziona?
I = D2
CLK
Q2 = D1
Q Q Q
Q1 = D0Q0 = U
L 9 – 6/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Shift register con i latch
I = D2
CLK
Q2 = D1
Q Q Q
Q1 = D0Q0 = U
&
"#$
%'
%(
%)* +, !t !t !t
L 9 – 7/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Flip-Flop – tipo DT
Bistabili “edge sensitive”: i Flip-Flop
! Dispositivi attivi sul fronte del clock (edge sensitive):
" il loro stato (uscita) può commutare solo in corrispondenza del
fronte di salita o di discesa del clock.
Bistabile tipo DT – Configurazione “Master-Slave”
D
CLK
Qmaster = Dslave
Qmaster Q
QDmaster Qslave
L 9 – 8/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Flip-flop: struttura master–slave
! -#&.: L’ingresso D viene memorizzato nel latch MASTER
" L’uscita è bloccata
! -#/.: l’uscita stabile del latch MASTER viene propagato al latchSLAVE
" L’ingresso è bloccato, l’uscita è stabile.
D
CLK Qm= Ds
Qm= Ds
Q
Q
CLK
Dm
Dm
L 9 – 9/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Funzionamento: FLIP
D
CLK = 1Qm= Ds
Qm= Ds
Q
Q
CLK
Dm
Dm
Flip
CLK
D
Qm
CLK•D
Qm
t
L 9 – 10/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Funzionamento: FLOP
D
CLK = 0Qm= Ds
Qm= Ds
Q
Q
CLK
Dm
Dm
Flop
CLK
Qm
Q
CLK•Qm
Q
t
L 9 – 11/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Funzionamento dei Flip-Flop
! Fronte di SALITA – FLIP
" Attivato lo stadio MASTER
" Memorizzato il dato sull’ingresso: D ! STATO
" Uscita invariata
Cancello ingresso aperto, cancello uscita chiuso
! Fronte di DISCESA – FLOP
" Attivato stadio SLAVE
" Presenta il dato memorizzato in uscita: STATO ! Q
" Ingresso isolato
Cancello ingresso chiuso, cancello uscita aperto
L 9 – 12/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Struttura di un circuito sequenziale
Cancello ! Circuito combinatorio ! Cancello
! Sincronizzazione: la logica combinatoria deve terminare lapropria commutazione in tempo utile
Logica
combinatoriaD Qflip-flop
T
D Qflip-flop
T
"#$
&0 Out
L 9 – 13/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Temporizzazione circuito sequenziale
! Il clock arriva contemporaneamente a tutti i dispositivisincronizzati
! Dimensionamento del periodo di clock:
" la commutazione del clock deve avvenire dopo che la logicacombinatoria ha terminato tutte le commutazioni
" Il tempo necessario alla logica combinatoria per commutare dipendedal cammino critico
Logicacombinatoria
D Q
flip-flop
T
D Q
flip-flop
T
CLK
In Out
L 9 – 14/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Temporizzazione: problemi
! Tempo di set-up: è il tempo minimo per cui deve rimanere stabilel’input D prima del fronte di clock.
! Tempo di hold: è il tempo minimo per cui deve rimanere stabilel’input D dopo il fronte di clock (solitamente trascurabile).
Logicacombinatoria
D Q
flip-flop
T
D Q
flip-flop
T
CLK
In Out
t
Tempo di holdTempo di set-up
+!
+"#$
tsetup thold
L 9 – 15/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Dimensionamento del periodo di Clock
! Tempo di propagazione: è il tempo necessario per propagare il segnale dall’uscitaslave alla logica combinatoria: tp
" maggiore del tempo di hold: th
! Tempo di skew: ritardo massimo del clock tw
Tclock > k * (tp+ tc + ts+ tw)
Logicacombinatoria
D Q
flip-flop
T
D Q
flip-flop
T
CLK
In Out
t
Tempo di propagazione: tp > th
Tempo di set-up
+!
+"#$
tsetup thold
L 9 – 16/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Sommario
! I bistabili DT edge-sensitive: Flip-Flop
! I registri ed il register file
!Circuiti sequenziali (macchine a stati finiti)
L 9 – 17/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Registri
! Registro a N bit # N Flip-flop DT
SCRITTURA:
" L’impulso di CLK memorizza i dati sugli ingressi D
LETTURA:
" I dati memorizzati sono presenti sulle uscite Q
L 9 – 18/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Register file (CPU MIPS)
! Register File: famiglia di CPU “MIPS”:
" 32 registri da 32 bit
" 1 linea di ingresso
" 2 linee di uscita
#Reg read 1
#Reg read 2 Contenuto 1
Contenuto 2
#Reg write
Contenuto
Write
W
Register File MIPS:
32 registri da 32 bit
32
32
32
5
5
5
1
L 9 – 19/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Register File
! Banco di registri: 2k registri da n bit ciascuno
" Utilizzabile come memoria per i dati
! SELEZIONE: fornendo in ingresso il numero del registro (#reg)
! LETTURA: non modifica il contenuto del registro selezionato
! SCRITTURA: Inserisce <ContenutoWrite> nel registro selezionato
" Comando: segnale W
#Reg read 1
#Reg read 2 Contenuto 1
Contenuto 2
#Reg write
Contenuto
Write
W
Register File:
2k registri da n bit
n
n
n
k
k
k
L 9 – 20/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Register File MIPS: Porta di LETTURA
5
5
32
! 2 MUX di selezione registro
" 2 registri possono essere letti contemporaneamente
L 9 – 21/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Register file MIPS: Porta di SCRITTURA
! Ingresso CLK: (Selezione) AND W
" Se no ad ogni CLK scriverei nei registri
! Ingresso D:
" Dato (32 bit)W
#Reg Write
Dato32
5
L 9 – 22/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Sommario
! I bistabili DT edge-sensitive: Flip-Flop
! I registri ed il register file
!Circuiti sequenziali (macchine a stati finiti)
L 9 – 23/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Macchine sequenziali
! Macchina combinatoria: U = f ( I )
" senza memoria, uscita dipende solo dagli ingressi
! Macchina sequenziale: X* = f ( X, I )U = g( X )
" 2 funzioni: uscita e stato prossimo
" esiste la memoria: lo STATO
UI UI
X
combinatoria sequenziale
L 9 – 24/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Macchine sequenziali
! Elemento necessario di ogni macchina sequenziale è la retroazione
" Uscita riportata in ingresso
" Bistabile: (macchina sequenziale elem.): 2 porte NOR +retroazione
1
2
%
%
! Macchina sequenziale sincrona
" Impiega bistabili sincroni
" Es: Flip-Flop tipo DT!
3
%
& ,
"#$
rete
combinatoria
macchina sequenziale
retroazione
L 9 – 25/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
La macchina sequenziale di Huffman
14546
ioi1iM
yo
y1
yN!‘ x*1
xK
x1
x*K
&07 89::;,:<;49
14546+=86::;> 6
L 9 – 26/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Macchina a Stati Finiti - di Moore
! Una Macchina a Stati Finiti (MSF) è definita dalla quintupla:
< X, I, Y, f(·), g(·) >
X: insieme degli stati (in numero finito).
I: alfabeto di ingresso: l’insieme dei simboli che si possono presentare in ingresso.Con n ingressi, avremo 2n possibili configurazioni.
Y: alfabeto di uscita: l’insieme dei simboli che si possono generare in uscita. Conm uscite, avremo 2m possibili configurazioni
f(·): funzione stato prossimo: X* = f( X , I )Definisce l’evoluzione della macchina nel tempo, in modo deterministico
g(·): funzione di uscita: Y= g( X ) (macchina di Moore)
Y= g( X , I ) (macchina di Mealy)
" Per il buon funzionamento della macchina è previsto uno stato iniziale, alquale la macchina può essere portata mediante un comando di reset.
L 9 – 27/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Macchina di Moore: STT
! STT: State Transition Table(Tabella delle transizioni di stato)
" Per ogni coppia: <stato attuale, ingresso> definisco uscita y e stato prossimo x*
(xi?+X , ij?+I) # y(xi) ; x*( xi, ij )
! Esempio: M stati (log2M bit di stato), N ingressi (log2M bit d’ingresso):
y(xM)x*(xM,iN)x*(xM,i2)x*(xM,i1)xM
……
y(x2)x*(x2,iN)x*(x2,i2)x*(x2,i1)x2
y(x1)x*(x1,iN)x*(x1,i2)x*(x1,i1)x1
YiN…i2i1
L 9 – 28/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Macchina di Moore: STG
! STG: State Transition Graph(Diagramma degli Stati o Grafo delle transizioni)
" Ad ogni nodo è associato uno stato: xi ? X
" Ed un valore della funzione d’uscita: yi ? Y, yi=g(xi)
" Un arco orientato da uno stato xi ad uno stato xj, contrassegnato da un
simbolo (di ingresso) iK, rappresenta una transizione che si verifica quando
la macchina, essendo nello stato xi, riceve come ingresso iK
xI ? X xJ ? X
iK ? I
yI = g(xI) yJ = g(xJ)xJ = f(xI,iK)
L 9 – 29/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Controllore di un semaforo
SEMAFORO:
! Incrocio tra 2 strade: nord-sud (NS) ed est-ovest (EO) controllate da
un semaforo (per semplicità consideriamo solamente rosso e verde)
! Il semaforo può commutare ogni 30 secondi
" Macchina sincrona, clock con frequenza = ?
! E’ presente un sensore in grado di “leggere”, per ogni direttrice, se esiste almeno
un’auto in attesa, oppure un’auto che si accinga ad attraversare (condizioni trattate
allo stesso modo).
! Il semaforo deve cambiare colore (da rosso a verde) quando esiste un’auto in
attesa sulla sua direttrice.
! Se ci sono auto in attesa sulle entrambe le direttrici il semaforo deve cambiare
colore (al termine del tempo di commutazione)
L 9 – 30/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
SEMAFORO: Stato, Ingresso, Uscita
STATO
" Semaforo NS VERDE, semaforo EO ROSSO
" Semaforo NS ROSSO, semaforo EO VERDE
! 1 bit di STATO (1 flip-flop)
INGRESSI
" Auto NS presente / non presente
• AutoNS=1/0
" Auto EO presente / non presente
• AutoEO = 1/0
! 2 bit di INGRESSO ! 4 configurazioni d’ingresso
USCITE: = STATO
" LuceEO verde (LuceNS rossa)
" LuceNS verde (LuceEO rossa)
! 2 configurazioni d’uscita ! 1 bit di USCITA
auto NSsì / no
auto EOsì / no
L 9 – 31/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Funzionamento: stato prossimo
! Per ogni valore dello stato dobbiamo prevedernel’evoluzione in funzione degli ingressi
X(t+1) = X* = f( X(t), I )
! Stato: X(t) = X = {VerdeNS, VerdeEO}
! X(t+1) = X* = “VerdeNS”
" Se X(t)=“VerdeNS” AND non ci sono auto sulla direttrice EO
" Se X(t)=“VerdeEO” AND ci sono auto sulla direttrice NS
! X(t+1) = X* = “VerdeEO”
" Se X(t)=“VerdeEO” AND non ci sono auto sulla direttrice NS
" Se X(t)=“VerdeNS” AND ci sono auto sulla direttrice EO
L 9 – 32/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
Funzionamento: uscita
!Per ogni stato, definire l’uscita della macchina
!Uscita " STATO
" VerdeNS ! Verde sulla direttrice NS, rosso sulladirettrice EO
" VerdeEO ! Verde sulla direttrice EO, rosso sulladirettrice NS
!Luce Verde NS = VerdeNS
!Luce Verde EO = VerdeEO
L 9 – 33/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
! Stato prossimo: X* = f(X, I)
Per ogni variabile di stato, calcolare l’evoluzione in funzione degliingressi:
" Se X = “VerdeNS” e AutoEO=“0”
" Se X = “VerdeEO” e AutoNS=“1”
" Se X = “VerdeEO” e AutoNS=“0”
" Se X = “VerdeNS” e AutoEO=“1”
VerdeNS = VerdeNS · ~autoEO + VerdeEO · autoNS
VerdeEO = VerdeEO · ~autoNS + VerdeNS · autoEO
! Uscita: Y = g(X)
Per ogni stato, definire l’uscita della macchina:
" X = “VerdeNS” ↔ Y = “Luce Verde NS”
" X = “VerdeEO” ↔ Y = “Luce Verde EO”
Sintesi funzioni: stato prossimo e uscita
$ X* = “VerdeNS”
$ X* = “VerdeEO”
L 9 – 34/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
STG del semaforo
! Funzione stato prossimo:
VerdeNS* = VerdeNS · ~autoEO + VerdeEO · autoNSVerdeEO* = VerdeEO · ~autoNS + VerdeNS · autoEO
! Funzione uscita:
Y = X
AutoEO = 1
AutoNS = 1
AutoEO = 0AutoNS = 0
VerdeEO VerdeNS
LuceVerdeNS
LuceVerdeEO
L 9 – 35/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
STT del semaforo
Luce
VerdeEOVerdeNSVerdeEOVerdeNSVerdeEOVerdeEO
LuceVerdeNS
VerdeEOVerdeEOVerdeNSVerdeNSVerdeNS
UscitaautoEOautoNS
autoEO~autoNS
~autoEO autoNS
~autoEO~autoNS
IX
Funzione stato prossimo:X* = f(X, I)
Funzione uscita:Y = g(X)
L 9 – 36/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
STT del semaforo: CODIFICA binaria
! Stato:
" (VerdeNS/RossoEO, RossoNS/VerdeEO) ! (0, 1)
! Ingresso:
" 2 Variabili: AutoNS, AutoEO ! 1 =“presente”, 0 =“assente”
" 4 Configurazioni: (00, 01, 10, 11)
! Uscita:
" (Luce_VerdeNS, Luce_VerdeEO) ! (0, 1)
101011
011000
UscitaY
11100100IX
L 9 – 37/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
! Struttura: macchina diMOORE
" 2 stati (0,1) ! 1 flip-flop
" 2 linee di ingresso
" 1 linea d’uscita
! SINTESI:rete combinatoria
" stato prossimo: f(X,I)
" uscita: g(X)
Sintesi della MSF del semaforo
2 reti
combinatorie:
X* = f (X,I)
Y = g (X’)
I
X X*
clk
!%
3
Yi0
i1
L 9 – 38/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
XY
IXIX
IIXIXIIIXIIXX
=
+=
=+++=
10
11010010*
101011
011000
Y11100100
Sintesi della MSF del semaforo
IX
!Mediante la STT codificata in binario, posso
esprimere X* e Y come somma di prodotti:
" cerco i mintermini:
L 9 – 39/39A.A. 2005/06 Copyright : A. Borghese, F. Pedersini – DSI, UniMI
MSF del semaforo: sintesi del circuito
2 reti
combinatorie:
X* = f (X,I)
Y = g (X’)
I
X X*
clk
!%
3
Yi0
i1
XY
IXIX
IIXIXIIIXIIXX
=
+=
=+++=
10
11010010*
i0
i1
X
X*
Y
rete combinatoria
TCLK = 30 sec