Appunti completi corso Architettura dei Calcolatori

STRUTTURE DI CONTROLLO GOTO

Il goto del C è il semplice salto incondizionato nell'Assembly, quindi è molto semplice.

… …

goto MARCA; j MARCA

… …

MARCA: … MARCA: …

… …

IF (condizione ad una via)

Si considera la condizione falsa per il salto.

A: .word

int a; …

… IF: lw $t0, A

if (a == 5) { li $t1, 5

… bne $t0, $t1, ENDIF

} THEN: …

… ENDIF: …

IF (condizione a due vie)

Non solo si considera la condizione falsa per il salto, ma ricordati di inserire un salto alla

fine dell'if, altrimenti viene eseguito anche l'else!

A: .word

int a; …

… IF: lw $t0, A

if (a == 5) { li $t1, 5

… bne $t0, $t1, ENDIF

} else { THEN: …

… j ENDIF

} ELSE: …

… ENDIF: …

WHILE

A: .word

int a; …

… WHILE: lw $t0, A

while (a == 5) { li $t1, 5

… bne $t0, $t1, ENDWHILE

} …

… j WHILE

ENDWHILE: …

DO-WHILE

A: .word

int a; …

… DO: …

do { lw $t0, A

… li $t1, 5

} while (a == 5); beq $t0, $t1, DO

… ENDDO: …

FOR

A: .word

…

li $t0, 2

int a; sw $t0, A

… FOR: lw $t0, A

for (a = 2; a <= 5; ++a) { li $t1, 5

… bgt $t0, $t1, ENDFOR

} …

… lw $t0, A

addi $t0, $t0, 1

sw $t0, A

j FOR

ENDFOR: …

BREAK

A: .word

int a; …

… LOOP: …

while (…) { …

… lw $t0, A

if (a == 5) li $t1, 5

break; beq $t0, $t1, ENDLOOP

… …

} j LOOP

… ENDLOOP: …

TRADURRE ESPRESSIONI

Purtroppo mentre in C puoi scrivere espressioni algebriche complicate in una volta sola, in

Assembly ogni operazione matematica accetta solo due operandi, e tu devi metterti a

tradurre ogni calcolo intermedio D:

Per poterlo fare devi analizzare l'albero sintattico dell'espressione, schedulare le variabili

nei registri temporanei e utilizzare quelli per svolgere l'operazione algebrica. Nei nostri

esercizi considereremo i registri temporanei sempre in quantità sufficiente per poter fare i

calcoli (alla magistrale c'è un corso intero su come fare quando mancano i registri D: )

Per esempio divertiamoci a tradurre a - (b + (c - a)

A: .word

B: .word

C: .word

lw $t0, A

lw $t1, B

lw $t2, C

lw $t3, A

sub $t2, $t2, $t3

add $t1, $t1, $t2

sub $t0, $t0, $t1

Le condizioni algebriche funzionano in modo analogo. Calcola separatamente le due

espressioni e salva i risultati in due registri separati. Poi utilizza quei registri per attuare il

confronto.

Per le espressioni logiche invece è più incasinato, perché devi cercare te di rendere la

regola del cortocircuito usando il cervello e basta ._. esempio con a || b && !c

A: .word

B: .word

C: .word

lw $t0, A

lw $t1, B

lw $t2, C

bne $t0, $0, THEN # se A è vero tutto è vero

beq $t1, $0, ELSE # se B è falso tutto è falso

beq $t2, $0, THEN # ultima condizione utile

THEN: …

ELSE: …

L'ASSEMBLATORE traduce tutte le istruzioni simboliche nel loro equivalente in linguaggio

macchina in un file oggetto che NON è ancora in formato eseguibile. Le pseudoistruzioni

vengono tradotte nelle istruzioni native, utilizzando $at come registro d'appoggio. Per

questo motivo non va toccato perché potresti interferire con il lavoro dell'assemblatore e

alla fine non si sa che cacchio succede :)

L'assemblatore opera su ogni singolo file separatamente, come succedeva nei diversi

moduli in C. Ogni istruzione mnemonica viene tradotta nel suo corrispettivo binario. Ogni

riferimento ad un registro viene tradotto nel suo numero. E fin qui è tutto facile. MA!

I riferimenti simbolici (etichette, nomi di variabili, direttive .eqv) laddove possibile

vengono tradotti nei loro indirizzi binari. Tuttavia può tranquillamente succedere che

l'assemblatore trovi un simbolo che non è ancora stato definito (per esempio nel caso di

un salto in avanti, oppure quando si usa una variabile dichiarata in un altro modulo). Per

questo motivo l'assemblatore genera una TABELLA DEI SIMBOLI nel file oggetto.

Gli indirizzi utilizzati nel file oggetto sono virtuali e non fisici, perché ogni modulo ha le sue

variabili, le sue etichette, e l'assemblatore vede il singolo modulo come se fosse unico.

L'indirizzo effettivo verrà assegnato solo alla fine dal linker. Tra l'altro gli indirizzi di ogni

segmento (compresi il text e il data dello stesso modulo) partono da zero, quindi il file

oggetto non è assolutamente eseguibile...

Un programma in Assembly è sempre composto da più moduli per l'uso delle librerie,

quindi ci sono sempre riferimenti non risolti: questi sono i simboli esterni (presenti in un

altro modulo) oppure i simboli rilocabili (che utilizzano lo stesso indirizzo di altri simboli).

L'assemblatore unisce questi riferimenti in una TABELLA DI RILOCAZIONE. Quindi il file

oggetto generato dall'assemblatore contiene la tabella dei simboli e la tabella di

rilocazione.

Assemblaggio: PRIMO PASSO

Per prima cosa l'assemblatore non traduce istruzioni ma genera la tabella dei simboli,

che può essere costituita da:

Etichette associate a direttive .eqv nella forma <simbolo, valore>

– Etichette associate a variabili globali nella forma <simbolo, indirizzo>

– Etichette associate a istruzioni di salto nella forma <simbolo, indirizzo>

–

Assemblaggio: SECONDO PASSO

È la fase di traduzione vera e propria: usa la tabella dei simboli e crea anche una tabella

di rilocazione. Un'istruzione è tradotta in modo “incompleto” se possiede un riferimento

non risolto. Viene temporaneamente tradotto con uno zero e l'assemblatore, all'interno

della tabella di rilocazione, inserisce l'istruzione incompleta nella forma <indirizzo

istruzione, opcode istruzione, simbolo da risolvere>.

Vediamo un bell'esempio.

CODICE ASSEMBLY B

.text

B: bne $a0, $0, E

sw $a0, Y

E: lui $t0, W

ori $t0, $t0, W

,data

Y: .word 0

CODICE ASSEMBLY B – PRIMO PASSO

Dimensione testo: ---

Dimensione dati: ---

TESTO:

0 bne $a0, $0, E

4 sw $a0, Y

8 lui $t0, W

C ori $t0, $t0, W

DATI:

0 0

TABELLA DEI SIMBOLI:

B 0 T

E 8 T

Y 0 D

CODICE ASSEMBLY B – SECONDO PASSO

Dimensione testo: 0x10

Dimensione dati: 0x4

TESTO:

0 bne $a0, $0, 1 # offset: tradotto subito

4 sw $a0, 0($gp) # indirizzo: simbolo rilocabile

8 lui $t0, 0 # simbolo esterno

C ori $t0, $t0, 0 # simbolo esterno

DATI:

0 0

TABELLA DEI SIMBOLI:

B 0 T

E 8 T

Y 0 D

TABELLA DI RILOCAZIONE:

4 sw Y

8 lui W

C ori W

CONTENUTO DI UN FILE OGGETTO

Intestazione

– Contiene le dimensioni del segmento testo e del segmento dati.

Segmento di testo

– Istruzioni in linguaggio macchina non eseguibili a causa dei riferimenti non risolti.

Segmento dati

– Dati non ancora utilizzabili sempre per la presenza di riferimenti non risolti.

Tabella di rilocazione

– Istruzioni che hanno bisogno di immediati e indirizzi assoluti da sistemare.

Tabella dei simboli

– Tutte le etichette che necessitano di essere processate dal linker.

Informazioni di debug

– Extra, quella parte che si inserisce negli eseguibili in Qt :D

Esempio con due sorgenti :D

CODICE ASSEMBLY A CODICE ASSEMBLY B

.text .text

A: lw $a0, X B: bne $a0, $0, E

beq $a0, $0, E sw $a0, Y

jal B E: lui $t0, W

ori $t0, $t0, W

.data ,data

X: .word 128 Y: .word 0

W: .word 0x12345678

FILE OGGETTO A FILE OGGETTO B

Dimensione testo: 0xC Dimensione testo: 0x10

Dimensione dati: 0x8 Dimensione dati: 0x4

TESTO: TESTO:

0 lw $a0, 0($gp) 0 bne $a0, $0, 1

4 beq $a0, $0, 0 4 sw $a0, 0($gp)

8 jal 0 8 lui $t0, 0

C ori $t0, $t0, 0

DATI: DATI:

0 0x80 0 0

4 0x12345678

TABELLA DEI SIMBOLI: TABELLA DEI SIMBOLI:

A 0 T B 0 T

X 0 D E 8 T

W 4 D Y 0 D

TABELLA DI RILOCAZIONE: TABELLA DI RILOCAZIONE:

0 lw X 4 sw Y

4 beq E 8 lui W

8 jal B C ori W

Il registro global pointer è un'ottimizzazione per velocizzare il caricamento dei dati statici.

Gli indirizzi infatti hanno 32 bit, e caricare l'indirizzo assoluto significa ogni volta eseguire

due istruzioni, invece usando la furbata dell'offset il caricamento delle variabili avviene

sempre con una sola istruzione. Ma ora è il momento del LINKER!

Il linker ha il compito di unire tutti i moduli in un unico file eseguibile con un solo spazio di

indirizzamento virtuale, in base alla lunghezza dei segmenti di ogni modulo e all'indirizzo

di impianto. Calcola gli indirizzi dei riferimenti non risolti e completa la traduzione delle

istruzioni presenti nella tabella di rilocazione.

Determina l'indirizzo iniziale dei segmenti testo e dati di ogni modulo;

– Determina il nuovo valore di tutti gli indirizzi simbolici, modificati a causa dello

– spostamento della base (genera una TABELLA DEI SIMBOLI GLOBALE);

Corregge in tutti i moduli i riferimenti a indirizzi modificati, usando la tabella di

– rilocazione fornita dall'assemblatore.

L'assemblatore assegna a tutti i moduli e a tutti i segmenti l'indirizzo zero come punto di

partenza. Naturalmente non possiamo avere tutti i dati nello stesso indirizzo e ci sono

anche le limitazioni dell'hardware. Il linker quindi impila sequenzialmente ogni singolo

segmento rispettando l limiti dell'architettura su cui lavora.

La tabella dei simboli globale è l'unione delle tabelle dei simboli di tutti i moduli e ad ogni

simbolo si aggiunge l'indirizzo di base per ottenere l'indirizzo finale. Dagli esempi

otteniamo questo:

Simbolo Indirizzo iniziale Base di rilocazione Indirizzo finale

A 0 0x0040 0000 0x0040 0000

X 0 0x1000 0000 0x1000 0000

W 4 0x1000 0000 0x1000 0004

B 0 0x0040 000C 0x0040 000C

E 8 0x0040 000C 0x0040 0014

Y 0 0x1000 0008 0x1000 0008

La correzione delle istruzioni segue queste regole:

ISTR è in formato J: inserisce VS/4 nell'istruzione;

– ISTR è un salto in formato I: inserisce (VS – (IADDR + 1))/4;

– ISTR è un'operazione matematica in formato I: inserisce i 16 bit meno significativi;

– ISTR è una load/store: inserisce VS – GP;

– ISTR è una lui: inserisce i 16 bit più significativi.

–

Indirizzo Istruzione completa

Segmento codice lw $a0, 0x8000($gp)

40 0000 beq $a0, $0, 0x3

40 0004 jal 0x40 0003

40 0008 bne $a0, $0, 1

40 000C sw $a0, 0x8008($gp)

40 0010 lui $t0, 0x1000

40 0014 ori $t0, $t0, 0x0004

40 0018

Segmento testo

1000 0000 128

1000 0004 0x12345678

1000 0008 0

E quando carichiamo l'eseguibile il sistema operativo cosa fa?

Legge l'intestazione per determinare la lunghezza del testo e dei dati;

– Crea uno spazio di indirizzamento per il testo, i dati e anche per lo stack;

– Copia le istruzioni e i dati dell'eseguibile all'interno della memoria;

– Copia nello stack gli argomenti passati al programma;

– Si svuotano i registri per motivi di sicurezza e viene inizializzato lo stack pointer;

– E si va su UNIX a comandare!

–

Nel nostro processore MIPS abbiamo assunto che esistono due memorie distinte: la

Memoria Istruzioni e la Memoria Dati. Ma noi sappiamo bene che in realtà c'è una sola

memoria. Come si spiega tutto ciò? Con la memoria CACHE, cioè “nascosto” in francese.

Si tratta come vedremo di una memoria che è “nascosta” a tutti: al programmatore, al

progettista della CPU, alla CPU stessa e pure al sistema operativo!

La memoria centrale è mediamente venti volte più lenta del clock della CPU, ovvero ci

vorrebbero ben venti cicli per una lettura in memoria. Il ciclo MEM della pipeline quindi non

dovrebbe durare 0,2 ns ma ben quattro nanosecondi! Inconcepibile. Ma grazie a memorie

piccole e veloci (come di fatto sono le cache) possiamo “ingannare” la CPU.

La logica di funzionamento è questa: mettiamo una memoria piccola e veloce con un suo

controllore. Il controllore, ad ogni richiesta di accesso alla memoria da parte della CPU,

deve decidere se usare la memoria veloce da 0,2 ns o quella lenta da 4 ns. La cache in

pratica contiene copie del contenuto della memoria centrale! Il compito del controllore è

quindi capire se il dato richiesto è già nella cache e in quel caso fornirlo subito, altrimenti

bisognerà prelevarlo dalla memoria centrale, copiarlo nella cache e poi fornire il dato, e si

sarà obbligati a stallare la CPU per ben venti cicli di clock.

Le cache si rivelano utili se si applicano due principi statistici:

PRINCIPIO DI LOCALITÀ TEMPORALE: se utilizziamo un certo dato, è molto

– probabile che nelle prossime istruzioni quel dato verrà utilizzato ancora. La copia di

un dato serve più volte ed è bene tenerla in cache il più tempo possibile.

PRINCIPIO DI LOCALITÀ SPAZIALE: se la CPU accede ad un dato indirizzo,

– sicuramente i prossimi accessi avverranno su indirizzi adiacenti. Di fatto le variabili

globali sono contigue tra loro e i dati nello stack pure. Questo implica che nella

cache non si copia un singolo dato che serve al momento, ma un intero BLOCCO

di dati che può essere da 2, 4, 8, 16... byte o word. In questo modo avremo i dati

già pronti anche per le prossime richieste di accesso in memoria.

Quando il dato cercato non è in cache, si dice che abbiamo un MISS. Se invece troviamo il

dato in cache si dice che abbiamo un HIT. Ogni blocco in cache ha il bit VALID che

informa se quel blocco è occupato o meno. Ma che succede se abbiamo un miss e la

cache è tutta piena? Dobbiamo togliere un dato già presente, e come lo scegliamo?

Esistono varie politiche di sostituzione:

CASUALE: ovviamente è la scelta peggiore perché potremmo sostituire un dato

– usato frequentemente e che magari serve subito dopo.

FIFO (first in first out): un po' più sensato ma non troppo. Può darsi che il dato

– che entra per primo è comunque un dato utilizzato molto spesso. Per implementare

questa politica bisogna inserire un contatore su ogni dato e incrementarlo ad ogni

accesso in cache. Il dato con il contatore più grosso sarà quello scartato e il

contatore viene poi azzerato.

LRU (least recently used): è la scelta più sensata dal punto di vista logico, ma

– indovina un po'? È difficilissimo da implementare e non viene usato :)

Ci manca da esaminare un altro caso: che succede in caso di richiesta di scrittura della

memoria? Se il dato da scrivere è in cache, avremo il problema che in cache abbiamo un

dato aggiornato, mentre in memoria abbiamo ancora il dato vecchio. Allora esistono due

politiche di gestione delle richieste di scrittura:

WRITE THROUGH: vogliamo coerenza in tempo reale tra i dati in cache e i dati in

– memoria. Ad ogni scrittura in cache, subito andiamo ad aggiornare il dato in

memoria. Non è richiesto lo stallo della CPU perché quella nel frattempo può

continuare l'esecuzione delle istruzioni senza problemi. Diventa tutto complicato

però se la CPU chiede un dato mentre il controllore sta scrivendo in memoria...

WRITE BACK: il controllore non aggiorna il dato in memoria finché non è

– necessario farlo. Ovvero: la CPU scrive un dato che è in cache, poi chiede la lettura

di un dato che non è in cache. Il controllore preleva il dato dalla memoria, lo mette

in cache ma non c'è spazio. E che fa? DECIDE DI TOGLIERE IL DATO CHE

ABBIAMO SCRITTO E CHE NON È STATO SALVATO! In questo caso allora siamo

costretti ad aggiornare il dato in memoria. Per implementare questo sistema ogni

dato in cache deve avere un bit detto DIRTY che segnala se è stato modificato e se

deve essere riscritto in memoria. In questo caso il controllore deve copiare il dato

dalla cache alla memoria prima di inserire il dato richiesto dalla CPU. Questo

sistema richiede per forza 40 stalli nella CPU.

Esistono tre tipi di cache:

A INDIRIZZAMENTO DIRETTO

– FULLY ASSOCIATIVE

– SET-ASSOCIATIVE A N VIE

–

A INDIRIZZAMENTO DIRETTO

È la struttura più semplice. L'intero indirizzo da caricare viene “suddiviso” su diverse unità

della cache. Alcuni bit all'interno dell'indirizzo identificano il blocco da attivare all'interno

della cache. I bit meno significativi selezionano il byte o la word da attivare all'interno del

blocco selezionato, mentre i bit più significativi sono memorizzati dentro il blocco di cache

e servono a identificare il blocco di cache con il corrispettivo blocco in memoria, per

questo sono detti ETICHETTA.

Se hai capito come funziona (sicuramente no lelz) ti sarai accorto di una falla in questo

metodo: ogni blocco di memoria PUÒ STARE IN UN SOLO BLOCCO DI CACHE

SPECIFICO, ANCHE SE GLI ALTRI SONO TUTTI VUOTI!

Facciamo un esempio e un disegnino per capirci. Abbiamo una memoria centrale da 4 GB,

una cache da 64 KB con blocchi da 16 byte.

4 GB di memoria centrale = 32 bit di indirizzo

Blocchi da 16 byte = 4 bit meno significativi

64 KB / 16 byte = 4 K blocchi = 12 bit di blocco cache

= 16 bit di etichetta

= 28 bit di blocco memoria

Dato un indirizzo 00101110010111000101011100101000, può essere analizzato così:

0010111001011100 010101110010 1000

Etichetta Blocco cache Byte del blocco cache

Blocco memoria

FULLY ASSOCIATIVE

Per risolvere il problema delle cache a indirizzamento diretto, dove ogni blocco di memoria

può stare in un solo determinato blocco di cache anche se gli altri sono vuoti, si possono

realizzare le cache completamente associative, dove l'indirizzo di memoria e quello di

cache sono completamente scorrelati. Tuttavia sono difficilissime da realizzare e non

funzionano come delle vere e proprie memorie. Ad ogni richiesta di lettura il controllore

deve leggere tutti i blocchi di cache che ci sono: per farlo ogni blocco è un registro dotato

di un confrontatore. Devono esserci tanti confrontatori quanti sono i registri. È chiaro che

questa cache non funziona né come una memoria standard né come un banco di registri

standard ed è costosissima. Per questo normalmente non viene usata, tranne in un unico

caso dove i blocchi sono pochissimi, quello della MEMORIA VIRTUALE che però vedremo

nella seconda parte del corso :)

L'unica cosa di rilievo da sapere è che gli indirizzi di memoria non necessitano di bit che

identificano blocchi cache (non ce n'è bisogno), ma hanno un'unica etichetta che coincide

con il blocco di memoria. Riprendendo l'esempio precedente:

0010111001011100010101110010 1000

Etichetta Byte del blocco cache

Blocco memoria

ASSOCIATIVE A N VIE

In sostanza sono più cache a indirizzamento diretto affiancate una accanto all'altra, quindi

si possono memorizzare n dati con diversa etichetta ma stesso indice di blocco. L'insieme

di n blocchi è detto GRUPPO e di solito n vale 2, 4 e raramente 8. questo perché il

guadagno sullo hit rate diventa insignificante all'aumentare del numero di cache in

parallelo.

Studiamo le reti logiche per capire come funziona l'Assembly/ISA, perché cerchiamo di

capire come funzionano i registri e alcune componenti hardware. Naturalmente diciamo le

cose fondamentali che ci servono, perché l'anno prossimo c'è un corso intero su questo

argomento.

Cos'è una RETE LOGICA? Un oggetto (non per forza digitale, ma considereremo solo reti

elettroniche) che permette l'ingresso e l'uscita di informazioni nonché la loro elaborazione

sotto forma di segnali. Usiamo come variabile di riferimento la tensione, che oscilla tra

due valori: un valore più basso che identifichiamo con il bit 0 e un valore più alto che

identifichiamo con il bit 1. Dobbiamo assicurarci che la rete non trasporti una tensione più

bassa della soglia minima o più alta della soglia massima, altrimenti può succedere di

tutto. Inoltre non ha senso chiedersi che bit viene trasportato durante un transitorio.

Il segnale binario può essere trattato con due tipologie di reti:

RETI COMBINATORIE: sono privi di retroazione, cioè i segnali non influenzano se

– stessi. I segnali di uscita in un istante t dipendono direttamente dai segnali in

ingresso nello stesso istante (escludendo i ritardi di propagazione);

RETI SEQUENZIALI: sono reti che ammettono retroazioni, ovvero i segnali in

– uscita dipendono da quelli in ingresso che modificano anche lo stato della rete. Lo

stato quindi dipende dagli ingressi del passato.

Il comportamento delle reti può essere espresso tramite delle FUNZIONI LOGICHE o

BOOLEANE, costituite dai seguenti elementi:

VARIABILI DI COMMUTAZIONE: i singoli bit in considerazione;

– OPERATORI FONDAMENTALI: negazione (not), prodotto (and), somma (or);

– PROPRIETÀ DEGLI OPERATORI LOGICI:

– LEGGE AND OR

Identità 1 A = A 0 + A = A

Elemento nullo 0 A = 0 1 + A = 1

Idempotenza A A = A A + A = A

Inverso A !A = 0 A + !A = 1

Commutativa A B = B A A + B = B + A

Associativa (A B) C = A (B C) (A + B) + C = A + (B + C)

Distributiva A (B + C) = A B + A C A + B C = (A + B)(A + C)

Assorbimento A (A + B) = A A + A B = A

De Morgan !(A B) = !A + !B !(A + B) = !A !B

Nell'algebra booleana teoricamente esistono la sottrazione e la divisione, ma sono

operazioni inutili perché:

L'inverso di un numero è se stesso: -A = A

– Il reciproco di 1 è 1: A/B = A B se B = 1

– Il reciproco di 0 non esiste: A/B = impossibile se B = 0

–

Siccome le variabili hanno solo due valori, i teoremi e le proprietà algebriche indicate nella

tabella si dimostrano semplicemente per sostituzione :)

Gli operatori logici nelle reti elettriche sono realizzati per mezzo delle PORTE LOGICHE,

che ammettono ingressi, uscite e si comportano come i rispettivi operatori booleani.

NOT Triangolo a punta con un cerchio (o semplicemente un cerchio)

AND Semiellisse

OR Semiellisse scavato

XOR Semiellisse scavato con un tratto

NAND AND seguito dal cerchio

NOR OR seguito dal cerchio

XNOR XOR seguito dal cerchio

Ad ogni funzione combinatoria si può sempre associare un circuito digitale formato da

porte logiche, detto RETE COMBINATORIA.

ANALISI DI RETI COMBINATORIE – Dalla rete all'espressione

Sembrerebbe piuttosto facile. Basta partire dai segnali più interni (che saranno una sorta

di variabili temporanee) ed esprimere i segnali interni in funzione di quelli esterni. Fatto.

Una funzione combinatoria può essere espressa da differenti reti combinatorie: queste

vengono dette tra loro equivalenti, perché hanno la stessa tabella delle verità. Possono

tuttavia avere struttura e costi differenti.

SINTESI DI RETI COMBINATORIE

Significa passare dalla tabella delle verità alla rete logica che ammette quella tabella.

Si applicano le forme canoniche, in particolare:

Somma di Prodotti SoP (PRIMA FORMA CANONICA);

– Prodotto di Somme PoS (SECONDA FORMA CANONICA).

–

Per ogni funzione booleana esiste una e una sola forma canonica SoP e una e una sola

forma PoS.

La prima forma canonica SoP richiede due regole:

La somma logica è la somma di tutti e i soli termini prodotto delle variabili in

– ingresso corrispondenti agli 1 della funzione;

Ogni termine prodotto (mintermine) è costituito dal prodotto logico delle variabili in

– ingresso prese in forma naturale se valgono 1, in forma negata se valgono 0.

La seconda forma canonica è semplicemente la versione duale della prima:

Il prodotto logico è il prodotto di tutti e i soli termini somma delle variabili in

– ingresso corrispondenti agli 0 della funzione;

Ogni termine somma (maxtermine) è costituito dalla somma logica delle variabili in

– ingresso prese in forma naturale se valgono 0, in forma negata se valgono 1.

CALCOLO DEI RITARDI DI PROPAGAZIONE

NON si sommano i ritardi di ogni singola porta (altrimenti sei scemo) ma si calcola il

PERCORSO CRITICO, cioè quello che richiede più tempo per influenzare l'uscita ad una

variazione dell'ingresso.

I BLOCCHI COMBINATORI che andremo a studiare sono:

Multiplexer

– Demultiplexer

– Decoder

– Comparator

– Shifter combinatorio

– Half adder e Full adder

– Addizionatore a n bit in binario naturale intero

– ALU: or, and, not e somma

–

MULTIPLEXER (o multiplatore o mux)

È un componente che riceve in entrata bit da più fili e ne fa uscire uno solo. Precisamente:

Ha n INGRESSI DI SELEZIONE

– n

Ha 2 INGRESSI DATI

– Ha una uscita

– n

Gli ingressi dati sono numerati da k = 0 fino a k = 2 – 1

– Se sugli ingressi di selezione è indicato il numero binario k, il k-esimo elemento

– sarà quello inviato all'uscita.

Internamente è implementato come somma di prodotti con operandi opportunamente

negati. Esempio semplice con due ingressi dati A e B, un ingresso selezione S ed una

uscita Y. La funzione logica di questo multiplexer è (A !S) + (B S).

La sua tabella delle verità è:

A B S Y

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 1

1 1 1 1

DEMULTIPLEXER (o demultiplatore o demux)

È la variante duale del multiplexer, e ha lo scopo di reinserire su più fili i bit ricevuti da un

unico ingresso. Ovvero:

Ha n INGRESSI DI SELEZIONE

– n

Ha 2 USCITE DATI

– Ha un ingresso

– n

Le uscite dati sono numerate da k = 0 fino a k = 2 – 1

– Se sugli ingressi di selezione è indicato il numero binario k, la k-esima uscita sarà

– quella che riceverà il bit in ingresso. Le rimanenti sono a 0.

DECODER (o decodificatore)

Codifica dei bit in ingresso in una combinazione differente di bit in uscita (per esempio per

la televisione satellitare o digitale e per i lettori MP3). Precisamente:

Ha n ingressi

– n

Ha 2 uscite

– n

Le uscite sono numerate da k = 0 fino a k = 2 – 1

– Se sugli ingressi è indicato il numero binario k, la k-esima uscita assume il valore

– 1, le restanti il valore 0.

È implementato con vari AND con operandi opportunamente negati.

Esempio con due ingressi I , I e quattro uscite U , U , U , U .

1 2 1 2 3 4

I I U U U U

1 2 1 2 3 4

0 0 1 0 0 0

0 1 0 1 0 0

1 0 0 0 1 0

1 1 0 0 0 1

COMPARATOR (o comparatore)

Il nome si spiega da solo.

Ha due gruppi A e B di ingressi da n bit

– Ha tre uscite per segnalare se A < B, A = B, A > B

– Il blocco confronta i due input e attiva a 1 l'uscita relativa all'esito del confronto.

–

Esempio di tabella della verità.

A1 A0 B1 B0 < = >

0 0 0 0 0 1 0

0 0 0 1 1 0 0

0 0 1 0 1 0 0

0 0 1 1 1 0 0

0 1 0 0 0 0 1

0 1 0 1 0 1 0

0 1 1 0 1 0 0

0 1 1 1 1 0 0

1 0 0 0 0 0 1

1 0 0 1 0 0 1

1 0 1 0 0 1 0

1 0 1 1 1 0 0

1 1 0 0 0 0 1

1 1 0 1 0 0 1

1 1 1 0 0 0 1

1 1 1 1 0 1 0

SHIFTER

Circuito logico per le operazioni logiche di scorrimento.

n ingressi per i bit dell'operando

– 1 ingresso per il bit aggiunto a sx (scorrimento a destra)

– 1 ingresso per il bit aggiunto a dx (scorrimento a sinistra)

– 1 ingresso di controllo che comanda lo scorrimento

– n uscite per i bit dell'operando

–

Nota che lo scorrimento a destra equivale ad una divisione per 2 mentre lo scorrimento a

sinistra equivale ad una moltiplicazione per 2. Qua ci vuole un disegnino per capire

meglio. Qua abbiamo uno shifter a 5 ingressi.

HALF ADDER

Compie un'addizione ad un bit e genera l'eventuale riporto.

A B Carry Sum

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

Carry = A B

⊕

Sum = A B

Lo half adder si ottiene con una porta XOR e una porta AND in parallelo.

FULL ADDER

Compie un'addizione ad un bit generando l'eventuale riporto, ma tiene anche in

considerazione i riporti precedenti.

A B C_in Sum C_out

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Sum = !A!BC + !AB!C + A!B!C + ABC

= C(!A!B + AB) + !C(!AB + A!B)

⊕ ⊕ ⊕

= C!(A B) + !C(A B) # poniamo Z = A B

= C!Z + !CZ

⊕

= Z C

⊕ ⊕

= A B C_in

C_out = !ABC + A!BC + AB!C + ABC

= C(!AB + A!B) + AB(!C + C)

⊕

= AB + C_in(A B)

Puoi ricavarti facilmente lo schema della rete :)

ADDIZIONATORE a n bit in binario naturale intero

Si fa componendo insieme gli half adder e full adder. Esempio con 3 bit:

SOTTRATTORE

In modo analogo per l'addizionatore, il sottrattore è composto da un semi-sottrattore da 1

bit e più sottrattori completi da 1 bit. L'implementazione è molto simile.

Per il semi-sottrattore a 1 bit

A B Carry Diff

0 0 0 0

0 1 1 1

1 0 0 1

1 1 0 0

Carry = !(A B) # half adder negato

⊕

Diff = A B # uguale a half adder

Per il sottrattore completo a 1 bit

A B C_in Diff C_out

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Diff = !A!BC + !AB!C + A!B!C + ABC

= C(!A!B + AB) + !C(!AB + A!B)

⊕ ⊕

= C!(A B) + !C(A B)

= C!Z + !CZ

⊕

= Z C

⊕ ⊕

= A B C_in # uguale a full adder!

C_out = !A!BC + !AB!C + !ABC + ABC

= C(!A!B + AB) + !AB(!C + C)

⊕

= !AB + C_in!(A B) # simile a full adder

ALU

È il momento della verità...

Esempi di istruzioni in entrata ed esiti:

Realizzazione con multiplexer:

Realizzazione con decoder: Per fare la

sottrazione in

complemento a 2

basta impostare

Binvert = 1 e CarryIn

= 1 (in questo modo

ottieni l'inverso del

secondo operando e

aggiungi 1, come

previsto nella

codifica C2).

Queste sono tutte ALU ad 1 bit: per avere più bit basta replicare in serie questi circuiti.

Impostando Ainvert =

1 e Binvert = 1 si ha

l'operazione logica di

NOR all'uscita della

porta AND (legge di

De Morgan). In

teoria puoi pure

ottenere la NAND

ma non la hanno

messa...

La gestione

dell'OVERFLOW è

fondamentale e il

suo bit è attivato se:

oper_a = 0

oper_b = 0

result = 1

oppure

oper_a = 1

oper_b = 1

result = 0

con oper_a = a

sempre mentre

oper_b = b per

addizioni e !b per

sottrazioni.

L'istruzione slt è implementata come

sottrazione dei contenuti dei registri. Se la

differenza è negativa, il bit di segno sarà

1. Esso è contenuto nel bit più

significativo, memorizzato nel segnale set.

Questo viene posto in ingresso nel bit

meno significativo ed esce nel segnale

less. In tutti gli altri bit less è posto a zero.

Il bit Zero contiene 1 se il

risultato della ALU è zero,

altrimenti vale 0.

Il Bnegate è una

ottimizzazione per la

sottrazione in

complemento 2: unisce in

un unico segnale il Binvert

e il CarryIn.

Segnali di controllo ALU Operazione

0000 AND

0001 OR

0010 Addizione

0110 Sottrazione

0111 Set less than

1100 NOR

Ora puoi divertirti a sperimentare la ALU con questa tabella.

I segnali di controllo della ALU sono Ainvert, Bnegate e Operation (2).

I circuiti SEQUENZIALI sono circuiti logici in cui il valore di uscita in un determinato istante

non dipende solo dagli ingressi dello stesso istante, ma anche da alcuni di quelli

precedenti. Ciò comporta che una stessa sequenza di ingressi mandata in due momenti

diversi può portare ad uscite differenti. Ogni circuito sequenziale quindi, oltre che dagli

ingressi, è dotato di uno STATO che ne determina il comportamento futuro. Lo stato

rappresenta una sorta di memoria contenente informazioni sulla storia passata del circuito.

L'elemento fondamentale per la creazione di tali circuiti è il BISTABILE, che è in grado di

memorizzare un bit di informazione. Lo stato di un circuito è quindi l'insieme dei valori

contenuti nei bistabili. Essi sono appunto “stabili” e “bi” perché possono contenere due

possibili valori (0 e 1) che restano costanti, finché un segnale esterno non ne forza il

cambiamento.

I bistabili si suddividono in due categorie:

ASINCRONI: sono privi di segnali di sincronizzazione e rispondono direttamente a eventi

sul segnale di ingresso.

SINCRONI: sono sensibili ad un segnale di sincronizzazione e la transizione da uno stato

all'altro avviene tramite eventi del segnale di controllo, che normalmente è il CLOCK.

BISTABILE SR ASINCRONO

Prevede due ingressi S (set) ed R (reset) e due uscite Q e !Q tali che:

Se Q = 1 → stato di set

– Se Q = 0 → stato di reset

–

L'uscita Q quindi rappresenta il bit memorizzato.

Facendo un po' di giochetti con questo circuito scopri che:

Se (S, R) = (0, 0), il contenuto di Q si mantiene e non viene modificato;

– Se (S, R) = (1, 0), allora Q diventa 1;

– Se (S, R) = (0, 1), allora Q diventa 0;

– (S, R) = (1, 1) è una configurazione vietata perché idealmente porta a Q = !Q = 0.

–

Nel nostro PC però sto coso farebbe danni, perché le retroazioni si propagherebbero

subito e non sarebbe possibile governare i ritardi. In questo modo il circuito si

comporterebbe in modo imprevedibile. Ci serve quindi fare in modo che le transizioni di

stato avvengano solo quando lo vogliamo noi, in determinati istanti di tempo. È qui che

entra in gioco il CLOCK che è il nostro segnale di temporizzazione. Stabilisce quando le

transizioni di stato possono avvenire ed è sostanzialmente un segnale binario e

periodico.

Ogni evento può avvenire in quattro momenti diversi di un ciclo di clock:

FRONTE DI SALITA

– FRONTE DI DISCESA

– LIVELLO ALTO

– LIVELLO BASSO

–

I bistabili sincroni con temporizzazione possono essere classificati in base a due aspetti:

Relazione INGRESSO-STATO: definisce quando gli ingressi possono modificare lo

– stato del bistabile.

Temporizzazione basata sul LIVELLO del clock: durante tutto l'intervallo di

tempo in cui il clock è alto, tutti gli ingressi possono modificare lo stato.

Temporizzazione basata sul FRONTE del clock: lo stato interno viene

aggiornato solo in corrispondenza di un fronte del segnale di controllo.

Relazione STATO-USCITA: definisce quando lo stato modifica le uscite.

– Temporizzazione basata sul LIVELLO del clock: durante tutto l'intervallo di

tempo in cui il clock è alto, gli ingressi modificano anche le uscite oltre che lo

stato interno. Dispositivi con questa caratteristica sono detti LATCH.

Temporizzazione basata sul FRONTE del clock: le uscite sono aggiornate

solo in corrispondenza di un fronte del segnale di controllo. Dispositivi con

questa caratteristica sono detti FLIP FLOP.

BISTABILE SR SINCORNIZZATO (SR-LATCH)

Funziona come il bistabile SR normale, a cui si aggiunge l'ingresso del segnale di clock.

Se esso è basso gli ingressi R ed S non hanno alcun effetto e il valore di Q rimane

invariato. Solo quando il clock è alto allora R ed S possono modificare Q.

C S R Q !Q

0 X X Q !Q

1 0 0 Q !Q

1 0 1 0 1

1 1 0 1 0

1 1 1 - -

BISTABILE D SINCRONIZZATO (D-LATCH)

Ha in ingresso il dato D da memorizzare e il segnale di clock. Il dato viene memorizzato

solo quando il segnale di clock è alto.

C D Q !Q

0 X Q !Q

1 0 0 1

1 1 1 0

Tutti i tipi di bistabili hanno delle varianti con i segnali di clear e preset che forzano

rispettivamente il dato memorizzato a 0 e ad 1. Questi segnali sono asincroni, perciò

agiscono senza attendere il clock.

I latch sincroni, durante la fase alta del clock, presentano il fenomeno della

TRASPARENZA, ovvero se gli ingressi cambiano le uscite subiscono immediatamente il

cambiamento, perciò non hanno alcun effetto di memorizzazione. Per evitare questo

problema si usano i flip flop che sono costituiti da due latch in cascata, in modo da

modificare le uscite solo in corrispondenza del fronte del segnale di controllo.

La relazione stato-uscita è sul fronte mentre la relazione ingresso-stato può essere a

livello (FLIP FLOP MASTER SLAVE) oppure a fronte (FLIP FLOP EDGE TRIGGERED).

FLIP FLOP MASTER SLAVE

Sono formati da un latch D (o SR) e un SR in cascata. Il primo è il master e il secondo è lo

slave. Il clock passa dritto nel master e negato nello slave, in questo modo succede che,

durante il livello alto del clock, il master può ricevere ingressi diversi ma il dato

memorizzato (uscita slave) rimane invariato. Solo quando il clock diventa basso allora

l'uscita può cambiare. In pratica i due latch si alternano lo stato di trasparenza, ma non lo

sono mai contemporaneamente.

Nei flip flop edge triggered invece sia l'ingresso che l'uscita sono comandati a fronte. La

loro struttura interna è complicata e non la vediamo, ma dobbiamo sapere che esistono. In

questi circuiti la durata del tempo di clock deve essere abbastanza lunga da garantire che

gli ingressi e le uscite siano stabili prima dell'arrivo del fronte.

I blocchi sequenziali che andremo a vedere sono:

Registro parallelo

– Registro a scorrimento

– Banco di registri

– Memoria

–

REGISTRO PARALLELO

È formato da un vettore di flip flop D edge triggered con n ingressi ed n uscite.

Ad ogni ciclo di clock legge gli n bit in ingresso e li presenta sulle n uscite al ciclo

successivo. Per ottenere questo fenomeno bisogna utilizzare flip flop sincronizzati sul

fronte e non a livello, altrimenti il registro sarebbe trasparente!

I registri paralleli possono avere un ulteriore ingresso che è quello di caricamento

(LOAD). Se questo ingresso vale 1 allora l'uscita viene effettivamente aggiornata al ciclo

successivo con gli ingressi del ciclo precedente. Se vale 0 l'uscita viene invece mantenuta

inalterata. Questa variante è implementata usando dei multiplexer e il segnale load come

segnale di selezione.

Volendo poi si possono aggiungere tante cose belle: comando di caricamento, di

ripristino, di precarica...

REGISTRO A SCORRIMENTO

È una successione di flip flop D edge triggered con un solo ingresso seriale e n uscite.

Ad ogni ciclo di clock, fa scorrere verso destra la parola memorizzata (l'ultimo bit si perde)

e inserisce a sinistra il bit in arrivo dall'ingresso seriale. Anche in questo caso si usano flip

flop sincronizzati sul fronte, altrimenti il segnale di ingresso si propagherebbe su tutti i bit!

Come varianti abbiamo lo scorrimento a sinistra, lo scorrimento su entrambe le direzioni

(a scelta), registro universale...

Ora vogliamo vedere come gestire più registri insieme. Beh, noi sappiamo che i registri

sono tutti collegati sulle stesse linee di uscita (BUS). Come possiamo garantire che non ci

siano interferenze di segnali tra le componenti che condividono gli stessi bus? Ci vuole il

BUFFER TRI-STATE! È un semplice componente che può essere in due stati: BASSA

IMPEDENZA (permette il passaggio del bit) o ALTA IMPEDENZA (isola elettricamente

l'uscita). Tramite un ingresso di controllo OUTPUT ENABLE è possibile passare da uno

stato all'altro. Se Output Enable è attivo, il buffer è in stato di bassa impedenza. Se non è

attivo, il buffer è in stato di alta impedenza (circuito aperto). È un possibile modo per

implementare un multiplexer!

Il BANCO DI REGISTRI ci permette di gestire più registri: nel caso del MIPS ne abbiamo

32 da 32 bit. Ognuno è identificato da un numero di 5 bit. Si possono eseguire le

operazioni di lettura (i 32 bit contenuti nel registro vanno in uscita) o di scrittura (i 32 bit

in ingresso vengono memorizzati). Nel caso del MIPS abbiamo due porte di lettura

indipendenti e una porta di scrittura.

ACCESSO IN LETTURA:

Lo stato del registro non viene modificato.

– Non serve un comando esplicito di lettura, è richiesto l'indirizzo del registro

– coinvolto e la lettura avviene ad ogni ciclo di clock.

Le uscite devono essere scollegate con il buffer tri-state.

–

ACCESSO IN SCRITTURA:

Indirizzo del registro coinvolto.

– Dato da scrivere.

– Comando di scrittura (qui è richiesto).

–

Porte di lettura nel MIPS con MULTIPLEXER Il numero identificativo di

ogni registro è usato come

segnale di controllo del

multiplexer.

I due multiplexer sono tra

loro indipendenti.