Calcolatori Elettronici Lezione 5 Reti Sequenziali Sincrone · Definizione di Rete Sequenziale ......

1

Calcolatori ElettroniciLezione 5Reti Sequenziali Sincrone

Ing. Gestionale e delle TelecomunicazioniA.A. 2007/08Gabriele Cecchetti

G. Cecchetti Calcolatori Elettronici per Ing. Gestionale e Telecomunicazioni 2

Reti Sequenziali Sincrone

Sommario:Introduzione, tipi e definizioneCondizioni per il corretto funzionamentoRete Sequenziale Sincronizzate di MooreRegistri, Flip-flop J-KRete Sequenziale Sincronizzata di Mealy ritardatoRete Sequenziale Sincronizzata di MealyUnità con Parte Operativa e Parte Controllo

RiferimentiG. Corsini “Dalle porte AND OR NOT al sistema calcolatore: un viaggio nel mondo delle reti logiche”: cap. “Reti Sequenziali Sincrone”

2


Introduzione alle Reti Sequenziali Sincrone

Le Reti Sequenziali Sincrone (RSS) si differenziano dalle RSA per il fatto che lo stato può evolvere solo a determinati istanti.Questi istanti sono determinati dalla transizione da 0 a 1 di una particolare variabile detta clock.Quindi, per quando riguarda l’evoluzione dello stato è come se il tempo fosse discreto e non continuo.La frequenza di clock indica quante volte il clock passa da 0 a 1 e viceversa nell’unità di tempo.Esempio 1Mhz = 1 ciclo di clock ogni μs.


Tipi di Reti Sequenziali Sincrone

Moore: l’uscita dipende solo dallo statoMealy: l’uscita dipende sia dallo stato che dall’ingresso

3


Rete sequenziale sincrone di Moore


Definizione di Rete SequenzialeSincronizzata di MooreRSS di Moore è una qualunque struttura che soddisfa ai seguenti requisiti:

è dotata di N var. d’ingresso xN-1,xN-2,…,x0è dotata di M var. di uscita zM-1,zM-2,…,z0a’è dotata di un meccanismo di marcatura che seleziona ad ogni istante uno ed un solo elemento appartenente ad un opportuno insieme S={S0,S1,…,SK-1},implementa una legge per gli stati interni A: SxX ⇒ S,implementa una legge per gli stati di uscita B: S ⇒ Z,è dotata di un ingresso p, detto clock, le cui transizioni dal 0 a 1 vanno considerate come informazioni temporali da utilizzarsi in accordo alla seguente legge di evoluzione del tempo:“detti X[t] e S[t] sono lo stato d’ingresso presente e lo stato interno presenti ad un certo istante t precedente l’arrivo di un fronte in salita del clock,calcolare lo stato lo stato interno successivo S*=A{S[t],X[t]};quando arriva il fonte in salita del clock marcare S* promuovendolo al rango di stato interno presente;quindi calcolare ed impostare lo stato di uscita Z=B{S*},e così via all’infinito.

4


Condizioni per il corretto funzionamento di una RSS di Moore (1/2)

Il tempo T fra due fronti in saluta del clocksia sufficiente a che la rete possa:

utilizzare il meccanismo di marcatura (per promuovere S* a S;calcolare il nuovo stato di uscita (sia TB il tempo necessario);calcolare il nuovo stato interno successivo (sia TA il tempo necessario);avere ancora un margine di tempo TSETUP legato alla natura del meccanismo di marcatura.


Condizioni per il corretto funzionamento di una RSS di Moore (2/2)

T-(TMARK +TA+TASETUP) è il tempo a disposizione per cambiare X e far estinguere tutti i transitori.TA+TASETUPè il tempo in cui X non deve essere rimosso (calcolo S* e marcatura) In questo modo la rete si comporta in

modo deterministico.

5


Evoluzione temporale di una RSS di Moore

Macchina (ideale) sincrona a stati finiti.


Non trasparenza delle RSS di Moore

Lo stato di uscita non cambia negli intervalli di tempo:

ti – TSETUP , ti + TMARK

6


Modelli strutturali per le RSS di Moore (1/2)

S = {S0,S1,…,SK-1} sono codificati tramite K delle 2W combinazioni dei valori delle var. di stato yw-1,yw-2,…,y0 con W ≥⎡log2K ;La sottorete sequenziale SN marca all’uscita lo stato interno;CN1 + SN implementano sia la legge A che il meccanismo di marcatura(operazione non istantanea, SN produce stati spuri che però non creano malfunzionamenti perché SN non è trsparente;CN2 implementa la legge B.


Modelli strutturali per le RSS di Moore (2/2)

SN (RSS primitiva) può essere implementata conregistri,flip-flop SR sincronizzati,flip-flop J-K sincronizzati.

7


Registri

Ugual numero di variabili di ingresso e uscita.Lo stato di uscita all’istante ti coincide con lo stato d’ingresso presente all’istante ti-1.E’ dotato di un ingresso per il reset asincrono (tutte le varabili di uscita vengono fissate al livello 0).

Il registro è una collezione di FF D+edge triggeredtemporizzati in parallelo.


Flip Flop J-K : specifica di funzionamento

Specifica di funzionamento:

Commutazioneq’=/q11

ConservazioneConservazioneq’=q00

Reset010

Set101

qkj

Tabella di applicazione

-

--10j

101

-011-10-00kq’q

8


Flip-Flop J-K: diagramma a stati e tabella di fluso

S0/0 S1/1

j k1 01 1

j k0 11 1

j k0 01 0

j k0 00 1


Flip-Flop J-K: considerazioni

Non ci sono problemi di stabilità percheè il tempo èdiscreto. Lo stato rimane sempre staile per un intero ciclo di clock e così anche l’uscita.Non è importante se CN1 ha alee oppure no.Non c’è il problema della corsa delle variabili di stato, quindi in generale sono ammesse transizioni multiple in ingresso.

→ Quindi l’introduzione del clock semplifica la realizzazione dei circuiti a patto che la temporizzazione sia rispettata.

9


Flip-Flop J-K: sintesi

1. Modello strutturale sceltoLa sottorete SN è un registro

2. Codifica degli statiS0 = <0>S1 = <1>

Con questa codifica degli stati CN2 è un corto circuito

3. Tabella degli stati

4. Sintesi CN1a = j/y + /ky

110011

011000

q10110100y jk


Riconoscitore di sequenza 01,11,10 (1/3)

Diagramma di flusso

S0/0 S1/0 S2/0 S3/100

10

11

01

01

01

11 10

00, 10

00, 11,10

00,11

01

10



1. Tabella di flusso2. Codifica degli stati interni3. Tabella di flusso con gli stati interni codificati



Modello strutturale

CN1

S pR Q

pCN2

j1

j0

k0

x1

y1

y0

z1

z0

J QK p k1

x0

Leggi caratterizzanti CN1 e CN2CN1: a partire dalla tabella degli stati codificati,

1) si calcola calcolano il valore che deve essere impostato sui piedini j1,k1 e j0,k0 affinché avvengano le transizioni di stato richieste;

2) si dividono le tabelle di pilotaggio cosi’ ottenute in modo da ottenere le espressioni algebriche di j1, k1, j0 e k0.

CN2: a partire dalla codifica degli stati e delle uscite corrispondenti (in questo caso z=y1/y0)

11


Reti sequenziali sincronizzate di Mealy Ritardato

Differenza rispetto alle RSS di Moore:B : S x X ZLegge di evoluzione nel tempo:“Detti X[t] e S[t] lo stato d’ingresso presente e lo stato interno presenti ad un certo istante t precedente l’arrivo di un fronte in salita del clock,calcolare sia lo stato lo stato interno successivoS*=A{S[t],X[t]} che lo stato di uscita Z=B{S[t],X[t]}e promuoverli al rango di stati presenti solo quando arriva il fronte in salita del clock,e così via all’infinito.”


Modello strutturale per RSS di Mealy Ritardato

Definiamo:registro STAR, la porzione di registro che memorizza lo stato S;registro OUTR, la porzione di registro che memorizza il prossimo stato di uscita.

12


Condizioni per il corretto funzionamento

Condizioni per il corretto funzionamento:T ≥ TMARK + max{TA,TB} + TSETUP

X[t] stabile da max{TA,TB} + TSETUP secondi prima a TMARKsecondi dopo

Rispettando queste condizioni la rete si evolve in modo deterministico eZ[ti] è funzione di X[ti-1], X[ti-1], …, X[t0], S[t0]Vantaggi:

minor numero di stati interni a parità di problema risolto,si adatta meglio ad essere implementato sulle PLA


Reti sequenziali sincronizzate di Mealy

Differenza rispetto alle RSS di Mealy ritardato:le variabili di uscita sono prelevate direttamente dalla rete combinatoria

l’ingresso influenza direttamente l’uscitasvantaggio: troppi transitori sull’ucita

svantaggio: rischio di creare anelli instabili di reti combinatorie se più reti di Mealy vengono interconnesse nel costruire unitàcomplesse

Per questi motivi non vengono utilizzate.

13


Modello strutturale per RSS di Mealy


Formalizzazione delle RSS di Mealy ritardato tramite programmi (1/2)L0: OUTR:=0; goto {if <x1 x0> eq 11 then L1 else L0}

L1: OUTR:=0; goto {if <x1 x0> eq 01 then L2 else if <x1 x0> eq 11 then L1 else L0}

L2: OUTR:=if <x1 x0> eq 10 then 1 else 0; goto{if <x1 x0> eq 11 then L1 else L0}

Ove: Lh ⇔ Sh ed eseguire lo statement Lh significa:1) calcolare sia lo stato di uscita (espressione a dx. di := );2) calcolare lo stato interno successivo (espressione a dx. di goto);

3) dopo il clock rinnovare OUTR e STAR.

14


Formalizzazione delle RSS di Mealy ritardato tramite programmi (2/2)

Ogni statement k-esimo del programma è costituito da:Un etichetta Lk in corrispondenza biunivoca con lo stato interno (Lh ⇔ Sh) Una microoperazione che ha la forma OUTR=fk(X)Un microsalto che in generale ha la forma:goto {if conditionk1(X) then Lk1T else if …conditionkP(X) then LkPT else LkF}

L’insieme dei microsalti costituisce il flusso di controllo;L’insieme delle microperazioni rappresenta il flusso dei dati.


Rete combinatoria operativa

Sono presenti due microoperazioni:OUTR:=0OUTR:=if <x1 x0> eq 10 then 1 else 0

Esse possono essere compattate nella microoperazione globale:OUTR:=case <b0> of

{ 0 : 0.

1 : if <x1 x0> eq 10 then 1 else 0}

Implementabile con il seguente circuito sequenziale(rete combinatoria OPERATIVA)dove b0 è la var. di comando.

15


Rete combinatoria di condizionamento

b0 può essere generata da un RSS di Moore per mezzo del seguenteprogramma.L0: <b0>=0; goto {if <x1 x0> eq 11 then L1 else L0}L1: <b0>=0; goto {if <x1 x0> eq 01 then L2 else if <x1 x0> eq 11 then L1 else L0}L2: <b0>=1; goto {if <x1 x0> eq 11 then L1 else L0}Si noti che i microsalti possono essere di 2 tipi:if <x1 x0> eq 11 then …if <x1 x0> eq 01 then …Allora è possibile definire una rete combinatoria di condizionamento avente in ingresso x1 ed x0 che genera le var. c1 e c0:c1 = if <x1 x0> eq 11 then 1 else 0c0 = if <x1 x0> eq 01 then 1 else 0


Parte controllo

Il circuito che porta avanti il flusso di controllo è detto parte controllo ed è espresso quindi dal seguente programma:L0: <b0>=0; goto {if <c1> eq 1 then L1 else L0}L1: <b0>=0; goto {if <c0> eq 1 then L2 else if <c1> eq1 then L1 else L0}L2: <b0>=1; goto {if <c1> eq 1 then L1 else L0}

L’insieme del registro OUTR, la rete combinatoria operativa e la rete combinatoria di condizionamento è invece detto parte operativa.

16


Modello di Mealy ritardato per il riconoscitore di sequenza con parte operativa e parte controllo


Modello generalizzato di Mealy ritardato con parte operativa e parte controllo

17


Considerazioni sul modello generalizzato di Mealy Ritardato con PO e PC

Scarsa elasticità della parte operativa.Conviene migliorare il modello in modo da poter eseguire i programmi scritti in linguaggio ad alto livello. Pertanto occorre:

differenziare il registro OUTR in tanti registri operativi R0 .. RQ-1;i registri operativi possono essere utilizzati anche per risultati iniziali o intermedi oltre che per le var. di uscita;I registri operativi possono essere anche accessi in lettura.

Pertanto ora il k-esimo statement ha:Q microoperazioni del tipo Rq=fk(.) con q = 0, .., Q-1un microsalto del tipogoto {if conditionk1(.) then Lk1T else if …conditionkP(.) then LkPT else LkF}dove (.) sta per (X, <R0>, .., <RQ-1>).


Unità sincronizzata

PC è RSS di MoorePO è RSS di Mealy con

var. effettiva di uscita seguite dai registrivar. di uscita in ingresso alla PC attraversano una rete combinatoria.

Globalmente è una RSS di Moore

18


Es.: unità con 2 ingressi e 4 uscite che conta modulo 16 il numero delle sequenze 11, 01, 10L0: <COUNT>:=<COUNT>; goto {if <x1 x0> eq 11 then L1

else L0}L1: <COUNT>:=<COUNT>; goto {if <x1 x0> eq 01 then L2

else if <x1 x0> eq 11 then L1 else L0}L2: <COUNT>:=if <x1 x0> eq 10 then increment{<COUNT>}

else <COUNT>; goto {if <x1 x0> eq 11 then L1 else L0Variabili di condizionamento:

c1 = if <x1 x0> eq 11 then 1 else 0c0 = if <x1 x0> eq 01 then 1 else 0

Microperazioni:COUNT:=case <b0> of

{ 0 : <COUNT>1 : if <x1 x0> eq 10 then inc{<COUNT>}

else <COUNT>}


Linguaggio di trasferimento

Formato dello statement:etichetta: microoper., …, microop.; microsalto

19


Esempio: PO e PC

PO:La sottorete inc implementa la funzione <COUNT>Ogni clock se var. b0 = 0 viene eseguita la prima microoperazione, se b0 = 1 la seconda.

PC:L0: <b0>=0; goto {if <c1> eq 1 then L1 else L0}L1: <b0>=0; goto {if <c0> eq 1 then L2 else if <c1>

eq 1 then L1 else L0}L2: <b0>=1; goto {if <c1> eq 1 then L1 else L0}


Microsalti

condizionato a 2 vie:goto {if condition(.) then Lu else Lh}

incondizionato:goto Lu

20


Microoperazioni

Rq = costanteRq = input_dataRq = <Rv>Rq = increment(<Rv>)Rq = decrement(<Rv>)Rq = addition(<Rv>)Rq = carry(<Rv>)Rq = borrow(<Rv>)Rq = shift_left(<Rv>)Rq = shitt_right(<Rv>)


Tecniche di microprogrammazione per implementare la PC di unità sincronizzate

Facciamo riferimento a 2 modelli strutturali che prevedono l’utilizzo di una ROM.La ROM ha K entrate (da 0 a K-1, una per ogni statement).Ogni entrata della ROM è selezionata tramite un microindirizzok e contiene:

i valori che le variabili di comando devono assumere in corrispondenza dello statement Lk – microcodice operativo;la codifica dell’indice EFFk della var. di condizionamento che appare nel microsalto di etichetta Lk;;gli indirizzi: microindirizzoT e microindirizzoF.

La ROM contiene una lista di microistruzioni, cioè un microprogramma e ogni microistruzione della ROM èindividuata da un microindirizzo.

21


Modello microistruction-based

Il registro STAR della parte controllo (μIR) contiene le microistruzioni, cioè gli stati S0, S1, … SK-1 , vengono codificati come microistruzioni.

- Il registro STAR deve essere molto grande (+ di 100 bit).


Modello microaddress-based

Il registro STAR della parte controllo (μIR) contiene i microindirizzi, cioè gli stati S0, S1, …SK-1, vengono codificati come microindirizzi.

+ Il registro STAR ha un formato ridotto (es. 16 bit)

22


Modello ad un livello di pipeline

Se inglobiamo la rete i condizionamento nella parte operativa, utilizzando un registro CR ad 1 bit che tiene conto del condizionamento:scompare il multiplexer per la selezione di EFF,aumenta la dimensione della ROM.


Microsalti con più alternative (1/2)

Non possiamo fare statement generali con microsalti a piùalternative: la dimensione della ROM aumenterebbe troppo.Non è accettabile dal punto di vista dei tempi avere tanti statement con microsalti standard a due vie:Introduciamo un registro operativo:Multiway Jump Register (MJR) atto a contenere microindirizzi.Scriviamo gli statement in questo modo:

Lu: MJR:=if conditionu1(.) thenmicroindirizzou1T else if … conditionuP(.) then microindirizzouPT elsemicroindirizzouPF}; goto Lu*

Lu*: … ; goto MJR.Quindi realizziamo l’unità secondo il modello illustrato nella figura seguente: ( slide successiva)

23


Microsalti con più alternative (2/2)

Il microtipok contiene0, se lo statement di etichetta Lk prevede un microsalto standard (condizionato o incondizionato),1, se lo statement di etichetta Lk preve il microsalto goto MJR.


Microprogrammi

L0: …L1: ……

Lu: … ; gosub Lsott

…

Lsott: ……

Lret: … ; return

Occorre:aggiungere alla parte operativa un registro chiamato Link Register(LR), atto a memorizzare il microindirizzo di riento dal microsottoprogramma.introdurre due nuovi tipi di microalto

gosub Lh

return.

24


Modello per i microprogrammi

La rete di selezione sceglie come indirizzo della istruzione successiva:

microindirizzoKT o

microindirizzoKF, oppure

il contenuto di MJR, se il microtipo vale 10, oppureil microindirizzoK

sott se il microtipo vale 01, oppureil contenuto del registro LR se il microtipo vale 11.


Considerazioni finali

Esistono diversi modelli strutturali ognuno caratterizzato da un proprio linguaggio di trasferimento.Questi modelli costituiscono l’architettura dei moderni microprocessori, influenzandone le caratteristiche e le potenzialità offerte.L’evoluzione temporale di queste unità costituisce l’evoluzione sequenziale degli stati delle CPU.

Calcolatori Elettronici Lezione 5 Reti Sequenziali Sincrone · Definizione di Rete Sequenziale ......

Documents

Transcript of Calcolatori Elettronici Lezione 5 Reti Sequenziali Sincrone · Definizione di Rete Sequenziale ......