Cognome e Nome: Matricola:
Arch. degli Elaboratori (Mod. 2 – 2 a prova intermedia) (30 Maggio 2019)
Esercizio 1
Considerare un sistema di memoria virtuale con indirizzo virtuale di 32 b, che include una TLB 2-way set associative composta da 256 set con TAG = 13 b. Inoltre, ciascun ingresso della TLB ha dimensione 4 B, ed ` e composto da:
4 b (valid,dirty,reference,protection) : TAG : N PAG FISICA.
Rispondere ai seguenti quesiti:
1. Individuare la dimensione della pagina fisica e la dimensione in bit del numero di pagina virtuale.
2. Qual ` e la dimensione in byte della TLB?
3. Qual ` e la dimensione in bit dell’indirizzo fisico?
4. Dato l’indirizzo virtuale 0x10080F48, individuare il SET della TLB e il numero di pagina virtuale. In quale caso si potrebbe verificare un TLB miss. Come potrebbe evolvere il miss?
Soluzione
1. Poich` e gli insiemi sono 256, allora INDEX = log
2256 = 8 b. Quindi PAGE OFFSET = DIM IND VIRT - INDEX - TAG = 32 - 8 - 13 = 11 b, per cui DIM PAGE = 2
11= 2048 B.
N PAG VIRTUALE = DIM IND VIRT - PAGE OFFSET = 32 - 11 = 21 b.
2. 4B * NUM SET * NUM VIE = 4 ∗ 2 ∗ 2
8= 2
11= 2048 B.
3. N PAG FISICA = DIM ENTRY - 4BIT - TAG = 32 - 4 - 13 = 15 b.
PAG FISICA = N PAG FISICA + PAGE OFFSET = 15 + 11 = 26 b.
4. 0x100A0F48 = 0001 0000 0000 1000 0000 1111 0100 1000 TAG (13 b) = 0001 0000 0000 1
INDEX (8 b) = 000 0000 1 OFFSET (11 b) = 111 0100 1000
N PAG VIRTUALE = TAG : OFFEST = 000100000000100000001
Il SET ` e quello con INDEX uguale a 1 (il secondo). Il miss si potrebbe verificare perch´ e entrambe le vie sono NOT VALID, oppure perch´ e quelle VALID non contengono il TAG: ”0001000000001”.
Il TLB miss potrebbe evolvere in un page fault nel caso in cui la entry della PT individuata dal numero di pagina virtale 000100000000100000001 sia non valida. Altrimenti, se l’ingresso ` e valido, il TLB miss viene risolto usando i dati della PT per aggiornare una dei due ingressi della TLB (via 0 o 1).
Esercizio 2
Tradurre in assembly MIPS la funzione C int find min(int *v, int n, int *min)
che calcola il minimo di un vettore v di interi di dimensione n. Ritorna -1 se n <= 0, 1 altrimenti.
Il risultato deve essere memorizzato nella variabile min passata per indirizzo.
int find_min(int *v, int n, int *min) { int i, m;
if (n <= 0) return -1;
m = *v;
v = v+1;
for (i=1; i < n; i++) {
if (*v < m) m = *v;
v = v+1;
}
*min = m;
return 1;
}
1. Tradurre in C con if-goto e goto.
2. Tradurre in assembly MIPS, considerando l’aritmetica dei puntatiori (v = v+1) che tiene conto del sizeof(int)).
Usare i registri $s0 e $s1 per memorizzare le variabili locali i e m.
E’ inoltre possibile usare pseudo-istruzioni come blt, ble, bgt e bge, con anche costanti al posto di uno dei due registri.
Infine si ricorda che, per convenzione, i registri $t0, . . . , $t9, $a0, . . . , $a3, $v0, $v1 sono preservati (salvati e ripri- stinati) dalla funzione chiamante (solo se necessario).
Soluzione
Il codice con if-goto:
int find_min(int *v, int n, int *min) { int i, m;
if (n > 0) goto next1;
return -1;
next1:
m = *v;
v = v+1; /* incrementa l’ind. del sizeof del tipo */
i = 1;
init_for:
if (i >= n) goto exit_for;
if (*v >= m) goto next2;
m = *v;
next2:
v = v+1; /* incrementa l’ind. del sizeof del tipo */
i++;
goto init_for;
exit_for:
*min = m;
return 1;
}
Traduzione MIPS¿
find_min:
# PARAMETRI: $a0= v, $a1 = n, $a2 = min
# VARIABILI LOCALI: $s0 = i $s1 = m
addi $sp, $sp, -8 sw $s0, 0($sp) sw $s1, 4($sp)
bgt $a1, 0, next1 # if (n > 0) goto next1;
addi $sp, $sp, 8 # Non serve ripristinare $s0 and $s1 li $v0, -1
jr $ra # return -1;
next1:
lw $s1, 0($a0) # m = *v;
add $a0, $a0, 4 # v = v+1;
li $s0, 1 # i = 1;
init_for:
bge $s0, $a1, exit_for # if (i >= n) goto exit_for;
lw $t0, 0($a0) # $t0 = *v
bge $t0, $s1, next2 # if (*v >= m) goto next2;
ori $s1, $t0, 0 # m = *v;
next2:
add $a0, $a0, 4 # v = v+1;
addi $s0, $s0, 1 # i++;
j init_for;
exit_for:
sw $s1, 0($a2) # *min = m;
lw $s0, 0($sp) lw $s1, 4($sp) addi $sp, $sp, 8
li $v0, 1
jr $ra # return 1;
