Circuiti logici Multilivello

Minimizzazione di Reti
Logiche Combinatorie
Multi-livello
Maurizio Palesi
Maurizio Palesi
1
Introduzione
 Obiettivo della sintesi logica: ottimizzazione
delle cifre di merito area e prestazioni
 Prestazioni: valutate di norma come il ritardo
di propagazione lungo il percorso critico
Reti combinatorie a due livelli: si riducono
contemporaneamente areae ritardo
Reti combinatorie a più livelli: area e ritardo non
procedono nella stessa direzione
Maurizio Palesi
2
Introduzione
 I circuiti logici combinatori sono molto spesso
realizzati come reti multi-livello di porte logiche
Aumento dei gradi di libertà per l’ottimizzazione
 Sfruttamento del trade-off area/ritardo
 Soddisfare i vincoli tecnologici
Difficoltà di modeling e ottimizzazione
 Metodi esatti: praticamente non attuabili
 Euristiche (2 passi)
– Ottimizzazione trascurando i vincoli (semplici modelli per area e
prestazioni)
– I vincoli sono presi in considerazione (library binding)
Fattorizzazione
Maurizio Palesi
3
Fattorizzazione
Costo: 31 porte a 2 ingressi
Ritardo: 5
f = xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv
 Corrispondente ad un circuito costituito da 8 porte
AND a 4 ingressi e 1 porta OR a 8 ingressi
Raramente disponibili in una libreria
Caratterizzati da ritardi elevati
Maurizio Palesi
4
Fattorizzazione
f = xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv
 Applicando la proprità distributiva del prodotto
rispetto alla somma
f = xy(zv + zv) + xy(zv + zv) + xy(zv + zv) + xy(zv + zv)
 Riapplicando nuovamente la stessa proprietà
f = (xy + xy)(zv + zv) + (xy + xy)(zv + zv)
 Ricordando che (ab + ab)’=(ab + ab)
i = (xy + xy)
j = (zv + zv)
f = ij + ij
Maurizio Palesi
5
Fattorizzazione
 Costo della rete ancora di 9 porte logiche
 Ma tutte le porte sono a 2 ingressi
 Numero di letterali da 32 a 12
Costo: 9 porte a 2 ingressi
Ritardo: 4
Maurizio Palesi
6
Fattorizzazione
 La tecnica di fattorizzazione, se applicata
manualmente, implica una certa misura di intuito
(o di fortuna) da parte del progettista
Deve sapere scegliere nel modo migliore i termini
rispetto a cui fattorizzare e l’ordine
Spesso occore effettuare una fase di espansione
(Teorema di Shannon) prima di fattorizzare
 Utilizzo di strumenti di progettazione automatica
Maurizio Palesi
7
Esempio (1/3)
 Si supponga 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’
 La porta AND a cinque ingressi è realizzata come
cascata di due AND a tre ingressi; l’OR a otto
ingressi realizzato con tre OR in parallelo seguiti da
un OR finale
Costo: 23 letterali
Ritardo: 5
Maurizio Palesi
8
Esempio (2/3)
 Si proceda ora a fattorizzare k’ fra il 3° e il 4° termine
f = l’ + c’*g*h’ + k’(a*b’+ g) + a’*b’*c’*d’*e’ +
a*d’*e’*f’ + e’*g’*i’ + e’*j’;
Costo: 22 letterali
Ritardo: 5
 Si applichi ancora la fattorizzazione – questa volta
rispetto a e’, per i termini dal 4° all’ultimo
f = l’ + c’*g*h’ + k’(a*b’+ g) + e’*(a’*b’*c’*d’ +
a*d’*f’+g’*i’+j’);
Costo: 19 letterali
Ritardo: 6
Maurizio Palesi
9
Esempio (3/3)
 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’)
7.5
Costo: 18 letterali
7
Ritardo: 7
Ritardo
6.5
6
5.5
5
4.5
4
17
18
19
20
21
22
23
24
Area
Maurizio Palesi
10
Obiettivi della Sintesi
 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 ritardo
 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)
Maurizio Palesi
11
Criteri Guida (1/2)
 Si pone il problema di scegliere rispetto a
quale/quali variabili fattorizzare a ogni passo
Quali variabili raccogliere a fattor comune?
Fra quali termini?
 Si ricorre a semplici criteri-guida
Maurizio Palesi
12
Criteri Guida (2/2)
 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
Maurizio Palesi
13
Esempio 1 (1/5)
 Si consideri
f = a*c*d + a’*b*c’ + a’*b*d’ + b’*c*d
 Si faccia riferimento a porte a 3 ingressi con ritardo
uniforme 
Costo: 12 letterali
Ritardo: 3
Maurizio Palesi
14
Esempio 1 (2/5)
 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
(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
Maurizio Palesi
15
Esempio 1 (3/5)
Maurizio Palesi
16
Esempio 1 (4/5)
 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 porta a
un’ulteriore fattorizzazione
rispetto al prodotto a’b
 Anche in questo caso si estrae
una tabella residua
Maurizio Palesi
17
Esempio 1 (5/5)
 Dalla sequenza di passi ora visti si ottiene la
forma fattorizzata
f = d*c*(a+b’) + a’*b*(c’+d’)
Costo: 8 letterali
Ritardo: 3
Maurizio Palesi
18
Esempio 2
Maurizio Palesi
19
Esempio 3
Maurizio Palesi
20
Modelli di Reti Logiche
 Il comportamento di un circuito combinatorio a n ingressi ed m uscite
può essere espresso da un vettore di funzioni Booleane:
fi:Bn → {0,1,*}, i=1,2,...,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 descritta da una rete
logica
 Una rete logica è una struttura che collega dei moduli (porte di I/O e
porte logiche) attraverso reti di interconnessione
Maurizio Palesi
21
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
Maurizio Palesi
22
Esempio di Rete Logica
Comportamento
logico di I/O
x = ab
y = c + ab
Rete logica mappata
p
a
b
x
q
c
y
va
Grafo della rete
logica
vb
vc
Maurizio Palesi
vp
vx
vq
vy
23
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
 VI vertici relativi a ingressi primari e ni = |VI| numero degli ingressi
primari
 VO vertici relativi a uscite primarie e no = |Vo| numero delle uscite
primarie
 VG vertici interni e ng = |VG| 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à)
Maurizio Palesi
24
Modelli di Reti Logiche
Esempio
 Si consideri la rete logica con variabili di ingresso primarie {a,b,c,d,e},
variabili di uscita primarie {w,x,y,z} descritta dalle seguenti equazioni
p = ce + d e
q=a+b
r = p + a'
s = r + b'
t = ac + ad + bc + bd + e
u = q'c + qc' + qc
v = a'd + bd + c'd + ae'
w=v
x=s
y=t
z=u
Maurizio Palesi
25
Modelli di Reti Logiche
Esempio - Rappresentazione
Costo associato alla rete logica = (8 + 8 + 9 +8) letterali = 33 letterali
Maurizio Palesi
26
Stima dell’Area
 L’area occupata da una rete logica multi-livello è
proporzionale al numero di porte logiche e alle
interconnessioni (wiring)
L’area delle porte logiche è definibile una volta che si
conosca la libreria tecnologica
 Valutabile parametricamente in base al numero di ingressi
 In base al numero di porte logiche equivalenti (NAND2) che
implementano la corrispondente funzionalità logica e al numero
di letterali
L’area dovuta ai collegamenti è molto più difficile da
stimare
 Proporzionale al numero di letterali
Maurizio Palesi
27
Stima del Ritardo
 Ritardo proporzionale al numero di livelli logici e alle
interconnessioni
 Nel caso di bounded network (reti mappate su una libreria
tecnologica), il ritardo di ogni singola porta logica è specificato
 Altrimenti il ritardo è stimato in base al ritardo associato ad ogni
vertice (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
Maurizio Palesi
28
Ottimizzazione Multi-livello: Metodi
 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
Maurizio Palesi
29
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
Maurizio Palesi
30
Ottimizzazione Multi-livello
 Le traformazioni
 Si valutano utilizzando delle cifre di merito
 In modo da scartare le trasformazioni non convenienti
 Si applicano in modo iterativo
 Il procedimento termina quando nessuna ulteriore applicazione di
queste la migliora
 Per ogni trasformazione è definito un algoritmo
 Dove la trasformazione può essere applicata?
 Termina quando nessuna trasformazione dello stesso tipo può essere
applicabile
 Gli algoritmi legati a trasformazioni diverse vengono applicati in
sequenza
 Sequenze di applicazione diversa portano a risultati diversi
 Script di sintesi
Maurizio Palesi
31
Trasformazioni Algebriche
 Sweep
 Eliminazione
 Decomposizione
 Estrazione
 Semplificazione
 Sostituzione
Maurizio Palesi
32
Sweep
 Elimina dalla rete
I nodi con un solo ingresso
I nodi le cui funzioni danno valore costante
 Viene richiamata a valle di altre
trasformazioni
Maurizio Palesi
33
Eliminazione
 L’eliminazione di un vertice interno è la sua rimozione dalla rete. La variabile
corrispondente al vertice è rimpiazzata dalla corrispondente espressione in
tutte le sue occorrenze nella rete logica
Eliminazione
Maurizio Palesi
34
Eliminazione (cont.)
Maurizio Palesi
35
Decomposizione
 La decomposizione di un vertice interno è la sostituzione del vertice con due (o
più) vertici che formano una sottorete equivalente al vertice originale
Decomposizione
v = (a’ + b’ + c’)d + ae’
j = a’ + b’ + c’
v = jd + ae’
Maurizio Palesi
36
Decomposizione (cont.)
Maurizio Palesi
37
Estrazione
 Una sotto-espressione comune a due funzioni associate a due vertici può
essere estratta creando un nuovo vertice associato alla sottoespressione
p = (c + d)e
k=c+d
p = ke
t = ka + kb + e
t = (c + d)(a + b) + e
Maurizio Palesi
38
Estrazione (cont.)
Maurizio Palesi
39
Semplificazione
 Una funzione è ridotta in complessità sfruttando le proprietà della sua
rappresentazione. Se la funzione è rappresentata nella forma a due livelli allora
le tecniche di ottimizzazione a due livelli possono essere utilizzate. Se l’insieme
di supporto non cambia allora la trasformazione si dice locale
u=q+c
Trasformazione locale
Maurizio Palesi
40
Sostituzione
 Una funzione è ridotta in complessità utilizzando un ingresso addizionale che
non appartiene all’insieme di supporto. La trasformazione richiede la creazione
di una dipendenza ma può anche portare ad eliminarne altre
t = k(a + b) + e
Maurizio Palesi
41
Sostituzione (cont.)
Maurizio Palesi
42
Risultato delle Trasformazioni
Costo associato alla rete logica trasformata = (7 + 4 + 5 +8) letterali = 24 letterali
Maurizio Palesi
43
Risultato delle Trasformazioni
k=c+d
q=a+b
s = ke + a' + b'
t = kq + e
u = q’c + qc’ + qc
v = jd + ae'
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
Maurizio Palesi
44
Trasformazioni Booleane
 Idea di base
Associare ad ogni nodo della rete
Non solo la funzione booleana locale
…ma anche un insieme di condizioni di indifferenza
locali
– Si considerano le relazioni tra il singolo nodo e l’intera rete
 Condizioni di indifferenza esterne
Di controllabilità di ingresso
Di osservabilità di uscita
Maurizio Palesi
45
Condizioni di Indifferenza Esterne
 Di controllabilità di ingresso
Controllability don’t care (CDCin)
Configurazioni di ingresso che non vengono mai
prodotte dall’ambiente
 E quindi non vengono mai presentate agli ingressi primari
 CDCin = x1x2x3x4+x1x2+x1x3+x1x4+x2x3 +x2x4 +x3x4
Maurizio Palesi
46
Condizioni di Indifferenza Esterne
 Di osservabilità in uscita
Observability don’t care (ODCout)
Configurazioni di ingresso corrispondenti a situazioni in
cui l’uscita non verrà osservata
 ODCout = [x1 x1 x4 x4]T
Maurizio Palesi
47
Condizioni di Indifferenza Esterne
 Insieme complessivo delle condizioni d’indifferenza esterne
 External don’t care (DCext)
 DCext = CDCin ∪ ODCout
 CDCin = x1x2x3x4+x1x2+x1x3+x1x4+x2x3 +x2x4 +x3x4
 ODCout = [x1 x1 x4 x4]T
[
x1 x 2 x 3 x 4
x1 x 2 x 3 x 4
DC ext =CDC in ODC out =
x 4 x 2 x 3 x1
x 4 x 2 x3 x 1
Maurizio Palesi
]
48
Insiemi Locali di Condizioni di
Indifferenza
 Mappa di Karnaugh per y
Maurizio Palesi
49
Insiemi Locali di Condizioni di
Indifferenza
 Non puo mai essere x≠ a+b
 E’ possibile definire le seguenti condizioni di indifferenza di controllabilità
CDC=x ⊕  a b= x a x bxa b
¿
Maurizio Palesi
50
Insieme di Soddisfacibilità
 L’uscita di una funzione non può mai essere
diversa dalla valutazione della funzione
stessa
 Per l’intera rete G(V,E) si può calcolare
l’insieme di soddisfacibilità
x

SDC= ∑ x ⊕ f 
v x ∈V
x è l’uscita del generico nodo vx
fx è la funzione che genera x
Maurizio Palesi
51