Test completo per Architettura degli Elaboratori

METODO ELETTRICO PER LA RAPPRESENTAZIONE DEGLI OPERATORI LOGICI

Uso dei transistor a tecnologia CMOS:

Transistor n: in conduzione con ΔV, in interdizione senza ΔV

Transistor p: in conduzione senza ΔV, in interdizione con ΔV

Porta logica: rappresentatori elettrici degli operatori

ESEMPIO DI TRANSISTOR PER NOT:

TABELLA RIASSUNTIVA DELLE PORTE LOGICHE FONDAMENTALI

CRITERI DI OTTIMABILITA’

- Area (circuito con dimensioni inferiori)

- Ritardo (circuito più veloce)

- Potenza (economicità)

RIDURRE LE DIMENSIONI DI UN CIRCUITO

Per avere circuiti più piccoli si deve ridurre il numero degli ingressi BISOGNA RIDURRE I LETTERALI

REGOLA DI ASSORBIMENTO

Usata da tutti gli algoritmi di risoluzione. (A*B) + (¬ A*B) = B*(¬ A + A) = B*(1) = B

Come scegliere dove semplificare? Usando lo spazio booleano

trigonometrico. Quando ci sono 3 variabili infatti si possono unire i

mintermini più vicini per usare la regola dell’assorbimento. Tutti i

mintermini devono essere coperti almeno una volta.

IMPLICANTE: mintermine o insieme di mintermini (sottocubo).

IMPLICANTE PRIMO: implicante che non è contenuto in altri

implicanti (sottocubo massimo).

IMPLICANTE PRIMO ESSENZIALE: implicante primo che copre un implicante che nessun’altro

implicante primo copre. METODO DI KARNAUGH

- Non deve essere vista come una semplice tabella ma come un cilindro;

- Bisogna cercare tutti i sottocubi adiacenti;

- Non viene usato dai calcolatori perché non segue un algoritmo.

METODO QUINE-McCLUSKEY

1) TROVARE GLI IMPLICANTI PRIMI

Per trovarli senza occupare memoria eccessiva si usano i BDD.

X Y Z V O M L’andamento delle tavole di verità è infatti esponenziale (n variabili

0 0 0 0 0 n

proposizionali2 configurazioni). Con i BDD si passa da un andamento

0 0 0 1 1 M1

0 0 1 0 0 esponenziale a un andamento polinomiale, occupando meno memoria.

0 0 1 1 0 Solo in qualche caso i BDD non funzionano.

0 1 0 0 1 M4 Quando due mintermini differiscono per 1 Bit solo hanno una distanza di

0 1 0 1 1 M5 Hamming = 1. Bisogna associare i mintermini di distanza 1 , mettendo in

0 1 1 0 1 M6 ordine di Bit i mintermini e associando i mintermini (n) con quelli (n-1).

0 1 1 1 1 M7

1 0 0 0 0

1 0 0 1 1 M9 0-01 M1,M5 P1

11

S

1 0 1 0 0 -001 M1,M9 P2

1 0 1 1 1 M11 010- M4,M5

1 1 0 0 0 01-0 M4,M6

1 1 0 1 0 01-1 M5,M7

1 1 1 0 1 M14 12

S

1 1 1 1 1 M15 011- M6,M7

-110 M6,M14

00

S 10-1 M9,M11 P3

0001 M1

01 -111 M7,M15

13

S S

0100 M4 1-11 M11,M15 P4

0101 M5

02 111- M14,M15

S 0110 M6

1001 M9

0111 M7

03

S 01-- M4,M5,M6,M7 P5

21

S

1011 M11

1110 M14 -11- M6,M7,M14,M15 P6

22

S

1111 M15

04

S - La mole di dati aumenta e poi diminuisce iterazione dopo iterazione;

- Viene ridotta almeno una riga dopo ogni passaggio;

- Il ciclo finisce massimo dopo n passi, dove n è il numero di variabili;

- Se un mintermine ha un “don’t care” (-) deve associarsi per ridursi solo con un altro

mintermine con un “don’t care” nella stessa sua posizione e con un valore diverso dagli

altri.

2) TROVARE LA COPERTURA MINIMA

Ci sono delle regole da seguire per selezionare gli implicanti

P1 P2 P3 P4 P5 P6 da utilizzare:

M1 1 1 1) RIGHE ESSENZIALI

M4 1 2) DOMINANZA TRA COLONNE

M5 1 1 3) DOMINANZA TRA RIGHE

M6 1 1

M7 1 1 RIGHE ESSENZIALI

M9 1 1

M11 1 1 Bisogna cercare i mintermini che hanno un solo 1 per ogni

M14 1 riga. Così facendo si trovano gli implicanti primi essenziali.

M15 1 1

O = P5 + P6 + […]

A questo punto elimino i mintermini che sono coperti dagli implicanti

P1 P2 P3 P4 primi essenziali. Adesso per criterio di dominanza tra colonne bisogna

M1 1 1 eliminare gli implicanti che hanno meno mintermini.

M9 1 1

M11 1 1

O = P5 + P6 + P2 + P3

O = (01--) + (-11-) + (-001) + (10-1)

Nel caso che con il criterio di dominanza delle colonne non si riesca a ottimizzare, bisogna

passare al criterio di dominanza delle righe. Quest’ultimo funziona al contrario, infatti

viene eliminata la riga con il maggior numero di 1, al contrario delle colonne.

In alcuni casi non è possibile determinare un’ottimizzazione dell’area usando i criteri di

dominanza. In questo caso si parla di problemi NP (non polinomiali), dei quali non si può appunto

trovare una soluzione esatta.

IL DC-SET

Anche nell’output ci può essere un “don’t care”. Avviene solo quando:

- Non verrà mai utilizzato con determinati valori di input;

- Non è possibile praticamente ottenere quei valori di input;

La creazione del DC-SET porta ad avere un circuito con prestazioni migliori, in quanto ricopre un

area minore.

Utilizzo del DC-SET nel metodo espresso(SIS)

1. TROVARE GLI IMPLICANTI PRIMI

Il DC-SET deve essere considerato come ON-SET per aumentare la probabilità di trovare implicanti

primi più grandi, che costano meno in termini di spazio.

N.B : se viene trovato un implicante primo con soli elementi del DC-SET, non deve essere

considerato.

2. TROVARE LA COPERTURA MINIMA

Il DC-SET viene considerato come OFF-SET.

PLA (Programmable Logic Array)

L’espressione trovata con il metodo Espresso è

difficilmente realizzabile nella realtà a causa della

dimensione troppo grande. Negli anni 80’ sono

riusciti a realizzarli mediante l’uso di PLA.

Ad ogni ingresso viene costruito anche il suo

negato. Per creare i punti di contatto veniva

posta una forte tensione in corrispondenza delle

giuste righe e colonne che ne saldava i contatti.

FPGA (Field Programmable Gate Array)

Circuito programmabile in grado di eseguire qualsiasi funzione booleana. Gli switch sono

programmabili ed essendo poste tra le LUT (blocchi logici) ne determinano le connessioni fra di

loro. Ogni LUT può elaborare una piccola funzione booleana oppure parte di una funzione più

grande. Così facendo si una grande funzione booleana può essere distribuita per la realizzazione

tra più LUT.

Le FPGA hanno però il difetto di essere costose, in quanto non vengono sfruttate mai al massimo

del loro potenziale avendo sempre delle LUT libere. Sono ancora utilizzate per la realizzazione di

calcolatori con in produzione meno di 10'000 copie.

ASIC

(Application specific integrated circuit)

Si tratta di un parallelepipedo di lato 1cm*1cm, sul quale sono

posizionati miliardi di transistor di dimensione inferiore a 20 nm. I

transistor sono disposti su più strati. Lo sviluppo di questo genere di

integrati è però molto costoso e per questo motivo il loro impiego

è limitato a campi in cui possano essere usati in maniera massiccia

(alti volumi di mercato), come l'elettronica di consumo

(masterizzatori, schede video, schede madri, apparati di rete,

trasmissione audio-video) mentre per usi su scala più limitata vengono preferite, ad esempio,

tecnologie riprogrammabili come le FPGA.

OTTIMIZZAZIONE DI UN CIRCUITO

Per ottimizzare al massimo un circuito bisogna passare da 2 livelli a una configurazione multilivello.

Sono realizzabili praticamente ma non esiste una teoria per fare una minimizzazione esatta. Bisogna

trovare un compromesso tra area e ritardo del circuito, in quanto in una configurazione multilivello

non sono più caratteristiche convergenti, bensì divergenti.

Per migliorare un circuito multilivello bisogna:

1- Minimizzare il circuito di partenza con il metodo Quine McCluskey;

2- Peggiorare il circuito con algoritmi di ristrutturazione;

3- Ottimizzare gli algoritmi con algoritmi di minimizzazione;

Continuare l’iterazione dei punti 2 e 3 finchè non si raggiunge un risultato soddisfacente in termini

di spazio e ritardo.

MODELLO: NETWORK DAG (N,E)

Il circuito può anche essere visto come un grafo diretto aciclico, con nodi e archi. Non si possono

infatti avere cicli perché ci potrebbero essere condizioni di instabilità I nodi sono funzioni booleane

con n ingressi e 1 uscita. ALGORITMI DI RISTRUTTURAZIONE

SWEEP

Elimina tutti i nodi con uscita non utilizzata da altri nodi.

ELIMINATE

Riduce i nodi ma aumenta i letterali. Così facendo diminuisce il ritardo ma aumenta la dimensione

del circuito.

RESUB(FX)

Aumenta i nodi ma diminuisce i letterali, aumentando il ritardo ma diminuendo la dimensione del

circuito. Resub lavora sui singoli nodi mentre Fx lavora su coppie di nodi.

ALGORITMI DI MINIMIZZAZIONE

SIMPLIFY

Automatizzazione del metodo di Quine-McCluskey, alla fine

del quale si arriva sempre ad una soluzione, anche se non si

un’approssimazione.

sa se sia la migliore oppure

FULL_SIMPLIFY

È molto più potente della Simplify, calcola il CDC-SET

(insieme dei punti che non si possono mai presentare) e

l’ODC SET (insieme dei punti che non contribuiscono a

generare l’uscita principale). CIRCUITI COMBINATORI



- OTTIMIZZAZIONE A DUE LIVELLI (area e ritardo) ESATTA



- OTTIMIZZAZIONE MULTILIVELLO (area e ritardo) APPROSSIMATA

Entrambe portano a creare porte logiche irrealizzabili, per utilizzo puramente teorico.

Per ottenere un circuito reale bisogna avere un’associazione con libreria di porte logiche.

Possono essere rappresentate da grafi (DAG). Bisogna riuscire a trovare il maggior numero di sottografi che

rappresentano il grafo. I DAG delle librerie infatti devono avere la stessa funzione booleana del DAG da

rappresentare. Si può rappresentare qualsiasi funzione booleana con una composizione di porte NAND.

I circuiti su silicio vengono realizzati con standard cell con tutte la stessa forma.

TREE MAPPING

Bisogna passare da un DAG iniziale, formato da sole porte NAND, ad un insieme di sottoalberi (tree). Così

facendo si ottiene un percorso meno ottimizzato ma realizzabile. In sis si usa per accedere alle librerie rlib.

CAMMINO CRITICO: percorso più lungo che lega un ingresso all’uscita.

CIRCUITO SEQUENZIALE

Un circuito sequenziale è un circuito che tiene conto dell’evoluzione degli stati, a differenza del circuito

combinatorio. Ha perciò bisogno di una memoria.

Solo teoricamente si possono tenere in memoria tutti gli stati e le variabili. Nel caso pratico bisogna

comprimere in modo efficiente gli ingressi.

LATCH S R Q ¬Q

1 0 1 0

0 1 0 1

0 0 Q ¬Q

1 1 NO NO

Il latch è un unità di memoria di 1 Bit. Se infatti l’input sarà 00, allora continuerà ad avere l’output

precedente diverso da da 00. Non può avvenire per nessun motivo 11, non deve essere applicato.

D-LATCH D CLK Q

(t)

1 1 1

0 1 0

- 0 Q (t-1)

Il valore di clock oscilla tra 0 e 1 con interva