Sintesi Combinatoria - Intranet...

Sintesi CombinatoriaSintesi CombinatoriaSintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli:

IntroduzioneIntroduzione

MariagiovannaMariagiovanna SamiSamiCorso di reti Logiche 8Corso di reti Logiche 8

Anno 2007Anno 2007--0808

20072007--0808 -- 22 --

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: IntroduzioneIntroduzione

Obiettivo della sintesi logica: ottimizzazione delle cifre di merito area e prestazioniPrestazioni: valutate di norma come il ritardo di propagazionelungo il percorso critico – semplificabile alla somma dei ritardi di propagazione delle porte logiche attraversate su tale percorso.

– Reti combinatorie a due livelli: si riducono contemporaneamente area e ritardo.

– Reti combinatorie a più livelli: area e ritardo non procedono nella stessa direzione

20072007--0808 -- 33 --


Le reti a più livelli portano in generale a soluzioni più efficienti in termini di area/prestazioni e consentono un utilizzo migliore delle librerie

area

ritardo

area

ritardo

due livellidue livelli più livellipiù livelli

20072007--0808 -- 44 --


Esempio: si supponga di utilizzare porte con un massimo di 3 ingressi (ritardo uniforme: τ): si parte dalla forma canonica

f(a,b,c,d)= a'c'+ad+b'cd‘(forma minima 2 livelli)

f(a,b,c,d)= a’b’c’d’+a’b’c’d+a’b’cd’+a’bc’d’+a’bc’d+ab’c’d+ ab’cd’+ab’cd+abc’d+abcd

Ritardo: 5 τ; Costo in letterali: 40

Ritardo: 2 τ; Costo in letterali: 7

20072007--0808 -- 55 --

Si veda ora un caso in cui si passa dalla forma canonica a una forma a più livelli. Si supponga ancora di disporre di porte con un massimo di 3 ingressi (ritardo uniforme: τ):

f= l’+ c’*g*h’+ a*b’*k’+ g*k’+ a’*b’*c’*d’*e’+ a*d’*e’*f’+e’*g’*i’+e’*j’;

In una soluzione banale, le due porte AND a cinque ingressi vengono realizzate come cascata di due AND a tre ingressi; l’OR a otto ingressi si realizza con tre OR in parallelo seguiti da un OR finale – il ritardo è 5τ, il costo in letterali è pari a 23.


Ritardo: 4 τ; Costo: 23

20072007--0808 -- 66 --

Si proceda ora a fattorizzare k’ fra i 3° e il 4° termine: si ottiene

f= l’+ c’*g*h’+ k’(a*b’+ g)+ a’*b’*c’*d’*e’+ a*d’*e’*f’+e’*g’*i’+e’*j’;

Il ritardo è ancora pari a 5 τ, il costo (in letterali) è sceso a 22.

Si applichi ancora la fattorizzazione – questa volta rispetto a e’, per i termini dal 4° all’ultimo. Si ottiene

f= l’+ c’*g*h’+ k’(a*b’+ g)+ e’*(a’*b’*c’*d’+ a*d’*f’+g’*i’+j’);

Il ritardo è salito a 6 τ, il costo è sceso a 19.


20072007--0808 -- 77 --

Infine, si applichi iterativamente la fattorizzazione entro la seconda parentesi, questa volta rispetto a d:

f= l’+ c’*g*h’+ k’*(a*b’+ g)+ e’*(d’*(a’*b’*c’+ a*f’)+g’*i’+j’);

Il ritardo è salito a 7 τ, il costo è sceso a 18. la curva che rappresenta costi e prestazioni per le varie soluzioni è la seguente


18

19

20

21

22

23

4 5 6 7ritardo

area

20072007--0808 -- 88 --


Nella realizzazione di reti combinatorie a più livelli, più che ricercare un ottimo (che non è sempre definibile in maniera univoca), si cerca una soluzione accettabile in termini di area e prestazioni.

Sarebbe più corretto parlare di sintesi invece che di ottimizzazione. La sintesi può prevedere:

– Minimizzazione dell'area (con vincolo sul ritardo)– Minimizzazione del ritardo (con vincolo sull'area)

20072007--0808 -- 99 --


Le operazioni e trasformazioni definite per la sintesi a più livelli hanno come scopo base quello di manipolare l’espressione logica della rete combinatoria in modo da individuare ed estrarre sotto-espressioni logiche comuni nell’espressione di partenza; questo consente, in generale, di avere realizzazioni più efficienti in termini di porte utilizzate (rispetto all’ottimizzazione a due livelli) con tempi di propagazione peggiori

20072007--0808 -- 1010 --


Ottimizzazione a più livelli:– Vantaggi:

• Più efficiente in termini di area e prestazioni.• Permette di utilizzare elementi di libreria.

– Svantaggi:• Maggiore complessità dell’ottimizzazione.

Metodi di ottimizzazione:– Esatti

• Complessità computazionale estremamente elevata: inaccettabili.

– Euristici• Definizione di euristica: “procedimento non rigoroso

(approssimativo, intuitivo) che permette di conseguire un risultato la cui qualità è paragonabile a quella ottenuta con metodi rigorosi”

20072007--0808 -- 1111 --

Euristica del problema di ottimizzazione - due passi:a) Si produce una soluzione ottimale (cioè sub-ottima)

ignorando i vincoli di realizzazione (Fan-in, fan-out, elementi di libreria…); la soluzione è ottenuta tramite sequenze di trasformazioni applicate in modo iterativo.

b) Si raffina il risultato considerando i vincoli strutturali (fan-in, fan-out, elementi di libreria..): è la fase di librarymapping (o library binding). Il risultato dell'ottimizzazione è di inferiore qualità rispetto ad una ottimizzazione che considera contemporaneamente i punti a) e b) ma risulta computazionalmente più semplice.


20072007--0808 -- 1212 --

Gli strumenti di CAD applicano tecniche euristiche basate sull’uso di logica booleana e – più in generale – di trasformazioni algebriche;

Le varie trasformazioni vengono applicate iterativamente fino a quando si raggiunge un valore predeterminato oppure fino a quando si verifica che non si ottengono ulteriori miglioramenti.

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: TrasformazioniTrasformazioni

20072007--0808 -- 1313 --

L’approccio tipicamente utilizzato è quello algoritmicoOgni trasformazione è associata ad un algoritmoL'algoritmo:

– determina dove può essere applicata la trasformazione;– applica la trasformazione e la mantiene se porta benefici; – termina quando nessuna trasformazione di quel tipo è ulteriormente

applicabile.

Il maggior vantaggio dell'approccio algoritmico è che trasformazioni di un dato tipo sono sistematicamente applicate alla rete.Algoritmi legati a differenti trasformazioni sono applicati in sequenza. Sfortunatamente differenti sequenze possono portare a soluzioni diverse.Si usano sequenze derivate da sperimentazioni.

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Approcci alla ottimizzazione Approcci alla ottimizzazione multimulti--livellolivello

20072007--0808 -- 1414 --

Si è visto qualche esempio di uso della fattorizzazione che permette di realizzare reti a più livelli che rispondano facilmente a vincoli quali il numero di ingressi per le porte logiche usate, la riduzione del numero di letterali, etc.;In genere, si pone il problema di scegliere rispetto a quale/quali variabili fattorizzare a ogni passo (= quali variabili raccogliere a fattor comune, e fra quali termini);Si ricorre a semplici criteri-guida:

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: uso della uso della fatorizzazionefatorizzazione

20072007--0808 -- 1515 --

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: FattorizzazioneFattorizzazione -- esempiesempi

Partendo da una forma iniziale (tipicamente, una forma a due livelli) si costruisce una tabella in cui

A ogni riga corrisponde uno dei termini prodotto (implicanti) presenti nella espressione;Per ogni variabile si introducono due colonne – una corrispondente alla forma naturale, una alla forma complementata;In ogni casella si scrive 1 se il letterale compare nell’implicante, 0 altrimenti

Nell’ultima riga della tabella, colonna per colonna, si inserisce la somma aritmetica dei termini della colonna – un semplice indicatore di quanto “sia presente” il letterale nei diversi implicanti.

20072007--0808 -- 1616 --


Esempio: si parta dall’espressione f= a*c*d+a’*b*c’+a’*b*d’+b’*c*d

Supponendo ancora di usare porte a 3 ingressi, il ritardo è pari a 3τ, il costo (in letterali) pari a 12. Si costruisce ora la tabella su introdotta:

a a’b b’c c’d d’a*c*d 1 0 0 0 1 0 1 0a’*b*c’ 0 1 1 0 0 1 0 0a’*b*d’ 0 1 1 0 0 0 0 1b’*c*d 0 0 0 1 1 0 1 0

1 2 2 1 2 1 2 1

Ritardo: 3τcosto: 12

20072007--0808 -- 1717 --


I letterali di maggior peso sono a’, b, c, d. Si nota inoltre che c e d compaiono nelle stesse righe; il termine cd è quindi un buon candidato per la fattorizzazione. Si estraggono due tabelle: una costituita dalle righe in cui compaiono sia c sia d (contrassegnate con i termini residui estraendo cd dai rispettivi implicanti) e dalle colonne relative alle variabili residue, l’altra “residua” costituita da tutte le righe restanti. La tabella completa (cioè la funzione) è la somma logica delle due.

20072007--0808 -- 1818 --


a a’b b’c c’d d’a*c*d 1 0 0 0 1 0 1 0a’*b*c’ 0 1 1 0 0 1 0 0a’*b*d’ 0 1 1 0 0 0 0 1b’*c*d 0 0 0 1 1 0 1 0

1 2 2 1 2 1 2 1

a a’b b’a 1 0 0 0 b’ 0 0 0 1

1 0 0 1

a a’b b’c c’d d’a’*b*c’ 0 1 1 0 0 1 0 0a’*b*d’ 0 1 1 0 0 0 0 1

0 2 2 0 0 1 0 1

Blocco della partizione indotta dal fattore comune dc

+

Blocco residuo della partizione

γ ξF = cd* γ + ξ

20072007--0808 -- 1919 --

Sintesi di reti combinatorie a più Sintesi di reti combinatorie a più livelli: livelli: FattorizzazioneFattorizzazione -- esempiesempi

Dalla tabella di sinistra non risultano ulteriori possibilità di fattorizzazione: la tabella corrisponde alla somma dei due termini prodotto che marcano le righe (quindi ad a+b’)La tabella di destra – sulla base degli stessi ragionamenti già usati – porta a un’ulteriore fattorizzazione rispetto al prodotto a’b. Anche in questo caso si estrae una tabella residua

a a’b b’c c’d d’a’*b*c’ 0 1 1 0 0 1 0 0a’*b*d’ 0 1 1 0 0 0 0 1

0 2 2 0 0 1 0 1Fattore comune a’b

c c’d d’c’ 0 1 0 0 d’ 0 0 0 1

0 1 0 1

++d’ c’

20072007--0808 -- 2020 --


Dalla sequenza di passi ora visti si ottiene la forma fattorizzata

f= d*c*(a+b’)+a’*b*(c’+d’)per un ritardo pari a 3τ e un costo di 8 letterali

20072007--0808 -- 2121 --


Esempio2: (forma 2 livelli non ottimizzata)

f = a*b*c*d+ a*b'*c'*d+ a'*b'*c*d+ a'*b'*c'*df = a*b*c*d+ a*b'*c'*d+ a'*b'*c*d+ a'*b'*c'*d

a a' b b' c c' d d'a*b*c*d 1 0 1 0 1 0 1 0a*b'*c'*d 1 0 0 1 0 1 1 0a'*b'*c*d 0 1 0 1 1 0 1 0a'*b'*c'*d 0 1 0 1 0 1 1 0

2 2 1 3 2 2 4 0

a a' b b' c c'a*b*c 1 0 1 0 1 0a*b'*c' 1 0 0 1 0 1a'*b'*c 0 1 0 1 1 0a'*b'*c' 0 1 0 1 0 1

2 2 1 3 2 2

Fattore comune d

+ a*b*ca a' c c'a*c' 1 0 0 1a'*c 0 1 1 0a'*c' 0 1 0 1

1 2 1 2


Blocco della partizione indotta dal fattore comune b'

a'*c

a a'a 1 0a' 0 1

1 1+

Blocco della partizione indotta dal fattore comune c'

a a'+ f = d*(a*b*c+b'*(a'*c+c'*(a+a')))f = d*(a*b*c+b'*(a'*c+c'*(a+a')))



20072007--0808 -- 2222 --

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: FattorizzazioneFattorizzazione –– esempiesempi

Esempio3: f= a*b*d'+ a'*b*d+ a'*b'*d'+ a'*c*d+ b'*c*d'f= a*b*d'+ a'*b*d+ a'*b'*d'+ a'*c*d+ b'*c*d'

a a' b b' c c' d d'a'*b*d 0 1 1 0 0 0 1 0a'*c*d 0 1 0 0 1 0 1 0a*b*d' 1 0 1 0 0 0 0 1a'*b'*d' 0 1 0 1 0 0 0 1b'*c*d' 0 0 0 1 1 0 0 1

1 3 2 2 2 0 2 3a a' b b' c c'a*b 1 0 1 0 0 0a'*b' 0 1 0 1 0 0b'*c 0 0 0 1 1 0

1 1 1 2 1 0

a a' b b' c c' d d'a'*b*d 0 1 1 0 0 0 1 0a'*c*d 0 1 0 0 1 0 1 0

0 2 1 0 1 0 2 0

b b' c c'b 1 0 0 0c 0 0 1 01 0 1 0

b+ca*b

a a' c c'a' 0 1 0 0c 0 0 1 0

0 1 1 0 a'+c f= d'*(a*b+b'*(a'+c))+a'*d*(b+c)f= d'*(a*b+b'*(a'+c))+a'*d*(b+c)

Blocco della partizione indotta dal fattore comune d'


+Blocco della partizione indotta dal fattore comune b'

+Fattore comune a'*d



20072007--0808 -- 2323 --

Sintesi di reti combinatorie a più Sintesi di reti combinatorie a più livelli: livelli: altre proprietàaltre proprietà

La fattorizzazione si realizza applicando solamente le proprietà distributiva e commutativa (oltre alle proprietà degli operatori – es., 1+x = x, x+x =x);Su una forma fattorizzata si può pensare di applicare poi ulteriori proprietà (in particolare, De Morgan) per giungere a soluzioni di costo ancor più ridotto in termini di porte logiche (non di letterali) grazie a condivisione di porte.Es.: si parta dalla forma canonica (che è anche minima)

F=a’b’c’d’+a’b’cd+a’bc’d+a’bcd’+abcd+abc’d’+ab’c’d+ab’cd’

20072007--0808 -- 2424 --


Il costo è di 8 porte AND a 4 ingressi e un OR a otto ingressi; in termini di letterali, il costo è pari a 32Fattorizzando si ottiene in un primo passo:F=a’b’(c’d’+cd)+ab(c’d’+cd)+a’b(c’d+cd’)+ab’(c’d+cd’)

E successivamenteF=(a’b’+ab)(c’d’+cd)+(a’b+ab’)(c’d+cd’)

cioè una forma a quattro livelli in cui compaiono solo porte a due ingressi; costo in porte logiche: 10 AND a due ingressi, 5 OR a due ingressi; costo in letterali: 16; ritardo: 4τ

20072007--0808 -- 2525 --


Osserviamo ora meglio la formaF=(a’b’+ab)(c’d’+cd)+(a’b+ab’)(c’d+cd’)

L’espressione x’y+xy’ costituisce il cosiddetto “OR esclusivo”, molto ampiamente usato nella si ntesidigitale (vale 1 se una o l’altra delle due variabili, ma non ambedue contemporaneamente, vale 1)L’espressione x’y’+x’y’ (detta a volte coincidenza, in quanto vale 1 se le due variabili hanno valori coincidenti) costituisce la complementazione dell’OR esclusivo. L’espressione si può quindi ulteriormente trasformare usando tali considerazioni:

20072007--0808 -- 2626 --


F=(a’b’+ab)(c’d’+cd)+(a’b+ab’)(c’d+cd’)=(a’b+ab’)(c’d+cd’)+((a’b’+ab))’((c’d’+cd))’

I due termini OR esclusivo (EXOR) vengono utilizzati ognuno due volte (una volta in forma naturale, una in forma negata), quindi l’effettivo costo in termini di porte diventa: 6 AND a 2 ingressi, 3 OR a due ingressi

20072007--0808 -- 2727 --


F=(a’b’+ab)(c’d’+cd)+(a’b+ab’)(c’d+cd’)=(a’b+ab’)(c’d+cd’)+((a’b’+ab))’((c’d’+cd))’a’

b

a

b’

c’

d

c

d’

Sintesi Combinatoria - Intranet...

Documents

Transcript of Sintesi Combinatoria - Intranet...