Teoria del contollo automatico
Circuiti sequenziali – Sistema dinamico
I Circuiti Sequenziali sono circuiti i cui segnali di uscita dipendono non solo dai segnali di ingresso ma anche
dallo stato all’interno del circuito stesso: O = F (I, S). In questi circuiti si introduce il concetto di Stato del
Sistema e di Tempo.
Lo stato del sistema è dato dalla capacità del circuito di memorizzare e preservare un valore, affermato o
negato, che influisce sui segnali di ingresso.
Il tempo acquista valore perché la funzione di uscita dovrà tener conto dello stato del sistema al tempo t e
utilizzarlo per calcolare il proprio stato al tempo t + 1.
Il circuito sequenziale è il circuito base che realizza l’elemento fondamentale dei sistemi dinamici: la
memoria. La sua componente caratteristica è la retroazione: il segnale di uscita rientra come segnale di
ingresso al circuito che lo compone.
Quando a = 1 e b = 0 possiamo supporre l’uscita S = 0.
Quando a = 0 e b = 1 possiamo supporre l’uscita S = 0.
Cosa succede quando sia a che b sono = 0 o 1 ?
Non possiamo saperlo se non prendiamo in considerazione l’uscita S t
nell’istante t in cui applichiamo il segnale a e b.
Quando a = 0 e b = 0 nell’istante t, se S t = 0, l’uscita S t+1 = 0, mentre
se S t = 1, l’uscita S t+1 = 1.
Il valore dell’uscita non cambia e preserva il suo valore quando
manteniamo i segnali di ingresso a 0.
Abbiamo realizzato un circuito di memoria.
Circuito RS
Il circuito sequenziale RS , Reset and Set, realizza un circuito di memoria e ha la caratteristica di avere due
ingressi, uno per affermare l’uscita Q, l’altro per negarla. Gli altri valori di ingresso lasciano inalterato il valore
dell’uscita Q. la combinazione di ingressi R = 1 e S = 1 non viene applicata.
1
Circuito Bistabile Asincrono Trasparente - BAT – detto LATCH D
Questo circuito è composto da un circuito sequenziale RS con gli ingressi R e S pilotati da un bit di dato D e
abilitati da un segnale di controllo C.
Circuito Sequenziale Flip-Flop
Questo circuito è composto da due LatchD in cascata, pilotati da un segnale di controllo C. Il cambiamento
del segnale di uscita Q avverrà solo in presenza del fronte di discesa del segnale di controllo, realizzando
così un dispositivo sincronizzato.
E’ il componente fondamentale di ogni calcolatore col quale si realizzano per esempio i registri della CPU.
2
Automi a stati finiti
Definizione di automa a stati finiti
Un automa a stati finiti è un dispositivo ideale definito da:
•
un insieme S = {S1, S2, …, S k} di stati interni
•
uno stato iniziale S i ∈ S
•
un insieme X = {X1, X2, …, X p} degli stati di ingresso, ovvero delle combinazioni di segnali applicati
dall’esterno
•
un insieme Z = {Z1, Z2, …, Z q} degli stati di uscita, ovvero delle combinazioni dei segnali in uscita
•
una funzione Z = F ( X, S ) che rappresenta la dinamica del sistema, ovvero calcola il prossimo stato in
funzione degli ingressi applicati e dello stato del dispositivo.
Un automa a stati finiti ci permette di descrivere un qualunque problema che evolva in tempi discreti e si
possa trovare in un numero finito di stati diversi.
Per consentire stabilità nel passaggio da uno stato all’altro nel momento di applicazione dei segnali di
ingresso, i nostri dispositivi memorizzeranno gli stati interni in circuiti sequenziali di tipo RS, LatchD o FlipFlop.
Diagramma degli stati
Per mostrare i diagrammi degli stati useremo dei grafi orientati composti da nodi, gli stati del dispositivo, da
cui partono degli archi orientati, le transizioni di stato, su ognuno dei quali è indicato lo stato degli ingressi
che generano la transizione e lo stato delle uscite dopo la transizione.
3
Progettare un automa che riconosca tutte le stringhe binarie che terminano con 3 bit a 1.
Il seguente diagramma mostra l’automa a stati finiti che realizza il dispositivo che riconosce le stringhe
binarie che terminano con 3 bit a 1.
Questo circuito ha quattro stati, quindi potrà essere realizzato utilizzando 2 bistabili: Log 2 S n.
Tabella della verità di questo automa a stati finiti, riduzione algebrica e circuito che lo implementa.
U1
U2
I
D1
D2
Si
0
0
0
0
0
S0
D1 = I U1 U2 + I U1 U2 + I U1 U2
0
0
1
0
1
S1
D1 = I U1 U2 + I U1 ( U2 + U2 )
0
1
0
0
0
S0
D1 = I U1 U2 + I U1
0
1
1
1
0
S2
1
0
0
0
0
S0
D2 = I U1 U2 + I U1 U2 + I U1 U2
1
0
1
1
1
S3
D2 = I U1 U2 + I U1 ( U2 + U2 )
1
1
0
0
0
S0
D2 = I U1 U2 + I U1
1
1
1
1
1
S3
4
Progettare un bistabile di tipo J K.
Il Bistabile JK è un circuito sequenziale che si comporta come descritto nella seguente tabella di verità.
Per realizzare questo bistabile utilizzeremo come circuito per memorizzare lo stato dell’automa il circuito
sequenziale RS.
J
K
Qt
Q t+1
R
S
Si
0
0
0
0
0
0
S0
R=JKQt+JKQt
0
0
1
1
0
0
S1
R=JQt(K+K)
0
1
0
1
0
1
S1
R=JQt
0
1
1
1
0
0
S1
1
0
0
0
0
0
S0
S=JKQt+JKQt
1
0
1
0
1
0
S0
S=KQt(J+J)
1
1
0
1
0
1
S1
S=KQt
1
1
1
0
1
0
S0
Il diagramma a stati che rappresenta il bistabile JK è il seguente:
Questo circuito ha due stati distinti, quindi potrà essere realizzato utilizzando un solo bistabile: Log 2 2.
5
Caratteristiche generali di una CPU
In generale le CPU hanno i seguenti componenti di base:
•
il Program Counter
è il registro che contiene l’indirizzo di memoria della prossima istruzione da eseguire.
•
L’Istruction Register
è il registro che contiene l’istruzione da eseguire letta dalla memoria
•
l’Accumulatore
è il registro da dove passano tutte le operazioni della CPU
Modelli architetturali di CPU
Ci sono modelli differenti di progettazione delle CPU.
Modello orientato all’accumulatore
Cicli di clock
Istruzione assembler
Descrizione
1+1
Load C
Carica il dato all’indirizzo C nell’accumulatore
1+1
Add B
Somma il dato all’indirizzo B all’accumulatore (C)
1+1
Store A
Memorizza la somma all’indirizzo A
Le istruzioni passano sempre per l’accumulatore.
Modello orientato alla memoria
Cicli di clock
Istruzione assembler
Descrizione
4+?
Add A, B, C
Somma i dati contenuti agli indirizzi B e C e lo memorizza
all’indirizzo A
Questo è l’approccio seguito dai processori CISC. Le istruzioni sono più potenti ma hanno più accessi alla
memoria.
Modello orientato allo stack
Cicli di clock
Istruzione assembler
Descrizione
1+1
Push B
Carica dall’indirizzo B il dato e lo pone sullo stack
1+1
Push C
Carica dall’indirizzo C il dato e lo pone sullo stack
1+1
Add
Somma i due dati contenuti sulla cima dello stack
1+1
Pop A
Muove all’indirizzo A la cima dello stack contenente la
somma B + C
Questo è l’approccio seguito dai processori CISC. Le istruzioni sono più potenti ma hanno più accessi alla
memoria.
6
Modello orientato ai registri
Cicli di clock
Istruzione assembler
Descrizione
1+1
Load R1, C
Carica il registro R1 con il dato contenuto all’indirizzo C
1+1
Load R2, B
Carica il registro R2 con il dato contenuto all’indirizzo B
1
Add R3, R1, R2
Somma i valori contenuti nei due registri R1 e R2 e lo pone
nel registro R3
1+1
Store R3, A
Copia il valore contenuto in R3 all’indirizzo A
Questo è l’approccio seguito dai processori RISC. Le istruzioni sono lunghe tutte una parola (32 bit), si fa
uso massivo dei registri e le modalità di accesso alla memoria sono estremamente limitate.
Una caratteristica importante delle CPU RISC è che sono più semplici e quindi più piccole di CPU CISC.
Per capire meglio la differenza tra un processore CISC e un processore RISC possiamo vedere questo
esempio: a = b + c + d + e
Processore CISC
Processore RISC
Add Temp, d, e
Load R1, b
Add Temp, Temp, c
Load R2, c
Add a, Temp, b
Load R3, d
Load R4, e
Add R5, R4, R3
Add R5, R5, R2
Add R5, R5, R1
Store R5, a
Le CPU di tipo CISC, data la loro complessità, contengono dei veri e propri microprogrammi per la
realizzazione delle proprie istruzioni, secondo l’intuizione di Morris Wilkes.
7
Elementi di Aritmetica Binaria
La numerazione naturale binaria e la notazione binaria in complemento a due.
La numerazione naturale binaria con n bit rappresenta numeri da 0 a 2
n
– 1.
La notazione binaria in complemento a due con n bit rappresenta numeri da: - 2
Se a = – 2
n–1
eb=2
n-1
Numero
Binario
Numero in
Decimale
011
3
010
2
001
1
000
0
111
-1
110
-2
101
-3
100
-4
– 1 allora b – a + 1 = 2
n-1
–1+2
n-1
+1=2*2
n-1
n–1
a+2
n-1
– 1.
n
=2 .
Note
01xxx = Numero Massimo
1* = Tutti 1 = -1
10* = Numero Minimo
Se N è uguale ad un numero binario di 4 bit: b3 b2 b1 b0 qual è il numero – N ?
Osserviamo che: N + (– N ) = 0 e in binario una stringa di bit: b3 b2 b1 b0 +⎯b3⎯b2⎯b1⎯b0 + 1 = 0.
Infatti la somma bit a bit: ( bx +⎯bx ) è una stringa di bit ad 1 che in notazione complemento due rappresenta
il numero decimale –1, che sommato ad 1 da sempre 0.
La rappresentazione del numero binario segue la regola posizionale dei numeri decimali, quindi il valore
della cifra più a destra avrà un peso pari a n b 0 dove n è la cifra e b è la base della numerazione in oggetto.
Nel caso di numerazione binaria, le potenze sono tutte potenze di 2, le cifre possono essere 0 o 1.
Esempio 1001 = 9, cioè 1 * 2 3 + 0 * 2 2 + 0 * 2 1 + 1 * 2 0 = 9.
Proprietà di estensione del segno dei numeri binari in complemento a 2
I numeri binari in complemento a due godono della proprietà di estensione del segno:
Esempio: da 4 bit a 8 bit: 1101 = 11111101 oppure 0101 = 00000101.
La rappresentazione del valore decimale associato a 4 bit in complemento 2 è:(a) - 2 3 b3 + Σ i = 0..2 b i * 2 i,
infatti 1101 = - 2 3 + 2 2 + 2 0 = - 8 + 4 + 1 = -3.
Se noi estendiamo il segno da 4 bit a 5 bit otteniamo che:
- 2 4 b3 + Σ i = 0..3 b i * 2 i = - 2 4 b3 + 2 3 b3 + Σ i = 0..2 b i * 2 i = b3 ( 2 3 - 2 4 ) + Σ i = 0..2 b i * 2 i =
b3 ( 2 3 - 2 4 ) + Σ i = 0..2 b i * 2 i = b3 ( 2 3 ( 1 - 2) ) + Σ i = 0..2 b i * 2 i = b3 ( - 2 3 ) + Σ i = 0..2 b i * 2 i (a)
Big endian – peso più significativo delle cifre verso sinistra (MIPS)
Little endian – peso più significativo delle cifre verso destra (PENTIUM)
8
Il MIPS, processore RISC a 32 bit
Il microprocessore MIPS
Il MIPS è un microprocessore RISC a 32 bit.
Ha la capacità di indirizzare 2 32 locazioni di memoria pari a 4 Gbyte.
L’unità di trasferimento, la parola, è di 32 bit. Il bus di memoria è composto da:
•
32 bit di indirizzo, unidirezionali
•
32 bit di dati bidirezionali
•
# bit di controllo bidirezionali
Tutte le istruzioni del MIPS sono lunghe 32 bit (Reduced Istruction Set Computer).
Il MIPS contiene 32 registri da 32 bit nel suo Register File (o Banco Registri).
La lettura e la scrittura dei dati sul Bus della memoria avviene mediante due registri:
•
il MAR, Memory Address Registry e
•
il MDR, Memory data Registry, detto anche MBR, Memory Buffer registry
Tipi di istruzione
Il MIPS ha tre tipi di istruzioni:
•
istruzioni di tipo R – Registro (le tre R: read ‘rite, ‘ritmeitc)
•
istruzioni di tipo I – Immediato
•
istruzioni di tipo J – Salto incondizionato
Tempi di accesso ai vari tipi di memoria
Il tempo di esecuzione di un’istruzione della CPU è dell’ordine di 10 ns,
Il tempo di esecuzione di un accesso alla memoria è dell’ordine dei 100 ns, mentre
Il tempo di esecuzione di un accesso al disco è dell’ordine dei 10 ms
9
Modi di indirizzamento del MIPS
Il MIPS ha i seguenti modi di indirizzamento, di cui uno solo per accedere alla memoria
Istruzioni di
tipo I
Istruzioni di
tipo R aritmetiche
Istruzioni di
tipo R –
Load/Store
Istruzioni di
tipo R –
Salto
condizionato
Istruzioni di
tipo J –
Salto
incondiziona
to
10
Il Register File
Il register file del MIPS è composto da 32 registri di 32 bit ciascuno, due circuiti per leggere
contemporaneamente due registri: RL1, RL2, un circuito per scrivere un dato D di 32 bit in un registro: RS.
11
ALU – Unità Logica Aritmetica
L’ALU del MIPS è in grado di fare solo poche operazioni di base.
•
Il prodotto logico AND
•
La somma logica OR
•
La somma aritmetica
•
La differenza aritmetica
•
L’istruzione SLT: imposta il registro Rd con 1 nel il contenuto del registro Rs < Rt, altrimenti 0
•
Imposta il segnale di Zero se il risultato della differenza dei due registri Rs - Rt è uguale a zero
Di seguito la cellula elementare di un bit dell’ALU.
La differenza è ottenuta applicando la formula valida per i numeri binari in complemento 2: a – b = a +⎯b + 1.
Il segnale di controllo Kalu2 è chiamato anche “inverti b” e serve sia per selezionare il segnale b negato in
ingresso al sommatore, sia per impostare ad 1 il bit di carry del solo bit 0 dell’ALU.
Gli altri bit di controllo KAlu0 e KAlu1, selezionano l’operazione richiesta dall’istruzione eseguita.
I bit di controllo KAlu0, KAlu1, KAlu2 sono calcolati dall’unità di controllo della CPU e dell’ALU.
12
Di seguito riportiamo il simbolo dell’ALU e la tabella delle combinazioni dei 3 bit di controllo calcolati dalla
CPU e forniti in input per controllare l’operazione aritmetico/logica richiesta:
Op
Kalu2 Kalu1 Kalu0
AND
X
0
0
OR
X
0
1
ADD
0
1
0
SUB
1
1
0
SLT
1
1
1
E’ possibile rappresentare l’ALU come un insieme di cellule di un bit in cascata anche se non è la soluzione
adottata nelle CPU a causa dei tempi di propagazione delle somme ai bit successivi (problema della
profondità dei circuiti booleani).
Il bit Zero è impostato quando tutti i bit del risultato dell’operazione sono a zero ed è utilizzato per eseguire i
salti condizionati, infatti l’esecuzione di una beq $r1, $r2, label (salta se i due registri sono uguali), è ottenuta
sottraendo al primo registro il secondo e utilizzando il valore del bit di zero impostato come abilitazione al
circuito di salto (vedi istruzioni di tipo R).
13
La moltiplicazione nel MIPS
La moltiplicazione è realizzata secondo l’algoritmo sotto riportato.
Pseudo istruzione
Note
Risultato = 0
Ripeti 32 volte
Se il bit meno significativo del Moltiplicatore = 1
Risultato = Risultato + Moltiplicando
Left Shift ( Moltiplicando )
Right Shift ( Moltiplicatore )
Fine Ripeti
Il circuito che lo implementa è il seguente:
Questo circuito però presenta un problema: è necessario utilizzare 3 registri a 64 bit con conseguente
complicazione della logica del processore.
Si è arrivati quindi alla seguente soluzione:
Ponendo il risultato della somma iterata nella parte superiore dei 64 bit del risultato e shiftando il risultato a
destra ad ogni iterazione, utilizziamo solo un registro a 64 bit per il risultato, gli altri 2 sono a 32 bit.
14
Di conseguenza l’algortimo utilizzato risulta il seguente:
Pseudo istruzione
Commento
Ris = 0
Ris = Registro risultato a 64 bit
M = Moltiplicando
Q = Moltiplicatore in LRis
LRis = 32 bit meno significativi
Ripeti 32 volte
Se Q0 = 1
HRis = HRis + M
Q0 = Bit meno significativo del moltiplicatore
HRis = 32 bit più significativi
Right Shift ( Ris )
Fine Ripeti
Se poi osserviamo che i 32 bit meno significativi del risultato sono inutilizzati e vengono shiftati a destra
come il moltiplicatore, possiamo realizzare una ulteriore versione:
15
L’algoritmo di Booth
Una ulteriore raffinamento del processo di moltiplicazione è stato introdotto da Booth, da cui il nome
Algoritmo di Booth, che ha osservato come data una sequenza di bit a 1, per esempio 00111100, la somma
dei bit a 1 consecutivi poteva essere espressa come la differenza tra 01000000 e 00000100:
c = 00111100 = 1 x 25 + 1 x 24 + 1 x 23 + 1 x 22 = 60,
a = 01000000 = 1 x 26 = 64,
b = 00000100 = 1 x 22 = 4,
a – b = 64 – 4 = 60 = c
In simboli possiamo scrivere che:
Σ i = a .. b bi x 2i
= 2b+1 – 2a .
Possiamo quindi eseguire meno somme per ottenere lo stesso risultato:
Senza algoritmo di Booth
Con algoritmo di Booth
Moltiplicando x ( 00011110 )
4
3
2
Moltiplicando x ( 00011110 )
1
Mx(1x2 +1x2 +1x2 +1x2 )
M x (1 x 25 - 1 x 21 )
M x ( 16 + 8 + 4 + 2 ) = M x 30
M x ( 32 - 2 ) = M x 30
Dal momento che la moltiplicazione è realizzata mediante l’iterazione di somme del moltiplicando, l’algoritmo
di booth diminuisce il numero di somme necessarie, lasciando inalterato il numero degli shift a destra:
Pseudo istruzione
Note
Ris = 0
Ris = Registro risultato a 64 bit
Q-1 = 0
Bit shiftato = 0
M = Moltiplicando
Q = Moltiplicatore in LRis
LRis = 32 bit meno significativi
Ripeti 32 volte
Se Q0 Q-1 = “10” allora
HRis = HRis - M
– 2a , HRis = 32 bit più significativi
Altrimenti Se Q0 Q-1 = “01” allora
HRis = HRis + M
+ 2b+1
Right Shift ( Ris )
Fine Ripeti
16
Progetto dell’Unita di Controllo Principale del MIPS
Le istruzioni di tipo R
Le istruzioni di tipo R sono quelle prevedono l’utilizzo dei registri per effettuare operazioni aritmetiche sui
registri, salti condizionati, letture e scritture in memoria.
Segnali di controllo
Di seguito la tabella riassuntiva dei segnali di controllo in funzione del tipo di istruzione eseguita.
17
Istruzioni tipo R - Aritmetiche
Le istruzioni aritmetiche sono caratterizzate dall’avere il codice operativo dell’istruzione IR [31..26] con i 6 bit
tutti a 0.
I 6 bit a zero sono utilizzati per generare il bit di controllo RegWrite (porta NOR), che abilita la scrittura del
risultato dell’operazione logica calcolata, nel registro di destinazione.
18
Istruzioni tipo R – Salti condizionati
Le istruzioni di salto condizionato sono caratterizzate dall’utilizzare i registri Rs e Rt per eseguire il confronto,
mentre i bit da 0..15, che normalmente contengono di valori di Rd, Shamt e Funct, contengono un offset che
rappresenta il numero di istruzioni da saltare in avanti o indietro rispetto al Program Counter (PC).
Il confronto nella Branch On Equal è realizzato mediante la sottrazione di Rs con Rt. Se i due registri sono
uguali, il bit di Zero dell’ALU è posto a 1 e abilita la somma del’offset PC + 4 + #Istruzioni x 4.
19
beq R1, R2, Offset
Note
PC Å PC + 4
Incrementa subito il Program Counter
BRANCH Å 1
Segnale di controllo
ALU1 Å R1
1° Operando ALU
ALU2 Å R2
2° Operando ALU
ZERO Å True ( ALU1 – ALU2 == 0 )
FullOffset Å SE(Offset(16 bit))
Estensione di segno a 32 bit dell’offeset
FullOffsetx4 Å SHL2 ( FullOffset)
Moltiplico l’offset per 4 eseguendo lo shift a sinistra
NEWPC Å PC + 4 + FullOffsetx4
Preparo il salto di FullOffset istruzioni per il PC
If ( ZERO And BRANCH ) Then PC Å NEWPC
Eseguo il salto se la condizione è rispettata
Else PC Å PC + 4
Istruzioni tipo R – Load / Store
Le istruzioni di caricamento dalla memoria e salvataggio in memoria sono caratterizzate dall’utilizzare i
registri Rs + Offset di 16 bit per determinare l’indirizzo di memoria dal quale leggere / scrivere il dato da
depositare in / prelevato da Rt.
Lw R1, Offset(R2)
Note
PC Å PC + 4
Incrementa subito il Program Counter
MemRead Å 1
Segnale di controllo
ALU1 Å R2
1° Operando ALU
FullOffset Å SE(Offset(16 bit))
2° Operando ALU – Est. di segno a 32 bit dell’offset
MAR Å ALUOut
L’indirizzo da leggere è posto sul bus degli indirizzi
MBR Å MEM [ MAR ]
Lettura del dato all’indirizzo MAR
RegWrite Å 1
Segnale di controllo
MemoToReg Å 1
Segnale di controllo
R1 Å MBR
Scrivo il dato in R1
20
I segnali KAlu[0..2] impostano la somma dei due operandi, il segnale AluSrc indica al mutiplexer di
selezionare come secondo operando l’offset, esteso a 32 bit, al contenuto del registro di base Rs.
Questo schema è comune sia alla lettura che alla scrittura, nei prossimi schemi vedremo come vengono
utilizzati i segnali MemWrite, MemtoReg e MemRead.
21
MIPS simple data path
Schema riassuntivo dei datapath fino ad ora visti, con l’aggiunta della logica di fetch dell’istruzione (1)
combinata con la logica del salto condizionato (2)
1
2
Di seguito un’ipotesi di integrazione ulteriore con la logica di salto incondizionato (3).
3
22