calcolatori elettronicicalcunibs.altervista.org/calcolatori-elettronici... · •le macchine...
TRANSCRIPT
1
Calcolatori Elettronici
RETI LOGICHE:RETI SEQUENZIALI
Massimiliano Giacomin
2
• Nelle reti combinatorie le uscite dipendono solo dall’ingressoÞ impossibile far dipendere l’uscita dalla “storia” del sistema
(esempio: sistemi interattivi)
• Le reti combinatorie sono senza retroazione Þ impossibile “riutilizzare” un elemento funzionale
(esempio: l’operazione di moltiplicazione tra due interi)Þ per realizzare funzioni complesse sarebbe necessario
usare reti con un numero molto elevato di porte
LIMITI DELLE RETI COMBINATORIE
- Si introducono elementi di memoriache memorizzano lo stato del sistema
- Reti con elementi di memoria (o di stato): dette sequenziali
3
Il “passo base”: memoria-rete_combinatoria-memoria
MEM MEMCOMB COMB MEM
Es: MEMC.LE
Es: IR
…
…
• Necessità di un sincronismo: diventa cruciale controllare istanti incui valori in ingresso a elementi di memoria vengono memorizzati
Si utilizza un circuito in grado di generare un segnale di clock (clock pulse generator)
4
• Segnale che evolve con un periodo (tempo di ciclo) predeterminato e costante (intervallo di tempo fra 2 segnali di clock consecutivi)
• La frequenza di clock è l’inverso del periodo (numero di cicli di clock al secondo)
• Esempio: periodo 25 ns, frequenza 40 MHz
T1 T2 T3
clock
1 nsec 25 nsec
Il segnale di clock
5
Reti sincrone e metodologie di temporizzazione
• Il segnale di clock è collegato agli elementi di memoria edetermina quando gli elementi cambiano stato
• Esistono due metodologie di temporizzazione (approccio per determinare quando gli elementi di memoria cambiano stato)
- sensibile ai livelli- sensibile ai fronti
Il ruolo del segnale di clock è sincronizzare la rete: le reti che lo utilizzano sono dette sincrone
COME?
6
Limiti della temporizzazione sensibile ai livelli
MEM MEMCOMB COMB MEM
Es: MEMC.LE
Es: IR
…
CK
• Durante il livello attivo, tutti gli elementi di memoria sono “trasparenti”
• Il valore memorizzato in un elemento di memoria alla fine del(livello attivo del) ciclo di clock non è determinato – dipendedalla durata del livello attivo
7
Periodo (ciclo) di clock
Fronte di salita
Fronte di discesa
In questa metodologia uno dei due fronti è detto attivo e causa le variazioni di stato: si usano elementi di memoria, detti flip-flop, il cui contenuto può cambiare solo in corrispondenza del fronte attivo del clock
Metodologia di temporizzazione sensibile ai fronti
8
FLIP-FLOP DI TIPO D
FFD Q
CK
Comportamento:- al fronte di salita di CK:
FF “memorizza” D, Q=D- in tutti gli altri istanti:
Q = valore memorizzato a prescindere da D
Esempio
D
C
Q
9
Nota sulla simbologia
FFD Q
CK
FF sensibile ai fronti di salita
FFD Q
CK
FF sensibile ai fronti di discesa
FFD Q
CK
NB: nel seguito verranno sempre utilizzati FF sensibili al fronte di salita, per i quali si utilizzerà (talvolta omettendo segnale CK)
10
TEMPO DI SET-UP, DI HOLD, DI PROPAGAZIONE
• Dato che l’ingresso viene “campionato” in corrispondenza del fronteattivo del clock, è facile capire che esso deve essere:- stabile almeno da un intervallo di tempo precedente al fronte (Tsetup)- stabile per almeno un intervallo di tempo successivo al fronte (Thold)
• Inoltre, l’uscita sarà stabile al più dopo un certo tempo di propagazione
Tsetup TholdD
C
Q
Tprop
•Tutti i tempi riferiti al fronte del clock
• In generaleThold < Tprop
• Tsetup, Thold, Tprop caratterizzano il FF (livello circuitale-fisico)
11
ST1 F ST2D Q
CK
D Q
CK
ST1(IN)
CLOCK
ST1(OUT)
ST2(IN)
ST2(OUT)
B
A
F(A)
C
B
F(A)
B
F(B)
A F(A)
D
C
F(B)
F(C)
• Al fronte di clock, un elemento di stato memorizza il valore di ingresso• Nel periodo di clock, un nuovo valore di ingresso viene propagato
dalla parte combinatoria e sarà disponibile al successivo fronte
TEMPORIZZAZIONE SENSIBILE AI FRONTI
• Sistemi sincroni: segnale di clock comune determina aggiornamento elementi di stato
12
FD Q
CK
D
CLOCK
Q
F2(A)
F2(A)
F3(A)
A
A
F(A)
F(A)
F(A)
UN CASO PARTICOLARE
13
ST1 F ST2D Q
CK
D Q
CK
T1prop Tcombinatorio T2setup
• Dopo T1prop + Tcombinatorio, ingresso a ST2 è stabile: anticipo di almeno T2
setup
Tclock ³ T1prop + Tcombinatorio + T2
setup
• Vincolo per rispetto di T2hold : ingresso ST2 permane per almeno T2
hold dopo il fronte
T1prop + Tcombinatorio ³ T2
hold
[verificato automaticamente perché Thold < Tprop ]
TEMPORIZZAZIONE E VINCOLI TEMPORALI
Tcombinatorio
14
ESTENDENDO QUESTE CONSIDERAZIONI AD UNA RETE COMPLESSA…
Occorre considerare il caso peggiore; in particolare il “cammino critico”vincola la lunghezza del periodo di clock e quindi limita la frequenza ottenibile!
Tclock ³ Tprop + Tcammino critico + Tsetup
15
SPECIFICA DI UNA RETE SEQUENZIALE
• Rete sequenziale: l’uscita non dipende solo dagli ingressi, ma tutta la loro sequenza, sintetizzata nello stato corrente- l’insieme dei possibili stati è finito (corrisponde alle possibilicombinazioni di valori degli elementi di memoria interna)
- rete sincrona (rispetto al fronte): durante un ciclo di clock la rete sitrova in un ben preciso stato, transizione di stato alla fine del ciclo
• lo stato futuro dipende dagli ingressi correnti e dallo stato corrente:Þ funzione di transizione: calcolata durante il ciclo di clock
• le uscite dipendono da stato corrente e [eventualmente] ingressi: Þ funzione di uscita: calcolata durante il ciclo di clock
16
• Le macchine (automi) a stati finiti sono descrivibili mediante:I = {i1, i2,…, ip} insieme simboli (combinazioni) di ingressoU = {u1, u2, …, ur} insieme simboli (combinazioni) di uscitaS = {s1, s2, …, sn} insieme degli statid funzione di transizione che specifica il nuovo stato in
base allo stato corrente e all’ingressow funzione di uscita che specifica il valore di uscita in
base allo stato corrente e all’ingresso
ÞAutoma A = <I, U, S, d, w>
Due modelli: Moore vs. Mealy
• Nel modello di Moore le uscite dipendono solo dallo stato corrente,nel modello di Mealy le uscite dipendono anche dagli ingressi
inoltre si distingue s ∈ S stato iniziale
17
Un esempio: macchina sequenziale per controllo di un semaforo
• Ingressi = {AutoNS, AutoEO}00,01,10,11
• Uscite = {LuceVerde} 0,1
RETE SEQ.
AutoNS
LuceVerde
AutoEO
18
Verde / 1 Rosso / 0
10
01
10
11
11
00
01
00
MODELLO DI MOORE
Ingressi: (AutoNS, AutoEO): 1 presente, 0 assenteUscite: (LuceVerde): 1 acceso il verde, 0 acceso il rosso
NB: il “cambio” nel semaforo si ha al successivo ciclo di clock
19
MODELLO DI MEALY EQUIVALENTE
Verde Rosso
10/1
01/1
10/0
11/1
11/0
00/1
01/0
00/0
NB: il “cambio” nel semaforo si ha al successivo ciclo di clock
Ingressi: (AutoNS, AutoEO): 1 presente, 0 assenteUscite: (LuceVerde): 1 acceso il verde, 0 acceso il rosso
20
MODELLO DI MEALY NON EQUIVALENTE
Verde Rosso
10/1
01/0
10/1
11/0
11/1
00/1
01/0
00/0
NB: il “cambio” si ha appena arriva un’auto nell’altra direzione
Ingressi: (AutoNS, AutoEO): 1 presente, 0 assenteUscite: (LuceVerde): 1 acceso il verde, 0 acceso il rosso
21
• Gli automi di Mealy hanno, per ogni arco, un simbolo di entrata e uno di uscita
• Negli automi di Moore l’uscita è invece già codificata nel valore dello stato in cui si trova la macchina, ovvero la funzione di uscita dipende solo da S anziché da I x S
• E’ possibile trasformare una macchina di Mealy in una di Moore e viceversa, solitamente quelle di Moore hanno più stati (ma sono “più veloci” – vedremo quando parleremo del controllo nella CPU)
• In una macchina di Moore l’uscita nello stato iniziale è predeterminata (non dipende dagli ingressi)
MEALY VS MOORE
22
SINTESI DI UNA RETE SEQUENZIALE• E’ sufficiente usare:
- un insieme di flip-flop per rappresentare lo stato corrente- una rete combinatoria per calcolare lo stato futuro- una rete combinatoria per calcolare l’uscita
Elementi di memoria
UsciteIngressi Rete sequenziale
clock
…VEDIAMO COME…
23
Macchina sequenziale di Moore
Stato corrente
Ingressi
UsciteFunzione di uscita
Funzione di stato futuro Stato
futuro
CLOCK
Flip-flop in parallelo(registro)
24
Macchina sequenziale di Mealy
Stato corrente
Ingressi
UsciteFunzione di uscita
Funzione di stato futuro Stato
futuro
CLOCK
Flip-flop in parallelo(registro)
25
PROCEDURA DI SINTESI
1. Specificare la macchina a stati finiti o la tabella degli stati
2. Determinare il numero dei flip-flop necessari (in base al numero degli stati) e definire una codifica per gli stati (valori da memorizzare nei flip-flop)
3. Derivare la tabella delle transizioni e delle uscite
4. Ricavare le formule per le variabili di stato (a seconda del tipo di flip-flop scelto)
5. Ricavare le formule per le variabili di uscita
6. Realizzazione circuitale per il blocco combinatorio
26
ESEMPIO DEL SEMAFORO (CON MOORE)
Codifica degli stati
y
Verde 0
Rosso 12 stati: sufficiente 1 FF
NB: se uso FF D, l’ingresso D coincide con lo stato futuro y
27
Stato presente
Ingressi Stato futuro
y AutoNS AutoEO y' 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0
Stato presente
Uscite
y LuceVerde 0 1 1 0
luceVerde = y
Funzione di stato futuro Funzione di uscita
Tabelle di transizione e delle uscite + formule
y' = yAutoNSAutoEO + yAutoNSAutoEO + yAutoNSAutoEO + yAutoNSAutoEO
= yAutoEO + yAutoNS
28
clock
AutoNS
y'
yFF
LuceVerdeAutoEO
Realizzazione circuitale
29
Stato presente
Ingressi Stato futuro
Uscite
y AutoNS AutoEO y' LuceVerde 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1
y' = yAutoNSAutoEO + yAutoNSAutoEO + yAutoNSAutoEO + yAutoNSAutoEO = yAutoNS + yAutoEO
LuceVerde = y'
Tabelle di transizione e delle uscite + formule
ESEMPIO DEL SEMAFORO CON MEALY 2
[stessa codifica stati rispetto ad automa di Moore]
30
clock
AutoNS
y'
yFF
LuceVerde
AutoEO
Realizzazione circuitale
31
• Occorre fare 2 tabelle di verità:
– una tabella rappresenta la funzione di stato futuro (o di transizione),
dove lo stato futuro è funzione degli ingressi e dello stato presente
– l’altra tabella rappresenta la funzione di uscita, dove l’uscita è funzione
solo dello stato presente (Moore) oppure degli ingressi e dello stato
presente (Mealy)
• Nella macchina sequenziale la logica combinatoria può essere divisa in 2
parti: la prima determina le uscite e la seconda determina lo stato futuro
RICAPITOLANDO
32
TEMPORIZZAZIONE
Logica combinatoria:Funzione
di stato futuro δ
Reg. di stato
Ingressi
Logica combinatoria:Funzione di uscita ω
Uscite
Solo mod.Mealy
clock
1 (percorso transiz stato)
2 (percorso uscita)
Tclock
Tprop Tcomb(δ) Tsetup
33
Logica combinatoria:Funzione
di stato futuro δ
Reg. di stato
Ingressi
Logica combinatoria:Funzione di uscita ω
Uscite
Solo mod.Mealy
clock
1 (percorso transiz stato)
2 (percorso uscita)
Tclock
Tprop Tcomb(ω)
34
Logica combinatoria:Funzione
di stato futuro δ
Reg. di stato
Ingressi
Logica combinatoria:Funzione di uscita ω
Uscite
Solo mod.Mealy
clock
1 (percorso transiz stato)
2 (percorso uscita)
Tclock
Tprop Tcomb(ω)
MEALY vs MOOREMEALY:
- Risente degli ingressi- Stabilità in funzione di stabilità ingressi
MOORE:- vantaggio in termini di velocità(se le uscite devono essere disponibili il piùpresto possibile: cfr. unità di controllo processore multiciclo)