Cognome e Nome: Matricola: Mod 2: Mod 1+2:
Architettura degli Elaboratori (modulo II) (Compito 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.
Il sistema include anche una cache 4-way set associative la cui parte dati `e 1 MB, e ogni blocco ha dimensione 2 word.
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. Quanti set contiene la cache, e qual `e la dimensione dell’INDEX della cache?
5. Dato l’indirizzo fisico 0x11FA (gli zeri pi`u significativi sono omessi), individuare il TAG rispetto alla cache.
Soluzione
1. Poich`e gli insiemi sono 256, allora INDEX = log2256 = 8 b. Quindi PAGE OFFSET = DIM IND VIRT - INDEX - TAG = 32 - 8 - 13 = 11 b, per cui DIM PAGE = 211= 2048 B.
N PAG VIRTUALE = DIM IND VIRT - PAGE OFFSET = 32 - 11 = 21 b.
2. 4B * NUM SET * NUM VIE = 4 ∗ 2 ∗ 28= 211= 2048 B.
3. N PAG FISICA = DIM ENTRY - 4BIT - TAG = 32 - 4 - 13 = 15 b.
IND FISICO = N PAG FISICA + PAGE OFFSET = 15 + 11 = 26 b.
4. Il numero totale di blocchi `e: NUM BLOCCHI = 1 MB / 2 word = 220/23= 217. Il numero di set `e: NUM SET
= NUM BLOCCHI / 4 vie = 217/22= 215. INDEX = log NUM SET = log 215= 15 b.
5. OFFSET = log 2 word = log 23 = 3 b. Quindi INDEX:OFFSET = 15+3 = 18 b, e TAG = IND FISICO - INDEX - OFFSET = 26 - 18 = 8 b. Rispetto all’indirizzo fisico 0x11FA, abbiamo TAG = 000000002.
Esercizio 2
Tradurre in assembly MIPS la funzione C:
void find min(int *v, int n, int *min)
il cui risultato deve essere memorizzato nella variabile min passata per indirizzo.
void find_min(int *v, int n, int *min) { int i, m;
m = *v;
v = v+1;
for (i=1; i < n; i++) { if (*v < m)
m = *v;
v = v+1;
}
*min = m;
}
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 il registro $s0 e $s1 per memorizzare le variabili locali i e m. E’ inoltre possibile usare pseudo-istruzioni come blt, ble, bgt e bge.
Soluzione
Il codice con if-goto:
void find_min(int *v, int n, int *min) { int i, m;
m = *v;
v = v+1;
i = 1;
init_for:
if (i >= n) goto exit_for;
if (*v >= m) goto next1;
m = *v;
next1:
v = v+1;
i++;
goto init_for;
exit_for:
*min = m;
}
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)
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, next1 # if (*v >= m) goto next1;
ori $s1, $t0, 0 # m = *v;
next1:
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 jr $ra
Esercizio 3
Si consideri il seguente codice MIPS:
1. add $4, $6, $7 2. and $2, $4, $8 3. sw $4, 0($2) 4. lw $3, 10($5) 5. beq $3, $4, label 6. nop
1. Mostrare le dipendenze RAW.
2. Data l’architettura a pipeline a 5 stadi vista a lezione con hazard control unit, forwarding, register file speciale, disegnare il diagramma temporale di esecuzione. Si consideri inoltre la presenza del delayed branch, con il branch che termina la sua esecuzione nello stadio ID.
3. Discutere quali dipendenze vengono risolte impiegando il forwarding (indicando se il dato viene prelevato dal reg EX/ME o ME/WB) o il register file speciale.
4. E’ possibile modificare il codice in modo la ridurre gli stalli e riempire il branch delay slot con un’istruzione utile?
Soluzione
1. Le dipendenze sono 1 → 2 (reg. $4), 1 → 3 (reg. $4), 1 → 5 (reg. $4), 2 → 3 (reg. $2), 4 → 5 (reg. $3).
2. Il diagramma di esecuzione `e il seguente:
1 2 3 4 5 6 7 8 9 10 11 12
1. add IF ID EX ME WB
2. and IF ID EX ME WB
3. sw IF ID EX ME WB
4. lw IF ID EX ME WB
5. beq IF ID <ID><ID> EX ME WB
6. nop IF <IF><IF> ID EX ME WB
3. La dipendenza 1 → 2 viene risolta tramite forwarding (tra reg. EX/ME e ingresso stadio EXE).
La dipendenza 1 → 3 viene risolta tramite forwarding (tra reg. ME/WB e ingresso stadio EXE).
La dipendenza 1 → 5 viene risolta naturalmente (WB di 1 avviene prima di ID di 5).
La dipendenza 2 → 3 viene risolta tramite forwarding (tra reg. EX/ME e ingresso stadio EXE).
La dipendenza 4 → 5 viene risolta tramite registrer file speciale.
4. L’istruzione lw `e indipendente e ne pu`o essere anticipata l’esecuzione. Inoltre l’istruzione sw pu`o essere spostata nel delay slot. Lo scheduling che continua a rispettare le dipendenze precenti `e il seguente:
4. lw $3, 10($5) 1. add $4, $6, $7 2. and $2, $4, $8 5. beq $3, $4, label 3. sw $4, 0($2)
Il nuovo diagramma di esecuzione `e il seguente (lo stallo serve per far rispettare la dipendenza 1 → 5):
1 2 3 4 5 6 7 8 9 10 11 12
4. lw IF ID EX ME WB
1. add IF ID EX ME WB
2. and IF ID EX ME WB
5. beq IF ID <ID> ME WB
3. sw IF <IF> ID EX ME WB
Domande
1. L’I/O si pu`o programmare sia con il polling e sia tramite interrupt. Quando conviene l’uno o l’altro metodo? Distinguere tra dispositivi lenti o veloci, e per i veloci i casi in cui i dispositivi trasferiscono in continuazione o raramente.
2. Comparare transazioni su bus sincroni e asincroni per portare a termine operazioni di I/O.
3. Un cache miss pu`o dar luogo ad un page fault miss? Motivare.
