Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

(1)

Università degli Studi dell’Insubria

Dipartimento di Scienze Teoriche e Applicate Architettura degli Elaboratori

Cognome e nome Matricola

Esercizio 1 (6 pts)

Qui a fianco è riportata la tabella di verità di una funzione booleana F a quattro variabili. Le X denotano input che non fanno parte del dominio di F.

(a) Scrivere un’espressione booleana, ottimizzata col metodo di Karnaugh, in prima forma canonica.

(b) Ripetere, per la seconda forma canonica.

(c) Se una porta AND (a due ingressi) costa quanto 2 porte NOT, e una porta OR (a due ingressi) costa quanto 3 porte NOT (e non è disponibile nessun altro tipo di porta), quale delle due espressioni risulterà nel circuito meno caro? (giustificare la risposta)

(a) \B \D + BD + CD (b) ( \B + D ) (B + C + \D )

(c) 1a forma: 2 NOT + 3 AND + 2 OR = 2 + 3x2 + 2x3 = 12  meno cara 2a forma: 2 NOT + 1 AND + 3 OR = 2 + 1x2 + 3x3 = 13

(Altri raggruppamenti sono possibili, ma quelli risultano in un numero maggiore di gruppi, o in gruppi di dimensione minore, non sono ottimali )

Esercizio 2 (6 pts)

Una architettura con words di 8 bits dispone di un formato in virgola mobile con 4 bit di esponente (memorizzato con spiazzamento 8) seguiti da 3 bit di mantissa. Descrivere il valore memorizzato nei seguenti floats:

(le risposte devono essere fornite in base 10, come numero con virgola oppure come frazione, cioè come rapporto di interi; non è sufficiente fornire le risposte in notazione scientifica).

(a) 00101100 (c) 11101010 (e) 00000000

(b) 10101100 (d) 00001000 (f) 01000010

(a) 0 0101 100  + 1.100b x 2^(0101b – 8) = 1.1b x 2^(–3) = 11b x 2^(–4) = 3/16 (b) 1 0101 100  come sopra ma con segno invertito, quindi –3/16

(c) 1 1101 010  - 1.010b x 2^(1101b – 8) = -1.01b x 2^5 = -101b x 2^3 = -5x8 = -40 (d) 0 0001 000  + 1.000b x 2^(0001b – 8) = 1 x 2^(-7) = 1/128

(e) 0 0000 000  rappresentazione speciale di +0

(f) 0 1000 010  + 1.010b x 2^(1000b – 8) = 1.01b x 2^0 = 1.01b = 1 + ¼

a b c d F 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 X 1 1 0 1 X 1 1 1 0 0 1 1 1 1 X

(2)

Esercizio 3 (6 pts)

Si supponga di avere a disposizione il datapath mostrato sotto (è uno di quelli visti a lezione). L’ALU dispone delle comuni funzioni (ADD, SUB, PASSA, PASSB, eccetera).

Si scriva un microprogramma che realizza la nuova istruzione, avente opcode = 39:

DBLIND regA regB

“Double Indirection”, cioè doppia indirezione(*).

L’effetto di questa istruzione è quello di memorizzare nel registro A il valore in RAM presente alla locazione registrata in RAM all’indirizzo regB. Cioè:

regA = RAM[

RAM [ regB ]

]

Non è necessario includere la fase di fetch: il microprogramma parte dal passo 3, dopo tale fase.

(*) si ricorda che “indirezione”, o “deferenziazione”, è il procedimento di ottenere un valore registrato in memoria a partire dal suo indirizzo.

Input: Output:

OP code

Step Esiti Comandi Next

Step

Effetti:

39 3 X RegBout , MARin , Read , WMFC 4 MDR  MEM[ Reg B ] 39 4 X MDRout , MARin , Read , WMFC 5 MDR  MEM[ MDR ]

39 5 X MDRout , RegBout 0 RegB  MDR , goto 0

Note:

Gli esiti della ALU, in questo esempio, non influiscono sul comportamento della Control Unit.

La ALU non prende parte a nessun passo.

Nei passi (o microistruzioni) 3 e 4, si manda il comando alla RAM e si stalla subito la Control Unit in attesa del completamento dell’accesso in RAM (con WMFC). Infatti il risultato della lettura è, in entrambi i casi, necessario da subito, al passo successivo. Non è dunque ottimizzare rimandando la WFMC di alcun passo.

Nel passo 4, il valore letto dalla RAM (ora dentro MDR) viene passato direttamente a MAR, che contiene l’indirizzo a cui effettuare la lettura successiva.

Entrambi gli accessi alla RAM sono LETTURE (comando READ).

(3)

(a) dire quanti bit di uscita ha un decoder a 4 ingressi, e specificare l’uscita per l’ingresso 0010 2^4 = 16 bits.

Con 0010, solo bit n.2 (il terzo, partendo dal n. 0) è settato, quindi: 0000 0000 0000 0100.

(b) disegnare il circuito di un latch SR usando solo le comuni porte logiche

vedi lucidi, o varianti (servono due NOR, oppure due NAND, oppure OR e due NOT) (c) disegnare il circuito di un Multiplexer a due segnali di ingresso (da un bit ciascuno)

per es: (note: S = 0  U = A. S = 1  U = B)

Esercizio 5 (6 pts)

(a) Si ha a disposizione un Clock con frequenza 1MHz, e lo si vuole impegnare per implementare un Clock con frequenza 0.5Hz. Si possono usare tutti i comuni blocchi funzionali, come quelli visti a lezione. Suggerimento: prima di procedere allo svolgimento, ci si accerti di aver capito bene quale comportamento è richiesto dal circuito realizzato; nel proprio elaborato, specificare esplicitamente la durata: del ciclo, dell’intervallo basso, e alto del clock che si vuole ottenere.

(b) Per ciascun blocco funzionale usato, specificare se si tratta di un circuito combinatorio oppure sequenziale.

Durata del ciclo del clock da realizzare: 1/(0.5Hx)= 2 secondi. (1 sec int. Basso, e 1 sec int. alto) Durata del ciclo del clock di partenza: 1/(1MHz) = 1/(1,000,000Hz) = 0.000001 sec.

Idea (ma altre soluz sono possibili): vogliamo cambiare stato nell’output ogni 1,000,000 cicli.

 usiamo registro R per contare i cicli trascorsi.

 usiamo un flip-flop F per determinare l’uscita del clock (1 nell’intervallo alto, 0 nel basso).

 quando sono stati contati 1,000,000 cicli… (1) resettiamo R e (2) flippiamo F.

 nel registro ci bastano 20 bit, perché 2^20 = 2^10 x 2^10 > 1,000 x 1,000 = 1,000,000.

 per incrementare il contatore, possiamo usare un addizionatore (anche se è sprecato).

 per paragonare il valore del contatore, possiamo usare un circuito comparatore Quindi:

b) i 2 blocchi dello schema sopra con i triangoli sono sequenziali, gli altri 4 sono combinatori

(4)

Esercizio 6 (5+1 pts)

Completare il programma Assembly MIPS qui sotto, fornendo il codice da sostituire alla parte indicata.

La sezione dati contiene una variabile n intera, seguita da un array 1 di n numeri interi, e un array 2 di altri n numeri interi.

Lo scopo del programma è scoprire se almeno uno dei due array contiene uno o più elementi strettamente negativi ( < 0 ). In questo caso, si deve eseguire il codice contrassegnato dall’ etichetta “casoA”;

altrimenti, se entrambi gli array sono costituiti solo da elementi positivi (o nulli), va eseguito il codice

contrassegnato dall’etichetta “casoB”.

Ci si sforzi di scrivere un programma il più possibile efficiente e coinciso. Bonus di 1 punto al programma corretto che usi numero minore di istruzioni.

Si forniscono a fianco le sintassi di alcune istruzioni.

.data .word

n: < qui un valore >

array_1: < qui dei valori >

array_2: < qui dei valori >

.text main:

casoB:

< qui il trattamento del caso B, e uscita.>

casoA:

< qui il trattamento del caso A, e uscita.>

SOLUZIONE 1: due cicli separati (quasi identici…), uno per array

la $t5 , n # $t5 = locazione dove e’ memorizzato n

lw $t2 , ($t5) # $t2 = valore di n = num di elementi da leggere la $t1 , array_1 # $t1 = locaz da leggere nell’array_1

ciclo1:

beqz $t2, fine_ciclo1 # se $t2 = 0, esci dal ciclo

lw $t3, ($t1) # $t3 = valore letto dall’array 1

bltz $t3, casoA # se $t3 e’ negativo, vai dirett. al caso A addi $t1, $t1, 4 # incrementa la locaz da leggere di 4 byte addi $t2, $t2, -1 # decrementa $t2 di uno

j ciclo1 fine_ciclo1:

la $t1 , array_2 # $t1 = locaz da leggere nell’array_2

lw $t2 , ($t5) # il numero di elementi da leggere viene resettato ciclo2:

beqz $t2, casoB # se anche il secondo array e’ finito, caso B lw $t3, ($t1) # $t3 = valore letto dall’array 2

bltz $t3, casoA # se $t3 e’ negativo, vai al caso A

addi $t1, $t1, 4 # incrementa la locaz da leggere di 4 byte addi $t2, $t2, -1 # decrementa $t2 di uno

j ciclo2

la reg , etichetta load address li reg , valore load immediate move regA , regB copia il registro B nel

registro A lw reg , offset(reg) load word

(l’offset è opzionale) sw reg , offset(reg) store word

(l’offset è opzionale) add reg , reg , reg add (somma) addi reg , reg , val add immediate sub reg , reg , reg subtract (differenza) sll reg , reg , val Shift left logical srl reg , reg , val Shift right logical

j etichetta jump

bgez reg , etichetta branch on greater than or equal to zero bgtz reg , etichetta branch on greater than

zero

bnez reg , etichetta branch on not equal zero

beqz reg , etichetta branch on equal zero bltz reg , etichetta branch on less than

zero

bltz reg , etichetta branch on less than or equal to zero

(5)

poi leggere da questa locazione con un LW.

Nota che il codice funziona anche se gli array sono vuoti (n = 0). Si salta fuori dal ciclo appena entrati (questo vale anche per le altre soluzioni fornite qui sotto). Questo è un vantaggio del testare la terminazione dell’array (con uscita dal ciclo) come prima cosa di ogni iterazione.

La soluzione 1 non è molto ottimizzata. Risparmiamo qualche istruzione eseguendo invece un solo ciclo: in ogni iterazione, analizziamo prima un elemento dell’array_1, poi l’elemento corrispondente dell’array_2. Questo è corretto perché i due array hanno lo stesso numero di elementi.

SOLUZIONE 2: un solo ciclo per controllare due array

lw $t5 , ($t5) # $t5 = num di elementi da leggere (da ciascun array) la $t1 , array_1 # $t1 = locaz da leggere nell’array_1

la $t2 , array_2 # $t2 = locaz da leggere nell’array_2 ciclo:

beqz $t5, casoB # se $t5 = 0 (nessun elemento rimane da leggere), caso B lw $t3, ($t1) # $t3 = valore letto dall’array 1

lw $t3, ($t2) # $t3 = valore letto dall’array 2 (sovrascrittura) bltz $t3, casoA # se $t3 e’ negativo, vai al caso A

addi $t1, $t1, 4 # incrementa la locaz da cui leggere nell’array 1 (di 4 bytes) addi $t2, $t2, 4 # incrementa la locaz da cui leggere nell’array 2 (di 4 bytes) addi $t5, $t5, -1 # decrementa il numero degli el da leggere (di uno)

j ciclo

Siamo passati da 17 a 13 istruzioni (volendo, se ne può limare via un’altra). E’ un codice anche più veloce da eseguire, perché si effettuano meno controlli di fine-array.

Ma la soluzione più compatta è un'altra ancora. Infatti, osservando il segmento “data”, possiamo notare che i due array sono contigui in memoria (*). Quindi possiamo considerarlo come un solo array, con il doppio degli elementi! Scandiamo il doppio degli elementi a partire dal primo array:

quando questo sarà finito, “sforeremo” direttamente nel secondo array. Se troviamo un solo negativo (non importa in quale dei due array), allora saltiamo al casoA. Altrimenti, se arriviamo in fondo al secondo (dopo 2n elementi), saltiamo al caso B.

(*) Nota importante: quest’ipotesi non potremmo farla in un linguaggio ad alto livello, es Java, perché non potremmo sapere dove in RAM il compilatore decida di allocare le variabili. Ma a basso livello, in MIPS, siamo noi a decidere dove e in che ordine vengano allocate le variabili.

SOLUZIONE 3: un solo ciclo per controllare un solo array (ma lungo il doppio)

lw $t5 , ($t5) # $t5 = num di elementi dell’array (el da leggere)

add $t5 , $t5, $t5 # raddoppio di $t5 (oppure con lo shift: sll $t5, $t5, 1 ) la $t1 , array_1 # $t1 = locaz da leggere (dal primo dei due array)

ciclo:

beqz $t5, casoB # se $t5 = 0 (nessun elemento rimane da leggere), caso B lw $t2, ($t1) # $t3 = valore letto dall’array

addi $t2, $t2, 4 # incrementa la locaz da cui leggere nell’array (di 4 bytes) addi $t5, $t5, -1 # decrementa il numero di el da leggere di 1

j ciclo

Siamo passati da 13 a 10 istruzioni. Fino a prova contraria, questa soluzione è la più corta possibile. E’ anche almeno tanto efficiente quanto Soluz.2, perché vengono effettuati lo stesso numero di controlli. Inoltre, questa soluzione potrebbe essere applicata anche se i due array fossero stati di dimensione diversa (a differenza della Soluz. 2).

(Ovviamente, in uno scritto basta fornire UNA soluzione, e anche molti dei commenti qui esposti sono superflui).