Prove svolte Architettura dei calcolatori

DMIF — Dipartimento di Scienze

Università degli Studi di Udine Matematiche, Informatiche e Fisiche

Esame A di Architetture degli Elaboratori

Soluzione

A.A. 2018-19 — II appello — 12 febbraio 2019

N.B.: il punteggio associato ad ogni domanda è solo una misura della difficoltà, e peso, di ogni domanda.

Per calcolare il voto complessivo bisogna normalizzare a 32.

1. Convertire il valore 155.12 alla base 12.

6

R: (3 pt) Conviene dapprima convertire alla base 10 e poi alla base 12:

−1 −2

2 1 0

· · · · ·

155.12 = 1 6 + 5 6 + 5 6 + 1 6 + 2 6 = 71 + 1/6 + 2/36 = 71 + 2/9 = 71.2

6

71 | 12 .222222222 | 12 2/9 | 12

------- --------------- --> --------

5 | 11=B .666666666 | 2 2/3 | 2

0 | 5 0 | 8 0 | 8

da cui il risultato: 5B.28 .

12

2. É data la seguente codifica in complemento a 2 a 10 bit: n = Esprimere lo stesso numero

1111110000.

C2

in codifica in complemento a 1 a 10 bit. −n

R: (3 pt) Poiché n codifica un numero negativo, cambiandolo di segno otteniamo = 0000010000.

C2 C2

Per valori positivi le due codifiche combaciano, sicché cambiando il segno secondo le regole del comple-

mento a uno otteniamo subito la corrispondente codifica: n = Alternativamente era

1111101111.

C1

sufficiente decrementare di uno n inteso come valore assoluto, applicando direttamente la definizione

C2

di codifica in complemento a due.

3. [INF] Fornire in codifica floating point IEEE 754 a 32 bit il risultato (non intero) della divisione 255/128.

R: (3 pt) La stessa divisione espressa in notazione binaria risulta essere immediatamente uguale a

/10000000 = . La codifica richiesta avrà dunque bit di segno non asserito, espo-

11111111 1.1111111

2 2 2

nente uguale a 127 + 0 = 127 = e infine mantissa uguale a . Sistemando sui 32 bit

01111111 1111111

2 2

previsti dallo standard IEEE 754 e convertendo alla base esadecimale:

0|0 1 1 1 1 1 1 1|1 1 1 1 1 1 1 0 ...

3 | F | F | F | 0 ...

da cui la codifica richiesta: 0x3FFF0000. 10 2

4. Un chip di memoria di forma quadrata e capacità uguale a 10 byte occupa un’area di 0.25 cm nella

scheda madre. Quanto misura il lato di una memoria di forma e densità identica se la sua capacità è

12 byte?

uguale a 10

R: (3 pt) Se la capacità della seconda è 100 volte quella della prima allora il nuovo quadrato sarà di

2

·

100 0.25 = 25 cm . Di conseguenza, il nuovo lato misura 5 cm.

5. Adoperando le regole dell’algebra booleana, dimostrare che C + CD = D + CD. Successivamente si

minimizzi la stessa espressione attraverso l’uso di una tabella di verità.

R: (3 pt) C + CD = C(D + D) + CD = CD + CD + CD = CD + (C + C)D = CD + D = D + CD.

Dalla tabella di verità si verifica immediatamente l’uguaglianza C + CD = C + D.

6. [INF] Si dica qual è il numero minimo di transistor necessari per realizzare la rete logica che calcola

l’espressione dell’esercizio precedente.

R: (3 pt) C + D = C + D. Ricordando che la porta NOR si compone di due transistor e la NOT di un

transistor, si deduce che il numero minimo di transistor necessari per realizzare l’espressione in questione

è 3.

7. É possibile realizzare una porta ternaria AND adoperando un demultiplexer a tre ingressi? In caso

affermativo se ne dia la rete logica.

R: (3 pt) É sufficiente collegare l’ingresso del demultiplexer al valore alto di tensione e l’uscita associata

all’ingresso all’uscita della rete logica richiesta. Era accettato anche l’utilizzo di un decoder, nel qual

111

caso l’ingresso poteva essere omesso.

8. [INF] Progettare la rete sequenziale che realizza la macchina di Mealy che riconosce ogni sottostringa

A {0,

contenuta in una sequenza definita sull’alfabeto = 1}. La rete restituisce il simbolo solo

01 1

quando riconosce la sottostringa, altrimenti restituendo a fronte di ogni nuovo ingresso appartenente

0

alla sequenza.

R: (3 pt) 1/0

S I S’ E I E

0/0 S

0 0 0

1

0 0

1 0 q0 q1

0

1 1 0 S’

Q D

1 1 0 1 1/1 Q’

0/0 Clock distanza di Hamming .

9. Si sceglie di definire la seguente funzione di efficienza per un codice: efficienza = costo

Calcolare l’efficienza di un codice di parità dispari a 16 bit.

R: (3 pt) Ricordando che un codice di parità dispari a 16 bit ha distanza di Hamming uguale a 2 e

2

costo uguale a 1/15 si ha subito efficienza = = 30.

1/15

10. Un bus parallelo a 16 linee trasmette bit sincronizzati, simultaneamente su ciascuna linea a una frequenza

uguale a 532 MHz. A quale valore dovrebbe essere reimpostato il periodo di clock affinché il bus abbia

globalmente una banda di 133 Mbyte/s ? ·

R: (3 pt) Considerato che adoperando l’impostazione iniziale la banda del bus è uguale a 16 532

·

Mbit/s, corrispondente a 2 532 Mbyte/s, per ottenere la banda richiesta occorre dividere la frequenza

·

di clock per un fattore 8. Infatti: 2 532/8 = 133 Mbyte/s. Dunque, il periodo di clock risulta uguale a

6

· ≈

1/frequenza = 1/(532 10 /8) 15 ns.

11. La conoscenza del linguaggio Assembly è utile allo sviluppatore di applicazioni per l’Internet of Things?

Se sı̀, si dia un possibile contesto applicativo tra quelli visti durante il corso.

R: (3 pt) Sı̀. Per esempio, al fine di ottimizzare le prestazioni del microcontrollore della scheda Arduino,

molto adoperata per realizzare applicazioni nell’Internet of Things le quali spesso richiedono tempi di

esecuzione molto ridotti pur nel contesto di hardware estremamente semplice ed economico.

12. La realizzazione nel processore ARM di un’istruzione di rientro da procedura, che possiamo chia-

mare richiederebbe la presenza di microcodice progettato allo scopo oppure può appoggiarsi

return,

direttamente su microcodice che realizza istruzioni già esistenti?

R: (3 pt) Un’istruzione di rientro da procedura corrisponde a spostare il contenuto del link register (lr)

nel program counter (pc), entrambi realizzati all’interno del processore ARM su registri accessibili con

le stesse modalità di tutti gli altri. Quindi, l’istruzione equivale a una move: mov pc,lr.

13. Assumendo uno spazio indirizzabile di memoria uguale a 4 GB, qual è la dimensione di una cache a

corrispondenza diretta (cioè ad accesso diretto) nel caso in cui ogni linea di cache occupa 128 byte e il

campo TAG che contiene l’indirizzo di memoria da cui proviene la linea è lungo 14 bit?

R: Lo spazio indirizzabile in questione è associato a indirizzi di 32 bit. Di questi, i 14 bit più significativi

indirizzano la linea e quindi fanno parte del campo TAG. In parallelo, i 7 meno significativi indirizzano

il word e l’eventuale byte nella linea. Conseguentemente restano 11 bit per indirizzare ogni riga della

7

·

cache, che sarà lunga 1 (validità) + 14 (TAG) + 8 2 = 1039 bit. La dimensione della cache in definitiva

11

· ≈

è di 1039 2 = 2127872 bit 260 kB.

14. [INF] Scrivere un programma in assembly per ARM il quale riordina in senso contrario gli elementi di

un array presente in memoria. Inoltre, restituisce nel registro la somma degli elementi contenuti

r0

nell’array. La dimensione dell’array è anch’essa reperibile in memoria.

R: (9 pt) .data

array_dim:

.word 5

array_el:

.word 18, 12, 1, 14, 3

.text

main: ldr r0, =array_dim

ldr r0, [r0] ; array dim in r0

ldr r1, =array_el ; base in r1

ldr r2, =array_el ; base in r2

add r2, r2, r0, lsl #2 ; base + dim in r2

sub r2, r2, #4 ; last element position in r2

mov r0, #0 ; reset r0 (accumulator)

cmp r2, r1 ; set initial status

blt end ; exit if array dim <=0

swap: ldr r3, [r1] ; load lower element in r3

ldr r4, [r2] ; load higher element in r4

add r0, r0, r3 ; accumulate lower element

addgt r0, r0, r4 ; if r2-r1>0 then accumulate also higher element

str r3, [r2], #-4 ; store r3 in higher position, update pos

str r4, [r1], #4 ; store r4 in lower position, update pos

cmp r2, r1 ; if r2-r1..

bge swap ; ..>=0 then repeat

end: swi 0x11 ; exit

.end DMIF — Dipartimento di Scienze

Università degli Studi di Udine Matematiche, Informatiche e Fisiche

Esame B di Architetture degli Elaboratori

Soluzione

A.A. 2018-19 — II appello — 12 febbraio 2019

N.B.: il punteggio associato ad ogni domanda è solo una misura della difficoltà, e peso, di ogni domanda.

Per calcolare il voto complessivo bisogna normalizzare a 32.

1. Convertire il valore 2035.4 alla base 12.

6

R: (3 pt) Conviene dapprima convertire alla base 10 e poi alla base 12:

−1

3 2 1 0

· · · · ·

2035.4 = 2 6 + 0 6 + 3 6 + 5 6 + 4 6 = 455 + 2/3 = 455.8

6

455 | 12 .666666666 | 12 2/3 | 12

------- --------------- --> --------

37 | 11=B 0 | 8 0 | 8

3 | 1

0 | 3

da cui il risultato: 31B.8 .

12

2. É data la seguente codifica in complemento a 2 a 10 bit: n = Esprimere lo stesso numero

1110000111.

C2

in codifica in complemento a 1 a 10 bit. −n

R: (3 pt) Poiché n codifica un numero negativo, cambiandolo di segno otteniamo = 0001111001.

C2 C2

Per valori positivi le due codifiche combaciano, sicché cambiando il segno secondo le regole del comple-

mento a uno otteniamo subito la corrispondente codifica: n = Alternativamente era

1110000110.

C1

sufficiente decrementare di uno n inteso come valore assoluto, applicando direttamente la definizione

C2

di codifica in complemento a due.

3. [INF] Fornire in codifica floating point IEEE 754 a 32 bit il risultato (non intero) della divisione 510/256.

R: (3 pt) La stessa divisione espressa in notazione binaria risulta essere immediatamente uguale a

/100000000 = . La codifica richiesta avrà dunque bit di segno non asserito,

111111110 1.1111111

2 2 2

esponente uguale a 127 + 0 = 127 = e infine mantissa uguale a . Sistemando sui 32

01111111 1111111

2 2

bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale:

0|0 1 1 1 1 1 1 1|1 1 1 1 1 1 1 0 ...

3 | F | F | F | 0 ...

da cui la codifica richiesta: 0x3FFF0000. 12 2

4. Un chip di memoria di forma quadrata e capacità uguale a 10 byte occupa un’area di 1.6 cm nella

scheda madre. Quanto misura il lato di una memoria di forma e densità identica se la sua capacità è

13

uguale a 10 byte?

R: (3 pt) Se la capacità della seconda è 10 volte quella della prima allora il nuovo quadrato sarà di

2

·

10 1.6 = 16 cm . Di conseguenza, il nuovo lato misura 4 cm.

5. Adoperando le regole dell’algebra booleana, dimostrare che B + AB = A + AB. Successivamente si

minimizzi la stessa espressione attraverso l’uso di una tabella di verità.

R: (3 pt) B + AB = (A + A)B + AB = AB + AB + AB = AB + A(B + B) = AB + A = A + AB.