Maurizio Palesi 1

Minimizzazione di Reti Minimizzazione di Reti Logiche Combinatorie Logiche Combinatorie

Multi-livelloMulti-livello

Maurizio Palesi

Maurizio Palesi 2

IntroduzioneIntroduzioneObiettivo della sintesi logica: ottimizzazione

delle cifre di merito area e prestazioniPrestazioni: valutate di norma come il ritardo

di propagazione lungo il percorso criticoReti combinatorie a due livelli: si riducono

contemporaneamente areae ritardoReti combinatorie a più livelli: area e ritardo non

procedono nella stessa direzione

Maurizio Palesi 3

IntroduzioneIntroduzione I circuiti logici combinatori sono molto spesso

realizzati come reti multi-livello di porte logicheAumento dei gradi di libertà per l’ottimizzazione

Sfruttamento del trade-off area/ritardoSoddisfare i vincoli tecnologici

Difficoltà di modeling e ottimizzazioneMetodi esatti: praticamente non attuabiliEuristiche (2 passi)

– Ottimizzazione trascurando i vincoli (semplici modelli per area e prestazioni)

– I vincoli sono presi in considerazione (library binding)

Fattorizzazione

Maurizio Palesi 4

FattorizzazioneFattorizzazione

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 ingressiRaramente disponibili in una libreriaCaratterizzati da ritardi elevati

Costo: 31 porte a 2 ingressi

Ritardo: 5

Maurizio Palesi 5

FattorizzazioneFattorizzazione

f = xy(zv + zv) + xy(zv + zv) + xy(zv + zv) + xy(zv + zv)

Riapplicando nuovamente la stessa proprietà

Applicando la proprità distributiva del prodotto rispetto alla somma

f = xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv + xyzv

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 6

FattorizzazioneFattorizzazione Costo della rete ancora di 9 porte logiche

Ma tutte le porte sono a 2 ingressi

Numero di letterali da 32 a 12Costo: 9 porte a 2 ingressi

Ritardo: 4

Maurizio Palesi 7

FattorizzazioneFattorizzazione La tecnica di fattorizzazione, se applicata

manualmente, implica una certa misura di intuito (o di fortuna) da parte del progettistaDeve sapere scegliere nel modo migliore i termini

rispetto a cui fattorizzare e l’ordineSpesso occore effettuare una fase di espansione

(Teorema di Shannon) prima di fattorizzare

Utilizzo di strumenti di progettazione automatica

Maurizio Palesi 8

Esempio (1/3)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 9

Esempio (2/3)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’;

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: 22 letterali

Ritardo: 5

Costo: 19 letterali

Ritardo: 6

Maurizio Palesi 10

Esempio (3/3)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’)

Costo: 18 letterali

Ritardo: 7

17 18 19 20 21 22 23 244

4.5

5

5.5

6

6.5

7

7.5

Area

Rita

rdo

Maurizio Palesi 11

Obiettivi della SintesiObiettivi 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ò prevedereMinimizzazione dell'area (con vincolo sul ritardo)Minimizzazione del ritardo (con vincolo sull'area)

Maurizio Palesi 12

Criteri Guida (1/2)Criteri Guida (1/2)Si pone il problema di scegliere rispetto a

quale/quali variabili fattorizzare a ogni passoQuali variabili raccogliere a fattor comune?Fra quali termini?

Si ricorre a semplici criteri-guida

Maurizio Palesi 13

Criteri Guida (2/2)Criteri Guida (2/2) Partendo da una forma iniziale (tipicamente, una forma

a due livelli) si costruisce una tabella in cuiA ogni riga corrisponde uno dei termini prodotto (implicanti)

presenti nella espressionePer 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 14

Esempio 1 (1/5)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 15

Esempio 1 (2/5)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 tabelleUna 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 16

Esempio 1 (3/5)Esempio 1 (3/5)

Maurizio Palesi 17

Esempio 1 (4/5)Esempio 1 (4/5) Dalla tabella di sinistra non

risultano ulteriori possibilità di fattorizzazioneLa 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’bAnche in questo caso si estrae

una tabella residua

Maurizio Palesi 18

Esempio 1 (5/5)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 19

Esempio 2Esempio 2

Maurizio Palesi 20

Esempio 3Esempio 3

Maurizio Palesi 21

Modelli di Reti LogicheModelli 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 22

Modelli di Reti LogicheModelli di Reti LogicheEsempioEsempio

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 eq = a + br = p + a's = r + b't = ac + ad + bc + bd + eu = q'c + qc' + qcv = a'd + bd + c'd + ae'w = vx = sy = tz = u

Maurizio Palesi 23

Modelli di Reti LogicheModelli di Reti LogicheEsempio - RappresentazioneEsempio - Rappresentazione

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

Maurizio Palesi 24

Stima dell’AreaStima 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 tecnologicaValutabile parametricamente in base al numero di ingressiIn 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 stimareProporzionale al numero di letterali

Maurizio Palesi 25

Stima del RitardoStima del Ritardo Ritardo proporzionale al numero di livelli logici e alle

interconnessioniNel caso di bounded network (reti mappate su una libreria

tecnologica), il ritardo di ogni singola porta logica è specificatoAltrimenti 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 26

Ottimizzazione Multi-livello: MetodiOttimizzazione Multi-livello: Metodi

Metodi esattiElevata complessità computazionaleNon applicabili ai casi reali

Metodi approssimatiMetodi euristici basati sull’applicazione iterativa di

trasformazioni che preservano il comportamento di I/OL’esecuzione di trasformazioni in qualunque sequenza

salvaguarda l’equivalenza della rete logicaMetodi che differiscono per

Tipo delle trasformazioniSelezione e ordine delle trasformazioni

Maurizio Palesi 27

Ottimizzazione Multi-livelloOttimizzazione Multi-livello

Problema della sintesi multi-livelloTrovare un’appropriata sequenza di

trasformazioni da applicare alla rete logicaUna 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 28

Ottimizzazione Multi-livelloOttimizzazione Multi-livello Le trasformazioni

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 algoritmoDove la trasformazione può essere applicata?Termina quando nessuna trasformazione dello stesso tipo può essere

applicabileGli algoritmi legati a trasformazioni diverse vengono applicati in

sequenza

Sequenze di applicazione diversa portano a risultati diversi Script di sintesi

Maurizio Palesi 29

Trasformazioni AlgebricheTrasformazioni AlgebricheSweepEliminazioneDecomposizioneEstrazioneSemplificazioneSostituzione

Maurizio Palesi 30

SweepSweepElimina dalla rete

I nodi con un solo ingressoI nodi le cui funzioni danno valore costante

Viene richiamata a valle di altre trasformazioni

Maurizio Palesi 31

EliminazioneEliminazione 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 32

Eliminazione (cont.)Eliminazione (cont.)

Maurizio Palesi 33

DecomposizioneDecomposizione La decomposizione di un vertice interno è la sostituzione del vertice con due (o

più) vertici che formano una sottorete equivalente al vertice originale

Decomposizionev = (a’ + b’ + c’)d + ae’j = a’ + b’ + c’v = jd + ae’

Maurizio Palesi 34

Decomposizione (cont.)Decomposizione (cont.)

Maurizio Palesi 35

EstrazioneEstrazione Una sotto-espressione comune a due funzioni associate a due vertici può

essere estratta creando un nuovo vertice associato alla sottoespressione

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

p = (c + d)e k = c + dp = ket = ka + kb + e

Maurizio Palesi 36

Estrazione (cont.)Estrazione (cont.)

Maurizio Palesi 37

SemplificazioneSemplificazione 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 38

SostituzioneSostituzione 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 39

Sostituzione (cont.)Sostituzione (cont.)

Maurizio Palesi 40

Risultato delle TrasformazioniRisultato delle Trasformazioni

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

Maurizio Palesi 41

Risultato delle TrasformazioniRisultato delle Trasformazioni

k = c + dq = a + bs = ke + a' + b't = kq + eu = q’c + qc’ + qcv = jd + ae'w = vx = sy = tz = u

Rispetto alla rete logica di riferimento il numero totale dei letterali è stato ridotto da 33 a 24

Maurizio Palesi 42

Trasformazioni BooleaneTrasformazioni BooleaneIdea di base

Associare ad ogni nodo della reteNon 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 esterneDi controllabilità di ingressoDi osservabilità di uscita

Maurizio Palesi 43

Condizioni di Indifferenza EsterneCondizioni di Indifferenza Esterne

Di controllabilità di ingressoControllability don’t care (CDCin)

Configurazioni di ingresso che non vengono mai prodotte dall’ambienteE quindi non vengono mai presentate agli ingressi primari

CDCin = x1x2x3x4+x1x2+x1x3+x1x4+x2x3 +x2x4 +x3x4

Maurizio Palesi 44

Condizioni di Indifferenza EsterneCondizioni di Indifferenza Esterne

Di osservabilità in uscitaObservability 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 45

Condizioni di Indifferenza EsterneCondizioni 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

DC ext=CDC inODCout=[x1x2x3x4

x1x2x3x4

x4x2x3x1

x 4x2x3x1]

Maurizio Palesi 46

Insiemi Locali di Condizioni di Insiemi Locali di Condizioni di IndifferenzaIndifferenza

Mappa di Karnaugh per y

Maurizio Palesi 47

Insiemi Locali di Condizioni di Insiemi Locali di Condizioni di IndifferenzaIndifferenza

Non può mai essere x≠ a+b E’ possibile definire le seguenti condizioni di indifferenza di controllabilità

CDC=x⊕ ab =x axbxa b¿

Maurizio Palesi 48

Insieme di Soddisfacibilità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 è l’uscita del generico nodo vx

fx è la funzione che genera x

SDC= ∑v x∈V

x⊕ f x