Minimizzazione a più livelli di reti...

Minimizzazione a più livelli di reti combinatorie

Cristina Silvano

Università degli Studi di Milano Dipartimento di Scienze dell’Informazione

Milano (Italy)

Cristina Silvano - Università degli Studi di Milano 2

Sommario

• Modello booleano e modello algebrico

• Rappresentazione di reti logiche multi-livello.

• Metodi esatti ed approssimati.

• Ottimizzazioni basate su trasformazioni:

− Eliminazione

− Decomposizione

− Estrazione

− Semplificazione

− Sostituzione


Modelli di Rappresentazione

• Modello Booleano

• Modello Algebrico


Modello Booleano

• Sfrutta le proprietà della logica booleana.

• Utilizza le variabili complementate.

• Utilizza le condizioni di indifferenza (DC Conditions).

• Caratterizzato da elevata complessità computazionale.


Modello Algebrico

• Le funzioni sono viste come polinomi.

• Sfrutta le proprietà dell’algebra polinomiale, mentre non utilizza le proprietà della logica booleana. In particolare, vale la proprietà distributiva:

a ( b + c) = a b + a c

ma risulta:

a + (b c) ≠ (a + b) (a + c)

• Le variabili complementate sono viste come nuove variabili non correlate con le variabili non complementate ⇒ non si possono sfruttare le proprietà di assorbimento, idempotenza, involuzione, De Morgan e le identità:

a + a′ = 1, a a′ = 0.

• Le condizioni di indifferenza non sono utilizzate.

• Espressioni tipo somme di prodotti (cubi) vengono viste come polinomi (somme di monomi).

• Caratterizzato da semplicità e velocità.


Modello Booleano e Modello Algebrico

• Esempio di sostituzione Booleana:

h = a + b c d + e

q = a + c d

⇒ h = a + b q + e

poiché: a + b q + e = a + b ( a + c d) + e = a + b c d + e

• Esempio di sostituzione algebrica:

t = k a + k b + e

q = a + b

⇒ t = k q + e

poiché: k q + e = k ( a + b) + e = k a + k b + e


Divisione Algebrica

• Date due espressioni algebriche si ha che:

f quoziente = f dividendo / f divisore

quando sono soddisfatte le seguenti condizioni:

− f dividendo = f divisore f quoziente + f resto

− f divisore f quoziente ≠ 0

− il supporto di f divisore e di f quoziente è disgiunto:

supp (f divisore) ∩ supp(f quoziente) = Ø • Un divisore algebrico è detto fattore quando il resto della divisione è vuoto:

f dividendo = f divisore f quoziente


Esempio di Divisione Algebrica

• Date le due espressioni algebriche:

f dividendo = a c + a d + b c + b d + e

f divisore = a + b

⇒ f quoziente = c + d

f resto = e

poiché sono soddisfatte le seguenti condizioni:

− f dividendo = f divisore f quoziente + f resto essendo: f dividendo = (a + b ) (c + d) + e

− f divisore f quoziente ≠ 0

− il supporto di f divisore e di f quoziente è disgiunto:

{ a, b} ∩ { c, d} = Ø


Esempio di Divisione non Algebrica


f i = a + b c

f j = a + b

⇒ f j non è un divisore algebrico di f i perché la relazione:

− f i = f j f k con f k = a + c ⇒ f i = (a + b ) (a + c) vale in ambito Booleano ma non in ambito algebrico

− f i f k ≠ 0

Inoltre il supporto di f j e di f k non è disgiunto:

{ a, b} ∩ { a, c} ≠ Ø

⇒ f k non è il quoziente della divisione algebrica.


Modelli di Reti Logiche

• Il comportamento di un circuito combinatorio multi-livello a n-ingressi e m-uscite può essere espresso da una funzione booleana:

f: Bn → { 0, 1, -} m

• Tale funzione, che può essere non completamente specificata, rappresenta una corrispondenza esplicita tra lo spazio degli ingressi primari e lo spazio delle uscite primarie.

• La struttura di un circuito combinatorio multi-livello, in termini di interconnessione di porte logiche, può essere descritto da una rete logica.

• Una rete logica è una struttura che collega dei moduli (porte di I/O e porte logiche) attraverso reti di interconnessione.


Modelli di Reti Logiche (cont.)

• Una rete logica può essere rappresentata da un DAG (Directed Acyclic Graph) nel quale i vertici corrispondono ai moduli e i lati rappresentano reti a due terminali, nelle quali le reti originali a terminale multiplo sono state ridotte.

• Una rete logica i cui moduli interni corrispondano a porte logiche appartenenti ad una libreria viene chiamata rete logica mappata (bounded or mapped logic network).

• Il comportamento di un circuito può essere rappresentato attraverso strutture equivalenti. Al contrario, un unico comportamento può essere derivato dalla struttura di un circuito.


Esempio di Rete Logica

• Comportamento logico di I/O: x = ab y = c + ab

• Rete logica mappata:

c

q y

a

b

p x

• Grafo di rete logica:

va

vb

vc

vp

vq

vx

vy


Modelli di Reti Logiche

• Una rete logica non gerarchica rappresentata dal grafo Gn (V, E) è costituita da:

− Un insieme di vertici V partizionato in 3 sotto-insiemi:

V I vertici relativi a ingressi primari e ni = V I numero degli ingressi primari

V O vertici relativi a uscite primarie e no = V o numero delle uscite primarie

V G vertici interni e ng = V G numero dei vertici interni Ogni vertice è etichettato da una variabile.

− Un insieme di funzioni booleane combinatorie scalari associate ai vertici interni.

• Gli invertitori sono impliciti nel modello e non sono rappresentati. In pratica, ogni vertice può fornire segnali di entrambe le polarità ⇒ Rete logica a doppia polarità.


Rete Logica di Riferimento

• Variabili di ingresso primarie: { a, b, c, d, e}

• Variabili di uscita primarie: { w, x, y, z}

• Rete logica descritta dalle seguenti equazioni:

p = c e + d e q = a + b r = p + a′ s = r + b′ t = a c + a d + b c + b d + e u = q′ c + q c′ + q c v = a′ d + b d + c′ d + a e′ w = v x = s y = t z = u


Rappresentazione della Rete Logica di Riferimento

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b

t = ac + ad + bc + bd +e

s = r + b’

u = q’c + qc’ + qc

Costo associato alla rete logica di riferimento = (8 + 8 + 9 +8) letterali = 33 letterali


Grafo Associato alla Rete Logica di Riferimento

va

vb

vc

vv

vp

vq

vt

vr

ve

vd

vu

vs

vz

vy

vx

vw


Comportamento di I/O della Rete Logica di Riferimento

a′ d + b d + c′d + a e′

f = a′ + b′ + c e + d e

a c + a d + b c + b d + e

a + b + c


Ottimizzazione di Reti Logiche

• Gli obiettivi dell’ottimizzazione logica a due livelli e multi-livello sono differenti:

− Per logica a due livelli rappresentata come somma di prodotti ⇒ Area e ritardo sono proporzionali alla dimensione della copertura ⇒ Ottenere una copertura minima corrisponde ad ottimizzare sia area sia ritardo.

− Per logica multi-livello, implementazione ad area minima non corrisponde a implementazione a ritardo minimo e viceversa ad es. addizionatori ⇒ Compromesso tra area e ritardo.


Ottimizzazione di Reti Logiche (cont.)

• Spazio di valutazione progettuale per logica a due livelli e multi-livello.

area

ritardo

area

ritardo


Problema di Stima dell’Area

• L’area occupata da una rete logica multi-livello è proporzionale al numero di porte logiche e alle interconnessioni.

• Nel caso di rete logica mappata su libreria di celle (bounded network), l’area di ogni singola porta logica è nota.

• Altrimenti l’area è stimata in base al numero di porte logiche equivalenti (NAND2) che implementano la corrispondente funzionalità logica e al numero di letterali.


Problema di Stima del Ritardo

• Ritardo proporzionale al numero di livelli logici e alle interconnessioni.

• Nel caso di bounded network, il ritardo di ogni singola porta logica è specificato.

• Altrimenti il ritardo è stimato in base al ritardo associato ad ogni vertice (ad es. ritardo unitario per ogni vertice).

• Modelli di ritardo più sofisticati tengono conto del fan-out e delle interconnessioni associati ai vertici.

• Ottimizzazione in timing = Ridurre il ritardo associato al percorso più lungo detto percorso critico.


Problema dell’Ottimizzazione Multi-Livello

• Metodi esatti:

− Elevata complessità computazionale.

− Non applicabili ai casi reali.

• Metodi approssimati:

− Metodi euristici basati sull’applicazione iterativa di trasformazioni che preservano il comportamento di I/O.

− L’esecuzione di trasformazioni in qualunque sequenza salvaguarda l’equivalenza della rete logica.

− Metodi che differiscono per: Tipo delle trasformazioni. Selezione e ordine delle trasformazioni.


Ottimizzazione Multi-Livello

• Problema della sintesi multi-livello: trovare un’appropriata sequenza di trasformazioni da applicare alla rete logica.

• Una rete logica viene dichiarata ottima in area e ritardo rispetto ad un insieme di trasformazioni quando l’aplicazione di queste non può più migliorare la funzione di costo.


Trasformazioni

• Eliminazione

• Decomposizione

• Estrazione

• Semplificazione

• Sostituzione


Eliminazione

• Eliminazione di una funzione associata ad un vertice interno della rete logica che viene sostituita dalla corrispondente espressione.

• In pratica corrisponde all’eliminazione di un livello logico relativo ad una funzione semplice e all’aggregazione ad altre funzioni.

• Esempio: Eliminazione di vr dove r = p + a′ e sostituzione della corrispondente espressione in s = r + b′

⇒ s = p + a′ + b′


Eliminazione (cont.)

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b


s = r + b’

u = q’c + qc’ + qc


Eliminazione (cont.)

a

e

d

c

b

z

y

x

wv = a’ d + b d + a’ c + a e’

p = c e + d e

q = a + b


s = p + a’ + b’

u = q’c + qc’ + qc


Decomposizione

• Decomposizione della funzione associata ad un vertice interno della rete logica che viene fattorizzata introducendo uno o più vertici nuovi che formano una sotto-rete equivalente al vertice originale.

• In pratica vengono introdotti uno o più livelli logici che corrispondono ad una funzione complessa.

• Esempio: Decomposizione di vv dove v = a′ d + b d + c′ d + a e′ viene fattorizzato pre-calcolando l’espressione (a′ + b + c′ ) nel nuovo vertice vj: j = a′ + b + c′

⇒ v = j d + a e′


Esempio di Decomposizione


f v = a′ d + b d + c′ d + a e′ f j = a′ + b + c′ la divisione algebrica f v / f j ha quoziente f quoziente = d e resto f resto = a e′ ⇒ f v = j d + a e′


Decomposizione (cont.)

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b


s = r + b’

u = q’c + qc’ + qc


Decomposizione (cont.)

a

e

d

c

b

z

y

x

w

r = p + a’p = c e + d e

q = a + b

t = ac + ad + bc + bd + e

s = r + b’

u = q’c + qc’ + qc

v = j d + a e’j = a’ + b + c’


Estrazione

• Estrazione di una sotto-espressione comune a due o più funzioni e introduzione di un nuovo vertice comune associato alla sotto-espressione.

• In pratica il nuovo vertice introdotto permette di semplificare la rappresentazione di due o più funzioni complesse sfruttando una sotto-espressione comune.

• Esempio: Estrazione della sotto-espressione comune (c + d) da p = c e + d e e da t = a c + a d + b c + b d + e fattorizzati come:

p = (c + d) e

t = (c + d) (a + b) + e

Vengono creati il nuovo vertice comune vk e la variabile k associata all’espressione comune estratta: k = c + d

⇒ p = k e

⇒ t = k a + k b + e


Esempio di Estrazione

• Le due espressioni algebriche:

f p = c e + d e

f t = a c+ a d + b c + b d + e

possono essere semplificate estraendo il divisore comune f k = c + d associato alla variabile k = f k

⇒ f p e f t possono essere sostituite da : (k f quoziente + f resto)

f p = k e

f t = k ( a + b) + e


Estrazione (cont.)

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b


s = r + b’

u = q’c + qc’ + qc


Estrazione (cont.)

p = k e

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

q = a + b

t = k a + k b + e

s = r + b’

u = q’ c + q c’ + q c

k = c + d


Semplificazione

• Semplificazione della complessità di una funzione sfruttando le proprietà della rappresentazione (cioè le proprietà dell’algebra Booleana o le proprietà dell’algebra polinomiale).

• In particolare, se la funzione è rappresentata in forma a due livelli ⇒ Possono essere applicate tecniche di ottimizzazione a due livelli.

• Se il supporto della funzione non cambia ⇒ La trasformazione è locale. Altrimenti è globale e corrisponde a cancellare una o più dipendenze da variabili.

• Esempio: Semplificazione booleana della funzione u = q′ c + q c′ + q c

⇒ u = q + c

Trasformazione locale perché non impatta il supporto della funzione.


Semplificazione (cont.)

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b


s = r + b’

u = q’c + qc’ + qc


Semplificazione (cont.)

u = q + c

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

p = c e + d e

q = a + b


s = r + b’


Sostituzione

• Semplificazione di una funzione locale che viene fattorizzata usando un ingresso addizionale non appartenente al supporto della funzione.

• In pratica richiede la creazione di una dipendenza da un vertice pre-esistente non appartenente al supporto della funzione.

• Esempio: Si consideri il vertice vt della rete di riferimento dopo aver effettuato l’estrazione:

t = k a + k b + e

La sotto-espressione (a+ b) è pre-calcolata nel vertice vq pre-esistente e non appartenente al supporto di t. ⇒ La funzione associata a vt può essere riscritta come:

t = k q + e dove q = a + b

Ciò richiede l’aggiunta della dipendenza di vt da vq.

• La sostituzione è un’applicazione diretta della divisione algebrica.


Esempio di Sostituzione


f t = k a + k b + e

f q = a + b

la divisione algebrica f t / f q ha quoziente f quoziente = k e resto f resto = e

⇒ f t = k q + e


Sostituzione (cont.)

p = k e

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

q = a + b

t = k a + k b + e

s = r + b’

u = q’ c + q c’ + q c

k = c + d


Sostituzione (cont.)

p = k e

a

e

d

c

b

z

y

x

w

r = p + a’

v = a’ d + b d + c’ d + a e’

q = a + b

t = k q + e

s = r + b’

u = q’c + qc’ + qc

k = c + d


Risultato delle Trasformazioni Algebriche

a

e

d

c

b

z

y

x

w j = a’ + b + c’ v = j d + a e’

q = a + b

t = k q + e

s = k e + a’ + b’

u = q ‘ c + q c’ + q c

k = c + d

• Oltre alle trasformazioni algebriche applicate sinora, è stata applicata l’eliminazione del vertice p.

Costo associato alla rete logica ottimizzata = (7 + 4 + 5 +8) letterali = 24 letterali


Risultato delle Trasformazioni Algebriche

j = a′ + b + c′ k = c + d

q = a + b

s = k e + a′ + b′ t = k q + e

u = q’ c + q c’ + q c

v = j d + a e′ w = v

x = s

y = t

z = u

• Rispetto alla rete logica di riferimento il numero totale dei letterali è stato ridotto da 33 a 24 ⇒ Riduzione dell’area stimata.


Esercizio 1:

• Utilizzando il modello algebrico, si consideri la rete logica definita dalle seguenti espressioni :

p = a d’ + a’ b’ + a’ d’ + b c + b d’ + a c

q = a + b

r = a’ c’ + a’ d’ + b’ c’ + b’ d’ + e

s = a’ c + a’ d + b’ d + e’

x = p

y = q

z = r

u = s

Siano {a, b, c, d, e} gli ingressi e {x, y, z, u} le uscite.


Esercizio 1 (cont.):

• Si disegni il grafo associato alla rete logica e si calcoli il costo associato in termini di letterali.

• Si esegua la sostituzione di q in p e si ridisegni il grafo.

• Si esegua una decomposizione di p introducendo un nuovo vertice j e si ridisegni il grafo.

• Si esegua l’estrazione di una sotto-espressione k comune a r e s e si ridisegni il grafo.

• Si calcoli il costo associato alla rete logica ottimizzata in termini di letterali.


Esercizio 2:


p = a b + a’ b’ + a d + b c’ + c’ d + b’ c’ e

q = a + c’

r = a’ b’ + a’ d’ + b’ c’ + c’ d’ + a c’

s = a b + b c + a’ d e + c’ d e

x = p

y = q

z = r

u = s

Siano {a, b, c, d, e} gli ingressi e {x, y, z, u} le uscite.




• Si esegua la sostituzione di q in p e si ridisegni il grafo.

• Si esegua una decomposizione di p introducendo un nuovo vertice j e si ridisegni il grafo.

• Si esegua l’estrazione di una sotto-espressione k comune a r e s e si ridisegni il grafo.

• Si esegua una decomposizione di s introducendo un nuovo vertice l e si ridisegni il grafo.

• Si calcoli il costo associato alla rete logica ottimizzata in termini di letterali


Esercizio 3:


p = a c + a d + b´c + b´ d + e

q = e b´ + e a

r = c + d

s = q + a´ b

t = a´ b + a´ e + c b + d´ b + c´ e

u = s + a c

x = p

y = q

z = t

w = u

Siano {a, b, c, d, e} gli ingressi e {x, y, z, w} le uscite.




• Si esegua l’estrazione di una sotto-espressione k comune a p e q e si ridisegni il grafo.

• Si esegua la sostituzione di r in p e si ridisegni il grafo.

• Si esegua l'eliminazione di s e si ridisegni il grafo.

• Si esegua una decomposizione di t introducendo due nuovi vertici (i, j) e si ridisegni il grafo.

• Si calcoli il costo associato alla rete logica ottimizzata in termini di letterali.

Minimizzazione a più livelli di reti...

Documents

Transcript of Minimizzazione a più livelli di reti...