Sistemi Complessi di reti
sequenziali
Pipeline
Corso ASE - Prof. Antonino Mazzeo
Ing. Valentina Casola
2009/2010
1
Tempificazione dei sistemi sequenziali
complessi
I
U
X
Y
CK
2
Il segnale di clock
• Il clock è un segnale indipendente caratterizzato da un
periodo di clock (o ciclo di clock) TCK.
• Frequenza del clock: fCK= 1/TCK;
• Nel periodo TCK il segnale assume Il valore logico 1 per
un tempo TH e il valore logico 0 per un tempo TL
• Il rapporto TH / TCK è detto duty-cycle
• Il passaggio dal valore 0 al valore 1 è detto fronte di
salita
• Il passaggio dal valore 1 al valore 0 è detto fronte di
discesa
3
Tempi caratteristici di un flip-flop
• Per essere riconosciuto correttamente, l’ingresso
deve rimanere stabile all’interno di una finestra di
tempo nell’intorno di un fronte del clock
• Tempo di Set-Up (Ts)
– Intervallo minimo che precede l’evento di clock
durante il quale l’ingresso deve essere mantenuto
stabile;
• Tempo di Hold (TH)
– Intervallo minimo che segue l’evento di clock durante
il quale l’ingresso deve essere mantenuto stabile
• Tempo di propagazione (Tq)
4
Tempificazione di un sistema
sequenziale: vincoli
T deve soddisfare la
condizione:
T ≥ tq + τc,max +tsetup
tq è il tempo di
commutazione
τc,max è il tempo di calcolo
della rete
tsetup è il tempo di set-up
del registro
Vincolo sui FF:
5
Note: clock skew
Y
W
M
M
CK’
CK
Δ
T + Δ ≥ tq + τc,max +tsetup
tq + τc,min >th + Δ
6
Interconnessione fra reti sequenziali
Rete
1
Rete
3
Rete
2
Rete
4
7
Ciascuna rete sequenziale può essere
•
•
•
•
Una rete di Mealy
Una rete di Moore
Ciascuna rete può essere di tipo impulsivo o asincrona
Se le reti sono di tipo differente la descrizione del
funzionamento del sistema dipende dal tipo di ogni
singola rete e dalla loro interconnessione
• Se le reti sono omogenee e di tipo LLC è possibile
descrivere il loro comportamento in modo sistematico
con metodi di specifica e verifica ben consolidati nel
mondo industriale (i sistemi digitali complessi sono di
questo tipo).
8
Determinazione del tempo di ciclo
• In una rete level input, level output, clocked (LLC)
occorre determinare il periodo del clock, ovvero il
tempo di ciclo (intervallo minimo tra due impulsi
di abilitazione della rete)
• Il tempo di ciclo dipende dalla tipologia delle
macchine adottate (Mealy, Moore) e dalla
topologia della loro interconnessione;
• Analizziamo:
– Catene a ciclo aperto,
– Catene a ciclo chiuso
9
Catene aperte e catene chiuse di reti
sequenziali
• Una catena aperta è costituita da una cascata
di reti sequenziali in cui l’uscita dell’una è
applicata all’ingresso della successiva, fatta
eccezione della prima e dell’ultima
Rete
Combin.
Rete
Combin.
Rete
Combin.
10
Reti di Mealy e di Moore e dipendenza
dalle informazioni (input e stato)
Rete di Mealy
I
Rete di Moore
U
S
S’
CK
I
U
S
S’
CK
11
Definizioni e determinazione del ciclo
di clock
• Per classificare le reti si introduce il concetto
di percorso, fatto da diverse tratte connesse in
cascata:
– Percorso libero è fatto di tratte libere, ovvero
costituite da sole reti combinatorie (es. funzione
uscita e funzione stato prossimo);
– Percorso condizionato, se è presente almeno una
tratta condizionata, ovvero che contiene almeno
un registro.
12
Catena aperta di macchine di Mealy
I
U
I
U
I
U
S
S
’
S
S
’
S
S
’
CK
13
Determinazione del ciclo di clock per
catena aperta Mealy
• Esiste più di un percorso libero che connette
l’ingresso con l’uscita:
– ω1(i1,s1), ω2(i2,s2),…….. ωn(in,sn)
– ω1(i1,s1), ω2(i2,s2),…….. δn(in,sn)
T ≥ (n-1) tω,max + max (tω,max , tδ,max ) ≈ n tω,max
14
Catena aperta di macchine di Mealy-Moore
I
U I
U
I
U
I
U
S
S S
’
S
’
S
S
’
S
S
’
CK
15
Determinazione del ciclo di clock per
catena aperta Mealy- Moore
• Esiste più di un percorso libero che connette
l’ingresso con l’uscita; le tipologie di tratte libere:
– Ingresso, tratte Mealy, tratta Moore
– Tratta Moore, tratte Mealy, tratta Moore
– Tratta Moore, tratte Mealy, uscita
– Il T sarà calcolato considerando il tempo di
propagazione massimo tra tutti i percorsi liberi
16
Catena aperta di macchine di Moore
I
U
I
U
I
U
S
S
’
S
S
’
S
S
’
CK
17
Determinazione del ciclo di clock per
catena aperta Moore
• Caso particolare del precedente, i percorsi liberi
sono:
– Ingresso esterno, tratta δ
– Tratta ω, tratta δ
– Tratta ω, uscita
• Il tempo di propagazione massimo è dato al più
dalla somma di due reti combinatorie MA:
l’ingresso applicato all’ingresso condiziona
l’uscita solo dopo n cicli di clock, dunque è
sempre necessario attendere nT
18
Catena chiusa di macchine di Mealy
I
U
I
U
I
U
S
S
’
S
S
’
S
S
’
CK
Queste macchine possono non funzionare correttamente, l’uscita dipende da se stessa e
Il sistema può non stabilizzarsi:
un= ωn(in,sn) = ωn(ωn-1(in-1,sn-1),sn) = ωn(ωn-1( ……. ω1(u1,s1)),sn)
19
Catena chiusa Mealy-Moore
I
U I
U
I
U
I
U
S
S S
’
S
’
S
S
’
S
S
’
CK
20
Determinazione del ciclo di clock
per catena chiusa Moore
Come nel caso di catena chiusa ma senza ingressi ed
uscite esterne:
– Una tratta δ
– Una tratta ωmoore
– Zero, una o più tratte ωmealy
• Il tempo di propagazione massimo è
dimensionato dal massimo tra i tempi dei vari
percorsi possibili
21
Realizzare una catena chiusa avendo solo
macchine di Mealy: aggiunta registro
I
U
I
U
M
S
S’
S
S’
CK
Percorsi:
-ω2,δ1
-ω2, ω1
-δ2
22
Catena aperta di reti combinatorie
Y
A
D
F
G
H
D
CK
Tmin = tq + ts + tpF + tpG + tpH ≈ 3 tp,comb
23
Pipeline: Introduzione
• Il miglioramento delle prestazioni di un generico circuito digitale è
legato principalmente alla riduzione della profondità combinatoria
• Tale riduzione si può ottenere:
– Ottimizzando le parti puramente combinatorie del circuito
– Frazionando opportunamente le parti combinatorie per mezzo di registri
• Un generico data-path è costituito da una sequenza di operazioni
eseguite in cascata: questa struttura si presta molto bene al
frazionamento
• Una architettura in cui sono presenti registri con lo scopo di
frazionare la computazione viene detta pipeline
• Nelle architetture dei calcolatori l’introduzione di pipeline aumenta
il numero di istruzioni eseguite nell’unità di tempo
24
Pipeline di reti combinatorie
A
M
XF
F
YF
M
XG
G
M
H
M
Ck
25
Tempificazione di una Pipeline
Tmin ≈ max( tpF , tpG , tpH )
Il fattore guadagnato è pari al numero di stadi della pipe
26
Architetture pipeline parallele
• 3 reti con tempi di calcolo di 50 ns e una rete
con tempo di calcolo di 100 ns
– Frequenza di pipe non può essere migliore di 100
MHz (T=1/f=100 ns) e le tre reti più veloci sono
sfruttate al 50%
• Soluzione parallela che duplica rete a 100 ns,
con reti funzionanti in controfase, multiplate
nel tempo
27
Architettura pipeline con reti parallelo
φ/2
φ/2
M
C1
M
!φ/2
C2
M
Cn
M
M
φ
φ/2
T-FF
!φ/2
28
Calcolo del tempo di ciclo
• T per la rete lenta è vincolato da
2T ≥ tf + 2τcmax + τmux+ tsetup
da cui
T ≥ τcmax + ½(tf + 2τmux+ tsetup)
• T per la rete veloce è vincolato da
T ≥ tf + τcmax + tsetup
• Va scelto il massimo fra i due:
T ≥ τcmax + max(½(tf + τmux+ tsetup), (tf + tsetup))
29
Applicazioni delle pipeline alle CPU
• L’esecuzione di una istruzione assembler consiste nello
svolgimento di alcune operazioni in sequenza
• E’ possibile scomporre una istruzione in un numero
variabile di operazioni:
– Una scelta comune consiste nella decomposizione in 5
operazioni
– Le architetture moderne arrivano fino a 20 operazioni
• Le varie operazioni, dette fasi o stadi, possono essere
eseguite:
– Nello stesso ciclo di clock
– In cicli di clock successivi
• Nel secondo caso si parla di una architettura pipeline
30
Esempio: Fasi di esecuzione del
Processore DLX
• La decomposizione in 5 fasi consiste in
– Fetch: Lettura dell’istruzione (una o più parole) dalla
memoria di programma. L’istruzione viene memorizzata
nel registro IR
– Decode: Scomposizione dell’istruzione in campi (codice
operativo, registro, costante, ecc), a seconda del formato e
delle modalità di indirazzamento
– Execute: Esecuzione delle operazioni aritmetico-logiche
oppure calcolo dell’indirizzo di destinazione di un salto
– Memory access: Accesso in lettura o scrittura alla
memoria o ad una periferica
– Write back: Salvataggio del risultato prodotto
dall’istruzione nel registro destinazione
31
Modello di riferimento del DLX
Istruzione i
istruzione i+1
istruzione i+2
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
32
Pipeline: Speed up e latenza
• Teoricamente, se gli stage della pipe sono
perfettamente bilanciati e non si verificano
condizioni di stallo, il tempo per ogni singola
istruzione è:
Ti = tempo per istruzione senza pipe
Nstage della pipe
• Il tempo per avere la prima istruzione è detto tempo
di latenza ( si ha ogni qual volta si verifica uno stallo)
• In realtà bisogna considerare il tempo di setup dei
latch tra i vari stadi della pipe ed il bus skew
33
Fasi di esecuzione
• Si noti che:
– Non tutte le fasi devono essere sempre presenti.
Alcune istruzioni possono necessitare solo di
alcune delle fasi descritte
– Non tutte le fasi devono essere sempre distinte.
Alcune istruzioni possono raggruppare due o più
fasi in una sola
– La fase di fetch è sempre presente
– Fasi diverse possono avere durate diverse
34
Esempio: Sistemi Superscalari con
più Pipeline
Addizione:
Addizione e
Moltiplicazione:
35
Conclusioni
• Throghput: quantità di dati elaborati nell’unità di tempo
• Thoughput = Noperations / T
• Latenza: ritardo tra l’ingresso e l’uscita (tempo necessario da attendere per
l’esecuzione della prima istruzione)
• Latenza = Ty - Tx = T
• L’introduzione di pipelining è vantaggioso in quanto:
• Throughputpipe >>Throughput no pipe
• Latenzapipe ≈ Latenzano pipe
36