Prove svolte Architettura degli elaboratori

Al fine di rispettare questa nuova specifica, quanto dovrà valere la nuova frequenza?

3

·

R: (3 pt) Poiché in un secondo ogni linea trasmette 128 10 bit, la banda del bus inizialmente vale

3 3

· · ·

8 128 10 = 1024 10 bit/s = 1 Mbit/s. Se si desidera che dopo l’espansione la nuova banda valga

3

· · ·

3 Mbit/s, le corrispondenti 12 linee dovranno essere tali da garantire 12 f = 3 1024 10 bit/s. Di

e

3

·

qui, f = 3072/12 10 = 256 kHz. Intuitivamente, infatti, se il numero di linee aumenta del 50% e se la

e

frequenza raddoppia, allora la banda del bus triplica.

12. Su un’architettura a 32 bit viene realizzata un’ISA di 34 istruzioni a lunghezza fissa. Quante istruzioni

al momento indefinite potranno essere aggiunte in futuro all’ISA nell’ipotesi di mantenere il vincolo

sulla lunghezza fissa? Quanti bit sono al momento disponibili per la specifica degli argomenti nell’ISA

realizzato? −

R: (3 pt) Qualunque lunghezza fissa L scelta va bene. Fatta questa scelta, restano disponibili 32 L

bit per specificare gli argomenti delle istruzioni. Se per semplicità si sceglie la lunghezza più piccola,

allora un set di 34 istruzioni richiede 6 bit per essere specificato. Idealmente, quindi, restano indefinite

6 −

2 34 = 30 codifiche su cui possono essere realizzate ulteriori 30 istruzioni di 6 bit. Evidentemente, la

−

parte restante di 32 6 = 26 bit è disponibile per specificare gli argomenti delle istruzioni.

13. La memoria virtuale paginata di un’architettura a 32 bit, fornita di sufficiente memoria di massa, è

20

configurata per indirizzare 2 pagine. La stessa architettura ha a disposizione una memoria fisica in

5

grado di contenere 2 pagine in caso di riempimento ottimale della stessa memoria. Mantenendo fermo il

vincolo sul riempimento ottimale, ovvero nel caso in cui ogni pagina possa essere posizionata solamente

in un page frame della memoria principale, si calcolino le dimensioni della page table.

20 5 20

R: La page table dovrà mappare 2 pagine su 2 page frame. Quindi, essa sarà costituita da 2 righe

ciascuna delle quali formata dai 5 bit necessari a indirizzare un page frame più il bit di presenza/assenza.

20 ·

Ne risulta una dimensione di 2 6 = 6291456 bit = 768 kB.

14. [INF] Si consideri il seguente programma in assembly per ARM il quale, potendo avere accesso in memoria

a un array di interi positivi di lunghezza parimenti specificata in memoria, crea una corrispondente

n

lista concatenata (eventualmente vuota):

.data

head: .skip 4

stringa:

.asciz "inputLista.txt"

.text

main: @@ create list containing the array elements

ldr r4, =head @ list head address in r4

ldr r0, =stringa @ string head address in r0

mov r1, #0 @ read mode

swi 0x66 @ open file in read mode

mov r2, r0 @ save file handler

swi 0x6c @ read number of integers

movs r3, r0 @ save number of integers in r3, check if empty list

streq r3, [r4] @ #NULL head if empty list

beq end @ go to end if empty list

next_node: @@ create nodes

mov r0, #8 @ allocate 8 bytes

swi 0x12 @ create node, pointer in r0

str r0, [r4] @ enlist new node

mov r6, r0 @ copy new address in current pointer

mov r0, r2 @ load file handler

swi 0x6c @ read integer from file

mov r5, r0 @ save integer in r5

str r5, [r6,#4] @ store integer, point to address

subs r3, r3, #1 @ decrement r3

movne r4, r6 @ if another node then advance r4

bne next_node @ next read

str r3, [r6] @ last node points to NULL

end: @@ exit

swi 0x11

.end

Si aggiunga al programma del codice che realizza la procedura seguente: se la lista possiede un nodo

che contiene come dato il numero intero 6, alla lista viene concatenato un nuovo nodo contenente il

numero intero 8 in posizione immediatamente successiva a quello che contiene il numero intero 6. Per

esempio, se la lista concatena gli elementi allora la stessa lista successivamente all’esecuzione

1,6,23,5

della procedura concatenerà gli elementi Non occorre trascrivere il codice soprastante nella

1,6,8,23,5.

soluzione. É gradita la presenza di commenti al codice prodotto.

R: (9 pt)

.data

head: .skip 4

stringa:

.asciz "inputLista.txt"

.text

main: ldr r4, =head @ list head address in r4

ldr r0, =stringa @ string head address in r0

mov r1, #0 @ read mode

swi 0x66 @ open file in read mode

mov r2, r0 @ save file handler

swi 0x6c @ read number of integers

movs r3, r0 @ save number of integers in r3, check if empty list

streq r3, [r4] @ #NULL head if empty list

beq end @ go directly to end if empty list

next_node:

mov r0, #8 @ allocate 8 bytes

swi 0x12 @ create node, pointer in r0

str r0, [r4] @ enlist new node

mov r6, r0 @ copy new address in current pointer

mov r0, r2 @ load file handler

swi 0x6c @ read integer from file

mov r5, r0 @ save integer in r5

str r5, [r6,#4] @ store integer, point to address

subs r3, r3, #1 @ decrement r3

movne r4, r6 @ if another node then advance r4

bne next_node @ next read

str r3, [r6] @ last node points to NULL

@@ exercise about node insertion starts here

ldr r4, =head @ copy head address in r4

cmp r4, #0 @ if at the last node..

beq end @ ..then exit

loop: ldr r4, [r4] @ advance current pointer

cmp r4, #0 @ if at the last node..

beq end @ ..then exit

ldr r6, [r4,#4] @ load integer on next node in r6

cmp r6, #6 @ if data == 6 then..

moveq r0, #8 @ ..allocate 8 bytes

swieq 0x12 @ ..create node, pointer in r0

addeq r6, r6, #2 @ ..set r6 to integer 8

streq r6, [r0,#4] @ ..store integer 8 in new node

ldreq r5, [r4] @ ..load pointer to next (old) node in r5

streq r5, [r0] @ ..store pointer to next (old) node in new node

streq r0, [r4] @ ..store pointer to new node in current node

b loop @ make another loop

end: @ exit

swi 0x11

.end DMIF — Dipartimento di Scienze

Università degli Studi di Udine Matematiche, Informatiche e Fisiche

Esame di Architetture degli Elaboratori

Soluzione

A.A. 2022-23 — V appello — 19 settembre 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.

1. Si dica quali dei seguenti numeri sono rappresentati scorrettamente nelle rispettive basi, spiegando perchè:

6 , 11 , 5 , 0 , F .

7 10 0 1 15

R: (3 pt) 5 è scorretto in quanto non ha senso definire una base (o alfabeto) contenente zero cifre (o

0

simboli). F è scorretto in quanto convenzionalmente F è, nell’ordine, la sedicesima cifra in una base.

15 · fornisce

2. Mostrare che l’operazione 2 (−1) eseguita interamente in aritmetica complemento a due a 4 bit

il risultato effettivamente corretto.

R: (3 pt) Codifichiamo i due operandi in aritmetica complemento a due a 4 bit ed eseguiamone la

moltiplicazione:

0010 *

1111 =

--------

0010

0010

0010

0010

--------

11110 -> (scarto bit di overflow) -> 1110 −2,

Ora, il numero in aritmetica complemento a due a 4 bit corrisponde effettivamente a che è il

1110

risultato cercato.

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

R: (3 pt) Poichè 0.6 = 1001 , il numero 1.6 può essere messo nella forma esponenziale binaria 1.1001... E0.

2 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

1001...

2

alla base esadecimale:

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

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

da cui la codifica richiesta: 0x3FCCCCCC.

4. Se la densità del numero dei transistor raddoppia ogni anno e mezzo, si dica di quante volte aumenta la

capacità di un chip di memoria a parità di superficie dopo 9 anni.

R: (3 pt) Dal dato sulla crescita si evince che, a parità di superficie, il numero dei transistor all’interno

· ·

di un chip di memoria cresce di un fattore 4 ogni tre anni e quindi di un fattore 4 4 4 = 64 dopo nove

anni.

5. É possibile realizzare una porta binaria adoperando solo porte binarie utilizzando le regole

NAND NOR

dell’algebra booleana date a lezione? Se sı̀, la si derivi mediante opportune espressioni booleane.

R: (3 pt) Ricordando l’uguaglianza = + e adoperando le regole di De Morgan, + = e

A A A A B A B

= + si ottiene

AB A B,

= = + = + + + = + + + = + + + + + + +

E AB A B A A B B A A B B A A B B A A B B.

6. Comunque sia stato risolto l’esercizio 5, di quante porte binarie necessita la rete booleana rappre-

NOR

sentata dall’espressione appena trovata?

R: (3 pt) Quattro porte binarie sono sufficienti per realizzare la rete proposta. Infatti, leggendo

NOR

= + come una formula di riduzione di complessità, l’espressione all’esercizio

stavolta l’uguaglianza A A A

5 può essere vista come = + =

E A B AB.

7. [INF] Comunque sia stato risolto l’esercizio 5, si dicano quanti transistor occorrono per realizzare l’e-

spressione booleana = adoperando, rispettivamente: i) solo porte binarie; ii) solo porte

E AB NAND NOR

binarie; iii) porte binarie e porte unarie.

NOR NOT

R: (3 pt) Ricordando che una porta binaria e una porta binaria sono realizzate con 2 transistor

NAND NOR

e, invece, una porta unaria è realizzata con un solo transistor, l’espressione in questione è realizzabile

NOT

rispettivamente con: i) 2 transistor (una porta binaria ii) 8 transistor (quattro porte binarie

NAND); NOR);

iii) 5 transistor (una porta binaria e tre porte unarie

NOR NOT). A {0,

8. [INF] Realizzare una macchina di Mealy o di Moore sull’alfabeto = 1}, la quale in uscita riproduce

la sequenza che giunge in ingresso. Se però i tre simboli più recenti ricevuti sono tutti uguali a 1,

allora il simbolo che viene prodotto in uscita dopo di essi è in ogni caso uguale a e, successivamente,

1

la macchina riprende a riprodurre la sequenza d’ingresso. Per esempio, se la sequenza d’ingresso è

la corrispondente sequenza d’uscita è

100111000111100..., 100111100111110....

R: (3 pt) Una soluzione è fornita dalla seguente macchina di Mealy:

1/1 1/1 1/1

q0 q1 q2 q3 1/1

0/0 0/0 0/0 0/1

9. Un trasmettitore di pacchetti di 8 bit introduce quattro bit di controllo su ogni pacchetto per rendere

la trasmissione affidabile, adoperando un codice a ripetizione doppia di ogni bit. Quindi, se per esempio

la parola da codificare è allora viene trasmesso un pacchetto contenente la corrispondente codifica

1001

Qual è la percentuale di codifiche tra quelle complessivamente disponibili che il codice sfrutta

11000011.

effettivamente?