Calcolatori Elettronici - Politecnico di Milano Fabio Salice Sintesi Combinatoria Sintesi di reti...

Fabio Salice Calcolatori Elettronici - Politecnico di Milano

Sintesi CombinatoriaSintesi Combinatoria

Sintesi di reti combinatorie a due livelli

Calcolatori Elettronici - Politecnico di Milano 2 Fabio Salice

Sintesi di reti combinatorie a due livelli: Sintesi di reti combinatorie a due livelli: IntroduzioneIntroduzione

• ObiettivoObiettivo:

ridurre la complessità di una (o più) funzione(i) booleana(e) espressa(e) in forma di Prodotto di Somme o di Somma di Prodotti (SOP). Ci si concentrerà solo sulla forma Somma Di Prodotti (l'altra ne è la duale).• Nella sintesi a due livelli gli obiettivi sono due:

• Riduzione del numero dei termini prodotto (principale)

• Riduzione del numero di letterali (secondario)

• Obiettivo della sintesi a più livelli: riduzione numero dei letterali


Sintesi di reti combinatorie a due livelli: Sintesi di reti combinatorie a due livelli: IntroduzioneIntroduzione

• metodologie di sintesi ottima:

Esatte• Karnaugh• Quine - Mc Cluskey

Euristiche per sintesi a due livelli


Sintesi di reti combinatorie a due livelli: Sintesi di reti combinatorie a due livelli: Metodi esattiMetodi esattimetodo di Karnaugh (cenni)metodo di Karnaugh (cenni)

• KarnaughKarnaugh• Si propone di identificare forme minime a due livelli.• La formula di riduzione da applicare è del tipo:

a B + a' B = (a+a') B = B

con B termine prodotto di n-1 variabili.• Metodo:

• individuazione degli implicanti primi e primi essenziali;– Implicante primo

» Termine prodotto associato ad un “raggruppamento” di dimensione massima.

– implicante primo essenziale» Implicante primo che copre uno o più 1 non coperti da nessun altro implicante primo.

• copertura.implicanti

implicanti primiimplicanti primi essenziali



• Esempio:

15,13,11,10,9,5,4,2,1,0),,,( dcbaf0 0 0 0 10 0 0 1 10 0 1 0 10 0 1 1 00 1 0 0 10 1 0 1 10 1 1 0 00 1 1 1 01 0 0 0 01 0 0 1 11 0 1 0 11 0 1 1 11 1 0 0 01 1 0 1 11 1 1 0 01 1 1 1 1

a b c d f

1 1 0 0

1 1 1 1

0 0 1 1

1 0 0 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

implicanti primi essenziali

implicanti primi essenzialia' c' ; a da' c' ; a dimplicanti primi

a' b' d' ; b' c d'b' c d' ; a b' c ; c' d

f(a,b,c,d) = a' c' + a d + b' c d'forma minima (unica)



• Nel caso di funzioni non completamente specificate, la generazione degli implicanti primi tratta le condizioni di indifferenza come 1.• condizioni di indifferenza (don't care) sono valori dell'uscita non specificate

dal problema• ad esempio, legate a configurazioni degli ingressi che non si presentano mai.

• Nella fase di copertura vengono considerati solo gli 1 (on-set della funzione) e non le condizioni di indifferenza (dc-set della funzione)



• Esempio

9,5,4,315,14,13,12,11,1),,,( DCONdcbaf 0 0 0 0 00 0 0 1 1

0 0 1 1 x0 1 0 0 x0 1 0 1 x0 1 1 0 00 1 1 1 01 0 0 0 01 0 0 1 x1 0 1 0 01 0 1 1 11 1 0 0 11 1 0 1 11 1 1 0 1

a b c d f

0 x 1 0

1 x 1 x

x 0 1 1

0 0 1 0

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

implicanti primi

0 0 1 0 0

1 1 1 1 1

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

b'd ; c'd ; c'b ; ab ; ad


Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi esatti Metodi esatti Quine - Mc CluskeyQuine - Mc Cluskey

• Metodo di minimizzazione tabellare• facilmente traducibile in un algoritmo.

• Due fasi:

1) Ricerca degli implicanti primi;

2) Ricerca della copertura ottima.


Prima Fase (ricerca degli implicanti primi)

• (nota: si fa riferimento alla forma SOP).

• Si applica sistematicamente la proprietà: a B + a’ B = B• Ad ogni passo della minimizzazione:

• si confrontano esaustivamente tutti i termini prodotto appartenenti all’ON-set;

• si operano le riduzioni su tutte quelle coppie che hanno una parte comune ed una sola variabile differente. I termini prodotto semplificati vengono marcati;

• si crea un nuovo insieme di termini prodotto da confrontare. • Il processo ha fine quando non sono più possibili delle riduzioni. I

termini non marcati sono implicanti primi.



• Per ridurre la complessità algoritmica, l'operazione di confronto viene svolta considerando solamente gli insiemi Si

j e Si+1J

• insieme Si j : insieme dei termini prodotto, all'iterazione j, con un numero

di 1 pari ad i.

• Le configurazioni adiacenti ad un termine prodotto appartenente a Sij

possono essere contenute solo in Si-1 j e Si+1

j.

• Per facilitare la costruzione della tabella di copertura (seconda fase):• Ad ogni termine prodotto è associata una etichetta che rappresenta

l'insieme dei mintermini che esso copre. L'etichetta di un nuovo termine prodotto è ottenuta per concatenamento delle etichette dei termini da cui proviene.




• Algoritmo di Quine - Mk Cluskey J=0J=0;

tutti i mintermini appartenenti all’ON-set vengono etichettati e posti nei loro rispettivi Si

0;

RipetiRipetiPerPer k=min(i) fino afino a (max(i) - 1)

confronta ogni configurazione in SiJ con ogni altra in Si+1

J . Le configurazioni semplificate vengono marcate ed il risultato della semplificazione viene etichettato e posto in Si

J+1.

J=J+1J=J+1;

Fino a cheFino a che non sono più possibili delle riduzioni

Tutte le configurazioni non marcate sono implicanti primi


15,14,13,12,11,9,1),,,( ONdcbaf

151111

141110

131101

111011

121100

91001

10001

04

03

02

01

S

S

S

S

15,14111

15,13111

15,11111

14,12011

13,12110

13,9011

11,9110

9,1001

13

12

11

S

S

S

15,14,13,1211

15,13,11,91122S

0 0 1 0

1 0 1 1

0 0 1 1

0 0 1 0

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

Equivalente mappa di Karnaugh

Implicanti Primi:P0(1,9): b' c' dP1(9,11,13,15): a dP2(12,13,14,15): a b


• Esempio:


Seconda Fase (ricerca della copertura ottima)

• Tabella degli implicanti (o tabella di copertura)É una matrice binaria A dove: • indici di riga: Implicanti primi trovati nella prima fase • indici di colonna: I mintermini appartenenti all’ON-set della funzione.

• elementi ai,j : a 1 quando l'implicante primo i_esimo copre il mintermine j_esimo, altrimenti 0.

• Il problema di copertura è intrattabile. Si utilizzano le proprietà di essenzialità e dominanza.



• Relazioni tra implicanti e mintermini che permettono la semplificazione della tabella:

• Essenzialità• Dominanza

• Dominanza di riga• Dominanza di colonna



• Righe Essenziali:• Descrizione:

• Se una colonna contiene un solo 1, la colonna corrisponde ad un prodotto fondamentale e la riga corrisponde ad un implicante primo essenziale.La riga è chiamata riga essenziale.

• Semplificazione:• La riga essenziale e le colonne da essa coperte (presenza di un 1) vengono

eliminate dalla tabella.


1 3 5 8 9 10 12 13 151 1 1 1

1 11 1

1 11 1 1 11 1 1 1

0

1

2

3

4

5

PPPPPP

Righe essenziali:P1 ; P2 ; P3

1 5 12 131 1 11 1 1 11 1 1

0

4

5

PPP


• Dominanza tra righe:• Descrizione:

• Un implicante i-esimo domina un implicante j-esimo quando Pi copre almeno tutti i mintermini coperti da Pj.

• Semplificazione:• Pj è eliminato dalla tabella.

• Ulteriori semplificazioni:• L'eliminazione per dominanza di una riga può generare dei nuovi implicanti

essenziali. Poiché questi ultimi divengono essenziali a causa delle semplificazioni, le righe ad essi associate sono chiamate righe essenziali secondarie.


1 5 12 13 151 11 1 1 1

1 11 1

0

1

2

3

PPPP

P0 : dominataP1 : dominante

1 5 12 13 151 1 1 1

1 11 1

1

2

3

PPP

P1: implicante essenziale secondario


• Dominanza tra colonne:• Descrizione:

• Un mintermine i-esimo domina un mintermine j-esimo quando ogni implicante che copre mj copre anche mi. (Può non valere l'opposto)

• Semplificazione:• mi è eliminato dalla tabella.

• Significato: un implicante che copre mj copre anche mi.

1 5 12 13 151 1

1 1 1 11 1 1 1

1 1

0

1

2

3

PPPP

1 12 131

1 11 1

1

0

1

2

3

PPPP



• Quando tutte le righe essenziali e le colonne e righe dominate sono rimosse, la tabella ottenuta, se esiste, è ridotta e ciclica.E' detta Tabella ciclica degli implicanti primi

Soluzione:a) Branch (esponenziale con la dimensione della tabella)

b) Metodo di Petrik.• Permette di risolvere il problema della scelta degli implicanti

quando la tabella degli implicanti è ciclica.



• Esempio del metodo di Petrik:

0 3 10 11 151 1

1 1 11 1

1 1 1

0

1

2

3

PPPP

(P0+P3) (P0+P1) (P1+P2) (P2+P3) (P1+P3) = 1

(P0+P3 P1) (P1P3+P2) (P1+P3) = 1(P0P2+P3 P1) (P1+P3) = 1

(P0P2P1+P0P2P3+P3 P1) = 1

Gruppi di implicanti primi: P0P2P1 ; P0P2P3 ; P3 P1

Da un prodotto di somme

ad una somma di prodotti



• Nel caso di funzioni non completamente specificate, la generazione degli implicanti primi tratta le condizioni di indifferenza come 1.

• A quanto visto in precedenza si aggiungono le seguenti regole:• Tutte le condizioni di indifferenza sono trattate come 1;• Nella tabella di copertura compaiono come indici di colonna solo i

mintermini appartenenti all’ON-set.

• Per evitare di considerare implicanti primi costituiti da sole condizioni di indifferenza è possibile attuare ulteriori regole: • Tutte le configurazioni in Si

0 relative alle condizioni di indifferenza sono marcate a priori e Tutte le configurazioni relative a raggruppamenti di sole condizioni di indifferenza sono marcate anche se non semplificate.

• (riduce il numero degli implicanti primi da considerare nella copertura);



• Esempio:

5,413,12,2,0),,,( DCONdcbaf

131101

121100

50101

40100

20010

00000

03

02

01

00

S

S

S

S

13,5101

12,4100

5,4010

4,0000

2,0000

12

11

10

S

S

S

13,12,5,41021 S

da sole condizioni di indifferenza

Implicanti primi:

P0 : a' b' d'P1 : a' c' d'P2 : b c'

0 2 12 131 11

1 1

0

1

2

PPP

f(a,b,c,d,)=a'b'd' + bc'



Espresso-Exact• Algoritmo implementato in Espresso per la minimizzazione

esatta.• I principi su cui si basa sono gli stessi della procedura di Quine-

Mc Cluskey (algoritmi utilizzati sono un po’ diversi).• Efficienza maggiore.

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi esatti Metodi esatti Espresso-ExactEspresso-Exact


• In Espresso-exact gli implicanti sono partizionati in tre insiemi:• Essenziali.• Totalmente ridondanti: sono quelli coperti da implicanti essenziali e dal

DC-set.• Parzialmente ridondanti: i rimanenti.

• Questo ultimo insieme è l'unico ad essere coinvolto nella fase di copertura.

• Una tabella di copertura ridotta è ottenuta ponendo come indici di riga i soli implicanti parzialmente ridondanti. Gli indici di colonna sono in corrispondenza uno a uno con l'insieme dei mintermini.

• La tabella è più compatta rispetto a quella ottenuta con Quine-Mc Cluskey e non ha colonne essenziali.

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi esatti Metodi esatti Espresso-ExactEspresso-Exact


• La minimizzazione esatta ha due problemi:• L'enorme numero di implicanti primi.

• Può essere dimostrato che il numero degli implicanti primi di una funzione logica di n ingressi può essere maggiore di 3n/n.

• L'intrattabilità del problema di copertura.• E’ un problema NP-completo.

• Soluzione:

Miglioramento iterativo della soluzione. Partendo da una condizione iniziale (specifiche della funzione) la copertura è modificata per cancellazione, aggiunta e modifica di implicanti fino a che non è raggiunta una condizione di minimalità (quando nessuna delle operazioni porta a successivi miglioramenti).

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi euristiciMetodi euristici


• I metodi euristici di minimizzazione differiscono per qualità della soluzione.• Qualità: Differenza in cardinalità tra la copertura minimale (euristica) e

quella minima (ottenuta con metodi esatti [quando possibile]).

• Le soluzioni di espresso Espresso coincidono spesso con quelle di Espresso-Exact (ma in tempi più brevi).• Procedura di minimizzazione:

• Ingresso: Lista degli implicanti (ON-set) ed il DC-set della funzione.

• Condizione iniziale:– La lista degli implicanti rappresenta la copertura iniziale della funzione.

• Sviluppo:– La copertura iniziale viene iterativamente manipolata da alcuni operatori.

• Termine:– L'operazione si conclude quando nessun operatore migliora la copertura.



• Gli operatori utilizzati da Espresso sono:

• Expand• espande i cubi rendendoli primi; la copertura risulta prima

• Reduce• riduce i cubi; la copertura risulta non prima ma della stessa

cardinalità di quella di partenza.

• Irredundant• elimina i cubi ridondanti; modifica la cardinalità della

copertura.



Expand• Gli implicanti relativi alla copertura sono rielaborati uno alla volta.

Ogni implicante è espanso a primo e tutti gli implicanti da esso coperti sono eliminati.

• L'operatore Expand rende la copertura prima e minimale. L'espansione di un implicante è realizzata aumentando il sotto cubo ad esso associato in una o più direzioni e verificando se l'espanso è ammissibile

• Verifica dell'ammissibilità dell'espansione:• Una espansione è ammissibile se l'implicante ottenuto non interseca

l’OFF-set. (E' richiesta la conoscenza dell’OFF-set e questo può essere pesante in termini di memoria utilizzata.)

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi euristiciMetodi euristiciEXPANDEXPAND


• Esempio:

0 0 1 1

0 0 x 0

1 1 1 0

0 0 x 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

Implicante da espandere: a c' d'

Espansione rispetto a c: a d'espansione ammissibile

Espansione rispetto ad a: c' d'espansione non ammissibile

Espansione rispetto a d: a c'espansione non ammissibile


OFF-Set : a’c’ + ab’d+a’cd’

Verifica ammissibilità:OFF-Set * (c’d’) = a’c’d’ 0 non ammissibile


• Esempio di espansione:

Copertura iniziale:on-set: {ac'd' , a'b'cd , bcd , ab'cd'} ; dc-set: {abc'd , abcd'}

Copertura iniziale

Copertura dopo Expand

ordine implicanti da espandere: (1) (2) (3)

0 0 1 1

0 0 x 0

1 1 1 0

0 0 x 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

E' coperto dall'espansione(1) ed è eliminato

Copertura finale:on-set: {ad' , a'cd , bcd } ; dc-set: {abc'd , abcd'}



• La qualità del risultato dipende da due fattori:

(a) Ordine degli implicanti da espandere;

(b) Ordine di espansione (direzione).• Si usano delle euristiche. La più semplice è la seguente:

• (b) ordine lessico-grafico• (a) Gli implicanti che hanno più probabilità di essere espansi sono per

analizzati primi.• Si utilizza la notazione positional-cube per codificare 0,1 e -:

– 0 10, 1 01, - 11 , non ammesso 00

• Ad ogni implicante è associato un peso.

• L'implicante con peso minore è quello che ha più probabilità di essere espanso e non coperto da altri.



• Esempio di ordinamento degli implicanti da espandere:

• Ogni peso è calcolato come Prodotto Interno del vettore conteggio per colonna con il vettore relativo all’implicante, espresso in notazione positional-cube.

• Es: |01 11 10 10| * |23 32 13 21|T = 11

Implicanti: ac’d’ 01 11 10 10 3+3+2+1+2=11 (2) a’b’cd 10 10 01 01 2+3+3+1=9 (1) bcd 11 01 01 01 2+3+2+3+1=11 (3) ab’cd’ 01 10 01 10 3+3+3+2=11 (4)

Ordineconteggio per colonna: 23 32 13 21

peso minore = più letterali, meno letterali condivisi più probabile sia espandibilepeso minore = più letterali, meno letterali condivisi più probabile sia espandibile



Reduce• Trasforma la copertura in un'altra non prima della stessa

cardinalità. Gli implicanti sono rielaborati uno alla volta; questa operazione può ridurre gli implicanti di dimensione.

• Condizione: Il nuovo insieme di implicanti deve essere una copertura per la funzione.

• La trasformazione di un implicante è attuata riducendo il sottocubo ad esso associato in una o più direzioni.

(nota: permette di uscire da minimi locali)

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi euristiciMetodi euristiciREDUCEREDUCE


• Una riduzione è ammissibile se l'implicante ridotto forma con i rimanenti una copertura per la funzione.

• La copertura non è prima ma mantiene la stessa cardinalità.• Sia un implicante appartenente alla copertura della funzione e

La riduzione massima di è

setdcsetonQ __

)'(~ Qsupercubo



• Esempio:

0 0 1 1

0 0 x 0

1 1 1 0

0 0 x 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

1 1

1 1 0 0

1 1 0 1

0 0 1 1

1 1 0 0

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

supercubo(Q')

0 0 1 1

0 0 1 0

1 1 0 0

0 0 1 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d

supercubo(Q)

0 0 1 1

0 0 x 0

1 1 1 0

0 0 x 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d



• Il risultato della riduzione dipende dall'ordine con il quale gli implicanti sono selezionati.La regola euristica di scelta: • Il primo implicante da ridurre è quello con peso maggiore (peso calcolato

come in Expand).

• Esempio:


Implicanti: ad’ 01 11 11 10 3+2+3+1+3+1=13 (1) bcd 11 01 01 01 1+3+3+3+2=12 (3) a’cd 01 11 01 01 3+2+3+3+2=13 (2)

Ordineconteggio per colonna: 13 23 13 12


Irredundant• Rende la copertura non ridondante. E' scelto un sottinsieme di

implicanti parzialmente ridondanti tale che ogni implicante non è interamente coperto da un altro dello stesso sottinsieme.• la copertura è divisa in tre insiemi

• relativamente essenziali

• parzialmente ridondanti

• totalmente ridondanti

Rispetto al metodo esatto, la copertura è costituita da implicanti non tutti necessariamente primi.

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi euristiciMetodi euristiciIRREDUNDANTIRREDUNDANT


• L'uscita di Espresso è:Una copertura non ridondanteSpesso di minima cardinalità.

• Algoritmo: Procedure • Complement: genera il complemento• Essentials: estrae gli implicanti essenziali• Last_gasp: modifica la copertura usando Expand e Reduce con euristiche

diverse.• Cost: calcola il costo della copertura

Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: Metodi euristiciMetodi euristiciESPRESSOESPRESSO


• (1982) ESPRESSO II è basato sulla applicazione di iterate espansioni e riduzioni . I passi seguiti da ESPRESSO II sono:

1. COMPLEMENT: Calcola l'OFF set.2. EXPAND: Espande gli implicanti portandoli a primi e rimuovendo quelli coperti.3. ESSENTIAL PRIMES: Estrae gli implicanti essenziali primi e li unisce al DC set.

4. EXPAND: Espande gli implicanti portandoli a primi e rimuovendo quelli coperti.5. IRREDUNDANT COVER: Trova la copertura minimale non ridondante.6. REDUCE: Riduce ogni implicante a un implicante essenziale minimo.7. Si iterano i passi 4,5,6 fino a che non si ottiene un miglioramento.

8. LASTGASP: applica per un'ultima volta REDUCE, EXPAND e IRREDUNDANT COVER usando una differente strategia. Se questa operazione ha successo viene continuata l'iterazione (passo 7).

9. MAKESPARSE: Rende la struttura della PLA sparsa; Per ridurre il numero dei transistor modifica il #1 e il #0 senza cambiare la copertura (aumenta la parte di ingresso riducendo quella di uscita di ogni implicante).



Espresso(on_set,dc_set)off_set=Complement(on_set U dc_set)on_set=Expand(on_set, off_set) /*copertura prima ridondante*/on_set=Irredundant(on_set, dc_set) essential_set=Essentials(on_set, dc_set)on_set=on_set - essential_set /* toglie 1 dall'on_set */dc_set=dc_set U essential_set /* e li aggiunge al dc_set */ripeti

2=Cost(on_set)ripeti

1=|on_set|on_set=Reduce(on_set,dc_set)on_set=Expand(on_set, off_set)on_set=Irredundant(on_set,dc_set)

fino a che (|on_set|< 1)on_set=Last_gasp(on_set,dc_set,off_set)

fino a che (Cost(on_set) < 2)on_set=on_set U essential_setdc_set=dc_set - essential_seton_set=Make_sparse(on_set,dc_set,off_set)



Sintesi di reti combinatorie a due livelli:Sintesi di reti combinatorie a due livelli: ESPRESSOESPRESSO

• Comando:• espresso [parametri] [file]

• Funzione:• minimizzazione di funzioni logiche a due livelli.

• Parametri:• -d: debugging

• -e[opzioni]: seleziona le opzioni di espresso:• fast, ness, nirr, nunwrap, onset, pos, strong, eat, eatdots, kiss, random

• -o[tipo]: seleziona il formato di uscita:• f, fd, fr, fdr, pleasure, eqntott, kiss, cons

• -s: fornisce un breve sommario relativo all’esecuzione;

• -t: fornisce un ampio sommario relativo all’esecuzione;

• -x: non visualizza la soluzione;



• Parametri (continua):• -v[typo]: messaggi di dettaglio (-v ‘’ per un accurato dettaglio)• -D[comando]: esegue il sotto-comando:

• ESPRESSO, many, exact, qm, single_output, so, so_both, simplify, echo, opo, opoall, pair, pairall, check, stats, verify, PLAverify, equiv, map, mapdc, fsm, contain, d1merge, d1merge_in, disjoint, dsharp, intersect, minterms, primes, separate, sharp, union, xor, essen, expand, gasp, irred, make_sparse, reduce, taut, super_gasp, lexsort, test

• -Sn: seleziona la strategia per il sotto comando (solo quelli riportati):• opo: bit2=esatto, bit1=ripetuto bit0=salta sparse• opoall: 0=minimizza, 1=esatto• pair: 0=algebrico, 1=strongd, 2=espresso, 3=esatto• pairall: 0=minimizza, 1=esatto, 2=opo• so_espresso: 0=minimize, 1=exact• so_both: 0=minimize, 1=exact



• Esempio:ipeca4>espresso -v '' ex3.plaEXPAND: 0011 1 (covered 0)EXPAND: 1-00 1 (covered 1)EXPAND: -111 1 (covered 0)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0ESSENTIAL: 0-11 1ESSENTIAL: 1--0 1REDUCE: -111 1 to 1111 1 0.00 secEXPAND: 1111 1 (covered 0)# IRRED: F=1 E=1 R=0 Rt=0 Rp=0 Rc=0 Final=1 Bound=0REDUCE_GASP: 11-- 1 reduced to 1111 1# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0.i 4.o 1.p 311-- 10-11 11--0 1.eipeca4>

ipeca4>espresso -v '' ex3.plaEXPAND: 0011 1 (covered 0)EXPAND: 1-00 1 (covered 1)EXPAND: -111 1 (covered 0)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0ESSENTIAL: 0-11 1ESSENTIAL: 1--0 1REDUCE: -111 1 to 1111 1 0.00 secEXPAND: 1111 1 (covered 0)# IRRED: F=1 E=1 R=0 Rt=0 Rp=0 Rc=0 Final=1 Bound=0REDUCE_GASP: 11-- 1 reduced to 1111 1# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0.i 4.o 1.p 311-- 10-11 11--0 1.eipeca4>

0 0 1 1

0 0 x 0

1 1 1 0

0 0 x 1

0 0 0 1 1 1 1 0

0 0

0 1

1 1

1 0

a bc d .i 4

.o 1

.type fd1-00 10011 1-111 11010 11101 -1110 -

.i 4

.o 1

.type fd1-00 10011 1-111 11010 11101 -1110 -

Cubi Notazione Pesi Ordine positional-cube 1-00 1 0 1 1 0 1 0 1 11 20011 0 1 0 1 1 0 1 0 10 1-111 1 1 1 0 1 0 1 0 12 41010 1 0 0 1 1 0 0 1 11 3 2 3 3 2 1 3 2 2

Cubi Notazione Pesi Ordine positional-cube 1-00 1 0 1 1 0 1 0 1 11 20011 0 1 0 1 1 0 1 0 10 1-111 1 1 1 0 1 0 1 0 12 41010 1 0 0 1 1 0 0 1 11 3 2 3 3 2 1 3 2 2

1-00-111

0011

1010



• Esempio:

.i 4

.o 3

.type fr00-1 1-101-- 0011000 0--1001 --11011 -1-1100 1111101 0001110 -101111 01-

EXPAND: 1100 100 (covered 2)EXPAND: 1011 010 (covered 3)EXPAND: 1111 010 (covered 0)EXPAND: 1100 001 (covered 0)EXPAND: 01-- 001 (covered 0)# IRRED: F=5 E=5 R=0 Rt=0 Rp=0 Rc=0 Final=5 Bound=0ESSENTIAL: 0--- 001REDUCE: -0-1 111 to -0-1 101 0.00 secREDUCE: 1-1- 010 to 1-11 010 0.00 secREDUCE: 1-00 011 to 1100 001 0.00 secEXPAND: 1100 001 (covered 0)EXPAND: 1-11 010 (covered 0)EXPAND: -0-1 101 (covered 0)# IRRED: F=4 E=4 R=0 Rt=0 Rp=0 Rc=0 Final=4 Bound=0REDUCE_GASP: 1-00 011 reduced to 1100 001REDUCE_GASP: 1-1- 010 reduced to 1111 010REDUCE_GASP: 11-0 110 reduced to 1100 100REDUCE_GASP: -0-1 111 reduced to -0-1 101EXPAND: 1100 111 (covered 0)# IRRED: F=5 E=2 R=3 Rt=0 Rp=3 Rc=1 Final=3 Bound=0REDUCE: -0-1 111 to -0-1 101 0.01 secEXPAND: -0-1 101 (covered 0)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0… (continua)

EXPAND: 1100 100 (covered 2)EXPAND: 1011 010 (covered 3)EXPAND: 1111 010 (covered 0)EXPAND: 1100 001 (covered 0)EXPAND: 01-- 001 (covered 0)# IRRED: F=5 E=5 R=0 Rt=0 Rp=0 Rc=0 Final=5 Bound=0ESSENTIAL: 0--- 001REDUCE: -0-1 111 to -0-1 101 0.00 secREDUCE: 1-1- 010 to 1-11 010 0.00 secREDUCE: 1-00 011 to 1100 001 0.00 secEXPAND: 1100 001 (covered 0)EXPAND: 1-11 010 (covered 0)EXPAND: -0-1 101 (covered 0)# IRRED: F=4 E=4 R=0 Rt=0 Rp=0 Rc=0 Final=4 Bound=0REDUCE_GASP: 1-00 011 reduced to 1100 001REDUCE_GASP: 1-1- 010 reduced to 1111 010REDUCE_GASP: 11-0 110 reduced to 1100 100REDUCE_GASP: -0-1 111 reduced to -0-1 101EXPAND: 1100 111 (covered 0)# IRRED: F=5 E=2 R=3 Rt=0 Rp=3 Rc=1 Final=3 Bound=0REDUCE: -0-1 111 to -0-1 101 0.01 secEXPAND: -0-1 101 (covered 0)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0… (continua)

… (continua)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0REDUCE_GASP: 1-1- 010 reduced to 111- 010REDUCE_GASP: 1100 111 reduced to 1100 111REDUCE_GASP: -0-1 111 reduced to -0-1 101# IRRED: F=2 E=2 R=0 Rt=0 Rp=0 Rc=0 Final=2 Bound=0# IRRED: F=3 E=2 R=1 Rt=1 Rp=0 Rc=0 Final=2 Bound=0# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0EXPAND: -0-1 101 (covered 0).i 4.o 3.p 41100 1111-1- 010-0-1 1010--- 001.e

… (continua)# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0REDUCE_GASP: 1-1- 010 reduced to 111- 010REDUCE_GASP: 1100 111 reduced to 1100 111REDUCE_GASP: -0-1 111 reduced to -0-1 101# IRRED: F=2 E=2 R=0 Rt=0 Rp=0 Rc=0 Final=2 Bound=0# IRRED: F=3 E=2 R=1 Rt=1 Rp=0 Rc=0 Final=2 Bound=0# IRRED: F=3 E=3 R=0 Rt=0 Rp=0 Rc=0 Final=3 Bound=0EXPAND: -0-1 101 (covered 0).i 4.o 3.p 41100 1111-1- 010-0-1 1010--- 001.e

Fabio Salice Calcolatori Elettronici - Politecnico di Milano

Sintesi CombinatoriaSintesi Combinatoria

Sintesi di reti combinatorie a più livelli


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

• Obiettivo (della sintesi combinatoria)• Ridurre Area-tempo.

• Reti combinatorie a due livelli: Area e tempo sono ridotti contemporaneamente.

• Reti combinatorie a più livelli: Area e tempo non procedono nella stessa direzione

area

ritardo

area

ritardo

due livelli più livelli



• Problemi da risolvere nella minimizzazione di reti combinatorie multi-livello:

Minimizzazione dell'area (con vincolo sul ritardo)

Minimizzazione del ritardo (con vincolo sull'area)



• Ottimizzazione a più livelli:• Vantaggi:

• Più efficiente in termini di area e prestazioni.

• Permette di utilizzare elementi di libreria.

• Svantaggi:• Maggiore complessità della ottimizzazione.

• Metodi di ottimizzazione:• Esatti

• Complessità computazionale estremamente elevata. • Euristici


• Euristica del problema di ottimizzazione:• Due passi:

• a) Si ignorano i vincoli di realizzazione (quali fan_in, fan_out, elementi di libreria...)

• b) Si raffina il risultato considerando i vincoli strutturali (library mapping).

• Risultato dell'ottimizzazione è di inferiore qualità rispetto ad una ottimizzazione che considera contemporaneamente i punti a) e b) ma risulta computazionalmente più semplice.

• Si analizzerà il solo punto a).



• Un circuito combinatorio è rappresentato mediante un grafo orientato aciclico (DAG - Direct Acyclic Graph).

• Grafo per reti combinatorie• È un grafo orientato G(V,E) aciclico

• V: insieme dei nodi

• E: insieme degli archi

• V è partizionato negli insiemi:• nodi di ingresso VI (Primary Inputs - PI)• nodi di uscita VO (Primary Outputs - PO)• nodi interni VG: Sono moduli della rete combinatoria a cui è associata una

funzione combinatoria scalare (una uscita)

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


• E' un modello comportamentale/strutturale• Strutturale: connessioni.• Comportamentale: ad ogni nodo è associata una funzione.

• Nel modello considerato, ogni funzione è a due livelli.

• Il modello è bipolare e non gerarchico• Bipolare: Ogni arco può assumere valore 0 o 1.

i1

i2

i3

a= i1 i2

c= i1 + i3

b= a i3 + i2

o2

d= b c o1

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


Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Trasformazioni per Trasformazioni per reti logichereti logiche

• Metodi euristici• Realizzano un miglioramento iterativo della rete logica mediante

trasformazioni logiche che conservano il comportamento di I/O.

• Due tipi di trasformazioni:• Locali

• Modificano localmente la funzione non toccando la struttura della rete.

• Globali• Modificano anche la struttura della rete (es. la cancellazione di un nodo)


• Le trasformazioni logiche modificano sia l'area che le prestazioni• Poiché modificano:

• numero dei letterali,• le funzioni locali,• le connessioni.

• Sono usate cifre di merito per valutare le trasformazioni• Trasformazioni non convenienti sono rifiutate.

• Le trasformazioni sono applicate in modo iterativo.• La rete è considerata ottimale rispetto ad un insieme di operatori

quando nessuno di questi la migliora.

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Trasformazioni per Trasformazioni per reti logichereti logiche


• L’approccio tipicamente utilizzato è quello algoritmico (Viene utilizzato in SIS)

• Consiste nel definire un algoritmo per ogni tipo di trasformazione.• L'algoritmo determina dove può essere applicata la trasformazione, attua

la trasformazione stessa e la mantiene se porta benefici e 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.

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Approcci alla Approcci alla ottimizzazione multi-livelloottimizzazione multi-livello


• Problema: differenti sequenze possono portare a differenti soluzioni.

• Soluzione: si usano regole frutto di sperimentazioni. • Esempio: per reti combinatorie è consigliato lo Rugged.script.

sweep; eliminate -1simplify -m nocompeliminate -1sweep; eliminate 5simplify -m nocompresub -afxresub -a; sweepeliminate -1; sweepfull_semplify -m nocomp

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Approcci alla Approcci alla ottimizzazione multi-livelloottimizzazione multi-livello


Sweep• Elimina, nella rete, tutti i vertici con un solo ingresso e quelli relativi a funzioni

costanti.

Simplify e Full_simplify• Semplificazione due livelli di ogni nodo.

• -m nocomp: non calcola l'off-set

Eliminate• Riduce la lunghezza del percorso I/O. La lunghezza è calcolata in numero di

nodi attraversati .• Riduzione vincolata (opzione Val_Intero) - es. eliminate 5

• L'eliminazione di un vertice è accettata se incrementa l'area di una quantità inferiore a Val_Intero dove l’incremento di area è calcolato come n*l -n -l dovel è numero di letterali del nodo eliminato mentre n è il numero di nodi che lo assorbono

• Riduzione non vincolata• tutti i nodi vengono collassati in un solo nodo: rete a due livelli.

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Trasformazioni e Trasformazioni e algoritmialgoritmi


• Esempio di eliminate 2:

• Eliminate -1

d=a+b+c

x=de+ef

y=df+de

x=(a+b+c)e+ef

y=(a+b+c)f+de

Costo: 3 + 4 + 4 = 11 Costo: 6 + 6 = 12

Osservano i dati relativi a n*l-n-l al variare di n e l si può constatare che l’effetto di eliminate -1 è quello di eliminare tutti i nodi composti da un solo letterale.


incremento di costo: 2*3 -2 -3 = 1

1 2 3 4 5 6 71 -1 -1 -1 -1 -1 -1 -12 -1 0 1 2 3 4 53 -1 1 3 5 7 9 11

l 4 -1 2 5 8 11 14 175 -1 3 7 11 15 19 236 -1 4 9 14 19 24 297 -1 5 11 17 23 29 358 -1 6 13 20 27 34 419 -1 7 15 23 31 39 47

n


• Le altre trasformazioni sono più complesse a causa dei gradi di libertà disponibili nella manipolazione di espressioni Booleane.

• Per semplificare la ricerca di trasformazioni utili, a prezzo della qualità del risultato, si utilizzano delle trasformazioni algebriche (algebra polinomiale) poiché sono un sottoinsieme delle trasformazioni Booleane.

• Espressioni algebriche:• Derivano dalle espressioni Booleane considerando i cubi (prodotti di

letterali) come monomi.• Letterali con diversa polarità sono da considerarsi variabili differenti (ad

esempio, a è differente da a’).

• Trasformazioni Algebriche:• Manipolazione delle espressioni mediante regole dell'algebra polinomiale



• Trasformazioni che utilizzano la manipolazione algebrica delle espressioni:

• SUBSTITUTION• sostituisce una sotto-espressione di un nodo mediante una variabile

(nodo) già presente nella rete.

• EXTRACTION• estrae un cubo (o una espressione multi_cubo) da un gruppo di nodi.

• DECOMPOSITION• decompone un nodo estraendo da quest’ultimo un gruppo di nodi.



Substitution• Sostituzione di una sotto-espressione mediante una variabile

(nodo) già presente nella rete. Ogni sostituzione è accettata se produce guadagno nel numero di letterali.

• Fa uso della divisione algebrica; si cerca di ridurre fi usando fj

fi=fdivisore fquoziente + fresto

fj=fdivisorefi=fj fquoziente + fresto

fj=fdivisore



Extraction• Si estrae un cubo (o una espressione multi_cubo) da gruppi di

nodi. L'estrazione viene fatta fino a che è possibile.• Identificazione di divisori comuni a 2 o più espressioni. Un divisore può

essere estratto e costituisce un nuovo nodo della rete che ha per successori i nodi da cui proviene.

• Vincoli:• n: ogni n iterazioni vengono ricalcolate tutte le possibili parti condivisibili• k: dimensione massima del multi_cubo.



• Esempio:

fi=fdivisore fquoziente_i + fresto_i

fj=fdivisore fquoziente_i + fresto_j

fi=fk fquoziente_i + fresto_i

fj=fk fquoziente_i + fresto_j

fk=fdivisore



Decomposition• Due obiettivi:

• Ridurre le dimensioni di una espressione a quelle accettabili da un generatore di celle

• Espressioni più piccole (possono essere più probabilmente divisori e quindi usabili da Substitute)

• La decomposizione associa una nuova variabile al divisore e riduce la funzione originale. La decomposizione può essere applicata ricorsivamente al divisore, quoziente e resto.



• Esempio:

fi=fd (fdq fqq + frq) + (fdr fqr+ frr)

fj=fq

fi=fj (fk fqq+frq) + fl fqr + frrfl=fdr

fk=fdq



• Punto fondamentale:

Divisione Algebrica• Definizione:

• una funzione fdivisore è un divisore algebrico di fdividendo quando fdividendo=fdivisore*fquoziente+fresto con fdivisore*fquoziente 0 e il supporto di fdivisore è disgiunto dal supporto di fquoziente (non condividono le stesse variabili).

• Supporti disgiunti• l'espressione ottenuta dal prodotto delle due espressioni a supporto

disgiunto è una espressione somma di prodotti booleana non ridondante.

• Esempio: (a + b) (a + c) = aa + ac + ba + bc espressione booleana non nella forma minima poiché aa = a. Si noti che {a,b}{a,c} = {a}.



• Esempio: siano dati un dividendo ed un divisore.

fresto = cde+bd+ef

fdividendo= ac+ab+cde+bd+ef fdivisore=c+b

A={ac,ab,cde,bd, ef} B={c,b}

divisione per c: Ac={a,de} divisione per b: Ab={a,d}

Q= Ac Ab={a} poiché i monomi sono elementi atomici

R= A - Q x B = A - {a} x {c,b} = {ac,ab,cde,bd,ef} - {ac, ab}= {cde,bd,ef}



Substitution• Data una espressione fi si vuole ridurne le dimensioni usando una

variabile j definita dalla equazione j=f j: fi= j fquoziente+fresto

• La ricerca dei sostitutori algebrici è fatta considerando tutte le coppie di espressioni presenti nella rete.

• La ricerca è ridotta considerando:• Filtri (condizioni di ammissibilità della divisione algebrica).

La divisione algebrica fi/ fj è vuota se:

• fj contiene variabili non presenti in fi

• fj contiene più termini di fi

• fj contiene almeno un monomio che ha più termini di ogni altro contenuto in f i

• Teorema: Il quoziente di una divisione algebrica tra due espressioni è vuoto se esiste un percorso che le collega.



Extraction• Estrazione di una sotto_espressione divisore comune di due o più

espressioni.• Estrazioni:

• Di un singolo cubo: monomio• Di una espressione multi_cubo: polinomio

• Importante: se il risultato della divisione per un monomio è ancora un monomio, il raccoglimento è banale (da scartare).

• Esempio: espressione: ace + bce• divisore a: quoziente ce. Da scartare • divisore b: quoziente be. Da scartare• divisore c: quoziente ae+be. E’ ulteriormente fattorizzabile da e.

divisore ce: quoziente a+b. E’ divisore!!



• Esempio (fattorizzazione monomica):

1) ae + be + cde 2) ad + ae + bd + be + bg

a: {d, e}b: {d, e, g}c: Ød: {a, b}e: {a ,b}1: {ad, ae, bd, be, bg}

a: {e}b: {e}c: {de}e: {a, b, cd}1: fattorizzabile per e

{a, b} {a, b}

k=a+bf1=ke+cdef2=ke+ad+bd+bg

k=a+bf1=ke+cdef2=kd+ae+be+bg

banali

Divisore Quoziente


Divisore Quoziente


• Estrazione di un cubo.• Il metodo precedentemente sviluppato porta ad ottenere un sotto insieme

delle soluzioni ammissibili (che può essere anche vuoto).

• Esempio:

• Poiché le funzioni da cui estrarre il cubo sono analizzate separatamente, non vengono considerate soluzioni che rappresentano dei raccoglimenti banali.Alcune delle soluzioni ammissibili possono essere escluse.

f=a’b+bc+abc’ ; g=ab’+a’bc+bcd

b: {a’, c, ac’} b: {a’c, cd} ; bc: {a’, d}

NON c’è soluzione comune (non banale - es.: a’)

bc potrebbe essere estratto da f e da g. . . . .




• Estrazione di un cubo.• Ogni coppia di funzioni fi e fk è raggruppata sotto una unica funzione

ausiliaria fi+fk di cui si calcolano i divisori.

• Il cubo che può essere estratto è il divisore di dimensione massima che ha intersezione non nulla con le due funzioni di partenza.

• Esempio:

Divisori:{b, ce}

faux= ace + bce + bg + cde + h

b : appartiene solo a f1. E' da scartarece: compare sia in f1 che in f2. Va bene!

f1=k(a+b) + bg

f2=kd + hK=ce

f1= ace + bce + bg

f2=cde + h


• Esempio:

f=a’b+bc+abc’ ; g=ab’+a’bc+bcd

faux=a’b+bc+abc’+ab’+a’bc+bcd

a: {bc’, b’}b: {a’, c, ac’, cd}c: {b, a’b, bd} cb: {1, a’, d}a’: {b, bc’} a’b: {1,c}

q=cbf=a’b+q+abc’g=ab’+q(a’+d)

a, b, cb, a’b sono divisoricomuni alle due funzioni.



• Estrazione di un multi_cubo.• Si cerca l'intersezione tra due elementi dell'insieme dei quozienti delle

funzioni.

• Esempio:

f1=ace + bce + de + g ; Quozienti(f1)={(ace+bce+de+g), (ac+bc+d), (a+b)}f2=ad + ae + bd + be + bg ; Quozienti(f2)={(ad+ae+bd+be+bg), (d+e), (d+e+g), (a+b)}

Quozienti(f1)={{xace,xbce,xde,xg}, {xac,xbc,xd}, {xa,xb}}Quozienti(f2)={{xad,xae,xbd,xbe,xbg}, {xd,xe}, {xd,xe,xg}, {xa,xb}}

Trasformazione in nuove variabili

faux=xace xbce xde xg+xac xbc xd+xa xb+xad xae xbd xbe xbg+xd xe+xd xe xg

Divisori:{xd,xe,xa xb,xd xe} si sceglie a+b poiché d+e non è in f1




• Comando:• print_kernel [-as] node-list

• Funzione:• Stampa i divisori ed i rispettivi quozienti di tutti i nodi specificati nella node-

list.

• Parametri:• -a: (default) stampa tutti i divisori ed i rispettivi quozienti.• -s: stampa solamente i sotto-quozienti.



• Comando:• gcx [-bcdf] [-t threshold]

• Funzione:• Estrae da una rete i cubi comuni e ri-descrive la rete stessa in termini di

questi cubi puntando alla riduzione del costo.

• Parametri:• -b: estrae, ad ogni passo, il miglior cubo che può essere estratto• -c: estrae il cubo o il suo complemento durante la fase di estrazione.• -f: il numero dei letterali è valutato sulle forme fattorizzate invece che sulla

somma-di-prodotti.• -t: i cubi utilizzati per la ristrutturazione della rete sono quelli con costo

superiore alla soglia. • -d: opzione di debbuging.



• Esempio di applicazione di gcx (X2.eqn) (costo finale: lit(sop)=70 lits(fac)=69)

INORDER = a b c d e f g h i j;OUTORDER = k l m n o p q;k = j + !i + !h;l = !j*!m + !h*!m + i;m = !h*!i*!j;n = y + m + j + h + c;o = i*j + !h + !g;p = c*o*!y*z + f*j*!z + d*!e*!k + !i*!j + !g;q = h*o*!p*!y + d*!k*!p + p*!z + !l + !g;y = b + a;z = !i + h;lits(SOP)=90 lits(FAC)=75

sis> gcx -dCube_extract: cube literal matrix is 35 by 17 col7 by 2 value=5 literals 854 by 3 value=5 literals 804 by 2 value=2 literals 783 by 3 value=3 literals 753 by 2 value=1 literals 744 by 2 value=2 literals 722 by 2 value=1 literals 712 by 3 value=1 literals 70

INORDER = a b c d e f g h i j;OUTORDER = k l m n o p q;k = !i*!j + f1 + e1 + d1 + b1;l = g1 + f1 + d1 + b1;m = c1;n = g1 + e1 + d1 + c1 + b1 + c + b + a;o = f1 + d1 + c1 + b1 + !g;p = h*b1*i1 + !h*!i*i1 + d*!e*g1 + !i*!j + h1 + !g;q = !a*!b*!c*h*j + d*e*i*g1 + h1 + e1 + c1 + !g;b1 = i*j;c1 = !h*!i*!j;d1 = !h*j;e1 = h*!i*j;f1 = !h*i;g1 = h*!j;h1 = f*!h*b1;i1 = !a*!b*c;lits(SOP)=70 lits(FAC)=69



• Comando:• gkx [-1abcdfo] [-t threshold]

• Funzione:• Estrae da una rete i multi_cubo divisori comuni e ri-descrive la rete stessa in

termini di questi cubi puntando alla riduzione del costo.• Parametri:

• -a: genera tutti i divisori per tutte le funzioni presenti nella rete. Per default, utilizza solamente i divisori di livello 0.

• -b: seleziona, ad ogni passo dell’algoritmo, il miglior divisore multi_cubo. • -c: prova ad utilizzare sia il nuovo fattore che il suo complemento.• -d: opzione di debugging.• -f: il numero dei letterali è valutato sulle forme fattorizzate.• -o: consente la sovrapposizione di fattori.• -t: i divisori sono estratti solo se il loro valore supera la soglia. Per default la

soglia è 0 cosicché tutti i possibili multi_cubo sono estratti dalla rete.• -1: l’algoritmo attraversa la rete una sola volta. Per default l’estrazione dei

quozienti è iterata fino a che ci sono divisori il cui valore supera la soglia.



• Esempio di applicazione di gkx (X2.eqn) (costo finale: lit(sop)=67 lits(fac)=64)



• Comando:• fx [-o] [-b limit] [-z]

• Funzione:• Dopo avere trovato tutti i miglior divisori di ogni nodo composti da un cubo

(monimiali) e da un un doppio cubo (binomiali), associa un costo ad ogni nodo ed estrae, iterativamente, il nodo con la miglior funzione di costo. (algoritmo tipo Greedy)

• Parametri:• -o: divisori binomiali di solo livello 0.

• -b: limite superiore di divisori generati (default: 50000).

• -z: utilizza anche i divisori di peso zero; sono estratti tutti i divisori che non danno una perdita di costo nella decomposizione della rete. La decomposizione potrebbe essere migliore ma richiede un ampio sforzo computazionale.



• Esempio di applicazione di fx (X2.eqn) (costo finale: lit(sop)=55 lits(fac)=54)



• Esempio di applicazione di fx -z (X2.eqn)


Decompose• Obiettivi:

1) Ridurre le dimensioni delle espressioni a quelle accettabili da un generatore di celle

2) Espressioni più piccole sono probabilmente dei divisori ed utilizzabili da Substitute.

k=a'+b t=kc+d q=te+g

q=a'ce+bce+de+g




• Comando:• decomp [-gqd] [node-list]

• Funzione:• Decompone tutti i nodi della lista; se la lista non è specificata tutti i nodi

della rete saranno decomposti. decomp fattorizza i nodi e introduce nella rete i divisori come nuovi nodi.

• Parametri:• -g: estrae in successione i divisori migliori (good).• -q: decomposizione rapida (quick); estrae di un divisore arbitrario.• -d: decomposizione disgiunta; i divisori estratti non condividono variabili.

• Algoritmo: partiziona i cubi in insiemi che hanno variabili di supporto non condivise, crea un nodo per ogni partizione ed un nodo che è l’OR di queste partizioni (es: k=h’j+i’+hj’ k=[1]+[2]; [1]=h’j+hj’; [2]=i’)



• Esempio di applicazione di decomp (X2.eqn)


• Modello:• Rete logica costituita da vertici a cui è associata una funzione booleana

locale ed un DC-set locale

• Problema:

Valutazione del DC-set

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Valutazione delValutazione delDC-set localeDC-set locale


• Condizioni di Indifferenza Esterne: sono relative all’interazione della funzione booleana con l’ambiente.

• Due aspetti:• Controllabilità

• Condizioni di indifferenza di ingresso (CDCin)– Insieme di configurazioni di ingresso mai fornite alla rete

• Osservabilità• Condizioni di indifferenza di uscita (ODCout)

– Insieme delle configurazioni di configurazioni di ingresso che produco uscite non osservabili dall’ambiente.

– E’ un vettore che ha tante componenti quante sono le uscite primarie (nout)



• Condizioni di indifferenza esterne

DCext= CDCin ODCout

• CDCin e’ un vettore di nout componenti pari a CDCin

• Esempio:x1

x2

ab

c

y1

y2

retecombinatoria

o1

o2

DCext=CDCin+ODCout=

CDCin: x1 x2 non assume mai la configurazione 01 CDCin= x1’x2

ODCout: per x1=0, y1 non è osservabile ODCout= per x2=0, y2 non è osservabile

x

x

1

2

'

'

x x x

x x x

1 2 1

1 2 2

' '

' '



• Esempio: calcolo del CDC di un nodo

x y

a

bc

x=a’+b ; y=abx + a’cx le variabili di supporto di ysono a, b, c, x.

0 0 0 00 0 1 01 1 1 00 0 0 0

00011101

cx ab

y può essere ulteriormente semplificata osservando che:

non è possibile che x a’+b (x non è una variabile indipendente)

quindi CDC= x(a’+b) = x’a’ + x’b + xab’- - - 00 0 1 -1 1 1-

-- - 0

00011101

cxab

00 01 11 01

y=ax + cx

Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Valutazione delValutazione delDC-set locale: CDCDC-set locale: CDC


Sintesi di reti combinatorie a più livelli: Sintesi di reti combinatorie a più livelli: Trasformazioni e Trasformazioni e algoritmi per la semplificazionealgoritmi per la semplificazione

• Comando:• simplify [-d] [-m method] [-f filter] [node-list]

• Funzione:• semplifica ogni nodo della rete utilizzando il metodo specificato e

generando l’opportuno DC-set. Il nodo è sostituito con la nuova funzione se quest’ultima ha meno letterali (nella forma fattorizzata)

• Parametri:• -m method: specifica il metodo da utilizzare nella minimizzazione

• snocomp (default): non calcola l’OFF-set completo;• nocomp: utilizza ESPRESSO; non calcola l’OFF-set completo;• dcsimp: minimizzatore tautology-based;• dctype: specifica come il DC-set è generato;

• -d: il DC-set non è utilizzato;• -f filter: specifica come il DC-set è filtrato

• exact: filtro esatto;• disjsup: usa il filtro basato sui supporti disgiunti;



• Esempio: INORDER = a b c;OUTORDER = y;x=!a+b;y=a*b*x + !a*c*x;



• Esempio:

.model CM82

.inputs a b c d e

.outputs f g h

.names a s f01 110 1.names o r g11 100 1.names o d e h01- 10-1 1-11 1.names a b c o00- 10-0 1-00 1.names d e r01 110 1.names b c s01 110 1.end

.model CM82

.inputs a b c d e

.outputs f g h

.names a s f01 110 1.names o r g11 100 1.names o d e h01- 10-1 1-11 1.names a b c o00- 10-0 1-00 1.names d e r01 110 1.names b c s01 110 1.end



• Comando:• full_simplify [-d] [-o ordering] [-m method] [-l] [-v verbose ]

• Funzione:• semplifica ogni nodo della rete utilizzando i DC locali.

• Parametri:• -m method: specifica il metodo da utilizzare nella minimizzazione

• snocomp (default): non calcola l’OFF-set completo;• nocomp: utilizza ESPRESSO; non calcola l’OFF-set completo;• dcsimp: minimizzatore tautology-based;

• -d: l’ODC-set non è calcolato;• -o ordering: ordinamento dei nodi della rete

• 0 (default): i nodi sono ordinati in base alla profondità;• 1: utilizza il livello del nodo;

• -v: informazioni per il debugging.


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

Script.algebraicsweepeliminate 5simplify -m nocomp -dresub -a

gkx -abt 30resub -a;sweepgcx -bt 30resub -a; sweep

gkx -abt 10resub -a;sweepgcx -bt 10resub -a;sweep

gkx -abresub -a; sweepgcx -bresub -a; sweep

eliminate 0decomp -g *

Script.boolean sweep; eliminate -1simplifyeliminate -1sweep; eliminate 5simplifyresub -agkx -abt 30resub -a; sweepgcx -bt 30resub -a; sweepgkx -abt 10resub -a; sweepgcx -bt 10resub -a; sweepgkx -abresub -a; sweepgcx -bresub -a; sweepeliminate 0decomp -g *eliminate -1; sweep

Script.rugged sweep; eliminate -1simplify -m nocompeliminate -1

sweep; eliminate 5simplify -m nocompresub -a

fxresub -a; sweep

eliminate -1; sweepfull_simplify -m nocomp

Calcolatori Elettronici - Politecnico di Milano Fabio Salice Sintesi Combinatoria Sintesi di reti...

Documents

Transcript of Calcolatori Elettronici - Politecnico di Milano Fabio Salice Sintesi Combinatoria Sintesi di reti...