Progettazione DigitaleProgettazione DigitaleII EdizioneCapitolo 4: Ottimizzazione delle reti combinatorie

Testo di riferimentoFranco Fummi, Mariagiovanna Sami, Cristina SilvanoProgetta ione digitaleProgettazione digitaleMcGraw-Hill

T f i di i i i di d i dTrasformazione di un circuito in somma di prodotti a due livelli in un circuito a più livelli con sole porte a 2 ingressi

Rid i di i d d ll f i diRiduzione di area e ritardo dovuta alla trasformazione di due mintermini in un prodotto

Metodi di Ottimizzazione

I Metodi di Ottimizzazione possono essere l ifi ti i d t iclassificati in due macrocategorie:Metodi Esatti

Karnaugh Quine-McCluskeyQuine McCluskey

Euristiche

Tre tipologie di ottimizzazione circuiti combinatoricombinatori Circuiti a 2 livelli e 1 uscita: metodo esatto per

identificare i primi implicanti essenziali e unidentificare i primi implicanti essenziali e un metodo esatto o approssimato per identificare una copertura ottimauna copertura ottima.

Circuiti a 2 livelli e più uscite: metodo i t t l t ttiapprossimato per trovare la copertura ottima

basato sull’identificazione di implicanti primi i li di i i l itessenziali di ogni singola uscita.

Circuiti a più livelli e più uscite: numerosi metodi approssimati per esplorare diverse alternative di area e ritardo (i più efficaci sintesi ottima a 2 liv. di porzioni del circuito a 1 uscita. )

Relazione generale tra ottimizzazione di area e ritardo

T b ll d ll i à i bi d llTabella delle verità e rappresentazione cubica della funzione OR(a, b, c) descritta come f(B3) = B

Struttura delle mappe di Karnaugh per gli spazi B3 e B4

Mappa di Karnaugh della funzione OR(a, b, c)

Espansione del mintermine ā b c nel cubo b

Operazione di espansione effettuata a partire da ogni mintermine in tutte le direzioni per raggrupparne unmintermine in tutte le direzioni per raggrupparne un numero equivalente a una potenza di 2

Indicazione degli implicanti primi

Scelta dei implicanti primi e primi p p pessenziali…

Tabella delle verità di una funzione f(B4) B

Mappa di Karnaugh per la funzione del lucido 10

Criticità mappe Karnaugh

Impraticabili per f(Bn) con n>5 Non forniscono informazioni utili

all’identificazione di implicanti primi eall identificazione di implicanti primi e essenziali utili alla copertura di f()I li bili f i i iù it Inapplicabili a funzioni a più uscite

Rappresentano un metodo grafico e nonRappresentano un metodo grafico e non algoritmico

Metodo tabellare di Quine-McCluskeyMetodo tabellare di Quine-McCluskey

E’ una prima risposta per algoritmizzare un metodo di minimizzazione esatto

Il metodo si sviluppa per passi: Il metodo si sviluppa per passi:Riordino implicanti delle f() in base agli 1

Ri i id t iRicerca coincidenze e marcatura provenienza Iterazione ricerca coincidenze in tabella e

marcatura per ulteriori riduzioniTabella copertura minimap

Ri di d li i li i d ll f i d i l l idRiordino degli implicanti della funzione descritta nel lucido 10

Secondo e terzo passo dell’algoritmo di Quine-McCluskey

Tabella di copertura dell’algoritmo di Quine-McCluskey

Tabella di copertura dopo la cancellazione delle colonne essenziali

Tabella di copertura dopo la cancellazione delle colonne dominate

Esempio di tabella di copertura

Riduzione – Riduzione finale

Esempio di tabella di copertura

Tabella delle verità di una funzione non completamente specificata

Passi dell’algoritmo di Quine-McCluskey

Tabella di copertura della funzione del lucidoTabella di copertura della funzione del lucido 20

Mappe di Karnaugh di una funzione a due uscite

Prima realizzazione della funzione a due uscite

Realizzazione condivisa della funzione a due uscite

Realizzazione condivisa della funzione a due uscite

Realizzazione condivisa della funzione a due uscite

A li i d ll’ l i di Q i M Cl k llApplicazione dell’algoritmo di Quine-McCluskey alla funzione precedente

Tabella di copertura di una funzione a due uscite

Esempio di applicazione dell’algoritmo di Quine-McCluskey

Tabella di copertura della funzione a tre uscite precedente

T b ll di id d ll f i iTabella di copertura ridotta della funzione a tre uscite precedente

Mappa di Karnaugh di una funzione particolare

R t iù li lli h li l f iRete a più livelli che realizza la funzione precedente

Semplificazione pragmatica

COSTO

Costo di letterali CLCosto di letterali CLf=bc(a!d+!b+c)+!c(d+!a)(b+c) (i)f=b(!a+c+d) (ii)f=b(!a+c+d) (ii)

è pari al numero delle variabili indipendenti della funzione, ciascuna moltiplicata per il numero di volte che essa compare nella pforma. Per le reti bilaterali equivale al numero di contatti adoperatinumero di contatti adoperati

In base a tale definizione la forma (i) ha costo 11, mentre la (ii) ha costo 4

Costo di funzioni o di porte CPp Pf=bc(a!d+!b+c)+!c(d+!a)(b+c) (i)f=b(!a+c+d) (ii)f b(!a c d) (ii)

È pari al numero delle funzioni elementari fi che la compongono, che per reti unilaterali è uguale al numero complessivo g pdi porte adoperate

Secondo tale metrica il costo della (i) Secondo tale metrica il costo della (i) diviene 7 e di (ii) è 2

Costo di ingressi Cig if=bc(a!d+!b+c)+!c(d+!a)(b+c) (i)f=b(!a+c+d) (ii)f b(!a c d) (ii)

È pari al numero delle funzioni fi che la compongono ciascuna moltiplicata per lecompongono, ciascuna moltiplicata per le variabili (dipendenti o indipendenti) di cui è funzione Per reti unilaterali tale costofunzione. Per reti unilaterali tale costo equivale al numero complessivo di porte adoperate ciascuna pesata per il numero diadoperate, ciascuna pesata per il numero di ingressi (fan-in).

In tal caso la (i) ha costo 17 mentre la (ii) ha In tal caso la (i) ha costo 17 mentre la (ii) ha costo 5

Metodi esatti di minimizzazioneMetodi esatti di minimizzazione a 2 livelli Un processo di ottimizzazione logica a 2 livelli per

ottenere una soluzione ottima deve:ottenere una soluzione ottima deve:1. Individuare i mintermini della funzione in esame2. Individuare i primi implicanti relativi2. Individuare i primi implicanti relativi3. Utilizzare un processo di selezione per la scelta dei primi

implicanti

Tale metodo esatto è poco praticabile se la rete ha un numero elevato di variabili a causa dell’elevato numero di soluzione che occorre esaminaredi soluzione che occorre esaminare

Metodi di ottimizzazione

I metodi di ottimizzazione esatti nei casi ti i i l i li biliconcreti si rivelano inapplicabili:

Inapplicabili se il numero di variabili booleane di i / it è l tingresso/uscita è elevato

Complessità computazionale del problema di t t l t i tcopertura troppo elevata, in quanto

Dipende dal numero dei minterminiRi hi d l i di t tti li i li ti i i Richiede la generazione di tutti gli implicanti primi

Sviluppati nuovi algoritmi per risolvere il gproblema dell’ottimizzazione (ad es. Espresso II)Espresso II)

1. Non dipendono dal numero di mintermini2 Non richiedono la generazione di tutti i2. Non richiedono la generazione di tutti i

primi implicanti o3. non prevedono di di elencare i primi

implicanti alternativi per la loro selezionep p

Operazioni base di Espresso II

Expand Essential_Primes Irredundant Cover Irredundant_Cover Reduce Last_Gasp

Expand

Sostituisce ad ogni implicante della copertura F primi implicanti e garantisce che la copertura sia ridotta cioèimplicanti e garantisce che la copertura sia ridotta, cioè che non rimangano implicanti coperti da un solo singolo implicante. Si seleziona per primo l’implicante più grande p p p p p g(sottocubo area massima) tra quelli non ancora elaborati.

Fra i primi implicanti in cui può essere espanso si sceglie1. quello che copre il maggior numero di implicanti di F2. In caso di parità l’implicante più grande

Essential_Primes Seleziona fra i primi implicanti quelli essenziali I primi implicanti essenziali vengono I primi implicanti essenziali vengono

temporaneamente rimossi dallo spazio delle soluzionisoluzioni

I mintermini coperti dai primi implicanti essenziali rimossi sono trasformati in don’t careessenziali rimossi sono trasformati in don t care essendo certamente copertiL f i h i lt è i di t La nuova funzione che ne risulta è indicata con F-E

Irreduntant_Cover

Tale comando rimuove gli implicanti di F-E che sono complessivamente ridondanti cioè tutti quelli checomplessivamente ridondanti, cioè tutti quelli che possono essere rimossi senza lasciare mintermini non copertip

Successivamente la funzione effettua una selezione fra gli implicanti rimastig

ReduceLa procedura di reduce è usata per superare un minimo La procedura di reduce è usata per superare un minimo locale. Ogni implicante viene trasformato nel più piccolo implicante che garantisce la copertura di F E.implicante che garantisce la copertura di F-E.

Reduce viene eseguito sequenzialmente su ciascuno degli implicanti, per cui il risultato dipende dall’ordine di g p , p pin cui questi sono analizzati (la riduzione di un implicante modifica anche le celle coinvolte nella riduzione d ll’i li i )dell’implicante successivo).

Si sceglie implicante più grande Si ordinano gli implicanti restanti in base al più piccolo

numero di posizioni in cui l’implicante in esame differisce dall’implicante più grandedall implicante più grande

Last_Gasp

È una variante di Reduce seguita da una variante di Expand seguita da Irreduntant CoverExpand, seguita da Irreduntant_Cover.

La reduce riduce ogni singolo implicante nel più piccolo implicante possibile che ancora assicura la coperturaimplicante possibile che ancora assicura la copertura dell’ingresso. L’insieme derivato da tale riduzione sostituirà la copertura di partenza che non potrebbe coprire la funzione F-E. L’applicazione di Expand troverà tutti gli implicanti che coprono almeno due dei più piccoli i li ti ti T l i i di i li ti è iimplicanti generati. Tale insieme di implicanti, è prima combinato con la copertura utilizzata come ingresso a Last Gasp e quindi sottoposto a processo diLast_Gasp e quindi sottoposto a processo di Irredundant_Cover

Algoritmo Espresso

Utilizza metodi EuristiciNon assicurano la soluzione OTTIMA di un

problemaMa danno la possibilità di trovarne una in tempi

ragionevoli C Complessità computazionale contenuta

Come tutti i Problemi di ottimo, al presentarsi di una soluzione minima, deve verificare se il si tratta di un minimo locale, confrontandola con ulteriori soluzioni

Algoritmo Espresso

Parametri di Input:Leggi la funzione da ottimizzare F e la relativa

tabella (o mappa) di copertura iniziale costituita d ll’i i i i i l d i i t i idall’insieme iniziale dei mintermini

InizializzaC C Costo=Costo in termini di Porte di Ingresso di F

Algoritmo Espresso

Ciclo1:Esegui EXPANDSe sei alla prima iterazione

Esegui ESSENTIAL_PRIMESEsegui IRREDUNTANT_COVERSe costo non migliora

vai a OUT Altrimenti Aggiorna COSTO

Algoritmo Espresso Ciclo2:Esegui REDUCEEsegui REDUCEVai a Ciclo1

OUT: OUT:Esegui LAST_GASP

S t i liSe costo non migliora Vai a QUIT

QUIT: Inserisci gli implicanti primi essenziali in Fg p pFornisci F e Costo in output

Sostituisce ogniAlgoritmo Espresso

Sostituisce ogni implicante della copertura F con i li ti i i

Ciclo1:implicanti primi

E verifica che la copertura sia ridotta:

Esegui EXPANDSe sei alla prima iterazione

povvero che non vi siano implicanti coperti da un solo implicante

Esegui ESSENTIAL_PRIMESEsegui IRREDUNTANT_COVER

da un solo implicante

Se costo non migliora vai a OUT Altrimenti Aggiorna COSTO

Algoritmo EspressoAnalizza ogni implicante

Ciclo1:Analizza ogni implicante

per determinare se è un implicante primo

i lEsegui EXPANDSe sei alla prima iterazione

essenziale

Esegui ESSENTIAL_PRIMESEsegui IRREDUNTANT_COVERGli implicanti primi essenziali, in quanto necessari in tutte le

Se costo non migliora vai a OUT

soluzioni, vengono temporaneamente rimossi dallo spazio della soluzione

I i t i i ti d t li i li ti i i i li Altrimenti Aggiorna COSTOI mintermini coperti da tali implicanti primi essenziali, sono

trasformati, nello spazio delle soluzioni, in don’t care -

Rimuove gliAlgoritmo Espresso

Rimuove gli implicantiridondanti (che

Ciclo1:

(possono essere rimossi senza l iEsegui EXPAND

Se sei alla prima iterazione lasciare mintermini non coperti)

Esegui ESSENTIAL_PRIMESEsegui IRREDUNTANT_COVER

coperti)

Se costo non migliora vai a OUT Altrimenti Aggiorna COSTO

Questa funzione èAlgoritmo Espresso

Questa funzione è utilizzata per superare un

Ciclo2:Esegui REDUCE

minimo locale

Esegui REDUCEVai a Ciclo1

OUT:Ogni implicante è

trasformato nell’ OUT:Esegui LAST_GASP

S t i li

Implicante più piccolo che

Se costo non migliora Vai a QUIT

pancora assicura la copertura di F

QUIT: Inserisci gli implicanti primi essenziali in Fg p pFornisci F e Costo in output

Algoritmo EspressoQ t f i è

Ciclo2:Esegui REDUCE

Questa funzione è una variante di REDUCEseguita daEsegui REDUCE

Vai a Ciclo1 OUT:

seguita daIRREDUNTANT_COVER

(che rimuove gli implicanti OUT:Esegui LAST_GASP

S t i li

(c e uo e g p caridondanti)

Se costo non migliora Vai a QUIT

QUIT: Inserisci gli implicanti primi essenziali in Fg p pFornisci F e Costo in output

Reti multilivello

Semplificazione di circuitiSemplificazione di circuiti multilivello È basata sull’uso di un insieme di

trasformazioni che, applicate insieme alla valutazione del costo, portano , pall’identificazione di una soluzione che non è necessariamente quella ottimaè necessariamente quella ottima

Semplificazione di circuitiSemplificazione di circuiti multilivello (2)( ) Fattorizzazione

Consiste nel trovare una forma contenente fattori comuni Consiste nel trovare una forma contenente fattori comuni (letterali, prodotti, somme) per la funzione in esame, partendo dall’espressione in forma di somma di prodotti o prodotto di somme di funzione stessa. p

Di solito è usata la fattorizzazione algebrica, la quale non tiene conto degli assiomi specifici dell’algebra booleana, come quelli che coinvolgono il complemento e q g pl’idempotenza

Decomposizione Si esprime una funzione per mezzo di nuove opportune Si esprime una funzione per mezzo di nuove, opportune

funzioni

Semplificazione di circuitiSemplificazione di circuiti multilivello (3)( ) Estrazione

Si esprimono funzioni multiple per mezzo di nuove Si esprimono funzioni multiple per mezzo di nuove funzioni comuni

Sostituzione di una funzione G in una funzione F Consiste nell’esprimere F come funzione di G e di

alcune o tutte le variabili originali di F Eliminazione Eliminazione

È l’inverso della sostituzione, per cui la funzione Gche è contenuta in F viene sostituita con l’espressione di G. Tale trasformazione è anche detta appiattimento (flattening) o collassamento (collapsing)

G=a!ce + a!cf + a!de + a!df + bcd!e!fG a!ce + a!cf + a!de + a!df + bcd!e!fH=!abcd + abe + abf + bce + bcfcosto con porte (G)=28; costo(H)=27costo con porte (G)=28; costo(H)=27

Applicando la fattorizzazione si ha Applicando la fattorizzazione si haG=a!ce + a!cf + a!de + a!df + bcd!e!f==a(!ce + !cf + !de + !df) + bcd!e!f==a(!ce + !cf + !de + !df) + bcd!e!f==a(!c + !d)(e + f) + bcd!e!f Applicando decomposizione si ha Applicando decomposizione si haG=a(!c + !d)X2 + bX1!e!fX d X + fX1=cd; X2=e + fG=a!X1X2 + BX1!X2

G=a!ce + a!cf + a!de + a!df + bcd!e!fG=a!ce + a!cf + a!de + a!df + bcd!e!fH=!abcd + abe + abf + bce + bcf

Applicando l’estrazione si haH=b(!acd+ae+af+ce+cf) == b(!a(cd)+(a+c)(e+f) b(!a(cd) (a c)(e f)

PonendoX1=cd; X2=e+f; X3=a+cG=a!X1X2+bX1!X2H=b(!aX1+X3X2)

F3=AB+C(D+E) F3 AB+CD+CEF3=AB+CD+CEcosto letterali=5 per entrambi i circuiti;

t i i 8 ( ) 9 (b)costo ingressi=8 per (a) e 9 per (b)

G=ABCD +!A!B!C!D (i)G=ABCD +!A!B!C!D (i)G=(!A+B)(!B+C)(!C+D)(!D+A) (ii)( )( )( )( ) ( ) Costo letterali (i) e (ii) è pari a 8 ma la

forma (ii) occupa una maggiore area Costo ingressi è pari a 8+2=10 per (i) Costo ingressi è pari a 8+2 10 per (i) Costo ingressi è pari a 8+4=12 per (ii)

Modelli di rappresentazione diModelli di rappresentazione di una rete e trattamento algebricog

Modello di Rappresentazione

Una rete logica può essere rappresentata mediante un grafo orientato aciclico (DAG, directed acyclic graph) G(E,V) in cui:y g p ) ( , )

V è l’insieme dei vertici o nodi partizionati come Vi nodi di ingresso Vo nodi di uscitacome Vi nodi di ingresso, Vo nodi di uscita e Vg nodi interni a cui è associata una funzione scalare

E è l’insieme degli archi E è l insieme degli archi

DAG di una rete logica

Trasformazioni algebriche

Sweep Eliminazione Scomposizione Scomposizione Estrazione Semplificazione

Sostituzione Sostituzione

Trasformazioni Booleane

<inserire tabelle da fornaciari con proprietà algebra>

Esempio di eliminazione di un nodo

Rete logica di esempio

Rete dopo la decomposizione

Rete dopo l’estrazione della parte comune

Rete inserita in un contesto eRete inserita in un contesto e condizioni

Rete composta da moduli interagenti

Rete composta da moduli interagenti

Rete composta da moduli interagenti

Valori controllanti delle principali porte logiche

Valori controllanti delle principali porte logiche

Rete di esempio per il calcolo ODC

Esempio di rete per l’analisi dei ritardi

Esempio di rete per l’analisi dei ritardi

Esempio di rete per l’analisi dei ritardi

Esempio di rete per l’applicazione delle trasformazioniEsempio di rete per l applicazione delle trasformazioni

Esempio di rete per l’applicazione delle trasformazioni