Prove svolte Architettura dei calcolatori

DMIF - Dipartimento di Scienze Matematiche, Informatiche e Fisiche

Università degli Studi di Udine

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

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

• 155.12 = 1 6 + 5 6 + 5 6 + 1 6 + 2 6 = 71 + 1/6 + 2/36 = 71 + 2/9 = 71.267
• 71 | 12 .222222222 | 12 2/9 | 12
• 5 | 11=B .666666666 | 2 2/3 | 20 | 5 0 | 8 0 | 8

Da cui il risultato: 5B.28 .12

2. Codifica complemento a 2 a 10 bit

È data la seguente codifica in complemento a 2 a 10 bit: n = 1111110000.C2

Esprimere lo stesso numero 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. Per valori positivi le due codifiche combaciano, sicché cambiando il segno secondo le regole del complemento a uno otteniamo subito la corrispondente codifica: n = 1111101111.C1. Alternativamente era sufficiente decrementare di uno n inteso come valore assoluto, applicando direttamente la definizione di codifica in complemento a due.

3. Codifica floating point IEEE 754 a 32 bit

[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 1.1111111/10000000 = 1.11111112. La codifica richiesta avrà dunque bit di segno non asserito, esponente uguale a 127 + 0 = 127 = 01111111 e infine mantissa uguale a 11111112. Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale: 0x3FFF0000.

4. Dimensione del chip di memoria

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à è uguale a 1000 byte?

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. Algebra booleana

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. Numero minimo di transistor

[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. Porta ternaria AND con demultiplexer

È 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 caso l’ingresso poteva essere omesso.

8. Rete sequenziale per macchina di Mealy

[INF] Progettare la rete sequenziale che realizza la macchina di Mealy che riconosce ogni sottostringa contenuta in una sequenza definita sull’alfabeto A = {0, 1}. La rete restituisce il simbolo 1 solo quando riconosce la sottostringa 01, altrimenti restituendo 0 a fronte di ogni nuovo ingresso appartenente alla sequenza.

R: (3 pt) 1/0S I S’ 0/0 S0 0 01 0 q0 q1 1 0 1/1 Q’ 0/0.

9. Efficienza di un codice di parità dispari a 16 bit

Si sceglie di definire la seguente funzione di efficienza per un codice: efficienza = distanza di Hamming / 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 costo uguale a 1/15 si ha subito efficienza = 2 / (1/15) = 30.

10. Banda di un bus parallelo a 16 linee

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 1/frequenza = 1/(532·10⁶/8) ≈ 15 ns.

11. Utilità del linguaggio Assembly per l’IoT

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. Istruzione di rientro da procedura in ARM

La realizzazione nel processore ARM di un’istruzione di rientro da procedura, che possiamo chiamare return, richiederebbe la presenza di microcodice progettato allo scopo oppure può appoggiarsi 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. Dimensione di una cache a corrispondenza diretta

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 cache, che sarà lunga 1 (validità) + 14 (TAG) + 8·2⁷ = 1039 bit. La dimensione della cache in definitiva è di 1039·2¹¹ ≈ 2127872 bit ≈ 260 kB.

14. Programma in assembly per ARM

[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 r0 la somma degli elementi contenuti nell’array. La dimensione dell’array è anch’essa reperibile in memoria.

.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 Matematiche, Informatiche e Fisiche

Università degli Studi di Udine

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

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

• 2035.4 = 2 6 + 0 6 + 3 6 + 5 6 + 4 6 = 455 + 2/3 = 455.86
• 455 | 12 .666666666 | 12 2/3 | 12
• 37 | 11=B 0 | 8 0 | 83 | 10 | 3

Da cui il risultato: 31B.8 .12

2. Codifica complemento a 2 a 10 bit

È data la seguente codifica in complemento a 2 a 10 bit: n = 1110000111.C2

Esprimere lo stesso numero 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. Per valori positivi le due codifiche combaciano, sicché cambiando il segno secondo le regole del complemento a uno otteniamo subito la corrispondente codifica: n = 1110000110.C1. Alternativamente era sufficiente decrementare di uno n inteso come valore assoluto, applicando direttamente la definizione di codifica in complemento a due.

3. Codifica floating point IEEE 754 a 32 bit

[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 1.1111111/100000000 = 1.11111112. La codifica richiesta avrà dunque bit di segno non asserito, esponente uguale a 127 + 0 = 127 = 01111111 e infine mantissa uguale a 11111112. Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale: 0x3FFF0000.

4. Dimensione del chip di memoria

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à è uguale a 100 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. Algebra booleana

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.