Prove svolte di Architettura degli elaboratori

Università degli Studi di Udine

Matematiche, Informatiche e Fisiche

Esame A di Architetture degli Elaboratori

Soluzione A.A. 2017-18 — III appello — 19 giugno 2018

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 (circa).

Convertire il valore alla base 8

1. Convertire il valore 13.24

R: (3 pt) Trattandosi di basi che sono una potenza di due, conviene dapprima convertire alla base 2 e poi raggruppare le cifre risultanti per riscrivere il valore nella base 8: = 01 11 . = 0 111 . . = 7.52

13.2 = 01 11 . 10 101010 101 010 .4 2 2 2 8|{z} |{z} |{z}| {z } |{z} |{z}|{z} |{z} |{z} 1 3 71 3 222 5 24 4 824 4 4 8 842.

Calcolare il rapporto tra codifiche

Sono date le seguenti codifiche in complemento a 2 a 8 bit: n = 10110100, n = 00000100.

R: (3 pt) Per sicurezza conviene calcolare |n₁|/|n₂| e poi ricordare che n₁ codifica un valore negativo. Dunque, cambiando di segno n₁ si ha n₁/n₂ = 01001100. Poiché n₂ vale 4, il calcolo del rapporto è immediato: basta traslare n₁ di due bit, ottenendo 00010011. Complementando nuovamente si ha subito n₁/n₂ = 11101101. Si noti che lo stesso risultato sarebbe uscito anche senza passare per il valore assoluto di n₁.

Codifica in floating point IEEE 754

3. [INF] Fornire il risultato dell’esercizio precedente in codifica floating point IEEE 754 a 32 bit.

R: (3 pt) Il risultato trovato sopra può essere subito messo nella forma −1.0011E4. La codifica richiesta avrà dunque bit di segno asserito, esponente uguale a 127+4 = 131 = 10000011 e infine mantissa uguale 0011. Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale: C | 1 | 9 | 8 | 0... da cui la codifica richiesta: 0xC1980000.

La legge di Moore

4. La legge di Moore afferma che il numero di transistor nell’unità di memoria quadruplica ogni tre anni. Se un chip di memoria di forma rettangolare oggi misura mediamente 1×0.5 cm, quanto misuravano mediamente i lati di un chip analogo 18 mesi fa, a parità di capacità di memoria?

R: (3 pt) Se il numero di transistor nell’unità di memoria quadruplica ogni tre anni allora il raddoppio della densità avviene ogni anno e mezzo. Quindi, a parità di capacità di memoria un anno e mezzo prima i lati erano mediamente più lunghi di un fattore √2: 1.4×0.7 cm.

Listino prezzi

5. È dato il seguente listino prezzi in microeuro (µ):

• Porta NAND 1 µ
• Porta NOR 5 µ
• Porta NOT 10 µ
• Porta AND 20 µ
• Porta OR 20 µ

Adoperando le regole di equivalenza booleana, dare il circuito che realizza l’espressione booleana A + B al costo minimo, quantificando inoltre il costo stesso.

R: (3 pt) Adoperando le regole di De Morgan si ha A + B = AB = AB, che adopera una porta NAND e una porta NOT costando dunque 1 + 10 = 11 µ. Questa soluzione ha ricevuto punteggio pieno. Il costo minimo in assoluto si trovava ricordando l’uguaglianza E = E·E·E. Di qui l’ulteriore espressione AB = AB·AB che, richiedendo solo due porte NAND, costa 1 + 1 = 2 µ.

Ulteriore ottimizzazione del circuito

6. [INF] Si provi ad abbassare ulteriormente il costo del circuito all’esercizio precedente, ricordando che esso può accedere anche alle tensioni nulla e di alimentazione le quali rappresentano, rispettivamente, gli stati logici 0 e 1.

R: (3 pt) Continuando ad adoperare le regole di De Morgan si ha A + B = AB = AB + 0 = AB·1, che adoperando due porte NAND costa 1 + 1 = 2 µ. Chi all’esercizio precedente aveva già trovato la soluzione in assoluto migliore non poteva comunque scendere sotto il costo di 1 + 1 = 2 µ.

Realizzazione con multiplexer

7. Realizzare l’espressione all’esercizio 5 adoperando un multiplexer, il cui circuito combinatorio dev’essere chiaramente esplicitato all’interno della rete booleana proposta.

R: (3 pt)

10 A B

Diagramma della macchina di Mealy

8. [INF] Disegnare il diagramma della macchina di Mealy che, leggendo simbolo dopo simbolo una sequenza indefinitamente lunga di caratteri appartenenti all’alfabeto A = {0, 1, 2}, riconosce ogni istanza delle due sottosequenze 0010 e 0012 all'interno della sequenza letta. Per esempio, la sequenza 2200100122 contiene due istanze della sottosequenza 0010. A ogni ciclo di lettura la macchina in questione genera le seguenti uscite: 0 se non ha riconosciuto alcuna sottosequenza; 1 nell’istante in cui riconosce la sottosequenza 0010; 2 nell’istante in cui riconosce la sottosequenza 0012.

R: (3 pt) 0 / 1 1,2 / 0 0 / 0 0 / 0 q0 q1 q2 q3 1,2 / 0 2 / 0 1 / 0 v 2 / 2

Codice di Hamming

9. Quanti bit contenenti dati informativi possiede un codice di Hamming a N bit?

R: (3 pt) I codici di Hamming a N bit contengono log₂(N + 1) bit di controllo. Di conseguenza i bit informativi sono N − log₂(N + 1). Per esempio, il codice di Hamming a 7 bit contiene 7 − 3 = 4 bit informativi.

Protocollo I/O programmato e controllato

10. In un elementare sistema che deve servire un’unica periferica si deve scegliere tra un protocollo I/O, di tipo programmato oppure controllato. Di essi si sa che il primo serve la periferica in 3 ms, mentre il secondo necessita di 4 ms per espletare il medesimo servizio. In più si sa che la periferica può chiedere di essere servita esattamente ogni 100 ms, tuttavia questo avviene appunto solo se la periferica ha fatto richiesta; altrimenti essa non necessita di essere servita, e forse farà una richiesta trascorsi esattamente altri 100 ms. Sulla base di questi dati si calcoli qual è il minimo numero di richieste che rende mediamente conveniente adoperare il protocollo I/O di tipo programmato.

R: (3 pt) Se la periferica necessita di essere servita ogni 100 ms allora il protocollo I/O di tipo programmato fa guadagnare al sistema 1 ms di tempo di calcolo ogni 100 ms. Il punto di parità tra i due protocolli avviene quando la periferica dev’essere mediamente servita tre volte su quattro, cioè il 75% delle volte. In tal caso anche il protocollo I/O di tipo controllato richiede 12 ms di tempo al sistema per le interruzioni. In definitiva il numero medio minimo di interruzioni che rende conveniente adoperare il protocollo I/O di tipo programmato è uguale a 3 ogni 400 ms.

Richieste che saturano il sistema

11. Con riferimento all'esercizio precedente, si dica quante sono le richieste che saturano il sistema nel caso in cui si scelga di usare a) il protocollo I/O di tipo programmato e b) il protocollo I/O di tipo controllato.

R: (3 pt) Il protocollo I/O di tipo programmato è saturato quando la periferica richiede il servizio ogni 100 ms. Il protocollo I/O di tipo controllato non può essere mai saturato da una periferica che richiede il servizio ogni 100 ms, in quanto la serve in 4 ms.

Logical shift right vs arithmetic shift right

12. Si dia un esempio in cui un’operazione di logical shift right (lsr) eseguita da un processore ARM non corrisponde all’operazione di arithmetic shift right (asr) eseguita sullo stesso dato.

R: (3 pt) Le due operazioni hanno esito diverso per esempio quando il dato rappresenta la codifica in complemento a due di un valore intero negativo.

Dimensionamento della page table

13. Una memoria virtuale di 1 GB è organizzata in pagine di 64 kB, che possono trovare posto in memoria di massa oppure in posizioni casuali di una memoria principale di 4 MB. Non è prevista la presenza di pagine virtuali inesistenti. Come dev’essere dimensionata la corrispondente page table?

R: La memoria principale necessita di 30 bit per essere indirizzata. Di essi, 16 individuano l’offset all’interno di ogni pagina di 2¹⁶ = 64 kB. La page table dunque dev’essere formata da 2¹⁴ = 16384 righe indirizzate dalla parte più significativa dell’indirizzo. Ciascuna di esse dovrà contenere 22 bit per indirizzare ciascuna pagina casualmente in 2²² = 4 MB più il bit di presenza/assenza della pagina in memoria fisica, per un totale di 2¹⁴ righe di 23 bit ciascuna.

Programma in assembly per ARM

14. [INF] Con riferimento all’esercizio 8, scrivere un programma in assembly per ARM il quale legge dal file di testo input.txt una sequenza di caratteri appartenenti all’alfabeto A = {0,1,2} e quindi realizza la macchina sequenziale colà descritta. Il file di testo per comodità riporta nella prima riga il numero di caratteri presenti nel file a partire dalla seconda riga. L’output è scritto a ogni ciclo di lettura nel registro r5. Il programma termina allorquando il file è stato letto interamente.

R: (9 pt)

.data
stringa: .asciiz "input.txt"
.text
main: ldr r0, =stringa ; file name address in r0
mov r1, #0 ; read mode
swi 0x66 ; open file in read mode
mov r2, r0 ; save file handler
swi 0x6c ; read number of integers
mov r3, r0 ; save number of integers in r3
mov r6, #1 ; r6 loaded with one
machine_q0:
subs r3, r3, r6 ; decrement number of integers
beq end ; and exit if zero
mov r5, #0 ; output zero
mov r0, r2 ; load file handler
swi 0x6c ; read integer from file
cmp r0, #0 ; if input==0
beq machine_q1 ; jump to state q1
b machine_q0 ; else stay in current state
machine_q1:
subs r3, r3, r6 ; decrement number of integers
beq end ; and exit if zero
mov r5, #0 ; output zero
mov r0, r2 ; load file handler
swi 0x6c ; read integer from file
cmp r0, #0 ; if input==0
beq machine_q2 ; jump to state q2
b machine_q0 ; else jump to state q0
machine_q2:
subs r3, r3, r6 ; decrement number of integers
beq end ; and exit if zero
mov r5, #0 ; output zero
mov r0, r2 ; load file handler
swi 0x6c ; read integer from file
cmp r0, #1 ; if
beq machine_q3 ; input==1 jump to state q3
bgt machine_q0 ; input==2 jump to state q0
blt machine_q2 ; input==0 stay in current state
machine_q3:
subs r3, r3, r6 ; decrement number of integers
beq end ; and exit if zero
mov r0, r2 ; load file handler
swi 0x6c ; read integer from file
cmp r0, #0 ; if
bne non_zero ; input!=0 jump to non_zero
mov r5, #1 ; else output one
b machine_q1 ; and jump to state q1
non_zero:
cmp r0, #1 ; if
bne non_one ; input!=1 jump to non_one
mov r5, #0 ; else output zero
b machine_q0 ; and jump to state q0
non_one:
mov r5, #2 ; output two
b machine_q0 ; jump to state q0
end: swi 0x11 ; exit

DMIF — Dipartimento di Scienze

Università degli Studi di Udine

Matematiche, Informatiche e Fisiche

Esame di Architetture degli Elaboratori

Soluzione A.A. 2017-18 — IV appello — 3 luglio 2018

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