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

alla base 8.

1. Convertire il valore 13.2

4

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 7

1 3 222 5 2

4 4 8

2

4 4 4 8 8

4

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

10110100, 00000100.

1 2

si calcoli il rapporto n /n e se possibile lo si esprima nella stessa codifica.

1 2 |n |/|n |

R: (3 pt) Per sicurezza conviene calcolare e poi ricordare che n codifica un valore negativo.

1 2 1

−n

Dunque, cambiando di segno n si ha = Poiché n vale 4, il calcolo del rapporto è

01001100.

1 1 2

|n |/|n | |n |/n

immediato: basta traslare n di due bit, ottenendo = = Complementando

00010011.

1 1 2 1 2

−|n |/n

nuovamente si ha subito n /n = = 11101101.

1 2 1 2

Si noti che lo stesso risultato sarebbe uscito anche senza passare per il valore assoluto di n .

1

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

−1.0011E4.

R: (3 pt) Il risultato trovato sopra può essere subito messo nella forma La codifica richiesta

avrà dunque bit di segno asserito, esponente uguale a 127+4 = 131 = e infine mantissa uguale

10000011 2

a Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale:

0011.

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

C | 1 | 9 | 8 | 0 ...

da cui la codifica richiesta: 0xC1980000.

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

√ √

√ · × · ≈ ×

2: 1 2 0.5 2 1.4 0.7 cm.

i lati erano mediamente più lunghi di un fattore

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 µ.

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 µ.

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)

1

0 A B

8. [INF] Disegnare il diagramma della macchina di Mealy che, leggendo simbolo dopo simbolo una sequenza

A {0,

indefinitamente lunga di caratteri appartenenti all’alfabeto = riconosce ogni istanza delle

1, 2},

due sottosequenze e all’interno della sequenza letta. Per esempio, la sequenza

0012 0010 22001001022

contiene due istanze della sottosequenza A ogni ciclo di lettura la macchina in questione genera

0010.

le seguenti uscite: se non ha riconosciuto alcuna sottosequenza; nell’istante in cui riconosce la

0 1

sottosequenza nell’istante in cui riconosce la sottosequenza

0010; 2 0012.

R: (3 pt) 0 / 1

1,2 / 0 0 / 0

0 / 0 1 / 0

0 / 0

q0 q1 q2 q3

1,2 / 0

2 / 0 1 / 0 v 2 / 2

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

2

− −

informativi sono N log (N + 1). Per esempio, il codice di Hamming a 7 bit contiene 7 3 = 4 bit

2

informativi.

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 pro-

grammato 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.

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.

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.

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

10+6 30−16 14

all’interno di ogni pagina di 2 = 64 kB. La page table dunque dev’essere formata da 2 = 2

righe indirizzate dalla parte più significativa dell’indirizzo. Ciascuna di esse dovrà contenere 22 bit per

22

indirizzare ciascuna pagina casualmente in 2 = 4 Mbyte più il bit di presenza/assenza della pagina in

14

memoria fisica, per un totale di 2 righe di 23 bit ciascuna.

14. [INF] Con riferimento all’esercizio 8, scrivere un programma in assembly per ARM il quale legge dal

A {0,1,2}

file di testo una sequenza di caratteri appartenenti all’alfabeto = e quindi realizza

file.txt

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 Il programma termina allorquando il file è stato letto interamente.

r5.

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: ;; end

swi 0x11 ; exit

.end 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.<