Riprendiamo la funzione riportata in Tabella 4.1 e

Ottimizzazione delle reti combinatorie 99
Riprendiamo la funzione riportata in Tabella 4.1 e descriviamola in formato .blif.
Poiché la funzione è completamente specificata, si ricorda che è sufficiente descrivere
solamente l’On-set: i mintermini non elencati apparterranno all’Off-set. La funzione
di Tabella 4.1 è quindi descritta nel seguente modo:
.model COMPSPEC
.inputs x y z v
.outputs f
.names x y z v f
0001 1
0100 1
0101 1
0110 1
0111 1
1001 1
1011 1
1110 1
1111 1
.end
nodes= 1
latches= 0
Il suo caricamento in SIS e la stampa delle statistiche producono il seguente risultato:
po= 1
sis> read_blif compspec.blif
sis> print_stats
COMPSPEC
pi= 4
lits(sop)= 36
nodes= 1
latches= 0
Il modello ha un costo di 36 letterali poiché è descritto da 9 mintermini da 4 variabili.
La minimizzazione esatta a due livelli (comando full_simplify) produce il
seguente risultato:
sis> full_simplify
sis> print_stats
compspec
pi= 4 po= 1
lits(sop)= 10
sis> write_blif
.model compspec
.inputs x y z v
.outputs f
.names x y z v f
01-- 1
-11- 1
1-11 1
-001 1
.end
La funzione è ora descritta con quattro prodotti il cui costo è sceso a 10 letterali. Per
facilitare la lettura di questi prodotti, è possibile stamparli come equazioni:
100 Capitolo 4
sis> write_eqn
INORDER = x y z v;
OUTORDER = f;
f = !y*!z*v + x*z*v + y*z + !x*y;
Queste equazioni concordano quasi completamente con il risultato ottenuto
manualmente (f = y z v + x y v + yz + x y) e riportato in Tabella 4.5 e
Tabella 4.6. La differenza riguarda l’implicante primo D (1−11, xzv) che è stato
selezionato invece dell’implicante C (10−1, x y v). Il loro costo in termini di letterali
è però identico quindi la loro scelta in fase di copertura è indifferente.
Nel caso di funzioni parzialmente specificate, l’unica differenza consiste nella
scrittura del DC-set. Il DC-set viene descritto come l’On-set, ma viene identificato
perché è posto dopo la parola chiave .exdc. Per esempio, la funzione parzialmente
specificata di Tabella 4.11 è descritta in formato .blif nel seguente modo:
.model parspec
.inputs x y z v
.outputs f
.names x y z v f
0100 1
1010 1
1011 1
1101 1
1110 1
1111 1
.exdc
.inputs x y z v
.outputs f
.names x y z v f
0011 1
0101 1
0110 1
0111 1
.end
latches= 0
latches= 0
I mintermini per cui la funzione è don’t care sono riportati dopo la parola chiave
.exdc e completano l’On-set della funzione descritto come in precedenza.
L’esecuzione del comando full_simplify produce il seguente risultato:
sis> read_blif parspec.blif
sis> print_stats
parspec
pi= 4 po= 1 nodes= 1
lits(sop)= 24
sis> full_simplify
sis> print_stats
parspec
pi= 4 po= 1 nodes= 1
lits(sop)= 6
Ottimizzazione delle reti combinatorie 101
102 Capitolo 4
sis> write_eqn
INORDER = x y z v;
OUTORDER = f;
f = y*v + x*z + !x*y;
4.3 Minimizzazione a due livelli di reti combinatorie a più
uscite
Don’t care:
INORDER = x y z v;
OUTORDER = f;
f = !x*y*z*!v + !x*y*!z*v + !x*!y*z*v + !x*y*z*v;
Le funzioni minimizzate con gli algoritmi visti fino a ora sono state del tipo
n
f (B ) = B. Dal Capitolo 3 sappiamo però che la forma generale di una funzione
n
m
Booleana è f (B ) = B .
Una prima soluzione al problema della sintesi a due livelli di funzioni a più uscite
potrebbe apparire quella di minimizzare individualmente le singole uscite utilizzando
3
gli algoritmi già visti. Si consideri la funzione f (B ) riportata come mappe di
Karnaugh in Figura 4.10.
Il costo della funzione è sceso a 6 letterali per i tre prodotti (A, C, E) che erano stati
già identificati manualmente nella tabella di copertura 2.13. L’esecuzione del
comando full_simplify, senza il DC-set, produce il seguente risultato:
sis> read_blif parspec_nodc.blif
sis> print_stats
parspec_nodc pi= 4 po= 1 nodes= 1
lits(sop)= 24
sis> full_simplify
sis> print_stats
parspec_nodc pi= 4 po= 1 nodes= 1
lits(sop)= 9
latches= 0
f1
xy
f2
xy
0
00
0
01
1
11
1
10
0
1
0
0
1
0
z
0
00
1
01
1
11
0
10
0
1
1
0
0
0
z
latches= 0
sis> write_eqn
INORDER = x y z v;
OUTORDER = f;
f = !x*y*!z*!v + x*y*v + x*z;
Il maggior costo è correttamente dato dalla minore riduzione delle dimensioni dei tre
prodotti poiché non sono state sfruttate le condizioni di indifferenza.
Per analizzare meglio la riduzione effettuata dal DC-set, si riordinino, come segue,
i prodotti delle due espressioni trovate.
Figura 4.10 Mappe di Karnaugh di una funzione a due uscite.
La minimizzazione individuale porta alle due espressioni:
f1 = x y + y z
f2 = x y + x z
e quindi al circuito di Figura 4.11, per un costo totale di 4 porte AND a due ingressi e
2 porte OR a due ingressi.
f = x y z v +xz+xyv
fDC-set = x y + x z + y v
Confrontando i prodotti delle due espressioni con questo ordinamento, si vede come
l’utilizzo del DC-set abbia permesso di:
− ridurre di 2 letterali il primo prodotto;
− lasciare invariato il secondo prodotto;
− ridurre di 1 letterale il terzo prodotto.
Queste sono le motivazioni che hanno permesso di ridurre il costo della soluzione di 3
letterali, passando da 9 letterali a 6.
Si noti infine che esistono anche in SIS implementazioni non esatte dell’algoritmo
di Quine-McCluskey utili per la minimizzazione di circuiti combinatori di grandi
dimensioni. Questo argomento non viene trattato in questo testo a fronte dello scarso
utilizzo di questi programmi, come più approfonditamente descritto nel Paragrafo 4.4
dove viene motivata la necessità della sintesi multilivello.
x
x
y
y
zz
f1
y
x
z
Figura 4.11 Prima realizzazione della funzione a due uscite.
f2
Ottimizzazione delle reti combinatorie 123
a
b
w
v = a d + bd + c d + a e
p = ce + de
r=p+ a
q=a+b
u = q c + q c + qc
x
s=r+ b
c
z
d
e
y
t = ac + ad + bc + bd + e
Figura 4.23 Esempio di rete per l’applicazione delle trasformazioni.
2
Applichiamo questo script a un esempio di rete riportato in Figura 4.23 . È innanzi
tutto necessario descrivere questa rete in formato .blif verificandone l’esatta
rappresentazione.
.model rete5in4out
.inputs a b c d e
.outputs w x z y
.names c e d p
11- 1
-11 1
.names a b q
1- 1
-1 1
.names p a r
1- 1
-0 1
.names r b s
1- 1
-0 1
.names a c d b e t
11--- 1
1-1-- 1
2
Questa rete di esempio è tratta da G. De Micheli, Synthesis and Optimization of Digital
Circuits, McGraw-Hill, 1994. In questo libro il lettore interessato trova adeguati
approfondimenti sulla teoria descritta in questo capitolo.
124 Capitolo 4
-1-1- 1
--11- 1
----1 1
.names q
01 1
10 1
11 1
.names a
01--- 1
-11-- 1
-1-0- 1
1---1 1
.names v
1 1
.names s
1 1
.names t
1 1
.names u
1 1
.end
c u
d b c e v
w
x
y
z
Un metodo efficace per verificare la correttezza della descrizione in formato .blif
consiste nel caricare il file rete5in4out.blif in SIS e stamparne le equazioni
confrontandole con quelle presenti in Figura 4.23. Si ottiene:
sis> read_blif rete5in4out.blif
sis> print_stats
rete5in4out
pi= 5 po= 4 nodes= 7
lits(sop)= 33
sis> write_eqn
INORDER = a b c d e;
OUTORDER = w x z y;
p
q
r
x
y
z
w
=
=
=
=
=
=
=
latches= 0
e*d + c*e;
b + a;
!a + p;
!b + r;
d*b + c*b + a*d + a*c + e;
q*!c + !q*c + q*c;
a*e + d*!c + d*b + !a*d;
Queste equazioni, a meno della sostituzione delle variabili uguali, corrispondono a
quelle riportate in Figura 4.23. Si applichi ora lo script.rugged evidenziando i
comandi in esso contenuti (source -x) e facendo stampare automaticamente il
risultato del comando sulla rete (set autoexec print_stats). Si ottiene:
po= 4
latches= 0
latches= 0
Ottimizzazione delle reti combinatorie 125
nodes= 7
sis> set autoexec print_stats
rete5in4out
pi= 5 po= 4 nodes= 7
lits(sop)= 33
sis> source -x script.rugged
sweep
rete5in4out
pi= 5
lits(sop)= 33
po= 4
nodes= 5
latches= 0
− Elimina tutti i nodi non usati e sostituisce le costanti e i nodi con un solo
ingresso all’interno dei nodi che li usano; in questo caso non ci sono
modifiche.
eliminate -1
rete5in4out
pi= 5
lits(sop)= 31
po= 4
nodes= 5
latches= 0
− Elimina tutti i nodi della rete che permettono un guadagno superiore o uguale
alla soglia. Il guadagno è dato dalla differenza in letterali tra la rete in presenza
del nodo e la rete in cui il nodo è stato sostituito in tutti i suoi fanout. Se un
nodo è usato una sola volta il suo guadagno è −1. In questo caso vengono
quindi eliminati tutti i nodi che sono usati una sola volta.
simplify -m nocomp
rete5in4out
pi= 5
lits(sop)= 23
po= 4
po= 4
po= 4
po= 4
po= 4
nodes= 4
nodes= 4
nodes= 4
nodes= 5
nodes= 5
latches= 0
latches= 0
latches= 0
latches= 0
latches= 0
− Semplifica tutti i nodi della rete usando una minimizzazione alla ESPRESSO
basata anche sul calcolo dei don’t care set.
eliminate -1; sweep
rete5in4out
pi= 5
lits(sop)= 23
rete5in4out
pi= 5
lits(sop)= 23
eliminate 5
rete5in4out
pi= 5
lits(sop)= 26
simplify -m nocomp
rete5in4out
pi= 5
lits(sop)= 26
resub -a
rete5in4out
pi= 5
lits(sop)= 26
− Sostituisce ogni nodo della rete negli altri, applicando una divisione algebrica,
finché non si verificano ulteriori cambiamenti.
126 Capitolo 4
fx
rete5in4out
pi= 5
lits(sop)= 21
po= 4
nodes= 6
latches= 0
4
4
4
4
4
nodes= 6
nodes= 6
nodes= 6
nodes= 6
nodes= 6
latches= 0
latches= 0
latches= 0
latches= 0
latches= 0
− Ricerca in maniera greedy il cubo singolo e doppio che sia miglior divisore di
tutti gli altri cubi.
resub -a; sweep
rete5in4out
pi= 5 po=
lits(sop)= 21
rete5in4out
pi= 5 po=
lits(sop)= 21
eliminate -1; sweep
rete5in4out
pi= 5 po=
lits(sop)= 21
rete5in4out
pi= 5 po=
lits(sop)= 21
full_simplify -m nocomp
rete5in4out
pi= 5 po=
lits(sop)= 21
− Minimizza tutti i nodi della rete alla ESPRESSO usando i don’t care locali di
ingresso e uscita calcolati per ogni nodo.
e*[4] + !b + !a;
[4]*[5] + e;
[5] + c;
a*e + d*!c + d*b + !a*d;
= d + c;
= b + a;
sis> write_eqn
INORDER = a b c d e;
OUTORDER = w x z y;
x =
y =
z =
w =
[4]
[5]
Il risultato ottenuto è praticamente identico a ciò che potrebbe essere ottenuto
applicando manualmente gli algoritmi presentati nei paragrafi precedenti. L’unica
differenza può riguardare la mancata fattorizzazione di
j = a− + b + −
c
nel calcolo di w. Infatti, questa ulteriore fattorizzazione fa risparmiare un letterale, ma
aggiunge un nodo alla rete e l’algoritmo fx non ha ritenuto favorevole questa
operazione.
Applicando nuovamente lo script.rugged non si ottengono ulteriori
ottimizzazioni facendo così pensare che il minimo locale raggiunto sia stabile.
Ottimizzazione delle reti combinatorie 127
4.5
La valutazione dei ritardi
Dopo aver esaminato i problemi relativi alla minimizzazione dell’area di un circuito,
esaminiamo ora alcuni aspetti relativi al ritardo. La corretta valutazione del ritardo di
un circuito è un problema molto complesso poiché coinvolge direttamente aspetti
legati alla tecnologia di realizzazione del circuito. Se a tutti i nodi della rete sono
associate ben precise celle di libreria, la valutazione è più facile; a ogni cella è
associato un ritardo noto, altri ritardi di propagazione sono legati al carico delle celle
stesse, valutabile sulla base del fanout di ogni cella, e quindi un calcolo può essere
fatto con una discreta approssimazione molto vicina all’effettivo ritardo misurabile
sul circuito fisico.
Nel caso però che si è considerato in questo capitolo, di reti su cui si compie
un’ottimizzazione generica indipendente dalla tecnologia di realizzazione del
dispositivo, senza vincoli precisi sulle singole celle, la valutazione è meno immediata.
Lo schema più banale, utilizzato peraltro molto spesso, soprattutto finché si sono
utilizzati componenti a piccola integrazione, si limita ad associare un ritardo unitario
a ogni livello delle porte logiche. Questo criterio è stato usato all’inizio del capitolo
per calcolare la relazione area-ritardo di un circuito combinatorio a due livelli.
Con maggior cautela, si ricorre a volte a una stima del caso pessimo: si calcolano i
ritardi di propagazione nella rete logica facendo riferimento alle condizioni pessime
di funzionamento (temperatura, livelli di alimentazione, carico per le singole porte
ecc.), in base al concetto che il ritardo effettivo in funzionamento non potrà superare
quello calcolato, che può essere visto come un limite superiore. Con questo approccio
evidentemente è facile che il progetto non sfrutti al meglio le potenzialità della
tecnologia; peraltro, una stima troppo ottimistica dei ritardi può condurre a circuiti
che non funzionano correttamente.
Per rendere questo calcolo più preciso, supponiamo di conoscere per ogni nodo
della rete il ritardo di propagazione, che sarà indicato con un numero positivo. A
ogni nodo si assegna anche un tempo di arrivo, o istante data-ready, cioè la stima
dell’istante in cui il segnale che esso genera diventa stabile. Il tempo di arrivo ai
terminali d’ingresso primari indica l’istante in cui i segnali d’ingresso sono stabili, e
viene normalmente posto a zero. Una soluzione relativamente semplice consiste nel
calcolare i tempi di arrivo solo sulla base della topologia della rete logica, cioè
considerando solo i percorsi di propagazione e ignorando il fatto che particolari
combinazioni dei valori agli ingressi dei nodi precludano la propagazione delle
variazioni di segnale attraverso i nodi stessi. Di conseguenza, l’istante data-ready
all’uscita di un nodo non è che la somma fra l’istante data-ready del più lento fra gli
ingressi del nodo e il ritardo di propagazione del nodo stesso. Ogni terminale di uscita
primario dipende esattamente da un nodo interno; al terminale si può associare un
ritardo di propagazione per modellare caratteristiche della porta di uscita.
Se per qualsiasi nodo vi ∈ V si indica con di il ritardo di propagazione e con ti
l’istante di data-ready, si può dire che:
ti = di + max(tj : j ∈ {vj collegati a vi})
130 Capitolo 4
2.30)
r : arrival=( 6.50 6.50) required=( 6.50 6.50) slack=(-0.00
-0.00)
{x} : arrival=( 9.20 9.20) required=( 9.20 9.20) slack=(
0.00 0.00)
{y} : arrival=( 3.90 3.90) required=( 9.20 9.20) slack=(
5.30 5.30)
{z} : arrival=( 6.90 6.90) required=( 9.20 9.20) slack=(
2.30 2.30)
{w} : arrival=( 6.60 6.60) required=( 9.20 9.20) slack=(
2.60 2.60)
Si noti come il cammino più lento sia associato alla generazione del segnale x. Dopo
la minimizzazione logica si ottiene:
sis> print_stats
rete5in4out
pi= 5 po= 4 nodes= 6
latches= 0
lits(sop)= 21
sis> print_delay -m mapped
network not mapped, using mapped delay model
a : arrival=( 0.00 0.00) required=( 0.00 0.00) slack=( 0.00
0.00)
b : arrival=( 0.00 0.00) required=( 0.00 0.00) slack=( 0.00
0.00)
c : arrival=( 0.00 0.00) required=( 0.00 0.00) slack=( 0.00
0.00)
d : arrival=( 0.00 0.00) required=( 0.00 0.00) slack=( 0.00
0.00)
e : arrival=( 0.00 0.00) required=( 2.90 2.90) slack=( 2.90
2.90)
{x} : arrival=( 6.30 6.30) required=( 6.90 6.90) slack=(
0.60 0.60)
{y} : arrival=( 6.90 6.90) required=( 6.90 6.90) slack=(
0.00 0.00)
{z} : arrival=( 6.40 6.40) required=( 6.90 6.90) slack=(
0.50 0.50)
{w} : arrival=( 6.60 6.60) required=( 6.90 6.90) slack=(
0.30 0.30)
[483] : arrival=( 3.30 3.30) required=( 3.30 3.30) slack=(
0.00 0.00)
[484] : arrival=( 3.30 3.30) required=( 3.30 3.30) slack=(
0.00 0.00)
Si può vedere come il ritardo massimo sia sceso, si può però pensare di ristrutturare la
rete in funzione di ridurre la lunghezza dei cammini critici. Il comando
reduce_depth esegue questa operazione.
sis> reduce_depth
sis> print_delay -m mapped
network not mapped, using mapped delay model
Ottimizzazione delle reti combinatorie 131
a : arrival=( 0.00 0.00) required=( 1.10 1.10) slack=( 1.10
1.10)
b : arrival=( 0.00 0.00) required=( 0.00 0.00) slack=( 0.00
0.00)
c : arrival=( 0.00 0.00) required=( 1.20 1.20) slack=( 1.20
1.20)
d : arrival=( 0.00 0.00) required=( 2.60 2.60) slack=( 2.60
2.60)
e : arrival=( 0.00 0.00) required=( 2.60 2.60) slack=( 2.60
2.60)
{x} : arrival=( 3.80 3.80) required=( 6.60 6.60) slack=(
2.80 2.80)
{y} : arrival=( 3.90 3.90) required=( 6.60 6.60) slack=(
2.70 2.70)
{z} : arrival=( 4.70 4.70) required=( 6.60 6.60) slack=(
1.90 1.90)
{w} : arrival=( 6.60 6.60) required=( 6.60 6.60) slack=(
0.00 0.00)
sis> print_stats
rete5in4out
pi= 5
lits(sop)= 26
po= 4
nodes= 4
latches= 0
sis> write_eqn
INORDER = a b c d e;
OUTORDER = w x z y;
x = d*e + c*e + !b + !a;
y = b*d + a*d + b*c + a*c + e;
z = c + b + a;
w = a*e + d*!c + d*b + !a*d;
Il ritardo massimo è diminuito a fronte però di una ridondanza del circuito dovuta alla
replicazione di logica necessaria a diminuire i livelli, e quindi i ritardi, della rete.
Questo esempio è una ulteriore conferma della correttezza della curva di
ottimizzazione area/ritardo presentata in Figura 4.3. L’applicazione del comando
reduce_depth può essere vista come lo spostamento dal punto C al punto B del
grafico.
4.6 Esercizi
1) Descrivere il significato e l’utilizzo di una mappa di Karnaugh a quattro variabili.
Mostrare su una mappa di esempio un mintermine, un implicante primo e uno
essenziale.
2) Data la seguente funzione Booleana f(a, b, c, d, e) completamente specificata:
− On-set = {m1, m3, m11, m17, m19, m20, m27, m28}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi. Dare la
definizione di implicante primo. Calcolare l’Off-set della funzione data.
3) Data la funzione Booleana parzialmente specificata f(a, b, c, d, e):
132 Capitolo 4
− On-set = {m4, m4, m6, m6, m14, m15, m24, m25}
− DC-set = {m1, m3, m7, m16, m27, m28}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi. Identificare
una copertura minima della funzione descrivendo il significato delle operazioni
svolte.
4) Data la funzione Booleana f(a, b, c, d, e) completamente specificata:
− On-set = {m9, m11, m19, m25, m27, m28, m3, m4}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi. Identificare
l’implementazione a due livelli della funzione che corrisponde a una copertura
di costo minimo. Descrivere cosa sarebbe cambiato nelle varie fasi della sintesi
se la funzione fosse stata parzialmente specificata dal seguente DC-set:
− DC-set = {m8, m10, m18, m24}
5) Realizzare una implementazione minima a due livelli della funzione parzialmente
specificata f(a, b, c, d), elencando inoltre tutti gli implicanti primi ed essenziali:
− On-set = {m1, m13, m9, m10}
− Off-set = {m5, m2, m6, m14}
6) Data la funzione Booleana parzialmente specificata f(a, b, c, d, e):
− On-set = {m8, m10, m18, m24, m25}
− DC-set = {m9, m11, m19, m27, m28, m3, m4}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi.
7) Data la funzione Booleana parzialmente specificata f(a, b, c, d, e):
− On-set = {m4, m5, m6, m7, m14, m15, m24, m25}
− Off-set = {m1, m3, m16, m27, m28}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi.
8) Data la funzione Booleana parzialmente specificata f(a, b, c, d):
− On-set = {m1, m13, m9, m10}
− Off-set = {m5, m2, m6, m14}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi. Identificare
una copertura minima della funzione descrivendo il significato delle operazioni
compiute.
9) Data la funzione Booleana parzialmente specificata f(a, b, c, d, e):
− On-set = {m9, m11, m19, m27, m28, m3, m4}
− DC-set = {m8, m10, m18, m24, m25}
− Calcolare col metodo di Quine-McCluskey i suoi implicanti primi. Identificare,
tra gli implicanti primi trovati, quelli che non è necessario utilizzare durante il
calcolo della copertura ottima della funzione f, spiegandone il motivo.
10) Si consideri un circuito combinatorio che ha due ingressi a 2 bit: A(a1 a0) e B(b1
b0), un ingresso a 1 bit OP e una uscita OUT a 1 bit. Se OP = 0, OUT vale 1 se A
> B. Se OP = 1, OUT vale 1 se A = B. A e B sono interpretati come numeri in
modulo.
− Definire l’On-set della funzione OUT(OP, a1, a0, b1, b0). Calcolare col metodo
di Quine-McCluskey i suoi implicanti primi. Identificare una copertura minima
della funzione descrivendo il significato delle operazioni compiute.