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

1. Conversione di base

Convertire il numero 11111111111.1 ₂ alla base 32. Si specifichino solo i simboli necessari a rappresentare 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₃₂
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. Codifica in complemento a 2

Si scriva la codifica in complemento a 2 a 8 bit del numero n in valore assoluto più piccolo che, sommato algebricamente a n₂ espresso nella medesima codifica, manda l’aritmetica del calcolatore in overflow.

R: (3 pt) Il numero n deve avere lo stesso segno di n₂ e far produrre un risultato di segno opposto: 11000000₂ + 11111111₂ = 01111111₂
Infatti, riportando l’operazione alla base 10: n + n₂ = -128 - 129 = -1 che, appunto, non è rappresentabile in complemento a due a 8 bit. Inoltre, ogni altro numero n₂ negativo scelto sarebbe stato più grande in valore assoluto.

3. Rappresentazione in floating-point

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
• 1.141E45

R: (3 pt) Dalla nota approssimazione 10^-9 ≈ 2^-30, il primo numero dopo la conversione binaria avrà un esponente dato da 10^-9 ≈ 2^-30, 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à esponente approssimativamente uguale a 2¹⁵⁰ e quindi non ammette una rappresentazione finita.

4. Legge di Moore

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. Tabella di verità e espressioni booleane

È data la seguente tabella di verità:

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'B'C + AB'C + A'BC + ABC = (A + B + C)(A' + B' + C)(A' + B + C)(A + B' + C')

6. Semplificazione con mappa di Karnaugh

Si semplifichi l’espressione prodotta all’esercizio 5 mediante una mappa di Karnaugh.

R: (3 pt)

La quale immediatamente porge l’espressione E = C.

7. Semplificazione con regole dell’algebra booleana

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'B'C + AB'C + A'BC + ABC = (A + A')(BC + B'C) = (B + B')C = C.

8. Macchina a stati finiti

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.

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

9. Codice con distanza di Hamming

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. Trasmissione di pacchetti su bus seriale

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. Banda passante per la correzione dell’errore

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. Calcoli della ALU durante un’istruzione macchina di salto relativo

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 una word) e dell’argomento 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. Variazione del duty cycle e frequenza

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. Programma in assembly per ARM

[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’esecuzione del programma la stringa comprensiva del carattere speciale finale nullo è "ben fatto!\0", al termine dell’esecuzione la stringa è stata trasformata in "!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

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

1. Conversione di base

Convertire il numero 16.16₁₀ alla base 6, mostrando i calcoli necessari.

R: (3 pt)
16|6
2|4
da cui 16.16₁₀ = 24.1₆.

2. Codifica in complemento a 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 011011, la codifica in 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. Rappresentazione in floating-point IEEE 754

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 del numero è positivo. La codifica in notazione binaria eccesso 127 dell’esponente è dunque uguale a 01111110.
La mantissa è uguale a 100100... Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo alla base esadecimale: 0x3F4CCCCC.

4. Riduzione di silicio nei chip

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.

5. Rete booleana e espressione canonica

Una rete booleana avente ingressi A, B e C è definita dall’espressione E = A'BC + AB'C. Si dia la 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'BC + AB'C:

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