Prove svolte di Architettura dei calcolatori

Soluzione

A.A. 2022-23 — II appello — 14 febbraio 2023

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 32. Si specifichino solo i simboli necessari a rappresentare

1. Convertire il numero 11111111111.1 2

il risultato nella nuova base, senza viceversa definire l’intero alfabeto delle cifre in base 32.

R: (3 pt) Trattandosi di basi che sono una potenza di due, è sufficiente raggruppare gruppi di 5 cifre

binarie per riscrivere il numero nella base 32: = 1ZZ.Z

11111 .

1 11111 11111 .

32

|

|{z} | {z } {z } | {z }

1 Z Z Z

32 32 32 32

Si noti che la lettera Z è stata scelta arbitrariamente per definire la cifra più grande nella base 32. Altre

definizioni non occorrono per la specifica soluzione.

2. Si scriva la codifica in complemento a 2 a 8 bit del numero n in valore assoluto più piccolo che, sommato

2

algebricamente a n = espresso nella medesima codifica, manda l’aritmetica del calcolatore in

10000000

1

overflow.

R: (3 pt) Il numero n deve avere lo stesso segno di n e far produrre un risultato di segno opposto:

2 1

10000000 +

11111111 =

--------------

01111111 −128 − −129

Infatti, riportando l’operazione alla base 10: n + n = 1 = che, appunto, non è rappre-

1 2

sentabile in complemento a due a 8 bit. Inoltre, ogni altro numero n negativo scelto sarebbe stato più

2

grande in valore assoluto.

3. [INF] Si dica quali tra i seguenti numeri in base 10 ammettono una rappresentazione finita in floating

point IEEE 754 a 32 bit, barrando per ciascuno la corrispondente casella:

ˆ -0.1654E-9 SI NO

ˆ 1.141E45 SI NO

9 30

≈

R: (3 pt) Dalla nota approssimazione 10 2 , il primo numero dopo la conversione binaria avrà un

−9 −30

≈

esponente dato da 10 2 , quindi ammette una rappresentazione finita essendo l’intervallo degli

esponenti rappresentabili compreso tra -127 e 128. In base alla stessa formula il secondo numero avrà

45 9 5 30 5 150

≈

= (10 ) (2 ) = 2 e quindi non ammette una

esponente approssimativamente uguale a 10

rappresentazione finita.

4. La legge di Moore afferma che il numero di transistor nell’unità di memoria quadruplica ogni tre anni.

Quanto tempo è passato tra la produzione di due chip di forma quadrata aventi la medesima capacità

di memoria, se il lato del chip meno recente è lungo il doppio di quello del chip più recente?

R: (3 pt) Se la lunghezza del lato si è dimezzata allora l’area del chip più recente è un quarto di quella

del chip meno recente. Essendo la capacità di memoria identica, la densità dei transistor nel chip più

recente è dunque quadruplicata. Quindi, tra la produzione dei due chip sono trascorsi tre anni.

5. É data la seguente tabella di verità:

A B C | E

0 0 0 | 0

0 0 1 | 1

0 1 0 | 0

0 1 1 | 1

1 0 0 | 0

1 0 1 | 1

1 1 0 | 0

1 1 1 | 1

Si scrivano sia la corrispondente espressione booleana in forma canonica, generata automaticamente dal

noto algoritmo, sia quella generata dall’algoritmo duale.

R: (3 pt) Ricordando l’algoritmo in questione e la sua riscrittura duale, si ha immediatamente

E = A BC + ABC + ABC + ABC = (A + B + C)(A + B + C)(A + B + C)(A + B + C)

6. [INF] Si semplifichi l’espressione prodotta all’esercizio 5 mediante una mappa di Karnaugh.

R: (3 pt)

AB 00 01 11 10

C

0 0 0 0 0

1 1 1 1 1

la quale immediatamente porge l’espressione E = C.

7. Si semplifichi una delle due espressioni a scelta ottenute all’esercizio 5 adoperando le regole dell’algebra

booleana date a lezione.

R: (3 pt) E = A BC + ABC + ABC + ABC = (A + A)(BC + BC) = (B + B)C = C.

8. [INF] Data la macchina a stati finiti di Moore a sinistra in figura definita su un alfabeto binario, si dica

quale sequenza riconosce. Successivamente si disegni nello spazio a destra la macchina di Mealy che

riconosce la stessa sequenza.

q1/0 q1

1

1 1/0 1/0

0 0/0

0 0/0

q2/0

q0/0 q0 q2

0 0/0

1 1/0

0/0 0/0

0

0 q3/0

0 q4

1 1/0

q5/1 q4/0 q3

1 1/1

1

R: (3 pt) La macchina in figura riconosce ogni sequenza binaria formata da almeno cinque cifre uguali

a uno: 11111....

9. Si proponga un codice binario avente distanza di Hamming uguale a 3.

R: (3 pt) Per esempio un codice a ripetizione tripla del carattere.

10. Un bus seriale trasmette consecutivamente con continuità pacchetti di 8 bit, e possiede una banda

passante di 0.8 Gbit/s. Se ogni pacchetto codifica un carattere ASCII, quanti caratteri al secondo

trasmette il bus?

R: (3 pt) Se ogni pacchetto codifica un carattere ASCII, il numero di caratteri trasmessi ogni secondo

è uguale al numero di pacchetti al secondo: 0.8/8 = 0.1 Gcaratteri/s.

11. Ricordando la struttura del codice ASCII, qual è la banda passante che il bus all’esercizio precedente

riserva ai bit per la correzione dell’errore?

R: (3 pt) Poichè un carattere ASCII è codificato su 7 bit, l’ottavo bit non è informativo e può dunque

essere utilizzato per correggere l’errore sul rispettivo carattere, tipicamente verificando la parità su ogni

pacchetto. La banda passante corrispondentemente riservata dunque è uguale a 1/8 di quella complessiva:

0.8/8 = 0.1 Gbit/s.

12. La ALU di una CPU svolge dei calcoli durante l’esecuzione di un’istruzione macchina di salto relativo?

Se sı̀, che calcolo deve svolgere e dove depositerà il risultato?

R: Durante l’esecuzione di un’istruzione macchina di salto relativo da parte della CPU, la ALU deve

calcolare l’indirizzo assoluto come somma del contenuto del program counter (meno un word) e dell’ar-

gomento dell’istruzione di salto relativo. Il risultato infine deve essere caricato a sua volta nel program

counter, in modo che l’istruzione successiva che sarà eseguita sia quella a cui effettivamente si salta.

13. Si supponga che un’applicazione software in esecuzione nella scheda Arduino vari il duty cycle di un

segnale PWM. Questa variazione implica la variazione della frequenza dello stesso segnale? Si spieghi

perché.

R: (3 pt) No. La variazione del duty cycle non cambia il periodo del segnale PWM e, dunque, ne lascia

intatta la frequenza.

14. [INF] Scrivere un programma in assembly per ARM a 32 bit il quale, avendo accesso a una stringa di

caratteri ASCII presente nella memoria, la sostituisce con una nuova stringa (non inizialmente presente

in memoria) costituita dalla stringa precedente girata nel verso opposto. Per esempio, se prima dell’e-

\0

secuzione del programma la stringa comprensiva del carattere speciale finale nullo è ben fatto!\0,

al termine dell’esecuzione la stringa è stata trasformata in É gradita la presenza di

!ottaf neb\0.

commenti al codice prodotto.

R: (9 pt)

.data

string: .asciz "ben fatto!"

.text

main: ldr r0, =string @ string head position in r0

mov r1, r0 @ string tail pointer in r1

loop_1: @ advance r1 to find tail position

ldrb r3, [r1], #1 @ load char in r3, advance tail pointer

cmp r3, #0 @ if char != end_of_string...

bne loop_1 @ ...then iterate

sub r1, r1, #2 @ move back r1 to the last character (if any)

loop_2: @ iterate to swap characters

cmp r1, r0 @ if tail position <= head position...

ble exit @ ...then exit

ldrb r2, [r0] @ load leftward character in r2

ldrb r3, [r1] @ load rightward character in r3

strb r2, [r1], #-1 @ store leftward character in rightward slot, update position

strb r3, [r0], #1 @ store rightward character in leftward slot, update position

b loop_2 @ iterate on next element

exit: swi 0x11 @ exit

.end DMIF — Dipartimento di Scienze

Università degli Studi di Udine Matematiche, Informatiche e Fisiche

Esame A di Architetture degli Elaboratori

Soluzione

A.A. 2022-23 — III appello — 21 giugno 2023

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 6, mostrando i calcoli necessari.

1. Convertire il numero 16.16

10

R: (3 pt)

16|6 0.16666...|6

----|-- ------------|-

2|4 0|1

0|2

da cui 16.16 = 24.1 .

10 6 −27,

2. Si scriva, se esiste, la codifica in complemento a 2 a 6 bit del numero mostrando i calcoli necessari.

R: (3 pt) Essendo la rappresentazione binaria a 6 bit del numero 27 uguale a la codifica in

011011,

complemento a due dello stesso numero cambiato di segno si ottiene immediatamente complementando

a uno e incrementando la rappresentazione binaria vista in precedenza: 100101.

3. [INF] Si codifichi il numero 0.8 in notazione floating point IEEE 754 a 32 bit, mostrando i calcoli

necessari. −

R: (3 pt) La rappresentazione binaria del numero 0.8 è uguale a 0.1100 = 1.1001E 1 . Il segno

2 2

del numero è positivo. La codifica in notazione binaria eccesso 127 dell’esponente è dunque uguale

− 1001. Sistemando sui 32 bit previsti dallo standard

127 1 = 126 = 01111110 . La mantissa è uguale a

2

IEEE 754 e convertendo alla base esadecimale:

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

3 | F | 4 | C | C ...

da cui la codifica richiesta: 0x3F4CCCCC.

4. Un produttore di memorie a semiconduttore al silicio sa che ogni 6 anni il lato di un chip di forma

quadrata si riduce a 1/3 della lunghezza originale. In base a questa previsione, dopo 3 anni quanto silicio

sarà necessario per costruire un chip a parità di capacità di memoria, considerato che la quantità di

silicio adoperata è proporzionale alla superficie del chip? Si spieghi il risultato.

R: (3 pt) Se la lunghezza del lato si riduce a 1/3 della lunghezza originale ogni 6 anni, allora la superficie

del chip nello stesso periodo di tempo si riduce a 1/9 della superficie originale. Dunque, ogni 3 anni essa

si riduce a 1/3 di quella iniziale. Se la quantità di silicio necessaria è direttamente proporzionale alla

superficie, allora dopo 3 anni anche la quantità si riduce a 1/3 di quella necessaria inizialmente.

E = A B C + A B C. Si dia la

5. Una rete booleana avente ingressi e è definita dall’espressione

A, B C

tabella di verità della rete secondo la funzione canonica E = f (A, B, C). Fatto ciò, si scriva l’espressione

booleana in forma canonica generata automaticamente partendo dalla tabella di verità appena ottenuta.

R: (3 pt) Posto U = E, l’uscita E si ottiene immediatamente negando l’uscita nella tabella di verità di

U = A B C + A B C:

A B C | U | E

0 0 0 | 0 | 1

0 0 1 | 0 | 1

0 1 0 | 1 | 0

0 1 1 | 0 | 1

1 0 0 | 1 | 0

1 0 1 | 0 | 1

1 1 0 | 0 | 1

1 1 1 | 0 | 1

In forma canonica: E = A B C + A B C + A B C + A B C + A BC + A B C.