1

Sistemi Complessi di reti sequenziali

PipelineCorso ASE - Prof. Antonino Mazzeo

Ing. Valentina Casola2009/2010

2

Tempificazione dei sistemi sequenziali complessi

I

X

U

Y

CK

3

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

4

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)

5

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 retetsetup è il tempo di set-up del registro

Vincolo sui FF:

tq + τc,min >th

6

Note: clock skew

M M

ΔCK CK’

Y W

T + Δ ≥ tq + τc,max +tsetup

tq + τc,min >th + Δ

7

Interconnessione fra reti sequenziali

Rete1

Rete4

Rete2

Rete3

8

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).

9

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

10

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.

11

Reti di Mealy e di Moore e dipendenza dalle informazioni (input e stato)

I

S

U

S’

CK

I

S

U

S’

CK

Rete di Mealy Rete di Moore

12

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.

13

Catena aperta di macchine di Mealy

I

S

U

S’

CK

I

S

U

S’

I

S

U

S’

14

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

15

Catena aperta di macchine di Mealy-Moore

I

S

U

S’

CK

I

S

U

S’

I

S

U

S’

I

S

U

S’

16

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

17

Catena aperta di macchine di Moore

I

S

U

S’

CK

I

S

U

S’

I

S

U

S’

18

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

19

Catena chiusa di macchine di Mealy

I

S

U

S’

CK

I

S

U

S’

I

S

U

S’

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)

20

Catena chiusa Mealy-Moore

I

S

U

S’

CK

I

S

U

S’

I

S

U

S’

I

S

U

S’

21

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

22

Realizzare una catena chiusa avendo solo macchine di Mealy: aggiunta registro

I

S

U

S’

CK

I

S

U

S’

M

Percorsi:- ω2,δ1- ω2, ω1- δ2

23

Catena aperta di reti combinatorie

F G HD D

CK

A Y

Tmin = tq + ts + tpF + tpG + tpH ≈ 3 tp,comb

24

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

25

Pipeline di reti combinatorie

GF HM M M M

Ck

A XF YF XG

26

Tempificazione di una Pipeline

Tmin ≈ max( tpF , tpG , tpH )

Il fattore guadagnato è pari al numero di stadi della pipe

27

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

28

Architettura pipeline con reti paralleloφ/2

C1 C2 CnM

M

M M

M

T-FF

φ

φ/2

!φ/2

!φ/2

φ/2

29

Calcolo del tempo di ciclo

• T per la rete lenta è vincolato da2T ≥ tf + 2τcmax + τmux+ tsetup

da cui T ≥ τcmax + ½(tf + 2τmux+ tsetup)

• T per la rete veloce è vincolato daT ≥ tf + τcmax + tsetup

• Va scelto il massimo fra i due:T ≥ τcmax + max(½(tf + τmux+ tsetup), (tf + tsetup))

30

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

31

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

32

Modello di riferimento del DLX

Istruzione i IF ID EX MEM WB    

istruzione i+1   IF ID EX MEM WB  

istruzione i+2     IF ID EX MEM WB

IF ID EX MEM WB    

istruzione i+1   IF ID EX MEM WB  

istruzione i+2     IF ID EX MEM WB

33

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 pipeNstage 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

34

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

35

Esempio: Sistemi Superscalari con più Pipeline

Addizione: Addizione e Moltiplicazione:

36

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