Prove svolte Architettura dei calcolatori

AB

L’uguaglianza + = + viceversa era stata data a lezione solamente come esercizio, e dunque al

AB B A B

suo utilizzo senza ulteriori spiegazioni è stato attribuito un punteggio parziale.

6. [INF] Si ritrovi l’uguaglianza proposta dall’esercizio 5 minimizzando l’espressione a sinistra adoperando

una mappa di Karnaugh.

R: (3 pt) Si ha immediatamente:

BC 00 01 11 10

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

A 0 | 0 1 1 1 |

1 | 1 1 1 1 |

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

Adoperando la mappa dualmente, ovvero cercando una copertura degli zeri, si trova subito l’unico

×

rettangolo 1 1 il quale porge il risultato E = A + B + C.

7. Quanti transistor occorrono per realizzare l’espressione dell’esercizio 5 senza spreco di componenti elet-

troniche?

R: (3 pt) Potendo realizzare l’espressione a destra mediante una porta OR a tre ingressi, 4 transistor

sono sufficienti.

8. [INF] Adoperando solamente porte AND, OR e NOT nonchè flip-flop di tipo D, si realizzi un circuito

sequenziale che calcola l’OR esclusivo (cioè lo XOR) tra l’ingresso A all’istante corrente e l’uscita E dallo

stesso circuito all’istante precedente.

R: (3 pt) Ricordando l’espressione che restituisce l’OR esclusivo di due variabili A e B: E = AB + AB,

si tratta di sostituire l’ingresso B con lo stato S rappresentato dall’uscita E all’istante precedente. Se

∗

l’uscita corrente viene assegnata al valore S che sarà assunto successivamente dallo stato, in definitiva

∗

l’espressione da realizzare è: E = S = AS + AS, immediata dalla rete sequenziale seguente:

A S E

Q D

Q’ Clock

9. Un trasmettitore a 8 bit invia il codice ASCII della cifra decimale 0 assieme a un bit di parità pari.

Secondo la tradizionale tabella ASCII, la cifra decimale 0 corrisponde al codice esadecimale Se

30.

interviene un errore durante la trasmissione, quali sono le cifre decimali sbagliate che possono essere

decodificate senza che il ricevitore rilevi un errore nel corrispondente codice ricevuto?

R: (3 pt) Se l’errore coinvolgeva anche il bit di parità, allora ogni cifra decimale sbagliata poteva essere

decodificata senza rilevamento d’errore da parte del ricevitore.

Se l’errore non coinvolgeva il bit di parità, ricordando che le cifre decimali che vanno da 0 a 9 sono

mappate in codici ASCII a 7 bit a loro volta consecutivi, è sufficiente riconoscere quali tra questi codici

presentano un numero pari di variazioni di bit rispetto a Essi sono: e

0x30. 0x33, 0x35, 0x36 0x39.

Corrispondentemente, le cifre decimali che possono essere erroneamente decodificate senza che il ricevitore

rilevi un errore sono, ovviamente, 3, 5, 6 e 9.

10. Quali sono i principali protocolli di comunicazione presenti nella scheda Arduino?

R: (3 pt) Tra i principali protocolli di comunicazione ricordiamo:

- il protocollo seriale UART (Universal Asynchronous Receiver-Transmitter), abilitato dai due pin

dedicati di trasmissione (TX) e ricezione (RX);

- USB (Universal Serial Bus) attraverso cui è possibile caricare gli sketch nella memoria ROM del

microcontrollore montato sulla scheda;

2

- il protocollo sincrono I C (Inter-Integrated Circuit) attraverso cui è possibile la comunicazione con più

dispositivi collegati in serie, ognuno provvisto di un proprio indirizzo;

- SPI (Serial Peripheral Interface), per controllare uno o più dispositivi periferici.

11. Un bus parallelo a 24 linee trasmette bit a una frequenza f = 128 kHz su ogni linea. Nell’ipotesi di

24

ridurre a 9 il numero di linee, quale sarà il periodo T necessario a mantenere la stessa banda passante?

9

R: (3 pt) La banda passante viene mantenuta costante se la frequenza viene proporzionalmente aumen-

· ·

tata di un fattore 24/9: f = 24/9 f = 24/9 128 = 341.33 kHz. Il corrispondente periodo dunque è

9 24

≈

uguale a T = 1/f = 1/341.33 ms 2.9 µs.

9 9

12. Un’architettura a 32 bit ha a disposizione un’ISA formata da 16 istruzioni diverse, tra cui una che realizza

il salto incondizionato. Qual è l’estensione massima che teoricamente può avere questo tipo di salto nella

stessa architettura?

R: (3 pt) Nel caso di un codice a lunghezza costante, lo spazio che l’ISA deve mettere a disposizione

4 −

per il codice operativo delle istruzioni è di almeno 4 bit, infatti 2 = 16. Restano al più 32 4 = 28 bit

per l’argomento dell’istruzione di salto incondizionato. Potendo il salto essere in avanti o all’indietro, e

27

±(2 −1)·4

ricordando l’esistenza del salto di zero locazioni, la sua estensione massima teorica è uguale a

locazioni di memoria tenendo conto che ogni word nella stessa architettura tipicamente occupa 32 bit,

ovvero 4 byte.

Nel caso di un codice operativo a lunghezza variabile in cui all’istruzione di salto incondizionato fosse

stato attribuito il codice operativo più compatto, ovvero di un bit, si poteva raggiungere idealmente

31

±(2 − ·

un’estensione uguale a 1) 4 locazioni di memoria.

13. Avendo a disposizione una memoria RAM fisica di 4 MB, in un’architettura a 32 bit fornita di sufficiente

memoria di massa si vuole realizzare una memoria virtuale paginata che sfrutta tutto l’intervallo d’indi-

rizzamento. Assumendo che ogni pagina abbia un’estensione di 128 kB, si calcolino le dimensioni della

page table i) nel caso in cui ogni pagina possa essere collocata in una qualunque posizione in memoria

principale, e ii) nel caso in cui ogni pagina possa essere posizionata solamente in un page frame della

memoria principale. 10 17 32 17 15

· = 2 byte. La page table dovrà quindi mappare 2 /2 = 2 pagine.

R: Ogni pagina occupa 128 2 15 22

Quindi, essa sarà costituita da 2 righe. Poichè la RAM ha estensione uguale a 4 MB = 2 byte,

ciascuna riga sarà lunga i) 22 bit più il bit di presenza/assenza nel caso in cui ogni pagina possa essere

22 17 5

collocata in una qualunque posizione in memoria principale, e ii) 5 bit (da 2 /2 = 2 ) più il bit di

presenza/assenza nel caso in cui ogni pagina possa essere posizionata solamente in un page frame della

15

·

memoria principale. Le dimensioni della page table saranno quindi rispettivamente di (22 + 1) 2 bit

15

·

nel caso i), e di (5 + 1) 2 bit nel caso ii).

14. [INF] Assumendo di avere a disposizione una versione del processore ARM in grado di eseguire istruzioni

di moltiplicazione che non devono necessariamente operare su registri tutti diversi, scrivere un programma

in assembly per ARM il quale calcola la potenza di ogni elemento appartenente a un array

P-esima

numerico di dimensione presente in memoria. La procedura calcola il risultato sostituendo ogni elemento

n

in memoria con la sua potenza. Si assuma che il numero degli elementi e la potenza siano anch’essi

n P

presenti in memoria. Inoltre, non ci si preoccupi di eventuali overflow causati dalla procedura durante

il calcolo delle potenze. É gradita la presenza di commenti al codice prodotto.

R: (9 pt) Includendo il caso il che non era necessario per raggiungere il punteggio massimo:

P=0,

.data

n: .word 10

array: .word 1,2,3,4,5,6,7,8,9,10

P: .word 3

.text

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

ldr r1, =n

ldr r1, [r1] @ array length in r1

loop_el: @ iterate on elements

subs r1, r1, #1 @ decrement r1 and set status

blt exit @ if r1<0 then exit loop

ldr r2, =P

ldr r2, [r2] @ power in r2

cmp r2, #0 @ set sign from value of power

moveq r3, #1 @ if power==0 then copy result in r3

beq write @ if power==0 then go to result write

ldrne r3, [r0] @ if power!=0 then load result in r3

movne r4, r3 @ if power!=0 then copy multiply in r4

loop_pw: @ iterate on power

subs r2, r2, #1 @ decrement power and set status

write: strle r3, [r0], #4 @ if power<=0 then write result, point to next element

ble loop_el @ if power<=0 then go to next element

mul r3, r3, r4 @ multiply and copy in r3

b loop_pw @ go to next multiply

exit: 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. 2021-22 — II appello — 16 febbraio 2022

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. Si converta il numero 101.11 nella base 5 mostrando i calcoli necessari per la conversione.

2

R: (3 pt) Adoperiamo il metodo standard passando attraverso la base 10:

−1 −2

2 0

· · · ·

101.11 = 1 2 + 1 2 + 1 2 + 1 2 = 4 + 1 + 0.5 + 0.25. Ora passiamo alla base 5:

2 5| 5 .75| 5

----- ------

1| 0 .75| 3

0| 1 ... .

In conclusione quindi: 101.11 = 10.3

5

2

2. Si esegua la somma algebrica in aritmetica complemento a due a 6 bit tra il più grande numero positivo e

il più grande numero negativo che in quell’aritmetica possono essere rappresentati, esprimendo il risultato

ancora nella stessa aritmetica.

R: (3 pt) Ricordando che il più grande numero positivo e il più grande numero negativo che possono

−32

essere rappresentati in quell’aritmetica sono rispettivamente 31 come e come la

011111 100000,

− −1.

somma algebrica restituisce immediatamente corrispondente appunto a 31 32 =

111111,

3. [INF] Convertire il numero decimale 125.125 in codifica floating point IEEE 754 a 32 bit.

R: (3 pt) Riscriviamo innanzitutto il numero in base due: . Riportandolo in notazione

1111101.001

2

mantissa ed esponente: La codifica richiesta avrà dunque bit di segno non asserito,

1.111101001 E6.

2

campo esponente in notazione eccesso 127 e dunque uguale a 127 + 6 = 133 = , e infine

10000101 2

mantissa uguale a . Sistemando sui 32 bit previsti dallo standard IEEE 754 e convertendo

111101001

2

alla base esadecimale:

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

4 | 2 | F | A | 4 | 0 | ...

da cui la codifica richiesta: 0x42FA4000.

4. É maggiore l’aumento nel tempo della densità del numero dei transistor nell’unità di superficie di un chip

di memoria se essi quadruplicano ogni tre anni oppure se triplicano ogni due anni? Spiegare perchè.

R: (3 pt) Conviene verificare l’alternativa sul più breve lasso comune a entrambi i tempi di crescita: sei

anni. Se i transistor quadruplicano ogni tre anni allora dopo sei anni la densità aumenterà di un fattore

·

4 4 = 16. Se invece i transistor triplicano ogni due anni allora dopo sei anni la densità aumenterà di un

· ·

fattore 3 3 3 = 27. Quindi, è maggiore l’aumento della densità nel secondo caso.

5. É data la seguente tabella di verità di una porta logica a due in