Cognome e Nome: Matricola: Mod 2: Mod 1+2:
Architettura degli Elaboratori (modulo II)
(Compito 18 Giugno 2019)Esercizio 1
Considerare un sistema di memoria virtuale paginata con indirizzo virtuale di 32 b, che include una Page Table (PT) di 2 M ingressi, ognuno composto da 3 B (4 bit + Numero di Pagina Fisica).
Il sistema include anche una cache 4-way set associative la cui parte dati ˜A¨ 256 KB, e ogni blocco ha dimensione 16 B.
Rispondere ai seguenti quesiti:
1. Calcolare il numero di bit dell’Indirizzo Fisico e la dimensione della Pagina.
2. Calcolare il numero di blocchi della cache e il numero di insiemi (set) della cache.
3. Calcolare la dimensione di INDEX/TAG/OFFSET dell’indirizzo per l’accesso alla cache.
4. Data la sequenza di indirizzi fisici seguente, quali di questi saranno hit/miss, e quale sar ˜A la situazione finale della cache? Si consideri che la cache ˜A¨ inizialmente vuota.
0x09FA1200 0x09FA1204 0x0AFA1204 0x0BFA1204 0x0CFA1204 0x0DFA1204
Soluzione
1. NUM PAG VIRT (VPN) log 2M = log 221= 21 b.
PAG OFFSET = 32 - VPN = 32 - 21 = 11 b.
DIM PAGINA = 211 = 2 KB.
NUM PAG FISICA (PPN) = Dim entry PT - 4 b = 24 - 4 = 20 b.
IND FISICO = PPN + PAGE OFFSET = 20 + 11 = 31 b.
2. NUM BLOCCHI = DIM CACHE / DIM BLOCCO = 256 KB / 16 B = 28210/24= 214. NUM SET = 214/4 vie = 212.
3. INDEX = log NUM SET = log 212= 12 b.
OFFSET = log DIM BLOCCO = log 24= 4 b.
TAG = IND FISICO - (INDEX+OFFSET) = 31 - (12+4) = 15 b.
4. Tutti gli indirizzi fanno riferimento a INDEX = 0x120.
0x09FA1200 miss (TAG = 09FA) 0x09FA1204 hit (TAG = 09FA) 0x0AFA1204 miss (TAG = 0AFA) 0x0BFA1204 miss (TAG = 0BFA) 0x0CFA1204 miss (TAG = 0CFA)
0x0DFA1204 miss (TAG = 0DFA), rimpiazzo LRU del blocco in via 0
via 0 via 1 via 2 via 3
--- set con INDEX=120: | TAG=0DFA | TAG=0AFA | TAG=0BFA | TAG=0CFA | ---
Esercizio 2
Considerare la seguente funzione C, il cui risultato deve essere memorizzato nelle ultime due variabili passate per indirizzo:
void sum_even_odd(int v[], int n, int *sum_even, int *sum_odd) { int i, t1, t2;
t1 = 0;
for (i=0; i < n; i=i+2) t1 = t1 + v[i];
t2 = 0;
for (i=1; i < n; i=i+2) t2 = t2 + v[i];
*sum_even = t1;
*sum_odd = t2;
}
1. Tradurre in C con if-goto e goto.
2. Tradurre in assembly MIPS, completando almeno uno dei due for.
Usare il registro $s0 per la variabile i, e i registri $t1 e $t2 per memorizzare le variabili locali t1 e t2. E’ inoltre possibile usare pseudo-istruzioni come blt, ble, bgt e bge.
Soluzione
Il codice con if-goto:
void sum_even_odd_goto(int v[], int n, int *sum_even, int *sum_odd) { int i, t1, t2;
t1 = 0;
i = 0;
init_f1:
if (i >= n) goto exif_f1;
t1 += v[i];
i += 2;
goto init_f1;
exif_f1:
t2 = 0;
i = 1;
init_f2:
if (i >= n) goto exif_f2;
t2 += v[i];
i += 2;
goto init_f2;
exif_f2:
*sum_even = t1;
*sum_odd = t2;
}
Traduzione MIPS:
sum_even_odd:
# PARAMETRI: $a0= v, $a1 = n, $a2 = *sum_even, $a3 = *sum_odd
# VARIABILI LOCALI: $s0 = i $t1 = t1 $t2 = t2
addi $sp, $sp, -4 sw $s0, 0($sp)
li $t1, 0 # t1 = 0;
li $s0, 0 # i = 0;
init_f1:
bge $s0, $a1, exit_f1 # if (i >= n) goto exif_f1;
sll $t0, $s0, 2 # $t0 = i*4 add $t0, $a0, $t0 # $t0 = &v[i]
lw $t3, 0($t0) # $t3 = v[i]
add $t1, $t1, $t3 # t1 += v[i];
addi $s0, $s0, 2 # i += 2;
j init_f1 # goto init_f1;
exif_f1:
li $t2, 0 # t2 = 0;
li $s0, 1 # i = 1;
init_f2:
bge $s0, $a1, exit_f2 # if (i >= n) goto exif_f2;
sll $t0, $s0, 2 # $t0 = i*4 add $t0, $a0, $t0 # $t0 = &v[i]
lw $t3, 0($t0) # $t3 = v[i]
add $t2, $t2, $t3 # t2 += v[i];
addi $s0, $s0, 2 # i += 2;
j init_f2; # goto init_f2;
exif_f2:
sw $t1, 0($a2) # *sum_even = t1;
sw $t2, 0($a3) # *sum_odd = t2;
lw $s0, 0($sp) addi $sp, $sp, 4 jr $ra
Esercizio 3
Dato il seguente loop:
loop:
1. lw $10, 0($8) 2. add $5, $10, $5 3. addi $8, $8, 4 4. sw $5, -4($8) 5. bne $8, $7, loop
in esecuzione su un processore MIPS pipeline a 5 stadi come quello visto a lezione, con register file ottimizzato (scrive un nuovo registro nella prima parte di un ciclo, e legge una coppia di registri nella seconda parte del ciclo) e con hazard detection unit. Inoltre, per limitare a 1 il delay slot delle branch, queste ultime istruzioni terminano nello stadio ID.
1. Individuare le dipendenze RAW;
2. Disegnare il diagramma di esecuzione SENZA forwarding;
3. Disegnare il diagramma di esecuzione CON forwarding (indicando anche i forward con le freccette).
Soluzione
Le dipendenze RAW sono:
1->2 (reg. $10) 2->4 (reg. $5) 3->4 (reg. $8) 3->5 (reg. $8)
SENZA forwarding:
1. lw $10, 0($8) IF ID EX ME WB
2. add $5, $10, $5 IF ID <ID> <ID> EX ME WB 3. addi $8, $8, 4 IF <IF> <IF> ID EX ME WB
4. sw $5, -4($8) IF ID <ID> <ID> EX ME WB
5. bne $8, $7, loop IF <IF> <IF> ID EX ME WB
CON forwarding:
1. lw $10, 0($8) IF ID EX ME WB
2. add $5, $10, $5 IF ID <ID> EX ME WB
3. addi $8, $8, 4 IF <IF> ID EX ME WB
4. sw $5, -4($8) IF ID EX ME WB
5. bne $8, $7, loop IF ID EX ME WB
Riguardo le varie dipendenze, abbiamo:
1->2 (reg. $10) => forwarding, da registro ME/WB a unit~A EX 2->4 (reg. $11) => forwarding, da registro ME/WB a unit~A EX 3->4 (reg. $8) => forwarding, da registro EX/ME a unit~A EX 3->5 (reg. $8) => forwarding, da registro EX/ME a unit~A ID
Domande
1. Determinare la formula per calcolare il costo di acceso a un blocco dati dal disco. Quali tecniche si potrebbero adottare per aumentare la banda reale?
2. A cosa si riferiscono e in che cosa consistono le politiche write-back e write-through utilizzare per gestire le gerarchie di memoria?
3. I singoli core dei moderni microprocessori multicore sono superscalari e eseguono le istruzioni out-of-order.
Commentare.
