Prove svolte Architettura degli elaboratori

V

1.5

0.5 1 2 3 4 5 6 7 8 ms

−0.5

−1.5

Quanta banda passante garantisce il bus?

R: (3 pt) Poiché il segnale assume almeno 4 livelli distinti, esso a ogni slot temporale trasmette un’in-

formazione equivalente a 2 bit. In più il segnale commuta con un periodo di clock uguale a 1 ms, dunque

con frequenza uguale a 1 kHz. Consequentemente la banda passante del bus è almeno uguale a 2 kbit/s.

12. Un’architettura a 32 bit può eseguire programmi che si estendono al più su 4 MB di memoria. In tal

caso, quanti bit dovrà occupare l’argomento di un’istruzione di salto incondizionato (relativo)?

22 22 20

R: (3 pt) Dall’equivalenza 4 Mbyte = 2 byte si evince che la memoria può contenere 2 /4 = 2 word,

in quanto l’architettura in questione è a 32 bit. Quindi, 20 bit sono sufficienti a indirizzare ciascun word

in memoria. Infine, è necessario 1 bit per specificare se il salto relativo avviene in avanti o all’indietro.

In conclusione, 20 + 1 = 21 bit sono sufficienti per specificare l’argomento dell’istruzione di salto relativo

nell’architettura in questione.

13. In un’architettura a 32 bit è presente una memoria virtuale la cui page table si estende su 32768 righe.

Se in quella stessa architettura la memoria principale ha una capacità uguale a 1 MB, quante pagine

riescono a trovare posto nella stessa memoria principale nell’ipotesi di un suo riempimento ottimale?

15

R: Dal numero di righe (32768 = 2 ) di cui si compone la page table si deduce il numero di pagine

32 15 17

virtuali e, quindi, la dimensione di ogni pagina: 2 /2 = 2 byte, poiché ogni indirizzo è appunto

lungo 32 bit. Poichè siamo nell’ipotesi di un riempimento ottimale, a questo punto il numero di pagine

che riescono a trovare posto nella memoria principale si ottiene dividendo la capacità della memoria

20 20 17 3

principale (1 MB = 2 byte) per la dimensione di una pagina: 2 /2 = 2 = 8 pagine.

14. [INF] Scrivere un programma in assembly per ARM il quale calcola le prime n+1 potenze intere di 2, cioé

0 1 n

2 , 2 , . . . , 2 , e contestualmente le salva a partire da quella di valore più grande in un array di dimensione

10. Il programma funzionerà regolarmente tanto nel caso n < 10 in cui l’array resta parzialmente vuoto,

quanto nel caso n > 10 in cui lo stesso array non può contenere tutte le potenze calcolate, limitandosi

dunque alle 10 potenze più grandi. Non ci si preoccupi di gestire la situazione n > 31 in cui la potenza

di 2 corrispondente non può essere rappresentata come un numero intero dall’architettura in questione.

É gradita la presenza di commenti al codice prodotto.

R: (9 pt)

@ save n largest powers-of-two 2^n, 2^(n-1), ... 2^0 in an array sized 10 elements

@ .data

n: .word 5 @ n always positive or null

array: .skip 40 @ empty array with constant word size (10)

.text

main: ldr r0, =n @

ldr r0, [r0] @ n in r0

ldr r1, =array @ array position in r1

mov r3, #10 @ array size in r3

mov r2, #1 @ r2 = 1

mov r2, r2, lsl r0 @ r2 = 2^(n+1)

loop: str r2, [r1], #4 @ store element and next element address

subs r3, r3, #1 @ decrement n and set status

beq exit @ if array filled then exit

mov r2, r2, lsr #1 @ divide current element by two

b loop @ repeat loop

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. 2023-24 — II appello — 21 febbraio 2024

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. Eseguire l’operazione 123456789A + 253 , dando il risultato nella stessa base dei termini da sommare.

11 11

Si mostrino i calcoli necessari a trovare il risultato.

R: (3 pt) Eseguire l’operazione in base 10 dopo avere effettuato le necessarie conversioni, per poi riconver-

tire il risultato nella base di partenza, è sicuramente più dispensioso in termini di tempo che non sommare

direttamente nella base 11 su cui è sufficiente “contare fino a undici”: 0,1,2,3,4,5,6,7,8,9,A,10,11,. . .

111

123456789A +

253 =

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

1234568042

Si notino i riporti generati dalle operazioni fatte su ogni colonna.

2. Si mostri com’é rappresentato il valore zero in notazione eccesso 180 a 8 bit, evidenziando gli eventuali

calcoli necessari a ottenere la stessa rappresentazione.

R: (3 pt) Per definizione di notazione eccesso N, in cui il valore zero corrisponde appunto al numero

binario N, nel nostro caso dobbiamo rappresentare 180 binario su 8 bit:

180|2

---+-

90|0

45|0

22|1

11|0

5|1

2|1

1|0

0|1

Dunque, il valore zero in notazione eccesso 180 a 8 bit è rappresentato come 10110100.

3. [INF] Si codifichi il numero decimale 1.3 in notazione floating point IEEE 754 a 32 bit.

R: (3 pt) Poichè 1.3 = 1.01001 , il numero è già nella forma esponenziale binaria desiderata: 1.01001E0.

2

La codifica richiesta avrà dunque bit di segno non asserito, esponente uguale a 127+0 = 127 = 01111111 2

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

01001

2

alla base esadecimale, considerando anche la periodicità:

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

3 | F | A | 6 | 6 |...

da cui la codifica richiesta: 0x3FA66666.

4. La legge di Moore afferma che la densità di transistor all’interno di un chip di memoria quadruplica ogni

tre anni. Un chip che nel 2020 esponeva 23 piedini di linee indirizzo e 8 piedini di linee dato, quanti

piedini di linee indirizzo dovrà esporre nel 2026 se presenta le medesime dimensioni e nell’ipotesi che il

numero di linee dato resti invariato nel tempo? 4

·

R: (3 pt) Dopo sei anni la capacità, a parità di dimensioni, è aumentata di 4 4 = 16 = 2 volte.

Nell’ipotesi che il numero di linee dato resti invariato nel tempo allora è il numero di locazioni che è

aumentato dello stesso fattore. Occorrono quindi 4 linee in più per indirizzare tutte le locazioni, con il

risultato che il numero di piedini dedicati alle linee indirizzo passa da 23 a 23 + 4 = 27.

5. Si scriva la tabella di verità del circuito mostrato in figura. Il circuito realizza una forma normale

standard? Quanti transistor sono necessari per realizzarlo?

E

A B C

R: (3 pt) Il circuito in figura realizza la forma normale standard della seguente tabella di verità:

ABC|E

000|1

001|0

010|0

011|0

100|0

101|0

110|0

111|1

Contenendo 2 porte ternarie (4 transistor ciascuna), una porta binaria (3 transistor) e 3 porte

AND OR

(un transistor ciascuna), il circuito in totale contiene 14 transistor.

NOT

6. Si dia l’espressione booleana del circuito che realizza la forma normale standard duale (in cui cioè l’uscita

è ottenuta raccogliendo in una porta i segnali che arrivano da porte ternarie della tabella di

AND OR)

verità trovata all’esercizio precedente. Poi, ricordando che (A + + = si minimizzi l’espressione

F)(A F) F,

trovata.

R: (3 pt) Dalle righe in tabella di verità associate a uscite uguali a zero si ottiene immediatamente

= (A + + + + + + + + + + + +

E B C)(A B C)(A B C)(A B C)(A B C)(A B C).

A questo punto, osservando che le sei parentesi formano tre coppie in cui ciascuna contiene una variabile

e la sua negata mentre il resto del contenuto tra parentesi è identico, adoperando la semplificazione

suggerita rispettivamente sulle parentesi 1 e 5 per eliminare 4 e 6 per eliminare 2 e 3 per eliminare

A, B,

si ottiene

C, + +

= (B + C)(A C)(A B).

E

Analogamente, adoperando la stessa semplificazione rispettivamente sulle parentesi 2 e 6 per eliminare

1 e 3 per eliminare 4 e 5 per eliminare si ottiene

A, B, C,

+ + +

= (B C)(A C)(A B).

E

Di qui in poi, qualunque eventuale ulteriore passaggio era accettabile in dipendenza dal tipo di minimiz-

zazione scelta per la soluzione.

7. [INF] Esistono in verità più mimizzazioni possibili della forma normale standard dualizzata trovata

all’esercizio precedente. Si trovino queste minimizzazioni individuando le possibili coperture in una

mappa di Karnaugh che rispettivamente le realizzano. Facoltativo: si osservino le relazioni esistenti tra

le espressioni minime trovate, spiegando come sia possibile che siano realizzate dallo stesso circuito.

R: (3 pt)

\AB 00 01 11 10

C\ -----------

0 | 1 0 0 0

1 | 0 0 1 0

Le caselle contenenti gli zeri formano una linea spezzata chiusa che può essere coperta con due diverse

successioni di rettangoli a due a due contigui, ciascuno dei quali si estende su due caselle. Una di esse

fornisce la minimizzazione già trovata, mentre l’altra copertura fornisce una minimizzazione in cui ogni

variabile è viceversa negata:

= (B + + +

E C)(A C)(A B).

Ciò è possibile perche la tabella di verità originale è generata dall’espressione booleana in forma normale

in cui evidentemente l’uscita resta identica se ogni variabile d’ingresso è

standard = + A B C, E

E ABC

sostituita dalla sua negazione. Di qui la possibilità di negare le variabili in ogni espressione booleana

che produce l’uscita corretta, inclusa in particolare l’espressione ottenuta minimizzando quella in forma

normale standard dualizzata. A {0,

8. [INF] Realizzare il circuito di una macchina a stati finiti sull’alfabeto = 1}, la quale a ogni nuovo

in cui è l’ingresso al passo corrente, è l’ingresso al passo

passo produce l’uscita = + A B C A B

E ABC

precedente, e è l’ingresso giunto a due passi precedenti. Non ci si preoccupi dell’uscita che produce il

C

circuito ai primi due istanti, ovvero fintantoche non esiste ancora un ingresso giunto due istanti prima. Per

esempio, se la sequenza d’ingresso è la corrispondente sequenza d’uscita è

00011110..., 00100110...,

oppure o ancora

01100110..., 11100110....

R: (3 pt) É sufficiente accodare due flip-flop e comporre le rispettive uscite secondo l’espressione data.

Una soluzione è fornita dal seguente circuito sequenziale, in cui si sfrutta la rete combinatoria già fornita

all’esercizio 5: E

A B C

D Q D Q

Q’ Q’

Ck

Per maggiore economicità, in luogo dell’utilizzo di due delle tre porte si potevano sfruttare le uscite

NOT

negate dai corrispondenti flip-flop.

9. É noto che un codice binario di Hamming a 7 bit accetta una sequenza di 4 bit informativi in ingresso

e successivamente produce la corrispondente codifica lunga 7 bit contenente 3 bit di

ABCD XYAZBCD

controllo Si dia la tabella di verità che definisce i valori del bit di controllo nota la sequenza

XYZ. X

binaria d’i