Comments
Transcript
Modellazione e minimizzazione circuiti sequenziali
Laboratorio di Architettura degli Elaboratori Graziano Pravadelli, Davide Quaglia Dipartimento di Informatica – Università di Verona Modellazione e minimizzazione di Circuiti Sequenziali In questa lezione vengono riassunti i concetti fondamentali per la modellazione e la minimizzazione dei circuiti sequenziali mediante SIS. Concetti fondamentali sulla modellazione di circuiti sequenziali I circuiti sequenziali sono circuiti il cui comportamento dipende non solo dai valori assunti dai segnali di ingresso nel momento presente ma anche dai loro valori negli istanti passati. Un circuito sequenziale può essere modellato utilizzando una macchina a stati finiti (Finite State Machine - FSM) definita come una 6-upla M = (S, I, O, , , s) dove: - S è l’insieme degli stati; - I è l’insieme degli ingressi; - O è l’insieme delle uscite; - è la funzione di stato prossimo che ad una coppia (ingresso, stato presente) associa lo stato prossimo; - è la funzione d’uscita che o ad una coppia (ingresso, stato presente) associa un valore per l’uscita (FSM di Mealy); o ad uno stato presente associa un valore per l’uscita (FSM di Moore); - s è lo stato di reset (a volte potrebbe non essere definito). Quando il valore delle uscite dipende sia dallo stato presente sia dagli ingressi parliamo di FSM di Mealy, quando invece il valore delle uscite dipende solo dallo stato presente parliamo di FSM di Moore. In seguito tratteremo solo FSM di Mealy. Solitamente una FSM si rappresenta per mezzo di un grafo delle transizioni (State Transition Graph - STG) dove i nodi sono gli stati e gli archi rappresentano le transizioni da uno stato all’altro. Ad ogni transizione corrisponde un insieme dei valori di ingresso ed un insieme dei valori di uscita. I circuiti sequenziali possono essere sincroni se i valori delle uscite assumono significato in corrispondenza di un evento su un segnale di sincronismo (solitamente detto clock), oppure asincroni se i valori delle uscite cambiano al variare degli ingressi senza tener conto del segnale di sincronismo. Siccome il comportamento delle uscite di un circuito sequenziale dipende dai valori in ingresso anche negli istanti passati occorre che esso contenga una sorta di memoria di tale storia passata. Questa memoria è rappresentata dallo stato. La realizzazione pratica di un circuito sequenziale pertanto richiede la presenza di elementi di memoria per la memorizzazione dello stato. L'elettronica digitale mette a disposizione due tipi di componenti detti latch e flip-flop in grado di memorizzare il valore di un bit (stato binario). Occorre quindi codificare tutti gli stati che può assumere il circuito mediante dei numeri binari e poi utilizzare dei latch o flip-flop per memorizzare tali numeri. Una FSM con N stati necessita di ⌈log 2 N ⌉ componenti di memoria elementari. La codifica scelta ha un notevole impatto sulla possibile minimizzazione del circuito. Esistono diverse regole che permettono di assegnare la codifica in modo da minimizzare la logica del circuito in base a area, ritardo, consumo di potenza, ecc. Di seguito vengono riassunti i passi da eseguire per modellare, minimizzare e mappare su una libreria tecnologica un circuito sequenziale di cui sia nota una descrizione informale. 1. Rappresentare il diagramma degli stati. 2. Estrarre la tabella degli stati dal diagramma degli stati 3. Minimizzare gli stati della FSM mediante l’algoritmo di Paull-Unger (tabella delle implicazioni). 4. Assegnare una codifica agli stati. 5. Estrarre la tabella delle transizioni a partire dalla tabella degli stati e dalla codifica scelta. 6. Estrarre la tabella delle eccitazioni da cui è possibile estrarre la logica combinatoria che descrive la funzione di stato prossimo e la funzione di uscita. 7. Effettuare la minimizzazione delle logica combinatoria. 8. Effettuare il mapping tecnologico. Per approfondimenti sulle operazioni sopra elencate si faccia riferimento ai capitoli 5, 6 del libro “Progettazione digitale” (2a edizione) di F. Fummi, C. Silvano, M. Sami. Modellazione e minimizzazione di circuiti sequenziali in SIS Per modellare un circuito sequenziale in SIS è necessario definire la tabella delle transizioni ed eventualmente la codifica degli stati (esiste un comando che permette di eseguire la codifica in modo automatico). La tabella delle transizioni deve essere descritta all’interno della sezione delimitata dalle keyword .start_kiss e .end_kiss Le transizioni devono essere specificate come un insieme di righe che riportano in ordine: valore degli ingressi, stato presente, stato prossimo, valore delle uscite. La tabella delle transizioni deve essere preceduta da 5 righe che specificano il numero di segnali di input, il numero di segnali di output, il numero di transizioni, il numero di stati e lo stato di reset. Dopo la tabella delle transizioni (dopo .end_kiss) possono essere riportate le istruzioni necessarie per definire la codifica degli stati qualora non si decida di farla definire a SIS in modo automatico. La keyword da utilizzare per definire la codifica è .code seguita dal nome dello stato e dalla sua codifica binaria. Dopo aver modellato il circuito, è possibile procedere con la minimizzazione degli stati. Una volta caricato il file .blif con il comando read_blif, la minimizzazione degli stati si esegue con il comando state_minimize stamina. Se il file contiene già la codifica binaria degli stati (.code) allora occorre generare le funzioni e col comando stg_to_network, altrimenti occorre assegnare automaticamente gli stati con il comando state_assign jedi (che genera anche le funzioni e ). Attenzione che prima occorre minimizzare gli stati e poi farne l'assegnazione. Quindi è possibile eseguire la minimizzazione delle funzioni e , ad esempio lanciando lo script script.rugged come visto per la minimizzazione dei circuiti combinatori. Eseguendo print_stats dopo stg_to_network oppure state_assign jedi si noterà che viene valorizzato il campo latches che indica il numero di elementi di memoria utilizzati nel circuito per memorizzare lo stato. Esempio Si consideri il circuito sequenziale che è in grado di riconoscere la sequenza di ingresso 00 01 11, (ingresso IN a 2 bit). Il circuito è attivo ed inizia ad analizzare i valori dell’ingresso IN quando l’ingresso START passa da 0 a 1. Nello stesso ciclo di clock in cui viene riconosciuta la sequenza 00 01 11, l’uscita OUT passa da 0 a 1. OUT rimane a 1 fino a quando gli ingressi assumeranno il valore 10; momento in cui il circuito viene nuovamente posto in attesa che il segnale START passi da 0 a 1. La seguente figura illustra il grafo di transizione degli stati. Nello stato ATT, il circuito è in attesa che il segnale di start commuti da 0 a 1. Gli altri 4 stati indicano che una porzione della sequenza è stata riconosciuta. Si noti che se nello stato 01 viene applicato l’input 00, l’automa anziché portarsi nello stato NUL si sposta nello stato 00 riconoscendo l’inizio di una sequenza valida. Scegliendo di codificare gli stati come ATT = 000, NUL = 001, 00 = 010, 01 = 011 e 11 = 100, si riporta di seguito la tabella di verità della funzione dello stato prossimo e dell’uscita OUT. Lo stato attuale è codificato mediante i bit a2 a1 a0, mentre lo stato prossimo è codificato con i bit s2 s1 s0. La rappresentazione nel formato blif è la seguente: .model automa .inputs START IN1 IN0 .outputs OUT .start_kiss .i 3 .o 1 .s 5 .p 15 .r ATT #numero di segnali di ingresso #numero di segnali di uscita #numero di stati #numero di transizioni #stato di reset #tabella delle transizioni #(ingressi, stato presente, stato prossimo, uscita) 0-- ATT ATT 0 1-- ATT NUL 0 --1 NUL NUL 0 -1- NUL NUL 0 -00 NUL 00 0 -00 00 00 0 -1- 00 NUL 0 -01 00 01 0 -00 01 00 0 -10 01 NUL 0 -01 01 NUL 0 -11 01 11 1 --1 11 11 1 -0- 11 11 1 -10 11 ATT 0 .end_kiss #codifica degli stati. #E’ opzionale perché può essere calcolata automaticamente #tramite il comando state_assign jedi .code ATT 000 .code NUL 001 .code 00 010 .code 01 011 .code 11 100 .end Una volta caricato il file blif con il comando read_blif, è possibile creare le funzioni per lo stato prossimo e per l’output con il comando stg_to_network in quanto l'assegnazione degli stati è già stata fatta manualmente. Comandi utili di SIS read_blif simulate i0 i1 i2 … print_stats write_blif write_eqn stg_to_network state_assign jedi state_minimize stamina write_kiss Carica la descrizione blif del circuito Simula il circuito in base ai valori forniti per gli ingressi. Esecuzioni successive del comando considerano lo stato in cui il circuito si è portato dopo l’ultima esecuzione Visualizza informazioni sul circuito Visualizza la descrizione blif del circuito. Visualizza le equazioni booleane corrispondenti ai nodi del circuito Costruisce le funzioni di stato prossimo e di uscita a partire dalla tabella delle transizioni e dalla codifica degli stati Usa l’algoritmo jedi per effettuare automaticamente la codifica degli stati; costruisce anche le funzioni di stato prossimo e di uscita Usa l’algoritmo stamina per minimizzare gli stati della FSM Visualizza la tabella delle transizioni Utilizzo di BVE per la definizione del diagramma degli stati BVE è un’applicazione realizzata da un gruppo di studenti dell’Università di Verona che permette di progettare graficamente circuiti digitali. Con il BVE è possibile realizzare circuiti digitali in formato blif semplicemente utilizzando il mouse e “disegnando” il circuito sullo schermo. E’ possibile progettare sia una FSM che un datapath. Un nuovo progetto in BVE 1. Lanciare il BVE con il comando bve. 2. Selezionare New Project… dalla schermata iniziale ( nella versione Beta non è implementata la funzione Load Project…, i progetti vanno aperti singolarmente dall’interno delle due sezioni distinte). 3. Selezionare il tipo di progetto: Data Path o FSM. Creazione di un circuito combinatorio con BVE: Half-Adder 1. Nella finestra Set In&Out inserire inputs e ouputs del circuito con il relativo numero di bits. L’Half-Adder riceve in ingresso due bit A e B e ne calcola la somma restituendo in uscita SUM e il riporto CARRY. Perciò è necessario creare due input da 1 bit, A e B, e due output da 1 bit, SUM e CARRY. 2. Gli ingressi e le uscite vengono visualizzati su di un foglio all’interno della finestra del progetto. Sulla sinistra nella parte superiore vi è la libreria dei sottocircuiti, nella parte inferiore l’Object Browser che mostra gli oggetti inseriti sul foglio, come inputs, outputs, bus e sottocircuiti. 3. Per generare le uscite sono necessarie due porte logiche: un AND per generare CARRY e uno XOR per generare SUM. Poiché tali porte non sono presenti nella libreria, è necessario procedere al loro inserimento utilizzando il tool di disegno. 4. Sulla destra in alto cliccare sull’icona Load a Subckt. Viene visualizzata una finestra che richiede l’inserimento del sottocircuito. Per crearne uno nuovo fare click su Editor. Viene visualizzata una finestra simile a quella del Set In&Out. 5. Generare un sottocircuito per la porta logica AND inserendo due inputs, IN1 e IN2, e un output, OUT, dopo aver inserito il nome della porta (AND) nel textbox Module Name. 6. Viene ora richiesto di inserire la tabella delle verità per la porta AND. E’ necessario definire on-set e don’t-care-set. Order specifica per quale uscita si sta specificando la tabella delle verità. Nel nostro caso l’uscita è unica, pertanto la tabella delle verità richiesta è una sola. Introdurre il seguente testo controllando di inserire uno spazio tra gli ingressi e le uscite: 11 1. 7. Cliccando su Ok viene visualizzata una piccola finestra dove è possibile disegnare l’immagine che rappresenterà la porta AND all’interno del circuito. Gli ingressi vengono posti sul lato superiore dell’immagine e le uscite sul lato inferiore. E’ possibile, ad esempio, disegnare un ovale (rispettando i limiti dell’area di disegno) e inserire al suo interno l’etichetta di testo “AND”. 8. Una volta terminato il disegno si procede al salvataggio dal menu File, Save as… Il salvataggio crea due files, un .BVG che contiene i dati grafici e un .BLIF che è l’effettivo formato blif utilizzato in SIS. Salvare AND.bvg e AND.blif. 9. Una volta salvati i files chiudere la finestra del BVE Graphic Editor. La porta AND è stata creata. E’ necessario inserirla nella libreria di progetto in modo da poterla importare ad ogni necessità. All’interno della finestra da dove è stato lanciato l’editor grafico inserire il nome della porta AND. Tramite Choose scegliere il file bvg appena creato e il relativo file blif. Cliccando su Ok, la porta AND viene aggiunta all’interno della libreria. 10. Eseguire la stessa procedura per creare la porta XOR, creando il sottocircuito mediante il BVE Graphic Editor e inserendo i file BVG e BLIF all’interno della libreria. 11. E’ possibile salvare la libreria di oggetti in modo tale da poterla caricare ad ogni apertura del BVE. 12. Ora tutte le porte necessario per la realizzazione dell’Half-Adder sono pronte. E’ possibile procedere alla sua progettazione. 13. Selezionare dalla libreria la porta AND e cliccare sull’icona di inserimento Subckt nella barra degli strumenti in alto. Ciccare all’interno del foglio dove si vuole inserire la porta AND. Eventualmente spostare a piacimento il sottocircuito mediante l’icona . 14. Ora procedere al collegamento. Selezionare l’icona Draw Bus . Cliccare sull’input A, all’interno del cerchio, e tracciando delle linee ortogonali collegarsi al quadratino blu sulla parte alta della porta AND. Notare che non è possibile creare linee oblique, perciò non bisogna assolutamente cercare di collegare un input ad un subckt con una linea non ortogonale. In caso contrario, il collegamento viene effettuato, ma la linea, essendo obliqua, non viene visualizzata poiché non è riproducibile in un circuito. Ciò potrebbe dare origine ad errori in fase di scrittura del file blif. 15. Allo stesso modo creare il collegamento tra l’ingresso B e l’input del subckt AND. Viene visualizzata una finestra dove è possibile gestire e modificare il collegamento tra il bus e l’ingresso del subckt. Nel nostro della porta AND non vi è alcuna differenza tra input 1 e 2, perciò lasciare tutto invariato. 16. Collegare l’uscita della porta AND all’uscita CARRY. 17. Ripetere lo stesso procedimento per la porta XOR e collegarla all’uscita SUM. 18. La creazione dell’ Half-Adder è terminata. Procedere al salvataggio. Viene generato un file blif contenente tutte le informazioni riguardanti il progetto appena definito. Il file Blif generato è compatibile con SIS ma per sicurezza si consiglia di controllarlo manualmente visualizzandolo con un editor di testo. Le linee che iniziano con il carattere # sono commenti e vengono ignorate da SIS mentre sono essenziali per la riapertura del progetto tramite BVE, quindi non modificarle. Creazione di un circuito sequenziale con BVE: Semaforo con priorità Si consideri il classico esempio di un semaforo posto all’incrocio tra una strada principale (direttrice nord sud, NS) e una secondaria (direttrice est ovest, EO). Il semaforo può assumere solo i colori verde e rosso ed è dotato di sensori che rilevano la presenza di traffico. Il circuito che controlla il semaforo ha 2 segnali di ingresso forniti dai sensori (TRAFFICONS e TRAFFICOEO) e due di uscita (LUCENS e LUCEEO) con il seguente significato: - TRAFFICONS[1]: segnala la presenza di traffico lungo la direttrice NS assumendo il valore 1. - TRAFFICOEO[1]: segnala la presenza di traffico lungo la direttrice EO assumendo il valore 1. - LUCENS[1]: deve essere posto a 1 per accendere la luce verde sulla strada NS. Se viene posto a 0 si accende la luce rossa. - LUCEEO[1]: deve essere posto a 1 per accendere la luce verde sulla strada EO. Se viene posto a 0 si accende la luce rossa. Per evitare incidenti, il circuito di controllo deve garantire che le luci sulle strade NS e EO siano sempre accese in opposizione. Il circuito assegna priorità alla strada NS e commuta dal verde al rosso su NS solo se TRAFFICONS=0 e TRAFFICOEO=1, in caso contrario mantiene il verde su NS. In assenza di traffico sia su NS che su EO il semaforo non modifica la configurazione raggiunta. Non appena giunge traffico su NS, indipendentemente da cosa succede su EO, il semaforo assegna la luce verde a NS e la luce rossa a EO. Per realizzare il circuito usando BVE eseguire i seguenti passi: 1. Creare un nuovo progetto di tipo Finite State Machine. Nella prima finestra introdurre il nome del progetto: Semaforo, gli input: TRAFFICONS e TRAFFICOEO, e gli outputs: LUCENS e LUCEEO. Cliccando su Ok viene visualizzata la finestra con l’area di disegno. 2. Generare i due stati della FSM: quello dove la luce verde e assegnata alla direttrice NS (VERDENS) e quello dove il verde è assegnato alla direttrice EO (VERDEEO). Lo stato di reset è VERDENS. 3. Cliccare sull’icona rossa nella barra strumenti e cliccare sull’area di disegno. Viene visualizzato l’Object Inspector. Inserire come Label VERDENS e selezionare Set as Reset. Cliccare su Apply e poi su Close. 4. Ripetere la stessa procedura per creare lo stato VERDEEO, ma non selezionare Set as Reset. 5. Cliccare sull’icona a forma di freccia che si trova alla destra dell’icona Stato per inserire le transizioni. Cliccare sullo stato VERDENS e poi sullo stato VERDEEO per generare la relativa transizione tra i 2 stati. Si apre una finestra dove specificare gli input e gli output. Ricordando l’ordine compilare gli input e gli output di tale transizione. 6. Ripetere la procedura per tutte le transizioni della FSM fino ad ottenere quella completa. 7. Una volta terminato il disegno, salvare il progetto. Verrà generato un file blif perfettamente compatibile con SIS, salvo imperfezioni sintattiche da verificare manualmente. Esercizi Esercizio 1: Realizzare il circuito sequenziale (2 ingressi, 2 uscite) corrispondente alla seguente tabella degli stati. Sia A lo stato di reset. Minimizzare il numero degli stati e ottimizzare la logica combinatoria. Esercizio 2: Realizzare un circuito sequenziale con due ingressi binari in grado di riconoscere la sequenza 00 11 00 01. Si verifichi il comportamento del circuito durante il riconoscimento della sequenza 00 11 00 11 00 01. Esercizio 3: Su due linee vengono trasmessi serialmente dei numeri binari a partire dal bit meno significativo (un bit ogni colpo di clock). Si progetti un sommatore seriale in grado di fornire in uscita, per ogni colpo di clock relativo a ciascun bit trasmesso, il corrispondente bit di somma. Minimizzare il numero degli stati e ottimizzare la logica combinatoria. nei 2 casi: a) codifica manuale degli stati; b) codifica automatica degli stati.