Appunti completi corso Architettura dei Calcolatori
Anteprima
ESTRATTO DOCUMENTO
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.
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Architettura dei calcolatori e sistemi operativi e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Negrini Roberto.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato