Prove svolte Architettura

Complementando a 2 il risultato si ottiene equivalente al valore 62. La somma cercata vale

0111110,

−62.

dunque Per la validità della codifica associata si veda l’esercizio 4.

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

−1.1111E5

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

2

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

10000100 2

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

1111.

semplicità di lettura:

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

C | 2 | 7 | 8 | 0 ...

da cui la codifica richiesta: 0xC27800000.

4. Con riferimento all’esercizio 2, si spieghi come la ALU decide la validità del risultato di un’operazione

di somma in complemento a 2.

R: (3 pt) Se i termini da sommare differiscono nel bit più significativo allora hanno segno diverso e non

possono dare luogo a overflow. Altrimenti, se il bit più significativo del risultato è diverso da quello dei

due termini da sommare allora c’è certamente overflow, viceversa non può esserci overflow.

5. Adoperando le regole di equivalenza booleana, calcolare quanto vale E nell’espressione seguente:

·

E = ABC AC ·

R: (3 pt) Sfruttando le regole di De Morgan si ha E = ABC (A + C) = AABC + ABCC = 0 + ABC.

6. [INF] Verificare il risultato ottenuto sopra con una mappa di Karnaugh.

R: (3 pt)

BC 00 01 11 10

A

0 0 0 0 0

1 0 0 1 0

da cui E = ABC.

7. Si può realizzare l’espressione all’esercizio 5 avendo a disposizione solamente delle porte NOR a 3 ingressi?

Motivare la risposta. A + B + C = A + A + A + B + B + B + C + C + C.

R: (3 pt) Sı̀. Con 4 porte: ABC =

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

A {A,

indefinitamente lunga di caratteri appartenenti all’alfabeto = ω}, riconosce le parole

B, R, ARABA,

Il simbolo ω è adoperato esclusivamente per terminare ogni parola presente nella

BAR, BARABBA, BARBA.

sequenza: per esempio, la sequenza contiene la sola parola riconoscibile Per

ARABBAωBARωωARBAω BAR.

semplicità si omettano dal disegno tutti gli archi associati a simboli appartenenti a parole non riconoscibili

e le etichette degli stati non iniziali.

R: (3 pt) Se tutti gli archi associati a simboli appartenenti a parole non riconoscibili, omessi in figura,

producono in uscita per esempio il simbolo (“bocciato”), allora la macchina disegnata qui sotto rico-

B

nosce, partendo dallo stato etichettato, solo le parole richieste. Esse infatti vengono segnalate da una

sequenza non vuota di simboli (“accettato”) aperta e terminata da (“riconosciuto”).

A R

/R

ω

A/A R/A A/A B/A A/A

/R

ω I /R

ω

/R

ω

B/A A/A R/A B/A A/A

B/A B/A A/A

A/A /R

ω

dati ridondanti dei codici di Hamming, fermandosi al

9. Si tracci una funzione che esprime il rapporto dati totali

valore in ascissa dati totali = 16.

R: (3 pt) Per esempio:

ridondanti

4

3

2

1 1 3 7 15 totali

10. Un protocollo I/O di tipo programmato è sempre meno efficiente di uno di tipo controllato? Si motivi

la risposta.

R: (3 pt) Poichè la gestione dell’interruzione in un protocollo I/O di tipo programmato è più semplice,

rapida ed economica dell’interruzione in un protocollo I/O di tipo controllato, allora il primo può essere

più efficiente del secondo a patto che la richiesta di servizio arrivi in modo periodico e altamente frequente,

in modo da soddisfare tutte (o quasi tutte) le interruzioni.

11. Che cos’è il bus skew ?

R: (3 pt) Il bus skew è il disallineamento temporale dei bit trasmessi lungo un bus parallelo, a causa

dell’imperfetta sincronizzazione tra le linee che formano il bus.

12. Quali registri della CPU rendono possibile il costrutto di programmazione noto come chiamata a proce-

dura?

R: (3 pt) Il registro comunemente chiamato link register e, addizionalmente, il registro stack pointer.

13. In una memoria principale segmentata di 1 MB trovano posto segmenti tutti uguali di 8 kB. Nel tentativo

di caricare un nuovo segmento, il sistema operativo trova la memoria piena. Quanti segmenti stanno in

quel momento occupando la memoria nel caso di occupazione in assoluto più efficiente? Quanti nel caso

di occupazione in assoluto meno efficiente? Qual è la percentuale di occupazione della memoria nei due

casi?

R: Se è piena, allora la regione di memoria in questione non contiene spazi liberi contigui di 8 kB. Nel

caso di occupazione in assoluto più efficiente essa è occupata da 1024/8 = 128 segmenti, corrispondenti a

una percentuale di utilizzo del 100%, mentre nel caso di occupazione in assoluto meno efficiente esiste uno

spazio di 8 kB meno 1 Byte tra ogni coppia di segmenti occupati di 8 kB adiacenti. In questo caso, dunque,

20 ≈

i segmenti presenti sono 2 /(8192 + 8191) 64.004. In altre parole, i 64 segmenti occupano in totale

·

64 (8192 + 8191) = 1048512 Byte. La memoria libera ma inutilizzabile ammonta quindi al totale delle

20 6+13 20

· − · ·

locazioni di 1 Byte lasciate vuote: 64 8191 + (2 1048512) = 64 8191 + 64 = 64 8192 = 2 = 2 /2

Byte, dunque equivalenti esattamente al 50% della memoria principale.

14. [INF] Scrivere un programma in assembly per ARM il quale calcola la somma S dei primi n + 1 termini

n i

P

di una serie geometrica di ragione naturale positiva r: S = r . Per esempio, se r = 2 e n = 4

i=0

avremo 4

X i 0 1 2 3 4

S = 2 = 2 + 2 + 2 + 2 + 2 = 1 + 2 + 4 + 8 + 16 = 31.

i=0

Per convenzione il programma legge r e n da due word consecutivi in memoria, e li carica rispettivamente

nei registri e Inoltre mantiene il registro per il risultato. Infine, salva il risultato nel word in

r1 r3. r4 ≥ ≥

cui inizialmente compariva r. Per semplicità si assuma in ogni caso r 0 e n 0, e non ci preoccupi del

possibile overflow del risultato.

R: (9 pt)

.data

inout: .word 2,6 ; root, power

.text

main: ldr r0, =inout ; memory addr in r0

ldr r1, [r0], #4 ; load root in r1, update r0

mov r2, #1 ; set r2 to initial multiplier

mov r4, #1 ; set result in r4 to power^0 = 1

ldr r3, [r0] ; load power in r3

cmp r3, #0 ; if power null..

beq fine ; ..then go to end

loop: mul r2, r1, r2 ; r2 = r2*r1 = ... = r2^n

add r4, r4, r2 ; r4 = r4+r2

subs r3, r3, #1 ; decrement power in r3

bne loop ; loop again if power is not zero

fine: ldr r0, =inout ; memory addr in r0

str r4, [r0] ; save output

swi 0x11 ; end

.end DMIF — Dipartimento di Scienze

Università degli Studi di Udine Matematiche, Informatiche e Fisiche

Esame A di Architetture degli Elaboratori

Soluzione

A.A. 2018-19 — I appello — 29 gennaio 2019

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.

alla base 16.

1. Convertire il valore 3030.030 4

R: (3 pt) Trattandosi di basi che sono una potenza di due, conviene dapprima convertire alla base 2

e poi raggruppare le quartine risultanti per riscrivere il valore nella base 16, tenendo conto del periodo

nella parte decimale: | 1100 .0011 = CC.30C

0000 1100

3030.030 = 3030.030030 = 30|30.03|00|30 = 1100 2 2 2

4 4 2 2 16

4 |

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

| | 3 0

C C C

16 16

16 16 16

2. Sono date le seguenti codifiche in complemento a 2 a 8 bit: n = n = Si calcolino

10001000, 00001000.

1 2

risultato ed eventuale resto della divisione n : n e, se possibile, si esprima il risultato nella stessa

1 2

codifica. −n

R: (3 pt) Per sicurezza conviene complementare n per cambiarne il segno negativo: = 01111000.

1 1

Eseguiamo ora la divisione che, essendo il divisore una potenza di due, coincide con una translazione

verso destra del dividendo di un numero di posizioni uguale al numero di zeri del divisore:

01111000:00001000 = 00001111, resto 00000000 −00001111

che, restituendo il segno originale, è ancora codificabile in complemento a 2 e vale =

Si noti che la stessa operazione poteva essere eseguita direttamente nel dominio codificato.

11110001.

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

−1.111

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

E3.

2

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

10000010 2

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

111

2

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

C | 1 | 7 | 0 | 0 ...

da cui la codifica richiesta: 0xC1700000. 6

4. Qual è la potenza di quattro che offre la miglior approssimazione di un Megabyte (cioè 1 MB = 10

byte)?

Facoltativo e solo dopo avere terminato gli altri esercizi: Si dimostri l’affermazione appena fatta.

R: (3 pt) La potenza in questione è 10. Infatti, la potenza di quattro che offre la migliore approssimazione

10 5 10

≈ −

di 1 kB è 2 = 4 byte, che prevede un errore di circa il 2%: 1000 2 (1 0, 02). La stessa

2 20 2 20

≈ − −

considerazione vale per il MB in quanto quadrato del kB: 1000 2 (1 0, 02) = 2 (1 + 0, 0004

20 10

− −

≈ (1 0, 04) = 4 (1 0, 04), quindi con un’approssimazione per difetto di circa il 4%.

0, 04) 2

5. Adoperando le regole di equivalenza booleana, ridurre l’espressione seguente in modo che ammetta una

realizzazione adoperando esclusivamente porte NOT e porte OR a due ingressi:

E = ABC + BDD.

R: (3 pt) E = A+B +C +(B +D)D = A+B +C +BD+D = A+B(1+D)+C +D = (A+B)+(C +D).

6. [INF] Verificare il risultato ottenuto sopra con una mappa di Karnaugh.

×

R: (3 pt) La tabella di verità permette quattro coperture di 4 2 simboli confermando il risultato

1,

dell’esercizio precedente:

AB 00 01 11 10

CD

00 1 1 1 1 |

01 1 1 1 1 | |

11 1 1 1 1 |

10 1 1 0 1

-------

<--- --->

7. Realizzare la rete booleana appena progettata adoperando un multiplexer, di cui non occorre esplicitare

il circuito logico.

R: (3 pt) É sufficiente scegliere un multiplexer a 16 ingressi e 4 controlli collegati rispettivamente ad

e poi connettere a una sorgente in tensione (per esempio 5V) tutti gli ingressi fuorchè quello

ABCD,

associato al controllo che invece sarà connesso alla massa 0V.

1110,

8. [INF] Progettare la macchina di Mealy che riconosce ogni sottostringa contenuta in una sequenza

010

A {0,

definita sull’alfabeto = 1},