Reti sequenziali complesse

Con Moore, Mealy e Mealy ritardato si descrivono reti con pochi stati. Appena il problema contiene un numero (contare fino a 200, sommare due byte, aspettare n clock) gli stati esplodono: servono registri operativi che tengano i dati, accanto al registro di stato che tiene il «punto del programma». Questo modulo insegna a descrivere queste reti in Verilog, a farle dialogare in modo sicuro con altre reti tramite gli handshake, e a sintetizzarle con un procedimento quasi meccanico: la scomposizione in parte operativa e parte controllo.

Gli esempi si possono simulare: il simulatore esegue la descrizione Verilog clock per clock e disegna il diagramma di temporizzazione. Il codice si può modificare, e il diagramma si aggiorna.

I registri operativi

Perché il modello di Mealy ritardato non basta

Vogliamo una rete che conti, modulo 16, quante volte riceve la sequenza 00, 01, 10 sui due ingressi x₁x₀, e presenti il conteggio su 4 bit. Come rete di Mealy ritardato servono 3 stati per riconoscere la sequenza e 16 valori di conteggio: circa 3 · 16 = 48 stati, un registro STAR da 6 bit e un casex con 48 etichette. Ingestibile, e il motivo è chiaro: lo stato deve ricordare due cose indipendenti, a che punto è il riconoscimento e quante sequenze ha contato.

La soluzione è separarle. Lo stato «di controllo» resta in STAR (3 stati); il conteggio va in un registro operativo COUNT da 4 bit, che si incrementa quando serve. Si arriva a un modello più generale:

• un registro di stato STAR, che fa quello che faceva in ogni RSS;
• quanti registri operativi si vuole, della dimensione che si vuole;
• il contenuto dei registri operativi, oltre a quello di STAR, entra nelle reti combinatorie che preparano i nuovi valori: COUNT può dipendere da COUNT stesso. È questo il salto di qualità rispetto al Mealy ritardato;
• le uscite sono tutte sostenute da registri operativi (anche se non tutti i registri operativi sostengono un'uscita).

Il linguaggio di trasferimento tra registri

Le descrizioni si scrivono con un blocco always che contiene un casex(STAR): ogni ramo è uno statement, cioè quello che la rete fa in quello stato. Uno statement contiene:

1. zero o più μ-istruzioni: assegnamenti ai registri operativi, come COUNT <= COUNT+1;;
2. un μ-salto: l'assegnamento a STAR. Può essere incondizionato (STAR <= S2;), a due vie (STAR <= (x==1) ? S1 : S0;) o a più vie, con operatori condizionali in cascata.

Tre regole valgono sempre, e da sole evitano metà degli errori d'esame:

Ecco il contatore di sequenze. Nella prima versione il riconoscimento produce un bit in OUTR (come in un Mealy ritardato) e COUNT gli somma OUTR; nella seconda OUTR sparisce e COUNT si incrementa direttamente in S2. Confronta i due diagrammi: con OUTR il conteggio arriva un clock dopo.

Bastano 3 stati invece di 48. La compattezza nasce dal fatto che COUNT compare a destra di un assegnamento: nel modello di Mealy ritardato un registro di uscita non poteva rientrare nelle reti combinatorie. Dal punto di vista della temporizzazione la rete obbedisce alle stesse disuguaglianze del Mealy ritardato.

Statement più compatti con le function

Variazione: contare alternativamente le sequenze 00, 01, 10 e 11, 01, 10. Le due sequenze differiscono solo per il primo passo, e quale aspettarsi dipende dalla parità del conteggio, cioè da COUNT[0]. Una piccola rete combinatoria match dice se l'ingresso è il primo passo giusto:

COUNT[0]	x1	x0	match
0	0	0	1
1	1	1	1
tutti gli altri			0

In Verilog la tabella diventa una function, e la descrizione resta di tre stati. Le function servono proprio a questo: dare un nome a una tabella di verità o a un calcolo combinatorio, non a scrivere algoritmi.

Dialogare con reti asincrone: gli handshake

L'handshake /dav-rfd

Due reti sono mutuamente asincrone quando evolvono ciascuna per conto proprio, con clock indipendenti (magari di frequenza diversa). Se una, il produttore, deve passare dei dati all'altra, il consumatore, nascono tre problemi: come capisce il consumatore che è arrivato un dato nuovo (magari uguale al precedente)? Come sa il produttore che il consumatore l'ha preso? Che cosa succede se il produttore è più veloce?

Si risolvono una volta per tutte con due fili in più: /dav (data valid, attivo basso, dal produttore) e rfd (ready for data, attivo alto, dal consumatore). Al reset entrambi valgono 1: nessun dato, consumatore pronto. Poi le transizioni si alternano:

Esempio: il formatore di impulsi

Un produttore invia ogni tanto un numero naturale su 8 bit; la rete da descrivere tiene l'uscita out a 1 per tanti clock quanto vale il numero (256 se vale 0). Prima di scrivere codice si decidono i registri: uno per ogni uscita (OUT, RFD), un contatore COUNT da 8 bit per i clock che mancano, e STAR. Il dimensionamento si fa a occhio e si rivede alla fine.

Poi le condizioni al reset: tutte le reti condividono il reset, quindi si può assumere /dav = 1; la nostra rete deve partire con out = 0 e rfd = 1. Infine il diagramma di massima, a parole:

In S0 si assegna COUNT <= numero a ogni clock: finché /dav vale 1 si campiona spazzatura, ma l'ultimo campionamento, quello fatto con /dav = 0, è corretto, e da lì si va in S1. Prova nel simulatore: il produttore manda 3, 1 e 2. Le righe blu sono pilotate dal produttore, che rispetta l'handshake e reagisce con il ritardo che imposti.

Quanti giri fa un ciclo? La regola k − j + 1

Perché il test in S1 è COUNT==1 e non COUNT==0? Lo si capisce solo con un diagramma di temporizzazione (il simulatore qui sopra lo disegna). Con numero = 1: si entra in S1 con COUNT = 1, il test sul valore vecchio è già vero, si resta in S1 un solo clock e OUT vale 1 per un clock. Con COUNT==0 si resterebbe due clock. La regola generale:

se in S_init inizializzo il contatore a k, e in S_test lo decremento e esco quando vale j ≤ k, resto in S_test per k − j + 1 clock

Con numero = 0 il test fallisce, COUNT passa a 255 (modulo 2⁸) e si fanno altri 255 giri: 256 clock in tutto, come chiede la specifica, senza scrivere niente di speciale. Quando si può scegliere, conviene inizializzare a n − 1 e testare a 0: per 8 giri, COUNT da 7 a 0 sta in 3 bit invece che in 4.

Alcuni assegnamenti sono superflui (in S2 RFD è già 0, in S0 OUT è già 0) ma lasciarli rende la descrizione leggibile: si vede subito che cosa vale ogni uscita in ogni stato. Si potrebbe anche tenere RFD a 1 in S1 e abbassarlo solo in S2: è lecito, la rete è solo un po' più lenta a liberare il produttore. Attenzione invece se in S1 si vuole usare numero (ad esempio per gestire il caso 0 a parte): allora RFD deve restare a 1, altrimenti il produttore potrebbe aver già tolto il dato.

L'handshake soc/eoc

Un altro protocollo, tipico dei convertitori analogico/digitali, è soc/eoc (start of conversion, end of conversion). Qui la prima mossa la fa il consumatore, che chiede un dato; a riposo soc = 0, eoc = 1 e il dato presente è valido.

Il formatore di impulsi diventa: in S0 alza SOC e aspetta che eoc scenda; in S1 riabbassa SOC e campiona numero finché eoc non torna a 1 (l'ultimo campionamento, con eoc = 1, è quello buono); in S2 genera l'impulso.

La sintesi: parte operativa e parte controllo

L'idea

Una descrizione dice che cosa fa la rete, non come è fatta. Per arrivare alle porte logiche esiste un procedimento semiautomatico, la scomposizione in parte operativa (PO) e parte controllo (PC). Non cerca la sintesi ottima (se servisse, la farebbe un programma): cerca una sintesi che si ottiene meccanicamente dalla descrizione e che quindi si comporta come la descrizione.

• La PO contiene i registri operativi con le loro reti combinatorie. Riceve le variabili di comando b e produce le variabili di condizionamento c, che possono dipendere direttamente dagli ingressi della rete: è una rete di Mealy.
• La PC contiene STAR. Le sue uscite b dipendono solo da STAR: è una rete di Moore. Per questo l'anello PO → PC → PO non crea problemi: contiene sempre un registro.

Passo 1: ogni registro operativo è un registro multifunzionale

Il trucco da cui discende tutto: si prende un registro operativo alla volta e si elencano le μ-operazioni diverse che subisce nei vari stati. Per il formatore:

Ogni registro diventa un registro multifunzionale: un multiplexer davanti, una via per ogni μ-operazione, e le variabili di comando a scegliere la via. COUNT ha tre vie, quindi servono due variabili di comando:

Le variabili di comando le genera la PC a partire da STAR. Ne servirebbero quattro (una per RFD, una per OUT, due per COUNT), ma si possono riusare: se scelgo b₁b₀ = 00 in S0, 11 in S1 e 01 in S2, allora OUT = b₁, RFD = b₀, e COUNT distingue le tre vie con la coppia. Dare la stessa variabile di comando a registri che ne richiedono di uguali è l'unica ottimizzazione che ci si concede: per il resto la sintesi deve corrispondere uno a uno alla descrizione.

Passo 2: le variabili di condizionamento

Si guarda ora STAR e si isolano le condizioni indipendenti che guidano i μ-salti. Nel formatore sono due, dav_==1 (usata sia in S0 sia in S2) e COUNT==1. A ciascuna si associa una variabile che vale 1 quando la condizione è vera; la rete che le calcola è la rete combinatoria di condizionamento:

• c₁ = dav_: un semplice filo (corto circuito);
• c₀ = (COUNT==1): una AND a 8 ingressi, COUNT₇ · … · COUNT₁ · COUNT₀. In Verilog si scrive con l'operatore condizionale, più leggibile di un'espressione algebrica.

La PC si riscrive usando solo le c: S0: STAR <= (c1==1) ? S0 : S1; e così via. Quello che si ottiene è la sintesi in Verilog: due moduli collegati, che si possono simulare e confrontare con la descrizione.

Si notino le dichiarazioni: la PO ha in ingresso le b e in uscita le c, la PC il contrario; le istanze collegano i fili per posizione, nell'ordine in cui il modulo elenca le porte (sbagliare l'ordine è un errore classico: il simulatore lo segnala quando le larghezze non tornano). La parte controllo, essendo una rete di Moore con pochi stati, si può poi sintetizzare con i metodi già noti: codifica degli stati, RCA e RCB.

La parte controllo come ROM

Sintesi basata su μ-indirizzi

Per parti controllo con molti stati serve un metodo generale. Supponiamo che ogni μ-salto sia a due vie, STAR <= (c==1) ? Sa : Sb;, oppure incondizionato (che è un caso particolare: le due destinazioni coincidono). La codifica di uno stato si chiama μ-indirizzo; per ognuno si scrive una riga con:

1. il μ-codice: il valore delle variabili di comando in quello stato;
2. c_eff: la codifica (in base 2, sul pedice) della variabile di condizionamento che guida il salto, «–» se il salto è incondizionato;
3. il μ-indirizzo True, dove andare se la condizione vale 1;
4. il μ-indirizzo False, dove andare se vale 0.

Questa tabella è a tutti gli effetti una ROM di 4 celle da 7 bit, e ogni cella è una μ-istruzione: dice tutto ciò che la PC fa in quello stato. La PC diventa STAR più la ROM più due multiplexer:

Sintesi basata su μ-istruzioni

Niente vieta di scambiare di posto ROM e registro: si mette la ROM a monte e un registro STAR «molto grande» a valle, che contiene direttamente la μ-istruzione corrente. I due modelli si confrontano così:

Salti a più vie: il registro MJR

Un salto a N vie si può sempre spezzare in una catena di salti a due vie, uno stato per condizione. Ma ogni stato costa un clock, e in un processore il salto alla routine giusta dopo la decodifica di un'istruzione ha decine di alternative: perdere decine di clock per istruzione è inaccettabile, e prevedere 50 indirizzi in ogni cella della ROM è uno spreco. La soluzione è un registro operativo apposito, il Multiway Jump Register:

MJR è un registro operativo come gli altri (un multiplexer davanti, che con codifiche costanti si semplifica molto). Nella ROM si aggiunge un bit, il μ-tipo: 0 se il prossimo μ-indirizzo viene dai campi T/F, 1 se viene da MJR. Un esempio:

Le condizioni indipendenti sono tre, quindi c_eff sta su 2 bit; i salti incondizionati hanno c_eff non specificato e destinazioni T e F uguali; solo in S6 il μ-tipo vale 1.

Sottoliste

MJR permette anche di scrivere sottoliste, l'equivalente dei sottoprogrammi: pezzi di μ-programma raggiungibili da punti diversi, al termine dei quali si torna allo stato successivo a quello di partenza.

Il parallelo con i sottoprogrammi si ferma a un livello: con un solo MJR una sottolista non può chiamarne un'altra (servirebbe una pila di MJR). E in generale: MJR si usa solo se è indispensabile, molto comodo o richiesto dal testo. Quasi tutti gli esercizi si risolvono con salti a due vie.

Esercizi d'esame svolti

Perimetro di un rettangolo

Testo. Descrivere la rete XXX che ciclicamente preleva un byte dal Produttore 1 e uno dal Produttore 2, li interpreta come base e altezza di un rettangolo (naturali in base 2) e invia il perimetro al Consumatore. Non si può fare alcuna ipotesi sulla velocità degli interlocutori.

Si procede per approssimazioni successive.

1. Registri. Uno per ogni uscita: RFD1, RFD2, DAV_ (1 bit), PERIMETRO (10 bit); STAR, da dimensionare alla fine. Base e altezza si potrebbero salvare in registri, ma probabilmente non serve: una rete combinatoria mia_rete calcola 2(b + h) direttamente dagli ingressi.
2. Reset. Gli handshake sono a riposo: /dav1 = /dav2 = 1, rfd = 1 in ingresso; in uscita rfd1 = rfd2 = 1 e /dav = 1. Il valore iniziale di PERIMETRO non conta: la sua validità la stabilisce /dav.
3. S0. Tiene rfd1, rfd2, /dav a 1 e aspetta che entrambi i /dav siano a 0. Non ha senso aspettare prima uno e poi l'altro: sono indipendenti e servono tutti e due.
4. S1. Abbassa RFD1 e RFD2 (dati presi) e DAV_ (risultato pronto), poi aspetta rfd = 0 dal consumatore. Ma non può tornare in S0 senza controllare che /dav1 e /dav2 siano tornati a 1, altrimenti violerebbe l'handshake con i produttori.

Due trappole. Primo: se PERIMETRO si assegnasse in S1 e si restasse in S1 ad aspettare, dalla seconda iterazione si calcolerebbe su ingressi non più garantiti (i produttori hanno visto rfd scendere). Si sposta l'assegnamento in S0: lì PERIMETRO «balla» finché i /dav non sono a 0, ma l'ultimo valore, quello calcolato quando si esce da S0, è giusto; e nessuno lo legge prima che /dav scenda. Secondo: così non si controlla mai che rfd sia tornato a 1. Si aggiunge la condizione all'uscita da S0: si parte quando {dav1_, dav2_, rfd} == 'B001.

Guardando la descrizione si scopre che RFD1, RFD2 e DAV_ valgono sempre lo stesso bit: basta un solo registro, HS. Ecco la descrizione finale e la sua sintesi PO/PC, che il simulatore fa girare con produttori e consumatore di velocità diverse:

Nella sintesi HS è un registro a due vie (1 in S0, 0 in S1) e PERIMETRO pure (carica in S0, conserva in S1): basta una variabile di comando b₀, che vale 1 in S0. Le condizioni indipendenti sono due, quindi due variabili di condizionamento. La ROM della parte controllo:

μ-addr	μ-code b0	ceff	μ-addr T	μ-addr F
0 (S0)	1	0 (c0)	1 (S1)	0 (S0)
1 (S1)	0	1 (c1)	0 (S0)	1 (S1)

Curiosità: questa parte controllo è proprio un flip-flop JK, con c₀ = j, c₁ = k e b₀ = q.

Resta da specificare la rete mia_rete, che il testo chiede in dettaglio: un sommatore a 8 bit con il riporto uscente come nono bit dà b + h su 9 bit; moltiplicare per 2 è uno shift a sinistra, cioè un filo a massa aggiunto in coda. Nessun moltiplicatore: {(...), 1'B0}.

Prodotto con l'algoritmo di somma e shift

Testo. Stessi collegamenti, ma la rete calcola l'area (16 bit) con l'algoritmo di somma e shift: con P₀ = 0, a ogni passo

P_i+1 = ⌊(y_i · 2⁸ · X + P_i) / 2⌋    per i = 0, …, 7,    P₈ = X · Y

Cambiano i registri: AREA (16 bit) contiene P_i; serve un contatore COUNT per gli 8 giri; e serve un bit diverso di Y a ogni giro. Qui c'è una tecnica da ricordare:

Il resto segue la regola k − j + 1: per 8 giri si inizializza COUNT a 7 e si testa a 0, e COUNT sta in 3 bit. Due migliorie: abbassare RFD1, RFD2 solo in S2, così i tre registri di handshake tornano a essere uno solo (HS) e base si può usare direttamente dall'ingresso, che il produttore tiene fermo; e inizializzare COUNT al reset, perché quando si esce dal ciclo vale di nuovo 7. La rete combinatoria del passo, infine, non ha bisogno di un sommatore a 17 bit: gli 8 bit bassi del secondo addendo sono zeri, quindi ne basta uno a 9.

Nella sintesi HS, ALTEZZA e AREA sono registri a tre vie (una per stato), COUNT a due (decrementa in S1, conserva altrove): con b₁b₀ = 00, 01, 10 in S0, S1, S2 basta b₀ per COUNT. Le condizioni indipendenti sono tre:

μ-addr	μ-code b1b0	ceff	μ-addr T	μ-addr F
00 (S0)	00	00	01	00
01 (S1)	01	01	10	01
10 (S2)	10	10	00	10

Un'onda triangolare per un convertitore D/A

Testo. La rete riceve con un handshake /dav-rfd un numero N ≠ 0 su 7 bit e manda a un convertitore D/A, un byte per clock, i valori di un'onda triangolare di ampiezza N: 0, 1, …, N, N − 1, …, −N, …, 0. Il convertitore usa la legge binaria bipolare, cioè interpreta i byte come interi rappresentati in traslazione: K = k + 2⁷. Lo zero è quindi 128 ('H80), e nel caso peggiore si inviano i valori da 1 a 255.

Tre cicli: a salire da 128 a 128 + N, a scendere fino a 128 − N, a risalire fino a 128, tenendo i valori estremi per un solo clock. Per non ricalcolare gli estremi a ogni confronto si salvano in due registri, MAX e MIN. Il test va scritto sul valore vecchio, perché OUT cambia ancora al fronte: se lo si incrementa, la condizione è OUT==MAX-1; se lo si decrementa, OUT==MIN+1. Il simulatore disegna OUT come tensione:

Si noti che una nuova onda non parte subito dopo la precedente: in S4 si aspetta che il produttore abbia rialzato /dav, e nessuna specifica chiede di fare in fretta. Variante: se RFD resta a 1 fino a S3, il produttore tiene fermo ampiezza e si possono eliminare MAX e MIN, scrivendo i test come OUT==zero+ampiezza-1 e OUT==zero-ampiezza+1.

Metodo e buone norme

Prima la descrizione, poi la sintesi

Il progetto di qualunque rete logica ha due passi. La descrizione specifica in modo formale, e quindi verificabile, che cosa fa la rete; la sintesi la realizza seguendo un modello, e il procedimento garantisce che la rete sintetizzata si comporti come la descrizione (con il clock dimensionato bene e gli ingressi stabili attorno ai fronti). Saltare la descrizione è assurdo: da una sintesi sequenziale è praticamente impossibile risalire al comportamento, quindi non la si può verificare. E fermarsi alla descrizione dà l'impressione di non saper realizzare quello che si è pensato.

Verificare una descrizione combinatoria è una verifica statica: si controlla la tabella. Verificare una descrizione sequenziale è una verifica dinamica, come il test del software: si simula l'evoluzione a partire dal reset con un diagramma di temporizzazione. Non è mai esaustiva, ma non farla è sbagliato quanto non testare un programma.

Il Verilog si usa sia per descrivere sia per sintetizzare: è il formalismo, non il contenuto. assign z = (x1 & x0) | (x2 & ~x1); è una sintesi, perché si mappa direttamente su porte; un casex che elenca le uscite per ogni ingresso è una descrizione.

Buone norme per le descrizioni d'esame

Errori tipici

Verifica